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 #define DEBUG_TYPE "format-formatter"
17 
18 #include "ContinuationIndenter.h"
19 #include "TokenAnnotator.h"
20 #include "UnwrappedLineParser.h"
21 #include "WhitespaceManager.h"
22 #include "clang/Basic/Diagnostic.h"
23 #include "clang/Basic/SourceManager.h"
24 #include "clang/Format/Format.h"
25 #include "clang/Lex/Lexer.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/Support/Allocator.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/YAMLTraits.h"
30 #include "llvm/Support/Path.h"
31 #include <queue>
32 #include <string>
33 
34 using clang::format::FormatStyle;
35 
36 namespace llvm {
37 namespace yaml {
38 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
39   static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
40     IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
41     IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
42   }
43 };
44 
45 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
46   static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
47     IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03);
48     IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03);
49     IO.enumCase(Value, "Cpp11", FormatStyle::LS_Cpp11);
50     IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11);
51     IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
52   }
53 };
54 
55 template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
56   static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
57     IO.enumCase(Value, "Never", FormatStyle::UT_Never);
58     IO.enumCase(Value, "false", FormatStyle::UT_Never);
59     IO.enumCase(Value, "Always", FormatStyle::UT_Always);
60     IO.enumCase(Value, "true", FormatStyle::UT_Always);
61     IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
62   }
63 };
64 
65 template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
66   static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
67     IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
68     IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
69     IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
70     IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
71     IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
72   }
73 };
74 
75 template <>
76 struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
77   static void enumeration(IO &IO,
78                           FormatStyle::NamespaceIndentationKind &Value) {
79     IO.enumCase(Value, "None", FormatStyle::NI_None);
80     IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
81     IO.enumCase(Value, "All", FormatStyle::NI_All);
82   }
83 };
84 
85 template <>
86 struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
87   static void enumeration(IO &IO,
88                           FormatStyle::SpaceBeforeParensOptions &Value) {
89     IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
90     IO.enumCase(Value, "ControlStatements",
91                 FormatStyle::SBPO_ControlStatements);
92     IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
93 
94     // For backward compatibility.
95     IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
96     IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
97   }
98 };
99 
100 template <> struct MappingTraits<FormatStyle> {
101   static void mapping(IO &IO, FormatStyle &Style) {
102     // When reading, read the language first, we need it for getPredefinedStyle.
103     IO.mapOptional("Language", Style.Language);
104 
105     if (IO.outputting()) {
106       StringRef StylesArray[] = { "LLVM",    "Google", "Chromium",
107                                   "Mozilla", "WebKit", "GNU" };
108       ArrayRef<StringRef> Styles(StylesArray);
109       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
110         StringRef StyleName(Styles[i]);
111         FormatStyle PredefinedStyle;
112         if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
113             Style == PredefinedStyle) {
114           IO.mapOptional("# BasedOnStyle", StyleName);
115           break;
116         }
117       }
118     } else {
119       StringRef BasedOnStyle;
120       IO.mapOptional("BasedOnStyle", BasedOnStyle);
121       if (!BasedOnStyle.empty()) {
122         FormatStyle::LanguageKind OldLanguage = Style.Language;
123         FormatStyle::LanguageKind Language =
124             ((FormatStyle *)IO.getContext())->Language;
125         if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
126           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
127           return;
128         }
129         Style.Language = OldLanguage;
130       }
131     }
132 
133     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
134     IO.mapOptional("ConstructorInitializerIndentWidth",
135                    Style.ConstructorInitializerIndentWidth);
136     IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
137     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
138     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
139                    Style.AllowAllParametersOfDeclarationOnNextLine);
140     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
141                    Style.AllowShortIfStatementsOnASingleLine);
142     IO.mapOptional("AllowShortLoopsOnASingleLine",
143                    Style.AllowShortLoopsOnASingleLine);
144     IO.mapOptional("AllowShortFunctionsOnASingleLine",
145                    Style.AllowShortFunctionsOnASingleLine);
146     IO.mapOptional("AlwaysBreakTemplateDeclarations",
147                    Style.AlwaysBreakTemplateDeclarations);
148     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
149                    Style.AlwaysBreakBeforeMultilineStrings);
150     IO.mapOptional("BreakBeforeBinaryOperators",
151                    Style.BreakBeforeBinaryOperators);
152     IO.mapOptional("BreakBeforeTernaryOperators",
153                    Style.BreakBeforeTernaryOperators);
154     IO.mapOptional("BreakConstructorInitializersBeforeComma",
155                    Style.BreakConstructorInitializersBeforeComma);
156     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
157     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
158     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
159                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
160     IO.mapOptional("DerivePointerBinding", Style.DerivePointerBinding);
161     IO.mapOptional("ExperimentalAutoDetectBinPacking",
162                    Style.ExperimentalAutoDetectBinPacking);
163     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
164     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
165     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
166     IO.mapOptional("ObjCSpaceBeforeProtocolList",
167                    Style.ObjCSpaceBeforeProtocolList);
168     IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
169                    Style.PenaltyBreakBeforeFirstCallParameter);
170     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
171     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
172     IO.mapOptional("PenaltyBreakFirstLessLess",
173                    Style.PenaltyBreakFirstLessLess);
174     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
175     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
176                    Style.PenaltyReturnTypeOnItsOwnLine);
177     IO.mapOptional("PointerBindsToType", Style.PointerBindsToType);
178     IO.mapOptional("SpacesBeforeTrailingComments",
179                    Style.SpacesBeforeTrailingComments);
180     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
181     IO.mapOptional("Standard", Style.Standard);
182     IO.mapOptional("IndentWidth", Style.IndentWidth);
183     IO.mapOptional("TabWidth", Style.TabWidth);
184     IO.mapOptional("UseTab", Style.UseTab);
185     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
186     IO.mapOptional("IndentFunctionDeclarationAfterType",
187                    Style.IndentFunctionDeclarationAfterType);
188     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
189     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
190     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
191     IO.mapOptional("SpacesInCStyleCastParentheses",
192                    Style.SpacesInCStyleCastParentheses);
193     IO.mapOptional("SpaceBeforeAssignmentOperators",
194                    Style.SpaceBeforeAssignmentOperators);
195     IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
196 
197     // For backward compatibility.
198     if (!IO.outputting()) {
199       IO.mapOptional("SpaceAfterControlStatementKeyword",
200                      Style.SpaceBeforeParens);
201     }
202     IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
203   }
204 };
205 
206 // Allows to read vector<FormatStyle> while keeping default values.
207 // IO.getContext() should contain a pointer to the FormatStyle structure, that
208 // will be used to get default values for missing keys.
209 // If the first element has no Language specified, it will be treated as the
210 // default one for the following elements.
211 template <> struct DocumentListTraits<std::vector<FormatStyle> > {
212   static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
213     return Seq.size();
214   }
215   static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
216                               size_t Index) {
217     if (Index >= Seq.size()) {
218       assert(Index == Seq.size());
219       FormatStyle Template;
220       if (Seq.size() > 0 && Seq[0].Language == FormatStyle::LK_None) {
221         Template = Seq[0];
222       } else {
223         Template = *((const FormatStyle*)IO.getContext());
224         Template.Language = FormatStyle::LK_None;
225       }
226       Seq.resize(Index + 1, Template);
227     }
228     return Seq[Index];
229   }
230 };
231 }
232 }
233 
234 namespace clang {
235 namespace format {
236 
237 FormatStyle getLLVMStyle() {
238   FormatStyle LLVMStyle;
239   LLVMStyle.Language = FormatStyle::LK_Cpp;
240   LLVMStyle.AccessModifierOffset = -2;
241   LLVMStyle.AlignEscapedNewlinesLeft = false;
242   LLVMStyle.AlignTrailingComments = true;
243   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
244   LLVMStyle.AllowShortFunctionsOnASingleLine = true;
245   LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
246   LLVMStyle.AllowShortLoopsOnASingleLine = false;
247   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
248   LLVMStyle.AlwaysBreakTemplateDeclarations = false;
249   LLVMStyle.BinPackParameters = true;
250   LLVMStyle.BreakBeforeBinaryOperators = false;
251   LLVMStyle.BreakBeforeTernaryOperators = true;
252   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
253   LLVMStyle.BreakConstructorInitializersBeforeComma = false;
254   LLVMStyle.ColumnLimit = 80;
255   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
256   LLVMStyle.ConstructorInitializerIndentWidth = 4;
257   LLVMStyle.Cpp11BracedListStyle = false;
258   LLVMStyle.DerivePointerBinding = false;
259   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
260   LLVMStyle.IndentCaseLabels = false;
261   LLVMStyle.IndentFunctionDeclarationAfterType = false;
262   LLVMStyle.IndentWidth = 2;
263   LLVMStyle.TabWidth = 8;
264   LLVMStyle.MaxEmptyLinesToKeep = 1;
265   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
266   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
267   LLVMStyle.PointerBindsToType = false;
268   LLVMStyle.SpacesBeforeTrailingComments = 1;
269   LLVMStyle.Standard = FormatStyle::LS_Cpp03;
270   LLVMStyle.UseTab = FormatStyle::UT_Never;
271   LLVMStyle.SpacesInParentheses = false;
272   LLVMStyle.SpaceInEmptyParentheses = false;
273   LLVMStyle.SpacesInCStyleCastParentheses = false;
274   LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
275   LLVMStyle.SpaceBeforeAssignmentOperators = true;
276   LLVMStyle.ContinuationIndentWidth = 4;
277   LLVMStyle.SpacesInAngles = false;
278 
279   LLVMStyle.PenaltyBreakComment = 60;
280   LLVMStyle.PenaltyBreakFirstLessLess = 120;
281   LLVMStyle.PenaltyBreakString = 1000;
282   LLVMStyle.PenaltyExcessCharacter = 1000000;
283   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
284   LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
285 
286   return LLVMStyle;
287 }
288 
289 FormatStyle getGoogleStyle() {
290   FormatStyle GoogleStyle = getLLVMStyle();
291   GoogleStyle.AccessModifierOffset = -1;
292   GoogleStyle.AlignEscapedNewlinesLeft = true;
293   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
294   GoogleStyle.AllowShortLoopsOnASingleLine = true;
295   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
296   GoogleStyle.AlwaysBreakTemplateDeclarations = true;
297   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
298   GoogleStyle.Cpp11BracedListStyle = true;
299   GoogleStyle.DerivePointerBinding = true;
300   GoogleStyle.IndentCaseLabels = true;
301   GoogleStyle.IndentFunctionDeclarationAfterType = true;
302   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
303   GoogleStyle.PointerBindsToType = true;
304   GoogleStyle.SpacesBeforeTrailingComments = 2;
305   GoogleStyle.Standard = FormatStyle::LS_Auto;
306 
307   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
308   GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
309 
310   return GoogleStyle;
311 }
312 
313 FormatStyle getGoogleJSStyle() {
314   FormatStyle GoogleJSStyle = getGoogleStyle();
315   GoogleJSStyle.Language = FormatStyle::LK_JavaScript;
316   GoogleJSStyle.BreakBeforeTernaryOperators = false;
317   // FIXME: Currently unimplemented:
318   // var arr = [1, 2, 3];  // No space after [ or before ].
319   // var obj = {a: 1, b: 2, c: 3};  // No space after ':'.
320   return GoogleJSStyle;
321 }
322 
323 FormatStyle getChromiumStyle() {
324   FormatStyle ChromiumStyle = getGoogleStyle();
325   ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
326   ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
327   ChromiumStyle.AllowShortLoopsOnASingleLine = false;
328   ChromiumStyle.BinPackParameters = false;
329   ChromiumStyle.DerivePointerBinding = false;
330   ChromiumStyle.Standard = FormatStyle::LS_Cpp03;
331   return ChromiumStyle;
332 }
333 
334 FormatStyle getMozillaStyle() {
335   FormatStyle MozillaStyle = getLLVMStyle();
336   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
337   MozillaStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
338   MozillaStyle.DerivePointerBinding = true;
339   MozillaStyle.IndentCaseLabels = true;
340   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
341   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
342   MozillaStyle.PointerBindsToType = true;
343   return MozillaStyle;
344 }
345 
346 FormatStyle getWebKitStyle() {
347   FormatStyle Style = getLLVMStyle();
348   Style.AccessModifierOffset = -4;
349   Style.AlignTrailingComments = false;
350   Style.BreakBeforeBinaryOperators = true;
351   Style.BreakBeforeBraces = FormatStyle::BS_Stroustrup;
352   Style.BreakConstructorInitializersBeforeComma = true;
353   Style.ColumnLimit = 0;
354   Style.IndentWidth = 4;
355   Style.NamespaceIndentation = FormatStyle::NI_Inner;
356   Style.PointerBindsToType = true;
357   return Style;
358 }
359 
360 FormatStyle getGNUStyle() {
361   FormatStyle Style = getLLVMStyle();
362   Style.BreakBeforeBinaryOperators = true;
363   Style.BreakBeforeBraces = FormatStyle::BS_GNU;
364   Style.BreakBeforeTernaryOperators = true;
365   Style.ColumnLimit = 79;
366   Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
367   return Style;
368 }
369 
370 bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
371                         FormatStyle *Style) {
372   if (Name.equals_lower("llvm")) {
373     *Style = getLLVMStyle();
374   } else if (Name.equals_lower("chromium")) {
375     *Style = getChromiumStyle();
376   } else if (Name.equals_lower("mozilla")) {
377     *Style = getMozillaStyle();
378   } else if (Name.equals_lower("google")) {
379     *Style = Language == FormatStyle::LK_JavaScript ? getGoogleJSStyle()
380                                                     : getGoogleStyle();
381   } else if (Name.equals_lower("webkit")) {
382     *Style = getWebKitStyle();
383   } else if (Name.equals_lower("gnu")) {
384     *Style = getGNUStyle();
385   } else {
386     return false;
387   }
388 
389   Style->Language = Language;
390   return true;
391 }
392 
393 llvm::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
394   assert(Style);
395   FormatStyle::LanguageKind Language = Style->Language;
396   assert(Language != FormatStyle::LK_None);
397   if (Text.trim().empty())
398     return llvm::make_error_code(llvm::errc::invalid_argument);
399 
400   std::vector<FormatStyle> Styles;
401   llvm::yaml::Input Input(Text);
402   // DocumentListTraits<vector<FormatStyle>> uses the context to get default
403   // values for the fields, keys for which are missing from the configuration.
404   // Mapping also uses the context to get the language to find the correct
405   // base style.
406   Input.setContext(Style);
407   Input >> Styles;
408   if (Input.error())
409     return Input.error();
410 
411   for (unsigned i = 0; i < Styles.size(); ++i) {
412     // Ensures that only the first configuration can skip the Language option.
413     if (Styles[i].Language == FormatStyle::LK_None && i != 0)
414       return llvm::make_error_code(llvm::errc::invalid_argument);
415     // Ensure that each language is configured at most once.
416     for (unsigned j = 0; j < i; ++j) {
417       if (Styles[i].Language == Styles[j].Language) {
418         DEBUG(llvm::dbgs()
419               << "Duplicate languages in the config file on positions " << j
420               << " and " << i << "\n");
421         return llvm::make_error_code(llvm::errc::invalid_argument);
422       }
423     }
424   }
425   // Look for a suitable configuration starting from the end, so we can
426   // find the configuration for the specific language first, and the default
427   // configuration (which can only be at slot 0) after it.
428   for (int i = Styles.size() - 1; i >= 0; --i) {
429     if (Styles[i].Language == Language ||
430         Styles[i].Language == FormatStyle::LK_None) {
431       *Style = Styles[i];
432       Style->Language = Language;
433       return llvm::make_error_code(llvm::errc::success);
434     }
435   }
436   return llvm::make_error_code(llvm::errc::not_supported);
437 }
438 
439 std::string configurationAsText(const FormatStyle &Style) {
440   std::string Text;
441   llvm::raw_string_ostream Stream(Text);
442   llvm::yaml::Output Output(Stream);
443   // We use the same mapping method for input and output, so we need a non-const
444   // reference here.
445   FormatStyle NonConstStyle = Style;
446   Output << NonConstStyle;
447   return Stream.str();
448 }
449 
450 namespace {
451 
452 class NoColumnLimitFormatter {
453 public:
454   NoColumnLimitFormatter(ContinuationIndenter *Indenter) : Indenter(Indenter) {}
455 
456   /// \brief Formats the line starting at \p State, simply keeping all of the
457   /// input's line breaking decisions.
458   void format(unsigned FirstIndent, const AnnotatedLine *Line,
459               bool LineIsMerged) {
460     LineState State =
461         Indenter->getInitialState(FirstIndent, Line, /*DryRun=*/false);
462     while (State.NextToken != NULL) {
463       bool Newline =
464           (!LineIsMerged && Indenter->mustBreak(State)) ||
465           (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
466       Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
467     }
468   }
469 
470 private:
471   ContinuationIndenter *Indenter;
472 };
473 
474 class LineJoiner {
475 public:
476   LineJoiner(const FormatStyle &Style) : Style(Style) {}
477 
478   /// \brief Calculates how many lines can be merged into 1 starting at \p I.
479   unsigned
480   tryFitMultipleLinesInOne(unsigned Indent,
481                            SmallVectorImpl<AnnotatedLine *>::const_iterator I,
482                            SmallVectorImpl<AnnotatedLine *>::const_iterator E) {
483     // We can never merge stuff if there are trailing line comments.
484     AnnotatedLine *TheLine = *I;
485     if (TheLine->Last->Type == TT_LineComment)
486       return 0;
487 
488     if (Style.ColumnLimit > 0 && Indent > Style.ColumnLimit)
489       return 0;
490 
491     unsigned Limit =
492         Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent;
493     // If we already exceed the column limit, we set 'Limit' to 0. The different
494     // tryMerge..() functions can then decide whether to still do merging.
495     Limit = TheLine->Last->TotalLength > Limit
496                 ? 0
497                 : Limit - TheLine->Last->TotalLength;
498 
499     if (I + 1 == E || I[1]->Type == LT_Invalid)
500       return 0;
501 
502     if (TheLine->Last->Type == TT_FunctionLBrace) {
503       return Style.AllowShortFunctionsOnASingleLine
504                  ? tryMergeSimpleBlock(I, E, Limit)
505                  : 0;
506     }
507     if (TheLine->Last->is(tok::l_brace)) {
508       return Style.BreakBeforeBraces == FormatStyle::BS_Attach
509                  ? tryMergeSimpleBlock(I, E, Limit)
510                  : 0;
511     }
512     if (I[1]->First->Type == TT_FunctionLBrace &&
513         Style.BreakBeforeBraces != FormatStyle::BS_Attach) {
514       // Reduce the column limit by the number of spaces we need to insert
515       // around braces.
516       Limit = Limit > 3 ? Limit - 3 : 0;
517       unsigned MergedLines = 0;
518       if (Style.AllowShortFunctionsOnASingleLine) {
519         MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
520         // If we managed to merge the block, count the function header, which is
521         // on a separate line.
522         if (MergedLines > 0)
523           ++MergedLines;
524       }
525       return MergedLines;
526     }
527     if (TheLine->First->is(tok::kw_if)) {
528       return Style.AllowShortIfStatementsOnASingleLine
529                  ? tryMergeSimpleControlStatement(I, E, Limit)
530                  : 0;
531     }
532     if (TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
533       return Style.AllowShortLoopsOnASingleLine
534                  ? tryMergeSimpleControlStatement(I, E, Limit)
535                  : 0;
536     }
537     if (TheLine->InPPDirective &&
538         (TheLine->First->HasUnescapedNewline || TheLine->First->IsFirst)) {
539       return tryMergeSimplePPDirective(I, E, Limit);
540     }
541     return 0;
542   }
543 
544 private:
545   unsigned
546   tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
547                             SmallVectorImpl<AnnotatedLine *>::const_iterator E,
548                             unsigned Limit) {
549     if (Limit == 0)
550       return 0;
551     if (!I[1]->InPPDirective || I[1]->First->HasUnescapedNewline)
552       return 0;
553     if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)
554       return 0;
555     if (1 + I[1]->Last->TotalLength > Limit)
556       return 0;
557     return 1;
558   }
559 
560   unsigned tryMergeSimpleControlStatement(
561       SmallVectorImpl<AnnotatedLine *>::const_iterator I,
562       SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
563     if (Limit == 0)
564       return 0;
565     if ((Style.BreakBeforeBraces == FormatStyle::BS_Allman ||
566          Style.BreakBeforeBraces == FormatStyle::BS_GNU) &&
567         I[1]->First->is(tok::l_brace))
568       return 0;
569     if (I[1]->InPPDirective != (*I)->InPPDirective ||
570         (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline))
571       return 0;
572     AnnotatedLine &Line = **I;
573     if (Line.Last->isNot(tok::r_paren))
574       return 0;
575     if (1 + I[1]->Last->TotalLength > Limit)
576       return 0;
577     if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for,
578                              tok::kw_while) ||
579         I[1]->First->Type == TT_LineComment)
580       return 0;
581     // Only inline simple if's (no nested if or else).
582     if (I + 2 != E && Line.First->is(tok::kw_if) &&
583         I[2]->First->is(tok::kw_else))
584       return 0;
585     return 1;
586   }
587 
588   unsigned
589   tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
590                       SmallVectorImpl<AnnotatedLine *>::const_iterator E,
591                       unsigned Limit) {
592     // First, check that the current line allows merging. This is the case if
593     // we're not in a control flow statement and the last token is an opening
594     // brace.
595     AnnotatedLine &Line = **I;
596     if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::r_brace,
597                             tok::kw_else, tok::kw_try, tok::kw_catch,
598                             tok::kw_for,
599                             // This gets rid of all ObjC @ keywords and methods.
600                             tok::at, tok::minus, tok::plus))
601       return 0;
602 
603     FormatToken *Tok = I[1]->First;
604     if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
605         (Tok->getNextNonComment() == NULL ||
606          Tok->getNextNonComment()->is(tok::semi))) {
607       // We merge empty blocks even if the line exceeds the column limit.
608       Tok->SpacesRequiredBefore = 0;
609       Tok->CanBreakBefore = true;
610       return 1;
611     } else if (Limit != 0 && Line.First->isNot(tok::kw_namespace)) {
612       // Check that we still have three lines and they fit into the limit.
613       if (I + 2 == E || I[2]->Type == LT_Invalid)
614         return 0;
615 
616       if (!nextTwoLinesFitInto(I, Limit))
617         return 0;
618 
619       // Second, check that the next line does not contain any braces - if it
620       // does, readability declines when putting it into a single line.
621       if (I[1]->Last->Type == TT_LineComment || Tok->MustBreakBefore)
622         return 0;
623       do {
624         if (Tok->isOneOf(tok::l_brace, tok::r_brace))
625           return 0;
626         Tok = Tok->Next;
627       } while (Tok != NULL);
628 
629       // Last, check that the third line contains a single closing brace.
630       Tok = I[2]->First;
631       if (Tok->getNextNonComment() != NULL || Tok->isNot(tok::r_brace) ||
632           Tok->MustBreakBefore)
633         return 0;
634 
635       return 2;
636     }
637     return 0;
638   }
639 
640   bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
641                            unsigned Limit) {
642     return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;
643   }
644 
645   const FormatStyle &Style;
646 };
647 
648 class UnwrappedLineFormatter {
649 public:
650   UnwrappedLineFormatter(ContinuationIndenter *Indenter,
651                          WhitespaceManager *Whitespaces,
652                          const FormatStyle &Style)
653       : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style),
654         Joiner(Style) {}
655 
656   unsigned format(const SmallVectorImpl<AnnotatedLine *> &Lines, bool DryRun,
657                   int AdditionalIndent = 0, bool FixBadIndentation = false) {
658     assert(!Lines.empty());
659     unsigned Penalty = 0;
660     std::vector<int> IndentForLevel;
661     for (unsigned i = 0, e = Lines[0]->Level; i != e; ++i)
662       IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent);
663     const AnnotatedLine *PreviousLine = NULL;
664     for (SmallVectorImpl<AnnotatedLine *>::const_iterator I = Lines.begin(),
665                                                           E = Lines.end();
666          I != E; ++I) {
667       const AnnotatedLine &TheLine = **I;
668       const FormatToken *FirstTok = TheLine.First;
669       int Offset = getIndentOffset(*FirstTok);
670 
671       // Determine indent and try to merge multiple unwrapped lines.
672       while (IndentForLevel.size() <= TheLine.Level)
673         IndentForLevel.push_back(-1);
674       IndentForLevel.resize(TheLine.Level + 1);
675       unsigned Indent = getIndent(IndentForLevel, TheLine.Level);
676       if (static_cast<int>(Indent) + Offset >= 0)
677         Indent += Offset;
678       unsigned MergedLines = Joiner.tryFitMultipleLinesInOne(Indent, I, E);
679       if (MergedLines > 0 && Style.ColumnLimit == 0) {
680         // Disallow line merging if there is a break at the start of one of the
681         // input lines.
682         for (unsigned i = 0; i < MergedLines; ++i) {
683           if (I[i + 1]->First->NewlinesBefore > 0)
684             MergedLines = 0;
685         }
686       }
687       if (!DryRun) {
688         for (unsigned i = 0; i < MergedLines; ++i) {
689           join(*I[i], *I[i + 1]);
690         }
691       }
692       I += MergedLines;
693 
694       unsigned LevelIndent = getIndent(IndentForLevel, TheLine.Level);
695       bool FixIndentation =
696           FixBadIndentation && (LevelIndent != FirstTok->OriginalColumn);
697       if (TheLine.First->is(tok::eof)) {
698         if (PreviousLine && PreviousLine->Affected && !DryRun) {
699           // Remove the file's trailing whitespace.
700           unsigned Newlines = std::min(FirstTok->NewlinesBefore, 1u);
701           Whitespaces->replaceWhitespace(*TheLine.First, Newlines,
702                                          /*IndentLevel=*/0, /*Spaces=*/0,
703                                          /*TargetColumn=*/0);
704         }
705       } else if (TheLine.Type != LT_Invalid &&
706                  (TheLine.Affected || FixIndentation)) {
707         if (FirstTok->WhitespaceRange.isValid()) {
708           if (!DryRun)
709             formatFirstToken(*TheLine.First, PreviousLine, TheLine.Level,
710                              Indent, TheLine.InPPDirective);
711         } else {
712           Indent = LevelIndent = FirstTok->OriginalColumn;
713         }
714 
715         // If everything fits on a single line, just put it there.
716         unsigned ColumnLimit = Style.ColumnLimit;
717         if (I + 1 != E) {
718           AnnotatedLine *NextLine = I[1];
719           if (NextLine->InPPDirective && !NextLine->First->HasUnescapedNewline)
720             ColumnLimit = getColumnLimit(TheLine.InPPDirective);
721         }
722 
723         if (TheLine.Last->TotalLength + Indent <= ColumnLimit) {
724           LineState State = Indenter->getInitialState(Indent, &TheLine, DryRun);
725           while (State.NextToken != NULL)
726             Indenter->addTokenToState(State, /*Newline=*/false, DryRun);
727         } else if (Style.ColumnLimit == 0) {
728           // FIXME: Implement nested blocks for ColumnLimit = 0.
729           NoColumnLimitFormatter Formatter(Indenter);
730           if (!DryRun)
731             Formatter.format(Indent, &TheLine,
732                              /*LineIsMerged=*/MergedLines > 0);
733         } else {
734           Penalty += format(TheLine, Indent, DryRun);
735         }
736 
737         IndentForLevel[TheLine.Level] = LevelIndent;
738       } else if (TheLine.ChildrenAffected) {
739         format(TheLine.Children, DryRun);
740       } else {
741         // Format the first token if necessary, and notify the WhitespaceManager
742         // about the unchanged whitespace.
743         for (FormatToken *Tok = TheLine.First; Tok != NULL; Tok = Tok->Next) {
744           if (Tok == TheLine.First &&
745               (Tok->NewlinesBefore > 0 || Tok->IsFirst)) {
746             unsigned LevelIndent = Tok->OriginalColumn;
747             if (!DryRun) {
748               // Remove trailing whitespace of the previous line.
749               if ((PreviousLine && PreviousLine->Affected) ||
750                   TheLine.LeadingEmptyLinesAffected) {
751                 formatFirstToken(*Tok, PreviousLine, TheLine.Level, LevelIndent,
752                                  TheLine.InPPDirective);
753               } else {
754                 Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
755               }
756             }
757 
758             if (static_cast<int>(LevelIndent) - Offset >= 0)
759               LevelIndent -= Offset;
760             if (Tok->isNot(tok::comment))
761               IndentForLevel[TheLine.Level] = LevelIndent;
762           } else if (!DryRun) {
763             Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
764           }
765         }
766       }
767       if (!DryRun) {
768         for (FormatToken *Tok = TheLine.First; Tok != NULL; Tok = Tok->Next) {
769           Tok->Finalized = true;
770         }
771       }
772       PreviousLine = *I;
773     }
774     return Penalty;
775   }
776 
777 private:
778   /// \brief Formats an \c AnnotatedLine and returns the penalty.
779   ///
780   /// If \p DryRun is \c false, directly applies the changes.
781   unsigned format(const AnnotatedLine &Line, unsigned FirstIndent,
782                   bool DryRun) {
783     LineState State = Indenter->getInitialState(FirstIndent, &Line, DryRun);
784 
785     // If the ObjC method declaration does not fit on a line, we should format
786     // it with one arg per line.
787     if (State.Line->Type == LT_ObjCMethodDecl)
788       State.Stack.back().BreakBeforeParameter = true;
789 
790     // Find best solution in solution space.
791     return analyzeSolutionSpace(State, DryRun);
792   }
793 
794   /// \brief An edge in the solution space from \c Previous->State to \c State,
795   /// inserting a newline dependent on the \c NewLine.
796   struct StateNode {
797     StateNode(const LineState &State, bool NewLine, StateNode *Previous)
798         : State(State), NewLine(NewLine), Previous(Previous) {}
799     LineState State;
800     bool NewLine;
801     StateNode *Previous;
802   };
803 
804   /// \brief A pair of <penalty, count> that is used to prioritize the BFS on.
805   ///
806   /// In case of equal penalties, we want to prefer states that were inserted
807   /// first. During state generation we make sure that we insert states first
808   /// that break the line as late as possible.
809   typedef std::pair<unsigned, unsigned> OrderedPenalty;
810 
811   /// \brief An item in the prioritized BFS search queue. The \c StateNode's
812   /// \c State has the given \c OrderedPenalty.
813   typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
814 
815   /// \brief The BFS queue type.
816   typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
817                               std::greater<QueueItem> > QueueType;
818 
819   /// \brief Get the offset of the line relatively to the level.
820   ///
821   /// For example, 'public:' labels in classes are offset by 1 or 2
822   /// characters to the left from their level.
823   int getIndentOffset(const FormatToken &RootToken) {
824     if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier())
825       return Style.AccessModifierOffset;
826     return 0;
827   }
828 
829   /// \brief Add a new line and the required indent before the first Token
830   /// of the \c UnwrappedLine if there was no structural parsing error.
831   void formatFirstToken(FormatToken &RootToken,
832                         const AnnotatedLine *PreviousLine, unsigned IndentLevel,
833                         unsigned Indent, bool InPPDirective) {
834     unsigned Newlines =
835         std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
836     // Remove empty lines before "}" where applicable.
837     if (RootToken.is(tok::r_brace) &&
838         (!RootToken.Next ||
839          (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)))
840       Newlines = std::min(Newlines, 1u);
841     if (Newlines == 0 && !RootToken.IsFirst)
842       Newlines = 1;
843 
844     // Insert extra new line before access specifiers.
845     if (PreviousLine && PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) &&
846         RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
847       ++Newlines;
848 
849     // Remove empty lines after access specifiers.
850     if (PreviousLine && PreviousLine->First->isAccessSpecifier())
851       Newlines = std::min(1u, Newlines);
852 
853     Whitespaces->replaceWhitespace(RootToken, Newlines, IndentLevel, Indent,
854                                    Indent, InPPDirective &&
855                                                !RootToken.HasUnescapedNewline);
856   }
857 
858   /// \brief Get the indent of \p Level from \p IndentForLevel.
859   ///
860   /// \p IndentForLevel must contain the indent for the level \c l
861   /// at \p IndentForLevel[l], or a value < 0 if the indent for
862   /// that level is unknown.
863   unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) {
864     if (IndentForLevel[Level] != -1)
865       return IndentForLevel[Level];
866     if (Level == 0)
867       return 0;
868     return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth;
869   }
870 
871   void join(AnnotatedLine &A, const AnnotatedLine &B) {
872     assert(!A.Last->Next);
873     assert(!B.First->Previous);
874     if (B.Affected)
875       A.Affected = true;
876     A.Last->Next = B.First;
877     B.First->Previous = A.Last;
878     B.First->CanBreakBefore = true;
879     unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
880     for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
881       Tok->TotalLength += LengthA;
882       A.Last = Tok;
883     }
884   }
885 
886   unsigned getColumnLimit(bool InPPDirective) const {
887     // In preprocessor directives reserve two chars for trailing " \"
888     return Style.ColumnLimit - (InPPDirective ? 2 : 0);
889   }
890 
891   /// \brief Analyze the entire solution space starting from \p InitialState.
892   ///
893   /// This implements a variant of Dijkstra's algorithm on the graph that spans
894   /// the solution space (\c LineStates are the nodes). The algorithm tries to
895   /// find the shortest path (the one with lowest penalty) from \p InitialState
896   /// to a state where all tokens are placed. Returns the penalty.
897   ///
898   /// If \p DryRun is \c false, directly applies the changes.
899   unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun = false) {
900     std::set<LineState> Seen;
901 
902     // Increasing count of \c StateNode items we have created. This is used to
903     // create a deterministic order independent of the container.
904     unsigned Count = 0;
905     QueueType Queue;
906 
907     // Insert start element into queue.
908     StateNode *Node =
909         new (Allocator.Allocate()) StateNode(InitialState, false, NULL);
910     Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
911     ++Count;
912 
913     unsigned Penalty = 0;
914 
915     // While not empty, take first element and follow edges.
916     while (!Queue.empty()) {
917       Penalty = Queue.top().first.first;
918       StateNode *Node = Queue.top().second;
919       if (Node->State.NextToken == NULL) {
920         DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n");
921         break;
922       }
923       Queue.pop();
924 
925       // Cut off the analysis of certain solutions if the analysis gets too
926       // complex. See description of IgnoreStackForComparison.
927       if (Count > 10000)
928         Node->State.IgnoreStackForComparison = true;
929 
930       if (!Seen.insert(Node->State).second)
931         // State already examined with lower penalty.
932         continue;
933 
934       FormatDecision LastFormat = Node->State.NextToken->Decision;
935       if (LastFormat == FD_Unformatted || LastFormat == FD_Continue)
936         addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue);
937       if (LastFormat == FD_Unformatted || LastFormat == FD_Break)
938         addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue);
939     }
940 
941     if (Queue.empty()) {
942       // We were unable to find a solution, do nothing.
943       // FIXME: Add diagnostic?
944       DEBUG(llvm::dbgs() << "Could not find a solution.\n");
945       return 0;
946     }
947 
948     // Reconstruct the solution.
949     if (!DryRun)
950       reconstructPath(InitialState, Queue.top().second);
951 
952     DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n");
953     DEBUG(llvm::dbgs() << "---\n");
954 
955     return Penalty;
956   }
957 
958   void reconstructPath(LineState &State, StateNode *Current) {
959     std::deque<StateNode *> Path;
960     // We do not need a break before the initial token.
961     while (Current->Previous) {
962       Path.push_front(Current);
963       Current = Current->Previous;
964     }
965     for (std::deque<StateNode *>::iterator I = Path.begin(), E = Path.end();
966          I != E; ++I) {
967       unsigned Penalty = 0;
968       formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
969       Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
970 
971       DEBUG({
972         if ((*I)->NewLine) {
973           llvm::dbgs() << "Penalty for placing "
974                        << (*I)->Previous->State.NextToken->Tok.getName() << ": "
975                        << Penalty << "\n";
976         }
977       });
978     }
979   }
980 
981   /// \brief Add the following state to the analysis queue \c Queue.
982   ///
983   /// Assume the current state is \p PreviousNode and has been reached with a
984   /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
985   void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
986                            bool NewLine, unsigned *Count, QueueType *Queue) {
987     if (NewLine && !Indenter->canBreak(PreviousNode->State))
988       return;
989     if (!NewLine && Indenter->mustBreak(PreviousNode->State))
990       return;
991 
992     StateNode *Node = new (Allocator.Allocate())
993         StateNode(PreviousNode->State, NewLine, PreviousNode);
994     if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
995       return;
996 
997     Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
998 
999     Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node));
1000     ++(*Count);
1001   }
1002 
1003   /// \brief If the \p State's next token is an r_brace closing a nested block,
1004   /// format the nested block before it.
1005   ///
1006   /// Returns \c true if all children could be placed successfully and adapts
1007   /// \p Penalty as well as \p State. If \p DryRun is false, also directly
1008   /// creates changes using \c Whitespaces.
1009   ///
1010   /// The crucial idea here is that children always get formatted upon
1011   /// encountering the closing brace right after the nested block. Now, if we
1012   /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is
1013   /// \c false), the entire block has to be kept on the same line (which is only
1014   /// possible if it fits on the line, only contains a single statement, etc.
1015   ///
1016   /// If \p NewLine is true, we format the nested block on separate lines, i.e.
1017   /// break after the "{", format all lines with correct indentation and the put
1018   /// the closing "}" on yet another new line.
1019   ///
1020   /// This enables us to keep the simple structure of the
1021   /// \c UnwrappedLineFormatter, where we only have two options for each token:
1022   /// break or don't break.
1023   bool formatChildren(LineState &State, bool NewLine, bool DryRun,
1024                       unsigned &Penalty) {
1025     FormatToken &Previous = *State.NextToken->Previous;
1026     const FormatToken *LBrace = State.NextToken->getPreviousNonComment();
1027     if (!LBrace || LBrace->isNot(tok::l_brace) ||
1028         LBrace->BlockKind != BK_Block || Previous.Children.size() == 0)
1029       // The previous token does not open a block. Nothing to do. We don't
1030       // assert so that we can simply call this function for all tokens.
1031       return true;
1032 
1033     if (NewLine) {
1034       int AdditionalIndent = State.Stack.back().Indent -
1035                              Previous.Children[0]->Level * Style.IndentWidth;
1036       Penalty += format(Previous.Children, DryRun, AdditionalIndent,
1037                         /*FixBadIndentation=*/true);
1038       return true;
1039     }
1040 
1041     // Cannot merge multiple statements into a single line.
1042     if (Previous.Children.size() > 1)
1043       return false;
1044 
1045     // We can't put the closing "}" on a line with a trailing comment.
1046     if (Previous.Children[0]->Last->isTrailingComment())
1047       return false;
1048 
1049     if (!DryRun) {
1050       Whitespaces->replaceWhitespace(
1051           *Previous.Children[0]->First,
1052           /*Newlines=*/0, /*IndentLevel=*/0, /*Spaces=*/1,
1053           /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective);
1054     }
1055     Penalty += format(*Previous.Children[0], State.Column + 1, DryRun);
1056 
1057     State.Column += 1 + Previous.Children[0]->Last->TotalLength;
1058     return true;
1059   }
1060 
1061   ContinuationIndenter *Indenter;
1062   WhitespaceManager *Whitespaces;
1063   FormatStyle Style;
1064   LineJoiner Joiner;
1065 
1066   llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
1067 };
1068 
1069 class FormatTokenLexer {
1070 public:
1071   FormatTokenLexer(Lexer &Lex, SourceManager &SourceMgr, FormatStyle &Style,
1072                    encoding::Encoding Encoding)
1073       : FormatTok(NULL), IsFirstToken(true), GreaterStashed(false), Column(0),
1074         TrailingWhitespace(0), Lex(Lex), SourceMgr(SourceMgr), Style(Style),
1075         IdentTable(getFormattingLangOpts()), Encoding(Encoding) {
1076     Lex.SetKeepWhitespaceMode(true);
1077   }
1078 
1079   ArrayRef<FormatToken *> lex() {
1080     assert(Tokens.empty());
1081     do {
1082       Tokens.push_back(getNextToken());
1083       tryMergePreviousTokens();
1084     } while (Tokens.back()->Tok.isNot(tok::eof));
1085     return Tokens;
1086   }
1087 
1088   IdentifierTable &getIdentTable() { return IdentTable; }
1089 
1090 private:
1091   void tryMergePreviousTokens() {
1092     if (tryMerge_TMacro())
1093       return;
1094 
1095     if (Style.Language == FormatStyle::LK_JavaScript) {
1096       static tok::TokenKind JSIdentity[] = { tok::equalequal, tok::equal };
1097       static tok::TokenKind JSNotIdentity[] = { tok::exclaimequal, tok::equal };
1098       static tok::TokenKind JSShiftEqual[] = { tok::greater, tok::greater,
1099                                                tok::greaterequal };
1100       // FIXME: We probably need to change token type to mimic operator with the
1101       // correct priority.
1102       if (tryMergeTokens(JSIdentity))
1103         return;
1104       if (tryMergeTokens(JSNotIdentity))
1105         return;
1106       if (tryMergeTokens(JSShiftEqual))
1107         return;
1108     }
1109   }
1110 
1111   bool tryMergeTokens(ArrayRef<tok::TokenKind> Kinds) {
1112     if (Tokens.size() < Kinds.size())
1113       return false;
1114 
1115     SmallVectorImpl<FormatToken *>::const_iterator First =
1116         Tokens.end() - Kinds.size();
1117     if (!First[0]->is(Kinds[0]))
1118       return false;
1119     unsigned AddLength = 0;
1120     for (unsigned i = 1; i < Kinds.size(); ++i) {
1121       if (!First[i]->is(Kinds[i]) || First[i]->WhitespaceRange.getBegin() !=
1122                                          First[i]->WhitespaceRange.getEnd())
1123         return false;
1124       AddLength += First[i]->TokenText.size();
1125     }
1126     Tokens.resize(Tokens.size() - Kinds.size() + 1);
1127     First[0]->TokenText = StringRef(First[0]->TokenText.data(),
1128                                     First[0]->TokenText.size() + AddLength);
1129     First[0]->ColumnWidth += AddLength;
1130     return true;
1131   }
1132 
1133   bool tryMerge_TMacro() {
1134     if (Tokens.size() < 4)
1135       return false;
1136     FormatToken *Last = Tokens.back();
1137     if (!Last->is(tok::r_paren))
1138       return false;
1139 
1140     FormatToken *String = Tokens[Tokens.size() - 2];
1141     if (!String->is(tok::string_literal) || String->IsMultiline)
1142       return false;
1143 
1144     if (!Tokens[Tokens.size() - 3]->is(tok::l_paren))
1145       return false;
1146 
1147     FormatToken *Macro = Tokens[Tokens.size() - 4];
1148     if (Macro->TokenText != "_T")
1149       return false;
1150 
1151     const char *Start = Macro->TokenText.data();
1152     const char *End = Last->TokenText.data() + Last->TokenText.size();
1153     String->TokenText = StringRef(Start, End - Start);
1154     String->IsFirst = Macro->IsFirst;
1155     String->LastNewlineOffset = Macro->LastNewlineOffset;
1156     String->WhitespaceRange = Macro->WhitespaceRange;
1157     String->OriginalColumn = Macro->OriginalColumn;
1158     String->ColumnWidth = encoding::columnWidthWithTabs(
1159         String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding);
1160 
1161     Tokens.pop_back();
1162     Tokens.pop_back();
1163     Tokens.pop_back();
1164     Tokens.back() = String;
1165     return true;
1166   }
1167 
1168   FormatToken *getNextToken() {
1169     if (GreaterStashed) {
1170       // Create a synthesized second '>' token.
1171       // FIXME: Increment Column and set OriginalColumn.
1172       Token Greater = FormatTok->Tok;
1173       FormatTok = new (Allocator.Allocate()) FormatToken;
1174       FormatTok->Tok = Greater;
1175       SourceLocation GreaterLocation =
1176           FormatTok->Tok.getLocation().getLocWithOffset(1);
1177       FormatTok->WhitespaceRange =
1178           SourceRange(GreaterLocation, GreaterLocation);
1179       FormatTok->TokenText = ">";
1180       FormatTok->ColumnWidth = 1;
1181       GreaterStashed = false;
1182       return FormatTok;
1183     }
1184 
1185     FormatTok = new (Allocator.Allocate()) FormatToken;
1186     readRawToken(*FormatTok);
1187     SourceLocation WhitespaceStart =
1188         FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
1189     FormatTok->IsFirst = IsFirstToken;
1190     IsFirstToken = false;
1191 
1192     // Consume and record whitespace until we find a significant token.
1193     unsigned WhitespaceLength = TrailingWhitespace;
1194     while (FormatTok->Tok.is(tok::unknown)) {
1195       for (int i = 0, e = FormatTok->TokenText.size(); i != e; ++i) {
1196         switch (FormatTok->TokenText[i]) {
1197         case '\n':
1198           ++FormatTok->NewlinesBefore;
1199           // FIXME: This is technically incorrect, as it could also
1200           // be a literal backslash at the end of the line.
1201           if (i == 0 || (FormatTok->TokenText[i - 1] != '\\' &&
1202                          (FormatTok->TokenText[i - 1] != '\r' || i == 1 ||
1203                           FormatTok->TokenText[i - 2] != '\\')))
1204             FormatTok->HasUnescapedNewline = true;
1205           FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1206           Column = 0;
1207           break;
1208         case '\r':
1209         case '\f':
1210         case '\v':
1211           Column = 0;
1212           break;
1213         case ' ':
1214           ++Column;
1215           break;
1216         case '\t':
1217           Column += Style.TabWidth - Column % Style.TabWidth;
1218           break;
1219         case '\\':
1220           ++Column;
1221           if (i + 1 == e || (FormatTok->TokenText[i + 1] != '\r' &&
1222                              FormatTok->TokenText[i + 1] != '\n'))
1223             FormatTok->Type = TT_ImplicitStringLiteral;
1224           break;
1225         default:
1226           FormatTok->Type = TT_ImplicitStringLiteral;
1227           ++Column;
1228           break;
1229         }
1230       }
1231 
1232       if (FormatTok->Type == TT_ImplicitStringLiteral)
1233         break;
1234       WhitespaceLength += FormatTok->Tok.getLength();
1235 
1236       readRawToken(*FormatTok);
1237     }
1238 
1239     // In case the token starts with escaped newlines, we want to
1240     // take them into account as whitespace - this pattern is quite frequent
1241     // in macro definitions.
1242     // FIXME: Add a more explicit test.
1243     while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
1244            FormatTok->TokenText[1] == '\n') {
1245       // FIXME: ++FormatTok->NewlinesBefore is missing...
1246       WhitespaceLength += 2;
1247       Column = 0;
1248       FormatTok->TokenText = FormatTok->TokenText.substr(2);
1249     }
1250 
1251     FormatTok->WhitespaceRange = SourceRange(
1252         WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
1253 
1254     FormatTok->OriginalColumn = Column;
1255 
1256     TrailingWhitespace = 0;
1257     if (FormatTok->Tok.is(tok::comment)) {
1258       // FIXME: Add the trimmed whitespace to Column.
1259       StringRef UntrimmedText = FormatTok->TokenText;
1260       FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
1261       TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
1262     } else if (FormatTok->Tok.is(tok::raw_identifier)) {
1263       IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
1264       FormatTok->Tok.setIdentifierInfo(&Info);
1265       FormatTok->Tok.setKind(Info.getTokenID());
1266     } else if (FormatTok->Tok.is(tok::greatergreater)) {
1267       FormatTok->Tok.setKind(tok::greater);
1268       FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1269       GreaterStashed = true;
1270     }
1271 
1272     // Now FormatTok is the next non-whitespace token.
1273 
1274     StringRef Text = FormatTok->TokenText;
1275     size_t FirstNewlinePos = Text.find('\n');
1276     if (FirstNewlinePos == StringRef::npos) {
1277       // FIXME: ColumnWidth actually depends on the start column, we need to
1278       // take this into account when the token is moved.
1279       FormatTok->ColumnWidth =
1280           encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding);
1281       Column += FormatTok->ColumnWidth;
1282     } else {
1283       FormatTok->IsMultiline = true;
1284       // FIXME: ColumnWidth actually depends on the start column, we need to
1285       // take this into account when the token is moved.
1286       FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
1287           Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding);
1288 
1289       // The last line of the token always starts in column 0.
1290       // Thus, the length can be precomputed even in the presence of tabs.
1291       FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
1292           Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth,
1293           Encoding);
1294       Column = FormatTok->LastLineColumnWidth;
1295     }
1296 
1297     return FormatTok;
1298   }
1299 
1300   FormatToken *FormatTok;
1301   bool IsFirstToken;
1302   bool GreaterStashed;
1303   unsigned Column;
1304   unsigned TrailingWhitespace;
1305   Lexer &Lex;
1306   SourceManager &SourceMgr;
1307   FormatStyle &Style;
1308   IdentifierTable IdentTable;
1309   encoding::Encoding Encoding;
1310   llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
1311   SmallVector<FormatToken *, 16> Tokens;
1312 
1313   void readRawToken(FormatToken &Tok) {
1314     Lex.LexFromRawLexer(Tok.Tok);
1315     Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
1316                               Tok.Tok.getLength());
1317     // For formatting, treat unterminated string literals like normal string
1318     // literals.
1319     if (Tok.is(tok::unknown) && !Tok.TokenText.empty() &&
1320         Tok.TokenText[0] == '"') {
1321       Tok.Tok.setKind(tok::string_literal);
1322       Tok.IsUnterminatedLiteral = true;
1323     }
1324   }
1325 };
1326 
1327 static StringRef getLanguageName(FormatStyle::LanguageKind Language) {
1328   switch (Language) {
1329   case FormatStyle::LK_Cpp:
1330     return "C++";
1331   case FormatStyle::LK_JavaScript:
1332     return "JavaScript";
1333   default:
1334     return "Unknown";
1335   }
1336 }
1337 
1338 class Formatter : public UnwrappedLineConsumer {
1339 public:
1340   Formatter(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr,
1341             const std::vector<CharSourceRange> &Ranges)
1342       : Style(Style), Lex(Lex), SourceMgr(SourceMgr),
1343         Whitespaces(SourceMgr, Style, inputUsesCRLF(Lex.getBuffer())),
1344         Ranges(Ranges.begin(), Ranges.end()), UnwrappedLines(1),
1345         Encoding(encoding::detectEncoding(Lex.getBuffer())) {
1346     DEBUG(llvm::dbgs() << "File encoding: "
1347                        << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
1348                                                                : "unknown")
1349                        << "\n");
1350     DEBUG(llvm::dbgs() << "Language: " << getLanguageName(Style.Language)
1351                        << "\n");
1352   }
1353 
1354   tooling::Replacements format() {
1355     tooling::Replacements Result;
1356     FormatTokenLexer Tokens(Lex, SourceMgr, Style, Encoding);
1357 
1358     UnwrappedLineParser Parser(Style, Tokens.lex(), *this);
1359     bool StructuralError = Parser.parse();
1360     assert(UnwrappedLines.rbegin()->empty());
1361     for (unsigned Run = 0, RunE = UnwrappedLines.size(); Run + 1 != RunE;
1362          ++Run) {
1363       DEBUG(llvm::dbgs() << "Run " << Run << "...\n");
1364       SmallVector<AnnotatedLine *, 16> AnnotatedLines;
1365       for (unsigned i = 0, e = UnwrappedLines[Run].size(); i != e; ++i) {
1366         AnnotatedLines.push_back(new AnnotatedLine(UnwrappedLines[Run][i]));
1367       }
1368       tooling::Replacements RunResult =
1369           format(AnnotatedLines, StructuralError, Tokens);
1370       DEBUG({
1371         llvm::dbgs() << "Replacements for run " << Run << ":\n";
1372         for (tooling::Replacements::iterator I = RunResult.begin(),
1373                                              E = RunResult.end();
1374              I != E; ++I) {
1375           llvm::dbgs() << I->toString() << "\n";
1376         }
1377       });
1378       for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1379         delete AnnotatedLines[i];
1380       }
1381       Result.insert(RunResult.begin(), RunResult.end());
1382       Whitespaces.reset();
1383     }
1384     return Result;
1385   }
1386 
1387   tooling::Replacements format(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1388                                bool StructuralError, FormatTokenLexer &Tokens) {
1389     TokenAnnotator Annotator(Style, Tokens.getIdentTable().get("in"));
1390     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1391       Annotator.annotate(*AnnotatedLines[i]);
1392     }
1393     deriveLocalStyle(AnnotatedLines);
1394     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1395       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1396     }
1397     computeAffectedLines(AnnotatedLines.begin(), AnnotatedLines.end());
1398 
1399     Annotator.setCommentLineLevels(AnnotatedLines);
1400     ContinuationIndenter Indenter(Style, SourceMgr, Whitespaces, Encoding,
1401                                   BinPackInconclusiveFunctions);
1402     UnwrappedLineFormatter Formatter(&Indenter, &Whitespaces, Style);
1403     Formatter.format(AnnotatedLines, /*DryRun=*/false);
1404     return Whitespaces.generateReplacements();
1405   }
1406 
1407 private:
1408   // Determines which lines are affected by the SourceRanges given as input.
1409   // Returns \c true if at least one line between I and E or one of their
1410   // children is affected.
1411   bool computeAffectedLines(SmallVectorImpl<AnnotatedLine *>::iterator I,
1412                             SmallVectorImpl<AnnotatedLine *>::iterator E) {
1413     bool SomeLineAffected = false;
1414     const AnnotatedLine *PreviousLine = NULL;
1415     while (I != E) {
1416       AnnotatedLine *Line = *I;
1417       Line->LeadingEmptyLinesAffected = affectsLeadingEmptyLines(*Line->First);
1418 
1419       // If a line is part of a preprocessor directive, it needs to be formatted
1420       // if any token within the directive is affected.
1421       if (Line->InPPDirective) {
1422         FormatToken *Last = Line->Last;
1423         SmallVectorImpl<AnnotatedLine *>::iterator PPEnd = I + 1;
1424         while (PPEnd != E && !(*PPEnd)->First->HasUnescapedNewline) {
1425           Last = (*PPEnd)->Last;
1426           ++PPEnd;
1427         }
1428 
1429         if (affectsTokenRange(*Line->First, *Last,
1430                               /*IncludeLeadingNewlines=*/false)) {
1431           SomeLineAffected = true;
1432           markAllAsAffected(I, PPEnd);
1433         }
1434         I = PPEnd;
1435         continue;
1436       }
1437 
1438       if (nonPPLineAffected(Line, PreviousLine))
1439         SomeLineAffected = true;
1440 
1441       PreviousLine = Line;
1442       ++I;
1443     }
1444     return SomeLineAffected;
1445   }
1446 
1447   // Determines whether 'Line' is affected by the SourceRanges given as input.
1448   // Returns \c true if line or one if its children is affected.
1449   bool nonPPLineAffected(AnnotatedLine *Line,
1450                          const AnnotatedLine *PreviousLine) {
1451     bool SomeLineAffected = false;
1452     Line->ChildrenAffected =
1453         computeAffectedLines(Line->Children.begin(), Line->Children.end());
1454     if (Line->ChildrenAffected)
1455       SomeLineAffected = true;
1456 
1457     // Stores whether one of the line's tokens is directly affected.
1458     bool SomeTokenAffected = false;
1459     // Stores whether we need to look at the leading newlines of the next token
1460     // in order to determine whether it was affected.
1461     bool IncludeLeadingNewlines = false;
1462 
1463     // Stores whether the first child line of any of this line's tokens is
1464     // affected.
1465     bool SomeFirstChildAffected = false;
1466 
1467     for (FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
1468       // Determine whether 'Tok' was affected.
1469       if (affectsTokenRange(*Tok, *Tok, IncludeLeadingNewlines))
1470         SomeTokenAffected = true;
1471 
1472       // Determine whether the first child of 'Tok' was affected.
1473       if (!Tok->Children.empty() && Tok->Children.front()->Affected)
1474         SomeFirstChildAffected = true;
1475 
1476       IncludeLeadingNewlines = Tok->Children.empty();
1477     }
1478 
1479     // Was this line moved, i.e. has it previously been on the same line as an
1480     // affected line?
1481     bool LineMoved = PreviousLine && PreviousLine->Affected &&
1482                      Line->First->NewlinesBefore == 0;
1483 
1484     bool IsContinuedComment = Line->First->is(tok::comment) &&
1485                               Line->First->Next == NULL &&
1486                               Line->First->NewlinesBefore < 2 && PreviousLine &&
1487                               PreviousLine->Affected &&
1488                               PreviousLine->Last->is(tok::comment);
1489 
1490     if (SomeTokenAffected || SomeFirstChildAffected || LineMoved ||
1491         IsContinuedComment) {
1492       Line->Affected = true;
1493       SomeLineAffected = true;
1494     }
1495     return SomeLineAffected;
1496   }
1497 
1498   // Marks all lines between I and E as well as all their children as affected.
1499   void markAllAsAffected(SmallVectorImpl<AnnotatedLine *>::iterator I,
1500                          SmallVectorImpl<AnnotatedLine *>::iterator E) {
1501     while (I != E) {
1502       (*I)->Affected = true;
1503       markAllAsAffected((*I)->Children.begin(), (*I)->Children.end());
1504       ++I;
1505     }
1506   }
1507 
1508   // Returns true if the range from 'First' to 'Last' intersects with one of the
1509   // input ranges.
1510   bool affectsTokenRange(const FormatToken &First, const FormatToken &Last,
1511                          bool IncludeLeadingNewlines) {
1512     SourceLocation Start = First.WhitespaceRange.getBegin();
1513     if (!IncludeLeadingNewlines)
1514       Start = Start.getLocWithOffset(First.LastNewlineOffset);
1515     SourceLocation End = Last.getStartOfNonWhitespace();
1516     if (Last.TokenText.size() > 0)
1517       End = End.getLocWithOffset(Last.TokenText.size() - 1);
1518     CharSourceRange Range = CharSourceRange::getCharRange(Start, End);
1519     return affectsCharSourceRange(Range);
1520   }
1521 
1522   // Returns true if one of the input ranges intersect the leading empty lines
1523   // before 'Tok'.
1524   bool affectsLeadingEmptyLines(const FormatToken &Tok) {
1525     CharSourceRange EmptyLineRange = CharSourceRange::getCharRange(
1526         Tok.WhitespaceRange.getBegin(),
1527         Tok.WhitespaceRange.getBegin().getLocWithOffset(Tok.LastNewlineOffset));
1528     return affectsCharSourceRange(EmptyLineRange);
1529   }
1530 
1531   // Returns true if 'Range' intersects with one of the input ranges.
1532   bool affectsCharSourceRange(const CharSourceRange &Range) {
1533     for (SmallVectorImpl<CharSourceRange>::const_iterator I = Ranges.begin(),
1534                                                           E = Ranges.end();
1535          I != E; ++I) {
1536       if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), I->getBegin()) &&
1537           !SourceMgr.isBeforeInTranslationUnit(I->getEnd(), Range.getBegin()))
1538         return true;
1539     }
1540     return false;
1541   }
1542 
1543   static bool inputUsesCRLF(StringRef Text) {
1544     return Text.count('\r') * 2 > Text.count('\n');
1545   }
1546 
1547   void
1548   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1549     unsigned CountBoundToVariable = 0;
1550     unsigned CountBoundToType = 0;
1551     bool HasCpp03IncompatibleFormat = false;
1552     bool HasBinPackedFunction = false;
1553     bool HasOnePerLineFunction = false;
1554     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1555       if (!AnnotatedLines[i]->First->Next)
1556         continue;
1557       FormatToken *Tok = AnnotatedLines[i]->First->Next;
1558       while (Tok->Next) {
1559         if (Tok->Type == TT_PointerOrReference) {
1560           bool SpacesBefore =
1561               Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1562           bool SpacesAfter = Tok->Next->WhitespaceRange.getBegin() !=
1563                              Tok->Next->WhitespaceRange.getEnd();
1564           if (SpacesBefore && !SpacesAfter)
1565             ++CountBoundToVariable;
1566           else if (!SpacesBefore && SpacesAfter)
1567             ++CountBoundToType;
1568         }
1569 
1570         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
1571           if (Tok->is(tok::coloncolon) &&
1572               Tok->Previous->Type == TT_TemplateOpener)
1573             HasCpp03IncompatibleFormat = true;
1574           if (Tok->Type == TT_TemplateCloser &&
1575               Tok->Previous->Type == TT_TemplateCloser)
1576             HasCpp03IncompatibleFormat = true;
1577         }
1578 
1579         if (Tok->PackingKind == PPK_BinPacked)
1580           HasBinPackedFunction = true;
1581         if (Tok->PackingKind == PPK_OnePerLine)
1582           HasOnePerLineFunction = true;
1583 
1584         Tok = Tok->Next;
1585       }
1586     }
1587     if (Style.DerivePointerBinding) {
1588       if (CountBoundToType > CountBoundToVariable)
1589         Style.PointerBindsToType = true;
1590       else if (CountBoundToType < CountBoundToVariable)
1591         Style.PointerBindsToType = false;
1592     }
1593     if (Style.Standard == FormatStyle::LS_Auto) {
1594       Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11
1595                                                   : FormatStyle::LS_Cpp03;
1596     }
1597     BinPackInconclusiveFunctions =
1598         HasBinPackedFunction || !HasOnePerLineFunction;
1599   }
1600 
1601   virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) {
1602     assert(!UnwrappedLines.empty());
1603     UnwrappedLines.back().push_back(TheLine);
1604   }
1605 
1606   virtual void finishRun() {
1607     UnwrappedLines.push_back(SmallVector<UnwrappedLine, 16>());
1608   }
1609 
1610   FormatStyle Style;
1611   Lexer &Lex;
1612   SourceManager &SourceMgr;
1613   WhitespaceManager Whitespaces;
1614   SmallVector<CharSourceRange, 8> Ranges;
1615   SmallVector<SmallVector<UnwrappedLine, 16>, 2> UnwrappedLines;
1616 
1617   encoding::Encoding Encoding;
1618   bool BinPackInconclusiveFunctions;
1619 };
1620 
1621 } // end anonymous namespace
1622 
1623 tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
1624                                SourceManager &SourceMgr,
1625                                std::vector<CharSourceRange> Ranges) {
1626   Formatter formatter(Style, Lex, SourceMgr, Ranges);
1627   return formatter.format();
1628 }
1629 
1630 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1631                                std::vector<tooling::Range> Ranges,
1632                                StringRef FileName) {
1633   FileManager Files((FileSystemOptions()));
1634   DiagnosticsEngine Diagnostics(
1635       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
1636       new DiagnosticOptions);
1637   SourceManager SourceMgr(Diagnostics, Files);
1638   llvm::MemoryBuffer *Buf = llvm::MemoryBuffer::getMemBuffer(Code, FileName);
1639   const clang::FileEntry *Entry =
1640       Files.getVirtualFile(FileName, Buf->getBufferSize(), 0);
1641   SourceMgr.overrideFileContents(Entry, Buf);
1642   FileID ID =
1643       SourceMgr.createFileID(Entry, SourceLocation(), clang::SrcMgr::C_User);
1644   Lexer Lex(ID, SourceMgr.getBuffer(ID), SourceMgr,
1645             getFormattingLangOpts(Style.Standard));
1646   SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
1647   std::vector<CharSourceRange> CharRanges;
1648   for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1649     SourceLocation Start = StartOfFile.getLocWithOffset(Ranges[i].getOffset());
1650     SourceLocation End = Start.getLocWithOffset(Ranges[i].getLength());
1651     CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
1652   }
1653   return reformat(Style, Lex, SourceMgr, CharRanges);
1654 }
1655 
1656 LangOptions getFormattingLangOpts(FormatStyle::LanguageStandard Standard) {
1657   LangOptions LangOpts;
1658   LangOpts.CPlusPlus = 1;
1659   LangOpts.CPlusPlus11 = Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1660   LangOpts.LineComment = 1;
1661   LangOpts.Bool = 1;
1662   LangOpts.ObjC1 = 1;
1663   LangOpts.ObjC2 = 1;
1664   return LangOpts;
1665 }
1666 
1667 const char *StyleOptionHelpDescription =
1668     "Coding style, currently supports:\n"
1669     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
1670     "Use -style=file to load style configuration from\n"
1671     ".clang-format file located in one of the parent\n"
1672     "directories of the source file (or current\n"
1673     "directory for stdin).\n"
1674     "Use -style=\"{key: value, ...}\" to set specific\n"
1675     "parameters, e.g.:\n"
1676     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
1677 
1678 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
1679   if (FileName.endswith_lower(".js")) {
1680     return FormatStyle::LK_JavaScript;
1681   }
1682   return FormatStyle::LK_Cpp;
1683 }
1684 
1685 FormatStyle getStyle(StringRef StyleName, StringRef FileName,
1686                      StringRef FallbackStyle) {
1687   FormatStyle Style = getLLVMStyle();
1688   Style.Language = getLanguageByFileName(FileName);
1689   if (!getPredefinedStyle(FallbackStyle, Style.Language, &Style)) {
1690     llvm::errs() << "Invalid fallback style \"" << FallbackStyle
1691                  << "\" using LLVM style\n";
1692     return Style;
1693   }
1694 
1695   if (StyleName.startswith("{")) {
1696     // Parse YAML/JSON style from the command line.
1697     if (llvm::error_code ec = parseConfiguration(StyleName, &Style)) {
1698       llvm::errs() << "Error parsing -style: " << ec.message() << ", using "
1699                    << FallbackStyle << " style\n";
1700     }
1701     return Style;
1702   }
1703 
1704   if (!StyleName.equals_lower("file")) {
1705     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
1706       llvm::errs() << "Invalid value for -style, using " << FallbackStyle
1707                    << " style\n";
1708     return Style;
1709   }
1710 
1711   // Look for .clang-format/_clang-format file in the file's parent directories.
1712   SmallString<128> UnsuitableConfigFiles;
1713   SmallString<128> Path(FileName);
1714   llvm::sys::fs::make_absolute(Path);
1715   for (StringRef Directory = Path; !Directory.empty();
1716        Directory = llvm::sys::path::parent_path(Directory)) {
1717     if (!llvm::sys::fs::is_directory(Directory))
1718       continue;
1719     SmallString<128> ConfigFile(Directory);
1720 
1721     llvm::sys::path::append(ConfigFile, ".clang-format");
1722     DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1723     bool IsFile = false;
1724     // Ignore errors from is_regular_file: we only need to know if we can read
1725     // the file or not.
1726     llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1727 
1728     if (!IsFile) {
1729       // Try _clang-format too, since dotfiles are not commonly used on Windows.
1730       ConfigFile = Directory;
1731       llvm::sys::path::append(ConfigFile, "_clang-format");
1732       DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1733       llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1734     }
1735 
1736     if (IsFile) {
1737       OwningPtr<llvm::MemoryBuffer> Text;
1738       if (llvm::error_code ec =
1739               llvm::MemoryBuffer::getFile(ConfigFile.c_str(), Text)) {
1740         llvm::errs() << ec.message() << "\n";
1741         break;
1742       }
1743       if (llvm::error_code ec = parseConfiguration(Text->getBuffer(), &Style)) {
1744         if (ec == llvm::errc::not_supported) {
1745           if (!UnsuitableConfigFiles.empty())
1746             UnsuitableConfigFiles.append(", ");
1747           UnsuitableConfigFiles.append(ConfigFile);
1748           continue;
1749         }
1750         llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message()
1751                      << "\n";
1752         break;
1753       }
1754       DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
1755       return Style;
1756     }
1757   }
1758   llvm::errs() << "Can't find usable .clang-format, using " << FallbackStyle
1759                << " style\n";
1760   if (!UnsuitableConfigFiles.empty()) {
1761     llvm::errs() << "Configuration file(s) do(es) not support "
1762                  << getLanguageName(Style.Language) << ": "
1763                  << UnsuitableConfigFiles << "\n";
1764   }
1765   return Style;
1766 }
1767 
1768 } // namespace format
1769 } // namespace clang
1770