1 //===--- FormatTokenLexer.cpp - Lex FormatTokens -------------*- C++ ----*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 /// This file implements FormatTokenLexer, which tokenizes a source file
11 /// into a FormatToken stream suitable for ClangFormat.
13 //===----------------------------------------------------------------------===//
15 #include "FormatTokenLexer.h"
16 #include "FormatToken.h"
17 #include "clang/Basic/SourceLocation.h"
18 #include "clang/Basic/SourceManager.h"
19 #include "clang/Format/Format.h"
20 #include "llvm/Support/Regex.h"
25 FormatTokenLexer::FormatTokenLexer(
26 const SourceManager &SourceMgr, FileID ID, unsigned Column,
27 const FormatStyle &Style, encoding::Encoding Encoding,
28 llvm::SpecificBumpPtrAllocator<FormatToken> &Allocator,
29 IdentifierTable &IdentTable)
30 : FormatTok(nullptr), IsFirstToken(true), StateStack({LexerState::NORMAL}),
31 Column(Column), TrailingWhitespace(0),
32 LangOpts(getFormattingLangOpts(Style)), SourceMgr(SourceMgr), ID(ID),
33 Style(Style), IdentTable(IdentTable), Keywords(IdentTable),
34 Encoding(Encoding), Allocator(Allocator), FirstInLineIndex(0),
35 FormattingDisabled(false), MacroBlockBeginRegex(Style.MacroBlockBegin),
36 MacroBlockEndRegex(Style.MacroBlockEnd) {
37 Lex.reset(new Lexer(ID, SourceMgr.getBufferOrFake(ID), SourceMgr, LangOpts));
38 Lex->SetKeepWhitespaceMode(true);
40 for (const std::string &ForEachMacro : Style.ForEachMacros) {
41 auto Identifier = &IdentTable.get(ForEachMacro);
42 Macros.insert({Identifier, TT_ForEachMacro});
44 for (const std::string &IfMacro : Style.IfMacros) {
45 auto Identifier = &IdentTable.get(IfMacro);
46 Macros.insert({Identifier, TT_IfMacro});
48 for (const std::string &AttributeMacro : Style.AttributeMacros) {
49 auto Identifier = &IdentTable.get(AttributeMacro);
50 Macros.insert({Identifier, TT_AttributeMacro});
52 for (const std::string &StatementMacro : Style.StatementMacros) {
53 auto Identifier = &IdentTable.get(StatementMacro);
54 Macros.insert({Identifier, TT_StatementMacro});
56 for (const std::string &TypenameMacro : Style.TypenameMacros) {
57 auto Identifier = &IdentTable.get(TypenameMacro);
58 Macros.insert({Identifier, TT_TypenameMacro});
60 for (const std::string &NamespaceMacro : Style.NamespaceMacros) {
61 auto Identifier = &IdentTable.get(NamespaceMacro);
62 Macros.insert({Identifier, TT_NamespaceMacro});
64 for (const std::string &WhitespaceSensitiveMacro :
65 Style.WhitespaceSensitiveMacros) {
66 auto Identifier = &IdentTable.get(WhitespaceSensitiveMacro);
67 Macros.insert({Identifier, TT_UntouchableMacroFunc});
69 for (const std::string &StatementAttributeLikeMacro :
70 Style.StatementAttributeLikeMacros) {
71 auto Identifier = &IdentTable.get(StatementAttributeLikeMacro);
72 Macros.insert({Identifier, TT_StatementAttributeLikeMacro});
76 ArrayRef<FormatToken *> FormatTokenLexer::lex() {
77 assert(Tokens.empty());
78 assert(FirstInLineIndex == 0);
80 Tokens.push_back(getNextToken());
81 if (Style.isJavaScript()) {
82 tryParseJSRegexLiteral();
83 handleTemplateStrings();
85 if (Style.Language == FormatStyle::LK_TextProto)
86 tryParsePythonComment();
87 tryMergePreviousTokens();
88 if (Style.isCSharp()) {
89 // This needs to come after tokens have been merged so that C#
90 // string literals are correctly identified.
91 handleCSharpVerbatimAndInterpolatedStrings();
93 if (Tokens.back()->NewlinesBefore > 0 || Tokens.back()->IsMultiline)
94 FirstInLineIndex = Tokens.size() - 1;
95 } while (Tokens.back()->isNot(tok::eof));
99 void FormatTokenLexer::tryMergePreviousTokens() {
100 if (tryMerge_TMacro())
102 if (tryMergeConflictMarkers())
104 if (tryMergeLessLess())
106 if (tryMergeForEach())
108 if (Style.isCpp() && tryTransformTryUsageForC())
111 if (Style.isJavaScript() || Style.isCSharp()) {
112 static const tok::TokenKind NullishCoalescingOperator[] = {tok::question,
114 static const tok::TokenKind NullPropagatingOperator[] = {tok::question,
116 static const tok::TokenKind FatArrow[] = {tok::equal, tok::greater};
118 if (tryMergeTokens(FatArrow, TT_FatArrow))
120 if (tryMergeTokens(NullishCoalescingOperator, TT_NullCoalescingOperator)) {
121 // Treat like the "||" operator (as opposed to the ternary ?).
122 Tokens.back()->Tok.setKind(tok::pipepipe);
125 if (tryMergeTokens(NullPropagatingOperator, TT_NullPropagatingOperator)) {
126 // Treat like a regular "." access.
127 Tokens.back()->Tok.setKind(tok::period);
130 if (tryMergeNullishCoalescingEqual())
134 if (Style.isCSharp()) {
135 static const tok::TokenKind CSharpNullConditionalLSquare[] = {
136 tok::question, tok::l_square};
138 if (tryMergeCSharpKeywordVariables())
140 if (tryMergeCSharpStringLiteral())
142 if (tryTransformCSharpForEach())
144 if (tryMergeTokens(CSharpNullConditionalLSquare,
145 TT_CSharpNullConditionalLSquare)) {
146 // Treat like a regular "[" operator.
147 Tokens.back()->Tok.setKind(tok::l_square);
152 if (tryMergeNSStringLiteral())
155 if (Style.isJavaScript()) {
156 static const tok::TokenKind JSIdentity[] = {tok::equalequal, tok::equal};
157 static const tok::TokenKind JSNotIdentity[] = {tok::exclaimequal,
159 static const tok::TokenKind JSShiftEqual[] = {tok::greater, tok::greater,
161 static const tok::TokenKind JSExponentiation[] = {tok::star, tok::star};
162 static const tok::TokenKind JSExponentiationEqual[] = {tok::star,
164 static const tok::TokenKind JSPipePipeEqual[] = {tok::pipepipe, tok::equal};
165 static const tok::TokenKind JSAndAndEqual[] = {tok::ampamp, tok::equal};
167 // FIXME: Investigate what token type gives the correct operator priority.
168 if (tryMergeTokens(JSIdentity, TT_BinaryOperator))
170 if (tryMergeTokens(JSNotIdentity, TT_BinaryOperator))
172 if (tryMergeTokens(JSShiftEqual, TT_BinaryOperator))
174 if (tryMergeTokens(JSExponentiation, TT_JsExponentiation))
176 if (tryMergeTokens(JSExponentiationEqual, TT_JsExponentiationEqual)) {
177 Tokens.back()->Tok.setKind(tok::starequal);
180 if (tryMergeTokens(JSAndAndEqual, TT_JsAndAndEqual) ||
181 tryMergeTokens(JSPipePipeEqual, TT_JsPipePipeEqual)) {
182 // Treat like the "=" assignment operator.
183 Tokens.back()->Tok.setKind(tok::equal);
186 if (tryMergeJSPrivateIdentifier())
190 if (Style.Language == FormatStyle::LK_Java) {
191 static const tok::TokenKind JavaRightLogicalShiftAssign[] = {
192 tok::greater, tok::greater, tok::greaterequal};
193 if (tryMergeTokens(JavaRightLogicalShiftAssign, TT_BinaryOperator))
198 bool FormatTokenLexer::tryMergeNSStringLiteral() {
199 if (Tokens.size() < 2)
201 auto &At = *(Tokens.end() - 2);
202 auto &String = *(Tokens.end() - 1);
203 if (!At->is(tok::at) || !String->is(tok::string_literal))
205 At->Tok.setKind(tok::string_literal);
206 At->TokenText = StringRef(At->TokenText.begin(),
207 String->TokenText.end() - At->TokenText.begin());
208 At->ColumnWidth += String->ColumnWidth;
209 At->setType(TT_ObjCStringLiteral);
210 Tokens.erase(Tokens.end() - 1);
214 bool FormatTokenLexer::tryMergeJSPrivateIdentifier() {
215 // Merges #idenfier into a single identifier with the text #identifier
216 // but the token tok::identifier.
217 if (Tokens.size() < 2)
219 auto &Hash = *(Tokens.end() - 2);
220 auto &Identifier = *(Tokens.end() - 1);
221 if (!Hash->is(tok::hash) || !Identifier->is(tok::identifier))
223 Hash->Tok.setKind(tok::identifier);
225 StringRef(Hash->TokenText.begin(),
226 Identifier->TokenText.end() - Hash->TokenText.begin());
227 Hash->ColumnWidth += Identifier->ColumnWidth;
228 Hash->setType(TT_JsPrivateIdentifier);
229 Tokens.erase(Tokens.end() - 1);
233 // Search for verbatim or interpolated string literals @"ABC" or
234 // $"aaaaa{abc}aaaaa" i and mark the token as TT_CSharpStringLiteral, and to
235 // prevent splitting of @, $ and ".
236 // Merging of multiline verbatim strings with embedded '"' is handled in
237 // handleCSharpVerbatimAndInterpolatedStrings with lower-level lexing.
238 bool FormatTokenLexer::tryMergeCSharpStringLiteral() {
239 if (Tokens.size() < 2)
242 // Look for @"aaaaaa" or $"aaaaaa".
243 auto &String = *(Tokens.end() - 1);
244 if (!String->is(tok::string_literal))
247 auto &At = *(Tokens.end() - 2);
248 if (!(At->is(tok::at) || At->TokenText == "$"))
251 if (Tokens.size() > 2 && At->is(tok::at)) {
252 auto &Dollar = *(Tokens.end() - 3);
253 if (Dollar->TokenText == "$") {
254 // This looks like $@"aaaaa" so we need to combine all 3 tokens.
255 Dollar->Tok.setKind(tok::string_literal);
257 StringRef(Dollar->TokenText.begin(),
258 String->TokenText.end() - Dollar->TokenText.begin());
259 Dollar->ColumnWidth += (At->ColumnWidth + String->ColumnWidth);
260 Dollar->setType(TT_CSharpStringLiteral);
261 Tokens.erase(Tokens.end() - 2);
262 Tokens.erase(Tokens.end() - 1);
267 // Convert back into just a string_literal.
268 At->Tok.setKind(tok::string_literal);
269 At->TokenText = StringRef(At->TokenText.begin(),
270 String->TokenText.end() - At->TokenText.begin());
271 At->ColumnWidth += String->ColumnWidth;
272 At->setType(TT_CSharpStringLiteral);
273 Tokens.erase(Tokens.end() - 1);
277 // Valid C# attribute targets:
278 // https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/concepts/attributes/#attribute-targets
279 const llvm::StringSet<> FormatTokenLexer::CSharpAttributeTargets = {
280 "assembly", "module", "field", "event", "method",
281 "param", "property", "return", "type",
284 bool FormatTokenLexer::tryMergeNullishCoalescingEqual() {
285 if (Tokens.size() < 2)
287 auto &NullishCoalescing = *(Tokens.end() - 2);
288 auto &Equal = *(Tokens.end() - 1);
289 if (NullishCoalescing->getType() != TT_NullCoalescingOperator ||
290 !Equal->is(tok::equal)) {
293 NullishCoalescing->Tok.setKind(tok::equal); // no '??=' in clang tokens.
294 NullishCoalescing->TokenText =
295 StringRef(NullishCoalescing->TokenText.begin(),
296 Equal->TokenText.end() - NullishCoalescing->TokenText.begin());
297 NullishCoalescing->ColumnWidth += Equal->ColumnWidth;
298 NullishCoalescing->setType(TT_NullCoalescingEqual);
299 Tokens.erase(Tokens.end() - 1);
303 bool FormatTokenLexer::tryMergeCSharpKeywordVariables() {
304 if (Tokens.size() < 2)
306 auto &At = *(Tokens.end() - 2);
307 auto &Keyword = *(Tokens.end() - 1);
308 if (!At->is(tok::at))
310 if (!Keywords.isCSharpKeyword(*Keyword))
313 At->Tok.setKind(tok::identifier);
314 At->TokenText = StringRef(At->TokenText.begin(),
315 Keyword->TokenText.end() - At->TokenText.begin());
316 At->ColumnWidth += Keyword->ColumnWidth;
317 At->setType(Keyword->getType());
318 Tokens.erase(Tokens.end() - 1);
322 // In C# transform identifier foreach into kw_foreach
323 bool FormatTokenLexer::tryTransformCSharpForEach() {
324 if (Tokens.size() < 1)
326 auto &Identifier = *(Tokens.end() - 1);
327 if (!Identifier->is(tok::identifier))
329 if (Identifier->TokenText != "foreach")
332 Identifier->setType(TT_ForEachMacro);
333 Identifier->Tok.setKind(tok::kw_for);
337 bool FormatTokenLexer::tryMergeForEach() {
338 if (Tokens.size() < 2)
340 auto &For = *(Tokens.end() - 2);
341 auto &Each = *(Tokens.end() - 1);
342 if (!For->is(tok::kw_for))
344 if (!Each->is(tok::identifier))
346 if (Each->TokenText != "each")
349 For->setType(TT_ForEachMacro);
350 For->Tok.setKind(tok::kw_for);
352 For->TokenText = StringRef(For->TokenText.begin(),
353 Each->TokenText.end() - For->TokenText.begin());
354 For->ColumnWidth += Each->ColumnWidth;
355 Tokens.erase(Tokens.end() - 1);
359 bool FormatTokenLexer::tryTransformTryUsageForC() {
360 if (Tokens.size() < 2)
362 auto &Try = *(Tokens.end() - 2);
363 if (!Try->is(tok::kw_try))
365 auto &Next = *(Tokens.end() - 1);
366 if (Next->isOneOf(tok::l_brace, tok::colon, tok::hash, tok::comment))
369 if (Tokens.size() > 2) {
370 auto &At = *(Tokens.end() - 3);
375 Try->Tok.setKind(tok::identifier);
379 bool FormatTokenLexer::tryMergeLessLess() {
380 // Merge X,less,less,Y into X,lessless,Y unless X or Y is less.
381 if (Tokens.size() < 3)
384 auto First = Tokens.end() - 3;
385 if (First[0]->isNot(tok::less) || First[1]->isNot(tok::less))
388 // Only merge if there currently is no whitespace between the two "<".
389 if (First[1]->hasWhitespaceBefore())
392 auto X = Tokens.size() > 3 ? First[-1] : nullptr;
394 if ((X && X->is(tok::less)) || Y->is(tok::less))
397 // Do not remove a whitespace between the two "<" e.g. "operator< <>".
398 if (X && X->is(tok::kw_operator) && Y->is(tok::greater))
401 First[0]->Tok.setKind(tok::lessless);
402 First[0]->TokenText = "<<";
403 First[0]->ColumnWidth += 1;
404 Tokens.erase(Tokens.end() - 2);
408 bool FormatTokenLexer::tryMergeTokens(ArrayRef<tok::TokenKind> Kinds,
410 if (Tokens.size() < Kinds.size())
413 SmallVectorImpl<FormatToken *>::const_iterator First =
414 Tokens.end() - Kinds.size();
415 if (!First[0]->is(Kinds[0]))
417 unsigned AddLength = 0;
418 for (unsigned i = 1; i < Kinds.size(); ++i) {
419 if (!First[i]->is(Kinds[i]) || First[i]->hasWhitespaceBefore())
421 AddLength += First[i]->TokenText.size();
423 Tokens.resize(Tokens.size() - Kinds.size() + 1);
424 First[0]->TokenText = StringRef(First[0]->TokenText.data(),
425 First[0]->TokenText.size() + AddLength);
426 First[0]->ColumnWidth += AddLength;
427 First[0]->setType(NewType);
431 // Returns \c true if \p Tok can only be followed by an operand in JavaScript.
432 bool FormatTokenLexer::precedesOperand(FormatToken *Tok) {
433 // NB: This is not entirely correct, as an r_paren can introduce an operand
434 // location in e.g. `if (foo) /bar/.exec(...);`. That is a rare enough
435 // corner case to not matter in practice, though.
436 return Tok->isOneOf(tok::period, tok::l_paren, tok::comma, tok::l_brace,
437 tok::r_brace, tok::l_square, tok::semi, tok::exclaim,
438 tok::colon, tok::question, tok::tilde) ||
439 Tok->isOneOf(tok::kw_return, tok::kw_do, tok::kw_case, tok::kw_throw,
440 tok::kw_else, tok::kw_new, tok::kw_delete, tok::kw_void,
441 tok::kw_typeof, Keywords.kw_instanceof, Keywords.kw_in) ||
442 Tok->isBinaryOperator();
445 bool FormatTokenLexer::canPrecedeRegexLiteral(FormatToken *Prev) {
449 // Regex literals can only follow after prefix unary operators, not after
450 // postfix unary operators. If the '++' is followed by a non-operand
451 // introducing token, the slash here is the operand and not the start of a
453 // `!` is an unary prefix operator, but also a post-fix operator that casts
454 // away nullability, so the same check applies.
455 if (Prev->isOneOf(tok::plusplus, tok::minusminus, tok::exclaim))
456 return Tokens.size() < 3 || precedesOperand(Tokens[Tokens.size() - 3]);
458 // The previous token must introduce an operand location where regex
459 // literals can occur.
460 if (!precedesOperand(Prev))
466 // Tries to parse a JavaScript Regex literal starting at the current token,
467 // if that begins with a slash and is in a location where JavaScript allows
468 // regex literals. Changes the current token to a regex literal and updates
469 // its text if successful.
470 void FormatTokenLexer::tryParseJSRegexLiteral() {
471 FormatToken *RegexToken = Tokens.back();
472 if (!RegexToken->isOneOf(tok::slash, tok::slashequal))
475 FormatToken *Prev = nullptr;
476 for (FormatToken *FT : llvm::drop_begin(llvm::reverse(Tokens))) {
477 // NB: Because previous pointers are not initialized yet, this cannot use
478 // Token.getPreviousNonComment.
479 if (FT->isNot(tok::comment)) {
485 if (!canPrecedeRegexLiteral(Prev))
488 // 'Manually' lex ahead in the current file buffer.
489 const char *Offset = Lex->getBufferLocation();
490 const char *RegexBegin = Offset - RegexToken->TokenText.size();
491 StringRef Buffer = Lex->getBuffer();
492 bool InCharacterClass = false;
493 bool HaveClosingSlash = false;
494 for (; !HaveClosingSlash && Offset != Buffer.end(); ++Offset) {
495 // Regular expressions are terminated with a '/', which can only be
496 // escaped using '\' or a character class between '[' and ']'.
497 // See http://www.ecma-international.org/ecma-262/5.1/#sec-7.8.5.
500 // Skip the escaped character.
504 InCharacterClass = true;
507 InCharacterClass = false;
510 if (!InCharacterClass)
511 HaveClosingSlash = true;
516 RegexToken->setType(TT_RegexLiteral);
517 // Treat regex literals like other string_literals.
518 RegexToken->Tok.setKind(tok::string_literal);
519 RegexToken->TokenText = StringRef(RegexBegin, Offset - RegexBegin);
520 RegexToken->ColumnWidth = RegexToken->TokenText.size();
522 resetLexer(SourceMgr.getFileOffset(Lex->getSourceLocation(Offset)));
525 static auto lexCSharpString(const char *Begin, const char *End, bool Verbatim,
527 auto Repeated = [&Begin, End]() {
528 return Begin + 1 < End && Begin[1] == Begin[0];
531 // Look for a terminating '"' in the current file buffer.
532 // Make no effort to format code within an interpolated or verbatim string.
534 // Interpolated strings could contain { } with " characters inside.
536 // should not be split into $"{x ?? ", null, "}" but should be treated as a
537 // single string-literal.
539 // We opt not to try and format expressions inside {} within a C#
540 // interpolated string. Formatting expressions within an interpolated string
541 // would require similar work as that done for JavaScript template strings
542 // in `handleTemplateStrings()`.
543 for (int UnmatchedOpeningBraceCount = 0; Begin < End; ++Begin) {
551 // {{ inside an interpolated string is escaped, so skip it.
555 ++UnmatchedOpeningBraceCount;
560 // }} inside an interpolated string is escaped, so skip it.
563 else if (UnmatchedOpeningBraceCount > 0)
564 --UnmatchedOpeningBraceCount;
570 if (UnmatchedOpeningBraceCount > 0)
572 // "" within a verbatim string is an escaped double quote: skip it.
573 if (Verbatim && Repeated()) {
584 void FormatTokenLexer::handleCSharpVerbatimAndInterpolatedStrings() {
585 FormatToken *CSharpStringLiteral = Tokens.back();
587 if (CSharpStringLiteral->isNot(TT_CSharpStringLiteral))
590 auto &TokenText = CSharpStringLiteral->TokenText;
592 bool Verbatim = false;
593 bool Interpolated = false;
594 if (TokenText.startswith(R"($@")")) {
597 } else if (TokenText.startswith(R"(@")")) {
599 } else if (TokenText.startswith(R"($")")) {
603 // Deal with multiline strings.
604 if (!Verbatim && !Interpolated)
607 const char *StrBegin = Lex->getBufferLocation() - TokenText.size();
608 const char *Offset = StrBegin;
609 if (Verbatim && Interpolated)
614 const auto End = Lex->getBuffer().end();
615 Offset = lexCSharpString(Offset, End, Verbatim, Interpolated);
617 // Make no attempt to format code properly if a verbatim string is
622 StringRef LiteralText(StrBegin, Offset - StrBegin + 1);
623 TokenText = LiteralText;
625 // Adjust width for potentially multiline string literals.
626 size_t FirstBreak = LiteralText.find('\n');
627 StringRef FirstLineText = FirstBreak == StringRef::npos
629 : LiteralText.substr(0, FirstBreak);
630 CSharpStringLiteral->ColumnWidth = encoding::columnWidthWithTabs(
631 FirstLineText, CSharpStringLiteral->OriginalColumn, Style.TabWidth,
633 size_t LastBreak = LiteralText.rfind('\n');
634 if (LastBreak != StringRef::npos) {
635 CSharpStringLiteral->IsMultiline = true;
636 unsigned StartColumn = 0;
637 CSharpStringLiteral->LastLineColumnWidth =
638 encoding::columnWidthWithTabs(LiteralText.substr(LastBreak + 1),
639 StartColumn, Style.TabWidth, Encoding);
642 assert(Offset < End);
643 resetLexer(SourceMgr.getFileOffset(Lex->getSourceLocation(Offset + 1)));
646 void FormatTokenLexer::handleTemplateStrings() {
647 FormatToken *BacktickToken = Tokens.back();
649 if (BacktickToken->is(tok::l_brace)) {
650 StateStack.push(LexerState::NORMAL);
653 if (BacktickToken->is(tok::r_brace)) {
654 if (StateStack.size() == 1)
657 if (StateStack.top() != LexerState::TEMPLATE_STRING)
659 // If back in TEMPLATE_STRING, fallthrough and continue parsing the
660 } else if (BacktickToken->is(tok::unknown) &&
661 BacktickToken->TokenText == "`") {
662 StateStack.push(LexerState::TEMPLATE_STRING);
664 return; // Not actually a template
667 // 'Manually' lex ahead in the current file buffer.
668 const char *Offset = Lex->getBufferLocation();
669 const char *TmplBegin = Offset - BacktickToken->TokenText.size(); // at "`"
670 for (; Offset != Lex->getBuffer().end(); ++Offset) {
671 if (Offset[0] == '`') {
675 if (Offset[0] == '\\') {
676 ++Offset; // Skip the escaped character.
677 } else if (Offset + 1 < Lex->getBuffer().end() && Offset[0] == '$' &&
679 // '${' introduces an expression interpolation in the template string.
680 StateStack.push(LexerState::NORMAL);
686 StringRef LiteralText(TmplBegin, Offset - TmplBegin + 1);
687 BacktickToken->setType(TT_TemplateString);
688 BacktickToken->Tok.setKind(tok::string_literal);
689 BacktickToken->TokenText = LiteralText;
691 // Adjust width for potentially multiline string literals.
692 size_t FirstBreak = LiteralText.find('\n');
693 StringRef FirstLineText = FirstBreak == StringRef::npos
695 : LiteralText.substr(0, FirstBreak);
696 BacktickToken->ColumnWidth = encoding::columnWidthWithTabs(
697 FirstLineText, BacktickToken->OriginalColumn, Style.TabWidth, Encoding);
698 size_t LastBreak = LiteralText.rfind('\n');
699 if (LastBreak != StringRef::npos) {
700 BacktickToken->IsMultiline = true;
701 unsigned StartColumn = 0; // The template tail spans the entire line.
702 BacktickToken->LastLineColumnWidth =
703 encoding::columnWidthWithTabs(LiteralText.substr(LastBreak + 1),
704 StartColumn, Style.TabWidth, Encoding);
707 SourceLocation loc = Offset < Lex->getBuffer().end()
708 ? Lex->getSourceLocation(Offset + 1)
709 : SourceMgr.getLocForEndOfFile(ID);
710 resetLexer(SourceMgr.getFileOffset(loc));
713 void FormatTokenLexer::tryParsePythonComment() {
714 FormatToken *HashToken = Tokens.back();
715 if (!HashToken->isOneOf(tok::hash, tok::hashhash))
717 // Turn the remainder of this line into a comment.
718 const char *CommentBegin =
719 Lex->getBufferLocation() - HashToken->TokenText.size(); // at "#"
720 size_t From = CommentBegin - Lex->getBuffer().begin();
721 size_t To = Lex->getBuffer().find_first_of('\n', From);
722 if (To == StringRef::npos)
723 To = Lex->getBuffer().size();
724 size_t Len = To - From;
725 HashToken->setType(TT_LineComment);
726 HashToken->Tok.setKind(tok::comment);
727 HashToken->TokenText = Lex->getBuffer().substr(From, Len);
728 SourceLocation Loc = To < Lex->getBuffer().size()
729 ? Lex->getSourceLocation(CommentBegin + Len)
730 : SourceMgr.getLocForEndOfFile(ID);
731 resetLexer(SourceMgr.getFileOffset(Loc));
734 bool FormatTokenLexer::tryMerge_TMacro() {
735 if (Tokens.size() < 4)
737 FormatToken *Last = Tokens.back();
738 if (!Last->is(tok::r_paren))
741 FormatToken *String = Tokens[Tokens.size() - 2];
742 if (!String->is(tok::string_literal) || String->IsMultiline)
745 if (!Tokens[Tokens.size() - 3]->is(tok::l_paren))
748 FormatToken *Macro = Tokens[Tokens.size() - 4];
749 if (Macro->TokenText != "_T")
752 const char *Start = Macro->TokenText.data();
753 const char *End = Last->TokenText.data() + Last->TokenText.size();
754 String->TokenText = StringRef(Start, End - Start);
755 String->IsFirst = Macro->IsFirst;
756 String->LastNewlineOffset = Macro->LastNewlineOffset;
757 String->WhitespaceRange = Macro->WhitespaceRange;
758 String->OriginalColumn = Macro->OriginalColumn;
759 String->ColumnWidth = encoding::columnWidthWithTabs(
760 String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding);
761 String->NewlinesBefore = Macro->NewlinesBefore;
762 String->HasUnescapedNewline = Macro->HasUnescapedNewline;
767 Tokens.back() = String;
768 if (FirstInLineIndex >= Tokens.size())
769 FirstInLineIndex = Tokens.size() - 1;
773 bool FormatTokenLexer::tryMergeConflictMarkers() {
774 if (Tokens.back()->NewlinesBefore == 0 && Tokens.back()->isNot(tok::eof))
777 // Conflict lines look like:
778 // <marker> <text from the vcs>
780 // >>>>>>> /file/in/file/system at revision 1234
782 // We merge all tokens in a line that starts with a conflict marker
783 // into a single token with a special token type that the unwrapped line
784 // parser will use to correctly rebuild the underlying code.
787 // Get the position of the first token in the line.
788 unsigned FirstInLineOffset;
789 std::tie(ID, FirstInLineOffset) = SourceMgr.getDecomposedLoc(
790 Tokens[FirstInLineIndex]->getStartOfNonWhitespace());
791 StringRef Buffer = SourceMgr.getBufferOrFake(ID).getBuffer();
792 // Calculate the offset of the start of the current line.
793 auto LineOffset = Buffer.rfind('\n', FirstInLineOffset);
794 if (LineOffset == StringRef::npos)
799 auto FirstSpace = Buffer.find_first_of(" \n", LineOffset);
801 if (FirstSpace == StringRef::npos)
802 LineStart = Buffer.substr(LineOffset);
804 LineStart = Buffer.substr(LineOffset, FirstSpace - LineOffset);
806 TokenType Type = TT_Unknown;
807 if (LineStart == "<<<<<<<" || LineStart == ">>>>") {
808 Type = TT_ConflictStart;
809 } else if (LineStart == "|||||||" || LineStart == "=======" ||
810 LineStart == "====") {
811 Type = TT_ConflictAlternative;
812 } else if (LineStart == ">>>>>>>" || LineStart == "<<<<") {
813 Type = TT_ConflictEnd;
816 if (Type != TT_Unknown) {
817 FormatToken *Next = Tokens.back();
819 Tokens.resize(FirstInLineIndex + 1);
820 // We do not need to build a complete token here, as we will skip it
821 // during parsing anyway (as we must not touch whitespace around conflict
823 Tokens.back()->setType(Type);
824 Tokens.back()->Tok.setKind(tok::kw___unknown_anytype);
826 Tokens.push_back(Next);
833 FormatToken *FormatTokenLexer::getStashedToken() {
834 // Create a synthesized second '>' or '<' token.
835 Token Tok = FormatTok->Tok;
836 StringRef TokenText = FormatTok->TokenText;
838 unsigned OriginalColumn = FormatTok->OriginalColumn;
839 FormatTok = new (Allocator.Allocate()) FormatToken;
840 FormatTok->Tok = Tok;
841 SourceLocation TokLocation =
842 FormatTok->Tok.getLocation().getLocWithOffset(Tok.getLength() - 1);
843 FormatTok->Tok.setLocation(TokLocation);
844 FormatTok->WhitespaceRange = SourceRange(TokLocation, TokLocation);
845 FormatTok->TokenText = TokenText;
846 FormatTok->ColumnWidth = 1;
847 FormatTok->OriginalColumn = OriginalColumn + 1;
852 /// Truncate the current token to the new length and make the lexer continue
853 /// from the end of the truncated token. Used for other languages that have
854 /// different token boundaries, like JavaScript in which a comment ends at a
855 /// line break regardless of whether the line break follows a backslash. Also
856 /// used to set the lexer to the end of whitespace if the lexer regards
857 /// whitespace and an unrecognized symbol as one token.
858 void FormatTokenLexer::truncateToken(size_t NewLen) {
859 assert(NewLen <= FormatTok->TokenText.size());
860 resetLexer(SourceMgr.getFileOffset(Lex->getSourceLocation(
861 Lex->getBufferLocation() - FormatTok->TokenText.size() + NewLen)));
862 FormatTok->TokenText = FormatTok->TokenText.substr(0, NewLen);
863 FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
864 FormatTok->TokenText, FormatTok->OriginalColumn, Style.TabWidth,
866 FormatTok->Tok.setLength(NewLen);
869 /// Count the length of leading whitespace in a token.
870 static size_t countLeadingWhitespace(StringRef Text) {
871 // Basically counting the length matched by this regex.
872 // "^([\n\r\f\v \t]|(\\\\|\\?\\?/)[\n\r])+"
873 // Directly using the regex turned out to be slow. With the regex
874 // version formatting all files in this directory took about 1.25
875 // seconds. This version took about 0.5 seconds.
876 const unsigned char *const Begin = Text.bytes_begin();
877 const unsigned char *const End = Text.bytes_end();
878 const unsigned char *Cur = Begin;
880 if (isspace(Cur[0])) {
882 } else if (Cur[0] == '\\' && (Cur[1] == '\n' || Cur[1] == '\r')) {
883 // A '\' followed by a newline always escapes the newline, regardless
884 // of whether there is another '\' before it.
885 // The source has a null byte at the end. So the end of the entire input
886 // isn't reached yet. Also the lexer doesn't break apart an escaped
888 assert(End - Cur >= 2);
890 } else if (Cur[0] == '?' && Cur[1] == '?' && Cur[2] == '/' &&
891 (Cur[3] == '\n' || Cur[3] == '\r')) {
892 // Newlines can also be escaped by a '?' '?' '/' trigraph. By the way, the
893 // characters are quoted individually in this comment because if we write
894 // them together some compilers warn that we have a trigraph in the code.
895 assert(End - Cur >= 4);
904 FormatToken *FormatTokenLexer::getNextToken() {
905 if (StateStack.top() == LexerState::TOKEN_STASHED) {
907 return getStashedToken();
910 FormatTok = new (Allocator.Allocate()) FormatToken;
911 readRawToken(*FormatTok);
912 SourceLocation WhitespaceStart =
913 FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
914 FormatTok->IsFirst = IsFirstToken;
915 IsFirstToken = false;
917 // Consume and record whitespace until we find a significant token.
918 // Some tok::unknown tokens are not just whitespace, e.g. whitespace
919 // followed by a symbol such as backtick. Those symbols may be
920 // significant in other languages.
921 unsigned WhitespaceLength = TrailingWhitespace;
922 while (FormatTok->isNot(tok::eof)) {
923 auto LeadingWhitespace = countLeadingWhitespace(FormatTok->TokenText);
924 if (LeadingWhitespace == 0)
926 if (LeadingWhitespace < FormatTok->TokenText.size())
927 truncateToken(LeadingWhitespace);
928 StringRef Text = FormatTok->TokenText;
929 bool InEscape = false;
930 for (int i = 0, e = Text.size(); i != e; ++i) {
933 // If this is a CRLF sequence, break here and the LF will be handled on
934 // the next loop iteration. Otherwise, this is a single Mac CR, treat it
935 // the same as a single LF.
936 if (i + 1 < e && Text[i + 1] == '\n')
940 ++FormatTok->NewlinesBefore;
942 FormatTok->HasUnescapedNewline = true;
945 FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
957 Style.TabWidth - (Style.TabWidth ? Column % Style.TabWidth : 0);
962 // The text was entirely whitespace when this loop was entered. Thus
963 // this has to be an escape sequence.
964 assert(Text.substr(i, 2) == "\\\r" || Text.substr(i, 2) == "\\\n" ||
965 Text.substr(i, 4) == "\?\?/\r" ||
966 Text.substr(i, 4) == "\?\?/\n" ||
967 (i >= 1 && (Text.substr(i - 1, 4) == "\?\?/\r" ||
968 Text.substr(i - 1, 4) == "\?\?/\n")) ||
969 (i >= 2 && (Text.substr(i - 2, 4) == "\?\?/\r" ||
970 Text.substr(i - 2, 4) == "\?\?/\n")));
974 // This shouldn't happen.
979 WhitespaceLength += Text.size();
980 readRawToken(*FormatTok);
983 if (FormatTok->is(tok::unknown))
984 FormatTok->setType(TT_ImplicitStringLiteral);
986 // JavaScript and Java do not allow to escape the end of the line with a
987 // backslash. Backslashes are syntax errors in plain source, but can occur in
988 // comments. When a single line comment ends with a \, it'll cause the next
989 // line of code to be lexed as a comment, breaking formatting. The code below
990 // finds comments that contain a backslash followed by a line break, truncates
991 // the comment token at the backslash, and resets the lexer to restart behind
993 if ((Style.isJavaScript() || Style.Language == FormatStyle::LK_Java) &&
994 FormatTok->is(tok::comment) && FormatTok->TokenText.startswith("//")) {
995 size_t BackslashPos = FormatTok->TokenText.find('\\');
996 while (BackslashPos != StringRef::npos) {
997 if (BackslashPos + 1 < FormatTok->TokenText.size() &&
998 FormatTok->TokenText[BackslashPos + 1] == '\n') {
999 truncateToken(BackslashPos + 1);
1002 BackslashPos = FormatTok->TokenText.find('\\', BackslashPos + 1);
1006 if (Style.isVerilog()) {
1007 // Verilog uses the backtick instead of the hash for preprocessor stuff.
1008 // And it uses the hash for delays and parameter lists. In order to continue
1009 // using `tok::hash` in other places, the backtick gets marked as the hash
1010 // here. And in order to tell the backtick and hash apart for
1011 // Verilog-specific stuff, the hash becomes an identifier.
1012 if (FormatTok->isOneOf(tok::hash, tok::hashhash)) {
1013 FormatTok->Tok.setKind(tok::raw_identifier);
1014 } else if (FormatTok->is(tok::raw_identifier)) {
1015 if (FormatTok->TokenText == "`") {
1016 FormatTok->Tok.setIdentifierInfo(nullptr);
1017 FormatTok->Tok.setKind(tok::hash);
1018 } else if (FormatTok->TokenText == "``") {
1019 FormatTok->Tok.setIdentifierInfo(nullptr);
1020 FormatTok->Tok.setKind(tok::hashhash);
1025 FormatTok->WhitespaceRange = SourceRange(
1026 WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
1028 FormatTok->OriginalColumn = Column;
1030 TrailingWhitespace = 0;
1031 if (FormatTok->is(tok::comment)) {
1032 // FIXME: Add the trimmed whitespace to Column.
1033 StringRef UntrimmedText = FormatTok->TokenText;
1034 FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
1035 TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
1036 } else if (FormatTok->is(tok::raw_identifier)) {
1037 IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
1038 FormatTok->Tok.setIdentifierInfo(&Info);
1039 FormatTok->Tok.setKind(Info.getTokenID());
1040 if (Style.Language == FormatStyle::LK_Java &&
1041 FormatTok->isOneOf(tok::kw_struct, tok::kw_union, tok::kw_delete,
1042 tok::kw_operator)) {
1043 FormatTok->Tok.setKind(tok::identifier);
1044 FormatTok->Tok.setIdentifierInfo(nullptr);
1045 } else if (Style.isJavaScript() &&
1046 FormatTok->isOneOf(tok::kw_struct, tok::kw_union,
1047 tok::kw_operator)) {
1048 FormatTok->Tok.setKind(tok::identifier);
1049 FormatTok->Tok.setIdentifierInfo(nullptr);
1051 } else if (FormatTok->is(tok::greatergreater)) {
1052 FormatTok->Tok.setKind(tok::greater);
1053 FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1055 StateStack.push(LexerState::TOKEN_STASHED);
1056 } else if (FormatTok->is(tok::lessless)) {
1057 FormatTok->Tok.setKind(tok::less);
1058 FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1060 StateStack.push(LexerState::TOKEN_STASHED);
1063 // Now FormatTok is the next non-whitespace token.
1065 StringRef Text = FormatTok->TokenText;
1066 size_t FirstNewlinePos = Text.find('\n');
1067 if (FirstNewlinePos == StringRef::npos) {
1068 // FIXME: ColumnWidth actually depends on the start column, we need to
1069 // take this into account when the token is moved.
1070 FormatTok->ColumnWidth =
1071 encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding);
1072 Column += FormatTok->ColumnWidth;
1074 FormatTok->IsMultiline = true;
1075 // FIXME: ColumnWidth actually depends on the start column, we need to
1076 // take this into account when the token is moved.
1077 FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
1078 Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding);
1080 // The last line of the token always starts in column 0.
1081 // Thus, the length can be precomputed even in the presence of tabs.
1082 FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
1083 Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth, Encoding);
1084 Column = FormatTok->LastLineColumnWidth;
1087 if (Style.isCpp()) {
1088 auto it = Macros.find(FormatTok->Tok.getIdentifierInfo());
1089 if (!(Tokens.size() > 0 && Tokens.back()->Tok.getIdentifierInfo() &&
1090 Tokens.back()->Tok.getIdentifierInfo()->getPPKeywordID() ==
1092 it != Macros.end()) {
1093 FormatTok->setType(it->second);
1094 if (it->second == TT_IfMacro) {
1095 // The lexer token currently has type tok::kw_unknown. However, for this
1096 // substitution to be treated correctly in the TokenAnnotator, faking
1097 // the tok value seems to be needed. Not sure if there's a more elegant
1099 FormatTok->Tok.setKind(tok::kw_if);
1101 } else if (FormatTok->is(tok::identifier)) {
1102 if (MacroBlockBeginRegex.match(Text))
1103 FormatTok->setType(TT_MacroBlockBegin);
1104 else if (MacroBlockEndRegex.match(Text))
1105 FormatTok->setType(TT_MacroBlockEnd);
1112 bool FormatTokenLexer::readRawTokenVerilogSpecific(Token &Tok) {
1113 // In Verilog the quote is not a character literal.
1115 // Make the backtick and double backtick identifiers to match against them
1118 // In Verilog an escaped identifier starts with backslash and ends with
1119 // whitespace. Unless that whitespace is an escaped newline. A backslash can
1120 // also begin an escaped newline outside of an escaped identifier. We check
1121 // for that outside of the Regex since we can't use negative lookhead
1122 // assertions. Simply changing the '*' to '+' breaks stuff as the escaped
1123 // identifier may have a length of 0 according to Section A.9.3.
1124 // FIXME: If there is an escaped newline in the middle of an escaped
1125 // identifier, allow for pasting the two lines together, But escaped
1126 // identifiers usually occur only in generated code anyway.
1127 static const llvm::Regex VerilogToken(R"re(^('|``?|\\(\\)re"
1128 "(\r?\n|\r)|[^[:space:]])*)");
1130 SmallVector<StringRef, 4> Matches;
1131 const char *Start = Lex->getBufferLocation();
1132 if (!VerilogToken.match(StringRef(Start, Lex->getBuffer().end() - Start),
1136 // There is a null byte at the end of the buffer, so we don't have to check
1137 // Start[1] is within the buffer.
1138 if (Start[0] == '\\' && (Start[1] == '\r' || Start[1] == '\n'))
1140 size_t Len = Matches[0].size();
1142 // The kind has to be an identifier so we can match it against those defined
1143 // in Keywords. The kind has to be set before the length because the setLength
1144 // function checks that the kind is not an annotation.
1145 Tok.setKind(tok::raw_identifier);
1147 Tok.setLocation(Lex->getSourceLocation(Start, Len));
1148 Tok.setRawIdentifierData(Start);
1149 Lex->seek(Lex->getCurrentBufferOffset() + Len, /*IsAtStartofline=*/false);
1153 void FormatTokenLexer::readRawToken(FormatToken &Tok) {
1154 // For Verilog, first see if there is a special token, and fall back to the
1155 // normal lexer if there isn't one.
1156 if (!Style.isVerilog() || !readRawTokenVerilogSpecific(Tok.Tok))
1157 Lex->LexFromRawLexer(Tok.Tok);
1158 Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
1159 Tok.Tok.getLength());
1160 // For formatting, treat unterminated string literals like normal string
1162 if (Tok.is(tok::unknown)) {
1163 if (!Tok.TokenText.empty() && Tok.TokenText[0] == '"') {
1164 Tok.Tok.setKind(tok::string_literal);
1165 Tok.IsUnterminatedLiteral = true;
1166 } else if (Style.isJavaScript() && Tok.TokenText == "''") {
1167 Tok.Tok.setKind(tok::string_literal);
1171 if ((Style.isJavaScript() || Style.Language == FormatStyle::LK_Proto ||
1172 Style.Language == FormatStyle::LK_TextProto) &&
1173 Tok.is(tok::char_constant)) {
1174 Tok.Tok.setKind(tok::string_literal);
1177 if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format on" ||
1178 Tok.TokenText == "/* clang-format on */")) {
1179 FormattingDisabled = false;
1182 Tok.Finalized = FormattingDisabled;
1184 if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format off" ||
1185 Tok.TokenText == "/* clang-format off */")) {
1186 FormattingDisabled = true;
1190 void FormatTokenLexer::resetLexer(unsigned Offset) {
1191 StringRef Buffer = SourceMgr.getBufferData(ID);
1192 LangOpts = getFormattingLangOpts(Style);
1193 Lex.reset(new Lexer(SourceMgr.getLocForStartOfFile(ID), LangOpts,
1194 Buffer.begin(), Buffer.begin() + Offset, Buffer.end()));
1195 Lex->SetKeepWhitespaceMode(true);
1196 TrailingWhitespace = 0;
1199 } // namespace format
1200 } // namespace clang