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