1 /* 2 * Copyright (C) 2013 Google Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above 11 * copyright notice, this list of conditions and the following disclaimer 12 * in the documentation and/or other materials provided with the 13 * distribution. 14 * * Neither the name of Google Inc. nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 #include "config.h" 32 #include "core/rendering/FastTextAutosizer.h" 33 34 #include "core/dom/Document.h" 35 #include "core/frame/FrameView.h" 36 #include "core/frame/LocalFrame.h" 37 #include "core/frame/Settings.h" 38 #include "core/html/HTMLTextAreaElement.h" 39 #include "core/page/Page.h" 40 #include "core/rendering/InlineIterator.h" 41 #include "core/rendering/RenderBlock.h" 42 #include "core/rendering/RenderListItem.h" 43 #include "core/rendering/RenderListMarker.h" 44 #include "core/rendering/RenderTableCell.h" 45 #include "core/rendering/RenderView.h" 46 47 #ifdef AUTOSIZING_DOM_DEBUG_INFO 48 #include "core/dom/ExecutionContextTask.h" 49 #endif 50 51 using namespace std; 52 53 namespace WebCore { 54 55 #ifdef AUTOSIZING_DOM_DEBUG_INFO 56 class WriteDebugInfoTask : public ExecutionContextTask { 57 public: 58 WriteDebugInfoTask(PassRefPtrWillBeRawPtr<Element> element, AtomicString value) 59 : m_element(element) 60 , m_value(value) 61 { 62 } 63 64 virtual void performTask(ExecutionContext*) 65 { 66 m_element->setAttribute("data-autosizing", m_value, ASSERT_NO_EXCEPTION); 67 } 68 69 private: 70 RefPtrWillBePersistent<Element> m_element; 71 AtomicString m_value; 72 }; 73 74 static void writeDebugInfo(RenderObject* renderer, const AtomicString& output) 75 { 76 Node* node = renderer->node(); 77 if (!node) 78 return; 79 if (node->isDocumentNode()) 80 node = toDocument(node)->documentElement(); 81 if (!node->isElementNode()) 82 return; 83 node->document().postTask(adoptPtr(new WriteDebugInfoTask(toElement(node), output))); 84 } 85 86 void FastTextAutosizer::writeClusterDebugInfo(Cluster* cluster) 87 { 88 String explanation = ""; 89 if (cluster->m_flags & SUPPRESSING) { 90 explanation = "[suppressed]"; 91 } else if (!(cluster->m_flags & (INDEPENDENT | WIDER_OR_NARROWER))) { 92 explanation = "[inherited]"; 93 } else if (cluster->m_supercluster) { 94 explanation = "[supercluster]"; 95 } else if (!clusterHasEnoughTextToAutosize(cluster)) { 96 explanation = "[insufficient-text]"; 97 } else { 98 const RenderBlock* widthProvider = clusterWidthProvider(cluster->m_root); 99 if (cluster->m_hasTableAncestor && cluster->m_multiplier < multiplierFromBlock(widthProvider)) { 100 explanation = "[table-ancestor-limited]"; 101 } else { 102 explanation = String::format("[from width %d of %s]", 103 static_cast<int>(widthFromBlock(widthProvider)), widthProvider->debugName().utf8().data()); 104 } 105 } 106 String pageInfo = ""; 107 if (cluster->m_root->isRenderView()) { 108 pageInfo = String::format("; pageinfo: bm %f * (lw %d / fw %d)", 109 m_pageInfo.m_baseMultiplier, m_pageInfo.m_layoutWidth, m_pageInfo.m_frameWidth); 110 } 111 float multiplier = cluster->m_flags & SUPPRESSING ? 1.0 : cluster->m_multiplier; 112 writeDebugInfo(const_cast<RenderBlock*>(cluster->m_root), 113 AtomicString(String::format("cluster: %f %s%s", multiplier, 114 explanation.utf8().data(), pageInfo.utf8().data()))); 115 } 116 #endif 117 118 static const RenderObject* parentElementRenderer(const RenderObject* renderer) 119 { 120 // At style recalc, the renderer's parent may not be attached, 121 // so we need to obtain this from the DOM tree. 122 const Node* node = renderer->node(); 123 if (!node) 124 return 0; 125 126 while ((node = node->parentNode())) { 127 if (node->isElementNode()) 128 return node->renderer(); 129 } 130 return 0; 131 } 132 133 static bool isNonTextAreaFormControl(const RenderObject* renderer) 134 { 135 const Node* node = renderer ? renderer->node() : 0; 136 if (!node || !node->isElementNode()) 137 return false; 138 const Element* element = toElement(node); 139 140 return (element->isFormControlElement() && !isHTMLTextAreaElement(element)); 141 } 142 143 static bool isPotentialClusterRoot(const RenderObject* renderer) 144 { 145 // "Potential cluster roots" are the smallest unit for which we can 146 // enable/disable text autosizing. 147 // - Must not be inline, as different multipliers on one line looks terrible. 148 // Exceptions are inline-block and alike elements (inline-table, -webkit-inline-*), 149 // as they often contain entire multi-line columns of text. 150 // - Must not be normal list items, as items in the same list should look 151 // consistent, unless they are floating or position:absolute/fixed. 152 Node* node = renderer->generatingNode(); 153 if (node && !node->hasChildren()) 154 return false; 155 if (!renderer->isRenderBlock()) 156 return false; 157 if (renderer->isInline() && !renderer->style()->isDisplayReplacedType()) 158 return false; 159 if (renderer->isListItem()) 160 return (renderer->isFloating() || renderer->isOutOfFlowPositioned()); 161 162 return true; 163 } 164 165 static bool isIndependentDescendant(const RenderBlock* renderer) 166 { 167 ASSERT(isPotentialClusterRoot(renderer)); 168 169 RenderBlock* containingBlock = renderer->containingBlock(); 170 return renderer->isRenderView() 171 || renderer->isFloating() 172 || renderer->isOutOfFlowPositioned() 173 || renderer->isTableCell() 174 || renderer->isTableCaption() 175 || renderer->isFlexibleBoxIncludingDeprecated() 176 || renderer->hasColumns() 177 || (containingBlock && containingBlock->isHorizontalWritingMode() != renderer->isHorizontalWritingMode()) 178 || renderer->style()->isDisplayReplacedType() 179 || renderer->isTextArea() 180 || renderer->style()->userModify() != READ_ONLY; 181 } 182 183 static bool blockIsRowOfLinks(const RenderBlock* block) 184 { 185 // A "row of links" is a block for which: 186 // 1. It does not contain non-link text elements longer than 3 characters 187 // 2. It contains a minimum of 3 inline links and all links should 188 // have the same specified font size. 189 // 3. It should not contain <br> elements. 190 // 4. It should contain only inline elements unless they are containers, 191 // children of link elements or children of sub-containers. 192 int linkCount = 0; 193 RenderObject* renderer = block->firstChild(); 194 float matchingFontSize = -1; 195 196 while (renderer) { 197 if (!isPotentialClusterRoot(renderer)) { 198 if (renderer->isText() && toRenderText(renderer)->text().impl()->stripWhiteSpace()->length() > 3) 199 return false; 200 if (!renderer->isInline() || renderer->isBR()) 201 return false; 202 } 203 if (renderer->style()->isLink()) { 204 linkCount++; 205 if (matchingFontSize < 0) 206 matchingFontSize = renderer->style()->specifiedFontSize(); 207 else if (matchingFontSize != renderer->style()->specifiedFontSize()) 208 return false; 209 210 // Skip traversing descendants of the link. 211 renderer = renderer->nextInPreOrderAfterChildren(block); 212 continue; 213 } 214 renderer = renderer->nextInPreOrder(block); 215 } 216 217 return (linkCount >= 3); 218 } 219 220 static bool blockHeightConstrained(const RenderBlock* block) 221 { 222 // FIXME: Propagate constrainedness down the tree, to avoid inefficiently walking back up from each box. 223 // FIXME: This code needs to take into account vertical writing modes. 224 // FIXME: Consider additional heuristics, such as ignoring fixed heights if the content is already overflowing before autosizing kicks in. 225 for (; block; block = block->containingBlock()) { 226 RenderStyle* style = block->style(); 227 if (style->overflowY() >= OSCROLL) 228 return false; 229 if (style->height().isSpecified() || style->maxHeight().isSpecified() || block->isOutOfFlowPositioned()) { 230 // Some sites (e.g. wikipedia) set their html and/or body elements to height:100%, 231 // without intending to constrain the height of the content within them. 232 return !block->isDocumentElement() && !block->isBody(); 233 } 234 if (block->isFloating()) 235 return false; 236 } 237 return false; 238 } 239 240 static bool blockOrImmediateChildrenAreFormControls(const RenderBlock* block) 241 { 242 if (isNonTextAreaFormControl(block)) 243 return true; 244 const RenderObject* renderer = block->firstChild(); 245 while (renderer) { 246 if (isNonTextAreaFormControl(renderer)) 247 return true; 248 renderer = renderer->nextSibling(); 249 } 250 251 return false; 252 } 253 254 // Some blocks are not autosized even if their parent cluster wants them to. 255 static bool blockSuppressesAutosizing(const RenderBlock* block) 256 { 257 if (blockOrImmediateChildrenAreFormControls(block)) 258 return true; 259 260 if (blockIsRowOfLinks(block)) 261 return true; 262 263 // Don't autosize block-level text that can't wrap (as it's likely to 264 // expand sideways and break the page's layout). 265 if (!block->style()->autoWrap()) 266 return true; 267 268 if (blockHeightConstrained(block)) 269 return true; 270 271 return false; 272 } 273 274 static bool hasExplicitWidth(const RenderBlock* block) 275 { 276 // FIXME: This heuristic may need to be expanded to other ways a block can be wider or narrower 277 // than its parent containing block. 278 return block->style() && block->style()->width().isSpecified(); 279 } 280 281 FastTextAutosizer::FastTextAutosizer(const Document* document) 282 : m_document(document) 283 , m_firstBlockToBeginLayout(0) 284 #ifndef NDEBUG 285 , m_blocksThatHaveBegunLayout() 286 #endif 287 , m_superclusters() 288 , m_clusterStack() 289 , m_fingerprintMapper() 290 , m_pageInfo() 291 , m_updatePageInfoDeferred(false) 292 { 293 } 294 295 void FastTextAutosizer::record(const RenderBlock* block) 296 { 297 if (!m_pageInfo.m_settingEnabled) 298 return; 299 300 ASSERT(!m_blocksThatHaveBegunLayout.contains(block)); 301 302 if (!classifyBlock(block, INDEPENDENT | EXPLICIT_WIDTH)) 303 return; 304 305 if (Fingerprint fingerprint = computeFingerprint(block)) 306 m_fingerprintMapper.addTentativeClusterRoot(block, fingerprint); 307 } 308 309 void FastTextAutosizer::destroy(const RenderBlock* block) 310 { 311 if (!m_pageInfo.m_settingEnabled) 312 return; 313 314 ASSERT(!m_blocksThatHaveBegunLayout.contains(block)); 315 316 if (m_fingerprintMapper.remove(block) && m_firstBlockToBeginLayout) { 317 // RenderBlock with a fingerprint was destroyed during layout. 318 // Clear the cluster stack and the supercluster map to avoid stale pointers. 319 // Speculative fix for http://crbug.com/369485. 320 m_firstBlockToBeginLayout = 0; 321 m_clusterStack.clear(); 322 m_superclusters.clear(); 323 } 324 } 325 326 FastTextAutosizer::BeginLayoutBehavior FastTextAutosizer::prepareForLayout(const RenderBlock* block) 327 { 328 #ifndef NDEBUG 329 m_blocksThatHaveBegunLayout.add(block); 330 #endif 331 332 if (!m_firstBlockToBeginLayout) { 333 m_firstBlockToBeginLayout = block; 334 prepareClusterStack(block->parent()); 335 } else if (block == currentCluster()->m_root) { 336 // Ignore beginLayout on the same block twice. 337 // This can happen with paginated overflow. 338 return StopLayout; 339 } 340 341 return ContinueLayout; 342 } 343 344 void FastTextAutosizer::prepareClusterStack(const RenderObject* renderer) 345 { 346 if (!renderer) 347 return; 348 prepareClusterStack(renderer->parent()); 349 350 if (renderer->isRenderBlock()) { 351 const RenderBlock* block = toRenderBlock(renderer); 352 #ifndef NDEBUG 353 m_blocksThatHaveBegunLayout.add(block); 354 #endif 355 if (Cluster* cluster = maybeCreateCluster(block)) 356 m_clusterStack.append(adoptPtr(cluster)); 357 } 358 } 359 360 void FastTextAutosizer::beginLayout(RenderBlock* block) 361 { 362 ASSERT(shouldHandleLayout()); 363 364 if (prepareForLayout(block) == StopLayout) 365 return; 366 367 if (Cluster* cluster = maybeCreateCluster(block)) 368 m_clusterStack.append(adoptPtr(cluster)); 369 370 // Cells in auto-layout tables are handled separately by inflateAutoTable. 371 bool isAutoTableCell = block->isTableCell() && !toRenderTableCell(block)->table()->style()->isFixedTableLayout(); 372 if (!isAutoTableCell && !m_clusterStack.isEmpty()) 373 inflate(block); 374 } 375 376 void FastTextAutosizer::inflateListItem(RenderListItem* listItem, RenderListMarker* listItemMarker) 377 { 378 if (!shouldHandleLayout()) 379 return; 380 ASSERT(listItem && listItemMarker); 381 382 if (prepareForLayout(listItem) == StopLayout) 383 return; 384 385 // Force the LI to be inside the DBCAT when computing the multiplier. 386 // This guarantees that the DBCAT has entered layout, so we can ask for its width. 387 // It also makes sense because the list marker is autosized like a text node. 388 float multiplier = clusterMultiplier(currentCluster()); 389 390 applyMultiplier(listItem, multiplier); 391 applyMultiplier(listItemMarker, multiplier); 392 } 393 394 void FastTextAutosizer::inflateAutoTable(RenderTable* table) 395 { 396 ASSERT(table); 397 ASSERT(!table->style()->isFixedTableLayout()); 398 ASSERT(table->containingBlock()); 399 400 Cluster* cluster = currentCluster(); 401 if (cluster->m_root != table) 402 return; 403 404 // Pre-inflate cells that have enough text so that their inflated preferred widths will be used 405 // for column sizing. 406 for (RenderObject* section = table->firstChild(); section; section = section->nextSibling()) { 407 if (!section->isTableSection()) 408 continue; 409 for (RenderTableRow* row = toRenderTableSection(section)->firstRow(); row; row = row->nextRow()) { 410 for (RenderTableCell* cell = row->firstCell(); cell; cell = cell->nextCell()) { 411 if (!cell->needsLayout()) 412 continue; 413 414 beginLayout(cell); 415 inflate(cell, DescendToInnerBlocks); 416 endLayout(cell); 417 } 418 } 419 } 420 } 421 422 void FastTextAutosizer::endLayout(RenderBlock* block) 423 { 424 ASSERT(shouldHandleLayout()); 425 426 if (block == m_firstBlockToBeginLayout) { 427 m_firstBlockToBeginLayout = 0; 428 m_clusterStack.clear(); 429 m_superclusters.clear(); 430 m_stylesRetainedDuringLayout.clear(); 431 #ifndef NDEBUG 432 m_blocksThatHaveBegunLayout.clear(); 433 #endif 434 // Tables can create two layout scopes for the same block so the isEmpty 435 // check below is needed to guard against endLayout being called twice. 436 } else if (!m_clusterStack.isEmpty() && currentCluster()->m_root == block) { 437 m_clusterStack.removeLast(); 438 } 439 } 440 441 float FastTextAutosizer::inflate(RenderObject* parent, InflateBehavior behavior, float multiplier) 442 { 443 Cluster* cluster = currentCluster(); 444 bool hasTextChild = false; 445 446 RenderObject* child = 0; 447 if (parent->isRenderBlock() && (parent->childrenInline() || behavior == DescendToInnerBlocks)) 448 child = toRenderBlock(parent)->firstChild(); 449 else if (parent->isRenderInline()) 450 child = toRenderInline(parent)->firstChild(); 451 452 while (child) { 453 if (child->isText()) { 454 hasTextChild = true; 455 // We only calculate this multiplier on-demand to ensure the parent block of this text 456 // has entered layout. 457 if (!multiplier) 458 multiplier = cluster->m_flags & SUPPRESSING ? 1.0f : clusterMultiplier(cluster); 459 applyMultiplier(child, multiplier); 460 // FIXME: Investigate why MarkOnlyThis is sufficient. 461 if (parent->isRenderInline()) 462 child->setPreferredLogicalWidthsDirty(MarkOnlyThis); 463 } else if (child->isRenderInline()) { 464 multiplier = inflate(child, behavior, multiplier); 465 } else if (child->isRenderBlock() && behavior == DescendToInnerBlocks 466 && !classifyBlock(child, INDEPENDENT | EXPLICIT_WIDTH | SUPPRESSING)) { 467 multiplier = inflate(child, behavior, multiplier); 468 } 469 child = child->nextSibling(); 470 } 471 472 if (hasTextChild) { 473 applyMultiplier(parent, multiplier); // Parent handles line spacing. 474 } else if (!parent->isListItem()) { 475 // For consistency, a block with no immediate text child should always have a 476 // multiplier of 1 (except for list items which are handled in inflateListItem). 477 applyMultiplier(parent, 1); 478 } 479 return multiplier; 480 } 481 482 bool FastTextAutosizer::shouldHandleLayout() const 483 { 484 return m_pageInfo.m_settingEnabled && m_pageInfo.m_pageNeedsAutosizing && !m_updatePageInfoDeferred; 485 } 486 487 void FastTextAutosizer::updatePageInfoInAllFrames() 488 { 489 ASSERT(!m_document->frame() || m_document->frame()->isMainFrame()); 490 491 for (Frame* frame = m_document->frame(); frame; frame = frame->tree().traverseNext()) { 492 if (!frame->isLocalFrame()) 493 continue; 494 if (FastTextAutosizer* textAutosizer = toLocalFrame(frame)->document()->fastTextAutosizer()) 495 textAutosizer->updatePageInfo(); 496 } 497 } 498 499 void FastTextAutosizer::updatePageInfo() 500 { 501 if (m_updatePageInfoDeferred || !m_document->page() || !m_document->settings()) 502 return; 503 504 PageInfo previousPageInfo(m_pageInfo); 505 m_pageInfo.m_settingEnabled = m_document->settings()->textAutosizingEnabled(); 506 507 if (!m_pageInfo.m_settingEnabled || m_document->printing()) { 508 m_pageInfo.m_pageNeedsAutosizing = false; 509 } else { 510 RenderView* renderView = m_document->renderView(); 511 bool horizontalWritingMode = isHorizontalWritingMode(renderView->style()->writingMode()); 512 513 LocalFrame* mainFrame = m_document->page()->deprecatedLocalMainFrame(); 514 IntSize frameSize = m_document->settings()->textAutosizingWindowSizeOverride(); 515 if (frameSize.isEmpty()) 516 frameSize = mainFrame->view()->unscaledVisibleContentSize(IncludeScrollbars); 517 m_pageInfo.m_frameWidth = horizontalWritingMode ? frameSize.width() : frameSize.height(); 518 519 IntSize layoutSize = mainFrame->view()->layoutSize(); 520 m_pageInfo.m_layoutWidth = horizontalWritingMode ? layoutSize.width() : layoutSize.height(); 521 522 // Compute the base font scale multiplier based on device and accessibility settings. 523 m_pageInfo.m_baseMultiplier = m_document->settings()->accessibilityFontScaleFactor(); 524 // If the page has a meta viewport or @viewport, don't apply the device scale adjustment. 525 const ViewportDescription& viewportDescription = mainFrame->document()->viewportDescription(); 526 if (!viewportDescription.isSpecifiedByAuthor()) { 527 float deviceScaleAdjustment = m_document->settings()->deviceScaleAdjustment(); 528 m_pageInfo.m_baseMultiplier *= deviceScaleAdjustment; 529 } 530 531 m_pageInfo.m_pageNeedsAutosizing = !!m_pageInfo.m_frameWidth 532 && (m_pageInfo.m_baseMultiplier * (static_cast<float>(m_pageInfo.m_layoutWidth) / m_pageInfo.m_frameWidth) > 1.0f); 533 } 534 535 if (m_pageInfo.m_pageNeedsAutosizing) { 536 // If page info has changed, multipliers may have changed. Force a layout to recompute them. 537 if (m_pageInfo.m_frameWidth != previousPageInfo.m_frameWidth 538 || m_pageInfo.m_layoutWidth != previousPageInfo.m_layoutWidth 539 || m_pageInfo.m_baseMultiplier != previousPageInfo.m_baseMultiplier 540 || m_pageInfo.m_settingEnabled != previousPageInfo.m_settingEnabled) 541 setAllTextNeedsLayout(); 542 } else if (previousPageInfo.m_hasAutosized) { 543 // If we are no longer autosizing the page, we won't do anything during the next layout. 544 // Set all the multipliers back to 1 now. 545 resetMultipliers(); 546 m_pageInfo.m_hasAutosized = false; 547 } 548 } 549 550 void FastTextAutosizer::resetMultipliers() 551 { 552 RenderObject* renderer = m_document->renderView(); 553 while (renderer) { 554 if (RenderStyle* style = renderer->style()) { 555 if (style->textAutosizingMultiplier() != 1) 556 applyMultiplier(renderer, 1, LayoutNeeded); 557 } 558 renderer = renderer->nextInPreOrder(); 559 } 560 } 561 562 void FastTextAutosizer::setAllTextNeedsLayout() 563 { 564 RenderObject* renderer = m_document->renderView(); 565 while (renderer) { 566 if (renderer->isText()) 567 renderer->setNeedsLayoutAndFullPaintInvalidation(); 568 renderer = renderer->nextInPreOrder(); 569 } 570 } 571 572 FastTextAutosizer::BlockFlags FastTextAutosizer::classifyBlock(const RenderObject* renderer, BlockFlags mask) 573 { 574 if (!renderer->isRenderBlock()) 575 return 0; 576 577 const RenderBlock* block = toRenderBlock(renderer); 578 BlockFlags flags = 0; 579 580 if (isPotentialClusterRoot(block)) { 581 if (mask & POTENTIAL_ROOT) 582 flags |= POTENTIAL_ROOT; 583 584 if ((mask & INDEPENDENT) && (isIndependentDescendant(block) || block->isTable())) 585 flags |= INDEPENDENT; 586 587 if ((mask & EXPLICIT_WIDTH) && hasExplicitWidth(block)) 588 flags |= EXPLICIT_WIDTH; 589 590 if ((mask & SUPPRESSING) && blockSuppressesAutosizing(block)) 591 flags |= SUPPRESSING; 592 } 593 return flags; 594 } 595 596 bool FastTextAutosizer::clusterWouldHaveEnoughTextToAutosize(const RenderBlock* root, const RenderBlock* widthProvider) 597 { 598 Cluster hypotheticalCluster(root, classifyBlock(root), 0); 599 return clusterHasEnoughTextToAutosize(&hypotheticalCluster, widthProvider); 600 } 601 602 bool FastTextAutosizer::clusterHasEnoughTextToAutosize(Cluster* cluster, const RenderBlock* widthProvider) 603 { 604 if (cluster->m_hasEnoughTextToAutosize != UnknownAmountOfText) 605 return cluster->m_hasEnoughTextToAutosize == HasEnoughText; 606 607 const RenderBlock* root = cluster->m_root; 608 if (!widthProvider) 609 widthProvider = clusterWidthProvider(root); 610 611 // TextAreas and user-modifiable areas get a free pass to autosize regardless of text content. 612 if (root->isTextArea() || (root->style() && root->style()->userModify() != READ_ONLY)) { 613 cluster->m_hasEnoughTextToAutosize = HasEnoughText; 614 return true; 615 } 616 617 if (cluster->m_flags & SUPPRESSING) { 618 cluster->m_hasEnoughTextToAutosize = NotEnoughText; 619 return false; 620 } 621 622 // 4 lines of text is considered enough to autosize. 623 float minimumTextLengthToAutosize = widthFromBlock(widthProvider) * 4; 624 625 float length = 0; 626 RenderObject* descendant = root->firstChild(); 627 while (descendant) { 628 if (descendant->isRenderBlock()) { 629 if (classifyBlock(descendant, INDEPENDENT | SUPPRESSING)) { 630 descendant = descendant->nextInPreOrderAfterChildren(root); 631 continue; 632 } 633 } else if (descendant->isText()) { 634 // Note: Using text().stripWhiteSpace().length() instead of renderedTextLength() because 635 // the lineboxes will not be built until layout. These values can be different. 636 // Note: This is an approximation assuming each character is 1em wide. 637 length += toRenderText(descendant)->text().stripWhiteSpace().length() * descendant->style()->specifiedFontSize(); 638 639 if (length >= minimumTextLengthToAutosize) { 640 cluster->m_hasEnoughTextToAutosize = HasEnoughText; 641 return true; 642 } 643 } 644 descendant = descendant->nextInPreOrder(root); 645 } 646 647 cluster->m_hasEnoughTextToAutosize = NotEnoughText; 648 return false; 649 } 650 651 FastTextAutosizer::Fingerprint FastTextAutosizer::getFingerprint(const RenderObject* renderer) 652 { 653 Fingerprint result = m_fingerprintMapper.get(renderer); 654 if (!result) { 655 result = computeFingerprint(renderer); 656 m_fingerprintMapper.add(renderer, result); 657 } 658 return result; 659 } 660 661 FastTextAutosizer::Fingerprint FastTextAutosizer::computeFingerprint(const RenderObject* renderer) 662 { 663 Node* node = renderer->generatingNode(); 664 if (!node || !node->isElementNode()) 665 return 0; 666 667 FingerprintSourceData data; 668 if (const RenderObject* parent = parentElementRenderer(renderer)) 669 data.m_parentHash = getFingerprint(parent); 670 671 data.m_qualifiedNameHash = QualifiedNameHash::hash(toElement(node)->tagQName()); 672 673 if (RenderStyle* style = renderer->style()) { 674 data.m_packedStyleProperties = style->direction(); 675 data.m_packedStyleProperties |= (style->position() << 1); 676 data.m_packedStyleProperties |= (style->floating() << 4); 677 data.m_packedStyleProperties |= (style->display() << 6); 678 data.m_packedStyleProperties |= (style->width().type() << 11); 679 // packedStyleProperties effectively using 15 bits now. 680 681 // consider for adding: writing mode, padding. 682 683 data.m_width = style->width().getFloatValue(); 684 } 685 686 // Use nodeIndex as a rough approximation of column number 687 // (it's too early to call RenderTableCell::col). 688 // FIXME: account for colspan 689 if (renderer->isTableCell()) 690 data.m_column = renderer->node()->nodeIndex(); 691 692 return StringHasher::computeHash<UChar>( 693 static_cast<const UChar*>(static_cast<const void*>(&data)), 694 sizeof data / sizeof(UChar)); 695 } 696 697 FastTextAutosizer::Cluster* FastTextAutosizer::maybeCreateCluster(const RenderBlock* block) 698 { 699 BlockFlags flags = classifyBlock(block); 700 if (!(flags & POTENTIAL_ROOT)) 701 return 0; 702 703 Cluster* parentCluster = m_clusterStack.isEmpty() ? 0 : currentCluster(); 704 ASSERT(parentCluster || block->isRenderView()); 705 706 // If a non-independent block would not alter the SUPPRESSING flag, it doesn't need to be a cluster. 707 bool parentSuppresses = parentCluster && (parentCluster->m_flags & SUPPRESSING); 708 if (!(flags & INDEPENDENT) && !(flags & EXPLICIT_WIDTH) && !!(flags & SUPPRESSING) == parentSuppresses) 709 return 0; 710 711 Cluster* cluster = new Cluster(block, flags, parentCluster, getSupercluster(block)); 712 #ifdef AUTOSIZING_DOM_DEBUG_INFO 713 // Non-SUPPRESSING clusters are annotated in clusterMultiplier. 714 if (flags & SUPPRESSING) 715 writeClusterDebugInfo(cluster); 716 #endif 717 return cluster; 718 } 719 720 FastTextAutosizer::Supercluster* FastTextAutosizer::getSupercluster(const RenderBlock* block) 721 { 722 Fingerprint fingerprint = m_fingerprintMapper.get(block); 723 if (!fingerprint) 724 return 0; 725 726 BlockSet* roots = &m_fingerprintMapper.getTentativeClusterRoots(fingerprint); 727 if (!roots || roots->size() < 2 || !roots->contains(block)) 728 return 0; 729 730 SuperclusterMap::AddResult addResult = m_superclusters.add(fingerprint, PassOwnPtr<Supercluster>()); 731 if (!addResult.isNewEntry) 732 return addResult.storedValue->value.get(); 733 734 Supercluster* supercluster = new Supercluster(roots); 735 addResult.storedValue->value = adoptPtr(supercluster); 736 return supercluster; 737 } 738 739 float FastTextAutosizer::clusterMultiplier(Cluster* cluster) 740 { 741 if (cluster->m_multiplier) 742 return cluster->m_multiplier; 743 744 // FIXME: why does isWiderOrNarrowerDescendant crash on independent clusters? 745 if (!(cluster->m_flags & INDEPENDENT) && isWiderOrNarrowerDescendant(cluster)) 746 cluster->m_flags |= WIDER_OR_NARROWER; 747 748 if (cluster->m_flags & (INDEPENDENT | WIDER_OR_NARROWER)) { 749 if (cluster->m_supercluster) 750 cluster->m_multiplier = superclusterMultiplier(cluster); 751 else if (clusterHasEnoughTextToAutosize(cluster)) 752 cluster->m_multiplier = multiplierFromBlock(clusterWidthProvider(cluster->m_root)); 753 else 754 cluster->m_multiplier = 1.0f; 755 } else { 756 cluster->m_multiplier = cluster->m_parent ? clusterMultiplier(cluster->m_parent) : 1.0f; 757 } 758 759 #ifdef AUTOSIZING_DOM_DEBUG_INFO 760 writeClusterDebugInfo(cluster); 761 #endif 762 763 ASSERT(cluster->m_multiplier); 764 return cluster->m_multiplier; 765 } 766 767 bool FastTextAutosizer::superclusterHasEnoughTextToAutosize(Supercluster* supercluster, const RenderBlock* widthProvider) 768 { 769 if (supercluster->m_hasEnoughTextToAutosize != UnknownAmountOfText) 770 return supercluster->m_hasEnoughTextToAutosize == HasEnoughText; 771 772 BlockSet::iterator end = supercluster->m_roots->end(); 773 for (BlockSet::iterator it = supercluster->m_roots->begin(); it != end; ++it) { 774 if (clusterWouldHaveEnoughTextToAutosize(*it, widthProvider)) { 775 supercluster->m_hasEnoughTextToAutosize = HasEnoughText; 776 return true; 777 } 778 } 779 supercluster->m_hasEnoughTextToAutosize = NotEnoughText; 780 return false; 781 } 782 783 float FastTextAutosizer::superclusterMultiplier(Cluster* cluster) 784 { 785 Supercluster* supercluster = cluster->m_supercluster; 786 if (!supercluster->m_multiplier) { 787 const RenderBlock* widthProvider = maxClusterWidthProvider(cluster->m_supercluster, cluster->m_root); 788 supercluster->m_multiplier = superclusterHasEnoughTextToAutosize(supercluster, widthProvider) 789 ? multiplierFromBlock(widthProvider) : 1.0f; 790 } 791 ASSERT(supercluster->m_multiplier); 792 return supercluster->m_multiplier; 793 } 794 795 const RenderBlock* FastTextAutosizer::clusterWidthProvider(const RenderBlock* root) 796 { 797 if (root->isTable() || root->isTableCell()) 798 return root; 799 800 return deepestBlockContainingAllText(root); 801 } 802 803 const RenderBlock* FastTextAutosizer::maxClusterWidthProvider(const Supercluster* supercluster, const RenderBlock* currentRoot) 804 { 805 const RenderBlock* result = clusterWidthProvider(currentRoot); 806 float maxWidth = widthFromBlock(result); 807 808 const BlockSet* roots = supercluster->m_roots; 809 for (BlockSet::iterator it = roots->begin(); it != roots->end(); ++it) { 810 const RenderBlock* widthProvider = clusterWidthProvider(*it); 811 if (widthProvider->needsLayout()) 812 continue; 813 float width = widthFromBlock(widthProvider); 814 if (width > maxWidth) { 815 maxWidth = width; 816 result = widthProvider; 817 } 818 } 819 RELEASE_ASSERT(result); 820 return result; 821 } 822 823 float FastTextAutosizer::widthFromBlock(const RenderBlock* block) 824 { 825 RELEASE_ASSERT(block); 826 RELEASE_ASSERT(block->style()); 827 828 if (!(block->isTable() || block->isTableCell() || block->isListItem())) 829 return block->contentLogicalWidth().toFloat(); 830 831 if (!block->containingBlock()) 832 return 0; 833 834 // Tables may be inflated before computing their preferred widths. Try several methods to 835 // obtain a width, and fall back on a containing block's width. 836 do { 837 float width; 838 Length specifiedWidth = block->isTableCell() 839 ? toRenderTableCell(block)->styleOrColLogicalWidth() : block->style()->logicalWidth(); 840 if (specifiedWidth.isFixed()) { 841 if ((width = specifiedWidth.value()) > 0) 842 return width; 843 } 844 if (specifiedWidth.isPercent()) { 845 if (float containerWidth = block->containingBlock()->contentLogicalWidth().toFloat()) { 846 if ((width = floatValueForLength(specifiedWidth, containerWidth)) > 0) 847 return width; 848 } 849 } 850 if ((width = block->contentLogicalWidth().toFloat()) > 0) 851 return width; 852 } while ((block = block->containingBlock())); 853 return 0; 854 } 855 856 float FastTextAutosizer::multiplierFromBlock(const RenderBlock* block) 857 { 858 // If block->needsLayout() is false, it does not need to be in m_blocksThatHaveBegunLayout. 859 // This can happen during layout of a positioned object if the cluster's DBCAT is deeper 860 // than the positioned object's containing block, and wasn't marked as needing layout. 861 ASSERT(m_blocksThatHaveBegunLayout.contains(block) || !block->needsLayout()); 862 863 // Block width, in CSS pixels. 864 float blockWidth = widthFromBlock(block); 865 float multiplier = m_pageInfo.m_frameWidth ? min(blockWidth, static_cast<float>(m_pageInfo.m_layoutWidth)) / m_pageInfo.m_frameWidth : 1.0f; 866 867 return max(m_pageInfo.m_baseMultiplier * multiplier, 1.0f); 868 } 869 870 const RenderBlock* FastTextAutosizer::deepestBlockContainingAllText(Cluster* cluster) 871 { 872 if (!cluster->m_deepestBlockContainingAllText) 873 cluster->m_deepestBlockContainingAllText = deepestBlockContainingAllText(cluster->m_root); 874 875 return cluster->m_deepestBlockContainingAllText; 876 } 877 878 // FIXME: Refactor this to look more like FastTextAutosizer::deepestCommonAncestor. This is copied 879 // from TextAutosizer::findDeepestBlockContainingAllText. 880 const RenderBlock* FastTextAutosizer::deepestBlockContainingAllText(const RenderBlock* root) 881 { 882 size_t firstDepth = 0; 883 const RenderObject* firstTextLeaf = findTextLeaf(root, firstDepth, First); 884 if (!firstTextLeaf) 885 return root; 886 887 size_t lastDepth = 0; 888 const RenderObject* lastTextLeaf = findTextLeaf(root, lastDepth, Last); 889 ASSERT(lastTextLeaf); 890 891 // Equalize the depths if necessary. Only one of the while loops below will get executed. 892 const RenderObject* firstNode = firstTextLeaf; 893 const RenderObject* lastNode = lastTextLeaf; 894 while (firstDepth > lastDepth) { 895 firstNode = firstNode->parent(); 896 --firstDepth; 897 } 898 while (lastDepth > firstDepth) { 899 lastNode = lastNode->parent(); 900 --lastDepth; 901 } 902 903 // Go up from both nodes until the parent is the same. Both pointers will point to the LCA then. 904 while (firstNode != lastNode) { 905 firstNode = firstNode->parent(); 906 lastNode = lastNode->parent(); 907 } 908 909 if (firstNode->isRenderBlock()) 910 return toRenderBlock(firstNode); 911 912 // containingBlock() should never leave the cluster, since it only skips ancestors when finding 913 // the container of position:absolute/fixed blocks, and those cannot exist between a cluster and 914 // its text node's lowest common ancestor as isAutosizingCluster would have made them into their 915 // own independent cluster. 916 const RenderBlock* containingBlock = firstNode->containingBlock(); 917 if (!containingBlock) 918 return root; 919 920 ASSERT(containingBlock->isDescendantOf(root)); 921 return containingBlock; 922 } 923 924 const RenderObject* FastTextAutosizer::findTextLeaf(const RenderObject* parent, size_t& depth, TextLeafSearch firstOrLast) 925 { 926 // List items are treated as text due to the marker. 927 // The actual renderer for the marker (RenderListMarker) may not be in the tree yet since it is added during layout. 928 if (parent->isListItem()) 929 return parent; 930 931 if (parent->isText()) 932 return parent; 933 934 ++depth; 935 const RenderObject* child = (firstOrLast == First) ? parent->slowFirstChild() : parent->slowLastChild(); 936 while (child) { 937 // Note: At this point clusters may not have been created for these blocks so we cannot rely 938 // on m_clusters. Instead, we use a best-guess about whether the block will become a cluster. 939 if (!classifyBlock(child, INDEPENDENT)) { 940 if (const RenderObject* leaf = findTextLeaf(child, depth, firstOrLast)) 941 return leaf; 942 } 943 child = (firstOrLast == First) ? child->nextSibling() : child->previousSibling(); 944 } 945 --depth; 946 947 return 0; 948 } 949 950 void FastTextAutosizer::applyMultiplier(RenderObject* renderer, float multiplier, RelayoutBehavior relayoutBehavior) 951 { 952 ASSERT(renderer && renderer->style()); 953 RenderStyle* currentStyle = renderer->style(); 954 if (currentStyle->textAutosizingMultiplier() == multiplier) 955 return; 956 957 // We need to clone the render style to avoid breaking style sharing. 958 RefPtr<RenderStyle> style = RenderStyle::clone(currentStyle); 959 style->setTextAutosizingMultiplier(multiplier); 960 style->setUnique(); 961 962 switch (relayoutBehavior) { 963 case AlreadyInLayout: 964 // Don't free currentStyle until the end of the layout pass. This allows other parts of the system 965 // to safely hold raw RenderStyle* pointers during layout, e.g. BreakingContext::m_currentStyle. 966 m_stylesRetainedDuringLayout.append(currentStyle); 967 968 renderer->setStyleInternal(style.release()); 969 renderer->setNeedsLayoutAndFullPaintInvalidation(); 970 break; 971 972 case LayoutNeeded: 973 renderer->setStyle(style.release()); 974 break; 975 } 976 977 if (multiplier != 1) 978 m_pageInfo.m_hasAutosized = true; 979 } 980 981 bool FastTextAutosizer::isWiderOrNarrowerDescendant(Cluster* cluster) 982 { 983 // FIXME: Why do we return true when hasExplicitWidth returns false?? 984 if (!cluster->m_parent || !hasExplicitWidth(cluster->m_root)) 985 return true; 986 987 const RenderBlock* parentDeepestBlockContainingAllText = deepestBlockContainingAllText(cluster->m_parent); 988 ASSERT(m_blocksThatHaveBegunLayout.contains(cluster->m_root)); 989 ASSERT(m_blocksThatHaveBegunLayout.contains(parentDeepestBlockContainingAllText)); 990 991 float contentWidth = cluster->m_root->contentLogicalWidth().toFloat(); 992 float clusterTextWidth = parentDeepestBlockContainingAllText->contentLogicalWidth().toFloat(); 993 994 // Clusters with a root that is wider than the deepestBlockContainingAllText of their parent 995 // autosize independently of their parent. 996 if (contentWidth > clusterTextWidth) 997 return true; 998 999 // Clusters with a root that is significantly narrower than the deepestBlockContainingAllText of 1000 // their parent autosize independently of their parent. 1001 static float narrowWidthDifference = 200; 1002 if (clusterTextWidth - contentWidth > narrowWidthDifference) 1003 return true; 1004 1005 return false; 1006 } 1007 1008 FastTextAutosizer::Cluster* FastTextAutosizer::currentCluster() const 1009 { 1010 ASSERT_WITH_SECURITY_IMPLICATION(!m_clusterStack.isEmpty()); 1011 return m_clusterStack.last().get(); 1012 } 1013 1014 #ifndef NDEBUG 1015 void FastTextAutosizer::FingerprintMapper::assertMapsAreConsistent() 1016 { 1017 // For each fingerprint -> block mapping in m_blocksForFingerprint we should have an associated 1018 // map from block -> fingerprint in m_fingerprints. 1019 ReverseFingerprintMap::iterator end = m_blocksForFingerprint.end(); 1020 for (ReverseFingerprintMap::iterator fingerprintIt = m_blocksForFingerprint.begin(); fingerprintIt != end; ++fingerprintIt) { 1021 Fingerprint fingerprint = fingerprintIt->key; 1022 BlockSet* blocks = fingerprintIt->value.get(); 1023 for (BlockSet::iterator blockIt = blocks->begin(); blockIt != blocks->end(); ++blockIt) { 1024 const RenderBlock* block = (*blockIt); 1025 ASSERT(m_fingerprints.get(block) == fingerprint); 1026 } 1027 } 1028 } 1029 #endif 1030 1031 void FastTextAutosizer::FingerprintMapper::add(const RenderObject* renderer, Fingerprint fingerprint) 1032 { 1033 remove(renderer); 1034 1035 m_fingerprints.set(renderer, fingerprint); 1036 #ifndef NDEBUG 1037 assertMapsAreConsistent(); 1038 #endif 1039 } 1040 1041 void FastTextAutosizer::FingerprintMapper::addTentativeClusterRoot(const RenderBlock* block, Fingerprint fingerprint) 1042 { 1043 add(block, fingerprint); 1044 1045 ReverseFingerprintMap::AddResult addResult = m_blocksForFingerprint.add(fingerprint, PassOwnPtr<BlockSet>()); 1046 if (addResult.isNewEntry) 1047 addResult.storedValue->value = adoptPtr(new BlockSet); 1048 addResult.storedValue->value->add(block); 1049 #ifndef NDEBUG 1050 assertMapsAreConsistent(); 1051 #endif 1052 } 1053 1054 bool FastTextAutosizer::FingerprintMapper::remove(const RenderObject* renderer) 1055 { 1056 Fingerprint fingerprint = m_fingerprints.take(renderer); 1057 if (!fingerprint || !renderer->isRenderBlock()) 1058 return false; 1059 1060 ReverseFingerprintMap::iterator blocksIter = m_blocksForFingerprint.find(fingerprint); 1061 if (blocksIter == m_blocksForFingerprint.end()) 1062 return false; 1063 1064 BlockSet& blocks = *blocksIter->value; 1065 blocks.remove(toRenderBlock(renderer)); 1066 if (blocks.isEmpty()) 1067 m_blocksForFingerprint.remove(blocksIter); 1068 #ifndef NDEBUG 1069 assertMapsAreConsistent(); 1070 #endif 1071 return true; 1072 } 1073 1074 FastTextAutosizer::Fingerprint FastTextAutosizer::FingerprintMapper::get(const RenderObject* renderer) 1075 { 1076 return m_fingerprints.get(renderer); 1077 } 1078 1079 FastTextAutosizer::BlockSet& FastTextAutosizer::FingerprintMapper::getTentativeClusterRoots(Fingerprint fingerprint) 1080 { 1081 return *m_blocksForFingerprint.get(fingerprint); 1082 } 1083 1084 FastTextAutosizer::LayoutScope::LayoutScope(RenderBlock* block) 1085 : m_textAutosizer(block->document().fastTextAutosizer()) 1086 , m_block(block) 1087 { 1088 if (!m_textAutosizer) 1089 return; 1090 1091 if (m_textAutosizer->shouldHandleLayout()) 1092 m_textAutosizer->beginLayout(m_block); 1093 else 1094 m_textAutosizer = 0; 1095 } 1096 1097 FastTextAutosizer::LayoutScope::~LayoutScope() 1098 { 1099 if (m_textAutosizer) 1100 m_textAutosizer->endLayout(m_block); 1101 } 1102 1103 1104 FastTextAutosizer::TableLayoutScope::TableLayoutScope(RenderTable* table) 1105 : LayoutScope(table) 1106 { 1107 if (m_textAutosizer) { 1108 ASSERT(m_textAutosizer->shouldHandleLayout()); 1109 m_textAutosizer->inflateAutoTable(table); 1110 } 1111 } 1112 1113 FastTextAutosizer::DeferUpdatePageInfo::DeferUpdatePageInfo(Page* page) 1114 : m_mainFrame(page->deprecatedLocalMainFrame()) 1115 { 1116 if (FastTextAutosizer* textAutosizer = m_mainFrame->document()->fastTextAutosizer()) { 1117 ASSERT(!textAutosizer->m_updatePageInfoDeferred); 1118 textAutosizer->m_updatePageInfoDeferred = true; 1119 } 1120 } 1121 1122 FastTextAutosizer::DeferUpdatePageInfo::~DeferUpdatePageInfo() 1123 { 1124 if (FastTextAutosizer* textAutosizer = m_mainFrame->document()->fastTextAutosizer()) { 1125 ASSERT(textAutosizer->m_updatePageInfoDeferred); 1126 textAutosizer->m_updatePageInfoDeferred = false; 1127 textAutosizer->updatePageInfoInAllFrames(); 1128 } 1129 } 1130 1131 } // namespace WebCore 1132