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/NoopLattice.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<NoopLattice>;
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 }
317 
318 void transferMakeOptionalCall(const CallExpr *E,
319                               const MatchFinder::MatchResult &,
320                               LatticeTransferState &State) {
321   auto &Loc = State.Env.createStorageLocation(*E);
322   State.Env.setStorageLocation(*E, Loc);
323   State.Env.setValue(
324       Loc, createOptionalValue(State.Env, State.Env.getBoolLiteralValue(true)));
325 }
326 
327 void transferOptionalHasValueCall(const CXXMemberCallExpr *CallExpr,
328                                   const MatchFinder::MatchResult &,
329                                   LatticeTransferState &State) {
330   if (auto *HasValueVal = getHasValue(
331           State.Env, State.Env.getValue(*CallExpr->getImplicitObjectArgument(),
332                                         SkipPast::ReferenceThenPointer))) {
333     auto &CallExprLoc = State.Env.createStorageLocation(*CallExpr);
334     State.Env.setValue(CallExprLoc, *HasValueVal);
335     State.Env.setStorageLocation(*CallExpr, CallExprLoc);
336   }
337 }
338 
339 /// `ModelPred` builds a logical formula relating the predicate in
340 /// `ValueOrPredExpr` to the optional's `has_value` property.
341 void transferValueOrImpl(const clang::Expr *ValueOrPredExpr,
342                          const MatchFinder::MatchResult &Result,
343                          LatticeTransferState &State,
344                          BoolValue &(*ModelPred)(Environment &Env,
345                                                  BoolValue &ExprVal,
346                                                  BoolValue &HasValueVal)) {
347   auto &Env = State.Env;
348 
349   const auto *ObjectArgumentExpr =
350       Result.Nodes.getNodeAs<clang::CXXMemberCallExpr>(ValueOrCallID)
351           ->getImplicitObjectArgument();
352 
353   auto *HasValueVal = getHasValue(
354       State.Env,
355       State.Env.getValue(*ObjectArgumentExpr, SkipPast::ReferenceThenPointer));
356   if (HasValueVal == nullptr)
357     return;
358 
359   auto *ExprValue = cast_or_null<BoolValue>(
360       State.Env.getValue(*ValueOrPredExpr, SkipPast::None));
361   if (ExprValue == nullptr) {
362     auto &ExprLoc = State.Env.createStorageLocation(*ValueOrPredExpr);
363     ExprValue = &State.Env.makeAtomicBoolValue();
364     State.Env.setValue(ExprLoc, *ExprValue);
365     State.Env.setStorageLocation(*ValueOrPredExpr, ExprLoc);
366   }
367 
368   Env.addToFlowCondition(ModelPred(Env, *ExprValue, *HasValueVal));
369 }
370 
371 void transferValueOrStringEmptyCall(const clang::Expr *ComparisonExpr,
372                                     const MatchFinder::MatchResult &Result,
373                                     LatticeTransferState &State) {
374   return transferValueOrImpl(ComparisonExpr, Result, State,
375                              [](Environment &Env, BoolValue &ExprVal,
376                                 BoolValue &HasValueVal) -> BoolValue & {
377                                // If the result is *not* empty, then we know the
378                                // optional must have been holding a value. If
379                                // `ExprVal` is true, though, we don't learn
380                                // anything definite about `has_value`, so we
381                                // don't add any corresponding implications to
382                                // the flow condition.
383                                return Env.makeImplication(Env.makeNot(ExprVal),
384                                                           HasValueVal);
385                              });
386 }
387 
388 void transferValueOrNotEqX(const Expr *ComparisonExpr,
389                            const MatchFinder::MatchResult &Result,
390                            LatticeTransferState &State) {
391   transferValueOrImpl(ComparisonExpr, Result, State,
392                       [](Environment &Env, BoolValue &ExprVal,
393                          BoolValue &HasValueVal) -> BoolValue & {
394                         // We know that if `(opt.value_or(X) != X)` then
395                         // `opt.hasValue()`, even without knowing further
396                         // details about the contents of `opt`.
397                         return Env.makeImplication(ExprVal, HasValueVal);
398                       });
399 }
400 
401 void transferCallReturningOptional(const CallExpr *E,
402                                    const MatchFinder::MatchResult &Result,
403                                    LatticeTransferState &State) {
404   if (State.Env.getStorageLocation(*E, SkipPast::None) != nullptr)
405     return;
406 
407   auto &Loc = State.Env.createStorageLocation(*E);
408   State.Env.setStorageLocation(*E, Loc);
409   State.Env.setValue(
410       Loc, createOptionalValue(State.Env, State.Env.makeAtomicBoolValue()));
411 }
412 
413 void assignOptionalValue(const Expr &E, LatticeTransferState &State,
414                          BoolValue &HasValueVal) {
415   if (auto *OptionalLoc =
416           State.Env.getStorageLocation(E, SkipPast::ReferenceThenPointer)) {
417     State.Env.setValue(*OptionalLoc,
418                        createOptionalValue(State.Env, HasValueVal));
419   }
420 }
421 
422 /// Returns a symbolic value for the "has_value" property of an `optional<T>`
423 /// value that is constructed/assigned from a value of type `U` or `optional<U>`
424 /// where `T` is constructible from `U`.
425 BoolValue &value_orConversionHasValue(const FunctionDecl &F, const Expr &E,
426                                       const MatchFinder::MatchResult &MatchRes,
427                                       LatticeTransferState &State) {
428   assert(F.getTemplateSpecializationArgs()->size() > 0);
429 
430   const int TemplateParamOptionalWrappersCount = countOptionalWrappers(
431       *MatchRes.Context,
432       stripReference(F.getTemplateSpecializationArgs()->get(0).getAsType()));
433   const int ArgTypeOptionalWrappersCount =
434       countOptionalWrappers(*MatchRes.Context, stripReference(E.getType()));
435 
436   // Check if this is a constructor/assignment call for `optional<T>` with
437   // argument of type `U` such that `T` is constructible from `U`.
438   if (TemplateParamOptionalWrappersCount == ArgTypeOptionalWrappersCount)
439     return State.Env.getBoolLiteralValue(true);
440 
441   // This is a constructor/assignment call for `optional<T>` with argument of
442   // type `optional<U>` such that `T` is constructible from `U`.
443   if (auto *HasValueVal =
444           getHasValue(State.Env, State.Env.getValue(E, SkipPast::Reference)))
445     return *HasValueVal;
446   return State.Env.makeAtomicBoolValue();
447 }
448 
449 void transferValueOrConversionConstructor(
450     const CXXConstructExpr *E, const MatchFinder::MatchResult &MatchRes,
451     LatticeTransferState &State) {
452   assert(E->getNumArgs() > 0);
453 
454   assignOptionalValue(*E, State,
455                       value_orConversionHasValue(*E->getConstructor(),
456                                                  *E->getArg(0), MatchRes,
457                                                  State));
458 }
459 
460 void transferAssignment(const CXXOperatorCallExpr *E, BoolValue &HasValueVal,
461                         LatticeTransferState &State) {
462   assert(E->getNumArgs() > 0);
463 
464   auto *OptionalLoc =
465       State.Env.getStorageLocation(*E->getArg(0), SkipPast::Reference);
466   if (OptionalLoc == nullptr)
467     return;
468 
469   State.Env.setValue(*OptionalLoc, createOptionalValue(State.Env, HasValueVal));
470 
471   // Assign a storage location for the whole expression.
472   State.Env.setStorageLocation(*E, *OptionalLoc);
473 }
474 
475 void transferValueOrConversionAssignment(
476     const CXXOperatorCallExpr *E, const MatchFinder::MatchResult &MatchRes,
477     LatticeTransferState &State) {
478   assert(E->getNumArgs() > 1);
479   transferAssignment(E,
480                      value_orConversionHasValue(*E->getDirectCallee(),
481                                                 *E->getArg(1), MatchRes, State),
482                      State);
483 }
484 
485 void transferNulloptAssignment(const CXXOperatorCallExpr *E,
486                                const MatchFinder::MatchResult &,
487                                LatticeTransferState &State) {
488   transferAssignment(E, State.Env.getBoolLiteralValue(false), State);
489 }
490 
491 void transferSwap(const StorageLocation &OptionalLoc1,
492                   const StorageLocation &OptionalLoc2,
493                   LatticeTransferState &State) {
494   auto *OptionalVal1 = State.Env.getValue(OptionalLoc1);
495   assert(OptionalVal1 != nullptr);
496 
497   auto *OptionalVal2 = State.Env.getValue(OptionalLoc2);
498   assert(OptionalVal2 != nullptr);
499 
500   State.Env.setValue(OptionalLoc1, *OptionalVal2);
501   State.Env.setValue(OptionalLoc2, *OptionalVal1);
502 }
503 
504 void transferSwapCall(const CXXMemberCallExpr *E,
505                       const MatchFinder::MatchResult &,
506                       LatticeTransferState &State) {
507   assert(E->getNumArgs() == 1);
508 
509   auto *OptionalLoc1 = State.Env.getStorageLocation(
510       *E->getImplicitObjectArgument(), SkipPast::ReferenceThenPointer);
511   assert(OptionalLoc1 != nullptr);
512 
513   auto *OptionalLoc2 =
514       State.Env.getStorageLocation(*E->getArg(0), SkipPast::Reference);
515   assert(OptionalLoc2 != nullptr);
516 
517   transferSwap(*OptionalLoc1, *OptionalLoc2, State);
518 }
519 
520 void transferStdSwapCall(const CallExpr *E, const MatchFinder::MatchResult &,
521                          LatticeTransferState &State) {
522   assert(E->getNumArgs() == 2);
523 
524   auto *OptionalLoc1 =
525       State.Env.getStorageLocation(*E->getArg(0), SkipPast::Reference);
526   assert(OptionalLoc1 != nullptr);
527 
528   auto *OptionalLoc2 =
529       State.Env.getStorageLocation(*E->getArg(1), SkipPast::Reference);
530   assert(OptionalLoc2 != nullptr);
531 
532   transferSwap(*OptionalLoc1, *OptionalLoc2, State);
533 }
534 
535 llvm::Optional<StatementMatcher>
536 ignorableOptional(const UncheckedOptionalAccessModelOptions &Options) {
537   if (Options.IgnoreSmartPointerDereference)
538     return memberExpr(hasObjectExpression(ignoringParenImpCasts(
539         cxxOperatorCallExpr(anyOf(hasOverloadedOperatorName("->"),
540                                   hasOverloadedOperatorName("*")),
541                             unless(hasArgument(0, expr(hasOptionalType())))))));
542   return llvm::None;
543 }
544 
545 StatementMatcher
546 valueCall(llvm::Optional<StatementMatcher> &IgnorableOptional) {
547   return isOptionalMemberCallWithName("value", IgnorableOptional);
548 }
549 
550 StatementMatcher
551 valueOperatorCall(llvm::Optional<StatementMatcher> &IgnorableOptional) {
552   return expr(anyOf(isOptionalOperatorCallWithName("*", IgnorableOptional),
553                     isOptionalOperatorCallWithName("->", IgnorableOptional)));
554 }
555 
556 auto buildTransferMatchSwitch(
557     const UncheckedOptionalAccessModelOptions &Options) {
558   // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
559   // lot of duplicated work (e.g. string comparisons), consider providing APIs
560   // that avoid it through memoization.
561   auto IgnorableOptional = ignorableOptional(Options);
562   return MatchSwitchBuilder<LatticeTransferState>()
563       // Attach a symbolic "has_value" state to optional values that we see for
564       // the first time.
565       .CaseOf<Expr>(
566           expr(anyOf(declRefExpr(), memberExpr()), hasOptionalType()),
567           initializeOptionalReference)
568 
569       // make_optional
570       .CaseOf<CallExpr>(isMakeOptionalCall(), transferMakeOptionalCall)
571 
572       // optional::optional
573       .CaseOf<CXXConstructExpr>(
574           isOptionalInPlaceConstructor(),
575           [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
576              LatticeTransferState &State) {
577             assignOptionalValue(*E, State, State.Env.getBoolLiteralValue(true));
578           })
579       .CaseOf<CXXConstructExpr>(
580           isOptionalNulloptConstructor(),
581           [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
582              LatticeTransferState &State) {
583             assignOptionalValue(*E, State,
584                                 State.Env.getBoolLiteralValue(false));
585           })
586       .CaseOf<CXXConstructExpr>(isOptionalValueOrConversionConstructor(),
587                                 transferValueOrConversionConstructor)
588 
589       // optional::operator=
590       .CaseOf<CXXOperatorCallExpr>(isOptionalValueOrConversionAssignment(),
591                                    transferValueOrConversionAssignment)
592       .CaseOf<CXXOperatorCallExpr>(isOptionalNulloptAssignment(),
593                                    transferNulloptAssignment)
594 
595       // optional::value
596       .CaseOf<CXXMemberCallExpr>(
597           valueCall(IgnorableOptional),
598           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
599              LatticeTransferState &State) {
600             transferUnwrapCall(E, E->getImplicitObjectArgument(), State);
601           })
602 
603       // optional::operator*, optional::operator->
604       .CaseOf<CallExpr>(valueOperatorCall(IgnorableOptional),
605                         [](const CallExpr *E, const MatchFinder::MatchResult &,
606                            LatticeTransferState &State) {
607                           transferUnwrapCall(E, E->getArg(0), State);
608                         })
609 
610       // optional::has_value
611       .CaseOf<CXXMemberCallExpr>(isOptionalMemberCallWithName("has_value"),
612                                  transferOptionalHasValueCall)
613 
614       // optional::operator bool
615       .CaseOf<CXXMemberCallExpr>(isOptionalMemberCallWithName("operator bool"),
616                                  transferOptionalHasValueCall)
617 
618       // optional::emplace
619       .CaseOf<CXXMemberCallExpr>(
620           isOptionalMemberCallWithName("emplace"),
621           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
622              LatticeTransferState &State) {
623             assignOptionalValue(*E->getImplicitObjectArgument(), State,
624                                 State.Env.getBoolLiteralValue(true));
625           })
626 
627       // optional::reset
628       .CaseOf<CXXMemberCallExpr>(
629           isOptionalMemberCallWithName("reset"),
630           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
631              LatticeTransferState &State) {
632             assignOptionalValue(*E->getImplicitObjectArgument(), State,
633                                 State.Env.getBoolLiteralValue(false));
634           })
635 
636       // optional::swap
637       .CaseOf<CXXMemberCallExpr>(isOptionalMemberCallWithName("swap"),
638                                  transferSwapCall)
639 
640       // std::swap
641       .CaseOf<CallExpr>(isStdSwapCall(), transferStdSwapCall)
642 
643       // opt.value_or("").empty()
644       .CaseOf<Expr>(isValueOrStringEmptyCall(), transferValueOrStringEmptyCall)
645 
646       // opt.value_or(X) != X
647       .CaseOf<Expr>(isValueOrNotEqX(), transferValueOrNotEqX)
648 
649       // returns optional
650       .CaseOf<CallExpr>(isCallReturningOptional(),
651                         transferCallReturningOptional)
652 
653       .Build();
654 }
655 
656 std::vector<SourceLocation> diagnoseUnwrapCall(const Expr *UnwrapExpr,
657                                                const Expr *ObjectExpr,
658                                                const Environment &Env) {
659   if (auto *OptionalVal =
660           Env.getValue(*ObjectExpr, SkipPast::ReferenceThenPointer)) {
661     auto *Prop = OptionalVal->getProperty("has_value");
662     if (auto *HasValueVal = cast_or_null<BoolValue>(Prop)) {
663       if (Env.flowConditionImplies(*HasValueVal))
664         return {};
665     }
666   }
667 
668   // Record that this unwrap is *not* provably safe.
669   // FIXME: include either the name of the optional (if applicable) or a source
670   // range of the access for easier interpretation of the result.
671   return {ObjectExpr->getBeginLoc()};
672 }
673 
674 auto buildDiagnoseMatchSwitch(
675     const UncheckedOptionalAccessModelOptions &Options) {
676   // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
677   // lot of duplicated work (e.g. string comparisons), consider providing APIs
678   // that avoid it through memoization.
679   auto IgnorableOptional = ignorableOptional(Options);
680   return MatchSwitchBuilder<const Environment, std::vector<SourceLocation>>()
681       // optional::value
682       .CaseOf<CXXMemberCallExpr>(
683           valueCall(IgnorableOptional),
684           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
685              const Environment &Env) {
686             return diagnoseUnwrapCall(E, E->getImplicitObjectArgument(), Env);
687           })
688 
689       // optional::operator*, optional::operator->
690       .CaseOf<CallExpr>(
691           valueOperatorCall(IgnorableOptional),
692           [](const CallExpr *E, const MatchFinder::MatchResult &,
693              const Environment &Env) {
694             return diagnoseUnwrapCall(E, E->getArg(0), Env);
695           })
696       .Build();
697 }
698 
699 } // namespace
700 
701 ast_matchers::DeclarationMatcher
702 UncheckedOptionalAccessModel::optionalClassDecl() {
703   return optionalClass();
704 }
705 
706 UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(
707     ASTContext &Ctx, UncheckedOptionalAccessModelOptions Options)
708     : DataflowAnalysis<UncheckedOptionalAccessModel, NoopLattice>(Ctx),
709       TransferMatchSwitch(buildTransferMatchSwitch(Options)) {}
710 
711 void UncheckedOptionalAccessModel::transfer(const Stmt *S, NoopLattice &L,
712                                             Environment &Env) {
713   LatticeTransferState State(L, Env);
714   TransferMatchSwitch(*S, getASTContext(), State);
715 }
716 
717 bool UncheckedOptionalAccessModel::compareEquivalent(QualType Type,
718                                                      const Value &Val1,
719                                                      const Environment &Env1,
720                                                      const Value &Val2,
721                                                      const Environment &Env2) {
722   return isNonEmptyOptional(Val1, Env1) == isNonEmptyOptional(Val2, Env2);
723 }
724 
725 bool UncheckedOptionalAccessModel::merge(QualType Type, const Value &Val1,
726                                          const Environment &Env1,
727                                          const Value &Val2,
728                                          const Environment &Env2,
729                                          Value &MergedVal,
730                                          Environment &MergedEnv) {
731   if (!IsOptionalType(Type))
732     return true;
733 
734   auto &HasValueVal = MergedEnv.makeAtomicBoolValue();
735   if (isNonEmptyOptional(Val1, Env1) && isNonEmptyOptional(Val2, Env2))
736     MergedEnv.addToFlowCondition(HasValueVal);
737   else if (isEmptyOptional(Val1, Env1) && isEmptyOptional(Val2, Env2))
738     MergedEnv.addToFlowCondition(MergedEnv.makeNot(HasValueVal));
739   setHasValue(MergedVal, HasValueVal);
740   return true;
741 }
742 
743 UncheckedOptionalAccessDiagnoser::UncheckedOptionalAccessDiagnoser(
744     UncheckedOptionalAccessModelOptions Options)
745     : DiagnoseMatchSwitch(buildDiagnoseMatchSwitch(Options)) {}
746 
747 std::vector<SourceLocation> UncheckedOptionalAccessDiagnoser::diagnose(
748     ASTContext &Context, const Stmt *Stmt, const Environment &Env) {
749   return DiagnoseMatchSwitch(*Stmt, Context, Env);
750 }
751 
752 } // namespace dataflow
753 } // namespace clang
754