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