1 //===--- Format.cpp - Format C++ code -------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief This file implements functions declared in Format.h. This will be
12 /// split into separate files as we go.
13 ///
14 //===----------------------------------------------------------------------===//
15 
16 #include "clang/Format/Format.h"
17 #include "AffectedRangeManager.h"
18 #include "ContinuationIndenter.h"
19 #include "FormatTokenLexer.h"
20 #include "SortJavaScriptImports.h"
21 #include "TokenAnalyzer.h"
22 #include "TokenAnnotator.h"
23 #include "UnwrappedLineFormatter.h"
24 #include "UnwrappedLineParser.h"
25 #include "WhitespaceManager.h"
26 #include "clang/Basic/Diagnostic.h"
27 #include "clang/Basic/DiagnosticOptions.h"
28 #include "clang/Basic/SourceManager.h"
29 #include "clang/Basic/VirtualFileSystem.h"
30 #include "clang/Lex/Lexer.h"
31 #include "llvm/ADT/STLExtras.h"
32 #include "llvm/Support/Allocator.h"
33 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/Path.h"
35 #include "llvm/Support/Regex.h"
36 #include "llvm/Support/YAMLTraits.h"
37 #include <algorithm>
38 #include <memory>
39 #include <string>
40 
41 #define DEBUG_TYPE "format-formatter"
42 
43 using clang::format::FormatStyle;
44 
45 LLVM_YAML_IS_FLOW_SEQUENCE_VECTOR(std::string)
46 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::format::FormatStyle::IncludeCategory)
47 
48 namespace llvm {
49 namespace yaml {
50 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
51   static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
52     IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
53     IO.enumCase(Value, "Java", FormatStyle::LK_Java);
54     IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
55     IO.enumCase(Value, "Proto", FormatStyle::LK_Proto);
56     IO.enumCase(Value, "TableGen", FormatStyle::LK_TableGen);
57   }
58 };
59 
60 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
61   static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
62     IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03);
63     IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03);
64     IO.enumCase(Value, "Cpp11", FormatStyle::LS_Cpp11);
65     IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11);
66     IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
67   }
68 };
69 
70 template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
71   static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
72     IO.enumCase(Value, "Never", FormatStyle::UT_Never);
73     IO.enumCase(Value, "false", FormatStyle::UT_Never);
74     IO.enumCase(Value, "Always", FormatStyle::UT_Always);
75     IO.enumCase(Value, "true", FormatStyle::UT_Always);
76     IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
77     IO.enumCase(Value, "ForContinuationAndIndentation",
78                 FormatStyle::UT_ForContinuationAndIndentation);
79   }
80 };
81 
82 template <> struct ScalarEnumerationTraits<FormatStyle::JavaScriptQuoteStyle> {
83   static void enumeration(IO &IO, FormatStyle::JavaScriptQuoteStyle &Value) {
84     IO.enumCase(Value, "Leave", FormatStyle::JSQS_Leave);
85     IO.enumCase(Value, "Single", FormatStyle::JSQS_Single);
86     IO.enumCase(Value, "Double", FormatStyle::JSQS_Double);
87   }
88 };
89 
90 template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
91   static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
92     IO.enumCase(Value, "None", FormatStyle::SFS_None);
93     IO.enumCase(Value, "false", FormatStyle::SFS_None);
94     IO.enumCase(Value, "All", FormatStyle::SFS_All);
95     IO.enumCase(Value, "true", FormatStyle::SFS_All);
96     IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
97     IO.enumCase(Value, "Empty", FormatStyle::SFS_Empty);
98   }
99 };
100 
101 template <> struct ScalarEnumerationTraits<FormatStyle::BinaryOperatorStyle> {
102   static void enumeration(IO &IO, FormatStyle::BinaryOperatorStyle &Value) {
103     IO.enumCase(Value, "All", FormatStyle::BOS_All);
104     IO.enumCase(Value, "true", FormatStyle::BOS_All);
105     IO.enumCase(Value, "None", FormatStyle::BOS_None);
106     IO.enumCase(Value, "false", FormatStyle::BOS_None);
107     IO.enumCase(Value, "NonAssignment", FormatStyle::BOS_NonAssignment);
108   }
109 };
110 
111 template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
112   static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
113     IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
114     IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
115     IO.enumCase(Value, "Mozilla", FormatStyle::BS_Mozilla);
116     IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
117     IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
118     IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
119     IO.enumCase(Value, "WebKit", FormatStyle::BS_WebKit);
120     IO.enumCase(Value, "Custom", FormatStyle::BS_Custom);
121   }
122 };
123 
124 template <>
125 struct ScalarEnumerationTraits<FormatStyle::ReturnTypeBreakingStyle> {
126   static void enumeration(IO &IO, FormatStyle::ReturnTypeBreakingStyle &Value) {
127     IO.enumCase(Value, "None", FormatStyle::RTBS_None);
128     IO.enumCase(Value, "All", FormatStyle::RTBS_All);
129     IO.enumCase(Value, "TopLevel", FormatStyle::RTBS_TopLevel);
130     IO.enumCase(Value, "TopLevelDefinitions",
131                 FormatStyle::RTBS_TopLevelDefinitions);
132     IO.enumCase(Value, "AllDefinitions", FormatStyle::RTBS_AllDefinitions);
133   }
134 };
135 
136 template <>
137 struct ScalarEnumerationTraits<FormatStyle::DefinitionReturnTypeBreakingStyle> {
138   static void
139   enumeration(IO &IO, FormatStyle::DefinitionReturnTypeBreakingStyle &Value) {
140     IO.enumCase(Value, "None", FormatStyle::DRTBS_None);
141     IO.enumCase(Value, "All", FormatStyle::DRTBS_All);
142     IO.enumCase(Value, "TopLevel", FormatStyle::DRTBS_TopLevel);
143 
144     // For backward compatibility.
145     IO.enumCase(Value, "false", FormatStyle::DRTBS_None);
146     IO.enumCase(Value, "true", FormatStyle::DRTBS_All);
147   }
148 };
149 
150 template <>
151 struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
152   static void enumeration(IO &IO,
153                           FormatStyle::NamespaceIndentationKind &Value) {
154     IO.enumCase(Value, "None", FormatStyle::NI_None);
155     IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
156     IO.enumCase(Value, "All", FormatStyle::NI_All);
157   }
158 };
159 
160 template <> struct ScalarEnumerationTraits<FormatStyle::BracketAlignmentStyle> {
161   static void enumeration(IO &IO, FormatStyle::BracketAlignmentStyle &Value) {
162     IO.enumCase(Value, "Align", FormatStyle::BAS_Align);
163     IO.enumCase(Value, "DontAlign", FormatStyle::BAS_DontAlign);
164     IO.enumCase(Value, "AlwaysBreak", FormatStyle::BAS_AlwaysBreak);
165 
166     // For backward compatibility.
167     IO.enumCase(Value, "true", FormatStyle::BAS_Align);
168     IO.enumCase(Value, "false", FormatStyle::BAS_DontAlign);
169   }
170 };
171 
172 template <> struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
173   static void enumeration(IO &IO, FormatStyle::PointerAlignmentStyle &Value) {
174     IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
175     IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
176     IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
177 
178     // For backward compatibility.
179     IO.enumCase(Value, "true", FormatStyle::PAS_Left);
180     IO.enumCase(Value, "false", FormatStyle::PAS_Right);
181   }
182 };
183 
184 template <>
185 struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
186   static void enumeration(IO &IO,
187                           FormatStyle::SpaceBeforeParensOptions &Value) {
188     IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
189     IO.enumCase(Value, "ControlStatements",
190                 FormatStyle::SBPO_ControlStatements);
191     IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
192 
193     // For backward compatibility.
194     IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
195     IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
196   }
197 };
198 
199 template <> struct MappingTraits<FormatStyle> {
200   static void mapping(IO &IO, FormatStyle &Style) {
201     // When reading, read the language first, we need it for getPredefinedStyle.
202     IO.mapOptional("Language", Style.Language);
203 
204     if (IO.outputting()) {
205       StringRef StylesArray[] = {"LLVM",    "Google", "Chromium",
206                                  "Mozilla", "WebKit", "GNU"};
207       ArrayRef<StringRef> Styles(StylesArray);
208       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
209         StringRef StyleName(Styles[i]);
210         FormatStyle PredefinedStyle;
211         if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
212             Style == PredefinedStyle) {
213           IO.mapOptional("# BasedOnStyle", StyleName);
214           break;
215         }
216       }
217     } else {
218       StringRef BasedOnStyle;
219       IO.mapOptional("BasedOnStyle", BasedOnStyle);
220       if (!BasedOnStyle.empty()) {
221         FormatStyle::LanguageKind OldLanguage = Style.Language;
222         FormatStyle::LanguageKind Language =
223             ((FormatStyle *)IO.getContext())->Language;
224         if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
225           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
226           return;
227         }
228         Style.Language = OldLanguage;
229       }
230     }
231 
232     // For backward compatibility.
233     if (!IO.outputting()) {
234       IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
235       IO.mapOptional("IndentFunctionDeclarationAfterType",
236                      Style.IndentWrappedFunctionNames);
237       IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
238       IO.mapOptional("SpaceAfterControlStatementKeyword",
239                      Style.SpaceBeforeParens);
240     }
241 
242     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
243     IO.mapOptional("AlignAfterOpenBracket", Style.AlignAfterOpenBracket);
244     IO.mapOptional("AlignConsecutiveAssignments",
245                    Style.AlignConsecutiveAssignments);
246     IO.mapOptional("AlignConsecutiveDeclarations",
247                    Style.AlignConsecutiveDeclarations);
248     IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
249     IO.mapOptional("AlignOperands", Style.AlignOperands);
250     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
251     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
252                    Style.AllowAllParametersOfDeclarationOnNextLine);
253     IO.mapOptional("AllowShortBlocksOnASingleLine",
254                    Style.AllowShortBlocksOnASingleLine);
255     IO.mapOptional("AllowShortCaseLabelsOnASingleLine",
256                    Style.AllowShortCaseLabelsOnASingleLine);
257     IO.mapOptional("AllowShortFunctionsOnASingleLine",
258                    Style.AllowShortFunctionsOnASingleLine);
259     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
260                    Style.AllowShortIfStatementsOnASingleLine);
261     IO.mapOptional("AllowShortLoopsOnASingleLine",
262                    Style.AllowShortLoopsOnASingleLine);
263     IO.mapOptional("AlwaysBreakAfterDefinitionReturnType",
264                    Style.AlwaysBreakAfterDefinitionReturnType);
265     IO.mapOptional("AlwaysBreakAfterReturnType",
266                    Style.AlwaysBreakAfterReturnType);
267     // If AlwaysBreakAfterDefinitionReturnType was specified but
268     // AlwaysBreakAfterReturnType was not, initialize the latter from the
269     // former for backwards compatibility.
270     if (Style.AlwaysBreakAfterDefinitionReturnType != FormatStyle::DRTBS_None &&
271         Style.AlwaysBreakAfterReturnType == FormatStyle::RTBS_None) {
272       if (Style.AlwaysBreakAfterDefinitionReturnType == FormatStyle::DRTBS_All)
273         Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
274       else if (Style.AlwaysBreakAfterDefinitionReturnType ==
275                FormatStyle::DRTBS_TopLevel)
276         Style.AlwaysBreakAfterReturnType =
277             FormatStyle::RTBS_TopLevelDefinitions;
278     }
279 
280     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
281                    Style.AlwaysBreakBeforeMultilineStrings);
282     IO.mapOptional("AlwaysBreakTemplateDeclarations",
283                    Style.AlwaysBreakTemplateDeclarations);
284     IO.mapOptional("BinPackArguments", Style.BinPackArguments);
285     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
286     IO.mapOptional("BraceWrapping", Style.BraceWrapping);
287     IO.mapOptional("BreakBeforeBinaryOperators",
288                    Style.BreakBeforeBinaryOperators);
289     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
290     IO.mapOptional("BreakBeforeTernaryOperators",
291                    Style.BreakBeforeTernaryOperators);
292     IO.mapOptional("BreakConstructorInitializersBeforeComma",
293                    Style.BreakConstructorInitializersBeforeComma);
294     IO.mapOptional("BreakAfterJavaFieldAnnotations",
295                    Style.BreakAfterJavaFieldAnnotations);
296     IO.mapOptional("BreakStringLiterals", Style.BreakStringLiterals);
297     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
298     IO.mapOptional("CommentPragmas", Style.CommentPragmas);
299     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
300                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
301     IO.mapOptional("ConstructorInitializerIndentWidth",
302                    Style.ConstructorInitializerIndentWidth);
303     IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
304     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
305     IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
306     IO.mapOptional("DisableFormat", Style.DisableFormat);
307     IO.mapOptional("ExperimentalAutoDetectBinPacking",
308                    Style.ExperimentalAutoDetectBinPacking);
309     IO.mapOptional("ForEachMacros", Style.ForEachMacros);
310     IO.mapOptional("IncludeCategories", Style.IncludeCategories);
311     IO.mapOptional("IncludeIsMainRegex", Style.IncludeIsMainRegex);
312     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
313     IO.mapOptional("IndentWidth", Style.IndentWidth);
314     IO.mapOptional("IndentWrappedFunctionNames",
315                    Style.IndentWrappedFunctionNames);
316     IO.mapOptional("JavaScriptQuotes", Style.JavaScriptQuotes);
317     IO.mapOptional("JavaScriptWrapImports", Style.JavaScriptWrapImports);
318     IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
319                    Style.KeepEmptyLinesAtTheStartOfBlocks);
320     IO.mapOptional("MacroBlockBegin", Style.MacroBlockBegin);
321     IO.mapOptional("MacroBlockEnd", Style.MacroBlockEnd);
322     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
323     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
324     IO.mapOptional("ObjCBlockIndentWidth", Style.ObjCBlockIndentWidth);
325     IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
326     IO.mapOptional("ObjCSpaceBeforeProtocolList",
327                    Style.ObjCSpaceBeforeProtocolList);
328     IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
329                    Style.PenaltyBreakBeforeFirstCallParameter);
330     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
331     IO.mapOptional("PenaltyBreakFirstLessLess",
332                    Style.PenaltyBreakFirstLessLess);
333     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
334     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
335     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
336                    Style.PenaltyReturnTypeOnItsOwnLine);
337     IO.mapOptional("PointerAlignment", Style.PointerAlignment);
338     IO.mapOptional("ReflowComments", Style.ReflowComments);
339     IO.mapOptional("SortIncludes", Style.SortIncludes);
340     IO.mapOptional("SpaceAfterCStyleCast", Style.SpaceAfterCStyleCast);
341     IO.mapOptional("SpaceBeforeAssignmentOperators",
342                    Style.SpaceBeforeAssignmentOperators);
343     IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
344     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
345     IO.mapOptional("SpacesBeforeTrailingComments",
346                    Style.SpacesBeforeTrailingComments);
347     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
348     IO.mapOptional("SpacesInContainerLiterals",
349                    Style.SpacesInContainerLiterals);
350     IO.mapOptional("SpacesInCStyleCastParentheses",
351                    Style.SpacesInCStyleCastParentheses);
352     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
353     IO.mapOptional("SpacesInSquareBrackets", Style.SpacesInSquareBrackets);
354     IO.mapOptional("Standard", Style.Standard);
355     IO.mapOptional("TabWidth", Style.TabWidth);
356     IO.mapOptional("UseTab", Style.UseTab);
357   }
358 };
359 
360 template <> struct MappingTraits<FormatStyle::BraceWrappingFlags> {
361   static void mapping(IO &IO, FormatStyle::BraceWrappingFlags &Wrapping) {
362     IO.mapOptional("AfterClass", Wrapping.AfterClass);
363     IO.mapOptional("AfterControlStatement", Wrapping.AfterControlStatement);
364     IO.mapOptional("AfterEnum", Wrapping.AfterEnum);
365     IO.mapOptional("AfterFunction", Wrapping.AfterFunction);
366     IO.mapOptional("AfterNamespace", Wrapping.AfterNamespace);
367     IO.mapOptional("AfterObjCDeclaration", Wrapping.AfterObjCDeclaration);
368     IO.mapOptional("AfterStruct", Wrapping.AfterStruct);
369     IO.mapOptional("AfterUnion", Wrapping.AfterUnion);
370     IO.mapOptional("BeforeCatch", Wrapping.BeforeCatch);
371     IO.mapOptional("BeforeElse", Wrapping.BeforeElse);
372     IO.mapOptional("IndentBraces", Wrapping.IndentBraces);
373   }
374 };
375 
376 template <> struct MappingTraits<FormatStyle::IncludeCategory> {
377   static void mapping(IO &IO, FormatStyle::IncludeCategory &Category) {
378     IO.mapOptional("Regex", Category.Regex);
379     IO.mapOptional("Priority", Category.Priority);
380   }
381 };
382 
383 // Allows to read vector<FormatStyle> while keeping default values.
384 // IO.getContext() should contain a pointer to the FormatStyle structure, that
385 // will be used to get default values for missing keys.
386 // If the first element has no Language specified, it will be treated as the
387 // default one for the following elements.
388 template <> struct DocumentListTraits<std::vector<FormatStyle>> {
389   static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
390     return Seq.size();
391   }
392   static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
393                               size_t Index) {
394     if (Index >= Seq.size()) {
395       assert(Index == Seq.size());
396       FormatStyle Template;
397       if (Seq.size() > 0 && Seq[0].Language == FormatStyle::LK_None) {
398         Template = Seq[0];
399       } else {
400         Template = *((const FormatStyle *)IO.getContext());
401         Template.Language = FormatStyle::LK_None;
402       }
403       Seq.resize(Index + 1, Template);
404     }
405     return Seq[Index];
406   }
407 };
408 } // namespace yaml
409 } // namespace llvm
410 
411 namespace clang {
412 namespace format {
413 
414 const std::error_category &getParseCategory() {
415   static ParseErrorCategory C;
416   return C;
417 }
418 std::error_code make_error_code(ParseError e) {
419   return std::error_code(static_cast<int>(e), getParseCategory());
420 }
421 
422 const char *ParseErrorCategory::name() const LLVM_NOEXCEPT {
423   return "clang-format.parse_error";
424 }
425 
426 std::string ParseErrorCategory::message(int EV) const {
427   switch (static_cast<ParseError>(EV)) {
428   case ParseError::Success:
429     return "Success";
430   case ParseError::Error:
431     return "Invalid argument";
432   case ParseError::Unsuitable:
433     return "Unsuitable";
434   }
435   llvm_unreachable("unexpected parse error");
436 }
437 
438 static FormatStyle expandPresets(const FormatStyle &Style) {
439   if (Style.BreakBeforeBraces == FormatStyle::BS_Custom)
440     return Style;
441   FormatStyle Expanded = Style;
442   Expanded.BraceWrapping = {false, false, false, false, false, false,
443                             false, false, false, false, false};
444   switch (Style.BreakBeforeBraces) {
445   case FormatStyle::BS_Linux:
446     Expanded.BraceWrapping.AfterClass = true;
447     Expanded.BraceWrapping.AfterFunction = true;
448     Expanded.BraceWrapping.AfterNamespace = true;
449     break;
450   case FormatStyle::BS_Mozilla:
451     Expanded.BraceWrapping.AfterClass = true;
452     Expanded.BraceWrapping.AfterEnum = true;
453     Expanded.BraceWrapping.AfterFunction = true;
454     Expanded.BraceWrapping.AfterStruct = true;
455     Expanded.BraceWrapping.AfterUnion = true;
456     break;
457   case FormatStyle::BS_Stroustrup:
458     Expanded.BraceWrapping.AfterFunction = true;
459     Expanded.BraceWrapping.BeforeCatch = true;
460     Expanded.BraceWrapping.BeforeElse = true;
461     break;
462   case FormatStyle::BS_Allman:
463     Expanded.BraceWrapping.AfterClass = true;
464     Expanded.BraceWrapping.AfterControlStatement = true;
465     Expanded.BraceWrapping.AfterEnum = true;
466     Expanded.BraceWrapping.AfterFunction = true;
467     Expanded.BraceWrapping.AfterNamespace = true;
468     Expanded.BraceWrapping.AfterObjCDeclaration = true;
469     Expanded.BraceWrapping.AfterStruct = true;
470     Expanded.BraceWrapping.BeforeCatch = true;
471     Expanded.BraceWrapping.BeforeElse = true;
472     break;
473   case FormatStyle::BS_GNU:
474     Expanded.BraceWrapping = {true, true, true, true, true, true,
475                               true, true, true, true, true};
476     break;
477   case FormatStyle::BS_WebKit:
478     Expanded.BraceWrapping.AfterFunction = true;
479     break;
480   default:
481     break;
482   }
483   return Expanded;
484 }
485 
486 FormatStyle getLLVMStyle() {
487   FormatStyle LLVMStyle;
488   LLVMStyle.Language = FormatStyle::LK_Cpp;
489   LLVMStyle.AccessModifierOffset = -2;
490   LLVMStyle.AlignEscapedNewlinesLeft = false;
491   LLVMStyle.AlignAfterOpenBracket = FormatStyle::BAS_Align;
492   LLVMStyle.AlignOperands = true;
493   LLVMStyle.AlignTrailingComments = true;
494   LLVMStyle.AlignConsecutiveAssignments = false;
495   LLVMStyle.AlignConsecutiveDeclarations = false;
496   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
497   LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
498   LLVMStyle.AllowShortBlocksOnASingleLine = false;
499   LLVMStyle.AllowShortCaseLabelsOnASingleLine = false;
500   LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
501   LLVMStyle.AllowShortLoopsOnASingleLine = false;
502   LLVMStyle.AlwaysBreakAfterReturnType = FormatStyle::RTBS_None;
503   LLVMStyle.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_None;
504   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
505   LLVMStyle.AlwaysBreakTemplateDeclarations = false;
506   LLVMStyle.BinPackParameters = true;
507   LLVMStyle.BinPackArguments = true;
508   LLVMStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_None;
509   LLVMStyle.BreakBeforeTernaryOperators = true;
510   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
511   LLVMStyle.BraceWrapping = {false, false, false, false, false, false,
512                              false, false, false, false, false};
513   LLVMStyle.BreakAfterJavaFieldAnnotations = false;
514   LLVMStyle.BreakConstructorInitializersBeforeComma = false;
515   LLVMStyle.BreakStringLiterals = true;
516   LLVMStyle.ColumnLimit = 80;
517   LLVMStyle.CommentPragmas = "^ IWYU pragma:";
518   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
519   LLVMStyle.ConstructorInitializerIndentWidth = 4;
520   LLVMStyle.ContinuationIndentWidth = 4;
521   LLVMStyle.Cpp11BracedListStyle = true;
522   LLVMStyle.DerivePointerAlignment = false;
523   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
524   LLVMStyle.ForEachMacros.push_back("foreach");
525   LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
526   LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
527   LLVMStyle.IncludeCategories = {{"^\"(llvm|llvm-c|clang|clang-c)/", 2},
528                                  {"^(<|\"(gtest|isl|json)/)", 3},
529                                  {".*", 1}};
530   LLVMStyle.IncludeIsMainRegex = "$";
531   LLVMStyle.IndentCaseLabels = false;
532   LLVMStyle.IndentWrappedFunctionNames = false;
533   LLVMStyle.IndentWidth = 2;
534   LLVMStyle.JavaScriptQuotes = FormatStyle::JSQS_Leave;
535   LLVMStyle.JavaScriptWrapImports = true;
536   LLVMStyle.TabWidth = 8;
537   LLVMStyle.MaxEmptyLinesToKeep = 1;
538   LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
539   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
540   LLVMStyle.ObjCBlockIndentWidth = 2;
541   LLVMStyle.ObjCSpaceAfterProperty = false;
542   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
543   LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
544   LLVMStyle.SpacesBeforeTrailingComments = 1;
545   LLVMStyle.Standard = FormatStyle::LS_Cpp11;
546   LLVMStyle.UseTab = FormatStyle::UT_Never;
547   LLVMStyle.JavaScriptQuotes = FormatStyle::JSQS_Leave;
548   LLVMStyle.ReflowComments = true;
549   LLVMStyle.SpacesInParentheses = false;
550   LLVMStyle.SpacesInSquareBrackets = false;
551   LLVMStyle.SpaceInEmptyParentheses = false;
552   LLVMStyle.SpacesInContainerLiterals = true;
553   LLVMStyle.SpacesInCStyleCastParentheses = false;
554   LLVMStyle.SpaceAfterCStyleCast = false;
555   LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
556   LLVMStyle.SpaceBeforeAssignmentOperators = true;
557   LLVMStyle.SpacesInAngles = false;
558 
559   LLVMStyle.PenaltyBreakComment = 300;
560   LLVMStyle.PenaltyBreakFirstLessLess = 120;
561   LLVMStyle.PenaltyBreakString = 1000;
562   LLVMStyle.PenaltyExcessCharacter = 1000000;
563   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
564   LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
565 
566   LLVMStyle.DisableFormat = false;
567   LLVMStyle.SortIncludes = true;
568 
569   return LLVMStyle;
570 }
571 
572 FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
573   FormatStyle GoogleStyle = getLLVMStyle();
574   GoogleStyle.Language = Language;
575 
576   GoogleStyle.AccessModifierOffset = -1;
577   GoogleStyle.AlignEscapedNewlinesLeft = true;
578   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
579   GoogleStyle.AllowShortLoopsOnASingleLine = true;
580   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
581   GoogleStyle.AlwaysBreakTemplateDeclarations = true;
582   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
583   GoogleStyle.DerivePointerAlignment = true;
584   GoogleStyle.IncludeCategories = {{"^<.*\\.h>", 1}, {"^<.*", 2}, {".*", 3}};
585   GoogleStyle.IncludeIsMainRegex = "([-_](test|unittest))?$";
586   GoogleStyle.IndentCaseLabels = true;
587   GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
588   GoogleStyle.ObjCSpaceAfterProperty = false;
589   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
590   GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
591   GoogleStyle.SpacesBeforeTrailingComments = 2;
592   GoogleStyle.Standard = FormatStyle::LS_Auto;
593 
594   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
595   GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
596 
597   if (Language == FormatStyle::LK_Java) {
598     GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
599     GoogleStyle.AlignOperands = false;
600     GoogleStyle.AlignTrailingComments = false;
601     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
602     GoogleStyle.AllowShortIfStatementsOnASingleLine = false;
603     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
604     GoogleStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_NonAssignment;
605     GoogleStyle.ColumnLimit = 100;
606     GoogleStyle.SpaceAfterCStyleCast = true;
607     GoogleStyle.SpacesBeforeTrailingComments = 1;
608   } else if (Language == FormatStyle::LK_JavaScript) {
609     GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_AlwaysBreak;
610     GoogleStyle.AlignOperands = false;
611     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
612     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
613     GoogleStyle.BreakBeforeTernaryOperators = false;
614     GoogleStyle.CommentPragmas = "@(export|requirecss|return|see|visibility) ";
615     GoogleStyle.MaxEmptyLinesToKeep = 3;
616     GoogleStyle.NamespaceIndentation = FormatStyle::NI_All;
617     GoogleStyle.SpacesInContainerLiterals = false;
618     GoogleStyle.JavaScriptQuotes = FormatStyle::JSQS_Single;
619     GoogleStyle.JavaScriptWrapImports = false;
620   } else if (Language == FormatStyle::LK_Proto) {
621     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
622     GoogleStyle.SpacesInContainerLiterals = false;
623   }
624 
625   return GoogleStyle;
626 }
627 
628 FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
629   FormatStyle ChromiumStyle = getGoogleStyle(Language);
630   if (Language == FormatStyle::LK_Java) {
631     ChromiumStyle.AllowShortIfStatementsOnASingleLine = true;
632     ChromiumStyle.BreakAfterJavaFieldAnnotations = true;
633     ChromiumStyle.ContinuationIndentWidth = 8;
634     ChromiumStyle.IndentWidth = 4;
635   } else {
636     ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
637     ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
638     ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
639     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
640     ChromiumStyle.BinPackParameters = false;
641     ChromiumStyle.DerivePointerAlignment = false;
642   }
643   ChromiumStyle.SortIncludes = false;
644   return ChromiumStyle;
645 }
646 
647 FormatStyle getMozillaStyle() {
648   FormatStyle MozillaStyle = getLLVMStyle();
649   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
650   MozillaStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
651   MozillaStyle.AlwaysBreakAfterReturnType =
652       FormatStyle::RTBS_TopLevelDefinitions;
653   MozillaStyle.AlwaysBreakAfterDefinitionReturnType =
654       FormatStyle::DRTBS_TopLevel;
655   MozillaStyle.AlwaysBreakTemplateDeclarations = true;
656   MozillaStyle.BreakBeforeBraces = FormatStyle::BS_Mozilla;
657   MozillaStyle.BreakConstructorInitializersBeforeComma = true;
658   MozillaStyle.ConstructorInitializerIndentWidth = 2;
659   MozillaStyle.ContinuationIndentWidth = 2;
660   MozillaStyle.Cpp11BracedListStyle = false;
661   MozillaStyle.IndentCaseLabels = true;
662   MozillaStyle.ObjCSpaceAfterProperty = true;
663   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
664   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
665   MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
666   return MozillaStyle;
667 }
668 
669 FormatStyle getWebKitStyle() {
670   FormatStyle Style = getLLVMStyle();
671   Style.AccessModifierOffset = -4;
672   Style.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
673   Style.AlignOperands = false;
674   Style.AlignTrailingComments = false;
675   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
676   Style.BreakBeforeBraces = FormatStyle::BS_WebKit;
677   Style.BreakConstructorInitializersBeforeComma = true;
678   Style.Cpp11BracedListStyle = false;
679   Style.ColumnLimit = 0;
680   Style.IndentWidth = 4;
681   Style.NamespaceIndentation = FormatStyle::NI_Inner;
682   Style.ObjCBlockIndentWidth = 4;
683   Style.ObjCSpaceAfterProperty = true;
684   Style.PointerAlignment = FormatStyle::PAS_Left;
685   Style.Standard = FormatStyle::LS_Cpp03;
686   return Style;
687 }
688 
689 FormatStyle getGNUStyle() {
690   FormatStyle Style = getLLVMStyle();
691   Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_All;
692   Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
693   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
694   Style.BreakBeforeBraces = FormatStyle::BS_GNU;
695   Style.BreakBeforeTernaryOperators = true;
696   Style.Cpp11BracedListStyle = false;
697   Style.ColumnLimit = 79;
698   Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
699   Style.Standard = FormatStyle::LS_Cpp03;
700   return Style;
701 }
702 
703 FormatStyle getNoStyle() {
704   FormatStyle NoStyle = getLLVMStyle();
705   NoStyle.DisableFormat = true;
706   NoStyle.SortIncludes = false;
707   return NoStyle;
708 }
709 
710 bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
711                         FormatStyle *Style) {
712   if (Name.equals_lower("llvm")) {
713     *Style = getLLVMStyle();
714   } else if (Name.equals_lower("chromium")) {
715     *Style = getChromiumStyle(Language);
716   } else if (Name.equals_lower("mozilla")) {
717     *Style = getMozillaStyle();
718   } else if (Name.equals_lower("google")) {
719     *Style = getGoogleStyle(Language);
720   } else if (Name.equals_lower("webkit")) {
721     *Style = getWebKitStyle();
722   } else if (Name.equals_lower("gnu")) {
723     *Style = getGNUStyle();
724   } else if (Name.equals_lower("none")) {
725     *Style = getNoStyle();
726   } else {
727     return false;
728   }
729 
730   Style->Language = Language;
731   return true;
732 }
733 
734 std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
735   assert(Style);
736   FormatStyle::LanguageKind Language = Style->Language;
737   assert(Language != FormatStyle::LK_None);
738   if (Text.trim().empty())
739     return make_error_code(ParseError::Error);
740 
741   std::vector<FormatStyle> Styles;
742   llvm::yaml::Input Input(Text);
743   // DocumentListTraits<vector<FormatStyle>> uses the context to get default
744   // values for the fields, keys for which are missing from the configuration.
745   // Mapping also uses the context to get the language to find the correct
746   // base style.
747   Input.setContext(Style);
748   Input >> Styles;
749   if (Input.error())
750     return Input.error();
751 
752   for (unsigned i = 0; i < Styles.size(); ++i) {
753     // Ensures that only the first configuration can skip the Language option.
754     if (Styles[i].Language == FormatStyle::LK_None && i != 0)
755       return make_error_code(ParseError::Error);
756     // Ensure that each language is configured at most once.
757     for (unsigned j = 0; j < i; ++j) {
758       if (Styles[i].Language == Styles[j].Language) {
759         DEBUG(llvm::dbgs()
760               << "Duplicate languages in the config file on positions " << j
761               << " and " << i << "\n");
762         return make_error_code(ParseError::Error);
763       }
764     }
765   }
766   // Look for a suitable configuration starting from the end, so we can
767   // find the configuration for the specific language first, and the default
768   // configuration (which can only be at slot 0) after it.
769   for (int i = Styles.size() - 1; i >= 0; --i) {
770     if (Styles[i].Language == Language ||
771         Styles[i].Language == FormatStyle::LK_None) {
772       *Style = Styles[i];
773       Style->Language = Language;
774       return make_error_code(ParseError::Success);
775     }
776   }
777   return make_error_code(ParseError::Unsuitable);
778 }
779 
780 std::string configurationAsText(const FormatStyle &Style) {
781   std::string Text;
782   llvm::raw_string_ostream Stream(Text);
783   llvm::yaml::Output Output(Stream);
784   // We use the same mapping method for input and output, so we need a non-const
785   // reference here.
786   FormatStyle NonConstStyle = expandPresets(Style);
787   Output << NonConstStyle;
788   return Stream.str();
789 }
790 
791 namespace {
792 
793 class Formatter : public TokenAnalyzer {
794 public:
795   Formatter(const Environment &Env, const FormatStyle &Style,
796             bool *IncompleteFormat)
797       : TokenAnalyzer(Env, Style), IncompleteFormat(IncompleteFormat) {}
798 
799   tooling::Replacements
800   analyze(TokenAnnotator &Annotator,
801           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
802           FormatTokenLexer &Tokens, tooling::Replacements &Result) override {
803     deriveLocalStyle(AnnotatedLines);
804     AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
805                                           AnnotatedLines.end());
806 
807     if (Style.Language == FormatStyle::LK_JavaScript &&
808         Style.JavaScriptQuotes != FormatStyle::JSQS_Leave)
809       requoteJSStringLiteral(AnnotatedLines, Result);
810 
811     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
812       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
813     }
814 
815     Annotator.setCommentLineLevels(AnnotatedLines);
816 
817     WhitespaceManager Whitespaces(
818         Env.getSourceManager(), Style,
819         inputUsesCRLF(Env.getSourceManager().getBufferData(Env.getFileID())));
820     ContinuationIndenter Indenter(Style, Tokens.getKeywords(),
821                                   Env.getSourceManager(), Whitespaces, Encoding,
822                                   BinPackInconclusiveFunctions);
823     UnwrappedLineFormatter(&Indenter, &Whitespaces, Style, Tokens.getKeywords(),
824                            IncompleteFormat)
825         .format(AnnotatedLines);
826     return Whitespaces.generateReplacements();
827   }
828 
829 private:
830   // If the last token is a double/single-quoted string literal, generates a
831   // replacement with a single/double quoted string literal, re-escaping the
832   // contents in the process.
833   void requoteJSStringLiteral(SmallVectorImpl<AnnotatedLine *> &Lines,
834                               tooling::Replacements &Result) {
835     for (AnnotatedLine *Line : Lines) {
836       requoteJSStringLiteral(Line->Children, Result);
837       if (!Line->Affected)
838         continue;
839       for (FormatToken *FormatTok = Line->First; FormatTok;
840            FormatTok = FormatTok->Next) {
841         StringRef Input = FormatTok->TokenText;
842         if (FormatTok->Finalized || !FormatTok->isStringLiteral() ||
843             // NB: testing for not starting with a double quote to avoid
844             // breaking
845             // `template strings`.
846             (Style.JavaScriptQuotes == FormatStyle::JSQS_Single &&
847              !Input.startswith("\"")) ||
848             (Style.JavaScriptQuotes == FormatStyle::JSQS_Double &&
849              !Input.startswith("\'")))
850           continue;
851 
852         // Change start and end quote.
853         bool IsSingle = Style.JavaScriptQuotes == FormatStyle::JSQS_Single;
854         SourceLocation Start = FormatTok->Tok.getLocation();
855         auto Replace = [&](SourceLocation Start, unsigned Length,
856                            StringRef ReplacementText) {
857           Result.insert(tooling::Replacement(Env.getSourceManager(), Start,
858                                              Length, ReplacementText));
859         };
860         Replace(Start, 1, IsSingle ? "'" : "\"");
861         Replace(FormatTok->Tok.getEndLoc().getLocWithOffset(-1), 1,
862                 IsSingle ? "'" : "\"");
863 
864         // Escape internal quotes.
865         size_t ColumnWidth = FormatTok->TokenText.size();
866         bool Escaped = false;
867         for (size_t i = 1; i < Input.size() - 1; i++) {
868           switch (Input[i]) {
869           case '\\':
870             if (!Escaped && i + 1 < Input.size() &&
871                 ((IsSingle && Input[i + 1] == '"') ||
872                  (!IsSingle && Input[i + 1] == '\''))) {
873               // Remove this \, it's escaping a " or ' that no longer needs
874               // escaping
875               ColumnWidth--;
876               Replace(Start.getLocWithOffset(i), 1, "");
877               continue;
878             }
879             Escaped = !Escaped;
880             break;
881           case '\"':
882           case '\'':
883             if (!Escaped && IsSingle == (Input[i] == '\'')) {
884               // Escape the quote.
885               Replace(Start.getLocWithOffset(i), 0, "\\");
886               ColumnWidth++;
887             }
888             Escaped = false;
889             break;
890           default:
891             Escaped = false;
892             break;
893           }
894         }
895 
896         // For formatting, count the number of non-escaped single quotes in them
897         // and adjust ColumnWidth to take the added escapes into account.
898         // FIXME(martinprobst): this might conflict with code breaking a long
899         // string literal (which clang-format doesn't do, yet). For that to
900         // work, this code would have to modify TokenText directly.
901         FormatTok->ColumnWidth = ColumnWidth;
902       }
903     }
904   }
905 
906   static bool inputUsesCRLF(StringRef Text) {
907     return Text.count('\r') * 2 > Text.count('\n');
908   }
909 
910   bool
911   hasCpp03IncompatibleFormat(const SmallVectorImpl<AnnotatedLine *> &Lines) {
912     for (const AnnotatedLine *Line : Lines) {
913       if (hasCpp03IncompatibleFormat(Line->Children))
914         return true;
915       for (FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next) {
916         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
917           if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
918             return true;
919           if (Tok->is(TT_TemplateCloser) &&
920               Tok->Previous->is(TT_TemplateCloser))
921             return true;
922         }
923       }
924     }
925     return false;
926   }
927 
928   int countVariableAlignments(const SmallVectorImpl<AnnotatedLine *> &Lines) {
929     int AlignmentDiff = 0;
930     for (const AnnotatedLine *Line : Lines) {
931       AlignmentDiff += countVariableAlignments(Line->Children);
932       for (FormatToken *Tok = Line->First; Tok && Tok->Next; Tok = Tok->Next) {
933         if (!Tok->is(TT_PointerOrReference))
934           continue;
935         bool SpaceBefore =
936             Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
937         bool SpaceAfter = Tok->Next->WhitespaceRange.getBegin() !=
938                           Tok->Next->WhitespaceRange.getEnd();
939         if (SpaceBefore && !SpaceAfter)
940           ++AlignmentDiff;
941         if (!SpaceBefore && SpaceAfter)
942           --AlignmentDiff;
943       }
944     }
945     return AlignmentDiff;
946   }
947 
948   void
949   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
950     bool HasBinPackedFunction = false;
951     bool HasOnePerLineFunction = false;
952     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
953       if (!AnnotatedLines[i]->First->Next)
954         continue;
955       FormatToken *Tok = AnnotatedLines[i]->First->Next;
956       while (Tok->Next) {
957         if (Tok->PackingKind == PPK_BinPacked)
958           HasBinPackedFunction = true;
959         if (Tok->PackingKind == PPK_OnePerLine)
960           HasOnePerLineFunction = true;
961 
962         Tok = Tok->Next;
963       }
964     }
965     if (Style.DerivePointerAlignment)
966       Style.PointerAlignment = countVariableAlignments(AnnotatedLines) <= 0
967                                    ? FormatStyle::PAS_Left
968                                    : FormatStyle::PAS_Right;
969     if (Style.Standard == FormatStyle::LS_Auto)
970       Style.Standard = hasCpp03IncompatibleFormat(AnnotatedLines)
971                            ? FormatStyle::LS_Cpp11
972                            : FormatStyle::LS_Cpp03;
973     BinPackInconclusiveFunctions =
974         HasBinPackedFunction || !HasOnePerLineFunction;
975   }
976 
977   bool BinPackInconclusiveFunctions;
978   bool *IncompleteFormat;
979 };
980 
981 // This class clean up the erroneous/redundant code around the given ranges in
982 // file.
983 class Cleaner : public TokenAnalyzer {
984 public:
985   Cleaner(const Environment &Env, const FormatStyle &Style)
986       : TokenAnalyzer(Env, Style),
987         DeletedTokens(FormatTokenLess(Env.getSourceManager())) {}
988 
989   // FIXME: eliminate unused parameters.
990   tooling::Replacements
991   analyze(TokenAnnotator &Annotator,
992           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
993           FormatTokenLexer &Tokens, tooling::Replacements &Result) override {
994     // FIXME: in the current implementation the granularity of affected range
995     // is an annotated line. However, this is not sufficient. Furthermore,
996     // redundant code introduced by replacements does not necessarily
997     // intercept with ranges of replacements that result in the redundancy.
998     // To determine if some redundant code is actually introduced by
999     // replacements(e.g. deletions), we need to come up with a more
1000     // sophisticated way of computing affected ranges.
1001     AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
1002                                           AnnotatedLines.end());
1003 
1004     checkEmptyNamespace(AnnotatedLines);
1005 
1006     for (auto &Line : AnnotatedLines) {
1007       if (Line->Affected) {
1008         cleanupRight(Line->First, tok::comma, tok::comma);
1009         cleanupRight(Line->First, TT_CtorInitializerColon, tok::comma);
1010         cleanupLeft(Line->First, TT_CtorInitializerComma, tok::l_brace);
1011         cleanupLeft(Line->First, TT_CtorInitializerColon, tok::l_brace);
1012       }
1013     }
1014 
1015     return generateFixes();
1016   }
1017 
1018 private:
1019   bool containsOnlyComments(const AnnotatedLine &Line) {
1020     for (FormatToken *Tok = Line.First; Tok != nullptr; Tok = Tok->Next) {
1021       if (Tok->isNot(tok::comment))
1022         return false;
1023     }
1024     return true;
1025   }
1026 
1027   // Iterate through all lines and remove any empty (nested) namespaces.
1028   void checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1029     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1030       auto &Line = *AnnotatedLines[i];
1031       if (Line.startsWith(tok::kw_namespace) ||
1032           Line.startsWith(tok::kw_inline, tok::kw_namespace)) {
1033         checkEmptyNamespace(AnnotatedLines, i, i);
1034       }
1035     }
1036 
1037     for (auto Line : DeletedLines) {
1038       FormatToken *Tok = AnnotatedLines[Line]->First;
1039       while (Tok) {
1040         deleteToken(Tok);
1041         Tok = Tok->Next;
1042       }
1043     }
1044   }
1045 
1046   // The function checks if the namespace, which starts from \p CurrentLine, and
1047   // its nested namespaces are empty and delete them if they are empty. It also
1048   // sets \p NewLine to the last line checked.
1049   // Returns true if the current namespace is empty.
1050   bool checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1051                            unsigned CurrentLine, unsigned &NewLine) {
1052     unsigned InitLine = CurrentLine, End = AnnotatedLines.size();
1053     if (Style.BraceWrapping.AfterNamespace) {
1054       // If the left brace is in a new line, we should consume it first so that
1055       // it does not make the namespace non-empty.
1056       // FIXME: error handling if there is no left brace.
1057       if (!AnnotatedLines[++CurrentLine]->startsWith(tok::l_brace)) {
1058         NewLine = CurrentLine;
1059         return false;
1060       }
1061     } else if (!AnnotatedLines[CurrentLine]->endsWith(tok::l_brace)) {
1062       return false;
1063     }
1064     while (++CurrentLine < End) {
1065       if (AnnotatedLines[CurrentLine]->startsWith(tok::r_brace))
1066         break;
1067 
1068       if (AnnotatedLines[CurrentLine]->startsWith(tok::kw_namespace) ||
1069           AnnotatedLines[CurrentLine]->startsWith(tok::kw_inline,
1070                                                   tok::kw_namespace)) {
1071         if (!checkEmptyNamespace(AnnotatedLines, CurrentLine, NewLine))
1072           return false;
1073         CurrentLine = NewLine;
1074         continue;
1075       }
1076 
1077       if (containsOnlyComments(*AnnotatedLines[CurrentLine]))
1078         continue;
1079 
1080       // If there is anything other than comments or nested namespaces in the
1081       // current namespace, the namespace cannot be empty.
1082       NewLine = CurrentLine;
1083       return false;
1084     }
1085 
1086     NewLine = CurrentLine;
1087     if (CurrentLine >= End)
1088       return false;
1089 
1090     // Check if the empty namespace is actually affected by changed ranges.
1091     if (!AffectedRangeMgr.affectsCharSourceRange(CharSourceRange::getCharRange(
1092             AnnotatedLines[InitLine]->First->Tok.getLocation(),
1093             AnnotatedLines[CurrentLine]->Last->Tok.getEndLoc())))
1094       return false;
1095 
1096     for (unsigned i = InitLine; i <= CurrentLine; ++i) {
1097       DeletedLines.insert(i);
1098     }
1099 
1100     return true;
1101   }
1102 
1103   // Checks pairs {start, start->next},..., {end->previous, end} and deletes one
1104   // of the token in the pair if the left token has \p LK token kind and the
1105   // right token has \p RK token kind. If \p DeleteLeft is true, the left token
1106   // is deleted on match; otherwise, the right token is deleted.
1107   template <typename LeftKind, typename RightKind>
1108   void cleanupPair(FormatToken *Start, LeftKind LK, RightKind RK,
1109                    bool DeleteLeft) {
1110     auto NextNotDeleted = [this](const FormatToken &Tok) -> FormatToken * {
1111       for (auto *Res = Tok.Next; Res; Res = Res->Next)
1112         if (!Res->is(tok::comment) &&
1113             DeletedTokens.find(Res) == DeletedTokens.end())
1114           return Res;
1115       return nullptr;
1116     };
1117     for (auto *Left = Start; Left;) {
1118       auto *Right = NextNotDeleted(*Left);
1119       if (!Right)
1120         break;
1121       if (Left->is(LK) && Right->is(RK)) {
1122         deleteToken(DeleteLeft ? Left : Right);
1123         // If the right token is deleted, we should keep the left token
1124         // unchanged and pair it with the new right token.
1125         if (!DeleteLeft)
1126           continue;
1127       }
1128       Left = Right;
1129     }
1130   }
1131 
1132   template <typename LeftKind, typename RightKind>
1133   void cleanupLeft(FormatToken *Start, LeftKind LK, RightKind RK) {
1134     cleanupPair(Start, LK, RK, /*DeleteLeft=*/true);
1135   }
1136 
1137   template <typename LeftKind, typename RightKind>
1138   void cleanupRight(FormatToken *Start, LeftKind LK, RightKind RK) {
1139     cleanupPair(Start, LK, RK, /*DeleteLeft=*/false);
1140   }
1141 
1142   // Delete the given token.
1143   inline void deleteToken(FormatToken *Tok) {
1144     if (Tok)
1145       DeletedTokens.insert(Tok);
1146   }
1147 
1148   tooling::Replacements generateFixes() {
1149     tooling::Replacements Fixes;
1150     std::vector<FormatToken *> Tokens;
1151     std::copy(DeletedTokens.begin(), DeletedTokens.end(),
1152               std::back_inserter(Tokens));
1153 
1154     // Merge multiple continuous token deletions into one big deletion so that
1155     // the number of replacements can be reduced. This makes computing affected
1156     // ranges more efficient when we run reformat on the changed code.
1157     unsigned Idx = 0;
1158     while (Idx < Tokens.size()) {
1159       unsigned St = Idx, End = Idx;
1160       while ((End + 1) < Tokens.size() &&
1161              Tokens[End]->Next == Tokens[End + 1]) {
1162         End++;
1163       }
1164       auto SR = CharSourceRange::getCharRange(Tokens[St]->Tok.getLocation(),
1165                                               Tokens[End]->Tok.getEndLoc());
1166       Fixes.insert(tooling::Replacement(Env.getSourceManager(), SR, ""));
1167       Idx = End + 1;
1168     }
1169 
1170     return Fixes;
1171   }
1172 
1173   // Class for less-than inequality comparason for the set `RedundantTokens`.
1174   // We store tokens in the order they appear in the translation unit so that
1175   // we do not need to sort them in `generateFixes()`.
1176   struct FormatTokenLess {
1177     FormatTokenLess(const SourceManager &SM) : SM(SM) {}
1178 
1179     bool operator()(const FormatToken *LHS, const FormatToken *RHS) const {
1180       return SM.isBeforeInTranslationUnit(LHS->Tok.getLocation(),
1181                                           RHS->Tok.getLocation());
1182     }
1183     const SourceManager &SM;
1184   };
1185 
1186   // Tokens to be deleted.
1187   std::set<FormatToken *, FormatTokenLess> DeletedTokens;
1188   // The line numbers of lines to be deleted.
1189   std::set<unsigned> DeletedLines;
1190 };
1191 
1192 struct IncludeDirective {
1193   StringRef Filename;
1194   StringRef Text;
1195   unsigned Offset;
1196   int Category;
1197 };
1198 
1199 } // end anonymous namespace
1200 
1201 // Determines whether 'Ranges' intersects with ('Start', 'End').
1202 static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
1203                          unsigned End) {
1204   for (auto Range : Ranges) {
1205     if (Range.getOffset() < End &&
1206         Range.getOffset() + Range.getLength() > Start)
1207       return true;
1208   }
1209   return false;
1210 }
1211 
1212 // Sorts a block of includes given by 'Includes' alphabetically adding the
1213 // necessary replacement to 'Replaces'. 'Includes' must be in strict source
1214 // order.
1215 static void sortCppIncludes(const FormatStyle &Style,
1216                          const SmallVectorImpl<IncludeDirective> &Includes,
1217                          ArrayRef<tooling::Range> Ranges, StringRef FileName,
1218                          tooling::Replacements &Replaces, unsigned *Cursor) {
1219   if (!affectsRange(Ranges, Includes.front().Offset,
1220                     Includes.back().Offset + Includes.back().Text.size()))
1221     return;
1222   SmallVector<unsigned, 16> Indices;
1223   for (unsigned i = 0, e = Includes.size(); i != e; ++i)
1224     Indices.push_back(i);
1225   std::stable_sort(
1226       Indices.begin(), Indices.end(), [&](unsigned LHSI, unsigned RHSI) {
1227         return std::tie(Includes[LHSI].Category, Includes[LHSI].Filename) <
1228                std::tie(Includes[RHSI].Category, Includes[RHSI].Filename);
1229       });
1230 
1231   // If the #includes are out of order, we generate a single replacement fixing
1232   // the entire block. Otherwise, no replacement is generated.
1233   if (std::is_sorted(Indices.begin(), Indices.end()))
1234     return;
1235 
1236   std::string result;
1237   bool CursorMoved = false;
1238   for (unsigned Index : Indices) {
1239     if (!result.empty())
1240       result += "\n";
1241     result += Includes[Index].Text;
1242 
1243     if (Cursor && !CursorMoved) {
1244       unsigned Start = Includes[Index].Offset;
1245       unsigned End = Start + Includes[Index].Text.size();
1246       if (*Cursor >= Start && *Cursor < End) {
1247         *Cursor = Includes.front().Offset + result.size() + *Cursor - End;
1248         CursorMoved = true;
1249       }
1250     }
1251   }
1252 
1253   // Sorting #includes shouldn't change their total number of characters.
1254   // This would otherwise mess up 'Ranges'.
1255   assert(result.size() ==
1256          Includes.back().Offset + Includes.back().Text.size() -
1257              Includes.front().Offset);
1258 
1259   Replaces.insert(tooling::Replacement(FileName, Includes.front().Offset,
1260                                        result.size(), result));
1261 }
1262 
1263 namespace {
1264 
1265 // This class manages priorities of #include categories and calculates
1266 // priorities for headers.
1267 class IncludeCategoryManager {
1268 public:
1269   IncludeCategoryManager(const FormatStyle &Style, StringRef FileName)
1270       : Style(Style), FileName(FileName) {
1271     FileStem = llvm::sys::path::stem(FileName);
1272     for (const auto &Category : Style.IncludeCategories)
1273       CategoryRegexs.emplace_back(Category.Regex);
1274     IsMainFile = FileName.endswith(".c") || FileName.endswith(".cc") ||
1275                  FileName.endswith(".cpp") || FileName.endswith(".c++") ||
1276                  FileName.endswith(".cxx") || FileName.endswith(".m") ||
1277                  FileName.endswith(".mm");
1278   }
1279 
1280   // Returns the priority of the category which \p IncludeName belongs to.
1281   // If \p CheckMainHeader is true and \p IncludeName is a main header, returns
1282   // 0. Otherwise, returns the priority of the matching category or INT_MAX.
1283   int getIncludePriority(StringRef IncludeName, bool CheckMainHeader) {
1284     int Ret = INT_MAX;
1285     for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i)
1286       if (CategoryRegexs[i].match(IncludeName)) {
1287         Ret = Style.IncludeCategories[i].Priority;
1288         break;
1289       }
1290     if (CheckMainHeader && IsMainFile && Ret > 0 && isMainHeader(IncludeName))
1291       Ret = 0;
1292     return Ret;
1293   }
1294 
1295 private:
1296   bool isMainHeader(StringRef IncludeName) const {
1297     if (!IncludeName.startswith("\""))
1298       return false;
1299     StringRef HeaderStem =
1300         llvm::sys::path::stem(IncludeName.drop_front(1).drop_back(1));
1301     if (FileStem.startswith(HeaderStem)) {
1302       llvm::Regex MainIncludeRegex(
1303           (HeaderStem + Style.IncludeIsMainRegex).str());
1304       if (MainIncludeRegex.match(FileStem))
1305         return true;
1306     }
1307     return false;
1308   }
1309 
1310   const FormatStyle &Style;
1311   bool IsMainFile;
1312   StringRef FileName;
1313   StringRef FileStem;
1314   SmallVector<llvm::Regex, 4> CategoryRegexs;
1315 };
1316 
1317 const char IncludeRegexPattern[] =
1318     R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
1319 
1320 } // anonymous namespace
1321 
1322 tooling::Replacements sortCppIncludes(const FormatStyle &Style, StringRef Code,
1323                                       ArrayRef<tooling::Range> Ranges,
1324                                       StringRef FileName,
1325                                       tooling::Replacements &Replaces,
1326                                       unsigned *Cursor) {
1327   unsigned Prev = 0;
1328   unsigned SearchFrom = 0;
1329   llvm::Regex IncludeRegex(IncludeRegexPattern);
1330   SmallVector<StringRef, 4> Matches;
1331   SmallVector<IncludeDirective, 16> IncludesInBlock;
1332 
1333   // In compiled files, consider the first #include to be the main #include of
1334   // the file if it is not a system #include. This ensures that the header
1335   // doesn't have hidden dependencies
1336   // (http://llvm.org/docs/CodingStandards.html#include-style).
1337   //
1338   // FIXME: Do some sanity checking, e.g. edit distance of the base name, to fix
1339   // cases where the first #include is unlikely to be the main header.
1340   IncludeCategoryManager Categories(Style, FileName);
1341   bool FirstIncludeBlock = true;
1342   bool MainIncludeFound = false;
1343   bool FormattingOff = false;
1344 
1345   for (;;) {
1346     auto Pos = Code.find('\n', SearchFrom);
1347     StringRef Line =
1348         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
1349 
1350     StringRef Trimmed = Line.trim();
1351     if (Trimmed == "// clang-format off")
1352       FormattingOff = true;
1353     else if (Trimmed == "// clang-format on")
1354       FormattingOff = false;
1355 
1356     if (!FormattingOff && !Line.endswith("\\")) {
1357       if (IncludeRegex.match(Line, &Matches)) {
1358         StringRef IncludeName = Matches[2];
1359         int Category = Categories.getIncludePriority(
1360             IncludeName,
1361             /*CheckMainHeader=*/!MainIncludeFound && FirstIncludeBlock);
1362         if (Category == 0)
1363           MainIncludeFound = true;
1364         IncludesInBlock.push_back({IncludeName, Line, Prev, Category});
1365       } else if (!IncludesInBlock.empty()) {
1366         sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces,
1367                         Cursor);
1368         IncludesInBlock.clear();
1369         FirstIncludeBlock = false;
1370       }
1371       Prev = Pos + 1;
1372     }
1373     if (Pos == StringRef::npos || Pos + 1 == Code.size())
1374       break;
1375     SearchFrom = Pos + 1;
1376   }
1377   if (!IncludesInBlock.empty())
1378     sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces, Cursor);
1379   return Replaces;
1380 }
1381 
1382 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
1383                                    ArrayRef<tooling::Range> Ranges,
1384                                    StringRef FileName, unsigned *Cursor) {
1385   tooling::Replacements Replaces;
1386   if (!Style.SortIncludes)
1387     return Replaces;
1388   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript)
1389     return sortJavaScriptImports(Style, Code, Ranges, FileName);
1390   sortCppIncludes(Style, Code, Ranges, FileName, Replaces, Cursor);
1391   return Replaces;
1392 }
1393 
1394 template <typename T>
1395 static llvm::Expected<tooling::Replacements>
1396 processReplacements(T ProcessFunc, StringRef Code,
1397                     const tooling::Replacements &Replaces,
1398                     const FormatStyle &Style) {
1399   if (Replaces.empty())
1400     return tooling::Replacements();
1401 
1402   auto NewCode = applyAllReplacements(Code, Replaces);
1403   if (!NewCode)
1404     return NewCode.takeError();
1405   std::vector<tooling::Range> ChangedRanges =
1406       tooling::calculateChangedRanges(Replaces);
1407   StringRef FileName = Replaces.begin()->getFilePath();
1408 
1409   tooling::Replacements FormatReplaces =
1410       ProcessFunc(Style, *NewCode, ChangedRanges, FileName);
1411 
1412   return mergeReplacements(Replaces, FormatReplaces);
1413 }
1414 
1415 llvm::Expected<tooling::Replacements>
1416 formatReplacements(StringRef Code, const tooling::Replacements &Replaces,
1417                    const FormatStyle &Style) {
1418   // We need to use lambda function here since there are two versions of
1419   // `sortIncludes`.
1420   auto SortIncludes = [](const FormatStyle &Style, StringRef Code,
1421                          std::vector<tooling::Range> Ranges,
1422                          StringRef FileName) -> tooling::Replacements {
1423     return sortIncludes(Style, Code, Ranges, FileName);
1424   };
1425   auto SortedReplaces =
1426       processReplacements(SortIncludes, Code, Replaces, Style);
1427   if (!SortedReplaces)
1428     return SortedReplaces.takeError();
1429 
1430   // We need to use lambda function here since there are two versions of
1431   // `reformat`.
1432   auto Reformat = [](const FormatStyle &Style, StringRef Code,
1433                      std::vector<tooling::Range> Ranges,
1434                      StringRef FileName) -> tooling::Replacements {
1435     return reformat(Style, Code, Ranges, FileName);
1436   };
1437   return processReplacements(Reformat, Code, *SortedReplaces, Style);
1438 }
1439 
1440 namespace {
1441 
1442 inline bool isHeaderInsertion(const tooling::Replacement &Replace) {
1443   return Replace.getOffset() == UINT_MAX &&
1444          llvm::Regex(IncludeRegexPattern).match(Replace.getReplacementText());
1445 }
1446 
1447 void skipComments(Lexer &Lex, Token &Tok) {
1448   while (Tok.is(tok::comment))
1449     if (Lex.LexFromRawLexer(Tok))
1450       return;
1451 }
1452 
1453 // Check if a sequence of tokens is like "#<Name> <raw_identifier>". If it is,
1454 // \p Tok will be the token after this directive; otherwise, it can be any token
1455 // after the given \p Tok (including \p Tok).
1456 bool checkAndConsumeDirectiveWithName(Lexer &Lex, StringRef Name, Token &Tok) {
1457   bool Matched = Tok.is(tok::hash) && !Lex.LexFromRawLexer(Tok) &&
1458                  Tok.is(tok::raw_identifier) &&
1459                  Tok.getRawIdentifier() == Name && !Lex.LexFromRawLexer(Tok) &&
1460                  Tok.is(tok::raw_identifier);
1461   if (Matched)
1462     Lex.LexFromRawLexer(Tok);
1463   return Matched;
1464 }
1465 
1466 unsigned getOffsetAfterHeaderGuardsAndComments(StringRef FileName,
1467                                                StringRef Code,
1468                                                const FormatStyle &Style) {
1469   std::unique_ptr<Environment> Env =
1470       Environment::CreateVirtualEnvironment(Code, FileName, /*Ranges=*/{});
1471   const SourceManager &SourceMgr = Env->getSourceManager();
1472   Lexer Lex(Env->getFileID(), SourceMgr.getBuffer(Env->getFileID()), SourceMgr,
1473             getFormattingLangOpts(Style));
1474   Token Tok;
1475   // Get the first token.
1476   Lex.LexFromRawLexer(Tok);
1477   skipComments(Lex, Tok);
1478   unsigned AfterComments = SourceMgr.getFileOffset(Tok.getLocation());
1479   if (checkAndConsumeDirectiveWithName(Lex, "ifndef", Tok)) {
1480     skipComments(Lex, Tok);
1481     if (checkAndConsumeDirectiveWithName(Lex, "define", Tok))
1482       return SourceMgr.getFileOffset(Tok.getLocation());
1483   }
1484   return AfterComments;
1485 }
1486 
1487 // FIXME: we also need to insert a '\n' at the end of the code if we have an
1488 // insertion with offset Code.size(), and there is no '\n' at the end of the
1489 // code.
1490 // FIXME: do not insert headers into conditional #include blocks, e.g. #includes
1491 // surrounded by compile condition "#if...".
1492 // FIXME: insert empty lines between newly created blocks.
1493 tooling::Replacements
1494 fixCppIncludeInsertions(StringRef Code, const tooling::Replacements &Replaces,
1495                         const FormatStyle &Style) {
1496   if (Style.Language != FormatStyle::LanguageKind::LK_Cpp)
1497     return Replaces;
1498 
1499   tooling::Replacements HeaderInsertions;
1500   for (const auto &R : Replaces) {
1501     if (isHeaderInsertion(R))
1502       HeaderInsertions.insert(R);
1503     else if (R.getOffset() == UINT_MAX)
1504       llvm::errs() << "Insertions other than header #include insertion are "
1505                       "not supported! "
1506                    << R.getReplacementText() << "\n";
1507   }
1508   if (HeaderInsertions.empty())
1509     return Replaces;
1510   tooling::Replacements Result;
1511   std::set_difference(Replaces.begin(), Replaces.end(),
1512                       HeaderInsertions.begin(), HeaderInsertions.end(),
1513                       std::inserter(Result, Result.begin()));
1514 
1515   llvm::Regex IncludeRegex(IncludeRegexPattern);
1516   llvm::Regex DefineRegex(R"(^[\t\ ]*#[\t\ ]*define[\t\ ]*[^\\]*$)");
1517   SmallVector<StringRef, 4> Matches;
1518 
1519   StringRef FileName = Replaces.begin()->getFilePath();
1520   IncludeCategoryManager Categories(Style, FileName);
1521 
1522   // Record the offset of the end of the last include in each category.
1523   std::map<int, int> CategoryEndOffsets;
1524   // All possible priorities.
1525   // Add 0 for main header and INT_MAX for headers that are not in any category.
1526   std::set<int> Priorities = {0, INT_MAX};
1527   for (const auto &Category : Style.IncludeCategories)
1528     Priorities.insert(Category.Priority);
1529   int FirstIncludeOffset = -1;
1530   // All new headers should be inserted after this offset.
1531   unsigned MinInsertOffset =
1532       getOffsetAfterHeaderGuardsAndComments(FileName, Code, Style);
1533   StringRef TrimmedCode = Code.drop_front(MinInsertOffset);
1534   SmallVector<StringRef, 32> Lines;
1535   TrimmedCode.split(Lines, '\n');
1536   unsigned Offset = MinInsertOffset;
1537   unsigned NextLineOffset;
1538   std::set<StringRef> ExistingIncludes;
1539   for (auto Line : Lines) {
1540     NextLineOffset = std::min(Code.size(), Offset + Line.size() + 1);
1541     if (IncludeRegex.match(Line, &Matches)) {
1542       StringRef IncludeName = Matches[2];
1543       ExistingIncludes.insert(IncludeName);
1544       int Category = Categories.getIncludePriority(
1545           IncludeName, /*CheckMainHeader=*/FirstIncludeOffset < 0);
1546       CategoryEndOffsets[Category] = NextLineOffset;
1547       if (FirstIncludeOffset < 0)
1548         FirstIncludeOffset = Offset;
1549     }
1550     Offset = NextLineOffset;
1551   }
1552 
1553   // Populate CategoryEndOfssets:
1554   // - Ensure that CategoryEndOffset[Highest] is always populated.
1555   // - If CategoryEndOffset[Priority] isn't set, use the next higher value that
1556   //   is set, up to CategoryEndOffset[Highest].
1557   auto Highest = Priorities.begin();
1558   if (CategoryEndOffsets.find(*Highest) == CategoryEndOffsets.end()) {
1559     if (FirstIncludeOffset >= 0)
1560       CategoryEndOffsets[*Highest] = FirstIncludeOffset;
1561     else
1562       CategoryEndOffsets[*Highest] = MinInsertOffset;
1563   }
1564   // By this point, CategoryEndOffset[Highest] is always set appropriately:
1565   //  - to an appropriate location before/after existing #includes, or
1566   //  - to right after the header guard, or
1567   //  - to the beginning of the file.
1568   for (auto I = ++Priorities.begin(), E = Priorities.end(); I != E; ++I)
1569     if (CategoryEndOffsets.find(*I) == CategoryEndOffsets.end())
1570       CategoryEndOffsets[*I] = CategoryEndOffsets[*std::prev(I)];
1571 
1572   for (const auto &R : HeaderInsertions) {
1573     auto IncludeDirective = R.getReplacementText();
1574     bool Matched = IncludeRegex.match(IncludeDirective, &Matches);
1575     assert(Matched && "Header insertion replacement must have replacement text "
1576                       "'#include ...'");
1577     (void)Matched;
1578     auto IncludeName = Matches[2];
1579     if (ExistingIncludes.find(IncludeName) != ExistingIncludes.end()) {
1580       DEBUG(llvm::dbgs() << "Skip adding existing include : " << IncludeName
1581                          << "\n");
1582       continue;
1583     }
1584     int Category =
1585         Categories.getIncludePriority(IncludeName, /*CheckMainHeader=*/true);
1586     Offset = CategoryEndOffsets[Category];
1587     std::string NewInclude = !IncludeDirective.endswith("\n")
1588                                  ? (IncludeDirective + "\n").str()
1589                                  : IncludeDirective.str();
1590     Result.insert(tooling::Replacement(FileName, Offset, 0, NewInclude));
1591   }
1592   return Result;
1593 }
1594 
1595 } // anonymous namespace
1596 
1597 llvm::Expected<tooling::Replacements>
1598 cleanupAroundReplacements(StringRef Code, const tooling::Replacements &Replaces,
1599                           const FormatStyle &Style) {
1600   // We need to use lambda function here since there are two versions of
1601   // `cleanup`.
1602   auto Cleanup = [](const FormatStyle &Style, StringRef Code,
1603                     std::vector<tooling::Range> Ranges,
1604                     StringRef FileName) -> tooling::Replacements {
1605     return cleanup(Style, Code, Ranges, FileName);
1606   };
1607   // Make header insertion replacements insert new headers into correct blocks.
1608   tooling::Replacements NewReplaces =
1609       fixCppIncludeInsertions(Code, Replaces, Style);
1610   return processReplacements(Cleanup, Code, NewReplaces, Style);
1611 }
1612 
1613 tooling::Replacements reformat(const FormatStyle &Style, SourceManager &SM,
1614                                FileID ID, ArrayRef<CharSourceRange> Ranges,
1615                                bool *IncompleteFormat) {
1616   FormatStyle Expanded = expandPresets(Style);
1617   if (Expanded.DisableFormat)
1618     return tooling::Replacements();
1619 
1620   Environment Env(SM, ID, Ranges);
1621   Formatter Format(Env, Expanded, IncompleteFormat);
1622   return Format.process();
1623 }
1624 
1625 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1626                                ArrayRef<tooling::Range> Ranges,
1627                                StringRef FileName, bool *IncompleteFormat) {
1628   FormatStyle Expanded = expandPresets(Style);
1629   if (Expanded.DisableFormat)
1630     return tooling::Replacements();
1631 
1632   std::unique_ptr<Environment> Env =
1633       Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
1634   Formatter Format(*Env, Expanded, IncompleteFormat);
1635   return Format.process();
1636 }
1637 
1638 tooling::Replacements cleanup(const FormatStyle &Style, SourceManager &SM,
1639                               FileID ID, ArrayRef<CharSourceRange> Ranges) {
1640   Environment Env(SM, ID, Ranges);
1641   Cleaner Clean(Env, Style);
1642   return Clean.process();
1643 }
1644 
1645 tooling::Replacements cleanup(const FormatStyle &Style, StringRef Code,
1646                               ArrayRef<tooling::Range> Ranges,
1647                               StringRef FileName) {
1648   std::unique_ptr<Environment> Env =
1649       Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
1650   Cleaner Clean(*Env, Style);
1651   return Clean.process();
1652 }
1653 
1654 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
1655   LangOptions LangOpts;
1656   LangOpts.CPlusPlus = 1;
1657   LangOpts.CPlusPlus11 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1658   LangOpts.CPlusPlus14 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1659   LangOpts.LineComment = 1;
1660   bool AlternativeOperators = Style.Language == FormatStyle::LK_Cpp;
1661   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
1662   LangOpts.Bool = 1;
1663   LangOpts.ObjC1 = 1;
1664   LangOpts.ObjC2 = 1;
1665   LangOpts.MicrosoftExt = 1;    // To get kw___try, kw___finally.
1666   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
1667   return LangOpts;
1668 }
1669 
1670 const char *StyleOptionHelpDescription =
1671     "Coding style, currently supports:\n"
1672     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
1673     "Use -style=file to load style configuration from\n"
1674     ".clang-format file located in one of the parent\n"
1675     "directories of the source file (or current\n"
1676     "directory for stdin).\n"
1677     "Use -style=\"{key: value, ...}\" to set specific\n"
1678     "parameters, e.g.:\n"
1679     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
1680 
1681 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
1682   if (FileName.endswith(".java"))
1683     return FormatStyle::LK_Java;
1684   if (FileName.endswith_lower(".js") || FileName.endswith_lower(".ts"))
1685     return FormatStyle::LK_JavaScript; // JavaScript or TypeScript.
1686   if (FileName.endswith_lower(".proto") ||
1687       FileName.endswith_lower(".protodevel"))
1688     return FormatStyle::LK_Proto;
1689   if (FileName.endswith_lower(".td"))
1690     return FormatStyle::LK_TableGen;
1691   return FormatStyle::LK_Cpp;
1692 }
1693 
1694 FormatStyle getStyle(StringRef StyleName, StringRef FileName,
1695                      StringRef FallbackStyle, vfs::FileSystem *FS) {
1696   if (!FS) {
1697     FS = vfs::getRealFileSystem().get();
1698   }
1699   FormatStyle Style = getLLVMStyle();
1700   Style.Language = getLanguageByFileName(FileName);
1701   if (!getPredefinedStyle(FallbackStyle, Style.Language, &Style)) {
1702     llvm::errs() << "Invalid fallback style \"" << FallbackStyle
1703                  << "\" using LLVM style\n";
1704     return Style;
1705   }
1706 
1707   if (StyleName.startswith("{")) {
1708     // Parse YAML/JSON style from the command line.
1709     if (std::error_code ec = parseConfiguration(StyleName, &Style)) {
1710       llvm::errs() << "Error parsing -style: " << ec.message() << ", using "
1711                    << FallbackStyle << " style\n";
1712     }
1713     return Style;
1714   }
1715 
1716   if (!StyleName.equals_lower("file")) {
1717     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
1718       llvm::errs() << "Invalid value for -style, using " << FallbackStyle
1719                    << " style\n";
1720     return Style;
1721   }
1722 
1723   // Look for .clang-format/_clang-format file in the file's parent directories.
1724   SmallString<128> UnsuitableConfigFiles;
1725   SmallString<128> Path(FileName);
1726   llvm::sys::fs::make_absolute(Path);
1727   for (StringRef Directory = Path; !Directory.empty();
1728        Directory = llvm::sys::path::parent_path(Directory)) {
1729 
1730     auto Status = FS->status(Directory);
1731     if (!Status ||
1732         Status->getType() != llvm::sys::fs::file_type::directory_file) {
1733       continue;
1734     }
1735 
1736     SmallString<128> ConfigFile(Directory);
1737 
1738     llvm::sys::path::append(ConfigFile, ".clang-format");
1739     DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1740 
1741     Status = FS->status(ConfigFile.str());
1742     bool IsFile =
1743         Status && (Status->getType() == llvm::sys::fs::file_type::regular_file);
1744     if (!IsFile) {
1745       // Try _clang-format too, since dotfiles are not commonly used on Windows.
1746       ConfigFile = Directory;
1747       llvm::sys::path::append(ConfigFile, "_clang-format");
1748       DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1749       Status = FS->status(ConfigFile.str());
1750       IsFile = Status &&
1751                (Status->getType() == llvm::sys::fs::file_type::regular_file);
1752     }
1753 
1754     if (IsFile) {
1755       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
1756           FS->getBufferForFile(ConfigFile.str());
1757       if (std::error_code EC = Text.getError()) {
1758         llvm::errs() << EC.message() << "\n";
1759         break;
1760       }
1761       if (std::error_code ec =
1762               parseConfiguration(Text.get()->getBuffer(), &Style)) {
1763         if (ec == ParseError::Unsuitable) {
1764           if (!UnsuitableConfigFiles.empty())
1765             UnsuitableConfigFiles.append(", ");
1766           UnsuitableConfigFiles.append(ConfigFile);
1767           continue;
1768         }
1769         llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message()
1770                      << "\n";
1771         break;
1772       }
1773       DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
1774       return Style;
1775     }
1776   }
1777   if (!UnsuitableConfigFiles.empty()) {
1778     llvm::errs() << "Configuration file(s) do(es) not support "
1779                  << getLanguageName(Style.Language) << ": "
1780                  << UnsuitableConfigFiles << "\n";
1781   }
1782   return Style;
1783 }
1784 
1785 } // namespace format
1786 } // namespace clang
1787