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           unsigned Newlines = std::min((*I)->First->NewlinesBefore,
535                                        Style.MaxEmptyLinesToKeep + 1);
536           Newlines = std::max(1u, Newlines);
537           Whitespaces->replaceWhitespace(
538               *(*I)->First, Newlines, /*Spaces=*/Indent,
539               /*StartOfTokenColumn=*/Indent, Line.InPPDirective);
540         }
541         UnwrappedLineFormatter Formatter(Indenter, Whitespaces, Style, **I);
542         Penalty += Formatter.format(Indent, DryRun);
543       }
544       return true;
545     }
546 
547     if (LBrace.Children.size() > 1)
548       return false; // Cannot merge multiple statements into a single line.
549 
550     // We can't put the closing "}" on a line with a trailing comment.
551     if (LBrace.Children[0]->Last->isTrailingComment())
552       return false;
553 
554     if (!DryRun) {
555       Whitespaces->replaceWhitespace(*LBrace.Children[0]->First,
556                                      /*Newlines=*/0, /*Spaces=*/1,
557                                      /*StartOfTokenColumn=*/State.Column,
558                                      State.Line->InPPDirective);
559       UnwrappedLineFormatter Formatter(Indenter, Whitespaces, Style,
560                                        *LBrace.Children[0]);
561       Penalty += Formatter.format(State.Column + 1, DryRun);
562     }
563 
564     State.Column += 1 + LBrace.Children[0]->Last->TotalLength;
565     return true;
566   }
567 
568   ContinuationIndenter *Indenter;
569   WhitespaceManager *Whitespaces;
570   FormatStyle Style;
571   const AnnotatedLine &Line;
572 
573   llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
574   QueueType Queue;
575   // Increasing count of \c StateNode items we have created. This is used
576   // to create a deterministic order independent of the container.
577   unsigned Count;
578 };
579 
580 class FormatTokenLexer {
581 public:
582   FormatTokenLexer(Lexer &Lex, SourceManager &SourceMgr, FormatStyle &Style,
583                    encoding::Encoding Encoding)
584       : FormatTok(NULL), GreaterStashed(false), Column(0),
585         TrailingWhitespace(0), Lex(Lex), SourceMgr(SourceMgr), Style(Style),
586         IdentTable(getFormattingLangOpts()), Encoding(Encoding) {
587     Lex.SetKeepWhitespaceMode(true);
588   }
589 
590   ArrayRef<FormatToken *> lex() {
591     assert(Tokens.empty());
592     do {
593       Tokens.push_back(getNextToken());
594     } while (Tokens.back()->Tok.isNot(tok::eof));
595     return Tokens;
596   }
597 
598   IdentifierTable &getIdentTable() { return IdentTable; }
599 
600 private:
601   FormatToken *getNextToken() {
602     if (GreaterStashed) {
603       // Create a synthesized second '>' token.
604       // FIXME: Increment Column and set OriginalColumn.
605       Token Greater = FormatTok->Tok;
606       FormatTok = new (Allocator.Allocate()) FormatToken;
607       FormatTok->Tok = Greater;
608       SourceLocation GreaterLocation =
609           FormatTok->Tok.getLocation().getLocWithOffset(1);
610       FormatTok->WhitespaceRange =
611           SourceRange(GreaterLocation, GreaterLocation);
612       FormatTok->TokenText = ">";
613       FormatTok->CodePointCount = 1;
614       GreaterStashed = false;
615       return FormatTok;
616     }
617 
618     FormatTok = new (Allocator.Allocate()) FormatToken;
619     readRawToken(*FormatTok);
620     SourceLocation WhitespaceStart =
621         FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
622     if (SourceMgr.getFileOffset(WhitespaceStart) == 0)
623       FormatTok->IsFirst = true;
624 
625     // Consume and record whitespace until we find a significant token.
626     unsigned WhitespaceLength = TrailingWhitespace;
627     while (FormatTok->Tok.is(tok::unknown)) {
628       for (int i = 0, e = FormatTok->TokenText.size(); i != e; ++i) {
629         switch (FormatTok->TokenText[i]) {
630         case '\n':
631           ++FormatTok->NewlinesBefore;
632           // FIXME: This is technically incorrect, as it could also
633           // be a literal backslash at the end of the line.
634           if (i == 0 || FormatTok->TokenText[i - 1] != '\\')
635             FormatTok->HasUnescapedNewline = true;
636           FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
637           Column = 0;
638           break;
639         case ' ':
640           ++Column;
641           break;
642         case '\t':
643           Column += Style.TabWidth - Column % Style.TabWidth;
644           break;
645         default:
646           ++Column;
647           break;
648         }
649       }
650 
651       WhitespaceLength += FormatTok->Tok.getLength();
652 
653       readRawToken(*FormatTok);
654     }
655 
656     // In case the token starts with escaped newlines, we want to
657     // take them into account as whitespace - this pattern is quite frequent
658     // in macro definitions.
659     // FIXME: What do we want to do with other escaped spaces, and escaped
660     // spaces or newlines in the middle of tokens?
661     // FIXME: Add a more explicit test.
662     while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
663            FormatTok->TokenText[1] == '\n') {
664       // FIXME: ++FormatTok->NewlinesBefore is missing...
665       WhitespaceLength += 2;
666       Column = 0;
667       FormatTok->TokenText = FormatTok->TokenText.substr(2);
668     }
669     FormatTok->OriginalColumn = Column;
670 
671     TrailingWhitespace = 0;
672     if (FormatTok->Tok.is(tok::comment)) {
673       // FIXME: Add the trimmed whitespace to Column.
674       StringRef UntrimmedText = FormatTok->TokenText;
675       FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
676       TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
677     } else if (FormatTok->Tok.is(tok::raw_identifier)) {
678       IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
679       FormatTok->Tok.setIdentifierInfo(&Info);
680       FormatTok->Tok.setKind(Info.getTokenID());
681     } else if (FormatTok->Tok.is(tok::greatergreater)) {
682       FormatTok->Tok.setKind(tok::greater);
683       FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
684       GreaterStashed = true;
685     }
686 
687     // Now FormatTok is the next non-whitespace token.
688     FormatTok->CodePointCount =
689         encoding::getCodePointCount(FormatTok->TokenText, Encoding);
690 
691     if (FormatTok->isOneOf(tok::string_literal, tok::comment)) {
692       StringRef Text = FormatTok->TokenText;
693       size_t FirstNewlinePos = Text.find('\n');
694       if (FirstNewlinePos != StringRef::npos) {
695         // FIXME: Handle embedded tabs.
696         FormatTok->FirstLineColumnWidth = encoding::columnWidthWithTabs(
697             Text.substr(0, FirstNewlinePos), 0, Style.TabWidth, Encoding);
698         FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
699             Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth,
700             Encoding);
701       }
702     }
703     // FIXME: Add the CodePointCount to Column.
704     FormatTok->WhitespaceRange = SourceRange(
705         WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
706     return FormatTok;
707   }
708 
709   FormatToken *FormatTok;
710   bool GreaterStashed;
711   unsigned Column;
712   unsigned TrailingWhitespace;
713   Lexer &Lex;
714   SourceManager &SourceMgr;
715   FormatStyle &Style;
716   IdentifierTable IdentTable;
717   encoding::Encoding Encoding;
718   llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
719   SmallVector<FormatToken *, 16> Tokens;
720 
721   void readRawToken(FormatToken &Tok) {
722     Lex.LexFromRawLexer(Tok.Tok);
723     Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
724                               Tok.Tok.getLength());
725     // For formatting, treat unterminated string literals like normal string
726     // literals.
727     if (Tok.is(tok::unknown) && !Tok.TokenText.empty() &&
728         Tok.TokenText[0] == '"') {
729       Tok.Tok.setKind(tok::string_literal);
730       Tok.IsUnterminatedLiteral = true;
731     }
732   }
733 };
734 
735 class Formatter : public UnwrappedLineConsumer {
736 public:
737   Formatter(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr,
738             const std::vector<CharSourceRange> &Ranges)
739       : Style(Style), Lex(Lex), SourceMgr(SourceMgr),
740         Whitespaces(SourceMgr, Style), Ranges(Ranges),
741         Encoding(encoding::detectEncoding(Lex.getBuffer())) {
742     DEBUG(llvm::dbgs() << "File encoding: "
743                        << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
744                                                                : "unknown")
745                        << "\n");
746   }
747 
748   virtual ~Formatter() {
749     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
750       delete AnnotatedLines[i];
751     }
752   }
753 
754   tooling::Replacements format() {
755     FormatTokenLexer Tokens(Lex, SourceMgr, Style, Encoding);
756 
757     UnwrappedLineParser Parser(Style, Tokens.lex(), *this);
758     bool StructuralError = Parser.parse();
759     TokenAnnotator Annotator(Style, Tokens.getIdentTable().get("in"));
760     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
761       Annotator.annotate(*AnnotatedLines[i]);
762     }
763     deriveLocalStyle();
764     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
765       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
766     }
767 
768     Annotator.setCommentLineLevels(AnnotatedLines);
769 
770     std::vector<int> IndentForLevel;
771     bool PreviousLineWasTouched = false;
772     const FormatToken *PreviousLineLastToken = 0;
773     bool FormatPPDirective = false;
774     for (SmallVectorImpl<AnnotatedLine *>::iterator I = AnnotatedLines.begin(),
775                                                     E = AnnotatedLines.end();
776          I != E; ++I) {
777       const AnnotatedLine &TheLine = **I;
778       const FormatToken *FirstTok = TheLine.First;
779       int Offset = getIndentOffset(*TheLine.First);
780 
781       // Check whether this line is part of a formatted preprocessor directive.
782       if (FirstTok->HasUnescapedNewline)
783         FormatPPDirective = false;
784       if (!FormatPPDirective && TheLine.InPPDirective &&
785           (touchesLine(TheLine) || touchesPPDirective(I + 1, E)))
786         FormatPPDirective = true;
787 
788       // Determine indent and try to merge multiple unwrapped lines.
789       while (IndentForLevel.size() <= TheLine.Level)
790         IndentForLevel.push_back(-1);
791       IndentForLevel.resize(TheLine.Level + 1);
792       unsigned Indent = getIndent(IndentForLevel, TheLine.Level);
793       if (static_cast<int>(Indent) + Offset >= 0)
794         Indent += Offset;
795       tryFitMultipleLinesInOne(Indent, I, E);
796 
797       bool WasMoved = PreviousLineWasTouched && FirstTok->NewlinesBefore == 0;
798       if (TheLine.First->is(tok::eof)) {
799         if (PreviousLineWasTouched) {
800           unsigned NewLines = std::min(FirstTok->NewlinesBefore, 1u);
801           Whitespaces.replaceWhitespace(*TheLine.First, NewLines, /*Indent*/ 0,
802                                         /*TargetColumn*/ 0);
803         }
804       } else if (TheLine.Type != LT_Invalid &&
805                  (WasMoved || FormatPPDirective || touchesLine(TheLine))) {
806         unsigned LevelIndent = getIndent(IndentForLevel, TheLine.Level);
807         if (FirstTok->WhitespaceRange.isValid() &&
808             // Insert a break even if there is a structural error in case where
809             // we break apart a line consisting of multiple unwrapped lines.
810             (FirstTok->NewlinesBefore == 0 || !StructuralError)) {
811           formatFirstToken(*TheLine.First, PreviousLineLastToken, Indent,
812                            TheLine.InPPDirective);
813         } else {
814           Indent = LevelIndent = FirstTok->OriginalColumn;
815         }
816         ContinuationIndenter Indenter(Style, SourceMgr, Whitespaces, Encoding,
817                                       BinPackInconclusiveFunctions);
818 
819         // If everything fits on a single line, just put it there.
820         unsigned ColumnLimit = Style.ColumnLimit;
821         AnnotatedLine *NextLine = *(I + 1);
822         if ((I + 1) != E && NextLine->InPPDirective &&
823             !NextLine->First->HasUnescapedNewline)
824           ColumnLimit = getColumnLimit(TheLine.InPPDirective);
825 
826         if (TheLine.Last->TotalLength + Indent <= ColumnLimit) {
827           LineState State =
828               Indenter.getInitialState(Indent, &TheLine, /*DryRun=*/false);
829           while (State.NextToken != NULL)
830             Indenter.addTokenToState(State, false, false);
831         } else if (Style.ColumnLimit == 0) {
832           NoColumnLimitFormatter Formatter(&Indenter);
833           Formatter.format(Indent, &TheLine);
834         } else {
835           UnwrappedLineFormatter Formatter(&Indenter, &Whitespaces, Style,
836                                            TheLine);
837           Formatter.format(Indent);
838         }
839 
840         IndentForLevel[TheLine.Level] = LevelIndent;
841         PreviousLineWasTouched = true;
842       } else {
843         // Format the first token if necessary, and notify the WhitespaceManager
844         // about the unchanged whitespace.
845         for (const FormatToken *Tok = TheLine.First; Tok != NULL;
846              Tok = Tok->Next) {
847           if (Tok == TheLine.First &&
848               (Tok->NewlinesBefore > 0 || Tok->IsFirst)) {
849             unsigned LevelIndent = Tok->OriginalColumn;
850             // Remove trailing whitespace of the previous line if it was
851             // touched.
852             if (PreviousLineWasTouched || touchesEmptyLineBefore(TheLine)) {
853               formatFirstToken(*Tok, PreviousLineLastToken, LevelIndent,
854                                TheLine.InPPDirective);
855             } else {
856               Whitespaces.addUntouchableToken(*Tok, TheLine.InPPDirective);
857             }
858 
859             if (static_cast<int>(LevelIndent) - Offset >= 0)
860               LevelIndent -= Offset;
861             if (Tok->isNot(tok::comment))
862               IndentForLevel[TheLine.Level] = LevelIndent;
863           } else {
864             Whitespaces.addUntouchableToken(*Tok, TheLine.InPPDirective);
865           }
866         }
867         // If we did not reformat this unwrapped line, the column at the end of
868         // the last token is unchanged - thus, we can calculate the end of the
869         // last token.
870         PreviousLineWasTouched = false;
871       }
872       PreviousLineLastToken = TheLine.Last;
873     }
874     return Whitespaces.generateReplacements();
875   }
876 
877 private:
878   void deriveLocalStyle() {
879     unsigned CountBoundToVariable = 0;
880     unsigned CountBoundToType = 0;
881     bool HasCpp03IncompatibleFormat = false;
882     bool HasBinPackedFunction = false;
883     bool HasOnePerLineFunction = false;
884     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
885       if (!AnnotatedLines[i]->First->Next)
886         continue;
887       FormatToken *Tok = AnnotatedLines[i]->First->Next;
888       while (Tok->Next) {
889         if (Tok->Type == TT_PointerOrReference) {
890           bool SpacesBefore =
891               Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
892           bool SpacesAfter = Tok->Next->WhitespaceRange.getBegin() !=
893                              Tok->Next->WhitespaceRange.getEnd();
894           if (SpacesBefore && !SpacesAfter)
895             ++CountBoundToVariable;
896           else if (!SpacesBefore && SpacesAfter)
897             ++CountBoundToType;
898         }
899 
900         if (Tok->Type == TT_TemplateCloser &&
901             Tok->Previous->Type == TT_TemplateCloser &&
902             Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd())
903           HasCpp03IncompatibleFormat = true;
904 
905         if (Tok->PackingKind == PPK_BinPacked)
906           HasBinPackedFunction = true;
907         if (Tok->PackingKind == PPK_OnePerLine)
908           HasOnePerLineFunction = true;
909 
910         Tok = Tok->Next;
911       }
912     }
913     if (Style.DerivePointerBinding) {
914       if (CountBoundToType > CountBoundToVariable)
915         Style.PointerBindsToType = true;
916       else if (CountBoundToType < CountBoundToVariable)
917         Style.PointerBindsToType = false;
918     }
919     if (Style.Standard == FormatStyle::LS_Auto) {
920       Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11
921                                                   : FormatStyle::LS_Cpp03;
922     }
923     BinPackInconclusiveFunctions =
924         HasBinPackedFunction || !HasOnePerLineFunction;
925   }
926 
927   /// \brief Get the indent of \p Level from \p IndentForLevel.
928   ///
929   /// \p IndentForLevel must contain the indent for the level \c l
930   /// at \p IndentForLevel[l], or a value < 0 if the indent for
931   /// that level is unknown.
932   unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) {
933     if (IndentForLevel[Level] != -1)
934       return IndentForLevel[Level];
935     if (Level == 0)
936       return 0;
937     return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth;
938   }
939 
940   /// \brief Get the offset of the line relatively to the level.
941   ///
942   /// For example, 'public:' labels in classes are offset by 1 or 2
943   /// characters to the left from their level.
944   int getIndentOffset(const FormatToken &RootToken) {
945     if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier())
946       return Style.AccessModifierOffset;
947     return 0;
948   }
949 
950   /// \brief Tries to merge lines into one.
951   ///
952   /// This will change \c Line and \c AnnotatedLine to contain the merged line,
953   /// if possible; note that \c I will be incremented when lines are merged.
954   void tryFitMultipleLinesInOne(unsigned Indent,
955                                 SmallVectorImpl<AnnotatedLine *>::iterator &I,
956                                 SmallVectorImpl<AnnotatedLine *>::iterator E) {
957     // We can never merge stuff if there are trailing line comments.
958     AnnotatedLine *TheLine = *I;
959     if (TheLine->Last->Type == TT_LineComment)
960       return;
961 
962     if (Indent > Style.ColumnLimit)
963       return;
964 
965     unsigned Limit = Style.ColumnLimit - Indent;
966     // If we already exceed the column limit, we set 'Limit' to 0. The different
967     // tryMerge..() functions can then decide whether to still do merging.
968     Limit = TheLine->Last->TotalLength > Limit
969                 ? 0
970                 : Limit - TheLine->Last->TotalLength;
971 
972     if (I + 1 == E || (*(I + 1))->Type == LT_Invalid)
973       return;
974 
975     if (TheLine->Last->is(tok::l_brace)) {
976       tryMergeSimpleBlock(I, E, Limit);
977     } else if (Style.AllowShortIfStatementsOnASingleLine &&
978                TheLine->First->is(tok::kw_if)) {
979       tryMergeSimpleControlStatement(I, E, Limit);
980     } else if (Style.AllowShortLoopsOnASingleLine &&
981                TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
982       tryMergeSimpleControlStatement(I, E, Limit);
983     } else if (TheLine->InPPDirective && (TheLine->First->HasUnescapedNewline ||
984                                           TheLine->First->IsFirst)) {
985       tryMergeSimplePPDirective(I, E, Limit);
986     }
987   }
988 
989   void tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::iterator &I,
990                                  SmallVectorImpl<AnnotatedLine *>::iterator E,
991                                  unsigned Limit) {
992     if (Limit == 0)
993       return;
994     AnnotatedLine &Line = **I;
995     if (!(*(I + 1))->InPPDirective || (*(I + 1))->First->HasUnescapedNewline)
996       return;
997     if (I + 2 != E && (*(I + 2))->InPPDirective &&
998         !(*(I + 2))->First->HasUnescapedNewline)
999       return;
1000     if (1 + (*(I + 1))->Last->TotalLength > Limit)
1001       return;
1002     join(Line, **(++I));
1003   }
1004 
1005   void
1006   tryMergeSimpleControlStatement(SmallVectorImpl<AnnotatedLine *>::iterator &I,
1007                                  SmallVectorImpl<AnnotatedLine *>::iterator E,
1008                                  unsigned Limit) {
1009     if (Limit == 0)
1010       return;
1011     if (Style.BreakBeforeBraces == FormatStyle::BS_Allman &&
1012         (*(I + 1))->First->is(tok::l_brace))
1013       return;
1014     if ((*(I + 1))->InPPDirective != (*I)->InPPDirective ||
1015         ((*(I + 1))->InPPDirective && (*(I + 1))->First->HasUnescapedNewline))
1016       return;
1017     AnnotatedLine &Line = **I;
1018     if (Line.Last->isNot(tok::r_paren))
1019       return;
1020     if (1 + (*(I + 1))->Last->TotalLength > Limit)
1021       return;
1022     if ((*(I + 1))->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for,
1023                                    tok::kw_while) ||
1024         (*(I + 1))->First->Type == TT_LineComment)
1025       return;
1026     // Only inline simple if's (no nested if or else).
1027     if (I + 2 != E && Line.First->is(tok::kw_if) &&
1028         (*(I + 2))->First->is(tok::kw_else))
1029       return;
1030     join(Line, **(++I));
1031   }
1032 
1033   void tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::iterator &I,
1034                            SmallVectorImpl<AnnotatedLine *>::iterator E,
1035                            unsigned Limit) {
1036     // No merging if the brace already is on the next line.
1037     if (Style.BreakBeforeBraces != FormatStyle::BS_Attach)
1038       return;
1039 
1040     // First, check that the current line allows merging. This is the case if
1041     // we're not in a control flow statement and the last token is an opening
1042     // brace.
1043     AnnotatedLine &Line = **I;
1044     if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::r_brace,
1045                             tok::kw_else, tok::kw_try, tok::kw_catch,
1046                             tok::kw_for,
1047                             // This gets rid of all ObjC @ keywords and methods.
1048                             tok::at, tok::minus, tok::plus))
1049       return;
1050 
1051     FormatToken *Tok = (*(I + 1))->First;
1052     if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
1053         (Tok->getNextNonComment() == NULL ||
1054          Tok->getNextNonComment()->is(tok::semi))) {
1055       // We merge empty blocks even if the line exceeds the column limit.
1056       Tok->SpacesRequiredBefore = 0;
1057       Tok->CanBreakBefore = true;
1058       join(Line, **(I + 1));
1059       I += 1;
1060     } else if (Limit != 0 && Line.First->isNot(tok::kw_namespace)) {
1061       // Check that we still have three lines and they fit into the limit.
1062       if (I + 2 == E || (*(I + 2))->Type == LT_Invalid ||
1063           !nextTwoLinesFitInto(I, Limit))
1064         return;
1065 
1066       // Second, check that the next line does not contain any braces - if it
1067       // does, readability declines when putting it into a single line.
1068       if ((*(I + 1))->Last->Type == TT_LineComment || Tok->MustBreakBefore)
1069         return;
1070       do {
1071         if (Tok->isOneOf(tok::l_brace, tok::r_brace))
1072           return;
1073         Tok = Tok->Next;
1074       } while (Tok != NULL);
1075 
1076       // Last, check that the third line contains a single closing brace.
1077       Tok = (*(I + 2))->First;
1078       if (Tok->getNextNonComment() != NULL || Tok->isNot(tok::r_brace) ||
1079           Tok->MustBreakBefore)
1080         return;
1081 
1082       join(Line, **(I + 1));
1083       join(Line, **(I + 2));
1084       I += 2;
1085     }
1086   }
1087 
1088   bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::iterator I,
1089                            unsigned Limit) {
1090     return 1 + (*(I + 1))->Last->TotalLength + 1 +
1091                (*(I + 2))->Last->TotalLength <=
1092            Limit;
1093   }
1094 
1095   void join(AnnotatedLine &A, const AnnotatedLine &B) {
1096     assert(!A.Last->Next);
1097     assert(!B.First->Previous);
1098     A.Last->Next = B.First;
1099     B.First->Previous = A.Last;
1100     unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
1101     for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
1102       Tok->TotalLength += LengthA;
1103       A.Last = Tok;
1104     }
1105   }
1106 
1107   bool touchesRanges(const CharSourceRange &Range) {
1108     for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1109       if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),
1110                                                Ranges[i].getBegin()) &&
1111           !SourceMgr.isBeforeInTranslationUnit(Ranges[i].getEnd(),
1112                                                Range.getBegin()))
1113         return true;
1114     }
1115     return false;
1116   }
1117 
1118   bool touchesLine(const AnnotatedLine &TheLine) {
1119     const FormatToken *First = TheLine.First;
1120     const FormatToken *Last = TheLine.Last;
1121     CharSourceRange LineRange = CharSourceRange::getCharRange(
1122         First->WhitespaceRange.getBegin().getLocWithOffset(
1123             First->LastNewlineOffset),
1124         Last->Tok.getLocation().getLocWithOffset(Last->TokenText.size() - 1));
1125     return touchesRanges(LineRange);
1126   }
1127 
1128   bool touchesPPDirective(SmallVectorImpl<AnnotatedLine *>::iterator I,
1129                           SmallVectorImpl<AnnotatedLine *>::iterator E) {
1130     for (; I != E; ++I) {
1131       if ((*I)->First->HasUnescapedNewline)
1132         return false;
1133       if (touchesLine(**I))
1134         return true;
1135     }
1136     return false;
1137   }
1138 
1139   bool touchesEmptyLineBefore(const AnnotatedLine &TheLine) {
1140     const FormatToken *First = TheLine.First;
1141     CharSourceRange LineRange = CharSourceRange::getCharRange(
1142         First->WhitespaceRange.getBegin(),
1143         First->WhitespaceRange.getBegin().getLocWithOffset(
1144             First->LastNewlineOffset));
1145     return touchesRanges(LineRange);
1146   }
1147 
1148   virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) {
1149     AnnotatedLines.push_back(new AnnotatedLine(TheLine));
1150   }
1151 
1152   /// \brief Add a new line and the required indent before the first Token
1153   /// of the \c UnwrappedLine if there was no structural parsing error.
1154   /// Returns the indent level of the \c UnwrappedLine.
1155   void formatFirstToken(const FormatToken &RootToken,
1156                         const FormatToken *PreviousToken, unsigned Indent,
1157                         bool InPPDirective) {
1158     unsigned Newlines =
1159         std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
1160     // Remove empty lines before "}" where applicable.
1161     if (RootToken.is(tok::r_brace) &&
1162         (!RootToken.Next ||
1163          (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)))
1164       Newlines = std::min(Newlines, 1u);
1165     if (Newlines == 0 && !RootToken.IsFirst)
1166       Newlines = 1;
1167 
1168     // Insert extra new line before access specifiers.
1169     if (PreviousToken && PreviousToken->isOneOf(tok::semi, tok::r_brace) &&
1170         RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
1171       ++Newlines;
1172 
1173     Whitespaces.replaceWhitespace(
1174         RootToken, Newlines, Indent, Indent,
1175         InPPDirective && !RootToken.HasUnescapedNewline);
1176   }
1177 
1178   unsigned getColumnLimit(bool InPPDirective) const {
1179     // In preprocessor directives reserve two chars for trailing " \"
1180     return Style.ColumnLimit - (InPPDirective ? 2 : 0);
1181   }
1182 
1183   FormatStyle Style;
1184   Lexer &Lex;
1185   SourceManager &SourceMgr;
1186   WhitespaceManager Whitespaces;
1187   std::vector<CharSourceRange> Ranges;
1188   SmallVector<AnnotatedLine *, 16> AnnotatedLines;
1189 
1190   encoding::Encoding Encoding;
1191   bool BinPackInconclusiveFunctions;
1192 };
1193 
1194 } // end anonymous namespace
1195 
1196 tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
1197                                SourceManager &SourceMgr,
1198                                std::vector<CharSourceRange> Ranges) {
1199   Formatter formatter(Style, Lex, SourceMgr, Ranges);
1200   return formatter.format();
1201 }
1202 
1203 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1204                                std::vector<tooling::Range> Ranges,
1205                                StringRef FileName) {
1206   FileManager Files((FileSystemOptions()));
1207   DiagnosticsEngine Diagnostics(
1208       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
1209       new DiagnosticOptions);
1210   SourceManager SourceMgr(Diagnostics, Files);
1211   llvm::MemoryBuffer *Buf = llvm::MemoryBuffer::getMemBuffer(Code, FileName);
1212   const clang::FileEntry *Entry =
1213       Files.getVirtualFile(FileName, Buf->getBufferSize(), 0);
1214   SourceMgr.overrideFileContents(Entry, Buf);
1215   FileID ID =
1216       SourceMgr.createFileID(Entry, SourceLocation(), clang::SrcMgr::C_User);
1217   Lexer Lex(ID, SourceMgr.getBuffer(ID), SourceMgr,
1218             getFormattingLangOpts(Style.Standard));
1219   SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
1220   std::vector<CharSourceRange> CharRanges;
1221   for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1222     SourceLocation Start = StartOfFile.getLocWithOffset(Ranges[i].getOffset());
1223     SourceLocation End = Start.getLocWithOffset(Ranges[i].getLength());
1224     CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
1225   }
1226   return reformat(Style, Lex, SourceMgr, CharRanges);
1227 }
1228 
1229 LangOptions getFormattingLangOpts(FormatStyle::LanguageStandard Standard) {
1230   LangOptions LangOpts;
1231   LangOpts.CPlusPlus = 1;
1232   LangOpts.CPlusPlus11 = Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1233   LangOpts.LineComment = 1;
1234   LangOpts.Bool = 1;
1235   LangOpts.ObjC1 = 1;
1236   LangOpts.ObjC2 = 1;
1237   return LangOpts;
1238 }
1239 
1240 } // namespace format
1241 } // namespace clang
1242