[clang-format] Respect BreakBeforeClosingBrace while calculating length

[krasimir]

Summary

This patch makes getLengthToMatchingParen respect the BreakBeforeClosingBrace
ParenState for matching scope closers. In order to distinguish between paren states
introduced by real vs. fake parens, I've added the token opening the ParensState
to that struct.

[djasper]

lib/Format/ContinuationIndenter.cpp

81

I think this needs a long explanatory comment, possibly with an example of the problem it is actually solving.

Also, I am somewhat skeptical as we are using this logic for all paren kinds, not just braces. That seems to be unnecessary work and also might be unexpected at some point (although I cannot come up with a test case where that would be wrong).

86

Maybe pull out a lambda:

auto FindParenState = [&](const FormatToken *Tok) {
  while (MatchingStackIndex >= 0 && Stack[MatchingStackIndex].Tok != &Tok)
    --MatchingStackIndex;
  return MatchingStackIndex >= 0 ? &Stack[MatchingStackIndex] : nullptr;
};

Then you could write the rest as:

...
FindParenState(&Tok);
const auto* End = Tok.MatchingParen
for (; End->Next; End = End->Next) {
  if (End->Next->CanBreakBefore || !End->Next->closesScope())
    break;
  auto ParenState = FindParenState(End->Next->MatchingParen);
  if (ParenState && ParenState.BreakBeforeClosingBrace)
    break;
}
return End->TotalLength - Tok.TotalLength + 1;

(not entirely sure it's better)

lib/Format/ContinuationIndenter.h

215

The comment should include that this is not considered for memoization as the same state will always be represented by the same token (similar to other below). I wonder whether we should actually move the fields that don't affect memoization out to a different structure at some point.

[krasimir]

• Address review comments

[krasimir]

lib/Format/ContinuationIndenter.cpp

81

Thanks! Added an example and tweaked it a little bit so that it doesn't traverse the stack unless it is visiting tok::r_brace.

86

Yeah, a lambda is good.

[djasper]

Generally looks good.

lib/Format/ContinuationIndenter.cpp

95

I r_brace enough? Do we have something similar for TT_ArrayInitializer? I'd look at usages of BreakBeforeClosingBrace to determine.

[krasimir]

• Added other parens detection

[krasimir]

lib/Format/ContinuationIndenter.cpp

95

Thanks! Based on:
https://github.com/llvm-mirror/clang/blob/bf81db4ab70b45a77fba0d9f7d43190f1ad91bb9/lib/Format/ContinuationIndenter.cpp#L804
I've added also cases for array [-s and text proto <-s and updated comments.

lib/Format/ContinuationIndenter.h

private:
   WhitespaceManager &Whitespaces;
   encoding::Encoding Encoding;
   bool BinPackInconclusiveFunctions;
   llvm::Regex CommentPragmasRegex;
   const RawStringFormatStyleManager RawStringFormats;
 };
 
 struct ParenState {
-  ParenState(unsigned Indent, unsigned LastSpace, bool AvoidBinPacking,
-             bool NoLineBreak)
-      : Indent(Indent), LastSpace(LastSpace), NestedBlockIndent(Indent),
-        BreakBeforeClosingBrace(false), AvoidBinPacking(AvoidBinPacking),
-        BreakBeforeParameter(false), NoLineBreak(NoLineBreak),
-        NoLineBreakInOperand(false), LastOperatorWrapped(true),
-        ContainsLineBreak(false), ContainsUnwrappedBuilder(false),
-        AlignColons(true), ObjCSelectorNameFound(false),
-        HasMultipleNestedBlocks(false), NestedBlockInlined(false),
-        IsInsideObjCArrayLiteral(false) {}
+  ParenState(const FormatToken *Tok, unsigned Indent, unsigned LastSpace,
+             bool AvoidBinPacking, bool NoLineBreak)
+      : Tok(Tok), Indent(Indent), LastSpace(LastSpace),
+        NestedBlockIndent(Indent), BreakBeforeClosingBrace(false),
+        AvoidBinPacking(AvoidBinPacking), BreakBeforeParameter(false),
+        NoLineBreak(NoLineBreak), NoLineBreakInOperand(false),
+        LastOperatorWrapped(true), ContainsLineBreak(false),
+        ContainsUnwrappedBuilder(false), AlignColons(true),
+        ObjCSelectorNameFound(false), HasMultipleNestedBlocks(false),
+        NestedBlockInlined(false), IsInsideObjCArrayLiteral(false) {}
+
+  /// \brief The token opening this parenthesis level, or nullptr if this level
+  /// is opened by fake parenthesis.
+  ///
+  /// Not considered for memoization as it will always have the same value at
+  /// the same token.
+  const FormatToken *Tok;
 
   /// The position to which a specific parenthesis level needs to be
   /// indented.
   unsigned Indent;
 
   /// The position of the last space on each level.
   ///
   /// Used e.g. to break like:

lib/Format/ContinuationIndenter.cpp

 // false otherwise.
 static bool shouldIndentWrappedSelectorName(const FormatStyle &Style,
                                             LineType LineType) {
   return Style.IndentWrappedFunctionNames || LineType == LT_ObjCMethodDecl;
 }
 
 // Returns the length of everything up to the first possible line break after
 // the ), ], } or > matching \c Tok.
-static unsigned getLengthToMatchingParen(const FormatToken &Tok) {
+static unsigned getLengthToMatchingParen(const FormatToken &Tok,
+                                         const std::vector<ParenState> &Stack) {
+  // Normally whether or not a break before T is possible is calculated and
+  // stored in T.CanBreakBefore. Braces, array initializers and text proto
+  // messages like `key: < ... >` are an exception: a break is possible
+  // before a closing brace R if a break was inserted after the corresponding
+  // opening brace. The information about whether or not a break is needed
+  // before a closing brace R is stored in the ParenState field
+  // S.BreakBeforeClosingBrace where S is the state that R closes.
+  //
+  // In order to decide whether there can be a break before encountered right
+  // braces, this implementation iterates over the sequence of tokens and over
+  // the paren stack in lockstep, keeping track of the stack level which visited
+  // right braces correspond to in MatchingStackIndex.
+  //
+  // For example, consider:
+  // L. <- line number
+  // 1. {
+  // 2. {1},
+  // 3. {2},
+  // 4. {{3}}}
+  //     ^ where we call this method with this token.
+  // The paren stack at this point contains 3 brace levels:
+  //  0. { at line 1, BreakBeforeClosingBrace: true
+  //  1. first { at line 4, BreakBeforeClosingBrace: false
+  //  2. second { at line 4, BreakBeforeClosingBrace: false,
+  //  where there might be fake parens levels in-between these levels.
+  // The algorithm will start at the first } on line 4, which is the matching
+  // brace of the initial left brace and at level 2 of the stack. Then,
+  // examining BreakBeforeClosingBrace: false at level 2, it will continue to
+  // the second } on line 4, and will traverse the stack downwards until it
+  // finds the matching { on level 1. Then, examining BreakBeforeClosingBrace:
+  // false at level 1, it will continue to the third } on line 4 and will
+  // traverse the stack downwards until it finds the matching { on level 0.
+  // Then, examining BreakBeforeClosingBrace: true at level 0, the algorithm
+  // will stop and will use the second } on line 4 to determine the length to
+  // return, as in this example the range will include the tokens: {3}}
+  //
+  // The algorithm will only traverse the stack if it encounters braces, array
+  // initializer squares or text proto angle brackets.
   if (!Tok.MatchingParen)
     return 0;
   FormatToken *End = Tok.MatchingParen;
-  while (End->Next && !End->Next->CanBreakBefore) {
-    End = End->Next;
+  // Maintains a stack level corresponding to the current End token.
+  int MatchingStackIndex = Stack.size() - 1;
+  // Traverses the stack downwards, looking for the level to which LBrace
+  // corresponds. Returns either a pointer to the matching level or nullptr if
+  // LParen is not found in the initial portion of the stack up to
+  // MatchingStackIndex.
+  auto FindParenState = [&](const FormatToken *LBrace) -> const ParenState * {
+    while (MatchingStackIndex >= 0 && Stack[MatchingStackIndex].Tok != LBrace)
+      --MatchingStackIndex;
+    return MatchingStackIndex >= 0 ? &Stack[MatchingStackIndex] : nullptr;
+  };
+  for (; End->Next; End = End->Next) {
+    if (End->Next->CanBreakBefore || !End->Next->closesScope())
+      break;
+    if (End->Next->MatchingParen->isOneOf(tok::l_brace,
+                                          TT_ArrayInitializerLSquare,
+                                          tok::less)) {
+      const ParenState *State = FindParenState(End->Next->MatchingParen);
+      if (State && State->BreakBeforeClosingBrace)
+        break;
+    }
   }
   return End->TotalLength - Tok.TotalLength + 1;
 }
 
 static unsigned getLengthToNextOperator(const FormatToken &Tok) {
   if (!Tok.NextOperator)
     return 0;
   return Tok.NextOperator->TotalLength - Tok.TotalLength;
LineState ContinuationIndenter::getInitialState(unsigned FirstIndent,
   // since it's indented after the hash, but FirstIndent is set to the
   // preprocessor indent.
   if (Style.IndentPPDirectives == FormatStyle::PPDIS_AfterHash &&
       (Line->Type == LT_PreprocessorDirective ||
        Line->Type == LT_ImportStatement))
     State.Column = 0;
   State.Line = Line;
   State.NextToken = Line->First;
-  State.Stack.push_back(ParenState(FirstIndent, FirstIndent,
+  State.Stack.push_back(ParenState(/*Tok=*/nullptr, FirstIndent, FirstIndent,
                                    /*AvoidBinPacking=*/false,
                                    /*NoLineBreak=*/false));
   State.LineContainsContinuedForLoopSection = false;
   State.NoContinuation = false;
   State.StartOfStringLiteral = 0;
   State.StartOfLineLevel = 0;
   State.LowestLevelOnLine = 0;
   State.IgnoreStackForComparison = false;
if ((startsNextParameter(Current, Style) || Previous.is(tok::semi) ||
       State.Stack.back().BreakBeforeParameter && !Current.isTrailingComment() &&
       !Current.isOneOf(tok::r_paren, tok::r_brace))
     return true;
   if (((Previous.is(TT_DictLiteral) && Previous.is(tok::l_brace)) ||
        (Previous.is(TT_ArrayInitializerLSquare) &&
         Previous.ParameterCount > 1) ||
        opensProtoMessageField(Previous, Style)) &&
       Style.ColumnLimit > 0 &&
-      getLengthToMatchingParen(Previous) + State.Column - 1 >
+      getLengthToMatchingParen(Previous, State.Stack) + State.Column - 1 >
           getColumnLimit(State))
     return true;
 
   const FormatToken &BreakConstructorInitializersToken =
       Style.BreakConstructorInitializers == FormatStyle::BCIS_AfterColon
           ? Previous
           : Current;
   if (BreakConstructorInitializersToken.is(TT_CtorInitializerColon) &&
bool SkipFirstExtraIndent =
                     (Previous->getPrecedence() == prec::Assignment &&
                      Style.AlignOperands) ||
                     Previous->is(TT_ObjCMethodExpr)));
   for (SmallVectorImpl<prec::Level>::const_reverse_iterator
            I = Current.FakeLParens.rbegin(),
            E = Current.FakeLParens.rend();
        I != E; ++I) {
     ParenState NewParenState = State.Stack.back();
+    NewParenState.Tok = nullptr;
     NewParenState.ContainsLineBreak = false;
     NewParenState.LastOperatorWrapped = true;
     NewParenState.NoLineBreak =
         NewParenState.NoLineBreak || State.Stack.back().NoLineBreakInOperand;
 
     // Don't propagate AvoidBinPacking into subexpressions of arg/param lists.
     if (*I > prec::Comma)
       NewParenState.AvoidBinPacking = false;
AvoidBinPacking =
          (Current.PackingKind == PPK_OnePerLine ||
           (!BinPackInconclusiveFunctions &&
            Current.PackingKind == PPK_Inconclusive)));
 
     if (Current.is(TT_ObjCMethodExpr) && Current.MatchingParen) {
       if (Style.ColumnLimit) {
         // If this '[' opens an ObjC call, determine whether all parameters fit
         // into one line and put one per line if they don't.
-        if (getLengthToMatchingParen(Current) + State.Column >
+        if (getLengthToMatchingParen(Current, State.Stack) + State.Column >
             getColumnLimit(State))
           BreakBeforeParameter = true;
       } else {
         // For ColumnLimit = 0, we have to figure out whether there is or has to
         // be a line break within this call.
         for (const FormatToken *Tok = &Current;
              Tok && Tok != Current.MatchingParen; Tok = Tok->Next) {
           if (Tok->MustBreakBefore ||
void ContinuationIndenter::moveStatePastScopeOpener(LineState &State,
   bool NoLineBreak =
       Current.Children.empty() &&
       !Current.isOneOf(TT_DictLiteral, TT_ArrayInitializerLSquare) &&
       (State.Stack.back().NoLineBreak ||
        State.Stack.back().NoLineBreakInOperand ||
        (Current.is(TT_TemplateOpener) &&
         State.Stack.back().ContainsUnwrappedBuilder));
   State.Stack.push_back(
-      ParenState(NewIndent, LastSpace, AvoidBinPacking, NoLineBreak));
+      ParenState(&Current, NewIndent, LastSpace, AvoidBinPacking, NoLineBreak));
   State.Stack.back().NestedBlockIndent = NestedBlockIndent;
   State.Stack.back().BreakBeforeParameter = BreakBeforeParameter;
   State.Stack.back().HasMultipleNestedBlocks = Current.BlockParameterCount > 1;
   State.Stack.back().IsInsideObjCArrayLiteral =
       Current.is(TT_ArrayInitializerLSquare) && Current.Previous &&
       Current.Previous->is(tok::at);
 }
 

 
 void ContinuationIndenter::moveStateToNewBlock(LineState &State) {
   unsigned NestedBlockIndent = State.Stack.back().NestedBlockIndent;
   // ObjC block sometimes follow special indentation rules.
   unsigned NewIndent =
       NestedBlockIndent + (State.NextToken->is(TT_ObjCBlockLBrace)
                                ? Style.ObjCBlockIndentWidth
                                : Style.IndentWidth);
-  State.Stack.push_back(ParenState(NewIndent, State.Stack.back().LastSpace,
+  State.Stack.push_back(ParenState(State.NextToken, NewIndent,
+                                   State.Stack.back().LastSpace,
                                    /*AvoidBinPacking=*/true,
                                    /*NoLineBreak=*/false));
   State.Stack.back().NestedBlockIndent = NestedBlockIndent;
   State.Stack.back().BreakBeforeParameter = true;
 }
 
 static unsigned getLastLineEndColumn(StringRef Text, unsigned StartColumn,
                                      unsigned TabWidth,

lib/Format/UnwrappedLineFormatter.cpp

for (AnnotatedLine *Child : Tok->Children)
       markFinalized(Child->First);
   }
 }
 
 #ifndef NDEBUG
 static void printLineState(const LineState &State) {
   llvm::dbgs() << "State: ";
   for (const ParenState &P : State.Stack) {
-    llvm::dbgs() << P.Indent << "|" << P.LastSpace << "|" << P.NestedBlockIndent
-                 << " ";
+    llvm::dbgs() << (P.Tok ? P.Tok->TokenText : "F") << "|" << P.Indent << "|"
+                 << P.LastSpace << "|" << P.NestedBlockIndent << " ";
   }
   llvm::dbgs() << State.NextToken->TokenText << "\n";
 }
 #endif
 
 /// Base class for classes that format one \c AnnotatedLine.
 class LineFormatter {
 public:

unittests/Format/FormatTestProto.cpp

 }
 
 TEST_F(FormatTestProto, AcceptsOperatorAsKeyInOptions) {
   verifyFormat("option (MyProto.options) = {\n"
                "  bbbbbbbbb: <\n"
                "    ccccccccccccccccccccccc: <\n"
                "      operator: 1\n"
                "      operator: 2\n"
+               "      operator: 3\n"
                "      operator { key: value }\n"
                "    >\n"
                "  >\n"
                "};");
 }
 
 } // end namespace tooling
 } // end namespace clang

unittests/Format/FormatTestRawStrings.cpp

 )test",
             format(R"test(
 xxxxxxxaaaaax wwwwwww = _Verxrrrrrrrrr(PARSE_TEXT_PROTO(R"pb(
       Category: aaaaaaaaaaaaaaaaaaaaaaaaaa
 )pb"));
 )test", Style));
 }
 
+TEST_F(FormatTestRawStrings, KeepsRBraceFolloedByMoreLBracesOnSameLine) {
+  FormatStyle Style = getRawStringPbStyleWithColumns(80);
+
+  expect_eq(
+                    R"test(
+int f() {
+  if (1) {
+    TTTTTTTTTTTTTTTTTTTTT s = PARSE_TEXT_PROTO(R"pb(
+      ttttttttt {
+        ppppppppppppp {
+          [cccccccccc.pppppppppppppp.TTTTTTTTTTTTTTTTTTTT] { field_1: "123_1" }
+          [cccccccccc.pppppppppppppp.TTTTTTTTTTTTTTTTTTTT] { field_2: "123_2" }
+        }
+      }
+    )pb");
+  }
+}
+)test",
+            format(
+                    R"test(
+int f() {
+  if (1) {
+   TTTTTTTTTTTTTTTTTTTTT s = PARSE_TEXT_PROTO(R"pb(
+   ttttttttt {
+   ppppppppppppp {
+   [cccccccccc.pppppppppppppp.TTTTTTTTTTTTTTTTTTTT] { field_1: "123_1" }
+   [cccccccccc.pppppppppppppp.TTTTTTTTTTTTTTTTTTTT] { field_2: "123_2" }}}
+   )pb");
+  }
+}
+)test",
+                    Style));
+}
+
+
 } // end namespace
 } // end namespace format
 } // end namespace clang

unittests/Format/FormatTestTextProto.cpp

 }
 
 TEST_F(FormatTestTextProto, AcceptsOperatorAsKey) {
   verifyFormat("aaaaaaaaaaa: <\n"
                "  bbbbbbbbb: <\n"
                "    ccccccccccccccccccccccc: <\n"
                "      operator: 1\n"
                "      operator: 2\n"
+               "      operator: 3\n"
                "      operator { key: value }\n"
                "    >\n"
                "  >\n"
                ">");
 }
 
 TEST_F(FormatTestTextProto, BreaksConsecutiveStringLiterals) {
   verifyFormat("ala: \"str1\"\n"
verifyFormat("pppppppppp: {\n"
                "    begin: 24\n"
                "    end: 252\n"
                "    key: value\n"
                "    key: value\n"
                "  }\n"
                "}", Style);
 }
 
+TEST_F(FormatTestTextProto, BreaksAfterBraceFollowedByClosingBraceOnNextLine) {
+  FormatStyle Style = getGoogleStyle(FormatStyle::LK_TextProto);
+  Style.ColumnLimit = 60;
+  verifyFormat("keys: [\n"
+               "  data: { item: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' }\n"
+               "]");
+  verifyFormat("keys: <\n"
+               "  data: { item: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' }\n"
+               ">");
+}
+
 } // end namespace tooling
 } // end namespace clang