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