src/third_party/WebKit/Source/core/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 #include "core/rendering/TextAutosizer.h"
  23
  24 #include <algorithm>
  25
  26 #include "core/dom/Document.h"
  27 #include "core/frame/LocalFrame.h"
  28 #include "core/frame/Settings.h"
  29 #include "core/frame/UseCounter.h"
  30 #include "core/html/HTMLElement.h"
  31 #include "core/page/Page.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 "platform/TraceEvent.h"
  39 #include "platform/geometry/IntSize.h"
  40 #include "wtf/StdLibExtras.h"
  41
  42 namespace WebCore {
  43
  44 #define AUTOSIZING_CLUSTER_HASH
  45
  46 using namespace HTMLNames;
  47
  48 struct TextAutosizingWindowInfo {
  49     IntSize windowSize;
  50     IntSize minLayoutSize;
  51 };
  52
  53 // Represents a POD of a selection of fields for hashing. The fields are selected to detect similar
  54 // nodes in the Render Tree from the viewpoint of text autosizing.
  55 struct RenderObjectPodForHash {
  56     RenderObjectPodForHash()
  57         : qualifiedNameHash(0)
  58         , packedStyleProperties(0)
  59         , width(0)
  60     {
  61     }
  62     ~RenderObjectPodForHash() { }
  63
  64     unsigned qualifiedNameHash;
  65
  66     // Style specific selection of signals
  67     unsigned packedStyleProperties;
  68     float width;
  69 };
  70 // To allow for efficient hashing using StringHasher.
  71 COMPILE_ASSERT(!(sizeof(RenderObjectPodForHash) % sizeof(UChar)), RenderObjectPodForHashMultipleOfUchar);
  72
  73 #ifdef AUTOSIZING_DOM_DEBUG_INFO
  74 static void writeDebugInfo(RenderObject* renderObject, const AtomicString& output)
  75 {
  76     Node* node = renderObject->node();
  77     if (node && node->isElementNode())
  78         toElement(node)->setAttribute("data-autosizing", output, ASSERT_NO_EXCEPTION);
  79 }
  80 #endif
  81
  82 static const Vector<QualifiedName>& formInputTags()
  83 {
  84     // Returns the tags for the form input elements.
  85     DEFINE_STATIC_LOCAL(Vector<QualifiedName>, formInputTags, ());
  86     if (formInputTags.isEmpty()) {
  87         formInputTags.append(inputTag);
  88         formInputTags.append(buttonTag);
  89         formInputTags.append(selectTag);
  90     }
  91     return formInputTags;
  92 }
  93
  94 static RenderListItem* getAncestorListItem(const RenderObject* renderer)
  95 {
  96     RenderObject* ancestor = renderer->parent();
  97     while (ancestor && (ancestor->isRenderInline() || ancestor->isAnonymousBlock()))
  98         ancestor = ancestor->parent();
  99
 100     return (ancestor && ancestor->isListItem()) ? toRenderListItem(ancestor) : 0;
 101 }
 102
 103 static RenderObject* getAncestorList(const RenderObject* renderer)
 104 {
 105     // FIXME: Add support for <menu> elements as a possible ancestor of an <li> element,
 106     // see http://www.whatwg.org/specs/web-apps/current-work/multipage/grouping-content.html#the-li-element
 107     for (RenderObject* ancestor = renderer->parent(); ancestor; ancestor = ancestor->parent()) {
 108         Node* parentNode = ancestor->generatingNode();
 109         if (parentNode && (isHTMLOListElement(*parentNode) || isHTMLUListElement(*parentNode)))
 110             return ancestor;
 111     }
 112     return 0;
 113 }
 114
 115 static Node* getGeneratingElementNode(const RenderObject* renderer)
 116 {
 117     Node* node = renderer->generatingNode();
 118     return (node && node->isElementNode()) ? node : 0;
 119 }
 120
 121 static unsigned hashMemory(const void* data, size_t length)
 122 {
 123     return StringHasher::computeHash<UChar>(static_cast<const UChar*>(data), length / sizeof(UChar));
 124 }
 125
 126 static unsigned computeLocalHash(const RenderObject* renderer)
 127 {
 128     Node* generatingElementNode = getGeneratingElementNode(renderer);
 129     ASSERT(generatingElementNode);
 130
 131     RenderObjectPodForHash podForHash;
 132     podForHash.qualifiedNameHash = QualifiedNameHash::hash(toElement(generatingElementNode)->tagQName());
 133
 134     if (RenderStyle* style = renderer->style()) {
 135         podForHash.packedStyleProperties = style->direction();
 136         podForHash.packedStyleProperties |= (style->position() << 1);
 137         podForHash.packedStyleProperties |= (style->floating() << 4);
 138         podForHash.packedStyleProperties |= (style->display() << 6);
 139         podForHash.packedStyleProperties |= (style->width().type() << 11);
 140         // packedStyleProperties effectively using 15 bits now.
 141
 142         // consider for adding: writing mode, padding.
 143
 144         podForHash.width = style->width().getFloatValue();
 145     }
 146
 147     return hashMemory(&podForHash, sizeof(podForHash));
 148 }
 149
 150 TextAutosizer::TextAutosizer(Document* document)
 151     : m_document(document)
 152     , m_previouslyAutosized(false)
 153 {
 154 }
 155
 156 unsigned TextAutosizer::getCachedHash(const RenderObject* renderer, bool putInCacheIfAbsent)
 157 {
 158     HashMap<const RenderObject*, unsigned>::const_iterator it = m_hashCache.find(renderer);
 159     if (it != m_hashCache.end())
 160         return it->value;
 161
 162     RenderObject* rendererParent = renderer->parent();
 163     while (rendererParent && !getGeneratingElementNode(rendererParent))
 164         rendererParent = rendererParent->parent();
 165
 166     const unsigned parentHashValue = rendererParent ? getCachedHash(rendererParent, true) : 0;
 167     const unsigned hashes[2] = { parentHashValue, computeLocalHash(renderer) };
 168     const unsigned combinedHashValue = hashMemory(hashes, sizeof(hashes));
 169     if (putInCacheIfAbsent)
 170         m_hashCache.add(renderer, combinedHashValue);
 171     return combinedHashValue;
 172 }
 173
 174 bool TextAutosizer::isApplicable() const
 175 {
 176     return m_document->settings()
 177         && m_document->settings()->textAutosizingEnabled()
 178         && m_document->page()
 179         && m_document->page()->mainFrame()
 180         && m_document->page()->mainFrame()->loader().stateMachine()->committedFirstRealDocumentLoad();
 181 }
 182
 183 void TextAutosizer::recalculateMultipliers()
 184 {
 185     if (!isApplicable() && !m_previouslyAutosized)
 186         return;
 187
 188     RenderObject* renderer = m_document->renderer();
 189     while (renderer) {
 190         if (renderer->style() && renderer->style()->textAutosizingMultiplier() != 1)
 191             setMultiplier(renderer, 1);
 192         renderer = renderer->nextInPreOrder();
 193     }
 194     m_previouslyAutosized = false;
 195 }
 196
 197 bool TextAutosizer::processSubtree(RenderObject* layoutRoot)
 198 {
 199     TRACE_EVENT0("webkit", "TextAutosizer: check if needed");
 200
 201     if (!isApplicable() || layoutRoot->view()->document().printing())
 202         return false;
 203
 204     LocalFrame* mainFrame = m_document->page()->mainFrame();
 205     TextAutosizingWindowInfo windowInfo;
 206
 207     // Window area, in logical (density-independent) pixels.
 208     windowInfo.windowSize = m_document->settings()->textAutosizingWindowSizeOverride();
 209     if (windowInfo.windowSize.isEmpty())
 210         windowInfo.windowSize = mainFrame->view()->unscaledVisibleContentSize(IncludeScrollbars);
 211
 212     // Largest area of block that can be visible at once (assuming the main
 213     // frame doesn't get scaled to less than overview scale), in CSS pixels.
 214     windowInfo.minLayoutSize = mainFrame->view()->layoutSize();
 215     for (LocalFrame* frame = m_document->frame(); frame; frame = frame->tree().parent())
 216         windowInfo.minLayoutSize = windowInfo.minLayoutSize.shrunkTo(frame->view()->layoutSize());
 217
 218     // The layoutRoot could be neither a container nor a cluster, so walk up the tree till we find each of these.
 219     RenderBlock* container = layoutRoot->isRenderBlock() ? toRenderBlock(layoutRoot) : layoutRoot->containingBlock();
 220     while (container && !isAutosizingContainer(container))
 221         container = container->containingBlock();
 222
 223     RenderBlock* cluster = container;
 224     while (cluster && (!isAutosizingContainer(cluster) || !isIndependentDescendant(cluster)))
 225         cluster = cluster->containingBlock();
 226
 227     // Skip autosizing for orphaned trees, or if it will have no effect.
 228     // Note: this might suppress autosizing of an inner cluster with a different writing mode.
 229     // It's not clear what the correct behavior is for mixed writing modes anyway.
 230     if (!cluster || clusterMultiplier(cluster->style()->writingMode(), windowInfo,
 231         std::numeric_limits<float>::infinity()) == 1.0f)
 232         return false;
 233
 234     TRACE_EVENT0("webkit", "TextAutosizer: process root cluster");
 235     UseCounter::count(*m_document, UseCounter::TextAutosizing);
 236
 237     TextAutosizingClusterInfo clusterInfo(cluster);
 238     processCluster(clusterInfo, container, layoutRoot, windowInfo);
 239
 240 #ifdef AUTOSIZING_CLUSTER_HASH
 241     // Second pass to autosize stale non-autosized clusters for consistency.
 242     secondPassProcessStaleNonAutosizedClusters();
 243     m_hashCache.clear();
 244     m_hashToMultiplier.clear();
 245     m_hashesToAutosizeSecondPass.clear();
 246     m_nonAutosizedClusters.clear();
 247 #endif
 248     m_previouslyAutosized = true;
 249     return true;
 250 }
 251
 252 float TextAutosizer::clusterMultiplier(WritingMode writingMode, const TextAutosizingWindowInfo& windowInfo, float textWidth) const
 253 {
 254     int logicalWindowWidth = isHorizontalWritingMode(writingMode) ? windowInfo.windowSize.width() : windowInfo.windowSize.height();
 255     int logicalLayoutWidth = isHorizontalWritingMode(writingMode) ? windowInfo.minLayoutSize.width() : windowInfo.minLayoutSize.height();
 256     // Ignore box width in excess of the layout width, to avoid extreme multipliers.
 257     float logicalClusterWidth = std::min<float>(textWidth, logicalLayoutWidth);
 258
 259     float multiplier = logicalClusterWidth / logicalWindowWidth;
 260     multiplier *= m_document->settings()->accessibilityFontScaleFactor();
 261
 262     // If the page has a meta viewport or @viewport, don't apply the device scale adjustment.
 263     const ViewportDescription& viewportDescription = m_document->page()->mainFrame()->document()->viewportDescription();
 264     if (!viewportDescription.isSpecifiedByAuthor()) {
 265         float deviceScaleAdjustment = m_document->settings()->deviceScaleAdjustment();
 266         multiplier *= deviceScaleAdjustment;
 267     }
 268     return std::max(1.0f, multiplier);
 269 }
 270
 271 void TextAutosizer::processClusterInternal(TextAutosizingClusterInfo& clusterInfo, RenderBlock* container, RenderObject* subtreeRoot, const TextAutosizingWindowInfo& windowInfo, float multiplier)
 272 {
 273     processContainer(multiplier, container, clusterInfo, subtreeRoot, windowInfo);
 274 #ifdef AUTOSIZING_DOM_DEBUG_INFO
 275     writeDebugInfo(clusterInfo.root, AtomicString(String::format("cluster:%f", multiplier)));
 276 #endif
 277
 278     Vector<Vector<TextAutosizingClusterInfo> > narrowDescendantsGroups;
 279     getNarrowDescendantsGroupedByWidth(clusterInfo, narrowDescendantsGroups);
 280     for (size_t i = 0; i < narrowDescendantsGroups.size(); ++i)
 281         processCompositeCluster(narrowDescendantsGroups[i], windowInfo);
 282 }
 283
 284 unsigned TextAutosizer::computeCompositeClusterHash(Vector<TextAutosizingClusterInfo>& clusterInfos)
 285 {
 286     if (clusterInfos.size() == 1 && getGeneratingElementNode(clusterInfos[0].root))
 287         return getCachedHash(clusterInfos[0].root, false);
 288
 289     // FIXME: consider hashing clusters for which clusterInfos.size() > 1
 290     return 0;
 291 }
 292
 293 void TextAutosizer::addNonAutosizedCluster(unsigned key, TextAutosizingClusterInfo& value)
 294 {
 295     HashMap<unsigned, OwnPtr<Vector<TextAutosizingClusterInfo> > >::const_iterator it = m_nonAutosizedClusters.find(key);
 296     if (it == m_nonAutosizedClusters.end()) {
 297         m_nonAutosizedClusters.add(key, adoptPtr(new Vector<TextAutosizingClusterInfo>(1, value)));
 298         return;
 299     }
 300     it->value->append(value);
 301 }
 302
 303 float TextAutosizer::computeMultiplier(Vector<TextAutosizingClusterInfo>& clusterInfos, const TextAutosizingWindowInfo& windowInfo, float textWidth)
 304 {
 305 #ifdef AUTOSIZING_CLUSTER_HASH
 306     // When hashing is enabled this function returns a multiplier based on previously seen clusters.
 307     // It will return a non-unit multiplier if a cluster with the same hash value has been previously
 308     // autosized.
 309     unsigned clusterHash = computeCompositeClusterHash(clusterInfos);
 310 #else
 311     unsigned clusterHash = 0;
 312 #endif
 313
 314     if (clusterHash) {
 315         HashMap<unsigned, float>::iterator it = m_hashToMultiplier.find(clusterHash);
 316         if (it != m_hashToMultiplier.end())
 317             return it->value;
 318     }
 319
 320     if (compositeClusterShouldBeAutosized(clusterInfos, textWidth)) {
 321         float multiplier = clusterMultiplier(clusterInfos[0].root->style()->writingMode(), windowInfo, textWidth);
 322         if (clusterHash) {
 323             if (multiplier > 1 && m_nonAutosizedClusters.contains(clusterHash))
 324                 m_hashesToAutosizeSecondPass.append(clusterHash);
 325             m_hashToMultiplier.add(clusterHash, multiplier);
 326         }
 327         return multiplier;
 328     }
 329
 330     if (clusterHash)
 331         addNonAutosizedCluster(clusterHash, clusterInfos[0]);
 332
 333     return 1.0f;
 334 }
 335
 336 void TextAutosizer::processCluster(TextAutosizingClusterInfo& clusterInfo, RenderBlock* container, RenderObject* subtreeRoot, const TextAutosizingWindowInfo& windowInfo)
 337 {
 338     // Many pages set a max-width on their content. So especially for the RenderView, instead of
 339     // just taking the width of |cluster| we find the lowest common ancestor of the first and last
 340     // descendant text node of the cluster (i.e. the deepest wrapper block that contains all the
 341     // text), and use its width instead.
 342     clusterInfo.blockContainingAllText = findDeepestBlockContainingAllText(clusterInfo.root);
 343     float textWidth = clusterInfo.blockContainingAllText->contentLogicalWidth().toFloat();
 344
 345     Vector<TextAutosizingClusterInfo> clusterInfos(1, clusterInfo);
 346     float multiplier = computeMultiplier(clusterInfos, windowInfo, textWidth);
 347
 348     processClusterInternal(clusterInfo, container, subtreeRoot, windowInfo, multiplier);
 349 }
 350
 351 void TextAutosizer::processCompositeCluster(Vector<TextAutosizingClusterInfo>& clusterInfos, const TextAutosizingWindowInfo& windowInfo)
 352 {
 353     if (clusterInfos.isEmpty())
 354         return;
 355
 356     float maxTextWidth = 0;
 357     for (size_t i = 0; i < clusterInfos.size(); ++i) {
 358         TextAutosizingClusterInfo& clusterInfo = clusterInfos[i];
 359         clusterInfo.blockContainingAllText = findDeepestBlockContainingAllText(clusterInfo.root);
 360         maxTextWidth = max<float>(maxTextWidth, clusterInfo.blockContainingAllText->contentLogicalWidth().toFloat());
 361     }
 362
 363     float multiplier =  computeMultiplier(clusterInfos, windowInfo, maxTextWidth);
 364     for (size_t i = 0; i < clusterInfos.size(); ++i) {
 365         ASSERT(clusterInfos[i].root->style()->writingMode() == clusterInfos[0].root->style()->writingMode());
 366         processClusterInternal(clusterInfos[i], clusterInfos[i].root, clusterInfos[i].root, windowInfo, multiplier);
 367     }
 368 }
 369
 370 void TextAutosizer::secondPassProcessStaleNonAutosizedClusters()
 371 {
 372     for (size_t i = 0; i < m_hashesToAutosizeSecondPass.size(); ++i) {
 373         unsigned hash = m_hashesToAutosizeSecondPass[i];
 374         float multiplier = m_hashToMultiplier.get(hash);
 375         Vector<TextAutosizingClusterInfo>* val = m_nonAutosizedClusters.get(hash);
 376         for (Vector<TextAutosizingClusterInfo>::iterator it2 = val->begin(); it2 != val->end(); ++it2)
 377             processStaleContainer(multiplier, (*it2).root, *it2);
 378     }
 379 }
 380
 381 void TextAutosizer::processStaleContainer(float multiplier, RenderBlock* cluster, TextAutosizingClusterInfo& clusterInfo)
 382 {
 383     ASSERT(isAutosizingContainer(cluster));
 384
 385     // This method is different from processContainer() mainly in that it does not recurse into sub-clusters.
 386     // Multiplier updates are restricted to the specified cluster only. Also the multiplier > 1 by construction
 387     // of m_hashesToAutosizeSecondPass, so we don't need to check it explicitly.
 388     float localMultiplier = containerShouldBeAutosized(cluster) ? multiplier : 1;
 389
 390     RenderObject* descendant = nextInPreOrderSkippingDescendantsOfContainers(cluster, cluster);
 391     while (descendant) {
 392         if (descendant->isText()) {
 393             if (localMultiplier != 1 && descendant->style()->textAutosizingMultiplier() == 1) {
 394                 setMultiplier(descendant, localMultiplier);
 395                 setMultiplier(descendant->parent(), localMultiplier); // Parent does line spacing.
 396             }
 397         } else if (isAutosizingContainer(descendant)) {
 398             RenderBlock* descendantBlock = toRenderBlock(descendant);
 399             if (!isAutosizingCluster(descendantBlock, clusterInfo))
 400                 processStaleContainer(multiplier, descendantBlock, clusterInfo);
 401         }
 402         descendant = nextInPreOrderSkippingDescendantsOfContainers(descendant, cluster);
 403     }
 404 }
 405
 406 void TextAutosizer::processContainer(float multiplier, RenderBlock* container, TextAutosizingClusterInfo& clusterInfo, RenderObject* subtreeRoot, const TextAutosizingWindowInfo& windowInfo)
 407 {
 408     ASSERT(isAutosizingContainer(container));
 409 #ifdef AUTOSIZING_DOM_DEBUG_INFO
 410     writeDebugInfo(container, "container");
 411 #endif
 412
 413     float localMultiplier = (multiplier > 1 && containerShouldBeAutosized(container)) ? multiplier: 1;
 414
 415     RenderObject* descendant = nextInPreOrderSkippingDescendantsOfContainers(subtreeRoot, subtreeRoot);
 416     while (descendant) {
 417         if (descendant->isText()) {
 418             if (localMultiplier != 1 && descendant->style()->textAutosizingMultiplier() == 1) {
 419                 setMultiplier(descendant, localMultiplier);
 420                 setMultiplier(descendant->parent(), localMultiplier); // Parent does line spacing.
 421
 422                 if (RenderListItem* listItemAncestor = getAncestorListItem(descendant)) {
 423                     if (RenderObject* list = getAncestorList(listItemAncestor)) {
 424                         if (list->style()->textAutosizingMultiplier() == 1)
 425                             setMultiplierForList(list, localMultiplier);
 426                     }
 427                 }
 428             }
 429         } else if (isAutosizingContainer(descendant)) {
 430             RenderBlock* descendantBlock = toRenderBlock(descendant);
 431             TextAutosizingClusterInfo descendantClusterInfo(descendantBlock);
 432             if (isWiderDescendant(descendantBlock, clusterInfo) || isIndependentDescendant(descendantBlock))
 433                 processCluster(descendantClusterInfo, descendantBlock, descendantBlock, windowInfo);
 434             else if (isNarrowDescendant(descendantBlock, clusterInfo)) {
 435                 // Narrow descendants are processed together later to be able to apply the same multiplier
 436                 // to each of them if necessary.
 437                 clusterInfo.narrowDescendants.append(descendantClusterInfo);
 438             } else
 439                 processContainer(multiplier, descendantBlock, clusterInfo, descendantBlock, windowInfo);
 440         }
 441         descendant = nextInPreOrderSkippingDescendantsOfContainers(descendant, subtreeRoot);
 442     }
 443 }
 444
 445 void TextAutosizer::setMultiplier(RenderObject* renderer, float multiplier)
 446 {
 447     RefPtr<RenderStyle> newStyle = RenderStyle::clone(renderer->style());
 448     newStyle->setTextAutosizingMultiplier(multiplier);
 449     newStyle->setUnique();
 450     renderer->setStyle(newStyle.release());
 451 }
 452
 453 void TextAutosizer::setMultiplierForList(RenderObject* renderer, float multiplier)
 454 {
 455 #ifndef NDEBUG
 456     Node* parentNode = renderer->generatingNode();
 457     ASSERT(parentNode);
 458     ASSERT(isHTMLOListElement(parentNode) || isHTMLUListElement(parentNode));
 459 #endif
 460     setMultiplier(renderer, multiplier);
 461
 462     // Make sure all list items are autosized consistently.
 463     for (RenderObject* child = renderer->firstChild(); child; child = child->nextSibling()) {
 464         if (child->isListItem() && child->style()->textAutosizingMultiplier() == 1)
 465             setMultiplier(child, multiplier);
 466     }
 467 }
 468
 469 float TextAutosizer::computeAutosizedFontSize(float specifiedSize, float multiplier)
 470 {
 471     // Somewhat arbitrary "pleasant" font size.
 472     const float pleasantSize = 16;
 473
 474     // Multiply fonts that the page author has specified to be larger than
 475     // pleasantSize by less and less, until huge fonts are not increased at all.
 476     // For specifiedSize between 0 and pleasantSize we directly apply the
 477     // multiplier; hence for specifiedSize == pleasantSize, computedSize will be
 478     // multiplier * pleasantSize. For greater specifiedSizes we want to
 479     // gradually fade out the multiplier, so for every 1px increase in
 480     // specifiedSize beyond pleasantSize we will only increase computedSize
 481     // by gradientAfterPleasantSize px until we meet the
 482     // computedSize = specifiedSize line, after which we stay on that line (so
 483     // then every 1px increase in specifiedSize increases computedSize by 1px).
 484     const float gradientAfterPleasantSize = 0.5;
 485
 486     float computedSize;
 487     if (specifiedSize <= pleasantSize)
 488         computedSize = multiplier * specifiedSize;
 489     else {
 490         computedSize = multiplier * pleasantSize + gradientAfterPleasantSize * (specifiedSize - pleasantSize);
 491         if (computedSize < specifiedSize)
 492             computedSize = specifiedSize;
 493     }
 494     return computedSize;
 495 }
 496
 497 bool TextAutosizer::isAutosizingContainer(const RenderObject* renderer)
 498 {
 499     // "Autosizing containers" are the smallest unit for which we can
 500     // enable/disable Text Autosizing.
 501     // - Must not be inline, as different multipliers on one line looks terrible.
 502     //   Exceptions are inline-block and alike elements (inline-table, -webkit-inline-*),
 503     //   as they often contain entire multi-line columns of text.
 504     // - Must not be list items, as items in the same list should look consistent (*).
 505     // - Must not be normal list items, as items in the same list should look
 506     //   consistent, unless they are floating or position:absolute/fixed.
 507     Node* node = renderer->generatingNode();
 508     if ((node && !node->hasChildren())
 509         || !renderer->isRenderBlock()
 510         || (renderer->isInline() && !renderer->style()->isDisplayReplacedType()))
 511         return false;
 512     if (renderer->isListItem())
 513         return renderer->isFloating() || renderer->isOutOfFlowPositioned();
 514     // Avoid creating containers for text within text controls, buttons, or <select> buttons.
 515     Node* parentNode = renderer->parent() ? renderer->parent()->generatingNode() : 0;
 516     if (parentNode && parentNode->isElementNode() && formInputTags().contains(toElement(parentNode)->tagQName()))
 517         return false;
 518
 519     return true;
 520 }
 521
 522 bool TextAutosizer::isNarrowDescendant(const RenderBlock* renderer, TextAutosizingClusterInfo& parentClusterInfo)
 523 {
 524     ASSERT(isAutosizingContainer(renderer));
 525
 526     // Autosizing containers that are significantly narrower than the |blockContainingAllText| of
 527     // their enclosing cluster may be acting as separate columns, hence must be autosized
 528     // separately. For example the 2nd div in:
 529     // <body>
 530     //     <div style="float: right; width: 50%"></div>
 531     //     <div style="width: 50%"></div>
 532     // <body>
 533     // is the left column, and should be autosized differently from the body.
 534     // If however the container is only narrower by 150px or less, it's considered part of
 535     // the enclosing cluster. This 150px limit is adjusted whenever a descendant container is
 536     // less than 50px narrower than the current limit.
 537     const float differenceFromMaxWidthDifference = 50;
 538     LayoutUnit contentWidth = renderer->contentLogicalWidth();
 539     LayoutUnit clusterTextWidth = parentClusterInfo.blockContainingAllText->contentLogicalWidth();
 540     LayoutUnit widthDifference = clusterTextWidth - contentWidth;
 541
 542     if (widthDifference - parentClusterInfo.maxAllowedDifferenceFromTextWidth > differenceFromMaxWidthDifference)
 543         return true;
 544
 545     parentClusterInfo.maxAllowedDifferenceFromTextWidth = std::max(widthDifference.toFloat(), parentClusterInfo.maxAllowedDifferenceFromTextWidth);
 546     return false;
 547 }
 548
 549 bool TextAutosizer::isWiderDescendant(const RenderBlock* renderer, const TextAutosizingClusterInfo& parentClusterInfo)
 550 {
 551     ASSERT(isAutosizingContainer(renderer));
 552
 553     // Autosizing containers that are wider than the |blockContainingAllText| of their enclosing
 554     // cluster are treated the same way as autosizing clusters to be autosized separately.
 555     LayoutUnit contentWidth = renderer->contentLogicalWidth();
 556     LayoutUnit clusterTextWidth = parentClusterInfo.blockContainingAllText->contentLogicalWidth();
 557     return contentWidth > clusterTextWidth;
 558 }
 559
 560 bool TextAutosizer::isIndependentDescendant(const RenderBlock* renderer)
 561 {
 562     ASSERT(isAutosizingContainer(renderer));
 563
 564     // "Autosizing clusters" are special autosizing containers within which we
 565     // want to enforce a uniform text size multiplier, in the hopes of making
 566     // the major sections of the page look internally consistent.
 567     // All their descendants (including other autosizing containers) must share
 568     // the same multiplier, except for subtrees which are themselves clusters,
 569     // and some of their descendant containers might not be autosized at all
 570     // (for example if their height is constrained).
 571     // Additionally, clusterShouldBeAutosized requires each cluster to contain a
 572     // minimum amount of text, without which it won't be autosized.
 573     //
 574     // Clusters are chosen using very similar criteria to CSS flow roots, aka
 575     // block formatting contexts (http://w3.org/TR/css3-box/#flow-root), since
 576     // flow roots correspond to box containers that behave somewhat
 577     // independently from their parent (for example they don't overlap floats).
 578     // The definition of a flow root also conveniently includes most of the
 579     // ways that a box and its children can have significantly different width
 580     // from the box's parent (we want to avoid having significantly different
 581     // width blocks within a cluster, since the narrower blocks would end up
 582     // larger than would otherwise be necessary).
 583     RenderBlock* containingBlock = renderer->containingBlock();
 584     return renderer->isRenderView()
 585         || renderer->isFloating()
 586         || renderer->isOutOfFlowPositioned()
 587         || renderer->isTableCell()
 588         || renderer->isTableCaption()
 589         || renderer->isFlexibleBoxIncludingDeprecated()
 590         || renderer->hasColumns()
 591         || (containingBlock && containingBlock->isHorizontalWritingMode() != renderer->isHorizontalWritingMode())
 592         || renderer->style()->isDisplayReplacedType()
 593         || renderer->isTextArea()
 594         || renderer->style()->userModify() != READ_ONLY;
 595     // FIXME: Tables need special handling to multiply all their columns by
 596     // the same amount even if they're different widths; so do hasColumns()
 597     // containers, and probably flexboxes...
 598 }
 599
 600 bool TextAutosizer::isAutosizingCluster(const RenderBlock* renderer, TextAutosizingClusterInfo& parentClusterInfo)
 601 {
 602     ASSERT(isAutosizingContainer(renderer));
 603
 604     return isNarrowDescendant(renderer, parentClusterInfo)
 605         || isWiderDescendant(renderer, parentClusterInfo)
 606         || isIndependentDescendant(renderer);
 607 }
 608
 609 bool TextAutosizer::containerShouldBeAutosized(const RenderBlock* container)
 610 {
 611     if (containerContainsOneOfTags(container, formInputTags()))
 612         return false;
 613
 614     if (containerIsRowOfLinks(container))
 615         return false;
 616
 617     // Don't autosize block-level text that can't wrap (as it's likely to
 618     // expand sideways and break the page's layout).
 619     if (!container->style()->autoWrap())
 620         return false;
 621
 622     return !contentHeightIsConstrained(container);
 623 }
 624
 625 bool TextAutosizer::containerContainsOneOfTags(const RenderBlock* container, const Vector<QualifiedName>& tags)
 626 {
 627     const RenderObject* renderer = container;
 628     while (renderer) {
 629         const Node* rendererNode = renderer->node();
 630         if (rendererNode && rendererNode->isElementNode()) {
 631             if (tags.contains(toElement(rendererNode)->tagQName()))
 632                 return true;
 633         }
 634         renderer = nextInPreOrderSkippingDescendantsOfContainers(renderer, container);
 635     }
 636
 637     return false;
 638 }
 639
 640 bool TextAutosizer::containerIsRowOfLinks(const RenderObject* container)
 641 {
 642     // A "row of links" is a container for which holds:
 643     //  1. it should not contain non-link text elements longer than 3 characters
 644     //  2. it should contain min. 3 inline links and all links should
 645     //     have the same specified font size
 646     //  3. it should not contain <br> elements
 647     //  4. it should contain only inline elements unless they are containers,
 648     //     children of link elements or children of sub-containers.
 649     int linkCount = 0;
 650     RenderObject* renderer = container->nextInPreOrder(container);
 651     float matchingFontSize = -1;
 652
 653     while (renderer) {
 654         if (!isAutosizingContainer(renderer)) {
 655             if (renderer->isText() && toRenderText(renderer)->text().impl()->stripWhiteSpace()->length() > 3)
 656                 return false;
 657             if (!renderer->isInline())
 658                 return false;
 659             if (renderer->isBR())
 660                 return false;
 661         }
 662         if (renderer->style()->isLink()) {
 663             if (matchingFontSize < 0)
 664                 matchingFontSize = renderer->style()->specifiedFontSize();
 665             else {
 666                 if (matchingFontSize != renderer->style()->specifiedFontSize())
 667                     return false;
 668             }
 669
 670             linkCount++;
 671             // Skip traversing descendants of the link.
 672             renderer = renderer->nextInPreOrderAfterChildren(container);
 673         } else
 674             renderer = nextInPreOrderSkippingDescendantsOfContainers(renderer, container);
 675     }
 676
 677     return (linkCount >= 3);
 678 }
 679
 680 bool TextAutosizer::contentHeightIsConstrained(const RenderBlock* container)
 681 {
 682     // FIXME: Propagate constrainedness down the tree, to avoid inefficiently walking back up from each box.
 683     // FIXME: This code needs to take into account vertical writing modes.
 684     // FIXME: Consider additional heuristics, such as ignoring fixed heights if the content is already overflowing before autosizing kicks in.
 685     for (; container; container = container->containingBlock()) {
 686         RenderStyle* style = container->style();
 687         if (style->overflowY() >= OSCROLL)
 688             return false;
 689         if (style->height().isSpecified() || style->maxHeight().isSpecified() || container->isOutOfFlowPositioned()) {
 690             // Some sites (e.g. wikipedia) set their html and/or body elements to height:100%,
 691             // without intending to constrain the height of the content within them.
 692             return !container->isDocumentElement() && !container->isBody();
 693         }
 694         if (container->isFloating())
 695             return false;
 696     }
 697     return false;
 698 }
 699
 700 bool TextAutosizer::compositeClusterShouldBeAutosized(Vector<TextAutosizingClusterInfo>& clusterInfos, float blockWidth)
 701 {
 702     // Don't autosize clusters that contain less than 4 lines of text (in
 703     // practice less lines are required, since measureDescendantTextWidth
 704     // assumes that characters are 1em wide, but most characters are narrower
 705     // than that, so we're overestimating their contribution to the linecount).
 706     //
 707     // This is to reduce the likelihood of autosizing things like headers and
 708     // footers, which can be quite visually distracting. The rationale is that
 709     // if a cluster contains very few lines of text then it's ok to have to zoom
 710     // in and pan from side to side to read each line, since if there are very
 711     // few lines of text you'll only need to pan across once or twice.
 712     //
 713     // An exception to the 4 lines of text are the textarea and contenteditable
 714     // clusters, which are always autosized by default (i.e. threated as if they
 715     // contain more than 4 lines of text). This is to ensure that the text does
 716     // not suddenly get autosized when the user enters more than 4 lines of text.
 717     float totalTextWidth = 0;
 718     const float minLinesOfText = 4;
 719     float minTextWidth = blockWidth * minLinesOfText;
 720     for (size_t i = 0; i < clusterInfos.size(); ++i) {
 721         if (clusterInfos[i].root->isTextArea() || (clusterInfos[i].root->style() && clusterInfos[i].root->style()->userModify() != READ_ONLY))
 722             return true;
 723         measureDescendantTextWidth(clusterInfos[i].blockContainingAllText, clusterInfos[i], minTextWidth, totalTextWidth);
 724         if (totalTextWidth >= minTextWidth)
 725             return true;
 726     }
 727     return false;
 728 }
 729
 730 void TextAutosizer::measureDescendantTextWidth(const RenderBlock* container, TextAutosizingClusterInfo& clusterInfo, float minTextWidth, float& textWidth)
 731 {
 732     bool skipLocalText = !containerShouldBeAutosized(container);
 733
 734     RenderObject* descendant = nextInPreOrderSkippingDescendantsOfContainers(container, container);
 735     while (descendant) {
 736         if (!skipLocalText && descendant->isText()) {
 737             textWidth += toRenderText(descendant)->renderedTextLength() * descendant->style()->specifiedFontSize();
 738         } else if (isAutosizingContainer(descendant)) {
 739             RenderBlock* descendantBlock = toRenderBlock(descendant);
 740             if (!isAutosizingCluster(descendantBlock, clusterInfo))
 741                 measureDescendantTextWidth(descendantBlock, clusterInfo, minTextWidth, textWidth);
 742         }
 743         if (textWidth >= minTextWidth)
 744             return;
 745         descendant = nextInPreOrderSkippingDescendantsOfContainers(descendant, container);
 746     }
 747 }
 748
 749 RenderObject* TextAutosizer::nextInPreOrderSkippingDescendantsOfContainers(const RenderObject* current, const RenderObject* stayWithin)
 750 {
 751     if (current == stayWithin || !isAutosizingContainer(current))
 752         return current->nextInPreOrder(stayWithin);
 753     return current->nextInPreOrderAfterChildren(stayWithin);
 754 }
 755
 756 const RenderBlock* TextAutosizer::findDeepestBlockContainingAllText(const RenderBlock* cluster)
 757 {
 758     size_t firstDepth = 0;
 759     const RenderObject* firstTextLeaf = findFirstTextLeafNotInCluster(cluster, firstDepth, FirstToLast);
 760     if (!firstTextLeaf)
 761         return cluster;
 762
 763     size_t lastDepth = 0;
 764     const RenderObject* lastTextLeaf = findFirstTextLeafNotInCluster(cluster, lastDepth, LastToFirst);
 765     ASSERT(lastTextLeaf);
 766
 767     // Equalize the depths if necessary. Only one of the while loops below will get executed.
 768     const RenderObject* firstNode = firstTextLeaf;
 769     const RenderObject* lastNode = lastTextLeaf;
 770     while (firstDepth > lastDepth) {
 771         firstNode = firstNode->parent();
 772         --firstDepth;
 773     }
 774     while (lastDepth > firstDepth) {
 775         lastNode = lastNode->parent();
 776         --lastDepth;
 777     }
 778
 779     // Go up from both nodes until the parent is the same. Both pointers will point to the LCA then.
 780     while (firstNode != lastNode) {
 781         firstNode = firstNode->parent();
 782         lastNode = lastNode->parent();
 783     }
 784
 785     if (firstNode->isRenderBlock())
 786         return toRenderBlock(firstNode);
 787
 788     // containingBlock() should never leave the cluster, since it only skips ancestors when finding the
 789     // container of position:absolute/fixed blocks, and those cannot exist between a cluster and its text
 790     // nodes lowest common ancestor as isAutosizingCluster would have made them into their own independent
 791     // cluster.
 792     RenderBlock* containingBlock = firstNode->containingBlock();
 793     ASSERT(containingBlock->isDescendantOf(cluster));
 794
 795     return containingBlock;
 796 }
 797
 798 const RenderObject* TextAutosizer::findFirstTextLeafNotInCluster(const RenderObject* parent, size_t& depth, TraversalDirection direction)
 799 {
 800     if (parent->isText())
 801         return parent;
 802
 803     ++depth;
 804     const RenderObject* child = (direction == FirstToLast) ? parent->firstChild() : parent->lastChild();
 805     while (child) {
 806         if (!isAutosizingContainer(child) || !isIndependentDescendant(toRenderBlock(child))) {
 807             const RenderObject* leaf = findFirstTextLeafNotInCluster(child, depth, direction);
 808             if (leaf)
 809                 return leaf;
 810         }
 811         child = (direction == FirstToLast) ? child->nextSibling() : child->previousSibling();
 812     }
 813     --depth;
 814
 815     return 0;
 816 }
 817
 818 namespace {
 819
 820 // Compares the width of the specified cluster's roots in descending order.
 821 bool clusterWiderThanComparisonFn(const TextAutosizingClusterInfo& first, const TextAutosizingClusterInfo& second)
 822 {
 823     return first.root->contentLogicalWidth() > second.root->contentLogicalWidth();
 824 }
 825
 826 } // namespace
 827
 828 void TextAutosizer::getNarrowDescendantsGroupedByWidth(const TextAutosizingClusterInfo& parentClusterInfo, Vector<Vector<TextAutosizingClusterInfo> >& groups)
 829 {
 830     ASSERT(parentClusterInfo.blockContainingAllText);
 831     ASSERT(groups.isEmpty());
 832
 833     Vector<TextAutosizingClusterInfo> clusterInfos(parentClusterInfo.narrowDescendants);
 834     if (clusterInfos.isEmpty())
 835         return;
 836
 837     std::sort(clusterInfos.begin(), clusterInfos.end(), &clusterWiderThanComparisonFn);
 838     groups.grow(1);
 839
 840     // If the width difference between two consecutive elements of |clusterInfos| is greater than
 841     // this empirically determined value, the next element should start a new group.
 842     const float maxWidthDifferenceWithinGroup = 100;
 843     for (size_t i = 0; i < clusterInfos.size(); ++i) {
 844         groups.last().append(clusterInfos[i]);
 845
 846         if (i + 1 < clusterInfos.size()) {
 847             LayoutUnit currentWidth = clusterInfos[i].root->contentLogicalWidth();
 848             LayoutUnit nextWidth = clusterInfos[i + 1].root->contentLogicalWidth();
 849             if (currentWidth - nextWidth > maxWidthDifferenceWithinGroup)
 850                 groups.grow(groups.size() + 1);
 851         }
 852     }
 853 }
 854
 855 } // namespace WebCore