clang/lib/StaticAnalyzer/Core/SymbolManager.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file defines SymbolManager, a class that manages symbolic values
  10 //  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/AST/StmtObjC.h"
  18 #include "clang/Analysis/Analyses/LiveVariables.h"
  19 #include "clang/Analysis/AnalysisDeclContext.h"
  20 #include "clang/Basic/LLVM.h"
  21 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
  22 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  23 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
  25 #include "llvm/ADT/FoldingSet.h"
  26 #include "llvm/ADT/STLExtras.h"
  27 #include "llvm/Support/Casting.h"
  28 #include "llvm/Support/Compiler.h"
  29 #include "llvm/Support/ErrorHandling.h"
  30 #include "llvm/Support/raw_ostream.h"
  31 #include <cassert>
  32
  33 using namespace clang;
  34 using namespace ento;
  35
  36 void SymExpr::anchor() {}
  37
  38 StringRef SymbolConjured::getKindStr() const { return "conj_$"; }
  39 StringRef SymbolDerived::getKindStr() const { return "derived_$"; }
  40 StringRef SymbolExtent::getKindStr() const { return "extent_$"; }
  41 StringRef SymbolMetadata::getKindStr() const { return "meta_$"; }
  42 StringRef SymbolRegionValue::getKindStr() const { return "reg_$"; }
  43
  44 LLVM_DUMP_METHOD void SymExpr::dump() const { dumpToStream(llvm::errs()); }
  45
  46 void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS, const SymExpr *Sym) {
  47   OS << '(';
  48   Sym->dumpToStream(OS);
  49   OS << ')';
  50 }
  51
  52 void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS,
  53                                      const llvm::APSInt &Value) {
  54   if (Value.isUnsigned())
  55     OS << Value.getZExtValue();
  56   else
  57     OS << Value.getSExtValue();
  58   if (Value.isUnsigned())
  59     OS << 'U';
  60 }
  61
  62 void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS,
  63                                      BinaryOperator::Opcode Op) {
  64   OS << ' ' << BinaryOperator::getOpcodeStr(Op) << ' ';
  65 }
  66
  67 void SymbolCast::dumpToStream(raw_ostream &os) const {
  68   os << '(' << ToTy << ") (";
  69   Operand->dumpToStream(os);
  70   os << ')';
  71 }
  72
  73 void UnarySymExpr::dumpToStream(raw_ostream &os) const {
  74   os << UnaryOperator::getOpcodeStr(Op);
  75   bool Binary = isa<BinarySymExpr>(Operand);
  76   if (Binary)
  77     os << '(';
  78   Operand->dumpToStream(os);
  79   if (Binary)
  80     os << ')';
  81 }
  82
  83 void SymbolConjured::dumpToStream(raw_ostream &os) const {
  84   os << getKindStr() << getSymbolID() << '{' << T << ", LC" << LCtx->getID();
  85   if (S)
  86     os << ", S" << S->getID(LCtx->getDecl()->getASTContext());
  87   else
  88     os << ", no stmt";
  89   os << ", #" << Count << '}';
  90 }
  91
  92 void SymbolDerived::dumpToStream(raw_ostream &os) const {
  93   os << getKindStr() << getSymbolID() << '{' << getParentSymbol() << ','
  94      << getRegion() << '}';
  95 }
  96
  97 void SymbolExtent::dumpToStream(raw_ostream &os) const {
  98   os << getKindStr() << getSymbolID() << '{' << getRegion() << '}';
  99 }
 100
 101 void SymbolMetadata::dumpToStream(raw_ostream &os) const {
 102   os << getKindStr() << getSymbolID() << '{' << getRegion() << ',' << T << '}';
 103 }
 104
 105 void SymbolData::anchor() {}
 106
 107 void SymbolRegionValue::dumpToStream(raw_ostream &os) const {
 108   os << getKindStr() << getSymbolID() << '<' << getType() << ' ' << R << '>';
 109 }
 110
 111 bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const {
 112   return itr == X.itr;
 113 }
 114
 115 bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const {
 116   return itr != X.itr;
 117 }
 118
 119 SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) {
 120   itr.push_back(SE);
 121 }
 122
 123 SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() {
 124   assert(!itr.empty() && "attempting to iterate on an 'end' iterator");
 125   expand();
 126   return *this;
 127 }
 128
 129 SymbolRef SymExpr::symbol_iterator::operator*() {
 130   assert(!itr.empty() && "attempting to dereference an 'end' iterator");
 131   return itr.back();
 132 }
 133
 134 void SymExpr::symbol_iterator::expand() {
 135   const SymExpr *SE = itr.pop_back_val();
 136
 137   switch (SE->getKind()) {
 138     case SymExpr::SymbolRegionValueKind:
 139     case SymExpr::SymbolConjuredKind:
 140     case SymExpr::SymbolDerivedKind:
 141     case SymExpr::SymbolExtentKind:
 142     case SymExpr::SymbolMetadataKind:
 143       return;
 144     case SymExpr::SymbolCastKind:
 145       itr.push_back(cast<SymbolCast>(SE)->getOperand());
 146       return;
 147     case SymExpr::UnarySymExprKind:
 148       itr.push_back(cast<UnarySymExpr>(SE)->getOperand());
 149       return;
 150     case SymExpr::SymIntExprKind:
 151       itr.push_back(cast<SymIntExpr>(SE)->getLHS());
 152       return;
 153     case SymExpr::IntSymExprKind:
 154       itr.push_back(cast<IntSymExpr>(SE)->getRHS());
 155       return;
 156     case SymExpr::SymSymExprKind: {
 157       const auto *x = cast<SymSymExpr>(SE);
 158       itr.push_back(x->getLHS());
 159       itr.push_back(x->getRHS());
 160       return;
 161     }
 162   }
 163   llvm_unreachable("unhandled expansion case");
 164 }
 165
 166 const SymbolRegionValue*
 167 SymbolManager::getRegionValueSymbol(const TypedValueRegion* R) {
 168   llvm::FoldingSetNodeID profile;
 169   SymbolRegionValue::Profile(profile, R);
 170   void *InsertPos;
 171   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
 172   if (!SD) {
 173     SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>();
 174     new (SD) SymbolRegionValue(SymbolCounter, R);
 175     DataSet.InsertNode(SD, InsertPos);
 176     ++SymbolCounter;
 177   }
 178
 179   return cast<SymbolRegionValue>(SD);
 180 }
 181
 182 const SymbolConjured* SymbolManager::conjureSymbol(const Stmt *E,
 183                                                    const LocationContext *LCtx,
 184                                                    QualType T,
 185                                                    unsigned Count,
 186                                                    const void *SymbolTag) {
 187   llvm::FoldingSetNodeID profile;
 188   SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag);
 189   void *InsertPos;
 190   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
 191   if (!SD) {
 192     SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>();
 193     new (SD) SymbolConjured(SymbolCounter, E, LCtx, T, Count, SymbolTag);
 194     DataSet.InsertNode(SD, InsertPos);
 195     ++SymbolCounter;
 196   }
 197
 198   return cast<SymbolConjured>(SD);
 199 }
 200
 201 const SymbolDerived*
 202 SymbolManager::getDerivedSymbol(SymbolRef parentSymbol,
 203                                 const TypedValueRegion *R) {
 204   llvm::FoldingSetNodeID profile;
 205   SymbolDerived::Profile(profile, parentSymbol, R);
 206   void *InsertPos;
 207   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
 208   if (!SD) {
 209     SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>();
 210     new (SD) SymbolDerived(SymbolCounter, parentSymbol, R);
 211     DataSet.InsertNode(SD, InsertPos);
 212     ++SymbolCounter;
 213   }
 214
 215   return cast<SymbolDerived>(SD);
 216 }
 217
 218 const SymbolExtent*
 219 SymbolManager::getExtentSymbol(const SubRegion *R) {
 220   llvm::FoldingSetNodeID profile;
 221   SymbolExtent::Profile(profile, R);
 222   void *InsertPos;
 223   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
 224   if (!SD) {
 225     SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>();
 226     new (SD) SymbolExtent(SymbolCounter, R);
 227     DataSet.InsertNode(SD, InsertPos);
 228     ++SymbolCounter;
 229   }
 230
 231   return cast<SymbolExtent>(SD);
 232 }
 233
 234 const SymbolMetadata *
 235 SymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T,
 236                                  const LocationContext *LCtx,
 237                                  unsigned Count, const void *SymbolTag) {
 238   llvm::FoldingSetNodeID profile;
 239   SymbolMetadata::Profile(profile, R, S, T, LCtx, Count, SymbolTag);
 240   void *InsertPos;
 241   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
 242   if (!SD) {
 243     SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>();
 244     new (SD) SymbolMetadata(SymbolCounter, R, S, T, LCtx, Count, SymbolTag);
 245     DataSet.InsertNode(SD, InsertPos);
 246     ++SymbolCounter;
 247   }
 248
 249   return cast<SymbolMetadata>(SD);
 250 }
 251
 252 const SymbolCast*
 253 SymbolManager::getCastSymbol(const SymExpr *Op,
 254                              QualType From, QualType To) {
 255   llvm::FoldingSetNodeID ID;
 256   SymbolCast::Profile(ID, Op, From, To);
 257   void *InsertPos;
 258   SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
 259   if (!data) {
 260     data = (SymbolCast*) BPAlloc.Allocate<SymbolCast>();
 261     new (data) SymbolCast(Op, From, To);
 262     DataSet.InsertNode(data, InsertPos);
 263   }
 264
 265   return cast<SymbolCast>(data);
 266 }
 267
 268 const SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs,
 269                                                BinaryOperator::Opcode op,
 270                                                const llvm::APSInt& v,
 271                                                QualType t) {
 272   llvm::FoldingSetNodeID ID;
 273   SymIntExpr::Profile(ID, lhs, op, v, t);
 274   void *InsertPos;
 275   SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
 276
 277   if (!data) {
 278     data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>();
 279     new (data) SymIntExpr(lhs, op, v, t);
 280     DataSet.InsertNode(data, InsertPos);
 281   }
 282
 283   return cast<SymIntExpr>(data);
 284 }
 285
 286 const IntSymExpr *SymbolManager::getIntSymExpr(const llvm::APSInt& lhs,
 287                                                BinaryOperator::Opcode op,
 288                                                const SymExpr *rhs,
 289                                                QualType t) {
 290   llvm::FoldingSetNodeID ID;
 291   IntSymExpr::Profile(ID, lhs, op, rhs, t);
 292   void *InsertPos;
 293   SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
 294
 295   if (!data) {
 296     data = (IntSymExpr*) BPAlloc.Allocate<IntSymExpr>();
 297     new (data) IntSymExpr(lhs, op, rhs, t);
 298     DataSet.InsertNode(data, InsertPos);
 299   }
 300
 301   return cast<IntSymExpr>(data);
 302 }
 303
 304 const SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs,
 305                                                BinaryOperator::Opcode op,
 306                                                const SymExpr *rhs,
 307                                                QualType t) {
 308   llvm::FoldingSetNodeID ID;
 309   SymSymExpr::Profile(ID, lhs, op, rhs, t);
 310   void *InsertPos;
 311   SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
 312
 313   if (!data) {
 314     data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>();
 315     new (data) SymSymExpr(lhs, op, rhs, t);
 316     DataSet.InsertNode(data, InsertPos);
 317   }
 318
 319   return cast<SymSymExpr>(data);
 320 }
 321
 322 const UnarySymExpr *SymbolManager::getUnarySymExpr(const SymExpr *Operand,
 323                                                    UnaryOperator::Opcode Opc,
 324                                                    QualType T) {
 325   llvm::FoldingSetNodeID ID;
 326   UnarySymExpr::Profile(ID, Operand, Opc, T);
 327   void *InsertPos;
 328   SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
 329   if (!data) {
 330     data = (UnarySymExpr *)BPAlloc.Allocate<UnarySymExpr>();
 331     new (data) UnarySymExpr(Operand, Opc, T);
 332     DataSet.InsertNode(data, InsertPos);
 333   }
 334
 335   return cast<UnarySymExpr>(data);
 336 }
 337
 338 QualType SymbolConjured::getType() const {
 339   return T;
 340 }
 341
 342 QualType SymbolDerived::getType() const {
 343   return R->getValueType();
 344 }
 345
 346 QualType SymbolExtent::getType() const {
 347   ASTContext &Ctx = R->getMemRegionManager().getContext();
 348   return Ctx.getSizeType();
 349 }
 350
 351 QualType SymbolMetadata::getType() const {
 352   return T;
 353 }
 354
 355 QualType SymbolRegionValue::getType() const {
 356   return R->getValueType();
 357 }
 358
 359 bool SymbolManager::canSymbolicate(QualType T) {
 360   T = T.getCanonicalType();
 361
 362   if (Loc::isLocType(T))
 363     return true;
 364
 365   if (T->isIntegralOrEnumerationType())
 366     return true;
 367
 368   if (T->isRecordType() && !T->isUnionType())
 369     return true;
 370
 371   return false;
 372 }
 373
 374 void SymbolManager::addSymbolDependency(const SymbolRef Primary,
 375                                         const SymbolRef Dependent) {
 376   auto &dependencies = SymbolDependencies[Primary];
 377   if (!dependencies) {
 378     dependencies = std::make_unique<SymbolRefSmallVectorTy>();
 379   }
 380   dependencies->push_back(Dependent);
 381 }
 382
 383 const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols(
 384                                                      const SymbolRef Primary) {
 385   SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary);
 386   if (I == SymbolDependencies.end())
 387     return nullptr;
 388   return I->second.get();
 389 }
 390
 391 void SymbolReaper::markDependentsLive(SymbolRef sym) {
 392   // Do not mark dependents more then once.
 393   SymbolMapTy::iterator LI = TheLiving.find(sym);
 394   assert(LI != TheLiving.end() && "The primary symbol is not live.");
 395   if (LI->second == HaveMarkedDependents)
 396     return;
 397   LI->second = HaveMarkedDependents;
 398
 399   if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) {
 400     for (const auto I : *Deps) {
 401       if (TheLiving.find(I) != TheLiving.end())
 402         continue;
 403       markLive(I);
 404     }
 405   }
 406 }
 407
 408 void SymbolReaper::markLive(SymbolRef sym) {
 409   TheLiving[sym] = NotProcessed;
 410   markDependentsLive(sym);
 411 }
 412
 413 void SymbolReaper::markLive(const MemRegion *region) {
 414   LiveRegionRoots.insert(region->getBaseRegion());
 415   markElementIndicesLive(region);
 416 }
 417
 418 void SymbolReaper::markLazilyCopied(const clang::ento::MemRegion *region) {
 419   LazilyCopiedRegionRoots.insert(region->getBaseRegion());
 420 }
 421
 422 void SymbolReaper::markElementIndicesLive(const MemRegion *region) {
 423   for (auto SR = dyn_cast<SubRegion>(region); SR;
 424        SR = dyn_cast<SubRegion>(SR->getSuperRegion())) {
 425     if (const auto ER = dyn_cast<ElementRegion>(SR)) {
 426       SVal Idx = ER->getIndex();
 427       for (auto SI = Idx.symbol_begin(), SE = Idx.symbol_end(); SI != SE; ++SI)
 428         markLive(*SI);
 429     }
 430   }
 431 }
 432
 433 void SymbolReaper::markInUse(SymbolRef sym) {
 434   if (isa<SymbolMetadata>(sym))
 435     MetadataInUse.insert(sym);
 436 }
 437
 438 bool SymbolReaper::isLiveRegion(const MemRegion *MR) {
 439   // TODO: For now, liveness of a memory region is equivalent to liveness of its
 440   // base region. In fact we can do a bit better: say, if a particular FieldDecl
 441   // is not used later in the path, we can diagnose a leak of a value within
 442   // that field earlier than, say, the variable that contains the field dies.
 443   MR = MR->getBaseRegion();
 444   if (LiveRegionRoots.count(MR))
 445     return true;
 446
 447   if (const auto *SR = dyn_cast<SymbolicRegion>(MR))
 448     return isLive(SR->getSymbol());
 449
 450   if (const auto *VR = dyn_cast<VarRegion>(MR))
 451     return isLive(VR, true);
 452
 453   // FIXME: This is a gross over-approximation. What we really need is a way to
 454   // tell if anything still refers to this region. Unlike SymbolicRegions,
 455   // AllocaRegions don't have associated symbols, though, so we don't actually
 456   // have a way to track their liveness.
 457   return isa<AllocaRegion, CXXThisRegion, MemSpaceRegion, CodeTextRegion>(MR);
 458 }
 459
 460 bool SymbolReaper::isLazilyCopiedRegion(const MemRegion *MR) const {
 461   // TODO: See comment in isLiveRegion.
 462   return LazilyCopiedRegionRoots.count(MR->getBaseRegion());
 463 }
 464
 465 bool SymbolReaper::isReadableRegion(const MemRegion *MR) {
 466   return isLiveRegion(MR) || isLazilyCopiedRegion(MR);
 467 }
 468
 469 bool SymbolReaper::isLive(SymbolRef sym) {
 470   if (TheLiving.count(sym)) {
 471     markDependentsLive(sym);
 472     return true;
 473   }
 474
 475   bool KnownLive;
 476
 477   switch (sym->getKind()) {
 478   case SymExpr::SymbolRegionValueKind:
 479     KnownLive = isReadableRegion(cast<SymbolRegionValue>(sym)->getRegion());
 480     break;
 481   case SymExpr::SymbolConjuredKind:
 482     KnownLive = false;
 483     break;
 484   case SymExpr::SymbolDerivedKind:
 485     KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol());
 486     break;
 487   case SymExpr::SymbolExtentKind:
 488     KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion());
 489     break;
 490   case SymExpr::SymbolMetadataKind:
 491     KnownLive = MetadataInUse.count(sym) &&
 492                 isLiveRegion(cast<SymbolMetadata>(sym)->getRegion());
 493     if (KnownLive)
 494       MetadataInUse.erase(sym);
 495     break;
 496   case SymExpr::SymIntExprKind:
 497     KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS());
 498     break;
 499   case SymExpr::IntSymExprKind:
 500     KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS());
 501     break;
 502   case SymExpr::SymSymExprKind:
 503     KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) &&
 504                 isLive(cast<SymSymExpr>(sym)->getRHS());
 505     break;
 506   case SymExpr::SymbolCastKind:
 507     KnownLive = isLive(cast<SymbolCast>(sym)->getOperand());
 508     break;
 509   case SymExpr::UnarySymExprKind:
 510     KnownLive = isLive(cast<UnarySymExpr>(sym)->getOperand());
 511     break;
 512   }
 513
 514   if (KnownLive)
 515     markLive(sym);
 516
 517   return KnownLive;
 518 }
 519
 520 bool
 521 SymbolReaper::isLive(const Expr *ExprVal, const LocationContext *ELCtx) const {
 522   if (LCtx == nullptr)
 523     return false;
 524
 525   if (LCtx != ELCtx) {
 526     // If the reaper's location context is a parent of the expression's
 527     // location context, then the expression value is now "out of scope".
 528     if (LCtx->isParentOf(ELCtx))
 529       return false;
 530     return true;
 531   }
 532
 533   // If no statement is provided, everything in this and parent contexts is
 534   // live.
 535   if (!Loc)
 536     return true;
 537
 538   return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal);
 539 }
 540
 541 bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
 542   const StackFrameContext *VarContext = VR->getStackFrame();
 543
 544   if (!VarContext)
 545     return true;
 546
 547   if (!LCtx)
 548     return false;
 549   const StackFrameContext *CurrentContext = LCtx->getStackFrame();
 550
 551   if (VarContext == CurrentContext) {
 552     // If no statement is provided, everything is live.
 553     if (!Loc)
 554       return true;
 555
 556     // Anonymous parameters of an inheriting constructor are live for the entire
 557     // duration of the constructor.
 558     if (isa<CXXInheritedCtorInitExpr>(Loc))
 559       return true;
 560
 561     if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl()))
 562       return true;
 563
 564     if (!includeStoreBindings)
 565       return false;
 566
 567     unsigned &cachedQuery =
 568       const_cast<SymbolReaper *>(this)->includedRegionCache[VR];
 569
 570     if (cachedQuery) {
 571       return cachedQuery == 1;
 572     }
 573
 574     // Query the store to see if the region occurs in any live bindings.
 575     if (Store store = reapedStore.getStore()) {
 576       bool hasRegion =
 577         reapedStore.getStoreManager().includedInBindings(store, VR);
 578       cachedQuery = hasRegion ? 1 : 2;
 579       return hasRegion;
 580     }
 581
 582     return false;
 583   }
 584
 585   return VarContext->isParentOf(CurrentContext);
 586 }