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