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