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