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