1341825Sdim//===- SymbolManager.h - Management of Symbolic Values ----------*- C++ -*-===// 2218887Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6218887Sdim// 7218887Sdim//===----------------------------------------------------------------------===// 8218887Sdim// 9218887Sdim// This file defines SymbolManager, a class that manages symbolic values 10218887Sdim// created for use by ExprEngine and related classes. 11218887Sdim// 12218887Sdim//===----------------------------------------------------------------------===// 13218887Sdim 14280031Sdim#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H 15280031Sdim#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H 16218887Sdim 17218887Sdim#include "clang/AST/Expr.h" 18341825Sdim#include "clang/AST/Type.h" 19327952Sdim#include "clang/Analysis/AnalysisDeclContext.h" 20226633Sdim#include "clang/Basic/LLVM.h" 21309124Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 22226633Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" 23309124Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" 24249423Sdim#include "llvm/ADT/DenseMap.h" 25249423Sdim#include "llvm/ADT/DenseSet.h" 26249423Sdim#include "llvm/ADT/FoldingSet.h" 27276479Sdim#include "llvm/Support/Allocator.h" 28341825Sdim#include <cassert> 29218887Sdim 30218887Sdimnamespace clang { 31218887Sdim 32341825Sdimclass ASTContext; 33341825Sdimclass Stmt; 34341825Sdim 35218887Sdimnamespace ento { 36218887Sdim 37341825Sdimclass BasicValueFactory; 38341825Sdimclass StoreManager; 39341825Sdim 40341825Sdim///A symbol representing the value stored at a MemRegion. 41218887Sdimclass SymbolRegionValue : public SymbolData { 42226633Sdim const TypedValueRegion *R; 43218887Sdim 44218887Sdimpublic: 45226633Sdim SymbolRegionValue(SymbolID sym, const TypedValueRegion *r) 46321369Sdim : SymbolData(SymbolRegionValueKind, sym), R(r) { 47321369Sdim assert(r); 48321369Sdim assert(isValidTypeForSymbol(r->getValueType())); 49321369Sdim } 50218887Sdim 51226633Sdim const TypedValueRegion* getRegion() const { return R; } 52218887Sdim 53226633Sdim static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) { 54296417Sdim profile.AddInteger((unsigned) SymbolRegionValueKind); 55218887Sdim profile.AddPointer(R); 56218887Sdim } 57218887Sdim 58276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 59218887Sdim Profile(profile, R); 60218887Sdim } 61218887Sdim 62276479Sdim void dumpToStream(raw_ostream &os) const override; 63309124Sdim const MemRegion *getOriginRegion() const override { return getRegion(); } 64218887Sdim 65276479Sdim QualType getType() const override; 66218887Sdim 67218887Sdim // Implement isa<T> support. 68341825Sdim static bool classof(const SymExpr *SE) { 69296417Sdim return SE->getKind() == SymbolRegionValueKind; 70218887Sdim } 71218887Sdim}; 72218887Sdim 73234353Sdim/// A symbol representing the result of an expression in the case when we do 74234353Sdim/// not know anything about what the expression is. 75218887Sdimclass SymbolConjured : public SymbolData { 76226633Sdim const Stmt *S; 77218887Sdim QualType T; 78218887Sdim unsigned Count; 79234353Sdim const LocationContext *LCtx; 80226633Sdim const void *SymbolTag; 81218887Sdim 82218887Sdimpublic: 83234353Sdim SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx, 84296417Sdim QualType t, unsigned count, const void *symbolTag) 85296417Sdim : SymbolData(SymbolConjuredKind, sym), S(s), T(t), Count(count), 86321369Sdim LCtx(lctx), SymbolTag(symbolTag) { 87321369Sdim // FIXME: 's' might be a nullptr if we're conducting invalidation 88321369Sdim // that was caused by a destructor call on a temporary object, 89321369Sdim // which has no statement associated with it. 90321369Sdim // Due to this, we might be creating the same invalidation symbol for 91321369Sdim // two different invalidation passes (for two different temporaries). 92321369Sdim assert(lctx); 93321369Sdim assert(isValidTypeForSymbol(t)); 94321369Sdim } 95218887Sdim 96226633Sdim const Stmt *getStmt() const { return S; } 97218887Sdim unsigned getCount() const { return Count; } 98226633Sdim const void *getTag() const { return SymbolTag; } 99218887Sdim 100276479Sdim QualType getType() const override; 101218887Sdim 102276479Sdim void dumpToStream(raw_ostream &os) const override; 103218887Sdim 104226633Sdim static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S, 105234353Sdim QualType T, unsigned Count, const LocationContext *LCtx, 106234353Sdim const void *SymbolTag) { 107296417Sdim profile.AddInteger((unsigned) SymbolConjuredKind); 108218887Sdim profile.AddPointer(S); 109234353Sdim profile.AddPointer(LCtx); 110218887Sdim profile.Add(T); 111218887Sdim profile.AddInteger(Count); 112218887Sdim profile.AddPointer(SymbolTag); 113218887Sdim } 114218887Sdim 115276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 116234353Sdim Profile(profile, S, T, Count, LCtx, SymbolTag); 117218887Sdim } 118218887Sdim 119218887Sdim // Implement isa<T> support. 120341825Sdim static bool classof(const SymExpr *SE) { 121296417Sdim return SE->getKind() == SymbolConjuredKind; 122218887Sdim } 123218887Sdim}; 124218887Sdim 125226633Sdim/// A symbol representing the value of a MemRegion whose parent region has 126226633Sdim/// symbolic value. 127218887Sdimclass SymbolDerived : public SymbolData { 128218887Sdim SymbolRef parentSymbol; 129226633Sdim const TypedValueRegion *R; 130218887Sdim 131218887Sdimpublic: 132226633Sdim SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r) 133321369Sdim : SymbolData(SymbolDerivedKind, sym), parentSymbol(parent), R(r) { 134321369Sdim assert(parent); 135321369Sdim assert(r); 136321369Sdim assert(isValidTypeForSymbol(r->getValueType())); 137321369Sdim } 138218887Sdim 139218887Sdim SymbolRef getParentSymbol() const { return parentSymbol; } 140226633Sdim const TypedValueRegion *getRegion() const { return R; } 141218887Sdim 142276479Sdim QualType getType() const override; 143218887Sdim 144276479Sdim void dumpToStream(raw_ostream &os) const override; 145309124Sdim const MemRegion *getOriginRegion() const override { return getRegion(); } 146218887Sdim 147218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, 148226633Sdim const TypedValueRegion *r) { 149296417Sdim profile.AddInteger((unsigned) SymbolDerivedKind); 150218887Sdim profile.AddPointer(r); 151218887Sdim profile.AddPointer(parent); 152218887Sdim } 153218887Sdim 154276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 155218887Sdim Profile(profile, parentSymbol, R); 156218887Sdim } 157218887Sdim 158218887Sdim // Implement isa<T> support. 159341825Sdim static bool classof(const SymExpr *SE) { 160296417Sdim return SE->getKind() == SymbolDerivedKind; 161218887Sdim } 162218887Sdim}; 163218887Sdim 164218887Sdim/// SymbolExtent - Represents the extent (size in bytes) of a bounded region. 165218887Sdim/// Clients should not ask the SymbolManager for a region's extent. Always use 166218887Sdim/// SubRegion::getExtent instead -- the value returned may not be a symbol. 167218887Sdimclass SymbolExtent : public SymbolData { 168218887Sdim const SubRegion *R; 169341825Sdim 170218887Sdimpublic: 171218887Sdim SymbolExtent(SymbolID sym, const SubRegion *r) 172321369Sdim : SymbolData(SymbolExtentKind, sym), R(r) { 173321369Sdim assert(r); 174321369Sdim } 175218887Sdim 176218887Sdim const SubRegion *getRegion() const { return R; } 177218887Sdim 178276479Sdim QualType getType() const override; 179218887Sdim 180276479Sdim void dumpToStream(raw_ostream &os) const override; 181218887Sdim 182218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) { 183296417Sdim profile.AddInteger((unsigned) SymbolExtentKind); 184218887Sdim profile.AddPointer(R); 185218887Sdim } 186218887Sdim 187276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 188218887Sdim Profile(profile, R); 189218887Sdim } 190218887Sdim 191218887Sdim // Implement isa<T> support. 192341825Sdim static bool classof(const SymExpr *SE) { 193296417Sdim return SE->getKind() == SymbolExtentKind; 194218887Sdim } 195218887Sdim}; 196218887Sdim 197218887Sdim/// SymbolMetadata - Represents path-dependent metadata about a specific region. 198218887Sdim/// Metadata symbols remain live as long as they are marked as in use before 199218887Sdim/// dead-symbol sweeping AND their associated regions are still alive. 200218887Sdim/// Intended for use by checkers. 201218887Sdimclass SymbolMetadata : public SymbolData { 202218887Sdim const MemRegion* R; 203226633Sdim const Stmt *S; 204218887Sdim QualType T; 205314564Sdim const LocationContext *LCtx; 206218887Sdim unsigned Count; 207226633Sdim const void *Tag; 208341825Sdim 209218887Sdimpublic: 210226633Sdim SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t, 211314564Sdim const LocationContext *LCtx, unsigned count, const void *tag) 212341825Sdim : SymbolData(SymbolMetadataKind, sym), R(r), S(s), T(t), LCtx(LCtx), 213341825Sdim Count(count), Tag(tag) { 214321369Sdim assert(r); 215321369Sdim assert(s); 216321369Sdim assert(isValidTypeForSymbol(t)); 217321369Sdim assert(LCtx); 218321369Sdim assert(tag); 219321369Sdim } 220218887Sdim 221218887Sdim const MemRegion *getRegion() const { return R; } 222226633Sdim const Stmt *getStmt() const { return S; } 223314564Sdim const LocationContext *getLocationContext() const { return LCtx; } 224218887Sdim unsigned getCount() const { return Count; } 225226633Sdim const void *getTag() const { return Tag; } 226218887Sdim 227276479Sdim QualType getType() const override; 228218887Sdim 229276479Sdim void dumpToStream(raw_ostream &os) const override; 230218887Sdim 231218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, 232314564Sdim const Stmt *S, QualType T, const LocationContext *LCtx, 233314564Sdim unsigned Count, const void *Tag) { 234296417Sdim profile.AddInteger((unsigned) SymbolMetadataKind); 235218887Sdim profile.AddPointer(R); 236218887Sdim profile.AddPointer(S); 237218887Sdim profile.Add(T); 238314564Sdim profile.AddPointer(LCtx); 239218887Sdim profile.AddInteger(Count); 240218887Sdim profile.AddPointer(Tag); 241218887Sdim } 242218887Sdim 243276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 244314564Sdim Profile(profile, R, S, T, LCtx, Count, Tag); 245218887Sdim } 246218887Sdim 247218887Sdim // Implement isa<T> support. 248341825Sdim static bool classof(const SymExpr *SE) { 249296417Sdim return SE->getKind() == SymbolMetadataKind; 250218887Sdim } 251218887Sdim}; 252218887Sdim 253341825Sdim/// Represents a cast expression. 254234353Sdimclass SymbolCast : public SymExpr { 255234353Sdim const SymExpr *Operand; 256341825Sdim 257234353Sdim /// Type of the operand. 258234353Sdim QualType FromTy; 259341825Sdim 260234353Sdim /// The type of the result. 261234353Sdim QualType ToTy; 262234353Sdim 263234353Sdimpublic: 264321369Sdim SymbolCast(const SymExpr *In, QualType From, QualType To) 265321369Sdim : SymExpr(SymbolCastKind), Operand(In), FromTy(From), ToTy(To) { 266321369Sdim assert(In); 267321369Sdim assert(isValidTypeForSymbol(From)); 268321369Sdim // FIXME: GenericTaintChecker creates symbols of void type. 269321369Sdim // Otherwise, 'To' should also be a valid type. 270321369Sdim } 271234353Sdim 272341825Sdim unsigned computeComplexity() const override { 273341825Sdim if (Complexity == 0) 274341825Sdim Complexity = 1 + Operand->computeComplexity(); 275341825Sdim return Complexity; 276341825Sdim } 277341825Sdim 278276479Sdim QualType getType() const override { return ToTy; } 279234353Sdim 280234353Sdim const SymExpr *getOperand() const { return Operand; } 281234353Sdim 282276479Sdim void dumpToStream(raw_ostream &os) const override; 283234353Sdim 284234353Sdim static void Profile(llvm::FoldingSetNodeID& ID, 285234353Sdim const SymExpr *In, QualType From, QualType To) { 286296417Sdim ID.AddInteger((unsigned) SymbolCastKind); 287234353Sdim ID.AddPointer(In); 288234353Sdim ID.Add(From); 289234353Sdim ID.Add(To); 290234353Sdim } 291234353Sdim 292276479Sdim void Profile(llvm::FoldingSetNodeID& ID) override { 293234353Sdim Profile(ID, Operand, FromTy, ToTy); 294234353Sdim } 295234353Sdim 296234353Sdim // Implement isa<T> support. 297341825Sdim static bool classof(const SymExpr *SE) { 298296417Sdim return SE->getKind() == SymbolCastKind; 299234353Sdim } 300234353Sdim}; 301234353Sdim 302341825Sdim/// Represents a symbolic expression involving a binary operator 303251662Sdimclass BinarySymExpr : public SymExpr { 304218887Sdim BinaryOperator::Opcode Op; 305218887Sdim QualType T; 306218887Sdim 307251662Sdimprotected: 308251662Sdim BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t) 309321369Sdim : SymExpr(k), Op(op), T(t) { 310321369Sdim assert(classof(this)); 311344779Sdim // Binary expressions are results of arithmetic. Pointer arithmetic is not 312344779Sdim // handled by binary expressions, but it is instead handled by applying 313344779Sdim // sub-regions to regions. 314344779Sdim assert(isValidTypeForSymbol(t) && !Loc::isLocType(t)); 315321369Sdim } 316251662Sdim 317218887Sdimpublic: 318218887Sdim // FIXME: We probably need to make this out-of-line to avoid redundant 319218887Sdim // generation of virtual functions. 320276479Sdim QualType getType() const override { return T; } 321218887Sdim 322218887Sdim BinaryOperator::Opcode getOpcode() const { return Op; } 323218887Sdim 324251662Sdim // Implement isa<T> support. 325341825Sdim static bool classof(const SymExpr *SE) { 326251662Sdim Kind k = SE->getKind(); 327251662Sdim return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS; 328251662Sdim } 329251662Sdim}; 330251662Sdim 331341825Sdim/// Represents a symbolic expression like 'x' + 3. 332251662Sdimclass SymIntExpr : public BinarySymExpr { 333251662Sdim const SymExpr *LHS; 334251662Sdim const llvm::APSInt& RHS; 335251662Sdim 336251662Sdimpublic: 337251662Sdim SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 338321369Sdim const llvm::APSInt &rhs, QualType t) 339321369Sdim : BinarySymExpr(SymIntExprKind, op, t), LHS(lhs), RHS(rhs) { 340321369Sdim assert(lhs); 341321369Sdim } 342251662Sdim 343276479Sdim void dumpToStream(raw_ostream &os) const override; 344218887Sdim 345218887Sdim const SymExpr *getLHS() const { return LHS; } 346218887Sdim const llvm::APSInt &getRHS() const { return RHS; } 347218887Sdim 348341825Sdim unsigned computeComplexity() const override { 349341825Sdim if (Complexity == 0) 350341825Sdim Complexity = 1 + LHS->computeComplexity(); 351341825Sdim return Complexity; 352341825Sdim } 353341825Sdim 354218887Sdim static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 355218887Sdim BinaryOperator::Opcode op, const llvm::APSInt& rhs, 356218887Sdim QualType t) { 357296417Sdim ID.AddInteger((unsigned) SymIntExprKind); 358218887Sdim ID.AddPointer(lhs); 359218887Sdim ID.AddInteger(op); 360218887Sdim ID.AddPointer(&rhs); 361218887Sdim ID.Add(t); 362218887Sdim } 363218887Sdim 364276479Sdim void Profile(llvm::FoldingSetNodeID& ID) override { 365251662Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 366218887Sdim } 367218887Sdim 368218887Sdim // Implement isa<T> support. 369341825Sdim static bool classof(const SymExpr *SE) { 370296417Sdim return SE->getKind() == SymIntExprKind; 371218887Sdim } 372218887Sdim}; 373218887Sdim 374341825Sdim/// Represents a symbolic expression like 3 - 'x'. 375251662Sdimclass IntSymExpr : public BinarySymExpr { 376234353Sdim const llvm::APSInt& LHS; 377234353Sdim const SymExpr *RHS; 378234353Sdim 379234353Sdimpublic: 380321369Sdim IntSymExpr(const llvm::APSInt &lhs, BinaryOperator::Opcode op, 381234353Sdim const SymExpr *rhs, QualType t) 382321369Sdim : BinarySymExpr(IntSymExprKind, op, t), LHS(lhs), RHS(rhs) { 383321369Sdim assert(rhs); 384321369Sdim } 385234353Sdim 386276479Sdim void dumpToStream(raw_ostream &os) const override; 387234353Sdim 388234353Sdim const SymExpr *getRHS() const { return RHS; } 389234353Sdim const llvm::APSInt &getLHS() const { return LHS; } 390234353Sdim 391341825Sdim unsigned computeComplexity() const override { 392341825Sdim if (Complexity == 0) 393341825Sdim Complexity = 1 + RHS->computeComplexity(); 394341825Sdim return Complexity; 395341825Sdim } 396341825Sdim 397234353Sdim static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs, 398234353Sdim BinaryOperator::Opcode op, const SymExpr *rhs, 399234353Sdim QualType t) { 400296417Sdim ID.AddInteger((unsigned) IntSymExprKind); 401234353Sdim ID.AddPointer(&lhs); 402234353Sdim ID.AddInteger(op); 403234353Sdim ID.AddPointer(rhs); 404234353Sdim ID.Add(t); 405234353Sdim } 406234353Sdim 407276479Sdim void Profile(llvm::FoldingSetNodeID& ID) override { 408251662Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 409234353Sdim } 410234353Sdim 411234353Sdim // Implement isa<T> support. 412341825Sdim static bool classof(const SymExpr *SE) { 413296417Sdim return SE->getKind() == IntSymExprKind; 414234353Sdim } 415234353Sdim}; 416234353Sdim 417341825Sdim/// Represents a symbolic expression like 'x' + 'y'. 418251662Sdimclass SymSymExpr : public BinarySymExpr { 419218887Sdim const SymExpr *LHS; 420218887Sdim const SymExpr *RHS; 421218887Sdim 422218887Sdimpublic: 423218887Sdim SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, 424218887Sdim QualType t) 425321369Sdim : BinarySymExpr(SymSymExprKind, op, t), LHS(lhs), RHS(rhs) { 426321369Sdim assert(lhs); 427321369Sdim assert(rhs); 428321369Sdim } 429218887Sdim 430218887Sdim const SymExpr *getLHS() const { return LHS; } 431218887Sdim const SymExpr *getRHS() const { return RHS; } 432218887Sdim 433276479Sdim void dumpToStream(raw_ostream &os) const override; 434218887Sdim 435341825Sdim unsigned computeComplexity() const override { 436341825Sdim if (Complexity == 0) 437341825Sdim Complexity = RHS->computeComplexity() + LHS->computeComplexity(); 438341825Sdim return Complexity; 439341825Sdim } 440341825Sdim 441218887Sdim static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 442218887Sdim BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { 443296417Sdim ID.AddInteger((unsigned) SymSymExprKind); 444218887Sdim ID.AddPointer(lhs); 445218887Sdim ID.AddInteger(op); 446218887Sdim ID.AddPointer(rhs); 447218887Sdim ID.Add(t); 448218887Sdim } 449218887Sdim 450276479Sdim void Profile(llvm::FoldingSetNodeID& ID) override { 451251662Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 452218887Sdim } 453218887Sdim 454218887Sdim // Implement isa<T> support. 455341825Sdim static bool classof(const SymExpr *SE) { 456296417Sdim return SE->getKind() == SymSymExprKind; 457218887Sdim } 458218887Sdim}; 459218887Sdim 460218887Sdimclass SymbolManager { 461341825Sdim using DataSetTy = llvm::FoldingSet<SymExpr>; 462341825Sdim using SymbolDependTy = llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy *>; 463226633Sdim 464218887Sdim DataSetTy DataSet; 465341825Sdim 466226633Sdim /// Stores the extra dependencies between symbols: the data should be kept 467226633Sdim /// alive as long as the key is live. 468226633Sdim SymbolDependTy SymbolDependencies; 469341825Sdim 470341825Sdim unsigned SymbolCounter = 0; 471218887Sdim llvm::BumpPtrAllocator& BPAlloc; 472218887Sdim BasicValueFactory &BV; 473226633Sdim ASTContext &Ctx; 474218887Sdim 475218887Sdimpublic: 476226633Sdim SymbolManager(ASTContext &ctx, BasicValueFactory &bv, 477218887Sdim llvm::BumpPtrAllocator& bpalloc) 478341825Sdim : SymbolDependencies(16), BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} 479218887Sdim ~SymbolManager(); 480218887Sdim 481218887Sdim static bool canSymbolicate(QualType T); 482218887Sdim 483341825Sdim /// Make a unique symbol for MemRegion R according to its kind. 484226633Sdim const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R); 485218887Sdim 486243830Sdim const SymbolConjured* conjureSymbol(const Stmt *E, 487243830Sdim const LocationContext *LCtx, 488243830Sdim QualType T, 489243830Sdim unsigned VisitCount, 490276479Sdim const void *SymbolTag = nullptr); 491218887Sdim 492243830Sdim const SymbolConjured* conjureSymbol(const Expr *E, 493243830Sdim const LocationContext *LCtx, 494243830Sdim unsigned VisitCount, 495276479Sdim const void *SymbolTag = nullptr) { 496243830Sdim return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag); 497218887Sdim } 498218887Sdim 499218887Sdim const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol, 500226633Sdim const TypedValueRegion *R); 501218887Sdim 502218887Sdim const SymbolExtent *getExtentSymbol(const SubRegion *R); 503218887Sdim 504341825Sdim /// Creates a metadata symbol associated with a specific region. 505226633Sdim /// 506226633Sdim /// VisitCount can be used to differentiate regions corresponding to 507226633Sdim /// different loop iterations, thus, making the symbol path-dependent. 508276479Sdim const SymbolMetadata *getMetadataSymbol(const MemRegion *R, const Stmt *S, 509314564Sdim QualType T, 510314564Sdim const LocationContext *LCtx, 511314564Sdim unsigned VisitCount, 512276479Sdim const void *SymbolTag = nullptr); 513218887Sdim 514234353Sdim const SymbolCast* getCastSymbol(const SymExpr *Operand, 515234353Sdim QualType From, QualType To); 516234353Sdim 517218887Sdim const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 518218887Sdim const llvm::APSInt& rhs, QualType t); 519218887Sdim 520218887Sdim const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op, 521218887Sdim const llvm::APSInt& rhs, QualType t) { 522218887Sdim return getSymIntExpr(&lhs, op, rhs, t); 523218887Sdim } 524218887Sdim 525234353Sdim const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs, 526234353Sdim BinaryOperator::Opcode op, 527234353Sdim const SymExpr *rhs, QualType t); 528234353Sdim 529218887Sdim const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 530218887Sdim const SymExpr *rhs, QualType t); 531218887Sdim 532218887Sdim QualType getType(const SymExpr *SE) const { 533243830Sdim return SE->getType(); 534218887Sdim } 535218887Sdim 536341825Sdim /// Add artificial symbol dependency. 537226633Sdim /// 538226633Sdim /// The dependent symbol should stay alive as long as the primary is alive. 539226633Sdim void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent); 540226633Sdim 541226633Sdim const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary); 542226633Sdim 543218887Sdim ASTContext &getContext() { return Ctx; } 544218887Sdim BasicValueFactory &getBasicVals() { return BV; } 545218887Sdim}; 546218887Sdim 547341825Sdim/// A class responsible for cleaning up unused symbols. 548218887Sdimclass SymbolReaper { 549226633Sdim enum SymbolStatus { 550226633Sdim NotProcessed, 551226633Sdim HaveMarkedDependents 552226633Sdim }; 553218887Sdim 554341825Sdim using SymbolSetTy = llvm::DenseSet<SymbolRef>; 555341825Sdim using SymbolMapTy = llvm::DenseMap<SymbolRef, SymbolStatus>; 556341825Sdim using RegionSetTy = llvm::DenseSet<const MemRegion *>; 557226633Sdim 558226633Sdim SymbolMapTy TheLiving; 559226633Sdim SymbolSetTy MetadataInUse; 560226633Sdim 561226633Sdim RegionSetTy RegionRoots; 562341825Sdim 563239462Sdim const StackFrameContext *LCtx; 564218887Sdim const Stmt *Loc; 565218887Sdim SymbolManager& SymMgr; 566226633Sdim StoreRef reapedStore; 567226633Sdim llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache; 568218887Sdim 569218887Sdimpublic: 570341825Sdim /// Construct a reaper object, which removes everything which is not 571239462Sdim /// live before we execute statement s in the given location context. 572239462Sdim /// 573239462Sdim /// If the statement is NULL, everything is this and parent contexts is 574239462Sdim /// considered live. 575243830Sdim /// If the stack frame context is NULL, everything on stack is considered 576243830Sdim /// dead. 577341825Sdim SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, 578341825Sdim SymbolManager &symmgr, StoreManager &storeMgr) 579341825Sdim : LCtx(Ctx), Loc(s), SymMgr(symmgr), reapedStore(nullptr, storeMgr) {} 580218887Sdim 581218887Sdim const LocationContext *getLocationContext() const { return LCtx; } 582218887Sdim 583218887Sdim bool isLive(SymbolRef sym); 584226633Sdim bool isLiveRegion(const MemRegion *region); 585234353Sdim bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const; 586226633Sdim bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const; 587218887Sdim 588341825Sdim /// Unconditionally marks a symbol as live. 589226633Sdim /// 590226633Sdim /// This should never be 591226633Sdim /// used by checkers, only by the state infrastructure such as the store and 592226633Sdim /// environment. Checkers should instead use metadata symbols and markInUse. 593218887Sdim void markLive(SymbolRef sym); 594218887Sdim 595341825Sdim /// Marks a symbol as important to a checker. 596226633Sdim /// 597226633Sdim /// For metadata symbols, 598226633Sdim /// this will keep the symbol alive as long as its associated region is also 599226633Sdim /// live. For other symbols, this has no effect; checkers are not permitted 600226633Sdim /// to influence the life of other symbols. This should be used before any 601226633Sdim /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback. 602218887Sdim void markInUse(SymbolRef sym); 603218887Sdim 604341825Sdim using region_iterator = RegionSetTy::const_iterator; 605341825Sdim 606226633Sdim region_iterator region_begin() const { return RegionRoots.begin(); } 607226633Sdim region_iterator region_end() const { return RegionRoots.end(); } 608218887Sdim 609341825Sdim /// Returns whether or not a symbol has been confirmed dead. 610226633Sdim /// 611226633Sdim /// This should only be called once all marking of dead symbols has completed. 612344779Sdim /// (For checkers, this means only in the checkDeadSymbols callback.) 613344779Sdim bool isDead(SymbolRef sym) { 614344779Sdim return !isLive(sym); 615218887Sdim } 616341825Sdim 617226633Sdim void markLive(const MemRegion *region); 618296417Sdim void markElementIndicesLive(const MemRegion *region); 619341825Sdim 620341825Sdim /// Set to the value of the symbolic store after 621226633Sdim /// StoreManager::removeDeadBindings has been called. 622226633Sdim void setReapedStore(StoreRef st) { reapedStore = st; } 623226633Sdim 624226633Sdimprivate: 625226633Sdim /// Mark the symbols dependent on the input symbol as live. 626226633Sdim void markDependentsLive(SymbolRef sym); 627218887Sdim}; 628218887Sdim 629218887Sdimclass SymbolVisitor { 630296417Sdimprotected: 631296417Sdim ~SymbolVisitor() = default; 632296417Sdim 633218887Sdimpublic: 634296417Sdim SymbolVisitor() = default; 635296417Sdim SymbolVisitor(const SymbolVisitor &) = default; 636296417Sdim SymbolVisitor(SymbolVisitor &&) {} 637296417Sdim 638341825Sdim /// A visitor method invoked by ProgramStateManager::scanReachableSymbols. 639226633Sdim /// 640226633Sdim /// The method returns \c true if symbols should continue be scanned and \c 641226633Sdim /// false otherwise. 642218887Sdim virtual bool VisitSymbol(SymbolRef sym) = 0; 643344779Sdim virtual bool VisitMemRegion(const MemRegion *) { return true; } 644218887Sdim}; 645218887Sdim 646341825Sdim} // namespace ento 647218887Sdim 648341825Sdim} // namespace clang 649218887Sdim 650341825Sdim#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H 651