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