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