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