Coverage Report

Created: 2023-09-30 09:22

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- UncheckedOptionalAccessModel.cpp ------------------------*- C++ -*-===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
//  This file defines a dataflow analysis that detects unsafe uses of optional
10
//  values.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h"
15
#include "clang/AST/ASTContext.h"
16
#include "clang/AST/DeclCXX.h"
17
#include "clang/AST/Expr.h"
18
#include "clang/AST/ExprCXX.h"
19
#include "clang/AST/Stmt.h"
20
#include "clang/ASTMatchers/ASTMatchers.h"
21
#include "clang/ASTMatchers/ASTMatchersMacros.h"
22
#include "clang/Analysis/CFG.h"
23
#include "clang/Analysis/FlowSensitive/CFGMatchSwitch.h"
24
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
25
#include "clang/Analysis/FlowSensitive/Formula.h"
26
#include "clang/Analysis/FlowSensitive/NoopLattice.h"
27
#include "clang/Analysis/FlowSensitive/StorageLocation.h"
28
#include "clang/Analysis/FlowSensitive/Value.h"
29
#include "clang/Basic/SourceLocation.h"
30
#include "llvm/ADT/StringRef.h"
31
#include "llvm/Support/Casting.h"
32
#include "llvm/Support/ErrorHandling.h"
33
#include <cassert>
34
#include <memory>
35
#include <optional>
36
#include <utility>
37
38
namespace clang {
39
namespace dataflow {
40
41
static bool isTopLevelNamespaceWithName(const NamespaceDecl &NS,
42
5.06k
                                        llvm::StringRef Name) {
43
5.06k
  return NS.getDeclName().isIdentifier() && NS.getName() == Name &&
44
5.06k
         
NS.getParent() != nullptr5.03k
&&
NS.getParent()->isTranslationUnit()5.03k
;
45
5.06k
}
46
47
7.99k
static bool hasOptionalClassName(const CXXRecordDecl &RD) {
48
7.99k
  if (!RD.getDeclName().isIdentifier())
49
0
    return false;
50
51
7.99k
  if (RD.getName() == "optional") {
52
5.06k
    if (const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext()))
53
5.06k
      return N->isStdNamespace() || 
isTopLevelNamespaceWithName(*N, "absl")2.53k
;
54
0
    return false;
55
5.06k
  }
56
57
2.93k
  if (RD.getName() == "Optional") {
58
    // Check whether namespace is "::base" or "::folly".
59
2.51k
    const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext());
60
2.51k
    return N != nullptr && (isTopLevelNamespaceWithName(*N, "base") ||
61
2.51k
                            
isTopLevelNamespaceWithName(*N, "folly")15
);
62
2.51k
  }
63
64
417
  return false;
65
2.93k
}
66
67
namespace {
68
69
using namespace ::clang::ast_matchers;
70
using LatticeTransferState = TransferState<NoopLattice>;
71
72
7.50k
AST_MATCHER(CXXRecordDecl, hasOptionalClassNameMatcher) {
73
7.50k
  return hasOptionalClassName(Node);
74
7.50k
}
75
76
14.3k
DeclarationMatcher optionalClass() {
77
14.3k
  return classTemplateSpecializationDecl(
78
14.3k
      hasOptionalClassNameMatcher(),
79
14.3k
      hasTemplateArgument(0, refersToType(type().bind("T"))));
80
14.3k
}
81
82
9.47k
auto optionalOrAliasType() {
83
9.47k
  return hasUnqualifiedDesugaredType(
84
9.47k
      recordType(hasDeclaration(optionalClass())));
85
9.47k
}
86
87
/// Matches any of the spellings of the optional types and sugar, aliases, etc.
88
6.31k
auto hasOptionalType() { return hasType(optionalOrAliasType()); }
89
90
auto isOptionalMemberCallWithNameMatcher(
91
    ast_matchers::internal::Matcher<NamedDecl> matcher,
92
2.45k
    const std::optional<StatementMatcher> &Ignorable = std::nullopt) {
93
2.45k
  auto Exception = unless(Ignorable ? 
expr(anyOf(*Ignorable, cxxThisExpr()))351
94
2.45k
                                    : 
cxxThisExpr()2.10k
);
95
2.45k
  return cxxMemberCallExpr(
96
2.45k
      on(expr(Exception,
97
2.45k
              anyOf(hasOptionalType(),
98
2.45k
                    hasType(pointerType(pointee(optionalOrAliasType())))))),
99
2.45k
      callee(cxxMethodDecl(matcher)));
100
2.45k
}
101
102
auto isOptionalOperatorCallWithName(
103
    llvm::StringRef operator_name,
104
1.40k
    const std::optional<StatementMatcher> &Ignorable = std::nullopt) {
105
1.40k
  return cxxOperatorCallExpr(
106
1.40k
      hasOverloadedOperatorName(operator_name),
107
1.40k
      callee(cxxMethodDecl(ofClass(optionalClass()))),
108
1.40k
      Ignorable ? 
callExpr(unless(hasArgument(0, *Ignorable)))702
:
callExpr()702
);
109
1.40k
}
110
111
351
auto isMakeOptionalCall() {
112
351
  return callExpr(callee(functionDecl(hasAnyName(
113
351
                      "std::make_optional", "base::make_optional",
114
351
                      "absl::make_optional", "folly::make_optional"))),
115
351
                  hasOptionalType());
116
351
}
117
118
3.51k
auto nulloptTypeDecl() {
119
3.51k
  return namedDecl(hasAnyName("std::nullopt_t", "absl::nullopt_t",
120
3.51k
                              "base::nullopt_t", "folly::None"));
121
3.51k
}
122
123
2.10k
auto hasNulloptType() { return hasType(nulloptTypeDecl()); }
124
125
// `optional` or `nullopt_t`
126
1.40k
auto hasAnyOptionalType() {
127
1.40k
  return hasType(hasUnqualifiedDesugaredType(
128
1.40k
      recordType(hasDeclaration(anyOf(nulloptTypeDecl(), optionalClass())))));
129
1.40k
}
130
131
351
auto inPlaceClass() {
132
351
  return recordDecl(hasAnyName("std::in_place_t", "absl::in_place_t",
133
351
                               "base::in_place_t", "folly::in_place_t"));
134
351
}
135
136
351
auto isOptionalNulloptConstructor() {
137
351
  return cxxConstructExpr(
138
351
      hasOptionalType(),
139
351
      hasDeclaration(cxxConstructorDecl(parameterCountIs(1),
140
351
                                        hasParameter(0, hasNulloptType()))));
141
351
}
142
143
351
auto isOptionalInPlaceConstructor() {
144
351
  return cxxConstructExpr(hasOptionalType(),
145
351
                          hasArgument(0, hasType(inPlaceClass())));
146
351
}
147
148
351
auto isOptionalValueOrConversionConstructor() {
149
351
  return cxxConstructExpr(
150
351
      hasOptionalType(),
151
351
      unless(hasDeclaration(
152
351
          cxxConstructorDecl(anyOf(isCopyConstructor(), isMoveConstructor())))),
153
351
      argumentCountIs(1), hasArgument(0, unless(hasNulloptType())));
154
351
}
155
156
351
auto isOptionalValueOrConversionAssignment() {
157
351
  return cxxOperatorCallExpr(
158
351
      hasOverloadedOperatorName("="),
159
351
      callee(cxxMethodDecl(ofClass(optionalClass()))),
160
351
      unless(hasDeclaration(cxxMethodDecl(
161
351
          anyOf(isCopyAssignmentOperator(), isMoveAssignmentOperator())))),
162
351
      argumentCountIs(2), hasArgument(1, unless(hasNulloptType())));
163
351
}
164
165
351
auto isNulloptConstructor() {
166
351
  return cxxConstructExpr(hasNulloptType(), argumentCountIs(1),
167
351
                          hasArgument(0, hasNulloptType()));
168
351
}
169
170
351
auto isOptionalNulloptAssignment() {
171
351
  return cxxOperatorCallExpr(hasOverloadedOperatorName("="),
172
351
                             callee(cxxMethodDecl(ofClass(optionalClass()))),
173
351
                             argumentCountIs(2),
174
351
                             hasArgument(1, hasNulloptType()));
175
351
}
176
177
351
auto isStdSwapCall() {
178
351
  return callExpr(callee(functionDecl(hasName("std::swap"))),
179
351
                  argumentCountIs(2), hasArgument(0, hasOptionalType()),
180
351
                  hasArgument(1, hasOptionalType()));
181
351
}
182
183
351
auto isStdForwardCall() {
184
351
  return callExpr(callee(functionDecl(hasName("std::forward"))),
185
351
                  argumentCountIs(1), hasArgument(0, hasOptionalType()));
186
351
}
187
188
constexpr llvm::StringLiteral ValueOrCallID = "ValueOrCall";
189
190
351
auto isValueOrStringEmptyCall() {
191
  // `opt.value_or("").empty()`
192
351
  return cxxMemberCallExpr(
193
351
      callee(cxxMethodDecl(hasName("empty"))),
194
351
      onImplicitObjectArgument(ignoringImplicit(
195
351
          cxxMemberCallExpr(on(expr(unless(cxxThisExpr()))),
196
351
                            callee(cxxMethodDecl(hasName("value_or"),
197
351
                                                 ofClass(optionalClass()))),
198
351
                            hasArgument(0, stringLiteral(hasSize(0))))
199
351
              .bind(ValueOrCallID))));
200
351
}
201
202
351
auto isValueOrNotEqX() {
203
1.05k
  auto ComparesToSame = [](ast_matchers::internal::Matcher<Stmt> Arg) {
204
1.05k
    return hasOperands(
205
1.05k
        ignoringImplicit(
206
1.05k
            cxxMemberCallExpr(on(expr(unless(cxxThisExpr()))),
207
1.05k
                              callee(cxxMethodDecl(hasName("value_or"),
208
1.05k
                                                   ofClass(optionalClass()))),
209
1.05k
                              hasArgument(0, Arg))
210
1.05k
                .bind(ValueOrCallID)),
211
1.05k
        ignoringImplicit(Arg));
212
1.05k
  };
213
214
  // `opt.value_or(X) != X`, for X is `nullptr`, `""`, or `0`. Ideally, we'd
215
  // support this pattern for any expression, but the AST does not have a
216
  // generic expression comparison facility, so we specialize to common cases
217
  // seen in practice.  FIXME: define a matcher that compares values across
218
  // nodes, which would let us generalize this to any `X`.
219
351
  return binaryOperation(hasOperatorName("!="),
220
351
                         anyOf(ComparesToSame(cxxNullPtrLiteralExpr()),
221
351
                               ComparesToSame(stringLiteral(hasSize(0))),
222
351
                               ComparesToSame(integerLiteral(equals(0)))));
223
351
}
224
225
351
auto isCallReturningOptional() {
226
351
  return callExpr(hasType(qualType(anyOf(
227
351
      optionalOrAliasType(), referenceType(pointee(optionalOrAliasType()))))));
228
351
}
229
230
template <typename L, typename R>
231
1.05k
auto isComparisonOperatorCall(L lhs_arg_matcher, R rhs_arg_matcher) {
232
1.05k
  return cxxOperatorCallExpr(
233
1.05k
      anyOf(hasOverloadedOperatorName("=="), hasOverloadedOperatorName("!=")),
234
1.05k
      argumentCountIs(2), hasArgument(0, lhs_arg_matcher),
235
1.05k
      hasArgument(1, rhs_arg_matcher));
236
1.05k
}
UncheckedOptionalAccessModel.cpp:auto clang::dataflow::(anonymous namespace)::isComparisonOperatorCall<clang::ast_matchers::internal::PolymorphicMatcher<clang::ast_matchers::internal::matcher_hasType0Matcher, void (clang::ast_matchers::internal::TypeList<clang::Expr, clang::FriendDecl, clang::TypedefNameDecl, clang::ValueDecl, clang::CXXBaseSpecifier>), clang::ast_matchers::internal::Matcher<clang::QualType> >, clang::ast_matchers::internal::PolymorphicMatcher<clang::ast_matchers::internal::matcher_hasType0Matcher, void (clang::ast_matchers::internal::TypeList<clang::Expr, clang::FriendDecl, clang::TypedefNameDecl, clang::ValueDecl, clang::CXXBaseSpecifier>), clang::ast_matchers::internal::Matcher<clang::QualType> > >(clang::ast_matchers::internal::PolymorphicMatcher<clang::ast_matchers::internal::matcher_hasType0Matcher, void (clang::ast_matchers::internal::TypeList<clang::Expr, clang::FriendDecl, clang::TypedefNameDecl, clang::ValueDecl, clang::CXXBaseSpecifier>), clang::ast_matchers::internal::Matcher<clang::QualType> >, clang::ast_matchers::internal::PolymorphicMatcher<clang::ast_matchers::internal::matcher_hasType0Matcher, void (clang::ast_matchers::internal::TypeList<clang::Expr, clang::FriendDecl, clang::TypedefNameDecl, clang::ValueDecl, clang::CXXBaseSpecifier>), clang::ast_matchers::internal::Matcher<clang::QualType> >)
Line
Count
Source
231
351
auto isComparisonOperatorCall(L lhs_arg_matcher, R rhs_arg_matcher) {
232
351
  return cxxOperatorCallExpr(
233
351
      anyOf(hasOverloadedOperatorName("=="), hasOverloadedOperatorName("!=")),
234
351
      argumentCountIs(2), hasArgument(0, lhs_arg_matcher),
235
351
      hasArgument(1, rhs_arg_matcher));
236
351
}
UncheckedOptionalAccessModel.cpp:auto clang::dataflow::(anonymous namespace)::isComparisonOperatorCall<clang::ast_matchers::internal::PolymorphicMatcher<clang::ast_matchers::internal::matcher_hasType0Matcher, void (clang::ast_matchers::internal::TypeList<clang::Expr, clang::FriendDecl, clang::TypedefNameDecl, clang::ValueDecl, clang::CXXBaseSpecifier>), clang::ast_matchers::internal::Matcher<clang::QualType> >, clang::ast_matchers::internal::VariadicOperatorMatcher<clang::ast_matchers::internal::PolymorphicMatcher<clang::ast_matchers::internal::matcher_hasType0Matcher, void (clang::ast_matchers::internal::TypeList<clang::Expr, clang::FriendDecl, clang::TypedefNameDecl, clang::ValueDecl, clang::CXXBaseSpecifier>), clang::ast_matchers::internal::Matcher<clang::QualType> > > >(clang::ast_matchers::internal::PolymorphicMatcher<clang::ast_matchers::internal::matcher_hasType0Matcher, void (clang::ast_matchers::internal::TypeList<clang::Expr, clang::FriendDecl, clang::TypedefNameDecl, clang::ValueDecl, clang::CXXBaseSpecifier>), clang::ast_matchers::internal::Matcher<clang::QualType> >, clang::ast_matchers::internal::VariadicOperatorMatcher<clang::ast_matchers::internal::PolymorphicMatcher<clang::ast_matchers::internal::matcher_hasType0Matcher, void (clang::ast_matchers::internal::TypeList<clang::Expr, clang::FriendDecl, clang::TypedefNameDecl, clang::ValueDecl, clang::CXXBaseSpecifier>), clang::ast_matchers::internal::Matcher<clang::QualType> > >)
Line
Count
Source
231
351
auto isComparisonOperatorCall(L lhs_arg_matcher, R rhs_arg_matcher) {
232
351
  return cxxOperatorCallExpr(
233
351
      anyOf(hasOverloadedOperatorName("=="), hasOverloadedOperatorName("!=")),
234
351
      argumentCountIs(2), hasArgument(0, lhs_arg_matcher),
235
351
      hasArgument(1, rhs_arg_matcher));
236
351
}
UncheckedOptionalAccessModel.cpp:auto clang::dataflow::(anonymous namespace)::isComparisonOperatorCall<clang::ast_matchers::internal::VariadicOperatorMatcher<clang::ast_matchers::internal::PolymorphicMatcher<clang::ast_matchers::internal::matcher_hasType0Matcher, void (clang::ast_matchers::internal::TypeList<clang::Expr, clang::FriendDecl, clang::TypedefNameDecl, clang::ValueDecl, clang::CXXBaseSpecifier>), clang::ast_matchers::internal::Matcher<clang::QualType> > >, clang::ast_matchers::internal::PolymorphicMatcher<clang::ast_matchers::internal::matcher_hasType0Matcher, void (clang::ast_matchers::internal::TypeList<clang::Expr, clang::FriendDecl, clang::TypedefNameDecl, clang::ValueDecl, clang::CXXBaseSpecifier>), clang::ast_matchers::internal::Matcher<clang::QualType> > >(clang::ast_matchers::internal::VariadicOperatorMatcher<clang::ast_matchers::internal::PolymorphicMatcher<clang::ast_matchers::internal::matcher_hasType0Matcher, void (clang::ast_matchers::internal::TypeList<clang::Expr, clang::FriendDecl, clang::TypedefNameDecl, clang::ValueDecl, clang::CXXBaseSpecifier>), clang::ast_matchers::internal::Matcher<clang::QualType> > >, clang::ast_matchers::internal::PolymorphicMatcher<clang::ast_matchers::internal::matcher_hasType0Matcher, void (clang::ast_matchers::internal::TypeList<clang::Expr, clang::FriendDecl, clang::TypedefNameDecl, clang::ValueDecl, clang::CXXBaseSpecifier>), clang::ast_matchers::internal::Matcher<clang::QualType> >)
Line
Count
Source
231
351
auto isComparisonOperatorCall(L lhs_arg_matcher, R rhs_arg_matcher) {
232
351
  return cxxOperatorCallExpr(
233
351
      anyOf(hasOverloadedOperatorName("=="), hasOverloadedOperatorName("!=")),
234
351
      argumentCountIs(2), hasArgument(0, lhs_arg_matcher),
235
351
      hasArgument(1, rhs_arg_matcher));
236
351
}
237
238
/// Ensures that `Expr` is mapped to a `BoolValue` and returns its formula.
239
138
const Formula &forceBoolValue(Environment &Env, const Expr &Expr) {
240
138
  auto *Value = cast_or_null<BoolValue>(Env.getValue(Expr));
241
138
  if (Value != nullptr)
242
18
    return Value->formula();
243
244
120
  Value = &Env.makeAtomicBoolValue();
245
120
  Env.setValue(Expr, *Value);
246
120
  return Value->formula();
247
138
}
248
249
/// Sets `HasValueVal` as the symbolic value that represents the "has_value"
250
/// property of the optional value `OptionalVal`.
251
1.49k
void setHasValue(Value &OptionalVal, BoolValue &HasValueVal) {
252
1.49k
  OptionalVal.setProperty("has_value", HasValueVal);
253
1.49k
}
254
255
/// Creates a symbolic value for an `optional` value at an existing storage
256
/// location. Uses `HasValueVal` as the symbolic value of the "has_value"
257
/// property.
258
RecordValue &createOptionalValue(RecordStorageLocation &Loc,
259
1.12k
                                 BoolValue &HasValueVal, Environment &Env) {
260
1.12k
  auto &OptionalVal = Env.create<RecordValue>(Loc);
261
1.12k
  Env.setValue(Loc, OptionalVal);
262
1.12k
  setHasValue(OptionalVal, HasValueVal);
263
1.12k
  return OptionalVal;
264
1.12k
}
265
266
/// Returns the symbolic value that represents the "has_value" property of the
267
/// optional value `OptionalVal`. Returns null if `OptionalVal` is null.
268
600
BoolValue *getHasValue(Environment &Env, Value *OptionalVal) {
269
600
  if (OptionalVal != nullptr) {
270
573
    auto *HasValueVal =
271
573
        cast_or_null<BoolValue>(OptionalVal->getProperty("has_value"));
272
573
    if (HasValueVal == nullptr) {
273
24
      HasValueVal = &Env.makeAtomicBoolValue();
274
24
      OptionalVal->setProperty("has_value", *HasValueVal);
275
24
    }
276
573
    return HasValueVal;
277
573
  }
278
27
  return nullptr;
279
600
}
280
281
/// Returns true if and only if `Type` is an optional type.
282
1.12k
bool isOptionalType(QualType Type) {
283
1.12k
  if (!Type->isRecordType())
284
642
    return false;
285
483
  const CXXRecordDecl *D = Type->getAsCXXRecordDecl();
286
483
  return D != nullptr && hasOptionalClassName(*D);
287
1.12k
}
288
289
/// Returns the number of optional wrappers in `Type`.
290
///
291
/// For example, if `Type` is `optional<optional<int>>`, the result of this
292
/// function will be 2.
293
732
int countOptionalWrappers(const ASTContext &ASTCtx, QualType Type) {
294
732
  if (!isOptionalType(Type))
295
672
    return 0;
296
60
  return 1 + countOptionalWrappers(
297
60
                 ASTCtx,
298
60
                 cast<ClassTemplateSpecializationDecl>(Type->getAsRecordDecl())
299
60
                     ->getTemplateArgs()
300
60
                     .get(0)
301
60
                     .getAsType()
302
60
                     .getDesugaredType(ASTCtx));
303
732
}
304
305
/// Tries to initialize the `optional`'s value (that is, contents), and return
306
/// its location. Returns nullptr if the value can't be represented.
307
StorageLocation *maybeInitializeOptionalValueMember(QualType Q,
308
                                                    Value &OptionalVal,
309
963
                                                    Environment &Env) {
310
  // The "value" property represents a synthetic field. As such, it needs
311
  // `StorageLocation`, like normal fields (and other variables). So, we model
312
  // it with a `PointerValue`, since that includes a storage location.  Once
313
  // the property is set, it will be shared by all environments that access the
314
  // `Value` representing the optional (here, `OptionalVal`).
315
963
  if (auto *ValueProp = OptionalVal.getProperty("value")) {
316
357
    auto *ValuePtr = clang::cast<PointerValue>(ValueProp);
317
357
    auto &ValueLoc = ValuePtr->getPointeeLoc();
318
357
    if (Env.getValue(ValueLoc) != nullptr)
319
42
      return &ValueLoc;
320
321
    // The property was previously set, but the value has been lost. This can
322
    // happen in various situations, for example:
323
    // - Because of an environment merge (where the two environments mapped the
324
    //   property to different values, which resulted in them both being
325
    //   discarded).
326
    // - When two blocks in the CFG, with neither a dominator of the other,
327
    //   visit the same optional value. (FIXME: This is something we can and
328
    //   should fix -- see also the lengthy FIXME below.)
329
    // - Or even when a block is revisited during testing to collect
330
    //   per-statement state.
331
    // FIXME: This situation means that the optional contents are not shared
332
    // between branches and the like. Practically, this lack of sharing
333
    // reduces the precision of the model when the contents are relevant to
334
    // the check, like another optional or a boolean that influences control
335
    // flow.
336
315
    if (ValueLoc.getType()->isRecordType()) {
337
54
      refreshRecordValue(cast<RecordStorageLocation>(ValueLoc), Env);
338
54
      return &ValueLoc;
339
261
    } else {
340
261
      auto *ValueVal = Env.createValue(ValueLoc.getType());
341
261
      if (ValueVal == nullptr)
342
0
        return nullptr;
343
261
      Env.setValue(ValueLoc, *ValueVal);
344
261
      return &ValueLoc;
345
261
    }
346
315
  }
347
348
606
  auto Ty = Q.getNonReferenceType();
349
606
  auto &ValueLoc = Env.createObject(Ty);
350
606
  auto &ValuePtr = Env.create<PointerValue>(ValueLoc);
351
  // FIXME:
352
  // The change we make to the `value` property below may become visible to
353
  // other blocks that aren't successors of the current block and therefore
354
  // don't see the change we made above mapping `ValueLoc` to `ValueVal`. For
355
  // example:
356
  //
357
  //   void target(optional<int> oo, bool b) {
358
  //     // `oo` is associated with a `RecordValue` here, which we will call
359
  //     // `OptionalVal`.
360
  //
361
  //     // The `has_value` property is set on `OptionalVal` (but not the
362
  //     // `value` property yet).
363
  //     if (!oo.has_value()) return;
364
  //
365
  //     if (b) {
366
  //       // Let's assume we transfer the `if` branch first.
367
  //       //
368
  //       // This causes us to call `maybeInitializeOptionalValueMember()`,
369
  //       // which causes us to set the `value` property on `OptionalVal`
370
  //       // (which had not been set until this point). This `value` property
371
  //       // refers to a `PointerValue`, which in turn refers to a
372
  //       // StorageLocation` that is associated to an `IntegerValue`.
373
  //       oo.value();
374
  //     } else {
375
  //       // Let's assume we transfer the `else` branch after the `if` branch.
376
  //       //
377
  //       // We see the `value` property that the `if` branch set on
378
  //       // `OptionalVal`, but in the environment for this block, the
379
  //       // `StorageLocation` in the `PointerValue` is not associated with any
380
  //       // `Value`.
381
  //       oo.value();
382
  //     }
383
  //   }
384
  //
385
  // This situation is currently "saved" by the code above that checks whether
386
  // the `value` property is already set, and if, the `ValueLoc` is not
387
  // associated with a `ValueVal`, creates a new `ValueVal`.
388
  //
389
  // However, what we should really do is to make sure that the change to the
390
  // `value` property does not "leak" to other blocks that are not successors
391
  // of this block. To do this, instead of simply setting the `value` property
392
  // on the existing `OptionalVal`, we should create a new `Value` for the
393
  // optional, set the property on that, and associate the storage location that
394
  // is currently associated with the existing `OptionalVal` with the newly
395
  // created `Value` instead.
396
606
  OptionalVal.setProperty("value", ValuePtr);
397
606
  return &ValueLoc;
398
963
}
399
400
void initializeOptionalReference(const Expr *OptionalExpr,
401
                                 const MatchFinder::MatchResult &,
402
1.71k
                                 LatticeTransferState &State) {
403
1.71k
  if (auto *OptionalVal = State.Env.getValue(*OptionalExpr)) {
404
1.65k
    if (OptionalVal->getProperty("has_value") == nullptr) {
405
198
      setHasValue(*OptionalVal, State.Env.makeAtomicBoolValue());
406
198
    }
407
1.65k
  }
408
1.71k
}
409
410
/// Returns true if and only if `OptionalVal` is initialized and known to be
411
/// empty in `Env`.
412
102
bool isEmptyOptional(const Value &OptionalVal, const Environment &Env) {
413
102
  auto *HasValueVal =
414
102
      cast_or_null<BoolValue>(OptionalVal.getProperty("has_value"));
415
102
  return HasValueVal != nullptr &&
416
102
         Env.flowConditionImplies(Env.arena().makeNot(HasValueVal->formula()));
417
102
}
418
419
/// Returns true if and only if `OptionalVal` is initialized and known to be
420
/// non-empty in `Env`.
421
414
bool isNonEmptyOptional(const Value &OptionalVal, const Environment &Env) {
422
414
  auto *HasValueVal =
423
414
      cast_or_null<BoolValue>(OptionalVal.getProperty("has_value"));
424
414
  return HasValueVal != nullptr &&
425
414
         Env.flowConditionImplies(HasValueVal->formula());
426
414
}
427
428
1.73k
Value *getValueBehindPossiblePointer(const Expr &E, const Environment &Env) {
429
1.73k
  Value *Val = Env.getValue(E);
430
1.73k
  if (auto *PointerVal = dyn_cast_or_null<PointerValue>(Val))
431
90
    return Env.getValue(PointerVal->getPointeeLoc());
432
1.64k
  return Val;
433
1.73k
}
434
435
void transferUnwrapCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
436
921
                        LatticeTransferState &State) {
437
921
  if (auto *OptionalVal =
438
921
          getValueBehindPossiblePointer(*ObjectExpr, State.Env)) {
439
891
    if (State.Env.getStorageLocation(*UnwrapExpr) == nullptr)
440
891
      if (auto *Loc = maybeInitializeOptionalValueMember(
441
891
              UnwrapExpr->getType(), *OptionalVal, State.Env))
442
891
        State.Env.setStorageLocation(*UnwrapExpr, *Loc);
443
891
  }
444
921
}
445
446
void transferArrowOpCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
447
72
                         LatticeTransferState &State) {
448
72
  if (auto *OptionalVal =
449
72
          getValueBehindPossiblePointer(*ObjectExpr, State.Env)) {
450
72
    if (auto *Loc = maybeInitializeOptionalValueMember(
451
72
            UnwrapExpr->getType()->getPointeeType(), *OptionalVal, State.Env)) {
452
72
      State.Env.setValue(*UnwrapExpr, State.Env.create<PointerValue>(*Loc));
453
72
    }
454
72
  }
455
72
}
456
457
void transferMakeOptionalCall(const CallExpr *E,
458
                              const MatchFinder::MatchResult &,
459
24
                              LatticeTransferState &State) {
460
24
  State.Env.setValue(
461
24
      *E, createOptionalValue(State.Env.getResultObjectLocation(*E),
462
24
                              State.Env.getBoolLiteralValue(true), State.Env));
463
24
}
464
465
void transferOptionalHasValueCall(const CXXMemberCallExpr *CallExpr,
466
                                  const MatchFinder::MatchResult &,
467
234
                                  LatticeTransferState &State) {
468
234
  if (auto *HasValueVal = getHasValue(
469
234
          State.Env, getValueBehindPossiblePointer(
470
234
                         *CallExpr->getImplicitObjectArgument(), State.Env))) {
471
231
    State.Env.setValue(*CallExpr, *HasValueVal);
472
231
  }
473
234
}
474
475
/// `ModelPred` builds a logical formula relating the predicate in
476
/// `ValueOrPredExpr` to the optional's `has_value` property.
477
void transferValueOrImpl(
478
    const clang::Expr *ValueOrPredExpr, const MatchFinder::MatchResult &Result,
479
    LatticeTransferState &State,
480
    const Formula &(*ModelPred)(Environment &Env, const Formula &ExprVal,
481
30
                                const Formula &HasValueVal)) {
482
30
  auto &Env = State.Env;
483
484
30
  const auto *ObjectArgumentExpr =
485
30
      Result.Nodes.getNodeAs<clang::CXXMemberCallExpr>(ValueOrCallID)
486
30
          ->getImplicitObjectArgument();
487
488
30
  auto *HasValueVal = getHasValue(
489
30
      State.Env, getValueBehindPossiblePointer(*ObjectArgumentExpr, State.Env));
490
30
  if (HasValueVal == nullptr)
491
0
    return;
492
493
30
  Env.addToFlowCondition(ModelPred(Env, forceBoolValue(Env, *ValueOrPredExpr),
494
30
                                   HasValueVal->formula()));
495
30
}
496
497
void transferValueOrStringEmptyCall(const clang::Expr *ComparisonExpr,
498
                                    const MatchFinder::MatchResult &Result,
499
6
                                    LatticeTransferState &State) {
500
6
  return transferValueOrImpl(ComparisonExpr, Result, State,
501
6
                             [](Environment &Env, const Formula &ExprVal,
502
6
                                const Formula &HasValueVal) -> const Formula & {
503
6
                               auto &A = Env.arena();
504
                               // If the result is *not* empty, then we know the
505
                               // optional must have been holding a value. If
506
                               // `ExprVal` is true, though, we don't learn
507
                               // anything definite about `has_value`, so we
508
                               // don't add any corresponding implications to
509
                               // the flow condition.
510
6
                               return A.makeImplies(A.makeNot(ExprVal),
511
6
                                                    HasValueVal);
512
6
                             });
513
6
}
514
515
void transferValueOrNotEqX(const Expr *ComparisonExpr,
516
                           const MatchFinder::MatchResult &Result,
517
24
                           LatticeTransferState &State) {
518
24
  transferValueOrImpl(ComparisonExpr, Result, State,
519
24
                      [](Environment &Env, const Formula &ExprVal,
520
24
                         const Formula &HasValueVal) -> const Formula & {
521
24
                        auto &A = Env.arena();
522
                        // We know that if `(opt.value_or(X) != X)` then
523
                        // `opt.hasValue()`, even without knowing further
524
                        // details about the contents of `opt`.
525
24
                        return A.makeImplies(ExprVal, HasValueVal);
526
24
                      });
527
24
}
528
529
void transferCallReturningOptional(const CallExpr *E,
530
                                   const MatchFinder::MatchResult &Result,
531
450
                                   LatticeTransferState &State) {
532
450
  if (State.Env.getValue(*E) != nullptr)
533
189
    return;
534
535
261
  RecordStorageLocation *Loc = nullptr;
536
261
  if (E->isPRValue()) {
537
237
    Loc = &State.Env.getResultObjectLocation(*E);
538
237
  } else {
539
24
    Loc = cast_or_null<RecordStorageLocation>(State.Env.getStorageLocation(*E));
540
24
    if (Loc == nullptr) {
541
24
      Loc = &cast<RecordStorageLocation>(State.Env.createStorageLocation(*E));
542
24
      State.Env.setStorageLocation(*E, *Loc);
543
24
    }
544
24
  }
545
546
261
  RecordValue &Val =
547
261
      createOptionalValue(*Loc, State.Env.makeAtomicBoolValue(), State.Env);
548
261
  if (E->isPRValue())
549
237
    State.Env.setValue(*E, Val);
550
261
}
551
552
void constructOptionalValue(const Expr &E, Environment &Env,
553
615
                            BoolValue &HasValueVal) {
554
615
  RecordStorageLocation &Loc = Env.getResultObjectLocation(E);
555
615
  Env.setValue(E, createOptionalValue(Loc, HasValueVal, Env));
556
615
}
557
558
/// Returns a symbolic value for the "has_value" property of an `optional<T>`
559
/// value that is constructed/assigned from a value of type `U` or `optional<U>`
560
/// where `T` is constructible from `U`.
561
BoolValue &valueOrConversionHasValue(const FunctionDecl &F, const Expr &E,
562
                                     const MatchFinder::MatchResult &MatchRes,
563
336
                                     LatticeTransferState &State) {
564
336
  assert(F.getTemplateSpecializationArgs() != nullptr);
565
336
  assert(F.getTemplateSpecializationArgs()->size() > 0);
566
567
336
  const int TemplateParamOptionalWrappersCount =
568
336
      countOptionalWrappers(*MatchRes.Context, F.getTemplateSpecializationArgs()
569
336
                                                   ->get(0)
570
336
                                                   .getAsType()
571
336
                                                   .getNonReferenceType());
572
336
  const int ArgTypeOptionalWrappersCount = countOptionalWrappers(
573
336
      *MatchRes.Context, E.getType().getNonReferenceType());
574
575
  // Check if this is a constructor/assignment call for `optional<T>` with
576
  // argument of type `U` such that `T` is constructible from `U`.
577
336
  if (TemplateParamOptionalWrappersCount == ArgTypeOptionalWrappersCount)
578
288
    return State.Env.getBoolLiteralValue(true);
579
580
  // This is a constructor/assignment call for `optional<T>` with argument of
581
  // type `optional<U>` such that `T` is constructible from `U`.
582
48
  if (auto *HasValueVal = getHasValue(State.Env, State.Env.getValue(E)))
583
48
    return *HasValueVal;
584
0
  return State.Env.makeAtomicBoolValue();
585
48
}
586
587
void transferValueOrConversionConstructor(
588
    const CXXConstructExpr *E, const MatchFinder::MatchResult &MatchRes,
589
300
    LatticeTransferState &State) {
590
300
  assert(E->getNumArgs() > 0);
591
592
300
  constructOptionalValue(*E, State.Env,
593
300
                         valueOrConversionHasValue(*E->getConstructor(),
594
300
                                                   *E->getArg(0), MatchRes,
595
300
                                                   State));
596
300
}
597
598
void transferAssignment(const CXXOperatorCallExpr *E, BoolValue &HasValueVal,
599
69
                        LatticeTransferState &State) {
600
69
  assert(E->getNumArgs() > 0);
601
602
69
  if (auto *Loc = cast<RecordStorageLocation>(
603
69
          State.Env.getStorageLocation(*E->getArg(0)))) {
604
69
    createOptionalValue(*Loc, HasValueVal, State.Env);
605
606
    // Assign a storage location for the whole expression.
607
69
    State.Env.setStorageLocation(*E, *Loc);
608
69
  }
609
69
}
610
611
void transferValueOrConversionAssignment(
612
    const CXXOperatorCallExpr *E, const MatchFinder::MatchResult &MatchRes,
613
36
    LatticeTransferState &State) {
614
36
  assert(E->getNumArgs() > 1);
615
36
  transferAssignment(E,
616
36
                     valueOrConversionHasValue(*E->getDirectCallee(),
617
36
                                               *E->getArg(1), MatchRes, State),
618
36
                     State);
619
36
}
620
621
void transferNulloptAssignment(const CXXOperatorCallExpr *E,
622
                               const MatchFinder::MatchResult &,
623
33
                               LatticeTransferState &State) {
624
33
  transferAssignment(E, State.Env.getBoolLiteralValue(false), State);
625
33
}
626
627
void transferSwap(RecordStorageLocation *Loc1, RecordStorageLocation *Loc2,
628
60
                  Environment &Env) {
629
  // We account for cases where one or both of the optionals are not modeled,
630
  // either lacking associated storage locations, or lacking values associated
631
  // to such storage locations.
632
633
60
  if (Loc1 == nullptr) {
634
6
    if (Loc2 != nullptr)
635
6
      createOptionalValue(*Loc2, Env.makeAtomicBoolValue(), Env);
636
6
    return;
637
6
  }
638
54
  if (Loc2 == nullptr) {
639
6
    createOptionalValue(*Loc1, Env.makeAtomicBoolValue(), Env);
640
6
    return;
641
6
  }
642
643
  // Both expressions have locations, though they may not have corresponding
644
  // values. In that case, we create a fresh value at this point. Note that if
645
  // two branches both do this, they will not share the value, but it at least
646
  // allows for local reasoning about the value. To avoid the above, we would
647
  // need *lazy* value allocation.
648
  // FIXME: allocate values lazily, instead of just creating a fresh value.
649
48
  BoolValue *BoolVal1 = getHasValue(Env, Env.getValue(*Loc1));
650
48
  if (BoolVal1 == nullptr)
651
12
    BoolVal1 = &Env.makeAtomicBoolValue();
652
653
48
  BoolValue *BoolVal2 = getHasValue(Env, Env.getValue(*Loc2));
654
48
  if (BoolVal2 == nullptr)
655
12
    BoolVal2 = &Env.makeAtomicBoolValue();
656
657
48
  createOptionalValue(*Loc1, *BoolVal2, Env);
658
48
  createOptionalValue(*Loc2, *BoolVal1, Env);
659
48
}
660
661
void transferSwapCall(const CXXMemberCallExpr *E,
662
                      const MatchFinder::MatchResult &,
663
48
                      LatticeTransferState &State) {
664
48
  assert(E->getNumArgs() == 1);
665
48
  auto *OtherLoc = cast_or_null<RecordStorageLocation>(
666
48
      State.Env.getStorageLocation(*E->getArg(0)));
667
48
  transferSwap(getImplicitObjectLocation(*E, State.Env), OtherLoc, State.Env);
668
48
}
669
670
void transferStdSwapCall(const CallExpr *E, const MatchFinder::MatchResult &,
671
12
                         LatticeTransferState &State) {
672
12
  assert(E->getNumArgs() == 2);
673
12
  auto *Arg0Loc = cast_or_null<RecordStorageLocation>(
674
12
      State.Env.getStorageLocation(*E->getArg(0)));
675
12
  auto *Arg1Loc = cast_or_null<RecordStorageLocation>(
676
12
      State.Env.getStorageLocation(*E->getArg(1)));
677
12
  transferSwap(Arg0Loc, Arg1Loc, State.Env);
678
12
}
679
680
void transferStdForwardCall(const CallExpr *E, const MatchFinder::MatchResult &,
681
0
                            LatticeTransferState &State) {
682
0
  assert(E->getNumArgs() == 1);
683
684
0
  if (auto *Loc = State.Env.getStorageLocation(*E->getArg(0)))
685
0
    State.Env.setStorageLocation(*E, *Loc);
686
0
}
687
688
const Formula &evaluateEquality(Arena &A, const Formula &EqVal,
689
108
                                const Formula &LHS, const Formula &RHS) {
690
  // Logically, an optional<T> object is composed of two values - a `has_value`
691
  // bit and a value of type T. Equality of optional objects compares both
692
  // values. Therefore, merely comparing the `has_value` bits isn't sufficient:
693
  // when two optional objects are engaged, the equality of their respective
694
  // values of type T matters. Since we only track the `has_value` bits, we
695
  // can't make any conclusions about equality when we know that two optional
696
  // objects are engaged.
697
  //
698
  // We express this as two facts about the equality:
699
  // a) EqVal => (LHS & RHS) v (!RHS & !LHS)
700
  //    If they are equal, then either both are set or both are unset.
701
  // b) (!LHS & !RHS) => EqVal
702
  //    If neither is set, then they are equal.
703
  // We rewrite b) as !EqVal => (LHS v RHS), for a more compact formula.
704
108
  return A.makeAnd(
705
108
      A.makeImplies(EqVal, A.makeOr(A.makeAnd(LHS, RHS),
706
108
                                    A.makeAnd(A.makeNot(LHS), A.makeNot(RHS)))),
707
108
      A.makeImplies(A.makeNot(EqVal), A.makeOr(LHS, RHS)));
708
108
}
709
710
void transferOptionalAndOptionalCmp(const clang::CXXOperatorCallExpr *CmpExpr,
711
                                    const MatchFinder::MatchResult &,
712
84
                                    LatticeTransferState &State) {
713
84
  Environment &Env = State.Env;
714
84
  auto &A = Env.arena();
715
84
  auto *CmpValue = &forceBoolValue(Env, *CmpExpr);
716
84
  if (auto *LHasVal = getHasValue(Env, Env.getValue(*CmpExpr->getArg(0))))
717
84
    if (auto *RHasVal = getHasValue(Env, Env.getValue(*CmpExpr->getArg(1)))) {
718
84
      if (CmpExpr->getOperator() == clang::OO_ExclaimEqual)
719
42
        CmpValue = &A.makeNot(*CmpValue);
720
84
      Env.addToFlowCondition(evaluateEquality(A, *CmpValue, LHasVal->formula(),
721
84
                                              RHasVal->formula()));
722
84
    }
723
84
}
724
725
void transferOptionalAndValueCmp(const clang::CXXOperatorCallExpr *CmpExpr,
726
24
                                 const clang::Expr *E, Environment &Env) {
727
24
  auto &A = Env.arena();
728
24
  auto *CmpValue = &forceBoolValue(Env, *CmpExpr);
729
24
  if (auto *HasVal = getHasValue(Env, Env.getValue(*E))) {
730
24
    if (CmpExpr->getOperator() == clang::OO_ExclaimEqual)
731
12
      CmpValue = &A.makeNot(*CmpValue);
732
24
    Env.addToFlowCondition(
733
24
        evaluateEquality(A, *CmpValue, HasVal->formula(), A.makeLiteral(true)));
734
24
  }
735
24
}
736
737
std::optional<StatementMatcher>
738
351
ignorableOptional(const UncheckedOptionalAccessModelOptions &Options) {
739
351
  if (Options.IgnoreSmartPointerDereference) {
740
351
    auto SmartPtrUse = expr(ignoringParenImpCasts(cxxOperatorCallExpr(
741
351
        anyOf(hasOverloadedOperatorName("->"), hasOverloadedOperatorName("*")),
742
351
        unless(hasArgument(0, expr(hasOptionalType()))))));
743
351
    return expr(
744
351
        anyOf(SmartPtrUse, memberExpr(hasObjectExpression(SmartPtrUse))));
745
351
  }
746
0
  return std::nullopt;
747
351
}
748
749
StatementMatcher
750
702
valueCall(const std::optional<StatementMatcher> &IgnorableOptional) {
751
702
  return isOptionalMemberCallWithNameMatcher(hasName("value"),
752
702
                                             IgnorableOptional);
753
702
}
754
755
StatementMatcher
756
351
valueOperatorCall(const std::optional<StatementMatcher> &IgnorableOptional) {
757
351
  return expr(anyOf(isOptionalOperatorCallWithName("*", IgnorableOptional),
758
351
                    isOptionalOperatorCallWithName("->", IgnorableOptional)));
759
351
}
760
761
351
auto buildTransferMatchSwitch() {
762
  // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
763
  // lot of duplicated work (e.g. string comparisons), consider providing APIs
764
  // that avoid it through memoization.
765
351
  return CFGMatchSwitchBuilder<LatticeTransferState>()
766
      // Attach a symbolic "has_value" state to optional values that we see for
767
      // the first time.
768
351
      .CaseOfCFGStmt<Expr>(
769
351
          expr(anyOf(declRefExpr(), memberExpr()), hasOptionalType()),
770
351
          initializeOptionalReference)
771
772
      // make_optional
773
351
      .CaseOfCFGStmt<CallExpr>(isMakeOptionalCall(), transferMakeOptionalCall)
774
775
      // optional::optional (in place)
776
351
      .CaseOfCFGStmt<CXXConstructExpr>(
777
351
          isOptionalInPlaceConstructor(),
778
351
          [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
779
351
             LatticeTransferState &State) {
780
24
            constructOptionalValue(*E, State.Env,
781
24
                                   State.Env.getBoolLiteralValue(true));
782
24
          })
783
      // nullopt_t::nullopt_t
784
351
      .CaseOfCFGStmt<CXXConstructExpr>(
785
351
          isNulloptConstructor(),
786
351
          [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
787
351
             LatticeTransferState &State) {
788
174
            constructOptionalValue(*E, State.Env,
789
174
                                   State.Env.getBoolLiteralValue(false));
790
174
          })
791
      // optional::optional(nullopt_t)
792
351
      .CaseOfCFGStmt<CXXConstructExpr>(
793
351
          isOptionalNulloptConstructor(),
794
351
          [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
795
351
             LatticeTransferState &State) {
796
117
            constructOptionalValue(*E, State.Env,
797
117
                                   State.Env.getBoolLiteralValue(false));
798
117
          })
799
      // optional::optional (value/conversion)
800
351
      .CaseOfCFGStmt<CXXConstructExpr>(isOptionalValueOrConversionConstructor(),
801
351
                                       transferValueOrConversionConstructor)
802
803
      // optional::operator=
804
351
      .CaseOfCFGStmt<CXXOperatorCallExpr>(
805
351
          isOptionalValueOrConversionAssignment(),
806
351
          transferValueOrConversionAssignment)
807
351
      .CaseOfCFGStmt<CXXOperatorCallExpr>(isOptionalNulloptAssignment(),
808
351
                                          transferNulloptAssignment)
809
810
      // optional::value
811
351
      .CaseOfCFGStmt<CXXMemberCallExpr>(
812
351
          valueCall(std::nullopt),
813
351
          [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
814
867
             LatticeTransferState &State) {
815
867
            transferUnwrapCall(E, E->getImplicitObjectArgument(), State);
816
867
          })
817
818
      // optional::operator*
819
351
      .CaseOfCFGStmt<CallExpr>(isOptionalOperatorCallWithName("*"),
820
351
                               [](const CallExpr *E,
821
351
                                  const MatchFinder::MatchResult &,
822
351
                                  LatticeTransferState &State) {
823
54
                                 transferUnwrapCall(E, E->getArg(0), State);
824
54
                               })
825
826
      // optional::operator->
827
351
      .CaseOfCFGStmt<CallExpr>(isOptionalOperatorCallWithName("->"),
828
351
                               [](const CallExpr *E,
829
351
                                  const MatchFinder::MatchResult &,
830
351
                                  LatticeTransferState &State) {
831
72
                                 transferArrowOpCall(E, E->getArg(0), State);
832
72
                               })
833
834
      // optional::has_value, optional::hasValue
835
      // Of the supported optionals only folly::Optional uses hasValue, but this
836
      // will also pass for other types
837
351
      .CaseOfCFGStmt<CXXMemberCallExpr>(
838
351
          isOptionalMemberCallWithNameMatcher(
839
351
              hasAnyName("has_value", "hasValue")),
840
351
          transferOptionalHasValueCall)
841
842
      // optional::operator bool
843
351
      .CaseOfCFGStmt<CXXMemberCallExpr>(
844
351
          isOptionalMemberCallWithNameMatcher(hasName("operator bool")),
845
351
          transferOptionalHasValueCall)
846
847
      // optional::emplace
848
351
      .CaseOfCFGStmt<CXXMemberCallExpr>(
849
351
          isOptionalMemberCallWithNameMatcher(hasName("emplace")),
850
351
          [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
851
351
             LatticeTransferState &State) {
852
12
            if (RecordStorageLocation *Loc =
853
12
                    getImplicitObjectLocation(*E, State.Env)) {
854
12
              createOptionalValue(*Loc, State.Env.getBoolLiteralValue(true),
855
12
                                  State.Env);
856
12
            }
857
12
          })
858
859
      // optional::reset
860
351
      .CaseOfCFGStmt<CXXMemberCallExpr>(
861
351
          isOptionalMemberCallWithNameMatcher(hasName("reset")),
862
351
          [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
863
351
             LatticeTransferState &State) {
864
18
            if (RecordStorageLocation *Loc =
865
18
                    getImplicitObjectLocation(*E, State.Env)) {
866
18
              createOptionalValue(*Loc, State.Env.getBoolLiteralValue(false),
867
18
                                  State.Env);
868
18
            }
869
18
          })
870
871
      // optional::swap
872
351
      .CaseOfCFGStmt<CXXMemberCallExpr>(
873
351
          isOptionalMemberCallWithNameMatcher(hasName("swap")),
874
351
          transferSwapCall)
875
876
      // std::swap
877
351
      .CaseOfCFGStmt<CallExpr>(isStdSwapCall(), transferStdSwapCall)
878
879
      // std::forward
880
351
      .CaseOfCFGStmt<CallExpr>(isStdForwardCall(), transferStdForwardCall)
881
882
      // opt.value_or("").empty()
883
351
      .CaseOfCFGStmt<Expr>(isValueOrStringEmptyCall(),
884
351
                           transferValueOrStringEmptyCall)
885
886
      // opt.value_or(X) != X
887
351
      .CaseOfCFGStmt<Expr>(isValueOrNotEqX(), transferValueOrNotEqX)
888
889
      // Comparisons (==, !=):
890
351
      .CaseOfCFGStmt<CXXOperatorCallExpr>(
891
351
          isComparisonOperatorCall(hasAnyOptionalType(), hasAnyOptionalType()),
892
351
          transferOptionalAndOptionalCmp)
893
351
      .CaseOfCFGStmt<CXXOperatorCallExpr>(
894
351
          isComparisonOperatorCall(hasOptionalType(),
895
351
                                   unless(hasAnyOptionalType())),
896
351
          [](const clang::CXXOperatorCallExpr *Cmp,
897
351
             const MatchFinder::MatchResult &, LatticeTransferState &State) {
898
12
            transferOptionalAndValueCmp(Cmp, Cmp->getArg(0), State.Env);
899
12
          })
900
351
      .CaseOfCFGStmt<CXXOperatorCallExpr>(
901
351
          isComparisonOperatorCall(unless(hasAnyOptionalType()),
902
351
                                   hasOptionalType()),
903
351
          [](const clang::CXXOperatorCallExpr *Cmp,
904
351
             const MatchFinder::MatchResult &, LatticeTransferState &State) {
905
12
            transferOptionalAndValueCmp(Cmp, Cmp->getArg(1), State.Env);
906
12
          })
907
908
      // returns optional
909
351
      .CaseOfCFGStmt<CallExpr>(isCallReturningOptional(),
910
351
                               transferCallReturningOptional)
911
912
351
      .Build();
913
351
}
914
915
llvm::SmallVector<SourceLocation> diagnoseUnwrapCall(const Expr *ObjectExpr,
916
477
                                                     const Environment &Env) {
917
477
  if (auto *OptionalVal = getValueBehindPossiblePointer(*ObjectExpr, Env)) {
918
471
    auto *Prop = OptionalVal->getProperty("has_value");
919
471
    if (auto *HasValueVal = cast_or_null<BoolValue>(Prop)) {
920
471
      if (Env.flowConditionImplies(HasValueVal->formula()))
921
261
        return {};
922
471
    }
923
471
  }
924
925
  // Record that this unwrap is *not* provably safe.
926
  // FIXME: include either the name of the optional (if applicable) or a source
927
  // range of the access for easier interpretation of the result.
928
216
  return {ObjectExpr->getBeginLoc()};
929
477
}
930
931
auto buildDiagnoseMatchSwitch(
932
351
    const UncheckedOptionalAccessModelOptions &Options) {
933
  // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
934
  // lot of duplicated work (e.g. string comparisons), consider providing APIs
935
  // that avoid it through memoization.
936
351
  auto IgnorableOptional = ignorableOptional(Options);
937
351
  return CFGMatchSwitchBuilder<const Environment,
938
351
                               llvm::SmallVector<SourceLocation>>()
939
      // optional::value
940
351
      .CaseOfCFGStmt<CXXMemberCallExpr>(
941
351
          valueCall(IgnorableOptional),
942
351
          [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
943
420
             const Environment &Env) {
944
420
            return diagnoseUnwrapCall(E->getImplicitObjectArgument(), Env);
945
420
          })
946
947
      // optional::operator*, optional::operator->
948
351
      .CaseOfCFGStmt<CallExpr>(valueOperatorCall(IgnorableOptional),
949
351
                               [](const CallExpr *E,
950
351
                                  const MatchFinder::MatchResult &,
951
351
                                  const Environment &Env) {
952
57
                                 return diagnoseUnwrapCall(E->getArg(0), Env);
953
57
                               })
954
351
      .Build();
955
351
}
956
957
} // namespace
958
959
ast_matchers::DeclarationMatcher
960
0
UncheckedOptionalAccessModel::optionalClassDecl() {
961
0
  return optionalClass();
962
0
}
963
964
UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(ASTContext &Ctx)
965
351
    : DataflowAnalysis<UncheckedOptionalAccessModel, NoopLattice>(Ctx),
966
351
      TransferMatchSwitch(buildTransferMatchSwitch()) {}
967
968
void UncheckedOptionalAccessModel::transfer(const CFGElement &Elt,
969
12.5k
                                            NoopLattice &L, Environment &Env) {
970
12.5k
  LatticeTransferState State(L, Env);
971
12.5k
  TransferMatchSwitch(Elt, getASTContext(), State);
972
12.5k
}
973
974
ComparisonResult UncheckedOptionalAccessModel::compare(
975
    QualType Type, const Value &Val1, const Environment &Env1,
976
81
    const Value &Val2, const Environment &Env2) {
977
81
  if (!isOptionalType(Type))
978
48
    return ComparisonResult::Unknown;
979
33
  bool MustNonEmpty1 = isNonEmptyOptional(Val1, Env1);
980
33
  bool MustNonEmpty2 = isNonEmptyOptional(Val2, Env2);
981
33
  if (MustNonEmpty1 && 
MustNonEmpty212
)
982
3
    return ComparisonResult::Same;
983
  // If exactly one is true, then they're different, no reason to check whether
984
  // they're definitely empty.
985
30
  if (MustNonEmpty1 || 
MustNonEmpty221
)
986
9
    return ComparisonResult::Different;
987
  // Check if they're both definitely empty.
988
21
  return (isEmptyOptional(Val1, Env1) && 
isEmptyOptional(Val2, Env2)6
)
989
21
             ? 
ComparisonResult::Same0
990
21
             : ComparisonResult::Different;
991
30
}
992
993
bool UncheckedOptionalAccessModel::merge(QualType Type, const Value &Val1,
994
                                         const Environment &Env1,
995
                                         const Value &Val2,
996
                                         const Environment &Env2,
997
                                         Value &MergedVal,
998
312
                                         Environment &MergedEnv) {
999
312
  if (!isOptionalType(Type))
1000
138
    return true;
1001
  // FIXME: uses same approach as join for `BoolValues`. Requires non-const
1002
  // values, though, so will require updating the interface.
1003
174
  auto &HasValueVal = MergedEnv.makeAtomicBoolValue();
1004
174
  bool MustNonEmpty1 = isNonEmptyOptional(Val1, Env1);
1005
174
  bool MustNonEmpty2 = isNonEmptyOptional(Val2, Env2);
1006
174
  if (MustNonEmpty1 && 
MustNonEmpty278
)
1007
33
    MergedEnv.addToFlowCondition(HasValueVal.formula());
1008
141
  else if (
1009
      // Only make the costly calls to `isEmptyOptional` if we got "unknown"
1010
      // (false) for both calls to `isNonEmptyOptional`.
1011
141
      !MustNonEmpty1 && 
!MustNonEmpty296
&&
isEmptyOptional(Val1, Env1)57
&&
1012
141
      
isEmptyOptional(Val2, Env2)18
)
1013
18
    MergedEnv.addToFlowCondition(
1014
18
        MergedEnv.arena().makeNot(HasValueVal.formula()));
1015
174
  setHasValue(MergedVal, HasValueVal);
1016
174
  return true;
1017
312
}
1018
1019
Value *UncheckedOptionalAccessModel::widen(QualType Type, Value &Prev,
1020
                                           const Environment &PrevEnv,
1021
                                           Value &Current,
1022
33
                                           Environment &CurrentEnv) {
1023
33
  switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) {
1024
3
  case ComparisonResult::Same:
1025
3
    return &Prev;
1026
30
  case ComparisonResult::Different:
1027
30
    if (auto *PrevHasVal =
1028
30
            cast_or_null<BoolValue>(Prev.getProperty("has_value"))) {
1029
30
      if (isa<TopBoolValue>(PrevHasVal))
1030
15
        return &Prev;
1031
30
    }
1032
15
    if (auto *CurrentHasVal =
1033
15
            cast_or_null<BoolValue>(Current.getProperty("has_value"))) {
1034
15
      if (isa<TopBoolValue>(CurrentHasVal))
1035
0
        return &Current;
1036
15
    }
1037
15
    return &createOptionalValue(cast<RecordValue>(Current).getLoc(),
1038
15
                                CurrentEnv.makeTopBoolValue(), CurrentEnv);
1039
0
  case ComparisonResult::Unknown:
1040
0
    return nullptr;
1041
33
  }
1042
0
  llvm_unreachable("all cases covered in switch");
1043
0
}
1044
1045
UncheckedOptionalAccessDiagnoser::UncheckedOptionalAccessDiagnoser(
1046
    UncheckedOptionalAccessModelOptions Options)
1047
351
    : DiagnoseMatchSwitch(buildDiagnoseMatchSwitch(Options)) {}
1048
1049
} // namespace dataflow
1050
} // namespace clang