contrib/llvm/tools/clang/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/Support/Debug.h"
  19
  20 #define DEBUG_TYPE "format-token-annotator"
  21
  22 namespace clang {
  23 namespace format {
  24
  25 namespace {
  26
  27 /// \brief A parser that gathers additional information about tokens.
  28 ///
  29 /// The \c TokenAnnotator tries to match parenthesis and square brakets and
  30 /// store a parenthesis levels. It also tries to resolve matching "<" and ">"
  31 /// into template parameter lists.
  32 class AnnotatingParser {
  33 public:
  34   AnnotatingParser(const FormatStyle &Style, AnnotatedLine &Line,
  35                    IdentifierInfo &Ident_in)
  36       : Style(Style), Line(Line), CurrentToken(Line.First),
  37         KeywordVirtualFound(false), AutoFound(false), Ident_in(Ident_in) {
  38     Contexts.push_back(Context(tok::unknown, 1, /*IsExpression=*/false));
  39     resetTokenMetadata(CurrentToken);
  40   }
  41
  42 private:
  43   bool parseAngle() {
  44     if (!CurrentToken)
  45       return false;
  46     ScopedContextCreator ContextCreator(*this, tok::less, 10);
  47     FormatToken *Left = CurrentToken->Previous;
  48     Contexts.back().IsExpression = false;
  49     // If there's a template keyword before the opening angle bracket, this is a
  50     // template parameter, not an argument.
  51     Contexts.back().InTemplateArgument =
  52         Left->Previous && Left->Previous->Tok.isNot(tok::kw_template);
  53
  54     while (CurrentToken) {
  55       if (CurrentToken->is(tok::greater)) {
  56         Left->MatchingParen = CurrentToken;
  57         CurrentToken->MatchingParen = Left;
  58         CurrentToken->Type = TT_TemplateCloser;
  59         next();
  60         return true;
  61       }
  62       if (CurrentToken->isOneOf(tok::r_paren, tok::r_square, tok::r_brace,
  63                                 tok::question, tok::colon))
  64         return false;
  65       // If a && or || is found and interpreted as a binary operator, this set
  66       // of angles is likely part of something like "a < b && c > d". If the
  67       // angles are inside an expression, the ||/&& might also be a binary
  68       // operator that was misinterpreted because we are parsing template
  69       // parameters.
  70       // FIXME: This is getting out of hand, write a decent parser.
  71       if (CurrentToken->Previous->isOneOf(tok::pipepipe, tok::ampamp) &&
  72           ((CurrentToken->Previous->Type == TT_BinaryOperator &&
  73             // Toplevel bool expressions do not make lots of sense;
  74             // If we're on the top level, it contains only the base context and
  75             // the context for the current opening angle bracket.
  76             Contexts.size() > 2) ||
  77            Contexts[Contexts.size() - 2].IsExpression) &&
  78           Line.First->isNot(tok::kw_template))
  79         return false;
  80       updateParameterCount(Left, CurrentToken);
  81       if (!consumeToken())
  82         return false;
  83     }
  84     return false;
  85   }
  86
  87   bool parseParens(bool LookForDecls = false) {
  88     if (!CurrentToken)
  89       return false;
  90     ScopedContextCreator ContextCreator(*this, tok::l_paren, 1);
  91
  92     // FIXME: This is a bit of a hack. Do better.
  93     Contexts.back().ColonIsForRangeExpr =
  94         Contexts.size() == 2 && Contexts[0].ColonIsForRangeExpr;
  95
  96     bool StartsObjCMethodExpr = false;
  97     FormatToken *Left = CurrentToken->Previous;
  98     if (CurrentToken->is(tok::caret)) {
  99       // (^ can start a block type.
 100       Left->Type = TT_ObjCBlockLParen;
 101     } else if (FormatToken *MaybeSel = Left->Previous) {
 102       // @selector( starts a selector.
 103       if (MaybeSel->isObjCAtKeyword(tok::objc_selector) && MaybeSel->Previous &&
 104           MaybeSel->Previous->is(tok::at)) {
 105         StartsObjCMethodExpr = true;
 106       }
 107     }
 108
 109     if (Left->Previous &&
 110         (Left->Previous->isOneOf(tok::kw_static_assert, tok::kw_if,
 111                                  tok::kw_while, tok::l_paren, tok::comma) ||
 112          Left->Previous->Type == TT_BinaryOperator)) {
 113       // static_assert, if and while usually contain expressions.
 114       Contexts.back().IsExpression = true;
 115     } else if (Line.InPPDirective &&
 116                (!Left->Previous ||
 117                 (Left->Previous->isNot(tok::identifier) &&
 118                  Left->Previous->Type != TT_OverloadedOperator))) {
 119       Contexts.back().IsExpression = true;
 120     } else if (Left->Previous && Left->Previous->is(tok::r_square) &&
 121                Left->Previous->MatchingParen &&
 122                Left->Previous->MatchingParen->Type == TT_LambdaLSquare) {
 123       // This is a parameter list of a lambda expression.
 124       Contexts.back().IsExpression = false;
 125     } else if (Contexts[Contexts.size() - 2].CaretFound) {
 126       // This is the parameter list of an ObjC block.
 127       Contexts.back().IsExpression = false;
 128     } else if (Left->Previous && Left->Previous->is(tok::kw___attribute)) {
 129       Left->Type = TT_AttributeParen;
 130     } else if (Left->Previous && Left->Previous->IsForEachMacro) {
 131       // The first argument to a foreach macro is a declaration.
 132       Contexts.back().IsForEachMacro = true;
 133       Contexts.back().IsExpression = false;
 134     }
 135
 136     if (StartsObjCMethodExpr) {
 137       Contexts.back().ColonIsObjCMethodExpr = true;
 138       Left->Type = TT_ObjCMethodExpr;
 139     }
 140
 141     bool MightBeFunctionType = CurrentToken->is(tok::star);
 142     bool HasMultipleLines = false;
 143     bool HasMultipleParametersOnALine = false;
 144     while (CurrentToken) {
 145       // LookForDecls is set when "if (" has been seen. Check for
 146       // 'identifier' '*' 'identifier' followed by not '=' -- this
 147       // '*' has to be a binary operator but determineStarAmpUsage() will
 148       // categorize it as an unary operator, so set the right type here.
 149       if (LookForDecls && CurrentToken->Next) {
 150         FormatToken *Prev = CurrentToken->getPreviousNonComment();
 151         if (Prev) {
 152           FormatToken *PrevPrev = Prev->getPreviousNonComment();
 153           FormatToken *Next = CurrentToken->Next;
 154           if (PrevPrev && PrevPrev->is(tok::identifier) &&
 155               Prev->isOneOf(tok::star, tok::amp, tok::ampamp) &&
 156               CurrentToken->is(tok::identifier) && Next->isNot(tok::equal)) {
 157             Prev->Type = TT_BinaryOperator;
 158             LookForDecls = false;
 159           }
 160         }
 161       }
 162
 163       if (CurrentToken->Previous->Type == TT_PointerOrReference &&
 164           CurrentToken->Previous->Previous->isOneOf(tok::l_paren,
 165                                                     tok::coloncolon))
 166         MightBeFunctionType = true;
 167       if (CurrentToken->Previous->Type == TT_BinaryOperator)
 168         Contexts.back().IsExpression = true;
 169       if (CurrentToken->is(tok::r_paren)) {
 170         if (MightBeFunctionType && CurrentToken->Next &&
 171             (CurrentToken->Next->is(tok::l_paren) ||
 172              (CurrentToken->Next->is(tok::l_square) &&
 173               !Contexts.back().IsExpression)))
 174           Left->Type = TT_FunctionTypeLParen;
 175         Left->MatchingParen = CurrentToken;
 176         CurrentToken->MatchingParen = Left;
 177
 178         if (StartsObjCMethodExpr) {
 179           CurrentToken->Type = TT_ObjCMethodExpr;
 180           if (Contexts.back().FirstObjCSelectorName) {
 181             Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName =
 182                 Contexts.back().LongestObjCSelectorName;
 183           }
 184         }
 185
 186         if (Left->Type == TT_AttributeParen)
 187           CurrentToken->Type = TT_AttributeParen;
 188
 189         if (!HasMultipleLines)
 190           Left->PackingKind = PPK_Inconclusive;
 191         else if (HasMultipleParametersOnALine)
 192           Left->PackingKind = PPK_BinPacked;
 193         else
 194           Left->PackingKind = PPK_OnePerLine;
 195
 196         next();
 197         return true;
 198       }
 199       if (CurrentToken->isOneOf(tok::r_square, tok::r_brace))
 200         return false;
 201       else if (CurrentToken->is(tok::l_brace))
 202         Left->Type = TT_Unknown; // Not TT_ObjCBlockLParen
 203       if (CurrentToken->is(tok::comma) && CurrentToken->Next &&
 204           !CurrentToken->Next->HasUnescapedNewline &&
 205           !CurrentToken->Next->isTrailingComment())
 206         HasMultipleParametersOnALine = true;
 207       if (CurrentToken->isOneOf(tok::kw_const, tok::kw_auto) ||
 208           CurrentToken->isSimpleTypeSpecifier())
 209         Contexts.back().IsExpression = false;
 210       FormatToken *Tok = CurrentToken;
 211       if (!consumeToken())
 212         return false;
 213       updateParameterCount(Left, Tok);
 214       if (CurrentToken && CurrentToken->HasUnescapedNewline)
 215         HasMultipleLines = true;
 216     }
 217     return false;
 218   }
 219
 220   bool parseSquare() {
 221     if (!CurrentToken)
 222       return false;
 223
 224     // A '[' could be an index subscript (after an identifier or after
 225     // ')' or ']'), it could be the start of an Objective-C method
 226     // expression, or it could the the start of an Objective-C array literal.
 227     FormatToken *Left = CurrentToken->Previous;
 228     FormatToken *Parent = Left->getPreviousNonComment();
 229     bool StartsObjCMethodExpr =
 230         Contexts.back().CanBeExpression && Left->Type != TT_LambdaLSquare &&
 231         CurrentToken->isNot(tok::l_brace) &&
 232         (!Parent || Parent->isOneOf(tok::colon, tok::l_square, tok::l_paren,
 233                                     tok::kw_return, tok::kw_throw) ||
 234          Parent->isUnaryOperator() || Parent->Type == TT_ObjCForIn ||
 235          Parent->Type == TT_CastRParen ||
 236          getBinOpPrecedence(Parent->Tok.getKind(), true, true) > prec::Unknown);
 237     ScopedContextCreator ContextCreator(*this, tok::l_square, 10);
 238     Contexts.back().IsExpression = true;
 239     bool ColonFound = false;
 240
 241     if (StartsObjCMethodExpr) {
 242       Contexts.back().ColonIsObjCMethodExpr = true;
 243       Left->Type = TT_ObjCMethodExpr;
 244     } else if (Parent && Parent->is(tok::at)) {
 245       Left->Type = TT_ArrayInitializerLSquare;
 246     } else if (Left->Type == TT_Unknown) {
 247       Left->Type = TT_ArraySubscriptLSquare;
 248     }
 249
 250     while (CurrentToken) {
 251       if (CurrentToken->is(tok::r_square)) {
 252         if (CurrentToken->Next && CurrentToken->Next->is(tok::l_paren) &&
 253             Left->Type == TT_ObjCMethodExpr) {
 254           // An ObjC method call is rarely followed by an open parenthesis.
 255           // FIXME: Do we incorrectly label ":" with this?
 256           StartsObjCMethodExpr = false;
 257           Left->Type = TT_Unknown;
 258         }
 259         if (StartsObjCMethodExpr && CurrentToken->Previous != Left) {
 260           CurrentToken->Type = TT_ObjCMethodExpr;
 261           // determineStarAmpUsage() thinks that '*' '[' is allocating an
 262           // array of pointers, but if '[' starts a selector then '*' is a
 263           // binary operator.
 264           if (Parent && Parent->Type == TT_PointerOrReference)
 265             Parent->Type = TT_BinaryOperator;
 266         }
 267         Left->MatchingParen = CurrentToken;
 268         CurrentToken->MatchingParen = Left;
 269         if (Contexts.back().FirstObjCSelectorName) {
 270           Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName =
 271               Contexts.back().LongestObjCSelectorName;
 272           if (Left->BlockParameterCount > 1)
 273             Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName = 0;
 274         }
 275         next();
 276         return true;
 277       }
 278       if (CurrentToken->isOneOf(tok::r_paren, tok::r_brace))
 279         return false;
 280       if (CurrentToken->is(tok::colon))
 281         ColonFound = true;
 282       if (CurrentToken->is(tok::comma) &&
 283           Style.Language != FormatStyle::LK_Proto &&
 284           (Left->Type == TT_ArraySubscriptLSquare ||
 285            (Left->Type == TT_ObjCMethodExpr && !ColonFound)))
 286         Left->Type = TT_ArrayInitializerLSquare;
 287       FormatToken* Tok = CurrentToken;
 288       if (!consumeToken())
 289         return false;
 290       updateParameterCount(Left, Tok);
 291     }
 292     return false;
 293   }
 294
 295   bool parseBrace() {
 296     if (CurrentToken) {
 297       FormatToken *Left = CurrentToken->Previous;
 298
 299       if (Contexts.back().CaretFound)
 300         Left->Type = TT_ObjCBlockLBrace;
 301       Contexts.back().CaretFound = false;
 302
 303       ScopedContextCreator ContextCreator(*this, tok::l_brace, 1);
 304       Contexts.back().ColonIsDictLiteral = true;
 305       if (Left->BlockKind == BK_BracedInit)
 306         Contexts.back().IsExpression = true;
 307
 308       while (CurrentToken) {
 309         if (CurrentToken->is(tok::r_brace)) {
 310           Left->MatchingParen = CurrentToken;
 311           CurrentToken->MatchingParen = Left;
 312           next();
 313           return true;
 314         }
 315         if (CurrentToken->isOneOf(tok::r_paren, tok::r_square))
 316           return false;
 317         updateParameterCount(Left, CurrentToken);
 318         if (CurrentToken->is(tok::colon) &&
 319             Style.Language != FormatStyle::LK_Proto) {
 320           if (CurrentToken->getPreviousNonComment()->is(tok::identifier))
 321             CurrentToken->getPreviousNonComment()->Type = TT_SelectorName;
 322           Left->Type = TT_DictLiteral;
 323         }
 324         if (!consumeToken())
 325           return false;
 326       }
 327     }
 328     return true;
 329   }
 330
 331   void updateParameterCount(FormatToken *Left, FormatToken *Current) {
 332     if (Current->Type == TT_LambdaLSquare ||
 333         (Current->is(tok::caret) && Current->Type == TT_UnaryOperator) ||
 334         (Style.Language == FormatStyle::LK_JavaScript &&
 335          Current->TokenText == "function")) {
 336       ++Left->BlockParameterCount;
 337     }
 338     if (Current->is(tok::comma)) {
 339       ++Left->ParameterCount;
 340       if (!Left->Role)
 341         Left->Role.reset(new CommaSeparatedList(Style));
 342       Left->Role->CommaFound(Current);
 343     } else if (Left->ParameterCount == 0 && Current->isNot(tok::comment)) {
 344       Left->ParameterCount = 1;
 345     }
 346   }
 347
 348   bool parseConditional() {
 349     while (CurrentToken) {
 350       if (CurrentToken->is(tok::colon)) {
 351         CurrentToken->Type = TT_ConditionalExpr;
 352         next();
 353         return true;
 354       }
 355       if (!consumeToken())
 356         return false;
 357     }
 358     return false;
 359   }
 360
 361   bool parseTemplateDeclaration() {
 362     if (CurrentToken && CurrentToken->is(tok::less)) {
 363       CurrentToken->Type = TT_TemplateOpener;
 364       next();
 365       if (!parseAngle())
 366         return false;
 367       if (CurrentToken)
 368         CurrentToken->Previous->ClosesTemplateDeclaration = true;
 369       return true;
 370     }
 371     return false;
 372   }
 373
 374   bool consumeToken() {
 375     FormatToken *Tok = CurrentToken;
 376     next();
 377     switch (Tok->Tok.getKind()) {
 378     case tok::plus:
 379     case tok::minus:
 380       if (!Tok->Previous && Line.MustBeDeclaration)
 381         Tok->Type = TT_ObjCMethodSpecifier;
 382       break;
 383     case tok::colon:
 384       if (!Tok->Previous)
 385         return false;
 386       // Colons from ?: are handled in parseConditional().
 387       if (Tok->Previous->is(tok::r_paren) && Contexts.size() == 1 &&
 388           Line.First->isNot(tok::kw_case)) {
 389         Tok->Type = TT_CtorInitializerColon;
 390       } else if (Contexts.back().ColonIsDictLiteral) {
 391         Tok->Type = TT_DictLiteral;
 392       } else if (Contexts.back().ColonIsObjCMethodExpr ||
 393                  Line.First->Type == TT_ObjCMethodSpecifier) {
 394         Tok->Type = TT_ObjCMethodExpr;
 395         Tok->Previous->Type = TT_SelectorName;
 396         if (Tok->Previous->ColumnWidth >
 397             Contexts.back().LongestObjCSelectorName) {
 398           Contexts.back().LongestObjCSelectorName = Tok->Previous->ColumnWidth;
 399         }
 400         if (!Contexts.back().FirstObjCSelectorName)
 401           Contexts.back().FirstObjCSelectorName = Tok->Previous;
 402       } else if (Contexts.back().ColonIsForRangeExpr) {
 403         Tok->Type = TT_RangeBasedForLoopColon;
 404       } else if (CurrentToken && CurrentToken->is(tok::numeric_constant)) {
 405         Tok->Type = TT_BitFieldColon;
 406       } else if (Contexts.size() == 1 &&
 407                  !Line.First->isOneOf(tok::kw_enum, tok::kw_case)) {
 408         Tok->Type = TT_InheritanceColon;
 409       } else if (Contexts.back().ContextKind == tok::l_paren) {
 410         Tok->Type = TT_InlineASMColon;
 411       }
 412       break;
 413     case tok::kw_if:
 414     case tok::kw_while:
 415       if (CurrentToken && CurrentToken->is(tok::l_paren)) {
 416         next();
 417         if (!parseParens(/*LookForDecls=*/true))
 418           return false;
 419       }
 420       break;
 421     case tok::kw_for:
 422       Contexts.back().ColonIsForRangeExpr = true;
 423       next();
 424       if (!parseParens())
 425         return false;
 426       break;
 427     case tok::l_paren:
 428       if (!parseParens())
 429         return false;
 430       if (Line.MustBeDeclaration && Contexts.size() == 1 &&
 431           !Contexts.back().IsExpression &&
 432           Line.First->Type != TT_ObjCProperty &&
 433           (!Tok->Previous || Tok->Previous->isNot(tok::kw_decltype)))
 434         Line.MightBeFunctionDecl = true;
 435       break;
 436     case tok::l_square:
 437       if (!parseSquare())
 438         return false;
 439       break;
 440     case tok::l_brace:
 441       if (!parseBrace())
 442         return false;
 443       break;
 444     case tok::less:
 445       if (Tok->Previous && !Tok->Previous->Tok.isLiteral() && parseAngle())
 446         Tok->Type = TT_TemplateOpener;
 447       else {
 448         Tok->Type = TT_BinaryOperator;
 449         CurrentToken = Tok;
 450         next();
 451       }
 452       break;
 453     case tok::r_paren:
 454     case tok::r_square:
 455       return false;
 456     case tok::r_brace:
 457       // Lines can start with '}'.
 458       if (Tok->Previous)
 459         return false;
 460       break;
 461     case tok::greater:
 462       Tok->Type = TT_BinaryOperator;
 463       break;
 464     case tok::kw_operator:
 465       while (CurrentToken &&
 466              !CurrentToken->isOneOf(tok::l_paren, tok::semi, tok::r_paren)) {
 467         if (CurrentToken->isOneOf(tok::star, tok::amp))
 468           CurrentToken->Type = TT_PointerOrReference;
 469         consumeToken();
 470         if (CurrentToken && CurrentToken->Previous->Type == TT_BinaryOperator)
 471           CurrentToken->Previous->Type = TT_OverloadedOperator;
 472       }
 473       if (CurrentToken) {
 474         CurrentToken->Type = TT_OverloadedOperatorLParen;
 475         if (CurrentToken->Previous->Type == TT_BinaryOperator)
 476           CurrentToken->Previous->Type = TT_OverloadedOperator;
 477       }
 478       break;
 479     case tok::question:
 480       parseConditional();
 481       break;
 482     case tok::kw_template:
 483       parseTemplateDeclaration();
 484       break;
 485     case tok::identifier:
 486       if (Line.First->is(tok::kw_for) &&
 487           Tok->Tok.getIdentifierInfo() == &Ident_in)
 488         Tok->Type = TT_ObjCForIn;
 489       break;
 490     case tok::comma:
 491       if (Contexts.back().FirstStartOfName)
 492         Contexts.back().FirstStartOfName->PartOfMultiVariableDeclStmt = true;
 493       if (Contexts.back().InCtorInitializer)
 494         Tok->Type = TT_CtorInitializerComma;
 495       if (Contexts.back().IsForEachMacro)
 496         Contexts.back().IsExpression = true;
 497       break;
 498     default:
 499       break;
 500     }
 501     return true;
 502   }
 503
 504   void parseIncludeDirective() {
 505     next();
 506     if (CurrentToken && CurrentToken->is(tok::less)) {
 507       next();
 508       while (CurrentToken) {
 509         if (CurrentToken->isNot(tok::comment) || CurrentToken->Next)
 510           CurrentToken->Type = TT_ImplicitStringLiteral;
 511         next();
 512       }
 513     } else {
 514       while (CurrentToken) {
 515         if (CurrentToken->is(tok::string_literal))
 516           // Mark these string literals as "implicit" literals, too, so that
 517           // they are not split or line-wrapped.
 518           CurrentToken->Type = TT_ImplicitStringLiteral;
 519         next();
 520       }
 521     }
 522   }
 523
 524   void parseWarningOrError() {
 525     next();
 526     // We still want to format the whitespace left of the first token of the
 527     // warning or error.
 528     next();
 529     while (CurrentToken) {
 530       CurrentToken->Type = TT_ImplicitStringLiteral;
 531       next();
 532     }
 533   }
 534
 535   void parsePragma() {
 536     next(); // Consume "pragma".
 537     if (CurrentToken && CurrentToken->TokenText == "mark") {
 538       next(); // Consume "mark".
 539       next(); // Consume first token (so we fix leading whitespace).
 540       while (CurrentToken) {
 541         CurrentToken->Type = TT_ImplicitStringLiteral;
 542         next();
 543       }
 544     }
 545   }
 546
 547   void parsePreprocessorDirective() {
 548     next();
 549     if (!CurrentToken)
 550       return;
 551     if (CurrentToken->Tok.is(tok::numeric_constant)) {
 552       CurrentToken->SpacesRequiredBefore = 1;
 553       return;
 554     }
 555     // Hashes in the middle of a line can lead to any strange token
 556     // sequence.
 557     if (!CurrentToken->Tok.getIdentifierInfo())
 558       return;
 559     switch (CurrentToken->Tok.getIdentifierInfo()->getPPKeywordID()) {
 560     case tok::pp_include:
 561     case tok::pp_import:
 562       parseIncludeDirective();
 563       break;
 564     case tok::pp_error:
 565     case tok::pp_warning:
 566       parseWarningOrError();
 567       break;
 568     case tok::pp_pragma:
 569       parsePragma();
 570       break;
 571     case tok::pp_if:
 572     case tok::pp_elif:
 573       Contexts.back().IsExpression = true;
 574       parseLine();
 575       break;
 576     default:
 577       break;
 578     }
 579     while (CurrentToken)
 580       next();
 581   }
 582
 583 public:
 584   LineType parseLine() {
 585     if (CurrentToken->is(tok::hash)) {
 586       parsePreprocessorDirective();
 587       return LT_PreprocessorDirective;
 588     }
 589
 590     // Directly allow to 'import <string-literal>' to support protocol buffer
 591     // definitions (code.google.com/p/protobuf) or missing "#" (either way we
 592     // should not break the line).
 593     IdentifierInfo *Info = CurrentToken->Tok.getIdentifierInfo();
 594     if (Info && Info->getPPKeywordID() == tok::pp_import &&
 595         CurrentToken->Next && CurrentToken->Next->is(tok::string_literal))
 596       parseIncludeDirective();
 597
 598     while (CurrentToken) {
 599       if (CurrentToken->is(tok::kw_virtual))
 600         KeywordVirtualFound = true;
 601       if (!consumeToken())
 602         return LT_Invalid;
 603     }
 604     if (KeywordVirtualFound)
 605       return LT_VirtualFunctionDecl;
 606
 607     if (Line.First->Type == TT_ObjCMethodSpecifier) {
 608       if (Contexts.back().FirstObjCSelectorName)
 609         Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName =
 610             Contexts.back().LongestObjCSelectorName;
 611       return LT_ObjCMethodDecl;
 612     }
 613
 614     return LT_Other;
 615   }
 616
 617 private:
 618   void resetTokenMetadata(FormatToken *Token) {
 619     if (!Token)
 620       return;
 621
 622     // Reset token type in case we have already looked at it and then
 623     // recovered from an error (e.g. failure to find the matching >).
 624     if (CurrentToken->Type != TT_LambdaLSquare &&
 625         CurrentToken->Type != TT_FunctionLBrace &&
 626         CurrentToken->Type != TT_ImplicitStringLiteral &&
 627         CurrentToken->Type != TT_RegexLiteral &&
 628         CurrentToken->Type != TT_TrailingReturnArrow)
 629       CurrentToken->Type = TT_Unknown;
 630     CurrentToken->Role.reset();
 631     CurrentToken->FakeLParens.clear();
 632     CurrentToken->FakeRParens = 0;
 633   }
 634
 635   void next() {
 636     if (CurrentToken) {
 637       determineTokenType(*CurrentToken);
 638       CurrentToken->BindingStrength = Contexts.back().BindingStrength;
 639       CurrentToken->NestingLevel = Contexts.size() - 1;
 640       CurrentToken = CurrentToken->Next;
 641     }
 642
 643     resetTokenMetadata(CurrentToken);
 644   }
 645
 646   /// \brief A struct to hold information valid in a specific context, e.g.
 647   /// a pair of parenthesis.
 648   struct Context {
 649     Context(tok::TokenKind ContextKind, unsigned BindingStrength,
 650             bool IsExpression)
 651         : ContextKind(ContextKind), BindingStrength(BindingStrength),
 652           LongestObjCSelectorName(0), ColonIsForRangeExpr(false),
 653           ColonIsDictLiteral(false), ColonIsObjCMethodExpr(false),
 654           FirstObjCSelectorName(nullptr), FirstStartOfName(nullptr),
 655           IsExpression(IsExpression), CanBeExpression(true),
 656           InTemplateArgument(false), InCtorInitializer(false),
 657           CaretFound(false), IsForEachMacro(false) {}
 658
 659     tok::TokenKind ContextKind;
 660     unsigned BindingStrength;
 661     unsigned LongestObjCSelectorName;
 662     bool ColonIsForRangeExpr;
 663     bool ColonIsDictLiteral;
 664     bool ColonIsObjCMethodExpr;
 665     FormatToken *FirstObjCSelectorName;
 666     FormatToken *FirstStartOfName;
 667     bool IsExpression;
 668     bool CanBeExpression;
 669     bool InTemplateArgument;
 670     bool InCtorInitializer;
 671     bool CaretFound;
 672     bool IsForEachMacro;
 673   };
 674
 675   /// \brief Puts a new \c Context onto the stack \c Contexts for the lifetime
 676   /// of each instance.
 677   struct ScopedContextCreator {
 678     AnnotatingParser &P;
 679
 680     ScopedContextCreator(AnnotatingParser &P, tok::TokenKind ContextKind,
 681                          unsigned Increase)
 682         : P(P) {
 683       P.Contexts.push_back(Context(ContextKind,
 684                                    P.Contexts.back().BindingStrength + Increase,
 685                                    P.Contexts.back().IsExpression));
 686     }
 687
 688     ~ScopedContextCreator() { P.Contexts.pop_back(); }
 689   };
 690
 691   void determineTokenType(FormatToken &Current) {
 692     if (Current.getPrecedence() == prec::Assignment &&
 693         !Line.First->isOneOf(tok::kw_template, tok::kw_using) &&
 694         (!Current.Previous || Current.Previous->isNot(tok::kw_operator))) {
 695       Contexts.back().IsExpression = true;
 696       for (FormatToken *Previous = Current.Previous;
 697            Previous && !Previous->isOneOf(tok::comma, tok::semi);
 698            Previous = Previous->Previous) {
 699         if (Previous->isOneOf(tok::r_square, tok::r_paren))
 700           Previous = Previous->MatchingParen;
 701         if (Previous->Type == TT_BinaryOperator &&
 702             Previous->isOneOf(tok::star, tok::amp)) {
 703           Previous->Type = TT_PointerOrReference;
 704         }
 705       }
 706     } else if (Current.isOneOf(tok::kw_return, tok::kw_throw)) {
 707       Contexts.back().IsExpression = true;
 708     } else if (Current.is(tok::l_paren) && !Line.MustBeDeclaration &&
 709                !Line.InPPDirective &&
 710                (!Current.Previous ||
 711                 Current.Previous->isNot(tok::kw_decltype))) {
 712       bool ParametersOfFunctionType =
 713           Current.Previous && Current.Previous->is(tok::r_paren) &&
 714           Current.Previous->MatchingParen &&
 715           Current.Previous->MatchingParen->Type == TT_FunctionTypeLParen;
 716       bool IsForOrCatch = Current.Previous &&
 717                           Current.Previous->isOneOf(tok::kw_for, tok::kw_catch);
 718       Contexts.back().IsExpression = !ParametersOfFunctionType && !IsForOrCatch;
 719     } else if (Current.isOneOf(tok::r_paren, tok::greater, tok::comma)) {
 720       for (FormatToken *Previous = Current.Previous;
 721            Previous && Previous->isOneOf(tok::star, tok::amp);
 722            Previous = Previous->Previous)
 723         Previous->Type = TT_PointerOrReference;
 724     } else if (Current.Previous &&
 725                Current.Previous->Type == TT_CtorInitializerColon) {
 726       Contexts.back().IsExpression = true;
 727       Contexts.back().InCtorInitializer = true;
 728     } else if (Current.is(tok::kw_new)) {
 729       Contexts.back().CanBeExpression = false;
 730     } else if (Current.is(tok::semi) || Current.is(tok::exclaim)) {
 731       // This should be the condition or increment in a for-loop.
 732       Contexts.back().IsExpression = true;
 733     }
 734
 735     if (Current.Type == TT_Unknown) {
 736       // Line.MightBeFunctionDecl can only be true after the parentheses of a
 737       // function declaration have been found. In this case, 'Current' is a
 738       // trailing token of this declaration and thus cannot be a name.
 739       if (isStartOfName(Current) && !Line.MightBeFunctionDecl) {
 740         Contexts.back().FirstStartOfName = &Current;
 741         Current.Type = TT_StartOfName;
 742       } else if (Current.is(tok::kw_auto)) {
 743         AutoFound = true;
 744       } else if (Current.is(tok::arrow) && AutoFound &&
 745                  Line.MustBeDeclaration) {
 746         Current.Type = TT_TrailingReturnArrow;
 747       } else if (Current.isOneOf(tok::star, tok::amp, tok::ampamp)) {
 748         Current.Type =
 749             determineStarAmpUsage(Current, Contexts.back().CanBeExpression &&
 750                                                Contexts.back().IsExpression,
 751                                   Contexts.back().InTemplateArgument);
 752       } else if (Current.isOneOf(tok::minus, tok::plus, tok::caret)) {
 753         Current.Type = determinePlusMinusCaretUsage(Current);
 754         if (Current.Type == TT_UnaryOperator && Current.is(tok::caret))
 755           Contexts.back().CaretFound = true;
 756       } else if (Current.isOneOf(tok::minusminus, tok::plusplus)) {
 757         Current.Type = determineIncrementUsage(Current);
 758       } else if (Current.is(tok::exclaim)) {
 759         Current.Type = TT_UnaryOperator;
 760       } else if (Current.is(tok::question)) {
 761         Current.Type = TT_ConditionalExpr;
 762       } else if (Current.isBinaryOperator() &&
 763                  (!Current.Previous ||
 764                   Current.Previous->isNot(tok::l_square))) {
 765         Current.Type = TT_BinaryOperator;
 766       } else if (Current.is(tok::comment)) {
 767         if (Current.TokenText.startswith("//"))
 768           Current.Type = TT_LineComment;
 769         else
 770           Current.Type = TT_BlockComment;
 771       } else if (Current.is(tok::r_paren)) {
 772         if (rParenEndsCast(Current))
 773           Current.Type = TT_CastRParen;
 774       } else if (Current.is(tok::at) && Current.Next) {
 775         switch (Current.Next->Tok.getObjCKeywordID()) {
 776         case tok::objc_interface:
 777         case tok::objc_implementation:
 778         case tok::objc_protocol:
 779           Current.Type = TT_ObjCDecl;
 780           break;
 781         case tok::objc_property:
 782           Current.Type = TT_ObjCProperty;
 783           break;
 784         default:
 785           break;
 786         }
 787       } else if (Current.is(tok::period)) {
 788         FormatToken *PreviousNoComment = Current.getPreviousNonComment();
 789         if (PreviousNoComment &&
 790             PreviousNoComment->isOneOf(tok::comma, tok::l_brace))
 791           Current.Type = TT_DesignatedInitializerPeriod;
 792       } else if (Current.isOneOf(tok::identifier, tok::kw_const) &&
 793                  Current.Previous && Current.Previous->isNot(tok::equal) &&
 794                  Line.MightBeFunctionDecl && Contexts.size() == 1) {
 795         // Line.MightBeFunctionDecl can only be true after the parentheses of a
 796         // function declaration have been found.
 797         Current.Type = TT_TrailingAnnotation;
 798       }
 799     }
 800   }
 801
 802   /// \brief Take a guess at whether \p Tok starts a name of a function or
 803   /// variable declaration.
 804   ///
 805   /// This is a heuristic based on whether \p Tok is an identifier following
 806   /// something that is likely a type.
 807   bool isStartOfName(const FormatToken &Tok) {
 808     if (Tok.isNot(tok::identifier) || !Tok.Previous)
 809       return false;
 810
 811     // Skip "const" as it does not have an influence on whether this is a name.
 812     FormatToken *PreviousNotConst = Tok.Previous;
 813     while (PreviousNotConst && PreviousNotConst->is(tok::kw_const))
 814       PreviousNotConst = PreviousNotConst->Previous;
 815
 816     if (!PreviousNotConst)
 817       return false;
 818
 819     bool IsPPKeyword = PreviousNotConst->is(tok::identifier) &&
 820                        PreviousNotConst->Previous &&
 821                        PreviousNotConst->Previous->is(tok::hash);
 822
 823     if (PreviousNotConst->Type == TT_TemplateCloser)
 824       return PreviousNotConst && PreviousNotConst->MatchingParen &&
 825              PreviousNotConst->MatchingParen->Previous &&
 826              PreviousNotConst->MatchingParen->Previous->isNot(tok::kw_template);
 827
 828     if (PreviousNotConst->is(tok::r_paren) && PreviousNotConst->MatchingParen &&
 829         PreviousNotConst->MatchingParen->Previous &&
 830         PreviousNotConst->MatchingParen->Previous->is(tok::kw_decltype))
 831       return true;
 832
 833     return (!IsPPKeyword && PreviousNotConst->is(tok::identifier)) ||
 834            PreviousNotConst->Type == TT_PointerOrReference ||
 835            PreviousNotConst->isSimpleTypeSpecifier();
 836   }
 837
 838   /// \brief Determine whether ')' is ending a cast.
 839   bool rParenEndsCast(const FormatToken &Tok) {
 840     FormatToken *LeftOfParens = nullptr;
 841     if (Tok.MatchingParen)
 842       LeftOfParens = Tok.MatchingParen->getPreviousNonComment();
 843     if (LeftOfParens && LeftOfParens->is(tok::r_paren))
 844       return false;
 845     bool IsCast = false;
 846     bool ParensAreEmpty = Tok.Previous == Tok.MatchingParen;
 847     bool ParensAreType = !Tok.Previous ||
 848                          Tok.Previous->Type == TT_PointerOrReference ||
 849                          Tok.Previous->Type == TT_TemplateCloser ||
 850                          Tok.Previous->isSimpleTypeSpecifier();
 851     bool ParensCouldEndDecl =
 852         Tok.Next && Tok.Next->isOneOf(tok::equal, tok::semi, tok::l_brace);
 853     bool IsSizeOfOrAlignOf =
 854         LeftOfParens && LeftOfParens->isOneOf(tok::kw_sizeof, tok::kw_alignof);
 855     if (ParensAreType && !ParensCouldEndDecl && !IsSizeOfOrAlignOf &&
 856         ((Contexts.size() > 1 && Contexts[Contexts.size() - 2].IsExpression) ||
 857          (Tok.Next && Tok.Next->isBinaryOperator())))
 858       IsCast = true;
 859     else if (Tok.Next && Tok.Next->isNot(tok::string_literal) &&
 860              (Tok.Next->Tok.isLiteral() ||
 861               Tok.Next->isOneOf(tok::kw_sizeof, tok::kw_alignof)))
 862       IsCast = true;
 863     // If there is an identifier after the (), it is likely a cast, unless
 864     // there is also an identifier before the ().
 865     else if (LeftOfParens &&
 866              (LeftOfParens->Tok.getIdentifierInfo() == nullptr ||
 867               LeftOfParens->is(tok::kw_return)) &&
 868              LeftOfParens->Type != TT_OverloadedOperator &&
 869              LeftOfParens->isNot(tok::at) &&
 870              LeftOfParens->Type != TT_TemplateCloser && Tok.Next) {
 871       if (Tok.Next->isOneOf(tok::identifier, tok::numeric_constant)) {
 872         IsCast = true;
 873       } else {
 874         // Use heuristics to recognize c style casting.
 875         FormatToken *Prev = Tok.Previous;
 876         if (Prev && Prev->isOneOf(tok::amp, tok::star))
 877           Prev = Prev->Previous;
 878
 879         if (Prev && Tok.Next && Tok.Next->Next) {
 880           bool NextIsUnary = Tok.Next->isUnaryOperator() ||
 881                              Tok.Next->isOneOf(tok::amp, tok::star);
 882           IsCast = NextIsUnary && Tok.Next->Next->isOneOf(
 883                                       tok::identifier, tok::numeric_constant);
 884         }
 885
 886         for (; Prev != Tok.MatchingParen; Prev = Prev->Previous) {
 887           if (!Prev || !Prev->isOneOf(tok::kw_const, tok::identifier)) {
 888             IsCast = false;
 889             break;
 890           }
 891         }
 892       }
 893     }
 894     return IsCast && !ParensAreEmpty;
 895   }
 896
 897   /// \brief Return the type of the given token assuming it is * or &.
 898   TokenType determineStarAmpUsage(const FormatToken &Tok, bool IsExpression,
 899                                   bool InTemplateArgument) {
 900     const FormatToken *PrevToken = Tok.getPreviousNonComment();
 901     if (!PrevToken)
 902       return TT_UnaryOperator;
 903
 904     const FormatToken *NextToken = Tok.getNextNonComment();
 905     if (!NextToken || NextToken->is(tok::l_brace))
 906       return TT_Unknown;
 907
 908     if (PrevToken->is(tok::coloncolon) ||
 909         (PrevToken->is(tok::l_paren) && !IsExpression))
 910       return TT_PointerOrReference;
 911
 912     if (PrevToken->isOneOf(tok::l_paren, tok::l_square, tok::l_brace,
 913                            tok::comma, tok::semi, tok::kw_return, tok::colon,
 914                            tok::equal, tok::kw_delete, tok::kw_sizeof) ||
 915         PrevToken->Type == TT_BinaryOperator ||
 916         PrevToken->Type == TT_ConditionalExpr ||
 917         PrevToken->Type == TT_UnaryOperator || PrevToken->Type == TT_CastRParen)
 918       return TT_UnaryOperator;
 919
 920     if (NextToken->is(tok::l_square) && NextToken->Type != TT_LambdaLSquare)
 921       return TT_PointerOrReference;
 922     if (NextToken->is(tok::kw_operator))
 923       return TT_PointerOrReference;
 924
 925     if (PrevToken->is(tok::r_paren) && PrevToken->MatchingParen &&
 926         PrevToken->MatchingParen->Previous &&
 927         PrevToken->MatchingParen->Previous->isOneOf(tok::kw_typeof,
 928                                                     tok::kw_decltype))
 929       return TT_PointerOrReference;
 930
 931     if (PrevToken->Tok.isLiteral() ||
 932         PrevToken->isOneOf(tok::r_paren, tok::r_square, tok::kw_true,
 933                            tok::kw_false) ||
 934         NextToken->Tok.isLiteral() ||
 935         NextToken->isOneOf(tok::kw_true, tok::kw_false) ||
 936         NextToken->isUnaryOperator() ||
 937         // If we know we're in a template argument, there are no named
 938         // declarations. Thus, having an identifier on the right-hand side
 939         // indicates a binary operator.
 940         (InTemplateArgument && NextToken->Tok.isAnyIdentifier()))
 941       return TT_BinaryOperator;
 942
 943     // This catches some cases where evaluation order is used as control flow:
 944     //   aaa && aaa->f();
 945     const FormatToken *NextNextToken = NextToken->getNextNonComment();
 946     if (NextNextToken && NextNextToken->is(tok::arrow))
 947       return TT_BinaryOperator;
 948
 949     // It is very unlikely that we are going to find a pointer or reference type
 950     // definition on the RHS of an assignment.
 951     if (IsExpression)
 952       return TT_BinaryOperator;
 953
 954     return TT_PointerOrReference;
 955   }
 956
 957   TokenType determinePlusMinusCaretUsage(const FormatToken &Tok) {
 958     const FormatToken *PrevToken = Tok.getPreviousNonComment();
 959     if (!PrevToken || PrevToken->Type == TT_CastRParen)
 960       return TT_UnaryOperator;
 961
 962     // Use heuristics to recognize unary operators.
 963     if (PrevToken->isOneOf(tok::equal, tok::l_paren, tok::comma, tok::l_square,
 964                            tok::question, tok::colon, tok::kw_return,
 965                            tok::kw_case, tok::at, tok::l_brace))
 966       return TT_UnaryOperator;
 967
 968     // There can't be two consecutive binary operators.
 969     if (PrevToken->Type == TT_BinaryOperator)
 970       return TT_UnaryOperator;
 971
 972     // Fall back to marking the token as binary operator.
 973     return TT_BinaryOperator;
 974   }
 975
 976   /// \brief Determine whether ++/-- are pre- or post-increments/-decrements.
 977   TokenType determineIncrementUsage(const FormatToken &Tok) {
 978     const FormatToken *PrevToken = Tok.getPreviousNonComment();
 979     if (!PrevToken || PrevToken->Type == TT_CastRParen)
 980       return TT_UnaryOperator;
 981     if (PrevToken->isOneOf(tok::r_paren, tok::r_square, tok::identifier))
 982       return TT_TrailingUnaryOperator;
 983
 984     return TT_UnaryOperator;
 985   }
 986
 987   SmallVector<Context, 8> Contexts;
 988
 989   const FormatStyle &Style;
 990   AnnotatedLine &Line;
 991   FormatToken *CurrentToken;
 992   bool KeywordVirtualFound;
 993   bool AutoFound;
 994   IdentifierInfo &Ident_in;
 995 };
 996
 997 static int PrecedenceUnaryOperator = prec::PointerToMember + 1;
 998 static int PrecedenceArrowAndPeriod = prec::PointerToMember + 2;
 999
1000 /// \brief Parses binary expressions by inserting fake parenthesis based on
1001 /// operator precedence.
1002 class ExpressionParser {
1003 public:
1004   ExpressionParser(AnnotatedLine &Line) : Current(Line.First) {
1005     // Skip leading "}", e.g. in "} else if (...) {".
1006     if (Current->is(tok::r_brace))
1007       next();
1008   }
1009
1010   /// \brief Parse expressions with the given operatore precedence.
1011   void parse(int Precedence = 0) {
1012     // Skip 'return' and ObjC selector colons as they are not part of a binary
1013     // expression.
1014     while (Current &&
1015            (Current->is(tok::kw_return) ||
1016             (Current->is(tok::colon) && (Current->Type == TT_ObjCMethodExpr ||
1017                                          Current->Type == TT_DictLiteral))))
1018       next();
1019
1020     if (!Current || Precedence > PrecedenceArrowAndPeriod)
1021       return;
1022
1023     // Conditional expressions need to be parsed separately for proper nesting.
1024     if (Precedence == prec::Conditional) {
1025       parseConditionalExpr();
1026       return;
1027     }
1028
1029     // Parse unary operators, which all have a higher precedence than binary
1030     // operators.
1031     if (Precedence == PrecedenceUnaryOperator) {
1032       parseUnaryOperator();
1033       return;
1034     }
1035
1036     FormatToken *Start = Current;
1037     FormatToken *LatestOperator = nullptr;
1038     unsigned OperatorIndex = 0;
1039
1040     while (Current) {
1041       // Consume operators with higher precedence.
1042       parse(Precedence + 1);
1043
1044       int CurrentPrecedence = getCurrentPrecedence();
1045
1046       if (Current && Current->Type == TT_SelectorName &&
1047           Precedence == CurrentPrecedence) {
1048         if (LatestOperator)
1049           addFakeParenthesis(Start, prec::Level(Precedence));
1050         Start = Current;
1051       }
1052
1053       // At the end of the line or when an operator with higher precedence is
1054       // found, insert fake parenthesis and return.
1055       if (!Current || Current->closesScope() ||
1056           (CurrentPrecedence != -1 && CurrentPrecedence < Precedence)) {
1057         if (LatestOperator) {
1058           LatestOperator->LastOperator = true;
1059           if (Precedence == PrecedenceArrowAndPeriod) {
1060             // Call expressions don't have a binary operator precedence.
1061             addFakeParenthesis(Start, prec::Unknown);
1062           } else {
1063             addFakeParenthesis(Start, prec::Level(Precedence));
1064           }
1065         }
1066         return;
1067       }
1068
1069       // Consume scopes: (), [], <> and {}
1070       if (Current->opensScope()) {
1071         while (Current && !Current->closesScope()) {
1072           next();
1073           parse();
1074         }
1075         next();
1076       } else {
1077         // Operator found.
1078         if (CurrentPrecedence == Precedence) {
1079           LatestOperator = Current;
1080           Current->OperatorIndex = OperatorIndex;
1081           ++OperatorIndex;
1082         }
1083
1084         next();
1085       }
1086     }
1087   }
1088
1089 private:
1090   /// \brief Gets the precedence (+1) of the given token for binary operators
1091   /// and other tokens that we treat like binary operators.
1092   int getCurrentPrecedence() {
1093     if (Current) {
1094       if (Current->Type == TT_ConditionalExpr)
1095         return prec::Conditional;
1096       else if (Current->is(tok::semi) || Current->Type == TT_InlineASMColon ||
1097                Current->Type == TT_SelectorName)
1098         return 0;
1099       else if (Current->Type == TT_RangeBasedForLoopColon)
1100         return prec::Comma;
1101       else if (Current->Type == TT_BinaryOperator || Current->is(tok::comma))
1102         return Current->getPrecedence();
1103       else if (Current->isOneOf(tok::period, tok::arrow))
1104         return PrecedenceArrowAndPeriod;
1105     }
1106     return -1;
1107   }
1108
1109   void addFakeParenthesis(FormatToken *Start, prec::Level Precedence) {
1110     Start->FakeLParens.push_back(Precedence);
1111     if (Precedence > prec::Unknown)
1112       Start->StartsBinaryExpression = true;
1113     if (Current) {
1114       ++Current->Previous->FakeRParens;
1115       if (Precedence > prec::Unknown)
1116         Current->Previous->EndsBinaryExpression = true;
1117     }
1118   }
1119
1120   /// \brief Parse unary operator expressions and surround them with fake
1121   /// parentheses if appropriate.
1122   void parseUnaryOperator() {
1123     if (!Current || Current->Type != TT_UnaryOperator) {
1124       parse(PrecedenceArrowAndPeriod);
1125       return;
1126     }
1127
1128     FormatToken *Start = Current;
1129     next();
1130     parseUnaryOperator();
1131
1132     // The actual precedence doesn't matter.
1133     addFakeParenthesis(Start, prec::Unknown);
1134   }
1135
1136   void parseConditionalExpr() {
1137     FormatToken *Start = Current;
1138     parse(prec::LogicalOr);
1139     if (!Current || !Current->is(tok::question))
1140       return;
1141     next();
1142     parseConditionalExpr();
1143     if (!Current || Current->Type != TT_ConditionalExpr)
1144       return;
1145     next();
1146     parseConditionalExpr();
1147     addFakeParenthesis(Start, prec::Conditional);
1148   }
1149
1150   void next() {
1151     if (Current)
1152       Current = Current->Next;
1153     while (Current && Current->isTrailingComment())
1154       Current = Current->Next;
1155   }
1156
1157   FormatToken *Current;
1158 };
1159
1160 } // end anonymous namespace
1161
1162 void
1163 TokenAnnotator::setCommentLineLevels(SmallVectorImpl<AnnotatedLine *> &Lines) {
1164   const AnnotatedLine *NextNonCommentLine = nullptr;
1165   for (SmallVectorImpl<AnnotatedLine *>::reverse_iterator I = Lines.rbegin(),
1166                                                           E = Lines.rend();
1167        I != E; ++I) {
1168     if (NextNonCommentLine && (*I)->First->is(tok::comment) &&
1169         (*I)->First->Next == nullptr)
1170       (*I)->Level = NextNonCommentLine->Level;
1171     else
1172       NextNonCommentLine = (*I)->First->isNot(tok::r_brace) ? (*I) : nullptr;
1173
1174     setCommentLineLevels((*I)->Children);
1175   }
1176 }
1177
1178 void TokenAnnotator::annotate(AnnotatedLine &Line) {
1179   for (SmallVectorImpl<AnnotatedLine *>::iterator I = Line.Children.begin(),
1180                                                   E = Line.Children.end();
1181        I != E; ++I) {
1182     annotate(**I);
1183   }
1184   AnnotatingParser Parser(Style, Line, Ident_in);
1185   Line.Type = Parser.parseLine();
1186   if (Line.Type == LT_Invalid)
1187     return;
1188
1189   ExpressionParser ExprParser(Line);
1190   ExprParser.parse();
1191
1192   if (Line.First->Type == TT_ObjCMethodSpecifier)
1193     Line.Type = LT_ObjCMethodDecl;
1194   else if (Line.First->Type == TT_ObjCDecl)
1195     Line.Type = LT_ObjCDecl;
1196   else if (Line.First->Type == TT_ObjCProperty)
1197     Line.Type = LT_ObjCProperty;
1198
1199   Line.First->SpacesRequiredBefore = 1;
1200   Line.First->CanBreakBefore = Line.First->MustBreakBefore;
1201 }
1202
1203 // This function heuristically determines whether 'Current' starts the name of a
1204 // function declaration.
1205 static bool isFunctionDeclarationName(const FormatToken &Current) {
1206   if (Current.Type != TT_StartOfName ||
1207       Current.NestingLevel != 0 ||
1208       Current.Previous->Type == TT_StartOfName)
1209     return false;
1210   const FormatToken *Next = Current.Next;
1211   for (; Next; Next = Next->Next) {
1212     if (Next->Type == TT_TemplateOpener) {
1213       Next = Next->MatchingParen;
1214     } else if (Next->is(tok::coloncolon)) {
1215       Next = Next->Next;
1216       if (!Next || !Next->is(tok::identifier))
1217         return false;
1218     } else if (Next->is(tok::l_paren)) {
1219       break;
1220     } else {
1221       return false;
1222     }
1223   }
1224   if (!Next)
1225     return false;
1226   assert(Next->is(tok::l_paren));
1227   if (Next->Next == Next->MatchingParen)
1228     return true;
1229   for (const FormatToken *Tok = Next->Next; Tok != Next->MatchingParen;
1230        Tok = Tok->Next) {
1231     if (Tok->is(tok::kw_const) || Tok->isSimpleTypeSpecifier() ||
1232         Tok->Type == TT_PointerOrReference || Tok->Type == TT_StartOfName)
1233       return true;
1234     if (Tok->isOneOf(tok::l_brace, tok::string_literal) || Tok->Tok.isLiteral())
1235       return false;
1236   }
1237   return false;
1238 }
1239
1240 void TokenAnnotator::calculateFormattingInformation(AnnotatedLine &Line) {
1241   for (SmallVectorImpl<AnnotatedLine *>::iterator I = Line.Children.begin(),
1242                                                   E = Line.Children.end();
1243        I != E; ++I) {
1244     calculateFormattingInformation(**I);
1245   }
1246
1247   Line.First->TotalLength =
1248       Line.First->IsMultiline ? Style.ColumnLimit : Line.First->ColumnWidth;
1249   if (!Line.First->Next)
1250     return;
1251   FormatToken *Current = Line.First->Next;
1252   bool InFunctionDecl = Line.MightBeFunctionDecl;
1253   while (Current) {
1254     if (isFunctionDeclarationName(*Current))
1255       Current->Type = TT_FunctionDeclarationName;
1256     if (Current->Type == TT_LineComment) {
1257       if (Current->Previous->BlockKind == BK_BracedInit &&
1258           Current->Previous->opensScope())
1259         Current->SpacesRequiredBefore = Style.Cpp11BracedListStyle ? 0 : 1;
1260       else
1261         Current->SpacesRequiredBefore = Style.SpacesBeforeTrailingComments;
1262
1263       // If we find a trailing comment, iterate backwards to determine whether
1264       // it seems to relate to a specific parameter. If so, break before that
1265       // parameter to avoid changing the comment's meaning. E.g. don't move 'b'
1266       // to the previous line in:
1267       //   SomeFunction(a,
1268       //                b, // comment
1269       //                c);
1270       if (!Current->HasUnescapedNewline) {
1271         for (FormatToken *Parameter = Current->Previous; Parameter;
1272              Parameter = Parameter->Previous) {
1273           if (Parameter->isOneOf(tok::comment, tok::r_brace))
1274             break;
1275           if (Parameter->Previous && Parameter->Previous->is(tok::comma)) {
1276             if (Parameter->Previous->Type != TT_CtorInitializerComma &&
1277                 Parameter->HasUnescapedNewline)
1278               Parameter->MustBreakBefore = true;
1279             break;
1280           }
1281         }
1282       }
1283     } else if (Current->SpacesRequiredBefore == 0 &&
1284                spaceRequiredBefore(Line, *Current)) {
1285       Current->SpacesRequiredBefore = 1;
1286     }
1287
1288     Current->MustBreakBefore =
1289         Current->MustBreakBefore || mustBreakBefore(Line, *Current);
1290
1291     Current->CanBreakBefore =
1292         Current->MustBreakBefore || canBreakBefore(Line, *Current);
1293     unsigned ChildSize = 0;
1294     if (Current->Previous->Children.size() == 1) {
1295       FormatToken &LastOfChild = *Current->Previous->Children[0]->Last;
1296       ChildSize = LastOfChild.isTrailingComment() ? Style.ColumnLimit
1297                                                   : LastOfChild.TotalLength + 1;
1298     }
1299     if (Current->MustBreakBefore || Current->Previous->Children.size() > 1 ||
1300         Current->IsMultiline)
1301       Current->TotalLength = Current->Previous->TotalLength + Style.ColumnLimit;
1302     else
1303       Current->TotalLength = Current->Previous->TotalLength +
1304                              Current->ColumnWidth + ChildSize +
1305                              Current->SpacesRequiredBefore;
1306
1307     if (Current->Type == TT_CtorInitializerColon)
1308       InFunctionDecl = false;
1309
1310     // FIXME: Only calculate this if CanBreakBefore is true once static
1311     // initializers etc. are sorted out.
1312     // FIXME: Move magic numbers to a better place.
1313     Current->SplitPenalty = 20 * Current->BindingStrength +
1314                             splitPenalty(Line, *Current, InFunctionDecl);
1315
1316     Current = Current->Next;
1317   }
1318
1319   calculateUnbreakableTailLengths(Line);
1320   for (Current = Line.First; Current != nullptr; Current = Current->Next) {
1321     if (Current->Role)
1322       Current->Role->precomputeFormattingInfos(Current);
1323   }
1324
1325   DEBUG({ printDebugInfo(Line); });
1326 }
1327
1328 void TokenAnnotator::calculateUnbreakableTailLengths(AnnotatedLine &Line) {
1329   unsigned UnbreakableTailLength = 0;
1330   FormatToken *Current = Line.Last;
1331   while (Current) {
1332     Current->UnbreakableTailLength = UnbreakableTailLength;
1333     if (Current->CanBreakBefore ||
1334         Current->isOneOf(tok::comment, tok::string_literal)) {
1335       UnbreakableTailLength = 0;
1336     } else {
1337       UnbreakableTailLength +=
1338           Current->ColumnWidth + Current->SpacesRequiredBefore;
1339     }
1340     Current = Current->Previous;
1341   }
1342 }
1343
1344 unsigned TokenAnnotator::splitPenalty(const AnnotatedLine &Line,
1345                                       const FormatToken &Tok,
1346                                       bool InFunctionDecl) {
1347   const FormatToken &Left = *Tok.Previous;
1348   const FormatToken &Right = Tok;
1349
1350   if (Left.is(tok::semi))
1351     return 0;
1352   if (Left.is(tok::comma) || (Right.is(tok::identifier) && Right.Next &&
1353                               Right.Next->Type == TT_DictLiteral))
1354     return 1;
1355   if (Right.is(tok::l_square)) {
1356     if (Style.Language == FormatStyle::LK_Proto)
1357       return 1;
1358     if (Right.Type != TT_ObjCMethodExpr && Right.Type != TT_LambdaLSquare)
1359       return 500;
1360   }
1361   if (Right.Type == TT_StartOfName ||
1362       Right.Type == TT_FunctionDeclarationName || Right.is(tok::kw_operator)) {
1363     if (Line.First->is(tok::kw_for) && Right.PartOfMultiVariableDeclStmt)
1364       return 3;
1365     if (Left.Type == TT_StartOfName)
1366       return 20;
1367     if (InFunctionDecl && Right.NestingLevel == 0)
1368       return Style.PenaltyReturnTypeOnItsOwnLine;
1369     return 200;
1370   }
1371   if (Left.is(tok::equal) && Right.is(tok::l_brace))
1372     return 150;
1373   if (Left.Type == TT_CastRParen)
1374     return 100;
1375   if (Left.is(tok::coloncolon) ||
1376       (Right.is(tok::period) && Style.Language == FormatStyle::LK_Proto))
1377     return 500;
1378   if (Left.isOneOf(tok::kw_class, tok::kw_struct))
1379     return 5000;
1380
1381   if (Left.Type == TT_RangeBasedForLoopColon ||
1382       Left.Type == TT_InheritanceColon)
1383     return 2;
1384
1385   if (Right.isMemberAccess()) {
1386     if (Left.is(tok::r_paren) && Left.MatchingParen &&
1387         Left.MatchingParen->ParameterCount > 0)
1388       return 20; // Should be smaller than breaking at a nested comma.
1389     return 150;
1390   }
1391
1392   if (Right.Type == TT_TrailingAnnotation &&
1393       (!Right.Next || Right.Next->isNot(tok::l_paren))) {
1394     // Generally, breaking before a trailing annotation is bad unless it is
1395     // function-like. It seems to be especially preferable to keep standard
1396     // annotations (i.e. "const", "final" and "override") on the same line.
1397     // Use a slightly higher penalty after ")" so that annotations like
1398     // "const override" are kept together.
1399     bool is_short_annotation = Right.TokenText.size() < 10;
1400     return (Left.is(tok::r_paren) ? 100 : 120) + (is_short_annotation ? 50 : 0);
1401   }
1402
1403   // In for-loops, prefer breaking at ',' and ';'.
1404   if (Line.First->is(tok::kw_for) && Left.is(tok::equal))
1405     return 4;
1406
1407   // In Objective-C method expressions, prefer breaking before "param:" over
1408   // breaking after it.
1409   if (Right.Type == TT_SelectorName)
1410     return 0;
1411   if (Left.is(tok::colon) && Left.Type == TT_ObjCMethodExpr)
1412     return Line.MightBeFunctionDecl ? 50 : 500;
1413
1414   if (Left.is(tok::l_paren) && InFunctionDecl)
1415     return 100;
1416   if (Left.is(tok::equal) && InFunctionDecl)
1417     return 110;
1418   if (Left.opensScope())
1419     return Left.ParameterCount > 1 ? Style.PenaltyBreakBeforeFirstCallParameter
1420                                    : 19;
1421
1422   if (Right.is(tok::lessless)) {
1423     if (Left.is(tok::string_literal)) {
1424       StringRef Content = Left.TokenText;
1425       if (Content.startswith("\""))
1426         Content = Content.drop_front(1);
1427       if (Content.endswith("\""))
1428         Content = Content.drop_back(1);
1429       Content = Content.trim();
1430       if (Content.size() > 1 &&
1431           (Content.back() == ':' || Content.back() == '='))
1432         return 25;
1433     }
1434     return 1; // Breaking at a << is really cheap.
1435   }
1436   if (Left.Type == TT_ConditionalExpr)
1437     return prec::Conditional;
1438   prec::Level Level = Left.getPrecedence();
1439
1440   if (Level != prec::Unknown)
1441     return Level;
1442
1443   return 3;
1444 }
1445
1446 bool TokenAnnotator::spaceRequiredBetween(const AnnotatedLine &Line,
1447                                           const FormatToken &Left,
1448                                           const FormatToken &Right) {
1449   if (Style.Language == FormatStyle::LK_Proto) {
1450     if (Right.is(tok::period) &&
1451         (Left.TokenText == "optional" || Left.TokenText == "required" ||
1452          Left.TokenText == "repeated"))
1453       return true;
1454     if (Right.is(tok::l_paren) &&
1455         (Left.TokenText == "returns" || Left.TokenText == "option"))
1456       return true;
1457   } else if (Style.Language == FormatStyle::LK_JavaScript) {
1458     if (Left.TokenText == "var")
1459       return true;
1460   }
1461   if (Left.is(tok::kw_return) && Right.isNot(tok::semi))
1462     return true;
1463   if (Style.ObjCSpaceAfterProperty && Line.Type == LT_ObjCProperty &&
1464       Left.Tok.getObjCKeywordID() == tok::objc_property)
1465     return true;
1466   if (Right.is(tok::hashhash))
1467     return Left.is(tok::hash);
1468   if (Left.isOneOf(tok::hashhash, tok::hash))
1469     return Right.is(tok::hash);
1470   if (Left.is(tok::l_paren) && Right.is(tok::r_paren))
1471     return Style.SpaceInEmptyParentheses;
1472   if (Left.is(tok::l_paren) || Right.is(tok::r_paren))
1473     return (Right.Type == TT_CastRParen ||
1474             (Left.MatchingParen && Left.MatchingParen->Type == TT_CastRParen))
1475                ? Style.SpacesInCStyleCastParentheses
1476                : Style.SpacesInParentheses;
1477   if (Style.SpacesInAngles &&
1478       ((Left.Type == TT_TemplateOpener) != (Right.Type == TT_TemplateCloser)))
1479     return true;
1480   if (Right.isOneOf(tok::semi, tok::comma))
1481     return false;
1482   if (Right.is(tok::less) &&
1483       (Left.is(tok::kw_template) ||
1484        (Line.Type == LT_ObjCDecl && Style.ObjCSpaceBeforeProtocolList)))
1485     return true;
1486   if (Left.is(tok::arrow) || Right.is(tok::arrow))
1487     return false;
1488   if (Left.isOneOf(tok::exclaim, tok::tilde))
1489     return false;
1490   if (Left.is(tok::at) &&
1491       Right.isOneOf(tok::identifier, tok::string_literal, tok::char_constant,
1492                     tok::numeric_constant, tok::l_paren, tok::l_brace,
1493                     tok::kw_true, tok::kw_false))
1494     return false;
1495   if (Left.is(tok::coloncolon))
1496     return false;
1497   if (Right.is(tok::coloncolon) && Left.isNot(tok::l_brace))
1498     return (Left.is(tok::less) && Style.Standard == FormatStyle::LS_Cpp03) ||
1499            !Left.isOneOf(tok::identifier, tok::greater, tok::l_paren,
1500                          tok::r_paren, tok::less);
1501   if (Left.is(tok::less) || Right.isOneOf(tok::greater, tok::less))
1502     return false;
1503   if (Right.is(tok::ellipsis))
1504     return Left.Tok.isLiteral();
1505   if (Left.is(tok::l_square) && Right.is(tok::amp))
1506     return false;
1507   if (Right.Type == TT_PointerOrReference)
1508     return Left.Tok.isLiteral() ||
1509            ((Left.Type != TT_PointerOrReference) && Left.isNot(tok::l_paren) &&
1510             Style.PointerAlignment != FormatStyle::PAS_Left);
1511   if (Right.Type == TT_FunctionTypeLParen && Left.isNot(tok::l_paren) &&
1512       (Left.Type != TT_PointerOrReference || Style.PointerAlignment != FormatStyle::PAS_Right))
1513     return true;
1514   if (Left.Type == TT_PointerOrReference)
1515     return Right.Tok.isLiteral() || Right.Type == TT_BlockComment ||
1516            ((Right.Type != TT_PointerOrReference) &&
1517             Right.isNot(tok::l_paren) && Style.PointerAlignment != FormatStyle::PAS_Right &&
1518             Left.Previous &&
1519             !Left.Previous->isOneOf(tok::l_paren, tok::coloncolon));
1520   if (Right.is(tok::star) && Left.is(tok::l_paren))
1521     return false;
1522   if (Left.is(tok::l_square))
1523     return Left.Type == TT_ArrayInitializerLSquare &&
1524            Style.SpacesInContainerLiterals && Right.isNot(tok::r_square);
1525   if (Right.is(tok::r_square))
1526     return Right.MatchingParen && Style.SpacesInContainerLiterals &&
1527            Right.MatchingParen->Type == TT_ArrayInitializerLSquare;
1528   if (Right.is(tok::l_square) && Right.Type != TT_ObjCMethodExpr &&
1529       Right.Type != TT_LambdaLSquare && Left.isNot(tok::numeric_constant) &&
1530       Left.Type != TT_DictLiteral)
1531     return false;
1532   if (Left.is(tok::colon))
1533     return Left.Type != TT_ObjCMethodExpr;
1534   if (Left.Type == TT_BlockComment)
1535     return !Left.TokenText.endswith("=*/");
1536   if (Right.is(tok::l_paren)) {
1537     if (Left.is(tok::r_paren) && Left.Type == TT_AttributeParen)
1538       return true;
1539     return Line.Type == LT_ObjCDecl ||
1540            Left.isOneOf(tok::kw_new, tok::kw_delete, tok::semi) ||
1541            (Style.SpaceBeforeParens != FormatStyle::SBPO_Never &&
1542             (Left.isOneOf(tok::kw_if, tok::kw_for, tok::kw_while,
1543                           tok::kw_switch, tok::kw_catch, tok::kw_case) ||
1544              Left.IsForEachMacro)) ||
1545            (Style.SpaceBeforeParens == FormatStyle::SBPO_Always &&
1546             Left.isOneOf(tok::identifier, tok::kw___attribute) &&
1547             Line.Type != LT_PreprocessorDirective);
1548   }
1549   if (Left.is(tok::at) && Right.Tok.getObjCKeywordID() != tok::objc_not_keyword)
1550     return false;
1551   if (Left.is(tok::l_brace) && Right.is(tok::r_brace))
1552     return !Left.Children.empty(); // No spaces in "{}".
1553   if ((Left.is(tok::l_brace) && Left.BlockKind != BK_Block) ||
1554       (Right.is(tok::r_brace) && Right.MatchingParen &&
1555        Right.MatchingParen->BlockKind != BK_Block))
1556     return !Style.Cpp11BracedListStyle;
1557   if (Right.Type == TT_UnaryOperator)
1558     return !Left.isOneOf(tok::l_paren, tok::l_square, tok::at) &&
1559            (Left.isNot(tok::colon) || Left.Type != TT_ObjCMethodExpr);
1560   if ((Left.isOneOf(tok::identifier, tok::greater, tok::r_square,
1561                     tok::r_paren) ||
1562        Left.isSimpleTypeSpecifier()) &&
1563       Right.is(tok::l_brace) && Right.getNextNonComment() &&
1564       Right.BlockKind != BK_Block)
1565     return false;
1566   if (Left.is(tok::period) || Right.is(tok::period))
1567     return false;
1568   if (Right.is(tok::hash) && Left.is(tok::identifier) && Left.TokenText == "L")
1569     return false;
1570   return true;
1571 }
1572
1573 bool TokenAnnotator::spaceRequiredBefore(const AnnotatedLine &Line,
1574                                          const FormatToken &Tok) {
1575   if (Tok.Tok.getIdentifierInfo() && Tok.Previous->Tok.getIdentifierInfo())
1576     return true; // Never ever merge two identifiers.
1577   if (Tok.Previous->Type == TT_ImplicitStringLiteral)
1578     return Tok.WhitespaceRange.getBegin() != Tok.WhitespaceRange.getEnd();
1579   if (Line.Type == LT_ObjCMethodDecl) {
1580     if (Tok.Previous->Type == TT_ObjCMethodSpecifier)
1581       return true;
1582     if (Tok.Previous->is(tok::r_paren) && Tok.is(tok::identifier))
1583       // Don't space between ')' and <id>
1584       return false;
1585   }
1586   if (Line.Type == LT_ObjCProperty &&
1587       (Tok.is(tok::equal) || Tok.Previous->is(tok::equal)))
1588     return false;
1589
1590   if (Tok.Type == TT_TrailingReturnArrow ||
1591       Tok.Previous->Type == TT_TrailingReturnArrow)
1592     return true;
1593   if (Tok.Previous->is(tok::comma))
1594     return true;
1595   if (Tok.is(tok::comma))
1596     return false;
1597   if (Tok.Type == TT_CtorInitializerColon || Tok.Type == TT_ObjCBlockLParen)
1598     return true;
1599   if (Tok.Previous->Tok.is(tok::kw_operator))
1600     return Tok.is(tok::coloncolon);
1601   if (Tok.Type == TT_OverloadedOperatorLParen)
1602     return false;
1603   if (Tok.is(tok::colon))
1604     return !Line.First->isOneOf(tok::kw_case, tok::kw_default) &&
1605            Tok.getNextNonComment() && Tok.Type != TT_ObjCMethodExpr &&
1606            !Tok.Previous->is(tok::question) &&
1607            (Tok.Type != TT_DictLiteral || Style.SpacesInContainerLiterals);
1608   if (Tok.Previous->Type == TT_UnaryOperator ||
1609       Tok.Previous->Type == TT_CastRParen)
1610     return Tok.Type == TT_BinaryOperator;
1611   if (Tok.Previous->is(tok::greater) && Tok.is(tok::greater)) {
1612     return Tok.Type == TT_TemplateCloser &&
1613            Tok.Previous->Type == TT_TemplateCloser &&
1614            (Style.Standard != FormatStyle::LS_Cpp11 || Style.SpacesInAngles);
1615   }
1616   if (Tok.isOneOf(tok::arrowstar, tok::periodstar) ||
1617       Tok.Previous->isOneOf(tok::arrowstar, tok::periodstar))
1618     return false;
1619   if (!Style.SpaceBeforeAssignmentOperators &&
1620       Tok.getPrecedence() == prec::Assignment)
1621     return false;
1622   if ((Tok.Type == TT_BinaryOperator && !Tok.Previous->is(tok::l_paren)) ||
1623       Tok.Previous->Type == TT_BinaryOperator ||
1624       Tok.Previous->Type == TT_ConditionalExpr)
1625     return true;
1626   if (Tok.Previous->Type == TT_TemplateCloser && Tok.is(tok::l_paren))
1627     return false;
1628   if (Tok.is(tok::less) && Tok.Previous->isNot(tok::l_paren) &&
1629       Line.First->is(tok::hash))
1630     return true;
1631   if (Tok.Type == TT_TrailingUnaryOperator)
1632     return false;
1633   if (Tok.Previous->Type == TT_RegexLiteral)
1634     return false;
1635   return spaceRequiredBetween(Line, *Tok.Previous, Tok);
1636 }
1637
1638 // Returns 'true' if 'Tok' is a brace we'd want to break before in Allman style.
1639 static bool isAllmanBrace(const FormatToken &Tok) {
1640   return Tok.is(tok::l_brace) && Tok.BlockKind == BK_Block &&
1641          Tok.Type != TT_ObjCBlockLBrace && Tok.Type != TT_DictLiteral;
1642 }
1643
1644 bool TokenAnnotator::mustBreakBefore(const AnnotatedLine &Line,
1645                                      const FormatToken &Right) {
1646   const FormatToken &Left = *Right.Previous;
1647   if (Right.NewlinesBefore > 1)
1648     return true;
1649   if (Right.is(tok::comment)) {
1650     return Right.Previous->BlockKind != BK_BracedInit &&
1651            Right.Previous->Type != TT_CtorInitializerColon &&
1652            (Right.NewlinesBefore > 0 && Right.HasUnescapedNewline);
1653   } else if (Right.Previous->isTrailingComment() ||
1654              (Right.isStringLiteral() && Right.Previous->isStringLiteral())) {
1655     return true;
1656   } else if (Right.Previous->IsUnterminatedLiteral) {
1657     return true;
1658   } else if (Right.is(tok::lessless) && Right.Next &&
1659              Right.Previous->is(tok::string_literal) &&
1660              Right.Next->is(tok::string_literal)) {
1661     return true;
1662   } else if (Right.Previous->ClosesTemplateDeclaration &&
1663              Right.Previous->MatchingParen &&
1664              Right.Previous->MatchingParen->NestingLevel == 0 &&
1665              Style.AlwaysBreakTemplateDeclarations) {
1666     return true;
1667   } else if ((Right.Type == TT_CtorInitializerComma ||
1668               Right.Type == TT_CtorInitializerColon) &&
1669              Style.BreakConstructorInitializersBeforeComma &&
1670              !Style.ConstructorInitializerAllOnOneLineOrOnePerLine) {
1671     return true;
1672   } else if (Right.is(tok::string_literal) &&
1673              Right.TokenText.startswith("R\"")) {
1674     // Raw string literals are special wrt. line breaks. The author has made a
1675     // deliberate choice and might have aligned the contents of the string
1676     // literal accordingly. Thus, we try keep existing line breaks.
1677     return Right.NewlinesBefore > 0;
1678   } else if (Right.Previous->is(tok::l_brace) && Right.NestingLevel == 1 &&
1679              Style.Language == FormatStyle::LK_Proto) {
1680     // Don't enums onto single lines in protocol buffers.
1681     return true;
1682   } else if (isAllmanBrace(Left) || isAllmanBrace(Right)) {
1683     return Style.BreakBeforeBraces == FormatStyle::BS_Allman ||
1684            Style.BreakBeforeBraces == FormatStyle::BS_GNU;
1685   }
1686
1687   // If the last token before a '}' is a comma or a comment, the intention is to
1688   // insert a line break after it in order to make shuffling around entries
1689   // easier.
1690   const FormatToken *BeforeClosingBrace = nullptr;
1691   if (Left.is(tok::l_brace) && Left.MatchingParen)
1692     BeforeClosingBrace = Left.MatchingParen->Previous;
1693   else if (Right.is(tok::r_brace))
1694     BeforeClosingBrace = Right.Previous;
1695   if (BeforeClosingBrace &&
1696       BeforeClosingBrace->isOneOf(tok::comma, tok::comment))
1697     return true;
1698
1699   if (Style.Language == FormatStyle::LK_JavaScript) {
1700     // FIXME: This might apply to other languages and token kinds.
1701     if (Right.is(tok::char_constant) && Left.is(tok::plus) && Left.Previous &&
1702         Left.Previous->is(tok::char_constant))
1703       return true;
1704   }
1705
1706   return false;
1707 }
1708
1709 bool TokenAnnotator::canBreakBefore(const AnnotatedLine &Line,
1710                                     const FormatToken &Right) {
1711   const FormatToken &Left = *Right.Previous;
1712   if (Left.is(tok::at))
1713     return false;
1714   if (Left.Tok.getObjCKeywordID() == tok::objc_interface)
1715     return false;
1716   if (Right.Type == TT_StartOfName ||
1717       Right.Type == TT_FunctionDeclarationName || Right.is(tok::kw_operator))
1718     return true;
1719   if (Right.isTrailingComment())
1720     // We rely on MustBreakBefore being set correctly here as we should not
1721     // change the "binding" behavior of a comment.
1722     // The first comment in a braced lists is always interpreted as belonging to
1723     // the first list element. Otherwise, it should be placed outside of the
1724     // list.
1725     return Left.BlockKind == BK_BracedInit;
1726   if (Left.is(tok::question) && Right.is(tok::colon))
1727     return false;
1728   if (Right.Type == TT_ConditionalExpr || Right.is(tok::question))
1729     return Style.BreakBeforeTernaryOperators;
1730   if (Left.Type == TT_ConditionalExpr || Left.is(tok::question))
1731     return !Style.BreakBeforeTernaryOperators;
1732   if (Right.Type == TT_InheritanceColon)
1733     return true;
1734   if (Right.is(tok::colon) && (Right.Type != TT_CtorInitializerColon &&
1735                                Right.Type != TT_InlineASMColon))
1736     return false;
1737   if (Left.is(tok::colon) &&
1738       (Left.Type == TT_DictLiteral || Left.Type == TT_ObjCMethodExpr))
1739     return true;
1740   if (Right.Type == TT_SelectorName)
1741     return true;
1742   if (Left.is(tok::r_paren) && Line.Type == LT_ObjCProperty)
1743     return true;
1744   if (Left.ClosesTemplateDeclaration)
1745     return true;
1746   if (Right.Type == TT_RangeBasedForLoopColon ||
1747       Right.Type == TT_OverloadedOperatorLParen ||
1748       Right.Type == TT_OverloadedOperator)
1749     return false;
1750   if (Left.Type == TT_RangeBasedForLoopColon)
1751     return true;
1752   if (Right.Type == TT_RangeBasedForLoopColon)
1753     return false;
1754   if (Left.Type == TT_PointerOrReference || Left.Type == TT_TemplateCloser ||
1755       Left.Type == TT_UnaryOperator || Left.is(tok::kw_operator))
1756     return false;
1757   if (Left.is(tok::equal) && Line.Type == LT_VirtualFunctionDecl)
1758     return false;
1759   if (Left.is(tok::l_paren) && Left.Type == TT_AttributeParen)
1760     return false;
1761   if (Left.is(tok::l_paren) && Left.Previous &&
1762       (Left.Previous->Type == TT_BinaryOperator ||
1763        Left.Previous->Type == TT_CastRParen || Left.Previous->is(tok::kw_if)))
1764     return false;
1765   if (Right.Type == TT_ImplicitStringLiteral)
1766     return false;
1767
1768   if (Right.is(tok::r_paren) || Right.Type == TT_TemplateCloser)
1769     return false;
1770
1771   // We only break before r_brace if there was a corresponding break before
1772   // the l_brace, which is tracked by BreakBeforeClosingBrace.
1773   if (Right.is(tok::r_brace))
1774     return Right.MatchingParen && Right.MatchingParen->BlockKind == BK_Block;
1775
1776   // Allow breaking after a trailing annotation, e.g. after a method
1777   // declaration.
1778   if (Left.Type == TT_TrailingAnnotation)
1779     return !Right.isOneOf(tok::l_brace, tok::semi, tok::equal, tok::l_paren,
1780                           tok::less, tok::coloncolon);
1781
1782   if (Right.is(tok::kw___attribute))
1783     return true;
1784
1785   if (Left.is(tok::identifier) && Right.is(tok::string_literal))
1786     return true;
1787
1788   if (Right.is(tok::identifier) && Right.Next &&
1789       Right.Next->Type == TT_DictLiteral)
1790     return true;
1791
1792   if (Left.Type == TT_CtorInitializerComma &&
1793       Style.BreakConstructorInitializersBeforeComma)
1794     return false;
1795   if (Right.Type == TT_CtorInitializerComma &&
1796       Style.BreakConstructorInitializersBeforeComma)
1797     return true;
1798   if (Left.is(tok::greater) && Right.is(tok::greater) &&
1799       Left.Type != TT_TemplateCloser)
1800     return false;
1801   if (Right.Type == TT_BinaryOperator && Style.BreakBeforeBinaryOperators)
1802     return true;
1803   if (Left.Type == TT_ArrayInitializerLSquare)
1804     return true;
1805   return (Left.isBinaryOperator() &&
1806           !Left.isOneOf(tok::arrowstar, tok::lessless) &&
1807           !Style.BreakBeforeBinaryOperators) ||
1808          Left.isOneOf(tok::comma, tok::coloncolon, tok::semi, tok::l_brace,
1809                       tok::kw_class, tok::kw_struct) ||
1810          Right.isMemberAccess() ||
1811          Right.isOneOf(tok::lessless, tok::colon, tok::l_square, tok::at) ||
1812          (Left.is(tok::r_paren) &&
1813           Right.isOneOf(tok::identifier, tok::kw_const)) ||
1814          (Left.is(tok::l_paren) && !Right.is(tok::r_paren));
1815 }
1816
1817 void TokenAnnotator::printDebugInfo(const AnnotatedLine &Line) {
1818   llvm::errs() << "AnnotatedTokens:\n";
1819   const FormatToken *Tok = Line.First;
1820   while (Tok) {
1821     llvm::errs() << " M=" << Tok->MustBreakBefore
1822                  << " C=" << Tok->CanBreakBefore << " T=" << Tok->Type
1823                  << " S=" << Tok->SpacesRequiredBefore
1824                  << " B=" << Tok->BlockParameterCount
1825                  << " P=" << Tok->SplitPenalty << " Name=" << Tok->Tok.getName()
1826                  << " L=" << Tok->TotalLength << " PPK=" << Tok->PackingKind
1827                  << " FakeLParens=";
1828     for (unsigned i = 0, e = Tok->FakeLParens.size(); i != e; ++i)
1829       llvm::errs() << Tok->FakeLParens[i] << "/";
1830     llvm::errs() << " FakeRParens=" << Tok->FakeRParens << "\n";
1831     if (!Tok->Next)
1832       assert(Tok == Line.Last);
1833     Tok = Tok->Next;
1834   }
1835   llvm::errs() << "----\n";
1836 }
1837
1838 } // namespace format
1839 } // namespace clang