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