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