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 "ContinuationIndenter.h"
18 #include "FormatInternal.h"
19 #include "FormatTokenLexer.h"
20 #include "NamespaceEndCommentsFixer.h"
21 #include "SortJavaScriptImports.h"
22 #include "TokenAnalyzer.h"
23 #include "TokenAnnotator.h"
24 #include "UnwrappedLineFormatter.h"
25 #include "UnwrappedLineParser.h"
26 #include "UsingDeclarationsSorter.h"
27 #include "WhitespaceManager.h"
28 #include "clang/Basic/Diagnostic.h"
29 #include "clang/Basic/DiagnosticOptions.h"
30 #include "clang/Basic/SourceManager.h"
31 #include "clang/Lex/Lexer.h"
32 #include "clang/Tooling/Inclusions/HeaderIncludes.h"
33 #include "llvm/ADT/STLExtras.h"
34 #include "llvm/ADT/StringRef.h"
35 #include "llvm/Support/Allocator.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/Path.h"
38 #include "llvm/Support/Regex.h"
39 #include "llvm/Support/VirtualFileSystem.h"
40 #include "llvm/Support/YAMLTraits.h"
41 #include <algorithm>
42 #include <memory>
43 #include <mutex>
44 #include <string>
45 #include <unordered_map>
46 
47 #define DEBUG_TYPE "format-formatter"
48 
49 using clang::format::FormatStyle;
50 
51 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::format::FormatStyle::RawStringFormat)
52 
53 namespace llvm {
54 namespace yaml {
55 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
56   static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
57     IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
58     IO.enumCase(Value, "Java", FormatStyle::LK_Java);
59     IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
60     IO.enumCase(Value, "ObjC", FormatStyle::LK_ObjC);
61     IO.enumCase(Value, "Proto", FormatStyle::LK_Proto);
62     IO.enumCase(Value, "TableGen", FormatStyle::LK_TableGen);
63     IO.enumCase(Value, "TextProto", FormatStyle::LK_TextProto);
64     IO.enumCase(Value, "CSharp", FormatStyle::LK_CSharp);
65   }
66 };
67 
68 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
69   static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
70     IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03);
71     IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03);
72     IO.enumCase(Value, "Cpp11", FormatStyle::LS_Cpp11);
73     IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11);
74     IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
75   }
76 };
77 
78 template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
79   static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
80     IO.enumCase(Value, "Never", FormatStyle::UT_Never);
81     IO.enumCase(Value, "false", FormatStyle::UT_Never);
82     IO.enumCase(Value, "Always", FormatStyle::UT_Always);
83     IO.enumCase(Value, "true", FormatStyle::UT_Always);
84     IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
85     IO.enumCase(Value, "ForContinuationAndIndentation",
86                 FormatStyle::UT_ForContinuationAndIndentation);
87   }
88 };
89 
90 template <> struct ScalarEnumerationTraits<FormatStyle::JavaScriptQuoteStyle> {
91   static void enumeration(IO &IO, FormatStyle::JavaScriptQuoteStyle &Value) {
92     IO.enumCase(Value, "Leave", FormatStyle::JSQS_Leave);
93     IO.enumCase(Value, "Single", FormatStyle::JSQS_Single);
94     IO.enumCase(Value, "Double", FormatStyle::JSQS_Double);
95   }
96 };
97 
98 template <> struct ScalarEnumerationTraits<FormatStyle::ShortBlockStyle> {
99   static void enumeration(IO &IO, FormatStyle::ShortBlockStyle &Value) {
100     IO.enumCase(Value, "Never", FormatStyle::SBS_Never);
101     IO.enumCase(Value, "false", FormatStyle::SBS_Never);
102     IO.enumCase(Value, "Always", FormatStyle::SBS_Always);
103     IO.enumCase(Value, "true", FormatStyle::SBS_Always);
104     IO.enumCase(Value, "Empty", FormatStyle::SBS_Empty);
105   }
106 };
107 
108 template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
109   static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
110     IO.enumCase(Value, "None", FormatStyle::SFS_None);
111     IO.enumCase(Value, "false", FormatStyle::SFS_None);
112     IO.enumCase(Value, "All", FormatStyle::SFS_All);
113     IO.enumCase(Value, "true", FormatStyle::SFS_All);
114     IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
115     IO.enumCase(Value, "InlineOnly", FormatStyle::SFS_InlineOnly);
116     IO.enumCase(Value, "Empty", FormatStyle::SFS_Empty);
117   }
118 };
119 
120 template <> struct ScalarEnumerationTraits<FormatStyle::ShortIfStyle> {
121   static void enumeration(IO &IO, FormatStyle::ShortIfStyle &Value) {
122     IO.enumCase(Value, "Never", FormatStyle::SIS_Never);
123     IO.enumCase(Value, "Always", FormatStyle::SIS_Always);
124     IO.enumCase(Value, "WithoutElse", FormatStyle::SIS_WithoutElse);
125 
126     // For backward compatibility.
127     IO.enumCase(Value, "false", FormatStyle::SIS_Never);
128     IO.enumCase(Value, "true", FormatStyle::SIS_WithoutElse);
129   }
130 };
131 
132 template <> struct ScalarEnumerationTraits<FormatStyle::ShortLambdaStyle> {
133   static void enumeration(IO &IO, FormatStyle::ShortLambdaStyle &Value) {
134     IO.enumCase(Value, "None", FormatStyle::SLS_None);
135     IO.enumCase(Value, "false", FormatStyle::SLS_None);
136     IO.enumCase(Value, "Empty", FormatStyle::SLS_Empty);
137     IO.enumCase(Value, "Inline", FormatStyle::SLS_Inline);
138     IO.enumCase(Value, "All", FormatStyle::SLS_All);
139     IO.enumCase(Value, "true", FormatStyle::SLS_All);
140   }
141 };
142 
143 template <> struct ScalarEnumerationTraits<FormatStyle::BinPackStyle> {
144   static void enumeration(IO &IO, FormatStyle::BinPackStyle &Value) {
145     IO.enumCase(Value, "Auto", FormatStyle::BPS_Auto);
146     IO.enumCase(Value, "Always", FormatStyle::BPS_Always);
147     IO.enumCase(Value, "Never", FormatStyle::BPS_Never);
148   }
149 };
150 
151 template <> struct ScalarEnumerationTraits<FormatStyle::BinaryOperatorStyle> {
152   static void enumeration(IO &IO, FormatStyle::BinaryOperatorStyle &Value) {
153     IO.enumCase(Value, "All", FormatStyle::BOS_All);
154     IO.enumCase(Value, "true", FormatStyle::BOS_All);
155     IO.enumCase(Value, "None", FormatStyle::BOS_None);
156     IO.enumCase(Value, "false", FormatStyle::BOS_None);
157     IO.enumCase(Value, "NonAssignment", FormatStyle::BOS_NonAssignment);
158   }
159 };
160 
161 template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
162   static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
163     IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
164     IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
165     IO.enumCase(Value, "Mozilla", FormatStyle::BS_Mozilla);
166     IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
167     IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
168     IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
169     IO.enumCase(Value, "WebKit", FormatStyle::BS_WebKit);
170     IO.enumCase(Value, "Custom", FormatStyle::BS_Custom);
171   }
172 };
173 
174 template <>
175 struct ScalarEnumerationTraits<FormatStyle::BreakConstructorInitializersStyle> {
176   static void
177   enumeration(IO &IO, FormatStyle::BreakConstructorInitializersStyle &Value) {
178     IO.enumCase(Value, "BeforeColon", FormatStyle::BCIS_BeforeColon);
179     IO.enumCase(Value, "BeforeComma", FormatStyle::BCIS_BeforeComma);
180     IO.enumCase(Value, "AfterColon", FormatStyle::BCIS_AfterColon);
181   }
182 };
183 
184 template <>
185 struct ScalarEnumerationTraits<FormatStyle::BreakInheritanceListStyle> {
186   static void enumeration(IO &IO,
187                           FormatStyle::BreakInheritanceListStyle &Value) {
188     IO.enumCase(Value, "BeforeColon", FormatStyle::BILS_BeforeColon);
189     IO.enumCase(Value, "BeforeComma", FormatStyle::BILS_BeforeComma);
190     IO.enumCase(Value, "AfterColon", FormatStyle::BILS_AfterColon);
191   }
192 };
193 
194 template <>
195 struct ScalarEnumerationTraits<FormatStyle::PPDirectiveIndentStyle> {
196   static void enumeration(IO &IO, FormatStyle::PPDirectiveIndentStyle &Value) {
197     IO.enumCase(Value, "None", FormatStyle::PPDIS_None);
198     IO.enumCase(Value, "AfterHash", FormatStyle::PPDIS_AfterHash);
199     IO.enumCase(Value, "BeforeHash", FormatStyle::PPDIS_BeforeHash);
200   }
201 };
202 
203 template <>
204 struct ScalarEnumerationTraits<FormatStyle::ReturnTypeBreakingStyle> {
205   static void enumeration(IO &IO, FormatStyle::ReturnTypeBreakingStyle &Value) {
206     IO.enumCase(Value, "None", FormatStyle::RTBS_None);
207     IO.enumCase(Value, "All", FormatStyle::RTBS_All);
208     IO.enumCase(Value, "TopLevel", FormatStyle::RTBS_TopLevel);
209     IO.enumCase(Value, "TopLevelDefinitions",
210                 FormatStyle::RTBS_TopLevelDefinitions);
211     IO.enumCase(Value, "AllDefinitions", FormatStyle::RTBS_AllDefinitions);
212   }
213 };
214 
215 template <>
216 struct ScalarEnumerationTraits<FormatStyle::BreakTemplateDeclarationsStyle> {
217   static void enumeration(IO &IO,
218                           FormatStyle::BreakTemplateDeclarationsStyle &Value) {
219     IO.enumCase(Value, "No", FormatStyle::BTDS_No);
220     IO.enumCase(Value, "MultiLine", FormatStyle::BTDS_MultiLine);
221     IO.enumCase(Value, "Yes", FormatStyle::BTDS_Yes);
222 
223     // For backward compatibility.
224     IO.enumCase(Value, "false", FormatStyle::BTDS_MultiLine);
225     IO.enumCase(Value, "true", FormatStyle::BTDS_Yes);
226   }
227 };
228 
229 template <>
230 struct ScalarEnumerationTraits<FormatStyle::DefinitionReturnTypeBreakingStyle> {
231   static void
232   enumeration(IO &IO, FormatStyle::DefinitionReturnTypeBreakingStyle &Value) {
233     IO.enumCase(Value, "None", FormatStyle::DRTBS_None);
234     IO.enumCase(Value, "All", FormatStyle::DRTBS_All);
235     IO.enumCase(Value, "TopLevel", FormatStyle::DRTBS_TopLevel);
236 
237     // For backward compatibility.
238     IO.enumCase(Value, "false", FormatStyle::DRTBS_None);
239     IO.enumCase(Value, "true", FormatStyle::DRTBS_All);
240   }
241 };
242 
243 template <>
244 struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
245   static void enumeration(IO &IO,
246                           FormatStyle::NamespaceIndentationKind &Value) {
247     IO.enumCase(Value, "None", FormatStyle::NI_None);
248     IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
249     IO.enumCase(Value, "All", FormatStyle::NI_All);
250   }
251 };
252 
253 template <> struct ScalarEnumerationTraits<FormatStyle::BracketAlignmentStyle> {
254   static void enumeration(IO &IO, FormatStyle::BracketAlignmentStyle &Value) {
255     IO.enumCase(Value, "Align", FormatStyle::BAS_Align);
256     IO.enumCase(Value, "DontAlign", FormatStyle::BAS_DontAlign);
257     IO.enumCase(Value, "AlwaysBreak", FormatStyle::BAS_AlwaysBreak);
258 
259     // For backward compatibility.
260     IO.enumCase(Value, "true", FormatStyle::BAS_Align);
261     IO.enumCase(Value, "false", FormatStyle::BAS_DontAlign);
262   }
263 };
264 
265 template <>
266 struct ScalarEnumerationTraits<FormatStyle::EscapedNewlineAlignmentStyle> {
267   static void enumeration(IO &IO,
268                           FormatStyle::EscapedNewlineAlignmentStyle &Value) {
269     IO.enumCase(Value, "DontAlign", FormatStyle::ENAS_DontAlign);
270     IO.enumCase(Value, "Left", FormatStyle::ENAS_Left);
271     IO.enumCase(Value, "Right", FormatStyle::ENAS_Right);
272 
273     // For backward compatibility.
274     IO.enumCase(Value, "true", FormatStyle::ENAS_Left);
275     IO.enumCase(Value, "false", FormatStyle::ENAS_Right);
276   }
277 };
278 
279 template <> struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
280   static void enumeration(IO &IO, FormatStyle::PointerAlignmentStyle &Value) {
281     IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
282     IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
283     IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
284 
285     // For backward compatibility.
286     IO.enumCase(Value, "true", FormatStyle::PAS_Left);
287     IO.enumCase(Value, "false", FormatStyle::PAS_Right);
288   }
289 };
290 
291 template <>
292 struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
293   static void enumeration(IO &IO,
294                           FormatStyle::SpaceBeforeParensOptions &Value) {
295     IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
296     IO.enumCase(Value, "ControlStatements",
297                 FormatStyle::SBPO_ControlStatements);
298     IO.enumCase(Value, "NonEmptyParentheses",
299                 FormatStyle::SBPO_NonEmptyParentheses);
300     IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
301 
302     // For backward compatibility.
303     IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
304     IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
305   }
306 };
307 
308 template <> struct MappingTraits<FormatStyle> {
309   static void mapping(IO &IO, FormatStyle &Style) {
310     // When reading, read the language first, we need it for getPredefinedStyle.
311     IO.mapOptional("Language", Style.Language);
312 
313     if (IO.outputting()) {
314       StringRef StylesArray[] = {"LLVM",   "Google", "Chromium", "Mozilla",
315                                  "WebKit", "GNU",    "Microsoft"};
316       ArrayRef<StringRef> Styles(StylesArray);
317       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
318         StringRef StyleName(Styles[i]);
319         FormatStyle PredefinedStyle;
320         if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
321             Style == PredefinedStyle) {
322           IO.mapOptional("# BasedOnStyle", StyleName);
323           break;
324         }
325       }
326     } else {
327       StringRef BasedOnStyle;
328       IO.mapOptional("BasedOnStyle", BasedOnStyle);
329       if (!BasedOnStyle.empty()) {
330         FormatStyle::LanguageKind OldLanguage = Style.Language;
331         FormatStyle::LanguageKind Language =
332             ((FormatStyle *)IO.getContext())->Language;
333         if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
334           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
335           return;
336         }
337         Style.Language = OldLanguage;
338       }
339     }
340 
341     // For backward compatibility.
342     if (!IO.outputting()) {
343       IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlines);
344       IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
345       IO.mapOptional("IndentFunctionDeclarationAfterType",
346                      Style.IndentWrappedFunctionNames);
347       IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
348       IO.mapOptional("SpaceAfterControlStatementKeyword",
349                      Style.SpaceBeforeParens);
350     }
351 
352     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
353     IO.mapOptional("AlignAfterOpenBracket", Style.AlignAfterOpenBracket);
354     IO.mapOptional("AlignConsecutiveMacros", Style.AlignConsecutiveMacros);
355     IO.mapOptional("AlignConsecutiveAssignments",
356                    Style.AlignConsecutiveAssignments);
357     IO.mapOptional("AlignConsecutiveDeclarations",
358                    Style.AlignConsecutiveDeclarations);
359     IO.mapOptional("AlignEscapedNewlines", Style.AlignEscapedNewlines);
360     IO.mapOptional("AlignOperands", Style.AlignOperands);
361     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
362     IO.mapOptional("AllowAllArgumentsOnNextLine",
363                    Style.AllowAllArgumentsOnNextLine);
364     IO.mapOptional("AllowAllConstructorInitializersOnNextLine",
365                    Style.AllowAllConstructorInitializersOnNextLine);
366     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
367                    Style.AllowAllParametersOfDeclarationOnNextLine);
368     IO.mapOptional("AllowShortBlocksOnASingleLine",
369                    Style.AllowShortBlocksOnASingleLine);
370     IO.mapOptional("AllowShortCaseLabelsOnASingleLine",
371                    Style.AllowShortCaseLabelsOnASingleLine);
372     IO.mapOptional("AllowShortFunctionsOnASingleLine",
373                    Style.AllowShortFunctionsOnASingleLine);
374     IO.mapOptional("AllowShortLambdasOnASingleLine",
375                    Style.AllowShortLambdasOnASingleLine);
376     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
377                    Style.AllowShortIfStatementsOnASingleLine);
378     IO.mapOptional("AllowShortLoopsOnASingleLine",
379                    Style.AllowShortLoopsOnASingleLine);
380     IO.mapOptional("AlwaysBreakAfterDefinitionReturnType",
381                    Style.AlwaysBreakAfterDefinitionReturnType);
382     IO.mapOptional("AlwaysBreakAfterReturnType",
383                    Style.AlwaysBreakAfterReturnType);
384 
385     // If AlwaysBreakAfterDefinitionReturnType was specified but
386     // AlwaysBreakAfterReturnType was not, initialize the latter from the
387     // former for backwards compatibility.
388     if (Style.AlwaysBreakAfterDefinitionReturnType != FormatStyle::DRTBS_None &&
389         Style.AlwaysBreakAfterReturnType == FormatStyle::RTBS_None) {
390       if (Style.AlwaysBreakAfterDefinitionReturnType == FormatStyle::DRTBS_All)
391         Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
392       else if (Style.AlwaysBreakAfterDefinitionReturnType ==
393                FormatStyle::DRTBS_TopLevel)
394         Style.AlwaysBreakAfterReturnType =
395             FormatStyle::RTBS_TopLevelDefinitions;
396     }
397 
398     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
399                    Style.AlwaysBreakBeforeMultilineStrings);
400     IO.mapOptional("AlwaysBreakTemplateDeclarations",
401                    Style.AlwaysBreakTemplateDeclarations);
402     IO.mapOptional("BinPackArguments", Style.BinPackArguments);
403     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
404     IO.mapOptional("BraceWrapping", Style.BraceWrapping);
405     IO.mapOptional("BreakBeforeBinaryOperators",
406                    Style.BreakBeforeBinaryOperators);
407     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
408 
409     bool BreakBeforeInheritanceComma = false;
410     IO.mapOptional("BreakBeforeInheritanceComma", BreakBeforeInheritanceComma);
411     IO.mapOptional("BreakInheritanceList", Style.BreakInheritanceList);
412     // If BreakBeforeInheritanceComma was specified but
413     // BreakInheritance was not, initialize the latter from the
414     // former for backwards compatibility.
415     if (BreakBeforeInheritanceComma &&
416         Style.BreakInheritanceList == FormatStyle::BILS_BeforeColon)
417       Style.BreakInheritanceList = FormatStyle::BILS_BeforeComma;
418 
419     IO.mapOptional("BreakBeforeTernaryOperators",
420                    Style.BreakBeforeTernaryOperators);
421 
422     bool BreakConstructorInitializersBeforeComma = false;
423     IO.mapOptional("BreakConstructorInitializersBeforeComma",
424                    BreakConstructorInitializersBeforeComma);
425     IO.mapOptional("BreakConstructorInitializers",
426                    Style.BreakConstructorInitializers);
427     // If BreakConstructorInitializersBeforeComma was specified but
428     // BreakConstructorInitializers was not, initialize the latter from the
429     // former for backwards compatibility.
430     if (BreakConstructorInitializersBeforeComma &&
431         Style.BreakConstructorInitializers == FormatStyle::BCIS_BeforeColon)
432       Style.BreakConstructorInitializers = FormatStyle::BCIS_BeforeComma;
433 
434     IO.mapOptional("BreakAfterJavaFieldAnnotations",
435                    Style.BreakAfterJavaFieldAnnotations);
436     IO.mapOptional("BreakStringLiterals", Style.BreakStringLiterals);
437     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
438     IO.mapOptional("CommentPragmas", Style.CommentPragmas);
439     IO.mapOptional("CompactNamespaces", Style.CompactNamespaces);
440     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
441                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
442     IO.mapOptional("ConstructorInitializerIndentWidth",
443                    Style.ConstructorInitializerIndentWidth);
444     IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
445     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
446     IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
447     IO.mapOptional("DisableFormat", Style.DisableFormat);
448     IO.mapOptional("ExperimentalAutoDetectBinPacking",
449                    Style.ExperimentalAutoDetectBinPacking);
450     IO.mapOptional("FixNamespaceComments", Style.FixNamespaceComments);
451     IO.mapOptional("ForEachMacros", Style.ForEachMacros);
452     IO.mapOptional("IncludeBlocks", Style.IncludeStyle.IncludeBlocks);
453     IO.mapOptional("IncludeCategories", Style.IncludeStyle.IncludeCategories);
454     IO.mapOptional("IncludeIsMainRegex", Style.IncludeStyle.IncludeIsMainRegex);
455     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
456     IO.mapOptional("IndentGotoLabels", Style.IndentGotoLabels);
457     IO.mapOptional("IndentPPDirectives", Style.IndentPPDirectives);
458     IO.mapOptional("IndentWidth", Style.IndentWidth);
459     IO.mapOptional("IndentWrappedFunctionNames",
460                    Style.IndentWrappedFunctionNames);
461     IO.mapOptional("JavaImportGroups", Style.JavaImportGroups);
462     IO.mapOptional("JavaScriptQuotes", Style.JavaScriptQuotes);
463     IO.mapOptional("JavaScriptWrapImports", Style.JavaScriptWrapImports);
464     IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
465                    Style.KeepEmptyLinesAtTheStartOfBlocks);
466     IO.mapOptional("MacroBlockBegin", Style.MacroBlockBegin);
467     IO.mapOptional("MacroBlockEnd", Style.MacroBlockEnd);
468     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
469     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
470     IO.mapOptional("NamespaceMacros", Style.NamespaceMacros);
471     IO.mapOptional("ObjCBinPackProtocolList", Style.ObjCBinPackProtocolList);
472     IO.mapOptional("ObjCBlockIndentWidth", Style.ObjCBlockIndentWidth);
473     IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
474     IO.mapOptional("ObjCSpaceBeforeProtocolList",
475                    Style.ObjCSpaceBeforeProtocolList);
476     IO.mapOptional("PenaltyBreakAssignment", Style.PenaltyBreakAssignment);
477     IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
478                    Style.PenaltyBreakBeforeFirstCallParameter);
479     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
480     IO.mapOptional("PenaltyBreakFirstLessLess",
481                    Style.PenaltyBreakFirstLessLess);
482     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
483     IO.mapOptional("PenaltyBreakTemplateDeclaration",
484                    Style.PenaltyBreakTemplateDeclaration);
485     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
486     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
487                    Style.PenaltyReturnTypeOnItsOwnLine);
488     IO.mapOptional("PointerAlignment", Style.PointerAlignment);
489     IO.mapOptional("RawStringFormats", Style.RawStringFormats);
490     IO.mapOptional("ReflowComments", Style.ReflowComments);
491     IO.mapOptional("SortIncludes", Style.SortIncludes);
492     IO.mapOptional("SortUsingDeclarations", Style.SortUsingDeclarations);
493     IO.mapOptional("SpaceAfterCStyleCast", Style.SpaceAfterCStyleCast);
494     IO.mapOptional("SpaceAfterLogicalNot", Style.SpaceAfterLogicalNot);
495     IO.mapOptional("SpaceAfterTemplateKeyword",
496                    Style.SpaceAfterTemplateKeyword);
497     IO.mapOptional("SpaceBeforeAssignmentOperators",
498                    Style.SpaceBeforeAssignmentOperators);
499     IO.mapOptional("SpaceBeforeCpp11BracedList",
500                    Style.SpaceBeforeCpp11BracedList);
501     IO.mapOptional("SpaceBeforeCtorInitializerColon",
502                    Style.SpaceBeforeCtorInitializerColon);
503     IO.mapOptional("SpaceBeforeInheritanceColon",
504                    Style.SpaceBeforeInheritanceColon);
505     IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
506     IO.mapOptional("SpaceBeforeRangeBasedForLoopColon",
507                    Style.SpaceBeforeRangeBasedForLoopColon);
508     IO.mapOptional("SpaceInEmptyBlock", Style.SpaceInEmptyBlock);
509     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
510     IO.mapOptional("SpacesBeforeTrailingComments",
511                    Style.SpacesBeforeTrailingComments);
512     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
513     IO.mapOptional("SpacesInContainerLiterals",
514                    Style.SpacesInContainerLiterals);
515     IO.mapOptional("SpacesInCStyleCastParentheses",
516                    Style.SpacesInCStyleCastParentheses);
517     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
518     IO.mapOptional("SpacesInSquareBrackets", Style.SpacesInSquareBrackets);
519     IO.mapOptional("Standard", Style.Standard);
520     IO.mapOptional("StatementMacros", Style.StatementMacros);
521     IO.mapOptional("TabWidth", Style.TabWidth);
522     IO.mapOptional("TypenameMacros", Style.TypenameMacros);
523     IO.mapOptional("UseTab", Style.UseTab);
524   }
525 };
526 
527 template <> struct MappingTraits<FormatStyle::BraceWrappingFlags> {
528   static void mapping(IO &IO, FormatStyle::BraceWrappingFlags &Wrapping) {
529     IO.mapOptional("AfterCaseLabel", Wrapping.AfterCaseLabel);
530     IO.mapOptional("AfterClass", Wrapping.AfterClass);
531     IO.mapOptional("AfterControlStatement", Wrapping.AfterControlStatement);
532     IO.mapOptional("AfterEnum", Wrapping.AfterEnum);
533     IO.mapOptional("AfterFunction", Wrapping.AfterFunction);
534     IO.mapOptional("AfterNamespace", Wrapping.AfterNamespace);
535     IO.mapOptional("AfterObjCDeclaration", Wrapping.AfterObjCDeclaration);
536     IO.mapOptional("AfterStruct", Wrapping.AfterStruct);
537     IO.mapOptional("AfterUnion", Wrapping.AfterUnion);
538     IO.mapOptional("AfterExternBlock", Wrapping.AfterExternBlock);
539     IO.mapOptional("BeforeCatch", Wrapping.BeforeCatch);
540     IO.mapOptional("BeforeElse", Wrapping.BeforeElse);
541     IO.mapOptional("IndentBraces", Wrapping.IndentBraces);
542     IO.mapOptional("SplitEmptyFunction", Wrapping.SplitEmptyFunction);
543     IO.mapOptional("SplitEmptyRecord", Wrapping.SplitEmptyRecord);
544     IO.mapOptional("SplitEmptyNamespace", Wrapping.SplitEmptyNamespace);
545   }
546 };
547 
548 template <> struct MappingTraits<FormatStyle::RawStringFormat> {
549   static void mapping(IO &IO, FormatStyle::RawStringFormat &Format) {
550     IO.mapOptional("Language", Format.Language);
551     IO.mapOptional("Delimiters", Format.Delimiters);
552     IO.mapOptional("EnclosingFunctions", Format.EnclosingFunctions);
553     IO.mapOptional("CanonicalDelimiter", Format.CanonicalDelimiter);
554     IO.mapOptional("BasedOnStyle", Format.BasedOnStyle);
555   }
556 };
557 
558 // Allows to read vector<FormatStyle> while keeping default values.
559 // IO.getContext() should contain a pointer to the FormatStyle structure, that
560 // will be used to get default values for missing keys.
561 // If the first element has no Language specified, it will be treated as the
562 // default one for the following elements.
563 template <> struct DocumentListTraits<std::vector<FormatStyle>> {
564   static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
565     return Seq.size();
566   }
567   static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
568                               size_t Index) {
569     if (Index >= Seq.size()) {
570       assert(Index == Seq.size());
571       FormatStyle Template;
572       if (!Seq.empty() && Seq[0].Language == FormatStyle::LK_None) {
573         Template = Seq[0];
574       } else {
575         Template = *((const FormatStyle *)IO.getContext());
576         Template.Language = FormatStyle::LK_None;
577       }
578       Seq.resize(Index + 1, Template);
579     }
580     return Seq[Index];
581   }
582 };
583 } // namespace yaml
584 } // namespace llvm
585 
586 namespace clang {
587 namespace format {
588 
589 const std::error_category &getParseCategory() {
590   static const ParseErrorCategory C{};
591   return C;
592 }
593 std::error_code make_error_code(ParseError e) {
594   return std::error_code(static_cast<int>(e), getParseCategory());
595 }
596 
597 inline llvm::Error make_string_error(const llvm::Twine &Message) {
598   return llvm::make_error<llvm::StringError>(Message,
599                                              llvm::inconvertibleErrorCode());
600 }
601 
602 const char *ParseErrorCategory::name() const noexcept {
603   return "clang-format.parse_error";
604 }
605 
606 std::string ParseErrorCategory::message(int EV) const {
607   switch (static_cast<ParseError>(EV)) {
608   case ParseError::Success:
609     return "Success";
610   case ParseError::Error:
611     return "Invalid argument";
612   case ParseError::Unsuitable:
613     return "Unsuitable";
614   }
615   llvm_unreachable("unexpected parse error");
616 }
617 
618 static FormatStyle expandPresets(const FormatStyle &Style) {
619   if (Style.BreakBeforeBraces == FormatStyle::BS_Custom)
620     return Style;
621   FormatStyle Expanded = Style;
622   Expanded.BraceWrapping = {false, false, false, false, false, false,
623                             false, false, false, false, false, false,
624                             false, true,  true,  true};
625   switch (Style.BreakBeforeBraces) {
626   case FormatStyle::BS_Linux:
627     Expanded.BraceWrapping.AfterClass = true;
628     Expanded.BraceWrapping.AfterFunction = true;
629     Expanded.BraceWrapping.AfterNamespace = true;
630     break;
631   case FormatStyle::BS_Mozilla:
632     Expanded.BraceWrapping.AfterClass = true;
633     Expanded.BraceWrapping.AfterEnum = true;
634     Expanded.BraceWrapping.AfterFunction = true;
635     Expanded.BraceWrapping.AfterStruct = true;
636     Expanded.BraceWrapping.AfterUnion = true;
637     Expanded.BraceWrapping.AfterExternBlock = true;
638     Expanded.BraceWrapping.SplitEmptyFunction = true;
639     Expanded.BraceWrapping.SplitEmptyRecord = false;
640     break;
641   case FormatStyle::BS_Stroustrup:
642     Expanded.BraceWrapping.AfterFunction = true;
643     Expanded.BraceWrapping.BeforeCatch = true;
644     Expanded.BraceWrapping.BeforeElse = true;
645     break;
646   case FormatStyle::BS_Allman:
647     Expanded.BraceWrapping.AfterCaseLabel = true;
648     Expanded.BraceWrapping.AfterClass = true;
649     Expanded.BraceWrapping.AfterControlStatement = true;
650     Expanded.BraceWrapping.AfterEnum = true;
651     Expanded.BraceWrapping.AfterFunction = true;
652     Expanded.BraceWrapping.AfterNamespace = true;
653     Expanded.BraceWrapping.AfterObjCDeclaration = true;
654     Expanded.BraceWrapping.AfterStruct = true;
655     Expanded.BraceWrapping.AfterUnion = true;
656     Expanded.BraceWrapping.AfterExternBlock = true;
657     Expanded.BraceWrapping.BeforeCatch = true;
658     Expanded.BraceWrapping.BeforeElse = true;
659     break;
660   case FormatStyle::BS_GNU:
661     Expanded.BraceWrapping = {true, true, true, true, true, true, true, true,
662                               true, true, true, true, true, true, true, true};
663     break;
664   case FormatStyle::BS_WebKit:
665     Expanded.BraceWrapping.AfterFunction = true;
666     break;
667   default:
668     break;
669   }
670   return Expanded;
671 }
672 
673 FormatStyle getLLVMStyle(FormatStyle::LanguageKind Language) {
674   FormatStyle LLVMStyle;
675   LLVMStyle.Language = Language;
676   LLVMStyle.AccessModifierOffset = -2;
677   LLVMStyle.AlignEscapedNewlines = FormatStyle::ENAS_Right;
678   LLVMStyle.AlignAfterOpenBracket = FormatStyle::BAS_Align;
679   LLVMStyle.AlignOperands = true;
680   LLVMStyle.AlignTrailingComments = true;
681   LLVMStyle.AlignConsecutiveAssignments = false;
682   LLVMStyle.AlignConsecutiveDeclarations = false;
683   LLVMStyle.AlignConsecutiveMacros = false;
684   LLVMStyle.AllowAllArgumentsOnNextLine = true;
685   LLVMStyle.AllowAllConstructorInitializersOnNextLine = true;
686   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
687   LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
688   LLVMStyle.AllowShortBlocksOnASingleLine = FormatStyle::SBS_Never;
689   LLVMStyle.AllowShortCaseLabelsOnASingleLine = false;
690   LLVMStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
691   LLVMStyle.AllowShortLambdasOnASingleLine = FormatStyle::SLS_All;
692   LLVMStyle.AllowShortLoopsOnASingleLine = false;
693   LLVMStyle.AlwaysBreakAfterReturnType = FormatStyle::RTBS_None;
694   LLVMStyle.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_None;
695   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
696   LLVMStyle.AlwaysBreakTemplateDeclarations = FormatStyle::BTDS_MultiLine;
697   LLVMStyle.BinPackArguments = true;
698   LLVMStyle.BinPackParameters = true;
699   LLVMStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_None;
700   LLVMStyle.BreakBeforeTernaryOperators = true;
701   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
702   LLVMStyle.BraceWrapping = {false, false, false, false, false, false,
703                              false, false, false, false, false, false,
704                              false, true,  true,  true};
705   LLVMStyle.BreakAfterJavaFieldAnnotations = false;
706   LLVMStyle.BreakConstructorInitializers = FormatStyle::BCIS_BeforeColon;
707   LLVMStyle.BreakInheritanceList = FormatStyle::BILS_BeforeColon;
708   LLVMStyle.BreakStringLiterals = true;
709   LLVMStyle.ColumnLimit = 80;
710   LLVMStyle.CommentPragmas = "^ IWYU pragma:";
711   LLVMStyle.CompactNamespaces = false;
712   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
713   LLVMStyle.ConstructorInitializerIndentWidth = 4;
714   LLVMStyle.ContinuationIndentWidth = 4;
715   LLVMStyle.Cpp11BracedListStyle = true;
716   LLVMStyle.DerivePointerAlignment = false;
717   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
718   LLVMStyle.FixNamespaceComments = true;
719   LLVMStyle.ForEachMacros.push_back("foreach");
720   LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
721   LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
722   LLVMStyle.IncludeStyle.IncludeCategories = {
723       {"^\"(llvm|llvm-c|clang|clang-c)/", 2},
724       {"^(<|\"(gtest|gmock|isl|json)/)", 3},
725       {".*", 1}};
726   LLVMStyle.IncludeStyle.IncludeIsMainRegex = "(Test)?$";
727   LLVMStyle.IncludeStyle.IncludeBlocks = tooling::IncludeStyle::IBS_Preserve;
728   LLVMStyle.IndentCaseLabels = false;
729   LLVMStyle.IndentGotoLabels = true;
730   LLVMStyle.IndentPPDirectives = FormatStyle::PPDIS_None;
731   LLVMStyle.IndentWrappedFunctionNames = false;
732   LLVMStyle.IndentWidth = 2;
733   LLVMStyle.JavaScriptQuotes = FormatStyle::JSQS_Leave;
734   LLVMStyle.JavaScriptWrapImports = true;
735   LLVMStyle.TabWidth = 8;
736   LLVMStyle.MaxEmptyLinesToKeep = 1;
737   LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
738   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
739   LLVMStyle.ObjCBinPackProtocolList = FormatStyle::BPS_Auto;
740   LLVMStyle.ObjCBlockIndentWidth = 2;
741   LLVMStyle.ObjCSpaceAfterProperty = false;
742   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
743   LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
744   LLVMStyle.SpacesBeforeTrailingComments = 1;
745   LLVMStyle.Standard = FormatStyle::LS_Cpp11;
746   LLVMStyle.UseTab = FormatStyle::UT_Never;
747   LLVMStyle.ReflowComments = true;
748   LLVMStyle.SpacesInParentheses = false;
749   LLVMStyle.SpacesInSquareBrackets = false;
750   LLVMStyle.SpaceInEmptyBlock = false;
751   LLVMStyle.SpaceInEmptyParentheses = false;
752   LLVMStyle.SpacesInContainerLiterals = true;
753   LLVMStyle.SpacesInCStyleCastParentheses = false;
754   LLVMStyle.SpaceAfterCStyleCast = false;
755   LLVMStyle.SpaceAfterLogicalNot = false;
756   LLVMStyle.SpaceAfterTemplateKeyword = true;
757   LLVMStyle.SpaceBeforeCtorInitializerColon = true;
758   LLVMStyle.SpaceBeforeInheritanceColon = true;
759   LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
760   LLVMStyle.SpaceBeforeRangeBasedForLoopColon = true;
761   LLVMStyle.SpaceBeforeAssignmentOperators = true;
762   LLVMStyle.SpaceBeforeCpp11BracedList = false;
763   LLVMStyle.SpacesInAngles = false;
764 
765   LLVMStyle.PenaltyBreakAssignment = prec::Assignment;
766   LLVMStyle.PenaltyBreakComment = 300;
767   LLVMStyle.PenaltyBreakFirstLessLess = 120;
768   LLVMStyle.PenaltyBreakString = 1000;
769   LLVMStyle.PenaltyExcessCharacter = 1000000;
770   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
771   LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
772   LLVMStyle.PenaltyBreakTemplateDeclaration = prec::Relational;
773 
774   LLVMStyle.DisableFormat = false;
775   LLVMStyle.SortIncludes = true;
776   LLVMStyle.SortUsingDeclarations = true;
777   LLVMStyle.StatementMacros.push_back("Q_UNUSED");
778   LLVMStyle.StatementMacros.push_back("QT_REQUIRE_VERSION");
779 
780   // Defaults that differ when not C++.
781   if (Language == FormatStyle::LK_TableGen) {
782     LLVMStyle.SpacesInContainerLiterals = false;
783   }
784 
785   return LLVMStyle;
786 }
787 
788 FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
789   if (Language == FormatStyle::LK_TextProto) {
790     FormatStyle GoogleStyle = getGoogleStyle(FormatStyle::LK_Proto);
791     GoogleStyle.Language = FormatStyle::LK_TextProto;
792 
793     return GoogleStyle;
794   }
795 
796   FormatStyle GoogleStyle = getLLVMStyle(Language);
797 
798   GoogleStyle.AccessModifierOffset = -1;
799   GoogleStyle.AlignEscapedNewlines = FormatStyle::ENAS_Left;
800   GoogleStyle.AllowShortIfStatementsOnASingleLine =
801       FormatStyle::SIS_WithoutElse;
802   GoogleStyle.AllowShortLoopsOnASingleLine = true;
803   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
804   GoogleStyle.AlwaysBreakTemplateDeclarations = FormatStyle::BTDS_Yes;
805   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
806   GoogleStyle.DerivePointerAlignment = true;
807   GoogleStyle.IncludeStyle.IncludeCategories = {
808       {"^<ext/.*\\.h>", 2}, {"^<.*\\.h>", 1}, {"^<.*", 2}, {".*", 3}};
809   GoogleStyle.IncludeStyle.IncludeIsMainRegex = "([-_](test|unittest))?$";
810   GoogleStyle.IncludeStyle.IncludeBlocks = tooling::IncludeStyle::IBS_Regroup;
811   GoogleStyle.IndentCaseLabels = true;
812   GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
813   GoogleStyle.ObjCBinPackProtocolList = FormatStyle::BPS_Never;
814   GoogleStyle.ObjCSpaceAfterProperty = false;
815   GoogleStyle.ObjCSpaceBeforeProtocolList = true;
816   GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
817   GoogleStyle.RawStringFormats = {
818       {
819           FormatStyle::LK_Cpp,
820           /*Delimiters=*/
821           {
822               "cc",
823               "CC",
824               "cpp",
825               "Cpp",
826               "CPP",
827               "c++",
828               "C++",
829           },
830           /*EnclosingFunctionNames=*/
831           {},
832           /*CanonicalDelimiter=*/"",
833           /*BasedOnStyle=*/"google",
834       },
835       {
836           FormatStyle::LK_TextProto,
837           /*Delimiters=*/
838           {
839               "pb",
840               "PB",
841               "proto",
842               "PROTO",
843           },
844           /*EnclosingFunctionNames=*/
845           {
846               "EqualsProto",
847               "EquivToProto",
848               "PARSE_PARTIAL_TEXT_PROTO",
849               "PARSE_TEST_PROTO",
850               "PARSE_TEXT_PROTO",
851               "ParseTextOrDie",
852               "ParseTextProtoOrDie",
853           },
854           /*CanonicalDelimiter=*/"",
855           /*BasedOnStyle=*/"google",
856       },
857   };
858   GoogleStyle.SpacesBeforeTrailingComments = 2;
859   GoogleStyle.Standard = FormatStyle::LS_Auto;
860 
861   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
862   GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
863 
864   if (Language == FormatStyle::LK_Java) {
865     GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
866     GoogleStyle.AlignOperands = false;
867     GoogleStyle.AlignTrailingComments = false;
868     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
869     GoogleStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
870     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
871     GoogleStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_NonAssignment;
872     GoogleStyle.ColumnLimit = 100;
873     GoogleStyle.SpaceAfterCStyleCast = true;
874     GoogleStyle.SpacesBeforeTrailingComments = 1;
875   } else if (Language == FormatStyle::LK_JavaScript) {
876     GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_AlwaysBreak;
877     GoogleStyle.AlignOperands = false;
878     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
879     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
880     GoogleStyle.BreakBeforeTernaryOperators = false;
881     // taze:, triple slash directives (`/// <...`), @see, which is commonly
882     // followed by overlong URLs.
883     GoogleStyle.CommentPragmas = "(taze:|^/[ \t]*<|@see)";
884     GoogleStyle.MaxEmptyLinesToKeep = 3;
885     GoogleStyle.NamespaceIndentation = FormatStyle::NI_All;
886     GoogleStyle.SpacesInContainerLiterals = false;
887     GoogleStyle.JavaScriptQuotes = FormatStyle::JSQS_Single;
888     GoogleStyle.JavaScriptWrapImports = false;
889   } else if (Language == FormatStyle::LK_Proto) {
890     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
891     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
892     GoogleStyle.SpacesInContainerLiterals = false;
893     GoogleStyle.Cpp11BracedListStyle = false;
894     // This affects protocol buffer options specifications and text protos.
895     // Text protos are currently mostly formatted inside C++ raw string literals
896     // and often the current breaking behavior of string literals is not
897     // beneficial there. Investigate turning this on once proper string reflow
898     // has been implemented.
899     GoogleStyle.BreakStringLiterals = false;
900   } else if (Language == FormatStyle::LK_ObjC) {
901     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
902     GoogleStyle.ColumnLimit = 100;
903     // "Regroup" doesn't work well for ObjC yet (main header heuristic,
904     // relationship between ObjC standard library headers and other heades,
905     // #imports, etc.)
906     GoogleStyle.IncludeStyle.IncludeBlocks =
907         tooling::IncludeStyle::IBS_Preserve;
908   }
909 
910   return GoogleStyle;
911 }
912 
913 FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
914   FormatStyle ChromiumStyle = getGoogleStyle(Language);
915 
916   // Disable include reordering across blocks in Chromium code.
917   // - clang-format tries to detect that foo.h is the "main" header for
918   //   foo.cc and foo_unittest.cc via IncludeIsMainRegex. However, Chromium
919   //   uses many other suffices (_win.cc, _mac.mm, _posix.cc, _browsertest.cc,
920   //   _private.cc, _impl.cc etc) in different permutations
921   //   (_win_browsertest.cc) so disable this until IncludeIsMainRegex has a
922   //   better default for Chromium code.
923   // - The default for .cc and .mm files is different (r357695) for Google style
924   //   for the same reason. The plan is to unify this again once the main
925   //   header detection works for Google's ObjC code, but this hasn't happened
926   //   yet. Since Chromium has some ObjC code, switching Chromium is blocked
927   //   on that.
928   // - Finally, "If include reordering is harmful, put things in different
929   //   blocks to prevent it" has been a recommendation for a long time that
930   //   people are used to. We'll need a dev education push to change this to
931   //   "If include reordering is harmful, put things in a different block and
932   //   _prepend that with a comment_ to prevent it" before changing behavior.
933   ChromiumStyle.IncludeStyle.IncludeBlocks =
934       tooling::IncludeStyle::IBS_Preserve;
935 
936   if (Language == FormatStyle::LK_Java) {
937     ChromiumStyle.AllowShortIfStatementsOnASingleLine =
938         FormatStyle::SIS_WithoutElse;
939     ChromiumStyle.BreakAfterJavaFieldAnnotations = true;
940     ChromiumStyle.ContinuationIndentWidth = 8;
941     ChromiumStyle.IndentWidth = 4;
942     // See styleguide for import groups:
943     // https://chromium.googlesource.com/chromium/src/+/master/styleguide/java/java.md#Import-Order
944     ChromiumStyle.JavaImportGroups = {
945         "android",
946         "androidx",
947         "com",
948         "dalvik",
949         "junit",
950         "org",
951         "com.google.android.apps.chrome",
952         "org.chromium",
953         "java",
954         "javax",
955     };
956     ChromiumStyle.SortIncludes = true;
957   } else if (Language == FormatStyle::LK_JavaScript) {
958     ChromiumStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
959     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
960   } else {
961     ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
962     ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
963     ChromiumStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
964     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
965     ChromiumStyle.BinPackParameters = false;
966     ChromiumStyle.DerivePointerAlignment = false;
967     if (Language == FormatStyle::LK_ObjC)
968       ChromiumStyle.ColumnLimit = 80;
969   }
970   return ChromiumStyle;
971 }
972 
973 FormatStyle getMozillaStyle() {
974   FormatStyle MozillaStyle = getLLVMStyle();
975   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
976   MozillaStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
977   MozillaStyle.AlwaysBreakAfterReturnType = FormatStyle::RTBS_TopLevel;
978   MozillaStyle.AlwaysBreakAfterDefinitionReturnType =
979       FormatStyle::DRTBS_TopLevel;
980   MozillaStyle.AlwaysBreakTemplateDeclarations = FormatStyle::BTDS_Yes;
981   MozillaStyle.BinPackParameters = false;
982   MozillaStyle.BinPackArguments = false;
983   MozillaStyle.BreakBeforeBraces = FormatStyle::BS_Mozilla;
984   MozillaStyle.BreakConstructorInitializers = FormatStyle::BCIS_BeforeComma;
985   MozillaStyle.BreakInheritanceList = FormatStyle::BILS_BeforeComma;
986   MozillaStyle.ConstructorInitializerIndentWidth = 2;
987   MozillaStyle.ContinuationIndentWidth = 2;
988   MozillaStyle.Cpp11BracedListStyle = false;
989   MozillaStyle.FixNamespaceComments = false;
990   MozillaStyle.IndentCaseLabels = true;
991   MozillaStyle.ObjCSpaceAfterProperty = true;
992   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
993   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
994   MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
995   MozillaStyle.SpaceAfterTemplateKeyword = false;
996   return MozillaStyle;
997 }
998 
999 FormatStyle getWebKitStyle() {
1000   FormatStyle Style = getLLVMStyle();
1001   Style.AccessModifierOffset = -4;
1002   Style.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
1003   Style.AlignOperands = false;
1004   Style.AlignTrailingComments = false;
1005   Style.AllowShortBlocksOnASingleLine = FormatStyle::SBS_Empty;
1006   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
1007   Style.BreakBeforeBraces = FormatStyle::BS_WebKit;
1008   Style.BreakConstructorInitializers = FormatStyle::BCIS_BeforeComma;
1009   Style.Cpp11BracedListStyle = false;
1010   Style.ColumnLimit = 0;
1011   Style.FixNamespaceComments = false;
1012   Style.IndentWidth = 4;
1013   Style.NamespaceIndentation = FormatStyle::NI_Inner;
1014   Style.ObjCBlockIndentWidth = 4;
1015   Style.ObjCSpaceAfterProperty = true;
1016   Style.PointerAlignment = FormatStyle::PAS_Left;
1017   Style.SpaceBeforeCpp11BracedList = true;
1018   Style.SpaceInEmptyBlock = true;
1019   return Style;
1020 }
1021 
1022 FormatStyle getGNUStyle() {
1023   FormatStyle Style = getLLVMStyle();
1024   Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_All;
1025   Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
1026   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
1027   Style.BreakBeforeBraces = FormatStyle::BS_GNU;
1028   Style.BreakBeforeTernaryOperators = true;
1029   Style.Cpp11BracedListStyle = false;
1030   Style.ColumnLimit = 79;
1031   Style.FixNamespaceComments = false;
1032   Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
1033   Style.Standard = FormatStyle::LS_Cpp03;
1034   return Style;
1035 }
1036 
1037 FormatStyle getMicrosoftStyle(FormatStyle::LanguageKind Language) {
1038   FormatStyle Style = getLLVMStyle();
1039   Style.ColumnLimit = 120;
1040   Style.TabWidth = 4;
1041   Style.IndentWidth = 4;
1042   Style.UseTab = FormatStyle::UT_Never;
1043   Style.BreakBeforeBraces = FormatStyle::BS_Custom;
1044   Style.BraceWrapping.AfterClass = true;
1045   Style.BraceWrapping.AfterControlStatement = true;
1046   Style.BraceWrapping.AfterEnum = true;
1047   Style.BraceWrapping.AfterFunction = true;
1048   Style.BraceWrapping.AfterNamespace = true;
1049   Style.BraceWrapping.AfterObjCDeclaration = true;
1050   Style.BraceWrapping.AfterStruct = true;
1051   Style.BraceWrapping.AfterExternBlock = true;
1052   Style.BraceWrapping.BeforeCatch = true;
1053   Style.BraceWrapping.BeforeElse = true;
1054   Style.PenaltyReturnTypeOnItsOwnLine = 1000;
1055   Style.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
1056   Style.AllowShortCaseLabelsOnASingleLine = false;
1057   Style.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1058   Style.AllowShortLoopsOnASingleLine = false;
1059   return Style;
1060 }
1061 
1062 FormatStyle getNoStyle() {
1063   FormatStyle NoStyle = getLLVMStyle();
1064   NoStyle.DisableFormat = true;
1065   NoStyle.SortIncludes = false;
1066   NoStyle.SortUsingDeclarations = false;
1067   return NoStyle;
1068 }
1069 
1070 bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
1071                         FormatStyle *Style) {
1072   if (Name.equals_lower("llvm")) {
1073     *Style = getLLVMStyle(Language);
1074   } else if (Name.equals_lower("chromium")) {
1075     *Style = getChromiumStyle(Language);
1076   } else if (Name.equals_lower("mozilla")) {
1077     *Style = getMozillaStyle();
1078   } else if (Name.equals_lower("google")) {
1079     *Style = getGoogleStyle(Language);
1080   } else if (Name.equals_lower("webkit")) {
1081     *Style = getWebKitStyle();
1082   } else if (Name.equals_lower("gnu")) {
1083     *Style = getGNUStyle();
1084   } else if (Name.equals_lower("microsoft")) {
1085     *Style = getMicrosoftStyle(Language);
1086   } else if (Name.equals_lower("none")) {
1087     *Style = getNoStyle();
1088   } else {
1089     return false;
1090   }
1091 
1092   Style->Language = Language;
1093   return true;
1094 }
1095 
1096 std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
1097   assert(Style);
1098   FormatStyle::LanguageKind Language = Style->Language;
1099   assert(Language != FormatStyle::LK_None);
1100   if (Text.trim().empty())
1101     return make_error_code(ParseError::Error);
1102   Style->StyleSet.Clear();
1103   std::vector<FormatStyle> Styles;
1104   llvm::yaml::Input Input(Text);
1105   // DocumentListTraits<vector<FormatStyle>> uses the context to get default
1106   // values for the fields, keys for which are missing from the configuration.
1107   // Mapping also uses the context to get the language to find the correct
1108   // base style.
1109   Input.setContext(Style);
1110   Input >> Styles;
1111   if (Input.error())
1112     return Input.error();
1113 
1114   for (unsigned i = 0; i < Styles.size(); ++i) {
1115     // Ensures that only the first configuration can skip the Language option.
1116     if (Styles[i].Language == FormatStyle::LK_None && i != 0)
1117       return make_error_code(ParseError::Error);
1118     // Ensure that each language is configured at most once.
1119     for (unsigned j = 0; j < i; ++j) {
1120       if (Styles[i].Language == Styles[j].Language) {
1121         LLVM_DEBUG(llvm::dbgs()
1122                    << "Duplicate languages in the config file on positions "
1123                    << j << " and " << i << "\n");
1124         return make_error_code(ParseError::Error);
1125       }
1126     }
1127   }
1128   // Look for a suitable configuration starting from the end, so we can
1129   // find the configuration for the specific language first, and the default
1130   // configuration (which can only be at slot 0) after it.
1131   FormatStyle::FormatStyleSet StyleSet;
1132   bool LanguageFound = false;
1133   for (int i = Styles.size() - 1; i >= 0; --i) {
1134     if (Styles[i].Language != FormatStyle::LK_None)
1135       StyleSet.Add(Styles[i]);
1136     if (Styles[i].Language == Language)
1137       LanguageFound = true;
1138   }
1139   if (!LanguageFound) {
1140     if (Styles.empty() || Styles[0].Language != FormatStyle::LK_None)
1141       return make_error_code(ParseError::Unsuitable);
1142     FormatStyle DefaultStyle = Styles[0];
1143     DefaultStyle.Language = Language;
1144     StyleSet.Add(std::move(DefaultStyle));
1145   }
1146   *Style = *StyleSet.Get(Language);
1147   return make_error_code(ParseError::Success);
1148 }
1149 
1150 std::string configurationAsText(const FormatStyle &Style) {
1151   std::string Text;
1152   llvm::raw_string_ostream Stream(Text);
1153   llvm::yaml::Output Output(Stream);
1154   // We use the same mapping method for input and output, so we need a non-const
1155   // reference here.
1156   FormatStyle NonConstStyle = expandPresets(Style);
1157   Output << NonConstStyle;
1158   return Stream.str();
1159 }
1160 
1161 llvm::Optional<FormatStyle>
1162 FormatStyle::FormatStyleSet::Get(FormatStyle::LanguageKind Language) const {
1163   if (!Styles)
1164     return None;
1165   auto It = Styles->find(Language);
1166   if (It == Styles->end())
1167     return None;
1168   FormatStyle Style = It->second;
1169   Style.StyleSet = *this;
1170   return Style;
1171 }
1172 
1173 void FormatStyle::FormatStyleSet::Add(FormatStyle Style) {
1174   assert(Style.Language != LK_None &&
1175          "Cannot add a style for LK_None to a StyleSet");
1176   assert(
1177       !Style.StyleSet.Styles &&
1178       "Cannot add a style associated with an existing StyleSet to a StyleSet");
1179   if (!Styles)
1180     Styles = std::make_shared<MapType>();
1181   (*Styles)[Style.Language] = std::move(Style);
1182 }
1183 
1184 void FormatStyle::FormatStyleSet::Clear() { Styles.reset(); }
1185 
1186 llvm::Optional<FormatStyle>
1187 FormatStyle::GetLanguageStyle(FormatStyle::LanguageKind Language) const {
1188   return StyleSet.Get(Language);
1189 }
1190 
1191 namespace {
1192 
1193 class JavaScriptRequoter : public TokenAnalyzer {
1194 public:
1195   JavaScriptRequoter(const Environment &Env, const FormatStyle &Style)
1196       : TokenAnalyzer(Env, Style) {}
1197 
1198   std::pair<tooling::Replacements, unsigned>
1199   analyze(TokenAnnotator &Annotator,
1200           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1201           FormatTokenLexer &Tokens) override {
1202     AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1203     tooling::Replacements Result;
1204     requoteJSStringLiteral(AnnotatedLines, Result);
1205     return {Result, 0};
1206   }
1207 
1208 private:
1209   // Replaces double/single-quoted string literal as appropriate, re-escaping
1210   // the contents in the process.
1211   void requoteJSStringLiteral(SmallVectorImpl<AnnotatedLine *> &Lines,
1212                               tooling::Replacements &Result) {
1213     for (AnnotatedLine *Line : Lines) {
1214       requoteJSStringLiteral(Line->Children, Result);
1215       if (!Line->Affected)
1216         continue;
1217       for (FormatToken *FormatTok = Line->First; FormatTok;
1218            FormatTok = FormatTok->Next) {
1219         StringRef Input = FormatTok->TokenText;
1220         if (FormatTok->Finalized || !FormatTok->isStringLiteral() ||
1221             // NB: testing for not starting with a double quote to avoid
1222             // breaking `template strings`.
1223             (Style.JavaScriptQuotes == FormatStyle::JSQS_Single &&
1224              !Input.startswith("\"")) ||
1225             (Style.JavaScriptQuotes == FormatStyle::JSQS_Double &&
1226              !Input.startswith("\'")))
1227           continue;
1228 
1229         // Change start and end quote.
1230         bool IsSingle = Style.JavaScriptQuotes == FormatStyle::JSQS_Single;
1231         SourceLocation Start = FormatTok->Tok.getLocation();
1232         auto Replace = [&](SourceLocation Start, unsigned Length,
1233                            StringRef ReplacementText) {
1234           auto Err = Result.add(tooling::Replacement(
1235               Env.getSourceManager(), Start, Length, ReplacementText));
1236           // FIXME: handle error. For now, print error message and skip the
1237           // replacement for release version.
1238           if (Err) {
1239             llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1240             assert(false);
1241           }
1242         };
1243         Replace(Start, 1, IsSingle ? "'" : "\"");
1244         Replace(FormatTok->Tok.getEndLoc().getLocWithOffset(-1), 1,
1245                 IsSingle ? "'" : "\"");
1246 
1247         // Escape internal quotes.
1248         bool Escaped = false;
1249         for (size_t i = 1; i < Input.size() - 1; i++) {
1250           switch (Input[i]) {
1251           case '\\':
1252             if (!Escaped && i + 1 < Input.size() &&
1253                 ((IsSingle && Input[i + 1] == '"') ||
1254                  (!IsSingle && Input[i + 1] == '\''))) {
1255               // Remove this \, it's escaping a " or ' that no longer needs
1256               // escaping
1257               Replace(Start.getLocWithOffset(i), 1, "");
1258               continue;
1259             }
1260             Escaped = !Escaped;
1261             break;
1262           case '\"':
1263           case '\'':
1264             if (!Escaped && IsSingle == (Input[i] == '\'')) {
1265               // Escape the quote.
1266               Replace(Start.getLocWithOffset(i), 0, "\\");
1267             }
1268             Escaped = false;
1269             break;
1270           default:
1271             Escaped = false;
1272             break;
1273           }
1274         }
1275       }
1276     }
1277   }
1278 };
1279 
1280 class Formatter : public TokenAnalyzer {
1281 public:
1282   Formatter(const Environment &Env, const FormatStyle &Style,
1283             FormattingAttemptStatus *Status)
1284       : TokenAnalyzer(Env, Style), Status(Status) {}
1285 
1286   std::pair<tooling::Replacements, unsigned>
1287   analyze(TokenAnnotator &Annotator,
1288           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1289           FormatTokenLexer &Tokens) override {
1290     tooling::Replacements Result;
1291     deriveLocalStyle(AnnotatedLines);
1292     AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1293     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1294       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1295     }
1296     Annotator.setCommentLineLevels(AnnotatedLines);
1297 
1298     WhitespaceManager Whitespaces(
1299         Env.getSourceManager(), Style,
1300         inputUsesCRLF(Env.getSourceManager().getBufferData(Env.getFileID())));
1301     ContinuationIndenter Indenter(Style, Tokens.getKeywords(),
1302                                   Env.getSourceManager(), Whitespaces, Encoding,
1303                                   BinPackInconclusiveFunctions);
1304     unsigned Penalty =
1305         UnwrappedLineFormatter(&Indenter, &Whitespaces, Style,
1306                                Tokens.getKeywords(), Env.getSourceManager(),
1307                                Status)
1308             .format(AnnotatedLines, /*DryRun=*/false,
1309                     /*AdditionalIndent=*/0,
1310                     /*FixBadIndentation=*/false,
1311                     /*FirstStartColumn=*/Env.getFirstStartColumn(),
1312                     /*NextStartColumn=*/Env.getNextStartColumn(),
1313                     /*LastStartColumn=*/Env.getLastStartColumn());
1314     for (const auto &R : Whitespaces.generateReplacements())
1315       if (Result.add(R))
1316         return std::make_pair(Result, 0);
1317     return std::make_pair(Result, Penalty);
1318   }
1319 
1320 private:
1321   static bool inputUsesCRLF(StringRef Text) {
1322     return Text.count('\r') * 2 > Text.count('\n');
1323   }
1324 
1325   bool
1326   hasCpp03IncompatibleFormat(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1327     for (const AnnotatedLine *Line : Lines) {
1328       if (hasCpp03IncompatibleFormat(Line->Children))
1329         return true;
1330       for (FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next) {
1331         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
1332           if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
1333             return true;
1334           if (Tok->is(TT_TemplateCloser) &&
1335               Tok->Previous->is(TT_TemplateCloser))
1336             return true;
1337         }
1338       }
1339     }
1340     return false;
1341   }
1342 
1343   int countVariableAlignments(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1344     int AlignmentDiff = 0;
1345     for (const AnnotatedLine *Line : Lines) {
1346       AlignmentDiff += countVariableAlignments(Line->Children);
1347       for (FormatToken *Tok = Line->First; Tok && Tok->Next; Tok = Tok->Next) {
1348         if (!Tok->is(TT_PointerOrReference))
1349           continue;
1350         bool SpaceBefore =
1351             Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1352         bool SpaceAfter = Tok->Next->WhitespaceRange.getBegin() !=
1353                           Tok->Next->WhitespaceRange.getEnd();
1354         if (SpaceBefore && !SpaceAfter)
1355           ++AlignmentDiff;
1356         if (!SpaceBefore && SpaceAfter)
1357           --AlignmentDiff;
1358       }
1359     }
1360     return AlignmentDiff;
1361   }
1362 
1363   void
1364   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1365     bool HasBinPackedFunction = false;
1366     bool HasOnePerLineFunction = false;
1367     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1368       if (!AnnotatedLines[i]->First->Next)
1369         continue;
1370       FormatToken *Tok = AnnotatedLines[i]->First->Next;
1371       while (Tok->Next) {
1372         if (Tok->PackingKind == PPK_BinPacked)
1373           HasBinPackedFunction = true;
1374         if (Tok->PackingKind == PPK_OnePerLine)
1375           HasOnePerLineFunction = true;
1376 
1377         Tok = Tok->Next;
1378       }
1379     }
1380     if (Style.DerivePointerAlignment)
1381       Style.PointerAlignment = countVariableAlignments(AnnotatedLines) <= 0
1382                                    ? FormatStyle::PAS_Left
1383                                    : FormatStyle::PAS_Right;
1384     if (Style.Standard == FormatStyle::LS_Auto)
1385       Style.Standard = hasCpp03IncompatibleFormat(AnnotatedLines)
1386                            ? FormatStyle::LS_Cpp11
1387                            : FormatStyle::LS_Cpp03;
1388     BinPackInconclusiveFunctions =
1389         HasBinPackedFunction || !HasOnePerLineFunction;
1390   }
1391 
1392   bool BinPackInconclusiveFunctions;
1393   FormattingAttemptStatus *Status;
1394 };
1395 
1396 // This class clean up the erroneous/redundant code around the given ranges in
1397 // file.
1398 class Cleaner : public TokenAnalyzer {
1399 public:
1400   Cleaner(const Environment &Env, const FormatStyle &Style)
1401       : TokenAnalyzer(Env, Style),
1402         DeletedTokens(FormatTokenLess(Env.getSourceManager())) {}
1403 
1404   // FIXME: eliminate unused parameters.
1405   std::pair<tooling::Replacements, unsigned>
1406   analyze(TokenAnnotator &Annotator,
1407           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1408           FormatTokenLexer &Tokens) override {
1409     // FIXME: in the current implementation the granularity of affected range
1410     // is an annotated line. However, this is not sufficient. Furthermore,
1411     // redundant code introduced by replacements does not necessarily
1412     // intercept with ranges of replacements that result in the redundancy.
1413     // To determine if some redundant code is actually introduced by
1414     // replacements(e.g. deletions), we need to come up with a more
1415     // sophisticated way of computing affected ranges.
1416     AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1417 
1418     checkEmptyNamespace(AnnotatedLines);
1419 
1420     for (auto *Line : AnnotatedLines)
1421       cleanupLine(Line);
1422 
1423     return {generateFixes(), 0};
1424   }
1425 
1426 private:
1427   void cleanupLine(AnnotatedLine *Line) {
1428     for (auto *Child : Line->Children) {
1429       cleanupLine(Child);
1430     }
1431 
1432     if (Line->Affected) {
1433       cleanupRight(Line->First, tok::comma, tok::comma);
1434       cleanupRight(Line->First, TT_CtorInitializerColon, tok::comma);
1435       cleanupRight(Line->First, tok::l_paren, tok::comma);
1436       cleanupLeft(Line->First, tok::comma, tok::r_paren);
1437       cleanupLeft(Line->First, TT_CtorInitializerComma, tok::l_brace);
1438       cleanupLeft(Line->First, TT_CtorInitializerColon, tok::l_brace);
1439       cleanupLeft(Line->First, TT_CtorInitializerColon, tok::equal);
1440     }
1441   }
1442 
1443   bool containsOnlyComments(const AnnotatedLine &Line) {
1444     for (FormatToken *Tok = Line.First; Tok != nullptr; Tok = Tok->Next) {
1445       if (Tok->isNot(tok::comment))
1446         return false;
1447     }
1448     return true;
1449   }
1450 
1451   // Iterate through all lines and remove any empty (nested) namespaces.
1452   void checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1453     std::set<unsigned> DeletedLines;
1454     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1455       auto &Line = *AnnotatedLines[i];
1456       if (Line.startsWithNamespace()) {
1457         checkEmptyNamespace(AnnotatedLines, i, i, DeletedLines);
1458       }
1459     }
1460 
1461     for (auto Line : DeletedLines) {
1462       FormatToken *Tok = AnnotatedLines[Line]->First;
1463       while (Tok) {
1464         deleteToken(Tok);
1465         Tok = Tok->Next;
1466       }
1467     }
1468   }
1469 
1470   // The function checks if the namespace, which starts from \p CurrentLine, and
1471   // its nested namespaces are empty and delete them if they are empty. It also
1472   // sets \p NewLine to the last line checked.
1473   // Returns true if the current namespace is empty.
1474   bool checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1475                            unsigned CurrentLine, unsigned &NewLine,
1476                            std::set<unsigned> &DeletedLines) {
1477     unsigned InitLine = CurrentLine, End = AnnotatedLines.size();
1478     if (Style.BraceWrapping.AfterNamespace) {
1479       // If the left brace is in a new line, we should consume it first so that
1480       // it does not make the namespace non-empty.
1481       // FIXME: error handling if there is no left brace.
1482       if (!AnnotatedLines[++CurrentLine]->startsWith(tok::l_brace)) {
1483         NewLine = CurrentLine;
1484         return false;
1485       }
1486     } else if (!AnnotatedLines[CurrentLine]->endsWith(tok::l_brace)) {
1487       return false;
1488     }
1489     while (++CurrentLine < End) {
1490       if (AnnotatedLines[CurrentLine]->startsWith(tok::r_brace))
1491         break;
1492 
1493       if (AnnotatedLines[CurrentLine]->startsWithNamespace()) {
1494         if (!checkEmptyNamespace(AnnotatedLines, CurrentLine, NewLine,
1495                                  DeletedLines))
1496           return false;
1497         CurrentLine = NewLine;
1498         continue;
1499       }
1500 
1501       if (containsOnlyComments(*AnnotatedLines[CurrentLine]))
1502         continue;
1503 
1504       // If there is anything other than comments or nested namespaces in the
1505       // current namespace, the namespace cannot be empty.
1506       NewLine = CurrentLine;
1507       return false;
1508     }
1509 
1510     NewLine = CurrentLine;
1511     if (CurrentLine >= End)
1512       return false;
1513 
1514     // Check if the empty namespace is actually affected by changed ranges.
1515     if (!AffectedRangeMgr.affectsCharSourceRange(CharSourceRange::getCharRange(
1516             AnnotatedLines[InitLine]->First->Tok.getLocation(),
1517             AnnotatedLines[CurrentLine]->Last->Tok.getEndLoc())))
1518       return false;
1519 
1520     for (unsigned i = InitLine; i <= CurrentLine; ++i) {
1521       DeletedLines.insert(i);
1522     }
1523 
1524     return true;
1525   }
1526 
1527   // Checks pairs {start, start->next},..., {end->previous, end} and deletes one
1528   // of the token in the pair if the left token has \p LK token kind and the
1529   // right token has \p RK token kind. If \p DeleteLeft is true, the left token
1530   // is deleted on match; otherwise, the right token is deleted.
1531   template <typename LeftKind, typename RightKind>
1532   void cleanupPair(FormatToken *Start, LeftKind LK, RightKind RK,
1533                    bool DeleteLeft) {
1534     auto NextNotDeleted = [this](const FormatToken &Tok) -> FormatToken * {
1535       for (auto *Res = Tok.Next; Res; Res = Res->Next)
1536         if (!Res->is(tok::comment) &&
1537             DeletedTokens.find(Res) == DeletedTokens.end())
1538           return Res;
1539       return nullptr;
1540     };
1541     for (auto *Left = Start; Left;) {
1542       auto *Right = NextNotDeleted(*Left);
1543       if (!Right)
1544         break;
1545       if (Left->is(LK) && Right->is(RK)) {
1546         deleteToken(DeleteLeft ? Left : Right);
1547         for (auto *Tok = Left->Next; Tok && Tok != Right; Tok = Tok->Next)
1548           deleteToken(Tok);
1549         // If the right token is deleted, we should keep the left token
1550         // unchanged and pair it with the new right token.
1551         if (!DeleteLeft)
1552           continue;
1553       }
1554       Left = Right;
1555     }
1556   }
1557 
1558   template <typename LeftKind, typename RightKind>
1559   void cleanupLeft(FormatToken *Start, LeftKind LK, RightKind RK) {
1560     cleanupPair(Start, LK, RK, /*DeleteLeft=*/true);
1561   }
1562 
1563   template <typename LeftKind, typename RightKind>
1564   void cleanupRight(FormatToken *Start, LeftKind LK, RightKind RK) {
1565     cleanupPair(Start, LK, RK, /*DeleteLeft=*/false);
1566   }
1567 
1568   // Delete the given token.
1569   inline void deleteToken(FormatToken *Tok) {
1570     if (Tok)
1571       DeletedTokens.insert(Tok);
1572   }
1573 
1574   tooling::Replacements generateFixes() {
1575     tooling::Replacements Fixes;
1576     std::vector<FormatToken *> Tokens;
1577     std::copy(DeletedTokens.begin(), DeletedTokens.end(),
1578               std::back_inserter(Tokens));
1579 
1580     // Merge multiple continuous token deletions into one big deletion so that
1581     // the number of replacements can be reduced. This makes computing affected
1582     // ranges more efficient when we run reformat on the changed code.
1583     unsigned Idx = 0;
1584     while (Idx < Tokens.size()) {
1585       unsigned St = Idx, End = Idx;
1586       while ((End + 1) < Tokens.size() &&
1587              Tokens[End]->Next == Tokens[End + 1]) {
1588         End++;
1589       }
1590       auto SR = CharSourceRange::getCharRange(Tokens[St]->Tok.getLocation(),
1591                                               Tokens[End]->Tok.getEndLoc());
1592       auto Err =
1593           Fixes.add(tooling::Replacement(Env.getSourceManager(), SR, ""));
1594       // FIXME: better error handling. for now just print error message and skip
1595       // for the release version.
1596       if (Err) {
1597         llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1598         assert(false && "Fixes must not conflict!");
1599       }
1600       Idx = End + 1;
1601     }
1602 
1603     return Fixes;
1604   }
1605 
1606   // Class for less-than inequality comparason for the set `RedundantTokens`.
1607   // We store tokens in the order they appear in the translation unit so that
1608   // we do not need to sort them in `generateFixes()`.
1609   struct FormatTokenLess {
1610     FormatTokenLess(const SourceManager &SM) : SM(SM) {}
1611 
1612     bool operator()(const FormatToken *LHS, const FormatToken *RHS) const {
1613       return SM.isBeforeInTranslationUnit(LHS->Tok.getLocation(),
1614                                           RHS->Tok.getLocation());
1615     }
1616     const SourceManager &SM;
1617   };
1618 
1619   // Tokens to be deleted.
1620   std::set<FormatToken *, FormatTokenLess> DeletedTokens;
1621 };
1622 
1623 class ObjCHeaderStyleGuesser : public TokenAnalyzer {
1624 public:
1625   ObjCHeaderStyleGuesser(const Environment &Env, const FormatStyle &Style)
1626       : TokenAnalyzer(Env, Style), IsObjC(false) {}
1627 
1628   std::pair<tooling::Replacements, unsigned>
1629   analyze(TokenAnnotator &Annotator,
1630           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1631           FormatTokenLexer &Tokens) override {
1632     assert(Style.Language == FormatStyle::LK_Cpp);
1633     IsObjC = guessIsObjC(Env.getSourceManager(), AnnotatedLines,
1634                          Tokens.getKeywords());
1635     tooling::Replacements Result;
1636     return {Result, 0};
1637   }
1638 
1639   bool isObjC() { return IsObjC; }
1640 
1641 private:
1642   static bool
1643   guessIsObjC(const SourceManager &SourceManager,
1644               const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1645               const AdditionalKeywords &Keywords) {
1646     // Keep this array sorted, since we are binary searching over it.
1647     static constexpr llvm::StringLiteral FoundationIdentifiers[] = {
1648         "CGFloat",
1649         "CGPoint",
1650         "CGPointMake",
1651         "CGPointZero",
1652         "CGRect",
1653         "CGRectEdge",
1654         "CGRectInfinite",
1655         "CGRectMake",
1656         "CGRectNull",
1657         "CGRectZero",
1658         "CGSize",
1659         "CGSizeMake",
1660         "CGVector",
1661         "CGVectorMake",
1662         "NSAffineTransform",
1663         "NSArray",
1664         "NSAttributedString",
1665         "NSBlockOperation",
1666         "NSBundle",
1667         "NSCache",
1668         "NSCalendar",
1669         "NSCharacterSet",
1670         "NSCountedSet",
1671         "NSData",
1672         "NSDataDetector",
1673         "NSDecimal",
1674         "NSDecimalNumber",
1675         "NSDictionary",
1676         "NSEdgeInsets",
1677         "NSHashTable",
1678         "NSIndexPath",
1679         "NSIndexSet",
1680         "NSInteger",
1681         "NSInvocationOperation",
1682         "NSLocale",
1683         "NSMapTable",
1684         "NSMutableArray",
1685         "NSMutableAttributedString",
1686         "NSMutableCharacterSet",
1687         "NSMutableData",
1688         "NSMutableDictionary",
1689         "NSMutableIndexSet",
1690         "NSMutableOrderedSet",
1691         "NSMutableSet",
1692         "NSMutableString",
1693         "NSNumber",
1694         "NSNumberFormatter",
1695         "NSObject",
1696         "NSOperation",
1697         "NSOperationQueue",
1698         "NSOperationQueuePriority",
1699         "NSOrderedSet",
1700         "NSPoint",
1701         "NSPointerArray",
1702         "NSQualityOfService",
1703         "NSRange",
1704         "NSRect",
1705         "NSRegularExpression",
1706         "NSSet",
1707         "NSSize",
1708         "NSString",
1709         "NSTimeZone",
1710         "NSUInteger",
1711         "NSURL",
1712         "NSURLComponents",
1713         "NSURLQueryItem",
1714         "NSUUID",
1715         "NSValue",
1716         "UIImage",
1717         "UIView",
1718     };
1719 
1720     for (auto Line : AnnotatedLines) {
1721       for (const FormatToken *FormatTok = Line->First; FormatTok;
1722            FormatTok = FormatTok->Next) {
1723         if ((FormatTok->Previous && FormatTok->Previous->is(tok::at) &&
1724              (FormatTok->Tok.getObjCKeywordID() != tok::objc_not_keyword ||
1725               FormatTok->isOneOf(tok::numeric_constant, tok::l_square,
1726                                  tok::l_brace))) ||
1727             (FormatTok->Tok.isAnyIdentifier() &&
1728              std::binary_search(std::begin(FoundationIdentifiers),
1729                                 std::end(FoundationIdentifiers),
1730                                 FormatTok->TokenText)) ||
1731             FormatTok->is(TT_ObjCStringLiteral) ||
1732             FormatTok->isOneOf(Keywords.kw_NS_CLOSED_ENUM, Keywords.kw_NS_ENUM,
1733                                Keywords.kw_NS_OPTIONS, TT_ObjCBlockLBrace,
1734                                TT_ObjCBlockLParen, TT_ObjCDecl, TT_ObjCForIn,
1735                                TT_ObjCMethodExpr, TT_ObjCMethodSpecifier,
1736                                TT_ObjCProperty)) {
1737           LLVM_DEBUG(llvm::dbgs()
1738                      << "Detected ObjC at location "
1739                      << FormatTok->Tok.getLocation().printToString(
1740                             SourceManager)
1741                      << " token: " << FormatTok->TokenText << " token type: "
1742                      << getTokenTypeName(FormatTok->Type) << "\n");
1743           return true;
1744         }
1745         if (guessIsObjC(SourceManager, Line->Children, Keywords))
1746           return true;
1747       }
1748     }
1749     return false;
1750   }
1751 
1752   bool IsObjC;
1753 };
1754 
1755 struct IncludeDirective {
1756   StringRef Filename;
1757   StringRef Text;
1758   unsigned Offset;
1759   int Category;
1760 };
1761 
1762 struct JavaImportDirective {
1763   StringRef Identifier;
1764   StringRef Text;
1765   unsigned Offset;
1766   std::vector<StringRef> AssociatedCommentLines;
1767   bool IsStatic;
1768 };
1769 
1770 } // end anonymous namespace
1771 
1772 // Determines whether 'Ranges' intersects with ('Start', 'End').
1773 static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
1774                          unsigned End) {
1775   for (auto Range : Ranges) {
1776     if (Range.getOffset() < End &&
1777         Range.getOffset() + Range.getLength() > Start)
1778       return true;
1779   }
1780   return false;
1781 }
1782 
1783 // Returns a pair (Index, OffsetToEOL) describing the position of the cursor
1784 // before sorting/deduplicating. Index is the index of the include under the
1785 // cursor in the original set of includes. If this include has duplicates, it is
1786 // the index of the first of the duplicates as the others are going to be
1787 // removed. OffsetToEOL describes the cursor's position relative to the end of
1788 // its current line.
1789 // If `Cursor` is not on any #include, `Index` will be UINT_MAX.
1790 static std::pair<unsigned, unsigned>
1791 FindCursorIndex(const SmallVectorImpl<IncludeDirective> &Includes,
1792                 const SmallVectorImpl<unsigned> &Indices, unsigned Cursor) {
1793   unsigned CursorIndex = UINT_MAX;
1794   unsigned OffsetToEOL = 0;
1795   for (int i = 0, e = Includes.size(); i != e; ++i) {
1796     unsigned Start = Includes[Indices[i]].Offset;
1797     unsigned End = Start + Includes[Indices[i]].Text.size();
1798     if (!(Cursor >= Start && Cursor < End))
1799       continue;
1800     CursorIndex = Indices[i];
1801     OffsetToEOL = End - Cursor;
1802     // Put the cursor on the only remaining #include among the duplicate
1803     // #includes.
1804     while (--i >= 0 && Includes[CursorIndex].Text == Includes[Indices[i]].Text)
1805       CursorIndex = i;
1806     break;
1807   }
1808   return std::make_pair(CursorIndex, OffsetToEOL);
1809 }
1810 
1811 // Sorts and deduplicate a block of includes given by 'Includes' alphabetically
1812 // adding the necessary replacement to 'Replaces'. 'Includes' must be in strict
1813 // source order.
1814 // #include directives with the same text will be deduplicated, and only the
1815 // first #include in the duplicate #includes remains. If the `Cursor` is
1816 // provided and put on a deleted #include, it will be moved to the remaining
1817 // #include in the duplicate #includes.
1818 static void sortCppIncludes(const FormatStyle &Style,
1819                             const SmallVectorImpl<IncludeDirective> &Includes,
1820                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
1821                             StringRef Code, tooling::Replacements &Replaces,
1822                             unsigned *Cursor) {
1823   unsigned IncludesBeginOffset = Includes.front().Offset;
1824   unsigned IncludesEndOffset =
1825       Includes.back().Offset + Includes.back().Text.size();
1826   unsigned IncludesBlockSize = IncludesEndOffset - IncludesBeginOffset;
1827   if (!affectsRange(Ranges, IncludesBeginOffset, IncludesEndOffset))
1828     return;
1829   SmallVector<unsigned, 16> Indices;
1830   for (unsigned i = 0, e = Includes.size(); i != e; ++i)
1831     Indices.push_back(i);
1832   llvm::stable_sort(Indices, [&](unsigned LHSI, unsigned RHSI) {
1833     return std::tie(Includes[LHSI].Category, Includes[LHSI].Filename) <
1834            std::tie(Includes[RHSI].Category, Includes[RHSI].Filename);
1835   });
1836   // The index of the include on which the cursor will be put after
1837   // sorting/deduplicating.
1838   unsigned CursorIndex;
1839   // The offset from cursor to the end of line.
1840   unsigned CursorToEOLOffset;
1841   if (Cursor)
1842     std::tie(CursorIndex, CursorToEOLOffset) =
1843         FindCursorIndex(Includes, Indices, *Cursor);
1844 
1845   // Deduplicate #includes.
1846   Indices.erase(std::unique(Indices.begin(), Indices.end(),
1847                             [&](unsigned LHSI, unsigned RHSI) {
1848                               return Includes[LHSI].Text == Includes[RHSI].Text;
1849                             }),
1850                 Indices.end());
1851 
1852   int CurrentCategory = Includes.front().Category;
1853 
1854   // If the #includes are out of order, we generate a single replacement fixing
1855   // the entire block. Otherwise, no replacement is generated.
1856   // In case Style.IncldueStyle.IncludeBlocks != IBS_Preserve, this check is not
1857   // enough as additional newlines might be added or removed across #include
1858   // blocks. This we handle below by generating the updated #imclude blocks and
1859   // comparing it to the original.
1860   if (Indices.size() == Includes.size() &&
1861       std::is_sorted(Indices.begin(), Indices.end()) &&
1862       Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Preserve)
1863     return;
1864 
1865   std::string result;
1866   for (unsigned Index : Indices) {
1867     if (!result.empty()) {
1868       result += "\n";
1869       if (Style.IncludeStyle.IncludeBlocks ==
1870               tooling::IncludeStyle::IBS_Regroup &&
1871           CurrentCategory != Includes[Index].Category)
1872         result += "\n";
1873     }
1874     result += Includes[Index].Text;
1875     if (Cursor && CursorIndex == Index)
1876       *Cursor = IncludesBeginOffset + result.size() - CursorToEOLOffset;
1877     CurrentCategory = Includes[Index].Category;
1878   }
1879 
1880   // If the #includes are out of order, we generate a single replacement fixing
1881   // the entire range of blocks. Otherwise, no replacement is generated.
1882   if (result == Code.substr(IncludesBeginOffset, IncludesBlockSize))
1883     return;
1884 
1885   auto Err = Replaces.add(tooling::Replacement(
1886       FileName, Includes.front().Offset, IncludesBlockSize, result));
1887   // FIXME: better error handling. For now, just skip the replacement for the
1888   // release version.
1889   if (Err) {
1890     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1891     assert(false);
1892   }
1893 }
1894 
1895 namespace {
1896 
1897 const char CppIncludeRegexPattern[] =
1898     R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
1899 
1900 } // anonymous namespace
1901 
1902 tooling::Replacements sortCppIncludes(const FormatStyle &Style, StringRef Code,
1903                                       ArrayRef<tooling::Range> Ranges,
1904                                       StringRef FileName,
1905                                       tooling::Replacements &Replaces,
1906                                       unsigned *Cursor) {
1907   unsigned Prev = 0;
1908   unsigned SearchFrom = 0;
1909   llvm::Regex IncludeRegex(CppIncludeRegexPattern);
1910   SmallVector<StringRef, 4> Matches;
1911   SmallVector<IncludeDirective, 16> IncludesInBlock;
1912 
1913   // In compiled files, consider the first #include to be the main #include of
1914   // the file if it is not a system #include. This ensures that the header
1915   // doesn't have hidden dependencies
1916   // (http://llvm.org/docs/CodingStandards.html#include-style).
1917   //
1918   // FIXME: Do some sanity checking, e.g. edit distance of the base name, to fix
1919   // cases where the first #include is unlikely to be the main header.
1920   tooling::IncludeCategoryManager Categories(Style.IncludeStyle, FileName);
1921   bool FirstIncludeBlock = true;
1922   bool MainIncludeFound = false;
1923   bool FormattingOff = false;
1924 
1925   for (;;) {
1926     auto Pos = Code.find('\n', SearchFrom);
1927     StringRef Line =
1928         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
1929 
1930     StringRef Trimmed = Line.trim();
1931     if (Trimmed == "// clang-format off" || Trimmed == "/* clang-format off */")
1932       FormattingOff = true;
1933     else if (Trimmed == "// clang-format on" ||
1934              Trimmed == "/* clang-format on */")
1935       FormattingOff = false;
1936 
1937     const bool EmptyLineSkipped =
1938         Trimmed.empty() &&
1939         (Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Merge ||
1940          Style.IncludeStyle.IncludeBlocks ==
1941              tooling::IncludeStyle::IBS_Regroup);
1942 
1943     if (!FormattingOff && !Line.endswith("\\")) {
1944       if (IncludeRegex.match(Line, &Matches)) {
1945         StringRef IncludeName = Matches[2];
1946         int Category = Categories.getIncludePriority(
1947             IncludeName,
1948             /*CheckMainHeader=*/!MainIncludeFound && FirstIncludeBlock);
1949         if (Category == 0)
1950           MainIncludeFound = true;
1951         IncludesInBlock.push_back({IncludeName, Line, Prev, Category});
1952       } else if (!IncludesInBlock.empty() && !EmptyLineSkipped) {
1953         sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code,
1954                         Replaces, Cursor);
1955         IncludesInBlock.clear();
1956         FirstIncludeBlock = false;
1957       }
1958       Prev = Pos + 1;
1959     }
1960     if (Pos == StringRef::npos || Pos + 1 == Code.size())
1961       break;
1962     SearchFrom = Pos + 1;
1963   }
1964   if (!IncludesInBlock.empty()) {
1965     sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code, Replaces,
1966                     Cursor);
1967   }
1968   return Replaces;
1969 }
1970 
1971 // Returns group number to use as a first order sort on imports. Gives UINT_MAX
1972 // if the import does not match any given groups.
1973 static unsigned findJavaImportGroup(const FormatStyle &Style,
1974                                     StringRef ImportIdentifier) {
1975   unsigned LongestMatchIndex = UINT_MAX;
1976   unsigned LongestMatchLength = 0;
1977   for (unsigned I = 0; I < Style.JavaImportGroups.size(); I++) {
1978     std::string GroupPrefix = Style.JavaImportGroups[I];
1979     if (ImportIdentifier.startswith(GroupPrefix) &&
1980         GroupPrefix.length() > LongestMatchLength) {
1981       LongestMatchIndex = I;
1982       LongestMatchLength = GroupPrefix.length();
1983     }
1984   }
1985   return LongestMatchIndex;
1986 }
1987 
1988 // Sorts and deduplicates a block of includes given by 'Imports' based on
1989 // JavaImportGroups, then adding the necessary replacement to 'Replaces'.
1990 // Import declarations with the same text will be deduplicated. Between each
1991 // import group, a newline is inserted, and within each import group, a
1992 // lexicographic sort based on ASCII value is performed.
1993 static void sortJavaImports(const FormatStyle &Style,
1994                             const SmallVectorImpl<JavaImportDirective> &Imports,
1995                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
1996                             StringRef Code, tooling::Replacements &Replaces) {
1997   unsigned ImportsBeginOffset = Imports.front().Offset;
1998   unsigned ImportsEndOffset =
1999       Imports.back().Offset + Imports.back().Text.size();
2000   unsigned ImportsBlockSize = ImportsEndOffset - ImportsBeginOffset;
2001   if (!affectsRange(Ranges, ImportsBeginOffset, ImportsEndOffset))
2002     return;
2003   SmallVector<unsigned, 16> Indices;
2004   SmallVector<unsigned, 16> JavaImportGroups;
2005   for (unsigned i = 0, e = Imports.size(); i != e; ++i) {
2006     Indices.push_back(i);
2007     JavaImportGroups.push_back(
2008         findJavaImportGroup(Style, Imports[i].Identifier));
2009   }
2010   llvm::sort(Indices, [&](unsigned LHSI, unsigned RHSI) {
2011     // Negating IsStatic to push static imports above non-static imports.
2012     return std::make_tuple(!Imports[LHSI].IsStatic, JavaImportGroups[LHSI],
2013                            Imports[LHSI].Identifier) <
2014            std::make_tuple(!Imports[RHSI].IsStatic, JavaImportGroups[RHSI],
2015                            Imports[RHSI].Identifier);
2016   });
2017 
2018   // Deduplicate imports.
2019   Indices.erase(std::unique(Indices.begin(), Indices.end(),
2020                             [&](unsigned LHSI, unsigned RHSI) {
2021                               return Imports[LHSI].Text == Imports[RHSI].Text;
2022                             }),
2023                 Indices.end());
2024 
2025   bool CurrentIsStatic = Imports[Indices.front()].IsStatic;
2026   unsigned CurrentImportGroup = JavaImportGroups[Indices.front()];
2027 
2028   std::string result;
2029   for (unsigned Index : Indices) {
2030     if (!result.empty()) {
2031       result += "\n";
2032       if (CurrentIsStatic != Imports[Index].IsStatic ||
2033           CurrentImportGroup != JavaImportGroups[Index])
2034         result += "\n";
2035     }
2036     for (StringRef CommentLine : Imports[Index].AssociatedCommentLines) {
2037       result += CommentLine;
2038       result += "\n";
2039     }
2040     result += Imports[Index].Text;
2041     CurrentIsStatic = Imports[Index].IsStatic;
2042     CurrentImportGroup = JavaImportGroups[Index];
2043   }
2044 
2045   // If the imports are out of order, we generate a single replacement fixing
2046   // the entire block. Otherwise, no replacement is generated.
2047   if (result == Code.substr(Imports.front().Offset, ImportsBlockSize))
2048     return;
2049 
2050   auto Err = Replaces.add(tooling::Replacement(FileName, Imports.front().Offset,
2051                                                ImportsBlockSize, result));
2052   // FIXME: better error handling. For now, just skip the replacement for the
2053   // release version.
2054   if (Err) {
2055     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
2056     assert(false);
2057   }
2058 }
2059 
2060 namespace {
2061 
2062 const char JavaImportRegexPattern[] =
2063     "^[\t ]*import[\t ]+(static[\t ]*)?([^\t ]*)[\t ]*;";
2064 
2065 } // anonymous namespace
2066 
2067 tooling::Replacements sortJavaImports(const FormatStyle &Style, StringRef Code,
2068                                       ArrayRef<tooling::Range> Ranges,
2069                                       StringRef FileName,
2070                                       tooling::Replacements &Replaces) {
2071   unsigned Prev = 0;
2072   unsigned SearchFrom = 0;
2073   llvm::Regex ImportRegex(JavaImportRegexPattern);
2074   SmallVector<StringRef, 4> Matches;
2075   SmallVector<JavaImportDirective, 16> ImportsInBlock;
2076   std::vector<StringRef> AssociatedCommentLines;
2077 
2078   bool FormattingOff = false;
2079 
2080   for (;;) {
2081     auto Pos = Code.find('\n', SearchFrom);
2082     StringRef Line =
2083         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
2084 
2085     StringRef Trimmed = Line.trim();
2086     if (Trimmed == "// clang-format off")
2087       FormattingOff = true;
2088     else if (Trimmed == "// clang-format on")
2089       FormattingOff = false;
2090 
2091     if (ImportRegex.match(Line, &Matches)) {
2092       if (FormattingOff) {
2093         // If at least one import line has formatting turned off, turn off
2094         // formatting entirely.
2095         return Replaces;
2096       }
2097       StringRef Static = Matches[1];
2098       StringRef Identifier = Matches[2];
2099       bool IsStatic = false;
2100       if (Static.contains("static")) {
2101         IsStatic = true;
2102       }
2103       ImportsInBlock.push_back(
2104           {Identifier, Line, Prev, AssociatedCommentLines, IsStatic});
2105       AssociatedCommentLines.clear();
2106     } else if (Trimmed.size() > 0 && !ImportsInBlock.empty()) {
2107       // Associating comments within the imports with the nearest import below
2108       AssociatedCommentLines.push_back(Line);
2109     }
2110     Prev = Pos + 1;
2111     if (Pos == StringRef::npos || Pos + 1 == Code.size())
2112       break;
2113     SearchFrom = Pos + 1;
2114   }
2115   if (!ImportsInBlock.empty())
2116     sortJavaImports(Style, ImportsInBlock, Ranges, FileName, Code, Replaces);
2117   return Replaces;
2118 }
2119 
2120 bool isMpegTS(StringRef Code) {
2121   // MPEG transport streams use the ".ts" file extension. clang-format should
2122   // not attempt to format those. MPEG TS' frame format starts with 0x47 every
2123   // 189 bytes - detect that and return.
2124   return Code.size() > 188 && Code[0] == 0x47 && Code[188] == 0x47;
2125 }
2126 
2127 bool isLikelyXml(StringRef Code) { return Code.ltrim().startswith("<"); }
2128 
2129 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
2130                                    ArrayRef<tooling::Range> Ranges,
2131                                    StringRef FileName, unsigned *Cursor) {
2132   tooling::Replacements Replaces;
2133   if (!Style.SortIncludes)
2134     return Replaces;
2135   if (isLikelyXml(Code))
2136     return Replaces;
2137   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript &&
2138       isMpegTS(Code))
2139     return Replaces;
2140   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript)
2141     return sortJavaScriptImports(Style, Code, Ranges, FileName);
2142   if (Style.Language == FormatStyle::LanguageKind::LK_Java)
2143     return sortJavaImports(Style, Code, Ranges, FileName, Replaces);
2144   sortCppIncludes(Style, Code, Ranges, FileName, Replaces, Cursor);
2145   return Replaces;
2146 }
2147 
2148 template <typename T>
2149 static llvm::Expected<tooling::Replacements>
2150 processReplacements(T ProcessFunc, StringRef Code,
2151                     const tooling::Replacements &Replaces,
2152                     const FormatStyle &Style) {
2153   if (Replaces.empty())
2154     return tooling::Replacements();
2155 
2156   auto NewCode = applyAllReplacements(Code, Replaces);
2157   if (!NewCode)
2158     return NewCode.takeError();
2159   std::vector<tooling::Range> ChangedRanges = Replaces.getAffectedRanges();
2160   StringRef FileName = Replaces.begin()->getFilePath();
2161 
2162   tooling::Replacements FormatReplaces =
2163       ProcessFunc(Style, *NewCode, ChangedRanges, FileName);
2164 
2165   return Replaces.merge(FormatReplaces);
2166 }
2167 
2168 llvm::Expected<tooling::Replacements>
2169 formatReplacements(StringRef Code, const tooling::Replacements &Replaces,
2170                    const FormatStyle &Style) {
2171   // We need to use lambda function here since there are two versions of
2172   // `sortIncludes`.
2173   auto SortIncludes = [](const FormatStyle &Style, StringRef Code,
2174                          std::vector<tooling::Range> Ranges,
2175                          StringRef FileName) -> tooling::Replacements {
2176     return sortIncludes(Style, Code, Ranges, FileName);
2177   };
2178   auto SortedReplaces =
2179       processReplacements(SortIncludes, Code, Replaces, Style);
2180   if (!SortedReplaces)
2181     return SortedReplaces.takeError();
2182 
2183   // We need to use lambda function here since there are two versions of
2184   // `reformat`.
2185   auto Reformat = [](const FormatStyle &Style, StringRef Code,
2186                      std::vector<tooling::Range> Ranges,
2187                      StringRef FileName) -> tooling::Replacements {
2188     return reformat(Style, Code, Ranges, FileName);
2189   };
2190   return processReplacements(Reformat, Code, *SortedReplaces, Style);
2191 }
2192 
2193 namespace {
2194 
2195 inline bool isHeaderInsertion(const tooling::Replacement &Replace) {
2196   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 0 &&
2197          llvm::Regex(CppIncludeRegexPattern)
2198              .match(Replace.getReplacementText());
2199 }
2200 
2201 inline bool isHeaderDeletion(const tooling::Replacement &Replace) {
2202   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 1;
2203 }
2204 
2205 // FIXME: insert empty lines between newly created blocks.
2206 tooling::Replacements
2207 fixCppIncludeInsertions(StringRef Code, const tooling::Replacements &Replaces,
2208                         const FormatStyle &Style) {
2209   if (!Style.isCpp())
2210     return Replaces;
2211 
2212   tooling::Replacements HeaderInsertions;
2213   std::set<llvm::StringRef> HeadersToDelete;
2214   tooling::Replacements Result;
2215   for (const auto &R : Replaces) {
2216     if (isHeaderInsertion(R)) {
2217       // Replacements from \p Replaces must be conflict-free already, so we can
2218       // simply consume the error.
2219       llvm::consumeError(HeaderInsertions.add(R));
2220     } else if (isHeaderDeletion(R)) {
2221       HeadersToDelete.insert(R.getReplacementText());
2222     } else if (R.getOffset() == UINT_MAX) {
2223       llvm::errs() << "Insertions other than header #include insertion are "
2224                       "not supported! "
2225                    << R.getReplacementText() << "\n";
2226     } else {
2227       llvm::consumeError(Result.add(R));
2228     }
2229   }
2230   if (HeaderInsertions.empty() && HeadersToDelete.empty())
2231     return Replaces;
2232 
2233   StringRef FileName = Replaces.begin()->getFilePath();
2234   tooling::HeaderIncludes Includes(FileName, Code, Style.IncludeStyle);
2235 
2236   for (const auto &Header : HeadersToDelete) {
2237     tooling::Replacements Replaces =
2238         Includes.remove(Header.trim("\"<>"), Header.startswith("<"));
2239     for (const auto &R : Replaces) {
2240       auto Err = Result.add(R);
2241       if (Err) {
2242         // Ignore the deletion on conflict.
2243         llvm::errs() << "Failed to add header deletion replacement for "
2244                      << Header << ": " << llvm::toString(std::move(Err))
2245                      << "\n";
2246       }
2247     }
2248   }
2249 
2250   llvm::Regex IncludeRegex = llvm::Regex(CppIncludeRegexPattern);
2251   llvm::SmallVector<StringRef, 4> Matches;
2252   for (const auto &R : HeaderInsertions) {
2253     auto IncludeDirective = R.getReplacementText();
2254     bool Matched = IncludeRegex.match(IncludeDirective, &Matches);
2255     assert(Matched && "Header insertion replacement must have replacement text "
2256                       "'#include ...'");
2257     (void)Matched;
2258     auto IncludeName = Matches[2];
2259     auto Replace =
2260         Includes.insert(IncludeName.trim("\"<>"), IncludeName.startswith("<"));
2261     if (Replace) {
2262       auto Err = Result.add(*Replace);
2263       if (Err) {
2264         llvm::consumeError(std::move(Err));
2265         unsigned NewOffset =
2266             Result.getShiftedCodePosition(Replace->getOffset());
2267         auto Shifted = tooling::Replacement(FileName, NewOffset, 0,
2268                                             Replace->getReplacementText());
2269         Result = Result.merge(tooling::Replacements(Shifted));
2270       }
2271     }
2272   }
2273   return Result;
2274 }
2275 
2276 } // anonymous namespace
2277 
2278 llvm::Expected<tooling::Replacements>
2279 cleanupAroundReplacements(StringRef Code, const tooling::Replacements &Replaces,
2280                           const FormatStyle &Style) {
2281   // We need to use lambda function here since there are two versions of
2282   // `cleanup`.
2283   auto Cleanup = [](const FormatStyle &Style, StringRef Code,
2284                     std::vector<tooling::Range> Ranges,
2285                     StringRef FileName) -> tooling::Replacements {
2286     return cleanup(Style, Code, Ranges, FileName);
2287   };
2288   // Make header insertion replacements insert new headers into correct blocks.
2289   tooling::Replacements NewReplaces =
2290       fixCppIncludeInsertions(Code, Replaces, Style);
2291   return processReplacements(Cleanup, Code, NewReplaces, Style);
2292 }
2293 
2294 namespace internal {
2295 std::pair<tooling::Replacements, unsigned>
2296 reformat(const FormatStyle &Style, StringRef Code,
2297          ArrayRef<tooling::Range> Ranges, unsigned FirstStartColumn,
2298          unsigned NextStartColumn, unsigned LastStartColumn, StringRef FileName,
2299          FormattingAttemptStatus *Status) {
2300   FormatStyle Expanded = expandPresets(Style);
2301   if (Expanded.DisableFormat)
2302     return {tooling::Replacements(), 0};
2303   if (isLikelyXml(Code))
2304     return {tooling::Replacements(), 0};
2305   if (Expanded.Language == FormatStyle::LK_JavaScript && isMpegTS(Code))
2306     return {tooling::Replacements(), 0};
2307 
2308   typedef std::function<std::pair<tooling::Replacements, unsigned>(
2309       const Environment &)>
2310       AnalyzerPass;
2311   SmallVector<AnalyzerPass, 4> Passes;
2312 
2313   if (Style.Language == FormatStyle::LK_Cpp) {
2314     if (Style.FixNamespaceComments)
2315       Passes.emplace_back([&](const Environment &Env) {
2316         return NamespaceEndCommentsFixer(Env, Expanded).process();
2317       });
2318 
2319     if (Style.SortUsingDeclarations)
2320       Passes.emplace_back([&](const Environment &Env) {
2321         return UsingDeclarationsSorter(Env, Expanded).process();
2322       });
2323   }
2324 
2325   if (Style.Language == FormatStyle::LK_JavaScript &&
2326       Style.JavaScriptQuotes != FormatStyle::JSQS_Leave)
2327     Passes.emplace_back([&](const Environment &Env) {
2328       return JavaScriptRequoter(Env, Expanded).process();
2329     });
2330 
2331   Passes.emplace_back([&](const Environment &Env) {
2332     return Formatter(Env, Expanded, Status).process();
2333   });
2334 
2335   auto Env =
2336       std::make_unique<Environment>(Code, FileName, Ranges, FirstStartColumn,
2337                                      NextStartColumn, LastStartColumn);
2338   llvm::Optional<std::string> CurrentCode = None;
2339   tooling::Replacements Fixes;
2340   unsigned Penalty = 0;
2341   for (size_t I = 0, E = Passes.size(); I < E; ++I) {
2342     std::pair<tooling::Replacements, unsigned> PassFixes = Passes[I](*Env);
2343     auto NewCode = applyAllReplacements(
2344         CurrentCode ? StringRef(*CurrentCode) : Code, PassFixes.first);
2345     if (NewCode) {
2346       Fixes = Fixes.merge(PassFixes.first);
2347       Penalty += PassFixes.second;
2348       if (I + 1 < E) {
2349         CurrentCode = std::move(*NewCode);
2350         Env = std::make_unique<Environment>(
2351             *CurrentCode, FileName,
2352             tooling::calculateRangesAfterReplacements(Fixes, Ranges),
2353             FirstStartColumn, NextStartColumn, LastStartColumn);
2354       }
2355     }
2356   }
2357 
2358   return {Fixes, Penalty};
2359 }
2360 } // namespace internal
2361 
2362 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
2363                                ArrayRef<tooling::Range> Ranges,
2364                                StringRef FileName,
2365                                FormattingAttemptStatus *Status) {
2366   return internal::reformat(Style, Code, Ranges,
2367                             /*FirstStartColumn=*/0,
2368                             /*NextStartColumn=*/0,
2369                             /*LastStartColumn=*/0, FileName, Status)
2370       .first;
2371 }
2372 
2373 tooling::Replacements cleanup(const FormatStyle &Style, StringRef Code,
2374                               ArrayRef<tooling::Range> Ranges,
2375                               StringRef FileName) {
2376   // cleanups only apply to C++ (they mostly concern ctor commas etc.)
2377   if (Style.Language != FormatStyle::LK_Cpp)
2378     return tooling::Replacements();
2379   return Cleaner(Environment(Code, FileName, Ranges), Style).process().first;
2380 }
2381 
2382 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
2383                                ArrayRef<tooling::Range> Ranges,
2384                                StringRef FileName, bool *IncompleteFormat) {
2385   FormattingAttemptStatus Status;
2386   auto Result = reformat(Style, Code, Ranges, FileName, &Status);
2387   if (!Status.FormatComplete)
2388     *IncompleteFormat = true;
2389   return Result;
2390 }
2391 
2392 tooling::Replacements fixNamespaceEndComments(const FormatStyle &Style,
2393                                               StringRef Code,
2394                                               ArrayRef<tooling::Range> Ranges,
2395                                               StringRef FileName) {
2396   return NamespaceEndCommentsFixer(Environment(Code, FileName, Ranges), Style)
2397       .process()
2398       .first;
2399 }
2400 
2401 tooling::Replacements sortUsingDeclarations(const FormatStyle &Style,
2402                                             StringRef Code,
2403                                             ArrayRef<tooling::Range> Ranges,
2404                                             StringRef FileName) {
2405   return UsingDeclarationsSorter(Environment(Code, FileName, Ranges), Style)
2406       .process()
2407       .first;
2408 }
2409 
2410 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
2411   LangOptions LangOpts;
2412   FormatStyle::LanguageStandard LexingStd =
2413       Style.Standard == FormatStyle::LS_Auto ? FormatStyle::LS_Cpp11
2414                                              : Style.Standard;
2415   LangOpts.CPlusPlus = 1;
2416   LangOpts.CPlusPlus11 = LexingStd >= FormatStyle::LS_Cpp11;
2417   LangOpts.CPlusPlus14 = LexingStd >= FormatStyle::LS_Cpp11;
2418   LangOpts.CPlusPlus17 = LexingStd >= FormatStyle::LS_Cpp11;
2419   LangOpts.CPlusPlus2a = LexingStd >= FormatStyle::LS_Cpp11;
2420   LangOpts.LineComment = 1;
2421   bool AlternativeOperators = Style.isCpp();
2422   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
2423   LangOpts.Bool = 1;
2424   LangOpts.ObjC = 1;
2425   LangOpts.MicrosoftExt = 1;    // To get kw___try, kw___finally.
2426   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
2427   return LangOpts;
2428 }
2429 
2430 const char *StyleOptionHelpDescription =
2431     "Coding style, currently supports:\n"
2432     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
2433     "Use -style=file to load style configuration from\n"
2434     ".clang-format file located in one of the parent\n"
2435     "directories of the source file (or current\n"
2436     "directory for stdin).\n"
2437     "Use -style=\"{key: value, ...}\" to set specific\n"
2438     "parameters, e.g.:\n"
2439     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
2440 
2441 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
2442   if (FileName.endswith(".java"))
2443     return FormatStyle::LK_Java;
2444   if (FileName.endswith_lower(".js") || FileName.endswith_lower(".mjs") ||
2445       FileName.endswith_lower(".ts"))
2446     return FormatStyle::LK_JavaScript; // (module) JavaScript or TypeScript.
2447   if (FileName.endswith(".m") || FileName.endswith(".mm"))
2448     return FormatStyle::LK_ObjC;
2449   if (FileName.endswith_lower(".proto") ||
2450       FileName.endswith_lower(".protodevel"))
2451     return FormatStyle::LK_Proto;
2452   if (FileName.endswith_lower(".textpb") ||
2453       FileName.endswith_lower(".pb.txt") ||
2454       FileName.endswith_lower(".textproto") ||
2455       FileName.endswith_lower(".asciipb"))
2456     return FormatStyle::LK_TextProto;
2457   if (FileName.endswith_lower(".td"))
2458     return FormatStyle::LK_TableGen;
2459   if (FileName.endswith_lower(".cs"))
2460     return FormatStyle::LK_CSharp;
2461   return FormatStyle::LK_Cpp;
2462 }
2463 
2464 FormatStyle::LanguageKind guessLanguage(StringRef FileName, StringRef Code) {
2465   const auto GuessedLanguage = getLanguageByFileName(FileName);
2466   if (GuessedLanguage == FormatStyle::LK_Cpp) {
2467     auto Extension = llvm::sys::path::extension(FileName);
2468     // If there's no file extension (or it's .h), we need to check the contents
2469     // of the code to see if it contains Objective-C.
2470     if (Extension.empty() || Extension == ".h") {
2471       auto NonEmptyFileName = FileName.empty() ? "guess.h" : FileName;
2472       Environment Env(Code, NonEmptyFileName, /*Ranges=*/{});
2473       ObjCHeaderStyleGuesser Guesser(Env, getLLVMStyle());
2474       Guesser.process();
2475       if (Guesser.isObjC())
2476         return FormatStyle::LK_ObjC;
2477     }
2478   }
2479   return GuessedLanguage;
2480 }
2481 
2482 const char *DefaultFormatStyle = "file";
2483 
2484 const char *DefaultFallbackStyle = "LLVM";
2485 
2486 llvm::Expected<FormatStyle> getStyle(StringRef StyleName, StringRef FileName,
2487                                      StringRef FallbackStyleName,
2488                                      StringRef Code,
2489                                      llvm::vfs::FileSystem *FS) {
2490   if (!FS) {
2491     FS = llvm::vfs::getRealFileSystem().get();
2492   }
2493   FormatStyle Style = getLLVMStyle(guessLanguage(FileName, Code));
2494 
2495   FormatStyle FallbackStyle = getNoStyle();
2496   if (!getPredefinedStyle(FallbackStyleName, Style.Language, &FallbackStyle))
2497     return make_string_error("Invalid fallback style \"" + FallbackStyleName);
2498 
2499   if (StyleName.startswith("{")) {
2500     // Parse YAML/JSON style from the command line.
2501     if (std::error_code ec = parseConfiguration(StyleName, &Style))
2502       return make_string_error("Error parsing -style: " + ec.message());
2503     return Style;
2504   }
2505 
2506   if (!StyleName.equals_lower("file")) {
2507     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
2508       return make_string_error("Invalid value for -style");
2509     return Style;
2510   }
2511 
2512   // Look for .clang-format/_clang-format file in the file's parent directories.
2513   SmallString<128> UnsuitableConfigFiles;
2514   SmallString<128> Path(FileName);
2515   if (std::error_code EC = FS->makeAbsolute(Path))
2516     return make_string_error(EC.message());
2517 
2518   for (StringRef Directory = Path; !Directory.empty();
2519        Directory = llvm::sys::path::parent_path(Directory)) {
2520 
2521     auto Status = FS->status(Directory);
2522     if (!Status ||
2523         Status->getType() != llvm::sys::fs::file_type::directory_file) {
2524       continue;
2525     }
2526 
2527     SmallString<128> ConfigFile(Directory);
2528 
2529     llvm::sys::path::append(ConfigFile, ".clang-format");
2530     LLVM_DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2531 
2532     Status = FS->status(ConfigFile.str());
2533     bool FoundConfigFile =
2534         Status && (Status->getType() == llvm::sys::fs::file_type::regular_file);
2535     if (!FoundConfigFile) {
2536       // Try _clang-format too, since dotfiles are not commonly used on Windows.
2537       ConfigFile = Directory;
2538       llvm::sys::path::append(ConfigFile, "_clang-format");
2539       LLVM_DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2540       Status = FS->status(ConfigFile.str());
2541       FoundConfigFile = Status && (Status->getType() ==
2542                                    llvm::sys::fs::file_type::regular_file);
2543     }
2544 
2545     if (FoundConfigFile) {
2546       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
2547           FS->getBufferForFile(ConfigFile.str());
2548       if (std::error_code EC = Text.getError())
2549         return make_string_error(EC.message());
2550       if (std::error_code ec =
2551               parseConfiguration(Text.get()->getBuffer(), &Style)) {
2552         if (ec == ParseError::Unsuitable) {
2553           if (!UnsuitableConfigFiles.empty())
2554             UnsuitableConfigFiles.append(", ");
2555           UnsuitableConfigFiles.append(ConfigFile);
2556           continue;
2557         }
2558         return make_string_error("Error reading " + ConfigFile + ": " +
2559                                  ec.message());
2560       }
2561       LLVM_DEBUG(llvm::dbgs()
2562                  << "Using configuration file " << ConfigFile << "\n");
2563       return Style;
2564     }
2565   }
2566   if (!UnsuitableConfigFiles.empty())
2567     return make_string_error("Configuration file(s) do(es) not support " +
2568                              getLanguageName(Style.Language) + ": " +
2569                              UnsuitableConfigFiles);
2570   return FallbackStyle;
2571 }
2572 
2573 } // namespace format
2574 } // namespace clang
2575