454 lines · cpp
1//===- SymbolManager.h - Management of Symbolic 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 defines SymbolManager, a class that manages symbolic values10// created for use by ExprEngine and related classes.11//12//===----------------------------------------------------------------------===//13 14#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"15#include "clang/AST/ASTContext.h"16#include "clang/AST/Expr.h"17#include "clang/Analysis/Analyses/LiveVariables.h"18#include "clang/Analysis/AnalysisDeclContext.h"19#include "clang/Basic/LLVM.h"20#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"21#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"22#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"23#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"24#include "llvm/Support/Compiler.h"25#include "llvm/Support/ErrorHandling.h"26#include "llvm/Support/raw_ostream.h"27#include <cassert>28 29using namespace clang;30using namespace ento;31 32void SymExpr::anchor() {}33 34StringRef SymbolConjured::getKindStr() const { return "conj_$"; }35StringRef SymbolDerived::getKindStr() const { return "derived_$"; }36StringRef SymbolExtent::getKindStr() const { return "extent_$"; }37StringRef SymbolMetadata::getKindStr() const { return "meta_$"; }38StringRef SymbolRegionValue::getKindStr() const { return "reg_$"; }39 40LLVM_DUMP_METHOD void SymExpr::dump() const { dumpToStream(llvm::errs()); }41 42void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS, const SymExpr *Sym) {43 OS << '(';44 Sym->dumpToStream(OS);45 OS << ')';46}47 48void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS,49 const llvm::APSInt &Value) {50 if (Value.isUnsigned())51 OS << Value.getZExtValue();52 else53 OS << Value.getSExtValue();54 if (Value.isUnsigned())55 OS << 'U';56}57 58void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS,59 BinaryOperator::Opcode Op) {60 OS << ' ' << BinaryOperator::getOpcodeStr(Op) << ' ';61}62 63void SymbolCast::dumpToStream(raw_ostream &os) const {64 os << '(' << ToTy << ") (";65 Operand->dumpToStream(os);66 os << ')';67}68 69void UnarySymExpr::dumpToStream(raw_ostream &os) const {70 os << UnaryOperator::getOpcodeStr(Op);71 bool Binary = isa<BinarySymExpr>(Operand);72 if (Binary)73 os << '(';74 Operand->dumpToStream(os);75 if (Binary)76 os << ')';77}78 79const Stmt *SymbolConjured::getStmt() const {80 // Sometimes the CFG element is invalid, avoid dereferencing it.81 if (Elem.getParent() == nullptr ||82 Elem.getIndexInBlock() >= Elem.getParent()->size())83 return nullptr;84 switch (Elem->getKind()) {85 case CFGElement::Initializer:86 if (const auto *Init = Elem->castAs<CFGInitializer>().getInitializer()) {87 return Init->getInit();88 }89 return nullptr;90 case CFGElement::ScopeBegin:91 return Elem->castAs<CFGScopeBegin>().getTriggerStmt();92 case CFGElement::ScopeEnd:93 return Elem->castAs<CFGScopeEnd>().getTriggerStmt();94 case CFGElement::NewAllocator:95 return Elem->castAs<CFGNewAllocator>().getAllocatorExpr();96 case CFGElement::LifetimeEnds:97 return Elem->castAs<CFGLifetimeEnds>().getTriggerStmt();98 case CFGElement::LoopExit:99 return Elem->castAs<CFGLoopExit>().getLoopStmt();100 case CFGElement::Statement:101 return Elem->castAs<CFGStmt>().getStmt();102 case CFGElement::Constructor:103 return Elem->castAs<CFGConstructor>().getStmt();104 case CFGElement::CXXRecordTypedCall:105 return Elem->castAs<CFGCXXRecordTypedCall>().getStmt();106 case CFGElement::AutomaticObjectDtor:107 return Elem->castAs<CFGAutomaticObjDtor>().getTriggerStmt();108 case CFGElement::DeleteDtor:109 return Elem->castAs<CFGDeleteDtor>().getDeleteExpr();110 case CFGElement::BaseDtor:111 return nullptr;112 case CFGElement::MemberDtor:113 return nullptr;114 case CFGElement::TemporaryDtor:115 return Elem->castAs<CFGTemporaryDtor>().getBindTemporaryExpr();116 case CFGElement::CleanupFunction:117 return nullptr;118 }119 return nullptr;120}121 122void SymbolConjured::dumpToStream(raw_ostream &os) const {123 os << getKindStr() << getSymbolID() << '{' << T << ", LC" << LCtx->getID();124 if (auto *S = getStmt())125 os << ", S" << S->getID(LCtx->getDecl()->getASTContext());126 else127 os << ", no stmt";128 os << ", #" << Count << '}';129}130 131void SymbolDerived::dumpToStream(raw_ostream &os) const {132 os << getKindStr() << getSymbolID() << '{' << getParentSymbol() << ','133 << getRegion() << '}';134}135 136void SymbolExtent::dumpToStream(raw_ostream &os) const {137 os << getKindStr() << getSymbolID() << '{' << getRegion() << '}';138}139 140void SymbolMetadata::dumpToStream(raw_ostream &os) const {141 os << getKindStr() << getSymbolID() << '{' << getRegion() << ',' << T << '}';142}143 144void SymbolData::anchor() {}145 146void SymbolRegionValue::dumpToStream(raw_ostream &os) const {147 os << getKindStr() << getSymbolID() << '<' << getType() << ' ' << R << '>';148}149 150bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const {151 return itr == X.itr;152}153 154bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const {155 return itr != X.itr;156}157 158SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) {159 itr.push_back(SE);160}161 162SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() {163 assert(!itr.empty() && "attempting to iterate on an 'end' iterator");164 expand();165 return *this;166}167 168SymbolRef SymExpr::symbol_iterator::operator*() {169 assert(!itr.empty() && "attempting to dereference an 'end' iterator");170 return itr.back();171}172 173void SymExpr::symbol_iterator::expand() {174 const SymExpr *SE = itr.pop_back_val();175 176 switch (SE->getKind()) {177 case SymExpr::SymbolRegionValueKind:178 case SymExpr::SymbolConjuredKind:179 case SymExpr::SymbolDerivedKind:180 case SymExpr::SymbolExtentKind:181 case SymExpr::SymbolMetadataKind:182 return;183 case SymExpr::SymbolCastKind:184 itr.push_back(cast<SymbolCast>(SE)->getOperand());185 return;186 case SymExpr::UnarySymExprKind:187 itr.push_back(cast<UnarySymExpr>(SE)->getOperand());188 return;189 case SymExpr::SymIntExprKind:190 itr.push_back(cast<SymIntExpr>(SE)->getLHS());191 return;192 case SymExpr::IntSymExprKind:193 itr.push_back(cast<IntSymExpr>(SE)->getRHS());194 return;195 case SymExpr::SymSymExprKind: {196 const auto *x = cast<SymSymExpr>(SE);197 itr.push_back(x->getLHS());198 itr.push_back(x->getRHS());199 return;200 }201 }202 llvm_unreachable("unhandled expansion case");203}204 205QualType SymbolConjured::getType() const {206 return T;207}208 209QualType SymbolDerived::getType() const {210 return R->getValueType();211}212 213QualType SymbolExtent::getType() const {214 ASTContext &Ctx = R->getMemRegionManager().getContext();215 return Ctx.getSizeType();216}217 218QualType SymbolMetadata::getType() const {219 return T;220}221 222QualType SymbolRegionValue::getType() const {223 return R->getValueType();224}225 226bool SymbolManager::canSymbolicate(QualType T) {227 T = T.getCanonicalType();228 229 if (Loc::isLocType(T))230 return true;231 232 if (T->isIntegralOrEnumerationType())233 return true;234 235 if (T->isRecordType() && !T->isUnionType())236 return true;237 238 return false;239}240 241void SymbolManager::addSymbolDependency(const SymbolRef Primary,242 const SymbolRef Dependent) {243 auto &dependencies = SymbolDependencies[Primary];244 if (!dependencies) {245 dependencies = std::make_unique<SymbolRefSmallVectorTy>();246 }247 dependencies->push_back(Dependent);248}249 250const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols(251 const SymbolRef Primary) {252 SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary);253 if (I == SymbolDependencies.end())254 return nullptr;255 return I->second.get();256}257 258void SymbolReaper::markDependentsLive(SymbolRef sym) {259 // Do not mark dependents more then once.260 SymbolMapTy::iterator LI = TheLiving.find(sym);261 assert(LI != TheLiving.end() && "The primary symbol is not live.");262 if (LI->second == HaveMarkedDependents)263 return;264 LI->second = HaveMarkedDependents;265 266 if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) {267 for (const auto I : *Deps) {268 if (TheLiving.contains(I))269 continue;270 markLive(I);271 }272 }273}274 275void SymbolReaper::markLive(SymbolRef sym) {276 TheLiving[sym] = NotProcessed;277 markDependentsLive(sym);278}279 280void SymbolReaper::markLive(const MemRegion *region) {281 LiveRegionRoots.insert(region->getBaseRegion());282 markElementIndicesLive(region);283}284 285void SymbolReaper::markLazilyCopied(const clang::ento::MemRegion *region) {286 LazilyCopiedRegionRoots.insert(region->getBaseRegion());287}288 289void SymbolReaper::markElementIndicesLive(const MemRegion *region) {290 for (auto SR = dyn_cast<SubRegion>(region); SR;291 SR = dyn_cast<SubRegion>(SR->getSuperRegion())) {292 if (const auto ER = dyn_cast<ElementRegion>(SR)) {293 SVal Idx = ER->getIndex();294 for (SymbolRef Sym : Idx.symbols())295 markLive(Sym);296 }297 }298}299 300void SymbolReaper::markInUse(SymbolRef sym) {301 if (isa<SymbolMetadata>(sym))302 MetadataInUse.insert(sym);303}304 305bool SymbolReaper::isLiveRegion(const MemRegion *MR) {306 // TODO: For now, liveness of a memory region is equivalent to liveness of its307 // base region. In fact we can do a bit better: say, if a particular FieldDecl308 // is not used later in the path, we can diagnose a leak of a value within309 // that field earlier than, say, the variable that contains the field dies.310 MR = MR->getBaseRegion();311 if (LiveRegionRoots.count(MR))312 return true;313 314 if (const auto *SR = dyn_cast<SymbolicRegion>(MR))315 return isLive(SR->getSymbol());316 317 if (const auto *VR = dyn_cast<VarRegion>(MR))318 return isLive(VR, true);319 320 // FIXME: This is a gross over-approximation. What we really need is a way to321 // tell if anything still refers to this region. Unlike SymbolicRegions,322 // AllocaRegions don't have associated symbols, though, so we don't actually323 // have a way to track their liveness.324 return isa<AllocaRegion, CXXThisRegion, MemSpaceRegion, CodeTextRegion>(MR);325}326 327bool SymbolReaper::isLazilyCopiedRegion(const MemRegion *MR) const {328 // TODO: See comment in isLiveRegion.329 return LazilyCopiedRegionRoots.count(MR->getBaseRegion());330}331 332bool SymbolReaper::isReadableRegion(const MemRegion *MR) {333 return isLiveRegion(MR) || isLazilyCopiedRegion(MR);334}335 336bool SymbolReaper::isLive(SymbolRef sym) {337 if (TheLiving.count(sym)) {338 markDependentsLive(sym);339 return true;340 }341 342 bool KnownLive;343 344 switch (sym->getKind()) {345 case SymExpr::SymbolRegionValueKind:346 KnownLive = isReadableRegion(cast<SymbolRegionValue>(sym)->getRegion());347 break;348 case SymExpr::SymbolConjuredKind:349 KnownLive = false;350 break;351 case SymExpr::SymbolDerivedKind:352 KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol());353 break;354 case SymExpr::SymbolExtentKind:355 KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion());356 break;357 case SymExpr::SymbolMetadataKind:358 KnownLive = MetadataInUse.count(sym) &&359 isLiveRegion(cast<SymbolMetadata>(sym)->getRegion());360 if (KnownLive)361 MetadataInUse.erase(sym);362 break;363 case SymExpr::SymIntExprKind:364 KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS());365 break;366 case SymExpr::IntSymExprKind:367 KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS());368 break;369 case SymExpr::SymSymExprKind:370 KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) &&371 isLive(cast<SymSymExpr>(sym)->getRHS());372 break;373 case SymExpr::SymbolCastKind:374 KnownLive = isLive(cast<SymbolCast>(sym)->getOperand());375 break;376 case SymExpr::UnarySymExprKind:377 KnownLive = isLive(cast<UnarySymExpr>(sym)->getOperand());378 break;379 }380 381 if (KnownLive)382 markLive(sym);383 384 return KnownLive;385}386 387bool388SymbolReaper::isLive(const Expr *ExprVal, const LocationContext *ELCtx) const {389 if (LCtx == nullptr)390 return false;391 392 if (LCtx != ELCtx) {393 // If the reaper's location context is a parent of the expression's394 // location context, then the expression value is now "out of scope".395 if (LCtx->isParentOf(ELCtx))396 return false;397 return true;398 }399 400 // If no statement is provided, everything in this and parent contexts is401 // live.402 if (!Loc)403 return true;404 405 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal);406}407 408bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{409 const StackFrameContext *VarContext = VR->getStackFrame();410 411 if (!VarContext)412 return true;413 414 if (!LCtx)415 return false;416 const StackFrameContext *CurrentContext = LCtx->getStackFrame();417 418 if (VarContext == CurrentContext) {419 // If no statement is provided, everything is live.420 if (!Loc)421 return true;422 423 // Anonymous parameters of an inheriting constructor are live for the entire424 // duration of the constructor.425 if (isa<CXXInheritedCtorInitExpr>(Loc))426 return true;427 428 if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl()))429 return true;430 431 if (!includeStoreBindings)432 return false;433 434 unsigned &cachedQuery =435 const_cast<SymbolReaper *>(this)->includedRegionCache[VR];436 437 if (cachedQuery) {438 return cachedQuery == 1;439 }440 441 // Query the store to see if the region occurs in any live bindings.442 if (Store store = reapedStore.getStore()) {443 bool hasRegion =444 reapedStore.getStoreManager().includedInBindings(store, VR);445 cachedQuery = hasRegion ? 1 : 2;446 return hasRegion;447 }448 449 return false;450 }451 452 return VarContext->isParentOf(CurrentContext);453}454