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