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