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