1 //===- SVals.h - Abstract Values for Static Analysis ------------*- C++ -*-===// 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 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H 15 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H 16 17 #include "clang/AST/Expr.h" 18 #include "clang/AST/Type.h" 19 #include "clang/Basic/LLVM.h" 20 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" 21 #include "llvm/ADT/APSInt.h" 22 #include "llvm/ADT/FoldingSet.h" 23 #include "llvm/ADT/ImmutableList.h" 24 #include "llvm/ADT/PointerUnion.h" 25 #include "llvm/ADT/STLForwardCompat.h" 26 #include "llvm/ADT/iterator_range.h" 27 #include "llvm/Support/Casting.h" 28 #include <cassert> 29 #include <cstdint> 30 #include <optional> 31 #include <utility> 32 33 //==------------------------------------------------------------------------==// 34 // Base SVal types. 35 //==------------------------------------------------------------------------==// 36 37 namespace clang { 38 39 class CXXBaseSpecifier; 40 class FunctionDecl; 41 class LabelDecl; 42 43 namespace ento { 44 45 class CompoundValData; 46 class LazyCompoundValData; 47 class MemRegion; 48 class PointerToMemberData; 49 class SValBuilder; 50 class TypedValueRegion; 51 52 /// SVal - This represents a symbolic expression, which can be either 53 /// an L-value or an R-value. 54 /// 55 class SVal { 56 public: 57 enum SValKind : unsigned char { 58 #define BASIC_SVAL(Id, Parent) Id##Kind, 59 #define LOC_SVAL(Id, Parent) Loc##Id##Kind, 60 #define NONLOC_SVAL(Id, Parent) NonLoc##Id##Kind, 61 #define SVAL_RANGE(Id, First, Last) \ 62 BEGIN_##Id = Id##First##Kind, END_##Id = Id##Last##Kind, 63 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" 64 }; 65 66 protected: 67 const void *Data = nullptr; 68 SValKind Kind = UndefinedValKind; 69 70 explicit SVal(SValKind Kind, const void *Data = nullptr) Data(Data)71 : Data(Data), Kind(Kind) {} 72 castDataAs()73 template <typename T> const T *castDataAs() const { 74 return static_cast<const T *>(Data); 75 } 76 77 public: 78 explicit SVal() = default; 79 80 /// Convert to the specified SVal type, asserting that this SVal is of 81 /// the desired type. castAs()82 template <typename T> T castAs() const { return llvm::cast<T>(*this); } 83 84 /// Convert to the specified SVal type, returning std::nullopt if this SVal is 85 /// not of the desired type. getAs()86 template <typename T> std::optional<T> getAs() const { 87 return llvm::dyn_cast<T>(*this); 88 } 89 getKind()90 SValKind getKind() const { return Kind; } 91 92 // This method is required for using SVal in a FoldingSetNode. It 93 // extracts a unique signature for this SVal object. Profile(llvm::FoldingSetNodeID & ID)94 void Profile(llvm::FoldingSetNodeID &ID) const { 95 ID.AddPointer(Data); 96 ID.AddInteger(llvm::to_underlying(getKind())); 97 } 98 99 bool operator==(SVal R) const { return Kind == R.Kind && Data == R.Data; } 100 bool operator!=(SVal R) const { return !(*this == R); } 101 isUnknown()102 bool isUnknown() const { return getKind() == UnknownValKind; } 103 isUndef()104 bool isUndef() const { return getKind() == UndefinedValKind; } 105 isUnknownOrUndef()106 bool isUnknownOrUndef() const { return isUnknown() || isUndef(); } 107 isValid()108 bool isValid() const { return !isUnknownOrUndef(); } 109 110 bool isConstant() const; 111 112 bool isConstant(int I) const; 113 114 bool isZeroConstant() const; 115 116 /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a 117 /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl. 118 /// Otherwise return 0. 119 const FunctionDecl *getAsFunctionDecl() const; 120 121 /// If this SVal is a location and wraps a symbol, return that 122 /// SymbolRef. 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 getAsLocSymbol(bool IncludeBaseRegions = false) const; 128 129 /// Get the symbol in the SVal or its base region. 130 SymbolRef getLocSymbolInBase() const; 131 132 /// If this SVal wraps a symbol return that SymbolRef. 133 /// Otherwise, return 0. 134 /// 135 /// Casts are ignored during lookup. 136 /// \param IncludeBaseRegions The boolean that controls whether the search 137 /// should continue to the base regions if the region is not symbolic. 138 SymbolRef getAsSymbol(bool IncludeBaseRegions = false) const; 139 140 /// If this SVal is loc::ConcreteInt or nonloc::ConcreteInt, 141 /// return a pointer to APSInt which is held in it. 142 /// Otherwise, return nullptr. 143 const llvm::APSInt *getAsInteger() const; 144 145 const MemRegion *getAsRegion() const; 146 147 /// printJson - Pretty-prints in JSON format. 148 void printJson(raw_ostream &Out, bool AddQuotes) const; 149 150 void dumpToStream(raw_ostream &OS) const; 151 void dump() const; 152 symbols()153 llvm::iterator_range<SymExpr::symbol_iterator> symbols() const { 154 if (const SymExpr *SE = getAsSymbol(/*IncludeBaseRegions=*/true)) 155 return SE->symbols(); 156 SymExpr::symbol_iterator end{}; 157 return llvm::make_range(end, end); 158 } 159 160 /// Try to get a reasonable type for the given value. 161 /// 162 /// \returns The best approximation of the value type or Null. 163 /// In theory, all symbolic values should be typed, but this function 164 /// is still a WIP and might have a few blind spots. 165 /// 166 /// \note This function should not be used when the user has access to the 167 /// bound expression AST node as well, since AST always has exact types. 168 /// 169 /// \note Loc values are interpreted as pointer rvalues for the purposes of 170 /// this method. 171 QualType getType(const ASTContext &) const; 172 }; 173 174 inline raw_ostream &operator<<(raw_ostream &os, clang::ento::SVal V) { 175 V.dumpToStream(os); 176 return os; 177 } 178 179 namespace nonloc { 180 /// Sub-kinds for NonLoc values. 181 #define NONLOC_SVAL(Id, Parent) \ 182 inline constexpr auto Id##Kind = SVal::SValKind::NonLoc##Id##Kind; 183 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" 184 } // namespace nonloc 185 186 namespace loc { 187 /// Sub-kinds for Loc values. 188 #define LOC_SVAL(Id, Parent) \ 189 inline constexpr auto Id##Kind = SVal::SValKind::Loc##Id##Kind; 190 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" 191 } // namespace loc 192 193 class UndefinedVal : public SVal { 194 public: UndefinedVal()195 UndefinedVal() : SVal(UndefinedValKind) {} classof(SVal V)196 static bool classof(SVal V) { return V.getKind() == UndefinedValKind; } 197 }; 198 199 class DefinedOrUnknownSVal : public SVal { 200 public: 201 // We want calling these methods to be a compiler error since they are 202 // tautologically false. 203 bool isUndef() const = delete; 204 bool isValid() const = delete; 205 classof(SVal V)206 static bool classof(SVal V) { return !V.isUndef(); } 207 208 protected: 209 explicit DefinedOrUnknownSVal(SValKind Kind, const void *Data = nullptr) SVal(Kind,Data)210 : SVal(Kind, Data) {} 211 }; 212 213 class UnknownVal : public DefinedOrUnknownSVal { 214 public: UnknownVal()215 explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {} 216 classof(SVal V)217 static bool classof(SVal V) { return V.getKind() == UnknownValKind; } 218 }; 219 220 class DefinedSVal : public DefinedOrUnknownSVal { 221 public: 222 // We want calling these methods to be a compiler error since they are 223 // tautologically true/false. 224 bool isUnknown() const = delete; 225 bool isUnknownOrUndef() const = delete; 226 bool isValid() const = delete; 227 classof(SVal V)228 static bool classof(SVal V) { return !V.isUnknownOrUndef(); } 229 230 protected: DefinedSVal(SValKind Kind,const void * Data)231 explicit DefinedSVal(SValKind Kind, const void *Data) 232 : DefinedOrUnknownSVal(Kind, Data) {} 233 }; 234 235 /// Represents an SVal that is guaranteed to not be UnknownVal. 236 class KnownSVal : public SVal { 237 public: KnownSVal(DefinedSVal V)238 /*implicit*/ KnownSVal(DefinedSVal V) : SVal(V) {} KnownSVal(UndefinedVal V)239 /*implicit*/ KnownSVal(UndefinedVal V) : SVal(V) {} classof(SVal V)240 static bool classof(SVal V) { return !V.isUnknown(); } 241 }; 242 243 class NonLoc : public DefinedSVal { 244 protected: NonLoc(SValKind Kind,const void * Data)245 NonLoc(SValKind Kind, const void *Data) : DefinedSVal(Kind, Data) {} 246 247 public: 248 void dumpToStream(raw_ostream &Out) const; 249 isCompoundType(QualType T)250 static bool isCompoundType(QualType T) { 251 return T->isArrayType() || T->isRecordType() || 252 T->isAnyComplexType() || T->isVectorType(); 253 } 254 classof(SVal V)255 static bool classof(SVal V) { 256 return BEGIN_NonLoc <= V.getKind() && V.getKind() <= END_NonLoc; 257 } 258 }; 259 260 class Loc : public DefinedSVal { 261 protected: Loc(SValKind Kind,const void * Data)262 Loc(SValKind Kind, const void *Data) : DefinedSVal(Kind, Data) {} 263 264 public: 265 void dumpToStream(raw_ostream &Out) const; 266 isLocType(QualType T)267 static bool isLocType(QualType T) { 268 return T->isAnyPointerType() || T->isBlockPointerType() || 269 T->isReferenceType() || T->isNullPtrType(); 270 } 271 classof(SVal V)272 static bool classof(SVal V) { 273 return BEGIN_Loc <= V.getKind() && V.getKind() <= END_Loc; 274 } 275 }; 276 277 //==------------------------------------------------------------------------==// 278 // Subclasses of NonLoc. 279 //==------------------------------------------------------------------------==// 280 281 namespace nonloc { 282 283 /// Represents symbolic expression that isn't a location. 284 class SymbolVal : public NonLoc { 285 public: 286 SymbolVal() = delete; SymbolVal(SymbolRef Sym)287 explicit SymbolVal(SymbolRef Sym) : NonLoc(SymbolValKind, Sym) { 288 assert(Sym); 289 assert(!Loc::isLocType(Sym->getType())); 290 } 291 292 LLVM_ATTRIBUTE_RETURNS_NONNULL getSymbol()293 SymbolRef getSymbol() const { 294 return (const SymExpr *) Data; 295 } 296 isExpression()297 bool isExpression() const { 298 return !isa<SymbolData>(getSymbol()); 299 } 300 classof(SVal V)301 static bool classof(SVal V) { return V.getKind() == SymbolValKind; } 302 }; 303 304 /// Value representing integer constant. 305 class ConcreteInt : public NonLoc { 306 public: ConcreteInt(const llvm::APSInt & V)307 explicit ConcreteInt(const llvm::APSInt &V) : NonLoc(ConcreteIntKind, &V) {} 308 getValue()309 const llvm::APSInt &getValue() const { return *castDataAs<llvm::APSInt>(); } 310 classof(SVal V)311 static bool classof(SVal V) { return V.getKind() == ConcreteIntKind; } 312 }; 313 314 class LocAsInteger : public NonLoc { 315 friend class ento::SValBuilder; 316 LocAsInteger(const std::pair<SVal,uintptr_t> & data)317 explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data) 318 : NonLoc(LocAsIntegerKind, &data) { 319 // We do not need to represent loc::ConcreteInt as LocAsInteger, 320 // as it'd collapse into a nonloc::ConcreteInt instead. 321 [[maybe_unused]] SValKind K = data.first.getKind(); 322 assert(K == loc::MemRegionValKind || K == loc::GotoLabelKind); 323 } 324 325 public: getLoc()326 Loc getLoc() const { 327 return castDataAs<std::pair<SVal, uintptr_t>>()->first.castAs<Loc>(); 328 } 329 getNumBits()330 unsigned getNumBits() const { 331 return castDataAs<std::pair<SVal, uintptr_t>>()->second; 332 } 333 classof(SVal V)334 static bool classof(SVal V) { return V.getKind() == LocAsIntegerKind; } 335 }; 336 337 class CompoundVal : public NonLoc { 338 friend class ento::SValBuilder; 339 CompoundVal(const CompoundValData * D)340 explicit CompoundVal(const CompoundValData *D) : NonLoc(CompoundValKind, D) { 341 assert(D); 342 } 343 344 public: 345 LLVM_ATTRIBUTE_RETURNS_NONNULL getValue()346 const CompoundValData* getValue() const { 347 return castDataAs<CompoundValData>(); 348 } 349 350 using iterator = llvm::ImmutableList<SVal>::iterator; 351 iterator begin() const; 352 iterator end() const; 353 classof(SVal V)354 static bool classof(SVal V) { return V.getKind() == CompoundValKind; } 355 }; 356 357 class LazyCompoundVal : public NonLoc { 358 friend class ento::SValBuilder; 359 LazyCompoundVal(const LazyCompoundValData * D)360 explicit LazyCompoundVal(const LazyCompoundValData *D) 361 : NonLoc(LazyCompoundValKind, D) { 362 assert(D); 363 } 364 365 public: 366 LLVM_ATTRIBUTE_RETURNS_NONNULL getCVData()367 const LazyCompoundValData *getCVData() const { 368 return castDataAs<LazyCompoundValData>(); 369 } 370 371 /// It might return null. 372 const void *getStore() const; 373 374 LLVM_ATTRIBUTE_RETURNS_NONNULL 375 const TypedValueRegion *getRegion() const; 376 classof(SVal V)377 static bool classof(SVal V) { return V.getKind() == LazyCompoundValKind; } 378 }; 379 380 /// Value representing pointer-to-member. 381 /// 382 /// This value is qualified as NonLoc because neither loading nor storing 383 /// operations are applied to it. Instead, the analyzer uses the L-value coming 384 /// from pointer-to-member applied to an object. 385 /// This SVal is represented by a NamedDecl which can be a member function 386 /// pointer or a member data pointer and an optional list of CXXBaseSpecifiers. 387 /// This list is required to accumulate the pointer-to-member cast history to 388 /// figure out the correct subobject field. In particular, implicit casts grow 389 /// this list and explicit casts like static_cast shrink this list. 390 class PointerToMember : public NonLoc { 391 friend class ento::SValBuilder; 392 393 public: 394 using PTMDataType = 395 llvm::PointerUnion<const NamedDecl *, const PointerToMemberData *>; 396 getPTMData()397 const PTMDataType getPTMData() const { 398 return PTMDataType::getFromOpaqueValue(const_cast<void *>(Data)); 399 } 400 401 bool isNullMemberPointer() const; 402 403 const NamedDecl *getDecl() const; 404 405 template<typename AdjustedDecl> getDeclAs()406 const AdjustedDecl *getDeclAs() const { 407 return dyn_cast_or_null<AdjustedDecl>(getDecl()); 408 } 409 410 using iterator = llvm::ImmutableList<const CXXBaseSpecifier *>::iterator; 411 412 iterator begin() const; 413 iterator end() const; 414 classof(SVal V)415 static bool classof(SVal V) { return V.getKind() == PointerToMemberKind; } 416 417 private: PointerToMember(const PTMDataType D)418 explicit PointerToMember(const PTMDataType D) 419 : NonLoc(PointerToMemberKind, D.getOpaqueValue()) {} 420 }; 421 422 } // namespace nonloc 423 424 //==------------------------------------------------------------------------==// 425 // Subclasses of Loc. 426 //==------------------------------------------------------------------------==// 427 428 namespace loc { 429 430 class GotoLabel : public Loc { 431 public: GotoLabel(const LabelDecl * Label)432 explicit GotoLabel(const LabelDecl *Label) : Loc(GotoLabelKind, Label) { 433 assert(Label); 434 } 435 getLabel()436 const LabelDecl *getLabel() const { return castDataAs<LabelDecl>(); } 437 classof(SVal V)438 static bool classof(SVal V) { return V.getKind() == GotoLabelKind; } 439 }; 440 441 class MemRegionVal : public Loc { 442 public: MemRegionVal(const MemRegion * r)443 explicit MemRegionVal(const MemRegion *r) : Loc(MemRegionValKind, r) { 444 assert(r); 445 } 446 447 /// Get the underlining region. 448 LLVM_ATTRIBUTE_RETURNS_NONNULL getRegion()449 const MemRegion *getRegion() const { return castDataAs<MemRegion>(); } 450 451 /// Get the underlining region and strip casts. 452 LLVM_ATTRIBUTE_RETURNS_NONNULL 453 const MemRegion* stripCasts(bool StripBaseCasts = true) const; 454 455 template <typename REGION> getRegionAs()456 const REGION* getRegionAs() const { 457 return dyn_cast<REGION>(getRegion()); 458 } 459 460 bool operator==(const MemRegionVal &R) const { 461 return getRegion() == R.getRegion(); 462 } 463 464 bool operator!=(const MemRegionVal &R) const { 465 return getRegion() != R.getRegion(); 466 } 467 classof(SVal V)468 static bool classof(SVal V) { return V.getKind() == MemRegionValKind; } 469 }; 470 471 class ConcreteInt : public Loc { 472 public: ConcreteInt(const llvm::APSInt & V)473 explicit ConcreteInt(const llvm::APSInt &V) : Loc(ConcreteIntKind, &V) {} 474 getValue()475 const llvm::APSInt &getValue() const { return *castDataAs<llvm::APSInt>(); } 476 classof(SVal V)477 static bool classof(SVal V) { return V.getKind() == ConcreteIntKind; } 478 }; 479 480 } // namespace loc 481 } // namespace ento 482 } // namespace clang 483 484 namespace llvm { 485 template <typename To, typename From> 486 struct CastInfo< 487 To, From, 488 std::enable_if_t<std::is_base_of<::clang::ento::SVal, From>::value>> 489 : public CastIsPossible<To, ::clang::ento::SVal> { 490 using Self = CastInfo< 491 To, From, 492 std::enable_if_t<std::is_base_of<::clang::ento::SVal, From>::value>>; 493 static bool isPossible(const From &V) { 494 return To::classof(*static_cast<const ::clang::ento::SVal *>(&V)); 495 } 496 static std::optional<To> castFailed() { return std::optional<To>{}; } 497 static To doCast(const From &f) { 498 return *static_cast<const To *>(cast<::clang::ento::SVal>(&f)); 499 } 500 static std::optional<To> doCastIfPossible(const From &f) { 501 if (!Self::isPossible(f)) 502 return Self::castFailed(); 503 return doCast(f); 504 } 505 }; 506 } // namespace llvm 507 508 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H 509