Column balancing refactoring. Don't propagate data during layout.

third_party/WebKit/Source/core/layout/MultiColumnFragmentainerGroup.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 "config.h"
 
 #include "core/layout/MultiColumnFragmentainerGroup.h"
 
+#include "core/layout/ColumnBalancer.h"
 #include "core/layout/LayoutMultiColumnSet.h"
 
 namespace blink {
 
 MultiColumnFragmentainerGroup::MultiColumnFragmentainerGroup(LayoutMultiColumnSet& columnSet)
     : m_columnSet(columnSet)
 {
 }
 
+bool MultiColumnFragmentainerGroup::isFirstGroup() const
+{
+    return &m_columnSet.firstFragmentainerGroup() == this;
+}
+
 bool MultiColumnFragmentainerGroup::isLastGroup() const
 {
     return &m_columnSet.lastFragmentainerGroup() == this;
 }
 
 LayoutSize MultiColumnFragmentainerGroup::offsetFromColumnSet() const
 {
     LayoutSize offset(LayoutUnit(), logicalTop());
     if (!m_columnSet.flowThread()->isHorizontalWritingMode())
         return offset.transposedSize();
@@ skipping 30 matching lines @@
         LayoutUnit columnHeight = heightIsAuto() ? m_maxColumnHeight : heightAdjustedForRowOffset(flowThread->columnHeightAvailable());
         setAndConstrainColumnHeight(columnHeight);
     } else if (heightIsAuto()) {
         m_columnHeight = LayoutUnit();
     } else {
         setAndConstrainColumnHeight(heightAdjustedForRowOffset(flowThread->columnHeightAvailable()));
     }
 
     if (m_columnHeight != oldColumnHeight)
         m_columnSet.setChildNeedsLayout(MarkOnlyThis);
-
-    // Content runs are only needed in the initial layout pass, in order to find an initial column
-    // height, and should have been deleted afterwards. We're about to rebuild the content runs, so
-    // the list needs to be empty.
-    ASSERT(m_contentRuns.isEmpty());
-}
-
-void MultiColumnFragmentainerGroup::addContentRun(LayoutUnit 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() < m_columnSet.usedColumnCount())
-        m_contentRuns.append(ContentRun(endOffsetInFlowThread));
-}
-
-void MultiColumnFragmentainerGroup::recordSpaceShortage(LayoutUnit spaceShortage)
-{
-    if (spaceShortage >= m_minSpaceShortage)
-        return;
-
-    // The space shortage is what we use as our stretch amount. We need a positive number here in
-    // order to get anywhere.
-    ASSERT(spaceShortage > 0);
-
-    m_minSpaceShortage = spaceShortage;
 }
 
 bool MultiColumnFragmentainerGroup::recalculateColumnHeight(BalancedColumnHeightCalculation calculationMode)
 {
     LayoutUnit oldColumnHeight = m_columnHeight;
 
     m_maxColumnHeight = calculateMaxColumnHeight();
 
     if (heightIsAuto()) {
-        if (calculationMode == GuessFromFlowThreadPortion) {
-            // Post-process the content runs and find out where the implicit breaks will occur.
-            distributeImplicitBreaks();
-        }
         LayoutUnit newColumnHeight = calculateColumnHeight(calculationMode);
         setAndConstrainColumnHeight(newColumnHeight);
         // After having calculated an initial column height, the multicol container typically needs at
         // least one more layout pass with a new column height, but if a height was specified, we only
         // need to do this if we think that we need less space than specified. Conversely, if we
         // determined that the columns need to be as tall as the specified height of the container, we
         // have already laid it out correctly, and there's no need for another pass.
     } else {
         // The position of the column set may have changed, in which case height available for
         // columns may have changed as well.
         setAndConstrainColumnHeight(m_columnHeight);
     }
 
-    // We can get rid of the content runs now, if we haven't already done so. They are only needed
-    // to calculate the initial balanced column height. In fact, we have to get rid of them before
-    // the next layout pass, since each pass will rebuild this.
-    m_contentRuns.clear();
-
     if (m_columnHeight == oldColumnHeight)
         return false; // No change. We're done.
 
-    m_minSpaceShortage = LayoutUnit::max();
     return true; // Need another pass.
 }
 
 LayoutSize MultiColumnFragmentainerGroup::flowThreadTranslationAtOffset(LayoutUnit offsetInFlowThread) const
 {
     LayoutMultiColumnFlowThread* flowThread = m_columnSet.multiColumnFlowThread();
     unsigned columnIndex = columnIndexAtOffset(offsetInFlowThread);
     LayoutRect portionRect(flowThreadPortionRectAt(columnIndex));
     flowThread->flipForWritingMode(portionRect);
     LayoutRect columnRect(columnRectAt(columnIndex));
@@ skipping 227 matching lines @@
     return maxHeight;
 }
 
 void MultiColumnFragmentainerGroup::setAndConstrainColumnHeight(LayoutUnit newHeight)
 {
     m_columnHeight = newHeight;
     if (m_columnHeight > m_maxColumnHeight)
         m_columnHeight = m_maxColumnHeight;
 }
 
-unsigned MultiColumnFragmentainerGroup::findRunWithTallestColumns() const
-{
-    unsigned indexWithLargestHeight = 0;
-    LayoutUnit largestHeight;
-    LayoutUnit previousOffset = m_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 MultiColumnFragmentainerGroup::distributeImplicitBreaks()
-{
-#if ENABLE(ASSERT)
-    // There should be no implicit breaks assumed at this point.
-    for (unsigned i = 0; i < m_contentRuns.size(); i++)
-        ASSERT(!m_contentRuns[i].assumedImplicitBreaks());
-#endif // ENABLE(ASSERT)
-
-    // Insert a final content run to encompass all content. This will include overflow if this is
-    // the last set.
-    addContentRun(m_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 < m_columnSet.usedColumnCount()) {
-        unsigned index = findRunWithTallestColumns();
-        m_contentRuns[index].assumeAnotherImplicitBreak();
-        columnCount++;
-    }
-}
-
 LayoutUnit MultiColumnFragmentainerGroup::calculateColumnHeight(BalancedColumnHeightCalculation calculationMode) const
 {
     if (calculationMode == GuessFromFlowThreadPortion) {
         // Initial balancing. Start with the lowest imaginable column height. We use the tallest
         // content run (after having "inserted" implicit breaks), and find its start offset (by
         // looking at the previous run's end offset, or, if there's no previous run, the set's start
         // offset in the flow thread).
-        unsigned index = findRunWithTallestColumns();
-        LayoutUnit startOffset = index > 0 ? m_contentRuns[index - 1].breakOffset() : m_logicalTopInFlowThread;
-        return std::max<LayoutUnit>(m_contentRuns[index].columnLogicalHeight(startOffset), m_minimumColumnHeight);
+        return std::max(InitialColumnHeightFinder::initialMinimalBalancedHeight(*this), m_minimumColumnHeight);
     }
 
     if (actualColumnCount() <= m_columnSet.usedColumnCount()) {
         // With the current column height, the content fits without creating overflowing columns. We're done.
         return m_columnHeight;
     }
 
-    if (m_contentRuns.size() >= m_columnSet.usedColumnCount()) {
-        // Too many forced breaks to allow any implicit breaks. Initial balancing should already
-        // have set a good height. There's nothing more we should do.
-        return m_columnHeight;
-    }
-
     if (m_columnHeight >= m_maxColumnHeight) {
         // We cannot stretch any further. We'll just have to live with the overflowing columns. This
         // typically happens if the max column height is less than the height of the tallest piece
         // of unbreakable content (e.g. lines).
         return m_columnHeight;
     }
 
+    MinimumSpaceShortageFinder shortageFinder(*this);
+
+    if (shortageFinder.forcedBreaksCount() + 1 >= m_columnSet.usedColumnCount()) {
+        // Too many forced breaks to allow any implicit breaks. Initial balancing should already
+        // have set a good height. There's nothing more we should do.
+        return m_columnHeight;
+    }
+
     // If the initial guessed column height wasn't enough, stretch it now. Stretch by the lowest
-    // amount of space shortage found during layout.
+    // amount of space.
+    LayoutUnit minSpaceShortage = shortageFinder.minimumSpaceShortage();
 
-    ASSERT(m_minSpaceShortage > 0); // We should never _shrink_ the height!
-    ASSERT(m_minSpaceShortage != LayoutUnit::max()); // If this happens, we probably have a bug.
-    if (m_minSpaceShortage == LayoutUnit::max())
+    ASSERT(minSpaceShortage > 0); // We should never _shrink_ the height!
+    ASSERT(minSpaceShortage != LayoutUnit::max()); // If this happens, we probably have a bug.
+    if (minSpaceShortage == LayoutUnit::max())
         return m_columnHeight; // So bail out rather than looping infinitely.
 
-    return m_columnHeight + m_minSpaceShortage;
+    return m_columnHeight + minSpaceShortage;
 }
 
 LayoutRect MultiColumnFragmentainerGroup::columnRectAt(unsigned columnIndex) const
 {
     LayoutUnit columnLogicalWidth = m_columnSet.pageLogicalWidth();
     LayoutUnit columnLogicalHeight = m_columnHeight;
     LayoutUnit columnLogicalTop;
     LayoutUnit columnLogicalLeft;
     LayoutUnit columnGap = m_columnSet.columnGap();
     LayoutUnit portionOutsideFlowThread = logicalTopInFlowThread() + (columnIndex + 1) * columnLogicalHeight - logicalBottomInFlowThread();
@@ skipping 165 matching lines @@
     append(MultiColumnFragmentainerGroup(m_columnSet));
     return last();
 }
 
 void MultiColumnFragmentainerGroupList::deleteExtraGroups()
 {
     shrink(1);
 }
 
 } // namespace blink