clang  10.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"
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 
71  : std::pair<const Stmt *,
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 
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::ConstantExprClass:
96  case Stmt::ParenExprClass:
97  case Stmt::SubstNonTypeTemplateParmExprClass:
98  llvm_unreachable("Should have been handled by ignoreTransparentExprs");
99 
100  case Stmt::AddrLabelExprClass:
101  case Stmt::CharacterLiteralClass:
102  case Stmt::CXXBoolLiteralExprClass:
103  case Stmt::CXXScalarValueInitExprClass:
104  case Stmt::ImplicitValueInitExprClass:
105  case Stmt::IntegerLiteralClass:
106  case Stmt::ObjCBoolLiteralExprClass:
107  case Stmt::CXXNullPtrLiteralExprClass:
108  case Stmt::ObjCStringLiteralClass:
109  case Stmt::StringLiteralClass:
110  case Stmt::TypeTraitExprClass:
111  case Stmt::SizeOfPackExprClass:
112  // Known constants; defer to SValBuilder.
113  return svalBuilder.getConstantVal(cast<Expr>(S)).getValue();
114 
115  case Stmt::ReturnStmtClass: {
116  const auto *RS = cast<ReturnStmt>(S);
117  if (const Expr *RE = RS->getRetValue())
118  return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder);
119  return UndefinedVal();
120  }
121 
122  // Handle all other Stmt* using a lookup.
123  default:
124  return lookupExpr(EnvironmentEntry(S, LCtx));
125  }
126 }
127 
129  const EnvironmentEntry &E,
130  SVal V,
131  bool Invalidate) {
132  if (V.isUnknown()) {
133  if (Invalidate)
134  return Environment(F.remove(Env.ExprBindings, E));
135  else
136  return Env;
137  }
138  return Environment(F.add(Env.ExprBindings, E, V));
139 }
140 
141 namespace {
142 
143 class MarkLiveCallback final : public SymbolVisitor {
144  SymbolReaper &SymReaper;
145 
146 public:
147  MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
148 
149  bool VisitSymbol(SymbolRef sym) override {
150  SymReaper.markLive(sym);
151  return true;
152  }
153 
154  bool VisitMemRegion(const MemRegion *R) override {
155  SymReaper.markLive(R);
156  return true;
157  }
158 };
159 
160 } // namespace
161 
162 // removeDeadBindings:
163 // - Remove subexpression bindings.
164 // - Remove dead block expression bindings.
165 // - Keep live block expression bindings:
166 // - Mark their reachable symbols live in SymbolReaper,
167 // see ScanReachableSymbols.
168 // - Mark the region in DRoots if the binding is a loc::MemRegionVal.
171  SymbolReaper &SymReaper,
172  ProgramStateRef ST) {
173  // We construct a new Environment object entirely, as this is cheaper than
174  // individually removing all the subexpression bindings (which will greatly
175  // outnumber block-level expression bindings).
176  Environment NewEnv = getInitialEnvironment();
177 
178  MarkLiveCallback CB(SymReaper);
179  ScanReachableSymbols RSScaner(ST, CB);
180 
181  llvm::ImmutableMapRef<EnvironmentEntry, SVal>
182  EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
183  F.getTreeFactory());
184 
185  // Iterate over the block-expr bindings.
186  for (Environment::iterator I = Env.begin(), E = Env.end();
187  I != E; ++I) {
188  const EnvironmentEntry &BlkExpr = I.getKey();
189  const SVal &X = I.getData();
190 
191  if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
192  // Copy the binding to the new map.
193  EBMapRef = EBMapRef.add(BlkExpr, X);
194 
195  // Mark all symbols in the block expr's value live.
196  RSScaner.scan(X);
197  }
198  }
199 
200  NewEnv.ExprBindings = EBMapRef.asImmutableMap();
201  return NewEnv;
202 }
203 
204 void Environment::printJson(raw_ostream &Out, const ASTContext &Ctx,
205  const LocationContext *LCtx, const char *NL,
206  unsigned int Space, bool IsDot) const {
207  Indent(Out, Space, IsDot) << "\"environment\": ";
208 
209  if (ExprBindings.isEmpty()) {
210  Out << "null," << NL;
211  return;
212  }
213 
214  ++Space;
215  if (!LCtx) {
216  // Find the freshest location context.
217  llvm::SmallPtrSet<const LocationContext *, 16> FoundContexts;
218  for (const auto &I : *this) {
219  const LocationContext *LC = I.first.getLocationContext();
220  if (FoundContexts.count(LC) == 0) {
221  // This context is fresher than all other contexts so far.
222  LCtx = LC;
223  for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent())
224  FoundContexts.insert(LCI);
225  }
226  }
227  }
228 
229  assert(LCtx);
230 
231  Out << "{ \"pointer\": \"" << (const void *)LCtx->getStackFrame()
232  << "\", \"items\": [" << NL;
234 
235  LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) {
236  // LCtx items begin
237  bool HasItem = false;
238  unsigned int InnerSpace = Space + 1;
239 
240  // Store the last ExprBinding which we will print.
241  BindingsTy::iterator LastI = ExprBindings.end();
242  for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end();
243  ++I) {
244  if (I->first.getLocationContext() != LC)
245  continue;
246 
247  if (!HasItem) {
248  HasItem = true;
249  Out << '[' << NL;
250  }
251 
252  const Stmt *S = I->first.getStmt();
253  (void)S;
254  assert(S != nullptr && "Expected non-null Stmt");
255 
256  LastI = I;
257  }
258 
259  for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end();
260  ++I) {
261  if (I->first.getLocationContext() != LC)
262  continue;
263 
264  const Stmt *S = I->first.getStmt();
265  Indent(Out, InnerSpace, IsDot)
266  << "{ \"stmt_id\": " << S->getID(Ctx) << ", \"pretty\": ";
267  S->printJson(Out, nullptr, PP, /*AddQuotes=*/true);
268 
269  Out << ", \"value\": ";
270  I->second.printJson(Out, /*AddQuotes=*/true);
271 
272  Out << " }";
273 
274  if (I != LastI)
275  Out << ',';
276  Out << NL;
277  }
278 
279  if (HasItem)
280  Indent(Out, --InnerSpace, IsDot) << ']';
281  else
282  Out << "null ";
283  });
284 
285  Indent(Out, --Space, IsDot) << "]}," << NL;
286 }
EnvironmentEntry(const Stmt *s, const LocationContext *L)
Definition: Environment.cpp:70
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:94
Stmt - This represents one statement.
Definition: Stmt.h:66
A utility class that visits the reachable symbols using a custom SymbolVisitor.
Definition: ProgramState.h:857
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:160
void printJson(raw_ostream &Out, PrinterHelper *Helper, const PrintingPolicy &Policy, bool AddQuotes) const
Pretty-prints in JSON format.
Definition: Format.h:2327
Environment bindExpr(Environment Env, const EnvironmentEntry &E, SVal V, bool Invalidate)
Bind a symbolic value to the given environment entry.
void printJson(raw_ostream &Out, const ASTContext &Ctx, const LocationContext *LCtx=nullptr, const char *NL="\, unsigned int Space=0, bool IsDot=false) const
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
static const Expr * ignoreTransparentExprs(const Expr *E)
Definition: Environment.cpp:37
const clang::PrintingPolicy & getPrintingPolicy() const
Definition: ASTContext.h:667
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.
#define V(N, I)
Definition: ASTContext.h:2913
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:85
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:299
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:1087
const StackFrameContext * getStackFrame() const
void printJson(raw_ostream &Out, const char *NL="\, unsigned int Space=0, bool IsDot=false, std::function< void(const LocationContext *)> printMoreInfoPerContext=[](const LocationContext *) {}) const
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:14584
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)
raw_ostream & Indent(raw_ostream &Out, const unsigned int Space, bool IsDot)
Definition: JsonSupport.h:20
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:2962
const LocationContext * getLocationContext() const
Definition: Environment.h:41