Environment.cpp revision 38f68ef19cb51d5876e9025b5fceb44b33ec9ed7 
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
21using namespace clang;
22using namespace ento;
23
24static 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  default:
41    // This is the base case: we can't look through more than we already have.
42    return E;
43  }
44
45  return ignoreTransparentExprs(E);
46}
47
48static const Stmt *ignoreTransparentExprs(const Stmt *S) {
49  if (const Expr *E = dyn_cast<Expr>(S))
50    return ignoreTransparentExprs(E);
51  return S;
52}
53
54EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L)
55  : std::pair<const Stmt *,
56              const StackFrameContext *>(ignoreTransparentExprs(S),
57                                         L ? L->getCurrentStackFrame() : 0) {}
58
59SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
60  const SVal* X = ExprBindings.lookup(E);
61  if (X) {
62    SVal V = *X;
63    return V;
64  }
65  return UnknownVal();
66}
67
68SVal Environment::getSVal(const EnvironmentEntry &Entry,
69                          SValBuilder& svalBuilder) const {
70  const Stmt *S = Entry.getStmt();
71  const LocationContext *LCtx = Entry.getLocationContext();
72
73  switch (S->getStmtClass()) {
74  case Stmt::CXXBindTemporaryExprClass:
75  case Stmt::ExprWithCleanupsClass:
76  case Stmt::GenericSelectionExprClass:
77  case Stmt::OpaqueValueExprClass:
78  case Stmt::ParenExprClass:
79  case Stmt::SubstNonTypeTemplateParmExprClass:
80    llvm_unreachable("Should have been handled by ignoreTransparentExprs");
81
82  case Stmt::AddrLabelExprClass:
83    return svalBuilder.makeLoc(cast<AddrLabelExpr>(S));
84
85  case Stmt::CharacterLiteralClass: {
86    const CharacterLiteral *C = cast<CharacterLiteral>(S);
87    return svalBuilder.makeIntVal(C->getValue(), C->getType());
88  }
89
90  case Stmt::CXXBoolLiteralExprClass:
91    return svalBuilder.makeBoolVal(cast<CXXBoolLiteralExpr>(S));
92
93  case Stmt::CXXScalarValueInitExprClass:
94  case Stmt::ImplicitValueInitExprClass: {
95    QualType Ty = cast<Expr>(S)->getType();
96    return svalBuilder.makeZeroVal(Ty);
97  }
98
99  case Stmt::IntegerLiteralClass:
100    return svalBuilder.makeIntVal(cast<IntegerLiteral>(S));
101
102  case Stmt::ObjCBoolLiteralExprClass:
103    return svalBuilder.makeBoolVal(cast<ObjCBoolLiteralExpr>(S));
104
105  // For special C0xx nullptr case, make a null pointer SVal.
106  case Stmt::CXXNullPtrLiteralExprClass:
107    return svalBuilder.makeNull();
108
109  case Stmt::ObjCStringLiteralClass: {
110    MemRegionManager &MRMgr = svalBuilder.getRegionManager();
111    const ObjCStringLiteral *SL = cast<ObjCStringLiteral>(S);
112    return svalBuilder.makeLoc(MRMgr.getObjCStringRegion(SL));
113  }
114
115  case Stmt::StringLiteralClass: {
116    MemRegionManager &MRMgr = svalBuilder.getRegionManager();
117    const StringLiteral *SL = cast<StringLiteral>(S);
118    return svalBuilder.makeLoc(MRMgr.getStringRegion(SL));
119  }
120
121  case Stmt::ReturnStmtClass: {
122    const ReturnStmt *RS = cast<ReturnStmt>(S);
123    if (const Expr *RE = RS->getRetValue())
124      return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder);
125    return UndefinedVal();
126  }
127
128  // Handle all other Stmt* using a lookup.
129  default:
130    break;
131  }
132
133  return lookupExpr(EnvironmentEntry(S, LCtx));
134}
135
136Environment 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
149namespace {
150class MarkLiveCallback : public SymbolVisitor {
151  SymbolReaper &SymReaper;
152public:
153  MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
154  bool VisitSymbol(SymbolRef sym) {
155    SymReaper.markLive(sym);
156    return true;
157  }
158  bool VisitMemRegion(const MemRegion *R) {
159    SymReaper.markLive(R);
160    return true;
161  }
162};
163} // end anonymous namespace
164
165// removeDeadBindings:
166//  - Remove subexpression bindings.
167//  - Remove dead block expression bindings.
168//  - Keep live block expression bindings:
169//   - Mark their reachable symbols live in SymbolReaper,
170//     see ScanReachableSymbols.
171//   - Mark the region in DRoots if the binding is a loc::MemRegionVal.
172Environment
173EnvironmentManager::removeDeadBindings(Environment Env,
174                                       SymbolReaper &SymReaper,
175                                       ProgramStateRef ST) {
176
177  // We construct a new Environment object entirely, as this is cheaper than
178  // individually removing all the subexpression bindings (which will greatly
179  // outnumber block-level expression bindings).
180  Environment NewEnv = getInitialEnvironment();
181
182  MarkLiveCallback CB(SymReaper);
183  ScanReachableSymbols RSScaner(ST, CB);
184
185  llvm::ImmutableMapRef<EnvironmentEntry,SVal>
186    EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
187             F.getTreeFactory());
188
189  // Iterate over the block-expr bindings.
190  for (Environment::iterator I = Env.begin(), E = Env.end();
191       I != E; ++I) {
192
193    const EnvironmentEntry &BlkExpr = I.getKey();
194    const SVal &X = I.getData();
195
196    if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
197      // Copy the binding to the new map.
198      EBMapRef = EBMapRef.add(BlkExpr, X);
199
200      // If the block expr's value is a memory region, then mark that region.
201      if (isa<loc::MemRegionVal>(X)) {
202        const MemRegion *R = cast<loc::MemRegionVal>(X).getRegion();
203        SymReaper.markLive(R);
204      }
205
206      // Mark all symbols in the block expr's value live.
207      RSScaner.scan(X);
208      continue;
209    } else {
210      SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
211      for (; SI != SE; ++SI)
212        SymReaper.maybeDead(*SI);
213    }
214  }
215
216  NewEnv.ExprBindings = EBMapRef.asImmutableMap();
217  return NewEnv;
218}
219
220void Environment::print(raw_ostream &Out, const char *NL,
221                        const char *Sep) const {
222  bool isFirst = true;
223
224  for (Environment::iterator I = begin(), E = end(); I != E; ++I) {
225    const EnvironmentEntry &En = I.getKey();
226
227    if (isFirst) {
228      Out << NL << NL
229          << "Expressions:"
230          << NL;
231      isFirst = false;
232    } else {
233      Out << NL;
234    }
235
236    const Stmt *S = En.getStmt();
237
238    Out << " (" << (const void*) En.getLocationContext() << ','
239      << (const void*) S << ") ";
240    LangOptions LO; // FIXME.
241    S->printPretty(Out, 0, PrintingPolicy(LO));
242    Out << " : " << I.getData();
243  }
244}
245