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 /// Symbolic value. These values used to capture symbolic execution of 29 /// the program. 30 class SymExpr : public llvm::FoldingSetNode { 31 virtual void anchor(); 32 33 public: 34 enum Kind { 35 #define SYMBOL(Id, Parent) Id##Kind, 36 #define SYMBOL_RANGE(Id, First, Last) BEGIN_##Id = First, END_##Id = Last, 37 #include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def" 38 }; 39 40 private: 41 Kind K; 42 43 protected: SymExpr(Kind k)44 SymExpr(Kind k) : K(k) {} 45 isValidTypeForSymbol(QualType T)46 static bool isValidTypeForSymbol(QualType T) { 47 // FIXME: Depending on whether we choose to deprecate structural symbols, 48 // this may become much stricter. 49 return !T.isNull() && !T->isVoidType(); 50 } 51 52 mutable unsigned Complexity = 0; 53 54 public: 55 virtual ~SymExpr() = default; 56 getKind()57 Kind getKind() const { return K; } 58 59 virtual void dump() const; 60 dumpToStream(raw_ostream & os)61 virtual void dumpToStream(raw_ostream &os) const {} 62 63 virtual QualType getType() const = 0; 64 virtual void Profile(llvm::FoldingSetNodeID &profile) = 0; 65 66 /// Iterator over symbols that the current symbol depends on. 67 /// 68 /// For SymbolData, it's the symbol itself; for expressions, it's the 69 /// expression symbol and all the operands in it. Note, SymbolDerived is 70 /// treated as SymbolData - the iterator will NOT visit the parent region. 71 class symbol_iterator { 72 SmallVector<const SymExpr *, 5> itr; 73 74 void expand(); 75 76 public: 77 symbol_iterator() = default; 78 symbol_iterator(const SymExpr *SE); 79 80 symbol_iterator &operator++(); 81 const SymExpr *operator*(); 82 83 bool operator==(const symbol_iterator &X) const; 84 bool operator!=(const symbol_iterator &X) const; 85 }; 86 symbols()87 llvm::iterator_range<symbol_iterator> symbols() const { 88 return llvm::make_range(symbol_iterator(this), symbol_iterator()); 89 } 90 91 virtual unsigned computeComplexity() const = 0; 92 93 /// Find the region from which this symbol originates. 94 /// 95 /// Whenever the symbol was constructed to denote an unknown value of 96 /// a certain memory region, return this region. This method 97 /// allows checkers to make decisions depending on the origin of the symbol. 98 /// Symbol classes for which the origin region is known include 99 /// SymbolRegionValue which denotes the value of the region before 100 /// the beginning of the analysis, and SymbolDerived which denotes the value 101 /// of a certain memory region after its super region (a memory space or 102 /// a larger record region) is default-bound with a certain symbol. 103 /// It might return null. getOriginRegion()104 virtual const MemRegion *getOriginRegion() const { return nullptr; } 105 }; 106 107 inline raw_ostream &operator<<(raw_ostream &os, 108 const clang::ento::SymExpr *SE) { 109 SE->dumpToStream(os); 110 return os; 111 } 112 113 using SymbolRef = const SymExpr *; 114 using SymbolRefSmallVectorTy = SmallVector<SymbolRef, 2>; 115 using SymbolID = unsigned; 116 117 /// A symbol representing data which can be stored in a memory location 118 /// (region). 119 class SymbolData : public SymExpr { 120 const SymbolID Sym; 121 122 void anchor() override; 123 124 protected: SymbolData(Kind k,SymbolID sym)125 SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) { 126 assert(classof(this)); 127 } 128 129 public: 130 ~SymbolData() override = default; 131 132 /// Get a string representation of the kind of the region. 133 virtual StringRef getKindStr() const = 0; 134 getSymbolID()135 SymbolID getSymbolID() const { return Sym; } 136 computeComplexity()137 unsigned computeComplexity() const override { 138 return 1; 139 }; 140 141 // Implement isa<T> support. classof(const SymExpr * SE)142 static inline bool classof(const SymExpr *SE) { 143 Kind k = SE->getKind(); 144 return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS; 145 } 146 }; 147 148 } // namespace ento 149 } // namespace clang 150 151 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H 152