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/Expr.h"
17 #include "clang/AST/ExprCXX.h"
18 #include "clang/AST/Stmt.h"
19 #include "clang/ASTMatchers/ASTMatchers.h"
20 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
21 #include "clang/Analysis/FlowSensitive/MatchSwitch.h"
22 #include "clang/Analysis/FlowSensitive/SourceLocationsLattice.h"
23 #include "clang/Analysis/FlowSensitive/Value.h"
24 #include "llvm/ADT/StringRef.h"
25 #include "llvm/Support/Casting.h"
26 #include <cassert>
27 #include <memory>
28 #include <utility>
29 
30 namespace clang {
31 namespace dataflow {
32 namespace {
33 
34 using namespace ::clang::ast_matchers;
35 
36 using LatticeTransferState = TransferState<SourceLocationsLattice>;
37 
38 auto optionalClass() {
39   return classTemplateSpecializationDecl(
40       anyOf(hasName("std::optional"), hasName("std::__optional_storage_base"),
41             hasName("__optional_destruct_base"), hasName("absl::optional"),
42             hasName("base::Optional")),
43       hasTemplateArgument(0, refersToType(type().bind("T"))));
44 }
45 
46 auto hasOptionalType() { return hasType(optionalClass()); }
47 
48 auto isOptionalMemberCallWithName(llvm::StringRef MemberName) {
49   return cxxMemberCallExpr(
50       on(expr(unless(cxxThisExpr()))),
51       callee(cxxMethodDecl(hasName(MemberName), ofClass(optionalClass()))));
52 }
53 
54 auto isOptionalOperatorCallWithName(llvm::StringRef OperatorName) {
55   return cxxOperatorCallExpr(hasOverloadedOperatorName(OperatorName),
56                              callee(cxxMethodDecl(ofClass(optionalClass()))));
57 }
58 
59 auto isMakeOptionalCall() {
60   return callExpr(
61       callee(functionDecl(hasAnyName(
62           "std::make_optional", "base::make_optional", "absl::make_optional"))),
63       hasOptionalType());
64 }
65 
66 auto hasNulloptType() {
67   return hasType(namedDecl(
68       hasAnyName("std::nullopt_t", "absl::nullopt_t", "base::nullopt_t")));
69 }
70 
71 auto inPlaceClass() {
72   return recordDecl(
73       hasAnyName("std::in_place_t", "absl::in_place_t", "base::in_place_t"));
74 }
75 
76 auto isOptionalNulloptConstructor() {
77   return cxxConstructExpr(hasOptionalType(), argumentCountIs(1),
78                           hasArgument(0, hasNulloptType()));
79 }
80 
81 auto isOptionalInPlaceConstructor() {
82   return cxxConstructExpr(hasOptionalType(),
83                           hasArgument(0, hasType(inPlaceClass())));
84 }
85 
86 auto isOptionalValueOrConversionConstructor() {
87   return cxxConstructExpr(
88       hasOptionalType(),
89       unless(hasDeclaration(
90           cxxConstructorDecl(anyOf(isCopyConstructor(), isMoveConstructor())))),
91       argumentCountIs(1), hasArgument(0, unless(hasNulloptType())));
92 }
93 
94 auto isOptionalValueOrConversionAssignment() {
95   return cxxOperatorCallExpr(
96       hasOverloadedOperatorName("="),
97       callee(cxxMethodDecl(ofClass(optionalClass()))),
98       unless(hasDeclaration(cxxMethodDecl(
99           anyOf(isCopyAssignmentOperator(), isMoveAssignmentOperator())))),
100       argumentCountIs(2), hasArgument(1, unless(hasNulloptType())));
101 }
102 
103 auto isOptionalNulloptAssignment() {
104   return cxxOperatorCallExpr(hasOverloadedOperatorName("="),
105                              callee(cxxMethodDecl(ofClass(optionalClass()))),
106                              argumentCountIs(2),
107                              hasArgument(1, hasNulloptType()));
108 }
109 
110 /// Creates a symbolic value for an `optional` value using `HasValueVal` as the
111 /// symbolic value of its "has_value" property.
112 StructValue &createOptionalValue(Environment &Env, BoolValue &HasValueVal) {
113   auto OptionalVal = std::make_unique<StructValue>();
114   OptionalVal->setProperty("has_value", HasValueVal);
115   return Env.takeOwnership(std::move(OptionalVal));
116 }
117 
118 /// Returns the symbolic value that represents the "has_value" property of the
119 /// optional value `Val`. Returns null if `Val` is null.
120 BoolValue *getHasValue(Value *Val) {
121   if (auto *OptionalVal = cast_or_null<StructValue>(Val)) {
122     return cast<BoolValue>(OptionalVal->getProperty("has_value"));
123   }
124   return nullptr;
125 }
126 
127 /// If `Type` is a reference type, returns the type of its pointee. Otherwise,
128 /// returns `Type` itself.
129 QualType stripReference(QualType Type) {
130   return Type->isReferenceType() ? Type->getPointeeType() : Type;
131 }
132 
133 /// Returns true if and only if `Type` is an optional type.
134 bool IsOptionalType(QualType Type) {
135   if (!Type->isRecordType())
136     return false;
137   // FIXME: Optimize this by avoiding the `getQualifiedNameAsString` call.
138   auto TypeName = Type->getAsCXXRecordDecl()->getQualifiedNameAsString();
139   return TypeName == "std::optional" || TypeName == "absl::optional" ||
140          TypeName == "base::Optional";
141 }
142 
143 /// Returns the number of optional wrappers in `Type`.
144 ///
145 /// For example, if `Type` is `optional<optional<int>>`, the result of this
146 /// function will be 2.
147 int countOptionalWrappers(const ASTContext &ASTCtx, QualType Type) {
148   if (!IsOptionalType(Type))
149     return 0;
150   return 1 + countOptionalWrappers(
151                  ASTCtx,
152                  cast<ClassTemplateSpecializationDecl>(Type->getAsRecordDecl())
153                      ->getTemplateArgs()
154                      .get(0)
155                      .getAsType()
156                      .getDesugaredType(ASTCtx));
157 }
158 
159 void initializeOptionalReference(const Expr *OptionalExpr,
160                                  const MatchFinder::MatchResult &,
161                                  LatticeTransferState &State) {
162   if (auto *OptionalVal = cast_or_null<StructValue>(
163           State.Env.getValue(*OptionalExpr, SkipPast::Reference))) {
164     if (OptionalVal->getProperty("has_value") == nullptr) {
165       OptionalVal->setProperty("has_value", State.Env.makeAtomicBoolValue());
166     }
167   }
168 }
169 
170 void transferUnwrapCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
171                         LatticeTransferState &State) {
172   if (auto *OptionalVal = cast_or_null<StructValue>(
173           State.Env.getValue(*ObjectExpr, SkipPast::ReferenceThenPointer))) {
174     auto *HasValueVal = getHasValue(OptionalVal);
175     assert(HasValueVal != nullptr);
176 
177     if (State.Env.flowConditionImplies(*HasValueVal))
178       return;
179   }
180 
181   // Record that this unwrap is *not* provably safe.
182   State.Lattice.getSourceLocations().insert(ObjectExpr->getBeginLoc());
183 }
184 
185 void transferMakeOptionalCall(const CallExpr *E,
186                               const MatchFinder::MatchResult &,
187                               LatticeTransferState &State) {
188   auto &Loc = State.Env.createStorageLocation(*E);
189   State.Env.setStorageLocation(*E, Loc);
190   State.Env.setValue(
191       Loc, createOptionalValue(State.Env, State.Env.getBoolLiteralValue(true)));
192 }
193 
194 void transferOptionalHasValueCall(const CXXMemberCallExpr *CallExpr,
195                                   const MatchFinder::MatchResult &,
196                                   LatticeTransferState &State) {
197   if (auto *OptionalVal = cast_or_null<StructValue>(
198           State.Env.getValue(*CallExpr->getImplicitObjectArgument(),
199                              SkipPast::ReferenceThenPointer))) {
200     auto *HasValueVal = getHasValue(OptionalVal);
201     assert(HasValueVal != nullptr);
202 
203     auto &CallExprLoc = State.Env.createStorageLocation(*CallExpr);
204     State.Env.setValue(CallExprLoc, *HasValueVal);
205     State.Env.setStorageLocation(*CallExpr, CallExprLoc);
206   }
207 }
208 
209 void assignOptionalValue(const Expr &E, LatticeTransferState &State,
210                          BoolValue &HasValueVal) {
211   if (auto *OptionalLoc =
212           State.Env.getStorageLocation(E, SkipPast::ReferenceThenPointer)) {
213     State.Env.setValue(*OptionalLoc,
214                        createOptionalValue(State.Env, HasValueVal));
215   }
216 }
217 
218 /// Returns a symbolic value for the "has_value" property of an `optional<T>`
219 /// value that is constructed/assigned from a value of type `U` or `optional<U>`
220 /// where `T` is constructible from `U`.
221 BoolValue &
222 getValueOrConversionHasValue(const FunctionDecl &F, const Expr &E,
223                              const MatchFinder::MatchResult &MatchRes,
224                              LatticeTransferState &State) {
225   assert(F.getTemplateSpecializationArgs()->size() > 0);
226 
227   const int TemplateParamOptionalWrappersCount = countOptionalWrappers(
228       *MatchRes.Context,
229       stripReference(F.getTemplateSpecializationArgs()->get(0).getAsType()));
230   const int ArgTypeOptionalWrappersCount =
231       countOptionalWrappers(*MatchRes.Context, stripReference(E.getType()));
232 
233   // Check if this is a constructor/assignment call for `optional<T>` with
234   // argument of type `U` such that `T` is constructible from `U`.
235   if (TemplateParamOptionalWrappersCount == ArgTypeOptionalWrappersCount)
236     return State.Env.getBoolLiteralValue(true);
237 
238   // This is a constructor/assignment call for `optional<T>` with argument of
239   // type `optional<U>` such that `T` is constructible from `U`.
240   if (BoolValue *Val = getHasValue(State.Env.getValue(E, SkipPast::Reference)))
241     return *Val;
242   return State.Env.makeAtomicBoolValue();
243 }
244 
245 void transferValueOrConversionConstructor(
246     const CXXConstructExpr *E, const MatchFinder::MatchResult &MatchRes,
247     LatticeTransferState &State) {
248   assert(E->getNumArgs() > 0);
249 
250   assignOptionalValue(*E, State,
251                       getValueOrConversionHasValue(*E->getConstructor(),
252                                                    *E->getArg(0), MatchRes,
253                                                    State));
254 }
255 
256 void transferAssignment(const CXXOperatorCallExpr *E, BoolValue &HasValueVal,
257                         LatticeTransferState &State) {
258   assert(E->getNumArgs() > 0);
259 
260   auto *OptionalLoc =
261       State.Env.getStorageLocation(*E->getArg(0), SkipPast::Reference);
262   assert(OptionalLoc != nullptr);
263 
264   State.Env.setValue(*OptionalLoc, createOptionalValue(State.Env, HasValueVal));
265 
266   // Assign a storage location for the whole expression.
267   State.Env.setStorageLocation(*E, *OptionalLoc);
268 }
269 
270 void transferValueOrConversionAssignment(
271     const CXXOperatorCallExpr *E, const MatchFinder::MatchResult &MatchRes,
272     LatticeTransferState &State) {
273   assert(E->getNumArgs() > 1);
274   transferAssignment(E,
275                      getValueOrConversionHasValue(
276                          *E->getDirectCallee(), *E->getArg(1), MatchRes, State),
277                      State);
278 }
279 
280 void transferNulloptAssignment(const CXXOperatorCallExpr *E,
281                                const MatchFinder::MatchResult &,
282                                LatticeTransferState &State) {
283   transferAssignment(E, State.Env.getBoolLiteralValue(false), State);
284 }
285 
286 auto buildTransferMatchSwitch() {
287   // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
288   // lot of duplicated work (e.g. string comparisons), consider providing APIs
289   // that avoid it through memoization.
290   return MatchSwitchBuilder<LatticeTransferState>()
291       // Attach a symbolic "has_value" state to optional values that we see for
292       // the first time.
293       .CaseOf<Expr>(expr(anyOf(declRefExpr(), memberExpr()), hasOptionalType()),
294                     initializeOptionalReference)
295 
296       // make_optional
297       .CaseOf<CallExpr>(isMakeOptionalCall(), transferMakeOptionalCall)
298 
299       // optional::optional
300       .CaseOf<CXXConstructExpr>(
301           isOptionalInPlaceConstructor(),
302           [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
303              LatticeTransferState &State) {
304             assignOptionalValue(*E, State, State.Env.getBoolLiteralValue(true));
305           })
306       .CaseOf<CXXConstructExpr>(
307           isOptionalNulloptConstructor(),
308           [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
309              LatticeTransferState &State) {
310             assignOptionalValue(*E, State,
311                                 State.Env.getBoolLiteralValue(false));
312           })
313       .CaseOf<CXXConstructExpr>(isOptionalValueOrConversionConstructor(),
314                                 transferValueOrConversionConstructor)
315 
316       // optional::operator=
317       .CaseOf<CXXOperatorCallExpr>(isOptionalValueOrConversionAssignment(),
318                                    transferValueOrConversionAssignment)
319       .CaseOf<CXXOperatorCallExpr>(isOptionalNulloptAssignment(),
320                                    transferNulloptAssignment)
321 
322       // optional::value
323       .CaseOf<CXXMemberCallExpr>(
324           isOptionalMemberCallWithName("value"),
325           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
326              LatticeTransferState &State) {
327             transferUnwrapCall(E, E->getImplicitObjectArgument(), State);
328           })
329 
330       // optional::operator*, optional::operator->
331       .CaseOf<CallExpr>(expr(anyOf(isOptionalOperatorCallWithName("*"),
332                                    isOptionalOperatorCallWithName("->"))),
333                         [](const CallExpr *E, const MatchFinder::MatchResult &,
334                            LatticeTransferState &State) {
335                           transferUnwrapCall(E, E->getArg(0), State);
336                         })
337 
338       // optional::has_value
339       .CaseOf<CXXMemberCallExpr>(isOptionalMemberCallWithName("has_value"),
340                                  transferOptionalHasValueCall)
341 
342       // optional::operator bool
343       .CaseOf<CXXMemberCallExpr>(isOptionalMemberCallWithName("operator bool"),
344                                  transferOptionalHasValueCall)
345 
346       // optional::emplace
347       .CaseOf<CXXMemberCallExpr>(
348           isOptionalMemberCallWithName("emplace"),
349           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
350              LatticeTransferState &State) {
351             assignOptionalValue(*E->getImplicitObjectArgument(), State,
352                                 State.Env.getBoolLiteralValue(true));
353           })
354 
355       // optional::reset
356       .CaseOf<CXXMemberCallExpr>(
357           isOptionalMemberCallWithName("reset"),
358           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
359              LatticeTransferState &State) {
360             assignOptionalValue(*E->getImplicitObjectArgument(), State,
361                                 State.Env.getBoolLiteralValue(false));
362           })
363 
364       .Build();
365 }
366 
367 } // namespace
368 
369 UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(ASTContext &Ctx)
370     : DataflowAnalysis<UncheckedOptionalAccessModel, SourceLocationsLattice>(
371           Ctx),
372       TransferMatchSwitch(buildTransferMatchSwitch()) {}
373 
374 void UncheckedOptionalAccessModel::transfer(const Stmt *S,
375                                             SourceLocationsLattice &L,
376                                             Environment &Env) {
377   LatticeTransferState State(L, Env);
378   TransferMatchSwitch(*S, getASTContext(), State);
379 }
380 
381 } // namespace dataflow
382 } // namespace clang
383