1 //===--- Format.cpp - Format C++ code -------------------------------------===//
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 functions declared in Format.h. This will be
11 /// split into separate files as we go.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #include "clang/Format/Format.h"
16 #include "AffectedRangeManager.h"
17 #include "BreakableToken.h"
18 #include "ContinuationIndenter.h"
19 #include "FormatInternal.h"
20 #include "FormatTokenLexer.h"
21 #include "NamespaceEndCommentsFixer.h"
22 #include "QualifierAlignmentFixer.h"
23 #include "SortJavaScriptImports.h"
24 #include "TokenAnalyzer.h"
25 #include "TokenAnnotator.h"
26 #include "UnwrappedLineFormatter.h"
27 #include "UnwrappedLineParser.h"
28 #include "UsingDeclarationsSorter.h"
29 #include "WhitespaceManager.h"
30 #include "clang/Basic/Diagnostic.h"
31 #include "clang/Basic/DiagnosticOptions.h"
32 #include "clang/Basic/SourceManager.h"
33 #include "clang/Lex/Lexer.h"
34 #include "clang/Tooling/Inclusions/HeaderIncludes.h"
35 #include "llvm/ADT/STLExtras.h"
36 #include "llvm/ADT/StringRef.h"
37 #include "llvm/Support/Allocator.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/Path.h"
40 #include "llvm/Support/Regex.h"
41 #include "llvm/Support/VirtualFileSystem.h"
42 #include "llvm/Support/YAMLTraits.h"
43 #include <algorithm>
44 #include <memory>
45 #include <mutex>
46 #include <string>
47 #include <unordered_map>
48 
49 #define DEBUG_TYPE "format-formatter"
50 
51 using clang::format::FormatStyle;
52 
53 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::format::FormatStyle::RawStringFormat)
54 
55 namespace llvm {
56 namespace yaml {
57 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
58   static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
59     IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
60     IO.enumCase(Value, "Java", FormatStyle::LK_Java);
61     IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
62     IO.enumCase(Value, "ObjC", FormatStyle::LK_ObjC);
63     IO.enumCase(Value, "Proto", FormatStyle::LK_Proto);
64     IO.enumCase(Value, "TableGen", FormatStyle::LK_TableGen);
65     IO.enumCase(Value, "TextProto", FormatStyle::LK_TextProto);
66     IO.enumCase(Value, "CSharp", FormatStyle::LK_CSharp);
67     IO.enumCase(Value, "Json", FormatStyle::LK_Json);
68   }
69 };
70 
71 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
72   static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
73     IO.enumCase(Value, "c++03", FormatStyle::LS_Cpp03);
74     IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03); // Legacy alias
75     IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03); // Legacy alias
76 
77     IO.enumCase(Value, "c++11", FormatStyle::LS_Cpp11);
78     IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11); // Legacy alias
79 
80     IO.enumCase(Value, "c++14", FormatStyle::LS_Cpp14);
81     IO.enumCase(Value, "c++17", FormatStyle::LS_Cpp17);
82     IO.enumCase(Value, "c++20", FormatStyle::LS_Cpp20);
83 
84     IO.enumCase(Value, "Latest", FormatStyle::LS_Latest);
85     IO.enumCase(Value, "Cpp11", FormatStyle::LS_Latest); // Legacy alias
86     IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
87   }
88 };
89 
90 template <>
91 struct ScalarEnumerationTraits<FormatStyle::LambdaBodyIndentationKind> {
92   static void enumeration(IO &IO,
93                           FormatStyle::LambdaBodyIndentationKind &Value) {
94     IO.enumCase(Value, "Signature", FormatStyle::LBI_Signature);
95     IO.enumCase(Value, "OuterScope", FormatStyle::LBI_OuterScope);
96   }
97 };
98 
99 template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
100   static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
101     IO.enumCase(Value, "Never", FormatStyle::UT_Never);
102     IO.enumCase(Value, "false", FormatStyle::UT_Never);
103     IO.enumCase(Value, "Always", FormatStyle::UT_Always);
104     IO.enumCase(Value, "true", FormatStyle::UT_Always);
105     IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
106     IO.enumCase(Value, "ForContinuationAndIndentation",
107                 FormatStyle::UT_ForContinuationAndIndentation);
108     IO.enumCase(Value, "AlignWithSpaces", FormatStyle::UT_AlignWithSpaces);
109   }
110 };
111 
112 template <> struct ScalarEnumerationTraits<FormatStyle::JavaScriptQuoteStyle> {
113   static void enumeration(IO &IO, FormatStyle::JavaScriptQuoteStyle &Value) {
114     IO.enumCase(Value, "Leave", FormatStyle::JSQS_Leave);
115     IO.enumCase(Value, "Single", FormatStyle::JSQS_Single);
116     IO.enumCase(Value, "Double", FormatStyle::JSQS_Double);
117   }
118 };
119 
120 template <> struct ScalarEnumerationTraits<FormatStyle::ShortBlockStyle> {
121   static void enumeration(IO &IO, FormatStyle::ShortBlockStyle &Value) {
122     IO.enumCase(Value, "Never", FormatStyle::SBS_Never);
123     IO.enumCase(Value, "false", FormatStyle::SBS_Never);
124     IO.enumCase(Value, "Always", FormatStyle::SBS_Always);
125     IO.enumCase(Value, "true", FormatStyle::SBS_Always);
126     IO.enumCase(Value, "Empty", FormatStyle::SBS_Empty);
127   }
128 };
129 
130 template <>
131 struct ScalarEnumerationTraits<FormatStyle::QualifierAlignmentStyle> {
132   static void enumeration(IO &IO, FormatStyle::QualifierAlignmentStyle &Value) {
133     IO.enumCase(Value, "Leave", FormatStyle::QAS_Leave);
134     IO.enumCase(Value, "Left", FormatStyle::QAS_Left);
135     IO.enumCase(Value, "Right", FormatStyle::QAS_Right);
136     IO.enumCase(Value, "Custom", FormatStyle::QAS_Custom);
137   }
138 };
139 
140 template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
141   static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
142     IO.enumCase(Value, "None", FormatStyle::SFS_None);
143     IO.enumCase(Value, "false", FormatStyle::SFS_None);
144     IO.enumCase(Value, "All", FormatStyle::SFS_All);
145     IO.enumCase(Value, "true", FormatStyle::SFS_All);
146     IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
147     IO.enumCase(Value, "InlineOnly", FormatStyle::SFS_InlineOnly);
148     IO.enumCase(Value, "Empty", FormatStyle::SFS_Empty);
149   }
150 };
151 
152 template <> struct ScalarEnumerationTraits<FormatStyle::AlignConsecutiveStyle> {
153   static void enumeration(IO &IO, FormatStyle::AlignConsecutiveStyle &Value) {
154     IO.enumCase(Value, "None", FormatStyle::ACS_None);
155     IO.enumCase(Value, "Consecutive", FormatStyle::ACS_Consecutive);
156     IO.enumCase(Value, "AcrossEmptyLines", FormatStyle::ACS_AcrossEmptyLines);
157     IO.enumCase(Value, "AcrossComments", FormatStyle::ACS_AcrossComments);
158     IO.enumCase(Value, "AcrossEmptyLinesAndComments",
159                 FormatStyle::ACS_AcrossEmptyLinesAndComments);
160 
161     // For backward compatibility.
162     IO.enumCase(Value, "true", FormatStyle::ACS_Consecutive);
163     IO.enumCase(Value, "false", FormatStyle::ACS_None);
164   }
165 };
166 
167 template <>
168 struct ScalarEnumerationTraits<FormatStyle::ArrayInitializerAlignmentStyle> {
169   static void enumeration(IO &IO,
170                           FormatStyle::ArrayInitializerAlignmentStyle &Value) {
171     IO.enumCase(Value, "None", FormatStyle::AIAS_None);
172     IO.enumCase(Value, "Left", FormatStyle::AIAS_Left);
173     IO.enumCase(Value, "Right", FormatStyle::AIAS_Right);
174   }
175 };
176 
177 template <> struct ScalarEnumerationTraits<FormatStyle::ShortIfStyle> {
178   static void enumeration(IO &IO, FormatStyle::ShortIfStyle &Value) {
179     IO.enumCase(Value, "Never", FormatStyle::SIS_Never);
180     IO.enumCase(Value, "WithoutElse", FormatStyle::SIS_WithoutElse);
181     IO.enumCase(Value, "OnlyFirstIf", FormatStyle::SIS_OnlyFirstIf);
182     IO.enumCase(Value, "AllIfsAndElse", FormatStyle::SIS_AllIfsAndElse);
183 
184     // For backward compatibility.
185     IO.enumCase(Value, "Always", FormatStyle::SIS_OnlyFirstIf);
186     IO.enumCase(Value, "false", FormatStyle::SIS_Never);
187     IO.enumCase(Value, "true", FormatStyle::SIS_WithoutElse);
188   }
189 };
190 
191 template <> struct ScalarEnumerationTraits<FormatStyle::ShortLambdaStyle> {
192   static void enumeration(IO &IO, FormatStyle::ShortLambdaStyle &Value) {
193     IO.enumCase(Value, "None", FormatStyle::SLS_None);
194     IO.enumCase(Value, "false", FormatStyle::SLS_None);
195     IO.enumCase(Value, "Empty", FormatStyle::SLS_Empty);
196     IO.enumCase(Value, "Inline", FormatStyle::SLS_Inline);
197     IO.enumCase(Value, "All", FormatStyle::SLS_All);
198     IO.enumCase(Value, "true", FormatStyle::SLS_All);
199   }
200 };
201 
202 template <> struct ScalarEnumerationTraits<FormatStyle::BinPackStyle> {
203   static void enumeration(IO &IO, FormatStyle::BinPackStyle &Value) {
204     IO.enumCase(Value, "Auto", FormatStyle::BPS_Auto);
205     IO.enumCase(Value, "Always", FormatStyle::BPS_Always);
206     IO.enumCase(Value, "Never", FormatStyle::BPS_Never);
207   }
208 };
209 
210 template <> struct ScalarEnumerationTraits<FormatStyle::TrailingCommaStyle> {
211   static void enumeration(IO &IO, FormatStyle::TrailingCommaStyle &Value) {
212     IO.enumCase(Value, "None", FormatStyle::TCS_None);
213     IO.enumCase(Value, "Wrapped", FormatStyle::TCS_Wrapped);
214   }
215 };
216 
217 template <> struct ScalarEnumerationTraits<FormatStyle::BinaryOperatorStyle> {
218   static void enumeration(IO &IO, FormatStyle::BinaryOperatorStyle &Value) {
219     IO.enumCase(Value, "All", FormatStyle::BOS_All);
220     IO.enumCase(Value, "true", FormatStyle::BOS_All);
221     IO.enumCase(Value, "None", FormatStyle::BOS_None);
222     IO.enumCase(Value, "false", FormatStyle::BOS_None);
223     IO.enumCase(Value, "NonAssignment", FormatStyle::BOS_NonAssignment);
224   }
225 };
226 
227 template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
228   static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
229     IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
230     IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
231     IO.enumCase(Value, "Mozilla", FormatStyle::BS_Mozilla);
232     IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
233     IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
234     IO.enumCase(Value, "Whitesmiths", FormatStyle::BS_Whitesmiths);
235     IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
236     IO.enumCase(Value, "WebKit", FormatStyle::BS_WebKit);
237     IO.enumCase(Value, "Custom", FormatStyle::BS_Custom);
238   }
239 };
240 
241 template <>
242 struct ScalarEnumerationTraits<
243     FormatStyle::BraceWrappingAfterControlStatementStyle> {
244   static void
245   enumeration(IO &IO,
246               FormatStyle::BraceWrappingAfterControlStatementStyle &Value) {
247     IO.enumCase(Value, "Never", FormatStyle::BWACS_Never);
248     IO.enumCase(Value, "MultiLine", FormatStyle::BWACS_MultiLine);
249     IO.enumCase(Value, "Always", FormatStyle::BWACS_Always);
250 
251     // For backward compatibility.
252     IO.enumCase(Value, "false", FormatStyle::BWACS_Never);
253     IO.enumCase(Value, "true", FormatStyle::BWACS_Always);
254   }
255 };
256 
257 template <>
258 struct ScalarEnumerationTraits<FormatStyle::BreakConstructorInitializersStyle> {
259   static void
260   enumeration(IO &IO, FormatStyle::BreakConstructorInitializersStyle &Value) {
261     IO.enumCase(Value, "BeforeColon", FormatStyle::BCIS_BeforeColon);
262     IO.enumCase(Value, "BeforeComma", FormatStyle::BCIS_BeforeComma);
263     IO.enumCase(Value, "AfterColon", FormatStyle::BCIS_AfterColon);
264   }
265 };
266 
267 template <>
268 struct ScalarEnumerationTraits<FormatStyle::BreakInheritanceListStyle> {
269   static void enumeration(IO &IO,
270                           FormatStyle::BreakInheritanceListStyle &Value) {
271     IO.enumCase(Value, "BeforeColon", FormatStyle::BILS_BeforeColon);
272     IO.enumCase(Value, "BeforeComma", FormatStyle::BILS_BeforeComma);
273     IO.enumCase(Value, "AfterColon", FormatStyle::BILS_AfterColon);
274     IO.enumCase(Value, "AfterComma", FormatStyle::BILS_AfterComma);
275   }
276 };
277 
278 template <>
279 struct ScalarEnumerationTraits<FormatStyle::PackConstructorInitializersStyle> {
280   static void
281   enumeration(IO &IO, FormatStyle::PackConstructorInitializersStyle &Value) {
282     IO.enumCase(Value, "Never", FormatStyle::PCIS_Never);
283     IO.enumCase(Value, "BinPack", FormatStyle::PCIS_BinPack);
284     IO.enumCase(Value, "CurrentLine", FormatStyle::PCIS_CurrentLine);
285     IO.enumCase(Value, "NextLine", FormatStyle::PCIS_NextLine);
286   }
287 };
288 
289 template <>
290 struct ScalarEnumerationTraits<FormatStyle::EmptyLineAfterAccessModifierStyle> {
291   static void
292   enumeration(IO &IO, FormatStyle::EmptyLineAfterAccessModifierStyle &Value) {
293     IO.enumCase(Value, "Never", FormatStyle::ELAAMS_Never);
294     IO.enumCase(Value, "Leave", FormatStyle::ELAAMS_Leave);
295     IO.enumCase(Value, "Always", FormatStyle::ELAAMS_Always);
296   }
297 };
298 
299 template <>
300 struct ScalarEnumerationTraits<
301     FormatStyle::EmptyLineBeforeAccessModifierStyle> {
302   static void
303   enumeration(IO &IO, FormatStyle::EmptyLineBeforeAccessModifierStyle &Value) {
304     IO.enumCase(Value, "Never", FormatStyle::ELBAMS_Never);
305     IO.enumCase(Value, "Leave", FormatStyle::ELBAMS_Leave);
306     IO.enumCase(Value, "LogicalBlock", FormatStyle::ELBAMS_LogicalBlock);
307     IO.enumCase(Value, "Always", FormatStyle::ELBAMS_Always);
308   }
309 };
310 
311 template <>
312 struct ScalarEnumerationTraits<FormatStyle::PPDirectiveIndentStyle> {
313   static void enumeration(IO &IO, FormatStyle::PPDirectiveIndentStyle &Value) {
314     IO.enumCase(Value, "None", FormatStyle::PPDIS_None);
315     IO.enumCase(Value, "AfterHash", FormatStyle::PPDIS_AfterHash);
316     IO.enumCase(Value, "BeforeHash", FormatStyle::PPDIS_BeforeHash);
317   }
318 };
319 
320 template <>
321 struct ScalarEnumerationTraits<FormatStyle::IndentExternBlockStyle> {
322   static void enumeration(IO &IO, FormatStyle::IndentExternBlockStyle &Value) {
323     IO.enumCase(Value, "AfterExternBlock", FormatStyle::IEBS_AfterExternBlock);
324     IO.enumCase(Value, "Indent", FormatStyle::IEBS_Indent);
325     IO.enumCase(Value, "NoIndent", FormatStyle::IEBS_NoIndent);
326     IO.enumCase(Value, "true", FormatStyle::IEBS_Indent);
327     IO.enumCase(Value, "false", FormatStyle::IEBS_NoIndent);
328   }
329 };
330 
331 template <>
332 struct ScalarEnumerationTraits<FormatStyle::ReturnTypeBreakingStyle> {
333   static void enumeration(IO &IO, FormatStyle::ReturnTypeBreakingStyle &Value) {
334     IO.enumCase(Value, "None", FormatStyle::RTBS_None);
335     IO.enumCase(Value, "All", FormatStyle::RTBS_All);
336     IO.enumCase(Value, "TopLevel", FormatStyle::RTBS_TopLevel);
337     IO.enumCase(Value, "TopLevelDefinitions",
338                 FormatStyle::RTBS_TopLevelDefinitions);
339     IO.enumCase(Value, "AllDefinitions", FormatStyle::RTBS_AllDefinitions);
340   }
341 };
342 
343 template <>
344 struct ScalarEnumerationTraits<FormatStyle::BreakTemplateDeclarationsStyle> {
345   static void enumeration(IO &IO,
346                           FormatStyle::BreakTemplateDeclarationsStyle &Value) {
347     IO.enumCase(Value, "No", FormatStyle::BTDS_No);
348     IO.enumCase(Value, "MultiLine", FormatStyle::BTDS_MultiLine);
349     IO.enumCase(Value, "Yes", FormatStyle::BTDS_Yes);
350 
351     // For backward compatibility.
352     IO.enumCase(Value, "false", FormatStyle::BTDS_MultiLine);
353     IO.enumCase(Value, "true", FormatStyle::BTDS_Yes);
354   }
355 };
356 
357 template <>
358 struct ScalarEnumerationTraits<FormatStyle::DefinitionReturnTypeBreakingStyle> {
359   static void
360   enumeration(IO &IO, FormatStyle::DefinitionReturnTypeBreakingStyle &Value) {
361     IO.enumCase(Value, "None", FormatStyle::DRTBS_None);
362     IO.enumCase(Value, "All", FormatStyle::DRTBS_All);
363     IO.enumCase(Value, "TopLevel", FormatStyle::DRTBS_TopLevel);
364 
365     // For backward compatibility.
366     IO.enumCase(Value, "false", FormatStyle::DRTBS_None);
367     IO.enumCase(Value, "true", FormatStyle::DRTBS_All);
368   }
369 };
370 
371 template <>
372 struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
373   static void enumeration(IO &IO,
374                           FormatStyle::NamespaceIndentationKind &Value) {
375     IO.enumCase(Value, "None", FormatStyle::NI_None);
376     IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
377     IO.enumCase(Value, "All", FormatStyle::NI_All);
378   }
379 };
380 
381 template <> struct ScalarEnumerationTraits<FormatStyle::BracketAlignmentStyle> {
382   static void enumeration(IO &IO, FormatStyle::BracketAlignmentStyle &Value) {
383     IO.enumCase(Value, "Align", FormatStyle::BAS_Align);
384     IO.enumCase(Value, "DontAlign", FormatStyle::BAS_DontAlign);
385     IO.enumCase(Value, "AlwaysBreak", FormatStyle::BAS_AlwaysBreak);
386 
387     // For backward compatibility.
388     IO.enumCase(Value, "true", FormatStyle::BAS_Align);
389     IO.enumCase(Value, "false", FormatStyle::BAS_DontAlign);
390   }
391 };
392 
393 template <>
394 struct ScalarEnumerationTraits<FormatStyle::EscapedNewlineAlignmentStyle> {
395   static void enumeration(IO &IO,
396                           FormatStyle::EscapedNewlineAlignmentStyle &Value) {
397     IO.enumCase(Value, "DontAlign", FormatStyle::ENAS_DontAlign);
398     IO.enumCase(Value, "Left", FormatStyle::ENAS_Left);
399     IO.enumCase(Value, "Right", FormatStyle::ENAS_Right);
400 
401     // For backward compatibility.
402     IO.enumCase(Value, "true", FormatStyle::ENAS_Left);
403     IO.enumCase(Value, "false", FormatStyle::ENAS_Right);
404   }
405 };
406 
407 template <> struct ScalarEnumerationTraits<FormatStyle::OperandAlignmentStyle> {
408   static void enumeration(IO &IO, FormatStyle::OperandAlignmentStyle &Value) {
409     IO.enumCase(Value, "DontAlign", FormatStyle::OAS_DontAlign);
410     IO.enumCase(Value, "Align", FormatStyle::OAS_Align);
411     IO.enumCase(Value, "AlignAfterOperator",
412                 FormatStyle::OAS_AlignAfterOperator);
413 
414     // For backward compatibility.
415     IO.enumCase(Value, "true", FormatStyle::OAS_Align);
416     IO.enumCase(Value, "false", FormatStyle::OAS_DontAlign);
417   }
418 };
419 
420 template <> struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
421   static void enumeration(IO &IO, FormatStyle::PointerAlignmentStyle &Value) {
422     IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
423     IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
424     IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
425 
426     // For backward compatibility.
427     IO.enumCase(Value, "true", FormatStyle::PAS_Left);
428     IO.enumCase(Value, "false", FormatStyle::PAS_Right);
429   }
430 };
431 
432 template <>
433 struct ScalarEnumerationTraits<FormatStyle::SpaceAroundPointerQualifiersStyle> {
434   static void
435   enumeration(IO &IO, FormatStyle::SpaceAroundPointerQualifiersStyle &Value) {
436     IO.enumCase(Value, "Default", FormatStyle::SAPQ_Default);
437     IO.enumCase(Value, "Before", FormatStyle::SAPQ_Before);
438     IO.enumCase(Value, "After", FormatStyle::SAPQ_After);
439     IO.enumCase(Value, "Both", FormatStyle::SAPQ_Both);
440   }
441 };
442 
443 template <>
444 struct ScalarEnumerationTraits<FormatStyle::ReferenceAlignmentStyle> {
445   static void enumeration(IO &IO, FormatStyle::ReferenceAlignmentStyle &Value) {
446     IO.enumCase(Value, "Pointer", FormatStyle::RAS_Pointer);
447     IO.enumCase(Value, "Middle", FormatStyle::RAS_Middle);
448     IO.enumCase(Value, "Left", FormatStyle::RAS_Left);
449     IO.enumCase(Value, "Right", FormatStyle::RAS_Right);
450   }
451 };
452 
453 template <>
454 struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
455   static void enumeration(IO &IO,
456                           FormatStyle::SpaceBeforeParensOptions &Value) {
457     IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
458     IO.enumCase(Value, "ControlStatements",
459                 FormatStyle::SBPO_ControlStatements);
460     IO.enumCase(Value, "ControlStatementsExceptControlMacros",
461                 FormatStyle::SBPO_ControlStatementsExceptControlMacros);
462     IO.enumCase(Value, "NonEmptyParentheses",
463                 FormatStyle::SBPO_NonEmptyParentheses);
464     IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
465 
466     // For backward compatibility.
467     IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
468     IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
469     IO.enumCase(Value, "ControlStatementsExceptForEachMacros",
470                 FormatStyle::SBPO_ControlStatementsExceptControlMacros);
471   }
472 };
473 
474 template <>
475 struct ScalarEnumerationTraits<FormatStyle::BitFieldColonSpacingStyle> {
476   static void enumeration(IO &IO,
477                           FormatStyle::BitFieldColonSpacingStyle &Value) {
478     IO.enumCase(Value, "Both", FormatStyle::BFCS_Both);
479     IO.enumCase(Value, "None", FormatStyle::BFCS_None);
480     IO.enumCase(Value, "Before", FormatStyle::BFCS_Before);
481     IO.enumCase(Value, "After", FormatStyle::BFCS_After);
482   }
483 };
484 
485 template <> struct ScalarEnumerationTraits<FormatStyle::SortIncludesOptions> {
486   static void enumeration(IO &IO, FormatStyle::SortIncludesOptions &Value) {
487     IO.enumCase(Value, "Never", FormatStyle::SI_Never);
488     IO.enumCase(Value, "CaseInsensitive", FormatStyle::SI_CaseInsensitive);
489     IO.enumCase(Value, "CaseSensitive", FormatStyle::SI_CaseSensitive);
490 
491     // For backward compatibility.
492     IO.enumCase(Value, "false", FormatStyle::SI_Never);
493     IO.enumCase(Value, "true", FormatStyle::SI_CaseSensitive);
494   }
495 };
496 
497 template <>
498 struct ScalarEnumerationTraits<FormatStyle::SortJavaStaticImportOptions> {
499   static void enumeration(IO &IO,
500                           FormatStyle::SortJavaStaticImportOptions &Value) {
501     IO.enumCase(Value, "Before", FormatStyle::SJSIO_Before);
502     IO.enumCase(Value, "After", FormatStyle::SJSIO_After);
503   }
504 };
505 
506 template <> struct ScalarEnumerationTraits<FormatStyle::SpacesInAnglesStyle> {
507   static void enumeration(IO &IO, FormatStyle::SpacesInAnglesStyle &Value) {
508     IO.enumCase(Value, "Never", FormatStyle::SIAS_Never);
509     IO.enumCase(Value, "Always", FormatStyle::SIAS_Always);
510     IO.enumCase(Value, "Leave", FormatStyle::SIAS_Leave);
511 
512     // For backward compatibility.
513     IO.enumCase(Value, "false", FormatStyle::SIAS_Never);
514     IO.enumCase(Value, "true", FormatStyle::SIAS_Always);
515   }
516 };
517 
518 template <> struct MappingTraits<FormatStyle> {
519   static void mapping(IO &IO, FormatStyle &Style) {
520     // When reading, read the language first, we need it for getPredefinedStyle.
521     IO.mapOptional("Language", Style.Language);
522 
523     if (IO.outputting()) {
524       StringRef StylesArray[] = {"LLVM",   "Google", "Chromium", "Mozilla",
525                                  "WebKit", "GNU",    "Microsoft"};
526       ArrayRef<StringRef> Styles(StylesArray);
527       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
528         StringRef StyleName(Styles[i]);
529         FormatStyle PredefinedStyle;
530         if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
531             Style == PredefinedStyle) {
532           IO.mapOptional("# BasedOnStyle", StyleName);
533           break;
534         }
535       }
536     } else {
537       StringRef BasedOnStyle;
538       IO.mapOptional("BasedOnStyle", BasedOnStyle);
539       if (!BasedOnStyle.empty()) {
540         FormatStyle::LanguageKind OldLanguage = Style.Language;
541         FormatStyle::LanguageKind Language =
542             ((FormatStyle *)IO.getContext())->Language;
543         if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
544           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
545           return;
546         }
547         Style.Language = OldLanguage;
548       }
549     }
550 
551     // For backward compatibility.
552     if (!IO.outputting()) {
553       IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlines);
554       IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
555       IO.mapOptional("IndentFunctionDeclarationAfterType",
556                      Style.IndentWrappedFunctionNames);
557       IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
558       IO.mapOptional("SpaceAfterControlStatementKeyword",
559                      Style.SpaceBeforeParens);
560     }
561 
562     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
563     IO.mapOptional("AlignAfterOpenBracket", Style.AlignAfterOpenBracket);
564     IO.mapOptional("AlignArrayOfStructures", Style.AlignArrayOfStructures);
565     IO.mapOptional("AlignConsecutiveMacros", Style.AlignConsecutiveMacros);
566     IO.mapOptional("AlignConsecutiveAssignments",
567                    Style.AlignConsecutiveAssignments);
568     IO.mapOptional("AlignConsecutiveBitFields",
569                    Style.AlignConsecutiveBitFields);
570     IO.mapOptional("AlignConsecutiveDeclarations",
571                    Style.AlignConsecutiveDeclarations);
572     IO.mapOptional("AlignEscapedNewlines", Style.AlignEscapedNewlines);
573     IO.mapOptional("AlignOperands", Style.AlignOperands);
574     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
575     IO.mapOptional("AllowAllArgumentsOnNextLine",
576                    Style.AllowAllArgumentsOnNextLine);
577     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
578                    Style.AllowAllParametersOfDeclarationOnNextLine);
579     IO.mapOptional("AllowShortEnumsOnASingleLine",
580                    Style.AllowShortEnumsOnASingleLine);
581     IO.mapOptional("AllowShortBlocksOnASingleLine",
582                    Style.AllowShortBlocksOnASingleLine);
583     IO.mapOptional("AllowShortCaseLabelsOnASingleLine",
584                    Style.AllowShortCaseLabelsOnASingleLine);
585     IO.mapOptional("AllowShortFunctionsOnASingleLine",
586                    Style.AllowShortFunctionsOnASingleLine);
587     IO.mapOptional("AllowShortLambdasOnASingleLine",
588                    Style.AllowShortLambdasOnASingleLine);
589     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
590                    Style.AllowShortIfStatementsOnASingleLine);
591     IO.mapOptional("AllowShortLoopsOnASingleLine",
592                    Style.AllowShortLoopsOnASingleLine);
593     IO.mapOptional("AlwaysBreakAfterDefinitionReturnType",
594                    Style.AlwaysBreakAfterDefinitionReturnType);
595     IO.mapOptional("AlwaysBreakAfterReturnType",
596                    Style.AlwaysBreakAfterReturnType);
597 
598     // If AlwaysBreakAfterDefinitionReturnType was specified but
599     // AlwaysBreakAfterReturnType was not, initialize the latter from the
600     // former for backwards compatibility.
601     if (Style.AlwaysBreakAfterDefinitionReturnType != FormatStyle::DRTBS_None &&
602         Style.AlwaysBreakAfterReturnType == FormatStyle::RTBS_None) {
603       if (Style.AlwaysBreakAfterDefinitionReturnType == FormatStyle::DRTBS_All)
604         Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
605       else if (Style.AlwaysBreakAfterDefinitionReturnType ==
606                FormatStyle::DRTBS_TopLevel)
607         Style.AlwaysBreakAfterReturnType =
608             FormatStyle::RTBS_TopLevelDefinitions;
609     }
610 
611     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
612                    Style.AlwaysBreakBeforeMultilineStrings);
613     IO.mapOptional("AlwaysBreakTemplateDeclarations",
614                    Style.AlwaysBreakTemplateDeclarations);
615     IO.mapOptional("AttributeMacros", Style.AttributeMacros);
616     IO.mapOptional("BinPackArguments", Style.BinPackArguments);
617     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
618     IO.mapOptional("BraceWrapping", Style.BraceWrapping);
619     IO.mapOptional("BreakBeforeBinaryOperators",
620                    Style.BreakBeforeBinaryOperators);
621     IO.mapOptional("BreakBeforeConceptDeclarations",
622                    Style.BreakBeforeConceptDeclarations);
623     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
624 
625     bool BreakBeforeInheritanceComma = false;
626     IO.mapOptional("BreakBeforeInheritanceComma", BreakBeforeInheritanceComma);
627     IO.mapOptional("BreakInheritanceList", Style.BreakInheritanceList);
628     // If BreakBeforeInheritanceComma was specified but
629     // BreakInheritance was not, initialize the latter from the
630     // former for backwards compatibility.
631     if (BreakBeforeInheritanceComma &&
632         Style.BreakInheritanceList == FormatStyle::BILS_BeforeColon)
633       Style.BreakInheritanceList = FormatStyle::BILS_BeforeComma;
634 
635     IO.mapOptional("BreakBeforeTernaryOperators",
636                    Style.BreakBeforeTernaryOperators);
637 
638     bool BreakConstructorInitializersBeforeComma = false;
639     IO.mapOptional("BreakConstructorInitializersBeforeComma",
640                    BreakConstructorInitializersBeforeComma);
641     IO.mapOptional("BreakConstructorInitializers",
642                    Style.BreakConstructorInitializers);
643     // If BreakConstructorInitializersBeforeComma was specified but
644     // BreakConstructorInitializers was not, initialize the latter from the
645     // former for backwards compatibility.
646     if (BreakConstructorInitializersBeforeComma &&
647         Style.BreakConstructorInitializers == FormatStyle::BCIS_BeforeColon)
648       Style.BreakConstructorInitializers = FormatStyle::BCIS_BeforeComma;
649 
650     IO.mapOptional("BreakAfterJavaFieldAnnotations",
651                    Style.BreakAfterJavaFieldAnnotations);
652     IO.mapOptional("BreakStringLiterals", Style.BreakStringLiterals);
653     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
654     IO.mapOptional("CommentPragmas", Style.CommentPragmas);
655     IO.mapOptional("QualifierAlignment", Style.QualifierAlignment);
656 
657     // Default Order for Left/Right based Qualifier alignment.
658     if (Style.QualifierAlignment == FormatStyle::QAS_Right) {
659       Style.QualifierOrder = {"type", "const", "volatile"};
660     } else if (Style.QualifierAlignment == FormatStyle::QAS_Left) {
661       Style.QualifierOrder = {"const", "volatile", "type"};
662     } else if (Style.QualifierAlignment == FormatStyle::QAS_Custom) {
663       IO.mapOptional("QualifierOrder", Style.QualifierOrder);
664     }
665 
666     IO.mapOptional("CompactNamespaces", Style.CompactNamespaces);
667     IO.mapOptional("ConstructorInitializerIndentWidth",
668                    Style.ConstructorInitializerIndentWidth);
669     IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
670     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
671     IO.mapOptional("DeriveLineEnding", Style.DeriveLineEnding);
672     IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
673     IO.mapOptional("DisableFormat", Style.DisableFormat);
674     IO.mapOptional("EmptyLineAfterAccessModifier",
675                    Style.EmptyLineAfterAccessModifier);
676     IO.mapOptional("EmptyLineBeforeAccessModifier",
677                    Style.EmptyLineBeforeAccessModifier);
678     IO.mapOptional("ExperimentalAutoDetectBinPacking",
679                    Style.ExperimentalAutoDetectBinPacking);
680 
681     IO.mapOptional("PackConstructorInitializers",
682                    Style.PackConstructorInitializers);
683     // For backward compatibility:
684     // The default value of ConstructorInitializerAllOnOneLineOrOnePerLine was
685     // false unless BasedOnStyle was Google or Chromium whereas that of
686     // AllowAllConstructorInitializersOnNextLine was always true, so the
687     // equivalent default value of PackConstructorInitializers is PCIS_NextLine
688     // for Google/Chromium or PCIS_BinPack otherwise. If the deprecated options
689     // had a non-default value while PackConstructorInitializers has a default
690     // value, set the latter to an equivalent non-default value if needed.
691     StringRef BasedOn;
692     IO.mapOptional("BasedOnStyle", BasedOn);
693     const bool IsGoogleOrChromium = BasedOn.equals_insensitive("google") ||
694                                     BasedOn.equals_insensitive("chromium");
695     bool OnCurrentLine = IsGoogleOrChromium;
696     bool OnNextLine = true;
697     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
698                    OnCurrentLine);
699     IO.mapOptional("AllowAllConstructorInitializersOnNextLine", OnNextLine);
700     if (!IsGoogleOrChromium) {
701       if (Style.PackConstructorInitializers == FormatStyle::PCIS_BinPack &&
702           OnCurrentLine) {
703         Style.PackConstructorInitializers = OnNextLine
704                                                 ? FormatStyle::PCIS_NextLine
705                                                 : FormatStyle::PCIS_CurrentLine;
706       }
707     } else if (Style.PackConstructorInitializers ==
708                FormatStyle::PCIS_NextLine) {
709       if (!OnCurrentLine)
710         Style.PackConstructorInitializers = FormatStyle::PCIS_BinPack;
711       else if (!OnNextLine)
712         Style.PackConstructorInitializers = FormatStyle::PCIS_CurrentLine;
713     }
714 
715     IO.mapOptional("FixNamespaceComments", Style.FixNamespaceComments);
716     IO.mapOptional("ForEachMacros", Style.ForEachMacros);
717     IO.mapOptional("IfMacros", Style.IfMacros);
718 
719     IO.mapOptional("IncludeBlocks", Style.IncludeStyle.IncludeBlocks);
720     IO.mapOptional("IncludeCategories", Style.IncludeStyle.IncludeCategories);
721     IO.mapOptional("IncludeIsMainRegex", Style.IncludeStyle.IncludeIsMainRegex);
722     IO.mapOptional("IncludeIsMainSourceRegex",
723                    Style.IncludeStyle.IncludeIsMainSourceRegex);
724     IO.mapOptional("IndentAccessModifiers", Style.IndentAccessModifiers);
725     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
726     IO.mapOptional("IndentCaseBlocks", Style.IndentCaseBlocks);
727     IO.mapOptional("IndentGotoLabels", Style.IndentGotoLabels);
728     IO.mapOptional("IndentPPDirectives", Style.IndentPPDirectives);
729     IO.mapOptional("IndentExternBlock", Style.IndentExternBlock);
730     IO.mapOptional("IndentRequires", Style.IndentRequires);
731     IO.mapOptional("IndentWidth", Style.IndentWidth);
732     IO.mapOptional("IndentWrappedFunctionNames",
733                    Style.IndentWrappedFunctionNames);
734     IO.mapOptional("InsertTrailingCommas", Style.InsertTrailingCommas);
735     IO.mapOptional("JavaImportGroups", Style.JavaImportGroups);
736     IO.mapOptional("JavaScriptQuotes", Style.JavaScriptQuotes);
737     IO.mapOptional("JavaScriptWrapImports", Style.JavaScriptWrapImports);
738     IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
739                    Style.KeepEmptyLinesAtTheStartOfBlocks);
740     IO.mapOptional("LambdaBodyIndentation", Style.LambdaBodyIndentation);
741     IO.mapOptional("MacroBlockBegin", Style.MacroBlockBegin);
742     IO.mapOptional("MacroBlockEnd", Style.MacroBlockEnd);
743     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
744     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
745     IO.mapOptional("NamespaceMacros", Style.NamespaceMacros);
746     IO.mapOptional("ObjCBinPackProtocolList", Style.ObjCBinPackProtocolList);
747     IO.mapOptional("ObjCBlockIndentWidth", Style.ObjCBlockIndentWidth);
748     IO.mapOptional("ObjCBreakBeforeNestedBlockParam",
749                    Style.ObjCBreakBeforeNestedBlockParam);
750     IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
751     IO.mapOptional("ObjCSpaceBeforeProtocolList",
752                    Style.ObjCSpaceBeforeProtocolList);
753     IO.mapOptional("PenaltyBreakAssignment", Style.PenaltyBreakAssignment);
754     IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
755                    Style.PenaltyBreakBeforeFirstCallParameter);
756     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
757     IO.mapOptional("PenaltyBreakFirstLessLess",
758                    Style.PenaltyBreakFirstLessLess);
759     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
760     IO.mapOptional("PenaltyBreakTemplateDeclaration",
761                    Style.PenaltyBreakTemplateDeclaration);
762     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
763     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
764                    Style.PenaltyReturnTypeOnItsOwnLine);
765     IO.mapOptional("PenaltyIndentedWhitespace",
766                    Style.PenaltyIndentedWhitespace);
767     IO.mapOptional("PointerAlignment", Style.PointerAlignment);
768     IO.mapOptional("PPIndentWidth", Style.PPIndentWidth);
769     IO.mapOptional("RawStringFormats", Style.RawStringFormats);
770     IO.mapOptional("ReferenceAlignment", Style.ReferenceAlignment);
771     IO.mapOptional("ReflowComments", Style.ReflowComments);
772     IO.mapOptional("ShortNamespaceLines", Style.ShortNamespaceLines);
773     IO.mapOptional("SortIncludes", Style.SortIncludes);
774     IO.mapOptional("SortJavaStaticImport", Style.SortJavaStaticImport);
775     IO.mapOptional("SortUsingDeclarations", Style.SortUsingDeclarations);
776     IO.mapOptional("SpaceAfterCStyleCast", Style.SpaceAfterCStyleCast);
777     IO.mapOptional("SpaceAfterLogicalNot", Style.SpaceAfterLogicalNot);
778     IO.mapOptional("SpaceAfterTemplateKeyword",
779                    Style.SpaceAfterTemplateKeyword);
780     IO.mapOptional("SpaceBeforeAssignmentOperators",
781                    Style.SpaceBeforeAssignmentOperators);
782     IO.mapOptional("SpaceBeforeCaseColon", Style.SpaceBeforeCaseColon);
783     IO.mapOptional("SpaceBeforeCpp11BracedList",
784                    Style.SpaceBeforeCpp11BracedList);
785     IO.mapOptional("SpaceBeforeCtorInitializerColon",
786                    Style.SpaceBeforeCtorInitializerColon);
787     IO.mapOptional("SpaceBeforeInheritanceColon",
788                    Style.SpaceBeforeInheritanceColon);
789     IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
790     IO.mapOptional("SpaceAroundPointerQualifiers",
791                    Style.SpaceAroundPointerQualifiers);
792     IO.mapOptional("SpaceBeforeRangeBasedForLoopColon",
793                    Style.SpaceBeforeRangeBasedForLoopColon);
794     IO.mapOptional("SpaceInEmptyBlock", Style.SpaceInEmptyBlock);
795     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
796     IO.mapOptional("SpacesBeforeTrailingComments",
797                    Style.SpacesBeforeTrailingComments);
798     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
799     IO.mapOptional("SpacesInConditionalStatement",
800                    Style.SpacesInConditionalStatement);
801     IO.mapOptional("SpacesInContainerLiterals",
802                    Style.SpacesInContainerLiterals);
803     IO.mapOptional("SpacesInCStyleCastParentheses",
804                    Style.SpacesInCStyleCastParentheses);
805     IO.mapOptional("SpacesInLineCommentPrefix",
806                    Style.SpacesInLineCommentPrefix);
807     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
808     IO.mapOptional("SpacesInSquareBrackets", Style.SpacesInSquareBrackets);
809     IO.mapOptional("SpaceBeforeSquareBrackets",
810                    Style.SpaceBeforeSquareBrackets);
811     IO.mapOptional("BitFieldColonSpacing", Style.BitFieldColonSpacing);
812     IO.mapOptional("Standard", Style.Standard);
813     IO.mapOptional("StatementAttributeLikeMacros",
814                    Style.StatementAttributeLikeMacros);
815     IO.mapOptional("StatementMacros", Style.StatementMacros);
816     IO.mapOptional("TabWidth", Style.TabWidth);
817     IO.mapOptional("TypenameMacros", Style.TypenameMacros);
818     IO.mapOptional("UseCRLF", Style.UseCRLF);
819     IO.mapOptional("UseTab", Style.UseTab);
820     IO.mapOptional("WhitespaceSensitiveMacros",
821                    Style.WhitespaceSensitiveMacros);
822   }
823 };
824 
825 template <> struct MappingTraits<FormatStyle::BraceWrappingFlags> {
826   static void mapping(IO &IO, FormatStyle::BraceWrappingFlags &Wrapping) {
827     IO.mapOptional("AfterCaseLabel", Wrapping.AfterCaseLabel);
828     IO.mapOptional("AfterClass", Wrapping.AfterClass);
829     IO.mapOptional("AfterControlStatement", Wrapping.AfterControlStatement);
830     IO.mapOptional("AfterEnum", Wrapping.AfterEnum);
831     IO.mapOptional("AfterFunction", Wrapping.AfterFunction);
832     IO.mapOptional("AfterNamespace", Wrapping.AfterNamespace);
833     IO.mapOptional("AfterObjCDeclaration", Wrapping.AfterObjCDeclaration);
834     IO.mapOptional("AfterStruct", Wrapping.AfterStruct);
835     IO.mapOptional("AfterUnion", Wrapping.AfterUnion);
836     IO.mapOptional("AfterExternBlock", Wrapping.AfterExternBlock);
837     IO.mapOptional("BeforeCatch", Wrapping.BeforeCatch);
838     IO.mapOptional("BeforeElse", Wrapping.BeforeElse);
839     IO.mapOptional("BeforeLambdaBody", Wrapping.BeforeLambdaBody);
840     IO.mapOptional("BeforeWhile", Wrapping.BeforeWhile);
841     IO.mapOptional("IndentBraces", Wrapping.IndentBraces);
842     IO.mapOptional("SplitEmptyFunction", Wrapping.SplitEmptyFunction);
843     IO.mapOptional("SplitEmptyRecord", Wrapping.SplitEmptyRecord);
844     IO.mapOptional("SplitEmptyNamespace", Wrapping.SplitEmptyNamespace);
845   }
846 };
847 
848 template <> struct MappingTraits<FormatStyle::RawStringFormat> {
849   static void mapping(IO &IO, FormatStyle::RawStringFormat &Format) {
850     IO.mapOptional("Language", Format.Language);
851     IO.mapOptional("Delimiters", Format.Delimiters);
852     IO.mapOptional("EnclosingFunctions", Format.EnclosingFunctions);
853     IO.mapOptional("CanonicalDelimiter", Format.CanonicalDelimiter);
854     IO.mapOptional("BasedOnStyle", Format.BasedOnStyle);
855   }
856 };
857 
858 template <> struct MappingTraits<FormatStyle::SpacesInLineComment> {
859   static void mapping(IO &IO, FormatStyle::SpacesInLineComment &Space) {
860     // Transform the maximum to signed, to parse "-1" correctly
861     int signedMaximum = static_cast<int>(Space.Maximum);
862     IO.mapOptional("Minimum", Space.Minimum);
863     IO.mapOptional("Maximum", signedMaximum);
864     Space.Maximum = static_cast<unsigned>(signedMaximum);
865 
866     if (Space.Maximum != -1u) {
867       Space.Minimum = std::min(Space.Minimum, Space.Maximum);
868     }
869   }
870 };
871 
872 // Allows to read vector<FormatStyle> while keeping default values.
873 // IO.getContext() should contain a pointer to the FormatStyle structure, that
874 // will be used to get default values for missing keys.
875 // If the first element has no Language specified, it will be treated as the
876 // default one for the following elements.
877 template <> struct DocumentListTraits<std::vector<FormatStyle>> {
878   static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
879     return Seq.size();
880   }
881   static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
882                               size_t Index) {
883     if (Index >= Seq.size()) {
884       assert(Index == Seq.size());
885       FormatStyle Template;
886       if (!Seq.empty() && Seq[0].Language == FormatStyle::LK_None) {
887         Template = Seq[0];
888       } else {
889         Template = *((const FormatStyle *)IO.getContext());
890         Template.Language = FormatStyle::LK_None;
891       }
892       Seq.resize(Index + 1, Template);
893     }
894     return Seq[Index];
895   }
896 };
897 } // namespace yaml
898 } // namespace llvm
899 
900 namespace clang {
901 namespace format {
902 
903 const std::error_category &getParseCategory() {
904   static const ParseErrorCategory C{};
905   return C;
906 }
907 std::error_code make_error_code(ParseError e) {
908   return std::error_code(static_cast<int>(e), getParseCategory());
909 }
910 
911 inline llvm::Error make_string_error(const llvm::Twine &Message) {
912   return llvm::make_error<llvm::StringError>(Message,
913                                              llvm::inconvertibleErrorCode());
914 }
915 
916 const char *ParseErrorCategory::name() const noexcept {
917   return "clang-format.parse_error";
918 }
919 
920 std::string ParseErrorCategory::message(int EV) const {
921   switch (static_cast<ParseError>(EV)) {
922   case ParseError::Success:
923     return "Success";
924   case ParseError::Error:
925     return "Invalid argument";
926   case ParseError::Unsuitable:
927     return "Unsuitable";
928   case ParseError::BinPackTrailingCommaConflict:
929     return "trailing comma insertion cannot be used with bin packing";
930   case ParseError::InvalidQualifierSpecified:
931     return "Invalid qualifier specified in QualifierOrder";
932   case ParseError::DuplicateQualifierSpecified:
933     return "Duplicate qualifier specified in QualfierOrder";
934   case ParseError::MissingQualifierType:
935     return "Missing type in QualfierOrder";
936   case ParseError::MissingQualifierOrder:
937     return "Missing QualfierOrder";
938   }
939   llvm_unreachable("unexpected parse error");
940 }
941 
942 static FormatStyle expandPresets(const FormatStyle &Style) {
943   if (Style.BreakBeforeBraces == FormatStyle::BS_Custom)
944     return Style;
945   FormatStyle Expanded = Style;
946   Expanded.BraceWrapping = {/*AfterCaseLabel=*/false,
947                             /*AfterClass=*/false,
948                             /*AfterControlStatement=*/FormatStyle::BWACS_Never,
949                             /*AfterEnum=*/false,
950                             /*AfterFunction=*/false,
951                             /*AfterNamespace=*/false,
952                             /*AfterObjCDeclaration=*/false,
953                             /*AfterStruct=*/false,
954                             /*AfterUnion=*/false,
955                             /*AfterExternBlock=*/false,
956                             /*BeforeCatch=*/false,
957                             /*BeforeElse=*/false,
958                             /*BeforeLambdaBody=*/false,
959                             /*BeforeWhile=*/false,
960                             /*IndentBraces=*/false,
961                             /*SplitEmptyFunction=*/true,
962                             /*SplitEmptyRecord=*/true,
963                             /*SplitEmptyNamespace=*/true};
964   switch (Style.BreakBeforeBraces) {
965   case FormatStyle::BS_Linux:
966     Expanded.BraceWrapping.AfterClass = true;
967     Expanded.BraceWrapping.AfterFunction = true;
968     Expanded.BraceWrapping.AfterNamespace = true;
969     break;
970   case FormatStyle::BS_Mozilla:
971     Expanded.BraceWrapping.AfterClass = true;
972     Expanded.BraceWrapping.AfterEnum = true;
973     Expanded.BraceWrapping.AfterFunction = true;
974     Expanded.BraceWrapping.AfterStruct = true;
975     Expanded.BraceWrapping.AfterUnion = true;
976     Expanded.BraceWrapping.AfterExternBlock = true;
977     Expanded.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
978     Expanded.BraceWrapping.SplitEmptyFunction = true;
979     Expanded.BraceWrapping.SplitEmptyRecord = false;
980     break;
981   case FormatStyle::BS_Stroustrup:
982     Expanded.BraceWrapping.AfterFunction = true;
983     Expanded.BraceWrapping.BeforeCatch = true;
984     Expanded.BraceWrapping.BeforeElse = true;
985     break;
986   case FormatStyle::BS_Allman:
987     Expanded.BraceWrapping.AfterCaseLabel = true;
988     Expanded.BraceWrapping.AfterClass = true;
989     Expanded.BraceWrapping.AfterControlStatement = FormatStyle::BWACS_Always;
990     Expanded.BraceWrapping.AfterEnum = true;
991     Expanded.BraceWrapping.AfterFunction = true;
992     Expanded.BraceWrapping.AfterNamespace = true;
993     Expanded.BraceWrapping.AfterObjCDeclaration = true;
994     Expanded.BraceWrapping.AfterStruct = true;
995     Expanded.BraceWrapping.AfterUnion = true;
996     Expanded.BraceWrapping.AfterExternBlock = true;
997     Expanded.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
998     Expanded.BraceWrapping.BeforeCatch = true;
999     Expanded.BraceWrapping.BeforeElse = true;
1000     Expanded.BraceWrapping.BeforeLambdaBody = true;
1001     break;
1002   case FormatStyle::BS_Whitesmiths:
1003     Expanded.BraceWrapping.AfterCaseLabel = true;
1004     Expanded.BraceWrapping.AfterClass = true;
1005     Expanded.BraceWrapping.AfterControlStatement = FormatStyle::BWACS_Always;
1006     Expanded.BraceWrapping.AfterEnum = true;
1007     Expanded.BraceWrapping.AfterFunction = true;
1008     Expanded.BraceWrapping.AfterNamespace = true;
1009     Expanded.BraceWrapping.AfterObjCDeclaration = true;
1010     Expanded.BraceWrapping.AfterStruct = true;
1011     Expanded.BraceWrapping.AfterExternBlock = true;
1012     Expanded.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
1013     Expanded.BraceWrapping.BeforeCatch = true;
1014     Expanded.BraceWrapping.BeforeElse = true;
1015     Expanded.BraceWrapping.BeforeLambdaBody = true;
1016     break;
1017   case FormatStyle::BS_GNU:
1018     Expanded.BraceWrapping = {
1019         /*AfterCaseLabel=*/true,
1020         /*AfterClass=*/true,
1021         /*AfterControlStatement=*/FormatStyle::BWACS_Always,
1022         /*AfterEnum=*/true,
1023         /*AfterFunction=*/true,
1024         /*AfterNamespace=*/true,
1025         /*AfterObjCDeclaration=*/true,
1026         /*AfterStruct=*/true,
1027         /*AfterUnion=*/true,
1028         /*AfterExternBlock=*/true,
1029         /*BeforeCatch=*/true,
1030         /*BeforeElse=*/true,
1031         /*BeforeLambdaBody=*/false,
1032         /*BeforeWhile=*/true,
1033         /*IndentBraces=*/true,
1034         /*SplitEmptyFunction=*/true,
1035         /*SplitEmptyRecord=*/true,
1036         /*SplitEmptyNamespace=*/true};
1037     Expanded.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
1038     break;
1039   case FormatStyle::BS_WebKit:
1040     Expanded.BraceWrapping.AfterFunction = true;
1041     break;
1042   default:
1043     break;
1044   }
1045   return Expanded;
1046 }
1047 
1048 FormatStyle getLLVMStyle(FormatStyle::LanguageKind Language) {
1049   FormatStyle LLVMStyle;
1050   LLVMStyle.InheritsParentConfig = false;
1051   LLVMStyle.Language = Language;
1052   LLVMStyle.AccessModifierOffset = -2;
1053   LLVMStyle.AlignEscapedNewlines = FormatStyle::ENAS_Right;
1054   LLVMStyle.AlignAfterOpenBracket = FormatStyle::BAS_Align;
1055   LLVMStyle.AlignArrayOfStructures = FormatStyle::AIAS_None;
1056   LLVMStyle.AlignOperands = FormatStyle::OAS_Align;
1057   LLVMStyle.AlignTrailingComments = true;
1058   LLVMStyle.AlignConsecutiveAssignments = FormatStyle::ACS_None;
1059   LLVMStyle.AlignConsecutiveBitFields = FormatStyle::ACS_None;
1060   LLVMStyle.AlignConsecutiveDeclarations = FormatStyle::ACS_None;
1061   LLVMStyle.AlignConsecutiveMacros = FormatStyle::ACS_None;
1062   LLVMStyle.AllowAllArgumentsOnNextLine = true;
1063   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
1064   LLVMStyle.AllowShortEnumsOnASingleLine = true;
1065   LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
1066   LLVMStyle.AllowShortBlocksOnASingleLine = FormatStyle::SBS_Never;
1067   LLVMStyle.AllowShortCaseLabelsOnASingleLine = false;
1068   LLVMStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1069   LLVMStyle.AllowShortLambdasOnASingleLine = FormatStyle::SLS_All;
1070   LLVMStyle.AllowShortLoopsOnASingleLine = false;
1071   LLVMStyle.AlwaysBreakAfterReturnType = FormatStyle::RTBS_None;
1072   LLVMStyle.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_None;
1073   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
1074   LLVMStyle.AlwaysBreakTemplateDeclarations = FormatStyle::BTDS_MultiLine;
1075   LLVMStyle.AttributeMacros.push_back("__capability");
1076   LLVMStyle.BinPackArguments = true;
1077   LLVMStyle.BinPackParameters = true;
1078   LLVMStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_None;
1079   LLVMStyle.BreakBeforeConceptDeclarations = true;
1080   LLVMStyle.BreakBeforeTernaryOperators = true;
1081   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
1082   LLVMStyle.BraceWrapping = {/*AfterCaseLabel=*/false,
1083                              /*AfterClass=*/false,
1084                              /*AfterControlStatement=*/FormatStyle::BWACS_Never,
1085                              /*AfterEnum=*/false,
1086                              /*AfterFunction=*/false,
1087                              /*AfterNamespace=*/false,
1088                              /*AfterObjCDeclaration=*/false,
1089                              /*AfterStruct=*/false,
1090                              /*AfterUnion=*/false,
1091                              /*AfterExternBlock=*/false,
1092                              /*BeforeCatch=*/false,
1093                              /*BeforeElse=*/false,
1094                              /*BeforeLambdaBody=*/false,
1095                              /*BeforeWhile=*/false,
1096                              /*IndentBraces=*/false,
1097                              /*SplitEmptyFunction=*/true,
1098                              /*SplitEmptyRecord=*/true,
1099                              /*SplitEmptyNamespace=*/true};
1100   LLVMStyle.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
1101   LLVMStyle.BreakAfterJavaFieldAnnotations = false;
1102   LLVMStyle.BreakConstructorInitializers = FormatStyle::BCIS_BeforeColon;
1103   LLVMStyle.BreakInheritanceList = FormatStyle::BILS_BeforeColon;
1104   LLVMStyle.BreakStringLiterals = true;
1105   LLVMStyle.ColumnLimit = 80;
1106   LLVMStyle.CommentPragmas = "^ IWYU pragma:";
1107   LLVMStyle.CompactNamespaces = false;
1108   LLVMStyle.ConstructorInitializerIndentWidth = 4;
1109   LLVMStyle.ContinuationIndentWidth = 4;
1110   LLVMStyle.Cpp11BracedListStyle = true;
1111 
1112   // Off by default Qualifier ordering
1113   LLVMStyle.QualifierAlignment = FormatStyle::QAS_Leave;
1114 
1115   LLVMStyle.DeriveLineEnding = true;
1116   LLVMStyle.DerivePointerAlignment = false;
1117   LLVMStyle.EmptyLineAfterAccessModifier = FormatStyle::ELAAMS_Never;
1118   LLVMStyle.EmptyLineBeforeAccessModifier = FormatStyle::ELBAMS_LogicalBlock;
1119   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
1120   LLVMStyle.PackConstructorInitializers = FormatStyle::PCIS_BinPack;
1121   LLVMStyle.FixNamespaceComments = true;
1122   LLVMStyle.ForEachMacros.push_back("foreach");
1123   LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
1124   LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
1125   LLVMStyle.IfMacros.push_back("KJ_IF_MAYBE");
1126   LLVMStyle.IncludeStyle.IncludeCategories = {
1127       {"^\"(llvm|llvm-c|clang|clang-c)/", 2, 0, false},
1128       {"^(<|\"(gtest|gmock|isl|json)/)", 3, 0, false},
1129       {".*", 1, 0, false}};
1130   LLVMStyle.IncludeStyle.IncludeIsMainRegex = "(Test)?$";
1131   LLVMStyle.IncludeStyle.IncludeBlocks = tooling::IncludeStyle::IBS_Preserve;
1132   LLVMStyle.IndentAccessModifiers = false;
1133   LLVMStyle.IndentCaseLabels = false;
1134   LLVMStyle.IndentCaseBlocks = false;
1135   LLVMStyle.IndentGotoLabels = true;
1136   LLVMStyle.IndentPPDirectives = FormatStyle::PPDIS_None;
1137   LLVMStyle.IndentRequires = false;
1138   LLVMStyle.IndentWrappedFunctionNames = false;
1139   LLVMStyle.IndentWidth = 2;
1140   LLVMStyle.PPIndentWidth = -1;
1141   LLVMStyle.InsertTrailingCommas = FormatStyle::TCS_None;
1142   LLVMStyle.JavaScriptQuotes = FormatStyle::JSQS_Leave;
1143   LLVMStyle.JavaScriptWrapImports = true;
1144   LLVMStyle.TabWidth = 8;
1145   LLVMStyle.LambdaBodyIndentation = FormatStyle::LBI_Signature;
1146   LLVMStyle.MaxEmptyLinesToKeep = 1;
1147   LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
1148   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
1149   LLVMStyle.ObjCBinPackProtocolList = FormatStyle::BPS_Auto;
1150   LLVMStyle.ObjCBlockIndentWidth = 2;
1151   LLVMStyle.ObjCBreakBeforeNestedBlockParam = true;
1152   LLVMStyle.ObjCSpaceAfterProperty = false;
1153   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
1154   LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
1155   LLVMStyle.ReferenceAlignment = FormatStyle::RAS_Pointer;
1156   LLVMStyle.ShortNamespaceLines = 1;
1157   LLVMStyle.SpacesBeforeTrailingComments = 1;
1158   LLVMStyle.Standard = FormatStyle::LS_Latest;
1159   LLVMStyle.UseCRLF = false;
1160   LLVMStyle.UseTab = FormatStyle::UT_Never;
1161   LLVMStyle.ReflowComments = true;
1162   LLVMStyle.SpacesInParentheses = false;
1163   LLVMStyle.SpacesInSquareBrackets = false;
1164   LLVMStyle.SpaceInEmptyBlock = false;
1165   LLVMStyle.SpaceInEmptyParentheses = false;
1166   LLVMStyle.SpacesInContainerLiterals = true;
1167   LLVMStyle.SpacesInCStyleCastParentheses = false;
1168   LLVMStyle.SpacesInLineCommentPrefix = {/*Minimum=*/1, /*Maximum=*/-1u};
1169   LLVMStyle.SpaceAfterCStyleCast = false;
1170   LLVMStyle.SpaceAfterLogicalNot = false;
1171   LLVMStyle.SpaceAfterTemplateKeyword = true;
1172   LLVMStyle.SpaceAroundPointerQualifiers = FormatStyle::SAPQ_Default;
1173   LLVMStyle.SpaceBeforeCaseColon = false;
1174   LLVMStyle.SpaceBeforeCtorInitializerColon = true;
1175   LLVMStyle.SpaceBeforeInheritanceColon = true;
1176   LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
1177   LLVMStyle.SpaceBeforeRangeBasedForLoopColon = true;
1178   LLVMStyle.SpaceBeforeAssignmentOperators = true;
1179   LLVMStyle.SpaceBeforeCpp11BracedList = false;
1180   LLVMStyle.SpaceBeforeSquareBrackets = false;
1181   LLVMStyle.BitFieldColonSpacing = FormatStyle::BFCS_Both;
1182   LLVMStyle.SpacesInAngles = FormatStyle::SIAS_Never;
1183   LLVMStyle.SpacesInConditionalStatement = false;
1184 
1185   LLVMStyle.PenaltyBreakAssignment = prec::Assignment;
1186   LLVMStyle.PenaltyBreakComment = 300;
1187   LLVMStyle.PenaltyBreakFirstLessLess = 120;
1188   LLVMStyle.PenaltyBreakString = 1000;
1189   LLVMStyle.PenaltyExcessCharacter = 1000000;
1190   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
1191   LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
1192   LLVMStyle.PenaltyBreakTemplateDeclaration = prec::Relational;
1193   LLVMStyle.PenaltyIndentedWhitespace = 0;
1194 
1195   LLVMStyle.DisableFormat = false;
1196   LLVMStyle.SortIncludes = FormatStyle::SI_CaseSensitive;
1197   LLVMStyle.SortJavaStaticImport = FormatStyle::SJSIO_Before;
1198   LLVMStyle.SortUsingDeclarations = true;
1199   LLVMStyle.StatementAttributeLikeMacros.push_back("Q_EMIT");
1200   LLVMStyle.StatementMacros.push_back("Q_UNUSED");
1201   LLVMStyle.StatementMacros.push_back("QT_REQUIRE_VERSION");
1202   LLVMStyle.WhitespaceSensitiveMacros.push_back("STRINGIZE");
1203   LLVMStyle.WhitespaceSensitiveMacros.push_back("PP_STRINGIZE");
1204   LLVMStyle.WhitespaceSensitiveMacros.push_back("BOOST_PP_STRINGIZE");
1205   LLVMStyle.WhitespaceSensitiveMacros.push_back("NS_SWIFT_NAME");
1206   LLVMStyle.WhitespaceSensitiveMacros.push_back("CF_SWIFT_NAME");
1207 
1208   // Defaults that differ when not C++.
1209   if (Language == FormatStyle::LK_TableGen) {
1210     LLVMStyle.SpacesInContainerLiterals = false;
1211   }
1212   if (LLVMStyle.isJson()) {
1213     LLVMStyle.ColumnLimit = 0;
1214   }
1215 
1216   return LLVMStyle;
1217 }
1218 
1219 FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
1220   if (Language == FormatStyle::LK_TextProto) {
1221     FormatStyle GoogleStyle = getGoogleStyle(FormatStyle::LK_Proto);
1222     GoogleStyle.Language = FormatStyle::LK_TextProto;
1223 
1224     return GoogleStyle;
1225   }
1226 
1227   FormatStyle GoogleStyle = getLLVMStyle(Language);
1228 
1229   GoogleStyle.AccessModifierOffset = -1;
1230   GoogleStyle.AlignEscapedNewlines = FormatStyle::ENAS_Left;
1231   GoogleStyle.AllowShortIfStatementsOnASingleLine =
1232       FormatStyle::SIS_WithoutElse;
1233   GoogleStyle.AllowShortLoopsOnASingleLine = true;
1234   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
1235   GoogleStyle.AlwaysBreakTemplateDeclarations = FormatStyle::BTDS_Yes;
1236   GoogleStyle.DerivePointerAlignment = true;
1237   GoogleStyle.IncludeStyle.IncludeCategories = {{"^<ext/.*\\.h>", 2, 0, false},
1238                                                 {"^<.*\\.h>", 1, 0, false},
1239                                                 {"^<.*", 2, 0, false},
1240                                                 {".*", 3, 0, false}};
1241   GoogleStyle.IncludeStyle.IncludeIsMainRegex = "([-_](test|unittest))?$";
1242   GoogleStyle.IncludeStyle.IncludeBlocks = tooling::IncludeStyle::IBS_Regroup;
1243   GoogleStyle.IndentCaseLabels = true;
1244   GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
1245   GoogleStyle.ObjCBinPackProtocolList = FormatStyle::BPS_Never;
1246   GoogleStyle.ObjCSpaceAfterProperty = false;
1247   GoogleStyle.ObjCSpaceBeforeProtocolList = true;
1248   GoogleStyle.PackConstructorInitializers = FormatStyle::PCIS_NextLine;
1249   GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
1250   GoogleStyle.RawStringFormats = {
1251       {
1252           FormatStyle::LK_Cpp,
1253           /*Delimiters=*/
1254           {
1255               "cc",
1256               "CC",
1257               "cpp",
1258               "Cpp",
1259               "CPP",
1260               "c++",
1261               "C++",
1262           },
1263           /*EnclosingFunctionNames=*/
1264           {},
1265           /*CanonicalDelimiter=*/"",
1266           /*BasedOnStyle=*/"google",
1267       },
1268       {
1269           FormatStyle::LK_TextProto,
1270           /*Delimiters=*/
1271           {
1272               "pb",
1273               "PB",
1274               "proto",
1275               "PROTO",
1276           },
1277           /*EnclosingFunctionNames=*/
1278           {
1279               "EqualsProto",
1280               "EquivToProto",
1281               "PARSE_PARTIAL_TEXT_PROTO",
1282               "PARSE_TEST_PROTO",
1283               "PARSE_TEXT_PROTO",
1284               "ParseTextOrDie",
1285               "ParseTextProtoOrDie",
1286               "ParseTestProto",
1287               "ParsePartialTestProto",
1288           },
1289           /*CanonicalDelimiter=*/"pb",
1290           /*BasedOnStyle=*/"google",
1291       },
1292   };
1293   GoogleStyle.SpacesBeforeTrailingComments = 2;
1294   GoogleStyle.Standard = FormatStyle::LS_Auto;
1295 
1296   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
1297   GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
1298 
1299   if (Language == FormatStyle::LK_Java) {
1300     GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
1301     GoogleStyle.AlignOperands = FormatStyle::OAS_DontAlign;
1302     GoogleStyle.AlignTrailingComments = false;
1303     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
1304     GoogleStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1305     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
1306     GoogleStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_NonAssignment;
1307     GoogleStyle.ColumnLimit = 100;
1308     GoogleStyle.SpaceAfterCStyleCast = true;
1309     GoogleStyle.SpacesBeforeTrailingComments = 1;
1310   } else if (Language == FormatStyle::LK_JavaScript) {
1311     GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_AlwaysBreak;
1312     GoogleStyle.AlignOperands = FormatStyle::OAS_DontAlign;
1313     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
1314     // TODO: still under discussion whether to switch to SLS_All.
1315     GoogleStyle.AllowShortLambdasOnASingleLine = FormatStyle::SLS_Empty;
1316     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
1317     GoogleStyle.BreakBeforeTernaryOperators = false;
1318     // taze:, triple slash directives (`/// <...`), tslint:, and @see, which is
1319     // commonly followed by overlong URLs.
1320     GoogleStyle.CommentPragmas = "(taze:|^/[ \t]*<|tslint:|@see)";
1321     // TODO: enable once decided, in particular re disabling bin packing.
1322     // https://google.github.io/styleguide/jsguide.html#features-arrays-trailing-comma
1323     // GoogleStyle.InsertTrailingCommas = FormatStyle::TCS_Wrapped;
1324     GoogleStyle.MaxEmptyLinesToKeep = 3;
1325     GoogleStyle.NamespaceIndentation = FormatStyle::NI_All;
1326     GoogleStyle.SpacesInContainerLiterals = false;
1327     GoogleStyle.JavaScriptQuotes = FormatStyle::JSQS_Single;
1328     GoogleStyle.JavaScriptWrapImports = false;
1329   } else if (Language == FormatStyle::LK_Proto) {
1330     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
1331     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
1332     GoogleStyle.SpacesInContainerLiterals = false;
1333     GoogleStyle.Cpp11BracedListStyle = false;
1334     // This affects protocol buffer options specifications and text protos.
1335     // Text protos are currently mostly formatted inside C++ raw string literals
1336     // and often the current breaking behavior of string literals is not
1337     // beneficial there. Investigate turning this on once proper string reflow
1338     // has been implemented.
1339     GoogleStyle.BreakStringLiterals = false;
1340   } else if (Language == FormatStyle::LK_ObjC) {
1341     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
1342     GoogleStyle.ColumnLimit = 100;
1343     // "Regroup" doesn't work well for ObjC yet (main header heuristic,
1344     // relationship between ObjC standard library headers and other heades,
1345     // #imports, etc.)
1346     GoogleStyle.IncludeStyle.IncludeBlocks =
1347         tooling::IncludeStyle::IBS_Preserve;
1348   } else if (Language == FormatStyle::LK_CSharp) {
1349     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
1350     GoogleStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1351     GoogleStyle.BreakStringLiterals = false;
1352     GoogleStyle.ColumnLimit = 100;
1353     GoogleStyle.NamespaceIndentation = FormatStyle::NI_All;
1354   }
1355 
1356   return GoogleStyle;
1357 }
1358 
1359 FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
1360   FormatStyle ChromiumStyle = getGoogleStyle(Language);
1361 
1362   // Disable include reordering across blocks in Chromium code.
1363   // - clang-format tries to detect that foo.h is the "main" header for
1364   //   foo.cc and foo_unittest.cc via IncludeIsMainRegex. However, Chromium
1365   //   uses many other suffices (_win.cc, _mac.mm, _posix.cc, _browsertest.cc,
1366   //   _private.cc, _impl.cc etc) in different permutations
1367   //   (_win_browsertest.cc) so disable this until IncludeIsMainRegex has a
1368   //   better default for Chromium code.
1369   // - The default for .cc and .mm files is different (r357695) for Google style
1370   //   for the same reason. The plan is to unify this again once the main
1371   //   header detection works for Google's ObjC code, but this hasn't happened
1372   //   yet. Since Chromium has some ObjC code, switching Chromium is blocked
1373   //   on that.
1374   // - Finally, "If include reordering is harmful, put things in different
1375   //   blocks to prevent it" has been a recommendation for a long time that
1376   //   people are used to. We'll need a dev education push to change this to
1377   //   "If include reordering is harmful, put things in a different block and
1378   //   _prepend that with a comment_ to prevent it" before changing behavior.
1379   ChromiumStyle.IncludeStyle.IncludeBlocks =
1380       tooling::IncludeStyle::IBS_Preserve;
1381 
1382   if (Language == FormatStyle::LK_Java) {
1383     ChromiumStyle.AllowShortIfStatementsOnASingleLine =
1384         FormatStyle::SIS_WithoutElse;
1385     ChromiumStyle.BreakAfterJavaFieldAnnotations = true;
1386     ChromiumStyle.ContinuationIndentWidth = 8;
1387     ChromiumStyle.IndentWidth = 4;
1388     // See styleguide for import groups:
1389     // https://chromium.googlesource.com/chromium/src/+/master/styleguide/java/java.md#Import-Order
1390     ChromiumStyle.JavaImportGroups = {
1391         "android",
1392         "androidx",
1393         "com",
1394         "dalvik",
1395         "junit",
1396         "org",
1397         "com.google.android.apps.chrome",
1398         "org.chromium",
1399         "java",
1400         "javax",
1401     };
1402     ChromiumStyle.SortIncludes = FormatStyle::SI_CaseSensitive;
1403   } else if (Language == FormatStyle::LK_JavaScript) {
1404     ChromiumStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1405     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
1406   } else {
1407     ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
1408     ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
1409     ChromiumStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1410     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
1411     ChromiumStyle.BinPackParameters = false;
1412     ChromiumStyle.DerivePointerAlignment = false;
1413     if (Language == FormatStyle::LK_ObjC)
1414       ChromiumStyle.ColumnLimit = 80;
1415   }
1416   return ChromiumStyle;
1417 }
1418 
1419 FormatStyle getMozillaStyle() {
1420   FormatStyle MozillaStyle = getLLVMStyle();
1421   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
1422   MozillaStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
1423   MozillaStyle.AlwaysBreakAfterReturnType = FormatStyle::RTBS_TopLevel;
1424   MozillaStyle.AlwaysBreakAfterDefinitionReturnType =
1425       FormatStyle::DRTBS_TopLevel;
1426   MozillaStyle.AlwaysBreakTemplateDeclarations = FormatStyle::BTDS_Yes;
1427   MozillaStyle.BinPackParameters = false;
1428   MozillaStyle.BinPackArguments = false;
1429   MozillaStyle.BreakBeforeBraces = FormatStyle::BS_Mozilla;
1430   MozillaStyle.BreakConstructorInitializers = FormatStyle::BCIS_BeforeComma;
1431   MozillaStyle.BreakInheritanceList = FormatStyle::BILS_BeforeComma;
1432   MozillaStyle.ConstructorInitializerIndentWidth = 2;
1433   MozillaStyle.ContinuationIndentWidth = 2;
1434   MozillaStyle.Cpp11BracedListStyle = false;
1435   MozillaStyle.FixNamespaceComments = false;
1436   MozillaStyle.IndentCaseLabels = true;
1437   MozillaStyle.ObjCSpaceAfterProperty = true;
1438   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
1439   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
1440   MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
1441   MozillaStyle.SpaceAfterTemplateKeyword = false;
1442   return MozillaStyle;
1443 }
1444 
1445 FormatStyle getWebKitStyle() {
1446   FormatStyle Style = getLLVMStyle();
1447   Style.AccessModifierOffset = -4;
1448   Style.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
1449   Style.AlignOperands = FormatStyle::OAS_DontAlign;
1450   Style.AlignTrailingComments = false;
1451   Style.AllowShortBlocksOnASingleLine = FormatStyle::SBS_Empty;
1452   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
1453   Style.BreakBeforeBraces = FormatStyle::BS_WebKit;
1454   Style.BreakConstructorInitializers = FormatStyle::BCIS_BeforeComma;
1455   Style.Cpp11BracedListStyle = false;
1456   Style.ColumnLimit = 0;
1457   Style.FixNamespaceComments = false;
1458   Style.IndentWidth = 4;
1459   Style.NamespaceIndentation = FormatStyle::NI_Inner;
1460   Style.ObjCBlockIndentWidth = 4;
1461   Style.ObjCSpaceAfterProperty = true;
1462   Style.PointerAlignment = FormatStyle::PAS_Left;
1463   Style.SpaceBeforeCpp11BracedList = true;
1464   Style.SpaceInEmptyBlock = true;
1465   return Style;
1466 }
1467 
1468 FormatStyle getGNUStyle() {
1469   FormatStyle Style = getLLVMStyle();
1470   Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_All;
1471   Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
1472   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
1473   Style.BreakBeforeBraces = FormatStyle::BS_GNU;
1474   Style.BreakBeforeTernaryOperators = true;
1475   Style.Cpp11BracedListStyle = false;
1476   Style.ColumnLimit = 79;
1477   Style.FixNamespaceComments = false;
1478   Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
1479   Style.Standard = FormatStyle::LS_Cpp03;
1480   return Style;
1481 }
1482 
1483 FormatStyle getMicrosoftStyle(FormatStyle::LanguageKind Language) {
1484   FormatStyle Style = getLLVMStyle(Language);
1485   Style.ColumnLimit = 120;
1486   Style.TabWidth = 4;
1487   Style.IndentWidth = 4;
1488   Style.UseTab = FormatStyle::UT_Never;
1489   Style.BreakBeforeBraces = FormatStyle::BS_Custom;
1490   Style.BraceWrapping.AfterClass = true;
1491   Style.BraceWrapping.AfterControlStatement = FormatStyle::BWACS_Always;
1492   Style.BraceWrapping.AfterEnum = true;
1493   Style.BraceWrapping.AfterFunction = true;
1494   Style.BraceWrapping.AfterNamespace = true;
1495   Style.BraceWrapping.AfterObjCDeclaration = true;
1496   Style.BraceWrapping.AfterStruct = true;
1497   Style.BraceWrapping.AfterExternBlock = true;
1498   Style.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
1499   Style.BraceWrapping.BeforeCatch = true;
1500   Style.BraceWrapping.BeforeElse = true;
1501   Style.BraceWrapping.BeforeWhile = false;
1502   Style.PenaltyReturnTypeOnItsOwnLine = 1000;
1503   Style.AllowShortEnumsOnASingleLine = false;
1504   Style.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
1505   Style.AllowShortCaseLabelsOnASingleLine = false;
1506   Style.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1507   Style.AllowShortLoopsOnASingleLine = false;
1508   Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_None;
1509   Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_None;
1510   return Style;
1511 }
1512 
1513 FormatStyle getNoStyle() {
1514   FormatStyle NoStyle = getLLVMStyle();
1515   NoStyle.DisableFormat = true;
1516   NoStyle.SortIncludes = FormatStyle::SI_Never;
1517   NoStyle.SortUsingDeclarations = false;
1518   return NoStyle;
1519 }
1520 
1521 bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
1522                         FormatStyle *Style) {
1523   if (Name.equals_insensitive("llvm")) {
1524     *Style = getLLVMStyle(Language);
1525   } else if (Name.equals_insensitive("chromium")) {
1526     *Style = getChromiumStyle(Language);
1527   } else if (Name.equals_insensitive("mozilla")) {
1528     *Style = getMozillaStyle();
1529   } else if (Name.equals_insensitive("google")) {
1530     *Style = getGoogleStyle(Language);
1531   } else if (Name.equals_insensitive("webkit")) {
1532     *Style = getWebKitStyle();
1533   } else if (Name.equals_insensitive("gnu")) {
1534     *Style = getGNUStyle();
1535   } else if (Name.equals_insensitive("microsoft")) {
1536     *Style = getMicrosoftStyle(Language);
1537   } else if (Name.equals_insensitive("none")) {
1538     *Style = getNoStyle();
1539   } else if (Name.equals_insensitive("inheritparentconfig")) {
1540     Style->InheritsParentConfig = true;
1541   } else {
1542     return false;
1543   }
1544 
1545   Style->Language = Language;
1546   return true;
1547 }
1548 
1549 ParseError validateQualifierOrder(FormatStyle *Style) {
1550   // If its empty then it means don't do anything.
1551   if (Style->QualifierOrder.empty())
1552     return ParseError::MissingQualifierOrder;
1553 
1554   // Ensure the list contains only currently valid qualifiers.
1555   for (const auto &Qualifier : Style->QualifierOrder) {
1556     if (Qualifier == "type")
1557       continue;
1558     auto token =
1559         LeftRightQualifierAlignmentFixer::getTokenFromQualifier(Qualifier);
1560     if (token == tok::identifier)
1561       return ParseError::InvalidQualifierSpecified;
1562   }
1563   // Ensure the list is unqiue (no duplicates).
1564   std::set<std::string> UniqueQualifiers(Style->QualifierOrder.begin(),
1565                                          Style->QualifierOrder.end());
1566   if (Style->QualifierOrder.size() != UniqueQualifiers.size()) {
1567     LLVM_DEBUG(llvm::dbgs()
1568                << "Duplicate Qualifiers " << Style->QualifierOrder.size()
1569                << " vs " << UniqueQualifiers.size() << "\n");
1570     return ParseError::DuplicateQualifierSpecified;
1571   }
1572 
1573   auto type = std::find(Style->QualifierOrder.begin(),
1574                         Style->QualifierOrder.end(), "type");
1575   if (type == Style->QualifierOrder.end())
1576     return ParseError::MissingQualifierType;
1577   return ParseError::Success;
1578 }
1579 
1580 std::error_code parseConfiguration(llvm::MemoryBufferRef Config,
1581                                    FormatStyle *Style, bool AllowUnknownOptions,
1582                                    llvm::SourceMgr::DiagHandlerTy DiagHandler,
1583                                    void *DiagHandlerCtxt) {
1584   assert(Style);
1585   FormatStyle::LanguageKind Language = Style->Language;
1586   assert(Language != FormatStyle::LK_None);
1587   if (Config.getBuffer().trim().empty())
1588     return make_error_code(ParseError::Error);
1589   Style->StyleSet.Clear();
1590   std::vector<FormatStyle> Styles;
1591   llvm::yaml::Input Input(Config, /*Ctxt=*/nullptr, DiagHandler,
1592                           DiagHandlerCtxt);
1593   // DocumentListTraits<vector<FormatStyle>> uses the context to get default
1594   // values for the fields, keys for which are missing from the configuration.
1595   // Mapping also uses the context to get the language to find the correct
1596   // base style.
1597   Input.setContext(Style);
1598   Input.setAllowUnknownKeys(AllowUnknownOptions);
1599   Input >> Styles;
1600   if (Input.error())
1601     return Input.error();
1602 
1603   for (unsigned i = 0; i < Styles.size(); ++i) {
1604     // Ensures that only the first configuration can skip the Language option.
1605     if (Styles[i].Language == FormatStyle::LK_None && i != 0)
1606       return make_error_code(ParseError::Error);
1607     // Ensure that each language is configured at most once.
1608     for (unsigned j = 0; j < i; ++j) {
1609       if (Styles[i].Language == Styles[j].Language) {
1610         LLVM_DEBUG(llvm::dbgs()
1611                    << "Duplicate languages in the config file on positions "
1612                    << j << " and " << i << "\n");
1613         return make_error_code(ParseError::Error);
1614       }
1615     }
1616   }
1617   // Look for a suitable configuration starting from the end, so we can
1618   // find the configuration for the specific language first, and the default
1619   // configuration (which can only be at slot 0) after it.
1620   FormatStyle::FormatStyleSet StyleSet;
1621   bool LanguageFound = false;
1622   for (int i = Styles.size() - 1; i >= 0; --i) {
1623     if (Styles[i].Language != FormatStyle::LK_None)
1624       StyleSet.Add(Styles[i]);
1625     if (Styles[i].Language == Language)
1626       LanguageFound = true;
1627   }
1628   if (!LanguageFound) {
1629     if (Styles.empty() || Styles[0].Language != FormatStyle::LK_None)
1630       return make_error_code(ParseError::Unsuitable);
1631     FormatStyle DefaultStyle = Styles[0];
1632     DefaultStyle.Language = Language;
1633     StyleSet.Add(std::move(DefaultStyle));
1634   }
1635   *Style = *StyleSet.Get(Language);
1636   if (Style->InsertTrailingCommas != FormatStyle::TCS_None &&
1637       Style->BinPackArguments) {
1638     // See comment on FormatStyle::TSC_Wrapped.
1639     return make_error_code(ParseError::BinPackTrailingCommaConflict);
1640   }
1641   if (Style->QualifierAlignment != FormatStyle::QAS_Leave)
1642     return make_error_code(validateQualifierOrder(Style));
1643   return make_error_code(ParseError::Success);
1644 }
1645 
1646 std::string configurationAsText(const FormatStyle &Style) {
1647   std::string Text;
1648   llvm::raw_string_ostream Stream(Text);
1649   llvm::yaml::Output Output(Stream);
1650   // We use the same mapping method for input and output, so we need a non-const
1651   // reference here.
1652   FormatStyle NonConstStyle = expandPresets(Style);
1653   Output << NonConstStyle;
1654   return Stream.str();
1655 }
1656 
1657 llvm::Optional<FormatStyle>
1658 FormatStyle::FormatStyleSet::Get(FormatStyle::LanguageKind Language) const {
1659   if (!Styles)
1660     return None;
1661   auto It = Styles->find(Language);
1662   if (It == Styles->end())
1663     return None;
1664   FormatStyle Style = It->second;
1665   Style.StyleSet = *this;
1666   return Style;
1667 }
1668 
1669 void FormatStyle::FormatStyleSet::Add(FormatStyle Style) {
1670   assert(Style.Language != LK_None &&
1671          "Cannot add a style for LK_None to a StyleSet");
1672   assert(
1673       !Style.StyleSet.Styles &&
1674       "Cannot add a style associated with an existing StyleSet to a StyleSet");
1675   if (!Styles)
1676     Styles = std::make_shared<MapType>();
1677   (*Styles)[Style.Language] = std::move(Style);
1678 }
1679 
1680 void FormatStyle::FormatStyleSet::Clear() { Styles.reset(); }
1681 
1682 llvm::Optional<FormatStyle>
1683 FormatStyle::GetLanguageStyle(FormatStyle::LanguageKind Language) const {
1684   return StyleSet.Get(Language);
1685 }
1686 
1687 namespace {
1688 
1689 class JavaScriptRequoter : public TokenAnalyzer {
1690 public:
1691   JavaScriptRequoter(const Environment &Env, const FormatStyle &Style)
1692       : TokenAnalyzer(Env, Style) {}
1693 
1694   std::pair<tooling::Replacements, unsigned>
1695   analyze(TokenAnnotator &Annotator,
1696           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1697           FormatTokenLexer &Tokens) override {
1698     AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1699     tooling::Replacements Result;
1700     requoteJSStringLiteral(AnnotatedLines, Result);
1701     return {Result, 0};
1702   }
1703 
1704 private:
1705   // Replaces double/single-quoted string literal as appropriate, re-escaping
1706   // the contents in the process.
1707   void requoteJSStringLiteral(SmallVectorImpl<AnnotatedLine *> &Lines,
1708                               tooling::Replacements &Result) {
1709     for (AnnotatedLine *Line : Lines) {
1710       requoteJSStringLiteral(Line->Children, Result);
1711       if (!Line->Affected)
1712         continue;
1713       for (FormatToken *FormatTok = Line->First; FormatTok;
1714            FormatTok = FormatTok->Next) {
1715         StringRef Input = FormatTok->TokenText;
1716         if (FormatTok->Finalized || !FormatTok->isStringLiteral() ||
1717             // NB: testing for not starting with a double quote to avoid
1718             // breaking `template strings`.
1719             (Style.JavaScriptQuotes == FormatStyle::JSQS_Single &&
1720              !Input.startswith("\"")) ||
1721             (Style.JavaScriptQuotes == FormatStyle::JSQS_Double &&
1722              !Input.startswith("\'")))
1723           continue;
1724 
1725         // Change start and end quote.
1726         bool IsSingle = Style.JavaScriptQuotes == FormatStyle::JSQS_Single;
1727         SourceLocation Start = FormatTok->Tok.getLocation();
1728         auto Replace = [&](SourceLocation Start, unsigned Length,
1729                            StringRef ReplacementText) {
1730           auto Err = Result.add(tooling::Replacement(
1731               Env.getSourceManager(), Start, Length, ReplacementText));
1732           // FIXME: handle error. For now, print error message and skip the
1733           // replacement for release version.
1734           if (Err) {
1735             llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1736             assert(false);
1737           }
1738         };
1739         Replace(Start, 1, IsSingle ? "'" : "\"");
1740         Replace(FormatTok->Tok.getEndLoc().getLocWithOffset(-1), 1,
1741                 IsSingle ? "'" : "\"");
1742 
1743         // Escape internal quotes.
1744         bool Escaped = false;
1745         for (size_t i = 1; i < Input.size() - 1; i++) {
1746           switch (Input[i]) {
1747           case '\\':
1748             if (!Escaped && i + 1 < Input.size() &&
1749                 ((IsSingle && Input[i + 1] == '"') ||
1750                  (!IsSingle && Input[i + 1] == '\''))) {
1751               // Remove this \, it's escaping a " or ' that no longer needs
1752               // escaping
1753               Replace(Start.getLocWithOffset(i), 1, "");
1754               continue;
1755             }
1756             Escaped = !Escaped;
1757             break;
1758           case '\"':
1759           case '\'':
1760             if (!Escaped && IsSingle == (Input[i] == '\'')) {
1761               // Escape the quote.
1762               Replace(Start.getLocWithOffset(i), 0, "\\");
1763             }
1764             Escaped = false;
1765             break;
1766           default:
1767             Escaped = false;
1768             break;
1769           }
1770         }
1771       }
1772     }
1773   }
1774 };
1775 
1776 class Formatter : public TokenAnalyzer {
1777 public:
1778   Formatter(const Environment &Env, const FormatStyle &Style,
1779             FormattingAttemptStatus *Status)
1780       : TokenAnalyzer(Env, Style), Status(Status) {}
1781 
1782   std::pair<tooling::Replacements, unsigned>
1783   analyze(TokenAnnotator &Annotator,
1784           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1785           FormatTokenLexer &Tokens) override {
1786     tooling::Replacements Result;
1787     deriveLocalStyle(AnnotatedLines);
1788     AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1789     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1790       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1791     }
1792     Annotator.setCommentLineLevels(AnnotatedLines);
1793 
1794     WhitespaceManager Whitespaces(
1795         Env.getSourceManager(), Style,
1796         Style.DeriveLineEnding
1797             ? inputUsesCRLF(
1798                   Env.getSourceManager().getBufferData(Env.getFileID()),
1799                   Style.UseCRLF)
1800             : Style.UseCRLF);
1801     ContinuationIndenter Indenter(Style, Tokens.getKeywords(),
1802                                   Env.getSourceManager(), Whitespaces, Encoding,
1803                                   BinPackInconclusiveFunctions);
1804     unsigned Penalty =
1805         UnwrappedLineFormatter(&Indenter, &Whitespaces, Style,
1806                                Tokens.getKeywords(), Env.getSourceManager(),
1807                                Status)
1808             .format(AnnotatedLines, /*DryRun=*/false,
1809                     /*AdditionalIndent=*/0,
1810                     /*FixBadIndentation=*/false,
1811                     /*FirstStartColumn=*/Env.getFirstStartColumn(),
1812                     /*NextStartColumn=*/Env.getNextStartColumn(),
1813                     /*LastStartColumn=*/Env.getLastStartColumn());
1814     for (const auto &R : Whitespaces.generateReplacements())
1815       if (Result.add(R))
1816         return std::make_pair(Result, 0);
1817     return std::make_pair(Result, Penalty);
1818   }
1819 
1820 private:
1821   static bool inputUsesCRLF(StringRef Text, bool DefaultToCRLF) {
1822     size_t LF = Text.count('\n');
1823     size_t CR = Text.count('\r') * 2;
1824     return LF == CR ? DefaultToCRLF : CR > LF;
1825   }
1826 
1827   bool
1828   hasCpp03IncompatibleFormat(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1829     for (const AnnotatedLine *Line : Lines) {
1830       if (hasCpp03IncompatibleFormat(Line->Children))
1831         return true;
1832       for (FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next) {
1833         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
1834           if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
1835             return true;
1836           if (Tok->is(TT_TemplateCloser) &&
1837               Tok->Previous->is(TT_TemplateCloser))
1838             return true;
1839         }
1840       }
1841     }
1842     return false;
1843   }
1844 
1845   int countVariableAlignments(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1846     int AlignmentDiff = 0;
1847     for (const AnnotatedLine *Line : Lines) {
1848       AlignmentDiff += countVariableAlignments(Line->Children);
1849       for (FormatToken *Tok = Line->First; Tok && Tok->Next; Tok = Tok->Next) {
1850         if (!Tok->is(TT_PointerOrReference))
1851           continue;
1852         bool SpaceBefore =
1853             Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1854         bool SpaceAfter = Tok->Next->WhitespaceRange.getBegin() !=
1855                           Tok->Next->WhitespaceRange.getEnd();
1856         if (SpaceBefore && !SpaceAfter)
1857           ++AlignmentDiff;
1858         if (!SpaceBefore && SpaceAfter)
1859           --AlignmentDiff;
1860       }
1861     }
1862     return AlignmentDiff;
1863   }
1864 
1865   void
1866   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1867     bool HasBinPackedFunction = false;
1868     bool HasOnePerLineFunction = false;
1869     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1870       if (!AnnotatedLines[i]->First->Next)
1871         continue;
1872       FormatToken *Tok = AnnotatedLines[i]->First->Next;
1873       while (Tok->Next) {
1874         if (Tok->is(PPK_BinPacked))
1875           HasBinPackedFunction = true;
1876         if (Tok->is(PPK_OnePerLine))
1877           HasOnePerLineFunction = true;
1878 
1879         Tok = Tok->Next;
1880       }
1881     }
1882     if (Style.DerivePointerAlignment) {
1883       Style.PointerAlignment = countVariableAlignments(AnnotatedLines) <= 0
1884                                    ? FormatStyle::PAS_Left
1885                                    : FormatStyle::PAS_Right;
1886       Style.ReferenceAlignment = FormatStyle::RAS_Pointer;
1887     }
1888     if (Style.Standard == FormatStyle::LS_Auto)
1889       Style.Standard = hasCpp03IncompatibleFormat(AnnotatedLines)
1890                            ? FormatStyle::LS_Latest
1891                            : FormatStyle::LS_Cpp03;
1892     BinPackInconclusiveFunctions =
1893         HasBinPackedFunction || !HasOnePerLineFunction;
1894   }
1895 
1896   bool BinPackInconclusiveFunctions;
1897   FormattingAttemptStatus *Status;
1898 };
1899 
1900 /// TrailingCommaInserter inserts trailing commas into container literals.
1901 /// E.g.:
1902 ///     const x = [
1903 ///       1,
1904 ///     ];
1905 /// TrailingCommaInserter runs after formatting. To avoid causing a required
1906 /// reformatting (and thus reflow), it never inserts a comma that'd exceed the
1907 /// ColumnLimit.
1908 ///
1909 /// Because trailing commas disable binpacking of arrays, TrailingCommaInserter
1910 /// is conceptually incompatible with bin packing.
1911 class TrailingCommaInserter : public TokenAnalyzer {
1912 public:
1913   TrailingCommaInserter(const Environment &Env, const FormatStyle &Style)
1914       : TokenAnalyzer(Env, Style) {}
1915 
1916   std::pair<tooling::Replacements, unsigned>
1917   analyze(TokenAnnotator &Annotator,
1918           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1919           FormatTokenLexer &Tokens) override {
1920     AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1921     tooling::Replacements Result;
1922     insertTrailingCommas(AnnotatedLines, Result);
1923     return {Result, 0};
1924   }
1925 
1926 private:
1927   /// Inserts trailing commas in [] and {} initializers if they wrap over
1928   /// multiple lines.
1929   void insertTrailingCommas(SmallVectorImpl<AnnotatedLine *> &Lines,
1930                             tooling::Replacements &Result) {
1931     for (AnnotatedLine *Line : Lines) {
1932       insertTrailingCommas(Line->Children, Result);
1933       if (!Line->Affected)
1934         continue;
1935       for (FormatToken *FormatTok = Line->First; FormatTok;
1936            FormatTok = FormatTok->Next) {
1937         if (FormatTok->NewlinesBefore == 0)
1938           continue;
1939         FormatToken *Matching = FormatTok->MatchingParen;
1940         if (!Matching || !FormatTok->getPreviousNonComment())
1941           continue;
1942         if (!(FormatTok->is(tok::r_square) &&
1943               Matching->is(TT_ArrayInitializerLSquare)) &&
1944             !(FormatTok->is(tok::r_brace) && Matching->is(TT_DictLiteral)))
1945           continue;
1946         FormatToken *Prev = FormatTok->getPreviousNonComment();
1947         if (Prev->is(tok::comma) || Prev->is(tok::semi))
1948           continue;
1949         // getEndLoc is not reliably set during re-lexing, use text length
1950         // instead.
1951         SourceLocation Start =
1952             Prev->Tok.getLocation().getLocWithOffset(Prev->TokenText.size());
1953         // If inserting a comma would push the code over the column limit, skip
1954         // this location - it'd introduce an unstable formatting due to the
1955         // required reflow.
1956         unsigned ColumnNumber =
1957             Env.getSourceManager().getSpellingColumnNumber(Start);
1958         if (ColumnNumber > Style.ColumnLimit)
1959           continue;
1960         // Comma insertions cannot conflict with each other, and this pass has a
1961         // clean set of Replacements, so the operation below cannot fail.
1962         cantFail(Result.add(
1963             tooling::Replacement(Env.getSourceManager(), Start, 0, ",")));
1964       }
1965     }
1966   }
1967 };
1968 
1969 // This class clean up the erroneous/redundant code around the given ranges in
1970 // file.
1971 class Cleaner : public TokenAnalyzer {
1972 public:
1973   Cleaner(const Environment &Env, const FormatStyle &Style)
1974       : TokenAnalyzer(Env, Style),
1975         DeletedTokens(FormatTokenLess(Env.getSourceManager())) {}
1976 
1977   // FIXME: eliminate unused parameters.
1978   std::pair<tooling::Replacements, unsigned>
1979   analyze(TokenAnnotator &Annotator,
1980           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1981           FormatTokenLexer &Tokens) override {
1982     // FIXME: in the current implementation the granularity of affected range
1983     // is an annotated line. However, this is not sufficient. Furthermore,
1984     // redundant code introduced by replacements does not necessarily
1985     // intercept with ranges of replacements that result in the redundancy.
1986     // To determine if some redundant code is actually introduced by
1987     // replacements(e.g. deletions), we need to come up with a more
1988     // sophisticated way of computing affected ranges.
1989     AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1990 
1991     checkEmptyNamespace(AnnotatedLines);
1992 
1993     for (auto *Line : AnnotatedLines)
1994       cleanupLine(Line);
1995 
1996     return {generateFixes(), 0};
1997   }
1998 
1999 private:
2000   void cleanupLine(AnnotatedLine *Line) {
2001     for (auto *Child : Line->Children) {
2002       cleanupLine(Child);
2003     }
2004 
2005     if (Line->Affected) {
2006       cleanupRight(Line->First, tok::comma, tok::comma);
2007       cleanupRight(Line->First, TT_CtorInitializerColon, tok::comma);
2008       cleanupRight(Line->First, tok::l_paren, tok::comma);
2009       cleanupLeft(Line->First, tok::comma, tok::r_paren);
2010       cleanupLeft(Line->First, TT_CtorInitializerComma, tok::l_brace);
2011       cleanupLeft(Line->First, TT_CtorInitializerColon, tok::l_brace);
2012       cleanupLeft(Line->First, TT_CtorInitializerColon, tok::equal);
2013     }
2014   }
2015 
2016   bool containsOnlyComments(const AnnotatedLine &Line) {
2017     for (FormatToken *Tok = Line.First; Tok != nullptr; Tok = Tok->Next) {
2018       if (Tok->isNot(tok::comment))
2019         return false;
2020     }
2021     return true;
2022   }
2023 
2024   // Iterate through all lines and remove any empty (nested) namespaces.
2025   void checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
2026     std::set<unsigned> DeletedLines;
2027     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
2028       auto &Line = *AnnotatedLines[i];
2029       if (Line.startsWithNamespace()) {
2030         checkEmptyNamespace(AnnotatedLines, i, i, DeletedLines);
2031       }
2032     }
2033 
2034     for (auto Line : DeletedLines) {
2035       FormatToken *Tok = AnnotatedLines[Line]->First;
2036       while (Tok) {
2037         deleteToken(Tok);
2038         Tok = Tok->Next;
2039       }
2040     }
2041   }
2042 
2043   // The function checks if the namespace, which starts from \p CurrentLine, and
2044   // its nested namespaces are empty and delete them if they are empty. It also
2045   // sets \p NewLine to the last line checked.
2046   // Returns true if the current namespace is empty.
2047   bool checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
2048                            unsigned CurrentLine, unsigned &NewLine,
2049                            std::set<unsigned> &DeletedLines) {
2050     unsigned InitLine = CurrentLine, End = AnnotatedLines.size();
2051     if (Style.BraceWrapping.AfterNamespace) {
2052       // If the left brace is in a new line, we should consume it first so that
2053       // it does not make the namespace non-empty.
2054       // FIXME: error handling if there is no left brace.
2055       if (!AnnotatedLines[++CurrentLine]->startsWith(tok::l_brace)) {
2056         NewLine = CurrentLine;
2057         return false;
2058       }
2059     } else if (!AnnotatedLines[CurrentLine]->endsWith(tok::l_brace)) {
2060       return false;
2061     }
2062     while (++CurrentLine < End) {
2063       if (AnnotatedLines[CurrentLine]->startsWith(tok::r_brace))
2064         break;
2065 
2066       if (AnnotatedLines[CurrentLine]->startsWithNamespace()) {
2067         if (!checkEmptyNamespace(AnnotatedLines, CurrentLine, NewLine,
2068                                  DeletedLines))
2069           return false;
2070         CurrentLine = NewLine;
2071         continue;
2072       }
2073 
2074       if (containsOnlyComments(*AnnotatedLines[CurrentLine]))
2075         continue;
2076 
2077       // If there is anything other than comments or nested namespaces in the
2078       // current namespace, the namespace cannot be empty.
2079       NewLine = CurrentLine;
2080       return false;
2081     }
2082 
2083     NewLine = CurrentLine;
2084     if (CurrentLine >= End)
2085       return false;
2086 
2087     // Check if the empty namespace is actually affected by changed ranges.
2088     if (!AffectedRangeMgr.affectsCharSourceRange(CharSourceRange::getCharRange(
2089             AnnotatedLines[InitLine]->First->Tok.getLocation(),
2090             AnnotatedLines[CurrentLine]->Last->Tok.getEndLoc())))
2091       return false;
2092 
2093     for (unsigned i = InitLine; i <= CurrentLine; ++i) {
2094       DeletedLines.insert(i);
2095     }
2096 
2097     return true;
2098   }
2099 
2100   // Checks pairs {start, start->next},..., {end->previous, end} and deletes one
2101   // of the token in the pair if the left token has \p LK token kind and the
2102   // right token has \p RK token kind. If \p DeleteLeft is true, the left token
2103   // is deleted on match; otherwise, the right token is deleted.
2104   template <typename LeftKind, typename RightKind>
2105   void cleanupPair(FormatToken *Start, LeftKind LK, RightKind RK,
2106                    bool DeleteLeft) {
2107     auto NextNotDeleted = [this](const FormatToken &Tok) -> FormatToken * {
2108       for (auto *Res = Tok.Next; Res; Res = Res->Next)
2109         if (!Res->is(tok::comment) &&
2110             DeletedTokens.find(Res) == DeletedTokens.end())
2111           return Res;
2112       return nullptr;
2113     };
2114     for (auto *Left = Start; Left;) {
2115       auto *Right = NextNotDeleted(*Left);
2116       if (!Right)
2117         break;
2118       if (Left->is(LK) && Right->is(RK)) {
2119         deleteToken(DeleteLeft ? Left : Right);
2120         for (auto *Tok = Left->Next; Tok && Tok != Right; Tok = Tok->Next)
2121           deleteToken(Tok);
2122         // If the right token is deleted, we should keep the left token
2123         // unchanged and pair it with the new right token.
2124         if (!DeleteLeft)
2125           continue;
2126       }
2127       Left = Right;
2128     }
2129   }
2130 
2131   template <typename LeftKind, typename RightKind>
2132   void cleanupLeft(FormatToken *Start, LeftKind LK, RightKind RK) {
2133     cleanupPair(Start, LK, RK, /*DeleteLeft=*/true);
2134   }
2135 
2136   template <typename LeftKind, typename RightKind>
2137   void cleanupRight(FormatToken *Start, LeftKind LK, RightKind RK) {
2138     cleanupPair(Start, LK, RK, /*DeleteLeft=*/false);
2139   }
2140 
2141   // Delete the given token.
2142   inline void deleteToken(FormatToken *Tok) {
2143     if (Tok)
2144       DeletedTokens.insert(Tok);
2145   }
2146 
2147   tooling::Replacements generateFixes() {
2148     tooling::Replacements Fixes;
2149     std::vector<FormatToken *> Tokens;
2150     std::copy(DeletedTokens.begin(), DeletedTokens.end(),
2151               std::back_inserter(Tokens));
2152 
2153     // Merge multiple continuous token deletions into one big deletion so that
2154     // the number of replacements can be reduced. This makes computing affected
2155     // ranges more efficient when we run reformat on the changed code.
2156     unsigned Idx = 0;
2157     while (Idx < Tokens.size()) {
2158       unsigned St = Idx, End = Idx;
2159       while ((End + 1) < Tokens.size() &&
2160              Tokens[End]->Next == Tokens[End + 1]) {
2161         End++;
2162       }
2163       auto SR = CharSourceRange::getCharRange(Tokens[St]->Tok.getLocation(),
2164                                               Tokens[End]->Tok.getEndLoc());
2165       auto Err =
2166           Fixes.add(tooling::Replacement(Env.getSourceManager(), SR, ""));
2167       // FIXME: better error handling. for now just print error message and skip
2168       // for the release version.
2169       if (Err) {
2170         llvm::errs() << llvm::toString(std::move(Err)) << "\n";
2171         assert(false && "Fixes must not conflict!");
2172       }
2173       Idx = End + 1;
2174     }
2175 
2176     return Fixes;
2177   }
2178 
2179   // Class for less-than inequality comparason for the set `RedundantTokens`.
2180   // We store tokens in the order they appear in the translation unit so that
2181   // we do not need to sort them in `generateFixes()`.
2182   struct FormatTokenLess {
2183     FormatTokenLess(const SourceManager &SM) : SM(SM) {}
2184 
2185     bool operator()(const FormatToken *LHS, const FormatToken *RHS) const {
2186       return SM.isBeforeInTranslationUnit(LHS->Tok.getLocation(),
2187                                           RHS->Tok.getLocation());
2188     }
2189     const SourceManager &SM;
2190   };
2191 
2192   // Tokens to be deleted.
2193   std::set<FormatToken *, FormatTokenLess> DeletedTokens;
2194 };
2195 
2196 class ObjCHeaderStyleGuesser : public TokenAnalyzer {
2197 public:
2198   ObjCHeaderStyleGuesser(const Environment &Env, const FormatStyle &Style)
2199       : TokenAnalyzer(Env, Style), IsObjC(false) {}
2200 
2201   std::pair<tooling::Replacements, unsigned>
2202   analyze(TokenAnnotator &Annotator,
2203           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
2204           FormatTokenLexer &Tokens) override {
2205     assert(Style.Language == FormatStyle::LK_Cpp);
2206     IsObjC = guessIsObjC(Env.getSourceManager(), AnnotatedLines,
2207                          Tokens.getKeywords());
2208     tooling::Replacements Result;
2209     return {Result, 0};
2210   }
2211 
2212   bool isObjC() { return IsObjC; }
2213 
2214 private:
2215   static bool
2216   guessIsObjC(const SourceManager &SourceManager,
2217               const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
2218               const AdditionalKeywords &Keywords) {
2219     // Keep this array sorted, since we are binary searching over it.
2220     static constexpr llvm::StringLiteral FoundationIdentifiers[] = {
2221         "CGFloat",
2222         "CGPoint",
2223         "CGPointMake",
2224         "CGPointZero",
2225         "CGRect",
2226         "CGRectEdge",
2227         "CGRectInfinite",
2228         "CGRectMake",
2229         "CGRectNull",
2230         "CGRectZero",
2231         "CGSize",
2232         "CGSizeMake",
2233         "CGVector",
2234         "CGVectorMake",
2235         "NSAffineTransform",
2236         "NSArray",
2237         "NSAttributedString",
2238         "NSBlockOperation",
2239         "NSBundle",
2240         "NSCache",
2241         "NSCalendar",
2242         "NSCharacterSet",
2243         "NSCountedSet",
2244         "NSData",
2245         "NSDataDetector",
2246         "NSDecimal",
2247         "NSDecimalNumber",
2248         "NSDictionary",
2249         "NSEdgeInsets",
2250         "NSHashTable",
2251         "NSIndexPath",
2252         "NSIndexSet",
2253         "NSInteger",
2254         "NSInvocationOperation",
2255         "NSLocale",
2256         "NSMapTable",
2257         "NSMutableArray",
2258         "NSMutableAttributedString",
2259         "NSMutableCharacterSet",
2260         "NSMutableData",
2261         "NSMutableDictionary",
2262         "NSMutableIndexSet",
2263         "NSMutableOrderedSet",
2264         "NSMutableSet",
2265         "NSMutableString",
2266         "NSNumber",
2267         "NSNumberFormatter",
2268         "NSObject",
2269         "NSOperation",
2270         "NSOperationQueue",
2271         "NSOperationQueuePriority",
2272         "NSOrderedSet",
2273         "NSPoint",
2274         "NSPointerArray",
2275         "NSQualityOfService",
2276         "NSRange",
2277         "NSRect",
2278         "NSRegularExpression",
2279         "NSSet",
2280         "NSSize",
2281         "NSString",
2282         "NSTimeZone",
2283         "NSUInteger",
2284         "NSURL",
2285         "NSURLComponents",
2286         "NSURLQueryItem",
2287         "NSUUID",
2288         "NSValue",
2289         "UIImage",
2290         "UIView",
2291     };
2292 
2293     for (auto Line : AnnotatedLines) {
2294       if (Line->First && (Line->First->TokenText.startswith("#") ||
2295                           Line->First->TokenText == "__pragma" ||
2296                           Line->First->TokenText == "_Pragma"))
2297         continue;
2298       for (const FormatToken *FormatTok = Line->First; FormatTok;
2299            FormatTok = FormatTok->Next) {
2300         if ((FormatTok->Previous && FormatTok->Previous->is(tok::at) &&
2301              (FormatTok->Tok.getObjCKeywordID() != tok::objc_not_keyword ||
2302               FormatTok->isOneOf(tok::numeric_constant, tok::l_square,
2303                                  tok::l_brace))) ||
2304             (FormatTok->Tok.isAnyIdentifier() &&
2305              std::binary_search(std::begin(FoundationIdentifiers),
2306                                 std::end(FoundationIdentifiers),
2307                                 FormatTok->TokenText)) ||
2308             FormatTok->is(TT_ObjCStringLiteral) ||
2309             FormatTok->isOneOf(Keywords.kw_NS_CLOSED_ENUM, Keywords.kw_NS_ENUM,
2310                                Keywords.kw_NS_OPTIONS, TT_ObjCBlockLBrace,
2311                                TT_ObjCBlockLParen, TT_ObjCDecl, TT_ObjCForIn,
2312                                TT_ObjCMethodExpr, TT_ObjCMethodSpecifier,
2313                                TT_ObjCProperty)) {
2314           LLVM_DEBUG(llvm::dbgs()
2315                      << "Detected ObjC at location "
2316                      << FormatTok->Tok.getLocation().printToString(
2317                             SourceManager)
2318                      << " token: " << FormatTok->TokenText << " token type: "
2319                      << getTokenTypeName(FormatTok->getType()) << "\n");
2320           return true;
2321         }
2322         if (guessIsObjC(SourceManager, Line->Children, Keywords))
2323           return true;
2324       }
2325     }
2326     return false;
2327   }
2328 
2329   bool IsObjC;
2330 };
2331 
2332 struct IncludeDirective {
2333   StringRef Filename;
2334   StringRef Text;
2335   unsigned Offset;
2336   int Category;
2337   int Priority;
2338 };
2339 
2340 struct JavaImportDirective {
2341   StringRef Identifier;
2342   StringRef Text;
2343   unsigned Offset;
2344   std::vector<StringRef> AssociatedCommentLines;
2345   bool IsStatic;
2346 };
2347 
2348 } // end anonymous namespace
2349 
2350 // Determines whether 'Ranges' intersects with ('Start', 'End').
2351 static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
2352                          unsigned End) {
2353   for (auto Range : Ranges) {
2354     if (Range.getOffset() < End &&
2355         Range.getOffset() + Range.getLength() > Start)
2356       return true;
2357   }
2358   return false;
2359 }
2360 
2361 // Returns a pair (Index, OffsetToEOL) describing the position of the cursor
2362 // before sorting/deduplicating. Index is the index of the include under the
2363 // cursor in the original set of includes. If this include has duplicates, it is
2364 // the index of the first of the duplicates as the others are going to be
2365 // removed. OffsetToEOL describes the cursor's position relative to the end of
2366 // its current line.
2367 // If `Cursor` is not on any #include, `Index` will be UINT_MAX.
2368 static std::pair<unsigned, unsigned>
2369 FindCursorIndex(const SmallVectorImpl<IncludeDirective> &Includes,
2370                 const SmallVectorImpl<unsigned> &Indices, unsigned Cursor) {
2371   unsigned CursorIndex = UINT_MAX;
2372   unsigned OffsetToEOL = 0;
2373   for (int i = 0, e = Includes.size(); i != e; ++i) {
2374     unsigned Start = Includes[Indices[i]].Offset;
2375     unsigned End = Start + Includes[Indices[i]].Text.size();
2376     if (!(Cursor >= Start && Cursor < End))
2377       continue;
2378     CursorIndex = Indices[i];
2379     OffsetToEOL = End - Cursor;
2380     // Put the cursor on the only remaining #include among the duplicate
2381     // #includes.
2382     while (--i >= 0 && Includes[CursorIndex].Text == Includes[Indices[i]].Text)
2383       CursorIndex = i;
2384     break;
2385   }
2386   return std::make_pair(CursorIndex, OffsetToEOL);
2387 }
2388 
2389 // Replace all "\r\n" with "\n".
2390 std::string replaceCRLF(const std::string &Code) {
2391   std::string NewCode;
2392   size_t Pos = 0, LastPos = 0;
2393 
2394   do {
2395     Pos = Code.find("\r\n", LastPos);
2396     if (Pos == LastPos) {
2397       LastPos++;
2398       continue;
2399     }
2400     if (Pos == std::string::npos) {
2401       NewCode += Code.substr(LastPos);
2402       break;
2403     }
2404     NewCode += Code.substr(LastPos, Pos - LastPos) + "\n";
2405     LastPos = Pos + 2;
2406   } while (Pos != std::string::npos);
2407 
2408   return NewCode;
2409 }
2410 
2411 // Sorts and deduplicate a block of includes given by 'Includes' alphabetically
2412 // adding the necessary replacement to 'Replaces'. 'Includes' must be in strict
2413 // source order.
2414 // #include directives with the same text will be deduplicated, and only the
2415 // first #include in the duplicate #includes remains. If the `Cursor` is
2416 // provided and put on a deleted #include, it will be moved to the remaining
2417 // #include in the duplicate #includes.
2418 static void sortCppIncludes(const FormatStyle &Style,
2419                             const SmallVectorImpl<IncludeDirective> &Includes,
2420                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
2421                             StringRef Code, tooling::Replacements &Replaces,
2422                             unsigned *Cursor) {
2423   tooling::IncludeCategoryManager Categories(Style.IncludeStyle, FileName);
2424   unsigned IncludesBeginOffset = Includes.front().Offset;
2425   unsigned IncludesEndOffset =
2426       Includes.back().Offset + Includes.back().Text.size();
2427   unsigned IncludesBlockSize = IncludesEndOffset - IncludesBeginOffset;
2428   if (!affectsRange(Ranges, IncludesBeginOffset, IncludesEndOffset))
2429     return;
2430   SmallVector<unsigned, 16> Indices;
2431   for (unsigned i = 0, e = Includes.size(); i != e; ++i) {
2432     Indices.push_back(i);
2433   }
2434 
2435   if (Style.SortIncludes == FormatStyle::SI_CaseInsensitive) {
2436     llvm::stable_sort(Indices, [&](unsigned LHSI, unsigned RHSI) {
2437       const auto LHSFilenameLower = Includes[LHSI].Filename.lower();
2438       const auto RHSFilenameLower = Includes[RHSI].Filename.lower();
2439       return std::tie(Includes[LHSI].Priority, LHSFilenameLower,
2440                       Includes[LHSI].Filename) <
2441              std::tie(Includes[RHSI].Priority, RHSFilenameLower,
2442                       Includes[RHSI].Filename);
2443     });
2444   } else {
2445     llvm::stable_sort(Indices, [&](unsigned LHSI, unsigned RHSI) {
2446       return std::tie(Includes[LHSI].Priority, Includes[LHSI].Filename) <
2447              std::tie(Includes[RHSI].Priority, Includes[RHSI].Filename);
2448     });
2449   }
2450 
2451   // The index of the include on which the cursor will be put after
2452   // sorting/deduplicating.
2453   unsigned CursorIndex;
2454   // The offset from cursor to the end of line.
2455   unsigned CursorToEOLOffset;
2456   if (Cursor)
2457     std::tie(CursorIndex, CursorToEOLOffset) =
2458         FindCursorIndex(Includes, Indices, *Cursor);
2459 
2460   // Deduplicate #includes.
2461   Indices.erase(std::unique(Indices.begin(), Indices.end(),
2462                             [&](unsigned LHSI, unsigned RHSI) {
2463                               return Includes[LHSI].Text.trim() ==
2464                                      Includes[RHSI].Text.trim();
2465                             }),
2466                 Indices.end());
2467 
2468   int CurrentCategory = Includes.front().Category;
2469 
2470   // If the #includes are out of order, we generate a single replacement fixing
2471   // the entire block. Otherwise, no replacement is generated.
2472   // In case Style.IncldueStyle.IncludeBlocks != IBS_Preserve, this check is not
2473   // enough as additional newlines might be added or removed across #include
2474   // blocks. This we handle below by generating the updated #imclude blocks and
2475   // comparing it to the original.
2476   if (Indices.size() == Includes.size() && llvm::is_sorted(Indices) &&
2477       Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Preserve)
2478     return;
2479 
2480   std::string result;
2481   for (unsigned Index : Indices) {
2482     if (!result.empty()) {
2483       result += "\n";
2484       if (Style.IncludeStyle.IncludeBlocks ==
2485               tooling::IncludeStyle::IBS_Regroup &&
2486           CurrentCategory != Includes[Index].Category)
2487         result += "\n";
2488     }
2489     result += Includes[Index].Text;
2490     if (Cursor && CursorIndex == Index)
2491       *Cursor = IncludesBeginOffset + result.size() - CursorToEOLOffset;
2492     CurrentCategory = Includes[Index].Category;
2493   }
2494 
2495   // If the #includes are out of order, we generate a single replacement fixing
2496   // the entire range of blocks. Otherwise, no replacement is generated.
2497   if (replaceCRLF(result) == replaceCRLF(std::string(Code.substr(
2498                                  IncludesBeginOffset, IncludesBlockSize))))
2499     return;
2500 
2501   auto Err = Replaces.add(tooling::Replacement(
2502       FileName, Includes.front().Offset, IncludesBlockSize, result));
2503   // FIXME: better error handling. For now, just skip the replacement for the
2504   // release version.
2505   if (Err) {
2506     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
2507     assert(false);
2508   }
2509 }
2510 
2511 namespace {
2512 
2513 const char CppIncludeRegexPattern[] =
2514     R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
2515 
2516 } // anonymous namespace
2517 
2518 tooling::Replacements sortCppIncludes(const FormatStyle &Style, StringRef Code,
2519                                       ArrayRef<tooling::Range> Ranges,
2520                                       StringRef FileName,
2521                                       tooling::Replacements &Replaces,
2522                                       unsigned *Cursor) {
2523   unsigned Prev = llvm::StringSwitch<size_t>(Code)
2524                       .StartsWith("\xEF\xBB\xBF", 3) // UTF-8 BOM
2525                       .Default(0);
2526   unsigned SearchFrom = 0;
2527   llvm::Regex IncludeRegex(CppIncludeRegexPattern);
2528   SmallVector<StringRef, 4> Matches;
2529   SmallVector<IncludeDirective, 16> IncludesInBlock;
2530 
2531   // In compiled files, consider the first #include to be the main #include of
2532   // the file if it is not a system #include. This ensures that the header
2533   // doesn't have hidden dependencies
2534   // (http://llvm.org/docs/CodingStandards.html#include-style).
2535   //
2536   // FIXME: Do some sanity checking, e.g. edit distance of the base name, to fix
2537   // cases where the first #include is unlikely to be the main header.
2538   tooling::IncludeCategoryManager Categories(Style.IncludeStyle, FileName);
2539   bool FirstIncludeBlock = true;
2540   bool MainIncludeFound = false;
2541   bool FormattingOff = false;
2542 
2543   for (;;) {
2544     auto Pos = Code.find('\n', SearchFrom);
2545     StringRef Line =
2546         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
2547 
2548     StringRef Trimmed = Line.trim();
2549     if (Trimmed == "// clang-format off" || Trimmed == "/* clang-format off */")
2550       FormattingOff = true;
2551     else if (Trimmed == "// clang-format on" ||
2552              Trimmed == "/* clang-format on */")
2553       FormattingOff = false;
2554 
2555     const bool EmptyLineSkipped =
2556         Trimmed.empty() &&
2557         (Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Merge ||
2558          Style.IncludeStyle.IncludeBlocks ==
2559              tooling::IncludeStyle::IBS_Regroup);
2560 
2561     bool MergeWithNextLine = Trimmed.endswith("\\");
2562     if (!FormattingOff && !MergeWithNextLine) {
2563       if (IncludeRegex.match(Line, &Matches)) {
2564         StringRef IncludeName = Matches[2];
2565         int Category = Categories.getIncludePriority(
2566             IncludeName,
2567             /*CheckMainHeader=*/!MainIncludeFound && FirstIncludeBlock);
2568         int Priority = Categories.getSortIncludePriority(
2569             IncludeName, !MainIncludeFound && FirstIncludeBlock);
2570         if (Category == 0)
2571           MainIncludeFound = true;
2572         IncludesInBlock.push_back(
2573             {IncludeName, Line, Prev, Category, Priority});
2574       } else if (!IncludesInBlock.empty() && !EmptyLineSkipped) {
2575         sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code,
2576                         Replaces, Cursor);
2577         IncludesInBlock.clear();
2578         if (Trimmed.startswith("#pragma hdrstop")) // Precompiled headers.
2579           FirstIncludeBlock = true;
2580         else
2581           FirstIncludeBlock = false;
2582       }
2583     }
2584     if (Pos == StringRef::npos || Pos + 1 == Code.size())
2585       break;
2586 
2587     if (!MergeWithNextLine)
2588       Prev = Pos + 1;
2589     SearchFrom = Pos + 1;
2590   }
2591   if (!IncludesInBlock.empty()) {
2592     sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code, Replaces,
2593                     Cursor);
2594   }
2595   return Replaces;
2596 }
2597 
2598 // Returns group number to use as a first order sort on imports. Gives UINT_MAX
2599 // if the import does not match any given groups.
2600 static unsigned findJavaImportGroup(const FormatStyle &Style,
2601                                     StringRef ImportIdentifier) {
2602   unsigned LongestMatchIndex = UINT_MAX;
2603   unsigned LongestMatchLength = 0;
2604   for (unsigned I = 0; I < Style.JavaImportGroups.size(); I++) {
2605     std::string GroupPrefix = Style.JavaImportGroups[I];
2606     if (ImportIdentifier.startswith(GroupPrefix) &&
2607         GroupPrefix.length() > LongestMatchLength) {
2608       LongestMatchIndex = I;
2609       LongestMatchLength = GroupPrefix.length();
2610     }
2611   }
2612   return LongestMatchIndex;
2613 }
2614 
2615 // Sorts and deduplicates a block of includes given by 'Imports' based on
2616 // JavaImportGroups, then adding the necessary replacement to 'Replaces'.
2617 // Import declarations with the same text will be deduplicated. Between each
2618 // import group, a newline is inserted, and within each import group, a
2619 // lexicographic sort based on ASCII value is performed.
2620 static void sortJavaImports(const FormatStyle &Style,
2621                             const SmallVectorImpl<JavaImportDirective> &Imports,
2622                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
2623                             StringRef Code, tooling::Replacements &Replaces) {
2624   unsigned ImportsBeginOffset = Imports.front().Offset;
2625   unsigned ImportsEndOffset =
2626       Imports.back().Offset + Imports.back().Text.size();
2627   unsigned ImportsBlockSize = ImportsEndOffset - ImportsBeginOffset;
2628   if (!affectsRange(Ranges, ImportsBeginOffset, ImportsEndOffset))
2629     return;
2630   SmallVector<unsigned, 16> Indices;
2631   SmallVector<unsigned, 16> JavaImportGroups;
2632   for (unsigned i = 0, e = Imports.size(); i != e; ++i) {
2633     Indices.push_back(i);
2634     JavaImportGroups.push_back(
2635         findJavaImportGroup(Style, Imports[i].Identifier));
2636   }
2637   bool StaticImportAfterNormalImport =
2638       Style.SortJavaStaticImport == FormatStyle::SJSIO_After;
2639   llvm::sort(Indices, [&](unsigned LHSI, unsigned RHSI) {
2640     // Negating IsStatic to push static imports above non-static imports.
2641     return std::make_tuple(!Imports[LHSI].IsStatic ^
2642                                StaticImportAfterNormalImport,
2643                            JavaImportGroups[LHSI], Imports[LHSI].Identifier) <
2644            std::make_tuple(!Imports[RHSI].IsStatic ^
2645                                StaticImportAfterNormalImport,
2646                            JavaImportGroups[RHSI], Imports[RHSI].Identifier);
2647   });
2648 
2649   // Deduplicate imports.
2650   Indices.erase(std::unique(Indices.begin(), Indices.end(),
2651                             [&](unsigned LHSI, unsigned RHSI) {
2652                               return Imports[LHSI].Text == Imports[RHSI].Text;
2653                             }),
2654                 Indices.end());
2655 
2656   bool CurrentIsStatic = Imports[Indices.front()].IsStatic;
2657   unsigned CurrentImportGroup = JavaImportGroups[Indices.front()];
2658 
2659   std::string result;
2660   for (unsigned Index : Indices) {
2661     if (!result.empty()) {
2662       result += "\n";
2663       if (CurrentIsStatic != Imports[Index].IsStatic ||
2664           CurrentImportGroup != JavaImportGroups[Index])
2665         result += "\n";
2666     }
2667     for (StringRef CommentLine : Imports[Index].AssociatedCommentLines) {
2668       result += CommentLine;
2669       result += "\n";
2670     }
2671     result += Imports[Index].Text;
2672     CurrentIsStatic = Imports[Index].IsStatic;
2673     CurrentImportGroup = JavaImportGroups[Index];
2674   }
2675 
2676   // If the imports are out of order, we generate a single replacement fixing
2677   // the entire block. Otherwise, no replacement is generated.
2678   if (replaceCRLF(result) == replaceCRLF(std::string(Code.substr(
2679                                  Imports.front().Offset, ImportsBlockSize))))
2680     return;
2681 
2682   auto Err = Replaces.add(tooling::Replacement(FileName, Imports.front().Offset,
2683                                                ImportsBlockSize, result));
2684   // FIXME: better error handling. For now, just skip the replacement for the
2685   // release version.
2686   if (Err) {
2687     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
2688     assert(false);
2689   }
2690 }
2691 
2692 namespace {
2693 
2694 const char JavaImportRegexPattern[] =
2695     "^[\t ]*import[\t ]+(static[\t ]*)?([^\t ]*)[\t ]*;";
2696 
2697 } // anonymous namespace
2698 
2699 tooling::Replacements sortJavaImports(const FormatStyle &Style, StringRef Code,
2700                                       ArrayRef<tooling::Range> Ranges,
2701                                       StringRef FileName,
2702                                       tooling::Replacements &Replaces) {
2703   unsigned Prev = 0;
2704   unsigned SearchFrom = 0;
2705   llvm::Regex ImportRegex(JavaImportRegexPattern);
2706   SmallVector<StringRef, 4> Matches;
2707   SmallVector<JavaImportDirective, 16> ImportsInBlock;
2708   std::vector<StringRef> AssociatedCommentLines;
2709 
2710   bool FormattingOff = false;
2711 
2712   for (;;) {
2713     auto Pos = Code.find('\n', SearchFrom);
2714     StringRef Line =
2715         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
2716 
2717     StringRef Trimmed = Line.trim();
2718     if (Trimmed == "// clang-format off")
2719       FormattingOff = true;
2720     else if (Trimmed == "// clang-format on")
2721       FormattingOff = false;
2722 
2723     if (ImportRegex.match(Line, &Matches)) {
2724       if (FormattingOff) {
2725         // If at least one import line has formatting turned off, turn off
2726         // formatting entirely.
2727         return Replaces;
2728       }
2729       StringRef Static = Matches[1];
2730       StringRef Identifier = Matches[2];
2731       bool IsStatic = false;
2732       if (Static.contains("static")) {
2733         IsStatic = true;
2734       }
2735       ImportsInBlock.push_back(
2736           {Identifier, Line, Prev, AssociatedCommentLines, IsStatic});
2737       AssociatedCommentLines.clear();
2738     } else if (Trimmed.size() > 0 && !ImportsInBlock.empty()) {
2739       // Associating comments within the imports with the nearest import below
2740       AssociatedCommentLines.push_back(Line);
2741     }
2742     Prev = Pos + 1;
2743     if (Pos == StringRef::npos || Pos + 1 == Code.size())
2744       break;
2745     SearchFrom = Pos + 1;
2746   }
2747   if (!ImportsInBlock.empty())
2748     sortJavaImports(Style, ImportsInBlock, Ranges, FileName, Code, Replaces);
2749   return Replaces;
2750 }
2751 
2752 bool isMpegTS(StringRef Code) {
2753   // MPEG transport streams use the ".ts" file extension. clang-format should
2754   // not attempt to format those. MPEG TS' frame format starts with 0x47 every
2755   // 189 bytes - detect that and return.
2756   return Code.size() > 188 && Code[0] == 0x47 && Code[188] == 0x47;
2757 }
2758 
2759 bool isLikelyXml(StringRef Code) { return Code.ltrim().startswith("<"); }
2760 
2761 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
2762                                    ArrayRef<tooling::Range> Ranges,
2763                                    StringRef FileName, unsigned *Cursor) {
2764   tooling::Replacements Replaces;
2765   if (!Style.SortIncludes || Style.DisableFormat)
2766     return Replaces;
2767   if (isLikelyXml(Code))
2768     return Replaces;
2769   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript &&
2770       isMpegTS(Code))
2771     return Replaces;
2772   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript)
2773     return sortJavaScriptImports(Style, Code, Ranges, FileName);
2774   if (Style.Language == FormatStyle::LanguageKind::LK_Java)
2775     return sortJavaImports(Style, Code, Ranges, FileName, Replaces);
2776   sortCppIncludes(Style, Code, Ranges, FileName, Replaces, Cursor);
2777   return Replaces;
2778 }
2779 
2780 template <typename T>
2781 static llvm::Expected<tooling::Replacements>
2782 processReplacements(T ProcessFunc, StringRef Code,
2783                     const tooling::Replacements &Replaces,
2784                     const FormatStyle &Style) {
2785   if (Replaces.empty())
2786     return tooling::Replacements();
2787 
2788   auto NewCode = applyAllReplacements(Code, Replaces);
2789   if (!NewCode)
2790     return NewCode.takeError();
2791   std::vector<tooling::Range> ChangedRanges = Replaces.getAffectedRanges();
2792   StringRef FileName = Replaces.begin()->getFilePath();
2793 
2794   tooling::Replacements FormatReplaces =
2795       ProcessFunc(Style, *NewCode, ChangedRanges, FileName);
2796 
2797   return Replaces.merge(FormatReplaces);
2798 }
2799 
2800 llvm::Expected<tooling::Replacements>
2801 formatReplacements(StringRef Code, const tooling::Replacements &Replaces,
2802                    const FormatStyle &Style) {
2803   // We need to use lambda function here since there are two versions of
2804   // `sortIncludes`.
2805   auto SortIncludes = [](const FormatStyle &Style, StringRef Code,
2806                          std::vector<tooling::Range> Ranges,
2807                          StringRef FileName) -> tooling::Replacements {
2808     return sortIncludes(Style, Code, Ranges, FileName);
2809   };
2810   auto SortedReplaces =
2811       processReplacements(SortIncludes, Code, Replaces, Style);
2812   if (!SortedReplaces)
2813     return SortedReplaces.takeError();
2814 
2815   // We need to use lambda function here since there are two versions of
2816   // `reformat`.
2817   auto Reformat = [](const FormatStyle &Style, StringRef Code,
2818                      std::vector<tooling::Range> Ranges,
2819                      StringRef FileName) -> tooling::Replacements {
2820     return reformat(Style, Code, Ranges, FileName);
2821   };
2822   return processReplacements(Reformat, Code, *SortedReplaces, Style);
2823 }
2824 
2825 namespace {
2826 
2827 inline bool isHeaderInsertion(const tooling::Replacement &Replace) {
2828   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 0 &&
2829          llvm::Regex(CppIncludeRegexPattern)
2830              .match(Replace.getReplacementText());
2831 }
2832 
2833 inline bool isHeaderDeletion(const tooling::Replacement &Replace) {
2834   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 1;
2835 }
2836 
2837 // FIXME: insert empty lines between newly created blocks.
2838 tooling::Replacements
2839 fixCppIncludeInsertions(StringRef Code, const tooling::Replacements &Replaces,
2840                         const FormatStyle &Style) {
2841   if (!Style.isCpp())
2842     return Replaces;
2843 
2844   tooling::Replacements HeaderInsertions;
2845   std::set<llvm::StringRef> HeadersToDelete;
2846   tooling::Replacements Result;
2847   for (const auto &R : Replaces) {
2848     if (isHeaderInsertion(R)) {
2849       // Replacements from \p Replaces must be conflict-free already, so we can
2850       // simply consume the error.
2851       llvm::consumeError(HeaderInsertions.add(R));
2852     } else if (isHeaderDeletion(R)) {
2853       HeadersToDelete.insert(R.getReplacementText());
2854     } else if (R.getOffset() == UINT_MAX) {
2855       llvm::errs() << "Insertions other than header #include insertion are "
2856                       "not supported! "
2857                    << R.getReplacementText() << "\n";
2858     } else {
2859       llvm::consumeError(Result.add(R));
2860     }
2861   }
2862   if (HeaderInsertions.empty() && HeadersToDelete.empty())
2863     return Replaces;
2864 
2865   StringRef FileName = Replaces.begin()->getFilePath();
2866   tooling::HeaderIncludes Includes(FileName, Code, Style.IncludeStyle);
2867 
2868   for (const auto &Header : HeadersToDelete) {
2869     tooling::Replacements Replaces =
2870         Includes.remove(Header.trim("\"<>"), Header.startswith("<"));
2871     for (const auto &R : Replaces) {
2872       auto Err = Result.add(R);
2873       if (Err) {
2874         // Ignore the deletion on conflict.
2875         llvm::errs() << "Failed to add header deletion replacement for "
2876                      << Header << ": " << llvm::toString(std::move(Err))
2877                      << "\n";
2878       }
2879     }
2880   }
2881 
2882   llvm::Regex IncludeRegex = llvm::Regex(CppIncludeRegexPattern);
2883   llvm::SmallVector<StringRef, 4> Matches;
2884   for (const auto &R : HeaderInsertions) {
2885     auto IncludeDirective = R.getReplacementText();
2886     bool Matched = IncludeRegex.match(IncludeDirective, &Matches);
2887     assert(Matched && "Header insertion replacement must have replacement text "
2888                       "'#include ...'");
2889     (void)Matched;
2890     auto IncludeName = Matches[2];
2891     auto Replace =
2892         Includes.insert(IncludeName.trim("\"<>"), IncludeName.startswith("<"));
2893     if (Replace) {
2894       auto Err = Result.add(*Replace);
2895       if (Err) {
2896         llvm::consumeError(std::move(Err));
2897         unsigned NewOffset =
2898             Result.getShiftedCodePosition(Replace->getOffset());
2899         auto Shifted = tooling::Replacement(FileName, NewOffset, 0,
2900                                             Replace->getReplacementText());
2901         Result = Result.merge(tooling::Replacements(Shifted));
2902       }
2903     }
2904   }
2905   return Result;
2906 }
2907 
2908 } // anonymous namespace
2909 
2910 llvm::Expected<tooling::Replacements>
2911 cleanupAroundReplacements(StringRef Code, const tooling::Replacements &Replaces,
2912                           const FormatStyle &Style) {
2913   // We need to use lambda function here since there are two versions of
2914   // `cleanup`.
2915   auto Cleanup = [](const FormatStyle &Style, StringRef Code,
2916                     std::vector<tooling::Range> Ranges,
2917                     StringRef FileName) -> tooling::Replacements {
2918     return cleanup(Style, Code, Ranges, FileName);
2919   };
2920   // Make header insertion replacements insert new headers into correct blocks.
2921   tooling::Replacements NewReplaces =
2922       fixCppIncludeInsertions(Code, Replaces, Style);
2923   return processReplacements(Cleanup, Code, NewReplaces, Style);
2924 }
2925 
2926 namespace internal {
2927 std::pair<tooling::Replacements, unsigned>
2928 reformat(const FormatStyle &Style, StringRef Code,
2929          ArrayRef<tooling::Range> Ranges, unsigned FirstStartColumn,
2930          unsigned NextStartColumn, unsigned LastStartColumn, StringRef FileName,
2931          FormattingAttemptStatus *Status) {
2932   FormatStyle Expanded = expandPresets(Style);
2933   if (Expanded.DisableFormat)
2934     return {tooling::Replacements(), 0};
2935   if (isLikelyXml(Code))
2936     return {tooling::Replacements(), 0};
2937   if (Expanded.Language == FormatStyle::LK_JavaScript && isMpegTS(Code))
2938     return {tooling::Replacements(), 0};
2939 
2940   // JSON only needs the formatting passing.
2941   if (Style.isJson()) {
2942     std::vector<tooling::Range> Ranges(1, tooling::Range(0, Code.size()));
2943     auto Env =
2944         std::make_unique<Environment>(Code, FileName, Ranges, FirstStartColumn,
2945                                       NextStartColumn, LastStartColumn);
2946     // Perform the actual formatting pass.
2947     tooling::Replacements Replaces =
2948         Formatter(*Env, Style, Status).process().first;
2949     // add a replacement to remove the "x = " from the result.
2950     if (!Replaces.add(tooling::Replacement(FileName, 0, 4, ""))) {
2951       // apply the reformatting changes and the removal of "x = ".
2952       if (applyAllReplacements(Code, Replaces)) {
2953         return {Replaces, 0};
2954       }
2955     }
2956     return {tooling::Replacements(), 0};
2957   }
2958 
2959   typedef std::function<std::pair<tooling::Replacements, unsigned>(
2960       const Environment &)>
2961       AnalyzerPass;
2962   SmallVector<AnalyzerPass, 4> Passes;
2963 
2964   if (Style.isCpp() && Style.QualifierAlignment != FormatStyle::QAS_Leave) {
2965     Passes.emplace_back([&](const Environment &Env) {
2966       return QualifierAlignmentFixer(Env, Expanded, Code, Ranges,
2967                                      FirstStartColumn, NextStartColumn,
2968                                      LastStartColumn, FileName)
2969           .process();
2970     });
2971   }
2972 
2973   if (Style.Language == FormatStyle::LK_Cpp) {
2974     if (Style.FixNamespaceComments)
2975       Passes.emplace_back([&](const Environment &Env) {
2976         return NamespaceEndCommentsFixer(Env, Expanded).process();
2977       });
2978 
2979     if (Style.SortUsingDeclarations)
2980       Passes.emplace_back([&](const Environment &Env) {
2981         return UsingDeclarationsSorter(Env, Expanded).process();
2982       });
2983   }
2984 
2985   if (Style.Language == FormatStyle::LK_JavaScript &&
2986       Style.JavaScriptQuotes != FormatStyle::JSQS_Leave)
2987     Passes.emplace_back([&](const Environment &Env) {
2988       return JavaScriptRequoter(Env, Expanded).process();
2989     });
2990 
2991   Passes.emplace_back([&](const Environment &Env) {
2992     return Formatter(Env, Expanded, Status).process();
2993   });
2994 
2995   if (Style.Language == FormatStyle::LK_JavaScript &&
2996       Style.InsertTrailingCommas == FormatStyle::TCS_Wrapped)
2997     Passes.emplace_back([&](const Environment &Env) {
2998       return TrailingCommaInserter(Env, Expanded).process();
2999     });
3000 
3001   auto Env =
3002       std::make_unique<Environment>(Code, FileName, Ranges, FirstStartColumn,
3003                                     NextStartColumn, LastStartColumn);
3004   llvm::Optional<std::string> CurrentCode = None;
3005   tooling::Replacements Fixes;
3006   unsigned Penalty = 0;
3007   for (size_t I = 0, E = Passes.size(); I < E; ++I) {
3008     std::pair<tooling::Replacements, unsigned> PassFixes = Passes[I](*Env);
3009     auto NewCode = applyAllReplacements(
3010         CurrentCode ? StringRef(*CurrentCode) : Code, PassFixes.first);
3011     if (NewCode) {
3012       Fixes = Fixes.merge(PassFixes.first);
3013       Penalty += PassFixes.second;
3014       if (I + 1 < E) {
3015         CurrentCode = std::move(*NewCode);
3016         Env = std::make_unique<Environment>(
3017             *CurrentCode, FileName,
3018             tooling::calculateRangesAfterReplacements(Fixes, Ranges),
3019             FirstStartColumn, NextStartColumn, LastStartColumn);
3020       }
3021     }
3022   }
3023 
3024   return {Fixes, Penalty};
3025 }
3026 } // namespace internal
3027 
3028 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
3029                                ArrayRef<tooling::Range> Ranges,
3030                                StringRef FileName,
3031                                FormattingAttemptStatus *Status) {
3032   return internal::reformat(Style, Code, Ranges,
3033                             /*FirstStartColumn=*/0,
3034                             /*NextStartColumn=*/0,
3035                             /*LastStartColumn=*/0, FileName, Status)
3036       .first;
3037 }
3038 
3039 tooling::Replacements cleanup(const FormatStyle &Style, StringRef Code,
3040                               ArrayRef<tooling::Range> Ranges,
3041                               StringRef FileName) {
3042   // cleanups only apply to C++ (they mostly concern ctor commas etc.)
3043   if (Style.Language != FormatStyle::LK_Cpp)
3044     return tooling::Replacements();
3045   return Cleaner(Environment(Code, FileName, Ranges), Style).process().first;
3046 }
3047 
3048 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
3049                                ArrayRef<tooling::Range> Ranges,
3050                                StringRef FileName, bool *IncompleteFormat) {
3051   FormattingAttemptStatus Status;
3052   auto Result = reformat(Style, Code, Ranges, FileName, &Status);
3053   if (!Status.FormatComplete)
3054     *IncompleteFormat = true;
3055   return Result;
3056 }
3057 
3058 tooling::Replacements fixNamespaceEndComments(const FormatStyle &Style,
3059                                               StringRef Code,
3060                                               ArrayRef<tooling::Range> Ranges,
3061                                               StringRef FileName) {
3062   return NamespaceEndCommentsFixer(Environment(Code, FileName, Ranges), Style)
3063       .process()
3064       .first;
3065 }
3066 
3067 tooling::Replacements sortUsingDeclarations(const FormatStyle &Style,
3068                                             StringRef Code,
3069                                             ArrayRef<tooling::Range> Ranges,
3070                                             StringRef FileName) {
3071   return UsingDeclarationsSorter(Environment(Code, FileName, Ranges), Style)
3072       .process()
3073       .first;
3074 }
3075 
3076 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
3077   LangOptions LangOpts;
3078 
3079   FormatStyle::LanguageStandard LexingStd = Style.Standard;
3080   if (LexingStd == FormatStyle::LS_Auto)
3081     LexingStd = FormatStyle::LS_Latest;
3082   if (LexingStd == FormatStyle::LS_Latest)
3083     LexingStd = FormatStyle::LS_Cpp20;
3084   LangOpts.CPlusPlus = 1;
3085   LangOpts.CPlusPlus11 = LexingStd >= FormatStyle::LS_Cpp11;
3086   LangOpts.CPlusPlus14 = LexingStd >= FormatStyle::LS_Cpp14;
3087   LangOpts.CPlusPlus17 = LexingStd >= FormatStyle::LS_Cpp17;
3088   LangOpts.CPlusPlus20 = LexingStd >= FormatStyle::LS_Cpp20;
3089   LangOpts.Char8 = LexingStd >= FormatStyle::LS_Cpp20;
3090 
3091   LangOpts.LineComment = 1;
3092   bool AlternativeOperators = Style.isCpp();
3093   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
3094   LangOpts.Bool = 1;
3095   LangOpts.ObjC = 1;
3096   LangOpts.MicrosoftExt = 1;    // To get kw___try, kw___finally.
3097   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
3098   LangOpts.C99 = 1; // To get kw_restrict for non-underscore-prefixed restrict.
3099   return LangOpts;
3100 }
3101 
3102 const char *StyleOptionHelpDescription =
3103     "Coding style, currently supports:\n"
3104     "  LLVM, GNU, Google, Chromium, Microsoft, Mozilla, WebKit.\n"
3105     "Use -style=file to load style configuration from\n"
3106     ".clang-format file located in one of the parent\n"
3107     "directories of the source file (or current\n"
3108     "directory for stdin).\n"
3109     "Use -style=\"{key: value, ...}\" to set specific\n"
3110     "parameters, e.g.:\n"
3111     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
3112 
3113 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
3114   if (FileName.endswith(".java"))
3115     return FormatStyle::LK_Java;
3116   if (FileName.endswith_insensitive(".js") ||
3117       FileName.endswith_insensitive(".mjs") ||
3118       FileName.endswith_insensitive(".ts"))
3119     return FormatStyle::LK_JavaScript; // (module) JavaScript or TypeScript.
3120   if (FileName.endswith(".m") || FileName.endswith(".mm"))
3121     return FormatStyle::LK_ObjC;
3122   if (FileName.endswith_insensitive(".proto") ||
3123       FileName.endswith_insensitive(".protodevel"))
3124     return FormatStyle::LK_Proto;
3125   if (FileName.endswith_insensitive(".textpb") ||
3126       FileName.endswith_insensitive(".pb.txt") ||
3127       FileName.endswith_insensitive(".textproto") ||
3128       FileName.endswith_insensitive(".asciipb"))
3129     return FormatStyle::LK_TextProto;
3130   if (FileName.endswith_insensitive(".td"))
3131     return FormatStyle::LK_TableGen;
3132   if (FileName.endswith_insensitive(".cs"))
3133     return FormatStyle::LK_CSharp;
3134   if (FileName.endswith_insensitive(".json"))
3135     return FormatStyle::LK_Json;
3136   return FormatStyle::LK_Cpp;
3137 }
3138 
3139 FormatStyle::LanguageKind guessLanguage(StringRef FileName, StringRef Code) {
3140   const auto GuessedLanguage = getLanguageByFileName(FileName);
3141   if (GuessedLanguage == FormatStyle::LK_Cpp) {
3142     auto Extension = llvm::sys::path::extension(FileName);
3143     // If there's no file extension (or it's .h), we need to check the contents
3144     // of the code to see if it contains Objective-C.
3145     if (Extension.empty() || Extension == ".h") {
3146       auto NonEmptyFileName = FileName.empty() ? "guess.h" : FileName;
3147       Environment Env(Code, NonEmptyFileName, /*Ranges=*/{});
3148       ObjCHeaderStyleGuesser Guesser(Env, getLLVMStyle());
3149       Guesser.process();
3150       if (Guesser.isObjC())
3151         return FormatStyle::LK_ObjC;
3152     }
3153   }
3154   return GuessedLanguage;
3155 }
3156 
3157 const char *DefaultFormatStyle = "file";
3158 
3159 const char *DefaultFallbackStyle = "LLVM";
3160 
3161 llvm::Expected<FormatStyle> getStyle(StringRef StyleName, StringRef FileName,
3162                                      StringRef FallbackStyleName,
3163                                      StringRef Code, llvm::vfs::FileSystem *FS,
3164                                      bool AllowUnknownOptions) {
3165   if (!FS) {
3166     FS = llvm::vfs::getRealFileSystem().get();
3167   }
3168   FormatStyle Style = getLLVMStyle(guessLanguage(FileName, Code));
3169 
3170   FormatStyle FallbackStyle = getNoStyle();
3171   if (!getPredefinedStyle(FallbackStyleName, Style.Language, &FallbackStyle))
3172     return make_string_error("Invalid fallback style \"" + FallbackStyleName);
3173 
3174   llvm::SmallVector<std::unique_ptr<llvm::MemoryBuffer>, 1>
3175       ChildFormatTextToApply;
3176 
3177   if (StyleName.startswith("{")) {
3178     // Parse YAML/JSON style from the command line.
3179     StringRef Source = "<command-line>";
3180     if (std::error_code ec =
3181             parseConfiguration(llvm::MemoryBufferRef(StyleName, Source), &Style,
3182                                AllowUnknownOptions))
3183       return make_string_error("Error parsing -style: " + ec.message());
3184     if (Style.InheritsParentConfig)
3185       ChildFormatTextToApply.emplace_back(
3186           llvm::MemoryBuffer::getMemBuffer(StyleName, Source, false));
3187     else
3188       return Style;
3189   }
3190 
3191   // If the style inherits the parent configuration it is a command line
3192   // configuration, which wants to inherit, so we have to skip the check of the
3193   // StyleName.
3194   if (!Style.InheritsParentConfig && !StyleName.equals_insensitive("file")) {
3195     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
3196       return make_string_error("Invalid value for -style");
3197     if (!Style.InheritsParentConfig)
3198       return Style;
3199   }
3200 
3201   // Reset possible inheritance
3202   Style.InheritsParentConfig = false;
3203 
3204   // Look for .clang-format/_clang-format file in the file's parent directories.
3205   SmallString<128> UnsuitableConfigFiles;
3206   SmallString<128> Path(FileName);
3207   if (std::error_code EC = FS->makeAbsolute(Path))
3208     return make_string_error(EC.message());
3209 
3210   llvm::SmallVector<std::string, 2> FilesToLookFor;
3211   FilesToLookFor.push_back(".clang-format");
3212   FilesToLookFor.push_back("_clang-format");
3213 
3214   auto dropDiagnosticHandler = [](const llvm::SMDiagnostic &, void *) {};
3215 
3216   for (StringRef Directory = Path; !Directory.empty();
3217        Directory = llvm::sys::path::parent_path(Directory)) {
3218 
3219     auto Status = FS->status(Directory);
3220     if (!Status ||
3221         Status->getType() != llvm::sys::fs::file_type::directory_file) {
3222       continue;
3223     }
3224 
3225     for (const auto &F : FilesToLookFor) {
3226       SmallString<128> ConfigFile(Directory);
3227 
3228       llvm::sys::path::append(ConfigFile, F);
3229       LLVM_DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
3230 
3231       Status = FS->status(ConfigFile.str());
3232 
3233       if (Status &&
3234           (Status->getType() == llvm::sys::fs::file_type::regular_file)) {
3235         llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
3236             FS->getBufferForFile(ConfigFile.str());
3237         if (std::error_code EC = Text.getError())
3238           return make_string_error(EC.message());
3239         if (std::error_code ec =
3240                 parseConfiguration(*Text.get(), &Style, AllowUnknownOptions)) {
3241           if (ec == ParseError::Unsuitable) {
3242             if (!UnsuitableConfigFiles.empty())
3243               UnsuitableConfigFiles.append(", ");
3244             UnsuitableConfigFiles.append(ConfigFile);
3245             continue;
3246           }
3247           return make_string_error("Error reading " + ConfigFile + ": " +
3248                                    ec.message());
3249         }
3250         LLVM_DEBUG(llvm::dbgs()
3251                    << "Using configuration file " << ConfigFile << "\n");
3252 
3253         if (!Style.InheritsParentConfig) {
3254           if (ChildFormatTextToApply.empty())
3255             return Style;
3256 
3257           LLVM_DEBUG(llvm::dbgs() << "Applying child configurations\n");
3258 
3259           for (const auto &MemBuf : llvm::reverse(ChildFormatTextToApply)) {
3260             auto Ec = parseConfiguration(*MemBuf, &Style, AllowUnknownOptions,
3261                                          dropDiagnosticHandler);
3262             // It was already correctly parsed.
3263             assert(!Ec);
3264             static_cast<void>(Ec);
3265           }
3266 
3267           return Style;
3268         }
3269 
3270         LLVM_DEBUG(llvm::dbgs() << "Inherits parent configuration\n");
3271 
3272         // Reset inheritance of style
3273         Style.InheritsParentConfig = false;
3274 
3275         ChildFormatTextToApply.emplace_back(std::move(*Text));
3276 
3277         // Breaking out of the inner loop, since we don't want to parse
3278         // .clang-format AND _clang-format, if both exist. Then we continue the
3279         // inner loop (parent directories) in search for the parent
3280         // configuration.
3281         break;
3282       }
3283     }
3284   }
3285   if (!UnsuitableConfigFiles.empty())
3286     return make_string_error("Configuration file(s) do(es) not support " +
3287                              getLanguageName(Style.Language) + ": " +
3288                              UnsuitableConfigFiles);
3289 
3290   if (!ChildFormatTextToApply.empty()) {
3291     assert(ChildFormatTextToApply.size() == 1);
3292 
3293     LLVM_DEBUG(llvm::dbgs()
3294                << "Applying child configuration on fallback style\n");
3295 
3296     auto Ec =
3297         parseConfiguration(*ChildFormatTextToApply.front(), &FallbackStyle,
3298                            AllowUnknownOptions, dropDiagnosticHandler);
3299     // It was already correctly parsed.
3300     assert(!Ec);
3301     static_cast<void>(Ec);
3302   }
3303 
3304   return FallbackStyle;
3305 }
3306 
3307 } // namespace format
3308 } // namespace clang
3309