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                             StringRef Code,
1857                             tooling::Replacements &Replaces) {
1858   unsigned ImportsBeginOffset = Imports.front().Offset;
1859   unsigned ImportsEndOffset =
1860       Imports.back().Offset + Imports.back().Text.size();
1861   unsigned ImportsBlockSize = ImportsEndOffset - ImportsBeginOffset;
1862   if (!affectsRange(Ranges, ImportsBeginOffset, ImportsEndOffset))
1863     return;
1864   SmallVector<unsigned, 16> Indices;
1865   SmallVector<unsigned, 16> JavaImportGroups;
1866   for (unsigned i = 0, e = Imports.size(); i != e; ++i) {
1867     Indices.push_back(i);
1868     JavaImportGroups.push_back(
1869         findJavaImportGroup(Style, Imports[i].Identifier));
1870   }
1871   llvm::sort(Indices, [&](unsigned LHSI, unsigned RHSI) {
1872     // Negating IsStatic to push static imports above non-static imports.
1873     return std::make_tuple(!Imports[LHSI].IsStatic, JavaImportGroups[LHSI],
1874                            Imports[LHSI].Identifier) <
1875            std::make_tuple(!Imports[RHSI].IsStatic, JavaImportGroups[RHSI],
1876                            Imports[RHSI].Identifier);
1877   });
1878 
1879   // Deduplicate imports.
1880   Indices.erase(std::unique(Indices.begin(), Indices.end(),
1881                             [&](unsigned LHSI, unsigned RHSI) {
1882                               return Imports[LHSI].Text == Imports[RHSI].Text;
1883                             }),
1884                 Indices.end());
1885 
1886   bool CurrentIsStatic = Imports[Indices.front()].IsStatic;
1887   unsigned CurrentImportGroup = JavaImportGroups[Indices.front()];
1888 
1889   std::string result;
1890   for (unsigned Index : Indices) {
1891     if (!result.empty()) {
1892       result += "\n";
1893       if (CurrentIsStatic != Imports[Index].IsStatic ||
1894           CurrentImportGroup != JavaImportGroups[Index])
1895         result += "\n";
1896     }
1897     for (StringRef CommentLine : Imports[Index].AssociatedCommentLines) {
1898       result += CommentLine;
1899       result += "\n";
1900     }
1901     result += Imports[Index].Text;
1902     CurrentIsStatic = Imports[Index].IsStatic;
1903     CurrentImportGroup = JavaImportGroups[Index];
1904   }
1905 
1906   // If the imports are out of order, we generate a single replacement fixing
1907   // the entire block. Otherwise, no replacement is generated.
1908   if (result == Code.substr(Imports.front().Offset, ImportsBlockSize))
1909     return;
1910 
1911   auto Err = Replaces.add(tooling::Replacement(FileName, Imports.front().Offset,
1912                                                ImportsBlockSize, result));
1913   // FIXME: better error handling. For now, just skip the replacement for the
1914   // release version.
1915   if (Err) {
1916     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1917     assert(false);
1918   }
1919 }
1920 
1921 namespace {
1922 
1923 const char JavaImportRegexPattern[] =
1924     "^[\t ]*import[\t ]*(static[\t ]*)?([^\t ]*)[\t ]*;";
1925 
1926 } // anonymous namespace
1927 
1928 tooling::Replacements sortJavaImports(const FormatStyle &Style, StringRef Code,
1929                                       ArrayRef<tooling::Range> Ranges,
1930                                       StringRef FileName,
1931                                       tooling::Replacements &Replaces) {
1932   unsigned Prev = 0;
1933   unsigned SearchFrom = 0;
1934   llvm::Regex ImportRegex(JavaImportRegexPattern);
1935   SmallVector<StringRef, 4> Matches;
1936   SmallVector<JavaImportDirective, 16> ImportsInBlock;
1937   std::vector<StringRef> AssociatedCommentLines;
1938 
1939   bool FormattingOff = false;
1940 
1941   for (;;) {
1942     auto Pos = Code.find('\n', SearchFrom);
1943     StringRef Line =
1944         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
1945 
1946     StringRef Trimmed = Line.trim();
1947     if (Trimmed == "// clang-format off")
1948       FormattingOff = true;
1949     else if (Trimmed == "// clang-format on")
1950       FormattingOff = false;
1951 
1952     if (ImportRegex.match(Line, &Matches)) {
1953       if (FormattingOff) {
1954         // If at least one import line has formatting turned off, turn off
1955         // formatting entirely.
1956         return Replaces;
1957       }
1958       StringRef Static = Matches[1];
1959       StringRef Identifier = Matches[2];
1960       bool IsStatic = false;
1961       if (Static.contains("static")) {
1962         IsStatic = true;
1963       }
1964       ImportsInBlock.push_back({Identifier, Line, Prev, AssociatedCommentLines, IsStatic});
1965       AssociatedCommentLines.clear();
1966     } else if (Trimmed.size() > 0 && !ImportsInBlock.empty()) {
1967       // Associating comments within the imports with the nearest import below
1968       AssociatedCommentLines.push_back(Line);
1969     }
1970     Prev = Pos + 1;
1971     if (Pos == StringRef::npos || Pos + 1 == Code.size())
1972       break;
1973     SearchFrom = Pos + 1;
1974   }
1975   if (!ImportsInBlock.empty())
1976     sortJavaImports(Style, ImportsInBlock, Ranges, FileName, Code, Replaces);
1977   return Replaces;
1978 }
1979 
1980 bool isMpegTS(StringRef Code) {
1981   // MPEG transport streams use the ".ts" file extension. clang-format should
1982   // not attempt to format those. MPEG TS' frame format starts with 0x47 every
1983   // 189 bytes - detect that and return.
1984   return Code.size() > 188 && Code[0] == 0x47 && Code[188] == 0x47;
1985 }
1986 
1987 bool isLikelyXml(StringRef Code) { return Code.ltrim().startswith("<"); }
1988 
1989 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
1990                                    ArrayRef<tooling::Range> Ranges,
1991                                    StringRef FileName, unsigned *Cursor) {
1992   tooling::Replacements Replaces;
1993   if (!Style.SortIncludes)
1994     return Replaces;
1995   if (isLikelyXml(Code))
1996     return Replaces;
1997   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript &&
1998       isMpegTS(Code))
1999     return Replaces;
2000   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript)
2001     return sortJavaScriptImports(Style, Code, Ranges, FileName);
2002   if (Style.Language == FormatStyle::LanguageKind::LK_Java)
2003     return sortJavaImports(Style, Code, Ranges, FileName, Replaces);
2004   sortCppIncludes(Style, Code, Ranges, FileName, Replaces, Cursor);
2005   return Replaces;
2006 }
2007 
2008 template <typename T>
2009 static llvm::Expected<tooling::Replacements>
2010 processReplacements(T ProcessFunc, StringRef Code,
2011                     const tooling::Replacements &Replaces,
2012                     const FormatStyle &Style) {
2013   if (Replaces.empty())
2014     return tooling::Replacements();
2015 
2016   auto NewCode = applyAllReplacements(Code, Replaces);
2017   if (!NewCode)
2018     return NewCode.takeError();
2019   std::vector<tooling::Range> ChangedRanges = Replaces.getAffectedRanges();
2020   StringRef FileName = Replaces.begin()->getFilePath();
2021 
2022   tooling::Replacements FormatReplaces =
2023       ProcessFunc(Style, *NewCode, ChangedRanges, FileName);
2024 
2025   return Replaces.merge(FormatReplaces);
2026 }
2027 
2028 llvm::Expected<tooling::Replacements>
2029 formatReplacements(StringRef Code, const tooling::Replacements &Replaces,
2030                    const FormatStyle &Style) {
2031   // We need to use lambda function here since there are two versions of
2032   // `sortIncludes`.
2033   auto SortIncludes = [](const FormatStyle &Style, StringRef Code,
2034                          std::vector<tooling::Range> Ranges,
2035                          StringRef FileName) -> tooling::Replacements {
2036     return sortIncludes(Style, Code, Ranges, FileName);
2037   };
2038   auto SortedReplaces =
2039       processReplacements(SortIncludes, Code, Replaces, Style);
2040   if (!SortedReplaces)
2041     return SortedReplaces.takeError();
2042 
2043   // We need to use lambda function here since there are two versions of
2044   // `reformat`.
2045   auto Reformat = [](const FormatStyle &Style, StringRef Code,
2046                      std::vector<tooling::Range> Ranges,
2047                      StringRef FileName) -> tooling::Replacements {
2048     return reformat(Style, Code, Ranges, FileName);
2049   };
2050   return processReplacements(Reformat, Code, *SortedReplaces, Style);
2051 }
2052 
2053 namespace {
2054 
2055 inline bool isHeaderInsertion(const tooling::Replacement &Replace) {
2056   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 0 &&
2057          llvm::Regex(CppIncludeRegexPattern)
2058              .match(Replace.getReplacementText());
2059 }
2060 
2061 inline bool isHeaderDeletion(const tooling::Replacement &Replace) {
2062   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 1;
2063 }
2064 
2065 // FIXME: insert empty lines between newly created blocks.
2066 tooling::Replacements
2067 fixCppIncludeInsertions(StringRef Code, const tooling::Replacements &Replaces,
2068                         const FormatStyle &Style) {
2069   if (!Style.isCpp())
2070     return Replaces;
2071 
2072   tooling::Replacements HeaderInsertions;
2073   std::set<llvm::StringRef> HeadersToDelete;
2074   tooling::Replacements Result;
2075   for (const auto &R : Replaces) {
2076     if (isHeaderInsertion(R)) {
2077       // Replacements from \p Replaces must be conflict-free already, so we can
2078       // simply consume the error.
2079       llvm::consumeError(HeaderInsertions.add(R));
2080     } else if (isHeaderDeletion(R)) {
2081       HeadersToDelete.insert(R.getReplacementText());
2082     } else if (R.getOffset() == UINT_MAX) {
2083       llvm::errs() << "Insertions other than header #include insertion are "
2084                       "not supported! "
2085                    << R.getReplacementText() << "\n";
2086     } else {
2087       llvm::consumeError(Result.add(R));
2088     }
2089   }
2090   if (HeaderInsertions.empty() && HeadersToDelete.empty())
2091     return Replaces;
2092 
2093 
2094   StringRef FileName = Replaces.begin()->getFilePath();
2095   tooling::HeaderIncludes Includes(FileName, Code, Style.IncludeStyle);
2096 
2097   for (const auto &Header : HeadersToDelete) {
2098     tooling::Replacements Replaces =
2099         Includes.remove(Header.trim("\"<>"), Header.startswith("<"));
2100     for (const auto &R : Replaces) {
2101       auto Err = Result.add(R);
2102       if (Err) {
2103         // Ignore the deletion on conflict.
2104         llvm::errs() << "Failed to add header deletion replacement for "
2105                      << Header << ": " << llvm::toString(std::move(Err))
2106                      << "\n";
2107       }
2108     }
2109   }
2110 
2111   llvm::Regex IncludeRegex = llvm::Regex(CppIncludeRegexPattern);
2112   llvm::SmallVector<StringRef, 4> Matches;
2113   for (const auto &R : HeaderInsertions) {
2114     auto IncludeDirective = R.getReplacementText();
2115     bool Matched = IncludeRegex.match(IncludeDirective, &Matches);
2116     assert(Matched && "Header insertion replacement must have replacement text "
2117                       "'#include ...'");
2118     (void)Matched;
2119     auto IncludeName = Matches[2];
2120     auto Replace =
2121         Includes.insert(IncludeName.trim("\"<>"), IncludeName.startswith("<"));
2122     if (Replace) {
2123       auto Err = Result.add(*Replace);
2124       if (Err) {
2125         llvm::consumeError(std::move(Err));
2126         unsigned NewOffset = Result.getShiftedCodePosition(Replace->getOffset());
2127         auto Shifted = tooling::Replacement(FileName, NewOffset, 0,
2128                                             Replace->getReplacementText());
2129         Result = Result.merge(tooling::Replacements(Shifted));
2130       }
2131     }
2132   }
2133   return Result;
2134 }
2135 
2136 } // anonymous namespace
2137 
2138 llvm::Expected<tooling::Replacements>
2139 cleanupAroundReplacements(StringRef Code, const tooling::Replacements &Replaces,
2140                           const FormatStyle &Style) {
2141   // We need to use lambda function here since there are two versions of
2142   // `cleanup`.
2143   auto Cleanup = [](const FormatStyle &Style, StringRef Code,
2144                     std::vector<tooling::Range> Ranges,
2145                     StringRef FileName) -> tooling::Replacements {
2146     return cleanup(Style, Code, Ranges, FileName);
2147   };
2148   // Make header insertion replacements insert new headers into correct blocks.
2149   tooling::Replacements NewReplaces =
2150       fixCppIncludeInsertions(Code, Replaces, Style);
2151   return processReplacements(Cleanup, Code, NewReplaces, Style);
2152 }
2153 
2154 namespace internal {
2155 std::pair<tooling::Replacements, unsigned>
2156 reformat(const FormatStyle &Style, StringRef Code,
2157          ArrayRef<tooling::Range> Ranges, unsigned FirstStartColumn,
2158          unsigned NextStartColumn, unsigned LastStartColumn, StringRef FileName,
2159          FormattingAttemptStatus *Status) {
2160   FormatStyle Expanded = expandPresets(Style);
2161   if (Expanded.DisableFormat)
2162     return {tooling::Replacements(), 0};
2163   if (isLikelyXml(Code))
2164     return {tooling::Replacements(), 0};
2165   if (Expanded.Language == FormatStyle::LK_JavaScript && isMpegTS(Code))
2166     return {tooling::Replacements(), 0};
2167 
2168   typedef std::function<std::pair<tooling::Replacements, unsigned>(
2169       const Environment &)>
2170       AnalyzerPass;
2171   SmallVector<AnalyzerPass, 4> Passes;
2172 
2173   if (Style.Language == FormatStyle::LK_Cpp) {
2174     if (Style.FixNamespaceComments)
2175       Passes.emplace_back([&](const Environment &Env) {
2176         return NamespaceEndCommentsFixer(Env, Expanded).process();
2177       });
2178 
2179     if (Style.SortUsingDeclarations)
2180       Passes.emplace_back([&](const Environment &Env) {
2181         return UsingDeclarationsSorter(Env, Expanded).process();
2182       });
2183   }
2184 
2185   if (Style.Language == FormatStyle::LK_JavaScript &&
2186       Style.JavaScriptQuotes != FormatStyle::JSQS_Leave)
2187     Passes.emplace_back([&](const Environment &Env) {
2188       return JavaScriptRequoter(Env, Expanded).process();
2189     });
2190 
2191   Passes.emplace_back([&](const Environment &Env) {
2192     return Formatter(Env, Expanded, Status).process();
2193   });
2194 
2195   auto Env =
2196       llvm::make_unique<Environment>(Code, FileName, Ranges, FirstStartColumn,
2197                                      NextStartColumn, LastStartColumn);
2198   llvm::Optional<std::string> CurrentCode = None;
2199   tooling::Replacements Fixes;
2200   unsigned Penalty = 0;
2201   for (size_t I = 0, E = Passes.size(); I < E; ++I) {
2202     std::pair<tooling::Replacements, unsigned> PassFixes = Passes[I](*Env);
2203     auto NewCode = applyAllReplacements(
2204         CurrentCode ? StringRef(*CurrentCode) : Code, PassFixes.first);
2205     if (NewCode) {
2206       Fixes = Fixes.merge(PassFixes.first);
2207       Penalty += PassFixes.second;
2208       if (I + 1 < E) {
2209         CurrentCode = std::move(*NewCode);
2210         Env = llvm::make_unique<Environment>(
2211             *CurrentCode, FileName,
2212             tooling::calculateRangesAfterReplacements(Fixes, Ranges),
2213             FirstStartColumn, NextStartColumn, LastStartColumn);
2214       }
2215     }
2216   }
2217 
2218   return {Fixes, Penalty};
2219 }
2220 } // namespace internal
2221 
2222 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
2223                                ArrayRef<tooling::Range> Ranges,
2224                                StringRef FileName,
2225                                FormattingAttemptStatus *Status) {
2226   return internal::reformat(Style, Code, Ranges,
2227                             /*FirstStartColumn=*/0,
2228                             /*NextStartColumn=*/0,
2229                             /*LastStartColumn=*/0, FileName, Status)
2230       .first;
2231 }
2232 
2233 tooling::Replacements cleanup(const FormatStyle &Style, StringRef Code,
2234                               ArrayRef<tooling::Range> Ranges,
2235                               StringRef FileName) {
2236   // cleanups only apply to C++ (they mostly concern ctor commas etc.)
2237   if (Style.Language != FormatStyle::LK_Cpp)
2238     return tooling::Replacements();
2239   return Cleaner(Environment(Code, FileName, Ranges), Style).process().first;
2240 }
2241 
2242 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
2243                                ArrayRef<tooling::Range> Ranges,
2244                                StringRef FileName, bool *IncompleteFormat) {
2245   FormattingAttemptStatus Status;
2246   auto Result = reformat(Style, Code, Ranges, FileName, &Status);
2247   if (!Status.FormatComplete)
2248     *IncompleteFormat = true;
2249   return Result;
2250 }
2251 
2252 tooling::Replacements fixNamespaceEndComments(const FormatStyle &Style,
2253                                               StringRef Code,
2254                                               ArrayRef<tooling::Range> Ranges,
2255                                               StringRef FileName) {
2256   return NamespaceEndCommentsFixer(Environment(Code, FileName, Ranges), Style)
2257       .process()
2258       .first;
2259 }
2260 
2261 tooling::Replacements sortUsingDeclarations(const FormatStyle &Style,
2262                                             StringRef Code,
2263                                             ArrayRef<tooling::Range> Ranges,
2264                                             StringRef FileName) {
2265   return UsingDeclarationsSorter(Environment(Code, FileName, Ranges), Style)
2266       .process()
2267       .first;
2268 }
2269 
2270 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
2271   LangOptions LangOpts;
2272   LangOpts.CPlusPlus = 1;
2273   LangOpts.CPlusPlus11 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
2274   LangOpts.CPlusPlus14 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
2275   LangOpts.CPlusPlus17 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
2276   LangOpts.CPlusPlus2a = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
2277   LangOpts.LineComment = 1;
2278   bool AlternativeOperators = Style.isCpp();
2279   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
2280   LangOpts.Bool = 1;
2281   LangOpts.ObjC = 1;
2282   LangOpts.MicrosoftExt = 1;    // To get kw___try, kw___finally.
2283   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
2284   return LangOpts;
2285 }
2286 
2287 const char *StyleOptionHelpDescription =
2288     "Coding style, currently supports:\n"
2289     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
2290     "Use -style=file to load style configuration from\n"
2291     ".clang-format file located in one of the parent\n"
2292     "directories of the source file (or current\n"
2293     "directory for stdin).\n"
2294     "Use -style=\"{key: value, ...}\" to set specific\n"
2295     "parameters, e.g.:\n"
2296     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
2297 
2298 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
2299   if (FileName.endswith(".java"))
2300     return FormatStyle::LK_Java;
2301   if (FileName.endswith_lower(".js") || FileName.endswith_lower(".ts"))
2302     return FormatStyle::LK_JavaScript; // JavaScript or TypeScript.
2303   if (FileName.endswith(".m") || FileName.endswith(".mm"))
2304     return FormatStyle::LK_ObjC;
2305   if (FileName.endswith_lower(".proto") ||
2306       FileName.endswith_lower(".protodevel"))
2307     return FormatStyle::LK_Proto;
2308   if (FileName.endswith_lower(".textpb") ||
2309       FileName.endswith_lower(".pb.txt") ||
2310       FileName.endswith_lower(".textproto") ||
2311       FileName.endswith_lower(".asciipb"))
2312     return FormatStyle::LK_TextProto;
2313   if (FileName.endswith_lower(".td"))
2314     return FormatStyle::LK_TableGen;
2315   return FormatStyle::LK_Cpp;
2316 }
2317 
2318 FormatStyle::LanguageKind guessLanguage(StringRef FileName, StringRef Code) {
2319   const auto GuessedLanguage = getLanguageByFileName(FileName);
2320   if (GuessedLanguage == FormatStyle::LK_Cpp) {
2321     auto Extension = llvm::sys::path::extension(FileName);
2322     // If there's no file extension (or it's .h), we need to check the contents
2323     // of the code to see if it contains Objective-C.
2324     if (Extension.empty() || Extension == ".h") {
2325       auto NonEmptyFileName = FileName.empty() ? "guess.h" : FileName;
2326       Environment Env(Code, NonEmptyFileName, /*Ranges=*/{});
2327       ObjCHeaderStyleGuesser Guesser(Env, getLLVMStyle());
2328       Guesser.process();
2329       if (Guesser.isObjC())
2330         return FormatStyle::LK_ObjC;
2331     }
2332   }
2333   return GuessedLanguage;
2334 }
2335 
2336 const char *DefaultFormatStyle = "file";
2337 
2338 const char *DefaultFallbackStyle = "LLVM";
2339 
2340 llvm::Expected<FormatStyle> getStyle(StringRef StyleName, StringRef FileName,
2341                                      StringRef FallbackStyleName,
2342                                      StringRef Code,
2343                                      llvm::vfs::FileSystem *FS) {
2344   if (!FS) {
2345     FS = llvm::vfs::getRealFileSystem().get();
2346   }
2347   FormatStyle Style = getLLVMStyle();
2348   Style.Language = guessLanguage(FileName, Code);
2349 
2350   FormatStyle FallbackStyle = getNoStyle();
2351   if (!getPredefinedStyle(FallbackStyleName, Style.Language, &FallbackStyle))
2352     return make_string_error("Invalid fallback style \"" + FallbackStyleName);
2353 
2354   if (StyleName.startswith("{")) {
2355     // Parse YAML/JSON style from the command line.
2356     if (std::error_code ec = parseConfiguration(StyleName, &Style))
2357       return make_string_error("Error parsing -style: " + ec.message());
2358     return Style;
2359   }
2360 
2361   if (!StyleName.equals_lower("file")) {
2362     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
2363       return make_string_error("Invalid value for -style");
2364     return Style;
2365   }
2366 
2367   // Look for .clang-format/_clang-format file in the file's parent directories.
2368   SmallString<128> UnsuitableConfigFiles;
2369   SmallString<128> Path(FileName);
2370   if (std::error_code EC = FS->makeAbsolute(Path))
2371     return make_string_error(EC.message());
2372 
2373   for (StringRef Directory = Path; !Directory.empty();
2374        Directory = llvm::sys::path::parent_path(Directory)) {
2375 
2376     auto Status = FS->status(Directory);
2377     if (!Status ||
2378         Status->getType() != llvm::sys::fs::file_type::directory_file) {
2379       continue;
2380     }
2381 
2382     SmallString<128> ConfigFile(Directory);
2383 
2384     llvm::sys::path::append(ConfigFile, ".clang-format");
2385     LLVM_DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2386 
2387     Status = FS->status(ConfigFile.str());
2388     bool FoundConfigFile =
2389         Status && (Status->getType() == llvm::sys::fs::file_type::regular_file);
2390     if (!FoundConfigFile) {
2391       // Try _clang-format too, since dotfiles are not commonly used on Windows.
2392       ConfigFile = Directory;
2393       llvm::sys::path::append(ConfigFile, "_clang-format");
2394       LLVM_DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2395       Status = FS->status(ConfigFile.str());
2396       FoundConfigFile = Status && (Status->getType() ==
2397                                    llvm::sys::fs::file_type::regular_file);
2398     }
2399 
2400     if (FoundConfigFile) {
2401       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
2402           FS->getBufferForFile(ConfigFile.str());
2403       if (std::error_code EC = Text.getError())
2404         return make_string_error(EC.message());
2405       if (std::error_code ec =
2406               parseConfiguration(Text.get()->getBuffer(), &Style)) {
2407         if (ec == ParseError::Unsuitable) {
2408           if (!UnsuitableConfigFiles.empty())
2409             UnsuitableConfigFiles.append(", ");
2410           UnsuitableConfigFiles.append(ConfigFile);
2411           continue;
2412         }
2413         return make_string_error("Error reading " + ConfigFile + ": " +
2414                                  ec.message());
2415       }
2416       LLVM_DEBUG(llvm::dbgs()
2417                  << "Using configuration file " << ConfigFile << "\n");
2418       return Style;
2419     }
2420   }
2421   if (!UnsuitableConfigFiles.empty())
2422     return make_string_error("Configuration file(s) do(es) not support " +
2423                              getLanguageName(Style.Language) + ": " +
2424                              UnsuitableConfigFiles);
2425   return FallbackStyle;
2426 }
2427 
2428 } // namespace format
2429 } // namespace clang
2430