Improve positioned/percentHeight descendant/container tracking

third_party/WebKit/Source/core/layout/LayoutBlock.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 69 matching lines @@
 using namespace HTMLNames;
 
 struct SameSizeAsLayoutBlock : public LayoutBox {
     LayoutObjectChildList children;
     LineBoxList lineBoxes;
     uint32_t bitfields;
 };
 
 static_assert(sizeof(LayoutBlock) == sizeof(SameSizeAsLayoutBlock), "LayoutBlock should stay small");
 
-// This map keeps track of the positioned objects associated with a containing
-// block.
-//
-// This map is populated during layout. It is kept across layouts to handle
-// that we skip unchanged sub-trees during layout, in such a way that we are
-// able to lay out deeply nested out-of-flow descendants if their containing
-// block got laid out. The map could be invalidated during style change but
-// keeping track of containing blocks at that time is complicated (we are in
-// the middle of recomputing the style so we can't rely on any of its
-// information), which is why it's easier to just update it for every layout.
-static TrackedDescendantsMap* gPositionedDescendantsMap = nullptr;
-
-// This map keeps track of the descendants whose 'height' is percentage associated
-// with a containing block. Like |gPositionedDescendantsMap|, it is also recomputed
-// for every layout (see the comment above about why).
-static TrackedDescendantsMap* gPercentHeightDescendantsMap = nullptr;
-
-static TrackedContainerMap* gPositionedContainerMap = nullptr;
-static TrackedContainerMap* gPercentHeightContainerMap = nullptr;
-
 struct ScrollInfo {
     ScrollInfo() : autoHorizontalScrollBarChanged(false), autoVerticalScrollBarChanged(false) {}
     DoubleSize scrollOffset;
     bool autoHorizontalScrollBarChanged;
     bool autoVerticalScrollBarChanged;
     bool hasOffset() const { return scrollOffset != DoubleSize(); }
     bool scrollBarsChanged() const { return autoHorizontalScrollBarChanged || autoVerticalScrollBarChanged; }
     void merge(const ScrollInfo& other)
     {
         // We always keep the first scrollOffset we saw for this block, so don't copy that field.
@@ skipping 13 matching lines @@
     , m_hasMarkupTruncation(false)
     , m_widthAvailableToChildrenChanged(false)
     , m_hasOnlySelfCollapsingChildren(false)
     , m_descendantsWithFloatsMarkedForLayout(false)
     , m_needsRecalcLogicalWidthAfterLayoutChildren(false)
 {
     // LayoutBlockFlow calls setChildrenInline(true).
     // By default, subclasses do not have inline children.
 }
 
-static void removeBlockFromDescendantAndContainerMaps(LayoutBlock* block, TrackedDescendantsMap*& descendantMap, TrackedContainerMap*& containerMap)
+LayoutBlock::~LayoutBlock()
 {
-    if (OwnPtr<TrackedLayoutBoxListHashSet> descendantSet = descendantMap->take(block)) {
-        for (auto& descendant : *descendantSet) {
-            TrackedContainerMap::iterator it = containerMap->find(descendant);
-            ASSERT(it != containerMap->end());
-            if (it == containerMap->end())
-                continue;
-            HashSet<LayoutBlock*>* containerSet = it->value.get();
-            ASSERT(containerSet->contains(block));
-            containerSet->remove(block);
-            if (containerSet->isEmpty())
-                containerMap->remove(it);
+    if (TrackedLayoutBoxListHashSet* descendants = positionedObjects()) {
+        for (LayoutBox* descendant : *descendants) {
+            ASSERT(descendant->positionedContainer() == this);
+            descendant->setPositionedContainer(nullptr);
+        }
+    }
+    if (TrackedLayoutBoxListHashSet* descendants = percentHeightDescendants()) {
+        for (LayoutBox* descendant : *descendants) {
+            ASSERT(descendant->percentHeightContainer() == this);
+            descendant->setPercentHeightContainer(nullptr);
         }
     }
 }
 
-void LayoutBlock::removeFromGlobalMaps()
-{
-    if (gPercentHeightDescendantsMap)
-        removeBlockFromDescendantAndContainerMaps(this, gPercentHeightDescendantsMap, gPercentHeightContainerMap);
-    if (gPositionedDescendantsMap)
-        removeBlockFromDescendantAndContainerMaps(this, gPositionedDescendantsMap, gPositionedContainerMap);
-}
-
-LayoutBlock::~LayoutBlock()
-{
-    removeFromGlobalMaps();
-}
-
 void LayoutBlock::willBeDestroyed()
 {
     // Mark as being destroyed to avoid trouble with merges in removeChild().
     m_beingDestroyed = true;
 
     // Make sure to destroy anonymous children first while they are still connected to the rest of the tree, so that they will
     // properly dirty line boxes that they are removed from. Effects that do :before/:after only on hover could crash otherwise.
     children()->destroyLeftoverChildren();
 
     // Destroy our continuation before anything other than anonymous children.
@@ skipping 1206 matching lines @@
 }
 
 void LayoutBlock::setSelectionState(SelectionState state)
 {
     LayoutBox::setSelectionState(state);
 
     if (inlineBoxWrapper() && canUpdateSelectionOnRootLineBoxes())
         inlineBoxWrapper()->root().setHasSelectedChildren(state != SelectionNone);
 }
 
-void LayoutBlock::insertIntoTrackedLayoutBoxMaps(LayoutBox* descendant, TrackedDescendantsMap*& descendantsMap, TrackedContainerMap*& containerMap)
+void LayoutBlock::insertPositionedObject(LayoutBox* descendant)
 {
-    if (!descendantsMap) {
-        descendantsMap = new TrackedDescendantsMap;
-        containerMap = new TrackedContainerMap;
+    ASSERT(!isAnonymousBlock());
+    OwnPtr<TrackedLayoutBoxListHashSet>& positionedDescendants = ensureLayoutBlockRareData().m_positionedDescendants;
+    if (!positionedDescendants)
+        positionedDescendants = adoptPtr(new TrackedLayoutBoxListHashSet);
+    if (descendant->positionedContainer()) {
+        if (descendant->positionedContainer() == this) {
+            ASSERT(positionedDescendants->contains(descendant));
+            return;
+        }
+        descendant->removeFromPositionedContainer();
     }
+    positionedDescendants->add(descendant);
+    descendant->setPositionedContainer(this);
+}
 
-    TrackedLayoutBoxListHashSet* descendantSet = descendantsMap->get(this);
-    if (!descendantSet) {
-        descendantSet = new TrackedLayoutBoxListHashSet;
-        descendantsMap->set(this, adoptPtr(descendantSet));
-    }
-    bool added = descendantSet->add(descendant).isNewEntry;
-    if (!added) {
-        ASSERT(containerMap->get(descendant));
-        ASSERT(containerMap->get(descendant)->contains(this));
+void LayoutBlock::removePositionedObject(LayoutBox* descendant)
+{
+    TrackedLayoutBoxListHashSet* positionedDescendants = positionedObjects();
+    if (!descendant->positionedContainer()) {
+        ASSERT(!positionedDescendants || !positionedDescendants->contains(descendant));
         return;
     }
-
-    HashSet<LayoutBlock*>* containerSet = containerMap->get(descendant);
-    if (!containerSet) {
-        containerSet = new HashSet<LayoutBlock*>;
-        containerMap->set(descendant, adoptPtr(containerSet));
-    }
-    ASSERT(!containerSet->contains(this));
-    containerSet->add(this);
-}
-
-void LayoutBlock::removeFromTrackedLayoutBoxMaps(LayoutBox* descendant, TrackedDescendantsMap*& descendantsMap, TrackedContainerMap*& containerMap)
-{
-    if (!descendantsMap)
-        return;
-
-    OwnPtr<HashSet<LayoutBlock*>> containerSet = containerMap->take(descendant);
-    if (!containerSet)
-        return;
-
-    for (auto* container : *containerSet) {
-        // FIXME: Disabling this assert temporarily until we fix the layout
-        // bugs associated with positioned objects not properly cleared from
-        // their ancestor chain before being moved. See webkit bug 93766.
-        // ASSERT(descendant->isDescendantOf(container));
-
-        TrackedDescendantsMap::iterator descendantsMapIterator = descendantsMap->find(container);
-        ASSERT(descendantsMapIterator != descendantsMap->end());
-        if (descendantsMapIterator == descendantsMap->end())
-            continue;
-        TrackedLayoutBoxListHashSet* descendantSet = descendantsMapIterator->value.get();
-        ASSERT(descendantSet->contains(descendant));
-        descendantSet->remove(descendant);
-        if (descendantSet->isEmpty())
-            descendantsMap->remove(descendantsMapIterator);
-    }
-}
-
-TrackedLayoutBoxListHashSet* LayoutBlock::positionedObjects() const
-{
-    if (gPositionedDescendantsMap)
-        return gPositionedDescendantsMap->get(this);
-    return nullptr;
-}
-
-void LayoutBlock::insertPositionedObject(LayoutBox* o)
-{
-    ASSERT(!isAnonymousBlock());
-    insertIntoTrackedLayoutBoxMaps(o, gPositionedDescendantsMap, gPositionedContainerMap);
-}
-
-void LayoutBlock::removePositionedObject(LayoutBox* o)
-{
-    removeFromTrackedLayoutBoxMaps(o, gPositionedDescendantsMap, gPositionedContainerMap);
+    ASSERT(descendant->positionedContainer() == this);
+    ASSERT(positionedDescendants && positionedDescendants->contains(descendant));
+    positionedDescendants->remove(descendant);
+    descendant->setPositionedContainer(nullptr);
 }
 
 void LayoutBlock::removePositionedObjects(LayoutBlock* o, ContainingBlockState containingBlockState)
 {
     TrackedLayoutBoxListHashSet* positionedDescendants = positionedObjects();
     if (!positionedDescendants)
         return;
 
     Vector<LayoutBox*, 16> deadObjects;
     for (auto* positionedObject : *positionedDescendants) {
@@ skipping 18 matching lines @@
             LayoutObject* p = positionedObject->parent();
             while (p && !p->isLayoutBlock())
                 p = p->parent();
             if (p)
                 p->setChildNeedsLayout();
 
             deadObjects.append(positionedObject);
         }
     }
 
-    for (unsigned i = 0; i < deadObjects.size(); i++)
-        removePositionedObject(deadObjects.at(i));
+    for (auto* deadObject : deadObjects)
+        deadObject->removeFromPositionedContainer();
 }
 
 void LayoutBlock::addPercentHeightDescendant(LayoutBox* descendant)
 {
-    insertIntoTrackedLayoutBoxMaps(descendant, gPercentHeightDescendantsMap, gPercentHeightContainerMap);
+    OwnPtr<TrackedLayoutBoxListHashSet>& percentHeightDescendants = ensureLayoutBlockRareData().m_percentHeightDescendants;
+    if (!percentHeightDescendants)
+        percentHeightDescendants = adoptPtr(new TrackedLayoutBoxListHashSet);
+    if (descendant->percentHeightContainer()) {
+        if (descendant->percentHeightContainer() == this) {
+            ASSERT(percentHeightDescendants->contains(descendant));
+            return;
+        }
+        descendant->removeFromPercentHeightContainer();
+    }
+    percentHeightDescendants->add(descendant);
+    descendant->setPercentHeightContainer(this);
 }
 
 void LayoutBlock::removePercentHeightDescendant(LayoutBox* descendant)
 {
-    removeFromTrackedLayoutBoxMaps(descendant, gPercentHeightDescendantsMap, gPercentHeightContainerMap);
-}
-
-TrackedLayoutBoxListHashSet* LayoutBlock::percentHeightDescendants() const
-{
-    return gPercentHeightDescendantsMap ? gPercentHeightDescendantsMap->get(this) : 0;
-}
-
-bool LayoutBlock::hasPercentHeightContainerMap()
-{
-    return gPercentHeightContainerMap;
+    TrackedLayoutBoxListHashSet* percentHeightDescendants = this->percentHeightDescendants();
+    if (!descendant->percentHeightContainer()) {
+        ASSERT(!percentHeightDescendants || !percentHeightDescendants->contains(descendant));
+        return;
+    }
+    ASSERT(descendant->percentHeightContainer() == this);
+    ASSERT(percentHeightDescendants && percentHeightDescendants->contains(descendant));
+    percentHeightDescendants->remove(descendant);
+    descendant->setPercentHeightContainer(nullptr);
 }
 
 bool LayoutBlock::hasPercentHeightDescendant(LayoutBox* descendant)
 {
-    // We don't null check gPercentHeightContainerMap since the caller
-    // already ensures this and we need to call this function on every
-    // descendant in clearPercentHeightDescendantsFrom().
-    ASSERT(gPercentHeightContainerMap);
-    return gPercentHeightContainerMap->contains(descendant);
+    return percentHeightDescendants() && percentHeightDescendants()->contains(descendant);
 }
 
 void LayoutBlock::dirtyForLayoutFromPercentageHeightDescendants(SubtreeLayoutScope& layoutScope)
 {
-    if (!gPercentHeightDescendantsMap)
+    TrackedLayoutBoxListHashSet* percentHeightDescendants = this->percentHeightDescendants();
+    if (!percentHeightDescendants)
         return;
 
-    TrackedLayoutBoxListHashSet* descendants = gPercentHeightDescendantsMap->get(this);
-    if (!descendants)
-        return;
-
-    for (auto* box : *descendants) {
+    for (auto* box : *percentHeightDescendants) {
         ASSERT(box->isDescendantOf(this));
         while (box != this) {
             if (box->normalChildNeedsLayout())
                 break;
             layoutScope.setChildNeedsLayout(box);
             box = box->containingBlock();
             ASSERT(box);
             if (!box)
                 break;
         }
     }
 }
 
-void LayoutBlock::removePercentHeightDescendantIfNeeded(LayoutBox* descendant)
-{
-    // We query the map directly, rather than looking at style's
-    // logicalHeight()/logicalMinHeight()/logicalMaxHeight() since those
-    // can change with writing mode/directional changes.
-    if (!hasPercentHeightContainerMap())
-        return;
-
-    if (!hasPercentHeightDescendant(descendant))
-        return;
-
-    removePercentHeightDescendant(descendant);
-}
-
-void LayoutBlock::clearPercentHeightDescendantsFrom(LayoutBox* parent)
-{
-    ASSERT(gPercentHeightContainerMap);
-    for (LayoutObject* curr = parent->slowFirstChild(); curr; curr = curr->nextInPreOrder(parent)) {
-        if (!curr->isBox())
-            continue;
-
-        LayoutBox* box = toLayoutBox(curr);
-        if (!hasPercentHeightDescendant(box))
-            continue;
-
-        removePercentHeightDescendant(box);
-    }
-}
-
 LayoutUnit LayoutBlock::textIndentOffset() const
 {
     LayoutUnit cw = 0;
     if (style()->textIndent().hasPercent())
         cw = containingBlock()->availableLogicalWidth();
     return minimumValueForLength(style()->textIndent(), cw);
 }
 
 void LayoutBlock::markLinesDirtyInBlockRange(LayoutUnit logicalTop, LayoutUnit logicalBottom, RootInlineBox* highest)
 {
@@ skipping 1266 matching lines @@
     setLogicalTop(computedValues.m_position);
     setMarginBefore(computedValues.m_margins.m_before);
     setMarginAfter(computedValues.m_margins.m_after);
 
     return true;
 }
 
 #if ENABLE(ASSERT)
 void LayoutBlock::checkPositionedObjectsNeedLayout()
 {
-    if (!gPositionedDescendantsMap)
-        return;
-
     if (TrackedLayoutBoxListHashSet* positionedDescendantSet = positionedObjects()) {
-        TrackedLayoutBoxListHashSet::const_iterator end = positionedDescendantSet->end();
-        for (TrackedLayoutBoxListHashSet::const_iterator it = positionedDescendantSet->begin(); it != end; ++it) {
-            LayoutBox* currBox = *it;
-            ASSERT(!currBox->needsLayout());
-        }
+        for (LayoutBox* box : *positionedDescendantSet)
+            ASSERT(!box->needsLayout());
     }
 }
 
 #endif
 
 #ifndef NDEBUG
 
 void LayoutBlock::showLineTreeAndMark(const InlineBox* markedBox1, const char* markedLabel1, const InlineBox* markedBox2, const char* markedLabel2, const LayoutObject* obj) const
 {
     showLayoutObject();
     for (const RootInlineBox* root = firstRootBox(); root; root = root->nextRootBox())
         root->showLineTreeAndMark(markedBox1, markedLabel1, markedBox2, markedLabel2, obj, 1);
 }
 
 #endif
 
 } // namespace blink