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