[pseudo] Split greatergreater token.

[hokein]

Summary

For a >> token (a right shift operator, or a nested template?), the clang
lexer always returns a single greatergreater token, as a result,
the grammar-based GLR parser never try to parse the nested template
case.

We derive a token stream by always splitting the >> token, so that the
GLR parser is able to pursue both options during parsing (usually 1
path fails).

[hokein]

define a greatergreater nonterminal per discussion.

[sammccall]

This seems like the right approach to me.

It seems a bit strange to be doing this whether we're parsing C++ or not, but I guess we're not going to want low-level grammar differences between C and C++ if we can avoid it.

clang/lib/Tooling/Syntax/Pseudo/Token.cpp

97 ↗

(On Diff #415363)

What do you think about combining this into cook()?
Seems a bit wasteful to do a separate pass for this. (We can always split it out again later if cook() gets too complicated)

107 ↗

(On Diff #415363)

I don't think we'll ever fix this, I'd drop the FIXME and add a ! at the end :-)

112 ↗

(On Diff #415363)

why not assert at the top and remove the if?

This can only be caused by a really bad programmer error, I don't think we should worry about defending against it making it into production.

clang/lib/Tooling/Syntax/Pseudo/cxx.bnf

102 ↗

(On Diff #415363)

we should rather indirect this change through a new nonterminal:

greater-greater := > >
fold-operator := greater-greater

This lets us document the change in one place, and makes it easier to avoid the false parses if they prove important. We could restrict the first rule to only match if the second token has a mergeable bit or something.

[hokein]

address comments

[hokein]

rebase.

[uabelho]

Hello,

It seems like the new testcase fails when run with sanitizers:
https://lab.llvm.org/buildbot/#/builders/5/builds/20833

[zequanwu]

This fails on windows bot at https://logs.chromium.org/logs/chromium/buildbucket/cr-buildbucket/8819402935494502225/+/u/package_clang/stdout?format=raw.

C:\b\s\w\ir\cache\builder\src\third_party\llvm\clang-tools-extra\pseudo\unittests\TokenTest.cpp(190): error: Value of: Split.tokens()


 Expected: has 5 elements where


 element #0 token (">", 51),


 element #1 token (">", 51),


 element #2 token (">", 51),


 element #3 token (">", 51),


 element #4 token (">>=", 54)


   Actual: { greater 1:0 ">" flags=1, greater 1:0 ">" flags=1, greater 3:0 "\80" flags=1, greater 3:0 "\10" flags=1, greatergreaterequal 5:0 ">>=" flags=1 }, whose element #2 doesn't match


 [  FAILED  ] TokenTest.SplitGreaterGreater (1 ms)

[probinson]

We had the same thing happen downstream. One of our guys speculates that because some allocations are "owned" by the returned TokenStream, but the returned TokenStream is a temporary, the lifetimes might not be sufficient and some deallocations can happen.
If I change the nested calls stripComments(cook(lex(Code, Opts), Opts)) to separate calls stored to separate locals, the problem goes away.

[hokein]

Thanks for the report and revert, and sorry for the failures and the late response (was OOO on Friday).

One of our guys speculates that because some allocations are "owned" by the returned TokenStream, but the returned TokenStream is a temporary, the lifetimes might not be sufficient and some deallocations can happen.
If I change the nested calls stripComments(cook(lex(Code, Opts), Opts)) to separate calls stored to separate locals, the problem goes away.

Thanks for diagnosing it. Yeah, this is the root cause. cook returns a tokenStream (which has its own payload), and this token stream is a temporary and being destroyed after the stripComments statement, and we have dangling pointers. I will prepare a fix.

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

enum class LexFlags : uint8_t {
   /// Careful, the directive may not start exactly on the StartsPPLine token:
   ///   /*comment*/ #include <foo.h>
   StartsPPLine = 1 << 0,
   /// Marks tokens containing trigraphs, escaped newlines, UCNs etc.
   /// The text() of such tokens will contain the raw trigrah.
   NeedsCleaning = 1 << 1,
 };
 
-/// Derives a token stream by decoding escapes and interpreting raw_identifiers.
+/// Derives a token stream by decoding escapes, interpreting raw_identifiers and
+/// splitting the greatergreater token.
 ///
 /// Tokens containing UCNs, escaped newlines, trigraphs etc are decoded and
 /// their backing data is owned by the returned stream.
 /// raw_identifier tokens are assigned specific types (identifier, keyword etc).
 ///
 /// The StartsPPLine flag is preserved.
 ///
 /// Formally the identifier correctly happens before preprocessing, while we

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

if (Tok.flag(LexFlags::NeedsCleaning)) {
       llvm::SmallString<64> UCNBuffer;
       clang::expandUCNs(UCNBuffer, CleanBuffer);
 
       llvm::StringRef Text = llvm::StringRef(UCNBuffer).copy(*CleanedStorage);
       Tok.Data = Text.data();
       Tok.Length = Text.size();
       Tok.Flags &= ~static_cast<decltype(Tok.Flags)>(LexFlags::NeedsCleaning);
     }
+
+    if (Tok.Kind == tok::raw_identifier) {
       // Cook raw_identifiers into identifier, keyword, etc.
-    if (Tok.Kind == tok::raw_identifier)
       Tok.Kind = Identifiers.get(Tok.text()).getTokenID();
+    } else if (Tok.Kind == tok::greatergreater) {
+      // Split the greatergreater token.
+      // FIXME: split lessless token to support Cuda triple angle brackets <<<.
+      assert(Tok.text() == ">>");
+      Tok.Kind = tok::greater;
+      Tok.Length = 1;
+      Result.push(Tok);
+      // Line is wrong if the first greater is followed by an escaped newline!
+      Tok.Data = Tok.text().data() + 1;
+    }
+
     Result.push(std::move(Tok));
   }
 
   Result.finalize();
   return Result;
 }
 
 } // namespace pseudo
 } // namespace clang

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

 # This is a C++ grammar from the C++ standard [1].
 #
 # The grammar is a superset of the true grammar requring semantic constraints to
 # resolve ambiguties. The grammar is context-free and ambiguous (beyond the
 # limit of LR(k)). We use general parsing algorithm (e.g GLR) to handle the
 # grammar and generate a transition table which is used to drive the parsing.
 #
 # It aims to align with the ISO C++ grammar as much as possible. We adjust it
 # to fit the need for the grammar-based parser:
 #  - attributes are omitted, which will be handled as comments;
 #  - we don't allow nullable non-terminal symbols. There are few nullable
 #    non-terminals in the spec grammar, they are adjusted to be non-nullable;
 #  - the file merely describes the core C++ grammar. Preprocessor directives and
 #    lexical conversions are omitted as we reuse clang's lexer and run a fake
 #    preprocessor;
+#  - grammar rules with the >> token are adjusted, the greatergreater token is
+#    split into two > tokens, to make the GLR parser aware of nested templates
+#    and right shift operator;
 #
 # Guidelines:
 #   - non-terminals are lower_case; terminals (aka tokens) correspond to
 #     clang::TokenKind, written as "IDENTIFIER", "USING", "::" etc;
 #   - optional symbols are supported, with a _opt suffix;
 #
 # [1] https://isocpp.org/files/papers/N4860.pdf
 #

 fold-operator := +
 fold-operator := -
 fold-operator := *
 fold-operator := /
 fold-operator := %
 fold-operator := ^
 fold-operator := |
 fold-operator := <<
-fold-operator := >>
+fold-operator := greatergreater
 fold-operator := +=
 fold-operator := -=
 fold-operator := *=
 fold-operator := /=
 fold-operator := %=
 fold-operator := ^=
 fold-operator := &=
 fold-operator := |=

 multiplicative-expression := multiplicative-expression % pm-expression
 # expr.add
 additive-expression := multiplicative-expression
 additive-expression := additive-expression + multiplicative-expression
 additive-expression := additive-expression - multiplicative-expression
 # expr.shift
 shift-expression := additive-expression
 shift-expression := shift-expression << additive-expression
-shift-expression := shift-expression >> additive-expression
+shift-expression := shift-expression greatergreater additive-expression
 # expr.spaceship
 compare-expression := shift-expression
 compare-expression := compare-expression <=> shift-expression
 # expr.rel
 relational-expression := compare-expression
 relational-expression := relational-expression < compare-expression
 relational-expression := relational-expression > compare-expression
 relational-expression := relational-expression <= compare-expression

 operator-name := <
 operator-name := >
 operator-name := <=
 operator-name := >=
 operator-name := <=>
 operator-name := ^^
 operator-name := ||
 operator-name := <<
-operator-name := >>
+operator-name := greatergreater
 operator-name := <<=
 operator-name := >>=
 operator-name := ++
 operator-name := --
 operator-name := ,
 literal-operator-id := OPERATOR string-literal IDENTIFIER
 literal-operator-id := OPERATOR user-defined-string-literal
 

 #! Contextual keywords -- clang lexer always lexes them as identifier tokens.
 #! Placeholders for literal text in the grammar that lex as other things.
 contextual-override := IDENTIFIER
 contextual-final := IDENTIFIER
 contextual-zero := NUMERIC_CONSTANT
 module-keyword := IDENTIFIER
 import-keyword := IDENTIFIER
 export-keyword := IDENTIFIER
+
+#! greatergreater token -- clang lexer always lexes it as a single token, we
+#! split it into two tokens to make the GLR parser aware of the nested-template
+#! case.
+greatergreater := > >

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

)cpp";
   EXPECT_THAT(Raw.tokens(), ElementsAreArray({
                                 lineIndent(0, 3), // hello
                                 lineIndent(0, 3), // world
                                 lineIndent(1, 0), // no_indent
                                 lineIndent(2, 2), // line_was_continued
                             }));
 }
 
+TEST(TokenTest, SplitGreaterGreater) {
+  LangOptions Opts;
+  std::string Code = R"cpp(
+>> // split
+// >> with an escaped newline in the middle, split
+>\
+>
+>>= // not split
+)cpp";
+  TokenStream Split = stripComments(cook(lex(Code, Opts), Opts));
+  EXPECT_THAT(Split.tokens(), ElementsAreArray({
+                                  token(">", tok::greater),
+                                  token(">", tok::greater),
+                                  token(">", tok::greater),
+                                  token(">", tok::greater),
+                                  token(">>=", tok::greatergreaterequal),
+                              }));
+}
+
 TEST(TokenTest, DropComments) {
   LangOptions Opts;
   std::string Code = R"cpp(
   // comment
   int /*abc*/;
 )cpp";
   TokenStream Raw = cook(lex(Code, Opts), Opts);
   TokenStream Stripped = stripComments(Raw);