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