Ensure that positioned objects' list is always in parent first order

Source/core/rendering/RenderBlock.cpp

Index: Source/core/rendering/RenderBlock.cpp
diff --git a/Source/core/rendering/RenderBlock.cpp b/Source/core/rendering/RenderBlock.cpp
index 5f6519f77ca37901b568e9e161b136a5bb61ffc1..ef9da4cc129dc5eecf635f9e4c4c3e0338a767b3 100644
--- a/Source/core/rendering/RenderBlock.cpp
+++ b/Source/core/rendering/RenderBlock.cpp
@@ -1939,13 +1939,28 @@ void RenderBlock::insertIntoTrackedRendererMaps(RenderBox* descendant, TrackedDe
         descendantSet = new TrackedRendererListHashSet;
         descendantsMap->set(this, adoptPtr(descendantSet));
     }
-    bool added = descendantSet->add(descendant).isNewEntry;
-    if (!added) {
+
+    if (descendantSet->contains(descendant)) {
         ASSERT(containerMap->get(descendant));
         ASSERT(containerMap->get(descendant)->contains(this));
         return;
     }
 
+    // Try to insert parent before child, as layoutPositionedObjects relies on 'parent first' ordering.
+    bool didInsertDescendant = false;
+    if (descendant->isRenderBlock()) {
+        TrackedRendererListHashSet::iterator end = descendantSet->end();
+        for (TrackedRendererListHashSet::iterator it = descendantSet->begin(); it != end; ++it) {
+            RenderBox* box = *it;
+            if (box->isDescendantOf(descendant)) {

[Julien - ping for review, 2015/01/27 14:47:46]

This check is expensive as it involves walking the tree up repeatedly (due to
the for loop).

This will be run for *every* layout, which is a show-stopper for me. Your
description mentions a precise situation(s) in which we could have this problem.
It seems to me that we should narrow this code for this case(s).

[alexanderk, 2015/01/28 14:15:27]

Right, isDescendantOf() is expensive.
And optimization is possible for this particular "remove and then append back"
case, but, as it turned out, we have some other cases when "parent first" order
is broken.
I will try to analyse these cases to minimize isDescendantOf() calls.

+                didInsertDescendant = descendantSet->insertBefore(box, descendant).isNewEntry;
+                break;
+            }
+        }
+    }
+    if (!didInsertDescendant)
+        descendantSet->add(descendant);

[Julien - ping for review, 2015/01/27 14:47:46]

I think descendantSet->insertBefore() should be able to handle already added
nodes.

Thus we could write:

// Insert the descendant.
bool added = descendantSet->add(descendant).isNewEntry;

if (added) {
   ...
}

// We may need to change the order, e.g. if a containing block changed position.
// Try to find the right position for this case.
if (descendant->isRenderBlock()) {
    TrackedRendererListHashSet::iterator end = descendantSet->end();
    for (TrackedRendererListHashSet::iterator it = descendantSet->begin(); it !=
end; ++it) {
        RenderBox* box = *it;
        if (box->isDescendantOf(descendant)) {
            descendantSet->insertBefore(box, descendant);
            break;
        }
    }
}

Which seems more readable to me.

[alexanderk, 2015/01/28 14:15:27]

Unfortunately insertBefore() does not move already added nodes.

+
     HashSet<RenderBlock*>* containerSet = containerMap->get(descendant);
     if (!containerSet) {
         containerSet = new HashSet<RenderBlock*>;