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