Clang Project

clang_source_code/lib/StaticAnalyzer/Core/Environment.cpp
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
13#include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h"
14#include "clang/AST/Expr.h"
15#include "clang/AST/ExprCXX.h"
16#include "clang/AST/PrettyPrinter.h"
17#include "clang/AST/Stmt.h"
18#include "clang/Analysis/AnalysisDeclContext.h"
19#include "clang/Basic/LLVM.h"
20#include "clang/Basic/LangOptions.h"
21#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
22#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
24#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
25#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.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
33using namespace clang;
34using namespace ento;
35
36static 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
63static const Stmt *ignoreTransparentExprs(const Stmt *S) {
64  if (const auto *E = dyn_cast<Expr>(S))
65    return ignoreTransparentExprs(E);
66  return S;
67}
68
69EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L)
70    : std::pair<const Stmt *,
71                const StackFrameContext *>(ignoreTransparentExprs(S),
72                                           L ? L->getStackFrame()
73                                             : nullptr) {}
74
75SVal 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
84SVal Environment::getSVal(const EnvironmentEntry &Entry,
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
126Environment EnvironmentManager::bindExpr(Environment Env,
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
139namespace {
140
141class MarkLiveCallback final : public SymbolVisitor {
142  SymbolReaper &SymReaper;
143
144public:
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.
167Environment
168EnvironmentManager::removeDeadBindings(Environment Env,
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
202void 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       (0) . __assert_fail ("S != nullptr && \"Expected non-null Stmt\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/Environment.cpp", 234, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">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}
242
clang::ento::Environment::lookupExpr
clang::ento::Environment::getSVal
clang::ento::EnvironmentManager::bindExpr
clang::ento::EnvironmentManager::removeDeadBindings
clang::ento::Environment::print
CodeThinker, Enjoy your reading code