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