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