1 //===- Environment.cpp - Map from Stmt* to Locations/Values ---------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file defined the Environment and EnvironmentManager classes.
11 //===----------------------------------------------------------------------===//
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"
34 using namespace clang;
37 static const Expr *ignoreTransparentExprs(const Expr *E) {
38 E = E->IgnoreParens();
40 switch (E->getStmtClass()) {
41 case Stmt::OpaqueValueExprClass:
42 E = cast<OpaqueValueExpr>(E)->getSourceExpr();
44 case Stmt::ExprWithCleanupsClass:
45 E = cast<ExprWithCleanups>(E)->getSubExpr();
47 case Stmt::ConstantExprClass:
48 E = cast<ConstantExpr>(E)->getSubExpr();
50 case Stmt::CXXBindTemporaryExprClass:
51 E = cast<CXXBindTemporaryExpr>(E)->getSubExpr();
53 case Stmt::SubstNonTypeTemplateParmExprClass:
54 E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement();
57 // This is the base case: we can't look through more than we already have.
61 return ignoreTransparentExprs(E);
64 static const Stmt *ignoreTransparentExprs(const Stmt *S) {
65 if (const auto *E = dyn_cast<Expr>(S))
66 return ignoreTransparentExprs(E);
70 EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L)
71 : std::pair<const Stmt *,
72 const StackFrameContext *>(ignoreTransparentExprs(S),
73 L ? L->getStackFrame()
76 SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
77 const SVal* X = ExprBindings.lookup(E);
85 SVal Environment::getSVal(const EnvironmentEntry &Entry,
86 SValBuilder& svalBuilder) const {
87 const Stmt *S = Entry.getStmt();
88 const LocationContext *LCtx = Entry.getLocationContext();
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");
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();
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();
122 // Handle all other Stmt* using a lookup.
124 return lookupExpr(EnvironmentEntry(S, LCtx));
128 Environment EnvironmentManager::bindExpr(Environment Env,
129 const EnvironmentEntry &E,
134 return Environment(F.remove(Env.ExprBindings, E));
138 return Environment(F.add(Env.ExprBindings, E, V));
143 class MarkLiveCallback final : public SymbolVisitor {
144 SymbolReaper &SymReaper;
147 MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
149 bool VisitSymbol(SymbolRef sym) override {
150 SymReaper.markLive(sym);
154 bool VisitMemRegion(const MemRegion *R) override {
155 SymReaper.markLive(R);
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.
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();
178 MarkLiveCallback CB(SymReaper);
179 ScanReachableSymbols RSScaner(ST, CB);
181 llvm::ImmutableMapRef<EnvironmentEntry, SVal>
182 EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
185 // Iterate over the block-expr bindings.
186 for (Environment::iterator I = Env.begin(), E = Env.end();
188 const EnvironmentEntry &BlkExpr = I.getKey();
189 const SVal &X = I.getData();
191 if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
192 // Copy the binding to the new map.
193 EBMapRef = EBMapRef.add(BlkExpr, X);
195 // Mark all symbols in the block expr's value live.
200 NewEnv.ExprBindings = EBMapRef.asImmutableMap();
204 void Environment::printJson(raw_ostream &Out, const ASTContext &Ctx,
205 const LocationContext *LCtx, const char *NL,
206 unsigned int Space, bool IsDot) const {
207 Indent(Out, Space, IsDot) << "\"environment\": ";
209 if (ExprBindings.isEmpty()) {
210 Out << "null," << NL;
216 // Find the freshest location context.
217 llvm::SmallPtrSet<const LocationContext *, 16> FoundContexts;
218 for (const auto &I : *this) {
219 const LocationContext *LC = I.first.getLocationContext();
220 if (FoundContexts.count(LC) == 0) {
221 // This context is fresher than all other contexts so far.
223 for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent())
224 FoundContexts.insert(LCI);
231 Out << "{ \"pointer\": \"" << (const void *)LCtx->getStackFrame()
232 << "\", \"items\": [" << NL;
233 PrintingPolicy PP = Ctx.getPrintingPolicy();
235 LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) {
237 bool HasItem = false;
238 unsigned int InnerSpace = Space + 1;
240 // Store the last ExprBinding which we will print.
241 BindingsTy::iterator LastI = ExprBindings.end();
242 for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end();
244 if (I->first.getLocationContext() != LC)
252 const Stmt *S = I->first.getStmt();
254 assert(S != nullptr && "Expected non-null Stmt");
259 for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end();
261 if (I->first.getLocationContext() != LC)
264 const Stmt *S = I->first.getStmt();
265 Indent(Out, InnerSpace, IsDot)
266 << "{ \"stmt_id\": " << S->getID(Ctx) << ", \"pretty\": ";
267 S->printJson(Out, nullptr, PP, /*AddQuotes=*/true);
269 Out << ", \"value\": ";
270 I->second.printJson(Out, /*AddQuotes=*/true);
280 Indent(Out, --InnerSpace, IsDot) << ']';
285 Indent(Out, --Space, IsDot) << "]}," << NL;