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