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