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