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