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