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
22namespace lldb_private {
23
24class Stream;
25
26namespace postfix {
27
28/// The base class for all nodes in the parsed postfix tree.
29class Node {
30public:
31  enum Kind {
32    BinaryOp,
33    InitialValue,
34    Integer,
35    Register,
36    Symbol,
37    UnaryOp,
38  };
39
40protected:
41  Node(Kind kind) : m_kind(kind) {}
42
43public:
44  Kind GetKind() const { return m_kind; }
45
46private:
47  Kind m_kind;
48};
49
50/// A node representing a binary expression.
51class BinaryOpNode : public Node {
52public:
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
72private:
73  OpType m_op_type;
74  Node *m_left;
75  Node *m_right;
76};
77
78/// A node representing the canonical frame address.
79class InitialValueNode: public Node {
80public:
81  InitialValueNode() : Node(InitialValue) {}
82
83  static bool classof(const Node *node) {
84    return node->GetKind() == InitialValue;
85  }
86};
87
88/// A node representing an integer literal.
89class IntegerNode : public Node {
90public:
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
97private:
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.
105class RegisterNode : public Node {
106public:
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
113private:
114  uint32_t m_reg_num;
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.
119class SymbolNode : public Node {
120public:
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
127private:
128  llvm::StringRef m_name;
129};
130
131/// A node representing a unary operation.
132class UnaryOpNode : public Node {
133public:
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
148private:
149  OpType m_op_type;
150  Node *m_operand;
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.
163template <typename ResultT = void> class Visitor {
164protected:
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.
203bool ResolveSymbols(Node *&node,
204                    llvm::function_ref<Node *(SymbolNode &symbol)> replacer);
205
206template <typename T, typename... Args>
207inline 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.
215Node *ParseOneExpression(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc);
216
217std::vector<std::pair<llvm::StringRef, Node *>>
218ParseFPOProgram(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).
225void ToDWARF(Node &node, Stream &stream);
226
227} // namespace postfix
228} // namespace lldb_private
229
230#endif // LLDB_SYMBOL_POSTFIXEXPRESSION_H
231