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