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