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