contrib/llvm-project/clang/lib/Format/TokenAnnotator.cpp

   1 //===--- TokenAnnotator.cpp - Format C++ code -----------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 ///
   9 /// \file
  10 /// This file implements a token annotator, i.e. creates
  11 /// \c AnnotatedTokens out of \c FormatTokens with required extra information.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "TokenAnnotator.h"
  16 #include "FormatToken.h"
  17 #include "clang/Basic/SourceManager.h"
  18 #include "clang/Basic/TokenKinds.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/Support/Debug.h"
  21
  22 #define DEBUG_TYPE "format-token-annotator"
  23
  24 namespace clang {
  25 namespace format {
  26
  27 namespace {
  28
  29 /// Returns \c true if the token can be used as an identifier in
  30 /// an Objective-C \c @selector, \c false otherwise.
  31 ///
  32 /// Because getFormattingLangOpts() always lexes source code as
  33 /// Objective-C++, C++ keywords like \c new and \c delete are
  34 /// lexed as tok::kw_*, not tok::identifier, even for Objective-C.
  35 ///
  36 /// For Objective-C and Objective-C++, both identifiers and keywords
  37 /// are valid inside @selector(...) (or a macro which
  38 /// invokes @selector(...)). So, we allow treat any identifier or
  39 /// keyword as a potential Objective-C selector component.
  40 static bool canBeObjCSelectorComponent(const FormatToken &Tok) {
  41   return Tok.Tok.getIdentifierInfo() != nullptr;
  42 }
  43
  44 /// With `Left` being '(', check if we're at either `[...](` or
  45 /// `[...]<...>(`, where the [ opens a lambda capture list.
  46 static bool isLambdaParameterList(const FormatToken *Left) {
  47   // Skip <...> if present.
  48   if (Left->Previous && Left->Previous->is(tok::greater) &&
  49       Left->Previous->MatchingParen &&
  50       Left->Previous->MatchingParen->is(TT_TemplateOpener))
  51     Left = Left->Previous->MatchingParen;
  52
  53   // Check for `[...]`.
  54   return Left->Previous && Left->Previous->is(tok::r_square) &&
  55          Left->Previous->MatchingParen &&
  56          Left->Previous->MatchingParen->is(TT_LambdaLSquare);
  57 }
  58
  59 /// A parser that gathers additional information about tokens.
  60 ///
  61 /// The \c TokenAnnotator tries to match parenthesis and square brakets and
  62 /// store a parenthesis levels. It also tries to resolve matching "<" and ">"
  63 /// into template parameter lists.
  64 class AnnotatingParser {
  65 public:
  66   AnnotatingParser(const FormatStyle &Style, AnnotatedLine &Line,
  67                    const AdditionalKeywords &Keywords)
  68       : Style(Style), Line(Line), CurrentToken(Line.First), AutoFound(false),
  69         Keywords(Keywords) {
  70     Contexts.push_back(Context(tok::unknown, 1, /*IsExpression=*/false));
  71     resetTokenMetadata(CurrentToken);
  72   }
  73
  74 private:
  75   bool parseAngle() {
  76     if (!CurrentToken || !CurrentToken->Previous)
  77       return false;
  78     if (NonTemplateLess.count(CurrentToken->Previous))
  79       return false;
  80
  81     const FormatToken &Previous = *CurrentToken->Previous; // The '<'.
  82     if (Previous.Previous) {
  83       if (Previous.Previous->Tok.isLiteral())
  84         return false;
  85       if (Previous.Previous->is(tok::r_paren) && Contexts.size() > 1 &&
  86           (!Previous.Previous->MatchingParen ||
  87            !Previous.Previous->MatchingParen->is(TT_OverloadedOperatorLParen)))
  88         return false;
  89     }
  90
  91     FormatToken *Left = CurrentToken->Previous;
  92     Left->ParentBracket = Contexts.back().ContextKind;
  93     ScopedContextCreator ContextCreator(*this, tok::less, 12);
  94
  95     // If this angle is in the context of an expression, we need to be more
  96     // hesitant to detect it as opening template parameters.
  97     bool InExprContext = Contexts.back().IsExpression;
  98
  99     Contexts.back().IsExpression = false;
 100     // If there's a template keyword before the opening angle bracket, this is a
 101     // template parameter, not an argument.
 102     Contexts.back().InTemplateArgument =
 103         Left->Previous && Left->Previous->Tok.isNot(tok::kw_template);
 104
 105     if (Style.Language == FormatStyle::LK_Java &&
 106         CurrentToken->is(tok::question))
 107       next();
 108
 109     while (CurrentToken) {
 110       if (CurrentToken->is(tok::greater)) {
 111         Left->MatchingParen = CurrentToken;
 112         CurrentToken->MatchingParen = Left;
 113         // In TT_Proto, we must distignuish between:
 114         //   map<key, value>
 115         //   msg < item: data >
 116         //   msg: < item: data >
 117         // In TT_TextProto, map<key, value> does not occur.
 118         if (Style.Language == FormatStyle::LK_TextProto ||
 119             (Style.Language == FormatStyle::LK_Proto && Left->Previous &&
 120              Left->Previous->isOneOf(TT_SelectorName, TT_DictLiteral)))
 121           CurrentToken->Type = TT_DictLiteral;
 122         else
 123           CurrentToken->Type = TT_TemplateCloser;
 124         next();
 125         return true;
 126       }
 127       if (CurrentToken->is(tok::question) &&
 128           Style.Language == FormatStyle::LK_Java) {
 129         next();
 130         continue;
 131       }
 132       if (CurrentToken->isOneOf(tok::r_paren, tok::r_square, tok::r_brace) ||
 133           (CurrentToken->isOneOf(tok::colon, tok::question) && InExprContext &&
 134            Style.Language != FormatStyle::LK_Proto &&
 135            Style.Language != FormatStyle::LK_TextProto))
 136         return false;
 137       // If a && or || is found and interpreted as a binary operator, this set
 138       // of angles is likely part of something like "a < b && c > d". If the
 139       // angles are inside an expression, the ||/&& might also be a binary
 140       // operator that was misinterpreted because we are parsing template
 141       // parameters.
 142       // FIXME: This is getting out of hand, write a decent parser.
 143       if (CurrentToken->Previous->isOneOf(tok::pipepipe, tok::ampamp) &&
 144           CurrentToken->Previous->is(TT_BinaryOperator) &&
 145           Contexts[Contexts.size() - 2].IsExpression &&
 146           !Line.startsWith(tok::kw_template))
 147         return false;
 148       updateParameterCount(Left, CurrentToken);
 149       if (Style.Language == FormatStyle::LK_Proto) {
 150         if (FormatToken *Previous = CurrentToken->getPreviousNonComment()) {
 151           if (CurrentToken->is(tok::colon) ||
 152               (CurrentToken->isOneOf(tok::l_brace, tok::less) &&
 153                Previous->isNot(tok::colon)))
 154             Previous->Type = TT_SelectorName;
 155         }
 156       }
 157       if (!consumeToken())
 158         return false;
 159     }
 160     return false;
 161   }
 162
 163   bool parseParens(bool LookForDecls = false) {
 164     if (!CurrentToken)
 165       return false;
 166     FormatToken *Left = CurrentToken->Previous;
 167     Left->ParentBracket = Contexts.back().ContextKind;
 168     ScopedContextCreator ContextCreator(*this, tok::l_paren, 1);
 169
 170     // FIXME: This is a bit of a hack. Do better.
 171     Contexts.back().ColonIsForRangeExpr =
 172         Contexts.size() == 2 && Contexts[0].ColonIsForRangeExpr;
 173
 174     bool StartsObjCMethodExpr = false;
 175     if (FormatToken *MaybeSel = Left->Previous) {
 176       // @selector( starts a selector.
 177       if (MaybeSel->isObjCAtKeyword(tok::objc_selector) && MaybeSel->Previous &&
 178           MaybeSel->Previous->is(tok::at)) {
 179         StartsObjCMethodExpr = true;
 180       }
 181     }
 182
 183     if (Left->is(TT_OverloadedOperatorLParen)) {
 184       Contexts.back().IsExpression = false;
 185     } else if (Style.Language == FormatStyle::LK_JavaScript &&
 186                (Line.startsWith(Keywords.kw_type, tok::identifier) ||
 187                 Line.startsWith(tok::kw_export, Keywords.kw_type,
 188                                 tok::identifier))) {
 189       // type X = (...);
 190       // export type X = (...);
 191       Contexts.back().IsExpression = false;
 192     } else if (Left->Previous &&
 193                (Left->Previous->isOneOf(tok::kw_static_assert, tok::kw_decltype,
 194                                         tok::kw_while, tok::l_paren,
 195                                         tok::comma) ||
 196                 Left->Previous->isIf() ||
 197                 Left->Previous->is(TT_BinaryOperator))) {
 198       // static_assert, if and while usually contain expressions.
 199       Contexts.back().IsExpression = true;
 200     } else if (Style.Language == FormatStyle::LK_JavaScript && Left->Previous &&
 201                (Left->Previous->is(Keywords.kw_function) ||
 202                 (Left->Previous->endsSequence(tok::identifier,
 203                                               Keywords.kw_function)))) {
 204       // function(...) or function f(...)
 205       Contexts.back().IsExpression = false;
 206     } else if (Style.Language == FormatStyle::LK_JavaScript && Left->Previous &&
 207                Left->Previous->is(TT_JsTypeColon)) {
 208       // let x: (SomeType);
 209       Contexts.back().IsExpression = false;
 210     } else if (isLambdaParameterList(Left)) {
 211       // This is a parameter list of a lambda expression.
 212       Contexts.back().IsExpression = false;
 213     } else if (Line.InPPDirective &&
 214                (!Left->Previous || !Left->Previous->is(tok::identifier))) {
 215       Contexts.back().IsExpression = true;
 216     } else if (Contexts[Contexts.size() - 2].CaretFound) {
 217       // This is the parameter list of an ObjC block.
 218       Contexts.back().IsExpression = false;
 219     } else if (Left->Previous && Left->Previous->is(tok::kw___attribute)) {
 220       Left->Type = TT_AttributeParen;
 221     } else if (Left->Previous && Left->Previous->is(TT_ForEachMacro)) {
 222       // The first argument to a foreach macro is a declaration.
 223       Contexts.back().IsForEachMacro = true;
 224       Contexts.back().IsExpression = false;
 225     } else if (Left->Previous && Left->Previous->MatchingParen &&
 226                Left->Previous->MatchingParen->is(TT_ObjCBlockLParen)) {
 227       Contexts.back().IsExpression = false;
 228     } else if (!Line.MustBeDeclaration && !Line.InPPDirective) {
 229       bool IsForOrCatch =
 230           Left->Previous && Left->Previous->isOneOf(tok::kw_for, tok::kw_catch);
 231       Contexts.back().IsExpression = !IsForOrCatch;
 232     }
 233
 234     if (StartsObjCMethodExpr) {
 235       Contexts.back().ColonIsObjCMethodExpr = true;
 236       Left->Type = TT_ObjCMethodExpr;
 237     }
 238
 239     // MightBeFunctionType and ProbablyFunctionType are used for
 240     // function pointer and reference types as well as Objective-C
 241     // block types:
 242     //
 243     // void (*FunctionPointer)(void);
 244     // void (&FunctionReference)(void);
 245     // void (^ObjCBlock)(void);
 246     bool MightBeFunctionType = !Contexts[Contexts.size() - 2].IsExpression;
 247     bool ProbablyFunctionType =
 248         CurrentToken->isOneOf(tok::star, tok::amp, tok::caret);
 249     bool HasMultipleLines = false;
 250     bool HasMultipleParametersOnALine = false;
 251     bool MightBeObjCForRangeLoop =
 252         Left->Previous && Left->Previous->is(tok::kw_for);
 253     FormatToken *PossibleObjCForInToken = nullptr;
 254     while (CurrentToken) {
 255       // LookForDecls is set when "if (" has been seen. Check for
 256       // 'identifier' '*' 'identifier' followed by not '=' -- this
 257       // '*' has to be a binary operator but determineStarAmpUsage() will
 258       // categorize it as an unary operator, so set the right type here.
 259       if (LookForDecls && CurrentToken->Next) {
 260         FormatToken *Prev = CurrentToken->getPreviousNonComment();
 261         if (Prev) {
 262           FormatToken *PrevPrev = Prev->getPreviousNonComment();
 263           FormatToken *Next = CurrentToken->Next;
 264           if (PrevPrev && PrevPrev->is(tok::identifier) &&
 265               Prev->isOneOf(tok::star, tok::amp, tok::ampamp) &&
 266               CurrentToken->is(tok::identifier) && Next->isNot(tok::equal)) {
 267             Prev->Type = TT_BinaryOperator;
 268             LookForDecls = false;
 269           }
 270         }
 271       }
 272
 273       if (CurrentToken->Previous->is(TT_PointerOrReference) &&
 274           CurrentToken->Previous->Previous->isOneOf(tok::l_paren,
 275                                                     tok::coloncolon))
 276         ProbablyFunctionType = true;
 277       if (CurrentToken->is(tok::comma))
 278         MightBeFunctionType = false;
 279       if (CurrentToken->Previous->is(TT_BinaryOperator))
 280         Contexts.back().IsExpression = true;
 281       if (CurrentToken->is(tok::r_paren)) {
 282         if (MightBeFunctionType && ProbablyFunctionType && CurrentToken->Next &&
 283             (CurrentToken->Next->is(tok::l_paren) ||
 284              (CurrentToken->Next->is(tok::l_square) && Line.MustBeDeclaration)))
 285           Left->Type = Left->Next->is(tok::caret) ? TT_ObjCBlockLParen
 286                                                   : TT_FunctionTypeLParen;
 287         Left->MatchingParen = CurrentToken;
 288         CurrentToken->MatchingParen = Left;
 289
 290         if (CurrentToken->Next && CurrentToken->Next->is(tok::l_brace) &&
 291             Left->Previous && Left->Previous->is(tok::l_paren)) {
 292           // Detect the case where macros are used to generate lambdas or
 293           // function bodies, e.g.:
 294           //   auto my_lambda = MARCO((Type *type, int i) { .. body .. });
 295           for (FormatToken *Tok = Left; Tok != CurrentToken; Tok = Tok->Next) {
 296             if (Tok->is(TT_BinaryOperator) &&
 297                 Tok->isOneOf(tok::star, tok::amp, tok::ampamp))
 298               Tok->Type = TT_PointerOrReference;
 299           }
 300         }
 301
 302         if (StartsObjCMethodExpr) {
 303           CurrentToken->Type = TT_ObjCMethodExpr;
 304           if (Contexts.back().FirstObjCSelectorName) {
 305             Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName =
 306                 Contexts.back().LongestObjCSelectorName;
 307           }
 308         }
 309
 310         if (Left->is(TT_AttributeParen))
 311           CurrentToken->Type = TT_AttributeParen;
 312         if (Left->Previous && Left->Previous->is(TT_JavaAnnotation))
 313           CurrentToken->Type = TT_JavaAnnotation;
 314         if (Left->Previous && Left->Previous->is(TT_LeadingJavaAnnotation))
 315           CurrentToken->Type = TT_LeadingJavaAnnotation;
 316         if (Left->Previous && Left->Previous->is(TT_AttributeSquare))
 317           CurrentToken->Type = TT_AttributeSquare;
 318
 319         if (!HasMultipleLines)
 320           Left->PackingKind = PPK_Inconclusive;
 321         else if (HasMultipleParametersOnALine)
 322           Left->PackingKind = PPK_BinPacked;
 323         else
 324           Left->PackingKind = PPK_OnePerLine;
 325
 326         next();
 327         return true;
 328       }
 329       if (CurrentToken->isOneOf(tok::r_square, tok::r_brace))
 330         return false;
 331
 332       if (CurrentToken->is(tok::l_brace))
 333         Left->Type = TT_Unknown; // Not TT_ObjCBlockLParen
 334       if (CurrentToken->is(tok::comma) && CurrentToken->Next &&
 335           !CurrentToken->Next->HasUnescapedNewline &&
 336           !CurrentToken->Next->isTrailingComment())
 337         HasMultipleParametersOnALine = true;
 338       if ((CurrentToken->Previous->isOneOf(tok::kw_const, tok::kw_auto) ||
 339            CurrentToken->Previous->isSimpleTypeSpecifier()) &&
 340           !CurrentToken->is(tok::l_brace))
 341         Contexts.back().IsExpression = false;
 342       if (CurrentToken->isOneOf(tok::semi, tok::colon)) {
 343         MightBeObjCForRangeLoop = false;
 344         if (PossibleObjCForInToken) {
 345           PossibleObjCForInToken->Type = TT_Unknown;
 346           PossibleObjCForInToken = nullptr;
 347         }
 348       }
 349       if (MightBeObjCForRangeLoop && CurrentToken->is(Keywords.kw_in)) {
 350         PossibleObjCForInToken = CurrentToken;
 351         PossibleObjCForInToken->Type = TT_ObjCForIn;
 352       }
 353       // When we discover a 'new', we set CanBeExpression to 'false' in order to
 354       // parse the type correctly. Reset that after a comma.
 355       if (CurrentToken->is(tok::comma))
 356         Contexts.back().CanBeExpression = true;
 357
 358       FormatToken *Tok = CurrentToken;
 359       if (!consumeToken())
 360         return false;
 361       updateParameterCount(Left, Tok);
 362       if (CurrentToken && CurrentToken->HasUnescapedNewline)
 363         HasMultipleLines = true;
 364     }
 365     return false;
 366   }
 367
 368   bool isCSharpAttributeSpecifier(const FormatToken &Tok) {
 369     if (!Style.isCSharp())
 370       return false;
 371
 372     const FormatToken *AttrTok = Tok.Next;
 373     if (!AttrTok)
 374       return false;
 375
 376     // Just an empty declaration e.g. string [].
 377     if (AttrTok->is(tok::r_square))
 378       return false;
 379
 380     // Move along the tokens inbetween the '[' and ']' e.g. [STAThread].
 381     while (AttrTok && AttrTok->isNot(tok::r_square)) {
 382       AttrTok = AttrTok->Next;
 383     }
 384
 385     if (!AttrTok)
 386       return false;
 387
 388     // Move past the end of ']'.
 389     AttrTok = AttrTok->Next;
 390     if (!AttrTok)
 391       return false;
 392
 393     // Limit this to being an access modifier that follows.
 394     if (AttrTok->isOneOf(tok::kw_public, tok::kw_private, tok::kw_protected,
 395                          tok::kw_class, tok::kw_static, tok::l_square,
 396                          Keywords.kw_internal)) {
 397       return true;
 398     }
 399
 400     // incase its a [XXX] retval func(....
 401     if (AttrTok->Next &&
 402         AttrTok->Next->startsSequence(tok::identifier, tok::l_paren))
 403       return true;
 404
 405     return false;
 406   }
 407
 408   bool isCpp11AttributeSpecifier(const FormatToken &Tok) {
 409     if (!Style.isCpp() || !Tok.startsSequence(tok::l_square, tok::l_square))
 410       return false;
 411     // The first square bracket is part of an ObjC array literal
 412     if (Tok.Previous && Tok.Previous->is(tok::at)) {
 413       return false;
 414     }
 415     const FormatToken *AttrTok = Tok.Next->Next;
 416     if (!AttrTok)
 417       return false;
 418     // C++17 '[[using ns: foo, bar(baz, blech)]]'
 419     // We assume nobody will name an ObjC variable 'using'.
 420     if (AttrTok->startsSequence(tok::kw_using, tok::identifier, tok::colon))
 421       return true;
 422     if (AttrTok->isNot(tok::identifier))
 423       return false;
 424     while (AttrTok && !AttrTok->startsSequence(tok::r_square, tok::r_square)) {
 425       // ObjC message send. We assume nobody will use : in a C++11 attribute
 426       // specifier parameter, although this is technically valid:
 427       // [[foo(:)]].
 428       if (AttrTok->is(tok::colon) ||
 429           AttrTok->startsSequence(tok::identifier, tok::identifier) ||
 430           AttrTok->startsSequence(tok::r_paren, tok::identifier))
 431         return false;
 432       if (AttrTok->is(tok::ellipsis))
 433         return true;
 434       AttrTok = AttrTok->Next;
 435     }
 436     return AttrTok && AttrTok->startsSequence(tok::r_square, tok::r_square);
 437   }
 438
 439   bool parseSquare() {
 440     if (!CurrentToken)
 441       return false;
 442
 443     // A '[' could be an index subscript (after an identifier or after
 444     // ')' or ']'), it could be the start of an Objective-C method
 445     // expression, it could the start of an Objective-C array literal,
 446     // or it could be a C++ attribute specifier [[foo::bar]].
 447     FormatToken *Left = CurrentToken->Previous;
 448     Left->ParentBracket = Contexts.back().ContextKind;
 449     FormatToken *Parent = Left->getPreviousNonComment();
 450
 451     // Cases where '>' is followed by '['.
 452     // In C++, this can happen either in array of templates (foo<int>[10])
 453     // or when array is a nested template type (unique_ptr<type1<type2>[]>).
 454     bool CppArrayTemplates =
 455         Style.isCpp() && Parent && Parent->is(TT_TemplateCloser) &&
 456         (Contexts.back().CanBeExpression || Contexts.back().IsExpression ||
 457          Contexts.back().InTemplateArgument);
 458
 459     bool IsCpp11AttributeSpecifier = isCpp11AttributeSpecifier(*Left) ||
 460                                      Contexts.back().InCpp11AttributeSpecifier;
 461
 462     // Treat C# Attributes [STAThread] much like C++ attributes [[...]].
 463     bool IsCSharp11AttributeSpecifier =
 464         isCSharpAttributeSpecifier(*Left) ||
 465         Contexts.back().InCSharpAttributeSpecifier;
 466
 467     bool InsideInlineASM = Line.startsWith(tok::kw_asm);
 468     bool IsCppStructuredBinding = Left->isCppStructuredBinding(Style);
 469     bool StartsObjCMethodExpr =
 470         !IsCppStructuredBinding && !InsideInlineASM && !CppArrayTemplates &&
 471         Style.isCpp() && !IsCpp11AttributeSpecifier &&
 472         Contexts.back().CanBeExpression && Left->isNot(TT_LambdaLSquare) &&
 473         !CurrentToken->isOneOf(tok::l_brace, tok::r_square) &&
 474         (!Parent ||
 475          Parent->isOneOf(tok::colon, tok::l_square, tok::l_paren,
 476                          tok::kw_return, tok::kw_throw) ||
 477          Parent->isUnaryOperator() ||
 478          // FIXME(bug 36976): ObjC return types shouldn't use TT_CastRParen.
 479          Parent->isOneOf(TT_ObjCForIn, TT_CastRParen) ||
 480          (getBinOpPrecedence(Parent->Tok.getKind(), true, true) >
 481           prec::Unknown));
 482     bool ColonFound = false;
 483
 484     unsigned BindingIncrease = 1;
 485     if (IsCppStructuredBinding) {
 486       Left->Type = TT_StructuredBindingLSquare;
 487     } else if (Left->is(TT_Unknown)) {
 488       if (StartsObjCMethodExpr) {
 489         Left->Type = TT_ObjCMethodExpr;
 490       } else if (IsCpp11AttributeSpecifier) {
 491         Left->Type = TT_AttributeSquare;
 492       } else if (Style.Language == FormatStyle::LK_JavaScript && Parent &&
 493                  Contexts.back().ContextKind == tok::l_brace &&
 494                  Parent->isOneOf(tok::l_brace, tok::comma)) {
 495         Left->Type = TT_JsComputedPropertyName;
 496       } else if (Style.isCpp() && Contexts.back().ContextKind == tok::l_brace &&
 497                  Parent && Parent->isOneOf(tok::l_brace, tok::comma)) {
 498         Left->Type = TT_DesignatedInitializerLSquare;
 499       } else if (IsCSharp11AttributeSpecifier) {
 500         Left->Type = TT_AttributeSquare;
 501       } else if (CurrentToken->is(tok::r_square) && Parent &&
 502                  Parent->is(TT_TemplateCloser)) {
 503         Left->Type = TT_ArraySubscriptLSquare;
 504       } else if (Style.Language == FormatStyle::LK_Proto ||
 505                  Style.Language == FormatStyle::LK_TextProto) {
 506         // Square braces in LK_Proto can either be message field attributes:
 507         //
 508         // optional Aaa aaa = 1 [
 509         //   (aaa) = aaa
 510         // ];
 511         //
 512         // extensions 123 [
 513         //   (aaa) = aaa
 514         // ];
 515         //
 516         // or text proto extensions (in options):
 517         //
 518         // option (Aaa.options) = {
 519         //   [type.type/type] {
 520         //     key: value
 521         //   }
 522         // }
 523         //
 524         // or repeated fields (in options):
 525         //
 526         // option (Aaa.options) = {
 527         //   keys: [ 1, 2, 3 ]
 528         // }
 529         //
 530         // In the first and the third case we want to spread the contents inside
 531         // the square braces; in the second we want to keep them inline.
 532         Left->Type = TT_ArrayInitializerLSquare;
 533         if (!Left->endsSequence(tok::l_square, tok::numeric_constant,
 534                                 tok::equal) &&
 535             !Left->endsSequence(tok::l_square, tok::numeric_constant,
 536                                 tok::identifier) &&
 537             !Left->endsSequence(tok::l_square, tok::colon, TT_SelectorName)) {
 538           Left->Type = TT_ProtoExtensionLSquare;
 539           BindingIncrease = 10;
 540         }
 541       } else if (!CppArrayTemplates && Parent &&
 542                  Parent->isOneOf(TT_BinaryOperator, TT_TemplateCloser, tok::at,
 543                                  tok::comma, tok::l_paren, tok::l_square,
 544                                  tok::question, tok::colon, tok::kw_return,
 545                                  // Should only be relevant to JavaScript:
 546                                  tok::kw_default)) {
 547         Left->Type = TT_ArrayInitializerLSquare;
 548       } else {
 549         BindingIncrease = 10;
 550         Left->Type = TT_ArraySubscriptLSquare;
 551       }
 552     }
 553
 554     ScopedContextCreator ContextCreator(*this, tok::l_square, BindingIncrease);
 555     Contexts.back().IsExpression = true;
 556     if (Style.Language == FormatStyle::LK_JavaScript && Parent &&
 557         Parent->is(TT_JsTypeColon))
 558       Contexts.back().IsExpression = false;
 559
 560     Contexts.back().ColonIsObjCMethodExpr = StartsObjCMethodExpr;
 561     Contexts.back().InCpp11AttributeSpecifier = IsCpp11AttributeSpecifier;
 562     Contexts.back().InCSharpAttributeSpecifier = IsCSharp11AttributeSpecifier;
 563
 564     while (CurrentToken) {
 565       if (CurrentToken->is(tok::r_square)) {
 566         if (IsCpp11AttributeSpecifier)
 567           CurrentToken->Type = TT_AttributeSquare;
 568         if (IsCSharp11AttributeSpecifier)
 569           CurrentToken->Type = TT_AttributeSquare;
 570         else if (((CurrentToken->Next &&
 571                    CurrentToken->Next->is(tok::l_paren)) ||
 572                   (CurrentToken->Previous &&
 573                    CurrentToken->Previous->Previous == Left)) &&
 574                  Left->is(TT_ObjCMethodExpr)) {
 575           // An ObjC method call is rarely followed by an open parenthesis. It
 576           // also can't be composed of just one token, unless it's a macro that
 577           // will be expanded to more tokens.
 578           // FIXME: Do we incorrectly label ":" with this?
 579           StartsObjCMethodExpr = false;
 580           Left->Type = TT_Unknown;
 581         }
 582         if (StartsObjCMethodExpr && CurrentToken->Previous != Left) {
 583           CurrentToken->Type = TT_ObjCMethodExpr;
 584           // If we haven't seen a colon yet, make sure the last identifier
 585           // before the r_square is tagged as a selector name component.
 586           if (!ColonFound && CurrentToken->Previous &&
 587               CurrentToken->Previous->is(TT_Unknown) &&
 588               canBeObjCSelectorComponent(*CurrentToken->Previous))
 589             CurrentToken->Previous->Type = TT_SelectorName;
 590           // determineStarAmpUsage() thinks that '*' '[' is allocating an
 591           // array of pointers, but if '[' starts a selector then '*' is a
 592           // binary operator.
 593           if (Parent && Parent->is(TT_PointerOrReference))
 594             Parent->Type = TT_BinaryOperator;
 595         }
 596         // An arrow after an ObjC method expression is not a lambda arrow.
 597         if (CurrentToken->Type == TT_ObjCMethodExpr && CurrentToken->Next &&
 598             CurrentToken->Next->is(TT_LambdaArrow))
 599           CurrentToken->Next->Type = TT_Unknown;
 600         Left->MatchingParen = CurrentToken;
 601         CurrentToken->MatchingParen = Left;
 602         // FirstObjCSelectorName is set when a colon is found. This does
 603         // not work, however, when the method has no parameters.
 604         // Here, we set FirstObjCSelectorName when the end of the method call is
 605         // reached, in case it was not set already.
 606         if (!Contexts.back().FirstObjCSelectorName) {
 607           FormatToken *Previous = CurrentToken->getPreviousNonComment();
 608           if (Previous && Previous->is(TT_SelectorName)) {
 609             Previous->ObjCSelectorNameParts = 1;
 610             Contexts.back().FirstObjCSelectorName = Previous;
 611           }
 612         } else {
 613           Left->ParameterCount =
 614               Contexts.back().FirstObjCSelectorName->ObjCSelectorNameParts;
 615         }
 616         if (Contexts.back().FirstObjCSelectorName) {
 617           Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName =
 618               Contexts.back().LongestObjCSelectorName;
 619           if (Left->BlockParameterCount > 1)
 620             Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName = 0;
 621         }
 622         next();
 623         return true;
 624       }
 625       if (CurrentToken->isOneOf(tok::r_paren, tok::r_brace))
 626         return false;
 627       if (CurrentToken->is(tok::colon)) {
 628         if (IsCpp11AttributeSpecifier &&
 629             CurrentToken->endsSequence(tok::colon, tok::identifier,
 630                                        tok::kw_using)) {
 631           // Remember that this is a [[using ns: foo]] C++ attribute, so we
 632           // don't add a space before the colon (unlike other colons).
 633           CurrentToken->Type = TT_AttributeColon;
 634         } else if (Left->isOneOf(TT_ArraySubscriptLSquare,
 635                                  TT_DesignatedInitializerLSquare)) {
 636           Left->Type = TT_ObjCMethodExpr;
 637           StartsObjCMethodExpr = true;
 638           Contexts.back().ColonIsObjCMethodExpr = true;
 639           if (Parent && Parent->is(tok::r_paren))
 640             // FIXME(bug 36976): ObjC return types shouldn't use TT_CastRParen.
 641             Parent->Type = TT_CastRParen;
 642         }
 643         ColonFound = true;
 644       }
 645       if (CurrentToken->is(tok::comma) && Left->is(TT_ObjCMethodExpr) &&
 646           !ColonFound)
 647         Left->Type = TT_ArrayInitializerLSquare;
 648       FormatToken *Tok = CurrentToken;
 649       if (!consumeToken())
 650         return false;
 651       updateParameterCount(Left, Tok);
 652     }
 653     return false;
 654   }
 655
 656   bool parseBrace() {
 657     if (CurrentToken) {
 658       FormatToken *Left = CurrentToken->Previous;
 659       Left->ParentBracket = Contexts.back().ContextKind;
 660
 661       if (Contexts.back().CaretFound)
 662         Left->Type = TT_ObjCBlockLBrace;
 663       Contexts.back().CaretFound = false;
 664
 665       ScopedContextCreator ContextCreator(*this, tok::l_brace, 1);
 666       Contexts.back().ColonIsDictLiteral = true;
 667       if (Left->BlockKind == BK_BracedInit)
 668         Contexts.back().IsExpression = true;
 669       if (Style.Language == FormatStyle::LK_JavaScript && Left->Previous &&
 670           Left->Previous->is(TT_JsTypeColon))
 671         Contexts.back().IsExpression = false;
 672
 673       while (CurrentToken) {
 674         if (CurrentToken->is(tok::r_brace)) {
 675           Left->MatchingParen = CurrentToken;
 676           CurrentToken->MatchingParen = Left;
 677           next();
 678           return true;
 679         }
 680         if (CurrentToken->isOneOf(tok::r_paren, tok::r_square))
 681           return false;
 682         updateParameterCount(Left, CurrentToken);
 683         if (CurrentToken->isOneOf(tok::colon, tok::l_brace, tok::less)) {
 684           FormatToken *Previous = CurrentToken->getPreviousNonComment();
 685           if (Previous->is(TT_JsTypeOptionalQuestion))
 686             Previous = Previous->getPreviousNonComment();
 687           if ((CurrentToken->is(tok::colon) &&
 688                (!Contexts.back().ColonIsDictLiteral || !Style.isCpp())) ||
 689               Style.Language == FormatStyle::LK_Proto ||
 690               Style.Language == FormatStyle::LK_TextProto) {
 691             Left->Type = TT_DictLiteral;
 692             if (Previous->Tok.getIdentifierInfo() ||
 693                 Previous->is(tok::string_literal))
 694               Previous->Type = TT_SelectorName;
 695           }
 696           if (CurrentToken->is(tok::colon) ||
 697               Style.Language == FormatStyle::LK_JavaScript)
 698             Left->Type = TT_DictLiteral;
 699         }
 700         if (CurrentToken->is(tok::comma) &&
 701             Style.Language == FormatStyle::LK_JavaScript)
 702           Left->Type = TT_DictLiteral;
 703         if (!consumeToken())
 704           return false;
 705       }
 706     }
 707     return true;
 708   }
 709
 710   void updateParameterCount(FormatToken *Left, FormatToken *Current) {
 711     // For ObjC methods, the number of parameters is calculated differently as
 712     // method declarations have a different structure (the parameters are not
 713     // inside a bracket scope).
 714     if (Current->is(tok::l_brace) && Current->BlockKind == BK_Block)
 715       ++Left->BlockParameterCount;
 716     if (Current->is(tok::comma)) {
 717       ++Left->ParameterCount;
 718       if (!Left->Role)
 719         Left->Role.reset(new CommaSeparatedList(Style));
 720       Left->Role->CommaFound(Current);
 721     } else if (Left->ParameterCount == 0 && Current->isNot(tok::comment)) {
 722       Left->ParameterCount = 1;
 723     }
 724   }
 725
 726   bool parseConditional() {
 727     while (CurrentToken) {
 728       if (CurrentToken->is(tok::colon)) {
 729         CurrentToken->Type = TT_ConditionalExpr;
 730         next();
 731         return true;
 732       }
 733       if (!consumeToken())
 734         return false;
 735     }
 736     return false;
 737   }
 738
 739   bool parseTemplateDeclaration() {
 740     if (CurrentToken && CurrentToken->is(tok::less)) {
 741       CurrentToken->Type = TT_TemplateOpener;
 742       next();
 743       if (!parseAngle())
 744         return false;
 745       if (CurrentToken)
 746         CurrentToken->Previous->ClosesTemplateDeclaration = true;
 747       return true;
 748     }
 749     return false;
 750   }
 751
 752   bool consumeToken() {
 753     FormatToken *Tok = CurrentToken;
 754     next();
 755     switch (Tok->Tok.getKind()) {
 756     case tok::plus:
 757     case tok::minus:
 758       if (!Tok->Previous && Line.MustBeDeclaration)
 759         Tok->Type = TT_ObjCMethodSpecifier;
 760       break;
 761     case tok::colon:
 762       if (!Tok->Previous)
 763         return false;
 764       // Colons from ?: are handled in parseConditional().
 765       if (Style.Language == FormatStyle::LK_JavaScript) {
 766         if (Contexts.back().ColonIsForRangeExpr || // colon in for loop
 767             (Contexts.size() == 1 &&               // switch/case labels
 768              !Line.First->isOneOf(tok::kw_enum, tok::kw_case)) ||
 769             Contexts.back().ContextKind == tok::l_paren ||  // function params
 770             Contexts.back().ContextKind == tok::l_square || // array type
 771             (!Contexts.back().IsExpression &&
 772              Contexts.back().ContextKind == tok::l_brace) || // object type
 773             (Contexts.size() == 1 &&
 774              Line.MustBeDeclaration)) { // method/property declaration
 775           Contexts.back().IsExpression = false;
 776           Tok->Type = TT_JsTypeColon;
 777           break;
 778         }
 779       }
 780       if (Contexts.back().ColonIsDictLiteral ||
 781           Style.Language == FormatStyle::LK_Proto ||
 782           Style.Language == FormatStyle::LK_TextProto) {
 783         Tok->Type = TT_DictLiteral;
 784         if (Style.Language == FormatStyle::LK_TextProto) {
 785           if (FormatToken *Previous = Tok->getPreviousNonComment())
 786             Previous->Type = TT_SelectorName;
 787         }
 788       } else if (Contexts.back().ColonIsObjCMethodExpr ||
 789                  Line.startsWith(TT_ObjCMethodSpecifier)) {
 790         Tok->Type = TT_ObjCMethodExpr;
 791         const FormatToken *BeforePrevious = Tok->Previous->Previous;
 792         // Ensure we tag all identifiers in method declarations as
 793         // TT_SelectorName.
 794         bool UnknownIdentifierInMethodDeclaration =
 795             Line.startsWith(TT_ObjCMethodSpecifier) &&
 796             Tok->Previous->is(tok::identifier) && Tok->Previous->is(TT_Unknown);
 797         if (!BeforePrevious ||
 798             // FIXME(bug 36976): ObjC return types shouldn't use TT_CastRParen.
 799             !(BeforePrevious->is(TT_CastRParen) ||
 800               (BeforePrevious->is(TT_ObjCMethodExpr) &&
 801                BeforePrevious->is(tok::colon))) ||
 802             BeforePrevious->is(tok::r_square) ||
 803             Contexts.back().LongestObjCSelectorName == 0 ||
 804             UnknownIdentifierInMethodDeclaration) {
 805           Tok->Previous->Type = TT_SelectorName;
 806           if (!Contexts.back().FirstObjCSelectorName)
 807             Contexts.back().FirstObjCSelectorName = Tok->Previous;
 808           else if (Tok->Previous->ColumnWidth >
 809                    Contexts.back().LongestObjCSelectorName)
 810             Contexts.back().LongestObjCSelectorName =
 811                 Tok->Previous->ColumnWidth;
 812           Tok->Previous->ParameterIndex =
 813               Contexts.back().FirstObjCSelectorName->ObjCSelectorNameParts;
 814           ++Contexts.back().FirstObjCSelectorName->ObjCSelectorNameParts;
 815         }
 816       } else if (Contexts.back().ColonIsForRangeExpr) {
 817         Tok->Type = TT_RangeBasedForLoopColon;
 818       } else if (CurrentToken && CurrentToken->is(tok::numeric_constant)) {
 819         Tok->Type = TT_BitFieldColon;
 820       } else if (Contexts.size() == 1 &&
 821                  !Line.First->isOneOf(tok::kw_enum, tok::kw_case)) {
 822         if (Tok->getPreviousNonComment()->isOneOf(tok::r_paren,
 823                                                   tok::kw_noexcept))
 824           Tok->Type = TT_CtorInitializerColon;
 825         else
 826           Tok->Type = TT_InheritanceColon;
 827       } else if (canBeObjCSelectorComponent(*Tok->Previous) && Tok->Next &&
 828                  (Tok->Next->isOneOf(tok::r_paren, tok::comma) ||
 829                   (canBeObjCSelectorComponent(*Tok->Next) && Tok->Next->Next &&
 830                    Tok->Next->Next->is(tok::colon)))) {
 831         // This handles a special macro in ObjC code where selectors including
 832         // the colon are passed as macro arguments.
 833         Tok->Type = TT_ObjCMethodExpr;
 834       } else if (Contexts.back().ContextKind == tok::l_paren) {
 835         Tok->Type = TT_InlineASMColon;
 836       }
 837       break;
 838     case tok::pipe:
 839     case tok::amp:
 840       // | and & in declarations/type expressions represent union and
 841       // intersection types, respectively.
 842       if (Style.Language == FormatStyle::LK_JavaScript &&
 843           !Contexts.back().IsExpression)
 844         Tok->Type = TT_JsTypeOperator;
 845       break;
 846     case tok::kw_if:
 847     case tok::kw_while:
 848       if (Tok->is(tok::kw_if) && CurrentToken &&
 849           CurrentToken->isOneOf(tok::kw_constexpr, tok::identifier))
 850         next();
 851       if (CurrentToken && CurrentToken->is(tok::l_paren)) {
 852         next();
 853         if (!parseParens(/*LookForDecls=*/true))
 854           return false;
 855       }
 856       break;
 857     case tok::kw_for:
 858       if (Style.Language == FormatStyle::LK_JavaScript) {
 859         // x.for and {for: ...}
 860         if ((Tok->Previous && Tok->Previous->is(tok::period)) ||
 861             (Tok->Next && Tok->Next->is(tok::colon)))
 862           break;
 863         // JS' for await ( ...
 864         if (CurrentToken && CurrentToken->is(Keywords.kw_await))
 865           next();
 866       }
 867       Contexts.back().ColonIsForRangeExpr = true;
 868       next();
 869       if (!parseParens())
 870         return false;
 871       break;
 872     case tok::l_paren:
 873       // When faced with 'operator()()', the kw_operator handler incorrectly
 874       // marks the first l_paren as a OverloadedOperatorLParen. Here, we make
 875       // the first two parens OverloadedOperators and the second l_paren an
 876       // OverloadedOperatorLParen.
 877       if (Tok->Previous && Tok->Previous->is(tok::r_paren) &&
 878           Tok->Previous->MatchingParen &&
 879           Tok->Previous->MatchingParen->is(TT_OverloadedOperatorLParen)) {
 880         Tok->Previous->Type = TT_OverloadedOperator;
 881         Tok->Previous->MatchingParen->Type = TT_OverloadedOperator;
 882         Tok->Type = TT_OverloadedOperatorLParen;
 883       }
 884
 885       if (!parseParens())
 886         return false;
 887       if (Line.MustBeDeclaration && Contexts.size() == 1 &&
 888           !Contexts.back().IsExpression && !Line.startsWith(TT_ObjCProperty) &&
 889           (!Tok->Previous ||
 890            !Tok->Previous->isOneOf(tok::kw_decltype, tok::kw___attribute,
 891                                    TT_LeadingJavaAnnotation)))
 892         Line.MightBeFunctionDecl = true;
 893       break;
 894     case tok::l_square:
 895       if (!parseSquare())
 896         return false;
 897       break;
 898     case tok::l_brace:
 899       if (Style.Language == FormatStyle::LK_TextProto) {
 900         FormatToken *Previous = Tok->getPreviousNonComment();
 901         if (Previous && Previous->Type != TT_DictLiteral)
 902           Previous->Type = TT_SelectorName;
 903       }
 904       if (!parseBrace())
 905         return false;
 906       break;
 907     case tok::less:
 908       if (parseAngle()) {
 909         Tok->Type = TT_TemplateOpener;
 910         // In TT_Proto, we must distignuish between:
 911         //   map<key, value>
 912         //   msg < item: data >
 913         //   msg: < item: data >
 914         // In TT_TextProto, map<key, value> does not occur.
 915         if (Style.Language == FormatStyle::LK_TextProto ||
 916             (Style.Language == FormatStyle::LK_Proto && Tok->Previous &&
 917              Tok->Previous->isOneOf(TT_SelectorName, TT_DictLiteral))) {
 918           Tok->Type = TT_DictLiteral;
 919           FormatToken *Previous = Tok->getPreviousNonComment();
 920           if (Previous && Previous->Type != TT_DictLiteral)
 921             Previous->Type = TT_SelectorName;
 922         }
 923       } else {
 924         Tok->Type = TT_BinaryOperator;
 925         NonTemplateLess.insert(Tok);
 926         CurrentToken = Tok;
 927         next();
 928       }
 929       break;
 930     case tok::r_paren:
 931     case tok::r_square:
 932       return false;
 933     case tok::r_brace:
 934       // Lines can start with '}'.
 935       if (Tok->Previous)
 936         return false;
 937       break;
 938     case tok::greater:
 939       if (Style.Language != FormatStyle::LK_TextProto)
 940         Tok->Type = TT_BinaryOperator;
 941       if (Tok->Previous && Tok->Previous->is(TT_TemplateCloser))
 942         Tok->SpacesRequiredBefore = 1;
 943       break;
 944     case tok::kw_operator:
 945       if (Style.Language == FormatStyle::LK_TextProto ||
 946           Style.Language == FormatStyle::LK_Proto)
 947         break;
 948       while (CurrentToken &&
 949              !CurrentToken->isOneOf(tok::l_paren, tok::semi, tok::r_paren)) {
 950         if (CurrentToken->isOneOf(tok::star, tok::amp))
 951           CurrentToken->Type = TT_PointerOrReference;
 952         consumeToken();
 953         if (CurrentToken && CurrentToken->Previous->isOneOf(
 954                                 TT_BinaryOperator, TT_UnaryOperator, tok::comma,
 955                                 tok::star, tok::arrow, tok::amp, tok::ampamp))
 956           CurrentToken->Previous->Type = TT_OverloadedOperator;
 957       }
 958       if (CurrentToken) {
 959         CurrentToken->Type = TT_OverloadedOperatorLParen;
 960         if (CurrentToken->Previous->is(TT_BinaryOperator))
 961           CurrentToken->Previous->Type = TT_OverloadedOperator;
 962       }
 963       break;
 964     case tok::question:
 965       if (Style.Language == FormatStyle::LK_JavaScript && Tok->Next &&
 966           Tok->Next->isOneOf(tok::semi, tok::comma, tok::colon, tok::r_paren,
 967                              tok::r_brace)) {
 968         // Question marks before semicolons, colons, etc. indicate optional
 969         // types (fields, parameters), e.g.
 970         //   function(x?: string, y?) {...}
 971         //   class X { y?; }
 972         Tok->Type = TT_JsTypeOptionalQuestion;
 973         break;
 974       }
 975       // Declarations cannot be conditional expressions, this can only be part
 976       // of a type declaration.
 977       if (Line.MustBeDeclaration && !Contexts.back().IsExpression &&
 978           Style.Language == FormatStyle::LK_JavaScript)
 979         break;
 980       parseConditional();
 981       break;
 982     case tok::kw_template:
 983       parseTemplateDeclaration();
 984       break;
 985     case tok::comma:
 986       if (Contexts.back().InCtorInitializer)
 987         Tok->Type = TT_CtorInitializerComma;
 988       else if (Contexts.back().InInheritanceList)
 989         Tok->Type = TT_InheritanceComma;
 990       else if (Contexts.back().FirstStartOfName &&
 991                (Contexts.size() == 1 || Line.startsWith(tok::kw_for))) {
 992         Contexts.back().FirstStartOfName->PartOfMultiVariableDeclStmt = true;
 993         Line.IsMultiVariableDeclStmt = true;
 994       }
 995       if (Contexts.back().IsForEachMacro)
 996         Contexts.back().IsExpression = true;
 997       break;
 998     case tok::identifier:
 999       if (Tok->isOneOf(Keywords.kw___has_include,
1000                        Keywords.kw___has_include_next)) {
1001         parseHasInclude();
1002       }
1003       break;
1004     default:
1005       break;
1006     }
1007     return true;
1008   }
1009
1010   void parseIncludeDirective() {
1011     if (CurrentToken && CurrentToken->is(tok::less)) {
1012       next();
1013       while (CurrentToken) {
1014         // Mark tokens up to the trailing line comments as implicit string
1015         // literals.
1016         if (CurrentToken->isNot(tok::comment) &&
1017             !CurrentToken->TokenText.startswith("//"))
1018           CurrentToken->Type = TT_ImplicitStringLiteral;
1019         next();
1020       }
1021     }
1022   }
1023
1024   void parseWarningOrError() {
1025     next();
1026     // We still want to format the whitespace left of the first token of the
1027     // warning or error.
1028     next();
1029     while (CurrentToken) {
1030       CurrentToken->Type = TT_ImplicitStringLiteral;
1031       next();
1032     }
1033   }
1034
1035   void parsePragma() {
1036     next(); // Consume "pragma".
1037     if (CurrentToken &&
1038         CurrentToken->isOneOf(Keywords.kw_mark, Keywords.kw_option)) {
1039       bool IsMark = CurrentToken->is(Keywords.kw_mark);
1040       next(); // Consume "mark".
1041       next(); // Consume first token (so we fix leading whitespace).
1042       while (CurrentToken) {
1043         if (IsMark || CurrentToken->Previous->is(TT_BinaryOperator))
1044           CurrentToken->Type = TT_ImplicitStringLiteral;
1045         next();
1046       }
1047     }
1048   }
1049
1050   void parseHasInclude() {
1051     if (!CurrentToken || !CurrentToken->is(tok::l_paren))
1052       return;
1053     next(); // '('
1054     parseIncludeDirective();
1055     next(); // ')'
1056   }
1057
1058   LineType parsePreprocessorDirective() {
1059     bool IsFirstToken = CurrentToken->IsFirst;
1060     LineType Type = LT_PreprocessorDirective;
1061     next();
1062     if (!CurrentToken)
1063       return Type;
1064
1065     if (Style.Language == FormatStyle::LK_JavaScript && IsFirstToken) {
1066       // JavaScript files can contain shebang lines of the form:
1067       // #!/usr/bin/env node
1068       // Treat these like C++ #include directives.
1069       while (CurrentToken) {
1070         // Tokens cannot be comments here.
1071         CurrentToken->Type = TT_ImplicitStringLiteral;
1072         next();
1073       }
1074       return LT_ImportStatement;
1075     }
1076
1077     if (CurrentToken->Tok.is(tok::numeric_constant)) {
1078       CurrentToken->SpacesRequiredBefore = 1;
1079       return Type;
1080     }
1081     // Hashes in the middle of a line can lead to any strange token
1082     // sequence.
1083     if (!CurrentToken->Tok.getIdentifierInfo())
1084       return Type;
1085     switch (CurrentToken->Tok.getIdentifierInfo()->getPPKeywordID()) {
1086     case tok::pp_include:
1087     case tok::pp_include_next:
1088     case tok::pp_import:
1089       next();
1090       parseIncludeDirective();
1091       Type = LT_ImportStatement;
1092       break;
1093     case tok::pp_error:
1094     case tok::pp_warning:
1095       parseWarningOrError();
1096       break;
1097     case tok::pp_pragma:
1098       parsePragma();
1099       break;
1100     case tok::pp_if:
1101     case tok::pp_elif:
1102       Contexts.back().IsExpression = true;
1103       next();
1104       parseLine();
1105       break;
1106     default:
1107       break;
1108     }
1109     while (CurrentToken) {
1110       FormatToken *Tok = CurrentToken;
1111       next();
1112       if (Tok->is(tok::l_paren))
1113         parseParens();
1114       else if (Tok->isOneOf(Keywords.kw___has_include,
1115                             Keywords.kw___has_include_next))
1116         parseHasInclude();
1117     }
1118     return Type;
1119   }
1120
1121 public:
1122   LineType parseLine() {
1123     if (!CurrentToken)
1124       return LT_Invalid;
1125     NonTemplateLess.clear();
1126     if (CurrentToken->is(tok::hash))
1127       return parsePreprocessorDirective();
1128
1129     // Directly allow to 'import <string-literal>' to support protocol buffer
1130     // definitions (github.com/google/protobuf) or missing "#" (either way we
1131     // should not break the line).
1132     IdentifierInfo *Info = CurrentToken->Tok.getIdentifierInfo();
1133     if ((Style.Language == FormatStyle::LK_Java &&
1134          CurrentToken->is(Keywords.kw_package)) ||
1135         (Info && Info->getPPKeywordID() == tok::pp_import &&
1136          CurrentToken->Next &&
1137          CurrentToken->Next->isOneOf(tok::string_literal, tok::identifier,
1138                                      tok::kw_static))) {
1139       next();
1140       parseIncludeDirective();
1141       return LT_ImportStatement;
1142     }
1143
1144     // If this line starts and ends in '<' and '>', respectively, it is likely
1145     // part of "#define <a/b.h>".
1146     if (CurrentToken->is(tok::less) && Line.Last->is(tok::greater)) {
1147       parseIncludeDirective();
1148       return LT_ImportStatement;
1149     }
1150
1151     // In .proto files, top-level options and package statements are very
1152     // similar to import statements and should not be line-wrapped.
1153     if (Style.Language == FormatStyle::LK_Proto && Line.Level == 0 &&
1154         CurrentToken->isOneOf(Keywords.kw_option, Keywords.kw_package)) {
1155       next();
1156       if (CurrentToken && CurrentToken->is(tok::identifier)) {
1157         while (CurrentToken)
1158           next();
1159         return LT_ImportStatement;
1160       }
1161     }
1162
1163     bool KeywordVirtualFound = false;
1164     bool ImportStatement = false;
1165
1166     // import {...} from '...';
1167     if (Style.Language == FormatStyle::LK_JavaScript &&
1168         CurrentToken->is(Keywords.kw_import))
1169       ImportStatement = true;
1170
1171     while (CurrentToken) {
1172       if (CurrentToken->is(tok::kw_virtual))
1173         KeywordVirtualFound = true;
1174       if (Style.Language == FormatStyle::LK_JavaScript) {
1175         // export {...} from '...';
1176         // An export followed by "from 'some string';" is a re-export from
1177         // another module identified by a URI and is treated as a
1178         // LT_ImportStatement (i.e. prevent wraps on it for long URIs).
1179         // Just "export {...};" or "export class ..." should not be treated as
1180         // an import in this sense.
1181         if (Line.First->is(tok::kw_export) &&
1182             CurrentToken->is(Keywords.kw_from) && CurrentToken->Next &&
1183             CurrentToken->Next->isStringLiteral())
1184           ImportStatement = true;
1185         if (isClosureImportStatement(*CurrentToken))
1186           ImportStatement = true;
1187       }
1188       if (!consumeToken())
1189         return LT_Invalid;
1190     }
1191     if (KeywordVirtualFound)
1192       return LT_VirtualFunctionDecl;
1193     if (ImportStatement)
1194       return LT_ImportStatement;
1195
1196     if (Line.startsWith(TT_ObjCMethodSpecifier)) {
1197       if (Contexts.back().FirstObjCSelectorName)
1198         Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName =
1199             Contexts.back().LongestObjCSelectorName;
1200       return LT_ObjCMethodDecl;
1201     }
1202
1203     return LT_Other;
1204   }
1205
1206 private:
1207   bool isClosureImportStatement(const FormatToken &Tok) {
1208     // FIXME: Closure-library specific stuff should not be hard-coded but be
1209     // configurable.
1210     return Tok.TokenText == "goog" && Tok.Next && Tok.Next->is(tok::period) &&
1211            Tok.Next->Next &&
1212            (Tok.Next->Next->TokenText == "module" ||
1213             Tok.Next->Next->TokenText == "provide" ||
1214             Tok.Next->Next->TokenText == "require" ||
1215             Tok.Next->Next->TokenText == "requireType" ||
1216             Tok.Next->Next->TokenText == "forwardDeclare") &&
1217            Tok.Next->Next->Next && Tok.Next->Next->Next->is(tok::l_paren);
1218   }
1219
1220   void resetTokenMetadata(FormatToken *Token) {
1221     if (!Token)
1222       return;
1223
1224     // Reset token type in case we have already looked at it and then
1225     // recovered from an error (e.g. failure to find the matching >).
1226     if (!CurrentToken->isOneOf(
1227             TT_LambdaLSquare, TT_LambdaLBrace, TT_ForEachMacro,
1228             TT_TypenameMacro, TT_FunctionLBrace, TT_ImplicitStringLiteral,
1229             TT_InlineASMBrace, TT_JsFatArrow, TT_LambdaArrow, TT_NamespaceMacro,
1230             TT_OverloadedOperator, TT_RegexLiteral, TT_TemplateString,
1231             TT_ObjCStringLiteral))
1232       CurrentToken->Type = TT_Unknown;
1233     CurrentToken->Role.reset();
1234     CurrentToken->MatchingParen = nullptr;
1235     CurrentToken->FakeLParens.clear();
1236     CurrentToken->FakeRParens = 0;
1237   }
1238
1239   void next() {
1240     if (CurrentToken) {
1241       CurrentToken->NestingLevel = Contexts.size() - 1;
1242       CurrentToken->BindingStrength = Contexts.back().BindingStrength;
1243       modifyContext(*CurrentToken);
1244       determineTokenType(*CurrentToken);
1245       CurrentToken = CurrentToken->Next;
1246     }
1247
1248     resetTokenMetadata(CurrentToken);
1249   }
1250
1251   /// A struct to hold information valid in a specific context, e.g.
1252   /// a pair of parenthesis.
1253   struct Context {
1254     Context(tok::TokenKind ContextKind, unsigned BindingStrength,
1255             bool IsExpression)
1256         : ContextKind(ContextKind), BindingStrength(BindingStrength),
1257           IsExpression(IsExpression) {}
1258
1259     tok::TokenKind ContextKind;
1260     unsigned BindingStrength;
1261     bool IsExpression;
1262     unsigned LongestObjCSelectorName = 0;
1263     bool ColonIsForRangeExpr = false;
1264     bool ColonIsDictLiteral = false;
1265     bool ColonIsObjCMethodExpr = false;
1266     FormatToken *FirstObjCSelectorName = nullptr;
1267     FormatToken *FirstStartOfName = nullptr;
1268     bool CanBeExpression = true;
1269     bool InTemplateArgument = false;
1270     bool InCtorInitializer = false;
1271     bool InInheritanceList = false;
1272     bool CaretFound = false;
1273     bool IsForEachMacro = false;
1274     bool InCpp11AttributeSpecifier = false;
1275     bool InCSharpAttributeSpecifier = false;
1276   };
1277
1278   /// Puts a new \c Context onto the stack \c Contexts for the lifetime
1279   /// of each instance.
1280   struct ScopedContextCreator {
1281     AnnotatingParser &P;
1282
1283     ScopedContextCreator(AnnotatingParser &P, tok::TokenKind ContextKind,
1284                          unsigned Increase)
1285         : P(P) {
1286       P.Contexts.push_back(Context(ContextKind,
1287                                    P.Contexts.back().BindingStrength + Increase,
1288                                    P.Contexts.back().IsExpression));
1289     }
1290
1291     ~ScopedContextCreator() { P.Contexts.pop_back(); }
1292   };
1293
1294   void modifyContext(const FormatToken &Current) {
1295     if (Current.getPrecedence() == prec::Assignment &&
1296         !Line.First->isOneOf(tok::kw_template, tok::kw_using, tok::kw_return) &&
1297         // Type aliases use `type X = ...;` in TypeScript and can be exported
1298         // using `export type ...`.
1299         !(Style.Language == FormatStyle::LK_JavaScript &&
1300           (Line.startsWith(Keywords.kw_type, tok::identifier) ||
1301            Line.startsWith(tok::kw_export, Keywords.kw_type,
1302                            tok::identifier))) &&
1303         (!Current.Previous || Current.Previous->isNot(tok::kw_operator))) {
1304       Contexts.back().IsExpression = true;
1305       if (!Line.startsWith(TT_UnaryOperator)) {
1306         for (FormatToken *Previous = Current.Previous;
1307              Previous && Previous->Previous &&
1308              !Previous->Previous->isOneOf(tok::comma, tok::semi);
1309              Previous = Previous->Previous) {
1310           if (Previous->isOneOf(tok::r_square, tok::r_paren)) {
1311             Previous = Previous->MatchingParen;
1312             if (!Previous)
1313               break;
1314           }
1315           if (Previous->opensScope())
1316             break;
1317           if (Previous->isOneOf(TT_BinaryOperator, TT_UnaryOperator) &&
1318               Previous->isOneOf(tok::star, tok::amp, tok::ampamp) &&
1319               Previous->Previous && Previous->Previous->isNot(tok::equal))
1320             Previous->Type = TT_PointerOrReference;
1321         }
1322       }
1323     } else if (Current.is(tok::lessless) &&
1324                (!Current.Previous || !Current.Previous->is(tok::kw_operator))) {
1325       Contexts.back().IsExpression = true;
1326     } else if (Current.isOneOf(tok::kw_return, tok::kw_throw)) {
1327       Contexts.back().IsExpression = true;
1328     } else if (Current.is(TT_TrailingReturnArrow)) {
1329       Contexts.back().IsExpression = false;
1330     } else if (Current.is(TT_LambdaArrow) || Current.is(Keywords.kw_assert)) {
1331       Contexts.back().IsExpression = Style.Language == FormatStyle::LK_Java;
1332     } else if (Current.Previous &&
1333                Current.Previous->is(TT_CtorInitializerColon)) {
1334       Contexts.back().IsExpression = true;
1335       Contexts.back().InCtorInitializer = true;
1336     } else if (Current.Previous && Current.Previous->is(TT_InheritanceColon)) {
1337       Contexts.back().InInheritanceList = true;
1338     } else if (Current.isOneOf(tok::r_paren, tok::greater, tok::comma)) {
1339       for (FormatToken *Previous = Current.Previous;
1340            Previous && Previous->isOneOf(tok::star, tok::amp);
1341            Previous = Previous->Previous)
1342         Previous->Type = TT_PointerOrReference;
1343       if (Line.MustBeDeclaration && !Contexts.front().InCtorInitializer)
1344         Contexts.back().IsExpression = false;
1345     } else if (Current.is(tok::kw_new)) {
1346       Contexts.back().CanBeExpression = false;
1347     } else if (Current.is(tok::semi) ||
1348                (Current.is(tok::exclaim) && Current.Previous &&
1349                 !Current.Previous->is(tok::kw_operator))) {
1350       // This should be the condition or increment in a for-loop.
1351       // But not operator !() (can't use TT_OverloadedOperator here as its not
1352       // been annotated yet).
1353       Contexts.back().IsExpression = true;
1354     }
1355   }
1356
1357   static FormatToken *untilMatchingParen(FormatToken *Current) {
1358     // Used when `MatchingParen` is not yet established.
1359     int ParenLevel = 0;
1360     while (Current) {
1361       if (Current->is(tok::l_paren))
1362         ParenLevel++;
1363       if (Current->is(tok::r_paren))
1364         ParenLevel--;
1365       if (ParenLevel < 1)
1366         break;
1367       Current = Current->Next;
1368     }
1369     return Current;
1370   }
1371
1372   static bool isDeductionGuide(FormatToken &Current) {
1373     // Look for a deduction guide template<T> A(...) -> A<...>;
1374     if (Current.Previous && Current.Previous->is(tok::r_paren) &&
1375         Current.startsSequence(tok::arrow, tok::identifier, tok::less)) {
1376       // Find the TemplateCloser.
1377       FormatToken *TemplateCloser = Current.Next->Next;
1378       int NestingLevel = 0;
1379       while (TemplateCloser) {
1380         // Skip over an expressions in parens  A<(3 < 2)>;
1381         if (TemplateCloser->is(tok::l_paren)) {
1382           // No Matching Paren yet so skip to matching paren
1383           TemplateCloser = untilMatchingParen(TemplateCloser);
1384         }
1385         if (TemplateCloser->is(tok::less))
1386           NestingLevel++;
1387         if (TemplateCloser->is(tok::greater))
1388           NestingLevel--;
1389         if (NestingLevel < 1)
1390           break;
1391         TemplateCloser = TemplateCloser->Next;
1392       }
1393       // Assuming we have found the end of the template ensure its followed
1394       // with a semi-colon.
1395       if (TemplateCloser && TemplateCloser->Next &&
1396           TemplateCloser->Next->is(tok::semi) &&
1397           Current.Previous->MatchingParen) {
1398         // Determine if the identifier `A` prior to the A<..>; is the same as
1399         // prior to the A(..)
1400         FormatToken *LeadingIdentifier =
1401             Current.Previous->MatchingParen->Previous;
1402
1403         // Differentiate a deduction guide by seeing the
1404         // > of the template prior to the leading identifier.
1405         if (LeadingIdentifier) {
1406           FormatToken *PriorLeadingIdentifier = LeadingIdentifier->Previous;
1407           // Skip back past explicit decoration
1408           if (PriorLeadingIdentifier &&
1409               PriorLeadingIdentifier->is(tok::kw_explicit))
1410             PriorLeadingIdentifier = PriorLeadingIdentifier->Previous;
1411
1412           return (PriorLeadingIdentifier &&
1413                   PriorLeadingIdentifier->is(TT_TemplateCloser) &&
1414                   LeadingIdentifier->TokenText == Current.Next->TokenText);
1415         }
1416       }
1417     }
1418     return false;
1419   }
1420
1421   void determineTokenType(FormatToken &Current) {
1422     if (!Current.is(TT_Unknown))
1423       // The token type is already known.
1424       return;
1425
1426     if (Style.Language == FormatStyle::LK_JavaScript) {
1427       if (Current.is(tok::exclaim)) {
1428         if (Current.Previous &&
1429             (Current.Previous->isOneOf(tok::identifier, tok::kw_namespace,
1430                                        tok::r_paren, tok::r_square,
1431                                        tok::r_brace) ||
1432              Current.Previous->Tok.isLiteral())) {
1433           Current.Type = TT_JsNonNullAssertion;
1434           return;
1435         }
1436         if (Current.Next &&
1437             Current.Next->isOneOf(TT_BinaryOperator, Keywords.kw_as)) {
1438           Current.Type = TT_JsNonNullAssertion;
1439           return;
1440         }
1441       }
1442     }
1443
1444     // Line.MightBeFunctionDecl can only be true after the parentheses of a
1445     // function declaration have been found. In this case, 'Current' is a
1446     // trailing token of this declaration and thus cannot be a name.
1447     if (Current.is(Keywords.kw_instanceof)) {
1448       Current.Type = TT_BinaryOperator;
1449     } else if (isStartOfName(Current) &&
1450                (!Line.MightBeFunctionDecl || Current.NestingLevel != 0)) {
1451       Contexts.back().FirstStartOfName = &Current;
1452       Current.Type = TT_StartOfName;
1453     } else if (Current.is(tok::semi)) {
1454       // Reset FirstStartOfName after finding a semicolon so that a for loop
1455       // with multiple increment statements is not confused with a for loop
1456       // having multiple variable declarations.
1457       Contexts.back().FirstStartOfName = nullptr;
1458     } else if (Current.isOneOf(tok::kw_auto, tok::kw___auto_type)) {
1459       AutoFound = true;
1460     } else if (Current.is(tok::arrow) &&
1461                Style.Language == FormatStyle::LK_Java) {
1462       Current.Type = TT_LambdaArrow;
1463     } else if (Current.is(tok::arrow) && AutoFound && Line.MustBeDeclaration &&
1464                Current.NestingLevel == 0 &&
1465                !Current.Previous->is(tok::kw_operator)) {
1466       // not auto operator->() -> xxx;
1467       Current.Type = TT_TrailingReturnArrow;
1468
1469     } else if (isDeductionGuide(Current)) {
1470       // Deduction guides trailing arrow " A(...) -> A<T>;".
1471       Current.Type = TT_TrailingReturnArrow;
1472     } else if (Current.isOneOf(tok::star, tok::amp, tok::ampamp)) {
1473       Current.Type = determineStarAmpUsage(Current,
1474                                            Contexts.back().CanBeExpression &&
1475                                                Contexts.back().IsExpression,
1476                                            Contexts.back().InTemplateArgument);
1477     } else if (Current.isOneOf(tok::minus, tok::plus, tok::caret)) {
1478       Current.Type = determinePlusMinusCaretUsage(Current);
1479       if (Current.is(TT_UnaryOperator) && Current.is(tok::caret))
1480         Contexts.back().CaretFound = true;
1481     } else if (Current.isOneOf(tok::minusminus, tok::plusplus)) {
1482       Current.Type = determineIncrementUsage(Current);
1483     } else if (Current.isOneOf(tok::exclaim, tok::tilde)) {
1484       Current.Type = TT_UnaryOperator;
1485     } else if (Current.is(tok::question)) {
1486       if (Style.Language == FormatStyle::LK_JavaScript &&
1487           Line.MustBeDeclaration && !Contexts.back().IsExpression) {
1488         // In JavaScript, `interface X { foo?(): bar; }` is an optional method
1489         // on the interface, not a ternary expression.
1490         Current.Type = TT_JsTypeOptionalQuestion;
1491       } else {
1492         Current.Type = TT_ConditionalExpr;
1493       }
1494     } else if (Current.isBinaryOperator() &&
1495                (!Current.Previous || Current.Previous->isNot(tok::l_square)) &&
1496                (!Current.is(tok::greater) &&
1497                 Style.Language != FormatStyle::LK_TextProto)) {
1498       Current.Type = TT_BinaryOperator;
1499     } else if (Current.is(tok::comment)) {
1500       if (Current.TokenText.startswith("/*")) {
1501         if (Current.TokenText.endswith("*/"))
1502           Current.Type = TT_BlockComment;
1503         else
1504           // The lexer has for some reason determined a comment here. But we
1505           // cannot really handle it, if it isn't properly terminated.
1506           Current.Tok.setKind(tok::unknown);
1507       } else {
1508         Current.Type = TT_LineComment;
1509       }
1510     } else if (Current.is(tok::r_paren)) {
1511       if (rParenEndsCast(Current))
1512         Current.Type = TT_CastRParen;
1513       if (Current.MatchingParen && Current.Next &&
1514           !Current.Next->isBinaryOperator() &&
1515           !Current.Next->isOneOf(tok::semi, tok::colon, tok::l_brace,
1516                                  tok::comma, tok::period, tok::arrow,
1517                                  tok::coloncolon))
1518         if (FormatToken *AfterParen = Current.MatchingParen->Next) {
1519           // Make sure this isn't the return type of an Obj-C block declaration
1520           if (AfterParen->Tok.isNot(tok::caret)) {
1521             if (FormatToken *BeforeParen = Current.MatchingParen->Previous)
1522               if (BeforeParen->is(tok::identifier) &&
1523                   !BeforeParen->is(TT_TypenameMacro) &&
1524                   BeforeParen->TokenText == BeforeParen->TokenText.upper() &&
1525                   (!BeforeParen->Previous ||
1526                    BeforeParen->Previous->ClosesTemplateDeclaration))
1527                 Current.Type = TT_FunctionAnnotationRParen;
1528           }
1529         }
1530     } else if (Current.is(tok::at) && Current.Next &&
1531                Style.Language != FormatStyle::LK_JavaScript &&
1532                Style.Language != FormatStyle::LK_Java) {
1533       // In Java & JavaScript, "@..." is a decorator or annotation. In ObjC, it
1534       // marks declarations and properties that need special formatting.
1535       switch (Current.Next->Tok.getObjCKeywordID()) {
1536       case tok::objc_interface:
1537       case tok::objc_implementation:
1538       case tok::objc_protocol:
1539         Current.Type = TT_ObjCDecl;
1540         break;
1541       case tok::objc_property:
1542         Current.Type = TT_ObjCProperty;
1543         break;
1544       default:
1545         break;
1546       }
1547     } else if (Current.is(tok::period)) {
1548       FormatToken *PreviousNoComment = Current.getPreviousNonComment();
1549       if (PreviousNoComment &&
1550           PreviousNoComment->isOneOf(tok::comma, tok::l_brace))
1551         Current.Type = TT_DesignatedInitializerPeriod;
1552       else if (Style.Language == FormatStyle::LK_Java && Current.Previous &&
1553                Current.Previous->isOneOf(TT_JavaAnnotation,
1554                                          TT_LeadingJavaAnnotation)) {
1555         Current.Type = Current.Previous->Type;
1556       }
1557     } else if (canBeObjCSelectorComponent(Current) &&
1558                // FIXME(bug 36976): ObjC return types shouldn't use
1559                // TT_CastRParen.
1560                Current.Previous && Current.Previous->is(TT_CastRParen) &&
1561                Current.Previous->MatchingParen &&
1562                Current.Previous->MatchingParen->Previous &&
1563                Current.Previous->MatchingParen->Previous->is(
1564                    TT_ObjCMethodSpecifier)) {
1565       // This is the first part of an Objective-C selector name. (If there's no
1566       // colon after this, this is the only place which annotates the identifier
1567       // as a selector.)
1568       Current.Type = TT_SelectorName;
1569     } else if (Current.isOneOf(tok::identifier, tok::kw_const,
1570                                tok::kw_noexcept) &&
1571                Current.Previous &&
1572                !Current.Previous->isOneOf(tok::equal, tok::at) &&
1573                Line.MightBeFunctionDecl && Contexts.size() == 1) {
1574       // Line.MightBeFunctionDecl can only be true after the parentheses of a
1575       // function declaration have been found.
1576       Current.Type = TT_TrailingAnnotation;
1577     } else if ((Style.Language == FormatStyle::LK_Java ||
1578                 Style.Language == FormatStyle::LK_JavaScript) &&
1579                Current.Previous) {
1580       if (Current.Previous->is(tok::at) &&
1581           Current.isNot(Keywords.kw_interface)) {
1582         const FormatToken &AtToken = *Current.Previous;
1583         const FormatToken *Previous = AtToken.getPreviousNonComment();
1584         if (!Previous || Previous->is(TT_LeadingJavaAnnotation))
1585           Current.Type = TT_LeadingJavaAnnotation;
1586         else
1587           Current.Type = TT_JavaAnnotation;
1588       } else if (Current.Previous->is(tok::period) &&
1589                  Current.Previous->isOneOf(TT_JavaAnnotation,
1590                                            TT_LeadingJavaAnnotation)) {
1591         Current.Type = Current.Previous->Type;
1592       }
1593     }
1594   }
1595
1596   /// Take a guess at whether \p Tok starts a name of a function or
1597   /// variable declaration.
1598   ///
1599   /// This is a heuristic based on whether \p Tok is an identifier following
1600   /// something that is likely a type.
1601   bool isStartOfName(const FormatToken &Tok) {
1602     if (Tok.isNot(tok::identifier) || !Tok.Previous)
1603       return false;
1604
1605     if (Tok.Previous->isOneOf(TT_LeadingJavaAnnotation, Keywords.kw_instanceof,
1606                               Keywords.kw_as))
1607       return false;
1608     if (Style.Language == FormatStyle::LK_JavaScript &&
1609         Tok.Previous->is(Keywords.kw_in))
1610       return false;
1611
1612     // Skip "const" as it does not have an influence on whether this is a name.
1613     FormatToken *PreviousNotConst = Tok.getPreviousNonComment();
1614     while (PreviousNotConst && PreviousNotConst->is(tok::kw_const))
1615       PreviousNotConst = PreviousNotConst->getPreviousNonComment();
1616
1617     if (!PreviousNotConst)
1618       return false;
1619
1620     bool IsPPKeyword = PreviousNotConst->is(tok::identifier) &&
1621                        PreviousNotConst->Previous &&
1622                        PreviousNotConst->Previous->is(tok::hash);
1623
1624     if (PreviousNotConst->is(TT_TemplateCloser))
1625       return PreviousNotConst && PreviousNotConst->MatchingParen &&
1626              PreviousNotConst->MatchingParen->Previous &&
1627              PreviousNotConst->MatchingParen->Previous->isNot(tok::period) &&
1628              PreviousNotConst->MatchingParen->Previous->isNot(tok::kw_template);
1629
1630     if (PreviousNotConst->is(tok::r_paren) && PreviousNotConst->MatchingParen &&
1631         PreviousNotConst->MatchingParen->Previous &&
1632         PreviousNotConst->MatchingParen->Previous->is(tok::kw_decltype))
1633       return true;
1634
1635     return (!IsPPKeyword &&
1636             PreviousNotConst->isOneOf(tok::identifier, tok::kw_auto)) ||
1637            PreviousNotConst->is(TT_PointerOrReference) ||
1638            PreviousNotConst->isSimpleTypeSpecifier();
1639   }
1640
1641   /// Determine whether ')' is ending a cast.
1642   bool rParenEndsCast(const FormatToken &Tok) {
1643     // C-style casts are only used in C++ and Java.
1644     if (!Style.isCpp() && Style.Language != FormatStyle::LK_Java)
1645       return false;
1646
1647     // Empty parens aren't casts and there are no casts at the end of the line.
1648     if (Tok.Previous == Tok.MatchingParen || !Tok.Next || !Tok.MatchingParen)
1649       return false;
1650
1651     FormatToken *LeftOfParens = Tok.MatchingParen->getPreviousNonComment();
1652     if (LeftOfParens) {
1653       // If there is a closing parenthesis left of the current parentheses,
1654       // look past it as these might be chained casts.
1655       if (LeftOfParens->is(tok::r_paren)) {
1656         if (!LeftOfParens->MatchingParen ||
1657             !LeftOfParens->MatchingParen->Previous)
1658           return false;
1659         LeftOfParens = LeftOfParens->MatchingParen->Previous;
1660       }
1661
1662       // If there is an identifier (or with a few exceptions a keyword) right
1663       // before the parentheses, this is unlikely to be a cast.
1664       if (LeftOfParens->Tok.getIdentifierInfo() &&
1665           !LeftOfParens->isOneOf(Keywords.kw_in, tok::kw_return, tok::kw_case,
1666                                  tok::kw_delete))
1667         return false;
1668
1669       // Certain other tokens right before the parentheses are also signals that
1670       // this cannot be a cast.
1671       if (LeftOfParens->isOneOf(tok::at, tok::r_square, TT_OverloadedOperator,
1672                                 TT_TemplateCloser, tok::ellipsis))
1673         return false;
1674     }
1675
1676     if (Tok.Next->is(tok::question))
1677       return false;
1678
1679     // Functions which end with decorations like volatile, noexcept are unlikely
1680     // to be casts.
1681     if (Tok.Next->isOneOf(tok::kw_noexcept, tok::kw_volatile, tok::kw_const,
1682                           tok::kw_throw, tok::arrow, Keywords.kw_override,
1683                           Keywords.kw_final) ||
1684         isCpp11AttributeSpecifier(*Tok.Next))
1685       return false;
1686
1687     // As Java has no function types, a "(" after the ")" likely means that this
1688     // is a cast.
1689     if (Style.Language == FormatStyle::LK_Java && Tok.Next->is(tok::l_paren))
1690       return true;
1691
1692     // If a (non-string) literal follows, this is likely a cast.
1693     if (Tok.Next->isNot(tok::string_literal) &&
1694         (Tok.Next->Tok.isLiteral() ||
1695          Tok.Next->isOneOf(tok::kw_sizeof, tok::kw_alignof)))
1696       return true;
1697
1698     // Heuristically try to determine whether the parentheses contain a type.
1699     bool ParensAreType =
1700         !Tok.Previous ||
1701         Tok.Previous->isOneOf(TT_PointerOrReference, TT_TemplateCloser) ||
1702         Tok.Previous->isSimpleTypeSpecifier();
1703     bool ParensCouldEndDecl =
1704         Tok.Next->isOneOf(tok::equal, tok::semi, tok::l_brace, tok::greater);
1705     if (ParensAreType && !ParensCouldEndDecl)
1706       return true;
1707
1708     // At this point, we heuristically assume that there are no casts at the
1709     // start of the line. We assume that we have found most cases where there
1710     // are by the logic above, e.g. "(void)x;".
1711     if (!LeftOfParens)
1712       return false;
1713
1714     // Certain token types inside the parentheses mean that this can't be a
1715     // cast.
1716     for (const FormatToken *Token = Tok.MatchingParen->Next; Token != &Tok;
1717          Token = Token->Next)
1718       if (Token->is(TT_BinaryOperator))
1719         return false;
1720
1721     // If the following token is an identifier or 'this', this is a cast. All
1722     // cases where this can be something else are handled above.
1723     if (Tok.Next->isOneOf(tok::identifier, tok::kw_this))
1724       return true;
1725
1726     if (!Tok.Next->Next)
1727       return false;
1728
1729     // If the next token after the parenthesis is a unary operator, assume
1730     // that this is cast, unless there are unexpected tokens inside the
1731     // parenthesis.
1732     bool NextIsUnary =
1733         Tok.Next->isUnaryOperator() || Tok.Next->isOneOf(tok::amp, tok::star);
1734     if (!NextIsUnary || Tok.Next->is(tok::plus) ||
1735         !Tok.Next->Next->isOneOf(tok::identifier, tok::numeric_constant))
1736       return false;
1737     // Search for unexpected tokens.
1738     for (FormatToken *Prev = Tok.Previous; Prev != Tok.MatchingParen;
1739          Prev = Prev->Previous) {
1740       if (!Prev->isOneOf(tok::kw_const, tok::identifier, tok::coloncolon))
1741         return false;
1742     }
1743     return true;
1744   }
1745
1746   /// Return the type of the given token assuming it is * or &.
1747   TokenType determineStarAmpUsage(const FormatToken &Tok, bool IsExpression,
1748                                   bool InTemplateArgument) {
1749     if (Style.Language == FormatStyle::LK_JavaScript)
1750       return TT_BinaryOperator;
1751
1752     const FormatToken *PrevToken = Tok.getPreviousNonComment();
1753     if (!PrevToken)
1754       return TT_UnaryOperator;
1755
1756     const FormatToken *NextToken = Tok.getNextNonComment();
1757     if (!NextToken ||
1758         NextToken->isOneOf(tok::arrow, tok::equal, tok::kw_const,
1759                            tok::kw_noexcept) ||
1760         (NextToken->is(tok::l_brace) && !NextToken->getNextNonComment()))
1761       return TT_PointerOrReference;
1762
1763     if (PrevToken->is(tok::coloncolon))
1764       return TT_PointerOrReference;
1765
1766     if (PrevToken->isOneOf(tok::l_paren, tok::l_square, tok::l_brace,
1767                            tok::comma, tok::semi, tok::kw_return, tok::colon,
1768                            tok::equal, tok::kw_delete, tok::kw_sizeof,
1769                            tok::kw_throw) ||
1770         PrevToken->isOneOf(TT_BinaryOperator, TT_ConditionalExpr,
1771                            TT_UnaryOperator, TT_CastRParen))
1772       return TT_UnaryOperator;
1773
1774     if (NextToken->is(tok::l_square) && NextToken->isNot(TT_LambdaLSquare))
1775       return TT_PointerOrReference;
1776     if (NextToken->is(tok::kw_operator) && !IsExpression)
1777       return TT_PointerOrReference;
1778     if (NextToken->isOneOf(tok::comma, tok::semi))
1779       return TT_PointerOrReference;
1780
1781     if (PrevToken->is(tok::r_paren) && PrevToken->MatchingParen) {
1782       FormatToken *TokenBeforeMatchingParen =
1783           PrevToken->MatchingParen->getPreviousNonComment();
1784       if (TokenBeforeMatchingParen &&
1785           TokenBeforeMatchingParen->isOneOf(tok::kw_typeof, tok::kw_decltype,
1786                                             TT_TypenameMacro))
1787         return TT_PointerOrReference;
1788     }
1789
1790     if (PrevToken->Tok.isLiteral() ||
1791         PrevToken->isOneOf(tok::r_paren, tok::r_square, tok::kw_true,
1792                            tok::kw_false, tok::r_brace) ||
1793         NextToken->Tok.isLiteral() ||
1794         NextToken->isOneOf(tok::kw_true, tok::kw_false) ||
1795         NextToken->isUnaryOperator() ||
1796         // If we know we're in a template argument, there are no named
1797         // declarations. Thus, having an identifier on the right-hand side
1798         // indicates a binary operator.
1799         (InTemplateArgument && NextToken->Tok.isAnyIdentifier()))
1800       return TT_BinaryOperator;
1801
1802     // "&&(" is quite unlikely to be two successive unary "&".
1803     if (Tok.is(tok::ampamp) && NextToken && NextToken->is(tok::l_paren))
1804       return TT_BinaryOperator;
1805
1806     // This catches some cases where evaluation order is used as control flow:
1807     //   aaa && aaa->f();
1808     const FormatToken *NextNextToken = NextToken->getNextNonComment();
1809     if (NextNextToken && NextNextToken->is(tok::arrow))
1810       return TT_BinaryOperator;
1811
1812     // It is very unlikely that we are going to find a pointer or reference type
1813     // definition on the RHS of an assignment.
1814     if (IsExpression && !Contexts.back().CaretFound)
1815       return TT_BinaryOperator;
1816
1817     return TT_PointerOrReference;
1818   }
1819
1820   TokenType determinePlusMinusCaretUsage(const FormatToken &Tok) {
1821     const FormatToken *PrevToken = Tok.getPreviousNonComment();
1822     if (!PrevToken)
1823       return TT_UnaryOperator;
1824
1825     if (PrevToken->isOneOf(TT_CastRParen, TT_UnaryOperator))
1826       // This must be a sequence of leading unary operators.
1827       return TT_UnaryOperator;
1828
1829     // Use heuristics to recognize unary operators.
1830     if (PrevToken->isOneOf(tok::equal, tok::l_paren, tok::comma, tok::l_square,
1831                            tok::question, tok::colon, tok::kw_return,
1832                            tok::kw_case, tok::at, tok::l_brace, tok::kw_throw,
1833                            tok::kw_co_return, tok::kw_co_yield))
1834       return TT_UnaryOperator;
1835
1836     // There can't be two consecutive binary operators.
1837     if (PrevToken->is(TT_BinaryOperator))
1838       return TT_UnaryOperator;
1839
1840     // Fall back to marking the token as binary operator.
1841     return TT_BinaryOperator;
1842   }
1843
1844   /// Determine whether ++/-- are pre- or post-increments/-decrements.
1845   TokenType determineIncrementUsage(const FormatToken &Tok) {
1846     const FormatToken *PrevToken = Tok.getPreviousNonComment();
1847     if (!PrevToken || PrevToken->is(TT_CastRParen))
1848       return TT_UnaryOperator;
1849     if (PrevToken->isOneOf(tok::r_paren, tok::r_square, tok::identifier))
1850       return TT_TrailingUnaryOperator;
1851
1852     return TT_UnaryOperator;
1853   }
1854
1855   SmallVector<Context, 8> Contexts;
1856
1857   const FormatStyle &Style;
1858   AnnotatedLine &Line;
1859   FormatToken *CurrentToken;
1860   bool AutoFound;
1861   const AdditionalKeywords &Keywords;
1862
1863   // Set of "<" tokens that do not open a template parameter list. If parseAngle
1864   // determines that a specific token can't be a template opener, it will make
1865   // same decision irrespective of the decisions for tokens leading up to it.
1866   // Store this information to prevent this from causing exponential runtime.
1867   llvm::SmallPtrSet<FormatToken *, 16> NonTemplateLess;
1868 };
1869
1870 static const int PrecedenceUnaryOperator = prec::PointerToMember + 1;
1871 static const int PrecedenceArrowAndPeriod = prec::PointerToMember + 2;
1872
1873 /// Parses binary expressions by inserting fake parenthesis based on
1874 /// operator precedence.
1875 class ExpressionParser {
1876 public:
1877   ExpressionParser(const FormatStyle &Style, const AdditionalKeywords &Keywords,
1878                    AnnotatedLine &Line)
1879       : Style(Style), Keywords(Keywords), Current(Line.First) {}
1880
1881   /// Parse expressions with the given operator precedence.
1882   void parse(int Precedence = 0) {
1883     // Skip 'return' and ObjC selector colons as they are not part of a binary
1884     // expression.
1885     while (Current && (Current->is(tok::kw_return) ||
1886                        (Current->is(tok::colon) &&
1887                         Current->isOneOf(TT_ObjCMethodExpr, TT_DictLiteral))))
1888       next();
1889
1890     if (!Current || Precedence > PrecedenceArrowAndPeriod)
1891       return;
1892
1893     // Conditional expressions need to be parsed separately for proper nesting.
1894     if (Precedence == prec::Conditional) {
1895       parseConditionalExpr();
1896       return;
1897     }
1898
1899     // Parse unary operators, which all have a higher precedence than binary
1900     // operators.
1901     if (Precedence == PrecedenceUnaryOperator) {
1902       parseUnaryOperator();
1903       return;
1904     }
1905
1906     FormatToken *Start = Current;
1907     FormatToken *LatestOperator = nullptr;
1908     unsigned OperatorIndex = 0;
1909
1910     while (Current) {
1911       // Consume operators with higher precedence.
1912       parse(Precedence + 1);
1913
1914       int CurrentPrecedence = getCurrentPrecedence();
1915
1916       if (Current && Current->is(TT_SelectorName) &&
1917           Precedence == CurrentPrecedence) {
1918         if (LatestOperator)
1919           addFakeParenthesis(Start, prec::Level(Precedence));
1920         Start = Current;
1921       }
1922
1923       // At the end of the line or when an operator with higher precedence is
1924       // found, insert fake parenthesis and return.
1925       if (!Current ||
1926           (Current->closesScope() &&
1927            (Current->MatchingParen || Current->is(TT_TemplateString))) ||
1928           (CurrentPrecedence != -1 && CurrentPrecedence < Precedence) ||
1929           (CurrentPrecedence == prec::Conditional &&
1930            Precedence == prec::Assignment && Current->is(tok::colon))) {
1931         break;
1932       }
1933
1934       // Consume scopes: (), [], <> and {}
1935       if (Current->opensScope()) {
1936         // In fragment of a JavaScript template string can look like '}..${' and
1937         // thus close a scope and open a new one at the same time.
1938         while (Current && (!Current->closesScope() || Current->opensScope())) {
1939           next();
1940           parse();
1941         }
1942         next();
1943       } else {
1944         // Operator found.
1945         if (CurrentPrecedence == Precedence) {
1946           if (LatestOperator)
1947             LatestOperator->NextOperator = Current;
1948           LatestOperator = Current;
1949           Current->OperatorIndex = OperatorIndex;
1950           ++OperatorIndex;
1951         }
1952         next(/*SkipPastLeadingComments=*/Precedence > 0);
1953       }
1954     }
1955
1956     if (LatestOperator && (Current || Precedence > 0)) {
1957       // LatestOperator->LastOperator = true;
1958       if (Precedence == PrecedenceArrowAndPeriod) {
1959         // Call expressions don't have a binary operator precedence.
1960         addFakeParenthesis(Start, prec::Unknown);
1961       } else {
1962         addFakeParenthesis(Start, prec::Level(Precedence));
1963       }
1964     }
1965   }
1966
1967 private:
1968   /// Gets the precedence (+1) of the given token for binary operators
1969   /// and other tokens that we treat like binary operators.
1970   int getCurrentPrecedence() {
1971     if (Current) {
1972       const FormatToken *NextNonComment = Current->getNextNonComment();
1973       if (Current->is(TT_ConditionalExpr))
1974         return prec::Conditional;
1975       if (NextNonComment && Current->is(TT_SelectorName) &&
1976           (NextNonComment->isOneOf(TT_DictLiteral, TT_JsTypeColon) ||
1977            ((Style.Language == FormatStyle::LK_Proto ||
1978              Style.Language == FormatStyle::LK_TextProto) &&
1979             NextNonComment->is(tok::less))))
1980         return prec::Assignment;
1981       if (Current->is(TT_JsComputedPropertyName))
1982         return prec::Assignment;
1983       if (Current->is(TT_LambdaArrow))
1984         return prec::Comma;
1985       if (Current->is(TT_JsFatArrow))
1986         return prec::Assignment;
1987       if (Current->isOneOf(tok::semi, TT_InlineASMColon, TT_SelectorName) ||
1988           (Current->is(tok::comment) && NextNonComment &&
1989            NextNonComment->is(TT_SelectorName)))
1990         return 0;
1991       if (Current->is(TT_RangeBasedForLoopColon))
1992         return prec::Comma;
1993       if ((Style.Language == FormatStyle::LK_Java ||
1994            Style.Language == FormatStyle::LK_JavaScript) &&
1995           Current->is(Keywords.kw_instanceof))
1996         return prec::Relational;
1997       if (Style.Language == FormatStyle::LK_JavaScript &&
1998           Current->isOneOf(Keywords.kw_in, Keywords.kw_as))
1999         return prec::Relational;
2000       if (Current->is(TT_BinaryOperator) || Current->is(tok::comma))
2001         return Current->getPrecedence();
2002       if (Current->isOneOf(tok::period, tok::arrow))
2003         return PrecedenceArrowAndPeriod;
2004       if ((Style.Language == FormatStyle::LK_Java ||
2005            Style.Language == FormatStyle::LK_JavaScript) &&
2006           Current->isOneOf(Keywords.kw_extends, Keywords.kw_implements,
2007                            Keywords.kw_throws))
2008         return 0;
2009     }
2010     return -1;
2011   }
2012
2013   void addFakeParenthesis(FormatToken *Start, prec::Level Precedence) {
2014     Start->FakeLParens.push_back(Precedence);
2015     if (Precedence > prec::Unknown)
2016       Start->StartsBinaryExpression = true;
2017     if (Current) {
2018       FormatToken *Previous = Current->Previous;
2019       while (Previous->is(tok::comment) && Previous->Previous)
2020         Previous = Previous->Previous;
2021       ++Previous->FakeRParens;
2022       if (Precedence > prec::Unknown)
2023         Previous->EndsBinaryExpression = true;
2024     }
2025   }
2026
2027   /// Parse unary operator expressions and surround them with fake
2028   /// parentheses if appropriate.
2029   void parseUnaryOperator() {
2030     llvm::SmallVector<FormatToken *, 2> Tokens;
2031     while (Current && Current->is(TT_UnaryOperator)) {
2032       Tokens.push_back(Current);
2033       next();
2034     }
2035     parse(PrecedenceArrowAndPeriod);
2036     for (FormatToken *Token : llvm::reverse(Tokens))
2037       // The actual precedence doesn't matter.
2038       addFakeParenthesis(Token, prec::Unknown);
2039   }
2040
2041   void parseConditionalExpr() {
2042     while (Current && Current->isTrailingComment()) {
2043       next();
2044     }
2045     FormatToken *Start = Current;
2046     parse(prec::LogicalOr);
2047     if (!Current || !Current->is(tok::question))
2048       return;
2049     next();
2050     parse(prec::Assignment);
2051     if (!Current || Current->isNot(TT_ConditionalExpr))
2052       return;
2053     next();
2054     parse(prec::Assignment);
2055     addFakeParenthesis(Start, prec::Conditional);
2056   }
2057
2058   void next(bool SkipPastLeadingComments = true) {
2059     if (Current)
2060       Current = Current->Next;
2061     while (Current &&
2062            (Current->NewlinesBefore == 0 || SkipPastLeadingComments) &&
2063            Current->isTrailingComment())
2064       Current = Current->Next;
2065   }
2066
2067   const FormatStyle &Style;
2068   const AdditionalKeywords &Keywords;
2069   FormatToken *Current;
2070 };
2071
2072 } // end anonymous namespace
2073
2074 void TokenAnnotator::setCommentLineLevels(
2075     SmallVectorImpl<AnnotatedLine *> &Lines) {
2076   const AnnotatedLine *NextNonCommentLine = nullptr;
2077   for (SmallVectorImpl<AnnotatedLine *>::reverse_iterator I = Lines.rbegin(),
2078                                                           E = Lines.rend();
2079        I != E; ++I) {
2080     bool CommentLine = true;
2081     for (const FormatToken *Tok = (*I)->First; Tok; Tok = Tok->Next) {
2082       if (!Tok->is(tok::comment)) {
2083         CommentLine = false;
2084         break;
2085       }
2086     }
2087
2088     // If the comment is currently aligned with the line immediately following
2089     // it, that's probably intentional and we should keep it.
2090     if (NextNonCommentLine && CommentLine &&
2091         NextNonCommentLine->First->NewlinesBefore <= 1 &&
2092         NextNonCommentLine->First->OriginalColumn ==
2093             (*I)->First->OriginalColumn) {
2094       // Align comments for preprocessor lines with the # in column 0 if
2095       // preprocessor lines are not indented. Otherwise, align with the next
2096       // line.
2097       (*I)->Level =
2098           (Style.IndentPPDirectives != FormatStyle::PPDIS_BeforeHash &&
2099            (NextNonCommentLine->Type == LT_PreprocessorDirective ||
2100             NextNonCommentLine->Type == LT_ImportStatement))
2101               ? 0
2102               : NextNonCommentLine->Level;
2103     } else {
2104       NextNonCommentLine = (*I)->First->isNot(tok::r_brace) ? (*I) : nullptr;
2105     }
2106
2107     setCommentLineLevels((*I)->Children);
2108   }
2109 }
2110
2111 static unsigned maxNestingDepth(const AnnotatedLine &Line) {
2112   unsigned Result = 0;
2113   for (const auto *Tok = Line.First; Tok != nullptr; Tok = Tok->Next)
2114     Result = std::max(Result, Tok->NestingLevel);
2115   return Result;
2116 }
2117
2118 void TokenAnnotator::annotate(AnnotatedLine &Line) {
2119   for (SmallVectorImpl<AnnotatedLine *>::iterator I = Line.Children.begin(),
2120                                                   E = Line.Children.end();
2121        I != E; ++I) {
2122     annotate(**I);
2123   }
2124   AnnotatingParser Parser(Style, Line, Keywords);
2125   Line.Type = Parser.parseLine();
2126
2127   // With very deep nesting, ExpressionParser uses lots of stack and the
2128   // formatting algorithm is very slow. We're not going to do a good job here
2129   // anyway - it's probably generated code being formatted by mistake.
2130   // Just skip the whole line.
2131   if (maxNestingDepth(Line) > 50)
2132     Line.Type = LT_Invalid;
2133
2134   if (Line.Type == LT_Invalid)
2135     return;
2136
2137   ExpressionParser ExprParser(Style, Keywords, Line);
2138   ExprParser.parse();
2139
2140   if (Line.startsWith(TT_ObjCMethodSpecifier))
2141     Line.Type = LT_ObjCMethodDecl;
2142   else if (Line.startsWith(TT_ObjCDecl))
2143     Line.Type = LT_ObjCDecl;
2144   else if (Line.startsWith(TT_ObjCProperty))
2145     Line.Type = LT_ObjCProperty;
2146
2147   Line.First->SpacesRequiredBefore = 1;
2148   Line.First->CanBreakBefore = Line.First->MustBreakBefore;
2149 }
2150
2151 // This function heuristically determines whether 'Current' starts the name of a
2152 // function declaration.
2153 static bool isFunctionDeclarationName(const FormatToken &Current,
2154                                       const AnnotatedLine &Line) {
2155   auto skipOperatorName = [](const FormatToken *Next) -> const FormatToken * {
2156     for (; Next; Next = Next->Next) {
2157       if (Next->is(TT_OverloadedOperatorLParen))
2158         return Next;
2159       if (Next->is(TT_OverloadedOperator))
2160         continue;
2161       if (Next->isOneOf(tok::kw_new, tok::kw_delete)) {
2162         // For 'new[]' and 'delete[]'.
2163         if (Next->Next &&
2164             Next->Next->startsSequence(tok::l_square, tok::r_square))
2165           Next = Next->Next->Next;
2166         continue;
2167       }
2168       if (Next->startsSequence(tok::l_square, tok::r_square)) {
2169         // For operator[]().
2170         Next = Next->Next;
2171         continue;
2172       }
2173       if ((Next->isSimpleTypeSpecifier() || Next->is(tok::identifier)) &&
2174           Next->Next && Next->Next->isOneOf(tok::star, tok::amp, tok::ampamp)) {
2175         // For operator void*(), operator char*(), operator Foo*().
2176         Next = Next->Next;
2177         continue;
2178       }
2179
2180       break;
2181     }
2182     return nullptr;
2183   };
2184
2185   // Find parentheses of parameter list.
2186   const FormatToken *Next = Current.Next;
2187   if (Current.is(tok::kw_operator)) {
2188     if (Current.Previous && Current.Previous->is(tok::coloncolon))
2189       return false;
2190     Next = skipOperatorName(Next);
2191   } else {
2192     if (!Current.is(TT_StartOfName) || Current.NestingLevel != 0)
2193       return false;
2194     for (; Next; Next = Next->Next) {
2195       if (Next->is(TT_TemplateOpener)) {
2196         Next = Next->MatchingParen;
2197       } else if (Next->is(tok::coloncolon)) {
2198         Next = Next->Next;
2199         if (!Next)
2200           return false;
2201         if (Next->is(tok::kw_operator)) {
2202           Next = skipOperatorName(Next->Next);
2203           break;
2204         }
2205         if (!Next->is(tok::identifier))
2206           return false;
2207       } else if (Next->is(tok::l_paren)) {
2208         break;
2209       } else {
2210         return false;
2211       }
2212     }
2213   }
2214
2215   // Check whether parameter list can belong to a function declaration.
2216   if (!Next || !Next->is(tok::l_paren) || !Next->MatchingParen)
2217     return false;
2218   // If the lines ends with "{", this is likely an function definition.
2219   if (Line.Last->is(tok::l_brace))
2220     return true;
2221   if (Next->Next == Next->MatchingParen)
2222     return true; // Empty parentheses.
2223   // If there is an &/&& after the r_paren, this is likely a function.
2224   if (Next->MatchingParen->Next &&
2225       Next->MatchingParen->Next->is(TT_PointerOrReference))
2226     return true;
2227   for (const FormatToken *Tok = Next->Next; Tok && Tok != Next->MatchingParen;
2228        Tok = Tok->Next) {
2229     if (Tok->isOneOf(tok::l_paren, TT_TemplateOpener) && Tok->MatchingParen) {
2230       Tok = Tok->MatchingParen;
2231       continue;
2232     }
2233     if (Tok->is(tok::kw_const) || Tok->isSimpleTypeSpecifier() ||
2234         Tok->isOneOf(TT_PointerOrReference, TT_StartOfName, tok::ellipsis))
2235       return true;
2236     if (Tok->isOneOf(tok::l_brace, tok::string_literal, TT_ObjCMethodExpr) ||
2237         Tok->Tok.isLiteral())
2238       return false;
2239   }
2240   return false;
2241 }
2242
2243 bool TokenAnnotator::mustBreakForReturnType(const AnnotatedLine &Line) const {
2244   assert(Line.MightBeFunctionDecl);
2245
2246   if ((Style.AlwaysBreakAfterReturnType == FormatStyle::RTBS_TopLevel ||
2247        Style.AlwaysBreakAfterReturnType ==
2248            FormatStyle::RTBS_TopLevelDefinitions) &&
2249       Line.Level > 0)
2250     return false;
2251
2252   switch (Style.AlwaysBreakAfterReturnType) {
2253   case FormatStyle::RTBS_None:
2254     return false;
2255   case FormatStyle::RTBS_All:
2256   case FormatStyle::RTBS_TopLevel:
2257     return true;
2258   case FormatStyle::RTBS_AllDefinitions:
2259   case FormatStyle::RTBS_TopLevelDefinitions:
2260     return Line.mightBeFunctionDefinition();
2261   }
2262
2263   return false;
2264 }
2265
2266 void TokenAnnotator::calculateFormattingInformation(AnnotatedLine &Line) {
2267   for (SmallVectorImpl<AnnotatedLine *>::iterator I = Line.Children.begin(),
2268                                                   E = Line.Children.end();
2269        I != E; ++I) {
2270     calculateFormattingInformation(**I);
2271   }
2272
2273   Line.First->TotalLength =
2274       Line.First->IsMultiline ? Style.ColumnLimit
2275                               : Line.FirstStartColumn + Line.First->ColumnWidth;
2276   FormatToken *Current = Line.First->Next;
2277   bool InFunctionDecl = Line.MightBeFunctionDecl;
2278   while (Current) {
2279     if (isFunctionDeclarationName(*Current, Line))
2280       Current->Type = TT_FunctionDeclarationName;
2281     if (Current->is(TT_LineComment)) {
2282       if (Current->Previous->BlockKind == BK_BracedInit &&
2283           Current->Previous->opensScope())
2284         Current->SpacesRequiredBefore =
2285             (Style.Cpp11BracedListStyle && !Style.SpacesInParentheses) ? 0 : 1;
2286       else
2287         Current->SpacesRequiredBefore = Style.SpacesBeforeTrailingComments;
2288
2289       // If we find a trailing comment, iterate backwards to determine whether
2290       // it seems to relate to a specific parameter. If so, break before that
2291       // parameter to avoid changing the comment's meaning. E.g. don't move 'b'
2292       // to the previous line in:
2293       //   SomeFunction(a,
2294       //                b, // comment
2295       //                c);
2296       if (!Current->HasUnescapedNewline) {
2297         for (FormatToken *Parameter = Current->Previous; Parameter;
2298              Parameter = Parameter->Previous) {
2299           if (Parameter->isOneOf(tok::comment, tok::r_brace))
2300             break;
2301           if (Parameter->Previous && Parameter->Previous->is(tok::comma)) {
2302             if (!Parameter->Previous->is(TT_CtorInitializerComma) &&
2303                 Parameter->HasUnescapedNewline)
2304               Parameter->MustBreakBefore = true;
2305             break;
2306           }
2307         }
2308       }
2309     } else if (Current->SpacesRequiredBefore == 0 &&
2310                spaceRequiredBefore(Line, *Current)) {
2311       Current->SpacesRequiredBefore = 1;
2312     }
2313
2314     Current->MustBreakBefore =
2315         Current->MustBreakBefore || mustBreakBefore(Line, *Current);
2316
2317     if (!Current->MustBreakBefore && InFunctionDecl &&
2318         Current->is(TT_FunctionDeclarationName))
2319       Current->MustBreakBefore = mustBreakForReturnType(Line);
2320
2321     Current->CanBreakBefore =
2322         Current->MustBreakBefore || canBreakBefore(Line, *Current);
2323     unsigned ChildSize = 0;
2324     if (Current->Previous->Children.size() == 1) {
2325       FormatToken &LastOfChild = *Current->Previous->Children[0]->Last;
2326       ChildSize = LastOfChild.isTrailingComment() ? Style.ColumnLimit
2327                                                   : LastOfChild.TotalLength + 1;
2328     }
2329     const FormatToken *Prev = Current->Previous;
2330     if (Current->MustBreakBefore || Prev->Children.size() > 1 ||
2331         (Prev->Children.size() == 1 &&
2332          Prev->Children[0]->First->MustBreakBefore) ||
2333         Current->IsMultiline)
2334       Current->TotalLength = Prev->TotalLength + Style.ColumnLimit;
2335     else
2336       Current->TotalLength = Prev->TotalLength + Current->ColumnWidth +
2337                              ChildSize + Current->SpacesRequiredBefore;
2338
2339     if (Current->is(TT_CtorInitializerColon))
2340       InFunctionDecl = false;
2341
2342     // FIXME: Only calculate this if CanBreakBefore is true once static
2343     // initializers etc. are sorted out.
2344     // FIXME: Move magic numbers to a better place.
2345
2346     // Reduce penalty for aligning ObjC method arguments using the colon
2347     // alignment as this is the canonical way (still prefer fitting everything
2348     // into one line if possible). Trying to fit a whole expression into one
2349     // line should not force other line breaks (e.g. when ObjC method
2350     // expression is a part of other expression).
2351     Current->SplitPenalty = splitPenalty(Line, *Current, InFunctionDecl);
2352     if (Style.Language == FormatStyle::LK_ObjC &&
2353         Current->is(TT_SelectorName) && Current->ParameterIndex > 0) {
2354       if (Current->ParameterIndex == 1)
2355         Current->SplitPenalty += 5 * Current->BindingStrength;
2356     } else {
2357       Current->SplitPenalty += 20 * Current->BindingStrength;
2358     }
2359
2360     Current = Current->Next;
2361   }
2362
2363   calculateUnbreakableTailLengths(Line);
2364   unsigned IndentLevel = Line.Level;
2365   for (Current = Line.First; Current != nullptr; Current = Current->Next) {
2366     if (Current->Role)
2367       Current->Role->precomputeFormattingInfos(Current);
2368     if (Current->MatchingParen &&
2369         Current->MatchingParen->opensBlockOrBlockTypeList(Style)) {
2370       assert(IndentLevel > 0);
2371       --IndentLevel;
2372     }
2373     Current->IndentLevel = IndentLevel;
2374     if (Current->opensBlockOrBlockTypeList(Style))
2375       ++IndentLevel;
2376   }
2377
2378   LLVM_DEBUG({ printDebugInfo(Line); });
2379 }
2380
2381 void TokenAnnotator::calculateUnbreakableTailLengths(AnnotatedLine &Line) {
2382   unsigned UnbreakableTailLength = 0;
2383   FormatToken *Current = Line.Last;
2384   while (Current) {
2385     Current->UnbreakableTailLength = UnbreakableTailLength;
2386     if (Current->CanBreakBefore ||
2387         Current->isOneOf(tok::comment, tok::string_literal)) {
2388       UnbreakableTailLength = 0;
2389     } else {
2390       UnbreakableTailLength +=
2391           Current->ColumnWidth + Current->SpacesRequiredBefore;
2392     }
2393     Current = Current->Previous;
2394   }
2395 }
2396
2397 unsigned TokenAnnotator::splitPenalty(const AnnotatedLine &Line,
2398                                       const FormatToken &Tok,
2399                                       bool InFunctionDecl) {
2400   const FormatToken &Left = *Tok.Previous;
2401   const FormatToken &Right = Tok;
2402
2403   if (Left.is(tok::semi))
2404     return 0;
2405
2406   if (Style.Language == FormatStyle::LK_Java) {
2407     if (Right.isOneOf(Keywords.kw_extends, Keywords.kw_throws))
2408       return 1;
2409     if (Right.is(Keywords.kw_implements))
2410       return 2;
2411     if (Left.is(tok::comma) && Left.NestingLevel == 0)
2412       return 3;
2413   } else if (Style.Language == FormatStyle::LK_JavaScript) {
2414     if (Right.is(Keywords.kw_function) && Left.isNot(tok::comma))
2415       return 100;
2416     if (Left.is(TT_JsTypeColon))
2417       return 35;
2418     if ((Left.is(TT_TemplateString) && Left.TokenText.endswith("${")) ||
2419         (Right.is(TT_TemplateString) && Right.TokenText.startswith("}")))
2420       return 100;
2421     // Prefer breaking call chains (".foo") over empty "{}", "[]" or "()".
2422     if (Left.opensScope() && Right.closesScope())
2423       return 200;
2424   }
2425
2426   if (Right.is(tok::identifier) && Right.Next && Right.Next->is(TT_DictLiteral))
2427     return 1;
2428   if (Right.is(tok::l_square)) {
2429     if (Style.Language == FormatStyle::LK_Proto)
2430       return 1;
2431     if (Left.is(tok::r_square))
2432       return 200;
2433     // Slightly prefer formatting local lambda definitions like functions.
2434     if (Right.is(TT_LambdaLSquare) && Left.is(tok::equal))
2435       return 35;
2436     if (!Right.isOneOf(TT_ObjCMethodExpr, TT_LambdaLSquare,
2437                        TT_ArrayInitializerLSquare,
2438                        TT_DesignatedInitializerLSquare, TT_AttributeSquare))
2439       return 500;
2440   }
2441
2442   if (Left.is(tok::coloncolon) ||
2443       (Right.is(tok::period) && Style.Language == FormatStyle::LK_Proto))
2444     return 500;
2445   if (Right.isOneOf(TT_StartOfName, TT_FunctionDeclarationName) ||
2446       Right.is(tok::kw_operator)) {
2447     if (Line.startsWith(tok::kw_for) && Right.PartOfMultiVariableDeclStmt)
2448       return 3;
2449     if (Left.is(TT_StartOfName))
2450       return 110;
2451     if (InFunctionDecl && Right.NestingLevel == 0)
2452       return Style.PenaltyReturnTypeOnItsOwnLine;
2453     return 200;
2454   }
2455   if (Right.is(TT_PointerOrReference))
2456     return 190;
2457   if (Right.is(TT_LambdaArrow))
2458     return 110;
2459   if (Left.is(tok::equal) && Right.is(tok::l_brace))
2460     return 160;
2461   if (Left.is(TT_CastRParen))
2462     return 100;
2463   if (Left.isOneOf(tok::kw_class, tok::kw_struct))
2464     return 5000;
2465   if (Left.is(tok::comment))
2466     return 1000;
2467
2468   if (Left.isOneOf(TT_RangeBasedForLoopColon, TT_InheritanceColon,
2469                    TT_CtorInitializerColon))
2470     return 2;
2471
2472   if (Right.isMemberAccess()) {
2473     // Breaking before the "./->" of a chained call/member access is reasonably
2474     // cheap, as formatting those with one call per line is generally
2475     // desirable. In particular, it should be cheaper to break before the call
2476     // than it is to break inside a call's parameters, which could lead to weird
2477     // "hanging" indents. The exception is the very last "./->" to support this
2478     // frequent pattern:
2479     //
2480     //   aaaaaaaa.aaaaaaaa.bbbbbbb().ccccccccccccccccccccc(
2481     //       dddddddd);
2482     //
2483     // which might otherwise be blown up onto many lines. Here, clang-format
2484     // won't produce "hanging" indents anyway as there is no other trailing
2485     // call.
2486     //
2487     // Also apply higher penalty is not a call as that might lead to a wrapping
2488     // like:
2489     //
2490     //   aaaaaaa
2491     //       .aaaaaaaaa.bbbbbbbb(cccccccc);
2492     return !Right.NextOperator || !Right.NextOperator->Previous->closesScope()
2493                ? 150
2494                : 35;
2495   }
2496
2497   if (Right.is(TT_TrailingAnnotation) &&
2498       (!Right.Next || Right.Next->isNot(tok::l_paren))) {
2499     // Moving trailing annotations to the next line is fine for ObjC method
2500     // declarations.
2501     if (Line.startsWith(TT_ObjCMethodSpecifier))
2502       return 10;
2503     // Generally, breaking before a trailing annotation is bad unless it is
2504     // function-like. It seems to be especially preferable to keep standard
2505     // annotations (i.e. "const", "final" and "override") on the same line.
2506     // Use a slightly higher penalty after ")" so that annotations like
2507     // "const override" are kept together.
2508     bool is_short_annotation = Right.TokenText.size() < 10;
2509     return (Left.is(tok::r_paren) ? 100 : 120) + (is_short_annotation ? 50 : 0);
2510   }
2511
2512   // In for-loops, prefer breaking at ',' and ';'.
2513   if (Line.startsWith(tok::kw_for) && Left.is(tok::equal))
2514     return 4;
2515
2516   // In Objective-C method expressions, prefer breaking before "param:" over
2517   // breaking after it.
2518   if (Right.is(TT_SelectorName))
2519     return 0;
2520   if (Left.is(tok::colon) && Left.is(TT_ObjCMethodExpr))
2521     return Line.MightBeFunctionDecl ? 50 : 500;
2522
2523   // In Objective-C type declarations, avoid breaking after the category's
2524   // open paren (we'll prefer breaking after the protocol list's opening
2525   // angle bracket, if present).
2526   if (Line.Type == LT_ObjCDecl && Left.is(tok::l_paren) && Left.Previous &&
2527       Left.Previous->isOneOf(tok::identifier, tok::greater))
2528     return 500;
2529
2530   if (Left.is(tok::l_paren) && InFunctionDecl &&
2531       Style.AlignAfterOpenBracket != FormatStyle::BAS_DontAlign)
2532     return 100;
2533   if (Left.is(tok::l_paren) && Left.Previous &&
2534       (Left.Previous->is(tok::kw_for) || Left.Previous->isIf()))
2535     return 1000;
2536   if (Left.is(tok::equal) && InFunctionDecl)
2537     return 110;
2538   if (Right.is(tok::r_brace))
2539     return 1;
2540   if (Left.is(TT_TemplateOpener))
2541     return 100;
2542   if (Left.opensScope()) {
2543     if (Style.AlignAfterOpenBracket == FormatStyle::BAS_DontAlign)
2544       return 0;
2545     if (Left.is(tok::l_brace) && !Style.Cpp11BracedListStyle)
2546       return 19;
2547     return Left.ParameterCount > 1 ? Style.PenaltyBreakBeforeFirstCallParameter
2548                                    : 19;
2549   }
2550   if (Left.is(TT_JavaAnnotation))
2551     return 50;
2552
2553   if (Left.is(TT_UnaryOperator))
2554     return 60;
2555   if (Left.isOneOf(tok::plus, tok::comma) && Left.Previous &&
2556       Left.Previous->isLabelString() &&
2557       (Left.NextOperator || Left.OperatorIndex != 0))
2558     return 50;
2559   if (Right.is(tok::plus) && Left.isLabelString() &&
2560       (Right.NextOperator || Right.OperatorIndex != 0))
2561     return 25;
2562   if (Left.is(tok::comma))
2563     return 1;
2564   if (Right.is(tok::lessless) && Left.isLabelString() &&
2565       (Right.NextOperator || Right.OperatorIndex != 1))
2566     return 25;
2567   if (Right.is(tok::lessless)) {
2568     // Breaking at a << is really cheap.
2569     if (!Left.is(tok::r_paren) || Right.OperatorIndex > 0)
2570       // Slightly prefer to break before the first one in log-like statements.
2571       return 2;
2572     return 1;
2573   }
2574   if (Left.ClosesTemplateDeclaration)
2575     return Style.PenaltyBreakTemplateDeclaration;
2576   if (Left.is(TT_ConditionalExpr))
2577     return prec::Conditional;
2578   prec::Level Level = Left.getPrecedence();
2579   if (Level == prec::Unknown)
2580     Level = Right.getPrecedence();
2581   if (Level == prec::Assignment)
2582     return Style.PenaltyBreakAssignment;
2583   if (Level != prec::Unknown)
2584     return Level;
2585
2586   return 3;
2587 }
2588
2589 bool TokenAnnotator::spaceRequiredBeforeParens(const FormatToken &Right) const {
2590   return Style.SpaceBeforeParens == FormatStyle::SBPO_Always ||
2591          (Style.SpaceBeforeParens == FormatStyle::SBPO_NonEmptyParentheses &&
2592           Right.ParameterCount > 0);
2593 }
2594
2595 /// Returns \c true if the token is followed by a boolean condition, \c false
2596 /// otherwise.
2597 static bool isKeywordWithCondition(const FormatToken &Tok) {
2598   return Tok.isOneOf(tok::kw_if, tok::kw_for, tok::kw_while, tok::kw_switch,
2599                      tok::kw_constexpr, tok::kw_catch);
2600 }
2601
2602 bool TokenAnnotator::spaceRequiredBetween(const AnnotatedLine &Line,
2603                                           const FormatToken &Left,
2604                                           const FormatToken &Right) {
2605   if (Left.is(tok::kw_return) && Right.isNot(tok::semi))
2606     return true;
2607   if (Left.is(Keywords.kw_assert) && Style.Language == FormatStyle::LK_Java)
2608     return true;
2609   if (Style.ObjCSpaceAfterProperty && Line.Type == LT_ObjCProperty &&
2610       Left.Tok.getObjCKeywordID() == tok::objc_property)
2611     return true;
2612   if (Right.is(tok::hashhash))
2613     return Left.is(tok::hash);
2614   if (Left.isOneOf(tok::hashhash, tok::hash))
2615     return Right.is(tok::hash);
2616   if ((Left.is(tok::l_paren) && Right.is(tok::r_paren)) ||
2617       (Left.is(tok::l_brace) && Left.BlockKind != BK_Block &&
2618        Right.is(tok::r_brace) && Right.BlockKind != BK_Block))
2619     return Style.SpaceInEmptyParentheses;
2620   if (Style.SpacesInConditionalStatement) {
2621     if (Left.is(tok::l_paren) && Left.Previous &&
2622         isKeywordWithCondition(*Left.Previous))
2623       return true;
2624     if (Right.is(tok::r_paren) && Right.MatchingParen &&
2625         Right.MatchingParen->Previous &&
2626         isKeywordWithCondition(*Right.MatchingParen->Previous))
2627       return true;
2628   }
2629   if (Left.is(tok::l_paren) || Right.is(tok::r_paren))
2630     return (Right.is(TT_CastRParen) ||
2631             (Left.MatchingParen && Left.MatchingParen->is(TT_CastRParen)))
2632                ? Style.SpacesInCStyleCastParentheses
2633                : Style.SpacesInParentheses;
2634   if (Right.isOneOf(tok::semi, tok::comma))
2635     return false;
2636   if (Right.is(tok::less) && Line.Type == LT_ObjCDecl) {
2637     bool IsLightweightGeneric = Right.MatchingParen &&
2638                                 Right.MatchingParen->Next &&
2639                                 Right.MatchingParen->Next->is(tok::colon);
2640     return !IsLightweightGeneric && Style.ObjCSpaceBeforeProtocolList;
2641   }
2642   if (Right.is(tok::less) && Left.is(tok::kw_template))
2643     return Style.SpaceAfterTemplateKeyword;
2644   if (Left.isOneOf(tok::exclaim, tok::tilde))
2645     return false;
2646   if (Left.is(tok::at) &&
2647       Right.isOneOf(tok::identifier, tok::string_literal, tok::char_constant,
2648                     tok::numeric_constant, tok::l_paren, tok::l_brace,
2649                     tok::kw_true, tok::kw_false))
2650     return false;
2651   if (Left.is(tok::colon))
2652     return !Left.is(TT_ObjCMethodExpr);
2653   if (Left.is(tok::coloncolon))
2654     return false;
2655   if (Left.is(tok::less) || Right.isOneOf(tok::greater, tok::less)) {
2656     if (Style.Language == FormatStyle::LK_TextProto ||
2657         (Style.Language == FormatStyle::LK_Proto &&
2658          (Left.is(TT_DictLiteral) || Right.is(TT_DictLiteral)))) {
2659       // Format empty list as `<>`.
2660       if (Left.is(tok::less) && Right.is(tok::greater))
2661         return false;
2662       return !Style.Cpp11BracedListStyle;
2663     }
2664     return false;
2665   }
2666   if (Right.is(tok::ellipsis))
2667     return Left.Tok.isLiteral() || (Left.is(tok::identifier) && Left.Previous &&
2668                                     Left.Previous->is(tok::kw_case));
2669   if (Left.is(tok::l_square) && Right.is(tok::amp))
2670     return Style.SpacesInSquareBrackets;
2671   if (Right.is(TT_PointerOrReference)) {
2672     if (Left.is(tok::r_paren) && Line.MightBeFunctionDecl) {
2673       if (!Left.MatchingParen)
2674         return true;
2675       FormatToken *TokenBeforeMatchingParen =
2676           Left.MatchingParen->getPreviousNonComment();
2677       if (!TokenBeforeMatchingParen ||
2678           !TokenBeforeMatchingParen->isOneOf(tok::kw_typeof, tok::kw_decltype,
2679                                              TT_TypenameMacro))
2680         return true;
2681     }
2682     return (Left.Tok.isLiteral() ||
2683             (!Left.isOneOf(TT_PointerOrReference, tok::l_paren) &&
2684              (Style.PointerAlignment != FormatStyle::PAS_Left ||
2685               (Line.IsMultiVariableDeclStmt &&
2686                (Left.NestingLevel == 0 ||
2687                 (Left.NestingLevel == 1 && Line.First->is(tok::kw_for)))))));
2688   }
2689   if (Right.is(TT_FunctionTypeLParen) && Left.isNot(tok::l_paren) &&
2690       (!Left.is(TT_PointerOrReference) ||
2691        (Style.PointerAlignment != FormatStyle::PAS_Right &&
2692         !Line.IsMultiVariableDeclStmt)))
2693     return true;
2694   if (Left.is(TT_PointerOrReference))
2695     return Right.Tok.isLiteral() || Right.is(TT_BlockComment) ||
2696            (Right.isOneOf(Keywords.kw_override, Keywords.kw_final) &&
2697             !Right.is(TT_StartOfName)) ||
2698            (Right.is(tok::l_brace) && Right.BlockKind == BK_Block) ||
2699            (!Right.isOneOf(TT_PointerOrReference, TT_ArraySubscriptLSquare,
2700                            tok::l_paren) &&
2701             (Style.PointerAlignment != FormatStyle::PAS_Right &&
2702              !Line.IsMultiVariableDeclStmt) &&
2703             Left.Previous &&
2704             !Left.Previous->isOneOf(tok::l_paren, tok::coloncolon,
2705                                     tok::l_square));
2706   if (Right.is(tok::star) && Left.is(tok::l_paren))
2707     return false;
2708   if (Right.isOneOf(tok::star, tok::amp, tok::ampamp) &&
2709       (Left.is(tok::identifier) || Left.isSimpleTypeSpecifier()) &&
2710       // Space between the type and the * in:
2711       //   operator void*()
2712       //   operator char*()
2713       //   operator /*comment*/ const char*()
2714       //   operator volatile /*comment*/ char*()
2715       //   operator Foo*()
2716       // dependent on PointerAlignment style.
2717       Left.Previous &&
2718       (Left.Previous->endsSequence(tok::kw_operator) ||
2719        Left.Previous->endsSequence(tok::kw_const, tok::kw_operator) ||
2720        Left.Previous->endsSequence(tok::kw_volatile, tok::kw_operator)))
2721     return (Style.PointerAlignment != FormatStyle::PAS_Left);
2722   const auto SpaceRequiredForArrayInitializerLSquare =
2723       [](const FormatToken &LSquareTok, const FormatStyle &Style) {
2724         return Style.SpacesInContainerLiterals ||
2725                ((Style.Language == FormatStyle::LK_Proto ||
2726                  Style.Language == FormatStyle::LK_TextProto) &&
2727                 !Style.Cpp11BracedListStyle &&
2728                 LSquareTok.endsSequence(tok::l_square, tok::colon,
2729                                         TT_SelectorName));
2730       };
2731   if (Left.is(tok::l_square))
2732     return (Left.is(TT_ArrayInitializerLSquare) && Right.isNot(tok::r_square) &&
2733             SpaceRequiredForArrayInitializerLSquare(Left, Style)) ||
2734            (Left.isOneOf(TT_ArraySubscriptLSquare, TT_StructuredBindingLSquare,
2735                          TT_LambdaLSquare) &&
2736             Style.SpacesInSquareBrackets && Right.isNot(tok::r_square));
2737   if (Right.is(tok::r_square))
2738     return Right.MatchingParen &&
2739            ((Right.MatchingParen->is(TT_ArrayInitializerLSquare) &&
2740              SpaceRequiredForArrayInitializerLSquare(*Right.MatchingParen,
2741                                                      Style)) ||
2742             (Style.SpacesInSquareBrackets &&
2743              Right.MatchingParen->isOneOf(TT_ArraySubscriptLSquare,
2744                                           TT_StructuredBindingLSquare,
2745                                           TT_LambdaLSquare)) ||
2746             Right.MatchingParen->is(TT_AttributeParen));
2747   if (Right.is(tok::l_square) &&
2748       !Right.isOneOf(TT_ObjCMethodExpr, TT_LambdaLSquare,
2749                      TT_DesignatedInitializerLSquare,
2750                      TT_StructuredBindingLSquare, TT_AttributeSquare) &&
2751       !Left.isOneOf(tok::numeric_constant, TT_DictLiteral) &&
2752       !(!Left.is(tok::r_square) && Style.SpaceBeforeSquareBrackets &&
2753         Right.is(TT_ArraySubscriptLSquare)))
2754     return false;
2755   if (Left.is(tok::l_brace) && Right.is(tok::r_brace))
2756     return !Left.Children.empty(); // No spaces in "{}".
2757   if ((Left.is(tok::l_brace) && Left.BlockKind != BK_Block) ||
2758       (Right.is(tok::r_brace) && Right.MatchingParen &&
2759        Right.MatchingParen->BlockKind != BK_Block))
2760     return Style.Cpp11BracedListStyle ? Style.SpacesInParentheses : true;
2761   if (Left.is(TT_BlockComment))
2762     // No whitespace in x(/*foo=*/1), except for JavaScript.
2763     return Style.Language == FormatStyle::LK_JavaScript ||
2764            !Left.TokenText.endswith("=*/");
2765   if (Right.is(tok::l_paren)) {
2766     if ((Left.is(tok::r_paren) && Left.is(TT_AttributeParen)) ||
2767         (Left.is(tok::r_square) && Left.is(TT_AttributeSquare)))
2768       return true;
2769     return Line.Type == LT_ObjCDecl || Left.is(tok::semi) ||
2770            (Style.SpaceBeforeParens != FormatStyle::SBPO_Never &&
2771             (Left.isOneOf(tok::pp_elif, tok::kw_for, tok::kw_while,
2772                           tok::kw_switch, tok::kw_case, TT_ForEachMacro,
2773                           TT_ObjCForIn) ||
2774              Left.isIf(Line.Type != LT_PreprocessorDirective) ||
2775              (Left.isOneOf(tok::kw_try, Keywords.kw___except, tok::kw_catch,
2776                            tok::kw_new, tok::kw_delete) &&
2777               (!Left.Previous || Left.Previous->isNot(tok::period))))) ||
2778            (spaceRequiredBeforeParens(Right) &&
2779             (Left.is(tok::identifier) || Left.isFunctionLikeKeyword() ||
2780              Left.is(tok::r_paren) || Left.isSimpleTypeSpecifier() ||
2781              (Left.is(tok::r_square) && Left.MatchingParen &&
2782               Left.MatchingParen->is(TT_LambdaLSquare))) &&
2783             Line.Type != LT_PreprocessorDirective);
2784   }
2785   if (Left.is(tok::at) && Right.Tok.getObjCKeywordID() != tok::objc_not_keyword)
2786     return false;
2787   if (Right.is(TT_UnaryOperator))
2788     return !Left.isOneOf(tok::l_paren, tok::l_square, tok::at) &&
2789            (Left.isNot(tok::colon) || Left.isNot(TT_ObjCMethodExpr));
2790   if ((Left.isOneOf(tok::identifier, tok::greater, tok::r_square,
2791                     tok::r_paren) ||
2792        Left.isSimpleTypeSpecifier()) &&
2793       Right.is(tok::l_brace) && Right.getNextNonComment() &&
2794       Right.BlockKind != BK_Block)
2795     return false;
2796   if (Left.is(tok::period) || Right.is(tok::period))
2797     return false;
2798   if (Right.is(tok::hash) && Left.is(tok::identifier) && Left.TokenText == "L")
2799     return false;
2800   if (Left.is(TT_TemplateCloser) && Left.MatchingParen &&
2801       Left.MatchingParen->Previous &&
2802       (Left.MatchingParen->Previous->is(tok::period) ||
2803        Left.MatchingParen->Previous->is(tok::coloncolon)))
2804     // Java call to generic function with explicit type:
2805     // A.<B<C<...>>>DoSomething();
2806     // A::<B<C<...>>>DoSomething();  // With a Java 8 method reference.
2807     return false;
2808   if (Left.is(TT_TemplateCloser) && Right.is(tok::l_square))
2809     return false;
2810   if (Left.is(tok::l_brace) && Left.endsSequence(TT_DictLiteral, tok::at))
2811     // Objective-C dictionary literal -> no space after opening brace.
2812     return false;
2813   if (Right.is(tok::r_brace) && Right.MatchingParen &&
2814       Right.MatchingParen->endsSequence(TT_DictLiteral, tok::at))
2815     // Objective-C dictionary literal -> no space before closing brace.
2816     return false;
2817   if (Right.Type == TT_TrailingAnnotation &&
2818       Right.isOneOf(tok::amp, tok::ampamp) &&
2819       Left.isOneOf(tok::kw_const, tok::kw_volatile) &&
2820       (!Right.Next || Right.Next->is(tok::semi)))
2821     // Match const and volatile ref-qualifiers without any additional
2822     // qualifiers such as
2823     // void Fn() const &;
2824     return Style.PointerAlignment != FormatStyle::PAS_Left;
2825   return true;
2826 }
2827
2828 bool TokenAnnotator::spaceRequiredBefore(const AnnotatedLine &Line,
2829                                          const FormatToken &Right) {
2830   const FormatToken &Left = *Right.Previous;
2831   if (Right.Tok.getIdentifierInfo() && Left.Tok.getIdentifierInfo())
2832     return true; // Never ever merge two identifiers.
2833   if (Style.isCpp()) {
2834     if (Left.is(tok::kw_operator))
2835       return Right.is(tok::coloncolon);
2836     if (Right.is(tok::l_brace) && Right.BlockKind == BK_BracedInit &&
2837         !Left.opensScope() && Style.SpaceBeforeCpp11BracedList)
2838       return true;
2839   } else if (Style.Language == FormatStyle::LK_Proto ||
2840              Style.Language == FormatStyle::LK_TextProto) {
2841     if (Right.is(tok::period) &&
2842         Left.isOneOf(Keywords.kw_optional, Keywords.kw_required,
2843                      Keywords.kw_repeated, Keywords.kw_extend))
2844       return true;
2845     if (Right.is(tok::l_paren) &&
2846         Left.isOneOf(Keywords.kw_returns, Keywords.kw_option))
2847       return true;
2848     if (Right.isOneOf(tok::l_brace, tok::less) && Left.is(TT_SelectorName))
2849       return true;
2850     // Slashes occur in text protocol extension syntax: [type/type] { ... }.
2851     if (Left.is(tok::slash) || Right.is(tok::slash))
2852       return false;
2853     if (Left.MatchingParen &&
2854         Left.MatchingParen->is(TT_ProtoExtensionLSquare) &&
2855         Right.isOneOf(tok::l_brace, tok::less))
2856       return !Style.Cpp11BracedListStyle;
2857     // A percent is probably part of a formatting specification, such as %lld.
2858     if (Left.is(tok::percent))
2859       return false;
2860     // Preserve the existence of a space before a percent for cases like 0x%04x
2861     // and "%d %d"
2862     if (Left.is(tok::numeric_constant) && Right.is(tok::percent))
2863       return Right.WhitespaceRange.getEnd() != Right.WhitespaceRange.getBegin();
2864   } else if (Style.isCSharp()) {
2865     // space between type and variable e.g. Dictionary<string,string> foo;
2866     if (Left.is(TT_TemplateCloser) && Right.is(TT_StartOfName))
2867       return true;
2868     // space between keywords and paren e.g. "using ("
2869     if (Right.is(tok::l_paren))
2870       if (Left.is(tok::kw_using))
2871         return spaceRequiredBeforeParens(Left);
2872   } else if (Style.Language == FormatStyle::LK_JavaScript) {
2873     if (Left.is(TT_JsFatArrow))
2874       return true;
2875     // for await ( ...
2876     if (Right.is(tok::l_paren) && Left.is(Keywords.kw_await) && Left.Previous &&
2877         Left.Previous->is(tok::kw_for))
2878       return true;
2879     if (Left.is(Keywords.kw_async) && Right.is(tok::l_paren) &&
2880         Right.MatchingParen) {
2881       const FormatToken *Next = Right.MatchingParen->getNextNonComment();
2882       // An async arrow function, for example: `x = async () => foo();`,
2883       // as opposed to calling a function called async: `x = async();`
2884       if (Next && Next->is(TT_JsFatArrow))
2885         return true;
2886     }
2887     if ((Left.is(TT_TemplateString) && Left.TokenText.endswith("${")) ||
2888         (Right.is(TT_TemplateString) && Right.TokenText.startswith("}")))
2889       return false;
2890     // In tagged template literals ("html`bar baz`"), there is no space between
2891     // the tag identifier and the template string. getIdentifierInfo makes sure
2892     // that the identifier is not a pseudo keyword like `yield`, either.
2893     if (Left.is(tok::identifier) && Keywords.IsJavaScriptIdentifier(Left) &&
2894         Right.is(TT_TemplateString))
2895       return false;
2896     if (Right.is(tok::star) &&
2897         Left.isOneOf(Keywords.kw_function, Keywords.kw_yield))
2898       return false;
2899     if (Right.isOneOf(tok::l_brace, tok::l_square) &&
2900         Left.isOneOf(Keywords.kw_function, Keywords.kw_yield,
2901                      Keywords.kw_extends, Keywords.kw_implements))
2902       return true;
2903     if (Right.is(tok::l_paren)) {
2904       // JS methods can use some keywords as names (e.g. `delete()`).
2905       if (Line.MustBeDeclaration && Left.Tok.getIdentifierInfo())
2906         return false;
2907       // Valid JS method names can include keywords, e.g. `foo.delete()` or
2908       // `bar.instanceof()`. Recognize call positions by preceding period.
2909       if (Left.Previous && Left.Previous->is(tok::period) &&
2910           Left.Tok.getIdentifierInfo())
2911         return false;
2912       // Additional unary JavaScript operators that need a space after.
2913       if (Left.isOneOf(tok::kw_throw, Keywords.kw_await, Keywords.kw_typeof,
2914                        tok::kw_void))
2915         return true;
2916     }
2917     // `foo as const;` casts into a const type.
2918     if (Left.endsSequence(tok::kw_const, Keywords.kw_as)) {
2919       return false;
2920     }
2921     if ((Left.isOneOf(Keywords.kw_let, Keywords.kw_var, Keywords.kw_in,
2922                       tok::kw_const) ||
2923          // "of" is only a keyword if it appears after another identifier
2924          // (e.g. as "const x of y" in a for loop), or after a destructuring
2925          // operation (const [x, y] of z, const {a, b} of c).
2926          (Left.is(Keywords.kw_of) && Left.Previous &&
2927           (Left.Previous->Tok.is(tok::identifier) ||
2928            Left.Previous->isOneOf(tok::r_square, tok::r_brace)))) &&
2929         (!Left.Previous || !Left.Previous->is(tok::period)))
2930       return true;
2931     if (Left.isOneOf(tok::kw_for, Keywords.kw_as) && Left.Previous &&
2932         Left.Previous->is(tok::period) && Right.is(tok::l_paren))
2933       return false;
2934     if (Left.is(Keywords.kw_as) &&
2935         Right.isOneOf(tok::l_square, tok::l_brace, tok::l_paren))
2936       return true;
2937     if (Left.is(tok::kw_default) && Left.Previous &&
2938         Left.Previous->is(tok::kw_export))
2939       return true;
2940     if (Left.is(Keywords.kw_is) && Right.is(tok::l_brace))
2941       return true;
2942     if (Right.isOneOf(TT_JsTypeColon, TT_JsTypeOptionalQuestion))
2943       return false;
2944     if (Left.is(TT_JsTypeOperator) || Right.is(TT_JsTypeOperator))
2945       return false;
2946     if ((Left.is(tok::l_brace) || Right.is(tok::r_brace)) &&
2947         Line.First->isOneOf(Keywords.kw_import, tok::kw_export))
2948       return false;
2949     if (Left.is(tok::ellipsis))
2950       return false;
2951     if (Left.is(TT_TemplateCloser) &&
2952         !Right.isOneOf(tok::equal, tok::l_brace, tok::comma, tok::l_square,
2953                        Keywords.kw_implements, Keywords.kw_extends))
2954       // Type assertions ('<type>expr') are not followed by whitespace. Other
2955       // locations that should have whitespace following are identified by the
2956       // above set of follower tokens.
2957       return false;
2958     if (Right.is(TT_JsNonNullAssertion))
2959       return false;
2960     if (Left.is(TT_JsNonNullAssertion) &&
2961         Right.isOneOf(Keywords.kw_as, Keywords.kw_in))
2962       return true; // "x! as string", "x! in y"
2963   } else if (Style.Language == FormatStyle::LK_Java) {
2964     if (Left.is(tok::r_square) && Right.is(tok::l_brace))
2965       return true;
2966     if (Left.is(Keywords.kw_synchronized) && Right.is(tok::l_paren))
2967       return Style.SpaceBeforeParens != FormatStyle::SBPO_Never;
2968     if ((Left.isOneOf(tok::kw_static, tok::kw_public, tok::kw_private,
2969                       tok::kw_protected) ||
2970          Left.isOneOf(Keywords.kw_final, Keywords.kw_abstract,
2971                       Keywords.kw_native)) &&
2972         Right.is(TT_TemplateOpener))
2973       return true;
2974   }
2975   if (Left.is(TT_ImplicitStringLiteral))
2976     return Right.WhitespaceRange.getBegin() != Right.WhitespaceRange.getEnd();
2977   if (Line.Type == LT_ObjCMethodDecl) {
2978     if (Left.is(TT_ObjCMethodSpecifier))
2979       return true;
2980     if (Left.is(tok::r_paren) && canBeObjCSelectorComponent(Right))
2981       // Don't space between ')' and <id> or ')' and 'new'. 'new' is not a
2982       // keyword in Objective-C, and '+ (instancetype)new;' is a standard class
2983       // method declaration.
2984       return false;
2985   }
2986   if (Line.Type == LT_ObjCProperty &&
2987       (Right.is(tok::equal) || Left.is(tok::equal)))
2988     return false;
2989
2990   if (Right.isOneOf(TT_TrailingReturnArrow, TT_LambdaArrow) ||
2991       Left.isOneOf(TT_TrailingReturnArrow, TT_LambdaArrow))
2992     return true;
2993   if (Right.is(TT_OverloadedOperatorLParen))
2994     return spaceRequiredBeforeParens(Right);
2995   if (Left.is(tok::comma))
2996     return true;
2997   if (Right.is(tok::comma))
2998     return false;
2999   if (Right.is(TT_ObjCBlockLParen))
3000     return true;
3001   if (Right.is(TT_CtorInitializerColon))
3002     return Style.SpaceBeforeCtorInitializerColon;
3003   if (Right.is(TT_InheritanceColon) && !Style.SpaceBeforeInheritanceColon)
3004     return false;
3005   if (Right.is(TT_RangeBasedForLoopColon) &&
3006       !Style.SpaceBeforeRangeBasedForLoopColon)
3007     return false;
3008   if (Right.is(tok::colon)) {
3009     if (Line.First->isOneOf(tok::kw_case, tok::kw_default) ||
3010         !Right.getNextNonComment() || Right.getNextNonComment()->is(tok::semi))
3011       return false;
3012     if (Right.is(TT_ObjCMethodExpr))
3013       return false;
3014     if (Left.is(tok::question))
3015       return false;
3016     if (Right.is(TT_InlineASMColon) && Left.is(tok::coloncolon))
3017       return false;
3018     if (Right.is(TT_DictLiteral))
3019       return Style.SpacesInContainerLiterals;
3020     if (Right.is(TT_AttributeColon))
3021       return false;
3022     return true;
3023   }
3024   if (Left.is(TT_UnaryOperator)) {
3025     if (!Right.is(tok::l_paren)) {
3026       // The alternative operators for ~ and ! are "compl" and "not".
3027       // If they are used instead, we do not want to combine them with
3028       // the token to the right, unless that is a left paren.
3029       if (Left.is(tok::exclaim) && Left.TokenText == "not")
3030         return true;
3031       if (Left.is(tok::tilde) && Left.TokenText == "compl")
3032         return true;
3033       // Lambda captures allow for a lone &, so "&]" needs to be properly
3034       // handled.
3035       if (Left.is(tok::amp) && Right.is(tok::r_square))
3036         return Style.SpacesInSquareBrackets;
3037     }
3038     return (Style.SpaceAfterLogicalNot && Left.is(tok::exclaim)) ||
3039            Right.is(TT_BinaryOperator);
3040   }
3041
3042   // If the next token is a binary operator or a selector name, we have
3043   // incorrectly classified the parenthesis as a cast. FIXME: Detect correctly.
3044   if (Left.is(TT_CastRParen))
3045     return Style.SpaceAfterCStyleCast ||
3046            Right.isOneOf(TT_BinaryOperator, TT_SelectorName);
3047
3048   if (Left.is(tok::greater) && Right.is(tok::greater)) {
3049     if (Style.Language == FormatStyle::LK_TextProto ||
3050         (Style.Language == FormatStyle::LK_Proto && Left.is(TT_DictLiteral)))
3051       return !Style.Cpp11BracedListStyle;
3052     return Right.is(TT_TemplateCloser) && Left.is(TT_TemplateCloser) &&
3053            (Style.Standard < FormatStyle::LS_Cpp11 || Style.SpacesInAngles);
3054   }
3055   if (Right.isOneOf(tok::arrow, tok::arrowstar, tok::periodstar) ||
3056       Left.isOneOf(tok::arrow, tok::period, tok::arrowstar, tok::periodstar) ||
3057       (Right.is(tok::period) && Right.isNot(TT_DesignatedInitializerPeriod)))
3058     return false;
3059   if (!Style.SpaceBeforeAssignmentOperators && Left.isNot(TT_TemplateCloser) &&
3060       Right.getPrecedence() == prec::Assignment)
3061     return false;
3062   if (Style.Language == FormatStyle::LK_Java && Right.is(tok::coloncolon) &&
3063       (Left.is(tok::identifier) || Left.is(tok::kw_this)))
3064     return false;
3065   if (Right.is(tok::coloncolon) && Left.is(tok::identifier))
3066     // Generally don't remove existing spaces between an identifier and "::".
3067     // The identifier might actually be a macro name such as ALWAYS_INLINE. If
3068     // this turns out to be too lenient, add analysis of the identifier itself.
3069     return Right.WhitespaceRange.getBegin() != Right.WhitespaceRange.getEnd();
3070   if (Right.is(tok::coloncolon) &&
3071       !Left.isOneOf(tok::l_brace, tok::comment, tok::l_paren))
3072     return (Left.is(TT_TemplateOpener) &&
3073             Style.Standard < FormatStyle::LS_Cpp11) ||
3074            !(Left.isOneOf(tok::l_paren, tok::r_paren, tok::l_square,
3075                           tok::kw___super, TT_TemplateCloser,
3076                           TT_TemplateOpener)) ||
3077            (Left.is(tok ::l_paren) && Style.SpacesInParentheses);
3078   if ((Left.is(TT_TemplateOpener)) != (Right.is(TT_TemplateCloser)))
3079     return Style.SpacesInAngles;
3080   // Space before TT_StructuredBindingLSquare.
3081   if (Right.is(TT_StructuredBindingLSquare))
3082     return !Left.isOneOf(tok::amp, tok::ampamp) ||
3083            Style.PointerAlignment != FormatStyle::PAS_Right;
3084   // Space before & or && following a TT_StructuredBindingLSquare.
3085   if (Right.Next && Right.Next->is(TT_StructuredBindingLSquare) &&
3086       Right.isOneOf(tok::amp, tok::ampamp))
3087     return Style.PointerAlignment != FormatStyle::PAS_Left;
3088   if ((Right.is(TT_BinaryOperator) && !Left.is(tok::l_paren)) ||
3089       (Left.isOneOf(TT_BinaryOperator, TT_ConditionalExpr) &&
3090        !Right.is(tok::r_paren)))
3091     return true;
3092   if (Left.is(TT_TemplateCloser) && Right.is(tok::l_paren) &&
3093       Right.isNot(TT_FunctionTypeLParen))
3094     return spaceRequiredBeforeParens(Right);
3095   if (Right.is(TT_TemplateOpener) && Left.is(tok::r_paren) &&
3096       Left.MatchingParen && Left.MatchingParen->is(TT_OverloadedOperatorLParen))
3097     return false;
3098   if (Right.is(tok::less) && Left.isNot(tok::l_paren) &&
3099       Line.startsWith(tok::hash))
3100     return true;
3101   if (Right.is(TT_TrailingUnaryOperator))
3102     return false;
3103   if (Left.is(TT_RegexLiteral))
3104     return false;
3105   return spaceRequiredBetween(Line, Left, Right);
3106 }
3107
3108 // Returns 'true' if 'Tok' is a brace we'd want to break before in Allman style.
3109 static bool isAllmanBrace(const FormatToken &Tok) {
3110   return Tok.is(tok::l_brace) && Tok.BlockKind == BK_Block &&
3111          !Tok.isOneOf(TT_ObjCBlockLBrace, TT_LambdaLBrace, TT_DictLiteral);
3112 }
3113
3114 bool TokenAnnotator::mustBreakBefore(const AnnotatedLine &Line,
3115                                      const FormatToken &Right) {
3116   const FormatToken &Left = *Right.Previous;
3117   if (Right.NewlinesBefore > 1 && Style.MaxEmptyLinesToKeep > 0)
3118     return true;
3119
3120   if (Style.Language == FormatStyle::LK_JavaScript) {
3121     // FIXME: This might apply to other languages and token kinds.
3122     if (Right.is(tok::string_literal) && Left.is(tok::plus) && Left.Previous &&
3123         Left.Previous->is(tok::string_literal))
3124       return true;
3125     if (Left.is(TT_DictLiteral) && Left.is(tok::l_brace) && Line.Level == 0 &&
3126         Left.Previous && Left.Previous->is(tok::equal) &&
3127         Line.First->isOneOf(tok::identifier, Keywords.kw_import, tok::kw_export,
3128                             tok::kw_const) &&
3129         // kw_var/kw_let are pseudo-tokens that are tok::identifier, so match
3130         // above.
3131         !Line.First->isOneOf(Keywords.kw_var, Keywords.kw_let))
3132       // Object literals on the top level of a file are treated as "enum-style".
3133       // Each key/value pair is put on a separate line, instead of bin-packing.
3134       return true;
3135     if (Left.is(tok::l_brace) && Line.Level == 0 &&
3136         (Line.startsWith(tok::kw_enum) ||
3137          Line.startsWith(tok::kw_const, tok::kw_enum) ||
3138          Line.startsWith(tok::kw_export, tok::kw_enum) ||
3139          Line.startsWith(tok::kw_export, tok::kw_const, tok::kw_enum)))
3140       // JavaScript top-level enum key/value pairs are put on separate lines
3141       // instead of bin-packing.
3142       return true;
3143     if (Right.is(tok::r_brace) && Left.is(tok::l_brace) &&
3144         !Left.Children.empty())
3145       // Support AllowShortFunctionsOnASingleLine for JavaScript.
3146       return Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_None ||
3147              Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_Empty ||
3148              (Left.NestingLevel == 0 && Line.Level == 0 &&
3149               Style.AllowShortFunctionsOnASingleLine &
3150                   FormatStyle::SFS_InlineOnly);
3151   } else if (Style.Language == FormatStyle::LK_Java) {
3152     if (Right.is(tok::plus) && Left.is(tok::string_literal) && Right.Next &&
3153         Right.Next->is(tok::string_literal))
3154       return true;
3155   } else if (Style.Language == FormatStyle::LK_Cpp ||
3156              Style.Language == FormatStyle::LK_ObjC ||
3157              Style.Language == FormatStyle::LK_Proto ||
3158              Style.Language == FormatStyle::LK_TableGen ||
3159              Style.Language == FormatStyle::LK_TextProto) {
3160     if (Left.isStringLiteral() && Right.isStringLiteral())
3161       return true;
3162   }
3163
3164   // If the last token before a '}', ']', or ')' is a comma or a trailing
3165   // comment, the intention is to insert a line break after it in order to make
3166   // shuffling around entries easier. Import statements, especially in
3167   // JavaScript, can be an exception to this rule.
3168   if (Style.JavaScriptWrapImports || Line.Type != LT_ImportStatement) {
3169     const FormatToken *BeforeClosingBrace = nullptr;
3170     if ((Left.isOneOf(tok::l_brace, TT_ArrayInitializerLSquare) ||
3171          (Style.Language == FormatStyle::LK_JavaScript &&
3172           Left.is(tok::l_paren))) &&
3173         Left.BlockKind != BK_Block && Left.MatchingParen)
3174       BeforeClosingBrace = Left.MatchingParen->Previous;
3175     else if (Right.MatchingParen &&
3176              (Right.MatchingParen->isOneOf(tok::l_brace,
3177                                            TT_ArrayInitializerLSquare) ||
3178               (Style.Language == FormatStyle::LK_JavaScript &&
3179                Right.MatchingParen->is(tok::l_paren))))
3180       BeforeClosingBrace = &Left;
3181     if (BeforeClosingBrace && (BeforeClosingBrace->is(tok::comma) ||
3182                                BeforeClosingBrace->isTrailingComment()))
3183       return true;
3184   }
3185
3186   if (Right.is(tok::comment))
3187     return Left.BlockKind != BK_BracedInit &&
3188            Left.isNot(TT_CtorInitializerColon) &&
3189            (Right.NewlinesBefore > 0 && Right.HasUnescapedNewline);
3190   if (Left.isTrailingComment())
3191     return true;
3192   if (Right.Previous->IsUnterminatedLiteral)
3193     return true;
3194   if (Right.is(tok::lessless) && Right.Next &&
3195       Right.Previous->is(tok::string_literal) &&
3196       Right.Next->is(tok::string_literal))
3197     return true;
3198   if (Right.Previous->ClosesTemplateDeclaration &&
3199       Right.Previous->MatchingParen &&
3200       Right.Previous->MatchingParen->NestingLevel == 0 &&
3201       Style.AlwaysBreakTemplateDeclarations == FormatStyle::BTDS_Yes)
3202     return true;
3203   if (Right.is(TT_CtorInitializerComma) &&
3204       Style.BreakConstructorInitializers == FormatStyle::BCIS_BeforeComma &&
3205       !Style.ConstructorInitializerAllOnOneLineOrOnePerLine)
3206     return true;
3207   if (Right.is(TT_CtorInitializerColon) &&
3208       Style.BreakConstructorInitializers == FormatStyle::BCIS_BeforeComma &&
3209       !Style.ConstructorInitializerAllOnOneLineOrOnePerLine)
3210     return true;
3211   // Break only if we have multiple inheritance.
3212   if (Style.BreakInheritanceList == FormatStyle::BILS_BeforeComma &&
3213       Right.is(TT_InheritanceComma))
3214     return true;
3215   if (Right.is(tok::string_literal) && Right.TokenText.startswith("R\""))
3216     // Multiline raw string literals are special wrt. line breaks. The author
3217     // has made a deliberate choice and might have aligned the contents of the
3218     // string literal accordingly. Thus, we try keep existing line breaks.
3219     return Right.IsMultiline && Right.NewlinesBefore > 0;
3220   if ((Right.Previous->is(tok::l_brace) ||
3221        (Right.Previous->is(tok::less) && Right.Previous->Previous &&
3222         Right.Previous->Previous->is(tok::equal))) &&
3223       Right.NestingLevel == 1 && Style.Language == FormatStyle::LK_Proto) {
3224     // Don't put enums or option definitions onto single lines in protocol
3225     // buffers.
3226     return true;
3227   }
3228   if (Right.is(TT_InlineASMBrace))
3229     return Right.HasUnescapedNewline;
3230   if (isAllmanBrace(Left) || isAllmanBrace(Right))
3231     return (Line.startsWith(tok::kw_enum) && Style.BraceWrapping.AfterEnum) ||
3232            (Line.startsWith(tok::kw_typedef, tok::kw_enum) &&
3233             Style.BraceWrapping.AfterEnum) ||
3234            (Line.startsWith(tok::kw_class) && Style.BraceWrapping.AfterClass) ||
3235            (Line.startsWith(tok::kw_struct) && Style.BraceWrapping.AfterStruct);
3236   if (Left.is(TT_ObjCBlockLBrace) &&
3237       Style.AllowShortBlocksOnASingleLine == FormatStyle::SBS_Never)
3238     return true;
3239
3240   if (Left.is(TT_LambdaLBrace)) {
3241     if (Left.MatchingParen && Left.MatchingParen->Next &&
3242         Left.MatchingParen->Next->isOneOf(tok::comma, tok::r_paren) &&
3243         Style.AllowShortLambdasOnASingleLine == FormatStyle::SLS_Inline)
3244       return false;
3245
3246     if (Style.AllowShortLambdasOnASingleLine == FormatStyle::SLS_None ||
3247         Style.AllowShortLambdasOnASingleLine == FormatStyle::SLS_Inline ||
3248         (!Left.Children.empty() &&
3249          Style.AllowShortLambdasOnASingleLine == FormatStyle::SLS_Empty))
3250       return true;
3251   }
3252
3253   // Put multiple C# attributes on a new line.
3254   if (Style.isCSharp() &&
3255       ((Left.is(TT_AttributeSquare) && Left.is(tok::r_square)) ||
3256        (Left.is(tok::r_square) && Right.is(TT_AttributeSquare) &&
3257         Right.is(tok::l_square))))
3258     return true;
3259
3260   // Put multiple Java annotation on a new line.
3261   if ((Style.Language == FormatStyle::LK_Java ||
3262        Style.Language == FormatStyle::LK_JavaScript) &&
3263       Left.is(TT_LeadingJavaAnnotation) &&
3264       Right.isNot(TT_LeadingJavaAnnotation) && Right.isNot(tok::l_paren) &&
3265       (Line.Last->is(tok::l_brace) || Style.BreakAfterJavaFieldAnnotations))
3266     return true;
3267
3268   if (Right.is(TT_ProtoExtensionLSquare))
3269     return true;
3270
3271   // In text proto instances if a submessage contains at least 2 entries and at
3272   // least one of them is a submessage, like A { ... B { ... } ... },
3273   // put all of the entries of A on separate lines by forcing the selector of
3274   // the submessage B to be put on a newline.
3275   //
3276   // Example: these can stay on one line:
3277   // a { scalar_1: 1 scalar_2: 2 }
3278   // a { b { key: value } }
3279   //
3280   // and these entries need to be on a new line even if putting them all in one
3281   // line is under the column limit:
3282   // a {
3283   //   scalar: 1
3284   //   b { key: value }
3285   // }
3286   //
3287   // We enforce this by breaking before a submessage field that has previous
3288   // siblings, *and* breaking before a field that follows a submessage field.
3289   //
3290   // Be careful to exclude the case  [proto.ext] { ... } since the `]` is
3291   // the TT_SelectorName there, but we don't want to break inside the brackets.
3292   //
3293   // Another edge case is @submessage { key: value }, which is a common
3294   // substitution placeholder. In this case we want to keep `@` and `submessage`
3295   // together.
3296   //
3297   // We ensure elsewhere that extensions are always on their own line.
3298   if ((Style.Language == FormatStyle::LK_Proto ||
3299        Style.Language == FormatStyle::LK_TextProto) &&
3300       Right.is(TT_SelectorName) && !Right.is(tok::r_square) && Right.Next) {
3301     // Keep `@submessage` together in:
3302     // @submessage { key: value }
3303     if (Right.Previous && Right.Previous->is(tok::at))
3304       return false;
3305     // Look for the scope opener after selector in cases like:
3306     // selector { ...
3307     // selector: { ...
3308     // selector: @base { ...
3309     FormatToken *LBrace = Right.Next;
3310     if (LBrace && LBrace->is(tok::colon)) {
3311       LBrace = LBrace->Next;
3312       if (LBrace && LBrace->is(tok::at)) {
3313         LBrace = LBrace->Next;
3314         if (LBrace)
3315           LBrace = LBrace->Next;
3316       }
3317     }
3318     if (LBrace &&
3319         // The scope opener is one of {, [, <:
3320         // selector { ... }
3321         // selector [ ... ]
3322         // selector < ... >
3323         //
3324         // In case of selector { ... }, the l_brace is TT_DictLiteral.
3325         // In case of an empty selector {}, the l_brace is not TT_DictLiteral,
3326         // so we check for immediately following r_brace.
3327         ((LBrace->is(tok::l_brace) &&
3328           (LBrace->is(TT_DictLiteral) ||
3329            (LBrace->Next && LBrace->Next->is(tok::r_brace)))) ||
3330          LBrace->is(TT_ArrayInitializerLSquare) || LBrace->is(tok::less))) {
3331       // If Left.ParameterCount is 0, then this submessage entry is not the
3332       // first in its parent submessage, and we want to break before this entry.
3333       // If Left.ParameterCount is greater than 0, then its parent submessage
3334       // might contain 1 or more entries and we want to break before this entry
3335       // if it contains at least 2 entries. We deal with this case later by
3336       // detecting and breaking before the next entry in the parent submessage.
3337       if (Left.ParameterCount == 0)
3338         return true;
3339       // However, if this submessage is the first entry in its parent
3340       // submessage, Left.ParameterCount might be 1 in some cases.
3341       // We deal with this case later by detecting an entry
3342       // following a closing paren of this submessage.
3343     }
3344
3345     // If this is an entry immediately following a submessage, it will be
3346     // preceded by a closing paren of that submessage, like in:
3347     //     left---.  .---right
3348     //            v  v
3349     // sub: { ... } key: value
3350     // If there was a comment between `}` an `key` above, then `key` would be
3351     // put on a new line anyways.
3352     if (Left.isOneOf(tok::r_brace, tok::greater, tok::r_square))
3353       return true;
3354   }
3355
3356   // Deal with lambda arguments in C++ - we want consistent line breaks whether
3357   // they happen to be at arg0, arg1 or argN. The selection is a bit nuanced
3358   // as aggressive line breaks are placed when the lambda is not the last arg.
3359   if ((Style.Language == FormatStyle::LK_Cpp ||
3360        Style.Language == FormatStyle::LK_ObjC) &&
3361       Left.is(tok::l_paren) && Left.BlockParameterCount > 0 &&
3362       !Right.isOneOf(tok::l_paren, TT_LambdaLSquare)) {
3363     // Multiple lambdas in the same function call force line breaks.
3364     if (Left.BlockParameterCount > 1)
3365       return true;
3366
3367     // A lambda followed by another arg forces a line break.
3368     if (!Left.Role)
3369       return false;
3370     auto Comma = Left.Role->lastComma();
3371     if (!Comma)
3372       return false;
3373     auto Next = Comma->getNextNonComment();
3374     if (!Next)
3375       return false;
3376     if (!Next->isOneOf(TT_LambdaLSquare, tok::l_brace, tok::caret))
3377       return true;
3378   }
3379
3380   return false;
3381 }
3382
3383 bool TokenAnnotator::canBreakBefore(const AnnotatedLine &Line,
3384                                     const FormatToken &Right) {
3385   const FormatToken &Left = *Right.Previous;
3386
3387   // Language-specific stuff.
3388   if (Style.Language == FormatStyle::LK_Java) {
3389     if (Left.isOneOf(Keywords.kw_throws, Keywords.kw_extends,
3390                      Keywords.kw_implements))
3391       return false;
3392     if (Right.isOneOf(Keywords.kw_throws, Keywords.kw_extends,
3393                       Keywords.kw_implements))
3394       return true;
3395   } else if (Style.Language == FormatStyle::LK_JavaScript) {
3396     const FormatToken *NonComment = Right.getPreviousNonComment();
3397     if (NonComment &&
3398         NonComment->isOneOf(
3399             tok::kw_return, Keywords.kw_yield, tok::kw_continue, tok::kw_break,
3400             tok::kw_throw, Keywords.kw_interface, Keywords.kw_type,
3401             tok::kw_static, tok::kw_public, tok::kw_private, tok::kw_protected,
3402             Keywords.kw_readonly, Keywords.kw_abstract, Keywords.kw_get,
3403             Keywords.kw_set, Keywords.kw_async, Keywords.kw_await))
3404       return false; // Otherwise automatic semicolon insertion would trigger.
3405     if (Right.NestingLevel == 0 &&
3406         (Left.Tok.getIdentifierInfo() ||
3407          Left.isOneOf(tok::r_square, tok::r_paren)) &&
3408         Right.isOneOf(tok::l_square, tok::l_paren))
3409       return false; // Otherwise automatic semicolon insertion would trigger.
3410     if (Left.is(TT_JsFatArrow) && Right.is(tok::l_brace))
3411       return false;
3412     if (Left.is(TT_JsTypeColon))
3413       return true;
3414     // Don't wrap between ":" and "!" of a strict prop init ("field!: type;").
3415     if (Left.is(tok::exclaim) && Right.is(tok::colon))
3416       return false;
3417     // Look for is type annotations like:
3418     // function f(): a is B { ... }
3419     // Do not break before is in these cases.
3420     if (Right.is(Keywords.kw_is)) {
3421       const FormatToken *Next = Right.getNextNonComment();
3422       // If `is` is followed by a colon, it's likely that it's a dict key, so
3423       // ignore it for this check.
3424       // For example this is common in Polymer:
3425       // Polymer({
3426       //   is: 'name',
3427       //   ...
3428       // });
3429       if (!Next || !Next->is(tok::colon))
3430         return false;
3431     }
3432     if (Left.is(Keywords.kw_in))
3433       return Style.BreakBeforeBinaryOperators == FormatStyle::BOS_None;
3434     if (Right.is(Keywords.kw_in))
3435       return Style.BreakBeforeBinaryOperators != FormatStyle::BOS_None;
3436     if (Right.is(Keywords.kw_as))
3437       return false; // must not break before as in 'x as type' casts
3438     if (Right.isOneOf(Keywords.kw_extends, Keywords.kw_infer)) {
3439       // extends and infer can appear as keywords in conditional types:
3440       //   https://www.typescriptlang.org/docs/handbook/release-notes/typescript-2-8.html#conditional-types
3441       // do not break before them, as the expressions are subject to ASI.
3442       return false;
3443     }
3444     if (Left.is(Keywords.kw_as))
3445       return true;
3446     if (Left.is(TT_JsNonNullAssertion))
3447       return true;
3448     if (Left.is(Keywords.kw_declare) &&
3449         Right.isOneOf(Keywords.kw_module, tok::kw_namespace,
3450                       Keywords.kw_function, tok::kw_class, tok::kw_enum,
3451                       Keywords.kw_interface, Keywords.kw_type, Keywords.kw_var,
3452                       Keywords.kw_let, tok::kw_const))
3453       // See grammar for 'declare' statements at:
3454       // https://github.com/Microsoft/TypeScript/blob/master/doc/spec.md#A.10
3455       return false;
3456     if (Left.isOneOf(Keywords.kw_module, tok::kw_namespace) &&
3457         Right.isOneOf(tok::identifier, tok::string_literal))
3458       return false; // must not break in "module foo { ...}"
3459     if (Right.is(TT_TemplateString) && Right.closesScope())
3460       return false;
3461     // Don't split tagged template literal so there is a break between the tag
3462     // identifier and template string.
3463     if (Left.is(tok::identifier) && Right.is(TT_TemplateString)) {
3464       return false;
3465     }
3466     if (Left.is(TT_TemplateString) && Left.opensScope())
3467       return true;
3468   }
3469
3470   if (Left.is(tok::at))
3471     return false;
3472   if (Left.Tok.getObjCKeywordID() == tok::objc_interface)
3473     return false;
3474   if (Left.isOneOf(TT_JavaAnnotation, TT_LeadingJavaAnnotation))
3475     return !Right.is(tok::l_paren);
3476   if (Right.is(TT_PointerOrReference))
3477     return Line.IsMultiVariableDeclStmt ||
3478            (Style.PointerAlignment == FormatStyle::PAS_Right &&
3479             (!Right.Next || Right.Next->isNot(TT_FunctionDeclarationName)));
3480   if (Right.isOneOf(TT_StartOfName, TT_FunctionDeclarationName) ||
3481       Right.is(tok::kw_operator))
3482     return true;
3483   if (Left.is(TT_PointerOrReference))
3484     return false;
3485   if (Right.isTrailingComment())
3486     // We rely on MustBreakBefore being set correctly here as we should not
3487     // change the "binding" behavior of a comment.
3488     // The first comment in a braced lists is always interpreted as belonging to
3489     // the first list element. Otherwise, it should be placed outside of the
3490     // list.
3491     return Left.BlockKind == BK_BracedInit ||
3492            (Left.is(TT_CtorInitializerColon) &&
3493             Style.BreakConstructorInitializers == FormatStyle::BCIS_AfterColon);
3494   if (Left.is(tok::question) && Right.is(tok::colon))
3495     return false;
3496   if (Right.is(TT_ConditionalExpr) || Right.is(tok::question))
3497     return Style.BreakBeforeTernaryOperators;
3498   if (Left.is(TT_ConditionalExpr) || Left.is(tok::question))
3499     return !Style.BreakBeforeTernaryOperators;
3500   if (Left.is(TT_InheritanceColon))
3501     return Style.BreakInheritanceList == FormatStyle::BILS_AfterColon;
3502   if (Right.is(TT_InheritanceColon))
3503     return Style.BreakInheritanceList != FormatStyle::BILS_AfterColon;
3504   if (Right.is(TT_ObjCMethodExpr) && !Right.is(tok::r_square) &&
3505       Left.isNot(TT_SelectorName))
3506     return true;
3507
3508   if (Right.is(tok::colon) &&
3509       !Right.isOneOf(TT_CtorInitializerColon, TT_InlineASMColon))
3510     return false;
3511   if (Left.is(tok::colon) && Left.isOneOf(TT_DictLiteral, TT_ObjCMethodExpr)) {
3512     if (Style.Language == FormatStyle::LK_Proto ||
3513         Style.Language == FormatStyle::LK_TextProto) {
3514       if (!Style.AlwaysBreakBeforeMultilineStrings && Right.isStringLiteral())
3515         return false;
3516       // Prevent cases like:
3517       //
3518       // submessage:
3519       //     { key: valueeeeeeeeeeee }
3520       //
3521       // when the snippet does not fit into one line.
3522       // Prefer:
3523       //
3524       // submessage: {
3525       //   key: valueeeeeeeeeeee
3526       // }
3527       //
3528       // instead, even if it is longer by one line.
3529       //
3530       // Note that this allows allows the "{" to go over the column limit
3531       // when the column limit is just between ":" and "{", but that does
3532       // not happen too often and alternative formattings in this case are
3533       // not much better.
3534       //
3535       // The code covers the cases:
3536       //
3537       // submessage: { ... }
3538       // submessage: < ... >
3539       // repeated: [ ... ]
3540       if (((Right.is(tok::l_brace) || Right.is(tok::less)) &&
3541            Right.is(TT_DictLiteral)) ||
3542           Right.is(TT_ArrayInitializerLSquare))
3543         return false;
3544     }
3545     return true;
3546   }
3547   if (Right.is(tok::r_square) && Right.MatchingParen &&
3548       Right.MatchingParen->is(TT_ProtoExtensionLSquare))
3549     return false;
3550   if (Right.is(TT_SelectorName) || (Right.is(tok::identifier) && Right.Next &&
3551                                     Right.Next->is(TT_ObjCMethodExpr)))
3552     return Left.isNot(tok::period); // FIXME: Properly parse ObjC calls.
3553   if (Left.is(tok::r_paren) && Line.Type == LT_ObjCProperty)
3554     return true;
3555   if (Left.ClosesTemplateDeclaration || Left.is(TT_FunctionAnnotationRParen))
3556     return true;
3557   if (Right.isOneOf(TT_RangeBasedForLoopColon, TT_OverloadedOperatorLParen,
3558                     TT_OverloadedOperator))
3559     return false;
3560   if (Left.is(TT_RangeBasedForLoopColon))
3561     return true;
3562   if (Right.is(TT_RangeBasedForLoopColon))
3563     return false;
3564   if (Left.is(TT_TemplateCloser) && Right.is(TT_TemplateOpener))
3565     return true;
3566   if (Left.isOneOf(TT_TemplateCloser, TT_UnaryOperator) ||
3567       Left.is(tok::kw_operator))
3568     return false;
3569   if (Left.is(tok::equal) && !Right.isOneOf(tok::kw_default, tok::kw_delete) &&
3570       Line.Type == LT_VirtualFunctionDecl && Left.NestingLevel == 0)
3571     return false;
3572   if (Left.is(tok::equal) && Right.is(tok::l_brace) &&
3573       !Style.Cpp11BracedListStyle)
3574     return false;
3575   if (Left.is(tok::l_paren) && Left.is(TT_AttributeParen))
3576     return false;
3577   if (Left.is(tok::l_paren) && Left.Previous &&
3578       (Left.Previous->isOneOf(TT_BinaryOperator, TT_CastRParen)))
3579     return false;
3580   if (Right.is(TT_ImplicitStringLiteral))
3581     return false;
3582
3583   if (Right.is(tok::r_paren) || Right.is(TT_TemplateCloser))
3584     return false;
3585   if (Right.is(tok::r_square) && Right.MatchingParen &&
3586       Right.MatchingParen->is(TT_LambdaLSquare))
3587     return false;
3588
3589   // We only break before r_brace if there was a corresponding break before
3590   // the l_brace, which is tracked by BreakBeforeClosingBrace.
3591   if (Right.is(tok::r_brace))
3592     return Right.MatchingParen && Right.MatchingParen->BlockKind == BK_Block;
3593
3594   // Allow breaking after a trailing annotation, e.g. after a method
3595   // declaration.
3596   if (Left.is(TT_TrailingAnnotation))
3597     return !Right.isOneOf(tok::l_brace, tok::semi, tok::equal, tok::l_paren,
3598                           tok::less, tok::coloncolon);
3599
3600   if (Right.is(tok::kw___attribute) ||
3601       (Right.is(tok::l_square) && Right.is(TT_AttributeSquare)))
3602     return true;
3603
3604   if (Left.is(tok::identifier) && Right.is(tok::string_literal))
3605     return true;
3606
3607   if (Right.is(tok::identifier) && Right.Next && Right.Next->is(TT_DictLiteral))
3608     return true;
3609
3610   if (Left.is(TT_CtorInitializerColon))
3611     return Style.BreakConstructorInitializers == FormatStyle::BCIS_AfterColon;
3612   if (Right.is(TT_CtorInitializerColon))
3613     return Style.BreakConstructorInitializers != FormatStyle::BCIS_AfterColon;
3614   if (Left.is(TT_CtorInitializerComma) &&
3615       Style.BreakConstructorInitializers == FormatStyle::BCIS_BeforeComma)
3616     return false;
3617   if (Right.is(TT_CtorInitializerComma) &&
3618       Style.BreakConstructorInitializers == FormatStyle::BCIS_BeforeComma)
3619     return true;
3620   if (Left.is(TT_InheritanceComma) &&
3621       Style.BreakInheritanceList == FormatStyle::BILS_BeforeComma)
3622     return false;
3623   if (Right.is(TT_InheritanceComma) &&
3624       Style.BreakInheritanceList == FormatStyle::BILS_BeforeComma)
3625     return true;
3626   if ((Left.is(tok::greater) && Right.is(tok::greater)) ||
3627       (Left.is(tok::less) && Right.is(tok::less)))
3628     return false;
3629   if (Right.is(TT_BinaryOperator) &&
3630       Style.BreakBeforeBinaryOperators != FormatStyle::BOS_None &&
3631       (Style.BreakBeforeBinaryOperators == FormatStyle::BOS_All ||
3632        Right.getPrecedence() != prec::Assignment))
3633     return true;
3634   if (Left.is(TT_ArrayInitializerLSquare))
3635     return true;
3636   if (Right.is(tok::kw_typename) && Left.isNot(tok::kw_const))
3637     return true;
3638   if ((Left.isBinaryOperator() || Left.is(TT_BinaryOperator)) &&
3639       !Left.isOneOf(tok::arrowstar, tok::lessless) &&
3640       Style.BreakBeforeBinaryOperators != FormatStyle::BOS_All &&
3641       (Style.BreakBeforeBinaryOperators == FormatStyle::BOS_None ||
3642        Left.getPrecedence() == prec::Assignment))
3643     return true;
3644   if ((Left.is(TT_AttributeSquare) && Right.is(tok::l_square)) ||
3645       (Left.is(tok::r_square) && Right.is(TT_AttributeSquare)))
3646     return false;
3647   return Left.isOneOf(tok::comma, tok::coloncolon, tok::semi, tok::l_brace,
3648                       tok::kw_class, tok::kw_struct, tok::comment) ||
3649          Right.isMemberAccess() ||
3650          Right.isOneOf(TT_TrailingReturnArrow, TT_LambdaArrow, tok::lessless,
3651                        tok::colon, tok::l_square, tok::at) ||
3652          (Left.is(tok::r_paren) &&
3653           Right.isOneOf(tok::identifier, tok::kw_const)) ||
3654          (Left.is(tok::l_paren) && !Right.is(tok::r_paren)) ||
3655          (Left.is(TT_TemplateOpener) && !Right.is(TT_TemplateCloser));
3656 }
3657
3658 void TokenAnnotator::printDebugInfo(const AnnotatedLine &Line) {
3659   llvm::errs() << "AnnotatedTokens(L=" << Line.Level << "):\n";
3660   const FormatToken *Tok = Line.First;
3661   while (Tok) {
3662     llvm::errs() << " M=" << Tok->MustBreakBefore
3663                  << " C=" << Tok->CanBreakBefore
3664                  << " T=" << getTokenTypeName(Tok->Type)
3665                  << " S=" << Tok->SpacesRequiredBefore
3666                  << " B=" << Tok->BlockParameterCount
3667                  << " BK=" << Tok->BlockKind << " P=" << Tok->SplitPenalty
3668                  << " Name=" << Tok->Tok.getName() << " L=" << Tok->TotalLength
3669                  << " PPK=" << Tok->PackingKind << " FakeLParens=";
3670     for (unsigned i = 0, e = Tok->FakeLParens.size(); i != e; ++i)
3671       llvm::errs() << Tok->FakeLParens[i] << "/";
3672     llvm::errs() << " FakeRParens=" << Tok->FakeRParens;
3673     llvm::errs() << " II=" << Tok->Tok.getIdentifierInfo();
3674     llvm::errs() << " Text='" << Tok->TokenText << "'\n";
3675     if (!Tok->Next)
3676       assert(Tok == Line.Last);
3677     Tok = Tok->Next;
3678   }
3679   llvm::errs() << "----\n";
3680 }
3681
3682 } // namespace format
3683 } // namespace clang