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::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       continue;
196     } else {
197       SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
198       for (; SI != SE; ++SI)
199         SymReaper.maybeDead(*SI);
200     }
201   }
202 
203   NewEnv.ExprBindings = EBMapRef.asImmutableMap();
204   return NewEnv;
205 }
206 
207 void Environment::print(raw_ostream &Out, const char *NL,
208                         const char *Sep,
209                         const ASTContext &Context,
210                         const LocationContext *WithLC) const {
211   if (ExprBindings.isEmpty())
212     return;
213 
214   if (!WithLC) {
215     // Find the freshest location context.
216     llvm::SmallPtrSet<const LocationContext *, 16> FoundContexts;
217     for (auto I : *this) {
218       const LocationContext *LC = I.first.getLocationContext();
219       if (FoundContexts.count(LC) == 0) {
220         // This context is fresher than all other contexts so far.
221         WithLC = LC;
222         for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent())
223           FoundContexts.insert(LCI);
224       }
225     }
226   }
227 
228   assert(WithLC);
229 
230   PrintingPolicy PP = Context.getPrintingPolicy();
231 
232   Out << NL << "Expressions by stack frame:" << NL;
233   WithLC->dumpStack(Out, "", NL, Sep, [&](const LocationContext *LC) {
234     for (auto I : ExprBindings) {
235       if (I.first.getLocationContext() != LC)
236         continue;
237 
238       const Stmt *S = I.first.getStmt();
239       assert(S != nullptr && "Expected non-null Stmt");
240 
241       Out << "(LC" << LC->getID() << ", S" << S->getID(Context) << ") ";
242       S->printPretty(Out, /*Helper=*/nullptr, PP);
243       Out << " : " << I.second << NL;
244     }
245   });
246 }
247