1/*
2 * Copyright (C) 2012 Google Inc. All rights reserved.
3 * Copyright (C) 2012 Apple Inc. All rights reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 * Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU Library General Public License
16 * along with this library; see the file COPYING.LIB.  If not, write to
17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 */
20
21#include "config.h"
22
23#if ENABLE(TEXT_AUTOSIZING)
24
25#include "TextAutosizer.h"
26
27#include "Document.h"
28#include "HTMLElement.h"
29#include "InspectorInstrumentation.h"
30#include "IntSize.h"
31#include "RenderObject.h"
32#include "RenderStyle.h"
33#include "RenderText.h"
34#include "RenderView.h"
35#include "Settings.h"
36#include "StyleInheritedData.h"
37
38#include <algorithm>
39#include <wtf/StdLibExtras.h>
40#include <wtf/Vector.h>
41
42namespace WebCore {
43
44using namespace HTMLNames;
45
46struct TextAutosizingWindowInfo {
47    IntSize windowSize;
48    IntSize minLayoutSize;
49};
50
51// Represents cluster related data. Instances should not persist between calls to processSubtree.
52struct TextAutosizingClusterInfo {
53    explicit TextAutosizingClusterInfo(RenderBlock* root)
54        : root(root)
55        , blockContainingAllText(0)
56        , maxAllowedDifferenceFromTextWidth(150)
57    {
58    }
59
60    RenderBlock* root;
61    const RenderBlock* blockContainingAllText;
62
63    // Upper limit on the difference between the width of the cluster's block containing all
64    // text and that of a narrow child before the child becomes a separate cluster.
65    float maxAllowedDifferenceFromTextWidth;
66
67    // Descendants of the cluster that are narrower than the block containing all text and must be
68    // processed together.
69    Vector<TextAutosizingClusterInfo> narrowDescendants;
70};
71
72
73static const Vector<QualifiedName>& formInputTags()
74{
75    // Returns the tags for the form input elements.
76    DEFINE_STATIC_LOCAL(Vector<QualifiedName>, formInputTags, ());
77    if (formInputTags.isEmpty()) {
78        formInputTags.append(inputTag);
79        formInputTags.append(buttonTag);
80        formInputTags.append(selectTag);
81    }
82    return formInputTags;
83}
84
85TextAutosizer::TextAutosizer(Document* document)
86    : m_document(document)
87{
88}
89
90TextAutosizer::~TextAutosizer()
91{
92}
93
94void TextAutosizer::recalculateMultipliers()
95{
96    RenderObject* renderer = m_document->renderer();
97    while (renderer) {
98        if (renderer->style() && renderer->style()->textAutosizingMultiplier() != 1)
99            setMultiplier(renderer, 1);
100        renderer = renderer->nextInPreOrder();
101    }
102}
103
104bool TextAutosizer::processSubtree(RenderObject* layoutRoot)
105{
106    // FIXME: Text Autosizing should only be enabled when m_document->page()->mainFrame()->view()->useFixedLayout()
107    // is true, but for now it's useful to ignore this so that it can be tested on desktop.
108    if (!m_document->settings() || !m_document->settings()->textAutosizingEnabled() || layoutRoot->view()->printing() || !m_document->page())
109        return false;
110
111    Frame* mainFrame = m_document->page()->mainFrame();
112
113    TextAutosizingWindowInfo windowInfo;
114
115    // Window area, in logical (density-independent) pixels.
116    windowInfo.windowSize = m_document->settings()->textAutosizingWindowSizeOverride();
117    if (windowInfo.windowSize.isEmpty()) {
118        bool includeScrollbars = !InspectorInstrumentation::shouldApplyScreenWidthOverride(mainFrame);
119        windowInfo.windowSize = mainFrame->view()->unscaledVisibleContentSize(includeScrollbars ? ScrollableArea::IncludeScrollbars : ScrollableArea::ExcludeScrollbars);
120    }
121
122    // Largest area of block that can be visible at once (assuming the main
123    // frame doesn't get scaled to less than overview scale), in CSS pixels.
124    windowInfo.minLayoutSize = mainFrame->view()->layoutSize();
125    for (Frame* frame = m_document->frame(); frame; frame = frame->tree()->parent()) {
126        if (!frame->view()->isInChildFrameWithFrameFlattening())
127            windowInfo.minLayoutSize = windowInfo.minLayoutSize.shrunkTo(frame->view()->layoutSize());
128    }
129
130    // The layoutRoot could be neither a container nor a cluster, so walk up the tree till we find each of these.
131    RenderBlock* container = layoutRoot->isRenderBlock() ? toRenderBlock(layoutRoot) : layoutRoot->containingBlock();
132    while (container && !isAutosizingContainer(container))
133        container = container->containingBlock();
134
135    RenderBlock* cluster = container;
136    while (cluster && (!isAutosizingContainer(cluster) || !isIndependentDescendant(cluster)))
137        cluster = cluster->containingBlock();
138
139    TextAutosizingClusterInfo clusterInfo(cluster);
140    processCluster(clusterInfo, container, layoutRoot, windowInfo);
141    return true;
142}
143
144float TextAutosizer::clusterMultiplier(WritingMode writingMode, const TextAutosizingWindowInfo& windowInfo, float textWidth) const
145{
146    int logicalWindowWidth = isHorizontalWritingMode(writingMode) ? windowInfo.windowSize.width() : windowInfo.windowSize.height();
147    int logicalLayoutWidth = isHorizontalWritingMode(writingMode) ? windowInfo.minLayoutSize.width() : windowInfo.minLayoutSize.height();
148    // Ignore box width in excess of the layout width, to avoid extreme multipliers.
149    float logicalClusterWidth = std::min<float>(textWidth, logicalLayoutWidth);
150
151    float multiplier = logicalClusterWidth / logicalWindowWidth;
152    multiplier *= m_document->settings()->textAutosizingFontScaleFactor();
153    return std::max(1.0f, multiplier);
154}
155
156void TextAutosizer::processClusterInternal(TextAutosizingClusterInfo& clusterInfo, RenderBlock* container, RenderObject* subtreeRoot, const TextAutosizingWindowInfo& windowInfo, float multiplier)
157{
158    processContainer(multiplier, container, clusterInfo, subtreeRoot, windowInfo);
159
160    Vector<Vector<TextAutosizingClusterInfo> > narrowDescendantsGroups;
161    getNarrowDescendantsGroupedByWidth(clusterInfo, narrowDescendantsGroups);
162    for (size_t i = 0; i < narrowDescendantsGroups.size(); ++i)
163        processCompositeCluster(narrowDescendantsGroups[i], windowInfo);
164}
165
166void TextAutosizer::processCluster(TextAutosizingClusterInfo& clusterInfo, RenderBlock* container, RenderObject* subtreeRoot, const TextAutosizingWindowInfo& windowInfo)
167{
168    // Many pages set a max-width on their content. So especially for the RenderView, instead of
169    // just taking the width of |cluster| we find the lowest common ancestor of the first and last
170    // descendant text node of the cluster (i.e. the deepest wrapper block that contains all the
171    // text), and use its width instead.
172    clusterInfo.blockContainingAllText = findDeepestBlockContainingAllText(clusterInfo.root);
173    float textWidth = clusterInfo.blockContainingAllText->contentLogicalWidth();
174    float multiplier =  1.0;
175    if (clusterShouldBeAutosized(clusterInfo, textWidth))
176        multiplier = clusterMultiplier(clusterInfo.root->style()->writingMode(), windowInfo, textWidth);
177    processClusterInternal(clusterInfo, container, subtreeRoot, windowInfo, multiplier);
178}
179
180void TextAutosizer::processCompositeCluster(Vector<TextAutosizingClusterInfo>& clusterInfos, const TextAutosizingWindowInfo& windowInfo)
181{
182    if (clusterInfos.isEmpty())
183        return;
184
185    float maxTextWidth = 0;
186    for (size_t i = 0; i < clusterInfos.size(); ++i) {
187        TextAutosizingClusterInfo& clusterInfo = clusterInfos[i];
188        clusterInfo.blockContainingAllText = findDeepestBlockContainingAllText(clusterInfo.root);
189        maxTextWidth = max<float>(maxTextWidth, clusterInfo.blockContainingAllText->contentLogicalWidth());
190    }
191
192    float multiplier = 1.0;
193    if (compositeClusterShouldBeAutosized(clusterInfos, maxTextWidth))
194        multiplier = clusterMultiplier(clusterInfos[0].root->style()->writingMode(), windowInfo, maxTextWidth);
195    for (size_t i = 0; i < clusterInfos.size(); ++i) {
196        ASSERT(clusterInfos[i].root->style()->writingMode() == clusterInfos[0].root->style()->writingMode());
197        processClusterInternal(clusterInfos[i], clusterInfos[i].root, clusterInfos[i].root, windowInfo, multiplier);
198    }
199}
200
201void TextAutosizer::processContainer(float multiplier, RenderBlock* container, TextAutosizingClusterInfo& clusterInfo, RenderObject* subtreeRoot, const TextAutosizingWindowInfo& windowInfo)
202{
203    ASSERT(isAutosizingContainer(container));
204
205    float localMultiplier = containerShouldBeAutosized(container) ? multiplier: 1;
206
207    RenderObject* descendant = nextInPreOrderSkippingDescendantsOfContainers(subtreeRoot, subtreeRoot);
208    while (descendant) {
209        if (descendant->isText()) {
210            if (localMultiplier != 1 && descendant->style()->textAutosizingMultiplier() == 1) {
211                setMultiplier(descendant, localMultiplier);
212                setMultiplier(descendant->parent(), localMultiplier); // Parent does line spacing.
213            }
214            // FIXME: Increase list marker size proportionately.
215        } else if (isAutosizingContainer(descendant)) {
216            RenderBlock* descendantBlock = toRenderBlock(descendant);
217            TextAutosizingClusterInfo descendantClusterInfo(descendantBlock);
218            if (isWiderDescendant(descendantBlock, clusterInfo) || isIndependentDescendant(descendantBlock))
219                processCluster(descendantClusterInfo, descendantBlock, descendantBlock, windowInfo);
220            else if (isNarrowDescendant(descendantBlock, clusterInfo)) {
221                // Narrow descendants are processed together later to be able to apply the same multiplier
222                // to each of them if necessary.
223                clusterInfo.narrowDescendants.append(descendantClusterInfo);
224            } else
225                processContainer(multiplier, descendantBlock, clusterInfo, descendantBlock, windowInfo);
226        }
227        descendant = nextInPreOrderSkippingDescendantsOfContainers(descendant, subtreeRoot);
228    }
229}
230
231void TextAutosizer::setMultiplier(RenderObject* renderer, float multiplier)
232{
233    RefPtr<RenderStyle> newStyle = RenderStyle::clone(renderer->style());
234    newStyle->setTextAutosizingMultiplier(multiplier);
235    renderer->setStyle(newStyle.release());
236}
237
238float TextAutosizer::computeAutosizedFontSize(float specifiedSize, float multiplier)
239{
240    // Somewhat arbitrary "pleasant" font size.
241    const float pleasantSize = 16;
242
243    // Multiply fonts that the page author has specified to be larger than
244    // pleasantSize by less and less, until huge fonts are not increased at all.
245    // For specifiedSize between 0 and pleasantSize we directly apply the
246    // multiplier; hence for specifiedSize == pleasantSize, computedSize will be
247    // multiplier * pleasantSize. For greater specifiedSizes we want to
248    // gradually fade out the multiplier, so for every 1px increase in
249    // specifiedSize beyond pleasantSize we will only increase computedSize
250    // by gradientAfterPleasantSize px until we meet the
251    // computedSize = specifiedSize line, after which we stay on that line (so
252    // then every 1px increase in specifiedSize increases computedSize by 1px).
253    const float gradientAfterPleasantSize = 0.5;
254
255    float computedSize;
256    if (specifiedSize <= pleasantSize)
257        computedSize = multiplier * specifiedSize;
258    else {
259        computedSize = multiplier * pleasantSize + gradientAfterPleasantSize * (specifiedSize - pleasantSize);
260        if (computedSize < specifiedSize)
261            computedSize = specifiedSize;
262    }
263    return computedSize;
264}
265
266bool TextAutosizer::isAutosizingContainer(const RenderObject* renderer)
267{
268    // "Autosizing containers" are the smallest unit for which we can
269    // enable/disable Text Autosizing.
270    // - Must not be inline, as different multipliers on one line looks terrible.
271    //   Exceptions are inline-block and alike elements (inline-table, -webkit-inline-*),
272    //   as they often contain entire multi-line columns of text.
273    // - Must not be list items, as items in the same list should look consistent (*).
274    // - Must not be normal list items, as items in the same list should look
275    //   consistent, unless they are floating or position:absolute/fixed.
276    if (!renderer->isRenderBlock() || (renderer->isInline() && !renderer->style()->isDisplayReplacedType()))
277        return false;
278    if (renderer->isListItem())
279        return renderer->isFloating() || renderer->isOutOfFlowPositioned();
280    // Avoid creating containers for text within text controls, buttons, or <select> buttons.
281    Node* parentNode = renderer->parent() ? renderer->parent()->generatingNode() : 0;
282    if (parentNode && parentNode->isElementNode() && formInputTags().contains(toElement(parentNode)->tagQName()))
283        return false;
284
285    return true;
286}
287
288bool TextAutosizer::isNarrowDescendant(const RenderBlock* renderer, TextAutosizingClusterInfo& parentClusterInfo)
289{
290    ASSERT(isAutosizingContainer(renderer));
291
292    // Autosizing containers that are significantly narrower than the |blockContainingAllText| of
293    // their enclosing cluster may be acting as separate columns, hence must be autosized
294    // separately. For example the 2nd div in:
295    // <body>
296    //     <div style="float: right; width: 50%"></div>
297    //     <div style="width: 50%"></div>
298    // <body>
299    // is the left column, and should be autosized differently from the body.
300    // If however the container is only narrower by 150px or less, it's considered part of
301    // the enclosing cluster. This 150px limit is adjusted whenever a descendant container is
302    // less than 50px narrower than the current limit.
303    const float differenceFromMaxWidthDifference = 50;
304    float contentWidth = renderer->contentLogicalWidth();
305    float clusterTextWidth = parentClusterInfo.blockContainingAllText->contentLogicalWidth();
306    float widthDifference = clusterTextWidth - contentWidth;
307
308    if (widthDifference - parentClusterInfo.maxAllowedDifferenceFromTextWidth > differenceFromMaxWidthDifference)
309        return true;
310
311    parentClusterInfo.maxAllowedDifferenceFromTextWidth = std::max(widthDifference, parentClusterInfo.maxAllowedDifferenceFromTextWidth);
312    return false;
313}
314
315bool TextAutosizer::isWiderDescendant(const RenderBlock* renderer, const TextAutosizingClusterInfo& parentClusterInfo)
316{
317    ASSERT(isAutosizingContainer(renderer));
318
319    // Autosizing containers that are wider than the |blockContainingAllText| of their enclosing
320    // cluster are treated the same way as autosizing clusters to be autosized separately.
321    float contentWidth = renderer->contentLogicalWidth();
322    float clusterTextWidth = parentClusterInfo.blockContainingAllText->contentLogicalWidth();
323    return contentWidth > clusterTextWidth;
324}
325
326bool TextAutosizer::isIndependentDescendant(const RenderBlock* renderer)
327{
328    ASSERT(isAutosizingContainer(renderer));
329
330    // "Autosizing clusters" are special autosizing containers within which we
331    // want to enforce a uniform text size multiplier, in the hopes of making
332    // the major sections of the page look internally consistent.
333    // All their descendants (including other autosizing containers) must share
334    // the same multiplier, except for subtrees which are themselves clusters,
335    // and some of their descendant containers might not be autosized at all
336    // (for example if their height is constrained).
337    // Additionally, clusterShouldBeAutosized requires each cluster to contain a
338    // minimum amount of text, without which it won't be autosized.
339    //
340    // Clusters are chosen using very similar criteria to CSS flow roots, aka
341    // block formatting contexts (http://w3.org/TR/css3-box/#flow-root), since
342    // flow roots correspond to box containers that behave somewhat
343    // independently from their parent (for example they don't overlap floats).
344    // The definition of a flow root also conveniently includes most of the
345    // ways that a box and its children can have significantly different width
346    // from the box's parent (we want to avoid having significantly different
347    // width blocks within a cluster, since the narrower blocks would end up
348    // larger than would otherwise be necessary).
349    return renderer->isRenderView()
350        || renderer->isFloating()
351        || renderer->isOutOfFlowPositioned()
352        || renderer->isTableCell()
353        || renderer->isTableCaption()
354        || renderer->isFlexibleBoxIncludingDeprecated()
355        || renderer->hasColumns()
356        || renderer->containingBlock()->isHorizontalWritingMode() != renderer->isHorizontalWritingMode()
357        || renderer->style()->isDisplayReplacedType();
358    // FIXME: Tables need special handling to multiply all their columns by
359    // the same amount even if they're different widths; so do hasColumns()
360    // containers, and probably flexboxes...
361}
362
363bool TextAutosizer::isAutosizingCluster(const RenderBlock* renderer, TextAutosizingClusterInfo& parentClusterInfo)
364{
365    ASSERT(isAutosizingContainer(renderer));
366
367    return isNarrowDescendant(renderer, parentClusterInfo)
368        || isWiderDescendant(renderer, parentClusterInfo)
369        || isIndependentDescendant(renderer);
370}
371
372bool TextAutosizer::containerShouldBeAutosized(const RenderBlock* container)
373{
374    if (containerContainsOneOfTags(container, formInputTags()))
375        return false;
376
377    if (containerIsRowOfLinks(container))
378        return false;
379
380    // Don't autosize block-level text that can't wrap (as it's likely to
381    // expand sideways and break the page's layout).
382    if (!container->style()->autoWrap())
383        return false;
384
385    return !contentHeightIsConstrained(container);
386}
387
388bool TextAutosizer::containerContainsOneOfTags(const RenderBlock* container, const Vector<QualifiedName>& tags)
389{
390    const RenderObject* renderer = container;
391    while (renderer) {
392        const Node* rendererNode = renderer->node();
393        if (rendererNode && rendererNode->isElementNode()) {
394            if (tags.contains(toElement(rendererNode)->tagQName()))
395                return true;
396        }
397        renderer = nextInPreOrderSkippingDescendantsOfContainers(renderer, container);
398    }
399
400    return false;
401}
402
403bool TextAutosizer::containerIsRowOfLinks(const RenderObject* container)
404{
405    // A "row of links" is a container for which holds:
406    //  1. it should not contain non-link text elements longer than 3 characters
407    //  2. it should contain min. 3 inline links and all links should
408    //     have the same specified font size
409    //  3. it should not contain <br> elements
410    //  4. it should contain only inline elements unless they are containers,
411    //     children of link elements or children of sub-containers.
412    int linkCount = 0;
413    RenderObject* renderer = container->nextInPreOrder(container);
414    float matchingFontSize = -1;
415
416    while (renderer) {
417        if (!isAutosizingContainer(renderer)) {
418            if (renderer->isText() && toRenderText(renderer)->text()->stripWhiteSpace()->length() > 3)
419                return false;
420            if (!renderer->isInline())
421                return false;
422            if (renderer->isBR())
423                return false;
424        }
425        if (renderer->style()->isLink()) {
426            if (matchingFontSize < 0)
427                matchingFontSize = renderer->style()->specifiedFontSize();
428            else {
429                if (matchingFontSize != renderer->style()->specifiedFontSize())
430                    return false;
431            }
432
433            linkCount++;
434            // Skip traversing descendants of the link.
435            renderer = renderer->nextInPreOrderAfterChildren(container);
436        } else
437            renderer = nextInPreOrderSkippingDescendantsOfContainers(renderer, container);
438    }
439
440    return (linkCount >= 3);
441}
442
443bool TextAutosizer::contentHeightIsConstrained(const RenderBlock* container)
444{
445    // FIXME: Propagate constrainedness down the tree, to avoid inefficiently walking back up from each box.
446    // FIXME: This code needs to take into account vertical writing modes.
447    // FIXME: Consider additional heuristics, such as ignoring fixed heights if the content is already overflowing before autosizing kicks in.
448    for (; container; container = container->containingBlock()) {
449        RenderStyle* style = container->style();
450        if (style->overflowY() >= OSCROLL)
451            return false;
452        if (style->height().isSpecified() || style->maxHeight().isSpecified()) {
453            // Some sites (e.g. wikipedia) set their html and/or body elements to height:100%,
454            // without intending to constrain the height of the content within them.
455            return !container->isRoot() && !container->isBody();
456        }
457        if (container->isFloatingOrOutOfFlowPositioned())
458            return false;
459    }
460    return false;
461}
462
463bool TextAutosizer::clusterShouldBeAutosized(TextAutosizingClusterInfo& clusterInfo, float blockWidth)
464{
465    Vector<TextAutosizingClusterInfo> clusterInfos(1, clusterInfo);
466    return compositeClusterShouldBeAutosized(clusterInfos, blockWidth);
467}
468
469bool TextAutosizer::compositeClusterShouldBeAutosized(Vector<TextAutosizingClusterInfo>& clusterInfos, float blockWidth)
470{
471    // Don't autosize clusters that contain less than 4 lines of text (in
472    // practice less lines are required, since measureDescendantTextWidth
473    // assumes that characters are 1em wide, but most characters are narrower
474    // than that, so we're overestimating their contribution to the linecount).
475    //
476    // This is to reduce the likelihood of autosizing things like headers and
477    // footers, which can be quite visually distracting. The rationale is that
478    // if a cluster contains very few lines of text then it's ok to have to zoom
479    // in and pan from side to side to read each line, since if there are very
480    // few lines of text you'll only need to pan across once or twice.
481    float totalTextWidth = 0;
482    const float minLinesOfText = 4;
483    float minTextWidth = blockWidth * minLinesOfText;
484    for (size_t i = 0; i < clusterInfos.size(); ++i) {
485        measureDescendantTextWidth(clusterInfos[i].blockContainingAllText, clusterInfos[i], minTextWidth, totalTextWidth);
486        if (totalTextWidth >= minTextWidth)
487            return true;
488    }
489    return false;
490}
491
492void TextAutosizer::measureDescendantTextWidth(const RenderBlock* container, TextAutosizingClusterInfo& clusterInfo, float minTextWidth, float& textWidth)
493{
494    bool skipLocalText = !containerShouldBeAutosized(container);
495
496    RenderObject* descendant = nextInPreOrderSkippingDescendantsOfContainers(container, container);
497    while (descendant) {
498        if (!skipLocalText && descendant->isText()) {
499            textWidth += toRenderText(descendant)->renderedTextLength() * descendant->style()->specifiedFontSize();
500        } else if (isAutosizingContainer(descendant)) {
501            RenderBlock* descendantBlock = toRenderBlock(descendant);
502            if (!isAutosizingCluster(descendantBlock, clusterInfo))
503                measureDescendantTextWidth(descendantBlock, clusterInfo, minTextWidth, textWidth);
504        }
505        if (textWidth >= minTextWidth)
506            return;
507        descendant = nextInPreOrderSkippingDescendantsOfContainers(descendant, container);
508    }
509}
510
511RenderObject* TextAutosizer::nextInPreOrderSkippingDescendantsOfContainers(const RenderObject* current, const RenderObject* stayWithin)
512{
513    if (current == stayWithin || !isAutosizingContainer(current))
514        return current->nextInPreOrder(stayWithin);
515    return current->nextInPreOrderAfterChildren(stayWithin);
516}
517
518const RenderBlock* TextAutosizer::findDeepestBlockContainingAllText(const RenderBlock* cluster)
519{
520    size_t firstDepth = 0;
521    const RenderObject* firstTextLeaf = findFirstTextLeafNotInCluster(cluster, firstDepth, FirstToLast);
522    if (!firstTextLeaf)
523        return cluster;
524
525    size_t lastDepth = 0;
526    const RenderObject* lastTextLeaf = findFirstTextLeafNotInCluster(cluster, lastDepth, LastToFirst);
527    ASSERT(lastTextLeaf);
528
529    // Equalize the depths if necessary. Only one of the while loops below will get executed.
530    const RenderObject* firstNode = firstTextLeaf;
531    const RenderObject* lastNode = lastTextLeaf;
532    while (firstDepth > lastDepth) {
533        firstNode = firstNode->parent();
534        --firstDepth;
535    }
536    while (lastDepth > firstDepth) {
537        lastNode = lastNode->parent();
538        --lastDepth;
539    }
540
541    // Go up from both nodes until the parent is the same. Both pointers will point to the LCA then.
542    while (firstNode != lastNode) {
543        firstNode = firstNode->parent();
544        lastNode = lastNode->parent();
545    }
546
547    if (firstNode->isRenderBlock())
548        return toRenderBlock(firstNode);
549
550    // containingBlock() should never leave the cluster, since it only skips ancestors when finding the
551    // container of position:absolute/fixed blocks, and those cannot exist between a cluster and its text
552    // nodes lowest common ancestor as isAutosizingCluster would have made them into their own independent
553    // cluster.
554    RenderBlock* containingBlock = firstNode->containingBlock();
555    ASSERT(containingBlock->isDescendantOf(cluster));
556
557    return containingBlock;
558}
559
560const RenderObject* TextAutosizer::findFirstTextLeafNotInCluster(const RenderObject* parent, size_t& depth, TraversalDirection direction)
561{
562    if (parent->isEmpty())
563        return parent->isText() ? parent : 0;
564
565    ++depth;
566    const RenderObject* child = (direction == FirstToLast) ? parent->firstChild() : parent->lastChild();
567    while (child) {
568        if (!isAutosizingContainer(child) || !isIndependentDescendant(toRenderBlock(child))) {
569            const RenderObject* leaf = findFirstTextLeafNotInCluster(child, depth, direction);
570            if (leaf)
571                return leaf;
572        }
573        child = (direction == FirstToLast) ? child->nextSibling() : child->previousSibling();
574    }
575    --depth;
576
577    return 0;
578}
579
580namespace {
581
582// Compares the width of the specified cluster's roots in descending order.
583bool clusterWiderThanComparisonFn(const TextAutosizingClusterInfo& first, const TextAutosizingClusterInfo& second)
584{
585    return first.root->contentLogicalWidth() > second.root->contentLogicalWidth();
586}
587
588} // namespace
589
590void TextAutosizer::getNarrowDescendantsGroupedByWidth(const TextAutosizingClusterInfo& parentClusterInfo, Vector<Vector<TextAutosizingClusterInfo> >& groups)
591{
592    ASSERT(parentClusterInfo.blockContainingAllText);
593    ASSERT(groups.isEmpty());
594
595    Vector<TextAutosizingClusterInfo> clusterInfos(parentClusterInfo.narrowDescendants);
596    if (clusterInfos.isEmpty())
597        return;
598
599    std::sort(clusterInfos.begin(), clusterInfos.end(), &clusterWiderThanComparisonFn);
600    groups.grow(1);
601
602    // If the width difference between two consecutive elements of |clusterInfos| is greater than
603    // this empirically determined value, the next element should start a new group.
604    const float maxWidthDifferenceWithinGroup = 100;
605    for (size_t i = 0; i < clusterInfos.size(); ++i) {
606        groups.last().append(clusterInfos[i]);
607
608        if (i + 1 < clusterInfos.size()) {
609            float currentWidth = clusterInfos[i].root->contentLogicalWidth();
610            float nextWidth = clusterInfos[i + 1].root->contentLogicalWidth();
611            if (currentWidth - nextWidth > maxWidthDifferenceWithinGroup)
612                groups.grow(groups.size() + 1);
613        }
614    }
615}
616
617} // namespace WebCore
618
619#endif // ENABLE(TEXT_AUTOSIZING)
620