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