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