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