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