Format.cpp revision 0df6acdf4f6faf7579775a739e1c09448c076c0f 
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/// This is EXPERIMENTAL code under heavy development. It is not in a state yet,
15/// where it can be used to format real code.
16///
17//===----------------------------------------------------------------------===//
18
19#define DEBUG_TYPE "format-formatter"
20
21#include "UnwrappedLineParser.h"
22#include "clang/Basic/Diagnostic.h"
23#include "clang/Basic/OperatorPrecedence.h"
24#include "clang/Basic/SourceManager.h"
25#include "clang/Format/Format.h"
26#include "clang/Frontend/TextDiagnosticPrinter.h"
27#include "clang/Lex/Lexer.h"
28#include "llvm/Support/Debug.h"
29#include <string>
30
31// Uncomment to get debug output from tests:
32// #define DEBUG_WITH_TYPE(T, X) do { X; } while(0)
33
34namespace clang {
35namespace format {
36
37enum TokenType {
38  TT_BinaryOperator,
39  TT_BlockComment,
40  TT_CastRParen,
41  TT_ConditionalExpr,
42  TT_CtorInitializerColon,
43  TT_ImplicitStringLiteral,
44  TT_LineComment,
45  TT_ObjCBlockLParen,
46  TT_ObjCDecl,
47  TT_ObjCMethodSpecifier,
48  TT_ObjCMethodExpr,
49  TT_ObjCSelectorStart,
50  TT_ObjCProperty,
51  TT_OverloadedOperator,
52  TT_PointerOrReference,
53  TT_PureVirtualSpecifier,
54  TT_TemplateCloser,
55  TT_TemplateOpener,
56  TT_TrailingUnaryOperator,
57  TT_UnaryOperator,
58  TT_Unknown
59};
60
61enum LineType {
62  LT_Invalid,
63  LT_Other,
64  LT_PreprocessorDirective,
65  LT_VirtualFunctionDecl,
66  LT_ObjCDecl, // An @interface, @implementation, or @protocol line.
67  LT_ObjCMethodDecl,
68  LT_ObjCProperty // An @property line.
69};
70
71class AnnotatedToken {
72public:
73  AnnotatedToken(const FormatToken &FormatTok)
74      : FormatTok(FormatTok), Type(TT_Unknown), SpaceRequiredBefore(false),
75        CanBreakBefore(false), MustBreakBefore(false),
76        ClosesTemplateDeclaration(false), MatchingParen(NULL), Parent(NULL) {}
77
78  bool is(tok::TokenKind Kind) const { return FormatTok.Tok.is(Kind); }
79  bool isNot(tok::TokenKind Kind) const { return FormatTok.Tok.isNot(Kind); }
80
81  bool isObjCAtKeyword(tok::ObjCKeywordKind Kind) const {
82    return FormatTok.Tok.isObjCAtKeyword(Kind);
83  }
84
85  FormatToken FormatTok;
86
87  TokenType Type;
88
89  bool SpaceRequiredBefore;
90  bool CanBreakBefore;
91  bool MustBreakBefore;
92
93  bool ClosesTemplateDeclaration;
94
95  AnnotatedToken *MatchingParen;
96
97  /// \brief The total length of the line up to and including this token.
98  unsigned TotalLength;
99
100  std::vector<AnnotatedToken> Children;
101  AnnotatedToken *Parent;
102};
103
104class AnnotatedLine {
105public:
106  AnnotatedLine(const UnwrappedLine &Line)
107      : First(Line.Tokens.front()), Level(Line.Level),
108        InPPDirective(Line.InPPDirective) {
109    assert(!Line.Tokens.empty());
110    AnnotatedToken *Current = &First;
111    for (std::list<FormatToken>::const_iterator I = ++Line.Tokens.begin(),
112                                                E = Line.Tokens.end();
113         I != E; ++I) {
114      Current->Children.push_back(*I);
115      Current->Children[0].Parent = Current;
116      Current = &Current->Children[0];
117    }
118    Last = Current;
119  }
120  AnnotatedLine(const AnnotatedLine &Other)
121      : First(Other.First), Type(Other.Type), Level(Other.Level),
122        InPPDirective(Other.InPPDirective) {
123    Last = &First;
124    while (!Last->Children.empty()) {
125      Last->Children[0].Parent = Last;
126      Last = &Last->Children[0];
127    }
128  }
129
130  AnnotatedToken First;
131  AnnotatedToken *Last;
132
133  LineType Type;
134  unsigned Level;
135  bool InPPDirective;
136};
137
138static prec::Level getPrecedence(const AnnotatedToken &Tok) {
139  return getBinOpPrecedence(Tok.FormatTok.Tok.getKind(), true, true);
140}
141
142FormatStyle getLLVMStyle() {
143  FormatStyle LLVMStyle;
144  LLVMStyle.ColumnLimit = 80;
145  LLVMStyle.MaxEmptyLinesToKeep = 1;
146  LLVMStyle.PointerAndReferenceBindToType = false;
147  LLVMStyle.AccessModifierOffset = -2;
148  LLVMStyle.SplitTemplateClosingGreater = true;
149  LLVMStyle.IndentCaseLabels = false;
150  LLVMStyle.SpacesBeforeTrailingComments = 1;
151  LLVMStyle.BinPackParameters = true;
152  LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
153  LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
154  LLVMStyle.ObjCSpaceBeforeProtocolList = true;
155  LLVMStyle.ObjCSpaceBeforeReturnType = true;
156  return LLVMStyle;
157}
158
159FormatStyle getGoogleStyle() {
160  FormatStyle GoogleStyle;
161  GoogleStyle.ColumnLimit = 80;
162  GoogleStyle.MaxEmptyLinesToKeep = 1;
163  GoogleStyle.PointerAndReferenceBindToType = true;
164  GoogleStyle.AccessModifierOffset = -1;
165  GoogleStyle.SplitTemplateClosingGreater = false;
166  GoogleStyle.IndentCaseLabels = true;
167  GoogleStyle.SpacesBeforeTrailingComments = 2;
168  GoogleStyle.BinPackParameters = false;
169  GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
170  GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
171  GoogleStyle.ObjCSpaceBeforeProtocolList = false;
172  GoogleStyle.ObjCSpaceBeforeReturnType = false;
173  return GoogleStyle;
174}
175
176FormatStyle getChromiumStyle() {
177  FormatStyle ChromiumStyle = getGoogleStyle();
178  ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
179  return ChromiumStyle;
180}
181
182struct OptimizationParameters {
183  unsigned PenaltyIndentLevel;
184  unsigned PenaltyLevelDecrease;
185  unsigned PenaltyExcessCharacter;
186};
187
188/// \brief Replaces the whitespace in front of \p Tok. Only call once for
189/// each \c FormatToken.
190static void replaceWhitespace(const AnnotatedToken &Tok, unsigned NewLines,
191                              unsigned Spaces, const FormatStyle &Style,
192                              SourceManager &SourceMgr,
193                              tooling::Replacements &Replaces) {
194  Replaces.insert(tooling::Replacement(
195      SourceMgr, Tok.FormatTok.WhiteSpaceStart, Tok.FormatTok.WhiteSpaceLength,
196      std::string(NewLines, '\n') + std::string(Spaces, ' ')));
197}
198
199/// \brief Like \c replaceWhitespace, but additionally adds right-aligned
200/// backslashes to escape newlines inside a preprocessor directive.
201///
202/// This function and \c replaceWhitespace have the same behavior if
203/// \c Newlines == 0.
204static void replacePPWhitespace(
205    const AnnotatedToken &Tok, unsigned NewLines, unsigned Spaces,
206    unsigned WhitespaceStartColumn, const FormatStyle &Style,
207    SourceManager &SourceMgr, tooling::Replacements &Replaces) {
208  std::string NewLineText;
209  if (NewLines > 0) {
210    unsigned Offset = std::min<int>(Style.ColumnLimit - 1,
211                                    WhitespaceStartColumn);
212    for (unsigned i = 0; i < NewLines; ++i) {
213      NewLineText += std::string(Style.ColumnLimit - Offset - 1, ' ');
214      NewLineText += "\\\n";
215      Offset = 0;
216    }
217  }
218  Replaces.insert(tooling::Replacement(SourceMgr, Tok.FormatTok.WhiteSpaceStart,
219                                       Tok.FormatTok.WhiteSpaceLength,
220                                       NewLineText + std::string(Spaces, ' ')));
221}
222
223/// \brief Returns if a token is an Objective-C selector name.
224///
225/// For example, "bar" is a selector name in [foo bar:(4 + 5)].
226static bool isObjCSelectorName(const AnnotatedToken &Tok) {
227  return Tok.is(tok::identifier) && !Tok.Children.empty() &&
228         Tok.Children[0].is(tok::colon) &&
229         Tok.Children[0].Type == TT_ObjCMethodExpr;
230}
231
232class UnwrappedLineFormatter {
233public:
234  UnwrappedLineFormatter(const FormatStyle &Style, SourceManager &SourceMgr,
235                         const AnnotatedLine &Line, unsigned FirstIndent,
236                         const AnnotatedToken &RootToken,
237                         tooling::Replacements &Replaces, bool StructuralError)
238      : Style(Style), SourceMgr(SourceMgr), Line(Line),
239        FirstIndent(FirstIndent), RootToken(RootToken), Replaces(Replaces) {
240    Parameters.PenaltyIndentLevel = 15;
241    Parameters.PenaltyLevelDecrease = 30;
242    Parameters.PenaltyExcessCharacter = 1000000;
243  }
244
245  /// \brief Formats an \c UnwrappedLine.
246  ///
247  /// \returns The column after the last token in the last line of the
248  /// \c UnwrappedLine.
249  unsigned format() {
250    // Initialize state dependent on indent.
251    LineState State;
252    State.Column = FirstIndent;
253    State.NextToken = &RootToken;
254    State.Stack.push_back(ParenState(FirstIndent + 4, FirstIndent));
255    State.ForLoopVariablePos = 0;
256    State.LineContainsContinuedForLoopSection = false;
257    State.StartOfLineLevel = 1;
258
259    DEBUG({
260      DebugTokenState(*State.NextToken);
261    });
262
263    // The first token has already been indented and thus consumed.
264    moveStateToNextToken(State);
265
266    // Start iterating at 1 as we have correctly formatted of Token #0 above.
267    while (State.NextToken != NULL) {
268      if (State.NextToken->Type == TT_ImplicitStringLiteral)
269        // We will not touch the rest of the white space in this
270        // \c UnwrappedLine. The returned value can also not matter, as we
271        // cannot continue an top-level implicit string literal on the next
272        // line.
273        return 0;
274      if (Line.Last->TotalLength <= getColumnLimit() - FirstIndent) {
275        addTokenToState(false, false, State);
276      } else {
277        unsigned NoBreak = calcPenalty(State, false, UINT_MAX);
278        unsigned Break = calcPenalty(State, true, NoBreak);
279        DEBUG({
280          if (Break < NoBreak)
281            llvm::errs() << "\n";
282          else
283            llvm::errs() << " ";
284          llvm::errs() << "<";
285          DebugPenalty(Break, Break < NoBreak);
286          llvm::errs() << "/";
287          DebugPenalty(NoBreak, !(Break < NoBreak));
288          llvm::errs() << "> ";
289          DebugTokenState(*State.NextToken);
290        });
291        addTokenToState(Break < NoBreak, false, State);
292        if (State.NextToken != NULL &&
293            State.NextToken->Parent->Type == TT_CtorInitializerColon) {
294          if (Style.ConstructorInitializerAllOnOneLineOrOnePerLine &&
295              Line.Last->TotalLength > getColumnLimit() - State.Column - 1)
296            State.Stack.back().BreakAfterComma = true;
297        }
298      }
299    }
300    DEBUG(llvm::errs() << "\n");
301    return State.Column;
302  }
303
304private:
305  void DebugTokenState(const AnnotatedToken &AnnotatedTok) {
306    const Token &Tok = AnnotatedTok.FormatTok.Tok;
307    llvm::errs()
308        << StringRef(SourceMgr.getCharacterData(Tok.getLocation()),
309                     Tok.getLength());
310    llvm::errs();
311  }
312
313  void DebugPenalty(unsigned Penalty, bool Winner) {
314    llvm::errs().changeColor(Winner ? raw_ostream::GREEN : raw_ostream::RED);
315    if (Penalty == UINT_MAX)
316      llvm::errs() << "MAX";
317    else
318      llvm::errs() << Penalty;
319    llvm::errs().resetColor();
320  }
321
322  struct ParenState {
323    ParenState(unsigned Indent, unsigned LastSpace)
324        : Indent(Indent), LastSpace(LastSpace), FirstLessLess(0),
325          BreakBeforeClosingBrace(false), BreakAfterComma(false),
326          HasMultiParameterLine(false) {}
327
328    /// \brief The position to which a specific parenthesis level needs to be
329    /// indented.
330    unsigned Indent;
331
332    /// \brief The position of the last space on each level.
333    ///
334    /// Used e.g. to break like:
335    /// functionCall(Parameter, otherCall(
336    ///                             OtherParameter));
337    unsigned LastSpace;
338
339    /// \brief The position the first "<<" operator encountered on each level.
340    ///
341    /// Used to align "<<" operators. 0 if no such operator has been encountered
342    /// on a level.
343    unsigned FirstLessLess;
344
345    /// \brief Whether a newline needs to be inserted before the block's closing
346    /// brace.
347    ///
348    /// We only want to insert a newline before the closing brace if there also
349    /// was a newline after the beginning left brace.
350    bool BreakBeforeClosingBrace;
351
352    bool BreakAfterComma;
353    bool HasMultiParameterLine;
354
355    bool operator<(const ParenState &Other) const {
356      if (Indent != Other.Indent)
357        return Indent < Other.Indent;
358      if (LastSpace != Other.LastSpace)
359        return LastSpace < Other.LastSpace;
360      if (FirstLessLess != Other.FirstLessLess)
361        return FirstLessLess < Other.FirstLessLess;
362      if (BreakBeforeClosingBrace != Other.BreakBeforeClosingBrace)
363        return BreakBeforeClosingBrace;
364      if (BreakAfterComma != Other.BreakAfterComma)
365        return BreakAfterComma;
366      if (HasMultiParameterLine != Other.HasMultiParameterLine)
367        return HasMultiParameterLine;
368      return false;
369    }
370  };
371
372  /// \brief The current state when indenting a unwrapped line.
373  ///
374  /// As the indenting tries different combinations this is copied by value.
375  struct LineState {
376    /// \brief The number of used columns in the current line.
377    unsigned Column;
378
379    /// \brief The token that needs to be next formatted.
380    const AnnotatedToken *NextToken;
381
382    /// \brief The parenthesis level of the first token on the current line.
383    unsigned StartOfLineLevel;
384
385    /// \brief The column of the first variable in a for-loop declaration.
386    ///
387    /// Used to align the second variable if necessary.
388    unsigned ForLoopVariablePos;
389
390    /// \brief \c true if this line contains a continued for-loop section.
391    bool LineContainsContinuedForLoopSection;
392
393    /// \brief A stack keeping track of properties applying to parenthesis
394    /// levels.
395    std::vector<ParenState> Stack;
396
397    /// \brief Comparison operator to be able to used \c LineState in \c map.
398    bool operator<(const LineState &Other) const {
399      if (Other.NextToken != NextToken)
400        return Other.NextToken > NextToken;
401      if (Other.Column != Column)
402        return Other.Column > Column;
403      if (Other.StartOfLineLevel != StartOfLineLevel)
404        return Other.StartOfLineLevel > StartOfLineLevel;
405      if (Other.ForLoopVariablePos != ForLoopVariablePos)
406        return Other.ForLoopVariablePos < ForLoopVariablePos;
407      if (Other.LineContainsContinuedForLoopSection !=
408          LineContainsContinuedForLoopSection)
409        return LineContainsContinuedForLoopSection;
410      return Other.Stack < Stack;
411    }
412  };
413
414  /// \brief Appends the next token to \p State and updates information
415  /// necessary for indentation.
416  ///
417  /// Puts the token on the current line if \p Newline is \c true and adds a
418  /// line break and necessary indentation otherwise.
419  ///
420  /// If \p DryRun is \c false, also creates and stores the required
421  /// \c Replacement.
422  void addTokenToState(bool Newline, bool DryRun, LineState &State) {
423    const AnnotatedToken &Current = *State.NextToken;
424    const AnnotatedToken &Previous = *State.NextToken->Parent;
425    assert(State.Stack.size());
426    unsigned ParenLevel = State.Stack.size() - 1;
427
428    if (Newline) {
429      unsigned WhitespaceStartColumn = State.Column;
430      if (Current.is(tok::r_brace)) {
431        State.Column = Line.Level * 2;
432      } else if (Current.is(tok::string_literal) &&
433                 Previous.is(tok::string_literal)) {
434        State.Column = State.Column - Previous.FormatTok.TokenLength;
435      } else if (Current.is(tok::lessless) &&
436                 State.Stack[ParenLevel].FirstLessLess != 0) {
437        State.Column = State.Stack[ParenLevel].FirstLessLess;
438      } else if (ParenLevel != 0 &&
439                 (Previous.is(tok::equal) || Current.is(tok::arrow) ||
440                  Current.is(tok::period) || Previous.is(tok::question) ||
441                  Previous.Type == TT_ConditionalExpr)) {
442        // Indent and extra 4 spaces after if we know the current expression is
443        // continued.  Don't do that on the top level, as we already indent 4
444        // there.
445        State.Column = State.Stack[ParenLevel].Indent + 4;
446      } else if (RootToken.is(tok::kw_for) && Previous.is(tok::comma)) {
447        State.Column = State.ForLoopVariablePos;
448      } else if (State.NextToken->Parent->ClosesTemplateDeclaration) {
449        State.Column = State.Stack[ParenLevel].Indent - 4;
450      } else {
451        State.Column = State.Stack[ParenLevel].Indent;
452      }
453
454      // A line starting with a closing brace is assumed to be correct for the
455      // same level as before the opening brace.
456      State.StartOfLineLevel = ParenLevel + (Current.is(tok::r_brace) ? 0 : 1);
457
458      if (RootToken.is(tok::kw_for))
459        State.LineContainsContinuedForLoopSection = Previous.isNot(tok::semi);
460
461      if (!DryRun) {
462        if (!Line.InPPDirective)
463          replaceWhitespace(Current.FormatTok, 1, State.Column, Style,
464                            SourceMgr, Replaces);
465        else
466          replacePPWhitespace(Current.FormatTok, 1, State.Column,
467                              WhitespaceStartColumn, Style, SourceMgr,
468                              Replaces);
469      }
470
471      State.Stack[ParenLevel].LastSpace = State.Column;
472      if (Current.is(tok::colon) && State.NextToken->Type != TT_ConditionalExpr)
473        State.Stack[ParenLevel].Indent += 2;
474    } else {
475      if (Current.is(tok::equal) && RootToken.is(tok::kw_for))
476        State.ForLoopVariablePos = State.Column -
477                                   Previous.FormatTok.TokenLength;
478
479      unsigned Spaces = State.NextToken->SpaceRequiredBefore ? 1 : 0;
480      if (State.NextToken->Type == TT_LineComment)
481        Spaces = Style.SpacesBeforeTrailingComments;
482
483      if (!DryRun)
484        replaceWhitespace(Current, 0, Spaces, Style, SourceMgr, Replaces);
485
486      // FIXME: Do we need to do this for assignments nested in other
487      // expressions?
488      if (RootToken.isNot(tok::kw_for) && ParenLevel == 0 &&
489          (getPrecedence(Previous) == prec::Assignment ||
490           Previous.is(tok::kw_return)))
491        State.Stack[ParenLevel].Indent = State.Column + Spaces;
492      if (Previous.is(tok::l_paren) || Previous.is(tok::l_brace) ||
493          State.NextToken->Parent->Type == TT_TemplateOpener)
494        State.Stack[ParenLevel].Indent = State.Column + Spaces;
495      if (Previous.is(tok::comma))
496        State.Stack[ParenLevel].HasMultiParameterLine = true;
497
498
499      // Top-level spaces that are not part of assignments are exempt as that
500      // mostly leads to better results.
501      State.Column += Spaces;
502      if (Spaces > 0 &&
503          (ParenLevel != 0 || getPrecedence(Previous) == prec::Assignment))
504        State.Stack[ParenLevel].LastSpace = State.Column;
505    }
506
507    // If we break after an {, we should also break before the corresponding }.
508    if (Newline && Previous.is(tok::l_brace))
509      State.Stack.back().BreakBeforeClosingBrace = true;
510
511    // If we are breaking after '(', '{', '<' or ',', we need to break after
512    // future commas as well to avoid bin packing.
513    if (!Style.BinPackParameters && Newline &&
514        (Previous.is(tok::comma) || Previous.is(tok::l_paren) ||
515         Previous.is(tok::l_brace) || Previous.Type == TT_TemplateOpener))
516      State.Stack.back().BreakAfterComma = true;
517
518    moveStateToNextToken(State);
519  }
520
521  /// \brief Mark the next token as consumed in \p State and modify its stacks
522  /// accordingly.
523  void moveStateToNextToken(LineState &State) {
524    const AnnotatedToken &Current = *State.NextToken;
525    assert(State.Stack.size());
526
527    if (Current.is(tok::lessless) && State.Stack.back().FirstLessLess == 0)
528      State.Stack.back().FirstLessLess = State.Column;
529
530    // If we encounter an opening (, [, { or <, we add a level to our stacks to
531    // prepare for the following tokens.
532    if (Current.is(tok::l_paren) || Current.is(tok::l_square) ||
533        Current.is(tok::l_brace) ||
534        State.NextToken->Type == TT_TemplateOpener) {
535      unsigned NewIndent;
536      if (Current.is(tok::l_brace)) {
537        // FIXME: This does not work with nested static initializers.
538        // Implement a better handling for static initializers and similar
539        // constructs.
540        NewIndent = Line.Level * 2 + 2;
541      } else {
542        NewIndent = 4 + State.Stack.back().LastSpace;
543      }
544      State.Stack.push_back(
545          ParenState(NewIndent, State.Stack.back().LastSpace));
546
547      // If the entire set of parameters will not fit on the current line, we
548      // will need to break after commas on this level to avoid bin-packing.
549      if (!Style.BinPackParameters && Current.MatchingParen != NULL &&
550          !Current.Children.empty()) {
551        if (getColumnLimit() < State.Column + Current.FormatTok.TokenLength +
552            Current.MatchingParen->TotalLength -
553            Current.Children[0].TotalLength) {
554          State.Stack.back().BreakAfterComma = true;
555        }
556      }
557    }
558
559    // If we encounter a closing ), ], } or >, we can remove a level from our
560    // stacks.
561    if (Current.is(tok::r_paren) || Current.is(tok::r_square) ||
562        (Current.is(tok::r_brace) && State.NextToken != &RootToken) ||
563        State.NextToken->Type == TT_TemplateCloser) {
564      State.Stack.pop_back();
565    }
566
567    if (State.NextToken->Children.empty())
568      State.NextToken = NULL;
569    else
570      State.NextToken = &State.NextToken->Children[0];
571
572    State.Column += Current.FormatTok.TokenLength;
573  }
574
575  /// \brief Calculate the penalty for splitting after the token at \p Index.
576  unsigned splitPenalty(const AnnotatedToken &Tok) {
577    const AnnotatedToken &Left = Tok;
578    const AnnotatedToken &Right = Tok.Children[0];
579
580    if (Left.is(tok::l_brace) && Right.isNot(tok::l_brace))
581      return 50;
582    if (Left.is(tok::equal) && Right.is(tok::l_brace))
583      return 150;
584
585    // In for-loops, prefer breaking at ',' and ';'.
586    if (RootToken.is(tok::kw_for) &&
587        (Left.isNot(tok::comma) && Left.isNot(tok::semi)))
588      return 20;
589
590    if (Left.is(tok::semi) || Left.is(tok::comma) ||
591        Left.ClosesTemplateDeclaration)
592      return 0;
593
594    // In Objective-C method expressions, prefer breaking before "param:" over
595    // breaking after it.
596    if (isObjCSelectorName(Right))
597      return 0;
598    if (Right.is(tok::colon) && Right.Type == TT_ObjCMethodExpr)
599      return 20;
600
601    if (Left.is(tok::l_paren))
602      return 20;
603
604    if (Left.is(tok::question) || Left.Type == TT_ConditionalExpr)
605      return prec::Assignment;
606    prec::Level Level = getPrecedence(Left);
607
608    // Breaking after an assignment leads to a bad result as the two sides of
609    // the assignment are visually very close together.
610    if (Level == prec::Assignment)
611      return 50;
612
613    if (Level != prec::Unknown)
614      return Level;
615
616    if (Right.is(tok::arrow) || Right.is(tok::period))
617      return 150;
618
619    return 3;
620  }
621
622  unsigned getColumnLimit() {
623    return Style.ColumnLimit - (Line.InPPDirective ? 1 : 0);
624  }
625
626  /// \brief Calculate the number of lines needed to format the remaining part
627  /// of the unwrapped line.
628  ///
629  /// Assumes the formatting so far has led to
630  /// the \c LineSta \p State. If \p NewLine is set, a new line will be
631  /// added after the previous token.
632  ///
633  /// \param StopAt is used for optimization. If we can determine that we'll
634  /// definitely need at least \p StopAt additional lines, we already know of a
635  /// better solution.
636  unsigned calcPenalty(LineState State, bool NewLine, unsigned StopAt) {
637    // We are at the end of the unwrapped line, so we don't need any more lines.
638    if (State.NextToken == NULL)
639      return 0;
640
641    if (!NewLine && State.NextToken->MustBreakBefore)
642      return UINT_MAX;
643    if (NewLine && !State.NextToken->CanBreakBefore &&
644        !(State.NextToken->is(tok::r_brace) &&
645          State.Stack.back().BreakBeforeClosingBrace))
646      return UINT_MAX;
647    if (!NewLine && State.NextToken->is(tok::r_brace) &&
648        State.Stack.back().BreakBeforeClosingBrace)
649      return UINT_MAX;
650    if (!NewLine && State.NextToken->Parent->is(tok::semi) &&
651        State.LineContainsContinuedForLoopSection)
652      return UINT_MAX;
653    if (!NewLine && State.NextToken->Parent->is(tok::comma) &&
654        State.NextToken->Type != TT_LineComment &&
655        State.Stack.back().BreakAfterComma)
656      return UINT_MAX;
657    // Trying to insert a parameter on a new line if there are already more than
658    // one parameter on the current line is bin packing.
659    if (NewLine && State.NextToken->Parent->is(tok::comma) &&
660        State.Stack.back().HasMultiParameterLine && !Style.BinPackParameters)
661      return UINT_MAX;
662    if (!NewLine && State.NextToken->Type == TT_CtorInitializerColon)
663      return UINT_MAX;
664
665    unsigned CurrentPenalty = 0;
666    if (NewLine) {
667      CurrentPenalty += Parameters.PenaltyIndentLevel * State.Stack.size() +
668                        splitPenalty(*State.NextToken->Parent);
669    } else {
670      if (State.Stack.size() < State.StartOfLineLevel &&
671          State.NextToken->is(tok::identifier))
672        CurrentPenalty += Parameters.PenaltyLevelDecrease *
673                          (State.StartOfLineLevel - State.Stack.size());
674    }
675
676    addTokenToState(NewLine, true, State);
677
678    // Exceeding column limit is bad, assign penalty.
679    if (State.Column > getColumnLimit()) {
680      unsigned ExcessCharacters = State.Column - getColumnLimit();
681      CurrentPenalty += Parameters.PenaltyExcessCharacter * ExcessCharacters;
682    }
683
684    if (StopAt <= CurrentPenalty)
685      return UINT_MAX;
686    StopAt -= CurrentPenalty;
687    StateMap::iterator I = Memory.find(State);
688    if (I != Memory.end()) {
689      // If this state has already been examined, we can safely return the
690      // previous result if we
691      // - have not hit the optimatization (and thus returned UINT_MAX) OR
692      // - are now computing for a smaller or equal StopAt.
693      unsigned SavedResult = I->second.first;
694      unsigned SavedStopAt = I->second.second;
695      if (SavedResult != UINT_MAX)
696        return SavedResult + CurrentPenalty;
697      else if (StopAt <= SavedStopAt)
698        return UINT_MAX;
699    }
700
701    unsigned NoBreak = calcPenalty(State, false, StopAt);
702    unsigned WithBreak = calcPenalty(State, true, std::min(StopAt, NoBreak));
703    unsigned Result = std::min(NoBreak, WithBreak);
704
705    // We have to store 'Result' without adding 'CurrentPenalty' as the latter
706    // can depend on 'NewLine'.
707    Memory[State] = std::pair<unsigned, unsigned>(Result, StopAt);
708
709    return Result == UINT_MAX ? UINT_MAX : Result + CurrentPenalty;
710  }
711
712  FormatStyle Style;
713  SourceManager &SourceMgr;
714  const AnnotatedLine &Line;
715  const unsigned FirstIndent;
716  const AnnotatedToken &RootToken;
717  tooling::Replacements &Replaces;
718
719  // A map from an indent state to a pair (Result, Used-StopAt).
720  typedef std::map<LineState, std::pair<unsigned, unsigned> > StateMap;
721  StateMap Memory;
722
723  OptimizationParameters Parameters;
724};
725
726/// \brief Determines extra information about the tokens comprising an
727/// \c UnwrappedLine.
728class TokenAnnotator {
729public:
730  TokenAnnotator(const FormatStyle &Style, SourceManager &SourceMgr, Lexer &Lex,
731                 AnnotatedLine &Line)
732      : Style(Style), SourceMgr(SourceMgr), Lex(Lex), Line(Line) {}
733
734  /// \brief A parser that gathers additional information about tokens.
735  ///
736  /// The \c TokenAnnotator tries to matches parenthesis and square brakets and
737  /// store a parenthesis levels. It also tries to resolve matching "<" and ">"
738  /// into template parameter lists.
739  class AnnotatingParser {
740  public:
741    AnnotatingParser(AnnotatedToken &RootToken)
742        : CurrentToken(&RootToken), KeywordVirtualFound(false),
743          ColonIsObjCMethodExpr(false) {}
744
745    bool parseAngle() {
746      if (CurrentToken == NULL)
747        return false;
748      AnnotatedToken *Left = CurrentToken->Parent;
749      while (CurrentToken != NULL) {
750        if (CurrentToken->is(tok::greater)) {
751          Left->MatchingParen = CurrentToken;
752          CurrentToken->MatchingParen = Left;
753          CurrentToken->Type = TT_TemplateCloser;
754          next();
755          return true;
756        }
757        if (CurrentToken->is(tok::r_paren) || CurrentToken->is(tok::r_square) ||
758            CurrentToken->is(tok::r_brace))
759          return false;
760        if (CurrentToken->is(tok::pipepipe) || CurrentToken->is(tok::ampamp) ||
761            CurrentToken->is(tok::question) || CurrentToken->is(tok::colon))
762          return false;
763        if (!consumeToken())
764          return false;
765      }
766      return false;
767    }
768
769    bool parseParens() {
770      if (CurrentToken == NULL)
771        return false;
772      AnnotatedToken *Left = CurrentToken->Parent;
773      if (CurrentToken->is(tok::caret))
774        Left->Type = TT_ObjCBlockLParen;
775      while (CurrentToken != NULL) {
776        if (CurrentToken->is(tok::r_paren)) {
777          Left->MatchingParen = CurrentToken;
778          CurrentToken->MatchingParen = Left;
779          next();
780          return true;
781        }
782        if (CurrentToken->is(tok::r_square) || CurrentToken->is(tok::r_brace))
783          return false;
784        if (!consumeToken())
785          return false;
786      }
787      return false;
788    }
789
790    bool parseSquare() {
791      if (!CurrentToken)
792        return false;
793
794      // A '[' could be an index subscript (after an indentifier or after
795      // ')' or ']'), or it could be the start of an Objective-C method
796      // expression.
797      AnnotatedToken *LSquare = CurrentToken->Parent;
798      bool StartsObjCMethodExpr =
799          !LSquare->Parent || LSquare->Parent->is(tok::colon) ||
800          LSquare->Parent->is(tok::l_square) ||
801          LSquare->Parent->is(tok::l_paren) ||
802          LSquare->Parent->is(tok::kw_return) ||
803          LSquare->Parent->is(tok::kw_throw) ||
804          getBinOpPrecedence(LSquare->Parent->FormatTok.Tok.getKind(),
805                             true, true) > prec::Unknown;
806
807      bool ColonWasObjCMethodExpr = ColonIsObjCMethodExpr;
808      if (StartsObjCMethodExpr) {
809        ColonIsObjCMethodExpr = true;
810        LSquare->Type = TT_ObjCMethodExpr;
811      }
812
813      while (CurrentToken != NULL) {
814        if (CurrentToken->is(tok::r_square)) {
815          if (StartsObjCMethodExpr) {
816            ColonIsObjCMethodExpr = ColonWasObjCMethodExpr;
817            CurrentToken->Type = TT_ObjCMethodExpr;
818          }
819          next();
820          return true;
821        }
822        if (CurrentToken->is(tok::r_paren) || CurrentToken->is(tok::r_brace))
823          return false;
824        if (!consumeToken())
825          return false;
826      }
827      return false;
828    }
829
830    bool parseBrace() {
831      // Lines are fine to end with '{'.
832      if (CurrentToken == NULL)
833        return true;
834      AnnotatedToken *Left = CurrentToken->Parent;
835      while (CurrentToken != NULL) {
836        if (CurrentToken->is(tok::r_brace)) {
837          Left->MatchingParen = CurrentToken;
838          CurrentToken->MatchingParen = Left;
839          next();
840          return true;
841        }
842        if (CurrentToken->is(tok::r_paren) || CurrentToken->is(tok::r_square))
843          return false;
844        if (!consumeToken())
845          return false;
846      }
847      return true;
848    }
849
850    bool parseConditional() {
851      while (CurrentToken != NULL) {
852        if (CurrentToken->is(tok::colon)) {
853          CurrentToken->Type = TT_ConditionalExpr;
854          next();
855          return true;
856        }
857        if (!consumeToken())
858          return false;
859      }
860      return false;
861    }
862
863    bool parseTemplateDeclaration() {
864      if (CurrentToken != NULL && CurrentToken->is(tok::less)) {
865        CurrentToken->Type = TT_TemplateOpener;
866        next();
867        if (!parseAngle())
868          return false;
869        CurrentToken->Parent->ClosesTemplateDeclaration = true;
870        parseLine();
871        return true;
872      }
873      return false;
874    }
875
876    bool consumeToken() {
877      AnnotatedToken *Tok = CurrentToken;
878      next();
879      switch (Tok->FormatTok.Tok.getKind()) {
880      case tok::plus:
881      case tok::minus:
882        // At the start of the line, +/- specific ObjectiveC method
883        // declarations.
884        if (Tok->Parent == NULL)
885          Tok->Type = TT_ObjCMethodSpecifier;
886        break;
887      case tok::colon:
888        // Colons from ?: are handled in parseConditional().
889        if (ColonIsObjCMethodExpr)
890          Tok->Type = TT_ObjCMethodExpr;
891        break;
892      case tok::l_paren: {
893        bool ParensWereObjCReturnType = Tok->Parent && Tok->Parent->Type ==
894                                        TT_ObjCMethodSpecifier;
895        if (!parseParens())
896          return false;
897        if (CurrentToken != NULL && CurrentToken->is(tok::colon)) {
898          CurrentToken->Type = TT_CtorInitializerColon;
899          next();
900        } else if (CurrentToken != NULL && ParensWereObjCReturnType) {
901          CurrentToken->Type = TT_ObjCSelectorStart;
902          next();
903        }
904      } break;
905      case tok::l_square:
906        if (!parseSquare())
907          return false;
908        break;
909      case tok::l_brace:
910        if (!parseBrace())
911          return false;
912        break;
913      case tok::less:
914        if (parseAngle())
915          Tok->Type = TT_TemplateOpener;
916        else {
917          Tok->Type = TT_BinaryOperator;
918          CurrentToken = Tok;
919          next();
920        }
921        break;
922      case tok::r_paren:
923      case tok::r_square:
924        return false;
925      case tok::r_brace:
926        // Lines can start with '}'.
927        if (Tok->Parent != NULL)
928          return false;
929        break;
930      case tok::greater:
931        Tok->Type = TT_BinaryOperator;
932        break;
933      case tok::kw_operator:
934        if (CurrentToken->is(tok::l_paren)) {
935          CurrentToken->Type = TT_OverloadedOperator;
936          next();
937          if (CurrentToken != NULL && CurrentToken->is(tok::r_paren)) {
938            CurrentToken->Type = TT_OverloadedOperator;
939            next();
940          }
941        } else {
942          while (CurrentToken != NULL && CurrentToken->isNot(tok::l_paren)) {
943            CurrentToken->Type = TT_OverloadedOperator;
944            next();
945          }
946        }
947        break;
948      case tok::question:
949        parseConditional();
950        break;
951      case tok::kw_template:
952        parseTemplateDeclaration();
953        break;
954      default:
955        break;
956      }
957      return true;
958    }
959
960    void parseIncludeDirective() {
961      next();
962      if (CurrentToken != NULL && CurrentToken->is(tok::less)) {
963        next();
964        while (CurrentToken != NULL) {
965          CurrentToken->Type = TT_ImplicitStringLiteral;
966          next();
967        }
968      } else {
969        while (CurrentToken != NULL) {
970          next();
971        }
972      }
973    }
974
975    void parseWarningOrError() {
976      next();
977      // We still want to format the whitespace left of the first token of the
978      // warning or error.
979      next();
980      while (CurrentToken != NULL) {
981        CurrentToken->Type = TT_ImplicitStringLiteral;
982        next();
983      }
984    }
985
986    void parsePreprocessorDirective() {
987      next();
988      if (CurrentToken == NULL)
989        return;
990      // Hashes in the middle of a line can lead to any strange token
991      // sequence.
992      if (CurrentToken->FormatTok.Tok.getIdentifierInfo() == NULL)
993        return;
994      switch (
995          CurrentToken->FormatTok.Tok.getIdentifierInfo()->getPPKeywordID()) {
996      case tok::pp_include:
997      case tok::pp_import:
998        parseIncludeDirective();
999        break;
1000      case tok::pp_error:
1001      case tok::pp_warning:
1002        parseWarningOrError();
1003        break;
1004      default:
1005        break;
1006      }
1007    }
1008
1009    LineType parseLine() {
1010      if (CurrentToken->is(tok::hash)) {
1011        parsePreprocessorDirective();
1012        return LT_PreprocessorDirective;
1013      }
1014      while (CurrentToken != NULL) {
1015        if (CurrentToken->is(tok::kw_virtual))
1016          KeywordVirtualFound = true;
1017        if (!consumeToken())
1018          return LT_Invalid;
1019      }
1020      if (KeywordVirtualFound)
1021        return LT_VirtualFunctionDecl;
1022      return LT_Other;
1023    }
1024
1025    void next() {
1026      if (CurrentToken != NULL && !CurrentToken->Children.empty())
1027        CurrentToken = &CurrentToken->Children[0];
1028      else
1029        CurrentToken = NULL;
1030    }
1031
1032  private:
1033    AnnotatedToken *CurrentToken;
1034    bool KeywordVirtualFound;
1035    bool ColonIsObjCMethodExpr;
1036  };
1037
1038  void calculateExtraInformation(AnnotatedToken &Current) {
1039    Current.SpaceRequiredBefore = spaceRequiredBefore(Current);
1040
1041    if (Current.FormatTok.MustBreakBefore) {
1042      Current.MustBreakBefore = true;
1043    } else {
1044      if (Current.Type == TT_LineComment) {
1045        Current.MustBreakBefore = Current.FormatTok.NewlinesBefore > 0;
1046      } else if (Current.Parent->Type == TT_LineComment ||
1047                 (Current.is(tok::string_literal) &&
1048                  Current.Parent->is(tok::string_literal))) {
1049        Current.MustBreakBefore = true;
1050      } else {
1051        Current.MustBreakBefore = false;
1052      }
1053    }
1054    Current.CanBreakBefore = Current.MustBreakBefore || canBreakBefore(Current);
1055    if (Current.MustBreakBefore)
1056      Current.TotalLength = Current.Parent->TotalLength + Style.ColumnLimit;
1057    else
1058      Current.TotalLength = Current.Parent->TotalLength +
1059                            Current.FormatTok.TokenLength +
1060                            (Current.SpaceRequiredBefore ? 1 : 0);
1061    if (!Current.Children.empty())
1062      calculateExtraInformation(Current.Children[0]);
1063  }
1064
1065  void annotate() {
1066    AnnotatingParser Parser(Line.First);
1067    Line.Type = Parser.parseLine();
1068    if (Line.Type == LT_Invalid)
1069      return;
1070
1071    determineTokenTypes(Line.First, /*IsRHS=*/false);
1072
1073    if (Line.First.Type == TT_ObjCMethodSpecifier)
1074      Line.Type = LT_ObjCMethodDecl;
1075    else if (Line.First.Type == TT_ObjCDecl)
1076      Line.Type = LT_ObjCDecl;
1077    else if (Line.First.Type == TT_ObjCProperty)
1078      Line.Type = LT_ObjCProperty;
1079
1080    Line.First.SpaceRequiredBefore = true;
1081    Line.First.MustBreakBefore = Line.First.FormatTok.MustBreakBefore;
1082    Line.First.CanBreakBefore = Line.First.MustBreakBefore;
1083
1084    Line.First.TotalLength = Line.First.FormatTok.TokenLength;
1085    if (!Line.First.Children.empty())
1086      calculateExtraInformation(Line.First.Children[0]);
1087  }
1088
1089private:
1090  void determineTokenTypes(AnnotatedToken &Current, bool IsRHS) {
1091    if (getPrecedence(Current) == prec::Assignment ||
1092        Current.is(tok::kw_return) || Current.is(tok::kw_throw))
1093      IsRHS = true;
1094
1095    if (Current.Type == TT_Unknown) {
1096      if (Current.is(tok::star) || Current.is(tok::amp)) {
1097        Current.Type = determineStarAmpUsage(Current, IsRHS);
1098      } else if (Current.is(tok::minus) || Current.is(tok::plus) ||
1099                 Current.is(tok::caret)) {
1100        Current.Type = determinePlusMinusCaretUsage(Current);
1101      } else if (Current.is(tok::minusminus) || Current.is(tok::plusplus)) {
1102        Current.Type = determineIncrementUsage(Current);
1103      } else if (Current.is(tok::exclaim)) {
1104        Current.Type = TT_UnaryOperator;
1105      } else if (isBinaryOperator(Current)) {
1106        Current.Type = TT_BinaryOperator;
1107      } else if (Current.is(tok::comment)) {
1108        std::string Data(Lexer::getSpelling(Current.FormatTok.Tok, SourceMgr,
1109                                            Lex.getLangOpts()));
1110        if (StringRef(Data).startswith("//"))
1111          Current.Type = TT_LineComment;
1112        else
1113          Current.Type = TT_BlockComment;
1114      } else if (Current.is(tok::r_paren) &&
1115                 (Current.Parent->Type == TT_PointerOrReference ||
1116                  Current.Parent->Type == TT_TemplateCloser) &&
1117                 (Current.Children.empty() ||
1118                  (Current.Children[0].isNot(tok::equal) &&
1119                   Current.Children[0].isNot(tok::semi) &&
1120                   Current.Children[0].isNot(tok::l_brace)))) {
1121        // FIXME: We need to get smarter and understand more cases of casts.
1122        Current.Type = TT_CastRParen;
1123      } else if (Current.is(tok::at) && Current.Children.size()) {
1124        switch (Current.Children[0].FormatTok.Tok.getObjCKeywordID()) {
1125        case tok::objc_interface:
1126        case tok::objc_implementation:
1127        case tok::objc_protocol:
1128          Current.Type = TT_ObjCDecl;
1129          break;
1130        case tok::objc_property:
1131          Current.Type = TT_ObjCProperty;
1132          break;
1133        default:
1134          break;
1135        }
1136      }
1137    }
1138
1139    if (!Current.Children.empty())
1140      determineTokenTypes(Current.Children[0], IsRHS);
1141  }
1142
1143  bool isBinaryOperator(const AnnotatedToken &Tok) {
1144    // Comma is a binary operator, but does not behave as such wrt. formatting.
1145    return getPrecedence(Tok) > prec::Comma;
1146  }
1147
1148  /// \brief Returns the previous token ignoring comments.
1149  const AnnotatedToken *getPreviousToken(const AnnotatedToken &Tok) {
1150    const AnnotatedToken *PrevToken = Tok.Parent;
1151    while (PrevToken != NULL && PrevToken->is(tok::comment))
1152      PrevToken = PrevToken->Parent;
1153    return PrevToken;
1154  }
1155
1156  /// \brief Returns the next token ignoring comments.
1157  const AnnotatedToken *getNextToken(const AnnotatedToken &Tok) {
1158    if (Tok.Children.empty())
1159      return NULL;
1160    const AnnotatedToken *NextToken = &Tok.Children[0];
1161    while (NextToken->is(tok::comment)) {
1162      if (NextToken->Children.empty())
1163        return NULL;
1164      NextToken = &NextToken->Children[0];
1165    }
1166    return NextToken;
1167  }
1168
1169  /// \brief Return the type of the given token assuming it is * or &.
1170  TokenType determineStarAmpUsage(const AnnotatedToken &Tok, bool IsRHS) {
1171    const AnnotatedToken *PrevToken = getPreviousToken(Tok);
1172    if (PrevToken == NULL)
1173      return TT_UnaryOperator;
1174
1175    const AnnotatedToken *NextToken = getNextToken(Tok);
1176    if (NextToken == NULL)
1177      return TT_Unknown;
1178
1179    if (PrevToken->is(tok::l_paren) || PrevToken->is(tok::l_square) ||
1180        PrevToken->is(tok::l_brace) || PrevToken->is(tok::comma) ||
1181        PrevToken->is(tok::kw_return) || PrevToken->is(tok::colon) ||
1182        PrevToken->Type == TT_BinaryOperator ||
1183        PrevToken->Type == TT_CastRParen)
1184      return TT_UnaryOperator;
1185
1186    if (PrevToken->FormatTok.Tok.isLiteral() || PrevToken->is(tok::r_paren) ||
1187        PrevToken->is(tok::r_square) || NextToken->FormatTok.Tok.isLiteral() ||
1188        NextToken->is(tok::plus) || NextToken->is(tok::minus) ||
1189        NextToken->is(tok::plusplus) || NextToken->is(tok::minusminus) ||
1190        NextToken->is(tok::tilde) || NextToken->is(tok::exclaim) ||
1191        NextToken->is(tok::l_paren) || NextToken->is(tok::l_square) ||
1192        NextToken->is(tok::kw_alignof) || NextToken->is(tok::kw_sizeof))
1193      return TT_BinaryOperator;
1194
1195    if (NextToken->is(tok::comma) || NextToken->is(tok::r_paren) ||
1196        NextToken->is(tok::greater))
1197      return TT_PointerOrReference;
1198
1199    // It is very unlikely that we are going to find a pointer or reference type
1200    // definition on the RHS of an assignment.
1201    if (IsRHS)
1202      return TT_BinaryOperator;
1203
1204    return TT_PointerOrReference;
1205  }
1206
1207  TokenType determinePlusMinusCaretUsage(const AnnotatedToken &Tok) {
1208    const AnnotatedToken *PrevToken = getPreviousToken(Tok);
1209    if (PrevToken == NULL)
1210      return TT_UnaryOperator;
1211
1212    // Use heuristics to recognize unary operators.
1213    if (PrevToken->is(tok::equal) || PrevToken->is(tok::l_paren) ||
1214        PrevToken->is(tok::comma) || PrevToken->is(tok::l_square) ||
1215        PrevToken->is(tok::question) || PrevToken->is(tok::colon) ||
1216        PrevToken->is(tok::kw_return) || PrevToken->is(tok::kw_case) ||
1217        PrevToken->is(tok::at) || PrevToken->is(tok::l_brace))
1218      return TT_UnaryOperator;
1219
1220    // There can't be to consecutive binary operators.
1221    if (PrevToken->Type == TT_BinaryOperator)
1222      return TT_UnaryOperator;
1223
1224    // Fall back to marking the token as binary operator.
1225    return TT_BinaryOperator;
1226  }
1227
1228  /// \brief Determine whether ++/-- are pre- or post-increments/-decrements.
1229  TokenType determineIncrementUsage(const AnnotatedToken &Tok) {
1230    const AnnotatedToken *PrevToken = getPreviousToken(Tok);
1231    if (PrevToken == NULL)
1232      return TT_UnaryOperator;
1233    if (PrevToken->is(tok::r_paren) || PrevToken->is(tok::r_square) ||
1234        PrevToken->is(tok::identifier))
1235      return TT_TrailingUnaryOperator;
1236
1237    return TT_UnaryOperator;
1238  }
1239
1240  bool spaceRequiredBetween(const AnnotatedToken &Left,
1241                            const AnnotatedToken &Right) {
1242    if (Right.is(tok::hashhash))
1243      return Left.is(tok::hash);
1244    if (Left.is(tok::hashhash) || Left.is(tok::hash))
1245      return Right.is(tok::hash);
1246    if (Right.is(tok::r_paren) || Right.is(tok::semi) || Right.is(tok::comma))
1247      return false;
1248    if (Right.is(tok::less) &&
1249        (Left.is(tok::kw_template) ||
1250         (Line.Type == LT_ObjCDecl && Style.ObjCSpaceBeforeProtocolList)))
1251      return true;
1252    if (Left.is(tok::arrow) || Right.is(tok::arrow))
1253      return false;
1254    if (Left.is(tok::exclaim) || Left.is(tok::tilde))
1255      return false;
1256    if (Left.is(tok::at) &&
1257        (Right.is(tok::identifier) || Right.is(tok::string_literal) ||
1258         Right.is(tok::char_constant) || Right.is(tok::numeric_constant) ||
1259         Right.is(tok::l_paren) || Right.is(tok::l_brace) ||
1260         Right.is(tok::kw_true) || Right.is(tok::kw_false)))
1261      return false;
1262    if (Left.is(tok::coloncolon))
1263      return false;
1264    if (Right.is(tok::coloncolon))
1265      return Left.isNot(tok::identifier) && Left.isNot(tok::greater);
1266    if (Left.is(tok::less) || Right.is(tok::greater) || Right.is(tok::less))
1267      return false;
1268    if (Right.is(tok::amp) || Right.is(tok::star))
1269      return Left.FormatTok.Tok.isLiteral() ||
1270             (Left.isNot(tok::star) && Left.isNot(tok::amp) &&
1271              !Style.PointerAndReferenceBindToType);
1272    if (Left.is(tok::amp) || Left.is(tok::star))
1273      return Right.FormatTok.Tok.isLiteral() ||
1274             Style.PointerAndReferenceBindToType;
1275    if (Right.is(tok::star) && Left.is(tok::l_paren))
1276      return false;
1277    if (Left.is(tok::l_square) || Right.is(tok::r_square))
1278      return false;
1279    if (Right.is(tok::l_square) && Right.Type != TT_ObjCMethodExpr)
1280      return false;
1281    if (Left.is(tok::period) || Right.is(tok::period))
1282      return false;
1283    if (Left.is(tok::colon))
1284      return Left.Type != TT_ObjCMethodExpr;
1285    if (Right.is(tok::colon))
1286      return Right.Type != TT_ObjCMethodExpr;
1287    if (Left.is(tok::l_paren))
1288      return false;
1289    if (Right.is(tok::l_paren)) {
1290      return Line.Type == LT_ObjCDecl || Left.is(tok::kw_if) ||
1291             Left.is(tok::kw_for) || Left.is(tok::kw_while) ||
1292             Left.is(tok::kw_switch) || Left.is(tok::kw_return) ||
1293             Left.is(tok::kw_catch) || Left.is(tok::kw_new) ||
1294             Left.is(tok::kw_delete);
1295    }
1296    if (Left.is(tok::at) &&
1297        Right.FormatTok.Tok.getObjCKeywordID() != tok::objc_not_keyword)
1298      return false;
1299    if (Left.is(tok::l_brace) && Right.is(tok::r_brace))
1300      return false;
1301    return true;
1302  }
1303
1304  bool spaceRequiredBefore(const AnnotatedToken &Tok) {
1305    if (Line.Type == LT_ObjCMethodDecl) {
1306      if (Tok.is(tok::identifier) && !Tok.Children.empty() &&
1307          Tok.Children[0].is(tok::colon) && Tok.Parent->is(tok::identifier))
1308        return true;
1309      if (Tok.is(tok::colon))
1310        return false;
1311      if (Tok.Parent->Type == TT_ObjCMethodSpecifier)
1312        return Style.ObjCSpaceBeforeReturnType || Tok.isNot(tok::l_paren);
1313      if (Tok.Type == TT_ObjCSelectorStart)
1314        return !Style.ObjCSpaceBeforeReturnType;
1315      if (Tok.Parent->is(tok::r_paren) && Tok.is(tok::identifier))
1316        // Don't space between ')' and <id>
1317        return false;
1318      if (Tok.Parent->is(tok::colon) && Tok.is(tok::l_paren))
1319        // Don't space between ':' and '('
1320        return false;
1321    }
1322    if (Line.Type == LT_ObjCProperty &&
1323        (Tok.is(tok::equal) || Tok.Parent->is(tok::equal)))
1324      return false;
1325
1326    if (Tok.Parent->is(tok::comma))
1327      return true;
1328    if (Tok.Type == TT_CtorInitializerColon || Tok.Type == TT_ObjCBlockLParen)
1329      return true;
1330    if (Tok.Type == TT_OverloadedOperator)
1331      return Tok.is(tok::identifier) || Tok.is(tok::kw_new) ||
1332             Tok.is(tok::kw_delete) || Tok.is(tok::kw_bool);
1333    if (Tok.Parent->Type == TT_OverloadedOperator)
1334      return false;
1335    if (Tok.is(tok::colon))
1336      return Line.First.isNot(tok::kw_case) && !Tok.Children.empty() &&
1337             Tok.Type != TT_ObjCMethodExpr;
1338    if (Tok.Parent->Type == TT_UnaryOperator ||
1339        Tok.Parent->Type == TT_CastRParen)
1340      return false;
1341    if (Tok.Type == TT_UnaryOperator)
1342      return Tok.Parent->isNot(tok::l_paren) &&
1343             Tok.Parent->isNot(tok::l_square) && Tok.Parent->isNot(tok::at) &&
1344             (Tok.Parent->isNot(tok::colon) ||
1345              Tok.Parent->Type != TT_ObjCMethodExpr);
1346    if (Tok.Parent->is(tok::greater) && Tok.is(tok::greater)) {
1347      return Tok.Type == TT_TemplateCloser && Tok.Parent->Type ==
1348             TT_TemplateCloser && Style.SplitTemplateClosingGreater;
1349    }
1350    if (Tok.Type == TT_BinaryOperator || Tok.Parent->Type == TT_BinaryOperator)
1351      return true;
1352    if (Tok.Parent->Type == TT_TemplateCloser && Tok.is(tok::l_paren))
1353      return false;
1354    if (Tok.is(tok::less) && Line.First.is(tok::hash))
1355      return true;
1356    if (Tok.Type == TT_TrailingUnaryOperator)
1357      return false;
1358    return spaceRequiredBetween(*Tok.Parent, Tok);
1359  }
1360
1361  bool canBreakBefore(const AnnotatedToken &Right) {
1362    const AnnotatedToken &Left = *Right.Parent;
1363    if (Line.Type == LT_ObjCMethodDecl) {
1364      if (Right.is(tok::identifier) && !Right.Children.empty() &&
1365          Right.Children[0].is(tok::colon) && Left.is(tok::identifier))
1366        return true;
1367      if (Right.is(tok::identifier) && Left.is(tok::l_paren) &&
1368          Left.Parent->is(tok::colon))
1369        // Don't break this identifier as ':' or identifier
1370        // before it will break.
1371        return false;
1372      if (Right.is(tok::colon) && Left.is(tok::identifier) &&
1373          Left.CanBreakBefore)
1374        // Don't break at ':' if identifier before it can beak.
1375        return false;
1376    }
1377    if (Right.is(tok::colon) && Right.Type == TT_ObjCMethodExpr)
1378      return false;
1379    if (Left.is(tok::colon) && Left.Type == TT_ObjCMethodExpr)
1380      return true;
1381    if (isObjCSelectorName(Right))
1382      return true;
1383    if (Left.ClosesTemplateDeclaration)
1384      return true;
1385    if (Left.Type == TT_PointerOrReference || Left.Type == TT_TemplateCloser ||
1386        Left.Type == TT_UnaryOperator || Right.Type == TT_ConditionalExpr)
1387      return false;
1388    if (Left.is(tok::equal) && Line.Type == LT_VirtualFunctionDecl)
1389      return false;
1390
1391    if (Right.is(tok::comment))
1392      // We rely on MustBreakBefore being set correctly here as we should not
1393      // change the "binding" behavior of a comment.
1394      return false;
1395
1396    // We only break before r_brace if there was a corresponding break before
1397    // the l_brace, which is tracked by BreakBeforeClosingBrace.
1398    if (Right.is(tok::r_brace))
1399      return false;
1400
1401    if (Right.is(tok::r_paren) || Right.is(tok::greater))
1402      return false;
1403    return (isBinaryOperator(Left) && Left.isNot(tok::lessless)) ||
1404           Left.is(tok::comma) || Right.is(tok::lessless) ||
1405           Right.is(tok::arrow) || Right.is(tok::period) ||
1406           Right.is(tok::colon) || Left.is(tok::semi) ||
1407           Left.is(tok::l_brace) || Left.is(tok::question) || Left.Type ==
1408           TT_ConditionalExpr || (Left.is(tok::r_paren) && Left.Type !=
1409                                  TT_CastRParen && Right.is(tok::identifier)) ||
1410           (Left.is(tok::l_paren) && !Right.is(tok::r_paren));
1411  }
1412
1413  FormatStyle Style;
1414  SourceManager &SourceMgr;
1415  Lexer &Lex;
1416  AnnotatedLine &Line;
1417};
1418
1419class LexerBasedFormatTokenSource : public FormatTokenSource {
1420public:
1421  LexerBasedFormatTokenSource(Lexer &Lex, SourceManager &SourceMgr)
1422      : GreaterStashed(false), Lex(Lex), SourceMgr(SourceMgr),
1423        IdentTable(Lex.getLangOpts()) {
1424    Lex.SetKeepWhitespaceMode(true);
1425  }
1426
1427  virtual FormatToken getNextToken() {
1428    if (GreaterStashed) {
1429      FormatTok.NewlinesBefore = 0;
1430      FormatTok.WhiteSpaceStart =
1431          FormatTok.Tok.getLocation().getLocWithOffset(1);
1432      FormatTok.WhiteSpaceLength = 0;
1433      GreaterStashed = false;
1434      return FormatTok;
1435    }
1436
1437    FormatTok = FormatToken();
1438    Lex.LexFromRawLexer(FormatTok.Tok);
1439    StringRef Text = rawTokenText(FormatTok.Tok);
1440    FormatTok.WhiteSpaceStart = FormatTok.Tok.getLocation();
1441    if (SourceMgr.getFileOffset(FormatTok.WhiteSpaceStart) == 0)
1442      FormatTok.IsFirst = true;
1443
1444    // Consume and record whitespace until we find a significant token.
1445    while (FormatTok.Tok.is(tok::unknown)) {
1446      FormatTok.NewlinesBefore += Text.count('\n');
1447      FormatTok.HasUnescapedNewline = Text.count("\\\n") !=
1448                                      FormatTok.NewlinesBefore;
1449      FormatTok.WhiteSpaceLength += FormatTok.Tok.getLength();
1450
1451      if (FormatTok.Tok.is(tok::eof))
1452        return FormatTok;
1453      Lex.LexFromRawLexer(FormatTok.Tok);
1454      Text = rawTokenText(FormatTok.Tok);
1455    }
1456
1457    // Now FormatTok is the next non-whitespace token.
1458    FormatTok.TokenLength = Text.size();
1459
1460    // In case the token starts with escaped newlines, we want to
1461    // take them into account as whitespace - this pattern is quite frequent
1462    // in macro definitions.
1463    // FIXME: What do we want to do with other escaped spaces, and escaped
1464    // spaces or newlines in the middle of tokens?
1465    // FIXME: Add a more explicit test.
1466    unsigned i = 0;
1467    while (i + 1 < Text.size() && Text[i] == '\\' && Text[i + 1] == '\n') {
1468      FormatTok.WhiteSpaceLength += 2;
1469      FormatTok.TokenLength -= 2;
1470      i += 2;
1471    }
1472
1473    if (FormatTok.Tok.is(tok::raw_identifier)) {
1474      IdentifierInfo &Info = IdentTable.get(Text);
1475      FormatTok.Tok.setIdentifierInfo(&Info);
1476      FormatTok.Tok.setKind(Info.getTokenID());
1477    }
1478
1479    if (FormatTok.Tok.is(tok::greatergreater)) {
1480      FormatTok.Tok.setKind(tok::greater);
1481      GreaterStashed = true;
1482    }
1483
1484    return FormatTok;
1485  }
1486
1487private:
1488  FormatToken FormatTok;
1489  bool GreaterStashed;
1490  Lexer &Lex;
1491  SourceManager &SourceMgr;
1492  IdentifierTable IdentTable;
1493
1494  /// Returns the text of \c FormatTok.
1495  StringRef rawTokenText(Token &Tok) {
1496    return StringRef(SourceMgr.getCharacterData(Tok.getLocation()),
1497                     Tok.getLength());
1498  }
1499};
1500
1501class Formatter : public UnwrappedLineConsumer {
1502public:
1503  Formatter(DiagnosticsEngine &Diag, const FormatStyle &Style, Lexer &Lex,
1504            SourceManager &SourceMgr,
1505            const std::vector<CharSourceRange> &Ranges)
1506      : Diag(Diag), Style(Style), Lex(Lex), SourceMgr(SourceMgr),
1507        Ranges(Ranges) {}
1508
1509  virtual ~Formatter() {}
1510
1511  tooling::Replacements format() {
1512    LexerBasedFormatTokenSource Tokens(Lex, SourceMgr);
1513    UnwrappedLineParser Parser(Diag, Style, Tokens, *this);
1514    StructuralError = Parser.parse();
1515    unsigned PreviousEndOfLineColumn = 0;
1516    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1517      TokenAnnotator Annotator(Style, SourceMgr, Lex, AnnotatedLines[i]);
1518      Annotator.annotate();
1519    }
1520    for (std::vector<AnnotatedLine>::iterator I = AnnotatedLines.begin(),
1521                                              E = AnnotatedLines.end();
1522         I != E; ++I) {
1523      const AnnotatedLine &TheLine = *I;
1524      if (touchesRanges(TheLine) && TheLine.Type != LT_Invalid) {
1525        unsigned Indent = formatFirstToken(TheLine.First, TheLine.Level,
1526                                           TheLine.InPPDirective,
1527                                           PreviousEndOfLineColumn);
1528        tryFitMultipleLinesInOne(Indent, I, E);
1529        UnwrappedLineFormatter Formatter(Style, SourceMgr, TheLine, Indent,
1530                                         TheLine.First, Replaces,
1531                                         StructuralError);
1532        PreviousEndOfLineColumn = Formatter.format();
1533      } else {
1534        // If we did not reformat this unwrapped line, the column at the end of
1535        // the last token is unchanged - thus, we can calculate the end of the
1536        // last token, and return the result.
1537        PreviousEndOfLineColumn =
1538            SourceMgr.getSpellingColumnNumber(
1539                TheLine.Last->FormatTok.Tok.getLocation()) +
1540            Lex.MeasureTokenLength(TheLine.Last->FormatTok.Tok.getLocation(),
1541                                   SourceMgr, Lex.getLangOpts()) -
1542            1;
1543      }
1544    }
1545    return Replaces;
1546  }
1547
1548private:
1549  /// \brief Tries to merge lines into one.
1550  ///
1551  /// This will change \c Line and \c AnnotatedLine to contain the merged line,
1552  /// if possible; note that \c I will be incremented when lines are merged.
1553  ///
1554  /// Returns whether the resulting \c Line can fit in a single line.
1555  void tryFitMultipleLinesInOne(unsigned Indent,
1556                                std::vector<AnnotatedLine>::iterator &I,
1557                                std::vector<AnnotatedLine>::iterator E) {
1558    unsigned Limit = Style.ColumnLimit - (I->InPPDirective ? 1 : 0) - Indent;
1559
1560    // We can never merge stuff if there are trailing line comments.
1561    if (I->Last->Type == TT_LineComment)
1562      return;
1563
1564    // Check whether the UnwrappedLine can be put onto a single line. If
1565    // so, this is bound to be the optimal solution (by definition) and we
1566    // don't need to analyze the entire solution space.
1567    if (I->Last->TotalLength >= Limit)
1568      return;
1569    Limit -= I->Last->TotalLength + 1; // One space.
1570
1571    if (I + 1 == E)
1572      return;
1573
1574    if (I->Last->is(tok::l_brace)) {
1575      tryMergeSimpleBlock(I, E, Limit);
1576    } else if (I->First.is(tok::kw_if)) {
1577      tryMergeSimpleIf(I, E, Limit);
1578    } else if (I->InPPDirective && (I->First.FormatTok.HasUnescapedNewline ||
1579                                    I->First.FormatTok.IsFirst)) {
1580      tryMergeSimplePPDirective(I, E, Limit);
1581    }
1582    return;
1583  }
1584
1585  void tryMergeSimplePPDirective(std::vector<AnnotatedLine>::iterator &I,
1586                                 std::vector<AnnotatedLine>::iterator E,
1587                                 unsigned Limit) {
1588    AnnotatedLine &Line = *I;
1589    if (!(I + 1)->InPPDirective || (I + 1)->First.FormatTok.HasUnescapedNewline)
1590      return;
1591    if (I + 2 != E && (I + 2)->InPPDirective &&
1592        !(I + 2)->First.FormatTok.HasUnescapedNewline)
1593      return;
1594    if ((I + 1)->Last->TotalLength > Limit)
1595      return;
1596    join(Line, *(++I));
1597  }
1598
1599  void tryMergeSimpleIf(std::vector<AnnotatedLine>::iterator &I,
1600                        std::vector<AnnotatedLine>::iterator E,
1601                        unsigned Limit) {
1602    if (!Style.AllowShortIfStatementsOnASingleLine)
1603      return;
1604    AnnotatedLine &Line = *I;
1605    if (Line.Last->isNot(tok::r_paren))
1606      return;
1607    if ((I + 1)->Last->TotalLength > Limit)
1608      return;
1609    if ((I + 1)->First.is(tok::kw_if) || (I + 1)->First.Type == TT_LineComment)
1610      return;
1611    // Only inline simple if's (no nested if or else).
1612    if (I + 2 != E && (I + 2)->First.is(tok::kw_else))
1613      return;
1614    join(Line, *(++I));
1615  }
1616
1617  void tryMergeSimpleBlock(std::vector<AnnotatedLine>::iterator &I,
1618                        std::vector<AnnotatedLine>::iterator E,
1619                        unsigned Limit){
1620    // Check that we still have three lines and they fit into the limit.
1621    if (I + 2 == E || !nextTwoLinesFitInto(I, Limit))
1622      return;
1623
1624    // First, check that the current line allows merging. This is the case if
1625    // we're not in a control flow statement and the last token is an opening
1626    // brace.
1627    AnnotatedLine &Line = *I;
1628    bool AllowedTokens =
1629        Line.First.isNot(tok::kw_if) && Line.First.isNot(tok::kw_while) &&
1630        Line.First.isNot(tok::kw_do) && Line.First.isNot(tok::r_brace) &&
1631        Line.First.isNot(tok::kw_else) && Line.First.isNot(tok::kw_try) &&
1632        Line.First.isNot(tok::kw_catch) && Line.First.isNot(tok::kw_for) &&
1633        // This gets rid of all ObjC @ keywords and methods.
1634        Line.First.isNot(tok::at) && Line.First.isNot(tok::minus) &&
1635        Line.First.isNot(tok::plus);
1636    if (!AllowedTokens)
1637      return;
1638
1639    // Second, check that the next line does not contain any braces - if it
1640    // does, readability declines when putting it into a single line.
1641    const AnnotatedToken *Tok = &(I + 1)->First;
1642    if ((I + 1)->Last->Type == TT_LineComment || Tok->MustBreakBefore)
1643      return;
1644    do {
1645      if (Tok->is(tok::l_brace) || Tok->is(tok::r_brace))
1646        return;
1647      Tok = Tok->Children.empty() ? NULL : &Tok->Children.back();
1648    } while (Tok != NULL);
1649
1650    // Last, check that the third line contains a single closing brace.
1651    Tok = &(I + 2)->First;
1652    if (!Tok->Children.empty() || Tok->isNot(tok::r_brace) ||
1653        Tok->MustBreakBefore)
1654      return;
1655
1656    // If the merged line fits, we use that instead and skip the next two lines.
1657    Line.Last->Children.push_back((I + 1)->First);
1658    while (!Line.Last->Children.empty()) {
1659      Line.Last->Children[0].Parent = Line.Last;
1660      Line.Last = &Line.Last->Children[0];
1661    }
1662
1663    join(Line, *(I + 1));
1664    join(Line, *(I + 2));
1665    I += 2;
1666  }
1667
1668  bool nextTwoLinesFitInto(std::vector<AnnotatedLine>::iterator I,
1669                           unsigned Limit) {
1670    return (I + 1)->Last->TotalLength + 1 + (I + 2)->Last->TotalLength <= Limit;
1671  }
1672
1673  void join(AnnotatedLine &A, const AnnotatedLine &B) {
1674    A.Last->Children.push_back(B.First);
1675    while (!A.Last->Children.empty()) {
1676      A.Last->Children[0].Parent = A.Last;
1677      A.Last = &A.Last->Children[0];
1678    }
1679  }
1680
1681  bool touchesRanges(const AnnotatedLine &TheLine) {
1682    const FormatToken *First = &TheLine.First.FormatTok;
1683    const FormatToken *Last = &TheLine.Last->FormatTok;
1684    CharSourceRange LineRange = CharSourceRange::getTokenRange(
1685                                    First->Tok.getLocation(),
1686                                    Last->Tok.getLocation());
1687    for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1688      if (!SourceMgr.isBeforeInTranslationUnit(LineRange.getEnd(),
1689                                               Ranges[i].getBegin()) &&
1690          !SourceMgr.isBeforeInTranslationUnit(Ranges[i].getEnd(),
1691                                               LineRange.getBegin()))
1692        return true;
1693    }
1694    return false;
1695  }
1696
1697  virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) {
1698    AnnotatedLines.push_back(AnnotatedLine(TheLine));
1699  }
1700
1701  /// \brief Add a new line and the required indent before the first Token
1702  /// of the \c UnwrappedLine if there was no structural parsing error.
1703  /// Returns the indent level of the \c UnwrappedLine.
1704  unsigned formatFirstToken(const AnnotatedToken &RootToken, unsigned Level,
1705                            bool InPPDirective,
1706                            unsigned PreviousEndOfLineColumn) {
1707    const FormatToken &Tok = RootToken.FormatTok;
1708    if (!Tok.WhiteSpaceStart.isValid() || StructuralError)
1709      return SourceMgr.getSpellingColumnNumber(Tok.Tok.getLocation()) - 1;
1710
1711    unsigned Newlines = std::min(Tok.NewlinesBefore,
1712                                 Style.MaxEmptyLinesToKeep + 1);
1713    if (Newlines == 0 && !Tok.IsFirst)
1714      Newlines = 1;
1715    unsigned Indent = Level * 2;
1716
1717    bool IsAccessModifier = false;
1718    if (RootToken.is(tok::kw_public) || RootToken.is(tok::kw_protected) ||
1719        RootToken.is(tok::kw_private))
1720      IsAccessModifier = true;
1721    else if (RootToken.is(tok::at) && !RootToken.Children.empty() &&
1722             (RootToken.Children[0].isObjCAtKeyword(tok::objc_public) ||
1723              RootToken.Children[0].isObjCAtKeyword(tok::objc_protected) ||
1724              RootToken.Children[0].isObjCAtKeyword(tok::objc_package) ||
1725              RootToken.Children[0].isObjCAtKeyword(tok::objc_private)))
1726      IsAccessModifier = true;
1727
1728    if (IsAccessModifier &&
1729        static_cast<int>(Indent) + Style.AccessModifierOffset >= 0)
1730      Indent += Style.AccessModifierOffset;
1731    if (!InPPDirective || Tok.HasUnescapedNewline) {
1732      replaceWhitespace(Tok, Newlines, Indent, Style, SourceMgr, Replaces);
1733    } else {
1734      replacePPWhitespace(Tok, Newlines, Indent, PreviousEndOfLineColumn, Style,
1735                          SourceMgr, Replaces);
1736    }
1737    return Indent;
1738  }
1739
1740  DiagnosticsEngine &Diag;
1741  FormatStyle Style;
1742  Lexer &Lex;
1743  SourceManager &SourceMgr;
1744  tooling::Replacements Replaces;
1745  std::vector<CharSourceRange> Ranges;
1746  std::vector<AnnotatedLine> AnnotatedLines;
1747  bool StructuralError;
1748};
1749
1750tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
1751                               SourceManager &SourceMgr,
1752                               std::vector<CharSourceRange> Ranges,
1753                               DiagnosticConsumer *DiagClient) {
1754  IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts = new DiagnosticOptions();
1755  OwningPtr<DiagnosticConsumer> DiagPrinter;
1756  if (DiagClient == 0) {
1757    DiagPrinter.reset(new TextDiagnosticPrinter(llvm::errs(), &*DiagOpts));
1758    DiagPrinter->BeginSourceFile(Lex.getLangOpts(), Lex.getPP());
1759    DiagClient = DiagPrinter.get();
1760  }
1761  DiagnosticsEngine Diagnostics(
1762      IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs()), &*DiagOpts,
1763      DiagClient, false);
1764  Diagnostics.setSourceManager(&SourceMgr);
1765  Formatter formatter(Diagnostics, Style, Lex, SourceMgr, Ranges);
1766  return formatter.format();
1767}
1768
1769LangOptions getFormattingLangOpts() {
1770  LangOptions LangOpts;
1771  LangOpts.CPlusPlus = 1;
1772  LangOpts.CPlusPlus11 = 1;
1773  LangOpts.Bool = 1;
1774  LangOpts.ObjC1 = 1;
1775  LangOpts.ObjC2 = 1;
1776  return LangOpts;
1777}
1778
1779} // namespace format
1780} // namespace clang
1781