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