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