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
28/// Symbolic value. These values used to capture symbolic execution of
29/// the program.
30class SymExpr : public llvm::FoldingSetNode {
31 virtual void anchor();
32
33public:
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
40private:
41 Kind K;
42
43protected:
44 SymExpr(Kind k) : K(k) {}
45
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
54public:
55 virtual ~SymExpr() = default;
56
57 Kind getKind() const { return K; }
58
59 virtual void dump() const;
60
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
87 llvm::iterator_range<symbol_iterator> symbols() const {
88 return llvm::make_range(x: symbol_iterator(this), y: 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.
104 virtual const MemRegion *getOriginRegion() const { return nullptr; }
105};
106
107inline raw_ostream &operator<<(raw_ostream &os,
108 const clang::ento::SymExpr *SE) {
109 SE->dumpToStream(os);
110 return os;
111}
112
113using SymbolRef = const SymExpr *;
114using SymbolRefSmallVectorTy = SmallVector<SymbolRef, 2>;
115using SymbolID = unsigned;
116
117/// A symbol representing data which can be stored in a memory location
118/// (region).
119class SymbolData : public SymExpr {
120 const SymbolID Sym;
121
122 void anchor() override;
123
124protected:
125 SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {
126 assert(classof(this));
127 }
128
129public:
130 ~SymbolData() override = default;
131
132 /// Get a string representation of the kind of the region.
133 virtual StringRef getKindStr() const = 0;
134
135 SymbolID getSymbolID() const { return Sym; }
136
137 unsigned computeComplexity() const override {
138 return 1;
139 };
140
141 // Implement isa<T> support.
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