contrib/llvm-project/clang/lib/StaticAnalyzer/Core/SVals.cpp

   1 //===-- SVals.cpp - Abstract RValues for Path-Sens. Value Tracking --------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file defines SVal, Loc, and NonLoc, classes that represent
  10 //  abstract r-values for use with path-sensitive value tracking.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  15 #include "clang/AST/ASTContext.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/JsonSupport.h"
  21 #include "clang/Basic/LLVM.h"
  22 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
  23 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
  25 #include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
  26 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
  27 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
  28 #include "llvm/ADT/Optional.h"
  29 #include "llvm/Support/Casting.h"
  30 #include "llvm/Support/Compiler.h"
  31 #include "llvm/Support/ErrorHandling.h"
  32 #include "llvm/Support/raw_ostream.h"
  33 #include <cassert>
  34
  35 using namespace clang;
  36 using namespace ento;
  37
  38 //===----------------------------------------------------------------------===//
  39 // Symbol iteration within an SVal.
  40 //===----------------------------------------------------------------------===//
  41
  42 //===----------------------------------------------------------------------===//
  43 // Utility methods.
  44 //===----------------------------------------------------------------------===//
  45
  46 bool SVal::hasConjuredSymbol() const {
  47   if (Optional<nonloc::SymbolVal> SV = getAs<nonloc::SymbolVal>()) {
  48     SymbolRef sym = SV->getSymbol();
  49     if (isa<SymbolConjured>(sym))
  50       return true;
  51   }
  52
  53   if (Optional<loc::MemRegionVal> RV = getAs<loc::MemRegionVal>()) {
  54     const MemRegion *R = RV->getRegion();
  55     if (const auto *SR = dyn_cast<SymbolicRegion>(R)) {
  56       SymbolRef sym = SR->getSymbol();
  57       if (isa<SymbolConjured>(sym))
  58         return true;
  59     }
  60   }
  61
  62   return false;
  63 }
  64
  65 const FunctionDecl *SVal::getAsFunctionDecl() const {
  66   if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>()) {
  67     const MemRegion* R = X->getRegion();
  68     if (const FunctionCodeRegion *CTR = R->getAs<FunctionCodeRegion>())
  69       if (const auto *FD = dyn_cast<FunctionDecl>(CTR->getDecl()))
  70         return FD;
  71   }
  72
  73   if (auto X = getAs<nonloc::PointerToMember>()) {
  74     if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(X->getDecl()))
  75       return MD;
  76   }
  77   return nullptr;
  78 }
  79
  80 /// If this SVal is a location (subclasses Loc) and wraps a symbol,
  81 /// return that SymbolRef.  Otherwise return 0.
  82 ///
  83 /// Implicit casts (ex: void* -> char*) can turn Symbolic region into Element
  84 /// region. If that is the case, gets the underlining region.
  85 /// When IncludeBaseRegions is set to true and the SubRegion is non-symbolic,
  86 /// the first symbolic parent region is returned.
  87 SymbolRef SVal::getAsLocSymbol(bool IncludeBaseRegions) const {
  88   // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
  89   if (const MemRegion *R = getAsRegion())
  90     if (const SymbolicRegion *SymR =
  91             IncludeBaseRegions ? R->getSymbolicBase()
  92                                : dyn_cast<SymbolicRegion>(R->StripCasts()))
  93       return SymR->getSymbol();
  94
  95   return nullptr;
  96 }
  97
  98 /// Get the symbol in the SVal or its base region.
  99 SymbolRef SVal::getLocSymbolInBase() const {
 100   Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>();
 101
 102   if (!X)
 103     return nullptr;
 104
 105   const MemRegion *R = X->getRegion();
 106
 107   while (const auto *SR = dyn_cast<SubRegion>(R)) {
 108     if (const auto *SymR = dyn_cast<SymbolicRegion>(SR))
 109       return SymR->getSymbol();
 110     else
 111       R = SR->getSuperRegion();
 112   }
 113
 114   return nullptr;
 115 }
 116
 117 /// If this SVal wraps a symbol return that SymbolRef.
 118 /// Otherwise, return 0.
 119 ///
 120 /// Casts are ignored during lookup.
 121 /// \param IncludeBaseRegions The boolean that controls whether the search
 122 /// should continue to the base regions if the region is not symbolic.
 123 SymbolRef SVal::getAsSymbol(bool IncludeBaseRegions) const {
 124   // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
 125   if (Optional<nonloc::SymbolVal> X = getAs<nonloc::SymbolVal>())
 126     return X->getSymbol();
 127
 128   return getAsLocSymbol(IncludeBaseRegions);
 129 }
 130
 131 const MemRegion *SVal::getAsRegion() const {
 132   if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>())
 133     return X->getRegion();
 134
 135   if (Optional<nonloc::LocAsInteger> X = getAs<nonloc::LocAsInteger>())
 136     return X->getLoc().getAsRegion();
 137
 138   return nullptr;
 139 }
 140
 141 namespace {
 142 class TypeRetrievingVisitor
 143     : public FullSValVisitor<TypeRetrievingVisitor, QualType> {
 144 private:
 145   const ASTContext &Context;
 146
 147 public:
 148   TypeRetrievingVisitor(const ASTContext &Context) : Context(Context) {}
 149
 150   QualType VisitLocMemRegionVal(loc::MemRegionVal MRV) {
 151     return Visit(MRV.getRegion());
 152   }
 153   QualType VisitLocGotoLabel(loc::GotoLabel GL) {
 154     return QualType{Context.VoidPtrTy};
 155   }
 156   template <class ConcreteInt> QualType VisitConcreteInt(ConcreteInt CI) {
 157     const llvm::APSInt &Value = CI.getValue();
 158     return Context.getIntTypeForBitwidth(Value.getBitWidth(), Value.isSigned());
 159   }
 160   QualType VisitLocConcreteInt(loc::ConcreteInt CI) {
 161     return VisitConcreteInt(CI);
 162   }
 163   QualType VisitNonLocConcreteInt(nonloc::ConcreteInt CI) {
 164     return VisitConcreteInt(CI);
 165   }
 166   QualType VisitNonLocLocAsInteger(nonloc::LocAsInteger LI) {
 167     QualType NestedType = Visit(LI.getLoc());
 168     if (NestedType.isNull())
 169       return NestedType;
 170
 171     return Context.getIntTypeForBitwidth(LI.getNumBits(),
 172                                          NestedType->isSignedIntegerType());
 173   }
 174   QualType VisitNonLocCompoundVal(nonloc::CompoundVal CV) {
 175     return CV.getValue()->getType();
 176   }
 177   QualType VisitNonLocLazyCompoundVal(nonloc::LazyCompoundVal LCV) {
 178     return LCV.getRegion()->getValueType();
 179   }
 180   QualType VisitNonLocSymbolVal(nonloc::SymbolVal SV) {
 181     return Visit(SV.getSymbol());
 182   }
 183   QualType VisitSymbolicRegion(const SymbolicRegion *SR) {
 184     return Visit(SR->getSymbol());
 185   }
 186   QualType VisitTypedRegion(const TypedRegion *TR) {
 187     return TR->getLocationType();
 188   }
 189   QualType VisitSymExpr(const SymExpr *SE) { return SE->getType(); }
 190 };
 191 } // end anonymous namespace
 192
 193 QualType SVal::getType(const ASTContext &Context) const {
 194   TypeRetrievingVisitor TRV{Context};
 195   return TRV.Visit(*this);
 196 }
 197
 198 const MemRegion *loc::MemRegionVal::stripCasts(bool StripBaseCasts) const {
 199   const MemRegion *R = getRegion();
 200   return R ?  R->StripCasts(StripBaseCasts) : nullptr;
 201 }
 202
 203 const void *nonloc::LazyCompoundVal::getStore() const {
 204   return static_cast<const LazyCompoundValData*>(Data)->getStore();
 205 }
 206
 207 const TypedValueRegion *nonloc::LazyCompoundVal::getRegion() const {
 208   return static_cast<const LazyCompoundValData*>(Data)->getRegion();
 209 }
 210
 211 bool nonloc::PointerToMember::isNullMemberPointer() const {
 212   return getPTMData().isNull();
 213 }
 214
 215 const NamedDecl *nonloc::PointerToMember::getDecl() const {
 216   const auto PTMD = this->getPTMData();
 217   if (PTMD.isNull())
 218     return nullptr;
 219
 220   const NamedDecl *ND = nullptr;
 221   if (PTMD.is<const NamedDecl *>())
 222     ND = PTMD.get<const NamedDecl *>();
 223   else
 224     ND = PTMD.get<const PointerToMemberData *>()->getDeclaratorDecl();
 225
 226   return ND;
 227 }
 228
 229 //===----------------------------------------------------------------------===//
 230 // Other Iterators.
 231 //===----------------------------------------------------------------------===//
 232
 233 nonloc::CompoundVal::iterator nonloc::CompoundVal::begin() const {
 234   return getValue()->begin();
 235 }
 236
 237 nonloc::CompoundVal::iterator nonloc::CompoundVal::end() const {
 238   return getValue()->end();
 239 }
 240
 241 nonloc::PointerToMember::iterator nonloc::PointerToMember::begin() const {
 242   const PTMDataType PTMD = getPTMData();
 243   if (PTMD.is<const NamedDecl *>())
 244     return {};
 245   return PTMD.get<const PointerToMemberData *>()->begin();
 246 }
 247
 248 nonloc::PointerToMember::iterator nonloc::PointerToMember::end() const {
 249   const PTMDataType PTMD = getPTMData();
 250   if (PTMD.is<const NamedDecl *>())
 251     return {};
 252   return PTMD.get<const PointerToMemberData *>()->end();
 253 }
 254
 255 //===----------------------------------------------------------------------===//
 256 // Useful predicates.
 257 //===----------------------------------------------------------------------===//
 258
 259 bool SVal::isConstant() const {
 260   return getAs<nonloc::ConcreteInt>() || getAs<loc::ConcreteInt>();
 261 }
 262
 263 bool SVal::isConstant(int I) const {
 264   if (Optional<loc::ConcreteInt> LV = getAs<loc::ConcreteInt>())
 265     return LV->getValue() == I;
 266   if (Optional<nonloc::ConcreteInt> NV = getAs<nonloc::ConcreteInt>())
 267     return NV->getValue() == I;
 268   return false;
 269 }
 270
 271 bool SVal::isZeroConstant() const {
 272   return isConstant(0);
 273 }
 274
 275 //===----------------------------------------------------------------------===//
 276 // Transfer function dispatch for Non-Locs.
 277 //===----------------------------------------------------------------------===//
 278
 279 SVal nonloc::ConcreteInt::evalBinOp(SValBuilder &svalBuilder,
 280                                     BinaryOperator::Opcode Op,
 281                                     const nonloc::ConcreteInt& R) const {
 282   const llvm::APSInt* X =
 283     svalBuilder.getBasicValueFactory().evalAPSInt(Op, getValue(), R.getValue());
 284
 285   if (X)
 286     return nonloc::ConcreteInt(*X);
 287   else
 288     return UndefinedVal();
 289 }
 290
 291 nonloc::ConcreteInt
 292 nonloc::ConcreteInt::evalComplement(SValBuilder &svalBuilder) const {
 293   return svalBuilder.makeIntVal(~getValue());
 294 }
 295
 296 nonloc::ConcreteInt
 297 nonloc::ConcreteInt::evalMinus(SValBuilder &svalBuilder) const {
 298   return svalBuilder.makeIntVal(-getValue());
 299 }
 300
 301 //===----------------------------------------------------------------------===//
 302 // Transfer function dispatch for Locs.
 303 //===----------------------------------------------------------------------===//
 304
 305 SVal loc::ConcreteInt::evalBinOp(BasicValueFactory& BasicVals,
 306                                  BinaryOperator::Opcode Op,
 307                                  const loc::ConcreteInt& R) const {
 308   assert(BinaryOperator::isComparisonOp(Op) || Op == BO_Sub);
 309
 310   const llvm::APSInt *X = BasicVals.evalAPSInt(Op, getValue(), R.getValue());
 311
 312   if (X)
 313     return nonloc::ConcreteInt(*X);
 314   else
 315     return UndefinedVal();
 316 }
 317
 318 //===----------------------------------------------------------------------===//
 319 // Pretty-Printing.
 320 //===----------------------------------------------------------------------===//
 321
 322 LLVM_DUMP_METHOD void SVal::dump() const { dumpToStream(llvm::errs()); }
 323
 324 void SVal::printJson(raw_ostream &Out, bool AddQuotes) const {
 325   std::string Buf;
 326   llvm::raw_string_ostream TempOut(Buf);
 327
 328   dumpToStream(TempOut);
 329
 330   Out << JsonFormat(TempOut.str(), AddQuotes);
 331 }
 332
 333 void SVal::dumpToStream(raw_ostream &os) const {
 334   switch (getBaseKind()) {
 335     case UnknownValKind:
 336       os << "Unknown";
 337       break;
 338     case NonLocKind:
 339       castAs<NonLoc>().dumpToStream(os);
 340       break;
 341     case LocKind:
 342       castAs<Loc>().dumpToStream(os);
 343       break;
 344     case UndefinedValKind:
 345       os << "Undefined";
 346       break;
 347   }
 348 }
 349
 350 void NonLoc::dumpToStream(raw_ostream &os) const {
 351   switch (getSubKind()) {
 352     case nonloc::ConcreteIntKind: {
 353       const auto &Value = castAs<nonloc::ConcreteInt>().getValue();
 354       os << Value << ' ' << (Value.isSigned() ? 'S' : 'U')
 355          << Value.getBitWidth() << 'b';
 356       break;
 357     }
 358     case nonloc::SymbolValKind:
 359       os << castAs<nonloc::SymbolVal>().getSymbol();
 360       break;
 361
 362     case nonloc::LocAsIntegerKind: {
 363       const nonloc::LocAsInteger& C = castAs<nonloc::LocAsInteger>();
 364       os << C.getLoc() << " [as " << C.getNumBits() << " bit integer]";
 365       break;
 366     }
 367     case nonloc::CompoundValKind: {
 368       const nonloc::CompoundVal& C = castAs<nonloc::CompoundVal>();
 369       os << "compoundVal{";
 370       bool first = true;
 371       for (const auto &I : C) {
 372         if (first) {
 373           os << ' '; first = false;
 374         }
 375         else
 376           os << ", ";
 377
 378         I.dumpToStream(os);
 379       }
 380       os << "}";
 381       break;
 382     }
 383     case nonloc::LazyCompoundValKind: {
 384       const nonloc::LazyCompoundVal &C = castAs<nonloc::LazyCompoundVal>();
 385       os << "lazyCompoundVal{" << const_cast<void *>(C.getStore())
 386          << ',' << C.getRegion()
 387          << '}';
 388       break;
 389     }
 390     case nonloc::PointerToMemberKind: {
 391       os << "pointerToMember{";
 392       const nonloc::PointerToMember &CastRes =
 393           castAs<nonloc::PointerToMember>();
 394       if (CastRes.getDecl())
 395         os << "|" << CastRes.getDecl()->getQualifiedNameAsString() << "|";
 396       bool first = true;
 397       for (const auto &I : CastRes) {
 398         if (first) {
 399           os << ' '; first = false;
 400         }
 401         else
 402           os << ", ";
 403
 404         os << (*I).getType().getAsString();
 405       }
 406
 407       os << '}';
 408       break;
 409     }
 410     default:
 411       assert(false && "Pretty-printed not implemented for this NonLoc.");
 412       break;
 413   }
 414 }
 415
 416 void Loc::dumpToStream(raw_ostream &os) const {
 417   switch (getSubKind()) {
 418     case loc::ConcreteIntKind:
 419       os << castAs<loc::ConcreteInt>().getValue().getZExtValue() << " (Loc)";
 420       break;
 421     case loc::GotoLabelKind:
 422       os << "&&" << castAs<loc::GotoLabel>().getLabel()->getName();
 423       break;
 424     case loc::MemRegionValKind:
 425       os << '&' << castAs<loc::MemRegionVal>().getRegion()->getString();
 426       break;
 427     default:
 428       llvm_unreachable("Pretty-printing not implemented for this Loc.");
 429   }
 430 }