[pseudo] Eliminate multiple-specified-types ambiguities in the grammar.

[sammccall]

Summary

Motivating case: foo bar; is not a declaration of nothing with foo and bar
both types.

This is a common and critical ambiguity, and I expect eliminating it in the
grammar is more efficient than using guards (without caching).

[sammccall]

I'm not sure that eliminating this in the grammar is the right technique vs guards, appreciate your thoughts.

On clangd/AST.cpp, this reduces ambiguities from 1748->1400 (20%).

[sammccall]

As discussed offline:

We agree on the goal of disallowing duplicate types in decl-specifier-seq, but the grammar changes are too intrusive if a guard-based approach can work instead.
The concern with guards on seq nodes is duplicate work (a tree walk at every level).
Since ForestNodes are immutable and reasonable in number we can introduce fairly cheap caching, e.g. of whether a decl-specifier[-seq] contains an exclusive type definition. This is a reusable building block for guards etc, so we should build it into the contract.

The other idea I was playing with of guarding simple-declaration := decl-specifier-seq /*no declarators*/ ; by requiring the decl-specifier-seq to declare a type (disallow "declaration declares nothing") is inferior as a) the code is technically legal, b) it doesn't address std::string x; misparsing as Type{std} Type{::string} Declarator{x};.

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

 nodeclspec-function-declaration := function-declarator ;
 alias-declaration := USING IDENTIFIER = defining-type-id ;
 simple-declaration := decl-specifier-seq init-declarator-list_opt ;
 simple-declaration := decl-specifier-seq ref-qualifier_opt [ identifier-list ] initializer ;
 static_assert-declaration := STATIC_ASSERT ( constant-expression ) ;
 static_assert-declaration := STATIC_ASSERT ( constant-expression , string-literal ) ;
 empty-declaration := ;
 # dcl.spec
-decl-specifier := storage-class-specifier
-decl-specifier := defining-type-specifier
-decl-specifier := function-specifier
-decl-specifier := FRIEND
-decl-specifier := TYPEDEF
-decl-specifier := CONSTEXPR
-decl-specifier := CONSTEVAL
-decl-specifier := CONSTINIT
-decl-specifier := INLINE
-decl-specifier-seq := decl-specifier
-decl-specifier-seq := decl-specifier decl-specifier-seq
+#! Standard grammar doesn't require a {decl,type,defining-type}-specifier-seq
+#! to have only one e.g. class name.
+#! This leads to ambiguity: does `foo bar;` declare:
+#!  - a variable named `bar` of type `foo`?
+#!  - nothing, with both `foo` and `bar` being types?!
+#! Here we eliminate that ambiguity in the grammar:
+#!  exclusive-* has a type name (e.g exclusive-type-specifier ~ IDENTIFIER)
+#!  combining-* has no type name (e.g. combining-type-specifier ~ UNSIGNED)
+#!  combining-*-seq has no type name (e.g. UNSIGNED CONST)
+#!  *-seq has at most one type name (e.g. type-specifier-seq ~ CONST IDENTIFIER)
+combining-decl-specifier := storage-class-specifier
+combining-decl-specifier := combining-defining-type-specifier
+combining-decl-specifier := function-specifier
+combining-decl-specifier := FRIEND
+combining-decl-specifier := TYPEDEF
+combining-decl-specifier := CONSTEXPR
+combining-decl-specifier := CONSTEVAL
+combining-decl-specifier := CONSTINIT
+combining-decl-specifier := INLINE
+combining-decl-specifier-seq := combining-decl-specifier combining-decl-specifier-seq_opt
+decl-specifier-seq := combining-decl-specifier-seq
+decl-specifier-seq := combining-decl-specifier-seq_opt exclusive-defining-type-specifier combining-decl-specifier-seq_opt
 storage-class-specifier := STATIC
 storage-class-specifier := THREAD_LOCAL
 storage-class-specifier := EXTERN
 storage-class-specifier := MUTABLE
 function-specifier := VIRTUAL
 function-specifier := explicit-specifier
 explicit-specifier := EXPLICIT ( constant-expression )
 explicit-specifier := EXPLICIT
-type-specifier := simple-type-specifier
-type-specifier := elaborated-type-specifier
-type-specifier := typename-specifier
-type-specifier := cv-qualifier
-type-specifier-seq := type-specifier
-type-specifier-seq := type-specifier type-specifier-seq
-defining-type-specifier := type-specifier
-defining-type-specifier := class-specifier
-defining-type-specifier := enum-specifier
-defining-type-specifier-seq := defining-type-specifier
-defining-type-specifier-seq := defining-type-specifier defining-type-specifier-seq
-simple-type-specifier := nested-name-specifier_opt type-name
-simple-type-specifier := nested-name-specifier TEMPLATE simple-template-id
-simple-type-specifier := decltype-specifier
-simple-type-specifier := placeholder-type-specifier
-simple-type-specifier := nested-name-specifier_opt template-name
-simple-type-specifier := CHAR
-simple-type-specifier := CHAR8_T
-simple-type-specifier := CHAR16_T
-simple-type-specifier := CHAR32_T
-simple-type-specifier := WCHAR_T
-simple-type-specifier := BOOL
-simple-type-specifier := SHORT
-simple-type-specifier := INT
-simple-type-specifier := LONG
-simple-type-specifier := SIGNED
-simple-type-specifier := UNSIGNED
-simple-type-specifier := FLOAT
-simple-type-specifier := DOUBLE
-simple-type-specifier := VOID
+combining-type-specifier := combining-simple-type-specifier
+exclusive-type-specifier := exclusive-simple-type-specifier
+exclusive-type-specifier := elaborated-type-specifier
+exclusive-type-specifier := typename-specifier
+combining-type-specifier := cv-qualifier
+combining-type-specifier-seq := combining-type-specifier combining-type-specifier-seq_opt
+type-specifier-seq := combining-type-specifier-seq
+type-specifier-seq := combining-type-specifier_opt exclusive-type-specifier combining-type-specifier_opt
+combining-defining-type-specifier := combining-type-specifier
+exclusive-defining-type-specifier := exclusive-type-specifier
+exclusive-defining-type-specifier := class-specifier
+exclusive-defining-type-specifier := enum-specifier
+combining-defining-type-specifier-seq := combining-defining-type-specifier combining-defining-type-specifier-seq_opt
+defining-type-specifier-seq := combining-defining-type-specifier-seq
+defining-type-specifier-seq := combining-defining-type-specifier-seq_opt exclusive-type-specifier combining-defining-type-specifier-seq_opt
+simple-type-specifier := exclusive-simple-type-specifier
+simple-type-specifier := combining-simple-type-specifier
+exclusive-simple-type-specifier := nested-name-specifier_opt type-name
+exclusive-simple-type-specifier := nested-name-specifier TEMPLATE simple-template-id
+exclusive-simple-type-specifier := decltype-specifier
+exclusive-simple-type-specifier := placeholder-type-specifier
+exclusive-simple-type-specifier := nested-name-specifier_opt template-name
+exclusive-simple-type-specifier := CHAR
+exclusive-simple-type-specifier := CHAR8_T
+exclusive-simple-type-specifier := CHAR16_T
+exclusive-simple-type-specifier := CHAR32_T
+exclusive-simple-type-specifier := WCHAR_T
+exclusive-simple-type-specifier := BOOL
+combining-simple-type-specifier := SHORT
+exclusive-simple-type-specifier := INT
+combining-simple-type-specifier := LONG
+combining-simple-type-specifier := SIGNED
+combining-simple-type-specifier := UNSIGNED
+exclusive-simple-type-specifier := FLOAT
+exclusive-simple-type-specifier := DOUBLE
+exclusive-simple-type-specifier := VOID
 type-name := class-name
 type-name := enum-name
 type-name := typedef-name
 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

clang-tools-extra/pseudo/test/cxx/decl-specifier-seq.cpp

+// RUN: clang-pseudo -grammar=cxx -source=%s --print-forest | FileCheck %s
+// No ambiguity: 'bar' is definitely a variable name.
+const foo volatile bar;
+// CHECK:      simple-declaration
+// CHECK-NEXT: ├─decl-specifier-seq
+// CHECK-NEXT: │ ├─combining-decl-specifier-seq~CONST
+// CHECK-NEXT: │ ├─exclusive-defining-type-specifier~exclusive-simple-type-specifier := <ambiguous>
+// CHECK-NEXT: │ │ ├─exclusive-simple-type-specifier~type-name := <ambiguous>
+// CHECK-NEXT: │ │ │ ├─type-name~IDENTIFIER
+// CHECK-NEXT: │ │ │ ├─type-name~IDENTIFIER
+// CHECK-NEXT: │ │ │ └─type-name~IDENTIFIER
+// CHECK-NEXT: │ │ └─exclusive-simple-type-specifier~IDENTIFIER
+// CHECK-NEXT: │ └─combining-decl-specifier-seq~VOLATILE
+// CHECK-NEXT: ├─init-declarator-list~IDENTIFIER
+// CHECK-NEXT: └─; := tok[4]
+// Ambiguity: though unlikely, we may be declaring nothing.
+unsigned baz;
+// CHECK-NEXT: declaration~simple-declaration := <ambiguous>
+// CHECK-NEXT: ├─simple-declaration := decl-specifier-seq ;
+// CHECK-NEXT: ├─decl-specifier-seq
+// CHECK-NEXT: │ │ ├─combining-decl-specifier-seq := combining-decl-specifier #1
+// CHECK-NEXT: │ │ │ └─combining-decl-specifier~UNSIGNED
+// CHECK-NEXT: │ │ └─exclusive-defining-type-specifier~exclusive-simple-type-specifier
+// CHECK-NEXT: │ │   ├─exclusive-simple-type-specifier~type-name
+// CHECK-NEXT: │ │   │ ├─type-name~IDENTIFIER
+// CHECK-NEXT: │ │   │ ├─type-name~IDENTIFIER
+// CHECK-NEXT: │ │   │ └─type-name~IDENTIFIER
+// CHECK-NEXT: │ │   └─exclusive-simple-type-specifier~IDENTIFIER
+// CHECK-NEXT: │ └─;
+// CHECK-NEXT: └─simple-declaration := decl-specifier-seq init-declarator-list ;
+// CHECK-NEXT:   ├─decl-specifier-seq~combining-decl-specifier-seq =#1
+// CHECK-NEXT:   ├─init-declarator-list~IDENTIFIER
+// CHECK-NEXT:   └─;
+

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:   ├─decl-specifier-seq~exclusive-simple-type-specifier := <ambiguous>
+// CHECK-NEXT:   │ ├─exclusive-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:   │ └─exclusive-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 exclusive-simple-type-specifier
 // CHECK-NEXT: 1 statement
 // CHECK-NEXT: 1 type-name
 // CHECK-EMPTY:
 // CHECK-NEXT: 0 Opaque nodes: