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