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