[New Multicolumn] Add support for column-span:all

Source/core/rendering/RenderMultiColumnFlowThread.cpp

Index: Source/core/rendering/RenderMultiColumnFlowThread.cpp
diff --git a/Source/core/rendering/RenderMultiColumnFlowThread.cpp b/Source/core/rendering/RenderMultiColumnFlowThread.cpp
index 3bacd490d4ec1a851be613a0f9ec31f375ca95dc..ab48ffe3a845a57d703eca14f90f7f6d7bc8acae 100644
--- a/Source/core/rendering/RenderMultiColumnFlowThread.cpp
+++ b/Source/core/rendering/RenderMultiColumnFlowThread.cpp
@@ -27,15 +27,19 @@
 #include "core/rendering/RenderMultiColumnFlowThread.h"
 
 #include "core/rendering/RenderMultiColumnSet.h"
+#include "core/rendering/RenderMultiColumnSpannerPlaceholder.h"
 
 namespace blink {
 
 RenderMultiColumnFlowThread::RenderMultiColumnFlowThread()
-    : m_columnCount(1)
+    : m_lastSetWorkedOn(0)
+    , m_columnCount(1)
     , m_columnHeightAvailable(0)
+    , m_columnSetHeightsAreUnknown(false)
     , m_inBalancingPass(false)
     , m_needsColumnHeightsRecalculation(false)
     , m_progressionIsInline(true)
+    , m_beingEvacuated(false)
 {
     setFlowThreadState(InsideInFlowThread);
 }
@@ -70,21 +74,82 @@ RenderMultiColumnSet* RenderMultiColumnFlowThread::lastMultiColumnSet() const
     return 0;
 }
 
-void RenderMultiColumnFlowThread::addChild(RenderObject* newChild, RenderObject* beforeChild)
+RenderBox* RenderMultiColumnFlowThread::firstColumnSetOrSpanner() const
 {
-    RenderBlockFlow::addChild(newChild, beforeChild);
-    if (firstMultiColumnSet())
-        return;
+    if (RenderObject* sibling = nextSibling()) {
+        ASSERT(sibling->isBox());
+        ASSERT(sibling->isRenderMultiColumnSet() || findColumnSpannerPlaceholder(toRenderBox(sibling)));
+        return toRenderBox(sibling);
+    }
+    return 0;
+}
+
+RenderBox* RenderMultiColumnFlowThread::nextColumnSetOrSpannerSiblingOf(const RenderBox* child)
+{
+    if (!child)
+        return 0;
+    if (RenderObject* sibling = child->nextSibling()) {
+        ASSERT(sibling->isBox());
+        return toRenderBox(sibling);
+    }
+    return 0;
+}
+
+RenderBox* RenderMultiColumnFlowThread::previousColumnSetOrSpannerSiblingOf(const RenderBox* child)
+{
+    if (!child)
+        return 0;
+    if (RenderObject* sibling = child->previousSibling()) {
+        ASSERT(sibling->isBox());
+        if (sibling->isRenderFlowThread())
+            return 0;
+        return toRenderBox(sibling);
+    }
+    return 0;
+}
 
-    // For now we only create one column set. It's created as soon as the multicol container gets
-    // any content at all.
-    RenderMultiColumnSet* newSet = RenderMultiColumnSet::createAnonymous(this, multiColumnBlockFlow()->style());
+RenderMultiColumnSet* RenderMultiColumnFlowThread::findSetRendering(RenderObject* renderer) const
+{
+    RenderMultiColumnSet* multicolSet = firstMultiColumnSet();
+    if (!multicolSet)
+        return 0;
 
-    // Need to skip RenderBlockFlow's implementation of addChild(), or we'd get redirected right
-    // back here.
-    multiColumnBlockFlow()->RenderBlock::addChild(newSet);
+    if (!multicolSet->nextSiblingMultiColumnSet()) {
+        // There is only one set. This is easy, then: if it's in the flow thread, it's part of the set.
+        return renderer->isDescendantOf(this) ? multicolSet : 0;
+    }
 
-    invalidateRegions();
+    // This is SLOW! But luckily very uncommon. You need to dynamically insert a spanner into the
+    // middle of the tree to trigger this.
+    for (; multicolSet; multicolSet = multicolSet->nextSiblingMultiColumnSet()) {
+        RenderObject* startRenderer;
+        if (RenderBox* sibling = previousColumnSetOrSpannerSiblingOf(multicolSet)) {
+            // Adjacent sets should not occur. Currently we would have no way of figuring out what each
+            // of them contains then.
+            ASSERT(!sibling->isRenderMultiColumnSet());
+            startRenderer = findColumnSpannerPlaceholder(sibling)->nextInPreOrderAfterChildren(this);
+        } else {
+            startRenderer = firstChild();
+        }
+        ASSERT(startRenderer);
+
+        RenderObject* stopRenderer;
+        if (RenderBox* sibling = nextColumnSetOrSpannerSiblingOf(multicolSet)) {
+            // Adjacent sets should not occur. Currently we would have no way of figuring out what each
+            // of them contains then.
+            ASSERT(!sibling->isRenderMultiColumnSet());
+            stopRenderer = findColumnSpannerPlaceholder(sibling);
+        } else {
+            stopRenderer = 0;
+        }
+
+        for (RenderObject* walker = startRenderer; walker != stopRenderer; walker = walker->nextInPreOrder(this)) {
+            if (walker == renderer)
+                return multicolSet;
+        }
+    }
+
+    return 0;
 }
 
 void RenderMultiColumnFlowThread::populate()
@@ -100,20 +165,30 @@ void RenderMultiColumnFlowThread::populate()
 void RenderMultiColumnFlowThread::evacuateAndDestroy()
 {
     RenderBlockFlow* multicolContainer = multiColumnBlockFlow();
+    m_beingEvacuated = true;
 
-    // Remove all sets.
-    while (RenderMultiColumnSet* columnSet = firstMultiColumnSet())
-        columnSet->destroy();
-
-    ASSERT(!previousSibling());
-    ASSERT(!nextSibling());
-
-    // Finally we can promote all flow thread's children. Before we move them to the flow thread's
+    // First promote all children of the flow thread. Before we move them to the flow thread's
     // container, we need to unregister the flow thread, so that they aren't just re-added again to
     // the flow thread that we're trying to empty.
     multicolContainer->resetMultiColumnFlowThread();
     moveAllChildrenTo(multicolContainer, true);
 
+    // Move spanners back to their original DOM position in the tree, and destroy the placeholders.
+    SpannerMap::iterator it;
+    while ((it = m_spannerMap.begin()) != m_spannerMap.end()) {
+        RenderBox* spanner = it->key;
+        RenderMultiColumnSpannerPlaceholder* placeholder = it->value;
+        RenderBlockFlow* originalContainer = toRenderBlockFlow(placeholder->parent());
+        multicolContainer->removeChild(spanner);
+        originalContainer->addChild(spanner, placeholder);
+        placeholder->destroy();
+        m_spannerMap.remove(it);
+    }
+
+    // Remove all sets.
+    while (RenderMultiColumnSet* columnSet = firstMultiColumnSet())
+        columnSet->destroy();
+
     // FIXME: it's scary that neither destroy() nor the move*Children* methods take care of this,
     // and instead leave you with dangling root line box pointers. But since this is how it is done
     // in other parts of the code that deal with reparenting renderers, let's do the cleanup on our
@@ -167,10 +242,11 @@ void RenderMultiColumnFlowThread::layoutColumns(bool relayoutChildren, SubtreeLa
             // typically have changed.
             columnSet->resetColumnHeight();
         }
+        columnSet->resetFlow();
     }
 
     invalidateRegions();
-    m_needsColumnHeightsRecalculation = heightIsAuto();
+    m_needsColumnHeightsRecalculation = true;
     layout();
 }
 
@@ -206,6 +282,25 @@ bool RenderMultiColumnFlowThread::recalculateColumnHeights()
     return needsRelayout;
 }
 
+void RenderMultiColumnFlowThread::advanceToNextColumnSet(RenderMultiColumnSpannerPlaceholder* placeholder)
+{
+    LayoutUnit logicalBottomInFlowThread = placeholder->offsetFromLogicalTopOfFirstPage();
+    for (RenderBox* prev = previousColumnSetOrSpannerSiblingOf(placeholder->spanner()); prev; prev = previousColumnSetOrSpannerSiblingOf(prev)) {
+        if (!prev->isRenderMultiColumnSet())
+            continue;
+        toRenderMultiColumnSet(prev)->endFlow(logicalBottomInFlowThread);
+        break;
+    }
+
+    for (RenderBox* next = nextColumnSetOrSpannerSiblingOf(placeholder->spanner()); next; next = nextColumnSetOrSpannerSiblingOf(next)) {
+        if (!next->isRenderMultiColumnSet())
+            continue;
+        m_lastSetWorkedOn = toRenderMultiColumnSet(next);
+        m_lastSetWorkedOn->beginFlow(logicalBottomInFlowThread);
+        break;
+    }
+}
+
 void RenderMultiColumnFlowThread::calculateColumnCountAndWidth(LayoutUnit& width, unsigned& count) const
 {
     RenderBlock* columnBlock = multiColumnBlockFlow();
@@ -228,6 +323,38 @@ void RenderMultiColumnFlowThread::calculateColumnCountAndWidth(LayoutUnit& width
     }
 }
 
+bool RenderMultiColumnFlowThread::isDescendantValidColumnSpanner(RenderObject* descendant) const
+{
+    // We assume that we're inside the flow thread. This function is not to be called otherwise.
+    ASSERT(descendant->isDescendantOf(this));
+
+    // First make sure that the renderer itself has the right properties for becoming a spanner.
+    RenderStyle* style = descendant->style();
+    if (style->columnSpan() != ColumnSpanAll || !descendant->isBox() || descendant->isFloatingOrOutOfFlowPositioned())
+        return false;
+
+    RenderBlock* container = descendant->containingBlock();
+    if (!container->isRenderBlockFlow() || container->childrenInline()) {
+        // Needs to be block-level.
+        return false;
+    }
+
+    // This looks like a spanner, but if we're inside something unbreakable, it's not to be treated as one.
+    for (RenderBox* ancestor = toRenderBox(descendant)->parentBox(); ancestor; ancestor = ancestor->parentBox()) {
+        if (ancestor->isRenderFlowThread()) {
+            // Don't allow any intervening non-multicol fragmentation contexts. The spec doesn't say
+            // anything about disallowing this, but it's just going to be too complicated to
+            // implement (not to mention specify behavior).
+            return ancestor == this;
+        }
+        ASSERT(ancestor->style()->columnSpan() != ColumnSpanAll || !isDescendantValidColumnSpanner(ancestor));
+        if (ancestor->isUnsplittableForPagination())
+            return false;
+    }
+    ASSERT_NOT_REACHED();
+    return false;
+}
+
 const char* RenderMultiColumnFlowThread::renderName() const
 {
     return "RenderMultiColumnFlowThread";
@@ -256,6 +383,153 @@ void RenderMultiColumnFlowThread::willBeRemovedFromTree()
     RenderFlowThread::willBeRemovedFromTree();
 }
 
+RenderObject* RenderMultiColumnFlowThread::resolveMovedChild(RenderObject* child) const
+{
+    if (child->style()->columnSpan() != ColumnSpanAll || !child->isBox()) {
+        // We only need to resolve for column spanners.
+        return child;
+    }
+    // The renderer for the actual DOM node that establishes a spanner is moved from its original
+    // location in the render tree to becoming a sibling of the column sets. In other words, it's
+    // moved out from the flow thread (and becomes a sibling of it). When we for instance want to
+    // create and insert a renderer for the sibling node immediately preceding the spanner, we need
+    // to map that spanner renderer to the spanner's placeholder, which is where the new inserted
+    // renderer belongs.
+    if (RenderMultiColumnSpannerPlaceholder* placeholder = findColumnSpannerPlaceholder(toRenderBox(child)))
+        return placeholder;
+
+    // This is an invalid spanner, or its placeholder hasn't been created yet. This happens when
+    // moving an entire subtree into the flow thread, when we are processing the insertion of this
+    // spanner's preceding sibling, and we obviously haven't got as far as processing this spanner
+    // yet.
+    return child;
+}
+
+void RenderMultiColumnFlowThread::flowThreadDescendantInserted(RenderObject* descendant)
+{
+    if (m_beingEvacuated)
+        return;
+    RenderObject* subtreeRoot = descendant;
+    for (; descendant; descendant = descendant->nextInPreOrder(subtreeRoot)) {
+        if (descendant->isRenderMultiColumnSpannerPlaceholder()) {
+            // A spanner's placeholder has been inserted. The actual spanner renderer is moved from
+            // where it would otherwise occur (if it weren't a spanner) to becoming a sibling of the
+            // column sets.
+            RenderMultiColumnSpannerPlaceholder* placeholder = toRenderMultiColumnSpannerPlaceholder(descendant);
+            ASSERT(!m_spannerMap.get(placeholder->spanner()));
+            m_spannerMap.add(placeholder->spanner(), placeholder);
+            ASSERT(!placeholder->slowFirstChild()); // There should be no children here, but if there are, we ought to skip them.
+            continue;
+        }
+        RenderBlockFlow* multicolContainer = multiColumnBlockFlow();
+        RenderObject* nextRendererInFlowThread = descendant->nextInPreOrderAfterChildren(this);
+        RenderObject* insertBeforeMulticolChild = 0;
+        if (isDescendantValidColumnSpanner(descendant)) {
+            // This is a spanner (column-span:all). Such renderers are moved from where they would
+            // otherwise occur in the render tree to becoming a direct child of the multicol container,
+            // so that they live among the column sets. This simplifies the layout implementation, and
+            // basically just relies on regular block layout done by the RenderBlockFlow that
+            // establishes the multicol container.
+            RenderBlockFlow* container = toRenderBlockFlow(descendant->parent());
+            RenderMultiColumnSet* setToSplit = 0;
+            if (nextRendererInFlowThread) {
+                setToSplit = findSetRendering(descendant);
+                if (setToSplit) {
+                    setToSplit->setNeedsLayoutAndFullPaintInvalidation();
+                    insertBeforeMulticolChild = setToSplit->nextSibling();
+                }
+            }
+            // Moving a spanner's renderer so that it becomes a sibling of the column sets requires us
+            // to insert an anonymous placeholder in the tree where the spanner's renderer otherwise
+            // would have been. This is needed for two reasons: We need a way of separating inline
+            // content before and after the spanner, so that it becomes separate line boxes. Secondly,
+            // this placeholder serves as a break point for column sets, so that, when encountered, we
+            // end flowing one column set and move on to the next one.
+            RenderMultiColumnSpannerPlaceholder* placeholder = RenderMultiColumnSpannerPlaceholder::createAnonymous(this, toRenderBox(descendant), container->style());
+            container->addChild(placeholder, descendant->nextSibling());
+            container->removeChild(descendant);
+            multicolContainer->RenderBlock::addChild(descendant, insertBeforeMulticolChild);
+
+            // The spanner has now been moved out from the flow thread, but we don't want to
+            // examine its children anyway. They are all part of the spanner and shouldn't trigger
+            // creation of column sets or anything like that. Continue at its original position in
+            // the tree, i.e. where the placeholder was just put.
+            if (subtreeRoot == descendant)
+                subtreeRoot = placeholder;
+            descendant = placeholder;
+        } else {
+            // This is regular multicol content, i.e. not part of a spanner.
+            if (nextRendererInFlowThread && nextRendererInFlowThread->isRenderMultiColumnSpannerPlaceholder()) {
+                // Inserted right before a spanner. Is there a set for us there?
+                RenderMultiColumnSpannerPlaceholder* placeholder = toRenderMultiColumnSpannerPlaceholder(nextRendererInFlowThread);
+                if (RenderObject* previous = placeholder->spanner()->previousSibling()) {
+                    if (previous->isRenderMultiColumnSet())
+                        continue; // There's already a set there. Nothing to do.
+                }
+                insertBeforeMulticolChild = placeholder->spanner();
+            } else if (RenderMultiColumnSet* lastSet = lastMultiColumnSet()) {
+                // This child is not an immediate predecessor of a spanner, which means that if this
+                // child precedes a spanner at all, there has to be a column set created for us there
+                // already. If it doesn't precede any spanner at all, on the other hand, we need a
+                // column set at the end of the multicol container. We don't really check here if the
+                // child inserted precedes any spanner or not (as that's an expensive operation). Just
+                // make sure we have a column set at the end. It's no big deal if it remains unused.
+                if (!lastSet->nextSibling())
+                    continue;
+            }
+        }
+        // Need to create a new column set when there's no set already created. We also always insert
+        // another column set after a spanner. Even if it turns out that there are no renderers
+        // following the spanner, there may be bottom margins there, which take up space.
+        RenderMultiColumnSet* newSet = RenderMultiColumnSet::createAnonymous(this, multicolContainer->style());
+        multicolContainer->RenderBlock::addChild(newSet, insertBeforeMulticolChild);
+        invalidateRegions();
+
+        // We cannot handle immediate column set siblings at the moment (and there's no need for
+        // it, either). There has to be at least one spanner separating them.
+        ASSERT(!previousColumnSetOrSpannerSiblingOf(newSet) || !previousColumnSetOrSpannerSiblingOf(newSet)->isRenderMultiColumnSet());
+        ASSERT(!nextColumnSetOrSpannerSiblingOf(newSet) || !nextColumnSetOrSpannerSiblingOf(newSet)->isRenderMultiColumnSet());
+    }
+}
+
+void RenderMultiColumnFlowThread::flowThreadDescendantOrSiblingWillBeRemoved(RenderObject* relative)
+{
+    if (m_beingEvacuated)
+        return;
+    invalidateRegions();
+    if (relative->isRenderMultiColumnSpannerPlaceholder()) {
+        // Remove the map entry for this spanner, but leave the actual spanner renderer alone. Also
+        // keep the reference to the spanner, since the placeholder may be about to be re-inserted
+        // into the tree.
+        ASSERT(relative->isDescendantOf(this));
+        m_spannerMap.remove(toRenderMultiColumnSpannerPlaceholder(relative)->spanner());
+        return;
+    }
+    if (relative->style()->columnSpan() == ColumnSpanAll) {
+        if (relative->parent() != parent())
+            return; // not a valid spanner.
+
+        // The placeholder may already have been removed, but if it hasn't, do so now.
+        if (RenderMultiColumnSpannerPlaceholder* placeholder = m_spannerMap.get(toRenderBox(relative))) {
+            placeholder->containingBlock()->RenderBlock::removeChild(placeholder);
+            m_spannerMap.remove(toRenderBox(relative));
+        }
+
+        if (RenderObject* next = relative->nextSibling()) {
+            if (RenderObject* previous = relative->previousSibling()) {
+                if (previous->isRenderMultiColumnSet() && next->isRenderMultiColumnSet()) {
+                    // Merge two sets that no longer will be separated by a spanner.
+                    next->destroy();
+                    previous->setNeedsLayoutAndFullPaintInvalidation();
+                }
+            }
+        }
+    }
+    // Note that we might end up with empty column sets if all column content is removed. That's no
+    // big deal though (and locating them would be expensive), and they will be found and re-used if
+    // content is added again later.
+}
+
 void RenderMultiColumnFlowThread::computeLogicalHeight(LayoutUnit logicalHeight, LayoutUnit logicalTop, LogicalExtentComputedValues& computedValues) const
 {
     // We simply remain at our intrinsic height.
@@ -272,9 +546,23 @@ void RenderMultiColumnFlowThread::updateLogicalWidth()
 
 void RenderMultiColumnFlowThread::layout()
 {
+    ASSERT(!m_columnSetHeightsAreUnknown);
+    m_columnSetHeightsAreUnknown = true;
+    m_lastSetWorkedOn = 0;
+    if (RenderBox* first = firstColumnSetOrSpanner()) {
+        if (first->isRenderMultiColumnSet()) {
+            m_lastSetWorkedOn = toRenderMultiColumnSet(first);
+            m_lastSetWorkedOn->beginFlow(LayoutUnit());
+        }
+    }
     RenderFlowThread::layout();
-    if (RenderMultiColumnSet* lastSet = lastMultiColumnSet())
+    if (RenderMultiColumnSet* lastSet = lastMultiColumnSet()) {
+        if (!nextColumnSetOrSpannerSiblingOf(lastSet))
+            lastSet->endFlow(logicalHeight());
         lastSet->expandToEncompassFlowThreadContentsIfNeeded();
+    }
+    m_columnSetHeightsAreUnknown = false;
+    m_lastSetWorkedOn = 0;
 }
 
 void RenderMultiColumnFlowThread::setPageBreak(LayoutUnit offset, LayoutUnit spaceShortage)
@@ -296,16 +584,61 @@ void RenderMultiColumnFlowThread::updateMinimumPageHeight(LayoutUnit offset, Lay
         multicolSet->updateMinimumColumnHeight(minHeight);
 }
 
-RenderMultiColumnSet* RenderMultiColumnFlowThread::columnSetAtBlockOffset(LayoutUnit /*offset*/) const
+RenderMultiColumnSet* RenderMultiColumnFlowThread::columnSetAtBlockOffset(LayoutUnit offset) const
 {
-    // For now there's only one column set, so this is easy:
-    return firstMultiColumnSet();
+    if (m_columnSetHeightsAreUnknown) {
+        // Layout in progress. We are calculating the set heights as we speak, so the column set range
+        // information is not up-to-date.
+
+        RenderMultiColumnSet* columnSet = m_lastSetWorkedOn ? m_lastSetWorkedOn : firstMultiColumnSet();
+        if (!columnSet) {
+            // If there's no set, bail. This multicol is empty or only consists of spanners. There
+            // are no regions.
+            return 0;
+        }
+        // The last set worked on is a good guess. But if we're not within the bounds, search for the
+        // right one.
+        if (offset < columnSet->logicalTopInFlowThread()) {
+            // In some cases we need to search backwards for a column set we've advanced past. This
+            // happens when a block crosses a column set boundary, and someone wants to examine or
+            // adjust its top after or during layout. FIXME: If its top acually gets adjusted
+            // (e.g. because of an incorrect initial top position estimate), this may be problematic
+            // for column balancing, but returning the correct set here is at least better than
+            // nothing.
+            do {
+                if (RenderMultiColumnSet* prev = columnSet->previousSiblingMultiColumnSet())
+                    columnSet = prev;
+                else
+                    break;
+            } while (offset < columnSet->logicalTopInFlowThread());
+        } else {
+            // We currently don't support searching forwards for a set, and there should be no need
+            // for it, either.
+            ASSERT(offset < columnSet->logicalBottomInFlowThread());
+        }
+        return columnSet;
+    }
+
+    ASSERT(!m_regionsInvalidated);
+    if (offset <= 0)
+        return m_multiColumnSetList.isEmpty() ? 0 : m_multiColumnSetList.first();
+
+    MultiColumnSetSearchAdapter adapter(offset);
+    m_multiColumnSetIntervalTree.allOverlapsWithAdapter<MultiColumnSetSearchAdapter>(adapter);
+
+    // If no set was found, the offset is in the flow thread overflow.
+    if (!adapter.result() && !m_multiColumnSetList.isEmpty())
+        return m_multiColumnSetList.last();
+    return adapter.result();
 }
 
-bool RenderMultiColumnFlowThread::addForcedRegionBreak(LayoutUnit offset, RenderObject* /*breakChild*/, bool /*isBefore*/, LayoutUnit* offsetBreakAdjustment)
+bool RenderMultiColumnFlowThread::addForcedRegionBreak(LayoutUnit offset, RenderObject* breakChild, bool /*isBefore*/, LayoutUnit* offsetBreakAdjustment)
 {
     if (RenderMultiColumnSet* multicolSet = columnSetAtBlockOffset(offset)) {
-        multicolSet->addContentRun(offset);
+        // Spanner placeholders force a break (to make sure that the unused part of the last column
+        // is empty), but this break should not affect column balancing.
+        if (!breakChild->isRenderMultiColumnSpannerPlaceholder())
+            multicolSet->addContentRun(offset);
         if (offsetBreakAdjustment)
             *offsetBreakAdjustment = pageLogicalHeightForOffset(offset) ? pageRemainingLogicalHeightForOffset(offset, IncludePageBoundary) : LayoutUnit();
         return true;