TokenAnnotator.cpp revision 3ff4a2fea4aa6e5182b7799ccb4352e56961a212 
1//===--- TokenAnnotator.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 a token annotator, i.e. creates
12/// \c AnnotatedTokens out of \c FormatTokens with required extra information.
13///
14//===----------------------------------------------------------------------===//
15
16#include "TokenAnnotator.h"
17#include "clang/Basic/SourceManager.h"
18#include "clang/Lex/Lexer.h"
19#include "llvm/Support/Debug.h"
20
21namespace clang {
22namespace format {
23
24bool AnnotatedToken::isUnaryOperator() const {
25  switch (FormatTok->Tok.getKind()) {
26  case tok::plus:
27  case tok::plusplus:
28  case tok::minus:
29  case tok::minusminus:
30  case tok::exclaim:
31  case tok::tilde:
32  case tok::kw_sizeof:
33  case tok::kw_alignof:
34    return true;
35  default:
36    return false;
37  }
38}
39
40bool AnnotatedToken::isBinaryOperator() const {
41  // Comma is a binary operator, but does not behave as such wrt. formatting.
42  return getPrecedence(*this) > prec::Comma;
43}
44
45bool AnnotatedToken::isTrailingComment() const {
46  return is(tok::comment) &&
47         (Children.empty() || Children[0].FormatTok->NewlinesBefore > 0);
48}
49
50AnnotatedToken *AnnotatedToken::getPreviousNoneComment() const {
51  AnnotatedToken *Tok = Parent;
52  while (Tok != NULL && Tok->is(tok::comment))
53    Tok = Tok->Parent;
54  return Tok;
55}
56
57const AnnotatedToken *AnnotatedToken::getNextNoneComment() const {
58  const AnnotatedToken *Tok = Children.empty() ? NULL : &Children[0];
59  while (Tok != NULL && Tok->is(tok::comment))
60    Tok = Tok->Children.empty() ? NULL : &Tok->Children[0];
61  return Tok;
62}
63
64bool AnnotatedToken::closesScope() const {
65  return isOneOf(tok::r_paren, tok::r_brace, tok::r_square) ||
66         Type == TT_TemplateCloser;
67}
68
69bool AnnotatedToken::opensScope() const {
70  return isOneOf(tok::l_paren, tok::l_brace, tok::l_square) ||
71         Type == TT_TemplateOpener;
72}
73
74/// \brief A parser that gathers additional information about tokens.
75///
76/// The \c TokenAnnotator tries to match parenthesis and square brakets and
77/// store a parenthesis levels. It also tries to resolve matching "<" and ">"
78/// into template parameter lists.
79class AnnotatingParser {
80public:
81  AnnotatingParser(SourceManager &SourceMgr, Lexer &Lex, AnnotatedLine &Line,
82                   IdentifierInfo &Ident_in)
83      : SourceMgr(SourceMgr), Lex(Lex), Line(Line), CurrentToken(&Line.First),
84        KeywordVirtualFound(false), NameFound(false), Ident_in(Ident_in) {
85    Contexts.push_back(Context(tok::unknown, 1, /*IsExpression=*/ false));
86  }
87
88private:
89  bool parseAngle() {
90    if (CurrentToken == NULL)
91      return false;
92    ScopedContextCreator ContextCreator(*this, tok::less, 10);
93    AnnotatedToken *Left = CurrentToken->Parent;
94    Contexts.back().IsExpression = false;
95    while (CurrentToken != NULL) {
96      if (CurrentToken->is(tok::greater)) {
97        Left->MatchingParen = CurrentToken;
98        CurrentToken->MatchingParen = Left;
99        CurrentToken->Type = TT_TemplateCloser;
100        next();
101        return true;
102      }
103      if (CurrentToken->isOneOf(tok::r_paren, tok::r_square, tok::r_brace,
104                                tok::question, tok::colon))
105        return false;
106      if (CurrentToken->Parent->isOneOf(tok::pipepipe, tok::ampamp) &&
107          CurrentToken->Parent->Type != TT_PointerOrReference &&
108          Line.First.isNot(tok::kw_template))
109        return false;
110      updateParameterCount(Left, CurrentToken);
111      if (!consumeToken())
112        return false;
113    }
114    return false;
115  }
116
117  bool parseParens(bool LookForDecls = false) {
118    if (CurrentToken == NULL)
119      return false;
120    ScopedContextCreator ContextCreator(*this, tok::l_paren, 1);
121
122    // FIXME: This is a bit of a hack. Do better.
123    Contexts.back().ColonIsForRangeExpr =
124        Contexts.size() == 2 && Contexts[0].ColonIsForRangeExpr;
125
126    bool StartsObjCMethodExpr = false;
127    AnnotatedToken *Left = CurrentToken->Parent;
128    if (CurrentToken->is(tok::caret)) {
129      // ^( starts a block.
130      Left->Type = TT_ObjCBlockLParen;
131    } else if (AnnotatedToken *MaybeSel = Left->Parent) {
132      // @selector( starts a selector.
133      if (MaybeSel->isObjCAtKeyword(tok::objc_selector) && MaybeSel->Parent &&
134          MaybeSel->Parent->is(tok::at)) {
135        StartsObjCMethodExpr = true;
136      }
137    }
138
139    if (StartsObjCMethodExpr) {
140      Contexts.back().ColonIsObjCMethodExpr = true;
141      Left->Type = TT_ObjCMethodExpr;
142    }
143
144    bool MightBeFunctionType = CurrentToken->is(tok::star);
145    while (CurrentToken != NULL) {
146      // LookForDecls is set when "if (" has been seen. Check for
147      // 'identifier' '*' 'identifier' followed by not '=' -- this
148      // '*' has to be a binary operator but determineStarAmpUsage() will
149      // categorize it as an unary operator, so set the right type here.
150      if (LookForDecls && !CurrentToken->Children.empty()) {
151        AnnotatedToken &Prev = *CurrentToken->Parent;
152        AnnotatedToken &Next = CurrentToken->Children[0];
153        if (Prev.Parent->is(tok::identifier) &&
154            Prev.isOneOf(tok::star, tok::amp, tok::ampamp) &&
155            CurrentToken->is(tok::identifier) && Next.isNot(tok::equal)) {
156          Prev.Type = TT_BinaryOperator;
157          LookForDecls = false;
158        }
159      }
160
161      if (CurrentToken->is(tok::r_paren)) {
162        if (MightBeFunctionType && !CurrentToken->Children.empty() &&
163            CurrentToken->Children[0].isOneOf(tok::l_paren, tok::l_square))
164          Left->Type = TT_FunctionTypeLParen;
165        Left->MatchingParen = CurrentToken;
166        CurrentToken->MatchingParen = Left;
167
168        if (StartsObjCMethodExpr) {
169          CurrentToken->Type = TT_ObjCMethodExpr;
170          if (Contexts.back().FirstObjCSelectorName != NULL) {
171            Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName =
172                Contexts.back().LongestObjCSelectorName;
173          }
174        }
175
176        next();
177        return true;
178      }
179      if (CurrentToken->isOneOf(tok::r_square, tok::r_brace))
180        return false;
181      if (CurrentToken->Parent->Type == TT_PointerOrReference &&
182          CurrentToken->Parent->Parent->isOneOf(tok::l_paren, tok::coloncolon))
183        MightBeFunctionType = true;
184      updateParameterCount(Left, CurrentToken);
185      if (!consumeToken())
186        return false;
187    }
188    return false;
189  }
190
191  bool parseSquare() {
192    if (!CurrentToken)
193      return false;
194
195    // A '[' could be an index subscript (after an indentifier or after
196    // ')' or ']'), it could be the start of an Objective-C method
197    // expression, or it could the the start of an Objective-C array literal.
198    AnnotatedToken *Left = CurrentToken->Parent;
199    AnnotatedToken *Parent = Left->getPreviousNoneComment();
200    bool StartsObjCMethodExpr =
201        Contexts.back().CanBeExpression &&
202        (!Parent || Parent->isOneOf(tok::colon, tok::l_square, tok::l_paren,
203                                    tok::kw_return, tok::kw_throw) ||
204         Parent->isUnaryOperator() || Parent->Type == TT_ObjCForIn ||
205         Parent->Type == TT_CastRParen ||
206         getBinOpPrecedence(Parent->FormatTok->Tok.getKind(), true, true) >
207             prec::Unknown);
208    ScopedContextCreator ContextCreator(*this, tok::l_square, 10);
209    Contexts.back().IsExpression = true;
210    bool StartsObjCArrayLiteral = Parent && Parent->is(tok::at);
211
212    if (StartsObjCMethodExpr) {
213      Contexts.back().ColonIsObjCMethodExpr = true;
214      Left->Type = TT_ObjCMethodExpr;
215    } else if (StartsObjCArrayLiteral) {
216      Left->Type = TT_ObjCArrayLiteral;
217    }
218
219    while (CurrentToken != NULL) {
220      if (CurrentToken->is(tok::r_square)) {
221        if (!CurrentToken->Children.empty() &&
222            CurrentToken->Children[0].is(tok::l_paren)) {
223          // An ObjC method call is rarely followed by an open parenthesis.
224          // FIXME: Do we incorrectly label ":" with this?
225          StartsObjCMethodExpr = false;
226          Left->Type = TT_Unknown;
227        }
228        if (StartsObjCMethodExpr) {
229          CurrentToken->Type = TT_ObjCMethodExpr;
230          // determineStarAmpUsage() thinks that '*' '[' is allocating an
231          // array of pointers, but if '[' starts a selector then '*' is a
232          // binary operator.
233          if (Parent != NULL && Parent->Type == TT_PointerOrReference)
234            Parent->Type = TT_BinaryOperator;
235        } else if (StartsObjCArrayLiteral) {
236          CurrentToken->Type = TT_ObjCArrayLiteral;
237        }
238        Left->MatchingParen = CurrentToken;
239        CurrentToken->MatchingParen = Left;
240        if (Contexts.back().FirstObjCSelectorName != NULL)
241          Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName =
242              Contexts.back().LongestObjCSelectorName;
243        next();
244        return true;
245      }
246      if (CurrentToken->isOneOf(tok::r_paren, tok::r_brace))
247        return false;
248      updateParameterCount(Left, CurrentToken);
249      if (!consumeToken())
250        return false;
251    }
252    return false;
253  }
254
255  bool parseBrace() {
256    if (CurrentToken != NULL) {
257      ScopedContextCreator ContextCreator(*this, tok::l_brace, 1);
258      AnnotatedToken *Left = CurrentToken->Parent;
259
260      AnnotatedToken *Parent = Left->getPreviousNoneComment();
261      bool StartsObjCDictLiteral = Parent && Parent->is(tok::at);
262      if (StartsObjCDictLiteral) {
263        Contexts.back().ColonIsObjCDictLiteral = true;
264        Left->Type = TT_ObjCDictLiteral;
265      }
266
267      while (CurrentToken != NULL) {
268        if (CurrentToken->is(tok::r_brace)) {
269          if (StartsObjCDictLiteral)
270            CurrentToken->Type = TT_ObjCDictLiteral;
271          Left->MatchingParen = CurrentToken;
272          CurrentToken->MatchingParen = Left;
273          next();
274          return true;
275        }
276        if (CurrentToken->isOneOf(tok::r_paren, tok::r_square))
277          return false;
278        updateParameterCount(Left, CurrentToken);
279        if (!consumeToken())
280          return false;
281      }
282    }
283    // No closing "}" found, this probably starts a definition.
284    Line.StartsDefinition = true;
285    return true;
286  }
287
288  void updateParameterCount(AnnotatedToken *Left, AnnotatedToken *Current) {
289    if (Current->is(tok::comma))
290      ++Left->ParameterCount;
291    else if (Left->ParameterCount == 0 && Current->isNot(tok::comment))
292      Left->ParameterCount = 1;
293  }
294
295  bool parseConditional() {
296    while (CurrentToken != NULL) {
297      if (CurrentToken->is(tok::colon)) {
298        CurrentToken->Type = TT_ConditionalExpr;
299        next();
300        return true;
301      }
302      if (!consumeToken())
303        return false;
304    }
305    return false;
306  }
307
308  bool parseTemplateDeclaration() {
309    if (CurrentToken != NULL && CurrentToken->is(tok::less)) {
310      CurrentToken->Type = TT_TemplateOpener;
311      next();
312      if (!parseAngle())
313        return false;
314      if (CurrentToken != NULL)
315        CurrentToken->Parent->ClosesTemplateDeclaration = true;
316      return true;
317    }
318    return false;
319  }
320
321  bool consumeToken() {
322    AnnotatedToken *Tok = CurrentToken;
323    next();
324    switch (Tok->FormatTok->Tok.getKind()) {
325    case tok::plus:
326    case tok::minus:
327      if (Tok->Parent == NULL && Line.MustBeDeclaration)
328        Tok->Type = TT_ObjCMethodSpecifier;
329      break;
330    case tok::colon:
331      if (Tok->Parent == NULL)
332        return false;
333      // Colons from ?: are handled in parseConditional().
334      if (Tok->Parent->is(tok::r_paren) && Contexts.size() == 1) {
335        Tok->Type = TT_CtorInitializerColon;
336      } else if (Contexts.back().ColonIsObjCDictLiteral) {
337        Tok->Type = TT_ObjCDictLiteral;
338      } else if (Contexts.back().ColonIsObjCMethodExpr ||
339                 Line.First.Type == TT_ObjCMethodSpecifier) {
340        Tok->Type = TT_ObjCMethodExpr;
341        Tok->Parent->Type = TT_ObjCSelectorName;
342        if (Tok->Parent->FormatTok->TokenLength >
343            Contexts.back().LongestObjCSelectorName)
344          Contexts.back().LongestObjCSelectorName =
345              Tok->Parent->FormatTok->TokenLength;
346        if (Contexts.back().FirstObjCSelectorName == NULL)
347          Contexts.back().FirstObjCSelectorName = Tok->Parent;
348      } else if (Contexts.back().ColonIsForRangeExpr) {
349        Tok->Type = TT_RangeBasedForLoopColon;
350      } else if (Contexts.size() == 1) {
351        Tok->Type = TT_InheritanceColon;
352      } else if (Contexts.back().ContextKind == tok::l_paren) {
353        Tok->Type = TT_InlineASMColon;
354      }
355      break;
356    case tok::kw_if:
357    case tok::kw_while:
358      if (CurrentToken != NULL && CurrentToken->is(tok::l_paren)) {
359        next();
360        if (!parseParens(/*LookForDecls=*/ true))
361          return false;
362      }
363      break;
364    case tok::kw_for:
365      Contexts.back().ColonIsForRangeExpr = true;
366      next();
367      if (!parseParens())
368        return false;
369      break;
370    case tok::l_paren:
371      if (!parseParens())
372        return false;
373      if (Line.MustBeDeclaration && NameFound && !Contexts.back().IsExpression)
374        Line.MightBeFunctionDecl = true;
375      break;
376    case tok::l_square:
377      if (!parseSquare())
378        return false;
379      break;
380    case tok::l_brace:
381      if (!parseBrace())
382        return false;
383      break;
384    case tok::less:
385      if (parseAngle())
386        Tok->Type = TT_TemplateOpener;
387      else {
388        Tok->Type = TT_BinaryOperator;
389        CurrentToken = Tok;
390        next();
391      }
392      break;
393    case tok::r_paren:
394    case tok::r_square:
395      return false;
396    case tok::r_brace:
397      // Lines can start with '}'.
398      if (Tok->Parent != NULL)
399        return false;
400      break;
401    case tok::greater:
402      Tok->Type = TT_BinaryOperator;
403      break;
404    case tok::kw_operator:
405      while (CurrentToken && CurrentToken->isNot(tok::l_paren)) {
406        if (CurrentToken->isOneOf(tok::star, tok::amp))
407          CurrentToken->Type = TT_PointerOrReference;
408        consumeToken();
409      }
410      if (CurrentToken) {
411        CurrentToken->Type = TT_OverloadedOperatorLParen;
412        if (CurrentToken->Parent->Type == TT_BinaryOperator)
413          CurrentToken->Parent->Type = TT_OverloadedOperator;
414      }
415      break;
416    case tok::question:
417      parseConditional();
418      break;
419    case tok::kw_template:
420      parseTemplateDeclaration();
421      break;
422    case tok::identifier:
423      if (Line.First.is(tok::kw_for) &&
424          Tok->FormatTok->Tok.getIdentifierInfo() == &Ident_in)
425        Tok->Type = TT_ObjCForIn;
426      break;
427    case tok::comma:
428      if (Contexts.back().FirstStartOfName)
429        Contexts.back().FirstStartOfName->PartOfMultiVariableDeclStmt = true;
430      break;
431    default:
432      break;
433    }
434    return true;
435  }
436
437  void parseIncludeDirective() {
438    next();
439    if (CurrentToken != NULL && CurrentToken->is(tok::less)) {
440      next();
441      while (CurrentToken != NULL) {
442        if (CurrentToken->isNot(tok::comment) ||
443            !CurrentToken->Children.empty())
444          CurrentToken->Type = TT_ImplicitStringLiteral;
445        next();
446      }
447    } else {
448      while (CurrentToken != NULL) {
449        if (CurrentToken->is(tok::string_literal))
450          // Mark these string literals as "implicit" literals, too, so that
451          // they are not split or line-wrapped.
452          CurrentToken->Type = TT_ImplicitStringLiteral;
453        next();
454      }
455    }
456  }
457
458  void parseWarningOrError() {
459    next();
460    // We still want to format the whitespace left of the first token of the
461    // warning or error.
462    next();
463    while (CurrentToken != NULL) {
464      CurrentToken->Type = TT_ImplicitStringLiteral;
465      next();
466    }
467  }
468
469  void parsePreprocessorDirective() {
470    next();
471    if (CurrentToken == NULL)
472      return;
473    // Hashes in the middle of a line can lead to any strange token
474    // sequence.
475    if (CurrentToken->FormatTok->Tok.getIdentifierInfo() == NULL)
476      return;
477    switch (
478        CurrentToken->FormatTok->Tok.getIdentifierInfo()->getPPKeywordID()) {
479    case tok::pp_include:
480    case tok::pp_import:
481      parseIncludeDirective();
482      break;
483    case tok::pp_error:
484    case tok::pp_warning:
485      parseWarningOrError();
486      break;
487    case tok::pp_if:
488    case tok::pp_elif:
489      parseLine();
490      break;
491    default:
492      break;
493    }
494    while (CurrentToken != NULL)
495      next();
496  }
497
498public:
499  LineType parseLine() {
500    int PeriodsAndArrows = 0;
501    AnnotatedToken *LastPeriodOrArrow = NULL;
502    bool CanBeBuilderTypeStmt = true;
503    if (CurrentToken->is(tok::hash)) {
504      parsePreprocessorDirective();
505      return LT_PreprocessorDirective;
506    }
507    while (CurrentToken != NULL) {
508      if (CurrentToken->is(tok::kw_virtual))
509        KeywordVirtualFound = true;
510      if (CurrentToken->isOneOf(tok::period, tok::arrow)) {
511        ++PeriodsAndArrows;
512        LastPeriodOrArrow = CurrentToken;
513      }
514      AnnotatedToken *TheToken = CurrentToken;
515      if (!consumeToken())
516        return LT_Invalid;
517      if (getPrecedence(*TheToken) > prec::Assignment &&
518          TheToken->Type == TT_BinaryOperator)
519        CanBeBuilderTypeStmt = false;
520    }
521    if (KeywordVirtualFound)
522      return LT_VirtualFunctionDecl;
523
524    // Assume a builder-type call if there are 2 or more "." and "->".
525    if (PeriodsAndArrows >= 2 && CanBeBuilderTypeStmt) {
526      LastPeriodOrArrow->LastInChainOfCalls = true;
527      return LT_BuilderTypeCall;
528    }
529
530    if (Line.First.Type == TT_ObjCMethodSpecifier) {
531      if (Contexts.back().FirstObjCSelectorName != NULL)
532        Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName =
533            Contexts.back().LongestObjCSelectorName;
534      return LT_ObjCMethodDecl;
535    }
536
537    return LT_Other;
538  }
539
540private:
541  void next() {
542    if (CurrentToken != NULL) {
543      determineTokenType(*CurrentToken);
544      CurrentToken->BindingStrength = Contexts.back().BindingStrength;
545    }
546
547    if (CurrentToken != NULL && !CurrentToken->Children.empty())
548      CurrentToken = &CurrentToken->Children[0];
549    else
550      CurrentToken = NULL;
551
552    // Reset token type in case we have already looked at it and then recovered
553    // from an error (e.g. failure to find the matching >).
554    if (CurrentToken != NULL)
555      CurrentToken->Type = TT_Unknown;
556  }
557
558  /// \brief A struct to hold information valid in a specific context, e.g.
559  /// a pair of parenthesis.
560  struct Context {
561    Context(tok::TokenKind ContextKind, unsigned BindingStrength,
562            bool IsExpression)
563        : ContextKind(ContextKind), BindingStrength(BindingStrength),
564          LongestObjCSelectorName(0), ColonIsForRangeExpr(false),
565          ColonIsObjCDictLiteral(false), ColonIsObjCMethodExpr(false),
566          FirstObjCSelectorName(NULL), FirstStartOfName(NULL),
567          IsExpression(IsExpression), CanBeExpression(true) {}
568
569    tok::TokenKind ContextKind;
570    unsigned BindingStrength;
571    unsigned LongestObjCSelectorName;
572    bool ColonIsForRangeExpr;
573    bool ColonIsObjCDictLiteral;
574    bool ColonIsObjCMethodExpr;
575    AnnotatedToken *FirstObjCSelectorName;
576    AnnotatedToken *FirstStartOfName;
577    bool IsExpression;
578    bool CanBeExpression;
579  };
580
581  /// \brief Puts a new \c Context onto the stack \c Contexts for the lifetime
582  /// of each instance.
583  struct ScopedContextCreator {
584    AnnotatingParser &P;
585
586    ScopedContextCreator(AnnotatingParser &P, tok::TokenKind ContextKind,
587                         unsigned Increase)
588        : P(P) {
589      P.Contexts.push_back(
590          Context(ContextKind, P.Contexts.back().BindingStrength + Increase,
591                  P.Contexts.back().IsExpression));
592    }
593
594    ~ScopedContextCreator() { P.Contexts.pop_back(); }
595  };
596
597  void determineTokenType(AnnotatedToken &Current) {
598    if (getPrecedence(Current) == prec::Assignment &&
599        (!Current.Parent || Current.Parent->isNot(tok::kw_operator))) {
600      Contexts.back().IsExpression = true;
601      for (AnnotatedToken *Previous = Current.Parent;
602           Previous && Previous->isNot(tok::comma);
603           Previous = Previous->Parent) {
604        if (Previous->is(tok::r_square))
605          Previous = Previous->MatchingParen;
606        if (Previous->Type == TT_BinaryOperator &&
607            Previous->isOneOf(tok::star, tok::amp)) {
608          Previous->Type = TT_PointerOrReference;
609        }
610      }
611    } else if (Current.isOneOf(tok::kw_return, tok::kw_throw) ||
612               (Current.is(tok::l_paren) && !Line.MustBeDeclaration &&
613                !Line.InPPDirective &&
614                (!Current.Parent || Current.Parent->isNot(tok::kw_for)))) {
615      Contexts.back().IsExpression = true;
616    } else if (Current.isOneOf(tok::r_paren, tok::greater, tok::comma)) {
617      for (AnnotatedToken *Previous = Current.Parent;
618           Previous && Previous->isOneOf(tok::star, tok::amp);
619           Previous = Previous->Parent)
620        Previous->Type = TT_PointerOrReference;
621    } else if (Current.Parent &&
622               Current.Parent->Type == TT_CtorInitializerColon) {
623      Contexts.back().IsExpression = true;
624    } else if (Current.is(tok::kw_new)) {
625      Contexts.back().CanBeExpression = false;
626    } else if (Current.is(tok::semi)) {
627      // This should be the condition or increment in a for-loop.
628      Contexts.back().IsExpression = true;
629    }
630
631    if (Current.Type == TT_Unknown) {
632      if (Current.Parent && Current.is(tok::identifier) &&
633          ((Current.Parent->is(tok::identifier) &&
634            Current.Parent->FormatTok->Tok.getIdentifierInfo()
635                    ->getPPKeywordID() ==
636                tok::pp_not_keyword) ||
637           isSimpleTypeSpecifier(*Current.Parent) ||
638           Current.Parent->Type == TT_PointerOrReference ||
639           Current.Parent->Type == TT_TemplateCloser)) {
640        Contexts.back().FirstStartOfName = &Current;
641        Current.Type = TT_StartOfName;
642        NameFound = true;
643      } else if (Current.isOneOf(tok::star, tok::amp, tok::ampamp)) {
644        Current.Type =
645            determineStarAmpUsage(Current, Contexts.back().IsExpression);
646      } else if (Current.isOneOf(tok::minus, tok::plus, tok::caret)) {
647        Current.Type = determinePlusMinusCaretUsage(Current);
648      } else if (Current.isOneOf(tok::minusminus, tok::plusplus)) {
649        Current.Type = determineIncrementUsage(Current);
650      } else if (Current.is(tok::exclaim)) {
651        Current.Type = TT_UnaryOperator;
652      } else if (Current.isBinaryOperator()) {
653        Current.Type = TT_BinaryOperator;
654      } else if (Current.is(tok::comment)) {
655        std::string Data(Lexer::getSpelling(Current.FormatTok->Tok, SourceMgr,
656                                            Lex.getLangOpts()));
657        if (StringRef(Data).startswith("//"))
658          Current.Type = TT_LineComment;
659        else
660          Current.Type = TT_BlockComment;
661      } else if (Current.is(tok::r_paren)) {
662        bool ParensNotExpr =
663            !Current.Parent || Current.Parent->Type == TT_PointerOrReference ||
664            Current.Parent->Type == TT_TemplateCloser;
665        bool ParensCouldEndDecl =
666            !Current.Children.empty() &&
667            Current.Children[0].isOneOf(tok::equal, tok::semi, tok::l_brace);
668        bool IsSizeOfOrAlignOf =
669            Current.MatchingParen && Current.MatchingParen->Parent &&
670            Current.MatchingParen->Parent->isOneOf(tok::kw_sizeof,
671                                                   tok::kw_alignof);
672        if (ParensNotExpr && !ParensCouldEndDecl && !IsSizeOfOrAlignOf &&
673            Contexts.back().IsExpression)
674          // FIXME: We need to get smarter and understand more cases of casts.
675          Current.Type = TT_CastRParen;
676      } else if (Current.is(tok::at) && Current.Children.size()) {
677        switch (Current.Children[0].FormatTok->Tok.getObjCKeywordID()) {
678        case tok::objc_interface:
679        case tok::objc_implementation:
680        case tok::objc_protocol:
681          Current.Type = TT_ObjCDecl;
682          break;
683        case tok::objc_property:
684          Current.Type = TT_ObjCProperty;
685          break;
686        default:
687          break;
688        }
689      } else if (Current.is(tok::period)) {
690        AnnotatedToken *PreviousNoComment= Current.getPreviousNoneComment();
691        if (PreviousNoComment &&
692            PreviousNoComment->isOneOf(tok::comma, tok::l_brace))
693          Current.Type = TT_DesignatedInitializerPeriod;
694      }
695    }
696  }
697
698  /// \brief Return the type of the given token assuming it is * or &.
699  TokenType determineStarAmpUsage(const AnnotatedToken &Tok,
700                                  bool IsExpression) {
701    const AnnotatedToken *PrevToken = Tok.getPreviousNoneComment();
702    if (PrevToken == NULL)
703      return TT_UnaryOperator;
704
705    const AnnotatedToken *NextToken = Tok.getNextNoneComment();
706    if (NextToken == NULL)
707      return TT_Unknown;
708
709    if (PrevToken->is(tok::coloncolon) ||
710        (PrevToken->is(tok::l_paren) && !IsExpression))
711      return TT_PointerOrReference;
712
713    if (PrevToken->isOneOf(tok::l_paren, tok::l_square, tok::l_brace,
714                           tok::comma, tok::semi, tok::kw_return, tok::colon,
715                           tok::equal, tok::kw_delete) ||
716        PrevToken->Type == TT_BinaryOperator ||
717        PrevToken->Type == TT_UnaryOperator || PrevToken->Type == TT_CastRParen)
718      return TT_UnaryOperator;
719
720    if (NextToken->is(tok::l_square))
721      return TT_PointerOrReference;
722
723    if (PrevToken->FormatTok->Tok.isLiteral() ||
724        PrevToken->isOneOf(tok::r_paren, tok::r_square) ||
725        NextToken->FormatTok->Tok.isLiteral() || NextToken->isUnaryOperator())
726      return TT_BinaryOperator;
727
728    // It is very unlikely that we are going to find a pointer or reference type
729    // definition on the RHS of an assignment.
730    if (IsExpression)
731      return TT_BinaryOperator;
732
733    return TT_PointerOrReference;
734  }
735
736  TokenType determinePlusMinusCaretUsage(const AnnotatedToken &Tok) {
737    const AnnotatedToken *PrevToken = Tok.getPreviousNoneComment();
738    if (PrevToken == NULL)
739      return TT_UnaryOperator;
740
741    // Use heuristics to recognize unary operators.
742    if (PrevToken->isOneOf(tok::equal, tok::l_paren, tok::comma, tok::l_square,
743                           tok::question, tok::colon, tok::kw_return,
744                           tok::kw_case, tok::at, tok::l_brace))
745      return TT_UnaryOperator;
746
747    // There can't be two consecutive binary operators.
748    if (PrevToken->Type == TT_BinaryOperator)
749      return TT_UnaryOperator;
750
751    // Fall back to marking the token as binary operator.
752    return TT_BinaryOperator;
753  }
754
755  /// \brief Determine whether ++/-- are pre- or post-increments/-decrements.
756  TokenType determineIncrementUsage(const AnnotatedToken &Tok) {
757    const AnnotatedToken *PrevToken = Tok.getPreviousNoneComment();
758    if (PrevToken == NULL)
759      return TT_UnaryOperator;
760    if (PrevToken->isOneOf(tok::r_paren, tok::r_square, tok::identifier))
761      return TT_TrailingUnaryOperator;
762
763    return TT_UnaryOperator;
764  }
765
766  // FIXME: This is copy&pasted from Sema. Put it in a common place and remove
767  // duplication.
768  /// \brief Determine whether the token kind starts a simple-type-specifier.
769  bool isSimpleTypeSpecifier(const AnnotatedToken &Tok) const {
770    switch (Tok.FormatTok->Tok.getKind()) {
771    case tok::kw_short:
772    case tok::kw_long:
773    case tok::kw___int64:
774    case tok::kw___int128:
775    case tok::kw_signed:
776    case tok::kw_unsigned:
777    case tok::kw_void:
778    case tok::kw_char:
779    case tok::kw_int:
780    case tok::kw_half:
781    case tok::kw_float:
782    case tok::kw_double:
783    case tok::kw_wchar_t:
784    case tok::kw_bool:
785    case tok::kw___underlying_type:
786      return true;
787    case tok::annot_typename:
788    case tok::kw_char16_t:
789    case tok::kw_char32_t:
790    case tok::kw_typeof:
791    case tok::kw_decltype:
792      return Lex.getLangOpts().CPlusPlus;
793    default:
794      break;
795    }
796    return false;
797  }
798
799  SmallVector<Context, 8> Contexts;
800
801  SourceManager &SourceMgr;
802  Lexer &Lex;
803  AnnotatedLine &Line;
804  AnnotatedToken *CurrentToken;
805  bool KeywordVirtualFound;
806  bool NameFound;
807  IdentifierInfo &Ident_in;
808};
809
810/// \brief Parses binary expressions by inserting fake parenthesis based on
811/// operator precedence.
812class ExpressionParser {
813public:
814  ExpressionParser(AnnotatedLine &Line) : Current(&Line.First) {}
815
816  /// \brief Parse expressions with the given operatore precedence.
817  void parse(int Precedence = 0) {
818    if (Precedence > prec::PointerToMember || Current == NULL)
819      return;
820
821    // Eagerly consume trailing comments.
822    while (Current && Current->isTrailingComment()) {
823      next();
824    }
825
826    AnnotatedToken *Start = Current;
827    bool OperatorFound = false;
828
829    while (Current) {
830      // Consume operators with higher precedence.
831      parse(Precedence + 1);
832
833      int CurrentPrecedence = 0;
834      if (Current) {
835        if (Current->Type == TT_ConditionalExpr)
836          CurrentPrecedence = 1 + (int) prec::Conditional;
837        else if (Current->is(tok::semi) || Current->Type == TT_InlineASMColon)
838          CurrentPrecedence = 1;
839        else if (Current->Type == TT_BinaryOperator || Current->is(tok::comma))
840          CurrentPrecedence = 1 + (int) getPrecedence(*Current);
841      }
842
843      // At the end of the line or when an operator with higher precedence is
844      // found, insert fake parenthesis and return.
845      if (Current == NULL || Current->closesScope() ||
846          (CurrentPrecedence != 0 && CurrentPrecedence < Precedence)) {
847        if (OperatorFound) {
848          Start->FakeLParens.push_back(prec::Level(Precedence - 1));
849          if (Current)
850            ++Current->Parent->FakeRParens;
851        }
852        return;
853      }
854
855      // Consume scopes: (), [], <> and {}
856      if (Current->opensScope()) {
857        while (Current && !Current->closesScope()) {
858          next();
859          parse();
860        }
861        next();
862      } else {
863        // Operator found.
864        if (CurrentPrecedence == Precedence)
865          OperatorFound = true;
866
867        next();
868      }
869    }
870  }
871
872private:
873  void next() {
874    if (Current != NULL)
875      Current = Current->Children.empty() ? NULL : &Current->Children[0];
876  }
877
878  AnnotatedToken *Current;
879};
880
881void TokenAnnotator::annotate(AnnotatedLine &Line) {
882  AnnotatingParser Parser(SourceMgr, Lex, Line, Ident_in);
883  Line.Type = Parser.parseLine();
884  if (Line.Type == LT_Invalid)
885    return;
886
887  ExpressionParser ExprParser(Line);
888  ExprParser.parse();
889
890  if (Line.First.Type == TT_ObjCMethodSpecifier)
891    Line.Type = LT_ObjCMethodDecl;
892  else if (Line.First.Type == TT_ObjCDecl)
893    Line.Type = LT_ObjCDecl;
894  else if (Line.First.Type == TT_ObjCProperty)
895    Line.Type = LT_ObjCProperty;
896
897  Line.First.SpacesRequiredBefore = 1;
898  Line.First.MustBreakBefore = Line.First.FormatTok->MustBreakBefore;
899  Line.First.CanBreakBefore = Line.First.MustBreakBefore;
900}
901
902void TokenAnnotator::calculateFormattingInformation(AnnotatedLine &Line) {
903  if (Line.First.Children.empty())
904    return;
905  AnnotatedToken *Current = &Line.First.Children[0];
906  while (Current != NULL) {
907    if (Current->Type == TT_LineComment)
908      Current->SpacesRequiredBefore = Style.SpacesBeforeTrailingComments;
909    else
910      Current->SpacesRequiredBefore =
911          spaceRequiredBefore(Line, *Current) ? 1 : 0;
912
913    if (Current->FormatTok->MustBreakBefore) {
914      Current->MustBreakBefore = true;
915    } else if (Current->Type == TT_LineComment) {
916      Current->MustBreakBefore = Current->FormatTok->NewlinesBefore > 0;
917    } else if (Current->Parent->isTrailingComment() ||
918               (Current->is(tok::string_literal) &&
919                Current->Parent->is(tok::string_literal))) {
920      Current->MustBreakBefore = true;
921    } else if (Current->is(tok::lessless) && !Current->Children.empty() &&
922               Current->Parent->is(tok::string_literal) &&
923               Current->Children[0].is(tok::string_literal)) {
924      Current->MustBreakBefore = true;
925    } else {
926      Current->MustBreakBefore = false;
927    }
928    Current->CanBreakBefore =
929        Current->MustBreakBefore || canBreakBefore(Line, *Current);
930    if (Current->MustBreakBefore)
931      Current->TotalLength = Current->Parent->TotalLength + Style.ColumnLimit;
932    else
933      Current->TotalLength =
934          Current->Parent->TotalLength + Current->FormatTok->TokenLength +
935          Current->SpacesRequiredBefore;
936    // FIXME: Only calculate this if CanBreakBefore is true once static
937    // initializers etc. are sorted out.
938    // FIXME: Move magic numbers to a better place.
939    Current->SplitPenalty =
940        20 * Current->BindingStrength + splitPenalty(Line, *Current);
941
942    Current = Current->Children.empty() ? NULL : &Current->Children[0];
943  }
944
945  calculateUnbreakableTailLengths(Line);
946  DEBUG({
947    printDebugInfo(Line);
948  });
949}
950
951void TokenAnnotator::calculateUnbreakableTailLengths(AnnotatedLine &Line) {
952  unsigned UnbreakableTailLength = 0;
953  AnnotatedToken *Current = Line.Last;
954  while (Current != NULL) {
955    Current->UnbreakableTailLength = UnbreakableTailLength;
956    if (Current->CanBreakBefore ||
957        Current->isOneOf(tok::comment, tok::string_literal)) {
958      UnbreakableTailLength = 0;
959    } else {
960      UnbreakableTailLength +=
961          Current->FormatTok->TokenLength + Current->SpacesRequiredBefore;
962    }
963    Current = Current->Parent;
964  }
965}
966
967unsigned TokenAnnotator::splitPenalty(const AnnotatedLine &Line,
968                                      const AnnotatedToken &Tok) {
969  const AnnotatedToken &Left = *Tok.Parent;
970  const AnnotatedToken &Right = Tok;
971
972  if (Left.is(tok::semi))
973    return 0;
974  if (Left.is(tok::comma))
975    return 1;
976
977  if (Right.Type == TT_StartOfName) {
978    if (Line.First.is(tok::kw_for) && Right.PartOfMultiVariableDeclStmt)
979      return 3;
980    else if (Line.MightBeFunctionDecl && Right.BindingStrength == 1)
981      // FIXME: Clean up hack of using BindingStrength to find top-level names.
982      return Style.PenaltyReturnTypeOnItsOwnLine;
983    else
984      return 200;
985  }
986  if (Left.is(tok::equal) && Right.is(tok::l_brace))
987    return 150;
988  if (Left.is(tok::coloncolon))
989    return 500;
990  if (Left.isOneOf(tok::kw_class, tok::kw_struct))
991    return 5000;
992
993  if (Left.Type == TT_RangeBasedForLoopColon ||
994      Left.Type == TT_InheritanceColon)
995    return 2;
996
997  if (Right.isOneOf(tok::arrow, tok::period) &&
998      Right.Type != TT_DesignatedInitializerPeriod) {
999    if (Line.Type == LT_BuilderTypeCall)
1000      return prec::PointerToMember;
1001    if (Left.isOneOf(tok::r_paren, tok::r_square) && Left.MatchingParen &&
1002        Left.MatchingParen->ParameterCount > 0)
1003      return 20; // Should be smaller than breaking at a nested comma.
1004    return 150;
1005  }
1006
1007  // Breaking before a trailing 'const' is bad.
1008  if (Left.is(tok::r_paren) && Right.is(tok::kw_const))
1009    return 150;
1010
1011  // In for-loops, prefer breaking at ',' and ';'.
1012  if (Line.First.is(tok::kw_for) && Left.is(tok::equal))
1013    return 4;
1014
1015  // In Objective-C method expressions, prefer breaking before "param:" over
1016  // breaking after it.
1017  if (Right.Type == TT_ObjCSelectorName)
1018    return 0;
1019  if (Left.is(tok::colon) && Left.Type == TT_ObjCMethodExpr)
1020    return 20;
1021
1022  if (Left.is(tok::l_paren) && Line.MightBeFunctionDecl)
1023    return 100;
1024  if (Left.opensScope())
1025    return Left.ParameterCount > 1 ? prec::Comma : 20;
1026
1027  if (Right.is(tok::lessless)) {
1028    if (Left.is(tok::string_literal)) {
1029      StringRef Content = StringRef(Left.FormatTok->Tok.getLiteralData(),
1030                                    Left.FormatTok->TokenLength);
1031      Content = Content.drop_back(1).drop_front(1).trim();
1032      if (Content.size() > 1 &&
1033          (Content.back() == ':' || Content.back() == '='))
1034        return 20;
1035    }
1036    return prec::Shift;
1037  }
1038  if (Left.Type == TT_ConditionalExpr)
1039    return prec::Conditional;
1040  prec::Level Level = getPrecedence(Left);
1041
1042  if (Level != prec::Unknown)
1043    return Level;
1044
1045  return 3;
1046}
1047
1048bool TokenAnnotator::spaceRequiredBetween(const AnnotatedLine &Line,
1049                                          const AnnotatedToken &Left,
1050                                          const AnnotatedToken &Right) {
1051  if (Right.is(tok::hashhash))
1052    return Left.is(tok::hash);
1053  if (Left.isOneOf(tok::hashhash, tok::hash))
1054    return Right.is(tok::hash);
1055  if (Right.isOneOf(tok::r_paren, tok::semi, tok::comma))
1056    return false;
1057  if (Right.is(tok::less) &&
1058      (Left.is(tok::kw_template) ||
1059       (Line.Type == LT_ObjCDecl && Style.ObjCSpaceBeforeProtocolList)))
1060    return true;
1061  if (Left.is(tok::arrow) || Right.is(tok::arrow))
1062    return false;
1063  if (Left.isOneOf(tok::exclaim, tok::tilde))
1064    return false;
1065  if (Left.is(tok::at) &&
1066      Right.isOneOf(tok::identifier, tok::string_literal, tok::char_constant,
1067                    tok::numeric_constant, tok::l_paren, tok::l_brace,
1068                    tok::kw_true, tok::kw_false))
1069    return false;
1070  if (Left.is(tok::coloncolon))
1071    return false;
1072  if (Right.is(tok::coloncolon))
1073    return !Left.isOneOf(tok::identifier, tok::greater, tok::l_paren);
1074  if (Left.is(tok::less) || Right.isOneOf(tok::greater, tok::less))
1075    return false;
1076  if (Right.Type == TT_PointerOrReference)
1077    return Left.FormatTok->Tok.isLiteral() ||
1078           ((Left.Type != TT_PointerOrReference) && Left.isNot(tok::l_paren) &&
1079            !Style.PointerBindsToType);
1080  if (Right.Type == TT_FunctionTypeLParen && Left.isNot(tok::l_paren) &&
1081      (Left.Type != TT_PointerOrReference || Style.PointerBindsToType))
1082    return true;
1083  if (Left.Type == TT_PointerOrReference)
1084    return Right.FormatTok->Tok.isLiteral() ||
1085           ((Right.Type != TT_PointerOrReference) &&
1086            Right.isNot(tok::l_paren) && Style.PointerBindsToType &&
1087            Left.Parent &&
1088            !Left.Parent->isOneOf(tok::l_paren, tok::coloncolon));
1089  if (Right.is(tok::star) && Left.is(tok::l_paren))
1090    return false;
1091  if (Left.is(tok::l_square))
1092    return Left.Type == TT_ObjCArrayLiteral && Right.isNot(tok::r_square);
1093  if (Right.is(tok::r_square))
1094    return Right.Type == TT_ObjCArrayLiteral;
1095  if (Right.is(tok::l_square) && Right.Type != TT_ObjCMethodExpr)
1096    return false;
1097  if (Left.is(tok::colon))
1098    return Left.Type != TT_ObjCMethodExpr;
1099  if (Right.is(tok::colon))
1100    return Right.Type != TT_ObjCMethodExpr;
1101  if (Left.is(tok::l_paren))
1102    return false;
1103  if (Right.is(tok::l_paren)) {
1104    return Line.Type == LT_ObjCDecl ||
1105           Left.isOneOf(tok::kw_if, tok::kw_for, tok::kw_while, tok::kw_switch,
1106                        tok::kw_return, tok::kw_catch, tok::kw_new,
1107                        tok::kw_delete, tok::semi);
1108  }
1109  if (Left.is(tok::at) &&
1110      Right.FormatTok->Tok.getObjCKeywordID() != tok::objc_not_keyword)
1111    return false;
1112  if (Left.is(tok::l_brace) && Right.is(tok::r_brace))
1113    return false; // No spaces in "{}".
1114  if (Left.is(tok::l_brace) || Right.is(tok::r_brace))
1115    return Style.SpacesInBracedLists;
1116  if (Right.Type == TT_UnaryOperator)
1117    return !Left.isOneOf(tok::l_paren, tok::l_square, tok::at) &&
1118           (Left.isNot(tok::colon) || Left.Type != TT_ObjCMethodExpr);
1119  if (Left.isOneOf(tok::identifier, tok::greater, tok::r_square) &&
1120      Right.is(tok::l_brace) && Right.getNextNoneComment())
1121    return false;
1122  if (Right.is(tok::ellipsis))
1123    return false;
1124  if (Left.is(tok::period) || Right.is(tok::period))
1125    return false;
1126  return true;
1127}
1128
1129bool TokenAnnotator::spaceRequiredBefore(const AnnotatedLine &Line,
1130                                         const AnnotatedToken &Tok) {
1131  if (Tok.FormatTok->Tok.getIdentifierInfo() &&
1132      Tok.Parent->FormatTok->Tok.getIdentifierInfo())
1133    return true; // Never ever merge two identifiers.
1134  if (Line.Type == LT_ObjCMethodDecl) {
1135    if (Tok.Parent->Type == TT_ObjCMethodSpecifier)
1136      return true;
1137    if (Tok.Parent->is(tok::r_paren) && Tok.is(tok::identifier))
1138      // Don't space between ')' and <id>
1139      return false;
1140  }
1141  if (Line.Type == LT_ObjCProperty &&
1142      (Tok.is(tok::equal) || Tok.Parent->is(tok::equal)))
1143    return false;
1144
1145  if (Tok.Parent->is(tok::comma))
1146    return true;
1147  if (Tok.is(tok::comma))
1148    return false;
1149  if (Tok.Type == TT_CtorInitializerColon || Tok.Type == TT_ObjCBlockLParen)
1150    return true;
1151  if (Tok.Parent->FormatTok->Tok.is(tok::kw_operator))
1152    return false;
1153  if (Tok.Type == TT_OverloadedOperatorLParen)
1154    return false;
1155  if (Tok.is(tok::colon))
1156    return !Line.First.isOneOf(tok::kw_case, tok::kw_default) &&
1157           Tok.getNextNoneComment() != NULL && Tok.Type != TT_ObjCMethodExpr;
1158  if (Tok.Parent->Type == TT_UnaryOperator || Tok.Parent->Type == TT_CastRParen)
1159    return false;
1160  if (Tok.Parent->is(tok::greater) && Tok.is(tok::greater)) {
1161    return Tok.Type == TT_TemplateCloser &&
1162           Tok.Parent->Type == TT_TemplateCloser &&
1163           Style.Standard != FormatStyle::LS_Cpp11;
1164  }
1165  if (Tok.isOneOf(tok::arrowstar, tok::periodstar) ||
1166      Tok.Parent->isOneOf(tok::arrowstar, tok::periodstar))
1167    return false;
1168  if (Tok.Type == TT_BinaryOperator || Tok.Parent->Type == TT_BinaryOperator)
1169    return true;
1170  if (Tok.Parent->Type == TT_TemplateCloser && Tok.is(tok::l_paren))
1171    return false;
1172  if (Tok.is(tok::less) && Line.First.is(tok::hash))
1173    return true;
1174  if (Tok.Type == TT_TrailingUnaryOperator)
1175    return false;
1176  return spaceRequiredBetween(Line, *Tok.Parent, Tok);
1177}
1178
1179bool TokenAnnotator::canBreakBefore(const AnnotatedLine &Line,
1180                                    const AnnotatedToken &Right) {
1181  const AnnotatedToken &Left = *Right.Parent;
1182  if (Right.Type == TT_StartOfName)
1183    return true;
1184  if (Right.is(tok::colon) &&
1185      (Right.Type == TT_ObjCDictLiteral || Right.Type == TT_ObjCMethodExpr))
1186    return false;
1187  if (Left.is(tok::colon) &&
1188      (Left.Type == TT_ObjCDictLiteral || Left.Type == TT_ObjCMethodExpr))
1189    return true;
1190  if (Right.Type == TT_ObjCSelectorName)
1191    return true;
1192  if (Left.ClosesTemplateDeclaration)
1193    return true;
1194  if (Right.Type == TT_ConditionalExpr || Right.is(tok::question))
1195    return true;
1196  if (Right.Type == TT_RangeBasedForLoopColon ||
1197      Right.Type == TT_OverloadedOperatorLParen)
1198    return false;
1199  if (Left.Type == TT_RangeBasedForLoopColon)
1200    return true;
1201  if (Right.Type == TT_RangeBasedForLoopColon)
1202    return false;
1203  if (Left.Type == TT_PointerOrReference || Left.Type == TT_TemplateCloser ||
1204      Left.Type == TT_UnaryOperator || Left.Type == TT_ConditionalExpr ||
1205      Left.isOneOf(tok::question, tok::kw_operator))
1206    return false;
1207  if (Left.is(tok::equal) && Line.Type == LT_VirtualFunctionDecl)
1208    return false;
1209  if (Left.is(tok::l_paren) && Right.is(tok::l_paren) && Left.Parent &&
1210      Left.Parent->is(tok::kw___attribute))
1211    return false;
1212
1213  if (Right.Type == TT_LineComment)
1214    // We rely on MustBreakBefore being set correctly here as we should not
1215    // change the "binding" behavior of a comment.
1216    return false;
1217
1218  // We only break before r_brace if there was a corresponding break before
1219  // the l_brace, which is tracked by BreakBeforeClosingBrace.
1220  if (Right.isOneOf(tok::r_brace, tok::r_paren, tok::greater))
1221    return false;
1222
1223  // Allow breaking after a trailing 'const', e.g. after a method declaration,
1224  // unless it is follow by ';', '{' or '='.
1225  if (Left.is(tok::kw_const) && Left.Parent != NULL &&
1226      Left.Parent->is(tok::r_paren))
1227    return !Right.isOneOf(tok::l_brace, tok::semi, tok::equal);
1228
1229  if (Right.is(tok::kw___attribute))
1230    return true;
1231
1232  if (Left.is(tok::identifier) && Right.is(tok::string_literal))
1233    return true;
1234  return (Left.isBinaryOperator() && Left.isNot(tok::lessless)) ||
1235         Left.isOneOf(tok::comma, tok::coloncolon, tok::semi, tok::l_brace,
1236                      tok::kw_class, tok::kw_struct) ||
1237         Right.isOneOf(tok::lessless, tok::arrow, tok::period, tok::colon) ||
1238         (Left.is(tok::r_paren) && Left.Type != TT_CastRParen &&
1239          Right.isOneOf(tok::identifier, tok::kw_const, tok::kw___attribute)) ||
1240         (Left.is(tok::l_paren) && !Right.is(tok::r_paren)) ||
1241         (Left.is(tok::l_square) && !Right.is(tok::r_square));
1242}
1243
1244void TokenAnnotator::printDebugInfo(const AnnotatedLine &Line) {
1245  llvm::errs() << "AnnotatedTokens:\n";
1246  const AnnotatedToken *Tok = &Line.First;
1247  while (Tok) {
1248    llvm::errs()
1249        << " M=" << Tok->MustBreakBefore << " C=" << Tok->CanBreakBefore
1250        << " T=" << Tok->Type << " S=" << Tok->SpacesRequiredBefore
1251        << " P=" << Tok->SplitPenalty
1252        << " Name=" << Tok->FormatTok->Tok.getName() << " FakeLParens=";
1253    for (unsigned i = 0, e = Tok->FakeLParens.size(); i != e; ++i)
1254      llvm::errs() << Tok->FakeLParens[i] << "/";
1255    llvm::errs() << " FakeRParens=" << Tok->FakeRParens << "\n";
1256    Tok = Tok->Children.empty() ? NULL : &Tok->Children[0];
1257  }
1258  llvm::errs() << "----\n";
1259}
1260
1261} // namespace format
1262} // namespace clang
1263