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

Source/core/rendering/RenderBlock.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2007 David Smith (catfish.man@gmail.com)
  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved.
  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
@@ skipping 1921 matching lines @@
     if (!descendantsMap) {
         descendantsMap = new TrackedDescendantsMap;
         containerMap = new TrackedContainerMap;
     }
 
     TrackedRendererListHashSet* descendantSet = descendantsMap->get(this);
     if (!descendantSet) {
         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*>;
         containerMap->set(descendant, adoptPtr(containerSet));
     }
     ASSERT(!containerSet->contains(this));
     containerSet->add(this);
 }
 
 void RenderBlock::removeFromTrackedRendererMaps(RenderBox* descendant, TrackedDescendantsMap*& descendantsMap, TrackedContainerMap*& containerMap)
@@ skipping 1982 matching lines @@
 void RenderBlock::showLineTreeAndMark(const InlineBox* markedBox1, const char* markedLabel1, const InlineBox* markedBox2, const char* markedLabel2, const RenderObject* obj) const
 {
     showRenderObject();
     for (const RootInlineBox* root = firstRootBox(); root; root = root->nextRootBox())
         root->showLineTreeAndMark(markedBox1, markedLabel1, markedBox2, markedLabel2, obj, 1);
 }
 
 #endif
 
 } // namespace blink