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