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