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