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 <queue>
31 #include <string>
32 
33 namespace llvm {
34 namespace yaml {
35 template <>
36 struct ScalarEnumerationTraits<clang::format::FormatStyle::LanguageStandard> {
37   static void enumeration(IO &IO,
38                           clang::format::FormatStyle::LanguageStandard &Value) {
39     IO.enumCase(Value, "Cpp03", clang::format::FormatStyle::LS_Cpp03);
40     IO.enumCase(Value, "C++03", clang::format::FormatStyle::LS_Cpp03);
41     IO.enumCase(Value, "Cpp11", clang::format::FormatStyle::LS_Cpp11);
42     IO.enumCase(Value, "C++11", clang::format::FormatStyle::LS_Cpp11);
43     IO.enumCase(Value, "Auto", clang::format::FormatStyle::LS_Auto);
44   }
45 };
46 
47 template <>
48 struct ScalarEnumerationTraits<clang::format::FormatStyle::BraceBreakingStyle> {
49   static void
50   enumeration(IO &IO, clang::format::FormatStyle::BraceBreakingStyle &Value) {
51     IO.enumCase(Value, "Attach", clang::format::FormatStyle::BS_Attach);
52     IO.enumCase(Value, "Linux", clang::format::FormatStyle::BS_Linux);
53     IO.enumCase(Value, "Stroustrup", clang::format::FormatStyle::BS_Stroustrup);
54     IO.enumCase(Value, "Allman", clang::format::FormatStyle::BS_Allman);
55   }
56 };
57 
58 template <>
59 struct ScalarEnumerationTraits<
60     clang::format::FormatStyle::NamespaceIndentationKind> {
61   static void
62   enumeration(IO &IO,
63               clang::format::FormatStyle::NamespaceIndentationKind &Value) {
64     IO.enumCase(Value, "None", clang::format::FormatStyle::NI_None);
65     IO.enumCase(Value, "Inner", clang::format::FormatStyle::NI_Inner);
66     IO.enumCase(Value, "All", clang::format::FormatStyle::NI_All);
67   }
68 };
69 
70 template <> struct MappingTraits<clang::format::FormatStyle> {
71   static void mapping(llvm::yaml::IO &IO, clang::format::FormatStyle &Style) {
72     if (IO.outputting()) {
73       StringRef StylesArray[] = { "LLVM",    "Google", "Chromium",
74                                   "Mozilla", "WebKit" };
75       ArrayRef<StringRef> Styles(StylesArray);
76       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
77         StringRef StyleName(Styles[i]);
78         clang::format::FormatStyle PredefinedStyle;
79         if (clang::format::getPredefinedStyle(StyleName, &PredefinedStyle) &&
80             Style == PredefinedStyle) {
81           IO.mapOptional("# BasedOnStyle", StyleName);
82           break;
83         }
84       }
85     } else {
86       StringRef BasedOnStyle;
87       IO.mapOptional("BasedOnStyle", BasedOnStyle);
88       if (!BasedOnStyle.empty())
89         if (!clang::format::getPredefinedStyle(BasedOnStyle, &Style)) {
90           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
91           return;
92         }
93     }
94 
95     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
96     IO.mapOptional("ConstructorInitializerIndentWidth",
97                    Style.ConstructorInitializerIndentWidth);
98     IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
99     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
100     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
101                    Style.AllowAllParametersOfDeclarationOnNextLine);
102     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
103                    Style.AllowShortIfStatementsOnASingleLine);
104     IO.mapOptional("AllowShortLoopsOnASingleLine",
105                    Style.AllowShortLoopsOnASingleLine);
106     IO.mapOptional("AlwaysBreakTemplateDeclarations",
107                    Style.AlwaysBreakTemplateDeclarations);
108     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
109                    Style.AlwaysBreakBeforeMultilineStrings);
110     IO.mapOptional("BreakBeforeBinaryOperators",
111                    Style.BreakBeforeBinaryOperators);
112     IO.mapOptional("BreakConstructorInitializersBeforeComma",
113                    Style.BreakConstructorInitializersBeforeComma);
114     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
115     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
116     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
117                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
118     IO.mapOptional("DerivePointerBinding", Style.DerivePointerBinding);
119     IO.mapOptional("ExperimentalAutoDetectBinPacking",
120                    Style.ExperimentalAutoDetectBinPacking);
121     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
122     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
123     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
124     IO.mapOptional("ObjCSpaceBeforeProtocolList",
125                    Style.ObjCSpaceBeforeProtocolList);
126     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
127     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
128     IO.mapOptional("PenaltyBreakFirstLessLess",
129                    Style.PenaltyBreakFirstLessLess);
130     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
131     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
132                    Style.PenaltyReturnTypeOnItsOwnLine);
133     IO.mapOptional("PointerBindsToType", Style.PointerBindsToType);
134     IO.mapOptional("SpacesBeforeTrailingComments",
135                    Style.SpacesBeforeTrailingComments);
136     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
137     IO.mapOptional("Standard", Style.Standard);
138     IO.mapOptional("IndentWidth", Style.IndentWidth);
139     IO.mapOptional("TabWidth", Style.TabWidth);
140     IO.mapOptional("UseTab", Style.UseTab);
141     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
142     IO.mapOptional("IndentFunctionDeclarationAfterType",
143                    Style.IndentFunctionDeclarationAfterType);
144     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
145     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
146     IO.mapOptional("SpacesInCStyleCastParentheses",
147                    Style.SpacesInCStyleCastParentheses);
148     IO.mapOptional("SpaceAfterControlStatementKeyword",
149                    Style.SpaceAfterControlStatementKeyword);
150   }
151 };
152 }
153 }
154 
155 namespace clang {
156 namespace format {
157 
158 void setDefaultPenalties(FormatStyle &Style) {
159   Style.PenaltyBreakComment = 60;
160   Style.PenaltyBreakFirstLessLess = 120;
161   Style.PenaltyBreakString = 1000;
162   Style.PenaltyExcessCharacter = 1000000;
163 }
164 
165 FormatStyle getLLVMStyle() {
166   FormatStyle LLVMStyle;
167   LLVMStyle.AccessModifierOffset = -2;
168   LLVMStyle.AlignEscapedNewlinesLeft = false;
169   LLVMStyle.AlignTrailingComments = true;
170   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
171   LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
172   LLVMStyle.AllowShortLoopsOnASingleLine = false;
173   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
174   LLVMStyle.AlwaysBreakTemplateDeclarations = false;
175   LLVMStyle.BinPackParameters = true;
176   LLVMStyle.BreakBeforeBinaryOperators = false;
177   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
178   LLVMStyle.BreakConstructorInitializersBeforeComma = false;
179   LLVMStyle.ColumnLimit = 80;
180   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
181   LLVMStyle.ConstructorInitializerIndentWidth = 4;
182   LLVMStyle.Cpp11BracedListStyle = false;
183   LLVMStyle.DerivePointerBinding = false;
184   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
185   LLVMStyle.IndentCaseLabels = false;
186   LLVMStyle.IndentFunctionDeclarationAfterType = false;
187   LLVMStyle.IndentWidth = 2;
188   LLVMStyle.TabWidth = 8;
189   LLVMStyle.MaxEmptyLinesToKeep = 1;
190   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
191   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
192   LLVMStyle.PointerBindsToType = false;
193   LLVMStyle.SpacesBeforeTrailingComments = 1;
194   LLVMStyle.Standard = FormatStyle::LS_Cpp03;
195   LLVMStyle.UseTab = false;
196   LLVMStyle.SpacesInParentheses = false;
197   LLVMStyle.SpaceInEmptyParentheses = false;
198   LLVMStyle.SpacesInCStyleCastParentheses = false;
199   LLVMStyle.SpaceAfterControlStatementKeyword = true;
200 
201   setDefaultPenalties(LLVMStyle);
202   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
203 
204   return LLVMStyle;
205 }
206 
207 FormatStyle getGoogleStyle() {
208   FormatStyle GoogleStyle;
209   GoogleStyle.AccessModifierOffset = -1;
210   GoogleStyle.AlignEscapedNewlinesLeft = true;
211   GoogleStyle.AlignTrailingComments = true;
212   GoogleStyle.AllowAllParametersOfDeclarationOnNextLine = true;
213   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
214   GoogleStyle.AllowShortLoopsOnASingleLine = true;
215   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
216   GoogleStyle.AlwaysBreakTemplateDeclarations = true;
217   GoogleStyle.BinPackParameters = true;
218   GoogleStyle.BreakBeforeBinaryOperators = false;
219   GoogleStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
220   GoogleStyle.BreakConstructorInitializersBeforeComma = false;
221   GoogleStyle.ColumnLimit = 80;
222   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
223   GoogleStyle.ConstructorInitializerIndentWidth = 4;
224   GoogleStyle.Cpp11BracedListStyle = true;
225   GoogleStyle.DerivePointerBinding = true;
226   GoogleStyle.ExperimentalAutoDetectBinPacking = false;
227   GoogleStyle.IndentCaseLabels = true;
228   GoogleStyle.IndentFunctionDeclarationAfterType = true;
229   GoogleStyle.IndentWidth = 2;
230   GoogleStyle.TabWidth = 8;
231   GoogleStyle.MaxEmptyLinesToKeep = 1;
232   GoogleStyle.NamespaceIndentation = FormatStyle::NI_None;
233   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
234   GoogleStyle.PointerBindsToType = true;
235   GoogleStyle.SpacesBeforeTrailingComments = 2;
236   GoogleStyle.Standard = FormatStyle::LS_Auto;
237   GoogleStyle.UseTab = false;
238   GoogleStyle.SpacesInParentheses = false;
239   GoogleStyle.SpaceInEmptyParentheses = false;
240   GoogleStyle.SpacesInCStyleCastParentheses = false;
241   GoogleStyle.SpaceAfterControlStatementKeyword = true;
242 
243   setDefaultPenalties(GoogleStyle);
244   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
245 
246   return GoogleStyle;
247 }
248 
249 FormatStyle getChromiumStyle() {
250   FormatStyle ChromiumStyle = getGoogleStyle();
251   ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
252   ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
253   ChromiumStyle.AllowShortLoopsOnASingleLine = false;
254   ChromiumStyle.BinPackParameters = false;
255   ChromiumStyle.DerivePointerBinding = false;
256   ChromiumStyle.Standard = FormatStyle::LS_Cpp03;
257   return ChromiumStyle;
258 }
259 
260 FormatStyle getMozillaStyle() {
261   FormatStyle MozillaStyle = getLLVMStyle();
262   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
263   MozillaStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
264   MozillaStyle.DerivePointerBinding = true;
265   MozillaStyle.IndentCaseLabels = true;
266   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
267   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
268   MozillaStyle.PointerBindsToType = true;
269   return MozillaStyle;
270 }
271 
272 FormatStyle getWebKitStyle() {
273   FormatStyle Style = getLLVMStyle();
274   Style.AccessModifierOffset = -4;
275   Style.AlignTrailingComments = false;
276   Style.BreakBeforeBinaryOperators = true;
277   Style.BreakBeforeBraces = FormatStyle::BS_Stroustrup;
278   Style.BreakConstructorInitializersBeforeComma = true;
279   Style.ColumnLimit = 0;
280   Style.IndentWidth = 4;
281   Style.NamespaceIndentation = FormatStyle::NI_Inner;
282   Style.PointerBindsToType = true;
283   return Style;
284 }
285 
286 bool getPredefinedStyle(StringRef Name, FormatStyle *Style) {
287   if (Name.equals_lower("llvm"))
288     *Style = getLLVMStyle();
289   else if (Name.equals_lower("chromium"))
290     *Style = getChromiumStyle();
291   else if (Name.equals_lower("mozilla"))
292     *Style = getMozillaStyle();
293   else if (Name.equals_lower("google"))
294     *Style = getGoogleStyle();
295   else if (Name.equals_lower("webkit"))
296     *Style = getWebKitStyle();
297   else
298     return false;
299 
300   return true;
301 }
302 
303 llvm::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
304   if (Text.trim().empty())
305     return llvm::make_error_code(llvm::errc::invalid_argument);
306   llvm::yaml::Input Input(Text);
307   Input >> *Style;
308   return Input.error();
309 }
310 
311 std::string configurationAsText(const FormatStyle &Style) {
312   std::string Text;
313   llvm::raw_string_ostream Stream(Text);
314   llvm::yaml::Output Output(Stream);
315   // We use the same mapping method for input and output, so we need a non-const
316   // reference here.
317   FormatStyle NonConstStyle = Style;
318   Output << NonConstStyle;
319   return Stream.str();
320 }
321 
322 namespace {
323 
324 class NoColumnLimitFormatter {
325 public:
326   NoColumnLimitFormatter(ContinuationIndenter *Indenter) : Indenter(Indenter) {}
327 
328   /// \brief Formats the line starting at \p State, simply keeping all of the
329   /// input's line breaking decisions.
330   void format(unsigned FirstIndent, const AnnotatedLine *Line) {
331     LineState State = Indenter->getInitialState(FirstIndent, Line);
332     while (State.NextToken != NULL) {
333       bool Newline =
334           Indenter->mustBreak(State) ||
335           (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
336       Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
337     }
338   }
339 
340 private:
341   ContinuationIndenter *Indenter;
342 };
343 
344 class UnwrappedLineFormatter {
345 public:
346   UnwrappedLineFormatter(ContinuationIndenter *Indenter,
347                          WhitespaceManager *Whitespaces,
348                          const FormatStyle &Style, const AnnotatedLine &Line)
349       : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style), Line(Line),
350         Count(0) {}
351 
352   /// \brief Formats an \c UnwrappedLine and returns the penalty.
353   ///
354   /// If \p DryRun is \c false, directly applies the changes.
355   unsigned format(unsigned FirstIndent, bool DryRun = false) {
356     LineState State = Indenter->getInitialState(FirstIndent, &Line);
357 
358     // If the ObjC method declaration does not fit on a line, we should format
359     // it with one arg per line.
360     if (Line.Type == LT_ObjCMethodDecl)
361       State.Stack.back().BreakBeforeParameter = true;
362 
363     // Find best solution in solution space.
364     return analyzeSolutionSpace(State, DryRun);
365   }
366 
367 private:
368   /// \brief An edge in the solution space from \c Previous->State to \c State,
369   /// inserting a newline dependent on the \c NewLine.
370   struct StateNode {
371     StateNode(const LineState &State, bool NewLine, StateNode *Previous)
372         : State(State), NewLine(NewLine), Previous(Previous) {}
373     LineState State;
374     bool NewLine;
375     StateNode *Previous;
376   };
377 
378   /// \brief A pair of <penalty, count> that is used to prioritize the BFS on.
379   ///
380   /// In case of equal penalties, we want to prefer states that were inserted
381   /// first. During state generation we make sure that we insert states first
382   /// that break the line as late as possible.
383   typedef std::pair<unsigned, unsigned> OrderedPenalty;
384 
385   /// \brief An item in the prioritized BFS search queue. The \c StateNode's
386   /// \c State has the given \c OrderedPenalty.
387   typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
388 
389   /// \brief The BFS queue type.
390   typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
391                               std::greater<QueueItem> > QueueType;
392 
393   /// \brief Analyze the entire solution space starting from \p InitialState.
394   ///
395   /// This implements a variant of Dijkstra's algorithm on the graph that spans
396   /// the solution space (\c LineStates are the nodes). The algorithm tries to
397   /// find the shortest path (the one with lowest penalty) from \p InitialState
398   /// to a state where all tokens are placed. Returns the penalty.
399   ///
400   /// If \p DryRun is \c false, directly applies the changes.
401   unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun = false) {
402     std::set<LineState> Seen;
403 
404     // Insert start element into queue.
405     StateNode *Node =
406         new (Allocator.Allocate()) StateNode(InitialState, false, NULL);
407     Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
408     ++Count;
409 
410     unsigned Penalty = 0;
411 
412     // While not empty, take first element and follow edges.
413     while (!Queue.empty()) {
414       Penalty = Queue.top().first.first;
415       StateNode *Node = Queue.top().second;
416       if (Node->State.NextToken == NULL) {
417         DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n");
418         break;
419       }
420       Queue.pop();
421 
422       // Cut off the analysis of certain solutions if the analysis gets too
423       // complex. See description of IgnoreStackForComparison.
424       if (Count > 10000)
425         Node->State.IgnoreStackForComparison = true;
426 
427       if (!Seen.insert(Node->State).second)
428         // State already examined with lower penalty.
429         continue;
430 
431       addNextStateToQueue(Penalty, Node, /*NewLine=*/false);
432       addNextStateToQueue(Penalty, Node, /*NewLine=*/true);
433     }
434 
435     if (Queue.empty())
436       // We were unable to find a solution, do nothing.
437       // FIXME: Add diagnostic?
438       return 0;
439 
440     // Reconstruct the solution.
441     if (!DryRun)
442       reconstructPath(InitialState, Queue.top().second);
443 
444     DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n");
445     DEBUG(llvm::dbgs() << "---\n");
446 
447     return Penalty;
448   }
449 
450   void reconstructPath(LineState &State, StateNode *Current) {
451     std::deque<StateNode *> Path;
452     // We do not need a break before the initial token.
453     while (Current->Previous) {
454       Path.push_front(Current);
455       Current = Current->Previous;
456     }
457     for (std::deque<StateNode *>::iterator I = Path.begin(), E = Path.end();
458          I != E; ++I) {
459       unsigned Penalty = 0;
460       formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
461       Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
462 
463       DEBUG({
464         if ((*I)->NewLine) {
465           llvm::dbgs() << "Penalty for placing "
466                        << (*I)->Previous->State.NextToken->Tok.getName() << ": "
467                        << Penalty << "\n";
468         }
469       });
470     }
471   }
472 
473   /// \brief Add the following state to the analysis queue \c Queue.
474   ///
475   /// Assume the current state is \p PreviousNode and has been reached with a
476   /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
477   void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
478                            bool NewLine) {
479     if (NewLine && !Indenter->canBreak(PreviousNode->State))
480       return;
481     if (!NewLine && Indenter->mustBreak(PreviousNode->State))
482       return;
483 
484     StateNode *Node = new (Allocator.Allocate())
485         StateNode(PreviousNode->State, NewLine, PreviousNode);
486     if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
487       return;
488 
489     Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
490 
491     Queue.push(QueueItem(OrderedPenalty(Penalty, Count), Node));
492     ++Count;
493   }
494 
495   /// \brief If the \p State's next token is an r_brace closing a nested block,
496   /// format the nested block before it.
497   ///
498   /// Returns \c true if all children could be placed successfully and adapts
499   /// \p Penalty as well as \p State. If \p DryRun is false, also directly
500   /// creates changes using \c Whitespaces.
501   ///
502   /// The crucial idea here is that children always get formatted upon
503   /// encountering the closing brace right after the nested block. Now, if we
504   /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is
505   /// \c false), the entire block has to be kept on the same line (which is only
506   /// possible if it fits on the line, only contains a single statement, etc.
507   ///
508   /// If \p NewLine is true, we format the nested block on separate lines, i.e.
509   /// break after the "{", format all lines with correct indentation and the put
510   /// the closing "}" on yet another new line.
511   ///
512   /// This enables us to keep the simple structure of the
513   /// \c UnwrappedLineFormatter, where we only have two options for each token:
514   /// break or don't break.
515   bool formatChildren(LineState &State, bool NewLine, bool DryRun,
516                       unsigned &Penalty) {
517     const FormatToken &LBrace = *State.NextToken->Previous;
518     if (LBrace.isNot(tok::l_brace) || LBrace.BlockKind != BK_Block ||
519         LBrace.Children.size() == 0)
520       // The previous token does not open a block. Nothing to do. We don't
521       // assert so that we can simply call this function for all tokens.
522       return true;
523 
524     if (NewLine) {
525       unsigned ParentIndent = State.Stack.back().Indent;
526       for (SmallVector<AnnotatedLine *, 1>::const_iterator
527                I = LBrace.Children.begin(),
528                E = LBrace.Children.end();
529            I != E; ++I) {
530         unsigned Indent =
531             ParentIndent + ((*I)->Level - Line.Level) * Style.IndentWidth;
532         if (!DryRun)
533           Whitespaces->replaceWhitespace(
534               *(*I)->First, /*Newlines=*/1, /*Spaces=*/Indent,
535               /*StartOfTokenColumn=*/Indent, Line.InPPDirective);
536         UnwrappedLineFormatter Formatter(Indenter, Whitespaces, Style, **I);
537         Penalty += Formatter.format(Indent, DryRun);
538       }
539       return true;
540     }
541 
542     if (LBrace.Children.size() > 1)
543       return false; // Cannot merge multiple statements into a single line.
544 
545     // We can't put the closing "}" on a line with a trailing comment.
546     if (LBrace.Children[0]->Last->isTrailingComment())
547       return false;
548 
549     if (!DryRun) {
550       Whitespaces->replaceWhitespace(*LBrace.Children[0]->First,
551                                      /*Newlines=*/0, /*Spaces=*/1,
552                                      /*StartOfTokenColumn=*/State.Column,
553                                      State.Line->InPPDirective);
554     }
555 
556     State.Column += 1 + LBrace.Children[0]->Last->TotalLength;
557     return true;
558   }
559 
560   ContinuationIndenter *Indenter;
561   WhitespaceManager *Whitespaces;
562   FormatStyle Style;
563   const AnnotatedLine &Line;
564 
565   llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
566   QueueType Queue;
567   // Increasing count of \c StateNode items we have created. This is used
568   // to create a deterministic order independent of the container.
569   unsigned Count;
570 };
571 
572 class FormatTokenLexer {
573 public:
574   FormatTokenLexer(Lexer &Lex, SourceManager &SourceMgr, FormatStyle &Style,
575                    encoding::Encoding Encoding)
576       : FormatTok(NULL), GreaterStashed(false), Column(0),
577         TrailingWhitespace(0), Lex(Lex), SourceMgr(SourceMgr), Style(Style),
578         IdentTable(getFormattingLangOpts()), Encoding(Encoding) {
579     Lex.SetKeepWhitespaceMode(true);
580   }
581 
582   ArrayRef<FormatToken *> lex() {
583     assert(Tokens.empty());
584     do {
585       Tokens.push_back(getNextToken());
586     } while (Tokens.back()->Tok.isNot(tok::eof));
587     return Tokens;
588   }
589 
590   IdentifierTable &getIdentTable() { return IdentTable; }
591 
592 private:
593   FormatToken *getNextToken() {
594     if (GreaterStashed) {
595       // Create a synthesized second '>' token.
596       // FIXME: Increment Column and set OriginalColumn.
597       Token Greater = FormatTok->Tok;
598       FormatTok = new (Allocator.Allocate()) FormatToken;
599       FormatTok->Tok = Greater;
600       SourceLocation GreaterLocation =
601           FormatTok->Tok.getLocation().getLocWithOffset(1);
602       FormatTok->WhitespaceRange =
603           SourceRange(GreaterLocation, GreaterLocation);
604       FormatTok->TokenText = ">";
605       FormatTok->CodePointCount = 1;
606       GreaterStashed = false;
607       return FormatTok;
608     }
609 
610     FormatTok = new (Allocator.Allocate()) FormatToken;
611     readRawToken(*FormatTok);
612     SourceLocation WhitespaceStart =
613         FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
614     if (SourceMgr.getFileOffset(WhitespaceStart) == 0)
615       FormatTok->IsFirst = true;
616 
617     // Consume and record whitespace until we find a significant token.
618     unsigned WhitespaceLength = TrailingWhitespace;
619     while (FormatTok->Tok.is(tok::unknown)) {
620       for (int i = 0, e = FormatTok->TokenText.size(); i != e; ++i) {
621         switch (FormatTok->TokenText[i]) {
622         case '\n':
623           ++FormatTok->NewlinesBefore;
624           // FIXME: This is technically incorrect, as it could also
625           // be a literal backslash at the end of the line.
626           if (i == 0 || FormatTok->TokenText[i-1] != '\\')
627             FormatTok->HasUnescapedNewline = true;
628           FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
629           Column = 0;
630           break;
631         case ' ':
632           ++Column;
633           break;
634         case '\t':
635           Column += Style.TabWidth - Column % Style.TabWidth;
636           break;
637         default:
638           ++Column;
639           break;
640         }
641       }
642 
643       WhitespaceLength += FormatTok->Tok.getLength();
644 
645       readRawToken(*FormatTok);
646     }
647 
648     // In case the token starts with escaped newlines, we want to
649     // take them into account as whitespace - this pattern is quite frequent
650     // in macro definitions.
651     // FIXME: What do we want to do with other escaped spaces, and escaped
652     // spaces or newlines in the middle of tokens?
653     // FIXME: Add a more explicit test.
654     while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
655            FormatTok->TokenText[1] == '\n') {
656       // FIXME: ++FormatTok->NewlinesBefore is missing...
657       WhitespaceLength += 2;
658       Column = 0;
659       FormatTok->TokenText = FormatTok->TokenText.substr(2);
660     }
661     FormatTok->OriginalColumn = Column;
662 
663     TrailingWhitespace = 0;
664     if (FormatTok->Tok.is(tok::comment)) {
665       // FIXME: Add the trimmed whitespace to Column.
666       StringRef UntrimmedText = FormatTok->TokenText;
667       FormatTok->TokenText = FormatTok->TokenText.rtrim();
668       TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
669     } else if (FormatTok->Tok.is(tok::raw_identifier)) {
670       IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
671       FormatTok->Tok.setIdentifierInfo(&Info);
672       FormatTok->Tok.setKind(Info.getTokenID());
673     } else if (FormatTok->Tok.is(tok::greatergreater)) {
674       FormatTok->Tok.setKind(tok::greater);
675       FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
676       GreaterStashed = true;
677     }
678 
679     // Now FormatTok is the next non-whitespace token.
680     FormatTok->CodePointCount =
681         encoding::getCodePointCount(FormatTok->TokenText, Encoding);
682 
683     if (FormatTok->isOneOf(tok::string_literal, tok::comment)) {
684       StringRef Text = FormatTok->TokenText;
685       size_t FirstNewlinePos = Text.find('\n');
686       if (FirstNewlinePos != StringRef::npos) {
687         // FIXME: Handle embedded tabs.
688         FormatTok->FirstLineColumnWidth = encoding::columnWidthWithTabs(
689             Text.substr(0, FirstNewlinePos), 0, Style.TabWidth, Encoding);
690         FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
691             Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth,
692             Encoding);
693       }
694     }
695     // FIXME: Add the CodePointCount to Column.
696     FormatTok->WhitespaceRange = SourceRange(
697         WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
698     return FormatTok;
699   }
700 
701   FormatToken *FormatTok;
702   bool GreaterStashed;
703   unsigned Column;
704   unsigned TrailingWhitespace;
705   Lexer &Lex;
706   SourceManager &SourceMgr;
707   FormatStyle &Style;
708   IdentifierTable IdentTable;
709   encoding::Encoding Encoding;
710   llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
711   SmallVector<FormatToken *, 16> Tokens;
712 
713   void readRawToken(FormatToken &Tok) {
714     Lex.LexFromRawLexer(Tok.Tok);
715     Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
716                               Tok.Tok.getLength());
717     // For formatting, treat unterminated string literals like normal string
718     // literals.
719     if (Tok.is(tok::unknown) && !Tok.TokenText.empty() &&
720         Tok.TokenText[0] == '"') {
721       Tok.Tok.setKind(tok::string_literal);
722       Tok.IsUnterminatedLiteral = true;
723     }
724   }
725 };
726 
727 class Formatter : public UnwrappedLineConsumer {
728 public:
729   Formatter(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr,
730             const std::vector<CharSourceRange> &Ranges)
731       : Style(Style), Lex(Lex), SourceMgr(SourceMgr),
732         Whitespaces(SourceMgr, Style), Ranges(Ranges),
733         Encoding(encoding::detectEncoding(Lex.getBuffer())) {
734     DEBUG(llvm::dbgs() << "File encoding: "
735                        << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
736                                                                : "unknown")
737                        << "\n");
738   }
739 
740   virtual ~Formatter() {
741     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
742       delete AnnotatedLines[i];
743     }
744   }
745 
746   tooling::Replacements format() {
747     FormatTokenLexer Tokens(Lex, SourceMgr, Style, Encoding);
748 
749     UnwrappedLineParser Parser(Style, Tokens.lex(), *this);
750     bool StructuralError = Parser.parse();
751     TokenAnnotator Annotator(Style, Tokens.getIdentTable().get("in"));
752     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
753       Annotator.annotate(*AnnotatedLines[i]);
754     }
755     deriveLocalStyle();
756     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
757       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
758     }
759 
760     // Adapt level to the next line if this is a comment.
761     // FIXME: Can/should this be done in the UnwrappedLineParser?
762     const AnnotatedLine *NextNonCommentLine = NULL;
763     for (unsigned i = AnnotatedLines.size() - 1; i > 0; --i) {
764       if (NextNonCommentLine && AnnotatedLines[i]->First->is(tok::comment) &&
765           !AnnotatedLines[i]->First->Next)
766         AnnotatedLines[i]->Level = NextNonCommentLine->Level;
767       else
768         NextNonCommentLine = AnnotatedLines[i]->First->isNot(tok::r_brace)
769                                  ? AnnotatedLines[i]
770                                  : NULL;
771     }
772 
773     std::vector<int> IndentForLevel;
774     bool PreviousLineWasTouched = false;
775     const FormatToken *PreviousLineLastToken = 0;
776     bool FormatPPDirective = false;
777     for (std::vector<AnnotatedLine *>::iterator I = AnnotatedLines.begin(),
778                                                 E = AnnotatedLines.end();
779          I != E; ++I) {
780       const AnnotatedLine &TheLine = **I;
781       const FormatToken *FirstTok = TheLine.First;
782       int Offset = getIndentOffset(*TheLine.First);
783 
784       // Check whether this line is part of a formatted preprocessor directive.
785       if (FirstTok->HasUnescapedNewline)
786         FormatPPDirective = false;
787       if (!FormatPPDirective && TheLine.InPPDirective &&
788           (touchesLine(TheLine) || touchesPPDirective(I + 1, E)))
789         FormatPPDirective = true;
790 
791       // Determine indent and try to merge multiple unwrapped lines.
792       while (IndentForLevel.size() <= TheLine.Level)
793         IndentForLevel.push_back(-1);
794       IndentForLevel.resize(TheLine.Level + 1);
795       unsigned Indent = getIndent(IndentForLevel, TheLine.Level);
796       if (static_cast<int>(Indent) + Offset >= 0)
797         Indent += Offset;
798       tryFitMultipleLinesInOne(Indent, I, E);
799 
800       bool WasMoved = PreviousLineWasTouched && FirstTok->NewlinesBefore == 0;
801       if (TheLine.First->is(tok::eof)) {
802         if (PreviousLineWasTouched) {
803           unsigned NewLines = std::min(FirstTok->NewlinesBefore, 1u);
804           Whitespaces.replaceWhitespace(*TheLine.First, NewLines, /*Indent*/ 0,
805                                         /*TargetColumn*/ 0);
806         }
807       } else if (TheLine.Type != LT_Invalid &&
808                  (WasMoved || FormatPPDirective || touchesLine(TheLine))) {
809         unsigned LevelIndent = getIndent(IndentForLevel, TheLine.Level);
810         if (FirstTok->WhitespaceRange.isValid() &&
811             // Insert a break even if there is a structural error in case where
812             // we break apart a line consisting of multiple unwrapped lines.
813             (FirstTok->NewlinesBefore == 0 || !StructuralError)) {
814           formatFirstToken(*TheLine.First, PreviousLineLastToken, Indent,
815                            TheLine.InPPDirective);
816         } else {
817           Indent = LevelIndent = FirstTok->OriginalColumn;
818         }
819         ContinuationIndenter Indenter(Style, SourceMgr, Whitespaces, Encoding,
820                                       BinPackInconclusiveFunctions);
821 
822         // If everything fits on a single line, just put it there.
823         unsigned ColumnLimit = Style.ColumnLimit;
824         AnnotatedLine *NextLine = *(I + 1);
825         if ((I + 1) != E && NextLine->InPPDirective &&
826             !NextLine->First->HasUnescapedNewline)
827           ColumnLimit = getColumnLimit(TheLine.InPPDirective);
828 
829         if (TheLine.Last->TotalLength + Indent <= ColumnLimit) {
830           LineState State = Indenter.getInitialState(Indent, &TheLine);
831           while (State.NextToken != NULL)
832             Indenter.addTokenToState(State, false, false);
833         } else if (Style.ColumnLimit == 0) {
834           NoColumnLimitFormatter Formatter(&Indenter);
835           Formatter.format(Indent, &TheLine);
836         } else {
837           UnwrappedLineFormatter Formatter(&Indenter, &Whitespaces, Style,
838                                            TheLine);
839           Formatter.format(Indent);
840         }
841 
842         IndentForLevel[TheLine.Level] = LevelIndent;
843         PreviousLineWasTouched = true;
844       } else {
845         // Format the first token if necessary, and notify the WhitespaceManager
846         // about the unchanged whitespace.
847         for (const FormatToken *Tok = TheLine.First; Tok != NULL;
848              Tok = Tok->Next) {
849           if (Tok == TheLine.First &&
850               (Tok->NewlinesBefore > 0 || Tok->IsFirst)) {
851             unsigned LevelIndent = Tok->OriginalColumn;
852             // Remove trailing whitespace of the previous line if it was
853             // touched.
854             if (PreviousLineWasTouched || touchesEmptyLineBefore(TheLine)) {
855               formatFirstToken(*Tok, PreviousLineLastToken, LevelIndent,
856                                TheLine.InPPDirective);
857             } else {
858               Whitespaces.addUntouchableToken(*Tok, TheLine.InPPDirective);
859             }
860 
861             if (static_cast<int>(LevelIndent) - Offset >= 0)
862               LevelIndent -= Offset;
863             if (Tok->isNot(tok::comment))
864               IndentForLevel[TheLine.Level] = LevelIndent;
865           } else {
866             Whitespaces.addUntouchableToken(*Tok, TheLine.InPPDirective);
867           }
868         }
869         // If we did not reformat this unwrapped line, the column at the end of
870         // the last token is unchanged - thus, we can calculate the end of the
871         // last token.
872         PreviousLineWasTouched = false;
873       }
874       PreviousLineLastToken = TheLine.Last;
875     }
876     return Whitespaces.generateReplacements();
877   }
878 
879 private:
880   void deriveLocalStyle() {
881     unsigned CountBoundToVariable = 0;
882     unsigned CountBoundToType = 0;
883     bool HasCpp03IncompatibleFormat = false;
884     bool HasBinPackedFunction = false;
885     bool HasOnePerLineFunction = false;
886     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
887       if (!AnnotatedLines[i]->First->Next)
888         continue;
889       FormatToken *Tok = AnnotatedLines[i]->First->Next;
890       while (Tok->Next) {
891         if (Tok->Type == TT_PointerOrReference) {
892           bool SpacesBefore =
893               Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
894           bool SpacesAfter = Tok->Next->WhitespaceRange.getBegin() !=
895                              Tok->Next->WhitespaceRange.getEnd();
896           if (SpacesBefore && !SpacesAfter)
897             ++CountBoundToVariable;
898           else if (!SpacesBefore && SpacesAfter)
899             ++CountBoundToType;
900         }
901 
902         if (Tok->Type == TT_TemplateCloser &&
903             Tok->Previous->Type == TT_TemplateCloser &&
904             Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd())
905           HasCpp03IncompatibleFormat = true;
906 
907         if (Tok->PackingKind == PPK_BinPacked)
908           HasBinPackedFunction = true;
909         if (Tok->PackingKind == PPK_OnePerLine)
910           HasOnePerLineFunction = true;
911 
912         Tok = Tok->Next;
913       }
914     }
915     if (Style.DerivePointerBinding) {
916       if (CountBoundToType > CountBoundToVariable)
917         Style.PointerBindsToType = true;
918       else if (CountBoundToType < CountBoundToVariable)
919         Style.PointerBindsToType = false;
920     }
921     if (Style.Standard == FormatStyle::LS_Auto) {
922       Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11
923                                                   : FormatStyle::LS_Cpp03;
924     }
925     BinPackInconclusiveFunctions =
926         HasBinPackedFunction || !HasOnePerLineFunction;
927   }
928 
929   /// \brief Get the indent of \p Level from \p IndentForLevel.
930   ///
931   /// \p IndentForLevel must contain the indent for the level \c l
932   /// at \p IndentForLevel[l], or a value < 0 if the indent for
933   /// that level is unknown.
934   unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) {
935     if (IndentForLevel[Level] != -1)
936       return IndentForLevel[Level];
937     if (Level == 0)
938       return 0;
939     return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth;
940   }
941 
942   /// \brief Get the offset of the line relatively to the level.
943   ///
944   /// For example, 'public:' labels in classes are offset by 1 or 2
945   /// characters to the left from their level.
946   int getIndentOffset(const FormatToken &RootToken) {
947     if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier())
948       return Style.AccessModifierOffset;
949     return 0;
950   }
951 
952   /// \brief Tries to merge lines into one.
953   ///
954   /// This will change \c Line and \c AnnotatedLine to contain the merged line,
955   /// if possible; note that \c I will be incremented when lines are merged.
956   void tryFitMultipleLinesInOne(unsigned Indent,
957                                 std::vector<AnnotatedLine *>::iterator &I,
958                                 std::vector<AnnotatedLine *>::iterator E) {
959     // We can never merge stuff if there are trailing line comments.
960     AnnotatedLine *TheLine = *I;
961     if (TheLine->Last->Type == TT_LineComment)
962       return;
963 
964     if (Indent > Style.ColumnLimit)
965       return;
966 
967     unsigned Limit = Style.ColumnLimit - Indent;
968     // If we already exceed the column limit, we set 'Limit' to 0. The different
969     // tryMerge..() functions can then decide whether to still do merging.
970     Limit = TheLine->Last->TotalLength > Limit
971                 ? 0
972                 : Limit - TheLine->Last->TotalLength;
973 
974     if (I + 1 == E || (*(I + 1))->Type == LT_Invalid)
975       return;
976 
977     if (TheLine->Last->is(tok::l_brace)) {
978       tryMergeSimpleBlock(I, E, Limit);
979     } else if (Style.AllowShortIfStatementsOnASingleLine &&
980                TheLine->First->is(tok::kw_if)) {
981       tryMergeSimpleControlStatement(I, E, Limit);
982     } else if (Style.AllowShortLoopsOnASingleLine &&
983                TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
984       tryMergeSimpleControlStatement(I, E, Limit);
985     } else if (TheLine->InPPDirective && (TheLine->First->HasUnescapedNewline ||
986                                           TheLine->First->IsFirst)) {
987       tryMergeSimplePPDirective(I, E, Limit);
988     }
989   }
990 
991   void tryMergeSimplePPDirective(std::vector<AnnotatedLine *>::iterator &I,
992                                  std::vector<AnnotatedLine *>::iterator E,
993                                  unsigned Limit) {
994     if (Limit == 0)
995       return;
996     AnnotatedLine &Line = **I;
997     if (!(*(I + 1))->InPPDirective || (*(I + 1))->First->HasUnescapedNewline)
998       return;
999     if (I + 2 != E && (*(I + 2))->InPPDirective &&
1000         !(*(I + 2))->First->HasUnescapedNewline)
1001       return;
1002     if (1 + (*(I + 1))->Last->TotalLength > Limit)
1003       return;
1004     join(Line, **(++I));
1005   }
1006 
1007   void tryMergeSimpleControlStatement(std::vector<AnnotatedLine *>::iterator &I,
1008                                       std::vector<AnnotatedLine *>::iterator E,
1009                                       unsigned Limit) {
1010     if (Limit == 0)
1011       return;
1012     if (Style.BreakBeforeBraces == FormatStyle::BS_Allman &&
1013         (*(I + 1))->First->is(tok::l_brace))
1014       return;
1015     if ((*(I + 1))->InPPDirective != (*I)->InPPDirective ||
1016         ((*(I + 1))->InPPDirective && (*(I + 1))->First->HasUnescapedNewline))
1017       return;
1018     AnnotatedLine &Line = **I;
1019     if (Line.Last->isNot(tok::r_paren))
1020       return;
1021     if (1 + (*(I + 1))->Last->TotalLength > Limit)
1022       return;
1023     if ((*(I + 1))->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for,
1024                                    tok::kw_while) ||
1025         (*(I + 1))->First->Type == TT_LineComment)
1026       return;
1027     // Only inline simple if's (no nested if or else).
1028     if (I + 2 != E && Line.First->is(tok::kw_if) &&
1029         (*(I + 2))->First->is(tok::kw_else))
1030       return;
1031     join(Line, **(++I));
1032   }
1033 
1034   void tryMergeSimpleBlock(std::vector<AnnotatedLine *>::iterator &I,
1035                            std::vector<AnnotatedLine *>::iterator E,
1036                            unsigned Limit) {
1037     // No merging if the brace already is on the next line.
1038     if (Style.BreakBeforeBraces != FormatStyle::BS_Attach)
1039       return;
1040 
1041     // First, check that the current line allows merging. This is the case if
1042     // we're not in a control flow statement and the last token is an opening
1043     // brace.
1044     AnnotatedLine &Line = **I;
1045     if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::r_brace,
1046                             tok::kw_else, tok::kw_try, tok::kw_catch,
1047                             tok::kw_for,
1048                             // This gets rid of all ObjC @ keywords and methods.
1049                             tok::at, tok::minus, tok::plus))
1050       return;
1051 
1052     FormatToken *Tok = (*(I + 1))->First;
1053     if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
1054         (Tok->getNextNonComment() == NULL ||
1055          Tok->getNextNonComment()->is(tok::semi))) {
1056       // We merge empty blocks even if the line exceeds the column limit.
1057       Tok->SpacesRequiredBefore = 0;
1058       Tok->CanBreakBefore = true;
1059       join(Line, **(I + 1));
1060       I += 1;
1061     } else if (Limit != 0 && Line.First->isNot(tok::kw_namespace)) {
1062       // Check that we still have three lines and they fit into the limit.
1063       if (I + 2 == E || (*(I + 2))->Type == LT_Invalid ||
1064           !nextTwoLinesFitInto(I, Limit))
1065         return;
1066 
1067       // Second, check that the next line does not contain any braces - if it
1068       // does, readability declines when putting it into a single line.
1069       if ((*(I + 1))->Last->Type == TT_LineComment || Tok->MustBreakBefore)
1070         return;
1071       do {
1072         if (Tok->isOneOf(tok::l_brace, tok::r_brace))
1073           return;
1074         Tok = Tok->Next;
1075       } while (Tok != NULL);
1076 
1077       // Last, check that the third line contains a single closing brace.
1078       Tok = (*(I + 2))->First;
1079       if (Tok->getNextNonComment() != NULL || Tok->isNot(tok::r_brace) ||
1080           Tok->MustBreakBefore)
1081         return;
1082 
1083       join(Line, **(I + 1));
1084       join(Line, **(I + 2));
1085       I += 2;
1086     }
1087   }
1088 
1089   bool nextTwoLinesFitInto(std::vector<AnnotatedLine *>::iterator I,
1090                            unsigned Limit) {
1091     return 1 + (*(I + 1))->Last->TotalLength + 1 +
1092                (*(I + 2))->Last->TotalLength <=
1093            Limit;
1094   }
1095 
1096   void join(AnnotatedLine &A, const AnnotatedLine &B) {
1097     assert(!A.Last->Next);
1098     assert(!B.First->Previous);
1099     A.Last->Next = B.First;
1100     B.First->Previous = A.Last;
1101     unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
1102     for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
1103       Tok->TotalLength += LengthA;
1104       A.Last = Tok;
1105     }
1106   }
1107 
1108   bool touchesRanges(const CharSourceRange &Range) {
1109     for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1110       if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),
1111                                                Ranges[i].getBegin()) &&
1112           !SourceMgr.isBeforeInTranslationUnit(Ranges[i].getEnd(),
1113                                                Range.getBegin()))
1114         return true;
1115     }
1116     return false;
1117   }
1118 
1119   bool touchesLine(const AnnotatedLine &TheLine) {
1120     const FormatToken *First = TheLine.First;
1121     const FormatToken *Last = TheLine.Last;
1122     CharSourceRange LineRange = CharSourceRange::getCharRange(
1123         First->WhitespaceRange.getBegin().getLocWithOffset(
1124             First->LastNewlineOffset),
1125         Last->Tok.getLocation().getLocWithOffset(Last->TokenText.size() - 1));
1126     return touchesRanges(LineRange);
1127   }
1128 
1129   bool touchesPPDirective(std::vector<AnnotatedLine *>::iterator I,
1130                           std::vector<AnnotatedLine *>::iterator E) {
1131     for (; I != E; ++I) {
1132       if ((*I)->First->HasUnescapedNewline)
1133         return false;
1134       if (touchesLine(**I))
1135         return true;
1136     }
1137     return false;
1138   }
1139 
1140   bool touchesEmptyLineBefore(const AnnotatedLine &TheLine) {
1141     const FormatToken *First = TheLine.First;
1142     CharSourceRange LineRange = CharSourceRange::getCharRange(
1143         First->WhitespaceRange.getBegin(),
1144         First->WhitespaceRange.getBegin().getLocWithOffset(
1145             First->LastNewlineOffset));
1146     return touchesRanges(LineRange);
1147   }
1148 
1149   virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) {
1150     AnnotatedLines.push_back(new AnnotatedLine(TheLine));
1151   }
1152 
1153   /// \brief Add a new line and the required indent before the first Token
1154   /// of the \c UnwrappedLine if there was no structural parsing error.
1155   /// Returns the indent level of the \c UnwrappedLine.
1156   void formatFirstToken(const FormatToken &RootToken,
1157                         const FormatToken *PreviousToken, unsigned Indent,
1158                         bool InPPDirective) {
1159     unsigned Newlines =
1160         std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
1161     // Remove empty lines before "}" where applicable.
1162     if (RootToken.is(tok::r_brace) &&
1163         (!RootToken.Next ||
1164          (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)))
1165       Newlines = std::min(Newlines, 1u);
1166     if (Newlines == 0 && !RootToken.IsFirst)
1167       Newlines = 1;
1168 
1169     // Insert extra new line before access specifiers.
1170     if (PreviousToken && PreviousToken->isOneOf(tok::semi, tok::r_brace) &&
1171         RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
1172       ++Newlines;
1173 
1174     Whitespaces.replaceWhitespace(
1175         RootToken, Newlines, Indent, Indent,
1176         InPPDirective && !RootToken.HasUnescapedNewline);
1177   }
1178 
1179   unsigned getColumnLimit(bool InPPDirective) const {
1180     // In preprocessor directives reserve two chars for trailing " \"
1181     return Style.ColumnLimit - (InPPDirective ? 2 : 0);
1182   }
1183 
1184   FormatStyle Style;
1185   Lexer &Lex;
1186   SourceManager &SourceMgr;
1187   WhitespaceManager Whitespaces;
1188   std::vector<CharSourceRange> Ranges;
1189   std::vector<AnnotatedLine *> AnnotatedLines;
1190 
1191   encoding::Encoding Encoding;
1192   bool BinPackInconclusiveFunctions;
1193 };
1194 
1195 } // end anonymous namespace
1196 
1197 tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
1198                                SourceManager &SourceMgr,
1199                                std::vector<CharSourceRange> Ranges) {
1200   Formatter formatter(Style, Lex, SourceMgr, Ranges);
1201   return formatter.format();
1202 }
1203 
1204 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1205                                std::vector<tooling::Range> Ranges,
1206                                StringRef FileName) {
1207   FileManager Files((FileSystemOptions()));
1208   DiagnosticsEngine Diagnostics(
1209       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
1210       new DiagnosticOptions);
1211   SourceManager SourceMgr(Diagnostics, Files);
1212   llvm::MemoryBuffer *Buf = llvm::MemoryBuffer::getMemBuffer(Code, FileName);
1213   const clang::FileEntry *Entry =
1214       Files.getVirtualFile(FileName, Buf->getBufferSize(), 0);
1215   SourceMgr.overrideFileContents(Entry, Buf);
1216   FileID ID =
1217       SourceMgr.createFileID(Entry, SourceLocation(), clang::SrcMgr::C_User);
1218   Lexer Lex(ID, SourceMgr.getBuffer(ID), SourceMgr,
1219             getFormattingLangOpts(Style.Standard));
1220   SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
1221   std::vector<CharSourceRange> CharRanges;
1222   for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1223     SourceLocation Start = StartOfFile.getLocWithOffset(Ranges[i].getOffset());
1224     SourceLocation End = Start.getLocWithOffset(Ranges[i].getLength());
1225     CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
1226   }
1227   return reformat(Style, Lex, SourceMgr, CharRanges);
1228 }
1229 
1230 LangOptions getFormattingLangOpts(FormatStyle::LanguageStandard Standard) {
1231   LangOptions LangOpts;
1232   LangOpts.CPlusPlus = 1;
1233   LangOpts.CPlusPlus11 = Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1234   LangOpts.LineComment = 1;
1235   LangOpts.Bool = 1;
1236   LangOpts.ObjC1 = 1;
1237   LangOpts.ObjC2 = 1;
1238   return LangOpts;
1239 }
1240 
1241 } // namespace format
1242 } // namespace clang
1243