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 
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 
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 
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 
76 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 
85 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 
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:
147   MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
148 
149   bool VisitSymbol(SymbolRef sym) override {
150     SymReaper.markLive(sym);
151     return true;
152   }
153 
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
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 
210 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