clang  9.0.0svn
Environment.cpp
Go to the documentation of this file.
1 //===- Environment.cpp - Map from Stmt* to Locations/Values ---------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defined the Environment and EnvironmentManager classes.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "clang/AST/Expr.h"
15 #include "clang/AST/ExprCXX.h"
17 #include "clang/AST/Stmt.h"
19 #include "clang/Basic/LLVM.h"
26 #include "llvm/ADT/ImmutableMap.h"
27 #include "llvm/ADT/SmallPtrSet.h"
28 #include "llvm/Support/Casting.h"
29 #include "llvm/Support/ErrorHandling.h"
30 #include "llvm/Support/raw_ostream.h"
31 #include <cassert>
32 
33 using namespace clang;
34 using namespace ento;
35 
36 static const Expr *ignoreTransparentExprs(const Expr *E) {
37  E = E->IgnoreParens();
38 
39  switch (E->getStmtClass()) {
40  case Stmt::OpaqueValueExprClass:
41  E = cast<OpaqueValueExpr>(E)->getSourceExpr();
42  break;
43  case Stmt::ExprWithCleanupsClass:
44  E = cast<ExprWithCleanups>(E)->getSubExpr();
45  break;
46  case Stmt::ConstantExprClass:
47  E = cast<ConstantExpr>(E)->getSubExpr();
48  break;
49  case Stmt::CXXBindTemporaryExprClass:
50  E = cast<CXXBindTemporaryExpr>(E)->getSubExpr();
51  break;
52  case Stmt::SubstNonTypeTemplateParmExprClass:
53  E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement();
54  break;
55  default:
56  // This is the base case: we can't look through more than we already have.
57  return E;
58  }
59 
60  return ignoreTransparentExprs(E);
61 }
62 
63 static const Stmt *ignoreTransparentExprs(const Stmt *S) {
64  if (const auto *E = dyn_cast<Expr>(S))
65  return ignoreTransparentExprs(E);
66  return S;
67 }
68 
70  : std::pair<const Stmt *,
72  L ? L->getStackFrame()
73  : nullptr) {}
74 
75 SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
76  const SVal* X = ExprBindings.lookup(E);
77  if (X) {
78  SVal V = *X;
79  return V;
80  }
81  return UnknownVal();
82 }
83 
85  SValBuilder& svalBuilder) const {
86  const Stmt *S = Entry.getStmt();
87  const LocationContext *LCtx = Entry.getLocationContext();
88 
89  switch (S->getStmtClass()) {
90  case Stmt::CXXBindTemporaryExprClass:
91  case Stmt::ExprWithCleanupsClass:
92  case Stmt::GenericSelectionExprClass:
93  case Stmt::OpaqueValueExprClass:
94  case Stmt::ConstantExprClass:
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 
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.
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  }
196  }
197 
198  NewEnv.ExprBindings = EBMapRef.asImmutableMap();
199  return NewEnv;
200 }
201 
202 void Environment::print(raw_ostream &Out, const char *NL,
203  const char *Sep,
204  const ASTContext &Context,
205  const LocationContext *WithLC) const {
206  if (ExprBindings.isEmpty())
207  return;
208 
209  if (!WithLC) {
210  // Find the freshest location context.
211  llvm::SmallPtrSet<const LocationContext *, 16> FoundContexts;
212  for (auto I : *this) {
213  const LocationContext *LC = I.first.getLocationContext();
214  if (FoundContexts.count(LC) == 0) {
215  // This context is fresher than all other contexts so far.
216  WithLC = LC;
217  for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent())
218  FoundContexts.insert(LCI);
219  }
220  }
221  }
222 
223  assert(WithLC);
224 
225  PrintingPolicy PP = Context.getPrintingPolicy();
226 
227  Out << NL << "Expressions by stack frame:" << NL;
228  WithLC->dumpStack(Out, "", NL, Sep, [&](const LocationContext *LC) {
229  for (auto I : ExprBindings) {
230  if (I.first.getLocationContext() != LC)
231  continue;
232 
233  const Stmt *S = I.first.getStmt();
234  assert(S != nullptr && "Expected non-null Stmt");
235 
236  Out << "(LC" << LC->getID() << ", S" << S->getID(Context) << ") ";
237  S->printPretty(Out, /*Helper=*/nullptr, PP);
238  Out << " : " << I.second << NL;
239  }
240  });
241 }
EnvironmentEntry(const Stmt *s, const LocationContext *L)
Definition: Environment.cpp:69
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:94
Stmt - This represents one statement.
Definition: Stmt.h:65
A utility class that visits the reachable symbols using a custom SymbolVisitor.
Definition: ProgramState.h:892
Describes how types, statements, expressions, and declarations should be printed. ...
Definition: PrettyPrinter.h:37
Defines the clang::Expr interface and subclasses for C++ expressions.
Symbolic value.
Definition: SymExpr.h:29
const Stmt * getStmt() const
Definition: Environment.h:40
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:154
Definition: Format.h:2153
void dumpStack(raw_ostream &OS, StringRef Indent={}, const char *NL="\, const char *Sep="", std::function< void(const LocationContext *)> printMoreInfoPerContext=[](const LocationContext *) {}) const
Environment bindExpr(Environment Env, const EnvironmentEntry &E, SVal V, bool Invalidate)
Bind a symbolic value to the given environment entry.
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
static const Expr * ignoreTransparentExprs(const Expr *E)
Definition: Environment.cpp:36
const clang::PrintingPolicy & getPrintingPolicy() const
Definition: ASTContext.h:653
iterator end() const
Definition: Environment.h:72
const LocationContext * getParent() const
bool isUnknown() const
Definition: SVals.h:136
iterator begin() const
Definition: Environment.h:71
BindingsTy::iterator iterator
Definition: Environment.h:69
This represents one expression.
Definition: Expr.h:108
Defines the clang::LangOptions interface.
void print(raw_ostream &Out, const char *NL, const char *Sep, const ASTContext &Context, const LocationContext *WithLC=nullptr) const
bool scan(nonloc::LazyCompoundVal val)
SVal getSVal(const EnvironmentEntry &E, SValBuilder &svalBuilder) const
Fetches the current binding of the expression in the Environment.
Definition: Environment.cpp:84
An entry in the environment consists of a Stmt and an LocationContext.
Definition: Environment.h:35
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:75
int64_t getID(const ASTContext &Context) const
Definition: Stmt.cpp:288
A class responsible for cleaning up unused symbols.
An immutable map from EnvironemntEntries to SVals.
Definition: Environment.h:56
Dataflow Directional Tag Classes.
StmtClass getStmtClass() const
Definition: Stmt.h:1041
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:14015
void printPretty(raw_ostream &OS, PrinterHelper *Helper, const PrintingPolicy &Policy, unsigned Indentation=0, StringRef NewlineSymbol="\, const ASTContext *Context=nullptr) const
Optional< SVal > getConstantVal(const Expr *E)
Returns the value of E, if it can be determined in a non-path-sensitive manner.
Environment removeDeadBindings(Environment Env, SymbolReaper &SymReaper, ProgramStateRef state)
bool isLive(SymbolRef sym)
Expr * IgnoreParens() LLVM_READONLY
Skip past any parentheses which might surround this expression until reaching a fixed point...
Definition: Expr.cpp:2719
const LocationContext * getLocationContext() const
Definition: Environment.h:41