[clang-format] Fix whitespace counting stuff

[sstwcw]

Summary

The current way of counting whitespace would count backticks as
whitespace. For Verilog stuff we need backticks to be handled
correctly. For JavaScript the current way is to compare the entire
token text to see if it's a backtick. However, when the backtick is the
first token following an escaped newline, the escaped newline will be
part of the tok::unknown token. Verilog has macros and escaped newlines
unlike JavaScript. So we can't regard an entire tok::unknown token as
whitespace. Previously, the start of every token would be matched for
newlines. Now, it is all whitespace instead of just newlines.

The column counting problem has already been fixed for JavaScript in
e71b4cbdd140f059667f84464bd0ac0ebc348387 by counting columns elsewhere.

[HazardyKnusperkeks]

clang/lib/Format/FormatTokenLexer.cpp

843

Can you add some documentation?

872

I'd put (and search while reading) the comment after the case.

875–876

Please verify your assumption with an assert.

[owenpan]

Is this patch NFC?

clang/lib/Format/FormatTokenLexer.cpp

863–871

I'd replace the switch with if (isspace(Cur[0])) ... else if (Cur[1] == '\n' ...) ....

913

922–923

\r\n is a newline on Windows.

932

949–961

Don't you need to look ahead for a ??/?

[MyDeveloperDay]

Is there any way you could add a unit test for this?

[sstwcw]

• address review comments

[sstwcw]

This patch is not NFC. But there would not be change in behavior if the
input is valid C as far as I know.

input:
#define LIST \
`ENTRY \
`ENTRY
output before, note extra line:
#define LIST                                                                   \
                                                                               \
  `ENTRY \
`ENTRY
output after:
#define LIST \
`ENTRY \
`ENTRY

I don't know how I would add a test for this.

The tests in D124749 depend on this though.

clang/lib/Format/FormatTokenLexer.cpp

843

Is this comment enough?

922–923

I added a comment to make it clear the code is correct.

949–961

It has to be ??/. Now there's an assertion.

[HazardyKnusperkeks]

clang/lib/Format/FormatTokenLexer.cpp

843

Maybe some reasoning?

Also I think NewLen shouldn't be bigger than FormatTok->TokenText.size() should it? Add an assert and a comment on the restriction.

[sstwcw]

• add comment

[HazardyKnusperkeks]

Can there be a test case, not related to Verilog? Or do we need to wait until you pump up the support for that?

[kevcadieux]

@sstwcw @HazardyKnusperkeks : this change introduced a regression in one of the clang format unit tests. I fixed it in the revision below. Could anyone please take a look / approve this revision to unblock Windows debug builds? Thanks!

https://reviews.llvm.org/D128786

clang/lib/Format/FormatTokenLexer.h

private:
   void handleCSharpVerbatimAndInterpolatedStrings();
 
   void tryParsePythonComment();
 
   bool tryMerge_TMacro();
 
   bool tryMergeConflictMarkers();
 
+  void truncateToken(size_t NewLen);
+
   FormatToken *getStashedToken();
 
   FormatToken *getNextToken();
 
   FormatToken *FormatTok;
   bool IsFirstToken;
   std::stack<LexerState> StateStack;
   unsigned Column;

clang/lib/Format/FormatTokenLexer.cpp

FormatToken *FormatTokenLexer::getStashedToken() {
   FormatTok->WhitespaceRange = SourceRange(TokLocation, TokLocation);
   FormatTok->TokenText = TokenText;
   FormatTok->ColumnWidth = 1;
   FormatTok->OriginalColumn = OriginalColumn + 1;
 
   return FormatTok;
 }
 
+/// Truncate the current token to the new length and make the lexer continue
+/// from the end of the truncated token. Used for other languages that have
+/// different token boundaries, like JavaScript in which a comment ends at a
+/// line break regardless of whether the line break follows a backslash. Also
+/// used to set the lexer to the end of whitespace if the lexer regards
+/// whitespace and an unrecognized symbol as one token.
+void FormatTokenLexer::truncateToken(size_t NewLen) {
+  assert(NewLen <= FormatTok->TokenText.size());
+  resetLexer(SourceMgr.getFileOffset(Lex->getSourceLocation(
+      Lex->getBufferLocation() - FormatTok->TokenText.size() + NewLen)));
+  FormatTok->TokenText = FormatTok->TokenText.substr(0, NewLen);
+  FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
+      FormatTok->TokenText, FormatTok->OriginalColumn, Style.TabWidth,
+      Encoding);
+  FormatTok->Tok.setLength(NewLen);
+}
+
+/// Count the length of leading whitespace in a token.
+static size_t countLeadingWhitespace(StringRef Text) {
+  // Basically counting the length matched by this regex.
+  // "^([\n\r\f\v \t]|(\\\\|\\?\\?/)[\n\r])+"
+  // Directly using the regex turned out to be slow. With the regex
+  // version formatting all files in this directory took about 1.25
+  // seconds. This version took about 0.5 seconds.
+  const char *Cur = Text.begin();
+  while (Cur < Text.end()) {
+    if (isspace(Cur[0])) {
+      ++Cur;
+    } else if (Cur[0] == '\\' && (Cur[1] == '\n' || Cur[1] == '\r')) {
+      // A '\' followed by a newline always escapes the newline, regardless
+      // of whether there is another '\' before it.
+      // The source has a null byte at the end. So the end of the entire input
+      // isn't reached yet. Also the lexer doesn't break apart an escaped
+      // newline.
+      assert(Text.end() - Cur >= 2);
+      Cur += 2;
+    } else if (Cur[0] == '?' && Cur[1] == '?' && Cur[2] == '/' &&
+               (Cur[3] == '\n' || Cur[3] == '\r')) {
+      // Newlines can also be escaped by a '?' '?' '/' trigraph. By the way, the
+      // characters are quoted individually in this comment because if we write
+      // them together some compilers warn that we have a trigraph in the code.
+      assert(Text.end() - Cur >= 4);
+      Cur += 4;
+    } else {
+      break;
+    }
+  }
+  return Cur - Text.begin();
+}
+
 FormatToken *FormatTokenLexer::getNextToken() {
   if (StateStack.top() == LexerState::TOKEN_STASHED) {
     StateStack.pop();
     return getStashedToken();
   }
 
   FormatTok = new (Allocator.Allocate()) FormatToken;
   readRawToken(*FormatTok);
   SourceLocation WhitespaceStart =
       FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
   FormatTok->IsFirst = IsFirstToken;
   IsFirstToken = false;
 
   // Consume and record whitespace until we find a significant token.
+  // Some tok::unknown tokens are not just whitespace, e.g. whitespace
+  // followed by a symbol such as backtick. Those symbols may be
+  // significant in other languages.
   unsigned WhitespaceLength = TrailingWhitespace;
-  while (FormatTok->is(tok::unknown)) {
-    StringRef Text = FormatTok->TokenText;
-    auto EscapesNewline = [&](int pos) {
-      // A '\r' here is just part of '\r\n'. Skip it.
-      if (pos >= 0 && Text[pos] == '\r')
-        --pos;
-      // See whether there is an odd number of '\' before this.
-      // FIXME: This is wrong. A '\' followed by a newline is always removed,
-      // regardless of whether there is another '\' before it.
-      // FIXME: Newlines can also be escaped by a '?' '?' '/' trigraph.
-      unsigned count = 0;
-      for (; pos >= 0; --pos, ++count)
-        if (Text[pos] != '\\')
-          break;
-      return count & 1;
-    };
-    // FIXME: This miscounts tok:unknown tokens that are not just
-    // whitespace, e.g. a '`' character.
+  while (FormatTok->isNot(tok::eof)) {
+    auto LeadingWhitespace = countLeadingWhitespace(FormatTok->TokenText);
+    if (LeadingWhitespace == 0)
+    if (LeadingWhitespace < FormatTok->TokenText.size())
+      truncateToken(LeadingWhitespace);
+    StringRef Text = FormatTok->TokenText;
+    bool InEscape = false;
     for (int i = 0, e = Text.size(); i != e; ++i) {
       switch (Text[i]) {
+      case '\r':
+        // If this is a CRLF sequence, break here and the LF will be handled on
+        // the next loop iteration. Otherwise, this is a single Mac CR, treat it
+        // the same as a single LF.
+        if (i + 1 < e && Text[i + 1] == '\n')
+          break;
+        LLVM_FALLTHROUGH;
       case '\n':
         ++FormatTok->NewlinesBefore;
-        FormatTok->HasUnescapedNewline = !EscapesNewline(i - 1);
-        FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
-        Column = 0;
-        break;
-      case '\r':
+        if (!InEscape)
+          FormatTok->HasUnescapedNewline = true;
+        else
+          InEscape = false;
         FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
         Column = 0;
         break;
       case '\f':
       case '\v':
         Column = 0;
         break;
       case ' ':
         ++Column;
         break;
       case '\t':
         Column +=
             Style.TabWidth - (Style.TabWidth ? Column % Style.TabWidth : 0);
         break;
       case '\\':
-        if (i + 1 == e || (Text[i + 1] != '\r' && Text[i + 1] != '\n'))
-          FormatTok->setType(TT_ImplicitStringLiteral);
+      case '?':
+      case '/':
+        // The text was entirely whitespace when this loop was entered. Thus
+        // this has to be an escape sequence.
+        assert(Text.substr(i, 2) == "\\\r" || Text.substr(i, 2) == "\\\n" ||
+               Text.substr(i, 4) == "\?\?/\r" ||
+               Text.substr(i, 4) == "\?\?/\n" ||
+               (i >= 1 && (Text.substr(i - 1, 4) == "\?\?/\r" ||
+                           Text.substr(i - 1, 4) == "\?\?/\n")) ||
+               (i >= 2 && (Text.substr(i - 2, 4) == "\?\?/\r" ||
+                           Text.substr(i - 2, 4) == "\?\?/\n")));
+        InEscape = true;
         break;
       default:
-        FormatTok->setType(TT_ImplicitStringLiteral);
+        // This shouldn't happen.
+        assert(false);
         break;
       }
-      if (FormatTok->getType() == TT_ImplicitStringLiteral)
-        break;
     }
-
-    if (FormatTok->is(TT_ImplicitStringLiteral))
-      break;
-    WhitespaceLength += FormatTok->Tok.getLength();
-
+    WhitespaceLength += Text.size();
     readRawToken(*FormatTok);
   }
 
+  if (FormatTok->is(tok::unknown))
+    FormatTok->setType(TT_ImplicitStringLiteral);
+
   // JavaScript and Java do not allow to escape the end of the line with a
   // backslash. Backslashes are syntax errors in plain source, but can occur in
   // comments. When a single line comment ends with a \, it'll cause the next
   // line of code to be lexed as a comment, breaking formatting. The code below
   // finds comments that contain a backslash followed by a line break, truncates
   // the comment token at the backslash, and resets the lexer to restart behind
   // the backslash.
   if ((Style.isJavaScript() || Style.Language == FormatStyle::LK_Java) &&
       FormatTok->is(tok::comment) && FormatTok->TokenText.startswith("//")) {
     size_t BackslashPos = FormatTok->TokenText.find('\\');
     while (BackslashPos != StringRef::npos) {
       if (BackslashPos + 1 < FormatTok->TokenText.size() &&
           FormatTok->TokenText[BackslashPos + 1] == '\n') {
-        const char *Offset = Lex->getBufferLocation();
-        Offset -= FormatTok->TokenText.size();
-        Offset += BackslashPos + 1;
-        resetLexer(SourceMgr.getFileOffset(Lex->getSourceLocation(Offset)));
-        FormatTok->TokenText = FormatTok->TokenText.substr(0, BackslashPos + 1);
-        FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
-            FormatTok->TokenText, FormatTok->OriginalColumn, Style.TabWidth,
-            Encoding);
+        truncateToken(BackslashPos + 1);
         break;
       }
       BackslashPos = FormatTok->TokenText.find('\\', BackslashPos + 1);
     }
   }
 
-  // In case the token starts with escaped newlines, we want to
-  // take them into account as whitespace - this pattern is quite frequent
-  // in macro definitions.
-  // FIXME: Add a more explicit test.
-  while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\') {
-    unsigned SkippedWhitespace = 0;
-    if (FormatTok->TokenText.size() > 2 &&
-        (FormatTok->TokenText[1] == '\r' && FormatTok->TokenText[2] == '\n')) {
-      SkippedWhitespace = 3;
-    } else if (FormatTok->TokenText[1] == '\n') {
-      SkippedWhitespace = 2;
-    } else {
-      break;
-    }
-
-    ++FormatTok->NewlinesBefore;
-    WhitespaceLength += SkippedWhitespace;
-    FormatTok->LastNewlineOffset = SkippedWhitespace;
-    Column = 0;
-    FormatTok->TokenText = FormatTok->TokenText.substr(SkippedWhitespace);
-  }
-
   FormatTok->WhitespaceRange = SourceRange(
       WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
 
   FormatTok->OriginalColumn = Column;
 
   TrailingWhitespace = 0;
   if (FormatTok->is(tok::comment)) {
     // FIXME: Add the trimmed whitespace to Column.