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 = new (BPAlloc) SymbolRegionValue(SymbolCounter, R);
 174     DataSet.InsertNode(SD, InsertPos);
 175     ++SymbolCounter;
 176   }
 177
 178   return cast<SymbolRegionValue>(SD);
 179 }
 180
 181 const SymbolConjured* SymbolManager::conjureSymbol(const Stmt *E,
 182                                                    const LocationContext *LCtx,
 183                                                    QualType T,
 184                                                    unsigned Count,
 185                                                    const void *SymbolTag) {
 186   llvm::FoldingSetNodeID profile;
 187   SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag);
 188   void *InsertPos;
 189   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
 190   if (!SD) {
 191     SD = new (BPAlloc) SymbolConjured(SymbolCounter, E, LCtx, T, Count, SymbolTag);
 192     DataSet.InsertNode(SD, InsertPos);
 193     ++SymbolCounter;
 194   }
 195
 196   return cast<SymbolConjured>(SD);
 197 }
 198
 199 const SymbolDerived*
 200 SymbolManager::getDerivedSymbol(SymbolRef parentSymbol,
 201                                 const TypedValueRegion *R) {
 202   llvm::FoldingSetNodeID profile;
 203   SymbolDerived::Profile(profile, parentSymbol, R);
 204   void *InsertPos;
 205   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
 206   if (!SD) {
 207     SD = new (BPAlloc) SymbolDerived(SymbolCounter, parentSymbol, R);
 208     DataSet.InsertNode(SD, InsertPos);
 209     ++SymbolCounter;
 210   }
 211
 212   return cast<SymbolDerived>(SD);
 213 }
 214
 215 const SymbolExtent*
 216 SymbolManager::getExtentSymbol(const SubRegion *R) {
 217   llvm::FoldingSetNodeID profile;
 218   SymbolExtent::Profile(profile, R);
 219   void *InsertPos;
 220   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
 221   if (!SD) {
 222     SD = new (BPAlloc) SymbolExtent(SymbolCounter, R);
 223     DataSet.InsertNode(SD, InsertPos);
 224     ++SymbolCounter;
 225   }
 226
 227   return cast<SymbolExtent>(SD);
 228 }
 229
 230 const SymbolMetadata *
 231 SymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T,
 232                                  const LocationContext *LCtx,
 233                                  unsigned Count, const void *SymbolTag) {
 234   llvm::FoldingSetNodeID profile;
 235   SymbolMetadata::Profile(profile, R, S, T, LCtx, Count, SymbolTag);
 236   void *InsertPos;
 237   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
 238   if (!SD) {
 239     SD = new (BPAlloc) SymbolMetadata(SymbolCounter, R, S, T, LCtx, Count, SymbolTag);
 240     DataSet.InsertNode(SD, InsertPos);
 241     ++SymbolCounter;
 242   }
 243
 244   return cast<SymbolMetadata>(SD);
 245 }
 246
 247 const SymbolCast*
 248 SymbolManager::getCastSymbol(const SymExpr *Op,
 249                              QualType From, QualType To) {
 250   llvm::FoldingSetNodeID ID;
 251   SymbolCast::Profile(ID, Op, From, To);
 252   void *InsertPos;
 253   SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
 254   if (!data) {
 255     data = new (BPAlloc) SymbolCast(Op, From, To);
 256     DataSet.InsertNode(data, InsertPos);
 257   }
 258
 259   return cast<SymbolCast>(data);
 260 }
 261
 262 const SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs,
 263                                                BinaryOperator::Opcode op,
 264                                                const llvm::APSInt& v,
 265                                                QualType t) {
 266   llvm::FoldingSetNodeID ID;
 267   SymIntExpr::Profile(ID, lhs, op, v, t);
 268   void *InsertPos;
 269   SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
 270
 271   if (!data) {
 272     data = new (BPAlloc) SymIntExpr(lhs, op, v, t);
 273     DataSet.InsertNode(data, InsertPos);
 274   }
 275
 276   return cast<SymIntExpr>(data);
 277 }
 278
 279 const IntSymExpr *SymbolManager::getIntSymExpr(const llvm::APSInt& lhs,
 280                                                BinaryOperator::Opcode op,
 281                                                const SymExpr *rhs,
 282                                                QualType t) {
 283   llvm::FoldingSetNodeID ID;
 284   IntSymExpr::Profile(ID, lhs, op, rhs, t);
 285   void *InsertPos;
 286   SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
 287
 288   if (!data) {
 289     data = new (BPAlloc) IntSymExpr(lhs, op, rhs, t);
 290     DataSet.InsertNode(data, InsertPos);
 291   }
 292
 293   return cast<IntSymExpr>(data);
 294 }
 295
 296 const SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs,
 297                                                BinaryOperator::Opcode op,
 298                                                const SymExpr *rhs,
 299                                                QualType t) {
 300   llvm::FoldingSetNodeID ID;
 301   SymSymExpr::Profile(ID, lhs, op, rhs, t);
 302   void *InsertPos;
 303   SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
 304
 305   if (!data) {
 306     data = new (BPAlloc) SymSymExpr(lhs, op, rhs, t);
 307     DataSet.InsertNode(data, InsertPos);
 308   }
 309
 310   return cast<SymSymExpr>(data);
 311 }
 312
 313 const UnarySymExpr *SymbolManager::getUnarySymExpr(const SymExpr *Operand,
 314                                                    UnaryOperator::Opcode Opc,
 315                                                    QualType T) {
 316   llvm::FoldingSetNodeID ID;
 317   UnarySymExpr::Profile(ID, Operand, Opc, T);
 318   void *InsertPos;
 319   SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
 320   if (!data) {
 321     data = new (BPAlloc) UnarySymExpr(Operand, Opc, T);
 322     DataSet.InsertNode(data, InsertPos);
 323   }
 324
 325   return cast<UnarySymExpr>(data);
 326 }
 327
 328 QualType SymbolConjured::getType() const {
 329   return T;
 330 }
 331
 332 QualType SymbolDerived::getType() const {
 333   return R->getValueType();
 334 }
 335
 336 QualType SymbolExtent::getType() const {
 337   ASTContext &Ctx = R->getMemRegionManager().getContext();
 338   return Ctx.getSizeType();
 339 }
 340
 341 QualType SymbolMetadata::getType() const {
 342   return T;
 343 }
 344
 345 QualType SymbolRegionValue::getType() const {
 346   return R->getValueType();
 347 }
 348
 349 bool SymbolManager::canSymbolicate(QualType T) {
 350   T = T.getCanonicalType();
 351
 352   if (Loc::isLocType(T))
 353     return true;
 354
 355   if (T->isIntegralOrEnumerationType())
 356     return true;
 357
 358   if (T->isRecordType() && !T->isUnionType())
 359     return true;
 360
 361   return false;
 362 }
 363
 364 void SymbolManager::addSymbolDependency(const SymbolRef Primary,
 365                                         const SymbolRef Dependent) {
 366   auto &dependencies = SymbolDependencies[Primary];
 367   if (!dependencies) {
 368     dependencies = std::make_unique<SymbolRefSmallVectorTy>();
 369   }
 370   dependencies->push_back(Dependent);
 371 }
 372
 373 const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols(
 374                                                      const SymbolRef Primary) {
 375   SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary);
 376   if (I == SymbolDependencies.end())
 377     return nullptr;
 378   return I->second.get();
 379 }
 380
 381 void SymbolReaper::markDependentsLive(SymbolRef sym) {
 382   // Do not mark dependents more then once.
 383   SymbolMapTy::iterator LI = TheLiving.find(sym);
 384   assert(LI != TheLiving.end() && "The primary symbol is not live.");
 385   if (LI->second == HaveMarkedDependents)
 386     return;
 387   LI->second = HaveMarkedDependents;
 388
 389   if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) {
 390     for (const auto I : *Deps) {
 391       if (TheLiving.contains(I))
 392         continue;
 393       markLive(I);
 394     }
 395   }
 396 }
 397
 398 void SymbolReaper::markLive(SymbolRef sym) {
 399   TheLiving[sym] = NotProcessed;
 400   markDependentsLive(sym);
 401 }
 402
 403 void SymbolReaper::markLive(const MemRegion *region) {
 404   LiveRegionRoots.insert(region->getBaseRegion());
 405   markElementIndicesLive(region);
 406 }
 407
 408 void SymbolReaper::markLazilyCopied(const clang::ento::MemRegion *region) {
 409   LazilyCopiedRegionRoots.insert(region->getBaseRegion());
 410 }
 411
 412 void SymbolReaper::markElementIndicesLive(const MemRegion *region) {
 413   for (auto SR = dyn_cast<SubRegion>(region); SR;
 414        SR = dyn_cast<SubRegion>(SR->getSuperRegion())) {
 415     if (const auto ER = dyn_cast<ElementRegion>(SR)) {
 416       SVal Idx = ER->getIndex();
 417       for (SymbolRef Sym : Idx.symbols())
 418         markLive(Sym);
 419     }
 420   }
 421 }
 422
 423 void SymbolReaper::markInUse(SymbolRef sym) {
 424   if (isa<SymbolMetadata>(sym))
 425     MetadataInUse.insert(sym);
 426 }
 427
 428 bool SymbolReaper::isLiveRegion(const MemRegion *MR) {
 429   // TODO: For now, liveness of a memory region is equivalent to liveness of its
 430   // base region. In fact we can do a bit better: say, if a particular FieldDecl
 431   // is not used later in the path, we can diagnose a leak of a value within
 432   // that field earlier than, say, the variable that contains the field dies.
 433   MR = MR->getBaseRegion();
 434   if (LiveRegionRoots.count(MR))
 435     return true;
 436
 437   if (const auto *SR = dyn_cast<SymbolicRegion>(MR))
 438     return isLive(SR->getSymbol());
 439
 440   if (const auto *VR = dyn_cast<VarRegion>(MR))
 441     return isLive(VR, true);
 442
 443   // FIXME: This is a gross over-approximation. What we really need is a way to
 444   // tell if anything still refers to this region. Unlike SymbolicRegions,
 445   // AllocaRegions don't have associated symbols, though, so we don't actually
 446   // have a way to track their liveness.
 447   return isa<AllocaRegion, CXXThisRegion, MemSpaceRegion, CodeTextRegion>(MR);
 448 }
 449
 450 bool SymbolReaper::isLazilyCopiedRegion(const MemRegion *MR) const {
 451   // TODO: See comment in isLiveRegion.
 452   return LazilyCopiedRegionRoots.count(MR->getBaseRegion());
 453 }
 454
 455 bool SymbolReaper::isReadableRegion(const MemRegion *MR) {
 456   return isLiveRegion(MR) || isLazilyCopiedRegion(MR);
 457 }
 458
 459 bool SymbolReaper::isLive(SymbolRef sym) {
 460   if (TheLiving.count(sym)) {
 461     markDependentsLive(sym);
 462     return true;
 463   }
 464
 465   bool KnownLive;
 466
 467   switch (sym->getKind()) {
 468   case SymExpr::SymbolRegionValueKind:
 469     KnownLive = isReadableRegion(cast<SymbolRegionValue>(sym)->getRegion());
 470     break;
 471   case SymExpr::SymbolConjuredKind:
 472     KnownLive = false;
 473     break;
 474   case SymExpr::SymbolDerivedKind:
 475     KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol());
 476     break;
 477   case SymExpr::SymbolExtentKind:
 478     KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion());
 479     break;
 480   case SymExpr::SymbolMetadataKind:
 481     KnownLive = MetadataInUse.count(sym) &&
 482                 isLiveRegion(cast<SymbolMetadata>(sym)->getRegion());
 483     if (KnownLive)
 484       MetadataInUse.erase(sym);
 485     break;
 486   case SymExpr::SymIntExprKind:
 487     KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS());
 488     break;
 489   case SymExpr::IntSymExprKind:
 490     KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS());
 491     break;
 492   case SymExpr::SymSymExprKind:
 493     KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) &&
 494                 isLive(cast<SymSymExpr>(sym)->getRHS());
 495     break;
 496   case SymExpr::SymbolCastKind:
 497     KnownLive = isLive(cast<SymbolCast>(sym)->getOperand());
 498     break;
 499   case SymExpr::UnarySymExprKind:
 500     KnownLive = isLive(cast<UnarySymExpr>(sym)->getOperand());
 501     break;
 502   }
 503
 504   if (KnownLive)
 505     markLive(sym);
 506
 507   return KnownLive;
 508 }
 509
 510 bool
 511 SymbolReaper::isLive(const Expr *ExprVal, const LocationContext *ELCtx) const {
 512   if (LCtx == nullptr)
 513     return false;
 514
 515   if (LCtx != ELCtx) {
 516     // If the reaper's location context is a parent of the expression's
 517     // location context, then the expression value is now "out of scope".
 518     if (LCtx->isParentOf(ELCtx))
 519       return false;
 520     return true;
 521   }
 522
 523   // If no statement is provided, everything in this and parent contexts is
 524   // live.
 525   if (!Loc)
 526     return true;
 527
 528   return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal);
 529 }
 530
 531 bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
 532   const StackFrameContext *VarContext = VR->getStackFrame();
 533
 534   if (!VarContext)
 535     return true;
 536
 537   if (!LCtx)
 538     return false;
 539   const StackFrameContext *CurrentContext = LCtx->getStackFrame();
 540
 541   if (VarContext == CurrentContext) {
 542     // If no statement is provided, everything is live.
 543     if (!Loc)
 544       return true;
 545
 546     // Anonymous parameters of an inheriting constructor are live for the entire
 547     // duration of the constructor.
 548     if (isa<CXXInheritedCtorInitExpr>(Loc))
 549       return true;
 550
 551     if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl()))
 552       return true;
 553
 554     if (!includeStoreBindings)
 555       return false;
 556
 557     unsigned &cachedQuery =
 558       const_cast<SymbolReaper *>(this)->includedRegionCache[VR];
 559
 560     if (cachedQuery) {
 561       return cachedQuery == 1;
 562     }
 563
 564     // Query the store to see if the region occurs in any live bindings.
 565     if (Store store = reapedStore.getStore()) {
 566       bool hasRegion =
 567         reapedStore.getStoreManager().includedInBindings(store, VR);
 568       cachedQuery = hasRegion ? 1 : 2;
 569       return hasRegion;
 570     }
 571
 572     return false;
 573   }
 574
 575   return VarContext->isParentOf(CurrentContext);
 576 }