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