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 using namespace clang;
     19 using namespace ento;
     20 using llvm::APSInt;
     21 
     22 //===----------------------------------------------------------------------===//
     23 // Symbol iteration within an SVal.
     24 //===----------------------------------------------------------------------===//
     25 
     26 
     27 //===----------------------------------------------------------------------===//
     28 // Utility methods.
     29 //===----------------------------------------------------------------------===//
     30 
     31 bool SVal::hasConjuredSymbol() const {
     32   if (const nonloc::SymbolVal* SV = dyn_cast<nonloc::SymbolVal>(this)) {
     33     SymbolRef sym = SV->getSymbol();
     34     if (isa<SymbolConjured>(sym))
     35       return true;
     36   }
     37 
     38   if (const loc::MemRegionVal *RV = dyn_cast<loc::MemRegionVal>(this)) {
     39     const MemRegion *R = RV->getRegion();
     40     if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
     41       SymbolRef sym = SR->getSymbol();
     42       if (isa<SymbolConjured>(sym))
     43         return true;
     44     }
     45   }
     46 
     47   return false;
     48 }
     49 
     50 const FunctionDecl *SVal::getAsFunctionDecl() const {
     51   if (const loc::MemRegionVal* X = dyn_cast<loc::MemRegionVal>(this)) {
     52     const MemRegion* R = X->getRegion();
     53     if (const FunctionTextRegion *CTR = R->getAs<FunctionTextRegion>())
     54       return CTR->getDecl();
     55   }
     56 
     57   return NULL;
     58 }
     59 
     60 /// getAsLocSymbol - If this SVal is a location (subclasses Loc) and
     61 ///  wraps a symbol, return that SymbolRef.  Otherwise return 0.
     62 // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
     63 SymbolRef SVal::getAsLocSymbol() const {
     64   if (const nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(this))
     65     return X->getLoc().getAsLocSymbol();
     66 
     67   if (const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this)) {
     68     const MemRegion *R = X->stripCasts();
     69     if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R))
     70       return SymR->getSymbol();
     71   }
     72   return NULL;
     73 }
     74 
     75 /// Get the symbol in the SVal or its base region.
     76 SymbolRef SVal::getLocSymbolInBase() const {
     77   const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this);
     78 
     79   if (!X)
     80     return 0;
     81 
     82   const MemRegion *R = X->getRegion();
     83 
     84   while (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
     85     if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(SR))
     86       return SymR->getSymbol();
     87     else
     88       R = SR->getSuperRegion();
     89   }
     90 
     91   return 0;
     92 }
     93 
     94 /// getAsSymbol - If this Sval wraps a symbol return that SymbolRef.
     95 ///  Otherwise return 0.
     96 // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
     97 SymbolRef SVal::getAsSymbol() const {
     98   if (const nonloc::SymbolVal *X = dyn_cast<nonloc::SymbolVal>(this))
     99     return X->getSymbol();
    100 
    101   if (const nonloc::SymExprVal *X = dyn_cast<nonloc::SymExprVal>(this))
    102     if (SymbolRef Y = dyn_cast<SymbolData>(X->getSymbolicExpression()))
    103       return Y;
    104 
    105   return getAsLocSymbol();
    106 }
    107 
    108 /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
    109 ///  return that expression.  Otherwise return NULL.
    110 const SymExpr *SVal::getAsSymbolicExpression() const {
    111   if (const nonloc::SymExprVal *X = dyn_cast<nonloc::SymExprVal>(this))
    112     return X->getSymbolicExpression();
    113 
    114   return getAsSymbol();
    115 }
    116 
    117 const MemRegion *SVal::getAsRegion() const {
    118   if (const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this))
    119     return X->getRegion();
    120 
    121   if (const nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(this)) {
    122     return X->getLoc().getAsRegion();
    123   }
    124 
    125   return 0;
    126 }
    127 
    128 const MemRegion *loc::MemRegionVal::stripCasts() const {
    129   const MemRegion *R = getRegion();
    130   return R ?  R->StripCasts() : NULL;
    131 }
    132 
    133 bool SVal::symbol_iterator::operator==(const symbol_iterator &X) const {
    134   return itr == X.itr;
    135 }
    136 
    137 bool SVal::symbol_iterator::operator!=(const symbol_iterator &X) const {
    138   return itr != X.itr;
    139 }
    140 
    141 SVal::symbol_iterator::symbol_iterator(const SymExpr *SE) {
    142   itr.push_back(SE);
    143   while (!isa<SymbolData>(itr.back())) expand();
    144 }
    145 
    146 SVal::symbol_iterator &SVal::symbol_iterator::operator++() {
    147   assert(!itr.empty() && "attempting to iterate on an 'end' iterator");
    148   assert(isa<SymbolData>(itr.back()));
    149   itr.pop_back();
    150   if (!itr.empty())
    151     while (!isa<SymbolData>(itr.back())) expand();
    152   return *this;
    153 }
    154 
    155 SymbolRef SVal::symbol_iterator::operator*() {
    156   assert(!itr.empty() && "attempting to dereference an 'end' iterator");
    157   return cast<SymbolData>(itr.back());
    158 }
    159 
    160 void SVal::symbol_iterator::expand() {
    161   const SymExpr *SE = itr.back();
    162   itr.pop_back();
    163 
    164   if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
    165     itr.push_back(SIE->getLHS());
    166     return;
    167   }
    168   else if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
    169     itr.push_back(SSE->getLHS());
    170     itr.push_back(SSE->getRHS());
    171     return;
    172   }
    173 
    174   llvm_unreachable("unhandled expansion case");
    175 }
    176 
    177 const void *nonloc::LazyCompoundVal::getStore() const {
    178   return static_cast<const LazyCompoundValData*>(Data)->getStore();
    179 }
    180 
    181 const TypedRegion *nonloc::LazyCompoundVal::getRegion() const {
    182   return static_cast<const LazyCompoundValData*>(Data)->getRegion();
    183 }
    184 
    185 //===----------------------------------------------------------------------===//
    186 // Other Iterators.
    187 //===----------------------------------------------------------------------===//
    188 
    189 nonloc::CompoundVal::iterator nonloc::CompoundVal::begin() const {
    190   return getValue()->begin();
    191 }
    192 
    193 nonloc::CompoundVal::iterator nonloc::CompoundVal::end() const {
    194   return getValue()->end();
    195 }
    196 
    197 //===----------------------------------------------------------------------===//
    198 // Useful predicates.
    199 //===----------------------------------------------------------------------===//
    200 
    201 bool SVal::isConstant() const {
    202   return isa<nonloc::ConcreteInt>(this) || isa<loc::ConcreteInt>(this);
    203 }
    204 
    205 bool SVal::isConstant(int I) const {
    206   if (isa<loc::ConcreteInt>(*this))
    207     return cast<loc::ConcreteInt>(*this).getValue() == I;
    208   else if (isa<nonloc::ConcreteInt>(*this))
    209     return cast<nonloc::ConcreteInt>(*this).getValue() == I;
    210   else
    211     return false;
    212 }
    213 
    214 bool SVal::isZeroConstant() const {
    215   return isConstant(0);
    216 }
    217 
    218 
    219 //===----------------------------------------------------------------------===//
    220 // Transfer function dispatch for Non-Locs.
    221 //===----------------------------------------------------------------------===//
    222 
    223 SVal nonloc::ConcreteInt::evalBinOp(SValBuilder &svalBuilder,
    224                                     BinaryOperator::Opcode Op,
    225                                     const nonloc::ConcreteInt& R) const {
    226   const llvm::APSInt* X =
    227     svalBuilder.getBasicValueFactory().evalAPSInt(Op, getValue(), R.getValue());
    228 
    229   if (X)
    230     return nonloc::ConcreteInt(*X);
    231   else
    232     return UndefinedVal();
    233 }
    234 
    235 nonloc::ConcreteInt
    236 nonloc::ConcreteInt::evalComplement(SValBuilder &svalBuilder) const {
    237   return svalBuilder.makeIntVal(~getValue());
    238 }
    239 
    240 nonloc::ConcreteInt
    241 nonloc::ConcreteInt::evalMinus(SValBuilder &svalBuilder) const {
    242   return svalBuilder.makeIntVal(-getValue());
    243 }
    244 
    245 //===----------------------------------------------------------------------===//
    246 // Transfer function dispatch for Locs.
    247 //===----------------------------------------------------------------------===//
    248 
    249 SVal loc::ConcreteInt::evalBinOp(BasicValueFactory& BasicVals,
    250                                  BinaryOperator::Opcode Op,
    251                                  const loc::ConcreteInt& R) const {
    252 
    253   assert (Op == BO_Add || Op == BO_Sub ||
    254           (Op >= BO_LT && Op <= BO_NE));
    255 
    256   const llvm::APSInt* X = BasicVals.evalAPSInt(Op, getValue(), R.getValue());
    257 
    258   if (X)
    259     return loc::ConcreteInt(*X);
    260   else
    261     return UndefinedVal();
    262 }
    263 
    264 //===----------------------------------------------------------------------===//
    265 // Pretty-Printing.
    266 //===----------------------------------------------------------------------===//
    267 
    268 void SVal::dump() const { dumpToStream(llvm::errs()); }
    269 
    270 void SVal::dumpToStream(raw_ostream &os) const {
    271   switch (getBaseKind()) {
    272     case UnknownKind:
    273       os << "Unknown";
    274       break;
    275     case NonLocKind:
    276       cast<NonLoc>(this)->dumpToStream(os);
    277       break;
    278     case LocKind:
    279       cast<Loc>(this)->dumpToStream(os);
    280       break;
    281     case UndefinedKind:
    282       os << "Undefined";
    283       break;
    284     default:
    285       assert (false && "Invalid SVal.");
    286   }
    287 }
    288 
    289 void NonLoc::dumpToStream(raw_ostream &os) const {
    290   switch (getSubKind()) {
    291     case nonloc::ConcreteIntKind: {
    292       const nonloc::ConcreteInt& C = *cast<nonloc::ConcreteInt>(this);
    293       if (C.getValue().isUnsigned())
    294         os << C.getValue().getZExtValue();
    295       else
    296         os << C.getValue().getSExtValue();
    297       os << ' ' << (C.getValue().isUnsigned() ? 'U' : 'S')
    298          << C.getValue().getBitWidth() << 'b';
    299       break;
    300     }
    301     case nonloc::SymbolValKind:
    302       os << '$' << cast<nonloc::SymbolVal>(this)->getSymbol();
    303       break;
    304     case nonloc::SymExprValKind: {
    305       const nonloc::SymExprVal& C = *cast<nonloc::SymExprVal>(this);
    306       const SymExpr *SE = C.getSymbolicExpression();
    307       os << SE;
    308       break;
    309     }
    310     case nonloc::LocAsIntegerKind: {
    311       const nonloc::LocAsInteger& C = *cast<nonloc::LocAsInteger>(this);
    312       os << C.getLoc() << " [as " << C.getNumBits() << " bit integer]";
    313       break;
    314     }
    315     case nonloc::CompoundValKind: {
    316       const nonloc::CompoundVal& C = *cast<nonloc::CompoundVal>(this);
    317       os << "compoundVal{";
    318       bool first = true;
    319       for (nonloc::CompoundVal::iterator I=C.begin(), E=C.end(); I!=E; ++I) {
    320         if (first) {
    321           os << ' '; first = false;
    322         }
    323         else
    324           os << ", ";
    325 
    326         (*I).dumpToStream(os);
    327       }
    328       os << "}";
    329       break;
    330     }
    331     case nonloc::LazyCompoundValKind: {
    332       const nonloc::LazyCompoundVal &C = *cast<nonloc::LazyCompoundVal>(this);
    333       os << "lazyCompoundVal{" << const_cast<void *>(C.getStore())
    334          << ',' << C.getRegion()
    335          << '}';
    336       break;
    337     }
    338     default:
    339       assert (false && "Pretty-printed not implemented for this NonLoc.");
    340       break;
    341   }
    342 }
    343 
    344 void Loc::dumpToStream(raw_ostream &os) const {
    345   switch (getSubKind()) {
    346     case loc::ConcreteIntKind:
    347       os << cast<loc::ConcreteInt>(this)->getValue().getZExtValue() << " (Loc)";
    348       break;
    349     case loc::GotoLabelKind:
    350       os << "&&" << cast<loc::GotoLabel>(this)->getLabel()->getName();
    351       break;
    352     case loc::MemRegionKind:
    353       os << '&' << cast<loc::MemRegionVal>(this)->getRegion()->getString();
    354       break;
    355     case loc::ObjCPropRefKind: {
    356       const ObjCPropertyRefExpr *E = cast<loc::ObjCPropRef>(this)->getPropRefExpr();
    357       os << "objc-prop{";
    358       if (E->isSuperReceiver())
    359         os << "super.";
    360       else if (E->getBase())
    361         os << "<base>.";
    362 
    363       if (E->isImplicitProperty())
    364         os << E->getImplicitPropertyGetter()->getSelector().getAsString();
    365       else
    366         os << E->getExplicitProperty()->getName();
    367 
    368       os << "}";
    369       break;
    370     }
    371     default:
    372       llvm_unreachable("Pretty-printing not implemented for this Loc.");
    373   }
    374 }
    375