Fix supercluster logic.

Source/core/rendering/FastTextAutosizer.cpp

 /*
  * Copyright (C) 2013 Google 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:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 79 matching lines @@
     ASSERT(m_clusterStack.isEmpty() == block->isRenderView());
 
     if (block->isRenderView()) {
         prepareRenderViewInfo(toRenderView(block));
     } else if (block == currentCluster()->m_root) {
         // Ignore beginLayout on the same block twice.
         // This can happen with paginated overflow.
         return;
     }
 
-    if (Cluster* cluster = maybeGetOrCreateCluster(block))
-        m_clusterStack.append(cluster);
+    if (Cluster* cluster = maybeCreateCluster(block))
+        m_clusterStack.append(adoptPtr(cluster));
 
     if (block->childrenInline())
         inflate(block);
 }
 
 void FastTextAutosizer::inflateListItem(RenderListItem* listItem, RenderListMarker* listItemMarker)
 {
     if (!enabled())
         return;
     ASSERT(listItem && listItemMarker);
 #ifndef NDEBUG
     m_blocksThatHaveBegunLayout.add(listItem);
 #endif
     // Force the LI to be inside the DBCAT when computing the multiplier.
     // This guarantees that the DBCAT has entered layout, so we can ask for its width.
     // It also makes sense because the list marker is autosized like a text node.
     float multiplier = clusterMultiplier(currentCluster());
 
     applyMultiplier(listItem, multiplier);
     applyMultiplier(listItemMarker, multiplier);
 }
 
 void FastTextAutosizer::endLayout(RenderBlock* block)
 {
     ASSERT(enabled());
+    if (block->isRenderView()) {
+        m_superclusters.clear();
 #ifndef NDEBUG
-    if (block->isRenderView())
         m_blocksThatHaveBegunLayout.clear();
 #endif
+    }
 
     if (currentCluster()->m_root == block)
         m_clusterStack.removeLast();
 
     ASSERT(m_clusterStack.isEmpty() == block->isRenderView());
 }
 
 void FastTextAutosizer::inflate(RenderBlock* block)
 {
     Cluster* cluster = currentCluster();
@@ skipping 45 matching lines @@
 }
 
 bool FastTextAutosizer::isFingerprintingCandidate(const RenderBlock* block)
 {
     // FIXME: move the logic out of TextAutosizer.cpp into this class.
     return block->isRenderView()
         || (TextAutosizer::isAutosizingContainer(block)
             && TextAutosizer::isIndependentDescendant(block));
 }
 
+bool FastTextAutosizer::clusterWouldHaveEnoughTextToAutosize(const RenderBlock* root)
+{
+    Cluster hypotheticalCluster(root, true, 0);
+    return clusterHasEnoughTextToAutosize(&hypotheticalCluster);
+}
+
 bool FastTextAutosizer::clusterHasEnoughTextToAutosize(Cluster* cluster)
 {
     const RenderBlock* root = cluster->m_root;
 
     // TextAreas and user-modifiable areas get a free pass to autosize regardless of text content.
     if (root->isTextArea() || (root->style() && root->style()->userModify() != READ_ONLY))
         return true;
 
     static const float minLinesOfText = 4;
     if (textLength(cluster) >= root->contentLogicalWidth() * minLinesOfText)
         return true;
 
     return false;
 }
 
 float FastTextAutosizer::textLength(Cluster* cluster)
 {
     if (cluster->m_textLength >= 0)
         return cluster->m_textLength;
 
     float length = 0;
     const RenderBlock* root = cluster->m_root;
     bool measureLocalText = TextAutosizer::containerShouldBeAutosized(root);
     RenderObject* descendant = root->nextInPreOrder(root);
     while (descendant) {
         // FIXME: We should skip over text from descendant clusters (see:
         //        clusters-sufficient-text-except-in-root.html). This currently includes text
         //        from descendant clusters.
 
-        if (descendant->isRenderBlock() && m_clusters.contains(toRenderBlock(descendant))) {
-            length += textLength(m_clusters.get(toRenderBlock(descendant)));
-            descendant = descendant->nextInPreOrderAfterChildren(root);
-            continue;
-        }
-
         if (measureLocalText && descendant->isText()) {
             // Note: Using text().stripWhiteSpace().length() instead of renderedTextLength() because
             // the lineboxes will not be built until layout. These values can be different.
             length += toRenderText(descendant)->text().stripWhiteSpace().length() * descendant->style()->specifiedFontSize();
         }
         descendant = descendant->nextInPreOrder(root);
     }
 
     return cluster->m_textLength = length;
 }
 
 AtomicString FastTextAutosizer::computeFingerprint(const RenderBlock* block)
 {
     // FIXME(crbug.com/322340): Implement a fingerprinting algorithm.
     return nullAtom;
 }
 
-FastTextAutosizer::Cluster* FastTextAutosizer::maybeGetOrCreateCluster(const RenderBlock* block)
+FastTextAutosizer::Cluster* FastTextAutosizer::maybeCreateCluster(const RenderBlock* block)
 {
     if (!TextAutosizer::isAutosizingContainer(block))
         return 0;
 
     Cluster* parentCluster = m_clusterStack.isEmpty() ? 0 : currentCluster();
     ASSERT(parentCluster || block->isRenderView());
 
     // Create clusters to suppress / unsuppress autosizing based on containerShouldBeAutosized.
     bool containerCanAutosize = TextAutosizer::containerShouldBeAutosized(block);
     bool parentClusterCanAutosize = parentCluster && parentCluster->m_autosize;
     bool createClusterThatMightAutosize = mightBeWiderOrNarrowerDescendant(block) || TextAutosizer::isIndependentDescendant(block);
 
     // If the container would not alter the m_autosize bit, it doesn't need to be a cluster.
     if (!createClusterThatMightAutosize && containerCanAutosize == parentClusterCanAutosize)
         return 0;
 
-    ClusterMap::AddResult addResult = m_clusters.add(block, PassOwnPtr<Cluster>());
+    return new Cluster(block, containerCanAutosize, parentCluster, getSupercluster(block));
+}
+
+FastTextAutosizer::Supercluster* FastTextAutosizer::getSupercluster(const RenderBlock* block)
+{
+    AtomicString fingerprint = m_fingerprintMapper.get(block);
+    if (fingerprint.isNull())
+        return 0;
+
+    BlockSet* roots = &m_fingerprintMapper.getBlocks(fingerprint);
+    if (roots->size() < 2)
+        return 0;
+
+    SuperclusterMap::AddResult addResult = m_superclusters.add(fingerprint, PassOwnPtr<Supercluster>());
     if (!addResult.isNewEntry)
         return addResult.iterator->value.get();
 
-    AtomicString fingerprint = m_fingerprintMapper.get(block);
-    if (fingerprint.isNull()) {
-        addResult.iterator->value = adoptPtr(new Cluster(block, containerCanAutosize, parentCluster));
-        return addResult.iterator->value.get();
-    }
-    return addSupercluster(fingerprint, block);
-}
-
-// FIXME: The supercluster logic does not work yet.
-FastTextAutosizer::Cluster* FastTextAutosizer::addSupercluster(AtomicString fingerprint, const RenderBlock* returnFor)
-{
-    BlockSet& roots = m_fingerprintMapper.getBlocks(fingerprint);
-
-    Cluster* result = 0;
-    for (BlockSet::iterator it = roots.begin(); it != roots.end(); ++it) {
-        Cluster* cluster = new Cluster(*it, TextAutosizer::containerShouldBeAutosized(*it), currentCluster());
-        m_clusters.set(*it, adoptPtr(cluster));
-
-        if (*it == returnFor)
-            result = cluster;
-    }
-    return result;
+    Supercluster* supercluster = new Supercluster(roots);
+    addResult.iterator->value = adoptPtr(supercluster);
+    return supercluster;
 }
 
 const RenderBlock* FastTextAutosizer::deepestCommonAncestor(BlockSet& blocks)
 {
     // Find the lowest common ancestor of blocks.
     // Note: this could be improved to not be O(b*h) for b blocks and tree height h.
     HashCountedSet<const RenderBlock*> ancestors;
     for (BlockSet::iterator it = blocks.begin(); it != blocks.end(); ++it) {
         for (const RenderBlock* block = (*it); block; block = block->containingBlock()) {
             ancestors.add(block);
             // The first ancestor that has all of the blocks as children wins.
             if (ancestors.count(block) == blocks.size())
                 return block;
         }
     }
     ASSERT_NOT_REACHED();
     return 0;
 }
 
 float FastTextAutosizer::clusterMultiplier(Cluster* cluster)
 {
     ASSERT(m_renderViewInfoPrepared);
     if (!cluster->m_multiplier) {
         if (TextAutosizer::isIndependentDescendant(cluster->m_root) || isWiderDescendant(cluster) || isNarrowerDescendant(cluster)) {
-            if (clusterHasEnoughTextToAutosize(cluster)) {
-                const RenderBlock* deepestBlockWithAllText = deepestBlockContainingAllText(cluster);
-
-                // Ensure the deepest block containing all text has a valid contentLogicalWidth.
-                ASSERT(m_blocksThatHaveBegunLayout.contains(deepestBlockWithAllText));
-
-                // Block width, in CSS pixels.
-                float textBlockWidth = deepestBlockWithAllText->contentLogicalWidth();
-                float multiplier = min(textBlockWidth, static_cast<float>(m_layoutWidth)) / m_frameWidth;
-                cluster->m_multiplier = max(m_baseMultiplier * multiplier, 1.0f);
+            if (cluster->m_supercluster) {
+                cluster->m_multiplier = superclusterMultiplier(cluster->m_supercluster);
+            } else if (clusterHasEnoughTextToAutosize(cluster)) {
+                cluster->m_multiplier = multiplierFromBlock(deepestBlockContainingAllText(cluster));
             } else {
                 cluster->m_multiplier = 1.0f;
             }
         } else {
             cluster->m_multiplier = cluster->m_parent ? clusterMultiplier(cluster->m_parent) : 1.0f;
         }
     }
     ASSERT(cluster->m_multiplier);
     return cluster->m_multiplier;
 }
 
+float FastTextAutosizer::superclusterMultiplier(Supercluster* supercluster)
+{
+    if (!supercluster->m_multiplier) {
+        const BlockSet* roots = supercluster->m_roots;
+        // Set of the deepest block containing all text (DBCAT) of every cluster.
+        BlockSet dbcats;
+        for (BlockSet::iterator it = roots->begin(); it != roots->end(); ++it) {
+            dbcats.add(deepestBlockContainingAllText(*it));
+            supercluster->m_anyClusterHasEnoughText |= clusterWouldHaveEnoughTextToAutosize(*it);
+        }
+        supercluster->m_multiplier = supercluster->m_anyClusterHasEnoughText
+            ? multiplierFromBlock(deepestCommonAncestor(dbcats)) : 1.0f;
+    }
+    ASSERT(supercluster->m_multiplier);
+    return supercluster->m_multiplier;
+}
+
+float FastTextAutosizer::multiplierFromBlock(const RenderBlock* block)
+{
+    // If block->needsLayout() is false, it does not need to be in m_blocksThatHaveBegunLayout.
+    // This can happen during layout of a positioned object if the cluster's DBCAT is deeper
+    // than the positioned object's containing block, and wasn't marked as needing layout.
+    ASSERT(m_blocksThatHaveBegunLayout.contains(block) || !block->needsLayout());
+
+    // Block width, in CSS pixels.
+    float textBlockWidth = block->contentLogicalWidth();
+    float multiplier = min(textBlockWidth, static_cast<float>(m_layoutWidth)) / m_frameWidth;
+
+    return max(m_baseMultiplier * multiplier, 1.0f);
+}
+
+const RenderBlock* FastTextAutosizer::deepestBlockContainingAllText(Cluster* cluster)
+{
+    if (!cluster->m_deepestBlockContainingAllText)
+        cluster->m_deepestBlockContainingAllText = deepestBlockContainingAllText(cluster->m_root);
+
+    return cluster->m_deepestBlockContainingAllText;
+}
+
 // FIXME: Refactor this to look more like FastTextAutosizer::deepestCommonAncestor. This is copied
 //        from TextAutosizer::findDeepestBlockContainingAllText.
-const RenderBlock* FastTextAutosizer::deepestBlockContainingAllText(Cluster* cluster)
+const RenderBlock* FastTextAutosizer::deepestBlockContainingAllText(const RenderBlock* root)
 {
-    if (cluster->m_deepestBlockContainingAllText)
-        return cluster->m_deepestBlockContainingAllText;
-
     size_t firstDepth = 0;
-    const RenderObject* firstTextLeaf = findTextLeaf(cluster->m_root, firstDepth, First);
+    const RenderObject* firstTextLeaf = findTextLeaf(root, firstDepth, First);
     if (!firstTextLeaf)
-        return cluster->m_deepestBlockContainingAllText = cluster->m_root;
+        return root;
 
     size_t lastDepth = 0;
-    const RenderObject* lastTextLeaf = findTextLeaf(cluster->m_root, lastDepth, Last);
+    const RenderObject* lastTextLeaf = findTextLeaf(root, lastDepth, Last);
     ASSERT(lastTextLeaf);
 
     // Equalize the depths if necessary. Only one of the while loops below will get executed.
     const RenderObject* firstNode = firstTextLeaf;
     const RenderObject* lastNode = lastTextLeaf;
     while (firstDepth > lastDepth) {
         firstNode = firstNode->parent();
         --firstDepth;
     }
     while (lastDepth > firstDepth) {
         lastNode = lastNode->parent();
         --lastDepth;
     }
 
     // Go up from both nodes until the parent is the same. Both pointers will point to the LCA then.
     while (firstNode != lastNode) {
         firstNode = firstNode->parent();
         lastNode = lastNode->parent();
     }
 
     if (firstNode->isRenderBlock())
-        return cluster->m_deepestBlockContainingAllText = toRenderBlock(firstNode);
+        return toRenderBlock(firstNode);
 
     // containingBlock() should never leave the cluster, since it only skips ancestors when finding
     // the container of position:absolute/fixed blocks, and those cannot exist between a cluster and
     // its text node's lowest common ancestor as isAutosizingCluster would have made them into their
     // own independent cluster.
     const RenderBlock* containingBlock = firstNode->containingBlock();
-    ASSERT(containingBlock->isDescendantOf(cluster->m_root));
+    ASSERT(containingBlock->isDescendantOf(root));
 
-    return cluster->m_deepestBlockContainingAllText = containingBlock;
+    return containingBlock;
 }
 
 const RenderObject* FastTextAutosizer::findTextLeaf(const RenderObject* parent, size_t& depth, TextLeafSearch firstOrLast)
 {
     // List items are treated as text due to the marker.
     // The actual renderer for the marker (RenderListMarker) may not be in the tree yet since it is added during layout.
     if (parent->isListItem())
         return parent;
 
     if (parent->isEmpty())
@@ skipping 69 matching lines @@
     float contentWidth = cluster->m_root->contentLogicalWidth();
     float clusterTextWidth = parentDeepestBlockContainingAllText->contentLogicalWidth();
     float widthDifference = clusterTextWidth - contentWidth;
 
     return widthDifference > narrowWidthDifference;
 }
 
 FastTextAutosizer::Cluster* FastTextAutosizer::currentCluster() const
 {
     ASSERT(!m_clusterStack.isEmpty());
-    return m_clusterStack.last();
+    return m_clusterStack.last().get();
 }
 
 void FastTextAutosizer::FingerprintMapper::add(const RenderBlock* block, AtomicString fingerprint)
 {
     m_fingerprints.set(block, fingerprint);
 
     ReverseFingerprintMap::AddResult addResult = m_blocksForFingerprint.add(fingerprint, PassOwnPtr<BlockSet>());
     if (addResult.isNewEntry)
         addResult.iterator->value = adoptPtr(new BlockSet);
     addResult.iterator->value->add(block);
@@ skipping 23 matching lines @@
 }
 
 RenderObject* FastTextAutosizer::nextChildSkippingChildrenOfBlocks(const RenderObject* current, const RenderObject* stayWithin)
 {
     if (current == stayWithin || !current->isRenderBlock())
         return current->nextInPreOrder(stayWithin);
     return current->nextInPreOrderAfterChildren(stayWithin);
 }
 
 } // namespace WebCore