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