Clang Project

clang_source_code/lib/Format/FormatTokenLexer.cpp
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(const SourceManager &SourceMgr, FileID ID,
26                                   unsigned Column, const FormatStyle &Style,
27                                   encoding::Encoding Encoding)
28    : FormatTok(nullptr), IsFirstToken(true), StateStack({LexerState::NORMAL}),
29      Column(Column), TrailingWhitespace(0), SourceMgr(SourceMgr), ID(ID),
30      Style(Style), IdentTable(getFormattingLangOpts(Style)),
31      Keywords(IdentTable), Encoding(Encoding), FirstInLineIndex(0),
32      FormattingDisabled(false), MacroBlockBeginRegex(Style.MacroBlockBegin),
33      MacroBlockEndRegex(Style.MacroBlockEnd) {
34  Lex.reset(new Lexer(ID, SourceMgr.getBuffer(ID), SourceMgr,
35                      getFormattingLangOpts(Style)));
36  Lex->SetKeepWhitespaceMode(true);
37
38  for (const std::string &ForEachMacro : Style.ForEachMacros)
39    Macros.insert({&IdentTable.get(ForEachMacro), TT_ForEachMacro});
40  for (const std::string &StatementMacro : Style.StatementMacros)
41    Macros.insert({&IdentTable.get(StatementMacro), TT_StatementMacro});
42}
43
44ArrayRef<FormatToken *> FormatTokenLexer::lex() {
45  assert(Tokens.empty());
46  assert(FirstInLineIndex == 0);
47  do {
48    Tokens.push_back(getNextToken());
49    if (Style.Language == FormatStyle::LK_JavaScript) {
50      tryParseJSRegexLiteral();
51      handleTemplateStrings();
52    }
53    if (Style.Language == FormatStyle::LK_TextProto)
54      tryParsePythonComment();
55    tryMergePreviousTokens();
56    if (Tokens.back()->NewlinesBefore > 0 || Tokens.back()->IsMultiline)
57      FirstInLineIndex = Tokens.size() - 1;
58  } while (Tokens.back()->Tok.isNot(tok::eof));
59  return Tokens;
60}
61
62void FormatTokenLexer::tryMergePreviousTokens() {
63  if (tryMerge_TMacro())
64    return;
65  if (tryMergeConflictMarkers())
66    return;
67  if (tryMergeLessLess())
68    return;
69
70  if (Style.isCSharp()) {
71    if (tryMergeCSharpKeywordVariables())
72      return;
73    if (tryMergeCSharpVerbatimStringLiteral())
74      return;
75    if (tryMergeCSharpDoubleQuestion())
76      return;
77    if (tryMergeCSharpNullConditionals())
78      return;
79    static const tok::TokenKind JSRightArrow[] = {tok::equal, tok::greater};
80    if (tryMergeTokens(JSRightArrow, TT_JsFatArrow))
81      return;
82  }
83
84  if (tryMergeNSStringLiteral())
85    return;
86
87  if (Style.Language == FormatStyle::LK_JavaScript) {
88    static const tok::TokenKind JSIdentity[] = {tok::equalequal, tok::equal};
89    static const tok::TokenKind JSNotIdentity[] = {tok::exclaimequal,
90                                                   tok::equal};
91    static const tok::TokenKind JSShiftEqual[] = {tok::greater, tok::greater,
92                                                  tok::greaterequal};
93    static const tok::TokenKind JSRightArrow[] = {tok::equal, tok::greater};
94    static const tok::TokenKind JSExponentiation[] = {tok::star, tok::star};
95    static const tok::TokenKind JSExponentiationEqual[] = {tok::star,
96                                                           tok::starequal};
97
98    // FIXME: Investigate what token type gives the correct operator priority.
99    if (tryMergeTokens(JSIdentity, TT_BinaryOperator))
100      return;
101    if (tryMergeTokens(JSNotIdentity, TT_BinaryOperator))
102      return;
103    if (tryMergeTokens(JSShiftEqual, TT_BinaryOperator))
104      return;
105    if (tryMergeTokens(JSRightArrow, TT_JsFatArrow))
106      return;
107    if (tryMergeTokens(JSExponentiation, TT_JsExponentiation))
108      return;
109    if (tryMergeTokens(JSExponentiationEqual, TT_JsExponentiationEqual)) {
110      Tokens.back()->Tok.setKind(tok::starequal);
111      return;
112    }
113    if (tryMergeJSPrivateIdentifier())
114      return;
115  }
116
117  if (Style.Language == FormatStyle::LK_Java) {
118    static const tok::TokenKind JavaRightLogicalShiftAssign[] = {
119        tok::greater, tok::greater, tok::greaterequal};
120    if (tryMergeTokens(JavaRightLogicalShiftAssign, TT_BinaryOperator))
121      return;
122  }
123}
124
125bool FormatTokenLexer::tryMergeNSStringLiteral() {
126  if (Tokens.size() < 2)
127    return false;
128  auto &At = *(Tokens.end() - 2);
129  auto &String = *(Tokens.end() - 1);
130  if (!At->is(tok::at) || !String->is(tok::string_literal))
131    return false;
132  At->Tok.setKind(tok::string_literal);
133  At->TokenText = StringRef(At->TokenText.begin(),
134                            String->TokenText.end() - At->TokenText.begin());
135  At->ColumnWidth += String->ColumnWidth;
136  At->Type = TT_ObjCStringLiteral;
137  Tokens.erase(Tokens.end() - 1);
138  return true;
139}
140
141bool FormatTokenLexer::tryMergeJSPrivateIdentifier() {
142  // Merges #idenfier into a single identifier with the text #identifier
143  // but the token tok::identifier.
144  if (Tokens.size() < 2)
145    return false;
146  auto &Hash = *(Tokens.end() - 2);
147  auto &Identifier = *(Tokens.end() - 1);
148  if (!Hash->is(tok::hash) || !Identifier->is(tok::identifier))
149    return false;
150  Hash->Tok.setKind(tok::identifier);
151  Hash->TokenText =
152      StringRef(Hash->TokenText.begin(),
153                Identifier->TokenText.end() - Hash->TokenText.begin());
154  Hash->ColumnWidth += Identifier->ColumnWidth;
155  Hash->Type = TT_JsPrivateIdentifier;
156  Tokens.erase(Tokens.end() - 1);
157  return true;
158}
159
160// Search for verbatim or interpolated string literals @"ABC" or
161// $"aaaaa{abc}aaaaa" i and mark the token as TT_CSharpStringLiteral, and to
162// prevent splitting of @, $ and ".
163bool FormatTokenLexer::tryMergeCSharpVerbatimStringLiteral() {
164  if (Tokens.size() < 2)
165    return false;
166  auto &At = *(Tokens.end() - 2);
167  auto &String = *(Tokens.end() - 1);
168
169  // Look for $"aaaaaa" @"aaaaaa".
170  if (!(At->is(tok::at) || At->TokenText == "$") ||
171      !String->is(tok::string_literal))
172    return false;
173
174  if (Tokens.size() >= 2 && At->is(tok::at)) {
175    auto &Dollar = *(Tokens.end() - 3);
176    if (Dollar->TokenText == "$") {
177      // This looks like $@"aaaaa" so we need to combine all 3 tokens.
178      Dollar->Tok.setKind(tok::string_literal);
179      Dollar->TokenText =
180          StringRef(Dollar->TokenText.begin(),
181                    String->TokenText.end() - Dollar->TokenText.begin());
182      Dollar->ColumnWidth += (At->ColumnWidth + String->ColumnWidth);
183      Dollar->Type = TT_CSharpStringLiteral;
184      Tokens.erase(Tokens.end() - 2);
185      Tokens.erase(Tokens.end() - 1);
186      return true;
187    }
188  }
189
190  // Convert back into just a string_literal.
191  At->Tok.setKind(tok::string_literal);
192  At->TokenText = StringRef(At->TokenText.begin(),
193                            String->TokenText.end() - At->TokenText.begin());
194  At->ColumnWidth += String->ColumnWidth;
195  At->Type = TT_CSharpStringLiteral;
196  Tokens.erase(Tokens.end() - 1);
197  return true;
198}
199
200bool FormatTokenLexer::tryMergeCSharpDoubleQuestion() {
201  if (Tokens.size() < 2)
202    return false;
203  auto &FirstQuestion = *(Tokens.end() - 2);
204  auto &SecondQuestion = *(Tokens.end() - 1);
205  if (!FirstQuestion->is(tok::question) || !SecondQuestion->is(tok::question))
206    return false;
207  FirstQuestion->Tok.setKind(tok::question);
208  FirstQuestion->TokenText = StringRef(FirstQuestion->TokenText.begin(),
209                                       SecondQuestion->TokenText.end() -
210                                           FirstQuestion->TokenText.begin());
211  FirstQuestion->ColumnWidth += SecondQuestion->ColumnWidth;
212  FirstQuestion->Type = TT_CSharpNullCoalescing;
213  Tokens.erase(Tokens.end() - 1);
214  return true;
215}
216
217bool FormatTokenLexer::tryMergeCSharpKeywordVariables() {
218  if (Tokens.size() < 2)
219    return false;
220  auto &At = *(Tokens.end() - 2);
221  auto &Keyword = *(Tokens.end() - 1);
222  if (!At->is(tok::at))
223    return false;
224  if (!Keywords.isCSharpKeyword(*Keyword))
225    return false;
226
227  At->Tok.setKind(tok::identifier);
228  At->TokenText = StringRef(At->TokenText.begin(),
229                            Keyword->TokenText.end() - At->TokenText.begin());
230  At->ColumnWidth += Keyword->ColumnWidth;
231  At->Type = Keyword->Type;
232  Tokens.erase(Tokens.end() - 1);
233  return true;
234}
235
236// In C# merge the Identifier and the ? together e.g. arg?.
237bool FormatTokenLexer::tryMergeCSharpNullConditionals() {
238  if (Tokens.size() < 2)
239    return false;
240  auto &Identifier = *(Tokens.end() - 2);
241  auto &Question = *(Tokens.end() - 1);
242  if (!Identifier->isOneOf(tok::r_square, tok::identifier) ||
243      !Question->is(tok::question))
244    return false;
245  Identifier->TokenText =
246      StringRef(Identifier->TokenText.begin(),
247                Question->TokenText.end() - Identifier->TokenText.begin());
248  Identifier->ColumnWidth += Question->ColumnWidth;
249  Identifier->Type = Identifier->Type;
250  Tokens.erase(Tokens.end() - 1);
251  return true;
252}
253
254bool FormatTokenLexer::tryMergeLessLess() {
255  // Merge X,less,less,Y into X,lessless,Y unless X or Y is less.
256  if (Tokens.size() < 3)
257    return false;
258
259  bool FourthTokenIsLess = false;
260  if (Tokens.size() > 3)
261    FourthTokenIsLess = (Tokens.end() - 4)[0]->is(tok::less);
262
263  auto First = Tokens.end() - 3;
264  if (First[2]->is(tok::less) || First[1]->isNot(tok::less) ||
265      First[0]->isNot(tok::less) || FourthTokenIsLess)
266    return false;
267
268  // Only merge if there currently is no whitespace between the two "<".
269  if (First[1]->WhitespaceRange.getBegin() !=
270      First[1]->WhitespaceRange.getEnd())
271    return false;
272
273  First[0]->Tok.setKind(tok::lessless);
274  First[0]->TokenText = "<<";
275  First[0]->ColumnWidth += 1;
276  Tokens.erase(Tokens.end() - 2);
277  return true;
278}
279
280bool FormatTokenLexer::tryMergeTokens(ArrayRef<tok::TokenKind> Kinds,
281                                      TokenType NewType) {
282  if (Tokens.size() < Kinds.size())
283    return false;
284
285  SmallVectorImpl<FormatToken *>::const_iterator First =
286      Tokens.end() - Kinds.size();
287  if (!First[0]->is(Kinds[0]))
288    return false;
289  unsigned AddLength = 0;
290  for (unsigned i = 1; i < Kinds.size(); ++i) {
291    if (!First[i]->is(Kinds[i]) || First[i]->WhitespaceRange.getBegin() !=
292                                       First[i]->WhitespaceRange.getEnd())
293      return false;
294    AddLength += First[i]->TokenText.size();
295  }
296  Tokens.resize(Tokens.size() - Kinds.size() + 1);
297  First[0]->TokenText = StringRef(First[0]->TokenText.data(),
298                                  First[0]->TokenText.size() + AddLength);
299  First[0]->ColumnWidth += AddLength;
300  First[0]->Type = NewType;
301  return true;
302}
303
304// Returns \c true if \p Tok can only be followed by an operand in JavaScript.
305bool FormatTokenLexer::precedesOperand(FormatToken *Tok) {
306  // NB: This is not entirely correct, as an r_paren can introduce an operand
307  // location in e.g. `if (foo) /bar/.exec(...);`. That is a rare enough
308  // corner case to not matter in practice, though.
309  return Tok->isOneOf(tok::period, tok::l_paren, tok::comma, tok::l_brace,
310                      tok::r_brace, tok::l_square, tok::semi, tok::exclaim,
311                      tok::colon, tok::question, tok::tilde) ||
312         Tok->isOneOf(tok::kw_return, tok::kw_do, tok::kw_case, tok::kw_throw,
313                      tok::kw_else, tok::kw_new, tok::kw_delete, tok::kw_void,
314                      tok::kw_typeof, Keywords.kw_instanceof, Keywords.kw_in) ||
315         Tok->isBinaryOperator();
316}
317
318bool FormatTokenLexer::canPrecedeRegexLiteral(FormatToken *Prev) {
319  if (!Prev)
320    return true;
321
322  // Regex literals can only follow after prefix unary operators, not after
323  // postfix unary operators. If the '++' is followed by a non-operand
324  // introducing token, the slash here is the operand and not the start of a
325  // regex.
326  // `!` is an unary prefix operator, but also a post-fix operator that casts
327  // away nullability, so the same check applies.
328  if (Prev->isOneOf(tok::plusplus, tok::minusminus, tok::exclaim))
329    return (Tokens.size() < 3 || precedesOperand(Tokens[Tokens.size() - 3]));
330
331  // The previous token must introduce an operand location where regex
332  // literals can occur.
333  if (!precedesOperand(Prev))
334    return false;
335
336  return true;
337}
338
339// Tries to parse a JavaScript Regex literal starting at the current token,
340// if that begins with a slash and is in a location where JavaScript allows
341// regex literals. Changes the current token to a regex literal and updates
342// its text if successful.
343void FormatTokenLexer::tryParseJSRegexLiteral() {
344  FormatToken *RegexToken = Tokens.back();
345  if (!RegexToken->isOneOf(tok::slash, tok::slashequal))
346    return;
347
348  FormatToken *Prev = nullptr;
349  for (auto I = Tokens.rbegin() + 1, E = Tokens.rend(); I != E; ++I) {
350    // NB: Because previous pointers are not initialized yet, this cannot use
351    // Token.getPreviousNonComment.
352    if ((*I)->isNot(tok::comment)) {
353      Prev = *I;
354      break;
355    }
356  }
357
358  if (!canPrecedeRegexLiteral(Prev))
359    return;
360
361  // 'Manually' lex ahead in the current file buffer.
362  const char *Offset = Lex->getBufferLocation();
363  const char *RegexBegin = Offset - RegexToken->TokenText.size();
364  StringRef Buffer = Lex->getBuffer();
365  bool InCharacterClass = false;
366  bool HaveClosingSlash = false;
367  for (; !HaveClosingSlash && Offset != Buffer.end(); ++Offset) {
368    // Regular expressions are terminated with a '/', which can only be
369    // escaped using '\' or a character class between '[' and ']'.
370    // See http://www.ecma-international.org/ecma-262/5.1/#sec-7.8.5.
371    switch (*Offset) {
372    case '\\':
373      // Skip the escaped character.
374      ++Offset;
375      break;
376    case '[':
377      InCharacterClass = true;
378      break;
379    case ']':
380      InCharacterClass = false;
381      break;
382    case '/':
383      if (!InCharacterClass)
384        HaveClosingSlash = true;
385      break;
386    }
387  }
388
389  RegexToken->Type = TT_RegexLiteral;
390  // Treat regex literals like other string_literals.
391  RegexToken->Tok.setKind(tok::string_literal);
392  RegexToken->TokenText = StringRef(RegexBegin, Offset - RegexBegin);
393  RegexToken->ColumnWidth = RegexToken->TokenText.size();
394
395  resetLexer(SourceMgr.getFileOffset(Lex->getSourceLocation(Offset)));
396}
397
398void FormatTokenLexer::handleTemplateStrings() {
399  FormatToken *BacktickToken = Tokens.back();
400
401  if (BacktickToken->is(tok::l_brace)) {
402    StateStack.push(LexerState::NORMAL);
403    return;
404  }
405  if (BacktickToken->is(tok::r_brace)) {
406    if (StateStack.size() == 1)
407      return;
408    StateStack.pop();
409    if (StateStack.top() != LexerState::TEMPLATE_STRING)
410      return;
411    // If back in TEMPLATE_STRING, fallthrough and continue parsing the
412  } else if (BacktickToken->is(tok::unknown) &&
413             BacktickToken->TokenText == "`") {
414    StateStack.push(LexerState::TEMPLATE_STRING);
415  } else {
416    return; // Not actually a template
417  }
418
419  // 'Manually' lex ahead in the current file buffer.
420  const char *Offset = Lex->getBufferLocation();
421  const char *TmplBegin = Offset - BacktickToken->TokenText.size(); // at "`"
422  for (; Offset != Lex->getBuffer().end(); ++Offset) {
423    if (Offset[0] == '`') {
424      StateStack.pop();
425      break;
426    }
427    if (Offset[0] == '\\') {
428      ++Offset; // Skip the escaped character.
429    } else if (Offset + 1 < Lex->getBuffer().end() && Offset[0] == '$' &&
430               Offset[1] == '{') {
431      // '${' introduces an expression interpolation in the template string.
432      StateStack.push(LexerState::NORMAL);
433      ++Offset;
434      break;
435    }
436  }
437
438  StringRef LiteralText(TmplBegin, Offset - TmplBegin + 1);
439  BacktickToken->Type = TT_TemplateString;
440  BacktickToken->Tok.setKind(tok::string_literal);
441  BacktickToken->TokenText = LiteralText;
442
443  // Adjust width for potentially multiline string literals.
444  size_t FirstBreak = LiteralText.find('\n');
445  StringRef FirstLineText = FirstBreak == StringRef::npos
446                                ? LiteralText
447                                : LiteralText.substr(0, FirstBreak);
448  BacktickToken->ColumnWidth = encoding::columnWidthWithTabs(
449      FirstLineText, BacktickToken->OriginalColumn, Style.TabWidth, Encoding);
450  size_t LastBreak = LiteralText.rfind('\n');
451  if (LastBreak != StringRef::npos) {
452    BacktickToken->IsMultiline = true;
453    unsigned StartColumn = 0; // The template tail spans the entire line.
454    BacktickToken->LastLineColumnWidth = encoding::columnWidthWithTabs(
455        LiteralText.substr(LastBreak + 1, LiteralText.size()), StartColumn,
456        Style.TabWidth, Encoding);
457  }
458
459  SourceLocation loc = Offset < Lex->getBuffer().end()
460                           ? Lex->getSourceLocation(Offset + 1)
461                           : SourceMgr.getLocForEndOfFile(ID);
462  resetLexer(SourceMgr.getFileOffset(loc));
463}
464
465void FormatTokenLexer::tryParsePythonComment() {
466  FormatToken *HashToken = Tokens.back();
467  if (!HashToken->isOneOf(tok::hash, tok::hashhash))
468    return;
469  // Turn the remainder of this line into a comment.
470  const char *CommentBegin =
471      Lex->getBufferLocation() - HashToken->TokenText.size(); // at "#"
472  size_t From = CommentBegin - Lex->getBuffer().begin();
473  size_t To = Lex->getBuffer().find_first_of('\n', From);
474  if (To == StringRef::npos)
475    To = Lex->getBuffer().size();
476  size_t Len = To - From;
477  HashToken->Type = TT_LineComment;
478  HashToken->Tok.setKind(tok::comment);
479  HashToken->TokenText = Lex->getBuffer().substr(From, Len);
480  SourceLocation Loc = To < Lex->getBuffer().size()
481                           ? Lex->getSourceLocation(CommentBegin + Len)
482                           : SourceMgr.getLocForEndOfFile(ID);
483  resetLexer(SourceMgr.getFileOffset(Loc));
484}
485
486bool FormatTokenLexer::tryMerge_TMacro() {
487  if (Tokens.size() < 4)
488    return false;
489  FormatToken *Last = Tokens.back();
490  if (!Last->is(tok::r_paren))
491    return false;
492
493  FormatToken *String = Tokens[Tokens.size() - 2];
494  if (!String->is(tok::string_literal) || String->IsMultiline)
495    return false;
496
497  if (!Tokens[Tokens.size() - 3]->is(tok::l_paren))
498    return false;
499
500  FormatToken *Macro = Tokens[Tokens.size() - 4];
501  if (Macro->TokenText != "_T")
502    return false;
503
504  const char *Start = Macro->TokenText.data();
505  const char *End = Last->TokenText.data() + Last->TokenText.size();
506  String->TokenText = StringRef(Start, End - Start);
507  String->IsFirst = Macro->IsFirst;
508  String->LastNewlineOffset = Macro->LastNewlineOffset;
509  String->WhitespaceRange = Macro->WhitespaceRange;
510  String->OriginalColumn = Macro->OriginalColumn;
511  String->ColumnWidth = encoding::columnWidthWithTabs(
512      String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding);
513  String->NewlinesBefore = Macro->NewlinesBefore;
514  String->HasUnescapedNewline = Macro->HasUnescapedNewline;
515
516  Tokens.pop_back();
517  Tokens.pop_back();
518  Tokens.pop_back();
519  Tokens.back() = String;
520  return true;
521}
522
523bool FormatTokenLexer::tryMergeConflictMarkers() {
524  if (Tokens.back()->NewlinesBefore == 0 && Tokens.back()->isNot(tok::eof))
525    return false;
526
527  // Conflict lines look like:
528  // <marker> <text from the vcs>
529  // For example:
530  // >>>>>>> /file/in/file/system at revision 1234
531  //
532  // We merge all tokens in a line that starts with a conflict marker
533  // into a single token with a special token type that the unwrapped line
534  // parser will use to correctly rebuild the underlying code.
535
536  FileID ID;
537  // Get the position of the first token in the line.
538  unsigned FirstInLineOffset;
539  std::tie(ID, FirstInLineOffset) = SourceMgr.getDecomposedLoc(
540      Tokens[FirstInLineIndex]->getStartOfNonWhitespace());
541  StringRef Buffer = SourceMgr.getBuffer(ID)->getBuffer();
542  // Calculate the offset of the start of the current line.
543  auto LineOffset = Buffer.rfind('\n', FirstInLineOffset);
544  if (LineOffset == StringRef::npos) {
545    LineOffset = 0;
546  } else {
547    ++LineOffset;
548  }
549
550  auto FirstSpace = Buffer.find_first_of(" \n", LineOffset);
551  StringRef LineStart;
552  if (FirstSpace == StringRef::npos) {
553    LineStart = Buffer.substr(LineOffset);
554  } else {
555    LineStart = Buffer.substr(LineOffset, FirstSpace - LineOffset);
556  }
557
558  TokenType Type = TT_Unknown;
559  if (LineStart == "<<<<<<<" || LineStart == ">>>>") {
560    Type = TT_ConflictStart;
561  } else if (LineStart == "|||||||" || LineStart == "=======" ||
562             LineStart == "====") {
563    Type = TT_ConflictAlternative;
564  } else if (LineStart == ">>>>>>>" || LineStart == "<<<<") {
565    Type = TT_ConflictEnd;
566  }
567
568  if (Type != TT_Unknown) {
569    FormatToken *Next = Tokens.back();
570
571    Tokens.resize(FirstInLineIndex + 1);
572    // We do not need to build a complete token here, as we will skip it
573    // during parsing anyway (as we must not touch whitespace around conflict
574    // markers).
575    Tokens.back()->Type = Type;
576    Tokens.back()->Tok.setKind(tok::kw___unknown_anytype);
577
578    Tokens.push_back(Next);
579    return true;
580  }
581
582  return false;
583}
584
585FormatToken *FormatTokenLexer::getStashedToken() {
586  // Create a synthesized second '>' or '<' token.
587  Token Tok = FormatTok->Tok;
588  StringRef TokenText = FormatTok->TokenText;
589
590  unsigned OriginalColumn = FormatTok->OriginalColumn;
591  FormatTok = new (Allocator.Allocate()) FormatToken;
592  FormatTok->Tok = Tok;
593  SourceLocation TokLocation =
594      FormatTok->Tok.getLocation().getLocWithOffset(Tok.getLength() - 1);
595  FormatTok->Tok.setLocation(TokLocation);
596  FormatTok->WhitespaceRange = SourceRange(TokLocation, TokLocation);
597  FormatTok->TokenText = TokenText;
598  FormatTok->ColumnWidth = 1;
599  FormatTok->OriginalColumn = OriginalColumn + 1;
600
601  return FormatTok;
602}
603
604FormatToken *FormatTokenLexer::getNextToken() {
605  if (StateStack.top() == LexerState::TOKEN_STASHED) {
606    StateStack.pop();
607    return getStashedToken();
608  }
609
610  FormatTok = new (Allocator.Allocate()) FormatToken;
611  readRawToken(*FormatTok);
612  SourceLocation WhitespaceStart =
613      FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
614  FormatTok->IsFirst = IsFirstToken;
615  IsFirstToken = false;
616
617  // Consume and record whitespace until we find a significant token.
618  unsigned WhitespaceLength = TrailingWhitespace;
619  while (FormatTok->Tok.is(tok::unknown)) {
620    StringRef Text = FormatTok->TokenText;
621    auto EscapesNewline = [&](int pos) {
622      // A '\r' here is just part of '\r\n'. Skip it.
623      if (pos >= 0 && Text[pos] == '\r')
624        --pos;
625      // See whether there is an odd number of '\' before this.
626      // FIXME: This is wrong. A '\' followed by a newline is always removed,
627      // regardless of whether there is another '\' before it.
628      // FIXME: Newlines can also be escaped by a '?' '?' '/' trigraph.
629      unsigned count = 0;
630      for (; pos >= 0; --pos, ++count)
631        if (Text[pos] != '\\')
632          break;
633      return count & 1;
634    };
635    // FIXME: This miscounts tok:unknown tokens that are not just
636    // whitespace, e.g. a '`' character.
637    for (int i = 0, e = Text.size(); i != e; ++i) {
638      switch (Text[i]) {
639      case '\n':
640        ++FormatTok->NewlinesBefore;
641        FormatTok->HasUnescapedNewline = !EscapesNewline(i - 1);
642        FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
643        Column = 0;
644        break;
645      case '\r':
646        FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
647        Column = 0;
648        break;
649      case '\f':
650      case '\v':
651        Column = 0;
652        break;
653      case ' ':
654        ++Column;
655        break;
656      case '\t':
657        Column += Style.TabWidth - Column % Style.TabWidth;
658        break;
659      case '\\':
660        if (i + 1 == e || (Text[i + 1] != '\r' && Text[i + 1] != '\n'))
661          FormatTok->Type = TT_ImplicitStringLiteral;
662        break;
663      default:
664        FormatTok->Type = TT_ImplicitStringLiteral;
665        break;
666      }
667      if (FormatTok->Type == TT_ImplicitStringLiteral)
668        break;
669    }
670
671    if (FormatTok->is(TT_ImplicitStringLiteral))
672      break;
673    WhitespaceLength += FormatTok->Tok.getLength();
674
675    readRawToken(*FormatTok);
676  }
677
678  // JavaScript and Java do not allow to escape the end of the line with a
679  // backslash. Backslashes are syntax errors in plain source, but can occur in
680  // comments. When a single line comment ends with a \, it'll cause the next
681  // line of code to be lexed as a comment, breaking formatting. The code below
682  // finds comments that contain a backslash followed by a line break, truncates
683  // the comment token at the backslash, and resets the lexer to restart behind
684  // the backslash.
685  if ((Style.Language == FormatStyle::LK_JavaScript ||
686       Style.Language == FormatStyle::LK_Java) &&
687      FormatTok->is(tok::comment) && FormatTok->TokenText.startswith("//")) {
688    size_t BackslashPos = FormatTok->TokenText.find('\\');
689    while (BackslashPos != StringRef::npos) {
690      if (BackslashPos + 1 < FormatTok->TokenText.size() &&
691          FormatTok->TokenText[BackslashPos + 1] == '\n') {
692        const char *Offset = Lex->getBufferLocation();
693        Offset -= FormatTok->TokenText.size();
694        Offset += BackslashPos + 1;
695        resetLexer(SourceMgr.getFileOffset(Lex->getSourceLocation(Offset)));
696        FormatTok->TokenText = FormatTok->TokenText.substr(0, BackslashPos + 1);
697        FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
698            FormatTok->TokenText, FormatTok->OriginalColumn, Style.TabWidth,
699            Encoding);
700        break;
701      }
702      BackslashPos = FormatTok->TokenText.find('\\', BackslashPos + 1);
703    }
704  }
705
706  // In case the token starts with escaped newlines, we want to
707  // take them into account as whitespace - this pattern is quite frequent
708  // in macro definitions.
709  // FIXME: Add a more explicit test.
710  while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\') {
711    unsigned SkippedWhitespace = 0;
712    if (FormatTok->TokenText.size() > 2 &&
713        (FormatTok->TokenText[1] == '\r' && FormatTok->TokenText[2] == '\n'))
714      SkippedWhitespace = 3;
715    else if (FormatTok->TokenText[1] == '\n')
716      SkippedWhitespace = 2;
717    else
718      break;
719
720    ++FormatTok->NewlinesBefore;
721    WhitespaceLength += SkippedWhitespace;
722    FormatTok->LastNewlineOffset = SkippedWhitespace;
723    Column = 0;
724    FormatTok->TokenText = FormatTok->TokenText.substr(SkippedWhitespace);
725  }
726
727  FormatTok->WhitespaceRange = SourceRange(
728      WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
729
730  FormatTok->OriginalColumn = Column;
731
732  TrailingWhitespace = 0;
733  if (FormatTok->Tok.is(tok::comment)) {
734    // FIXME: Add the trimmed whitespace to Column.
735    StringRef UntrimmedText = FormatTok->TokenText;
736    FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
737    TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
738  } else if (FormatTok->Tok.is(tok::raw_identifier)) {
739    IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
740    FormatTok->Tok.setIdentifierInfo(&Info);
741    FormatTok->Tok.setKind(Info.getTokenID());
742    if (Style.Language == FormatStyle::LK_Java &&
743        FormatTok->isOneOf(tok::kw_struct, tok::kw_union, tok::kw_delete,
744                           tok::kw_operator)) {
745      FormatTok->Tok.setKind(tok::identifier);
746      FormatTok->Tok.setIdentifierInfo(nullptr);
747    } else if (Style.Language == FormatStyle::LK_JavaScript &&
748               FormatTok->isOneOf(tok::kw_struct, tok::kw_union,
749                                  tok::kw_operator)) {
750      FormatTok->Tok.setKind(tok::identifier);
751      FormatTok->Tok.setIdentifierInfo(nullptr);
752    }
753  } else if (FormatTok->Tok.is(tok::greatergreater)) {
754    FormatTok->Tok.setKind(tok::greater);
755    FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
756    ++Column;
757    StateStack.push(LexerState::TOKEN_STASHED);
758  } else if (FormatTok->Tok.is(tok::lessless)) {
759    FormatTok->Tok.setKind(tok::less);
760    FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
761    ++Column;
762    StateStack.push(LexerState::TOKEN_STASHED);
763  }
764
765  // Now FormatTok is the next non-whitespace token.
766
767  StringRef Text = FormatTok->TokenText;
768  size_t FirstNewlinePos = Text.find('\n');
769  if (FirstNewlinePos == StringRef::npos) {
770    // FIXME: ColumnWidth actually depends on the start column, we need to
771    // take this into account when the token is moved.
772    FormatTok->ColumnWidth =
773        encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding);
774    Column += FormatTok->ColumnWidth;
775  } else {
776    FormatTok->IsMultiline = true;
777    // FIXME: ColumnWidth actually depends on the start column, we need to
778    // take this into account when the token is moved.
779    FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
780        Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding);
781
782    // The last line of the token always starts in column 0.
783    // Thus, the length can be precomputed even in the presence of tabs.
784    FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
785        Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth, Encoding);
786    Column = FormatTok->LastLineColumnWidth;
787  }
788
789  if (Style.isCpp()) {
790    auto it = Macros.find(FormatTok->Tok.getIdentifierInfo());
791    if (!(Tokens.size() > 0 && Tokens.back()->Tok.getIdentifierInfo() &&
792          Tokens.back()->Tok.getIdentifierInfo()->getPPKeywordID() ==
793              tok::pp_define) &&
794        it != Macros.end()) {
795      FormatTok->Type = it->second;
796    } else if (FormatTok->is(tok::identifier)) {
797      if (MacroBlockBeginRegex.match(Text)) {
798        FormatTok->Type = TT_MacroBlockBegin;
799      } else if (MacroBlockEndRegex.match(Text)) {
800        FormatTok->Type = TT_MacroBlockEnd;
801      }
802    }
803  }
804
805  return FormatTok;
806}
807
808void FormatTokenLexer::readRawToken(FormatToken &Tok) {
809  Lex->LexFromRawLexer(Tok.Tok);
810  Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
811                            Tok.Tok.getLength());
812  // For formatting, treat unterminated string literals like normal string
813  // literals.
814  if (Tok.is(tok::unknown)) {
815    if (!Tok.TokenText.empty() && Tok.TokenText[0] == '"') {
816      Tok.Tok.setKind(tok::string_literal);
817      Tok.IsUnterminatedLiteral = true;
818    } else if (Style.Language == FormatStyle::LK_JavaScript &&
819               Tok.TokenText == "''") {
820      Tok.Tok.setKind(tok::string_literal);
821    }
822  }
823
824  if ((Style.Language == FormatStyle::LK_JavaScript ||
825       Style.Language == FormatStyle::LK_Proto ||
826       Style.Language == FormatStyle::LK_TextProto) &&
827      Tok.is(tok::char_constant)) {
828    Tok.Tok.setKind(tok::string_literal);
829  }
830
831  if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format on" ||
832                               Tok.TokenText == "/* clang-format on */")) {
833    FormattingDisabled = false;
834  }
835
836  Tok.Finalized = FormattingDisabled;
837
838  if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format off" ||
839                               Tok.TokenText == "/* clang-format off */")) {
840    FormattingDisabled = true;
841  }
842}
843
844void FormatTokenLexer::resetLexer(unsigned Offset) {
845  StringRef Buffer = SourceMgr.getBufferData(ID);
846  Lex.reset(new Lexer(SourceMgr.getLocForStartOfFile(ID),
847                      getFormattingLangOpts(Style), Buffer.begin(),
848                      Buffer.begin() + Offset, Buffer.end()));
849  Lex->SetKeepWhitespaceMode(true);
850  TrailingWhitespace = 0;
851}
852
853} // namespace format
854} // namespace clang
855
CodeThinker, Enjoy your reading code