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
33using namespace clang;
34using namespace ento;
35
36static 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
66EnvironmentEntry::EnvironmentEntry(const Expr *E, const StackFrame *SF)
67 : std::pair<const Expr *, const StackFrame *>(ignoreTransparentExprs(E),
68 SF) {}
69
70SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
71 const SVal* X = ExprBindings.lookup(K: E);
72 if (X) {
73 SVal V = *X;
74 return V;
75 }
76 return UnknownVal();
77}
78
79SVal Environment::getSVal(const EnvironmentEntry &Entry,
80 SValBuilder& svalBuilder) const {
81 const Expr *Ex = Entry.getExpr();
82 const StackFrame *SF = Entry.getStackFrame();
83
84 switch (Ex->getStmtClass()) {
85 case Stmt::CXXBindTemporaryExprClass:
86 case Stmt::ExprWithCleanupsClass:
87 case Stmt::GenericSelectionExprClass:
88 case Stmt::ConstantExprClass:
89 case Stmt::ParenExprClass:
90 case Stmt::SubstNonTypeTemplateParmExprClass:
91 llvm_unreachable("Should have been handled by ignoreTransparentExprs");
92
93 case Stmt::AddrLabelExprClass:
94 case Stmt::CharacterLiteralClass:
95 case Stmt::CXXBoolLiteralExprClass:
96 case Stmt::CXXScalarValueInitExprClass:
97 case Stmt::ImplicitValueInitExprClass:
98 case Stmt::IntegerLiteralClass:
99 case Stmt::ObjCBoolLiteralExprClass:
100 case Stmt::CXXNullPtrLiteralExprClass:
101 case Stmt::ObjCStringLiteralClass:
102 case Stmt::StringLiteralClass:
103 case Stmt::TypeTraitExprClass:
104 case Stmt::SizeOfPackExprClass:
105 case Stmt::PredefinedExprClass:
106 // Known constants; defer to SValBuilder.
107 return *svalBuilder.getConstantVal(E: Ex);
108
109 // Handle all other Expr* using a lookup.
110 default:
111 return lookupExpr(E: EnvironmentEntry(Ex, SF));
112 }
113}
114
115Environment EnvironmentManager::bindExpr(Environment Env,
116 const EnvironmentEntry &E,
117 SVal V,
118 bool Invalidate) {
119 if (V.isUnknown()) {
120 if (Invalidate)
121 return Environment(F.remove(Old: Env.ExprBindings, K: E));
122 else
123 return Env;
124 }
125 return Environment(F.add(Old: Env.ExprBindings, K: E, D: V));
126}
127
128namespace {
129
130class MarkLiveCallback final : public SymbolVisitor {
131 SymbolReaper &SymReaper;
132
133public:
134 MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
135
136 bool VisitSymbol(SymbolRef sym) override {
137 SymReaper.markLive(sym);
138 return true;
139 }
140
141 bool VisitMemRegion(const MemRegion *R) override {
142 SymReaper.markLive(region: R);
143 return true;
144 }
145};
146
147} // namespace
148
149// removeDeadBindings:
150// - Remove subexpression bindings.
151// - Remove dead block expression bindings.
152// - Keep live block expression bindings:
153// - Mark their reachable symbols live in SymbolReaper,
154// see ScanReachableSymbols.
155// - Mark the region in DRoots if the binding is a loc::MemRegionVal.
156Environment
157EnvironmentManager::removeDeadBindings(Environment Env,
158 SymbolReaper &SymReaper,
159 ProgramStateRef ST) {
160 // We construct a new Environment object entirely, as this is cheaper than
161 // individually removing all the subexpression bindings (which will greatly
162 // outnumber block-level expression bindings).
163 Environment NewEnv = getInitialEnvironment();
164
165 MarkLiveCallback CB(SymReaper);
166 ScanReachableSymbols RSScaner(ST, CB);
167
168 llvm::ImmutableMapRef<EnvironmentEntry, SVal>
169 EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
170 F.getTreeFactory());
171
172 // Iterate over the block-expr bindings.
173 for (Environment::iterator I = Env.begin(), End = Env.end(); I != End; ++I) {
174 const EnvironmentEntry &BlkExpr = I.getKey();
175 SVal X = I.getData();
176
177 if (SymReaper.isLive(ExprVal: BlkExpr.getExpr(), SF: BlkExpr.getStackFrame())) {
178 // Copy the binding to the new map.
179 EBMapRef = EBMapRef.add(K: BlkExpr, D: X);
180
181 // Mark all symbols in the block expr's value live.
182 RSScaner.scan(val: X);
183 }
184 }
185
186 NewEnv.ExprBindings = EBMapRef.asImmutableMap();
187 return NewEnv;
188}
189
190void Environment::printJson(raw_ostream &Out, const ASTContext &Ctx,
191 const StackFrame *SF, const char *NL,
192 unsigned int Space, bool IsDot) const {
193 Indent(Out, Space, IsDot) << "\"environment\": ";
194
195 if (ExprBindings.isEmpty()) {
196 Out << "null," << NL;
197 return;
198 }
199
200 ++Space;
201 if (!SF) {
202 // Find the freshest stack frame.
203 llvm::SmallPtrSet<const StackFrame *, 16> FoundStackFrames;
204 for (const auto &I : *this) {
205 const StackFrame *CurrentSF = I.first.getStackFrame();
206 if (FoundStackFrames.count(Ptr: CurrentSF) == 0) {
207 // This stack frame is fresher than all other stack frames so far.
208 SF = CurrentSF;
209 for (const StackFrame *SFI = CurrentSF; SFI; SFI = SFI->getParent())
210 FoundStackFrames.insert(Ptr: SFI);
211 }
212 }
213 }
214
215 assert(SF);
216
217 Out << "{ \"pointer\": \"" << (const void *)SF << "\", \"items\": [" << NL;
218 PrintingPolicy PP = Ctx.getPrintingPolicy();
219
220 SF->printJson(Out, NL, Space, IsDot, printMoreInfoPerStackFrame: [&](const StackFrame *SF) {
221 // SF items begin
222 bool HasItem = false;
223 unsigned int InnerSpace = Space + 1;
224
225 // Store the last ExprBinding which we will print.
226 BindingsTy::iterator LastI = ExprBindings.end();
227 for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end();
228 ++I) {
229 if (I->first.getStackFrame() != SF)
230 continue;
231
232 if (!HasItem) {
233 HasItem = true;
234 Out << '[' << NL;
235 }
236
237 const Expr *Ex = I->first.getExpr();
238 (void)Ex;
239 assert(Ex != nullptr && "Expected non-null Expr");
240
241 LastI = I;
242 }
243
244 for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end();
245 ++I) {
246 if (I->first.getStackFrame() != SF)
247 continue;
248
249 const Expr *Ex = I->first.getExpr();
250 Indent(Out, Space: InnerSpace, IsDot)
251 << "{ \"stmt_id\": " << Ex->getID(Context: Ctx) << ", \"kind\": \""
252 << Ex->getStmtClassName() << "\", \"pretty\": ";
253 Ex->printJson(Out, Helper: nullptr, Policy: PP, /*AddQuotes=*/true);
254
255 Out << ", \"value\": ";
256 I->second.printJson(Out, /*AddQuotes=*/true);
257
258 Out << " }";
259
260 if (I != LastI)
261 Out << ',';
262 Out << NL;
263 }
264
265 if (HasItem)
266 Indent(Out, Space: --InnerSpace, IsDot) << ']';
267 else
268 Out << "null ";
269 });
270
271 Indent(Out, Space: --Space, IsDot) << "]}," << NL;
272}
273