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