[clang-format] Further improve support for requires expressions

[HazardyKnusperkeks]

Summary

Detect requires expressions in more unusable contexts. This is far from
perfect, but currently we have no good metric to decide between a
requires expression and a trailing requires clause.

[curdeius]

Some nits.

clang/lib/Format/UnwrappedLineParser.cpp

1541–1542

2791

2818

2826

2854

2862

[HazardyKnusperkeks]

Rebased and updated

[• Quuxplusone]

clang/lib/Format/UnwrappedLineParser.cpp

2798–2802

s/doesn't/don't/
IIUC you're talking about, like, void member() && requires ( — is that right?
It might help the reader to give an example snippet right here. (OTOH, it might be "obvious," I don't know. I'm not in the target audience for this code.)
...Ah, I see you give a snippet on line 2837 that's basically what I mean; I just first felt the need for that snippet all the way up here.

2835–2841

I think it's weird that your heuristic parses backward rather than forward. I would think that the next token after the requires keyword tells you what it is with pretty high probability:
requires requires — it's a clause
requires identifier — it's a clause
requires { — it's an expression
requires ( — unclear, apply further heuristics

Or are those heuristics already present in trunk, and this PR is just dealing with the "unclear" case?

2882

[HazardyKnusperkeks]

clang/lib/Format/UnwrappedLineParser.cpp

2835–2841

That would be so much better, but I can't easily look forward. Next is still nullptr, until I call nextToken(), but then I'm already moved along.

But this got me thinking, at least for the easy stuff I can just go forward and don't start on the keyword in parseRequiresClause() and parseRequiresExpression(). The paren case is more tricky, but I will try something.

[HazardyKnusperkeks]

New approach for identifying the expressions.

[HazardyKnusperkeks]

clang/lib/Format/UnwrappedLineParser.cpp

2835–2841

Present in main everything is a clause, except for requires expressions in a constraint expression. So the stuff where you use the requires expression in a "normal" boolean expression are misparsed and thus most likely misformatted.

There is actually a peekToken(), let's see if this is better.

[curdeius]

LGTM!

[klimek]

Hey ho, sorry for the late comment here, but adding peekNextToken(n) is problematic, as this gets in the way of future changes we want to do to handle macros better.
Usually we want to use X = Tokens->getPosition() and FormatTok = Tokens->setPosition(X) pairs when doing look-ahead.
I did a quick attempt at fixing this, but ran into infinite loops later in the annotator :(

[klimek]

Generally, why do we need to have that much information? I.e. why do we need to know the exact type of the "requires" keyword?
I do understand we need to know the brace type, but that seems like it would be easier to figure out in the TokenAnnotator (where we already parsed UnwrappedLines).
Do we ever parse UnwrappedLines differently depending on requires clauses/expressions?
If not, we should really do the annotation in TokenAnnotator, where we already have nice parsing bounds from the parsed UnwrappedLines.

[HazardyKnusperkeks]

In D119138#3951749, @klimek wrote:

Generally, why do we need to have that much information? I.e. why do we need to know the exact type of the "requires" keyword?
I do understand we need to know the brace type, but that seems like it would be easier to figure out in the TokenAnnotator (where we already parsed UnwrappedLines).
Do we ever parse UnwrappedLines differently depending on requires clauses/expressions?
If not, we should really do the annotation in TokenAnnotator, where we already have nice parsing bounds from the parsed UnwrappedLines.

Who is we, I'm not part of that we and haven't heard of some macro improvements. And I don't see how that feature is harming you, but be my guest in changing that. If you look into the history of this change I had a heuristic approach which would only look behind to differentiate.

I don't know if that can be solved in the TokenAnnotator, but you and I have different opinions about that. I'd put more annotating in the UnwrappedLineParser, annotate it as soon as we can.

I'll happily review any changes proposed, but I will not rework this piece of code, unless I can see a big flaw in it (which I can't right now).

[klimek]

I changed it in 49aca00d63e14df8bc68fc4329e6cbc9c9805eb8.

"We" is the people working on clang-format :) I hope that we have a common goal of making clang-format as easy to maintain as we can.

FWIW, I once had the same opinion as you about best doing all parsing as early as possible, but djasper convinced me that the split was a good idea, and in the end, I think it turns out to be significantly less brittle to do more complex annotation in TokenAnnotator. E.g. we now have a lookahead limit of 50, which seems rather arbitrary, while in TokenAnnotator we could simply limit lookahead towards the current UnwrappedLine. Similarly, in TokenAnnotator, we already have all the parens connected, so we could simply look from requires l_paren to the corresponding r_paren and whether the next token is an l_brace. If I can find a bit of time I'll take an attempt at implementing it.

[HazardyKnusperkeks]

In D119138#3951850, @klimek wrote:

I changed it in 49aca00d63e14df8bc68fc4329e6cbc9c9805eb8.

"We" is the people working on clang-format :) I hope that we have a common goal of making clang-format as easy to maintain as we can.

FWIW, I once had the same opinion as you about best doing all parsing as early as possible, but djasper convinced me that the split was a good idea, and in the end, I think it turns out to be significantly less brittle to do more complex annotation in TokenAnnotator. E.g. we now have a lookahead limit of 50, which seems rather arbitrary, while in TokenAnnotator we could simply limit lookahead towards the current UnwrappedLine. Similarly, in TokenAnnotator, we already have all the parens connected, so we could simply look from requires l_paren to the corresponding r_paren and whether the next token is an l_brace. If I can find a bit of time I'll take an attempt at implementing it.

Your commit is in my view a an example of making that maintaining a bit harder, it didn't went through review, had you not posted it here I'd never seen it. LLVM receives to many commits to scan them for changes in clang-format. And as someone who isn't that long involved in clang-format I think there is an overview really missing.

[klimek]

For non-functional clean-ups generally llvm doesn't require pre-commit review - I did communicate here so people involved in the original change wouldn't miss the clean-up. I do agree that what commits to pre-review is a fine line, and usually try to err on the side of pre-review; I'll take your feedback into consideration for future changes.

Regarding a better overview, you're 100% right. This is something we've definitely not been good enough and we need to get better at.

clang/lib/Format/UnwrappedLineParser.h

private:
   void parseSwitch();
   void parseNamespace();
   void parseModuleImport();
   void parseNew();
   void parseAccessSpecifier();
   bool parseEnum();
   bool parseStructLike();
   void parseConcept();
+  bool parseRequires();
   void parseRequiresClause();
   void parseRequiresExpression();
   void parseConstraintExpression();
   void parseJavaEnumBody();
   // Parses a record (aka class) as a top level element. If ParseAsExpr is true,
   // parses the record as a child block, i.e. if the class declaration is an
   // expression.
   void parseRecord(bool ParseAsExpr = false);

clang/lib/Format/UnwrappedLineParser.cpp

case tok::at:
         return;
       default:
         break;
       }
       break;
     case tok::kw_concept:
       parseConcept();
       return;
-    case tok::kw_requires:
-      parseRequiresClause();
+    case tok::kw_requires: {
+      bool Return = parseRequires();
+      if (Return)
         return;
+      break;
+    }
     case tok::kw_enum:
       // Ignore if this is part of "template <enum ...".
       if (Previous && Previous->is(tok::less)) {
         nextToken();
         break;
       }
 
       // parseEnum falls through and does not yet add an unwrapped line as an
if (!FormatTok->Tok.is(tok::equal))
     return;
   nextToken();
   parseConstraintExpression();
   if (FormatTok->Tok.is(tok::semi))
     nextToken();
   addUnwrappedLine();
 }
 
+/// \brief Parses a requires, decides if it is a clause or an expression.
+/// \pre The current token has to be the requires keyword.
+/// \returns If it parsed a clause.
+bool clang::format::UnwrappedLineParser::parseRequires() {
+  assert(FormatTok->Tok.is(tok::kw_requires) && "'requires' expected");
+  auto *PreviousNonComment = FormatTok->getPreviousNonComment();
+
+  auto ProbablyExpressionAfterAmpOrAmpAmp = [PreviousNonComment] {
+    assert(PreviousNonComment->isOneOf(tok::amp, tok::ampamp));
+    // This one is really tricky, since most tokens doesn't have a type yet.
+    // The & or && can be binary operators, then we have a requires
+    // expression. But they also can be r-value overload indicators, then
+    // we have a trailing requires clause. We try to detect the latter and
+    // default to the expressions.
+
+    auto PrevPrev = PreviousNonComment->getPreviousNonComment();
+    if (!PrevPrev) {
+      // No Token is invalid code, just do whatever you want.
+      return true;
+    }
+
+    switch (PrevPrev->Tok.getKind()) {
+    case tok::kw_const:
+      // void foo() const & requires...
+      return false;
+    case tok::r_paren:
+      // We differentiate after the switch.
+      break;
+    default:
+      // Is most definitly an expression.
+      return true;
+    }
+
+    auto RParen = PrevPrev;
+    auto LastParenContent = RParen->getPreviousNonComment();
+
+    if (!LastParenContent) {
+      // No Token is invalid code, just do whatever you want.
+      return true;
+    }
+
+    switch (LastParenContent->Tok.getKind()) {
+    case tok::r_paren:
+      // Nested parens, probably not a clause.
+      return true;
+    case tok::l_paren:
+      // FIXME: We need an annotation on the paren to really know if it is a
+      // function call:
+      // ... foo() && requires ...
+      // or a declaration:
+      // void foo() && requires ...
+      // there is no distinction possible right now. We go for the latter,
+      // because it's more likely to appear in code.
+      return false;
+    case tok::amp:
+    case tok::ampamp:
+    case tok::star:
+      // A function declaration where the parameter name is omitted:
+      // void foo(Type&&) && requires ...
+      return false;
+    case tok::identifier:
+      // We have to look further...
+      break;
+    default:
+      if (LastParenContent->isSimpleTypeSpecifier()) {
+        // Definetly function delcaration.
+        return false;
+      }
+      return true;
+    }
+
+    auto BeforeLastParenContent = LastParenContent->getPreviousNonComment();
+    if (!BeforeLastParenContent) {
+      // No Token is invalid code, just do whatever you want.
+      return true;
+    }
+
+    switch (BeforeLastParenContent->Tok.getKind()) {
+    case tok::l_paren:
+      // FIXME: We need an annotation on the paren to really know if it is a
+      // function call:
+      // ... foo(variable) && requires ...
+      // or a declaration:
+      // void foo(Type /*with omitted*/) && requires ...
+      // there is no distinction possible right now. We go for the former,
+      // because it's more likely to appear in code.
+      return true;
+    case tok::identifier:
+      // Two identifiers is, without macros, a parameter type and value, thus a
+      // clause.
+      return false;
+    default:
+      if (BeforeLastParenContent->isSimpleTypeSpecifier()) {
+        // Definetly function delcaration.
+        return false;
+      }
+      break;
+    }
+    return true;
+  };
+
+  if (PreviousNonComment &&
+      !PreviousNonComment->isOneOf(tok::greater, tok::r_paren, tok::kw_noexcept,
+                                   tok::kw_const,
+                                   TT_RequiresExpressionLBrace) &&
+      (!PreviousNonComment->isOneOf(tok::amp, tok::ampamp) ||
+       ProbablyExpressionAfterAmpOrAmpAmp())) {
+    parseRequiresExpression();
+    return false;
+  }
+  parseRequiresClause();
+  return true;
+}
+
 /// \brief Parses a requires clause.
 /// \pre The current token needs to be the requires keyword.
 /// \sa parseRequiresExpression
 ///
 /// Returns if it either has finished parsing the clause, or it detects, that
 /// the clause is incorrect.
 void UnwrappedLineParser::parseRequiresClause() {
   assert(FormatTok->Tok.is(tok::kw_requires) && "'requires' expected");

clang/unittests/Format/TokenAnnotatorTest.cpp

TEST_F(TokenAnnotatorTest, UnderstandsRequiresClausesAndConcepts) {
   EXPECT_TOKEN(Tokens[13], tok::ampamp, TT_BinaryOperator);
   EXPECT_TOKEN(Tokens[16], tok::ampamp, TT_BinaryOperator);
 
   Tokens = annotate("template <typename T>\n"
                     "concept C = requires(T t) {\n"
                     "  { t.foo() };\n"
                     "} && Bar<T> && Baz<T>;");
   ASSERT_EQ(Tokens.size(), 35u) << Tokens;
+  EXPECT_TOKEN(Tokens[8], tok::kw_requires, TT_RequiresExpression);
+  EXPECT_TOKEN(Tokens[9], tok::l_paren, TT_RequiresExpressionLParen);
+  EXPECT_TOKEN(Tokens[13], tok::l_brace, TT_RequiresExpressionLBrace);
   EXPECT_TOKEN(Tokens[23], tok::ampamp, TT_BinaryOperator);
   EXPECT_TOKEN(Tokens[28], tok::ampamp, TT_BinaryOperator);
 
   Tokens = annotate("template<typename T>\n"
                     "requires C1<T> && (C21<T> || C22<T> && C2e<T>) && C3<T>\n"
                     "struct Foo;");
   ASSERT_EQ(Tokens.size(), 36u) << Tokens;
+  EXPECT_TOKEN(Tokens[5], tok::kw_requires, TT_RequiresClause);
   EXPECT_TOKEN(Tokens[6], tok::identifier, TT_Unknown);
   EXPECT_EQ(Tokens[6]->FakeLParens.size(), 1u);
   EXPECT_TOKEN(Tokens[10], tok::ampamp, TT_BinaryOperator);
   EXPECT_TOKEN(Tokens[16], tok::pipepipe, TT_BinaryOperator);
   EXPECT_TOKEN(Tokens[21], tok::ampamp, TT_BinaryOperator);
   EXPECT_TOKEN(Tokens[27], tok::ampamp, TT_BinaryOperator);
   EXPECT_TOKEN(Tokens[31], tok::greater, TT_TemplateCloser);
   EXPECT_EQ(Tokens[31]->FakeRParens, 1u);
   EXPECT_TRUE(Tokens[31]->ClosesRequiresClause);
 
   Tokens =
       annotate("template<typename T>\n"
                "requires (C1<T> && (C21<T> || C22<T> && C2e<T>) && C3<T>)\n"
                "struct Foo;");
   ASSERT_EQ(Tokens.size(), 38u) << Tokens;
+  EXPECT_TOKEN(Tokens[5], tok::kw_requires, TT_RequiresClause);
   EXPECT_TOKEN(Tokens[7], tok::identifier, TT_Unknown);
   EXPECT_EQ(Tokens[7]->FakeLParens.size(), 1u);
   EXPECT_TOKEN(Tokens[11], tok::ampamp, TT_BinaryOperator);
   EXPECT_TOKEN(Tokens[17], tok::pipepipe, TT_BinaryOperator);
   EXPECT_TOKEN(Tokens[22], tok::ampamp, TT_BinaryOperator);
   EXPECT_TOKEN(Tokens[28], tok::ampamp, TT_BinaryOperator);
   EXPECT_TOKEN(Tokens[32], tok::greater, TT_TemplateCloser);
   EXPECT_EQ(Tokens[32]->FakeRParens, 1u);
   EXPECT_TOKEN(Tokens[33], tok::r_paren, TT_Unknown);
   EXPECT_TRUE(Tokens[33]->ClosesRequiresClause);
+
+  Tokens = annotate("template <typename T>\n"
+                    "void foo(T) noexcept requires Bar<T>;");
+  ASSERT_EQ(Tokens.size(), 18u) << Tokens;
+  EXPECT_TOKEN(Tokens[11], tok::kw_requires, TT_RequiresClause);
+
+  Tokens = annotate("template <typename T>\n"
+                    "struct S {\n"
+                    "  void foo() const requires Bar<T>;\n"
+                    "  void bar() const & requires Baz<T>;\n"
+                    "  void bar() && requires Baz2<T>;\n"
+                    "  void baz() const & noexcept requires Baz<T>;\n"
+                    "  void baz() && noexcept requires Baz2<T>;\n"
+                    "};\n"
+                    "\n"
+                    "void S::bar() const & requires Baz<T> { }");
+  ASSERT_EQ(Tokens.size(), 85u) << Tokens;
+  EXPECT_TOKEN(Tokens[13], tok::kw_requires, TT_RequiresClause);
+  EXPECT_TOKEN(Tokens[25], tok::kw_requires, TT_RequiresClause);
+  EXPECT_TOKEN(Tokens[36], tok::kw_requires, TT_RequiresClause);
+  EXPECT_TOKEN(Tokens[49], tok::kw_requires, TT_RequiresClause);
+  EXPECT_TOKEN(Tokens[61], tok::kw_requires, TT_RequiresClause);
+  EXPECT_TOKEN(Tokens[77], tok::kw_requires, TT_RequiresClause);
+}
+
+TEST_F(TokenAnnotatorTest, UnderstandsRequiresExpressions) {
+  auto Tokens = annotate("bool b = requires(int i) { i + 5; };");
+  ASSERT_EQ(Tokens.size(), 16u) << Tokens;
+  EXPECT_TOKEN(Tokens[3], tok::kw_requires, TT_RequiresExpression);
+  EXPECT_TOKEN(Tokens[4], tok::l_paren, TT_RequiresExpressionLParen);
+  EXPECT_TOKEN(Tokens[8], tok::l_brace, TT_RequiresExpressionLBrace);
+
+  Tokens = annotate("if (requires(int i) { i + 5; }) return;");
+  ASSERT_EQ(Tokens.size(), 17u) << Tokens;
+  EXPECT_TOKEN(Tokens[2], tok::kw_requires, TT_RequiresExpression);
+  EXPECT_TOKEN(Tokens[3], tok::l_paren, TT_RequiresExpressionLParen);
+  EXPECT_TOKEN(Tokens[7], tok::l_brace, TT_RequiresExpressionLBrace);
+
+  Tokens = annotate("if (func() && requires(int i) { i + 5; }) return;");
+  ASSERT_EQ(Tokens.size(), 21u) << Tokens;
+  EXPECT_TOKEN(Tokens[6], tok::kw_requires, TT_RequiresExpression);
+  EXPECT_TOKEN(Tokens[7], tok::l_paren, TT_RequiresExpressionLParen);
+  EXPECT_TOKEN(Tokens[11], tok::l_brace, TT_RequiresExpressionLBrace);
+
+  Tokens = annotate("template <typename T>\n"
+                    "concept C = requires(T T) {\n"
+                    "  requires Bar<T> && Foo<T>;\n"
+                    "};");
+  ASSERT_EQ(Tokens.size(), 28u) << Tokens;
+  EXPECT_TOKEN(Tokens[8], tok::kw_requires, TT_RequiresExpression);
+  EXPECT_TOKEN(Tokens[9], tok::l_paren, TT_RequiresExpressionLParen);
+  EXPECT_TOKEN(Tokens[13], tok::l_brace, TT_RequiresExpressionLBrace);
+  EXPECT_TOKEN(Tokens[14], tok::kw_requires,
+               TT_RequiresClauseInARequiresExpression);
+
+  Tokens = annotate("template <typename T>\n"
+                    "concept C = requires(T T) {\n"
+                    "  { t.func() } -> std::same_as<int>;"
+                    "  requires Bar<T> && Foo<T>;\n"
+                    "};");
+  ASSERT_EQ(Tokens.size(), 43u) << Tokens;
+  EXPECT_TOKEN(Tokens[8], tok::kw_requires, TT_RequiresExpression);
+  EXPECT_TOKEN(Tokens[9], tok::l_paren, TT_RequiresExpressionLParen);
+  EXPECT_TOKEN(Tokens[13], tok::l_brace, TT_RequiresExpressionLBrace);
+  EXPECT_TOKEN(Tokens[29], tok::kw_requires,
+               TT_RequiresClauseInARequiresExpression);
 }
 
 TEST_F(TokenAnnotatorTest, RequiresDoesNotChangeParsingOfTheRest) {
   auto NumberOfAdditionalRequiresClauseTokens = 5u;
   auto NumberOfTokensBeforeRequires = 5u;
 
   auto BaseTokens = annotate("template<typename T>\n"
                              "T Pi = 3.14;");