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