[New Multicolumn] Support dynamic insertion and removal of multicol content.

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
@@ skipping 303 matching lines @@
         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;
     }
 }
 
-void RenderMultiColumnFlowThread::createAndInsertMultiColumnSet()
+void RenderMultiColumnFlowThread::createAndInsertMultiColumnSet(RenderBox* insertBefore)
 {
     RenderBlockFlow* multicolContainer = multiColumnBlockFlow();
     RenderMultiColumnSet* newSet = RenderMultiColumnSet::createAnonymous(this, multicolContainer->style());
-    multicolContainer->RenderBlock::addChild(newSet);
+    multicolContainer->RenderBlock::addChild(newSet, insertBefore);
     invalidateRegions();
 
     // We cannot handle immediate column set siblings (and there's no need for it, either).
     // There has to be at least one spanner separating them.
     ASSERT(!newSet->previousSiblingMultiColumnBox() || !newSet->previousSiblingMultiColumnBox()->isRenderMultiColumnSet());
     ASSERT(!newSet->nextSiblingMultiColumnBox() || !newSet->nextSiblingMultiColumnBox()->isRenderMultiColumnSet());
 }
 
-void RenderMultiColumnFlowThread::createAndInsertSpannerPlaceholder(RenderBox* spanner)
+void RenderMultiColumnFlowThread::createAndInsertSpannerPlaceholder(RenderBox* spanner, RenderBox* insertBefore)
 {
     RenderBlockFlow* multicolContainer = multiColumnBlockFlow();
     RenderMultiColumnSpannerPlaceholder* newPlaceholder = RenderMultiColumnSpannerPlaceholder::createAnonymous(multicolContainer->style(), spanner);
-    multicolContainer->RenderBlock::addChild(newPlaceholder);
+    multicolContainer->RenderBlock::addChild(newPlaceholder, insertBefore);
     spanner->setSpannerPlaceholder(*newPlaceholder);
 }
 
 bool RenderMultiColumnFlowThread::descendantIsValidColumnSpanner(RenderObject* descendant) const
 {
     // We assume that we're inside the flow thread. This function is not to be called otherwise.
     ASSERT(descendant->isDescendantOf(this));
 
     // We're evaluating if the descendant should be turned into a proper spanner. It shouldn't
     // already be one.
@@ skipping 82 matching lines @@
         RenderMultiColumnSet* nextSet = toRenderMultiColumnSet(nextColumnBox);
         m_lastSetWorkedOn = nextSet;
         nextSet->beginFlow(logicalTopInFlowThread);
     }
     return adjustment;
 }
 
 void RenderMultiColumnFlowThread::flowThreadDescendantWasInserted(RenderObject* descendant)
 {
     ASSERT(!m_isBeingEvacuated);
+    RenderObject* nextRenderer = descendant->nextInPreOrderAfterChildren(this);
     // Go through the subtree that was just inserted and create column sets (needed by regular
     // column content) and spanner placeholders (one needed by each spanner).
     for (RenderObject* renderer = descendant; renderer; renderer = renderer->nextInPreOrder(descendant)) {
         if (containingColumnSpannerPlaceholder(renderer))
             continue; // Inside a column spanner. Nothing to do, then.
         if (descendantIsValidColumnSpanner(renderer)) {
             // This renderer is a spanner, so it needs to establish a spanner placeholder.
-            createAndInsertSpannerPlaceholder(toRenderBox(renderer));
+            RenderBox* insertBefore = 0;
+            RenderMultiColumnSet* setToSplit = 0;
+            if (nextRenderer) {
+                // The spanner is inserted before something. Figure out what this entails. If the
+                // next renderer is a spanner too, it means that we can simply insert a new spanner
+                // placeholder in front of its placeholder.
+                insertBefore = nextRenderer->spannerPlaceholder();
+                if (!insertBefore) {
+                    // The next renderer isn't a spanner; it's regular column content. Examine what
+                    // comes right before us, then.
+                    RenderObject* previousRenderer = renderer->previousInPreOrder(this);

[Julien - ping for review, 2015/01/23 09:13:56]

You're using |this| as the |root| instead of |descendant| (in the for-loop
above), is that expected?

[mstensho (USE GERRIT), 2015/01/23 12:15:49]

Yes, |this| is the flow thread, and that's all we really want to stay within.

<div style="-webkit-columns:3;">
    <h1>a</h1>
    <div id="spanner" style="display:none; -webkit-column-span:all;">b</div>
    <h2>c</h2>
</div>

Now imagine that you later set display:block on "spanner". That would become
both |renderer| and |descendant| in this code. Staying within it for
previousInPreOrder() not what we want; we want to get the H1 renderer, not 0.

If we got 0 here in this case, that would have us enter the first if-block, and
insert the spanner placeholder before the first (and only) column set, resulting
in this layout:

b
a          c

While we should get:

a
b
c

... since we actually end up in the last else-block, where we split the column
set around the spanner placeholder.

Expanded the above comment a little bit, to make it clearer that the flow thread
is the thing to stay within.

+                    if (!previousRenderer || previousRenderer == this) {
+                        // The spanner is inserted as the first child of the multicol container,
+                        // which means that we simply insert a new spanner placeholder at the
+                        // beginning.
+                        insertBefore = firstMultiColumnBox();
+                    } else if (RenderMultiColumnSpannerPlaceholder* previousPlaceholder = containingColumnSpannerPlaceholder(previousRenderer)) {
+                        // Before us is another spanner. We belong right after it then.
+                        insertBefore = previousPlaceholder->nextSiblingMultiColumnBox();
+                    } else {
+                        // We're inside regular column content with both feet. Find out which column
+                        // set this is. It needs to be split it into two sets, so that we can insert
+                        // a new spanner placeholder between them.
+                        setToSplit = findSetRendering(previousRenderer);
+                        ASSERT(setToSplit == findSetRendering(nextRenderer));
+                        setToSplit->setNeedsLayoutAndFullPaintInvalidation();
+                        insertBefore = setToSplit->nextSiblingMultiColumnBox();
+                        // We've found out which set that needs to be split. Now proceed to
+                        // inserting the spanner placeholder, and then insert a second column set.
+                    }
+                }
+                ASSERT(setToSplit || insertBefore);
+            }
+            createAndInsertSpannerPlaceholder(toRenderBox(renderer), insertBefore);
+            if (setToSplit)
+                createAndInsertMultiColumnSet(insertBefore);
             continue;
         }
         // This renderer is regular column content (i.e. not a spanner). Create a set if necessary.
-        RenderBox* lastColumnBox = lastMultiColumnBox();
-        if (!lastColumnBox || !lastColumnBox->isRenderMultiColumnSet())
-            createAndInsertMultiColumnSet();
+        if (nextRenderer) {
+            if (RenderMultiColumnSpannerPlaceholder* placeholder = nextRenderer->spannerPlaceholder()) {
+                // If inserted right before a spanner, we need to make sure that there's a set for us there.
+                RenderBox* previous = placeholder->previousSiblingMultiColumnBox();
+                if (!previous || !previous->isRenderMultiColumnSet())
+                    createAndInsertMultiColumnSet(placeholder);
+            } else {
+                // Otherwise, since |nextRenderer| isn't a spanner, it has to mean that there's
+                // already a set for that content. We can use it for this renderer too.
+                ASSERT(findSetRendering(nextRenderer));
+                ASSERT(findSetRendering(renderer) == findSetRendering(nextRenderer));
+            }
+        } else {
+            // Inserting at the end. Then we just need to make sure that there's a column set at the end.
+            RenderBox* lastColumnBox = lastMultiColumnBox();
+            if (!lastColumnBox || !lastColumnBox->isRenderMultiColumnSet())
+                createAndInsertMultiColumnSet();
+        }
     }
 }
 
 void RenderMultiColumnFlowThread::flowThreadDescendantWillBeRemoved(RenderObject* descendant)
 {
     if (m_isBeingEvacuated)
         return;
+    bool hadContainingPlaceholder = containingColumnSpannerPlaceholder(descendant);
     RenderObject* next;
     // Remove spanner placeholders that are no longer needed, and merge column sets around them.
     for (RenderObject* renderer = descendant; renderer; renderer = next) {
         RenderMultiColumnSpannerPlaceholder* placeholder = renderer->spannerPlaceholder();
         if (!placeholder) {
             next = renderer->nextInPreOrder(descendant);
             continue;
         }
         next = renderer->nextInPreOrderAfterChildren(descendant); // It's a spanner. Its children are of no interest to us.
         if (RenderBox* nextColumnBox = placeholder->nextSiblingMultiColumnBox()) {
             RenderBox* previousColumnBox = placeholder->previousSiblingMultiColumnBox();
             if (nextColumnBox && nextColumnBox->isRenderMultiColumnSet()
                 && previousColumnBox && previousColumnBox->isRenderMultiColumnSet()) {
                 // Need to merge two column sets.
                 nextColumnBox->destroy();
                 previousColumnBox->setNeedsLayout();
                 invalidateRegions();
             }
         }
         placeholder->destroy();
     }
+    if (hadContainingPlaceholder)
+        return; // We're only removing a spanner (or something inside one), which means that no column content will be removed.
+
+    // Column content will be removed. Does this mean that we should destroy a column set?
+    RenderMultiColumnSpannerPlaceholder* adjacentPreviousSpannerPlaceholder = 0;
+    RenderObject* previousRenderer = descendant->previousInPreOrder(this);
+    if (previousRenderer && previousRenderer != this) {
+        adjacentPreviousSpannerPlaceholder = containingColumnSpannerPlaceholder(previousRenderer);
+        if (!adjacentPreviousSpannerPlaceholder)
+            return; // Preceded by column content. Set still needed.
+    }
+    RenderMultiColumnSpannerPlaceholder* adjacentNextSpannerPlaceholder = 0;
+    RenderObject* nextRenderer = descendant->nextInPreOrderAfterChildren(this);
+    if (nextRenderer) {
+        adjacentNextSpannerPlaceholder = containingColumnSpannerPlaceholder(nextRenderer);
+        if (!adjacentNextSpannerPlaceholder)
+            return; // Followed by column content. Set still needed.
+    }

[Julien - ping for review, 2015/01/23 09:13:56]

Shouldn't you ASSERT that you either have no children or are surrounded by
spanner holder?

[mstensho (USE GERRIT), 2015/01/23 12:15:50]

Discussed offline that what we already have is enough.

+    // We have now determined that, with the removal of |descendant|, we should remove a column
+    // set. Locate it and remove it. Do it without involving findSetRendering(), as that might be
+    // very slow. Deduce the right set from the spanner placeholders that we've already found.
+    RenderMultiColumnSet* columnSetToRemove;
+    if (adjacentNextSpannerPlaceholder) {
+        columnSetToRemove = toRenderMultiColumnSet(adjacentNextSpannerPlaceholder->previousSiblingMultiColumnBox());
+        ASSERT(!adjacentPreviousSpannerPlaceholder || columnSetToRemove == adjacentPreviousSpannerPlaceholder->nextSiblingMultiColumnBox());
+    } else if (adjacentPreviousSpannerPlaceholder) {
+        columnSetToRemove = toRenderMultiColumnSet(adjacentPreviousSpannerPlaceholder->nextSiblingMultiColumnBox());
+    } else {
+        // If there were no adjacent spanners, it has to mean that there's only one column set,
+        // since it's only spanners that may cause creation of multiple sets.
+        columnSetToRemove = firstMultiColumnSet();
+        ASSERT(columnSetToRemove && !columnSetToRemove->nextSiblingMultiColumnSet());
+    }
+    ASSERT(columnSetToRemove);
+    columnSetToRemove->destroy();
 }

[Julien - ping for review, 2015/01/23 09:13:56]

Adding a comment to explain the whole strategy would be useful. You implicitly
assume a certain structure for the tree that would be nice to be made explicit.

[mstensho (USE GERRIT), 2015/01/23 12:15:49]

Done.

Added some header file documentation, and referred to it at the top of this
method and the preceding one.

 
 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()
 {
@@ skipping 50 matching lines @@
 }
 
 bool RenderMultiColumnFlowThread::isPageLogicalHeightKnown() const
 {
     if (RenderMultiColumnSet* columnSet = lastMultiColumnSet())
         return columnSet->pageLogicalHeight();
     return false;
 }
 
 }