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