[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 8c406893d07571d1629c973e3d42e52db300086a..73cb131959cf0c7cde73ef9de37bce84220b017d 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 WebCore {
 
 RenderMultiColumnFlowThread::RenderMultiColumnFlowThread()
-    : m_columnCount(1)
+    : m_lastSetWorkedOn(0)
+    , m_columnCount(1)
     , m_columnHeightAvailable(0)
+    , m_inLayout(false)
     , m_inBalancingPass(false)
     , m_needsColumnHeightsRecalculation(false)
     , m_progressionIsInline(true)
+    , m_beingEvacuated(false)
 {
     setFlowThreadState(InsideInFlowThread);
 }
@@ -70,21 +74,47 @@ 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;
+}
 
-    // 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());
+RenderBox* RenderMultiColumnFlowThread::nextColumnSetOrSpannerSiblingOf(const RenderBox* child)
+{
+    if (!child)
+        return 0;
+    if (RenderObject* sibling = child->nextSibling()) {
+        ASSERT(sibling->isBox());
+        return toRenderBox(sibling);
+    }
+    return 0;
+}
 
-    // Need to skip RenderBlockFlow's implementation of addChild(), or we'd get redirected right
-    // back here.
-    multiColumnBlockFlow()->RenderBlock::addChild(newSet);
+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;
+}
 
-    invalidateRegions();
+RenderMultiColumnSet* RenderMultiColumnFlowThread::findSetRendering(RenderObject* renderer) const
+{
+    for (RenderMultiColumnSet* multicolSet = firstMultiColumnSet(); multicolSet; multicolSet = multicolSet->nextSiblingMultiColumnSet()) {
+        if (multicolSet->renders(renderer))
+            return multicolSet;
+    }
+    return 0;
 }
 
 void RenderMultiColumnFlowThread::populate()
@@ -100,20 +130,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 +207,11 @@ void RenderMultiColumnFlowThread::layoutColumns(bool relayoutChildren, SubtreeLa
             // typically have changed.
             columnSet->resetColumnHeight();
         }
+        columnSet->resetFlow();
     }
 
     invalidateRegions();
-    m_needsColumnHeightsRecalculation = heightIsAuto();
+    m_needsColumnHeightsRecalculation = true;
     layout();
 }
 
@@ -257,6 +298,210 @@ 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;
+}
+
+static bool isValidColumnSpanner(RenderMultiColumnFlowThread* flowThread, RenderObject* descendant)

[rune, 2014/06/19 14:24:32]

Why not make this a member method of the RenderMultiColumnFlowThread class
instead (possibly rename since _is_ would not be a property of "this")?

[mstensho (USE GERRIT), 2014/08/26 09:43:58]

Done.

[rune, 2014/08/27 08:17:38]

Acknowledged.

+{
+    // We assume that we're inside the flow thread. This function is not to be called otherwise.
+    ASSERT(descendant->isDescendantOf(flowThread));
+
+    if (flowThread->isRenderPagedFlowThread())
+        return false; // Spanners are for true multicol only.
+
+    // 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 == flowThread;
+        }
+        ASSERT(ancestor->style()->columnSpan() != ColumnSpanAll || !isValidColumnSpanner(flowThread, ancestor));
+        if (ancestor->isUnsplittableForPagination())
+            return false;
+    }
+    ASSERT_NOT_REACHED();
+    return false;
+}
+
+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 wound otherwise occur (if it weren't a spanner) to becoming a sibling of the

[rune, 2014/06/19 14:24:33]

"where it _would_ otherwise ..."

[mstensho (USE GERRIT), 2014/08/26 09:43:58]

Done.

[rune, 2014/08/27 08:17:38]

Acknowledged.

+            // 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 (isValidColumnSpanner(this, 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->setNeedsLayoutAndFullRepaint();
+                    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 a two reasons: We need a way of separating inline

[rune, 2014/06/19 14:24:32]

"needed for a two reasons"?

[mstensho (USE GERRIT), 2014/08/26 09:43:58]

Done.

[rune, 2014/08/27 08:17:38]

Acknowledged.

+            // 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 to the next one.

[rune, 2014/06/19 14:24:33]

"move _on_ to the next one" perhaps?

[mstensho (USE GERRIT), 2014/08/26 09:43:58]

Done.

[rune, 2014/08/27 08:17:38]

Acknowledged.

+            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::flowThreadRelativeWillBeRemoved(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
+        // in the tree.

[rune, 2014/06/19 14:24:32]

"into the tree"

[mstensho (USE GERRIT), 2014/08/26 09:43:58]

Done.

[rune, 2014/08/27 08:17:38]

Acknowledged.

+        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->setNeedsLayoutAndFullRepaint();
+                }
+            }
+        }
+    }
+    // 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::flowThreadDescendantBoxLaidOut(RenderBox* descendant, LayoutUnit logicalBottomInFlowThread)
+{
+    if (!descendant->isRenderMultiColumnSpannerPlaceholder())
+        return;
+    RenderMultiColumnSpannerPlaceholder* placeholder = toRenderMultiColumnSpannerPlaceholder(descendant);
+
+    for (RenderBox* prev = previousColumnSetOrSpannerSiblingOf(placeholder->spanner()); prev; prev = previousColumnSetOrSpannerSiblingOf(prev)) {
+        if (prev->isRenderMultiColumnSet()) {
+            toRenderMultiColumnSet(prev)->endFlow(logicalBottomInFlowThread);
+            break;
+        }
+    }
+
+    for (RenderBox* next = nextColumnSetOrSpannerSiblingOf(placeholder->spanner()); next; next = nextColumnSetOrSpannerSiblingOf(next)) {
+        if (next->isRenderMultiColumnSet()) {
+            m_lastSetWorkedOn = toRenderMultiColumnSet(next);
+            m_lastSetWorkedOn->beginFlow(logicalBottomInFlowThread);
+            break;
+        }
+    }
+}
+
 void RenderMultiColumnFlowThread::computeLogicalHeight(LayoutUnit logicalHeight, LayoutUnit logicalTop, LogicalExtentComputedValues& computedValues) const
 {
     // We simply remain at our intrinsic height.
@@ -273,9 +518,23 @@ void RenderMultiColumnFlowThread::updateLogicalWidth()
 
 void RenderMultiColumnFlowThread::layout()
 {
+    ASSERT(!m_inLayout);
+    m_inLayout = 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_inLayout = false;
+    m_lastSetWorkedOn = 0;
 }
 
 void RenderMultiColumnFlowThread::setPageBreak(LayoutUnit offset, LayoutUnit spaceShortage)
@@ -297,16 +556,47 @@ void RenderMultiColumnFlowThread::updateMinimumPageHeight(LayoutUnit offset, Lay
         multicolSet->updateMinimumColumnHeight(minHeight);
 }
 
-RenderRegion* RenderMultiColumnFlowThread::regionAtBlockOffset(LayoutUnit /*offset*/) const
+RenderRegion* RenderMultiColumnFlowThread::regionAtBlockOffset(LayoutUnit offset) const
 {
-    // For now there's only one column set, so this is easy:
-    return firstMultiColumnSet();

[rune, 2014/06/19 14:24:33]

A single set is still the case for RenderPagedFlowThread, right?

[mstensho (USE GERRIT), 2014/08/26 09:43:58]

Yes.

[rune, 2014/08/27 08:17:38]

Acknowledged.

+    if (!m_inLayout)
+        return RenderFlowThread::regionAtBlockOffset(offset);
+
+    // Layout in progress. We are calculating the set heights as we speak, so the region 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()) {
+        do {
+            if (RenderMultiColumnSet* prev = columnSet->previousSiblingMultiColumnSet())
+                columnSet = prev;
+            else
+                break;
+        } while (offset < columnSet->logicalTopInFlowThread());
+    } else {
+        while (offset >= columnSet->logicalBottomInFlowThread()) {
+            RenderMultiColumnSet* next = columnSet->nextSiblingMultiColumnSet();
+            if (!next || !next->hasBeenFlowed())
+                break;

[rune, 2014/06/19 14:24:33]

If I understand this correctly, if we ask for a regionAtBlockOffset during
layout, and that offset is past the last set that has been flowed, return the
last flowed set.

Is that something that typically can happen? What does that mean? I guess that
depends on what that returned RenderRegion is used for during layout.

[mstensho (USE GERRIT), 2014/08/26 09:43:58]

Done.

I'm not aware of any usecase for searching forwards past the last set worked on,
so I'm removing that code. Additionally, I'm documenting why we have to search
backwards sometimes.

[rune, 2014/08/27 08:17:38]

Acknowledged.

+            columnSet = next;
+        }
+    }
+    return columnSet;
 }
 
-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 = toRenderMultiColumnSet(regionAtBlockOffset(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;