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