Support multiple fragmentainer groups per ColumnBalancer run.

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

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "core/layout/ColumnBalancer.h"
 
 #include "core/layout/LayoutMultiColumnFlowThread.h"
 #include "core/layout/LayoutMultiColumnSet.h"
 #include "core/layout/api/LineLayoutBlockFlow.h"
 
 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());
 }
 
 void ColumnBalancer::traverseSubtree(const LayoutBox& box)
 {
     if (box.childrenInline() && box.isLayoutBlockFlow()) {
         // 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
     // inline children, there may be interesting floats to examine here.
     for (const LayoutObject* child = box.slowFirstChild(); child; child = child->nextSibling()) {
         if (!child->isBox() || child->isInline())
             continue;
         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;
         }
         if (childBox.isOutOfFlowPositioned() || childBox.isColumnSpanAll())
             continue;
 
         // Tables are wicked. Both table rows and table cells are relative to their table section.
         LayoutUnit offsetForThisChild = childBox.isTableRow() ? LayoutUnit() : childBox.logicalTop();
         m_flowThreadOffset += offsetForThisChild;
 
         examineBoxAfterEntering(childBox);
         // Unless the child is unsplittable, or if the child establishes an inner multicol
         // container, we descend into its subtree for further examination.
         if (childBox.getPaginationBreakability() != LayoutBox::ForbidBreaks
             && (!childBox.isLayoutBlockFlow() || !toLayoutBlockFlow(childBox).multiColumnFlowThread()))
             traverseSubtree(childBox);
         m_previousBreakAfterValue = childBox.breakAfter();
         examineBoxBeforeLeaving(childBox);
 
         m_flowThreadOffset -= offsetForThisChild;
     }
 }
 
-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();
     // We have now found each explicit / forced break, and their location. Now we need to figure out
     // how many additional implicit / soft breaks we need and guess where they will occur, in order
     // to provide an initial column height.
     distributeImplicitBreaks();
 }
 
 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);
 }
 
 void InitialColumnHeightFinder::examineBoxAfterEntering(const LayoutBox& box)
 {
     if (isLogicalTopWithinBounds(flowThreadOffset() - box.paginationStrut())) {
         if (box.needsForcedBreakBefore(previousBreakAfterValue())) {
             addContentRun(flowThreadOffset());
         } else {
             ASSERT(isFirstAfterBreak(flowThreadOffset()) || !box.paginationStrut());
@@ skipping 43 matching lines @@
     LayoutUnit lineTopInFlowThread = flowThreadOffset() + lineTop;
     LayoutUnit minimumLogialHeight = columnLogicalHeightRequirementForLine(line.block().styleRef(), line);
     m_tallestUnbreakableLogicalHeight = std::max(m_tallestUnbreakableLogicalHeight, minimumLogialHeight);
     ASSERT(isFirstAfterBreak(lineTopInFlowThread) || !line.paginationStrut() || !isLogicalTopWithinBounds(lineTopInFlowThread - line.paginationStrut()));
     if (isFirstAfterBreak(lineTopInFlowThread))
         recordStrutBeforeOffset(lineTopInFlowThread, line.paginationStrut());
 }
 
 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);
 }
 
 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++) {
         if (m_shortestStruts[i] != LayoutUnit::max())
             totalStrutSpace += m_shortestStruts[i];
     }
     return totalStrutSpace;
 }
 
 void InitialColumnHeightFinder::addContentRun(LayoutUnit endOffsetInFlowThread)
 {
     endOffsetInFlowThread -= spaceUsedByStrutsAt(endOffsetInFlowThread);
     if (!m_contentRuns.isEmpty() && endOffsetInFlowThread <= m_contentRuns.last().breakOffset())
         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));
 }
 
 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++) {
         const ContentRun& run = m_contentRuns[i];
         LayoutUnit height = run.columnLogicalHeight(previousOffset);
         if (largestHeight < height) {
             largestHeight = height;
             indexWithLargestHeight = i;
         }
         previousOffset = run.breakOffset();
     }
     return indexWithLargestHeight;
 }
 
 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
     // insert implicit breaks at suitable locations. At any given time, the content run with the
     // currently tallest columns will get another implicit break "inserted", which will increase its
     // 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)
 {
     traverse();
 }
 
 void MinimumSpaceShortageFinder::examineBoxAfterEntering(const LayoutBox& box)
 {
     LayoutBox::PaginationBreakability breakability = box.getPaginationBreakability();
@@ skipping 17 matching lines @@
                     // more suitable).
                     m_pendingStrut = strut;
                 }
             }
         }
     }
 
     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);
         }
     }
 
     // If this is an inner multicol container, look for space shortage inside it.
     if (!box.isLayoutBlockFlow())
         return;
     LayoutMultiColumnFlowThread* flowThread = toLayoutBlockFlow(box).multiColumnFlowThread();
     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());
     }
 }
 
 void MinimumSpaceShortageFinder::examineBoxBeforeLeaving(const LayoutBox& box)
 {
     if (m_pendingStrut == LayoutUnit::min() || box.getPaginationBreakability() != LayoutBox::ForbidBreaks)
         return;
 
     // 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();
 }
 
 void MinimumSpaceShortageFinder::examineLine(const RootInlineBox& line)
 {
     LayoutUnit lineTop = line.lineTopWithLeading();
     LayoutUnit lineTopInFlowThread = flowThreadOffset() + lineTop;
     LayoutUnit lineHeight = line.lineBottomWithLeading() - lineTop;
     if (m_pendingStrut != LayoutUnit::min()) {
         // 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;
     }
     ASSERT(isFirstAfterBreak(lineTopInFlowThread) || !line.paginationStrut() || !isLogicalTopWithinBounds(lineTopInFlowThread - line.paginationStrut()));
     if (isFirstAfterBreak(lineTopInFlowThread))
         recordSpaceShortage(lineHeight - line.paginationStrut());
 
     // 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);
     }
 }
 
 } // namespace blink