granicus.if.org Git - clang/blob - lib/Format/TokenAnnotator.cpp

   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/ADT/SmallPtrSet.h"
  19 #include "llvm/Support/Debug.h"
  20
  21 #define DEBUG_TYPE "format-token-annotator"
  22
  23 namespace clang {
  24 namespace format {
  25
  26 namespace {
  27
  28 /// \brief A parser that gathers additional information about tokens.
  29 ///
  30 /// The \c TokenAnnotator tries to match parenthesis and square brakets and
  31 /// store a parenthesis levels. It also tries to resolve matching "<" and ">"
  32 /// into template parameter lists.
  33 class AnnotatingParser {
  34 public:
  35   AnnotatingParser(const FormatStyle &Style, AnnotatedLine &Line,
  36                    const AdditionalKeywords &Keywords)
  37       : Style(Style), Line(Line), CurrentToken(Line.First), AutoFound(false),
  38         Keywords(Keywords) {
  39     Contexts.push_back(Context(tok::unknown, 1, /*IsExpression=*/false));
  40     resetTokenMetadata(CurrentToken);
  41   }
  42
  43 private:
  44   bool parseAngle() {
  45     if (!CurrentToken)
  46       return false;
  47     FormatToken *Left = CurrentToken->Previous;
  48     Left->ParentBracket = Contexts.back().ContextKind;
  49     ScopedContextCreator ContextCreator(*this, tok::less, 10);
  50
  51     // If this angle is in the context of an expression, we need to be more
  52     // hesitant to detect it as opening template parameters.
  53     bool InExprContext = Contexts.back().IsExpression;
  54
  55     Contexts.back().IsExpression = false;
  56     // If there's a template keyword before the opening angle bracket, this is a
  57     // template parameter, not an argument.
  58     Contexts.back().InTemplateArgument =
  59         Left->Previous && Left->Previous->Tok.isNot(tok::kw_template);
  60
  61     if (Style.Language == FormatStyle::LK_Java &&
  62         CurrentToken->is(tok::question))
  63       next();
  64
  65     while (CurrentToken) {
  66       if (CurrentToken->is(tok::greater)) {
  67         Left->MatchingParen = CurrentToken;
  68         CurrentToken->MatchingParen = Left;
  69         CurrentToken->Type = TT_TemplateCloser;
  70         next();
  71         return true;
  72       }
  73       if (CurrentToken->is(tok::question) &&
  74           Style.Language == FormatStyle::LK_Java) {
  75         next();
  76         continue;
  77       }
  78       if (CurrentToken->isOneOf(tok::r_paren, tok::r_square, tok::r_brace) ||
  79           (CurrentToken->isOneOf(tok::colon, tok::question) && InExprContext))
  80         return false;
  81       // If a && or || is found and interpreted as a binary operator, this set
  82       // of angles is likely part of something like "a < b && c > d". If the
  83       // angles are inside an expression, the ||/&& might also be a binary
  84       // operator that was misinterpreted because we are parsing template
  85       // parameters.
  86       // FIXME: This is getting out of hand, write a decent parser.
  87       if (CurrentToken->Previous->isOneOf(tok::pipepipe, tok::ampamp) &&
  88           CurrentToken->Previous->is(TT_BinaryOperator) &&
  89           Contexts[Contexts.size() - 2].IsExpression &&
  90           !Line.startsWith(tok::kw_template))
  91         return false;
  92       updateParameterCount(Left, CurrentToken);
  93       if (!consumeToken())
  94         return false;
  95     }
  96     return false;
  97   }
  98
  99   bool parseParens(bool LookForDecls = false) {
 100     if (!CurrentToken)
 101       return false;
 102     FormatToken *Left = CurrentToken->Previous;
 103     Left->ParentBracket = Contexts.back().ContextKind;
 104     ScopedContextCreator ContextCreator(*this, tok::l_paren, 1);
 105
 106     // FIXME: This is a bit of a hack. Do better.
 107     Contexts.back().ColonIsForRangeExpr =
 108         Contexts.size() == 2 && Contexts[0].ColonIsForRangeExpr;
 109
 110     bool StartsObjCMethodExpr = false;
 111     if (CurrentToken->is(tok::caret)) {
 112       // (^ can start a block type.
 113       Left->Type = TT_ObjCBlockLParen;
 114     } else if (FormatToken *MaybeSel = Left->Previous) {
 115       // @selector( starts a selector.
 116       if (MaybeSel->isObjCAtKeyword(tok::objc_selector) && MaybeSel->Previous &&
 117           MaybeSel->Previous->is(tok::at)) {
 118         StartsObjCMethodExpr = true;
 119       }
 120     }
 121
 122     if (Left->Previous &&
 123         (Left->Previous->isOneOf(tok::kw_static_assert, tok::kw_decltype,
 124                                  tok::kw_if, tok::kw_while, tok::l_paren,
 125                                  tok::comma) ||
 126          Left->Previous->is(TT_BinaryOperator))) {
 127       // static_assert, if and while usually contain expressions.
 128       Contexts.back().IsExpression = true;
 129     } else if (Left->Previous && Left->Previous->is(tok::r_square) &&
 130                Left->Previous->MatchingParen &&
 131                Left->Previous->MatchingParen->is(TT_LambdaLSquare)) {
 132       // This is a parameter list of a lambda expression.
 133       Contexts.back().IsExpression = false;
 134     } else if (Line.InPPDirective &&
 135                (!Left->Previous ||
 136                 !Left->Previous->isOneOf(tok::identifier,
 137                                          TT_OverloadedOperator))) {
 138       Contexts.back().IsExpression = true;
 139     } else if (Contexts[Contexts.size() - 2].CaretFound) {
 140       // This is the parameter list of an ObjC block.
 141       Contexts.back().IsExpression = false;
 142     } else if (Left->Previous && Left->Previous->is(tok::kw___attribute)) {
 143       Left->Type = TT_AttributeParen;
 144     } else if (Left->Previous && Left->Previous->is(TT_ForEachMacro)) {
 145       // The first argument to a foreach macro is a declaration.
 146       Contexts.back().IsForEachMacro = true;
 147       Contexts.back().IsExpression = false;
 148     } else if (Left->Previous && Left->Previous->MatchingParen &&
 149                Left->Previous->MatchingParen->is(TT_ObjCBlockLParen)) {
 150       Contexts.back().IsExpression = false;
 151     }
 152
 153     if (StartsObjCMethodExpr) {
 154       Contexts.back().ColonIsObjCMethodExpr = true;
 155       Left->Type = TT_ObjCMethodExpr;
 156     }
 157
 158     bool MightBeFunctionType = CurrentToken->isOneOf(tok::star, tok::amp);
 159     bool HasMultipleLines = false;
 160     bool HasMultipleParametersOnALine = false;
 161     bool MightBeObjCForRangeLoop =
 162         Left->Previous && Left->Previous->is(tok::kw_for);
 163     while (CurrentToken) {
 164       // LookForDecls is set when "if (" has been seen. Check for
 165       // 'identifier' '*' 'identifier' followed by not '=' -- this
 166       // '*' has to be a binary operator but determineStarAmpUsage() will
 167       // categorize it as an unary operator, so set the right type here.
 168       if (LookForDecls && CurrentToken->Next) {
 169         FormatToken *Prev = CurrentToken->getPreviousNonComment();
 170         if (Prev) {
 171           FormatToken *PrevPrev = Prev->getPreviousNonComment();
 172           FormatToken *Next = CurrentToken->Next;
 173           if (PrevPrev && PrevPrev->is(tok::identifier) &&
 174               Prev->isOneOf(tok::star, tok::amp, tok::ampamp) &&
 175               CurrentToken->is(tok::identifier) && Next->isNot(tok::equal)) {
 176             Prev->Type = TT_BinaryOperator;
 177             LookForDecls = false;
 178           }
 179         }
 180       }
 181
 182       if (CurrentToken->Previous->is(TT_PointerOrReference) &&
 183           CurrentToken->Previous->Previous->isOneOf(tok::l_paren,
 184                                                     tok::coloncolon))
 185         MightBeFunctionType = true;
 186       if (CurrentToken->Previous->is(TT_BinaryOperator))
 187         Contexts.back().IsExpression = true;
 188       if (CurrentToken->is(tok::r_paren)) {
 189         if (MightBeFunctionType && CurrentToken->Next &&
 190             (CurrentToken->Next->is(tok::l_paren) ||
 191              (CurrentToken->Next->is(tok::l_square) &&
 192               !Contexts.back().IsExpression)))
 193           Left->Type = TT_FunctionTypeLParen;
 194         Left->MatchingParen = CurrentToken;
 195         CurrentToken->MatchingParen = Left;
 196
 197         if (StartsObjCMethodExpr) {
 198           CurrentToken->Type = TT_ObjCMethodExpr;
 199           if (Contexts.back().FirstObjCSelectorName) {
 200             Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName =
 201                 Contexts.back().LongestObjCSelectorName;
 202           }
 203         }
 204
 205         if (Left->is(TT_AttributeParen))
 206           CurrentToken->Type = TT_AttributeParen;
 207         if (Left->Previous && Left->Previous->is(TT_JavaAnnotation))
 208           CurrentToken->Type = TT_JavaAnnotation;
 209         if (Left->Previous && Left->Previous->is(TT_LeadingJavaAnnotation))
 210           CurrentToken->Type = TT_LeadingJavaAnnotation;
 211
 212         if (!HasMultipleLines)
 213           Left->PackingKind = PPK_Inconclusive;
 214         else if (HasMultipleParametersOnALine)
 215           Left->PackingKind = PPK_BinPacked;
 216         else
 217           Left->PackingKind = PPK_OnePerLine;
 218
 219         next();
 220         return true;
 221       }
 222       if (CurrentToken->isOneOf(tok::r_square, tok::r_brace))
 223         return false;
 224
 225       if (CurrentToken->is(tok::l_brace))
 226         Left->Type = TT_Unknown; // Not TT_ObjCBlockLParen
 227       if (CurrentToken->is(tok::comma) && CurrentToken->Next &&
 228           !CurrentToken->Next->HasUnescapedNewline &&
 229           !CurrentToken->Next->isTrailingComment())
 230         HasMultipleParametersOnALine = true;
 231       if (CurrentToken->isOneOf(tok::kw_const, tok::kw_auto) ||
 232           CurrentToken->isSimpleTypeSpecifier())
 233         Contexts.back().IsExpression = false;
 234       if (CurrentToken->isOneOf(tok::semi, tok::colon))
 235         MightBeObjCForRangeLoop = false;
 236       if (MightBeObjCForRangeLoop && CurrentToken->is(Keywords.kw_in))
 237         CurrentToken->Type = TT_ObjCForIn;
 238       // When we discover a 'new', we set CanBeExpression to 'false' in order to
 239       // parse the type correctly. Reset that after a comma.
 240       if (CurrentToken->is(tok::comma))
 241         Contexts.back().CanBeExpression = true;
 242
 243       FormatToken *Tok = CurrentToken;
 244       if (!consumeToken())
 245         return false;
 246       updateParameterCount(Left, Tok);
 247       if (CurrentToken && CurrentToken->HasUnescapedNewline)
 248         HasMultipleLines = true;
 249     }
 250     return false;
 251   }
 252
 253   bool parseSquare() {
 254     if (!CurrentToken)
 255       return false;
 256
 257     // A '[' could be an index subscript (after an identifier or after
 258     // ')' or ']'), it could be the start of an Objective-C method
 259     // expression, or it could the start of an Objective-C array literal.
 260     FormatToken *Left = CurrentToken->Previous;
 261     Left->ParentBracket = Contexts.back().ContextKind;
 262     FormatToken *Parent = Left->getPreviousNonComment();
 263     bool StartsObjCMethodExpr =
 264         Style.Language == FormatStyle::LK_Cpp &&
 265         Contexts.back().CanBeExpression && Left->isNot(TT_LambdaLSquare) &&
 266         CurrentToken->isNot(tok::l_brace) &&
 267         (!Parent ||
 268          Parent->isOneOf(tok::colon, tok::l_square, tok::l_paren,
 269                          tok::kw_return, tok::kw_throw) ||
 270          Parent->isUnaryOperator() ||
 271          Parent->isOneOf(TT_ObjCForIn, TT_CastRParen) ||
 272          getBinOpPrecedence(Parent->Tok.getKind(), true, true) > prec::Unknown);
 273     bool ColonFound = false;
 274
 275     unsigned BindingIncrease = 1;
 276     if (Left->is(TT_Unknown)) {
 277       if (StartsObjCMethodExpr) {
 278         Left->Type = TT_ObjCMethodExpr;
 279       } else if (Style.Language == FormatStyle::LK_JavaScript && Parent &&
 280                  Contexts.back().ContextKind == tok::l_brace &&
 281                  Parent->isOneOf(tok::l_brace, tok::comma)) {
 282         Left->Type = TT_JsComputedPropertyName;
 283       } else if (Parent &&
 284                  Parent->isOneOf(tok::at, tok::equal, tok::comma, tok::l_paren,
 285                                  tok::l_square, tok::question, tok::colon,
 286                                  tok::kw_return)) {
 287         Left->Type = TT_ArrayInitializerLSquare;
 288       } else {
 289         BindingIncrease = 10;
 290         Left->Type = TT_ArraySubscriptLSquare;
 291       }
 292     }
 293
 294     ScopedContextCreator ContextCreator(*this, tok::l_square, BindingIncrease);
 295     Contexts.back().IsExpression = true;
 296     Contexts.back().ColonIsObjCMethodExpr = StartsObjCMethodExpr;
 297
 298     while (CurrentToken) {
 299       if (CurrentToken->is(tok::r_square)) {
 300         if (CurrentToken->Next && CurrentToken->Next->is(tok::l_paren) &&
 301             Left->is(TT_ObjCMethodExpr)) {
 302           // An ObjC method call is rarely followed by an open parenthesis.
 303           // FIXME: Do we incorrectly label ":" with this?
 304           StartsObjCMethodExpr = false;
 305           Left->Type = TT_Unknown;
 306         }
 307         if (StartsObjCMethodExpr && CurrentToken->Previous != Left) {
 308           CurrentToken->Type = TT_ObjCMethodExpr;
 309           // determineStarAmpUsage() thinks that '*' '[' is allocating an
 310           // array of pointers, but if '[' starts a selector then '*' is a
 311           // binary operator.
 312           if (Parent && Parent->is(TT_PointerOrReference))
 313             Parent->Type = TT_BinaryOperator;
 314         }
 315         Left->MatchingParen = CurrentToken;
 316         CurrentToken->MatchingParen = Left;
 317         if (Contexts.back().FirstObjCSelectorName) {
 318           Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName =
 319               Contexts.back().LongestObjCSelectorName;
 320           if (Left->BlockParameterCount > 1)
 321             Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName = 0;
 322         }
 323         next();
 324         return true;
 325       }
 326       if (CurrentToken->isOneOf(tok::r_paren, tok::r_brace))
 327         return false;
 328       if (CurrentToken->is(tok::colon)) {
 329         if (Left->is(TT_ArraySubscriptLSquare)) {
 330           Left->Type = TT_ObjCMethodExpr;
 331           StartsObjCMethodExpr = true;
 332           Contexts.back().ColonIsObjCMethodExpr = true;
 333           if (Parent && Parent->is(tok::r_paren))
 334             Parent->Type = TT_CastRParen;
 335         }
 336         ColonFound = true;
 337       }
 338       if (CurrentToken->is(tok::comma) && Left->is(TT_ObjCMethodExpr) &&
 339           !ColonFound)
 340         Left->Type = TT_ArrayInitializerLSquare;
 341       FormatToken *Tok = CurrentToken;
 342       if (!consumeToken())
 343         return false;
 344       updateParameterCount(Left, Tok);
 345     }
 346     return false;
 347   }
 348
 349   bool parseBrace() {
 350     if (CurrentToken) {
 351       FormatToken *Left = CurrentToken->Previous;
 352       Left->ParentBracket = Contexts.back().ContextKind;
 353
 354       if (Contexts.back().CaretFound)
 355         Left->Type = TT_ObjCBlockLBrace;
 356       Contexts.back().CaretFound = false;
 357
 358       ScopedContextCreator ContextCreator(*this, tok::l_brace, 1);
 359       Contexts.back().ColonIsDictLiteral = true;
 360       if (Left->BlockKind == BK_BracedInit)
 361         Contexts.back().IsExpression = true;
 362
 363       while (CurrentToken) {
 364         if (CurrentToken->is(tok::r_brace)) {
 365           Left->MatchingParen = CurrentToken;
 366           CurrentToken->MatchingParen = Left;
 367           next();
 368           return true;
 369         }
 370         if (CurrentToken->isOneOf(tok::r_paren, tok::r_square))
 371           return false;
 372         updateParameterCount(Left, CurrentToken);
 373         if (CurrentToken->isOneOf(tok::colon, tok::l_brace)) {
 374           FormatToken *Previous = CurrentToken->getPreviousNonComment();
 375           if (((CurrentToken->is(tok::colon) &&
 376                 (!Contexts.back().ColonIsDictLiteral ||
 377                  Style.Language != FormatStyle::LK_Cpp)) ||
 378                Style.Language == FormatStyle::LK_Proto) &&
 379               Previous->Tok.getIdentifierInfo())
 380             Previous->Type = TT_SelectorName;
 381           if (CurrentToken->is(tok::colon) ||
 382               Style.Language == FormatStyle::LK_JavaScript)
 383             Left->Type = TT_DictLiteral;
 384         }
 385         if (!consumeToken())
 386           return false;
 387       }
 388     }
 389     return true;
 390   }
 391
 392   void updateParameterCount(FormatToken *Left, FormatToken *Current) {
 393     if (Current->is(TT_LambdaLSquare) ||
 394         (Current->is(tok::caret) && Current->is(TT_UnaryOperator)) ||
 395         (Style.Language == FormatStyle::LK_JavaScript &&
 396          Current->is(Keywords.kw_function))) {
 397       ++Left->BlockParameterCount;
 398     }
 399     if (Current->is(tok::comma)) {
 400       ++Left->ParameterCount;
 401       if (!Left->Role)
 402         Left->Role.reset(new CommaSeparatedList(Style));
 403       Left->Role->CommaFound(Current);
 404     } else if (Left->ParameterCount == 0 && Current->isNot(tok::comment)) {
 405       Left->ParameterCount = 1;
 406     }
 407   }
 408
 409   bool parseConditional() {
 410     while (CurrentToken) {
 411       if (CurrentToken->is(tok::colon)) {
 412         CurrentToken->Type = TT_ConditionalExpr;
 413         next();
 414         return true;
 415       }
 416       if (!consumeToken())
 417         return false;
 418     }
 419     return false;
 420   }
 421
 422   bool parseTemplateDeclaration() {
 423     if (CurrentToken && CurrentToken->is(tok::less)) {
 424       CurrentToken->Type = TT_TemplateOpener;
 425       next();
 426       if (!parseAngle())
 427         return false;
 428       if (CurrentToken)
 429         CurrentToken->Previous->ClosesTemplateDeclaration = true;
 430       return true;
 431     }
 432     return false;
 433   }
 434
 435   bool consumeToken() {
 436     FormatToken *Tok = CurrentToken;
 437     next();
 438     switch (Tok->Tok.getKind()) {
 439     case tok::plus:
 440     case tok::minus:
 441       if (!Tok->Previous && Line.MustBeDeclaration)
 442         Tok->Type = TT_ObjCMethodSpecifier;
 443       break;
 444     case tok::colon:
 445       if (!Tok->Previous)
 446         return false;
 447       // Colons from ?: are handled in parseConditional().
 448       if (Style.Language == FormatStyle::LK_JavaScript) {
 449         if (Contexts.back().ColonIsForRangeExpr || // colon in for loop
 450             (Contexts.size() == 1 &&               // switch/case labels
 451              !Line.First->isOneOf(tok::kw_enum, tok::kw_case)) ||
 452             Contexts.back().ContextKind == tok::l_paren ||  // function params
 453             Contexts.back().ContextKind == tok::l_square || // array type
 454             (Contexts.size() == 1 &&
 455              Line.MustBeDeclaration)) { // method/property declaration
 456           Tok->Type = TT_JsTypeColon;
 457           break;
 458         }
 459       }
 460       if (Contexts.back().ColonIsDictLiteral) {
 461         Tok->Type = TT_DictLiteral;
 462       } else if (Contexts.back().ColonIsObjCMethodExpr ||
 463                  Line.startsWith(TT_ObjCMethodSpecifier)) {
 464         Tok->Type = TT_ObjCMethodExpr;
 465         Tok->Previous->Type = TT_SelectorName;
 466         if (Tok->Previous->ColumnWidth >
 467             Contexts.back().LongestObjCSelectorName) {
 468           Contexts.back().LongestObjCSelectorName = Tok->Previous->ColumnWidth;
 469         }
 470         if (!Contexts.back().FirstObjCSelectorName)
 471           Contexts.back().FirstObjCSelectorName = Tok->Previous;
 472       } else if (Contexts.back().ColonIsForRangeExpr) {
 473         Tok->Type = TT_RangeBasedForLoopColon;
 474       } else if (CurrentToken && CurrentToken->is(tok::numeric_constant)) {
 475         Tok->Type = TT_BitFieldColon;
 476       } else if (Contexts.size() == 1 &&
 477                  !Line.First->isOneOf(tok::kw_enum, tok::kw_case)) {
 478         if (Tok->Previous->is(tok::r_paren))
 479           Tok->Type = TT_CtorInitializerColon;
 480         else
 481           Tok->Type = TT_InheritanceColon;
 482       } else if (Tok->Previous->is(tok::identifier) && Tok->Next &&
 483                  Tok->Next->isOneOf(tok::r_paren, tok::comma)) {
 484         // This handles a special macro in ObjC code where selectors including
 485         // the colon are passed as macro arguments.
 486         Tok->Type = TT_ObjCMethodExpr;
 487       } else if (Contexts.back().ContextKind == tok::l_paren) {
 488         Tok->Type = TT_InlineASMColon;
 489       }
 490       break;
 491     case tok::kw_if:
 492     case tok::kw_while:
 493       if (CurrentToken && CurrentToken->is(tok::l_paren)) {
 494         next();
 495         if (!parseParens(/*LookForDecls=*/true))
 496           return false;
 497       }
 498       break;
 499     case tok::kw_for:
 500       Contexts.back().ColonIsForRangeExpr = true;
 501       next();
 502       if (!parseParens())
 503         return false;
 504       break;
 505     case tok::l_paren:
 506       // When faced with 'operator()()', the kw_operator handler incorrectly
 507       // marks the first l_paren as a OverloadedOperatorLParen. Here, we make
 508       // the first two parens OverloadedOperators and the second l_paren an
 509       // OverloadedOperatorLParen.
 510       if (Tok->Previous &&
 511           Tok->Previous->is(tok::r_paren) &&
 512           Tok->Previous->MatchingParen &&
 513           Tok->Previous->MatchingParen->is(TT_OverloadedOperatorLParen)) {
 514         Tok->Previous->Type = TT_OverloadedOperator;
 515         Tok->Previous->MatchingParen->Type = TT_OverloadedOperator;
 516         Tok->Type = TT_OverloadedOperatorLParen;
 517       }
 518
 519       if (!parseParens())
 520         return false;
 521       if (Line.MustBeDeclaration && Contexts.size() == 1 &&
 522           !Contexts.back().IsExpression && !Line.startsWith(TT_ObjCProperty) &&
 523           (!Tok->Previous ||
 524            !Tok->Previous->isOneOf(tok::kw_decltype, tok::kw___attribute,
 525                                    TT_LeadingJavaAnnotation)))
 526         Line.MightBeFunctionDecl = true;
 527       break;
 528     case tok::l_square:
 529       if (!parseSquare())
 530         return false;
 531       break;
 532     case tok::l_brace:
 533       if (!parseBrace())
 534         return false;
 535       break;
 536     case tok::less:
 537       if (!NonTemplateLess.count(Tok) &&
 538           (!Tok->Previous ||
 539            (!Tok->Previous->Tok.isLiteral() &&
 540             !(Tok->Previous->is(tok::r_paren) && Contexts.size() > 1))) &&
 541           parseAngle()) {
 542         Tok->Type = TT_TemplateOpener;
 543       } else {
 544         Tok->Type = TT_BinaryOperator;
 545         NonTemplateLess.insert(Tok);
 546         CurrentToken = Tok;
 547         next();
 548       }
 549       break;
 550     case tok::r_paren:
 551     case tok::r_square:
 552       return false;
 553     case tok::r_brace:
 554       // Lines can start with '}'.
 555       if (Tok->Previous)
 556         return false;
 557       break;
 558     case tok::greater:
 559       Tok->Type = TT_BinaryOperator;
 560       break;
 561     case tok::kw_operator:
 562       while (CurrentToken &&
 563              !CurrentToken->isOneOf(tok::l_paren, tok::semi, tok::r_paren)) {
 564         if (CurrentToken->isOneOf(tok::star, tok::amp))
 565           CurrentToken->Type = TT_PointerOrReference;
 566         consumeToken();
 567         if (CurrentToken && CurrentToken->Previous->is(TT_BinaryOperator))
 568           CurrentToken->Previous->Type = TT_OverloadedOperator;
 569       }
 570       if (CurrentToken) {
 571         CurrentToken->Type = TT_OverloadedOperatorLParen;
 572         if (CurrentToken->Previous->is(TT_BinaryOperator))
 573           CurrentToken->Previous->Type = TT_OverloadedOperator;
 574       }
 575       break;
 576     case tok::question:
 577       if (Style.Language == FormatStyle::LK_JavaScript && Tok->Next &&
 578           Tok->Next->isOneOf(tok::semi, tok::comma, tok::colon, tok::r_paren,
 579                              tok::r_brace)) {
 580         // Question marks before semicolons, colons, etc. indicate optional
 581         // types (fields, parameters), e.g.
 582         //   function(x?: string, y?) {...}
 583         //   class X { y?; }
 584         Tok->Type = TT_JsTypeOptionalQuestion;
 585         break;
 586       }
 587       // Declarations cannot be conditional expressions, this can only be part
 588       // of a type declaration.
 589       if (Line.MustBeDeclaration &&
 590           Style.Language == FormatStyle::LK_JavaScript)
 591         break;
 592       parseConditional();
 593       break;
 594     case tok::kw_template:
 595       parseTemplateDeclaration();
 596       break;
 597     case tok::comma:
 598       if (Contexts.back().InCtorInitializer)
 599         Tok->Type = TT_CtorInitializerComma;
 600       else if (Contexts.back().FirstStartOfName &&
 601                (Contexts.size() == 1 || Line.startsWith(tok::kw_for))) {
 602         Contexts.back().FirstStartOfName->PartOfMultiVariableDeclStmt = true;
 603         Line.IsMultiVariableDeclStmt = true;
 604       }
 605       if (Contexts.back().IsForEachMacro)
 606         Contexts.back().IsExpression = true;
 607       break;
 608     default:
 609       break;
 610     }
 611     return true;
 612   }
 613
 614   void parseIncludeDirective() {
 615     if (CurrentToken && CurrentToken->is(tok::less)) {
 616       next();
 617       while (CurrentToken) {
 618         if (CurrentToken->isNot(tok::comment) || CurrentToken->Next)
 619           CurrentToken->Type = TT_ImplicitStringLiteral;
 620         next();
 621       }
 622     }
 623   }
 624
 625   void parseWarningOrError() {
 626     next();
 627     // We still want to format the whitespace left of the first token of the
 628     // warning or error.
 629     next();
 630     while (CurrentToken) {
 631       CurrentToken->Type = TT_ImplicitStringLiteral;
 632       next();
 633     }
 634   }
 635
 636   void parsePragma() {
 637     next(); // Consume "pragma".
 638     if (CurrentToken &&
 639         CurrentToken->isOneOf(Keywords.kw_mark, Keywords.kw_option)) {
 640       bool IsMark = CurrentToken->is(Keywords.kw_mark);
 641       next(); // Consume "mark".
 642       next(); // Consume first token (so we fix leading whitespace).
 643       while (CurrentToken) {
 644         if (IsMark || CurrentToken->Previous->is(TT_BinaryOperator))
 645           CurrentToken->Type = TT_ImplicitStringLiteral;
 646         next();
 647       }
 648     }
 649   }
 650
 651   LineType parsePreprocessorDirective() {
 652     LineType Type = LT_PreprocessorDirective;
 653     next();
 654     if (!CurrentToken)
 655       return Type;
 656     if (CurrentToken->Tok.is(tok::numeric_constant)) {
 657       CurrentToken->SpacesRequiredBefore = 1;
 658       return Type;
 659     }
 660     // Hashes in the middle of a line can lead to any strange token
 661     // sequence.
 662     if (!CurrentToken->Tok.getIdentifierInfo())
 663       return Type;
 664     switch (CurrentToken->Tok.getIdentifierInfo()->getPPKeywordID()) {
 665     case tok::pp_include:
 666     case tok::pp_include_next:
 667     case tok::pp_import:
 668       next();
 669       parseIncludeDirective();
 670       Type = LT_ImportStatement;
 671       break;
 672     case tok::pp_error:
 673     case tok::pp_warning:
 674       parseWarningOrError();
 675       break;
 676     case tok::pp_pragma:
 677       parsePragma();
 678       break;
 679     case tok::pp_if:
 680     case tok::pp_elif:
 681       Contexts.back().IsExpression = true;
 682       parseLine();
 683       break;
 684     default:
 685       break;
 686     }
 687     while (CurrentToken)
 688       next();
 689     return Type;
 690   }
 691
 692 public:
 693   LineType parseLine() {
 694     NonTemplateLess.clear();
 695     if (CurrentToken->is(tok::hash))
 696       return parsePreprocessorDirective();
 697
 698     // Directly allow to 'import <string-literal>' to support protocol buffer
 699     // definitions (code.google.com/p/protobuf) or missing "#" (either way we
 700     // should not break the line).
 701     IdentifierInfo *Info = CurrentToken->Tok.getIdentifierInfo();
 702     if ((Style.Language == FormatStyle::LK_Java &&
 703          CurrentToken->is(Keywords.kw_package)) ||
 704         (Info && Info->getPPKeywordID() == tok::pp_import &&
 705          CurrentToken->Next &&
 706          CurrentToken->Next->isOneOf(tok::string_literal, tok::identifier,
 707                                      tok::kw_static))) {
 708       next();
 709       parseIncludeDirective();
 710       return LT_ImportStatement;
 711     }
 712
 713     // If this line starts and ends in '<' and '>', respectively, it is likely
 714     // part of "#define <a/b.h>".
 715     if (CurrentToken->is(tok::less) && Line.Last->is(tok::greater)) {
 716       parseIncludeDirective();
 717       return LT_ImportStatement;
 718     }
 719
 720     // In .proto files, top-level options are very similar to import statements
 721     // and should not be line-wrapped.
 722     if (Style.Language == FormatStyle::LK_Proto && Line.Level == 0 &&
 723         CurrentToken->is(Keywords.kw_option)) {
 724       next();
 725       if (CurrentToken && CurrentToken->is(tok::identifier))
 726         return LT_ImportStatement;
 727     }
 728
 729     bool KeywordVirtualFound = false;
 730     bool ImportStatement = false;
 731     while (CurrentToken) {
 732       if (CurrentToken->is(tok::kw_virtual))
 733         KeywordVirtualFound = true;
 734       if (IsImportStatement(*CurrentToken))
 735         ImportStatement = true;
 736       if (!consumeToken())
 737         return LT_Invalid;
 738     }
 739     if (KeywordVirtualFound)
 740       return LT_VirtualFunctionDecl;
 741     if (ImportStatement)
 742       return LT_ImportStatement;
 743
 744     if (Line.startsWith(TT_ObjCMethodSpecifier)) {
 745       if (Contexts.back().FirstObjCSelectorName)
 746         Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName =
 747             Contexts.back().LongestObjCSelectorName;
 748       return LT_ObjCMethodDecl;
 749     }
 750
 751     return LT_Other;
 752   }
 753
 754 private:
 755   bool IsImportStatement(const FormatToken &Tok) {
 756     // FIXME: Closure-library specific stuff should not be hard-coded but be
 757     // configurable.
 758     return Style.Language == FormatStyle::LK_JavaScript &&
 759            Tok.TokenText == "goog" && Tok.Next && Tok.Next->is(tok::period) &&
 760            Tok.Next->Next && (Tok.Next->Next->TokenText == "module" ||
 761                               Tok.Next->Next->TokenText == "require" ||
 762                               Tok.Next->Next->TokenText == "provide") &&
 763            Tok.Next->Next->Next && Tok.Next->Next->Next->is(tok::l_paren);
 764   }
 765
 766   void resetTokenMetadata(FormatToken *Token) {
 767     if (!Token)
 768       return;
 769
 770     // Reset token type in case we have already looked at it and then
 771     // recovered from an error (e.g. failure to find the matching >).
 772     if (!CurrentToken->isOneOf(TT_LambdaLSquare, TT_ForEachMacro,
 773                                TT_FunctionLBrace, TT_ImplicitStringLiteral,
 774                                TT_InlineASMBrace, TT_JsFatArrow, TT_LambdaArrow,
 775                                TT_RegexLiteral))
 776       CurrentToken->Type = TT_Unknown;
 777     CurrentToken->Role.reset();
 778     CurrentToken->MatchingParen = nullptr;
 779     CurrentToken->FakeLParens.clear();
 780     CurrentToken->FakeRParens = 0;
 781   }
 782
 783   void next() {
 784     if (CurrentToken) {
 785       CurrentToken->NestingLevel = Contexts.size() - 1;
 786       CurrentToken->BindingStrength = Contexts.back().BindingStrength;
 787       modifyContext(*CurrentToken);
 788       determineTokenType(*CurrentToken);
 789       CurrentToken = CurrentToken->Next;
 790     }
 791
 792     resetTokenMetadata(CurrentToken);
 793   }
 794
 795   /// \brief A struct to hold information valid in a specific context, e.g.
 796   /// a pair of parenthesis.
 797   struct Context {
 798     Context(tok::TokenKind ContextKind, unsigned BindingStrength,
 799             bool IsExpression)
 800         : ContextKind(ContextKind), BindingStrength(BindingStrength),
 801           IsExpression(IsExpression) {}
 802
 803     tok::TokenKind ContextKind;
 804     unsigned BindingStrength;
 805     bool IsExpression;
 806     unsigned LongestObjCSelectorName = 0;
 807     bool ColonIsForRangeExpr = false;
 808     bool ColonIsDictLiteral = false;
 809     bool ColonIsObjCMethodExpr = false;
 810     FormatToken *FirstObjCSelectorName = nullptr;
 811     FormatToken *FirstStartOfName = nullptr;
 812     bool CanBeExpression = true;
 813     bool InTemplateArgument = false;
 814     bool InCtorInitializer = false;
 815     bool CaretFound = false;
 816     bool IsForEachMacro = false;
 817   };
 818
 819   /// \brief Puts a new \c Context onto the stack \c Contexts for the lifetime
 820   /// of each instance.
 821   struct ScopedContextCreator {
 822     AnnotatingParser &P;
 823
 824     ScopedContextCreator(AnnotatingParser &P, tok::TokenKind ContextKind,
 825                          unsigned Increase)
 826         : P(P) {
 827       P.Contexts.push_back(Context(ContextKind,
 828                                    P.Contexts.back().BindingStrength + Increase,
 829                                    P.Contexts.back().IsExpression));
 830     }
 831
 832     ~ScopedContextCreator() { P.Contexts.pop_back(); }
 833   };
 834
 835   void modifyContext(const FormatToken &Current) {
 836     if (Current.getPrecedence() == prec::Assignment &&
 837         !Line.First->isOneOf(tok::kw_template, tok::kw_using) &&
 838         (!Current.Previous || Current.Previous->isNot(tok::kw_operator))) {
 839       Contexts.back().IsExpression = true;
 840       if (!Line.startsWith(TT_UnaryOperator)) {
 841         for (FormatToken *Previous = Current.Previous;
 842              Previous && Previous->Previous &&
 843              !Previous->Previous->isOneOf(tok::comma, tok::semi);
 844              Previous = Previous->Previous) {
 845           if (Previous->isOneOf(tok::r_square, tok::r_paren)) {
 846             Previous = Previous->MatchingParen;
 847             if (!Previous)
 848               break;
 849           }
 850           if (Previous->opensScope())
 851             break;
 852           if (Previous->isOneOf(TT_BinaryOperator, TT_UnaryOperator) &&
 853               Previous->isOneOf(tok::star, tok::amp, tok::ampamp) &&
 854               Previous->Previous && Previous->Previous->isNot(tok::equal))
 855             Previous->Type = TT_PointerOrReference;
 856         }
 857       }
 858     } else if (Current.is(tok::lessless) &&
 859                (!Current.Previous || !Current.Previous->is(tok::kw_operator))) {
 860       Contexts.back().IsExpression = true;
 861     } else if (Current.isOneOf(tok::kw_return, tok::kw_throw)) {
 862       Contexts.back().IsExpression = true;
 863     } else if (Current.is(TT_TrailingReturnArrow)) {
 864       Contexts.back().IsExpression = false;
 865     } else if (Current.is(TT_LambdaArrow) || Current.is(Keywords.kw_assert)) {
 866       Contexts.back().IsExpression = Style.Language == FormatStyle::LK_Java;
 867     } else if (Current.is(tok::l_paren) && !Line.MustBeDeclaration &&
 868                !Line.InPPDirective &&
 869                (!Current.Previous ||
 870                 Current.Previous->isNot(tok::kw_decltype))) {
 871       bool ParametersOfFunctionType =
 872           Current.Previous && Current.Previous->is(tok::r_paren) &&
 873           Current.Previous->MatchingParen &&
 874           Current.Previous->MatchingParen->is(TT_FunctionTypeLParen);
 875       bool IsForOrCatch = Current.Previous &&
 876                           Current.Previous->isOneOf(tok::kw_for, tok::kw_catch);
 877       Contexts.back().IsExpression = !ParametersOfFunctionType && !IsForOrCatch;
 878     } else if (Current.isOneOf(tok::r_paren, tok::greater, tok::comma)) {
 879       for (FormatToken *Previous = Current.Previous;
 880            Previous && Previous->isOneOf(tok::star, tok::amp);
 881            Previous = Previous->Previous)
 882         Previous->Type = TT_PointerOrReference;
 883       if (Line.MustBeDeclaration)
 884         Contexts.back().IsExpression = Contexts.front().InCtorInitializer;
 885     } else if (Current.Previous &&
 886                Current.Previous->is(TT_CtorInitializerColon)) {
 887       Contexts.back().IsExpression = true;
 888       Contexts.back().InCtorInitializer = true;
 889     } else if (Current.is(tok::kw_new)) {
 890       Contexts.back().CanBeExpression = false;
 891     } else if (Current.isOneOf(tok::semi, tok::exclaim)) {
 892       // This should be the condition or increment in a for-loop.
 893       Contexts.back().IsExpression = true;
 894     }
 895   }
 896
 897   void determineTokenType(FormatToken &Current) {
 898     if (!Current.is(TT_Unknown))
 899       // The token type is already known.
 900       return;
 901
 902     // Line.MightBeFunctionDecl can only be true after the parentheses of a
 903     // function declaration have been found. In this case, 'Current' is a
 904     // trailing token of this declaration and thus cannot be a name.
 905     if (Current.is(Keywords.kw_instanceof)) {
 906       Current.Type = TT_BinaryOperator;
 907     } else if (isStartOfName(Current) &&
 908                (!Line.MightBeFunctionDecl || Current.NestingLevel != 0)) {
 909       Contexts.back().FirstStartOfName = &Current;
 910       Current.Type = TT_StartOfName;
 911     } else if (Current.is(tok::kw_auto)) {
 912       AutoFound = true;
 913     } else if (Current.is(tok::arrow) &&
 914                Style.Language == FormatStyle::LK_Java) {
 915       Current.Type = TT_LambdaArrow;
 916     } else if (Current.is(tok::arrow) && AutoFound && Line.MustBeDeclaration &&
 917                Current.NestingLevel == 0) {
 918       Current.Type = TT_TrailingReturnArrow;
 919     } else if (Current.isOneOf(tok::star, tok::amp, tok::ampamp)) {
 920       Current.Type =
 921           determineStarAmpUsage(Current, Contexts.back().CanBeExpression &&
 922                                              Contexts.back().IsExpression,
 923                                 Contexts.back().InTemplateArgument);
 924     } else if (Current.isOneOf(tok::minus, tok::plus, tok::caret)) {
 925       Current.Type = determinePlusMinusCaretUsage(Current);
 926       if (Current.is(TT_UnaryOperator) && Current.is(tok::caret))
 927         Contexts.back().CaretFound = true;
 928     } else if (Current.isOneOf(tok::minusminus, tok::plusplus)) {
 929       Current.Type = determineIncrementUsage(Current);
 930     } else if (Current.isOneOf(tok::exclaim, tok::tilde)) {
 931       Current.Type = TT_UnaryOperator;
 932     } else if (Current.is(tok::question)) {
 933       if (Style.Language == FormatStyle::LK_JavaScript &&
 934           Line.MustBeDeclaration) {
 935         // In JavaScript, `interface X { foo?(): bar; }` is an optional method
 936         // on the interface, not a ternary expression.
 937         Current.Type = TT_JsTypeOptionalQuestion;
 938       } else {
 939         Current.Type = TT_ConditionalExpr;
 940       }
 941     } else if (Current.isBinaryOperator() &&
 942                (!Current.Previous || Current.Previous->isNot(tok::l_square))) {
 943       Current.Type = TT_BinaryOperator;
 944     } else if (Current.is(tok::comment)) {
 945       if (Current.TokenText.startswith("/*")) {
 946         if (Current.TokenText.endswith("*/"))
 947           Current.Type = TT_BlockComment;
 948         else
 949           // The lexer has for some reason determined a comment here. But we
 950           // cannot really handle it, if it isn't properly terminated.
 951           Current.Tok.setKind(tok::unknown);
 952       } else {
 953         Current.Type = TT_LineComment;
 954       }
 955     } else if (Current.is(tok::r_paren)) {
 956       if (rParenEndsCast(Current))
 957         Current.Type = TT_CastRParen;
 958       if (Current.MatchingParen && Current.Next &&
 959           !Current.Next->isBinaryOperator() &&
 960           !Current.Next->isOneOf(tok::semi, tok::colon, tok::l_brace))
 961         if (FormatToken *BeforeParen = Current.MatchingParen->Previous)
 962           if (BeforeParen->is(tok::identifier) &&
 963               BeforeParen->TokenText == BeforeParen->TokenText.upper() &&
 964               (!BeforeParen->Previous ||
 965                BeforeParen->Previous->ClosesTemplateDeclaration))
 966             Current.Type = TT_FunctionAnnotationRParen;
 967     } else if (Current.is(tok::at) && Current.Next) {
 968       if (Current.Next->isStringLiteral()) {
 969         Current.Type = TT_ObjCStringLiteral;
 970       } else {
 971         switch (Current.Next->Tok.getObjCKeywordID()) {
 972         case tok::objc_interface:
 973         case tok::objc_implementation:
 974         case tok::objc_protocol:
 975           Current.Type = TT_ObjCDecl;
 976           break;
 977         case tok::objc_property:
 978           Current.Type = TT_ObjCProperty;
 979           break;
 980         default:
 981           break;
 982         }
 983       }
 984     } else if (Current.is(tok::period)) {
 985       FormatToken *PreviousNoComment = Current.getPreviousNonComment();
 986       if (PreviousNoComment &&
 987           PreviousNoComment->isOneOf(tok::comma, tok::l_brace))
 988         Current.Type = TT_DesignatedInitializerPeriod;
 989       else if (Style.Language == FormatStyle::LK_Java && Current.Previous &&
 990                Current.Previous->isOneOf(TT_JavaAnnotation,
 991                                          TT_LeadingJavaAnnotation)) {
 992         Current.Type = Current.Previous->Type;
 993       }
 994     } else if (Current.isOneOf(tok::identifier, tok::kw_const) &&
 995                Current.Previous &&
 996                !Current.Previous->isOneOf(tok::equal, tok::at) &&
 997                Line.MightBeFunctionDecl && Contexts.size() == 1) {
 998       // Line.MightBeFunctionDecl can only be true after the parentheses of a
 999       // function declaration have been found.
1000       Current.Type = TT_TrailingAnnotation;
1001     } else if ((Style.Language == FormatStyle::LK_Java ||
1002                 Style.Language == FormatStyle::LK_JavaScript) &&
1003                Current.Previous) {
1004       if (Current.Previous->is(tok::at) &&
1005           Current.isNot(Keywords.kw_interface)) {
1006         const FormatToken &AtToken = *Current.Previous;
1007         const FormatToken *Previous = AtToken.getPreviousNonComment();
1008         if (!Previous || Previous->is(TT_LeadingJavaAnnotation))
1009           Current.Type = TT_LeadingJavaAnnotation;
1010         else
1011           Current.Type = TT_JavaAnnotation;
1012       } else if (Current.Previous->is(tok::period) &&
1013                  Current.Previous->isOneOf(TT_JavaAnnotation,
1014                                            TT_LeadingJavaAnnotation)) {
1015         Current.Type = Current.Previous->Type;
1016       }
1017     }
1018   }
1019
1020   /// \brief Take a guess at whether \p Tok starts a name of a function or
1021   /// variable declaration.
1022   ///
1023   /// This is a heuristic based on whether \p Tok is an identifier following
1024   /// something that is likely a type.
1025   bool isStartOfName(const FormatToken &Tok) {
1026     if (Tok.isNot(tok::identifier) || !Tok.Previous)
1027       return false;
1028
1029     if (Tok.Previous->isOneOf(TT_LeadingJavaAnnotation, Keywords.kw_instanceof))
1030       return false;
1031
1032     // Skip "const" as it does not have an influence on whether this is a name.
1033     FormatToken *PreviousNotConst = Tok.Previous;
1034     while (PreviousNotConst && PreviousNotConst->is(tok::kw_const))
1035       PreviousNotConst = PreviousNotConst->Previous;
1036
1037     if (!PreviousNotConst)
1038       return false;
1039
1040     bool IsPPKeyword = PreviousNotConst->is(tok::identifier) &&
1041                        PreviousNotConst->Previous &&
1042                        PreviousNotConst->Previous->is(tok::hash);
1043
1044     if (PreviousNotConst->is(TT_TemplateCloser))
1045       return PreviousNotConst && PreviousNotConst->MatchingParen &&
1046              PreviousNotConst->MatchingParen->Previous &&
1047              PreviousNotConst->MatchingParen->Previous->isNot(tok::period) &&
1048              PreviousNotConst->MatchingParen->Previous->isNot(tok::kw_template);
1049
1050     if (PreviousNotConst->is(tok::r_paren) && PreviousNotConst->MatchingParen &&
1051         PreviousNotConst->MatchingParen->Previous &&
1052         PreviousNotConst->MatchingParen->Previous->is(tok::kw_decltype))
1053       return true;
1054
1055     return (!IsPPKeyword &&
1056             PreviousNotConst->isOneOf(tok::identifier, tok::kw_auto)) ||
1057            PreviousNotConst->is(TT_PointerOrReference) ||
1058            PreviousNotConst->isSimpleTypeSpecifier();
1059   }
1060
1061   /// \brief Determine whether ')' is ending a cast.
1062   bool rParenEndsCast(const FormatToken &Tok) {
1063     FormatToken *LeftOfParens = nullptr;
1064     if (Tok.MatchingParen)
1065       LeftOfParens = Tok.MatchingParen->getPreviousNonComment();
1066     if (LeftOfParens && LeftOfParens->is(tok::r_paren) &&
1067         LeftOfParens->MatchingParen)
1068       LeftOfParens = LeftOfParens->MatchingParen->Previous;
1069     if (LeftOfParens && LeftOfParens->is(tok::r_square) &&
1070         LeftOfParens->MatchingParen &&
1071         LeftOfParens->MatchingParen->is(TT_LambdaLSquare))
1072       return false;
1073     if (Tok.Next) {
1074       if (Tok.Next->is(tok::question))
1075         return false;
1076       if (Style.Language == FormatStyle::LK_JavaScript &&
1077           Tok.Next->is(Keywords.kw_in))
1078         return false;
1079       if (Style.Language == FormatStyle::LK_Java && Tok.Next->is(tok::l_paren))
1080         return true;
1081     }
1082     bool IsCast = false;
1083     bool ParensAreEmpty = Tok.Previous == Tok.MatchingParen;
1084     bool ParensAreType =
1085         !Tok.Previous ||
1086         Tok.Previous->isOneOf(TT_PointerOrReference, TT_TemplateCloser) ||
1087         Tok.Previous->isSimpleTypeSpecifier();
1088     bool ParensCouldEndDecl =
1089         Tok.Next &&
1090         Tok.Next->isOneOf(tok::equal, tok::semi, tok::l_brace, tok::greater);
1091     bool IsSizeOfOrAlignOf =
1092         LeftOfParens && LeftOfParens->isOneOf(tok::kw_sizeof, tok::kw_alignof);
1093     if (ParensAreType && !ParensCouldEndDecl && !IsSizeOfOrAlignOf &&
1094         (Contexts.size() > 1 && Contexts[Contexts.size() - 2].IsExpression))
1095       IsCast = true;
1096     else if (Tok.Next && Tok.Next->isNot(tok::string_literal) &&
1097              (Tok.Next->Tok.isLiteral() ||
1098               Tok.Next->isOneOf(tok::kw_sizeof, tok::kw_alignof)))
1099       IsCast = true;
1100     // If there is an identifier after the (), it is likely a cast, unless
1101     // there is also an identifier before the ().
1102     else if (LeftOfParens && Tok.Next &&
1103              (LeftOfParens->Tok.getIdentifierInfo() == nullptr ||
1104               LeftOfParens->isOneOf(tok::kw_return, tok::kw_case)) &&
1105              !LeftOfParens->isOneOf(TT_OverloadedOperator, tok::at,
1106                                     TT_TemplateCloser)) {
1107       if (Tok.Next->isOneOf(tok::identifier, tok::numeric_constant)) {
1108         IsCast = true;
1109       } else {
1110         // Use heuristics to recognize c style casting.
1111         FormatToken *Prev = Tok.Previous;
1112         if (Prev && Prev->isOneOf(tok::amp, tok::star))
1113           Prev = Prev->Previous;
1114
1115         if (Prev && Tok.Next && Tok.Next->Next) {
1116           bool NextIsUnary = Tok.Next->isUnaryOperator() ||
1117                              Tok.Next->isOneOf(tok::amp, tok::star);
1118           IsCast =
1119               NextIsUnary && !Tok.Next->is(tok::plus) &&
1120               Tok.Next->Next->isOneOf(tok::identifier, tok::numeric_constant);
1121         }
1122
1123         for (; Prev != Tok.MatchingParen; Prev = Prev->Previous) {
1124           if (!Prev ||
1125               !Prev->isOneOf(tok::kw_const, tok::identifier, tok::coloncolon)) {
1126             IsCast = false;
1127             break;
1128           }
1129         }
1130       }
1131     }
1132     return IsCast && !ParensAreEmpty;
1133   }
1134
1135   /// \brief Return the type of the given token assuming it is * or &.
1136   TokenType determineStarAmpUsage(const FormatToken &Tok, bool IsExpression,
1137                                   bool InTemplateArgument) {
1138     if (Style.Language == FormatStyle::LK_JavaScript)
1139       return TT_BinaryOperator;
1140
1141     const FormatToken *PrevToken = Tok.getPreviousNonComment();
1142     if (!PrevToken)
1143       return TT_UnaryOperator;
1144
1145     const FormatToken *NextToken = Tok.getNextNonComment();
1146     if (!NextToken ||
1147         NextToken->isOneOf(tok::arrow, Keywords.kw_final,
1148                            Keywords.kw_override) ||
1149         (NextToken->is(tok::l_brace) && !NextToken->getNextNonComment()))
1150       return TT_PointerOrReference;
1151
1152     if (PrevToken->is(tok::coloncolon))
1153       return TT_PointerOrReference;
1154
1155     if (PrevToken->isOneOf(tok::l_paren, tok::l_square, tok::l_brace,
1156                            tok::comma, tok::semi, tok::kw_return, tok::colon,
1157                            tok::equal, tok::kw_delete, tok::kw_sizeof) ||
1158         PrevToken->isOneOf(TT_BinaryOperator, TT_ConditionalExpr,
1159                            TT_UnaryOperator, TT_CastRParen))
1160       return TT_UnaryOperator;
1161
1162     if (NextToken->is(tok::l_square) && NextToken->isNot(TT_LambdaLSquare))
1163       return TT_PointerOrReference;
1164     if (NextToken->is(tok::kw_operator) && !IsExpression)
1165       return TT_PointerOrReference;
1166     if (NextToken->isOneOf(tok::comma, tok::semi))
1167       return TT_PointerOrReference;
1168
1169     if (PrevToken->is(tok::r_paren) && PrevToken->MatchingParen &&
1170         PrevToken->MatchingParen->Previous &&
1171         PrevToken->MatchingParen->Previous->isOneOf(tok::kw_typeof,
1172                                                     tok::kw_decltype))
1173       return TT_PointerOrReference;
1174
1175     if (PrevToken->Tok.isLiteral() ||
1176         PrevToken->isOneOf(tok::r_paren, tok::r_square, tok::kw_true,
1177                            tok::kw_false, tok::r_brace) ||
1178         NextToken->Tok.isLiteral() ||
1179         NextToken->isOneOf(tok::kw_true, tok::kw_false) ||
1180         NextToken->isUnaryOperator() ||
1181         // If we know we're in a template argument, there are no named
1182         // declarations. Thus, having an identifier on the right-hand side
1183         // indicates a binary operator.
1184         (InTemplateArgument && NextToken->Tok.isAnyIdentifier()))
1185       return TT_BinaryOperator;
1186
1187     // "&&(" is quite unlikely to be two successive unary "&".
1188     if (Tok.is(tok::ampamp) && NextToken && NextToken->is(tok::l_paren))
1189       return TT_BinaryOperator;
1190
1191     // This catches some cases where evaluation order is used as control flow:
1192     //   aaa && aaa->f();
1193     const FormatToken *NextNextToken = NextToken->getNextNonComment();
1194     if (NextNextToken && NextNextToken->is(tok::arrow))
1195       return TT_BinaryOperator;
1196
1197     // It is very unlikely that we are going to find a pointer or reference type
1198     // definition on the RHS of an assignment.
1199     if (IsExpression && !Contexts.back().CaretFound)
1200       return TT_BinaryOperator;
1201
1202     return TT_PointerOrReference;
1203   }
1204
1205   TokenType determinePlusMinusCaretUsage(const FormatToken &Tok) {
1206     const FormatToken *PrevToken = Tok.getPreviousNonComment();
1207     if (!PrevToken || PrevToken->is(TT_CastRParen))
1208       return TT_UnaryOperator;
1209
1210     // Use heuristics to recognize unary operators.
1211     if (PrevToken->isOneOf(tok::equal, tok::l_paren, tok::comma, tok::l_square,
1212                            tok::question, tok::colon, tok::kw_return,
1213                            tok::kw_case, tok::at, tok::l_brace))
1214       return TT_UnaryOperator;
1215
1216     // There can't be two consecutive binary operators.
1217     if (PrevToken->is(TT_BinaryOperator))
1218       return TT_UnaryOperator;
1219
1220     // Fall back to marking the token as binary operator.
1221     return TT_BinaryOperator;
1222   }
1223
1224   /// \brief Determine whether ++/-- are pre- or post-increments/-decrements.
1225   TokenType determineIncrementUsage(const FormatToken &Tok) {
1226     const FormatToken *PrevToken = Tok.getPreviousNonComment();
1227     if (!PrevToken || PrevToken->is(TT_CastRParen))
1228       return TT_UnaryOperator;
1229     if (PrevToken->isOneOf(tok::r_paren, tok::r_square, tok::identifier))
1230       return TT_TrailingUnaryOperator;
1231
1232     return TT_UnaryOperator;
1233   }
1234
1235   SmallVector<Context, 8> Contexts;
1236
1237   const FormatStyle &Style;
1238   AnnotatedLine &Line;
1239   FormatToken *CurrentToken;
1240   bool AutoFound;
1241   const AdditionalKeywords &Keywords;
1242
1243   // Set of "<" tokens that do not open a template parameter list. If parseAngle
1244   // determines that a specific token can't be a template opener, it will make
1245   // same decision irrespective of the decisions for tokens leading up to it.
1246   // Store this information to prevent this from causing exponential runtime.
1247   llvm::SmallPtrSet<FormatToken *, 16> NonTemplateLess;
1248 };
1249
1250 static const int PrecedenceUnaryOperator = prec::PointerToMember + 1;
1251 static const int PrecedenceArrowAndPeriod = prec::PointerToMember + 2;
1252
1253 /// \brief Parses binary expressions by inserting fake parenthesis based on
1254 /// operator precedence.
1255 class ExpressionParser {
1256 public:
1257   ExpressionParser(const FormatStyle &Style, const AdditionalKeywords &Keywords,
1258                    AnnotatedLine &Line)
1259       : Style(Style), Keywords(Keywords), Current(Line.First) {}
1260
1261   /// \brief Parse expressions with the given operatore precedence.
1262   void parse(int Precedence = 0) {
1263     // Skip 'return' and ObjC selector colons as they are not part of a binary
1264     // expression.
1265     while (Current && (Current->is(tok::kw_return) ||
1266                        (Current->is(tok::colon) &&
1267                         Current->isOneOf(TT_ObjCMethodExpr, TT_DictLiteral))))
1268       next();
1269
1270     if (!Current || Precedence > PrecedenceArrowAndPeriod)
1271       return;
1272
1273     // Conditional expressions need to be parsed separately for proper nesting.
1274     if (Precedence == prec::Conditional) {
1275       parseConditionalExpr();
1276       return;
1277     }
1278
1279     // Parse unary operators, which all have a higher precedence than binary
1280     // operators.
1281     if (Precedence == PrecedenceUnaryOperator) {
1282       parseUnaryOperator();
1283       return;
1284     }
1285
1286     FormatToken *Start = Current;
1287     FormatToken *LatestOperator = nullptr;
1288     unsigned OperatorIndex = 0;
1289
1290     while (Current) {
1291       // Consume operators with higher precedence.
1292       parse(Precedence + 1);
1293
1294       int CurrentPrecedence = getCurrentPrecedence();
1295
1296       if (Current && Current->is(TT_SelectorName) &&
1297           Precedence == CurrentPrecedence) {
1298         if (LatestOperator)
1299           addFakeParenthesis(Start, prec::Level(Precedence));
1300         Start = Current;
1301       }
1302
1303       // At the end of the line or when an operator with higher precedence is
1304       // found, insert fake parenthesis and return.
1305       if (!Current || (Current->closesScope() && Current->MatchingParen) ||
1306           (CurrentPrecedence != -1 && CurrentPrecedence < Precedence) ||
1307           (CurrentPrecedence == prec::Conditional &&
1308            Precedence == prec::Assignment && Current->is(tok::colon))) {
1309         break;
1310       }
1311
1312       // Consume scopes: (), [], <> and {}
1313       if (Current->opensScope()) {
1314         while (Current && !Current->closesScope()) {
1315           next();
1316           parse();
1317         }
1318         next();
1319       } else {
1320         // Operator found.
1321         if (CurrentPrecedence == Precedence) {
1322           LatestOperator = Current;
1323           Current->OperatorIndex = OperatorIndex;
1324           ++OperatorIndex;
1325         }
1326         next(/*SkipPastLeadingComments=*/Precedence > 0);
1327       }
1328     }
1329
1330     if (LatestOperator && (Current || Precedence > 0)) {
1331       LatestOperator->LastOperator = true;
1332       if (Precedence == PrecedenceArrowAndPeriod) {
1333         // Call expressions don't have a binary operator precedence.
1334         addFakeParenthesis(Start, prec::Unknown);
1335       } else {
1336         addFakeParenthesis(Start, prec::Level(Precedence));
1337       }
1338     }
1339   }
1340
1341 private:
1342   /// \brief Gets the precedence (+1) of the given token for binary operators
1343   /// and other tokens that we treat like binary operators.
1344   int getCurrentPrecedence() {
1345     if (Current) {
1346       const FormatToken *NextNonComment = Current->getNextNonComment();
1347       if (Current->is(TT_ConditionalExpr))
1348         return prec::Conditional;
1349       if (NextNonComment && NextNonComment->is(tok::colon) &&
1350           NextNonComment->is(TT_DictLiteral))
1351         return prec::Comma;
1352       if (Current->is(TT_LambdaArrow))
1353         return prec::Comma;
1354       if (Current->is(TT_JsFatArrow))
1355         return prec::Assignment;
1356       if (Current->isOneOf(tok::semi, TT_InlineASMColon, TT_SelectorName,
1357                            TT_JsComputedPropertyName) ||
1358           (Current->is(tok::comment) && NextNonComment &&
1359            NextNonComment->is(TT_SelectorName)))
1360         return 0;
1361       if (Current->is(TT_RangeBasedForLoopColon))
1362         return prec::Comma;
1363       if ((Style.Language == FormatStyle::LK_Java ||
1364            Style.Language == FormatStyle::LK_JavaScript) &&
1365           Current->is(Keywords.kw_instanceof))
1366         return prec::Relational;
1367       if (Current->is(TT_BinaryOperator) || Current->is(tok::comma))
1368         return Current->getPrecedence();
1369       if (Current->isOneOf(tok::period, tok::arrow))
1370         return PrecedenceArrowAndPeriod;
1371       if (Style.Language == FormatStyle::LK_Java &&
1372           Current->isOneOf(Keywords.kw_extends, Keywords.kw_implements,
1373                            Keywords.kw_throws))
1374         return 0;
1375     }
1376     return -1;
1377   }
1378
1379   void addFakeParenthesis(FormatToken *Start, prec::Level Precedence) {
1380     Start->FakeLParens.push_back(Precedence);
1381     if (Precedence > prec::Unknown)
1382       Start->StartsBinaryExpression = true;
1383     if (Current) {
1384       FormatToken *Previous = Current->Previous;
1385       while (Previous->is(tok::comment) && Previous->Previous)
1386         Previous = Previous->Previous;
1387       ++Previous->FakeRParens;
1388       if (Precedence > prec::Unknown)
1389         Previous->EndsBinaryExpression = true;
1390     }
1391   }
1392
1393   /// \brief Parse unary operator expressions and surround them with fake
1394   /// parentheses if appropriate.
1395   void parseUnaryOperator() {
1396     if (!Current || Current->isNot(TT_UnaryOperator)) {
1397       parse(PrecedenceArrowAndPeriod);
1398       return;
1399     }
1400
1401     FormatToken *Start = Current;
1402     next();
1403     parseUnaryOperator();
1404
1405     // The actual precedence doesn't matter.
1406     addFakeParenthesis(Start, prec::Unknown);
1407   }
1408
1409   void parseConditionalExpr() {
1410     while (Current && Current->isTrailingComment()) {
1411       next();
1412     }
1413     FormatToken *Start = Current;
1414     parse(prec::LogicalOr);
1415     if (!Current || !Current->is(tok::question))
1416       return;
1417     next();
1418     parse(prec::Assignment);
1419     if (!Current || Current->isNot(TT_ConditionalExpr))
1420       return;
1421     next();
1422     parse(prec::Assignment);
1423     addFakeParenthesis(Start, prec::Conditional);
1424   }
1425
1426   void next(bool SkipPastLeadingComments = true) {
1427     if (Current)
1428       Current = Current->Next;
1429     while (Current &&
1430            (Current->NewlinesBefore == 0 || SkipPastLeadingComments) &&
1431            Current->isTrailingComment())
1432       Current = Current->Next;
1433   }
1434
1435   const FormatStyle &Style;
1436   const AdditionalKeywords &Keywords;
1437   FormatToken *Current;
1438 };
1439
1440 } // end anonymous namespace
1441
1442 void TokenAnnotator::setCommentLineLevels(
1443     SmallVectorImpl<AnnotatedLine *> &Lines) {
1444   const AnnotatedLine *NextNonCommentLine = nullptr;
1445   for (SmallVectorImpl<AnnotatedLine *>::reverse_iterator I = Lines.rbegin(),
1446                                                           E = Lines.rend();
1447        I != E; ++I) {
1448     if (NextNonCommentLine && (*I)->First->is(tok::comment) &&
1449         (*I)->First->Next == nullptr)
1450       (*I)->Level = NextNonCommentLine->Level;
1451     else
1452       NextNonCommentLine = (*I)->First->isNot(tok::r_brace) ? (*I) : nullptr;
1453
1454     setCommentLineLevels((*I)->Children);
1455   }
1456 }
1457
1458 void TokenAnnotator::annotate(AnnotatedLine &Line) {
1459   for (SmallVectorImpl<AnnotatedLine *>::iterator I = Line.Children.begin(),
1460                                                   E = Line.Children.end();
1461        I != E; ++I) {
1462     annotate(**I);
1463   }
1464   AnnotatingParser Parser(Style, Line, Keywords);
1465   Line.Type = Parser.parseLine();
1466   if (Line.Type == LT_Invalid)
1467     return;
1468
1469   ExpressionParser ExprParser(Style, Keywords, Line);
1470   ExprParser.parse();
1471
1472   if (Line.startsWith(TT_ObjCMethodSpecifier))
1473     Line.Type = LT_ObjCMethodDecl;
1474   else if (Line.startsWith(TT_ObjCDecl))
1475     Line.Type = LT_ObjCDecl;
1476   else if (Line.startsWith(TT_ObjCProperty))
1477     Line.Type = LT_ObjCProperty;
1478
1479   Line.First->SpacesRequiredBefore = 1;
1480   Line.First->CanBreakBefore = Line.First->MustBreakBefore;
1481 }
1482
1483 // This function heuristically determines whether 'Current' starts the name of a
1484 // function declaration.
1485 static bool isFunctionDeclarationName(const FormatToken &Current) {
1486   auto skipOperatorName = [](const FormatToken* Next) -> const FormatToken* {
1487     for (; Next; Next = Next->Next) {
1488       if (Next->is(TT_OverloadedOperatorLParen))
1489         return Next;
1490       if (Next->is(TT_OverloadedOperator))
1491         continue;
1492       if (Next->isOneOf(tok::kw_new, tok::kw_delete)) {
1493         // For 'new[]' and 'delete[]'.
1494         if (Next->Next && Next->Next->is(tok::l_square) &&
1495             Next->Next->Next && Next->Next->Next->is(tok::r_square))
1496           Next = Next->Next->Next;
1497         continue;
1498       }
1499
1500       break;
1501     }
1502     return nullptr;
1503   };
1504
1505   const FormatToken *Next = Current.Next;
1506   if (Current.is(tok::kw_operator)) {
1507     if (Current.Previous && Current.Previous->is(tok::coloncolon))
1508       return false;
1509     Next = skipOperatorName(Next);
1510   } else {
1511     if (!Current.is(TT_StartOfName) || Current.NestingLevel != 0)
1512       return false;
1513     for (; Next; Next = Next->Next) {
1514       if (Next->is(TT_TemplateOpener)) {
1515         Next = Next->MatchingParen;
1516       } else if (Next->is(tok::coloncolon)) {
1517         Next = Next->Next;
1518         if (!Next)
1519           return false;
1520         if (Next->is(tok::kw_operator)) {
1521           Next = skipOperatorName(Next->Next);
1522           break;
1523         }
1524         if (!Next->is(tok::identifier))
1525           return false;
1526       } else if (Next->is(tok::l_paren)) {
1527         break;
1528       } else {
1529         return false;
1530       }
1531     }
1532   }
1533
1534   if (!Next || !Next->is(tok::l_paren))
1535     return false;
1536   if (Next->Next == Next->MatchingParen)
1537     return true;
1538   for (const FormatToken *Tok = Next->Next; Tok && Tok != Next->MatchingParen;
1539        Tok = Tok->Next) {
1540     if (Tok->is(tok::kw_const) || Tok->isSimpleTypeSpecifier() ||
1541         Tok->isOneOf(TT_PointerOrReference, TT_StartOfName))
1542       return true;
1543     if (Tok->isOneOf(tok::l_brace, tok::string_literal, TT_ObjCMethodExpr) ||
1544         Tok->Tok.isLiteral())
1545       return false;
1546   }
1547   return false;
1548 }
1549
1550 void TokenAnnotator::calculateFormattingInformation(AnnotatedLine &Line) {
1551   for (SmallVectorImpl<AnnotatedLine *>::iterator I = Line.Children.begin(),
1552                                                   E = Line.Children.end();
1553        I != E; ++I) {
1554     calculateFormattingInformation(**I);
1555   }
1556
1557   Line.First->TotalLength =
1558       Line.First->IsMultiline ? Style.ColumnLimit : Line.First->ColumnWidth;
1559   if (!Line.First->Next)
1560     return;
1561   FormatToken *Current = Line.First->Next;
1562   bool InFunctionDecl = Line.MightBeFunctionDecl;
1563   while (Current) {
1564     if (isFunctionDeclarationName(*Current))
1565       Current->Type = TT_FunctionDeclarationName;
1566     if (Current->is(TT_LineComment)) {
1567       if (Current->Previous->BlockKind == BK_BracedInit &&
1568           Current->Previous->opensScope())
1569         Current->SpacesRequiredBefore = Style.Cpp11BracedListStyle ? 0 : 1;
1570       else
1571         Current->SpacesRequiredBefore = Style.SpacesBeforeTrailingComments;
1572
1573       // If we find a trailing comment, iterate backwards to determine whether
1574       // it seems to relate to a specific parameter. If so, break before that
1575       // parameter to avoid changing the comment's meaning. E.g. don't move 'b'
1576       // to the previous line in:
1577       //   SomeFunction(a,
1578       //                b, // comment
1579       //                c);
1580       if (!Current->HasUnescapedNewline) {
1581         for (FormatToken *Parameter = Current->Previous; Parameter;
1582              Parameter = Parameter->Previous) {
1583           if (Parameter->isOneOf(tok::comment, tok::r_brace))
1584             break;
1585           if (Parameter->Previous && Parameter->Previous->is(tok::comma)) {
1586             if (!Parameter->Previous->is(TT_CtorInitializerComma) &&
1587                 Parameter->HasUnescapedNewline)
1588               Parameter->MustBreakBefore = true;
1589             break;
1590           }
1591         }
1592       }
1593     } else if (Current->SpacesRequiredBefore == 0 &&
1594                spaceRequiredBefore(Line, *Current)) {
1595       Current->SpacesRequiredBefore = 1;
1596     }
1597
1598     Current->MustBreakBefore =
1599         Current->MustBreakBefore || mustBreakBefore(Line, *Current);
1600
1601     if ((Style.AlwaysBreakAfterDefinitionReturnType == FormatStyle::DRTBS_All ||
1602          (Style.AlwaysBreakAfterDefinitionReturnType ==
1603               FormatStyle::DRTBS_TopLevel &&
1604           Line.Level == 0)) &&
1605         InFunctionDecl && Current->is(TT_FunctionDeclarationName) &&
1606         !Line.Last->isOneOf(tok::semi, tok::comment)) // Only for definitions.
1607       // FIXME: Line.Last points to other characters than tok::semi
1608       // and tok::lbrace.
1609       Current->MustBreakBefore = true;
1610
1611     Current->CanBreakBefore =
1612         Current->MustBreakBefore || canBreakBefore(Line, *Current);
1613     unsigned ChildSize = 0;
1614     if (Current->Previous->Children.size() == 1) {
1615       FormatToken &LastOfChild = *Current->Previous->Children[0]->Last;
1616       ChildSize = LastOfChild.isTrailingComment() ? Style.ColumnLimit
1617                                                   : LastOfChild.TotalLength + 1;
1618     }
1619     const FormatToken *Prev = Current->Previous;
1620     if (Current->MustBreakBefore || Prev->Children.size() > 1 ||
1621         (Prev->Children.size() == 1 &&
1622          Prev->Children[0]->First->MustBreakBefore) ||
1623         Current->IsMultiline)
1624       Current->TotalLength = Prev->TotalLength + Style.ColumnLimit;
1625     else
1626       Current->TotalLength = Prev->TotalLength + Current->ColumnWidth +
1627                              ChildSize + Current->SpacesRequiredBefore;
1628
1629     if (Current->is(TT_CtorInitializerColon))
1630       InFunctionDecl = false;
1631
1632     // FIXME: Only calculate this if CanBreakBefore is true once static
1633     // initializers etc. are sorted out.
1634     // FIXME: Move magic numbers to a better place.
1635     Current->SplitPenalty = 20 * Current->BindingStrength +
1636                             splitPenalty(Line, *Current, InFunctionDecl);
1637
1638     Current = Current->Next;
1639   }
1640
1641   calculateUnbreakableTailLengths(Line);
1642   for (Current = Line.First; Current != nullptr; Current = Current->Next) {
1643     if (Current->Role)
1644       Current->Role->precomputeFormattingInfos(Current);
1645   }
1646
1647   DEBUG({ printDebugInfo(Line); });
1648 }
1649
1650 void TokenAnnotator::calculateUnbreakableTailLengths(AnnotatedLine &Line) {
1651   unsigned UnbreakableTailLength = 0;
1652   FormatToken *Current = Line.Last;
1653   while (Current) {
1654     Current->UnbreakableTailLength = UnbreakableTailLength;
1655     if (Current->CanBreakBefore ||
1656         Current->isOneOf(tok::comment, tok::string_literal)) {
1657       UnbreakableTailLength = 0;
1658     } else {
1659       UnbreakableTailLength +=
1660           Current->ColumnWidth + Current->SpacesRequiredBefore;
1661     }
1662     Current = Current->Previous;
1663   }
1664 }
1665
1666 unsigned TokenAnnotator::splitPenalty(const AnnotatedLine &Line,
1667                                       const FormatToken &Tok,
1668                                       bool InFunctionDecl) {
1669   const FormatToken &Left = *Tok.Previous;
1670   const FormatToken &Right = Tok;
1671
1672   if (Left.is(tok::semi))
1673     return 0;
1674
1675   if (Style.Language == FormatStyle::LK_Java) {
1676     if (Right.isOneOf(Keywords.kw_extends, Keywords.kw_throws))
1677       return 1;
1678     if (Right.is(Keywords.kw_implements))
1679       return 2;
1680     if (Left.is(tok::comma) && Left.NestingLevel == 0)
1681       return 3;
1682   } else if (Style.Language == FormatStyle::LK_JavaScript) {
1683     if (Right.is(Keywords.kw_function) && Left.isNot(tok::comma))
1684       return 100;
1685     if (Left.is(TT_JsTypeColon))
1686       return 100;
1687   }
1688
1689   if (Left.is(tok::comma) || (Right.is(tok::identifier) && Right.Next &&
1690                               Right.Next->is(TT_DictLiteral)))
1691     return 1;
1692   if (Right.is(tok::l_square)) {
1693     if (Style.Language == FormatStyle::LK_Proto)
1694       return 1;
1695     // Slightly prefer formatting local lambda definitions like functions.
1696     if (Right.is(TT_LambdaLSquare) && Left.is(tok::equal))
1697       return 50;
1698     if (!Right.isOneOf(TT_ObjCMethodExpr, TT_LambdaLSquare,
1699                        TT_ArrayInitializerLSquare))
1700       return 500;
1701   }
1702
1703   if (Right.isOneOf(TT_StartOfName, TT_FunctionDeclarationName) ||
1704       Right.is(tok::kw_operator)) {
1705     if (Line.startsWith(tok::kw_for) && Right.PartOfMultiVariableDeclStmt)
1706       return 3;
1707     if (Left.is(TT_StartOfName))
1708       return 110;
1709     if (InFunctionDecl && Right.NestingLevel == 0)
1710       return Style.PenaltyReturnTypeOnItsOwnLine;
1711     return 200;
1712   }
1713   if (Right.is(TT_PointerOrReference))
1714     return 190;
1715   if (Right.is(TT_LambdaArrow))
1716     return 110;
1717   if (Left.is(tok::equal) && Right.is(tok::l_brace))
1718     return 150;
1719   if (Left.is(TT_CastRParen))
1720     return 100;
1721   if (Left.is(tok::coloncolon) ||
1722       (Right.is(tok::period) && Style.Language == FormatStyle::LK_Proto))
1723     return 500;
1724   if (Left.isOneOf(tok::kw_class, tok::kw_struct))
1725     return 5000;
1726
1727   if (Left.isOneOf(TT_RangeBasedForLoopColon, TT_InheritanceColon))
1728     return 2;
1729
1730   if (Right.isMemberAccess()) {
1731     if (Left.is(tok::r_paren) && Left.MatchingParen &&
1732         Left.MatchingParen->ParameterCount > 0)
1733       return 20; // Should be smaller than breaking at a nested comma.
1734     return 150;
1735   }
1736
1737   if (Right.is(TT_TrailingAnnotation) &&
1738       (!Right.Next || Right.Next->isNot(tok::l_paren))) {
1739     // Moving trailing annotations to the next line is fine for ObjC method
1740     // declarations.
1741     if (Line.startsWith(TT_ObjCMethodSpecifier))
1742       return 10;
1743     // Generally, breaking before a trailing annotation is bad unless it is
1744     // function-like. It seems to be especially preferable to keep standard
1745     // annotations (i.e. "const", "final" and "override") on the same line.
1746     // Use a slightly higher penalty after ")" so that annotations like
1747     // "const override" are kept together.
1748     bool is_short_annotation = Right.TokenText.size() < 10;
1749     return (Left.is(tok::r_paren) ? 100 : 120) + (is_short_annotation ? 50 : 0);
1750   }
1751
1752   // In for-loops, prefer breaking at ',' and ';'.
1753   if (Line.startsWith(tok::kw_for) && Left.is(tok::equal))
1754     return 4;
1755
1756   // In Objective-C method expressions, prefer breaking before "param:" over
1757   // breaking after it.
1758   if (Right.is(TT_SelectorName))
1759     return 0;
1760   if (Left.is(tok::colon) && Left.is(TT_ObjCMethodExpr))
1761     return Line.MightBeFunctionDecl ? 50 : 500;
1762
1763   if (Left.is(tok::l_paren) && InFunctionDecl && Style.AlignAfterOpenBracket)
1764     return 100;
1765   if (Left.is(tok::l_paren) && Left.Previous &&
1766       Left.Previous->isOneOf(tok::kw_if, tok::kw_for))
1767     return 1000;
1768   if (Left.is(tok::equal) && InFunctionDecl)
1769     return 110;
1770   if (Right.is(tok::r_brace))
1771     return 1;
1772   if (Left.is(TT_TemplateOpener))
1773     return 100;
1774   if (Left.opensScope()) {
1775     if (!Style.AlignAfterOpenBracket)
1776       return 0;
1777     return Left.ParameterCount > 1 ? Style.PenaltyBreakBeforeFirstCallParameter
1778                                    : 19;
1779   }
1780   if (Left.is(TT_JavaAnnotation))
1781     return 50;
1782
1783   if (Right.is(tok::lessless)) {
1784     if (Left.is(tok::string_literal) &&
1785         (!Right.LastOperator || Right.OperatorIndex != 1)) {
1786       StringRef Content = Left.TokenText;
1787       if (Content.startswith("\""))
1788         Content = Content.drop_front(1);
1789       if (Content.endswith("\""))
1790         Content = Content.drop_back(1);
1791       Content = Content.trim();
1792       if (Content.size() > 1 &&
1793           (Content.back() == ':' || Content.back() == '='))
1794         return 25;
1795     }
1796     return 1; // Breaking at a << is really cheap.
1797   }
1798   if (Left.is(TT_ConditionalExpr))
1799     return prec::Conditional;
1800   prec::Level Level = Left.getPrecedence();
1801   if (Level != prec::Unknown)
1802     return Level;
1803   Level = Right.getPrecedence();
1804   if (Level != prec::Unknown)
1805     return Level;
1806
1807   return 3;
1808 }
1809
1810 bool TokenAnnotator::spaceRequiredBetween(const AnnotatedLine &Line,
1811                                           const FormatToken &Left,
1812                                           const FormatToken &Right) {
1813   if (Left.is(tok::kw_return) && Right.isNot(tok::semi))
1814     return true;
1815   if (Style.ObjCSpaceAfterProperty && Line.Type == LT_ObjCProperty &&
1816       Left.Tok.getObjCKeywordID() == tok::objc_property)
1817     return true;
1818   if (Right.is(tok::hashhash))
1819     return Left.is(tok::hash);
1820   if (Left.isOneOf(tok::hashhash, tok::hash))
1821     return Right.is(tok::hash);
1822   if (Left.is(tok::l_paren) && Right.is(tok::r_paren))
1823     return Style.SpaceInEmptyParentheses;
1824   if (Left.is(tok::l_paren) || Right.is(tok::r_paren))
1825     return (Right.is(TT_CastRParen) ||
1826             (Left.MatchingParen && Left.MatchingParen->is(TT_CastRParen)))
1827                ? Style.SpacesInCStyleCastParentheses
1828                : Style.SpacesInParentheses;
1829   if (Right.isOneOf(tok::semi, tok::comma))
1830     return false;
1831   if (Right.is(tok::less) &&
1832       (Left.is(tok::kw_template) ||
1833        (Line.Type == LT_ObjCDecl && Style.ObjCSpaceBeforeProtocolList)))
1834     return true;
1835   if (Left.isOneOf(tok::exclaim, tok::tilde))
1836     return false;
1837   if (Left.is(tok::at) &&
1838       Right.isOneOf(tok::identifier, tok::string_literal, tok::char_constant,
1839                     tok::numeric_constant, tok::l_paren, tok::l_brace,
1840                     tok::kw_true, tok::kw_false))
1841     return false;
1842   if (Left.is(tok::coloncolon))
1843     return false;
1844   if (Left.is(tok::less) || Right.isOneOf(tok::greater, tok::less))
1845     return false;
1846   if (Right.is(tok::ellipsis))
1847     return Left.Tok.isLiteral();
1848   if (Left.is(tok::l_square) && Right.is(tok::amp))
1849     return false;
1850   if (Right.is(TT_PointerOrReference))
1851     return (Left.is(tok::r_paren) && Left.MatchingParen &&
1852             (Left.MatchingParen->is(TT_OverloadedOperatorLParen) ||
1853              (Left.MatchingParen->Previous &&
1854               Left.MatchingParen->Previous->is(TT_FunctionDeclarationName)))) ||
1855            (Left.Tok.isLiteral() ||
1856             (!Left.isOneOf(TT_PointerOrReference, tok::l_paren) &&
1857              (Style.PointerAlignment != FormatStyle::PAS_Left ||
1858               Line.IsMultiVariableDeclStmt)));
1859   if (Right.is(TT_FunctionTypeLParen) && Left.isNot(tok::l_paren) &&
1860       (!Left.is(TT_PointerOrReference) ||
1861        (Style.PointerAlignment != FormatStyle::PAS_Right &&
1862         !Line.IsMultiVariableDeclStmt)))
1863     return true;
1864   if (Left.is(TT_PointerOrReference))
1865     return Right.Tok.isLiteral() ||
1866            Right.isOneOf(TT_BlockComment, Keywords.kw_final,
1867                          Keywords.kw_override) ||
1868            (Right.is(tok::l_brace) && Right.BlockKind == BK_Block) ||
1869            (!Right.isOneOf(TT_PointerOrReference, TT_ArraySubscriptLSquare,
1870                            tok::l_paren) &&
1871             (Style.PointerAlignment != FormatStyle::PAS_Right &&
1872              !Line.IsMultiVariableDeclStmt) &&
1873             Left.Previous &&
1874             !Left.Previous->isOneOf(tok::l_paren, tok::coloncolon));
1875   if (Right.is(tok::star) && Left.is(tok::l_paren))
1876     return false;
1877   if (Left.is(tok::l_square))
1878     return (Left.is(TT_ArrayInitializerLSquare) &&
1879             Style.SpacesInContainerLiterals && Right.isNot(tok::r_square)) ||
1880            (Left.is(TT_ArraySubscriptLSquare) && Style.SpacesInSquareBrackets &&
1881             Right.isNot(tok::r_square));
1882   if (Right.is(tok::r_square))
1883     return Right.MatchingParen &&
1884            ((Style.SpacesInContainerLiterals &&
1885              Right.MatchingParen->is(TT_ArrayInitializerLSquare)) ||
1886             (Style.SpacesInSquareBrackets &&
1887              Right.MatchingParen->is(TT_ArraySubscriptLSquare)));
1888   if (Right.is(tok::l_square) &&
1889       !Right.isOneOf(TT_ObjCMethodExpr, TT_LambdaLSquare) &&
1890       !Left.isOneOf(tok::numeric_constant, TT_DictLiteral))
1891     return false;
1892   if (Left.is(tok::colon))
1893     return !Left.is(TT_ObjCMethodExpr);
1894   if (Left.is(tok::l_brace) && Right.is(tok::r_brace))
1895     return !Left.Children.empty(); // No spaces in "{}".
1896   if ((Left.is(tok::l_brace) && Left.BlockKind != BK_Block) ||
1897       (Right.is(tok::r_brace) && Right.MatchingParen &&
1898        Right.MatchingParen->BlockKind != BK_Block))
1899     return !Style.Cpp11BracedListStyle;
1900   if (Left.is(TT_BlockComment))
1901     return !Left.TokenText.endswith("=*/");
1902   if (Right.is(tok::l_paren)) {
1903     if (Left.is(tok::r_paren) && Left.is(TT_AttributeParen))
1904       return true;
1905     return Line.Type == LT_ObjCDecl || Left.is(tok::semi) ||
1906            (Style.SpaceBeforeParens != FormatStyle::SBPO_Never &&
1907             (Left.isOneOf(tok::kw_if, tok::pp_elif, tok::kw_for, tok::kw_while,
1908                           tok::kw_switch, tok::kw_case, TT_ForEachMacro,
1909                           TT_ObjCForIn) ||
1910              (Left.isOneOf(tok::kw_try, Keywords.kw___except, tok::kw_catch,
1911                            tok::kw_new, tok::kw_delete) &&
1912               (!Left.Previous || Left.Previous->isNot(tok::period))))) ||
1913            (Style.SpaceBeforeParens == FormatStyle::SBPO_Always &&
1914             (Left.is(tok::identifier) || Left.isFunctionLikeKeyword() ||
1915              Left.is(tok::r_paren)) &&
1916             Line.Type != LT_PreprocessorDirective);
1917   }
1918   if (Left.is(tok::at) && Right.Tok.getObjCKeywordID() != tok::objc_not_keyword)
1919     return false;
1920   if (Right.is(TT_UnaryOperator))
1921     return !Left.isOneOf(tok::l_paren, tok::l_square, tok::at) &&
1922            (Left.isNot(tok::colon) || Left.isNot(TT_ObjCMethodExpr));
1923   if ((Left.isOneOf(tok::identifier, tok::greater, tok::r_square,
1924                     tok::r_paren) ||
1925        Left.isSimpleTypeSpecifier()) &&
1926       Right.is(tok::l_brace) && Right.getNextNonComment() &&
1927       Right.BlockKind != BK_Block)
1928     return false;
1929   if (Left.is(tok::period) || Right.is(tok::period))
1930     return false;
1931   if (Right.is(tok::hash) && Left.is(tok::identifier) && Left.TokenText == "L")
1932     return false;
1933   if (Left.is(TT_TemplateCloser) && Left.MatchingParen &&
1934       Left.MatchingParen->Previous &&
1935       Left.MatchingParen->Previous->is(tok::period))
1936     // A.<B>DoSomething();
1937     return false;
1938   if (Left.is(TT_TemplateCloser) && Right.is(tok::l_square))
1939     return false;
1940   return true;
1941 }
1942
1943 bool TokenAnnotator::spaceRequiredBefore(const AnnotatedLine &Line,
1944                                          const FormatToken &Right) {
1945   const FormatToken &Left = *Right.Previous;
1946   if (Right.Tok.getIdentifierInfo() && Left.Tok.getIdentifierInfo())
1947     return true; // Never ever merge two identifiers.
1948   if (Style.Language == FormatStyle::LK_Cpp) {
1949     if (Left.is(tok::kw_operator))
1950       return Right.is(tok::coloncolon);
1951   } else if (Style.Language == FormatStyle::LK_Proto) {
1952     if (Right.is(tok::period) &&
1953         Left.isOneOf(Keywords.kw_optional, Keywords.kw_required,
1954                      Keywords.kw_repeated))
1955       return true;
1956     if (Right.is(tok::l_paren) &&
1957         Left.isOneOf(Keywords.kw_returns, Keywords.kw_option))
1958       return true;
1959   } else if (Style.Language == FormatStyle::LK_JavaScript) {
1960     if (Left.isOneOf(Keywords.kw_let, Keywords.kw_var, TT_JsFatArrow))
1961       return true;
1962     if (Right.isOneOf(TT_JsTypeColon, TT_JsTypeOptionalQuestion))
1963       return false;
1964     if ((Left.is(tok::l_brace) || Right.is(tok::r_brace)) &&
1965         Line.First->isOneOf(Keywords.kw_import, tok::kw_export))
1966       return false;
1967     if (Left.is(tok::ellipsis))
1968       return false;
1969     if (Left.is(TT_TemplateCloser) &&
1970         !Right.isOneOf(tok::equal, tok::l_brace, tok::comma, tok::l_square,
1971                        Keywords.kw_implements, Keywords.kw_extends))
1972       // Type assertions ('<type>expr') are not followed by whitespace. Other
1973       // locations that should have whitespace following are identified by the
1974       // above set of follower tokens.
1975       return false;
1976   } else if (Style.Language == FormatStyle::LK_Java) {
1977     if (Left.is(tok::r_square) && Right.is(tok::l_brace))
1978       return true;
1979     if (Left.is(Keywords.kw_synchronized) && Right.is(tok::l_paren))
1980       return Style.SpaceBeforeParens != FormatStyle::SBPO_Never;
1981     if ((Left.isOneOf(tok::kw_static, tok::kw_public, tok::kw_private,
1982                       tok::kw_protected) ||
1983          Left.isOneOf(Keywords.kw_final, Keywords.kw_abstract,
1984                       Keywords.kw_native)) &&
1985         Right.is(TT_TemplateOpener))
1986       return true;
1987   }
1988   if (Left.is(TT_ImplicitStringLiteral))
1989     return Right.WhitespaceRange.getBegin() != Right.WhitespaceRange.getEnd();
1990   if (Line.Type == LT_ObjCMethodDecl) {
1991     if (Left.is(TT_ObjCMethodSpecifier))
1992       return true;
1993     if (Left.is(tok::r_paren) && Right.is(tok::identifier))
1994       // Don't space between ')' and <id>
1995       return false;
1996   }
1997   if (Line.Type == LT_ObjCProperty &&
1998       (Right.is(tok::equal) || Left.is(tok::equal)))
1999     return false;
2000
2001   if (Right.isOneOf(TT_TrailingReturnArrow, TT_LambdaArrow) ||
2002       Left.isOneOf(TT_TrailingReturnArrow, TT_LambdaArrow))
2003     return true;
2004   if (Left.is(tok::comma))
2005     return true;
2006   if (Right.is(tok::comma))
2007     return false;
2008   if (Right.isOneOf(TT_CtorInitializerColon, TT_ObjCBlockLParen))
2009     return true;
2010   if (Right.is(TT_OverloadedOperatorLParen))
2011     return Style.SpaceBeforeParens == FormatStyle::SBPO_Always;
2012   if (Right.is(tok::colon)) {
2013     if (Line.First->isOneOf(tok::kw_case, tok::kw_default) ||
2014         !Right.getNextNonComment() || Right.getNextNonComment()->is(tok::semi))
2015       return false;
2016     if (Right.is(TT_ObjCMethodExpr))
2017       return false;
2018     if (Left.is(tok::question))
2019       return false;
2020     if (Right.is(TT_InlineASMColon) && Left.is(tok::coloncolon))
2021       return false;
2022     if (Right.is(TT_DictLiteral))
2023       return Style.SpacesInContainerLiterals;
2024     return true;
2025   }
2026   if (Left.is(TT_UnaryOperator))
2027     return Right.is(TT_BinaryOperator);
2028
2029   // If the next token is a binary operator or a selector name, we have
2030   // incorrectly classified the parenthesis as a cast. FIXME: Detect correctly.
2031   if (Left.is(TT_CastRParen))
2032     return Style.SpaceAfterCStyleCast ||
2033            Right.isOneOf(TT_BinaryOperator, TT_SelectorName);
2034
2035   if (Left.is(tok::greater) && Right.is(tok::greater))
2036     return Right.is(TT_TemplateCloser) && Left.is(TT_TemplateCloser) &&
2037            (Style.Standard != FormatStyle::LS_Cpp11 || Style.SpacesInAngles);
2038   if (Right.isOneOf(tok::arrow, tok::period, tok::arrowstar, tok::periodstar) ||
2039       Left.isOneOf(tok::arrow, tok::period, tok::arrowstar, tok::periodstar))
2040     return false;
2041   if (!Style.SpaceBeforeAssignmentOperators &&
2042       Right.getPrecedence() == prec::Assignment)
2043     return false;
2044   if (Right.is(tok::coloncolon) && Left.isNot(tok::l_brace))
2045     return (Left.is(TT_TemplateOpener) &&
2046             Style.Standard == FormatStyle::LS_Cpp03) ||
2047            !(Left.isOneOf(tok::identifier, tok::l_paren, tok::r_paren) ||
2048              Left.isOneOf(TT_TemplateCloser, TT_TemplateOpener));
2049   if ((Left.is(TT_TemplateOpener)) != (Right.is(TT_TemplateCloser)))
2050     return Style.SpacesInAngles;
2051   if ((Right.is(TT_BinaryOperator) && !Left.is(tok::l_paren)) ||
2052       Left.isOneOf(TT_BinaryOperator, TT_ConditionalExpr))
2053     return true;
2054   if (Left.is(TT_TemplateCloser) && Right.is(tok::l_paren) &&
2055       Right.isNot(TT_FunctionTypeLParen))
2056     return Style.SpaceBeforeParens == FormatStyle::SBPO_Always;
2057   if (Right.is(TT_TemplateOpener) && Left.is(tok::r_paren) &&
2058       Left.MatchingParen && Left.MatchingParen->is(TT_OverloadedOperatorLParen))
2059     return false;
2060   if (Right.is(tok::less) && Left.isNot(tok::l_paren) &&
2061       Line.startsWith(tok::hash))
2062     return true;
2063   if (Right.is(TT_TrailingUnaryOperator))
2064     return false;
2065   if (Left.is(TT_RegexLiteral))
2066     return false;
2067   return spaceRequiredBetween(Line, Left, Right);
2068 }
2069
2070 // Returns 'true' if 'Tok' is a brace we'd want to break before in Allman style.
2071 static bool isAllmanBrace(const FormatToken &Tok) {
2072   return Tok.is(tok::l_brace) && Tok.BlockKind == BK_Block &&
2073          !Tok.isOneOf(TT_ObjCBlockLBrace, TT_DictLiteral);
2074 }
2075
2076 bool TokenAnnotator::mustBreakBefore(const AnnotatedLine &Line,
2077                                      const FormatToken &Right) {
2078   const FormatToken &Left = *Right.Previous;
2079   if (Right.NewlinesBefore > 1 && Style.MaxEmptyLinesToKeep > 0)
2080     return true;
2081
2082   if (Style.Language == FormatStyle::LK_JavaScript) {
2083     // FIXME: This might apply to other languages and token kinds.
2084     if (Right.is(tok::char_constant) && Left.is(tok::plus) && Left.Previous &&
2085         Left.Previous->is(tok::char_constant))
2086       return true;
2087     if (Left.is(TT_DictLiteral) && Left.is(tok::l_brace) && Line.Level == 0 &&
2088         Left.Previous && Left.Previous->is(tok::equal) &&
2089         Line.First->isOneOf(tok::identifier, Keywords.kw_import, tok::kw_export,
2090                             tok::kw_const) &&
2091         // kw_var/kw_let are pseudo-tokens that are tok::identifier, so match
2092         // above.
2093         !Line.First->isOneOf(Keywords.kw_var, Keywords.kw_let))
2094       // Object literals on the top level of a file are treated as "enum-style".
2095       // Each key/value pair is put on a separate line, instead of bin-packing.
2096       return true;
2097     if (Left.is(tok::l_brace) && Line.Level == 0 &&
2098         (Line.startsWith(tok::kw_enum) ||
2099          Line.startsWith(tok::kw_export, tok::kw_enum)))
2100       // JavaScript top-level enum key/value pairs are put on separate lines
2101       // instead of bin-packing.
2102       return true;
2103     if (Right.is(tok::r_brace) && Left.is(tok::l_brace) &&
2104         !Left.Children.empty())
2105       // Support AllowShortFunctionsOnASingleLine for JavaScript.
2106       return Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_None ||
2107              (Left.NestingLevel == 0 && Line.Level == 0 &&
2108               Style.AllowShortFunctionsOnASingleLine ==
2109                   FormatStyle::SFS_Inline);
2110   } else if (Style.Language == FormatStyle::LK_Java) {
2111     if (Right.is(tok::plus) && Left.is(tok::string_literal) && Right.Next &&
2112         Right.Next->is(tok::string_literal))
2113       return true;
2114   }
2115
2116   // If the last token before a '}' is a comma or a trailing comment, the
2117   // intention is to insert a line break after it in order to make shuffling
2118   // around entries easier.
2119   const FormatToken *BeforeClosingBrace = nullptr;
2120   if (Left.isOneOf(tok::l_brace, TT_ArrayInitializerLSquare) &&
2121       Left.BlockKind != BK_Block && Left.MatchingParen)
2122     BeforeClosingBrace = Left.MatchingParen->Previous;
2123   else if (Right.MatchingParen &&
2124            Right.MatchingParen->isOneOf(tok::l_brace,
2125                                         TT_ArrayInitializerLSquare))
2126     BeforeClosingBrace = &Left;
2127   if (BeforeClosingBrace && (BeforeClosingBrace->is(tok::comma) ||
2128                              BeforeClosingBrace->isTrailingComment()))
2129     return true;
2130
2131   if (Right.is(tok::comment))
2132     return Left.BlockKind != BK_BracedInit &&
2133            Left.isNot(TT_CtorInitializerColon) &&
2134            (Right.NewlinesBefore > 0 && Right.HasUnescapedNewline);
2135   if (Left.isTrailingComment())
2136     return true;
2137   if (Left.isStringLiteral() &&
2138       (Right.isStringLiteral() || Right.is(TT_ObjCStringLiteral)))
2139     return true;
2140   if (Right.Previous->IsUnterminatedLiteral)
2141     return true;
2142   if (Right.is(tok::lessless) && Right.Next &&
2143       Right.Previous->is(tok::string_literal) &&
2144       Right.Next->is(tok::string_literal))
2145     return true;
2146   if (Right.Previous->ClosesTemplateDeclaration &&
2147       Right.Previous->MatchingParen &&
2148       Right.Previous->MatchingParen->NestingLevel == 0 &&
2149       Style.AlwaysBreakTemplateDeclarations)
2150     return true;
2151   if ((Right.isOneOf(TT_CtorInitializerComma, TT_CtorInitializerColon)) &&
2152       Style.BreakConstructorInitializersBeforeComma &&
2153       !Style.ConstructorInitializerAllOnOneLineOrOnePerLine)
2154     return true;
2155   if (Right.is(tok::string_literal) && Right.TokenText.startswith("R\""))
2156     // Raw string literals are special wrt. line breaks. The author has made a
2157     // deliberate choice and might have aligned the contents of the string
2158     // literal accordingly. Thus, we try keep existing line breaks.
2159     return Right.NewlinesBefore > 0;
2160   if (Right.Previous->is(tok::l_brace) && Right.NestingLevel == 1 &&
2161       Style.Language == FormatStyle::LK_Proto)
2162     // Don't put enums onto single lines in protocol buffers.
2163     return true;
2164   if (Right.is(TT_InlineASMBrace))
2165     return Right.HasUnescapedNewline;
2166   if (isAllmanBrace(Left) || isAllmanBrace(Right))
2167     return (Line.startsWith(tok::kw_enum) && Style.BraceWrapping.AfterEnum) ||
2168            (Line.startsWith(tok::kw_class) && Style.BraceWrapping.AfterClass) ||
2169            (Line.startsWith(tok::kw_struct) && Style.BraceWrapping.AfterStruct);
2170   if (Style.Language == FormatStyle::LK_Proto && Left.isNot(tok::l_brace) &&
2171       Right.is(TT_SelectorName))
2172     return true;
2173   if (Left.is(TT_ObjCBlockLBrace) && !Style.AllowShortBlocksOnASingleLine)
2174     return true;
2175
2176   if ((Style.Language == FormatStyle::LK_Java ||
2177        Style.Language == FormatStyle::LK_JavaScript) &&
2178       Left.is(TT_LeadingJavaAnnotation) &&
2179       Right.isNot(TT_LeadingJavaAnnotation) && Right.isNot(tok::l_paren) &&
2180       (Line.Last->is(tok::l_brace) || Style.BreakAfterJavaFieldAnnotations))
2181     return true;
2182
2183   return false;
2184 }
2185
2186 bool TokenAnnotator::canBreakBefore(const AnnotatedLine &Line,
2187                                     const FormatToken &Right) {
2188   const FormatToken &Left = *Right.Previous;
2189
2190   // Language-specific stuff.
2191   if (Style.Language == FormatStyle::LK_Java) {
2192     if (Left.isOneOf(Keywords.kw_throws, Keywords.kw_extends,
2193                      Keywords.kw_implements))
2194       return false;
2195     if (Right.isOneOf(Keywords.kw_throws, Keywords.kw_extends,
2196                       Keywords.kw_implements))
2197       return true;
2198   } else if (Style.Language == FormatStyle::LK_JavaScript) {
2199     if (Left.is(TT_JsFatArrow) && Right.is(tok::l_brace))
2200       return false;
2201     if (Left.is(TT_JsTypeColon))
2202       return true;
2203   }
2204
2205   if (Left.is(tok::at))
2206     return false;
2207   if (Left.Tok.getObjCKeywordID() == tok::objc_interface)
2208     return false;
2209   if (Left.isOneOf(TT_JavaAnnotation, TT_LeadingJavaAnnotation))
2210     return !Right.is(tok::l_paren);
2211   if (Right.is(TT_PointerOrReference))
2212     return Line.IsMultiVariableDeclStmt ||
2213            (Style.PointerAlignment == FormatStyle::PAS_Right &&
2214             (!Right.Next || Right.Next->isNot(TT_FunctionDeclarationName)));
2215   if (Right.isOneOf(TT_StartOfName, TT_FunctionDeclarationName) ||
2216       Right.is(tok::kw_operator))
2217     return true;
2218   if (Left.is(TT_PointerOrReference))
2219     return false;
2220   if (Right.isTrailingComment())
2221     // We rely on MustBreakBefore being set correctly here as we should not
2222     // change the "binding" behavior of a comment.
2223     // The first comment in a braced lists is always interpreted as belonging to
2224     // the first list element. Otherwise, it should be placed outside of the
2225     // list.
2226     return Left.BlockKind == BK_BracedInit;
2227   if (Left.is(tok::question) && Right.is(tok::colon))
2228     return false;
2229   if (Right.is(TT_ConditionalExpr) || Right.is(tok::question))
2230     return Style.BreakBeforeTernaryOperators;
2231   if (Left.is(TT_ConditionalExpr) || Left.is(tok::question))
2232     return !Style.BreakBeforeTernaryOperators;
2233   if (Right.is(TT_InheritanceColon))
2234     return true;
2235   if (Right.is(tok::colon) &&
2236       !Right.isOneOf(TT_CtorInitializerColon, TT_InlineASMColon))
2237     return false;
2238   if (Left.is(tok::colon) && (Left.isOneOf(TT_DictLiteral, TT_ObjCMethodExpr)))
2239     return true;
2240   if (Right.is(TT_SelectorName) || (Right.is(tok::identifier) && Right.Next &&
2241                                     Right.Next->is(TT_ObjCMethodExpr)))
2242     return Left.isNot(tok::period); // FIXME: Properly parse ObjC calls.
2243   if (Left.is(tok::r_paren) && Line.Type == LT_ObjCProperty)
2244     return true;
2245   if (Left.ClosesTemplateDeclaration || Left.is(TT_FunctionAnnotationRParen))
2246     return true;
2247   if (Right.isOneOf(TT_RangeBasedForLoopColon, TT_OverloadedOperatorLParen,
2248                     TT_OverloadedOperator))
2249     return false;
2250   if (Left.is(TT_RangeBasedForLoopColon))
2251     return true;
2252   if (Right.is(TT_RangeBasedForLoopColon))
2253     return false;
2254   if (Left.isOneOf(TT_TemplateCloser, TT_UnaryOperator) ||
2255       Left.is(tok::kw_operator))
2256     return false;
2257   if (Left.is(tok::equal) && !Right.isOneOf(tok::kw_default, tok::kw_delete) &&
2258       Line.Type == LT_VirtualFunctionDecl && Left.NestingLevel == 0)
2259     return false;
2260   if (Left.is(tok::l_paren) && Left.is(TT_AttributeParen))
2261     return false;
2262   if (Left.is(tok::l_paren) && Left.Previous &&
2263       (Left.Previous->isOneOf(TT_BinaryOperator, TT_CastRParen)))
2264     return false;
2265   if (Right.is(TT_ImplicitStringLiteral))
2266     return false;
2267
2268   if (Right.is(tok::r_paren) || Right.is(TT_TemplateCloser))
2269     return false;
2270   if (Right.is(tok::r_square) && Right.MatchingParen &&
2271       Right.MatchingParen->is(TT_LambdaLSquare))
2272     return false;
2273
2274   // We only break before r_brace if there was a corresponding break before
2275   // the l_brace, which is tracked by BreakBeforeClosingBrace.
2276   if (Right.is(tok::r_brace))
2277     return Right.MatchingParen && Right.MatchingParen->BlockKind == BK_Block;
2278
2279   // Allow breaking after a trailing annotation, e.g. after a method
2280   // declaration.
2281   if (Left.is(TT_TrailingAnnotation))
2282     return !Right.isOneOf(tok::l_brace, tok::semi, tok::equal, tok::l_paren,
2283                           tok::less, tok::coloncolon);
2284
2285   if (Right.is(tok::kw___attribute))
2286     return true;
2287
2288   if (Left.is(tok::identifier) && Right.is(tok::string_literal))
2289     return true;
2290
2291   if (Right.is(tok::identifier) && Right.Next && Right.Next->is(TT_DictLiteral))
2292     return true;
2293
2294   if (Left.is(TT_CtorInitializerComma) &&
2295       Style.BreakConstructorInitializersBeforeComma)
2296     return false;
2297   if (Right.is(TT_CtorInitializerComma) &&
2298       Style.BreakConstructorInitializersBeforeComma)
2299     return true;
2300   if ((Left.is(tok::greater) && Right.is(tok::greater)) ||
2301       (Left.is(tok::less) && Right.is(tok::less)))
2302     return false;
2303   if (Right.is(TT_BinaryOperator) &&
2304       Style.BreakBeforeBinaryOperators != FormatStyle::BOS_None &&
2305       (Style.BreakBeforeBinaryOperators == FormatStyle::BOS_All ||
2306        Right.getPrecedence() != prec::Assignment))
2307     return true;
2308   if (Left.is(TT_ArrayInitializerLSquare))
2309     return true;
2310   if (Right.is(tok::kw_typename) && Left.isNot(tok::kw_const))
2311     return true;
2312   if ((Left.isBinaryOperator() || Left.is(TT_BinaryOperator)) &&
2313       !Left.isOneOf(tok::arrowstar, tok::lessless) &&
2314       Style.BreakBeforeBinaryOperators != FormatStyle::BOS_All &&
2315       (Style.BreakBeforeBinaryOperators == FormatStyle::BOS_None ||
2316        Left.getPrecedence() == prec::Assignment))
2317     return true;
2318   return Left.isOneOf(tok::comma, tok::coloncolon, tok::semi, tok::l_brace,
2319                       tok::kw_class, tok::kw_struct) ||
2320          Right.isMemberAccess() ||
2321          Right.isOneOf(TT_TrailingReturnArrow, TT_LambdaArrow, tok::lessless,
2322                        tok::colon, tok::l_square, tok::at) ||
2323          (Left.is(tok::r_paren) &&
2324           Right.isOneOf(tok::identifier, tok::kw_const)) ||
2325          (Left.is(tok::l_paren) && !Right.is(tok::r_paren));
2326 }
2327
2328 void TokenAnnotator::printDebugInfo(const AnnotatedLine &Line) {
2329   llvm::errs() << "AnnotatedTokens:\n";
2330   const FormatToken *Tok = Line.First;
2331   while (Tok) {
2332     llvm::errs() << " M=" << Tok->MustBreakBefore
2333                  << " C=" << Tok->CanBreakBefore
2334                  << " T=" << getTokenTypeName(Tok->Type)
2335                  << " S=" << Tok->SpacesRequiredBefore
2336                  << " B=" << Tok->BlockParameterCount
2337                  << " P=" << Tok->SplitPenalty << " Name=" << Tok->Tok.getName()
2338                  << " L=" << Tok->TotalLength << " PPK=" << Tok->PackingKind
2339                  << " FakeLParens=";
2340     for (unsigned i = 0, e = Tok->FakeLParens.size(); i != e; ++i)
2341       llvm::errs() << Tok->FakeLParens[i] << "/";
2342     llvm::errs() << " FakeRParens=" << Tok->FakeRParens << "\n";
2343     if (!Tok->Next)
2344       assert(Tok == Line.Last);
2345     Tok = Tok->Next;
2346   }
2347   llvm::errs() << "----\n";
2348 }
2349
2350 } // namespace format
2351 } // namespace clang