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