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