1 //===- Environment.cpp - Map from Stmt* to Locations/Values ---------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file defined the Environment and EnvironmentManager classes.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h"
15 #include "clang/AST/Expr.h"
16 #include "clang/AST/ExprCXX.h"
17 #include "clang/AST/PrettyPrinter.h"
18 #include "clang/AST/Stmt.h"
19 #include "clang/Analysis/AnalysisDeclContext.h"
20 #include "clang/Basic/LLVM.h"
21 #include "clang/Basic/LangOptions.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     // Known constants; defer to SValBuilder.
112     return svalBuilder.getConstantVal(cast<Expr>(S)).getValue();
113 
114   case Stmt::ReturnStmtClass: {
115     const auto *RS = cast<ReturnStmt>(S);
116     if (const Expr *RE = RS->getRetValue())
117       return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder);
118     return UndefinedVal();
119   }
120 
121   // Handle all other Stmt* using a lookup.
122   default:
123     return lookupExpr(EnvironmentEntry(S, LCtx));
124   }
125 }
126 
127 Environment EnvironmentManager::bindExpr(Environment Env,
128                                          const EnvironmentEntry &E,
129                                          SVal V,
130                                          bool Invalidate) {
131   if (V.isUnknown()) {
132     if (Invalidate)
133       return Environment(F.remove(Env.ExprBindings, E));
134     else
135       return Env;
136   }
137   return Environment(F.add(Env.ExprBindings, E, V));
138 }
139 
140 namespace {
141 
142 class MarkLiveCallback final : public SymbolVisitor {
143   SymbolReaper &SymReaper;
144 
145 public:
146   MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
147 
148   bool VisitSymbol(SymbolRef sym) override {
149     SymReaper.markLive(sym);
150     return true;
151   }
152 
153   bool VisitMemRegion(const MemRegion *R) override {
154     SymReaper.markLive(R);
155     return true;
156   }
157 };
158 
159 } // namespace
160 
161 // removeDeadBindings:
162 //  - Remove subexpression bindings.
163 //  - Remove dead block expression bindings.
164 //  - Keep live block expression bindings:
165 //   - Mark their reachable symbols live in SymbolReaper,
166 //     see ScanReachableSymbols.
167 //   - Mark the region in DRoots if the binding is a loc::MemRegionVal.
168 Environment
169 EnvironmentManager::removeDeadBindings(Environment Env,
170                                        SymbolReaper &SymReaper,
171                                        ProgramStateRef ST) {
172   // We construct a new Environment object entirely, as this is cheaper than
173   // individually removing all the subexpression bindings (which will greatly
174   // outnumber block-level expression bindings).
175   Environment NewEnv = getInitialEnvironment();
176 
177   MarkLiveCallback CB(SymReaper);
178   ScanReachableSymbols RSScaner(ST, CB);
179 
180   llvm::ImmutableMapRef<EnvironmentEntry, SVal>
181     EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
182              F.getTreeFactory());
183 
184   // Iterate over the block-expr bindings.
185   for (Environment::iterator I = Env.begin(), E = Env.end();
186        I != E; ++I) {
187     const EnvironmentEntry &BlkExpr = I.getKey();
188     const SVal &X = I.getData();
189 
190     if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
191       // Copy the binding to the new map.
192       EBMapRef = EBMapRef.add(BlkExpr, X);
193 
194       // Mark all symbols in the block expr's value live.
195       RSScaner.scan(X);
196     }
197   }
198 
199   NewEnv.ExprBindings = EBMapRef.asImmutableMap();
200   return NewEnv;
201 }
202 
203 void Environment::print(raw_ostream &Out, const char *NL,
204                         const char *Sep,
205                         const ASTContext &Context,
206                         const LocationContext *WithLC) const {
207   if (ExprBindings.isEmpty())
208     return;
209 
210   if (!WithLC) {
211     // Find the freshest location context.
212     llvm::SmallPtrSet<const LocationContext *, 16> FoundContexts;
213     for (auto I : *this) {
214       const LocationContext *LC = I.first.getLocationContext();
215       if (FoundContexts.count(LC) == 0) {
216         // This context is fresher than all other contexts so far.
217         WithLC = LC;
218         for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent())
219           FoundContexts.insert(LCI);
220       }
221     }
222   }
223 
224   assert(WithLC);
225 
226   PrintingPolicy PP = Context.getPrintingPolicy();
227 
228   Out << NL << "Expressions by stack frame:" << NL;
229   WithLC->dumpStack(Out, "", NL, Sep, [&](const LocationContext *LC) {
230     for (auto I : ExprBindings) {
231       if (I.first.getLocationContext() != LC)
232         continue;
233 
234       const Stmt *S = I.first.getStmt();
235       assert(S != nullptr && "Expected non-null Stmt");
236 
237       Out << "(LC" << LC->getID() << ", S" << S->getID(Context) << ") ";
238       S->printPretty(Out, /*Helper=*/nullptr, PP);
239       Out << " : " << I.second << NL;
240     }
241   });
242 }
243