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