Index: lldb/trunk/include/lldb/Symbol/PostfixExpression.h =================================================================== --- lldb/trunk/include/lldb/Symbol/PostfixExpression.h +++ lldb/trunk/include/lldb/Symbol/PostfixExpression.h @@ -15,6 +15,7 @@ #define LLDB_SYMBOL_POSTFIXEXPRESSION_H #include "llvm/ADT/StringRef.h" +#include "llvm/Support/Allocator.h" #include "llvm/Support/Casting.h" namespace lldb_private { @@ -173,6 +174,17 @@ } }; +template +inline T *MakeNode(llvm::BumpPtrAllocator &alloc, Args &&... args) { + static_assert(std::is_trivially_destructible::value, + "This object will not be destroyed!"); + return new (alloc.Allocate()) T(std::forward(args)...); +} + +/// Parse the given postfix expression. The parsed nodes are placed into the +/// provided allocator. +Node *Parse(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc); + } // namespace postfix } // namespace lldb_private Index: lldb/trunk/source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp =================================================================== --- lldb/trunk/source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp +++ lldb/trunk/source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp @@ -26,19 +26,6 @@ namespace { -class NodeAllocator { -public: - template T *makeNode(Args &&... args) { - static_assert(std::is_trivially_destructible::value, - "This object will not be destroyed!"); - void *new_node_mem = m_alloc.Allocate(sizeof(T), alignof(T)); - return new (new_node_mem) T(std::forward(args)...); - } - -private: - llvm::BumpPtrAllocator m_alloc; -}; - class FPOProgramASTVisitorMergeDependent : public Visitor<> { public: void Visit(BinaryOpNode &binary, Node *&) override { @@ -81,7 +68,8 @@ public: static bool Resolve(const llvm::DenseMap &dependent_programs, - llvm::Triple::ArchType arch_type, NodeAllocator &alloc, Node *&ast) { + llvm::Triple::ArchType arch_type, llvm::BumpPtrAllocator &alloc, + Node *&ast) { return FPOProgramASTVisitorResolveRegisterRefs(dependent_programs, arch_type, alloc) .Dispatch(ast); @@ -104,13 +92,13 @@ private: FPOProgramASTVisitorResolveRegisterRefs( const llvm::DenseMap &dependent_programs, - llvm::Triple::ArchType arch_type, NodeAllocator &alloc) + llvm::Triple::ArchType arch_type, llvm::BumpPtrAllocator &alloc) : m_dependent_programs(dependent_programs), m_arch_type(arch_type), m_alloc(alloc) {} const llvm::DenseMap &m_dependent_programs; llvm::Triple::ArchType m_arch_type; - NodeAllocator &m_alloc; + llvm::BumpPtrAllocator &m_alloc; }; static uint32_t ResolveLLDBRegisterNum(llvm::StringRef reg_name, llvm::Triple::ArchType arch_type) { @@ -145,7 +133,7 @@ if (reg_num == LLDB_INVALID_REGNUM) return false; - ref = m_alloc.makeNode(reg_num); + ref = MakeNode(m_alloc, reg_num); return true; } @@ -227,95 +215,23 @@ } // namespace static bool ParseFPOSingleAssignmentProgram(llvm::StringRef program, - NodeAllocator &alloc, + llvm::BumpPtrAllocator &alloc, llvm::StringRef ®ister_name, Node *&ast) { - llvm::SmallVector tokens; - llvm::SplitString(program, tokens, " "); - - if (tokens.empty()) - return false; - - llvm::SmallVector eval_stack; - - llvm::DenseMap ops_binary = { - {"+", BinaryOpNode::Plus}, - {"-", BinaryOpNode::Minus}, - {"@", BinaryOpNode::Align}, - }; - - llvm::DenseMap ops_unary = { - {"^", UnaryOpNode::Deref}, - }; - - constexpr llvm::StringLiteral ra_search_keyword = ".raSearch"; - // lvalue of assignment is always first token // rvalue program goes next - for (size_t i = 1; i < tokens.size(); ++i) { - llvm::StringRef cur = tokens[i]; - - auto ops_binary_it = ops_binary.find(cur); - if (ops_binary_it != ops_binary.end()) { - // token is binary operator - if (eval_stack.size() < 2) { - return false; - } - Node *right = eval_stack.pop_back_val(); - Node *left = eval_stack.pop_back_val(); - Node *node = - alloc.makeNode(ops_binary_it->second, *left, *right); - eval_stack.push_back(node); - continue; - } - - auto ops_unary_it = ops_unary.find(cur); - if (ops_unary_it != ops_unary.end()) { - // token is unary operator - if (eval_stack.empty()) { - return false; - } - Node *operand = eval_stack.pop_back_val(); - Node *node = alloc.makeNode(ops_unary_it->second, *operand); - eval_stack.push_back(node); - continue; - } - - if (cur.startswith("$")) { - eval_stack.push_back(alloc.makeNode(cur)); - continue; - } - - if (cur == ra_search_keyword) { - // TODO: .raSearch is unsupported - return false; - } - - uint32_t value; - if (!cur.getAsInteger(10, value)) { - // token is integer literal - eval_stack.push_back(alloc.makeNode(value)); - continue; - } - - // unexpected token + std::tie(register_name, program) = getToken(program); + if (register_name.empty()) return false; - } - if (eval_stack.size() != 1) { - return false; - } - - register_name = tokens[0]; - ast = eval_stack.pop_back_val(); - - return true; + ast = Parse(program, alloc); + return ast != nullptr; } static Node *ParseFPOProgram(llvm::StringRef program, llvm::StringRef register_name, llvm::Triple::ArchType arch_type, - NodeAllocator &alloc) { + llvm::BumpPtrAllocator &alloc) { llvm::DenseMap dependent_programs; size_t cur = 0; @@ -365,7 +281,7 @@ bool lldb_private::npdb::TranslateFPOProgramToDWARFExpression( llvm::StringRef program, llvm::StringRef register_name, llvm::Triple::ArchType arch_type, Stream &stream) { - NodeAllocator node_alloc; + llvm::BumpPtrAllocator node_alloc; Node *target_program = ParseFPOProgram(program, register_name, arch_type, node_alloc); if (target_program == nullptr) { Index: lldb/trunk/source/Symbol/CMakeLists.txt =================================================================== --- lldb/trunk/source/Symbol/CMakeLists.txt +++ lldb/trunk/source/Symbol/CMakeLists.txt @@ -26,6 +26,7 @@ LineTable.cpp LocateSymbolFile.cpp ObjectFile.cpp + PostfixExpression.cpp Symbol.cpp SymbolContext.cpp SymbolFile.cpp Index: lldb/trunk/source/Symbol/PostfixExpression.cpp =================================================================== --- lldb/trunk/source/Symbol/PostfixExpression.cpp +++ lldb/trunk/source/Symbol/PostfixExpression.cpp @@ -0,0 +1,82 @@ +//===-- PostfixExpression.cpp -----------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements support for postfix expressions found in several symbol +// file formats, and their conversion to DWARF. +// +//===----------------------------------------------------------------------===// + +#include "lldb/Symbol/PostfixExpression.h" +#include "llvm/ADT/StringExtras.h" + +using namespace lldb_private; +using namespace lldb_private::postfix; + +static llvm::Optional +GetBinaryOpType(llvm::StringRef token) { + if (token.size() != 1) + return llvm::None; + switch (token[0]) { + case '@': + return BinaryOpNode::Align; + case '-': + return BinaryOpNode::Minus; + case '+': + return BinaryOpNode::Plus; + } + return llvm::None; +} + +static llvm::Optional +GetUnaryOpType(llvm::StringRef token) { + if (token == "^") + return UnaryOpNode::Deref; + return llvm::None; +} + +Node *postfix::Parse(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc) { + llvm::SmallVector stack; + + llvm::StringRef token; + while (std::tie(token, expr) = getToken(expr), !token.empty()) { + if (auto op_type = GetBinaryOpType(token)) { + // token is binary operator + if (stack.size() < 2) + return nullptr; + + Node *right = stack.pop_back_val(); + Node *left = stack.pop_back_val(); + stack.push_back(MakeNode(alloc, *op_type, *left, *right)); + continue; + } + + if (auto op_type = GetUnaryOpType(token)) { + // token is unary operator + if (stack.empty()) + return nullptr; + + Node *operand = stack.pop_back_val(); + stack.push_back(MakeNode(alloc, *op_type, *operand)); + continue; + } + + uint32_t value; + if (to_integer(token, value, 10)) { + // token is integer literal + stack.push_back(MakeNode(alloc, value)); + continue; + } + + stack.push_back(MakeNode(alloc, token)); + } + + if (stack.size() != 1) + return nullptr; + + return stack.back(); +} Index: lldb/trunk/unittests/Symbol/CMakeLists.txt =================================================================== --- lldb/trunk/unittests/Symbol/CMakeLists.txt +++ lldb/trunk/unittests/Symbol/CMakeLists.txt @@ -1,5 +1,6 @@ add_lldb_unittest(SymbolTests LocateSymbolFileTest.cpp + PostfixExpressionTest.cpp TestClangASTContext.cpp TestDWARFCallFrameInfo.cpp TestType.cpp Index: lldb/trunk/unittests/Symbol/PostfixExpressionTest.cpp =================================================================== --- lldb/trunk/unittests/Symbol/PostfixExpressionTest.cpp +++ lldb/trunk/unittests/Symbol/PostfixExpressionTest.cpp @@ -0,0 +1,97 @@ +//===-- PostfixExpressionTest.cpp -------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "lldb/Symbol/PostfixExpression.h" +#include "llvm/Support/FormatVariadic.h" +#include "llvm/Support/raw_ostream.h" +#include "gtest/gtest.h" + +using namespace lldb_private; +using namespace lldb_private::postfix; + +static std::string ToString(BinaryOpNode::OpType type) { + switch (type) { + case BinaryOpNode::Align: + return "@"; + case BinaryOpNode::Minus: + return "-"; + case BinaryOpNode::Plus: + return "+"; + } + llvm_unreachable("Fully covered switch!"); +} + +static std::string ToString(UnaryOpNode::OpType type) { + switch (type) { + case UnaryOpNode::Deref: + return "^"; + } + llvm_unreachable("Fully covered switch!"); +} + +struct ASTPrinter : public Visitor { +protected: + std::string Visit(BinaryOpNode &binary, Node *&) override { + return llvm::formatv("{0}({1}, {2})", ToString(binary.GetOpType()), + Dispatch(binary.Left()), Dispatch(binary.Right())); + } + + std::string Visit(IntegerNode &integer, Node *&) override { + return llvm::formatv("int({0})", integer.GetValue()); + } + + std::string Visit(RegisterNode ®, Node *&) override { + return llvm::formatv("reg({0})", reg.GetRegNum()); + } + + std::string Visit(SymbolNode &symbol, Node *&) override { + return symbol.GetName(); + } + + std::string Visit(UnaryOpNode &unary, Node *&) override { + return llvm::formatv("{0}({1})", ToString(unary.GetOpType()), + Dispatch(unary.Operand())); + } + +public: + static std::string Print(Node *node) { + if (node) + return ASTPrinter().Dispatch(node); + return "nullptr"; + } +}; + +static std::string ParseAndStringify(llvm::StringRef expr) { + llvm::BumpPtrAllocator alloc; + return ASTPrinter::Print(Parse(expr, alloc)); +} + +TEST(PostfixExpression, Parse) { + EXPECT_EQ("int(47)", ParseAndStringify("47")); + EXPECT_EQ("$foo", ParseAndStringify("$foo")); + EXPECT_EQ("+(int(1), int(2))", ParseAndStringify("1 2 +")); + EXPECT_EQ("-(int(1), int(2))", ParseAndStringify("1 2 -")); + EXPECT_EQ("@(int(1), int(2))", ParseAndStringify("1 2 @")); + EXPECT_EQ("+(int(1), +(int(2), int(3)))", ParseAndStringify("1 2 3 + +")); + EXPECT_EQ("+(+(int(1), int(2)), int(3))", ParseAndStringify("1 2 + 3 +")); + EXPECT_EQ("^(int(1))", ParseAndStringify("1 ^")); + EXPECT_EQ("^(^(int(1)))", ParseAndStringify("1 ^ ^")); + EXPECT_EQ("^(+(int(1), ^(int(2))))", ParseAndStringify("1 2 ^ + ^")); + EXPECT_EQ("-($foo, int(47))", ParseAndStringify("$foo 47 -")); + + EXPECT_EQ("nullptr", ParseAndStringify("+")); + EXPECT_EQ("nullptr", ParseAndStringify("^")); + EXPECT_EQ("nullptr", ParseAndStringify("1 +")); + EXPECT_EQ("nullptr", ParseAndStringify("1 2 ^")); + EXPECT_EQ("nullptr", ParseAndStringify("1 2 3 +")); + EXPECT_EQ("nullptr", ParseAndStringify("^ 1")); + EXPECT_EQ("nullptr", ParseAndStringify("+ 1 2")); + EXPECT_EQ("nullptr", ParseAndStringify("1 + 2")); + EXPECT_EQ("nullptr", ParseAndStringify("1 2")); + EXPECT_EQ("nullptr", ParseAndStringify("")); +}