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