Format.cpp revision bac016bd3f67ca2f4db1ddc619e611759352b84d 
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#include "clang/Format/Format.h"
20
21#include "clang/Basic/SourceManager.h"
22#include "clang/Lex/Lexer.h"
23
24#include "UnwrappedLineParser.h"
25
26namespace clang {
27namespace format {
28
29// FIXME: Move somewhere sane.
30struct TokenAnnotation {
31  enum TokenType { TT_Unknown, TT_TemplateOpener, TT_BinaryOperator,
32      TT_UnaryOperator, TT_OverloadedOperator, TT_PointerOrReference,
33      TT_ConditionalExpr, TT_LineComment, TT_BlockComment };
34
35  TokenType Type;
36
37  /// \brief The current parenthesis level, i.e. the number of opening minus
38  /// the number of closing parenthesis left of the current position.
39  unsigned ParenLevel;
40
41  bool SpaceRequiredBefore;
42  bool CanBreakBefore;
43  bool MustBreakBefore;
44};
45
46using llvm::MutableArrayRef;
47
48FormatStyle getLLVMStyle() {
49  FormatStyle LLVMStyle;
50  LLVMStyle.ColumnLimit = 80;
51  LLVMStyle.MaxEmptyLinesToKeep = 1;
52  LLVMStyle.PointerAndReferenceBindToType = false;
53  LLVMStyle.AccessModifierOffset = -2;
54  LLVMStyle.SplitTemplateClosingGreater = true;
55  return LLVMStyle;
56}
57
58FormatStyle getGoogleStyle() {
59  FormatStyle GoogleStyle;
60  GoogleStyle.ColumnLimit = 80;
61  GoogleStyle.MaxEmptyLinesToKeep = 1;
62  GoogleStyle.PointerAndReferenceBindToType = true;
63  GoogleStyle.AccessModifierOffset = -1;
64  GoogleStyle.SplitTemplateClosingGreater = false;
65  return GoogleStyle;
66}
67
68struct OptimizationParameters {
69  unsigned PenaltyExtraLine;
70  unsigned PenaltyIndentLevel;
71};
72
73class UnwrappedLineFormatter {
74public:
75  UnwrappedLineFormatter(const FormatStyle &Style, SourceManager &SourceMgr,
76                         const UnwrappedLine &Line,
77                         const std::vector<TokenAnnotation> &Annotations,
78                         tooling::Replacements &Replaces)
79      : Style(Style),
80        SourceMgr(SourceMgr),
81        Line(Line),
82        Annotations(Annotations),
83        Replaces(Replaces) {
84    Parameters.PenaltyExtraLine = 100;
85    Parameters.PenaltyIndentLevel = 5;
86  }
87
88  void format() {
89    formatFirstToken();
90    count = 0;
91    IndentState State;
92    State.Column = Line.Level * 2 + Line.Tokens[0].Tok.getLength();
93    State.CtorInitializerOnNewLine = false;
94    State.InCtorInitializer = false;
95    State.ConsumedTokens = 1;
96
97    //State.UsedIndent.push_back(Line.Level * 2);
98    State.Indent.push_back(Line.Level * 2 + 4);
99    State.LastSpace.push_back(Line.Level * 2);
100
101    // Start iterating at 1 as we have correctly formatted of Token #0 above.
102    for (unsigned i = 1, n = Line.Tokens.size(); i != n; ++i) {
103      unsigned NoBreak = calcPenalty(State, false, UINT_MAX);
104      unsigned Break = calcPenalty(State, true, NoBreak);
105      addToken(Break < NoBreak, false, State);
106    }
107  }
108
109private:
110  /// \brief The current state when indenting a unwrapped line.
111  ///
112  /// As the indenting tries different combinations this is copied by value.
113  struct IndentState {
114    /// \brief The number of used columns in the current line.
115    unsigned Column;
116
117    /// \brief The number of tokens already consumed.
118    unsigned ConsumedTokens;
119
120    /// \brief The position to which a specific parenthesis level needs to be
121    /// indented.
122    std::vector<unsigned> Indent;
123
124    std::vector<unsigned> LastSpace;
125
126    bool CtorInitializerOnNewLine;
127    bool InCtorInitializer;
128
129    /// \brief Comparison operator to be able to used \c IndentState in \c map.
130    bool operator<(const IndentState &Other) const {
131      if (Other.ConsumedTokens != ConsumedTokens)
132        return Other.ConsumedTokens > ConsumedTokens;
133      if (Other.Column != Column)
134        return Other.Column > Column;
135      if (Other.Indent.size() != Indent.size())
136        return Other.Indent.size() > Indent.size();
137      for (int i = 0, e = Indent.size(); i != e; ++i) {
138        if (Other.Indent[i] != Indent[i])
139          return Other.Indent[i] > Indent[i];
140      }
141      if (Other.LastSpace.size() != LastSpace.size())
142        return Other.LastSpace.size() > LastSpace.size();
143      for (int i = 0, e = LastSpace.size(); i != e; ++i) {
144        if (Other.LastSpace[i] != LastSpace[i])
145          return Other.LastSpace[i] > LastSpace[i];
146      }
147      return false;
148    }
149  };
150
151  /// Append the next token to \p State.
152  void addToken(bool Newline, bool DryRun, IndentState &State) {
153    unsigned Index = State.ConsumedTokens;
154    const FormatToken &Current = Line.Tokens[Index];
155    const FormatToken &Previous = Line.Tokens[Index - 1];
156    unsigned ParenLevel = Annotations[Index].ParenLevel;
157
158    if (Current.Tok.is(tok::l_paren) || Current.Tok.is(tok::l_square) ||
159        Annotations[Index].Type == TokenAnnotation::TT_TemplateOpener) {
160      State.Indent.push_back(4 + State.LastSpace.back());
161      State.LastSpace.push_back(State.LastSpace.back());
162    }
163
164    if (Newline) {
165      if (Current.Tok.is(tok::string_literal) &&
166          Previous.Tok.is(tok::string_literal))
167        State.Column = State.Column - Previous.Tok.getLength();
168      else if (Previous.Tok.is(tok::equal) && ParenLevel != 0)
169        State.Column = State.Indent[ParenLevel] + 4;
170      else
171        State.Column = State.Indent[ParenLevel];
172      if (!DryRun)
173        replaceWhitespace(Current, 1, State.Column);
174
175      State.Column += Current.Tok.getLength();
176      State.LastSpace[ParenLevel] = State.Indent[ParenLevel];
177      if (Current.Tok.is(tok::colon) &&
178          Annotations[Index].Type != TokenAnnotation::TT_ConditionalExpr) {
179        State.Indent[ParenLevel] += 2;
180        State.CtorInitializerOnNewLine = true;
181        State.InCtorInitializer = true;
182      }
183    } else {
184      unsigned Spaces = Annotations[Index].SpaceRequiredBefore ? 1 : 0;
185      if (Annotations[Index].Type == TokenAnnotation::TT_LineComment)
186        Spaces = 2;
187      if (!DryRun)
188        replaceWhitespace(Current, 0, Spaces);
189      if (Previous.Tok.is(tok::l_paren))
190        State.Indent[ParenLevel] = State.Column;
191      if (Previous.Tok.is(tok::less) &&
192          Annotations[Index - 1].Type == TokenAnnotation::TT_TemplateOpener)
193        State.Indent[ParenLevel] = State.Column;
194      if (Current.Tok.is(tok::colon)) {
195        State.Indent[ParenLevel] = State.Column + 3;
196        State.InCtorInitializer = true;
197      }
198      // Top-level spaces are exempt as that mostly leads to better results.
199      if (Spaces > 0 && ParenLevel != 0)
200        State.LastSpace[ParenLevel] = State.Column + Spaces;
201      State.Column += Current.Tok.getLength() + Spaces;
202    }
203
204    if (Current.Tok.is(tok::r_paren) || Current.Tok.is(tok::r_square) ||
205        Annotations[Index].Type == TokenAnnotation::TT_TemplateOpener) {
206      State.Indent.pop_back();
207      State.LastSpace.pop_back();
208    }
209
210    ++State.ConsumedTokens;
211  }
212
213  typedef std::map<IndentState, unsigned> StateMap;
214  StateMap Memory;
215
216  unsigned splitPenalty(const FormatToken &Token) {
217    if (Token.Tok.is(tok::semi))
218      return 0;
219    if (Token.Tok.is(tok::comma))
220      return 1;
221    if (Token.Tok.is(tok::equal) || Token.Tok.is(tok::l_paren) ||
222        Token.Tok.is(tok::pipepipe) || Token.Tok.is(tok::ampamp))
223      return 2;
224    return 3;
225  }
226
227  /// \brief Calculate the number of lines needed to format the remaining part
228  /// of the unwrapped line.
229  ///
230  /// Assumes the formatting so far has led to
231  /// the \c IndentState \p State. If \p NewLine is set, a new line will be
232  /// added after the previous token.
233  ///
234  /// \param StopAt is used for optimization. If we can determine that we'll
235  /// definitely need at least \p StopAt additional lines, we already know of a
236  /// better solution.
237  unsigned calcPenalty(IndentState State, bool NewLine, unsigned StopAt) {
238    // We are at the end of the unwrapped line, so we don't need any more lines.
239    if (State.ConsumedTokens >= Line.Tokens.size())
240      return 0;
241
242    if (!NewLine && Annotations[State.ConsumedTokens].MustBreakBefore)
243      return UINT_MAX;
244    if (NewLine && !Annotations[State.ConsumedTokens].CanBreakBefore)
245      return UINT_MAX;
246
247    if (State.ConsumedTokens > 0 && !NewLine &&
248        State.CtorInitializerOnNewLine &&
249        Line.Tokens[State.ConsumedTokens - 1].Tok.is(tok::comma))
250      return UINT_MAX;
251
252    if (NewLine && State.InCtorInitializer && !State.CtorInitializerOnNewLine)
253      return UINT_MAX;
254
255    addToken(NewLine, true, State);
256
257    // Exceeding column limit is bad.
258    if (State.Column > Style.ColumnLimit)
259      return UINT_MAX;
260
261    unsigned CurrentPenalty = 0;
262    if (NewLine) {
263      CurrentPenalty += Parameters.PenaltyIndentLevel *
264          Annotations[State.ConsumedTokens - 1].ParenLevel +
265          Parameters.PenaltyExtraLine +
266          splitPenalty(Line.Tokens[State.ConsumedTokens - 2]);
267    }
268
269    if (StopAt <= CurrentPenalty)
270      return UINT_MAX;
271    StopAt -= CurrentPenalty;
272
273    // Has this state already been examined?
274    StateMap::iterator I = Memory.find(State);
275    if (I != Memory.end())
276      return I->second;
277    ++count;
278
279    unsigned NoBreak = calcPenalty(State, false, StopAt);
280    unsigned WithBreak = calcPenalty(State, true, std::min(StopAt, NoBreak));
281    unsigned Result = std::min(NoBreak, WithBreak);
282    if (Result != UINT_MAX)
283      Result += CurrentPenalty;
284    Memory[State] = Result;
285    assert(Memory.find(State) != Memory.end());
286    return Result;
287  }
288
289  /// \brief Replaces the whitespace in front of \p Tok. Only call once for
290  /// each \c FormatToken.
291  void replaceWhitespace(const FormatToken &Tok, unsigned NewLines,
292                         unsigned Spaces) {
293    Replaces.insert(tooling::Replacement(
294        SourceMgr, Tok.WhiteSpaceStart, Tok.WhiteSpaceLength,
295        std::string(NewLines, '\n') + std::string(Spaces, ' ')));
296  }
297
298  /// \brief Add a new line and the required indent before the first Token
299  /// of the \c UnwrappedLine.
300  void formatFirstToken() {
301    const FormatToken &Token = Line.Tokens[0];
302    if (Token.WhiteSpaceStart.isValid()) {
303      unsigned Newlines =
304          std::min(Token.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
305      unsigned Offset = SourceMgr.getFileOffset(Token.WhiteSpaceStart);
306      if (Newlines == 0 && Offset != 0)
307        Newlines = 1;
308      unsigned Indent = Line.Level * 2;
309      if (Token.Tok.is(tok::kw_public) || Token.Tok.is(tok::kw_protected) ||
310          Token.Tok.is(tok::kw_private))
311        Indent += Style.AccessModifierOffset;
312      replaceWhitespace(Token, Newlines, Indent);
313    }
314  }
315
316  FormatStyle Style;
317  SourceManager &SourceMgr;
318  const UnwrappedLine &Line;
319  const std::vector<TokenAnnotation> &Annotations;
320  tooling::Replacements &Replaces;
321  unsigned int count;
322
323  OptimizationParameters Parameters;
324};
325
326/// \brief Determines extra information about the tokens comprising an
327/// \c UnwrappedLine.
328class TokenAnnotator {
329public:
330  TokenAnnotator(const UnwrappedLine &Line, const FormatStyle &Style,
331                 SourceManager &SourceMgr)
332      : Line(Line),
333        Style(Style),
334        SourceMgr(SourceMgr) {
335  }
336
337  /// \brief A parser that gathers additional information about tokens.
338  ///
339  /// The \c TokenAnnotator tries to matches parenthesis and square brakets and
340  /// store a parenthesis levels. It also tries to resolve matching "<" and ">"
341  /// into template parameter lists.
342  class AnnotatingParser {
343  public:
344    AnnotatingParser(const SourceManager &SourceMgr,
345                     const SmallVector<FormatToken, 16> &Tokens,
346                     std::vector<TokenAnnotation> &Annotations)
347        : SourceMgr(SourceMgr),
348          Tokens(Tokens),
349          Annotations(Annotations),
350          Index(0) {
351    }
352
353    bool parseAngle(unsigned Level) {
354      while (Index < Tokens.size()) {
355        if (Tokens[Index].Tok.is(tok::greater)) {
356          Annotations[Index].Type = TokenAnnotation::TT_TemplateOpener;
357          Annotations[Index].ParenLevel = Level;
358          next();
359          return true;
360        }
361        if (Tokens[Index].Tok.is(tok::r_paren) ||
362            Tokens[Index].Tok.is(tok::r_square))
363          return false;
364        if (Tokens[Index].Tok.is(tok::pipepipe) ||
365            Tokens[Index].Tok.is(tok::ampamp) ||
366            Tokens[Index].Tok.is(tok::question) ||
367            Tokens[Index].Tok.is(tok::colon))
368          return false;
369        consumeToken(Level);
370      }
371      return false;
372    }
373
374    bool parseParens(unsigned Level) {
375      while (Index < Tokens.size()) {
376        if (Tokens[Index].Tok.is(tok::r_paren)) {
377          Annotations[Index].ParenLevel = Level;
378          next();
379          return true;
380        }
381        if (Tokens[Index].Tok.is(tok::r_square))
382          return false;
383        consumeToken(Level);
384      }
385      return false;
386    }
387
388    bool parseSquare(unsigned Level) {
389      while (Index < Tokens.size()) {
390        if (Tokens[Index].Tok.is(tok::r_square)) {
391          Annotations[Index].ParenLevel = Level;
392          next();
393          return true;
394        }
395        if (Tokens[Index].Tok.is(tok::r_paren))
396          return false;
397        consumeToken(Level);
398      }
399      return false;
400    }
401
402    bool parseConditional(unsigned Level) {
403      while (Index < Tokens.size()) {
404        if (Tokens[Index].Tok.is(tok::colon)) {
405          Annotations[Index].Type = TokenAnnotation::TT_ConditionalExpr;
406          next();
407          return true;
408        }
409        consumeToken(Level);
410      }
411      return false;
412    }
413
414    void consumeToken(unsigned Level) {
415      Annotations[Index].ParenLevel = Level;
416      unsigned CurrentIndex = Index;
417      next();
418      switch (Tokens[CurrentIndex].Tok.getKind()) {
419      case tok::l_paren:
420        parseParens(Level + 1);
421        break;
422      case tok::l_square:
423        parseSquare(Level + 1);
424        break;
425      case tok::less:
426        if (parseAngle(Level + 1))
427          Annotations[CurrentIndex].Type = TokenAnnotation::TT_TemplateOpener;
428        else {
429          Annotations[CurrentIndex].Type = TokenAnnotation::TT_BinaryOperator;
430          Index = CurrentIndex + 1;
431        }
432        break;
433      case tok::greater:
434        Annotations[CurrentIndex].Type = TokenAnnotation::TT_BinaryOperator;
435        break;
436      case tok::kw_operator:
437        if (!Tokens[Index].Tok.is(tok::l_paren))
438          Annotations[Index].Type = TokenAnnotation::TT_OverloadedOperator;
439        next();
440        break;
441      case tok::question:
442        parseConditional(Level);
443        break;
444      default:
445        break;
446      }
447    }
448
449    void parseLine() {
450      while (Index < Tokens.size()) {
451        consumeToken(0);
452      }
453    }
454
455    void next() {
456      ++Index;
457    }
458
459  private:
460    const SourceManager &SourceMgr;
461    const SmallVector<FormatToken, 16> &Tokens;
462    std::vector<TokenAnnotation> &Annotations;
463    unsigned Index;
464  };
465
466  void annotate() {
467    Annotations.clear();
468    for (int i = 0, e = Line.Tokens.size(); i != e; ++i) {
469      Annotations.push_back(TokenAnnotation());
470    }
471
472    AnnotatingParser Parser(SourceMgr, Line.Tokens, Annotations);
473    Parser.parseLine();
474
475    determineTokenTypes();
476
477    for (int i = 1, e = Line.Tokens.size(); i != e; ++i) {
478      TokenAnnotation &Annotation = Annotations[i];
479
480      Annotation.CanBreakBefore =
481          canBreakBetween(Line.Tokens[i - 1], Line.Tokens[i]);
482
483      if (Line.Tokens[i].Tok.is(tok::colon)) {
484        if (Line.Tokens[0].Tok.is(tok::kw_case) || i == e - 1) {
485          Annotation.SpaceRequiredBefore = false;
486        } else {
487          Annotation.SpaceRequiredBefore = TokenAnnotation::TT_ConditionalExpr;
488        }
489      } else if (Annotations[i - 1].Type == TokenAnnotation::TT_UnaryOperator) {
490        Annotation.SpaceRequiredBefore = false;
491      } else if (Annotation.Type == TokenAnnotation::TT_UnaryOperator) {
492        Annotation.SpaceRequiredBefore =
493            Line.Tokens[i - 1].Tok.isNot(tok::l_paren);
494      } else if (Line.Tokens[i - 1].Tok.is(tok::greater) &&
495                 Line.Tokens[i].Tok.is(tok::greater)) {
496        if (Annotation.Type == TokenAnnotation::TT_TemplateOpener &&
497            Annotations[i - 1].Type == TokenAnnotation::TT_TemplateOpener)
498          Annotation.SpaceRequiredBefore = Style.SplitTemplateClosingGreater;
499        else
500          Annotation.SpaceRequiredBefore = false;
501      } else if (
502          Annotation.Type == TokenAnnotation::TT_BinaryOperator ||
503          Annotations[i - 1].Type == TokenAnnotation::TT_BinaryOperator) {
504        Annotation.SpaceRequiredBefore = true;
505      } else if (
506          Annotations[i - 1].Type == TokenAnnotation::TT_TemplateOpener &&
507          Line.Tokens[i].Tok.is(tok::l_paren)) {
508        Annotation.SpaceRequiredBefore = false;
509      } else {
510        Annotation.SpaceRequiredBefore =
511            spaceRequiredBetween(Line.Tokens[i - 1].Tok, Line.Tokens[i].Tok);
512      }
513
514      if (Annotations[i - 1].Type == TokenAnnotation::TT_LineComment ||
515          (Line.Tokens[i].Tok.is(tok::string_literal) &&
516           Line.Tokens[i - 1].Tok.is(tok::string_literal))) {
517        Annotation.MustBreakBefore = true;
518      }
519
520      if (Annotation.MustBreakBefore)
521        Annotation.CanBreakBefore = true;
522    }
523  }
524
525  const std::vector<TokenAnnotation> &getAnnotations() {
526    return Annotations;
527  }
528
529private:
530  void determineTokenTypes() {
531    for (int i = 0, e = Line.Tokens.size(); i != e; ++i) {
532      TokenAnnotation &Annotation = Annotations[i];
533      const FormatToken &Tok = Line.Tokens[i];
534
535      if (Tok.Tok.is(tok::star) || Tok.Tok.is(tok::amp))
536        Annotation.Type = determineStarAmpUsage(i);
537      else if (Tok.Tok.is(tok::minus) && Line.Tokens[i - 1].Tok.is(tok::equal))
538        Annotation.Type = TokenAnnotation::TT_UnaryOperator;
539      else if (isBinaryOperator(Line.Tokens[i]))
540        Annotation.Type = TokenAnnotation::TT_BinaryOperator;
541      else if (Tok.Tok.is(tok::comment)) {
542        StringRef Data(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
543                       Tok.Tok.getLength());
544        if (Data.startswith("//"))
545          Annotation.Type = TokenAnnotation::TT_LineComment;
546        else
547          Annotation.Type = TokenAnnotation::TT_BlockComment;
548      }
549    }
550  }
551
552  bool isBinaryOperator(const FormatToken &Tok) {
553    switch (Tok.Tok.getKind()) {
554    case tok::equal:
555    case tok::equalequal:
556    case tok::star:
557      //case tok::amp:
558    case tok::plus:
559    case tok::slash:
560    case tok::minus:
561    case tok::ampamp:
562    case tok::pipe:
563    case tok::pipepipe:
564    case tok::percent:
565      return true;
566    default:
567      return false;
568    }
569  }
570
571  TokenAnnotation::TokenType determineStarAmpUsage(unsigned Index) {
572    if (Index == Annotations.size())
573      return TokenAnnotation::TT_Unknown;
574
575    if (Index == 0 || Line.Tokens[Index - 1].Tok.is(tok::l_paren) ||
576        Line.Tokens[Index - 1].Tok.is(tok::comma) ||
577        Annotations[Index - 1].Type == TokenAnnotation::TT_BinaryOperator)
578      return TokenAnnotation::TT_UnaryOperator;
579
580    if (Line.Tokens[Index - 1].Tok.isLiteral() ||
581        Line.Tokens[Index + 1].Tok.isLiteral())
582      return TokenAnnotation::TT_BinaryOperator;
583
584    return TokenAnnotation::TT_PointerOrReference;
585  }
586
587  bool isIfForOrWhile(Token Tok) {
588    return Tok.is(tok::kw_if) || Tok.is(tok::kw_for) || Tok.is(tok::kw_while);
589  }
590
591  bool spaceRequiredBetween(Token Left, Token Right) {
592    if (Left.is(tok::kw_template) && Right.is(tok::less))
593      return true;
594    if (Left.is(tok::arrow) || Right.is(tok::arrow))
595      return false;
596    if (Left.is(tok::exclaim) || Left.is(tok::tilde))
597      return false;
598    if (Left.is(tok::less) || Right.is(tok::greater) || Right.is(tok::less))
599      return false;
600    if (Left.is(tok::amp) || Left.is(tok::star))
601      return Right.isLiteral() || Style.PointerAndReferenceBindToType;
602    if (Right.is(tok::star) && Left.is(tok::l_paren))
603      return false;
604    if (Right.is(tok::amp) || Right.is(tok::star))
605      return Left.isLiteral() || !Style.PointerAndReferenceBindToType;
606    if (Left.is(tok::l_square) || Right.is(tok::l_square) ||
607        Right.is(tok::r_square))
608      return false;
609    if (Left.is(tok::coloncolon) || Right.is(tok::coloncolon))
610      return false;
611    if (Left.is(tok::period) || Right.is(tok::period))
612      return false;
613    if (Left.is(tok::colon) || Right.is(tok::colon))
614      return true;
615    if ((Left.is(tok::plusplus) && Right.isAnyIdentifier()) ||
616        (Left.isAnyIdentifier() && Right.is(tok::plusplus)) ||
617        (Left.is(tok::minusminus) && Right.isAnyIdentifier()) ||
618        (Left.isAnyIdentifier() && Right.is(tok::minusminus)))
619      return false;
620    if (Left.is(tok::l_paren))
621      return false;
622    if (Left.is(tok::hash))
623      return false;
624    if (Right.is(tok::r_paren) || Right.is(tok::semi) || Right.is(tok::comma))
625      return false;
626    if (Right.is(tok::l_paren)) {
627      return !Left.isAnyIdentifier() || isIfForOrWhile(Left);
628    }
629    return true;
630  }
631
632  bool canBreakBetween(const FormatToken &Left, const FormatToken &Right) {
633    if (Right.Tok.is(tok::r_paren))
634      return false;
635    if (isBinaryOperator(Left))
636      return true;
637    return Right.Tok.is(tok::colon) || Left.Tok.is(tok::comma) || Left.Tok.is(
638        tok::semi) || Left.Tok.is(tok::equal) || Left.Tok.is(tok::ampamp) ||
639        (Left.Tok.is(tok::l_paren) && !Right.Tok.is(tok::r_paren));
640  }
641
642  const UnwrappedLine &Line;
643  FormatStyle Style;
644  SourceManager &SourceMgr;
645  std::vector<TokenAnnotation> Annotations;
646};
647
648class Formatter : public UnwrappedLineConsumer {
649public:
650  Formatter(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr,
651            const std::vector<CharSourceRange> &Ranges)
652      : Style(Style),
653        Lex(Lex),
654        SourceMgr(SourceMgr),
655        Ranges(Ranges) {
656  }
657
658  tooling::Replacements format() {
659    UnwrappedLineParser Parser(Lex, SourceMgr, *this);
660    Parser.parse();
661    return Replaces;
662  }
663
664private:
665  virtual void formatUnwrappedLine(const UnwrappedLine &TheLine) {
666    if (TheLine.Tokens.size() == 0)
667      return;
668
669    CharSourceRange LineRange =
670        CharSourceRange::getTokenRange(TheLine.Tokens.front().Tok.getLocation(),
671                                       TheLine.Tokens.back().Tok.getLocation());
672
673    for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
674      if (SourceMgr.isBeforeInTranslationUnit(LineRange.getEnd(),
675                                              Ranges[i].getBegin()) ||
676          SourceMgr.isBeforeInTranslationUnit(Ranges[i].getEnd(),
677                                              LineRange.getBegin()))
678        continue;
679
680      TokenAnnotator Annotator(TheLine, Style, SourceMgr);
681      Annotator.annotate();
682      UnwrappedLineFormatter Formatter(Style, SourceMgr, TheLine,
683                                       Annotator.getAnnotations(), Replaces);
684      Formatter.format();
685      return;
686    }
687  }
688
689  FormatStyle Style;
690  Lexer &Lex;
691  SourceManager &SourceMgr;
692  tooling::Replacements Replaces;
693  std::vector<CharSourceRange> Ranges;
694};
695
696tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
697                               SourceManager &SourceMgr,
698                               std::vector<CharSourceRange> Ranges) {
699  Formatter formatter(Style, Lex, SourceMgr, Ranges);
700  return formatter.format();
701}
702
703}  // namespace format
704}  // namespace clang
705