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 ®, 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