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()
58                                           : nullptr) {}
59
60SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
61  const SVal* X = ExprBindings.lookup(E);
62  if (X) {
63    SVal V = *X;
64    return V;
65  }
66  return UnknownVal();
67}
68
69SVal Environment::getSVal(const EnvironmentEntry &Entry,
70                          SValBuilder& svalBuilder) const {
71  const Stmt *S = Entry.getStmt();
72  const LocationContext *LCtx = Entry.getLocationContext();
73
74  switch (S->getStmtClass()) {
75  case Stmt::CXXBindTemporaryExprClass:
76  case Stmt::ExprWithCleanupsClass:
77  case Stmt::GenericSelectionExprClass:
78  case Stmt::OpaqueValueExprClass:
79  case Stmt::ParenExprClass:
80  case Stmt::SubstNonTypeTemplateParmExprClass:
81    llvm_unreachable("Should have been handled by ignoreTransparentExprs");
82
83  case Stmt::AddrLabelExprClass:
84  case Stmt::CharacterLiteralClass:
85  case Stmt::CXXBoolLiteralExprClass:
86  case Stmt::CXXScalarValueInitExprClass:
87  case Stmt::ImplicitValueInitExprClass:
88  case Stmt::IntegerLiteralClass:
89  case Stmt::ObjCBoolLiteralExprClass:
90  case Stmt::CXXNullPtrLiteralExprClass:
91  case Stmt::ObjCStringLiteralClass:
92  case Stmt::StringLiteralClass:
93    // Known constants; defer to SValBuilder.
94    return svalBuilder.getConstantVal(cast<Expr>(S)).getValue();
95
96  case Stmt::ReturnStmtClass: {
97    const ReturnStmt *RS = cast<ReturnStmt>(S);
98    if (const Expr *RE = RS->getRetValue())
99      return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder);
100    return UndefinedVal();
101  }
102
103  // Handle all other Stmt* using a lookup.
104  default:
105    return lookupExpr(EnvironmentEntry(S, LCtx));
106  }
107}
108
109Environment EnvironmentManager::bindExpr(Environment Env,
110                                         const EnvironmentEntry &E,
111                                         SVal V,
112                                         bool Invalidate) {
113  if (V.isUnknown()) {
114    if (Invalidate)
115      return Environment(F.remove(Env.ExprBindings, E));
116    else
117      return Env;
118  }
119  return Environment(F.add(Env.ExprBindings, E, V));
120}
121
122namespace {
123class MarkLiveCallback : public SymbolVisitor {
124  SymbolReaper &SymReaper;
125public:
126  MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
127  bool VisitSymbol(SymbolRef sym) override {
128    SymReaper.markLive(sym);
129    return true;
130  }
131  bool VisitMemRegion(const MemRegion *R) override {
132    SymReaper.markLive(R);
133    return true;
134  }
135};
136} // end anonymous namespace
137
138// removeDeadBindings:
139//  - Remove subexpression bindings.
140//  - Remove dead block expression bindings.
141//  - Keep live block expression bindings:
142//   - Mark their reachable symbols live in SymbolReaper,
143//     see ScanReachableSymbols.
144//   - Mark the region in DRoots if the binding is a loc::MemRegionVal.
145Environment
146EnvironmentManager::removeDeadBindings(Environment Env,
147                                       SymbolReaper &SymReaper,
148                                       ProgramStateRef ST) {
149
150  // We construct a new Environment object entirely, as this is cheaper than
151  // individually removing all the subexpression bindings (which will greatly
152  // outnumber block-level expression bindings).
153  Environment NewEnv = getInitialEnvironment();
154
155  MarkLiveCallback CB(SymReaper);
156  ScanReachableSymbols RSScaner(ST, CB);
157
158  llvm::ImmutableMapRef<EnvironmentEntry,SVal>
159    EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
160             F.getTreeFactory());
161
162  // Iterate over the block-expr bindings.
163  for (Environment::iterator I = Env.begin(), E = Env.end();
164       I != E; ++I) {
165
166    const EnvironmentEntry &BlkExpr = I.getKey();
167    const SVal &X = I.getData();
168
169    if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
170      // Copy the binding to the new map.
171      EBMapRef = EBMapRef.add(BlkExpr, X);
172
173      // If the block expr's value is a memory region, then mark that region.
174      if (Optional<loc::MemRegionVal> R = X.getAs<loc::MemRegionVal>())
175        SymReaper.markLive(R->getRegion());
176
177      // Mark all symbols in the block expr's value live.
178      RSScaner.scan(X);
179      continue;
180    } else {
181      SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
182      for (; SI != SE; ++SI)
183        SymReaper.maybeDead(*SI);
184    }
185  }
186
187  NewEnv.ExprBindings = EBMapRef.asImmutableMap();
188  return NewEnv;
189}
190
191void Environment::print(raw_ostream &Out, const char *NL,
192                        const char *Sep) const {
193  bool isFirst = true;
194
195  for (Environment::iterator I = begin(), E = end(); I != E; ++I) {
196    const EnvironmentEntry &En = I.getKey();
197
198    if (isFirst) {
199      Out << NL << NL
200          << "Expressions:"
201          << NL;
202      isFirst = false;
203    } else {
204      Out << NL;
205    }
206
207    const Stmt *S = En.getStmt();
208    assert(S != nullptr && "Expected non-null Stmt");
209
210    Out << " (" << (const void*) En.getLocationContext() << ','
211      << (const void*) S << ") ";
212    LangOptions LO; // FIXME.
213    S->printPretty(Out, nullptr, PrintingPolicy(LO));
214    Out << " : " << I.getData();
215  }
216}
217