1//===--- FormatTokenLexer.cpp - Lex FormatTokens -------------*- C++ ----*-===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file implements FormatTokenLexer, which tokenizes a source file
11/// into a FormatToken stream suitable for ClangFormat.
12///
13//===----------------------------------------------------------------------===//
14
15#include "FormatTokenLexer.h"
16#include "FormatToken.h"
17#include "clang/Basic/CharInfo.h"
18#include "clang/Basic/SourceLocation.h"
19#include "clang/Basic/SourceManager.h"
20#include "clang/Format/Format.h"
21#include "llvm/Support/Regex.h"
22
23namespace clang {
24namespace format {
25
26FormatTokenLexer::FormatTokenLexer(
27 const SourceManager &SourceMgr, FileID ID, unsigned Column,
28 const FormatStyle &Style, encoding::Encoding Encoding,
29 llvm::SpecificBumpPtrAllocator<FormatToken> &Allocator,
30 IdentifierTable &IdentTable)
31 : FormatTok(nullptr), IsFirstToken(true), StateStack({LexerState::NORMAL}),
32 Column(Column), TrailingWhitespace(0),
33 LangOpts(getFormattingLangOpts(Style)), SourceMgr(SourceMgr), ID(ID),
34 Style(Style), IdentTable(IdentTable), Keywords(IdentTable),
35 Encoding(Encoding), Allocator(Allocator), FirstInLineIndex(0),
36 FormattingDisabled(false), FormatOffRegex(Style.OneLineFormatOffRegex),
37 MacroBlockBeginRegex(Style.MacroBlockBegin),
38 MacroBlockEndRegex(Style.MacroBlockEnd) {
39 Lex.reset(p: new Lexer(ID, SourceMgr.getBufferOrFake(FID: ID), SourceMgr, LangOpts));
40 Lex->SetKeepWhitespaceMode(true);
41
42 for (const std::string &ForEachMacro : Style.ForEachMacros) {
43 auto Identifier = &IdentTable.get(Name: ForEachMacro);
44 Macros.insert(KV: {Identifier, TT_ForEachMacro});
45 }
46 for (const std::string &IfMacro : Style.IfMacros) {
47 auto Identifier = &IdentTable.get(Name: IfMacro);
48 Macros.insert(KV: {Identifier, TT_IfMacro});
49 }
50 for (const std::string &AttributeMacro : Style.AttributeMacros) {
51 auto Identifier = &IdentTable.get(Name: AttributeMacro);
52 Macros.insert(KV: {Identifier, TT_AttributeMacro});
53 }
54 for (const std::string &StatementMacro : Style.StatementMacros) {
55 auto Identifier = &IdentTable.get(Name: StatementMacro);
56 Macros.insert(KV: {Identifier, TT_StatementMacro});
57 }
58 for (const std::string &TypenameMacro : Style.TypenameMacros) {
59 auto Identifier = &IdentTable.get(Name: TypenameMacro);
60 Macros.insert(KV: {Identifier, TT_TypenameMacro});
61 }
62 for (const std::string &NamespaceMacro : Style.NamespaceMacros) {
63 auto Identifier = &IdentTable.get(Name: NamespaceMacro);
64 Macros.insert(KV: {Identifier, TT_NamespaceMacro});
65 }
66 for (const std::string &WhitespaceSensitiveMacro :
67 Style.WhitespaceSensitiveMacros) {
68 auto Identifier = &IdentTable.get(Name: WhitespaceSensitiveMacro);
69 Macros.insert(KV: {Identifier, TT_UntouchableMacroFunc});
70 }
71 for (const std::string &StatementAttributeLikeMacro :
72 Style.StatementAttributeLikeMacros) {
73 auto Identifier = &IdentTable.get(Name: StatementAttributeLikeMacro);
74 Macros.insert(KV: {Identifier, TT_StatementAttributeLikeMacro});
75 }
76
77 for (const auto &TemplateName : Style.TemplateNames)
78 TemplateNames.insert(Ptr: &IdentTable.get(Name: TemplateName));
79 for (const auto &TypeName : Style.TypeNames)
80 TypeNames.insert(Ptr: &IdentTable.get(Name: TypeName));
81 for (const auto &VariableTemplate : Style.VariableTemplates)
82 VariableTemplates.insert(Ptr: &IdentTable.get(Name: VariableTemplate));
83}
84
85ArrayRef<FormatToken *> FormatTokenLexer::lex() {
86 assert(Tokens.empty());
87 assert(FirstInLineIndex == 0);
88 enum { FO_None, FO_CurrentLine, FO_NextLine } FormatOff = FO_None;
89 do {
90 Tokens.push_back(Elt: getNextToken());
91 auto &Tok = *Tokens.back();
92 const auto NewlinesBefore = Tok.NewlinesBefore;
93 switch (FormatOff) {
94 case FO_CurrentLine:
95 if (NewlinesBefore == 0)
96 Tok.Finalized = true;
97 else
98 FormatOff = FO_None;
99 break;
100 case FO_NextLine:
101 if (NewlinesBefore > 1) {
102 FormatOff = FO_None;
103 } else {
104 Tok.Finalized = true;
105 FormatOff = FO_CurrentLine;
106 }
107 break;
108 default:
109 if (!FormattingDisabled && FormatOffRegex.match(String: Tok.TokenText)) {
110 if (Tok.is(Kind: tok::comment) &&
111 (NewlinesBefore > 0 || Tokens.size() == 1)) {
112 Tok.Finalized = true;
113 FormatOff = FO_NextLine;
114 } else {
115 for (auto *Token : reverse(C&: Tokens)) {
116 Token->Finalized = true;
117 if (Token->NewlinesBefore > 0)
118 break;
119 }
120 FormatOff = FO_CurrentLine;
121 }
122 }
123 }
124 if (Style.isJavaScript()) {
125 tryParseJSRegexLiteral();
126 handleTemplateStrings();
127 } else if (Style.isTextProto()) {
128 tryParsePythonComment();
129 }
130 tryMergePreviousTokens();
131 if (Style.isCSharp()) {
132 // This needs to come after tokens have been merged so that C#
133 // string literals are correctly identified.
134 handleCSharpVerbatimAndInterpolatedStrings();
135 } else if (Style.isTableGen()) {
136 handleTableGenMultilineString();
137 handleTableGenNumericLikeIdentifier();
138 }
139 if (Tokens.back()->NewlinesBefore > 0 || Tokens.back()->IsMultiline)
140 FirstInLineIndex = Tokens.size() - 1;
141 } while (Tokens.back()->isNot(Kind: tok::eof));
142 if (Style.InsertNewlineAtEOF) {
143 auto &TokEOF = *Tokens.back();
144 if (TokEOF.NewlinesBefore == 0) {
145 TokEOF.NewlinesBefore = 1;
146 TokEOF.OriginalColumn = 0;
147 }
148 }
149 return Tokens;
150}
151
152void FormatTokenLexer::tryMergePreviousTokens() {
153 if (tryMerge_TMacro())
154 return;
155 if (tryMergeConflictMarkers())
156 return;
157 if (tryMergeLessLess())
158 return;
159 if (tryMergeGreaterGreater())
160 return;
161 if (tryMergeForEach())
162 return;
163 if (Style.isCpp() && tryTransformTryUsageForC())
164 return;
165
166 if ((Style.Language == FormatStyle::LK_Cpp ||
167 Style.Language == FormatStyle::LK_ObjC) &&
168 tryMergeUserDefinedLiteral()) {
169 return;
170 }
171
172 if (Style.isJavaScript() || Style.isCSharp()) {
173 static const tok::TokenKind NullishCoalescingOperator[] = {tok::question,
174 tok::question};
175 static const tok::TokenKind NullPropagatingOperator[] = {tok::question,
176 tok::period};
177 static const tok::TokenKind FatArrow[] = {tok::equal, tok::greater};
178
179 if (tryMergeTokens(Kinds: FatArrow, NewType: TT_FatArrow))
180 return;
181 if (tryMergeTokens(Kinds: NullishCoalescingOperator, NewType: TT_NullCoalescingOperator)) {
182 // Treat like the "||" operator (as opposed to the ternary ?).
183 Tokens.back()->Tok.setKind(tok::pipepipe);
184 return;
185 }
186 if (tryMergeTokens(Kinds: NullPropagatingOperator, NewType: TT_NullPropagatingOperator)) {
187 // Treat like a regular "." access.
188 Tokens.back()->Tok.setKind(tok::period);
189 return;
190 }
191 if (tryMergeNullishCoalescingEqual())
192 return;
193
194 if (Style.isCSharp()) {
195 static const tok::TokenKind CSharpNullConditionalLSquare[] = {
196 tok::question, tok::l_square};
197
198 if (tryMergeCSharpKeywordVariables())
199 return;
200 if (tryMergeCSharpStringLiteral())
201 return;
202 if (tryTransformCSharpForEach())
203 return;
204 if (tryMergeTokens(Kinds: CSharpNullConditionalLSquare,
205 NewType: TT_CSharpNullConditionalLSquare)) {
206 // Treat like a regular "[" operator.
207 Tokens.back()->Tok.setKind(tok::l_square);
208 return;
209 }
210 }
211 }
212
213 if (tryMergeNSStringLiteral())
214 return;
215
216 if (Style.isJavaScript()) {
217 static const tok::TokenKind JSIdentity[] = {tok::equalequal, tok::equal};
218 static const tok::TokenKind JSNotIdentity[] = {tok::exclaimequal,
219 tok::equal};
220 static const tok::TokenKind JSShiftEqual[] = {tok::greater, tok::greater,
221 tok::greaterequal};
222 static const tok::TokenKind JSExponentiation[] = {tok::star, tok::star};
223 static const tok::TokenKind JSExponentiationEqual[] = {tok::star,
224 tok::starequal};
225 static const tok::TokenKind JSPipePipeEqual[] = {tok::pipepipe, tok::equal};
226 static const tok::TokenKind JSAndAndEqual[] = {tok::ampamp, tok::equal};
227
228 // FIXME: Investigate what token type gives the correct operator priority.
229 if (tryMergeTokens(Kinds: JSIdentity, NewType: TT_BinaryOperator))
230 return;
231 if (tryMergeTokens(Kinds: JSNotIdentity, NewType: TT_BinaryOperator))
232 return;
233 if (tryMergeTokens(Kinds: JSShiftEqual, NewType: TT_BinaryOperator))
234 return;
235 if (tryMergeTokens(Kinds: JSExponentiation, NewType: TT_JsExponentiation))
236 return;
237 if (tryMergeTokens(Kinds: JSExponentiationEqual, NewType: TT_JsExponentiationEqual)) {
238 Tokens.back()->Tok.setKind(tok::starequal);
239 return;
240 }
241 if (tryMergeTokens(Kinds: JSAndAndEqual, NewType: TT_JsAndAndEqual) ||
242 tryMergeTokens(Kinds: JSPipePipeEqual, NewType: TT_JsPipePipeEqual)) {
243 // Treat like the "=" assignment operator.
244 Tokens.back()->Tok.setKind(tok::equal);
245 return;
246 }
247 if (tryMergeJSPrivateIdentifier())
248 return;
249 } else if (Style.isJava()) {
250 static const tok::TokenKind JavaRightLogicalShiftAssign[] = {
251 tok::greater, tok::greater, tok::greaterequal};
252 if (tryMergeTokens(Kinds: JavaRightLogicalShiftAssign, NewType: TT_BinaryOperator))
253 return;
254 } else if (Style.isVerilog()) {
255 // Merge the number following a base like `'h?a0`.
256 if (Tokens.size() >= 3 && Tokens.end()[-3]->is(TT: TT_VerilogNumberBase) &&
257 Tokens.end()[-2]->is(Kind: tok::numeric_constant) &&
258 Tokens.back()->isOneOf(K1: tok::numeric_constant, K2: tok::identifier,
259 Ks: tok::question) &&
260 tryMergeTokens(Count: 2, NewType: TT_Unknown)) {
261 return;
262 }
263 // Part select.
264 if (tryMergeTokensAny(Kinds: {{tok::minus, tok::colon}, {tok::plus, tok::colon}},
265 NewType: TT_BitFieldColon)) {
266 return;
267 }
268 // Xnor. The combined token is treated as a caret which can also be either a
269 // unary or binary operator. The actual type is determined in
270 // TokenAnnotator. We also check the token length so we know it is not
271 // already a merged token.
272 if (Tokens.back()->TokenText.size() == 1 &&
273 tryMergeTokensAny(Kinds: {{tok::caret, tok::tilde}, {tok::tilde, tok::caret}},
274 NewType: TT_BinaryOperator)) {
275 Tokens.back()->Tok.setKind(tok::caret);
276 return;
277 }
278 // Signed shift and distribution weight.
279 if (tryMergeTokens(Kinds: {tok::less, tok::less}, NewType: TT_BinaryOperator)) {
280 Tokens.back()->Tok.setKind(tok::lessless);
281 return;
282 }
283 if (tryMergeTokens(Kinds: {tok::greater, tok::greater}, NewType: TT_BinaryOperator)) {
284 Tokens.back()->Tok.setKind(tok::greatergreater);
285 return;
286 }
287 if (tryMergeTokensAny(Kinds: {{tok::lessless, tok::equal},
288 {tok::lessless, tok::lessequal},
289 {tok::greatergreater, tok::equal},
290 {tok::greatergreater, tok::greaterequal},
291 {tok::colon, tok::equal},
292 {tok::colon, tok::slash}},
293 NewType: TT_BinaryOperator)) {
294 Tokens.back()->ForcedPrecedence = prec::Assignment;
295 return;
296 }
297 // Exponentiation, signed shift, case equality, and wildcard equality.
298 if (tryMergeTokensAny(Kinds: {{tok::star, tok::star},
299 {tok::lessless, tok::less},
300 {tok::greatergreater, tok::greater},
301 {tok::exclaimequal, tok::equal},
302 {tok::exclaimequal, tok::question},
303 {tok::equalequal, tok::equal},
304 {tok::equalequal, tok::question}},
305 NewType: TT_BinaryOperator)) {
306 return;
307 }
308 // Module paths in specify blocks and the implication and boolean equality
309 // operators.
310 if (tryMergeTokensAny(Kinds: {{tok::plusequal, tok::greater},
311 {tok::plus, tok::star, tok::greater},
312 {tok::minusequal, tok::greater},
313 {tok::minus, tok::star, tok::greater},
314 {tok::less, tok::arrow},
315 {tok::equal, tok::greater},
316 {tok::star, tok::greater},
317 {tok::pipeequal, tok::greater},
318 {tok::pipe, tok::arrow},
319 {tok::hash, tok::minus, tok::hash},
320 {tok::hash, tok::equal, tok::hash}},
321 NewType: TT_BinaryOperator) ||
322 Tokens.back()->is(Kind: tok::arrow)) {
323 Tokens.back()->ForcedPrecedence = prec::Comma;
324 return;
325 }
326 } else if (Style.isTableGen()) {
327 // TableGen's Multi line string starts with [{
328 if (tryMergeTokens(Kinds: {tok::l_square, tok::l_brace},
329 NewType: TT_TableGenMultiLineString)) {
330 // Set again with finalizing. This must never be annotated as other types.
331 Tokens.back()->setFinalizedType(TT_TableGenMultiLineString);
332 Tokens.back()->Tok.setKind(tok::string_literal);
333 return;
334 }
335 // TableGen's bang operator is the form !<name>.
336 // !cond is a special case with specific syntax.
337 if (tryMergeTokens(Kinds: {tok::exclaim, tok::identifier},
338 NewType: TT_TableGenBangOperator)) {
339 Tokens.back()->Tok.setKind(tok::identifier);
340 Tokens.back()->Tok.setIdentifierInfo(nullptr);
341 if (Tokens.back()->TokenText == "!cond")
342 Tokens.back()->setFinalizedType(TT_TableGenCondOperator);
343 else
344 Tokens.back()->setFinalizedType(TT_TableGenBangOperator);
345 return;
346 }
347 if (tryMergeTokens(Kinds: {tok::exclaim, tok::kw_if}, NewType: TT_TableGenBangOperator)) {
348 // Here, "! if" becomes "!if". That is, ! captures if even when the space
349 // exists. That is only one possibility in TableGen's syntax.
350 Tokens.back()->Tok.setKind(tok::identifier);
351 Tokens.back()->Tok.setIdentifierInfo(nullptr);
352 Tokens.back()->setFinalizedType(TT_TableGenBangOperator);
353 return;
354 }
355 // +, - with numbers are literals. Not unary operators.
356 if (tryMergeTokens(Kinds: {tok::plus, tok::numeric_constant}, NewType: TT_Unknown)) {
357 Tokens.back()->Tok.setKind(tok::numeric_constant);
358 return;
359 }
360 if (tryMergeTokens(Kinds: {tok::minus, tok::numeric_constant}, NewType: TT_Unknown)) {
361 Tokens.back()->Tok.setKind(tok::numeric_constant);
362 return;
363 }
364 }
365}
366
367bool FormatTokenLexer::tryMergeNSStringLiteral() {
368 if (Tokens.size() < 2)
369 return false;
370 auto &At = *(Tokens.end() - 2);
371 auto &String = *(Tokens.end() - 1);
372 if (At->isNot(Kind: tok::at) || String->isNot(Kind: tok::string_literal))
373 return false;
374 At->Tok.setKind(tok::string_literal);
375 At->TokenText = StringRef(At->TokenText.begin(),
376 String->TokenText.end() - At->TokenText.begin());
377 At->ColumnWidth += String->ColumnWidth;
378 At->setType(TT_ObjCStringLiteral);
379 Tokens.erase(CI: Tokens.end() - 1);
380 return true;
381}
382
383bool FormatTokenLexer::tryMergeJSPrivateIdentifier() {
384 // Merges #idenfier into a single identifier with the text #identifier
385 // but the token tok::identifier.
386 if (Tokens.size() < 2)
387 return false;
388 auto &Hash = *(Tokens.end() - 2);
389 auto &Identifier = *(Tokens.end() - 1);
390 if (Hash->isNot(Kind: tok::hash) || Identifier->isNot(Kind: tok::identifier))
391 return false;
392 Hash->Tok.setKind(tok::identifier);
393 Hash->TokenText =
394 StringRef(Hash->TokenText.begin(),
395 Identifier->TokenText.end() - Hash->TokenText.begin());
396 Hash->ColumnWidth += Identifier->ColumnWidth;
397 Hash->setType(TT_JsPrivateIdentifier);
398 Tokens.erase(CI: Tokens.end() - 1);
399 return true;
400}
401
402// Search for verbatim or interpolated string literals @"ABC" or
403// $"aaaaa{abc}aaaaa" i and mark the token as TT_CSharpStringLiteral, and to
404// prevent splitting of @, $ and ".
405// Merging of multiline verbatim strings with embedded '"' is handled in
406// handleCSharpVerbatimAndInterpolatedStrings with lower-level lexing.
407bool FormatTokenLexer::tryMergeCSharpStringLiteral() {
408 if (Tokens.size() < 2)
409 return false;
410
411 // Look for @"aaaaaa" or $"aaaaaa".
412 const auto String = *(Tokens.end() - 1);
413 if (String->isNot(Kind: tok::string_literal))
414 return false;
415
416 auto Prefix = *(Tokens.end() - 2);
417 if (Prefix->isNot(Kind: tok::at) && Prefix->TokenText != "$")
418 return false;
419
420 if (Tokens.size() > 2) {
421 const auto Tok = *(Tokens.end() - 3);
422 if ((Tok->TokenText == "$" && Prefix->is(Kind: tok::at)) ||
423 (Tok->is(Kind: tok::at) && Prefix->TokenText == "$")) {
424 // This looks like $@"aaa" or @$"aaa" so we need to combine all 3 tokens.
425 Tok->ColumnWidth += Prefix->ColumnWidth;
426 Tokens.erase(CI: Tokens.end() - 2);
427 Prefix = Tok;
428 }
429 }
430
431 // Convert back into just a string_literal.
432 Prefix->Tok.setKind(tok::string_literal);
433 Prefix->TokenText =
434 StringRef(Prefix->TokenText.begin(),
435 String->TokenText.end() - Prefix->TokenText.begin());
436 Prefix->ColumnWidth += String->ColumnWidth;
437 Prefix->setType(TT_CSharpStringLiteral);
438 Tokens.erase(CI: Tokens.end() - 1);
439 return true;
440}
441
442// Valid C# attribute targets:
443// https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/concepts/attributes/#attribute-targets
444const llvm::StringSet<> FormatTokenLexer::CSharpAttributeTargets = {
445 "assembly", "module", "field", "event", "method",
446 "param", "property", "return", "type",
447};
448
449bool FormatTokenLexer::tryMergeNullishCoalescingEqual() {
450 if (Tokens.size() < 2)
451 return false;
452 auto &NullishCoalescing = *(Tokens.end() - 2);
453 auto &Equal = *(Tokens.end() - 1);
454 if (NullishCoalescing->isNot(Kind: TT_NullCoalescingOperator) ||
455 Equal->isNot(Kind: tok::equal)) {
456 return false;
457 }
458 NullishCoalescing->Tok.setKind(tok::equal); // no '??=' in clang tokens.
459 NullishCoalescing->TokenText =
460 StringRef(NullishCoalescing->TokenText.begin(),
461 Equal->TokenText.end() - NullishCoalescing->TokenText.begin());
462 NullishCoalescing->ColumnWidth += Equal->ColumnWidth;
463 NullishCoalescing->setType(TT_NullCoalescingEqual);
464 Tokens.erase(CI: Tokens.end() - 1);
465 return true;
466}
467
468bool FormatTokenLexer::tryMergeCSharpKeywordVariables() {
469 if (Tokens.size() < 2)
470 return false;
471 const auto At = *(Tokens.end() - 2);
472 if (At->isNot(Kind: tok::at))
473 return false;
474 const auto Keyword = *(Tokens.end() - 1);
475 if (Keyword->TokenText == "$")
476 return false;
477 if (!Keywords.isCSharpKeyword(Tok: *Keyword))
478 return false;
479
480 At->Tok.setKind(tok::identifier);
481 At->TokenText = StringRef(At->TokenText.begin(),
482 Keyword->TokenText.end() - At->TokenText.begin());
483 At->ColumnWidth += Keyword->ColumnWidth;
484 At->setType(Keyword->getType());
485 Tokens.erase(CI: Tokens.end() - 1);
486 return true;
487}
488
489// In C# transform identifier foreach into kw_foreach
490bool FormatTokenLexer::tryTransformCSharpForEach() {
491 if (Tokens.size() < 1)
492 return false;
493 auto &Identifier = *(Tokens.end() - 1);
494 if (Identifier->isNot(Kind: tok::identifier))
495 return false;
496 if (Identifier->TokenText != "foreach")
497 return false;
498
499 Identifier->setType(TT_ForEachMacro);
500 Identifier->Tok.setKind(tok::kw_for);
501 return true;
502}
503
504bool FormatTokenLexer::tryMergeForEach() {
505 if (Tokens.size() < 2)
506 return false;
507 auto &For = *(Tokens.end() - 2);
508 auto &Each = *(Tokens.end() - 1);
509 if (For->isNot(Kind: tok::kw_for))
510 return false;
511 if (Each->isNot(Kind: tok::identifier))
512 return false;
513 if (Each->TokenText != "each")
514 return false;
515
516 For->setType(TT_ForEachMacro);
517 For->Tok.setKind(tok::kw_for);
518
519 For->TokenText = StringRef(For->TokenText.begin(),
520 Each->TokenText.end() - For->TokenText.begin());
521 For->ColumnWidth += Each->ColumnWidth;
522 Tokens.erase(CI: Tokens.end() - 1);
523 return true;
524}
525
526bool FormatTokenLexer::tryTransformTryUsageForC() {
527 if (Tokens.size() < 2)
528 return false;
529 auto &Try = *(Tokens.end() - 2);
530 if (Try->isNot(Kind: tok::kw_try))
531 return false;
532 auto &Next = *(Tokens.end() - 1);
533 if (Next->isOneOf(K1: tok::l_brace, K2: tok::colon, Ks: tok::hash, Ks: tok::comment))
534 return false;
535
536 if (Tokens.size() > 2) {
537 auto &At = *(Tokens.end() - 3);
538 if (At->is(Kind: tok::at))
539 return false;
540 }
541
542 Try->Tok.setKind(tok::identifier);
543 return true;
544}
545
546bool FormatTokenLexer::tryMergeLessLess() {
547 // Merge X,less,less,Y into X,lessless,Y unless X or Y is less.
548 if (Tokens.size() < 3)
549 return false;
550
551 auto First = Tokens.end() - 3;
552 if (First[0]->isNot(Kind: tok::less) || First[1]->isNot(Kind: tok::less))
553 return false;
554
555 // Only merge if there currently is no whitespace between the two "<".
556 if (First[1]->hasWhitespaceBefore())
557 return false;
558
559 auto X = Tokens.size() > 3 ? First[-1] : nullptr;
560 if (X && X->is(Kind: tok::less))
561 return false;
562
563 auto Y = First[2];
564 if ((!X || X->isNot(Kind: tok::kw_operator)) && Y->is(Kind: tok::less))
565 return false;
566
567 First[0]->Tok.setKind(tok::lessless);
568 First[0]->TokenText = "<<";
569 First[0]->ColumnWidth += 1;
570 Tokens.erase(CI: Tokens.end() - 2);
571 return true;
572}
573
574bool FormatTokenLexer::tryMergeGreaterGreater() {
575 // Merge kw_operator,greater,greater into kw_operator,greatergreater.
576 if (Tokens.size() < 2)
577 return false;
578
579 auto First = Tokens.end() - 2;
580 if (First[0]->isNot(Kind: tok::greater) || First[1]->isNot(Kind: tok::greater))
581 return false;
582
583 // Only merge if there currently is no whitespace between the first two ">".
584 if (First[1]->hasWhitespaceBefore())
585 return false;
586
587 auto Tok = Tokens.size() > 2 ? First[-1] : nullptr;
588 if (Tok && Tok->isNot(Kind: tok::kw_operator))
589 return false;
590
591 First[0]->Tok.setKind(tok::greatergreater);
592 First[0]->TokenText = ">>";
593 First[0]->ColumnWidth += 1;
594 Tokens.erase(CI: Tokens.end() - 1);
595 return true;
596}
597
598bool FormatTokenLexer::tryMergeUserDefinedLiteral() {
599 if (Tokens.size() < 2)
600 return false;
601
602 auto *First = Tokens.end() - 2;
603 auto &Suffix = First[1];
604 if (Suffix->hasWhitespaceBefore() || Suffix->TokenText != "$")
605 return false;
606
607 auto &Literal = First[0];
608 if (!Literal->Tok.isLiteral())
609 return false;
610
611 auto &Text = Literal->TokenText;
612 if (!Text.ends_with(Suffix: "_"))
613 return false;
614
615 Text = StringRef(Text.data(), Text.size() + 1);
616 ++Literal->ColumnWidth;
617 Tokens.erase(CI: &Suffix);
618 return true;
619}
620
621bool FormatTokenLexer::tryMergeTokens(ArrayRef<tok::TokenKind> Kinds,
622 TokenType NewType) {
623 if (Tokens.size() < Kinds.size())
624 return false;
625
626 const auto *First = Tokens.end() - Kinds.size();
627 for (unsigned i = 0; i < Kinds.size(); ++i)
628 if (First[i]->isNot(Kind: Kinds[i]))
629 return false;
630
631 return tryMergeTokens(Count: Kinds.size(), NewType);
632}
633
634bool FormatTokenLexer::tryMergeTokens(size_t Count, TokenType NewType) {
635 if (Tokens.size() < Count)
636 return false;
637
638 const auto *First = Tokens.end() - Count;
639 unsigned AddLength = 0;
640 for (size_t i = 1; i < Count; ++i) {
641 // If there is whitespace separating the token and the previous one,
642 // they should not be merged.
643 if (First[i]->hasWhitespaceBefore())
644 return false;
645 AddLength += First[i]->TokenText.size();
646 }
647
648 Tokens.resize(N: Tokens.size() - Count + 1);
649 First[0]->TokenText = StringRef(First[0]->TokenText.data(),
650 First[0]->TokenText.size() + AddLength);
651 First[0]->ColumnWidth += AddLength;
652 First[0]->setType(NewType);
653 return true;
654}
655
656bool FormatTokenLexer::tryMergeTokensAny(
657 ArrayRef<ArrayRef<tok::TokenKind>> Kinds, TokenType NewType) {
658 return llvm::any_of(Range&: Kinds, P: [this, NewType](ArrayRef<tok::TokenKind> Kinds) {
659 return tryMergeTokens(Kinds, NewType);
660 });
661}
662
663// Returns \c true if \p Tok can only be followed by an operand in JavaScript.
664bool FormatTokenLexer::precedesOperand(FormatToken *Tok) {
665 // NB: This is not entirely correct, as an r_paren can introduce an operand
666 // location in e.g. `if (foo) /bar/.exec(...);`. That is a rare enough
667 // corner case to not matter in practice, though.
668 return Tok->isOneOf(K1: tok::period, K2: tok::l_paren, Ks: tok::comma, Ks: tok::l_brace,
669 Ks: tok::r_brace, Ks: tok::l_square, Ks: tok::semi, Ks: tok::exclaim,
670 Ks: tok::colon, Ks: tok::question, Ks: tok::tilde) ||
671 Tok->isOneOf(K1: tok::kw_return, K2: tok::kw_do, Ks: tok::kw_case, Ks: tok::kw_throw,
672 Ks: tok::kw_else, Ks: tok::kw_void, Ks: tok::kw_typeof,
673 Ks: Keywords.kw_instanceof, Ks: Keywords.kw_in) ||
674 Tok->isPlacementOperator() || Tok->isBinaryOperator();
675}
676
677bool FormatTokenLexer::canPrecedeRegexLiteral(FormatToken *Prev) {
678 if (!Prev)
679 return true;
680
681 // Regex literals can only follow after prefix unary operators, not after
682 // postfix unary operators. If the '++' is followed by a non-operand
683 // introducing token, the slash here is the operand and not the start of a
684 // regex.
685 // `!` is an unary prefix operator, but also a post-fix operator that casts
686 // away nullability, so the same check applies.
687 if (Prev->isOneOf(K1: tok::plusplus, K2: tok::minusminus, Ks: tok::exclaim))
688 return Tokens.size() < 3 || precedesOperand(Tok: Tokens[Tokens.size() - 3]);
689
690 // The previous token must introduce an operand location where regex
691 // literals can occur.
692 if (!precedesOperand(Tok: Prev))
693 return false;
694
695 return true;
696}
697
698void FormatTokenLexer::tryParseJavaTextBlock() {
699 if (FormatTok->TokenText != "\"\"")
700 return;
701
702 const auto *S = Lex->getBufferLocation();
703 const auto *End = Lex->getBuffer().end();
704
705 if (S == End || *S != '\"')
706 return;
707
708 ++S; // Skip the `"""` that begins a text block.
709
710 // Find the `"""` that ends the text block.
711 for (int Count = 0; Count < 3 && S < End; ++S) {
712 switch (*S) {
713 case '\\':
714 Count = -1;
715 break;
716 case '\"':
717 ++Count;
718 break;
719 default:
720 Count = 0;
721 }
722 }
723
724 // Ignore the possibly invalid text block.
725 resetLexer(Offset: SourceMgr.getFileOffset(SpellingLoc: Lex->getSourceLocation(Loc: S)));
726}
727
728// Tries to parse a JavaScript Regex literal starting at the current token,
729// if that begins with a slash and is in a location where JavaScript allows
730// regex literals. Changes the current token to a regex literal and updates
731// its text if successful.
732void FormatTokenLexer::tryParseJSRegexLiteral() {
733 FormatToken *RegexToken = Tokens.back();
734 if (!RegexToken->isOneOf(K1: tok::slash, K2: tok::slashequal))
735 return;
736
737 FormatToken *Prev = nullptr;
738 for (FormatToken *FT : llvm::drop_begin(RangeOrContainer: llvm::reverse(C&: Tokens))) {
739 // NB: Because previous pointers are not initialized yet, this cannot use
740 // Token.getPreviousNonComment.
741 if (FT->isNot(Kind: tok::comment)) {
742 Prev = FT;
743 break;
744 }
745 }
746
747 if (!canPrecedeRegexLiteral(Prev))
748 return;
749
750 // 'Manually' lex ahead in the current file buffer.
751 const char *Offset = Lex->getBufferLocation();
752 const char *RegexBegin = Offset - RegexToken->TokenText.size();
753 StringRef Buffer = Lex->getBuffer();
754 bool InCharacterClass = false;
755 bool HaveClosingSlash = false;
756 for (; !HaveClosingSlash && Offset != Buffer.end(); ++Offset) {
757 // Regular expressions are terminated with a '/', which can only be
758 // escaped using '\' or a character class between '[' and ']'.
759 // See http://www.ecma-international.org/ecma-262/5.1/#sec-7.8.5.
760 switch (*Offset) {
761 case '\\':
762 // Skip the escaped character.
763 ++Offset;
764 break;
765 case '[':
766 InCharacterClass = true;
767 break;
768 case ']':
769 InCharacterClass = false;
770 break;
771 case '/':
772 if (!InCharacterClass)
773 HaveClosingSlash = true;
774 break;
775 }
776 }
777
778 RegexToken->setType(TT_RegexLiteral);
779 // Treat regex literals like other string_literals.
780 RegexToken->Tok.setKind(tok::string_literal);
781 RegexToken->TokenText = StringRef(RegexBegin, Offset - RegexBegin);
782 RegexToken->ColumnWidth = RegexToken->TokenText.size();
783
784 resetLexer(Offset: SourceMgr.getFileOffset(SpellingLoc: Lex->getSourceLocation(Loc: Offset)));
785}
786
787static auto lexCSharpString(const char *Begin, const char *End, bool Verbatim,
788 bool Interpolated) {
789 auto Repeated = [&Begin, End]() {
790 return Begin + 1 < End && Begin[1] == Begin[0];
791 };
792
793 // Look for a terminating '"' in the current file buffer.
794 // Make no effort to format code within an interpolated or verbatim string.
795 //
796 // Interpolated strings could contain { } with " characters inside.
797 // $"{x ?? "null"}"
798 // should not be split into $"{x ?? ", null, "}" but should be treated as a
799 // single string-literal.
800 //
801 // We opt not to try and format expressions inside {} within a C#
802 // interpolated string. Formatting expressions within an interpolated string
803 // would require similar work as that done for JavaScript template strings
804 // in `handleTemplateStrings()`.
805 for (int UnmatchedOpeningBraceCount = 0; Begin < End; ++Begin) {
806 switch (*Begin) {
807 case '\\':
808 if (!Verbatim)
809 ++Begin;
810 break;
811 case '{':
812 if (Interpolated) {
813 // {{ inside an interpolated string is escaped, so skip it.
814 if (Repeated())
815 ++Begin;
816 else
817 ++UnmatchedOpeningBraceCount;
818 }
819 break;
820 case '}':
821 if (Interpolated) {
822 // }} inside an interpolated string is escaped, so skip it.
823 if (Repeated())
824 ++Begin;
825 else if (UnmatchedOpeningBraceCount > 0)
826 --UnmatchedOpeningBraceCount;
827 else
828 return End;
829 }
830 break;
831 case '"':
832 if (UnmatchedOpeningBraceCount > 0)
833 break;
834 // "" within a verbatim string is an escaped double quote: skip it.
835 if (Verbatim && Repeated()) {
836 ++Begin;
837 break;
838 }
839 return Begin;
840 }
841 }
842
843 return End;
844}
845
846void FormatTokenLexer::handleCSharpVerbatimAndInterpolatedStrings() {
847 FormatToken *CSharpStringLiteral = Tokens.back();
848
849 if (CSharpStringLiteral->isNot(Kind: TT_CSharpStringLiteral))
850 return;
851
852 auto &TokenText = CSharpStringLiteral->TokenText;
853
854 bool Verbatim = false;
855 bool Interpolated = false;
856 if (TokenText.starts_with(Prefix: R"($@")") || TokenText.starts_with(Prefix: R"(@$")")) {
857 Verbatim = true;
858 Interpolated = true;
859 } else if (TokenText.starts_with(Prefix: R"(@")")) {
860 Verbatim = true;
861 } else if (TokenText.starts_with(Prefix: R"($")")) {
862 Interpolated = true;
863 }
864
865 // Deal with multiline strings.
866 if (!Verbatim && !Interpolated)
867 return;
868
869 const char *StrBegin = Lex->getBufferLocation() - TokenText.size();
870 const char *Offset = StrBegin;
871 Offset += Verbatim && Interpolated ? 3 : 2;
872
873 const auto End = Lex->getBuffer().end();
874 Offset = lexCSharpString(Begin: Offset, End, Verbatim, Interpolated);
875
876 // Make no attempt to format code properly if a verbatim string is
877 // unterminated.
878 if (Offset >= End)
879 return;
880
881 StringRef LiteralText(StrBegin, Offset - StrBegin + 1);
882 TokenText = LiteralText;
883
884 // Adjust width for potentially multiline string literals.
885 size_t FirstBreak = LiteralText.find(C: '\n');
886 StringRef FirstLineText = FirstBreak == StringRef::npos
887 ? LiteralText
888 : LiteralText.substr(Start: 0, N: FirstBreak);
889 CSharpStringLiteral->ColumnWidth = encoding::columnWidthWithTabs(
890 Text: FirstLineText, StartColumn: CSharpStringLiteral->OriginalColumn, TabWidth: Style.TabWidth,
891 Encoding);
892 size_t LastBreak = LiteralText.rfind(C: '\n');
893 if (LastBreak != StringRef::npos) {
894 CSharpStringLiteral->IsMultiline = true;
895 unsigned StartColumn = 0;
896 CSharpStringLiteral->LastLineColumnWidth =
897 encoding::columnWidthWithTabs(Text: LiteralText.substr(Start: LastBreak + 1),
898 StartColumn, TabWidth: Style.TabWidth, Encoding);
899 }
900
901 assert(Offset < End);
902 resetLexer(Offset: SourceMgr.getFileOffset(SpellingLoc: Lex->getSourceLocation(Loc: Offset + 1)));
903}
904
905void FormatTokenLexer::handleTableGenMultilineString() {
906 FormatToken *MultiLineString = Tokens.back();
907 if (MultiLineString->isNot(Kind: TT_TableGenMultiLineString))
908 return;
909
910 auto OpenOffset = Lex->getCurrentBufferOffset() - 2 /* "[{" */;
911 // "}]" is the end of multi line string.
912 auto CloseOffset = Lex->getBuffer().find(Str: "}]", From: OpenOffset);
913 if (CloseOffset == StringRef::npos)
914 return;
915 auto Text = Lex->getBuffer().substr(Start: OpenOffset, N: CloseOffset - OpenOffset + 2);
916 MultiLineString->TokenText = Text;
917 resetLexer(Offset: SourceMgr.getFileOffset(
918 SpellingLoc: Lex->getSourceLocation(Loc: Lex->getBufferLocation() - 2 + Text.size())));
919 auto FirstLineText = Text;
920 auto FirstBreak = Text.find(C: '\n');
921 // Set ColumnWidth and LastLineColumnWidth when it has multiple lines.
922 if (FirstBreak != StringRef::npos) {
923 MultiLineString->IsMultiline = true;
924 FirstLineText = Text.substr(Start: 0, N: FirstBreak + 1);
925 // LastLineColumnWidth holds the width of the last line.
926 auto LastBreak = Text.rfind(C: '\n');
927 MultiLineString->LastLineColumnWidth = encoding::columnWidthWithTabs(
928 Text: Text.substr(Start: LastBreak + 1), StartColumn: MultiLineString->OriginalColumn,
929 TabWidth: Style.TabWidth, Encoding);
930 }
931 // ColumnWidth holds only the width of the first line.
932 MultiLineString->ColumnWidth = encoding::columnWidthWithTabs(
933 Text: FirstLineText, StartColumn: MultiLineString->OriginalColumn, TabWidth: Style.TabWidth, Encoding);
934}
935
936void FormatTokenLexer::handleTableGenNumericLikeIdentifier() {
937 FormatToken *Tok = Tokens.back();
938 // TableGen identifiers can begin with digits. Such tokens are lexed as
939 // numeric_constant now.
940 if (Tok->isNot(Kind: tok::numeric_constant))
941 return;
942 StringRef Text = Tok->TokenText;
943 // The following check is based on llvm::TGLexer::LexToken.
944 // That lexes the token as a number if any of the following holds:
945 // 1. It starts with '+', '-'.
946 // 2. All the characters are digits.
947 // 3. The first non-digit character is 'b', and the next is '0' or '1'.
948 // 4. The first non-digit character is 'x', and the next is a hex digit.
949 // Note that in the case 3 and 4, if the next character does not exists in
950 // this token, the token is an identifier.
951 if (Text.size() < 1 || Text[0] == '+' || Text[0] == '-')
952 return;
953 const auto NonDigitPos = Text.find_if(F: [](char C) { return !isdigit(C); });
954 // All the characters are digits
955 if (NonDigitPos == StringRef::npos)
956 return;
957 char FirstNonDigit = Text[NonDigitPos];
958 if (NonDigitPos < Text.size() - 1) {
959 char TheNext = Text[NonDigitPos + 1];
960 // Regarded as a binary number.
961 if (FirstNonDigit == 'b' && (TheNext == '0' || TheNext == '1'))
962 return;
963 // Regarded as hex number.
964 if (FirstNonDigit == 'x' && isxdigit(TheNext))
965 return;
966 }
967 if (isalpha(FirstNonDigit) || FirstNonDigit == '_') {
968 // This is actually an identifier in TableGen.
969 Tok->Tok.setKind(tok::identifier);
970 Tok->Tok.setIdentifierInfo(nullptr);
971 }
972}
973
974void FormatTokenLexer::handleTemplateStrings() {
975 FormatToken *BacktickToken = Tokens.back();
976
977 if (BacktickToken->is(Kind: tok::l_brace)) {
978 StateStack.push(x: LexerState::NORMAL);
979 return;
980 }
981 if (BacktickToken->is(Kind: tok::r_brace)) {
982 if (StateStack.size() == 1)
983 return;
984 StateStack.pop();
985 if (StateStack.top() != LexerState::TEMPLATE_STRING)
986 return;
987 // If back in TEMPLATE_STRING, fallthrough and continue parsing the
988 } else if (BacktickToken->is(Kind: tok::unknown) &&
989 BacktickToken->TokenText == "`") {
990 StateStack.push(x: LexerState::TEMPLATE_STRING);
991 } else {
992 return; // Not actually a template
993 }
994
995 // 'Manually' lex ahead in the current file buffer.
996 const char *Offset = Lex->getBufferLocation();
997 const char *TmplBegin = Offset - BacktickToken->TokenText.size(); // at "`"
998 for (; Offset != Lex->getBuffer().end(); ++Offset) {
999 if (Offset[0] == '`') {
1000 StateStack.pop();
1001 ++Offset;
1002 break;
1003 }
1004 if (Offset[0] == '\\') {
1005 ++Offset; // Skip the escaped character.
1006 } else if (Offset + 1 < Lex->getBuffer().end() && Offset[0] == '$' &&
1007 Offset[1] == '{') {
1008 // '${' introduces an expression interpolation in the template string.
1009 StateStack.push(x: LexerState::NORMAL);
1010 Offset += 2;
1011 break;
1012 }
1013 }
1014
1015 StringRef LiteralText(TmplBegin, Offset - TmplBegin);
1016 BacktickToken->setType(TT_TemplateString);
1017 BacktickToken->Tok.setKind(tok::string_literal);
1018 BacktickToken->TokenText = LiteralText;
1019
1020 // Adjust width for potentially multiline string literals.
1021 size_t FirstBreak = LiteralText.find(C: '\n');
1022 StringRef FirstLineText = FirstBreak == StringRef::npos
1023 ? LiteralText
1024 : LiteralText.substr(Start: 0, N: FirstBreak);
1025 BacktickToken->ColumnWidth = encoding::columnWidthWithTabs(
1026 Text: FirstLineText, StartColumn: BacktickToken->OriginalColumn, TabWidth: Style.TabWidth, Encoding);
1027 size_t LastBreak = LiteralText.rfind(C: '\n');
1028 if (LastBreak != StringRef::npos) {
1029 BacktickToken->IsMultiline = true;
1030 unsigned StartColumn = 0; // The template tail spans the entire line.
1031 BacktickToken->LastLineColumnWidth =
1032 encoding::columnWidthWithTabs(Text: LiteralText.substr(Start: LastBreak + 1),
1033 StartColumn, TabWidth: Style.TabWidth, Encoding);
1034 }
1035
1036 SourceLocation loc = Lex->getSourceLocation(Loc: Offset);
1037 resetLexer(Offset: SourceMgr.getFileOffset(SpellingLoc: loc));
1038}
1039
1040void FormatTokenLexer::tryParsePythonComment() {
1041 FormatToken *HashToken = Tokens.back();
1042 if (!HashToken->isOneOf(K1: tok::hash, K2: tok::hashhash))
1043 return;
1044 // Turn the remainder of this line into a comment.
1045 const char *CommentBegin =
1046 Lex->getBufferLocation() - HashToken->TokenText.size(); // at "#"
1047 size_t From = CommentBegin - Lex->getBuffer().begin();
1048 size_t To = Lex->getBuffer().find_first_of(C: '\n', From);
1049 if (To == StringRef::npos)
1050 To = Lex->getBuffer().size();
1051 size_t Len = To - From;
1052 HashToken->setType(TT_LineComment);
1053 HashToken->Tok.setKind(tok::comment);
1054 HashToken->TokenText = Lex->getBuffer().substr(Start: From, N: Len);
1055 SourceLocation Loc = To < Lex->getBuffer().size()
1056 ? Lex->getSourceLocation(Loc: CommentBegin + Len)
1057 : SourceMgr.getLocForEndOfFile(FID: ID);
1058 resetLexer(Offset: SourceMgr.getFileOffset(SpellingLoc: Loc));
1059}
1060
1061bool FormatTokenLexer::tryMerge_TMacro() {
1062 if (Tokens.size() < 4)
1063 return false;
1064 FormatToken *Last = Tokens.back();
1065 if (Last->isNot(Kind: tok::r_paren))
1066 return false;
1067
1068 FormatToken *String = Tokens[Tokens.size() - 2];
1069 if (String->isNot(Kind: tok::string_literal) || String->IsMultiline)
1070 return false;
1071
1072 if (Tokens[Tokens.size() - 3]->isNot(Kind: tok::l_paren))
1073 return false;
1074
1075 FormatToken *Macro = Tokens[Tokens.size() - 4];
1076 if (Macro->TokenText != "_T")
1077 return false;
1078
1079 const char *Start = Macro->TokenText.data();
1080 const char *End = Last->TokenText.data() + Last->TokenText.size();
1081 String->TokenText = StringRef(Start, End - Start);
1082 String->IsFirst = Macro->IsFirst;
1083 String->LastNewlineOffset = Macro->LastNewlineOffset;
1084 String->WhitespaceRange = Macro->WhitespaceRange;
1085 String->OriginalColumn = Macro->OriginalColumn;
1086 String->ColumnWidth = encoding::columnWidthWithTabs(
1087 Text: String->TokenText, StartColumn: String->OriginalColumn, TabWidth: Style.TabWidth, Encoding);
1088 String->NewlinesBefore = Macro->NewlinesBefore;
1089 String->HasUnescapedNewline = Macro->HasUnescapedNewline;
1090
1091 Tokens.pop_back();
1092 Tokens.pop_back();
1093 Tokens.pop_back();
1094 Tokens.back() = String;
1095 if (FirstInLineIndex >= Tokens.size())
1096 FirstInLineIndex = Tokens.size() - 1;
1097 return true;
1098}
1099
1100bool FormatTokenLexer::tryMergeConflictMarkers() {
1101 if (Tokens.back()->NewlinesBefore == 0 && Tokens.back()->isNot(Kind: tok::eof))
1102 return false;
1103
1104 // Conflict lines look like:
1105 // <marker> <text from the vcs>
1106 // For example:
1107 // >>>>>>> /file/in/file/system at revision 1234
1108 //
1109 // We merge all tokens in a line that starts with a conflict marker
1110 // into a single token with a special token type that the unwrapped line
1111 // parser will use to correctly rebuild the underlying code.
1112
1113 FileID ID;
1114 // Get the position of the first token in the line.
1115 unsigned FirstInLineOffset;
1116 std::tie(args&: ID, args&: FirstInLineOffset) = SourceMgr.getDecomposedLoc(
1117 Loc: Tokens[FirstInLineIndex]->getStartOfNonWhitespace());
1118 StringRef Buffer = SourceMgr.getBufferOrFake(FID: ID).getBuffer();
1119 // Calculate the offset of the start of the current line.
1120 auto LineOffset = Buffer.rfind(C: '\n', From: FirstInLineOffset);
1121 if (LineOffset == StringRef::npos)
1122 LineOffset = 0;
1123 else
1124 ++LineOffset;
1125
1126 auto FirstSpace = Buffer.find_first_of(Chars: " \n", From: LineOffset);
1127 StringRef LineStart;
1128 if (FirstSpace == StringRef::npos)
1129 LineStart = Buffer.substr(Start: LineOffset);
1130 else
1131 LineStart = Buffer.substr(Start: LineOffset, N: FirstSpace - LineOffset);
1132
1133 TokenType Type = TT_Unknown;
1134 if (LineStart == "<<<<<<<" || LineStart == ">>>>") {
1135 Type = TT_ConflictStart;
1136 } else if (LineStart == "|||||||" || LineStart == "=======" ||
1137 LineStart == "====") {
1138 Type = TT_ConflictAlternative;
1139 } else if (LineStart == ">>>>>>>" || LineStart == "<<<<") {
1140 Type = TT_ConflictEnd;
1141 }
1142
1143 if (Type != TT_Unknown) {
1144 FormatToken *Next = Tokens.back();
1145
1146 Tokens.resize(N: FirstInLineIndex + 1);
1147 // We do not need to build a complete token here, as we will skip it
1148 // during parsing anyway (as we must not touch whitespace around conflict
1149 // markers).
1150 Tokens.back()->setType(Type);
1151 Tokens.back()->Tok.setKind(tok::kw___unknown_anytype);
1152
1153 Tokens.push_back(Elt: Next);
1154 return true;
1155 }
1156
1157 return false;
1158}
1159
1160FormatToken *FormatTokenLexer::getStashedToken() {
1161 // Create a synthesized second '>' or '<' token.
1162 Token Tok = FormatTok->Tok;
1163 StringRef TokenText = FormatTok->TokenText;
1164
1165 unsigned OriginalColumn = FormatTok->OriginalColumn;
1166 FormatTok = new (Allocator.Allocate()) FormatToken;
1167 FormatTok->Tok = Tok;
1168 SourceLocation TokLocation =
1169 FormatTok->Tok.getLocation().getLocWithOffset(Offset: Tok.getLength() - 1);
1170 FormatTok->Tok.setLocation(TokLocation);
1171 FormatTok->WhitespaceRange = SourceRange(TokLocation, TokLocation);
1172 FormatTok->TokenText = TokenText;
1173 FormatTok->ColumnWidth = 1;
1174 FormatTok->OriginalColumn = OriginalColumn + 1;
1175
1176 return FormatTok;
1177}
1178
1179/// Truncate the current token to the new length and make the lexer continue
1180/// from the end of the truncated token. Used for other languages that have
1181/// different token boundaries, like JavaScript in which a comment ends at a
1182/// line break regardless of whether the line break follows a backslash. Also
1183/// used to set the lexer to the end of whitespace if the lexer regards
1184/// whitespace and an unrecognized symbol as one token.
1185void FormatTokenLexer::truncateToken(size_t NewLen) {
1186 assert(NewLen <= FormatTok->TokenText.size());
1187 resetLexer(Offset: SourceMgr.getFileOffset(SpellingLoc: Lex->getSourceLocation(
1188 Loc: Lex->getBufferLocation() - FormatTok->TokenText.size() + NewLen)));
1189 FormatTok->TokenText = FormatTok->TokenText.substr(Start: 0, N: NewLen);
1190 FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
1191 Text: FormatTok->TokenText, StartColumn: FormatTok->OriginalColumn, TabWidth: Style.TabWidth,
1192 Encoding);
1193 FormatTok->Tok.setLength(NewLen);
1194}
1195
1196/// Count the length of leading whitespace in a token.
1197static size_t countLeadingWhitespace(StringRef Text) {
1198 // Basically counting the length matched by this regex.
1199 // "^([\n\r\f\v \t]|(\\\\|\\?\\?/)[\n\r])+"
1200 // Directly using the regex turned out to be slow. With the regex
1201 // version formatting all files in this directory took about 1.25
1202 // seconds. This version took about 0.5 seconds.
1203 const unsigned char *const Begin = Text.bytes_begin();
1204 const unsigned char *const End = Text.bytes_end();
1205 const unsigned char *Cur = Begin;
1206 while (Cur < End) {
1207 if (isWhitespace(c: Cur[0])) {
1208 ++Cur;
1209 } else if (Cur[0] == '\\') {
1210 // A backslash followed by optional horizontal whitespaces (P22232R2) and
1211 // then a newline always escapes the newline.
1212 // The source has a null byte at the end. So the end of the entire input
1213 // isn't reached yet. Also the lexer doesn't break apart an escaped
1214 // newline.
1215 const auto *Lookahead = Cur + 1;
1216 while (isHorizontalWhitespace(c: *Lookahead))
1217 ++Lookahead;
1218 // No line splice found; the backslash is a token.
1219 if (!isVerticalWhitespace(c: *Lookahead))
1220 break;
1221 // Splice found, consume it.
1222 Cur = Lookahead + 1;
1223 } else if (Cur[0] == '?' && Cur[1] == '?' && Cur[2] == '/' &&
1224 (Cur[3] == '\n' || Cur[3] == '\r')) {
1225 // Newlines can also be escaped by a '?' '?' '/' trigraph. By the way, the
1226 // characters are quoted individually in this comment because if we write
1227 // them together some compilers warn that we have a trigraph in the code.
1228 assert(End - Cur >= 4);
1229 Cur += 4;
1230 } else {
1231 break;
1232 }
1233 }
1234 return Cur - Begin;
1235}
1236
1237FormatToken *FormatTokenLexer::getNextToken() {
1238 if (StateStack.top() == LexerState::TOKEN_STASHED) {
1239 StateStack.pop();
1240 return getStashedToken();
1241 }
1242
1243 FormatTok = new (Allocator.Allocate()) FormatToken;
1244 readRawToken(Tok&: *FormatTok);
1245 SourceLocation WhitespaceStart =
1246 FormatTok->Tok.getLocation().getLocWithOffset(Offset: -TrailingWhitespace);
1247 FormatTok->IsFirst = IsFirstToken;
1248 IsFirstToken = false;
1249
1250 // Consume and record whitespace until we find a significant token.
1251 // Some tok::unknown tokens are not just whitespace, e.g. whitespace
1252 // followed by a symbol such as backtick. Those symbols may be
1253 // significant in other languages.
1254 unsigned WhitespaceLength = TrailingWhitespace;
1255 while (FormatTok->isNot(Kind: tok::eof)) {
1256 auto LeadingWhitespace = countLeadingWhitespace(Text: FormatTok->TokenText);
1257 if (LeadingWhitespace == 0)
1258 break;
1259 if (LeadingWhitespace < FormatTok->TokenText.size())
1260 truncateToken(NewLen: LeadingWhitespace);
1261 StringRef Text = FormatTok->TokenText;
1262 bool InEscape = false;
1263 for (int i = 0, e = Text.size(); i != e; ++i) {
1264 switch (Text[i]) {
1265 case '\r':
1266 // If this is a CRLF sequence, break here and the LF will be handled on
1267 // the next loop iteration. Otherwise, this is a single Mac CR, treat it
1268 // the same as a single LF.
1269 if (i + 1 < e && Text[i + 1] == '\n')
1270 break;
1271 [[fallthrough]];
1272 case '\n':
1273 ++FormatTok->NewlinesBefore;
1274 if (!InEscape)
1275 FormatTok->HasUnescapedNewline = true;
1276 else
1277 InEscape = false;
1278 FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1279 Column = 0;
1280 break;
1281 case '\f':
1282 if (Style.KeepFormFeed && !FormatTok->HasFormFeedBefore &&
1283 // The form feed is immediately preceded and followed by a newline.
1284 i > 0 && Text[i - 1] == '\n' &&
1285 ((i + 1 < e && Text[i + 1] == '\n') ||
1286 (i + 2 < e && Text[i + 1] == '\r' && Text[i + 2] == '\n'))) {
1287 FormatTok->HasFormFeedBefore = true;
1288 }
1289 [[fallthrough]];
1290 case '\v':
1291 Column = 0;
1292 break;
1293 case ' ':
1294 ++Column;
1295 break;
1296 case '\t':
1297 Column +=
1298 Style.TabWidth - (Style.TabWidth ? Column % Style.TabWidth : 0);
1299 break;
1300 case '\\':
1301 case '?':
1302 case '/':
1303 // The text was entirely whitespace when this loop was entered. Thus
1304 // this has to be an escape sequence.
1305 assert(Text.substr(i, 4) == "\?\?/\r" ||
1306 Text.substr(i, 4) == "\?\?/\n" ||
1307 (i >= 1 && (Text.substr(i - 1, 4) == "\?\?/\r" ||
1308 Text.substr(i - 1, 4) == "\?\?/\n")) ||
1309 (i >= 2 && (Text.substr(i - 2, 4) == "\?\?/\r" ||
1310 Text.substr(i - 2, 4) == "\?\?/\n")) ||
1311 (Text[i] == '\\' && [&]() -> bool {
1312 size_t j = i + 1;
1313 while (j < Text.size() && isHorizontalWhitespace(Text[j]))
1314 ++j;
1315 return j < Text.size() && (Text[j] == '\n' || Text[j] == '\r');
1316 }()));
1317 InEscape = true;
1318 break;
1319 default:
1320 // This shouldn't happen.
1321 assert(false);
1322 break;
1323 }
1324 }
1325 WhitespaceLength += Text.size();
1326 readRawToken(Tok&: *FormatTok);
1327 }
1328
1329 if (FormatTok->is(Kind: tok::unknown))
1330 FormatTok->setType(TT_ImplicitStringLiteral);
1331
1332 // JavaScript and Java do not allow to escape the end of the line with a
1333 // backslash. Backslashes are syntax errors in plain source, but can occur in
1334 // comments. When a single line comment ends with a \, it'll cause the next
1335 // line of code to be lexed as a comment, breaking formatting. The code below
1336 // finds comments that contain a backslash followed by a line break, truncates
1337 // the comment token at the backslash, and resets the lexer to restart behind
1338 // the backslash.
1339 if ((Style.isJavaScript() || Style.isJava()) && FormatTok->is(Kind: tok::comment) &&
1340 FormatTok->TokenText.starts_with(Prefix: "//")) {
1341 size_t BackslashPos = FormatTok->TokenText.find(C: '\\');
1342 while (BackslashPos != StringRef::npos) {
1343 if (BackslashPos + 1 < FormatTok->TokenText.size() &&
1344 FormatTok->TokenText[BackslashPos + 1] == '\n') {
1345 truncateToken(NewLen: BackslashPos + 1);
1346 break;
1347 }
1348 BackslashPos = FormatTok->TokenText.find(C: '\\', From: BackslashPos + 1);
1349 }
1350 }
1351
1352 if (Style.isVerilog()) {
1353 static const llvm::Regex NumberBase("^s?[bdho]", llvm::Regex::IgnoreCase);
1354 SmallVector<StringRef, 1> Matches;
1355 // Verilog uses the backtick instead of the hash for preprocessor stuff.
1356 // And it uses the hash for delays and parameter lists. In order to continue
1357 // using `tok::hash` in other places, the backtick gets marked as the hash
1358 // here. And in order to tell the backtick and hash apart for
1359 // Verilog-specific stuff, the hash becomes an identifier.
1360 if (FormatTok->is(Kind: tok::numeric_constant)) {
1361 // In Verilog the quote is not part of a number.
1362 auto Quote = FormatTok->TokenText.find(C: '\'');
1363 if (Quote != StringRef::npos)
1364 truncateToken(NewLen: Quote);
1365 } else if (FormatTok->isOneOf(K1: tok::hash, K2: tok::hashhash)) {
1366 FormatTok->Tok.setKind(tok::raw_identifier);
1367 } else if (FormatTok->is(Kind: tok::raw_identifier)) {
1368 if (FormatTok->TokenText == "`") {
1369 FormatTok->Tok.setIdentifierInfo(nullptr);
1370 FormatTok->Tok.setKind(tok::hash);
1371 } else if (FormatTok->TokenText == "``") {
1372 FormatTok->Tok.setIdentifierInfo(nullptr);
1373 FormatTok->Tok.setKind(tok::hashhash);
1374 } else if (Tokens.size() > 0 &&
1375 Tokens.back()->is(II: Keywords.kw_apostrophe) &&
1376 NumberBase.match(String: FormatTok->TokenText, Matches: &Matches)) {
1377 // In Verilog in a based number literal like `'b10`, there may be
1378 // whitespace between `'b` and `10`. Therefore we handle the base and
1379 // the rest of the number literal as two tokens. But if there is no
1380 // space in the input code, we need to manually separate the two parts.
1381 truncateToken(NewLen: Matches[0].size());
1382 FormatTok->setFinalizedType(TT_VerilogNumberBase);
1383 }
1384 }
1385 }
1386
1387 FormatTok->WhitespaceRange = SourceRange(
1388 WhitespaceStart, WhitespaceStart.getLocWithOffset(Offset: WhitespaceLength));
1389
1390 FormatTok->OriginalColumn = Column;
1391
1392 TrailingWhitespace = 0;
1393 if (FormatTok->is(Kind: tok::comment)) {
1394 // FIXME: Add the trimmed whitespace to Column.
1395 StringRef UntrimmedText = FormatTok->TokenText;
1396 FormatTok->TokenText = FormatTok->TokenText.rtrim(Chars: " \t\v\f");
1397 TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
1398 } else if (FormatTok->is(Kind: tok::raw_identifier)) {
1399 IdentifierInfo &Info = IdentTable.get(Name: FormatTok->TokenText);
1400 FormatTok->Tok.setIdentifierInfo(&Info);
1401 FormatTok->Tok.setKind(Info.getTokenID());
1402 if (Style.isJava() &&
1403 FormatTok->isOneOf(K1: tok::kw_struct, K2: tok::kw_union, Ks: tok::kw_delete,
1404 Ks: tok::kw_operator)) {
1405 FormatTok->Tok.setKind(tok::identifier);
1406 } else if (Style.isJavaScript() &&
1407 FormatTok->isOneOf(K1: tok::kw_struct, K2: tok::kw_union,
1408 Ks: tok::kw_operator)) {
1409 FormatTok->Tok.setKind(tok::identifier);
1410 } else if (Style.isTableGen() && !Keywords.isTableGenKeyword(Tok: *FormatTok)) {
1411 FormatTok->Tok.setKind(tok::identifier);
1412 }
1413 } else if (const bool Greater = FormatTok->is(Kind: tok::greatergreater);
1414 Greater || FormatTok->is(Kind: tok::lessless)) {
1415 FormatTok->Tok.setKind(Greater ? tok::greater : tok::less);
1416 FormatTok->TokenText = FormatTok->TokenText.substr(Start: 0, N: 1);
1417 ++Column;
1418 StateStack.push(x: LexerState::TOKEN_STASHED);
1419 } else if (Style.isJava() && FormatTok->is(Kind: tok::string_literal)) {
1420 tryParseJavaTextBlock();
1421 }
1422
1423 if (Style.isVerilog() && Tokens.size() > 0 &&
1424 Tokens.back()->is(TT: TT_VerilogNumberBase) &&
1425 FormatTok->Tok.isOneOf(Ks: tok::identifier, Ks: tok::question)) {
1426 // Mark the number following a base like `'h?a0` as a number.
1427 FormatTok->Tok.setKind(tok::numeric_constant);
1428 }
1429
1430 // Now FormatTok is the next non-whitespace token.
1431
1432 StringRef Text = FormatTok->TokenText;
1433 size_t FirstNewlinePos = Text.find(C: '\n');
1434 if (FirstNewlinePos == StringRef::npos) {
1435 // FIXME: ColumnWidth actually depends on the start column, we need to
1436 // take this into account when the token is moved.
1437 FormatTok->ColumnWidth =
1438 encoding::columnWidthWithTabs(Text, StartColumn: Column, TabWidth: Style.TabWidth, Encoding);
1439 Column += FormatTok->ColumnWidth;
1440 } else {
1441 FormatTok->IsMultiline = true;
1442 // FIXME: ColumnWidth actually depends on the start column, we need to
1443 // take this into account when the token is moved.
1444 FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
1445 Text: Text.substr(Start: 0, N: FirstNewlinePos), StartColumn: Column, TabWidth: Style.TabWidth, Encoding);
1446
1447 // The last line of the token always starts in column 0.
1448 // Thus, the length can be precomputed even in the presence of tabs.
1449 FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
1450 Text: Text.substr(Start: Text.find_last_of(C: '\n') + 1), StartColumn: 0, TabWidth: Style.TabWidth, Encoding);
1451 Column = FormatTok->LastLineColumnWidth;
1452 }
1453
1454 if (Style.isCpp()) {
1455 auto *Identifier = FormatTok->Tok.getIdentifierInfo();
1456 auto it = Macros.find(Key: Identifier);
1457 if (!(Tokens.size() > 0 && Tokens.back()->Tok.getIdentifierInfo() &&
1458 Tokens.back()->Tok.getIdentifierInfo()->getPPKeywordID() ==
1459 tok::pp_define) &&
1460 it != Macros.end()) {
1461 FormatTok->setType(it->second);
1462 if (it->second == TT_IfMacro) {
1463 // The lexer token currently has type tok::kw_unknown. However, for this
1464 // substitution to be treated correctly in the TokenAnnotator, faking
1465 // the tok value seems to be needed. Not sure if there's a more elegant
1466 // way.
1467 FormatTok->Tok.setKind(tok::kw_if);
1468 }
1469 } else if (FormatTok->is(Kind: tok::identifier)) {
1470 if (MacroBlockBeginRegex.match(String: Text))
1471 FormatTok->setType(TT_MacroBlockBegin);
1472 else if (MacroBlockEndRegex.match(String: Text))
1473 FormatTok->setType(TT_MacroBlockEnd);
1474 else if (TemplateNames.contains(Ptr: Identifier))
1475 FormatTok->setFinalizedType(TT_TemplateName);
1476 else if (TypeNames.contains(Ptr: Identifier))
1477 FormatTok->setFinalizedType(TT_TypeName);
1478 else if (VariableTemplates.contains(Ptr: Identifier))
1479 FormatTok->setFinalizedType(TT_VariableTemplate);
1480 }
1481 }
1482
1483 return FormatTok;
1484}
1485
1486bool FormatTokenLexer::readRawTokenVerilogSpecific(Token &Tok) {
1487 const char *Start = Lex->getBufferLocation();
1488 size_t Len;
1489 switch (Start[0]) {
1490 // In Verilog the quote is not a character literal.
1491 case '\'':
1492 Len = 1;
1493 break;
1494 // Make the backtick and double backtick identifiers to match against them
1495 // more easily.
1496 case '`':
1497 if (Start[1] == '`')
1498 Len = 2;
1499 else
1500 Len = 1;
1501 break;
1502 // In Verilog an escaped identifier starts with a backslash and ends with
1503 // whitespace. Unless that whitespace is an escaped newline.
1504 // FIXME: If there is an escaped newline in the middle of an escaped
1505 // identifier, allow for pasting the two lines together, But escaped
1506 // identifiers usually occur only in generated code anyway.
1507 case '\\':
1508 // A backslash can also begin an escaped newline outside of an escaped
1509 // identifier.
1510 if (Start[1] == '\r' || Start[1] == '\n')
1511 return false;
1512 Len = 1;
1513 while (Start[Len] != '\0' && Start[Len] != '\f' && Start[Len] != '\n' &&
1514 Start[Len] != '\r' && Start[Len] != '\t' && Start[Len] != '\v' &&
1515 Start[Len] != ' ') {
1516 // There is a null byte at the end of the buffer, so we don't have to
1517 // check whether the next byte is within the buffer.
1518 if (Start[Len] == '\\' && Start[Len + 1] == '\r' &&
1519 Start[Len + 2] == '\n') {
1520 Len += 3;
1521 } else if (Start[Len] == '\\' &&
1522 (Start[Len + 1] == '\r' || Start[Len + 1] == '\n')) {
1523 Len += 2;
1524 } else {
1525 Len += 1;
1526 }
1527 }
1528 break;
1529 default:
1530 return false;
1531 }
1532
1533 // The kind has to be an identifier so we can match it against those defined
1534 // in Keywords. The kind has to be set before the length because the setLength
1535 // function checks that the kind is not an annotation.
1536 Tok.setKind(tok::raw_identifier);
1537 Tok.setLength(Len);
1538 Tok.setLocation(Lex->getSourceLocation(Loc: Start, TokLen: Len));
1539 Tok.setRawIdentifierData(Start);
1540 Lex->seek(Offset: Lex->getCurrentBufferOffset() + Len, /*IsAtStartofline=*/IsAtStartOfLine: false);
1541 return true;
1542}
1543
1544void FormatTokenLexer::readRawToken(FormatToken &Tok) {
1545 // For Verilog, first see if there is a special token, and fall back to the
1546 // normal lexer if there isn't one.
1547 if (!Style.isVerilog() || !readRawTokenVerilogSpecific(Tok&: Tok.Tok))
1548 Lex->LexFromRawLexer(Result&: Tok.Tok);
1549 Tok.TokenText = StringRef(SourceMgr.getCharacterData(SL: Tok.Tok.getLocation()),
1550 Tok.Tok.getLength());
1551 // For formatting, treat unterminated string literals like normal string
1552 // literals.
1553 if (Tok.is(Kind: tok::unknown)) {
1554 if (Tok.TokenText.starts_with(Prefix: "\"")) {
1555 Tok.Tok.setKind(tok::string_literal);
1556 Tok.IsUnterminatedLiteral = true;
1557 } else if (Style.isJavaScript() && Tok.TokenText == "''") {
1558 Tok.Tok.setKind(tok::string_literal);
1559 }
1560 }
1561
1562 if ((Style.isJavaScript() || Style.isProto()) && Tok.is(Kind: tok::char_constant))
1563 Tok.Tok.setKind(tok::string_literal);
1564
1565 if (Tok.is(Kind: tok::comment) && isClangFormatOn(Comment: Tok.TokenText))
1566 FormattingDisabled = false;
1567
1568 Tok.Finalized = FormattingDisabled;
1569
1570 if (Tok.is(Kind: tok::comment) && isClangFormatOff(Comment: Tok.TokenText))
1571 FormattingDisabled = true;
1572}
1573
1574void FormatTokenLexer::resetLexer(unsigned Offset) {
1575 StringRef Buffer = SourceMgr.getBufferData(FID: ID);
1576 Lex.reset(p: new Lexer(SourceMgr.getLocForStartOfFile(FID: ID), LangOpts,
1577 Buffer.begin(), Buffer.begin() + Offset, Buffer.end()));
1578 Lex->SetKeepWhitespaceMode(true);
1579 TrailingWhitespace = 0;
1580}
1581
1582} // namespace format
1583} // namespace clang
1584