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;
 #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)
 {
     if (!enabled())
         return;
+
+    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 74 matching lines @@
 
     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;
+        BlockSet dbcats;

[pdr., 2014/02/06 22:03:27]

Please add a comment explaining what a dbcat is, or just use the incredibly long
name.

[skobes, 2014/02/06 23:55:50]

Done.

+        for (BlockSet::iterator it = roots->begin(); it != roots->end(); ++it) {
+            // This is a bit of a hack to let us compute dbcat and text length for

[pdr., 2014/02/06 22:03:27]

The old autosizer used this hacky pattern quite a bit and I'm not a fan. Can you
extract out the logic from textLength and deepestBlockContainingAllText to call
it with just a block?

[skobes, 2014/02/06 23:55:50]

Done.

+            // clusters that don't technically exist yet.
+            Cluster pseudocluster(*it, true, 0, supercluster);
+            dbcats.add(deepestBlockContainingAllText(&pseudocluster));
+            supercluster->m_anyClusterHasEnoughText |= clusterHasEnoughTextToAutosize(&pseudocluster);
+        }
+        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)
+{
+    ASSERT(m_blocksThatHaveBegunLayout.contains(block));
+
+    // 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);
+}
+
 // FIXME: Refactor this to look more like FastTextAutosizer::deepestCommonAncestor. This is copied
 //        from TextAutosizer::findDeepestBlockContainingAllText.
 const RenderBlock* FastTextAutosizer::deepestBlockContainingAllText(Cluster* cluster)
 {
     if (cluster->m_deepestBlockContainingAllText)
         return cluster->m_deepestBlockContainingAllText;
 
     size_t firstDepth = 0;
     const RenderObject* firstTextLeaf = findTextLeaf(cluster->m_root, firstDepth, First);
     if (!firstTextLeaf)
@@ skipping 113 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