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