[pseudo] Add ForestNode descendants iterator, print ambiguous/opaque node stats.

[sammccall]

Results on the first 1k lines of SemaCodeComplete.cpp:

Forest bytes: 809824 nodes: 47378
GSS bytes: 24736 nodes: 41925

1490 Ambiguous nodes:
  518 type-name
  377 simple-type-specifier
  137 namespace-name
  135 nested-name-specifier
   65 postfix-expression
   45 decl-specifier-seq
   40 template-argument
   37 parameter-declaration
   26 relational-expression
   25 member-declaration
   21 virt-specifier
   18 function-definition
   16 mem-initializer-id
    9 literal
    7 user-defined-literal
    4 condition
    2 declaration-seq
    2 logical-or-expression
    2 simple-declaration
    2 statement
    1 logical-and-expression
    1 type-specifier-seq

0 Opaque nodes:

[hokein]

Nice!

clang-tools-extra/pseudo/tool/ClangPseudo.cpp

68

I can foresee we will use it in other places (e.g. our internal metric tool), I think it is worth to expose it. It is ok for now.

70

By reading the code, I believe the unsigned and SymbolID here are swap accidentally.

[sammccall]

clang-tools-extra/pseudo/tool/ClangPseudo.cpp

68

I had the same thought, but I wasn't sure we'll want exactly the same thing.

e.g. the breakdown-by-SymbolID is a somewhat specialized data structure, our (private) mapreduce analysis might want to use mapreduce counters for this.

I'd rather just share the iterator for now, and only expose the simple aggregation stuff once we know it's actually reusable.

[tschuett]

clang-tools-extra/pseudo/include/clang-pseudo/Forest.h

202

std::iterator is deprecated in C++17 and creates warnings.

[hokein]

clang-tools-extra/pseudo/include/clang-pseudo/Forest.h

202

This seems to be fixed in d9e5462da61c3e2137a21a868a36f7022a39b59e.

clang-tools-extra/pseudo/include/clang-pseudo/Forest.h

 // depending on the node kinds. For an Ambiguous node, it means all
 // possible interpretations; for a Sequence node, it means each symbol on the
 // right hand side of the production rule.
 //
 // Since this is a node in a DAG, a node may have multiple parents. And a node
 // doesn't have parent pointers.
 class alignas(class ForestNode *) ForestNode {
 public:
+  class RecursiveIterator;
   enum Kind {
     // A Terminal node is a single terminal symbol bound to a token.
     Terminal,
     // A Sequence node is a nonterminal symbol parsed from a grammar rule,
     // elements() are the parses of each symbol on the RHS of the rule.
     // If the rule is A := X Y Z, the node is for nonterminal A, and elements()
     // are [X, Y, Z].
     Sequence,
public:
 
   // Returns all possible interpretations of the code.
   // REQUIRES: this is an Ambiguous node.
   llvm::ArrayRef<const ForestNode *> alternatives() const {
     assert(kind() == Ambiguous);
     return children(Data);
   }
 
+  llvm::ArrayRef<const ForestNode *> children() const {
+    switch (kind()) {
+    case Sequence:
+      return elements();
+    case Ambiguous:
+      return alternatives();
+    case Terminal:
+    case Opaque:
+      return {};
+    }
+    llvm_unreachable("Bad kind");
+  }
+
+  // Iteration over all nodes in the forest, including this.
+  llvm::iterator_range<RecursiveIterator> descendants() const;
+
   std::string dump(const Grammar &) const;
   std::string dumpRecursive(const Grammar &, bool Abbreviated = false) const;
 
 private:
   friend class ForestArena;
 
   ForestNode(Kind K, SymbolID Symbol, Token::Index StartIndex, uint16_t Data)
       : StartIndex(StartIndex), K(K), Symbol(Symbol), Data(Data) {}
if (!Elements.empty())
       llvm::copy(Elements, reinterpret_cast<const ForestNode **>(New + 1));
     return *New;
   }
 
   llvm::BumpPtrAllocator Arena;
   uint32_t NodeCount = 0;
 };
 
+class ForestNode::RecursiveIterator
+    : public std::iterator<std::input_iterator_tag, const ForestNode> {
+  llvm::DenseSet<const ForestNode *> Seen;
+  struct StackFrame {
+    const ForestNode *Parent;
+    unsigned ChildIndex;
+  };
+  std::vector<StackFrame> Stack;
+  const ForestNode *Cur;
+
+public:
+  RecursiveIterator(const ForestNode *N = nullptr) : Cur(N) {}
+
+  const ForestNode &operator*() const { return *Cur; };
+  void operator++();
+  bool operator==(const RecursiveIterator &I) const { return Cur == I.Cur; }
+  bool operator!=(const RecursiveIterator &I) const { return !(*this == I); }
+};
+
 } // namespace pseudo
 } // namespace clang
 
 #endif // CLANG_PSEUDO_FOREST_H

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

 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/FormatVariadic.h"
 
 namespace clang {
 namespace pseudo {
 
+void ForestNode::RecursiveIterator::operator++() {
+  auto C = Cur->children();
+  // Try to find a child of the current node to descend into.
+  for (unsigned I = 0; I < C.size(); ++I) {
+    if (Seen.insert(C[I]).second) {
+      Stack.push_back({Cur, I});
+      Cur = C[I];
+      return;
+    }
+  }
+  // Try to find a sibling af an ancestor to advance to.
+  for (; !Stack.empty(); Stack.pop_back()) {
+    C = Stack.back().Parent->children();
+    unsigned &Index = Stack.back().ChildIndex;
+    while (++Index < C.size()) {
+      if (Seen.insert(C[Index]).second) {
+        Cur = C[Index];
+        return;
+      }
+    }
+  }
+  Cur = nullptr;
+}
+
+llvm::iterator_range<ForestNode::RecursiveIterator>
+ForestNode::descendants() const {
+  return {RecursiveIterator(this), RecursiveIterator()};
+}
+
 std::string ForestNode::dump(const Grammar &G) const {
   switch (kind()) {
   case Ambiguous:
     return llvm::formatv("{0} := <ambiguous>", G.symbolName(symbol()));
   case Terminal:
     return llvm::formatv("{0} := tok[{1}]", G.symbolName(symbol()),
                          startTokenIndex());
   case Sequence:

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

-// RUN: clang-pseudo -grammar=%cxx-bnf-file -source=%s --print-forest | FileCheck %s
+// RUN: clang-pseudo -grammar=%cxx-bnf-file -source=%s --print-forest -print-statistics | 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~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~id-expression =#1
 // CHECK-NEXT:   └─; := tok[8]
 }
+
+// CHECK:      3 Ambiguous nodes:
+// CHECK-NEXT: 1 simple-type-specifier
+// CHECK-NEXT: 1 statement
+// CHECK-NEXT: 1 type-name
+// CHECK-EMPTY:
+// CHECK-NEXT: 0 Opaque nodes:

clang-tools-extra/pseudo/tool/ClangPseudo.cpp

 //===-- ClangPseudo.cpp - Clang pseudoparser tool -------------------------===//
 //
 // 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 "clang-pseudo/Bracket.h"
 #include "clang-pseudo/DirectiveTree.h"
 #include "clang-pseudo/GLR.h"
 #include "clang-pseudo/Token.h"
 #include "clang-pseudo/grammar/Grammar.h"
 #include "clang-pseudo/grammar/LRGraph.h"
 #include "clang-pseudo/grammar/LRTable.h"
 #include "clang/Basic/LangOptions.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/STLFunctionalExtras.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Signals.h"
 
 using clang::pseudo::Grammar;
 using clang::pseudo::TokenStream;
static std::string readOrDie(llvm::StringRef Path) {
   if (std::error_code EC = Text.getError()) {
     llvm::errs() << "Error: can't read grammar file '" << Path
                  << "': " << EC.message() << "\n";
     ::exit(1);
   }
   return Text.get()->getBuffer().str();
 }
 
+namespace clang {
+namespace pseudo {
+namespace {
+
+struct NodeStats {
+  unsigned Total = 0;
+  std::vector<std::pair<SymbolID, unsigned>> BySymbol;
+
+  NodeStats(const ForestNode &Root,
+            llvm::function_ref<bool(const ForestNode &)> Filter) {
+    llvm::DenseMap<SymbolID, unsigned> Map;
+    for (const ForestNode &N : Root.descendants())
+      if (Filter(N)) {
+        ++Total;
+        ++Map[N.symbol()];
+      }
+    BySymbol = {Map.begin(), Map.end()};
+    // Sort by count descending, then symbol ascending.
+    llvm::sort(BySymbol, [](const auto &L, const auto &R) {
+      return std::tie(R.second, L.first) < std::tie(L.second, R.first);
+    });
+  }
+};
+
+} // namespace
+} // namespace pseudo
+} // namespace clang
+
 int main(int argc, char *argv[]) {
   llvm::cl::ParseCommandLineOptions(argc, argv, "");
   llvm::sys::PrintStackTraceOnErrorSignal(argv[0]);
 
   clang::LangOptions LangOpts = clang::pseudo::genericLangOpts();
   std::string SourceText;
   llvm::Optional<clang::pseudo::TokenStream> RawStream;
   llvm::Optional<TokenStream> PreprocessedStream;
if (ParseableStream) {
       if (PrintForest)
         llvm::outs() << Root.dumpRecursive(G, /*Abbreviated=*/true);
 
       if (PrintStatistics) {
         llvm::outs() << "Forest bytes: " << Arena.bytes()
                      << " nodes: " << Arena.nodeCount() << "\n";
         llvm::outs() << "GSS bytes: " << GSS.bytes()
                      << " nodes: " << GSS.nodesCreated() << "\n";
+
+        for (auto &P :
+             {std::make_pair("Ambiguous", clang::pseudo::ForestNode::Ambiguous),
+              std::make_pair("Opaque", clang::pseudo::ForestNode::Opaque)}) {
+          clang::pseudo::NodeStats Stats(
+              Root, [&](const auto &N) { return N.kind() == P.second; });
+          llvm::outs() << "\n" << Stats.Total << " " << P.first << " nodes:\n";
+          for (const auto &S : Stats.BySymbol)
+            llvm::outs() << llvm::formatv("  {0,3} {1}\n", S.second,
+                                          G.symbolName(S.first));
+        }
       }
     }
   }
 
   return 0;
 }

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

TEST_F(ForestTest, DumpAbbreviatedShared) {
   // 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");
 }
 
+TEST_F(ForestTest, Iteration) {
+  //   Z
+  //  / \
+  //  X Y
+  //  |\|
+  //  A B
+  ForestArena Arena;
+  const auto *A = &Arena.createTerminal(tok::identifier, 0);
+  const auto *B = &Arena.createOpaque(1, 0);
+  const auto *X = &Arena.createSequence(2, 1, {A, B});
+  const auto *Y = &Arena.createSequence(2, 2, {B});
+  const auto *Z = &Arena.createAmbiguous(2, {X, Y});
+
+  std::vector<const ForestNode *> Nodes;
+  for (const ForestNode &N : Z->descendants())
+    Nodes.push_back(&N);
+  EXPECT_THAT(Nodes, testing::UnorderedElementsAre(A, B, X, Y, Z));
+
+  Nodes.clear();
+  for (const ForestNode &N : X->descendants())
+    Nodes.push_back(&N);
+  EXPECT_THAT(Nodes, testing::UnorderedElementsAre(X, A, B));
+}
+
 } // namespace
 } // namespace pseudo
 } // namespace clang