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