1 //===--- FormatTokenLexer.cpp - Lex FormatTokens -------------*- C++ ----*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// \brief This file implements FormatTokenLexer, which tokenizes a source file
12 /// into a FormatToken stream suitable for ClangFormat.
14 //===----------------------------------------------------------------------===//
16 #include "FormatTokenLexer.h"
17 #include "FormatToken.h"
18 #include "clang/Basic/SourceLocation.h"
19 #include "clang/Basic/SourceManager.h"
20 #include "clang/Format/Format.h"
21 #include "llvm/Support/Regex.h"
26 FormatTokenLexer::FormatTokenLexer(const SourceManager &SourceMgr, FileID ID,
27 const FormatStyle &Style,
28 encoding::Encoding Encoding)
29 : FormatTok(nullptr), IsFirstToken(true), StateStack({LexerState::NORMAL}),
30 Column(0), TrailingWhitespace(0), SourceMgr(SourceMgr), ID(ID),
31 Style(Style), IdentTable(getFormattingLangOpts(Style)),
32 Keywords(IdentTable), Encoding(Encoding), FirstInLineIndex(0),
33 FormattingDisabled(false), MacroBlockBeginRegex(Style.MacroBlockBegin),
34 MacroBlockEndRegex(Style.MacroBlockEnd) {
35 Lex.reset(new Lexer(ID, SourceMgr.getBuffer(ID), SourceMgr,
36 getFormattingLangOpts(Style)));
37 Lex->SetKeepWhitespaceMode(true);
39 for (const std::string &ForEachMacro : Style.ForEachMacros)
40 ForEachMacros.push_back(&IdentTable.get(ForEachMacro));
41 std::sort(ForEachMacros.begin(), ForEachMacros.end());
44 ArrayRef<FormatToken *> FormatTokenLexer::lex() {
45 assert(Tokens.empty());
46 assert(FirstInLineIndex == 0);
48 Tokens.push_back(getNextToken());
49 if (Style.Language == FormatStyle::LK_JavaScript) {
50 tryParseJSRegexLiteral();
51 handleTemplateStrings();
53 tryMergePreviousTokens();
54 if (Tokens.back()->NewlinesBefore > 0 || Tokens.back()->IsMultiline)
55 FirstInLineIndex = Tokens.size() - 1;
56 } while (Tokens.back()->Tok.isNot(tok::eof));
60 void FormatTokenLexer::tryMergePreviousTokens() {
61 if (tryMerge_TMacro())
63 if (tryMergeConflictMarkers())
65 if (tryMergeLessLess())
68 if (Style.Language == FormatStyle::LK_JavaScript) {
69 static const tok::TokenKind JSIdentity[] = {tok::equalequal, tok::equal};
70 static const tok::TokenKind JSNotIdentity[] = {tok::exclaimequal,
72 static const tok::TokenKind JSShiftEqual[] = {tok::greater, tok::greater,
74 static const tok::TokenKind JSRightArrow[] = {tok::equal, tok::greater};
75 // FIXME: Investigate what token type gives the correct operator priority.
76 if (tryMergeTokens(JSIdentity, TT_BinaryOperator))
78 if (tryMergeTokens(JSNotIdentity, TT_BinaryOperator))
80 if (tryMergeTokens(JSShiftEqual, TT_BinaryOperator))
82 if (tryMergeTokens(JSRightArrow, TT_JsFatArrow))
87 bool FormatTokenLexer::tryMergeLessLess() {
88 // Merge X,less,less,Y into X,lessless,Y unless X or Y is less.
89 if (Tokens.size() < 3)
92 bool FourthTokenIsLess = false;
93 if (Tokens.size() > 3)
94 FourthTokenIsLess = (Tokens.end() - 4)[0]->is(tok::less);
96 auto First = Tokens.end() - 3;
97 if (First[2]->is(tok::less) || First[1]->isNot(tok::less) ||
98 First[0]->isNot(tok::less) || FourthTokenIsLess)
101 // Only merge if there currently is no whitespace between the two "<".
102 if (First[1]->WhitespaceRange.getBegin() !=
103 First[1]->WhitespaceRange.getEnd())
106 First[0]->Tok.setKind(tok::lessless);
107 First[0]->TokenText = "<<";
108 First[0]->ColumnWidth += 1;
109 Tokens.erase(Tokens.end() - 2);
113 bool FormatTokenLexer::tryMergeTokens(ArrayRef<tok::TokenKind> Kinds,
115 if (Tokens.size() < Kinds.size())
118 SmallVectorImpl<FormatToken *>::const_iterator First =
119 Tokens.end() - Kinds.size();
120 if (!First[0]->is(Kinds[0]))
122 unsigned AddLength = 0;
123 for (unsigned i = 1; i < Kinds.size(); ++i) {
124 if (!First[i]->is(Kinds[i]) ||
125 First[i]->WhitespaceRange.getBegin() !=
126 First[i]->WhitespaceRange.getEnd())
128 AddLength += First[i]->TokenText.size();
130 Tokens.resize(Tokens.size() - Kinds.size() + 1);
131 First[0]->TokenText = StringRef(First[0]->TokenText.data(),
132 First[0]->TokenText.size() + AddLength);
133 First[0]->ColumnWidth += AddLength;
134 First[0]->Type = NewType;
138 // Returns \c true if \p Tok can only be followed by an operand in JavaScript.
139 bool FormatTokenLexer::precedesOperand(FormatToken *Tok) {
140 // NB: This is not entirely correct, as an r_paren can introduce an operand
141 // location in e.g. `if (foo) /bar/.exec(...);`. That is a rare enough
142 // corner case to not matter in practice, though.
143 return Tok->isOneOf(tok::period, tok::l_paren, tok::comma, tok::l_brace,
144 tok::r_brace, tok::l_square, tok::semi, tok::exclaim,
145 tok::colon, tok::question, tok::tilde) ||
146 Tok->isOneOf(tok::kw_return, tok::kw_do, tok::kw_case, tok::kw_throw,
147 tok::kw_else, tok::kw_new, tok::kw_delete, tok::kw_void,
148 tok::kw_typeof, Keywords.kw_instanceof, Keywords.kw_in) ||
149 Tok->isBinaryOperator();
152 bool FormatTokenLexer::canPrecedeRegexLiteral(FormatToken *Prev) {
156 // Regex literals can only follow after prefix unary operators, not after
157 // postfix unary operators. If the '++' is followed by a non-operand
158 // introducing token, the slash here is the operand and not the start of a
160 if (Prev->isOneOf(tok::plusplus, tok::minusminus))
161 return (Tokens.size() < 3 || precedesOperand(Tokens[Tokens.size() - 3]));
163 // The previous token must introduce an operand location where regex
164 // literals can occur.
165 if (!precedesOperand(Prev))
171 // Tries to parse a JavaScript Regex literal starting at the current token,
172 // if that begins with a slash and is in a location where JavaScript allows
173 // regex literals. Changes the current token to a regex literal and updates
174 // its text if successful.
175 void FormatTokenLexer::tryParseJSRegexLiteral() {
176 FormatToken *RegexToken = Tokens.back();
177 if (!RegexToken->isOneOf(tok::slash, tok::slashequal))
180 FormatToken *Prev = nullptr;
181 for (auto I = Tokens.rbegin() + 1, E = Tokens.rend(); I != E; ++I) {
182 // NB: Because previous pointers are not initialized yet, this cannot use
183 // Token.getPreviousNonComment.
184 if ((*I)->isNot(tok::comment)) {
190 if (!canPrecedeRegexLiteral(Prev))
193 // 'Manually' lex ahead in the current file buffer.
194 const char *Offset = Lex->getBufferLocation();
195 const char *RegexBegin = Offset - RegexToken->TokenText.size();
196 StringRef Buffer = Lex->getBuffer();
197 bool InCharacterClass = false;
198 bool HaveClosingSlash = false;
199 for (; !HaveClosingSlash && Offset != Buffer.end(); ++Offset) {
200 // Regular expressions are terminated with a '/', which can only be
201 // escaped using '\' or a character class between '[' and ']'.
202 // See http://www.ecma-international.org/ecma-262/5.1/#sec-7.8.5.
205 // Skip the escaped character.
209 InCharacterClass = true;
212 InCharacterClass = false;
215 if (!InCharacterClass)
216 HaveClosingSlash = true;
221 RegexToken->Type = TT_RegexLiteral;
222 // Treat regex literals like other string_literals.
223 RegexToken->Tok.setKind(tok::string_literal);
224 RegexToken->TokenText = StringRef(RegexBegin, Offset - RegexBegin);
225 RegexToken->ColumnWidth = RegexToken->TokenText.size();
227 resetLexer(SourceMgr.getFileOffset(Lex->getSourceLocation(Offset)));
230 void FormatTokenLexer::handleTemplateStrings() {
231 FormatToken *BacktickToken = Tokens.back();
233 if (BacktickToken->is(tok::l_brace)) {
234 StateStack.push(LexerState::NORMAL);
237 if (BacktickToken->is(tok::r_brace)) {
238 if (StateStack.size() == 1)
241 if (StateStack.top() != LexerState::TEMPLATE_STRING)
243 // If back in TEMPLATE_STRING, fallthrough and continue parsing the
244 } else if (BacktickToken->is(tok::unknown) &&
245 BacktickToken->TokenText == "`") {
246 StateStack.push(LexerState::TEMPLATE_STRING);
248 return; // Not actually a template
251 // 'Manually' lex ahead in the current file buffer.
252 const char *Offset = Lex->getBufferLocation();
253 const char *TmplBegin = Offset - BacktickToken->TokenText.size(); // at "`"
254 for (; Offset != Lex->getBuffer().end(); ++Offset) {
255 if (Offset[0] == '`') {
259 if (Offset[0] == '\\') {
260 ++Offset; // Skip the escaped character.
261 } else if (Offset + 1 < Lex->getBuffer().end() && Offset[0] == '$' &&
263 // '${' introduces an expression interpolation in the template string.
264 StateStack.push(LexerState::NORMAL);
270 StringRef LiteralText(TmplBegin, Offset - TmplBegin + 1);
271 BacktickToken->Type = TT_TemplateString;
272 BacktickToken->Tok.setKind(tok::string_literal);
273 BacktickToken->TokenText = LiteralText;
275 // Adjust width for potentially multiline string literals.
276 size_t FirstBreak = LiteralText.find('\n');
277 StringRef FirstLineText = FirstBreak == StringRef::npos
279 : LiteralText.substr(0, FirstBreak);
280 BacktickToken->ColumnWidth = encoding::columnWidthWithTabs(
281 FirstLineText, BacktickToken->OriginalColumn, Style.TabWidth, Encoding);
282 size_t LastBreak = LiteralText.rfind('\n');
283 if (LastBreak != StringRef::npos) {
284 BacktickToken->IsMultiline = true;
285 unsigned StartColumn = 0; // The template tail spans the entire line.
286 BacktickToken->LastLineColumnWidth = encoding::columnWidthWithTabs(
287 LiteralText.substr(LastBreak + 1, LiteralText.size()), StartColumn,
288 Style.TabWidth, Encoding);
291 SourceLocation loc = Offset < Lex->getBuffer().end()
292 ? Lex->getSourceLocation(Offset + 1)
293 : SourceMgr.getLocForEndOfFile(ID);
294 resetLexer(SourceMgr.getFileOffset(loc));
297 bool FormatTokenLexer::tryMerge_TMacro() {
298 if (Tokens.size() < 4)
300 FormatToken *Last = Tokens.back();
301 if (!Last->is(tok::r_paren))
304 FormatToken *String = Tokens[Tokens.size() - 2];
305 if (!String->is(tok::string_literal) || String->IsMultiline)
308 if (!Tokens[Tokens.size() - 3]->is(tok::l_paren))
311 FormatToken *Macro = Tokens[Tokens.size() - 4];
312 if (Macro->TokenText != "_T")
315 const char *Start = Macro->TokenText.data();
316 const char *End = Last->TokenText.data() + Last->TokenText.size();
317 String->TokenText = StringRef(Start, End - Start);
318 String->IsFirst = Macro->IsFirst;
319 String->LastNewlineOffset = Macro->LastNewlineOffset;
320 String->WhitespaceRange = Macro->WhitespaceRange;
321 String->OriginalColumn = Macro->OriginalColumn;
322 String->ColumnWidth = encoding::columnWidthWithTabs(
323 String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding);
324 String->NewlinesBefore = Macro->NewlinesBefore;
325 String->HasUnescapedNewline = Macro->HasUnescapedNewline;
330 Tokens.back() = String;
334 bool FormatTokenLexer::tryMergeConflictMarkers() {
335 if (Tokens.back()->NewlinesBefore == 0 && Tokens.back()->isNot(tok::eof))
338 // Conflict lines look like:
339 // <marker> <text from the vcs>
341 // >>>>>>> /file/in/file/system at revision 1234
343 // We merge all tokens in a line that starts with a conflict marker
344 // into a single token with a special token type that the unwrapped line
345 // parser will use to correctly rebuild the underlying code.
348 // Get the position of the first token in the line.
349 unsigned FirstInLineOffset;
350 std::tie(ID, FirstInLineOffset) = SourceMgr.getDecomposedLoc(
351 Tokens[FirstInLineIndex]->getStartOfNonWhitespace());
352 StringRef Buffer = SourceMgr.getBuffer(ID)->getBuffer();
353 // Calculate the offset of the start of the current line.
354 auto LineOffset = Buffer.rfind('\n', FirstInLineOffset);
355 if (LineOffset == StringRef::npos) {
361 auto FirstSpace = Buffer.find_first_of(" \n", LineOffset);
363 if (FirstSpace == StringRef::npos) {
364 LineStart = Buffer.substr(LineOffset);
366 LineStart = Buffer.substr(LineOffset, FirstSpace - LineOffset);
369 TokenType Type = TT_Unknown;
370 if (LineStart == "<<<<<<<" || LineStart == ">>>>") {
371 Type = TT_ConflictStart;
372 } else if (LineStart == "|||||||" || LineStart == "=======" ||
373 LineStart == "====") {
374 Type = TT_ConflictAlternative;
375 } else if (LineStart == ">>>>>>>" || LineStart == "<<<<") {
376 Type = TT_ConflictEnd;
379 if (Type != TT_Unknown) {
380 FormatToken *Next = Tokens.back();
382 Tokens.resize(FirstInLineIndex + 1);
383 // We do not need to build a complete token here, as we will skip it
384 // during parsing anyway (as we must not touch whitespace around conflict
386 Tokens.back()->Type = Type;
387 Tokens.back()->Tok.setKind(tok::kw___unknown_anytype);
389 Tokens.push_back(Next);
396 FormatToken *FormatTokenLexer::getStashedToken() {
397 // Create a synthesized second '>' or '<' token.
398 Token Tok = FormatTok->Tok;
399 StringRef TokenText = FormatTok->TokenText;
401 unsigned OriginalColumn = FormatTok->OriginalColumn;
402 FormatTok = new (Allocator.Allocate()) FormatToken;
403 FormatTok->Tok = Tok;
404 SourceLocation TokLocation =
405 FormatTok->Tok.getLocation().getLocWithOffset(Tok.getLength() - 1);
406 FormatTok->Tok.setLocation(TokLocation);
407 FormatTok->WhitespaceRange = SourceRange(TokLocation, TokLocation);
408 FormatTok->TokenText = TokenText;
409 FormatTok->ColumnWidth = 1;
410 FormatTok->OriginalColumn = OriginalColumn + 1;
415 FormatToken *FormatTokenLexer::getNextToken() {
416 if (StateStack.top() == LexerState::TOKEN_STASHED) {
418 return getStashedToken();
421 FormatTok = new (Allocator.Allocate()) FormatToken;
422 readRawToken(*FormatTok);
423 SourceLocation WhitespaceStart =
424 FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
425 FormatTok->IsFirst = IsFirstToken;
426 IsFirstToken = false;
428 // Consume and record whitespace until we find a significant token.
429 unsigned WhitespaceLength = TrailingWhitespace;
430 while (FormatTok->Tok.is(tok::unknown)) {
431 StringRef Text = FormatTok->TokenText;
432 auto EscapesNewline = [&](int pos) {
433 // A '\r' here is just part of '\r\n'. Skip it.
434 if (pos >= 0 && Text[pos] == '\r')
436 // See whether there is an odd number of '\' before this.
438 for (; pos >= 0; --pos, ++count)
439 if (Text[pos] != '\\')
443 // FIXME: This miscounts tok:unknown tokens that are not just
444 // whitespace, e.g. a '`' character.
445 for (int i = 0, e = Text.size(); i != e; ++i) {
448 ++FormatTok->NewlinesBefore;
449 FormatTok->HasUnescapedNewline = !EscapesNewline(i - 1);
450 FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
454 FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
465 Column += Style.TabWidth - Column % Style.TabWidth;
468 if (i + 1 == e || (Text[i + 1] != '\r' && Text[i + 1] != '\n'))
469 FormatTok->Type = TT_ImplicitStringLiteral;
472 FormatTok->Type = TT_ImplicitStringLiteral;
475 if (FormatTok->Type == TT_ImplicitStringLiteral)
479 if (FormatTok->is(TT_ImplicitStringLiteral))
481 WhitespaceLength += FormatTok->Tok.getLength();
483 readRawToken(*FormatTok);
486 // In case the token starts with escaped newlines, we want to
487 // take them into account as whitespace - this pattern is quite frequent
488 // in macro definitions.
489 // FIXME: Add a more explicit test.
490 while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
491 FormatTok->TokenText[1] == '\n') {
492 ++FormatTok->NewlinesBefore;
493 WhitespaceLength += 2;
494 FormatTok->LastNewlineOffset = 2;
496 FormatTok->TokenText = FormatTok->TokenText.substr(2);
499 FormatTok->WhitespaceRange = SourceRange(
500 WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
502 FormatTok->OriginalColumn = Column;
504 TrailingWhitespace = 0;
505 if (FormatTok->Tok.is(tok::comment)) {
506 // FIXME: Add the trimmed whitespace to Column.
507 StringRef UntrimmedText = FormatTok->TokenText;
508 FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
509 TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
510 } else if (FormatTok->Tok.is(tok::raw_identifier)) {
511 IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
512 FormatTok->Tok.setIdentifierInfo(&Info);
513 FormatTok->Tok.setKind(Info.getTokenID());
514 if (Style.Language == FormatStyle::LK_Java &&
515 FormatTok->isOneOf(tok::kw_struct, tok::kw_union, tok::kw_delete,
517 FormatTok->Tok.setKind(tok::identifier);
518 FormatTok->Tok.setIdentifierInfo(nullptr);
519 } else if (Style.Language == FormatStyle::LK_JavaScript &&
520 FormatTok->isOneOf(tok::kw_struct, tok::kw_union,
522 FormatTok->Tok.setKind(tok::identifier);
523 FormatTok->Tok.setIdentifierInfo(nullptr);
525 } else if (FormatTok->Tok.is(tok::greatergreater)) {
526 FormatTok->Tok.setKind(tok::greater);
527 FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
529 StateStack.push(LexerState::TOKEN_STASHED);
530 } else if (FormatTok->Tok.is(tok::lessless)) {
531 FormatTok->Tok.setKind(tok::less);
532 FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
534 StateStack.push(LexerState::TOKEN_STASHED);
537 // Now FormatTok is the next non-whitespace token.
539 StringRef Text = FormatTok->TokenText;
540 size_t FirstNewlinePos = Text.find('\n');
541 if (FirstNewlinePos == StringRef::npos) {
542 // FIXME: ColumnWidth actually depends on the start column, we need to
543 // take this into account when the token is moved.
544 FormatTok->ColumnWidth =
545 encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding);
546 Column += FormatTok->ColumnWidth;
548 FormatTok->IsMultiline = true;
549 // FIXME: ColumnWidth actually depends on the start column, we need to
550 // take this into account when the token is moved.
551 FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
552 Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding);
554 // The last line of the token always starts in column 0.
555 // Thus, the length can be precomputed even in the presence of tabs.
556 FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
557 Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth, Encoding);
558 Column = FormatTok->LastLineColumnWidth;
561 if (Style.Language == FormatStyle::LK_Cpp ||
562 Style.Language == FormatStyle::LK_ObjC) {
563 if (!(Tokens.size() > 0 && Tokens.back()->Tok.getIdentifierInfo() &&
564 Tokens.back()->Tok.getIdentifierInfo()->getPPKeywordID() ==
566 std::find(ForEachMacros.begin(), ForEachMacros.end(),
567 FormatTok->Tok.getIdentifierInfo()) != ForEachMacros.end()) {
568 FormatTok->Type = TT_ForEachMacro;
569 } else if (FormatTok->is(tok::identifier)) {
570 if (MacroBlockBeginRegex.match(Text)) {
571 FormatTok->Type = TT_MacroBlockBegin;
572 } else if (MacroBlockEndRegex.match(Text)) {
573 FormatTok->Type = TT_MacroBlockEnd;
581 void FormatTokenLexer::readRawToken(FormatToken &Tok) {
582 Lex->LexFromRawLexer(Tok.Tok);
583 Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
584 Tok.Tok.getLength());
585 // For formatting, treat unterminated string literals like normal string
587 if (Tok.is(tok::unknown)) {
588 if (!Tok.TokenText.empty() && Tok.TokenText[0] == '"') {
589 Tok.Tok.setKind(tok::string_literal);
590 Tok.IsUnterminatedLiteral = true;
591 } else if (Style.Language == FormatStyle::LK_JavaScript &&
592 Tok.TokenText == "''") {
593 Tok.Tok.setKind(tok::string_literal);
597 if (Style.Language == FormatStyle::LK_JavaScript &&
598 Tok.is(tok::char_constant)) {
599 Tok.Tok.setKind(tok::string_literal);
602 if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format on" ||
603 Tok.TokenText == "/* clang-format on */")) {
604 FormattingDisabled = false;
607 Tok.Finalized = FormattingDisabled;
609 if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format off" ||
610 Tok.TokenText == "/* clang-format off */")) {
611 FormattingDisabled = true;
615 void FormatTokenLexer::resetLexer(unsigned Offset) {
616 StringRef Buffer = SourceMgr.getBufferData(ID);
617 Lex.reset(new Lexer(SourceMgr.getLocForStartOfFile(ID),
618 getFormattingLangOpts(Style), Buffer.begin(),
619 Buffer.begin() + Offset, Buffer.end()));
620 Lex->SetKeepWhitespaceMode(true);
621 TrailingWhitespace = 0;
624 } // namespace format