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