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