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