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:
43   SymExpr(Kind k) : K(k) {}
44 
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 
56   Kind getKind() const { return K; }
57 
58   virtual void dump() const;
59 
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 
86   symbol_iterator symbol_begin() const { return symbol_iterator(this); }
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.
101   /// It might return null.
102   virtual const MemRegion *getOriginRegion() const { return nullptr; }
103 };
104 
105 inline raw_ostream &operator<<(raw_ostream &os,
106                                const clang::ento::SymExpr *SE) {
107   SE->dumpToStream(os);
108   return os;
109 }
110 
111 using SymbolRef = const SymExpr *;
112 using SymbolRefSmallVectorTy = SmallVector<SymbolRef, 2>;
113 using SymbolID = unsigned;
114 
115 /// A symbol representing data which can be stored in a memory location
116 /// (region).
117 class SymbolData : public SymExpr {
118   const SymbolID Sym;
119 
120   void anchor() override;
121 
122 protected:
123   SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {
124     assert(classof(this));
125   }
126 
127 public:
128   ~SymbolData() override = default;
129 
130   /// Get a string representation of the kind of the region.
131   virtual StringRef getKindStr() const = 0;
132 
133   SymbolID getSymbolID() const { return Sym; }
134 
135   unsigned computeComplexity() const override {
136     return 1;
137   };
138 
139   // Implement isa<T> support.
140   static inline bool classof(const SymExpr *SE) {
141     Kind k = SE->getKind();
142     return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS;
143   }
144 };
145 
146 } // namespace ento
147 } // namespace clang
148 
149 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H
150