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