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