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