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/Basic/JsonSupport.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::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 70 EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L) 71 : std::pair<const Stmt *, 72 const StackFrameContext *>(ignoreTransparentExprs(S), 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 85 SVal Environment::getSVal(const EnvironmentEntry &Entry, 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 // Known constants; defer to SValBuilder. 112 return svalBuilder.getConstantVal(cast<Expr>(S)).getValue(); 113 114 case Stmt::ReturnStmtClass: { 115 const auto *RS = cast<ReturnStmt>(S); 116 if (const Expr *RE = RS->getRetValue()) 117 return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder); 118 return UndefinedVal(); 119 } 120 121 // Handle all other Stmt* using a lookup. 122 default: 123 return lookupExpr(EnvironmentEntry(S, LCtx)); 124 } 125 } 126 127 Environment EnvironmentManager::bindExpr(Environment Env, 128 const EnvironmentEntry &E, 129 SVal V, 130 bool Invalidate) { 131 if (V.isUnknown()) { 132 if (Invalidate) 133 return Environment(F.remove(Env.ExprBindings, E)); 134 else 135 return Env; 136 } 137 return Environment(F.add(Env.ExprBindings, E, V)); 138 } 139 140 namespace { 141 142 class MarkLiveCallback final : public SymbolVisitor { 143 SymbolReaper &SymReaper; 144 145 public: 146 MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {} 147 148 bool VisitSymbol(SymbolRef sym) override { 149 SymReaper.markLive(sym); 150 return true; 151 } 152 153 bool VisitMemRegion(const MemRegion *R) override { 154 SymReaper.markLive(R); 155 return true; 156 } 157 }; 158 159 } // namespace 160 161 // removeDeadBindings: 162 // - Remove subexpression bindings. 163 // - Remove dead block expression bindings. 164 // - Keep live block expression bindings: 165 // - Mark their reachable symbols live in SymbolReaper, 166 // see ScanReachableSymbols. 167 // - Mark the region in DRoots if the binding is a loc::MemRegionVal. 168 Environment 169 EnvironmentManager::removeDeadBindings(Environment Env, 170 SymbolReaper &SymReaper, 171 ProgramStateRef ST) { 172 // We construct a new Environment object entirely, as this is cheaper than 173 // individually removing all the subexpression bindings (which will greatly 174 // outnumber block-level expression bindings). 175 Environment NewEnv = getInitialEnvironment(); 176 177 MarkLiveCallback CB(SymReaper); 178 ScanReachableSymbols RSScaner(ST, CB); 179 180 llvm::ImmutableMapRef<EnvironmentEntry, SVal> 181 EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(), 182 F.getTreeFactory()); 183 184 // Iterate over the block-expr bindings. 185 for (Environment::iterator I = Env.begin(), E = Env.end(); 186 I != E; ++I) { 187 const EnvironmentEntry &BlkExpr = I.getKey(); 188 const SVal &X = I.getData(); 189 190 if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) { 191 // Copy the binding to the new map. 192 EBMapRef = EBMapRef.add(BlkExpr, X); 193 194 // Mark all symbols in the block expr's value live. 195 RSScaner.scan(X); 196 } 197 } 198 199 NewEnv.ExprBindings = EBMapRef.asImmutableMap(); 200 return NewEnv; 201 } 202 203 void Environment::printJson(raw_ostream &Out, const ASTContext &Ctx, 204 const LocationContext *LCtx, const char *NL, 205 unsigned int Space, bool IsDot) const { 206 Indent(Out, Space, IsDot) << "\"environment\": "; 207 208 if (ExprBindings.isEmpty()) { 209 Out << "null," << NL; 210 return; 211 } 212 213 ++Space; 214 if (!LCtx) { 215 // Find the freshest location context. 216 llvm::SmallPtrSet<const LocationContext *, 16> FoundContexts; 217 for (const auto &I : *this) { 218 const LocationContext *LC = I.first.getLocationContext(); 219 if (FoundContexts.count(LC) == 0) { 220 // This context is fresher than all other contexts so far. 221 LCtx = LC; 222 for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent()) 223 FoundContexts.insert(LCI); 224 } 225 } 226 } 227 228 assert(LCtx); 229 230 Out << "{ \"pointer\": \"" << (const void *)LCtx->getStackFrame() 231 << "\", \"items\": [" << NL; 232 PrintingPolicy PP = Ctx.getPrintingPolicy(); 233 234 LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) { 235 // LCtx items begin 236 bool HasItem = false; 237 unsigned int InnerSpace = Space + 1; 238 239 // Store the last ExprBinding which we will print. 240 BindingsTy::iterator LastI = ExprBindings.end(); 241 for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end(); 242 ++I) { 243 if (I->first.getLocationContext() != LC) 244 continue; 245 246 if (!HasItem) { 247 HasItem = true; 248 Out << '[' << NL; 249 } 250 251 const Stmt *S = I->first.getStmt(); 252 (void)S; 253 assert(S != nullptr && "Expected non-null Stmt"); 254 255 LastI = I; 256 } 257 258 for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end(); 259 ++I) { 260 if (I->first.getLocationContext() != LC) 261 continue; 262 263 const Stmt *S = I->first.getStmt(); 264 Indent(Out, InnerSpace, IsDot) 265 << "{ \"stmt_id\": " << S->getID(Ctx) << ", \"pretty\": "; 266 S->printJson(Out, nullptr, PP, /*AddQuotes=*/true); 267 268 Out << ", \"value\": "; 269 I->second.printJson(Out, /*AddQuotes=*/true); 270 271 Out << " }"; 272 273 if (I != LastI) 274 Out << ','; 275 Out << NL; 276 } 277 278 if (HasItem) 279 Indent(Out, --InnerSpace, IsDot) << ']'; 280 else 281 Out << "null "; 282 }); 283 284 Indent(Out, --Space, IsDot) << "]}," << NL; 285 } 286