[pseudo] Eliminate the false `::` nested-name-specifier ambiguity

[hokein]

Summary

The solution is to favor the longest possible nest-name-specifier, and
drop other alternatives by using the guard, per C++ [basic.lookup.qual.general].

Motivated cases:

Foo::Foo() {};
// the constructor can be parsed as:
//  - Foo ::Foo(); // where the first Foo is return-type, and ::Foo is the function declarator
//  + Foo::Foo(); // where Foo::Foo is the function declarator

void test() {

// a very slow parsing case when there are many qualifiers!
X::Y::Z;
// The statement can be parsed as:
//  - X ::Y::Z; // ::Y::Z is the declarator
//  - X::Y ::Z; // ::Z is the declarator
//  + X::Y::Z;  // a declaration without declarator (X::Y::Z is decl-specifier-seq)
//  + X::Y::Z;  // a qualifed-id expression
}

[sammccall]

My main concern here is that this might reject valid code (and if it doesn't, it's not obvious why).

It does look like C++ forbids the cases I can come up with (e.g. trying to provide a definition for ::Foo is rejected by clang with "definition or redeclaration of Foo cannot name the global scope).
But I'd be way more comfortable if we could connect the specific guard rules here with spec language.

If we can't do this rigorously and merely are trying to encourage the *common* parse, then we should do it in soft disambig.

I'd like to think about this some more, do you know what part of the spec says that x ::y is invalid if x is e.g. a typedef for int?

[hokein]

In D130511#3677423, @sammccall wrote:

My main concern here is that this might reject valid code (and if it doesn't, it's not obvious why).
It does look like C++ forbids the cases I can come up with (e.g. trying to provide a definition for ::Foo is rejected by clang with "definition or redeclaration of Foo cannot name the global scope).
But I'd be way more comfortable if we could connect the specific guard rules here with spec language.

The qualified declarator is tricky (it was forbidden until https://cplusplus.github.io/CWG/issues/482.html).

The closest thing I can find in the standard is basic.lookup.qual.general:

If a name, template-id, or decltype-specifier is followed by a ​::​, it shall designate a namespace, class, enumeration, or dependent type, and the ​::​ is never interpreted as a complete nested-name-specifier.

IIUC, this rule forbids the parses X::Y ::Z; and X ::Y::Z; (because in the declarator we have a complete :: nested-name-specifier).

If we can't do this rigorously and merely are trying to encourage the *common* parse, then we should do it in soft disambig.

I'd like to think about this some more, do you know what part of the spec says that x ::y is invalid if x is e.g. a typedef for int?

I didn't try to find it harder, I guess it is probably in the qualified-name-look-up section.

[sammccall]

TL;DR: I suspect this is valid but guarding nested-name-specifier := :: [guard=PrevNotIdentifier] may be equivalent and clearer.

In D130511#3678938, @hokein wrote:

In D130511#3677423, @sammccall wrote:

My main concern here is that this might reject valid code (and if it doesn't, it's not obvious why).
It does look like C++ forbids the cases I can come up with (e.g. trying to provide a definition for ::Foo is rejected by clang with "definition or redeclaration of Foo cannot name the global scope).
But I'd be way more comfortable if we could connect the specific guard rules here with spec language.

The qualified declarator is tricky (it was forbidden until https://cplusplus.github.io/CWG/issues/482.html).

The closest thing I can find in the standard is basic.lookup.qual.general:

If a name, template-id, or decltype-specifier is followed by a ​::​, it shall designate a namespace, class, enumeration, or dependent type, and the ​::​ is never interpreted as a complete nested-name-specifier.

OK, so just spelling this out so I don't get lost...

A name is an identifier or operator name.
From the grammar nested-name-specifier can have components preceding :::

• nothing (global scope)
• type-name, namespace-name: these are identifiers = names
• decltype-specifier,
• (simple)-template-id

So the rule is saying that if the :: can bind to the thing on its left, it must (*all* the non-null components are either names, template IDs, or decltype-specifiers).

I think this is probably what you've implemented here, though it's not totally obvious to me.

It seems most natural/more obviously-correct to express this as a guard on namespace-specifier := ::, as that's what the rule directly restricts. It's not simple to decide in general (in c < d > :: a, c<d> can be a template-id or not), but we can rule out the cases where the preceding token is an identifier (which is a limitation of your patch, right?).

Does nested-name-specifier := :: [guard=PrevTokenNotIdentifier] work for your testcases?
I think this is easier to tie to the [basic.language.qual.general] language you quoted.
(If you *don't* find this clearer, please do push back)

[hokein]

refine the patch: guard the "::" nested-name-specifier rule instead.

[hokein]

In D130511#3679161, @sammccall wrote:

TL;DR: I suspect this is valid but guarding nested-name-specifier := :: [guard=PrevNotIdentifier] may be equivalent and clearer.

Yeah, that's better!

[sammccall]

Nice!

clang-tools-extra/pseudo/lib/cxx/CXX.cpp

165

Is LookaheadIndex from another patch?
I can't find it at head.

It seems a bit gratuitous here vs P.RHS.front()->startTokenIndex()... In general getting the info from RHS seems cleaner than jumping across by reasoning how many tokens it has

321

You could write this as TOKEN_GUARD(coloncolon, Tok.prev().Kind != tok::identifier)

If it's that short i like having the guard logic inline to avoid the indirection for the reader

clang-tools-extra/pseudo/test/cxx/nested-name-specifier.cpp

19

Maybe check:
a<b>::c is ambiguous 3 ways, with a fixme to eliminate the one that is invalid. (I.e. the declaration of ::c)

[hokein]

address review comments.

[hokein]

clang-tools-extra/pseudo/lib/cxx/CXX.cpp

165

Yeah, the lookaheadIndex is from my other patch: https://reviews.llvm.org/D130591

I think using Tok.prev() is much better.

321

Good point!

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

struct Token {
   /// Returns the next token in the stream, skipping over comments.
   const Token &nextNC() const {
     const Token *T = this;
     do
       T = &T->next();
     while (T->Kind == tok::comment);
     return *T;
   }
+  /// Returns the previous token in the stream. this may not be a sentinel.
+  const Token &prev() const {
+    assert(Kind != tok::eof);
+    return *(this - 1);
+  }
   /// Returns the bracket paired with this one, if any.
   const Token *pair() const { return Pair == 0 ? nullptr : this + Pair; }
 
   /// The type of token as determined by clang's lexer.
   clang::tok::TokenKind Kind = clang::tok::unknown;
   /// If this token is a paired bracket, the offset of the pair in the stream.
   int32_t Pair = 0;
 };

clang-tools-extra/pseudo/lib/cxx/CXX.cpp

bool isFunctionDeclarator(const ForestNode *Declarator) {
   llvm_unreachable("unreachable");
 }
 
 bool guardNextTokenNotElse(const GuardParams &P) {
   return symbolToToken(P.Lookahead) != tok::kw_else;
 }
 
 // Whether this e.g. decl-specifier contains an "exclusive" type such as a class
 // name, and thus can't combine with a second exclusive type.
 //
 // Returns false for
 //  - non-types
 //  - "unsigned" etc that may suffice as types but may modify others
 //  - cases of uncertainty (e.g. due to ambiguity)
 bool hasExclusiveType(const ForestNode *N) {
   // FIXME: every time we apply this check, we walk the whole subtree.
   // Add per-node caching instead.
return {
        guardNextTokenNotElse},
       {rule::selection_statement::
            IF__CONSTEXPR__L_PAREN__condition__R_PAREN__statement,
        guardNextTokenNotElse},
       {rule::selection_statement::
            IF__CONSTEXPR__L_PAREN__init_statement__condition__R_PAREN__statement,
        guardNextTokenNotElse},
 
+      // Implement C++ [basic.lookup.qual.general]:
+      //   If a name, template-id, or decltype-specifier is followed by a
+      //   !::!, it shall designate a namespace, class, enumeration, or
+      //   dependent type, and the !::! is never interpreted as a complete
+      //   nested-name-specifier.
+      {rule::nested_name_specifier::COLONCOLON,
+       TOKEN_GUARD(coloncolon, Tok.prev().Kind != tok::identifier)},
+
       // The grammar distinguishes (only) user-defined vs plain string literals,
       // where the clang lexer distinguishes (only) encoding types.
       {rule::user_defined_string_literal_chunk::STRING_LITERAL,
        TOKEN_GUARD(string_literal, isStringUserDefined(Tok))},
       {rule::user_defined_string_literal_chunk::UTF8_STRING_LITERAL,
        TOKEN_GUARD(utf8_string_literal, isStringUserDefined(Tok))},
       {rule::user_defined_string_literal_chunk::UTF16_STRING_LITERAL,
        TOKEN_GUARD(utf16_string_literal, isStringUserDefined(Tok))},

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

 unqualified-id := IDENTIFIER
 unqualified-id := operator-function-id
 unqualified-id := conversion-function-id
 unqualified-id := literal-operator-id
 unqualified-id := ~ type-name
 unqualified-id := ~ decltype-specifier
 unqualified-id := template-id
 qualified-id := nested-name-specifier TEMPLATE_opt unqualified-id
-nested-name-specifier := ::
+nested-name-specifier := :: [guard]
 nested-name-specifier := type-name ::
 nested-name-specifier := namespace-name ::
 nested-name-specifier := decltype-specifier ::
 nested-name-specifier := nested-name-specifier IDENTIFIER ::
 nested-name-specifier := nested-name-specifier TEMPLATE_opt simple-template-id ::
 lambda-expression := lambda-introducer lambda-declarator_opt compound-statement
 lambda-expression := lambda-introducer < template-parameter-list > requires-clause_opt lambda-declarator_opt compound-statement
 #! We allow a capture-default to appear anywhere in a capture-list.

clang-tools-extra/pseudo/test/cxx/nested-name-specifier.cpp

+// RUN: clang-pseudo -grammar=cxx -source=%s --print-forest | FileCheck %s
+
+// Verify that we don't form a complete `::` nested-name-specifier if there is
+// an identifier preceding it.
+Foo::Foo() {} // No  "Foo ::Foo()" false parse
+// CHECK:      ├─declaration-seq~function-definition := function-declarator function-body
+// CHECK-NEXT: │ ├─function-declarator~noptr-declarator := noptr-declarator parameters-and-qualifiers
+
+int ::x;
+// CHECK:      declaration~simple-declaration := decl-specifier-seq init-declarator-list ;
+// CHECK-NEXT: ├─decl-specifier-seq~INT
+
+void test() {
+  X::Y::Z; // No false qualified-declarator parses "X ::Y::Z" and "X::Y ::Z".
+// CHECK:  statement-seq~statement := <ambiguous>
+// CHECK:  statement~expression-statement := expression ;
+// CHECK:  statement~simple-declaration := decl-specifier-seq ;
+// CHECK-NOT: simple-declaration := decl-specifier-seq init-declarator-list ;
+
+  // FIXME: eliminate the false `a<b> ::c` declaration parse.
+  a<b>::c;
+// CHECK: statement := <ambiguous>
+// CHECK-NEXT: ├─statement~expression-statement := expression ;
+// CHECK-NEXT: │ ├─expression~relational-expression :=
+// CHECK:      └─statement~simple-declaration := <ambiguous>
+// CHECK-NEXT:   ├─simple-declaration := decl-specifier-seq ;
+// CHECK:        └─simple-declaration := decl-specifier-seq init-declarator-list ;
+}