Remove internal recursion for RenderBlockFlow and RenderMultiColumnBlock layout

Remove internal recursion for RenderBlockFlow and RenderMultiColumnBlock layout

The layout routine for pagination and multicolumn support is changed to a
non-recursive algorithm.  The patch also removes a virtual function in the
process and reduces the binary size by 32 bytes.  This is a non-functional
change, but I have observed a 4%-6% performance improvement in some of the
flexbox tests in Performance/Layout.

BUG=331879
R=eseidel, esprehn

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=166076

[atreat, 2014-01-24 22:13:22]

Please have a look

[esprehn, 2014-01-24 22:19:16]

Can you explain what this patch is doing? Why do you call layout repeatedly?
"tryLayout" also looks sketchy.

https://codereview.chromium.org/147233002/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderBlockFlow.cpp (right):

https://codereview.chromium.org/147233002/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderBlockFlow.cpp:191: bool
RenderBlockFlow::shouldRelayoutForPagination(LayoutUnit& pageLogicalHeight,
LayoutUnit layoutOverflowLogicalBottom)
Add const? should methods usually don't have side effects.

https://codereview.chromium.org/147233002/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderBlockFlow.cpp:256: success =
tryLayoutBlockFlow(relayoutChildren, pageLogicalHeight, layoutScope);
Woah, this is really scary, why are you calling it repeatedly?

[atreat, 2014-01-24 22:31:43]

On 2014/01/24 22:19:16, esprehn wrote:
> Can you explain what this patch is doing? Why do you call layout repeatedly?
> "tryLayout" also looks sketchy.

Previously, this method was called recursively for multiple passes by the code
that handles columns and pagination.

I have not changed that behavior.  You can see this in
RenderMultiColumnBlock::relayoutForPagination and the associated
comment.

        // Column heights may change here because of balancing. We may have to
do multiple layout
        // passes, depending on how the contents is fitted to the changed column
heights. In most
        // cases, laying out again twice or even just once will suffice.
Sometimes we need more
        // passes than that, though, but the number of retries should not exceed
the number of
        // columns, unless we have a bug.

Notice the while loop in this method already.  What I have done is moved this
while loop up and got rid of the
recursion.  Now it is just more explicit.  I think the fact that it was not
obvious that there were multiple passes before
while with my patch it becomes more obvious is a feature.  This shows that
recursion here makes things harder to understand.

>
https://codereview.chromium.org/147233002/diff/1/Source/core/rendering/Render...
> File Source/core/rendering/RenderBlockFlow.cpp (right):
> 
>
https://codereview.chromium.org/147233002/diff/1/Source/core/rendering/Render...
> Source/core/rendering/RenderBlockFlow.cpp:191: bool
> RenderBlockFlow::shouldRelayoutForPagination(LayoutUnit& pageLogicalHeight,
> LayoutUnit layoutOverflowLogicalBottom)
> Add const? should methods usually don't have side effects.

I think I can do this now. For shouldRelayoutForMultiColumnBlock it is modifying
a member variable m_inBalancingPass which I
could make mutable I guess.  I agree in general, 'should' methods are usually
const and for good reason.

>
https://codereview.chromium.org/147233002/diff/1/Source/core/rendering/Render...
> Source/core/rendering/RenderBlockFlow.cpp:256: success =
> tryLayoutBlockFlow(relayoutChildren, pageLogicalHeight, layoutScope);
> Woah, this is really scary, why are you calling it repeatedly?

Again, this is being called repeatedly right now.  I've just made it more
obvious by getting rid of the recursion.  This exemplifies
a major motivating factor for getting rid of this recursion code.  It makes it
hard to understand what is going on and hard to debug.

Cheers,
Adam

[atreat, 2014-01-27 19:41:02]

On 2014/01/24 22:31:43, atreat wrote:
> On 2014/01/24 22:19:16, esprehn wrote:

Ready for another round of review.  I've made the 'shouldRelayout*' methods
const and added a comment to clearly indicate what is going on with the multiple
passes.  Please have a look.

[esprehn, 2014-01-27 19:45:51]

https://codereview.chromium.org/147233002/diff/80001/Source/core/rendering/Re...
File Source/core/rendering/RenderBlockFlow.cpp (right):

https://codereview.chromium.org/147233002/diff/80001/Source/core/rendering/Re...
Source/core/rendering/RenderBlockFlow.cpp:260: success =
tryLayoutBlockFlow(relayoutChildren, pageLogicalHeight, layoutScope);
I'm not a fan of the success and try pattern here. It didn't really fail if it
returns false, it's just done with the multiple pages.

https://codereview.chromium.org/147233002/diff/80001/Source/core/rendering/Re...
Source/core/rendering/RenderBlockFlow.cpp:263: inline bool
RenderBlockFlow::tryLayoutBlockFlow(bool relayoutChildren, LayoutUnit
&pageLogicalHeight, SubtreeLayoutScope& layoutScope)
Do we need to rename this? It's not really "trying" in the "try to get a block"
sense.

I'd suggest:

bool done = false;
while (!done)
  done = layoutBLockFlow(...);

[atreat, 2014-01-27 20:24:06]

On 2014/01/27 19:45:51, esprehn wrote:
> I'd suggest:
> 
> bool done = false;
> while (!done)
>   done = layoutBLockFlow(...);

Updated to remove the 'try' naming scheme in favor of loop until 'done'.

[atreat, 2014-01-28 16:37:14]

On 2014/01/27 20:24:06, atreat wrote:
> On 2014/01/27 19:45:51, esprehn wrote:
> > I'd suggest:
> > 
> > bool done = false;
> > while (!done)
> >   done = layoutBLockFlow(...);
> 
> Updated to remove the 'try' naming scheme in favor of loop until 'done'.

Any more feedback on this one?

[esprehn, 2014-01-29 00:39:54]

lgtm, ojan knows flex box and the inner bits of layout better and might have a
comment, but this seems fine to me.

[ojan, 2014-01-29 01:58:31]

On 2014/01/29 00:39:54, esprehn wrote:
> lgtm, ojan knows flex box and the inner bits of layout better and might have a
> comment, but this seems fine to me.

I have nothing to add. lgtm as well.

[commit-bot: I haz the power, 2014-01-29 15:29:59]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/adam.treat@samsung.com/147233002/120001

[commit-bot: I haz the power, 2014-01-29 15:30:07]

Failed to apply patch for Source/core/rendering/RenderBlockFlow.cpp:
While running patch -p1 --forward --force --no-backup-if-mismatch;
  patching file Source/core/rendering/RenderBlockFlow.cpp
  Hunk #2 succeeded at 220 with fuzz 1 (offset 32 lines).
  Hunk #3 succeeded at 269 (offset 32 lines).
  Hunk #4 succeeded at 280 (offset 32 lines).
  Hunk #5 succeeded at 334 (offset 32 lines).
  Hunk #6 FAILED at 327.
  Hunk #7 succeeded at 411 (offset 32 lines).
  Hunk #8 succeeded at 432 (offset 32 lines).
  1 out of 8 hunks FAILED -- saving rejects to file
Source/core/rendering/RenderBlockFlow.cpp.rej

Patch:       Source/core/rendering/RenderBlockFlow.cpp
Index: Source/core/rendering/RenderBlockFlow.cpp
diff --git a/Source/core/rendering/RenderBlockFlow.cpp
b/Source/core/rendering/RenderBlockFlow.cpp
index
840108dd5a2c728bf4f935408859f787da4632f2..0594de0b865d2ea07c0a35852adbe94370f8a949
100644
--- a/Source/core/rendering/RenderBlockFlow.cpp
+++ b/Source/core/rendering/RenderBlockFlow.cpp
@@ -38,6 +38,7 @@
 #include "core/rendering/LayoutRectRecorder.h"
 #include "core/rendering/LayoutRepainter.h"
 #include "core/rendering/RenderLayer.h"
+#include "core/rendering/RenderMultiColumnBlock.h"
 #include "core/rendering/RenderNamedFlowFragment.h"
 #include "core/rendering/RenderNamedFlowThread.h"
 #include "core/rendering/RenderText.h"
@@ -187,57 +188,45 @@ void RenderBlockFlow::willBeDestroyed()
     RenderBlock::willBeDestroyed();
 }
 
-bool RenderBlockFlow::relayoutForPagination(bool hasSpecifiedPageLogicalHeight,
LayoutUnit pageLogicalHeight, LayoutStateMaintainer& statePusher)
+bool RenderBlockFlow::shouldRelayoutForPagination(LayoutUnit&
pageLogicalHeight, LayoutUnit layoutOverflowLogicalBottom) const
 {
-    if (!hasColumns())
-        return false;
-
-    OwnPtr<RenderOverflow> savedOverflow = m_overflow.release();
-    if (childrenInline())
-        addOverflowFromInlineChildren();
-    else
-        addOverflowFromBlockChildren();
-    LayoutUnit layoutOverflowLogicalBottom = (isHorizontalWritingMode() ?
layoutOverflowRect().maxY() : layoutOverflowRect().maxX()) - borderBefore() -
paddingBefore();
-
     // FIXME: We don't balance properly at all in the presence of forced page
breaks. We need to understand what
     // the distance between forced page breaks is so that we can avoid making
the minimum column height too tall.
     ColumnInfo* colInfo = columnInfo();
-    if (!hasSpecifiedPageLogicalHeight) {
-        LayoutUnit columnHeight = pageLogicalHeight;
-        int minColumnCount = colInfo->forcedBreaks() + 1;
-        int desiredColumnCount = colInfo->desiredColumnCount();
-        if (minColumnCount >= desiredColumnCount) {
-            // The forced page breaks are in control of the balancing. Just set
the column height to the
-            // maximum page break distance.
-            if (!pageLogicalHeight) {
-                LayoutUnit distanceBetweenBreaks =
max<LayoutUnit>(colInfo->maximumDistanceBetweenForcedBreaks(),
-                    view()->layoutState()->pageLogicalOffset(this,
borderBefore() + paddingBefore() + layoutOverflowLogicalBottom) -
colInfo->forcedBreakOffset());
-                columnHeight = max(colInfo->minimumColumnHeight(),
distanceBetweenBreaks);
-            }
-        } else if (layoutOverflowLogicalBottom >
boundedMultiply(pageLogicalHeight, desiredColumnCount)) {
-            // Now that we know the intrinsic height of the columns, we have to
rebalance them.
-            columnHeight = max<LayoutUnit>(colInfo->minimumColumnHeight(),
ceilf((float)layoutOverflowLogicalBottom / desiredColumnCount));
+    LayoutUnit columnHeight = pageLogicalHeight;
+    const int minColumnCount = colInfo->forcedBreaks() + 1;
+    const int desiredColumnCount = colInfo->desiredColumnCount();
+    if (minColumnCount >= desiredColumnCount) {
+        // The forced page breaks are in control of the balancing. Just set the
column height to the
+        // maximum page break distance.
+        if (!pageLogicalHeight) {
+            LayoutUnit distanceBetweenBreaks =
max<LayoutUnit>(colInfo->maximumDistanceBetweenForcedBreaks(),
+                view()->layoutState()->pageLogicalOffset(this, borderBefore() +
paddingBefore() + layoutOverflowLogicalBottom) - colInfo->forcedBreakOffset());
+            columnHeight = max(colInfo->minimumColumnHeight(),
distanceBetweenBreaks);
         }
+    } else if (layoutOverflowLogicalBottom > boundedMultiply(pageLogicalHeight,
desiredColumnCount)) {
+        // Now that we know the intrinsic height of the columns, we have to
rebalance them.
+        columnHeight = max<LayoutUnit>(colInfo->minimumColumnHeight(),
ceilf((float)layoutOverflowLogicalBottom / desiredColumnCount));
+    }
 
-        if (columnHeight && columnHeight != pageLogicalHeight) {
-            statePusher.pop();
-            setEverHadLayout(true);
-            layoutBlockFlow(false, columnHeight);
-            return true;
-        }
+    if (columnHeight && columnHeight != pageLogicalHeight) {
+        pageLogicalHeight = columnHeight;
+        return true;
     }
 
+    return false;
+}
+
+void RenderBlockFlow::setColumnCountAndHeight(unsigned count, LayoutUnit
pageLogicalHeight)
+{
+    ColumnInfo* colInfo = columnInfo();
     if (pageLogicalHeight)
-       
colInfo->setColumnCountAndHeight(ceilf((float)layoutOverflowLogicalBottom /
pageLogicalHeight), pageLogicalHeight);
+        colInfo->setColumnCountAndHeight(count, pageLogicalHeight);
 
     if (columnCount(colInfo)) {
         setLogicalHeight(borderBefore() + paddingBefore() +
colInfo->columnHeight() + borderAfter() + paddingAfter() +
scrollbarLogicalHeight());
         m_overflow.clear();
-    } else {
-        m_overflow = savedOverflow.release();
     }
-
-    return false;
 }
 
 bool RenderBlockFlow::isSelfCollapsingBlock() const
@@ -248,11 +237,6 @@ bool RenderBlockFlow::isSelfCollapsingBlock() const
 
 void RenderBlockFlow::layoutBlock(bool relayoutChildren)
 {
-    layoutBlockFlow(relayoutChildren);
-}
-
-inline void RenderBlockFlow::layoutBlockFlow(bool relayoutChildren, LayoutUnit
pageLogicalHeight)
-{
     ASSERT(needsLayout());
     ASSERT(isInlineBlockOrInlineTable() || !isInline());
 
@@ -264,6 +248,20 @@ inline void RenderBlockFlow::layoutBlockFlow(bool
relayoutChildren, LayoutUnit p
     if (!relayoutChildren && simplifiedLayout())
         return;
 
+    SubtreeLayoutScope layoutScope(this);
+
+    // Multiple passes might be required for column and pagination based layout
+    // In the case of the old column code the number of passes will only be two
+    // however, in the newer column code the number of passes could equal the
+    // number of columns.
+    bool done = false;
+    LayoutUnit pageLogicalHeight = 0;
+    while (!done)
+        done = layoutBlockFlow(relayoutChildren, pageLogicalHeight,
layoutScope);
+}
+
+inline bool RenderBlockFlow::layoutBlockFlow(bool relayoutChildren, LayoutUnit
&pageLogicalHeight, SubtreeLayoutScope& layoutScope)
+{
     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
 
     if (updateLogicalWidthAndColumnWidth())
@@ -304,8 +302,6 @@ inline void RenderBlockFlow::layoutBlockFlow(bool
relayoutChildren, LayoutUnit p
         setPaginationStrut(0);
     }
 
-    SubtreeLayoutScope layoutScope(this);
-
     LayoutUnit beforeEdge = borderBefore() + paddingBefore();
     LayoutUnit afterEdge = borderAfter() + paddingAfter() +
scrollbarLogicalHeight();
     LayoutUnit previousHeight = logicalHeight();
@@ -331,16 +327,41 @@ inline void RenderBlockFlow::layoutBlockFlow(bool
relayoutChildren, LayoutUnit p
 
     if (frameView()->partialLayout().isStopping()) {
         statePusher.pop();
-        return;
+        return true;
     }
 
     // Expand our intrinsic height to encompass floats.
     if (lowestFloatLogicalBottom() > (logicalHeight() - afterEdge) &&
expandsToEncloseOverhangingFloats())
         setLogicalHeight(lowestFloatLogicalBottom() + afterEdge);
 
-    if (relayoutForPagination(hasSpecifiedPageLogicalHeight, pageLogicalHeight,
statePusher) || relayoutToAvoidWidows(statePusher)) {
-        ASSERT(!shouldBreakAtLineToAvoidWidow());
-        return;
+    if (isRenderMultiColumnBlock()) {
+        if (toRenderMultiColumnBlock(this)->shouldRelayoutMultiColumnBlock()) {
+            setChildNeedsLayout(MarkOnlyThis);
+            statePusher.pop();
+            return false;
+        }
+    } else if (hasColumns()) {
+        OwnPtr<RenderOverflow> savedOverflow = m_overflow.release();
+        if (childrenInline())
+            addOverflowFromInlineChildren();
+        else
+            addOverflowFromBlockChildren();
+        LayoutUnit layoutOverflowLogicalBottom = (isHorizontalWritingMode() ?
layoutOverflowRect().maxY() : layoutOverflowRect().maxX()) - borderBefore() -
paddingBefore();
+        m_overflow = savedOverflow.release();
+
+        if (!hasSpecifiedPageLogicalHeight &&
shouldRelayoutForPagination(pageLogicalHeight, layoutOverflowLogicalBottom)) {
+            statePusher.pop();
+            setEverHadLayout(true);
+            return false;
+        }
+
+        setColumnCountAndHeight(ceilf((float)layoutOverflowLogicalBottom /
pageLogicalHeight), pageLogicalHeight);
+    }
+
+    if (shouldBreakAtLineToAvoidWidow()) {
+        statePusher.pop();
+        setEverHadLayout(true);
+        return false;
     }
 
     // Calculate our new height.
@@ -383,7 +404,7 @@ inline void RenderBlockFlow::layoutBlockFlow(bool
relayoutChildren, LayoutUnit p
     fitBorderToLinesIfNeeded();
 
     if (frameView()->partialLayout().isStopping())
-        return;
+        return true;
 
     if (renderView->layoutState()->m_pageLogicalHeight)
         setPageLogicalOffset(renderView->layoutState()->pageLogicalOffset(this,
logicalTop()));
@@ -404,6 +425,7 @@ inline void RenderBlockFlow::layoutBlockFlow(bool
relayoutChildren, LayoutUnit p
     }
 
     clearNeedsLayout();
+    return true;
 }
 
 void RenderBlockFlow::layoutBlockChild(Rende…
(message too large)

[commit-bot: I haz the power, 2014-01-29 15:31:02]

CQ bit was unchecked on CL. Ignoring.

[commit-bot: I haz the power, 2014-01-29 15:48:32]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/adam.treat@samsung.com/147233002/140001

[commit-bot: I haz the power, 2014-01-30 02:10:46]

Change committed as 166076

[commit-bot: I haz the power, 2014-01-30 02:11:58]

CQ bit was unchecked on CL. Ignoring.