1 | //===- Environment.cpp - Map from Stmt* to Locations/Values ---------------===// |
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 defined the Environment and EnvironmentManager classes. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h" |
14 | #include "clang/AST/Expr.h" |
15 | #include "clang/AST/ExprCXX.h" |
16 | #include "clang/AST/PrettyPrinter.h" |
17 | #include "clang/AST/Stmt.h" |
18 | #include "clang/AST/StmtObjC.h" |
19 | #include "clang/Analysis/AnalysisDeclContext.h" |
20 | #include "clang/Basic/JsonSupport.h" |
21 | #include "clang/Basic/LLVM.h" |
22 | #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" |
23 | #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" |
24 | #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" |
25 | #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" |
26 | #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" |
27 | #include "llvm/ADT/ImmutableMap.h" |
28 | #include "llvm/ADT/SmallPtrSet.h" |
29 | #include "llvm/Support/ErrorHandling.h" |
30 | #include "llvm/Support/raw_ostream.h" |
31 | #include <cassert> |
32 | |
33 | using namespace clang; |
34 | using namespace ento; |
35 | |
36 | static const Expr *ignoreTransparentExprs(const Expr *E) { |
37 | E = E->IgnoreParens(); |
38 | |
39 | switch (E->getStmtClass()) { |
40 | case Stmt::OpaqueValueExprClass: |
41 | if (const Expr *SE = cast<OpaqueValueExpr>(Val: E)->getSourceExpr()) { |
42 | E = SE; |
43 | break; |
44 | } |
45 | return E; |
46 | case Stmt::ExprWithCleanupsClass: |
47 | E = cast<ExprWithCleanups>(Val: E)->getSubExpr(); |
48 | break; |
49 | case Stmt::ConstantExprClass: |
50 | E = cast<ConstantExpr>(Val: E)->getSubExpr(); |
51 | break; |
52 | case Stmt::CXXBindTemporaryExprClass: |
53 | E = cast<CXXBindTemporaryExpr>(Val: E)->getSubExpr(); |
54 | break; |
55 | case Stmt::SubstNonTypeTemplateParmExprClass: |
56 | E = cast<SubstNonTypeTemplateParmExpr>(Val: E)->getReplacement(); |
57 | break; |
58 | default: |
59 | // This is the base case: we can't look through more than we already have. |
60 | return E; |
61 | } |
62 | |
63 | return ignoreTransparentExprs(E); |
64 | } |
65 | |
66 | static const Stmt *ignoreTransparentExprs(const Stmt *S) { |
67 | if (const auto *E = dyn_cast<Expr>(Val: S)) |
68 | return ignoreTransparentExprs(E); |
69 | return S; |
70 | } |
71 | |
72 | EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L) |
73 | : std::pair<const Stmt *, |
74 | const StackFrameContext *>(ignoreTransparentExprs(S), |
75 | L ? L->getStackFrame() |
76 | : nullptr) {} |
77 | |
78 | SVal Environment::lookupExpr(const EnvironmentEntry &E) const { |
79 | const SVal* X = ExprBindings.lookup(K: E); |
80 | if (X) { |
81 | SVal V = *X; |
82 | return V; |
83 | } |
84 | return UnknownVal(); |
85 | } |
86 | |
87 | SVal Environment::getSVal(const EnvironmentEntry &Entry, |
88 | SValBuilder& svalBuilder) const { |
89 | const Stmt *S = Entry.getStmt(); |
90 | assert(!isa<ObjCForCollectionStmt>(S) && |
91 | "Use ExprEngine::hasMoreIteration()!" ); |
92 | assert((isa<Expr, ReturnStmt>(S)) && |
93 | "Environment can only argue about Exprs, since only they express " |
94 | "a value! Any non-expression statement stored in Environment is a " |
95 | "result of a hack!" ); |
96 | const LocationContext *LCtx = Entry.getLocationContext(); |
97 | |
98 | switch (S->getStmtClass()) { |
99 | case Stmt::CXXBindTemporaryExprClass: |
100 | case Stmt::ExprWithCleanupsClass: |
101 | case Stmt::GenericSelectionExprClass: |
102 | case Stmt::ConstantExprClass: |
103 | case Stmt::ParenExprClass: |
104 | case Stmt::SubstNonTypeTemplateParmExprClass: |
105 | llvm_unreachable("Should have been handled by ignoreTransparentExprs" ); |
106 | |
107 | case Stmt::AddrLabelExprClass: |
108 | case Stmt::CharacterLiteralClass: |
109 | case Stmt::CXXBoolLiteralExprClass: |
110 | case Stmt::CXXScalarValueInitExprClass: |
111 | case Stmt::ImplicitValueInitExprClass: |
112 | case Stmt::IntegerLiteralClass: |
113 | case Stmt::ObjCBoolLiteralExprClass: |
114 | case Stmt::CXXNullPtrLiteralExprClass: |
115 | case Stmt::ObjCStringLiteralClass: |
116 | case Stmt::StringLiteralClass: |
117 | case Stmt::TypeTraitExprClass: |
118 | case Stmt::SizeOfPackExprClass: |
119 | case Stmt::PredefinedExprClass: |
120 | // Known constants; defer to SValBuilder. |
121 | return *svalBuilder.getConstantVal(E: cast<Expr>(Val: S)); |
122 | |
123 | case Stmt::ReturnStmtClass: { |
124 | const auto *RS = cast<ReturnStmt>(Val: S); |
125 | if (const Expr *RE = RS->getRetValue()) |
126 | return getSVal(Entry: EnvironmentEntry(RE, LCtx), svalBuilder); |
127 | return UndefinedVal(); |
128 | } |
129 | |
130 | // Handle all other Stmt* using a lookup. |
131 | default: |
132 | return lookupExpr(E: EnvironmentEntry(S, LCtx)); |
133 | } |
134 | } |
135 | |
136 | Environment EnvironmentManager::bindExpr(Environment Env, |
137 | const EnvironmentEntry &E, |
138 | SVal V, |
139 | bool Invalidate) { |
140 | if (V.isUnknown()) { |
141 | if (Invalidate) |
142 | return Environment(F.remove(Old: Env.ExprBindings, K: E)); |
143 | else |
144 | return Env; |
145 | } |
146 | return Environment(F.add(Old: Env.ExprBindings, K: E, D: V)); |
147 | } |
148 | |
149 | namespace { |
150 | |
151 | class MarkLiveCallback final : public SymbolVisitor { |
152 | SymbolReaper &SymReaper; |
153 | |
154 | public: |
155 | MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {} |
156 | |
157 | bool VisitSymbol(SymbolRef sym) override { |
158 | SymReaper.markLive(sym); |
159 | return true; |
160 | } |
161 | |
162 | bool VisitMemRegion(const MemRegion *R) override { |
163 | SymReaper.markLive(region: R); |
164 | return true; |
165 | } |
166 | }; |
167 | |
168 | } // namespace |
169 | |
170 | // removeDeadBindings: |
171 | // - Remove subexpression bindings. |
172 | // - Remove dead block expression bindings. |
173 | // - Keep live block expression bindings: |
174 | // - Mark their reachable symbols live in SymbolReaper, |
175 | // see ScanReachableSymbols. |
176 | // - Mark the region in DRoots if the binding is a loc::MemRegionVal. |
177 | Environment |
178 | EnvironmentManager::removeDeadBindings(Environment Env, |
179 | SymbolReaper &SymReaper, |
180 | ProgramStateRef ST) { |
181 | // We construct a new Environment object entirely, as this is cheaper than |
182 | // individually removing all the subexpression bindings (which will greatly |
183 | // outnumber block-level expression bindings). |
184 | Environment NewEnv = getInitialEnvironment(); |
185 | |
186 | MarkLiveCallback CB(SymReaper); |
187 | ScanReachableSymbols (ST, CB); |
188 | |
189 | llvm::ImmutableMapRef<EnvironmentEntry, SVal> |
190 | EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(), |
191 | F.getTreeFactory()); |
192 | |
193 | // Iterate over the block-expr bindings. |
194 | for (Environment::iterator I = Env.begin(), End = Env.end(); I != End; ++I) { |
195 | const EnvironmentEntry &BlkExpr = I.getKey(); |
196 | SVal X = I.getData(); |
197 | |
198 | const Expr *E = dyn_cast<Expr>(Val: BlkExpr.getStmt()); |
199 | if (!E) |
200 | continue; |
201 | |
202 | if (SymReaper.isLive(ExprVal: E, LCtx: BlkExpr.getLocationContext())) { |
203 | // Copy the binding to the new map. |
204 | EBMapRef = EBMapRef.add(K: BlkExpr, D: X); |
205 | |
206 | // Mark all symbols in the block expr's value live. |
207 | RSScaner.scan(val: X); |
208 | } |
209 | } |
210 | |
211 | NewEnv.ExprBindings = EBMapRef.asImmutableMap(); |
212 | return NewEnv; |
213 | } |
214 | |
215 | void Environment::printJson(raw_ostream &Out, const ASTContext &Ctx, |
216 | const LocationContext *LCtx, const char *NL, |
217 | unsigned int Space, bool IsDot) const { |
218 | Indent(Out, Space, IsDot) << "\"environment\": " ; |
219 | |
220 | if (ExprBindings.isEmpty()) { |
221 | Out << "null," << NL; |
222 | return; |
223 | } |
224 | |
225 | ++Space; |
226 | if (!LCtx) { |
227 | // Find the freshest location context. |
228 | llvm::SmallPtrSet<const LocationContext *, 16> FoundContexts; |
229 | for (const auto &I : *this) { |
230 | const LocationContext *LC = I.first.getLocationContext(); |
231 | if (FoundContexts.count(Ptr: LC) == 0) { |
232 | // This context is fresher than all other contexts so far. |
233 | LCtx = LC; |
234 | for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent()) |
235 | FoundContexts.insert(Ptr: LCI); |
236 | } |
237 | } |
238 | } |
239 | |
240 | assert(LCtx); |
241 | |
242 | Out << "{ \"pointer\": \"" << (const void *)LCtx->getStackFrame() |
243 | << "\", \"items\": [" << NL; |
244 | PrintingPolicy PP = Ctx.getPrintingPolicy(); |
245 | |
246 | LCtx->printJson(Out, NL, Space, IsDot, printMoreInfoPerContext: [&](const LocationContext *LC) { |
247 | // LCtx items begin |
248 | bool HasItem = false; |
249 | unsigned int InnerSpace = Space + 1; |
250 | |
251 | // Store the last ExprBinding which we will print. |
252 | BindingsTy::iterator LastI = ExprBindings.end(); |
253 | for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end(); |
254 | ++I) { |
255 | if (I->first.getLocationContext() != LC) |
256 | continue; |
257 | |
258 | if (!HasItem) { |
259 | HasItem = true; |
260 | Out << '[' << NL; |
261 | } |
262 | |
263 | const Stmt *S = I->first.getStmt(); |
264 | (void)S; |
265 | assert(S != nullptr && "Expected non-null Stmt" ); |
266 | |
267 | LastI = I; |
268 | } |
269 | |
270 | for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end(); |
271 | ++I) { |
272 | if (I->first.getLocationContext() != LC) |
273 | continue; |
274 | |
275 | const Stmt *S = I->first.getStmt(); |
276 | Indent(Out, Space: InnerSpace, IsDot) |
277 | << "{ \"stmt_id\": " << S->getID(Context: Ctx) << ", \"kind\": \"" |
278 | << S->getStmtClassName() << "\", \"pretty\": " ; |
279 | S->printJson(Out, Helper: nullptr, Policy: PP, /*AddQuotes=*/true); |
280 | |
281 | Out << ", \"value\": " ; |
282 | I->second.printJson(Out, /*AddQuotes=*/true); |
283 | |
284 | Out << " }" ; |
285 | |
286 | if (I != LastI) |
287 | Out << ','; |
288 | Out << NL; |
289 | } |
290 | |
291 | if (HasItem) |
292 | Indent(Out, Space: --InnerSpace, IsDot) << ']'; |
293 | else |
294 | Out << "null " ; |
295 | }); |
296 | |
297 | Indent(Out, Space: --Space, IsDot) << "]}," << NL; |
298 | } |
299 | |