PostfixExpression: move DWARF generator out of NativePDB internals

Summary:
The new dwarf generator is pretty much a verbatim copy of the one in
PDB.

In order to write a pdb-independent test for it, I needed to write a
dummy "symbol resolver", which (together with the fact that I'll need
one more for breakpad-specific resolution logic) prompted me to create a
more simple interface for algorithms which replace or "resolve"
SymbolNodes. The resolving algorithms in NativePDB have been updated to
make use of that too.

I have removed a couple of NativePDB tests which weren't testing
anything pdb-specific and where the tested functionality was covered by
the new format-agnostic tests I have added.

Reviewers: amccarth, clayborg, aleksandr.urakov

Subscribers: aprantl, markmentovai, lldb-commits, jasonmolenda, JDevlieghere

Differential Revision: https://reviews.llvm.org/D61056

llvm-svn: 359288

4 files changed, 209 insertions, 183 deletions

diff --git a/lldb/include/lldb/Symbol/PostfixExpression.h b/lldb/include/lldb/Symbol/PostfixExpression.h
index d060436c193..a5c2fc57366 100644
--- a/lldb/include/lldb/Symbol/PostfixExpression.h
+++ b/lldb/include/lldb/Symbol/PostfixExpression.h
@@ -19,6 +19,9 @@
 #include "llvm/Support/Casting.h"
 
 namespace lldb_private {
+
+class Stream;
+
 namespace postfix {
 
 /// The base class for all nodes in the parsed postfix tree.
@@ -174,6 +177,17 @@ protected:
   }
 };
 
+/// A utility function for "resolving" SymbolNodes. It traverses a tree and
+/// calls the callback function for all SymbolNodes it encountered. The
+/// replacement function should return the node it wished to replace the current
+/// SymbolNode with (this can also be the original node), or nullptr in case of
+/// an error. The nodes returned by the callback are inspected and replaced
+/// recursively, *except* for the case when the function returns the exact same
+/// node as the input one. It returns true if all SymbolNodes were replaced
+/// successfully.
+bool ResolveSymbols(Node *&node,
+                    llvm::function_ref<Node *(SymbolNode &symbol)> replacer);
+
 template <typename T, typename... Args>
 inline T *MakeNode(llvm::BumpPtrAllocator &alloc, Args &&... args) {
   static_assert(std::is_trivially_destructible<T>::value,
@@ -185,6 +199,10 @@ inline T *MakeNode(llvm::BumpPtrAllocator &alloc, Args &&... args) {
 /// provided allocator.
 Node *Parse(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc);
 
+/// Serialize the given expression tree as DWARF. The result is written into the
+/// given stream. The AST should not contain any SymbolNodes.
+void ToDWARF(Node &node, Stream &stream);
+
 } // namespace postfix
 } // namespace lldb_private
 
diff --git a/lldb/source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp b/lldb/source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp
index 785cfe82171..fcee7cd1f98 100644
--- a/lldb/source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp
+++ b/lldb/source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp
@@ -10,7 +10,6 @@
 #include "CodeViewRegisterMapping.h"
 
 #include "lldb/Core/StreamBuffer.h"
-#include "lldb/Core/dwarf.h"
 #include "lldb/Symbol/PostfixExpression.h"
 #include "lldb/Utility/LLDBAssert.h"
 #include "lldb/Utility/Stream.h"
@@ -24,83 +23,6 @@ using namespace lldb;
 using namespace lldb_private;
 using namespace lldb_private::postfix;
 
-namespace {
-
-class FPOProgramASTVisitorMergeDependent : public Visitor<> {
-public:
-  void Visit(BinaryOpNode &binary, Node *&) override {
-    Dispatch(binary.Left());
-    Dispatch(binary.Right());
-  }
-
-  void Visit(UnaryOpNode &unary, Node *&) override {
-    Dispatch(unary.Operand());
-  }
-
-  void Visit(RegisterNode &, Node *&) override {}
-  void Visit(IntegerNode &, Node *&) override {}
-  void Visit(SymbolNode &symbol, Node *&ref) override;
-
-  static void
-  Merge(const llvm::DenseMap<llvm::StringRef, Node *> &dependent_programs,
-        Node *&ast) {
-    FPOProgramASTVisitorMergeDependent(dependent_programs).Dispatch(ast);
-  }
-
-private:
-  FPOProgramASTVisitorMergeDependent(
-      const llvm::DenseMap<llvm::StringRef, Node *> &dependent_programs)
-      : m_dependent_programs(dependent_programs) {}
-
-  const llvm::DenseMap<llvm::StringRef, Node *> &m_dependent_programs;
-};
-
-void FPOProgramASTVisitorMergeDependent::Visit(SymbolNode &symbol, Node *&ref) {
-  auto it = m_dependent_programs.find(symbol.GetName());
-  if (it == m_dependent_programs.end())
-    return;
-
-  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, 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, 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;
-  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 =
@@ -118,102 +40,6 @@ static uint32_t ResolveLLDBRegisterNum(llvm::StringRef reg_name, llvm::Triple::A
   return npdb::GetLLDBRegisterNumber(arch_type, reg_id);
 }
 
-bool FPOProgramASTVisitorResolveRegisterRefs::Visit(SymbolNode &symbol,
-                                                    Node *&ref) {
-  // Look up register reference as lvalue in preceding assignments.
-  auto it = m_dependent_programs.find(symbol.GetName());
-  if (it != m_dependent_programs.end()) {
-    // Dependent programs are handled elsewhere.
-    return true;
-  }
-
-  uint32_t reg_num =
-      ResolveLLDBRegisterNum(symbol.GetName().drop_front(1), m_arch_type);
-
-  if (reg_num == LLDB_INVALID_REGNUM)
-    return false;
-
-  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);
-  }
-
-  void Visit(RegisterNode &reg, Node *&);
-  void Visit(BinaryOpNode &binary, Node *&);
-  void Visit(UnaryOpNode &unary, Node *&);
-  void Visit(SymbolNode &symbol, Node *&) {
-    llvm_unreachable("Symbols should have been resolved by now!");
-  }
-  void Visit(IntegerNode &integer, Node *&);
-
-private:
-  FPOProgramASTVisitorDWARFCodegen(Stream &stream) : m_out_stream(stream) {}
-
-  Stream &m_out_stream;
-};
-
-void FPOProgramASTVisitorDWARFCodegen::Visit(RegisterNode &reg, Node *&) {
-  uint32_t reg_num = reg.GetRegNum();
-  lldbassert(reg_num != LLDB_INVALID_REGNUM);
-
-  if (reg_num > 31) {
-    m_out_stream.PutHex8(DW_OP_bregx);
-    m_out_stream.PutULEB128(reg_num);
-  } else
-    m_out_stream.PutHex8(DW_OP_breg0 + reg_num);
-
-  m_out_stream.PutSLEB128(0);
-}
-
-void FPOProgramASTVisitorDWARFCodegen::Visit(IntegerNode &integer, Node *&) {
-  uint32_t value = integer.GetValue();
-  m_out_stream.PutHex8(DW_OP_constu);
-  m_out_stream.PutULEB128(value);
-}
-
-void FPOProgramASTVisitorDWARFCodegen::Visit(BinaryOpNode &binary, Node *&) {
-  Dispatch(binary.Left());
-  Dispatch(binary.Right());
-
-  switch (binary.GetOpType()) {
-  case BinaryOpNode::Plus:
-    m_out_stream.PutHex8(DW_OP_plus);
-    // NOTE: can be optimized by using DW_OP_plus_uconst opcpode
-    //       if right child node is constant value
-    break;
-  case BinaryOpNode::Minus:
-    m_out_stream.PutHex8(DW_OP_minus);
-    break;
-  case BinaryOpNode::Align:
-    // emit align operator a @ b as
-    // a & ~(b - 1)
-    // NOTE: implicitly assuming that b is power of 2
-    m_out_stream.PutHex8(DW_OP_lit1);
-    m_out_stream.PutHex8(DW_OP_minus);
-    m_out_stream.PutHex8(DW_OP_not);
-
-    m_out_stream.PutHex8(DW_OP_and);
-    break;
-  }
-}
-
-void FPOProgramASTVisitorDWARFCodegen::Visit(UnaryOpNode &unary, Node *&) {
-  Dispatch(unary.Operand());
-
-  switch (unary.GetOpType()) {
-  case UnaryOpNode::Deref:
-    m_out_stream.PutHex8(DW_OP_deref);
-    break;
-  }
-}
-
-} // namespace
-
 static bool ParseFPOSingleAssignmentProgram(llvm::StringRef program,
                                             llvm::BumpPtrAllocator &alloc,
                                             llvm::StringRef &register_name,
@@ -256,18 +82,25 @@ static Node *ParseFPOProgram(llvm::StringRef program,
 
     lldbassert(rvalue_ast);
 
-    // check & resolve assignment program
-    if (!FPOProgramASTVisitorResolveRegisterRefs::Resolve(
-            dependent_programs, arch_type, alloc, rvalue_ast))
+    // Emplace valid dependent subtrees to make target assignment independent
+    // from predecessors. Resolve all other SymbolNodes as registers.
+    bool success =
+        ResolveSymbols(rvalue_ast, [&](SymbolNode &symbol) -> Node * {
+          if (Node *node = dependent_programs.lookup(symbol.GetName()))
+            return node;
+          uint32_t reg_num =
+              ResolveLLDBRegisterNum(symbol.GetName().drop_front(1), arch_type);
+
+          if (reg_num == LLDB_INVALID_REGNUM)
+            return nullptr;
+
+          return MakeNode<RegisterNode>(alloc, reg_num);
+        });
+    if (!success)
       return nullptr;
 
     if (lvalue_name == register_name) {
       // found target assignment program - no need to parse further
-
-      // emplace valid dependent subtrees to make target assignment independent
-      // from predecessors
-      FPOProgramASTVisitorMergeDependent::Merge(dependent_programs, rvalue_ast);
-
       return rvalue_ast;
     }
 
@@ -288,6 +121,6 @@ bool lldb_private::npdb::TranslateFPOProgramToDWARFExpression(
     return false;
   }
 
-  FPOProgramASTVisitorDWARFCodegen::Emit(stream, target_program);
+  ToDWARF(*target_program, stream);
   return true;
 }
diff --git a/lldb/source/Symbol/PostfixExpression.cpp b/lldb/source/Symbol/PostfixExpression.cpp
index 627c17b47fc..8be242a850f 100644
--- a/lldb/source/Symbol/PostfixExpression.cpp
+++ b/lldb/source/Symbol/PostfixExpression.cpp
@@ -12,6 +12,8 @@
 //===----------------------------------------------------------------------===//
 
 #include "lldb/Symbol/PostfixExpression.h"
+#include "lldb/Core/dwarf.h"
+#include "lldb/Utility/Stream.h"
 #include "llvm/ADT/StringExtras.h"
 
 using namespace lldb_private;
@@ -80,3 +82,121 @@ Node *postfix::Parse(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc) {
 
   return stack.back();
 }
+
+namespace {
+class SymbolResolver : public Visitor<bool> {
+public:
+  SymbolResolver(llvm::function_ref<Node *(SymbolNode &symbol)> replacer)
+      : m_replacer(replacer) {}
+
+  using Visitor<bool>::Dispatch;
+
+private:
+  bool Visit(BinaryOpNode &binary, Node *&) override {
+    return Dispatch(binary.Left()) && Dispatch(binary.Right());
+  }
+
+  bool Visit(IntegerNode &integer, Node *&) override { return true; }
+  bool Visit(RegisterNode &reg, Node *&) override { return true; }
+
+  bool Visit(SymbolNode &symbol, Node *&ref) override {
+    if (Node *replacement = m_replacer(symbol)) {
+      ref = replacement;
+      if (replacement != &symbol)
+        return Dispatch(ref);
+      return true;
+    }
+    return false;
+  }
+
+  bool Visit(UnaryOpNode &unary, Node *&) override {
+    return Dispatch(unary.Operand());
+  }
+
+  llvm::function_ref<Node *(SymbolNode &symbol)> m_replacer;
+};
+
+class DWARFCodegen : public Visitor<> {
+public:
+  DWARFCodegen(Stream &stream) : m_out_stream(stream) {}
+
+  using Visitor<>::Dispatch;
+
+private:
+  void Visit(BinaryOpNode &binary, Node *&);
+
+  void Visit(IntegerNode &integer, Node *&) {
+    m_out_stream.PutHex8(DW_OP_constu);
+    m_out_stream.PutULEB128(integer.GetValue());
+  }
+
+  void Visit(RegisterNode &reg, Node *&);
+
+  void Visit(SymbolNode &symbol, Node *&) {
+    llvm_unreachable("Symbols should have been resolved by now!");
+  }
+
+  void Visit(UnaryOpNode &unary, Node *&);
+
+  Stream &m_out_stream;
+};
+} // namespace
+
+void DWARFCodegen::Visit(BinaryOpNode &binary, Node *&) {
+  Dispatch(binary.Left());
+  Dispatch(binary.Right());
+
+  switch (binary.GetOpType()) {
+  case BinaryOpNode::Plus:
+    m_out_stream.PutHex8(DW_OP_plus);
+    // NOTE: can be optimized by using DW_OP_plus_uconst opcpode
+    //       if right child node is constant value
+    break;
+  case BinaryOpNode::Minus:
+    m_out_stream.PutHex8(DW_OP_minus);
+    break;
+  case BinaryOpNode::Align:
+    // emit align operator a @ b as
+    // a & ~(b - 1)
+    // NOTE: implicitly assuming that b is power of 2
+    m_out_stream.PutHex8(DW_OP_lit1);
+    m_out_stream.PutHex8(DW_OP_minus);
+    m_out_stream.PutHex8(DW_OP_not);
+
+    m_out_stream.PutHex8(DW_OP_and);
+    break;
+  }
+}
+
+void DWARFCodegen::Visit(RegisterNode &reg, Node *&) {
+  uint32_t reg_num = reg.GetRegNum();
+  assert(reg_num != LLDB_INVALID_REGNUM);
+
+  if (reg_num > 31) {
+    m_out_stream.PutHex8(DW_OP_bregx);
+    m_out_stream.PutULEB128(reg_num);
+  } else
+    m_out_stream.PutHex8(DW_OP_breg0 + reg_num);
+
+  m_out_stream.PutSLEB128(0);
+}
+
+void DWARFCodegen::Visit(UnaryOpNode &unary, Node *&) {
+  Dispatch(unary.Operand());
+
+  switch (unary.GetOpType()) {
+  case UnaryOpNode::Deref:
+    m_out_stream.PutHex8(DW_OP_deref);
+    break;
+  }
+}
+
+bool postfix::ResolveSymbols(
+    Node *&node, llvm::function_ref<Node *(SymbolNode &)> replacer) {
+  return SymbolResolver(replacer).Dispatch(node);
+}
+
+void postfix::ToDWARF(Node &node, Stream &stream) {
+  Node *ptr = &node;
+  DWARFCodegen(stream).Dispatch(ptr);
+}
diff --git a/lldb/unittests/Symbol/PostfixExpressionTest.cpp b/lldb/unittests/Symbol/PostfixExpressionTest.cpp
index 87cce32fc45..f919a944b0e 100644
--- a/lldb/unittests/Symbol/PostfixExpressionTest.cpp
+++ b/lldb/unittests/Symbol/PostfixExpressionTest.cpp
@@ -7,6 +7,9 @@
 //===----------------------------------------------------------------------===//
 
 #include "lldb/Symbol/PostfixExpression.h"
+#include "lldb/Expression/DWARFExpression.h"
+#include "lldb/Utility/DataExtractor.h"
+#include "lldb/Utility/StreamString.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/raw_ostream.h"
 #include "gtest/gtest.h"
@@ -95,3 +98,55 @@ TEST(PostfixExpression, Parse) {
   EXPECT_EQ("nullptr", ParseAndStringify("1 2"));
   EXPECT_EQ("nullptr", ParseAndStringify(""));
 }
+
+static std::string ParseAndGenerateDWARF(llvm::StringRef expr) {
+  llvm::BumpPtrAllocator alloc;
+  Node *ast = Parse(expr, alloc);
+  if (!ast)
+    return "Parse failed.";
+  if (!ResolveSymbols(ast, [&](SymbolNode &symbol) -> Node * {
+        uint32_t num;
+        if (to_integer(symbol.GetName().drop_front(), num))
+          return MakeNode<RegisterNode>(alloc, num);
+        return nullptr;
+      })) {
+    return "Resolution failed.";
+  }
+
+  const size_t addr_size = 4;
+  StreamString dwarf(Stream::eBinary, addr_size, lldb::eByteOrderLittle);
+  ToDWARF(*ast, dwarf);
+
+  // print dwarf expression to comparable textual representation
+  DataExtractor extractor(dwarf.GetData(), dwarf.GetSize(),
+                          lldb::eByteOrderLittle, addr_size);
+
+  StreamString result;
+  if (!DWARFExpression::PrintDWARFExpression(result, extractor, addr_size,
+                                             /*dwarf_ref_size*/ 4,
+                                             /*location_expression*/ false)) {
+    return "DWARF printing failed.";
+  }
+
+  return result.GetString();
+}
+
+TEST(PostfixExpression, ToDWARF) {
+  EXPECT_EQ("DW_OP_constu 0x0", ParseAndGenerateDWARF("0"));
+
+  EXPECT_EQ("DW_OP_breg1 +0", ParseAndGenerateDWARF("R1"));
+
+  EXPECT_EQ("DW_OP_bregx 65 0", ParseAndGenerateDWARF("R65"));
+
+  EXPECT_EQ("DW_OP_constu 0x4, DW_OP_constu 0x5, DW_OP_plus ",
+            ParseAndGenerateDWARF("4 5 +"));
+
+  EXPECT_EQ("DW_OP_constu 0x4, DW_OP_constu 0x5, DW_OP_minus ",
+            ParseAndGenerateDWARF("4 5 -"));
+
+  EXPECT_EQ("DW_OP_constu 0x4, DW_OP_deref ", ParseAndGenerateDWARF("4 ^"));
+
+  EXPECT_EQ("DW_OP_breg6 +0, DW_OP_constu 0x80, DW_OP_lit1 "
+            ", DW_OP_minus , DW_OP_not , DW_OP_and ",
+            ParseAndGenerateDWARF("R6 128 @"));
+}