[New Multicolumn] Preparatory work for nested multicol support.

Source/core/rendering/MultiColumnRow.cpp

Index: Source/core/rendering/MultiColumnRow.cpp
diff --git a/Source/core/rendering/MultiColumnRow.cpp b/Source/core/rendering/MultiColumnRow.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..3f76b9b762fd4e04bfe9e015f67178f8ebf5f643
--- /dev/null
+++ b/Source/core/rendering/MultiColumnRow.cpp
@@ -0,0 +1,487 @@
+// 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/rendering/MultiColumnRow.h"
+
+#include "core/rendering/RenderMultiColumnSet.h"
+
+namespace blink {
+
+MultiColumnRow::MultiColumnRow(RenderMultiColumnSet& columnSet)
+    : m_columnSet(columnSet)
+{
+}
+
+LayoutSize MultiColumnRow::offsetFromColumnSet() const
+{
+    LayoutSize offset(LayoutUnit(), logicalTop());
+    if (!m_columnSet.flowThread()->isHorizontalWritingMode())
+        return offset.transposedSize();
+    return offset;
+}
+
+bool MultiColumnRow::heightIsAuto() const
+{
+    // Only the last row may have auto height, and thus be balanced. There are no good reasons to
+    // balance the preceding rows, and that could potentially lead to an insane number of layout
+    // passes as well.
+    return !nextRow() && m_columnSet.heightIsAuto();
+}
+
+void MultiColumnRow::resetColumnHeight()
+{
+    // Nuke previously stored minimum column height. Contents may have changed for all we know.
+    m_minimumColumnHeight = 0;
+
+    m_maxColumnHeight = calculateMaxColumnHeight();
+
+    LayoutUnit oldColumnHeight = m_columnHeight;
+
+    if (heightIsAuto())
+        m_columnHeight = LayoutUnit();
+    else
+        setAndConstrainColumnHeight(heightAdjustedForRowOffset(m_columnSet.multiColumnFlowThread()->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 MultiColumnRow::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 MultiColumnRow::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 MultiColumnRow::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 = RenderFlowThread::maxLogicalHeight();
+    return true; // Need another pass.
+}
+
+void MultiColumnRow::expandToEncompassFlowThreadOverflow()
+{
+    ASSERT(!nextRow());
+    // Get the offset within the flow thread in its block progression direction. Then get the
+    // flow thread's remaining logical height including its overflow and expand our rect
+    // to encompass that remaining height and overflow. The idea is that we will generate
+    // additional columns and pages to hold that overflow, since people do write bad
+    // content like <body style="height:0px"> in multi-column layouts.
+    RenderMultiColumnFlowThread* flowThread = m_columnSet.multiColumnFlowThread();
+    LayoutRect layoutRect = flowThread->layoutOverflowRect();
+    m_logicalBottomInFlowThread = flowThread->isHorizontalWritingMode() ? layoutRect.maxY() : layoutRect.maxX();
+}
+
+LayoutSize MultiColumnRow::flowThreadTranslationAtOffset(LayoutUnit offsetInFlowThread) const
+{
+    unsigned columnIndex = columnIndexAtOffset(offsetInFlowThread);
+    LayoutRect portionRect(flowThreadPortionRectAt(columnIndex));
+    m_columnSet.flipForWritingMode(portionRect);
+    LayoutRect columnRect(columnRectAt(columnIndex));
+    m_columnSet.flipForWritingMode(columnRect);
+    return columnRect.location() - portionRect.location();
+}
+
+LayoutUnit MultiColumnRow::columnLogicalTopForOffset(LayoutUnit offsetInFlowThread) const
+{
+    unsigned columnIndex = columnIndexAtOffset(offsetInFlowThread, AssumeNewColumns);
+    return m_logicalTopInFlowThread + columnIndex * m_columnHeight;
+}
+
+void MultiColumnRow::collectLayerFragments(LayerFragments& fragments, const LayoutRect& layerBoundingBox, const LayoutRect& dirtyRect)
+{
+    // |layerBoundingBox| is in the flow thread coordinate space, relative to the top/left edge of
+    // the flow thread, but note that it has been converted with respect to writing mode (so that
+    // it's visual/physical in that sense).
+    //
+    // |dirtyRect| is visual, relative to the multicol container.
+    //
+    // Then there's the output from this method - the stuff we put into the list of fragments. The
+    // fragment.paginationOffset point is the actual visual translation required to get from a
+    // location in the flow thread to a location in a given column. The fragment.paginationClip
+    // rectangle, on the other hand, is in flow thread coordinates.
+    //
+    // All other rectangles in this method are sized physically, and the inline direction coordinate
+    // is physical too, but the block direction coordinate is "logical top". This is the same as
+    // e.g. RenderBox::frameRect(). These rectangles also pretend that there's only one long column,
+    // i.e. they are for the flow thread.
+
+    RenderMultiColumnFlowThread* flowThread = m_columnSet.multiColumnFlowThread();
+    bool isHorizontalWritingMode = m_columnSet.isHorizontalWritingMode();
+
+    // Put the layer bounds into flow thread-local coordinates by flipping it first. Since we're in
+    // a renderer, most rectangles are represented this way.
+    LayoutRect layerBoundsInFlowThread(layerBoundingBox);
+    flowThread->flipForWritingMode(layerBoundsInFlowThread);
+
+    // Now we can compare with the flow thread portions owned by each column. First let's
+    // see if the rect intersects our flow thread portion at all.
+    LayoutRect clippedRect(layerBoundsInFlowThread);
+    clippedRect.intersect(m_columnSet.RenderRegion::flowThreadPortionOverflowRect()); // FIXME: clean up this mess.
+    if (clippedRect.isEmpty())
+        return;
+
+    // Now we know we intersect at least one column. Let's figure out the logical top and logical
+    // bottom of the area we're checking.
+    LayoutUnit layerLogicalTop = isHorizontalWritingMode ? layerBoundsInFlowThread.y() : layerBoundsInFlowThread.x();
+    LayoutUnit layerLogicalBottom = (isHorizontalWritingMode ? layerBoundsInFlowThread.maxY() : layerBoundsInFlowThread.maxX()) - 1;
+
+    // Figure out the start and end columns and only check within that range so that we don't walk the
+    // entire column row.
+    unsigned startColumn = columnIndexAtOffset(layerLogicalTop);
+    unsigned endColumn = columnIndexAtOffset(layerLogicalBottom);
+
+    LayoutUnit colLogicalWidth = m_columnSet.pageLogicalWidth();
+    LayoutUnit colGap = m_columnSet.columnGap();
+    unsigned colCount = actualColumnCount();
+
+    bool progressionIsInline = flowThread->progressionIsInline();
+    bool leftToRight = m_columnSet.style()->isLeftToRightDirection();
+
+    LayoutUnit initialBlockOffset = m_columnSet.logicalTop() + logicalTop() - flowThread->logicalTop();
+
+    for (unsigned i = startColumn; i <= endColumn; i++) {
+        // Get the portion of the flow thread that corresponds to this column.
+        LayoutRect flowThreadPortion = flowThreadPortionRectAt(i);
+
+        // Now get the overflow rect that corresponds to the column.
+        LayoutRect flowThreadOverflowPortion = flowThreadPortionOverflowRect(flowThreadPortion, i, colCount, colGap);
+
+        // In order to create a fragment we must intersect the portion painted by this column.
+        LayoutRect clippedRect(layerBoundsInFlowThread);
+        clippedRect.intersect(flowThreadOverflowPortion);
+        if (clippedRect.isEmpty())
+            continue;
+
+        // We also need to intersect the dirty rect. We have to apply a translation and shift based off
+        // our column index.
+        LayoutPoint translationOffset;
+        LayoutUnit inlineOffset = progressionIsInline ? i * (colLogicalWidth + colGap) : LayoutUnit();
+        if (!leftToRight)
+            inlineOffset = -inlineOffset;
+        translationOffset.setX(inlineOffset);
+        LayoutUnit blockOffset;
+        if (progressionIsInline) {
+            blockOffset = initialBlockOffset + (isHorizontalWritingMode ? -flowThreadPortion.y() : -flowThreadPortion.x());
+        } else {
+            // Column gap can apply in the block direction for page fragmentainers.
+            // There is currently no spec which calls for column-gap to apply
+            // for page fragmentainers at all, but it's applied here for compatibility
+            // with the old multicolumn implementation.
+            blockOffset = i * colGap;
+        }
+        if (isFlippedBlocksWritingMode(m_columnSet.style()->writingMode()))
+            blockOffset = -blockOffset;
+        translationOffset.setY(blockOffset);
+        if (!isHorizontalWritingMode)
+            translationOffset = translationOffset.transposedPoint();
+
+        // Shift the dirty rect to be in flow thread coordinates with this translation applied.
+        LayoutRect translatedDirtyRect(dirtyRect);
+        translatedDirtyRect.moveBy(-translationOffset);
+
+        // See if we intersect the dirty rect.
+        clippedRect = layerBoundingBox;
+        clippedRect.intersect(translatedDirtyRect);
+        if (clippedRect.isEmpty())
+            continue;
+
+        // Something does need to paint in this column. Make a fragment now and supply the physical translation
+        // offset and the clip rect for the column with that offset applied.
+        LayerFragment fragment;
+        fragment.paginationOffset = translationOffset;
+
+        LayoutRect flippedFlowThreadOverflowPortion(flowThreadOverflowPortion);
+        // Flip it into more a physical (RenderLayer-style) rectangle.
+        flowThread->flipForWritingMode(flippedFlowThreadOverflowPortion);
+        fragment.paginationClip = flippedFlowThreadOverflowPortion;
+        fragments.append(fragment);
+    }
+}
+
+LayoutRect MultiColumnRow::calculateOverflow() const
+{
+    unsigned columnCount = actualColumnCount();
+    if (!columnCount)
+        return LayoutRect();
+    return columnRectAt(columnCount - 1);
+}
+
+unsigned MultiColumnRow::actualColumnCount() const
+{
+    // We must always return a value of 1 or greater. Column count = 0 is a meaningless situation,
+    // and will confuse and cause problems in other parts of the code.
+    if (!m_columnHeight)
+        return 1;
+
+    // Our flow thread portion determines our column count. We have as many columns as needed to fit
+    // all the content.
+    LayoutUnit flowThreadPortionHeight = logicalHeightInFlowThread();
+    if (!flowThreadPortionHeight)
+        return 1;
+
+    unsigned count = ceil(flowThreadPortionHeight.toFloat() / m_columnHeight.toFloat());
+    ASSERT(count >= 1);
+    return count;
+}
+
+LayoutUnit MultiColumnRow::heightAdjustedForRowOffset(LayoutUnit height) const
+{
+    // Adjust for the top offset within the content box of the multicol container (containing
+    // block), unless we're in the first set. We know that the top offset for the first set will be
+    // zero, but if the multicol container has non-zero top border or padding, the set's top offset
+    // (initially being 0 and relative to the border box) will be negative until it has been laid
+    // out. Had we used this bogus offset, we would calculate the wrong height, and risk performing
+    // a wasted layout iteration. Of course all other sets (if any) have this problem in the first
+    // layout pass too, but there's really nothing we can do there until the flow thread has been
+    // laid out anyway.
+    if (m_columnSet.previousSiblingMultiColumnSet()) {
+        RenderBlockFlow* multicolBlock = m_columnSet.multiColumnBlockFlow();
+        LayoutUnit contentLogicalTop = m_columnSet.logicalTop() - multicolBlock->borderAndPaddingBefore();
+        height -= contentLogicalTop;
+    }
+    height -= logicalTop();
+    return max(height, LayoutUnit(1)); // Let's avoid zero height, as that would probably cause an infinite amount of columns to be created.
+}
+
+LayoutUnit MultiColumnRow::calculateMaxColumnHeight() const
+{
+    RenderBlockFlow* multicolBlock = m_columnSet.multiColumnBlockFlow();
+    RenderStyle* multicolStyle = multicolBlock->style();
+    LayoutUnit availableHeight = m_columnSet.multiColumnFlowThread()->columnHeightAvailable();
+    LayoutUnit maxColumnHeight = availableHeight ? availableHeight : RenderFlowThread::maxLogicalHeight();
+    if (!multicolStyle->logicalMaxHeight().isMaxSizeNone()) {
+        LayoutUnit logicalMaxHeight = multicolBlock->computeContentLogicalHeight(multicolStyle->logicalMaxHeight(), -1);
+        if (logicalMaxHeight != -1 && maxColumnHeight > logicalMaxHeight)
+            maxColumnHeight = logicalMaxHeight;
+    }
+    return heightAdjustedForRowOffset(maxColumnHeight);
+}
+
+void MultiColumnRow::setAndConstrainColumnHeight(LayoutUnit newHeight)
+{
+    m_columnHeight = newHeight;
+    if (m_columnHeight > m_maxColumnHeight)
+        m_columnHeight = m_maxColumnHeight;
+    // FIXME: the height may also be affected by the enclosing pagination context, if any.
+}
+
+unsigned MultiColumnRow::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 MultiColumnRow::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 MultiColumnRow::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);
+    }
+
+    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 the initial guessed column height wasn't enough, stretch it now. Stretch by the lowest
+    // amount of space shortage found during layout.
+
+    ASSERT(m_minSpaceShortage > 0); // We should never _shrink_ the height!
+    ASSERT(m_minSpaceShortage != RenderFlowThread::maxLogicalHeight()); // If this happens, we probably have a bug.
+    if (m_minSpaceShortage == RenderFlowThread::maxLogicalHeight())
+        return m_columnHeight; // So bail out rather than looping infinitely.
+
+    return m_columnHeight + m_minSpaceShortage;
+}
+
+LayoutRect MultiColumnRow::columnRectAt(unsigned columnIndex) const
+{
+    LayoutUnit columnLogicalWidth = m_columnSet.pageLogicalWidth();
+    LayoutUnit columnLogicalHeight = m_columnHeight;
+    LayoutUnit columnLogicalTop;
+    LayoutUnit columnLogicalLeft;
+    LayoutUnit columnGap = m_columnSet.columnGap();
+
+    if (m_columnSet.multiColumnFlowThread()->progressionIsInline()) {
+        if (m_columnSet.style()->isLeftToRightDirection())
+            columnLogicalLeft += columnIndex * (columnLogicalWidth + columnGap);
+        else
+            columnLogicalLeft += m_columnSet.contentLogicalWidth() - columnLogicalWidth - columnIndex * (columnLogicalWidth + columnGap);
+    } else {
+        columnLogicalTop += columnIndex * (columnLogicalHeight + columnGap);
+    }
+
+    LayoutRect columnRect(columnLogicalLeft, columnLogicalTop, columnLogicalWidth, columnLogicalHeight);
+    if (!m_columnSet.isHorizontalWritingMode())
+        return columnRect.transposedRect();
+    return columnRect;
+}
+
+LayoutRect MultiColumnRow::flowThreadPortionRectAt(unsigned columnIndex) const
+{
+    LayoutUnit logicalTop = m_logicalTopInFlowThread + columnIndex * m_columnHeight;
+    if (m_columnSet.isHorizontalWritingMode())
+        return LayoutRect(LayoutUnit(), logicalTop, m_columnSet.pageLogicalWidth(), m_columnHeight);
+    return LayoutRect(logicalTop, LayoutUnit(), m_columnHeight, m_columnSet.pageLogicalWidth());
+}
+
+LayoutRect MultiColumnRow::flowThreadPortionOverflowRect(const LayoutRect& portionRect, unsigned columnIndex, unsigned columnCount, LayoutUnit columnGap) const
+{
+    // This function determines the portion of the flow thread that paints for the column. Along the inline axis, columns are
+    // unclipped at outside edges (i.e., the first and last column in the set), and they clip to half the column
+    // gap along interior edges.
+    //
+    // In the block direction, we will not clip overflow out of the top of the first column, or out of the bottom of
+    // the last column. This applies only to the true first column and last column across all column sets.
+    //
+    // FIXME: Eventually we will know overflow on a per-column basis, but we can't do this until we have a painting
+    // mode that understands not to paint contents from a previous column in the overflow area of a following column.
+    // This problem applies to regions and pages as well and is not unique to columns.
+    bool isFirstColumn = !columnIndex;
+    bool isLastColumn = columnIndex == columnCount - 1;
+    bool isLTR = m_columnSet.style()->isLeftToRightDirection();
+    bool isLeftmostColumn = isLTR ? isFirstColumn : isLastColumn;
+    bool isRightmostColumn = isLTR ? isLastColumn : isFirstColumn;
+
+    // Calculate the overflow rectangle, based on the flow thread's, clipped at column logical
+    // top/bottom unless it's the first/last column.
+    LayoutRect overflowRect = m_columnSet.overflowRectForFlowThreadPortion(portionRect, isFirstColumn && m_columnSet.isFirstRegion(), isLastColumn && m_columnSet.isLastRegion());
+
+    // Avoid overflowing into neighboring columns, by clipping in the middle of adjacent column
+    // gaps. Also make sure that we avoid rounding errors.
+    if (m_columnSet.isHorizontalWritingMode()) {
+        if (!isLeftmostColumn)
+            overflowRect.shiftXEdgeTo(portionRect.x() - columnGap / 2);
+        if (!isRightmostColumn)
+            overflowRect.shiftMaxXEdgeTo(portionRect.maxX() + columnGap - columnGap / 2);
+    } else {
+        if (!isLeftmostColumn)
+            overflowRect.shiftYEdgeTo(portionRect.y() - columnGap / 2);
+        if (!isRightmostColumn)
+            overflowRect.shiftMaxYEdgeTo(portionRect.maxY() + columnGap - columnGap / 2);
+    }
+    return overflowRect;
+}
+
+unsigned MultiColumnRow::columnIndexAtOffset(LayoutUnit offsetInFlowThread, ColumnIndexCalculationMode mode) const
+{
+    // Handle the offset being out of range.
+    if (offsetInFlowThread < m_logicalTopInFlowThread)
+        return 0;
+    // If we're laying out right now, we cannot constrain against some logical bottom, since it
+    // isn't known yet. Otherwise, just return the last column if we're past the logical bottom.
+    if (mode == ClampToExistingColumns) {
+        if (offsetInFlowThread >= m_logicalBottomInFlowThread)
+            return actualColumnCount() - 1;
+    }
+
+    if (m_columnHeight)
+        return (offsetInFlowThread - m_logicalTopInFlowThread).toFloat() / m_columnHeight.toFloat();
+    return 0;
+}
+
+} // namespace blink