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