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