[pseudo] Fix bugs/inconsistencies in forest dump.

[sammccall]

Summary

• when printing a shared node for the second time, don't print its children (This keeps output proportional to the size of the structure)
• when printing a shared node for the second time, print its type only, not rule (for consistency with above: don't dump details of nodes twice)
• don't abbreviate shared nodes, to ensure we can prune the tree there

[hokein]

clang-tools-extra/pseudo/unittests/ForestTest.cpp

138

I was confused by the forest here -- the fact that it doesn't reflect the grammar (I was trying to figure out why there is an ambiguous node for A by reading the grammar above)

I think there should be a comment clarifying the gap between the grammar and forest -- this is an artificial forest which is only for testing the dump purpose -- we only need the symbol bits from the grammar (I actual think GLRTest::buildGrammar is a better fit for the tests in this file).

[sammccall]

clang-tools-extra/pseudo/unittests/ForestTest.cpp

138

This forest does matches the grammar, unless I'm missing something.
It has imperfect sharing (two nodes with the same rule+range), but strictly it's our GLR parser that guarantees perfect sharing, not the forest itself.

Added a comment.

clang-tools-extra/pseudo/lib/Forest.cpp

std::string ForestNode::dumpRecursive(const Grammar &G,
   llvm::DenseMap<const ForestNode *, size_t> ReferenceIds;
   std::string Result;
   constexpr Token::Index KEnd = std::numeric_limits<Token::Index>::max();
   std::function<void(const ForestNode *, Token::Index, llvm::Optional<SymbolID>,
                      LineDecoration &LineDec)>
       Dump = [&](const ForestNode *P, Token::Index End,
                  llvm::Optional<SymbolID> ElidedParent,
                  LineDecoration LineDec) {
+        bool SharedNode = VisitCounts.find(P)->getSecond() > 1;
         llvm::ArrayRef<const ForestNode *> Children;
         auto EndOfElement = [&](size_t ChildIndex) {
           return ChildIndex + 1 == Children.size()
                      ? End
                      : Children[ChildIndex + 1]->startTokenIndex();
         };
         if (P->kind() == Ambiguous) {
           Children = P->alternatives();
         } else if (P->kind() == Sequence) {
           Children = P->elements();
           if (Abbreviated) {
-            if (Children.size() == 1) {
+            // Abbreviate chains of trivial sequence nodes.
+            //    A := B, B := C, C := D, D := X Y Z
+            // becomes
+            //    A~D := X Y Z
+            //
+            // We can't hide nodes that appear multiple times in the tree,
+            // because we need to call out their identity with IDs.
+            if (Children.size() == 1 && !SharedNode) {
               assert(Children[0]->startTokenIndex() == P->startTokenIndex() &&
                      EndOfElement(0) == End);
               return Dump(Children[0], End,
                           /*ElidedParent=*/ElidedParent.value_or(P->symbol()),
                           LineDec);
             }
           }
         }
 
         if (End == KEnd)
           Result += llvm::formatv("[{0,3}, end) ", P->startTokenIndex());
         else
           Result += llvm::formatv("[{0,3}, {1,3}) ", P->startTokenIndex(), End);
         Result += LineDec.Prefix;
         Result += LineDec.First;
         if (ElidedParent) {
           Result += G.symbolName(*ElidedParent);
           Result += "~";
         }
-        Result.append(P->dump(G));
 
-        if (VisitCounts.find(P)->getSecond() > 1 &&
-            P->kind() != ForestNode::Terminal) {
-          // The first time, print as #1. Later, =#1.
+        if (SharedNode && P->kind() != ForestNode::Terminal) {
           auto It = ReferenceIds.try_emplace(P, ReferenceIds.size() + 1);
-          Result +=
-              llvm::formatv(" {0}#{1}", It.second ? "" : "=", It.first->second);
+          bool First = It.second;
+          unsigned ID = It.first->second;
+
+          // The first time, print as #1. Later, =#1.
+          if (First) {
+            Result += llvm::formatv("{0} #{1}", P->dump(G), ID);
+          } else {
+            Result += llvm::formatv("{0} =#{1}", G.symbolName(P->symbol()), ID);
+            Children = {}; // Don't walk the children again.
+          }
+        } else {
+          Result.append(P->dump(G));
         }
         Result.push_back('\n');
 
         auto OldPrefixSize = LineDec.Prefix.size();
         LineDec.Prefix += LineDec.Subsequent;
         for (size_t I = 0; I < Children.size(); ++I) {
           if (I == Children.size() - 1) {
             LineDec.First = "└─";

clang-tools-extra/pseudo/test/glr.cpp

 // RUN: clang-pseudo -grammar=%cxx-bnf-file -source=%s --print-forest | FileCheck %s
 
 void foo() {
   T* a; // a multiply expression or a pointer declaration?
 // CHECK:      statement-seq~statement := <ambiguous>
 // CHECK-NEXT: ├─statement~expression-statement := expression ;
 // CHECK-NEXT: │ ├─expression~multiplicative-expression := multiplicative-expression * pm-expression
 // CHECK-NEXT: │ │ ├─multiplicative-expression~IDENTIFIER := tok[5]
 // CHECK-NEXT: │ │ ├─* := tok[6]
-// CHECK-NEXT: │ │ └─pm-expression~IDENTIFIER := tok[7]
+// CHECK-NEXT: │ │ └─pm-expression~id-expression := unqualified-id #1
+// CHECK-NEXT: │ │   └─unqualified-id~IDENTIFIER := tok[7]
 // CHECK-NEXT: │ └─; := tok[8]
 // CHECK-NEXT: └─statement~simple-declaration := decl-specifier-seq init-declarator-list ;
 // CHECK-NEXT:   ├─decl-specifier-seq~simple-type-specifier := <ambiguous>
 // CHECK-NEXT:   │ ├─simple-type-specifier~type-name := <ambiguous>
 // CHECK-NEXT:   │ │ ├─type-name~IDENTIFIER := tok[5]
 // CHECK-NEXT:   │ │ ├─type-name~IDENTIFIER := tok[5]
 // CHECK-NEXT:   │ │ └─type-name~IDENTIFIER := tok[5]
 // CHECK-NEXT:   │ └─simple-type-specifier~IDENTIFIER := tok[5]
 // CHECK-NEXT:   ├─init-declarator-list~ptr-declarator := ptr-operator ptr-declarator
 // CHECK-NEXT:   │ ├─ptr-operator~* := tok[6]
-// CHECK-NEXT:   │ └─ptr-declarator~IDENTIFIER := tok[7]
+// CHECK-NEXT:   │ └─ptr-declarator~id-expression =#1
 // CHECK-NEXT:   └─; := tok[8]
 }

clang-tools-extra/pseudo/unittests/ForestTest.cpp

TEST_F(ForestTest, DumpAmbiguousAndRefs) {
   EXPECT_EQ(Type->dumpRecursive(G),
             "[  0, end) type := <ambiguous>\n"
             "[  0, end) ├─type := class-type\n"
             "[  0, end) │ └─class-type := shared-type\n"
             "[  0, end) │   └─shared-type := IDENTIFIER #1\n"
             "[  0, end) │     └─IDENTIFIER := tok[0]\n"
             "[  0, end) └─type := enum-type\n"
             "[  0, end)   └─enum-type := shared-type\n"
-            "[  0, end)     └─shared-type := IDENTIFIER =#1\n"
-            "[  0, end)       └─IDENTIFIER := tok[0]\n");
+            "[  0, end)     └─shared-type =#1\n");
+}
+
+TEST_F(ForestTest, DumpAbbreviatedShared) {
+  build(R"cpp(
+    _ := A
+    A := B
+    B := *
+  )cpp");
+
+  ForestArena Arena;
+  const auto *Star = &Arena.createTerminal(tok::star, 0);
+
+  const auto *B = &Arena.createSequence(symbol("B"), ruleFor("B"), {Star});
+  // We have two identical (but distinct) A nodes.
+  // The GLR parser would never produce this, but it makes the example simpler.
+  const auto *A1 = &Arena.createSequence(symbol("A"), ruleFor("A"), {B});
+  const auto *A2 = &Arena.createSequence(symbol("A"), ruleFor("A"), {B});
+  const auto *A = &Arena.createAmbiguous(symbol("A"), {A1, A2});
+
+  // We must not abbreviate away shared nodes: if we show A~* there's no way to
+  // show that the intermediate B node is shared between A1 and A2.
+  EXPECT_EQ(A->dumpRecursive(G, /*Abbreviate=*/true),
+            "[  0, end) A := <ambiguous>\n"
+            "[  0, end) ├─A~B := * #1\n"
+            "[  0, end) │ └─* := tok[0]\n"
+            "[  0, end) └─A~B =#1\n");
 }
 
 } // namespace
 } // namespace pseudo
 } // namespace clang

clang-tools-extra/pseudo/unittests/GLRTest.cpp

EXPECT_EQ(Parsed.dumpRecursive(G), "[  0, end) test := <ambiguous>\n"
                                      "[  1, end) │ └─expr := IDENTIFIER #1\n"
                                      "[  1, end) │   └─IDENTIFIER := tok[1]\n"
                                      "[  0, end) ├─test := { IDENTIFIER\n"
                                      "[  0,   1) │ ├─{ := tok[0]\n"
                                      "[  1, end) │ └─IDENTIFIER := tok[1]\n"
                                      "[  0, end) └─test := left-paren expr\n"
                                      "[  0,   1)   ├─left-paren := {\n"
                                      "[  0,   1)   │ └─{ := tok[0]\n"
-                                     "[  1, end)   └─expr := IDENTIFIER =#1\n"
-                                     "[  1, end)     └─IDENTIFIER := tok[1]\n");
+                                     "[  1, end)   └─expr =#1\n");
 }
 
 TEST_F(GLRTest, GLRReduceOrder) {
   // Given the following grammar, and the input `IDENTIFIER`, reductions should
   // be performed in the following order:
   //  1. foo := IDENTIFIER
   //  2. { test := IDENTIFIER, test := foo }
   // foo should be reduced first, so that in step 2 we have completed reduces