[pseudo] Add ambiguity & unparseability metrics to -print-statistics

[sammccall]

Summary

These can be used to quantify parsing improvements from a change.

[sammccall]

As mentioned offline, we may want a length-weighted version of the ambiguity metric when prioritizing, but I think this one is easier to understand in isolation. If we end up preferring the weighted version we can change this.

[usaxena95]

Would it make sense to expose this tool run + statistics as a library. This would help share the code for all the metrics with google3 (as we wanted to keep these metrics in both the places).

[usaxena95]

Landed the patch. Will extract this as a library to share this with other continuous evaluation pipeline.

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

 }
 
 // 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:
+// CHECK-EMPTY:
+// CHECK-NEXT: Ambiguity: 0.40 misparses/token
+// CHECK-NEXT: Unparsed: 0.00%

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

 #include "clang/Basic/LangOptions.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/STLFunctionalExtras.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Signals.h"
 
+using clang::pseudo::ForestNode;
+using clang::pseudo::Token;
 using clang::pseudo::TokenStream;
 using llvm::cl::desc;
 using llvm::cl::init;
 using llvm::cl::opt;
 
 static opt<bool> PrintGrammar("print-grammar", desc("Print the grammar"));
 static opt<bool> PrintGraph("print-graph",
                             desc("Print the LR graph for the grammar"));
if (ParseableStream) {
     }
 
     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)}) {
+      for (auto &P : {std::make_pair("Ambiguous", ForestNode::Ambiguous),
+                      std::make_pair("Opaque", 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,
                                         Lang.G.symbolName(S.first));
       }
+
+      // Metrics for how imprecise parsing was.
+      // These are rough but aim to be:
+      // - linear: if we eliminate half the errors the metric should halve
+      // - length-independent
+      unsigned UnparsedTokens = 0; // Tokens covered by Opaque. (not unique)
+      unsigned Misparses = 0;      // Sum of alternatives-1
+      llvm::DenseSet<const ForestNode *> Visited;
+      auto DFS = [&](const ForestNode &N, Token::Index End, auto &DFS) -> void {
+        if (N.kind() == ForestNode::Opaque) {
+          UnparsedTokens += End - N.startTokenIndex();
+        } else if (N.kind() == ForestNode::Ambiguous) {
+          Misparses += N.alternatives().size() - 1;
+          for (const auto *C : N.alternatives())
+            if (Visited.insert(C).second)
+              DFS(*C, End, DFS);
+        } else if (N.kind() == ForestNode::Sequence) {
+          for (unsigned I = 0, E = N.children().size(); I < E; ++I)
+            if (Visited.insert(N.children()[I]).second)
+              DFS(*N.children()[I],
+                  I + 1 == N.children().size()
+                      ? End
+                      : N.children()[I + 1]->startTokenIndex(),
+                  DFS);
+        }
+      };
+      unsigned Len = ParseableStream->tokens().size();
+      DFS(Root, Len, DFS);
+      llvm::outs() << "\n";
+      llvm::outs() << llvm::formatv("Ambiguity: {0} misparses/token\n",
+                                    double(Misparses) / Len);
+      llvm::outs() << llvm::formatv("Unparsed: {0}%\n",
+                                    100.0 * UnparsedTokens / Len);
     }
   }
 
   return 0;
 }