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