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