contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/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/Core/PathSensitive/ProgramState.h"
  16 #include "clang/AST/ExprObjC.h"
  17 #include "clang/Basic/IdentifierTable.h"
  18 #include "llvm/Support/raw_ostream.h"
  19 #include "clang/AST/DeclCXX.h"
  20 using namespace clang;
  21 using namespace ento;
  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 (Optional<nonloc::SymbolVal> SV = getAs<nonloc::SymbolVal>()) {
  35     SymbolRef sym = SV->getSymbol();
  36     if (isa<SymbolConjured>(sym))
  37       return true;
  38   }
  39
  40   if (Optional<loc::MemRegionVal> RV = getAs<loc::MemRegionVal>()) {
  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 (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>()) {
  54     const MemRegion* R = X->getRegion();
  55     if (const FunctionCodeRegion *CTR = R->getAs<FunctionCodeRegion>())
  56       if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CTR->getDecl()))
  57         return FD;
  58   }
  59
  60   if (auto X = getAs<nonloc::PointerToMember>()) {
  61     if (const CXXMethodDecl *MD = dyn_cast_or_null<CXXMethodDecl>(X->getDecl()))
  62       return MD;
  63   }
  64   return nullptr;
  65 }
  66
  67 /// \brief If this SVal is a location (subclasses Loc) and wraps a symbol,
  68 /// return that SymbolRef.  Otherwise return 0.
  69 ///
  70 /// Implicit casts (ex: void* -> char*) can turn Symbolic region into Element
  71 /// region. If that is the case, gets the underlining region.
  72 /// When IncludeBaseRegions is set to true and the SubRegion is non-symbolic,
  73 /// the first symbolic parent region is returned.
  74 SymbolRef SVal::getAsLocSymbol(bool IncludeBaseRegions) const {
  75   // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
  76   if (Optional<nonloc::LocAsInteger> X = getAs<nonloc::LocAsInteger>())
  77     return X->getLoc().getAsLocSymbol();
  78
  79   if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>()) {
  80     const MemRegion *R = X->getRegion();
  81     if (const SymbolicRegion *SymR = IncludeBaseRegions ?
  82                                       R->getSymbolicBase() :
  83                                       dyn_cast<SymbolicRegion>(R->StripCasts()))
  84       return SymR->getSymbol();
  85   }
  86   return nullptr;
  87 }
  88
  89 /// Get the symbol in the SVal or its base region.
  90 SymbolRef SVal::getLocSymbolInBase() const {
  91   Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>();
  92
  93   if (!X)
  94     return nullptr;
  95
  96   const MemRegion *R = X->getRegion();
  97
  98   while (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
  99     if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(SR))
 100       return SymR->getSymbol();
 101     else
 102       R = SR->getSuperRegion();
 103   }
 104
 105   return nullptr;
 106 }
 107
 108 // TODO: The next 3 functions have to be simplified.
 109
 110 /// \brief If this SVal wraps a symbol return that SymbolRef.
 111 /// Otherwise, return 0.
 112 ///
 113 /// Casts are ignored during lookup.
 114 /// \param IncludeBaseRegions The boolean that controls whether the search
 115 /// should continue to the base regions if the region is not symbolic.
 116 SymbolRef SVal::getAsSymbol(bool IncludeBaseRegion) const {
 117   // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
 118   if (Optional<nonloc::SymbolVal> X = getAs<nonloc::SymbolVal>())
 119     return X->getSymbol();
 120
 121   return getAsLocSymbol(IncludeBaseRegion);
 122 }
 123
 124 /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
 125 ///  return that expression.  Otherwise return NULL.
 126 const SymExpr *SVal::getAsSymbolicExpression() const {
 127   if (Optional<nonloc::SymbolVal> X = getAs<nonloc::SymbolVal>())
 128     return X->getSymbol();
 129
 130   return getAsSymbol();
 131 }
 132
 133 const SymExpr* SVal::getAsSymExpr() const {
 134   const SymExpr* Sym = getAsSymbol();
 135   if (!Sym)
 136     Sym = getAsSymbolicExpression();
 137   return Sym;
 138 }
 139
 140 const MemRegion *SVal::getAsRegion() const {
 141   if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>())
 142     return X->getRegion();
 143
 144   if (Optional<nonloc::LocAsInteger> X = getAs<nonloc::LocAsInteger>())
 145     return X->getLoc().getAsRegion();
 146
 147   return nullptr;
 148 }
 149
 150 const MemRegion *loc::MemRegionVal::stripCasts(bool StripBaseCasts) const {
 151   const MemRegion *R = getRegion();
 152   return R ?  R->StripCasts(StripBaseCasts) : nullptr;
 153 }
 154
 155 const void *nonloc::LazyCompoundVal::getStore() const {
 156   return static_cast<const LazyCompoundValData*>(Data)->getStore();
 157 }
 158
 159 const TypedValueRegion *nonloc::LazyCompoundVal::getRegion() const {
 160   return static_cast<const LazyCompoundValData*>(Data)->getRegion();
 161 }
 162
 163 const DeclaratorDecl *nonloc::PointerToMember::getDecl() const {
 164   const auto PTMD = this->getPTMData();
 165   if (PTMD.isNull())
 166     return nullptr;
 167
 168   const DeclaratorDecl *DD = nullptr;
 169   if (PTMD.is<const DeclaratorDecl *>())
 170     DD = PTMD.get<const DeclaratorDecl *>();
 171   else
 172     DD = PTMD.get<const PointerToMemberData *>()->getDeclaratorDecl();
 173
 174   return DD;
 175 }
 176
 177 //===----------------------------------------------------------------------===//
 178 // Other Iterators.
 179 //===----------------------------------------------------------------------===//
 180
 181 nonloc::CompoundVal::iterator nonloc::CompoundVal::begin() const {
 182   return getValue()->begin();
 183 }
 184
 185 nonloc::CompoundVal::iterator nonloc::CompoundVal::end() const {
 186   return getValue()->end();
 187 }
 188
 189 nonloc::PointerToMember::iterator nonloc::PointerToMember::begin() const {
 190   const PTMDataType PTMD = getPTMData();
 191   if (PTMD.is<const DeclaratorDecl *>())
 192     return nonloc::PointerToMember::iterator();
 193   return PTMD.get<const PointerToMemberData *>()->begin();
 194 }
 195
 196 nonloc::PointerToMember::iterator nonloc::PointerToMember::end() const {
 197   const PTMDataType PTMD = getPTMData();
 198   if (PTMD.is<const DeclaratorDecl *>())
 199     return nonloc::PointerToMember::iterator();
 200   return PTMD.get<const PointerToMemberData *>()->end();
 201 }
 202
 203 //===----------------------------------------------------------------------===//
 204 // Useful predicates.
 205 //===----------------------------------------------------------------------===//
 206
 207 bool SVal::isConstant() const {
 208   return getAs<nonloc::ConcreteInt>() || getAs<loc::ConcreteInt>();
 209 }
 210
 211 bool SVal::isConstant(int I) const {
 212   if (Optional<loc::ConcreteInt> LV = getAs<loc::ConcreteInt>())
 213     return LV->getValue() == I;
 214   if (Optional<nonloc::ConcreteInt> NV = getAs<nonloc::ConcreteInt>())
 215     return NV->getValue() == I;
 216   return false;
 217 }
 218
 219 bool SVal::isZeroConstant() const {
 220   return isConstant(0);
 221 }
 222
 223
 224 //===----------------------------------------------------------------------===//
 225 // Transfer function dispatch for Non-Locs.
 226 //===----------------------------------------------------------------------===//
 227
 228 SVal nonloc::ConcreteInt::evalBinOp(SValBuilder &svalBuilder,
 229                                     BinaryOperator::Opcode Op,
 230                                     const nonloc::ConcreteInt& R) const {
 231   const llvm::APSInt* X =
 232     svalBuilder.getBasicValueFactory().evalAPSInt(Op, getValue(), R.getValue());
 233
 234   if (X)
 235     return nonloc::ConcreteInt(*X);
 236   else
 237     return UndefinedVal();
 238 }
 239
 240 nonloc::ConcreteInt
 241 nonloc::ConcreteInt::evalComplement(SValBuilder &svalBuilder) const {
 242   return svalBuilder.makeIntVal(~getValue());
 243 }
 244
 245 nonloc::ConcreteInt
 246 nonloc::ConcreteInt::evalMinus(SValBuilder &svalBuilder) const {
 247   return svalBuilder.makeIntVal(-getValue());
 248 }
 249
 250 //===----------------------------------------------------------------------===//
 251 // Transfer function dispatch for Locs.
 252 //===----------------------------------------------------------------------===//
 253
 254 SVal loc::ConcreteInt::evalBinOp(BasicValueFactory& BasicVals,
 255                                  BinaryOperator::Opcode Op,
 256                                  const loc::ConcreteInt& R) const {
 257
 258   assert(BinaryOperator::isComparisonOp(Op) || Op == BO_Sub);
 259
 260   const llvm::APSInt *X = BasicVals.evalAPSInt(Op, getValue(), R.getValue());
 261
 262   if (X)
 263     return nonloc::ConcreteInt(*X);
 264   else
 265     return UndefinedVal();
 266 }
 267
 268 //===----------------------------------------------------------------------===//
 269 // Pretty-Printing.
 270 //===----------------------------------------------------------------------===//
 271
 272 LLVM_DUMP_METHOD void SVal::dump() const { dumpToStream(llvm::errs()); }
 273
 274 void SVal::dumpToStream(raw_ostream &os) const {
 275   switch (getBaseKind()) {
 276     case UnknownValKind:
 277       os << "Unknown";
 278       break;
 279     case NonLocKind:
 280       castAs<NonLoc>().dumpToStream(os);
 281       break;
 282     case LocKind:
 283       castAs<Loc>().dumpToStream(os);
 284       break;
 285     case UndefinedValKind:
 286       os << "Undefined";
 287       break;
 288   }
 289 }
 290
 291 void NonLoc::dumpToStream(raw_ostream &os) const {
 292   switch (getSubKind()) {
 293     case nonloc::ConcreteIntKind: {
 294       const nonloc::ConcreteInt& C = castAs<nonloc::ConcreteInt>();
 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 << castAs<nonloc::SymbolVal>().getSymbol();
 305       break;
 306     }
 307     case nonloc::LocAsIntegerKind: {
 308       const nonloc::LocAsInteger& C = castAs<nonloc::LocAsInteger>();
 309       os << C.getLoc() << " [as " << C.getNumBits() << " bit integer]";
 310       break;
 311     }
 312     case nonloc::CompoundValKind: {
 313       const nonloc::CompoundVal& C = castAs<nonloc::CompoundVal>();
 314       os << "compoundVal{";
 315       bool first = true;
 316       for (nonloc::CompoundVal::iterator I=C.begin(), E=C.end(); I!=E; ++I) {
 317         if (first) {
 318           os << ' '; first = false;
 319         }
 320         else
 321           os << ", ";
 322
 323         (*I).dumpToStream(os);
 324       }
 325       os << "}";
 326       break;
 327     }
 328     case nonloc::LazyCompoundValKind: {
 329       const nonloc::LazyCompoundVal &C = castAs<nonloc::LazyCompoundVal>();
 330       os << "lazyCompoundVal{" << const_cast<void *>(C.getStore())
 331          << ',' << C.getRegion()
 332          << '}';
 333       break;
 334     }
 335     case nonloc::PointerToMemberKind: {
 336       os << "pointerToMember{";
 337       const nonloc::PointerToMember &CastRes =
 338           castAs<nonloc::PointerToMember>();
 339       if (CastRes.getDecl())
 340         os << "|" << CastRes.getDecl()->getQualifiedNameAsString() << "|";
 341       bool first = true;
 342       for (const auto &I : CastRes) {
 343         if (first) {
 344           os << ' '; first = false;
 345         }
 346         else
 347           os << ", ";
 348
 349         os << (*I).getType().getAsString();
 350       }
 351
 352       os << '}';
 353       break;
 354     }
 355     default:
 356       assert (false && "Pretty-printed not implemented for this NonLoc.");
 357       break;
 358   }
 359 }
 360
 361 void Loc::dumpToStream(raw_ostream &os) const {
 362   switch (getSubKind()) {
 363     case loc::ConcreteIntKind:
 364       os << castAs<loc::ConcreteInt>().getValue().getZExtValue() << " (Loc)";
 365       break;
 366     case loc::GotoLabelKind:
 367       os << "&&" << castAs<loc::GotoLabel>().getLabel()->getName();
 368       break;
 369     case loc::MemRegionValKind:
 370       os << '&' << castAs<loc::MemRegionVal>().getRegion()->getString();
 371       break;
 372     default:
 373       llvm_unreachable("Pretty-printing not implemented for this Loc.");
 374   }
 375 }