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