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
22namespace clang {
23namespace ento {
24
25class MemRegion;
26
27/// Symbolic value. These values used to capture symbolic execution of
28/// the program.
29class SymExpr : public llvm::FoldingSetNode {
30 virtual void anchor();
31
32public:
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
39private:
40 Kind K;
41
42protected:
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
53public:
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 virtual const MemRegion *getOriginRegion() const { return nullptr; }
102};
103
104inline raw_ostream &operator<<(raw_ostream &os,
105 const clang::ento::SymExpr *SE) {
106 SE->dumpToStream(os);
107 return os;
108}
109
110using SymbolRef = const SymExpr *;
111using SymbolRefSmallVectorTy = SmallVector<SymbolRef, 2>;
112using SymbolID = unsigned;
113
114/// A symbol representing data which can be stored in a memory location
115/// (region).
116class SymbolData : public SymExpr {
117 const SymbolID Sym;
118
119 void anchor() override;
120
121protected:
122 SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {
123 assert(classof(this));
124 }
125
126public:
127 ~SymbolData() override = default;
128
129 /// Get a string representation of the kind of the region.
130 virtual StringRef getKindStr() const = 0;
131
132 SymbolID getSymbolID() const { return Sym; }
133
134 unsigned computeComplexity() const override {
135 return 1;
136 };
137
138 // Implement isa<T> support.
139 static inline bool classof(const SymExpr *SE) {
140 Kind k = SE->getKind();
141 return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS;
142 }
143};
144
145} // namespace ento
146} // namespace clang
147
148#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H
149