lib/StaticAnalyzer/SVals.cpp

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