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 "NamespaceEndCommentsFixer.h"
21 #include "SortJavaScriptImports.h"
22 #include "TokenAnalyzer.h"
23 #include "TokenAnnotator.h"
24 #include "UnwrappedLineFormatter.h"
25 #include "UnwrappedLineParser.h"
26 #include "WhitespaceManager.h"
27 #include "clang/Basic/Diagnostic.h"
28 #include "clang/Basic/DiagnosticOptions.h"
29 #include "clang/Basic/SourceManager.h"
30 #include "clang/Basic/VirtualFileSystem.h"
31 #include "clang/Lex/Lexer.h"
32 #include "llvm/ADT/STLExtras.h"
33 #include "llvm/Support/Allocator.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/Path.h"
36 #include "llvm/Support/Regex.h"
37 #include "llvm/Support/YAMLTraits.h"
38 #include <algorithm>
39 #include <memory>
40 #include <string>
41 
42 #define DEBUG_TYPE "format-formatter"
43 
44 using clang::format::FormatStyle;
45 
46 LLVM_YAML_IS_FLOW_SEQUENCE_VECTOR(std::string)
47 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::format::FormatStyle::IncludeCategory)
48 
49 namespace llvm {
50 namespace yaml {
51 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
52   static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
53     IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
54     IO.enumCase(Value, "Java", FormatStyle::LK_Java);
55     IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
56     IO.enumCase(Value, "ObjC", FormatStyle::LK_ObjC);
57     IO.enumCase(Value, "Proto", FormatStyle::LK_Proto);
58     IO.enumCase(Value, "TableGen", FormatStyle::LK_TableGen);
59   }
60 };
61 
62 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
63   static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
64     IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03);
65     IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03);
66     IO.enumCase(Value, "Cpp11", FormatStyle::LS_Cpp11);
67     IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11);
68     IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
69   }
70 };
71 
72 template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
73   static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
74     IO.enumCase(Value, "Never", FormatStyle::UT_Never);
75     IO.enumCase(Value, "false", FormatStyle::UT_Never);
76     IO.enumCase(Value, "Always", FormatStyle::UT_Always);
77     IO.enumCase(Value, "true", FormatStyle::UT_Always);
78     IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
79     IO.enumCase(Value, "ForContinuationAndIndentation",
80                 FormatStyle::UT_ForContinuationAndIndentation);
81   }
82 };
83 
84 template <> struct ScalarEnumerationTraits<FormatStyle::JavaScriptQuoteStyle> {
85   static void enumeration(IO &IO, FormatStyle::JavaScriptQuoteStyle &Value) {
86     IO.enumCase(Value, "Leave", FormatStyle::JSQS_Leave);
87     IO.enumCase(Value, "Single", FormatStyle::JSQS_Single);
88     IO.enumCase(Value, "Double", FormatStyle::JSQS_Double);
89   }
90 };
91 
92 template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
93   static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
94     IO.enumCase(Value, "None", FormatStyle::SFS_None);
95     IO.enumCase(Value, "false", FormatStyle::SFS_None);
96     IO.enumCase(Value, "All", FormatStyle::SFS_All);
97     IO.enumCase(Value, "true", FormatStyle::SFS_All);
98     IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
99     IO.enumCase(Value, "Empty", FormatStyle::SFS_Empty);
100   }
101 };
102 
103 template <> struct ScalarEnumerationTraits<FormatStyle::BinaryOperatorStyle> {
104   static void enumeration(IO &IO, FormatStyle::BinaryOperatorStyle &Value) {
105     IO.enumCase(Value, "All", FormatStyle::BOS_All);
106     IO.enumCase(Value, "true", FormatStyle::BOS_All);
107     IO.enumCase(Value, "None", FormatStyle::BOS_None);
108     IO.enumCase(Value, "false", FormatStyle::BOS_None);
109     IO.enumCase(Value, "NonAssignment", FormatStyle::BOS_NonAssignment);
110   }
111 };
112 
113 template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
114   static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
115     IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
116     IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
117     IO.enumCase(Value, "Mozilla", FormatStyle::BS_Mozilla);
118     IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
119     IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
120     IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
121     IO.enumCase(Value, "WebKit", FormatStyle::BS_WebKit);
122     IO.enumCase(Value, "Custom", FormatStyle::BS_Custom);
123   }
124 };
125 
126 template <>
127 struct ScalarEnumerationTraits<FormatStyle::ReturnTypeBreakingStyle> {
128   static void enumeration(IO &IO, FormatStyle::ReturnTypeBreakingStyle &Value) {
129     IO.enumCase(Value, "None", FormatStyle::RTBS_None);
130     IO.enumCase(Value, "All", FormatStyle::RTBS_All);
131     IO.enumCase(Value, "TopLevel", FormatStyle::RTBS_TopLevel);
132     IO.enumCase(Value, "TopLevelDefinitions",
133                 FormatStyle::RTBS_TopLevelDefinitions);
134     IO.enumCase(Value, "AllDefinitions", FormatStyle::RTBS_AllDefinitions);
135   }
136 };
137 
138 template <>
139 struct ScalarEnumerationTraits<FormatStyle::DefinitionReturnTypeBreakingStyle> {
140   static void
141   enumeration(IO &IO, FormatStyle::DefinitionReturnTypeBreakingStyle &Value) {
142     IO.enumCase(Value, "None", FormatStyle::DRTBS_None);
143     IO.enumCase(Value, "All", FormatStyle::DRTBS_All);
144     IO.enumCase(Value, "TopLevel", FormatStyle::DRTBS_TopLevel);
145 
146     // For backward compatibility.
147     IO.enumCase(Value, "false", FormatStyle::DRTBS_None);
148     IO.enumCase(Value, "true", FormatStyle::DRTBS_All);
149   }
150 };
151 
152 template <>
153 struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
154   static void enumeration(IO &IO,
155                           FormatStyle::NamespaceIndentationKind &Value) {
156     IO.enumCase(Value, "None", FormatStyle::NI_None);
157     IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
158     IO.enumCase(Value, "All", FormatStyle::NI_All);
159   }
160 };
161 
162 template <> struct ScalarEnumerationTraits<FormatStyle::BracketAlignmentStyle> {
163   static void enumeration(IO &IO, FormatStyle::BracketAlignmentStyle &Value) {
164     IO.enumCase(Value, "Align", FormatStyle::BAS_Align);
165     IO.enumCase(Value, "DontAlign", FormatStyle::BAS_DontAlign);
166     IO.enumCase(Value, "AlwaysBreak", FormatStyle::BAS_AlwaysBreak);
167 
168     // For backward compatibility.
169     IO.enumCase(Value, "true", FormatStyle::BAS_Align);
170     IO.enumCase(Value, "false", FormatStyle::BAS_DontAlign);
171   }
172 };
173 
174 template <> struct ScalarEnumerationTraits<FormatStyle::EscapedNewlineAlignmentStyle> {
175   static void enumeration(IO &IO, FormatStyle::EscapedNewlineAlignmentStyle &Value) {
176     IO.enumCase(Value, "DontAlign", FormatStyle::ENAS_DontAlign);
177     IO.enumCase(Value, "Left", FormatStyle::ENAS_Left);
178     IO.enumCase(Value, "Right", FormatStyle::ENAS_Right);
179 
180     // For backward compatibility.
181     IO.enumCase(Value, "true", FormatStyle::ENAS_Left);
182     IO.enumCase(Value, "false", FormatStyle::ENAS_Right);
183   }
184 };
185 
186 template <> struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
187   static void enumeration(IO &IO, FormatStyle::PointerAlignmentStyle &Value) {
188     IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
189     IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
190     IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
191 
192     // For backward compatibility.
193     IO.enumCase(Value, "true", FormatStyle::PAS_Left);
194     IO.enumCase(Value, "false", FormatStyle::PAS_Right);
195   }
196 };
197 
198 template <>
199 struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
200   static void enumeration(IO &IO,
201                           FormatStyle::SpaceBeforeParensOptions &Value) {
202     IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
203     IO.enumCase(Value, "ControlStatements",
204                 FormatStyle::SBPO_ControlStatements);
205     IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
206 
207     // For backward compatibility.
208     IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
209     IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
210   }
211 };
212 
213 template <> struct MappingTraits<FormatStyle> {
214   static void mapping(IO &IO, FormatStyle &Style) {
215     // When reading, read the language first, we need it for getPredefinedStyle.
216     IO.mapOptional("Language", Style.Language);
217 
218     if (IO.outputting()) {
219       StringRef StylesArray[] = {"LLVM",    "Google", "Chromium",
220                                  "Mozilla", "WebKit", "GNU"};
221       ArrayRef<StringRef> Styles(StylesArray);
222       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
223         StringRef StyleName(Styles[i]);
224         FormatStyle PredefinedStyle;
225         if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
226             Style == PredefinedStyle) {
227           IO.mapOptional("# BasedOnStyle", StyleName);
228           break;
229         }
230       }
231     } else {
232       StringRef BasedOnStyle;
233       IO.mapOptional("BasedOnStyle", BasedOnStyle);
234       if (!BasedOnStyle.empty()) {
235         FormatStyle::LanguageKind OldLanguage = Style.Language;
236         FormatStyle::LanguageKind Language =
237             ((FormatStyle *)IO.getContext())->Language;
238         if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
239           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
240           return;
241         }
242         Style.Language = OldLanguage;
243       }
244     }
245 
246     // For backward compatibility.
247     if (!IO.outputting()) {
248       IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlines);
249       IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
250       IO.mapOptional("IndentFunctionDeclarationAfterType",
251                      Style.IndentWrappedFunctionNames);
252       IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
253       IO.mapOptional("SpaceAfterControlStatementKeyword",
254                      Style.SpaceBeforeParens);
255     }
256 
257     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
258     IO.mapOptional("AlignAfterOpenBracket", Style.AlignAfterOpenBracket);
259     IO.mapOptional("AlignConsecutiveAssignments",
260                    Style.AlignConsecutiveAssignments);
261     IO.mapOptional("AlignConsecutiveDeclarations",
262                    Style.AlignConsecutiveDeclarations);
263     IO.mapOptional("AlignEscapedNewlines", Style.AlignEscapedNewlines);
264     IO.mapOptional("AlignOperands", Style.AlignOperands);
265     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
266     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
267                    Style.AllowAllParametersOfDeclarationOnNextLine);
268     IO.mapOptional("AllowShortBlocksOnASingleLine",
269                    Style.AllowShortBlocksOnASingleLine);
270     IO.mapOptional("AllowShortCaseLabelsOnASingleLine",
271                    Style.AllowShortCaseLabelsOnASingleLine);
272     IO.mapOptional("AllowShortFunctionsOnASingleLine",
273                    Style.AllowShortFunctionsOnASingleLine);
274     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
275                    Style.AllowShortIfStatementsOnASingleLine);
276     IO.mapOptional("AllowShortLoopsOnASingleLine",
277                    Style.AllowShortLoopsOnASingleLine);
278     IO.mapOptional("AlwaysBreakAfterDefinitionReturnType",
279                    Style.AlwaysBreakAfterDefinitionReturnType);
280     IO.mapOptional("AlwaysBreakAfterReturnType",
281                    Style.AlwaysBreakAfterReturnType);
282     // If AlwaysBreakAfterDefinitionReturnType was specified but
283     // AlwaysBreakAfterReturnType was not, initialize the latter from the
284     // former for backwards compatibility.
285     if (Style.AlwaysBreakAfterDefinitionReturnType != FormatStyle::DRTBS_None &&
286         Style.AlwaysBreakAfterReturnType == FormatStyle::RTBS_None) {
287       if (Style.AlwaysBreakAfterDefinitionReturnType == FormatStyle::DRTBS_All)
288         Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
289       else if (Style.AlwaysBreakAfterDefinitionReturnType ==
290                FormatStyle::DRTBS_TopLevel)
291         Style.AlwaysBreakAfterReturnType =
292             FormatStyle::RTBS_TopLevelDefinitions;
293     }
294 
295     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
296                    Style.AlwaysBreakBeforeMultilineStrings);
297     IO.mapOptional("AlwaysBreakTemplateDeclarations",
298                    Style.AlwaysBreakTemplateDeclarations);
299     IO.mapOptional("BinPackArguments", Style.BinPackArguments);
300     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
301     IO.mapOptional("BraceWrapping", Style.BraceWrapping);
302     IO.mapOptional("BreakBeforeBinaryOperators",
303                    Style.BreakBeforeBinaryOperators);
304     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
305     IO.mapOptional("BreakBeforeTernaryOperators",
306                    Style.BreakBeforeTernaryOperators);
307     IO.mapOptional("BreakConstructorInitializersBeforeComma",
308                    Style.BreakConstructorInitializersBeforeComma);
309     IO.mapOptional("BreakAfterJavaFieldAnnotations",
310                    Style.BreakAfterJavaFieldAnnotations);
311     IO.mapOptional("BreakStringLiterals", Style.BreakStringLiterals);
312     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
313     IO.mapOptional("CommentPragmas", Style.CommentPragmas);
314     IO.mapOptional("BreakBeforeInheritanceComma",
315                    Style.BreakBeforeInheritanceComma);
316     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
317                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
318     IO.mapOptional("ConstructorInitializerIndentWidth",
319                    Style.ConstructorInitializerIndentWidth);
320     IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
321     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
322     IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
323     IO.mapOptional("DisableFormat", Style.DisableFormat);
324     IO.mapOptional("ExperimentalAutoDetectBinPacking",
325                    Style.ExperimentalAutoDetectBinPacking);
326     IO.mapOptional("FixNamespaceComments", Style.FixNamespaceComments);
327     IO.mapOptional("ForEachMacros", Style.ForEachMacros);
328     IO.mapOptional("IncludeCategories", Style.IncludeCategories);
329     IO.mapOptional("IncludeIsMainRegex", Style.IncludeIsMainRegex);
330     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
331     IO.mapOptional("IndentWidth", Style.IndentWidth);
332     IO.mapOptional("IndentWrappedFunctionNames",
333                    Style.IndentWrappedFunctionNames);
334     IO.mapOptional("JavaScriptQuotes", Style.JavaScriptQuotes);
335     IO.mapOptional("JavaScriptWrapImports", Style.JavaScriptWrapImports);
336     IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
337                    Style.KeepEmptyLinesAtTheStartOfBlocks);
338     IO.mapOptional("MacroBlockBegin", Style.MacroBlockBegin);
339     IO.mapOptional("MacroBlockEnd", Style.MacroBlockEnd);
340     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
341     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
342     IO.mapOptional("ObjCBlockIndentWidth", Style.ObjCBlockIndentWidth);
343     IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
344     IO.mapOptional("ObjCSpaceBeforeProtocolList",
345                    Style.ObjCSpaceBeforeProtocolList);
346     IO.mapOptional("PenaltyBreakAssignment",
347                    Style.PenaltyBreakAssignment);
348     IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
349                    Style.PenaltyBreakBeforeFirstCallParameter);
350     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
351     IO.mapOptional("PenaltyBreakFirstLessLess",
352                    Style.PenaltyBreakFirstLessLess);
353     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
354     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
355     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
356                    Style.PenaltyReturnTypeOnItsOwnLine);
357     IO.mapOptional("PointerAlignment", Style.PointerAlignment);
358     IO.mapOptional("ReflowComments", Style.ReflowComments);
359     IO.mapOptional("SortIncludes", Style.SortIncludes);
360     IO.mapOptional("SpaceAfterCStyleCast", Style.SpaceAfterCStyleCast);
361     IO.mapOptional("SpaceAfterTemplateKeyword", Style.SpaceAfterTemplateKeyword);
362     IO.mapOptional("SpaceBeforeAssignmentOperators",
363                    Style.SpaceBeforeAssignmentOperators);
364     IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
365     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
366     IO.mapOptional("SpacesBeforeTrailingComments",
367                    Style.SpacesBeforeTrailingComments);
368     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
369     IO.mapOptional("SpacesInContainerLiterals",
370                    Style.SpacesInContainerLiterals);
371     IO.mapOptional("SpacesInCStyleCastParentheses",
372                    Style.SpacesInCStyleCastParentheses);
373     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
374     IO.mapOptional("SpacesInSquareBrackets", Style.SpacesInSquareBrackets);
375     IO.mapOptional("Standard", Style.Standard);
376     IO.mapOptional("TabWidth", Style.TabWidth);
377     IO.mapOptional("UseTab", Style.UseTab);
378   }
379 };
380 
381 template <> struct MappingTraits<FormatStyle::BraceWrappingFlags> {
382   static void mapping(IO &IO, FormatStyle::BraceWrappingFlags &Wrapping) {
383     IO.mapOptional("AfterClass", Wrapping.AfterClass);
384     IO.mapOptional("AfterControlStatement", Wrapping.AfterControlStatement);
385     IO.mapOptional("AfterEnum", Wrapping.AfterEnum);
386     IO.mapOptional("AfterFunction", Wrapping.AfterFunction);
387     IO.mapOptional("AfterNamespace", Wrapping.AfterNamespace);
388     IO.mapOptional("AfterObjCDeclaration", Wrapping.AfterObjCDeclaration);
389     IO.mapOptional("AfterStruct", Wrapping.AfterStruct);
390     IO.mapOptional("AfterUnion", Wrapping.AfterUnion);
391     IO.mapOptional("BeforeCatch", Wrapping.BeforeCatch);
392     IO.mapOptional("BeforeElse", Wrapping.BeforeElse);
393     IO.mapOptional("IndentBraces", Wrapping.IndentBraces);
394   }
395 };
396 
397 template <> struct MappingTraits<FormatStyle::IncludeCategory> {
398   static void mapping(IO &IO, FormatStyle::IncludeCategory &Category) {
399     IO.mapOptional("Regex", Category.Regex);
400     IO.mapOptional("Priority", Category.Priority);
401   }
402 };
403 
404 // Allows to read vector<FormatStyle> while keeping default values.
405 // IO.getContext() should contain a pointer to the FormatStyle structure, that
406 // will be used to get default values for missing keys.
407 // If the first element has no Language specified, it will be treated as the
408 // default one for the following elements.
409 template <> struct DocumentListTraits<std::vector<FormatStyle>> {
410   static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
411     return Seq.size();
412   }
413   static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
414                               size_t Index) {
415     if (Index >= Seq.size()) {
416       assert(Index == Seq.size());
417       FormatStyle Template;
418       if (Seq.size() > 0 && Seq[0].Language == FormatStyle::LK_None) {
419         Template = Seq[0];
420       } else {
421         Template = *((const FormatStyle *)IO.getContext());
422         Template.Language = FormatStyle::LK_None;
423       }
424       Seq.resize(Index + 1, Template);
425     }
426     return Seq[Index];
427   }
428 };
429 } // namespace yaml
430 } // namespace llvm
431 
432 namespace clang {
433 namespace format {
434 
435 const std::error_category &getParseCategory() {
436   static ParseErrorCategory C;
437   return C;
438 }
439 std::error_code make_error_code(ParseError e) {
440   return std::error_code(static_cast<int>(e), getParseCategory());
441 }
442 
443 inline llvm::Error make_string_error(const llvm::Twine &Message) {
444   return llvm::make_error<llvm::StringError>(Message,
445                                              llvm::inconvertibleErrorCode());
446 }
447 
448 const char *ParseErrorCategory::name() const noexcept {
449   return "clang-format.parse_error";
450 }
451 
452 std::string ParseErrorCategory::message(int EV) const {
453   switch (static_cast<ParseError>(EV)) {
454   case ParseError::Success:
455     return "Success";
456   case ParseError::Error:
457     return "Invalid argument";
458   case ParseError::Unsuitable:
459     return "Unsuitable";
460   }
461   llvm_unreachable("unexpected parse error");
462 }
463 
464 static FormatStyle expandPresets(const FormatStyle &Style) {
465   if (Style.BreakBeforeBraces == FormatStyle::BS_Custom)
466     return Style;
467   FormatStyle Expanded = Style;
468   Expanded.BraceWrapping = {false, false, false, false, false, false,
469                             false, false, false, false, false};
470   switch (Style.BreakBeforeBraces) {
471   case FormatStyle::BS_Linux:
472     Expanded.BraceWrapping.AfterClass = true;
473     Expanded.BraceWrapping.AfterFunction = true;
474     Expanded.BraceWrapping.AfterNamespace = true;
475     break;
476   case FormatStyle::BS_Mozilla:
477     Expanded.BraceWrapping.AfterClass = true;
478     Expanded.BraceWrapping.AfterEnum = true;
479     Expanded.BraceWrapping.AfterFunction = true;
480     Expanded.BraceWrapping.AfterStruct = true;
481     Expanded.BraceWrapping.AfterUnion = true;
482     break;
483   case FormatStyle::BS_Stroustrup:
484     Expanded.BraceWrapping.AfterFunction = true;
485     Expanded.BraceWrapping.BeforeCatch = true;
486     Expanded.BraceWrapping.BeforeElse = true;
487     break;
488   case FormatStyle::BS_Allman:
489     Expanded.BraceWrapping.AfterClass = true;
490     Expanded.BraceWrapping.AfterControlStatement = true;
491     Expanded.BraceWrapping.AfterEnum = true;
492     Expanded.BraceWrapping.AfterFunction = true;
493     Expanded.BraceWrapping.AfterNamespace = true;
494     Expanded.BraceWrapping.AfterObjCDeclaration = true;
495     Expanded.BraceWrapping.AfterStruct = true;
496     Expanded.BraceWrapping.BeforeCatch = true;
497     Expanded.BraceWrapping.BeforeElse = true;
498     break;
499   case FormatStyle::BS_GNU:
500     Expanded.BraceWrapping = {true, true, true, true, true, true,
501                               true, true, true, true, true};
502     break;
503   case FormatStyle::BS_WebKit:
504     Expanded.BraceWrapping.AfterFunction = true;
505     break;
506   default:
507     break;
508   }
509   return Expanded;
510 }
511 
512 FormatStyle getLLVMStyle() {
513   FormatStyle LLVMStyle;
514   LLVMStyle.Language = FormatStyle::LK_Cpp;
515   LLVMStyle.AccessModifierOffset = -2;
516   LLVMStyle.AlignEscapedNewlines = FormatStyle::ENAS_Right;
517   LLVMStyle.AlignAfterOpenBracket = FormatStyle::BAS_Align;
518   LLVMStyle.AlignOperands = true;
519   LLVMStyle.AlignTrailingComments = true;
520   LLVMStyle.AlignConsecutiveAssignments = false;
521   LLVMStyle.AlignConsecutiveDeclarations = false;
522   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
523   LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
524   LLVMStyle.AllowShortBlocksOnASingleLine = false;
525   LLVMStyle.AllowShortCaseLabelsOnASingleLine = false;
526   LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
527   LLVMStyle.AllowShortLoopsOnASingleLine = false;
528   LLVMStyle.AlwaysBreakAfterReturnType = FormatStyle::RTBS_None;
529   LLVMStyle.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_None;
530   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
531   LLVMStyle.AlwaysBreakTemplateDeclarations = false;
532   LLVMStyle.BinPackParameters = true;
533   LLVMStyle.BinPackArguments = true;
534   LLVMStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_None;
535   LLVMStyle.BreakBeforeTernaryOperators = true;
536   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
537   LLVMStyle.BraceWrapping = {false, false, false, false, false, false,
538                              false, false, false, false, false};
539   LLVMStyle.BreakAfterJavaFieldAnnotations = false;
540   LLVMStyle.BreakConstructorInitializersBeforeComma = false;
541   LLVMStyle.BreakBeforeInheritanceComma = false;
542   LLVMStyle.BreakStringLiterals = true;
543   LLVMStyle.ColumnLimit = 80;
544   LLVMStyle.CommentPragmas = "^ IWYU pragma:";
545   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
546   LLVMStyle.ConstructorInitializerIndentWidth = 4;
547   LLVMStyle.ContinuationIndentWidth = 4;
548   LLVMStyle.Cpp11BracedListStyle = true;
549   LLVMStyle.DerivePointerAlignment = false;
550   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
551   LLVMStyle.FixNamespaceComments = true;
552   LLVMStyle.ForEachMacros.push_back("foreach");
553   LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
554   LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
555   LLVMStyle.IncludeCategories = {{"^\"(llvm|llvm-c|clang|clang-c)/", 2},
556                                  {"^(<|\"(gtest|isl|json)/)", 3},
557                                  {".*", 1}};
558   LLVMStyle.IncludeIsMainRegex = "$";
559   LLVMStyle.IndentCaseLabels = false;
560   LLVMStyle.IndentWrappedFunctionNames = false;
561   LLVMStyle.IndentWidth = 2;
562   LLVMStyle.JavaScriptQuotes = FormatStyle::JSQS_Leave;
563   LLVMStyle.JavaScriptWrapImports = true;
564   LLVMStyle.TabWidth = 8;
565   LLVMStyle.MaxEmptyLinesToKeep = 1;
566   LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
567   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
568   LLVMStyle.ObjCBlockIndentWidth = 2;
569   LLVMStyle.ObjCSpaceAfterProperty = false;
570   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
571   LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
572   LLVMStyle.SpacesBeforeTrailingComments = 1;
573   LLVMStyle.Standard = FormatStyle::LS_Cpp11;
574   LLVMStyle.UseTab = FormatStyle::UT_Never;
575   LLVMStyle.ReflowComments = true;
576   LLVMStyle.SpacesInParentheses = false;
577   LLVMStyle.SpacesInSquareBrackets = false;
578   LLVMStyle.SpaceInEmptyParentheses = false;
579   LLVMStyle.SpacesInContainerLiterals = true;
580   LLVMStyle.SpacesInCStyleCastParentheses = false;
581   LLVMStyle.SpaceAfterCStyleCast = false;
582   LLVMStyle.SpaceAfterTemplateKeyword = true;
583   LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
584   LLVMStyle.SpaceBeforeAssignmentOperators = true;
585   LLVMStyle.SpacesInAngles = false;
586 
587   LLVMStyle.PenaltyBreakAssignment = prec::Assignment;
588   LLVMStyle.PenaltyBreakComment = 300;
589   LLVMStyle.PenaltyBreakFirstLessLess = 120;
590   LLVMStyle.PenaltyBreakString = 1000;
591   LLVMStyle.PenaltyExcessCharacter = 1000000;
592   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
593   LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
594 
595   LLVMStyle.DisableFormat = false;
596   LLVMStyle.SortIncludes = true;
597 
598   return LLVMStyle;
599 }
600 
601 FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
602   FormatStyle GoogleStyle = getLLVMStyle();
603   GoogleStyle.Language = Language;
604 
605   GoogleStyle.AccessModifierOffset = -1;
606   GoogleStyle.AlignEscapedNewlines = FormatStyle::ENAS_Left;
607   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
608   GoogleStyle.AllowShortLoopsOnASingleLine = true;
609   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
610   GoogleStyle.AlwaysBreakTemplateDeclarations = true;
611   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
612   GoogleStyle.DerivePointerAlignment = true;
613   GoogleStyle.IncludeCategories = {{"^<.*\\.h>", 1}, {"^<.*", 2}, {".*", 3}};
614   GoogleStyle.IncludeIsMainRegex = "([-_](test|unittest))?$";
615   GoogleStyle.IndentCaseLabels = true;
616   GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
617   GoogleStyle.ObjCSpaceAfterProperty = false;
618   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
619   GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
620   GoogleStyle.SpacesBeforeTrailingComments = 2;
621   GoogleStyle.Standard = FormatStyle::LS_Auto;
622 
623   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
624   GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
625 
626   if (Language == FormatStyle::LK_Java) {
627     GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
628     GoogleStyle.AlignOperands = false;
629     GoogleStyle.AlignTrailingComments = false;
630     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
631     GoogleStyle.AllowShortIfStatementsOnASingleLine = false;
632     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
633     GoogleStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_NonAssignment;
634     GoogleStyle.ColumnLimit = 100;
635     GoogleStyle.SpaceAfterCStyleCast = true;
636     GoogleStyle.SpacesBeforeTrailingComments = 1;
637   } else if (Language == FormatStyle::LK_JavaScript) {
638     GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_AlwaysBreak;
639     GoogleStyle.AlignOperands = false;
640     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
641     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
642     GoogleStyle.BreakBeforeTernaryOperators = false;
643     // taze:, triple slash directives (`/// <...`), @tag followed by { for a lot
644     // of JSDoc tags, and @see, which is commonly followed by overlong URLs.
645     GoogleStyle.CommentPragmas =
646         "(taze:|^/[ \t]*<|(@[A-Za-z_0-9-]+[ \\t]*{)|@see)";
647     GoogleStyle.MaxEmptyLinesToKeep = 3;
648     GoogleStyle.NamespaceIndentation = FormatStyle::NI_All;
649     GoogleStyle.SpacesInContainerLiterals = false;
650     GoogleStyle.JavaScriptQuotes = FormatStyle::JSQS_Single;
651     GoogleStyle.JavaScriptWrapImports = false;
652   } else if (Language == FormatStyle::LK_Proto) {
653     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
654     GoogleStyle.SpacesInContainerLiterals = false;
655   } else if (Language == FormatStyle::LK_ObjC) {
656     GoogleStyle.ColumnLimit = 100;
657   }
658 
659   return GoogleStyle;
660 }
661 
662 FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
663   FormatStyle ChromiumStyle = getGoogleStyle(Language);
664   if (Language == FormatStyle::LK_Java) {
665     ChromiumStyle.AllowShortIfStatementsOnASingleLine = true;
666     ChromiumStyle.BreakAfterJavaFieldAnnotations = true;
667     ChromiumStyle.ContinuationIndentWidth = 8;
668     ChromiumStyle.IndentWidth = 4;
669   } else if (Language == FormatStyle::LK_JavaScript) {
670     ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
671     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
672   } else {
673     ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
674     ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
675     ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
676     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
677     ChromiumStyle.BinPackParameters = false;
678     ChromiumStyle.DerivePointerAlignment = false;
679     if (Language == FormatStyle::LK_ObjC)
680       ChromiumStyle.ColumnLimit = 80;
681   }
682   return ChromiumStyle;
683 }
684 
685 FormatStyle getMozillaStyle() {
686   FormatStyle MozillaStyle = getLLVMStyle();
687   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
688   MozillaStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
689   MozillaStyle.AlwaysBreakAfterReturnType =
690       FormatStyle::RTBS_TopLevel;
691   MozillaStyle.AlwaysBreakAfterDefinitionReturnType =
692       FormatStyle::DRTBS_TopLevel;
693   MozillaStyle.AlwaysBreakTemplateDeclarations = true;
694   MozillaStyle.BinPackParameters = false;
695   MozillaStyle.BinPackArguments = false;
696   MozillaStyle.BreakBeforeBraces = FormatStyle::BS_Mozilla;
697   MozillaStyle.BreakConstructorInitializersBeforeComma = true;
698   MozillaStyle.BreakBeforeInheritanceComma = true;
699   MozillaStyle.ConstructorInitializerIndentWidth = 2;
700   MozillaStyle.ContinuationIndentWidth = 2;
701   MozillaStyle.Cpp11BracedListStyle = false;
702   MozillaStyle.FixNamespaceComments = false;
703   MozillaStyle.IndentCaseLabels = true;
704   MozillaStyle.ObjCSpaceAfterProperty = true;
705   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
706   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
707   MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
708   MozillaStyle.SpaceAfterTemplateKeyword = false;
709   return MozillaStyle;
710 }
711 
712 FormatStyle getWebKitStyle() {
713   FormatStyle Style = getLLVMStyle();
714   Style.AccessModifierOffset = -4;
715   Style.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
716   Style.AlignOperands = false;
717   Style.AlignTrailingComments = false;
718   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
719   Style.BreakBeforeBraces = FormatStyle::BS_WebKit;
720   Style.BreakConstructorInitializersBeforeComma = true;
721   Style.Cpp11BracedListStyle = false;
722   Style.ColumnLimit = 0;
723   Style.FixNamespaceComments = false;
724   Style.IndentWidth = 4;
725   Style.NamespaceIndentation = FormatStyle::NI_Inner;
726   Style.ObjCBlockIndentWidth = 4;
727   Style.ObjCSpaceAfterProperty = true;
728   Style.PointerAlignment = FormatStyle::PAS_Left;
729   return Style;
730 }
731 
732 FormatStyle getGNUStyle() {
733   FormatStyle Style = getLLVMStyle();
734   Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_All;
735   Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
736   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
737   Style.BreakBeforeBraces = FormatStyle::BS_GNU;
738   Style.BreakBeforeTernaryOperators = true;
739   Style.Cpp11BracedListStyle = false;
740   Style.ColumnLimit = 79;
741   Style.FixNamespaceComments = false;
742   Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
743   Style.Standard = FormatStyle::LS_Cpp03;
744   return Style;
745 }
746 
747 FormatStyle getNoStyle() {
748   FormatStyle NoStyle = getLLVMStyle();
749   NoStyle.DisableFormat = true;
750   NoStyle.SortIncludes = false;
751   return NoStyle;
752 }
753 
754 bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
755                         FormatStyle *Style) {
756   if (Name.equals_lower("llvm")) {
757     *Style = getLLVMStyle();
758   } else if (Name.equals_lower("chromium")) {
759     *Style = getChromiumStyle(Language);
760   } else if (Name.equals_lower("mozilla")) {
761     *Style = getMozillaStyle();
762   } else if (Name.equals_lower("google")) {
763     *Style = getGoogleStyle(Language);
764   } else if (Name.equals_lower("webkit")) {
765     *Style = getWebKitStyle();
766   } else if (Name.equals_lower("gnu")) {
767     *Style = getGNUStyle();
768   } else if (Name.equals_lower("none")) {
769     *Style = getNoStyle();
770   } else {
771     return false;
772   }
773 
774   Style->Language = Language;
775   return true;
776 }
777 
778 std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
779   assert(Style);
780   FormatStyle::LanguageKind Language = Style->Language;
781   assert(Language != FormatStyle::LK_None);
782   if (Text.trim().empty())
783     return make_error_code(ParseError::Error);
784 
785   std::vector<FormatStyle> Styles;
786   llvm::yaml::Input Input(Text);
787   // DocumentListTraits<vector<FormatStyle>> uses the context to get default
788   // values for the fields, keys for which are missing from the configuration.
789   // Mapping also uses the context to get the language to find the correct
790   // base style.
791   Input.setContext(Style);
792   Input >> Styles;
793   if (Input.error())
794     return Input.error();
795 
796   for (unsigned i = 0; i < Styles.size(); ++i) {
797     // Ensures that only the first configuration can skip the Language option.
798     if (Styles[i].Language == FormatStyle::LK_None && i != 0)
799       return make_error_code(ParseError::Error);
800     // Ensure that each language is configured at most once.
801     for (unsigned j = 0; j < i; ++j) {
802       if (Styles[i].Language == Styles[j].Language) {
803         DEBUG(llvm::dbgs()
804               << "Duplicate languages in the config file on positions " << j
805               << " and " << i << "\n");
806         return make_error_code(ParseError::Error);
807       }
808     }
809   }
810   // Look for a suitable configuration starting from the end, so we can
811   // find the configuration for the specific language first, and the default
812   // configuration (which can only be at slot 0) after it.
813   for (int i = Styles.size() - 1; i >= 0; --i) {
814     if (Styles[i].Language == Language ||
815         Styles[i].Language == FormatStyle::LK_None) {
816       *Style = Styles[i];
817       Style->Language = Language;
818       return make_error_code(ParseError::Success);
819     }
820   }
821   return make_error_code(ParseError::Unsuitable);
822 }
823 
824 std::string configurationAsText(const FormatStyle &Style) {
825   std::string Text;
826   llvm::raw_string_ostream Stream(Text);
827   llvm::yaml::Output Output(Stream);
828   // We use the same mapping method for input and output, so we need a non-const
829   // reference here.
830   FormatStyle NonConstStyle = expandPresets(Style);
831   Output << NonConstStyle;
832   return Stream.str();
833 }
834 
835 namespace {
836 
837 class JavaScriptRequoter : public TokenAnalyzer {
838 public:
839   JavaScriptRequoter(const Environment &Env, const FormatStyle &Style)
840       : TokenAnalyzer(Env, Style) {}
841 
842   tooling::Replacements
843   analyze(TokenAnnotator &Annotator,
844           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
845           FormatTokenLexer &Tokens) override {
846     AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
847                                           AnnotatedLines.end());
848     tooling::Replacements Result;
849     requoteJSStringLiteral(AnnotatedLines, Result);
850     return Result;
851   }
852 
853 private:
854   // Replaces double/single-quoted string literal as appropriate, re-escaping
855   // the contents in the process.
856   void requoteJSStringLiteral(SmallVectorImpl<AnnotatedLine *> &Lines,
857                               tooling::Replacements &Result) {
858     for (AnnotatedLine *Line : Lines) {
859       requoteJSStringLiteral(Line->Children, Result);
860       if (!Line->Affected)
861         continue;
862       for (FormatToken *FormatTok = Line->First; FormatTok;
863            FormatTok = FormatTok->Next) {
864         StringRef Input = FormatTok->TokenText;
865         if (FormatTok->Finalized || !FormatTok->isStringLiteral() ||
866             // NB: testing for not starting with a double quote to avoid
867             // breaking `template strings`.
868             (Style.JavaScriptQuotes == FormatStyle::JSQS_Single &&
869              !Input.startswith("\"")) ||
870             (Style.JavaScriptQuotes == FormatStyle::JSQS_Double &&
871              !Input.startswith("\'")))
872           continue;
873 
874         // Change start and end quote.
875         bool IsSingle = Style.JavaScriptQuotes == FormatStyle::JSQS_Single;
876         SourceLocation Start = FormatTok->Tok.getLocation();
877         auto Replace = [&](SourceLocation Start, unsigned Length,
878                            StringRef ReplacementText) {
879           auto Err = Result.add(tooling::Replacement(
880               Env.getSourceManager(), Start, Length, ReplacementText));
881           // FIXME: handle error. For now, print error message and skip the
882           // replacement for release version.
883           if (Err) {
884             llvm::errs() << llvm::toString(std::move(Err)) << "\n";
885             assert(false);
886           }
887         };
888         Replace(Start, 1, IsSingle ? "'" : "\"");
889         Replace(FormatTok->Tok.getEndLoc().getLocWithOffset(-1), 1,
890                 IsSingle ? "'" : "\"");
891 
892         // Escape internal quotes.
893         bool Escaped = false;
894         for (size_t i = 1; i < Input.size() - 1; i++) {
895           switch (Input[i]) {
896           case '\\':
897             if (!Escaped && i + 1 < Input.size() &&
898                 ((IsSingle && Input[i + 1] == '"') ||
899                  (!IsSingle && Input[i + 1] == '\''))) {
900               // Remove this \, it's escaping a " or ' that no longer needs
901               // escaping
902               Replace(Start.getLocWithOffset(i), 1, "");
903               continue;
904             }
905             Escaped = !Escaped;
906             break;
907           case '\"':
908           case '\'':
909             if (!Escaped && IsSingle == (Input[i] == '\'')) {
910               // Escape the quote.
911               Replace(Start.getLocWithOffset(i), 0, "\\");
912             }
913             Escaped = false;
914             break;
915           default:
916             Escaped = false;
917             break;
918           }
919         }
920       }
921     }
922   }
923 };
924 
925 class Formatter : public TokenAnalyzer {
926 public:
927   Formatter(const Environment &Env, const FormatStyle &Style,
928             FormattingAttemptStatus *Status)
929       : TokenAnalyzer(Env, Style), Status(Status) {}
930 
931   tooling::Replacements
932   analyze(TokenAnnotator &Annotator,
933           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
934           FormatTokenLexer &Tokens) override {
935     tooling::Replacements Result;
936     deriveLocalStyle(AnnotatedLines);
937     AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
938                                           AnnotatedLines.end());
939     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
940       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
941     }
942     Annotator.setCommentLineLevels(AnnotatedLines);
943 
944     WhitespaceManager Whitespaces(
945         Env.getSourceManager(), Style,
946         inputUsesCRLF(Env.getSourceManager().getBufferData(Env.getFileID())));
947     ContinuationIndenter Indenter(Style, Tokens.getKeywords(),
948                                   Env.getSourceManager(), Whitespaces, Encoding,
949                                   BinPackInconclusiveFunctions);
950     UnwrappedLineFormatter(&Indenter, &Whitespaces, Style, Tokens.getKeywords(),
951                            Env.getSourceManager(), Status)
952         .format(AnnotatedLines);
953     for (const auto &R : Whitespaces.generateReplacements())
954       if (Result.add(R))
955         return Result;
956     return Result;
957   }
958 
959 private:
960 
961   static bool inputUsesCRLF(StringRef Text) {
962     return Text.count('\r') * 2 > Text.count('\n');
963   }
964 
965   bool
966   hasCpp03IncompatibleFormat(const SmallVectorImpl<AnnotatedLine *> &Lines) {
967     for (const AnnotatedLine *Line : Lines) {
968       if (hasCpp03IncompatibleFormat(Line->Children))
969         return true;
970       for (FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next) {
971         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
972           if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
973             return true;
974           if (Tok->is(TT_TemplateCloser) &&
975               Tok->Previous->is(TT_TemplateCloser))
976             return true;
977         }
978       }
979     }
980     return false;
981   }
982 
983   int countVariableAlignments(const SmallVectorImpl<AnnotatedLine *> &Lines) {
984     int AlignmentDiff = 0;
985     for (const AnnotatedLine *Line : Lines) {
986       AlignmentDiff += countVariableAlignments(Line->Children);
987       for (FormatToken *Tok = Line->First; Tok && Tok->Next; Tok = Tok->Next) {
988         if (!Tok->is(TT_PointerOrReference))
989           continue;
990         bool SpaceBefore =
991             Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
992         bool SpaceAfter = Tok->Next->WhitespaceRange.getBegin() !=
993                           Tok->Next->WhitespaceRange.getEnd();
994         if (SpaceBefore && !SpaceAfter)
995           ++AlignmentDiff;
996         if (!SpaceBefore && SpaceAfter)
997           --AlignmentDiff;
998       }
999     }
1000     return AlignmentDiff;
1001   }
1002 
1003   void
1004   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1005     bool HasBinPackedFunction = false;
1006     bool HasOnePerLineFunction = false;
1007     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1008       if (!AnnotatedLines[i]->First->Next)
1009         continue;
1010       FormatToken *Tok = AnnotatedLines[i]->First->Next;
1011       while (Tok->Next) {
1012         if (Tok->PackingKind == PPK_BinPacked)
1013           HasBinPackedFunction = true;
1014         if (Tok->PackingKind == PPK_OnePerLine)
1015           HasOnePerLineFunction = true;
1016 
1017         Tok = Tok->Next;
1018       }
1019     }
1020     if (Style.DerivePointerAlignment)
1021       Style.PointerAlignment = countVariableAlignments(AnnotatedLines) <= 0
1022                                    ? FormatStyle::PAS_Left
1023                                    : FormatStyle::PAS_Right;
1024     if (Style.Standard == FormatStyle::LS_Auto)
1025       Style.Standard = hasCpp03IncompatibleFormat(AnnotatedLines)
1026                            ? FormatStyle::LS_Cpp11
1027                            : FormatStyle::LS_Cpp03;
1028     BinPackInconclusiveFunctions =
1029         HasBinPackedFunction || !HasOnePerLineFunction;
1030   }
1031 
1032   bool BinPackInconclusiveFunctions;
1033   FormattingAttemptStatus *Status;
1034 };
1035 
1036 // This class clean up the erroneous/redundant code around the given ranges in
1037 // file.
1038 class Cleaner : public TokenAnalyzer {
1039 public:
1040   Cleaner(const Environment &Env, const FormatStyle &Style)
1041       : TokenAnalyzer(Env, Style),
1042         DeletedTokens(FormatTokenLess(Env.getSourceManager())) {}
1043 
1044   // FIXME: eliminate unused parameters.
1045   tooling::Replacements
1046   analyze(TokenAnnotator &Annotator,
1047           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1048           FormatTokenLexer &Tokens) override {
1049     // FIXME: in the current implementation the granularity of affected range
1050     // is an annotated line. However, this is not sufficient. Furthermore,
1051     // redundant code introduced by replacements does not necessarily
1052     // intercept with ranges of replacements that result in the redundancy.
1053     // To determine if some redundant code is actually introduced by
1054     // replacements(e.g. deletions), we need to come up with a more
1055     // sophisticated way of computing affected ranges.
1056     AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
1057                                           AnnotatedLines.end());
1058 
1059     checkEmptyNamespace(AnnotatedLines);
1060 
1061     for (auto &Line : AnnotatedLines) {
1062       if (Line->Affected) {
1063         cleanupRight(Line->First, tok::comma, tok::comma);
1064         cleanupRight(Line->First, TT_CtorInitializerColon, tok::comma);
1065         cleanupRight(Line->First, tok::l_paren, tok::comma);
1066         cleanupLeft(Line->First, tok::comma, tok::r_paren);
1067         cleanupLeft(Line->First, TT_CtorInitializerComma, tok::l_brace);
1068         cleanupLeft(Line->First, TT_CtorInitializerColon, tok::l_brace);
1069         cleanupLeft(Line->First, TT_CtorInitializerColon, tok::equal);
1070       }
1071     }
1072 
1073     return generateFixes();
1074   }
1075 
1076 private:
1077   bool containsOnlyComments(const AnnotatedLine &Line) {
1078     for (FormatToken *Tok = Line.First; Tok != nullptr; Tok = Tok->Next) {
1079       if (Tok->isNot(tok::comment))
1080         return false;
1081     }
1082     return true;
1083   }
1084 
1085   // Iterate through all lines and remove any empty (nested) namespaces.
1086   void checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1087     std::set<unsigned> DeletedLines;
1088     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1089       auto &Line = *AnnotatedLines[i];
1090       if (Line.startsWith(tok::kw_namespace) ||
1091           Line.startsWith(tok::kw_inline, tok::kw_namespace)) {
1092         checkEmptyNamespace(AnnotatedLines, i, i, DeletedLines);
1093       }
1094     }
1095 
1096     for (auto Line : DeletedLines) {
1097       FormatToken *Tok = AnnotatedLines[Line]->First;
1098       while (Tok) {
1099         deleteToken(Tok);
1100         Tok = Tok->Next;
1101       }
1102     }
1103   }
1104 
1105   // The function checks if the namespace, which starts from \p CurrentLine, and
1106   // its nested namespaces are empty and delete them if they are empty. It also
1107   // sets \p NewLine to the last line checked.
1108   // Returns true if the current namespace is empty.
1109   bool checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1110                            unsigned CurrentLine, unsigned &NewLine,
1111                            std::set<unsigned> &DeletedLines) {
1112     unsigned InitLine = CurrentLine, End = AnnotatedLines.size();
1113     if (Style.BraceWrapping.AfterNamespace) {
1114       // If the left brace is in a new line, we should consume it first so that
1115       // it does not make the namespace non-empty.
1116       // FIXME: error handling if there is no left brace.
1117       if (!AnnotatedLines[++CurrentLine]->startsWith(tok::l_brace)) {
1118         NewLine = CurrentLine;
1119         return false;
1120       }
1121     } else if (!AnnotatedLines[CurrentLine]->endsWith(tok::l_brace)) {
1122       return false;
1123     }
1124     while (++CurrentLine < End) {
1125       if (AnnotatedLines[CurrentLine]->startsWith(tok::r_brace))
1126         break;
1127 
1128       if (AnnotatedLines[CurrentLine]->startsWith(tok::kw_namespace) ||
1129           AnnotatedLines[CurrentLine]->startsWith(tok::kw_inline,
1130                                                   tok::kw_namespace)) {
1131         if (!checkEmptyNamespace(AnnotatedLines, CurrentLine, NewLine,
1132                                  DeletedLines))
1133           return false;
1134         CurrentLine = NewLine;
1135         continue;
1136       }
1137 
1138       if (containsOnlyComments(*AnnotatedLines[CurrentLine]))
1139         continue;
1140 
1141       // If there is anything other than comments or nested namespaces in the
1142       // current namespace, the namespace cannot be empty.
1143       NewLine = CurrentLine;
1144       return false;
1145     }
1146 
1147     NewLine = CurrentLine;
1148     if (CurrentLine >= End)
1149       return false;
1150 
1151     // Check if the empty namespace is actually affected by changed ranges.
1152     if (!AffectedRangeMgr.affectsCharSourceRange(CharSourceRange::getCharRange(
1153             AnnotatedLines[InitLine]->First->Tok.getLocation(),
1154             AnnotatedLines[CurrentLine]->Last->Tok.getEndLoc())))
1155       return false;
1156 
1157     for (unsigned i = InitLine; i <= CurrentLine; ++i) {
1158       DeletedLines.insert(i);
1159     }
1160 
1161     return true;
1162   }
1163 
1164   // Checks pairs {start, start->next},..., {end->previous, end} and deletes one
1165   // of the token in the pair if the left token has \p LK token kind and the
1166   // right token has \p RK token kind. If \p DeleteLeft is true, the left token
1167   // is deleted on match; otherwise, the right token is deleted.
1168   template <typename LeftKind, typename RightKind>
1169   void cleanupPair(FormatToken *Start, LeftKind LK, RightKind RK,
1170                    bool DeleteLeft) {
1171     auto NextNotDeleted = [this](const FormatToken &Tok) -> FormatToken * {
1172       for (auto *Res = Tok.Next; Res; Res = Res->Next)
1173         if (!Res->is(tok::comment) &&
1174             DeletedTokens.find(Res) == DeletedTokens.end())
1175           return Res;
1176       return nullptr;
1177     };
1178     for (auto *Left = Start; Left;) {
1179       auto *Right = NextNotDeleted(*Left);
1180       if (!Right)
1181         break;
1182       if (Left->is(LK) && Right->is(RK)) {
1183         deleteToken(DeleteLeft ? Left : Right);
1184         for (auto *Tok = Left->Next; Tok && Tok != Right; Tok = Tok->Next)
1185           deleteToken(Tok);
1186         // If the right token is deleted, we should keep the left token
1187         // unchanged and pair it with the new right token.
1188         if (!DeleteLeft)
1189           continue;
1190       }
1191       Left = Right;
1192     }
1193   }
1194 
1195   template <typename LeftKind, typename RightKind>
1196   void cleanupLeft(FormatToken *Start, LeftKind LK, RightKind RK) {
1197     cleanupPair(Start, LK, RK, /*DeleteLeft=*/true);
1198   }
1199 
1200   template <typename LeftKind, typename RightKind>
1201   void cleanupRight(FormatToken *Start, LeftKind LK, RightKind RK) {
1202     cleanupPair(Start, LK, RK, /*DeleteLeft=*/false);
1203   }
1204 
1205   // Delete the given token.
1206   inline void deleteToken(FormatToken *Tok) {
1207     if (Tok)
1208       DeletedTokens.insert(Tok);
1209   }
1210 
1211   tooling::Replacements generateFixes() {
1212     tooling::Replacements Fixes;
1213     std::vector<FormatToken *> Tokens;
1214     std::copy(DeletedTokens.begin(), DeletedTokens.end(),
1215               std::back_inserter(Tokens));
1216 
1217     // Merge multiple continuous token deletions into one big deletion so that
1218     // the number of replacements can be reduced. This makes computing affected
1219     // ranges more efficient when we run reformat on the changed code.
1220     unsigned Idx = 0;
1221     while (Idx < Tokens.size()) {
1222       unsigned St = Idx, End = Idx;
1223       while ((End + 1) < Tokens.size() &&
1224              Tokens[End]->Next == Tokens[End + 1]) {
1225         End++;
1226       }
1227       auto SR = CharSourceRange::getCharRange(Tokens[St]->Tok.getLocation(),
1228                                               Tokens[End]->Tok.getEndLoc());
1229       auto Err =
1230           Fixes.add(tooling::Replacement(Env.getSourceManager(), SR, ""));
1231       // FIXME: better error handling. for now just print error message and skip
1232       // for the release version.
1233       if (Err) {
1234         llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1235         assert(false && "Fixes must not conflict!");
1236       }
1237       Idx = End + 1;
1238     }
1239 
1240     return Fixes;
1241   }
1242 
1243   // Class for less-than inequality comparason for the set `RedundantTokens`.
1244   // We store tokens in the order they appear in the translation unit so that
1245   // we do not need to sort them in `generateFixes()`.
1246   struct FormatTokenLess {
1247     FormatTokenLess(const SourceManager &SM) : SM(SM) {}
1248 
1249     bool operator()(const FormatToken *LHS, const FormatToken *RHS) const {
1250       return SM.isBeforeInTranslationUnit(LHS->Tok.getLocation(),
1251                                           RHS->Tok.getLocation());
1252     }
1253     const SourceManager &SM;
1254   };
1255 
1256   // Tokens to be deleted.
1257   std::set<FormatToken *, FormatTokenLess> DeletedTokens;
1258 };
1259 
1260 struct IncludeDirective {
1261   StringRef Filename;
1262   StringRef Text;
1263   unsigned Offset;
1264   int Category;
1265 };
1266 
1267 } // end anonymous namespace
1268 
1269 // Determines whether 'Ranges' intersects with ('Start', 'End').
1270 static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
1271                          unsigned End) {
1272   for (auto Range : Ranges) {
1273     if (Range.getOffset() < End &&
1274         Range.getOffset() + Range.getLength() > Start)
1275       return true;
1276   }
1277   return false;
1278 }
1279 
1280 // Returns a pair (Index, OffsetToEOL) describing the position of the cursor
1281 // before sorting/deduplicating. Index is the index of the include under the
1282 // cursor in the original set of includes. If this include has duplicates, it is
1283 // the index of the first of the duplicates as the others are going to be
1284 // removed. OffsetToEOL describes the cursor's position relative to the end of
1285 // its current line.
1286 // If `Cursor` is not on any #include, `Index` will be UINT_MAX.
1287 static std::pair<unsigned, unsigned>
1288 FindCursorIndex(const SmallVectorImpl<IncludeDirective> &Includes,
1289                 const SmallVectorImpl<unsigned> &Indices, unsigned Cursor) {
1290   unsigned CursorIndex = UINT_MAX;
1291   unsigned OffsetToEOL = 0;
1292   for (int i = 0, e = Includes.size(); i != e; ++i) {
1293     unsigned Start = Includes[Indices[i]].Offset;
1294     unsigned End = Start + Includes[Indices[i]].Text.size();
1295     if (!(Cursor >= Start && Cursor < End))
1296       continue;
1297     CursorIndex = Indices[i];
1298     OffsetToEOL = End - Cursor;
1299     // Put the cursor on the only remaining #include among the duplicate
1300     // #includes.
1301     while (--i >= 0 && Includes[CursorIndex].Text == Includes[Indices[i]].Text)
1302       CursorIndex = i;
1303     break;
1304   }
1305   return std::make_pair(CursorIndex, OffsetToEOL);
1306 }
1307 
1308 // Sorts and deduplicate a block of includes given by 'Includes' alphabetically
1309 // adding the necessary replacement to 'Replaces'. 'Includes' must be in strict
1310 // source order.
1311 // #include directives with the same text will be deduplicated, and only the
1312 // first #include in the duplicate #includes remains. If the `Cursor` is
1313 // provided and put on a deleted #include, it will be moved to the remaining
1314 // #include in the duplicate #includes.
1315 static void sortCppIncludes(const FormatStyle &Style,
1316                             const SmallVectorImpl<IncludeDirective> &Includes,
1317                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
1318                             tooling::Replacements &Replaces, unsigned *Cursor) {
1319   unsigned IncludesBeginOffset = Includes.front().Offset;
1320   unsigned IncludesEndOffset =
1321       Includes.back().Offset + Includes.back().Text.size();
1322   unsigned IncludesBlockSize = IncludesEndOffset - IncludesBeginOffset;
1323   if (!affectsRange(Ranges, IncludesBeginOffset, IncludesEndOffset))
1324     return;
1325   SmallVector<unsigned, 16> Indices;
1326   for (unsigned i = 0, e = Includes.size(); i != e; ++i)
1327     Indices.push_back(i);
1328   std::stable_sort(
1329       Indices.begin(), Indices.end(), [&](unsigned LHSI, unsigned RHSI) {
1330         return std::tie(Includes[LHSI].Category, Includes[LHSI].Filename) <
1331                std::tie(Includes[RHSI].Category, Includes[RHSI].Filename);
1332       });
1333   // The index of the include on which the cursor will be put after
1334   // sorting/deduplicating.
1335   unsigned CursorIndex;
1336   // The offset from cursor to the end of line.
1337   unsigned CursorToEOLOffset;
1338   if (Cursor)
1339     std::tie(CursorIndex, CursorToEOLOffset) =
1340         FindCursorIndex(Includes, Indices, *Cursor);
1341 
1342   // Deduplicate #includes.
1343   Indices.erase(std::unique(Indices.begin(), Indices.end(),
1344                             [&](unsigned LHSI, unsigned RHSI) {
1345                               return Includes[LHSI].Text == Includes[RHSI].Text;
1346                             }),
1347                 Indices.end());
1348 
1349   // If the #includes are out of order, we generate a single replacement fixing
1350   // the entire block. Otherwise, no replacement is generated.
1351   if (Indices.size() == Includes.size() &&
1352       std::is_sorted(Indices.begin(), Indices.end()))
1353     return;
1354 
1355   std::string result;
1356   for (unsigned Index : Indices) {
1357     if (!result.empty())
1358       result += "\n";
1359     result += Includes[Index].Text;
1360     if (Cursor && CursorIndex == Index)
1361       *Cursor = IncludesBeginOffset + result.size() - CursorToEOLOffset;
1362   }
1363 
1364   auto Err = Replaces.add(tooling::Replacement(
1365       FileName, Includes.front().Offset, IncludesBlockSize, result));
1366   // FIXME: better error handling. For now, just skip the replacement for the
1367   // release version.
1368   if (Err) {
1369     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1370     assert(false);
1371   }
1372 }
1373 
1374 namespace {
1375 
1376 // This class manages priorities of #include categories and calculates
1377 // priorities for headers.
1378 class IncludeCategoryManager {
1379 public:
1380   IncludeCategoryManager(const FormatStyle &Style, StringRef FileName)
1381       : Style(Style), FileName(FileName) {
1382     FileStem = llvm::sys::path::stem(FileName);
1383     for (const auto &Category : Style.IncludeCategories)
1384       CategoryRegexs.emplace_back(Category.Regex);
1385     IsMainFile = FileName.endswith(".c") || FileName.endswith(".cc") ||
1386                  FileName.endswith(".cpp") || FileName.endswith(".c++") ||
1387                  FileName.endswith(".cxx") || FileName.endswith(".m") ||
1388                  FileName.endswith(".mm");
1389   }
1390 
1391   // Returns the priority of the category which \p IncludeName belongs to.
1392   // If \p CheckMainHeader is true and \p IncludeName is a main header, returns
1393   // 0. Otherwise, returns the priority of the matching category or INT_MAX.
1394   int getIncludePriority(StringRef IncludeName, bool CheckMainHeader) {
1395     int Ret = INT_MAX;
1396     for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i)
1397       if (CategoryRegexs[i].match(IncludeName)) {
1398         Ret = Style.IncludeCategories[i].Priority;
1399         break;
1400       }
1401     if (CheckMainHeader && IsMainFile && Ret > 0 && isMainHeader(IncludeName))
1402       Ret = 0;
1403     return Ret;
1404   }
1405 
1406 private:
1407   bool isMainHeader(StringRef IncludeName) const {
1408     if (!IncludeName.startswith("\""))
1409       return false;
1410     StringRef HeaderStem =
1411         llvm::sys::path::stem(IncludeName.drop_front(1).drop_back(1));
1412     if (FileStem.startswith(HeaderStem)) {
1413       llvm::Regex MainIncludeRegex(
1414           (HeaderStem + Style.IncludeIsMainRegex).str());
1415       if (MainIncludeRegex.match(FileStem))
1416         return true;
1417     }
1418     return false;
1419   }
1420 
1421   const FormatStyle &Style;
1422   bool IsMainFile;
1423   StringRef FileName;
1424   StringRef FileStem;
1425   SmallVector<llvm::Regex, 4> CategoryRegexs;
1426 };
1427 
1428 const char IncludeRegexPattern[] =
1429     R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
1430 
1431 } // anonymous namespace
1432 
1433 tooling::Replacements sortCppIncludes(const FormatStyle &Style, StringRef Code,
1434                                       ArrayRef<tooling::Range> Ranges,
1435                                       StringRef FileName,
1436                                       tooling::Replacements &Replaces,
1437                                       unsigned *Cursor) {
1438   unsigned Prev = 0;
1439   unsigned SearchFrom = 0;
1440   llvm::Regex IncludeRegex(IncludeRegexPattern);
1441   SmallVector<StringRef, 4> Matches;
1442   SmallVector<IncludeDirective, 16> IncludesInBlock;
1443 
1444   // In compiled files, consider the first #include to be the main #include of
1445   // the file if it is not a system #include. This ensures that the header
1446   // doesn't have hidden dependencies
1447   // (http://llvm.org/docs/CodingStandards.html#include-style).
1448   //
1449   // FIXME: Do some sanity checking, e.g. edit distance of the base name, to fix
1450   // cases where the first #include is unlikely to be the main header.
1451   IncludeCategoryManager Categories(Style, FileName);
1452   bool FirstIncludeBlock = true;
1453   bool MainIncludeFound = false;
1454   bool FormattingOff = false;
1455 
1456   for (;;) {
1457     auto Pos = Code.find('\n', SearchFrom);
1458     StringRef Line =
1459         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
1460 
1461     StringRef Trimmed = Line.trim();
1462     if (Trimmed == "// clang-format off")
1463       FormattingOff = true;
1464     else if (Trimmed == "// clang-format on")
1465       FormattingOff = false;
1466 
1467     if (!FormattingOff && !Line.endswith("\\")) {
1468       if (IncludeRegex.match(Line, &Matches)) {
1469         StringRef IncludeName = Matches[2];
1470         int Category = Categories.getIncludePriority(
1471             IncludeName,
1472             /*CheckMainHeader=*/!MainIncludeFound && FirstIncludeBlock);
1473         if (Category == 0)
1474           MainIncludeFound = true;
1475         IncludesInBlock.push_back({IncludeName, Line, Prev, Category});
1476       } else if (!IncludesInBlock.empty()) {
1477         sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces,
1478                         Cursor);
1479         IncludesInBlock.clear();
1480         FirstIncludeBlock = false;
1481       }
1482       Prev = Pos + 1;
1483     }
1484     if (Pos == StringRef::npos || Pos + 1 == Code.size())
1485       break;
1486     SearchFrom = Pos + 1;
1487   }
1488   if (!IncludesInBlock.empty())
1489     sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces, Cursor);
1490   return Replaces;
1491 }
1492 
1493 bool isMpegTS(StringRef Code) {
1494   // MPEG transport streams use the ".ts" file extension. clang-format should
1495   // not attempt to format those. MPEG TS' frame format starts with 0x47 every
1496   // 189 bytes - detect that and return.
1497   return Code.size() > 188 && Code[0] == 0x47 && Code[188] == 0x47;
1498 }
1499 
1500 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
1501                                    ArrayRef<tooling::Range> Ranges,
1502                                    StringRef FileName, unsigned *Cursor) {
1503   tooling::Replacements Replaces;
1504   if (!Style.SortIncludes)
1505     return Replaces;
1506   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript &&
1507       isMpegTS(Code))
1508     return Replaces;
1509   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript)
1510     return sortJavaScriptImports(Style, Code, Ranges, FileName);
1511   sortCppIncludes(Style, Code, Ranges, FileName, Replaces, Cursor);
1512   return Replaces;
1513 }
1514 
1515 template <typename T>
1516 static llvm::Expected<tooling::Replacements>
1517 processReplacements(T ProcessFunc, StringRef Code,
1518                     const tooling::Replacements &Replaces,
1519                     const FormatStyle &Style) {
1520   if (Replaces.empty())
1521     return tooling::Replacements();
1522 
1523   auto NewCode = applyAllReplacements(Code, Replaces);
1524   if (!NewCode)
1525     return NewCode.takeError();
1526   std::vector<tooling::Range> ChangedRanges = Replaces.getAffectedRanges();
1527   StringRef FileName = Replaces.begin()->getFilePath();
1528 
1529   tooling::Replacements FormatReplaces =
1530       ProcessFunc(Style, *NewCode, ChangedRanges, FileName);
1531 
1532   return Replaces.merge(FormatReplaces);
1533 }
1534 
1535 llvm::Expected<tooling::Replacements>
1536 formatReplacements(StringRef Code, const tooling::Replacements &Replaces,
1537                    const FormatStyle &Style) {
1538   // We need to use lambda function here since there are two versions of
1539   // `sortIncludes`.
1540   auto SortIncludes = [](const FormatStyle &Style, StringRef Code,
1541                          std::vector<tooling::Range> Ranges,
1542                          StringRef FileName) -> tooling::Replacements {
1543     return sortIncludes(Style, Code, Ranges, FileName);
1544   };
1545   auto SortedReplaces =
1546       processReplacements(SortIncludes, Code, Replaces, Style);
1547   if (!SortedReplaces)
1548     return SortedReplaces.takeError();
1549 
1550   // We need to use lambda function here since there are two versions of
1551   // `reformat`.
1552   auto Reformat = [](const FormatStyle &Style, StringRef Code,
1553                      std::vector<tooling::Range> Ranges,
1554                      StringRef FileName) -> tooling::Replacements {
1555     return reformat(Style, Code, Ranges, FileName);
1556   };
1557   return processReplacements(Reformat, Code, *SortedReplaces, Style);
1558 }
1559 
1560 namespace {
1561 
1562 inline bool isHeaderInsertion(const tooling::Replacement &Replace) {
1563   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 0 &&
1564          llvm::Regex(IncludeRegexPattern).match(Replace.getReplacementText());
1565 }
1566 
1567 inline bool isHeaderDeletion(const tooling::Replacement &Replace) {
1568   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 1;
1569 }
1570 
1571 // Returns the offset after skipping a sequence of tokens, matched by \p
1572 // GetOffsetAfterSequence, from the start of the code.
1573 // \p GetOffsetAfterSequence should be a function that matches a sequence of
1574 // tokens and returns an offset after the sequence.
1575 unsigned getOffsetAfterTokenSequence(
1576     StringRef FileName, StringRef Code, const FormatStyle &Style,
1577     llvm::function_ref<unsigned(const SourceManager &, Lexer &, Token &)>
1578         GetOffsetAfterSequence) {
1579   std::unique_ptr<Environment> Env =
1580       Environment::CreateVirtualEnvironment(Code, FileName, /*Ranges=*/{});
1581   const SourceManager &SourceMgr = Env->getSourceManager();
1582   Lexer Lex(Env->getFileID(), SourceMgr.getBuffer(Env->getFileID()), SourceMgr,
1583             getFormattingLangOpts(Style));
1584   Token Tok;
1585   // Get the first token.
1586   Lex.LexFromRawLexer(Tok);
1587   return GetOffsetAfterSequence(SourceMgr, Lex, Tok);
1588 }
1589 
1590 // Check if a sequence of tokens is like "#<Name> <raw_identifier>". If it is,
1591 // \p Tok will be the token after this directive; otherwise, it can be any token
1592 // after the given \p Tok (including \p Tok).
1593 bool checkAndConsumeDirectiveWithName(Lexer &Lex, StringRef Name, Token &Tok) {
1594   bool Matched = Tok.is(tok::hash) && !Lex.LexFromRawLexer(Tok) &&
1595                  Tok.is(tok::raw_identifier) &&
1596                  Tok.getRawIdentifier() == Name && !Lex.LexFromRawLexer(Tok) &&
1597                  Tok.is(tok::raw_identifier);
1598   if (Matched)
1599     Lex.LexFromRawLexer(Tok);
1600   return Matched;
1601 }
1602 
1603 void skipComments(Lexer &Lex, Token &Tok) {
1604   while (Tok.is(tok::comment))
1605     if (Lex.LexFromRawLexer(Tok))
1606       return;
1607 }
1608 
1609 // Returns the offset after header guard directives and any comments
1610 // before/after header guards. If no header guard presents in the code, this
1611 // will returns the offset after skipping all comments from the start of the
1612 // code.
1613 unsigned getOffsetAfterHeaderGuardsAndComments(StringRef FileName,
1614                                                StringRef Code,
1615                                                const FormatStyle &Style) {
1616   return getOffsetAfterTokenSequence(
1617       FileName, Code, Style,
1618       [](const SourceManager &SM, Lexer &Lex, Token Tok) {
1619         skipComments(Lex, Tok);
1620         unsigned InitialOffset = SM.getFileOffset(Tok.getLocation());
1621         if (checkAndConsumeDirectiveWithName(Lex, "ifndef", Tok)) {
1622           skipComments(Lex, Tok);
1623           if (checkAndConsumeDirectiveWithName(Lex, "define", Tok))
1624             return SM.getFileOffset(Tok.getLocation());
1625         }
1626         return InitialOffset;
1627       });
1628 }
1629 
1630 // Check if a sequence of tokens is like
1631 //    "#include ("header.h" | <header.h>)".
1632 // If it is, \p Tok will be the token after this directive; otherwise, it can be
1633 // any token after the given \p Tok (including \p Tok).
1634 bool checkAndConsumeInclusiveDirective(Lexer &Lex, Token &Tok) {
1635   auto Matched = [&]() {
1636     Lex.LexFromRawLexer(Tok);
1637     return true;
1638   };
1639   if (Tok.is(tok::hash) && !Lex.LexFromRawLexer(Tok) &&
1640       Tok.is(tok::raw_identifier) && Tok.getRawIdentifier() == "include") {
1641     if (Lex.LexFromRawLexer(Tok))
1642       return false;
1643     if (Tok.is(tok::string_literal))
1644       return Matched();
1645     if (Tok.is(tok::less)) {
1646       while (!Lex.LexFromRawLexer(Tok) && Tok.isNot(tok::greater)) {
1647       }
1648       if (Tok.is(tok::greater))
1649         return Matched();
1650     }
1651   }
1652   return false;
1653 }
1654 
1655 // Returns the offset of the last #include directive after which a new
1656 // #include can be inserted. This ignores #include's after the #include block(s)
1657 // in the beginning of a file to avoid inserting headers into code sections
1658 // where new #include's should not be added by default.
1659 // These code sections include:
1660 //      - raw string literals (containing #include).
1661 //      - #if blocks.
1662 //      - Special #include's among declarations (e.g. functions).
1663 //
1664 // If no #include after which a new #include can be inserted, this returns the
1665 // offset after skipping all comments from the start of the code.
1666 // Inserting after an #include is not allowed if it comes after code that is not
1667 // #include (e.g. pre-processing directive that is not #include, declarations).
1668 unsigned getMaxHeaderInsertionOffset(StringRef FileName, StringRef Code,
1669                                      const FormatStyle &Style) {
1670   return getOffsetAfterTokenSequence(
1671       FileName, Code, Style,
1672       [](const SourceManager &SM, Lexer &Lex, Token Tok) {
1673         skipComments(Lex, Tok);
1674         unsigned MaxOffset = SM.getFileOffset(Tok.getLocation());
1675         while (checkAndConsumeInclusiveDirective(Lex, Tok))
1676           MaxOffset = SM.getFileOffset(Tok.getLocation());
1677         return MaxOffset;
1678       });
1679 }
1680 
1681 bool isDeletedHeader(llvm::StringRef HeaderName,
1682                      const std::set<llvm::StringRef> &HeadersToDelete) {
1683   return HeadersToDelete.count(HeaderName) ||
1684          HeadersToDelete.count(HeaderName.trim("\"<>"));
1685 }
1686 
1687 // FIXME: insert empty lines between newly created blocks.
1688 tooling::Replacements
1689 fixCppIncludeInsertions(StringRef Code, const tooling::Replacements &Replaces,
1690                         const FormatStyle &Style) {
1691   if (!Style.isCpp())
1692     return Replaces;
1693 
1694   tooling::Replacements HeaderInsertions;
1695   std::set<llvm::StringRef> HeadersToDelete;
1696   tooling::Replacements Result;
1697   for (const auto &R : Replaces) {
1698     if (isHeaderInsertion(R)) {
1699       // Replacements from \p Replaces must be conflict-free already, so we can
1700       // simply consume the error.
1701       llvm::consumeError(HeaderInsertions.add(R));
1702     } else if (isHeaderDeletion(R)) {
1703       HeadersToDelete.insert(R.getReplacementText());
1704     } else if (R.getOffset() == UINT_MAX) {
1705       llvm::errs() << "Insertions other than header #include insertion are "
1706                       "not supported! "
1707                    << R.getReplacementText() << "\n";
1708     } else {
1709       llvm::consumeError(Result.add(R));
1710     }
1711   }
1712   if (HeaderInsertions.empty() && HeadersToDelete.empty())
1713     return Replaces;
1714 
1715   llvm::Regex IncludeRegex(IncludeRegexPattern);
1716   llvm::Regex DefineRegex(R"(^[\t\ ]*#[\t\ ]*define[\t\ ]*[^\\]*$)");
1717   SmallVector<StringRef, 4> Matches;
1718 
1719   StringRef FileName = Replaces.begin()->getFilePath();
1720   IncludeCategoryManager Categories(Style, FileName);
1721 
1722   // Record the offset of the end of the last include in each category.
1723   std::map<int, int> CategoryEndOffsets;
1724   // All possible priorities.
1725   // Add 0 for main header and INT_MAX for headers that are not in any category.
1726   std::set<int> Priorities = {0, INT_MAX};
1727   for (const auto &Category : Style.IncludeCategories)
1728     Priorities.insert(Category.Priority);
1729   int FirstIncludeOffset = -1;
1730   // All new headers should be inserted after this offset.
1731   unsigned MinInsertOffset =
1732       getOffsetAfterHeaderGuardsAndComments(FileName, Code, Style);
1733   StringRef TrimmedCode = Code.drop_front(MinInsertOffset);
1734   // Max insertion offset in the original code.
1735   unsigned MaxInsertOffset =
1736       MinInsertOffset +
1737       getMaxHeaderInsertionOffset(FileName, TrimmedCode, Style);
1738   SmallVector<StringRef, 32> Lines;
1739   TrimmedCode.split(Lines, '\n');
1740   unsigned Offset = MinInsertOffset;
1741   unsigned NextLineOffset;
1742   std::set<StringRef> ExistingIncludes;
1743   for (auto Line : Lines) {
1744     NextLineOffset = std::min(Code.size(), Offset + Line.size() + 1);
1745     if (IncludeRegex.match(Line, &Matches)) {
1746       // The header name with quotes or angle brackets.
1747       StringRef IncludeName = Matches[2];
1748       ExistingIncludes.insert(IncludeName);
1749       // Only record the offset of current #include if we can insert after it.
1750       if (Offset <= MaxInsertOffset) {
1751         int Category = Categories.getIncludePriority(
1752             IncludeName, /*CheckMainHeader=*/FirstIncludeOffset < 0);
1753         CategoryEndOffsets[Category] = NextLineOffset;
1754         if (FirstIncludeOffset < 0)
1755           FirstIncludeOffset = Offset;
1756       }
1757       if (isDeletedHeader(IncludeName, HeadersToDelete)) {
1758         // If this is the last line without trailing newline, we need to make
1759         // sure we don't delete across the file boundary.
1760         unsigned Length = std::min(Line.size() + 1, Code.size() - Offset);
1761         llvm::Error Err =
1762             Result.add(tooling::Replacement(FileName, Offset, Length, ""));
1763         if (Err) {
1764           // Ignore the deletion on conflict.
1765           llvm::errs() << "Failed to add header deletion replacement for "
1766                        << IncludeName << ": " << llvm::toString(std::move(Err))
1767                        << "\n";
1768         }
1769       }
1770     }
1771     Offset = NextLineOffset;
1772   }
1773 
1774   // Populate CategoryEndOfssets:
1775   // - Ensure that CategoryEndOffset[Highest] is always populated.
1776   // - If CategoryEndOffset[Priority] isn't set, use the next higher value that
1777   //   is set, up to CategoryEndOffset[Highest].
1778   auto Highest = Priorities.begin();
1779   if (CategoryEndOffsets.find(*Highest) == CategoryEndOffsets.end()) {
1780     if (FirstIncludeOffset >= 0)
1781       CategoryEndOffsets[*Highest] = FirstIncludeOffset;
1782     else
1783       CategoryEndOffsets[*Highest] = MinInsertOffset;
1784   }
1785   // By this point, CategoryEndOffset[Highest] is always set appropriately:
1786   //  - to an appropriate location before/after existing #includes, or
1787   //  - to right after the header guard, or
1788   //  - to the beginning of the file.
1789   for (auto I = ++Priorities.begin(), E = Priorities.end(); I != E; ++I)
1790     if (CategoryEndOffsets.find(*I) == CategoryEndOffsets.end())
1791       CategoryEndOffsets[*I] = CategoryEndOffsets[*std::prev(I)];
1792 
1793   bool NeedNewLineAtEnd = !Code.empty() && Code.back() != '\n';
1794   for (const auto &R : HeaderInsertions) {
1795     auto IncludeDirective = R.getReplacementText();
1796     bool Matched = IncludeRegex.match(IncludeDirective, &Matches);
1797     assert(Matched && "Header insertion replacement must have replacement text "
1798                       "'#include ...'");
1799     (void)Matched;
1800     auto IncludeName = Matches[2];
1801     if (ExistingIncludes.find(IncludeName) != ExistingIncludes.end()) {
1802       DEBUG(llvm::dbgs() << "Skip adding existing include : " << IncludeName
1803                          << "\n");
1804       continue;
1805     }
1806     int Category =
1807         Categories.getIncludePriority(IncludeName, /*CheckMainHeader=*/true);
1808     Offset = CategoryEndOffsets[Category];
1809     std::string NewInclude = !IncludeDirective.endswith("\n")
1810                                  ? (IncludeDirective + "\n").str()
1811                                  : IncludeDirective.str();
1812     // When inserting headers at end of the code, also append '\n' to the code
1813     // if it does not end with '\n'.
1814     if (NeedNewLineAtEnd && Offset == Code.size()) {
1815       NewInclude = "\n" + NewInclude;
1816       NeedNewLineAtEnd = false;
1817     }
1818     auto NewReplace = tooling::Replacement(FileName, Offset, 0, NewInclude);
1819     auto Err = Result.add(NewReplace);
1820     if (Err) {
1821       llvm::consumeError(std::move(Err));
1822       unsigned NewOffset = Result.getShiftedCodePosition(Offset);
1823       NewReplace = tooling::Replacement(FileName, NewOffset, 0, NewInclude);
1824       Result = Result.merge(tooling::Replacements(NewReplace));
1825     }
1826   }
1827   return Result;
1828 }
1829 
1830 } // anonymous namespace
1831 
1832 llvm::Expected<tooling::Replacements>
1833 cleanupAroundReplacements(StringRef Code, const tooling::Replacements &Replaces,
1834                           const FormatStyle &Style) {
1835   // We need to use lambda function here since there are two versions of
1836   // `cleanup`.
1837   auto Cleanup = [](const FormatStyle &Style, StringRef Code,
1838                     std::vector<tooling::Range> Ranges,
1839                     StringRef FileName) -> tooling::Replacements {
1840     return cleanup(Style, Code, Ranges, FileName);
1841   };
1842   // Make header insertion replacements insert new headers into correct blocks.
1843   tooling::Replacements NewReplaces =
1844       fixCppIncludeInsertions(Code, Replaces, Style);
1845   return processReplacements(Cleanup, Code, NewReplaces, Style);
1846 }
1847 
1848 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1849                                ArrayRef<tooling::Range> Ranges,
1850                                StringRef FileName,
1851                                FormattingAttemptStatus *Status) {
1852   FormatStyle Expanded = expandPresets(Style);
1853   if (Expanded.DisableFormat)
1854     return tooling::Replacements();
1855   if (Expanded.Language == FormatStyle::LK_JavaScript && isMpegTS(Code))
1856     return tooling::Replacements();
1857   auto Env = Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
1858 
1859   auto reformatAfterApplying = [&] (TokenAnalyzer& Fixer) {
1860     tooling::Replacements Fixes = Fixer.process();
1861     if (!Fixes.empty()) {
1862       auto NewCode = applyAllReplacements(Code, Fixes);
1863       if (NewCode) {
1864         auto NewEnv = Environment::CreateVirtualEnvironment(
1865             *NewCode, FileName,
1866             tooling::calculateRangesAfterReplacements(Fixes, Ranges));
1867         Formatter Format(*NewEnv, Expanded, Status);
1868         return Fixes.merge(Format.process());
1869       }
1870     }
1871     Formatter Format(*Env, Expanded, Status);
1872     return Format.process();
1873   };
1874 
1875   if (Style.Language == FormatStyle::LK_Cpp &&
1876       Style.FixNamespaceComments) {
1877     NamespaceEndCommentsFixer CommentsFixer(*Env, Expanded);
1878     return reformatAfterApplying(CommentsFixer);
1879   }
1880 
1881   if (Style.Language == FormatStyle::LK_JavaScript &&
1882       Style.JavaScriptQuotes != FormatStyle::JSQS_Leave) {
1883     JavaScriptRequoter Requoter(*Env, Expanded);
1884     return reformatAfterApplying(Requoter);
1885   }
1886 
1887   Formatter Format(*Env, Expanded, Status);
1888   return Format.process();
1889 }
1890 
1891 tooling::Replacements cleanup(const FormatStyle &Style, StringRef Code,
1892                               ArrayRef<tooling::Range> Ranges,
1893                               StringRef FileName) {
1894   std::unique_ptr<Environment> Env =
1895       Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
1896   Cleaner Clean(*Env, Style);
1897   return Clean.process();
1898 }
1899 
1900 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1901                                ArrayRef<tooling::Range> Ranges,
1902                                StringRef FileName, bool *IncompleteFormat) {
1903   FormattingAttemptStatus Status;
1904   auto Result = reformat(Style, Code, Ranges, FileName, &Status);
1905   if (!Status.FormatComplete)
1906     *IncompleteFormat = true;
1907   return Result;
1908 }
1909 
1910 tooling::Replacements fixNamespaceEndComments(const FormatStyle &Style,
1911                                               StringRef Code,
1912                                               ArrayRef<tooling::Range> Ranges,
1913                                               StringRef FileName) {
1914   std::unique_ptr<Environment> Env =
1915       Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
1916   NamespaceEndCommentsFixer Fix(*Env, Style);
1917   return Fix.process();
1918 }
1919 
1920 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
1921   LangOptions LangOpts;
1922   LangOpts.CPlusPlus = 1;
1923   LangOpts.CPlusPlus11 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1924   LangOpts.CPlusPlus14 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1925   LangOpts.CPlusPlus1z = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1926   LangOpts.LineComment = 1;
1927   bool AlternativeOperators = Style.isCpp();
1928   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
1929   LangOpts.Bool = 1;
1930   LangOpts.ObjC1 = 1;
1931   LangOpts.ObjC2 = 1;
1932   LangOpts.MicrosoftExt = 1;    // To get kw___try, kw___finally.
1933   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
1934   return LangOpts;
1935 }
1936 
1937 const char *StyleOptionHelpDescription =
1938     "Coding style, currently supports:\n"
1939     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
1940     "Use -style=file to load style configuration from\n"
1941     ".clang-format file located in one of the parent\n"
1942     "directories of the source file (or current\n"
1943     "directory for stdin).\n"
1944     "Use -style=\"{key: value, ...}\" to set specific\n"
1945     "parameters, e.g.:\n"
1946     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
1947 
1948 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
1949   if (FileName.endswith(".java"))
1950     return FormatStyle::LK_Java;
1951   if (FileName.endswith_lower(".js") || FileName.endswith_lower(".ts"))
1952     return FormatStyle::LK_JavaScript; // JavaScript or TypeScript.
1953   if (FileName.endswith(".m") || FileName.endswith(".mm"))
1954     return FormatStyle::LK_ObjC;
1955   if (FileName.endswith_lower(".proto") ||
1956       FileName.endswith_lower(".protodevel"))
1957     return FormatStyle::LK_Proto;
1958   if (FileName.endswith_lower(".td"))
1959     return FormatStyle::LK_TableGen;
1960   return FormatStyle::LK_Cpp;
1961 }
1962 
1963 llvm::Expected<FormatStyle> getStyle(StringRef StyleName, StringRef FileName,
1964                                      StringRef FallbackStyleName,
1965                                      StringRef Code, vfs::FileSystem *FS) {
1966   if (!FS) {
1967     FS = vfs::getRealFileSystem().get();
1968   }
1969   FormatStyle Style = getLLVMStyle();
1970   Style.Language = getLanguageByFileName(FileName);
1971 
1972   // This is a very crude detection of whether a header contains ObjC code that
1973   // should be improved over time and probably be done on tokens, not one the
1974   // bare content of the file.
1975   if (Style.Language == FormatStyle::LK_Cpp && FileName.endswith(".h") &&
1976       (Code.contains("\n- (") || Code.contains("\n+ (")))
1977     Style.Language = FormatStyle::LK_ObjC;
1978 
1979   FormatStyle FallbackStyle = getNoStyle();
1980   if (!getPredefinedStyle(FallbackStyleName, Style.Language, &FallbackStyle))
1981     return make_string_error("Invalid fallback style \"" + FallbackStyleName);
1982 
1983   if (StyleName.startswith("{")) {
1984     // Parse YAML/JSON style from the command line.
1985     if (std::error_code ec = parseConfiguration(StyleName, &Style))
1986       return make_string_error("Error parsing -style: " + ec.message());
1987     return Style;
1988   }
1989 
1990   if (!StyleName.equals_lower("file")) {
1991     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
1992       return make_string_error("Invalid value for -style");
1993     return Style;
1994   }
1995 
1996   // Look for .clang-format/_clang-format file in the file's parent directories.
1997   SmallString<128> UnsuitableConfigFiles;
1998   SmallString<128> Path(FileName);
1999   if (std::error_code EC = FS->makeAbsolute(Path))
2000     return make_string_error(EC.message());
2001 
2002   for (StringRef Directory = Path; !Directory.empty();
2003        Directory = llvm::sys::path::parent_path(Directory)) {
2004 
2005     auto Status = FS->status(Directory);
2006     if (!Status ||
2007         Status->getType() != llvm::sys::fs::file_type::directory_file) {
2008       continue;
2009     }
2010 
2011     SmallString<128> ConfigFile(Directory);
2012 
2013     llvm::sys::path::append(ConfigFile, ".clang-format");
2014     DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2015 
2016     Status = FS->status(ConfigFile.str());
2017     bool FoundConfigFile =
2018         Status && (Status->getType() == llvm::sys::fs::file_type::regular_file);
2019     if (!FoundConfigFile) {
2020       // Try _clang-format too, since dotfiles are not commonly used on Windows.
2021       ConfigFile = Directory;
2022       llvm::sys::path::append(ConfigFile, "_clang-format");
2023       DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2024       Status = FS->status(ConfigFile.str());
2025       FoundConfigFile = Status && (Status->getType() ==
2026                                    llvm::sys::fs::file_type::regular_file);
2027     }
2028 
2029     if (FoundConfigFile) {
2030       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
2031           FS->getBufferForFile(ConfigFile.str());
2032       if (std::error_code EC = Text.getError())
2033         return make_string_error(EC.message());
2034       if (std::error_code ec =
2035               parseConfiguration(Text.get()->getBuffer(), &Style)) {
2036         if (ec == ParseError::Unsuitable) {
2037           if (!UnsuitableConfigFiles.empty())
2038             UnsuitableConfigFiles.append(", ");
2039           UnsuitableConfigFiles.append(ConfigFile);
2040           continue;
2041         }
2042         return make_string_error("Error reading " + ConfigFile + ": " +
2043                                  ec.message());
2044       }
2045       DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
2046       return Style;
2047     }
2048   }
2049   if (!UnsuitableConfigFiles.empty())
2050     return make_string_error("Configuration file(s) do(es) not support " +
2051                              getLanguageName(Style.Language) + ": " +
2052                              UnsuitableConfigFiles);
2053   return FallbackStyle;
2054 }
2055 
2056 } // namespace format
2057 } // namespace clang
2058