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 "ContinuationIndenter.h"
17 #include "TokenAnnotator.h"
18 #include "UnwrappedLineParser.h"
19 #include "WhitespaceManager.h"
20 #include "clang/Basic/Diagnostic.h"
21 #include "clang/Basic/DiagnosticOptions.h"
22 #include "clang/Basic/SourceManager.h"
23 #include "clang/Format/Format.h"
24 #include "clang/Lex/Lexer.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/Support/Allocator.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Support/Path.h"
29 #include "llvm/Support/YAMLTraits.h"
30 #include <queue>
31 #include <string>
32 
33 #define DEBUG_TYPE "format-formatter"
34 
35 using clang::format::FormatStyle;
36 
37 LLVM_YAML_IS_FLOW_SEQUENCE_VECTOR(std::string)
38 
39 namespace llvm {
40 namespace yaml {
41 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
42   static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
43     IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
44     IO.enumCase(Value, "Java", FormatStyle::LK_Java);
45     IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
46     IO.enumCase(Value, "Proto", FormatStyle::LK_Proto);
47   }
48 };
49 
50 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
51   static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
52     IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03);
53     IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03);
54     IO.enumCase(Value, "Cpp11", FormatStyle::LS_Cpp11);
55     IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11);
56     IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
57   }
58 };
59 
60 template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
61   static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
62     IO.enumCase(Value, "Never", FormatStyle::UT_Never);
63     IO.enumCase(Value, "false", FormatStyle::UT_Never);
64     IO.enumCase(Value, "Always", FormatStyle::UT_Always);
65     IO.enumCase(Value, "true", FormatStyle::UT_Always);
66     IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
67   }
68 };
69 
70 template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
71   static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
72     IO.enumCase(Value, "None", FormatStyle::SFS_None);
73     IO.enumCase(Value, "false", FormatStyle::SFS_None);
74     IO.enumCase(Value, "All", FormatStyle::SFS_All);
75     IO.enumCase(Value, "true", FormatStyle::SFS_All);
76     IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
77   }
78 };
79 
80 template <> struct ScalarEnumerationTraits<FormatStyle::BinaryOperatorStyle> {
81   static void enumeration(IO &IO, FormatStyle::BinaryOperatorStyle &Value) {
82     IO.enumCase(Value, "All", FormatStyle::BOS_All);
83     IO.enumCase(Value, "true", FormatStyle::BOS_All);
84     IO.enumCase(Value, "None", FormatStyle::BOS_None);
85     IO.enumCase(Value, "false", FormatStyle::BOS_None);
86     IO.enumCase(Value, "NonAssignment", FormatStyle::BOS_NonAssignment);
87   }
88 };
89 
90 template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
91   static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
92     IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
93     IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
94     IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
95     IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
96     IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
97   }
98 };
99 
100 template <>
101 struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
102   static void enumeration(IO &IO,
103                           FormatStyle::NamespaceIndentationKind &Value) {
104     IO.enumCase(Value, "None", FormatStyle::NI_None);
105     IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
106     IO.enumCase(Value, "All", FormatStyle::NI_All);
107   }
108 };
109 
110 template <>
111 struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
112   static void enumeration(IO &IO,
113                           FormatStyle::PointerAlignmentStyle &Value) {
114     IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
115     IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
116     IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
117 
118     // For backward compatibility.
119     IO.enumCase(Value, "true", FormatStyle::PAS_Left);
120     IO.enumCase(Value, "false", FormatStyle::PAS_Right);
121   }
122 };
123 
124 template <>
125 struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
126   static void enumeration(IO &IO,
127                           FormatStyle::SpaceBeforeParensOptions &Value) {
128     IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
129     IO.enumCase(Value, "ControlStatements",
130                 FormatStyle::SBPO_ControlStatements);
131     IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
132 
133     // For backward compatibility.
134     IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
135     IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
136   }
137 };
138 
139 template <> struct MappingTraits<FormatStyle> {
140   static void mapping(IO &IO, FormatStyle &Style) {
141     // When reading, read the language first, we need it for getPredefinedStyle.
142     IO.mapOptional("Language", Style.Language);
143 
144     if (IO.outputting()) {
145       StringRef StylesArray[] = { "LLVM",    "Google", "Chromium",
146                                   "Mozilla", "WebKit", "GNU" };
147       ArrayRef<StringRef> Styles(StylesArray);
148       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
149         StringRef StyleName(Styles[i]);
150         FormatStyle PredefinedStyle;
151         if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
152             Style == PredefinedStyle) {
153           IO.mapOptional("# BasedOnStyle", StyleName);
154           break;
155         }
156       }
157     } else {
158       StringRef BasedOnStyle;
159       IO.mapOptional("BasedOnStyle", BasedOnStyle);
160       if (!BasedOnStyle.empty()) {
161         FormatStyle::LanguageKind OldLanguage = Style.Language;
162         FormatStyle::LanguageKind Language =
163             ((FormatStyle *)IO.getContext())->Language;
164         if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
165           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
166           return;
167         }
168         Style.Language = OldLanguage;
169       }
170     }
171 
172     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
173     IO.mapOptional("AlignAfterOpenBracket", Style.AlignAfterOpenBracket);
174     IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
175     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
176     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
177                    Style.AllowAllParametersOfDeclarationOnNextLine);
178     IO.mapOptional("AllowShortBlocksOnASingleLine",
179                    Style.AllowShortBlocksOnASingleLine);
180     IO.mapOptional("AllowShortCaseLabelsOnASingleLine",
181                    Style.AllowShortCaseLabelsOnASingleLine);
182     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
183                    Style.AllowShortIfStatementsOnASingleLine);
184     IO.mapOptional("AllowShortLoopsOnASingleLine",
185                    Style.AllowShortLoopsOnASingleLine);
186     IO.mapOptional("AllowShortFunctionsOnASingleLine",
187                    Style.AllowShortFunctionsOnASingleLine);
188     IO.mapOptional("AlwaysBreakAfterDefinitionReturnType",
189                    Style.AlwaysBreakAfterDefinitionReturnType);
190     IO.mapOptional("AlwaysBreakTemplateDeclarations",
191                    Style.AlwaysBreakTemplateDeclarations);
192     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
193                    Style.AlwaysBreakBeforeMultilineStrings);
194     IO.mapOptional("BreakBeforeBinaryOperators",
195                    Style.BreakBeforeBinaryOperators);
196     IO.mapOptional("BreakBeforeTernaryOperators",
197                    Style.BreakBeforeTernaryOperators);
198     IO.mapOptional("BreakConstructorInitializersBeforeComma",
199                    Style.BreakConstructorInitializersBeforeComma);
200     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
201     IO.mapOptional("BinPackArguments", Style.BinPackArguments);
202     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
203     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
204                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
205     IO.mapOptional("ConstructorInitializerIndentWidth",
206                    Style.ConstructorInitializerIndentWidth);
207     IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
208     IO.mapOptional("ExperimentalAutoDetectBinPacking",
209                    Style.ExperimentalAutoDetectBinPacking);
210     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
211     IO.mapOptional("IndentWrappedFunctionNames",
212                    Style.IndentWrappedFunctionNames);
213     IO.mapOptional("IndentFunctionDeclarationAfterType",
214                    Style.IndentWrappedFunctionNames);
215     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
216     IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
217                    Style.KeepEmptyLinesAtTheStartOfBlocks);
218     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
219     IO.mapOptional("ObjCBlockIndentWidth", Style.ObjCBlockIndentWidth);
220     IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
221     IO.mapOptional("ObjCSpaceBeforeProtocolList",
222                    Style.ObjCSpaceBeforeProtocolList);
223     IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
224                    Style.PenaltyBreakBeforeFirstCallParameter);
225     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
226     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
227     IO.mapOptional("PenaltyBreakFirstLessLess",
228                    Style.PenaltyBreakFirstLessLess);
229     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
230     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
231                    Style.PenaltyReturnTypeOnItsOwnLine);
232     IO.mapOptional("PointerAlignment", Style.PointerAlignment);
233     IO.mapOptional("SpacesBeforeTrailingComments",
234                    Style.SpacesBeforeTrailingComments);
235     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
236     IO.mapOptional("Standard", Style.Standard);
237     IO.mapOptional("IndentWidth", Style.IndentWidth);
238     IO.mapOptional("TabWidth", Style.TabWidth);
239     IO.mapOptional("UseTab", Style.UseTab);
240     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
241     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
242     IO.mapOptional("SpacesInSquareBrackets", Style.SpacesInSquareBrackets);
243     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
244     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
245     IO.mapOptional("SpacesInCStyleCastParentheses",
246                    Style.SpacesInCStyleCastParentheses);
247     IO.mapOptional("SpaceAfterCStyleCast", Style.SpaceAfterCStyleCast);
248     IO.mapOptional("SpacesInContainerLiterals",
249                    Style.SpacesInContainerLiterals);
250     IO.mapOptional("SpaceBeforeAssignmentOperators",
251                    Style.SpaceBeforeAssignmentOperators);
252     IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
253     IO.mapOptional("CommentPragmas", Style.CommentPragmas);
254     IO.mapOptional("ForEachMacros", Style.ForEachMacros);
255 
256     // For backward compatibility.
257     if (!IO.outputting()) {
258       IO.mapOptional("SpaceAfterControlStatementKeyword",
259                      Style.SpaceBeforeParens);
260       IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
261       IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
262     }
263     IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
264     IO.mapOptional("DisableFormat", Style.DisableFormat);
265   }
266 };
267 
268 // Allows to read vector<FormatStyle> while keeping default values.
269 // IO.getContext() should contain a pointer to the FormatStyle structure, that
270 // will be used to get default values for missing keys.
271 // If the first element has no Language specified, it will be treated as the
272 // default one for the following elements.
273 template <> struct DocumentListTraits<std::vector<FormatStyle> > {
274   static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
275     return Seq.size();
276   }
277   static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
278                               size_t Index) {
279     if (Index >= Seq.size()) {
280       assert(Index == Seq.size());
281       FormatStyle Template;
282       if (Seq.size() > 0 && Seq[0].Language == FormatStyle::LK_None) {
283         Template = Seq[0];
284       } else {
285         Template = *((const FormatStyle *)IO.getContext());
286         Template.Language = FormatStyle::LK_None;
287       }
288       Seq.resize(Index + 1, Template);
289     }
290     return Seq[Index];
291   }
292 };
293 }
294 }
295 
296 namespace clang {
297 namespace format {
298 
299 const std::error_category &getParseCategory() {
300   static ParseErrorCategory C;
301   return C;
302 }
303 std::error_code make_error_code(ParseError e) {
304   return std::error_code(static_cast<int>(e), getParseCategory());
305 }
306 
307 const char *ParseErrorCategory::name() const LLVM_NOEXCEPT {
308   return "clang-format.parse_error";
309 }
310 
311 std::string ParseErrorCategory::message(int EV) const {
312   switch (static_cast<ParseError>(EV)) {
313   case ParseError::Success:
314     return "Success";
315   case ParseError::Error:
316     return "Invalid argument";
317   case ParseError::Unsuitable:
318     return "Unsuitable";
319   }
320   llvm_unreachable("unexpected parse error");
321 }
322 
323 FormatStyle getLLVMStyle() {
324   FormatStyle LLVMStyle;
325   LLVMStyle.Language = FormatStyle::LK_Cpp;
326   LLVMStyle.AccessModifierOffset = -2;
327   LLVMStyle.AlignEscapedNewlinesLeft = false;
328   LLVMStyle.AlignAfterOpenBracket = true;
329   LLVMStyle.AlignTrailingComments = true;
330   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
331   LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
332   LLVMStyle.AllowShortBlocksOnASingleLine = false;
333   LLVMStyle.AllowShortCaseLabelsOnASingleLine = false;
334   LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
335   LLVMStyle.AllowShortLoopsOnASingleLine = false;
336   LLVMStyle.AlwaysBreakAfterDefinitionReturnType = false;
337   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
338   LLVMStyle.AlwaysBreakTemplateDeclarations = false;
339   LLVMStyle.BinPackParameters = true;
340   LLVMStyle.BinPackArguments = true;
341   LLVMStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_None;
342   LLVMStyle.BreakBeforeTernaryOperators = true;
343   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
344   LLVMStyle.BreakConstructorInitializersBeforeComma = false;
345   LLVMStyle.ColumnLimit = 80;
346   LLVMStyle.CommentPragmas = "^ IWYU pragma:";
347   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
348   LLVMStyle.ConstructorInitializerIndentWidth = 4;
349   LLVMStyle.ContinuationIndentWidth = 4;
350   LLVMStyle.Cpp11BracedListStyle = true;
351   LLVMStyle.DerivePointerAlignment = false;
352   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
353   LLVMStyle.ForEachMacros.push_back("foreach");
354   LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
355   LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
356   LLVMStyle.IndentCaseLabels = false;
357   LLVMStyle.IndentWrappedFunctionNames = false;
358   LLVMStyle.IndentWidth = 2;
359   LLVMStyle.TabWidth = 8;
360   LLVMStyle.MaxEmptyLinesToKeep = 1;
361   LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
362   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
363   LLVMStyle.ObjCBlockIndentWidth = 2;
364   LLVMStyle.ObjCSpaceAfterProperty = false;
365   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
366   LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
367   LLVMStyle.SpacesBeforeTrailingComments = 1;
368   LLVMStyle.Standard = FormatStyle::LS_Cpp11;
369   LLVMStyle.UseTab = FormatStyle::UT_Never;
370   LLVMStyle.SpacesInParentheses = false;
371   LLVMStyle.SpacesInSquareBrackets = false;
372   LLVMStyle.SpaceInEmptyParentheses = false;
373   LLVMStyle.SpacesInContainerLiterals = true;
374   LLVMStyle.SpacesInCStyleCastParentheses = false;
375   LLVMStyle.SpaceAfterCStyleCast = false;
376   LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
377   LLVMStyle.SpaceBeforeAssignmentOperators = true;
378   LLVMStyle.SpacesInAngles = false;
379 
380   LLVMStyle.PenaltyBreakComment = 300;
381   LLVMStyle.PenaltyBreakFirstLessLess = 120;
382   LLVMStyle.PenaltyBreakString = 1000;
383   LLVMStyle.PenaltyExcessCharacter = 1000000;
384   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
385   LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
386 
387   LLVMStyle.DisableFormat = false;
388 
389   return LLVMStyle;
390 }
391 
392 FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
393   FormatStyle GoogleStyle = getLLVMStyle();
394   GoogleStyle.Language = Language;
395 
396   GoogleStyle.AccessModifierOffset = -1;
397   GoogleStyle.AlignEscapedNewlinesLeft = true;
398   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
399   GoogleStyle.AllowShortLoopsOnASingleLine = true;
400   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
401   GoogleStyle.AlwaysBreakTemplateDeclarations = true;
402   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
403   GoogleStyle.DerivePointerAlignment = true;
404   GoogleStyle.IndentCaseLabels = true;
405   GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
406   GoogleStyle.ObjCSpaceAfterProperty = false;
407   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
408   GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
409   GoogleStyle.SpacesBeforeTrailingComments = 2;
410   GoogleStyle.Standard = FormatStyle::LS_Auto;
411 
412   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
413   GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
414 
415   if (Language == FormatStyle::LK_Java) {
416     GoogleStyle.AlignAfterOpenBracket = false;
417     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
418     GoogleStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_NonAssignment;
419     GoogleStyle.ColumnLimit = 100;
420     GoogleStyle.SpaceAfterCStyleCast = true;
421     GoogleStyle.SpacesBeforeTrailingComments = 1;
422   } else if (Language == FormatStyle::LK_JavaScript) {
423     GoogleStyle.BreakBeforeTernaryOperators = false;
424     GoogleStyle.MaxEmptyLinesToKeep = 3;
425     GoogleStyle.SpacesInContainerLiterals = false;
426     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
427   } else if (Language == FormatStyle::LK_Proto) {
428     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
429     GoogleStyle.SpacesInContainerLiterals = false;
430   }
431 
432   return GoogleStyle;
433 }
434 
435 FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
436   FormatStyle ChromiumStyle = getGoogleStyle(Language);
437   ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
438   ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
439   ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
440   ChromiumStyle.AllowShortLoopsOnASingleLine = false;
441   ChromiumStyle.BinPackParameters = false;
442   ChromiumStyle.DerivePointerAlignment = false;
443   return ChromiumStyle;
444 }
445 
446 FormatStyle getMozillaStyle() {
447   FormatStyle MozillaStyle = getLLVMStyle();
448   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
449   MozillaStyle.Cpp11BracedListStyle = false;
450   MozillaStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
451   MozillaStyle.DerivePointerAlignment = true;
452   MozillaStyle.IndentCaseLabels = true;
453   MozillaStyle.ObjCSpaceAfterProperty = true;
454   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
455   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
456   MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
457   MozillaStyle.Standard = FormatStyle::LS_Cpp03;
458   return MozillaStyle;
459 }
460 
461 FormatStyle getWebKitStyle() {
462   FormatStyle Style = getLLVMStyle();
463   Style.AccessModifierOffset = -4;
464   Style.AlignAfterOpenBracket = false;
465   Style.AlignTrailingComments = false;
466   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
467   Style.BreakBeforeBraces = FormatStyle::BS_Stroustrup;
468   Style.BreakConstructorInitializersBeforeComma = true;
469   Style.Cpp11BracedListStyle = false;
470   Style.ColumnLimit = 0;
471   Style.IndentWidth = 4;
472   Style.NamespaceIndentation = FormatStyle::NI_Inner;
473   Style.ObjCBlockIndentWidth = 4;
474   Style.ObjCSpaceAfterProperty = true;
475   Style.PointerAlignment = FormatStyle::PAS_Left;
476   Style.Standard = FormatStyle::LS_Cpp03;
477   return Style;
478 }
479 
480 FormatStyle getGNUStyle() {
481   FormatStyle Style = getLLVMStyle();
482   Style.AlwaysBreakAfterDefinitionReturnType = true;
483   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
484   Style.BreakBeforeBraces = FormatStyle::BS_GNU;
485   Style.BreakBeforeTernaryOperators = true;
486   Style.Cpp11BracedListStyle = false;
487   Style.ColumnLimit = 79;
488   Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
489   Style.Standard = FormatStyle::LS_Cpp03;
490   return Style;
491 }
492 
493 FormatStyle getNoStyle() {
494   FormatStyle NoStyle = getLLVMStyle();
495   NoStyle.DisableFormat = true;
496   return NoStyle;
497 }
498 
499 bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
500                         FormatStyle *Style) {
501   if (Name.equals_lower("llvm")) {
502     *Style = getLLVMStyle();
503   } else if (Name.equals_lower("chromium")) {
504     *Style = getChromiumStyle(Language);
505   } else if (Name.equals_lower("mozilla")) {
506     *Style = getMozillaStyle();
507   } else if (Name.equals_lower("google")) {
508     *Style = getGoogleStyle(Language);
509   } else if (Name.equals_lower("webkit")) {
510     *Style = getWebKitStyle();
511   } else if (Name.equals_lower("gnu")) {
512     *Style = getGNUStyle();
513   } else if (Name.equals_lower("none")) {
514     *Style = getNoStyle();
515   } else {
516     return false;
517   }
518 
519   Style->Language = Language;
520   return true;
521 }
522 
523 std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
524   assert(Style);
525   FormatStyle::LanguageKind Language = Style->Language;
526   assert(Language != FormatStyle::LK_None);
527   if (Text.trim().empty())
528     return make_error_code(ParseError::Error);
529 
530   std::vector<FormatStyle> Styles;
531   llvm::yaml::Input Input(Text);
532   // DocumentListTraits<vector<FormatStyle>> uses the context to get default
533   // values for the fields, keys for which are missing from the configuration.
534   // Mapping also uses the context to get the language to find the correct
535   // base style.
536   Input.setContext(Style);
537   Input >> Styles;
538   if (Input.error())
539     return Input.error();
540 
541   for (unsigned i = 0; i < Styles.size(); ++i) {
542     // Ensures that only the first configuration can skip the Language option.
543     if (Styles[i].Language == FormatStyle::LK_None && i != 0)
544       return make_error_code(ParseError::Error);
545     // Ensure that each language is configured at most once.
546     for (unsigned j = 0; j < i; ++j) {
547       if (Styles[i].Language == Styles[j].Language) {
548         DEBUG(llvm::dbgs()
549               << "Duplicate languages in the config file on positions " << j
550               << " and " << i << "\n");
551         return make_error_code(ParseError::Error);
552       }
553     }
554   }
555   // Look for a suitable configuration starting from the end, so we can
556   // find the configuration for the specific language first, and the default
557   // configuration (which can only be at slot 0) after it.
558   for (int i = Styles.size() - 1; i >= 0; --i) {
559     if (Styles[i].Language == Language ||
560         Styles[i].Language == FormatStyle::LK_None) {
561       *Style = Styles[i];
562       Style->Language = Language;
563       return make_error_code(ParseError::Success);
564     }
565   }
566   return make_error_code(ParseError::Unsuitable);
567 }
568 
569 std::string configurationAsText(const FormatStyle &Style) {
570   std::string Text;
571   llvm::raw_string_ostream Stream(Text);
572   llvm::yaml::Output Output(Stream);
573   // We use the same mapping method for input and output, so we need a non-const
574   // reference here.
575   FormatStyle NonConstStyle = Style;
576   Output << NonConstStyle;
577   return Stream.str();
578 }
579 
580 namespace {
581 
582 bool startsExternCBlock(const AnnotatedLine &Line) {
583   const FormatToken *Next = Line.First->getNextNonComment();
584   const FormatToken *NextNext = Next ? Next->getNextNonComment() : nullptr;
585   return Line.First->is(tok::kw_extern) && Next && Next->isStringLiteral() &&
586          NextNext && NextNext->is(tok::l_brace);
587 }
588 
589 class NoColumnLimitFormatter {
590 public:
591   NoColumnLimitFormatter(ContinuationIndenter *Indenter) : Indenter(Indenter) {}
592 
593   /// \brief Formats the line starting at \p State, simply keeping all of the
594   /// input's line breaking decisions.
595   void format(unsigned FirstIndent, const AnnotatedLine *Line) {
596     LineState State =
597         Indenter->getInitialState(FirstIndent, Line, /*DryRun=*/false);
598     while (State.NextToken) {
599       bool Newline =
600           Indenter->mustBreak(State) ||
601           (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
602       Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
603     }
604   }
605 
606 private:
607   ContinuationIndenter *Indenter;
608 };
609 
610 class LineJoiner {
611 public:
612   LineJoiner(const FormatStyle &Style) : Style(Style) {}
613 
614   /// \brief Calculates how many lines can be merged into 1 starting at \p I.
615   unsigned
616   tryFitMultipleLinesInOne(unsigned Indent,
617                            SmallVectorImpl<AnnotatedLine *>::const_iterator I,
618                            SmallVectorImpl<AnnotatedLine *>::const_iterator E) {
619     // We can never merge stuff if there are trailing line comments.
620     const AnnotatedLine *TheLine = *I;
621     if (TheLine->Last->Type == TT_LineComment)
622       return 0;
623 
624     if (Style.ColumnLimit > 0 && Indent > Style.ColumnLimit)
625       return 0;
626 
627     unsigned Limit =
628         Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent;
629     // If we already exceed the column limit, we set 'Limit' to 0. The different
630     // tryMerge..() functions can then decide whether to still do merging.
631     Limit = TheLine->Last->TotalLength > Limit
632                 ? 0
633                 : Limit - TheLine->Last->TotalLength;
634 
635     if (I + 1 == E || I[1]->Type == LT_Invalid || I[1]->First->MustBreakBefore)
636       return 0;
637 
638     // FIXME: TheLine->Level != 0 might or might not be the right check to do.
639     // If necessary, change to something smarter.
640     bool MergeShortFunctions =
641         Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_All ||
642         (Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_Inline &&
643          TheLine->Level != 0);
644 
645     if (TheLine->Last->Type == TT_FunctionLBrace &&
646         TheLine->First != TheLine->Last) {
647       return MergeShortFunctions ? tryMergeSimpleBlock(I, E, Limit) : 0;
648     }
649     if (TheLine->Last->is(tok::l_brace)) {
650       return Style.BreakBeforeBraces == FormatStyle::BS_Attach
651                  ? tryMergeSimpleBlock(I, E, Limit)
652                  : 0;
653     }
654     if (I[1]->First->Type == TT_FunctionLBrace &&
655         Style.BreakBeforeBraces != FormatStyle::BS_Attach) {
656       // Check for Limit <= 2 to account for the " {".
657       if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(TheLine)))
658         return 0;
659       Limit -= 2;
660 
661       unsigned MergedLines = 0;
662       if (MergeShortFunctions) {
663         MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
664         // If we managed to merge the block, count the function header, which is
665         // on a separate line.
666         if (MergedLines > 0)
667           ++MergedLines;
668       }
669       return MergedLines;
670     }
671     if (TheLine->First->is(tok::kw_if)) {
672       return Style.AllowShortIfStatementsOnASingleLine
673                  ? tryMergeSimpleControlStatement(I, E, Limit)
674                  : 0;
675     }
676     if (TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
677       return Style.AllowShortLoopsOnASingleLine
678                  ? tryMergeSimpleControlStatement(I, E, Limit)
679                  : 0;
680     }
681     if (TheLine->First->isOneOf(tok::kw_case, tok::kw_default)) {
682       return Style.AllowShortCaseLabelsOnASingleLine
683                  ? tryMergeShortCaseLabels(I, E, Limit)
684                  : 0;
685     }
686     if (TheLine->InPPDirective &&
687         (TheLine->First->HasUnescapedNewline || TheLine->First->IsFirst)) {
688       return tryMergeSimplePPDirective(I, E, Limit);
689     }
690     return 0;
691   }
692 
693 private:
694   unsigned
695   tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
696                             SmallVectorImpl<AnnotatedLine *>::const_iterator E,
697                             unsigned Limit) {
698     if (Limit == 0)
699       return 0;
700     if (!I[1]->InPPDirective || I[1]->First->HasUnescapedNewline)
701       return 0;
702     if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)
703       return 0;
704     if (1 + I[1]->Last->TotalLength > Limit)
705       return 0;
706     return 1;
707   }
708 
709   unsigned tryMergeSimpleControlStatement(
710       SmallVectorImpl<AnnotatedLine *>::const_iterator I,
711       SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
712     if (Limit == 0)
713       return 0;
714     if ((Style.BreakBeforeBraces == FormatStyle::BS_Allman ||
715          Style.BreakBeforeBraces == FormatStyle::BS_GNU) &&
716         (I[1]->First->is(tok::l_brace) && !Style.AllowShortBlocksOnASingleLine))
717       return 0;
718     if (I[1]->InPPDirective != (*I)->InPPDirective ||
719         (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline))
720       return 0;
721     Limit = limitConsideringMacros(I + 1, E, Limit);
722     AnnotatedLine &Line = **I;
723     if (Line.Last->isNot(tok::r_paren))
724       return 0;
725     if (1 + I[1]->Last->TotalLength > Limit)
726       return 0;
727     if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for,
728                              tok::kw_while) ||
729         I[1]->First->Type == TT_LineComment)
730       return 0;
731     // Only inline simple if's (no nested if or else).
732     if (I + 2 != E && Line.First->is(tok::kw_if) &&
733         I[2]->First->is(tok::kw_else))
734       return 0;
735     return 1;
736   }
737 
738   unsigned tryMergeShortCaseLabels(
739       SmallVectorImpl<AnnotatedLine *>::const_iterator I,
740       SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
741     if (Limit == 0 || I + 1 == E ||
742         I[1]->First->isOneOf(tok::kw_case, tok::kw_default))
743       return 0;
744     unsigned NumStmts = 0;
745     unsigned Length = 0;
746     for (; NumStmts < 3; ++NumStmts) {
747       if (I + 1 + NumStmts == E)
748         break;
749       const AnnotatedLine *Line = I[1 + NumStmts];
750       if (Line->First->isOneOf(tok::kw_case, tok::kw_default, tok::r_brace))
751         break;
752       if (Line->First->isOneOf(tok::kw_if, tok::kw_for, tok::kw_switch,
753                                tok::kw_while))
754         return 0;
755       Length += I[1 + NumStmts]->Last->TotalLength + 1; // 1 for the space.
756     }
757     if (NumStmts == 0 || NumStmts == 3 || Length > Limit)
758       return 0;
759     return NumStmts;
760   }
761 
762   unsigned
763   tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
764                       SmallVectorImpl<AnnotatedLine *>::const_iterator E,
765                       unsigned Limit) {
766     AnnotatedLine &Line = **I;
767 
768     // Don't merge ObjC @ keywords and methods.
769     if (Line.First->isOneOf(tok::at, tok::minus, tok::plus))
770       return 0;
771 
772     // Check that the current line allows merging. This depends on whether we
773     // are in a control flow statements as well as several style flags.
774     if (Line.First->isOneOf(tok::kw_else, tok::kw_case))
775       return 0;
776     if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::kw_try,
777                             tok::kw_catch, tok::kw_for, tok::r_brace)) {
778       if (!Style.AllowShortBlocksOnASingleLine)
779         return 0;
780       if (!Style.AllowShortIfStatementsOnASingleLine &&
781           Line.First->is(tok::kw_if))
782         return 0;
783       if (!Style.AllowShortLoopsOnASingleLine &&
784           Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for))
785         return 0;
786       // FIXME: Consider an option to allow short exception handling clauses on
787       // a single line.
788       if (Line.First->isOneOf(tok::kw_try, tok::kw_catch))
789         return 0;
790     }
791 
792     FormatToken *Tok = I[1]->First;
793     if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
794         (Tok->getNextNonComment() == nullptr ||
795          Tok->getNextNonComment()->is(tok::semi))) {
796       // We merge empty blocks even if the line exceeds the column limit.
797       Tok->SpacesRequiredBefore = 0;
798       Tok->CanBreakBefore = true;
799       return 1;
800     } else if (Limit != 0 && Line.First->isNot(tok::kw_namespace) &&
801                !startsExternCBlock(Line)) {
802       // We don't merge short records.
803       if (Line.First->isOneOf(tok::kw_class, tok::kw_union, tok::kw_struct))
804         return 0;
805 
806       // Check that we still have three lines and they fit into the limit.
807       if (I + 2 == E || I[2]->Type == LT_Invalid)
808         return 0;
809       Limit = limitConsideringMacros(I + 2, E, Limit);
810 
811       if (!nextTwoLinesFitInto(I, Limit))
812         return 0;
813 
814       // Second, check that the next line does not contain any braces - if it
815       // does, readability declines when putting it into a single line.
816       if (I[1]->Last->Type == TT_LineComment)
817         return 0;
818       do {
819         if (Tok->is(tok::l_brace) && Tok->BlockKind != BK_BracedInit)
820           return 0;
821         Tok = Tok->Next;
822       } while (Tok);
823 
824       // Last, check that the third line starts with a closing brace.
825       Tok = I[2]->First;
826       if (Tok->isNot(tok::r_brace))
827         return 0;
828 
829       return 2;
830     }
831     return 0;
832   }
833 
834   /// Returns the modified column limit for \p I if it is inside a macro and
835   /// needs a trailing '\'.
836   unsigned
837   limitConsideringMacros(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
838                          SmallVectorImpl<AnnotatedLine *>::const_iterator E,
839                          unsigned Limit) {
840     if (I[0]->InPPDirective && I + 1 != E &&
841         !I[1]->First->HasUnescapedNewline && !I[1]->First->is(tok::eof)) {
842       return Limit < 2 ? 0 : Limit - 2;
843     }
844     return Limit;
845   }
846 
847   bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
848                            unsigned Limit) {
849     if (I[1]->First->MustBreakBefore || I[2]->First->MustBreakBefore)
850       return false;
851     return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;
852   }
853 
854   bool containsMustBreak(const AnnotatedLine *Line) {
855     for (const FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
856       if (Tok->MustBreakBefore)
857         return true;
858     }
859     return false;
860   }
861 
862   const FormatStyle &Style;
863 };
864 
865 class UnwrappedLineFormatter {
866 public:
867   UnwrappedLineFormatter(ContinuationIndenter *Indenter,
868                          WhitespaceManager *Whitespaces,
869                          const FormatStyle &Style)
870       : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style),
871         Joiner(Style) {}
872 
873   unsigned format(const SmallVectorImpl<AnnotatedLine *> &Lines, bool DryRun,
874                   int AdditionalIndent = 0, bool FixBadIndentation = false) {
875     // Try to look up already computed penalty in DryRun-mode.
876     std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned> CacheKey(
877         &Lines, AdditionalIndent);
878     auto CacheIt = PenaltyCache.find(CacheKey);
879     if (DryRun && CacheIt != PenaltyCache.end())
880       return CacheIt->second;
881 
882     assert(!Lines.empty());
883     unsigned Penalty = 0;
884     std::vector<int> IndentForLevel;
885     for (unsigned i = 0, e = Lines[0]->Level; i != e; ++i)
886       IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent);
887     const AnnotatedLine *PreviousLine = nullptr;
888     for (SmallVectorImpl<AnnotatedLine *>::const_iterator I = Lines.begin(),
889                                                           E = Lines.end();
890          I != E; ++I) {
891       const AnnotatedLine &TheLine = **I;
892       const FormatToken *FirstTok = TheLine.First;
893       int Offset = getIndentOffset(*FirstTok);
894 
895       // Determine indent and try to merge multiple unwrapped lines.
896       unsigned Indent;
897       if (TheLine.InPPDirective) {
898         Indent = TheLine.Level * Style.IndentWidth;
899       } else {
900         while (IndentForLevel.size() <= TheLine.Level)
901           IndentForLevel.push_back(-1);
902         IndentForLevel.resize(TheLine.Level + 1);
903         Indent = getIndent(IndentForLevel, TheLine.Level);
904       }
905       unsigned LevelIndent = Indent;
906       if (static_cast<int>(Indent) + Offset >= 0)
907         Indent += Offset;
908 
909       // Merge multiple lines if possible.
910       unsigned MergedLines = Joiner.tryFitMultipleLinesInOne(Indent, I, E);
911       if (MergedLines > 0 && Style.ColumnLimit == 0) {
912         // Disallow line merging if there is a break at the start of one of the
913         // input lines.
914         for (unsigned i = 0; i < MergedLines; ++i) {
915           if (I[i + 1]->First->NewlinesBefore > 0)
916             MergedLines = 0;
917         }
918       }
919       if (!DryRun) {
920         for (unsigned i = 0; i < MergedLines; ++i) {
921           join(*I[i], *I[i + 1]);
922         }
923       }
924       I += MergedLines;
925 
926       bool FixIndentation =
927           FixBadIndentation && (LevelIndent != FirstTok->OriginalColumn);
928       if (TheLine.First->is(tok::eof)) {
929         if (PreviousLine && PreviousLine->Affected && !DryRun) {
930           // Remove the file's trailing whitespace.
931           unsigned Newlines = std::min(FirstTok->NewlinesBefore, 1u);
932           Whitespaces->replaceWhitespace(*TheLine.First, Newlines,
933                                          /*IndentLevel=*/0, /*Spaces=*/0,
934                                          /*TargetColumn=*/0);
935         }
936       } else if (TheLine.Type != LT_Invalid &&
937                  (TheLine.Affected || FixIndentation)) {
938         if (FirstTok->WhitespaceRange.isValid()) {
939           if (!DryRun)
940             formatFirstToken(*TheLine.First, PreviousLine, TheLine.Level,
941                              Indent, TheLine.InPPDirective);
942         } else {
943           Indent = LevelIndent = FirstTok->OriginalColumn;
944         }
945 
946         // If everything fits on a single line, just put it there.
947         unsigned ColumnLimit = Style.ColumnLimit;
948         if (I + 1 != E) {
949           AnnotatedLine *NextLine = I[1];
950           if (NextLine->InPPDirective && !NextLine->First->HasUnescapedNewline)
951             ColumnLimit = getColumnLimit(TheLine.InPPDirective);
952         }
953 
954         if (TheLine.Last->TotalLength + Indent <= ColumnLimit) {
955           LineState State = Indenter->getInitialState(Indent, &TheLine, DryRun);
956           while (State.NextToken) {
957             formatChildren(State, /*Newline=*/false, /*DryRun=*/false, Penalty);
958             Indenter->addTokenToState(State, /*Newline=*/false, DryRun);
959           }
960         } else if (Style.ColumnLimit == 0) {
961           // FIXME: Implement nested blocks for ColumnLimit = 0.
962           NoColumnLimitFormatter Formatter(Indenter);
963           if (!DryRun)
964             Formatter.format(Indent, &TheLine);
965         } else {
966           Penalty += format(TheLine, Indent, DryRun);
967         }
968 
969         if (!TheLine.InPPDirective)
970           IndentForLevel[TheLine.Level] = LevelIndent;
971       } else if (TheLine.ChildrenAffected) {
972         format(TheLine.Children, DryRun);
973       } else {
974         // Format the first token if necessary, and notify the WhitespaceManager
975         // about the unchanged whitespace.
976         for (FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next) {
977           if (Tok == TheLine.First &&
978               (Tok->NewlinesBefore > 0 || Tok->IsFirst)) {
979             unsigned LevelIndent = Tok->OriginalColumn;
980             if (!DryRun) {
981               // Remove trailing whitespace of the previous line.
982               if ((PreviousLine && PreviousLine->Affected) ||
983                   TheLine.LeadingEmptyLinesAffected) {
984                 formatFirstToken(*Tok, PreviousLine, TheLine.Level, LevelIndent,
985                                  TheLine.InPPDirective);
986               } else {
987                 Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
988               }
989             }
990 
991             if (static_cast<int>(LevelIndent) - Offset >= 0)
992               LevelIndent -= Offset;
993             if (Tok->isNot(tok::comment) && !TheLine.InPPDirective)
994               IndentForLevel[TheLine.Level] = LevelIndent;
995           } else if (!DryRun) {
996             Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
997           }
998         }
999       }
1000       if (!DryRun) {
1001         for (FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next) {
1002           Tok->Finalized = true;
1003         }
1004       }
1005       PreviousLine = *I;
1006     }
1007     PenaltyCache[CacheKey] = Penalty;
1008     return Penalty;
1009   }
1010 
1011 private:
1012   /// \brief Formats an \c AnnotatedLine and returns the penalty.
1013   ///
1014   /// If \p DryRun is \c false, directly applies the changes.
1015   unsigned format(const AnnotatedLine &Line, unsigned FirstIndent,
1016                   bool DryRun) {
1017     LineState State = Indenter->getInitialState(FirstIndent, &Line, DryRun);
1018 
1019     // If the ObjC method declaration does not fit on a line, we should format
1020     // it with one arg per line.
1021     if (State.Line->Type == LT_ObjCMethodDecl)
1022       State.Stack.back().BreakBeforeParameter = true;
1023 
1024     // Find best solution in solution space.
1025     return analyzeSolutionSpace(State, DryRun);
1026   }
1027 
1028   /// \brief An edge in the solution space from \c Previous->State to \c State,
1029   /// inserting a newline dependent on the \c NewLine.
1030   struct StateNode {
1031     StateNode(const LineState &State, bool NewLine, StateNode *Previous)
1032         : State(State), NewLine(NewLine), Previous(Previous) {}
1033     LineState State;
1034     bool NewLine;
1035     StateNode *Previous;
1036   };
1037 
1038   /// \brief A pair of <penalty, count> that is used to prioritize the BFS on.
1039   ///
1040   /// In case of equal penalties, we want to prefer states that were inserted
1041   /// first. During state generation we make sure that we insert states first
1042   /// that break the line as late as possible.
1043   typedef std::pair<unsigned, unsigned> OrderedPenalty;
1044 
1045   /// \brief An item in the prioritized BFS search queue. The \c StateNode's
1046   /// \c State has the given \c OrderedPenalty.
1047   typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
1048 
1049   /// \brief The BFS queue type.
1050   typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
1051                               std::greater<QueueItem> > QueueType;
1052 
1053   /// \brief Get the offset of the line relatively to the level.
1054   ///
1055   /// For example, 'public:' labels in classes are offset by 1 or 2
1056   /// characters to the left from their level.
1057   int getIndentOffset(const FormatToken &RootToken) {
1058     if (Style.Language == FormatStyle::LK_Java)
1059       return 0;
1060     if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier())
1061       return Style.AccessModifierOffset;
1062     return 0;
1063   }
1064 
1065   /// \brief Add a new line and the required indent before the first Token
1066   /// of the \c UnwrappedLine if there was no structural parsing error.
1067   void formatFirstToken(FormatToken &RootToken,
1068                         const AnnotatedLine *PreviousLine, unsigned IndentLevel,
1069                         unsigned Indent, bool InPPDirective) {
1070     unsigned Newlines =
1071         std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
1072     // Remove empty lines before "}" where applicable.
1073     if (RootToken.is(tok::r_brace) &&
1074         (!RootToken.Next ||
1075          (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)))
1076       Newlines = std::min(Newlines, 1u);
1077     if (Newlines == 0 && !RootToken.IsFirst)
1078       Newlines = 1;
1079     if (RootToken.IsFirst && !RootToken.HasUnescapedNewline)
1080       Newlines = 0;
1081 
1082     // Remove empty lines after "{".
1083     if (!Style.KeepEmptyLinesAtTheStartOfBlocks && PreviousLine &&
1084         PreviousLine->Last->is(tok::l_brace) &&
1085         PreviousLine->First->isNot(tok::kw_namespace) &&
1086         !startsExternCBlock(*PreviousLine))
1087       Newlines = 1;
1088 
1089     // Insert extra new line before access specifiers.
1090     if (PreviousLine && PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) &&
1091         RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
1092       ++Newlines;
1093 
1094     // Remove empty lines after access specifiers.
1095     if (PreviousLine && PreviousLine->First->isAccessSpecifier())
1096       Newlines = std::min(1u, Newlines);
1097 
1098     Whitespaces->replaceWhitespace(RootToken, Newlines, IndentLevel, Indent,
1099                                    Indent, InPPDirective &&
1100                                                !RootToken.HasUnescapedNewline);
1101   }
1102 
1103   /// \brief Get the indent of \p Level from \p IndentForLevel.
1104   ///
1105   /// \p IndentForLevel must contain the indent for the level \c l
1106   /// at \p IndentForLevel[l], or a value < 0 if the indent for
1107   /// that level is unknown.
1108   unsigned getIndent(ArrayRef<int> IndentForLevel, unsigned Level) {
1109     if (IndentForLevel[Level] != -1)
1110       return IndentForLevel[Level];
1111     if (Level == 0)
1112       return 0;
1113     return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth;
1114   }
1115 
1116   void join(AnnotatedLine &A, const AnnotatedLine &B) {
1117     assert(!A.Last->Next);
1118     assert(!B.First->Previous);
1119     if (B.Affected)
1120       A.Affected = true;
1121     A.Last->Next = B.First;
1122     B.First->Previous = A.Last;
1123     B.First->CanBreakBefore = true;
1124     unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
1125     for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
1126       Tok->TotalLength += LengthA;
1127       A.Last = Tok;
1128     }
1129   }
1130 
1131   unsigned getColumnLimit(bool InPPDirective) const {
1132     // In preprocessor directives reserve two chars for trailing " \"
1133     return Style.ColumnLimit - (InPPDirective ? 2 : 0);
1134   }
1135 
1136   struct CompareLineStatePointers {
1137     bool operator()(LineState *obj1, LineState *obj2) const {
1138       return *obj1 < *obj2;
1139     }
1140   };
1141 
1142   /// \brief Analyze the entire solution space starting from \p InitialState.
1143   ///
1144   /// This implements a variant of Dijkstra's algorithm on the graph that spans
1145   /// the solution space (\c LineStates are the nodes). The algorithm tries to
1146   /// find the shortest path (the one with lowest penalty) from \p InitialState
1147   /// to a state where all tokens are placed. Returns the penalty.
1148   ///
1149   /// If \p DryRun is \c false, directly applies the changes.
1150   unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun = false) {
1151     std::set<LineState *, CompareLineStatePointers> Seen;
1152 
1153     // Increasing count of \c StateNode items we have created. This is used to
1154     // create a deterministic order independent of the container.
1155     unsigned Count = 0;
1156     QueueType Queue;
1157 
1158     // Insert start element into queue.
1159     StateNode *Node =
1160         new (Allocator.Allocate()) StateNode(InitialState, false, nullptr);
1161     Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
1162     ++Count;
1163 
1164     unsigned Penalty = 0;
1165 
1166     // While not empty, take first element and follow edges.
1167     while (!Queue.empty()) {
1168       Penalty = Queue.top().first.first;
1169       StateNode *Node = Queue.top().second;
1170       if (!Node->State.NextToken) {
1171         DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n");
1172         break;
1173       }
1174       Queue.pop();
1175 
1176       // Cut off the analysis of certain solutions if the analysis gets too
1177       // complex. See description of IgnoreStackForComparison.
1178       if (Count > 10000)
1179         Node->State.IgnoreStackForComparison = true;
1180 
1181       if (!Seen.insert(&Node->State).second)
1182         // State already examined with lower penalty.
1183         continue;
1184 
1185       FormatDecision LastFormat = Node->State.NextToken->Decision;
1186       if (LastFormat == FD_Unformatted || LastFormat == FD_Continue)
1187         addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue);
1188       if (LastFormat == FD_Unformatted || LastFormat == FD_Break)
1189         addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue);
1190     }
1191 
1192     if (Queue.empty()) {
1193       // We were unable to find a solution, do nothing.
1194       // FIXME: Add diagnostic?
1195       DEBUG(llvm::dbgs() << "Could not find a solution.\n");
1196       return 0;
1197     }
1198 
1199     // Reconstruct the solution.
1200     if (!DryRun)
1201       reconstructPath(InitialState, Queue.top().second);
1202 
1203     DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n");
1204     DEBUG(llvm::dbgs() << "---\n");
1205 
1206     return Penalty;
1207   }
1208 
1209   void reconstructPath(LineState &State, StateNode *Current) {
1210     std::deque<StateNode *> Path;
1211     // We do not need a break before the initial token.
1212     while (Current->Previous) {
1213       Path.push_front(Current);
1214       Current = Current->Previous;
1215     }
1216     for (std::deque<StateNode *>::iterator I = Path.begin(), E = Path.end();
1217          I != E; ++I) {
1218       unsigned Penalty = 0;
1219       formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
1220       Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
1221 
1222       DEBUG({
1223         if ((*I)->NewLine) {
1224           llvm::dbgs() << "Penalty for placing "
1225                        << (*I)->Previous->State.NextToken->Tok.getName() << ": "
1226                        << Penalty << "\n";
1227         }
1228       });
1229     }
1230   }
1231 
1232   /// \brief Add the following state to the analysis queue \c Queue.
1233   ///
1234   /// Assume the current state is \p PreviousNode and has been reached with a
1235   /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
1236   void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
1237                            bool NewLine, unsigned *Count, QueueType *Queue) {
1238     if (NewLine && !Indenter->canBreak(PreviousNode->State))
1239       return;
1240     if (!NewLine && Indenter->mustBreak(PreviousNode->State))
1241       return;
1242 
1243     StateNode *Node = new (Allocator.Allocate())
1244         StateNode(PreviousNode->State, NewLine, PreviousNode);
1245     if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
1246       return;
1247 
1248     Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
1249 
1250     Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node));
1251     ++(*Count);
1252   }
1253 
1254   /// \brief If the \p State's next token is an r_brace closing a nested block,
1255   /// format the nested block before it.
1256   ///
1257   /// Returns \c true if all children could be placed successfully and adapts
1258   /// \p Penalty as well as \p State. If \p DryRun is false, also directly
1259   /// creates changes using \c Whitespaces.
1260   ///
1261   /// The crucial idea here is that children always get formatted upon
1262   /// encountering the closing brace right after the nested block. Now, if we
1263   /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is
1264   /// \c false), the entire block has to be kept on the same line (which is only
1265   /// possible if it fits on the line, only contains a single statement, etc.
1266   ///
1267   /// If \p NewLine is true, we format the nested block on separate lines, i.e.
1268   /// break after the "{", format all lines with correct indentation and the put
1269   /// the closing "}" on yet another new line.
1270   ///
1271   /// This enables us to keep the simple structure of the
1272   /// \c UnwrappedLineFormatter, where we only have two options for each token:
1273   /// break or don't break.
1274   bool formatChildren(LineState &State, bool NewLine, bool DryRun,
1275                       unsigned &Penalty) {
1276     FormatToken &Previous = *State.NextToken->Previous;
1277     const FormatToken *LBrace = State.NextToken->getPreviousNonComment();
1278     if (!LBrace || LBrace->isNot(tok::l_brace) ||
1279         LBrace->BlockKind != BK_Block || Previous.Children.size() == 0)
1280       // The previous token does not open a block. Nothing to do. We don't
1281       // assert so that we can simply call this function for all tokens.
1282       return true;
1283 
1284     if (NewLine) {
1285       int AdditionalIndent =
1286           State.FirstIndent - State.Line->Level * Style.IndentWidth;
1287       if (State.Stack.size() < 2 ||
1288           !State.Stack[State.Stack.size() - 2].JSFunctionInlined) {
1289         AdditionalIndent = State.Stack.back().Indent -
1290                            Previous.Children[0]->Level * Style.IndentWidth;
1291       }
1292 
1293       Penalty += format(Previous.Children, DryRun, AdditionalIndent,
1294                         /*FixBadIndentation=*/true);
1295       return true;
1296     }
1297 
1298     if (Previous.Children[0]->First->MustBreakBefore)
1299       return false;
1300 
1301     // Cannot merge multiple statements into a single line.
1302     if (Previous.Children.size() > 1)
1303       return false;
1304 
1305     // Cannot merge into one line if this line ends on a comment.
1306     if (Previous.is(tok::comment))
1307       return false;
1308 
1309     // We can't put the closing "}" on a line with a trailing comment.
1310     if (Previous.Children[0]->Last->isTrailingComment())
1311       return false;
1312 
1313     // If the child line exceeds the column limit, we wouldn't want to merge it.
1314     // We add +2 for the trailing " }".
1315     if (Style.ColumnLimit > 0 &&
1316         Previous.Children[0]->Last->TotalLength + State.Column + 2 >
1317             Style.ColumnLimit)
1318       return false;
1319 
1320     if (!DryRun) {
1321       Whitespaces->replaceWhitespace(
1322           *Previous.Children[0]->First,
1323           /*Newlines=*/0, /*IndentLevel=*/0, /*Spaces=*/1,
1324           /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective);
1325     }
1326     Penalty += format(*Previous.Children[0], State.Column + 1, DryRun);
1327 
1328     State.Column += 1 + Previous.Children[0]->Last->TotalLength;
1329     return true;
1330   }
1331 
1332   ContinuationIndenter *Indenter;
1333   WhitespaceManager *Whitespaces;
1334   FormatStyle Style;
1335   LineJoiner Joiner;
1336 
1337   llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
1338 
1339   // Cache to store the penalty of formatting a vector of AnnotatedLines
1340   // starting from a specific additional offset. Improves performance if there
1341   // are many nested blocks.
1342   std::map<std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned>,
1343            unsigned> PenaltyCache;
1344 };
1345 
1346 class FormatTokenLexer {
1347 public:
1348   FormatTokenLexer(SourceManager &SourceMgr, FileID ID, FormatStyle &Style,
1349                    encoding::Encoding Encoding)
1350       : FormatTok(nullptr), IsFirstToken(true), GreaterStashed(false),
1351         Column(0), TrailingWhitespace(0), SourceMgr(SourceMgr), ID(ID),
1352         Style(Style), IdentTable(getFormattingLangOpts(Style)),
1353         Keywords(IdentTable), Encoding(Encoding), FirstInLineIndex(0),
1354         FormattingDisabled(false) {
1355     Lex.reset(new Lexer(ID, SourceMgr.getBuffer(ID), SourceMgr,
1356                         getFormattingLangOpts(Style)));
1357     Lex->SetKeepWhitespaceMode(true);
1358 
1359     for (const std::string &ForEachMacro : Style.ForEachMacros)
1360       ForEachMacros.push_back(&IdentTable.get(ForEachMacro));
1361     std::sort(ForEachMacros.begin(), ForEachMacros.end());
1362   }
1363 
1364   ArrayRef<FormatToken *> lex() {
1365     assert(Tokens.empty());
1366     assert(FirstInLineIndex == 0);
1367     do {
1368       Tokens.push_back(getNextToken());
1369       tryMergePreviousTokens();
1370       if (Tokens.back()->NewlinesBefore > 0)
1371         FirstInLineIndex = Tokens.size() - 1;
1372     } while (Tokens.back()->Tok.isNot(tok::eof));
1373     return Tokens;
1374   }
1375 
1376   const AdditionalKeywords &getKeywords() { return Keywords; }
1377 
1378 private:
1379   void tryMergePreviousTokens() {
1380     if (tryMerge_TMacro())
1381       return;
1382     if (tryMergeConflictMarkers())
1383       return;
1384 
1385     if (Style.Language == FormatStyle::LK_JavaScript) {
1386       if (tryMergeJSRegexLiteral())
1387         return;
1388       if (tryMergeEscapeSequence())
1389         return;
1390 
1391       static tok::TokenKind JSIdentity[] = { tok::equalequal, tok::equal };
1392       static tok::TokenKind JSNotIdentity[] = { tok::exclaimequal, tok::equal };
1393       static tok::TokenKind JSShiftEqual[] = { tok::greater, tok::greater,
1394                                                tok::greaterequal };
1395       static tok::TokenKind JSRightArrow[] = { tok::equal, tok::greater };
1396       // FIXME: We probably need to change token type to mimic operator with the
1397       // correct priority.
1398       if (tryMergeTokens(JSIdentity))
1399         return;
1400       if (tryMergeTokens(JSNotIdentity))
1401         return;
1402       if (tryMergeTokens(JSShiftEqual))
1403         return;
1404       if (tryMergeTokens(JSRightArrow))
1405         return;
1406     }
1407   }
1408 
1409   bool tryMergeTokens(ArrayRef<tok::TokenKind> Kinds) {
1410     if (Tokens.size() < Kinds.size())
1411       return false;
1412 
1413     SmallVectorImpl<FormatToken *>::const_iterator First =
1414         Tokens.end() - Kinds.size();
1415     if (!First[0]->is(Kinds[0]))
1416       return false;
1417     unsigned AddLength = 0;
1418     for (unsigned i = 1; i < Kinds.size(); ++i) {
1419       if (!First[i]->is(Kinds[i]) || First[i]->WhitespaceRange.getBegin() !=
1420                                          First[i]->WhitespaceRange.getEnd())
1421         return false;
1422       AddLength += First[i]->TokenText.size();
1423     }
1424     Tokens.resize(Tokens.size() - Kinds.size() + 1);
1425     First[0]->TokenText = StringRef(First[0]->TokenText.data(),
1426                                     First[0]->TokenText.size() + AddLength);
1427     First[0]->ColumnWidth += AddLength;
1428     return true;
1429   }
1430 
1431   // Tries to merge an escape sequence, i.e. a "\\" and the following
1432   // character. Use e.g. inside JavaScript regex literals.
1433   bool tryMergeEscapeSequence() {
1434     if (Tokens.size() < 2)
1435       return false;
1436     FormatToken *Previous = Tokens[Tokens.size() - 2];
1437     if (Previous->isNot(tok::unknown) || Previous->TokenText != "\\")
1438       return false;
1439     ++Previous->ColumnWidth;
1440     StringRef Text = Previous->TokenText;
1441     Previous->TokenText = StringRef(Text.data(), Text.size() + 1);
1442     resetLexer(SourceMgr.getFileOffset(Tokens.back()->Tok.getLocation()) + 1);
1443     Tokens.resize(Tokens.size() - 1);
1444     Column = Previous->OriginalColumn + Previous->ColumnWidth;
1445     return true;
1446   }
1447 
1448   // Try to determine whether the current token ends a JavaScript regex literal.
1449   // We heuristically assume that this is a regex literal if we find two
1450   // unescaped slashes on a line and the token before the first slash is one of
1451   // "(;,{}![:?", a binary operator or 'return', as those cannot be followed by
1452   // a division.
1453   bool tryMergeJSRegexLiteral() {
1454     if (Tokens.size() < 2)
1455       return false;
1456     // If a regex literal ends in "\//", this gets represented by an unknown
1457     // token "\" and a comment.
1458     bool MightEndWithEscapedSlash =
1459         Tokens.back()->is(tok::comment) &&
1460         Tokens.back()->TokenText.startswith("//") &&
1461         Tokens[Tokens.size() - 2]->TokenText == "\\";
1462     if (!MightEndWithEscapedSlash &&
1463         (Tokens.back()->isNot(tok::slash) ||
1464          (Tokens[Tokens.size() - 2]->is(tok::unknown) &&
1465           Tokens[Tokens.size() - 2]->TokenText == "\\")))
1466       return false;
1467     unsigned TokenCount = 0;
1468     unsigned LastColumn = Tokens.back()->OriginalColumn;
1469     for (auto I = Tokens.rbegin() + 1, E = Tokens.rend(); I != E; ++I) {
1470       ++TokenCount;
1471       if (I[0]->is(tok::slash) && I + 1 != E &&
1472           (I[1]->isOneOf(tok::l_paren, tok::semi, tok::l_brace, tok::r_brace,
1473                          tok::exclaim, tok::l_square, tok::colon, tok::comma,
1474                          tok::question, tok::kw_return) ||
1475            I[1]->isBinaryOperator())) {
1476         if (MightEndWithEscapedSlash) {
1477           // This regex literal ends in '\//'. Skip past the '//' of the last
1478           // token and re-start lexing from there.
1479           SourceLocation Loc = Tokens.back()->Tok.getLocation();
1480           resetLexer(SourceMgr.getFileOffset(Loc) + 2);
1481         }
1482         Tokens.resize(Tokens.size() - TokenCount);
1483         Tokens.back()->Tok.setKind(tok::unknown);
1484         Tokens.back()->Type = TT_RegexLiteral;
1485         Tokens.back()->ColumnWidth += LastColumn - I[0]->OriginalColumn;
1486         return true;
1487       }
1488 
1489       // There can't be a newline inside a regex literal.
1490       if (I[0]->NewlinesBefore > 0)
1491         return false;
1492     }
1493     return false;
1494   }
1495 
1496   bool tryMerge_TMacro() {
1497     if (Tokens.size() < 4)
1498       return false;
1499     FormatToken *Last = Tokens.back();
1500     if (!Last->is(tok::r_paren))
1501       return false;
1502 
1503     FormatToken *String = Tokens[Tokens.size() - 2];
1504     if (!String->is(tok::string_literal) || String->IsMultiline)
1505       return false;
1506 
1507     if (!Tokens[Tokens.size() - 3]->is(tok::l_paren))
1508       return false;
1509 
1510     FormatToken *Macro = Tokens[Tokens.size() - 4];
1511     if (Macro->TokenText != "_T")
1512       return false;
1513 
1514     const char *Start = Macro->TokenText.data();
1515     const char *End = Last->TokenText.data() + Last->TokenText.size();
1516     String->TokenText = StringRef(Start, End - Start);
1517     String->IsFirst = Macro->IsFirst;
1518     String->LastNewlineOffset = Macro->LastNewlineOffset;
1519     String->WhitespaceRange = Macro->WhitespaceRange;
1520     String->OriginalColumn = Macro->OriginalColumn;
1521     String->ColumnWidth = encoding::columnWidthWithTabs(
1522         String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding);
1523 
1524     Tokens.pop_back();
1525     Tokens.pop_back();
1526     Tokens.pop_back();
1527     Tokens.back() = String;
1528     return true;
1529   }
1530 
1531   bool tryMergeConflictMarkers() {
1532     if (Tokens.back()->NewlinesBefore == 0 && Tokens.back()->isNot(tok::eof))
1533       return false;
1534 
1535     // Conflict lines look like:
1536     // <marker> <text from the vcs>
1537     // For example:
1538     // >>>>>>> /file/in/file/system at revision 1234
1539     //
1540     // We merge all tokens in a line that starts with a conflict marker
1541     // into a single token with a special token type that the unwrapped line
1542     // parser will use to correctly rebuild the underlying code.
1543 
1544     FileID ID;
1545     // Get the position of the first token in the line.
1546     unsigned FirstInLineOffset;
1547     std::tie(ID, FirstInLineOffset) = SourceMgr.getDecomposedLoc(
1548         Tokens[FirstInLineIndex]->getStartOfNonWhitespace());
1549     StringRef Buffer = SourceMgr.getBuffer(ID)->getBuffer();
1550     // Calculate the offset of the start of the current line.
1551     auto LineOffset = Buffer.rfind('\n', FirstInLineOffset);
1552     if (LineOffset == StringRef::npos) {
1553       LineOffset = 0;
1554     } else {
1555       ++LineOffset;
1556     }
1557 
1558     auto FirstSpace = Buffer.find_first_of(" \n", LineOffset);
1559     StringRef LineStart;
1560     if (FirstSpace == StringRef::npos) {
1561       LineStart = Buffer.substr(LineOffset);
1562     } else {
1563       LineStart = Buffer.substr(LineOffset, FirstSpace - LineOffset);
1564     }
1565 
1566     TokenType Type = TT_Unknown;
1567     if (LineStart == "<<<<<<<" || LineStart == ">>>>") {
1568       Type = TT_ConflictStart;
1569     } else if (LineStart == "|||||||" || LineStart == "=======" ||
1570                LineStart == "====") {
1571       Type = TT_ConflictAlternative;
1572     } else if (LineStart == ">>>>>>>" || LineStart == "<<<<") {
1573       Type = TT_ConflictEnd;
1574     }
1575 
1576     if (Type != TT_Unknown) {
1577       FormatToken *Next = Tokens.back();
1578 
1579       Tokens.resize(FirstInLineIndex + 1);
1580       // We do not need to build a complete token here, as we will skip it
1581       // during parsing anyway (as we must not touch whitespace around conflict
1582       // markers).
1583       Tokens.back()->Type = Type;
1584       Tokens.back()->Tok.setKind(tok::kw___unknown_anytype);
1585 
1586       Tokens.push_back(Next);
1587       return true;
1588     }
1589 
1590     return false;
1591   }
1592 
1593   FormatToken *getNextToken() {
1594     if (GreaterStashed) {
1595       // Create a synthesized second '>' token.
1596       // FIXME: Increment Column and set OriginalColumn.
1597       Token Greater = FormatTok->Tok;
1598       FormatTok = new (Allocator.Allocate()) FormatToken;
1599       FormatTok->Tok = Greater;
1600       SourceLocation GreaterLocation =
1601           FormatTok->Tok.getLocation().getLocWithOffset(1);
1602       FormatTok->WhitespaceRange =
1603           SourceRange(GreaterLocation, GreaterLocation);
1604       FormatTok->TokenText = ">";
1605       FormatTok->ColumnWidth = 1;
1606       GreaterStashed = false;
1607       return FormatTok;
1608     }
1609 
1610     FormatTok = new (Allocator.Allocate()) FormatToken;
1611     readRawToken(*FormatTok);
1612     SourceLocation WhitespaceStart =
1613         FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
1614     FormatTok->IsFirst = IsFirstToken;
1615     IsFirstToken = false;
1616 
1617     // Consume and record whitespace until we find a significant token.
1618     unsigned WhitespaceLength = TrailingWhitespace;
1619     while (FormatTok->Tok.is(tok::unknown)) {
1620       for (int i = 0, e = FormatTok->TokenText.size(); i != e; ++i) {
1621         switch (FormatTok->TokenText[i]) {
1622         case '\n':
1623           ++FormatTok->NewlinesBefore;
1624           // FIXME: This is technically incorrect, as it could also
1625           // be a literal backslash at the end of the line.
1626           if (i == 0 || (FormatTok->TokenText[i - 1] != '\\' &&
1627                          (FormatTok->TokenText[i - 1] != '\r' || i == 1 ||
1628                           FormatTok->TokenText[i - 2] != '\\')))
1629             FormatTok->HasUnescapedNewline = true;
1630           FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1631           Column = 0;
1632           break;
1633         case '\r':
1634         case '\f':
1635         case '\v':
1636           Column = 0;
1637           break;
1638         case ' ':
1639           ++Column;
1640           break;
1641         case '\t':
1642           Column += Style.TabWidth - Column % Style.TabWidth;
1643           break;
1644         case '\\':
1645           ++Column;
1646           if (i + 1 == e || (FormatTok->TokenText[i + 1] != '\r' &&
1647                              FormatTok->TokenText[i + 1] != '\n'))
1648             FormatTok->Type = TT_ImplicitStringLiteral;
1649           break;
1650         default:
1651           FormatTok->Type = TT_ImplicitStringLiteral;
1652           ++Column;
1653           break;
1654         }
1655       }
1656 
1657       if (FormatTok->Type == TT_ImplicitStringLiteral)
1658         break;
1659       WhitespaceLength += FormatTok->Tok.getLength();
1660 
1661       readRawToken(*FormatTok);
1662     }
1663 
1664     // In case the token starts with escaped newlines, we want to
1665     // take them into account as whitespace - this pattern is quite frequent
1666     // in macro definitions.
1667     // FIXME: Add a more explicit test.
1668     while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
1669            FormatTok->TokenText[1] == '\n') {
1670       ++FormatTok->NewlinesBefore;
1671       WhitespaceLength += 2;
1672       Column = 0;
1673       FormatTok->TokenText = FormatTok->TokenText.substr(2);
1674     }
1675 
1676     FormatTok->WhitespaceRange = SourceRange(
1677         WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
1678 
1679     FormatTok->OriginalColumn = Column;
1680 
1681     TrailingWhitespace = 0;
1682     if (FormatTok->Tok.is(tok::comment)) {
1683       // FIXME: Add the trimmed whitespace to Column.
1684       StringRef UntrimmedText = FormatTok->TokenText;
1685       FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
1686       TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
1687     } else if (FormatTok->Tok.is(tok::raw_identifier)) {
1688       IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
1689       FormatTok->Tok.setIdentifierInfo(&Info);
1690       FormatTok->Tok.setKind(Info.getTokenID());
1691       if (Style.Language == FormatStyle::LK_Java &&
1692           FormatTok->isOneOf(tok::kw_struct, tok::kw_union, tok::kw_delete)) {
1693         FormatTok->Tok.setKind(tok::identifier);
1694         FormatTok->Tok.setIdentifierInfo(nullptr);
1695       }
1696     } else if (FormatTok->Tok.is(tok::greatergreater)) {
1697       FormatTok->Tok.setKind(tok::greater);
1698       FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1699       GreaterStashed = true;
1700     }
1701 
1702     // Now FormatTok is the next non-whitespace token.
1703 
1704     StringRef Text = FormatTok->TokenText;
1705     size_t FirstNewlinePos = Text.find('\n');
1706     if (FirstNewlinePos == StringRef::npos) {
1707       // FIXME: ColumnWidth actually depends on the start column, we need to
1708       // take this into account when the token is moved.
1709       FormatTok->ColumnWidth =
1710           encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding);
1711       Column += FormatTok->ColumnWidth;
1712     } else {
1713       FormatTok->IsMultiline = true;
1714       // FIXME: ColumnWidth actually depends on the start column, we need to
1715       // take this into account when the token is moved.
1716       FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
1717           Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding);
1718 
1719       // The last line of the token always starts in column 0.
1720       // Thus, the length can be precomputed even in the presence of tabs.
1721       FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
1722           Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth,
1723           Encoding);
1724       Column = FormatTok->LastLineColumnWidth;
1725     }
1726 
1727     FormatTok->IsForEachMacro =
1728         std::binary_search(ForEachMacros.begin(), ForEachMacros.end(),
1729                            FormatTok->Tok.getIdentifierInfo());
1730 
1731     return FormatTok;
1732   }
1733 
1734   FormatToken *FormatTok;
1735   bool IsFirstToken;
1736   bool GreaterStashed;
1737   unsigned Column;
1738   unsigned TrailingWhitespace;
1739   std::unique_ptr<Lexer> Lex;
1740   SourceManager &SourceMgr;
1741   FileID ID;
1742   FormatStyle &Style;
1743   IdentifierTable IdentTable;
1744   AdditionalKeywords Keywords;
1745   encoding::Encoding Encoding;
1746   llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
1747   // Index (in 'Tokens') of the last token that starts a new line.
1748   unsigned FirstInLineIndex;
1749   SmallVector<FormatToken *, 16> Tokens;
1750   SmallVector<IdentifierInfo *, 8> ForEachMacros;
1751 
1752   bool FormattingDisabled;
1753 
1754   void readRawToken(FormatToken &Tok) {
1755     Lex->LexFromRawLexer(Tok.Tok);
1756     Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
1757                               Tok.Tok.getLength());
1758     // For formatting, treat unterminated string literals like normal string
1759     // literals.
1760     if (Tok.is(tok::unknown)) {
1761       if (!Tok.TokenText.empty() && Tok.TokenText[0] == '"') {
1762         Tok.Tok.setKind(tok::string_literal);
1763         Tok.IsUnterminatedLiteral = true;
1764       } else if (Style.Language == FormatStyle::LK_JavaScript &&
1765                  Tok.TokenText == "''") {
1766         Tok.Tok.setKind(tok::char_constant);
1767       }
1768     }
1769 
1770     if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format on" ||
1771                                  Tok.TokenText == "/* clang-format on */")) {
1772       FormattingDisabled = false;
1773     }
1774 
1775     Tok.Finalized = FormattingDisabled;
1776 
1777     if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format off" ||
1778                                  Tok.TokenText == "/* clang-format off */")) {
1779       FormattingDisabled = true;
1780     }
1781   }
1782 
1783   void resetLexer(unsigned Offset) {
1784     StringRef Buffer = SourceMgr.getBufferData(ID);
1785     Lex.reset(new Lexer(SourceMgr.getLocForStartOfFile(ID),
1786                         getFormattingLangOpts(Style), Buffer.begin(),
1787                         Buffer.begin() + Offset, Buffer.end()));
1788     Lex->SetKeepWhitespaceMode(true);
1789   }
1790 };
1791 
1792 static StringRef getLanguageName(FormatStyle::LanguageKind Language) {
1793   switch (Language) {
1794   case FormatStyle::LK_Cpp:
1795     return "C++";
1796   case FormatStyle::LK_Java:
1797     return "Java";
1798   case FormatStyle::LK_JavaScript:
1799     return "JavaScript";
1800   case FormatStyle::LK_Proto:
1801     return "Proto";
1802   default:
1803     return "Unknown";
1804   }
1805 }
1806 
1807 class Formatter : public UnwrappedLineConsumer {
1808 public:
1809   Formatter(const FormatStyle &Style, SourceManager &SourceMgr, FileID ID,
1810             ArrayRef<CharSourceRange> Ranges)
1811       : Style(Style), ID(ID), SourceMgr(SourceMgr),
1812         Whitespaces(SourceMgr, Style,
1813                     inputUsesCRLF(SourceMgr.getBufferData(ID))),
1814         Ranges(Ranges.begin(), Ranges.end()), UnwrappedLines(1),
1815         Encoding(encoding::detectEncoding(SourceMgr.getBufferData(ID))) {
1816     DEBUG(llvm::dbgs() << "File encoding: "
1817                        << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
1818                                                                : "unknown")
1819                        << "\n");
1820     DEBUG(llvm::dbgs() << "Language: " << getLanguageName(Style.Language)
1821                        << "\n");
1822   }
1823 
1824   tooling::Replacements format() {
1825     tooling::Replacements Result;
1826     FormatTokenLexer Tokens(SourceMgr, ID, Style, Encoding);
1827 
1828     UnwrappedLineParser Parser(Style, Tokens.getKeywords(), Tokens.lex(),
1829                                *this);
1830     bool StructuralError = Parser.parse();
1831     assert(UnwrappedLines.rbegin()->empty());
1832     for (unsigned Run = 0, RunE = UnwrappedLines.size(); Run + 1 != RunE;
1833          ++Run) {
1834       DEBUG(llvm::dbgs() << "Run " << Run << "...\n");
1835       SmallVector<AnnotatedLine *, 16> AnnotatedLines;
1836       for (unsigned i = 0, e = UnwrappedLines[Run].size(); i != e; ++i) {
1837         AnnotatedLines.push_back(new AnnotatedLine(UnwrappedLines[Run][i]));
1838       }
1839       tooling::Replacements RunResult =
1840           format(AnnotatedLines, StructuralError, Tokens);
1841       DEBUG({
1842         llvm::dbgs() << "Replacements for run " << Run << ":\n";
1843         for (tooling::Replacements::iterator I = RunResult.begin(),
1844                                              E = RunResult.end();
1845              I != E; ++I) {
1846           llvm::dbgs() << I->toString() << "\n";
1847         }
1848       });
1849       for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1850         delete AnnotatedLines[i];
1851       }
1852       Result.insert(RunResult.begin(), RunResult.end());
1853       Whitespaces.reset();
1854     }
1855     return Result;
1856   }
1857 
1858   tooling::Replacements format(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1859                                bool StructuralError, FormatTokenLexer &Tokens) {
1860     TokenAnnotator Annotator(Style, Tokens.getKeywords());
1861     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1862       Annotator.annotate(*AnnotatedLines[i]);
1863     }
1864     deriveLocalStyle(AnnotatedLines);
1865     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1866       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1867     }
1868     computeAffectedLines(AnnotatedLines.begin(), AnnotatedLines.end());
1869 
1870     Annotator.setCommentLineLevels(AnnotatedLines);
1871     ContinuationIndenter Indenter(Style, Tokens.getKeywords(), SourceMgr,
1872                                   Whitespaces, Encoding,
1873                                   BinPackInconclusiveFunctions);
1874     UnwrappedLineFormatter Formatter(&Indenter, &Whitespaces, Style);
1875     Formatter.format(AnnotatedLines, /*DryRun=*/false);
1876     return Whitespaces.generateReplacements();
1877   }
1878 
1879 private:
1880   // Determines which lines are affected by the SourceRanges given as input.
1881   // Returns \c true if at least one line between I and E or one of their
1882   // children is affected.
1883   bool computeAffectedLines(SmallVectorImpl<AnnotatedLine *>::iterator I,
1884                             SmallVectorImpl<AnnotatedLine *>::iterator E) {
1885     bool SomeLineAffected = false;
1886     const AnnotatedLine *PreviousLine = nullptr;
1887     while (I != E) {
1888       AnnotatedLine *Line = *I;
1889       Line->LeadingEmptyLinesAffected = affectsLeadingEmptyLines(*Line->First);
1890 
1891       // If a line is part of a preprocessor directive, it needs to be formatted
1892       // if any token within the directive is affected.
1893       if (Line->InPPDirective) {
1894         FormatToken *Last = Line->Last;
1895         SmallVectorImpl<AnnotatedLine *>::iterator PPEnd = I + 1;
1896         while (PPEnd != E && !(*PPEnd)->First->HasUnescapedNewline) {
1897           Last = (*PPEnd)->Last;
1898           ++PPEnd;
1899         }
1900 
1901         if (affectsTokenRange(*Line->First, *Last,
1902                               /*IncludeLeadingNewlines=*/false)) {
1903           SomeLineAffected = true;
1904           markAllAsAffected(I, PPEnd);
1905         }
1906         I = PPEnd;
1907         continue;
1908       }
1909 
1910       if (nonPPLineAffected(Line, PreviousLine))
1911         SomeLineAffected = true;
1912 
1913       PreviousLine = Line;
1914       ++I;
1915     }
1916     return SomeLineAffected;
1917   }
1918 
1919   // Determines whether 'Line' is affected by the SourceRanges given as input.
1920   // Returns \c true if line or one if its children is affected.
1921   bool nonPPLineAffected(AnnotatedLine *Line,
1922                          const AnnotatedLine *PreviousLine) {
1923     bool SomeLineAffected = false;
1924     Line->ChildrenAffected =
1925         computeAffectedLines(Line->Children.begin(), Line->Children.end());
1926     if (Line->ChildrenAffected)
1927       SomeLineAffected = true;
1928 
1929     // Stores whether one of the line's tokens is directly affected.
1930     bool SomeTokenAffected = false;
1931     // Stores whether we need to look at the leading newlines of the next token
1932     // in order to determine whether it was affected.
1933     bool IncludeLeadingNewlines = false;
1934 
1935     // Stores whether the first child line of any of this line's tokens is
1936     // affected.
1937     bool SomeFirstChildAffected = false;
1938 
1939     for (FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
1940       // Determine whether 'Tok' was affected.
1941       if (affectsTokenRange(*Tok, *Tok, IncludeLeadingNewlines))
1942         SomeTokenAffected = true;
1943 
1944       // Determine whether the first child of 'Tok' was affected.
1945       if (!Tok->Children.empty() && Tok->Children.front()->Affected)
1946         SomeFirstChildAffected = true;
1947 
1948       IncludeLeadingNewlines = Tok->Children.empty();
1949     }
1950 
1951     // Was this line moved, i.e. has it previously been on the same line as an
1952     // affected line?
1953     bool LineMoved = PreviousLine && PreviousLine->Affected &&
1954                      Line->First->NewlinesBefore == 0;
1955 
1956     bool IsContinuedComment =
1957         Line->First->is(tok::comment) && Line->First->Next == nullptr &&
1958         Line->First->NewlinesBefore < 2 && PreviousLine &&
1959         PreviousLine->Affected && PreviousLine->Last->is(tok::comment);
1960 
1961     if (SomeTokenAffected || SomeFirstChildAffected || LineMoved ||
1962         IsContinuedComment) {
1963       Line->Affected = true;
1964       SomeLineAffected = true;
1965     }
1966     return SomeLineAffected;
1967   }
1968 
1969   // Marks all lines between I and E as well as all their children as affected.
1970   void markAllAsAffected(SmallVectorImpl<AnnotatedLine *>::iterator I,
1971                          SmallVectorImpl<AnnotatedLine *>::iterator E) {
1972     while (I != E) {
1973       (*I)->Affected = true;
1974       markAllAsAffected((*I)->Children.begin(), (*I)->Children.end());
1975       ++I;
1976     }
1977   }
1978 
1979   // Returns true if the range from 'First' to 'Last' intersects with one of the
1980   // input ranges.
1981   bool affectsTokenRange(const FormatToken &First, const FormatToken &Last,
1982                          bool IncludeLeadingNewlines) {
1983     SourceLocation Start = First.WhitespaceRange.getBegin();
1984     if (!IncludeLeadingNewlines)
1985       Start = Start.getLocWithOffset(First.LastNewlineOffset);
1986     SourceLocation End = Last.getStartOfNonWhitespace();
1987     End = End.getLocWithOffset(Last.TokenText.size());
1988     CharSourceRange Range = CharSourceRange::getCharRange(Start, End);
1989     return affectsCharSourceRange(Range);
1990   }
1991 
1992   // Returns true if one of the input ranges intersect the leading empty lines
1993   // before 'Tok'.
1994   bool affectsLeadingEmptyLines(const FormatToken &Tok) {
1995     CharSourceRange EmptyLineRange = CharSourceRange::getCharRange(
1996         Tok.WhitespaceRange.getBegin(),
1997         Tok.WhitespaceRange.getBegin().getLocWithOffset(Tok.LastNewlineOffset));
1998     return affectsCharSourceRange(EmptyLineRange);
1999   }
2000 
2001   // Returns true if 'Range' intersects with one of the input ranges.
2002   bool affectsCharSourceRange(const CharSourceRange &Range) {
2003     for (SmallVectorImpl<CharSourceRange>::const_iterator I = Ranges.begin(),
2004                                                           E = Ranges.end();
2005          I != E; ++I) {
2006       if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), I->getBegin()) &&
2007           !SourceMgr.isBeforeInTranslationUnit(I->getEnd(), Range.getBegin()))
2008         return true;
2009     }
2010     return false;
2011   }
2012 
2013   static bool inputUsesCRLF(StringRef Text) {
2014     return Text.count('\r') * 2 > Text.count('\n');
2015   }
2016 
2017   void
2018   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
2019     unsigned CountBoundToVariable = 0;
2020     unsigned CountBoundToType = 0;
2021     bool HasCpp03IncompatibleFormat = false;
2022     bool HasBinPackedFunction = false;
2023     bool HasOnePerLineFunction = false;
2024     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
2025       if (!AnnotatedLines[i]->First->Next)
2026         continue;
2027       FormatToken *Tok = AnnotatedLines[i]->First->Next;
2028       while (Tok->Next) {
2029         if (Tok->Type == TT_PointerOrReference) {
2030           bool SpacesBefore =
2031               Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
2032           bool SpacesAfter = Tok->Next->WhitespaceRange.getBegin() !=
2033                              Tok->Next->WhitespaceRange.getEnd();
2034           if (SpacesBefore && !SpacesAfter)
2035             ++CountBoundToVariable;
2036           else if (!SpacesBefore && SpacesAfter)
2037             ++CountBoundToType;
2038         }
2039 
2040         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
2041           if (Tok->is(tok::coloncolon) &&
2042               Tok->Previous->Type == TT_TemplateOpener)
2043             HasCpp03IncompatibleFormat = true;
2044           if (Tok->Type == TT_TemplateCloser &&
2045               Tok->Previous->Type == TT_TemplateCloser)
2046             HasCpp03IncompatibleFormat = true;
2047         }
2048 
2049         if (Tok->PackingKind == PPK_BinPacked)
2050           HasBinPackedFunction = true;
2051         if (Tok->PackingKind == PPK_OnePerLine)
2052           HasOnePerLineFunction = true;
2053 
2054         Tok = Tok->Next;
2055       }
2056     }
2057     if (Style.DerivePointerAlignment) {
2058       if (CountBoundToType > CountBoundToVariable)
2059         Style.PointerAlignment = FormatStyle::PAS_Left;
2060       else if (CountBoundToType < CountBoundToVariable)
2061         Style.PointerAlignment = FormatStyle::PAS_Right;
2062     }
2063     if (Style.Standard == FormatStyle::LS_Auto) {
2064       Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11
2065                                                   : FormatStyle::LS_Cpp03;
2066     }
2067     BinPackInconclusiveFunctions =
2068         HasBinPackedFunction || !HasOnePerLineFunction;
2069   }
2070 
2071   void consumeUnwrappedLine(const UnwrappedLine &TheLine) override {
2072     assert(!UnwrappedLines.empty());
2073     UnwrappedLines.back().push_back(TheLine);
2074   }
2075 
2076   void finishRun() override {
2077     UnwrappedLines.push_back(SmallVector<UnwrappedLine, 16>());
2078   }
2079 
2080   FormatStyle Style;
2081   FileID ID;
2082   SourceManager &SourceMgr;
2083   WhitespaceManager Whitespaces;
2084   SmallVector<CharSourceRange, 8> Ranges;
2085   SmallVector<SmallVector<UnwrappedLine, 16>, 2> UnwrappedLines;
2086 
2087   encoding::Encoding Encoding;
2088   bool BinPackInconclusiveFunctions;
2089 };
2090 
2091 } // end anonymous namespace
2092 
2093 tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
2094                                SourceManager &SourceMgr,
2095                                ArrayRef<CharSourceRange> Ranges) {
2096   if (Style.DisableFormat)
2097     return tooling::Replacements();
2098   return reformat(Style, SourceMgr,
2099                   SourceMgr.getFileID(Lex.getSourceLocation()), Ranges);
2100 }
2101 
2102 tooling::Replacements reformat(const FormatStyle &Style,
2103                                SourceManager &SourceMgr, FileID ID,
2104                                ArrayRef<CharSourceRange> Ranges) {
2105   if (Style.DisableFormat)
2106     return tooling::Replacements();
2107   Formatter formatter(Style, SourceMgr, ID, Ranges);
2108   return formatter.format();
2109 }
2110 
2111 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
2112                                ArrayRef<tooling::Range> Ranges,
2113                                StringRef FileName) {
2114   if (Style.DisableFormat)
2115     return tooling::Replacements();
2116 
2117   FileManager Files((FileSystemOptions()));
2118   DiagnosticsEngine Diagnostics(
2119       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
2120       new DiagnosticOptions);
2121   SourceManager SourceMgr(Diagnostics, Files);
2122   std::unique_ptr<llvm::MemoryBuffer> Buf =
2123       llvm::MemoryBuffer::getMemBuffer(Code, FileName);
2124   const clang::FileEntry *Entry =
2125       Files.getVirtualFile(FileName, Buf->getBufferSize(), 0);
2126   SourceMgr.overrideFileContents(Entry, std::move(Buf));
2127   FileID ID =
2128       SourceMgr.createFileID(Entry, SourceLocation(), clang::SrcMgr::C_User);
2129   SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
2130   std::vector<CharSourceRange> CharRanges;
2131   for (const tooling::Range &Range : Ranges) {
2132     SourceLocation Start = StartOfFile.getLocWithOffset(Range.getOffset());
2133     SourceLocation End = Start.getLocWithOffset(Range.getLength());
2134     CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
2135   }
2136   return reformat(Style, SourceMgr, ID, CharRanges);
2137 }
2138 
2139 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
2140   LangOptions LangOpts;
2141   LangOpts.CPlusPlus = 1;
2142   LangOpts.CPlusPlus11 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
2143   LangOpts.CPlusPlus14 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
2144   LangOpts.LineComment = 1;
2145   bool AlternativeOperators = Style.Language != FormatStyle::LK_JavaScript &&
2146                               Style.Language != FormatStyle::LK_Java;
2147   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
2148   LangOpts.Bool = 1;
2149   LangOpts.ObjC1 = 1;
2150   LangOpts.ObjC2 = 1;
2151   return LangOpts;
2152 }
2153 
2154 const char *StyleOptionHelpDescription =
2155     "Coding style, currently supports:\n"
2156     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
2157     "Use -style=file to load style configuration from\n"
2158     ".clang-format file located in one of the parent\n"
2159     "directories of the source file (or current\n"
2160     "directory for stdin).\n"
2161     "Use -style=\"{key: value, ...}\" to set specific\n"
2162     "parameters, e.g.:\n"
2163     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
2164 
2165 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
2166   if (FileName.endswith(".java")) {
2167     return FormatStyle::LK_Java;
2168   } else if (FileName.endswith_lower(".js")) {
2169     return FormatStyle::LK_JavaScript;
2170   } else if (FileName.endswith_lower(".proto") ||
2171              FileName.endswith_lower(".protodevel")) {
2172     return FormatStyle::LK_Proto;
2173   }
2174   return FormatStyle::LK_Cpp;
2175 }
2176 
2177 FormatStyle getStyle(StringRef StyleName, StringRef FileName,
2178                      StringRef FallbackStyle) {
2179   FormatStyle Style = getLLVMStyle();
2180   Style.Language = getLanguageByFileName(FileName);
2181   if (!getPredefinedStyle(FallbackStyle, Style.Language, &Style)) {
2182     llvm::errs() << "Invalid fallback style \"" << FallbackStyle
2183                  << "\" using LLVM style\n";
2184     return Style;
2185   }
2186 
2187   if (StyleName.startswith("{")) {
2188     // Parse YAML/JSON style from the command line.
2189     if (std::error_code ec = parseConfiguration(StyleName, &Style)) {
2190       llvm::errs() << "Error parsing -style: " << ec.message() << ", using "
2191                    << FallbackStyle << " style\n";
2192     }
2193     return Style;
2194   }
2195 
2196   if (!StyleName.equals_lower("file")) {
2197     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
2198       llvm::errs() << "Invalid value for -style, using " << FallbackStyle
2199                    << " style\n";
2200     return Style;
2201   }
2202 
2203   // Look for .clang-format/_clang-format file in the file's parent directories.
2204   SmallString<128> UnsuitableConfigFiles;
2205   SmallString<128> Path(FileName);
2206   llvm::sys::fs::make_absolute(Path);
2207   for (StringRef Directory = Path; !Directory.empty();
2208        Directory = llvm::sys::path::parent_path(Directory)) {
2209     if (!llvm::sys::fs::is_directory(Directory))
2210       continue;
2211     SmallString<128> ConfigFile(Directory);
2212 
2213     llvm::sys::path::append(ConfigFile, ".clang-format");
2214     DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2215     bool IsFile = false;
2216     // Ignore errors from is_regular_file: we only need to know if we can read
2217     // the file or not.
2218     llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
2219 
2220     if (!IsFile) {
2221       // Try _clang-format too, since dotfiles are not commonly used on Windows.
2222       ConfigFile = Directory;
2223       llvm::sys::path::append(ConfigFile, "_clang-format");
2224       DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2225       llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
2226     }
2227 
2228     if (IsFile) {
2229       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
2230           llvm::MemoryBuffer::getFile(ConfigFile.c_str());
2231       if (std::error_code EC = Text.getError()) {
2232         llvm::errs() << EC.message() << "\n";
2233         break;
2234       }
2235       if (std::error_code ec =
2236               parseConfiguration(Text.get()->getBuffer(), &Style)) {
2237         if (ec == ParseError::Unsuitable) {
2238           if (!UnsuitableConfigFiles.empty())
2239             UnsuitableConfigFiles.append(", ");
2240           UnsuitableConfigFiles.append(ConfigFile);
2241           continue;
2242         }
2243         llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message()
2244                      << "\n";
2245         break;
2246       }
2247       DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
2248       return Style;
2249     }
2250   }
2251   llvm::errs() << "Can't find usable .clang-format, using " << FallbackStyle
2252                << " style\n";
2253   if (!UnsuitableConfigFiles.empty()) {
2254     llvm::errs() << "Configuration file(s) do(es) not support "
2255                  << getLanguageName(Style.Language) << ": "
2256                  << UnsuitableConfigFiles << "\n";
2257   }
2258   return Style;
2259 }
2260 
2261 } // namespace format
2262 } // namespace clang
2263