MFC 261991:

Upgrade our copy of llvm/clang to 3.4 release.  This version supports
all of the features in the current working draft of the upcoming C++
standard, provisionally named C++1y.

The code generator's performance is greatly increased, and the loop
auto-vectorizer is now enabled at -Os and -O2 in addition to -O3.  The
PowerPC backend has made several major improvements to code generation
quality and compile time, and the X86, SPARC, ARM32, Aarch64 and SystemZ
backends have all seen major feature work.

Release notes for llvm and clang can be found here:
<http://llvm.org/releases/3.4/docs/ReleaseNotes.html>
<http://llvm.org/releases/3.4/tools/clang/docs/ReleaseNotes.html>

MFC 262121 (by emaste):

Update lldb for clang/llvm 3.4 import

This commit largely restores the lldb source to the upstream r196259
snapshot with the addition of threaded inferior support and a few bug
fixes.

Specific upstream lldb revisions restored include:
   SVN      git
  181387  779e6ac
  181703  7bef4e2
  182099  b31044e
  182650  f2dcf35
  182683  0d91b80
  183862  15c1774
  183929  99447a6
  184177  0b2934b
  184948  4dc3761
  184954  007e7bc
  186990  eebd175

Sponsored by:	DARPA, AFRL

MFC 262186 (by emaste):

Fix mismerge in r262121

A break statement was lost in the merge.  The error had no functional
impact, but restore it to reduce the diff against upstream.

MFC 262303:

Pull in r197521 from upstream clang trunk (by rdivacky):

  Use the integrated assembler by default on FreeBSD/ppc and ppc64.

Requested by:	jhibbits

MFC 262611:

Pull in r196874 from upstream llvm trunk:

  Fix a crash that occurs when PWD is invalid.

  MCJIT needs to be able to run in hostile environments, even when PWD
  is invalid. There's no need to crash MCJIT in this case.

  The obvious fix is to simply leave MCContext's CompilationDir empty
  when PWD can't be determined. This way, MCJIT clients,
  and other clients that link with LLVM don't need a valid working directory.

  If we do want to guarantee valid CompilationDir, that should be done
  only for clients of getCompilationDir(). This is as simple as checking
  for an empty string.

  The only current use of getCompilationDir is EmitGenDwarfInfo, which
  won't conceivably run with an invalid working dir. However, in the
  purely hypothetically and untestable case that this happens, the
  AT_comp_dir will be omitted from the compilation_unit DIE.

This should help fix assertions occurring with ports-mgmt/tinderbox,
when it is using jails, and sometimes invalidates clang's current
working directory.

Reported by:	decke

MFC 262809:

Pull in r203007 from upstream clang trunk:

  Don't produce an alias between destructors with different calling conventions.

  Fixes pr19007.

(Please note that is an LLVM PR identifier, not a FreeBSD one.)

This should fix Firefox and/or libxul crashes (due to problems with
regparm/stdcall calling conventions) on i386.

Reported by:	multiple users on freebsd-current
PR:		bin/187103

MFC 263048:

Repair recognition of "CC" as an alias for the C++ compiler, since it
was silently broken by upstream for a Windows-specific use-case.

Apparently some versions of CMake still rely on this archaic feature...

Reported by:	rakuco

MFC 263049:

Garbage collect the old way of adding the libstdc++ include directories
in clang's InitHeaderSearch.cpp.  This has been superseded by David
Chisnall's commit in r255321.

Moreover, if libc++ is used, the libstdc++ include directories should
not be in the search path at all.  These directories are now only used
if you pass -stdlib=libstdc++.

1 files changed, 711 insertions, 385 deletions

diff --git a/contrib/llvm/tools/clang/lib/Format/TokenAnnotator.cpp b/contrib/llvm/tools/clang/lib/Format/TokenAnnotator.cpp
index 17abb01..074e1d7 100644
--- a/contrib/llvm/tools/clang/lib/Format/TokenAnnotator.cpp
+++ b/contrib/llvm/tools/clang/lib/Format/TokenAnnotator.cpp
@@ -15,61 +15,12 @@
 
 #include "TokenAnnotator.h"
 #include "clang/Basic/SourceManager.h"
-#include "clang/Lex/Lexer.h"
 #include "llvm/Support/Debug.h"
 
 namespace clang {
 namespace format {
 
-bool AnnotatedToken::isUnaryOperator() const {
-  switch (FormatTok.Tok.getKind()) {
-  case tok::plus:
-  case tok::plusplus:
-  case tok::minus:
-  case tok::minusminus:
-  case tok::exclaim:
-  case tok::tilde:
-  case tok::kw_sizeof:
-  case tok::kw_alignof:
-    return true;
-  default:
-    return false;
-  }
-}
-
-bool AnnotatedToken::isBinaryOperator() const {
-  // Comma is a binary operator, but does not behave as such wrt. formatting.
-  return getPrecedence(*this) > prec::Comma;
-}
-
-bool AnnotatedToken::isTrailingComment() const {
-  return is(tok::comment) &&
-         (Children.empty() || Children[0].FormatTok.NewlinesBefore > 0);
-}
-
-AnnotatedToken *AnnotatedToken::getPreviousNoneComment() const {
-  AnnotatedToken *Tok = Parent;
-  while (Tok != NULL && Tok->is(tok::comment))
-    Tok = Tok->Parent;
-  return Tok;
-}
-
-const AnnotatedToken *AnnotatedToken::getNextNoneComment() const {
-  const AnnotatedToken *Tok = Children.empty() ? NULL : &Children[0];
-  while (Tok != NULL && Tok->is(tok::comment))
-    Tok = Tok->Children.empty() ? NULL : &Tok->Children[0];
-  return Tok;
-}
-
-bool AnnotatedToken::closesScope() const {
-  return isOneOf(tok::r_paren, tok::r_brace, tok::r_square) ||
-         Type == TT_TemplateCloser;
-}
-
-bool AnnotatedToken::opensScope() const {
-  return isOneOf(tok::l_paren, tok::l_brace, tok::l_square) ||
-         Type == TT_TemplateOpener;
-}
+namespace {
 
 /// \brief A parser that gathers additional information about tokens.
 ///
@@ -78,11 +29,11 @@ bool AnnotatedToken::opensScope() const {
 /// into template parameter lists.
 class AnnotatingParser {
 public:
-  AnnotatingParser(SourceManager &SourceMgr, Lexer &Lex, AnnotatedLine &Line,
+  AnnotatingParser(const FormatStyle &Style, AnnotatedLine &Line,
                    IdentifierInfo &Ident_in)
-      : SourceMgr(SourceMgr), Lex(Lex), Line(Line), CurrentToken(&Line.First),
-        KeywordVirtualFound(false), NameFound(false), Ident_in(Ident_in) {
-    Contexts.push_back(Context(tok::unknown, 1, /*IsExpression=*/ false));
+      : Style(Style), Line(Line), CurrentToken(Line.First),
+        KeywordVirtualFound(false), AutoFound(false), Ident_in(Ident_in) {
+    Contexts.push_back(Context(tok::unknown, 1, /*IsExpression=*/false));
   }
 
 private:
@@ -90,7 +41,7 @@ private:
     if (CurrentToken == NULL)
       return false;
     ScopedContextCreator ContextCreator(*this, tok::less, 10);
-    AnnotatedToken *Left = CurrentToken->Parent;
+    FormatToken *Left = CurrentToken->Previous;
     Contexts.back().IsExpression = false;
     while (CurrentToken != NULL) {
       if (CurrentToken->is(tok::greater)) {
@@ -101,8 +52,18 @@ private:
         return true;
       }
       if (CurrentToken->isOneOf(tok::r_paren, tok::r_square, tok::r_brace,
-                                tok::pipepipe, tok::ampamp, tok::question,
-                                tok::colon))
+                                tok::question, tok::colon))
+        return false;
+      // If a && or || is found and interpreted as a binary operator, this set
+      // of angles is likely part of something like "a < b && c > d". If the
+      // angles are inside an expression, the ||/&& might also be a binary
+      // operator that was misinterpreted because we are parsing template
+      // parameters.
+      // FIXME: This is getting out of hand, write a decent parser.
+      if (CurrentToken->Previous->isOneOf(tok::pipepipe, tok::ampamp) &&
+          (CurrentToken->Previous->Type == TT_BinaryOperator ||
+           Contexts[Contexts.size() - 2].IsExpression) &&
+          Line.First->isNot(tok::kw_template))
         return false;
       updateParameterCount(Left, CurrentToken);
       if (!consumeToken())
@@ -121,42 +82,66 @@ private:
         Contexts.size() == 2 && Contexts[0].ColonIsForRangeExpr;
 
     bool StartsObjCMethodExpr = false;
-    AnnotatedToken *Left = CurrentToken->Parent;
+    FormatToken *Left = CurrentToken->Previous;
     if (CurrentToken->is(tok::caret)) {
       // ^( starts a block.
       Left->Type = TT_ObjCBlockLParen;
-    } else if (AnnotatedToken *MaybeSel = Left->Parent) {
+    } else if (FormatToken *MaybeSel = Left->Previous) {
       // @selector( starts a selector.
-      if (MaybeSel->isObjCAtKeyword(tok::objc_selector) && MaybeSel->Parent &&
-          MaybeSel->Parent->is(tok::at)) {
+      if (MaybeSel->isObjCAtKeyword(tok::objc_selector) && MaybeSel->Previous &&
+          MaybeSel->Previous->is(tok::at)) {
         StartsObjCMethodExpr = true;
       }
     }
 
+    if (Left->Previous && Left->Previous->isOneOf(tok::kw_static_assert,
+                                                  tok::kw_if, tok::kw_while)) {
+      // static_assert, if and while usually contain expressions.
+      Contexts.back().IsExpression = true;
+    } else if (Left->Previous && Left->Previous->is(tok::r_square) &&
+               Left->Previous->MatchingParen &&
+               Left->Previous->MatchingParen->Type == TT_LambdaLSquare) {
+      // This is a parameter list of a lambda expression.
+      Contexts.back().IsExpression = false;
+    }
+
     if (StartsObjCMethodExpr) {
       Contexts.back().ColonIsObjCMethodExpr = true;
       Left->Type = TT_ObjCMethodExpr;
     }
 
+    bool MightBeFunctionType = CurrentToken->is(tok::star);
+    bool HasMultipleLines = false;
+    bool HasMultipleParametersOnALine = false;
     while (CurrentToken != NULL) {
       // LookForDecls is set when "if (" has been seen. Check for
       // 'identifier' '*' 'identifier' followed by not '=' -- this
       // '*' has to be a binary operator but determineStarAmpUsage() will
       // categorize it as an unary operator, so set the right type here.
-      if (LookForDecls && !CurrentToken->Children.empty()) {
-        AnnotatedToken &Prev = *CurrentToken->Parent;
-        AnnotatedToken &Next = CurrentToken->Children[0];
-        if (Prev.Parent->is(tok::identifier) &&
-            Prev.isOneOf(tok::star, tok::amp, tok::ampamp) &&
-            CurrentToken->is(tok::identifier) && Next.isNot(tok::equal)) {
-          Prev.Type = TT_BinaryOperator;
-          LookForDecls = false;
+      if (LookForDecls && CurrentToken->Next) {
+        FormatToken *Prev = CurrentToken->getPreviousNonComment();
+        if (Prev) {
+          FormatToken *PrevPrev = Prev->getPreviousNonComment();
+          FormatToken *Next = CurrentToken->Next;
+          if (PrevPrev && PrevPrev->is(tok::identifier) &&
+              Prev->isOneOf(tok::star, tok::amp, tok::ampamp) &&
+              CurrentToken->is(tok::identifier) && Next->isNot(tok::equal)) {
+            Prev->Type = TT_BinaryOperator;
+            LookForDecls = false;
+          }
         }
       }
 
+      if (CurrentToken->Previous->Type == TT_PointerOrReference &&
+          CurrentToken->Previous->Previous->isOneOf(tok::l_paren,
+                                                    tok::coloncolon))
+        MightBeFunctionType = true;
       if (CurrentToken->is(tok::r_paren)) {
-        if (CurrentToken->Parent->closesScope())
-          CurrentToken->Parent->MatchingParen->NoMoreTokensOnLevel = true;
+        if (MightBeFunctionType && CurrentToken->Next &&
+            (CurrentToken->Next->is(tok::l_paren) ||
+             (CurrentToken->Next->is(tok::l_square) &&
+              !Contexts.back().IsExpression)))
+          Left->Type = TT_FunctionTypeLParen;
         Left->MatchingParen = CurrentToken;
         CurrentToken->MatchingParen = Left;
 
@@ -168,14 +153,27 @@ private:
           }
         }
 
+        if (!HasMultipleLines)
+          Left->PackingKind = PPK_Inconclusive;
+        else if (HasMultipleParametersOnALine)
+          Left->PackingKind = PPK_BinPacked;
+        else
+          Left->PackingKind = PPK_OnePerLine;
+
         next();
         return true;
       }
       if (CurrentToken->isOneOf(tok::r_square, tok::r_brace))
         return false;
       updateParameterCount(Left, CurrentToken);
+      if (CurrentToken->is(tok::comma) && CurrentToken->Next &&
+          !CurrentToken->Next->HasUnescapedNewline &&
+          !CurrentToken->Next->isTrailingComment())
+        HasMultipleParametersOnALine = true;
       if (!consumeToken())
         return false;
+      if (CurrentToken && CurrentToken->HasUnescapedNewline)
+        HasMultipleLines = true;
     }
     return false;
   }
@@ -184,34 +182,35 @@ private:
     if (!CurrentToken)
       return false;
 
-    // A '[' could be an index subscript (after an indentifier or after
+    // A '[' could be an index subscript (after an identifier or after
     // ')' or ']'), it could be the start of an Objective-C method
     // expression, or it could the the start of an Objective-C array literal.
-    AnnotatedToken *Left = CurrentToken->Parent;
-    AnnotatedToken *Parent = Left->getPreviousNoneComment();
+    FormatToken *Left = CurrentToken->Previous;
+    FormatToken *Parent = Left->getPreviousNonComment();
     bool StartsObjCMethodExpr =
-        Contexts.back().CanBeExpression &&
+        Contexts.back().CanBeExpression && Left->Type != TT_LambdaLSquare &&
         (!Parent || Parent->isOneOf(tok::colon, tok::l_square, tok::l_paren,
                                     tok::kw_return, tok::kw_throw) ||
          Parent->isUnaryOperator() || Parent->Type == TT_ObjCForIn ||
          Parent->Type == TT_CastRParen ||
-         getBinOpPrecedence(Parent->FormatTok.Tok.getKind(), true, true) >
-             prec::Unknown);
+         getBinOpPrecedence(Parent->Tok.getKind(), true, true) > prec::Unknown);
     ScopedContextCreator ContextCreator(*this, tok::l_square, 10);
     Contexts.back().IsExpression = true;
-    bool StartsObjCArrayLiteral = Parent && Parent->is(tok::at);
+    bool ColonFound = false;
 
     if (StartsObjCMethodExpr) {
       Contexts.back().ColonIsObjCMethodExpr = true;
       Left->Type = TT_ObjCMethodExpr;
-    } else if (StartsObjCArrayLiteral) {
-      Left->Type = TT_ObjCArrayLiteral;
+    } else if (Parent && Parent->is(tok::at)) {
+      Left->Type = TT_ArrayInitializerLSquare;
+    } else if (Left->Type == TT_Unknown) {
+      Left->Type = TT_ArraySubscriptLSquare;
     }
 
     while (CurrentToken != NULL) {
       if (CurrentToken->is(tok::r_square)) {
-        if (!CurrentToken->Children.empty() &&
-            CurrentToken->Children[0].is(tok::l_paren)) {
+        if (CurrentToken->Next && CurrentToken->Next->is(tok::l_paren) &&
+            Left->Type == TT_ObjCMethodExpr) {
           // An ObjC method call is rarely followed by an open parenthesis.
           // FIXME: Do we incorrectly label ":" with this?
           StartsObjCMethodExpr = false;
@@ -224,8 +223,6 @@ private:
           // binary operator.
           if (Parent != NULL && Parent->Type == TT_PointerOrReference)
             Parent->Type = TT_BinaryOperator;
-        } else if (StartsObjCArrayLiteral) {
-          CurrentToken->Type = TT_ObjCArrayLiteral;
         }
         Left->MatchingParen = CurrentToken;
         CurrentToken->MatchingParen = Left;
@@ -237,6 +234,12 @@ private:
       }
       if (CurrentToken->isOneOf(tok::r_paren, tok::r_brace))
         return false;
+      if (CurrentToken->is(tok::colon))
+        ColonFound = true;
+      if (CurrentToken->is(tok::comma) &&
+          (Left->Type == TT_ArraySubscriptLSquare ||
+           (Left->Type == TT_ObjCMethodExpr && !ColonFound)))
+        Left->Type = TT_ArrayInitializerLSquare;
       updateParameterCount(Left, CurrentToken);
       if (!consumeToken())
         return false;
@@ -246,8 +249,10 @@ private:
 
   bool parseBrace() {
     if (CurrentToken != NULL) {
+      FormatToken *Left = CurrentToken->Previous;
       ScopedContextCreator ContextCreator(*this, tok::l_brace, 1);
-      AnnotatedToken *Left = CurrentToken->Parent;
+      Contexts.back().ColonIsDictLiteral = true;
+
       while (CurrentToken != NULL) {
         if (CurrentToken->is(tok::r_brace)) {
           Left->MatchingParen = CurrentToken;
@@ -258,6 +263,8 @@ private:
         if (CurrentToken->isOneOf(tok::r_paren, tok::r_square))
           return false;
         updateParameterCount(Left, CurrentToken);
+        if (CurrentToken->is(tok::colon))
+          Left->Type = TT_DictLiteral;
         if (!consumeToken())
           return false;
       }
@@ -267,11 +274,15 @@ private:
     return true;
   }
 
-  void updateParameterCount(AnnotatedToken *Left, AnnotatedToken *Current) {
-    if (Current->is(tok::comma))
+  void updateParameterCount(FormatToken *Left, FormatToken *Current) {
+    if (Current->is(tok::comma)) {
       ++Left->ParameterCount;
-    else if (Left->ParameterCount == 0 && Current->isNot(tok::comment))
+      if (!Left->Role)
+        Left->Role.reset(new CommaSeparatedList(Style));
+      Left->Role->CommaFound(Current);
+    } else if (Left->ParameterCount == 0 && Current->isNot(tok::comment)) {
       Left->ParameterCount = 1;
+    }
   }
 
   bool parseConditional() {
@@ -294,40 +305,45 @@ private:
       if (!parseAngle())
         return false;
       if (CurrentToken != NULL)
-        CurrentToken->Parent->ClosesTemplateDeclaration = true;
+        CurrentToken->Previous->ClosesTemplateDeclaration = true;
       return true;
     }
     return false;
   }
 
   bool consumeToken() {
-    AnnotatedToken *Tok = CurrentToken;
+    FormatToken *Tok = CurrentToken;
     next();
-    switch (Tok->FormatTok.Tok.getKind()) {
+    switch (Tok->Tok.getKind()) {
     case tok::plus:
     case tok::minus:
-      if (Tok->Parent == NULL && Line.MustBeDeclaration)
+      if (Tok->Previous == NULL && Line.MustBeDeclaration)
         Tok->Type = TT_ObjCMethodSpecifier;
       break;
     case tok::colon:
-      if (Tok->Parent == NULL)
+      if (Tok->Previous == NULL)
         return false;
       // Colons from ?: are handled in parseConditional().
-      if (Tok->Parent->is(tok::r_paren) && Contexts.size() == 1) {
+      if (Tok->Previous->is(tok::r_paren) && Contexts.size() == 1) {
         Tok->Type = TT_CtorInitializerColon;
+      } else if (Contexts.back().ColonIsDictLiteral) {
+        Tok->Type = TT_DictLiteral;
       } else if (Contexts.back().ColonIsObjCMethodExpr ||
-                 Line.First.Type == TT_ObjCMethodSpecifier) {
+                 Line.First->Type == TT_ObjCMethodSpecifier) {
         Tok->Type = TT_ObjCMethodExpr;
-        Tok->Parent->Type = TT_ObjCSelectorName;
-        if (Tok->Parent->FormatTok.TokenLength >
-                Contexts.back().LongestObjCSelectorName)
-          Contexts.back().LongestObjCSelectorName =
-              Tok->Parent->FormatTok.TokenLength;
+        Tok->Previous->Type = TT_ObjCSelectorName;
+        if (Tok->Previous->ColumnWidth >
+            Contexts.back().LongestObjCSelectorName) {
+          Contexts.back().LongestObjCSelectorName = Tok->Previous->ColumnWidth;
+        }
         if (Contexts.back().FirstObjCSelectorName == NULL)
-          Contexts.back().FirstObjCSelectorName = Tok->Parent;
+          Contexts.back().FirstObjCSelectorName = Tok->Previous;
       } else if (Contexts.back().ColonIsForRangeExpr) {
         Tok->Type = TT_RangeBasedForLoopColon;
-      } else if (Contexts.size() == 1) {
+      } else if (CurrentToken != NULL &&
+                 CurrentToken->is(tok::numeric_constant)) {
+        Tok->Type = TT_BitFieldColon;
+      } else if (Contexts.size() == 1 && Line.First->isNot(tok::kw_enum)) {
         Tok->Type = TT_InheritanceColon;
       } else if (Contexts.back().ContextKind == tok::l_paren) {
         Tok->Type = TT_InlineASMColon;
@@ -337,7 +353,7 @@ private:
     case tok::kw_while:
       if (CurrentToken != NULL && CurrentToken->is(tok::l_paren)) {
         next();
-        if (!parseParens(/*LookForDecls=*/ true))
+        if (!parseParens(/*LookForDecls=*/true))
           return false;
       }
       break;
@@ -350,7 +366,8 @@ private:
     case tok::l_paren:
       if (!parseParens())
         return false;
-      if (Line.MustBeDeclaration && NameFound && !Contexts.back().IsExpression)
+      if (Line.MustBeDeclaration && Contexts.size() == 1 &&
+          !Contexts.back().IsExpression)
         Line.MightBeFunctionDecl = true;
       break;
     case tok::l_square:
@@ -362,7 +379,7 @@ private:
         return false;
       break;
     case tok::less:
-      if (parseAngle())
+      if (Tok->Previous && !Tok->Previous->Tok.isLiteral() && parseAngle())
         Tok->Type = TT_TemplateOpener;
       else {
         Tok->Type = TT_BinaryOperator;
@@ -375,20 +392,26 @@ private:
       return false;
     case tok::r_brace:
       // Lines can start with '}'.
-      if (Tok->Parent != NULL)
+      if (Tok->Previous != NULL)
         return false;
       break;
     case tok::greater:
       Tok->Type = TT_BinaryOperator;
       break;
     case tok::kw_operator:
-      while (CurrentToken && CurrentToken->isNot(tok::l_paren)) {
+      while (CurrentToken &&
+             !CurrentToken->isOneOf(tok::l_paren, tok::semi, tok::r_paren)) {
         if (CurrentToken->isOneOf(tok::star, tok::amp))
           CurrentToken->Type = TT_PointerOrReference;
         consumeToken();
+        if (CurrentToken && CurrentToken->Previous->Type == TT_BinaryOperator)
+          CurrentToken->Previous->Type = TT_OverloadedOperator;
       }
-      if (CurrentToken)
+      if (CurrentToken) {
         CurrentToken->Type = TT_OverloadedOperatorLParen;
+        if (CurrentToken->Previous->Type == TT_BinaryOperator)
+          CurrentToken->Previous->Type = TT_OverloadedOperator;
+      }
       break;
     case tok::question:
       parseConditional();
@@ -397,13 +420,15 @@ private:
       parseTemplateDeclaration();
       break;
     case tok::identifier:
-      if (Line.First.is(tok::kw_for) &&
-          Tok->FormatTok.Tok.getIdentifierInfo() == &Ident_in)
+      if (Line.First->is(tok::kw_for) &&
+          Tok->Tok.getIdentifierInfo() == &Ident_in)
         Tok->Type = TT_ObjCForIn;
       break;
     case tok::comma:
       if (Contexts.back().FirstStartOfName)
         Contexts.back().FirstStartOfName->PartOfMultiVariableDeclStmt = true;
+      if (Contexts.back().InCtorInitializer)
+        Tok->Type = TT_CtorInitializerComma;
       break;
     default:
       break;
@@ -416,8 +441,7 @@ private:
     if (CurrentToken != NULL && CurrentToken->is(tok::less)) {
       next();
       while (CurrentToken != NULL) {
-        if (CurrentToken->isNot(tok::comment) ||
-            !CurrentToken->Children.empty())
+        if (CurrentToken->isNot(tok::comment) || CurrentToken->Next)
           CurrentToken->Type = TT_ImplicitStringLiteral;
         next();
       }
@@ -447,11 +471,15 @@ private:
     next();
     if (CurrentToken == NULL)
       return;
+    if (CurrentToken->Tok.is(tok::numeric_constant)) {
+      CurrentToken->SpacesRequiredBefore = 1;
+      return;
+    }
     // Hashes in the middle of a line can lead to any strange token
     // sequence.
-    if (CurrentToken->FormatTok.Tok.getIdentifierInfo() == NULL)
+    if (CurrentToken->Tok.getIdentifierInfo() == NULL)
       return;
-    switch (CurrentToken->FormatTok.Tok.getIdentifierInfo()->getPPKeywordID()) {
+    switch (CurrentToken->Tok.getIdentifierInfo()->getPPKeywordID()) {
     case tok::pp_include:
     case tok::pp_import:
       parseIncludeDirective();
@@ -473,9 +501,6 @@ private:
 
 public:
   LineType parseLine() {
-    int PeriodsAndArrows = 0;
-    AnnotatedToken *LastPeriodOrArrow = NULL;
-    bool CanBeBuilderTypeStmt = true;
     if (CurrentToken->is(tok::hash)) {
       parsePreprocessorDirective();
       return LT_PreprocessorDirective;
@@ -483,27 +508,13 @@ public:
     while (CurrentToken != NULL) {
       if (CurrentToken->is(tok::kw_virtual))
         KeywordVirtualFound = true;
-      if (CurrentToken->isOneOf(tok::period, tok::arrow)) {
-        ++PeriodsAndArrows;
-        LastPeriodOrArrow = CurrentToken;
-      }
-      AnnotatedToken *TheToken = CurrentToken;
       if (!consumeToken())
         return LT_Invalid;
-      if (getPrecedence(*TheToken) > prec::Assignment &&
-          TheToken->Type == TT_BinaryOperator)
-        CanBeBuilderTypeStmt = false;
     }
     if (KeywordVirtualFound)
       return LT_VirtualFunctionDecl;
 
-    // Assume a builder-type call if there are 2 or more "." and "->".
-    if (PeriodsAndArrows >= 2 && CanBeBuilderTypeStmt) {
-      LastPeriodOrArrow->LastInChainOfCalls = true;
-      return LT_BuilderTypeCall;
-    }
-
-    if (Line.First.Type == TT_ObjCMethodSpecifier) {
+    if (Line.First->Type == TT_ObjCMethodSpecifier) {
       if (Contexts.back().FirstObjCSelectorName != NULL)
         Contexts.back().FirstObjCSelectorName->LongestObjCSelectorName =
             Contexts.back().LongestObjCSelectorName;
@@ -520,15 +531,20 @@ private:
       CurrentToken->BindingStrength = Contexts.back().BindingStrength;
     }
 
-    if (CurrentToken != NULL && !CurrentToken->Children.empty())
-      CurrentToken = &CurrentToken->Children[0];
-    else
-      CurrentToken = NULL;
-
-    // Reset token type in case we have already looked at it and then recovered
-    // from an error (e.g. failure to find the matching >).
     if (CurrentToken != NULL)
-      CurrentToken->Type = TT_Unknown;
+      CurrentToken = CurrentToken->Next;
+
+    if (CurrentToken != NULL) {
+      // Reset token type in case we have already looked at it and then
+      // recovered from an error (e.g. failure to find the matching >).
+      if (CurrentToken->Type != TT_LambdaLSquare &&
+          CurrentToken->Type != TT_ImplicitStringLiteral)
+        CurrentToken->Type = TT_Unknown;
+      if (CurrentToken->Role)
+        CurrentToken->Role.reset(NULL);
+      CurrentToken->FakeLParens.clear();
+      CurrentToken->FakeRParens = 0;
+    }
   }
 
   /// \brief A struct to hold information valid in a specific context, e.g.
@@ -538,19 +554,22 @@ private:
             bool IsExpression)
         : ContextKind(ContextKind), BindingStrength(BindingStrength),
           LongestObjCSelectorName(0), ColonIsForRangeExpr(false),
-          ColonIsObjCMethodExpr(false), FirstObjCSelectorName(NULL),
-          FirstStartOfName(NULL), IsExpression(IsExpression),
-          CanBeExpression(true) {}
+          ColonIsDictLiteral(false), ColonIsObjCMethodExpr(false),
+          FirstObjCSelectorName(NULL), FirstStartOfName(NULL),
+          IsExpression(IsExpression), CanBeExpression(true),
+          InCtorInitializer(false) {}
 
     tok::TokenKind ContextKind;
     unsigned BindingStrength;
     unsigned LongestObjCSelectorName;
     bool ColonIsForRangeExpr;
+    bool ColonIsDictLiteral;
     bool ColonIsObjCMethodExpr;
-    AnnotatedToken *FirstObjCSelectorName;
-    AnnotatedToken *FirstStartOfName;
+    FormatToken *FirstObjCSelectorName;
+    FormatToken *FirstStartOfName;
     bool IsExpression;
     bool CanBeExpression;
+    bool InCtorInitializer;
   };
 
   /// \brief Puts a new \c Context onto the stack \c Contexts for the lifetime
@@ -561,21 +580,22 @@ private:
     ScopedContextCreator(AnnotatingParser &P, tok::TokenKind ContextKind,
                          unsigned Increase)
         : P(P) {
-      P.Contexts.push_back(
-          Context(ContextKind, P.Contexts.back().BindingStrength + Increase,
-                  P.Contexts.back().IsExpression));
+      P.Contexts.push_back(Context(ContextKind,
+                                   P.Contexts.back().BindingStrength + Increase,
+                                   P.Contexts.back().IsExpression));
     }
 
     ~ScopedContextCreator() { P.Contexts.pop_back(); }
   };
 
-  void determineTokenType(AnnotatedToken &Current) {
-    if (getPrecedence(Current) == prec::Assignment &&
-        (!Current.Parent || Current.Parent->isNot(tok::kw_operator))) {
+  void determineTokenType(FormatToken &Current) {
+    if (Current.getPrecedence() == prec::Assignment &&
+        !Line.First->isOneOf(tok::kw_template, tok::kw_using) &&
+        (!Current.Previous || Current.Previous->isNot(tok::kw_operator))) {
       Contexts.back().IsExpression = true;
-      for (AnnotatedToken *Previous = Current.Parent;
-           Previous && Previous->isNot(tok::comma);
-           Previous = Previous->Parent) {
+      for (FormatToken *Previous = Current.Previous;
+           Previous && !Previous->isOneOf(tok::comma, tok::semi);
+           Previous = Previous->Previous) {
         if (Previous->is(tok::r_square))
           Previous = Previous->MatchingParen;
         if (Previous->Type == TT_BinaryOperator &&
@@ -585,69 +605,93 @@ private:
       }
     } else if (Current.isOneOf(tok::kw_return, tok::kw_throw) ||
                (Current.is(tok::l_paren) && !Line.MustBeDeclaration &&
-                (!Current.Parent || Current.Parent->isNot(tok::kw_for)))) {
+                !Line.InPPDirective &&
+                (!Current.Previous ||
+                 !Current.Previous->isOneOf(tok::kw_for, tok::kw_catch)))) {
       Contexts.back().IsExpression = true;
     } else if (Current.isOneOf(tok::r_paren, tok::greater, tok::comma)) {
-      for (AnnotatedToken *Previous = Current.Parent;
+      for (FormatToken *Previous = Current.Previous;
            Previous && Previous->isOneOf(tok::star, tok::amp);
-           Previous = Previous->Parent)
+           Previous = Previous->Previous)
         Previous->Type = TT_PointerOrReference;
-    } else if (Current.Parent &&
-               Current.Parent->Type == TT_CtorInitializerColon) {
+    } else if (Current.Previous &&
+               Current.Previous->Type == TT_CtorInitializerColon) {
       Contexts.back().IsExpression = true;
+      Contexts.back().InCtorInitializer = true;
     } else if (Current.is(tok::kw_new)) {
       Contexts.back().CanBeExpression = false;
-    } else if (Current.is(tok::semi)) {
+    } else if (Current.is(tok::semi) || Current.is(tok::exclaim)) {
       // This should be the condition or increment in a for-loop.
       Contexts.back().IsExpression = true;
     }
 
     if (Current.Type == TT_Unknown) {
-      if (Current.Parent && Current.is(tok::identifier) &&
-          ((Current.Parent->is(tok::identifier) &&
-            Current.Parent->FormatTok.Tok.getIdentifierInfo()
-                ->getPPKeywordID() == tok::pp_not_keyword) ||
-           isSimpleTypeSpecifier(*Current.Parent) ||
-           Current.Parent->Type == TT_PointerOrReference ||
-           Current.Parent->Type == TT_TemplateCloser)) {
+      // Line.MightBeFunctionDecl can only be true after the parentheses of a
+      // function declaration have been found. In this case, 'Current' is a
+      // trailing token of this declaration and thus cannot be a name.
+      if (isStartOfName(Current) && !Line.MightBeFunctionDecl) {
         Contexts.back().FirstStartOfName = &Current;
         Current.Type = TT_StartOfName;
-        NameFound = true;
+      } else if (Current.is(tok::kw_auto)) {
+        AutoFound = true;
+      } else if (Current.is(tok::arrow) && AutoFound &&
+                 Line.MustBeDeclaration) {
+        Current.Type = TT_TrailingReturnArrow;
       } else if (Current.isOneOf(tok::star, tok::amp, tok::ampamp)) {
         Current.Type =
-            determineStarAmpUsage(Current, Contexts.back().IsExpression);
+            determineStarAmpUsage(Current, Contexts.back().CanBeExpression &&
+                                               Contexts.back().IsExpression);
       } else if (Current.isOneOf(tok::minus, tok::plus, tok::caret)) {
         Current.Type = determinePlusMinusCaretUsage(Current);
       } else if (Current.isOneOf(tok::minusminus, tok::plusplus)) {
         Current.Type = determineIncrementUsage(Current);
       } else if (Current.is(tok::exclaim)) {
         Current.Type = TT_UnaryOperator;
-      } else if (Current.isBinaryOperator()) {
+      } else if (Current.isBinaryOperator() &&
+                 (!Current.Previous ||
+                  Current.Previous->isNot(tok::l_square))) {
         Current.Type = TT_BinaryOperator;
       } else if (Current.is(tok::comment)) {
-        std::string Data(Lexer::getSpelling(Current.FormatTok.Tok, SourceMgr,
-                                            Lex.getLangOpts()));
-        if (StringRef(Data).startswith("//"))
+        if (Current.TokenText.startswith("//"))
           Current.Type = TT_LineComment;
         else
           Current.Type = TT_BlockComment;
       } else if (Current.is(tok::r_paren)) {
-        bool ParensNotExpr = !Current.Parent ||
-                             Current.Parent->Type == TT_PointerOrReference ||
-                             Current.Parent->Type == TT_TemplateCloser;
+        FormatToken *LeftOfParens = NULL;
+        if (Current.MatchingParen)
+          LeftOfParens = Current.MatchingParen->getPreviousNonComment();
+        bool IsCast = false;
+        bool ParensAreEmpty = Current.Previous == Current.MatchingParen;
+        bool ParensAreType = !Current.Previous ||
+                             Current.Previous->Type == TT_PointerOrReference ||
+                             Current.Previous->Type == TT_TemplateCloser ||
+                             isSimpleTypeSpecifier(*Current.Previous);
         bool ParensCouldEndDecl =
-            !Current.Children.empty() &&
-            Current.Children[0].isOneOf(tok::equal, tok::semi, tok::l_brace);
+            Current.Next &&
+            Current.Next->isOneOf(tok::equal, tok::semi, tok::l_brace);
         bool IsSizeOfOrAlignOf =
-            Current.MatchingParen && Current.MatchingParen->Parent &&
-            Current.MatchingParen->Parent->isOneOf(tok::kw_sizeof,
-                                                   tok::kw_alignof);
-        if (ParensNotExpr && !ParensCouldEndDecl && !IsSizeOfOrAlignOf &&
-            Contexts.back().IsExpression)
-          // FIXME: We need to get smarter and understand more cases of casts.
+            LeftOfParens &&
+            LeftOfParens->isOneOf(tok::kw_sizeof, tok::kw_alignof);
+        if (ParensAreType && !ParensCouldEndDecl && !IsSizeOfOrAlignOf &&
+            (Contexts.back().IsExpression ||
+             (Current.Next && Current.Next->isBinaryOperator())))
+          IsCast = true;
+        if (Current.Next && Current.Next->isNot(tok::string_literal) &&
+            (Current.Next->Tok.isLiteral() ||
+             Current.Next->isOneOf(tok::kw_sizeof, tok::kw_alignof)))
+          IsCast = true;
+        // If there is an identifier after the (), it is likely a cast, unless
+        // there is also an identifier before the ().
+        if (LeftOfParens && (LeftOfParens->Tok.getIdentifierInfo() == NULL ||
+                             LeftOfParens->is(tok::kw_return)) &&
+            LeftOfParens->Type != TT_OverloadedOperator &&
+            LeftOfParens->Type != TT_TemplateCloser && Current.Next &&
+            Current.Next->is(tok::identifier))
+          IsCast = true;
+        if (IsCast && !ParensAreEmpty)
           Current.Type = TT_CastRParen;
-      } else if (Current.is(tok::at) && Current.Children.size()) {
-        switch (Current.Children[0].FormatTok.Tok.getObjCKeywordID()) {
+      } else if (Current.is(tok::at) && Current.Next) {
+        switch (Current.Next->Tok.getObjCKeywordID()) {
         case tok::objc_interface:
         case tok::objc_implementation:
         case tok::objc_protocol:
@@ -659,27 +703,63 @@ private:
         default:
           break;
         }
+      } else if (Current.is(tok::period)) {
+        FormatToken *PreviousNoComment = Current.getPreviousNonComment();
+        if (PreviousNoComment &&
+            PreviousNoComment->isOneOf(tok::comma, tok::l_brace))
+          Current.Type = TT_DesignatedInitializerPeriod;
       }
     }
   }
 
+  /// \brief Take a guess at whether \p Tok starts a name of a function or
+  /// variable declaration.
+  ///
+  /// This is a heuristic based on whether \p Tok is an identifier following
+  /// something that is likely a type.
+  bool isStartOfName(const FormatToken &Tok) {
+    if (Tok.isNot(tok::identifier) || Tok.Previous == NULL)
+      return false;
+
+    // Skip "const" as it does not have an influence on whether this is a name.
+    FormatToken *PreviousNotConst = Tok.Previous;
+    while (PreviousNotConst != NULL && PreviousNotConst->is(tok::kw_const))
+      PreviousNotConst = PreviousNotConst->Previous;
+
+    if (PreviousNotConst == NULL)
+      return false;
+
+    bool IsPPKeyword = PreviousNotConst->is(tok::identifier) &&
+                       PreviousNotConst->Previous &&
+                       PreviousNotConst->Previous->is(tok::hash);
+
+    if (PreviousNotConst->Type == TT_TemplateCloser)
+      return PreviousNotConst && PreviousNotConst->MatchingParen &&
+             PreviousNotConst->MatchingParen->Previous &&
+             PreviousNotConst->MatchingParen->Previous->isNot(tok::kw_template);
+
+    return (!IsPPKeyword && PreviousNotConst->is(tok::identifier)) ||
+           PreviousNotConst->Type == TT_PointerOrReference ||
+           isSimpleTypeSpecifier(*PreviousNotConst);
+  }
+
   /// \brief Return the type of the given token assuming it is * or &.
-  TokenType
-  determineStarAmpUsage(const AnnotatedToken &Tok, bool IsExpression) {
-    const AnnotatedToken *PrevToken = Tok.getPreviousNoneComment();
+  TokenType determineStarAmpUsage(const FormatToken &Tok, bool IsExpression) {
+    const FormatToken *PrevToken = Tok.getPreviousNonComment();
     if (PrevToken == NULL)
       return TT_UnaryOperator;
 
-    const AnnotatedToken *NextToken = Tok.getNextNoneComment();
+    const FormatToken *NextToken = Tok.getNextNonComment();
     if (NextToken == NULL)
       return TT_Unknown;
 
-    if (PrevToken->is(tok::l_paren) && !IsExpression)
+    if (PrevToken->is(tok::coloncolon) ||
+        (PrevToken->is(tok::l_paren) && !IsExpression))
       return TT_PointerOrReference;
 
     if (PrevToken->isOneOf(tok::l_paren, tok::l_square, tok::l_brace,
                            tok::comma, tok::semi, tok::kw_return, tok::colon,
-                           tok::equal) ||
+                           tok::equal, tok::kw_delete, tok::kw_sizeof) ||
         PrevToken->Type == TT_BinaryOperator ||
         PrevToken->Type == TT_UnaryOperator || PrevToken->Type == TT_CastRParen)
       return TT_UnaryOperator;
@@ -687,9 +767,14 @@ private:
     if (NextToken->is(tok::l_square))
       return TT_PointerOrReference;
 
-    if (PrevToken->FormatTok.Tok.isLiteral() ||
+    if (PrevToken->is(tok::r_paren) && PrevToken->MatchingParen &&
+        PrevToken->MatchingParen->Previous &&
+        PrevToken->MatchingParen->Previous->is(tok::kw_typeof))
+      return TT_PointerOrReference;
+
+    if (PrevToken->Tok.isLiteral() ||
         PrevToken->isOneOf(tok::r_paren, tok::r_square) ||
-        NextToken->FormatTok.Tok.isLiteral() || NextToken->isUnaryOperator())
+        NextToken->Tok.isLiteral() || NextToken->isUnaryOperator())
       return TT_BinaryOperator;
 
     // It is very unlikely that we are going to find a pointer or reference type
@@ -700,9 +785,9 @@ private:
     return TT_PointerOrReference;
   }
 
-  TokenType determinePlusMinusCaretUsage(const AnnotatedToken &Tok) {
-    const AnnotatedToken *PrevToken = Tok.getPreviousNoneComment();
-    if (PrevToken == NULL)
+  TokenType determinePlusMinusCaretUsage(const FormatToken &Tok) {
+    const FormatToken *PrevToken = Tok.getPreviousNonComment();
+    if (PrevToken == NULL || PrevToken->Type == TT_CastRParen)
       return TT_UnaryOperator;
 
     // Use heuristics to recognize unary operators.
@@ -720,9 +805,9 @@ private:
   }
 
   /// \brief Determine whether ++/-- are pre- or post-increments/-decrements.
-  TokenType determineIncrementUsage(const AnnotatedToken &Tok) {
-    const AnnotatedToken *PrevToken = Tok.getPreviousNoneComment();
-    if (PrevToken == NULL)
+  TokenType determineIncrementUsage(const FormatToken &Tok) {
+    const FormatToken *PrevToken = Tok.getPreviousNonComment();
+    if (PrevToken == NULL || PrevToken->Type == TT_CastRParen)
       return TT_UnaryOperator;
     if (PrevToken->isOneOf(tok::r_paren, tok::r_square, tok::identifier))
       return TT_TrailingUnaryOperator;
@@ -733,8 +818,8 @@ private:
   // FIXME: This is copy&pasted from Sema. Put it in a common place and remove
   // duplication.
   /// \brief Determine whether the token kind starts a simple-type-specifier.
-  bool isSimpleTypeSpecifier(const AnnotatedToken &Tok) const {
-    switch (Tok.FormatTok.Tok.getKind()) {
+  bool isSimpleTypeSpecifier(const FormatToken &Tok) const {
+    switch (Tok.Tok.getKind()) {
     case tok::kw_short:
     case tok::kw_long:
     case tok::kw___int64:
@@ -750,71 +835,90 @@ private:
     case tok::kw_wchar_t:
     case tok::kw_bool:
     case tok::kw___underlying_type:
-      return true;
     case tok::annot_typename:
     case tok::kw_char16_t:
     case tok::kw_char32_t:
     case tok::kw_typeof:
     case tok::kw_decltype:
-      return Lex.getLangOpts().CPlusPlus;
+      return true;
     default:
-      break;
+      return false;
     }
-    return false;
   }
 
   SmallVector<Context, 8> Contexts;
 
-  SourceManager &SourceMgr;
-  Lexer &Lex;
+  const FormatStyle &Style;
   AnnotatedLine &Line;
-  AnnotatedToken *CurrentToken;
+  FormatToken *CurrentToken;
   bool KeywordVirtualFound;
-  bool NameFound;
+  bool AutoFound;
   IdentifierInfo &Ident_in;
 };
 
+static int PrecedenceUnaryOperator = prec::PointerToMember + 1;
+static int PrecedenceArrowAndPeriod = prec::PointerToMember + 2;
+
 /// \brief Parses binary expressions by inserting fake parenthesis based on
 /// operator precedence.
 class ExpressionParser {
 public:
-  ExpressionParser(AnnotatedLine &Line) : Current(&Line.First) {}
+  ExpressionParser(AnnotatedLine &Line) : Current(Line.First) {
+    // Skip leading "}", e.g. in "} else if (...) {".
+    if (Current->is(tok::r_brace))
+      next();
+  }
 
   /// \brief Parse expressions with the given operatore precedence.
   void parse(int Precedence = 0) {
-    if (Precedence > prec::PointerToMember || Current == NULL)
+    // Skip 'return' and ObjC selector colons as they are not part of a binary
+    // expression.
+    while (Current &&
+           (Current->is(tok::kw_return) ||
+            (Current->is(tok::colon) && Current->Type == TT_ObjCMethodExpr)))
+      next();
+
+    if (Current == NULL || Precedence > PrecedenceArrowAndPeriod)
       return;
 
-    // Eagerly consume trailing comments.
-    while (Current && Current->isTrailingComment()) {
-      next();
+    // Conditional expressions need to be parsed separately for proper nesting.
+    if (Precedence == prec::Conditional) {
+      parseConditionalExpr();
+      return;
     }
 
-    AnnotatedToken *Start = Current;
-    bool OperatorFound = false;
+    // Parse unary operators, which all have a higher precedence than binary
+    // operators.
+    if (Precedence == PrecedenceUnaryOperator) {
+      parseUnaryOperator();
+      return;
+    }
+
+    FormatToken *Start = Current;
+    FormatToken *LatestOperator = NULL;
 
     while (Current) {
       // Consume operators with higher precedence.
       parse(Precedence + 1);
 
-      int CurrentPrecedence = 0;
-      if (Current) {
-        if (Current->Type == TT_ConditionalExpr)
-          CurrentPrecedence = 1 + (int) prec::Conditional;
-        else if (Current->is(tok::semi) || Current->Type == TT_InlineASMColon)
-          CurrentPrecedence = 1;
-        else if (Current->Type == TT_BinaryOperator || Current->is(tok::comma))
-          CurrentPrecedence = 1 + (int) getPrecedence(*Current);
-      }
+      int CurrentPrecedence = getCurrentPrecedence();
+
+      if (Current && Current->Type == TT_ObjCSelectorName &&
+          Precedence == CurrentPrecedence)
+        Start = Current;
 
       // At the end of the line or when an operator with higher precedence is
       // found, insert fake parenthesis and return.
       if (Current == NULL || Current->closesScope() ||
-          (CurrentPrecedence != 0 && CurrentPrecedence < Precedence)) {
-        if (OperatorFound) {
-          Start->FakeLParens.push_back(prec::Level(Precedence - 1));
-          if (Current)
-            ++Current->Parent->FakeRParens;
+          (CurrentPrecedence != -1 && CurrentPrecedence < Precedence)) {
+        if (LatestOperator) {
+          if (Precedence == PrecedenceArrowAndPeriod) {
+            LatestOperator->LastInChainOfCalls = true;
+            // Call expressions don't have a binary operator precedence.
+            addFakeParenthesis(Start, prec::Unknown);
+          } else {
+            addFakeParenthesis(Start, prec::Level(Precedence));
+          }
         }
         return;
       }
@@ -829,7 +933,7 @@ public:
       } else {
         // Operator found.
         if (CurrentPrecedence == Precedence)
-          OperatorFound = true;
+          LatestOperator = Current;
 
         next();
       }
@@ -837,16 +941,99 @@ public:
   }
 
 private:
+  /// \brief Gets the precedence (+1) of the given token for binary operators
+  /// and other tokens that we treat like binary operators.
+  int getCurrentPrecedence() {
+    if (Current) {
+      if (Current->Type == TT_ConditionalExpr)
+        return prec::Conditional;
+      else if (Current->is(tok::semi) || Current->Type == TT_InlineASMColon ||
+               Current->Type == TT_ObjCSelectorName)
+        return 0;
+      else if (Current->Type == TT_BinaryOperator || Current->is(tok::comma))
+        return Current->getPrecedence();
+      else if (Current->isOneOf(tok::period, tok::arrow))
+        return PrecedenceArrowAndPeriod;
+    }
+    return -1;
+  }
+
+  void addFakeParenthesis(FormatToken *Start, prec::Level Precedence) {
+    Start->FakeLParens.push_back(Precedence);
+    if (Precedence > prec::Unknown)
+      Start->StartsBinaryExpression = true;
+    if (Current) {
+      ++Current->Previous->FakeRParens;
+      if (Precedence > prec::Unknown)
+        Current->Previous->EndsBinaryExpression = true;
+    }
+  }
+
+  /// \brief Parse unary operator expressions and surround them with fake
+  /// parentheses if appropriate.
+  void parseUnaryOperator() {
+    if (Current == NULL || Current->Type != TT_UnaryOperator) {
+      parse(PrecedenceArrowAndPeriod);
+      return;
+    }
+
+    FormatToken *Start = Current;
+    next();
+    parseUnaryOperator();
+
+    // The actual precedence doesn't matter.
+    addFakeParenthesis(Start, prec::Unknown);
+  }
+
+  void parseConditionalExpr() {
+    FormatToken *Start = Current;
+    parse(prec::LogicalOr);
+    if (!Current || !Current->is(tok::question))
+      return;
+    next();
+    parse(prec::LogicalOr);
+    if (!Current || Current->Type != TT_ConditionalExpr)
+      return;
+    next();
+    parseConditionalExpr();
+    addFakeParenthesis(Start, prec::Conditional);
+  }
+
   void next() {
-    if (Current != NULL)
-      Current = Current->Children.empty() ? NULL : &Current->Children[0];
+    if (Current)
+      Current = Current->Next;
+    while (Current && Current->isTrailingComment())
+      Current = Current->Next;
   }
 
-  AnnotatedToken *Current;
+  FormatToken *Current;
 };
 
+} // end anonymous namespace
+
+void
+TokenAnnotator::setCommentLineLevels(SmallVectorImpl<AnnotatedLine *> &Lines) {
+  const AnnotatedLine *NextNonCommentLine = NULL;
+  for (SmallVectorImpl<AnnotatedLine *>::reverse_iterator I = Lines.rbegin(),
+                                                          E = Lines.rend();
+       I != E; ++I) {
+    if (NextNonCommentLine && (*I)->First->is(tok::comment) &&
+        (*I)->First->Next == NULL)
+      (*I)->Level = NextNonCommentLine->Level;
+    else
+      NextNonCommentLine = (*I)->First->isNot(tok::r_brace) ? (*I) : NULL;
+
+    setCommentLineLevels((*I)->Children);
+  }
+}
+
 void TokenAnnotator::annotate(AnnotatedLine &Line) {
-  AnnotatingParser Parser(SourceMgr, Lex, Line, Ident_in);
+  for (SmallVectorImpl<AnnotatedLine *>::iterator I = Line.Children.begin(),
+                                                  E = Line.Children.end();
+       I != E; ++I) {
+    annotate(**I);
+  }
+  AnnotatingParser Parser(Style, Line, Ident_in);
   Line.Type = Parser.parseLine();
   if (Line.Type == LT_Invalid)
     return;
@@ -854,84 +1041,114 @@ void TokenAnnotator::annotate(AnnotatedLine &Line) {
   ExpressionParser ExprParser(Line);
   ExprParser.parse();
 
-  if (Line.First.Type == TT_ObjCMethodSpecifier)
+  if (Line.First->Type == TT_ObjCMethodSpecifier)
     Line.Type = LT_ObjCMethodDecl;
-  else if (Line.First.Type == TT_ObjCDecl)
+  else if (Line.First->Type == TT_ObjCDecl)
     Line.Type = LT_ObjCDecl;
-  else if (Line.First.Type == TT_ObjCProperty)
+  else if (Line.First->Type == TT_ObjCProperty)
     Line.Type = LT_ObjCProperty;
 
-  Line.First.SpacesRequiredBefore = 1;
-  Line.First.MustBreakBefore = Line.First.FormatTok.MustBreakBefore;
-  Line.First.CanBreakBefore = Line.First.MustBreakBefore;
-
-  Line.First.TotalLength = Line.First.FormatTok.TokenLength;
+  Line.First->SpacesRequiredBefore = 1;
+  Line.First->CanBreakBefore = Line.First->MustBreakBefore;
 }
 
 void TokenAnnotator::calculateFormattingInformation(AnnotatedLine &Line) {
-  if (Line.First.Children.empty())
+  Line.First->TotalLength =
+      Line.First->IsMultiline ? Style.ColumnLimit : Line.First->ColumnWidth;
+  if (!Line.First->Next)
     return;
-  AnnotatedToken *Current = &Line.First.Children[0];
+  FormatToken *Current = Line.First->Next;
+  bool InFunctionDecl = Line.MightBeFunctionDecl;
   while (Current != NULL) {
     if (Current->Type == TT_LineComment)
       Current->SpacesRequiredBefore = Style.SpacesBeforeTrailingComments;
-    else
-      Current->SpacesRequiredBefore =
-          spaceRequiredBefore(Line, *Current) ? 1 : 0;
-
-    if (Current->FormatTok.MustBreakBefore) {
-      Current->MustBreakBefore = true;
-    } else if (Current->Type == TT_LineComment) {
-      Current->MustBreakBefore = Current->FormatTok.NewlinesBefore > 0;
-    } else if (Current->Parent->isTrailingComment() ||
-               (Current->is(tok::string_literal) &&
-                Current->Parent->is(tok::string_literal))) {
-      Current->MustBreakBefore = true;
-    } else if (Current->is(tok::lessless) && !Current->Children.empty() &&
-               Current->Parent->is(tok::string_literal) &&
-               Current->Children[0].is(tok::string_literal)) {
-      Current->MustBreakBefore = true;
-    } else {
-      Current->MustBreakBefore = false;
-    }
+    else if (Current->SpacesRequiredBefore == 0 &&
+             spaceRequiredBefore(Line, *Current))
+      Current->SpacesRequiredBefore = 1;
+
+    Current->MustBreakBefore =
+        Current->MustBreakBefore || mustBreakBefore(Line, *Current);
+
     Current->CanBreakBefore =
         Current->MustBreakBefore || canBreakBefore(Line, *Current);
-    if (Current->MustBreakBefore)
-      Current->TotalLength = Current->Parent->TotalLength + Style.ColumnLimit;
+    if (Current->MustBreakBefore || !Current->Children.empty() ||
+        Current->IsMultiline)
+      Current->TotalLength = Current->Previous->TotalLength + Style.ColumnLimit;
     else
-      Current->TotalLength =
-          Current->Parent->TotalLength + Current->FormatTok.TokenLength +
-          Current->SpacesRequiredBefore;
+      Current->TotalLength = Current->Previous->TotalLength +
+                             Current->ColumnWidth +
+                             Current->SpacesRequiredBefore;
+
+    if (Current->Type == TT_CtorInitializerColon)
+      InFunctionDecl = false;
+
     // FIXME: Only calculate this if CanBreakBefore is true once static
     // initializers etc. are sorted out.
     // FIXME: Move magic numbers to a better place.
-    Current->SplitPenalty =
-        20 * Current->BindingStrength + splitPenalty(Line, *Current);
+    Current->SplitPenalty = 20 * Current->BindingStrength +
+                            splitPenalty(Line, *Current, InFunctionDecl);
 
-    Current = Current->Children.empty() ? NULL : &Current->Children[0];
+    Current = Current->Next;
   }
 
-  DEBUG({
-    printDebugInfo(Line);
-  });
+  calculateUnbreakableTailLengths(Line);
+  for (Current = Line.First; Current != NULL; Current = Current->Next) {
+    if (Current->Role)
+      Current->Role->precomputeFormattingInfos(Current);
+  }
+
+  DEBUG({ printDebugInfo(Line); });
+
+  for (SmallVectorImpl<AnnotatedLine *>::iterator I = Line.Children.begin(),
+                                                  E = Line.Children.end();
+       I != E; ++I) {
+    calculateFormattingInformation(**I);
+  }
+}
+
+void TokenAnnotator::calculateUnbreakableTailLengths(AnnotatedLine &Line) {
+  unsigned UnbreakableTailLength = 0;
+  FormatToken *Current = Line.Last;
+  while (Current != NULL) {
+    Current->UnbreakableTailLength = UnbreakableTailLength;
+    if (Current->CanBreakBefore ||
+        Current->isOneOf(tok::comment, tok::string_literal)) {
+      UnbreakableTailLength = 0;
+    } else {
+      UnbreakableTailLength +=
+          Current->ColumnWidth + Current->SpacesRequiredBefore;
+    }
+    Current = Current->Previous;
+  }
 }
 
 unsigned TokenAnnotator::splitPenalty(const AnnotatedLine &Line,
-                                      const AnnotatedToken &Tok) {
-  const AnnotatedToken &Left = *Tok.Parent;
-  const AnnotatedToken &Right = Tok;
+                                      const FormatToken &Tok,
+                                      bool InFunctionDecl) {
+  const FormatToken &Left = *Tok.Previous;
+  const FormatToken &Right = Tok;
 
-  if (Right.Type == TT_StartOfName) {
-    if (Line.First.is(tok::kw_for) && Right.PartOfMultiVariableDeclStmt)
+  if (Left.is(tok::semi))
+    return 0;
+  if (Left.is(tok::comma))
+    return 1;
+  if (Right.is(tok::l_square))
+    return 150;
+
+  if (Right.Type == TT_StartOfName || Right.is(tok::kw_operator)) {
+    if (Line.First->is(tok::kw_for) && Right.PartOfMultiVariableDeclStmt)
       return 3;
-    else if (Line.MightBeFunctionDecl && Right.BindingStrength == 1)
+    if (Left.Type == TT_StartOfName)
+      return 20;
+    if (InFunctionDecl && Right.BindingStrength == 1)
       // FIXME: Clean up hack of using BindingStrength to find top-level names.
       return Style.PenaltyReturnTypeOnItsOwnLine;
-    else
-      return 200;
+    return 200;
   }
   if (Left.is(tok::equal) && Right.is(tok::l_brace))
     return 150;
+  if (Left.Type == TT_CastRParen)
+    return 100;
   if (Left.is(tok::coloncolon))
     return 500;
   if (Left.isOneOf(tok::kw_class, tok::kw_struct))
@@ -941,50 +1158,53 @@ unsigned TokenAnnotator::splitPenalty(const AnnotatedLine &Line,
       Left.Type == TT_InheritanceColon)
     return 2;
 
-  if (Right.isOneOf(tok::arrow, tok::period)) {
-    if (Line.Type == LT_BuilderTypeCall)
-      return prec::PointerToMember;
+  if (Right.isMemberAccess()) {
     if (Left.isOneOf(tok::r_paren, tok::r_square) && Left.MatchingParen &&
         Left.MatchingParen->ParameterCount > 0)
       return 20; // Should be smaller than breaking at a nested comma.
     return 150;
   }
 
+  // Breaking before a trailing 'const' or not-function-like annotation is bad.
+  if (Left.is(tok::r_paren) && Line.Type != LT_ObjCProperty &&
+      (Right.is(tok::kw_const) || (Right.is(tok::identifier) && Right.Next &&
+                                   Right.Next->isNot(tok::l_paren))))
+    return 100;
+
   // In for-loops, prefer breaking at ',' and ';'.
-  if (Line.First.is(tok::kw_for) && Left.is(tok::equal))
+  if (Line.First->is(tok::kw_for) && Left.is(tok::equal))
     return 4;
 
-  if (Left.is(tok::semi))
-    return 0;
-  if (Left.is(tok::comma))
-    return 1;
-
   // In Objective-C method expressions, prefer breaking before "param:" over
   // breaking after it.
   if (Right.Type == TT_ObjCSelectorName)
     return 0;
   if (Left.is(tok::colon) && Left.Type == TT_ObjCMethodExpr)
-    return 20;
+    return 50;
 
-  if (Left.is(tok::l_paren) && Line.MightBeFunctionDecl)
+  if (Left.is(tok::l_paren) && InFunctionDecl)
     return 100;
   if (Left.opensScope())
-    return Left.ParameterCount > 1 ? prec::Comma : 20;
+    return Left.ParameterCount > 1 ? Style.PenaltyBreakBeforeFirstCallParameter
+                                   : 19;
 
   if (Right.is(tok::lessless)) {
     if (Left.is(tok::string_literal)) {
-      StringRef Content = StringRef(Left.FormatTok.Tok.getLiteralData(),
-                                    Left.FormatTok.TokenLength);
-      Content = Content.drop_back(1).drop_front(1).trim();
+      StringRef Content = Left.TokenText;
+      if (Content.startswith("\""))
+        Content = Content.drop_front(1);
+      if (Content.endswith("\""))
+        Content = Content.drop_back(1);
+      Content = Content.trim();
       if (Content.size() > 1 &&
           (Content.back() == ':' || Content.back() == '='))
-        return 100;
+        return 25;
     }
-    return prec::Shift;
+    return 1; // Breaking at a << is really cheap.
   }
   if (Left.Type == TT_ConditionalExpr)
     return prec::Conditional;
-  prec::Level Level = getPrecedence(Left);
+  prec::Level Level = Left.getPrecedence();
 
   if (Level != prec::Unknown)
     return Level;
@@ -993,13 +1213,23 @@ unsigned TokenAnnotator::splitPenalty(const AnnotatedLine &Line,
 }
 
 bool TokenAnnotator::spaceRequiredBetween(const AnnotatedLine &Line,
-                                          const AnnotatedToken &Left,
-                                          const AnnotatedToken &Right) {
+                                          const FormatToken &Left,
+                                          const FormatToken &Right) {
   if (Right.is(tok::hashhash))
     return Left.is(tok::hash);
   if (Left.isOneOf(tok::hashhash, tok::hash))
     return Right.is(tok::hash);
-  if (Right.isOneOf(tok::r_paren, tok::semi, tok::comma))
+  if (Left.is(tok::l_paren) && Right.is(tok::r_paren))
+    return Style.SpaceInEmptyParentheses;
+  if (Left.is(tok::l_paren) || Right.is(tok::r_paren))
+    return (Right.Type == TT_CastRParen ||
+            (Left.MatchingParen && Left.MatchingParen->Type == TT_CastRParen))
+               ? Style.SpacesInCStyleCastParentheses
+               : Style.SpacesInParentheses;
+  if (Style.SpacesInAngles &&
+      ((Left.Type == TT_TemplateOpener) != (Right.Type == TT_TemplateCloser)))
+    return true;
+  if (Right.isOneOf(tok::semi, tok::comma))
     return false;
   if (Right.is(tok::less) &&
       (Left.is(tok::kw_template) ||
@@ -1017,186 +1247,282 @@ bool TokenAnnotator::spaceRequiredBetween(const AnnotatedLine &Line,
   if (Left.is(tok::coloncolon))
     return false;
   if (Right.is(tok::coloncolon))
-    return !Left.isOneOf(tok::identifier, tok::greater, tok::l_paren);
+    return (Left.is(tok::less) && Style.Standard == FormatStyle::LS_Cpp03) ||
+           !Left.isOneOf(tok::identifier, tok::greater, tok::l_paren,
+                         tok::r_paren, tok::less);
   if (Left.is(tok::less) || Right.isOneOf(tok::greater, tok::less))
     return false;
+  if (Right.is(tok::ellipsis))
+    return Left.Tok.isLiteral();
+  if (Left.is(tok::l_square) && Right.is(tok::amp))
+    return false;
   if (Right.Type == TT_PointerOrReference)
-    return Left.FormatTok.Tok.isLiteral() ||
+    return Left.Tok.isLiteral() ||
            ((Left.Type != TT_PointerOrReference) && Left.isNot(tok::l_paren) &&
             !Style.PointerBindsToType);
+  if (Right.Type == TT_FunctionTypeLParen && Left.isNot(tok::l_paren) &&
+      (Left.Type != TT_PointerOrReference || Style.PointerBindsToType))
+    return true;
   if (Left.Type == TT_PointerOrReference)
-    return Right.FormatTok.Tok.isLiteral() ||
+    return Right.Tok.isLiteral() || Right.Type == TT_BlockComment ||
            ((Right.Type != TT_PointerOrReference) &&
             Right.isNot(tok::l_paren) && Style.PointerBindsToType &&
-            Left.Parent && Left.Parent->isNot(tok::l_paren));
+            Left.Previous &&
+            !Left.Previous->isOneOf(tok::l_paren, tok::coloncolon));
   if (Right.is(tok::star) && Left.is(tok::l_paren))
     return false;
   if (Left.is(tok::l_square))
-    return Left.Type == TT_ObjCArrayLiteral && Right.isNot(tok::r_square);
+    return Left.Type == TT_ArrayInitializerLSquare &&
+           Right.isNot(tok::r_square);
   if (Right.is(tok::r_square))
-    return Right.Type == TT_ObjCArrayLiteral;
-  if (Right.is(tok::l_square) && Right.Type != TT_ObjCMethodExpr)
-    return false;
-  if (Left.is(tok::period) || Right.is(tok::period))
+    return Right.MatchingParen &&
+           Right.MatchingParen->Type == TT_ArrayInitializerLSquare;
+  if (Right.is(tok::l_square) && Right.Type != TT_ObjCMethodExpr &&
+      Right.Type != TT_LambdaLSquare && Left.isNot(tok::numeric_constant))
     return false;
   if (Left.is(tok::colon))
     return Left.Type != TT_ObjCMethodExpr;
   if (Right.is(tok::colon))
-    return Right.Type != TT_ObjCMethodExpr;
-  if (Left.is(tok::l_paren))
-    return false;
+    return Right.Type != TT_ObjCMethodExpr && !Left.is(tok::question);
   if (Right.is(tok::l_paren)) {
+    if (Left.is(tok::r_paren) && Left.MatchingParen &&
+        Left.MatchingParen->Previous &&
+        Left.MatchingParen->Previous->is(tok::kw___attribute))
+      return true;
     return Line.Type == LT_ObjCDecl ||
-           Left.isOneOf(tok::kw_if, tok::kw_for, tok::kw_while, tok::kw_switch,
-                        tok::kw_return, tok::kw_catch, tok::kw_new,
-                        tok::kw_delete, tok::semi);
+           Left.isOneOf(tok::kw_return, tok::kw_new, tok::kw_delete,
+                        tok::semi) ||
+           (Style.SpaceAfterControlStatementKeyword &&
+            Left.isOneOf(tok::kw_if, tok::kw_for, tok::kw_while, tok::kw_switch,
+                         tok::kw_catch));
   }
-  if (Left.is(tok::at) &&
-      Right.FormatTok.Tok.getObjCKeywordID() != tok::objc_not_keyword)
+  if (Left.is(tok::at) && Right.Tok.getObjCKeywordID() != tok::objc_not_keyword)
     return false;
   if (Left.is(tok::l_brace) && Right.is(tok::r_brace))
+    return !Left.Children.empty(); // No spaces in "{}".
+  if (Left.is(tok::l_brace) || Right.is(tok::r_brace))
+    return !Style.Cpp11BracedListStyle;
+  if (Right.Type == TT_UnaryOperator)
+    return !Left.isOneOf(tok::l_paren, tok::l_square, tok::at) &&
+           (Left.isNot(tok::colon) || Left.Type != TT_ObjCMethodExpr);
+  if (Left.isOneOf(tok::identifier, tok::greater, tok::r_square) &&
+      Right.is(tok::l_brace) && Right.getNextNonComment() &&
+      Right.BlockKind != BK_Block)
     return false;
-  if (Right.is(tok::ellipsis))
+  if (Left.is(tok::period) || Right.is(tok::period))
+    return false;
+  if (Left.Type == TT_BlockComment && Left.TokenText.endswith("=*/"))
+    return false;
+  if (Right.is(tok::hash) && Left.is(tok::identifier) && Left.TokenText == "L")
     return false;
   return true;
 }
 
 bool TokenAnnotator::spaceRequiredBefore(const AnnotatedLine &Line,
-                                         const AnnotatedToken &Tok) {
-  if (Tok.FormatTok.Tok.getIdentifierInfo() &&
-      Tok.Parent->FormatTok.Tok.getIdentifierInfo())
+                                         const FormatToken &Tok) {
+  if (Tok.Tok.getIdentifierInfo() && Tok.Previous->Tok.getIdentifierInfo())
     return true; // Never ever merge two identifiers.
+  if (Tok.Previous->Type == TT_ImplicitStringLiteral)
+    return Tok.WhitespaceRange.getBegin() != Tok.WhitespaceRange.getEnd();
   if (Line.Type == LT_ObjCMethodDecl) {
-    if (Tok.Parent->Type == TT_ObjCMethodSpecifier)
+    if (Tok.Previous->Type == TT_ObjCMethodSpecifier)
       return true;
-    if (Tok.Parent->is(tok::r_paren) && Tok.is(tok::identifier))
+    if (Tok.Previous->is(tok::r_paren) && Tok.is(tok::identifier))
       // Don't space between ')' and <id>
       return false;
   }
   if (Line.Type == LT_ObjCProperty &&
-      (Tok.is(tok::equal) || Tok.Parent->is(tok::equal)))
+      (Tok.is(tok::equal) || Tok.Previous->is(tok::equal)))
     return false;
 
-  if (Tok.Parent->is(tok::comma))
+  if (Tok.Type == TT_TrailingReturnArrow ||
+      Tok.Previous->Type == TT_TrailingReturnArrow)
+    return true;
+  if (Tok.Previous->is(tok::comma))
     return true;
   if (Tok.is(tok::comma))
     return false;
   if (Tok.Type == TT_CtorInitializerColon || Tok.Type == TT_ObjCBlockLParen)
     return true;
-  if (Tok.Parent->FormatTok.Tok.is(tok::kw_operator))
-    return false;
+  if (Tok.Previous->Tok.is(tok::kw_operator))
+    return Tok.is(tok::coloncolon);
   if (Tok.Type == TT_OverloadedOperatorLParen)
     return false;
   if (Tok.is(tok::colon))
-    return !Line.First.isOneOf(tok::kw_case, tok::kw_default) &&
-           Tok.getNextNoneComment() != NULL && Tok.Type != TT_ObjCMethodExpr;
-  if (Tok.is(tok::l_paren) && !Tok.Children.empty() &&
-      Tok.Children[0].Type == TT_PointerOrReference &&
-      !Tok.Children[0].Children.empty() &&
-      Tok.Children[0].Children[0].isNot(tok::r_paren) &&
-      Tok.Parent->isNot(tok::l_paren) &&
-      (Tok.Parent->Type != TT_PointerOrReference || Style.PointerBindsToType))
-    return true;
-  if (Tok.Parent->Type == TT_UnaryOperator || Tok.Parent->Type == TT_CastRParen)
+    return !Line.First->isOneOf(tok::kw_case, tok::kw_default) &&
+           Tok.getNextNonComment() != NULL && Tok.Type != TT_ObjCMethodExpr &&
+           !Tok.Previous->is(tok::question);
+  if (Tok.Previous->Type == TT_UnaryOperator ||
+      Tok.Previous->Type == TT_CastRParen)
     return false;
-  if (Tok.Type == TT_UnaryOperator)
-    return !Tok.Parent->isOneOf(tok::l_paren, tok::l_square, tok::at) &&
-           (Tok.Parent->isNot(tok::colon) ||
-            Tok.Parent->Type != TT_ObjCMethodExpr);
-  if (Tok.Parent->is(tok::greater) && Tok.is(tok::greater)) {
+  if (Tok.Previous->is(tok::greater) && Tok.is(tok::greater)) {
     return Tok.Type == TT_TemplateCloser &&
-           Tok.Parent->Type == TT_TemplateCloser &&
-           Style.Standard != FormatStyle::LS_Cpp11;
+           Tok.Previous->Type == TT_TemplateCloser &&
+           (Style.Standard != FormatStyle::LS_Cpp11 || Style.SpacesInAngles);
   }
   if (Tok.isOneOf(tok::arrowstar, tok::periodstar) ||
-      Tok.Parent->isOneOf(tok::arrowstar, tok::periodstar))
+      Tok.Previous->isOneOf(tok::arrowstar, tok::periodstar))
+    return false;
+  if (!Style.SpaceBeforeAssignmentOperators &&
+      Tok.getPrecedence() == prec::Assignment)
     return false;
-  if (Tok.Type == TT_BinaryOperator || Tok.Parent->Type == TT_BinaryOperator)
+  if ((Tok.Type == TT_BinaryOperator && !Tok.Previous->is(tok::l_paren)) ||
+      Tok.Previous->Type == TT_BinaryOperator)
     return true;
-  if (Tok.Parent->Type == TT_TemplateCloser && Tok.is(tok::l_paren))
+  if (Tok.Previous->Type == TT_TemplateCloser && Tok.is(tok::l_paren))
     return false;
-  if (Tok.is(tok::less) && Line.First.is(tok::hash))
+  if (Tok.is(tok::less) && Tok.Previous->isNot(tok::l_paren) &&
+      Line.First->is(tok::hash))
     return true;
   if (Tok.Type == TT_TrailingUnaryOperator)
     return false;
-  return spaceRequiredBetween(Line, *Tok.Parent, Tok);
+  return spaceRequiredBetween(Line, *Tok.Previous, Tok);
+}
+
+bool TokenAnnotator::mustBreakBefore(const AnnotatedLine &Line,
+                                     const FormatToken &Right) {
+  if (Right.is(tok::comment)) {
+    return Right.NewlinesBefore > 0;
+  } else if (Right.Previous->isTrailingComment() ||
+             (Right.is(tok::string_literal) &&
+              Right.Previous->is(tok::string_literal))) {
+    return true;
+  } else if (Right.Previous->IsUnterminatedLiteral) {
+    return true;
+  } else if (Right.is(tok::lessless) && Right.Next &&
+             Right.Previous->is(tok::string_literal) &&
+             Right.Next->is(tok::string_literal)) {
+    return true;
+  } else if (Right.Previous->ClosesTemplateDeclaration &&
+             Right.Previous->MatchingParen &&
+             Right.Previous->MatchingParen->BindingStrength == 1 &&
+             Style.AlwaysBreakTemplateDeclarations) {
+    // FIXME: Fix horrible hack of using BindingStrength to find top-level <>.
+    return true;
+  } else if (Right.Type == TT_CtorInitializerComma &&
+             Style.BreakConstructorInitializersBeforeComma &&
+             !Style.ConstructorInitializerAllOnOneLineOrOnePerLine) {
+    return true;
+  } else if (Right.Previous->BlockKind == BK_Block &&
+             Right.Previous->isNot(tok::r_brace) && Right.isNot(tok::r_brace)) {
+    return true;
+  } else if (Right.is(tok::l_brace) && (Right.BlockKind == BK_Block)) {
+    return Style.BreakBeforeBraces == FormatStyle::BS_Allman;
+  }
+  return false;
 }
 
 bool TokenAnnotator::canBreakBefore(const AnnotatedLine &Line,
-                                    const AnnotatedToken &Right) {
-  const AnnotatedToken &Left = *Right.Parent;
-  if (Right.Type == TT_StartOfName)
+                                    const FormatToken &Right) {
+  const FormatToken &Left = *Right.Previous;
+  if (Right.Type == TT_StartOfName || Right.is(tok::kw_operator))
     return true;
-  if (Right.is(tok::colon) && Right.Type == TT_ObjCMethodExpr)
+  if (Right.isTrailingComment())
+    // We rely on MustBreakBefore being set correctly here as we should not
+    // change the "binding" behavior of a comment.
     return false;
-  if (Left.is(tok::colon) && Left.Type == TT_ObjCMethodExpr)
+  if (Left.is(tok::question) && Right.is(tok::colon))
+    return false;
+  if (Right.Type == TT_ConditionalExpr || Right.is(tok::question))
+    return Style.BreakBeforeTernaryOperators;
+  if (Left.Type == TT_ConditionalExpr || Left.is(tok::question))
+    return !Style.BreakBeforeTernaryOperators;
+  if (Right.is(tok::colon) &&
+      (Right.Type == TT_DictLiteral || Right.Type == TT_ObjCMethodExpr))
+    return false;
+  if (Left.is(tok::colon) &&
+      (Left.Type == TT_DictLiteral || Left.Type == TT_ObjCMethodExpr))
     return true;
   if (Right.Type == TT_ObjCSelectorName)
     return true;
-  if (Left.ClosesTemplateDeclaration)
+  if (Left.is(tok::r_paren) && Line.Type == LT_ObjCProperty)
     return true;
-  if (Right.Type == TT_ConditionalExpr || Right.is(tok::question))
+  if (Left.ClosesTemplateDeclaration)
     return true;
   if (Right.Type == TT_RangeBasedForLoopColon ||
-      Right.Type == TT_OverloadedOperatorLParen)
+      Right.Type == TT_OverloadedOperatorLParen ||
+      Right.Type == TT_OverloadedOperator)
     return false;
   if (Left.Type == TT_RangeBasedForLoopColon)
     return true;
   if (Right.Type == TT_RangeBasedForLoopColon)
     return false;
   if (Left.Type == TT_PointerOrReference || Left.Type == TT_TemplateCloser ||
-      Left.Type == TT_UnaryOperator || Left.Type == TT_ConditionalExpr ||
-      Left.isOneOf(tok::question, tok::kw_operator))
+      Left.Type == TT_UnaryOperator || Left.is(tok::kw_operator))
     return false;
   if (Left.is(tok::equal) && Line.Type == LT_VirtualFunctionDecl)
     return false;
-  if (Left.is(tok::l_paren) && Right.is(tok::l_paren) && Left.Parent &&
-      Left.Parent->is(tok::kw___attribute))
+  if (Left.Previous) {
+    if (Left.is(tok::l_paren) && Right.is(tok::l_paren) &&
+        Left.Previous->is(tok::kw___attribute))
+      return false;
+    if (Left.is(tok::l_paren) && (Left.Previous->Type == TT_BinaryOperator ||
+                                  Left.Previous->Type == TT_CastRParen))
+      return false;
+  }
+  if (Right.Type == TT_ImplicitStringLiteral)
     return false;
 
-  if (Right.Type == TT_LineComment)
-    // We rely on MustBreakBefore being set correctly here as we should not
-    // change the "binding" behavior of a comment.
+  if (Right.is(tok::r_paren) || Right.Type == TT_TemplateCloser)
     return false;
 
+  // We only break before r_brace if there was a corresponding break before
+  // the l_brace, which is tracked by BreakBeforeClosingBrace.
+  if (Right.is(tok::r_brace))
+    return Right.MatchingParen && Right.MatchingParen->BlockKind == BK_Block;
+
   // Allow breaking after a trailing 'const', e.g. after a method declaration,
   // unless it is follow by ';', '{' or '='.
-  if (Left.is(tok::kw_const) && Left.Parent != NULL &&
-      Left.Parent->is(tok::r_paren))
+  if (Left.is(tok::kw_const) && Left.Previous != NULL &&
+      Left.Previous->is(tok::r_paren))
     return !Right.isOneOf(tok::l_brace, tok::semi, tok::equal);
 
   if (Right.is(tok::kw___attribute))
     return true;
 
-  // We only break before r_brace if there was a corresponding break before
-  // the l_brace, which is tracked by BreakBeforeClosingBrace.
-  if (Right.isOneOf(tok::r_brace, tok::r_paren, tok::greater))
-    return false;
   if (Left.is(tok::identifier) && Right.is(tok::string_literal))
     return true;
-  return (Left.isBinaryOperator() && Left.isNot(tok::lessless)) ||
+
+  if (Left.Type == TT_CtorInitializerComma &&
+      Style.BreakConstructorInitializersBeforeComma)
+    return false;
+  if (Right.Type == TT_CtorInitializerComma &&
+      Style.BreakConstructorInitializersBeforeComma)
+    return true;
+  if (Right.isBinaryOperator() && Style.BreakBeforeBinaryOperators)
+    return true;
+  if (Left.is(tok::greater) && Right.is(tok::greater) &&
+      Left.Type != TT_TemplateCloser)
+    return false;
+  if (Left.Type == TT_ArrayInitializerLSquare)
+    return true;
+  return (Left.isBinaryOperator() && Left.isNot(tok::lessless) &&
+          !Style.BreakBeforeBinaryOperators) ||
          Left.isOneOf(tok::comma, tok::coloncolon, tok::semi, tok::l_brace,
                       tok::kw_class, tok::kw_struct) ||
-         Right.isOneOf(tok::lessless, tok::arrow, tok::period, tok::colon) ||
-         (Left.is(tok::r_paren) && Left.Type != TT_CastRParen &&
-          Right.isOneOf(tok::identifier, tok::kw___attribute)) ||
-         (Left.is(tok::l_paren) && !Right.is(tok::r_paren)) ||
-         (Left.is(tok::l_square) && !Right.is(tok::r_square));
+         Right.isOneOf(tok::lessless, tok::arrow, tok::period, tok::colon,
+                       tok::l_square, tok::at) ||
+         (Left.is(tok::r_paren) &&
+          Right.isOneOf(tok::identifier, tok::kw_const, tok::kw___attribute)) ||
+         (Left.is(tok::l_paren) && !Right.is(tok::r_paren));
 }
 
 void TokenAnnotator::printDebugInfo(const AnnotatedLine &Line) {
   llvm::errs() << "AnnotatedTokens:\n";
-  const AnnotatedToken *Tok = &Line.First;
+  const FormatToken *Tok = Line.First;
   while (Tok) {
     llvm::errs() << " M=" << Tok->MustBreakBefore
                  << " C=" << Tok->CanBreakBefore << " T=" << Tok->Type
                  << " S=" << Tok->SpacesRequiredBefore
-                 << " P=" << Tok->SplitPenalty
-                 << " Name=" << Tok->FormatTok.Tok.getName() << " FakeLParens=";
+                 << " P=" << Tok->SplitPenalty << " Name=" << Tok->Tok.getName()
+                 << " L=" << Tok->TotalLength << " PPK=" << Tok->PackingKind
+                 << " FakeLParens=";
     for (unsigned i = 0, e = Tok->FakeLParens.size(); i != e; ++i)
       llvm::errs() << Tok->FakeLParens[i] << "/";
     llvm::errs() << " FakeRParens=" << Tok->FakeRParens << "\n";
-    Tok = Tok->Children.empty() ? NULL : &Tok->Children[0];
+    if (Tok->Next == NULL)
+      assert(Tok == Line.Last);
+    Tok = Tok->Next;
   }
   llvm::errs() << "----\n";
 }