Home | History | Annotate | Download | only in Core 
      1 //= RValues.cpp - Abstract RValues for Path-Sens. Value Tracking -*- C++ -*-==//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 //  This file defines SVal, Loc, and NonLoc, classes that represent
     11 //  abstract r-values for use with path-sensitive value tracking.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
     16 #include "clang/AST/ExprObjC.h"
     17 #include "clang/Basic/IdentifierTable.h"
     18 #include "llvm/Support/raw_ostream.h"
     19 using namespace clang;
     20 using namespace ento;
     21 using llvm::APSInt;
     22 
     23 //===----------------------------------------------------------------------===//
     24 // Symbol iteration within an SVal.
     25 //===----------------------------------------------------------------------===//
     26 
     27 
     28 //===----------------------------------------------------------------------===//
     29 // Utility methods.
     30 //===----------------------------------------------------------------------===//
     31 
     32 bool SVal::hasConjuredSymbol() const {
     33   if (Optional<nonloc::SymbolVal> SV = getAs<nonloc::SymbolVal>()) {
     34     SymbolRef sym = SV->getSymbol();
     35     if (isa<SymbolConjured>(sym))
     36       return true;
     37   }
     38 
     39   if (Optional<loc::MemRegionVal> RV = getAs<loc::MemRegionVal>()) {
     40     const MemRegion *R = RV->getRegion();
     41     if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
     42       SymbolRef sym = SR->getSymbol();
     43       if (isa<SymbolConjured>(sym))
     44         return true;
     45     }
     46   }
     47 
     48   return false;
     49 }
     50 
     51 const FunctionDecl *SVal::getAsFunctionDecl() const {
     52   if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>()) {
     53     const MemRegion* R = X->getRegion();
     54     if (const FunctionTextRegion *CTR = R->getAs<FunctionTextRegion>())
     55       if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CTR->getDecl()))
     56         return FD;
     57   }
     58 
     59   return nullptr;
     60 }
     61 
     62 /// \brief If this SVal is a location (subclasses Loc) and wraps a symbol,
     63 /// return that SymbolRef.  Otherwise return 0.
     64 ///
     65 /// Implicit casts (ex: void* -> char*) can turn Symbolic region into Element
     66 /// region. If that is the case, gets the underlining region.
     67 /// When IncludeBaseRegions is set to true and the SubRegion is non-symbolic,
     68 /// the first symbolic parent region is returned.
     69 SymbolRef SVal::getAsLocSymbol(bool IncludeBaseRegions) const {
     70   // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
     71   if (Optional<nonloc::LocAsInteger> X = getAs<nonloc::LocAsInteger>())
     72     return X->getLoc().getAsLocSymbol();
     73 
     74   if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>()) {
     75     const MemRegion *R = X->getRegion();
     76     if (const SymbolicRegion *SymR = IncludeBaseRegions ?
     77                                       R->getSymbolicBase() :
     78                                       dyn_cast<SymbolicRegion>(R->StripCasts()))
     79       return SymR->getSymbol();
     80   }
     81   return nullptr;
     82 }
     83 
     84 /// Get the symbol in the SVal or its base region.
     85 SymbolRef SVal::getLocSymbolInBase() const {
     86   Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>();
     87 
     88   if (!X)
     89     return nullptr;
     90 
     91   const MemRegion *R = X->getRegion();
     92 
     93   while (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
     94     if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(SR))
     95       return SymR->getSymbol();
     96     else
     97       R = SR->getSuperRegion();
     98   }
     99 
    100   return nullptr;
    101 }
    102 
    103 // TODO: The next 3 functions have to be simplified.
    104 
    105 /// \brief If this SVal wraps a symbol return that SymbolRef.
    106 /// Otherwise, return 0.
    107 ///
    108 /// Casts are ignored during lookup.
    109 /// \param IncludeBaseRegions The boolean that controls whether the search
    110 /// should continue to the base regions if the region is not symbolic.
    111 SymbolRef SVal::getAsSymbol(bool IncludeBaseRegion) const {
    112   // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
    113   if (Optional<nonloc::SymbolVal> X = getAs<nonloc::SymbolVal>())
    114     return X->getSymbol();
    115 
    116   return getAsLocSymbol(IncludeBaseRegion);
    117 }
    118 
    119 /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
    120 ///  return that expression.  Otherwise return NULL.
    121 const SymExpr *SVal::getAsSymbolicExpression() const {
    122   if (Optional<nonloc::SymbolVal> X = getAs<nonloc::SymbolVal>())
    123     return X->getSymbol();
    124 
    125   return getAsSymbol();
    126 }
    127 
    128 const SymExpr* SVal::getAsSymExpr() const {
    129   const SymExpr* Sym = getAsSymbol();
    130   if (!Sym)
    131     Sym = getAsSymbolicExpression();
    132   return Sym;
    133 }
    134 
    135 const MemRegion *SVal::getAsRegion() const {
    136   if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>())
    137     return X->getRegion();
    138 
    139   if (Optional<nonloc::LocAsInteger> X = getAs<nonloc::LocAsInteger>())
    140     return X->getLoc().getAsRegion();
    141 
    142   return nullptr;
    143 }
    144 
    145 const MemRegion *loc::MemRegionVal::stripCasts(bool StripBaseCasts) const {
    146   const MemRegion *R = getRegion();
    147   return R ?  R->StripCasts(StripBaseCasts) : nullptr;
    148 }
    149 
    150 const void *nonloc::LazyCompoundVal::getStore() const {
    151   return static_cast<const LazyCompoundValData*>(Data)->getStore();
    152 }
    153 
    154 const TypedValueRegion *nonloc::LazyCompoundVal::getRegion() const {
    155   return static_cast<const LazyCompoundValData*>(Data)->getRegion();
    156 }
    157 
    158 //===----------------------------------------------------------------------===//
    159 // Other Iterators.
    160 //===----------------------------------------------------------------------===//
    161 
    162 nonloc::CompoundVal::iterator nonloc::CompoundVal::begin() const {
    163   return getValue()->begin();
    164 }
    165 
    166 nonloc::CompoundVal::iterator nonloc::CompoundVal::end() const {
    167   return getValue()->end();
    168 }
    169 
    170 //===----------------------------------------------------------------------===//
    171 // Useful predicates.
    172 //===----------------------------------------------------------------------===//
    173 
    174 bool SVal::isConstant() const {
    175   return getAs<nonloc::ConcreteInt>() || getAs<loc::ConcreteInt>();
    176 }
    177 
    178 bool SVal::isConstant(int I) const {
    179   if (Optional<loc::ConcreteInt> LV = getAs<loc::ConcreteInt>())
    180     return LV->getValue() == I;
    181   if (Optional<nonloc::ConcreteInt> NV = getAs<nonloc::ConcreteInt>())
    182     return NV->getValue() == I;
    183   return false;
    184 }
    185 
    186 bool SVal::isZeroConstant() const {
    187   return isConstant(0);
    188 }
    189 
    190 
    191 //===----------------------------------------------------------------------===//
    192 // Transfer function dispatch for Non-Locs.
    193 //===----------------------------------------------------------------------===//
    194 
    195 SVal nonloc::ConcreteInt::evalBinOp(SValBuilder &svalBuilder,
    196                                     BinaryOperator::Opcode Op,
    197                                     const nonloc::ConcreteInt& R) const {
    198   const llvm::APSInt* X =
    199     svalBuilder.getBasicValueFactory().evalAPSInt(Op, getValue(), R.getValue());
    200 
    201   if (X)
    202     return nonloc::ConcreteInt(*X);
    203   else
    204     return UndefinedVal();
    205 }
    206 
    207 nonloc::ConcreteInt
    208 nonloc::ConcreteInt::evalComplement(SValBuilder &svalBuilder) const {
    209   return svalBuilder.makeIntVal(~getValue());
    210 }
    211 
    212 nonloc::ConcreteInt
    213 nonloc::ConcreteInt::evalMinus(SValBuilder &svalBuilder) const {
    214   return svalBuilder.makeIntVal(-getValue());
    215 }
    216 
    217 //===----------------------------------------------------------------------===//
    218 // Transfer function dispatch for Locs.
    219 //===----------------------------------------------------------------------===//
    220 
    221 SVal loc::ConcreteInt::evalBinOp(BasicValueFactory& BasicVals,
    222                                  BinaryOperator::Opcode Op,
    223                                  const loc::ConcreteInt& R) const {
    224 
    225   assert(BinaryOperator::isComparisonOp(Op) || Op == BO_Sub);
    226 
    227   const llvm::APSInt *X = BasicVals.evalAPSInt(Op, getValue(), R.getValue());
    228 
    229   if (X)
    230     return nonloc::ConcreteInt(*X);
    231   else
    232     return UndefinedVal();
    233 }
    234 
    235 //===----------------------------------------------------------------------===//
    236 // Pretty-Printing.
    237 //===----------------------------------------------------------------------===//
    238 
    239 void SVal::dump() const { dumpToStream(llvm::errs()); }
    240 
    241 void SVal::dumpToStream(raw_ostream &os) const {
    242   switch (getBaseKind()) {
    243     case UnknownKind:
    244       os << "Unknown";
    245       break;
    246     case NonLocKind:
    247       castAs<NonLoc>().dumpToStream(os);
    248       break;
    249     case LocKind:
    250       castAs<Loc>().dumpToStream(os);
    251       break;
    252     case UndefinedKind:
    253       os << "Undefined";
    254       break;
    255   }
    256 }
    257 
    258 void NonLoc::dumpToStream(raw_ostream &os) const {
    259   switch (getSubKind()) {
    260     case nonloc::ConcreteIntKind: {
    261       const nonloc::ConcreteInt& C = castAs<nonloc::ConcreteInt>();
    262       if (C.getValue().isUnsigned())
    263         os << C.getValue().getZExtValue();
    264       else
    265         os << C.getValue().getSExtValue();
    266       os << ' ' << (C.getValue().isUnsigned() ? 'U' : 'S')
    267          << C.getValue().getBitWidth() << 'b';
    268       break;
    269     }
    270     case nonloc::SymbolValKind: {
    271       os << castAs<nonloc::SymbolVal>().getSymbol();
    272       break;
    273     }
    274     case nonloc::LocAsIntegerKind: {
    275       const nonloc::LocAsInteger& C = castAs<nonloc::LocAsInteger>();
    276       os << C.getLoc() << " [as " << C.getNumBits() << " bit integer]";
    277       break;
    278     }
    279     case nonloc::CompoundValKind: {
    280       const nonloc::CompoundVal& C = castAs<nonloc::CompoundVal>();
    281       os << "compoundVal{";
    282       bool first = true;
    283       for (nonloc::CompoundVal::iterator I=C.begin(), E=C.end(); I!=E; ++I) {
    284         if (first) {
    285           os << ' '; first = false;
    286         }
    287         else
    288           os << ", ";
    289 
    290         (*I).dumpToStream(os);
    291       }
    292       os << "}";
    293       break;
    294     }
    295     case nonloc::LazyCompoundValKind: {
    296       const nonloc::LazyCompoundVal &C = castAs<nonloc::LazyCompoundVal>();
    297       os << "lazyCompoundVal{" << const_cast<void *>(C.getStore())
    298          << ',' << C.getRegion()
    299          << '}';
    300       break;
    301     }
    302     default:
    303       assert (false && "Pretty-printed not implemented for this NonLoc.");
    304       break;
    305   }
    306 }
    307 
    308 void Loc::dumpToStream(raw_ostream &os) const {
    309   switch (getSubKind()) {
    310     case loc::ConcreteIntKind:
    311       os << castAs<loc::ConcreteInt>().getValue().getZExtValue() << " (Loc)";
    312       break;
    313     case loc::GotoLabelKind:
    314       os << "&&" << castAs<loc::GotoLabel>().getLabel()->getName();
    315       break;
    316     case loc::MemRegionKind:
    317       os << '&' << castAs<loc::MemRegionVal>().getRegion()->getString();
    318       break;
    319     default:
    320       llvm_unreachable("Pretty-printing not implemented for this Loc.");
    321   }
    322 }
    323