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