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