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