Postfix: move more code out of the PDB plugin

[labath]

Summary

Previously we moved the code which parses a single expression out of the PDB
plugin, because that was useful for DWARF expressions in breakpad. However, FPO
programs are used in breakpad files too (when unwinding on windows), so this
completes the job, and moves the rest of the FPO parser too.

[aleksandr.urakov]

LGTM, thanks!

source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp

58

Do I understand right, you use a vector of pairs instead of a map due to the small number of expressions in a program (then a search on a small vector will be faster than on a map)?

[amccarth]

I have a couple inline questions. After that, it looks fine.

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

61 ↗

(On Diff #217116)

I would recommend making parsed a const vector. The lambda captures the iterator, and while the code currently looks fine, I'd hate for something to change in the future that could invalidate the captured iterator.

69 ↗

(On Diff #217116)

This looks O(n^2). Will that matter here or will the expressions always be short?

84 ↗

(On Diff #217116)

It's a shame the pair loses the more descriptive field names, but I don't see a good way to make it better, so this is a useless comment.

lldb/trunk/source/Symbol/PostfixExpression.cpp

101 ↗

(On Diff #217116)

Is it correct to return an empty vector here rather than result? If there's one bad expression, you'll consider the entire FPO program empty. That's sounds plausible, but I thought I'd ask.

[labath]

Please find my replies inline (including my yesterday's reply to Aleksandr, which I apparently failed to submit).

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

61 ↗

(On Diff #217116)

Making it const won't work because the symbol resolution process can actually modify the contents (not the size) of the vector -- if the RHS is a SymbolNode * directly, then we may need to replace that with a different kind of a node.

I don't think that the invalidation problem is really specific to the lambda -- even without the lambda, if anything modified the vector size while we were iterating over it, we would blow up.

69 ↗

(On Diff #217116)

I don't think that should matter, the expressions will typically have three of four assignments (frame base, aligned frame base, esp, eip). It may have additional entries for spilled registers, but there aren't that many of those either.

lldb/trunk/source/Symbol/PostfixExpression.cpp

101 ↗

(On Diff #217116)

Yeah, that was intentional here. If there's an error parsing one of the expressions, I am not sure we want to trust the parse of the preceding partial results either. I wouldn't really use the term "correct" here, because normally we should never fail to parse the expression, and the failure would either mean a bug in the parser, or the producer. And it's hard to say what is the "correct" thing to do in those cases without knowing the specifics...

source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp

58

Not exactly. The main reason for using a vector is that the order of expressions (according to my understanding) in these expressions is important. So a b = b c = would mean something different than b c = a b =. And once I already have them in a vector, I didn't see a point in putting them also into a map to get fast lookups (because the number of elements is small).

The previous implementation avoided that by parsing and resolving in the same loop, but here I first parse and then resolve stuff. This made it easier to implement, and I doubt the performance loss is noticeable due to the size of the data involved.

[amccarth]

When I added my comments, Phabricator showed this patch as still open. Now it looks like it landed four hours before that. :-(

[labath]

In D66634#1648119, @amccarth wrote:

When I added my comments, Phabricator showed this patch as still open. Now it looks like it landed four hours before that. :-(

Yeah, :(, but that doesn't mean I can't address any comments in a follow-up. If you have any additional feedback, or thoughts on my previous comments, let me know.

include/lldb/Symbol/PostfixExpression.h

 //===----------------------------------------------------------------------===//
 
 #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"
+#include <vector>
 
 namespace lldb_private {
 
 class Stream;
 
 namespace postfix {
 
 /// The base class for all nodes in the parsed postfix tree.

 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);
+Node *ParseOneExpression(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc);
+
+std::vector<std::pair<llvm::StringRef, Node *>>
+ParseFPOProgram(llvm::StringRef prog, 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. If the expression
 /// contains InitialValueNodes, the generated expression will assume that their
 /// value will be provided as the top value of the initial evaluation stack (as
 /// is the case with the CFA value in register eh_unwind rules).
 void ToDWARF(Node &node, Stream &stream);
 
 } // namespace postfix
 } // namespace lldb_private
 
 #endif // LLDB_SYMBOL_POSTFIXEXPRESSION_H

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

bool SymbolFileBreakpad::ParseUnwindRow(llvm::StringRef unwind_rules,
                                         const RegisterInfoResolver &resolver,
                                         UnwindPlan::Row &row) {
   Log *log = GetLogIfAllCategoriesSet(LIBLLDB_LOG_SYMBOLS);
 
   llvm::BumpPtrAllocator node_alloc;
   while (auto rule = GetRule(unwind_rules)) {
     node_alloc.Reset();
     llvm::StringRef lhs = rule->first;
-    postfix::Node *rhs = postfix::Parse(rule->second, node_alloc);
+    postfix::Node *rhs = postfix::ParseOneExpression(rule->second, node_alloc);
     if (!rhs) {
       LLDB_LOG(log, "Could not parse `{0}` as unwind rhs.", rule->second);
       return false;
     }
 
     bool success = postfix::ResolveSymbols(
         rhs, [&](postfix::SymbolNode &symbol) -> postfix::Node * {
           llvm::StringRef name = symbol.GetName();

source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp

static uint32_t ResolveLLDBRegisterNum(llvm::StringRef reg_name, llvm::Triple::ArchType arch_type) {
 
   if (it == register_names.end())
     return LLDB_INVALID_REGNUM;
 
   auto reg_id = static_cast<llvm::codeview::RegisterId>(it->Value);
   return npdb::GetLLDBRegisterNumber(arch_type, reg_id);
 }
 
-static bool ParseFPOSingleAssignmentProgram(llvm::StringRef program,
-                                            llvm::BumpPtrAllocator &alloc,
-                                            llvm::StringRef &register_name,
-                                            Node *&ast) {
-  // lvalue of assignment is always first token
-  // rvalue program goes next
-  std::tie(register_name, program) = getToken(program);
-  if (register_name.empty())
-    return false;
-
-  ast = Parse(program, alloc);
-  return ast != nullptr;
-}
-
-static Node *ParseFPOProgram(llvm::StringRef program,
+static Node *ResolveFPOProgram(llvm::StringRef program,
                              llvm::StringRef register_name,
                              llvm::Triple::ArchType arch_type,
                              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()) {
-        // missing assign operator
-        return nullptr;
-      }
-      break;
-    }
-    llvm::StringRef assignment_program = program.slice(cur, assign_index);
-
-    llvm::StringRef lvalue_name;
-    Node *rvalue_ast = nullptr;
-    if (!ParseFPOSingleAssignmentProgram(assignment_program, alloc, lvalue_name,
-                                         rvalue_ast)) {
-      return nullptr;
-    }
-
-    lldbassert(rvalue_ast);
+  std::vector<std::pair<llvm::StringRef, Node *>> parsed =
+      postfix::ParseFPOProgram(program, alloc);
 
+  for (auto it = parsed.begin(), end = parsed.end(); it != end; ++it) {
     // 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;
+        ResolveSymbols(it->second, [&](SymbolNode &symbol) -> Node * {
+          for (const auto &pair : llvm::make_range(parsed.begin(), it)) {
+            if (pair.first == symbol.GetName())
+              return pair.second;
+          }
+
           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) {
+    if (it->first == register_name) {
       // found target assignment program - no need to parse further
-      return rvalue_ast;
+      return it->second;
     }
-
-    dependent_programs[lvalue_name] = rvalue_ast;
-    cur = assign_index + 1;
   }
 
   return nullptr;
 }
 
 bool lldb_private::npdb::TranslateFPOProgramToDWARFExpression(
     llvm::StringRef program, llvm::StringRef register_name,
     llvm::Triple::ArchType arch_type, Stream &stream) {
   llvm::BumpPtrAllocator node_alloc;
   Node *target_program =
-      ParseFPOProgram(program, register_name, arch_type, node_alloc);
+      ResolveFPOProgram(program, register_name, arch_type, node_alloc);
   if (target_program == nullptr) {
     return false;
   }
 
   ToDWARF(*target_program, stream);
   return true;
 }

source/Symbol/PostfixExpression.cpp

 
 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) {
+Node *postfix::ParseOneExpression(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 *postfix::ParseOneExpression(llvm::StringRef expr,
   }
 
   if (stack.size() != 1)
     return nullptr;
 
   return stack.back();
 }
 
+std::vector<std::pair<llvm::StringRef, Node *>>
+postfix::ParseFPOProgram(llvm::StringRef prog, llvm::BumpPtrAllocator &alloc) {
+  llvm::SmallVector<llvm::StringRef, 4> exprs;
+  prog.split(exprs, '=');
+  if (exprs.empty() || !exprs.back().trim().empty())
+    return {};
+  exprs.pop_back();
+
+  std::vector<std::pair<llvm::StringRef, Node *>> result;
+  for (llvm::StringRef expr : exprs) {
+    llvm::StringRef lhs;
+    std::tie(lhs, expr) = getToken(expr);
+    Node *rhs = ParseOneExpression(expr, alloc);
+    if (!rhs)
+      return {};
+    result.emplace_back(lhs, rhs);
+  }
+  return result;
+}
+
 namespace {
 class SymbolResolver : public Visitor<bool> {
 public:
   SymbolResolver(llvm::function_ref<Node *(SymbolNode &symbol)> replacer)
       : m_replacer(replacer) {}
 
   using Visitor<bool>::Dispatch;
 

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 "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 "gmock/gmock.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:

 public:
   static std::string Print(Node *node) {
     if (node)
       return ASTPrinter().Dispatch(node);
     return "nullptr";
   }
 };
 
-static std::string ParseAndStringify(llvm::StringRef expr) {
+static std::string ParseOneAndStringify(llvm::StringRef expr) {
   llvm::BumpPtrAllocator alloc;
-  return ASTPrinter::Print(Parse(expr, alloc));
+  return ASTPrinter::Print(ParseOneExpression(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("+(int(47), int(-42))", ParseAndStringify("47 -42 +"));
-
-  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(""));
+TEST(PostfixExpression, ParseOneExpression) {
+  EXPECT_EQ("int(47)", ParseOneAndStringify("47"));
+  EXPECT_EQ("$foo", ParseOneAndStringify("$foo"));
+  EXPECT_EQ("+(int(1), int(2))", ParseOneAndStringify("1 2 +"));
+  EXPECT_EQ("-(int(1), int(2))", ParseOneAndStringify("1 2 -"));
+  EXPECT_EQ("@(int(1), int(2))", ParseOneAndStringify("1 2 @"));
+  EXPECT_EQ("+(int(1), +(int(2), int(3)))", ParseOneAndStringify("1 2 3 + +"));
+  EXPECT_EQ("+(+(int(1), int(2)), int(3))", ParseOneAndStringify("1 2 + 3 +"));
+  EXPECT_EQ("^(int(1))", ParseOneAndStringify("1 ^"));
+  EXPECT_EQ("^(^(int(1)))", ParseOneAndStringify("1 ^ ^"));
+  EXPECT_EQ("^(+(int(1), ^(int(2))))", ParseOneAndStringify("1 2 ^ + ^"));
+  EXPECT_EQ("-($foo, int(47))", ParseOneAndStringify("$foo 47 -"));
+  EXPECT_EQ("+(int(47), int(-42))", ParseOneAndStringify("47 -42 +"));
+
+  EXPECT_EQ("nullptr", ParseOneAndStringify("+"));
+  EXPECT_EQ("nullptr", ParseOneAndStringify("^"));
+  EXPECT_EQ("nullptr", ParseOneAndStringify("1 +"));
+  EXPECT_EQ("nullptr", ParseOneAndStringify("1 2 ^"));
+  EXPECT_EQ("nullptr", ParseOneAndStringify("1 2 3 +"));
+  EXPECT_EQ("nullptr", ParseOneAndStringify("^ 1"));
+  EXPECT_EQ("nullptr", ParseOneAndStringify("+ 1 2"));
+  EXPECT_EQ("nullptr", ParseOneAndStringify("1 + 2"));
+  EXPECT_EQ("nullptr", ParseOneAndStringify("1 2"));
+  EXPECT_EQ("nullptr", ParseOneAndStringify(""));
+}
+
+static std::vector<std::pair<std::string, std::string>>
+ParseFPOAndStringify(llvm::StringRef prog) {
+  llvm::BumpPtrAllocator alloc;
+  std::vector<std::pair<llvm::StringRef, Node *>> parsed =
+      ParseFPOProgram(prog, alloc);
+  auto range = llvm::map_range(
+      parsed, [](const std::pair<llvm::StringRef, Node *> &pair) {
+        return std::make_pair(pair.first, ASTPrinter::Print(pair.second));
+      });
+  return std::vector<std::pair<std::string, std::string>>(range.begin(),
+                                                          range.end());
+}
+
+TEST(PostfixExpression, ParseFPOProgram) {
+  EXPECT_THAT(ParseFPOAndStringify("a 1 ="),
+              testing::ElementsAre(std::make_pair("a", "int(1)")));
+  EXPECT_THAT(ParseFPOAndStringify("a 1 = b 2 3 + ="),
+              testing::ElementsAre(std::make_pair("a", "int(1)"),
+                                   std::make_pair("b", "+(int(2), int(3))")));
+
+  EXPECT_THAT(ParseFPOAndStringify(""), testing::IsEmpty());
+  EXPECT_THAT(ParseFPOAndStringify("="), testing::IsEmpty());
+  EXPECT_THAT(ParseFPOAndStringify("a 1"), testing::IsEmpty());
+  EXPECT_THAT(ParseFPOAndStringify("a 1 = ="), testing::IsEmpty());
+  EXPECT_THAT(ParseFPOAndStringify("a 1 + ="), testing::IsEmpty());
+  EXPECT_THAT(ParseFPOAndStringify("= a 1 ="), testing::IsEmpty());
 }
 
 static std::string ParseAndGenerateDWARF(llvm::StringRef expr) {
   llvm::BumpPtrAllocator alloc;
-  Node *ast = Parse(expr, alloc);
+  Node *ast = ParseOneExpression(expr, alloc);
   if (!ast)
     return "Parse failed.";
   if (!ResolveSymbols(ast, [&](SymbolNode &symbol) -> Node * {
         if (symbol.GetName() == "INIT")
           return MakeNode<InitialValueNode>(alloc);
 
         uint32_t num;
         if (to_integer(symbol.GetName().drop_front(), num))