PostfixExpression: move parser out of NativePDB internals

[labath]

Summary

The postfix expressions in PDB and breakpad symbol files are similar
enough that they can be parsed by the same parser. This patch
generalizes the parser in the NativePDB plugin and moves it into the
PostfixExpression file created in the previous commit (r358976).

The generalization consists of treating any unrecognised token as a
"symbol" node (previously these would only be created for tokens
starting with "$", and other token would abort the parse). This is
needed because breakpad symbols can also contain ".cfa" tokens, which
refer to the frame's CFA.

The cosmetic changes include:

• using a factory function instead of a class for creating nodes (this is more generic as it allows the same BumpPtrAllocator to be used for other things too)
• using dedicated function for parsing operator tokens instead of a DenseMap (more efficient as we don't need to create the DenseMap every time).

[aleksandr.urakov]

LGTM, thanks!

[amccarth]

Nice. Thanks for adding the test, too!

lldb/trunk/include/lldb/Symbol/PostfixExpression.h

 //  file formats, and their conversion to DWARF.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLDB_SYMBOL_POSTFIXEXPRESSION_H
 #define LLDB_SYMBOL_POSTFIXEXPRESSION_H
 
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Allocator.h"
 #include "llvm/Support/Casting.h"
 
 namespace lldb_private {
 namespace postfix {
 
 /// The base class for all nodes in the parsed postfix tree.
 class Node {
 public:
case Node::Symbol:
       return Visit(llvm::cast<SymbolNode>(*node), node);
     case Node::UnaryOp:
       return Visit(llvm::cast<UnaryOpNode>(*node), node);
     }
     llvm_unreachable("Fully covered switch!");
   }
 };
 
+template <typename T, typename... Args>
+inline T *MakeNode(llvm::BumpPtrAllocator &alloc, Args &&... args) {
+  static_assert(std::is_trivially_destructible<T>::value,
+                "This object will not be destroyed!");
+  return new (alloc.Allocate<T>()) T(std::forward<Args>(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
 
 #endif // LLDB_SYMBOL_POSTFIXEXPRESSION_H

lldb/trunk/source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp

 #include "llvm/DebugInfo/CodeView/EnumTables.h"
 
 using namespace lldb;
 using namespace lldb_private;
 using namespace lldb_private::postfix;
 
 namespace {
 
-class NodeAllocator {
-public:
-  template <typename T, typename... Args> T *makeNode(Args &&... args) {
-    static_assert(std::is_trivially_destructible<T>::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>(args)...);
-  }
-
-private:
-  llvm::BumpPtrAllocator m_alloc;
-};
-
 class FPOProgramASTVisitorMergeDependent : public Visitor<> {
 public:
   void Visit(BinaryOpNode &binary, Node *&) override {
     Dispatch(binary.Left());
     Dispatch(binary.Right());
   }
 
   void Visit(UnaryOpNode &unary, Node *&) override {
void FPOProgramASTVisitorMergeDependent::Visit(SymbolNode &symbol, Node *&ref) {
   ref = it->second;
   Dispatch(ref);
 }
 
 class FPOProgramASTVisitorResolveRegisterRefs : public Visitor<bool> {
 public:
   static bool
   Resolve(const llvm::DenseMap<llvm::StringRef, Node *> &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);
   }
 
   bool Visit(BinaryOpNode &binary, Node *&) override {
     return Dispatch(binary.Left()) && Dispatch(binary.Right());
   }
 
   bool Visit(UnaryOpNode &unary, Node *&) override {
     return Dispatch(unary.Operand());
   }
 
   bool Visit(RegisterNode &, Node *&) override { return true; }
 
   bool Visit(IntegerNode &, Node *&) override { return true; }
 
   bool Visit(SymbolNode &symbol, Node *&ref) override;
 
 private:
   FPOProgramASTVisitorResolveRegisterRefs(
       const llvm::DenseMap<llvm::StringRef, Node *> &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<llvm::StringRef, Node *> &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) {
   // lookup register name to get lldb register number
   llvm::ArrayRef<llvm::EnumEntry<uint16_t>> register_names =
       llvm::codeview::getRegisterNames();
   auto it = llvm::find_if(
       register_names,
bool FPOProgramASTVisitorResolveRegisterRefs::Visit(SymbolNode &symbol,
   }
 
   uint32_t reg_num =
       ResolveLLDBRegisterNum(symbol.GetName().drop_front(1), m_arch_type);
 
   if (reg_num == LLDB_INVALID_REGNUM)
     return false;
 
-  ref = m_alloc.makeNode<RegisterNode>(reg_num);
+  ref = MakeNode<RegisterNode>(m_alloc, reg_num);
   return true;
 }
 
 class FPOProgramASTVisitorDWARFCodegen : public Visitor<> {
 public:
   static void Emit(Stream &stream, Node *&ast) {
     FPOProgramASTVisitorDWARFCodegen(stream).Dispatch(ast);
   }
case UnaryOpNode::Deref:
     m_out_stream.PutHex8(DW_OP_deref);
     break;
   }
 }
 
 } // namespace
 
 static bool ParseFPOSingleAssignmentProgram(llvm::StringRef program,
-                                            NodeAllocator &alloc,
+                                            llvm::BumpPtrAllocator &alloc,
                                             llvm::StringRef &register_name,
                                             Node *&ast) {
-  llvm::SmallVector<llvm::StringRef, 16> tokens;
-  llvm::SplitString(program, tokens, " ");
-
-  if (tokens.empty())
-    return false;
-
-  llvm::SmallVector<Node *, 4> eval_stack;
-
-  llvm::DenseMap<llvm::StringRef, BinaryOpNode::OpType> ops_binary = {
-      {"+", BinaryOpNode::Plus},
-      {"-", BinaryOpNode::Minus},
-      {"@", BinaryOpNode::Align},
-  };
-
-  llvm::DenseMap<llvm::StringRef, UnaryOpNode::OpType> 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<BinaryOpNode>(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<UnaryOpNode>(ops_unary_it->second, *operand);
-      eval_stack.push_back(node);
-      continue;
-    }
-
-    if (cur.startswith("$")) {
-      eval_stack.push_back(alloc.makeNode<SymbolNode>(cur));
-      continue;
-    }
-
-    if (cur == ra_search_keyword) {
-      // TODO: .raSearch is unsupported
-      return false;
-    }
+  std::tie(register_name, program) = getToken(program);
+  if (register_name.empty())
 
-    uint32_t value;
-    if (!cur.getAsInteger(10, value)) {
-      // token is integer literal
-      eval_stack.push_back(alloc.makeNode<IntegerNode>(value));
-      continue;
-    }
-
-    // unexpected token
-    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<llvm::StringRef, Node *> dependent_programs;
 
   size_t cur = 0;
   while (true) {
     size_t assign_index = program.find('=', cur);
     if (assign_index == llvm::StringRef::npos) {
       llvm::StringRef tail = program.slice(cur, llvm::StringRef::npos);
       if (!tail.trim().empty()) {
static Node *ParseFPOProgram(llvm::StringRef program,
   }
 
   return nullptr;
 }
 
 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) {
     return false;
   }
 
   FPOProgramASTVisitorDWARFCodegen::Emit(stream, target_program);
   return true;
 }

lldb/trunk/source/Symbol/CMakeLists.txt

add_lldb_library(lldbSymbol
   Declaration.cpp
   DWARFCallFrameInfo.cpp
   Function.cpp
   FuncUnwinders.cpp
   LineEntry.cpp
   LineTable.cpp
   LocateSymbolFile.cpp
   ObjectFile.cpp
+  PostfixExpression.cpp
   Symbol.cpp
   SymbolContext.cpp
   SymbolFile.cpp
   SymbolVendor.cpp
   Symtab.cpp
   Type.cpp
   TypeList.cpp
   TypeMap.cpp

lldb/trunk/source/Symbol/PostfixExpression.cpp

+//===-- 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<BinaryOpNode::OpType>
+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<UnaryOpNode::OpType>
+GetUnaryOpType(llvm::StringRef token) {
+  if (token == "^")
+    return UnaryOpNode::Deref;
+  return llvm::None;
+}
+
+Node *postfix::Parse(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc) {
+  llvm::SmallVector<Node *, 4> 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<BinaryOpNode>(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<UnaryOpNode>(alloc, *op_type, *operand));
+      continue;
+    }
+
+    uint32_t value;
+    if (to_integer(token, value, 10)) {
+      // token is integer literal
+      stack.push_back(MakeNode<IntegerNode>(alloc, value));
+      continue;
+    }
+
+    stack.push_back(MakeNode<SymbolNode>(alloc, token));
+  }
+
+  if (stack.size() != 1)
+    return nullptr;
+
+  return stack.back();
+}

lldb/trunk/unittests/Symbol/CMakeLists.txt

 add_lldb_unittest(SymbolTests
   LocateSymbolFileTest.cpp
+  PostfixExpressionTest.cpp
   TestClangASTContext.cpp
   TestDWARFCallFrameInfo.cpp
   TestType.cpp
 
   LINK_LIBS
     lldbHost
     lldbSymbol
     lldbUtilityHelpers

lldb/trunk/unittests/Symbol/PostfixExpressionTest.cpp

+//===-- 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<std::string> {
+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 &reg, 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(""));
+}