[clang-format] [PR45218] Fix an issue where < and > and >> in a for loop gets incorrectly interpreted at a TemplateOpener/Closer

[MyDeveloperDay]

Summary

Fix to address https://bugs.llvm.org/show_bug.cgi?id=45218

The <> in the following code means the i < bits and v > in the following code gets incorrectly determined as a TemplateOpener/Closer (see debug output below)

While this became more prevalent after D66332: [clang-format] Fix the bug that joins template closer and > or >> this isn't the root cause, but instead as called out by PR45218 it's more to do with parseAngle() and how it labels < and >

`
for (unsigned i = 0; i < nbits; ++i, bIt.next(), v = v >> 1)
`

This can be seen by the following debug output for the line, where we can see that the <> have the wrong T value.

The tests pass and various directories within LLVM which are currently already clang-formatted don't show any new errors (although that far from exhaustive testing)

M=0 C=0 T=Unknown S=1 B=0 BK=0 P=0 Name=for L=3 PPK=2 FakeLParens= FakeRParens=0 II=0x1e0bf1b7c80 Text='for'
M=0 C=0 T=Unknown S=1 B=0 BK=0 P=23 Name=l_paren L=5 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='('
M=0 C=1 T=Unknown S=0 B=0 BK=0 P=1040 Name=unsigned L=13 PPK=2 FakeLParens=2/0/ FakeRParens=0 II=0x1e0bf1b7fc0 Text='unsigned'
M=0 C=1 T=StartOfName S=1 B=0 BK=0 P=240 Name=identifier L=15 PPK=2 FakeLParens= FakeRParens=0 II=0x1e0bf1f12a0 Text='i'
M=0 C=0 T=BinaryOperator S=1 B=0 BK=0 P=42 Name=equal L=17 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='='
M=0 C=1 T=Unknown S=1 B=0 BK=0 P=44 Name=numeric_constant L=19 PPK=2 FakeLParens= FakeRParens=1 II=0x0 Text='0'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=43 Name=semi L=20 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text=';'
M=0 C=1 T=Unknown S=1 B=0 BK=0 P=40 Name=identifier L=22 PPK=2 FakeLParens=10/ FakeRParens=0 II=0x1e0bf1f12a0 Text='i'
M=0 C=0 T=TemplateOpener S=0 B=0 BK=0 P=50 Name=less L=23 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='<'
M=0 C=1 T=Unknown S=0 B=0 BK=0 P=380 Name=identifier L=28 PPK=2 FakeLParens=0/ FakeRParens=0 II=0x1e0bf1f12d0 Text='nbits'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=283 Name=semi L=29 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text=';'
M=0 C=1 T=UnaryOperator S=1 B=0 BK=0 P=280 Name=plusplus L=32 PPK=2 FakeLParens=0/1/ FakeRParens=0 II=0x0 Text='++'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=340 Name=identifier L=33 PPK=2 FakeLParens= FakeRParens=1 II=0x1e0bf1f12a0 Text='i'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=281 Name=comma L=34 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text=','
M=0 C=1 T=Unknown S=1 B=0 BK=0 P=281 Name=identifier L=38 PPK=2 FakeLParens=0/ FakeRParens=0 II=0x1e0bf1f1300 Text='bIt'
M=0 C=1 T=Unknown S=0 B=0 BK=0 P=430 Name=period L=39 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='.'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=283 Name=identifier L=43 PPK=2 FakeLParens= FakeRParens=0 II=0x1e0bf1f1330 Text='next'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=283 Name=l_paren L=44 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='('
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=319 Name=r_paren L=45 PPK=2 FakeLParens= FakeRParens=1 II=0x0 Text=')'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=281 Name=comma L=46 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text=','
M=0 C=1 T=Unknown S=1 B=0 BK=0 P=281 Name=identifier L=48 PPK=2 FakeLParens=2/ FakeRParens=0 II=0x1e0bf1f1360 Text='v'
M=0 C=0 T=BinaryOperator S=1 B=0 BK=0 P=282 Name=equal L=50 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='='
M=0 C=1 T=Unknown S=1 B=0 BK=0 P=284 Name=identifier L=52 PPK=2 FakeLParens= FakeRParens=3 II=0x1e0bf1f1360 Text='v'
M=0 C=0 T=TemplateCloser S=0 B=0 BK=0 P=290 Name=greater L=53 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='>'
M=0 C=0 T=BinaryOperator S=0 B=0 BK=0 P=50 Name=greater L=54 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='>'
M=0 C=1 T=Unknown S=1 B=0 BK=0 P=50 Name=numeric_constant L=56 PPK=2 FakeLParens= FakeRParens=2 II=0x0 Text='1'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=43 Name=r_paren L=57 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text=')'

This fix tries to avoid that issue by determining that a ";" between the < and > would not be a template (I couldn't think of an example where that would be the case, but I'm sure there are..

Afterwards the token are interpreted correctly for this line. (

M=0 C=0 T=Unknown S=1 B=0 BK=0 P=0 Name=for L=3 PPK=2 FakeLParens= FakeRParens=0 II=0x1c891ac41b0 Text='for'
M=0 C=0 T=Unknown S=1 B=0 BK=0 P=23 Name=l_paren L=5 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='('
M=0 C=1 T=Unknown S=0 B=0 BK=0 P=1040 Name=unsigned L=13 PPK=2 FakeLParens=2/0/ FakeRParens=0 II=0x1c891ac44f0 Text='unsigned'
M=0 C=1 T=StartOfName S=1 B=0 BK=0 P=240 Name=identifier L=15 PPK=2 FakeLParens= FakeRParens=0 II=0x1c891abce10 Text='i'
M=0 C=0 T=BinaryOperator S=1 B=0 BK=0 P=42 Name=equal L=17 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='='
M=0 C=1 T=Unknown S=1 B=0 BK=0 P=44 Name=numeric_constant L=19 PPK=2 FakeLParens= FakeRParens=1 II=0x0 Text='0'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=43 Name=semi L=20 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text=';'
M=0 C=1 T=Unknown S=1 B=0 BK=0 P=40 Name=identifier L=22 PPK=2 FakeLParens=10/ FakeRParens=0 II=0x1c891abce10 Text='i'
M=0 C=0 T=BinaryOperator S=1 B=0 BK=0 P=50 Name=less L=24 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='<'
M=0 C=1 T=Unknown S=1 B=0 BK=0 P=50 Name=identifier L=30 PPK=2 FakeLParens= FakeRParens=1 II=0x1c891abce40 Text='nbits'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=43 Name=semi L=31 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text=';'
M=0 C=1 T=UnaryOperator S=1 B=0 BK=0 P=40 Name=plusplus L=34 PPK=2 FakeLParens=0/1/ FakeRParens=0 II=0x0 Text='++'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=100 Name=identifier L=35 PPK=2 FakeLParens= FakeRParens=1 II=0x1c891abce10 Text='i'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=41 Name=comma L=36 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text=','
M=0 C=1 T=Unknown S=1 B=0 BK=0 P=41 Name=identifier L=40 PPK=2 FakeLParens=0/ FakeRParens=0 II=0x1c891abce70 Text='bIt'
M=0 C=1 T=Unknown S=0 B=0 BK=0 P=190 Name=period L=41 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='.'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=43 Name=identifier L=45 PPK=2 FakeLParens= FakeRParens=0 II=0x1c891abcea0 Text='next'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=43 Name=l_paren L=46 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='('
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=79 Name=r_paren L=47 PPK=2 FakeLParens= FakeRParens=1 II=0x0 Text=')'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=41 Name=comma L=48 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text=','
M=0 C=1 T=Unknown S=1 B=0 BK=0 P=41 Name=identifier L=50 PPK=2 FakeLParens=2/ FakeRParens=0 II=0x1c891abced0 Text='v'
M=0 C=0 T=BinaryOperator S=1 B=0 BK=0 P=42 Name=equal L=52 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='='
M=0 C=1 T=Unknown S=1 B=0 BK=0 P=44 Name=identifier L=54 PPK=2 FakeLParens=10/ FakeRParens=0 II=0x1c891abced0 Text='v'
M=0 C=0 T=BinaryOperator S=1 B=0 BK=0 P=50 Name=greater L=56 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='>'
M=0 C=0 T=BinaryOperator S=0 B=0 BK=0 P=50 Name=greater L=57 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text='>'
M=0 C=1 T=Unknown S=1 B=0 BK=0 P=50 Name=numeric_constant L=59 PPK=2 FakeLParens= FakeRParens=4 II=0x0 Text='1'
M=0 C=0 T=Unknown S=0 B=0 BK=0 P=43 Name=r_paren L=60 PPK=2 FakeLParens= FakeRParens=0 II=0x0 Text=')'

[MyDeveloperDay]

Update for pre-merge checks

[rmansfield]

Couple examples:

void foo(int x) {
for (unsigned int i = 0; i < x >> 1; i++) { }
}

and

int i = 0;

if (i < x >> 1) {}

}

[MyDeveloperDay]

In D79293#2016410, @rmansfield wrote:

Couple examples:

void foo(int x) {
for (unsigned int i = 0; i < x >> 1; i++) { }
}

and

int i = 0;

if (i < x >> 1) {}

}

I don't deny there are places where this will fail, but that is clang-format all over its a series of rules or the arrangement of token to produce the desired result

I think we also have to say.. "who writes code like this" ;-)

[rmansfield]

They're overly reduced examples ;) but embedded programmers tend to make heavy use of shift operators, including within for loops and if stmts

[MyDeveloperDay]

Add more test cases to try to ensure TemplateOpener/Closer type isn't assigned incorrectly.

[curdeius]

This fix tries to avoid that issue by determining that a ";" between the < and > would not be a template (I couldn't think of an example where that would be the case, but I'm sure there are..

For what is worth, with lambdas in unevaluated context (C++20), you can get a semicolon between template opener/closer easily:

some_templated_type<decltype([](int i) { return i; })>

But I'm not sure if it's something that may break anything here.

Another idea in which a semicolon occurs between <> would be a macro X(;).

clang/lib/Format/TokenAnnotator.cpp

40

I know you haven't changed this, but...
Static function (internal linkage) in anonymous namespace?

46

Ditto (static).

1986

There should be no comment, it's the ending brace of a class.

[MyDeveloperDay]

Remove tok::semi check as its not actually needed now we label the < and > correctly

[MyDeveloperDay]

For what is worth, with lambdas in unevaluated context (C++20), you can get a semicolon between template opener/closer easily:

I actually no longer need the check for the semi if the TemplateOpener/Closer is correctly labelled

clang/lib/Format/TokenAnnotator.cpp

40

I believe the guideline is to not use anonymous namespaces for functions

https://llvm.org/docs/CodingStandards.html#anonymous-namespaces

(not my personal preference mind)

[krasimir]

I think these examples are too ambiguous for clang-format to try and format correctly.
Sadly for C++, correctly distinguishing between >>, the binary operator, and >>, the sequence of two closing template brackets, requires semantic analysis, I believe.
Such heuristics are very brittle, e.g. this patch fixes if (i < x >> 1) but regresses this:

% cat ~/test.cc
bool f() {
  if (w<u<v<x>>, 1>::t) return true;
}
% bin/clang-format ~/test.cc 
bool f() {
  if (w < u < v < x >>, 1 > ::t)
    return true;
}
%

We can of course enumerate a fixed set of patterns where we apply such fixes fixes, but I'm not sure how much is that worth.
I think clang-format's current approach to choose to interpret as a template, even if silly at times, is reasonable.
A way to deal with if (i < x >> 1) is to give clang-format a hint e.g. if (i < (x >> 1)). You can ~always surround an expression with braces, but if clang-format guesses incorrectly two template closers as a binary operator, I can't think of a good way to force it to stop.

[MyDeveloperDay]

Handle addition case

if (w<u<v<x>>, 1>::t) return true;

I do tend to agree with you, but at least for this case I think it can also be handled. It could of course just be the tip of the iceberg, but let me at least update the patch here to cover those cases.

[hans]

I suppose this is just piling on heuristics, but I guess it fixes the reported bug. Krasimir, what do you think?

[MyDeveloperDay]

Better solution here D86581: [clang-format] Handle shifts within conditions

clang/lib/Format/TokenAnnotator.cpp

 /// Because getFormattingLangOpts() always lexes source code as
 /// Objective-C++, C++ keywords like \c new and \c delete are
 /// lexed as tok::kw_*, not tok::identifier, even for Objective-C.
 ///
 /// For Objective-C and Objective-C++, both identifiers and keywords
 /// are valid inside @selector(...) (or a macro which
 /// invokes @selector(...)). So, we allow treat any identifier or
 /// keyword as a potential Objective-C selector component.
 static bool canBeObjCSelectorComponent(const FormatToken &Tok) {
   return Tok.Tok.getIdentifierInfo() != nullptr;
 }
 
 /// With `Left` being '(', check if we're at either `[...](` or
 /// `[...]<...>(`, where the [ opens a lambda capture list.
 static bool isLambdaParameterList(const FormatToken *Left) {
   // Skip <...> if present.
   if (Left->Previous && Left->Previous->is(tok::greater) &&
       Left->Previous->MatchingParen &&
       Left->Previous->MatchingParen->is(TT_TemplateOpener))
     Left = Left->Previous->MatchingParen;
 
   // Check for `[...]`.
   return Left->Previous && Left->Previous->is(tok::r_square) &&
while (CurrentToken) {
         //   map<key, value>
         //   msg < item: data >
         //   msg: < item: data >
         // In TT_TextProto, map<key, value> does not occur.
         if (Style.Language == FormatStyle::LK_TextProto ||
             (Style.Language == FormatStyle::LK_Proto && Left->Previous &&
              Left->Previous->isOneOf(TT_SelectorName, TT_DictLiteral)))
           CurrentToken->Type = TT_DictLiteral;
-        else
+        // In if/for/while  (i < x >> 1) ensure we don't see the <> as
+        // TemplateOpener/Closer
+        else if (CurrentToken->Next && CurrentToken->Next->is(tok::greater) &&
+                 CurrentToken->Next->Next &&
+                 !CurrentToken->Next->Next->isOneOf(
+                     tok::l_paren, tok::coloncolon, tok::comma) &&
+                 Line.First->isOneOf(tok::kw_if, tok::kw_for, tok::kw_while)) {
+          Left->Type = TT_BinaryOperator;
+          return false;
+        } else
           CurrentToken->Type = TT_TemplateCloser;
         next();
         return true;
       }
       if (CurrentToken->is(tok::question) &&
           Style.Language == FormatStyle::LK_Java) {
         next();
         continue;
if (Style.isCSharp() && CurrentToken->is(tok::question)) {
         Current.Type = TT_CSharpNullConditionalLSquare;
         return;
       }
     }
 
     if (Style.Language == FormatStyle::LK_JavaScript) {
       if (Current.is(tok::exclaim)) {
         if (Current.Previous &&
-            (Keywords.IsJavaScriptIdentifier(
-                 *Current.Previous, /* AcceptIdentifierName= */ true) ||
+            (Keywords.IsJavaScriptIdentifier(*Current.Previous,
+                                             /*AcceptIdentifierName=*/true) ||
              Current.Previous->isOneOf(
                  tok::kw_namespace, tok::r_paren, tok::r_square, tok::r_brace,
                  Keywords.kw_type, Keywords.kw_get, Keywords.kw_set) ||
              Current.Previous->Tok.isLiteral())) {
           Current.Type = TT_JsNonNullAssertion;
           return;
         }
         if (Current.Next &&
private:
   bool AutoFound;
   const AdditionalKeywords &Keywords;
 
   // Set of "<" tokens that do not open a template parameter list. If parseAngle
   // determines that a specific token can't be a template opener, it will make
   // same decision irrespective of the decisions for tokens leading up to it.
   // Store this information to prevent this from causing exponential runtime.
   llvm::SmallPtrSet<FormatToken *, 16> NonTemplateLess;
 };
 
 static const int PrecedenceUnaryOperator = prec::PointerToMember + 1;
 static const int PrecedenceArrowAndPeriod = prec::PointerToMember + 2;
 
 /// Parses binary expressions by inserting fake parenthesis based on
 /// operator precedence.
 class ExpressionParser {
 public:
while (Current &&
       Current = Current->Next;
   }
 
   const FormatStyle &Style;
   const AdditionalKeywords &Keywords;
   FormatToken *Current;
 };
 
-} // end anonymous namespace
+} // namespace
 
 void TokenAnnotator::setCommentLineLevels(
     SmallVectorImpl<AnnotatedLine *> &Lines) {
   const AnnotatedLine *NextNonCommentLine = nullptr;
   for (SmallVectorImpl<AnnotatedLine *>::reverse_iterator I = Lines.rbegin(),
                                                           E = Lines.rend();
        I != E; ++I) {
     bool CommentLine = true;

clang/unittests/Format/FormatTest.cpp

verifyFormat("template <typename... Types>\n"
                "typename enable_if<0 < sizeof...(Types)>::type Foo() {}");
 
   verifyFormat("aaaaaaaaaaaaaaaaaaaaaaaaaaaa(\n"
                "    aaaaaaaaaaaaaaaaaaaaaaaaaaaaa >> aaaaa);",
                getLLVMStyleWithColumns(60));
   verifyFormat("static_assert(is_convertible<A &&, B>::value, \"AAA\");");
   verifyFormat("Constructor(A... a) : a_(X<A>{std::forward<A>(a)}...) {}");
   verifyFormat("< < < < < < < < < < < < < < < < < < < < < < < < < < < < < <");
+
+  verifyFormat("some_templated_type<decltype([](int i) { return i; })>");
+}
+
+TEST_F(FormatTest, UnderstandsShiftOperators) {
+  verifyFormat("if (i < x >> 1)");
+  verifyFormat("while (i < x >> 1)");
+  verifyFormat("for (unsigned i = 0; i < i; ++i, v = v >> 1)");
+  verifyFormat("for (unsigned i = 0; i < x >> 1; ++i, v = v >> 1)");
+  verifyFormat(
+      "for (std::vector<int>::iterator i = 0; i < x >> 1; ++i, v = v >> 1)");
+  verifyFormat("Foo.call<Bar<Function>>()");
+  verifyFormat("if (Foo.call<Bar<Function>>() == 0)");
+  verifyFormat("for (std::vector<std::pair<int>>::iterator i = 0; i < x >> 1; "
+               "++i, v = v >> 1)");
+  verifyFormat("if (w<u<v<x>>, 1>::t)");
 }
 
 TEST_F(FormatTest, BitshiftOperatorWidth) {
   EXPECT_EQ("int a = 1 << 2; /* foo\n"
             "                   bar */",
             format("int    a=1<<2;  /* foo\n"
                    "                   bar */"));