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