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           auto Err = Result.add(tooling::Replacement(
858               Env.getSourceManager(), Start, Length, ReplacementText));
859           // FIXME: handle error. For now, print error message and skip the
860           // replacement for release version.
861           if (Err)
862             llvm::errs() << llvm::toString(std::move(Err)) << "\n";
863           assert(!Err);
864         };
865         Replace(Start, 1, IsSingle ? "'" : "\"");
866         Replace(FormatTok->Tok.getEndLoc().getLocWithOffset(-1), 1,
867                 IsSingle ? "'" : "\"");
868 
869         // Escape internal quotes.
870         size_t ColumnWidth = FormatTok->TokenText.size();
871         bool Escaped = false;
872         for (size_t i = 1; i < Input.size() - 1; i++) {
873           switch (Input[i]) {
874           case '\\':
875             if (!Escaped && i + 1 < Input.size() &&
876                 ((IsSingle && Input[i + 1] == '"') ||
877                  (!IsSingle && Input[i + 1] == '\''))) {
878               // Remove this \, it's escaping a " or ' that no longer needs
879               // escaping
880               ColumnWidth--;
881               Replace(Start.getLocWithOffset(i), 1, "");
882               continue;
883             }
884             Escaped = !Escaped;
885             break;
886           case '\"':
887           case '\'':
888             if (!Escaped && IsSingle == (Input[i] == '\'')) {
889               // Escape the quote.
890               Replace(Start.getLocWithOffset(i), 0, "\\");
891               ColumnWidth++;
892             }
893             Escaped = false;
894             break;
895           default:
896             Escaped = false;
897             break;
898           }
899         }
900 
901         // For formatting, count the number of non-escaped single quotes in them
902         // and adjust ColumnWidth to take the added escapes into account.
903         // FIXME(martinprobst): this might conflict with code breaking a long
904         // string literal (which clang-format doesn't do, yet). For that to
905         // work, this code would have to modify TokenText directly.
906         FormatTok->ColumnWidth = ColumnWidth;
907       }
908     }
909   }
910 
911   static bool inputUsesCRLF(StringRef Text) {
912     return Text.count('\r') * 2 > Text.count('\n');
913   }
914 
915   bool
916   hasCpp03IncompatibleFormat(const SmallVectorImpl<AnnotatedLine *> &Lines) {
917     for (const AnnotatedLine *Line : Lines) {
918       if (hasCpp03IncompatibleFormat(Line->Children))
919         return true;
920       for (FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next) {
921         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
922           if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
923             return true;
924           if (Tok->is(TT_TemplateCloser) &&
925               Tok->Previous->is(TT_TemplateCloser))
926             return true;
927         }
928       }
929     }
930     return false;
931   }
932 
933   int countVariableAlignments(const SmallVectorImpl<AnnotatedLine *> &Lines) {
934     int AlignmentDiff = 0;
935     for (const AnnotatedLine *Line : Lines) {
936       AlignmentDiff += countVariableAlignments(Line->Children);
937       for (FormatToken *Tok = Line->First; Tok && Tok->Next; Tok = Tok->Next) {
938         if (!Tok->is(TT_PointerOrReference))
939           continue;
940         bool SpaceBefore =
941             Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
942         bool SpaceAfter = Tok->Next->WhitespaceRange.getBegin() !=
943                           Tok->Next->WhitespaceRange.getEnd();
944         if (SpaceBefore && !SpaceAfter)
945           ++AlignmentDiff;
946         if (!SpaceBefore && SpaceAfter)
947           --AlignmentDiff;
948       }
949     }
950     return AlignmentDiff;
951   }
952 
953   void
954   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
955     bool HasBinPackedFunction = false;
956     bool HasOnePerLineFunction = false;
957     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
958       if (!AnnotatedLines[i]->First->Next)
959         continue;
960       FormatToken *Tok = AnnotatedLines[i]->First->Next;
961       while (Tok->Next) {
962         if (Tok->PackingKind == PPK_BinPacked)
963           HasBinPackedFunction = true;
964         if (Tok->PackingKind == PPK_OnePerLine)
965           HasOnePerLineFunction = true;
966 
967         Tok = Tok->Next;
968       }
969     }
970     if (Style.DerivePointerAlignment)
971       Style.PointerAlignment = countVariableAlignments(AnnotatedLines) <= 0
972                                    ? FormatStyle::PAS_Left
973                                    : FormatStyle::PAS_Right;
974     if (Style.Standard == FormatStyle::LS_Auto)
975       Style.Standard = hasCpp03IncompatibleFormat(AnnotatedLines)
976                            ? FormatStyle::LS_Cpp11
977                            : FormatStyle::LS_Cpp03;
978     BinPackInconclusiveFunctions =
979         HasBinPackedFunction || !HasOnePerLineFunction;
980   }
981 
982   bool BinPackInconclusiveFunctions;
983   bool *IncompleteFormat;
984 };
985 
986 // This class clean up the erroneous/redundant code around the given ranges in
987 // file.
988 class Cleaner : public TokenAnalyzer {
989 public:
990   Cleaner(const Environment &Env, const FormatStyle &Style)
991       : TokenAnalyzer(Env, Style),
992         DeletedTokens(FormatTokenLess(Env.getSourceManager())) {}
993 
994   // FIXME: eliminate unused parameters.
995   tooling::Replacements
996   analyze(TokenAnnotator &Annotator,
997           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
998           FormatTokenLexer &Tokens, tooling::Replacements &Result) override {
999     // FIXME: in the current implementation the granularity of affected range
1000     // is an annotated line. However, this is not sufficient. Furthermore,
1001     // redundant code introduced by replacements does not necessarily
1002     // intercept with ranges of replacements that result in the redundancy.
1003     // To determine if some redundant code is actually introduced by
1004     // replacements(e.g. deletions), we need to come up with a more
1005     // sophisticated way of computing affected ranges.
1006     AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
1007                                           AnnotatedLines.end());
1008 
1009     checkEmptyNamespace(AnnotatedLines);
1010 
1011     for (auto &Line : AnnotatedLines) {
1012       if (Line->Affected) {
1013         cleanupRight(Line->First, tok::comma, tok::comma);
1014         cleanupRight(Line->First, TT_CtorInitializerColon, tok::comma);
1015         cleanupLeft(Line->First, TT_CtorInitializerComma, tok::l_brace);
1016         cleanupLeft(Line->First, TT_CtorInitializerColon, tok::l_brace);
1017       }
1018     }
1019 
1020     return generateFixes();
1021   }
1022 
1023 private:
1024   bool containsOnlyComments(const AnnotatedLine &Line) {
1025     for (FormatToken *Tok = Line.First; Tok != nullptr; Tok = Tok->Next) {
1026       if (Tok->isNot(tok::comment))
1027         return false;
1028     }
1029     return true;
1030   }
1031 
1032   // Iterate through all lines and remove any empty (nested) namespaces.
1033   void checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1034     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1035       auto &Line = *AnnotatedLines[i];
1036       if (Line.startsWith(tok::kw_namespace) ||
1037           Line.startsWith(tok::kw_inline, tok::kw_namespace)) {
1038         checkEmptyNamespace(AnnotatedLines, i, i);
1039       }
1040     }
1041 
1042     for (auto Line : DeletedLines) {
1043       FormatToken *Tok = AnnotatedLines[Line]->First;
1044       while (Tok) {
1045         deleteToken(Tok);
1046         Tok = Tok->Next;
1047       }
1048     }
1049   }
1050 
1051   // The function checks if the namespace, which starts from \p CurrentLine, and
1052   // its nested namespaces are empty and delete them if they are empty. It also
1053   // sets \p NewLine to the last line checked.
1054   // Returns true if the current namespace is empty.
1055   bool checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1056                            unsigned CurrentLine, unsigned &NewLine) {
1057     unsigned InitLine = CurrentLine, End = AnnotatedLines.size();
1058     if (Style.BraceWrapping.AfterNamespace) {
1059       // If the left brace is in a new line, we should consume it first so that
1060       // it does not make the namespace non-empty.
1061       // FIXME: error handling if there is no left brace.
1062       if (!AnnotatedLines[++CurrentLine]->startsWith(tok::l_brace)) {
1063         NewLine = CurrentLine;
1064         return false;
1065       }
1066     } else if (!AnnotatedLines[CurrentLine]->endsWith(tok::l_brace)) {
1067       return false;
1068     }
1069     while (++CurrentLine < End) {
1070       if (AnnotatedLines[CurrentLine]->startsWith(tok::r_brace))
1071         break;
1072 
1073       if (AnnotatedLines[CurrentLine]->startsWith(tok::kw_namespace) ||
1074           AnnotatedLines[CurrentLine]->startsWith(tok::kw_inline,
1075                                                   tok::kw_namespace)) {
1076         if (!checkEmptyNamespace(AnnotatedLines, CurrentLine, NewLine))
1077           return false;
1078         CurrentLine = NewLine;
1079         continue;
1080       }
1081 
1082       if (containsOnlyComments(*AnnotatedLines[CurrentLine]))
1083         continue;
1084 
1085       // If there is anything other than comments or nested namespaces in the
1086       // current namespace, the namespace cannot be empty.
1087       NewLine = CurrentLine;
1088       return false;
1089     }
1090 
1091     NewLine = CurrentLine;
1092     if (CurrentLine >= End)
1093       return false;
1094 
1095     // Check if the empty namespace is actually affected by changed ranges.
1096     if (!AffectedRangeMgr.affectsCharSourceRange(CharSourceRange::getCharRange(
1097             AnnotatedLines[InitLine]->First->Tok.getLocation(),
1098             AnnotatedLines[CurrentLine]->Last->Tok.getEndLoc())))
1099       return false;
1100 
1101     for (unsigned i = InitLine; i <= CurrentLine; ++i) {
1102       DeletedLines.insert(i);
1103     }
1104 
1105     return true;
1106   }
1107 
1108   // Checks pairs {start, start->next},..., {end->previous, end} and deletes one
1109   // of the token in the pair if the left token has \p LK token kind and the
1110   // right token has \p RK token kind. If \p DeleteLeft is true, the left token
1111   // is deleted on match; otherwise, the right token is deleted.
1112   template <typename LeftKind, typename RightKind>
1113   void cleanupPair(FormatToken *Start, LeftKind LK, RightKind RK,
1114                    bool DeleteLeft) {
1115     auto NextNotDeleted = [this](const FormatToken &Tok) -> FormatToken * {
1116       for (auto *Res = Tok.Next; Res; Res = Res->Next)
1117         if (!Res->is(tok::comment) &&
1118             DeletedTokens.find(Res) == DeletedTokens.end())
1119           return Res;
1120       return nullptr;
1121     };
1122     for (auto *Left = Start; Left;) {
1123       auto *Right = NextNotDeleted(*Left);
1124       if (!Right)
1125         break;
1126       if (Left->is(LK) && Right->is(RK)) {
1127         deleteToken(DeleteLeft ? Left : Right);
1128         // If the right token is deleted, we should keep the left token
1129         // unchanged and pair it with the new right token.
1130         if (!DeleteLeft)
1131           continue;
1132       }
1133       Left = Right;
1134     }
1135   }
1136 
1137   template <typename LeftKind, typename RightKind>
1138   void cleanupLeft(FormatToken *Start, LeftKind LK, RightKind RK) {
1139     cleanupPair(Start, LK, RK, /*DeleteLeft=*/true);
1140   }
1141 
1142   template <typename LeftKind, typename RightKind>
1143   void cleanupRight(FormatToken *Start, LeftKind LK, RightKind RK) {
1144     cleanupPair(Start, LK, RK, /*DeleteLeft=*/false);
1145   }
1146 
1147   // Delete the given token.
1148   inline void deleteToken(FormatToken *Tok) {
1149     if (Tok)
1150       DeletedTokens.insert(Tok);
1151   }
1152 
1153   tooling::Replacements generateFixes() {
1154     tooling::Replacements Fixes;
1155     std::vector<FormatToken *> Tokens;
1156     std::copy(DeletedTokens.begin(), DeletedTokens.end(),
1157               std::back_inserter(Tokens));
1158 
1159     // Merge multiple continuous token deletions into one big deletion so that
1160     // the number of replacements can be reduced. This makes computing affected
1161     // ranges more efficient when we run reformat on the changed code.
1162     unsigned Idx = 0;
1163     while (Idx < Tokens.size()) {
1164       unsigned St = Idx, End = Idx;
1165       while ((End + 1) < Tokens.size() &&
1166              Tokens[End]->Next == Tokens[End + 1]) {
1167         End++;
1168       }
1169       auto SR = CharSourceRange::getCharRange(Tokens[St]->Tok.getLocation(),
1170                                               Tokens[End]->Tok.getEndLoc());
1171       auto Err =
1172           Fixes.add(tooling::Replacement(Env.getSourceManager(), SR, ""));
1173       // FIXME: better error handling. for now just print error message and skip
1174       // for the release version.
1175       if (Err)
1176         llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1177       assert(!Err && "Fixes must not conflict!");
1178       Idx = End + 1;
1179     }
1180 
1181     return Fixes;
1182   }
1183 
1184   // Class for less-than inequality comparason for the set `RedundantTokens`.
1185   // We store tokens in the order they appear in the translation unit so that
1186   // we do not need to sort them in `generateFixes()`.
1187   struct FormatTokenLess {
1188     FormatTokenLess(const SourceManager &SM) : SM(SM) {}
1189 
1190     bool operator()(const FormatToken *LHS, const FormatToken *RHS) const {
1191       return SM.isBeforeInTranslationUnit(LHS->Tok.getLocation(),
1192                                           RHS->Tok.getLocation());
1193     }
1194     const SourceManager &SM;
1195   };
1196 
1197   // Tokens to be deleted.
1198   std::set<FormatToken *, FormatTokenLess> DeletedTokens;
1199   // The line numbers of lines to be deleted.
1200   std::set<unsigned> DeletedLines;
1201 };
1202 
1203 struct IncludeDirective {
1204   StringRef Filename;
1205   StringRef Text;
1206   unsigned Offset;
1207   int Category;
1208 };
1209 
1210 } // end anonymous namespace
1211 
1212 // Determines whether 'Ranges' intersects with ('Start', 'End').
1213 static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
1214                          unsigned End) {
1215   for (auto Range : Ranges) {
1216     if (Range.getOffset() < End &&
1217         Range.getOffset() + Range.getLength() > Start)
1218       return true;
1219   }
1220   return false;
1221 }
1222 
1223 // Sorts a block of includes given by 'Includes' alphabetically adding the
1224 // necessary replacement to 'Replaces'. 'Includes' must be in strict source
1225 // order.
1226 static void sortCppIncludes(const FormatStyle &Style,
1227                          const SmallVectorImpl<IncludeDirective> &Includes,
1228                          ArrayRef<tooling::Range> Ranges, StringRef FileName,
1229                          tooling::Replacements &Replaces, unsigned *Cursor) {
1230   if (!affectsRange(Ranges, Includes.front().Offset,
1231                     Includes.back().Offset + Includes.back().Text.size()))
1232     return;
1233   SmallVector<unsigned, 16> Indices;
1234   for (unsigned i = 0, e = Includes.size(); i != e; ++i)
1235     Indices.push_back(i);
1236   std::stable_sort(
1237       Indices.begin(), Indices.end(), [&](unsigned LHSI, unsigned RHSI) {
1238         return std::tie(Includes[LHSI].Category, Includes[LHSI].Filename) <
1239                std::tie(Includes[RHSI].Category, Includes[RHSI].Filename);
1240       });
1241 
1242   // If the #includes are out of order, we generate a single replacement fixing
1243   // the entire block. Otherwise, no replacement is generated.
1244   if (std::is_sorted(Indices.begin(), Indices.end()))
1245     return;
1246 
1247   std::string result;
1248   bool CursorMoved = false;
1249   for (unsigned Index : Indices) {
1250     if (!result.empty())
1251       result += "\n";
1252     result += Includes[Index].Text;
1253 
1254     if (Cursor && !CursorMoved) {
1255       unsigned Start = Includes[Index].Offset;
1256       unsigned End = Start + Includes[Index].Text.size();
1257       if (*Cursor >= Start && *Cursor < End) {
1258         *Cursor = Includes.front().Offset + result.size() + *Cursor - End;
1259         CursorMoved = true;
1260       }
1261     }
1262   }
1263 
1264   // Sorting #includes shouldn't change their total number of characters.
1265   // This would otherwise mess up 'Ranges'.
1266   assert(result.size() ==
1267          Includes.back().Offset + Includes.back().Text.size() -
1268              Includes.front().Offset);
1269 
1270   auto Err = Replaces.add(tooling::Replacement(
1271       FileName, Includes.front().Offset, result.size(), result));
1272   // FIXME: better error handling. For now, just skip the replacement for the
1273   // release version.
1274   if (Err)
1275     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1276   assert(!Err);
1277 }
1278 
1279 namespace {
1280 
1281 // This class manages priorities of #include categories and calculates
1282 // priorities for headers.
1283 class IncludeCategoryManager {
1284 public:
1285   IncludeCategoryManager(const FormatStyle &Style, StringRef FileName)
1286       : Style(Style), FileName(FileName) {
1287     FileStem = llvm::sys::path::stem(FileName);
1288     for (const auto &Category : Style.IncludeCategories)
1289       CategoryRegexs.emplace_back(Category.Regex);
1290     IsMainFile = FileName.endswith(".c") || FileName.endswith(".cc") ||
1291                  FileName.endswith(".cpp") || FileName.endswith(".c++") ||
1292                  FileName.endswith(".cxx") || FileName.endswith(".m") ||
1293                  FileName.endswith(".mm");
1294   }
1295 
1296   // Returns the priority of the category which \p IncludeName belongs to.
1297   // If \p CheckMainHeader is true and \p IncludeName is a main header, returns
1298   // 0. Otherwise, returns the priority of the matching category or INT_MAX.
1299   int getIncludePriority(StringRef IncludeName, bool CheckMainHeader) {
1300     int Ret = INT_MAX;
1301     for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i)
1302       if (CategoryRegexs[i].match(IncludeName)) {
1303         Ret = Style.IncludeCategories[i].Priority;
1304         break;
1305       }
1306     if (CheckMainHeader && IsMainFile && Ret > 0 && isMainHeader(IncludeName))
1307       Ret = 0;
1308     return Ret;
1309   }
1310 
1311 private:
1312   bool isMainHeader(StringRef IncludeName) const {
1313     if (!IncludeName.startswith("\""))
1314       return false;
1315     StringRef HeaderStem =
1316         llvm::sys::path::stem(IncludeName.drop_front(1).drop_back(1));
1317     if (FileStem.startswith(HeaderStem)) {
1318       llvm::Regex MainIncludeRegex(
1319           (HeaderStem + Style.IncludeIsMainRegex).str());
1320       if (MainIncludeRegex.match(FileStem))
1321         return true;
1322     }
1323     return false;
1324   }
1325 
1326   const FormatStyle &Style;
1327   bool IsMainFile;
1328   StringRef FileName;
1329   StringRef FileStem;
1330   SmallVector<llvm::Regex, 4> CategoryRegexs;
1331 };
1332 
1333 const char IncludeRegexPattern[] =
1334     R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
1335 
1336 } // anonymous namespace
1337 
1338 tooling::Replacements sortCppIncludes(const FormatStyle &Style, StringRef Code,
1339                                       ArrayRef<tooling::Range> Ranges,
1340                                       StringRef FileName,
1341                                       tooling::Replacements &Replaces,
1342                                       unsigned *Cursor) {
1343   unsigned Prev = 0;
1344   unsigned SearchFrom = 0;
1345   llvm::Regex IncludeRegex(IncludeRegexPattern);
1346   SmallVector<StringRef, 4> Matches;
1347   SmallVector<IncludeDirective, 16> IncludesInBlock;
1348 
1349   // In compiled files, consider the first #include to be the main #include of
1350   // the file if it is not a system #include. This ensures that the header
1351   // doesn't have hidden dependencies
1352   // (http://llvm.org/docs/CodingStandards.html#include-style).
1353   //
1354   // FIXME: Do some sanity checking, e.g. edit distance of the base name, to fix
1355   // cases where the first #include is unlikely to be the main header.
1356   IncludeCategoryManager Categories(Style, FileName);
1357   bool FirstIncludeBlock = true;
1358   bool MainIncludeFound = false;
1359   bool FormattingOff = false;
1360 
1361   for (;;) {
1362     auto Pos = Code.find('\n', SearchFrom);
1363     StringRef Line =
1364         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
1365 
1366     StringRef Trimmed = Line.trim();
1367     if (Trimmed == "// clang-format off")
1368       FormattingOff = true;
1369     else if (Trimmed == "// clang-format on")
1370       FormattingOff = false;
1371 
1372     if (!FormattingOff && !Line.endswith("\\")) {
1373       if (IncludeRegex.match(Line, &Matches)) {
1374         StringRef IncludeName = Matches[2];
1375         int Category = Categories.getIncludePriority(
1376             IncludeName,
1377             /*CheckMainHeader=*/!MainIncludeFound && FirstIncludeBlock);
1378         if (Category == 0)
1379           MainIncludeFound = true;
1380         IncludesInBlock.push_back({IncludeName, Line, Prev, Category});
1381       } else if (!IncludesInBlock.empty()) {
1382         sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces,
1383                         Cursor);
1384         IncludesInBlock.clear();
1385         FirstIncludeBlock = false;
1386       }
1387       Prev = Pos + 1;
1388     }
1389     if (Pos == StringRef::npos || Pos + 1 == Code.size())
1390       break;
1391     SearchFrom = Pos + 1;
1392   }
1393   if (!IncludesInBlock.empty())
1394     sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces, Cursor);
1395   return Replaces;
1396 }
1397 
1398 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
1399                                    ArrayRef<tooling::Range> Ranges,
1400                                    StringRef FileName, unsigned *Cursor) {
1401   tooling::Replacements Replaces;
1402   if (!Style.SortIncludes)
1403     return Replaces;
1404   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript)
1405     return sortJavaScriptImports(Style, Code, Ranges, FileName);
1406   sortCppIncludes(Style, Code, Ranges, FileName, Replaces, Cursor);
1407   return Replaces;
1408 }
1409 
1410 template <typename T>
1411 static llvm::Expected<tooling::Replacements>
1412 processReplacements(T ProcessFunc, StringRef Code,
1413                     const tooling::Replacements &Replaces,
1414                     const FormatStyle &Style) {
1415   if (Replaces.empty())
1416     return tooling::Replacements();
1417 
1418   auto NewCode = applyAllReplacements(Code, Replaces);
1419   if (!NewCode)
1420     return NewCode.takeError();
1421   std::vector<tooling::Range> ChangedRanges = Replaces.getAffectedRanges();
1422   StringRef FileName = Replaces.begin()->getFilePath();
1423 
1424   tooling::Replacements FormatReplaces =
1425       ProcessFunc(Style, *NewCode, ChangedRanges, FileName);
1426 
1427   return Replaces.merge(FormatReplaces);
1428 }
1429 
1430 llvm::Expected<tooling::Replacements>
1431 formatReplacements(StringRef Code, const tooling::Replacements &Replaces,
1432                    const FormatStyle &Style) {
1433   // We need to use lambda function here since there are two versions of
1434   // `sortIncludes`.
1435   auto SortIncludes = [](const FormatStyle &Style, StringRef Code,
1436                          std::vector<tooling::Range> Ranges,
1437                          StringRef FileName) -> tooling::Replacements {
1438     return sortIncludes(Style, Code, Ranges, FileName);
1439   };
1440   auto SortedReplaces =
1441       processReplacements(SortIncludes, Code, Replaces, Style);
1442   if (!SortedReplaces)
1443     return SortedReplaces.takeError();
1444 
1445   // We need to use lambda function here since there are two versions of
1446   // `reformat`.
1447   auto Reformat = [](const FormatStyle &Style, StringRef Code,
1448                      std::vector<tooling::Range> Ranges,
1449                      StringRef FileName) -> tooling::Replacements {
1450     return reformat(Style, Code, Ranges, FileName);
1451   };
1452   return processReplacements(Reformat, Code, *SortedReplaces, Style);
1453 }
1454 
1455 namespace {
1456 
1457 inline bool isHeaderInsertion(const tooling::Replacement &Replace) {
1458   return Replace.getOffset() == UINT_MAX &&
1459          llvm::Regex(IncludeRegexPattern).match(Replace.getReplacementText());
1460 }
1461 
1462 void skipComments(Lexer &Lex, Token &Tok) {
1463   while (Tok.is(tok::comment))
1464     if (Lex.LexFromRawLexer(Tok))
1465       return;
1466 }
1467 
1468 // Check if a sequence of tokens is like "#<Name> <raw_identifier>". If it is,
1469 // \p Tok will be the token after this directive; otherwise, it can be any token
1470 // after the given \p Tok (including \p Tok).
1471 bool checkAndConsumeDirectiveWithName(Lexer &Lex, StringRef Name, Token &Tok) {
1472   bool Matched = Tok.is(tok::hash) && !Lex.LexFromRawLexer(Tok) &&
1473                  Tok.is(tok::raw_identifier) &&
1474                  Tok.getRawIdentifier() == Name && !Lex.LexFromRawLexer(Tok) &&
1475                  Tok.is(tok::raw_identifier);
1476   if (Matched)
1477     Lex.LexFromRawLexer(Tok);
1478   return Matched;
1479 }
1480 
1481 unsigned getOffsetAfterHeaderGuardsAndComments(StringRef FileName,
1482                                                StringRef Code,
1483                                                const FormatStyle &Style) {
1484   std::unique_ptr<Environment> Env =
1485       Environment::CreateVirtualEnvironment(Code, FileName, /*Ranges=*/{});
1486   const SourceManager &SourceMgr = Env->getSourceManager();
1487   Lexer Lex(Env->getFileID(), SourceMgr.getBuffer(Env->getFileID()), SourceMgr,
1488             getFormattingLangOpts(Style));
1489   Token Tok;
1490   // Get the first token.
1491   Lex.LexFromRawLexer(Tok);
1492   skipComments(Lex, Tok);
1493   unsigned AfterComments = SourceMgr.getFileOffset(Tok.getLocation());
1494   if (checkAndConsumeDirectiveWithName(Lex, "ifndef", Tok)) {
1495     skipComments(Lex, Tok);
1496     if (checkAndConsumeDirectiveWithName(Lex, "define", Tok))
1497       return SourceMgr.getFileOffset(Tok.getLocation());
1498   }
1499   return AfterComments;
1500 }
1501 
1502 // FIXME: we also need to insert a '\n' at the end of the code if we have an
1503 // insertion with offset Code.size(), and there is no '\n' at the end of the
1504 // code.
1505 // FIXME: do not insert headers into conditional #include blocks, e.g. #includes
1506 // surrounded by compile condition "#if...".
1507 // FIXME: insert empty lines between newly created blocks.
1508 tooling::Replacements
1509 fixCppIncludeInsertions(StringRef Code, const tooling::Replacements &Replaces,
1510                         const FormatStyle &Style) {
1511   if (Style.Language != FormatStyle::LanguageKind::LK_Cpp)
1512     return Replaces;
1513 
1514   tooling::Replacements HeaderInsertions;
1515   tooling::Replacements Result;
1516   for (const auto &R : Replaces) {
1517     if (isHeaderInsertion(R)) {
1518       // Replacements from \p Replaces must be conflict-free already, so we can
1519       // simply consume the error.
1520       llvm::consumeError(HeaderInsertions.add(R));
1521     } else if (R.getOffset() == UINT_MAX) {
1522       llvm::errs() << "Insertions other than header #include insertion are "
1523                       "not supported! "
1524                    << R.getReplacementText() << "\n";
1525     } else {
1526       llvm::consumeError(Result.add(R));
1527     }
1528   }
1529   if (HeaderInsertions.empty())
1530     return Replaces;
1531 
1532   llvm::Regex IncludeRegex(IncludeRegexPattern);
1533   llvm::Regex DefineRegex(R"(^[\t\ ]*#[\t\ ]*define[\t\ ]*[^\\]*$)");
1534   SmallVector<StringRef, 4> Matches;
1535 
1536   StringRef FileName = Replaces.begin()->getFilePath();
1537   IncludeCategoryManager Categories(Style, FileName);
1538 
1539   // Record the offset of the end of the last include in each category.
1540   std::map<int, int> CategoryEndOffsets;
1541   // All possible priorities.
1542   // Add 0 for main header and INT_MAX for headers that are not in any category.
1543   std::set<int> Priorities = {0, INT_MAX};
1544   for (const auto &Category : Style.IncludeCategories)
1545     Priorities.insert(Category.Priority);
1546   int FirstIncludeOffset = -1;
1547   // All new headers should be inserted after this offset.
1548   unsigned MinInsertOffset =
1549       getOffsetAfterHeaderGuardsAndComments(FileName, Code, Style);
1550   StringRef TrimmedCode = Code.drop_front(MinInsertOffset);
1551   SmallVector<StringRef, 32> Lines;
1552   TrimmedCode.split(Lines, '\n');
1553   unsigned Offset = MinInsertOffset;
1554   unsigned NextLineOffset;
1555   std::set<StringRef> ExistingIncludes;
1556   for (auto Line : Lines) {
1557     NextLineOffset = std::min(Code.size(), Offset + Line.size() + 1);
1558     if (IncludeRegex.match(Line, &Matches)) {
1559       StringRef IncludeName = Matches[2];
1560       ExistingIncludes.insert(IncludeName);
1561       int Category = Categories.getIncludePriority(
1562           IncludeName, /*CheckMainHeader=*/FirstIncludeOffset < 0);
1563       CategoryEndOffsets[Category] = NextLineOffset;
1564       if (FirstIncludeOffset < 0)
1565         FirstIncludeOffset = Offset;
1566     }
1567     Offset = NextLineOffset;
1568   }
1569 
1570   // Populate CategoryEndOfssets:
1571   // - Ensure that CategoryEndOffset[Highest] is always populated.
1572   // - If CategoryEndOffset[Priority] isn't set, use the next higher value that
1573   //   is set, up to CategoryEndOffset[Highest].
1574   auto Highest = Priorities.begin();
1575   if (CategoryEndOffsets.find(*Highest) == CategoryEndOffsets.end()) {
1576     if (FirstIncludeOffset >= 0)
1577       CategoryEndOffsets[*Highest] = FirstIncludeOffset;
1578     else
1579       CategoryEndOffsets[*Highest] = MinInsertOffset;
1580   }
1581   // By this point, CategoryEndOffset[Highest] is always set appropriately:
1582   //  - to an appropriate location before/after existing #includes, or
1583   //  - to right after the header guard, or
1584   //  - to the beginning of the file.
1585   for (auto I = ++Priorities.begin(), E = Priorities.end(); I != E; ++I)
1586     if (CategoryEndOffsets.find(*I) == CategoryEndOffsets.end())
1587       CategoryEndOffsets[*I] = CategoryEndOffsets[*std::prev(I)];
1588 
1589   for (const auto &R : HeaderInsertions) {
1590     auto IncludeDirective = R.getReplacementText();
1591     bool Matched = IncludeRegex.match(IncludeDirective, &Matches);
1592     assert(Matched && "Header insertion replacement must have replacement text "
1593                       "'#include ...'");
1594     (void)Matched;
1595     auto IncludeName = Matches[2];
1596     if (ExistingIncludes.find(IncludeName) != ExistingIncludes.end()) {
1597       DEBUG(llvm::dbgs() << "Skip adding existing include : " << IncludeName
1598                          << "\n");
1599       continue;
1600     }
1601     int Category =
1602         Categories.getIncludePriority(IncludeName, /*CheckMainHeader=*/true);
1603     Offset = CategoryEndOffsets[Category];
1604     std::string NewInclude = !IncludeDirective.endswith("\n")
1605                                  ? (IncludeDirective + "\n").str()
1606                                  : IncludeDirective.str();
1607     auto NewReplace = tooling::Replacement(FileName, Offset, 0, NewInclude);
1608     auto Err = Result.add(NewReplace);
1609     if (Err) {
1610       llvm::consumeError(std::move(Err));
1611       Result = Result.merge(tooling::Replacements(NewReplace));
1612     }
1613   }
1614   return Result;
1615 }
1616 
1617 } // anonymous namespace
1618 
1619 llvm::Expected<tooling::Replacements>
1620 cleanupAroundReplacements(StringRef Code, const tooling::Replacements &Replaces,
1621                           const FormatStyle &Style) {
1622   // We need to use lambda function here since there are two versions of
1623   // `cleanup`.
1624   auto Cleanup = [](const FormatStyle &Style, StringRef Code,
1625                     std::vector<tooling::Range> Ranges,
1626                     StringRef FileName) -> tooling::Replacements {
1627     return cleanup(Style, Code, Ranges, FileName);
1628   };
1629   // Make header insertion replacements insert new headers into correct blocks.
1630   tooling::Replacements NewReplaces =
1631       fixCppIncludeInsertions(Code, Replaces, Style);
1632   return processReplacements(Cleanup, Code, NewReplaces, Style);
1633 }
1634 
1635 tooling::Replacements reformat(const FormatStyle &Style, SourceManager &SM,
1636                                FileID ID, ArrayRef<CharSourceRange> Ranges,
1637                                bool *IncompleteFormat) {
1638   FormatStyle Expanded = expandPresets(Style);
1639   if (Expanded.DisableFormat)
1640     return tooling::Replacements();
1641 
1642   Environment Env(SM, ID, Ranges);
1643   Formatter Format(Env, Expanded, IncompleteFormat);
1644   return Format.process();
1645 }
1646 
1647 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1648                                ArrayRef<tooling::Range> Ranges,
1649                                StringRef FileName, bool *IncompleteFormat) {
1650   FormatStyle Expanded = expandPresets(Style);
1651   if (Expanded.DisableFormat)
1652     return tooling::Replacements();
1653 
1654   std::unique_ptr<Environment> Env =
1655       Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
1656   Formatter Format(*Env, Expanded, IncompleteFormat);
1657   return Format.process();
1658 }
1659 
1660 tooling::Replacements cleanup(const FormatStyle &Style, SourceManager &SM,
1661                               FileID ID, ArrayRef<CharSourceRange> Ranges) {
1662   Environment Env(SM, ID, Ranges);
1663   Cleaner Clean(Env, Style);
1664   return Clean.process();
1665 }
1666 
1667 tooling::Replacements cleanup(const FormatStyle &Style, StringRef Code,
1668                               ArrayRef<tooling::Range> Ranges,
1669                               StringRef FileName) {
1670   std::unique_ptr<Environment> Env =
1671       Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
1672   Cleaner Clean(*Env, Style);
1673   return Clean.process();
1674 }
1675 
1676 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
1677   LangOptions LangOpts;
1678   LangOpts.CPlusPlus = 1;
1679   LangOpts.CPlusPlus11 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1680   LangOpts.CPlusPlus14 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1681   LangOpts.LineComment = 1;
1682   bool AlternativeOperators = Style.Language == FormatStyle::LK_Cpp;
1683   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
1684   LangOpts.Bool = 1;
1685   LangOpts.ObjC1 = 1;
1686   LangOpts.ObjC2 = 1;
1687   LangOpts.MicrosoftExt = 1;    // To get kw___try, kw___finally.
1688   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
1689   return LangOpts;
1690 }
1691 
1692 const char *StyleOptionHelpDescription =
1693     "Coding style, currently supports:\n"
1694     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
1695     "Use -style=file to load style configuration from\n"
1696     ".clang-format file located in one of the parent\n"
1697     "directories of the source file (or current\n"
1698     "directory for stdin).\n"
1699     "Use -style=\"{key: value, ...}\" to set specific\n"
1700     "parameters, e.g.:\n"
1701     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
1702 
1703 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
1704   if (FileName.endswith(".java"))
1705     return FormatStyle::LK_Java;
1706   if (FileName.endswith_lower(".js") || FileName.endswith_lower(".ts"))
1707     return FormatStyle::LK_JavaScript; // JavaScript or TypeScript.
1708   if (FileName.endswith_lower(".proto") ||
1709       FileName.endswith_lower(".protodevel"))
1710     return FormatStyle::LK_Proto;
1711   if (FileName.endswith_lower(".td"))
1712     return FormatStyle::LK_TableGen;
1713   return FormatStyle::LK_Cpp;
1714 }
1715 
1716 FormatStyle getStyle(StringRef StyleName, StringRef FileName,
1717                      StringRef FallbackStyle, vfs::FileSystem *FS) {
1718   if (!FS) {
1719     FS = vfs::getRealFileSystem().get();
1720   }
1721   FormatStyle Style = getLLVMStyle();
1722   Style.Language = getLanguageByFileName(FileName);
1723   if (!getPredefinedStyle(FallbackStyle, Style.Language, &Style)) {
1724     llvm::errs() << "Invalid fallback style \"" << FallbackStyle
1725                  << "\" using LLVM style\n";
1726     return Style;
1727   }
1728 
1729   if (StyleName.startswith("{")) {
1730     // Parse YAML/JSON style from the command line.
1731     if (std::error_code ec = parseConfiguration(StyleName, &Style)) {
1732       llvm::errs() << "Error parsing -style: " << ec.message() << ", using "
1733                    << FallbackStyle << " style\n";
1734     }
1735     return Style;
1736   }
1737 
1738   if (!StyleName.equals_lower("file")) {
1739     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
1740       llvm::errs() << "Invalid value for -style, using " << FallbackStyle
1741                    << " style\n";
1742     return Style;
1743   }
1744 
1745   // Look for .clang-format/_clang-format file in the file's parent directories.
1746   SmallString<128> UnsuitableConfigFiles;
1747   SmallString<128> Path(FileName);
1748   llvm::sys::fs::make_absolute(Path);
1749   for (StringRef Directory = Path; !Directory.empty();
1750        Directory = llvm::sys::path::parent_path(Directory)) {
1751 
1752     auto Status = FS->status(Directory);
1753     if (!Status ||
1754         Status->getType() != llvm::sys::fs::file_type::directory_file) {
1755       continue;
1756     }
1757 
1758     SmallString<128> ConfigFile(Directory);
1759 
1760     llvm::sys::path::append(ConfigFile, ".clang-format");
1761     DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1762 
1763     Status = FS->status(ConfigFile.str());
1764     bool IsFile =
1765         Status && (Status->getType() == llvm::sys::fs::file_type::regular_file);
1766     if (!IsFile) {
1767       // Try _clang-format too, since dotfiles are not commonly used on Windows.
1768       ConfigFile = Directory;
1769       llvm::sys::path::append(ConfigFile, "_clang-format");
1770       DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1771       Status = FS->status(ConfigFile.str());
1772       IsFile = Status &&
1773                (Status->getType() == llvm::sys::fs::file_type::regular_file);
1774     }
1775 
1776     if (IsFile) {
1777       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
1778           FS->getBufferForFile(ConfigFile.str());
1779       if (std::error_code EC = Text.getError()) {
1780         llvm::errs() << EC.message() << "\n";
1781         break;
1782       }
1783       if (std::error_code ec =
1784               parseConfiguration(Text.get()->getBuffer(), &Style)) {
1785         if (ec == ParseError::Unsuitable) {
1786           if (!UnsuitableConfigFiles.empty())
1787             UnsuitableConfigFiles.append(", ");
1788           UnsuitableConfigFiles.append(ConfigFile);
1789           continue;
1790         }
1791         llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message()
1792                      << "\n";
1793         break;
1794       }
1795       DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
1796       return Style;
1797     }
1798   }
1799   if (!UnsuitableConfigFiles.empty()) {
1800     llvm::errs() << "Configuration file(s) do(es) not support "
1801                  << getLanguageName(Style.Language) << ": "
1802                  << UnsuitableConfigFiles << "\n";
1803   }
1804   return Style;
1805 }
1806 
1807 } // namespace format
1808 } // namespace clang
1809