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 "ContinuationIndenter.h"
18 #include "TokenAnnotator.h"
19 #include "UnwrappedLineFormatter.h"
20 #include "UnwrappedLineParser.h"
21 #include "WhitespaceManager.h"
22 #include "clang/Basic/Diagnostic.h"
23 #include "clang/Basic/DiagnosticOptions.h"
24 #include "clang/Basic/SourceManager.h"
25 #include "clang/Lex/Lexer.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/Support/Allocator.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/Path.h"
30 #include "llvm/Support/Regex.h"
31 #include "llvm/Support/YAMLTraits.h"
32 #include <queue>
33 #include <string>
34 
35 #define DEBUG_TYPE "format-formatter"
36 
37 using clang::format::FormatStyle;
38 
39 LLVM_YAML_IS_FLOW_SEQUENCE_VECTOR(std::string)
40 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::format::FormatStyle::IncludeCategory)
41 
42 namespace llvm {
43 namespace yaml {
44 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
45   static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
46     IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
47     IO.enumCase(Value, "Java", FormatStyle::LK_Java);
48     IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
49     IO.enumCase(Value, "Proto", FormatStyle::LK_Proto);
50   }
51 };
52 
53 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
54   static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
55     IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03);
56     IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03);
57     IO.enumCase(Value, "Cpp11", FormatStyle::LS_Cpp11);
58     IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11);
59     IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
60   }
61 };
62 
63 template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
64   static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
65     IO.enumCase(Value, "Never", FormatStyle::UT_Never);
66     IO.enumCase(Value, "false", FormatStyle::UT_Never);
67     IO.enumCase(Value, "Always", FormatStyle::UT_Always);
68     IO.enumCase(Value, "true", FormatStyle::UT_Always);
69     IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
70   }
71 };
72 
73 template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
74   static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
75     IO.enumCase(Value, "None", FormatStyle::SFS_None);
76     IO.enumCase(Value, "false", FormatStyle::SFS_None);
77     IO.enumCase(Value, "All", FormatStyle::SFS_All);
78     IO.enumCase(Value, "true", FormatStyle::SFS_All);
79     IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
80     IO.enumCase(Value, "Empty", FormatStyle::SFS_Empty);
81   }
82 };
83 
84 template <> struct ScalarEnumerationTraits<FormatStyle::BinaryOperatorStyle> {
85   static void enumeration(IO &IO, FormatStyle::BinaryOperatorStyle &Value) {
86     IO.enumCase(Value, "All", FormatStyle::BOS_All);
87     IO.enumCase(Value, "true", FormatStyle::BOS_All);
88     IO.enumCase(Value, "None", FormatStyle::BOS_None);
89     IO.enumCase(Value, "false", FormatStyle::BOS_None);
90     IO.enumCase(Value, "NonAssignment", FormatStyle::BOS_NonAssignment);
91   }
92 };
93 
94 template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
95   static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
96     IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
97     IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
98     IO.enumCase(Value, "Mozilla", FormatStyle::BS_Mozilla);
99     IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
100     IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
101     IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
102     IO.enumCase(Value, "WebKit", FormatStyle::BS_WebKit);
103     IO.enumCase(Value, "Custom", FormatStyle::BS_Custom);
104   }
105 };
106 
107 template <>
108 struct ScalarEnumerationTraits<FormatStyle::DefinitionReturnTypeBreakingStyle> {
109   static void
110   enumeration(IO &IO, FormatStyle::DefinitionReturnTypeBreakingStyle &Value) {
111     IO.enumCase(Value, "None", FormatStyle::DRTBS_None);
112     IO.enumCase(Value, "All", FormatStyle::DRTBS_All);
113     IO.enumCase(Value, "TopLevel", FormatStyle::DRTBS_TopLevel);
114 
115     // For backward compatibility.
116     IO.enumCase(Value, "false", FormatStyle::DRTBS_None);
117     IO.enumCase(Value, "true", FormatStyle::DRTBS_All);
118   }
119 };
120 
121 template <>
122 struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
123   static void enumeration(IO &IO,
124                           FormatStyle::NamespaceIndentationKind &Value) {
125     IO.enumCase(Value, "None", FormatStyle::NI_None);
126     IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
127     IO.enumCase(Value, "All", FormatStyle::NI_All);
128   }
129 };
130 
131 template <> struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
132   static void enumeration(IO &IO, FormatStyle::PointerAlignmentStyle &Value) {
133     IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
134     IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
135     IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
136 
137     // For backward compatibility.
138     IO.enumCase(Value, "true", FormatStyle::PAS_Left);
139     IO.enumCase(Value, "false", FormatStyle::PAS_Right);
140   }
141 };
142 
143 template <>
144 struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
145   static void enumeration(IO &IO,
146                           FormatStyle::SpaceBeforeParensOptions &Value) {
147     IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
148     IO.enumCase(Value, "ControlStatements",
149                 FormatStyle::SBPO_ControlStatements);
150     IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
151 
152     // For backward compatibility.
153     IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
154     IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
155   }
156 };
157 
158 template <> struct MappingTraits<FormatStyle> {
159   static void mapping(IO &IO, FormatStyle &Style) {
160     // When reading, read the language first, we need it for getPredefinedStyle.
161     IO.mapOptional("Language", Style.Language);
162 
163     if (IO.outputting()) {
164       StringRef StylesArray[] = {"LLVM",    "Google", "Chromium",
165                                  "Mozilla", "WebKit", "GNU"};
166       ArrayRef<StringRef> Styles(StylesArray);
167       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
168         StringRef StyleName(Styles[i]);
169         FormatStyle PredefinedStyle;
170         if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
171             Style == PredefinedStyle) {
172           IO.mapOptional("# BasedOnStyle", StyleName);
173           break;
174         }
175       }
176     } else {
177       StringRef BasedOnStyle;
178       IO.mapOptional("BasedOnStyle", BasedOnStyle);
179       if (!BasedOnStyle.empty()) {
180         FormatStyle::LanguageKind OldLanguage = Style.Language;
181         FormatStyle::LanguageKind Language =
182             ((FormatStyle *)IO.getContext())->Language;
183         if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
184           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
185           return;
186         }
187         Style.Language = OldLanguage;
188       }
189     }
190 
191     // For backward compatibility.
192     if (!IO.outputting()) {
193       IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
194       IO.mapOptional("IndentFunctionDeclarationAfterType",
195                      Style.IndentWrappedFunctionNames);
196       IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
197       IO.mapOptional("SpaceAfterControlStatementKeyword",
198                      Style.SpaceBeforeParens);
199     }
200 
201     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
202     IO.mapOptional("AlignAfterOpenBracket", Style.AlignAfterOpenBracket);
203     IO.mapOptional("AlignConsecutiveAssignments",
204                    Style.AlignConsecutiveAssignments);
205     IO.mapOptional("AlignConsecutiveDeclarations",
206                    Style.AlignConsecutiveDeclarations);
207     IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
208     IO.mapOptional("AlignOperands", Style.AlignOperands);
209     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
210     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
211                    Style.AllowAllParametersOfDeclarationOnNextLine);
212     IO.mapOptional("AllowShortBlocksOnASingleLine",
213                    Style.AllowShortBlocksOnASingleLine);
214     IO.mapOptional("AllowShortCaseLabelsOnASingleLine",
215                    Style.AllowShortCaseLabelsOnASingleLine);
216     IO.mapOptional("AllowShortFunctionsOnASingleLine",
217                    Style.AllowShortFunctionsOnASingleLine);
218     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
219                    Style.AllowShortIfStatementsOnASingleLine);
220     IO.mapOptional("AllowShortLoopsOnASingleLine",
221                    Style.AllowShortLoopsOnASingleLine);
222     IO.mapOptional("AlwaysBreakAfterDefinitionReturnType",
223                    Style.AlwaysBreakAfterDefinitionReturnType);
224     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
225                    Style.AlwaysBreakBeforeMultilineStrings);
226     IO.mapOptional("AlwaysBreakTemplateDeclarations",
227                    Style.AlwaysBreakTemplateDeclarations);
228     IO.mapOptional("BinPackArguments", Style.BinPackArguments);
229     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
230     IO.mapOptional("BraceWrapping", Style.BraceWrapping);
231     IO.mapOptional("BreakBeforeBinaryOperators",
232                    Style.BreakBeforeBinaryOperators);
233     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
234     IO.mapOptional("BreakBeforeTernaryOperators",
235                    Style.BreakBeforeTernaryOperators);
236     IO.mapOptional("BreakConstructorInitializersBeforeComma",
237                    Style.BreakConstructorInitializersBeforeComma);
238     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
239     IO.mapOptional("CommentPragmas", Style.CommentPragmas);
240     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
241                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
242     IO.mapOptional("ConstructorInitializerIndentWidth",
243                    Style.ConstructorInitializerIndentWidth);
244     IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
245     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
246     IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
247     IO.mapOptional("DisableFormat", Style.DisableFormat);
248     IO.mapOptional("ExperimentalAutoDetectBinPacking",
249                    Style.ExperimentalAutoDetectBinPacking);
250     IO.mapOptional("ForEachMacros", Style.ForEachMacros);
251     IO.mapOptional("IncludeCategories", Style.IncludeCategories);
252     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
253     IO.mapOptional("IndentWidth", Style.IndentWidth);
254     IO.mapOptional("IndentWrappedFunctionNames",
255                    Style.IndentWrappedFunctionNames);
256     IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
257                    Style.KeepEmptyLinesAtTheStartOfBlocks);
258     IO.mapOptional("MacroBlockBegin", Style.MacroBlockBegin);
259     IO.mapOptional("MacroBlockEnd", Style.MacroBlockEnd);
260     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
261     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
262     IO.mapOptional("ObjCBlockIndentWidth", Style.ObjCBlockIndentWidth);
263     IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
264     IO.mapOptional("ObjCSpaceBeforeProtocolList",
265                    Style.ObjCSpaceBeforeProtocolList);
266     IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
267                    Style.PenaltyBreakBeforeFirstCallParameter);
268     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
269     IO.mapOptional("PenaltyBreakFirstLessLess",
270                    Style.PenaltyBreakFirstLessLess);
271     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
272     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
273     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
274                    Style.PenaltyReturnTypeOnItsOwnLine);
275     IO.mapOptional("PointerAlignment", Style.PointerAlignment);
276     IO.mapOptional("SpaceAfterCStyleCast", Style.SpaceAfterCStyleCast);
277     IO.mapOptional("SpaceBeforeAssignmentOperators",
278                    Style.SpaceBeforeAssignmentOperators);
279     IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
280     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
281     IO.mapOptional("SpacesBeforeTrailingComments",
282                    Style.SpacesBeforeTrailingComments);
283     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
284     IO.mapOptional("SpacesInContainerLiterals",
285                    Style.SpacesInContainerLiterals);
286     IO.mapOptional("SpacesInCStyleCastParentheses",
287                    Style.SpacesInCStyleCastParentheses);
288     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
289     IO.mapOptional("SpacesInSquareBrackets", Style.SpacesInSquareBrackets);
290     IO.mapOptional("Standard", Style.Standard);
291     IO.mapOptional("TabWidth", Style.TabWidth);
292     IO.mapOptional("UseTab", Style.UseTab);
293   }
294 };
295 
296 template <> struct MappingTraits<FormatStyle::BraceWrappingFlags> {
297   static void mapping(IO &IO, FormatStyle::BraceWrappingFlags &Wrapping) {
298     IO.mapOptional("AfterClass", Wrapping.AfterClass);
299     IO.mapOptional("AfterControlStatement", Wrapping.AfterControlStatement);
300     IO.mapOptional("AfterEnum", Wrapping.AfterEnum);
301     IO.mapOptional("AfterFunction", Wrapping.AfterFunction);
302     IO.mapOptional("AfterNamespace", Wrapping.AfterNamespace);
303     IO.mapOptional("AfterObjCDeclaration", Wrapping.AfterObjCDeclaration);
304     IO.mapOptional("AfterStruct", Wrapping.AfterStruct);
305     IO.mapOptional("AfterUnion", Wrapping.AfterUnion);
306     IO.mapOptional("BeforeCatch", Wrapping.BeforeCatch);
307     IO.mapOptional("BeforeElse", Wrapping.BeforeElse);
308     IO.mapOptional("IndentBraces", Wrapping.IndentBraces);
309   }
310 };
311 
312 template <> struct MappingTraits<FormatStyle::IncludeCategory> {
313   static void mapping(IO &IO, FormatStyle::IncludeCategory &Category) {
314     IO.mapOptional("Regex", Category.Regex);
315     IO.mapOptional("Priority", Category.Priority);
316   }
317 };
318 
319 // Allows to read vector<FormatStyle> while keeping default values.
320 // IO.getContext() should contain a pointer to the FormatStyle structure, that
321 // will be used to get default values for missing keys.
322 // If the first element has no Language specified, it will be treated as the
323 // default one for the following elements.
324 template <> struct DocumentListTraits<std::vector<FormatStyle>> {
325   static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
326     return Seq.size();
327   }
328   static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
329                               size_t Index) {
330     if (Index >= Seq.size()) {
331       assert(Index == Seq.size());
332       FormatStyle Template;
333       if (Seq.size() > 0 && Seq[0].Language == FormatStyle::LK_None) {
334         Template = Seq[0];
335       } else {
336         Template = *((const FormatStyle *)IO.getContext());
337         Template.Language = FormatStyle::LK_None;
338       }
339       Seq.resize(Index + 1, Template);
340     }
341     return Seq[Index];
342   }
343 };
344 } // namespace yaml
345 } // namespace llvm
346 
347 namespace clang {
348 namespace format {
349 
350 const std::error_category &getParseCategory() {
351   static ParseErrorCategory C;
352   return C;
353 }
354 std::error_code make_error_code(ParseError e) {
355   return std::error_code(static_cast<int>(e), getParseCategory());
356 }
357 
358 const char *ParseErrorCategory::name() const LLVM_NOEXCEPT {
359   return "clang-format.parse_error";
360 }
361 
362 std::string ParseErrorCategory::message(int EV) const {
363   switch (static_cast<ParseError>(EV)) {
364   case ParseError::Success:
365     return "Success";
366   case ParseError::Error:
367     return "Invalid argument";
368   case ParseError::Unsuitable:
369     return "Unsuitable";
370   }
371   llvm_unreachable("unexpected parse error");
372 }
373 
374 static FormatStyle expandPresets(const FormatStyle &Style) {
375   if (Style.BreakBeforeBraces == FormatStyle::BS_Custom)
376     return Style;
377   FormatStyle Expanded = Style;
378   Expanded.BraceWrapping = {false, false, false, false, false, false,
379                             false, false, false, false, false};
380   switch (Style.BreakBeforeBraces) {
381   case FormatStyle::BS_Linux:
382     Expanded.BraceWrapping.AfterClass = true;
383     Expanded.BraceWrapping.AfterFunction = true;
384     Expanded.BraceWrapping.AfterNamespace = true;
385     Expanded.BraceWrapping.BeforeElse = true;
386     break;
387   case FormatStyle::BS_Mozilla:
388     Expanded.BraceWrapping.AfterClass = true;
389     Expanded.BraceWrapping.AfterEnum = true;
390     Expanded.BraceWrapping.AfterFunction = true;
391     Expanded.BraceWrapping.AfterStruct = true;
392     Expanded.BraceWrapping.AfterUnion = true;
393     break;
394   case FormatStyle::BS_Stroustrup:
395     Expanded.BraceWrapping.AfterFunction = true;
396     Expanded.BraceWrapping.BeforeCatch = true;
397     Expanded.BraceWrapping.BeforeElse = true;
398     break;
399   case FormatStyle::BS_Allman:
400     Expanded.BraceWrapping.AfterClass = true;
401     Expanded.BraceWrapping.AfterControlStatement = true;
402     Expanded.BraceWrapping.AfterEnum = true;
403     Expanded.BraceWrapping.AfterFunction = true;
404     Expanded.BraceWrapping.AfterNamespace = true;
405     Expanded.BraceWrapping.AfterObjCDeclaration = true;
406     Expanded.BraceWrapping.AfterStruct = true;
407     Expanded.BraceWrapping.BeforeCatch = true;
408     Expanded.BraceWrapping.BeforeElse = true;
409     break;
410   case FormatStyle::BS_GNU:
411     Expanded.BraceWrapping = {true, true, true, true, true, true,
412                               true, true, true, true, true};
413     break;
414   case FormatStyle::BS_WebKit:
415     Expanded.BraceWrapping.AfterFunction = true;
416     break;
417   default:
418     break;
419   }
420   return Expanded;
421 }
422 
423 FormatStyle getLLVMStyle() {
424   FormatStyle LLVMStyle;
425   LLVMStyle.Language = FormatStyle::LK_Cpp;
426   LLVMStyle.AccessModifierOffset = -2;
427   LLVMStyle.AlignEscapedNewlinesLeft = false;
428   LLVMStyle.AlignAfterOpenBracket = true;
429   LLVMStyle.AlignOperands = true;
430   LLVMStyle.AlignTrailingComments = true;
431   LLVMStyle.AlignConsecutiveAssignments = false;
432   LLVMStyle.AlignConsecutiveDeclarations = false;
433   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
434   LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
435   LLVMStyle.AllowShortBlocksOnASingleLine = false;
436   LLVMStyle.AllowShortCaseLabelsOnASingleLine = false;
437   LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
438   LLVMStyle.AllowShortLoopsOnASingleLine = false;
439   LLVMStyle.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_None;
440   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
441   LLVMStyle.AlwaysBreakTemplateDeclarations = false;
442   LLVMStyle.BinPackParameters = true;
443   LLVMStyle.BinPackArguments = true;
444   LLVMStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_None;
445   LLVMStyle.BreakBeforeTernaryOperators = true;
446   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
447   LLVMStyle.BraceWrapping = {false, false, false, false, false, false,
448                              false, false, false, false, false};
449   LLVMStyle.BreakConstructorInitializersBeforeComma = false;
450   LLVMStyle.ColumnLimit = 80;
451   LLVMStyle.CommentPragmas = "^ IWYU pragma:";
452   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
453   LLVMStyle.ConstructorInitializerIndentWidth = 4;
454   LLVMStyle.ContinuationIndentWidth = 4;
455   LLVMStyle.Cpp11BracedListStyle = true;
456   LLVMStyle.DerivePointerAlignment = false;
457   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
458   LLVMStyle.ForEachMacros.push_back("foreach");
459   LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
460   LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
461   LLVMStyle.IncludeCategories = {{"^\"(llvm|llvm-c|clang|clang-c)/", 2},
462                                  {"^(<|\"(gtest|isl|json)/)", 3},
463                                  {".*", 1}};
464   LLVMStyle.IndentCaseLabels = false;
465   LLVMStyle.IndentWrappedFunctionNames = false;
466   LLVMStyle.IndentWidth = 2;
467   LLVMStyle.TabWidth = 8;
468   LLVMStyle.MaxEmptyLinesToKeep = 1;
469   LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
470   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
471   LLVMStyle.ObjCBlockIndentWidth = 2;
472   LLVMStyle.ObjCSpaceAfterProperty = false;
473   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
474   LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
475   LLVMStyle.SpacesBeforeTrailingComments = 1;
476   LLVMStyle.Standard = FormatStyle::LS_Cpp11;
477   LLVMStyle.UseTab = FormatStyle::UT_Never;
478   LLVMStyle.SpacesInParentheses = false;
479   LLVMStyle.SpacesInSquareBrackets = false;
480   LLVMStyle.SpaceInEmptyParentheses = false;
481   LLVMStyle.SpacesInContainerLiterals = true;
482   LLVMStyle.SpacesInCStyleCastParentheses = false;
483   LLVMStyle.SpaceAfterCStyleCast = false;
484   LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
485   LLVMStyle.SpaceBeforeAssignmentOperators = true;
486   LLVMStyle.SpacesInAngles = false;
487 
488   LLVMStyle.PenaltyBreakComment = 300;
489   LLVMStyle.PenaltyBreakFirstLessLess = 120;
490   LLVMStyle.PenaltyBreakString = 1000;
491   LLVMStyle.PenaltyExcessCharacter = 1000000;
492   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
493   LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
494 
495   LLVMStyle.DisableFormat = false;
496 
497   return LLVMStyle;
498 }
499 
500 FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
501   FormatStyle GoogleStyle = getLLVMStyle();
502   GoogleStyle.Language = Language;
503 
504   GoogleStyle.AccessModifierOffset = -1;
505   GoogleStyle.AlignEscapedNewlinesLeft = true;
506   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
507   GoogleStyle.AllowShortLoopsOnASingleLine = true;
508   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
509   GoogleStyle.AlwaysBreakTemplateDeclarations = true;
510   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
511   GoogleStyle.DerivePointerAlignment = true;
512   GoogleStyle.IncludeCategories = {{"^<.*\\.h>", 1}, {"^<.*", 2}, {".*", 3}};
513   GoogleStyle.IndentCaseLabels = true;
514   GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
515   GoogleStyle.ObjCSpaceAfterProperty = false;
516   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
517   GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
518   GoogleStyle.SpacesBeforeTrailingComments = 2;
519   GoogleStyle.Standard = FormatStyle::LS_Auto;
520 
521   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
522   GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
523 
524   if (Language == FormatStyle::LK_Java) {
525     GoogleStyle.AlignAfterOpenBracket = false;
526     GoogleStyle.AlignOperands = false;
527     GoogleStyle.AlignTrailingComments = false;
528     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
529     GoogleStyle.AllowShortIfStatementsOnASingleLine = false;
530     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
531     GoogleStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_NonAssignment;
532     GoogleStyle.ColumnLimit = 100;
533     GoogleStyle.SpaceAfterCStyleCast = true;
534     GoogleStyle.SpacesBeforeTrailingComments = 1;
535   } else if (Language == FormatStyle::LK_JavaScript) {
536     GoogleStyle.BreakBeforeTernaryOperators = false;
537     GoogleStyle.MaxEmptyLinesToKeep = 3;
538     GoogleStyle.SpacesInContainerLiterals = false;
539     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
540     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
541   } else if (Language == FormatStyle::LK_Proto) {
542     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
543     GoogleStyle.SpacesInContainerLiterals = false;
544   }
545 
546   return GoogleStyle;
547 }
548 
549 FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
550   FormatStyle ChromiumStyle = getGoogleStyle(Language);
551   if (Language == FormatStyle::LK_Java) {
552     ChromiumStyle.AllowShortIfStatementsOnASingleLine = true;
553     ChromiumStyle.IndentWidth = 4;
554     ChromiumStyle.ContinuationIndentWidth = 8;
555   } else {
556     ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
557     ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
558     ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
559     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
560     ChromiumStyle.BinPackParameters = false;
561     ChromiumStyle.DerivePointerAlignment = false;
562   }
563   return ChromiumStyle;
564 }
565 
566 FormatStyle getMozillaStyle() {
567   FormatStyle MozillaStyle = getLLVMStyle();
568   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
569   MozillaStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
570   MozillaStyle.AlwaysBreakAfterDefinitionReturnType =
571       FormatStyle::DRTBS_TopLevel;
572   MozillaStyle.AlwaysBreakTemplateDeclarations = true;
573   MozillaStyle.BreakBeforeBraces = FormatStyle::BS_Mozilla;
574   MozillaStyle.BreakConstructorInitializersBeforeComma = true;
575   MozillaStyle.ConstructorInitializerIndentWidth = 2;
576   MozillaStyle.ContinuationIndentWidth = 2;
577   MozillaStyle.Cpp11BracedListStyle = false;
578   MozillaStyle.IndentCaseLabels = true;
579   MozillaStyle.ObjCSpaceAfterProperty = true;
580   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
581   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
582   MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
583   return MozillaStyle;
584 }
585 
586 FormatStyle getWebKitStyle() {
587   FormatStyle Style = getLLVMStyle();
588   Style.AccessModifierOffset = -4;
589   Style.AlignAfterOpenBracket = false;
590   Style.AlignOperands = false;
591   Style.AlignTrailingComments = false;
592   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
593   Style.BreakBeforeBraces = FormatStyle::BS_WebKit;
594   Style.BreakConstructorInitializersBeforeComma = true;
595   Style.Cpp11BracedListStyle = false;
596   Style.ColumnLimit = 0;
597   Style.IndentWidth = 4;
598   Style.NamespaceIndentation = FormatStyle::NI_Inner;
599   Style.ObjCBlockIndentWidth = 4;
600   Style.ObjCSpaceAfterProperty = true;
601   Style.PointerAlignment = FormatStyle::PAS_Left;
602   Style.Standard = FormatStyle::LS_Cpp03;
603   return Style;
604 }
605 
606 FormatStyle getGNUStyle() {
607   FormatStyle Style = getLLVMStyle();
608   Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_All;
609   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
610   Style.BreakBeforeBraces = FormatStyle::BS_GNU;
611   Style.BreakBeforeTernaryOperators = true;
612   Style.Cpp11BracedListStyle = false;
613   Style.ColumnLimit = 79;
614   Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
615   Style.Standard = FormatStyle::LS_Cpp03;
616   return Style;
617 }
618 
619 FormatStyle getNoStyle() {
620   FormatStyle NoStyle = getLLVMStyle();
621   NoStyle.DisableFormat = true;
622   return NoStyle;
623 }
624 
625 bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
626                         FormatStyle *Style) {
627   if (Name.equals_lower("llvm")) {
628     *Style = getLLVMStyle();
629   } else if (Name.equals_lower("chromium")) {
630     *Style = getChromiumStyle(Language);
631   } else if (Name.equals_lower("mozilla")) {
632     *Style = getMozillaStyle();
633   } else if (Name.equals_lower("google")) {
634     *Style = getGoogleStyle(Language);
635   } else if (Name.equals_lower("webkit")) {
636     *Style = getWebKitStyle();
637   } else if (Name.equals_lower("gnu")) {
638     *Style = getGNUStyle();
639   } else if (Name.equals_lower("none")) {
640     *Style = getNoStyle();
641   } else {
642     return false;
643   }
644 
645   Style->Language = Language;
646   return true;
647 }
648 
649 std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
650   assert(Style);
651   FormatStyle::LanguageKind Language = Style->Language;
652   assert(Language != FormatStyle::LK_None);
653   if (Text.trim().empty())
654     return make_error_code(ParseError::Error);
655 
656   std::vector<FormatStyle> Styles;
657   llvm::yaml::Input Input(Text);
658   // DocumentListTraits<vector<FormatStyle>> uses the context to get default
659   // values for the fields, keys for which are missing from the configuration.
660   // Mapping also uses the context to get the language to find the correct
661   // base style.
662   Input.setContext(Style);
663   Input >> Styles;
664   if (Input.error())
665     return Input.error();
666 
667   for (unsigned i = 0; i < Styles.size(); ++i) {
668     // Ensures that only the first configuration can skip the Language option.
669     if (Styles[i].Language == FormatStyle::LK_None && i != 0)
670       return make_error_code(ParseError::Error);
671     // Ensure that each language is configured at most once.
672     for (unsigned j = 0; j < i; ++j) {
673       if (Styles[i].Language == Styles[j].Language) {
674         DEBUG(llvm::dbgs()
675               << "Duplicate languages in the config file on positions " << j
676               << " and " << i << "\n");
677         return make_error_code(ParseError::Error);
678       }
679     }
680   }
681   // Look for a suitable configuration starting from the end, so we can
682   // find the configuration for the specific language first, and the default
683   // configuration (which can only be at slot 0) after it.
684   for (int i = Styles.size() - 1; i >= 0; --i) {
685     if (Styles[i].Language == Language ||
686         Styles[i].Language == FormatStyle::LK_None) {
687       *Style = Styles[i];
688       Style->Language = Language;
689       return make_error_code(ParseError::Success);
690     }
691   }
692   return make_error_code(ParseError::Unsuitable);
693 }
694 
695 std::string configurationAsText(const FormatStyle &Style) {
696   std::string Text;
697   llvm::raw_string_ostream Stream(Text);
698   llvm::yaml::Output Output(Stream);
699   // We use the same mapping method for input and output, so we need a non-const
700   // reference here.
701   FormatStyle NonConstStyle = expandPresets(Style);
702   Output << NonConstStyle;
703   return Stream.str();
704 }
705 
706 namespace {
707 
708 class FormatTokenLexer {
709 public:
710   FormatTokenLexer(SourceManager &SourceMgr, FileID ID, FormatStyle &Style,
711                    encoding::Encoding Encoding)
712       : FormatTok(nullptr), IsFirstToken(true), GreaterStashed(false),
713         LessStashed(false), Column(0), TrailingWhitespace(0),
714         SourceMgr(SourceMgr), ID(ID), Style(Style),
715         IdentTable(getFormattingLangOpts(Style)), Keywords(IdentTable),
716         Encoding(Encoding), FirstInLineIndex(0), FormattingDisabled(false),
717         MacroBlockBeginRegex(Style.MacroBlockBegin),
718         MacroBlockEndRegex(Style.MacroBlockEnd) {
719     Lex.reset(new Lexer(ID, SourceMgr.getBuffer(ID), SourceMgr,
720                         getFormattingLangOpts(Style)));
721     Lex->SetKeepWhitespaceMode(true);
722 
723     for (const std::string &ForEachMacro : Style.ForEachMacros)
724       ForEachMacros.push_back(&IdentTable.get(ForEachMacro));
725     std::sort(ForEachMacros.begin(), ForEachMacros.end());
726   }
727 
728   ArrayRef<FormatToken *> lex() {
729     assert(Tokens.empty());
730     assert(FirstInLineIndex == 0);
731     do {
732       Tokens.push_back(getNextToken());
733       tryMergePreviousTokens();
734       if (Tokens.back()->NewlinesBefore > 0 || Tokens.back()->IsMultiline)
735         FirstInLineIndex = Tokens.size() - 1;
736     } while (Tokens.back()->Tok.isNot(tok::eof));
737     return Tokens;
738   }
739 
740   const AdditionalKeywords &getKeywords() { return Keywords; }
741 
742 private:
743   void tryMergePreviousTokens() {
744     if (tryMerge_TMacro())
745       return;
746     if (tryMergeConflictMarkers())
747       return;
748     if (tryMergeLessLess())
749       return;
750 
751     if (Style.Language == FormatStyle::LK_JavaScript) {
752       if (tryMergeJSRegexLiteral())
753         return;
754       if (tryMergeEscapeSequence())
755         return;
756       if (tryMergeTemplateString())
757         return;
758 
759       static const tok::TokenKind JSIdentity[] = {tok::equalequal, tok::equal};
760       static const tok::TokenKind JSNotIdentity[] = {tok::exclaimequal,
761                                                      tok::equal};
762       static const tok::TokenKind JSShiftEqual[] = {tok::greater, tok::greater,
763                                                     tok::greaterequal};
764       static const tok::TokenKind JSRightArrow[] = {tok::equal, tok::greater};
765       // FIXME: Investigate what token type gives the correct operator priority.
766       if (tryMergeTokens(JSIdentity, TT_BinaryOperator))
767         return;
768       if (tryMergeTokens(JSNotIdentity, TT_BinaryOperator))
769         return;
770       if (tryMergeTokens(JSShiftEqual, TT_BinaryOperator))
771         return;
772       if (tryMergeTokens(JSRightArrow, TT_JsFatArrow))
773         return;
774     }
775   }
776 
777   bool tryMergeLessLess() {
778     // Merge X,less,less,Y into X,lessless,Y unless X or Y is less.
779     if (Tokens.size() < 3)
780       return false;
781 
782     bool FourthTokenIsLess = false;
783     if (Tokens.size() > 3)
784       FourthTokenIsLess = (Tokens.end() - 4)[0]->is(tok::less);
785 
786     auto First = Tokens.end() - 3;
787     if (First[2]->is(tok::less) || First[1]->isNot(tok::less) ||
788         First[0]->isNot(tok::less) || FourthTokenIsLess)
789       return false;
790 
791     // Only merge if there currently is no whitespace between the two "<".
792     if (First[1]->WhitespaceRange.getBegin() !=
793         First[1]->WhitespaceRange.getEnd())
794       return false;
795 
796     First[0]->Tok.setKind(tok::lessless);
797     First[0]->TokenText = "<<";
798     First[0]->ColumnWidth += 1;
799     Tokens.erase(Tokens.end() - 2);
800     return true;
801   }
802 
803   bool tryMergeTokens(ArrayRef<tok::TokenKind> Kinds, TokenType NewType) {
804     if (Tokens.size() < Kinds.size())
805       return false;
806 
807     SmallVectorImpl<FormatToken *>::const_iterator First =
808         Tokens.end() - Kinds.size();
809     if (!First[0]->is(Kinds[0]))
810       return false;
811     unsigned AddLength = 0;
812     for (unsigned i = 1; i < Kinds.size(); ++i) {
813       if (!First[i]->is(Kinds[i]) ||
814           First[i]->WhitespaceRange.getBegin() !=
815               First[i]->WhitespaceRange.getEnd())
816         return false;
817       AddLength += First[i]->TokenText.size();
818     }
819     Tokens.resize(Tokens.size() - Kinds.size() + 1);
820     First[0]->TokenText = StringRef(First[0]->TokenText.data(),
821                                     First[0]->TokenText.size() + AddLength);
822     First[0]->ColumnWidth += AddLength;
823     First[0]->Type = NewType;
824     return true;
825   }
826 
827   // Tries to merge an escape sequence, i.e. a "\\" and the following
828   // character. Use e.g. inside JavaScript regex literals.
829   bool tryMergeEscapeSequence() {
830     if (Tokens.size() < 2)
831       return false;
832     FormatToken *Previous = Tokens[Tokens.size() - 2];
833     if (Previous->isNot(tok::unknown) || Previous->TokenText != "\\")
834       return false;
835     ++Previous->ColumnWidth;
836     StringRef Text = Previous->TokenText;
837     Previous->TokenText = StringRef(Text.data(), Text.size() + 1);
838     resetLexer(SourceMgr.getFileOffset(Tokens.back()->Tok.getLocation()) + 1);
839     Tokens.resize(Tokens.size() - 1);
840     Column = Previous->OriginalColumn + Previous->ColumnWidth;
841     return true;
842   }
843 
844   // Try to determine whether the current token ends a JavaScript regex literal.
845   // We heuristically assume that this is a regex literal if we find two
846   // unescaped slashes on a line and the token before the first slash is one of
847   // "(;,{}![:?", a binary operator or 'return', as those cannot be followed by
848   // a division.
849   bool tryMergeJSRegexLiteral() {
850     if (Tokens.size() < 2)
851       return false;
852 
853     // If this is a string literal with a slash inside, compute the slash's
854     // offset and try to find the beginning of the regex literal.
855     // Also look at tok::unknown, as it can be an unterminated char literal.
856     size_t SlashInStringPos = StringRef::npos;
857     if (Tokens.back()->isOneOf(tok::string_literal, tok::char_constant,
858                                tok::unknown)) {
859       // Start search from position 1 as otherwise, this is an unknown token
860       // for an unterminated /*-comment which is handled elsewhere.
861       SlashInStringPos = Tokens.back()->TokenText.find('/', 1);
862       if (SlashInStringPos == StringRef::npos)
863         return false;
864     }
865 
866     // If a regex literal ends in "\//", this gets represented by an unknown
867     // token "\" and a comment.
868     bool MightEndWithEscapedSlash =
869         Tokens.back()->is(tok::comment) &&
870         Tokens.back()->TokenText.startswith("//") &&
871         Tokens[Tokens.size() - 2]->TokenText == "\\";
872     if (!MightEndWithEscapedSlash && SlashInStringPos == StringRef::npos &&
873         (Tokens.back()->isNot(tok::slash) ||
874          (Tokens[Tokens.size() - 2]->is(tok::unknown) &&
875           Tokens[Tokens.size() - 2]->TokenText == "\\")))
876       return false;
877 
878     unsigned TokenCount = 0;
879     bool InCharacterClass = false;
880     for (auto I = Tokens.rbegin() + 1, E = Tokens.rend(); I != E; ++I) {
881       ++TokenCount;
882       auto Prev = I + 1;
883       while (Prev != E && Prev[0]->is(tok::comment))
884         ++Prev;
885       // Slashes in character classes (delimited by [ and ]) do not need
886       // escaping. Escaping of the squares themselves is already handled by
887       // \c tryMergeEscapeSequence(), a plain tok::r_square must be non-escaped.
888       if (I[0]->is(tok::r_square))
889         InCharacterClass = true;
890       if (I[0]->is(tok::l_square)) {
891         if (!InCharacterClass)
892           return false;
893         InCharacterClass = false;
894       }
895       if (!InCharacterClass && I[0]->isOneOf(tok::slash, tok::slashequal) &&
896           (Prev == E ||
897            ((Prev[0]->isOneOf(tok::l_paren, tok::semi, tok::l_brace,
898                               tok::r_brace, tok::exclaim, tok::l_square,
899                               tok::colon, tok::comma, tok::question,
900                               tok::kw_return) ||
901              Prev[0]->isBinaryOperator())))) {
902         unsigned LastColumn = Tokens.back()->OriginalColumn;
903         SourceLocation Loc = Tokens.back()->Tok.getLocation();
904         if (MightEndWithEscapedSlash) {
905           // This regex literal ends in '\//'. Skip past the '//' of the last
906           // token and re-start lexing from there.
907           resetLexer(SourceMgr.getFileOffset(Loc) + 2);
908         } else if (SlashInStringPos != StringRef::npos) {
909           // This regex literal ends in a string_literal with a slash inside.
910           // Calculate end column and reset lexer appropriately.
911           resetLexer(SourceMgr.getFileOffset(Loc) + SlashInStringPos + 1);
912           LastColumn += SlashInStringPos;
913         }
914         Tokens.resize(Tokens.size() - TokenCount);
915         Tokens.back()->Tok.setKind(tok::unknown);
916         Tokens.back()->Type = TT_RegexLiteral;
917         // Treat regex literals like other string_literals.
918         Tokens.back()->Tok.setKind(tok::string_literal);
919         Tokens.back()->ColumnWidth += LastColumn - I[0]->OriginalColumn;
920         return true;
921       }
922 
923       // There can't be a newline inside a regex literal.
924       if (I[0]->NewlinesBefore > 0)
925         return false;
926     }
927     return false;
928   }
929 
930   bool tryMergeTemplateString() {
931     if (Tokens.size() < 2)
932       return false;
933 
934     FormatToken *EndBacktick = Tokens.back();
935     // Backticks get lexed as tok::unknown tokens. If a template string contains
936     // a comment start, it gets lexed as a tok::comment, or tok::unknown if
937     // unterminated.
938     if (!EndBacktick->isOneOf(tok::comment, tok::string_literal,
939                               tok::char_constant, tok::unknown))
940       return false;
941     size_t CommentBacktickPos = EndBacktick->TokenText.find('`');
942     // Unknown token that's not actually a backtick, or a comment that doesn't
943     // contain a backtick.
944     if (CommentBacktickPos == StringRef::npos)
945       return false;
946 
947     unsigned TokenCount = 0;
948     bool IsMultiline = false;
949     unsigned EndColumnInFirstLine =
950         EndBacktick->OriginalColumn + EndBacktick->ColumnWidth;
951     for (auto I = Tokens.rbegin() + 1, E = Tokens.rend(); I != E; I++) {
952       ++TokenCount;
953       if (I[0]->IsMultiline)
954         IsMultiline = true;
955 
956       // If there was a preceding template string, this must be the start of a
957       // template string, not the end.
958       if (I[0]->is(TT_TemplateString))
959         return false;
960 
961       if (I[0]->isNot(tok::unknown) || I[0]->TokenText != "`") {
962         // Keep track of the rhs offset of the last token to wrap across lines -
963         // its the rhs offset of the first line of the template string, used to
964         // determine its width.
965         if (I[0]->IsMultiline)
966           EndColumnInFirstLine = I[0]->OriginalColumn + I[0]->ColumnWidth;
967         // If the token has newlines, the token before it (if it exists) is the
968         // rhs end of the previous line.
969         if (I[0]->NewlinesBefore > 0 && (I + 1 != E)) {
970           EndColumnInFirstLine = I[1]->OriginalColumn + I[1]->ColumnWidth;
971           IsMultiline = true;
972         }
973         continue;
974       }
975 
976       Tokens.resize(Tokens.size() - TokenCount);
977       Tokens.back()->Type = TT_TemplateString;
978       const char *EndOffset =
979           EndBacktick->TokenText.data() + 1 + CommentBacktickPos;
980       if (CommentBacktickPos != 0) {
981         // If the backtick was not the first character (e.g. in a comment),
982         // re-lex after the backtick position.
983         SourceLocation Loc = EndBacktick->Tok.getLocation();
984         resetLexer(SourceMgr.getFileOffset(Loc) + CommentBacktickPos + 1);
985       }
986       Tokens.back()->TokenText =
987           StringRef(Tokens.back()->TokenText.data(),
988                     EndOffset - Tokens.back()->TokenText.data());
989 
990       unsigned EndOriginalColumn = EndBacktick->OriginalColumn;
991       if (EndOriginalColumn == 0) {
992         SourceLocation Loc = EndBacktick->Tok.getLocation();
993         EndOriginalColumn = SourceMgr.getSpellingColumnNumber(Loc);
994       }
995       // If the ` is further down within the token (e.g. in a comment).
996       EndOriginalColumn += CommentBacktickPos;
997 
998       if (IsMultiline) {
999         // ColumnWidth is from backtick to last token in line.
1000         // LastLineColumnWidth is 0 to backtick.
1001         // x = `some content
1002         //     until here`;
1003         Tokens.back()->ColumnWidth =
1004             EndColumnInFirstLine - Tokens.back()->OriginalColumn;
1005         // +1 for the ` itself.
1006         Tokens.back()->LastLineColumnWidth = EndOriginalColumn + 1;
1007         Tokens.back()->IsMultiline = true;
1008       } else {
1009         // Token simply spans from start to end, +1 for the ` itself.
1010         Tokens.back()->ColumnWidth =
1011             EndOriginalColumn - Tokens.back()->OriginalColumn + 1;
1012       }
1013       return true;
1014     }
1015     return false;
1016   }
1017 
1018   bool tryMerge_TMacro() {
1019     if (Tokens.size() < 4)
1020       return false;
1021     FormatToken *Last = Tokens.back();
1022     if (!Last->is(tok::r_paren))
1023       return false;
1024 
1025     FormatToken *String = Tokens[Tokens.size() - 2];
1026     if (!String->is(tok::string_literal) || String->IsMultiline)
1027       return false;
1028 
1029     if (!Tokens[Tokens.size() - 3]->is(tok::l_paren))
1030       return false;
1031 
1032     FormatToken *Macro = Tokens[Tokens.size() - 4];
1033     if (Macro->TokenText != "_T")
1034       return false;
1035 
1036     const char *Start = Macro->TokenText.data();
1037     const char *End = Last->TokenText.data() + Last->TokenText.size();
1038     String->TokenText = StringRef(Start, End - Start);
1039     String->IsFirst = Macro->IsFirst;
1040     String->LastNewlineOffset = Macro->LastNewlineOffset;
1041     String->WhitespaceRange = Macro->WhitespaceRange;
1042     String->OriginalColumn = Macro->OriginalColumn;
1043     String->ColumnWidth = encoding::columnWidthWithTabs(
1044         String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding);
1045     String->NewlinesBefore = Macro->NewlinesBefore;
1046     String->HasUnescapedNewline = Macro->HasUnescapedNewline;
1047 
1048     Tokens.pop_back();
1049     Tokens.pop_back();
1050     Tokens.pop_back();
1051     Tokens.back() = String;
1052     return true;
1053   }
1054 
1055   bool tryMergeConflictMarkers() {
1056     if (Tokens.back()->NewlinesBefore == 0 && Tokens.back()->isNot(tok::eof))
1057       return false;
1058 
1059     // Conflict lines look like:
1060     // <marker> <text from the vcs>
1061     // For example:
1062     // >>>>>>> /file/in/file/system at revision 1234
1063     //
1064     // We merge all tokens in a line that starts with a conflict marker
1065     // into a single token with a special token type that the unwrapped line
1066     // parser will use to correctly rebuild the underlying code.
1067 
1068     FileID ID;
1069     // Get the position of the first token in the line.
1070     unsigned FirstInLineOffset;
1071     std::tie(ID, FirstInLineOffset) = SourceMgr.getDecomposedLoc(
1072         Tokens[FirstInLineIndex]->getStartOfNonWhitespace());
1073     StringRef Buffer = SourceMgr.getBuffer(ID)->getBuffer();
1074     // Calculate the offset of the start of the current line.
1075     auto LineOffset = Buffer.rfind('\n', FirstInLineOffset);
1076     if (LineOffset == StringRef::npos) {
1077       LineOffset = 0;
1078     } else {
1079       ++LineOffset;
1080     }
1081 
1082     auto FirstSpace = Buffer.find_first_of(" \n", LineOffset);
1083     StringRef LineStart;
1084     if (FirstSpace == StringRef::npos) {
1085       LineStart = Buffer.substr(LineOffset);
1086     } else {
1087       LineStart = Buffer.substr(LineOffset, FirstSpace - LineOffset);
1088     }
1089 
1090     TokenType Type = TT_Unknown;
1091     if (LineStart == "<<<<<<<" || LineStart == ">>>>") {
1092       Type = TT_ConflictStart;
1093     } else if (LineStart == "|||||||" || LineStart == "=======" ||
1094                LineStart == "====") {
1095       Type = TT_ConflictAlternative;
1096     } else if (LineStart == ">>>>>>>" || LineStart == "<<<<") {
1097       Type = TT_ConflictEnd;
1098     }
1099 
1100     if (Type != TT_Unknown) {
1101       FormatToken *Next = Tokens.back();
1102 
1103       Tokens.resize(FirstInLineIndex + 1);
1104       // We do not need to build a complete token here, as we will skip it
1105       // during parsing anyway (as we must not touch whitespace around conflict
1106       // markers).
1107       Tokens.back()->Type = Type;
1108       Tokens.back()->Tok.setKind(tok::kw___unknown_anytype);
1109 
1110       Tokens.push_back(Next);
1111       return true;
1112     }
1113 
1114     return false;
1115   }
1116 
1117   FormatToken *getStashedToken() {
1118     // Create a synthesized second '>' or '<' token.
1119     Token Tok = FormatTok->Tok;
1120     StringRef TokenText = FormatTok->TokenText;
1121 
1122     unsigned OriginalColumn = FormatTok->OriginalColumn;
1123     FormatTok = new (Allocator.Allocate()) FormatToken;
1124     FormatTok->Tok = Tok;
1125     SourceLocation TokLocation =
1126         FormatTok->Tok.getLocation().getLocWithOffset(Tok.getLength() - 1);
1127     FormatTok->Tok.setLocation(TokLocation);
1128     FormatTok->WhitespaceRange = SourceRange(TokLocation, TokLocation);
1129     FormatTok->TokenText = TokenText;
1130     FormatTok->ColumnWidth = 1;
1131     FormatTok->OriginalColumn = OriginalColumn + 1;
1132 
1133     return FormatTok;
1134   }
1135 
1136   FormatToken *getNextToken() {
1137     if (GreaterStashed) {
1138       GreaterStashed = false;
1139       return getStashedToken();
1140     }
1141     if (LessStashed) {
1142       LessStashed = false;
1143       return getStashedToken();
1144     }
1145 
1146     FormatTok = new (Allocator.Allocate()) FormatToken;
1147     readRawToken(*FormatTok);
1148     SourceLocation WhitespaceStart =
1149         FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
1150     FormatTok->IsFirst = IsFirstToken;
1151     IsFirstToken = false;
1152 
1153     // Consume and record whitespace until we find a significant token.
1154     unsigned WhitespaceLength = TrailingWhitespace;
1155     while (FormatTok->Tok.is(tok::unknown)) {
1156       StringRef Text = FormatTok->TokenText;
1157       auto EscapesNewline = [&](int pos) {
1158         // A '\r' here is just part of '\r\n'. Skip it.
1159         if (pos >= 0 && Text[pos] == '\r')
1160           --pos;
1161         // See whether there is an odd number of '\' before this.
1162         unsigned count = 0;
1163         for (; pos >= 0; --pos, ++count)
1164           if (Text[pos] != '\\')
1165             break;
1166         return count & 1;
1167       };
1168       // FIXME: This miscounts tok:unknown tokens that are not just
1169       // whitespace, e.g. a '`' character.
1170       for (int i = 0, e = Text.size(); i != e; ++i) {
1171         switch (Text[i]) {
1172         case '\n':
1173           ++FormatTok->NewlinesBefore;
1174           FormatTok->HasUnescapedNewline = !EscapesNewline(i - 1);
1175           FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1176           Column = 0;
1177           break;
1178         case '\r':
1179           FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1180           Column = 0;
1181           break;
1182         case '\f':
1183         case '\v':
1184           Column = 0;
1185           break;
1186         case ' ':
1187           ++Column;
1188           break;
1189         case '\t':
1190           Column += Style.TabWidth - Column % Style.TabWidth;
1191           break;
1192         case '\\':
1193           if (i + 1 == e || (Text[i + 1] != '\r' && Text[i + 1] != '\n'))
1194             FormatTok->Type = TT_ImplicitStringLiteral;
1195           break;
1196         default:
1197           FormatTok->Type = TT_ImplicitStringLiteral;
1198           break;
1199         }
1200       }
1201 
1202       if (FormatTok->is(TT_ImplicitStringLiteral))
1203         break;
1204       WhitespaceLength += FormatTok->Tok.getLength();
1205 
1206       readRawToken(*FormatTok);
1207     }
1208 
1209     // In case the token starts with escaped newlines, we want to
1210     // take them into account as whitespace - this pattern is quite frequent
1211     // in macro definitions.
1212     // FIXME: Add a more explicit test.
1213     while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
1214            FormatTok->TokenText[1] == '\n') {
1215       ++FormatTok->NewlinesBefore;
1216       WhitespaceLength += 2;
1217       FormatTok->LastNewlineOffset = 2;
1218       Column = 0;
1219       FormatTok->TokenText = FormatTok->TokenText.substr(2);
1220     }
1221 
1222     FormatTok->WhitespaceRange = SourceRange(
1223         WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
1224 
1225     FormatTok->OriginalColumn = Column;
1226 
1227     TrailingWhitespace = 0;
1228     if (FormatTok->Tok.is(tok::comment)) {
1229       // FIXME: Add the trimmed whitespace to Column.
1230       StringRef UntrimmedText = FormatTok->TokenText;
1231       FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
1232       TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
1233     } else if (FormatTok->Tok.is(tok::raw_identifier)) {
1234       IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
1235       FormatTok->Tok.setIdentifierInfo(&Info);
1236       FormatTok->Tok.setKind(Info.getTokenID());
1237       if (Style.Language == FormatStyle::LK_Java &&
1238           FormatTok->isOneOf(tok::kw_struct, tok::kw_union, tok::kw_delete)) {
1239         FormatTok->Tok.setKind(tok::identifier);
1240         FormatTok->Tok.setIdentifierInfo(nullptr);
1241       }
1242     } else if (FormatTok->Tok.is(tok::greatergreater)) {
1243       FormatTok->Tok.setKind(tok::greater);
1244       FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1245       GreaterStashed = true;
1246     } else if (FormatTok->Tok.is(tok::lessless)) {
1247       FormatTok->Tok.setKind(tok::less);
1248       FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1249       LessStashed = true;
1250     }
1251 
1252     // Now FormatTok is the next non-whitespace token.
1253 
1254     StringRef Text = FormatTok->TokenText;
1255     size_t FirstNewlinePos = Text.find('\n');
1256     if (FirstNewlinePos == StringRef::npos) {
1257       // FIXME: ColumnWidth actually depends on the start column, we need to
1258       // take this into account when the token is moved.
1259       FormatTok->ColumnWidth =
1260           encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding);
1261       Column += FormatTok->ColumnWidth;
1262     } else {
1263       FormatTok->IsMultiline = true;
1264       // FIXME: ColumnWidth actually depends on the start column, we need to
1265       // take this into account when the token is moved.
1266       FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
1267           Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding);
1268 
1269       // The last line of the token always starts in column 0.
1270       // Thus, the length can be precomputed even in the presence of tabs.
1271       FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
1272           Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth,
1273           Encoding);
1274       Column = FormatTok->LastLineColumnWidth;
1275     }
1276 
1277     if (Style.Language == FormatStyle::LK_Cpp) {
1278       if (!(Tokens.size() > 0 && Tokens.back()->Tok.getIdentifierInfo() &&
1279             Tokens.back()->Tok.getIdentifierInfo()->getPPKeywordID() ==
1280                 tok::pp_define) &&
1281           std::find(ForEachMacros.begin(), ForEachMacros.end(),
1282                     FormatTok->Tok.getIdentifierInfo()) != ForEachMacros.end()) {
1283         FormatTok->Type = TT_ForEachMacro;
1284       } else if (FormatTok->is(tok::identifier)) {
1285         if (MacroBlockBeginRegex.match(Text)) {
1286           FormatTok->Type = TT_MacroBlockBegin;
1287         } else if (MacroBlockEndRegex.match(Text)) {
1288           FormatTok->Type = TT_MacroBlockEnd;
1289         }
1290       }
1291     }
1292 
1293     return FormatTok;
1294   }
1295 
1296   FormatToken *FormatTok;
1297   bool IsFirstToken;
1298   bool GreaterStashed, LessStashed;
1299   unsigned Column;
1300   unsigned TrailingWhitespace;
1301   std::unique_ptr<Lexer> Lex;
1302   SourceManager &SourceMgr;
1303   FileID ID;
1304   FormatStyle &Style;
1305   IdentifierTable IdentTable;
1306   AdditionalKeywords Keywords;
1307   encoding::Encoding Encoding;
1308   llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
1309   // Index (in 'Tokens') of the last token that starts a new line.
1310   unsigned FirstInLineIndex;
1311   SmallVector<FormatToken *, 16> Tokens;
1312   SmallVector<IdentifierInfo *, 8> ForEachMacros;
1313 
1314   bool FormattingDisabled;
1315 
1316   llvm::Regex MacroBlockBeginRegex;
1317   llvm::Regex MacroBlockEndRegex;
1318 
1319   void readRawToken(FormatToken &Tok) {
1320     Lex->LexFromRawLexer(Tok.Tok);
1321     Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
1322                               Tok.Tok.getLength());
1323     // For formatting, treat unterminated string literals like normal string
1324     // literals.
1325     if (Tok.is(tok::unknown)) {
1326       if (!Tok.TokenText.empty() && Tok.TokenText[0] == '"') {
1327         Tok.Tok.setKind(tok::string_literal);
1328         Tok.IsUnterminatedLiteral = true;
1329       } else if (Style.Language == FormatStyle::LK_JavaScript &&
1330                  Tok.TokenText == "''") {
1331         Tok.Tok.setKind(tok::char_constant);
1332       }
1333     }
1334 
1335     if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format on" ||
1336                                  Tok.TokenText == "/* clang-format on */")) {
1337       FormattingDisabled = false;
1338     }
1339 
1340     Tok.Finalized = FormattingDisabled;
1341 
1342     if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format off" ||
1343                                  Tok.TokenText == "/* clang-format off */")) {
1344       FormattingDisabled = true;
1345     }
1346   }
1347 
1348   void resetLexer(unsigned Offset) {
1349     StringRef Buffer = SourceMgr.getBufferData(ID);
1350     Lex.reset(new Lexer(SourceMgr.getLocForStartOfFile(ID),
1351                         getFormattingLangOpts(Style), Buffer.begin(),
1352                         Buffer.begin() + Offset, Buffer.end()));
1353     Lex->SetKeepWhitespaceMode(true);
1354     TrailingWhitespace = 0;
1355   }
1356 };
1357 
1358 static StringRef getLanguageName(FormatStyle::LanguageKind Language) {
1359   switch (Language) {
1360   case FormatStyle::LK_Cpp:
1361     return "C++";
1362   case FormatStyle::LK_Java:
1363     return "Java";
1364   case FormatStyle::LK_JavaScript:
1365     return "JavaScript";
1366   case FormatStyle::LK_Proto:
1367     return "Proto";
1368   default:
1369     return "Unknown";
1370   }
1371 }
1372 
1373 class Formatter : public UnwrappedLineConsumer {
1374 public:
1375   Formatter(const FormatStyle &Style, SourceManager &SourceMgr, FileID ID,
1376             ArrayRef<CharSourceRange> Ranges)
1377       : Style(Style), ID(ID), SourceMgr(SourceMgr),
1378         Whitespaces(SourceMgr, Style,
1379                     inputUsesCRLF(SourceMgr.getBufferData(ID))),
1380         Ranges(Ranges.begin(), Ranges.end()), UnwrappedLines(1),
1381         Encoding(encoding::detectEncoding(SourceMgr.getBufferData(ID))) {
1382     DEBUG(llvm::dbgs() << "File encoding: "
1383                        << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
1384                                                                : "unknown")
1385                        << "\n");
1386     DEBUG(llvm::dbgs() << "Language: " << getLanguageName(Style.Language)
1387                        << "\n");
1388   }
1389 
1390   tooling::Replacements format(bool *IncompleteFormat) {
1391     tooling::Replacements Result;
1392     FormatTokenLexer Tokens(SourceMgr, ID, Style, Encoding);
1393 
1394     UnwrappedLineParser Parser(Style, Tokens.getKeywords(), Tokens.lex(),
1395                                *this);
1396     Parser.parse();
1397     assert(UnwrappedLines.rbegin()->empty());
1398     for (unsigned Run = 0, RunE = UnwrappedLines.size(); Run + 1 != RunE;
1399          ++Run) {
1400       DEBUG(llvm::dbgs() << "Run " << Run << "...\n");
1401       SmallVector<AnnotatedLine *, 16> AnnotatedLines;
1402       for (unsigned i = 0, e = UnwrappedLines[Run].size(); i != e; ++i) {
1403         AnnotatedLines.push_back(new AnnotatedLine(UnwrappedLines[Run][i]));
1404       }
1405       tooling::Replacements RunResult =
1406           format(AnnotatedLines, Tokens, IncompleteFormat);
1407       DEBUG({
1408         llvm::dbgs() << "Replacements for run " << Run << ":\n";
1409         for (tooling::Replacements::iterator I = RunResult.begin(),
1410                                              E = RunResult.end();
1411              I != E; ++I) {
1412           llvm::dbgs() << I->toString() << "\n";
1413         }
1414       });
1415       for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1416         delete AnnotatedLines[i];
1417       }
1418       Result.insert(RunResult.begin(), RunResult.end());
1419       Whitespaces.reset();
1420     }
1421     return Result;
1422   }
1423 
1424   tooling::Replacements format(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1425                                FormatTokenLexer &Tokens,
1426                                bool *IncompleteFormat) {
1427     TokenAnnotator Annotator(Style, Tokens.getKeywords());
1428     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1429       Annotator.annotate(*AnnotatedLines[i]);
1430     }
1431     deriveLocalStyle(AnnotatedLines);
1432     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1433       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1434     }
1435     computeAffectedLines(AnnotatedLines.begin(), AnnotatedLines.end());
1436 
1437     Annotator.setCommentLineLevels(AnnotatedLines);
1438     ContinuationIndenter Indenter(Style, Tokens.getKeywords(), SourceMgr,
1439                                   Whitespaces, Encoding,
1440                                   BinPackInconclusiveFunctions);
1441     UnwrappedLineFormatter(&Indenter, &Whitespaces, Style, Tokens.getKeywords(),
1442                            IncompleteFormat)
1443         .format(AnnotatedLines);
1444     return Whitespaces.generateReplacements();
1445   }
1446 
1447 private:
1448   // Determines which lines are affected by the SourceRanges given as input.
1449   // Returns \c true if at least one line between I and E or one of their
1450   // children is affected.
1451   bool computeAffectedLines(SmallVectorImpl<AnnotatedLine *>::iterator I,
1452                             SmallVectorImpl<AnnotatedLine *>::iterator E) {
1453     bool SomeLineAffected = false;
1454     const AnnotatedLine *PreviousLine = nullptr;
1455     while (I != E) {
1456       AnnotatedLine *Line = *I;
1457       Line->LeadingEmptyLinesAffected = affectsLeadingEmptyLines(*Line->First);
1458 
1459       // If a line is part of a preprocessor directive, it needs to be formatted
1460       // if any token within the directive is affected.
1461       if (Line->InPPDirective) {
1462         FormatToken *Last = Line->Last;
1463         SmallVectorImpl<AnnotatedLine *>::iterator PPEnd = I + 1;
1464         while (PPEnd != E && !(*PPEnd)->First->HasUnescapedNewline) {
1465           Last = (*PPEnd)->Last;
1466           ++PPEnd;
1467         }
1468 
1469         if (affectsTokenRange(*Line->First, *Last,
1470                               /*IncludeLeadingNewlines=*/false)) {
1471           SomeLineAffected = true;
1472           markAllAsAffected(I, PPEnd);
1473         }
1474         I = PPEnd;
1475         continue;
1476       }
1477 
1478       if (nonPPLineAffected(Line, PreviousLine))
1479         SomeLineAffected = true;
1480 
1481       PreviousLine = Line;
1482       ++I;
1483     }
1484     return SomeLineAffected;
1485   }
1486 
1487   // Determines whether 'Line' is affected by the SourceRanges given as input.
1488   // Returns \c true if line or one if its children is affected.
1489   bool nonPPLineAffected(AnnotatedLine *Line,
1490                          const AnnotatedLine *PreviousLine) {
1491     bool SomeLineAffected = false;
1492     Line->ChildrenAffected =
1493         computeAffectedLines(Line->Children.begin(), Line->Children.end());
1494     if (Line->ChildrenAffected)
1495       SomeLineAffected = true;
1496 
1497     // Stores whether one of the line's tokens is directly affected.
1498     bool SomeTokenAffected = false;
1499     // Stores whether we need to look at the leading newlines of the next token
1500     // in order to determine whether it was affected.
1501     bool IncludeLeadingNewlines = false;
1502 
1503     // Stores whether the first child line of any of this line's tokens is
1504     // affected.
1505     bool SomeFirstChildAffected = false;
1506 
1507     for (FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
1508       // Determine whether 'Tok' was affected.
1509       if (affectsTokenRange(*Tok, *Tok, IncludeLeadingNewlines))
1510         SomeTokenAffected = true;
1511 
1512       // Determine whether the first child of 'Tok' was affected.
1513       if (!Tok->Children.empty() && Tok->Children.front()->Affected)
1514         SomeFirstChildAffected = true;
1515 
1516       IncludeLeadingNewlines = Tok->Children.empty();
1517     }
1518 
1519     // Was this line moved, i.e. has it previously been on the same line as an
1520     // affected line?
1521     bool LineMoved = PreviousLine && PreviousLine->Affected &&
1522                      Line->First->NewlinesBefore == 0;
1523 
1524     bool IsContinuedComment =
1525         Line->First->is(tok::comment) && Line->First->Next == nullptr &&
1526         Line->First->NewlinesBefore < 2 && PreviousLine &&
1527         PreviousLine->Affected && PreviousLine->Last->is(tok::comment);
1528 
1529     if (SomeTokenAffected || SomeFirstChildAffected || LineMoved ||
1530         IsContinuedComment) {
1531       Line->Affected = true;
1532       SomeLineAffected = true;
1533     }
1534     return SomeLineAffected;
1535   }
1536 
1537   // Marks all lines between I and E as well as all their children as affected.
1538   void markAllAsAffected(SmallVectorImpl<AnnotatedLine *>::iterator I,
1539                          SmallVectorImpl<AnnotatedLine *>::iterator E) {
1540     while (I != E) {
1541       (*I)->Affected = true;
1542       markAllAsAffected((*I)->Children.begin(), (*I)->Children.end());
1543       ++I;
1544     }
1545   }
1546 
1547   // Returns true if the range from 'First' to 'Last' intersects with one of the
1548   // input ranges.
1549   bool affectsTokenRange(const FormatToken &First, const FormatToken &Last,
1550                          bool IncludeLeadingNewlines) {
1551     SourceLocation Start = First.WhitespaceRange.getBegin();
1552     if (!IncludeLeadingNewlines)
1553       Start = Start.getLocWithOffset(First.LastNewlineOffset);
1554     SourceLocation End = Last.getStartOfNonWhitespace();
1555     End = End.getLocWithOffset(Last.TokenText.size());
1556     CharSourceRange Range = CharSourceRange::getCharRange(Start, End);
1557     return affectsCharSourceRange(Range);
1558   }
1559 
1560   // Returns true if one of the input ranges intersect the leading empty lines
1561   // before 'Tok'.
1562   bool affectsLeadingEmptyLines(const FormatToken &Tok) {
1563     CharSourceRange EmptyLineRange = CharSourceRange::getCharRange(
1564         Tok.WhitespaceRange.getBegin(),
1565         Tok.WhitespaceRange.getBegin().getLocWithOffset(Tok.LastNewlineOffset));
1566     return affectsCharSourceRange(EmptyLineRange);
1567   }
1568 
1569   // Returns true if 'Range' intersects with one of the input ranges.
1570   bool affectsCharSourceRange(const CharSourceRange &Range) {
1571     for (SmallVectorImpl<CharSourceRange>::const_iterator I = Ranges.begin(),
1572                                                           E = Ranges.end();
1573          I != E; ++I) {
1574       if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), I->getBegin()) &&
1575           !SourceMgr.isBeforeInTranslationUnit(I->getEnd(), Range.getBegin()))
1576         return true;
1577     }
1578     return false;
1579   }
1580 
1581   static bool inputUsesCRLF(StringRef Text) {
1582     return Text.count('\r') * 2 > Text.count('\n');
1583   }
1584 
1585   bool
1586   hasCpp03IncompatibleFormat(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1587     for (const AnnotatedLine* Line : Lines) {
1588       if (hasCpp03IncompatibleFormat(Line->Children))
1589         return true;
1590       for (FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next) {
1591         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
1592           if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
1593             return true;
1594           if (Tok->is(TT_TemplateCloser) &&
1595               Tok->Previous->is(TT_TemplateCloser))
1596             return true;
1597         }
1598       }
1599     }
1600     return false;
1601   }
1602 
1603   int countVariableAlignments(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1604     int AlignmentDiff = 0;
1605     for (const AnnotatedLine* Line : Lines) {
1606       AlignmentDiff += countVariableAlignments(Line->Children);
1607       for (FormatToken *Tok = Line->First; Tok && Tok->Next; Tok = Tok->Next) {
1608         if (!Tok->is(TT_PointerOrReference))
1609           continue;
1610         bool SpaceBefore =
1611             Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1612         bool SpaceAfter = Tok->Next->WhitespaceRange.getBegin() !=
1613                           Tok->Next->WhitespaceRange.getEnd();
1614         if (SpaceBefore && !SpaceAfter)
1615           ++AlignmentDiff;
1616         if (!SpaceBefore && SpaceAfter)
1617           --AlignmentDiff;
1618       }
1619     }
1620     return AlignmentDiff;
1621   }
1622 
1623   void
1624   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1625     bool HasBinPackedFunction = false;
1626     bool HasOnePerLineFunction = false;
1627     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1628       if (!AnnotatedLines[i]->First->Next)
1629         continue;
1630       FormatToken *Tok = AnnotatedLines[i]->First->Next;
1631       while (Tok->Next) {
1632         if (Tok->PackingKind == PPK_BinPacked)
1633           HasBinPackedFunction = true;
1634         if (Tok->PackingKind == PPK_OnePerLine)
1635           HasOnePerLineFunction = true;
1636 
1637         Tok = Tok->Next;
1638       }
1639     }
1640     if (Style.DerivePointerAlignment)
1641       Style.PointerAlignment = countVariableAlignments(AnnotatedLines) <= 0
1642                                    ? FormatStyle::PAS_Left
1643                                    : FormatStyle::PAS_Right;
1644     if (Style.Standard == FormatStyle::LS_Auto)
1645       Style.Standard = hasCpp03IncompatibleFormat(AnnotatedLines)
1646                            ? FormatStyle::LS_Cpp11
1647                            : FormatStyle::LS_Cpp03;
1648     BinPackInconclusiveFunctions =
1649         HasBinPackedFunction || !HasOnePerLineFunction;
1650   }
1651 
1652   void consumeUnwrappedLine(const UnwrappedLine &TheLine) override {
1653     assert(!UnwrappedLines.empty());
1654     UnwrappedLines.back().push_back(TheLine);
1655   }
1656 
1657   void finishRun() override {
1658     UnwrappedLines.push_back(SmallVector<UnwrappedLine, 16>());
1659   }
1660 
1661   FormatStyle Style;
1662   FileID ID;
1663   SourceManager &SourceMgr;
1664   WhitespaceManager Whitespaces;
1665   SmallVector<CharSourceRange, 8> Ranges;
1666   SmallVector<SmallVector<UnwrappedLine, 16>, 2> UnwrappedLines;
1667 
1668   encoding::Encoding Encoding;
1669   bool BinPackInconclusiveFunctions;
1670 };
1671 
1672 struct IncludeDirective {
1673   StringRef Filename;
1674   StringRef Text;
1675   unsigned Offset;
1676   unsigned Category;
1677 };
1678 
1679 } // end anonymous namespace
1680 
1681 // Determines whether 'Ranges' intersects with ('Start', 'End').
1682 static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
1683                          unsigned End) {
1684   for (auto Range : Ranges) {
1685     if (Range.getOffset() < End &&
1686         Range.getOffset() + Range.getLength() > Start)
1687       return true;
1688   }
1689   return false;
1690 }
1691 
1692 // Sorts a block of includes given by 'Includes' alphabetically adding the
1693 // necessary replacement to 'Replaces'. 'Includes' must be in strict source
1694 // order.
1695 static void sortIncludes(const FormatStyle &Style,
1696                          const SmallVectorImpl<IncludeDirective> &Includes,
1697                          ArrayRef<tooling::Range> Ranges, StringRef FileName,
1698                          tooling::Replacements &Replaces) {
1699   if (!affectsRange(Ranges, Includes.front().Offset,
1700                     Includes.back().Offset + Includes.back().Text.size()))
1701     return;
1702   SmallVector<unsigned, 16> Indices;
1703   for (unsigned i = 0, e = Includes.size(); i != e; ++i)
1704     Indices.push_back(i);
1705   std::sort(Indices.begin(), Indices.end(), [&](unsigned LHSI, unsigned RHSI) {
1706     return std::tie(Includes[LHSI].Category, Includes[LHSI].Filename) <
1707            std::tie(Includes[RHSI].Category, Includes[RHSI].Filename);
1708   });
1709 
1710   // If the #includes are out of order, we generate a single replacement fixing
1711   // the entire block. Otherwise, no replacement is generated.
1712   bool OutOfOrder = false;
1713   for (unsigned i = 1, e = Indices.size(); i != e; ++i) {
1714     if (Indices[i] != i) {
1715       OutOfOrder = true;
1716       break;
1717     }
1718   }
1719   if (!OutOfOrder)
1720     return;
1721 
1722   std::string result = Includes[Indices[0]].Text;
1723   for (unsigned i = 1, e = Indices.size(); i != e; ++i) {
1724     result += "\n";
1725     result += Includes[Indices[i]].Text;
1726   }
1727 
1728   // Sorting #includes shouldn't change their total number of characters.
1729   // This would otherwise mess up 'Ranges'.
1730   assert(result.size() ==
1731          Includes.back().Offset + Includes.back().Text.size() -
1732              Includes.front().Offset);
1733 
1734   Replaces.insert(tooling::Replacement(FileName, Includes.front().Offset,
1735                                        result.size(), result));
1736 }
1737 
1738 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
1739                                    ArrayRef<tooling::Range> Ranges,
1740                                    StringRef FileName) {
1741   tooling::Replacements Replaces;
1742   unsigned Prev = 0;
1743   unsigned SearchFrom = 0;
1744   llvm::Regex IncludeRegex(
1745       R"(^[\t\ ]*#[\t\ ]*include[^"<]*(["<][^">]*[">]))");
1746   SmallVector<StringRef, 4> Matches;
1747   SmallVector<IncludeDirective, 16> IncludesInBlock;
1748 
1749   // In compiled files, consider the first #include to be the main #include of
1750   // the file if it is not a system #include. This ensures that the header
1751   // doesn't have hidden dependencies
1752   // (http://llvm.org/docs/CodingStandards.html#include-style).
1753   //
1754   // FIXME: Do some sanity checking, e.g. edit distance of the base name, to fix
1755   // cases where the first #include is unlikely to be the main header.
1756   bool LookForMainHeader = FileName.endswith(".c") ||
1757                            FileName.endswith(".cc") ||
1758                            FileName.endswith(".cpp")||
1759                            FileName.endswith(".c++")||
1760                            FileName.endswith(".cxx");
1761 
1762   // Create pre-compiled regular expressions for the #include categories.
1763   SmallVector<llvm::Regex, 4> CategoryRegexs;
1764   for (const auto &Category : Style.IncludeCategories)
1765     CategoryRegexs.emplace_back(Category.Regex);
1766 
1767   for (;;) {
1768     auto Pos = Code.find('\n', SearchFrom);
1769     StringRef Line =
1770         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
1771     if (!Line.endswith("\\")) {
1772       if (IncludeRegex.match(Line, &Matches)) {
1773         unsigned Category;
1774         if (LookForMainHeader && !Matches[1].startswith("<")) {
1775           Category = 0;
1776         } else {
1777           Category = UINT_MAX;
1778           for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i) {
1779             if (CategoryRegexs[i].match(Matches[1])) {
1780               Category = Style.IncludeCategories[i].Priority;
1781               break;
1782             }
1783           }
1784         }
1785         LookForMainHeader = false;
1786         IncludesInBlock.push_back({Matches[1], Line, Prev, Category});
1787       } else if (!IncludesInBlock.empty()) {
1788         sortIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces);
1789         IncludesInBlock.clear();
1790       }
1791       Prev = Pos + 1;
1792     }
1793     if (Pos == StringRef::npos || Pos + 1 == Code.size())
1794       break;
1795     SearchFrom = Pos + 1;
1796   }
1797   if (!IncludesInBlock.empty())
1798     sortIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces);
1799   return Replaces;
1800 }
1801 
1802 tooling::Replacements reformat(const FormatStyle &Style,
1803                                SourceManager &SourceMgr, FileID ID,
1804                                ArrayRef<CharSourceRange> Ranges,
1805                                bool *IncompleteFormat) {
1806   FormatStyle Expanded = expandPresets(Style);
1807   if (Expanded.DisableFormat)
1808     return tooling::Replacements();
1809   Formatter formatter(Expanded, SourceMgr, ID, Ranges);
1810   return formatter.format(IncompleteFormat);
1811 }
1812 
1813 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1814                                ArrayRef<tooling::Range> Ranges,
1815                                StringRef FileName, bool *IncompleteFormat) {
1816   if (Style.DisableFormat)
1817     return tooling::Replacements();
1818 
1819   IntrusiveRefCntPtr<vfs::InMemoryFileSystem> InMemoryFileSystem(
1820       new vfs::InMemoryFileSystem);
1821   FileManager Files(FileSystemOptions(), InMemoryFileSystem);
1822   DiagnosticsEngine Diagnostics(
1823       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
1824       new DiagnosticOptions);
1825   SourceManager SourceMgr(Diagnostics, Files);
1826   InMemoryFileSystem->addFile(FileName, 0,
1827                               llvm::MemoryBuffer::getMemBuffer(Code, FileName));
1828   FileID ID = SourceMgr.createFileID(Files.getFile(FileName), SourceLocation(),
1829                                      clang::SrcMgr::C_User);
1830   SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
1831   std::vector<CharSourceRange> CharRanges;
1832   for (const tooling::Range &Range : Ranges) {
1833     SourceLocation Start = StartOfFile.getLocWithOffset(Range.getOffset());
1834     SourceLocation End = Start.getLocWithOffset(Range.getLength());
1835     CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
1836   }
1837   return reformat(Style, SourceMgr, ID, CharRanges, IncompleteFormat);
1838 }
1839 
1840 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
1841   LangOptions LangOpts;
1842   LangOpts.CPlusPlus = 1;
1843   LangOpts.CPlusPlus11 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1844   LangOpts.CPlusPlus14 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1845   LangOpts.LineComment = 1;
1846   bool AlternativeOperators = Style.Language == FormatStyle::LK_Cpp;
1847   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
1848   LangOpts.Bool = 1;
1849   LangOpts.ObjC1 = 1;
1850   LangOpts.ObjC2 = 1;
1851   LangOpts.MicrosoftExt = 1; // To get kw___try, kw___finally.
1852   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
1853   return LangOpts;
1854 }
1855 
1856 const char *StyleOptionHelpDescription =
1857     "Coding style, currently supports:\n"
1858     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
1859     "Use -style=file to load style configuration from\n"
1860     ".clang-format file located in one of the parent\n"
1861     "directories of the source file (or current\n"
1862     "directory for stdin).\n"
1863     "Use -style=\"{key: value, ...}\" to set specific\n"
1864     "parameters, e.g.:\n"
1865     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
1866 
1867 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
1868   if (FileName.endswith(".java")) {
1869     return FormatStyle::LK_Java;
1870   } else if (FileName.endswith_lower(".js") || FileName.endswith_lower(".ts")) {
1871     // JavaScript or TypeScript.
1872     return FormatStyle::LK_JavaScript;
1873   } else if (FileName.endswith_lower(".proto") ||
1874              FileName.endswith_lower(".protodevel")) {
1875     return FormatStyle::LK_Proto;
1876   }
1877   return FormatStyle::LK_Cpp;
1878 }
1879 
1880 FormatStyle getStyle(StringRef StyleName, StringRef FileName,
1881                      StringRef FallbackStyle) {
1882   FormatStyle Style = getLLVMStyle();
1883   Style.Language = getLanguageByFileName(FileName);
1884   if (!getPredefinedStyle(FallbackStyle, Style.Language, &Style)) {
1885     llvm::errs() << "Invalid fallback style \"" << FallbackStyle
1886                  << "\" using LLVM style\n";
1887     return Style;
1888   }
1889 
1890   if (StyleName.startswith("{")) {
1891     // Parse YAML/JSON style from the command line.
1892     if (std::error_code ec = parseConfiguration(StyleName, &Style)) {
1893       llvm::errs() << "Error parsing -style: " << ec.message() << ", using "
1894                    << FallbackStyle << " style\n";
1895     }
1896     return Style;
1897   }
1898 
1899   if (!StyleName.equals_lower("file")) {
1900     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
1901       llvm::errs() << "Invalid value for -style, using " << FallbackStyle
1902                    << " style\n";
1903     return Style;
1904   }
1905 
1906   // Look for .clang-format/_clang-format file in the file's parent directories.
1907   SmallString<128> UnsuitableConfigFiles;
1908   SmallString<128> Path(FileName);
1909   llvm::sys::fs::make_absolute(Path);
1910   for (StringRef Directory = Path; !Directory.empty();
1911        Directory = llvm::sys::path::parent_path(Directory)) {
1912     if (!llvm::sys::fs::is_directory(Directory))
1913       continue;
1914     SmallString<128> ConfigFile(Directory);
1915 
1916     llvm::sys::path::append(ConfigFile, ".clang-format");
1917     DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1918     bool IsFile = false;
1919     // Ignore errors from is_regular_file: we only need to know if we can read
1920     // the file or not.
1921     llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1922 
1923     if (!IsFile) {
1924       // Try _clang-format too, since dotfiles are not commonly used on Windows.
1925       ConfigFile = Directory;
1926       llvm::sys::path::append(ConfigFile, "_clang-format");
1927       DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1928       llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1929     }
1930 
1931     if (IsFile) {
1932       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
1933           llvm::MemoryBuffer::getFile(ConfigFile.c_str());
1934       if (std::error_code EC = Text.getError()) {
1935         llvm::errs() << EC.message() << "\n";
1936         break;
1937       }
1938       if (std::error_code ec =
1939               parseConfiguration(Text.get()->getBuffer(), &Style)) {
1940         if (ec == ParseError::Unsuitable) {
1941           if (!UnsuitableConfigFiles.empty())
1942             UnsuitableConfigFiles.append(", ");
1943           UnsuitableConfigFiles.append(ConfigFile);
1944           continue;
1945         }
1946         llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message()
1947                      << "\n";
1948         break;
1949       }
1950       DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
1951       return Style;
1952     }
1953   }
1954   if (!UnsuitableConfigFiles.empty()) {
1955     llvm::errs() << "Configuration file(s) do(es) not support "
1956                  << getLanguageName(Style.Language) << ": "
1957                  << UnsuitableConfigFiles << "\n";
1958   }
1959   return Style;
1960 }
1961 
1962 } // namespace format
1963 } // namespace clang
1964