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