Column balancing support in the region based multicol implementation.

Source/core/rendering/RenderMultiColumnSet.cpp

 /*
  * Copyright (C) 2012 Apple Inc.  All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
@@ skipping 22 matching lines @@
 
 using namespace std;
 
 namespace WebCore {
 
 RenderMultiColumnSet::RenderMultiColumnSet(RenderFlowThread* flowThread)
     : RenderRegionSet(0, flowThread)
     , m_computedColumnCount(1)
     , m_computedColumnWidth(0)
     , m_computedColumnHeight(0)
-    , m_requiresBalancing(false)
+    , m_maxColumnHeight(LayoutUnit::max())
+    , m_minSpaceShortage(LayoutUnit::max())
     , m_minimumColumnHeight(0)
     , m_forcedBreaksCount(0)
     , m_maximumDistanceBetweenForcedBreaks(0)
     , m_forcedBreakOffset(0)
 {
 }
 
 RenderMultiColumnSet* RenderMultiColumnSet::createAnonymous(RenderFlowThread* flowThread)
 {
     Document* document = flowThread->document();
     RenderMultiColumnSet* renderer = new (document->renderArena()) RenderMultiColumnSet(flowThread);
     renderer->setDocumentForAnonymous(document);
     return renderer;
 }
 
+LayoutUnit RenderMultiColumnSet::heightAdjustedForSetOffset(LayoutUnit height) const
+{
+    RenderMultiColumnBlock* multicolBlock = toRenderMultiColumnBlock(parent());
+    LayoutUnit contentLogicalTop = logicalTop() - multicolBlock->borderBefore() - multicolBlock->paddingBefore();
+
+    height -= contentLogicalTop;
+    return max(height, LayoutUnit(1)); // Let's avoid zero height, as that would probably cause an infinite amount of columns to be created.
+}
+
 LayoutUnit RenderMultiColumnSet::pageLogicalTopForOffset(LayoutUnit offset) const
 {
     LayoutUnit portionLogicalTop = (isHorizontalWritingMode() ? flowThreadPortionRect().y() : flowThreadPortionRect().x());
-    unsigned columnIndex = (offset - portionLogicalTop) / computedColumnHeight();
+    unsigned columnIndex = columnIndexAtOffset(offset, AssumeNewColumns);
     return portionLogicalTop + columnIndex * computedColumnHeight();
 }
 
+void RenderMultiColumnSet::setAndConstrainColumnHeight(LayoutUnit newHeight)
+{
+    m_computedColumnHeight = newHeight;
+    if (m_computedColumnHeight > m_maxColumnHeight)
+        m_computedColumnHeight = m_maxColumnHeight;
+    // FIXME: the height may also be affected by the enclosing pagination context, if any.
+}
+
+bool RenderMultiColumnSet::calculateBalancedHeight(bool initial)
+{
+    ASSERT(toRenderMultiColumnBlock(parent())->requiresBalancing());
+    LayoutUnit oldColumnHeight = m_computedColumnHeight;
+    LayoutUnit currentMinSpaceShortage = m_minSpaceShortage;
+    m_minSpaceShortage = LayoutUnit::max();
+
+    if (initial) {
+        // Start with the lowest imaginable column height.
+        LayoutUnit logicalHeightGuess = ceilf(float(flowThread()->logicalHeight()) / float(m_computedColumnCount));
+        logicalHeightGuess = max(logicalHeightGuess, m_minimumColumnHeight);
+        setAndConstrainColumnHeight(logicalHeightGuess);
+
+        // The multicol container now typically needs at least one more layout pass with a new
+        // column height, but if height was specified, we only need to do this if we found that we
+        // might need less space than that. On the other hand, 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.
+        return m_computedColumnHeight != oldColumnHeight;
+    }
+
+    if (columnCount() <= computedColumnCount()) {
+        // With the current column height, the content fits without creating overflowing columns. We're done.
+        return false;
+    }
+
+    // If the initial guessed column height wasn't enough, stretch it now. Stretch by the lowest
+    // amount of space shortage found during layout.
+
+    ASSERT(currentMinSpaceShortage != LayoutUnit::max()); // If this can actually happen, we probably have a bug.
+    if (currentMinSpaceShortage == LayoutUnit::max())
+        return false; // So bail out rather than looping infinitely.
+
+    setAndConstrainColumnHeight(m_computedColumnHeight + currentMinSpaceShortage);
+
+    // If we reach the maximum column height (typically set by the height or max-height property),
+    // we may not be allowed to stretch further. Return true only if stretching
+    // succeeded. Otherwise, we're done.
+    ASSERT(m_computedColumnHeight >= oldColumnHeight); // We shouldn't be able to shrink the height!
+    return m_computedColumnHeight > oldColumnHeight;
+}
+
+void RenderMultiColumnSet::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;
+}
+
 void RenderMultiColumnSet::updateLogicalWidth()
 {
     RenderMultiColumnBlock* parentBlock = toRenderMultiColumnBlock(parent());
     setComputedColumnWidthAndCount(parentBlock->columnWidth(), parentBlock->columnCount()); // FIXME: This will eventually vary if we are contained inside regions.
     
     // FIXME: When we add regions support, we'll start it off at the width of the multi-column
     // block in that particular region.
     setLogicalWidth(parentBox()->contentLogicalWidth());
 
     // If we overflow, increase our logical width.
     unsigned colCount = columnCount();
-    if (!colCount)
-        return;
-    
     LayoutUnit colGap = columnGap();
     LayoutUnit minimumContentLogicalWidth = colCount * computedColumnWidth() + (colCount - 1) * colGap;
     LayoutUnit currentContentLogicalWidth = contentLogicalWidth();
     LayoutUnit delta = max(LayoutUnit(), minimumContentLogicalWidth - currentContentLogicalWidth);
     if (!delta)
         return;
 
     // Increase our logical width by the delta.
     setLogicalWidth(logicalWidth() + delta);
 }
 
-void RenderMultiColumnSet::updateLogicalHeight()
+void RenderMultiColumnSet::prepareForLayout()
 {
-    // FIXME: This is the only class that overrides updateLogicalHeight. If we didn't have to set computedColumnHeight,
-    // we could remove this and make updateLogicalHeight non-virtual. https://bugs.webkit.org/show_bug.cgi?id=96804
-    // Make sure our column height is up to date.
-    LogicalExtentComputedValues computedValues;
-    computeLogicalHeight(0, 0, computedValues);
-    setComputedColumnHeight(computedValues.m_extent); // FIXME: Once we make more than one column set, this will become variable.
-    
-    // Our logical height is always just the height of our columns.
-    setLogicalHeight(computedColumnHeight());
+    RenderMultiColumnBlock* multicolBlock = toRenderMultiColumnBlock(parent());
+    RenderStyle* multicolStyle = multicolBlock->style();
+
+    // Set box logical top.
+    ASSERT(!previousSiblingBox() || !previousSiblingBox()->isRenderMultiColumnSet()); // FIXME: multiple set not implemented; need to examine previous set to calculate the correct logical top.
+    setLogicalTop(multicolBlock->borderBefore() + multicolBlock->paddingBefore());
+
+    // Set box width.
+    updateLogicalWidth();
+
+    if (multicolBlock->requiresBalancing()) {
+        // Set maximum column height. We will not stretch beyond this.
+        m_maxColumnHeight = LayoutUnit::max();
+        if (!multicolStyle->logicalHeight().isAuto())
+            m_maxColumnHeight = multicolBlock->computeContentLogicalHeight(multicolStyle->logicalHeight(), -1);
+        if (!multicolStyle->logicalMaxHeight().isUndefined()) {
+            LayoutUnit logicalMaxHeight = multicolBlock->computeContentLogicalHeight(multicolStyle->logicalMaxHeight(), -1);
+            if (m_maxColumnHeight > logicalMaxHeight)
+                m_maxColumnHeight = logicalMaxHeight;
+        }
+        m_maxColumnHeight = heightAdjustedForSetOffset(m_maxColumnHeight);
+        m_computedColumnHeight = 0; // Restart balancing.
+    } else {
+        setAndConstrainColumnHeight(heightAdjustedForSetOffset(multicolBlock->columnHeightAvailable()));
+    }
+
+    // Nuke previously stored minimum column height. Contents may have changed for all we know.
+    m_minimumColumnHeight = 0;
 }
 
-void RenderMultiColumnSet::computeLogicalHeight(LayoutUnit, LayoutUnit, LogicalExtentComputedValues& computedValues) const
+void RenderMultiColumnSet::computeLogicalHeight(LayoutUnit, LayoutUnit logicalTop, LogicalExtentComputedValues& computedValues) const
 {
-    RenderMultiColumnBlock* parentBlock = toRenderMultiColumnBlock(parent());
-    computedValues.m_extent = parentBlock->columnHeight();
+    computedValues.m_extent = m_computedColumnHeight;
+    computedValues.m_position = logicalTop;
 }
 
 LayoutUnit RenderMultiColumnSet::columnGap() const
 {
     // FIXME: Eventually we will cache the column gap when the widths of columns start varying, but for now we just
     // go to the parent block to get the gap.
     RenderMultiColumnBlock* parentBlock = toRenderMultiColumnBlock(parent());
     if (parentBlock->style()->hasNormalColumnGap())
         return parentBlock->style()->fontDescription().computedPixelSize(); // "1em" is recommended as the normal gap setting. Matches <p> margins.
     return parentBlock->style()->columnGap();
 }
 
 unsigned RenderMultiColumnSet::columnCount() 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 (!computedColumnHeight())
-        return 0;
-    
+        return 1;
+
     // Our portion rect determines our column count. We have as many columns as needed to fit all the content.
     LayoutUnit logicalHeightInColumns = flowThread()->isHorizontalWritingMode() ? flowThreadPortionRect().height() : flowThreadPortionRect().width();
-    return ceil(static_cast<float>(logicalHeightInColumns) / computedColumnHeight());
+    unsigned count = ceil(static_cast<float>(logicalHeightInColumns) / computedColumnHeight());
+    ASSERT(count >= 1);
+    return count;
 }
 
 LayoutRect RenderMultiColumnSet::columnRectAt(unsigned index) const
 {
     LayoutUnit colLogicalWidth = computedColumnWidth();
     LayoutUnit colLogicalHeight = computedColumnHeight();
     LayoutUnit colLogicalTop = borderBefore() + paddingBefore();
     LayoutUnit colLogicalLeft = borderAndPaddingLogicalLeft();
     LayoutUnit colGap = columnGap();
     if (style()->isLeftToRightDirection())
         colLogicalLeft += index * (colLogicalWidth + colGap);
     else
         colLogicalLeft += contentLogicalWidth() - colLogicalWidth - index * (colLogicalWidth + colGap);
 
     if (isHorizontalWritingMode())
         return LayoutRect(colLogicalLeft, colLogicalTop, colLogicalWidth, colLogicalHeight);
     return LayoutRect(colLogicalTop, colLogicalLeft, colLogicalHeight, colLogicalWidth);
 }
 
-unsigned RenderMultiColumnSet::columnIndexAtOffset(LayoutUnit offset) const
+unsigned RenderMultiColumnSet::columnIndexAtOffset(LayoutUnit offset, ColumnIndexCalculationMode mode) const
 {
     LayoutRect portionRect(flowThreadPortionRect());
+
+    // Handle the offset being out of range.
     LayoutUnit flowThreadLogicalTop = isHorizontalWritingMode() ? portionRect.y() : portionRect.x();
-    LayoutUnit flowThreadLogicalBottom = isHorizontalWritingMode() ? portionRect.maxY() : portionRect.maxX();
-    
-    // Handle the offset being out of range.
     if (offset < flowThreadLogicalTop)
         return 0;
-    if (offset >= flowThreadLogicalBottom)
-        return columnCount() - 1;
-    
+    // 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) {
+        LayoutUnit flowThreadLogicalBottom = isHorizontalWritingMode() ? portionRect.maxY() : portionRect.maxX();
+        if (offset >= flowThreadLogicalBottom)
+            return columnCount() - 1;
+    }
+
     // Just divide by the column height to determine the correct column.
     return static_cast<float>(offset - flowThreadLogicalTop) / computedColumnHeight();
 }
 
 LayoutRect RenderMultiColumnSet::flowThreadPortionRectAt(unsigned index) const
 {
     LayoutRect portionRect = flowThreadPortionRect();
     if (isHorizontalWritingMode())
         portionRect = LayoutRect(portionRect.x(), portionRect.y() + index * computedColumnHeight(), portionRect.width(), computedColumnHeight());
     else
@@ skipping 243 matching lines @@
         fragments.append(fragment);
     }
 }
 
 const char* RenderMultiColumnSet::renderName() const
 {    
     return "RenderMultiColumnSet";
 }
 
 }