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