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