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