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 =
332         Indenter->getInitialState(FirstIndent, Line, /*DryRun=*/false);
333     while (State.NextToken != NULL) {
334       bool Newline =
335           Indenter->mustBreak(State) ||
336           (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
337       Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
338     }
339   }
340 
341 private:
342   ContinuationIndenter *Indenter;
343 };
344 
345 class UnwrappedLineFormatter {
346 public:
347   UnwrappedLineFormatter(ContinuationIndenter *Indenter,
348                          WhitespaceManager *Whitespaces,
349                          const FormatStyle &Style, const AnnotatedLine &Line)
350       : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style), Line(Line),
351         Count(0) {}
352 
353   /// \brief Formats an \c UnwrappedLine and returns the penalty.
354   ///
355   /// If \p DryRun is \c false, directly applies the changes.
356   unsigned format(unsigned FirstIndent, bool DryRun = false) {
357     LineState State = Indenter->getInitialState(FirstIndent, &Line, DryRun);
358 
359     // If the ObjC method declaration does not fit on a line, we should format
360     // it with one arg per line.
361     if (Line.Type == LT_ObjCMethodDecl)
362       State.Stack.back().BreakBeforeParameter = true;
363 
364     // Find best solution in solution space.
365     return analyzeSolutionSpace(State, DryRun);
366   }
367 
368 private:
369   /// \brief An edge in the solution space from \c Previous->State to \c State,
370   /// inserting a newline dependent on the \c NewLine.
371   struct StateNode {
372     StateNode(const LineState &State, bool NewLine, StateNode *Previous)
373         : State(State), NewLine(NewLine), Previous(Previous) {}
374     LineState State;
375     bool NewLine;
376     StateNode *Previous;
377   };
378 
379   /// \brief A pair of <penalty, count> that is used to prioritize the BFS on.
380   ///
381   /// In case of equal penalties, we want to prefer states that were inserted
382   /// first. During state generation we make sure that we insert states first
383   /// that break the line as late as possible.
384   typedef std::pair<unsigned, unsigned> OrderedPenalty;
385 
386   /// \brief An item in the prioritized BFS search queue. The \c StateNode's
387   /// \c State has the given \c OrderedPenalty.
388   typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
389 
390   /// \brief The BFS queue type.
391   typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
392                               std::greater<QueueItem> > QueueType;
393 
394   /// \brief Analyze the entire solution space starting from \p InitialState.
395   ///
396   /// This implements a variant of Dijkstra's algorithm on the graph that spans
397   /// the solution space (\c LineStates are the nodes). The algorithm tries to
398   /// find the shortest path (the one with lowest penalty) from \p InitialState
399   /// to a state where all tokens are placed. Returns the penalty.
400   ///
401   /// If \p DryRun is \c false, directly applies the changes.
402   unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun = false) {
403     std::set<LineState> Seen;
404 
405     // Insert start element into queue.
406     StateNode *Node =
407         new (Allocator.Allocate()) StateNode(InitialState, false, NULL);
408     Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
409     ++Count;
410 
411     unsigned Penalty = 0;
412 
413     // While not empty, take first element and follow edges.
414     while (!Queue.empty()) {
415       Penalty = Queue.top().first.first;
416       StateNode *Node = Queue.top().second;
417       if (Node->State.NextToken == NULL) {
418         DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n");
419         break;
420       }
421       Queue.pop();
422 
423       // Cut off the analysis of certain solutions if the analysis gets too
424       // complex. See description of IgnoreStackForComparison.
425       if (Count > 10000)
426         Node->State.IgnoreStackForComparison = true;
427 
428       if (!Seen.insert(Node->State).second)
429         // State already examined with lower penalty.
430         continue;
431 
432       addNextStateToQueue(Penalty, Node, /*NewLine=*/false);
433       addNextStateToQueue(Penalty, Node, /*NewLine=*/true);
434     }
435 
436     if (Queue.empty())
437       // We were unable to find a solution, do nothing.
438       // FIXME: Add diagnostic?
439       return 0;
440 
441     // Reconstruct the solution.
442     if (!DryRun)
443       reconstructPath(InitialState, Queue.top().second);
444 
445     DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n");
446     DEBUG(llvm::dbgs() << "---\n");
447 
448     return Penalty;
449   }
450 
451   void reconstructPath(LineState &State, StateNode *Current) {
452     std::deque<StateNode *> Path;
453     // We do not need a break before the initial token.
454     while (Current->Previous) {
455       Path.push_front(Current);
456       Current = Current->Previous;
457     }
458     for (std::deque<StateNode *>::iterator I = Path.begin(), E = Path.end();
459          I != E; ++I) {
460       unsigned Penalty = 0;
461       formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
462       Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
463 
464       DEBUG({
465         if ((*I)->NewLine) {
466           llvm::dbgs() << "Penalty for placing "
467                        << (*I)->Previous->State.NextToken->Tok.getName() << ": "
468                        << Penalty << "\n";
469         }
470       });
471     }
472   }
473 
474   /// \brief Add the following state to the analysis queue \c Queue.
475   ///
476   /// Assume the current state is \p PreviousNode and has been reached with a
477   /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
478   void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
479                            bool NewLine) {
480     if (NewLine && !Indenter->canBreak(PreviousNode->State))
481       return;
482     if (!NewLine && Indenter->mustBreak(PreviousNode->State))
483       return;
484 
485     StateNode *Node = new (Allocator.Allocate())
486         StateNode(PreviousNode->State, NewLine, PreviousNode);
487     if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
488       return;
489 
490     Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
491 
492     Queue.push(QueueItem(OrderedPenalty(Penalty, Count), Node));
493     ++Count;
494   }
495 
496   /// \brief If the \p State's next token is an r_brace closing a nested block,
497   /// format the nested block before it.
498   ///
499   /// Returns \c true if all children could be placed successfully and adapts
500   /// \p Penalty as well as \p State. If \p DryRun is false, also directly
501   /// creates changes using \c Whitespaces.
502   ///
503   /// The crucial idea here is that children always get formatted upon
504   /// encountering the closing brace right after the nested block. Now, if we
505   /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is
506   /// \c false), the entire block has to be kept on the same line (which is only
507   /// possible if it fits on the line, only contains a single statement, etc.
508   ///
509   /// If \p NewLine is true, we format the nested block on separate lines, i.e.
510   /// break after the "{", format all lines with correct indentation and the put
511   /// the closing "}" on yet another new line.
512   ///
513   /// This enables us to keep the simple structure of the
514   /// \c UnwrappedLineFormatter, where we only have two options for each token:
515   /// break or don't break.
516   bool formatChildren(LineState &State, bool NewLine, bool DryRun,
517                       unsigned &Penalty) {
518     const FormatToken &LBrace = *State.NextToken->Previous;
519     if (LBrace.isNot(tok::l_brace) || LBrace.BlockKind != BK_Block ||
520         LBrace.Children.size() == 0)
521       // The previous token does not open a block. Nothing to do. We don't
522       // assert so that we can simply call this function for all tokens.
523       return true;
524 
525     if (NewLine) {
526       unsigned ParentIndent = State.Stack.back().Indent;
527       for (SmallVector<AnnotatedLine *, 1>::const_iterator
528                I = LBrace.Children.begin(),
529                E = LBrace.Children.end();
530            I != E; ++I) {
531         unsigned Indent =
532             ParentIndent + ((*I)->Level - Line.Level) * Style.IndentWidth;
533         if (!DryRun)
534           Whitespaces->replaceWhitespace(
535               *(*I)->First, /*Newlines=*/1, /*Spaces=*/Indent,
536               /*StartOfTokenColumn=*/Indent, Line.InPPDirective);
537         UnwrappedLineFormatter Formatter(Indenter, Whitespaces, Style, **I);
538         Penalty += Formatter.format(Indent, DryRun);
539       }
540       return true;
541     }
542 
543     if (LBrace.Children.size() > 1)
544       return false; // Cannot merge multiple statements into a single line.
545 
546     // We can't put the closing "}" on a line with a trailing comment.
547     if (LBrace.Children[0]->Last->isTrailingComment())
548       return false;
549 
550     if (!DryRun) {
551       Whitespaces->replaceWhitespace(*LBrace.Children[0]->First,
552                                      /*Newlines=*/0, /*Spaces=*/1,
553                                      /*StartOfTokenColumn=*/State.Column,
554                                      State.Line->InPPDirective);
555     }
556 
557     State.Column += 1 + LBrace.Children[0]->Last->TotalLength;
558     return true;
559   }
560 
561   ContinuationIndenter *Indenter;
562   WhitespaceManager *Whitespaces;
563   FormatStyle Style;
564   const AnnotatedLine &Line;
565 
566   llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
567   QueueType Queue;
568   // Increasing count of \c StateNode items we have created. This is used
569   // to create a deterministic order independent of the container.
570   unsigned Count;
571 };
572 
573 class FormatTokenLexer {
574 public:
575   FormatTokenLexer(Lexer &Lex, SourceManager &SourceMgr, FormatStyle &Style,
576                    encoding::Encoding Encoding)
577       : FormatTok(NULL), GreaterStashed(false), Column(0),
578         TrailingWhitespace(0), Lex(Lex), SourceMgr(SourceMgr), Style(Style),
579         IdentTable(getFormattingLangOpts()), Encoding(Encoding) {
580     Lex.SetKeepWhitespaceMode(true);
581   }
582 
583   ArrayRef<FormatToken *> lex() {
584     assert(Tokens.empty());
585     do {
586       Tokens.push_back(getNextToken());
587     } while (Tokens.back()->Tok.isNot(tok::eof));
588     return Tokens;
589   }
590 
591   IdentifierTable &getIdentTable() { return IdentTable; }
592 
593 private:
594   FormatToken *getNextToken() {
595     if (GreaterStashed) {
596       // Create a synthesized second '>' token.
597       // FIXME: Increment Column and set OriginalColumn.
598       Token Greater = FormatTok->Tok;
599       FormatTok = new (Allocator.Allocate()) FormatToken;
600       FormatTok->Tok = Greater;
601       SourceLocation GreaterLocation =
602           FormatTok->Tok.getLocation().getLocWithOffset(1);
603       FormatTok->WhitespaceRange =
604           SourceRange(GreaterLocation, GreaterLocation);
605       FormatTok->TokenText = ">";
606       FormatTok->CodePointCount = 1;
607       GreaterStashed = false;
608       return FormatTok;
609     }
610 
611     FormatTok = new (Allocator.Allocate()) FormatToken;
612     readRawToken(*FormatTok);
613     SourceLocation WhitespaceStart =
614         FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
615     if (SourceMgr.getFileOffset(WhitespaceStart) == 0)
616       FormatTok->IsFirst = true;
617 
618     // Consume and record whitespace until we find a significant token.
619     unsigned WhitespaceLength = TrailingWhitespace;
620     while (FormatTok->Tok.is(tok::unknown)) {
621       for (int i = 0, e = FormatTok->TokenText.size(); i != e; ++i) {
622         switch (FormatTok->TokenText[i]) {
623         case '\n':
624           ++FormatTok->NewlinesBefore;
625           // FIXME: This is technically incorrect, as it could also
626           // be a literal backslash at the end of the line.
627           if (i == 0 || FormatTok->TokenText[i - 1] != '\\')
628             FormatTok->HasUnescapedNewline = true;
629           FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
630           Column = 0;
631           break;
632         case ' ':
633           ++Column;
634           break;
635         case '\t':
636           Column += Style.TabWidth - Column % Style.TabWidth;
637           break;
638         default:
639           ++Column;
640           break;
641         }
642       }
643 
644       WhitespaceLength += FormatTok->Tok.getLength();
645 
646       readRawToken(*FormatTok);
647     }
648 
649     // In case the token starts with escaped newlines, we want to
650     // take them into account as whitespace - this pattern is quite frequent
651     // in macro definitions.
652     // FIXME: What do we want to do with other escaped spaces, and escaped
653     // spaces or newlines in the middle of tokens?
654     // FIXME: Add a more explicit test.
655     while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
656            FormatTok->TokenText[1] == '\n') {
657       // FIXME: ++FormatTok->NewlinesBefore is missing...
658       WhitespaceLength += 2;
659       Column = 0;
660       FormatTok->TokenText = FormatTok->TokenText.substr(2);
661     }
662     FormatTok->OriginalColumn = Column;
663 
664     TrailingWhitespace = 0;
665     if (FormatTok->Tok.is(tok::comment)) {
666       // FIXME: Add the trimmed whitespace to Column.
667       StringRef UntrimmedText = FormatTok->TokenText;
668       FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
669       TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
670     } else if (FormatTok->Tok.is(tok::raw_identifier)) {
671       IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
672       FormatTok->Tok.setIdentifierInfo(&Info);
673       FormatTok->Tok.setKind(Info.getTokenID());
674     } else if (FormatTok->Tok.is(tok::greatergreater)) {
675       FormatTok->Tok.setKind(tok::greater);
676       FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
677       GreaterStashed = true;
678     }
679 
680     // Now FormatTok is the next non-whitespace token.
681     FormatTok->CodePointCount =
682         encoding::getCodePointCount(FormatTok->TokenText, Encoding);
683 
684     if (FormatTok->isOneOf(tok::string_literal, tok::comment)) {
685       StringRef Text = FormatTok->TokenText;
686       size_t FirstNewlinePos = Text.find('\n');
687       if (FirstNewlinePos != StringRef::npos) {
688         // FIXME: Handle embedded tabs.
689         FormatTok->FirstLineColumnWidth = encoding::columnWidthWithTabs(
690             Text.substr(0, FirstNewlinePos), 0, Style.TabWidth, Encoding);
691         FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
692             Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth,
693             Encoding);
694       }
695     }
696     // FIXME: Add the CodePointCount to Column.
697     FormatTok->WhitespaceRange = SourceRange(
698         WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
699     return FormatTok;
700   }
701 
702   FormatToken *FormatTok;
703   bool GreaterStashed;
704   unsigned Column;
705   unsigned TrailingWhitespace;
706   Lexer &Lex;
707   SourceManager &SourceMgr;
708   FormatStyle &Style;
709   IdentifierTable IdentTable;
710   encoding::Encoding Encoding;
711   llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
712   SmallVector<FormatToken *, 16> Tokens;
713 
714   void readRawToken(FormatToken &Tok) {
715     Lex.LexFromRawLexer(Tok.Tok);
716     Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
717                               Tok.Tok.getLength());
718     // For formatting, treat unterminated string literals like normal string
719     // literals.
720     if (Tok.is(tok::unknown) && !Tok.TokenText.empty() &&
721         Tok.TokenText[0] == '"') {
722       Tok.Tok.setKind(tok::string_literal);
723       Tok.IsUnterminatedLiteral = true;
724     }
725   }
726 };
727 
728 class Formatter : public UnwrappedLineConsumer {
729 public:
730   Formatter(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr,
731             const std::vector<CharSourceRange> &Ranges)
732       : Style(Style), Lex(Lex), SourceMgr(SourceMgr),
733         Whitespaces(SourceMgr, Style), Ranges(Ranges),
734         Encoding(encoding::detectEncoding(Lex.getBuffer())) {
735     DEBUG(llvm::dbgs() << "File encoding: "
736                        << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
737                                                                : "unknown")
738                        << "\n");
739   }
740 
741   virtual ~Formatter() {
742     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
743       delete AnnotatedLines[i];
744     }
745   }
746 
747   tooling::Replacements format() {
748     FormatTokenLexer Tokens(Lex, SourceMgr, Style, Encoding);
749 
750     UnwrappedLineParser Parser(Style, Tokens.lex(), *this);
751     bool StructuralError = Parser.parse();
752     TokenAnnotator Annotator(Style, Tokens.getIdentTable().get("in"));
753     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
754       Annotator.annotate(*AnnotatedLines[i]);
755     }
756     deriveLocalStyle();
757     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
758       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
759     }
760 
761     Annotator.setCommentLineLevels(AnnotatedLines);
762 
763     std::vector<int> IndentForLevel;
764     bool PreviousLineWasTouched = false;
765     const FormatToken *PreviousLineLastToken = 0;
766     bool FormatPPDirective = false;
767     for (SmallVectorImpl<AnnotatedLine *>::iterator I = AnnotatedLines.begin(),
768                                                     E = AnnotatedLines.end();
769          I != E; ++I) {
770       const AnnotatedLine &TheLine = **I;
771       const FormatToken *FirstTok = TheLine.First;
772       int Offset = getIndentOffset(*TheLine.First);
773 
774       // Check whether this line is part of a formatted preprocessor directive.
775       if (FirstTok->HasUnescapedNewline)
776         FormatPPDirective = false;
777       if (!FormatPPDirective && TheLine.InPPDirective &&
778           (touchesLine(TheLine) || touchesPPDirective(I + 1, E)))
779         FormatPPDirective = true;
780 
781       // Determine indent and try to merge multiple unwrapped lines.
782       while (IndentForLevel.size() <= TheLine.Level)
783         IndentForLevel.push_back(-1);
784       IndentForLevel.resize(TheLine.Level + 1);
785       unsigned Indent = getIndent(IndentForLevel, TheLine.Level);
786       if (static_cast<int>(Indent) + Offset >= 0)
787         Indent += Offset;
788       tryFitMultipleLinesInOne(Indent, I, E);
789 
790       bool WasMoved = PreviousLineWasTouched && FirstTok->NewlinesBefore == 0;
791       if (TheLine.First->is(tok::eof)) {
792         if (PreviousLineWasTouched) {
793           unsigned NewLines = std::min(FirstTok->NewlinesBefore, 1u);
794           Whitespaces.replaceWhitespace(*TheLine.First, NewLines, /*Indent*/ 0,
795                                         /*TargetColumn*/ 0);
796         }
797       } else if (TheLine.Type != LT_Invalid &&
798                  (WasMoved || FormatPPDirective || touchesLine(TheLine))) {
799         unsigned LevelIndent = getIndent(IndentForLevel, TheLine.Level);
800         if (FirstTok->WhitespaceRange.isValid() &&
801             // Insert a break even if there is a structural error in case where
802             // we break apart a line consisting of multiple unwrapped lines.
803             (FirstTok->NewlinesBefore == 0 || !StructuralError)) {
804           formatFirstToken(*TheLine.First, PreviousLineLastToken, Indent,
805                            TheLine.InPPDirective);
806         } else {
807           Indent = LevelIndent = FirstTok->OriginalColumn;
808         }
809         ContinuationIndenter Indenter(Style, SourceMgr, Whitespaces, Encoding,
810                                       BinPackInconclusiveFunctions);
811 
812         // If everything fits on a single line, just put it there.
813         unsigned ColumnLimit = Style.ColumnLimit;
814         AnnotatedLine *NextLine = *(I + 1);
815         if ((I + 1) != E && NextLine->InPPDirective &&
816             !NextLine->First->HasUnescapedNewline)
817           ColumnLimit = getColumnLimit(TheLine.InPPDirective);
818 
819         if (TheLine.Last->TotalLength + Indent <= ColumnLimit) {
820           LineState State =
821               Indenter.getInitialState(Indent, &TheLine, /*DryRun=*/false);
822           while (State.NextToken != NULL)
823             Indenter.addTokenToState(State, false, false);
824         } else if (Style.ColumnLimit == 0) {
825           NoColumnLimitFormatter Formatter(&Indenter);
826           Formatter.format(Indent, &TheLine);
827         } else {
828           UnwrappedLineFormatter Formatter(&Indenter, &Whitespaces, Style,
829                                            TheLine);
830           Formatter.format(Indent);
831         }
832 
833         IndentForLevel[TheLine.Level] = LevelIndent;
834         PreviousLineWasTouched = true;
835       } else {
836         // Format the first token if necessary, and notify the WhitespaceManager
837         // about the unchanged whitespace.
838         for (const FormatToken *Tok = TheLine.First; Tok != NULL;
839              Tok = Tok->Next) {
840           if (Tok == TheLine.First &&
841               (Tok->NewlinesBefore > 0 || Tok->IsFirst)) {
842             unsigned LevelIndent = Tok->OriginalColumn;
843             // Remove trailing whitespace of the previous line if it was
844             // touched.
845             if (PreviousLineWasTouched || touchesEmptyLineBefore(TheLine)) {
846               formatFirstToken(*Tok, PreviousLineLastToken, LevelIndent,
847                                TheLine.InPPDirective);
848             } else {
849               Whitespaces.addUntouchableToken(*Tok, TheLine.InPPDirective);
850             }
851 
852             if (static_cast<int>(LevelIndent) - Offset >= 0)
853               LevelIndent -= Offset;
854             if (Tok->isNot(tok::comment))
855               IndentForLevel[TheLine.Level] = LevelIndent;
856           } else {
857             Whitespaces.addUntouchableToken(*Tok, TheLine.InPPDirective);
858           }
859         }
860         // If we did not reformat this unwrapped line, the column at the end of
861         // the last token is unchanged - thus, we can calculate the end of the
862         // last token.
863         PreviousLineWasTouched = false;
864       }
865       PreviousLineLastToken = TheLine.Last;
866     }
867     return Whitespaces.generateReplacements();
868   }
869 
870 private:
871   void deriveLocalStyle() {
872     unsigned CountBoundToVariable = 0;
873     unsigned CountBoundToType = 0;
874     bool HasCpp03IncompatibleFormat = false;
875     bool HasBinPackedFunction = false;
876     bool HasOnePerLineFunction = false;
877     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
878       if (!AnnotatedLines[i]->First->Next)
879         continue;
880       FormatToken *Tok = AnnotatedLines[i]->First->Next;
881       while (Tok->Next) {
882         if (Tok->Type == TT_PointerOrReference) {
883           bool SpacesBefore =
884               Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
885           bool SpacesAfter = Tok->Next->WhitespaceRange.getBegin() !=
886                              Tok->Next->WhitespaceRange.getEnd();
887           if (SpacesBefore && !SpacesAfter)
888             ++CountBoundToVariable;
889           else if (!SpacesBefore && SpacesAfter)
890             ++CountBoundToType;
891         }
892 
893         if (Tok->Type == TT_TemplateCloser &&
894             Tok->Previous->Type == TT_TemplateCloser &&
895             Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd())
896           HasCpp03IncompatibleFormat = true;
897 
898         if (Tok->PackingKind == PPK_BinPacked)
899           HasBinPackedFunction = true;
900         if (Tok->PackingKind == PPK_OnePerLine)
901           HasOnePerLineFunction = true;
902 
903         Tok = Tok->Next;
904       }
905     }
906     if (Style.DerivePointerBinding) {
907       if (CountBoundToType > CountBoundToVariable)
908         Style.PointerBindsToType = true;
909       else if (CountBoundToType < CountBoundToVariable)
910         Style.PointerBindsToType = false;
911     }
912     if (Style.Standard == FormatStyle::LS_Auto) {
913       Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11
914                                                   : FormatStyle::LS_Cpp03;
915     }
916     BinPackInconclusiveFunctions =
917         HasBinPackedFunction || !HasOnePerLineFunction;
918   }
919 
920   /// \brief Get the indent of \p Level from \p IndentForLevel.
921   ///
922   /// \p IndentForLevel must contain the indent for the level \c l
923   /// at \p IndentForLevel[l], or a value < 0 if the indent for
924   /// that level is unknown.
925   unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) {
926     if (IndentForLevel[Level] != -1)
927       return IndentForLevel[Level];
928     if (Level == 0)
929       return 0;
930     return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth;
931   }
932 
933   /// \brief Get the offset of the line relatively to the level.
934   ///
935   /// For example, 'public:' labels in classes are offset by 1 or 2
936   /// characters to the left from their level.
937   int getIndentOffset(const FormatToken &RootToken) {
938     if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier())
939       return Style.AccessModifierOffset;
940     return 0;
941   }
942 
943   /// \brief Tries to merge lines into one.
944   ///
945   /// This will change \c Line and \c AnnotatedLine to contain the merged line,
946   /// if possible; note that \c I will be incremented when lines are merged.
947   void tryFitMultipleLinesInOne(unsigned Indent,
948                                 SmallVectorImpl<AnnotatedLine *>::iterator &I,
949                                 SmallVectorImpl<AnnotatedLine *>::iterator E) {
950     // We can never merge stuff if there are trailing line comments.
951     AnnotatedLine *TheLine = *I;
952     if (TheLine->Last->Type == TT_LineComment)
953       return;
954 
955     if (Indent > Style.ColumnLimit)
956       return;
957 
958     unsigned Limit = Style.ColumnLimit - Indent;
959     // If we already exceed the column limit, we set 'Limit' to 0. The different
960     // tryMerge..() functions can then decide whether to still do merging.
961     Limit = TheLine->Last->TotalLength > Limit
962                 ? 0
963                 : Limit - TheLine->Last->TotalLength;
964 
965     if (I + 1 == E || (*(I + 1))->Type == LT_Invalid)
966       return;
967 
968     if (TheLine->Last->is(tok::l_brace)) {
969       tryMergeSimpleBlock(I, E, Limit);
970     } else if (Style.AllowShortIfStatementsOnASingleLine &&
971                TheLine->First->is(tok::kw_if)) {
972       tryMergeSimpleControlStatement(I, E, Limit);
973     } else if (Style.AllowShortLoopsOnASingleLine &&
974                TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
975       tryMergeSimpleControlStatement(I, E, Limit);
976     } else if (TheLine->InPPDirective && (TheLine->First->HasUnescapedNewline ||
977                                           TheLine->First->IsFirst)) {
978       tryMergeSimplePPDirective(I, E, Limit);
979     }
980   }
981 
982   void tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::iterator &I,
983                                  SmallVectorImpl<AnnotatedLine *>::iterator E,
984                                  unsigned Limit) {
985     if (Limit == 0)
986       return;
987     AnnotatedLine &Line = **I;
988     if (!(*(I + 1))->InPPDirective || (*(I + 1))->First->HasUnescapedNewline)
989       return;
990     if (I + 2 != E && (*(I + 2))->InPPDirective &&
991         !(*(I + 2))->First->HasUnescapedNewline)
992       return;
993     if (1 + (*(I + 1))->Last->TotalLength > Limit)
994       return;
995     join(Line, **(++I));
996   }
997 
998   void
999   tryMergeSimpleControlStatement(SmallVectorImpl<AnnotatedLine *>::iterator &I,
1000                                  SmallVectorImpl<AnnotatedLine *>::iterator E,
1001                                  unsigned Limit) {
1002     if (Limit == 0)
1003       return;
1004     if (Style.BreakBeforeBraces == FormatStyle::BS_Allman &&
1005         (*(I + 1))->First->is(tok::l_brace))
1006       return;
1007     if ((*(I + 1))->InPPDirective != (*I)->InPPDirective ||
1008         ((*(I + 1))->InPPDirective && (*(I + 1))->First->HasUnescapedNewline))
1009       return;
1010     AnnotatedLine &Line = **I;
1011     if (Line.Last->isNot(tok::r_paren))
1012       return;
1013     if (1 + (*(I + 1))->Last->TotalLength > Limit)
1014       return;
1015     if ((*(I + 1))->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for,
1016                                    tok::kw_while) ||
1017         (*(I + 1))->First->Type == TT_LineComment)
1018       return;
1019     // Only inline simple if's (no nested if or else).
1020     if (I + 2 != E && Line.First->is(tok::kw_if) &&
1021         (*(I + 2))->First->is(tok::kw_else))
1022       return;
1023     join(Line, **(++I));
1024   }
1025 
1026   void tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::iterator &I,
1027                            SmallVectorImpl<AnnotatedLine *>::iterator E,
1028                            unsigned Limit) {
1029     // No merging if the brace already is on the next line.
1030     if (Style.BreakBeforeBraces != FormatStyle::BS_Attach)
1031       return;
1032 
1033     // First, check that the current line allows merging. This is the case if
1034     // we're not in a control flow statement and the last token is an opening
1035     // brace.
1036     AnnotatedLine &Line = **I;
1037     if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::r_brace,
1038                             tok::kw_else, tok::kw_try, tok::kw_catch,
1039                             tok::kw_for,
1040                             // This gets rid of all ObjC @ keywords and methods.
1041                             tok::at, tok::minus, tok::plus))
1042       return;
1043 
1044     FormatToken *Tok = (*(I + 1))->First;
1045     if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
1046         (Tok->getNextNonComment() == NULL ||
1047          Tok->getNextNonComment()->is(tok::semi))) {
1048       // We merge empty blocks even if the line exceeds the column limit.
1049       Tok->SpacesRequiredBefore = 0;
1050       Tok->CanBreakBefore = true;
1051       join(Line, **(I + 1));
1052       I += 1;
1053     } else if (Limit != 0 && Line.First->isNot(tok::kw_namespace)) {
1054       // Check that we still have three lines and they fit into the limit.
1055       if (I + 2 == E || (*(I + 2))->Type == LT_Invalid ||
1056           !nextTwoLinesFitInto(I, Limit))
1057         return;
1058 
1059       // Second, check that the next line does not contain any braces - if it
1060       // does, readability declines when putting it into a single line.
1061       if ((*(I + 1))->Last->Type == TT_LineComment || Tok->MustBreakBefore)
1062         return;
1063       do {
1064         if (Tok->isOneOf(tok::l_brace, tok::r_brace))
1065           return;
1066         Tok = Tok->Next;
1067       } while (Tok != NULL);
1068 
1069       // Last, check that the third line contains a single closing brace.
1070       Tok = (*(I + 2))->First;
1071       if (Tok->getNextNonComment() != NULL || Tok->isNot(tok::r_brace) ||
1072           Tok->MustBreakBefore)
1073         return;
1074 
1075       join(Line, **(I + 1));
1076       join(Line, **(I + 2));
1077       I += 2;
1078     }
1079   }
1080 
1081   bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::iterator I,
1082                            unsigned Limit) {
1083     return 1 + (*(I + 1))->Last->TotalLength + 1 +
1084                (*(I + 2))->Last->TotalLength <=
1085            Limit;
1086   }
1087 
1088   void join(AnnotatedLine &A, const AnnotatedLine &B) {
1089     assert(!A.Last->Next);
1090     assert(!B.First->Previous);
1091     A.Last->Next = B.First;
1092     B.First->Previous = A.Last;
1093     unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
1094     for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
1095       Tok->TotalLength += LengthA;
1096       A.Last = Tok;
1097     }
1098   }
1099 
1100   bool touchesRanges(const CharSourceRange &Range) {
1101     for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1102       if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),
1103                                                Ranges[i].getBegin()) &&
1104           !SourceMgr.isBeforeInTranslationUnit(Ranges[i].getEnd(),
1105                                                Range.getBegin()))
1106         return true;
1107     }
1108     return false;
1109   }
1110 
1111   bool touchesLine(const AnnotatedLine &TheLine) {
1112     const FormatToken *First = TheLine.First;
1113     const FormatToken *Last = TheLine.Last;
1114     CharSourceRange LineRange = CharSourceRange::getCharRange(
1115         First->WhitespaceRange.getBegin().getLocWithOffset(
1116             First->LastNewlineOffset),
1117         Last->Tok.getLocation().getLocWithOffset(Last->TokenText.size() - 1));
1118     return touchesRanges(LineRange);
1119   }
1120 
1121   bool touchesPPDirective(SmallVectorImpl<AnnotatedLine *>::iterator I,
1122                           SmallVectorImpl<AnnotatedLine *>::iterator E) {
1123     for (; I != E; ++I) {
1124       if ((*I)->First->HasUnescapedNewline)
1125         return false;
1126       if (touchesLine(**I))
1127         return true;
1128     }
1129     return false;
1130   }
1131 
1132   bool touchesEmptyLineBefore(const AnnotatedLine &TheLine) {
1133     const FormatToken *First = TheLine.First;
1134     CharSourceRange LineRange = CharSourceRange::getCharRange(
1135         First->WhitespaceRange.getBegin(),
1136         First->WhitespaceRange.getBegin().getLocWithOffset(
1137             First->LastNewlineOffset));
1138     return touchesRanges(LineRange);
1139   }
1140 
1141   virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) {
1142     AnnotatedLines.push_back(new AnnotatedLine(TheLine));
1143   }
1144 
1145   /// \brief Add a new line and the required indent before the first Token
1146   /// of the \c UnwrappedLine if there was no structural parsing error.
1147   /// Returns the indent level of the \c UnwrappedLine.
1148   void formatFirstToken(const FormatToken &RootToken,
1149                         const FormatToken *PreviousToken, unsigned Indent,
1150                         bool InPPDirective) {
1151     unsigned Newlines =
1152         std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
1153     // Remove empty lines before "}" where applicable.
1154     if (RootToken.is(tok::r_brace) &&
1155         (!RootToken.Next ||
1156          (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)))
1157       Newlines = std::min(Newlines, 1u);
1158     if (Newlines == 0 && !RootToken.IsFirst)
1159       Newlines = 1;
1160 
1161     // Insert extra new line before access specifiers.
1162     if (PreviousToken && PreviousToken->isOneOf(tok::semi, tok::r_brace) &&
1163         RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
1164       ++Newlines;
1165 
1166     Whitespaces.replaceWhitespace(
1167         RootToken, Newlines, Indent, Indent,
1168         InPPDirective && !RootToken.HasUnescapedNewline);
1169   }
1170 
1171   unsigned getColumnLimit(bool InPPDirective) const {
1172     // In preprocessor directives reserve two chars for trailing " \"
1173     return Style.ColumnLimit - (InPPDirective ? 2 : 0);
1174   }
1175 
1176   FormatStyle Style;
1177   Lexer &Lex;
1178   SourceManager &SourceMgr;
1179   WhitespaceManager Whitespaces;
1180   std::vector<CharSourceRange> Ranges;
1181   SmallVector<AnnotatedLine *, 16> AnnotatedLines;
1182 
1183   encoding::Encoding Encoding;
1184   bool BinPackInconclusiveFunctions;
1185 };
1186 
1187 } // end anonymous namespace
1188 
1189 tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
1190                                SourceManager &SourceMgr,
1191                                std::vector<CharSourceRange> Ranges) {
1192   Formatter formatter(Style, Lex, SourceMgr, Ranges);
1193   return formatter.format();
1194 }
1195 
1196 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1197                                std::vector<tooling::Range> Ranges,
1198                                StringRef FileName) {
1199   FileManager Files((FileSystemOptions()));
1200   DiagnosticsEngine Diagnostics(
1201       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
1202       new DiagnosticOptions);
1203   SourceManager SourceMgr(Diagnostics, Files);
1204   llvm::MemoryBuffer *Buf = llvm::MemoryBuffer::getMemBuffer(Code, FileName);
1205   const clang::FileEntry *Entry =
1206       Files.getVirtualFile(FileName, Buf->getBufferSize(), 0);
1207   SourceMgr.overrideFileContents(Entry, Buf);
1208   FileID ID =
1209       SourceMgr.createFileID(Entry, SourceLocation(), clang::SrcMgr::C_User);
1210   Lexer Lex(ID, SourceMgr.getBuffer(ID), SourceMgr,
1211             getFormattingLangOpts(Style.Standard));
1212   SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
1213   std::vector<CharSourceRange> CharRanges;
1214   for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1215     SourceLocation Start = StartOfFile.getLocWithOffset(Ranges[i].getOffset());
1216     SourceLocation End = Start.getLocWithOffset(Ranges[i].getLength());
1217     CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
1218   }
1219   return reformat(Style, Lex, SourceMgr, CharRanges);
1220 }
1221 
1222 LangOptions getFormattingLangOpts(FormatStyle::LanguageStandard Standard) {
1223   LangOptions LangOpts;
1224   LangOpts.CPlusPlus = 1;
1225   LangOpts.CPlusPlus11 = Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1226   LangOpts.LineComment = 1;
1227   LangOpts.Bool = 1;
1228   LangOpts.ObjC1 = 1;
1229   LangOpts.ObjC2 = 1;
1230   return LangOpts;
1231 }
1232 
1233 } // namespace format
1234 } // namespace clang
1235