ChangeLog

2012-11-29  Anton Vayvod  <avayvod@chromium.org>

        Text Autosizing: text nodes wider than their ancestor clusters should be autosized as separate clusters

        https://bugs.webkit.org/show_bug.cgi?id=103627

        Reviewed by NOBODY (OOPS!).

        isAutosizingCluster() is checking for the width of the container being greater than the width of its

        descendant cluster (more precisely, its text nodes least common ancestor). This ancestor RenderBlock is

        passed throughout tree traversal methods.

        Algorithm that searches for text nodes least common ancestor had to be modified to avoid circular dependency

        between finding LCA and determining if container is a cluster. After initial LCA is found, we check if any of

        text leafs' parent nodes are clusters due to the new definition and if so, we find new text leafs and new LCA.

        This is repeated until there are no clusters in paths from LCA to the first and last text leafs.

        The change fixes several cases covered by existing tests.

        * rendering/TextAutosizer.cpp:

        (WebCore::TextAutosizer::processSubtree): passes found root cluster to processCluster as initial stayWithin value.

        (WebCore::TextAutosizer::processCluster): stayWithin parameter (for assertion only), passes found block containing all text into processContainer.

        (WebCore::TextAutosizer::processContainer): stayWithin parameter passed into processCluster and isAutosizingCluster.

        (WebCore::TextAutosizer::isAutosizingCluster): considers a block that is wider than its parent, containing all text nodes within the parent cluster, to be a cluster itself.

        (WebCore::TextAutosizer::clusterShouldBeAutosized): passes new parameter to measureDescendantTextWidth.

        (WebCore::TextAutosizer::measureDescendantTextWidth): uses stayWithin parameter to pass to isAutosizingCluster.

        (WebCore::TextAutosizer::findDeepestBlockContainingAllText): reimplemented to incrementally filter out clusters that are wider than the currently found block.

        (WebCore::TextAutosizer::findClosestCluster): find the first cluster in a collection of RenderObjects starting from the given position.

        (WebCore::TextAutosizer::findFirstTextLeafNotInCluster): finds text leaf that doesn't belong to any cluster, starts searching from the first child of the last node in the path.

        (WebCore::TextAutosizer::findNextTextLeafNotInCluster): finds text leaf that doesn't belong to any cluster, starts searching from the next sibling of the last node in the path.

        (WebCore::TextAutosizer::firstChildNotCluster): finds the first child of RenderObject that is not a cluster.

        (WebCore::TextAutosizer::nextSiblingNotCluster): finds the next sibling of RenderObject that is not a cluster.

        (WebCore::TextAutosizer::isObjectAutosizingCluster): convenience method reducing code duplication.

        (WebCore::TextAutosizer::objectFirstChild): convenience method reducing code duplication.

        (WebCore::TextAutosizer::objectNextSibling): convenience method reducing code duplication.

        * rendering/TextAutosizer.h:

        (TextAutosizer): type for a collection of const RenderObject*, new method definitions.

2012-11-29  Sheriff Bot  <webkit.review.bot@gmail.com>

        Unreviewed, rolling out r136111.

Source/WebCore/rendering/TextAutosizer.cpp

@@bool TextAutosizer::processSubtree(RenderObject* layoutRoot)

        container = container->containingBlock();

    RenderBlock* cluster = container;

88 while (cluster && (!isAutosizingContainer(cluster) || !isAutosizingCluster(cluster)))

88 while (cluster && (!isAutosizingContainer(cluster) || !isAutosizingCluster(cluster, 0)))

8989 cluster = cluster->containingBlock();

9090

91 processCluster(cluster, container, layoutRoot, windowInfo);

91 processCluster(cluster, container, cluster, layoutRoot, windowInfo);

    return true;

}

95 void TextAutosizer::processCluster(RenderBlock* cluster, RenderBlock* container, RenderObject* subtreeRoot, const TextAutosizingWindowInfo& windowInfo)

95void TextAutosizer::processCluster(RenderBlock* cluster, RenderBlock* container, const RenderBlock* stayWithin, RenderObject* subtreeRoot, const TextAutosizingWindowInfo& windowInfo)

9696{

97 ASSERT(isAutosizingCluster(cluster));

97 ASSERT_UNUSED(stayWithin, isAutosizingCluster(cluster, stayWithin));

    // Many pages set a max-width on their content. So especially for the

    // RenderView, instead of just taking the width of |cluster| we find

    // the lowest common ancestor of the first and last descendant text node of

    // the cluster (i.e. the deepest wrapper block that contains all the text),

    // and use its width instead.

104 const RenderBlock* ~~low~~est~~Commo~~n~~Anc~~es~~tor~~ = findDeepestBlockContainingAllText(cluster);

105 float ~~commonAnc~~es~~tor~~Width = ~~low~~est~~Commo~~n~~Anc~~es~~tor~~->contentLogicalWidth();

104 const RenderBlock* deepestBlockContainingAllText = findDeepestBlockContainingAllText(cluster);

105 float textWidth = deepestBlockContainingAllText->contentLogicalWidth();

106106

107107 float multiplier = 1;

108 if (clusterShouldBeAutosized(~~low~~est~~Commo~~n~~Anc~~es~~tor, commonAnc~~es~~tor~~Width)) {

108 if (clusterShouldBeAutosized(deepestBlockContainingAllText, textWidth)) {

        int logicalWindowWidth = cluster->isHorizontalWritingMode() ? windowInfo.windowSize.width() : windowInfo.windowSize.height();

        int logicalLayoutWidth = cluster->isHorizontalWritingMode() ? windowInfo.minLayoutSize.width() : windowInfo.minLayoutSize.height();

        // Ignore box width in excess of the layout width, to avoid extreme multipliers.

112 float logicalClusterWidth = std::min<float>(~~commonAnc~~es~~tor~~Width, logicalLayoutWidth);

112 float logicalClusterWidth = std::min<float>(textWidth, logicalLayoutWidth);

        multiplier = logicalClusterWidth / logicalWindowWidth;

        multiplier *= m_document->settings()->textAutosizingFontScaleFactor();

        multiplier = std::max(1.0f, multiplier);

    }

119 processContainer(multiplier, container, subtreeRoot, windowInfo);

119 processContainer(multiplier, container, deepestBlockContainingAllText, subtreeRoot, windowInfo);

}

static bool contentHeightIsConstrained(const RenderBlock* container)

@@static bool contentHeightIsConstrained(const RenderBlock* container)

    return false;

}

142 void TextAutosizer::processContainer(float multiplier, RenderBlock* container, RenderObject* subtreeRoot, const TextAutosizingWindowInfo& windowInfo)

142void TextAutosizer::processContainer(float multiplier, RenderBlock* container, const RenderBlock* stayWithin, RenderObject* subtreeRoot, const TextAutosizingWindowInfo& windowInfo)

{

    ASSERT(isAutosizingContainer(container));

@@void TextAutosizer::processContainer(float multiplier, RenderBlock* container, R

            // FIXME: Increase list marker size proportionately.

        } else if (isAutosizingContainer(descendant)) {

            RenderBlock* descendantBlock = toRenderBlock(descendant);

158 if (isAutosizingCluster(descendantBlock))

159 processCluster(descendantBlock, descendantBlock, descendantBlock, windowInfo);

158 if (isAutosizingCluster(descendantBlock, stayWithin))

159 processCluster(descendantBlock, descendantBlock, stayWithin, descendantBlock, windowInfo);

160160 else

161 processContainer(multiplier, descendantBlock, descendantBlock, windowInfo);

161 processContainer(multiplier, descendantBlock, stayWithin, descendantBlock, windowInfo);

        }

        descendant = nextInPreOrderSkippingDescendantsOfContainers(descendant, subtreeRoot);

    }

@@bool TextAutosizer::isAutosizingContainer(const RenderObject* renderer)

        && (!renderer->isListItem() || renderer->isOutOfFlowPositioned());

}

214 bool TextAutosizer::isAutosizingCluster(const RenderBlock* renderer)

214bool TextAutosizer::isAutosizingCluster(const RenderBlock* renderer, const RenderBlock* stayWithin)

{

    // "Autosizing clusters" are special autosizing containers within which we

    // want to enforce a uniform text size multiplier, in the hopes of making

@@bool TextAutosizer::isAutosizingCluster(const RenderBlock* renderer)

    // from the box's parent (we want to avoid having significantly different

    // width blocks within a cluster, since the narrower blocks would end up

    // larger than would otherwise be necessary).

235 // If a container is wider than its |stayWithin| parent, it becomes a cluster.

    ASSERT(isAutosizingContainer(renderer));

    return renderer->isRenderView()

@@bool TextAutosizer::isAutosizingCluster(const RenderBlock* renderer)

        || renderer->isTableCaption()

        || renderer->isFlexibleBoxIncludingDeprecated()

        || renderer->hasColumns()

244 || renderer->containingBlock()->isHorizontalWritingMode() != renderer->isHorizontalWritingMode();

245 || renderer->containingBlock()->isHorizontalWritingMode() != renderer->isHorizontalWritingMode()

246 || (stayWithin && renderer->contentLogicalWidth() > stayWithin->contentLogicalWidth());

    // FIXME: Tables need special handling to multiply all their columns by

    // the same amount even if they're different widths; so do hasColumns()

    // renderers, and probably flexboxes...

@@bool TextAutosizer::clusterShouldBeAutosized(const RenderBlock* lowestCommonAnce

    const float minLinesOfText = 4;

    float minTextWidth = commonAncestorWidth * minLinesOfText;

    float textWidth = 0;

265 measureDescendantTextWidth(lowestCommonAncestor, minTextWidth, textWidth);

267 measureDescendantTextWidth(lowestCommonAncestor, lowestCommonAncestor, minTextWidth, textWidth);

    if (textWidth >= minTextWidth)

        return true;

    return false;

}

271 void TextAutosizer::measureDescendantTextWidth(const RenderBlock* container, float minTextWidth, float& textWidth)

273void TextAutosizer::measureDescendantTextWidth(const RenderBlock* stayWithin, const RenderBlock* container, float minTextWidth, float& textWidth)

{

    bool skipLocalText = contentHeightIsConstrained(container);

@@void TextAutosizer::measureDescendantTextWidth(const RenderBlock* container, flo

            textWidth += toRenderText(descendant)->renderedTextLength() * descendant->style()->specifiedFontSize();

        } else if (isAutosizingContainer(descendant)) {

            RenderBlock* descendantBlock = toRenderBlock(descendant);

281 if (!isAutosizingCluster(descendantBlock))

282 measureDescendantTextWidth(descendantBlock, minTextWidth, textWidth);

283 if (!isAutosizingCluster(descendantBlock, stayWithin))

284 measureDescendantTextWidth(stayWithin, descendantBlock, minTextWidth, textWidth);

        }

        if (textWidth >= minTextWidth)

            return;

@@RenderObject* TextAutosizer::nextInPreOrderSkippingDescendantsOfContainers(const

    return 0;

}

306 const RenderBlock* TextAutosizer::findDeepestBlockContainingAllText(const RenderBlock* cluster)

308const RenderBlock* TextAutosizer::findDeepestBlockContainingAllText(const RenderBlock* subtreeRoot)

307309{

    ASSERT(isAutosizingCluster(cluster));

    size_t firstDepth = 0;

    const RenderObject* firstTextLeaf = findFirstTextLeafNotInCluster(cluster, firstDepth, FirstToLast);

310 RenderObjects firstPath(1, subtreeRoot);

311 const RenderObject* firstTextLeaf = findFirstTextLeafNotInCluster(FirstToLast, firstPath);

312312 if (!firstTextLeaf)

313 return cluster;

313 return subtreeRoot;

314314

315 ~~size_t~~ last~~Dep~~th ~~= 0~~;

316 const RenderObject* lastTextLeaf = findFirstTextLeafNotInCluster(~~cluster, lastDepth,~~ LastToFirst);

315 RenderObjects lastPath(1, subtreeRoot);

316 const RenderObject* lastTextLeaf = findFirstTextLeafNotInCluster(LastToFirst, lastPath);

317317 ASSERT(lastTextLeaf);

318318

    // 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;

    }

    const RenderBlock* containingBlock = 0;

    do {

        size_t minSize = std::min(firstPath.size(), lastPath.size());

        size_t firstNotEqualIndex = 1;

        while (firstNotEqualIndex < minSize && firstPath[firstNotEqualIndex] == lastPath[firstNotEqualIndex])

            firstNotEqualIndex++;

        const RenderObject* lowestCommonAncestor = firstPath[firstNotEqualIndex - 1];

        if (lowestCommonAncestor->isRenderBlock())

            containingBlock = toRenderBlock(lowestCommonAncestor);

        else

            containingBlock = lowestCommonAncestor->containingBlock();

        ASSERT(containingBlock->isDescendantOf(subtreeRoot));

        // Check if any of text leafs parents are going to be clusters due to being wider than the block just found.

        // In such case we need to start searching for the corresponding leaf again from the next not cluster node

        // after the closest cluster descendant in the corresponding path.

        size_t clusterInFirstPath = findClosestCluster(firstPath, firstNotEqualIndex, containingBlock);

        if (clusterInFirstPath < firstPath.size()) {

            firstPath.remove(clusterInFirstPath + 1, firstPath.size() - (clusterInFirstPath + 1));

            firstTextLeaf = findNextTextLeafNotInCluster(FirstToLast, firstPath);

            containingBlock = 0;

        }

        size_t clusterInLastPath = findClosestCluster(lastPath, firstNotEqualIndex, containingBlock);

        if (clusterInLastPath < lastPath.size()) {

            lastPath.remove(clusterInLastPath + 1, lastPath.size() - (clusterInLastPath + 1));

            lastTextLeaf = findNextTextLeafNotInCluster(LastToFirst, lastPath);

            containingBlock = 0;

        }

        if (!containingBlock && (!firstTextLeaf || !lastTextLeaf))

            containingBlock = subtreeRoot;

    } while (!containingBlock);

330350

    // 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();

    }

351 return containingBlock;

352}

336353

337 if (firstNode->isRenderBlock())

338 return toRenderBlock(firstNode);

size_t TextAutosizer::findClosestCluster(const RenderObjects& objects, size_t startFrom, const RenderBlock* stayWithin)

{

    for (size_t i = startFrom; i < objects.size(); ++i)

        if (isObjectAutosizingCluster(objects[i], stayWithin))

            return i;

    return objects.size();

}

339361

    // 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

    // nodes lowest common ancestor as isAutosizingCluster would have made them into their own independent

    // cluster.

    RenderBlock* containingBlock = firstNode->containingBlock();

    ASSERT(containingBlock->isDescendantOf(cluster));

const RenderObject* TextAutosizer::findFirstTextLeafNotInCluster(TraversalDirection direction, RenderObjects& path)

{

    while (!path.isEmpty()) {

        const RenderObject* current = path.last();

        if (current->isEmpty()) {

            if (current->isText())

                return current;

            return findNextTextLeafNotInCluster(direction, path);

        }

346371

347 return containingBlock;

        const RenderObject* next = firstChildNotCluster(direction, current);

        if (next)

            path.append(next);

        else

            return findNextTextLeafNotInCluster(direction, path);

    }

    return 0;

348379}

349380

350 const RenderObject* TextAutosizer::find~~Firs~~tTextLeafNotInCluster(~~const RenderObject* parent, size_t& depth,~~ TraversalDirection direction)

381const RenderObject* TextAutosizer::findNextTextLeafNotInCluster(TraversalDirection direction, RenderObjects& path)

351382{

    if (parent->isEmpty())

        return parent->isText() ? parent : 0;

    ++depth;

    const RenderObject* child = (direction == FirstToLast) ? parent->firstChild() : parent->lastChild();

    while (child) {

        if (!isAutosizingContainer(child) || !isAutosizingCluster(toRenderBlock(child))) {

            const RenderObject* leaf = findFirstTextLeafNotInCluster(child, depth, direction);

            if (leaf)

                return leaf;

    // Don't examine siblings of the root (first element in path).

    while (path.size() > 1) {

        const RenderObject* current = path.last();

        path.removeLast();

        const RenderObject* nextSibling = nextSiblingNotCluster(direction, current);

        if (nextSibling) {

            path.append(nextSibling);

            return findFirstTextLeafNotInCluster(direction, path);

362391 }

363 child = (direction == FirstToLast) ? child->nextSibling() : child->previousSibling();

364392 }

365 --depth;

393 return 0;

394}

366395

const RenderObject* TextAutosizer::firstChildNotCluster(TraversalDirection direction, const RenderObject* object)

{

    for (const RenderObject* child = objectFirstChild(object, direction); child; child = objectNextSibling(child, direction))

        if (!isObjectAutosizingCluster(child, 0))

            return child;

    return 0;

}

const RenderObject* TextAutosizer::nextSiblingNotCluster(TraversalDirection direction, const RenderObject* object)

{

    for (const RenderObject* sibling = objectNextSibling(object, direction); sibling; sibling = objectNextSibling(sibling, direction))

        if (!isObjectAutosizingCluster(sibling, 0))

            return sibling;

    return 0;

}

bool TextAutosizer::isObjectAutosizingCluster(const RenderObject* object, const RenderBlock* stayWithin)

{

    return isAutosizingContainer(object) && isAutosizingCluster(toRenderBlock(object), stayWithin);

}

const RenderObject* TextAutosizer::objectFirstChild(const RenderObject* object, TraversalDirection direction)

{

    return (direction == FirstToLast) ? object->firstChild() : object->lastChild();

}

const RenderObject* TextAutosizer::objectNextSibling(const RenderObject* object, TraversalDirection direction)

{

    return (direction == FirstToLast) ? object->nextSibling() : object->previousSibling();

}

} // namespace WebCore

#endif // ENABLE(TEXT_AUTOSIZING)

Source/WebCore/rendering/TextAutosizer.h

#include <wtf/Noncopyable.h>

#include <wtf/PassOwnPtr.h>

#include <wtf/PassRefPtr.h>

35#include <wtf/Vector.h>

namespace WebCore {

@@public:

    static float computeAutosizedFontSize(float specifiedSize, float multiplier);

private:

59 typedef Vector<const RenderObject*> RenderObjects;

    enum TraversalDirection {

        FirstToLast,

        LastToFirst

@@private:

    explicit TextAutosizer(Document*);

65 void processCluster(RenderBlock* cluster, RenderBlock* container, RenderObject* subtreeRoot, const TextAutosizingWindowInfo&);

66 void processContainer(float multiplier, RenderBlock* container, RenderObject* subtreeRoot, const TextAutosizingWindowInfo&);

67 void processCluster(RenderBlock* cluster, RenderBlock* container, const RenderBlock* stayWithin, RenderObject* subtreeRoot, const TextAutosizingWindowInfo&);

68 void processContainer(float multiplier, RenderBlock* container, const RenderBlock* stayWithin, RenderObject* subtreeRoot, const TextAutosizingWindowInfo&);

    void setMultiplier(RenderObject*, float);

    static bool isAutosizingContainer(const RenderObject*);

71 static bool isAutosizingCluster(const RenderBlock*);

7273

73 static bool clusterShouldBeAutosized(const RenderBlock* lowestCommonAncestor, float commonAncestorWidth);

74 static void measureDescendantTextWidth(const RenderBlock* container, float minTextWidth, float& textWidth);

    // Returns true if the specified autosizing container is also a cluster. If |stayWithin| is specified and |container| is wider,

    // it's also considered to be a cluster.

    static bool isAutosizingCluster(const RenderBlock* container, const RenderBlock* stayWithin);

    static bool clusterShouldBeAutosized(const RenderBlock* cluster, float clusterWidth);

    static void measureDescendantTextWidth(const RenderBlock* container, const RenderBlock* stayWithin, float minTextWidth, float& textWidth);

    // Use to traverse the tree of descendants, excluding descendants of containers (but returning the containers themselves).

    static RenderObject* nextInPreOrderSkippingDescendantsOfContainers(const RenderObject* current, const RenderObject* stayWithin);

@@private:

    // text node (excluding those belonging to other autosizing clusters).

    static const RenderBlock* findDeepestBlockContainingAllText(const RenderBlock* cluster);

    // Depending on the traversal direction specified, finds the first or the last leaf text node child that doesn't

    // belong to any cluster.

    static const RenderObject* findFirstTextLeafNotInCluster(const RenderObject*, size_t& depth, TraversalDirection);

    // Returns the index of the first autosizing cluster in given objects vector starting from |startFrom|.

    // If no cluster is found, returns the size of the collection of objects.

    static size_t findClosestCluster(const RenderObjects&, size_t startFrom, const RenderBlock* stayWithin);

    // Find the first leaf text node in-order that doesn't belong to any cluster under the first element of |path|.

    // Returns the found node and its complete path.

    static const RenderObject* findFirstTextLeafNotInCluster(TraversalDirection, RenderObjects& path);

    // Find the next leaf text node in-order that doesn't belong to any cluster under the first element of |path|.

    // Returns the found node and its complete path.

    static const RenderObject* findNextTextLeafNotInCluster(TraversalDirection, RenderObjects& path);

    // Finds the first child of the object that is not a cluster.

    static const RenderObject* firstChildNotCluster(TraversalDirection, const RenderObject*);

    // Finds the first sibling of the object that is not a cluster.

    static const RenderObject* nextSiblingNotCluster(TraversalDirection, const RenderObject*);

    // Returns true if the object is an autosizing container and an autosizing cluster.

    static bool isObjectAutosizingCluster(const RenderObject*, const RenderBlock* stayWithin);

    // Wrapper around firstChild() and lastChild() methods, calling one or another depending on the direction.

    static const RenderObject* objectFirstChild(const RenderObject*, TraversalDirection);

    // Wrapper around nextSibling() and previousSibling() methods, calling one or another depending on the direction.

    static const RenderObject* objectNextSibling(const RenderObject*, TraversalDirection);

    Document* m_document;

};

Source/WebCore/ChangeLog

Source/WebCore/rendering/TextAutosizer.cpp

Source/WebCore/rendering/TextAutosizer.h

LayoutTests/ChangeLog

LayoutTests/fast/text-autosizing/cluster-wide-in-narrow-expected.html

LayoutTests/fast/text-autosizing/cluster-wide-in-narrow.html

LayoutTests/fast/text-autosizing/wide-child-expected.html

LayoutTests/fast/text-autosizing/wide-child.html

LayoutTests/fast/text-autosizing/wide-in-narrow-overflow-scroll-expected.html

LayoutTests/fast/text-autosizing/wide-in-narrow-overflow-scroll.html