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