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() &&
2053       std::is_sorted(Indices.begin(), Indices.end()) &&
2054       Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Preserve)
2055     return;
2056 
2057   std::string result;
2058   for (unsigned Index : Indices) {
2059     if (!result.empty()) {
2060       result += "\n";
2061       if (Style.IncludeStyle.IncludeBlocks ==
2062               tooling::IncludeStyle::IBS_Regroup &&
2063           CurrentCategory != Includes[Index].Category)
2064         result += "\n";
2065     }
2066     result += Includes[Index].Text;
2067     if (Cursor && CursorIndex == Index)
2068       *Cursor = IncludesBeginOffset + result.size() - CursorToEOLOffset;
2069     CurrentCategory = Includes[Index].Category;
2070   }
2071 
2072   // If the #includes are out of order, we generate a single replacement fixing
2073   // the entire range of blocks. Otherwise, no replacement is generated.
2074   if (replaceCRLF(result) == replaceCRLF(std::string(Code.substr(
2075                                  IncludesBeginOffset, IncludesBlockSize))))
2076     return;
2077 
2078   auto Err = Replaces.add(tooling::Replacement(
2079       FileName, Includes.front().Offset, IncludesBlockSize, result));
2080   // FIXME: better error handling. For now, just skip the replacement for the
2081   // release version.
2082   if (Err) {
2083     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
2084     assert(false);
2085   }
2086 }
2087 
2088 namespace {
2089 
2090 const char CppIncludeRegexPattern[] =
2091     R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
2092 
2093 } // anonymous namespace
2094 
2095 tooling::Replacements sortCppIncludes(const FormatStyle &Style, StringRef Code,
2096                                       ArrayRef<tooling::Range> Ranges,
2097                                       StringRef FileName,
2098                                       tooling::Replacements &Replaces,
2099                                       unsigned *Cursor) {
2100   unsigned Prev = 0;
2101   unsigned SearchFrom = 0;
2102   llvm::Regex IncludeRegex(CppIncludeRegexPattern);
2103   SmallVector<StringRef, 4> Matches;
2104   SmallVector<IncludeDirective, 16> IncludesInBlock;
2105 
2106   // In compiled files, consider the first #include to be the main #include of
2107   // the file if it is not a system #include. This ensures that the header
2108   // doesn't have hidden dependencies
2109   // (http://llvm.org/docs/CodingStandards.html#include-style).
2110   //
2111   // FIXME: Do some sanity checking, e.g. edit distance of the base name, to fix
2112   // cases where the first #include is unlikely to be the main header.
2113   tooling::IncludeCategoryManager Categories(Style.IncludeStyle, FileName);
2114   bool FirstIncludeBlock = true;
2115   bool MainIncludeFound = false;
2116   bool FormattingOff = false;
2117 
2118   for (;;) {
2119     auto Pos = Code.find('\n', SearchFrom);
2120     StringRef Line =
2121         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
2122 
2123     StringRef Trimmed = Line.trim();
2124     if (Trimmed == "// clang-format off" || Trimmed == "/* clang-format off */")
2125       FormattingOff = true;
2126     else if (Trimmed == "// clang-format on" ||
2127              Trimmed == "/* clang-format on */")
2128       FormattingOff = false;
2129 
2130     const bool EmptyLineSkipped =
2131         Trimmed.empty() &&
2132         (Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Merge ||
2133          Style.IncludeStyle.IncludeBlocks ==
2134              tooling::IncludeStyle::IBS_Regroup);
2135 
2136     if (!FormattingOff && !Line.endswith("\\")) {
2137       if (IncludeRegex.match(Line, &Matches)) {
2138         StringRef IncludeName = Matches[2];
2139         int Category = Categories.getIncludePriority(
2140             IncludeName,
2141             /*CheckMainHeader=*/!MainIncludeFound && FirstIncludeBlock);
2142         int Priority = Categories.getSortIncludePriority(
2143             IncludeName, !MainIncludeFound && FirstIncludeBlock);
2144         if (Category == 0)
2145           MainIncludeFound = true;
2146         IncludesInBlock.push_back(
2147             {IncludeName, Line, Prev, Category, Priority});
2148       } else if (!IncludesInBlock.empty() && !EmptyLineSkipped) {
2149         sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code,
2150                         Replaces, Cursor);
2151         IncludesInBlock.clear();
2152         FirstIncludeBlock = false;
2153       }
2154       Prev = Pos + 1;
2155     }
2156     if (Pos == StringRef::npos || Pos + 1 == Code.size())
2157       break;
2158     SearchFrom = Pos + 1;
2159   }
2160   if (!IncludesInBlock.empty()) {
2161     sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code, Replaces,
2162                     Cursor);
2163   }
2164   return Replaces;
2165 }
2166 
2167 // Returns group number to use as a first order sort on imports. Gives UINT_MAX
2168 // if the import does not match any given groups.
2169 static unsigned findJavaImportGroup(const FormatStyle &Style,
2170                                     StringRef ImportIdentifier) {
2171   unsigned LongestMatchIndex = UINT_MAX;
2172   unsigned LongestMatchLength = 0;
2173   for (unsigned I = 0; I < Style.JavaImportGroups.size(); I++) {
2174     std::string GroupPrefix = Style.JavaImportGroups[I];
2175     if (ImportIdentifier.startswith(GroupPrefix) &&
2176         GroupPrefix.length() > LongestMatchLength) {
2177       LongestMatchIndex = I;
2178       LongestMatchLength = GroupPrefix.length();
2179     }
2180   }
2181   return LongestMatchIndex;
2182 }
2183 
2184 // Sorts and deduplicates a block of includes given by 'Imports' based on
2185 // JavaImportGroups, then adding the necessary replacement to 'Replaces'.
2186 // Import declarations with the same text will be deduplicated. Between each
2187 // import group, a newline is inserted, and within each import group, a
2188 // lexicographic sort based on ASCII value is performed.
2189 static void sortJavaImports(const FormatStyle &Style,
2190                             const SmallVectorImpl<JavaImportDirective> &Imports,
2191                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
2192                             StringRef Code, tooling::Replacements &Replaces) {
2193   unsigned ImportsBeginOffset = Imports.front().Offset;
2194   unsigned ImportsEndOffset =
2195       Imports.back().Offset + Imports.back().Text.size();
2196   unsigned ImportsBlockSize = ImportsEndOffset - ImportsBeginOffset;
2197   if (!affectsRange(Ranges, ImportsBeginOffset, ImportsEndOffset))
2198     return;
2199   SmallVector<unsigned, 16> Indices;
2200   SmallVector<unsigned, 16> JavaImportGroups;
2201   for (unsigned i = 0, e = Imports.size(); i != e; ++i) {
2202     Indices.push_back(i);
2203     JavaImportGroups.push_back(
2204         findJavaImportGroup(Style, Imports[i].Identifier));
2205   }
2206   llvm::sort(Indices, [&](unsigned LHSI, unsigned RHSI) {
2207     // Negating IsStatic to push static imports above non-static imports.
2208     return std::make_tuple(!Imports[LHSI].IsStatic, JavaImportGroups[LHSI],
2209                            Imports[LHSI].Identifier) <
2210            std::make_tuple(!Imports[RHSI].IsStatic, JavaImportGroups[RHSI],
2211                            Imports[RHSI].Identifier);
2212   });
2213 
2214   // Deduplicate imports.
2215   Indices.erase(std::unique(Indices.begin(), Indices.end(),
2216                             [&](unsigned LHSI, unsigned RHSI) {
2217                               return Imports[LHSI].Text == Imports[RHSI].Text;
2218                             }),
2219                 Indices.end());
2220 
2221   bool CurrentIsStatic = Imports[Indices.front()].IsStatic;
2222   unsigned CurrentImportGroup = JavaImportGroups[Indices.front()];
2223 
2224   std::string result;
2225   for (unsigned Index : Indices) {
2226     if (!result.empty()) {
2227       result += "\n";
2228       if (CurrentIsStatic != Imports[Index].IsStatic ||
2229           CurrentImportGroup != JavaImportGroups[Index])
2230         result += "\n";
2231     }
2232     for (StringRef CommentLine : Imports[Index].AssociatedCommentLines) {
2233       result += CommentLine;
2234       result += "\n";
2235     }
2236     result += Imports[Index].Text;
2237     CurrentIsStatic = Imports[Index].IsStatic;
2238     CurrentImportGroup = JavaImportGroups[Index];
2239   }
2240 
2241   // If the imports are out of order, we generate a single replacement fixing
2242   // the entire block. Otherwise, no replacement is generated.
2243   if (replaceCRLF(result) == replaceCRLF(std::string(Code.substr(
2244                                  Imports.front().Offset, ImportsBlockSize))))
2245     return;
2246 
2247   auto Err = Replaces.add(tooling::Replacement(FileName, Imports.front().Offset,
2248                                                ImportsBlockSize, result));
2249   // FIXME: better error handling. For now, just skip the replacement for the
2250   // release version.
2251   if (Err) {
2252     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
2253     assert(false);
2254   }
2255 }
2256 
2257 namespace {
2258 
2259 const char JavaImportRegexPattern[] =
2260     "^[\t ]*import[\t ]+(static[\t ]*)?([^\t ]*)[\t ]*;";
2261 
2262 } // anonymous namespace
2263 
2264 tooling::Replacements sortJavaImports(const FormatStyle &Style, StringRef Code,
2265                                       ArrayRef<tooling::Range> Ranges,
2266                                       StringRef FileName,
2267                                       tooling::Replacements &Replaces) {
2268   unsigned Prev = 0;
2269   unsigned SearchFrom = 0;
2270   llvm::Regex ImportRegex(JavaImportRegexPattern);
2271   SmallVector<StringRef, 4> Matches;
2272   SmallVector<JavaImportDirective, 16> ImportsInBlock;
2273   std::vector<StringRef> AssociatedCommentLines;
2274 
2275   bool FormattingOff = false;
2276 
2277   for (;;) {
2278     auto Pos = Code.find('\n', SearchFrom);
2279     StringRef Line =
2280         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
2281 
2282     StringRef Trimmed = Line.trim();
2283     if (Trimmed == "// clang-format off")
2284       FormattingOff = true;
2285     else if (Trimmed == "// clang-format on")
2286       FormattingOff = false;
2287 
2288     if (ImportRegex.match(Line, &Matches)) {
2289       if (FormattingOff) {
2290         // If at least one import line has formatting turned off, turn off
2291         // formatting entirely.
2292         return Replaces;
2293       }
2294       StringRef Static = Matches[1];
2295       StringRef Identifier = Matches[2];
2296       bool IsStatic = false;
2297       if (Static.contains("static")) {
2298         IsStatic = true;
2299       }
2300       ImportsInBlock.push_back(
2301           {Identifier, Line, Prev, AssociatedCommentLines, IsStatic});
2302       AssociatedCommentLines.clear();
2303     } else if (Trimmed.size() > 0 && !ImportsInBlock.empty()) {
2304       // Associating comments within the imports with the nearest import below
2305       AssociatedCommentLines.push_back(Line);
2306     }
2307     Prev = Pos + 1;
2308     if (Pos == StringRef::npos || Pos + 1 == Code.size())
2309       break;
2310     SearchFrom = Pos + 1;
2311   }
2312   if (!ImportsInBlock.empty())
2313     sortJavaImports(Style, ImportsInBlock, Ranges, FileName, Code, Replaces);
2314   return Replaces;
2315 }
2316 
2317 bool isMpegTS(StringRef Code) {
2318   // MPEG transport streams use the ".ts" file extension. clang-format should
2319   // not attempt to format those. MPEG TS' frame format starts with 0x47 every
2320   // 189 bytes - detect that and return.
2321   return Code.size() > 188 && Code[0] == 0x47 && Code[188] == 0x47;
2322 }
2323 
2324 bool isLikelyXml(StringRef Code) { return Code.ltrim().startswith("<"); }
2325 
2326 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
2327                                    ArrayRef<tooling::Range> Ranges,
2328                                    StringRef FileName, unsigned *Cursor) {
2329   tooling::Replacements Replaces;
2330   if (!Style.SortIncludes)
2331     return Replaces;
2332   if (isLikelyXml(Code))
2333     return Replaces;
2334   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript &&
2335       isMpegTS(Code))
2336     return Replaces;
2337   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript)
2338     return sortJavaScriptImports(Style, Code, Ranges, FileName);
2339   if (Style.Language == FormatStyle::LanguageKind::LK_Java)
2340     return sortJavaImports(Style, Code, Ranges, FileName, Replaces);
2341   sortCppIncludes(Style, Code, Ranges, FileName, Replaces, Cursor);
2342   return Replaces;
2343 }
2344 
2345 template <typename T>
2346 static llvm::Expected<tooling::Replacements>
2347 processReplacements(T ProcessFunc, StringRef Code,
2348                     const tooling::Replacements &Replaces,
2349                     const FormatStyle &Style) {
2350   if (Replaces.empty())
2351     return tooling::Replacements();
2352 
2353   auto NewCode = applyAllReplacements(Code, Replaces);
2354   if (!NewCode)
2355     return NewCode.takeError();
2356   std::vector<tooling::Range> ChangedRanges = Replaces.getAffectedRanges();
2357   StringRef FileName = Replaces.begin()->getFilePath();
2358 
2359   tooling::Replacements FormatReplaces =
2360       ProcessFunc(Style, *NewCode, ChangedRanges, FileName);
2361 
2362   return Replaces.merge(FormatReplaces);
2363 }
2364 
2365 llvm::Expected<tooling::Replacements>
2366 formatReplacements(StringRef Code, const tooling::Replacements &Replaces,
2367                    const FormatStyle &Style) {
2368   // We need to use lambda function here since there are two versions of
2369   // `sortIncludes`.
2370   auto SortIncludes = [](const FormatStyle &Style, StringRef Code,
2371                          std::vector<tooling::Range> Ranges,
2372                          StringRef FileName) -> tooling::Replacements {
2373     return sortIncludes(Style, Code, Ranges, FileName);
2374   };
2375   auto SortedReplaces =
2376       processReplacements(SortIncludes, Code, Replaces, Style);
2377   if (!SortedReplaces)
2378     return SortedReplaces.takeError();
2379 
2380   // We need to use lambda function here since there are two versions of
2381   // `reformat`.
2382   auto Reformat = [](const FormatStyle &Style, StringRef Code,
2383                      std::vector<tooling::Range> Ranges,
2384                      StringRef FileName) -> tooling::Replacements {
2385     return reformat(Style, Code, Ranges, FileName);
2386   };
2387   return processReplacements(Reformat, Code, *SortedReplaces, Style);
2388 }
2389 
2390 namespace {
2391 
2392 inline bool isHeaderInsertion(const tooling::Replacement &Replace) {
2393   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 0 &&
2394          llvm::Regex(CppIncludeRegexPattern)
2395              .match(Replace.getReplacementText());
2396 }
2397 
2398 inline bool isHeaderDeletion(const tooling::Replacement &Replace) {
2399   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 1;
2400 }
2401 
2402 // FIXME: insert empty lines between newly created blocks.
2403 tooling::Replacements
2404 fixCppIncludeInsertions(StringRef Code, const tooling::Replacements &Replaces,
2405                         const FormatStyle &Style) {
2406   if (!Style.isCpp())
2407     return Replaces;
2408 
2409   tooling::Replacements HeaderInsertions;
2410   std::set<llvm::StringRef> HeadersToDelete;
2411   tooling::Replacements Result;
2412   for (const auto &R : Replaces) {
2413     if (isHeaderInsertion(R)) {
2414       // Replacements from \p Replaces must be conflict-free already, so we can
2415       // simply consume the error.
2416       llvm::consumeError(HeaderInsertions.add(R));
2417     } else if (isHeaderDeletion(R)) {
2418       HeadersToDelete.insert(R.getReplacementText());
2419     } else if (R.getOffset() == UINT_MAX) {
2420       llvm::errs() << "Insertions other than header #include insertion are "
2421                       "not supported! "
2422                    << R.getReplacementText() << "\n";
2423     } else {
2424       llvm::consumeError(Result.add(R));
2425     }
2426   }
2427   if (HeaderInsertions.empty() && HeadersToDelete.empty())
2428     return Replaces;
2429 
2430   StringRef FileName = Replaces.begin()->getFilePath();
2431   tooling::HeaderIncludes Includes(FileName, Code, Style.IncludeStyle);
2432 
2433   for (const auto &Header : HeadersToDelete) {
2434     tooling::Replacements Replaces =
2435         Includes.remove(Header.trim("\"<>"), Header.startswith("<"));
2436     for (const auto &R : Replaces) {
2437       auto Err = Result.add(R);
2438       if (Err) {
2439         // Ignore the deletion on conflict.
2440         llvm::errs() << "Failed to add header deletion replacement for "
2441                      << Header << ": " << llvm::toString(std::move(Err))
2442                      << "\n";
2443       }
2444     }
2445   }
2446 
2447   llvm::Regex IncludeRegex = llvm::Regex(CppIncludeRegexPattern);
2448   llvm::SmallVector<StringRef, 4> Matches;
2449   for (const auto &R : HeaderInsertions) {
2450     auto IncludeDirective = R.getReplacementText();
2451     bool Matched = IncludeRegex.match(IncludeDirective, &Matches);
2452     assert(Matched && "Header insertion replacement must have replacement text "
2453                       "'#include ...'");
2454     (void)Matched;
2455     auto IncludeName = Matches[2];
2456     auto Replace =
2457         Includes.insert(IncludeName.trim("\"<>"), IncludeName.startswith("<"));
2458     if (Replace) {
2459       auto Err = Result.add(*Replace);
2460       if (Err) {
2461         llvm::consumeError(std::move(Err));
2462         unsigned NewOffset =
2463             Result.getShiftedCodePosition(Replace->getOffset());
2464         auto Shifted = tooling::Replacement(FileName, NewOffset, 0,
2465                                             Replace->getReplacementText());
2466         Result = Result.merge(tooling::Replacements(Shifted));
2467       }
2468     }
2469   }
2470   return Result;
2471 }
2472 
2473 } // anonymous namespace
2474 
2475 llvm::Expected<tooling::Replacements>
2476 cleanupAroundReplacements(StringRef Code, const tooling::Replacements &Replaces,
2477                           const FormatStyle &Style) {
2478   // We need to use lambda function here since there are two versions of
2479   // `cleanup`.
2480   auto Cleanup = [](const FormatStyle &Style, StringRef Code,
2481                     std::vector<tooling::Range> Ranges,
2482                     StringRef FileName) -> tooling::Replacements {
2483     return cleanup(Style, Code, Ranges, FileName);
2484   };
2485   // Make header insertion replacements insert new headers into correct blocks.
2486   tooling::Replacements NewReplaces =
2487       fixCppIncludeInsertions(Code, Replaces, Style);
2488   return processReplacements(Cleanup, Code, NewReplaces, Style);
2489 }
2490 
2491 namespace internal {
2492 std::pair<tooling::Replacements, unsigned>
2493 reformat(const FormatStyle &Style, StringRef Code,
2494          ArrayRef<tooling::Range> Ranges, unsigned FirstStartColumn,
2495          unsigned NextStartColumn, unsigned LastStartColumn, StringRef FileName,
2496          FormattingAttemptStatus *Status) {
2497   FormatStyle Expanded = expandPresets(Style);
2498   if (Expanded.DisableFormat)
2499     return {tooling::Replacements(), 0};
2500   if (isLikelyXml(Code))
2501     return {tooling::Replacements(), 0};
2502   if (Expanded.Language == FormatStyle::LK_JavaScript && isMpegTS(Code))
2503     return {tooling::Replacements(), 0};
2504 
2505   typedef std::function<std::pair<tooling::Replacements, unsigned>(
2506       const Environment &)>
2507       AnalyzerPass;
2508   SmallVector<AnalyzerPass, 4> Passes;
2509 
2510   if (Style.Language == FormatStyle::LK_Cpp) {
2511     if (Style.FixNamespaceComments)
2512       Passes.emplace_back([&](const Environment &Env) {
2513         return NamespaceEndCommentsFixer(Env, Expanded).process();
2514       });
2515 
2516     if (Style.SortUsingDeclarations)
2517       Passes.emplace_back([&](const Environment &Env) {
2518         return UsingDeclarationsSorter(Env, Expanded).process();
2519       });
2520   }
2521 
2522   if (Style.Language == FormatStyle::LK_JavaScript &&
2523       Style.JavaScriptQuotes != FormatStyle::JSQS_Leave)
2524     Passes.emplace_back([&](const Environment &Env) {
2525       return JavaScriptRequoter(Env, Expanded).process();
2526     });
2527 
2528   Passes.emplace_back([&](const Environment &Env) {
2529     return Formatter(Env, Expanded, Status).process();
2530   });
2531 
2532   if (Style.Language == FormatStyle::LK_JavaScript &&
2533       Style.InsertTrailingCommas == FormatStyle::TCS_Wrapped)
2534     Passes.emplace_back([&](const Environment &Env) {
2535       return TrailingCommaInserter(Env, Expanded).process();
2536     });
2537 
2538   auto Env =
2539       std::make_unique<Environment>(Code, FileName, Ranges, FirstStartColumn,
2540                                     NextStartColumn, LastStartColumn);
2541   llvm::Optional<std::string> CurrentCode = None;
2542   tooling::Replacements Fixes;
2543   unsigned Penalty = 0;
2544   for (size_t I = 0, E = Passes.size(); I < E; ++I) {
2545     std::pair<tooling::Replacements, unsigned> PassFixes = Passes[I](*Env);
2546     auto NewCode = applyAllReplacements(
2547         CurrentCode ? StringRef(*CurrentCode) : Code, PassFixes.first);
2548     if (NewCode) {
2549       Fixes = Fixes.merge(PassFixes.first);
2550       Penalty += PassFixes.second;
2551       if (I + 1 < E) {
2552         CurrentCode = std::move(*NewCode);
2553         Env = std::make_unique<Environment>(
2554             *CurrentCode, FileName,
2555             tooling::calculateRangesAfterReplacements(Fixes, Ranges),
2556             FirstStartColumn, NextStartColumn, LastStartColumn);
2557       }
2558     }
2559   }
2560 
2561   return {Fixes, Penalty};
2562 }
2563 } // namespace internal
2564 
2565 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
2566                                ArrayRef<tooling::Range> Ranges,
2567                                StringRef FileName,
2568                                FormattingAttemptStatus *Status) {
2569   return internal::reformat(Style, Code, Ranges,
2570                             /*FirstStartColumn=*/0,
2571                             /*NextStartColumn=*/0,
2572                             /*LastStartColumn=*/0, FileName, Status)
2573       .first;
2574 }
2575 
2576 tooling::Replacements cleanup(const FormatStyle &Style, StringRef Code,
2577                               ArrayRef<tooling::Range> Ranges,
2578                               StringRef FileName) {
2579   // cleanups only apply to C++ (they mostly concern ctor commas etc.)
2580   if (Style.Language != FormatStyle::LK_Cpp)
2581     return tooling::Replacements();
2582   return Cleaner(Environment(Code, FileName, Ranges), Style).process().first;
2583 }
2584 
2585 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
2586                                ArrayRef<tooling::Range> Ranges,
2587                                StringRef FileName, bool *IncompleteFormat) {
2588   FormattingAttemptStatus Status;
2589   auto Result = reformat(Style, Code, Ranges, FileName, &Status);
2590   if (!Status.FormatComplete)
2591     *IncompleteFormat = true;
2592   return Result;
2593 }
2594 
2595 tooling::Replacements fixNamespaceEndComments(const FormatStyle &Style,
2596                                               StringRef Code,
2597                                               ArrayRef<tooling::Range> Ranges,
2598                                               StringRef FileName) {
2599   return NamespaceEndCommentsFixer(Environment(Code, FileName, Ranges), Style)
2600       .process()
2601       .first;
2602 }
2603 
2604 tooling::Replacements sortUsingDeclarations(const FormatStyle &Style,
2605                                             StringRef Code,
2606                                             ArrayRef<tooling::Range> Ranges,
2607                                             StringRef FileName) {
2608   return UsingDeclarationsSorter(Environment(Code, FileName, Ranges), Style)
2609       .process()
2610       .first;
2611 }
2612 
2613 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
2614   LangOptions LangOpts;
2615 
2616   FormatStyle::LanguageStandard LexingStd = Style.Standard;
2617   if (LexingStd == FormatStyle::LS_Auto)
2618     LexingStd = FormatStyle::LS_Latest;
2619   if (LexingStd == FormatStyle::LS_Latest)
2620     LexingStd = FormatStyle::LS_Cpp20;
2621   LangOpts.CPlusPlus = 1;
2622   LangOpts.CPlusPlus11 = LexingStd >= FormatStyle::LS_Cpp11;
2623   LangOpts.CPlusPlus14 = LexingStd >= FormatStyle::LS_Cpp14;
2624   LangOpts.CPlusPlus17 = LexingStd >= FormatStyle::LS_Cpp17;
2625   LangOpts.CPlusPlus2a = LexingStd >= FormatStyle::LS_Cpp20;
2626 
2627   LangOpts.LineComment = 1;
2628   bool AlternativeOperators = Style.isCpp();
2629   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
2630   LangOpts.Bool = 1;
2631   LangOpts.ObjC = 1;
2632   LangOpts.MicrosoftExt = 1;    // To get kw___try, kw___finally.
2633   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
2634   return LangOpts;
2635 }
2636 
2637 const char *StyleOptionHelpDescription =
2638     "Coding style, currently supports:\n"
2639     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
2640     "Use -style=file to load style configuration from\n"
2641     ".clang-format file located in one of the parent\n"
2642     "directories of the source file (or current\n"
2643     "directory for stdin).\n"
2644     "Use -style=\"{key: value, ...}\" to set specific\n"
2645     "parameters, e.g.:\n"
2646     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
2647 
2648 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
2649   if (FileName.endswith(".java"))
2650     return FormatStyle::LK_Java;
2651   if (FileName.endswith_lower(".js") || FileName.endswith_lower(".mjs") ||
2652       FileName.endswith_lower(".ts"))
2653     return FormatStyle::LK_JavaScript; // (module) JavaScript or TypeScript.
2654   if (FileName.endswith(".m") || FileName.endswith(".mm"))
2655     return FormatStyle::LK_ObjC;
2656   if (FileName.endswith_lower(".proto") ||
2657       FileName.endswith_lower(".protodevel"))
2658     return FormatStyle::LK_Proto;
2659   if (FileName.endswith_lower(".textpb") ||
2660       FileName.endswith_lower(".pb.txt") ||
2661       FileName.endswith_lower(".textproto") ||
2662       FileName.endswith_lower(".asciipb"))
2663     return FormatStyle::LK_TextProto;
2664   if (FileName.endswith_lower(".td"))
2665     return FormatStyle::LK_TableGen;
2666   if (FileName.endswith_lower(".cs"))
2667     return FormatStyle::LK_CSharp;
2668   return FormatStyle::LK_Cpp;
2669 }
2670 
2671 FormatStyle::LanguageKind guessLanguage(StringRef FileName, StringRef Code) {
2672   const auto GuessedLanguage = getLanguageByFileName(FileName);
2673   if (GuessedLanguage == FormatStyle::LK_Cpp) {
2674     auto Extension = llvm::sys::path::extension(FileName);
2675     // If there's no file extension (or it's .h), we need to check the contents
2676     // of the code to see if it contains Objective-C.
2677     if (Extension.empty() || Extension == ".h") {
2678       auto NonEmptyFileName = FileName.empty() ? "guess.h" : FileName;
2679       Environment Env(Code, NonEmptyFileName, /*Ranges=*/{});
2680       ObjCHeaderStyleGuesser Guesser(Env, getLLVMStyle());
2681       Guesser.process();
2682       if (Guesser.isObjC())
2683         return FormatStyle::LK_ObjC;
2684     }
2685   }
2686   return GuessedLanguage;
2687 }
2688 
2689 const char *DefaultFormatStyle = "file";
2690 
2691 const char *DefaultFallbackStyle = "LLVM";
2692 
2693 llvm::Expected<FormatStyle> getStyle(StringRef StyleName, StringRef FileName,
2694                                      StringRef FallbackStyleName,
2695                                      StringRef Code,
2696                                      llvm::vfs::FileSystem *FS) {
2697   if (!FS) {
2698     FS = llvm::vfs::getRealFileSystem().get();
2699   }
2700   FormatStyle Style = getLLVMStyle(guessLanguage(FileName, Code));
2701 
2702   FormatStyle FallbackStyle = getNoStyle();
2703   if (!getPredefinedStyle(FallbackStyleName, Style.Language, &FallbackStyle))
2704     return make_string_error("Invalid fallback style \"" + FallbackStyleName);
2705 
2706   if (StyleName.startswith("{")) {
2707     // Parse YAML/JSON style from the command line.
2708     if (std::error_code ec = parseConfiguration(StyleName, &Style))
2709       return make_string_error("Error parsing -style: " + ec.message());
2710     return Style;
2711   }
2712 
2713   if (!StyleName.equals_lower("file")) {
2714     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
2715       return make_string_error("Invalid value for -style");
2716     return Style;
2717   }
2718 
2719   // Look for .clang-format/_clang-format file in the file's parent directories.
2720   SmallString<128> UnsuitableConfigFiles;
2721   SmallString<128> Path(FileName);
2722   if (std::error_code EC = FS->makeAbsolute(Path))
2723     return make_string_error(EC.message());
2724 
2725   llvm::SmallVector<std::string, 2> FilesToLookFor;
2726   FilesToLookFor.push_back(".clang-format");
2727   FilesToLookFor.push_back("_clang-format");
2728 
2729   for (StringRef Directory = Path; !Directory.empty();
2730        Directory = llvm::sys::path::parent_path(Directory)) {
2731 
2732     auto Status = FS->status(Directory);
2733     if (!Status ||
2734         Status->getType() != llvm::sys::fs::file_type::directory_file) {
2735       continue;
2736     }
2737 
2738     for (const auto &F : FilesToLookFor) {
2739       SmallString<128> ConfigFile(Directory);
2740 
2741       llvm::sys::path::append(ConfigFile, F);
2742       LLVM_DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2743 
2744       Status = FS->status(ConfigFile.str());
2745 
2746       if (Status &&
2747           (Status->getType() == llvm::sys::fs::file_type::regular_file)) {
2748         llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
2749             FS->getBufferForFile(ConfigFile.str());
2750         if (std::error_code EC = Text.getError())
2751           return make_string_error(EC.message());
2752         if (std::error_code ec =
2753                 parseConfiguration(Text.get()->getBuffer(), &Style)) {
2754           if (ec == ParseError::Unsuitable) {
2755             if (!UnsuitableConfigFiles.empty())
2756               UnsuitableConfigFiles.append(", ");
2757             UnsuitableConfigFiles.append(ConfigFile);
2758             continue;
2759           }
2760           return make_string_error("Error reading " + ConfigFile + ": " +
2761                                    ec.message());
2762         }
2763         LLVM_DEBUG(llvm::dbgs()
2764                    << "Using configuration file " << ConfigFile << "\n");
2765         return Style;
2766       }
2767     }
2768   }
2769   if (!UnsuitableConfigFiles.empty())
2770     return make_string_error("Configuration file(s) do(es) not support " +
2771                              getLanguageName(Style.Language) + ": " +
2772                              UnsuitableConfigFiles);
2773   return FallbackStyle;
2774 }
2775 
2776 } // namespace format
2777 } // namespace clang
2778