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
23namespace clang {
24namespace ento {
25
26class MemRegion;
27
28using SymbolID = unsigned;
29
30/// Symbolic value. These values used to capture symbolic execution of
31/// the program.
32class SymExpr : public llvm::FoldingSetNode {
33 virtual void anchor();
34
35public:
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
42private:
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
55protected:
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
66public:
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(x: symbol_iterator(this), y: 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
127inline raw_ostream &operator<<(raw_ostream &os,
128 const clang::ento::SymExpr *SE) {
129 SE->dumpToStream(os);
130 return os;
131}
132
133using SymbolRef = const SymExpr *;
134using SymbolRefSmallVectorTy = SmallVector<SymbolRef, 2>;
135
136/// A symbol representing data which can be stored in a memory location
137/// (region).
138class SymbolData : public SymExpr {
139 void anchor() override;
140
141protected:
142 SymbolData(Kind k, SymbolID sym) : SymExpr(k, sym) { assert(classof(this)); }
143
144public:
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 bool classof(const SymExpr *SE) { return classof(K: SE->getKind()); }
156 static constexpr bool classof(Kind K) {
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