[Lexer] Finding beginning of token with escaped new line

[idlecode]

Summary

Lexer::GetBeginningOfToken produced invalid location when
backtracking across escaped new lines.

This fixes PR26228

[alexfh]

lib/Lex/Lexer.cpp

462

We only care about two specific sequences here: \\\r\n or \\\n, not a backslash followed by arbitrary whitespace.

unittests/Lex/LexerTest.cpp

380

LLVM doesn't use "almost always auto" style. See http://llvm.org/docs/CodingStandards.html#use-auto-type-deduction-to-make-code-more-readable

381

Variable names should start with a capital letter: TextToLex. Same elsewhere.

396

Please clang-format.

[idlecode]

lib/Lex/Lexer.cpp

462

I just saw that some functions (e.g. line 1285 in this file) accept whitespaces between escape character and new line. How about now?

[idlecode]

Addressed Alexander's comments

[alexfh]

lib/Lex/Lexer.cpp

462

Indeed, both clang and gcc accept whitespace between the backslash and the newline character and issue a diagnostic: https://godbolt.org/g/PUCTzF.

This should probably be done similar to Lexer::getEscapedNewLineSize, but in reverse:

assert(isVerticalWhitespace(*P));
--P;
if (P >= BufferStart && isVerticalWhitespace(*P) && *P != P[1]) // Skip the second character of `\r\n` or `\n\r`.
  --P;
// Clang allows horizontal whitespace between backslash and new-line with a warning. Skip it.
while (P >= BufferStart && isHorizontalWhitespace(*P))
  --P;
return P >= BufferStart && *P == '\\';

I'd add a bunch of tests for this function specifically:

<backslash><\r> -> true
<backslash><\n> -> true
<backslash><\r><\n> -> true
<backslash><\n><\r> -> true
<backslash><space><tab><\v><\f><\r> -> true
<backslash><space><tab><\v><\f><\r><\n> -> true
<backslash><\r><\r> -> false
<backslash><\r><\r><\n> -> false
<backslash><\n><\n> -> false

[alexfh]

Paweł, are you planning to finish this patch?

[idlecode]

Oh, sorry about this - I forgot. I will send patch during this weekend

[alexfh]

In D30748#750626, @idlecode wrote:

Oh, sorry about this - I forgot. I will send patch during this weekend

No worries, I just stumbled upon the bug and recalled that there had been a patch to fix it.

[idlecode]

Added tests for isNewLineEscaped - this fixed some corner cases

[alexfh]

Sorry for the delay, I was on vacation.

This looks much better now, thanks! A few more comments though.

lib/Lex/Lexer.cpp

461

The way the function is exposed to the test may lead to confusion. I'd either properly declare it in the header (and place it in a namespace, if it is not yet) or at least leave a comment here that the function is not static, since it needs to be exposed to the test.

475

nit: Placing the Str > BufferStart first would make it more obvious that Str can be safely dereferenced.

unittests/Lex/LexerTest.cpp

378–393

I would better unroll the loop:

auto endsWithEscapedNewline = [] (const char *S) {
  return isNewLineEscaped(S, S + strlen(S) - 1);
};
EXPECT_TRUE(endsWithEscapedNewline("\\\r"));
EXPECT_TRUE(endsWithEscapedNewline("\\\n"));
...
EXPECT_FALSE(endsWithEscapedNewline("\\\r\r"));
...

This would simplify the test and make EXPECT_* macro output sufficient to detect failing patterns without any clarifying messages.

[idlecode]

lib/Lex/Lexer.cpp

461

Ok, I have made isNewLineEscaped a static method of Lexer - in Lexer.h there were no global function declaration and I didn't like the idea of introducing one.
I would make it protected/private member but it have to be visible to unit tests (and introducing friend classes just for this method doesn't seem worth it).

[idlecode]

Applied clang-format

[alexfh]

Looks good with one nit.

Do you need someone to commit the patch for you after you address the comment?

lib/Lex/Lexer.cpp

469–477

The logic is hard to get here. I'd use a single if and reverse the condition to get rid of the continues:

if (isVerticalWhitespace(*LexStart) && !Lexer::isNewLineEscaped(BufStart, LexStart)) {
  ++LexStart;
  break;
}

[idlecode]

I don't have commit rights yet so I would be grateful for help in this matter :)

lib/Lex/Lexer.cpp

469–477

Yes, I know - I thought that more vertical code composition would help

[idlecode]

Redability fix in findBeginningOfLine

include/clang/Lex/Lexer.h

static SourceLocation findLocationAfterToken(SourceLocation loc,
                                          tok::TokenKind TKind,
                                          const SourceManager &SM,
                                          const LangOptions &LangOpts,
                                          bool SkipTrailingWhitespaceAndNewLine);
 
   /// \brief Returns true if the given character could appear in an identifier.
   static bool isIdentifierBodyChar(char c, const LangOptions &LangOpts);
 
+  /// \brief Checks whether new line pointed by Str is preceded by escape sequence.
+  static bool isNewLineEscaped(const char *BufferStart, const char *Str);
+
   /// getCharAndSizeNoWarn - Like the getCharAndSize method, but does not ever
   /// emit a warning.
   static inline char getCharAndSizeNoWarn(const char *Ptr, unsigned &Size,
                                           const LangOptions &LangOpts) {
     // If this is not a trigraph and not a UCN or escaped newline, return
     // quickly.
     if (isObviouslySimpleCharacter(Ptr[0])) {
       Size = 1;

lib/Lex/Lexer.cpp

bool Lexer::getRawToken(SourceLocation Loc, Token &Result,
   Lexer TheLexer(SM.getLocForStartOfFile(LocInfo.first), LangOpts,
                  Buffer.begin(), StrData, Buffer.end());
   TheLexer.SetCommentRetentionState(true);
   TheLexer.LexFromRawLexer(Result);
   return false;
 }
 
 /// Returns the pointer that points to the beginning of line that contains
 /// the given offset, or null if the offset if invalid.
 static const char *findBeginningOfLine(StringRef Buffer, unsigned Offset) {
   const char *BufStart = Buffer.data();
   if (Offset >= Buffer.size())
     return nullptr;
-  const char *StrData = BufStart + Offset;
 
-  if (StrData[0] == '\n' || StrData[0] == '\r')
-    return StrData;
+  const char *LexStart = BufStart + Offset;
+  for (; LexStart != BufStart; --LexStart) {
+    if (!isVerticalWhitespace(LexStart[0]))
+      continue;
+
+    if (Lexer::isNewLineEscaped(BufStart, LexStart))
+      continue;
 
-  const char *LexStart = StrData;
-  while (LexStart != BufStart) {
-    if (LexStart[0] == '\n' || LexStart[0] == '\r') {
-      ++LexStart;
-      break;
-    }
-
-    --LexStart;
-  }
+    // LexStart should point at first character of logical line.
   return LexStart;
 }
 
 static SourceLocation getBeginningOfFileToken(SourceLocation Loc,
                                               const SourceManager &SM,
                                               const LangOptions &LangOpts) {
   assert(Loc.isFileID());
   std::pair<FileID, unsigned> LocInfo = SM.getDecomposedLoc(Loc);
   if (LocInfo.first.isInvalid())
     return Loc;
-  
   bool Invalid = false;
   StringRef Buffer = SM.getBufferData(LocInfo.first, &Invalid);
   if (Invalid)
     return Loc;
 
   // Back up from the current location until we hit the beginning of a line
   // (or the buffer). We'll relex from that point.
   const char *StrData = Buffer.data() + LocInfo.second;
   const char *LexStart = findBeginningOfLine(Buffer, LocInfo.second);
   if (!LexStart || LexStart == StrData)
     return Loc;
-  
   // Create a lexer starting at the beginning of this token.
   SourceLocation LexerStartLoc = Loc.getLocWithOffset(-LocInfo.second);
   Lexer TheLexer(LexerStartLoc, LangOpts, Buffer.data(), LexStart,
                  Buffer.end());
   TheLexer.SetCommentRetentionState(true);
-  
   // Lex tokens until we find the token that contains the source location.
   Token TheTok;
   do {
     TheLexer.LexFromRawLexer(TheTok);
-    
     if (TheLexer.getBufferLocation() > StrData) {
       // Lexing this token has taken the lexer past the source location we're
       // looking for. If the current token encompasses our source location,
       // return the beginning of that token.
       if (TheLexer.getBufferLocation() - TheTok.getLength() <= StrData)
         return TheTok.getLocation();
-      
       // We ended up skipping over the source location entirely, which means
       // that it points into whitespace. We're done here.
       break;
     }
   } while (TheTok.getKind() != tok::eof);
-  
   // We've passed our source location; just return the original source location.
   return Loc;
 }
 
 SourceLocation Lexer::GetBeginningOfToken(SourceLocation Loc,
                                           const SourceManager &SM,
                                           const LangOptions &LangOpts) {
   if (Loc.isFileID())
     return getBeginningOfFileToken(Loc, SM, LangOpts);
- 
   if (!SM.isMacroArgExpansion(Loc))
     return Loc;
 
   SourceLocation FileLoc = SM.getSpellingLoc(Loc);
   SourceLocation BeginFileLoc = getBeginningOfFileToken(FileLoc, SM, LangOpts);
   std::pair<FileID, unsigned> FileLocInfo = SM.getDecomposedLoc(FileLoc);
   std::pair<FileID, unsigned> BeginFileLocInfo
     = SM.getDecomposedLoc(BeginFileLoc);
   assert(FileLocInfo.first == BeginFileLocInfo.first &&
          FileLocInfo.second >= BeginFileLocInfo.second);
   return Loc.getLocWithOffset(BeginFileLocInfo.second - FileLocInfo.second);
 }
 
 namespace {
 
   enum PreambleDirectiveKind {
     PDK_Skipped,
     PDK_Unknown
   };
StringRef Lexer::getImmediateMacroNameForDiagnostics(
   StringRef ExpansionBuffer = SM.getBufferData(ExpansionInfo.first);
   return ExpansionBuffer.substr(ExpansionInfo.second, MacroTokenLength);
 }
 
 bool Lexer::isIdentifierBodyChar(char c, const LangOptions &LangOpts) {
   return isIdentifierBody(c, LangOpts.DollarIdents);
 }
 
+bool Lexer::isNewLineEscaped(const char *BufferStart, const char *Str) {
+  assert(isVerticalWhitespace(Str[0]));
+  if (Str - 1 < BufferStart)
+    return false;
+
+  if ((Str[0] == '\n' && Str[-1] == '\r') ||
+      (Str[0] == '\r' && Str[-1] == '\n')) {
+    if (Str - 2 < BufferStart)
+      return false;
+    --Str;
+  }
+  --Str;
+
+  // Rewind to first non-space character:
+  while (Str > BufferStart && isHorizontalWhitespace(*Str))
+    --Str;
+
+  return *Str == '\\';
+}
+
 StringRef Lexer::getIndentationForLine(SourceLocation Loc,
                                        const SourceManager &SM) {
   if (Loc.isInvalid() || Loc.isMacroID())
     return "";
   std::pair<FileID, unsigned> LocInfo = SM.getDecomposedLoc(Loc);
   if (LocInfo.first.isInvalid())
     return "";
   bool Invalid = false;

unittests/Lex/LexerTest.cpp

TEST_F(LexerTest, DontMergeMacroArgsFromDifferentMacroFiles) {
   // The lexer used to report its size as 31, meaning that the end of the
   // expansion would be on the *next line* (just past `M2("a", "b")`). Make
   // sure that we get the correct end location (the comma after "helper1").
   SourceLocation helper1ArgLoc = toks[20].getLocation();
   EXPECT_EQ(SourceMgr.getFileIDSize(SourceMgr.getFileID(helper1ArgLoc)), 8U);
 }
 
 TEST_F(LexerTest, DontOverallocateStringifyArgs) {
   TrivialModuleLoader ModLoader;
   auto PP = CreatePP("\"StrArg\", 5, 'C'", ModLoader);
 
   llvm::BumpPtrAllocator Allocator;
   std::array<IdentifierInfo *, 3> ParamList;
   MacroInfo *MI = PP->AllocateMacroInfo({});
   MI->setIsFunctionLike();
   MI->setParameterList(ParamList, Allocator);
   EXPECT_EQ(3u, MI->getNumParams());
   EXPECT_TRUE(MI->isFunctionLike());
 
   Token Eof;
   Eof.setKind(tok::eof);
   std::vector<Token> ArgTokens;
   while (1) {
     Token tok;
     PP->Lex(tok);
     if (tok.is(tok::eof)) {
       ArgTokens.push_back(Eof);
       break;
     }
     if (tok.is(tok::comma))
       ArgTokens.push_back(Eof);
     else
       ArgTokens.push_back(tok);
   }
 
TEST_F(LexerTest, DontOverallocateStringifyArgs) {
   EXPECT_EQ(tok::string_literal, Result.getKind());
   EXPECT_STREQ("\"'C'\"", Result.getLiteralData());
 #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
   EXPECT_DEATH(MA->getStringifiedArgument(3, *PP, {}, {}),
                "Invalid argument number!");
 #endif
 }
 
+TEST_F(LexerTest, IsNewLineEscapedValid) {
+  auto hasNewLineEscaped = [] (const char *S) {
+    return Lexer::isNewLineEscaped(S, S + strlen(S) - 1);
+  };
+
+  EXPECT_TRUE(hasNewLineEscaped("\\\r"));
+  EXPECT_TRUE(hasNewLineEscaped("\\\n"));
+  EXPECT_TRUE(hasNewLineEscaped("\\\r\n"));
+  EXPECT_TRUE(hasNewLineEscaped("\\\n\r"));
+  EXPECT_TRUE(hasNewLineEscaped("\\ \t\v\f\r"));
+  EXPECT_TRUE(hasNewLineEscaped("\\ \t\v\f\r\n"));
+
+  EXPECT_FALSE(hasNewLineEscaped("\\\r\r"));
+  EXPECT_FALSE(hasNewLineEscaped("\\\r\r\n"));
+  EXPECT_FALSE(hasNewLineEscaped("\\\n\n"));
+  EXPECT_FALSE(hasNewLineEscaped("\r"));
+  EXPECT_FALSE(hasNewLineEscaped("\n"));
+  EXPECT_FALSE(hasNewLineEscaped("\r\n"));
+  EXPECT_FALSE(hasNewLineEscaped("\n\r"));
+  EXPECT_FALSE(hasNewLineEscaped("\r\r"));
+  EXPECT_FALSE(hasNewLineEscaped("\n\n"));
+}
+
+TEST_F(LexerTest, GetBeginningOfTokenWithEscapedNewLine) {
+  // Each line should have the same length for
+  // further offset calculation to be more straightforward.
+  const unsigned IdentifierLength = 8;
+  std::string TextToLex = "rabarbar\n"
+                          "foo\\\nbar\n"
+                          "foo\\\rbar\n"
+                          "fo\\\r\nbar\n"
+                          "foo\\\n\rba\n";
+  std::vector<tok::TokenKind> ExpectedTokens{5, tok::identifier};
+  std::vector<Token> LexedTokens = CheckLex(TextToLex, ExpectedTokens);
+
+  for (const Token &Tok : LexedTokens) {
+    std::pair<FileID, unsigned> OriginalLocation =
+        SourceMgr.getDecomposedLoc(Tok.getLocation());
+    for (unsigned Offset = 0; Offset < IdentifierLength; ++Offset) {
+      SourceLocation LookupLocation =
+          Tok.getLocation().getLocWithOffset(Offset);
+
+      std::pair<FileID, unsigned> FoundLocation =
+          SourceMgr.getDecomposedExpansionLoc(
+              Lexer::GetBeginningOfToken(LookupLocation, SourceMgr, LangOpts));
+
+      // Check that location returned by the GetBeginningOfToken
+      // is the same as original token location reported by Lexer.
+      EXPECT_EQ(FoundLocation.second, OriginalLocation.second);
+    }
+  }
+}
+
 } // anonymous namespace