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