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/Analysis/FlowSensitive/DataflowEnvironment.h"
22 #include "clang/Analysis/FlowSensitive/MatchSwitch.h"
23 #include "clang/Analysis/FlowSensitive/SourceLocationsLattice.h"
24 #include "clang/Analysis/FlowSensitive/Value.h"
25 #include "clang/Basic/SourceLocation.h"
26 #include "llvm/ADT/StringRef.h"
27 #include "llvm/Support/Casting.h"
28 #include <cassert>
29 #include <memory>
30 #include <utility>
31 #include <vector>
32 
33 namespace clang {
34 namespace dataflow {
35 namespace {
36 
37 using namespace ::clang::ast_matchers;
38 using LatticeTransferState = TransferState<SourceLocationsLattice>;
39 
40 DeclarationMatcher optionalClass() {
41   return classTemplateSpecializationDecl(
42       anyOf(hasName("std::optional"), hasName("std::__optional_storage_base"),
43             hasName("__optional_destruct_base"), hasName("absl::optional"),
44             hasName("base::Optional")),
45       hasTemplateArgument(0, refersToType(type().bind("T"))));
46 }
47 
48 auto optionalOrAliasType() {
49   return hasUnqualifiedDesugaredType(
50       recordType(hasDeclaration(optionalClass())));
51 }
52 
53 /// Matches any of the spellings of the optional types and sugar, aliases, etc.
54 auto hasOptionalType() { return hasType(optionalOrAliasType()); }
55 
56 auto isOptionalMemberCallWithName(
57     llvm::StringRef MemberName,
58     llvm::Optional<StatementMatcher> Ignorable = llvm::None) {
59   auto Exception = unless(Ignorable ? expr(anyOf(*Ignorable, cxxThisExpr()))
60                                     : cxxThisExpr());
61   return cxxMemberCallExpr(
62       on(expr(Exception)),
63       callee(cxxMethodDecl(hasName(MemberName), ofClass(optionalClass()))));
64 }
65 
66 auto isOptionalOperatorCallWithName(
67     llvm::StringRef operator_name,
68     llvm::Optional<StatementMatcher> Ignorable = llvm::None) {
69   return cxxOperatorCallExpr(
70       hasOverloadedOperatorName(operator_name),
71       callee(cxxMethodDecl(ofClass(optionalClass()))),
72       Ignorable ? callExpr(unless(hasArgument(0, *Ignorable))) : callExpr());
73 }
74 
75 auto isMakeOptionalCall() {
76   return callExpr(
77       callee(functionDecl(hasAnyName(
78           "std::make_optional", "base::make_optional", "absl::make_optional"))),
79       hasOptionalType());
80 }
81 
82 auto hasNulloptType() {
83   return hasType(namedDecl(
84       hasAnyName("std::nullopt_t", "absl::nullopt_t", "base::nullopt_t")));
85 }
86 
87 auto inPlaceClass() {
88   return recordDecl(
89       hasAnyName("std::in_place_t", "absl::in_place_t", "base::in_place_t"));
90 }
91 
92 auto isOptionalNulloptConstructor() {
93   return cxxConstructExpr(hasOptionalType(), argumentCountIs(1),
94                           hasArgument(0, hasNulloptType()));
95 }
96 
97 auto isOptionalInPlaceConstructor() {
98   return cxxConstructExpr(hasOptionalType(),
99                           hasArgument(0, hasType(inPlaceClass())));
100 }
101 
102 auto isOptionalValueOrConversionConstructor() {
103   return cxxConstructExpr(
104       hasOptionalType(),
105       unless(hasDeclaration(
106           cxxConstructorDecl(anyOf(isCopyConstructor(), isMoveConstructor())))),
107       argumentCountIs(1), hasArgument(0, unless(hasNulloptType())));
108 }
109 
110 auto isOptionalValueOrConversionAssignment() {
111   return cxxOperatorCallExpr(
112       hasOverloadedOperatorName("="),
113       callee(cxxMethodDecl(ofClass(optionalClass()))),
114       unless(hasDeclaration(cxxMethodDecl(
115           anyOf(isCopyAssignmentOperator(), isMoveAssignmentOperator())))),
116       argumentCountIs(2), hasArgument(1, unless(hasNulloptType())));
117 }
118 
119 auto isOptionalNulloptAssignment() {
120   return cxxOperatorCallExpr(hasOverloadedOperatorName("="),
121                              callee(cxxMethodDecl(ofClass(optionalClass()))),
122                              argumentCountIs(2),
123                              hasArgument(1, hasNulloptType()));
124 }
125 
126 auto isStdSwapCall() {
127   return callExpr(callee(functionDecl(hasName("std::swap"))),
128                   argumentCountIs(2), hasArgument(0, hasOptionalType()),
129                   hasArgument(1, hasOptionalType()));
130 }
131 
132 constexpr llvm::StringLiteral ValueOrCallID = "ValueOrCall";
133 
134 auto isValueOrStringEmptyCall() {
135   // `opt.value_or("").empty()`
136   return cxxMemberCallExpr(
137       callee(cxxMethodDecl(hasName("empty"))),
138       onImplicitObjectArgument(ignoringImplicit(
139           cxxMemberCallExpr(on(expr(unless(cxxThisExpr()))),
140                             callee(cxxMethodDecl(hasName("value_or"),
141                                                  ofClass(optionalClass()))),
142                             hasArgument(0, stringLiteral(hasSize(0))))
143               .bind(ValueOrCallID))));
144 }
145 
146 auto isValueOrNotEqX() {
147   auto ComparesToSame = [](ast_matchers::internal::Matcher<Stmt> Arg) {
148     return hasOperands(
149         ignoringImplicit(
150             cxxMemberCallExpr(on(expr(unless(cxxThisExpr()))),
151                               callee(cxxMethodDecl(hasName("value_or"),
152                                                    ofClass(optionalClass()))),
153                               hasArgument(0, Arg))
154                 .bind(ValueOrCallID)),
155         ignoringImplicit(Arg));
156   };
157 
158   // `opt.value_or(X) != X`, for X is `nullptr`, `""`, or `0`. Ideally, we'd
159   // support this pattern for any expression, but the AST does not have a
160   // generic expression comparison facility, so we specialize to common cases
161   // seen in practice.  FIXME: define a matcher that compares values across
162   // nodes, which would let us generalize this to any `X`.
163   return binaryOperation(hasOperatorName("!="),
164                          anyOf(ComparesToSame(cxxNullPtrLiteralExpr()),
165                                ComparesToSame(stringLiteral(hasSize(0))),
166                                ComparesToSame(integerLiteral(equals(0)))));
167 }
168 
169 auto isCallReturningOptional() {
170   return callExpr(hasType(qualType(anyOf(
171       optionalOrAliasType(), referenceType(pointee(optionalOrAliasType()))))));
172 }
173 
174 /// Sets `HasValueVal` as the symbolic value that represents the "has_value"
175 /// property of the optional value `OptionalVal`.
176 void setHasValue(Value &OptionalVal, BoolValue &HasValueVal) {
177   OptionalVal.setProperty("has_value", HasValueVal);
178 }
179 
180 /// Creates a symbolic value for an `optional` value using `HasValueVal` as the
181 /// symbolic value of its "has_value" property.
182 StructValue &createOptionalValue(Environment &Env, BoolValue &HasValueVal) {
183   auto OptionalVal = std::make_unique<StructValue>();
184   setHasValue(*OptionalVal, HasValueVal);
185   return Env.takeOwnership(std::move(OptionalVal));
186 }
187 
188 /// Returns the symbolic value that represents the "has_value" property of the
189 /// optional value `OptionalVal`. Returns null if `OptionalVal` is null.
190 BoolValue *getHasValue(Environment &Env, Value *OptionalVal) {
191   if (OptionalVal != nullptr) {
192     auto *HasValueVal =
193         cast_or_null<BoolValue>(OptionalVal->getProperty("has_value"));
194     if (HasValueVal == nullptr) {
195       HasValueVal = &Env.makeAtomicBoolValue();
196       OptionalVal->setProperty("has_value", *HasValueVal);
197     }
198     return HasValueVal;
199   }
200   return nullptr;
201 }
202 
203 /// If `Type` is a reference type, returns the type of its pointee. Otherwise,
204 /// returns `Type` itself.
205 QualType stripReference(QualType Type) {
206   return Type->isReferenceType() ? Type->getPointeeType() : Type;
207 }
208 
209 /// Returns true if and only if `Type` is an optional type.
210 bool IsOptionalType(QualType Type) {
211   if (!Type->isRecordType())
212     return false;
213   // FIXME: Optimize this by avoiding the `getQualifiedNameAsString` call.
214   auto TypeName = Type->getAsCXXRecordDecl()->getQualifiedNameAsString();
215   return TypeName == "std::optional" || TypeName == "absl::optional" ||
216          TypeName == "base::Optional";
217 }
218 
219 /// Returns the number of optional wrappers in `Type`.
220 ///
221 /// For example, if `Type` is `optional<optional<int>>`, the result of this
222 /// function will be 2.
223 int countOptionalWrappers(const ASTContext &ASTCtx, QualType Type) {
224   if (!IsOptionalType(Type))
225     return 0;
226   return 1 + countOptionalWrappers(
227                  ASTCtx,
228                  cast<ClassTemplateSpecializationDecl>(Type->getAsRecordDecl())
229                      ->getTemplateArgs()
230                      .get(0)
231                      .getAsType()
232                      .getDesugaredType(ASTCtx));
233 }
234 
235 /// Tries to initialize the `optional`'s value (that is, contents), and return
236 /// its location. Returns nullptr if the value can't be represented.
237 StorageLocation *maybeInitializeOptionalValueMember(QualType Q,
238                                                     Value &OptionalVal,
239                                                     Environment &Env) {
240   // The "value" property represents a synthetic field. As such, it needs
241   // `StorageLocation`, like normal fields (and other variables). So, we model
242   // it with a `ReferenceValue`, since that includes a storage location.  Once
243   // the property is set, it will be shared by all environments that access the
244   // `Value` representing the optional (here, `OptionalVal`).
245   if (auto *ValueProp = OptionalVal.getProperty("value")) {
246     auto *ValueRef = clang::cast<ReferenceValue>(ValueProp);
247     auto &ValueLoc = ValueRef->getReferentLoc();
248     if (Env.getValue(ValueLoc) == nullptr) {
249       // The property was previously set, but the value has been lost. This can
250       // happen, for example, because of an environment merge (where the two
251       // environments mapped the property to different values, which resulted in
252       // them both being discarded), or when two blocks in the CFG, with neither
253       // a dominator of the other, visit the same optional value, or even when a
254       // block is revisited during testing to collect per-statement state.
255       // FIXME: This situation means that the optional contents are not shared
256       // between branches and the like. Practically, this lack of sharing
257       // reduces the precision of the model when the contents are relevant to
258       // the check, like another optional or a boolean that influences control
259       // flow.
260       auto *ValueVal = Env.createValue(ValueLoc.getType());
261       if (ValueVal == nullptr)
262         return nullptr;
263       Env.setValue(ValueLoc, *ValueVal);
264     }
265     return &ValueLoc;
266   }
267 
268   auto Ty = stripReference(Q);
269   auto *ValueVal = Env.createValue(Ty);
270   if (ValueVal == nullptr)
271     return nullptr;
272   auto &ValueLoc = Env.createStorageLocation(Ty);
273   Env.setValue(ValueLoc, *ValueVal);
274   auto ValueRef = std::make_unique<ReferenceValue>(ValueLoc);
275   OptionalVal.setProperty("value", Env.takeOwnership(std::move(ValueRef)));
276   return &ValueLoc;
277 }
278 
279 void initializeOptionalReference(const Expr *OptionalExpr,
280                                  const MatchFinder::MatchResult &,
281                                  LatticeTransferState &State) {
282   if (auto *OptionalVal =
283           State.Env.getValue(*OptionalExpr, SkipPast::Reference)) {
284     if (OptionalVal->getProperty("has_value") == nullptr) {
285       setHasValue(*OptionalVal, State.Env.makeAtomicBoolValue());
286     }
287   }
288 }
289 
290 /// Returns true if and only if `OptionalVal` is initialized and known to be
291 /// empty in `Env.
292 bool isEmptyOptional(const Value &OptionalVal, const Environment &Env) {
293   auto *HasValueVal =
294       cast_or_null<BoolValue>(OptionalVal.getProperty("has_value"));
295   return HasValueVal != nullptr &&
296          Env.flowConditionImplies(Env.makeNot(*HasValueVal));
297 }
298 
299 /// Returns true if and only if `OptionalVal` is initialized and known to be
300 /// non-empty in `Env.
301 bool isNonEmptyOptional(const Value &OptionalVal, const Environment &Env) {
302   auto *HasValueVal =
303       cast_or_null<BoolValue>(OptionalVal.getProperty("has_value"));
304   return HasValueVal != nullptr && Env.flowConditionImplies(*HasValueVal);
305 }
306 
307 void transferUnwrapCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
308                         LatticeTransferState &State) {
309   if (auto *OptionalVal =
310           State.Env.getValue(*ObjectExpr, SkipPast::ReferenceThenPointer)) {
311     if (State.Env.getStorageLocation(*UnwrapExpr, SkipPast::None) == nullptr)
312       if (auto *Loc = maybeInitializeOptionalValueMember(
313               UnwrapExpr->getType(), *OptionalVal, State.Env))
314         State.Env.setStorageLocation(*UnwrapExpr, *Loc);
315 
316     auto *Prop = OptionalVal->getProperty("has_value");
317     if (auto *HasValueVal = cast_or_null<BoolValue>(Prop)) {
318       if (State.Env.flowConditionImplies(*HasValueVal))
319         return;
320     }
321   }
322 
323   // Record that this unwrap is *not* provably safe.
324   // FIXME: include either the name of the optional (if applicable) or a source
325   // range of the access for easier interpretation of the result.
326   State.Lattice.getSourceLocations().insert(ObjectExpr->getBeginLoc());
327 }
328 
329 void transferMakeOptionalCall(const CallExpr *E,
330                               const MatchFinder::MatchResult &,
331                               LatticeTransferState &State) {
332   auto &Loc = State.Env.createStorageLocation(*E);
333   State.Env.setStorageLocation(*E, Loc);
334   State.Env.setValue(
335       Loc, createOptionalValue(State.Env, State.Env.getBoolLiteralValue(true)));
336 }
337 
338 void transferOptionalHasValueCall(const CXXMemberCallExpr *CallExpr,
339                                   const MatchFinder::MatchResult &,
340                                   LatticeTransferState &State) {
341   if (auto *HasValueVal = getHasValue(
342           State.Env, State.Env.getValue(*CallExpr->getImplicitObjectArgument(),
343                                         SkipPast::ReferenceThenPointer))) {
344     auto &CallExprLoc = State.Env.createStorageLocation(*CallExpr);
345     State.Env.setValue(CallExprLoc, *HasValueVal);
346     State.Env.setStorageLocation(*CallExpr, CallExprLoc);
347   }
348 }
349 
350 /// `ModelPred` builds a logical formula relating the predicate in
351 /// `ValueOrPredExpr` to the optional's `has_value` property.
352 void transferValueOrImpl(const clang::Expr *ValueOrPredExpr,
353                          const MatchFinder::MatchResult &Result,
354                          LatticeTransferState &State,
355                          BoolValue &(*ModelPred)(Environment &Env,
356                                                  BoolValue &ExprVal,
357                                                  BoolValue &HasValueVal)) {
358   auto &Env = State.Env;
359 
360   const auto *ObjectArgumentExpr =
361       Result.Nodes.getNodeAs<clang::CXXMemberCallExpr>(ValueOrCallID)
362           ->getImplicitObjectArgument();
363 
364   auto *HasValueVal = getHasValue(
365       State.Env,
366       State.Env.getValue(*ObjectArgumentExpr, SkipPast::ReferenceThenPointer));
367   if (HasValueVal == nullptr)
368     return;
369 
370   auto *ExprValue = cast_or_null<BoolValue>(
371       State.Env.getValue(*ValueOrPredExpr, SkipPast::None));
372   if (ExprValue == nullptr) {
373     auto &ExprLoc = State.Env.createStorageLocation(*ValueOrPredExpr);
374     ExprValue = &State.Env.makeAtomicBoolValue();
375     State.Env.setValue(ExprLoc, *ExprValue);
376     State.Env.setStorageLocation(*ValueOrPredExpr, ExprLoc);
377   }
378 
379   Env.addToFlowCondition(ModelPred(Env, *ExprValue, *HasValueVal));
380 }
381 
382 void transferValueOrStringEmptyCall(const clang::Expr *ComparisonExpr,
383                                     const MatchFinder::MatchResult &Result,
384                                     LatticeTransferState &State) {
385   return transferValueOrImpl(ComparisonExpr, Result, State,
386                              [](Environment &Env, BoolValue &ExprVal,
387                                 BoolValue &HasValueVal) -> BoolValue & {
388                                // If the result is *not* empty, then we know the
389                                // optional must have been holding a value. If
390                                // `ExprVal` is true, though, we don't learn
391                                // anything definite about `has_value`, so we
392                                // don't add any corresponding implications to
393                                // the flow condition.
394                                return Env.makeImplication(Env.makeNot(ExprVal),
395                                                           HasValueVal);
396                              });
397 }
398 
399 void transferValueOrNotEqX(const Expr *ComparisonExpr,
400                            const MatchFinder::MatchResult &Result,
401                            LatticeTransferState &State) {
402   transferValueOrImpl(ComparisonExpr, Result, State,
403                       [](Environment &Env, BoolValue &ExprVal,
404                          BoolValue &HasValueVal) -> BoolValue & {
405                         // We know that if `(opt.value_or(X) != X)` then
406                         // `opt.hasValue()`, even without knowing further
407                         // details about the contents of `opt`.
408                         return Env.makeImplication(ExprVal, HasValueVal);
409                       });
410 }
411 
412 void transferCallReturningOptional(const CallExpr *E,
413                                    const MatchFinder::MatchResult &Result,
414                                    LatticeTransferState &State) {
415   if (State.Env.getStorageLocation(*E, SkipPast::None) != nullptr)
416     return;
417 
418   auto &Loc = State.Env.createStorageLocation(*E);
419   State.Env.setStorageLocation(*E, Loc);
420   State.Env.setValue(
421       Loc, createOptionalValue(State.Env, State.Env.makeAtomicBoolValue()));
422 }
423 
424 void assignOptionalValue(const Expr &E, LatticeTransferState &State,
425                          BoolValue &HasValueVal) {
426   if (auto *OptionalLoc =
427           State.Env.getStorageLocation(E, SkipPast::ReferenceThenPointer)) {
428     State.Env.setValue(*OptionalLoc,
429                        createOptionalValue(State.Env, HasValueVal));
430   }
431 }
432 
433 /// Returns a symbolic value for the "has_value" property of an `optional<T>`
434 /// value that is constructed/assigned from a value of type `U` or `optional<U>`
435 /// where `T` is constructible from `U`.
436 BoolValue &value_orConversionHasValue(const FunctionDecl &F, const Expr &E,
437                                       const MatchFinder::MatchResult &MatchRes,
438                                       LatticeTransferState &State) {
439   assert(F.getTemplateSpecializationArgs()->size() > 0);
440 
441   const int TemplateParamOptionalWrappersCount = countOptionalWrappers(
442       *MatchRes.Context,
443       stripReference(F.getTemplateSpecializationArgs()->get(0).getAsType()));
444   const int ArgTypeOptionalWrappersCount =
445       countOptionalWrappers(*MatchRes.Context, stripReference(E.getType()));
446 
447   // Check if this is a constructor/assignment call for `optional<T>` with
448   // argument of type `U` such that `T` is constructible from `U`.
449   if (TemplateParamOptionalWrappersCount == ArgTypeOptionalWrappersCount)
450     return State.Env.getBoolLiteralValue(true);
451 
452   // This is a constructor/assignment call for `optional<T>` with argument of
453   // type `optional<U>` such that `T` is constructible from `U`.
454   if (auto *HasValueVal =
455           getHasValue(State.Env, State.Env.getValue(E, SkipPast::Reference)))
456     return *HasValueVal;
457   return State.Env.makeAtomicBoolValue();
458 }
459 
460 void transferValueOrConversionConstructor(
461     const CXXConstructExpr *E, const MatchFinder::MatchResult &MatchRes,
462     LatticeTransferState &State) {
463   assert(E->getNumArgs() > 0);
464 
465   assignOptionalValue(*E, State,
466                       value_orConversionHasValue(*E->getConstructor(),
467                                                  *E->getArg(0), MatchRes,
468                                                  State));
469 }
470 
471 void transferAssignment(const CXXOperatorCallExpr *E, BoolValue &HasValueVal,
472                         LatticeTransferState &State) {
473   assert(E->getNumArgs() > 0);
474 
475   auto *OptionalLoc =
476       State.Env.getStorageLocation(*E->getArg(0), SkipPast::Reference);
477   if (OptionalLoc == nullptr)
478     return;
479 
480   State.Env.setValue(*OptionalLoc, createOptionalValue(State.Env, HasValueVal));
481 
482   // Assign a storage location for the whole expression.
483   State.Env.setStorageLocation(*E, *OptionalLoc);
484 }
485 
486 void transferValueOrConversionAssignment(
487     const CXXOperatorCallExpr *E, const MatchFinder::MatchResult &MatchRes,
488     LatticeTransferState &State) {
489   assert(E->getNumArgs() > 1);
490   transferAssignment(E,
491                      value_orConversionHasValue(*E->getDirectCallee(),
492                                                 *E->getArg(1), MatchRes, State),
493                      State);
494 }
495 
496 void transferNulloptAssignment(const CXXOperatorCallExpr *E,
497                                const MatchFinder::MatchResult &,
498                                LatticeTransferState &State) {
499   transferAssignment(E, State.Env.getBoolLiteralValue(false), State);
500 }
501 
502 void transferSwap(const StorageLocation &OptionalLoc1,
503                   const StorageLocation &OptionalLoc2,
504                   LatticeTransferState &State) {
505   auto *OptionalVal1 = State.Env.getValue(OptionalLoc1);
506   assert(OptionalVal1 != nullptr);
507 
508   auto *OptionalVal2 = State.Env.getValue(OptionalLoc2);
509   assert(OptionalVal2 != nullptr);
510 
511   State.Env.setValue(OptionalLoc1, *OptionalVal2);
512   State.Env.setValue(OptionalLoc2, *OptionalVal1);
513 }
514 
515 void transferSwapCall(const CXXMemberCallExpr *E,
516                       const MatchFinder::MatchResult &,
517                       LatticeTransferState &State) {
518   assert(E->getNumArgs() == 1);
519 
520   auto *OptionalLoc1 = State.Env.getStorageLocation(
521       *E->getImplicitObjectArgument(), SkipPast::ReferenceThenPointer);
522   assert(OptionalLoc1 != nullptr);
523 
524   auto *OptionalLoc2 =
525       State.Env.getStorageLocation(*E->getArg(0), SkipPast::Reference);
526   assert(OptionalLoc2 != nullptr);
527 
528   transferSwap(*OptionalLoc1, *OptionalLoc2, State);
529 }
530 
531 void transferStdSwapCall(const CallExpr *E, const MatchFinder::MatchResult &,
532                          LatticeTransferState &State) {
533   assert(E->getNumArgs() == 2);
534 
535   auto *OptionalLoc1 =
536       State.Env.getStorageLocation(*E->getArg(0), SkipPast::Reference);
537   assert(OptionalLoc1 != nullptr);
538 
539   auto *OptionalLoc2 =
540       State.Env.getStorageLocation(*E->getArg(1), SkipPast::Reference);
541   assert(OptionalLoc2 != nullptr);
542 
543   transferSwap(*OptionalLoc1, *OptionalLoc2, State);
544 }
545 
546 llvm::Optional<StatementMatcher>
547 ignorableOptional(const UncheckedOptionalAccessModelOptions &Options) {
548   if (Options.IgnoreSmartPointerDereference)
549     return memberExpr(hasObjectExpression(ignoringParenImpCasts(
550         cxxOperatorCallExpr(anyOf(hasOverloadedOperatorName("->"),
551                                   hasOverloadedOperatorName("*")),
552                             unless(hasArgument(0, expr(hasOptionalType())))))));
553   return llvm::None;
554 }
555 
556 StatementMatcher
557 valueCall(llvm::Optional<StatementMatcher> &IgnorableOptional) {
558   return isOptionalMemberCallWithName("value", IgnorableOptional);
559 }
560 
561 StatementMatcher
562 valueOperatorCall(llvm::Optional<StatementMatcher> &IgnorableOptional) {
563   return expr(anyOf(isOptionalOperatorCallWithName("*", IgnorableOptional),
564                     isOptionalOperatorCallWithName("->", IgnorableOptional)));
565 }
566 
567 auto buildTransferMatchSwitch(
568     const UncheckedOptionalAccessModelOptions &Options) {
569   // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
570   // lot of duplicated work (e.g. string comparisons), consider providing APIs
571   // that avoid it through memoization.
572   auto IgnorableOptional = ignorableOptional(Options);
573   return MatchSwitchBuilder<LatticeTransferState>()
574       // Attach a symbolic "has_value" state to optional values that we see for
575       // the first time.
576       .CaseOf<Expr>(
577           expr(anyOf(declRefExpr(), memberExpr()), hasOptionalType()),
578           initializeOptionalReference)
579 
580       // make_optional
581       .CaseOf<CallExpr>(isMakeOptionalCall(), transferMakeOptionalCall)
582 
583       // optional::optional
584       .CaseOf<CXXConstructExpr>(
585           isOptionalInPlaceConstructor(),
586           [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
587              LatticeTransferState &State) {
588             assignOptionalValue(*E, State, State.Env.getBoolLiteralValue(true));
589           })
590       .CaseOf<CXXConstructExpr>(
591           isOptionalNulloptConstructor(),
592           [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
593              LatticeTransferState &State) {
594             assignOptionalValue(*E, State,
595                                 State.Env.getBoolLiteralValue(false));
596           })
597       .CaseOf<CXXConstructExpr>(isOptionalValueOrConversionConstructor(),
598                                 transferValueOrConversionConstructor)
599 
600       // optional::operator=
601       .CaseOf<CXXOperatorCallExpr>(isOptionalValueOrConversionAssignment(),
602                                    transferValueOrConversionAssignment)
603       .CaseOf<CXXOperatorCallExpr>(isOptionalNulloptAssignment(),
604                                    transferNulloptAssignment)
605 
606       // optional::value
607       .CaseOf<CXXMemberCallExpr>(
608           valueCall(IgnorableOptional),
609           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
610              LatticeTransferState &State) {
611             transferUnwrapCall(E, E->getImplicitObjectArgument(), State);
612           })
613 
614       // optional::operator*, optional::operator->
615       .CaseOf<CallExpr>(valueOperatorCall(IgnorableOptional),
616                         [](const CallExpr *E, const MatchFinder::MatchResult &,
617                            LatticeTransferState &State) {
618                           transferUnwrapCall(E, E->getArg(0), State);
619                         })
620 
621       // optional::has_value
622       .CaseOf<CXXMemberCallExpr>(isOptionalMemberCallWithName("has_value"),
623                                  transferOptionalHasValueCall)
624 
625       // optional::operator bool
626       .CaseOf<CXXMemberCallExpr>(isOptionalMemberCallWithName("operator bool"),
627                                  transferOptionalHasValueCall)
628 
629       // optional::emplace
630       .CaseOf<CXXMemberCallExpr>(
631           isOptionalMemberCallWithName("emplace"),
632           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
633              LatticeTransferState &State) {
634             assignOptionalValue(*E->getImplicitObjectArgument(), State,
635                                 State.Env.getBoolLiteralValue(true));
636           })
637 
638       // optional::reset
639       .CaseOf<CXXMemberCallExpr>(
640           isOptionalMemberCallWithName("reset"),
641           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
642              LatticeTransferState &State) {
643             assignOptionalValue(*E->getImplicitObjectArgument(), State,
644                                 State.Env.getBoolLiteralValue(false));
645           })
646 
647       // optional::swap
648       .CaseOf<CXXMemberCallExpr>(isOptionalMemberCallWithName("swap"),
649                                  transferSwapCall)
650 
651       // std::swap
652       .CaseOf<CallExpr>(isStdSwapCall(), transferStdSwapCall)
653 
654       // opt.value_or("").empty()
655       .CaseOf<Expr>(isValueOrStringEmptyCall(), transferValueOrStringEmptyCall)
656 
657       // opt.value_or(X) != X
658       .CaseOf<Expr>(isValueOrNotEqX(), transferValueOrNotEqX)
659 
660       // returns optional
661       .CaseOf<CallExpr>(isCallReturningOptional(),
662                         transferCallReturningOptional)
663 
664       .Build();
665 }
666 
667 std::vector<SourceLocation> diagnoseUnwrapCall(const Expr *UnwrapExpr,
668                                                const Expr *ObjectExpr,
669                                                const Environment &Env) {
670   if (auto *OptionalVal =
671           Env.getValue(*ObjectExpr, SkipPast::ReferenceThenPointer)) {
672     auto *Prop = OptionalVal->getProperty("has_value");
673     if (auto *HasValueVal = cast_or_null<BoolValue>(Prop)) {
674       if (Env.flowConditionImplies(*HasValueVal))
675         return {};
676     }
677   }
678 
679   // Record that this unwrap is *not* provably safe.
680   // FIXME: include either the name of the optional (if applicable) or a source
681   // range of the access for easier interpretation of the result.
682   return {ObjectExpr->getBeginLoc()};
683 }
684 
685 auto buildDiagnoseMatchSwitch(
686     const UncheckedOptionalAccessModelOptions &Options) {
687   // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
688   // lot of duplicated work (e.g. string comparisons), consider providing APIs
689   // that avoid it through memoization.
690   auto IgnorableOptional = ignorableOptional(Options);
691   return MatchSwitchBuilder<const Environment, std::vector<SourceLocation>>()
692       // optional::value
693       .CaseOf<CXXMemberCallExpr>(
694           valueCall(IgnorableOptional),
695           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
696              const Environment &Env) {
697             return diagnoseUnwrapCall(E, E->getImplicitObjectArgument(), Env);
698           })
699 
700       // optional::operator*, optional::operator->
701       .CaseOf<CallExpr>(
702           valueOperatorCall(IgnorableOptional),
703           [](const CallExpr *E, const MatchFinder::MatchResult &,
704              const Environment &Env) {
705             return diagnoseUnwrapCall(E, E->getArg(0), Env);
706           })
707       .Build();
708 }
709 
710 } // namespace
711 
712 ast_matchers::DeclarationMatcher
713 UncheckedOptionalAccessModel::optionalClassDecl() {
714   return optionalClass();
715 }
716 
717 UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(
718     ASTContext &Ctx, UncheckedOptionalAccessModelOptions Options)
719     : DataflowAnalysis<UncheckedOptionalAccessModel, SourceLocationsLattice>(
720           Ctx),
721       TransferMatchSwitch(buildTransferMatchSwitch(Options)) {}
722 
723 void UncheckedOptionalAccessModel::transfer(const Stmt *S,
724                                             SourceLocationsLattice &L,
725                                             Environment &Env) {
726   LatticeTransferState State(L, Env);
727   TransferMatchSwitch(*S, getASTContext(), State);
728 }
729 
730 bool UncheckedOptionalAccessModel::compareEquivalent(QualType Type,
731                                                      const Value &Val1,
732                                                      const Environment &Env1,
733                                                      const Value &Val2,
734                                                      const Environment &Env2) {
735   return isNonEmptyOptional(Val1, Env1) == isNonEmptyOptional(Val2, Env2);
736 }
737 
738 bool UncheckedOptionalAccessModel::merge(QualType Type, const Value &Val1,
739                                          const Environment &Env1,
740                                          const Value &Val2,
741                                          const Environment &Env2,
742                                          Value &MergedVal,
743                                          Environment &MergedEnv) {
744   if (!IsOptionalType(Type))
745     return true;
746 
747   auto &HasValueVal = MergedEnv.makeAtomicBoolValue();
748   if (isNonEmptyOptional(Val1, Env1) && isNonEmptyOptional(Val2, Env2))
749     MergedEnv.addToFlowCondition(HasValueVal);
750   else if (isEmptyOptional(Val1, Env1) && isEmptyOptional(Val2, Env2))
751     MergedEnv.addToFlowCondition(MergedEnv.makeNot(HasValueVal));
752   setHasValue(MergedVal, HasValueVal);
753   return true;
754 }
755 
756 UncheckedOptionalAccessDiagnoser::UncheckedOptionalAccessDiagnoser(
757     UncheckedOptionalAccessModelOptions Options)
758     : DiagnoseMatchSwitch(buildDiagnoseMatchSwitch(Options)) {}
759 
760 std::vector<SourceLocation> UncheckedOptionalAccessDiagnoser::diagnose(
761     ASTContext &Context, const Stmt *Stmt, const Environment &Env) {
762   return DiagnoseMatchSwitch(*Stmt, Context, Env);
763 }
764 
765 } // namespace dataflow
766 } // namespace clang
767