1 //===--- Format.cpp - Format C++ code -------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief This file implements functions declared in Format.h. This will be
12 /// split into separate files as we go.
13 ///
14 //===----------------------------------------------------------------------===//
15 
16 #include "clang/Format/Format.h"
17 #include "AffectedRangeManager.h"
18 #include "ContinuationIndenter.h"
19 #include "FormatTokenLexer.h"
20 #include "SortJavaScriptImports.h"
21 #include "TokenAnalyzer.h"
22 #include "TokenAnnotator.h"
23 #include "UnwrappedLineFormatter.h"
24 #include "UnwrappedLineParser.h"
25 #include "WhitespaceManager.h"
26 #include "clang/Basic/Diagnostic.h"
27 #include "clang/Basic/DiagnosticOptions.h"
28 #include "clang/Basic/SourceManager.h"
29 #include "clang/Basic/VirtualFileSystem.h"
30 #include "clang/Lex/Lexer.h"
31 #include "llvm/ADT/STLExtras.h"
32 #include "llvm/Support/Allocator.h"
33 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/Path.h"
35 #include "llvm/Support/Regex.h"
36 #include "llvm/Support/YAMLTraits.h"
37 #include <memory>
38 #include <queue>
39 #include <string>
40 
41 #define DEBUG_TYPE "format-formatter"
42 
43 using clang::format::FormatStyle;
44 
45 LLVM_YAML_IS_FLOW_SEQUENCE_VECTOR(std::string)
46 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::format::FormatStyle::IncludeCategory)
47 
48 namespace llvm {
49 namespace yaml {
50 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
51   static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
52     IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
53     IO.enumCase(Value, "Java", FormatStyle::LK_Java);
54     IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
55     IO.enumCase(Value, "Proto", FormatStyle::LK_Proto);
56     IO.enumCase(Value, "TableGen", FormatStyle::LK_TableGen);
57   }
58 };
59 
60 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
61   static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
62     IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03);
63     IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03);
64     IO.enumCase(Value, "Cpp11", FormatStyle::LS_Cpp11);
65     IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11);
66     IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
67   }
68 };
69 
70 template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
71   static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
72     IO.enumCase(Value, "Never", FormatStyle::UT_Never);
73     IO.enumCase(Value, "false", FormatStyle::UT_Never);
74     IO.enumCase(Value, "Always", FormatStyle::UT_Always);
75     IO.enumCase(Value, "true", FormatStyle::UT_Always);
76     IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
77     IO.enumCase(Value, "ForContinuationAndIndentation",
78                 FormatStyle::UT_ForContinuationAndIndentation);
79   }
80 };
81 
82 template <> struct ScalarEnumerationTraits<FormatStyle::JavaScriptQuoteStyle> {
83   static void enumeration(IO &IO, FormatStyle::JavaScriptQuoteStyle &Value) {
84     IO.enumCase(Value, "Leave", FormatStyle::JSQS_Leave);
85     IO.enumCase(Value, "Single", FormatStyle::JSQS_Single);
86     IO.enumCase(Value, "Double", FormatStyle::JSQS_Double);
87   }
88 };
89 
90 template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
91   static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
92     IO.enumCase(Value, "None", FormatStyle::SFS_None);
93     IO.enumCase(Value, "false", FormatStyle::SFS_None);
94     IO.enumCase(Value, "All", FormatStyle::SFS_All);
95     IO.enumCase(Value, "true", FormatStyle::SFS_All);
96     IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
97     IO.enumCase(Value, "Empty", FormatStyle::SFS_Empty);
98   }
99 };
100 
101 template <> struct ScalarEnumerationTraits<FormatStyle::BinaryOperatorStyle> {
102   static void enumeration(IO &IO, FormatStyle::BinaryOperatorStyle &Value) {
103     IO.enumCase(Value, "All", FormatStyle::BOS_All);
104     IO.enumCase(Value, "true", FormatStyle::BOS_All);
105     IO.enumCase(Value, "None", FormatStyle::BOS_None);
106     IO.enumCase(Value, "false", FormatStyle::BOS_None);
107     IO.enumCase(Value, "NonAssignment", FormatStyle::BOS_NonAssignment);
108   }
109 };
110 
111 template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
112   static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
113     IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
114     IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
115     IO.enumCase(Value, "Mozilla", FormatStyle::BS_Mozilla);
116     IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
117     IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
118     IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
119     IO.enumCase(Value, "WebKit", FormatStyle::BS_WebKit);
120     IO.enumCase(Value, "Custom", FormatStyle::BS_Custom);
121   }
122 };
123 
124 template <>
125 struct ScalarEnumerationTraits<FormatStyle::ReturnTypeBreakingStyle> {
126   static void enumeration(IO &IO, FormatStyle::ReturnTypeBreakingStyle &Value) {
127     IO.enumCase(Value, "None", FormatStyle::RTBS_None);
128     IO.enumCase(Value, "All", FormatStyle::RTBS_All);
129     IO.enumCase(Value, "TopLevel", FormatStyle::RTBS_TopLevel);
130     IO.enumCase(Value, "TopLevelDefinitions",
131                 FormatStyle::RTBS_TopLevelDefinitions);
132     IO.enumCase(Value, "AllDefinitions", FormatStyle::RTBS_AllDefinitions);
133   }
134 };
135 
136 template <>
137 struct ScalarEnumerationTraits<FormatStyle::DefinitionReturnTypeBreakingStyle> {
138   static void
139   enumeration(IO &IO, FormatStyle::DefinitionReturnTypeBreakingStyle &Value) {
140     IO.enumCase(Value, "None", FormatStyle::DRTBS_None);
141     IO.enumCase(Value, "All", FormatStyle::DRTBS_All);
142     IO.enumCase(Value, "TopLevel", FormatStyle::DRTBS_TopLevel);
143 
144     // For backward compatibility.
145     IO.enumCase(Value, "false", FormatStyle::DRTBS_None);
146     IO.enumCase(Value, "true", FormatStyle::DRTBS_All);
147   }
148 };
149 
150 template <>
151 struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
152   static void enumeration(IO &IO,
153                           FormatStyle::NamespaceIndentationKind &Value) {
154     IO.enumCase(Value, "None", FormatStyle::NI_None);
155     IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
156     IO.enumCase(Value, "All", FormatStyle::NI_All);
157   }
158 };
159 
160 template <> struct ScalarEnumerationTraits<FormatStyle::BracketAlignmentStyle> {
161   static void enumeration(IO &IO, FormatStyle::BracketAlignmentStyle &Value) {
162     IO.enumCase(Value, "Align", FormatStyle::BAS_Align);
163     IO.enumCase(Value, "DontAlign", FormatStyle::BAS_DontAlign);
164     IO.enumCase(Value, "AlwaysBreak", FormatStyle::BAS_AlwaysBreak);
165 
166     // For backward compatibility.
167     IO.enumCase(Value, "true", FormatStyle::BAS_Align);
168     IO.enumCase(Value, "false", FormatStyle::BAS_DontAlign);
169   }
170 };
171 
172 template <> struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
173   static void enumeration(IO &IO, FormatStyle::PointerAlignmentStyle &Value) {
174     IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
175     IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
176     IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
177 
178     // For backward compatibility.
179     IO.enumCase(Value, "true", FormatStyle::PAS_Left);
180     IO.enumCase(Value, "false", FormatStyle::PAS_Right);
181   }
182 };
183 
184 template <>
185 struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
186   static void enumeration(IO &IO,
187                           FormatStyle::SpaceBeforeParensOptions &Value) {
188     IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
189     IO.enumCase(Value, "ControlStatements",
190                 FormatStyle::SBPO_ControlStatements);
191     IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
192 
193     // For backward compatibility.
194     IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
195     IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
196   }
197 };
198 
199 template <> struct MappingTraits<FormatStyle> {
200   static void mapping(IO &IO, FormatStyle &Style) {
201     // When reading, read the language first, we need it for getPredefinedStyle.
202     IO.mapOptional("Language", Style.Language);
203 
204     if (IO.outputting()) {
205       StringRef StylesArray[] = {"LLVM",    "Google", "Chromium",
206                                  "Mozilla", "WebKit", "GNU"};
207       ArrayRef<StringRef> Styles(StylesArray);
208       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
209         StringRef StyleName(Styles[i]);
210         FormatStyle PredefinedStyle;
211         if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
212             Style == PredefinedStyle) {
213           IO.mapOptional("# BasedOnStyle", StyleName);
214           break;
215         }
216       }
217     } else {
218       StringRef BasedOnStyle;
219       IO.mapOptional("BasedOnStyle", BasedOnStyle);
220       if (!BasedOnStyle.empty()) {
221         FormatStyle::LanguageKind OldLanguage = Style.Language;
222         FormatStyle::LanguageKind Language =
223             ((FormatStyle *)IO.getContext())->Language;
224         if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
225           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
226           return;
227         }
228         Style.Language = OldLanguage;
229       }
230     }
231 
232     // For backward compatibility.
233     if (!IO.outputting()) {
234       IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
235       IO.mapOptional("IndentFunctionDeclarationAfterType",
236                      Style.IndentWrappedFunctionNames);
237       IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
238       IO.mapOptional("SpaceAfterControlStatementKeyword",
239                      Style.SpaceBeforeParens);
240     }
241 
242     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
243     IO.mapOptional("AlignAfterOpenBracket", Style.AlignAfterOpenBracket);
244     IO.mapOptional("AlignConsecutiveAssignments",
245                    Style.AlignConsecutiveAssignments);
246     IO.mapOptional("AlignConsecutiveDeclarations",
247                    Style.AlignConsecutiveDeclarations);
248     IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
249     IO.mapOptional("AlignOperands", Style.AlignOperands);
250     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
251     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
252                    Style.AllowAllParametersOfDeclarationOnNextLine);
253     IO.mapOptional("AllowShortBlocksOnASingleLine",
254                    Style.AllowShortBlocksOnASingleLine);
255     IO.mapOptional("AllowShortCaseLabelsOnASingleLine",
256                    Style.AllowShortCaseLabelsOnASingleLine);
257     IO.mapOptional("AllowShortFunctionsOnASingleLine",
258                    Style.AllowShortFunctionsOnASingleLine);
259     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
260                    Style.AllowShortIfStatementsOnASingleLine);
261     IO.mapOptional("AllowShortLoopsOnASingleLine",
262                    Style.AllowShortLoopsOnASingleLine);
263     IO.mapOptional("AlwaysBreakAfterDefinitionReturnType",
264                    Style.AlwaysBreakAfterDefinitionReturnType);
265     IO.mapOptional("AlwaysBreakAfterReturnType",
266                    Style.AlwaysBreakAfterReturnType);
267     // If AlwaysBreakAfterDefinitionReturnType was specified but
268     // AlwaysBreakAfterReturnType was not, initialize the latter from the
269     // former for backwards compatibility.
270     if (Style.AlwaysBreakAfterDefinitionReturnType != FormatStyle::DRTBS_None &&
271         Style.AlwaysBreakAfterReturnType == FormatStyle::RTBS_None) {
272       if (Style.AlwaysBreakAfterDefinitionReturnType == FormatStyle::DRTBS_All)
273         Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
274       else if (Style.AlwaysBreakAfterDefinitionReturnType ==
275                FormatStyle::DRTBS_TopLevel)
276         Style.AlwaysBreakAfterReturnType =
277             FormatStyle::RTBS_TopLevelDefinitions;
278     }
279 
280     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
281                    Style.AlwaysBreakBeforeMultilineStrings);
282     IO.mapOptional("AlwaysBreakTemplateDeclarations",
283                    Style.AlwaysBreakTemplateDeclarations);
284     IO.mapOptional("BinPackArguments", Style.BinPackArguments);
285     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
286     IO.mapOptional("BraceWrapping", Style.BraceWrapping);
287     IO.mapOptional("BreakBeforeBinaryOperators",
288                    Style.BreakBeforeBinaryOperators);
289     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
290     IO.mapOptional("BreakBeforeTernaryOperators",
291                    Style.BreakBeforeTernaryOperators);
292     IO.mapOptional("BreakConstructorInitializersBeforeComma",
293                    Style.BreakConstructorInitializersBeforeComma);
294     IO.mapOptional("BreakAfterJavaFieldAnnotations",
295                    Style.BreakAfterJavaFieldAnnotations);
296     IO.mapOptional("BreakStringLiterals", Style.BreakStringLiterals);
297     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
298     IO.mapOptional("CommentPragmas", Style.CommentPragmas);
299     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
300                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
301     IO.mapOptional("ConstructorInitializerIndentWidth",
302                    Style.ConstructorInitializerIndentWidth);
303     IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
304     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
305     IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
306     IO.mapOptional("DisableFormat", Style.DisableFormat);
307     IO.mapOptional("ExperimentalAutoDetectBinPacking",
308                    Style.ExperimentalAutoDetectBinPacking);
309     IO.mapOptional("ForEachMacros", Style.ForEachMacros);
310     IO.mapOptional("IncludeCategories", Style.IncludeCategories);
311     IO.mapOptional("IncludeIsMainRegex", Style.IncludeIsMainRegex);
312     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
313     IO.mapOptional("IndentWidth", Style.IndentWidth);
314     IO.mapOptional("IndentWrappedFunctionNames",
315                    Style.IndentWrappedFunctionNames);
316     IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
317                    Style.KeepEmptyLinesAtTheStartOfBlocks);
318     IO.mapOptional("MacroBlockBegin", Style.MacroBlockBegin);
319     IO.mapOptional("MacroBlockEnd", Style.MacroBlockEnd);
320     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
321     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
322     IO.mapOptional("ObjCBlockIndentWidth", Style.ObjCBlockIndentWidth);
323     IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
324     IO.mapOptional("ObjCSpaceBeforeProtocolList",
325                    Style.ObjCSpaceBeforeProtocolList);
326     IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
327                    Style.PenaltyBreakBeforeFirstCallParameter);
328     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
329     IO.mapOptional("PenaltyBreakFirstLessLess",
330                    Style.PenaltyBreakFirstLessLess);
331     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
332     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
333     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
334                    Style.PenaltyReturnTypeOnItsOwnLine);
335     IO.mapOptional("PointerAlignment", Style.PointerAlignment);
336     IO.mapOptional("ReflowComments", Style.ReflowComments);
337     IO.mapOptional("SortIncludes", Style.SortIncludes);
338     IO.mapOptional("SpaceAfterCStyleCast", Style.SpaceAfterCStyleCast);
339     IO.mapOptional("SpaceBeforeAssignmentOperators",
340                    Style.SpaceBeforeAssignmentOperators);
341     IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
342     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
343     IO.mapOptional("SpacesBeforeTrailingComments",
344                    Style.SpacesBeforeTrailingComments);
345     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
346     IO.mapOptional("SpacesInContainerLiterals",
347                    Style.SpacesInContainerLiterals);
348     IO.mapOptional("SpacesInCStyleCastParentheses",
349                    Style.SpacesInCStyleCastParentheses);
350     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
351     IO.mapOptional("SpacesInSquareBrackets", Style.SpacesInSquareBrackets);
352     IO.mapOptional("Standard", Style.Standard);
353     IO.mapOptional("TabWidth", Style.TabWidth);
354     IO.mapOptional("UseTab", Style.UseTab);
355     IO.mapOptional("JavaScriptQuotes", Style.JavaScriptQuotes);
356   }
357 };
358 
359 template <> struct MappingTraits<FormatStyle::BraceWrappingFlags> {
360   static void mapping(IO &IO, FormatStyle::BraceWrappingFlags &Wrapping) {
361     IO.mapOptional("AfterClass", Wrapping.AfterClass);
362     IO.mapOptional("AfterControlStatement", Wrapping.AfterControlStatement);
363     IO.mapOptional("AfterEnum", Wrapping.AfterEnum);
364     IO.mapOptional("AfterFunction", Wrapping.AfterFunction);
365     IO.mapOptional("AfterNamespace", Wrapping.AfterNamespace);
366     IO.mapOptional("AfterObjCDeclaration", Wrapping.AfterObjCDeclaration);
367     IO.mapOptional("AfterStruct", Wrapping.AfterStruct);
368     IO.mapOptional("AfterUnion", Wrapping.AfterUnion);
369     IO.mapOptional("BeforeCatch", Wrapping.BeforeCatch);
370     IO.mapOptional("BeforeElse", Wrapping.BeforeElse);
371     IO.mapOptional("IndentBraces", Wrapping.IndentBraces);
372   }
373 };
374 
375 template <> struct MappingTraits<FormatStyle::IncludeCategory> {
376   static void mapping(IO &IO, FormatStyle::IncludeCategory &Category) {
377     IO.mapOptional("Regex", Category.Regex);
378     IO.mapOptional("Priority", Category.Priority);
379   }
380 };
381 
382 // Allows to read vector<FormatStyle> while keeping default values.
383 // IO.getContext() should contain a pointer to the FormatStyle structure, that
384 // will be used to get default values for missing keys.
385 // If the first element has no Language specified, it will be treated as the
386 // default one for the following elements.
387 template <> struct DocumentListTraits<std::vector<FormatStyle>> {
388   static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
389     return Seq.size();
390   }
391   static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
392                               size_t Index) {
393     if (Index >= Seq.size()) {
394       assert(Index == Seq.size());
395       FormatStyle Template;
396       if (Seq.size() > 0 && Seq[0].Language == FormatStyle::LK_None) {
397         Template = Seq[0];
398       } else {
399         Template = *((const FormatStyle *)IO.getContext());
400         Template.Language = FormatStyle::LK_None;
401       }
402       Seq.resize(Index + 1, Template);
403     }
404     return Seq[Index];
405   }
406 };
407 } // namespace yaml
408 } // namespace llvm
409 
410 namespace clang {
411 namespace format {
412 
413 const std::error_category &getParseCategory() {
414   static ParseErrorCategory C;
415   return C;
416 }
417 std::error_code make_error_code(ParseError e) {
418   return std::error_code(static_cast<int>(e), getParseCategory());
419 }
420 
421 const char *ParseErrorCategory::name() const LLVM_NOEXCEPT {
422   return "clang-format.parse_error";
423 }
424 
425 std::string ParseErrorCategory::message(int EV) const {
426   switch (static_cast<ParseError>(EV)) {
427   case ParseError::Success:
428     return "Success";
429   case ParseError::Error:
430     return "Invalid argument";
431   case ParseError::Unsuitable:
432     return "Unsuitable";
433   }
434   llvm_unreachable("unexpected parse error");
435 }
436 
437 static FormatStyle expandPresets(const FormatStyle &Style) {
438   if (Style.BreakBeforeBraces == FormatStyle::BS_Custom)
439     return Style;
440   FormatStyle Expanded = Style;
441   Expanded.BraceWrapping = {false, false, false, false, false, false,
442                             false, false, false, false, false};
443   switch (Style.BreakBeforeBraces) {
444   case FormatStyle::BS_Linux:
445     Expanded.BraceWrapping.AfterClass = true;
446     Expanded.BraceWrapping.AfterFunction = true;
447     Expanded.BraceWrapping.AfterNamespace = true;
448     break;
449   case FormatStyle::BS_Mozilla:
450     Expanded.BraceWrapping.AfterClass = true;
451     Expanded.BraceWrapping.AfterEnum = true;
452     Expanded.BraceWrapping.AfterFunction = true;
453     Expanded.BraceWrapping.AfterStruct = true;
454     Expanded.BraceWrapping.AfterUnion = true;
455     break;
456   case FormatStyle::BS_Stroustrup:
457     Expanded.BraceWrapping.AfterFunction = true;
458     Expanded.BraceWrapping.BeforeCatch = true;
459     Expanded.BraceWrapping.BeforeElse = true;
460     break;
461   case FormatStyle::BS_Allman:
462     Expanded.BraceWrapping.AfterClass = true;
463     Expanded.BraceWrapping.AfterControlStatement = true;
464     Expanded.BraceWrapping.AfterEnum = true;
465     Expanded.BraceWrapping.AfterFunction = true;
466     Expanded.BraceWrapping.AfterNamespace = true;
467     Expanded.BraceWrapping.AfterObjCDeclaration = true;
468     Expanded.BraceWrapping.AfterStruct = true;
469     Expanded.BraceWrapping.BeforeCatch = true;
470     Expanded.BraceWrapping.BeforeElse = true;
471     break;
472   case FormatStyle::BS_GNU:
473     Expanded.BraceWrapping = {true, true, true, true, true, true,
474                               true, true, true, true, true};
475     break;
476   case FormatStyle::BS_WebKit:
477     Expanded.BraceWrapping.AfterFunction = true;
478     break;
479   default:
480     break;
481   }
482   return Expanded;
483 }
484 
485 FormatStyle getLLVMStyle() {
486   FormatStyle LLVMStyle;
487   LLVMStyle.Language = FormatStyle::LK_Cpp;
488   LLVMStyle.AccessModifierOffset = -2;
489   LLVMStyle.AlignEscapedNewlinesLeft = false;
490   LLVMStyle.AlignAfterOpenBracket = FormatStyle::BAS_Align;
491   LLVMStyle.AlignOperands = true;
492   LLVMStyle.AlignTrailingComments = true;
493   LLVMStyle.AlignConsecutiveAssignments = false;
494   LLVMStyle.AlignConsecutiveDeclarations = false;
495   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
496   LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
497   LLVMStyle.AllowShortBlocksOnASingleLine = false;
498   LLVMStyle.AllowShortCaseLabelsOnASingleLine = false;
499   LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
500   LLVMStyle.AllowShortLoopsOnASingleLine = false;
501   LLVMStyle.AlwaysBreakAfterReturnType = FormatStyle::RTBS_None;
502   LLVMStyle.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_None;
503   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
504   LLVMStyle.AlwaysBreakTemplateDeclarations = false;
505   LLVMStyle.BinPackParameters = true;
506   LLVMStyle.BinPackArguments = true;
507   LLVMStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_None;
508   LLVMStyle.BreakBeforeTernaryOperators = true;
509   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
510   LLVMStyle.BraceWrapping = {false, false, false, false, false, false,
511                              false, false, false, false, false};
512   LLVMStyle.BreakAfterJavaFieldAnnotations = false;
513   LLVMStyle.BreakConstructorInitializersBeforeComma = false;
514   LLVMStyle.BreakStringLiterals = true;
515   LLVMStyle.ColumnLimit = 80;
516   LLVMStyle.CommentPragmas = "^ IWYU pragma:";
517   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
518   LLVMStyle.ConstructorInitializerIndentWidth = 4;
519   LLVMStyle.ContinuationIndentWidth = 4;
520   LLVMStyle.Cpp11BracedListStyle = true;
521   LLVMStyle.DerivePointerAlignment = false;
522   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
523   LLVMStyle.ForEachMacros.push_back("foreach");
524   LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
525   LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
526   LLVMStyle.IncludeCategories = {{"^\"(llvm|llvm-c|clang|clang-c)/", 2},
527                                  {"^(<|\"(gtest|isl|json)/)", 3},
528                                  {".*", 1}};
529   LLVMStyle.IncludeIsMainRegex = "$";
530   LLVMStyle.IndentCaseLabels = false;
531   LLVMStyle.IndentWrappedFunctionNames = false;
532   LLVMStyle.IndentWidth = 2;
533   LLVMStyle.TabWidth = 8;
534   LLVMStyle.MaxEmptyLinesToKeep = 1;
535   LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
536   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
537   LLVMStyle.ObjCBlockIndentWidth = 2;
538   LLVMStyle.ObjCSpaceAfterProperty = false;
539   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
540   LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
541   LLVMStyle.SpacesBeforeTrailingComments = 1;
542   LLVMStyle.Standard = FormatStyle::LS_Cpp11;
543   LLVMStyle.UseTab = FormatStyle::UT_Never;
544   LLVMStyle.JavaScriptQuotes = FormatStyle::JSQS_Leave;
545   LLVMStyle.ReflowComments = true;
546   LLVMStyle.SpacesInParentheses = false;
547   LLVMStyle.SpacesInSquareBrackets = false;
548   LLVMStyle.SpaceInEmptyParentheses = false;
549   LLVMStyle.SpacesInContainerLiterals = true;
550   LLVMStyle.SpacesInCStyleCastParentheses = false;
551   LLVMStyle.SpaceAfterCStyleCast = false;
552   LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
553   LLVMStyle.SpaceBeforeAssignmentOperators = true;
554   LLVMStyle.SpacesInAngles = false;
555 
556   LLVMStyle.PenaltyBreakComment = 300;
557   LLVMStyle.PenaltyBreakFirstLessLess = 120;
558   LLVMStyle.PenaltyBreakString = 1000;
559   LLVMStyle.PenaltyExcessCharacter = 1000000;
560   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
561   LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
562 
563   LLVMStyle.DisableFormat = false;
564   LLVMStyle.SortIncludes = true;
565 
566   return LLVMStyle;
567 }
568 
569 FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
570   FormatStyle GoogleStyle = getLLVMStyle();
571   GoogleStyle.Language = Language;
572 
573   GoogleStyle.AccessModifierOffset = -1;
574   GoogleStyle.AlignEscapedNewlinesLeft = true;
575   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
576   GoogleStyle.AllowShortLoopsOnASingleLine = true;
577   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
578   GoogleStyle.AlwaysBreakTemplateDeclarations = true;
579   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
580   GoogleStyle.DerivePointerAlignment = true;
581   GoogleStyle.IncludeCategories = {{"^<.*\\.h>", 1}, {"^<.*", 2}, {".*", 3}};
582   GoogleStyle.IncludeIsMainRegex = "([-_](test|unittest))?$";
583   GoogleStyle.IndentCaseLabels = true;
584   GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
585   GoogleStyle.ObjCSpaceAfterProperty = false;
586   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
587   GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
588   GoogleStyle.SpacesBeforeTrailingComments = 2;
589   GoogleStyle.Standard = FormatStyle::LS_Auto;
590 
591   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
592   GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
593 
594   if (Language == FormatStyle::LK_Java) {
595     GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
596     GoogleStyle.AlignOperands = false;
597     GoogleStyle.AlignTrailingComments = false;
598     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
599     GoogleStyle.AllowShortIfStatementsOnASingleLine = false;
600     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
601     GoogleStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_NonAssignment;
602     GoogleStyle.ColumnLimit = 100;
603     GoogleStyle.SpaceAfterCStyleCast = true;
604     GoogleStyle.SpacesBeforeTrailingComments = 1;
605   } else if (Language == FormatStyle::LK_JavaScript) {
606     GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_AlwaysBreak;
607     GoogleStyle.AlignOperands = false;
608     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
609     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
610     GoogleStyle.BreakBeforeTernaryOperators = false;
611     GoogleStyle.CommentPragmas = "@(export|return|see|visibility) ";
612     GoogleStyle.MaxEmptyLinesToKeep = 3;
613     GoogleStyle.SpacesInContainerLiterals = false;
614     GoogleStyle.JavaScriptQuotes = FormatStyle::JSQS_Single;
615   } else if (Language == FormatStyle::LK_Proto) {
616     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
617     GoogleStyle.SpacesInContainerLiterals = false;
618   }
619 
620   return GoogleStyle;
621 }
622 
623 FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
624   FormatStyle ChromiumStyle = getGoogleStyle(Language);
625   if (Language == FormatStyle::LK_Java) {
626     ChromiumStyle.AllowShortIfStatementsOnASingleLine = true;
627     ChromiumStyle.BreakAfterJavaFieldAnnotations = true;
628     ChromiumStyle.ContinuationIndentWidth = 8;
629     ChromiumStyle.IndentWidth = 4;
630   } else {
631     ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
632     ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
633     ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
634     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
635     ChromiumStyle.BinPackParameters = false;
636     ChromiumStyle.DerivePointerAlignment = false;
637   }
638   ChromiumStyle.SortIncludes = false;
639   return ChromiumStyle;
640 }
641 
642 FormatStyle getMozillaStyle() {
643   FormatStyle MozillaStyle = getLLVMStyle();
644   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
645   MozillaStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
646   MozillaStyle.AlwaysBreakAfterReturnType =
647       FormatStyle::RTBS_TopLevelDefinitions;
648   MozillaStyle.AlwaysBreakAfterDefinitionReturnType =
649       FormatStyle::DRTBS_TopLevel;
650   MozillaStyle.AlwaysBreakTemplateDeclarations = true;
651   MozillaStyle.BreakBeforeBraces = FormatStyle::BS_Mozilla;
652   MozillaStyle.BreakConstructorInitializersBeforeComma = true;
653   MozillaStyle.ConstructorInitializerIndentWidth = 2;
654   MozillaStyle.ContinuationIndentWidth = 2;
655   MozillaStyle.Cpp11BracedListStyle = false;
656   MozillaStyle.IndentCaseLabels = true;
657   MozillaStyle.ObjCSpaceAfterProperty = true;
658   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
659   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
660   MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
661   return MozillaStyle;
662 }
663 
664 FormatStyle getWebKitStyle() {
665   FormatStyle Style = getLLVMStyle();
666   Style.AccessModifierOffset = -4;
667   Style.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
668   Style.AlignOperands = false;
669   Style.AlignTrailingComments = false;
670   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
671   Style.BreakBeforeBraces = FormatStyle::BS_WebKit;
672   Style.BreakConstructorInitializersBeforeComma = true;
673   Style.Cpp11BracedListStyle = false;
674   Style.ColumnLimit = 0;
675   Style.IndentWidth = 4;
676   Style.NamespaceIndentation = FormatStyle::NI_Inner;
677   Style.ObjCBlockIndentWidth = 4;
678   Style.ObjCSpaceAfterProperty = true;
679   Style.PointerAlignment = FormatStyle::PAS_Left;
680   Style.Standard = FormatStyle::LS_Cpp03;
681   return Style;
682 }
683 
684 FormatStyle getGNUStyle() {
685   FormatStyle Style = getLLVMStyle();
686   Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_All;
687   Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
688   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
689   Style.BreakBeforeBraces = FormatStyle::BS_GNU;
690   Style.BreakBeforeTernaryOperators = true;
691   Style.Cpp11BracedListStyle = false;
692   Style.ColumnLimit = 79;
693   Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
694   Style.Standard = FormatStyle::LS_Cpp03;
695   return Style;
696 }
697 
698 FormatStyle getNoStyle() {
699   FormatStyle NoStyle = getLLVMStyle();
700   NoStyle.DisableFormat = true;
701   NoStyle.SortIncludes = false;
702   return NoStyle;
703 }
704 
705 bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
706                         FormatStyle *Style) {
707   if (Name.equals_lower("llvm")) {
708     *Style = getLLVMStyle();
709   } else if (Name.equals_lower("chromium")) {
710     *Style = getChromiumStyle(Language);
711   } else if (Name.equals_lower("mozilla")) {
712     *Style = getMozillaStyle();
713   } else if (Name.equals_lower("google")) {
714     *Style = getGoogleStyle(Language);
715   } else if (Name.equals_lower("webkit")) {
716     *Style = getWebKitStyle();
717   } else if (Name.equals_lower("gnu")) {
718     *Style = getGNUStyle();
719   } else if (Name.equals_lower("none")) {
720     *Style = getNoStyle();
721   } else {
722     return false;
723   }
724 
725   Style->Language = Language;
726   return true;
727 }
728 
729 std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
730   assert(Style);
731   FormatStyle::LanguageKind Language = Style->Language;
732   assert(Language != FormatStyle::LK_None);
733   if (Text.trim().empty())
734     return make_error_code(ParseError::Error);
735 
736   std::vector<FormatStyle> Styles;
737   llvm::yaml::Input Input(Text);
738   // DocumentListTraits<vector<FormatStyle>> uses the context to get default
739   // values for the fields, keys for which are missing from the configuration.
740   // Mapping also uses the context to get the language to find the correct
741   // base style.
742   Input.setContext(Style);
743   Input >> Styles;
744   if (Input.error())
745     return Input.error();
746 
747   for (unsigned i = 0; i < Styles.size(); ++i) {
748     // Ensures that only the first configuration can skip the Language option.
749     if (Styles[i].Language == FormatStyle::LK_None && i != 0)
750       return make_error_code(ParseError::Error);
751     // Ensure that each language is configured at most once.
752     for (unsigned j = 0; j < i; ++j) {
753       if (Styles[i].Language == Styles[j].Language) {
754         DEBUG(llvm::dbgs()
755               << "Duplicate languages in the config file on positions " << j
756               << " and " << i << "\n");
757         return make_error_code(ParseError::Error);
758       }
759     }
760   }
761   // Look for a suitable configuration starting from the end, so we can
762   // find the configuration for the specific language first, and the default
763   // configuration (which can only be at slot 0) after it.
764   for (int i = Styles.size() - 1; i >= 0; --i) {
765     if (Styles[i].Language == Language ||
766         Styles[i].Language == FormatStyle::LK_None) {
767       *Style = Styles[i];
768       Style->Language = Language;
769       return make_error_code(ParseError::Success);
770     }
771   }
772   return make_error_code(ParseError::Unsuitable);
773 }
774 
775 std::string configurationAsText(const FormatStyle &Style) {
776   std::string Text;
777   llvm::raw_string_ostream Stream(Text);
778   llvm::yaml::Output Output(Stream);
779   // We use the same mapping method for input and output, so we need a non-const
780   // reference here.
781   FormatStyle NonConstStyle = expandPresets(Style);
782   Output << NonConstStyle;
783   return Stream.str();
784 }
785 
786 namespace {
787 
788 class Formatter : public TokenAnalyzer {
789 public:
790   Formatter(const Environment &Env, const FormatStyle &Style,
791             bool *IncompleteFormat)
792       : TokenAnalyzer(Env, Style), IncompleteFormat(IncompleteFormat) {}
793 
794   tooling::Replacements
795   analyze(TokenAnnotator &Annotator,
796           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
797           FormatTokenLexer &Tokens, tooling::Replacements &Result) override {
798     deriveLocalStyle(AnnotatedLines);
799     AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
800                                           AnnotatedLines.end());
801 
802     if (Style.Language == FormatStyle::LK_JavaScript &&
803         Style.JavaScriptQuotes != FormatStyle::JSQS_Leave)
804       requoteJSStringLiteral(AnnotatedLines, Result);
805 
806     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
807       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
808     }
809 
810     Annotator.setCommentLineLevels(AnnotatedLines);
811 
812     WhitespaceManager Whitespaces(
813         Env.getSourceManager(), Style,
814         inputUsesCRLF(Env.getSourceManager().getBufferData(Env.getFileID())));
815     ContinuationIndenter Indenter(Style, Tokens.getKeywords(),
816                                   Env.getSourceManager(), Whitespaces, Encoding,
817                                   BinPackInconclusiveFunctions);
818     UnwrappedLineFormatter(&Indenter, &Whitespaces, Style, Tokens.getKeywords(),
819                            IncompleteFormat)
820         .format(AnnotatedLines);
821     return Whitespaces.generateReplacements();
822   }
823 
824 private:
825   // If the last token is a double/single-quoted string literal, generates a
826   // replacement with a single/double quoted string literal, re-escaping the
827   // contents in the process.
828   void requoteJSStringLiteral(SmallVectorImpl<AnnotatedLine *> &Lines,
829                               tooling::Replacements &Result) {
830     for (AnnotatedLine *Line : Lines) {
831       requoteJSStringLiteral(Line->Children, Result);
832       if (!Line->Affected)
833         continue;
834       for (FormatToken *FormatTok = Line->First; FormatTok;
835            FormatTok = FormatTok->Next) {
836         StringRef Input = FormatTok->TokenText;
837         if (FormatTok->Finalized || !FormatTok->isStringLiteral() ||
838             // NB: testing for not starting with a double quote to avoid
839             // breaking
840             // `template strings`.
841             (Style.JavaScriptQuotes == FormatStyle::JSQS_Single &&
842              !Input.startswith("\"")) ||
843             (Style.JavaScriptQuotes == FormatStyle::JSQS_Double &&
844              !Input.startswith("\'")))
845           continue;
846 
847         // Change start and end quote.
848         bool IsSingle = Style.JavaScriptQuotes == FormatStyle::JSQS_Single;
849         SourceLocation Start = FormatTok->Tok.getLocation();
850         auto Replace = [&](SourceLocation Start, unsigned Length,
851                            StringRef ReplacementText) {
852           Result.insert(tooling::Replacement(Env.getSourceManager(), Start,
853                                              Length, ReplacementText));
854         };
855         Replace(Start, 1, IsSingle ? "'" : "\"");
856         Replace(FormatTok->Tok.getEndLoc().getLocWithOffset(-1), 1,
857                 IsSingle ? "'" : "\"");
858 
859         // Escape internal quotes.
860         size_t ColumnWidth = FormatTok->TokenText.size();
861         bool Escaped = false;
862         for (size_t i = 1; i < Input.size() - 1; i++) {
863           switch (Input[i]) {
864           case '\\':
865             if (!Escaped && i + 1 < Input.size() &&
866                 ((IsSingle && Input[i + 1] == '"') ||
867                  (!IsSingle && Input[i + 1] == '\''))) {
868               // Remove this \, it's escaping a " or ' that no longer needs
869               // escaping
870               ColumnWidth--;
871               Replace(Start.getLocWithOffset(i), 1, "");
872               continue;
873             }
874             Escaped = !Escaped;
875             break;
876           case '\"':
877           case '\'':
878             if (!Escaped && IsSingle == (Input[i] == '\'')) {
879               // Escape the quote.
880               Replace(Start.getLocWithOffset(i), 0, "\\");
881               ColumnWidth++;
882             }
883             Escaped = false;
884             break;
885           default:
886             Escaped = false;
887             break;
888           }
889         }
890 
891         // For formatting, count the number of non-escaped single quotes in them
892         // and adjust ColumnWidth to take the added escapes into account.
893         // FIXME(martinprobst): this might conflict with code breaking a long
894         // string literal (which clang-format doesn't do, yet). For that to
895         // work, this code would have to modify TokenText directly.
896         FormatTok->ColumnWidth = ColumnWidth;
897       }
898     }
899   }
900 
901   static bool inputUsesCRLF(StringRef Text) {
902     return Text.count('\r') * 2 > Text.count('\n');
903   }
904 
905   bool
906   hasCpp03IncompatibleFormat(const SmallVectorImpl<AnnotatedLine *> &Lines) {
907     for (const AnnotatedLine *Line : Lines) {
908       if (hasCpp03IncompatibleFormat(Line->Children))
909         return true;
910       for (FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next) {
911         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
912           if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
913             return true;
914           if (Tok->is(TT_TemplateCloser) &&
915               Tok->Previous->is(TT_TemplateCloser))
916             return true;
917         }
918       }
919     }
920     return false;
921   }
922 
923   int countVariableAlignments(const SmallVectorImpl<AnnotatedLine *> &Lines) {
924     int AlignmentDiff = 0;
925     for (const AnnotatedLine *Line : Lines) {
926       AlignmentDiff += countVariableAlignments(Line->Children);
927       for (FormatToken *Tok = Line->First; Tok && Tok->Next; Tok = Tok->Next) {
928         if (!Tok->is(TT_PointerOrReference))
929           continue;
930         bool SpaceBefore =
931             Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
932         bool SpaceAfter = Tok->Next->WhitespaceRange.getBegin() !=
933                           Tok->Next->WhitespaceRange.getEnd();
934         if (SpaceBefore && !SpaceAfter)
935           ++AlignmentDiff;
936         if (!SpaceBefore && SpaceAfter)
937           --AlignmentDiff;
938       }
939     }
940     return AlignmentDiff;
941   }
942 
943   void
944   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
945     bool HasBinPackedFunction = false;
946     bool HasOnePerLineFunction = false;
947     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
948       if (!AnnotatedLines[i]->First->Next)
949         continue;
950       FormatToken *Tok = AnnotatedLines[i]->First->Next;
951       while (Tok->Next) {
952         if (Tok->PackingKind == PPK_BinPacked)
953           HasBinPackedFunction = true;
954         if (Tok->PackingKind == PPK_OnePerLine)
955           HasOnePerLineFunction = true;
956 
957         Tok = Tok->Next;
958       }
959     }
960     if (Style.DerivePointerAlignment)
961       Style.PointerAlignment = countVariableAlignments(AnnotatedLines) <= 0
962                                    ? FormatStyle::PAS_Left
963                                    : FormatStyle::PAS_Right;
964     if (Style.Standard == FormatStyle::LS_Auto)
965       Style.Standard = hasCpp03IncompatibleFormat(AnnotatedLines)
966                            ? FormatStyle::LS_Cpp11
967                            : FormatStyle::LS_Cpp03;
968     BinPackInconclusiveFunctions =
969         HasBinPackedFunction || !HasOnePerLineFunction;
970   }
971 
972   bool BinPackInconclusiveFunctions;
973   bool *IncompleteFormat;
974 };
975 
976 // This class clean up the erroneous/redundant code around the given ranges in
977 // file.
978 class Cleaner : public TokenAnalyzer {
979 public:
980   Cleaner(const Environment &Env, const FormatStyle &Style)
981       : TokenAnalyzer(Env, Style),
982         DeletedTokens(FormatTokenLess(Env.getSourceManager())) {}
983 
984   // FIXME: eliminate unused parameters.
985   tooling::Replacements
986   analyze(TokenAnnotator &Annotator,
987           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
988           FormatTokenLexer &Tokens, tooling::Replacements &Result) override {
989     // FIXME: in the current implementation the granularity of affected range
990     // is an annotated line. However, this is not sufficient. Furthermore,
991     // redundant code introduced by replacements does not necessarily
992     // intercept with ranges of replacements that result in the redundancy.
993     // To determine if some redundant code is actually introduced by
994     // replacements(e.g. deletions), we need to come up with a more
995     // sophisticated way of computing affected ranges.
996     AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
997                                           AnnotatedLines.end());
998 
999     checkEmptyNamespace(AnnotatedLines);
1000 
1001     for (auto &Line : AnnotatedLines) {
1002       if (Line->Affected) {
1003         cleanupRight(Line->First, tok::comma, tok::comma);
1004         cleanupRight(Line->First, TT_CtorInitializerColon, tok::comma);
1005         cleanupLeft(Line->First, TT_CtorInitializerComma, tok::l_brace);
1006         cleanupLeft(Line->First, TT_CtorInitializerColon, tok::l_brace);
1007       }
1008     }
1009 
1010     return generateFixes();
1011   }
1012 
1013 private:
1014   bool containsOnlyComments(const AnnotatedLine &Line) {
1015     for (FormatToken *Tok = Line.First; Tok != nullptr; Tok = Tok->Next) {
1016       if (Tok->isNot(tok::comment))
1017         return false;
1018     }
1019     return true;
1020   }
1021 
1022   // Iterate through all lines and remove any empty (nested) namespaces.
1023   void checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1024     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1025       auto &Line = *AnnotatedLines[i];
1026       if (Line.startsWith(tok::kw_namespace) ||
1027           Line.startsWith(tok::kw_inline, tok::kw_namespace)) {
1028         checkEmptyNamespace(AnnotatedLines, i, i);
1029       }
1030     }
1031 
1032     for (auto Line : DeletedLines) {
1033       FormatToken *Tok = AnnotatedLines[Line]->First;
1034       while (Tok) {
1035         deleteToken(Tok);
1036         Tok = Tok->Next;
1037       }
1038     }
1039   }
1040 
1041   // The function checks if the namespace, which starts from \p CurrentLine, and
1042   // its nested namespaces are empty and delete them if they are empty. It also
1043   // sets \p NewLine to the last line checked.
1044   // Returns true if the current namespace is empty.
1045   bool checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1046                            unsigned CurrentLine, unsigned &NewLine) {
1047     unsigned InitLine = CurrentLine, End = AnnotatedLines.size();
1048     if (Style.BraceWrapping.AfterNamespace) {
1049       // If the left brace is in a new line, we should consume it first so that
1050       // it does not make the namespace non-empty.
1051       // FIXME: error handling if there is no left brace.
1052       if (!AnnotatedLines[++CurrentLine]->startsWith(tok::l_brace)) {
1053         NewLine = CurrentLine;
1054         return false;
1055       }
1056     } else if (!AnnotatedLines[CurrentLine]->endsWith(tok::l_brace)) {
1057       return false;
1058     }
1059     while (++CurrentLine < End) {
1060       if (AnnotatedLines[CurrentLine]->startsWith(tok::r_brace))
1061         break;
1062 
1063       if (AnnotatedLines[CurrentLine]->startsWith(tok::kw_namespace) ||
1064           AnnotatedLines[CurrentLine]->startsWith(tok::kw_inline,
1065                                                   tok::kw_namespace)) {
1066         if (!checkEmptyNamespace(AnnotatedLines, CurrentLine, NewLine))
1067           return false;
1068         CurrentLine = NewLine;
1069         continue;
1070       }
1071 
1072       if (containsOnlyComments(*AnnotatedLines[CurrentLine]))
1073         continue;
1074 
1075       // If there is anything other than comments or nested namespaces in the
1076       // current namespace, the namespace cannot be empty.
1077       NewLine = CurrentLine;
1078       return false;
1079     }
1080 
1081     NewLine = CurrentLine;
1082     if (CurrentLine >= End)
1083       return false;
1084 
1085     // Check if the empty namespace is actually affected by changed ranges.
1086     if (!AffectedRangeMgr.affectsCharSourceRange(CharSourceRange::getCharRange(
1087             AnnotatedLines[InitLine]->First->Tok.getLocation(),
1088             AnnotatedLines[CurrentLine]->Last->Tok.getEndLoc())))
1089       return false;
1090 
1091     for (unsigned i = InitLine; i <= CurrentLine; ++i) {
1092       DeletedLines.insert(i);
1093     }
1094 
1095     return true;
1096   }
1097 
1098   // Checks pairs {start, start->next},..., {end->previous, end} and deletes one
1099   // of the token in the pair if the left token has \p LK token kind and the
1100   // right token has \p RK token kind. If \p DeleteLeft is true, the left token
1101   // is deleted on match; otherwise, the right token is deleted.
1102   template <typename LeftKind, typename RightKind>
1103   void cleanupPair(FormatToken *Start, LeftKind LK, RightKind RK,
1104                    bool DeleteLeft) {
1105     auto NextNotDeleted = [this](const FormatToken &Tok) -> FormatToken * {
1106       for (auto *Res = Tok.Next; Res; Res = Res->Next)
1107         if (!Res->is(tok::comment) &&
1108             DeletedTokens.find(Res) == DeletedTokens.end())
1109           return Res;
1110       return nullptr;
1111     };
1112     for (auto *Left = Start; Left;) {
1113       auto *Right = NextNotDeleted(*Left);
1114       if (!Right)
1115         break;
1116       if (Left->is(LK) && Right->is(RK)) {
1117         deleteToken(DeleteLeft ? Left : Right);
1118         // If the right token is deleted, we should keep the left token
1119         // unchanged and pair it with the new right token.
1120         if (!DeleteLeft)
1121           continue;
1122       }
1123       Left = Right;
1124     }
1125   }
1126 
1127   template <typename LeftKind, typename RightKind>
1128   void cleanupLeft(FormatToken *Start, LeftKind LK, RightKind RK) {
1129     cleanupPair(Start, LK, RK, /*DeleteLeft=*/true);
1130   }
1131 
1132   template <typename LeftKind, typename RightKind>
1133   void cleanupRight(FormatToken *Start, LeftKind LK, RightKind RK) {
1134     cleanupPair(Start, LK, RK, /*DeleteLeft=*/false);
1135   }
1136 
1137   // Delete the given token.
1138   inline void deleteToken(FormatToken *Tok) {
1139     if (Tok)
1140       DeletedTokens.insert(Tok);
1141   }
1142 
1143   tooling::Replacements generateFixes() {
1144     tooling::Replacements Fixes;
1145     std::vector<FormatToken *> Tokens;
1146     std::copy(DeletedTokens.begin(), DeletedTokens.end(),
1147               std::back_inserter(Tokens));
1148 
1149     // Merge multiple continuous token deletions into one big deletion so that
1150     // the number of replacements can be reduced. This makes computing affected
1151     // ranges more efficient when we run reformat on the changed code.
1152     unsigned Idx = 0;
1153     while (Idx < Tokens.size()) {
1154       unsigned St = Idx, End = Idx;
1155       while ((End + 1) < Tokens.size() &&
1156              Tokens[End]->Next == Tokens[End + 1]) {
1157         End++;
1158       }
1159       auto SR = CharSourceRange::getCharRange(Tokens[St]->Tok.getLocation(),
1160                                               Tokens[End]->Tok.getEndLoc());
1161       Fixes.insert(tooling::Replacement(Env.getSourceManager(), SR, ""));
1162       Idx = End + 1;
1163     }
1164 
1165     return Fixes;
1166   }
1167 
1168   // Class for less-than inequality comparason for the set `RedundantTokens`.
1169   // We store tokens in the order they appear in the translation unit so that
1170   // we do not need to sort them in `generateFixes()`.
1171   struct FormatTokenLess {
1172     FormatTokenLess(const SourceManager &SM) : SM(SM) {}
1173 
1174     bool operator()(const FormatToken *LHS, const FormatToken *RHS) const {
1175       return SM.isBeforeInTranslationUnit(LHS->Tok.getLocation(),
1176                                           RHS->Tok.getLocation());
1177     }
1178     const SourceManager &SM;
1179   };
1180 
1181   // Tokens to be deleted.
1182   std::set<FormatToken *, FormatTokenLess> DeletedTokens;
1183   // The line numbers of lines to be deleted.
1184   std::set<unsigned> DeletedLines;
1185 };
1186 
1187 struct IncludeDirective {
1188   StringRef Filename;
1189   StringRef Text;
1190   unsigned Offset;
1191   int Category;
1192 };
1193 
1194 } // end anonymous namespace
1195 
1196 // Determines whether 'Ranges' intersects with ('Start', 'End').
1197 static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
1198                          unsigned End) {
1199   for (auto Range : Ranges) {
1200     if (Range.getOffset() < End &&
1201         Range.getOffset() + Range.getLength() > Start)
1202       return true;
1203   }
1204   return false;
1205 }
1206 
1207 // Sorts a block of includes given by 'Includes' alphabetically adding the
1208 // necessary replacement to 'Replaces'. 'Includes' must be in strict source
1209 // order.
1210 static void sortCppIncludes(const FormatStyle &Style,
1211                          const SmallVectorImpl<IncludeDirective> &Includes,
1212                          ArrayRef<tooling::Range> Ranges, StringRef FileName,
1213                          tooling::Replacements &Replaces, unsigned *Cursor) {
1214   if (!affectsRange(Ranges, Includes.front().Offset,
1215                     Includes.back().Offset + Includes.back().Text.size()))
1216     return;
1217   SmallVector<unsigned, 16> Indices;
1218   for (unsigned i = 0, e = Includes.size(); i != e; ++i)
1219     Indices.push_back(i);
1220   std::stable_sort(
1221       Indices.begin(), Indices.end(), [&](unsigned LHSI, unsigned RHSI) {
1222         return std::tie(Includes[LHSI].Category, Includes[LHSI].Filename) <
1223                std::tie(Includes[RHSI].Category, Includes[RHSI].Filename);
1224       });
1225 
1226   // If the #includes are out of order, we generate a single replacement fixing
1227   // the entire block. Otherwise, no replacement is generated.
1228   bool OutOfOrder = false;
1229   for (unsigned i = 1, e = Indices.size(); i != e; ++i) {
1230     if (Indices[i] != i) {
1231       OutOfOrder = true;
1232       break;
1233     }
1234   }
1235   if (!OutOfOrder)
1236     return;
1237 
1238   std::string result;
1239   bool CursorMoved = false;
1240   for (unsigned Index : Indices) {
1241     if (!result.empty())
1242       result += "\n";
1243     result += Includes[Index].Text;
1244 
1245     if (Cursor && !CursorMoved) {
1246       unsigned Start = Includes[Index].Offset;
1247       unsigned End = Start + Includes[Index].Text.size();
1248       if (*Cursor >= Start && *Cursor < End) {
1249         *Cursor = Includes.front().Offset + result.size() + *Cursor - End;
1250         CursorMoved = true;
1251       }
1252     }
1253   }
1254 
1255   // Sorting #includes shouldn't change their total number of characters.
1256   // This would otherwise mess up 'Ranges'.
1257   assert(result.size() ==
1258          Includes.back().Offset + Includes.back().Text.size() -
1259              Includes.front().Offset);
1260 
1261   Replaces.insert(tooling::Replacement(FileName, Includes.front().Offset,
1262                                        result.size(), result));
1263 }
1264 
1265 tooling::Replacements sortCppIncludes(const FormatStyle &Style, StringRef Code,
1266                                       ArrayRef<tooling::Range> Ranges,
1267                                       StringRef FileName,
1268                                       tooling::Replacements &Replaces,
1269                                       unsigned *Cursor) {
1270   unsigned Prev = 0;
1271   unsigned SearchFrom = 0;
1272   llvm::Regex IncludeRegex(
1273       R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))");
1274   SmallVector<StringRef, 4> Matches;
1275   SmallVector<IncludeDirective, 16> IncludesInBlock;
1276 
1277   // In compiled files, consider the first #include to be the main #include of
1278   // the file if it is not a system #include. This ensures that the header
1279   // doesn't have hidden dependencies
1280   // (http://llvm.org/docs/CodingStandards.html#include-style).
1281   //
1282   // FIXME: Do some sanity checking, e.g. edit distance of the base name, to fix
1283   // cases where the first #include is unlikely to be the main header.
1284   bool IsSource = FileName.endswith(".c") || FileName.endswith(".cc") ||
1285                   FileName.endswith(".cpp") || FileName.endswith(".c++") ||
1286                   FileName.endswith(".cxx") || FileName.endswith(".m") ||
1287                   FileName.endswith(".mm");
1288   StringRef FileStem = llvm::sys::path::stem(FileName);
1289   bool FirstIncludeBlock = true;
1290   bool MainIncludeFound = false;
1291 
1292   // Create pre-compiled regular expressions for the #include categories.
1293   SmallVector<llvm::Regex, 4> CategoryRegexs;
1294   for (const auto &Category : Style.IncludeCategories)
1295     CategoryRegexs.emplace_back(Category.Regex);
1296 
1297   bool FormattingOff = false;
1298 
1299   for (;;) {
1300     auto Pos = Code.find('\n', SearchFrom);
1301     StringRef Line =
1302         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
1303 
1304     StringRef Trimmed = Line.trim();
1305     if (Trimmed == "// clang-format off")
1306       FormattingOff = true;
1307     else if (Trimmed == "// clang-format on")
1308       FormattingOff = false;
1309 
1310     if (!FormattingOff && !Line.endswith("\\")) {
1311       if (IncludeRegex.match(Line, &Matches)) {
1312         StringRef IncludeName = Matches[2];
1313         int Category = INT_MAX;
1314         for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i) {
1315           if (CategoryRegexs[i].match(IncludeName)) {
1316             Category = Style.IncludeCategories[i].Priority;
1317             break;
1318           }
1319         }
1320         if (IsSource && !MainIncludeFound && Category > 0 &&
1321             FirstIncludeBlock && IncludeName.startswith("\"")) {
1322           StringRef HeaderStem =
1323               llvm::sys::path::stem(IncludeName.drop_front(1).drop_back(1));
1324           if (FileStem.startswith(HeaderStem)) {
1325             llvm::Regex MainIncludeRegex(
1326                 (HeaderStem + Style.IncludeIsMainRegex).str());
1327             if (MainIncludeRegex.match(FileStem)) {
1328               Category = 0;
1329               MainIncludeFound = true;
1330             }
1331           }
1332         }
1333         IncludesInBlock.push_back({IncludeName, Line, Prev, Category});
1334       } else if (!IncludesInBlock.empty()) {
1335         sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces,
1336                         Cursor);
1337         IncludesInBlock.clear();
1338         FirstIncludeBlock = false;
1339       }
1340       Prev = Pos + 1;
1341     }
1342     if (Pos == StringRef::npos || Pos + 1 == Code.size())
1343       break;
1344     SearchFrom = Pos + 1;
1345   }
1346   if (!IncludesInBlock.empty())
1347     sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces, Cursor);
1348   return Replaces;
1349 }
1350 
1351 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
1352                                    ArrayRef<tooling::Range> Ranges,
1353                                    StringRef FileName, unsigned *Cursor) {
1354   tooling::Replacements Replaces;
1355   if (!Style.SortIncludes)
1356     return Replaces;
1357   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript)
1358     return sortJavaScriptImports(Style, Code, Ranges, FileName);
1359   sortCppIncludes(Style, Code, Ranges, FileName, Replaces, Cursor);
1360   return Replaces;
1361 }
1362 
1363 template <typename T>
1364 static tooling::Replacements
1365 processReplacements(T ProcessFunc, StringRef Code,
1366                     const tooling::Replacements &Replaces,
1367                     const FormatStyle &Style) {
1368   if (Replaces.empty())
1369     return tooling::Replacements();
1370 
1371   std::string NewCode = applyAllReplacements(Code, Replaces);
1372   std::vector<tooling::Range> ChangedRanges =
1373       tooling::calculateChangedRanges(Replaces);
1374   StringRef FileName = Replaces.begin()->getFilePath();
1375 
1376   tooling::Replacements FormatReplaces =
1377       ProcessFunc(Style, NewCode, ChangedRanges, FileName);
1378 
1379   return mergeReplacements(Replaces, FormatReplaces);
1380 }
1381 
1382 tooling::Replacements formatReplacements(StringRef Code,
1383                                          const tooling::Replacements &Replaces,
1384                                          const FormatStyle &Style) {
1385   // We need to use lambda function here since there are two versions of
1386   // `sortIncludes`.
1387   auto SortIncludes = [](const FormatStyle &Style, StringRef Code,
1388                          std::vector<tooling::Range> Ranges,
1389                          StringRef FileName) -> tooling::Replacements {
1390     return sortIncludes(Style, Code, Ranges, FileName);
1391   };
1392   tooling::Replacements SortedReplaces =
1393       processReplacements(SortIncludes, Code, Replaces, Style);
1394 
1395   // We need to use lambda function here since there are two versions of
1396   // `reformat`.
1397   auto Reformat = [](const FormatStyle &Style, StringRef Code,
1398                      std::vector<tooling::Range> Ranges,
1399                      StringRef FileName) -> tooling::Replacements {
1400     return reformat(Style, Code, Ranges, FileName);
1401   };
1402   return processReplacements(Reformat, Code, SortedReplaces, Style);
1403 }
1404 
1405 tooling::Replacements
1406 cleanupAroundReplacements(StringRef Code, const tooling::Replacements &Replaces,
1407                           const FormatStyle &Style) {
1408   // We need to use lambda function here since there are two versions of
1409   // `cleanup`.
1410   auto Cleanup = [](const FormatStyle &Style, StringRef Code,
1411                     std::vector<tooling::Range> Ranges,
1412                     StringRef FileName) -> tooling::Replacements {
1413     return cleanup(Style, Code, Ranges, FileName);
1414   };
1415   return processReplacements(Cleanup, Code, Replaces, Style);
1416 }
1417 
1418 tooling::Replacements reformat(const FormatStyle &Style, SourceManager &SM,
1419                                FileID ID, ArrayRef<CharSourceRange> Ranges,
1420                                bool *IncompleteFormat) {
1421   FormatStyle Expanded = expandPresets(Style);
1422   if (Expanded.DisableFormat)
1423     return tooling::Replacements();
1424 
1425   Environment Env(SM, ID, Ranges);
1426   Formatter Format(Env, Expanded, IncompleteFormat);
1427   return Format.process();
1428 }
1429 
1430 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1431                                ArrayRef<tooling::Range> Ranges,
1432                                StringRef FileName, bool *IncompleteFormat) {
1433   FormatStyle Expanded = expandPresets(Style);
1434   if (Expanded.DisableFormat)
1435     return tooling::Replacements();
1436 
1437   std::unique_ptr<Environment> Env =
1438       Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
1439   Formatter Format(*Env, Expanded, IncompleteFormat);
1440   return Format.process();
1441 }
1442 
1443 tooling::Replacements cleanup(const FormatStyle &Style, SourceManager &SM,
1444                               FileID ID, ArrayRef<CharSourceRange> Ranges) {
1445   Environment Env(SM, ID, Ranges);
1446   Cleaner Clean(Env, Style);
1447   return Clean.process();
1448 }
1449 
1450 tooling::Replacements cleanup(const FormatStyle &Style, StringRef Code,
1451                               ArrayRef<tooling::Range> Ranges,
1452                               StringRef FileName) {
1453   std::unique_ptr<Environment> Env =
1454       Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
1455   Cleaner Clean(*Env, Style);
1456   return Clean.process();
1457 }
1458 
1459 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
1460   LangOptions LangOpts;
1461   LangOpts.CPlusPlus = 1;
1462   LangOpts.CPlusPlus11 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1463   LangOpts.CPlusPlus14 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1464   LangOpts.LineComment = 1;
1465   bool AlternativeOperators = Style.Language == FormatStyle::LK_Cpp;
1466   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
1467   LangOpts.Bool = 1;
1468   LangOpts.ObjC1 = 1;
1469   LangOpts.ObjC2 = 1;
1470   LangOpts.MicrosoftExt = 1;    // To get kw___try, kw___finally.
1471   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
1472   return LangOpts;
1473 }
1474 
1475 const char *StyleOptionHelpDescription =
1476     "Coding style, currently supports:\n"
1477     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
1478     "Use -style=file to load style configuration from\n"
1479     ".clang-format file located in one of the parent\n"
1480     "directories of the source file (or current\n"
1481     "directory for stdin).\n"
1482     "Use -style=\"{key: value, ...}\" to set specific\n"
1483     "parameters, e.g.:\n"
1484     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
1485 
1486 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
1487   if (FileName.endswith(".java"))
1488     return FormatStyle::LK_Java;
1489   if (FileName.endswith_lower(".js") || FileName.endswith_lower(".ts"))
1490     return FormatStyle::LK_JavaScript; // JavaScript or TypeScript.
1491   if (FileName.endswith_lower(".proto") ||
1492       FileName.endswith_lower(".protodevel"))
1493     return FormatStyle::LK_Proto;
1494   if (FileName.endswith_lower(".td"))
1495     return FormatStyle::LK_TableGen;
1496   return FormatStyle::LK_Cpp;
1497 }
1498 
1499 FormatStyle getStyle(StringRef StyleName, StringRef FileName,
1500                      StringRef FallbackStyle, vfs::FileSystem *FS) {
1501   if (!FS) {
1502     FS = vfs::getRealFileSystem().get();
1503   }
1504   FormatStyle Style = getLLVMStyle();
1505   Style.Language = getLanguageByFileName(FileName);
1506   if (!getPredefinedStyle(FallbackStyle, Style.Language, &Style)) {
1507     llvm::errs() << "Invalid fallback style \"" << FallbackStyle
1508                  << "\" using LLVM style\n";
1509     return Style;
1510   }
1511 
1512   if (StyleName.startswith("{")) {
1513     // Parse YAML/JSON style from the command line.
1514     if (std::error_code ec = parseConfiguration(StyleName, &Style)) {
1515       llvm::errs() << "Error parsing -style: " << ec.message() << ", using "
1516                    << FallbackStyle << " style\n";
1517     }
1518     return Style;
1519   }
1520 
1521   if (!StyleName.equals_lower("file")) {
1522     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
1523       llvm::errs() << "Invalid value for -style, using " << FallbackStyle
1524                    << " style\n";
1525     return Style;
1526   }
1527 
1528   // Look for .clang-format/_clang-format file in the file's parent directories.
1529   SmallString<128> UnsuitableConfigFiles;
1530   SmallString<128> Path(FileName);
1531   llvm::sys::fs::make_absolute(Path);
1532   for (StringRef Directory = Path; !Directory.empty();
1533        Directory = llvm::sys::path::parent_path(Directory)) {
1534 
1535     auto Status = FS->status(Directory);
1536     if (!Status ||
1537         Status->getType() != llvm::sys::fs::file_type::directory_file) {
1538       continue;
1539     }
1540 
1541     SmallString<128> ConfigFile(Directory);
1542 
1543     llvm::sys::path::append(ConfigFile, ".clang-format");
1544     DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1545 
1546     Status = FS->status(ConfigFile.str());
1547     bool IsFile =
1548         Status && (Status->getType() == llvm::sys::fs::file_type::regular_file);
1549     if (!IsFile) {
1550       // Try _clang-format too, since dotfiles are not commonly used on Windows.
1551       ConfigFile = Directory;
1552       llvm::sys::path::append(ConfigFile, "_clang-format");
1553       DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1554       Status = FS->status(ConfigFile.str());
1555       IsFile = Status &&
1556                (Status->getType() == llvm::sys::fs::file_type::regular_file);
1557     }
1558 
1559     if (IsFile) {
1560       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
1561           FS->getBufferForFile(ConfigFile.str());
1562       if (std::error_code EC = Text.getError()) {
1563         llvm::errs() << EC.message() << "\n";
1564         break;
1565       }
1566       if (std::error_code ec =
1567               parseConfiguration(Text.get()->getBuffer(), &Style)) {
1568         if (ec == ParseError::Unsuitable) {
1569           if (!UnsuitableConfigFiles.empty())
1570             UnsuitableConfigFiles.append(", ");
1571           UnsuitableConfigFiles.append(ConfigFile);
1572           continue;
1573         }
1574         llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message()
1575                      << "\n";
1576         break;
1577       }
1578       DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
1579       return Style;
1580     }
1581   }
1582   if (!UnsuitableConfigFiles.empty()) {
1583     llvm::errs() << "Configuration file(s) do(es) not support "
1584                  << getLanguageName(Style.Language) << ": "
1585                  << UnsuitableConfigFiles << "\n";
1586   }
1587   return Style;
1588 }
1589 
1590 } // namespace format
1591 } // namespace clang
1592