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