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