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