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