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