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