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                                         llvm::StringRef Name) {
43   return NS.getDeclName().isIdentifier() && NS.getName() == Name &&
44          NS.getParent() != nullptr && NS.getParent()->isTranslationUnit();
45 }
46 
47 static bool hasOptionalClassName(const CXXRecordDecl &RD) {
48   if (!RD.getDeclName().isIdentifier())
49     return false;
50 
51   if (RD.getName() == "optional") {
52     if (const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext()))
53       return N->isStdNamespace() || isTopLevelNamespaceWithName(*N, "absl");
54     return false;
55   }
56 
57   if (RD.getName() == "Optional") {
58     // Check whether namespace is "::base" or "::folly".
59     const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext());
60     return N != nullptr && (isTopLevelNamespaceWithName(*N, "base") ||
61                             isTopLevelNamespaceWithName(*N, "folly"));
62   }
63 
64   return false;
65 }
66 
67 namespace {
68 
69 using namespace ::clang::ast_matchers;
70 using LatticeTransferState = TransferState<NoopLattice>;
71 
72 AST_MATCHER(CXXRecordDecl, hasOptionalClassNameMatcher) {
73   return hasOptionalClassName(Node);
74 }
75 
76 DeclarationMatcher optionalClass() {
77   return classTemplateSpecializationDecl(
78       hasOptionalClassNameMatcher(),
79       hasTemplateArgument(0, refersToType(type().bind("T"))));
80 }
81 
82 auto optionalOrAliasType() {
83   return hasUnqualifiedDesugaredType(
84       recordType(hasDeclaration(optionalClass())));
85 }
86 
87 /// Matches any of the spellings of the optional types and sugar, aliases, etc.
88 auto hasOptionalType() { return hasType(optionalOrAliasType()); }
89 
90 auto isOptionalMemberCallWithNameMatcher(
91     ast_matchers::internal::Matcher<NamedDecl> matcher,
92     const std::optional<StatementMatcher> &Ignorable = std::nullopt) {
93   auto Exception = unless(Ignorable ? expr(anyOf(*Ignorable, cxxThisExpr()))
94                                     : cxxThisExpr());
95   return cxxMemberCallExpr(
96       on(expr(Exception,
97               anyOf(hasOptionalType(),
98                     hasType(pointerType(pointee(optionalOrAliasType())))))),
99       callee(cxxMethodDecl(matcher)));
100 }
101 
102 auto isOptionalOperatorCallWithName(
103     llvm::StringRef operator_name,
104     const std::optional<StatementMatcher> &Ignorable = std::nullopt) {
105   return cxxOperatorCallExpr(
106       hasOverloadedOperatorName(operator_name),
107       callee(cxxMethodDecl(ofClass(optionalClass()))),
108       Ignorable ? callExpr(unless(hasArgument(0, *Ignorable))) : callExpr());
109 }
110 
111 auto isMakeOptionalCall() {
112   return callExpr(callee(functionDecl(hasAnyName(
113                       "std::make_optional", "base::make_optional",
114                       "absl::make_optional", "folly::make_optional"))),
115                   hasOptionalType());
116 }
117 
118 auto nulloptTypeDecl() {
119   return namedDecl(hasAnyName("std::nullopt_t", "absl::nullopt_t",
120                               "base::nullopt_t", "folly::None"));
121 }
122 
123 auto hasNulloptType() { return hasType(nulloptTypeDecl()); }
124 
125 auto inPlaceClass() {
126   return recordDecl(hasAnyName("std::in_place_t", "absl::in_place_t",
127                                "base::in_place_t", "folly::in_place_t"));
128 }
129 
130 auto isOptionalNulloptConstructor() {
131   return cxxConstructExpr(
132       hasOptionalType(),
133       hasDeclaration(cxxConstructorDecl(parameterCountIs(1),
134                                         hasParameter(0, hasNulloptType()))));
135 }
136 
137 auto isOptionalInPlaceConstructor() {
138   return cxxConstructExpr(hasOptionalType(),
139                           hasArgument(0, hasType(inPlaceClass())));
140 }
141 
142 auto isOptionalValueOrConversionConstructor() {
143   return cxxConstructExpr(
144       hasOptionalType(),
145       unless(hasDeclaration(
146           cxxConstructorDecl(anyOf(isCopyConstructor(), isMoveConstructor())))),
147       argumentCountIs(1), hasArgument(0, unless(hasNulloptType())));
148 }
149 
150 auto isOptionalValueOrConversionAssignment() {
151   return cxxOperatorCallExpr(
152       hasOverloadedOperatorName("="),
153       callee(cxxMethodDecl(ofClass(optionalClass()))),
154       unless(hasDeclaration(cxxMethodDecl(
155           anyOf(isCopyAssignmentOperator(), isMoveAssignmentOperator())))),
156       argumentCountIs(2), hasArgument(1, unless(hasNulloptType())));
157 }
158 
159 auto isOptionalNulloptAssignment() {
160   return cxxOperatorCallExpr(hasOverloadedOperatorName("="),
161                              callee(cxxMethodDecl(ofClass(optionalClass()))),
162                              argumentCountIs(2),
163                              hasArgument(1, hasNulloptType()));
164 }
165 
166 auto isStdSwapCall() {
167   return callExpr(callee(functionDecl(hasName("std::swap"))),
168                   argumentCountIs(2), hasArgument(0, hasOptionalType()),
169                   hasArgument(1, hasOptionalType()));
170 }
171 
172 auto isStdForwardCall() {
173   return callExpr(callee(functionDecl(hasName("std::forward"))),
174                   argumentCountIs(1), hasArgument(0, hasOptionalType()));
175 }
176 
177 constexpr llvm::StringLiteral ValueOrCallID = "ValueOrCall";
178 
179 auto isValueOrStringEmptyCall() {
180   // `opt.value_or("").empty()`
181   return cxxMemberCallExpr(
182       callee(cxxMethodDecl(hasName("empty"))),
183       onImplicitObjectArgument(ignoringImplicit(
184           cxxMemberCallExpr(on(expr(unless(cxxThisExpr()))),
185                             callee(cxxMethodDecl(hasName("value_or"),
186                                                  ofClass(optionalClass()))),
187                             hasArgument(0, stringLiteral(hasSize(0))))
188               .bind(ValueOrCallID))));
189 }
190 
191 auto isValueOrNotEqX() {
192   auto ComparesToSame = [](ast_matchers::internal::Matcher<Stmt> Arg) {
193     return hasOperands(
194         ignoringImplicit(
195             cxxMemberCallExpr(on(expr(unless(cxxThisExpr()))),
196                               callee(cxxMethodDecl(hasName("value_or"),
197                                                    ofClass(optionalClass()))),
198                               hasArgument(0, Arg))
199                 .bind(ValueOrCallID)),
200         ignoringImplicit(Arg));
201   };
202 
203   // `opt.value_or(X) != X`, for X is `nullptr`, `""`, or `0`. Ideally, we'd
204   // support this pattern for any expression, but the AST does not have a
205   // generic expression comparison facility, so we specialize to common cases
206   // seen in practice.  FIXME: define a matcher that compares values across
207   // nodes, which would let us generalize this to any `X`.
208   return binaryOperation(hasOperatorName("!="),
209                          anyOf(ComparesToSame(cxxNullPtrLiteralExpr()),
210                                ComparesToSame(stringLiteral(hasSize(0))),
211                                ComparesToSame(integerLiteral(equals(0)))));
212 }
213 
214 auto isCallReturningOptional() {
215   return callExpr(hasType(qualType(anyOf(
216       optionalOrAliasType(), referenceType(pointee(optionalOrAliasType()))))));
217 }
218 
219 template <typename L, typename R>
220 auto isComparisonOperatorCall(L lhs_arg_matcher, R rhs_arg_matcher) {
221   return cxxOperatorCallExpr(
222       anyOf(hasOverloadedOperatorName("=="), hasOverloadedOperatorName("!=")),
223       argumentCountIs(2), hasArgument(0, lhs_arg_matcher),
224       hasArgument(1, rhs_arg_matcher));
225 }
226 
227 /// Ensures that `Expr` is mapped to a `BoolValue` and returns its formula.
228 const Formula &forceBoolValue(Environment &Env, const Expr &Expr) {
229   auto *Value = cast_or_null<BoolValue>(Env.getValue(Expr));
230   if (Value != nullptr)
231     return Value->formula();
232 
233   Value = &Env.makeAtomicBoolValue();
234   Env.setValue(Expr, *Value);
235   return Value->formula();
236 }
237 
238 StorageLocation &locForHasValue(const RecordStorageLocation &OptionalLoc) {
239   return OptionalLoc.getSyntheticField("has_value");
240 }
241 
242 StorageLocation &locForValue(const RecordStorageLocation &OptionalLoc) {
243   return OptionalLoc.getSyntheticField("value");
244 }
245 
246 /// Sets `HasValueVal` as the symbolic value that represents the "has_value"
247 /// property of the optional at `OptionalLoc`.
248 void setHasValue(RecordStorageLocation &OptionalLoc, BoolValue &HasValueVal,
249                  Environment &Env) {
250   Env.setValue(locForHasValue(OptionalLoc), HasValueVal);
251 }
252 
253 /// Creates a symbolic value for an `optional` value at an existing storage
254 /// location. Uses `HasValueVal` as the symbolic value of the "has_value"
255 /// property.
256 RecordValue &createOptionalValue(RecordStorageLocation &Loc,
257                                  BoolValue &HasValueVal, Environment &Env) {
258   auto &OptionalVal = Env.create<RecordValue>(Loc);
259   Env.setValue(Loc, OptionalVal);
260   setHasValue(Loc, HasValueVal, Env);
261   return OptionalVal;
262 }
263 
264 /// Returns the symbolic value that represents the "has_value" property of the
265 /// optional at `OptionalLoc`. Returns null if `OptionalLoc` is null.
266 BoolValue *getHasValue(Environment &Env, RecordStorageLocation *OptionalLoc) {
267   if (OptionalLoc == nullptr)
268     return nullptr;
269   StorageLocation &HasValueLoc = locForHasValue(*OptionalLoc);
270   auto *HasValueVal = cast_or_null<BoolValue>(Env.getValue(HasValueLoc));
271   if (HasValueVal == nullptr) {
272     HasValueVal = &Env.makeAtomicBoolValue();
273     Env.setValue(HasValueLoc, *HasValueVal);
274   }
275   return HasValueVal;
276 }
277 
278 /// Returns true if and only if `Type` is an optional type.
279 bool isOptionalType(QualType Type) {
280   if (!Type->isRecordType())
281     return false;
282   const CXXRecordDecl *D = Type->getAsCXXRecordDecl();
283   return D != nullptr && hasOptionalClassName(*D);
284 }
285 
286 /// Returns the number of optional wrappers in `Type`.
287 ///
288 /// For example, if `Type` is `optional<optional<int>>`, the result of this
289 /// function will be 2.
290 int countOptionalWrappers(const ASTContext &ASTCtx, QualType Type) {
291   if (!isOptionalType(Type))
292     return 0;
293   return 1 + countOptionalWrappers(
294                  ASTCtx,
295                  cast<ClassTemplateSpecializationDecl>(Type->getAsRecordDecl())
296                      ->getTemplateArgs()
297                      .get(0)
298                      .getAsType()
299                      .getDesugaredType(ASTCtx));
300 }
301 
302 StorageLocation *getLocBehindPossiblePointer(const Expr &E,
303                                              const Environment &Env) {
304   if (E.isPRValue()) {
305     if (auto *PointerVal = dyn_cast_or_null<PointerValue>(Env.getValue(E)))
306       return &PointerVal->getPointeeLoc();
307     return nullptr;
308   }
309   return Env.getStorageLocation(E);
310 }
311 
312 void transferUnwrapCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
313                         LatticeTransferState &State) {
314   if (auto *OptionalLoc = cast_or_null<RecordStorageLocation>(
315           getLocBehindPossiblePointer(*ObjectExpr, State.Env))) {
316     if (State.Env.getStorageLocation(*UnwrapExpr) == nullptr)
317       State.Env.setStorageLocation(*UnwrapExpr, locForValue(*OptionalLoc));
318   }
319 }
320 
321 void transferArrowOpCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
322                          LatticeTransferState &State) {
323   if (auto *OptionalLoc = cast_or_null<RecordStorageLocation>(
324           getLocBehindPossiblePointer(*ObjectExpr, State.Env)))
325     State.Env.setValue(
326         *UnwrapExpr, State.Env.create<PointerValue>(locForValue(*OptionalLoc)));
327 }
328 
329 void transferMakeOptionalCall(const CallExpr *E,
330                               const MatchFinder::MatchResult &,
331                               LatticeTransferState &State) {
332   State.Env.setValue(
333       *E, createOptionalValue(State.Env.getResultObjectLocation(*E),
334                               State.Env.getBoolLiteralValue(true), State.Env));
335 }
336 
337 void transferOptionalHasValueCall(const CXXMemberCallExpr *CallExpr,
338                                   const MatchFinder::MatchResult &,
339                                   LatticeTransferState &State) {
340   if (auto *HasValueVal = getHasValue(
341           State.Env, getImplicitObjectLocation(*CallExpr, State.Env))) {
342     State.Env.setValue(*CallExpr, *HasValueVal);
343   }
344 }
345 
346 /// `ModelPred` builds a logical formula relating the predicate in
347 /// `ValueOrPredExpr` to the optional's `has_value` property.
348 void transferValueOrImpl(
349     const clang::Expr *ValueOrPredExpr, const MatchFinder::MatchResult &Result,
350     LatticeTransferState &State,
351     const Formula &(*ModelPred)(Environment &Env, const Formula &ExprVal,
352                                 const Formula &HasValueVal)) {
353   auto &Env = State.Env;
354 
355   const auto *MCE =
356       Result.Nodes.getNodeAs<clang::CXXMemberCallExpr>(ValueOrCallID);
357 
358   auto *HasValueVal =
359       getHasValue(State.Env, getImplicitObjectLocation(*MCE, State.Env));
360   if (HasValueVal == nullptr)
361     return;
362 
363   Env.assume(ModelPred(Env, forceBoolValue(Env, *ValueOrPredExpr),
364                        HasValueVal->formula()));
365 }
366 
367 void transferValueOrStringEmptyCall(const clang::Expr *ComparisonExpr,
368                                     const MatchFinder::MatchResult &Result,
369                                     LatticeTransferState &State) {
370   return transferValueOrImpl(ComparisonExpr, Result, State,
371                              [](Environment &Env, const Formula &ExprVal,
372                                 const Formula &HasValueVal) -> const Formula & {
373                                auto &A = Env.arena();
374                                // If the result is *not* empty, then we know the
375                                // optional must have been holding a value. If
376                                // `ExprVal` is true, though, we don't learn
377                                // anything definite about `has_value`, so we
378                                // don't add any corresponding implications to
379                                // the flow condition.
380                                return A.makeImplies(A.makeNot(ExprVal),
381                                                     HasValueVal);
382                              });
383 }
384 
385 void transferValueOrNotEqX(const Expr *ComparisonExpr,
386                            const MatchFinder::MatchResult &Result,
387                            LatticeTransferState &State) {
388   transferValueOrImpl(ComparisonExpr, Result, State,
389                       [](Environment &Env, const Formula &ExprVal,
390                          const Formula &HasValueVal) -> const Formula & {
391                         auto &A = Env.arena();
392                         // We know that if `(opt.value_or(X) != X)` then
393                         // `opt.hasValue()`, even without knowing further
394                         // details about the contents of `opt`.
395                         return A.makeImplies(ExprVal, HasValueVal);
396                       });
397 }
398 
399 void transferCallReturningOptional(const CallExpr *E,
400                                    const MatchFinder::MatchResult &Result,
401                                    LatticeTransferState &State) {
402   if (State.Env.getValue(*E) != nullptr)
403     return;
404 
405   RecordStorageLocation *Loc = nullptr;
406   if (E->isPRValue()) {
407     Loc = &State.Env.getResultObjectLocation(*E);
408   } else {
409     Loc = cast_or_null<RecordStorageLocation>(State.Env.getStorageLocation(*E));
410     if (Loc == nullptr) {
411       Loc = &cast<RecordStorageLocation>(State.Env.createStorageLocation(*E));
412       State.Env.setStorageLocation(*E, *Loc);
413     }
414   }
415 
416   RecordValue &Val =
417       createOptionalValue(*Loc, State.Env.makeAtomicBoolValue(), State.Env);
418   if (E->isPRValue())
419     State.Env.setValue(*E, Val);
420 }
421 
422 void constructOptionalValue(const Expr &E, Environment &Env,
423                             BoolValue &HasValueVal) {
424   RecordStorageLocation &Loc = Env.getResultObjectLocation(E);
425   Env.setValue(E, createOptionalValue(Loc, HasValueVal, Env));
426 }
427 
428 /// Returns a symbolic value for the "has_value" property of an `optional<T>`
429 /// value that is constructed/assigned from a value of type `U` or `optional<U>`
430 /// where `T` is constructible from `U`.
431 BoolValue &valueOrConversionHasValue(const FunctionDecl &F, const Expr &E,
432                                      const MatchFinder::MatchResult &MatchRes,
433                                      LatticeTransferState &State) {
434   assert(F.getTemplateSpecializationArgs() != nullptr);
435   assert(F.getTemplateSpecializationArgs()->size() > 0);
436 
437   const int TemplateParamOptionalWrappersCount =
438       countOptionalWrappers(*MatchRes.Context, F.getTemplateSpecializationArgs()
439                                                    ->get(0)
440                                                    .getAsType()
441                                                    .getNonReferenceType());
442   const int ArgTypeOptionalWrappersCount = countOptionalWrappers(
443       *MatchRes.Context, E.getType().getNonReferenceType());
444 
445   // Check if this is a constructor/assignment call for `optional<T>` with
446   // argument of type `U` such that `T` is constructible from `U`.
447   if (TemplateParamOptionalWrappersCount == ArgTypeOptionalWrappersCount)
448     return State.Env.getBoolLiteralValue(true);
449 
450   // This is a constructor/assignment call for `optional<T>` with argument of
451   // type `optional<U>` such that `T` is constructible from `U`.
452   auto *Loc =
453       cast_or_null<RecordStorageLocation>(State.Env.getStorageLocation(E));
454   if (auto *HasValueVal = getHasValue(State.Env, Loc))
455     return *HasValueVal;
456   return State.Env.makeAtomicBoolValue();
457 }
458 
459 void transferValueOrConversionConstructor(
460     const CXXConstructExpr *E, const MatchFinder::MatchResult &MatchRes,
461     LatticeTransferState &State) {
462   assert(E->getNumArgs() > 0);
463 
464   constructOptionalValue(*E, State.Env,
465                          valueOrConversionHasValue(*E->getConstructor(),
466                                                    *E->getArg(0), MatchRes,
467                                                    State));
468 }
469 
470 void transferAssignment(const CXXOperatorCallExpr *E, BoolValue &HasValueVal,
471                         LatticeTransferState &State) {
472   assert(E->getNumArgs() > 0);
473 
474   if (auto *Loc = cast_or_null<RecordStorageLocation>(
475           State.Env.getStorageLocation(*E->getArg(0)))) {
476     createOptionalValue(*Loc, HasValueVal, State.Env);
477 
478     // Assign a storage location for the whole expression.
479     State.Env.setStorageLocation(*E, *Loc);
480   }
481 }
482 
483 void transferValueOrConversionAssignment(
484     const CXXOperatorCallExpr *E, const MatchFinder::MatchResult &MatchRes,
485     LatticeTransferState &State) {
486   assert(E->getNumArgs() > 1);
487   transferAssignment(E,
488                      valueOrConversionHasValue(*E->getDirectCallee(),
489                                                *E->getArg(1), MatchRes, State),
490                      State);
491 }
492 
493 void transferNulloptAssignment(const CXXOperatorCallExpr *E,
494                                const MatchFinder::MatchResult &,
495                                LatticeTransferState &State) {
496   transferAssignment(E, State.Env.getBoolLiteralValue(false), State);
497 }
498 
499 void transferSwap(RecordStorageLocation *Loc1, RecordStorageLocation *Loc2,
500                   Environment &Env) {
501   // We account for cases where one or both of the optionals are not modeled,
502   // either lacking associated storage locations, or lacking values associated
503   // to such storage locations.
504 
505   if (Loc1 == nullptr) {
506     if (Loc2 != nullptr)
507       createOptionalValue(*Loc2, Env.makeAtomicBoolValue(), Env);
508     return;
509   }
510   if (Loc2 == nullptr) {
511     createOptionalValue(*Loc1, Env.makeAtomicBoolValue(), Env);
512     return;
513   }
514 
515   // Both expressions have locations, though they may not have corresponding
516   // values. In that case, we create a fresh value at this point. Note that if
517   // two branches both do this, they will not share the value, but it at least
518   // allows for local reasoning about the value. To avoid the above, we would
519   // need *lazy* value allocation.
520   // FIXME: allocate values lazily, instead of just creating a fresh value.
521   BoolValue *BoolVal1 = getHasValue(Env, Loc1);
522   if (BoolVal1 == nullptr)
523     BoolVal1 = &Env.makeAtomicBoolValue();
524 
525   BoolValue *BoolVal2 = getHasValue(Env, Loc2);
526   if (BoolVal2 == nullptr)
527     BoolVal2 = &Env.makeAtomicBoolValue();
528 
529   createOptionalValue(*Loc1, *BoolVal2, Env);
530   createOptionalValue(*Loc2, *BoolVal1, Env);
531 }
532 
533 void transferSwapCall(const CXXMemberCallExpr *E,
534                       const MatchFinder::MatchResult &,
535                       LatticeTransferState &State) {
536   assert(E->getNumArgs() == 1);
537   auto *OtherLoc = cast_or_null<RecordStorageLocation>(
538       State.Env.getStorageLocation(*E->getArg(0)));
539   transferSwap(getImplicitObjectLocation(*E, State.Env), OtherLoc, State.Env);
540 }
541 
542 void transferStdSwapCall(const CallExpr *E, const MatchFinder::MatchResult &,
543                          LatticeTransferState &State) {
544   assert(E->getNumArgs() == 2);
545   auto *Arg0Loc = cast_or_null<RecordStorageLocation>(
546       State.Env.getStorageLocation(*E->getArg(0)));
547   auto *Arg1Loc = cast_or_null<RecordStorageLocation>(
548       State.Env.getStorageLocation(*E->getArg(1)));
549   transferSwap(Arg0Loc, Arg1Loc, State.Env);
550 }
551 
552 void transferStdForwardCall(const CallExpr *E, const MatchFinder::MatchResult &,
553                             LatticeTransferState &State) {
554   assert(E->getNumArgs() == 1);
555 
556   if (auto *Loc = State.Env.getStorageLocation(*E->getArg(0)))
557     State.Env.setStorageLocation(*E, *Loc);
558 }
559 
560 const Formula &evaluateEquality(Arena &A, const Formula &EqVal,
561                                 const Formula &LHS, const Formula &RHS) {
562   // Logically, an optional<T> object is composed of two values - a `has_value`
563   // bit and a value of type T. Equality of optional objects compares both
564   // values. Therefore, merely comparing the `has_value` bits isn't sufficient:
565   // when two optional objects are engaged, the equality of their respective
566   // values of type T matters. Since we only track the `has_value` bits, we
567   // can't make any conclusions about equality when we know that two optional
568   // objects are engaged.
569   //
570   // We express this as two facts about the equality:
571   // a) EqVal => (LHS & RHS) v (!RHS & !LHS)
572   //    If they are equal, then either both are set or both are unset.
573   // b) (!LHS & !RHS) => EqVal
574   //    If neither is set, then they are equal.
575   // We rewrite b) as !EqVal => (LHS v RHS), for a more compact formula.
576   return A.makeAnd(
577       A.makeImplies(EqVal, A.makeOr(A.makeAnd(LHS, RHS),
578                                     A.makeAnd(A.makeNot(LHS), A.makeNot(RHS)))),
579       A.makeImplies(A.makeNot(EqVal), A.makeOr(LHS, RHS)));
580 }
581 
582 void transferOptionalAndOptionalCmp(const clang::CXXOperatorCallExpr *CmpExpr,
583                                     const MatchFinder::MatchResult &,
584                                     LatticeTransferState &State) {
585   Environment &Env = State.Env;
586   auto &A = Env.arena();
587   auto *CmpValue = &forceBoolValue(Env, *CmpExpr);
588   auto *Arg0Loc = cast_or_null<RecordStorageLocation>(
589       Env.getStorageLocation(*CmpExpr->getArg(0)));
590   if (auto *LHasVal = getHasValue(Env, Arg0Loc)) {
591     auto *Arg1Loc = cast_or_null<RecordStorageLocation>(
592         Env.getStorageLocation(*CmpExpr->getArg(1)));
593     if (auto *RHasVal = getHasValue(Env, Arg1Loc)) {
594       if (CmpExpr->getOperator() == clang::OO_ExclaimEqual)
595         CmpValue = &A.makeNot(*CmpValue);
596       Env.assume(evaluateEquality(A, *CmpValue, LHasVal->formula(),
597                                   RHasVal->formula()));
598     }
599   }
600 }
601 
602 void transferOptionalAndValueCmp(const clang::CXXOperatorCallExpr *CmpExpr,
603                                  const clang::Expr *E, Environment &Env) {
604   auto &A = Env.arena();
605   auto *CmpValue = &forceBoolValue(Env, *CmpExpr);
606   auto *Loc = cast_or_null<RecordStorageLocation>(Env.getStorageLocation(*E));
607   if (auto *HasVal = getHasValue(Env, Loc)) {
608     if (CmpExpr->getOperator() == clang::OO_ExclaimEqual)
609       CmpValue = &A.makeNot(*CmpValue);
610     Env.assume(
611         evaluateEquality(A, *CmpValue, HasVal->formula(), A.makeLiteral(true)));
612   }
613 }
614 
615 void transferOptionalAndNulloptCmp(const clang::CXXOperatorCallExpr *CmpExpr,
616                                    const clang::Expr *E, Environment &Env) {
617   auto &A = Env.arena();
618   auto *CmpValue = &forceBoolValue(Env, *CmpExpr);
619   auto *Loc = cast_or_null<RecordStorageLocation>(Env.getStorageLocation(*E));
620   if (auto *HasVal = getHasValue(Env, Loc)) {
621     if (CmpExpr->getOperator() == clang::OO_ExclaimEqual)
622       CmpValue = &A.makeNot(*CmpValue);
623     Env.assume(evaluateEquality(A, *CmpValue, HasVal->formula(),
624                                 A.makeLiteral(false)));
625   }
626 }
627 
628 std::optional<StatementMatcher>
629 ignorableOptional(const UncheckedOptionalAccessModelOptions &Options) {
630   if (Options.IgnoreSmartPointerDereference) {
631     auto SmartPtrUse = expr(ignoringParenImpCasts(cxxOperatorCallExpr(
632         anyOf(hasOverloadedOperatorName("->"), hasOverloadedOperatorName("*")),
633         unless(hasArgument(0, expr(hasOptionalType()))))));
634     return expr(
635         anyOf(SmartPtrUse, memberExpr(hasObjectExpression(SmartPtrUse))));
636   }
637   return std::nullopt;
638 }
639 
640 StatementMatcher
641 valueCall(const std::optional<StatementMatcher> &IgnorableOptional) {
642   return isOptionalMemberCallWithNameMatcher(hasName("value"),
643                                              IgnorableOptional);
644 }
645 
646 StatementMatcher
647 valueOperatorCall(const std::optional<StatementMatcher> &IgnorableOptional) {
648   return expr(anyOf(isOptionalOperatorCallWithName("*", IgnorableOptional),
649                     isOptionalOperatorCallWithName("->", IgnorableOptional)));
650 }
651 
652 auto buildTransferMatchSwitch() {
653   // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
654   // lot of duplicated work (e.g. string comparisons), consider providing APIs
655   // that avoid it through memoization.
656   return CFGMatchSwitchBuilder<LatticeTransferState>()
657       // make_optional
658       .CaseOfCFGStmt<CallExpr>(isMakeOptionalCall(), transferMakeOptionalCall)
659 
660       // optional::optional (in place)
661       .CaseOfCFGStmt<CXXConstructExpr>(
662           isOptionalInPlaceConstructor(),
663           [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
664              LatticeTransferState &State) {
665             constructOptionalValue(*E, State.Env,
666                                    State.Env.getBoolLiteralValue(true));
667           })
668       // optional::optional(nullopt_t)
669       .CaseOfCFGStmt<CXXConstructExpr>(
670           isOptionalNulloptConstructor(),
671           [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
672              LatticeTransferState &State) {
673             constructOptionalValue(*E, State.Env,
674                                    State.Env.getBoolLiteralValue(false));
675           })
676       // optional::optional (value/conversion)
677       .CaseOfCFGStmt<CXXConstructExpr>(isOptionalValueOrConversionConstructor(),
678                                        transferValueOrConversionConstructor)
679 
680       // optional::operator=
681       .CaseOfCFGStmt<CXXOperatorCallExpr>(
682           isOptionalValueOrConversionAssignment(),
683           transferValueOrConversionAssignment)
684       .CaseOfCFGStmt<CXXOperatorCallExpr>(isOptionalNulloptAssignment(),
685                                           transferNulloptAssignment)
686 
687       // optional::value
688       .CaseOfCFGStmt<CXXMemberCallExpr>(
689           valueCall(std::nullopt),
690           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
691              LatticeTransferState &State) {
692             transferUnwrapCall(E, E->getImplicitObjectArgument(), State);
693           })
694 
695       // optional::operator*
696       .CaseOfCFGStmt<CallExpr>(isOptionalOperatorCallWithName("*"),
697                                [](const CallExpr *E,
698                                   const MatchFinder::MatchResult &,
699                                   LatticeTransferState &State) {
700                                  transferUnwrapCall(E, E->getArg(0), State);
701                                })
702 
703       // optional::operator->
704       .CaseOfCFGStmt<CallExpr>(isOptionalOperatorCallWithName("->"),
705                                [](const CallExpr *E,
706                                   const MatchFinder::MatchResult &,
707                                   LatticeTransferState &State) {
708                                  transferArrowOpCall(E, E->getArg(0), State);
709                                })
710 
711       // optional::has_value, optional::hasValue
712       // Of the supported optionals only folly::Optional uses hasValue, but this
713       // will also pass for other types
714       .CaseOfCFGStmt<CXXMemberCallExpr>(
715           isOptionalMemberCallWithNameMatcher(
716               hasAnyName("has_value", "hasValue")),
717           transferOptionalHasValueCall)
718 
719       // optional::operator bool
720       .CaseOfCFGStmt<CXXMemberCallExpr>(
721           isOptionalMemberCallWithNameMatcher(hasName("operator bool")),
722           transferOptionalHasValueCall)
723 
724       // optional::emplace
725       .CaseOfCFGStmt<CXXMemberCallExpr>(
726           isOptionalMemberCallWithNameMatcher(hasName("emplace")),
727           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
728              LatticeTransferState &State) {
729             if (RecordStorageLocation *Loc =
730                     getImplicitObjectLocation(*E, State.Env)) {
731               createOptionalValue(*Loc, State.Env.getBoolLiteralValue(true),
732                                   State.Env);
733             }
734           })
735 
736       // optional::reset
737       .CaseOfCFGStmt<CXXMemberCallExpr>(
738           isOptionalMemberCallWithNameMatcher(hasName("reset")),
739           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
740              LatticeTransferState &State) {
741             if (RecordStorageLocation *Loc =
742                     getImplicitObjectLocation(*E, State.Env)) {
743               createOptionalValue(*Loc, State.Env.getBoolLiteralValue(false),
744                                   State.Env);
745             }
746           })
747 
748       // optional::swap
749       .CaseOfCFGStmt<CXXMemberCallExpr>(
750           isOptionalMemberCallWithNameMatcher(hasName("swap")),
751           transferSwapCall)
752 
753       // std::swap
754       .CaseOfCFGStmt<CallExpr>(isStdSwapCall(), transferStdSwapCall)
755 
756       // std::forward
757       .CaseOfCFGStmt<CallExpr>(isStdForwardCall(), transferStdForwardCall)
758 
759       // opt.value_or("").empty()
760       .CaseOfCFGStmt<Expr>(isValueOrStringEmptyCall(),
761                            transferValueOrStringEmptyCall)
762 
763       // opt.value_or(X) != X
764       .CaseOfCFGStmt<Expr>(isValueOrNotEqX(), transferValueOrNotEqX)
765 
766       // Comparisons (==, !=):
767       .CaseOfCFGStmt<CXXOperatorCallExpr>(
768           isComparisonOperatorCall(hasOptionalType(), hasOptionalType()),
769           transferOptionalAndOptionalCmp)
770       .CaseOfCFGStmt<CXXOperatorCallExpr>(
771           isComparisonOperatorCall(hasOptionalType(), hasNulloptType()),
772           [](const clang::CXXOperatorCallExpr *Cmp,
773              const MatchFinder::MatchResult &, LatticeTransferState &State) {
774             transferOptionalAndNulloptCmp(Cmp, Cmp->getArg(0), State.Env);
775           })
776       .CaseOfCFGStmt<CXXOperatorCallExpr>(
777           isComparisonOperatorCall(hasNulloptType(), hasOptionalType()),
778           [](const clang::CXXOperatorCallExpr *Cmp,
779              const MatchFinder::MatchResult &, LatticeTransferState &State) {
780             transferOptionalAndNulloptCmp(Cmp, Cmp->getArg(1), State.Env);
781           })
782       .CaseOfCFGStmt<CXXOperatorCallExpr>(
783           isComparisonOperatorCall(
784               hasOptionalType(),
785               unless(anyOf(hasOptionalType(), hasNulloptType()))),
786           [](const clang::CXXOperatorCallExpr *Cmp,
787              const MatchFinder::MatchResult &, LatticeTransferState &State) {
788             transferOptionalAndValueCmp(Cmp, Cmp->getArg(0), State.Env);
789           })
790       .CaseOfCFGStmt<CXXOperatorCallExpr>(
791           isComparisonOperatorCall(
792               unless(anyOf(hasOptionalType(), hasNulloptType())),
793               hasOptionalType()),
794           [](const clang::CXXOperatorCallExpr *Cmp,
795              const MatchFinder::MatchResult &, LatticeTransferState &State) {
796             transferOptionalAndValueCmp(Cmp, Cmp->getArg(1), State.Env);
797           })
798 
799       // returns optional
800       .CaseOfCFGStmt<CallExpr>(isCallReturningOptional(),
801                                transferCallReturningOptional)
802 
803       .Build();
804 }
805 
806 llvm::SmallVector<SourceLocation> diagnoseUnwrapCall(const Expr *ObjectExpr,
807                                                      const Environment &Env) {
808   if (auto *OptionalLoc = cast_or_null<RecordStorageLocation>(
809           getLocBehindPossiblePointer(*ObjectExpr, Env))) {
810     auto *Prop = Env.getValue(locForHasValue(*OptionalLoc));
811     if (auto *HasValueVal = cast_or_null<BoolValue>(Prop)) {
812       if (Env.proves(HasValueVal->formula()))
813         return {};
814     }
815   }
816 
817   // Record that this unwrap is *not* provably safe.
818   // FIXME: include either the name of the optional (if applicable) or a source
819   // range of the access for easier interpretation of the result.
820   return {ObjectExpr->getBeginLoc()};
821 }
822 
823 auto buildDiagnoseMatchSwitch(
824     const UncheckedOptionalAccessModelOptions &Options) {
825   // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
826   // lot of duplicated work (e.g. string comparisons), consider providing APIs
827   // that avoid it through memoization.
828   auto IgnorableOptional = ignorableOptional(Options);
829   return CFGMatchSwitchBuilder<const Environment,
830                                llvm::SmallVector<SourceLocation>>()
831       // optional::value
832       .CaseOfCFGStmt<CXXMemberCallExpr>(
833           valueCall(IgnorableOptional),
834           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
835              const Environment &Env) {
836             return diagnoseUnwrapCall(E->getImplicitObjectArgument(), Env);
837           })
838 
839       // optional::operator*, optional::operator->
840       .CaseOfCFGStmt<CallExpr>(valueOperatorCall(IgnorableOptional),
841                                [](const CallExpr *E,
842                                   const MatchFinder::MatchResult &,
843                                   const Environment &Env) {
844                                  return diagnoseUnwrapCall(E->getArg(0), Env);
845                                })
846       .Build();
847 }
848 
849 } // namespace
850 
851 ast_matchers::DeclarationMatcher
852 UncheckedOptionalAccessModel::optionalClassDecl() {
853   return optionalClass();
854 }
855 
856 static QualType valueTypeFromOptionalType(QualType OptionalTy) {
857   auto *CTSD =
858       cast<ClassTemplateSpecializationDecl>(OptionalTy->getAsCXXRecordDecl());
859   return CTSD->getTemplateArgs()[0].getAsType();
860 }
861 
862 UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(ASTContext &Ctx,
863                                                            Environment &Env)
864     : DataflowAnalysis<UncheckedOptionalAccessModel, NoopLattice>(Ctx),
865       TransferMatchSwitch(buildTransferMatchSwitch()) {
866   Env.getDataflowAnalysisContext().setSyntheticFieldCallback(
867       [&Ctx](QualType Ty) -> llvm::StringMap<QualType> {
868         if (!isOptionalType(Ty))
869           return {};
870         return {{"value", valueTypeFromOptionalType(Ty)},
871                 {"has_value", Ctx.BoolTy}};
872       });
873 }
874 
875 void UncheckedOptionalAccessModel::transfer(const CFGElement &Elt,
876                                             NoopLattice &L, Environment &Env) {
877   LatticeTransferState State(L, Env);
878   TransferMatchSwitch(Elt, getASTContext(), State);
879 }
880 
881 UncheckedOptionalAccessDiagnoser::UncheckedOptionalAccessDiagnoser(
882     UncheckedOptionalAccessModelOptions Options)
883     : DiagnoseMatchSwitch(buildDiagnoseMatchSwitch(Options)) {}
884 
885 } // namespace dataflow
886 } // namespace clang
887