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 0;
     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 SymbolRef SVal::getAsLocSymbol() const {
     68   // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
     69   if (Optional<nonloc::LocAsInteger> X = getAs<nonloc::LocAsInteger>())
     70     return X->getLoc().getAsLocSymbol();
     71 
     72   if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>()) {
     73     const MemRegion *R = X->stripCasts();
     74     if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R))
     75       return SymR->getSymbol();
     76   }
     77   return 0;
     78 }
     79 
     80 /// Get the symbol in the SVal or its base region.
     81 SymbolRef SVal::getLocSymbolInBase() const {
     82   Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>();
     83 
     84   if (!X)
     85     return 0;
     86 
     87   const MemRegion *R = X->getRegion();
     88 
     89   while (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
     90     if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(SR))
     91       return SymR->getSymbol();
     92     else
     93       R = SR->getSuperRegion();
     94   }
     95 
     96   return 0;
     97 }
     98 
     99 // TODO: The next 3 functions have to be simplified.
    100 
    101 /// \brief If this SVal wraps a symbol return that SymbolRef.
    102 ///  Otherwise return 0.
    103 SymbolRef SVal::getAsSymbol() const {
    104   // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
    105   if (Optional<nonloc::SymbolVal> X = getAs<nonloc::SymbolVal>())
    106     return X->getSymbol();
    107 
    108   return getAsLocSymbol();
    109 }
    110 
    111 /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
    112 ///  return that expression.  Otherwise return NULL.
    113 const SymExpr *SVal::getAsSymbolicExpression() const {
    114   if (Optional<nonloc::SymbolVal> X = getAs<nonloc::SymbolVal>())
    115     return X->getSymbol();
    116 
    117   return getAsSymbol();
    118 }
    119 
    120 const SymExpr* SVal::getAsSymExpr() const {
    121   const SymExpr* Sym = getAsSymbol();
    122   if (!Sym)
    123     Sym = getAsSymbolicExpression();
    124   return Sym;
    125 }
    126 
    127 const MemRegion *SVal::getAsRegion() const {
    128   if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>())
    129     return X->getRegion();
    130 
    131   if (Optional<nonloc::LocAsInteger> X = getAs<nonloc::LocAsInteger>())
    132     return X->getLoc().getAsRegion();
    133 
    134   return 0;
    135 }
    136 
    137 const MemRegion *loc::MemRegionVal::stripCasts(bool StripBaseCasts) const {
    138   const MemRegion *R = getRegion();
    139   return R ?  R->StripCasts(StripBaseCasts) : NULL;
    140 }
    141 
    142 const void *nonloc::LazyCompoundVal::getStore() const {
    143   return static_cast<const LazyCompoundValData*>(Data)->getStore();
    144 }
    145 
    146 const TypedValueRegion *nonloc::LazyCompoundVal::getRegion() const {
    147   return static_cast<const LazyCompoundValData*>(Data)->getRegion();
    148 }
    149 
    150 //===----------------------------------------------------------------------===//
    151 // Other Iterators.
    152 //===----------------------------------------------------------------------===//
    153 
    154 nonloc::CompoundVal::iterator nonloc::CompoundVal::begin() const {
    155   return getValue()->begin();
    156 }
    157 
    158 nonloc::CompoundVal::iterator nonloc::CompoundVal::end() const {
    159   return getValue()->end();
    160 }
    161 
    162 //===----------------------------------------------------------------------===//
    163 // Useful predicates.
    164 //===----------------------------------------------------------------------===//
    165 
    166 bool SVal::isConstant() const {
    167   return getAs<nonloc::ConcreteInt>() || getAs<loc::ConcreteInt>();
    168 }
    169 
    170 bool SVal::isConstant(int I) const {
    171   if (Optional<loc::ConcreteInt> LV = getAs<loc::ConcreteInt>())
    172     return LV->getValue() == I;
    173   if (Optional<nonloc::ConcreteInt> NV = getAs<nonloc::ConcreteInt>())
    174     return NV->getValue() == I;
    175   return false;
    176 }
    177 
    178 bool SVal::isZeroConstant() const {
    179   return isConstant(0);
    180 }
    181 
    182 
    183 //===----------------------------------------------------------------------===//
    184 // Transfer function dispatch for Non-Locs.
    185 //===----------------------------------------------------------------------===//
    186 
    187 SVal nonloc::ConcreteInt::evalBinOp(SValBuilder &svalBuilder,
    188                                     BinaryOperator::Opcode Op,
    189                                     const nonloc::ConcreteInt& R) const {
    190   const llvm::APSInt* X =
    191     svalBuilder.getBasicValueFactory().evalAPSInt(Op, getValue(), R.getValue());
    192 
    193   if (X)
    194     return nonloc::ConcreteInt(*X);
    195   else
    196     return UndefinedVal();
    197 }
    198 
    199 nonloc::ConcreteInt
    200 nonloc::ConcreteInt::evalComplement(SValBuilder &svalBuilder) const {
    201   return svalBuilder.makeIntVal(~getValue());
    202 }
    203 
    204 nonloc::ConcreteInt
    205 nonloc::ConcreteInt::evalMinus(SValBuilder &svalBuilder) const {
    206   return svalBuilder.makeIntVal(-getValue());
    207 }
    208 
    209 //===----------------------------------------------------------------------===//
    210 // Transfer function dispatch for Locs.
    211 //===----------------------------------------------------------------------===//
    212 
    213 SVal loc::ConcreteInt::evalBinOp(BasicValueFactory& BasicVals,
    214                                  BinaryOperator::Opcode Op,
    215                                  const loc::ConcreteInt& R) const {
    216 
    217   assert (Op == BO_Add || Op == BO_Sub ||
    218           (Op >= BO_LT && Op <= BO_NE));
    219 
    220   const llvm::APSInt* X = BasicVals.evalAPSInt(Op, getValue(), R.getValue());
    221 
    222   if (X)
    223     return loc::ConcreteInt(*X);
    224   else
    225     return UndefinedVal();
    226 }
    227 
    228 //===----------------------------------------------------------------------===//
    229 // Pretty-Printing.
    230 //===----------------------------------------------------------------------===//
    231 
    232 void SVal::dump() const { dumpToStream(llvm::errs()); }
    233 
    234 void SVal::dumpToStream(raw_ostream &os) const {
    235   switch (getBaseKind()) {
    236     case UnknownKind:
    237       os << "Unknown";
    238       break;
    239     case NonLocKind:
    240       castAs<NonLoc>().dumpToStream(os);
    241       break;
    242     case LocKind:
    243       castAs<Loc>().dumpToStream(os);
    244       break;
    245     case UndefinedKind:
    246       os << "Undefined";
    247       break;
    248   }
    249 }
    250 
    251 void NonLoc::dumpToStream(raw_ostream &os) const {
    252   switch (getSubKind()) {
    253     case nonloc::ConcreteIntKind: {
    254       const nonloc::ConcreteInt& C = castAs<nonloc::ConcreteInt>();
    255       if (C.getValue().isUnsigned())
    256         os << C.getValue().getZExtValue();
    257       else
    258         os << C.getValue().getSExtValue();
    259       os << ' ' << (C.getValue().isUnsigned() ? 'U' : 'S')
    260          << C.getValue().getBitWidth() << 'b';
    261       break;
    262     }
    263     case nonloc::SymbolValKind: {
    264       os << castAs<nonloc::SymbolVal>().getSymbol();
    265       break;
    266     }
    267     case nonloc::LocAsIntegerKind: {
    268       const nonloc::LocAsInteger& C = castAs<nonloc::LocAsInteger>();
    269       os << C.getLoc() << " [as " << C.getNumBits() << " bit integer]";
    270       break;
    271     }
    272     case nonloc::CompoundValKind: {
    273       const nonloc::CompoundVal& C = castAs<nonloc::CompoundVal>();
    274       os << "compoundVal{";
    275       bool first = true;
    276       for (nonloc::CompoundVal::iterator I=C.begin(), E=C.end(); I!=E; ++I) {
    277         if (first) {
    278           os << ' '; first = false;
    279         }
    280         else
    281           os << ", ";
    282 
    283         (*I).dumpToStream(os);
    284       }
    285       os << "}";
    286       break;
    287     }
    288     case nonloc::LazyCompoundValKind: {
    289       const nonloc::LazyCompoundVal &C = castAs<nonloc::LazyCompoundVal>();
    290       os << "lazyCompoundVal{" << const_cast<void *>(C.getStore())
    291          << ',' << C.getRegion()
    292          << '}';
    293       break;
    294     }
    295     default:
    296       assert (false && "Pretty-printed not implemented for this NonLoc.");
    297       break;
    298   }
    299 }
    300 
    301 void Loc::dumpToStream(raw_ostream &os) const {
    302   switch (getSubKind()) {
    303     case loc::ConcreteIntKind:
    304       os << castAs<loc::ConcreteInt>().getValue().getZExtValue() << " (Loc)";
    305       break;
    306     case loc::GotoLabelKind:
    307       os << "&&" << castAs<loc::GotoLabel>().getLabel()->getName();
    308       break;
    309     case loc::MemRegionKind:
    310       os << '&' << castAs<loc::MemRegionVal>().getRegion()->getString();
    311       break;
    312     default:
    313       llvm_unreachable("Pretty-printing not implemented for this Loc.");
    314   }
    315 }
    316