xref: /freebsd/contrib/llvm-project/clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp (revision 770cf0a5f02dc8983a89c6568d741fbc25baa999) 
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/AST/Type.h"
21 #include "clang/ASTMatchers/ASTMatchers.h"
22 #include "clang/ASTMatchers/ASTMatchersMacros.h"
23 #include "clang/Analysis/CFG.h"
24 #include "clang/Analysis/FlowSensitive/CFGMatchSwitch.h"
25 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
26 #include "clang/Analysis/FlowSensitive/Formula.h"
27 #include "clang/Analysis/FlowSensitive/RecordOps.h"
28 #include "clang/Analysis/FlowSensitive/SmartPointerAccessorCaching.h"
29 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
30 #include "clang/Analysis/FlowSensitive/Value.h"
31 #include "clang/Basic/OperatorKinds.h"
32 #include "clang/Basic/SourceLocation.h"
33 #include "llvm/ADT/StringRef.h"
34 #include "llvm/Support/ErrorHandling.h"
35 #include <cassert>
36 #include <optional>
37 
38 namespace clang {
39 namespace dataflow {
40 
41 // Note: the Names appear in reverse order. E.g., to check
42 // if NS is foo::bar::, call isFullyQualifiedNamespaceEqualTo(NS, "bar", "foo")
43 template <class... NameTypes>
44 static bool isFullyQualifiedNamespaceEqualTo(const NamespaceDecl &NS,
45                                              llvm::StringRef Name,
46                                              NameTypes... Names) {
47   if (!(NS.getDeclName().isIdentifier() && NS.getName() == Name &&
48         NS.getParent() != nullptr))
49     return false;
50 
51   if constexpr (sizeof...(NameTypes) > 0) {
52     if (NS.getParent()->isTranslationUnit())
53       return false;
54     if (const auto *NextNS = dyn_cast_or_null<NamespaceDecl>(NS.getParent()))
55       return isFullyQualifiedNamespaceEqualTo(*NextNS, Names...);
56     return false;
57   } else {
58     return NS.getParent()->isTranslationUnit();
59   }
60 }
61 
62 static bool hasOptionalClassName(const CXXRecordDecl &RD) {
63   if (!RD.getDeclName().isIdentifier())
64     return false;
65 
66   if (RD.getName() == "optional") {
67     if (const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext()))
68       return N->isStdNamespace() ||
69              isFullyQualifiedNamespaceEqualTo(*N, "absl") ||
70              isFullyQualifiedNamespaceEqualTo(*N, "bsl");
71     return false;
72   }
73 
74   if (RD.getName() == "Optional") {
75     // Check whether namespace is "::base" or "::folly".
76     const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext());
77     return N != nullptr && (isFullyQualifiedNamespaceEqualTo(*N, "base") ||
78                             isFullyQualifiedNamespaceEqualTo(*N, "folly"));
79   }
80 
81   if (RD.getName() == "NullableValue") {
82     const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext());
83     return N != nullptr &&
84            isFullyQualifiedNamespaceEqualTo(*N, "bdlb", "BloombergLP");
85   }
86 
87   return false;
88 }
89 
90 static const CXXRecordDecl *getOptionalBaseClass(const CXXRecordDecl *RD) {
91   if (RD == nullptr)
92     return nullptr;
93   if (hasOptionalClassName(*RD))
94     return RD;
95 
96   if (!RD->hasDefinition())
97     return nullptr;
98 
99   for (const CXXBaseSpecifier &Base : RD->bases())
100     if (const CXXRecordDecl *BaseClass =
101             getOptionalBaseClass(Base.getType()->getAsCXXRecordDecl()))
102       return BaseClass;
103 
104   return nullptr;
105 }
106 
107 static bool isSupportedOptionalType(QualType Ty) {
108   const CXXRecordDecl *Optional =
109       getOptionalBaseClass(Ty->getAsCXXRecordDecl());
110   return Optional != nullptr;
111 }
112 
113 namespace {
114 
115 using namespace ::clang::ast_matchers;
116 
117 using LatticeTransferState = TransferState<UncheckedOptionalAccessLattice>;
118 
119 AST_MATCHER(CXXRecordDecl, optionalClass) { return hasOptionalClassName(Node); }
120 
121 AST_MATCHER(CXXRecordDecl, optionalOrDerivedClass) {
122   return getOptionalBaseClass(&Node) != nullptr;
123 }
124 
125 auto desugarsToOptionalType() {
126   return hasUnqualifiedDesugaredType(
127       recordType(hasDeclaration(cxxRecordDecl(optionalClass()))));
128 }
129 
130 auto desugarsToOptionalOrDerivedType() {
131   return hasUnqualifiedDesugaredType(
132       recordType(hasDeclaration(cxxRecordDecl(optionalOrDerivedClass()))));
133 }
134 
135 auto hasOptionalType() { return hasType(desugarsToOptionalType()); }
136 
137 /// Matches any of the spellings of the optional types and sugar, aliases,
138 /// derived classes, etc.
139 auto hasOptionalOrDerivedType() {
140   return hasType(desugarsToOptionalOrDerivedType());
141 }
142 
143 QualType getPublicType(const Expr *E) {
144   auto *Cast = dyn_cast<ImplicitCastExpr>(E->IgnoreParens());
145   if (Cast == nullptr || Cast->getCastKind() != CK_UncheckedDerivedToBase) {
146     QualType Ty = E->getType();
147     if (Ty->isPointerType())
148       return Ty->getPointeeType();
149     return Ty;
150   }
151 
152   // Is the derived type that we're casting from the type of `*this`? In this
153   // special case, we can upcast to the base class even if the base is
154   // non-public.
155   bool CastingFromThis = isa<CXXThisExpr>(Cast->getSubExpr());
156 
157   // Find the least-derived type in the path (i.e. the last entry in the list)
158   // that we can access.
159   const CXXBaseSpecifier *PublicBase = nullptr;
160   for (const CXXBaseSpecifier *Base : Cast->path()) {
161     if (Base->getAccessSpecifier() != AS_public && !CastingFromThis)
162       break;
163     PublicBase = Base;
164     CastingFromThis = false;
165   }
166 
167   if (PublicBase != nullptr)
168     return PublicBase->getType();
169 
170   // We didn't find any public type that we could cast to. There may be more
171   // casts in `getSubExpr()`, so recurse. (If there aren't any more casts, this
172   // will return the type of `getSubExpr()`.)
173   return getPublicType(Cast->getSubExpr());
174 }
175 
176 // Returns the least-derived type for the receiver of `MCE` that
177 // `MCE.getImplicitObjectArgument()->IgnoreParentImpCasts()` can be downcast to.
178 // Effectively, we upcast until we reach a non-public base class, unless that
179 // base is a base of `*this`.
180 //
181 // This is needed to correctly match methods called on types derived from
182 // `std::optional`.
183 //
184 // Say we have a `struct Derived : public std::optional<int> {} d;` For a call
185 // `d.has_value()`, the `getImplicitObjectArgument()` looks like this:
186 //
187 //   ImplicitCastExpr 'const std::__optional_storage_base<int>' lvalue
188 //   |            <UncheckedDerivedToBase (optional -> __optional_storage_base)>
189 //   `-DeclRefExpr 'Derived' lvalue Var 'd' 'Derived'
190 //
191 // The type of the implicit object argument is `__optional_storage_base`
192 // (since this is the internal type that `has_value()` is declared on). If we
193 // call `IgnoreParenImpCasts()` on the implicit object argument, we get the
194 // `DeclRefExpr`, which has type `Derived`. Neither of these types is
195 // `optional`, and hence neither is sufficient for querying whether we are
196 // calling a method on `optional`.
197 //
198 // Instead, starting with the most derived type, we need to follow the chain of
199 // casts
200 QualType getPublicReceiverType(const CXXMemberCallExpr &MCE) {
201   return getPublicType(MCE.getImplicitObjectArgument());
202 }
203 
204 AST_MATCHER_P(CXXMemberCallExpr, publicReceiverType,
205               ast_matchers::internal::Matcher<QualType>, InnerMatcher) {
206   return InnerMatcher.matches(getPublicReceiverType(Node), Finder, Builder);
207 }
208 
209 auto isOptionalMemberCallWithNameMatcher(
210     ast_matchers::internal::Matcher<NamedDecl> matcher,
211     const std::optional<StatementMatcher> &Ignorable = std::nullopt) {
212   return cxxMemberCallExpr(Ignorable ? on(expr(unless(*Ignorable)))
213                                      : anything(),
214                            publicReceiverType(desugarsToOptionalType()),
215                            callee(cxxMethodDecl(matcher)));
216 }
217 
218 auto isOptionalOperatorCallWithName(
219     llvm::StringRef operator_name,
220     const std::optional<StatementMatcher> &Ignorable = std::nullopt) {
221   return cxxOperatorCallExpr(
222       hasOverloadedOperatorName(operator_name),
223       callee(cxxMethodDecl(ofClass(optionalClass()))),
224       Ignorable ? callExpr(unless(hasArgument(0, *Ignorable))) : callExpr());
225 }
226 
227 auto isMakeOptionalCall() {
228   return callExpr(
229       callee(functionDecl(hasAnyName(
230           "std::make_optional", "base::make_optional", "absl::make_optional",
231           "folly::make_optional", "bsl::make_optional"))),
232       hasOptionalType());
233 }
234 
235 auto nulloptTypeDecl() {
236   return namedDecl(hasAnyName("std::nullopt_t", "absl::nullopt_t",
237                               "base::nullopt_t", "folly::None",
238                               "bsl::nullopt_t"));
239 }
240 
241 auto hasNulloptType() { return hasType(nulloptTypeDecl()); }
242 
243 auto inPlaceClass() {
244   return recordDecl(hasAnyName("std::in_place_t", "absl::in_place_t",
245                                "base::in_place_t", "folly::in_place_t",
246                                "bsl::in_place_t"));
247 }
248 
249 auto isOptionalNulloptConstructor() {
250   return cxxConstructExpr(
251       hasDeclaration(cxxConstructorDecl(parameterCountIs(1),
252                                         hasParameter(0, hasNulloptType()))),
253       hasOptionalOrDerivedType());
254 }
255 
256 auto isOptionalInPlaceConstructor() {
257   return cxxConstructExpr(hasArgument(0, hasType(inPlaceClass())),
258                           hasOptionalOrDerivedType());
259 }
260 
261 auto isOptionalValueOrConversionConstructor() {
262   return cxxConstructExpr(
263       unless(hasDeclaration(
264           cxxConstructorDecl(anyOf(isCopyConstructor(), isMoveConstructor())))),
265       argumentCountIs(1), hasArgument(0, unless(hasNulloptType())),
266       hasOptionalOrDerivedType());
267 }
268 
269 auto isOptionalValueOrConversionAssignment() {
270   return cxxOperatorCallExpr(
271       hasOverloadedOperatorName("="),
272       callee(cxxMethodDecl(ofClass(optionalOrDerivedClass()))),
273       unless(hasDeclaration(cxxMethodDecl(
274           anyOf(isCopyAssignmentOperator(), isMoveAssignmentOperator())))),
275       argumentCountIs(2), hasArgument(1, unless(hasNulloptType())));
276 }
277 
278 auto isOptionalNulloptAssignment() {
279   return cxxOperatorCallExpr(
280       hasOverloadedOperatorName("="),
281       callee(cxxMethodDecl(ofClass(optionalOrDerivedClass()))),
282       argumentCountIs(2), hasArgument(1, hasNulloptType()));
283 }
284 
285 auto isStdSwapCall() {
286   return callExpr(callee(functionDecl(hasName("std::swap"))),
287                   argumentCountIs(2),
288                   hasArgument(0, hasOptionalOrDerivedType()),
289                   hasArgument(1, hasOptionalOrDerivedType()));
290 }
291 
292 auto isStdForwardCall() {
293   return callExpr(callee(functionDecl(hasName("std::forward"))),
294                   argumentCountIs(1),
295                   hasArgument(0, hasOptionalOrDerivedType()));
296 }
297 
298 constexpr llvm::StringLiteral ValueOrCallID = "ValueOrCall";
299 
300 auto isValueOrStringEmptyCall() {
301   // `opt.value_or("").empty()`
302   return cxxMemberCallExpr(
303       callee(cxxMethodDecl(hasName("empty"))),
304       onImplicitObjectArgument(ignoringImplicit(
305           cxxMemberCallExpr(on(expr(unless(cxxThisExpr()))),
306                             callee(cxxMethodDecl(hasName("value_or"),
307                                                  ofClass(optionalClass()))),
308                             hasArgument(0, stringLiteral(hasSize(0))))
309               .bind(ValueOrCallID))));
310 }
311 
312 auto isValueOrNotEqX() {
313   auto ComparesToSame = [](ast_matchers::internal::Matcher<Stmt> Arg) {
314     return hasOperands(
315         ignoringImplicit(
316             cxxMemberCallExpr(on(expr(unless(cxxThisExpr()))),
317                               callee(cxxMethodDecl(hasName("value_or"),
318                                                    ofClass(optionalClass()))),
319                               hasArgument(0, Arg))
320                 .bind(ValueOrCallID)),
321         ignoringImplicit(Arg));
322   };
323 
324   // `opt.value_or(X) != X`, for X is `nullptr`, `""`, or `0`. Ideally, we'd
325   // support this pattern for any expression, but the AST does not have a
326   // generic expression comparison facility, so we specialize to common cases
327   // seen in practice.  FIXME: define a matcher that compares values across
328   // nodes, which would let us generalize this to any `X`.
329   return binaryOperation(hasOperatorName("!="),
330                          anyOf(ComparesToSame(cxxNullPtrLiteralExpr()),
331                                ComparesToSame(stringLiteral(hasSize(0))),
332                                ComparesToSame(integerLiteral(equals(0)))));
333 }
334 
335 auto isZeroParamConstMemberCall() {
336   return cxxMemberCallExpr(
337       callee(cxxMethodDecl(parameterCountIs(0), isConst())));
338 }
339 
340 auto isZeroParamConstMemberOperatorCall() {
341   return cxxOperatorCallExpr(
342       callee(cxxMethodDecl(parameterCountIs(0), isConst())));
343 }
344 
345 auto isNonConstMemberCall() {
346   return cxxMemberCallExpr(callee(cxxMethodDecl(unless(isConst()))));
347 }
348 
349 auto isNonConstMemberOperatorCall() {
350   return cxxOperatorCallExpr(callee(cxxMethodDecl(unless(isConst()))));
351 }
352 
353 auto isCallReturningOptional() {
354   return callExpr(hasType(qualType(
355       anyOf(desugarsToOptionalOrDerivedType(),
356             referenceType(pointee(desugarsToOptionalOrDerivedType()))))));
357 }
358 
359 template <typename L, typename R>
360 auto isComparisonOperatorCall(L lhs_arg_matcher, R rhs_arg_matcher) {
361   return cxxOperatorCallExpr(
362       anyOf(hasOverloadedOperatorName("=="), hasOverloadedOperatorName("!=")),
363       argumentCountIs(2), hasArgument(0, lhs_arg_matcher),
364       hasArgument(1, rhs_arg_matcher));
365 }
366 
367 /// Ensures that `Expr` is mapped to a `BoolValue` and returns its formula.
368 const Formula &forceBoolValue(Environment &Env, const Expr &Expr) {
369   auto *Value = Env.get<BoolValue>(Expr);
370   if (Value != nullptr)
371     return Value->formula();
372 
373   Value = &Env.makeAtomicBoolValue();
374   Env.setValue(Expr, *Value);
375   return Value->formula();
376 }
377 
378 StorageLocation &locForHasValue(const RecordStorageLocation &OptionalLoc) {
379   return OptionalLoc.getSyntheticField("has_value");
380 }
381 
382 StorageLocation &locForValue(const RecordStorageLocation &OptionalLoc) {
383   return OptionalLoc.getSyntheticField("value");
384 }
385 
386 /// Sets `HasValueVal` as the symbolic value that represents the "has_value"
387 /// property of the optional at `OptionalLoc`.
388 void setHasValue(RecordStorageLocation &OptionalLoc, BoolValue &HasValueVal,
389                  Environment &Env) {
390   Env.setValue(locForHasValue(OptionalLoc), HasValueVal);
391 }
392 
393 /// Returns the symbolic value that represents the "has_value" property of the
394 /// optional at `OptionalLoc`. Returns null if `OptionalLoc` is null.
395 BoolValue *getHasValue(Environment &Env, RecordStorageLocation *OptionalLoc) {
396   if (OptionalLoc == nullptr)
397     return nullptr;
398   StorageLocation &HasValueLoc = locForHasValue(*OptionalLoc);
399   auto *HasValueVal = Env.get<BoolValue>(HasValueLoc);
400   if (HasValueVal == nullptr) {
401     HasValueVal = &Env.makeAtomicBoolValue();
402     Env.setValue(HasValueLoc, *HasValueVal);
403   }
404   return HasValueVal;
405 }
406 
407 QualType valueTypeFromOptionalDecl(const CXXRecordDecl &RD) {
408   auto &CTSD = cast<ClassTemplateSpecializationDecl>(RD);
409   return CTSD.getTemplateArgs()[0].getAsType();
410 }
411 
412 /// Returns the number of optional wrappers in `Type`.
413 ///
414 /// For example, if `Type` is `optional<optional<int>>`, the result of this
415 /// function will be 2.
416 int countOptionalWrappers(const ASTContext &ASTCtx, QualType Type) {
417   const CXXRecordDecl *Optional =
418       getOptionalBaseClass(Type->getAsCXXRecordDecl());
419   if (Optional == nullptr)
420     return 0;
421   return 1 + countOptionalWrappers(
422                  ASTCtx,
423                  valueTypeFromOptionalDecl(*Optional).getDesugaredType(ASTCtx));
424 }
425 
426 StorageLocation *getLocBehindPossiblePointer(const Expr &E,
427                                              const Environment &Env) {
428   if (E.isPRValue()) {
429     if (auto *PointerVal = dyn_cast_or_null<PointerValue>(Env.getValue(E)))
430       return &PointerVal->getPointeeLoc();
431     return nullptr;
432   }
433   return Env.getStorageLocation(E);
434 }
435 
436 void transferUnwrapCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
437                         LatticeTransferState &State) {
438   if (auto *OptionalLoc = cast_or_null<RecordStorageLocation>(
439           getLocBehindPossiblePointer(*ObjectExpr, State.Env))) {
440     if (State.Env.getStorageLocation(*UnwrapExpr) == nullptr)
441       State.Env.setStorageLocation(*UnwrapExpr, locForValue(*OptionalLoc));
442   }
443 }
444 
445 void transferArrowOpCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
446                          LatticeTransferState &State) {
447   if (auto *OptionalLoc = cast_or_null<RecordStorageLocation>(
448           getLocBehindPossiblePointer(*ObjectExpr, State.Env)))
449     State.Env.setValue(
450         *UnwrapExpr, State.Env.create<PointerValue>(locForValue(*OptionalLoc)));
451 }
452 
453 void transferMakeOptionalCall(const CallExpr *E,
454                               const MatchFinder::MatchResult &,
455                               LatticeTransferState &State) {
456   setHasValue(State.Env.getResultObjectLocation(*E),
457               State.Env.getBoolLiteralValue(true), State.Env);
458 }
459 
460 void transferOptionalHasValueCall(const CXXMemberCallExpr *CallExpr,
461                                   const MatchFinder::MatchResult &,
462                                   LatticeTransferState &State) {
463   if (auto *HasValueVal = getHasValue(
464           State.Env, getImplicitObjectLocation(*CallExpr, State.Env))) {
465     State.Env.setValue(*CallExpr, *HasValueVal);
466   }
467 }
468 
469 void transferOptionalIsNullCall(const CXXMemberCallExpr *CallExpr,
470                                 const MatchFinder::MatchResult &,
471                                 LatticeTransferState &State) {
472   if (auto *HasValueVal = getHasValue(
473           State.Env, getImplicitObjectLocation(*CallExpr, State.Env))) {
474     State.Env.setValue(*CallExpr, State.Env.makeNot(*HasValueVal));
475   }
476 }
477 
478 /// `ModelPred` builds a logical formula relating the predicate in
479 /// `ValueOrPredExpr` to the optional's `has_value` property.
480 void transferValueOrImpl(
481     const clang::Expr *ValueOrPredExpr, const MatchFinder::MatchResult &Result,
482     LatticeTransferState &State,
483     const Formula &(*ModelPred)(Environment &Env, const Formula &ExprVal,
484                                 const Formula &HasValueVal)) {
485   auto &Env = State.Env;
486 
487   const auto *MCE =
488       Result.Nodes.getNodeAs<clang::CXXMemberCallExpr>(ValueOrCallID);
489 
490   auto *HasValueVal =
491       getHasValue(State.Env, getImplicitObjectLocation(*MCE, State.Env));
492   if (HasValueVal == nullptr)
493     return;
494 
495   Env.assume(ModelPred(Env, forceBoolValue(Env, *ValueOrPredExpr),
496                        HasValueVal->formula()));
497 }
498 
499 void transferValueOrStringEmptyCall(const clang::Expr *ComparisonExpr,
500                                     const MatchFinder::MatchResult &Result,
501                                     LatticeTransferState &State) {
502   return transferValueOrImpl(ComparisonExpr, Result, State,
503                              [](Environment &Env, const Formula &ExprVal,
504                                 const Formula &HasValueVal) -> const Formula & {
505                                auto &A = Env.arena();
506                                // If the result is *not* empty, then we know the
507                                // optional must have been holding a value. If
508                                // `ExprVal` is true, though, we don't learn
509                                // anything definite about `has_value`, so we
510                                // don't add any corresponding implications to
511                                // the flow condition.
512                                return A.makeImplies(A.makeNot(ExprVal),
513                                                     HasValueVal);
514                              });
515 }
516 
517 void transferValueOrNotEqX(const Expr *ComparisonExpr,
518                            const MatchFinder::MatchResult &Result,
519                            LatticeTransferState &State) {
520   transferValueOrImpl(ComparisonExpr, Result, State,
521                       [](Environment &Env, const Formula &ExprVal,
522                          const Formula &HasValueVal) -> const Formula & {
523                         auto &A = Env.arena();
524                         // We know that if `(opt.value_or(X) != X)` then
525                         // `opt.hasValue()`, even without knowing further
526                         // details about the contents of `opt`.
527                         return A.makeImplies(ExprVal, HasValueVal);
528                       });
529 }
530 
531 void transferCallReturningOptional(const CallExpr *E,
532                                    const MatchFinder::MatchResult &Result,
533                                    LatticeTransferState &State) {
534   RecordStorageLocation *Loc = nullptr;
535   if (E->isPRValue()) {
536     Loc = &State.Env.getResultObjectLocation(*E);
537   } else {
538     Loc = State.Env.get<RecordStorageLocation>(*E);
539     if (Loc == nullptr) {
540       Loc = &cast<RecordStorageLocation>(State.Env.createStorageLocation(*E));
541       State.Env.setStorageLocation(*E, *Loc);
542     }
543   }
544 
545   if (State.Env.getValue(locForHasValue(*Loc)) != nullptr)
546     return;
547 
548   setHasValue(*Loc, State.Env.makeAtomicBoolValue(), State.Env);
549 }
550 
551 // Returns true if the const accessor is handled by caching.
552 // Returns false if we could not cache. We should perform default handling
553 // in that case.
554 bool handleConstMemberCall(const CallExpr *CE,
555                            dataflow::RecordStorageLocation *RecordLoc,
556                            const MatchFinder::MatchResult &Result,
557                            LatticeTransferState &State) {
558   if (RecordLoc == nullptr)
559     return false;
560 
561   // Cache if the const method returns a reference.
562   if (CE->isGLValue()) {
563     const FunctionDecl *DirectCallee = CE->getDirectCallee();
564     if (DirectCallee == nullptr)
565       return false;
566 
567     // Initialize the optional's "has_value" property to true if the type is
568     // optional, otherwise no-op. If we want to support const ref to pointers or
569     // bools we should initialize their values here too.
570     auto Init = [&](StorageLocation &Loc) {
571       if (isSupportedOptionalType(CE->getType()))
572         setHasValue(cast<RecordStorageLocation>(Loc),
573                     State.Env.makeAtomicBoolValue(), State.Env);
574     };
575     StorageLocation &Loc =
576         State.Lattice.getOrCreateConstMethodReturnStorageLocation(
577             *RecordLoc, DirectCallee, State.Env, Init);
578 
579     State.Env.setStorageLocation(*CE, Loc);
580     return true;
581   }
582   // PRValue cases:
583   if (CE->getType()->isBooleanType() || CE->getType()->isPointerType()) {
584     // If the const method returns a boolean or pointer type.
585     Value *Val = State.Lattice.getOrCreateConstMethodReturnValue(*RecordLoc, CE,
586                                                                  State.Env);
587     if (Val == nullptr)
588       return false;
589     State.Env.setValue(*CE, *Val);
590     return true;
591   }
592   if (isSupportedOptionalType(CE->getType())) {
593     // If the const method returns an optional by value.
594     const FunctionDecl *DirectCallee = CE->getDirectCallee();
595     if (DirectCallee == nullptr)
596       return false;
597     StorageLocation &Loc =
598         State.Lattice.getOrCreateConstMethodReturnStorageLocation(
599             *RecordLoc, DirectCallee, State.Env, [&](StorageLocation &Loc) {
600               setHasValue(cast<RecordStorageLocation>(Loc),
601                           State.Env.makeAtomicBoolValue(), State.Env);
602             });
603     // Use copyRecord to link the optional to the result object of the call
604     // expression.
605     auto &ResultLoc = State.Env.getResultObjectLocation(*CE);
606     copyRecord(cast<RecordStorageLocation>(Loc), ResultLoc, State.Env);
607     return true;
608   }
609 
610   return false;
611 }
612 
613 void handleConstMemberCallWithFallbacks(
614     const CallExpr *CE, dataflow::RecordStorageLocation *RecordLoc,
615     const MatchFinder::MatchResult &Result, LatticeTransferState &State) {
616   if (handleConstMemberCall(CE, RecordLoc, Result, State))
617     return;
618   // Perform default handling if the call returns an optional, but wasn't
619   // handled by caching.
620   if (isSupportedOptionalType(CE->getType()))
621     transferCallReturningOptional(CE, Result, State);
622 }
623 
624 void transferConstMemberCall(const CXXMemberCallExpr *MCE,
625                              const MatchFinder::MatchResult &Result,
626                              LatticeTransferState &State) {
627   handleConstMemberCallWithFallbacks(
628       MCE, dataflow::getImplicitObjectLocation(*MCE, State.Env), Result, State);
629 }
630 
631 void transferConstMemberOperatorCall(const CXXOperatorCallExpr *OCE,
632                                      const MatchFinder::MatchResult &Result,
633                                      LatticeTransferState &State) {
634   auto *RecordLoc = cast_or_null<dataflow::RecordStorageLocation>(
635       State.Env.getStorageLocation(*OCE->getArg(0)));
636   handleConstMemberCallWithFallbacks(OCE, RecordLoc, Result, State);
637 }
638 
639 void handleNonConstMemberCall(const CallExpr *CE,
640                               dataflow::RecordStorageLocation *RecordLoc,
641                               const MatchFinder::MatchResult &Result,
642                               LatticeTransferState &State) {
643   if (RecordLoc != nullptr) {
644     // When a non-const member function is called, clear all (non-const)
645     // optional fields of the receiver. Const-qualified fields can't be
646     // changed (at least, not without UB).
647     for (const auto &[Field, FieldLoc] : RecordLoc->children()) {
648       QualType FieldType = Field->getType();
649       if (!FieldType.isConstQualified() &&
650           isSupportedOptionalType(Field->getType())) {
651         auto *FieldRecordLoc = cast_or_null<RecordStorageLocation>(FieldLoc);
652         if (FieldRecordLoc) {
653           setHasValue(*FieldRecordLoc, State.Env.makeAtomicBoolValue(),
654                       State.Env);
655         }
656       }
657     }
658     State.Lattice.clearConstMethodReturnValues(*RecordLoc);
659     State.Lattice.clearConstMethodReturnStorageLocations(*RecordLoc);
660   }
661 
662   // Perform default handling if the call returns an optional.
663   if (isSupportedOptionalType(CE->getType())) {
664     transferCallReturningOptional(CE, Result, State);
665   }
666 }
667 
668 void transferValue_NonConstMemberCall(const CXXMemberCallExpr *MCE,
669                                       const MatchFinder::MatchResult &Result,
670                                       LatticeTransferState &State) {
671   handleNonConstMemberCall(
672       MCE, dataflow::getImplicitObjectLocation(*MCE, State.Env), Result, State);
673 }
674 
675 void transferValue_NonConstMemberOperatorCall(
676     const CXXOperatorCallExpr *OCE, const MatchFinder::MatchResult &Result,
677     LatticeTransferState &State) {
678   auto *RecordLoc = cast_or_null<dataflow::RecordStorageLocation>(
679       State.Env.getStorageLocation(*OCE->getArg(0)));
680   handleNonConstMemberCall(OCE, RecordLoc, Result, State);
681 }
682 
683 void constructOptionalValue(const Expr &E, Environment &Env,
684                             BoolValue &HasValueVal) {
685   RecordStorageLocation &Loc = Env.getResultObjectLocation(E);
686   setHasValue(Loc, HasValueVal, Env);
687 }
688 
689 /// Returns a symbolic value for the "has_value" property of an `optional<T>`
690 /// value that is constructed/assigned from a value of type `U` or `optional<U>`
691 /// where `T` is constructible from `U`.
692 BoolValue &valueOrConversionHasValue(QualType DestType, const Expr &E,
693                                      const MatchFinder::MatchResult &MatchRes,
694                                      LatticeTransferState &State) {
695   const int DestTypeOptionalWrappersCount =
696       countOptionalWrappers(*MatchRes.Context, DestType);
697   const int ArgTypeOptionalWrappersCount = countOptionalWrappers(
698       *MatchRes.Context, E.getType().getNonReferenceType());
699 
700   // Is this an constructor of the form `template<class U> optional(U &&)` /
701   // assignment of the form `template<class U> optional& operator=(U &&)`
702   // (where `T` is assignable / constructible from `U`)?
703   // We recognize this because the number of optionals in the optional being
704   // assigned to is different from the function argument type.
705   if (DestTypeOptionalWrappersCount != ArgTypeOptionalWrappersCount)
706     return State.Env.getBoolLiteralValue(true);
707 
708   // Otherwise, this must be a constructor of the form
709   // `template <class U> optional<optional<U> &&)` / assignment of the form
710   // `template <class U> optional& operator=(optional<U> &&)
711   // (where, again, `T` is assignable / constructible from `U`).
712   auto *Loc = State.Env.get<RecordStorageLocation>(E);
713   if (auto *HasValueVal = getHasValue(State.Env, Loc))
714     return *HasValueVal;
715   return State.Env.makeAtomicBoolValue();
716 }
717 
718 void transferValueOrConversionConstructor(
719     const CXXConstructExpr *E, const MatchFinder::MatchResult &MatchRes,
720     LatticeTransferState &State) {
721   assert(E->getNumArgs() > 0);
722 
723   constructOptionalValue(
724       *E, State.Env,
725       valueOrConversionHasValue(
726           E->getConstructor()->getThisType()->getPointeeType(), *E->getArg(0),
727           MatchRes, State));
728 }
729 
730 void transferAssignment(const CXXOperatorCallExpr *E, BoolValue &HasValueVal,
731                         LatticeTransferState &State) {
732   assert(E->getNumArgs() > 0);
733 
734   if (auto *Loc = State.Env.get<RecordStorageLocation>(*E->getArg(0))) {
735     setHasValue(*Loc, HasValueVal, State.Env);
736 
737     // Assign a storage location for the whole expression.
738     State.Env.setStorageLocation(*E, *Loc);
739   }
740 }
741 
742 void transferValueOrConversionAssignment(
743     const CXXOperatorCallExpr *E, const MatchFinder::MatchResult &MatchRes,
744     LatticeTransferState &State) {
745   assert(E->getNumArgs() > 1);
746   transferAssignment(
747       E,
748       valueOrConversionHasValue(E->getArg(0)->getType().getNonReferenceType(),
749                                 *E->getArg(1), MatchRes, State),
750       State);
751 }
752 
753 void transferNulloptAssignment(const CXXOperatorCallExpr *E,
754                                const MatchFinder::MatchResult &,
755                                LatticeTransferState &State) {
756   transferAssignment(E, State.Env.getBoolLiteralValue(false), State);
757 }
758 
759 void transferSwap(RecordStorageLocation *Loc1, RecordStorageLocation *Loc2,
760                   Environment &Env) {
761   // We account for cases where one or both of the optionals are not modeled,
762   // either lacking associated storage locations, or lacking values associated
763   // to such storage locations.
764 
765   if (Loc1 == nullptr) {
766     if (Loc2 != nullptr)
767       setHasValue(*Loc2, Env.makeAtomicBoolValue(), Env);
768     return;
769   }
770   if (Loc2 == nullptr) {
771     setHasValue(*Loc1, Env.makeAtomicBoolValue(), Env);
772     return;
773   }
774 
775   // Both expressions have locations, though they may not have corresponding
776   // values. In that case, we create a fresh value at this point. Note that if
777   // two branches both do this, they will not share the value, but it at least
778   // allows for local reasoning about the value. To avoid the above, we would
779   // need *lazy* value allocation.
780   // FIXME: allocate values lazily, instead of just creating a fresh value.
781   BoolValue *BoolVal1 = getHasValue(Env, Loc1);
782   if (BoolVal1 == nullptr)
783     BoolVal1 = &Env.makeAtomicBoolValue();
784 
785   BoolValue *BoolVal2 = getHasValue(Env, Loc2);
786   if (BoolVal2 == nullptr)
787     BoolVal2 = &Env.makeAtomicBoolValue();
788 
789   setHasValue(*Loc1, *BoolVal2, Env);
790   setHasValue(*Loc2, *BoolVal1, Env);
791 }
792 
793 void transferSwapCall(const CXXMemberCallExpr *E,
794                       const MatchFinder::MatchResult &,
795                       LatticeTransferState &State) {
796   assert(E->getNumArgs() == 1);
797   auto *OtherLoc = State.Env.get<RecordStorageLocation>(*E->getArg(0));
798   transferSwap(getImplicitObjectLocation(*E, State.Env), OtherLoc, State.Env);
799 }
800 
801 void transferStdSwapCall(const CallExpr *E, const MatchFinder::MatchResult &,
802                          LatticeTransferState &State) {
803   assert(E->getNumArgs() == 2);
804   auto *Arg0Loc = State.Env.get<RecordStorageLocation>(*E->getArg(0));
805   auto *Arg1Loc = State.Env.get<RecordStorageLocation>(*E->getArg(1));
806   transferSwap(Arg0Loc, Arg1Loc, State.Env);
807 }
808 
809 void transferStdForwardCall(const CallExpr *E, const MatchFinder::MatchResult &,
810                             LatticeTransferState &State) {
811   assert(E->getNumArgs() == 1);
812 
813   if (auto *Loc = State.Env.getStorageLocation(*E->getArg(0)))
814     State.Env.setStorageLocation(*E, *Loc);
815 }
816 
817 const Formula &evaluateEquality(Arena &A, const Formula &EqVal,
818                                 const Formula &LHS, const Formula &RHS) {
819   // Logically, an optional<T> object is composed of two values - a `has_value`
820   // bit and a value of type T. Equality of optional objects compares both
821   // values. Therefore, merely comparing the `has_value` bits isn't sufficient:
822   // when two optional objects are engaged, the equality of their respective
823   // values of type T matters. Since we only track the `has_value` bits, we
824   // can't make any conclusions about equality when we know that two optional
825   // objects are engaged.
826   //
827   // We express this as two facts about the equality:
828   // a) EqVal => (LHS & RHS) v (!RHS & !LHS)
829   //    If they are equal, then either both are set or both are unset.
830   // b) (!LHS & !RHS) => EqVal
831   //    If neither is set, then they are equal.
832   // We rewrite b) as !EqVal => (LHS v RHS), for a more compact formula.
833   return A.makeAnd(
834       A.makeImplies(EqVal, A.makeOr(A.makeAnd(LHS, RHS),
835                                     A.makeAnd(A.makeNot(LHS), A.makeNot(RHS)))),
836       A.makeImplies(A.makeNot(EqVal), A.makeOr(LHS, RHS)));
837 }
838 
839 void transferOptionalAndOptionalCmp(const clang::CXXOperatorCallExpr *CmpExpr,
840                                     const MatchFinder::MatchResult &,
841                                     LatticeTransferState &State) {
842   Environment &Env = State.Env;
843   auto &A = Env.arena();
844   auto *CmpValue = &forceBoolValue(Env, *CmpExpr);
845   auto *Arg0Loc = Env.get<RecordStorageLocation>(*CmpExpr->getArg(0));
846   if (auto *LHasVal = getHasValue(Env, Arg0Loc)) {
847     auto *Arg1Loc = Env.get<RecordStorageLocation>(*CmpExpr->getArg(1));
848     if (auto *RHasVal = getHasValue(Env, Arg1Loc)) {
849       if (CmpExpr->getOperator() == clang::OO_ExclaimEqual)
850         CmpValue = &A.makeNot(*CmpValue);
851       Env.assume(evaluateEquality(A, *CmpValue, LHasVal->formula(),
852                                   RHasVal->formula()));
853     }
854   }
855 }
856 
857 void transferOptionalAndValueCmp(const clang::CXXOperatorCallExpr *CmpExpr,
858                                  const clang::Expr *E, Environment &Env) {
859   auto &A = Env.arena();
860   auto *CmpValue = &forceBoolValue(Env, *CmpExpr);
861   auto *Loc = Env.get<RecordStorageLocation>(*E);
862   if (auto *HasVal = getHasValue(Env, Loc)) {
863     if (CmpExpr->getOperator() == clang::OO_ExclaimEqual)
864       CmpValue = &A.makeNot(*CmpValue);
865     Env.assume(
866         evaluateEquality(A, *CmpValue, HasVal->formula(), A.makeLiteral(true)));
867   }
868 }
869 
870 void transferOptionalAndNulloptCmp(const clang::CXXOperatorCallExpr *CmpExpr,
871                                    const clang::Expr *E, Environment &Env) {
872   auto &A = Env.arena();
873   auto *CmpValue = &forceBoolValue(Env, *CmpExpr);
874   auto *Loc = Env.get<RecordStorageLocation>(*E);
875   if (auto *HasVal = getHasValue(Env, Loc)) {
876     if (CmpExpr->getOperator() == clang::OO_ExclaimEqual)
877       CmpValue = &A.makeNot(*CmpValue);
878     Env.assume(evaluateEquality(A, *CmpValue, HasVal->formula(),
879                                 A.makeLiteral(false)));
880   }
881 }
882 
883 std::optional<StatementMatcher>
884 ignorableOptional(const UncheckedOptionalAccessModelOptions &Options) {
885   if (Options.IgnoreSmartPointerDereference) {
886     auto SmartPtrUse = expr(ignoringParenImpCasts(cxxOperatorCallExpr(
887         anyOf(hasOverloadedOperatorName("->"), hasOverloadedOperatorName("*")),
888         unless(hasArgument(0, expr(hasOptionalType()))))));
889     return expr(
890         anyOf(SmartPtrUse, memberExpr(hasObjectExpression(SmartPtrUse))));
891   }
892   return std::nullopt;
893 }
894 
895 StatementMatcher
896 valueCall(const std::optional<StatementMatcher> &IgnorableOptional) {
897   return isOptionalMemberCallWithNameMatcher(hasName("value"),
898                                              IgnorableOptional);
899 }
900 
901 StatementMatcher
902 valueOperatorCall(const std::optional<StatementMatcher> &IgnorableOptional) {
903   return expr(anyOf(isOptionalOperatorCallWithName("*", IgnorableOptional),
904                     isOptionalOperatorCallWithName("->", IgnorableOptional)));
905 }
906 
907 auto buildTransferMatchSwitch() {
908   // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
909   // lot of duplicated work (e.g. string comparisons), consider providing APIs
910   // that avoid it through memoization.
911   return CFGMatchSwitchBuilder<LatticeTransferState>()
912       // make_optional
913       .CaseOfCFGStmt<CallExpr>(isMakeOptionalCall(), transferMakeOptionalCall)
914 
915       // optional::optional (in place)
916       .CaseOfCFGStmt<CXXConstructExpr>(
917           isOptionalInPlaceConstructor(),
918           [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
919              LatticeTransferState &State) {
920             constructOptionalValue(*E, State.Env,
921                                    State.Env.getBoolLiteralValue(true));
922           })
923       // optional::optional(nullopt_t)
924       .CaseOfCFGStmt<CXXConstructExpr>(
925           isOptionalNulloptConstructor(),
926           [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
927              LatticeTransferState &State) {
928             constructOptionalValue(*E, State.Env,
929                                    State.Env.getBoolLiteralValue(false));
930           })
931       // optional::optional (value/conversion)
932       .CaseOfCFGStmt<CXXConstructExpr>(isOptionalValueOrConversionConstructor(),
933                                        transferValueOrConversionConstructor)
934 
935       // optional::operator=
936       .CaseOfCFGStmt<CXXOperatorCallExpr>(
937           isOptionalValueOrConversionAssignment(),
938           transferValueOrConversionAssignment)
939       .CaseOfCFGStmt<CXXOperatorCallExpr>(isOptionalNulloptAssignment(),
940                                           transferNulloptAssignment)
941 
942       // optional::value
943       .CaseOfCFGStmt<CXXMemberCallExpr>(
944           valueCall(std::nullopt),
945           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
946              LatticeTransferState &State) {
947             transferUnwrapCall(E, E->getImplicitObjectArgument(), State);
948           })
949 
950       // optional::operator*
951       .CaseOfCFGStmt<CallExpr>(isOptionalOperatorCallWithName("*"),
952                                [](const CallExpr *E,
953                                   const MatchFinder::MatchResult &,
954                                   LatticeTransferState &State) {
955                                  transferUnwrapCall(E, E->getArg(0), State);
956                                })
957 
958       // optional::operator->
959       .CaseOfCFGStmt<CallExpr>(isOptionalOperatorCallWithName("->"),
960                                [](const CallExpr *E,
961                                   const MatchFinder::MatchResult &,
962                                   LatticeTransferState &State) {
963                                  transferArrowOpCall(E, E->getArg(0), State);
964                                })
965 
966       // optional::has_value, optional::hasValue
967       // Of the supported optionals only folly::Optional uses hasValue, but this
968       // will also pass for other types
969       .CaseOfCFGStmt<CXXMemberCallExpr>(
970           isOptionalMemberCallWithNameMatcher(
971               hasAnyName("has_value", "hasValue")),
972           transferOptionalHasValueCall)
973 
974       // optional::operator bool
975       .CaseOfCFGStmt<CXXMemberCallExpr>(
976           isOptionalMemberCallWithNameMatcher(hasName("operator bool")),
977           transferOptionalHasValueCall)
978 
979       // NullableValue::isNull
980       // Only NullableValue has isNull
981       .CaseOfCFGStmt<CXXMemberCallExpr>(
982           isOptionalMemberCallWithNameMatcher(hasName("isNull")),
983           transferOptionalIsNullCall)
984 
985       // optional::emplace
986       .CaseOfCFGStmt<CXXMemberCallExpr>(
987           isOptionalMemberCallWithNameMatcher(hasName("emplace")),
988           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
989              LatticeTransferState &State) {
990             if (RecordStorageLocation *Loc =
991                     getImplicitObjectLocation(*E, State.Env)) {
992               setHasValue(*Loc, State.Env.getBoolLiteralValue(true), State.Env);
993             }
994           })
995 
996       // optional::reset
997       .CaseOfCFGStmt<CXXMemberCallExpr>(
998           isOptionalMemberCallWithNameMatcher(hasName("reset")),
999           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
1000              LatticeTransferState &State) {
1001             if (RecordStorageLocation *Loc =
1002                     getImplicitObjectLocation(*E, State.Env)) {
1003               setHasValue(*Loc, State.Env.getBoolLiteralValue(false),
1004                           State.Env);
1005             }
1006           })
1007 
1008       // optional::swap
1009       .CaseOfCFGStmt<CXXMemberCallExpr>(
1010           isOptionalMemberCallWithNameMatcher(hasName("swap")),
1011           transferSwapCall)
1012 
1013       // std::swap
1014       .CaseOfCFGStmt<CallExpr>(isStdSwapCall(), transferStdSwapCall)
1015 
1016       // std::forward
1017       .CaseOfCFGStmt<CallExpr>(isStdForwardCall(), transferStdForwardCall)
1018 
1019       // opt.value_or("").empty()
1020       .CaseOfCFGStmt<Expr>(isValueOrStringEmptyCall(),
1021                            transferValueOrStringEmptyCall)
1022 
1023       // opt.value_or(X) != X
1024       .CaseOfCFGStmt<Expr>(isValueOrNotEqX(), transferValueOrNotEqX)
1025 
1026       // Comparisons (==, !=):
1027       .CaseOfCFGStmt<CXXOperatorCallExpr>(
1028           isComparisonOperatorCall(hasOptionalType(), hasOptionalType()),
1029           transferOptionalAndOptionalCmp)
1030       .CaseOfCFGStmt<CXXOperatorCallExpr>(
1031           isComparisonOperatorCall(hasOptionalType(), hasNulloptType()),
1032           [](const clang::CXXOperatorCallExpr *Cmp,
1033              const MatchFinder::MatchResult &, LatticeTransferState &State) {
1034             transferOptionalAndNulloptCmp(Cmp, Cmp->getArg(0), State.Env);
1035           })
1036       .CaseOfCFGStmt<CXXOperatorCallExpr>(
1037           isComparisonOperatorCall(hasNulloptType(), hasOptionalType()),
1038           [](const clang::CXXOperatorCallExpr *Cmp,
1039              const MatchFinder::MatchResult &, LatticeTransferState &State) {
1040             transferOptionalAndNulloptCmp(Cmp, Cmp->getArg(1), State.Env);
1041           })
1042       .CaseOfCFGStmt<CXXOperatorCallExpr>(
1043           isComparisonOperatorCall(
1044               hasOptionalType(),
1045               unless(anyOf(hasOptionalType(), hasNulloptType()))),
1046           [](const clang::CXXOperatorCallExpr *Cmp,
1047              const MatchFinder::MatchResult &, LatticeTransferState &State) {
1048             transferOptionalAndValueCmp(Cmp, Cmp->getArg(0), State.Env);
1049           })
1050       .CaseOfCFGStmt<CXXOperatorCallExpr>(
1051           isComparisonOperatorCall(
1052               unless(anyOf(hasOptionalType(), hasNulloptType())),
1053               hasOptionalType()),
1054           [](const clang::CXXOperatorCallExpr *Cmp,
1055              const MatchFinder::MatchResult &, LatticeTransferState &State) {
1056             transferOptionalAndValueCmp(Cmp, Cmp->getArg(1), State.Env);
1057           })
1058 
1059       // Smart-pointer-like operator* and operator-> calls that may look like
1060       // const accessors (below) but need special handling to allow mixing
1061       // the accessor calls.
1062       .CaseOfCFGStmt<CXXOperatorCallExpr>(
1063           isSmartPointerLikeOperatorStar(),
1064           [](const CXXOperatorCallExpr *E,
1065              const MatchFinder::MatchResult &Result,
1066              LatticeTransferState &State) {
1067             transferSmartPointerLikeCachedDeref(
1068                 E,
1069                 dyn_cast_or_null<RecordStorageLocation>(
1070                     getLocBehindPossiblePointer(*E->getArg(0), State.Env)),
1071                 State, [](StorageLocation &Loc) {});
1072           })
1073       .CaseOfCFGStmt<CXXOperatorCallExpr>(
1074           isSmartPointerLikeOperatorArrow(),
1075           [](const CXXOperatorCallExpr *E,
1076              const MatchFinder::MatchResult &Result,
1077              LatticeTransferState &State) {
1078             transferSmartPointerLikeCachedGet(
1079                 E,
1080                 dyn_cast_or_null<RecordStorageLocation>(
1081                     getLocBehindPossiblePointer(*E->getArg(0), State.Env)),
1082                 State, [](StorageLocation &Loc) {});
1083           })
1084       .CaseOfCFGStmt<CXXMemberCallExpr>(
1085           isSmartPointerLikeValueMethodCall(),
1086           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &Result,
1087              LatticeTransferState &State) {
1088             transferSmartPointerLikeCachedDeref(
1089                 E, getImplicitObjectLocation(*E, State.Env), State,
1090                 [](StorageLocation &Loc) {});
1091           })
1092       .CaseOfCFGStmt<CXXMemberCallExpr>(
1093           isSmartPointerLikeGetMethodCall(),
1094           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &Result,
1095              LatticeTransferState &State) {
1096             transferSmartPointerLikeCachedGet(
1097                 E, getImplicitObjectLocation(*E, State.Env), State,
1098                 [](StorageLocation &Loc) {});
1099           })
1100 
1101       // const accessor calls
1102       .CaseOfCFGStmt<CXXMemberCallExpr>(isZeroParamConstMemberCall(),
1103                                         transferConstMemberCall)
1104       .CaseOfCFGStmt<CXXOperatorCallExpr>(isZeroParamConstMemberOperatorCall(),
1105                                           transferConstMemberOperatorCall)
1106       // non-const member calls that may modify the state of an object.
1107       .CaseOfCFGStmt<CXXMemberCallExpr>(isNonConstMemberCall(),
1108                                         transferValue_NonConstMemberCall)
1109       .CaseOfCFGStmt<CXXOperatorCallExpr>(
1110           isNonConstMemberOperatorCall(),
1111           transferValue_NonConstMemberOperatorCall)
1112 
1113       // other cases of returning optional
1114       .CaseOfCFGStmt<CallExpr>(isCallReturningOptional(),
1115                                transferCallReturningOptional)
1116 
1117       .Build();
1118 }
1119 
1120 llvm::SmallVector<UncheckedOptionalAccessDiagnostic>
1121 diagnoseUnwrapCall(const Expr *ObjectExpr, const Environment &Env) {
1122   if (auto *OptionalLoc = cast_or_null<RecordStorageLocation>(
1123           getLocBehindPossiblePointer(*ObjectExpr, Env))) {
1124     auto *Prop = Env.getValue(locForHasValue(*OptionalLoc));
1125     if (auto *HasValueVal = cast_or_null<BoolValue>(Prop)) {
1126       if (Env.proves(HasValueVal->formula()))
1127         return {};
1128     }
1129   }
1130 
1131   // Record that this unwrap is *not* provably safe.
1132   // FIXME: include the name of the optional (if applicable).
1133   auto Range = CharSourceRange::getTokenRange(ObjectExpr->getSourceRange());
1134   return {UncheckedOptionalAccessDiagnostic{Range}};
1135 }
1136 
1137 auto buildDiagnoseMatchSwitch(
1138     const UncheckedOptionalAccessModelOptions &Options) {
1139   // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
1140   // lot of duplicated work (e.g. string comparisons), consider providing APIs
1141   // that avoid it through memoization.
1142   auto IgnorableOptional = ignorableOptional(Options);
1143   return CFGMatchSwitchBuilder<
1144              const Environment,
1145              llvm::SmallVector<UncheckedOptionalAccessDiagnostic>>()
1146       // optional::value
1147       .CaseOfCFGStmt<CXXMemberCallExpr>(
1148           valueCall(IgnorableOptional),
1149           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
1150              const Environment &Env) {
1151             return diagnoseUnwrapCall(E->getImplicitObjectArgument(), Env);
1152           })
1153 
1154       // optional::operator*, optional::operator->
1155       .CaseOfCFGStmt<CallExpr>(valueOperatorCall(IgnorableOptional),
1156                                [](const CallExpr *E,
1157                                   const MatchFinder::MatchResult &,
1158                                   const Environment &Env) {
1159                                  return diagnoseUnwrapCall(E->getArg(0), Env);
1160                                })
1161       .Build();
1162 }
1163 
1164 } // namespace
1165 
1166 ast_matchers::DeclarationMatcher
1167 UncheckedOptionalAccessModel::optionalClassDecl() {
1168   return cxxRecordDecl(optionalClass());
1169 }
1170 
1171 UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(ASTContext &Ctx,
1172                                                            Environment &Env)
1173     : DataflowAnalysis<UncheckedOptionalAccessModel,
1174                        UncheckedOptionalAccessLattice>(Ctx),
1175       TransferMatchSwitch(buildTransferMatchSwitch()) {
1176   Env.getDataflowAnalysisContext().setSyntheticFieldCallback(
1177       [&Ctx](QualType Ty) -> llvm::StringMap<QualType> {
1178         const CXXRecordDecl *Optional =
1179             getOptionalBaseClass(Ty->getAsCXXRecordDecl());
1180         if (Optional == nullptr)
1181           return {};
1182         return {{"value", valueTypeFromOptionalDecl(*Optional)},
1183                 {"has_value", Ctx.BoolTy}};
1184       });
1185 }
1186 
1187 void UncheckedOptionalAccessModel::transfer(const CFGElement &Elt,
1188                                             UncheckedOptionalAccessLattice &L,
1189                                             Environment &Env) {
1190   LatticeTransferState State(L, Env);
1191   TransferMatchSwitch(Elt, getASTContext(), State);
1192 }
1193 
1194 UncheckedOptionalAccessDiagnoser::UncheckedOptionalAccessDiagnoser(
1195     UncheckedOptionalAccessModelOptions Options)
1196     : DiagnoseMatchSwitch(buildDiagnoseMatchSwitch(Options)) {}
1197 
1198 } // namespace dataflow
1199 } // namespace clang
1200