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