1 //===- SymExpr.h - Management of Symbolic Values ----------------*- 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 SymExpr and SymbolData. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H 14 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H 15 16 #include "clang/AST/Type.h" 17 #include "clang/Basic/LLVM.h" 18 #include "llvm/ADT/FoldingSet.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/ADT/iterator_range.h" 21 #include <cassert> 22 23 namespace clang { 24 namespace ento { 25 26 class MemRegion; 27 28 using SymbolID = unsigned; 29 30 /// Symbolic value. These values used to capture symbolic execution of 31 /// the program. 32 class SymExpr : public llvm::FoldingSetNode { 33 virtual void anchor(); 34 35 public: 36 enum Kind { 37 #define SYMBOL(Id, Parent) Id##Kind, 38 #define SYMBOL_RANGE(Id, First, Last) BEGIN_##Id = First, END_##Id = Last, 39 #include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def" 40 }; 41 42 private: 43 Kind K; 44 /// A unique identifier for this symbol. 45 /// 46 /// It is useful for SymbolData to easily differentiate multiple symbols, but 47 /// also for "ephemeral" symbols, such as binary operations, because this id 48 /// can be used for arranging constraints or equivalence classes instead of 49 /// unstable pointer values. 50 /// 51 /// Note, however, that it can't be used in Profile because SymbolManager 52 /// needs to compute Profile before allocating SymExpr. 53 const SymbolID Sym; 54 55 protected: 56 SymExpr(Kind k, SymbolID Sym) : K(k), Sym(Sym) {} 57 58 static bool isValidTypeForSymbol(QualType T) { 59 // FIXME: Depending on whether we choose to deprecate structural symbols, 60 // this may become much stricter. 61 return !T.isNull() && !T->isVoidType(); 62 } 63 64 mutable unsigned Complexity = 0; 65 66 public: 67 virtual ~SymExpr() = default; 68 69 Kind getKind() const { return K; } 70 71 /// Get a unique identifier for this symbol. 72 /// The ID is unique across all SymExprs in a SymbolManager. 73 /// They reflect the allocation order of these SymExprs, 74 /// and are likely stable across runs. 75 /// Used as a key in SymbolRef containers and as part of identity 76 /// for SymbolData, e.g. SymbolConjured with ID = 7 is "conj_$7". 77 SymbolID getSymbolID() const { return Sym; } 78 79 virtual void dump() const; 80 81 virtual void dumpToStream(raw_ostream &os) const {} 82 83 virtual QualType getType() const = 0; 84 virtual void Profile(llvm::FoldingSetNodeID &profile) = 0; 85 86 /// Iterator over symbols that the current symbol depends on. 87 /// 88 /// For SymbolData, it's the symbol itself; for expressions, it's the 89 /// expression symbol and all the operands in it. Note, SymbolDerived is 90 /// treated as SymbolData - the iterator will NOT visit the parent region. 91 class symbol_iterator { 92 SmallVector<const SymExpr *, 5> itr; 93 94 void expand(); 95 96 public: 97 symbol_iterator() = default; 98 symbol_iterator(const SymExpr *SE); 99 100 symbol_iterator &operator++(); 101 const SymExpr *operator*(); 102 103 bool operator==(const symbol_iterator &X) const; 104 bool operator!=(const symbol_iterator &X) const; 105 }; 106 107 llvm::iterator_range<symbol_iterator> symbols() const { 108 return llvm::make_range(symbol_iterator(this), symbol_iterator()); 109 } 110 111 virtual unsigned computeComplexity() const = 0; 112 113 /// Find the region from which this symbol originates. 114 /// 115 /// Whenever the symbol was constructed to denote an unknown value of 116 /// a certain memory region, return this region. This method 117 /// allows checkers to make decisions depending on the origin of the symbol. 118 /// Symbol classes for which the origin region is known include 119 /// SymbolRegionValue which denotes the value of the region before 120 /// the beginning of the analysis, and SymbolDerived which denotes the value 121 /// of a certain memory region after its super region (a memory space or 122 /// a larger record region) is default-bound with a certain symbol. 123 /// It might return null. 124 virtual const MemRegion *getOriginRegion() const { return nullptr; } 125 }; 126 127 inline raw_ostream &operator<<(raw_ostream &os, 128 const clang::ento::SymExpr *SE) { 129 SE->dumpToStream(os); 130 return os; 131 } 132 133 using SymbolRef = const SymExpr *; 134 using SymbolRefSmallVectorTy = SmallVector<SymbolRef, 2>; 135 136 /// A symbol representing data which can be stored in a memory location 137 /// (region). 138 class SymbolData : public SymExpr { 139 void anchor() override; 140 141 protected: 142 SymbolData(Kind k, SymbolID sym) : SymExpr(k, sym) { assert(classof(this)); } 143 144 public: 145 ~SymbolData() override = default; 146 147 /// Get a string representation of the kind of the region. 148 virtual StringRef getKindStr() const = 0; 149 150 unsigned computeComplexity() const override { 151 return 1; 152 }; 153 154 // Implement isa<T> support. 155 static inline bool classof(const SymExpr *SE) { 156 Kind k = SE->getKind(); 157 return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS; 158 } 159 }; 160 161 } // namespace ento 162 } // namespace clang 163 164 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H 165