lldb/Symbol/PostfixExpression.h

0001 //===-- PostfixExpression.h -------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 //  This file implements support for postfix expressions found in several symbol
0010 //  file formats, and their conversion to DWARF.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLDB_SYMBOL_POSTFIXEXPRESSION_H
0015 #define LLDB_SYMBOL_POSTFIXEXPRESSION_H
0016
0017 #include "llvm/ADT/StringRef.h"
0018 #include "llvm/Support/Allocator.h"
0019 #include "llvm/Support/Casting.h"
0020 #include <vector>
0021
0022 namespace lldb_private {
0023
0024 class Stream;
0025
0026 namespace postfix {
0027
0028 /// The base class for all nodes in the parsed postfix tree.
0029 class Node {
0030 public:
0031   enum Kind {
0032     BinaryOp,
0033     InitialValue,
0034     Integer,
0035     Register,
0036     Symbol,
0037     UnaryOp,
0038   };
0039
0040 protected:
0041   Node(Kind kind) : m_kind(kind) {}
0042
0043 public:
0044   Kind GetKind() const { return m_kind; }
0045
0046 private:
0047   Kind m_kind;
0048 };
0049
0050 /// A node representing a binary expression.
0051 class BinaryOpNode : public Node {
0052 public:
0053   enum OpType {
0054     Align, // alignDown(a, b)
0055     Minus, // a - b
0056     Plus,  // a + b
0057   };
0058
0059   BinaryOpNode(OpType op_type, Node &left, Node &right)
0060       : Node(BinaryOp), m_op_type(op_type), m_left(&left), m_right(&right) {}
0061
0062   OpType GetOpType() const { return m_op_type; }
0063
0064   const Node *Left() const { return m_left; }
0065   Node *&Left() { return m_left; }
0066
0067   const Node *Right() const { return m_right; }
0068   Node *&Right() { return m_right; }
0069
0070   static bool classof(const Node *node) { return node->GetKind() == BinaryOp; }
0071
0072 private:
0073   OpType m_op_type;
0074   Node *m_left;
0075   Node *m_right;
0076 };
0077
0078 /// A node representing the canonical frame address.
0079 class InitialValueNode: public Node {
0080 public:
0081   InitialValueNode() : Node(InitialValue) {}
0082
0083   static bool classof(const Node *node) {
0084     return node->GetKind() == InitialValue;
0085   }
0086 };
0087
0088 /// A node representing an integer literal.
0089 class IntegerNode : public Node {
0090 public:
0091   IntegerNode(int64_t value) : Node(Integer), m_value(value) {}
0092
0093   int64_t GetValue() const { return m_value; }
0094
0095   static bool classof(const Node *node) { return node->GetKind() == Integer; }
0096
0097 private:
0098   int64_t m_value;
0099 };
0100
0101 /// A node representing the value of a register with the given register number.
0102 /// The register kind (RegisterKind enum) used for the specifying the register
0103 /// number is implicit and assumed to be the same for all Register nodes in a
0104 /// given tree.
0105 class RegisterNode : public Node {
0106 public:
0107   RegisterNode(uint32_t reg_num) : Node(Register), m_reg_num(reg_num) {}
0108
0109   uint32_t GetRegNum() const { return m_reg_num; }
0110
0111   static bool classof(const Node *node) { return node->GetKind() == Register; }
0112
0113 private:
0114   uint32_t m_reg_num;
0115 };
0116
0117 /// A node representing a symbolic reference to a named entity. This may be a
0118 /// register, which hasn't yet been resolved to a RegisterNode.
0119 class SymbolNode : public Node {
0120 public:
0121   SymbolNode(llvm::StringRef name) : Node(Symbol), m_name(name) {}
0122
0123   llvm::StringRef GetName() const { return m_name; }
0124
0125   static bool classof(const Node *node) { return node->GetKind() == Symbol; }
0126
0127 private:
0128   llvm::StringRef m_name;
0129 };
0130
0131 /// A node representing a unary operation.
0132 class UnaryOpNode : public Node {
0133 public:
0134   enum OpType {
0135     Deref, // *a
0136   };
0137
0138   UnaryOpNode(OpType op_type, Node &operand)
0139       : Node(UnaryOp), m_op_type(op_type), m_operand(&operand) {}
0140
0141   OpType GetOpType() const { return m_op_type; }
0142
0143   const Node *Operand() const { return m_operand; }
0144   Node *&Operand() { return m_operand; }
0145
0146   static bool classof(const Node *node) { return node->GetKind() == UnaryOp; }
0147
0148 private:
0149   OpType m_op_type;
0150   Node *m_operand;
0151 };
0152
0153 /// A template class implementing a visitor pattern, but with a couple of
0154 /// twists:
0155 /// - It uses type switch instead of virtual double dispatch. This allows the
0156 //    node classes to be vtable-free and trivially destructible.
0157 /// - The Visit functions get an extra Node *& parameter, which refers to the
0158 ///   child pointer of the parent of the node we are currently visiting. This
0159 ///   allows mutating algorithms, which replace the currently visited node with
0160 ///   a different one.
0161 /// - The class is templatized on the return type of the Visit functions, which
0162 ///   means it's possible to return values from them.
0163 template <typename ResultT = void> class Visitor {
0164 protected:
0165   virtual ~Visitor() = default;
0166
0167   virtual ResultT Visit(BinaryOpNode &binary, Node *&ref) = 0;
0168   virtual ResultT Visit(InitialValueNode &val, Node *&ref) = 0;
0169   virtual ResultT Visit(IntegerNode &integer, Node *&) = 0;
0170   virtual ResultT Visit(RegisterNode &reg, Node *&) = 0;
0171   virtual ResultT Visit(SymbolNode &symbol, Node *&ref) = 0;
0172   virtual ResultT Visit(UnaryOpNode &unary, Node *&ref) = 0;
0173
0174   /// Invoke the correct Visit function based on the dynamic type of the given
0175   /// node.
0176   ResultT Dispatch(Node *&node) {
0177     switch (node->GetKind()) {
0178     case Node::BinaryOp:
0179       return Visit(llvm::cast<BinaryOpNode>(*node), node);
0180     case Node::InitialValue:
0181       return Visit(llvm::cast<InitialValueNode>(*node), node);
0182     case Node::Integer:
0183       return Visit(llvm::cast<IntegerNode>(*node), node);
0184     case Node::Register:
0185       return Visit(llvm::cast<RegisterNode>(*node), node);
0186     case Node::Symbol:
0187       return Visit(llvm::cast<SymbolNode>(*node), node);
0188     case Node::UnaryOp:
0189       return Visit(llvm::cast<UnaryOpNode>(*node), node);
0190     }
0191     llvm_unreachable("Fully covered switch!");
0192   }
0193 };
0194
0195 /// A utility function for "resolving" SymbolNodes. It traverses a tree and
0196 /// calls the callback function for all SymbolNodes it encountered. The
0197 /// replacement function should return the node it wished to replace the current
0198 /// SymbolNode with (this can also be the original node), or nullptr in case of
0199 /// an error. The nodes returned by the callback are inspected and replaced
0200 /// recursively, *except* for the case when the function returns the exact same
0201 /// node as the input one. It returns true if all SymbolNodes were replaced
0202 /// successfully.
0203 bool ResolveSymbols(Node *&node,
0204                     llvm::function_ref<Node *(SymbolNode &symbol)> replacer);
0205
0206 template <typename T, typename... Args>
0207 inline T *MakeNode(llvm::BumpPtrAllocator &alloc, Args &&... args) {
0208   static_assert(std::is_trivially_destructible<T>::value,
0209                 "This object will not be destroyed!");
0210   return new (alloc.Allocate<T>()) T(std::forward<Args>(args)...);
0211 }
0212
0213 /// Parse the given postfix expression. The parsed nodes are placed into the
0214 /// provided allocator.
0215 Node *ParseOneExpression(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc);
0216
0217 std::vector<std::pair<llvm::StringRef, Node *>>
0218 ParseFPOProgram(llvm::StringRef prog, llvm::BumpPtrAllocator &alloc);
0219
0220 /// Serialize the given expression tree as DWARF. The result is written into the
0221 /// given stream. The AST should not contain any SymbolNodes. If the expression
0222 /// contains InitialValueNodes, the generated expression will assume that their
0223 /// value will be provided as the top value of the initial evaluation stack (as
0224 /// is the case with the CFA value in register eh_unwind rules).
0225 void ToDWARF(Node &node, Stream &stream);
0226
0227 } // namespace postfix
0228 } // namespace lldb_private
0229
0230 #endif // LLDB_SYMBOL_POSTFIXEXPRESSION_H