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

Source/core/rendering/RenderMultiColumnFlowThread.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
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  * PROFITS; OR BUSINESS IN..0TERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF  ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
 #include "config.h"
 #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_inLayout(false)
     , m_inBalancingPass(false)
     , m_needsColumnHeightsRecalculation(false)
     , m_progressionIsInline(true)
+    , m_beingEvacuated(false)
 {
     setFlowThreadState(InsideInFlowThread);
 }
 
 RenderMultiColumnFlowThread::~RenderMultiColumnFlowThread()
 {
 }
 
 RenderMultiColumnFlowThread* RenderMultiColumnFlowThread::createAnonymous(Document& document, RenderStyle* parentStyle)
 {
@@ skipping 14 matching lines @@
 
 RenderMultiColumnSet* RenderMultiColumnFlowThread::lastMultiColumnSet() const
 {
     for (RenderObject* sibling = multiColumnBlockFlow()->lastChild(); sibling; sibling = sibling->previousSibling()) {
         if (sibling->isRenderMultiColumnSet())
             return toRenderMultiColumnSet(sibling);
     }
     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
+{
+    RenderMultiColumnSet* multicolSet = firstMultiColumnSet();
+    if (!multicolSet)
+        return 0;
+
+    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;
+    }
+
+    // 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;

[rune, 2014/08/27 09:23:44]

The code in lastRendererInFlowThread() used flowThread()->lastLeafChild() for
this, will 0 make it go further than necessary?

[mstensho (USE GERRIT), 2014/08/27 10:12:36]

No, because the stayWithin parameter to nextInPreOrder() is the flow thread.

[rune, 2014/08/27 10:22:27]

Acknowledged.

+        }
+
+        for (RenderObject* walker = startRenderer; walker != stopRenderer; walker = walker->nextInPreOrder(this)) {
+            if (walker == renderer)
+                return multicolSet;
+        }
+    }
+
+    return 0;
 }
 
 void RenderMultiColumnFlowThread::populate()
 {
     RenderBlockFlow* multicolContainer = multiColumnBlockFlow();
     ASSERT(!nextSibling());
     // Reparent children preceding the flow thread into the flow thread. It's multicol content
     // now. At this point there's obviously nothing after the flow thread, but renderers (column
     // sets and spanners) will be inserted there as we insert elements into the flow thread.
     multicolContainer->moveChildrenTo(this, multicolContainer->firstChild(), this, true);
 }
 
 void RenderMultiColumnFlowThread::evacuateAndDestroy()
 {
     RenderBlockFlow* multicolContainer = multiColumnBlockFlow();
+    m_beingEvacuated = true;
+
+    // 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.

[Julien - ping for review, 2014/09/03 23:22:23]

This is a big concern that we don't respect the DOM ordering.

The few examples that we have of differences between the DOM and the render tree
have been a security nightmare:
- CSS tables with the anonymous wrappers: this is the reason you have to check
if |beforeChild| has the same parent you do in addChild. This is still the cause
of much pain.
- generated content used to be anonymous elements and was also a pain so we
converted it into PseudoElement.
- run-in

Ideally we would rather have something that keeps the DOM intact and uses an
external data structure to re-order the elements at layout / paint time. This is
akin to how 'order' is implemented in CSS grid or flexbox.

You wanted to reuse RenderBlockFlow::layoutBlock's logic (which is great), you
will want to look at the layoutSpecialExcludedChild logic, which should be able
to accommodate your needs.

[mstensho (USE GERRIT), 2014/09/04 12:14:02]

I understand, and I admit that this is easily the biggest inconvenience with the
implementation I chose. It was chosen because of its low amount of intrusiveness
in other parts of layout (admittedly, there IS some stuff in RenderObject and
RenderBlockFlow with this solution, but other solutions would cause more). Once
renderer reordering is done, everything is straight-forward. The spanner becomes
a child of the multicol container, so that it gets the right size without any
hacks or hooks in the common/central rendering classes, and is positioned nicely
between column sets, and everything kind of Just Works. But I don't know... Too
much dynamite just to make it Just Work?

Another solution I was experimenting with early on didn't require this renderer
reordering. Instead, a spanner was left where it was defined in the DOM, inside
the flow thread. There would instead be inserted a special "column set"/"region
thing" for it among the other regular column sets. The spanner was essentially
part of the flow thread, only that we had to do some tricks when it came to
sizing (you need to use the ancestor multicol container to calculate your
available width, instead of just examining your parent block, because that
parent block is inside a column and is therefore much narrower). I seem to
recall messing with RenderObject::containingBlock() (or the other one with a
similar name, or maybe both) to achieve this. All in all, it worked, but it
required a non-negligible amount of hooks here and there in the code. So I went
for the renderer reparenting solution instead. Which incidentally is the
solution that David Hyatt initially suggested too. :)

A third solution could be to do something similar to what the current/old
implementation does: Insert anonymous multicol containers before and after the
spanner, and turn the actual multicol container into a regular block. This is
intrusive in the RenderBlock code, and I suppose this is code we should rather
get rid of, rather than using it in the new multicol implementation. I'm talking
about lots of stuff in RenderBlock::addChild*() (and methods like splitBlocks(),
splitFlow(), makeChildrenAnonymousColumnBlocks(), etc.) that's only there
because of the current/old multicol implementation of spanners.
The 'order' property, as far as I know, only reorders within the same container.
Pretty similar to the section reordering in RenderTable  (topSection(),
sectionBelow(). etc.), I guess? Multicol spanners are reparented.
I'm not sure how layoutSpecialExcludedChild() would help. The spanner may not be
a direct child of the multicol container (it may be inside blocks, tables and
what not). Besides, there may be more than one of them, so what would
layoutSpecialExcludedChild() return? I have a feeling that I misunderstood you
here. :)

[Julien - ping for review, 2014/09/04 17:47:24]

It makes me very nervous. The reason is that all cases where the render tree
doesn't match the DOM tree, we have had a security / maintenance nightmare.

If you look at RenderMultiColumnFlowThread::flowThreadDescendantInserted, the
logic makes a ton of assumption about the structure of the tree, some of which
will probably be wrong.
The question is how intrusive is intrusive. :)

Without some details, it's difficult to say if it's an acceptable level of
intrusiveness, especially since we complained about the region code being too
intrusive.
Yes, that was one of the reason we invoked to remove the region code so it's
probably a show-stopper.
I was thinking about extending the logic to allow multiple excluded children. We
can redesign the API to make sense with that in mind.

[mstensho (USE GERRIT), 2014/09/10 21:40:53]

The answer is here (well, maybe): :)
https://codereview.chromium.org/551263005/

Take a look at files like RenderBlockFlow.cpp and let me know what you think.
Note that this has to be cleaned up (and documented), but you should get the
general idea.

+    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();
 
-    ASSERT(!previousSibling());
-    ASSERT(!nextSibling());
-
-    // Finally we can promote all flow thread's children. 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);
-
     // 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
     // own here as well.
     deleteLineBoxTree();
 
     destroy();
 }
 
 LayoutSize RenderMultiColumnFlowThread::columnOffset(const LayoutPoint& point) const
@@ skipping 33 matching lines @@
         m_needsColumnHeightsRecalculation = false;
         return;
     }
 
     for (RenderMultiColumnSet* columnSet = firstMultiColumnSet(); columnSet; columnSet = columnSet->nextSiblingMultiColumnSet()) {
         if (!m_inBalancingPass) {
             // This is the initial layout pass. We need to reset the column height, because contents
             // typically have changed.
             columnSet->resetColumnHeight();
         }
+        columnSet->resetFlow();
     }
 
     invalidateRegions();
-    m_needsColumnHeightsRecalculation = heightIsAuto();
+    m_needsColumnHeightsRecalculation = true;
     layout();
 }
 
 bool RenderMultiColumnFlowThread::recalculateColumnHeights()
 {
     // All column sets that needed layout have now been laid out, so we can finally validate them.
     validateRegions();
 
     if (!m_needsColumnHeightsRecalculation)
         return false;
@@ skipping 15 matching lines @@
         }
     }
 
     if (needsRelayout)
         setChildNeedsLayout(MarkOnlyThis);
 
     m_inBalancingPass = needsRelayout;
     return needsRelayout;
 }
 
+void RenderMultiColumnFlowThread::advanceToNextColumnSet(RenderMultiColumnSpannerPlaceholder* placeholder)
+{
+    LayoutUnit logicalBottomInFlowThread = placeholder->offsetFromLogicalTopOfFirstPage();
+    for (RenderBox* prev = previousColumnSetOrSpannerSiblingOf(placeholder->spanner()); prev; prev = previousColumnSetOrSpannerSiblingOf(prev)) {
+        if (prev->isRenderMultiColumnSet()) {

[Julien - ping for review, 2014/09/03 23:22:23]

Nit: We usually prefer early return / break.

[mstensho (USE GERRIT), 2014/09/04 12:14:02]

Done.

+            toRenderMultiColumnSet(prev)->endFlow(logicalBottomInFlowThread);
+            break;
+        }
+    }
+
+    for (RenderBox* next = nextColumnSetOrSpannerSiblingOf(placeholder->spanner()); next; next = nextColumnSetOrSpannerSiblingOf(next)) {
+        if (next->isRenderMultiColumnSet()) {

[Julien - ping for review, 2014/09/03 23:22:23]

Same comment.

[mstensho (USE GERRIT), 2014/09/04 12:14:02]

Done.

+            m_lastSetWorkedOn = toRenderMultiColumnSet(next);
+            m_lastSetWorkedOn->beginFlow(logicalBottomInFlowThread);
+            break;
+        }
+    }
+}
+
 void RenderMultiColumnFlowThread::calculateColumnCountAndWidth(LayoutUnit& width, unsigned& count) const
 {
     RenderBlock* columnBlock = multiColumnBlockFlow();
     const RenderStyle* columnStyle = columnBlock->style();
     LayoutUnit availableWidth = columnBlock->contentLogicalWidth();
     LayoutUnit columnGap = columnBlock->columnGap();
     LayoutUnit computedColumnWidth = max<LayoutUnit>(1, LayoutUnit(columnStyle->columnWidth()));
     unsigned computedColumnCount = max<int>(1, columnStyle->columnCount());
 
     ASSERT(!columnStyle->hasAutoColumnCount() || !columnStyle->hasAutoColumnWidth());
     if (columnStyle->hasAutoColumnWidth() && !columnStyle->hasAutoColumnCount()) {
         count = computedColumnCount;
         width = std::max<LayoutUnit>(0, (availableWidth - ((count - 1) * columnGap)) / count);
     } else if (!columnStyle->hasAutoColumnWidth() && columnStyle->hasAutoColumnCount()) {
         count = std::max<LayoutUnit>(1, (availableWidth + columnGap) / (computedColumnWidth + columnGap));
         width = ((availableWidth + columnGap) / count) - columnGap;
     } else {
         count = std::max<LayoutUnit>(std::min<LayoutUnit>(computedColumnCount, (availableWidth + columnGap) / (computedColumnWidth + columnGap)), 1);
         width = ((availableWidth + columnGap) / count) - columnGap;
     }
 }
 
+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";
 }
 
 void RenderMultiColumnFlowThread::addRegionToThread(RenderMultiColumnSet* columnSet)
 {
     if (RenderMultiColumnSet* nextSet = columnSet->nextSiblingMultiColumnSet()) {
         RenderMultiColumnSetList::iterator it = m_multiColumnSetList.find(nextSet);
         ASSERT(it != m_multiColumnSetList.end());
         m_multiColumnSetList.insertBefore(it, columnSet);
     } else {
         m_multiColumnSetList.add(columnSet);
     }
     columnSet->setIsValid(true);
 }
 
 void RenderMultiColumnFlowThread::willBeRemovedFromTree()
 {
     // Detach all column sets from the flow thread. Cannot destroy them at this point, since they
     // are siblings of this object, and there may be pointers to this object's sibling somewhere
     // further up on the call stack.
     for (RenderMultiColumnSet* columnSet = firstMultiColumnSet(); columnSet; columnSet = columnSet->nextSiblingMultiColumnSet())
         columnSet->detachRegion();
     multiColumnBlockFlow()->resetMultiColumnFlowThread();
     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::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
+        // 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.

[Julien - ping for review, 2014/09/03 23:22:23]

FWIW table used to have some layout bugs from this problem as we left empty
anonymous table rows into the tree.

[mstensho (USE GERRIT), 2014/09/04 12:14:02]

Funny that you should mention it. This is still an issue for tables. But we can
talk about that in https://codereview.chromium.org/540453003/ (which I filed
yesterday). :)

For column set, the idea is that if they are empty, they have no effect on
layout. Pretty big words, I know, but I'd rather make sure of that, instead of
spending time on nuking them here.

+}
+
 void RenderMultiColumnFlowThread::computeLogicalHeight(LayoutUnit logicalHeight, LayoutUnit logicalTop, LogicalExtentComputedValues& computedValues) const
 {
     // We simply remain at our intrinsic height.
     computedValues.m_extent = logicalHeight;
     computedValues.m_position = logicalTop;
 }
 
 void RenderMultiColumnFlowThread::updateLogicalWidth()
 {
     LayoutUnit columnWidth;
     calculateColumnCountAndWidth(columnWidth, m_columnCount);
     setLogicalWidth(columnWidth);
 }
 
 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)
 {
     // Only positive values are interesting (and allowed) here. Zero space shortage may be reported
     // when we're at the top of a column and the element has zero height. Ignore this, and also
     // ignore any negative values, which may occur when we set an early break in order to honor
     // widows in the next column.
     if (spaceShortage <= 0)
         return;
 
     if (RenderMultiColumnSet* multicolSet = columnSetAtBlockOffset(offset))
         multicolSet->recordSpaceShortage(spaceShortage);
 }
 
 void RenderMultiColumnFlowThread::updateMinimumPageHeight(LayoutUnit offset, LayoutUnit minHeight)
 {
     if (RenderMultiColumnSet* multicolSet = columnSetAtBlockOffset(offset))
         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_inLayout) {
+        // 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;
     }
     return false;
 }
 
 bool RenderMultiColumnFlowThread::isPageLogicalHeightKnown() const
 {
     if (RenderMultiColumnSet* columnSet = lastMultiColumnSet())
         return columnSet->pageLogicalHeight();
     return false;
 }
 
 }