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 (`/// <...`), @tag followed by { for a lot
812     // of JSDoc tags, and @see, which is commonly followed by overlong URLs.
813     GoogleStyle.CommentPragmas =
814         "(taze:|^/[ \t]*<|(@[A-Za-z_0-9-]+[ \\t]*{)|@see)";
815     GoogleStyle.MaxEmptyLinesToKeep = 3;
816     GoogleStyle.NamespaceIndentation = FormatStyle::NI_All;
817     GoogleStyle.SpacesInContainerLiterals = false;
818     GoogleStyle.JavaScriptQuotes = FormatStyle::JSQS_Single;
819     GoogleStyle.JavaScriptWrapImports = false;
820   } else if (Language == FormatStyle::LK_Proto) {
821     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
822     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
823     GoogleStyle.SpacesInContainerLiterals = false;
824     GoogleStyle.Cpp11BracedListStyle = false;
825     // This affects protocol buffer options specifications and text protos.
826     // Text protos are currently mostly formatted inside C++ raw string literals
827     // and often the current breaking behavior of string literals is not
828     // beneficial there. Investigate turning this on once proper string reflow
829     // has been implemented.
830     GoogleStyle.BreakStringLiterals = false;
831   } else if (Language == FormatStyle::LK_ObjC) {
832     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
833     GoogleStyle.ColumnLimit = 100;
834   }
835 
836   return GoogleStyle;
837 }
838 
839 FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
840   FormatStyle ChromiumStyle = getGoogleStyle(Language);
841   if (Language == FormatStyle::LK_Java) {
842     ChromiumStyle.AllowShortIfStatementsOnASingleLine = true;
843     ChromiumStyle.BreakAfterJavaFieldAnnotations = true;
844     ChromiumStyle.ContinuationIndentWidth = 8;
845     ChromiumStyle.IndentWidth = 4;
846   } else if (Language == FormatStyle::LK_JavaScript) {
847     ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
848     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
849   } else {
850     ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
851     ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
852     ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
853     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
854     ChromiumStyle.BinPackParameters = false;
855     ChromiumStyle.DerivePointerAlignment = false;
856     if (Language == FormatStyle::LK_ObjC)
857       ChromiumStyle.ColumnLimit = 80;
858   }
859   return ChromiumStyle;
860 }
861 
862 FormatStyle getMozillaStyle() {
863   FormatStyle MozillaStyle = getLLVMStyle();
864   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
865   MozillaStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
866   MozillaStyle.AlwaysBreakAfterReturnType = FormatStyle::RTBS_TopLevel;
867   MozillaStyle.AlwaysBreakAfterDefinitionReturnType =
868       FormatStyle::DRTBS_TopLevel;
869   MozillaStyle.AlwaysBreakTemplateDeclarations = FormatStyle::BTDS_Yes;
870   MozillaStyle.BinPackParameters = false;
871   MozillaStyle.BinPackArguments = false;
872   MozillaStyle.BreakBeforeBraces = FormatStyle::BS_Mozilla;
873   MozillaStyle.BreakConstructorInitializers = FormatStyle::BCIS_BeforeComma;
874   MozillaStyle.BreakInheritanceList = FormatStyle::BILS_BeforeComma;
875   MozillaStyle.ConstructorInitializerIndentWidth = 2;
876   MozillaStyle.ContinuationIndentWidth = 2;
877   MozillaStyle.Cpp11BracedListStyle = false;
878   MozillaStyle.FixNamespaceComments = false;
879   MozillaStyle.IndentCaseLabels = true;
880   MozillaStyle.ObjCSpaceAfterProperty = true;
881   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
882   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
883   MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
884   MozillaStyle.SpaceAfterTemplateKeyword = false;
885   return MozillaStyle;
886 }
887 
888 FormatStyle getWebKitStyle() {
889   FormatStyle Style = getLLVMStyle();
890   Style.AccessModifierOffset = -4;
891   Style.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
892   Style.AlignOperands = false;
893   Style.AlignTrailingComments = false;
894   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
895   Style.BreakBeforeBraces = FormatStyle::BS_WebKit;
896   Style.BreakConstructorInitializers = FormatStyle::BCIS_BeforeComma;
897   Style.Cpp11BracedListStyle = false;
898   Style.ColumnLimit = 0;
899   Style.FixNamespaceComments = false;
900   Style.IndentWidth = 4;
901   Style.NamespaceIndentation = FormatStyle::NI_Inner;
902   Style.ObjCBlockIndentWidth = 4;
903   Style.ObjCSpaceAfterProperty = true;
904   Style.PointerAlignment = FormatStyle::PAS_Left;
905   Style.SpaceBeforeCpp11BracedList = true;
906   return Style;
907 }
908 
909 FormatStyle getGNUStyle() {
910   FormatStyle Style = getLLVMStyle();
911   Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_All;
912   Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
913   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
914   Style.BreakBeforeBraces = FormatStyle::BS_GNU;
915   Style.BreakBeforeTernaryOperators = true;
916   Style.Cpp11BracedListStyle = false;
917   Style.ColumnLimit = 79;
918   Style.FixNamespaceComments = false;
919   Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
920   Style.Standard = FormatStyle::LS_Cpp03;
921   return Style;
922 }
923 
924 FormatStyle getNoStyle() {
925   FormatStyle NoStyle = getLLVMStyle();
926   NoStyle.DisableFormat = true;
927   NoStyle.SortIncludes = false;
928   NoStyle.SortUsingDeclarations = false;
929   return NoStyle;
930 }
931 
932 bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
933                         FormatStyle *Style) {
934   if (Name.equals_lower("llvm")) {
935     *Style = getLLVMStyle();
936   } else if (Name.equals_lower("chromium")) {
937     *Style = getChromiumStyle(Language);
938   } else if (Name.equals_lower("mozilla")) {
939     *Style = getMozillaStyle();
940   } else if (Name.equals_lower("google")) {
941     *Style = getGoogleStyle(Language);
942   } else if (Name.equals_lower("webkit")) {
943     *Style = getWebKitStyle();
944   } else if (Name.equals_lower("gnu")) {
945     *Style = getGNUStyle();
946   } else if (Name.equals_lower("none")) {
947     *Style = getNoStyle();
948   } else {
949     return false;
950   }
951 
952   Style->Language = Language;
953   return true;
954 }
955 
956 std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
957   assert(Style);
958   FormatStyle::LanguageKind Language = Style->Language;
959   assert(Language != FormatStyle::LK_None);
960   if (Text.trim().empty())
961     return make_error_code(ParseError::Error);
962   Style->StyleSet.Clear();
963   std::vector<FormatStyle> Styles;
964   llvm::yaml::Input Input(Text);
965   // DocumentListTraits<vector<FormatStyle>> uses the context to get default
966   // values for the fields, keys for which are missing from the configuration.
967   // Mapping also uses the context to get the language to find the correct
968   // base style.
969   Input.setContext(Style);
970   Input >> Styles;
971   if (Input.error())
972     return Input.error();
973 
974   for (unsigned i = 0; i < Styles.size(); ++i) {
975     // Ensures that only the first configuration can skip the Language option.
976     if (Styles[i].Language == FormatStyle::LK_None && i != 0)
977       return make_error_code(ParseError::Error);
978     // Ensure that each language is configured at most once.
979     for (unsigned j = 0; j < i; ++j) {
980       if (Styles[i].Language == Styles[j].Language) {
981         LLVM_DEBUG(llvm::dbgs()
982                    << "Duplicate languages in the config file on positions "
983                    << j << " and " << i << "\n");
984         return make_error_code(ParseError::Error);
985       }
986     }
987   }
988   // Look for a suitable configuration starting from the end, so we can
989   // find the configuration for the specific language first, and the default
990   // configuration (which can only be at slot 0) after it.
991   FormatStyle::FormatStyleSet StyleSet;
992   bool LanguageFound = false;
993   for (int i = Styles.size() - 1; i >= 0; --i) {
994     if (Styles[i].Language != FormatStyle::LK_None)
995       StyleSet.Add(Styles[i]);
996     if (Styles[i].Language == Language)
997       LanguageFound = true;
998   }
999   if (!LanguageFound) {
1000     if (Styles.empty() || Styles[0].Language != FormatStyle::LK_None)
1001       return make_error_code(ParseError::Unsuitable);
1002     FormatStyle DefaultStyle = Styles[0];
1003     DefaultStyle.Language = Language;
1004     StyleSet.Add(std::move(DefaultStyle));
1005   }
1006   *Style = *StyleSet.Get(Language);
1007   return make_error_code(ParseError::Success);
1008 }
1009 
1010 std::string configurationAsText(const FormatStyle &Style) {
1011   std::string Text;
1012   llvm::raw_string_ostream Stream(Text);
1013   llvm::yaml::Output Output(Stream);
1014   // We use the same mapping method for input and output, so we need a non-const
1015   // reference here.
1016   FormatStyle NonConstStyle = expandPresets(Style);
1017   Output << NonConstStyle;
1018   return Stream.str();
1019 }
1020 
1021 llvm::Optional<FormatStyle>
1022 FormatStyle::FormatStyleSet::Get(FormatStyle::LanguageKind Language) const {
1023   if (!Styles)
1024     return None;
1025   auto It = Styles->find(Language);
1026   if (It == Styles->end())
1027     return None;
1028   FormatStyle Style = It->second;
1029   Style.StyleSet = *this;
1030   return Style;
1031 }
1032 
1033 void FormatStyle::FormatStyleSet::Add(FormatStyle Style) {
1034   assert(Style.Language != LK_None &&
1035          "Cannot add a style for LK_None to a StyleSet");
1036   assert(
1037       !Style.StyleSet.Styles &&
1038       "Cannot add a style associated with an existing StyleSet to a StyleSet");
1039   if (!Styles)
1040     Styles = std::make_shared<MapType>();
1041   (*Styles)[Style.Language] = std::move(Style);
1042 }
1043 
1044 void FormatStyle::FormatStyleSet::Clear() {
1045   Styles.reset();
1046 }
1047 
1048 llvm::Optional<FormatStyle>
1049 FormatStyle::GetLanguageStyle(FormatStyle::LanguageKind Language) const {
1050   return StyleSet.Get(Language);
1051 }
1052 
1053 namespace {
1054 
1055 class JavaScriptRequoter : public TokenAnalyzer {
1056 public:
1057   JavaScriptRequoter(const Environment &Env, const FormatStyle &Style)
1058       : TokenAnalyzer(Env, Style) {}
1059 
1060   std::pair<tooling::Replacements, unsigned>
1061   analyze(TokenAnnotator &Annotator,
1062           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1063           FormatTokenLexer &Tokens) override {
1064     AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1065     tooling::Replacements Result;
1066     requoteJSStringLiteral(AnnotatedLines, Result);
1067     return {Result, 0};
1068   }
1069 
1070 private:
1071   // Replaces double/single-quoted string literal as appropriate, re-escaping
1072   // the contents in the process.
1073   void requoteJSStringLiteral(SmallVectorImpl<AnnotatedLine *> &Lines,
1074                               tooling::Replacements &Result) {
1075     for (AnnotatedLine *Line : Lines) {
1076       requoteJSStringLiteral(Line->Children, Result);
1077       if (!Line->Affected)
1078         continue;
1079       for (FormatToken *FormatTok = Line->First; FormatTok;
1080            FormatTok = FormatTok->Next) {
1081         StringRef Input = FormatTok->TokenText;
1082         if (FormatTok->Finalized || !FormatTok->isStringLiteral() ||
1083             // NB: testing for not starting with a double quote to avoid
1084             // breaking `template strings`.
1085             (Style.JavaScriptQuotes == FormatStyle::JSQS_Single &&
1086              !Input.startswith("\"")) ||
1087             (Style.JavaScriptQuotes == FormatStyle::JSQS_Double &&
1088              !Input.startswith("\'")))
1089           continue;
1090 
1091         // Change start and end quote.
1092         bool IsSingle = Style.JavaScriptQuotes == FormatStyle::JSQS_Single;
1093         SourceLocation Start = FormatTok->Tok.getLocation();
1094         auto Replace = [&](SourceLocation Start, unsigned Length,
1095                            StringRef ReplacementText) {
1096           auto Err = Result.add(tooling::Replacement(
1097               Env.getSourceManager(), Start, Length, ReplacementText));
1098           // FIXME: handle error. For now, print error message and skip the
1099           // replacement for release version.
1100           if (Err) {
1101             llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1102             assert(false);
1103           }
1104         };
1105         Replace(Start, 1, IsSingle ? "'" : "\"");
1106         Replace(FormatTok->Tok.getEndLoc().getLocWithOffset(-1), 1,
1107                 IsSingle ? "'" : "\"");
1108 
1109         // Escape internal quotes.
1110         bool Escaped = false;
1111         for (size_t i = 1; i < Input.size() - 1; i++) {
1112           switch (Input[i]) {
1113           case '\\':
1114             if (!Escaped && i + 1 < Input.size() &&
1115                 ((IsSingle && Input[i + 1] == '"') ||
1116                  (!IsSingle && Input[i + 1] == '\''))) {
1117               // Remove this \, it's escaping a " or ' that no longer needs
1118               // escaping
1119               Replace(Start.getLocWithOffset(i), 1, "");
1120               continue;
1121             }
1122             Escaped = !Escaped;
1123             break;
1124           case '\"':
1125           case '\'':
1126             if (!Escaped && IsSingle == (Input[i] == '\'')) {
1127               // Escape the quote.
1128               Replace(Start.getLocWithOffset(i), 0, "\\");
1129             }
1130             Escaped = false;
1131             break;
1132           default:
1133             Escaped = false;
1134             break;
1135           }
1136         }
1137       }
1138     }
1139   }
1140 };
1141 
1142 class Formatter : public TokenAnalyzer {
1143 public:
1144   Formatter(const Environment &Env, const FormatStyle &Style,
1145             FormattingAttemptStatus *Status)
1146       : TokenAnalyzer(Env, Style), Status(Status) {}
1147 
1148   std::pair<tooling::Replacements, unsigned>
1149   analyze(TokenAnnotator &Annotator,
1150           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1151           FormatTokenLexer &Tokens) override {
1152     tooling::Replacements Result;
1153     deriveLocalStyle(AnnotatedLines);
1154     AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1155     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1156       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1157     }
1158     Annotator.setCommentLineLevels(AnnotatedLines);
1159 
1160     WhitespaceManager Whitespaces(
1161         Env.getSourceManager(), Style,
1162         inputUsesCRLF(Env.getSourceManager().getBufferData(Env.getFileID())));
1163     ContinuationIndenter Indenter(Style, Tokens.getKeywords(),
1164                                   Env.getSourceManager(), Whitespaces, Encoding,
1165                                   BinPackInconclusiveFunctions);
1166     unsigned Penalty =
1167         UnwrappedLineFormatter(&Indenter, &Whitespaces, Style,
1168                                Tokens.getKeywords(), Env.getSourceManager(),
1169                                Status)
1170             .format(AnnotatedLines, /*DryRun=*/false,
1171                     /*AdditionalIndent=*/0,
1172                     /*FixBadIndentation=*/false,
1173                     /*FirstStartColumn=*/Env.getFirstStartColumn(),
1174                     /*NextStartColumn=*/Env.getNextStartColumn(),
1175                     /*LastStartColumn=*/Env.getLastStartColumn());
1176     for (const auto &R : Whitespaces.generateReplacements())
1177       if (Result.add(R))
1178         return std::make_pair(Result, 0);
1179     return std::make_pair(Result, Penalty);
1180   }
1181 
1182 private:
1183   static bool inputUsesCRLF(StringRef Text) {
1184     return Text.count('\r') * 2 > Text.count('\n');
1185   }
1186 
1187   bool
1188   hasCpp03IncompatibleFormat(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1189     for (const AnnotatedLine *Line : Lines) {
1190       if (hasCpp03IncompatibleFormat(Line->Children))
1191         return true;
1192       for (FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next) {
1193         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
1194           if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
1195             return true;
1196           if (Tok->is(TT_TemplateCloser) &&
1197               Tok->Previous->is(TT_TemplateCloser))
1198             return true;
1199         }
1200       }
1201     }
1202     return false;
1203   }
1204 
1205   int countVariableAlignments(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1206     int AlignmentDiff = 0;
1207     for (const AnnotatedLine *Line : Lines) {
1208       AlignmentDiff += countVariableAlignments(Line->Children);
1209       for (FormatToken *Tok = Line->First; Tok && Tok->Next; Tok = Tok->Next) {
1210         if (!Tok->is(TT_PointerOrReference))
1211           continue;
1212         bool SpaceBefore =
1213             Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1214         bool SpaceAfter = Tok->Next->WhitespaceRange.getBegin() !=
1215                           Tok->Next->WhitespaceRange.getEnd();
1216         if (SpaceBefore && !SpaceAfter)
1217           ++AlignmentDiff;
1218         if (!SpaceBefore && SpaceAfter)
1219           --AlignmentDiff;
1220       }
1221     }
1222     return AlignmentDiff;
1223   }
1224 
1225   void
1226   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1227     bool HasBinPackedFunction = false;
1228     bool HasOnePerLineFunction = false;
1229     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1230       if (!AnnotatedLines[i]->First->Next)
1231         continue;
1232       FormatToken *Tok = AnnotatedLines[i]->First->Next;
1233       while (Tok->Next) {
1234         if (Tok->PackingKind == PPK_BinPacked)
1235           HasBinPackedFunction = true;
1236         if (Tok->PackingKind == PPK_OnePerLine)
1237           HasOnePerLineFunction = true;
1238 
1239         Tok = Tok->Next;
1240       }
1241     }
1242     if (Style.DerivePointerAlignment)
1243       Style.PointerAlignment = countVariableAlignments(AnnotatedLines) <= 0
1244                                    ? FormatStyle::PAS_Left
1245                                    : FormatStyle::PAS_Right;
1246     if (Style.Standard == FormatStyle::LS_Auto)
1247       Style.Standard = hasCpp03IncompatibleFormat(AnnotatedLines)
1248                            ? FormatStyle::LS_Cpp11
1249                            : FormatStyle::LS_Cpp03;
1250     BinPackInconclusiveFunctions =
1251         HasBinPackedFunction || !HasOnePerLineFunction;
1252   }
1253 
1254   bool BinPackInconclusiveFunctions;
1255   FormattingAttemptStatus *Status;
1256 };
1257 
1258 // This class clean up the erroneous/redundant code around the given ranges in
1259 // file.
1260 class Cleaner : public TokenAnalyzer {
1261 public:
1262   Cleaner(const Environment &Env, const FormatStyle &Style)
1263       : TokenAnalyzer(Env, Style),
1264         DeletedTokens(FormatTokenLess(Env.getSourceManager())) {}
1265 
1266   // FIXME: eliminate unused parameters.
1267   std::pair<tooling::Replacements, unsigned>
1268   analyze(TokenAnnotator &Annotator,
1269           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1270           FormatTokenLexer &Tokens) override {
1271     // FIXME: in the current implementation the granularity of affected range
1272     // is an annotated line. However, this is not sufficient. Furthermore,
1273     // redundant code introduced by replacements does not necessarily
1274     // intercept with ranges of replacements that result in the redundancy.
1275     // To determine if some redundant code is actually introduced by
1276     // replacements(e.g. deletions), we need to come up with a more
1277     // sophisticated way of computing affected ranges.
1278     AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1279 
1280     checkEmptyNamespace(AnnotatedLines);
1281 
1282     for (auto &Line : AnnotatedLines) {
1283       if (Line->Affected) {
1284         cleanupRight(Line->First, tok::comma, tok::comma);
1285         cleanupRight(Line->First, TT_CtorInitializerColon, tok::comma);
1286         cleanupRight(Line->First, tok::l_paren, tok::comma);
1287         cleanupLeft(Line->First, tok::comma, tok::r_paren);
1288         cleanupLeft(Line->First, TT_CtorInitializerComma, tok::l_brace);
1289         cleanupLeft(Line->First, TT_CtorInitializerColon, tok::l_brace);
1290         cleanupLeft(Line->First, TT_CtorInitializerColon, tok::equal);
1291       }
1292     }
1293 
1294     return {generateFixes(), 0};
1295   }
1296 
1297 private:
1298   bool containsOnlyComments(const AnnotatedLine &Line) {
1299     for (FormatToken *Tok = Line.First; Tok != nullptr; Tok = Tok->Next) {
1300       if (Tok->isNot(tok::comment))
1301         return false;
1302     }
1303     return true;
1304   }
1305 
1306   // Iterate through all lines and remove any empty (nested) namespaces.
1307   void checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1308     std::set<unsigned> DeletedLines;
1309     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1310       auto &Line = *AnnotatedLines[i];
1311       if (Line.startsWith(tok::kw_namespace) ||
1312           Line.startsWith(tok::kw_inline, tok::kw_namespace)) {
1313         checkEmptyNamespace(AnnotatedLines, i, i, DeletedLines);
1314       }
1315     }
1316 
1317     for (auto Line : DeletedLines) {
1318       FormatToken *Tok = AnnotatedLines[Line]->First;
1319       while (Tok) {
1320         deleteToken(Tok);
1321         Tok = Tok->Next;
1322       }
1323     }
1324   }
1325 
1326   // The function checks if the namespace, which starts from \p CurrentLine, and
1327   // its nested namespaces are empty and delete them if they are empty. It also
1328   // sets \p NewLine to the last line checked.
1329   // Returns true if the current namespace is empty.
1330   bool checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1331                            unsigned CurrentLine, unsigned &NewLine,
1332                            std::set<unsigned> &DeletedLines) {
1333     unsigned InitLine = CurrentLine, End = AnnotatedLines.size();
1334     if (Style.BraceWrapping.AfterNamespace) {
1335       // If the left brace is in a new line, we should consume it first so that
1336       // it does not make the namespace non-empty.
1337       // FIXME: error handling if there is no left brace.
1338       if (!AnnotatedLines[++CurrentLine]->startsWith(tok::l_brace)) {
1339         NewLine = CurrentLine;
1340         return false;
1341       }
1342     } else if (!AnnotatedLines[CurrentLine]->endsWith(tok::l_brace)) {
1343       return false;
1344     }
1345     while (++CurrentLine < End) {
1346       if (AnnotatedLines[CurrentLine]->startsWith(tok::r_brace))
1347         break;
1348 
1349       if (AnnotatedLines[CurrentLine]->startsWith(tok::kw_namespace) ||
1350           AnnotatedLines[CurrentLine]->startsWith(tok::kw_inline,
1351                                                   tok::kw_namespace)) {
1352         if (!checkEmptyNamespace(AnnotatedLines, CurrentLine, NewLine,
1353                                  DeletedLines))
1354           return false;
1355         CurrentLine = NewLine;
1356         continue;
1357       }
1358 
1359       if (containsOnlyComments(*AnnotatedLines[CurrentLine]))
1360         continue;
1361 
1362       // If there is anything other than comments or nested namespaces in the
1363       // current namespace, the namespace cannot be empty.
1364       NewLine = CurrentLine;
1365       return false;
1366     }
1367 
1368     NewLine = CurrentLine;
1369     if (CurrentLine >= End)
1370       return false;
1371 
1372     // Check if the empty namespace is actually affected by changed ranges.
1373     if (!AffectedRangeMgr.affectsCharSourceRange(CharSourceRange::getCharRange(
1374             AnnotatedLines[InitLine]->First->Tok.getLocation(),
1375             AnnotatedLines[CurrentLine]->Last->Tok.getEndLoc())))
1376       return false;
1377 
1378     for (unsigned i = InitLine; i <= CurrentLine; ++i) {
1379       DeletedLines.insert(i);
1380     }
1381 
1382     return true;
1383   }
1384 
1385   // Checks pairs {start, start->next},..., {end->previous, end} and deletes one
1386   // of the token in the pair if the left token has \p LK token kind and the
1387   // right token has \p RK token kind. If \p DeleteLeft is true, the left token
1388   // is deleted on match; otherwise, the right token is deleted.
1389   template <typename LeftKind, typename RightKind>
1390   void cleanupPair(FormatToken *Start, LeftKind LK, RightKind RK,
1391                    bool DeleteLeft) {
1392     auto NextNotDeleted = [this](const FormatToken &Tok) -> FormatToken * {
1393       for (auto *Res = Tok.Next; Res; Res = Res->Next)
1394         if (!Res->is(tok::comment) &&
1395             DeletedTokens.find(Res) == DeletedTokens.end())
1396           return Res;
1397       return nullptr;
1398     };
1399     for (auto *Left = Start; Left;) {
1400       auto *Right = NextNotDeleted(*Left);
1401       if (!Right)
1402         break;
1403       if (Left->is(LK) && Right->is(RK)) {
1404         deleteToken(DeleteLeft ? Left : Right);
1405         for (auto *Tok = Left->Next; Tok && Tok != Right; Tok = Tok->Next)
1406           deleteToken(Tok);
1407         // If the right token is deleted, we should keep the left token
1408         // unchanged and pair it with the new right token.
1409         if (!DeleteLeft)
1410           continue;
1411       }
1412       Left = Right;
1413     }
1414   }
1415 
1416   template <typename LeftKind, typename RightKind>
1417   void cleanupLeft(FormatToken *Start, LeftKind LK, RightKind RK) {
1418     cleanupPair(Start, LK, RK, /*DeleteLeft=*/true);
1419   }
1420 
1421   template <typename LeftKind, typename RightKind>
1422   void cleanupRight(FormatToken *Start, LeftKind LK, RightKind RK) {
1423     cleanupPair(Start, LK, RK, /*DeleteLeft=*/false);
1424   }
1425 
1426   // Delete the given token.
1427   inline void deleteToken(FormatToken *Tok) {
1428     if (Tok)
1429       DeletedTokens.insert(Tok);
1430   }
1431 
1432   tooling::Replacements generateFixes() {
1433     tooling::Replacements Fixes;
1434     std::vector<FormatToken *> Tokens;
1435     std::copy(DeletedTokens.begin(), DeletedTokens.end(),
1436               std::back_inserter(Tokens));
1437 
1438     // Merge multiple continuous token deletions into one big deletion so that
1439     // the number of replacements can be reduced. This makes computing affected
1440     // ranges more efficient when we run reformat on the changed code.
1441     unsigned Idx = 0;
1442     while (Idx < Tokens.size()) {
1443       unsigned St = Idx, End = Idx;
1444       while ((End + 1) < Tokens.size() &&
1445              Tokens[End]->Next == Tokens[End + 1]) {
1446         End++;
1447       }
1448       auto SR = CharSourceRange::getCharRange(Tokens[St]->Tok.getLocation(),
1449                                               Tokens[End]->Tok.getEndLoc());
1450       auto Err =
1451           Fixes.add(tooling::Replacement(Env.getSourceManager(), SR, ""));
1452       // FIXME: better error handling. for now just print error message and skip
1453       // for the release version.
1454       if (Err) {
1455         llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1456         assert(false && "Fixes must not conflict!");
1457       }
1458       Idx = End + 1;
1459     }
1460 
1461     return Fixes;
1462   }
1463 
1464   // Class for less-than inequality comparason for the set `RedundantTokens`.
1465   // We store tokens in the order they appear in the translation unit so that
1466   // we do not need to sort them in `generateFixes()`.
1467   struct FormatTokenLess {
1468     FormatTokenLess(const SourceManager &SM) : SM(SM) {}
1469 
1470     bool operator()(const FormatToken *LHS, const FormatToken *RHS) const {
1471       return SM.isBeforeInTranslationUnit(LHS->Tok.getLocation(),
1472                                           RHS->Tok.getLocation());
1473     }
1474     const SourceManager &SM;
1475   };
1476 
1477   // Tokens to be deleted.
1478   std::set<FormatToken *, FormatTokenLess> DeletedTokens;
1479 };
1480 
1481 class ObjCHeaderStyleGuesser : public TokenAnalyzer {
1482 public:
1483   ObjCHeaderStyleGuesser(const Environment &Env, const FormatStyle &Style)
1484       : TokenAnalyzer(Env, Style), IsObjC(false) {}
1485 
1486   std::pair<tooling::Replacements, unsigned>
1487   analyze(TokenAnnotator &Annotator,
1488           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1489           FormatTokenLexer &Tokens) override {
1490     assert(Style.Language == FormatStyle::LK_Cpp);
1491     IsObjC = guessIsObjC(AnnotatedLines, Tokens.getKeywords());
1492     tooling::Replacements Result;
1493     return {Result, 0};
1494   }
1495 
1496   bool isObjC() { return IsObjC; }
1497 
1498 private:
1499   static bool guessIsObjC(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1500                           const AdditionalKeywords &Keywords) {
1501     // Keep this array sorted, since we are binary searching over it.
1502     static constexpr llvm::StringLiteral FoundationIdentifiers[] = {
1503         "CGFloat",
1504         "CGPoint",
1505         "CGPointMake",
1506         "CGPointZero",
1507         "CGRect",
1508         "CGRectEdge",
1509         "CGRectInfinite",
1510         "CGRectMake",
1511         "CGRectNull",
1512         "CGRectZero",
1513         "CGSize",
1514         "CGSizeMake",
1515         "CGVector",
1516         "CGVectorMake",
1517         "NSAffineTransform",
1518         "NSArray",
1519         "NSAttributedString",
1520         "NSBlockOperation",
1521         "NSBundle",
1522         "NSCache",
1523         "NSCalendar",
1524         "NSCharacterSet",
1525         "NSCountedSet",
1526         "NSData",
1527         "NSDataDetector",
1528         "NSDecimal",
1529         "NSDecimalNumber",
1530         "NSDictionary",
1531         "NSEdgeInsets",
1532         "NSHashTable",
1533         "NSIndexPath",
1534         "NSIndexSet",
1535         "NSInteger",
1536         "NSInvocationOperation",
1537         "NSLocale",
1538         "NSMapTable",
1539         "NSMutableArray",
1540         "NSMutableAttributedString",
1541         "NSMutableCharacterSet",
1542         "NSMutableData",
1543         "NSMutableDictionary",
1544         "NSMutableIndexSet",
1545         "NSMutableOrderedSet",
1546         "NSMutableSet",
1547         "NSMutableString",
1548         "NSNumber",
1549         "NSNumberFormatter",
1550         "NSObject",
1551         "NSOperation",
1552         "NSOperationQueue",
1553         "NSOperationQueuePriority",
1554         "NSOrderedSet",
1555         "NSPoint",
1556         "NSPointerArray",
1557         "NSQualityOfService",
1558         "NSRange",
1559         "NSRect",
1560         "NSRegularExpression",
1561         "NSSet",
1562         "NSSize",
1563         "NSString",
1564         "NSTimeZone",
1565         "NSUInteger",
1566         "NSURL",
1567         "NSURLComponents",
1568         "NSURLQueryItem",
1569         "NSUUID",
1570         "NSValue",
1571         "UIImage",
1572         "UIView",
1573     };
1574 
1575     for (auto Line : AnnotatedLines) {
1576       for (const FormatToken *FormatTok = Line->First; FormatTok;
1577            FormatTok = FormatTok->Next) {
1578         if ((FormatTok->Previous && FormatTok->Previous->is(tok::at) &&
1579              (FormatTok->Tok.getObjCKeywordID() != tok::objc_not_keyword ||
1580               FormatTok->isOneOf(tok::numeric_constant, tok::l_square,
1581                                  tok::l_brace))) ||
1582             (FormatTok->Tok.isAnyIdentifier() &&
1583              std::binary_search(std::begin(FoundationIdentifiers),
1584                                 std::end(FoundationIdentifiers),
1585                                 FormatTok->TokenText)) ||
1586             FormatTok->is(TT_ObjCStringLiteral) ||
1587             FormatTok->isOneOf(Keywords.kw_NS_ENUM, Keywords.kw_NS_OPTIONS,
1588                                TT_ObjCBlockLBrace, TT_ObjCBlockLParen,
1589                                TT_ObjCDecl, TT_ObjCForIn, TT_ObjCMethodExpr,
1590                                TT_ObjCMethodSpecifier, TT_ObjCProperty)) {
1591           return true;
1592         }
1593         if (guessIsObjC(Line->Children, Keywords))
1594           return true;
1595       }
1596     }
1597     return false;
1598   }
1599 
1600   bool IsObjC;
1601 };
1602 
1603 struct IncludeDirective {
1604   StringRef Filename;
1605   StringRef Text;
1606   unsigned Offset;
1607   int Category;
1608 };
1609 
1610 } // end anonymous namespace
1611 
1612 // Determines whether 'Ranges' intersects with ('Start', 'End').
1613 static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
1614                          unsigned End) {
1615   for (auto Range : Ranges) {
1616     if (Range.getOffset() < End &&
1617         Range.getOffset() + Range.getLength() > Start)
1618       return true;
1619   }
1620   return false;
1621 }
1622 
1623 // Returns a pair (Index, OffsetToEOL) describing the position of the cursor
1624 // before sorting/deduplicating. Index is the index of the include under the
1625 // cursor in the original set of includes. If this include has duplicates, it is
1626 // the index of the first of the duplicates as the others are going to be
1627 // removed. OffsetToEOL describes the cursor's position relative to the end of
1628 // its current line.
1629 // If `Cursor` is not on any #include, `Index` will be UINT_MAX.
1630 static std::pair<unsigned, unsigned>
1631 FindCursorIndex(const SmallVectorImpl<IncludeDirective> &Includes,
1632                 const SmallVectorImpl<unsigned> &Indices, unsigned Cursor) {
1633   unsigned CursorIndex = UINT_MAX;
1634   unsigned OffsetToEOL = 0;
1635   for (int i = 0, e = Includes.size(); i != e; ++i) {
1636     unsigned Start = Includes[Indices[i]].Offset;
1637     unsigned End = Start + Includes[Indices[i]].Text.size();
1638     if (!(Cursor >= Start && Cursor < End))
1639       continue;
1640     CursorIndex = Indices[i];
1641     OffsetToEOL = End - Cursor;
1642     // Put the cursor on the only remaining #include among the duplicate
1643     // #includes.
1644     while (--i >= 0 && Includes[CursorIndex].Text == Includes[Indices[i]].Text)
1645       CursorIndex = i;
1646     break;
1647   }
1648   return std::make_pair(CursorIndex, OffsetToEOL);
1649 }
1650 
1651 // Sorts and deduplicate a block of includes given by 'Includes' alphabetically
1652 // adding the necessary replacement to 'Replaces'. 'Includes' must be in strict
1653 // source order.
1654 // #include directives with the same text will be deduplicated, and only the
1655 // first #include in the duplicate #includes remains. If the `Cursor` is
1656 // provided and put on a deleted #include, it will be moved to the remaining
1657 // #include in the duplicate #includes.
1658 static void sortCppIncludes(const FormatStyle &Style,
1659                             const SmallVectorImpl<IncludeDirective> &Includes,
1660                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
1661                             tooling::Replacements &Replaces, unsigned *Cursor) {
1662   unsigned IncludesBeginOffset = Includes.front().Offset;
1663   unsigned IncludesEndOffset =
1664       Includes.back().Offset + Includes.back().Text.size();
1665   unsigned IncludesBlockSize = IncludesEndOffset - IncludesBeginOffset;
1666   if (!affectsRange(Ranges, IncludesBeginOffset, IncludesEndOffset))
1667     return;
1668   SmallVector<unsigned, 16> Indices;
1669   for (unsigned i = 0, e = Includes.size(); i != e; ++i)
1670     Indices.push_back(i);
1671   std::stable_sort(
1672       Indices.begin(), Indices.end(), [&](unsigned LHSI, unsigned RHSI) {
1673         return std::tie(Includes[LHSI].Category, Includes[LHSI].Filename) <
1674                std::tie(Includes[RHSI].Category, Includes[RHSI].Filename);
1675       });
1676   // The index of the include on which the cursor will be put after
1677   // sorting/deduplicating.
1678   unsigned CursorIndex;
1679   // The offset from cursor to the end of line.
1680   unsigned CursorToEOLOffset;
1681   if (Cursor)
1682     std::tie(CursorIndex, CursorToEOLOffset) =
1683         FindCursorIndex(Includes, Indices, *Cursor);
1684 
1685   // Deduplicate #includes.
1686   Indices.erase(std::unique(Indices.begin(), Indices.end(),
1687                             [&](unsigned LHSI, unsigned RHSI) {
1688                               return Includes[LHSI].Text == Includes[RHSI].Text;
1689                             }),
1690                 Indices.end());
1691 
1692   int CurrentCategory = Includes.front().Category;
1693 
1694   // If the #includes are out of order, we generate a single replacement fixing
1695   // the entire block. Otherwise, no replacement is generated.
1696   if (Indices.size() == Includes.size() &&
1697       std::is_sorted(Indices.begin(), Indices.end()) &&
1698       Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Preserve)
1699     return;
1700 
1701   std::string result;
1702   for (unsigned Index : Indices) {
1703     if (!result.empty()) {
1704       result += "\n";
1705       if (Style.IncludeStyle.IncludeBlocks ==
1706               tooling::IncludeStyle::IBS_Regroup &&
1707           CurrentCategory != Includes[Index].Category)
1708         result += "\n";
1709     }
1710     result += Includes[Index].Text;
1711     if (Cursor && CursorIndex == Index)
1712       *Cursor = IncludesBeginOffset + result.size() - CursorToEOLOffset;
1713     CurrentCategory = Includes[Index].Category;
1714   }
1715 
1716   auto Err = Replaces.add(tooling::Replacement(
1717       FileName, Includes.front().Offset, IncludesBlockSize, result));
1718   // FIXME: better error handling. For now, just skip the replacement for the
1719   // release version.
1720   if (Err) {
1721     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1722     assert(false);
1723   }
1724 }
1725 
1726 namespace {
1727 
1728 const char IncludeRegexPattern[] =
1729     R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
1730 
1731 } // anonymous namespace
1732 
1733 tooling::Replacements sortCppIncludes(const FormatStyle &Style, StringRef Code,
1734                                       ArrayRef<tooling::Range> Ranges,
1735                                       StringRef FileName,
1736                                       tooling::Replacements &Replaces,
1737                                       unsigned *Cursor) {
1738   unsigned Prev = 0;
1739   unsigned SearchFrom = 0;
1740   llvm::Regex IncludeRegex(IncludeRegexPattern);
1741   SmallVector<StringRef, 4> Matches;
1742   SmallVector<IncludeDirective, 16> IncludesInBlock;
1743 
1744   // In compiled files, consider the first #include to be the main #include of
1745   // the file if it is not a system #include. This ensures that the header
1746   // doesn't have hidden dependencies
1747   // (http://llvm.org/docs/CodingStandards.html#include-style).
1748   //
1749   // FIXME: Do some sanity checking, e.g. edit distance of the base name, to fix
1750   // cases where the first #include is unlikely to be the main header.
1751   tooling::IncludeCategoryManager Categories(Style.IncludeStyle, FileName);
1752   bool FirstIncludeBlock = true;
1753   bool MainIncludeFound = false;
1754   bool FormattingOff = false;
1755 
1756   for (;;) {
1757     auto Pos = Code.find('\n', SearchFrom);
1758     StringRef Line =
1759         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
1760 
1761     StringRef Trimmed = Line.trim();
1762     if (Trimmed == "// clang-format off")
1763       FormattingOff = true;
1764     else if (Trimmed == "// clang-format on")
1765       FormattingOff = false;
1766 
1767     const bool EmptyLineSkipped =
1768         Trimmed.empty() &&
1769         (Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Merge ||
1770          Style.IncludeStyle.IncludeBlocks ==
1771              tooling::IncludeStyle::IBS_Regroup);
1772 
1773     if (!FormattingOff && !Line.endswith("\\")) {
1774       if (IncludeRegex.match(Line, &Matches)) {
1775         StringRef IncludeName = Matches[2];
1776         int Category = Categories.getIncludePriority(
1777             IncludeName,
1778             /*CheckMainHeader=*/!MainIncludeFound && FirstIncludeBlock);
1779         if (Category == 0)
1780           MainIncludeFound = true;
1781         IncludesInBlock.push_back({IncludeName, Line, Prev, Category});
1782       } else if (!IncludesInBlock.empty() && !EmptyLineSkipped) {
1783         sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces,
1784                         Cursor);
1785         IncludesInBlock.clear();
1786         FirstIncludeBlock = false;
1787       }
1788       Prev = Pos + 1;
1789     }
1790     if (Pos == StringRef::npos || Pos + 1 == Code.size())
1791       break;
1792     SearchFrom = Pos + 1;
1793   }
1794   if (!IncludesInBlock.empty())
1795     sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces, Cursor);
1796   return Replaces;
1797 }
1798 
1799 bool isMpegTS(StringRef Code) {
1800   // MPEG transport streams use the ".ts" file extension. clang-format should
1801   // not attempt to format those. MPEG TS' frame format starts with 0x47 every
1802   // 189 bytes - detect that and return.
1803   return Code.size() > 188 && Code[0] == 0x47 && Code[188] == 0x47;
1804 }
1805 
1806 bool isLikelyXml(StringRef Code) { return Code.ltrim().startswith("<"); }
1807 
1808 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
1809                                    ArrayRef<tooling::Range> Ranges,
1810                                    StringRef FileName, unsigned *Cursor) {
1811   tooling::Replacements Replaces;
1812   if (!Style.SortIncludes)
1813     return Replaces;
1814   if (isLikelyXml(Code))
1815     return Replaces;
1816   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript &&
1817       isMpegTS(Code))
1818     return Replaces;
1819   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript)
1820     return sortJavaScriptImports(Style, Code, Ranges, FileName);
1821   sortCppIncludes(Style, Code, Ranges, FileName, Replaces, Cursor);
1822   return Replaces;
1823 }
1824 
1825 template <typename T>
1826 static llvm::Expected<tooling::Replacements>
1827 processReplacements(T ProcessFunc, StringRef Code,
1828                     const tooling::Replacements &Replaces,
1829                     const FormatStyle &Style) {
1830   if (Replaces.empty())
1831     return tooling::Replacements();
1832 
1833   auto NewCode = applyAllReplacements(Code, Replaces);
1834   if (!NewCode)
1835     return NewCode.takeError();
1836   std::vector<tooling::Range> ChangedRanges = Replaces.getAffectedRanges();
1837   StringRef FileName = Replaces.begin()->getFilePath();
1838 
1839   tooling::Replacements FormatReplaces =
1840       ProcessFunc(Style, *NewCode, ChangedRanges, FileName);
1841 
1842   return Replaces.merge(FormatReplaces);
1843 }
1844 
1845 llvm::Expected<tooling::Replacements>
1846 formatReplacements(StringRef Code, const tooling::Replacements &Replaces,
1847                    const FormatStyle &Style) {
1848   // We need to use lambda function here since there are two versions of
1849   // `sortIncludes`.
1850   auto SortIncludes = [](const FormatStyle &Style, StringRef Code,
1851                          std::vector<tooling::Range> Ranges,
1852                          StringRef FileName) -> tooling::Replacements {
1853     return sortIncludes(Style, Code, Ranges, FileName);
1854   };
1855   auto SortedReplaces =
1856       processReplacements(SortIncludes, Code, Replaces, Style);
1857   if (!SortedReplaces)
1858     return SortedReplaces.takeError();
1859 
1860   // We need to use lambda function here since there are two versions of
1861   // `reformat`.
1862   auto Reformat = [](const FormatStyle &Style, StringRef Code,
1863                      std::vector<tooling::Range> Ranges,
1864                      StringRef FileName) -> tooling::Replacements {
1865     return reformat(Style, Code, Ranges, FileName);
1866   };
1867   return processReplacements(Reformat, Code, *SortedReplaces, Style);
1868 }
1869 
1870 namespace {
1871 
1872 inline bool isHeaderInsertion(const tooling::Replacement &Replace) {
1873   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 0 &&
1874          llvm::Regex(IncludeRegexPattern).match(Replace.getReplacementText());
1875 }
1876 
1877 inline bool isHeaderDeletion(const tooling::Replacement &Replace) {
1878   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 1;
1879 }
1880 
1881 // FIXME: insert empty lines between newly created blocks.
1882 tooling::Replacements
1883 fixCppIncludeInsertions(StringRef Code, const tooling::Replacements &Replaces,
1884                         const FormatStyle &Style) {
1885   if (!Style.isCpp())
1886     return Replaces;
1887 
1888   tooling::Replacements HeaderInsertions;
1889   std::set<llvm::StringRef> HeadersToDelete;
1890   tooling::Replacements Result;
1891   for (const auto &R : Replaces) {
1892     if (isHeaderInsertion(R)) {
1893       // Replacements from \p Replaces must be conflict-free already, so we can
1894       // simply consume the error.
1895       llvm::consumeError(HeaderInsertions.add(R));
1896     } else if (isHeaderDeletion(R)) {
1897       HeadersToDelete.insert(R.getReplacementText());
1898     } else if (R.getOffset() == UINT_MAX) {
1899       llvm::errs() << "Insertions other than header #include insertion are "
1900                       "not supported! "
1901                    << R.getReplacementText() << "\n";
1902     } else {
1903       llvm::consumeError(Result.add(R));
1904     }
1905   }
1906   if (HeaderInsertions.empty() && HeadersToDelete.empty())
1907     return Replaces;
1908 
1909 
1910   StringRef FileName = Replaces.begin()->getFilePath();
1911   tooling::HeaderIncludes Includes(FileName, Code, Style.IncludeStyle);
1912 
1913   for (const auto &Header : HeadersToDelete) {
1914     tooling::Replacements Replaces =
1915         Includes.remove(Header.trim("\"<>"), Header.startswith("<"));
1916     for (const auto &R : Replaces) {
1917       auto Err = Result.add(R);
1918       if (Err) {
1919         // Ignore the deletion on conflict.
1920         llvm::errs() << "Failed to add header deletion replacement for "
1921                      << Header << ": " << llvm::toString(std::move(Err))
1922                      << "\n";
1923       }
1924     }
1925   }
1926 
1927   llvm::Regex IncludeRegex = llvm::Regex(IncludeRegexPattern);
1928   llvm::SmallVector<StringRef, 4> Matches;
1929   for (const auto &R : HeaderInsertions) {
1930     auto IncludeDirective = R.getReplacementText();
1931     bool Matched = IncludeRegex.match(IncludeDirective, &Matches);
1932     assert(Matched && "Header insertion replacement must have replacement text "
1933                       "'#include ...'");
1934     (void)Matched;
1935     auto IncludeName = Matches[2];
1936     auto Replace =
1937         Includes.insert(IncludeName.trim("\"<>"), IncludeName.startswith("<"));
1938     if (Replace) {
1939       auto Err = Result.add(*Replace);
1940       if (Err) {
1941         llvm::consumeError(std::move(Err));
1942         unsigned NewOffset = Result.getShiftedCodePosition(Replace->getOffset());
1943         auto Shifted = tooling::Replacement(FileName, NewOffset, 0,
1944                                             Replace->getReplacementText());
1945         Result = Result.merge(tooling::Replacements(Shifted));
1946       }
1947     }
1948   }
1949   return Result;
1950 }
1951 
1952 } // anonymous namespace
1953 
1954 llvm::Expected<tooling::Replacements>
1955 cleanupAroundReplacements(StringRef Code, const tooling::Replacements &Replaces,
1956                           const FormatStyle &Style) {
1957   // We need to use lambda function here since there are two versions of
1958   // `cleanup`.
1959   auto Cleanup = [](const FormatStyle &Style, StringRef Code,
1960                     std::vector<tooling::Range> Ranges,
1961                     StringRef FileName) -> tooling::Replacements {
1962     return cleanup(Style, Code, Ranges, FileName);
1963   };
1964   // Make header insertion replacements insert new headers into correct blocks.
1965   tooling::Replacements NewReplaces =
1966       fixCppIncludeInsertions(Code, Replaces, Style);
1967   return processReplacements(Cleanup, Code, NewReplaces, Style);
1968 }
1969 
1970 namespace internal {
1971 std::pair<tooling::Replacements, unsigned>
1972 reformat(const FormatStyle &Style, StringRef Code,
1973          ArrayRef<tooling::Range> Ranges, unsigned FirstStartColumn,
1974          unsigned NextStartColumn, unsigned LastStartColumn, StringRef FileName,
1975          FormattingAttemptStatus *Status) {
1976   FormatStyle Expanded = expandPresets(Style);
1977   if (Expanded.DisableFormat)
1978     return {tooling::Replacements(), 0};
1979   if (isLikelyXml(Code))
1980     return {tooling::Replacements(), 0};
1981   if (Expanded.Language == FormatStyle::LK_JavaScript && isMpegTS(Code))
1982     return {tooling::Replacements(), 0};
1983 
1984   typedef std::function<std::pair<tooling::Replacements, unsigned>(
1985       const Environment &)>
1986       AnalyzerPass;
1987   SmallVector<AnalyzerPass, 4> Passes;
1988 
1989   if (Style.Language == FormatStyle::LK_Cpp) {
1990     if (Style.FixNamespaceComments)
1991       Passes.emplace_back([&](const Environment &Env) {
1992         return NamespaceEndCommentsFixer(Env, Expanded).process();
1993       });
1994 
1995     if (Style.SortUsingDeclarations)
1996       Passes.emplace_back([&](const Environment &Env) {
1997         return UsingDeclarationsSorter(Env, Expanded).process();
1998       });
1999   }
2000 
2001   if (Style.Language == FormatStyle::LK_JavaScript &&
2002       Style.JavaScriptQuotes != FormatStyle::JSQS_Leave)
2003     Passes.emplace_back([&](const Environment &Env) {
2004       return JavaScriptRequoter(Env, Expanded).process();
2005     });
2006 
2007   Passes.emplace_back([&](const Environment &Env) {
2008     return Formatter(Env, Expanded, Status).process();
2009   });
2010 
2011   auto Env =
2012       llvm::make_unique<Environment>(Code, FileName, Ranges, FirstStartColumn,
2013                                      NextStartColumn, LastStartColumn);
2014   llvm::Optional<std::string> CurrentCode = None;
2015   tooling::Replacements Fixes;
2016   unsigned Penalty = 0;
2017   for (size_t I = 0, E = Passes.size(); I < E; ++I) {
2018     std::pair<tooling::Replacements, unsigned> PassFixes = Passes[I](*Env);
2019     auto NewCode = applyAllReplacements(
2020         CurrentCode ? StringRef(*CurrentCode) : Code, PassFixes.first);
2021     if (NewCode) {
2022       Fixes = Fixes.merge(PassFixes.first);
2023       Penalty += PassFixes.second;
2024       if (I + 1 < E) {
2025         CurrentCode = std::move(*NewCode);
2026         Env = llvm::make_unique<Environment>(
2027             *CurrentCode, FileName,
2028             tooling::calculateRangesAfterReplacements(Fixes, Ranges),
2029             FirstStartColumn, NextStartColumn, LastStartColumn);
2030       }
2031     }
2032   }
2033 
2034   return {Fixes, Penalty};
2035 }
2036 } // namespace internal
2037 
2038 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
2039                                ArrayRef<tooling::Range> Ranges,
2040                                StringRef FileName,
2041                                FormattingAttemptStatus *Status) {
2042   return internal::reformat(Style, Code, Ranges,
2043                             /*FirstStartColumn=*/0,
2044                             /*NextStartColumn=*/0,
2045                             /*LastStartColumn=*/0, FileName, Status)
2046       .first;
2047 }
2048 
2049 tooling::Replacements cleanup(const FormatStyle &Style, StringRef Code,
2050                               ArrayRef<tooling::Range> Ranges,
2051                               StringRef FileName) {
2052   // cleanups only apply to C++ (they mostly concern ctor commas etc.)
2053   if (Style.Language != FormatStyle::LK_Cpp)
2054     return tooling::Replacements();
2055   return Cleaner(Environment(Code, FileName, Ranges), Style).process().first;
2056 }
2057 
2058 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
2059                                ArrayRef<tooling::Range> Ranges,
2060                                StringRef FileName, bool *IncompleteFormat) {
2061   FormattingAttemptStatus Status;
2062   auto Result = reformat(Style, Code, Ranges, FileName, &Status);
2063   if (!Status.FormatComplete)
2064     *IncompleteFormat = true;
2065   return Result;
2066 }
2067 
2068 tooling::Replacements fixNamespaceEndComments(const FormatStyle &Style,
2069                                               StringRef Code,
2070                                               ArrayRef<tooling::Range> Ranges,
2071                                               StringRef FileName) {
2072   return NamespaceEndCommentsFixer(Environment(Code, FileName, Ranges), Style)
2073       .process()
2074       .first;
2075 }
2076 
2077 tooling::Replacements sortUsingDeclarations(const FormatStyle &Style,
2078                                             StringRef Code,
2079                                             ArrayRef<tooling::Range> Ranges,
2080                                             StringRef FileName) {
2081   return UsingDeclarationsSorter(Environment(Code, FileName, Ranges), Style)
2082       .process()
2083       .first;
2084 }
2085 
2086 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
2087   LangOptions LangOpts;
2088   LangOpts.CPlusPlus = 1;
2089   LangOpts.CPlusPlus11 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
2090   LangOpts.CPlusPlus14 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
2091   LangOpts.CPlusPlus17 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
2092   LangOpts.CPlusPlus2a = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
2093   LangOpts.LineComment = 1;
2094   bool AlternativeOperators = Style.isCpp();
2095   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
2096   LangOpts.Bool = 1;
2097   LangOpts.ObjC1 = 1;
2098   LangOpts.ObjC2 = 1;
2099   LangOpts.MicrosoftExt = 1;    // To get kw___try, kw___finally.
2100   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
2101   return LangOpts;
2102 }
2103 
2104 const char *StyleOptionHelpDescription =
2105     "Coding style, currently supports:\n"
2106     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
2107     "Use -style=file to load style configuration from\n"
2108     ".clang-format file located in one of the parent\n"
2109     "directories of the source file (or current\n"
2110     "directory for stdin).\n"
2111     "Use -style=\"{key: value, ...}\" to set specific\n"
2112     "parameters, e.g.:\n"
2113     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
2114 
2115 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
2116   if (FileName.endswith(".java"))
2117     return FormatStyle::LK_Java;
2118   if (FileName.endswith_lower(".js") || FileName.endswith_lower(".ts"))
2119     return FormatStyle::LK_JavaScript; // JavaScript or TypeScript.
2120   if (FileName.endswith(".m") || FileName.endswith(".mm"))
2121     return FormatStyle::LK_ObjC;
2122   if (FileName.endswith_lower(".proto") ||
2123       FileName.endswith_lower(".protodevel"))
2124     return FormatStyle::LK_Proto;
2125   if (FileName.endswith_lower(".textpb") ||
2126       FileName.endswith_lower(".pb.txt") ||
2127       FileName.endswith_lower(".textproto") ||
2128       FileName.endswith_lower(".asciipb"))
2129     return FormatStyle::LK_TextProto;
2130   if (FileName.endswith_lower(".td"))
2131     return FormatStyle::LK_TableGen;
2132   return FormatStyle::LK_Cpp;
2133 }
2134 
2135 FormatStyle::LanguageKind guessLanguage(StringRef FileName, StringRef Code) {
2136   const auto GuessedLanguage = getLanguageByFileName(FileName);
2137   if (GuessedLanguage == FormatStyle::LK_Cpp) {
2138     auto Extension = llvm::sys::path::extension(FileName);
2139     // If there's no file extension (or it's .h), we need to check the contents
2140     // of the code to see if it contains Objective-C.
2141     if (Extension.empty() || Extension == ".h") {
2142       auto NonEmptyFileName = FileName.empty() ? "guess.h" : FileName;
2143       Environment Env(Code, NonEmptyFileName, /*Ranges=*/{});
2144       ObjCHeaderStyleGuesser Guesser(Env, getLLVMStyle());
2145       Guesser.process();
2146       if (Guesser.isObjC())
2147         return FormatStyle::LK_ObjC;
2148     }
2149   }
2150   return GuessedLanguage;
2151 }
2152 
2153 const char *DefaultFormatStyle = "file";
2154 
2155 const char *DefaultFallbackStyle = "LLVM";
2156 
2157 llvm::Expected<FormatStyle> getStyle(StringRef StyleName, StringRef FileName,
2158                                      StringRef FallbackStyleName,
2159                                      StringRef Code, vfs::FileSystem *FS) {
2160   if (!FS) {
2161     FS = vfs::getRealFileSystem().get();
2162   }
2163   FormatStyle Style = getLLVMStyle();
2164   Style.Language = guessLanguage(FileName, Code);
2165 
2166   FormatStyle FallbackStyle = getNoStyle();
2167   if (!getPredefinedStyle(FallbackStyleName, Style.Language, &FallbackStyle))
2168     return make_string_error("Invalid fallback style \"" + FallbackStyleName);
2169 
2170   if (StyleName.startswith("{")) {
2171     // Parse YAML/JSON style from the command line.
2172     if (std::error_code ec = parseConfiguration(StyleName, &Style))
2173       return make_string_error("Error parsing -style: " + ec.message());
2174     return Style;
2175   }
2176 
2177   if (!StyleName.equals_lower("file")) {
2178     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
2179       return make_string_error("Invalid value for -style");
2180     return Style;
2181   }
2182 
2183   // Look for .clang-format/_clang-format file in the file's parent directories.
2184   SmallString<128> UnsuitableConfigFiles;
2185   SmallString<128> Path(FileName);
2186   if (std::error_code EC = FS->makeAbsolute(Path))
2187     return make_string_error(EC.message());
2188 
2189   for (StringRef Directory = Path; !Directory.empty();
2190        Directory = llvm::sys::path::parent_path(Directory)) {
2191 
2192     auto Status = FS->status(Directory);
2193     if (!Status ||
2194         Status->getType() != llvm::sys::fs::file_type::directory_file) {
2195       continue;
2196     }
2197 
2198     SmallString<128> ConfigFile(Directory);
2199 
2200     llvm::sys::path::append(ConfigFile, ".clang-format");
2201     LLVM_DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2202 
2203     Status = FS->status(ConfigFile.str());
2204     bool FoundConfigFile =
2205         Status && (Status->getType() == llvm::sys::fs::file_type::regular_file);
2206     if (!FoundConfigFile) {
2207       // Try _clang-format too, since dotfiles are not commonly used on Windows.
2208       ConfigFile = Directory;
2209       llvm::sys::path::append(ConfigFile, "_clang-format");
2210       LLVM_DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2211       Status = FS->status(ConfigFile.str());
2212       FoundConfigFile = Status && (Status->getType() ==
2213                                    llvm::sys::fs::file_type::regular_file);
2214     }
2215 
2216     if (FoundConfigFile) {
2217       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
2218           FS->getBufferForFile(ConfigFile.str());
2219       if (std::error_code EC = Text.getError())
2220         return make_string_error(EC.message());
2221       if (std::error_code ec =
2222               parseConfiguration(Text.get()->getBuffer(), &Style)) {
2223         if (ec == ParseError::Unsuitable) {
2224           if (!UnsuitableConfigFiles.empty())
2225             UnsuitableConfigFiles.append(", ");
2226           UnsuitableConfigFiles.append(ConfigFile);
2227           continue;
2228         }
2229         return make_string_error("Error reading " + ConfigFile + ": " +
2230                                  ec.message());
2231       }
2232       LLVM_DEBUG(llvm::dbgs()
2233                  << "Using configuration file " << ConfigFile << "\n");
2234       return Style;
2235     }
2236   }
2237   if (!UnsuitableConfigFiles.empty())
2238     return make_string_error("Configuration file(s) do(es) not support " +
2239                              getLanguageName(Style.Language) + ": " +
2240                              UnsuitableConfigFiles);
2241   return FallbackStyle;
2242 }
2243 
2244 } // namespace format
2245 } // namespace clang
2246