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