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