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 auto isStdSwapCall() {
111   return callExpr(callee(functionDecl(hasName("std::swap"))),
112                   argumentCountIs(2), hasArgument(0, hasOptionalType()),
113                   hasArgument(1, hasOptionalType()));
114 }
115 
116 /// Creates a symbolic value for an `optional` value using `HasValueVal` as the
117 /// symbolic value of its "has_value" property.
118 StructValue &createOptionalValue(Environment &Env, BoolValue &HasValueVal) {
119   auto OptionalVal = std::make_unique<StructValue>();
120   OptionalVal->setProperty("has_value", HasValueVal);
121   return Env.takeOwnership(std::move(OptionalVal));
122 }
123 
124 /// Returns the symbolic value that represents the "has_value" property of the
125 /// optional value `Val`. Returns null if `Val` is null.
126 BoolValue *getHasValue(Value *Val) {
127   if (auto *OptionalVal = cast_or_null<StructValue>(Val)) {
128     return cast<BoolValue>(OptionalVal->getProperty("has_value"));
129   }
130   return nullptr;
131 }
132 
133 /// If `Type` is a reference type, returns the type of its pointee. Otherwise,
134 /// returns `Type` itself.
135 QualType stripReference(QualType Type) {
136   return Type->isReferenceType() ? Type->getPointeeType() : Type;
137 }
138 
139 /// Returns true if and only if `Type` is an optional type.
140 bool IsOptionalType(QualType Type) {
141   if (!Type->isRecordType())
142     return false;
143   // FIXME: Optimize this by avoiding the `getQualifiedNameAsString` call.
144   auto TypeName = Type->getAsCXXRecordDecl()->getQualifiedNameAsString();
145   return TypeName == "std::optional" || TypeName == "absl::optional" ||
146          TypeName == "base::Optional";
147 }
148 
149 /// Returns the number of optional wrappers in `Type`.
150 ///
151 /// For example, if `Type` is `optional<optional<int>>`, the result of this
152 /// function will be 2.
153 int countOptionalWrappers(const ASTContext &ASTCtx, QualType Type) {
154   if (!IsOptionalType(Type))
155     return 0;
156   return 1 + countOptionalWrappers(
157                  ASTCtx,
158                  cast<ClassTemplateSpecializationDecl>(Type->getAsRecordDecl())
159                      ->getTemplateArgs()
160                      .get(0)
161                      .getAsType()
162                      .getDesugaredType(ASTCtx));
163 }
164 
165 void initializeOptionalReference(const Expr *OptionalExpr,
166                                  const MatchFinder::MatchResult &,
167                                  LatticeTransferState &State) {
168   if (auto *OptionalVal = cast_or_null<StructValue>(
169           State.Env.getValue(*OptionalExpr, SkipPast::Reference))) {
170     if (OptionalVal->getProperty("has_value") == nullptr) {
171       OptionalVal->setProperty("has_value", State.Env.makeAtomicBoolValue());
172     }
173   }
174 }
175 
176 void transferUnwrapCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
177                         LatticeTransferState &State) {
178   if (auto *OptionalVal = cast_or_null<StructValue>(
179           State.Env.getValue(*ObjectExpr, SkipPast::ReferenceThenPointer))) {
180     auto *HasValueVal = getHasValue(OptionalVal);
181     assert(HasValueVal != nullptr);
182 
183     if (State.Env.flowConditionImplies(*HasValueVal))
184       return;
185   }
186 
187   // Record that this unwrap is *not* provably safe.
188   State.Lattice.getSourceLocations().insert(ObjectExpr->getBeginLoc());
189 }
190 
191 void transferMakeOptionalCall(const CallExpr *E,
192                               const MatchFinder::MatchResult &,
193                               LatticeTransferState &State) {
194   auto &Loc = State.Env.createStorageLocation(*E);
195   State.Env.setStorageLocation(*E, Loc);
196   State.Env.setValue(
197       Loc, createOptionalValue(State.Env, State.Env.getBoolLiteralValue(true)));
198 }
199 
200 void transferOptionalHasValueCall(const CXXMemberCallExpr *CallExpr,
201                                   const MatchFinder::MatchResult &,
202                                   LatticeTransferState &State) {
203   if (auto *OptionalVal = cast_or_null<StructValue>(
204           State.Env.getValue(*CallExpr->getImplicitObjectArgument(),
205                              SkipPast::ReferenceThenPointer))) {
206     auto *HasValueVal = getHasValue(OptionalVal);
207     assert(HasValueVal != nullptr);
208 
209     auto &CallExprLoc = State.Env.createStorageLocation(*CallExpr);
210     State.Env.setValue(CallExprLoc, *HasValueVal);
211     State.Env.setStorageLocation(*CallExpr, CallExprLoc);
212   }
213 }
214 
215 void assignOptionalValue(const Expr &E, LatticeTransferState &State,
216                          BoolValue &HasValueVal) {
217   if (auto *OptionalLoc =
218           State.Env.getStorageLocation(E, SkipPast::ReferenceThenPointer)) {
219     State.Env.setValue(*OptionalLoc,
220                        createOptionalValue(State.Env, HasValueVal));
221   }
222 }
223 
224 /// Returns a symbolic value for the "has_value" property of an `optional<T>`
225 /// value that is constructed/assigned from a value of type `U` or `optional<U>`
226 /// where `T` is constructible from `U`.
227 BoolValue &
228 getValueOrConversionHasValue(const FunctionDecl &F, const Expr &E,
229                              const MatchFinder::MatchResult &MatchRes,
230                              LatticeTransferState &State) {
231   assert(F.getTemplateSpecializationArgs()->size() > 0);
232 
233   const int TemplateParamOptionalWrappersCount = countOptionalWrappers(
234       *MatchRes.Context,
235       stripReference(F.getTemplateSpecializationArgs()->get(0).getAsType()));
236   const int ArgTypeOptionalWrappersCount =
237       countOptionalWrappers(*MatchRes.Context, stripReference(E.getType()));
238 
239   // Check if this is a constructor/assignment call for `optional<T>` with
240   // argument of type `U` such that `T` is constructible from `U`.
241   if (TemplateParamOptionalWrappersCount == ArgTypeOptionalWrappersCount)
242     return State.Env.getBoolLiteralValue(true);
243 
244   // This is a constructor/assignment call for `optional<T>` with argument of
245   // type `optional<U>` such that `T` is constructible from `U`.
246   if (BoolValue *Val = getHasValue(State.Env.getValue(E, SkipPast::Reference)))
247     return *Val;
248   return State.Env.makeAtomicBoolValue();
249 }
250 
251 void transferValueOrConversionConstructor(
252     const CXXConstructExpr *E, const MatchFinder::MatchResult &MatchRes,
253     LatticeTransferState &State) {
254   assert(E->getNumArgs() > 0);
255 
256   assignOptionalValue(*E, State,
257                       getValueOrConversionHasValue(*E->getConstructor(),
258                                                    *E->getArg(0), MatchRes,
259                                                    State));
260 }
261 
262 void transferAssignment(const CXXOperatorCallExpr *E, BoolValue &HasValueVal,
263                         LatticeTransferState &State) {
264   assert(E->getNumArgs() > 0);
265 
266   auto *OptionalLoc =
267       State.Env.getStorageLocation(*E->getArg(0), SkipPast::Reference);
268   assert(OptionalLoc != nullptr);
269 
270   State.Env.setValue(*OptionalLoc, createOptionalValue(State.Env, HasValueVal));
271 
272   // Assign a storage location for the whole expression.
273   State.Env.setStorageLocation(*E, *OptionalLoc);
274 }
275 
276 void transferValueOrConversionAssignment(
277     const CXXOperatorCallExpr *E, const MatchFinder::MatchResult &MatchRes,
278     LatticeTransferState &State) {
279   assert(E->getNumArgs() > 1);
280   transferAssignment(E,
281                      getValueOrConversionHasValue(
282                          *E->getDirectCallee(), *E->getArg(1), MatchRes, State),
283                      State);
284 }
285 
286 void transferNulloptAssignment(const CXXOperatorCallExpr *E,
287                                const MatchFinder::MatchResult &,
288                                LatticeTransferState &State) {
289   transferAssignment(E, State.Env.getBoolLiteralValue(false), State);
290 }
291 
292 void transferSwap(const StorageLocation &OptionalLoc1,
293                   const StorageLocation &OptionalLoc2,
294                   LatticeTransferState &State) {
295   auto *OptionalVal1 = State.Env.getValue(OptionalLoc1);
296   assert(OptionalVal1 != nullptr);
297 
298   auto *OptionalVal2 = State.Env.getValue(OptionalLoc2);
299   assert(OptionalVal2 != nullptr);
300 
301   State.Env.setValue(OptionalLoc1, *OptionalVal2);
302   State.Env.setValue(OptionalLoc2, *OptionalVal1);
303 }
304 
305 void transferSwapCall(const CXXMemberCallExpr *E,
306                       const MatchFinder::MatchResult &,
307                       LatticeTransferState &State) {
308   assert(E->getNumArgs() == 1);
309 
310   auto *OptionalLoc1 = State.Env.getStorageLocation(
311       *E->getImplicitObjectArgument(), SkipPast::ReferenceThenPointer);
312   assert(OptionalLoc1 != nullptr);
313 
314   auto *OptionalLoc2 =
315       State.Env.getStorageLocation(*E->getArg(0), SkipPast::Reference);
316   assert(OptionalLoc2 != nullptr);
317 
318   transferSwap(*OptionalLoc1, *OptionalLoc2, State);
319 }
320 
321 void transferStdSwapCall(const CallExpr *E, const MatchFinder::MatchResult &,
322                          LatticeTransferState &State) {
323   assert(E->getNumArgs() == 2);
324 
325   auto *OptionalLoc1 =
326       State.Env.getStorageLocation(*E->getArg(0), SkipPast::Reference);
327   assert(OptionalLoc1 != nullptr);
328 
329   auto *OptionalLoc2 =
330       State.Env.getStorageLocation(*E->getArg(1), SkipPast::Reference);
331   assert(OptionalLoc2 != nullptr);
332 
333   transferSwap(*OptionalLoc1, *OptionalLoc2, State);
334 }
335 
336 auto buildTransferMatchSwitch() {
337   // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
338   // lot of duplicated work (e.g. string comparisons), consider providing APIs
339   // that avoid it through memoization.
340   return MatchSwitchBuilder<LatticeTransferState>()
341       // Attach a symbolic "has_value" state to optional values that we see for
342       // the first time.
343       .CaseOf<Expr>(expr(anyOf(declRefExpr(), memberExpr()), hasOptionalType()),
344                     initializeOptionalReference)
345 
346       // make_optional
347       .CaseOf<CallExpr>(isMakeOptionalCall(), transferMakeOptionalCall)
348 
349       // optional::optional
350       .CaseOf<CXXConstructExpr>(
351           isOptionalInPlaceConstructor(),
352           [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
353              LatticeTransferState &State) {
354             assignOptionalValue(*E, State, State.Env.getBoolLiteralValue(true));
355           })
356       .CaseOf<CXXConstructExpr>(
357           isOptionalNulloptConstructor(),
358           [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
359              LatticeTransferState &State) {
360             assignOptionalValue(*E, State,
361                                 State.Env.getBoolLiteralValue(false));
362           })
363       .CaseOf<CXXConstructExpr>(isOptionalValueOrConversionConstructor(),
364                                 transferValueOrConversionConstructor)
365 
366       // optional::operator=
367       .CaseOf<CXXOperatorCallExpr>(isOptionalValueOrConversionAssignment(),
368                                    transferValueOrConversionAssignment)
369       .CaseOf<CXXOperatorCallExpr>(isOptionalNulloptAssignment(),
370                                    transferNulloptAssignment)
371 
372       // optional::value
373       .CaseOf<CXXMemberCallExpr>(
374           isOptionalMemberCallWithName("value"),
375           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
376              LatticeTransferState &State) {
377             transferUnwrapCall(E, E->getImplicitObjectArgument(), State);
378           })
379 
380       // optional::operator*, optional::operator->
381       .CaseOf<CallExpr>(expr(anyOf(isOptionalOperatorCallWithName("*"),
382                                    isOptionalOperatorCallWithName("->"))),
383                         [](const CallExpr *E, const MatchFinder::MatchResult &,
384                            LatticeTransferState &State) {
385                           transferUnwrapCall(E, E->getArg(0), State);
386                         })
387 
388       // optional::has_value
389       .CaseOf<CXXMemberCallExpr>(isOptionalMemberCallWithName("has_value"),
390                                  transferOptionalHasValueCall)
391 
392       // optional::operator bool
393       .CaseOf<CXXMemberCallExpr>(isOptionalMemberCallWithName("operator bool"),
394                                  transferOptionalHasValueCall)
395 
396       // optional::emplace
397       .CaseOf<CXXMemberCallExpr>(
398           isOptionalMemberCallWithName("emplace"),
399           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
400              LatticeTransferState &State) {
401             assignOptionalValue(*E->getImplicitObjectArgument(), State,
402                                 State.Env.getBoolLiteralValue(true));
403           })
404 
405       // optional::reset
406       .CaseOf<CXXMemberCallExpr>(
407           isOptionalMemberCallWithName("reset"),
408           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
409              LatticeTransferState &State) {
410             assignOptionalValue(*E->getImplicitObjectArgument(), State,
411                                 State.Env.getBoolLiteralValue(false));
412           })
413 
414       // optional::swap
415       .CaseOf<CXXMemberCallExpr>(isOptionalMemberCallWithName("swap"),
416                                  transferSwapCall)
417 
418       // std::swap
419       .CaseOf<CallExpr>(isStdSwapCall(), transferStdSwapCall)
420 
421       .Build();
422 }
423 
424 } // namespace
425 
426 UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(ASTContext &Ctx)
427     : DataflowAnalysis<UncheckedOptionalAccessModel, SourceLocationsLattice>(
428           Ctx),
429       TransferMatchSwitch(buildTransferMatchSwitch()) {}
430 
431 void UncheckedOptionalAccessModel::transfer(const Stmt *S,
432                                             SourceLocationsLattice &L,
433                                             Environment &Env) {
434   LatticeTransferState State(L, Env);
435   TransferMatchSwitch(*S, getASTContext(), State);
436 }
437 
438 } // namespace dataflow
439 } // namespace clang
440