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