contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/SVals.cpp

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