1 //== Environment.cpp - Map from Stmt* to Locations/Values -------*- C++ -*--==//
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/AST/ExprCXX.h"
15 #include "clang/AST/ExprObjC.h"
16 #include "clang/Analysis/AnalysisContext.h"
17 #include "clang/Analysis/CFG.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
19 #include "llvm/Support/raw_ostream.h"
20 
21 using namespace clang;
22 using namespace ento;
23 
24 static const Expr *ignoreTransparentExprs(const Expr *E) {
25   E = E->IgnoreParens();
26 
27   switch (E->getStmtClass()) {
28   case Stmt::OpaqueValueExprClass:
29     E = cast<OpaqueValueExpr>(E)->getSourceExpr();
30     break;
31   case Stmt::ExprWithCleanupsClass:
32     E = cast<ExprWithCleanups>(E)->getSubExpr();
33     break;
34   case Stmt::CXXBindTemporaryExprClass:
35     E = cast<CXXBindTemporaryExpr>(E)->getSubExpr();
36     break;
37   case Stmt::SubstNonTypeTemplateParmExprClass:
38     E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement();
39     break;
40   case Stmt::CXXDefaultArgExprClass:
41     E = cast<CXXDefaultArgExpr>(E)->getExpr();
42     break;
43   default:
44     // This is the base case: we can't look through more than we already have.
45     return E;
46   }
47 
48   return ignoreTransparentExprs(E);
49 }
50 
51 static const Stmt *ignoreTransparentExprs(const Stmt *S) {
52   if (const Expr *E = dyn_cast<Expr>(S))
53     return ignoreTransparentExprs(E);
54   return S;
55 }
56 
57 EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L)
58   : std::pair<const Stmt *,
59               const StackFrameContext *>(ignoreTransparentExprs(S),
60                                          L ? L->getCurrentStackFrame() : 0) {}
61 
62 SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
63   const SVal* X = ExprBindings.lookup(E);
64   if (X) {
65     SVal V = *X;
66     return V;
67   }
68   return UnknownVal();
69 }
70 
71 SVal Environment::getSVal(const EnvironmentEntry &Entry,
72                           SValBuilder& svalBuilder) const {
73   const Stmt *S = Entry.getStmt();
74   const LocationContext *LCtx = Entry.getLocationContext();
75 
76   switch (S->getStmtClass()) {
77   case Stmt::CXXBindTemporaryExprClass:
78   case Stmt::CXXDefaultArgExprClass:
79   case Stmt::ExprWithCleanupsClass:
80   case Stmt::GenericSelectionExprClass:
81   case Stmt::OpaqueValueExprClass:
82   case Stmt::ParenExprClass:
83   case Stmt::SubstNonTypeTemplateParmExprClass:
84     llvm_unreachable("Should have been handled by ignoreTransparentExprs");
85 
86   case Stmt::AddrLabelExprClass:
87     return svalBuilder.makeLoc(cast<AddrLabelExpr>(S));
88 
89   case Stmt::CharacterLiteralClass: {
90     const CharacterLiteral *C = cast<CharacterLiteral>(S);
91     return svalBuilder.makeIntVal(C->getValue(), C->getType());
92   }
93 
94   case Stmt::CXXBoolLiteralExprClass:
95     return svalBuilder.makeBoolVal(cast<CXXBoolLiteralExpr>(S));
96 
97   case Stmt::CXXScalarValueInitExprClass:
98   case Stmt::ImplicitValueInitExprClass: {
99     QualType Ty = cast<Expr>(S)->getType();
100     return svalBuilder.makeZeroVal(Ty);
101   }
102 
103   case Stmt::IntegerLiteralClass:
104     return svalBuilder.makeIntVal(cast<IntegerLiteral>(S));
105 
106   case Stmt::ObjCBoolLiteralExprClass:
107     return svalBuilder.makeBoolVal(cast<ObjCBoolLiteralExpr>(S));
108 
109   // For special C0xx nullptr case, make a null pointer SVal.
110   case Stmt::CXXNullPtrLiteralExprClass:
111     return svalBuilder.makeNull();
112 
113   case Stmt::ObjCStringLiteralClass: {
114     MemRegionManager &MRMgr = svalBuilder.getRegionManager();
115     const ObjCStringLiteral *SL = cast<ObjCStringLiteral>(S);
116     return svalBuilder.makeLoc(MRMgr.getObjCStringRegion(SL));
117   }
118 
119   case Stmt::StringLiteralClass: {
120     MemRegionManager &MRMgr = svalBuilder.getRegionManager();
121     const StringLiteral *SL = cast<StringLiteral>(S);
122     return svalBuilder.makeLoc(MRMgr.getStringRegion(SL));
123   }
124 
125   case Stmt::ReturnStmtClass: {
126     const ReturnStmt *RS = cast<ReturnStmt>(S);
127     if (const Expr *RE = RS->getRetValue())
128       return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder);
129     return UndefinedVal();
130   }
131 
132   // Handle all other Stmt* using a lookup.
133   default:
134     break;
135   }
136 
137   return lookupExpr(EnvironmentEntry(S, LCtx));
138 }
139 
140 Environment EnvironmentManager::bindExpr(Environment Env,
141                                          const EnvironmentEntry &E,
142                                          SVal V,
143                                          bool Invalidate) {
144   if (V.isUnknown()) {
145     if (Invalidate)
146       return Environment(F.remove(Env.ExprBindings, E));
147     else
148       return Env;
149   }
150   return Environment(F.add(Env.ExprBindings, E, V));
151 }
152 
153 namespace {
154 class MarkLiveCallback : public SymbolVisitor {
155   SymbolReaper &SymReaper;
156 public:
157   MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
158   bool VisitSymbol(SymbolRef sym) {
159     SymReaper.markLive(sym);
160     return true;
161   }
162   bool VisitMemRegion(const MemRegion *R) {
163     SymReaper.markLive(R);
164     return true;
165   }
166 };
167 } // end anonymous namespace
168 
169 // removeDeadBindings:
170 //  - Remove subexpression bindings.
171 //  - Remove dead block expression bindings.
172 //  - Keep live block expression bindings:
173 //   - Mark their reachable symbols live in SymbolReaper,
174 //     see ScanReachableSymbols.
175 //   - Mark the region in DRoots if the binding is a loc::MemRegionVal.
176 Environment
177 EnvironmentManager::removeDeadBindings(Environment Env,
178                                        SymbolReaper &SymReaper,
179                                        ProgramStateRef ST) {
180 
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 
197     const EnvironmentEntry &BlkExpr = I.getKey();
198     const SVal &X = I.getData();
199 
200     if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
201       // Copy the binding to the new map.
202       EBMapRef = EBMapRef.add(BlkExpr, X);
203 
204       // If the block expr's value is a memory region, then mark that region.
205       if (isa<loc::MemRegionVal>(X)) {
206         const MemRegion *R = cast<loc::MemRegionVal>(X).getRegion();
207         SymReaper.markLive(R);
208       }
209 
210       // Mark all symbols in the block expr's value live.
211       RSScaner.scan(X);
212       continue;
213     } else {
214       SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
215       for (; SI != SE; ++SI)
216         SymReaper.maybeDead(*SI);
217     }
218   }
219 
220   NewEnv.ExprBindings = EBMapRef.asImmutableMap();
221   return NewEnv;
222 }
223 
224 void Environment::print(raw_ostream &Out, const char *NL,
225                         const char *Sep) const {
226   bool isFirst = true;
227 
228   for (Environment::iterator I = begin(), E = end(); I != E; ++I) {
229     const EnvironmentEntry &En = I.getKey();
230 
231     if (isFirst) {
232       Out << NL << NL
233           << "Expressions:"
234           << NL;
235       isFirst = false;
236     } else {
237       Out << NL;
238     }
239 
240     const Stmt *S = En.getStmt();
241 
242     Out << " (" << (const void*) En.getLocationContext() << ','
243       << (const void*) S << ") ";
244     LangOptions LO; // FIXME.
245     S->printPretty(Out, 0, PrintingPolicy(LO));
246     Out << " : " << I.getData();
247   }
248 }
249