Support multiple fragmentainer groups per ColumnBalancer run.

third_party/WebKit/Source/core/layout/ColumnBalancer.cpp

Index: third_party/WebKit/Source/core/layout/ColumnBalancer.cpp
diff --git a/third_party/WebKit/Source/core/layout/ColumnBalancer.cpp b/third_party/WebKit/Source/core/layout/ColumnBalancer.cpp
index 45607bdde8b166eb4b9092b18e8d059939e91489..1ba071994ee615703c926bdedf4bb874cca748d3 100644
--- a/third_party/WebKit/Source/core/layout/ColumnBalancer.cpp
+++ b/third_party/WebKit/Source/core/layout/ColumnBalancer.cpp
@@ -10,15 +10,17 @@
 
 namespace blink {
 
-ColumnBalancer::ColumnBalancer(const MultiColumnFragmentainerGroup& group)
-    : m_group(group)
+ColumnBalancer::ColumnBalancer(const LayoutMultiColumnSet& columnSet, LayoutUnit logicalTopInFlowThread, LayoutUnit logicalBottomInFlowThread)
+    : m_columnSet(columnSet)
+    , m_logicalTopInFlowThread(logicalTopInFlowThread)
+    , m_logicalBottomInFlowThread(logicalBottomInFlowThread)
     , m_previousBreakAfterValue(BreakAuto)
 {
 }
 
 void ColumnBalancer::traverse()
 {
-    traverseSubtree(*m_group.columnSet().flowThread());
+    traverseSubtree(*columnSet().flowThread());
     ASSERT(!flowThreadOffset());
 }
 
@@ -28,15 +30,15 @@ void ColumnBalancer::traverseSubtree(const LayoutBox& box)
         // Look for breaks between lines.
         for (const RootInlineBox* line = toLayoutBlockFlow(box).firstRootBox(); line; line = line->nextRootBox()) {
             LayoutUnit lineTopInFlowThread = m_flowThreadOffset + line->lineTopWithLeading();
-            if (lineTopInFlowThread < group().logicalTopInFlowThread())
+            if (lineTopInFlowThread < logicalTopInFlowThread())
                 continue;
-            if (lineTopInFlowThread >= group().logicalBottomInFlowThread())
+            if (lineTopInFlowThread >= logicalBottomInFlowThread())
                 break;
             examineLine(*line);
         }
     }
 
-    const LayoutFlowThread* flowThread = group().columnSet().flowThread();
+    const LayoutFlowThread* flowThread = columnSet().flowThread();
     bool isHorizontalWritingMode = flowThread->isHorizontalWritingMode();
 
     // Look for breaks between and inside block-level children. Even if this is a block flow with
@@ -47,13 +49,13 @@ void ColumnBalancer::traverseSubtree(const LayoutBox& box)
         const LayoutBox& childBox = toLayoutBox(*child);
         LayoutRect overflowRect = childBox.layoutOverflowRect();
         LayoutUnit childLogicalBottomWithOverflow = childBox.logicalTop() + (isHorizontalWritingMode ? overflowRect.maxY() : overflowRect.maxX());
-        if (m_flowThreadOffset + childLogicalBottomWithOverflow <= group().logicalTopInFlowThread()) {
-            // This child is fully above the fragmentainer group we're examining.
+        if (m_flowThreadOffset + childLogicalBottomWithOverflow <= logicalTopInFlowThread()) {
+            // This child is fully above the flow thread portion we're examining.
             continue;
         }
         LayoutUnit childLogicalTopWithOverflow = childBox.logicalTop() + (isHorizontalWritingMode ? overflowRect.y() : overflowRect.x());
-        if (m_flowThreadOffset + childLogicalTopWithOverflow >= group().logicalBottomInFlowThread()) {
-            // This child is fully below the fragmentainer group we're examining. We cannot just
+        if (m_flowThreadOffset + childLogicalTopWithOverflow >= logicalBottomInFlowThread()) {
+            // This child is fully below the flow thread portion we're examining. We cannot just
             // stop here, though, thanks to negative margins. So keep looking.
             continue;
         }
@@ -77,10 +79,10 @@ void ColumnBalancer::traverseSubtree(const LayoutBox& box)
     }
 }
 
-InitialColumnHeightFinder::InitialColumnHeightFinder(const MultiColumnFragmentainerGroup& group)
-    : ColumnBalancer(group)
+InitialColumnHeightFinder::InitialColumnHeightFinder(const LayoutMultiColumnSet& columnSet, LayoutUnit logicalTopInFlowThread, LayoutUnit logicalBottomInFlowThread)
+    : ColumnBalancer(columnSet, logicalTopInFlowThread, logicalBottomInFlowThread)
 {
-    m_shortestStruts.resize(group.columnSet().usedColumnCount());
+    m_shortestStruts.resize(columnSet.usedColumnCount());
     for (auto& strut : m_shortestStruts)
         strut = LayoutUnit::max();
     traverse();
@@ -93,7 +95,7 @@ InitialColumnHeightFinder::InitialColumnHeightFinder(const MultiColumnFragmentai
 LayoutUnit InitialColumnHeightFinder::initialMinimalBalancedHeight() const
 {
     unsigned index = contentRunIndexWithTallestColumns();
-    LayoutUnit startOffset = index > 0 ? m_contentRuns[index - 1].breakOffset() : group().logicalTopInFlowThread();
+    LayoutUnit startOffset = index > 0 ? m_contentRuns[index - 1].breakOffset() : logicalTopInFlowThread();
     return m_contentRuns[index].columnLogicalHeight(startOffset);
 }
 
@@ -157,11 +159,10 @@ void InitialColumnHeightFinder::examineLine(const RootInlineBox& line)
 
 void InitialColumnHeightFinder::recordStrutBeforeOffset(LayoutUnit offsetInFlowThread, LayoutUnit strut)
 {
-    const LayoutMultiColumnSet& columnSet = group().columnSet();
-    ASSERT(columnSet.usedColumnCount() >= 1);
-    unsigned columnCount = columnSet.usedColumnCount();
+    ASSERT(columnSet().usedColumnCount() >= 1);
+    unsigned columnCount = columnSet().usedColumnCount();
     ASSERT(m_shortestStruts.size() == columnCount);
-    unsigned index = group().columnIndexAtOffset(offsetInFlowThread - strut, MultiColumnFragmentainerGroup::AssumeNewColumns);
+    unsigned index = groupAtOffset(offsetInFlowThread).columnIndexAtOffset(offsetInFlowThread - strut, MultiColumnFragmentainerGroup::AssumeNewColumns);
     if (index >= columnCount)
         return;
     m_shortestStruts[index] = std::min(m_shortestStruts[index], strut);
@@ -169,8 +170,8 @@ void InitialColumnHeightFinder::recordStrutBeforeOffset(LayoutUnit offsetInFlowT
 
 LayoutUnit InitialColumnHeightFinder::spaceUsedByStrutsAt(LayoutUnit offsetInFlowThread) const
 {
-    unsigned stopBeforeColumn = group().columnIndexAtOffset(offsetInFlowThread, MultiColumnFragmentainerGroup::AssumeNewColumns) + 1;
-    stopBeforeColumn = std::min(stopBeforeColumn, group().columnSet().usedColumnCount());
+    unsigned stopBeforeColumn = groupAtOffset(offsetInFlowThread).columnIndexAtOffset(offsetInFlowThread, MultiColumnFragmentainerGroup::AssumeNewColumns) + 1;
+    stopBeforeColumn = std::min(stopBeforeColumn, columnSet().usedColumnCount());
     ASSERT(stopBeforeColumn <= m_shortestStruts.size());
     LayoutUnit totalStrutSpace;
     for (unsigned i = 0; i < stopBeforeColumn; i++) {
@@ -187,7 +188,7 @@ void InitialColumnHeightFinder::addContentRun(LayoutUnit endOffsetInFlowThread)
         return;
     // Append another item as long as we haven't exceeded used column count. What ends up in the
     // overflow area shouldn't affect column balancing.
-    if (m_contentRuns.size() < group().columnSet().usedColumnCount())
+    if (m_contentRuns.size() < columnSet().usedColumnCount())
         m_contentRuns.append(ContentRun(endOffsetInFlowThread));
 }
 
@@ -195,7 +196,7 @@ unsigned InitialColumnHeightFinder::contentRunIndexWithTallestColumns() const
 {
     unsigned indexWithLargestHeight = 0;
     LayoutUnit largestHeight;
-    LayoutUnit previousOffset = group().logicalTopInFlowThread();
+    LayoutUnit previousOffset = logicalTopInFlowThread();
     size_t runCount = m_contentRuns.size();
     ASSERT(runCount);
     for (size_t i = 0; i < runCount; i++) {
@@ -212,9 +213,9 @@ unsigned InitialColumnHeightFinder::contentRunIndexWithTallestColumns() const
 
 void InitialColumnHeightFinder::distributeImplicitBreaks()
 {
-    // Insert a final content run to encompass all content. This will include overflow if this is
-    // the last group in the multicol container.
-    addContentRun(group().logicalBottomInFlowThread());
+    // Insert a final content run to encompass all content. This will include overflow if we're at
+    // the end of the multicol container.
+    addContentRun(logicalBottomInFlowThread());
     unsigned columnCount = m_contentRuns.size();
 
     // If there is room for more breaks (to reach the used value of column-count), imagine that we
@@ -223,15 +224,15 @@ void InitialColumnHeightFinder::distributeImplicitBreaks()
     // column count by one and shrink its columns' height. Repeat until we have the desired total
     // number of breaks. The largest column height among the runs will then be the initial column
     // height for the balancer to use.
-    while (columnCount < group().columnSet().usedColumnCount()) {
+    while (columnCount < columnSet().usedColumnCount()) {
         unsigned index = contentRunIndexWithTallestColumns();
         m_contentRuns[index].assumeAnotherImplicitBreak();
         columnCount++;
     }
 }
 
-MinimumSpaceShortageFinder::MinimumSpaceShortageFinder(const MultiColumnFragmentainerGroup& group)
-    : ColumnBalancer(group)
+MinimumSpaceShortageFinder::MinimumSpaceShortageFinder(const LayoutMultiColumnSet& columnSet, LayoutUnit logicalTopInFlowThread, LayoutUnit logicalBottomInFlowThread)
+    : ColumnBalancer(columnSet, logicalTopInFlowThread, logicalBottomInFlowThread)
     , m_minimumSpaceShortage(LayoutUnit::max())
     , m_pendingStrut(LayoutUnit::min())
     , m_forcedBreaksCount(0)
@@ -269,14 +270,15 @@ void MinimumSpaceShortageFinder::examineBoxAfterEntering(const LayoutBox& box)
     if (breakability != LayoutBox::ForbidBreaks) {
         // See if this breakable box crosses column boundaries.
         LayoutUnit bottomInFlowThread = flowThreadOffset() + box.logicalHeight();
+        const MultiColumnFragmentainerGroup& group = groupAtOffset(flowThreadOffset());
         if (isFirstAfterBreak(flowThreadOffset())
-            || group().columnLogicalTopForOffset(flowThreadOffset()) != group().columnLogicalTopForOffset(bottomInFlowThread)) {
+            || group.columnLogicalTopForOffset(flowThreadOffset()) != group.columnLogicalTopForOffset(bottomInFlowThread)) {
             // If the child crosses a column boundary, record space shortage, in case nothing
             // inside it has already done so. The column balancer needs to know by how much it
             // has to stretch the columns to make more content fit. If no breaks are reported
             // (but do occur), the balancer will have no clue. Only measure the space after the
             // last column boundary, in case it crosses more than one.
-            LayoutUnit spaceUsedInLastColumn = bottomInFlowThread - group().columnLogicalTopForOffset(bottomInFlowThread);
+            LayoutUnit spaceUsedInLastColumn = bottomInFlowThread - group.columnLogicalTopForOffset(bottomInFlowThread);
             recordSpaceShortage(spaceUsedInLastColumn);
         }
     }
@@ -288,10 +290,12 @@ void MinimumSpaceShortageFinder::examineBoxAfterEntering(const LayoutBox& box)
     if (!flowThread || flowThread->isLayoutPagedFlowThread())
         return;
     for (const LayoutMultiColumnSet* columnSet = flowThread->firstMultiColumnSet(); columnSet; columnSet = columnSet->nextSiblingMultiColumnSet()) {
-        for (const MultiColumnFragmentainerGroup& row : columnSet->fragmentainerGroups()) {
-            MinimumSpaceShortageFinder innerFinder(row);
-            recordSpaceShortage(innerFinder.minimumSpaceShortage());
-        }
+        // Establish an inner shortage finder for this column set in the inner multicol
+        // container. We need to let it walk through all fragmentainer groups in one go, or we'd
+        // miss the column boundaries between each fragmentainer group. We need to record space
+        // shortage there too.
+        MinimumSpaceShortageFinder innerFinder(*columnSet, columnSet->logicalTopInFlowThread(), columnSet->logicalBottomInFlowThread());
+        recordSpaceShortage(innerFinder.minimumSpaceShortage());
     }
 }
 
@@ -303,7 +307,7 @@ void MinimumSpaceShortageFinder::examineBoxBeforeLeaving(const LayoutBox& box)
     // The previous break was before a breakable block. Here's the first piece of unbreakable
     // content after / inside that block. We want to record the distance from the top of the column
     // to the bottom of this box as space shortage.
-    LayoutUnit logicalOffsetFromCurrentColumn = flowThreadOffset() - group().columnLogicalTopForOffset(flowThreadOffset());
+    LayoutUnit logicalOffsetFromCurrentColumn = offsetFromColumnLogicalTop(flowThreadOffset());
     recordSpaceShortage(logicalOffsetFromCurrentColumn + box.logicalHeight() - m_pendingStrut);
     m_pendingStrut = LayoutUnit::min();
 }
@@ -317,7 +321,7 @@ void MinimumSpaceShortageFinder::examineLine(const RootInlineBox& line)
         // The previous break was before a breakable block. Here's the first line after / inside
         // that block. We want to record the distance from the top of the column to the bottom of
         // this box as space shortage.
-        LayoutUnit logicalOffsetFromCurrentColumn = lineTopInFlowThread - group().columnLogicalTopForOffset(lineTopInFlowThread);
+        LayoutUnit logicalOffsetFromCurrentColumn = offsetFromColumnLogicalTop(lineTopInFlowThread);
         recordSpaceShortage(logicalOffsetFromCurrentColumn + lineHeight - m_pendingStrut);
         m_pendingStrut = LayoutUnit::min();
         return;
@@ -329,9 +333,10 @@ void MinimumSpaceShortageFinder::examineLine(const RootInlineBox& line)
     // Even if the line box itself fits fine inside a column, some content may overflow the line
     // box bottom (due to restrictive line-height, for instance). We should check if some portion
     // of said overflow ends up in the next column. That counts as space shortage.
+    const MultiColumnFragmentainerGroup& group = groupAtOffset(lineTopInFlowThread);
     LayoutUnit lineBottomWithOverflow = lineTopInFlowThread + line.lineBottom() - lineTop;
-    if (group().columnLogicalTopForOffset(lineTopInFlowThread) != group().columnLogicalTopForOffset(lineBottomWithOverflow)) {
-        LayoutUnit shortage = lineBottomWithOverflow - group().columnLogicalTopForOffset(lineBottomWithOverflow);
+    if (group.columnLogicalTopForOffset(lineTopInFlowThread) != group.columnLogicalTopForOffset(lineBottomWithOverflow)) {
+        LayoutUnit shortage = lineBottomWithOverflow - group.columnLogicalTopForOffset(lineBottomWithOverflow);
         recordSpaceShortage(shortage);
     }
 }