1 //===- Environment.cpp - Map from Stmt* to Locations/Values ---------------===//
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/StaticAnalyzer/Core/PathSensitive/Environment.h"
15 #include "clang/AST/Expr.h"
16 #include "clang/AST/ExprCXX.h"
17 #include "clang/AST/PrettyPrinter.h"
18 #include "clang/AST/Stmt.h"
19 #include "clang/Analysis/AnalysisDeclContext.h"
20 #include "clang/Basic/LLVM.h"
21 #include "clang/Basic/LangOptions.h"
22 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
23 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
24 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
25 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
26 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.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::CXXBindTemporaryExprClass:
48     E = cast<CXXBindTemporaryExpr>(E)->getSubExpr();
49     break;
50   case Stmt::SubstNonTypeTemplateParmExprClass:
51     E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement();
52     break;
53   default:
54     // This is the base case: we can't look through more than we already have.
55     return E;
56   }
57 
58   return ignoreTransparentExprs(E);
59 }
60 
61 static const Stmt *ignoreTransparentExprs(const Stmt *S) {
62   if (const auto *E = dyn_cast<Expr>(S))
63     return ignoreTransparentExprs(E);
64   return S;
65 }
66 
67 EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L)
68     : std::pair<const Stmt *,
69                 const StackFrameContext *>(ignoreTransparentExprs(S),
70                                            L ? L->getStackFrame()
71                                              : nullptr) {}
72 
73 SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
74   const SVal* X = ExprBindings.lookup(E);
75   if (X) {
76     SVal V = *X;
77     return V;
78   }
79   return UnknownVal();
80 }
81 
82 SVal Environment::getSVal(const EnvironmentEntry &Entry,
83                           SValBuilder& svalBuilder) const {
84   const Stmt *S = Entry.getStmt();
85   const LocationContext *LCtx = Entry.getLocationContext();
86 
87   switch (S->getStmtClass()) {
88   case Stmt::CXXBindTemporaryExprClass:
89   case Stmt::ExprWithCleanupsClass:
90   case Stmt::GenericSelectionExprClass:
91   case Stmt::OpaqueValueExprClass:
92   case Stmt::ParenExprClass:
93   case Stmt::SubstNonTypeTemplateParmExprClass:
94     llvm_unreachable("Should have been handled by ignoreTransparentExprs");
95 
96   case Stmt::AddrLabelExprClass:
97   case Stmt::CharacterLiteralClass:
98   case Stmt::CXXBoolLiteralExprClass:
99   case Stmt::CXXScalarValueInitExprClass:
100   case Stmt::ImplicitValueInitExprClass:
101   case Stmt::IntegerLiteralClass:
102   case Stmt::ObjCBoolLiteralExprClass:
103   case Stmt::CXXNullPtrLiteralExprClass:
104   case Stmt::ObjCStringLiteralClass:
105   case Stmt::StringLiteralClass:
106   case Stmt::TypeTraitExprClass:
107     // Known constants; defer to SValBuilder.
108     return svalBuilder.getConstantVal(cast<Expr>(S)).getValue();
109 
110   case Stmt::ReturnStmtClass: {
111     const auto *RS = cast<ReturnStmt>(S);
112     if (const Expr *RE = RS->getRetValue())
113       return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder);
114     return UndefinedVal();
115   }
116 
117   // Handle all other Stmt* using a lookup.
118   default:
119     return lookupExpr(EnvironmentEntry(S, LCtx));
120   }
121 }
122 
123 Environment EnvironmentManager::bindExpr(Environment Env,
124                                          const EnvironmentEntry &E,
125                                          SVal V,
126                                          bool Invalidate) {
127   if (V.isUnknown()) {
128     if (Invalidate)
129       return Environment(F.remove(Env.ExprBindings, E));
130     else
131       return Env;
132   }
133   return Environment(F.add(Env.ExprBindings, E, V));
134 }
135 
136 namespace {
137 
138 class MarkLiveCallback final : public SymbolVisitor {
139   SymbolReaper &SymReaper;
140 
141 public:
142   MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
143 
144   bool VisitSymbol(SymbolRef sym) override {
145     SymReaper.markLive(sym);
146     return true;
147   }
148 
149   bool VisitMemRegion(const MemRegion *R) override {
150     SymReaper.markLive(R);
151     return true;
152   }
153 };
154 
155 } // namespace
156 
157 // removeDeadBindings:
158 //  - Remove subexpression bindings.
159 //  - Remove dead block expression bindings.
160 //  - Keep live block expression bindings:
161 //   - Mark their reachable symbols live in SymbolReaper,
162 //     see ScanReachableSymbols.
163 //   - Mark the region in DRoots if the binding is a loc::MemRegionVal.
164 Environment
165 EnvironmentManager::removeDeadBindings(Environment Env,
166                                        SymbolReaper &SymReaper,
167                                        ProgramStateRef ST) {
168   // We construct a new Environment object entirely, as this is cheaper than
169   // individually removing all the subexpression bindings (which will greatly
170   // outnumber block-level expression bindings).
171   Environment NewEnv = getInitialEnvironment();
172 
173   MarkLiveCallback CB(SymReaper);
174   ScanReachableSymbols RSScaner(ST, CB);
175 
176   llvm::ImmutableMapRef<EnvironmentEntry, SVal>
177     EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
178              F.getTreeFactory());
179 
180   // Iterate over the block-expr bindings.
181   for (Environment::iterator I = Env.begin(), E = Env.end();
182        I != E; ++I) {
183     const EnvironmentEntry &BlkExpr = I.getKey();
184     const SVal &X = I.getData();
185 
186     if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
187       // Copy the binding to the new map.
188       EBMapRef = EBMapRef.add(BlkExpr, X);
189 
190       // Mark all symbols in the block expr's value live.
191       RSScaner.scan(X);
192       continue;
193     } else {
194       SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
195       for (; SI != SE; ++SI)
196         SymReaper.maybeDead(*SI);
197     }
198   }
199 
200   NewEnv.ExprBindings = EBMapRef.asImmutableMap();
201   return NewEnv;
202 }
203 
204 void Environment::print(raw_ostream &Out, const char *NL,
205                         const char *Sep,
206                         const ASTContext &Context,
207                         const LocationContext *WithLC) const {
208   if (ExprBindings.isEmpty())
209     return;
210 
211   if (!WithLC) {
212     // Find the freshest location context.
213     llvm::SmallPtrSet<const LocationContext *, 16> FoundContexts;
214     for (auto I : *this) {
215       const LocationContext *LC = I.first.getLocationContext();
216       if (FoundContexts.count(LC) == 0) {
217         // This context is fresher than all other contexts so far.
218         WithLC = LC;
219         for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent())
220           FoundContexts.insert(LCI);
221       }
222     }
223   }
224 
225   assert(WithLC);
226 
227   PrintingPolicy PP = Context.getPrintingPolicy();
228 
229   Out << NL << "Expressions by stack frame:" << NL;
230   WithLC->dumpStack(Out, "", NL, Sep, [&](const LocationContext *LC) {
231     for (auto I : ExprBindings) {
232       if (I.first.getLocationContext() != LC)
233         continue;
234 
235       const Stmt *S = I.first.getStmt();
236       assert(S != nullptr && "Expected non-null Stmt");
237 
238       Out << "(LC" << LC->getID() << ", S" << S->getID(Context) << ") ";
239       S->printPretty(Out, /*Helper=*/nullptr, PP);
240       Out << " : " << I.second << NL;
241     }
242   });
243 }
244