[pseudo] Eliminate the type-name identifier ambiguities in the grammar.

[hokein]

Summary

See https://reviews.llvm.org/D130626 for motivation.

Identifier in the grammar has different categories (type-name, template-name, namespace-name), they requires semantic information to resolve.
This patch is to eliminate the "local" ambiguities in type-name, and namespace-name, which gives us a performance boost of the parser:

• eliminate all different type rules (class-name, enum-name, typedef-name), fold them into a unified type-name, this removes the #1 type-name ambiguity, and gives us a big performance boost;
• remove the namespace-alis rules, as they're hard and uninteresting;

Note that we could eliminate more and gain more performance (like fold template-name, type-name, namespace together), but at current stage, we'd like keep all existing categories of the identifier (as they might assist in correlated disambiguation & keep the representation of important concepts uniform).

[hokein]

update based on the offline discussion -- we'd like to keep all categories of
IDENTIFIER (type-name, namespace-name, template-name, template-name) as they
are useful in disambiguation, but we eliminate the ambiguities per each category

• eliminate all different type rules (class-name, enum-name, typedef-name), fold them into a unified type-name, this removes the #1 type-name ambiguity, and gives us a big performance boost;
• remove the namespace-alis rules, as they're less interesting and marginal useful;

[hokein]

New data on the patch:

file	ambiguous nodes	forest size	glrParse performance
SemaCodeComplete.cpp	11k -> 5.7K	10.4MB -> 7.9MB	7.1MB/s -> 9.98MB/s
AST.cpp	1.3k -> 0.73K	0.99MB -> 0.77MB	6.7MB/s -> 8.4MB/s

clang-tools-extra/pseudo/lib/cxx/cxx.bnf

39–40

this can be removed as well, but the class-head-name rule uses it.

[sammccall]

LG, though i think we should eliminate class-name altogether.

This gives most of the perf, which is nice!

The reduction in ambiguous nodes is less impressive than before :-( As discussed offline, i think the remaining ambiguous nodes serve a purpose as they will assist in correlated disambiguation & keep the representation of important concepts uniform. I may be wrong about that, in which case we can still drop them later.

The forest size reduction is nice to have, but least critical imo.

clang-tools-extra/pseudo/lib/cxx/cxx.bnf

37–38

Maybe "we don't distinguish between namespaces and namespace aliases, as it's hard and uninteresting"?

[sammccall]

clang-tools-extra/pseudo/lib/cxx/cxx.bnf

39–40

Can't we use class-head-name := nested-name-specifier_opt type-name as class-name and type-name now match?

(Oops, not sure how i lost this comment)

[hokein]

address comments.

[hokein]

In D130747#3727386, @sammccall wrote:

LG, though i think we should eliminate class-name altogether.

This gives most of the perf, which is nice!

The reduction in ambiguous nodes is less impressive than before :-( As discussed offline, i think the remaining ambiguous nodes serve a purpose as they will assist in correlated disambiguation & keep the representation of important concepts uniform. I may be wrong about that, in which case we can still drop them later.

Yeah, this is because we still keep two critical ambiguous nodes:

• simple-type-specifier (type-name vs template-name), e.g. for the CTAD case;
• nested-name-specifier (type-name vs namespace-name), e.g. for a::b::c case;

These two ambiguous nodes are the top1 and top2 now.

The forest size reduction is nice to have, but least critical imo.

clang-tools-extra/pseudo/lib/cxx/cxx.bnf

39–40

ah, this is clever, I missed that the fact that class-name and type-name are identical now.

clang-tools-extra/pseudo/lib/cxx/cxx.bnf

 # We list important nonterminals as start symbols, rather than doing it for all
 # nonterminals by default, this reduces the number of states by 30% and LRTable
 # actions by 16%.
 _ := translation-unit
 _ := statement-seq
 _ := declaration-seq
 
 # gram.key
-typedef-name := IDENTIFIER
-typedef-name := simple-template-id
+#! we don't distinguish between namespaces and namespace aliases, as it's hard
+#! and uninteresting.
 namespace-name := IDENTIFIER
-namespace-name := namespace-alias
-namespace-alias := IDENTIFIER
-class-name := IDENTIFIER
-class-name := simple-template-id
-enum-name := IDENTIFIER
 template-name := IDENTIFIER
 
 # gram.basic
 #! Custom modifications to eliminate optional declaration-seq
 translation-unit := declaration-seq
 translation-unit := global-module-fragment_opt module-declaration declaration-seq_opt private-module-fragment_opt
 
 # gram.expr
 # expr.prim

 builtin-type := CHAR16_T
 builtin-type := CHAR32_T
 builtin-type := WCHAR_T
 builtin-type := BOOL
 builtin-type := INT
 builtin-type := FLOAT
 builtin-type := DOUBLE
 builtin-type := VOID
-type-name := class-name
-type-name := enum-name
-type-name := typedef-name
+#! Unlike C++ standard grammar, we don't distinguish the underlying type (class,
+#! enum, typedef) of the IDENTIFIER, as these ambiguities are "local" and don't
+#! affect the final parse tree. Eliminating them gives a significant performance
+#! boost to the parser.
+type-name := IDENTIFIER
+type-name := simple-template-id
 elaborated-type-specifier := class-key nested-name-specifier_opt IDENTIFIER
 elaborated-type-specifier := class-key simple-template-id
 elaborated-type-specifier := class-key nested-name-specifier TEMPLATE_opt simple-template-id
 elaborated-type-specifier := elaborated-enum-specifier
 elaborated-enum-specifier := ENUM nested-name-specifier_opt IDENTIFIER
 decltype-specifier := DECLTYPE ( expression )
 placeholder-type-specifier := type-constraint_opt AUTO
 placeholder-type-specifier := type-constraint_opt DECLTYPE ( AUTO )

 # module-import-declaration := import-keyword header-name ;
 global-module-fragment := module-keyword ; declaration-seq_opt
 private-module-fragment := module-keyword : PRIVATE ; declaration-seq_opt
 
 # gram.class
 class-specifier := class-head { member-specification_opt [recover=Brackets] }
 class-head := class-key class-head-name class-virt-specifier_opt base-clause_opt
 class-head := class-key base-clause_opt
-class-head-name := nested-name-specifier_opt class-name
+class-head-name := nested-name-specifier_opt type-name
 class-virt-specifier := contextual-final
 class-key := CLASS
 class-key := STRUCT
 class-key := UNION
 member-specification := member-declaration member-specification_opt
 member-specification := access-specifier : member-specification_opt
 member-declaration := decl-specifier-seq member-declarator-list_opt ;
 member-declaration := member-declarator-list ;

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

 // RUN: clang-pseudo -grammar=cxx -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:   │ └─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:      2 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: Ambiguity: 0.20 misparses/token
 // CHECK-NEXT: Unparsed: 0.00%