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