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