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