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 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 128 Environment EnvironmentManager::bindExpr(Environment Env, 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. 169 Environment 170 EnvironmentManager::removeDeadBindings(Environment Env, 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(); I != E; ++I) { 187 const EnvironmentEntry &BlkExpr = I.getKey(); 188 const SVal &X = I.getData(); 189 190 const bool IsBlkExprLive = 191 SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext()); 192 193 assert((isa<Expr>(BlkExpr.getStmt()) || !IsBlkExprLive) && 194 "Only Exprs can be live, LivenessAnalysis argues about the liveness " 195 "of *values*!"); 196 197 if (IsBlkExprLive) { 198 // Copy the binding to the new map. 199 EBMapRef = EBMapRef.add(BlkExpr, X); 200 201 // Mark all symbols in the block expr's value live. 202 RSScaner.scan(X); 203 } 204 } 205 206 NewEnv.ExprBindings = EBMapRef.asImmutableMap(); 207 return NewEnv; 208 } 209 210 void Environment::printJson(raw_ostream &Out, const ASTContext &Ctx, 211 const LocationContext *LCtx, const char *NL, 212 unsigned int Space, bool IsDot) const { 213 Indent(Out, Space, IsDot) << "\"environment\": "; 214 215 if (ExprBindings.isEmpty()) { 216 Out << "null," << NL; 217 return; 218 } 219 220 ++Space; 221 if (!LCtx) { 222 // Find the freshest location context. 223 llvm::SmallPtrSet<const LocationContext *, 16> FoundContexts; 224 for (const auto &I : *this) { 225 const LocationContext *LC = I.first.getLocationContext(); 226 if (FoundContexts.count(LC) == 0) { 227 // This context is fresher than all other contexts so far. 228 LCtx = LC; 229 for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent()) 230 FoundContexts.insert(LCI); 231 } 232 } 233 } 234 235 assert(LCtx); 236 237 Out << "{ \"pointer\": \"" << (const void *)LCtx->getStackFrame() 238 << "\", \"items\": [" << NL; 239 PrintingPolicy PP = Ctx.getPrintingPolicy(); 240 241 LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) { 242 // LCtx items begin 243 bool HasItem = false; 244 unsigned int InnerSpace = Space + 1; 245 246 // Store the last ExprBinding which we will print. 247 BindingsTy::iterator LastI = ExprBindings.end(); 248 for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end(); 249 ++I) { 250 if (I->first.getLocationContext() != LC) 251 continue; 252 253 if (!HasItem) { 254 HasItem = true; 255 Out << '[' << NL; 256 } 257 258 const Stmt *S = I->first.getStmt(); 259 (void)S; 260 assert(S != nullptr && "Expected non-null Stmt"); 261 262 LastI = I; 263 } 264 265 for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end(); 266 ++I) { 267 if (I->first.getLocationContext() != LC) 268 continue; 269 270 const Stmt *S = I->first.getStmt(); 271 Indent(Out, InnerSpace, IsDot) 272 << "{ \"stmt_id\": " << S->getID(Ctx) << ", \"pretty\": "; 273 S->printJson(Out, nullptr, PP, /*AddQuotes=*/true); 274 275 Out << ", \"value\": "; 276 I->second.printJson(Out, /*AddQuotes=*/true); 277 278 Out << " }"; 279 280 if (I != LastI) 281 Out << ','; 282 Out << NL; 283 } 284 285 if (HasItem) 286 Indent(Out, --InnerSpace, IsDot) << ']'; 287 else 288 Out << "null "; 289 }); 290 291 Indent(Out, --Space, IsDot) << "]}," << NL; 292 } 293