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/AST/StmtObjC.h" 19 #include "clang/Analysis/AnalysisDeclContext.h" 20 #include "clang/Basic/JsonSupport.h" 21 #include "clang/Basic/LLVM.h" 22 #include "clang/Basic/LangOptions.h" 23 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 24 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 25 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 26 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" 27 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 28 #include "llvm/ADT/ImmutableMap.h" 29 #include "llvm/ADT/SmallPtrSet.h" 30 #include "llvm/Support/Casting.h" 31 #include "llvm/Support/ErrorHandling.h" 32 #include "llvm/Support/raw_ostream.h" 33 #include <cassert> 34 35 using namespace clang; 36 using namespace ento; 37 38 static const Expr *ignoreTransparentExprs(const Expr *E) { 39 E = E->IgnoreParens(); 40 41 switch (E->getStmtClass()) { 42 case Stmt::OpaqueValueExprClass: 43 if (const Expr *SE = cast<OpaqueValueExpr>(E)->getSourceExpr()) { 44 E = SE; 45 break; 46 } 47 return E; 48 case Stmt::ExprWithCleanupsClass: 49 E = cast<ExprWithCleanups>(E)->getSubExpr(); 50 break; 51 case Stmt::ConstantExprClass: 52 E = cast<ConstantExpr>(E)->getSubExpr(); 53 break; 54 case Stmt::CXXBindTemporaryExprClass: 55 E = cast<CXXBindTemporaryExpr>(E)->getSubExpr(); 56 break; 57 case Stmt::SubstNonTypeTemplateParmExprClass: 58 E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement(); 59 break; 60 default: 61 // This is the base case: we can't look through more than we already have. 62 return E; 63 } 64 65 return ignoreTransparentExprs(E); 66 } 67 68 static const Stmt *ignoreTransparentExprs(const Stmt *S) { 69 if (const auto *E = dyn_cast<Expr>(S)) 70 return ignoreTransparentExprs(E); 71 return S; 72 } 73 74 EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L) 75 : std::pair<const Stmt *, 76 const StackFrameContext *>(ignoreTransparentExprs(S), 77 L ? L->getStackFrame() 78 : nullptr) {} 79 80 SVal Environment::lookupExpr(const EnvironmentEntry &E) const { 81 const SVal* X = ExprBindings.lookup(E); 82 if (X) { 83 SVal V = *X; 84 return V; 85 } 86 return UnknownVal(); 87 } 88 89 SVal Environment::getSVal(const EnvironmentEntry &Entry, 90 SValBuilder& svalBuilder) const { 91 const Stmt *S = Entry.getStmt(); 92 assert(!isa<ObjCForCollectionStmt>(S) && 93 "Use ExprEngine::hasMoreIteration()!"); 94 assert((isa<Expr, ReturnStmt>(S)) && 95 "Environment can only argue about Exprs, since only they express " 96 "a value! Any non-expression statement stored in Environment is a " 97 "result of a hack!"); 98 const LocationContext *LCtx = Entry.getLocationContext(); 99 100 switch (S->getStmtClass()) { 101 case Stmt::CXXBindTemporaryExprClass: 102 case Stmt::ExprWithCleanupsClass: 103 case Stmt::GenericSelectionExprClass: 104 case Stmt::ConstantExprClass: 105 case Stmt::ParenExprClass: 106 case Stmt::SubstNonTypeTemplateParmExprClass: 107 llvm_unreachable("Should have been handled by ignoreTransparentExprs"); 108 109 case Stmt::AddrLabelExprClass: 110 case Stmt::CharacterLiteralClass: 111 case Stmt::CXXBoolLiteralExprClass: 112 case Stmt::CXXScalarValueInitExprClass: 113 case Stmt::ImplicitValueInitExprClass: 114 case Stmt::IntegerLiteralClass: 115 case Stmt::ObjCBoolLiteralExprClass: 116 case Stmt::CXXNullPtrLiteralExprClass: 117 case Stmt::ObjCStringLiteralClass: 118 case Stmt::StringLiteralClass: 119 case Stmt::TypeTraitExprClass: 120 case Stmt::SizeOfPackExprClass: 121 case Stmt::PredefinedExprClass: 122 // Known constants; defer to SValBuilder. 123 return *svalBuilder.getConstantVal(cast<Expr>(S)); 124 125 case Stmt::ReturnStmtClass: { 126 const auto *RS = cast<ReturnStmt>(S); 127 if (const Expr *RE = RS->getRetValue()) 128 return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder); 129 return UndefinedVal(); 130 } 131 132 // Handle all other Stmt* using a lookup. 133 default: 134 return lookupExpr(EnvironmentEntry(S, LCtx)); 135 } 136 } 137 138 Environment EnvironmentManager::bindExpr(Environment Env, 139 const EnvironmentEntry &E, 140 SVal V, 141 bool Invalidate) { 142 if (V.isUnknown()) { 143 if (Invalidate) 144 return Environment(F.remove(Env.ExprBindings, E)); 145 else 146 return Env; 147 } 148 return Environment(F.add(Env.ExprBindings, E, V)); 149 } 150 151 namespace { 152 153 class MarkLiveCallback final : public SymbolVisitor { 154 SymbolReaper &SymReaper; 155 156 public: 157 MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {} 158 159 bool VisitSymbol(SymbolRef sym) override { 160 SymReaper.markLive(sym); 161 return true; 162 } 163 164 bool VisitMemRegion(const MemRegion *R) override { 165 SymReaper.markLive(R); 166 return true; 167 } 168 }; 169 170 } // namespace 171 172 // removeDeadBindings: 173 // - Remove subexpression bindings. 174 // - Remove dead block expression bindings. 175 // - Keep live block expression bindings: 176 // - Mark their reachable symbols live in SymbolReaper, 177 // see ScanReachableSymbols. 178 // - Mark the region in DRoots if the binding is a loc::MemRegionVal. 179 Environment 180 EnvironmentManager::removeDeadBindings(Environment Env, 181 SymbolReaper &SymReaper, 182 ProgramStateRef ST) { 183 // We construct a new Environment object entirely, as this is cheaper than 184 // individually removing all the subexpression bindings (which will greatly 185 // outnumber block-level expression bindings). 186 Environment NewEnv = getInitialEnvironment(); 187 188 MarkLiveCallback CB(SymReaper); 189 ScanReachableSymbols RSScaner(ST, CB); 190 191 llvm::ImmutableMapRef<EnvironmentEntry, SVal> 192 EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(), 193 F.getTreeFactory()); 194 195 // Iterate over the block-expr bindings. 196 for (Environment::iterator I = Env.begin(), End = Env.end(); I != End; ++I) { 197 const EnvironmentEntry &BlkExpr = I.getKey(); 198 SVal X = I.getData(); 199 200 const Expr *E = dyn_cast<Expr>(BlkExpr.getStmt()); 201 if (!E) 202 continue; 203 204 if (SymReaper.isLive(E, BlkExpr.getLocationContext())) { 205 // Copy the binding to the new map. 206 EBMapRef = EBMapRef.add(BlkExpr, X); 207 208 // Mark all symbols in the block expr's value live. 209 RSScaner.scan(X); 210 } 211 } 212 213 NewEnv.ExprBindings = EBMapRef.asImmutableMap(); 214 return NewEnv; 215 } 216 217 void Environment::printJson(raw_ostream &Out, const ASTContext &Ctx, 218 const LocationContext *LCtx, const char *NL, 219 unsigned int Space, bool IsDot) const { 220 Indent(Out, Space, IsDot) << "\"environment\": "; 221 222 if (ExprBindings.isEmpty()) { 223 Out << "null," << NL; 224 return; 225 } 226 227 ++Space; 228 if (!LCtx) { 229 // Find the freshest location context. 230 llvm::SmallPtrSet<const LocationContext *, 16> FoundContexts; 231 for (const auto &I : *this) { 232 const LocationContext *LC = I.first.getLocationContext(); 233 if (FoundContexts.count(LC) == 0) { 234 // This context is fresher than all other contexts so far. 235 LCtx = LC; 236 for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent()) 237 FoundContexts.insert(LCI); 238 } 239 } 240 } 241 242 assert(LCtx); 243 244 Out << "{ \"pointer\": \"" << (const void *)LCtx->getStackFrame() 245 << "\", \"items\": [" << NL; 246 PrintingPolicy PP = Ctx.getPrintingPolicy(); 247 248 LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) { 249 // LCtx items begin 250 bool HasItem = false; 251 unsigned int InnerSpace = Space + 1; 252 253 // Store the last ExprBinding which we will print. 254 BindingsTy::iterator LastI = ExprBindings.end(); 255 for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end(); 256 ++I) { 257 if (I->first.getLocationContext() != LC) 258 continue; 259 260 if (!HasItem) { 261 HasItem = true; 262 Out << '[' << NL; 263 } 264 265 const Stmt *S = I->first.getStmt(); 266 (void)S; 267 assert(S != nullptr && "Expected non-null Stmt"); 268 269 LastI = I; 270 } 271 272 for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end(); 273 ++I) { 274 if (I->first.getLocationContext() != LC) 275 continue; 276 277 const Stmt *S = I->first.getStmt(); 278 Indent(Out, InnerSpace, IsDot) 279 << "{ \"stmt_id\": " << S->getID(Ctx) << ", \"kind\": \"" 280 << S->getStmtClassName() << "\", \"pretty\": "; 281 S->printJson(Out, nullptr, PP, /*AddQuotes=*/true); 282 283 Out << ", \"value\": "; 284 I->second.printJson(Out, /*AddQuotes=*/true); 285 286 Out << " }"; 287 288 if (I != LastI) 289 Out << ','; 290 Out << NL; 291 } 292 293 if (HasItem) 294 Indent(Out, --InnerSpace, IsDot) << ']'; 295 else 296 Out << "null "; 297 }); 298 299 Indent(Out, --Space, IsDot) << "]}," << NL; 300 } 301