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