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