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