Make cluster creation independent of fingerprinting. Keep track of current

Source/core/rendering/FastTextAutosizer.cpp

Index: Source/core/rendering/FastTextAutosizer.cpp
diff --git a/Source/core/rendering/FastTextAutosizer.cpp b/Source/core/rendering/FastTextAutosizer.cpp
index 933dc22b10cc35f38f7aa478323ac9bd4e5e46f3..867c5ab7f7eb41acbe7b8bab8a0da4b304c9c4cb 100644
--- a/Source/core/rendering/FastTextAutosizer.cpp
+++ b/Source/core/rendering/FastTextAutosizer.cpp
@@ -38,6 +38,7 @@
 #include "core/page/Page.h"
 #include "core/rendering/InlineIterator.h"
 #include "core/rendering/RenderBlock.h"
+#include "core/rendering/RenderView.h"
 #include "core/rendering/TextAutosizer.h"
 
 using namespace std;
@@ -49,183 +50,217 @@ FastTextAutosizer::FastTextAutosizer(Document* document)
 {
 }
 
-void FastTextAutosizer::prepareForLayout()
+void FastTextAutosizer::record(RenderBlock* block)
 {
-    if (!m_document->settings()
-        || !m_document->settings()->textAutosizingEnabled()
-        || m_document->printing()
-        || !m_document->page())
+    if (!enabled())
         return;
-    bool windowWidthChanged = updateWindowWidth();
-
-    // If needed, set existing clusters as needing their multiplier recalculated.
-    for (FingerprintToClusterMap::iterator it = m_clusterForFingerprint.begin(), end = m_clusterForFingerprint.end(); it != end; ++it) {
-        Cluster* cluster = it->value.get();
-        ASSERT(cluster);
-        WTF::HashSet<RenderBlock*>& blocks = cluster->m_blocks;
-
-        if (windowWidthChanged) {
-            // Clusters depend on the window width. Changes to the width should cause all clusters to recalc.
-            cluster->setNeedsClusterRecalc();
-        } else {
-            // If any of the cluster's blocks need a layout, mark the entire cluster as needing a recalc.
-            for (WTF::HashSet<RenderBlock*>::iterator block = blocks.begin(); block != blocks.end(); ++block) {
-                if ((*block)->needsLayout()) {
-                    cluster->setNeedsClusterRecalc();
-                    break;
-                }
-            }
-        }
-
-        // If the cluster needs a recalc, mark all blocks as needing a layout so they pick up the new cluster info.
-        if (cluster->needsClusterRecalc()) {
-            for (WTF::HashSet<RenderBlock*>::iterator block = blocks.begin(); block != blocks.end(); ++block)
-                (*block)->setNeedsLayout();
-        }
-    }
-}
 
-bool FastTextAutosizer::updateWindowWidth()
-{
-    int originalWindowWidth = m_windowWidth;
+    if (!shouldBeClusterRoot(block))
+        return;
 
-    Frame* mainFrame = m_document->page()->mainFrame();
-    IntSize windowSize = m_document->settings()->textAutosizingWindowSizeOverride();
-    if (windowSize.isEmpty())
-        windowSize = mainFrame->view()->unscaledVisibleContentSize(ScrollableArea::IncludeScrollbars);
-    m_windowWidth = windowSize.width();
+    AtomicString fingerprint = computeFingerprint(block);
+    if (fingerprint.isNull())
+        return;
 
-    return m_windowWidth != originalWindowWidth;
+    m_fingerprintMapper.add(block, fingerprint);
 }
 
-void FastTextAutosizer::record(RenderBlock* block)
+void FastTextAutosizer::destroy(RenderBlock* block)
 {
-    if (!m_document->settings()
-        || !m_document->settings()->textAutosizingEnabled()
-        || m_document->printing()
-        || !m_document->page())
-        return;
+    m_fingerprintMapper.remove(block);
+}
 
-    if (!TextAutosizer::isAutosizingContainer(block))
+void FastTextAutosizer::beginLayout(RenderBlock* block)
+{
+    if (!enabled())
         return;
 
-    AtomicString blockFingerprint = fingerprint(block);
-    HashMap<AtomicString, OwnPtr<Cluster> >::AddResult result =
-        m_clusterForFingerprint.add(blockFingerprint, PassOwnPtr<Cluster>());
+    if (block->isRenderView())
+        prepareWindowInfo(toRenderView(block));
 
-    if (result.isNewEntry)
-        result.iterator->value = adoptPtr(new Cluster(blockFingerprint));
-
-    Cluster* cluster = result.iterator->value.get();
-    cluster->addBlock(block);
-
-    m_clusterForBlock.set(block, cluster);
+    if (shouldBeClusterRoot(block))
+        m_clusterStack.append(getOrCreateCluster(block));
 }
 
-void FastTextAutosizer::destroy(RenderBlock* block)
+void FastTextAutosizer::inflate(RenderBlock* block)
 {
-    Cluster* cluster = m_clusterForBlock.take(block);
-    if (!cluster)
-        return;
-    cluster->m_blocks.remove(block);
-    if (cluster->m_blocks.isEmpty()) {
-        // This deletes the Cluster.
-        m_clusterForFingerprint.remove(cluster->m_fingerprint);
+    if (m_clusterStack.isEmpty())
         return;
+    Cluster* cluster = m_clusterStack.last();
+
+    applyMultiplier(block, cluster->m_multiplier);
+
+    // FIXME: Add an optimization to not do this walk if it's not needed.
+    for (InlineWalker walker(block); !walker.atEnd(); walker.advance()) {
+        RenderObject* inlineObj = walker.current();
+        if (inlineObj->isText())
+            applyMultiplier(inlineObj, cluster->m_multiplier);
     }
-    cluster->setNeedsClusterRecalc();
 }
 
-static void applyMultiplier(RenderObject* renderer, float multiplier)
+void FastTextAutosizer::endLayout(RenderBlock* block)
 {
-    RenderStyle* currentStyle  = renderer->style();
-    if (currentStyle->textAutosizingMultiplier() == multiplier)
+    if (!enabled())
         return;
 
-    // We need to clone the render style to avoid breaking style sharing.
-    RefPtr<RenderStyle> style = RenderStyle::clone(currentStyle);
-    style->setTextAutosizingMultiplier(multiplier);
-    style->setUnique();
-    renderer->setStyleInternal(style.release());
+    if (!m_clusterStack.isEmpty() && m_clusterStack.last()->m_root == block)
+        m_clusterStack.removeLast();
 }
 
-void FastTextAutosizer::inflate(RenderBlock* block)
+bool FastTextAutosizer::enabled()
 {
-    Cluster* cluster = 0;
-    for (const RenderObject* clusterBlock = block; clusterBlock && !cluster; clusterBlock = clusterBlock->parent()) {
-        if (clusterBlock->isRenderBlock())
-            cluster = m_clusterForBlock.get(toRenderBlock(clusterBlock));
-    }
-    if (!cluster)
-        return;
+    return m_document->settings()
+        && m_document->settings()->textAutosizingEnabled()
+        && !m_document->printing()
+        && m_document->page();
+}
 
-    recalcClusterIfNeeded(cluster);
+void FastTextAutosizer::prepareWindowInfo(RenderView* renderView)
+{
+    bool horizontalWritingMode = isHorizontalWritingMode(renderView->style()->writingMode());
 
-    applyMultiplier(block, cluster->m_multiplier);
+    Frame* mainFrame = m_document->page()->mainFrame();
+    IntSize windowSize = m_document->settings()->textAutosizingWindowSizeOverride();
+    if (windowSize.isEmpty())
+        windowSize = mainFrame->view()->unscaledVisibleContentSize(ScrollableArea::IncludeScrollbars);
+    m_windowWidth = horizontalWritingMode ? windowSize.width() : windowSize.height();
 
-    // FIXME: Add an optimization to not do this walk if it's not needed.
-    for (InlineWalker walker(block); !walker.atEnd(); walker.advance()) {
-        RenderObject* inlineObj = walker.current();
-        if (inlineObj->isRenderBlock() && m_clusterForBlock.contains(toRenderBlock(inlineObj)))
-            continue;
+    IntSize layoutSize = m_document->page()->mainFrame()->view()->layoutSize();
+    m_layoutWidth = horizontalWritingMode ? layoutSize.width() : layoutSize.height();
+}
 
-        applyMultiplier(inlineObj, cluster->m_multiplier);
-    }
+bool FastTextAutosizer::shouldBeClusterRoot(RenderBlock* block)
+{
+    // FIXME: move the logic out of TextAutosizer.cpp into this class.
+    return block->isRenderView()
+        || (TextAutosizer::isAutosizingContainer(block)
+            && TextAutosizer::isIndependentDescendant(block));
 }
 
-AtomicString FastTextAutosizer::fingerprint(const RenderBlock* block)
+bool FastTextAutosizer::clusterWantsAutosizing(RenderBlock* root)
 {
-    // FIXME(crbug.com/322340): Implement a better fingerprinting algorithm.
-    return AtomicString::number((unsigned long long) block);
+    // FIXME: this should be slightly different.
+    return TextAutosizer::containerShouldBeAutosized(root);
 }
 
-void FastTextAutosizer::recalcClusterIfNeeded(FastTextAutosizer::Cluster* cluster)
+AtomicString FastTextAutosizer::computeFingerprint(RenderBlock* block)
 {
-    ASSERT(m_windowWidth > 0);
-    if (!cluster->needsClusterRecalc())
-        return;
+    // FIXME(crbug.com/322340): Implement a fingerprinting algorithm.
+    return nullAtom;
+}
+
+FastTextAutosizer::Cluster* FastTextAutosizer::getOrCreateCluster(RenderBlock* block)
+{
+    ClusterMap::AddResult addResult = m_clusters.add(block, PassOwnPtr<Cluster>());
+    if (!addResult.isNewEntry)
+        return addResult.iterator->value.get();
+
+    AtomicString fingerprint = m_fingerprintMapper.get(block);
+    if (fingerprint.isNull()) {
+        addResult.iterator->value = adoptPtr(createCluster(block));
+        return addResult.iterator->value.get();
+    }
+    return addSupercluster(m_fingerprintMapper.getBlocks(fingerprint), block);
+}
+
+FastTextAutosizer::Cluster* FastTextAutosizer::createCluster(RenderBlock* block)
+{
+    float multiplier = clusterWantsAutosizing(block) ? computeMultiplier(block) : 1.0f;
+    return new Cluster(block, multiplier);
+}
 
-    WTF::HashSet<RenderBlock*>& blocks = cluster->m_blocks;
+FastTextAutosizer::Cluster* FastTextAutosizer::addSupercluster(WTF::HashSet<RenderBlock*>& roots, RenderBlock* returnFor)

[pdr., 2014/01/07 19:50:27]

Would it be cleaner to change this to:
FastTextAutosizer::Cluster* FastTextAutosizer::addSupercluster(RenderBlock*
block)
and have the function look up the roots?

[skobes, 2014/01/07 20:10:53]

How about passing the fingerprint in, and having it look up the BlockSet from
that?

(Note that the RenderBlock* param is a performance optimization to save us a
lookup for the first cluster, it's incidental to the purpose of
addSupercluster.)

+{
+    RenderBlock* superRoot = deepestCommonAncestor(roots);
 
     bool shouldAutosize = false;
-    for (WTF::HashSet<RenderBlock*>::iterator it = blocks.begin(); it != blocks.end(); ++it)
-        shouldAutosize |= TextAutosizer::containerShouldBeAutosized(*it);
+    for (WTF::HashSet<RenderBlock*>::iterator it = roots.begin(); it != roots.end(); ++it)
+        shouldAutosize |= clusterWantsAutosizing(*it);
 
-    if (!shouldAutosize) {
-        cluster->m_multiplier = 1.0f;
-        return;
+    float multiplier = shouldAutosize ? computeMultiplier(superRoot) : 1.0f;
+
+    Cluster* result = 0;
+    for (WTF::HashSet<RenderBlock*>::iterator it = roots.begin(); it != roots.end(); ++it) {
+        Cluster* cluster = new Cluster(*it, multiplier);
+        m_clusters.set(*it, adoptPtr(cluster));
+
+        if (*it == returnFor)
+            result = cluster;
     }
+    return result;
+}
 
+RenderBlock* FastTextAutosizer::deepestCommonAncestor(WTF::HashSet<RenderBlock*>& blocks)

[pdr., 2014/01/07 19:50:27]

It may be clean to pull out the typedef for BlockSet and use it here (and
above).

[skobes, 2014/01/07 20:10:53]

This is a great idea :)

+{
     // 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.
-    cluster->m_clusterRoot = 0;
-    HashCountedSet<const RenderObject*> ancestors;
-    for (WTF::HashSet<RenderBlock*>::iterator it = blocks.begin(); !cluster->m_clusterRoot && it != blocks.end(); ++it) {
-        const RenderObject* renderer = (*it);
-        while (renderer && (renderer = renderer->parent())) {
-            ancestors.add(renderer);
-            // The first ancestor that has all of the blocks as children wins and is crowned the cluster root.
-            if (ancestors.count(renderer) == blocks.size()) {
-                cluster->m_clusterRoot = renderer->isRenderBlock() ? renderer : renderer->containingBlock();
-                break;
-            }
+    HashCountedSet<RenderObject*> ancestors;
+    for (WTF::HashSet<RenderBlock*>::iterator it = blocks.begin(); it != blocks.end(); ++it) {
+        for (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;
+}
 
-    ASSERT(cluster->m_clusterRoot);
-    bool horizontalWritingMode = isHorizontalWritingMode(cluster->m_clusterRoot->style()->writingMode());
+float FastTextAutosizer::computeMultiplier(RenderBlock* block)
+{
+    // Block width, in CSS pixels.
+    float blockWidth = block->contentLogicalWidth();
 
-    // Largest area of block that can be visible at once (assuming the main
-    // frame doesn't get scaled to less than overview scale), in CSS pixels.
-    IntSize layoutSize = m_document->page()->mainFrame()->view()->layoutSize();
-    float layoutWidth = horizontalWritingMode ? layoutSize.width() : layoutSize.height();
+    // FIXME: incorporate font scale factor.
+    // FIXME: incorporate device scale adjustment.
+    return max(min(blockWidth, (float) m_layoutWidth) / m_windowWidth, 1.0f);
+}
 
-    // Cluster root layout width, in CSS pixels.
-    float rootWidth = toRenderBlock(cluster->m_clusterRoot)->contentLogicalWidth();
+void FastTextAutosizer::applyMultiplier(RenderObject* renderer, float multiplier)
+{
+    RenderStyle* currentStyle = renderer->style();
+    if (currentStyle->textAutosizingMultiplier() == multiplier)
+        return;
 
-    // FIXME: incorporate font scale factor.
-    float multiplier = min(rootWidth, layoutWidth) / m_windowWidth;
-    cluster->m_multiplier = max(multiplier, 1.0f);
+    // We need to clone the render style to avoid breaking style sharing.
+    RefPtr<RenderStyle> style = RenderStyle::clone(currentStyle);
+    style->setTextAutosizingMultiplier(multiplier);
+    style->setUnique();
+    renderer->setStyleInternal(style.release());
+}
+
+void FastTextAutosizer::FingerprintMapper::add(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);
+}
+
+void FastTextAutosizer::FingerprintMapper::remove(RenderBlock* block)
+{
+    AtomicString fingerprint = m_fingerprints.take(block);
+    if (fingerprint.isNull())
+        return;
+
+    ReverseFingerprintMap::iterator blocksIter = m_blocksForFingerprint.find(fingerprint);
+    WTF::HashSet<RenderBlock*>& blocks = *blocksIter->value;
+    blocks.remove(block);
+    if (blocks.isEmpty())
+        m_blocksForFingerprint.remove(blocksIter);
+}
+
+AtomicString FastTextAutosizer::FingerprintMapper::get(RenderBlock* block)
+{
+    return m_fingerprints.get(block);
+}
+
+WTF::HashSet<RenderBlock*>& FastTextAutosizer::FingerprintMapper::getBlocks(AtomicString fingerprint)
+{
+    return *m_blocksForFingerprint.get(fingerprint);
 }
 
 } // namespace WebCore