LLDB  mainline
PostfixExpression.h
Go to the documentation of this file.
1 //===-- PostfixExpression.h -------------------------------------*- 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 implements support for postfix expressions found in several symbol
10 // file formats, and their conversion to DWARF.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLDB_SYMBOL_POSTFIXEXPRESSION_H
15 #define LLDB_SYMBOL_POSTFIXEXPRESSION_H
16 
17 #include "llvm/ADT/StringRef.h"
18 #include "llvm/Support/Allocator.h"
19 #include "llvm/Support/Casting.h"
20 #include <vector>
21 
22 namespace lldb_private {
23 
24 class Stream;
25 
26 namespace postfix {
27 
28 /// The base class for all nodes in the parsed postfix tree.
29 class Node {
30 public:
31  enum Kind {
38  };
39 
40 protected:
41  Node(Kind kind) : m_kind(kind) {}
42 
43 public:
44  Kind GetKind() const { return m_kind; }
45 
46 private:
48 };
49 
50 /// A node representing a binary expression.
51 class BinaryOpNode : public Node {
52 public:
53  enum OpType {
54  Align, // alignDown(a, b)
55  Minus, // a - b
56  Plus, // a + b
57  };
58 
59  BinaryOpNode(OpType op_type, Node &left, Node &right)
60  : Node(BinaryOp), m_op_type(op_type), m_left(&left), m_right(&right) {}
61 
62  OpType GetOpType() const { return m_op_type; }
63 
64  const Node *Left() const { return m_left; }
65  Node *&Left() { return m_left; }
66 
67  const Node *Right() const { return m_right; }
68  Node *&Right() { return m_right; }
69 
70  static bool classof(const Node *node) { return node->GetKind() == BinaryOp; }
71 
72 private:
76 };
77 
78 /// A node representing the canonical frame address.
79 class InitialValueNode: public Node {
80 public:
82 
83  static bool classof(const Node *node) {
84  return node->GetKind() == InitialValue;
85  }
86 };
87 
88 /// A node representing an integer literal.
89 class IntegerNode : public Node {
90 public:
91  IntegerNode(int64_t value) : Node(Integer), m_value(value) {}
92 
93  int64_t GetValue() const { return m_value; }
94 
95  static bool classof(const Node *node) { return node->GetKind() == Integer; }
96 
97 private:
98  int64_t m_value;
99 };
100 
101 /// A node representing the value of a register with the given register number.
102 /// The register kind (RegisterKind enum) used for the specifying the register
103 /// number is implicit and assumed to be the same for all Register nodes in a
104 /// given tree.
105 class RegisterNode : public Node {
106 public:
107  RegisterNode(uint32_t reg_num) : Node(Register), m_reg_num(reg_num) {}
108 
109  uint32_t GetRegNum() const { return m_reg_num; }
110 
111  static bool classof(const Node *node) { return node->GetKind() == Register; }
112 
113 private:
115 };
116 
117 /// A node representing a symbolic reference to a named entity. This may be a
118 /// register, which hasn't yet been resolved to a RegisterNode.
119 class SymbolNode : public Node {
120 public:
121  SymbolNode(llvm::StringRef name) : Node(Symbol), m_name(name) {}
122 
123  llvm::StringRef GetName() const { return m_name; }
124 
125  static bool classof(const Node *node) { return node->GetKind() == Symbol; }
126 
127 private:
128  llvm::StringRef m_name;
129 };
130 
131 /// A node representing a unary operation.
132 class UnaryOpNode : public Node {
133 public:
134  enum OpType {
135  Deref, // *a
136  };
137 
138  UnaryOpNode(OpType op_type, Node &operand)
139  : Node(UnaryOp), m_op_type(op_type), m_operand(&operand) {}
140 
141  OpType GetOpType() const { return m_op_type; }
142 
143  const Node *Operand() const { return m_operand; }
144  Node *&Operand() { return m_operand; }
145 
146  static bool classof(const Node *node) { return node->GetKind() == UnaryOp; }
147 
148 private:
151 };
152 
153 /// A template class implementing a visitor pattern, but with a couple of
154 /// twists:
155 /// - It uses type switch instead of virtual double dispatch. This allows the
156 // node classes to be vtable-free and trivially destructible.
157 /// - The Visit functions get an extra Node *& parameter, which refers to the
158 /// child pointer of the parent of the node we are currently visiting. This
159 /// allows mutating algorithms, which replace the currently visited node with
160 /// a different one.
161 /// - The class is templatized on the return type of the Visit functions, which
162 /// means it's possible to return values from them.
163 template <typename ResultT = void> class Visitor {
164 protected:
165  virtual ~Visitor() = default;
166 
167  virtual ResultT Visit(BinaryOpNode &binary, Node *&ref) = 0;
168  virtual ResultT Visit(InitialValueNode &val, Node *&ref) = 0;
169  virtual ResultT Visit(IntegerNode &integer, Node *&) = 0;
170  virtual ResultT Visit(RegisterNode &reg, Node *&) = 0;
171  virtual ResultT Visit(SymbolNode &symbol, Node *&ref) = 0;
172  virtual ResultT Visit(UnaryOpNode &unary, Node *&ref) = 0;
173 
174  /// Invoke the correct Visit function based on the dynamic type of the given
175  /// node.
176  ResultT Dispatch(Node *&node) {
177  switch (node->GetKind()) {
178  case Node::BinaryOp:
179  return Visit(llvm::cast<BinaryOpNode>(*node), node);
180  case Node::InitialValue:
181  return Visit(llvm::cast<InitialValueNode>(*node), node);
182  case Node::Integer:
183  return Visit(llvm::cast<IntegerNode>(*node), node);
184  case Node::Register:
185  return Visit(llvm::cast<RegisterNode>(*node), node);
186  case Node::Symbol:
187  return Visit(llvm::cast<SymbolNode>(*node), node);
188  case Node::UnaryOp:
189  return Visit(llvm::cast<UnaryOpNode>(*node), node);
190  }
191  llvm_unreachable("Fully covered switch!");
192  }
193 };
194 
195 /// A utility function for "resolving" SymbolNodes. It traverses a tree and
196 /// calls the callback function for all SymbolNodes it encountered. The
197 /// replacement function should return the node it wished to replace the current
198 /// SymbolNode with (this can also be the original node), or nullptr in case of
199 /// an error. The nodes returned by the callback are inspected and replaced
200 /// recursively, *except* for the case when the function returns the exact same
201 /// node as the input one. It returns true if all SymbolNodes were replaced
202 /// successfully.
203 bool ResolveSymbols(Node *&node,
204  llvm::function_ref<Node *(SymbolNode &symbol)> replacer);
205 
206 template <typename T, typename... Args>
207 inline T *MakeNode(llvm::BumpPtrAllocator &alloc, Args &&... args) {
208  static_assert(std::is_trivially_destructible<T>::value,
209  "This object will not be destroyed!");
210  return new (alloc.Allocate<T>()) T(std::forward<Args>(args)...);
211 }
212 
213 /// Parse the given postfix expression. The parsed nodes are placed into the
214 /// provided allocator.
215 Node *ParseOneExpression(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc);
216 
217 std::vector<std::pair<llvm::StringRef, Node *>>
218 ParseFPOProgram(llvm::StringRef prog, llvm::BumpPtrAllocator &alloc);
219 
220 /// Serialize the given expression tree as DWARF. The result is written into the
221 /// given stream. The AST should not contain any SymbolNodes. If the expression
222 /// contains InitialValueNodes, the generated expression will assume that their
223 /// value will be provided as the top value of the initial evaluation stack (as
224 /// is the case with the CFA value in register eh_unwind rules).
225 void ToDWARF(Node &node, Stream &stream);
226 
227 } // namespace postfix
228 } // namespace lldb_private
229 
230 #endif // LLDB_SYMBOL_POSTFIXEXPRESSION_H
lldb_private::postfix::Node::GetKind
Kind GetKind() const
Definition: PostfixExpression.h:44
lldb_private::postfix::BinaryOpNode::m_op_type
OpType m_op_type
Definition: PostfixExpression.h:73
lldb_private::postfix::InitialValueNode::classof
static bool classof(const Node *node)
Definition: PostfixExpression.h:83
lldb_private::postfix::UnaryOpNode::Deref
@ Deref
Definition: PostfixExpression.h:135
lldb_private::postfix::BinaryOpNode::m_right
Node * m_right
Definition: PostfixExpression.h:75
lldb_private::Symbol
Definition: Symbol.h:20
lldb_private::postfix::Node
The base class for all nodes in the parsed postfix tree.
Definition: PostfixExpression.h:29
lldb_private::postfix::Node::m_kind
Kind m_kind
Definition: PostfixExpression.h:47
lldb_private::postfix::BinaryOpNode::Left
const Node * Left() const
Definition: PostfixExpression.h:64
lldb_private::postfix::ResolveSymbols
bool ResolveSymbols(Node *&node, llvm::function_ref< Node *(SymbolNode &symbol)> replacer)
A utility function for "resolving" SymbolNodes.
lldb_private::postfix::SymbolNode::m_name
llvm::StringRef m_name
Definition: PostfixExpression.h:128
lldb_private::postfix::Node::Symbol
@ Symbol
Definition: PostfixExpression.h:36
lldb_private::postfix::Node::Register
@ Register
Definition: PostfixExpression.h:35
lldb_private::postfix::RegisterNode
A node representing the value of a register with the given register number.
Definition: PostfixExpression.h:105
lldb_private::postfix::ToDWARF
void ToDWARF(Node &node, Stream &stream)
Serialize the given expression tree as DWARF.
Definition: PostfixExpression.cpp:245
lldb_private::postfix::RegisterNode::classof
static bool classof(const Node *node)
Definition: PostfixExpression.h:111
lldb_private::postfix::UnaryOpNode::Operand
const Node * Operand() const
Definition: PostfixExpression.h:143
lldb_private::Stream
Definition: Stream.h:28
lldb_private::postfix::Node::BinaryOp
@ BinaryOp
Definition: PostfixExpression.h:32
lldb_private::Args
Definition: Args.h:33
lldb_private::postfix::IntegerNode::classof
static bool classof(const Node *node)
Definition: PostfixExpression.h:95
lldb_private::postfix::Node::Node
Node(Kind kind)
Definition: PostfixExpression.h:41
lldb_private::postfix::UnaryOpNode::m_op_type
OpType m_op_type
Definition: PostfixExpression.h:149
lldb_private::postfix::Node::Kind
Kind
Definition: PostfixExpression.h:31
lldb_private::postfix::UnaryOpNode::m_operand
Node * m_operand
Definition: PostfixExpression.h:150
lldb_private::postfix::Visitor
A template class implementing a visitor pattern, but with a couple of twists:
Definition: PostfixExpression.h:163
lldb_private::postfix::Visitor::Visit
virtual ResultT Visit(BinaryOpNode &binary, Node *&ref)=0
lldb_private::postfix::IntegerNode::IntegerNode
IntegerNode(int64_t value)
Definition: PostfixExpression.h:91
lldb_private::postfix::UnaryOpNode::UnaryOpNode
UnaryOpNode(OpType op_type, Node &operand)
Definition: PostfixExpression.h:138
lldb_private::postfix::MakeNode
T * MakeNode(llvm::BumpPtrAllocator &alloc, Args &&... args)
Definition: PostfixExpression.h:207
lldb_private::postfix::UnaryOpNode::OpType
OpType
Definition: PostfixExpression.h:134
lldb_private::postfix::BinaryOpNode::Left
Node *& Left()
Definition: PostfixExpression.h:65
lldb_private::postfix::Node::InitialValue
@ InitialValue
Definition: PostfixExpression.h:33
lldb_private::postfix::IntegerNode::m_value
int64_t m_value
Definition: PostfixExpression.h:98
lldb_private::postfix::UnaryOpNode::GetOpType
OpType GetOpType() const
Definition: PostfixExpression.h:141
lldb_private::postfix::UnaryOpNode::Operand
Node *& Operand()
Definition: PostfixExpression.h:144
lldb_private::postfix::SymbolNode::SymbolNode
SymbolNode(llvm::StringRef name)
Definition: PostfixExpression.h:121
lldb_private::postfix::BinaryOpNode::GetOpType
OpType GetOpType() const
Definition: PostfixExpression.h:62
lldb_private::postfix::SymbolNode::GetName
llvm::StringRef GetName() const
Definition: PostfixExpression.h:123
lldb_private::postfix::InitialValueNode::InitialValueNode
InitialValueNode()
Definition: PostfixExpression.h:81
lldb_private::postfix::UnaryOpNode::classof
static bool classof(const Node *node)
Definition: PostfixExpression.h:146
lldb_private::postfix::IntegerNode
A node representing an integer literal.
Definition: PostfixExpression.h:89
lldb_private::postfix::BinaryOpNode::Align
@ Align
Definition: PostfixExpression.h:54
lldb_private::postfix::BinaryOpNode::Plus
@ Plus
Definition: PostfixExpression.h:56
uint32_t
lldb_private::postfix::ParseOneExpression
Node * ParseOneExpression(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc)
Parse the given postfix expression.
Definition: PostfixExpression.cpp:44
lldb_private::postfix::RegisterNode::m_reg_num
uint32_t m_reg_num
Definition: PostfixExpression.h:114
lldb_private::postfix::BinaryOpNode::BinaryOpNode
BinaryOpNode(OpType op_type, Node &left, Node &right)
Definition: PostfixExpression.h:59
lldb_private::postfix::ParseFPOProgram
std::vector< std::pair< llvm::StringRef, Node * > > ParseFPOProgram(llvm::StringRef prog, llvm::BumpPtrAllocator &alloc)
Definition: PostfixExpression.cpp:88
lldb_private::postfix::Node::UnaryOp
@ UnaryOp
Definition: PostfixExpression.h:37
lldb_private::postfix::RegisterNode::GetRegNum
uint32_t GetRegNum() const
Definition: PostfixExpression.h:109
lldb_private::postfix::SymbolNode::classof
static bool classof(const Node *node)
Definition: PostfixExpression.h:125
lldb_private::postfix::SymbolNode
A node representing a symbolic reference to a named entity.
Definition: PostfixExpression.h:119
lldb_private::postfix::BinaryOpNode::classof
static bool classof(const Node *node)
Definition: PostfixExpression.h:70
lldb_private::postfix::UnaryOpNode
A node representing a unary operation.
Definition: PostfixExpression.h:132
lldb_private::postfix::BinaryOpNode::Minus
@ Minus
Definition: PostfixExpression.h:55
lldb_private::postfix::IntegerNode::GetValue
int64_t GetValue() const
Definition: PostfixExpression.h:93
lldb_private::postfix::BinaryOpNode::Right
const Node * Right() const
Definition: PostfixExpression.h:67
lldb_private
A class that represents a running process on the host machine.
Definition: SBCommandInterpreterRunOptions.h:16
lldb_private::postfix::BinaryOpNode::m_left
Node * m_left
Definition: PostfixExpression.h:74
lldb_private::postfix::BinaryOpNode::OpType
OpType
Definition: PostfixExpression.h:53
lldb_private::postfix::BinaryOpNode
A node representing a binary expression.
Definition: PostfixExpression.h:51
lldb_private::postfix::RegisterNode::RegisterNode
RegisterNode(uint32_t reg_num)
Definition: PostfixExpression.h:107
integer
#define integer
Definition: EmulateInstructionARM64.cpp:75
lldb_private::postfix::BinaryOpNode::Right
Node *& Right()
Definition: PostfixExpression.h:68
lldb_private::postfix::Node::Integer
@ Integer
Definition: PostfixExpression.h:34
lldb_private::postfix::Visitor::~Visitor
virtual ~Visitor()=default
lldb_private::postfix::Visitor::Dispatch
ResultT Dispatch(Node *&node)
Invoke the correct Visit function based on the dynamic type of the given node.
Definition: PostfixExpression.h:176
lldb_private::postfix::InitialValueNode
A node representing the canonical frame address.
Definition: PostfixExpression.h:79