Better trade-off for excess characters vs. staying within the column limits.

[klimek]

Summary

When we break a long line like:
Column limit: 21

                    |
// foo foo foo foo foo foo foo foo foo foo foo foo

The local decision when to allow protruding vs. breaking can lead to this
outcome (2 excess characters, 2 breaks):

// foo foo foo foo foo
// foo foo foo foo foo
// foo foo

While strictly staying within the column limit leads to this strictly better
outcome (fully below the column limit, 2 breaks):

// foo foo foo foo
// foo foo foo foo
// foo foo foo foo

To get an optimal solution, we would need to consider all combinations of excess
characters vs. breaking for all lines, but that would lead to a significant
increase in the search space of the algorithm for little gain.

Instead, we blindly try both approches and·select the one that leads to the
overall lower penalty.

[krasimir]

lib/Format/ContinuationIndenter.cpp

1422

The problem here is that we're calling breakProtrudingToken 3 times more than we used to. Seems like such a waste.
@djasper: do you think this is fine?

1519

Why we return true here?

1773

Shouldn't we also be messing up something here in this patch?

[klimek]

lib/Format/ContinuationIndenter.cpp

1422

If we're in DryRun mode (all through the optimization phase) and we don't actually leave around excess characters, we call this exactly once per protruding token, so the vast majority of cases will see no change.

We'll always have an additional call in non-dry-run mode, but I think that completely doesn't matter, and we'll have a second call if we actually do leave around excess characters - note that this only happens when the excess character penalty is low enough, so it won't actually affect the normal LLVM / Google styles.

1519

Argh, because I first had inverted the concept and changed it later - thanks for catching, will fix.

1773

This just switches reflowing to false, which will keep the original line break. This basically figures out whether we will later be able to break. That might lead to a non-perfect solution later, as we might reflow ourselves into a situation where we have to leave excess characters around, which we could have avoided if we kept under the limit, but I do not think that matteres in an observable way.

[klimek]

Fix incorrect return value leading to unnecessary computation.

[krasimir]

unittests/Format/FormatTest.cpp

10007

Could you also add a test with line comments surrounded by stuff, like in:

int f() {
  int a = /* long block comment */ 42;
}

[klimek]

Add test.

lib/Format/ContinuationIndenter.h

private:
   /// \brief If \p Current is a raw string that is configured to be reformatted,
   /// return the style to be used.
   llvm::Optional<FormatStyle> getRawStringStyle(const FormatToken &Current,
                                                 const LineState &State);
 
   /// \brief If the current token sticks out over the end of the line, break
   /// it if possible.
   ///
-  /// \returns An extra penalty if a token was broken, otherwise 0.
+  /// \returns A pair (penalty, exceeded), where penalty is the extra penalty
+  /// when tokens are broken or lines exceed the column limit, and exceeded
+  /// indicates whether the algorithm purposefully left lines exceeding the
+  /// column limit.
   ///
   /// The returned penalty will cover the cost of the additional line breaks
   /// and column limit violation in all lines except for the last one. The
   /// penalty for the column limit violation in the last line (and in single
   /// line tokens) is handled in \c addNextStateToQueue.
-  unsigned breakProtrudingToken(const FormatToken &Current, LineState &State,
-                                bool AllowBreak, bool DryRun);
+  ///
+  /// \p Strict indicates whether reflowing is allowed to leave characters
+  /// protruding the column limit; if true, lines will be split strictly within
+  /// the column limit where possible; if false, words are allowed to protrude
+  /// over the column limit as long as the penalty is less than the penalty
+  /// of a break.
+  std::pair<unsigned, bool> breakProtrudingToken(const FormatToken &Current,
+                                                 LineState &State,
+                                                 bool AllowBreak, bool DryRun,
+                                                 bool Strict);
 
   /// \brief Returns the \c BreakableToken starting at \p Current, or nullptr
   /// if the current token cannot be broken.
   std::unique_ptr<BreakableToken>
   createBreakableToken(const FormatToken &Current, LineState &State,
                        bool AllowBreak);
 
   /// \brief Appends the next token to \p State and updates information

lib/Format/ContinuationIndenter.cpp

unsigned ContinuationIndenter::handleEndOfLine(const FormatToken &Current,
   if (RawStringStyle) {
     Penalty = reformatRawStringLiteral(Current, State, *RawStringStyle, DryRun);
   } else if (Current.IsMultiline && Current.isNot(TT_BlockComment)) {
     // Don't break multi-line tokens other than block comments and raw string
     // literals. Instead, just update the state.
     Penalty = addMultilineToken(Current, State);
   } else if (State.Line->Type != LT_ImportStatement) {
     // We generally don't break import statements.
-    Penalty = breakProtrudingToken(Current, State, AllowBreak, DryRun);
+    LineState OriginalState = State;
+
+    // Whether we force the reflowing algorithm to stay strictly within the
+    // column limit.
+    bool Strict = false;
+    // Whether the first non-strict attempt at reflowing did intentionally
+    // exceed the column limit.
+    bool Exceeded = false;
+    std::tie(Penalty, Exceeded) = breakProtrudingToken(
+        Current, State, AllowBreak, /*DryRun=*/true, Strict);
+    if (Exceeded) {
+      // If non-strict reflowing exceeds the column limit, try whether strict
+      // reflowing leads to an overall lower penalty.
+      LineState StrictState = OriginalState;
+      unsigned StrictPenalty =
+          breakProtrudingToken(Current, StrictState, AllowBreak,
+                               /*DryRun=*/true, /*Strict=*/true)
+              .first;
+      Strict = StrictPenalty <= Penalty;
+      if (Strict) {
+        Penalty = StrictPenalty;
+        State = StrictState;
+      }
+    }
+    if (!DryRun) {
+      // If we're not in dry-run mode, apply the changes with the decision on
+      // strictness made above.
+      breakProtrudingToken(Current, OriginalState, AllowBreak, /*DryRun=*/false,
+                           Strict);
+    }
   }
   if (State.Column > getColumnLimit(State)) {
     unsigned ExcessCharacters = State.Column - getColumnLimit(State);
     Penalty += Style.PenaltyExcessCharacter * ExcessCharacters;
   }
   return Penalty;
 }
 
if (!Style.ReflowComments ||
       return nullptr;
     return llvm::make_unique<BreakableLineCommentSection>(
         Current, StartColumn, Current.OriginalColumn, !Current.Previous,
         /*InPPDirective=*/false, Encoding, Style);
   }
   return nullptr;
 }
 
-unsigned ContinuationIndenter::breakProtrudingToken(const FormatToken &Current,
-                                                    LineState &State,
-                                                    bool AllowBreak,
-                                                    bool DryRun) {
+std::pair<unsigned, bool>
+ContinuationIndenter::breakProtrudingToken(const FormatToken &Current,
+                                           LineState &State, bool AllowBreak,
+                                           bool DryRun, bool Strict) {
   std::unique_ptr<const BreakableToken> Token =
       createBreakableToken(Current, State, AllowBreak);
   if (!Token)
-    return 0;
+    return {0, false};
   assert(Token->getLineCount() > 0);
   unsigned ColumnLimit = getColumnLimit(State);
   if (Current.is(TT_LineComment)) {
     // We don't insert backslashes when breaking line comments.
     ColumnLimit = Style.ColumnLimit;
   }
   if (Current.UnbreakableTailLength >= ColumnLimit)
-    return 0;
+    return {0, false};
   // ColumnWidth was already accounted into State.Column before calling
   // breakProtrudingToken.
   unsigned StartColumn = State.Column - Current.ColumnWidth;
   unsigned NewBreakPenalty = Current.isStringLiteral()
                                  ? Style.PenaltyBreakString
                                  : Style.PenaltyBreakComment;
+  // Stores whether we intentionally decide to let a line exceed the column
+  // limit.
+  bool Exceeded = false;
   // Stores whether we introduce a break anywhere in the token.
   bool BreakInserted = Token->introducesBreakBeforeToken();
   // Store whether we inserted a new line break at the end of the previous
   // logical line.
   bool NewBreakBefore = false;
   // We use a conservative reflowing strategy. Reflow starts after a line is
   // broken or the corresponding whitespace compressed. Reflow ends as soon as a
   // line that doesn't get reflown with the previous line is reached.
while (ContentStartColumn + RemainingTokenColumns > ColumnLimit) {
         DEBUG(llvm::dbgs() << "    ContentStartColumn: " << ContentStartColumn
                            << "\n");
         DEBUG(llvm::dbgs() << "    ToNextSplit: " << ToNextSplitColumns << "\n");
         // If the whitespace compression makes us fit, continue on the current
         // line.
         bool ContinueOnLine =
             ContentStartColumn + ToNextSplitColumns <= ColumnLimit;
         unsigned ExcessCharactersPenalty = 0;
-        if (!ContinueOnLine) {
+        if (!ContinueOnLine && !Strict) {
           // Similarly, if the excess characters' penalty is lower than the
           // penalty of introducing a new break, continue on the current line.
           ExcessCharactersPenalty =
               (ContentStartColumn + ToNextSplitColumns - ColumnLimit) *
               Style.PenaltyExcessCharacter;
           DEBUG(llvm::dbgs()
                 << "    Penalty excess: " << ExcessCharactersPenalty
                 << "\n            break : " << NewBreakPenalty << "\n");
-          if (ExcessCharactersPenalty < NewBreakPenalty)
+          if (ExcessCharactersPenalty < NewBreakPenalty) {
+            Exceeded = true;
             ContinueOnLine = true;
           }
+        }
         if (ContinueOnLine) {
           DEBUG(llvm::dbgs() << "    Continuing on line...\n");
           // The current line fits after compressing the whitespace - reflow
           // the next line into it if possible.
           TryReflow = true;
           if (!DryRun)
             Token->compressWhitespace(LineIndex, TailOffset, Split,
                                       Whitespaces);
if (LineIndex + 1 != EndIndex) {
                   NextLineIndex, TailOffset, Split.first, ContentStartColumn);
               if (ContentStartColumn + ToSplitColumns > ColumnLimit) {
                 DEBUG(llvm::dbgs() << "    Next split protrudes, need: "
                                    << (ContentStartColumn + ToSplitColumns)
                                    << ", space: " << ColumnLimit);
                 unsigned ExcessCharactersPenalty =
                     (ContentStartColumn + ToSplitColumns - ColumnLimit) *
                     Style.PenaltyExcessCharacter;
                 if (NewBreakPenalty < ExcessCharactersPenalty) {
                   Reflow = false;
                 }
               }
             }
           }
         } else {
           DEBUG(llvm::dbgs() << "not found.\n");
         }
if (BreakInserted) {
     if (Current.is(TT_BlockComment))
       State.NoContinuation = true;
 
     State.Stack.back().LastSpace = StartColumn;
   }
 
   Token->updateNextToken(State);
 
-  return Penalty;
+  return {Penalty, Exceeded};
 }
 
 unsigned ContinuationIndenter::getColumnLimit(const LineState &State) const {
   // In preprocessor directives reserve two chars for trailing " \"
   return Style.ColumnLimit - (State.Line->InPPDirective ? 2 : 0);
 }
 
 bool ContinuationIndenter::nextIsMultilineString(const LineState &State) {

unittests/Format/FormatTest.cpp

EXPECT_EQ("int a; // first line\n"
             format("int a; // first line\n"
                    "       // second line\n"
                    "       // third line",
                    Style));
 
   Style.PenaltyExcessCharacter = 90;
   verifyFormat("int a; // the comment", Style);
   EXPECT_EQ("int a; // the comment\n"
-            "       // aa",
-            format("int a; // the comment aa", Style));
+            "       // aaa",
+            format("int a; // the comment aaa", Style));
   EXPECT_EQ("int a; /* first line\n"
             "        * second line\n"
             "        * third line\n"
             "        */",
             format("int a; /* first line\n"
                    "        * second line\n"
                    "        * third line\n"
                    "        */",
EXPECT_EQ("int a; /* first line\n"
             "        * second line\n"
             "        * third line\n"
             "        */",
             format("int a; /* first line second line third line"
                    "\n*/",
                    Style));
 
   EXPECT_EQ("// foo bar baz bazfoo\n"
-            "// foo bar\n",
+            "// foo bar foo bar\n",
             format("// foo bar baz bazfoo\n"
-                   "// foo            bar\n",
+                   "// foo bar foo           bar\n",
                    Style));
   EXPECT_EQ("// foo bar baz bazfoo\n"
-            "// foo bar\n",
+            "// foo bar foo bar\n",
             format("// foo bar baz      bazfoo\n"
-                   "// foo            bar\n",
+                   "// foo            bar foo bar\n",
                    Style));
 
   // FIXME: Optimally, we'd keep bazfoo on the first line and reflow bar to the
   // next one.
   EXPECT_EQ("// foo bar baz bazfoo\n"
             "// bar foo bar\n",
             format("// foo bar baz      bazfoo bar\n"
                    "// foo            bar\n",
TEST_F(FormatTest, OptimizeBreakPenaltyVsExcess) {
 
   EXPECT_EQ("// foo bar baz bazfoo\n"
             "// foo bar baz bazfoo\n"
             "// bar foo bar\n",
             format("// foo bar baz      bazfoo\n"
                    "// foo bar baz      bazfoo bar\n"
                    "// foo           bar\n",
                    Style));
+
+  // Make sure we do not keep protruding characters if strict mode reflow is
+  // cheaper than keeping protruding characters.
+  Style.ColumnLimit = 21;
+  EXPECT_EQ("// foo foo foo foo\n"
+            "// foo foo foo foo\n"
+            "// foo foo foo foo\n",
+            format("// foo foo foo foo foo foo foo foo foo foo foo foo\n",
+                           Style));
 }
 
 #define EXPECT_ALL_STYLES_EQUAL(Styles)                                        \
   for (size_t i = 1; i < Styles.size(); ++i)                                   \
   EXPECT_EQ(Styles[0], Styles[i]) << "Style #" << i << " of " << Styles.size() \
                                   << " differs from Style #0"
 
 TEST_F(FormatTest, GetsPredefinedStyleByName) {