src/third_party/WebKit/Source/core/rendering/RenderBlock.cpp

   1 /*
   2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
   3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
   4  *           (C) 2007 David Smith (catfish.man@gmail.com)
   5  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved.
   6  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Library General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Library General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Library General Public License
  19  * along with this library; see the file COPYING.LIB.  If not, write to
  20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  21  * Boston, MA 02110-1301, USA.
  22  */
  23
  24 #include "config.h"
  25 #include "core/rendering/RenderBlock.h"
  26
  27 #include "HTMLNames.h"
  28 #include "core/accessibility/AXObjectCache.h"
  29 #include "core/dom/Document.h"
  30 #include "core/dom/Element.h"
  31 #include "core/events/OverflowEvent.h"
  32 #include "core/dom/shadow/ShadowRoot.h"
  33 #include "core/editing/Editor.h"
  34 #include "core/editing/FrameSelection.h"
  35 #include "core/fetch/ResourceLoadPriorityOptimizer.h"
  36 #include "core/frame/Frame.h"
  37 #include "core/frame/FrameView.h"
  38 #include "core/page/Page.h"
  39 #include "core/frame/Settings.h"
  40 #include "core/rendering/FastTextAutosizer.h"
  41 #include "core/rendering/GraphicsContextAnnotator.h"
  42 #include "core/rendering/HitTestLocation.h"
  43 #include "core/rendering/HitTestResult.h"
  44 #include "core/rendering/InlineIterator.h"
  45 #include "core/rendering/InlineTextBox.h"
  46 #include "core/rendering/LayoutRectRecorder.h"
  47 #include "core/rendering/LayoutRepainter.h"
  48 #include "core/rendering/PaintInfo.h"
  49 #include "core/rendering/RenderCombineText.h"
  50 #include "core/rendering/RenderDeprecatedFlexibleBox.h"
  51 #include "core/rendering/RenderFlexibleBox.h"
  52 #include "core/rendering/RenderFlowThread.h"
  53 #include "core/rendering/RenderInline.h"
  54 #include "core/rendering/RenderLayer.h"
  55 #include "core/rendering/RenderMarquee.h"
  56 #include "core/rendering/RenderRegion.h"
  57 #include "core/rendering/RenderTableCell.h"
  58 #include "core/rendering/RenderTextControl.h"
  59 #include "core/rendering/RenderTextFragment.h"
  60 #include "core/rendering/RenderTheme.h"
  61 #include "core/rendering/RenderView.h"
  62 #include "core/rendering/shapes/ShapeOutsideInfo.h"
  63 #include "core/rendering/style/ContentData.h"
  64 #include "core/rendering/style/RenderStyle.h"
  65 #include "platform/geometry/FloatQuad.h"
  66 #include "platform/geometry/TransformState.h"
  67 #include "platform/graphics/GraphicsContextStateSaver.h"
  68 #include "wtf/StdLibExtras.h"
  69 #include "wtf/TemporaryChange.h"
  70
  71 using namespace std;
  72 using namespace WTF;
  73 using namespace Unicode;
  74
  75 namespace WebCore {
  76
  77 using namespace HTMLNames;
  78
  79 struct SameSizeAsRenderBlock : public RenderBox {
  80     void* pointers[1];
  81     RenderObjectChildList children;
  82     RenderLineBoxList lineBoxes;
  83     uint32_t bitfields;
  84 };
  85
  86 struct SameSizeAsRenderBlockRareData {
  87     int paginationStrut;
  88     int pageLogicalOffset;
  89     void* pointers[1];
  90     uint32_t bitfields;
  91 };
  92
  93 COMPILE_ASSERT(sizeof(RenderBlock) == sizeof(SameSizeAsRenderBlock), RenderBlock_should_stay_small);
  94 COMPILE_ASSERT(sizeof(RenderBlock::RenderBlockRareData) == sizeof(SameSizeAsRenderBlockRareData), RenderBlockRareData_should_stay_small);
  95
  96 typedef WTF::HashMap<const RenderBox*, OwnPtr<ColumnInfo> > ColumnInfoMap;
  97 static ColumnInfoMap* gColumnInfoMap = 0;
  98
  99 static TrackedDescendantsMap* gPositionedDescendantsMap = 0;
 100 static TrackedDescendantsMap* gPercentHeightDescendantsMap = 0;
 101
 102 static TrackedContainerMap* gPositionedContainerMap = 0;
 103 static TrackedContainerMap* gPercentHeightContainerMap = 0;
 104
 105 typedef WTF::HashMap<RenderBlock*, OwnPtr<ListHashSet<RenderInline*> > > ContinuationOutlineTableMap;
 106
 107 typedef WTF::HashSet<RenderBlock*> DelayedUpdateScrollInfoSet;
 108 static int gDelayUpdateScrollInfo = 0;
 109 static DelayedUpdateScrollInfoSet* gDelayedUpdateScrollInfoSet = 0;
 110
 111 static bool gColumnFlowSplitEnabled = true;
 112
 113 // This class helps dispatching the 'overflow' event on layout change. overflow can be set on RenderBoxes, yet the existing code
 114 // only works on RenderBlocks. If this changes, this class should be shared with other RenderBoxes.
 115 class OverflowEventDispatcher {
 116     WTF_MAKE_NONCOPYABLE(OverflowEventDispatcher);
 117 public:
 118     OverflowEventDispatcher(const RenderBlock* block)
 119         : m_block(block)
 120     {
 121         m_shouldDispatchEvent = !m_block->isAnonymous() && m_block->hasOverflowClip() && m_block->document().hasListenerType(Document::OVERFLOWCHANGED_LISTENER);
 122         if (m_shouldDispatchEvent) {
 123             m_hadHorizontalLayoutOverflow = m_block->hasHorizontalLayoutOverflow();
 124             m_hadVerticalLayoutOverflow = m_block->hasVerticalLayoutOverflow();
 125         }
 126     }
 127
 128     ~OverflowEventDispatcher()
 129     {
 130         if (!m_shouldDispatchEvent)
 131             return;
 132
 133         bool hasHorizontalLayoutOverflow = m_block->hasHorizontalLayoutOverflow();
 134         bool hasVerticalLayoutOverflow = m_block->hasVerticalLayoutOverflow();
 135
 136         bool horizontalLayoutOverflowChanged = hasHorizontalLayoutOverflow != m_hadHorizontalLayoutOverflow;
 137         bool verticalLayoutOverflowChanged = hasVerticalLayoutOverflow != m_hadVerticalLayoutOverflow;
 138
 139         if (!horizontalLayoutOverflowChanged && !verticalLayoutOverflowChanged)
 140             return;
 141
 142         RefPtr<OverflowEvent> event = OverflowEvent::create(horizontalLayoutOverflowChanged, hasHorizontalLayoutOverflow, verticalLayoutOverflowChanged, hasVerticalLayoutOverflow);
 143         event->setTarget(m_block->node());
 144         m_block->document().enqueueAnimationFrameEvent(event.release());
 145     }
 146
 147 private:
 148     const RenderBlock* m_block;
 149     bool m_shouldDispatchEvent;
 150     bool m_hadHorizontalLayoutOverflow;
 151     bool m_hadVerticalLayoutOverflow;
 152 };
 153
 154 RenderBlock::RenderBlock(ContainerNode* node)
 155     : RenderBox(node)
 156     , m_lineHeight(-1)
 157     , m_hasMarginBeforeQuirk(false)
 158     , m_hasMarginAfterQuirk(false)
 159     , m_beingDestroyed(false)
 160     , m_hasMarkupTruncation(false)
 161     , m_hasBorderOrPaddingLogicalWidthChanged(false)
 162     , m_hasOnlySelfCollapsingChildren(false)
 163 {
 164     setChildrenInline(true);
 165 }
 166
 167 static void removeBlockFromDescendantAndContainerMaps(RenderBlock* block, TrackedDescendantsMap*& descendantMap, TrackedContainerMap*& containerMap)
 168 {
 169     if (OwnPtr<TrackedRendererListHashSet> descendantSet = descendantMap->take(block)) {
 170         TrackedRendererListHashSet::iterator end = descendantSet->end();
 171         for (TrackedRendererListHashSet::iterator descendant = descendantSet->begin(); descendant != end; ++descendant) {
 172             TrackedContainerMap::iterator it = containerMap->find(*descendant);
 173             ASSERT(it != containerMap->end());
 174             if (it == containerMap->end())
 175                 continue;
 176             HashSet<RenderBlock*>* containerSet = it->value.get();
 177             ASSERT(containerSet->contains(block));
 178             containerSet->remove(block);
 179             if (containerSet->isEmpty())
 180                 containerMap->remove(it);
 181         }
 182     }
 183 }
 184
 185 static void appendImageIfNotNull(Vector<ImageResource*>& imageResources, const StyleImage* styleImage)
 186 {
 187     if (styleImage && styleImage->cachedImage()) {
 188         ImageResource* imageResource = styleImage->cachedImage();
 189         if (imageResource && !imageResource->isLoaded())
 190             imageResources.append(styleImage->cachedImage());
 191     }
 192 }
 193
 194 static void appendLayers(Vector<ImageResource*>& images, const FillLayer* styleLayer)
 195 {
 196     for (const FillLayer* layer = styleLayer; layer; layer = layer->next()) {
 197         appendImageIfNotNull(images, layer->image());
 198     }
 199 }
 200
 201 static void appendImagesFromStyle(Vector<ImageResource*>& images, RenderStyle& blockStyle)
 202 {
 203     appendLayers(images, blockStyle.backgroundLayers());
 204     appendLayers(images, blockStyle.maskLayers());
 205
 206     const ContentData* contentData = blockStyle.contentData();
 207     if (contentData && contentData->isImage()) {
 208         const ImageContentData* imageContentData = static_cast<const ImageContentData*>(contentData);
 209         appendImageIfNotNull(images, imageContentData->image());
 210     }
 211     if (blockStyle.boxReflect())
 212         appendImageIfNotNull(images, blockStyle.boxReflect()->mask().image());
 213     appendImageIfNotNull(images, blockStyle.listStyleImage());
 214     appendImageIfNotNull(images, blockStyle.borderImageSource());
 215     appendImageIfNotNull(images, blockStyle.maskBoxImageSource());
 216 }
 217
 218 RenderBlock::~RenderBlock()
 219 {
 220     ResourceLoadPriorityOptimizer::resourceLoadPriorityOptimizer()->removeRenderObject(this);
 221     if (hasColumns())
 222         gColumnInfoMap->take(this);
 223     if (gPercentHeightDescendantsMap)
 224         removeBlockFromDescendantAndContainerMaps(this, gPercentHeightDescendantsMap, gPercentHeightContainerMap);
 225     if (gPositionedDescendantsMap)
 226         removeBlockFromDescendantAndContainerMaps(this, gPositionedDescendantsMap, gPositionedContainerMap);
 227 }
 228
 229 void RenderBlock::willBeDestroyed()
 230 {
 231     // Mark as being destroyed to avoid trouble with merges in removeChild().
 232     m_beingDestroyed = true;
 233
 234     // Make sure to destroy anonymous children first while they are still connected to the rest of the tree, so that they will
 235     // properly dirty line boxes that they are removed from. Effects that do :before/:after only on hover could crash otherwise.
 236     children()->destroyLeftoverChildren();
 237
 238     // Destroy our continuation before anything other than anonymous children.
 239     // The reason we don't destroy it before anonymous children is that they may
 240     // have continuations of their own that are anonymous children of our continuation.
 241     RenderBoxModelObject* continuation = this->continuation();
 242     if (continuation) {
 243         continuation->destroy();
 244         setContinuation(0);
 245     }
 246
 247     if (!documentBeingDestroyed()) {
 248         if (firstLineBox()) {
 249             // We can't wait for RenderBox::destroy to clear the selection,
 250             // because by then we will have nuked the line boxes.
 251             // FIXME: The FrameSelection should be responsible for this when it
 252             // is notified of DOM mutations.
 253             if (isSelectionBorder())
 254                 view()->clearSelection();
 255
 256             // If we are an anonymous block, then our line boxes might have children
 257             // that will outlast this block. In the non-anonymous block case those
 258             // children will be destroyed by the time we return from this function.
 259             if (isAnonymousBlock()) {
 260                 for (InlineFlowBox* box = firstLineBox(); box; box = box->nextLineBox()) {
 261                     while (InlineBox* childBox = box->firstChild())
 262                         childBox->remove();
 263                 }
 264             }
 265         } else if (parent())
 266             parent()->dirtyLinesFromChangedChild(this);
 267     }
 268
 269     m_lineBoxes.deleteLineBoxes();
 270
 271     if (UNLIKELY(gDelayedUpdateScrollInfoSet != 0))
 272         gDelayedUpdateScrollInfoSet->remove(this);
 273
 274     if (FastTextAutosizer* textAutosizer = document().fastTextAutosizer())
 275         textAutosizer->destroy(this);
 276
 277     RenderBox::willBeDestroyed();
 278 }
 279
 280 void RenderBlock::styleWillChange(StyleDifference diff, const RenderStyle* newStyle)
 281 {
 282     RenderStyle* oldStyle = style();
 283
 284     setReplaced(newStyle->isDisplayInlineType());
 285
 286     if (oldStyle && parent() && diff == StyleDifferenceLayout && oldStyle->position() != newStyle->position()) {
 287         if (newStyle->position() == StaticPosition)
 288             // Clear our positioned objects list. Our absolutely positioned descendants will be
 289             // inserted into our containing block's positioned objects list during layout.
 290             removePositionedObjects(0, NewContainingBlock);
 291         else if (oldStyle->position() == StaticPosition) {
 292             // Remove our absolutely positioned descendants from their current containing block.
 293             // They will be inserted into our positioned objects list during layout.
 294             RenderObject* cb = parent();
 295             while (cb && (cb->style()->position() == StaticPosition || (cb->isInline() && !cb->isReplaced())) && !cb->isRenderView()) {
 296                 if (cb->style()->position() == RelativePosition && cb->isInline() && !cb->isReplaced()) {
 297                     cb = cb->containingBlock();
 298                     break;
 299                 }
 300                 cb = cb->parent();
 301             }
 302
 303             if (cb->isRenderBlock())
 304                 toRenderBlock(cb)->removePositionedObjects(this, NewContainingBlock);
 305         }
 306     }
 307
 308     RenderBox::styleWillChange(diff, newStyle);
 309 }
 310
 311 static bool borderOrPaddingLogicalWidthChanged(const RenderStyle* oldStyle, const RenderStyle* newStyle)
 312 {
 313     if (newStyle->isHorizontalWritingMode())
 314         return oldStyle->borderLeftWidth() != newStyle->borderLeftWidth()
 315             || oldStyle->borderRightWidth() != newStyle->borderRightWidth()
 316             || oldStyle->paddingLeft() != newStyle->paddingLeft()
 317             || oldStyle->paddingRight() != newStyle->paddingRight();
 318
 319     return oldStyle->borderTopWidth() != newStyle->borderTopWidth()
 320         || oldStyle->borderBottomWidth() != newStyle->borderBottomWidth()
 321         || oldStyle->paddingTop() != newStyle->paddingTop()
 322         || oldStyle->paddingBottom() != newStyle->paddingBottom();
 323 }
 324
 325 void RenderBlock::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
 326 {
 327     RenderBox::styleDidChange(diff, oldStyle);
 328
 329     RenderStyle* newStyle = style();
 330
 331     updateShapeInsideInfoAfterStyleChange(newStyle->resolvedShapeInside(), oldStyle ? oldStyle->resolvedShapeInside() : RenderStyle::initialShapeInside());
 332
 333     if (!isAnonymousBlock()) {
 334         // Ensure that all of our continuation blocks pick up the new style.
 335         for (RenderBlock* currCont = blockElementContinuation(); currCont; currCont = currCont->blockElementContinuation()) {
 336             RenderBoxModelObject* nextCont = currCont->continuation();
 337             currCont->setContinuation(0);
 338             currCont->setStyle(newStyle);
 339             currCont->setContinuation(nextCont);
 340         }
 341     }
 342
 343     if (FastTextAutosizer* textAutosizer = document().fastTextAutosizer())
 344         textAutosizer->record(this);
 345
 346     propagateStyleToAnonymousChildren(true);
 347     m_lineHeight = -1;
 348
 349     // It's possible for our border/padding to change, but for the overall logical width of the block to
 350     // end up being the same. We keep track of this change so in layoutBlock, we can know to set relayoutChildren=true.
 351     m_hasBorderOrPaddingLogicalWidthChanged = oldStyle && diff == StyleDifferenceLayout && needsLayout() && borderOrPaddingLogicalWidthChanged(oldStyle, newStyle);
 352
 353     // If the style has unloaded images, want to notify the ResourceLoadPriorityOptimizer so that
 354     // network priorities can be set.
 355     Vector<ImageResource*> images;
 356     appendImagesFromStyle(images, *newStyle);
 357     if (images.isEmpty())
 358         ResourceLoadPriorityOptimizer::resourceLoadPriorityOptimizer()->removeRenderObject(this);
 359     else
 360         ResourceLoadPriorityOptimizer::resourceLoadPriorityOptimizer()->addRenderObject(this);
 361 }
 362
 363 RenderBlock* RenderBlock::continuationBefore(RenderObject* beforeChild)
 364 {
 365     if (beforeChild && beforeChild->parent() == this)
 366         return this;
 367
 368     RenderBlock* curr = toRenderBlock(continuation());
 369     RenderBlock* nextToLast = this;
 370     RenderBlock* last = this;
 371     while (curr) {
 372         if (beforeChild && beforeChild->parent() == curr) {
 373             if (curr->firstChild() == beforeChild)
 374                 return last;
 375             return curr;
 376         }
 377
 378         nextToLast = last;
 379         last = curr;
 380         curr = toRenderBlock(curr->continuation());
 381     }
 382
 383     if (!beforeChild && !last->firstChild())
 384         return nextToLast;
 385     return last;
 386 }
 387
 388 void RenderBlock::addChildToContinuation(RenderObject* newChild, RenderObject* beforeChild)
 389 {
 390     RenderBlock* flow = continuationBefore(beforeChild);
 391     ASSERT(!beforeChild || beforeChild->parent()->isAnonymousColumnSpanBlock() || beforeChild->parent()->isRenderBlock());
 392     RenderBoxModelObject* beforeChildParent = 0;
 393     if (beforeChild)
 394         beforeChildParent = toRenderBoxModelObject(beforeChild->parent());
 395     else {
 396         RenderBoxModelObject* cont = flow->continuation();
 397         if (cont)
 398             beforeChildParent = cont;
 399         else
 400             beforeChildParent = flow;
 401     }
 402
 403     if (newChild->isFloatingOrOutOfFlowPositioned()) {
 404         beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);
 405         return;
 406     }
 407
 408     // A continuation always consists of two potential candidates: a block or an anonymous
 409     // column span box holding column span children.
 410     bool childIsNormal = newChild->isInline() || !newChild->style()->columnSpan();
 411     bool bcpIsNormal = beforeChildParent->isInline() || !beforeChildParent->style()->columnSpan();
 412     bool flowIsNormal = flow->isInline() || !flow->style()->columnSpan();
 413
 414     if (flow == beforeChildParent) {
 415         flow->addChildIgnoringContinuation(newChild, beforeChild);
 416         return;
 417     }
 418
 419     // The goal here is to match up if we can, so that we can coalesce and create the
 420     // minimal # of continuations needed for the inline.
 421     if (childIsNormal == bcpIsNormal) {
 422         beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);
 423         return;
 424     }
 425     if (flowIsNormal == childIsNormal) {
 426         flow->addChildIgnoringContinuation(newChild, 0); // Just treat like an append.
 427         return;
 428     }
 429     beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);
 430 }
 431
 432
 433 void RenderBlock::addChildToAnonymousColumnBlocks(RenderObject* newChild, RenderObject* beforeChild)
 434 {
 435     ASSERT(!continuation()); // We don't yet support column spans that aren't immediate children of the multi-column block.
 436
 437     // The goal is to locate a suitable box in which to place our child.
 438     RenderBlock* beforeChildParent = 0;
 439     if (beforeChild) {
 440         RenderObject* curr = beforeChild;
 441         while (curr && curr->parent() != this)
 442             curr = curr->parent();
 443         beforeChildParent = toRenderBlock(curr);
 444         ASSERT(beforeChildParent);
 445         ASSERT(beforeChildParent->isAnonymousColumnsBlock() || beforeChildParent->isAnonymousColumnSpanBlock());
 446     } else
 447         beforeChildParent = toRenderBlock(lastChild());
 448
 449     // If the new child is floating or positioned it can just go in that block.
 450     if (newChild->isFloatingOrOutOfFlowPositioned()) {
 451         beforeChildParent->addChildIgnoringAnonymousColumnBlocks(newChild, beforeChild);
 452         return;
 453     }
 454
 455     // See if the child can be placed in the box.
 456     bool newChildHasColumnSpan = newChild->style()->columnSpan() && !newChild->isInline();
 457     bool beforeChildParentHoldsColumnSpans = beforeChildParent->isAnonymousColumnSpanBlock();
 458
 459     if (newChildHasColumnSpan == beforeChildParentHoldsColumnSpans) {
 460         beforeChildParent->addChildIgnoringAnonymousColumnBlocks(newChild, beforeChild);
 461         return;
 462     }
 463
 464     if (!beforeChild) {
 465         // Create a new block of the correct type.
 466         RenderBlock* newBox = newChildHasColumnSpan ? createAnonymousColumnSpanBlock() : createAnonymousColumnsBlock();
 467         children()->appendChildNode(this, newBox);
 468         newBox->addChildIgnoringAnonymousColumnBlocks(newChild, 0);
 469         return;
 470     }
 471
 472     RenderObject* immediateChild = beforeChild;
 473     bool isPreviousBlockViable = true;
 474     while (immediateChild->parent() != this) {
 475         if (isPreviousBlockViable)
 476             isPreviousBlockViable = !immediateChild->previousSibling();
 477         immediateChild = immediateChild->parent();
 478     }
 479     if (isPreviousBlockViable && immediateChild->previousSibling()) {
 480         toRenderBlock(immediateChild->previousSibling())->addChildIgnoringAnonymousColumnBlocks(newChild, 0); // Treat like an append.
 481         return;
 482     }
 483
 484     // Split our anonymous blocks.
 485     RenderObject* newBeforeChild = splitAnonymousBoxesAroundChild(beforeChild);
 486
 487
 488     // Create a new anonymous box of the appropriate type.
 489     RenderBlock* newBox = newChildHasColumnSpan ? createAnonymousColumnSpanBlock() : createAnonymousColumnsBlock();
 490     children()->insertChildNode(this, newBox, newBeforeChild);
 491     newBox->addChildIgnoringAnonymousColumnBlocks(newChild, 0);
 492     return;
 493 }
 494
 495 RenderBlockFlow* RenderBlock::containingColumnsBlock(bool allowAnonymousColumnBlock)
 496 {
 497     RenderBlock* firstChildIgnoringAnonymousWrappers = 0;
 498     for (RenderObject* curr = this; curr; curr = curr->parent()) {
 499         if (!curr->isRenderBlock() || curr->isFloatingOrOutOfFlowPositioned() || curr->isTableCell() || curr->isRoot() || curr->isRenderView() || curr->hasOverflowClip()
 500             || curr->isInlineBlockOrInlineTable())
 501             return 0;
 502
 503         // FIXME: Renderers that do special management of their children (tables, buttons,
 504         // lists, flexboxes, etc.) breaks when the flow is split through them. Disabling
 505         // multi-column for them to avoid this problem.)
 506         if (!curr->isRenderBlockFlow() || curr->isListItem())
 507             return 0;
 508
 509         RenderBlockFlow* currBlock = toRenderBlockFlow(curr);
 510         if (!currBlock->createsAnonymousWrapper())
 511             firstChildIgnoringAnonymousWrappers = currBlock;
 512
 513         if (currBlock->style()->specifiesColumns() && (allowAnonymousColumnBlock || !currBlock->isAnonymousColumnsBlock()))
 514             return toRenderBlockFlow(firstChildIgnoringAnonymousWrappers);
 515
 516         if (currBlock->isAnonymousColumnSpanBlock())
 517             return 0;
 518     }
 519     return 0;
 520 }
 521
 522 RenderBlock* RenderBlock::clone() const
 523 {
 524     RenderBlock* cloneBlock;
 525     if (isAnonymousBlock()) {
 526         cloneBlock = createAnonymousBlock();
 527         cloneBlock->setChildrenInline(childrenInline());
 528     }
 529     else {
 530         RenderObject* cloneRenderer = toElement(node())->createRenderer(style());
 531         cloneBlock = toRenderBlock(cloneRenderer);
 532         cloneBlock->setStyle(style());
 533
 534         // This takes care of setting the right value of childrenInline in case
 535         // generated content is added to cloneBlock and 'this' does not have
 536         // generated content added yet.
 537         cloneBlock->setChildrenInline(cloneBlock->firstChild() ? cloneBlock->firstChild()->isInline() : childrenInline());
 538     }
 539     cloneBlock->setFlowThreadState(flowThreadState());
 540     return cloneBlock;
 541 }
 542
 543 void RenderBlock::splitBlocks(RenderBlock* fromBlock, RenderBlock* toBlock,
 544                               RenderBlock* middleBlock,
 545                               RenderObject* beforeChild, RenderBoxModelObject* oldCont)
 546 {
 547     // Create a clone of this inline.
 548     RenderBlock* cloneBlock = clone();
 549     if (!isAnonymousBlock())
 550         cloneBlock->setContinuation(oldCont);
 551
 552     if (!beforeChild && isAfterContent(lastChild()))
 553         beforeChild = lastChild();
 554
 555     // If we are moving inline children from |this| to cloneBlock, then we need
 556     // to clear our line box tree.
 557     if (beforeChild && childrenInline())
 558         deleteLineBoxTree();
 559
 560     // Now take all of the children from beforeChild to the end and remove
 561     // them from |this| and place them in the clone.
 562     moveChildrenTo(cloneBlock, beforeChild, 0, true);
 563
 564     // Hook |clone| up as the continuation of the middle block.
 565     if (!cloneBlock->isAnonymousBlock())
 566         middleBlock->setContinuation(cloneBlock);
 567
 568     // We have been reparented and are now under the fromBlock.  We need
 569     // to walk up our block parent chain until we hit the containing anonymous columns block.
 570     // Once we hit the anonymous columns block we're done.
 571     RenderBoxModelObject* curr = toRenderBoxModelObject(parent());
 572     RenderBoxModelObject* currChild = this;
 573     RenderObject* currChildNextSibling = currChild->nextSibling();
 574
 575     while (curr && curr->isDescendantOf(fromBlock) && curr != fromBlock) {
 576         ASSERT_WITH_SECURITY_IMPLICATION(curr->isRenderBlock());
 577
 578         RenderBlock* blockCurr = toRenderBlock(curr);
 579
 580         // Create a new clone.
 581         RenderBlock* cloneChild = cloneBlock;
 582         cloneBlock = blockCurr->clone();
 583
 584         // Insert our child clone as the first child.
 585         cloneBlock->addChildIgnoringContinuation(cloneChild, 0);
 586
 587         // Hook the clone up as a continuation of |curr|.  Note we do encounter
 588         // anonymous blocks possibly as we walk up the block chain.  When we split an
 589         // anonymous block, there's no need to do any continuation hookup, since we haven't
 590         // actually split a real element.
 591         if (!blockCurr->isAnonymousBlock()) {
 592             oldCont = blockCurr->continuation();
 593             blockCurr->setContinuation(cloneBlock);
 594             cloneBlock->setContinuation(oldCont);
 595         }
 596
 597         // Now we need to take all of the children starting from the first child
 598         // *after* currChild and append them all to the clone.
 599         blockCurr->moveChildrenTo(cloneBlock, currChildNextSibling, 0, true);
 600
 601         // Keep walking up the chain.
 602         currChild = curr;
 603         currChildNextSibling = currChild->nextSibling();
 604         curr = toRenderBoxModelObject(curr->parent());
 605     }
 606
 607     // Now we are at the columns block level. We need to put the clone into the toBlock.
 608     toBlock->children()->appendChildNode(toBlock, cloneBlock);
 609
 610     // Now take all the children after currChild and remove them from the fromBlock
 611     // and put them in the toBlock.
 612     fromBlock->moveChildrenTo(toBlock, currChildNextSibling, 0, true);
 613 }
 614
 615 void RenderBlock::splitFlow(RenderObject* beforeChild, RenderBlock* newBlockBox,
 616                             RenderObject* newChild, RenderBoxModelObject* oldCont)
 617 {
 618     RenderBlock* pre = 0;
 619     RenderBlock* block = containingColumnsBlock();
 620
 621     // Delete our line boxes before we do the inline split into continuations.
 622     block->deleteLineBoxTree();
 623
 624     bool madeNewBeforeBlock = false;
 625     if (block->isAnonymousColumnsBlock()) {
 626         // We can reuse this block and make it the preBlock of the next continuation.
 627         pre = block;
 628         pre->removePositionedObjects(0);
 629         if (block->isRenderBlockFlow())
 630             toRenderBlockFlow(pre)->removeFloatingObjects();
 631         block = toRenderBlock(block->parent());
 632     } else {
 633         // No anonymous block available for use.  Make one.
 634         pre = block->createAnonymousColumnsBlock();
 635         pre->setChildrenInline(false);
 636         madeNewBeforeBlock = true;
 637     }
 638
 639     RenderBlock* post = block->createAnonymousColumnsBlock();
 640     post->setChildrenInline(false);
 641
 642     RenderObject* boxFirst = madeNewBeforeBlock ? block->firstChild() : pre->nextSibling();
 643     if (madeNewBeforeBlock)
 644         block->children()->insertChildNode(block, pre, boxFirst);
 645     block->children()->insertChildNode(block, newBlockBox, boxFirst);
 646     block->children()->insertChildNode(block, post, boxFirst);
 647     block->setChildrenInline(false);
 648
 649     if (madeNewBeforeBlock)
 650         block->moveChildrenTo(pre, boxFirst, 0, true);
 651
 652     splitBlocks(pre, post, newBlockBox, beforeChild, oldCont);
 653
 654     // We already know the newBlockBox isn't going to contain inline kids, so avoid wasting
 655     // time in makeChildrenNonInline by just setting this explicitly up front.
 656     newBlockBox->setChildrenInline(false);
 657
 658     newBlockBox->addChild(newChild);
 659
 660     // Always just do a full layout in order to ensure that line boxes (especially wrappers for images)
 661     // get deleted properly.  Because objects moves from the pre block into the post block, we want to
 662     // make new line boxes instead of leaving the old line boxes around.
 663     pre->setNeedsLayoutAndPrefWidthsRecalc();
 664     block->setNeedsLayoutAndPrefWidthsRecalc();
 665     post->setNeedsLayoutAndPrefWidthsRecalc();
 666 }
 667
 668 void RenderBlock::makeChildrenAnonymousColumnBlocks(RenderObject* beforeChild, RenderBlockFlow* newBlockBox, RenderObject* newChild)
 669 {
 670     RenderBlockFlow* pre = 0;
 671     RenderBlockFlow* post = 0;
 672     RenderBlock* block = this; // Eventually block will not just be |this|, but will also be a block nested inside |this|.  Assign to a variable
 673                                // so that we don't have to patch all of the rest of the code later on.
 674
 675     // Delete the block's line boxes before we do the split.
 676     block->deleteLineBoxTree();
 677
 678     if (beforeChild && beforeChild->parent() != this)
 679         beforeChild = splitAnonymousBoxesAroundChild(beforeChild);
 680
 681     if (beforeChild != firstChild()) {
 682         pre = block->createAnonymousColumnsBlock();
 683         pre->setChildrenInline(block->childrenInline());
 684     }
 685
 686     if (beforeChild) {
 687         post = block->createAnonymousColumnsBlock();
 688         post->setChildrenInline(block->childrenInline());
 689     }
 690
 691     RenderObject* boxFirst = block->firstChild();
 692     if (pre)
 693         block->children()->insertChildNode(block, pre, boxFirst);
 694     block->children()->insertChildNode(block, newBlockBox, boxFirst);
 695     if (post)
 696         block->children()->insertChildNode(block, post, boxFirst);
 697     block->setChildrenInline(false);
 698
 699     // The pre/post blocks always have layers, so we know to always do a full insert/remove (so we pass true as the last argument).
 700     block->moveChildrenTo(pre, boxFirst, beforeChild, true);
 701     block->moveChildrenTo(post, beforeChild, 0, true);
 702
 703     // We already know the newBlockBox isn't going to contain inline kids, so avoid wasting
 704     // time in makeChildrenNonInline by just setting this explicitly up front.
 705     newBlockBox->setChildrenInline(false);
 706
 707     newBlockBox->addChild(newChild);
 708
 709     // Always just do a full layout in order to ensure that line boxes (especially wrappers for images)
 710     // get deleted properly.  Because objects moved from the pre block into the post block, we want to
 711     // make new line boxes instead of leaving the old line boxes around.
 712     if (pre)
 713         pre->setNeedsLayoutAndPrefWidthsRecalc();
 714     block->setNeedsLayoutAndPrefWidthsRecalc();
 715     if (post)
 716         post->setNeedsLayoutAndPrefWidthsRecalc();
 717 }
 718
 719 RenderBlockFlow* RenderBlock::columnsBlockForSpanningElement(RenderObject* newChild)
 720 {
 721     // FIXME: This function is the gateway for the addition of column-span support.  It will
 722     // be added to in three stages:
 723     // (1) Immediate children of a multi-column block can span.
 724     // (2) Nested block-level children with only block-level ancestors between them and the multi-column block can span.
 725     // (3) Nested children with block or inline ancestors between them and the multi-column block can span (this is when we
 726     // cross the streams and have to cope with both types of continuations mixed together).
 727     // This function currently supports (1) and (2).
 728     RenderBlockFlow* columnsBlockAncestor = 0;
 729     if (!newChild->isText() && newChild->style()->columnSpan() && !newChild->isBeforeOrAfterContent()
 730         && !newChild->isFloatingOrOutOfFlowPositioned() && !newChild->isInline() && !isAnonymousColumnSpanBlock()) {
 731         columnsBlockAncestor = containingColumnsBlock(false);
 732         if (columnsBlockAncestor) {
 733             // Make sure that none of the parent ancestors have a continuation.
 734             // If yes, we do not want split the block into continuations.
 735             RenderObject* curr = this;
 736             while (curr && curr != columnsBlockAncestor) {
 737                 if (curr->isRenderBlock() && toRenderBlock(curr)->continuation()) {
 738                     columnsBlockAncestor = 0;
 739                     break;
 740                 }
 741                 curr = curr->parent();
 742             }
 743         }
 744     }
 745     return columnsBlockAncestor;
 746 }
 747
 748 void RenderBlock::addChildIgnoringAnonymousColumnBlocks(RenderObject* newChild, RenderObject* beforeChild)
 749 {
 750     if (beforeChild && beforeChild->parent() != this) {
 751         RenderObject* beforeChildContainer = beforeChild->parent();
 752         while (beforeChildContainer->parent() != this)
 753             beforeChildContainer = beforeChildContainer->parent();
 754         ASSERT(beforeChildContainer);
 755
 756         if (beforeChildContainer->isAnonymous()) {
 757             // If the requested beforeChild is not one of our children, then this is because
 758             // there is an anonymous container within this object that contains the beforeChild.
 759             RenderObject* beforeChildAnonymousContainer = beforeChildContainer;
 760             if (beforeChildAnonymousContainer->isAnonymousBlock()
 761                 // Full screen renderers and full screen placeholders act as anonymous blocks, not tables:
 762                 || beforeChildAnonymousContainer->isRenderFullScreen()
 763                 || beforeChildAnonymousContainer->isRenderFullScreenPlaceholder()
 764                 ) {
 765                 // Insert the child into the anonymous block box instead of here.
 766                 if (newChild->isInline() || newChild->isFloatingOrOutOfFlowPositioned() || beforeChild->parent()->firstChild() != beforeChild)
 767                     beforeChild->parent()->addChild(newChild, beforeChild);
 768                 else
 769                     addChild(newChild, beforeChild->parent());
 770                 return;
 771             }
 772
 773             ASSERT(beforeChildAnonymousContainer->isTable());
 774             if (newChild->isTablePart()) {
 775                 // Insert into the anonymous table.
 776                 beforeChildAnonymousContainer->addChild(newChild, beforeChild);
 777                 return;
 778             }
 779
 780             beforeChild = splitAnonymousBoxesAroundChild(beforeChild);
 781
 782             ASSERT(beforeChild->parent() == this);
 783             if (beforeChild->parent() != this) {
 784                 // We should never reach here. If we do, we need to use the
 785                 // safe fallback to use the topmost beforeChild container.
 786                 beforeChild = beforeChildContainer;
 787             }
 788         }
 789     }
 790
 791     // Check for a spanning element in columns.
 792     if (gColumnFlowSplitEnabled) {
 793         RenderBlockFlow* columnsBlockAncestor = columnsBlockForSpanningElement(newChild);
 794         if (columnsBlockAncestor) {
 795             TemporaryChange<bool> columnFlowSplitEnabled(gColumnFlowSplitEnabled, false);
 796             // We are placing a column-span element inside a block.
 797             RenderBlockFlow* newBox = createAnonymousColumnSpanBlock();
 798
 799             if (columnsBlockAncestor != this && !isRenderFlowThread()) {
 800                 // We are nested inside a multi-column element and are being split by the span. We have to break up
 801                 // our block into continuations.
 802                 RenderBoxModelObject* oldContinuation = continuation();
 803
 804                 // When we split an anonymous block, there's no need to do any continuation hookup,
 805                 // since we haven't actually split a real element.
 806                 if (!isAnonymousBlock())
 807                     setContinuation(newBox);
 808
 809                 splitFlow(beforeChild, newBox, newChild, oldContinuation);
 810                 return;
 811             }
 812
 813             // We have to perform a split of this block's children. This involves creating an anonymous block box to hold
 814             // the column-spanning |newChild|. We take all of the children from before |newChild| and put them into
 815             // one anonymous columns block, and all of the children after |newChild| go into another anonymous block.
 816             makeChildrenAnonymousColumnBlocks(beforeChild, newBox, newChild);
 817             return;
 818         }
 819     }
 820
 821     bool madeBoxesNonInline = false;
 822
 823     // A block has to either have all of its children inline, or all of its children as blocks.
 824     // So, if our children are currently inline and a block child has to be inserted, we move all our
 825     // inline children into anonymous block boxes.
 826     if (childrenInline() && !newChild->isInline() && !newChild->isFloatingOrOutOfFlowPositioned()) {
 827         // This is a block with inline content. Wrap the inline content in anonymous blocks.
 828         makeChildrenNonInline(beforeChild);
 829         madeBoxesNonInline = true;
 830
 831         if (beforeChild && beforeChild->parent() != this) {
 832             beforeChild = beforeChild->parent();
 833             ASSERT(beforeChild->isAnonymousBlock());
 834             ASSERT(beforeChild->parent() == this);
 835         }
 836     } else if (!childrenInline() && (newChild->isFloatingOrOutOfFlowPositioned() || newChild->isInline())) {
 837         // If we're inserting an inline child but all of our children are blocks, then we have to make sure
 838         // it is put into an anomyous block box. We try to use an existing anonymous box if possible, otherwise
 839         // a new one is created and inserted into our list of children in the appropriate position.
 840         RenderObject* afterChild = beforeChild ? beforeChild->previousSibling() : lastChild();
 841
 842         if (afterChild && afterChild->isAnonymousBlock()) {
 843             afterChild->addChild(newChild);
 844             return;
 845         }
 846
 847         if (newChild->isInline()) {
 848             // No suitable existing anonymous box - create a new one.
 849             RenderBlock* newBox = createAnonymousBlock();
 850             RenderBox::addChild(newBox, beforeChild);
 851             newBox->addChild(newChild);
 852             return;
 853         }
 854     }
 855
 856     RenderBox::addChild(newChild, beforeChild);
 857
 858     if (madeBoxesNonInline && parent() && isAnonymousBlock() && parent()->isRenderBlock())
 859         toRenderBlock(parent())->removeLeftoverAnonymousBlock(this);
 860     // this object may be dead here
 861 }
 862
 863 void RenderBlock::addChild(RenderObject* newChild, RenderObject* beforeChild)
 864 {
 865     if (continuation() && !isAnonymousBlock())
 866         addChildToContinuation(newChild, beforeChild);
 867     else
 868         addChildIgnoringContinuation(newChild, beforeChild);
 869 }
 870
 871 void RenderBlock::addChildIgnoringContinuation(RenderObject* newChild, RenderObject* beforeChild)
 872 {
 873     if (!isAnonymousBlock() && firstChild() && (firstChild()->isAnonymousColumnsBlock() || firstChild()->isAnonymousColumnSpanBlock()))
 874         addChildToAnonymousColumnBlocks(newChild, beforeChild);
 875     else
 876         addChildIgnoringAnonymousColumnBlocks(newChild, beforeChild);
 877 }
 878
 879 static void getInlineRun(RenderObject* start, RenderObject* boundary,
 880                          RenderObject*& inlineRunStart,
 881                          RenderObject*& inlineRunEnd)
 882 {
 883     // Beginning at |start| we find the largest contiguous run of inlines that
 884     // we can.  We denote the run with start and end points, |inlineRunStart|
 885     // and |inlineRunEnd|.  Note that these two values may be the same if
 886     // we encounter only one inline.
 887     //
 888     // We skip any non-inlines we encounter as long as we haven't found any
 889     // inlines yet.
 890     //
 891     // |boundary| indicates a non-inclusive boundary point.  Regardless of whether |boundary|
 892     // is inline or not, we will not include it in a run with inlines before it.  It's as though we encountered
 893     // a non-inline.
 894
 895     // Start by skipping as many non-inlines as we can.
 896     RenderObject * curr = start;
 897     bool sawInline;
 898     do {
 899         while (curr && !(curr->isInline() || curr->isFloatingOrOutOfFlowPositioned()))
 900             curr = curr->nextSibling();
 901
 902         inlineRunStart = inlineRunEnd = curr;
 903
 904         if (!curr)
 905             return; // No more inline children to be found.
 906
 907         sawInline = curr->isInline();
 908
 909         curr = curr->nextSibling();
 910         while (curr && (curr->isInline() || curr->isFloatingOrOutOfFlowPositioned()) && (curr != boundary)) {
 911             inlineRunEnd = curr;
 912             if (curr->isInline())
 913                 sawInline = true;
 914             curr = curr->nextSibling();
 915         }
 916     } while (!sawInline);
 917 }
 918
 919 void RenderBlock::deleteLineBoxTree()
 920 {
 921     m_lineBoxes.deleteLineBoxTree();
 922
 923     if (AXObjectCache* cache = document().existingAXObjectCache())
 924         cache->recomputeIsIgnored(this);
 925 }
 926
 927 void RenderBlock::makeChildrenNonInline(RenderObject *insertionPoint)
 928 {
 929     // makeChildrenNonInline takes a block whose children are *all* inline and it
 930     // makes sure that inline children are coalesced under anonymous
 931     // blocks.  If |insertionPoint| is defined, then it represents the insertion point for
 932     // the new block child that is causing us to have to wrap all the inlines.  This
 933     // means that we cannot coalesce inlines before |insertionPoint| with inlines following
 934     // |insertionPoint|, because the new child is going to be inserted in between the inlines,
 935     // splitting them.
 936     ASSERT(isInlineBlockOrInlineTable() || !isInline());
 937     ASSERT(!insertionPoint || insertionPoint->parent() == this);
 938
 939     setChildrenInline(false);
 940
 941     RenderObject *child = firstChild();
 942     if (!child)
 943         return;
 944
 945     deleteLineBoxTree();
 946
 947     while (child) {
 948         RenderObject *inlineRunStart, *inlineRunEnd;
 949         getInlineRun(child, insertionPoint, inlineRunStart, inlineRunEnd);
 950
 951         if (!inlineRunStart)
 952             break;
 953
 954         child = inlineRunEnd->nextSibling();
 955
 956         RenderBlock* block = createAnonymousBlock();
 957         children()->insertChildNode(this, block, inlineRunStart);
 958         moveChildrenTo(block, inlineRunStart, child);
 959     }
 960
 961 #ifndef NDEBUG
 962     for (RenderObject *c = firstChild(); c; c = c->nextSibling())
 963         ASSERT(!c->isInline());
 964 #endif
 965
 966     repaint();
 967 }
 968
 969 void RenderBlock::removeLeftoverAnonymousBlock(RenderBlock* child)
 970 {
 971     ASSERT(child->isAnonymousBlock());
 972     ASSERT(!child->childrenInline());
 973
 974     if (child->continuation() || (child->firstChild() && (child->isAnonymousColumnSpanBlock() || child->isAnonymousColumnsBlock())))
 975         return;
 976
 977     RenderObject* firstAnChild = child->m_children.firstChild();
 978     RenderObject* lastAnChild = child->m_children.lastChild();
 979     if (firstAnChild) {
 980         RenderObject* o = firstAnChild;
 981         while (o) {
 982             o->setParent(this);
 983             o = o->nextSibling();
 984         }
 985         firstAnChild->setPreviousSibling(child->previousSibling());
 986         lastAnChild->setNextSibling(child->nextSibling());
 987         if (child->previousSibling())
 988             child->previousSibling()->setNextSibling(firstAnChild);
 989         if (child->nextSibling())
 990             child->nextSibling()->setPreviousSibling(lastAnChild);
 991
 992         if (child == m_children.firstChild())
 993             m_children.setFirstChild(firstAnChild);
 994         if (child == m_children.lastChild())
 995             m_children.setLastChild(lastAnChild);
 996     } else {
 997         if (child == m_children.firstChild())
 998             m_children.setFirstChild(child->nextSibling());
 999         if (child == m_children.lastChild())
1000             m_children.setLastChild(child->previousSibling());
1001
1002         if (child->previousSibling())
1003             child->previousSibling()->setNextSibling(child->nextSibling());
1004         if (child->nextSibling())
1005             child->nextSibling()->setPreviousSibling(child->previousSibling());
1006     }
1007
1008     child->children()->setFirstChild(0);
1009     child->m_next = 0;
1010
1011     // Remove all the information in the flow thread associated with the leftover anonymous block.
1012     child->removeFromRenderFlowThread();
1013
1014     child->setParent(0);
1015     child->setPreviousSibling(0);
1016     child->setNextSibling(0);
1017
1018     child->destroy();
1019 }
1020
1021 static bool canMergeContiguousAnonymousBlocks(RenderObject* oldChild, RenderObject* prev, RenderObject* next)
1022 {
1023     if (oldChild->documentBeingDestroyed() || oldChild->isInline() || oldChild->virtualContinuation())
1024         return false;
1025
1026     if ((prev && (!prev->isAnonymousBlock() || toRenderBlock(prev)->continuation() || toRenderBlock(prev)->beingDestroyed()))
1027         || (next && (!next->isAnonymousBlock() || toRenderBlock(next)->continuation() || toRenderBlock(next)->beingDestroyed())))
1028         return false;
1029
1030     if ((prev && (prev->isRubyRun() || prev->isRubyBase()))
1031         || (next && (next->isRubyRun() || next->isRubyBase())))
1032         return false;
1033
1034     if (!prev || !next)
1035         return true;
1036
1037     // Make sure the types of the anonymous blocks match up.
1038     return prev->isAnonymousColumnsBlock() == next->isAnonymousColumnsBlock()
1039            && prev->isAnonymousColumnSpanBlock() == next->isAnonymousColumnSpanBlock();
1040 }
1041
1042 void RenderBlock::collapseAnonymousBlockChild(RenderBlock* parent, RenderBlock* child)
1043 {
1044     // It's possible that this block's destruction may have been triggered by the
1045     // child's removal. Just bail if the anonymous child block is already being
1046     // destroyed. See crbug.com/282088
1047     if (child->beingDestroyed())
1048         return;
1049     parent->setNeedsLayoutAndPrefWidthsRecalc();
1050     parent->setChildrenInline(child->childrenInline());
1051     RenderObject* nextSibling = child->nextSibling();
1052
1053     RenderFlowThread* childFlowThread = child->flowThreadContainingBlock();
1054     CurrentRenderFlowThreadMaintainer flowThreadMaintainer(childFlowThread);
1055
1056     parent->children()->removeChildNode(parent, child, child->hasLayer());
1057     child->moveAllChildrenTo(parent, nextSibling, child->hasLayer());
1058     // Explicitly delete the child's line box tree, or the special anonymous
1059     // block handling in willBeDestroyed will cause problems.
1060     child->deleteLineBoxTree();
1061     child->destroy();
1062 }
1063
1064 void RenderBlock::removeChild(RenderObject* oldChild)
1065 {
1066     // No need to waste time in merging or removing empty anonymous blocks.
1067     // We can just bail out if our document is getting destroyed.
1068     if (documentBeingDestroyed()) {
1069         RenderBox::removeChild(oldChild);
1070         return;
1071     }
1072
1073     // This protects against column split flows when anonymous blocks are getting merged.
1074     TemporaryChange<bool> columnFlowSplitEnabled(gColumnFlowSplitEnabled, false);
1075
1076     // If this child is a block, and if our previous and next siblings are
1077     // both anonymous blocks with inline content, then we can go ahead and
1078     // fold the inline content back together.
1079     RenderObject* prev = oldChild->previousSibling();
1080     RenderObject* next = oldChild->nextSibling();
1081     bool canMergeAnonymousBlocks = canMergeContiguousAnonymousBlocks(oldChild, prev, next);
1082     if (canMergeAnonymousBlocks && prev && next) {
1083         prev->setNeedsLayoutAndPrefWidthsRecalc();
1084         RenderBlockFlow* nextBlock = toRenderBlockFlow(next);
1085         RenderBlockFlow* prevBlock = toRenderBlockFlow(prev);
1086
1087         if (prev->childrenInline() != next->childrenInline()) {
1088             RenderBlock* inlineChildrenBlock = prev->childrenInline() ? prevBlock : nextBlock;
1089             RenderBlock* blockChildrenBlock = prev->childrenInline() ? nextBlock : prevBlock;
1090
1091             // Place the inline children block inside of the block children block instead of deleting it.
1092             // In order to reuse it, we have to reset it to just be a generic anonymous block.  Make sure
1093             // to clear out inherited column properties by just making a new style, and to also clear the
1094             // column span flag if it is set.
1095             ASSERT(!inlineChildrenBlock->continuation());
1096             RefPtr<RenderStyle> newStyle = RenderStyle::createAnonymousStyleWithDisplay(style(), BLOCK);
1097             // Cache this value as it might get changed in setStyle() call.
1098             bool inlineChildrenBlockHasLayer = inlineChildrenBlock->hasLayer();
1099             inlineChildrenBlock->setStyle(newStyle);
1100             children()->removeChildNode(this, inlineChildrenBlock, inlineChildrenBlockHasLayer);
1101
1102             // Now just put the inlineChildrenBlock inside the blockChildrenBlock.
1103             blockChildrenBlock->children()->insertChildNode(blockChildrenBlock, inlineChildrenBlock, prev == inlineChildrenBlock ? blockChildrenBlock->firstChild() : 0,
1104                                                             inlineChildrenBlockHasLayer || blockChildrenBlock->hasLayer());
1105             next->setNeedsLayoutAndPrefWidthsRecalc();
1106
1107             // inlineChildrenBlock got reparented to blockChildrenBlock, so it is no longer a child
1108             // of "this". we null out prev or next so that is not used later in the function.
1109             if (inlineChildrenBlock == prevBlock)
1110                 prev = 0;
1111             else
1112                 next = 0;
1113         } else {
1114             // Take all the children out of the |next| block and put them in
1115             // the |prev| block.
1116             nextBlock->moveAllChildrenIncludingFloatsTo(prevBlock, nextBlock->hasLayer() || prevBlock->hasLayer());
1117
1118             // Delete the now-empty block's lines and nuke it.
1119             nextBlock->deleteLineBoxTree();
1120             nextBlock->destroy();
1121             next = 0;
1122         }
1123     }
1124
1125     RenderBox::removeChild(oldChild);
1126
1127     RenderObject* child = prev ? prev : next;
1128     if (canMergeAnonymousBlocks && child && !child->previousSibling() && !child->nextSibling() && canCollapseAnonymousBlockChild()) {
1129         // The removal has knocked us down to containing only a single anonymous
1130         // box.  We can go ahead and pull the content right back up into our
1131         // box.
1132         collapseAnonymousBlockChild(this, toRenderBlock(child));
1133     } else if (((prev && prev->isAnonymousBlock()) || (next && next->isAnonymousBlock())) && canCollapseAnonymousBlockChild()) {
1134         // It's possible that the removal has knocked us down to a single anonymous
1135         // block with pseudo-style element siblings (e.g. first-letter). If these
1136         // are floating, then we need to pull the content up also.
1137         RenderBlock* anonymousBlock = toRenderBlock((prev && prev->isAnonymousBlock()) ? prev : next);
1138         if ((anonymousBlock->previousSibling() || anonymousBlock->nextSibling())
1139             && (!anonymousBlock->previousSibling() || (anonymousBlock->previousSibling()->style()->styleType() != NOPSEUDO && anonymousBlock->previousSibling()->isFloating() && !anonymousBlock->previousSibling()->previousSibling()))
1140             && (!anonymousBlock->nextSibling() || (anonymousBlock->nextSibling()->style()->styleType() != NOPSEUDO && anonymousBlock->nextSibling()->isFloating() && !anonymousBlock->nextSibling()->nextSibling()))) {
1141             collapseAnonymousBlockChild(this, anonymousBlock);
1142         }
1143     }
1144
1145     if (!firstChild()) {
1146         // If this was our last child be sure to clear out our line boxes.
1147         if (childrenInline())
1148             deleteLineBoxTree();
1149
1150         // If we are an empty anonymous block in the continuation chain,
1151         // we need to remove ourself and fix the continuation chain.
1152         if (!beingDestroyed() && isAnonymousBlockContinuation() && !oldChild->isListMarker()) {
1153             RenderObject* containingBlockIgnoringAnonymous = containingBlock();
1154             while (containingBlockIgnoringAnonymous && containingBlockIgnoringAnonymous->isAnonymousBlock())
1155                 containingBlockIgnoringAnonymous = containingBlockIgnoringAnonymous->containingBlock();
1156             for (RenderObject* curr = this; curr; curr = curr->previousInPreOrder(containingBlockIgnoringAnonymous)) {
1157                 if (curr->virtualContinuation() != this)
1158                     continue;
1159
1160                 // Found our previous continuation. We just need to point it to
1161                 // |this|'s next continuation.
1162                 RenderBoxModelObject* nextContinuation = continuation();
1163                 if (curr->isRenderInline())
1164                     toRenderInline(curr)->setContinuation(nextContinuation);
1165                 else if (curr->isRenderBlock())
1166                     toRenderBlock(curr)->setContinuation(nextContinuation);
1167                 else
1168                     ASSERT_NOT_REACHED();
1169
1170                 break;
1171             }
1172             setContinuation(0);
1173             destroy();
1174         }
1175     }
1176 }
1177
1178 bool RenderBlock::isSelfCollapsingBlock() const
1179 {
1180     // Placeholder elements are not laid out until the dimensions of their parent text control are known, so they
1181     // don't get layout until their parent has had layout - this is unique in the layout tree and means
1182     // when we call isSelfCollapsingBlock on them we find that they still need layout.
1183     ASSERT(!needsLayout() || (node() && node()->isElementNode() && toElement(node())->shadowPseudoId() == "-webkit-input-placeholder"));
1184
1185     // We are not self-collapsing if we
1186     // (a) have a non-zero height according to layout (an optimization to avoid wasting time)
1187     // (b) are a table,
1188     // (c) have border/padding,
1189     // (d) have a min-height
1190     // (e) have specified that one of our margins can't collapse using a CSS extension
1191     // (f) establish a new block formatting context.
1192
1193     if (createsBlockFormattingContext())
1194         return false;
1195
1196     if (logicalHeight() > 0
1197         || isTable() || borderAndPaddingLogicalHeight()
1198         || style()->logicalMinHeight().isPositive()
1199         || style()->marginBeforeCollapse() == MSEPARATE || style()->marginAfterCollapse() == MSEPARATE)
1200         return false;
1201
1202     Length logicalHeightLength = style()->logicalHeight();
1203     bool hasAutoHeight = logicalHeightLength.isAuto();
1204     if (logicalHeightLength.isPercent() && !document().inQuirksMode()) {
1205         hasAutoHeight = true;
1206         for (RenderBlock* cb = containingBlock(); !cb->isRenderView(); cb = cb->containingBlock()) {
1207             if (cb->style()->logicalHeight().isFixed() || cb->isTableCell())
1208                 hasAutoHeight = false;
1209         }
1210     }
1211
1212     // If the height is 0 or auto, then whether or not we are a self-collapsing block depends
1213     // on whether we have content that is all self-collapsing or not.
1214     if (hasAutoHeight || ((logicalHeightLength.isFixed() || logicalHeightLength.isPercent()) && logicalHeightLength.isZero())) {
1215         // If the block has inline children, see if we generated any line boxes.  If we have any
1216         // line boxes, then we can't be self-collapsing, since we have content.
1217         if (childrenInline())
1218             return !firstLineBox();
1219
1220         // Whether or not we collapse is dependent on whether all our normal flow children
1221         // are also self-collapsing.
1222         if (m_hasOnlySelfCollapsingChildren)
1223             return true;
1224         for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
1225             if (child->isFloatingOrOutOfFlowPositioned())
1226                 continue;
1227             if (!child->isSelfCollapsingBlock())
1228                 return false;
1229         }
1230         return true;
1231     }
1232     return false;
1233 }
1234
1235 void RenderBlock::startDelayUpdateScrollInfo()
1236 {
1237     if (gDelayUpdateScrollInfo == 0) {
1238         ASSERT(!gDelayedUpdateScrollInfoSet);
1239         gDelayedUpdateScrollInfoSet = new DelayedUpdateScrollInfoSet;
1240     }
1241     ASSERT(gDelayedUpdateScrollInfoSet);
1242     ++gDelayUpdateScrollInfo;
1243 }
1244
1245 void RenderBlock::finishDelayUpdateScrollInfo()
1246 {
1247     --gDelayUpdateScrollInfo;
1248     ASSERT(gDelayUpdateScrollInfo >= 0);
1249     if (gDelayUpdateScrollInfo == 0) {
1250         ASSERT(gDelayedUpdateScrollInfoSet);
1251
1252         OwnPtr<DelayedUpdateScrollInfoSet> infoSet(adoptPtr(gDelayedUpdateScrollInfoSet));
1253         gDelayedUpdateScrollInfoSet = 0;
1254
1255         for (DelayedUpdateScrollInfoSet::iterator it = infoSet->begin(); it != infoSet->end(); ++it) {
1256             RenderBlock* block = *it;
1257             if (block->hasOverflowClip()) {
1258                 block->layer()->scrollableArea()->updateAfterLayout();
1259             }
1260         }
1261     }
1262 }
1263
1264 void RenderBlock::updateScrollInfoAfterLayout()
1265 {
1266     if (hasOverflowClip()) {
1267         if (style()->isFlippedBlocksWritingMode()) {
1268             // FIXME: https://bugs.webkit.org/show_bug.cgi?id=97937
1269             // Workaround for now. We cannot delay the scroll info for overflow
1270             // for items with opposite writing directions, as the contents needs
1271             // to overflow in that direction
1272             layer()->scrollableArea()->updateAfterLayout();
1273             return;
1274         }
1275
1276         if (gDelayUpdateScrollInfo)
1277             gDelayedUpdateScrollInfoSet->add(this);
1278         else
1279             layer()->scrollableArea()->updateAfterLayout();
1280     }
1281 }
1282
1283 void RenderBlock::layout()
1284 {
1285     OverflowEventDispatcher dispatcher(this);
1286     LayoutRectRecorder recorder(*this);
1287
1288     // Update our first letter info now.
1289     updateFirstLetter();
1290
1291     // Table cells call layoutBlock directly, so don't add any logic here.  Put code into
1292     // layoutBlock().
1293     layoutBlock(false);
1294
1295     if (frameView()->partialLayout().isStopping())
1296         return;
1297
1298     // It's safe to check for control clip here, since controls can never be table cells.
1299     // If we have a lightweight clip, there can never be any overflow from children.
1300     if (hasControlClip() && m_overflow)
1301         clearLayoutOverflow();
1302
1303     invalidateBackgroundObscurationStatus();
1304 }
1305
1306 bool RenderBlock::updateImageLoadingPriorities()
1307 {
1308     Vector<ImageResource*> images;
1309     appendImagesFromStyle(images, *style());
1310
1311     if (images.isEmpty())
1312         return false;
1313
1314     LayoutRect viewBounds = viewRect();
1315     LayoutRect objectBounds = absoluteContentBox();
1316     // The object bounds might be empty right now, so intersects will fail since it doesn't deal
1317     // with empty rects. Use LayoutRect::contains in that case.
1318     bool isVisible;
1319     if (!objectBounds.isEmpty())
1320         isVisible =  viewBounds.intersects(objectBounds);
1321     else
1322         isVisible = viewBounds.contains(objectBounds);
1323
1324     ResourceLoadPriorityOptimizer::VisibilityStatus status = isVisible ?
1325         ResourceLoadPriorityOptimizer::Visible : ResourceLoadPriorityOptimizer::NotVisible;
1326
1327     for (Vector<ImageResource*>::iterator it = images.begin(), end = images.end(); it != end; ++it)
1328         ResourceLoadPriorityOptimizer::resourceLoadPriorityOptimizer()->notifyImageResourceVisibility(*it, status);
1329
1330     return true;
1331 }
1332
1333 void RenderBlock::relayoutShapeDescendantIfMoved(RenderBlock* child, LayoutSize offset)
1334 {
1335     LayoutUnit left = isHorizontalWritingMode() ? offset.width() : offset.height();
1336     if (!left || !child || child->shapeInsideInfo() || !layoutShapeInsideInfo())
1337         return;
1338     // Propagate layout markers only up to the child, as we are still in the middle
1339     // of a layout pass
1340     child->setNormalChildNeedsLayout(true);
1341     child->markShapeInsideDescendantsForLayout();
1342     child->layoutIfNeeded();
1343 }
1344
1345 ShapeInsideInfo* RenderBlock::layoutShapeInsideInfo() const
1346 {
1347     if (ShapeInsideInfo* shapeInsideInfo = view()->layoutState()->shapeInsideInfo())
1348         return shapeInsideInfo;
1349
1350     RenderFlowThread* flowThread = flowThreadContainingBlock();
1351     if (allowsShapeInsideInfoSharing(flowThread)) {
1352         LayoutUnit lineHeight = this->lineHeight(false, isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes);
1353         // regionAtBlockOffset returns regions like an array first={0,N-1}, second={N,M-1}, ...
1354         LayoutUnit offset = logicalHeight() + lineHeight - LayoutUnit(1);
1355         RenderRegion* region = regionAtBlockOffset(offset);
1356         if (region && region->logicalHeight())
1357             return region->shapeInsideInfo();
1358     }
1359
1360     return 0;
1361 }
1362
1363 LayoutSize RenderBlock::logicalOffsetFromShapeAncestorContainer(const RenderBlock* container) const
1364 {
1365     const RenderBlock* currentBlock = this;
1366     LayoutRect blockRect(currentBlock->borderBoxRect());
1367     while (currentBlock && !currentBlock->isRenderFlowThread() && currentBlock != container) {
1368         RenderBlock* containerBlock = currentBlock->containingBlock();
1369         ASSERT(containerBlock);
1370         if (!containerBlock)
1371             return LayoutSize();
1372
1373         if (containerBlock->style()->writingMode() != currentBlock->style()->writingMode()) {
1374             // We have to put the block rect in container coordinates
1375             // and we have to take into account both the container and current block flipping modes
1376             // Bug: Flipping inline and block directions at the same time will not work,
1377             // as one of the flipped dimensions will not yet have been set to its final size
1378             if (containerBlock->style()->isFlippedBlocksWritingMode()) {
1379                 if (containerBlock->isHorizontalWritingMode())
1380                     blockRect.setY(currentBlock->height() - blockRect.maxY());
1381                 else
1382                     blockRect.setX(currentBlock->width() - blockRect.maxX());
1383             }
1384             currentBlock->flipForWritingMode(blockRect);
1385         }
1386
1387         blockRect.moveBy(currentBlock->location());
1388         currentBlock = containerBlock;
1389     }
1390
1391     LayoutSize result = isHorizontalWritingMode() ? LayoutSize(blockRect.x(), blockRect.y()) : LayoutSize(blockRect.y(), blockRect.x());
1392     return result;
1393 }
1394
1395 void RenderBlock::imageChanged(WrappedImagePtr image, const IntRect*)
1396 {
1397     RenderBox::imageChanged(image);
1398
1399     if (!parent() || !everHadLayout())
1400         return;
1401
1402     ShapeValue* shapeValue = style()->shapeInside();
1403     if (shapeValue && shapeValue->image() && shapeValue->image()->data() == image) {
1404         ShapeInsideInfo* shapeInsideInfo = ensureShapeInsideInfo();
1405         shapeInsideInfo->dirtyShapeSize();
1406         markShapeInsideDescendantsForLayout();
1407     }
1408 }
1409
1410 void RenderBlock::updateShapeInsideInfoAfterStyleChange(const ShapeValue* shapeInside, const ShapeValue* oldShapeInside)
1411 {
1412     // FIXME: A future optimization would do a deep comparison for equality.
1413     if (shapeInside == oldShapeInside)
1414         return;
1415
1416     if (shapeInside) {
1417         ShapeInsideInfo* shapeInsideInfo = ensureShapeInsideInfo();
1418         shapeInsideInfo->dirtyShapeSize();
1419     } else {
1420         setShapeInsideInfo(nullptr);
1421         markShapeInsideDescendantsForLayout();
1422     }
1423 }
1424
1425 static inline bool shapeInfoRequiresRelayout(const RenderBlock* block)
1426 {
1427     ShapeInsideInfo* info = block->shapeInsideInfo();
1428     if (info)
1429         info->setNeedsLayout(info->shapeSizeDirty());
1430     else
1431         info = block->layoutShapeInsideInfo();
1432     return info && info->needsLayout();
1433 }
1434
1435 bool RenderBlock::updateRegionsAndShapesLogicalSize(RenderFlowThread* flowThread)
1436 {
1437     if (!flowThread && !shapeInsideInfo())
1438         return shapeInfoRequiresRelayout(this);
1439
1440     LayoutUnit oldHeight = logicalHeight();
1441     LayoutUnit oldTop = logicalTop();
1442
1443     // Compute the maximum logical height content may cause this block to expand to
1444     // FIXME: These should eventually use the const computeLogicalHeight rather than updateLogicalHeight
1445     setLogicalHeight(RenderFlowThread::maxLogicalHeight());
1446     updateLogicalHeight();
1447
1448     computeShapeSize();
1449
1450     // Set our start and end regions. No regions above or below us will be considered by our children. They are
1451     // effectively clamped to our region range.
1452     computeRegionRangeForBlock(flowThread);
1453
1454     setLogicalHeight(oldHeight);
1455     setLogicalTop(oldTop);
1456
1457     return shapeInfoRequiresRelayout(this);
1458 }
1459
1460 void RenderBlock::computeShapeSize()
1461 {
1462     ShapeInsideInfo* shapeInsideInfo = this->shapeInsideInfo();
1463     if (!shapeInsideInfo)
1464         return;
1465
1466     bool percentageLogicalHeightResolvable = percentageLogicalHeightIsResolvableFromBlock(this, false);
1467     shapeInsideInfo->setShapeSize(logicalWidth(), percentageLogicalHeightResolvable ? logicalHeight() : LayoutUnit());
1468 }
1469
1470 void RenderBlock::updateRegionsAndShapesAfterChildLayout(RenderFlowThread* flowThread, bool heightChanged)
1471 {
1472     // A previous sibling has changed dimension, so we need to relayout the shape with the content
1473     ShapeInsideInfo* shapeInsideInfo = layoutShapeInsideInfo();
1474     if (heightChanged && shapeInsideInfo)
1475         shapeInsideInfo->dirtyShapeSize();
1476
1477     computeRegionRangeForBlock(flowThread);
1478 }
1479
1480 void RenderBlock::computeRegionRangeForBlock(RenderFlowThread* flowThread)
1481 {
1482     if (flowThread)
1483         flowThread->setRegionRangeForBox(this, offsetFromLogicalTopOfFirstPage());
1484 }
1485
1486 bool RenderBlock::updateLogicalWidthAndColumnWidth()
1487 {
1488     LayoutUnit oldWidth = logicalWidth();
1489     LayoutUnit oldColumnWidth = desiredColumnWidth();
1490
1491     updateLogicalWidth();
1492     calcColumnWidth();
1493
1494     bool hasBorderOrPaddingLogicalWidthChanged = m_hasBorderOrPaddingLogicalWidthChanged;
1495     m_hasBorderOrPaddingLogicalWidthChanged = false;
1496
1497     return oldWidth != logicalWidth() || oldColumnWidth != desiredColumnWidth() || hasBorderOrPaddingLogicalWidthChanged;
1498 }
1499
1500 void RenderBlock::layoutBlock(bool)
1501 {
1502     ASSERT_NOT_REACHED();
1503     clearNeedsLayout();
1504 }
1505
1506 void RenderBlock::addOverflowFromChildren()
1507 {
1508     if (!hasColumns()) {
1509         if (childrenInline())
1510             toRenderBlockFlow(this)->addOverflowFromInlineChildren();
1511         else
1512             addOverflowFromBlockChildren();
1513     } else {
1514         ColumnInfo* colInfo = columnInfo();
1515         if (columnCount(colInfo)) {
1516             LayoutRect lastRect = columnRectAt(colInfo, columnCount(colInfo) - 1);
1517             addLayoutOverflow(lastRect);
1518             addContentsVisualOverflow(lastRect);
1519         }
1520     }
1521 }
1522
1523 void RenderBlock::computeOverflow(LayoutUnit oldClientAfterEdge, bool)
1524 {
1525     m_overflow.clear();
1526
1527     // Add overflow from children.
1528     addOverflowFromChildren();
1529
1530     // Add in the overflow from positioned objects.
1531     addOverflowFromPositionedObjects();
1532
1533     if (hasOverflowClip()) {
1534         // When we have overflow clip, propagate the original spillout since it will include collapsed bottom margins
1535         // and bottom padding.  Set the axis we don't care about to be 1, since we want this overflow to always
1536         // be considered reachable.
1537         LayoutRect clientRect(noOverflowRect());
1538         LayoutRect rectToApply;
1539         if (isHorizontalWritingMode())
1540             rectToApply = LayoutRect(clientRect.x(), clientRect.y(), 1, max<LayoutUnit>(0, oldClientAfterEdge - clientRect.y()));
1541         else
1542             rectToApply = LayoutRect(clientRect.x(), clientRect.y(), max<LayoutUnit>(0, oldClientAfterEdge - clientRect.x()), 1);
1543         addLayoutOverflow(rectToApply);
1544         if (hasRenderOverflow())
1545             m_overflow->setLayoutClientAfterEdge(oldClientAfterEdge);
1546     }
1547
1548     // Add visual overflow from box-shadow and border-image-outset.
1549     addVisualEffectOverflow();
1550
1551     // Add visual overflow from theme.
1552     addVisualOverflowFromTheme();
1553 }
1554
1555 void RenderBlock::addOverflowFromBlockChildren()
1556 {
1557     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
1558         if (!child->isFloatingOrOutOfFlowPositioned())
1559             addOverflowFromChild(child);
1560     }
1561 }
1562
1563 void RenderBlock::addOverflowFromPositionedObjects()
1564 {
1565     TrackedRendererListHashSet* positionedDescendants = positionedObjects();
1566     if (!positionedDescendants)
1567         return;
1568
1569     RenderBox* positionedObject;
1570     TrackedRendererListHashSet::iterator end = positionedDescendants->end();
1571     for (TrackedRendererListHashSet::iterator it = positionedDescendants->begin(); it != end; ++it) {
1572         positionedObject = *it;
1573
1574         // Fixed positioned elements don't contribute to layout overflow, since they don't scroll with the content.
1575         if (positionedObject->style()->position() != FixedPosition)
1576             addOverflowFromChild(positionedObject, LayoutSize(positionedObject->x(), positionedObject->y()));
1577     }
1578 }
1579
1580 void RenderBlock::addVisualOverflowFromTheme()
1581 {
1582     if (!style()->hasAppearance())
1583         return;
1584
1585     IntRect inflatedRect = pixelSnappedBorderBoxRect();
1586     RenderTheme::theme().adjustRepaintRect(this, inflatedRect);
1587     addVisualOverflow(inflatedRect);
1588 }
1589
1590 bool RenderBlock::createsBlockFormattingContext() const
1591 {
1592     return isInlineBlockOrInlineTable() || isFloatingOrOutOfFlowPositioned() || hasOverflowClip() || (parent() && parent()->isFlexibleBoxIncludingDeprecated())
1593         || style()->specifiesColumns() || isTableCell() || isTableCaption() || isFieldset() || isWritingModeRoot() || isRoot() || style()->columnSpan();
1594 }
1595
1596 void RenderBlock::determineLogicalLeftPositionForChild(RenderBox* child, ApplyLayoutDeltaMode applyDelta)
1597 {
1598     LayoutUnit startPosition = borderStart() + paddingStart();
1599     if (style()->shouldPlaceBlockDirectionScrollbarOnLogicalLeft())
1600         startPosition -= verticalScrollbarWidth();
1601     LayoutUnit totalAvailableLogicalWidth = borderAndPaddingLogicalWidth() + availableLogicalWidth();
1602
1603     // Add in our start margin.
1604     LayoutUnit childMarginStart = marginStartForChild(child);
1605     LayoutUnit newPosition = startPosition + childMarginStart;
1606
1607     // Some objects (e.g., tables, horizontal rules, overflow:auto blocks) avoid floats.  They need
1608     // to shift over as necessary to dodge any floats that might get in the way.
1609     if (child->avoidsFloats() && containsFloats() && !flowThreadContainingBlock())
1610         newPosition += toRenderBlockFlow(this)->computeStartPositionDeltaForChildAvoidingFloats(child, marginStartForChild(child));
1611
1612     setLogicalLeftForChild(child, style()->isLeftToRightDirection() ? newPosition : totalAvailableLogicalWidth - newPosition - logicalWidthForChild(child), applyDelta);
1613 }
1614
1615 void RenderBlock::setLogicalLeftForChild(RenderBox* child, LayoutUnit logicalLeft, ApplyLayoutDeltaMode applyDelta)
1616 {
1617     if (isHorizontalWritingMode()) {
1618         if (applyDelta == ApplyLayoutDelta && !RuntimeEnabledFeatures::repaintAfterLayoutEnabled())
1619             view()->addLayoutDelta(LayoutSize(child->x() - logicalLeft, 0));
1620         child->setX(logicalLeft);
1621     } else {
1622         if (applyDelta == ApplyLayoutDelta && !RuntimeEnabledFeatures::repaintAfterLayoutEnabled())
1623             view()->addLayoutDelta(LayoutSize(0, child->y() - logicalLeft));
1624         child->setY(logicalLeft);
1625     }
1626 }
1627
1628 void RenderBlock::setLogicalTopForChild(RenderBox* child, LayoutUnit logicalTop, ApplyLayoutDeltaMode applyDelta)
1629 {
1630     if (isHorizontalWritingMode()) {
1631         if (applyDelta == ApplyLayoutDelta && !RuntimeEnabledFeatures::repaintAfterLayoutEnabled())
1632             view()->addLayoutDelta(LayoutSize(0, child->y() - logicalTop));
1633         child->setY(logicalTop);
1634     } else {
1635         if (applyDelta == ApplyLayoutDelta && !RuntimeEnabledFeatures::repaintAfterLayoutEnabled())
1636             view()->addLayoutDelta(LayoutSize(child->x() - logicalTop, 0));
1637         child->setX(logicalTop);
1638     }
1639 }
1640
1641 void RenderBlock::updateBlockChildDirtyBitsBeforeLayout(bool relayoutChildren, RenderBox* child)
1642 {
1643     // FIXME: Technically percentage height objects only need a relayout if their percentage isn't going to be turned into
1644     // an auto value. Add a method to determine this, so that we can avoid the relayout.
1645     if (relayoutChildren || (child->hasRelativeLogicalHeight() && !isRenderView()))
1646         child->setChildNeedsLayout(MarkOnlyThis);
1647
1648     // If relayoutChildren is set and the child has percentage padding or an embedded content box, we also need to invalidate the childs pref widths.
1649     if (relayoutChildren && child->needsPreferredWidthsRecalculation())
1650         child->setPreferredLogicalWidthsDirty(MarkOnlyThis);
1651 }
1652
1653 void RenderBlock::simplifiedNormalFlowLayout()
1654 {
1655     if (childrenInline()) {
1656         ListHashSet<RootInlineBox*> lineBoxes;
1657         for (InlineWalker walker(this); !walker.atEnd(); walker.advance()) {
1658             RenderObject* o = walker.current();
1659             if (!o->isOutOfFlowPositioned() && (o->isReplaced() || o->isFloating())) {
1660                 o->layoutIfNeeded();
1661                 if (toRenderBox(o)->inlineBoxWrapper()) {
1662                     RootInlineBox* box = toRenderBox(o)->inlineBoxWrapper()->root();
1663                     lineBoxes.add(box);
1664                 }
1665             } else if (o->isText() || (o->isRenderInline() && !walker.atEndOfInline())) {
1666                 o->clearNeedsLayout();
1667             }
1668         }
1669
1670         // FIXME: Glyph overflow will get lost in this case, but not really a big deal.
1671         GlyphOverflowAndFallbackFontsMap textBoxDataMap;
1672         for (ListHashSet<RootInlineBox*>::const_iterator it = lineBoxes.begin(); it != lineBoxes.end(); ++it) {
1673             RootInlineBox* box = *it;
1674             box->computeOverflow(box->lineTop(), box->lineBottom(), textBoxDataMap);
1675         }
1676     } else {
1677         for (RenderBox* box = firstChildBox(); box; box = box->nextSiblingBox()) {
1678             if (!box->isOutOfFlowPositioned())
1679                 box->layoutIfNeeded();
1680         }
1681     }
1682 }
1683
1684 bool RenderBlock::simplifiedLayout()
1685 {
1686     if ((!posChildNeedsLayout() && !needsSimplifiedNormalFlowLayout()) || normalChildNeedsLayout() || selfNeedsLayout())
1687         return false;
1688
1689     LayoutStateMaintainer statePusher(view(), this, locationOffset(), hasColumns() || hasTransform() || hasReflection() || style()->isFlippedBlocksWritingMode());
1690
1691     if (needsPositionedMovementLayout() && !tryLayoutDoingPositionedMovementOnly())
1692         return false;
1693
1694     FastTextAutosizer::LayoutScope fastTextAutosizerLayoutScope(document(), this);
1695
1696     // Lay out positioned descendants or objects that just need to recompute overflow.
1697     if (needsSimplifiedNormalFlowLayout())
1698         simplifiedNormalFlowLayout();
1699
1700     // Make sure a forced break is applied after the content if we are a flow thread in a simplified layout.
1701     // This ensures the size information is correctly computed for the last auto-height region receiving content.
1702     if (isRenderFlowThread())
1703         toRenderFlowThread(this)->applyBreakAfterContent(clientLogicalBottom());
1704
1705     // Lay out our positioned objects if our positioned child bit is set.
1706     // Also, if an absolute position element inside a relative positioned container moves, and the absolute element has a fixed position
1707     // child, neither the fixed element nor its container learn of the movement since posChildNeedsLayout() is only marked as far as the
1708     // relative positioned container. So if we can have fixed pos objects in our positioned objects list check if any of them
1709     // are statically positioned and thus need to move with their absolute ancestors.
1710     bool canContainFixedPosObjects = canContainFixedPositionObjects();
1711     if (posChildNeedsLayout() || canContainFixedPosObjects)
1712         layoutPositionedObjects(false, !posChildNeedsLayout() && canContainFixedPosObjects);
1713
1714     // Recompute our overflow information.
1715     // FIXME: We could do better here by computing a temporary overflow object from layoutPositionedObjects and only
1716     // updating our overflow if we either used to have overflow or if the new temporary object has overflow.
1717     // For now just always recompute overflow.  This is no worse performance-wise than the old code that called rightmostPosition and
1718     // lowestPosition on every relayout so it's not a regression.
1719     // computeOverflow expects the bottom edge before we clamp our height. Since this information isn't available during
1720     // simplifiedLayout, we cache the value in m_overflow.
1721     LayoutUnit oldClientAfterEdge = hasRenderOverflow() ? m_overflow->layoutClientAfterEdge() : clientLogicalBottom();
1722     computeOverflow(oldClientAfterEdge, true);
1723
1724     statePusher.pop();
1725
1726     updateLayerTransform();
1727
1728     updateScrollInfoAfterLayout();
1729
1730     clearNeedsLayout();
1731     return true;
1732 }
1733
1734 void RenderBlock::markFixedPositionObjectForLayoutIfNeeded(RenderObject* child, SubtreeLayoutScope& layoutScope)
1735 {
1736     if (child->style()->position() != FixedPosition)
1737         return;
1738
1739     bool hasStaticBlockPosition = child->style()->hasStaticBlockPosition(isHorizontalWritingMode());
1740     bool hasStaticInlinePosition = child->style()->hasStaticInlinePosition(isHorizontalWritingMode());
1741     if (!hasStaticBlockPosition && !hasStaticInlinePosition)
1742         return;
1743
1744     RenderObject* o = child->parent();
1745     while (o && !o->isRenderView() && o->style()->position() != AbsolutePosition)
1746         o = o->parent();
1747     if (o->style()->position() != AbsolutePosition)
1748         return;
1749
1750     RenderBox* box = toRenderBox(child);
1751     if (hasStaticInlinePosition) {
1752         LogicalExtentComputedValues computedValues;
1753         box->computeLogicalWidth(computedValues);
1754         LayoutUnit newLeft = computedValues.m_position;
1755         if (newLeft != box->logicalLeft())
1756             layoutScope.setChildNeedsLayout(child);
1757     } else if (hasStaticBlockPosition) {
1758         LayoutUnit oldTop = box->logicalTop();
1759         box->updateLogicalHeight();
1760         if (box->logicalTop() != oldTop)
1761             layoutScope.setChildNeedsLayout(child);
1762     }
1763 }
1764
1765 LayoutUnit RenderBlock::marginIntrinsicLogicalWidthForChild(RenderBox* child) const
1766 {
1767     // A margin has three types: fixed, percentage, and auto (variable).
1768     // Auto and percentage margins become 0 when computing min/max width.
1769     // Fixed margins can be added in as is.
1770     Length marginLeft = child->style()->marginStartUsing(style());
1771     Length marginRight = child->style()->marginEndUsing(style());
1772     LayoutUnit margin = 0;
1773     if (marginLeft.isFixed())
1774         margin += marginLeft.value();
1775     if (marginRight.isFixed())
1776         margin += marginRight.value();
1777     return margin;
1778 }
1779
1780 void RenderBlock::layoutPositionedObjects(bool relayoutChildren, bool fixedPositionObjectsOnly)
1781 {
1782     TrackedRendererListHashSet* positionedDescendants = positionedObjects();
1783     if (!positionedDescendants)
1784         return;
1785
1786     if (hasColumns())
1787         view()->layoutState()->clearPaginationInformation(); // Positioned objects are not part of the column flow, so they don't paginate with the columns.
1788
1789     RenderBox* r;
1790     TrackedRendererListHashSet::iterator end = positionedDescendants->end();
1791     for (TrackedRendererListHashSet::iterator it = positionedDescendants->begin(); it != end; ++it) {
1792         r = *it;
1793
1794         SubtreeLayoutScope layoutScope(r);
1795         // A fixed position element with an absolute positioned ancestor has no way of knowing if the latter has changed position. So
1796         // if this is a fixed position element, mark it for layout if it has an abspos ancestor and needs to move with that ancestor, i.e.
1797         // it has static position.
1798         markFixedPositionObjectForLayoutIfNeeded(r, layoutScope);
1799         if (fixedPositionObjectsOnly) {
1800             r->layoutIfNeeded();
1801             continue;
1802         }
1803
1804         // When a non-positioned block element moves, it may have positioned children that are implicitly positioned relative to the
1805         // non-positioned block.  Rather than trying to detect all of these movement cases, we just always lay out positioned
1806         // objects that are positioned implicitly like this.  Such objects are rare, and so in typical DHTML menu usage (where everything is
1807         // positioned explicitly) this should not incur a performance penalty.
1808         if (relayoutChildren || (r->style()->hasStaticBlockPosition(isHorizontalWritingMode()) && r->parent() != this))
1809             layoutScope.setChildNeedsLayout(r);
1810
1811         // If relayoutChildren is set and the child has percentage padding or an embedded content box, we also need to invalidate the childs pref widths.
1812         if (relayoutChildren && r->needsPreferredWidthsRecalculation())
1813             r->setPreferredLogicalWidthsDirty(MarkOnlyThis);
1814
1815         if (!r->needsLayout())
1816             r->markForPaginationRelayoutIfNeeded(layoutScope);
1817
1818         // We don't have to do a full layout.  We just have to update our position. Try that first. If we have shrink-to-fit width
1819         // and we hit the available width constraint, the layoutIfNeeded() will catch it and do a full layout.
1820         if (r->needsPositionedMovementLayoutOnly() && r->tryLayoutDoingPositionedMovementOnly())
1821             r->clearNeedsLayout();
1822
1823         // If we are paginated or in a line grid, go ahead and compute a vertical position for our object now.
1824         // If it's wrong we'll lay out again.
1825         LayoutUnit oldLogicalTop = 0;
1826         bool needsBlockDirectionLocationSetBeforeLayout = r->needsLayout() && view()->layoutState()->needsBlockDirectionLocationSetBeforeLayout();
1827         if (needsBlockDirectionLocationSetBeforeLayout) {
1828             if (isHorizontalWritingMode() == r->isHorizontalWritingMode())
1829                 r->updateLogicalHeight();
1830             else
1831                 r->updateLogicalWidth();
1832             oldLogicalTop = logicalTopForChild(r);
1833         }
1834
1835         r->layoutIfNeeded();
1836
1837         // Lay out again if our estimate was wrong.
1838         if (needsBlockDirectionLocationSetBeforeLayout && logicalTopForChild(r) != oldLogicalTop)
1839             r->forceChildLayout();
1840     }
1841
1842     if (hasColumns())
1843         view()->layoutState()->m_columnInfo = columnInfo(); // FIXME: Kind of gross. We just put this back into the layout state so that pop() will work.
1844 }
1845
1846 void RenderBlock::markPositionedObjectsForLayout()
1847 {
1848     TrackedRendererListHashSet* positionedDescendants = positionedObjects();
1849     if (positionedDescendants) {
1850         RenderBox* r;
1851         TrackedRendererListHashSet::iterator end = positionedDescendants->end();
1852         for (TrackedRendererListHashSet::iterator it = positionedDescendants->begin(); it != end; ++it) {
1853             r = *it;
1854             r->setChildNeedsLayout();
1855         }
1856     }
1857 }
1858
1859 void RenderBlock::markForPaginationRelayoutIfNeeded(SubtreeLayoutScope& layoutScope)
1860 {
1861     ASSERT(!needsLayout());
1862     if (needsLayout())
1863         return;
1864
1865     if (view()->layoutState()->pageLogicalHeightChanged() || (view()->layoutState()->pageLogicalHeight() && view()->layoutState()->pageLogicalOffset(this, logicalTop()) != pageLogicalOffset()))
1866         layoutScope.setChildNeedsLayout(this);
1867 }
1868
1869 void RenderBlock::paint(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
1870 {
1871     ANNOTATE_GRAPHICS_CONTEXT(paintInfo, this);
1872
1873     LayoutPoint adjustedPaintOffset = paintOffset + location();
1874
1875     PaintPhase phase = paintInfo.phase;
1876
1877     // Check if we need to do anything at all.
1878     // FIXME: Could eliminate the isRoot() check if we fix background painting so that the RenderView
1879     // paints the root's background.
1880     if (!isRoot()) {
1881         LayoutRect overflowBox = overflowRectForPaintRejection();
1882         flipForWritingMode(overflowBox);
1883         overflowBox.inflate(maximalOutlineSize(paintInfo.phase));
1884         overflowBox.moveBy(adjustedPaintOffset);
1885         if (!overflowBox.intersects(paintInfo.rect))
1886             return;
1887     }
1888
1889     // There are some cases where not all clipped visual overflow is accounted for.
1890     // FIXME: reduce the number of such cases.
1891     ContentsClipBehavior contentsClipBehavior = ForceContentsClip;
1892     if (hasOverflowClip() && !hasControlClip() && !(shouldPaintSelectionGaps() && phase == PaintPhaseForeground) && !hasCaret())
1893         contentsClipBehavior = SkipContentsClipIfPossible;
1894
1895     bool pushedClip = pushContentsClip(paintInfo, adjustedPaintOffset, contentsClipBehavior);
1896     paintObject(paintInfo, adjustedPaintOffset);
1897     if (pushedClip)
1898         popContentsClip(paintInfo, phase, adjustedPaintOffset);
1899
1900     // Our scrollbar widgets paint exactly when we tell them to, so that they work properly with
1901     // z-index.  We paint after we painted the background/border, so that the scrollbars will
1902     // sit above the background/border.
1903     if (hasOverflowClip() && style()->visibility() == VISIBLE && (phase == PaintPhaseBlockBackground || phase == PaintPhaseChildBlockBackground) && paintInfo.shouldPaintWithinRoot(this) && !paintInfo.paintRootBackgroundOnly())
1904         layer()->scrollableArea()->paintOverflowControls(paintInfo.context, roundedIntPoint(adjustedPaintOffset), paintInfo.rect, false /* paintingOverlayControls */);
1905 }
1906
1907 void RenderBlock::paintColumnRules(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
1908 {
1909     if (paintInfo.context->paintingDisabled())
1910         return;
1911
1912     const Color& ruleColor = resolveColor(CSSPropertyWebkitColumnRuleColor);
1913     bool ruleTransparent = style()->columnRuleIsTransparent();
1914     EBorderStyle ruleStyle = style()->columnRuleStyle();
1915     LayoutUnit ruleThickness = style()->columnRuleWidth();
1916     LayoutUnit colGap = columnGap();
1917     bool renderRule = ruleStyle > BHIDDEN && !ruleTransparent;
1918     if (!renderRule)
1919         return;
1920
1921     ColumnInfo* colInfo = columnInfo();
1922     unsigned colCount = columnCount(colInfo);
1923
1924     bool antialias = shouldAntialiasLines(paintInfo.context);
1925
1926     if (colInfo->progressionAxis() == ColumnInfo::InlineAxis) {
1927         bool leftToRight = style()->isLeftToRightDirection() ^ colInfo->progressionIsReversed();
1928         LayoutUnit currLogicalLeftOffset = leftToRight ? LayoutUnit() : contentLogicalWidth();
1929         LayoutUnit ruleAdd = logicalLeftOffsetForContent();
1930         LayoutUnit ruleLogicalLeft = leftToRight ? LayoutUnit() : contentLogicalWidth();
1931         LayoutUnit inlineDirectionSize = colInfo->desiredColumnWidth();
1932         BoxSide boxSide = isHorizontalWritingMode()
1933             ? leftToRight ? BSLeft : BSRight
1934             : leftToRight ? BSTop : BSBottom;
1935
1936         for (unsigned i = 0; i < colCount; i++) {
1937             // Move to the next position.
1938             if (leftToRight) {
1939                 ruleLogicalLeft += inlineDirectionSize + colGap / 2;
1940                 currLogicalLeftOffset += inlineDirectionSize + colGap;
1941             } else {
1942                 ruleLogicalLeft -= (inlineDirectionSize + colGap / 2);
1943                 currLogicalLeftOffset -= (inlineDirectionSize + colGap);
1944             }
1945
1946             // Now paint the column rule.
1947             if (i < colCount - 1) {
1948                 LayoutUnit ruleLeft = isHorizontalWritingMode() ? paintOffset.x() + ruleLogicalLeft - ruleThickness / 2 + ruleAdd : paintOffset.x() + borderLeft() + paddingLeft();
1949                 LayoutUnit ruleRight = isHorizontalWritingMode() ? ruleLeft + ruleThickness : ruleLeft + contentWidth();
1950                 LayoutUnit ruleTop = isHorizontalWritingMode() ? paintOffset.y() + borderTop() + paddingTop() : paintOffset.y() + ruleLogicalLeft - ruleThickness / 2 + ruleAdd;
1951                 LayoutUnit ruleBottom = isHorizontalWritingMode() ? ruleTop + contentHeight() : ruleTop + ruleThickness;
1952                 IntRect pixelSnappedRuleRect = pixelSnappedIntRectFromEdges(ruleLeft, ruleTop, ruleRight, ruleBottom);
1953                 drawLineForBoxSide(paintInfo.context, pixelSnappedRuleRect.x(), pixelSnappedRuleRect.y(), pixelSnappedRuleRect.maxX(), pixelSnappedRuleRect.maxY(), boxSide, ruleColor, ruleStyle, 0, 0, antialias);
1954             }
1955
1956             ruleLogicalLeft = currLogicalLeftOffset;
1957         }
1958     } else {
1959         bool topToBottom = !style()->isFlippedBlocksWritingMode() ^ colInfo->progressionIsReversed();
1960         LayoutUnit ruleLeft = isHorizontalWritingMode()
1961             ? borderLeft() + paddingLeft()
1962             : colGap / 2 - colGap - ruleThickness / 2 + (!colInfo->progressionIsReversed() ? borderBefore() + paddingBefore() : borderAfter() + paddingAfter());
1963         LayoutUnit ruleWidth = isHorizontalWritingMode() ? contentWidth() : ruleThickness;
1964         LayoutUnit ruleTop = isHorizontalWritingMode()
1965             ? colGap / 2 - colGap - ruleThickness / 2 + (!colInfo->progressionIsReversed() ? borderBefore() + paddingBefore() : borderAfter() + paddingAfter())
1966             : borderStart() + paddingStart();
1967         LayoutUnit ruleHeight = isHorizontalWritingMode() ? ruleThickness : contentHeight();
1968         LayoutRect ruleRect(ruleLeft, ruleTop, ruleWidth, ruleHeight);
1969
1970         if (!topToBottom) {
1971             if (isHorizontalWritingMode())
1972                 ruleRect.setY(height() - ruleRect.maxY());
1973             else
1974                 ruleRect.setX(width() - ruleRect.maxX());
1975         }
1976
1977         ruleRect.moveBy(paintOffset);
1978
1979         BoxSide boxSide = isHorizontalWritingMode()
1980             ? topToBottom ? BSTop : BSBottom
1981             : topToBottom ? BSLeft : BSRight;
1982
1983         LayoutSize step(0, topToBottom ? colInfo->columnHeight() + colGap : -(colInfo->columnHeight() + colGap));
1984         if (!isHorizontalWritingMode())
1985             step = step.transposedSize();
1986
1987         for (unsigned i = 1; i < colCount; i++) {
1988             ruleRect.move(step);
1989             IntRect pixelSnappedRuleRect = pixelSnappedIntRect(ruleRect);
1990             drawLineForBoxSide(paintInfo.context, pixelSnappedRuleRect.x(), pixelSnappedRuleRect.y(), pixelSnappedRuleRect.maxX(), pixelSnappedRuleRect.maxY(), boxSide, ruleColor, ruleStyle, 0, 0, antialias);
1991         }
1992     }
1993 }
1994
1995 void RenderBlock::paintColumnContents(PaintInfo& paintInfo, const LayoutPoint& paintOffset, bool paintingFloats)
1996 {
1997     // We need to do multiple passes, breaking up our child painting into strips.
1998     GraphicsContext* context = paintInfo.context;
1999     ColumnInfo* colInfo = columnInfo();
2000     unsigned colCount = columnCount(colInfo);
2001     if (!colCount)
2002         return;
2003     LayoutUnit currLogicalTopOffset = 0;
2004     LayoutUnit colGap = columnGap();
2005     for (unsigned i = 0; i < colCount; i++) {
2006         // For each rect, we clip to the rect, and then we adjust our coords.
2007         LayoutRect colRect = columnRectAt(colInfo, i);
2008         flipForWritingMode(colRect);
2009         LayoutUnit logicalLeftOffset = (isHorizontalWritingMode() ? colRect.x() : colRect.y()) - logicalLeftOffsetForContent();
2010         LayoutSize offset = isHorizontalWritingMode() ? LayoutSize(logicalLeftOffset, currLogicalTopOffset) : LayoutSize(currLogicalTopOffset, logicalLeftOffset);
2011         if (colInfo->progressionAxis() == ColumnInfo::BlockAxis) {
2012             if (isHorizontalWritingMode())
2013                 offset.expand(0, colRect.y() - borderTop() - paddingTop());
2014             else
2015                 offset.expand(colRect.x() - borderLeft() - paddingLeft(), 0);
2016         }
2017         colRect.moveBy(paintOffset);
2018         PaintInfo info(paintInfo);
2019         info.rect.intersect(pixelSnappedIntRect(colRect));
2020
2021         if (!info.rect.isEmpty()) {
2022             GraphicsContextStateSaver stateSaver(*context);
2023             LayoutRect clipRect(colRect);
2024
2025             if (i < colCount - 1) {
2026                 if (isHorizontalWritingMode())
2027                     clipRect.expand(colGap / 2, 0);
2028                 else
2029                     clipRect.expand(0, colGap / 2);
2030             }
2031             // Each strip pushes a clip, since column boxes are specified as being
2032             // like overflow:hidden.
2033             // FIXME: Content and column rules that extend outside column boxes at the edges of the multi-column element
2034             // are clipped according to the 'overflow' property.
2035             context->clip(pixelSnappedIntRect(clipRect));
2036
2037             // Adjust our x and y when painting.
2038             LayoutPoint adjustedPaintOffset = paintOffset + offset;
2039             if (paintingFloats)
2040                 paintFloats(info, adjustedPaintOffset, paintInfo.phase == PaintPhaseSelection || paintInfo.phase == PaintPhaseTextClip);
2041             else
2042                 paintContents(info, adjustedPaintOffset);
2043         }
2044
2045         LayoutUnit blockDelta = (isHorizontalWritingMode() ? colRect.height() : colRect.width());
2046         if (style()->isFlippedBlocksWritingMode())
2047             currLogicalTopOffset += blockDelta;
2048         else
2049             currLogicalTopOffset -= blockDelta;
2050     }
2051 }
2052
2053 void RenderBlock::paintContents(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
2054 {
2055     // Avoid painting descendants of the root element when stylesheets haven't loaded.  This eliminates FOUC.
2056     // It's ok not to draw, because later on, when all the stylesheets do load, styleResolverChanged() on the Document
2057     // will do a full repaint.
2058     if (document().didLayoutWithPendingStylesheets() && !isRenderView())
2059         return;
2060
2061     if (childrenInline())
2062         m_lineBoxes.paint(this, paintInfo, paintOffset);
2063     else {
2064         PaintPhase newPhase = (paintInfo.phase == PaintPhaseChildOutlines) ? PaintPhaseOutline : paintInfo.phase;
2065         newPhase = (newPhase == PaintPhaseChildBlockBackgrounds) ? PaintPhaseChildBlockBackground : newPhase;
2066
2067         // We don't paint our own background, but we do let the kids paint their backgrounds.
2068         PaintInfo paintInfoForChild(paintInfo);
2069         paintInfoForChild.phase = newPhase;
2070         paintInfoForChild.updatePaintingRootForChildren(this);
2071         paintChildren(paintInfoForChild, paintOffset);
2072     }
2073 }
2074
2075 void RenderBlock::paintChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
2076 {
2077     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox())
2078         paintChild(child, paintInfo, paintOffset);
2079 }
2080
2081 void RenderBlock::paintChild(RenderBox* child, PaintInfo& paintInfo, const LayoutPoint& paintOffset)
2082 {
2083     LayoutPoint childPoint = flipForWritingModeForChild(child, paintOffset);
2084     if (!child->hasSelfPaintingLayer() && !child->isFloating())
2085         child->paint(paintInfo, childPoint);
2086 }
2087
2088 void RenderBlock::paintChildAsInlineBlock(RenderBox* child, PaintInfo& paintInfo, const LayoutPoint& paintOffset)
2089 {
2090     LayoutPoint childPoint = flipForWritingModeForChild(child, paintOffset);
2091     if (!child->hasSelfPaintingLayer() && !child->isFloating())
2092         paintAsInlineBlock(child, paintInfo, childPoint);
2093 }
2094
2095 void RenderBlock::paintAsInlineBlock(RenderObject* renderer, PaintInfo& paintInfo, const LayoutPoint& childPoint)
2096 {
2097     if (paintInfo.phase != PaintPhaseForeground && paintInfo.phase != PaintPhaseSelection)
2098         return;
2099
2100     // Paint all phases atomically, as though the element established its own
2101     // stacking context.  (See Appendix E.2, section 7.2.1.4 on
2102     // inline block/table/replaced elements in the CSS2.1 specification.)
2103     // This is also used by other elements (e.g. flex items and grid items).
2104     bool preservePhase = paintInfo.phase == PaintPhaseSelection || paintInfo.phase == PaintPhaseTextClip;
2105     PaintInfo info(paintInfo);
2106     info.phase = preservePhase ? paintInfo.phase : PaintPhaseBlockBackground;
2107     renderer->paint(info, childPoint);
2108     if (!preservePhase) {
2109         info.phase = PaintPhaseChildBlockBackgrounds;
2110         renderer->paint(info, childPoint);
2111         info.phase = PaintPhaseFloat;
2112         renderer->paint(info, childPoint);
2113         info.phase = PaintPhaseForeground;
2114         renderer->paint(info, childPoint);
2115         info.phase = PaintPhaseOutline;
2116         renderer->paint(info, childPoint);
2117     }
2118 }
2119
2120 bool RenderBlock::hasCaret(CaretType type) const
2121 {
2122     // Paint the caret if the FrameSelection says so or if caret browsing is enabled
2123     bool caretBrowsing = frame()->settings() && frame()->settings()->caretBrowsingEnabled();
2124     RenderObject* caretPainter;
2125     bool isContentEditable;
2126     if (type == CursorCaret) {
2127         caretPainter = frame()->selection().caretRenderer();
2128         isContentEditable = frame()->selection().rendererIsEditable();
2129     } else {
2130         caretPainter = frame()->page()->dragCaretController().caretRenderer();
2131         isContentEditable = frame()->page()->dragCaretController().isContentEditable();
2132     }
2133     return caretPainter == this && (isContentEditable || caretBrowsing);
2134 }
2135
2136 void RenderBlock::paintCaret(PaintInfo& paintInfo, const LayoutPoint& paintOffset, CaretType type)
2137 {
2138     if (!hasCaret(type))
2139         return;
2140
2141     if (type == CursorCaret)
2142         frame()->selection().paintCaret(paintInfo.context, paintOffset, paintInfo.rect);
2143     else
2144         frame()->page()->dragCaretController().paintDragCaret(frame(), paintInfo.context, paintOffset, paintInfo.rect);
2145 }
2146
2147 void RenderBlock::paintObject(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
2148 {
2149     PaintPhase paintPhase = paintInfo.phase;
2150
2151     // Adjust our painting position if we're inside a scrolled layer (e.g., an overflow:auto div).
2152     LayoutPoint scrolledOffset = paintOffset;
2153     if (hasOverflowClip())
2154         scrolledOffset.move(-scrolledContentOffset());
2155
2156     // 1. paint background, borders etc
2157     if ((paintPhase == PaintPhaseBlockBackground || paintPhase == PaintPhaseChildBlockBackground) && style()->visibility() == VISIBLE) {
2158         if (hasBoxDecorations())
2159             paintBoxDecorations(paintInfo, paintOffset);
2160         if (hasColumns() && !paintInfo.paintRootBackgroundOnly())
2161             paintColumnRules(paintInfo, scrolledOffset);
2162     }
2163
2164     if (paintPhase == PaintPhaseMask && style()->visibility() == VISIBLE) {
2165         paintMask(paintInfo, paintOffset);
2166         return;
2167     }
2168
2169     if (paintPhase == PaintPhaseClippingMask && style()->visibility() == VISIBLE) {
2170         paintClippingMask(paintInfo, paintOffset);
2171         return;
2172     }
2173
2174     // We're done.  We don't bother painting any children.
2175     if (paintPhase == PaintPhaseBlockBackground || paintInfo.paintRootBackgroundOnly())
2176         return;
2177
2178     // 2. paint contents
2179     if (paintPhase != PaintPhaseSelfOutline) {
2180         if (hasColumns())
2181             paintColumnContents(paintInfo, scrolledOffset);
2182         else
2183             paintContents(paintInfo, scrolledOffset);
2184     }
2185
2186     // 3. paint selection
2187     // FIXME: Make this work with multi column layouts.  For now don't fill gaps.
2188     bool isPrinting = document().printing();
2189     if (!isPrinting && !hasColumns())
2190         paintSelection(paintInfo, scrolledOffset); // Fill in gaps in selection on lines and between blocks.
2191
2192     // 4. paint floats.
2193     if (paintPhase == PaintPhaseFloat || paintPhase == PaintPhaseSelection || paintPhase == PaintPhaseTextClip) {
2194         if (hasColumns())
2195             paintColumnContents(paintInfo, scrolledOffset, true);
2196         else
2197             paintFloats(paintInfo, scrolledOffset, paintPhase == PaintPhaseSelection || paintPhase == PaintPhaseTextClip);
2198     }
2199
2200     // 5. paint outline.
2201     if ((paintPhase == PaintPhaseOutline || paintPhase == PaintPhaseSelfOutline) && hasOutline() && style()->visibility() == VISIBLE)
2202         paintOutline(paintInfo, LayoutRect(paintOffset, size()));
2203
2204     // 6. paint continuation outlines.
2205     if ((paintPhase == PaintPhaseOutline || paintPhase == PaintPhaseChildOutlines)) {
2206         RenderInline* inlineCont = inlineElementContinuation();
2207         if (inlineCont && inlineCont->hasOutline() && inlineCont->style()->visibility() == VISIBLE) {
2208             RenderInline* inlineRenderer = toRenderInline(inlineCont->node()->renderer());
2209             RenderBlock* cb = containingBlock();
2210
2211             bool inlineEnclosedInSelfPaintingLayer = false;
2212             for (RenderBoxModelObject* box = inlineRenderer; box != cb; box = box->parent()->enclosingBoxModelObject()) {
2213                 if (box->hasSelfPaintingLayer()) {
2214                     inlineEnclosedInSelfPaintingLayer = true;
2215                     break;
2216                 }
2217             }
2218
2219             // Do not add continuations for outline painting by our containing block if we are a relative positioned
2220             // anonymous block (i.e. have our own layer), paint them straightaway instead. This is because a block depends on renderers in its continuation table being
2221             // in the same layer.
2222             if (!inlineEnclosedInSelfPaintingLayer && !hasLayer())
2223                 cb->addContinuationWithOutline(inlineRenderer);
2224             else if (!inlineRenderer->firstLineBox() || (!inlineEnclosedInSelfPaintingLayer && hasLayer()))
2225                 inlineRenderer->paintOutline(paintInfo, paintOffset - locationOffset() + inlineRenderer->containingBlock()->location());
2226         }
2227         paintContinuationOutlines(paintInfo, paintOffset);
2228     }
2229
2230     // 7. paint caret.
2231     // If the caret's node's render object's containing block is this block, and the paint action is PaintPhaseForeground,
2232     // then paint the caret.
2233     if (paintPhase == PaintPhaseForeground) {
2234         paintCaret(paintInfo, paintOffset, CursorCaret);
2235         paintCaret(paintInfo, paintOffset, DragCaret);
2236     }
2237 }
2238
2239 RenderInline* RenderBlock::inlineElementContinuation() const
2240 {
2241     RenderBoxModelObject* continuation = this->continuation();
2242     return continuation && continuation->isInline() ? toRenderInline(continuation) : 0;
2243 }
2244
2245 RenderBlock* RenderBlock::blockElementContinuation() const
2246 {
2247     RenderBoxModelObject* currentContinuation = continuation();
2248     if (!currentContinuation || currentContinuation->isInline())
2249         return 0;
2250     RenderBlock* nextContinuation = toRenderBlock(currentContinuation);
2251     if (nextContinuation->isAnonymousBlock())
2252         return nextContinuation->blockElementContinuation();
2253     return nextContinuation;
2254 }
2255
2256 static ContinuationOutlineTableMap* continuationOutlineTable()
2257 {
2258     DEFINE_STATIC_LOCAL(ContinuationOutlineTableMap, table, ());
2259     return &table;
2260 }
2261
2262 void RenderBlock::addContinuationWithOutline(RenderInline* flow)
2263 {
2264     // We can't make this work if the inline is in a layer.  We'll just rely on the broken
2265     // way of painting.
2266     ASSERT(!flow->layer() && !flow->isInlineElementContinuation());
2267
2268     ContinuationOutlineTableMap* table = continuationOutlineTable();
2269     ListHashSet<RenderInline*>* continuations = table->get(this);
2270     if (!continuations) {
2271         continuations = new ListHashSet<RenderInline*>;
2272         table->set(this, adoptPtr(continuations));
2273     }
2274
2275     continuations->add(flow);
2276 }
2277
2278 bool RenderBlock::paintsContinuationOutline(RenderInline* flow)
2279 {
2280     ContinuationOutlineTableMap* table = continuationOutlineTable();
2281     if (table->isEmpty())
2282         return false;
2283
2284     ListHashSet<RenderInline*>* continuations = table->get(this);
2285     if (!continuations)
2286         return false;
2287
2288     return continuations->contains(flow);
2289 }
2290
2291 void RenderBlock::paintContinuationOutlines(PaintInfo& info, const LayoutPoint& paintOffset)
2292 {
2293     ContinuationOutlineTableMap* table = continuationOutlineTable();
2294     if (table->isEmpty())
2295         return;
2296
2297     OwnPtr<ListHashSet<RenderInline*> > continuations = table->take(this);
2298     if (!continuations)
2299         return;
2300
2301     LayoutPoint accumulatedPaintOffset = paintOffset;
2302     // Paint each continuation outline.
2303     ListHashSet<RenderInline*>::iterator end = continuations->end();
2304     for (ListHashSet<RenderInline*>::iterator it = continuations->begin(); it != end; ++it) {
2305         // Need to add in the coordinates of the intervening blocks.
2306         RenderInline* flow = *it;
2307         RenderBlock* block = flow->containingBlock();
2308         for ( ; block && block != this; block = block->containingBlock())
2309             accumulatedPaintOffset.moveBy(block->location());
2310         ASSERT(block);
2311         flow->paintOutline(info, accumulatedPaintOffset);
2312     }
2313 }
2314
2315 bool RenderBlock::shouldPaintSelectionGaps() const
2316 {
2317     return selectionState() != SelectionNone && style()->visibility() == VISIBLE && isSelectionRoot();
2318 }
2319
2320 bool RenderBlock::isSelectionRoot() const
2321 {
2322     if (isPseudoElement())
2323         return false;
2324     ASSERT(node() || isAnonymous());
2325
2326     // FIXME: Eventually tables should have to learn how to fill gaps between cells, at least in simple non-spanning cases.
2327     if (isTable())
2328         return false;
2329
2330     if (isBody() || isRoot() || hasOverflowClip()
2331         || isPositioned() || isFloating()
2332         || isTableCell() || isInlineBlockOrInlineTable()
2333         || hasTransform() || hasReflection() || hasMask() || isWritingModeRoot()
2334         || isRenderFlowThread())
2335         return true;
2336
2337     if (view() && view()->selectionStart()) {
2338         Node* startElement = view()->selectionStart()->node();
2339         if (startElement && startElement->rootEditableElement() == node())
2340             return true;
2341     }
2342
2343     return false;
2344 }
2345
2346 GapRects RenderBlock::selectionGapRectsForRepaint(const RenderLayerModelObject* repaintContainer)
2347 {
2348     ASSERT(!needsLayout());
2349
2350     if (!shouldPaintSelectionGaps())
2351         return GapRects();
2352
2353     TransformState transformState(TransformState::ApplyTransformDirection, FloatPoint());
2354     mapLocalToContainer(repaintContainer, transformState, ApplyContainerFlip | UseTransforms);
2355     LayoutPoint offsetFromRepaintContainer = roundedLayoutPoint(transformState.mappedPoint());
2356
2357     if (hasOverflowClip())
2358         offsetFromRepaintContainer -= scrolledContentOffset();
2359
2360     LayoutUnit lastTop = 0;
2361     LayoutUnit lastLeft = logicalLeftSelectionOffset(this, lastTop);
2362     LayoutUnit lastRight = logicalRightSelectionOffset(this, lastTop);
2363
2364     return selectionGaps(this, offsetFromRepaintContainer, IntSize(), lastTop, lastLeft, lastRight);
2365 }
2366
2367 void RenderBlock::paintSelection(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
2368 {
2369     if (shouldPaintSelectionGaps() && paintInfo.phase == PaintPhaseForeground) {
2370         LayoutUnit lastTop = 0;
2371         LayoutUnit lastLeft = logicalLeftSelectionOffset(this, lastTop);
2372         LayoutUnit lastRight = logicalRightSelectionOffset(this, lastTop);
2373         GraphicsContextStateSaver stateSaver(*paintInfo.context);
2374
2375         LayoutRect gapRectsBounds = selectionGaps(this, paintOffset, LayoutSize(), lastTop, lastLeft, lastRight, &paintInfo);
2376         if (!gapRectsBounds.isEmpty()) {
2377             if (RenderLayer* layer = enclosingLayer()) {
2378                 gapRectsBounds.moveBy(-paintOffset);
2379                 if (!hasLayer()) {
2380                     LayoutRect localBounds(gapRectsBounds);
2381                     flipForWritingMode(localBounds);
2382                     gapRectsBounds = localToContainerQuad(FloatRect(localBounds), layer->renderer()).enclosingBoundingBox();
2383                     if (layer->renderer()->hasOverflowClip())
2384                         gapRectsBounds.move(layer->renderBox()->scrolledContentOffset());
2385                 }
2386                 layer->addBlockSelectionGapsBounds(gapRectsBounds);
2387             }
2388         }
2389     }
2390 }
2391
2392 static void clipOutPositionedObjects(const PaintInfo* paintInfo, const LayoutPoint& offset, TrackedRendererListHashSet* positionedObjects)
2393 {
2394     if (!positionedObjects)
2395         return;
2396
2397     TrackedRendererListHashSet::const_iterator end = positionedObjects->end();
2398     for (TrackedRendererListHashSet::const_iterator it = positionedObjects->begin(); it != end; ++it) {
2399         RenderBox* r = *it;
2400         paintInfo->context->clipOut(IntRect(offset.x() + r->x(), offset.y() + r->y(), r->width(), r->height()));
2401     }
2402 }
2403
2404 LayoutUnit RenderBlock::blockDirectionOffset(const LayoutSize& offsetFromBlock) const
2405 {
2406     return isHorizontalWritingMode() ? offsetFromBlock.height() : offsetFromBlock.width();
2407 }
2408
2409 LayoutUnit RenderBlock::inlineDirectionOffset(const LayoutSize& offsetFromBlock) const
2410 {
2411     return isHorizontalWritingMode() ? offsetFromBlock.width() : offsetFromBlock.height();
2412 }
2413
2414 LayoutRect RenderBlock::logicalRectToPhysicalRect(const LayoutPoint& rootBlockPhysicalPosition, const LayoutRect& logicalRect)
2415 {
2416     LayoutRect result;
2417     if (isHorizontalWritingMode())
2418         result = logicalRect;
2419     else
2420         result = LayoutRect(logicalRect.y(), logicalRect.x(), logicalRect.height(), logicalRect.width());
2421     flipForWritingMode(result);
2422     result.moveBy(rootBlockPhysicalPosition);
2423     return result;
2424 }
2425
2426 GapRects RenderBlock::selectionGaps(RenderBlock* rootBlock, const LayoutPoint& rootBlockPhysicalPosition, const LayoutSize& offsetFromRootBlock,
2427                                     LayoutUnit& lastLogicalTop, LayoutUnit& lastLogicalLeft, LayoutUnit& lastLogicalRight, const PaintInfo* paintInfo)
2428 {
2429     // IMPORTANT: Callers of this method that intend for painting to happen need to do a save/restore.
2430     // Clip out floating and positioned objects when painting selection gaps.
2431     if (paintInfo) {
2432         // Note that we don't clip out overflow for positioned objects.  We just stick to the border box.
2433         LayoutRect flippedBlockRect(offsetFromRootBlock.width(), offsetFromRootBlock.height(), width(), height());
2434         rootBlock->flipForWritingMode(flippedBlockRect);
2435         flippedBlockRect.moveBy(rootBlockPhysicalPosition);
2436         clipOutPositionedObjects(paintInfo, flippedBlockRect.location(), positionedObjects());
2437         if (isBody() || isRoot()) // The <body> must make sure to examine its containingBlock's positioned objects.
2438             for (RenderBlock* cb = containingBlock(); cb && !cb->isRenderView(); cb = cb->containingBlock())
2439                 clipOutPositionedObjects(paintInfo, LayoutPoint(cb->x(), cb->y()), cb->positionedObjects()); // FIXME: Not right for flipped writing modes.
2440         clipOutFloatingObjects(rootBlock, paintInfo, rootBlockPhysicalPosition, offsetFromRootBlock);
2441     }
2442
2443     // FIXME: overflow: auto/scroll regions need more math here, since painting in the border box is different from painting in the padding box (one is scrolled, the other is
2444     // fixed).
2445     GapRects result;
2446     if (!isRenderBlockFlow() && !isFlexibleBoxIncludingDeprecated()) // FIXME: Make multi-column selection gap filling work someday.
2447         return result;
2448
2449     if (hasColumns() || hasTransform() || style()->columnSpan()) {
2450         // FIXME: We should learn how to gap fill multiple columns and transforms eventually.
2451         lastLogicalTop = rootBlock->blockDirectionOffset(offsetFromRootBlock) + logicalHeight();
2452         lastLogicalLeft = logicalLeftSelectionOffset(rootBlock, logicalHeight());
2453         lastLogicalRight = logicalRightSelectionOffset(rootBlock, logicalHeight());
2454         return result;
2455     }
2456
2457     if (childrenInline())
2458         result = toRenderBlockFlow(this)->inlineSelectionGaps(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, lastLogicalTop, lastLogicalLeft, lastLogicalRight, paintInfo);
2459     else
2460         result = blockSelectionGaps(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, lastLogicalTop, lastLogicalLeft, lastLogicalRight, paintInfo);
2461
2462     // Go ahead and fill the vertical gap all the way to the bottom of our block if the selection extends past our block.
2463     if (rootBlock == this && (selectionState() != SelectionBoth && selectionState() != SelectionEnd))
2464         result.uniteCenter(blockSelectionGap(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, lastLogicalTop, lastLogicalLeft, lastLogicalRight,
2465                                              logicalHeight(), paintInfo));
2466     return result;
2467 }
2468
2469 GapRects RenderBlock::blockSelectionGaps(RenderBlock* rootBlock, const LayoutPoint& rootBlockPhysicalPosition, const LayoutSize& offsetFromRootBlock,
2470                                          LayoutUnit& lastLogicalTop, LayoutUnit& lastLogicalLeft, LayoutUnit& lastLogicalRight, const PaintInfo* paintInfo)
2471 {
2472     GapRects result;
2473
2474     // Go ahead and jump right to the first block child that contains some selected objects.
2475     RenderBox* curr;
2476     for (curr = firstChildBox(); curr && curr->selectionState() == SelectionNone; curr = curr->nextSiblingBox()) { }
2477
2478     for (bool sawSelectionEnd = false; curr && !sawSelectionEnd; curr = curr->nextSiblingBox()) {
2479         SelectionState childState = curr->selectionState();
2480         if (childState == SelectionBoth || childState == SelectionEnd)
2481             sawSelectionEnd = true;
2482
2483         if (curr->isFloatingOrOutOfFlowPositioned())
2484             continue; // We must be a normal flow object in order to even be considered.
2485
2486         if (curr->isInFlowPositioned() && curr->hasLayer()) {
2487             // If the relposition offset is anything other than 0, then treat this just like an absolute positioned element.
2488             // Just disregard it completely.
2489             LayoutSize relOffset = curr->layer()->offsetForInFlowPosition();
2490             if (relOffset.width() || relOffset.height())
2491                 continue;
2492         }
2493
2494         bool paintsOwnSelection = curr->shouldPaintSelectionGaps() || curr->isTable(); // FIXME: Eventually we won't special-case table like this.
2495         bool fillBlockGaps = paintsOwnSelection || (curr->canBeSelectionLeaf() && childState != SelectionNone);
2496         if (fillBlockGaps) {
2497             // We need to fill the vertical gap above this object.
2498             if (childState == SelectionEnd || childState == SelectionInside)
2499                 // Fill the gap above the object.
2500                 result.uniteCenter(blockSelectionGap(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, lastLogicalTop, lastLogicalLeft, lastLogicalRight,
2501                                                      curr->logicalTop(), paintInfo));
2502
2503             // Only fill side gaps for objects that paint their own selection if we know for sure the selection is going to extend all the way *past*
2504             // our object.  We know this if the selection did not end inside our object.
2505             if (paintsOwnSelection && (childState == SelectionStart || sawSelectionEnd))
2506                 childState = SelectionNone;
2507
2508             // Fill side gaps on this object based off its state.
2509             bool leftGap, rightGap;
2510             getSelectionGapInfo(childState, leftGap, rightGap);
2511
2512             if (leftGap)
2513                 result.uniteLeft(logicalLeftSelectionGap(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, this, curr->logicalLeft(), curr->logicalTop(), curr->logicalHeight(), paintInfo));
2514             if (rightGap)
2515                 result.uniteRight(logicalRightSelectionGap(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, this, curr->logicalRight(), curr->logicalTop(), curr->logicalHeight(), paintInfo));
2516
2517             // Update lastLogicalTop to be just underneath the object.  lastLogicalLeft and lastLogicalRight extend as far as
2518             // they can without bumping into floating or positioned objects.  Ideally they will go right up
2519             // to the border of the root selection block.
2520             lastLogicalTop = rootBlock->blockDirectionOffset(offsetFromRootBlock) + curr->logicalBottom();
2521             lastLogicalLeft = logicalLeftSelectionOffset(rootBlock, curr->logicalBottom());
2522             lastLogicalRight = logicalRightSelectionOffset(rootBlock, curr->logicalBottom());
2523         } else if (childState != SelectionNone)
2524             // We must be a block that has some selected object inside it.  Go ahead and recur.
2525             result.unite(toRenderBlock(curr)->selectionGaps(rootBlock, rootBlockPhysicalPosition, LayoutSize(offsetFromRootBlock.width() + curr->x(), offsetFromRootBlock.height() + curr->y()),
2526                                                             lastLogicalTop, lastLogicalLeft, lastLogicalRight, paintInfo));
2527     }
2528     return result;
2529 }
2530
2531 LayoutRect RenderBlock::blockSelectionGap(RenderBlock* rootBlock, const LayoutPoint& rootBlockPhysicalPosition, const LayoutSize& offsetFromRootBlock,
2532                                           LayoutUnit lastLogicalTop, LayoutUnit lastLogicalLeft, LayoutUnit lastLogicalRight, LayoutUnit logicalBottom, const PaintInfo* paintInfo)
2533 {
2534     LayoutUnit logicalTop = lastLogicalTop;
2535     LayoutUnit logicalHeight = rootBlock->blockDirectionOffset(offsetFromRootBlock) + logicalBottom - logicalTop;
2536     if (logicalHeight <= 0)
2537         return LayoutRect();
2538
2539     // Get the selection offsets for the bottom of the gap
2540     LayoutUnit logicalLeft = max(lastLogicalLeft, logicalLeftSelectionOffset(rootBlock, logicalBottom));
2541     LayoutUnit logicalRight = min(lastLogicalRight, logicalRightSelectionOffset(rootBlock, logicalBottom));
2542     LayoutUnit logicalWidth = logicalRight - logicalLeft;
2543     if (logicalWidth <= 0)
2544         return LayoutRect();
2545
2546     LayoutRect gapRect = rootBlock->logicalRectToPhysicalRect(rootBlockPhysicalPosition, LayoutRect(logicalLeft, logicalTop, logicalWidth, logicalHeight));
2547     if (paintInfo)
2548         paintInfo->context->fillRect(pixelSnappedIntRect(gapRect), selectionBackgroundColor());
2549     return gapRect;
2550 }
2551
2552 LayoutRect RenderBlock::logicalLeftSelectionGap(RenderBlock* rootBlock, const LayoutPoint& rootBlockPhysicalPosition, const LayoutSize& offsetFromRootBlock,
2553                                                 RenderObject* selObj, LayoutUnit logicalLeft, LayoutUnit logicalTop, LayoutUnit logicalHeight, const PaintInfo* paintInfo)
2554 {
2555     LayoutUnit rootBlockLogicalTop = rootBlock->blockDirectionOffset(offsetFromRootBlock) + logicalTop;
2556     LayoutUnit rootBlockLogicalLeft = max(logicalLeftSelectionOffset(rootBlock, logicalTop), logicalLeftSelectionOffset(rootBlock, logicalTop + logicalHeight));
2557     LayoutUnit rootBlockLogicalRight = min(rootBlock->inlineDirectionOffset(offsetFromRootBlock) + floorToInt(logicalLeft), min(logicalRightSelectionOffset(rootBlock, logicalTop), logicalRightSelectionOffset(rootBlock, logicalTop + logicalHeight)));
2558     LayoutUnit rootBlockLogicalWidth = rootBlockLogicalRight - rootBlockLogicalLeft;
2559     if (rootBlockLogicalWidth <= 0)
2560         return LayoutRect();
2561
2562     LayoutRect gapRect = rootBlock->logicalRectToPhysicalRect(rootBlockPhysicalPosition, LayoutRect(rootBlockLogicalLeft, rootBlockLogicalTop, rootBlockLogicalWidth, logicalHeight));
2563     if (paintInfo)
2564         paintInfo->context->fillRect(pixelSnappedIntRect(gapRect), selObj->selectionBackgroundColor());
2565     return gapRect;
2566 }
2567
2568 LayoutRect RenderBlock::logicalRightSelectionGap(RenderBlock* rootBlock, const LayoutPoint& rootBlockPhysicalPosition, const LayoutSize& offsetFromRootBlock,
2569                                                  RenderObject* selObj, LayoutUnit logicalRight, LayoutUnit logicalTop, LayoutUnit logicalHeight, const PaintInfo* paintInfo)
2570 {
2571     LayoutUnit rootBlockLogicalTop = rootBlock->blockDirectionOffset(offsetFromRootBlock) + logicalTop;
2572     LayoutUnit rootBlockLogicalLeft = max(rootBlock->inlineDirectionOffset(offsetFromRootBlock) + floorToInt(logicalRight), max(logicalLeftSelectionOffset(rootBlock, logicalTop), logicalLeftSelectionOffset(rootBlock, logicalTop + logicalHeight)));
2573     LayoutUnit rootBlockLogicalRight = min(logicalRightSelectionOffset(rootBlock, logicalTop), logicalRightSelectionOffset(rootBlock, logicalTop + logicalHeight));
2574     LayoutUnit rootBlockLogicalWidth = rootBlockLogicalRight - rootBlockLogicalLeft;
2575     if (rootBlockLogicalWidth <= 0)
2576         return LayoutRect();
2577
2578     LayoutRect gapRect = rootBlock->logicalRectToPhysicalRect(rootBlockPhysicalPosition, LayoutRect(rootBlockLogicalLeft, rootBlockLogicalTop, rootBlockLogicalWidth, logicalHeight));
2579     if (paintInfo)
2580         paintInfo->context->fillRect(pixelSnappedIntRect(gapRect), selObj->selectionBackgroundColor());
2581     return gapRect;
2582 }
2583
2584 void RenderBlock::getSelectionGapInfo(SelectionState state, bool& leftGap, bool& rightGap)
2585 {
2586     bool ltr = style()->isLeftToRightDirection();
2587     leftGap = (state == RenderObject::SelectionInside) ||
2588               (state == RenderObject::SelectionEnd && ltr) ||
2589               (state == RenderObject::SelectionStart && !ltr);
2590     rightGap = (state == RenderObject::SelectionInside) ||
2591                (state == RenderObject::SelectionStart && ltr) ||
2592                (state == RenderObject::SelectionEnd && !ltr);
2593 }
2594
2595 LayoutUnit RenderBlock::logicalLeftSelectionOffset(RenderBlock* rootBlock, LayoutUnit position)
2596 {
2597     // The border can potentially be further extended by our containingBlock().
2598     if (rootBlock != this)
2599         return containingBlock()->logicalLeftSelectionOffset(rootBlock, position + logicalTop());
2600     return logicalLeftOffsetForContent();
2601 }
2602
2603 LayoutUnit RenderBlock::logicalRightSelectionOffset(RenderBlock* rootBlock, LayoutUnit position)
2604 {
2605     // The border can potentially be further extended by our containingBlock().
2606     if (rootBlock != this)
2607         return containingBlock()->logicalRightSelectionOffset(rootBlock, position + logicalTop());
2608     return logicalRightOffsetForContent();
2609 }
2610
2611 RenderBlock* RenderBlock::blockBeforeWithinSelectionRoot(LayoutSize& offset) const
2612 {
2613     if (isSelectionRoot())
2614         return 0;
2615
2616     const RenderObject* object = this;
2617     RenderObject* sibling;
2618     do {
2619         sibling = object->previousSibling();
2620         while (sibling && (!sibling->isRenderBlock() || toRenderBlock(sibling)->isSelectionRoot()))
2621             sibling = sibling->previousSibling();
2622
2623         offset -= LayoutSize(toRenderBlock(object)->logicalLeft(), toRenderBlock(object)->logicalTop());
2624         object = object->parent();
2625     } while (!sibling && object && object->isRenderBlock() && !toRenderBlock(object)->isSelectionRoot());
2626
2627     if (!sibling)
2628         return 0;
2629
2630     RenderBlock* beforeBlock = toRenderBlock(sibling);
2631
2632     offset += LayoutSize(beforeBlock->logicalLeft(), beforeBlock->logicalTop());
2633
2634     RenderObject* child = beforeBlock->lastChild();
2635     while (child && child->isRenderBlock()) {
2636         beforeBlock = toRenderBlock(child);
2637         offset += LayoutSize(beforeBlock->logicalLeft(), beforeBlock->logicalTop());
2638         child = beforeBlock->lastChild();
2639     }
2640     return beforeBlock;
2641 }
2642
2643 void RenderBlock::insertIntoTrackedRendererMaps(RenderBox* descendant, TrackedDescendantsMap*& descendantsMap, TrackedContainerMap*& containerMap)
2644 {
2645     if (!descendantsMap) {
2646         descendantsMap = new TrackedDescendantsMap;
2647         containerMap = new TrackedContainerMap;
2648     }
2649
2650     TrackedRendererListHashSet* descendantSet = descendantsMap->get(this);
2651     if (!descendantSet) {
2652         descendantSet = new TrackedRendererListHashSet;
2653         descendantsMap->set(this, adoptPtr(descendantSet));
2654     }
2655     bool added = descendantSet->add(descendant).isNewEntry;
2656     if (!added) {
2657         ASSERT(containerMap->get(descendant));
2658         ASSERT(containerMap->get(descendant)->contains(this));
2659         return;
2660     }
2661
2662     HashSet<RenderBlock*>* containerSet = containerMap->get(descendant);
2663     if (!containerSet) {
2664         containerSet = new HashSet<RenderBlock*>;
2665         containerMap->set(descendant, adoptPtr(containerSet));
2666     }
2667     ASSERT(!containerSet->contains(this));
2668     containerSet->add(this);
2669 }
2670
2671 void RenderBlock::removeFromTrackedRendererMaps(RenderBox* descendant, TrackedDescendantsMap*& descendantsMap, TrackedContainerMap*& containerMap)
2672 {
2673     if (!descendantsMap)
2674         return;
2675
2676     OwnPtr<HashSet<RenderBlock*> > containerSet = containerMap->take(descendant);
2677     if (!containerSet)
2678         return;
2679
2680     HashSet<RenderBlock*>::iterator end = containerSet->end();
2681     for (HashSet<RenderBlock*>::iterator it = containerSet->begin(); it != end; ++it) {
2682         RenderBlock* container = *it;
2683
2684         // FIXME: Disabling this assert temporarily until we fix the layout
2685         // bugs associated with positioned objects not properly cleared from
2686         // their ancestor chain before being moved. See webkit bug 93766.
2687         // ASSERT(descendant->isDescendantOf(container));
2688
2689         TrackedDescendantsMap::iterator descendantsMapIterator = descendantsMap->find(container);
2690         ASSERT(descendantsMapIterator != descendantsMap->end());
2691         if (descendantsMapIterator == descendantsMap->end())
2692             continue;
2693         TrackedRendererListHashSet* descendantSet = descendantsMapIterator->value.get();
2694         ASSERT(descendantSet->contains(descendant));
2695         descendantSet->remove(descendant);
2696         if (descendantSet->isEmpty())
2697             descendantsMap->remove(descendantsMapIterator);
2698     }
2699 }
2700
2701 TrackedRendererListHashSet* RenderBlock::positionedObjects() const
2702 {
2703     if (gPositionedDescendantsMap)
2704         return gPositionedDescendantsMap->get(this);
2705     return 0;
2706 }
2707
2708 void RenderBlock::insertPositionedObject(RenderBox* o)
2709 {
2710     ASSERT(!isAnonymousBlock());
2711
2712     if (o->isRenderFlowThread())
2713         return;
2714
2715     insertIntoTrackedRendererMaps(o, gPositionedDescendantsMap, gPositionedContainerMap);
2716 }
2717
2718 void RenderBlock::removePositionedObject(RenderBox* o)
2719 {
2720     removeFromTrackedRendererMaps(o, gPositionedDescendantsMap, gPositionedContainerMap);
2721 }
2722
2723 void RenderBlock::removePositionedObjects(RenderBlock* o, ContainingBlockState containingBlockState)
2724 {
2725     TrackedRendererListHashSet* positionedDescendants = positionedObjects();
2726     if (!positionedDescendants)
2727         return;
2728
2729     RenderBox* r;
2730
2731     TrackedRendererListHashSet::iterator end = positionedDescendants->end();
2732
2733     Vector<RenderBox*, 16> deadObjects;
2734
2735     for (TrackedRendererListHashSet::iterator it = positionedDescendants->begin(); it != end; ++it) {
2736         r = *it;
2737         if (!o || r->isDescendantOf(o)) {
2738             if (containingBlockState == NewContainingBlock)
2739                 r->setChildNeedsLayout(MarkOnlyThis);
2740
2741             // It is parent blocks job to add positioned child to positioned objects list of its containing block
2742             // Parent layout needs to be invalidated to ensure this happens.
2743             RenderObject* p = r->parent();
2744             while (p && !p->isRenderBlock())
2745                 p = p->parent();
2746             if (p)
2747                 p->setChildNeedsLayout();
2748
2749             deadObjects.append(r);
2750         }
2751     }
2752
2753     for (unsigned i = 0; i < deadObjects.size(); i++)
2754         removePositionedObject(deadObjects.at(i));
2755 }
2756
2757 void RenderBlock::addPercentHeightDescendant(RenderBox* descendant)
2758 {
2759     insertIntoTrackedRendererMaps(descendant, gPercentHeightDescendantsMap, gPercentHeightContainerMap);
2760 }
2761
2762 void RenderBlock::removePercentHeightDescendant(RenderBox* descendant)
2763 {
2764     removeFromTrackedRendererMaps(descendant, gPercentHeightDescendantsMap, gPercentHeightContainerMap);
2765 }
2766
2767 TrackedRendererListHashSet* RenderBlock::percentHeightDescendants() const
2768 {
2769     return gPercentHeightDescendantsMap ? gPercentHeightDescendantsMap->get(this) : 0;
2770 }
2771
2772 bool RenderBlock::hasPercentHeightContainerMap()
2773 {
2774     return gPercentHeightContainerMap;
2775 }
2776
2777 bool RenderBlock::hasPercentHeightDescendant(RenderBox* descendant)
2778 {
2779     // We don't null check gPercentHeightContainerMap since the caller
2780     // already ensures this and we need to call this function on every
2781     // descendant in clearPercentHeightDescendantsFrom().
2782     ASSERT(gPercentHeightContainerMap);
2783     return gPercentHeightContainerMap->contains(descendant);
2784 }
2785
2786 void RenderBlock::dirtyForLayoutFromPercentageHeightDescendants(SubtreeLayoutScope& layoutScope)
2787 {
2788     if (!gPercentHeightDescendantsMap)
2789         return;
2790
2791     TrackedRendererListHashSet* descendants = gPercentHeightDescendantsMap->get(this);
2792     if (!descendants)
2793         return;
2794
2795     TrackedRendererListHashSet::iterator end = descendants->end();
2796     for (TrackedRendererListHashSet::iterator it = descendants->begin(); it != end; ++it) {
2797         RenderBox* box = *it;
2798         while (box != this) {
2799             if (box->normalChildNeedsLayout())
2800                 break;
2801             layoutScope.setChildNeedsLayout(box);
2802             box = box->containingBlock();
2803             ASSERT(box);
2804             if (!box)
2805                 break;
2806         }
2807     }
2808 }
2809
2810 void RenderBlock::removePercentHeightDescendantIfNeeded(RenderBox* descendant)
2811 {
2812     // We query the map directly, rather than looking at style's
2813     // logicalHeight()/logicalMinHeight()/logicalMaxHeight() since those
2814     // can change with writing mode/directional changes.
2815     if (!hasPercentHeightContainerMap())
2816         return;
2817
2818     if (!hasPercentHeightDescendant(descendant))
2819         return;
2820
2821     removePercentHeightDescendant(descendant);
2822 }
2823
2824 void RenderBlock::clearPercentHeightDescendantsFrom(RenderBox* parent)
2825 {
2826     ASSERT(gPercentHeightContainerMap);
2827     for (RenderObject* curr = parent->firstChild(); curr; curr = curr->nextInPreOrder(parent)) {
2828         if (!curr->isBox())
2829             continue;
2830
2831         RenderBox* box = toRenderBox(curr);
2832         if (!hasPercentHeightDescendant(box))
2833             continue;
2834
2835         removePercentHeightDescendant(box);
2836     }
2837 }
2838
2839 LayoutUnit RenderBlock::textIndentOffset() const
2840 {
2841     LayoutUnit cw = 0;
2842     if (style()->textIndent().isPercent())
2843         cw = containingBlock()->availableLogicalWidth();
2844     return minimumValueForLength(style()->textIndent(), cw);
2845 }
2846
2847 void RenderBlock::markLinesDirtyInBlockRange(LayoutUnit logicalTop, LayoutUnit logicalBottom, RootInlineBox* highest)
2848 {
2849     if (logicalTop >= logicalBottom)
2850         return;
2851
2852     RootInlineBox* lowestDirtyLine = lastRootBox();
2853     RootInlineBox* afterLowest = lowestDirtyLine;
2854     while (lowestDirtyLine && lowestDirtyLine->lineBottomWithLeading() >= logicalBottom && logicalBottom < LayoutUnit::max()) {
2855         afterLowest = lowestDirtyLine;
2856         lowestDirtyLine = lowestDirtyLine->prevRootBox();
2857     }
2858
2859     while (afterLowest && afterLowest != highest && (afterLowest->lineBottomWithLeading() >= logicalTop || afterLowest->lineBottomWithLeading() < 0)) {
2860         afterLowest->markDirty();
2861         afterLowest = afterLowest->prevRootBox();
2862     }
2863 }
2864
2865 bool RenderBlock::avoidsFloats() const
2866 {
2867     // Floats can't intrude into our box if we have a non-auto column count or width.
2868     return RenderBox::avoidsFloats() || !style()->hasAutoColumnCount() || !style()->hasAutoColumnWidth();
2869 }
2870
2871 void RenderBlock::markShapeInsideDescendantsForLayout()
2872 {
2873     if (!everHadLayout())
2874         return;
2875     if (childrenInline()) {
2876         setNeedsLayout();
2877         return;
2878     }
2879     for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
2880         if (!child->isRenderBlock())
2881             continue;
2882         RenderBlock* childBlock = toRenderBlock(child);
2883         childBlock->markShapeInsideDescendantsForLayout();
2884     }
2885 }
2886
2887 bool RenderBlock::isPointInOverflowControl(HitTestResult& result, const LayoutPoint& locationInContainer, const LayoutPoint& accumulatedOffset)
2888 {
2889     if (!scrollsOverflow())
2890         return false;
2891
2892     return layer()->scrollableArea()->hitTestOverflowControls(result, roundedIntPoint(locationInContainer - toLayoutSize(accumulatedOffset)));
2893 }
2894
2895 Node* RenderBlock::nodeForHitTest() const
2896 {
2897     // If we are in the margins of block elements that are part of a
2898     // continuation we're actually still inside the enclosing element
2899     // that was split. Use the appropriate inner node.
2900     return isAnonymousBlockContinuation() ? continuation()->node() : node();
2901 }
2902
2903 bool RenderBlock::nodeAtPoint(const HitTestRequest& request, HitTestResult& result, const HitTestLocation& locationInContainer, const LayoutPoint& accumulatedOffset, HitTestAction hitTestAction)
2904 {
2905     LayoutPoint adjustedLocation(accumulatedOffset + location());
2906     LayoutSize localOffset = toLayoutSize(adjustedLocation);
2907
2908     if (!isRenderView()) {
2909         // Check if we need to do anything at all.
2910         LayoutRect overflowBox = visualOverflowRect();
2911         flipForWritingMode(overflowBox);
2912         overflowBox.moveBy(adjustedLocation);
2913         if (!locationInContainer.intersects(overflowBox))
2914             return false;
2915     }
2916
2917     if ((hitTestAction == HitTestBlockBackground || hitTestAction == HitTestChildBlockBackground)
2918         && visibleToHitTestRequest(request)
2919         && isPointInOverflowControl(result, locationInContainer.point(), adjustedLocation)) {
2920         updateHitTestResult(result, locationInContainer.point() - localOffset);
2921         // FIXME: isPointInOverflowControl() doesn't handle rect-based tests yet.
2922         if (!result.addNodeToRectBasedTestResult(nodeForHitTest(), request, locationInContainer))
2923            return true;
2924     }
2925
2926     // If we have clipping, then we can't have any spillout.
2927     bool useOverflowClip = hasOverflowClip() && !hasSelfPaintingLayer();
2928     bool useClip = (hasControlClip() || useOverflowClip);
2929     bool checkChildren = !useClip || (hasControlClip() ? locationInContainer.intersects(controlClipRect(adjustedLocation)) : locationInContainer.intersects(overflowClipRect(adjustedLocation, IncludeOverlayScrollbarSize)));
2930     if (checkChildren) {
2931         // Hit test descendants first.
2932         LayoutSize scrolledOffset(localOffset);
2933         if (hasOverflowClip())
2934             scrolledOffset -= scrolledContentOffset();
2935
2936         // Hit test contents if we don't have columns.
2937         if (!hasColumns()) {
2938             if (hitTestContents(request, result, locationInContainer, toLayoutPoint(scrolledOffset), hitTestAction)) {
2939                 updateHitTestResult(result, flipForWritingMode(locationInContainer.point() - localOffset));
2940                 return true;
2941             }
2942             if (hitTestAction == HitTestFloat && hitTestFloats(request, result, locationInContainer, toLayoutPoint(scrolledOffset)))
2943                 return true;
2944         } else if (hitTestColumns(request, result, locationInContainer, toLayoutPoint(scrolledOffset), hitTestAction)) {
2945             updateHitTestResult(result, flipForWritingMode(locationInContainer.point() - localOffset));
2946             return true;
2947         }
2948     }
2949
2950     // Check if the point is outside radii.
2951     if (!isRenderView() && style()->hasBorderRadius()) {
2952         LayoutRect borderRect = borderBoxRect();
2953         borderRect.moveBy(adjustedLocation);
2954         RoundedRect border = style()->getRoundedBorderFor(borderRect);
2955         if (!locationInContainer.intersects(border))
2956             return false;
2957     }
2958
2959     // Now hit test our background
2960     if (hitTestAction == HitTestBlockBackground || hitTestAction == HitTestChildBlockBackground) {
2961         LayoutRect boundsRect(adjustedLocation, size());
2962         if (visibleToHitTestRequest(request) && locationInContainer.intersects(boundsRect)) {
2963             updateHitTestResult(result, flipForWritingMode(locationInContainer.point() - localOffset));
2964             if (!result.addNodeToRectBasedTestResult(nodeForHitTest(), request, locationInContainer, boundsRect))
2965                 return true;
2966         }
2967     }
2968
2969     return false;
2970 }
2971
2972 class ColumnRectIterator {
2973     WTF_MAKE_NONCOPYABLE(ColumnRectIterator);
2974 public:
2975     ColumnRectIterator(const RenderBlock& block)
2976         : m_block(block)
2977         , m_colInfo(block.columnInfo())
2978         , m_direction(m_block.style()->isFlippedBlocksWritingMode() ? 1 : -1)
2979         , m_isHorizontal(block.isHorizontalWritingMode())
2980         , m_logicalLeft(block.logicalLeftOffsetForContent())
2981     {
2982         int colCount = m_colInfo->columnCount();
2983         m_colIndex = colCount - 1;
2984         m_currLogicalTopOffset = colCount * m_colInfo->columnHeight() * m_direction;
2985         update();
2986     }
2987
2988     void advance()
2989     {
2990         ASSERT(hasMore());
2991         m_colIndex--;
2992         update();
2993     }
2994
2995     LayoutRect columnRect() const { return m_colRect; }
2996     bool hasMore() const { return m_colIndex >= 0; }
2997
2998     void adjust(LayoutSize& offset) const
2999     {
3000         LayoutUnit currLogicalLeftOffset = (m_isHorizontal ? m_colRect.x() : m_colRect.y()) - m_logicalLeft;
3001         offset += m_isHorizontal ? LayoutSize(currLogicalLeftOffset, m_currLogicalTopOffset) : LayoutSize(m_currLogicalTopOffset, currLogicalLeftOffset);
3002         if (m_colInfo->progressionAxis() == ColumnInfo::BlockAxis) {
3003             if (m_isHorizontal)
3004                 offset.expand(0, m_colRect.y() - m_block.borderTop() - m_block.paddingTop());
3005             else
3006                 offset.expand(m_colRect.x() - m_block.borderLeft() - m_block.paddingLeft(), 0);
3007         }
3008     }
3009
3010 private:
3011     void update()
3012     {
3013         if (m_colIndex < 0)
3014             return;
3015
3016         m_colRect = m_block.columnRectAt(const_cast<ColumnInfo*>(m_colInfo), m_colIndex);
3017         m_block.flipForWritingMode(m_colRect);
3018         m_currLogicalTopOffset -= (m_isHorizontal ? m_colRect.height() : m_colRect.width()) * m_direction;
3019     }
3020
3021     const RenderBlock& m_block;
3022     const ColumnInfo* const m_colInfo;
3023     const int m_direction;
3024     const bool m_isHorizontal;
3025     const LayoutUnit m_logicalLeft;
3026     int m_colIndex;
3027     LayoutUnit m_currLogicalTopOffset;
3028     LayoutRect m_colRect;
3029 };
3030
3031 bool RenderBlock::hitTestColumns(const HitTestRequest& request, HitTestResult& result, const HitTestLocation& locationInContainer, const LayoutPoint& accumulatedOffset, HitTestAction hitTestAction)
3032 {
3033     // We need to do multiple passes, breaking up our hit testing into strips.
3034     if (!hasColumns())
3035         return false;
3036
3037     for (ColumnRectIterator it(*this); it.hasMore(); it.advance()) {
3038         LayoutRect hitRect = locationInContainer.boundingBox();
3039         LayoutRect colRect = it.columnRect();
3040         colRect.moveBy(accumulatedOffset);
3041         if (locationInContainer.intersects(colRect)) {
3042             // The point is inside this column.
3043             // Adjust accumulatedOffset to change where we hit test.
3044             LayoutSize offset;
3045             it.adjust(offset);
3046             LayoutPoint finalLocation = accumulatedOffset + offset;
3047             if (!result.isRectBasedTest() || colRect.contains(hitRect))
3048                 return hitTestContents(request, result, locationInContainer, finalLocation, hitTestAction) || (hitTestAction == HitTestFloat && hitTestFloats(request, result, locationInContainer, finalLocation));
3049
3050             hitTestContents(request, result, locationInContainer, finalLocation, hitTestAction);
3051         }
3052     }
3053
3054     return false;
3055 }
3056
3057 void RenderBlock::adjustForColumnRect(LayoutSize& offset, const LayoutPoint& locationInContainer) const
3058 {
3059     for (ColumnRectIterator it(*this); it.hasMore(); it.advance()) {
3060         LayoutRect colRect = it.columnRect();
3061         if (colRect.contains(locationInContainer)) {
3062             it.adjust(offset);
3063             return;
3064         }
3065     }
3066 }
3067
3068 bool RenderBlock::hitTestContents(const HitTestRequest& request, HitTestResult& result, const HitTestLocation& locationInContainer, const LayoutPoint& accumulatedOffset, HitTestAction hitTestAction)
3069 {
3070     if (childrenInline() && !isTable()) {
3071         // We have to hit-test our line boxes.
3072         if (m_lineBoxes.hitTest(this, request, result, locationInContainer, accumulatedOffset, hitTestAction))
3073             return true;
3074     } else {
3075         // Hit test our children.
3076         HitTestAction childHitTest = hitTestAction;
3077         if (hitTestAction == HitTestChildBlockBackgrounds)
3078             childHitTest = HitTestChildBlockBackground;
3079         for (RenderBox* child = lastChildBox(); child; child = child->previousSiblingBox()) {
3080             LayoutPoint childPoint = flipForWritingModeForChild(child, accumulatedOffset);
3081             if (!child->hasSelfPaintingLayer() && !child->isFloating() && child->nodeAtPoint(request, result, locationInContainer, childPoint, childHitTest))
3082                 return true;
3083         }
3084     }
3085
3086     return false;
3087 }
3088
3089 Position RenderBlock::positionForBox(InlineBox *box, bool start) const
3090 {
3091     if (!box)
3092         return Position();
3093
3094     if (!box->renderer()->nonPseudoNode())
3095         return createLegacyEditingPosition(nonPseudoNode(), start ? caretMinOffset() : caretMaxOffset());
3096
3097     if (!box->isInlineTextBox())
3098         return createLegacyEditingPosition(box->renderer()->nonPseudoNode(), start ? box->renderer()->caretMinOffset() : box->renderer()->caretMaxOffset());
3099
3100     InlineTextBox* textBox = toInlineTextBox(box);
3101     return createLegacyEditingPosition(box->renderer()->nonPseudoNode(), start ? textBox->start() : textBox->start() + textBox->len());
3102 }
3103
3104 static inline bool isEditingBoundary(RenderObject* ancestor, RenderObject* child)
3105 {
3106     ASSERT(!ancestor || ancestor->nonPseudoNode());
3107     ASSERT(child && child->nonPseudoNode());
3108     return !ancestor || !ancestor->parent() || (ancestor->hasLayer() && ancestor->parent()->isRenderView())
3109         || ancestor->nonPseudoNode()->rendererIsEditable() == child->nonPseudoNode()->rendererIsEditable();
3110 }
3111
3112 // FIXME: This function should go on RenderObject as an instance method. Then
3113 // all cases in which positionForPoint recurs could call this instead to
3114 // prevent crossing editable boundaries. This would require many tests.
3115 static PositionWithAffinity positionForPointRespectingEditingBoundaries(RenderBlock* parent, RenderBox* child, const LayoutPoint& pointInParentCoordinates)
3116 {
3117     LayoutPoint childLocation = child->location();
3118     if (child->isInFlowPositioned())
3119         childLocation += child->offsetForInFlowPosition();
3120
3121     // FIXME: This is wrong if the child's writing-mode is different from the parent's.
3122     LayoutPoint pointInChildCoordinates(toLayoutPoint(pointInParentCoordinates - childLocation));
3123
3124     // If this is an anonymous renderer, we just recur normally
3125     Node* childNode = child->nonPseudoNode();
3126     if (!childNode)
3127         return child->positionForPoint(pointInChildCoordinates);
3128
3129     // Otherwise, first make sure that the editability of the parent and child agree.
3130     // If they don't agree, then we return a visible position just before or after the child
3131     RenderObject* ancestor = parent;
3132     while (ancestor && !ancestor->nonPseudoNode())
3133         ancestor = ancestor->parent();
3134
3135     // If we can't find an ancestor to check editability on, or editability is unchanged, we recur like normal
3136     if (isEditingBoundary(ancestor, child))
3137         return child->positionForPoint(pointInChildCoordinates);
3138
3139     // Otherwise return before or after the child, depending on if the click was to the logical left or logical right of the child
3140     LayoutUnit childMiddle = parent->logicalWidthForChild(child) / 2;
3141     LayoutUnit logicalLeft = parent->isHorizontalWritingMode() ? pointInChildCoordinates.x() : pointInChildCoordinates.y();
3142     if (logicalLeft < childMiddle)
3143         return ancestor->createPositionWithAffinity(childNode->nodeIndex(), DOWNSTREAM);
3144     return ancestor->createPositionWithAffinity(childNode->nodeIndex() + 1, UPSTREAM);
3145 }
3146
3147 PositionWithAffinity RenderBlock::positionForPointWithInlineChildren(const LayoutPoint& pointInLogicalContents)
3148 {
3149     ASSERT(childrenInline());
3150
3151     if (!firstRootBox())
3152         return createPositionWithAffinity(0, DOWNSTREAM);
3153
3154     bool linesAreFlipped = style()->isFlippedLinesWritingMode();
3155     bool blocksAreFlipped = style()->isFlippedBlocksWritingMode();
3156
3157     // look for the closest line box in the root box which is at the passed-in y coordinate
3158     InlineBox* closestBox = 0;
3159     RootInlineBox* firstRootBoxWithChildren = 0;
3160     RootInlineBox* lastRootBoxWithChildren = 0;
3161     for (RootInlineBox* root = firstRootBox(); root; root = root->nextRootBox()) {
3162         if (!root->firstLeafChild())
3163             continue;
3164         if (!firstRootBoxWithChildren)
3165             firstRootBoxWithChildren = root;
3166
3167         if (!linesAreFlipped && root->isFirstAfterPageBreak() && (pointInLogicalContents.y() < root->lineTopWithLeading()
3168             || (blocksAreFlipped && pointInLogicalContents.y() == root->lineTopWithLeading())))
3169             break;
3170
3171         lastRootBoxWithChildren = root;
3172
3173         // check if this root line box is located at this y coordinate
3174         if (pointInLogicalContents.y() < root->selectionBottom() || (blocksAreFlipped && pointInLogicalContents.y() == root->selectionBottom())) {
3175             if (linesAreFlipped) {
3176                 RootInlineBox* nextRootBoxWithChildren = root->nextRootBox();
3177                 while (nextRootBoxWithChildren && !nextRootBoxWithChildren->firstLeafChild())
3178                     nextRootBoxWithChildren = nextRootBoxWithChildren->nextRootBox();
3179
3180                 if (nextRootBoxWithChildren && nextRootBoxWithChildren->isFirstAfterPageBreak() && (pointInLogicalContents.y() > nextRootBoxWithChildren->lineTopWithLeading()
3181                     || (!blocksAreFlipped && pointInLogicalContents.y() == nextRootBoxWithChildren->lineTopWithLeading())))
3182                     continue;
3183             }
3184             closestBox = root->closestLeafChildForLogicalLeftPosition(pointInLogicalContents.x());
3185             if (closestBox)
3186                 break;
3187         }
3188     }
3189
3190     bool moveCaretToBoundary = document().frame()->editor().behavior().shouldMoveCaretToHorizontalBoundaryWhenPastTopOrBottom();
3191
3192     if (!moveCaretToBoundary && !closestBox && lastRootBoxWithChildren) {
3193         // y coordinate is below last root line box, pretend we hit it
3194         closestBox = lastRootBoxWithChildren->closestLeafChildForLogicalLeftPosition(pointInLogicalContents.x());
3195     }
3196
3197     if (closestBox) {
3198         if (moveCaretToBoundary) {
3199             LayoutUnit firstRootBoxWithChildrenTop = min<LayoutUnit>(firstRootBoxWithChildren->selectionTop(), firstRootBoxWithChildren->logicalTop());
3200             if (pointInLogicalContents.y() < firstRootBoxWithChildrenTop
3201                 || (blocksAreFlipped && pointInLogicalContents.y() == firstRootBoxWithChildrenTop)) {
3202                 InlineBox* box = firstRootBoxWithChildren->firstLeafChild();
3203                 if (box->isLineBreak()) {
3204                     if (InlineBox* newBox = box->nextLeafChildIgnoringLineBreak())
3205                         box = newBox;
3206                 }
3207                 // y coordinate is above first root line box, so return the start of the first
3208                 return PositionWithAffinity(positionForBox(box, true), DOWNSTREAM);
3209             }
3210         }
3211
3212         // pass the box a top position that is inside it
3213         LayoutPoint point(pointInLogicalContents.x(), closestBox->root()->blockDirectionPointInLine());
3214         if (!isHorizontalWritingMode())
3215             point = point.transposedPoint();
3216         if (closestBox->renderer()->isReplaced())
3217             return positionForPointRespectingEditingBoundaries(this, toRenderBox(closestBox->renderer()), point);
3218         return closestBox->renderer()->positionForPoint(point);
3219     }
3220
3221     if (lastRootBoxWithChildren) {
3222         // We hit this case for Mac behavior when the Y coordinate is below the last box.
3223         ASSERT(moveCaretToBoundary);
3224         InlineBox* logicallyLastBox;
3225         if (lastRootBoxWithChildren->getLogicalEndBoxWithNode(logicallyLastBox))
3226             return PositionWithAffinity(positionForBox(logicallyLastBox, false), DOWNSTREAM);
3227     }
3228
3229     // Can't reach this. We have a root line box, but it has no kids.
3230     // FIXME: This should ASSERT_NOT_REACHED(), but clicking on placeholder text
3231     // seems to hit this code path.
3232     return createPositionWithAffinity(0, DOWNSTREAM);
3233 }
3234
3235 static inline bool isChildHitTestCandidate(RenderBox* box)
3236 {
3237     return box->height() && box->style()->visibility() == VISIBLE && !box->isFloatingOrOutOfFlowPositioned();
3238 }
3239
3240 PositionWithAffinity RenderBlock::positionForPoint(const LayoutPoint& point)
3241 {
3242     if (isTable())
3243         return RenderBox::positionForPoint(point);
3244
3245     if (isReplaced()) {
3246         // FIXME: This seems wrong when the object's writing-mode doesn't match the line's writing-mode.
3247         LayoutUnit pointLogicalLeft = isHorizontalWritingMode() ? point.x() : point.y();
3248         LayoutUnit pointLogicalTop = isHorizontalWritingMode() ? point.y() : point.x();
3249
3250         if (pointLogicalLeft < 0)
3251             return createPositionWithAffinity(caretMinOffset(), DOWNSTREAM);
3252         if (pointLogicalLeft >= logicalWidth())
3253             return createPositionWithAffinity(caretMaxOffset(), DOWNSTREAM);
3254         if (pointLogicalTop < 0)
3255             return createPositionWithAffinity(caretMinOffset(), DOWNSTREAM);
3256         if (pointLogicalTop >= logicalHeight())
3257             return createPositionWithAffinity(caretMaxOffset(), DOWNSTREAM);
3258     }
3259
3260     LayoutPoint pointInContents = point;
3261     offsetForContents(pointInContents);
3262     LayoutPoint pointInLogicalContents(pointInContents);
3263     if (!isHorizontalWritingMode())
3264         pointInLogicalContents = pointInLogicalContents.transposedPoint();
3265
3266     if (childrenInline())
3267         return positionForPointWithInlineChildren(pointInLogicalContents);
3268
3269     RenderBox* lastCandidateBox = lastChildBox();
3270     while (lastCandidateBox && !isChildHitTestCandidate(lastCandidateBox))
3271         lastCandidateBox = lastCandidateBox->previousSiblingBox();
3272
3273     bool blocksAreFlipped = style()->isFlippedBlocksWritingMode();
3274     if (lastCandidateBox) {
3275         if (pointInLogicalContents.y() > logicalTopForChild(lastCandidateBox)
3276             || (!blocksAreFlipped && pointInLogicalContents.y() == logicalTopForChild(lastCandidateBox)))
3277             return positionForPointRespectingEditingBoundaries(this, lastCandidateBox, pointInContents);
3278
3279         for (RenderBox* childBox = firstChildBox(); childBox; childBox = childBox->nextSiblingBox()) {
3280             if (!isChildHitTestCandidate(childBox))
3281                 continue;
3282             LayoutUnit childLogicalBottom = logicalTopForChild(childBox) + logicalHeightForChild(childBox);
3283             // We hit child if our click is above the bottom of its padding box (like IE6/7 and FF3).
3284             if (isChildHitTestCandidate(childBox) && (pointInLogicalContents.y() < childLogicalBottom
3285                 || (blocksAreFlipped && pointInLogicalContents.y() == childLogicalBottom)))
3286                 return positionForPointRespectingEditingBoundaries(this, childBox, pointInContents);
3287         }
3288     }
3289
3290     // We only get here if there are no hit test candidate children below the click.
3291     return RenderBox::positionForPoint(point);
3292 }
3293
3294 void RenderBlock::offsetForContents(LayoutPoint& offset) const
3295 {
3296     offset = flipForWritingMode(offset);
3297
3298     if (hasOverflowClip())
3299         offset += scrolledContentOffset();
3300
3301     if (hasColumns())
3302         adjustPointToColumnContents(offset);
3303
3304     offset = flipForWritingMode(offset);
3305 }
3306
3307 LayoutUnit RenderBlock::availableLogicalWidth() const
3308 {
3309     // If we have multiple columns, then the available logical width is reduced to our column width.
3310     if (hasColumns())
3311         return desiredColumnWidth();
3312     return RenderBox::availableLogicalWidth();
3313 }
3314
3315 int RenderBlock::columnGap() const
3316 {
3317     if (style()->hasNormalColumnGap())
3318         return style()->fontDescription().computedPixelSize(); // "1em" is recommended as the normal gap setting. Matches <p> margins.
3319     return static_cast<int>(style()->columnGap());
3320 }
3321
3322 void RenderBlock::calcColumnWidth()
3323 {
3324     if (document().regionBasedColumnsEnabled())
3325         return;
3326
3327     // Calculate our column width and column count.
3328     // FIXME: Can overflow on fast/block/float/float-not-removed-from-next-sibling4.html, see https://bugs.webkit.org/show_bug.cgi?id=68744
3329     unsigned desiredColumnCount = 1;
3330     LayoutUnit desiredColumnWidth = contentLogicalWidth();
3331
3332     // For now, we don't support multi-column layouts when printing, since we have to do a lot of work for proper pagination.
3333     if (document().paginated() || (style()->hasAutoColumnCount() && style()->hasAutoColumnWidth()) || !style()->hasInlineColumnAxis()) {
3334         setDesiredColumnCountAndWidth(desiredColumnCount, desiredColumnWidth);
3335         return;
3336     }
3337
3338     LayoutUnit availWidth = desiredColumnWidth;
3339     LayoutUnit colGap = columnGap();
3340     LayoutUnit colWidth = max<LayoutUnit>(1, LayoutUnit(style()->columnWidth()));
3341     int colCount = max<int>(1, style()->columnCount());
3342
3343     if (style()->hasAutoColumnWidth() && !style()->hasAutoColumnCount()) {
3344         desiredColumnCount = colCount;
3345         desiredColumnWidth = max<LayoutUnit>(0, (availWidth - ((desiredColumnCount - 1) * colGap)) / desiredColumnCount);
3346     } else if (!style()->hasAutoColumnWidth() && style()->hasAutoColumnCount()) {
3347         desiredColumnCount = max<LayoutUnit>(1, (availWidth + colGap) / (colWidth + colGap));
3348         desiredColumnWidth = ((availWidth + colGap) / desiredColumnCount) - colGap;
3349     } else {
3350         desiredColumnCount = max<LayoutUnit>(min<LayoutUnit>(colCount, (availWidth + colGap) / (colWidth + colGap)), 1);
3351         desiredColumnWidth = ((availWidth + colGap) / desiredColumnCount) - colGap;
3352     }
3353     setDesiredColumnCountAndWidth(desiredColumnCount, desiredColumnWidth);
3354 }
3355
3356 bool RenderBlock::requiresColumns(int desiredColumnCount) const
3357 {
3358     // Paged overflow is treated as multicol here, unless this element was the one that got its
3359     // overflow propagated to the viewport.
3360     bool isPaginated = style()->isOverflowPaged() && node() != document().viewportDefiningElement();
3361
3362     return firstChild()
3363         && (desiredColumnCount != 1 || !style()->hasAutoColumnWidth() || !style()->hasInlineColumnAxis() || isPaginated)
3364         && !firstChild()->isAnonymousColumnsBlock()
3365         && !firstChild()->isAnonymousColumnSpanBlock();
3366 }
3367
3368 void RenderBlock::setDesiredColumnCountAndWidth(int count, LayoutUnit width)
3369 {
3370     bool destroyColumns = !requiresColumns(count);
3371     if (destroyColumns) {
3372         if (hasColumns()) {
3373             gColumnInfoMap->take(this);
3374             setHasColumns(false);
3375         }
3376     } else {
3377         ColumnInfo* info;
3378         if (hasColumns())
3379             info = gColumnInfoMap->get(this);
3380         else {
3381             if (!gColumnInfoMap)
3382                 gColumnInfoMap = new ColumnInfoMap;
3383             info = new ColumnInfo;
3384             gColumnInfoMap->add(this, adoptPtr(info));
3385             setHasColumns(true);
3386         }
3387         info->setDesiredColumnWidth(width);
3388         if (style()->isOverflowPaged()) {
3389             info->setProgressionAxis(style()->hasInlinePaginationAxis() ? ColumnInfo::InlineAxis : ColumnInfo::BlockAxis);
3390         } else {
3391             info->setDesiredColumnCount(count);
3392             info->setProgressionAxis(style()->hasInlineColumnAxis() ? ColumnInfo::InlineAxis : ColumnInfo::BlockAxis);
3393             info->setProgressionIsReversed(style()->columnProgression() == ReverseColumnProgression);
3394         }
3395     }
3396 }
3397
3398 LayoutUnit RenderBlock::desiredColumnWidth() const
3399 {
3400     if (!hasColumns())
3401         return contentLogicalWidth();
3402     return gColumnInfoMap->get(this)->desiredColumnWidth();
3403 }
3404
3405 ColumnInfo* RenderBlock::columnInfo() const
3406 {
3407     if (!hasColumns())
3408         return 0;
3409     return gColumnInfoMap->get(this);
3410 }
3411
3412 unsigned RenderBlock::columnCount(ColumnInfo* colInfo) const
3413 {
3414     ASSERT(hasColumns());
3415     ASSERT(gColumnInfoMap->get(this) == colInfo);
3416     return colInfo->columnCount();
3417 }
3418
3419 LayoutRect RenderBlock::columnRectAt(ColumnInfo* colInfo, unsigned index) const
3420 {
3421     ASSERT(hasColumns() && gColumnInfoMap->get(this) == colInfo);
3422
3423     // Compute the appropriate rect based off our information.
3424     LayoutUnit colLogicalWidth = colInfo->desiredColumnWidth();
3425     LayoutUnit colLogicalHeight = colInfo->columnHeight();
3426     LayoutUnit colLogicalTop = borderBefore() + paddingBefore();
3427     LayoutUnit colLogicalLeft = logicalLeftOffsetForContent();
3428     LayoutUnit colGap = columnGap();
3429     if (colInfo->progressionAxis() == ColumnInfo::InlineAxis) {
3430         if (style()->isLeftToRightDirection() ^ colInfo->progressionIsReversed())
3431             colLogicalLeft += index * (colLogicalWidth + colGap);
3432         else
3433             colLogicalLeft += contentLogicalWidth() - colLogicalWidth - index * (colLogicalWidth + colGap);
3434     } else {
3435         if (!colInfo->progressionIsReversed())
3436             colLogicalTop += index * (colLogicalHeight + colGap);
3437         else
3438             colLogicalTop += contentLogicalHeight() - colLogicalHeight - index * (colLogicalHeight + colGap);
3439     }
3440
3441     if (isHorizontalWritingMode())
3442         return LayoutRect(colLogicalLeft, colLogicalTop, colLogicalWidth, colLogicalHeight);
3443     return LayoutRect(colLogicalTop, colLogicalLeft, colLogicalHeight, colLogicalWidth);
3444 }
3445
3446 void RenderBlock::adjustPointToColumnContents(LayoutPoint& point) const
3447 {
3448     // Just bail if we have no columns.
3449     if (!hasColumns())
3450         return;
3451
3452     ColumnInfo* colInfo = columnInfo();
3453     if (!columnCount(colInfo))
3454         return;
3455
3456     // Determine which columns we intersect.
3457     LayoutUnit colGap = columnGap();
3458     LayoutUnit halfColGap = colGap / 2;
3459     LayoutPoint columnPoint(columnRectAt(colInfo, 0).location());
3460     LayoutUnit logicalOffset = 0;
3461     for (unsigned i = 0; i < colInfo->columnCount(); i++) {
3462         // Add in half the column gap to the left and right of the rect.
3463         LayoutRect colRect = columnRectAt(colInfo, i);
3464         flipForWritingMode(colRect);
3465         if (isHorizontalWritingMode() == (colInfo->progressionAxis() == ColumnInfo::InlineAxis)) {
3466             LayoutRect gapAndColumnRect(colRect.x() - halfColGap, colRect.y(), colRect.width() + colGap, colRect.height());
3467             if (point.x() >= gapAndColumnRect.x() && point.x() < gapAndColumnRect.maxX()) {
3468                 if (colInfo->progressionAxis() == ColumnInfo::InlineAxis) {
3469                     // FIXME: The clamping that follows is not completely right for right-to-left
3470                     // content.
3471                     // Clamp everything above the column to its top left.
3472                     if (point.y() < gapAndColumnRect.y())
3473                         point = gapAndColumnRect.location();
3474                     // Clamp everything below the column to the next column's top left. If there is
3475                     // no next column, this still maps to just after this column.
3476                     else if (point.y() >= gapAndColumnRect.maxY()) {
3477                         point = gapAndColumnRect.location();
3478                         point.move(0, gapAndColumnRect.height());
3479                     }
3480                 } else {
3481                     if (point.x() < colRect.x())
3482                         point.setX(colRect.x());
3483                     else if (point.x() >= colRect.maxX())
3484                         point.setX(colRect.maxX() - 1);
3485                 }
3486
3487                 // We're inside the column.  Translate the x and y into our column coordinate space.
3488                 if (colInfo->progressionAxis() == ColumnInfo::InlineAxis)
3489                     point.move(columnPoint.x() - colRect.x(), (!style()->isFlippedBlocksWritingMode() ? logicalOffset : -logicalOffset));
3490                 else
3491                     point.move((!style()->isFlippedBlocksWritingMode() ? logicalOffset : -logicalOffset) - colRect.x() + borderLeft() + paddingLeft(), 0);
3492                 return;
3493             }
3494
3495             // Move to the next position.
3496             logicalOffset += colInfo->progressionAxis() == ColumnInfo::InlineAxis ? colRect.height() : colRect.width();
3497         } else {
3498             LayoutRect gapAndColumnRect(colRect.x(), colRect.y() - halfColGap, colRect.width(), colRect.height() + colGap);
3499             if (point.y() >= gapAndColumnRect.y() && point.y() < gapAndColumnRect.maxY()) {
3500                 if (colInfo->progressionAxis() == ColumnInfo::InlineAxis) {
3501                     // FIXME: The clamping that follows is not completely right for right-to-left
3502                     // content.
3503                     // Clamp everything above the column to its top left.
3504                     if (point.x() < gapAndColumnRect.x())
3505                         point = gapAndColumnRect.location();
3506                     // Clamp everything below the column to the next column's top left. If there is
3507                     // no next column, this still maps to just after this column.
3508                     else if (point.x() >= gapAndColumnRect.maxX()) {
3509                         point = gapAndColumnRect.location();
3510                         point.move(gapAndColumnRect.width(), 0);
3511                     }
3512                 } else {
3513                     if (point.y() < colRect.y())
3514                         point.setY(colRect.y());
3515                     else if (point.y() >= colRect.maxY())
3516                         point.setY(colRect.maxY() - 1);
3517                 }
3518
3519                 // We're inside the column.  Translate the x and y into our column coordinate space.
3520                 if (colInfo->progressionAxis() == ColumnInfo::InlineAxis)
3521                     point.move((!style()->isFlippedBlocksWritingMode() ? logicalOffset : -logicalOffset), columnPoint.y() - colRect.y());
3522                 else
3523                     point.move(0, (!style()->isFlippedBlocksWritingMode() ? logicalOffset : -logicalOffset) - colRect.y() + borderTop() + paddingTop());
3524                 return;
3525             }
3526
3527             // Move to the next position.
3528             logicalOffset += colInfo->progressionAxis() == ColumnInfo::InlineAxis ? colRect.width() : colRect.height();
3529         }
3530     }
3531 }
3532
3533 void RenderBlock::adjustRectForColumns(LayoutRect& r) const
3534 {
3535     // Just bail if we have no columns.
3536     if (!hasColumns())
3537         return;
3538
3539     ColumnInfo* colInfo = columnInfo();
3540
3541     // Determine which columns we intersect.
3542     unsigned colCount = columnCount(colInfo);
3543     if (!colCount)
3544         return;
3545
3546     // Begin with a result rect that is empty.
3547     LayoutRect result;
3548
3549     bool isHorizontal = isHorizontalWritingMode();
3550     LayoutUnit beforeBorderPadding = borderBefore() + paddingBefore();
3551     LayoutUnit colHeight = colInfo->columnHeight();
3552     if (!colHeight)
3553         return;
3554
3555     LayoutUnit startOffset = max(isHorizontal ? r.y() : r.x(), beforeBorderPadding);
3556     LayoutUnit endOffset = max(min<LayoutUnit>(isHorizontal ? r.maxY() : r.maxX(), beforeBorderPadding + colCount * colHeight), beforeBorderPadding);
3557
3558     // FIXME: Can overflow on fast/block/float/float-not-removed-from-next-sibling4.html, see https://bugs.webkit.org/show_bug.cgi?id=68744
3559     unsigned startColumn = (startOffset - beforeBorderPadding) / colHeight;
3560     unsigned endColumn = (endOffset - beforeBorderPadding) / colHeight;
3561
3562     if (startColumn == endColumn) {
3563         // The rect is fully contained within one column. Adjust for our offsets
3564         // and repaint only that portion.
3565         LayoutUnit logicalLeftOffset = logicalLeftOffsetForContent();
3566         LayoutRect colRect = columnRectAt(colInfo, startColumn);
3567         LayoutRect repaintRect = r;
3568
3569         if (colInfo->progressionAxis() == ColumnInfo::InlineAxis) {
3570             if (isHorizontal)
3571                 repaintRect.move(colRect.x() - logicalLeftOffset, - static_cast<int>(startColumn) * colHeight);
3572             else
3573                 repaintRect.move(- static_cast<int>(startColumn) * colHeight, colRect.y() - logicalLeftOffset);
3574         } else {
3575             if (isHorizontal)
3576                 repaintRect.move(0, colRect.y() - startColumn * colHeight - beforeBorderPadding);
3577             else
3578                 repaintRect.move(colRect.x() - startColumn * colHeight - beforeBorderPadding, 0);
3579         }
3580         repaintRect.intersect(colRect);
3581         result.unite(repaintRect);
3582     } else {
3583         // We span multiple columns. We can just unite the start and end column to get the final
3584         // repaint rect.
3585         result.unite(columnRectAt(colInfo, startColumn));
3586         result.unite(columnRectAt(colInfo, endColumn));
3587     }
3588
3589     r = result;
3590 }
3591
3592 LayoutPoint RenderBlock::flipForWritingModeIncludingColumns(const LayoutPoint& point) const
3593 {
3594     ASSERT(hasColumns());
3595     if (!hasColumns() || !style()->isFlippedBlocksWritingMode())
3596         return point;
3597     ColumnInfo* colInfo = columnInfo();
3598     LayoutUnit columnLogicalHeight = colInfo->columnHeight();
3599     LayoutUnit expandedLogicalHeight = borderBefore() + paddingBefore() + columnCount(colInfo) * columnLogicalHeight + borderAfter() + paddingAfter() + scrollbarLogicalHeight();
3600     if (isHorizontalWritingMode())
3601         return LayoutPoint(point.x(), expandedLogicalHeight - point.y());
3602     return LayoutPoint(expandedLogicalHeight - point.x(), point.y());
3603 }
3604
3605 void RenderBlock::adjustStartEdgeForWritingModeIncludingColumns(LayoutRect& rect) const
3606 {
3607     ASSERT(hasColumns());
3608     if (!hasColumns() || !style()->isFlippedBlocksWritingMode())
3609         return;
3610
3611     ColumnInfo* colInfo = columnInfo();
3612     LayoutUnit columnLogicalHeight = colInfo->columnHeight();
3613     LayoutUnit expandedLogicalHeight = borderBefore() + paddingBefore() + columnCount(colInfo) * columnLogicalHeight + borderAfter() + paddingAfter() + scrollbarLogicalHeight();
3614
3615     if (isHorizontalWritingMode())
3616         rect.setY(expandedLogicalHeight - rect.maxY());
3617     else
3618         rect.setX(expandedLogicalHeight - rect.maxX());
3619 }
3620
3621 void RenderBlock::adjustForColumns(LayoutSize& offset, const LayoutPoint& point) const
3622 {
3623     if (!hasColumns())
3624         return;
3625
3626     ColumnInfo* colInfo = columnInfo();
3627
3628     LayoutUnit logicalLeft = logicalLeftOffsetForContent();
3629     unsigned colCount = columnCount(colInfo);
3630     LayoutUnit colLogicalWidth = colInfo->desiredColumnWidth();
3631     LayoutUnit colLogicalHeight = colInfo->columnHeight();
3632
3633     for (unsigned i = 0; i < colCount; ++i) {
3634         // Compute the edges for a given column in the block progression direction.
3635         LayoutRect sliceRect = LayoutRect(logicalLeft, borderBefore() + paddingBefore() + i * colLogicalHeight, colLogicalWidth, colLogicalHeight);
3636         if (!isHorizontalWritingMode())
3637             sliceRect = sliceRect.transposedRect();
3638
3639         LayoutUnit logicalOffset = i * colLogicalHeight;
3640
3641         // Now we're in the same coordinate space as the point.  See if it is inside the rectangle.
3642         if (isHorizontalWritingMode()) {
3643             if (point.y() >= sliceRect.y() && point.y() < sliceRect.maxY()) {
3644                 if (colInfo->progressionAxis() == ColumnInfo::InlineAxis)
3645                     offset.expand(columnRectAt(colInfo, i).x() - logicalLeft, -logicalOffset);
3646                 else
3647                     offset.expand(0, columnRectAt(colInfo, i).y() - logicalOffset - borderBefore() - paddingBefore());
3648                 return;
3649             }
3650         } else {
3651             if (point.x() >= sliceRect.x() && point.x() < sliceRect.maxX()) {
3652                 if (colInfo->progressionAxis() == ColumnInfo::InlineAxis)
3653                     offset.expand(-logicalOffset, columnRectAt(colInfo, i).y() - logicalLeft);
3654                 else
3655                     offset.expand(columnRectAt(colInfo, i).x() - logicalOffset - borderBefore() - paddingBefore(), 0);
3656                 return;
3657             }
3658         }
3659     }
3660 }
3661
3662 void RenderBlock::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
3663 {
3664     if (childrenInline()) {
3665         // FIXME: Remove this const_cast.
3666         const_cast<RenderBlock*>(this)->computeInlinePreferredLogicalWidths(minLogicalWidth, maxLogicalWidth);
3667     } else
3668         computeBlockPreferredLogicalWidths(minLogicalWidth, maxLogicalWidth);
3669
3670     maxLogicalWidth = max(minLogicalWidth, maxLogicalWidth);
3671
3672     adjustIntrinsicLogicalWidthsForColumns(minLogicalWidth, maxLogicalWidth);
3673
3674     // A horizontal marquee with inline children has no minimum width.
3675     if (childrenInline() && isMarquee() && toRenderMarquee(this)->isHorizontal())
3676         minLogicalWidth = 0;
3677
3678     if (isTableCell()) {
3679         Length tableCellWidth = toRenderTableCell(this)->styleOrColLogicalWidth();
3680         if (tableCellWidth.isFixed() && tableCellWidth.value() > 0)
3681             maxLogicalWidth = max(minLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(tableCellWidth.value()));
3682     }
3683
3684     int scrollbarWidth = instrinsicScrollbarLogicalWidth();
3685     maxLogicalWidth += scrollbarWidth;
3686     minLogicalWidth += scrollbarWidth;
3687 }
3688
3689 void RenderBlock::computePreferredLogicalWidths()
3690 {
3691     ASSERT(preferredLogicalWidthsDirty());
3692
3693     updateFirstLetter();
3694
3695     m_minPreferredLogicalWidth = 0;
3696     m_maxPreferredLogicalWidth = 0;
3697
3698     // FIXME: The isFixed() calls here should probably be checking for isSpecified since you
3699     // should be able to use percentage, calc or viewport relative values for width.
3700     RenderStyle* styleToUse = style();
3701     if (!isTableCell() && styleToUse->logicalWidth().isFixed() && styleToUse->logicalWidth().value() >= 0
3702         && !(isDeprecatedFlexItem() && !styleToUse->logicalWidth().intValue()))
3703         m_minPreferredLogicalWidth = m_maxPreferredLogicalWidth = adjustContentBoxLogicalWidthForBoxSizing(styleToUse->logicalWidth().value());
3704     else
3705         computeIntrinsicLogicalWidths(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
3706
3707     if (styleToUse->logicalMinWidth().isFixed() && styleToUse->logicalMinWidth().value() > 0) {
3708         m_maxPreferredLogicalWidth = max(m_maxPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(styleToUse->logicalMinWidth().value()));
3709         m_minPreferredLogicalWidth = max(m_minPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(styleToUse->logicalMinWidth().value()));
3710     }
3711
3712     if (styleToUse->logicalMaxWidth().isFixed()) {
3713         m_maxPreferredLogicalWidth = min(m_maxPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(styleToUse->logicalMaxWidth().value()));
3714         m_minPreferredLogicalWidth = min(m_minPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(styleToUse->logicalMaxWidth().value()));
3715     }
3716
3717     // Table layout uses integers, ceil the preferred widths to ensure that they can contain the contents.
3718     if (isTableCell()) {
3719         m_minPreferredLogicalWidth = m_minPreferredLogicalWidth.ceil();
3720         m_maxPreferredLogicalWidth = m_maxPreferredLogicalWidth.ceil();
3721     }
3722
3723     LayoutUnit borderAndPadding = borderAndPaddingLogicalWidth();
3724     m_minPreferredLogicalWidth += borderAndPadding;
3725     m_maxPreferredLogicalWidth += borderAndPadding;
3726
3727     clearPreferredLogicalWidthsDirty();
3728 }
3729
3730 void RenderBlock::adjustIntrinsicLogicalWidthsForColumns(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
3731 {
3732     // FIXME: make this method virtual and move the code to RenderMultiColumnBlock once the old
3733     // multicol code is gone.
3734
3735     if (!style()->hasAutoColumnCount() || !style()->hasAutoColumnWidth()) {
3736         // The min/max intrinsic widths calculated really tell how much space elements need when
3737         // laid out inside the columns. In order to eventually end up with the desired column width,
3738         // we need to convert them to values pertaining to the multicol container.
3739         int columnCount = style()->hasAutoColumnCount() ? 1 : style()->columnCount();
3740         LayoutUnit columnWidth;
3741         LayoutUnit gapExtra = (columnCount - 1) * columnGap();
3742         if (style()->hasAutoColumnWidth()) {
3743             minLogicalWidth = minLogicalWidth * columnCount + gapExtra;
3744         } else {
3745             columnWidth = style()->columnWidth();
3746             minLogicalWidth = min(minLogicalWidth, columnWidth);
3747         }
3748         // FIXME: If column-count is auto here, we should resolve it to calculate the maximum
3749         // intrinsic width, instead of pretending that it's 1. The only way to do that is by
3750         // performing a layout pass, but this is not an appropriate time or place for layout. The
3751         // good news is that if height is unconstrained and there are no explicit breaks, the
3752         // resolved column-count really should be 1.
3753         maxLogicalWidth = max(maxLogicalWidth, columnWidth) * columnCount + gapExtra;
3754     }
3755 }
3756
3757 struct InlineMinMaxIterator {
3758 /* InlineMinMaxIterator is a class that will iterate over all render objects that contribute to
3759    inline min/max width calculations.  Note the following about the way it walks:
3760    (1) Positioned content is skipped (since it does not contribute to min/max width of a block)
3761    (2) We do not drill into the children of floats or replaced elements, since you can't break
3762        in the middle of such an element.
3763    (3) Inline flows (e.g., <a>, <span>, <i>) are walked twice, since each side can have
3764        distinct borders/margin/padding that contribute to the min/max width.
3765 */
3766     RenderObject* parent;
3767     RenderObject* current;
3768     bool endOfInline;
3769
3770     InlineMinMaxIterator(RenderObject* p, bool end = false)
3771         :parent(p), current(p), endOfInline(end) {}
3772
3773     RenderObject* next();
3774 };
3775
3776 RenderObject* InlineMinMaxIterator::next()
3777 {
3778     RenderObject* result = 0;
3779     bool oldEndOfInline = endOfInline;
3780     endOfInline = false;
3781     while (current || current == parent) {
3782         if (!oldEndOfInline &&
3783             (current == parent ||
3784              (!current->isFloating() && !current->isReplaced() && !current->isOutOfFlowPositioned())))
3785             result = current->firstChild();
3786         if (!result) {
3787             // We hit the end of our inline. (It was empty, e.g., <span></span>.)
3788             if (!oldEndOfInline && current->isRenderInline()) {
3789                 result = current;
3790                 endOfInline = true;
3791                 break;
3792             }
3793
3794             while (current && current != parent) {
3795                 result = current->nextSibling();
3796                 if (result) break;
3797                 current = current->parent();
3798                 if (current && current != parent && current->isRenderInline()) {
3799                     result = current;
3800                     endOfInline = true;
3801                     break;
3802                 }
3803             }
3804         }
3805
3806         if (!result)
3807             break;
3808
3809         if (!result->isOutOfFlowPositioned() && (result->isText() || result->isFloating() || result->isReplaced() || result->isRenderInline()))
3810              break;
3811
3812         current = result;
3813         result = 0;
3814     }
3815
3816     // Update our position.
3817     current = result;
3818     return current;
3819 }
3820
3821 static LayoutUnit getBPMWidth(LayoutUnit childValue, Length cssUnit)
3822 {
3823     if (cssUnit.type() != Auto)
3824         return (cssUnit.isFixed() ? static_cast<LayoutUnit>(cssUnit.value()) : childValue);
3825     return 0;
3826 }
3827
3828 static LayoutUnit getBorderPaddingMargin(const RenderBoxModelObject* child, bool endOfInline)
3829 {
3830     RenderStyle* childStyle = child->style();
3831     if (endOfInline)
3832         return getBPMWidth(child->marginEnd(), childStyle->marginEnd()) +
3833                getBPMWidth(child->paddingEnd(), childStyle->paddingEnd()) +
3834                child->borderEnd();
3835     return getBPMWidth(child->marginStart(), childStyle->marginStart()) +
3836                getBPMWidth(child->paddingStart(), childStyle->paddingStart()) +
3837                child->borderStart();
3838 }
3839
3840 static inline void stripTrailingSpace(float& inlineMax, float& inlineMin,
3841                                       RenderObject* trailingSpaceChild)
3842 {
3843     if (trailingSpaceChild && trailingSpaceChild->isText()) {
3844         // Collapse away the trailing space at the end of a block.
3845         RenderText* t = toRenderText(trailingSpaceChild);
3846         const UChar space = ' ';
3847         const Font& font = t->style()->font(); // FIXME: This ignores first-line.
3848         float spaceWidth = font.width(RenderBlockFlow::constructTextRun(t, font, &space, 1, t->style(), LTR));
3849         inlineMax -= spaceWidth + font.fontDescription().wordSpacing();
3850         if (inlineMin > inlineMax)
3851             inlineMin = inlineMax;
3852     }
3853 }
3854
3855 static inline void updatePreferredWidth(LayoutUnit& preferredWidth, float& result)
3856 {
3857     LayoutUnit snappedResult = LayoutUnit::fromFloatCeil(result);
3858     preferredWidth = max(snappedResult, preferredWidth);
3859 }
3860
3861 // When converting between floating point and LayoutUnits we risk losing precision
3862 // with each conversion. When this occurs while accumulating our preferred widths,
3863 // we can wind up with a line width that's larger than our maxPreferredWidth due to
3864 // pure float accumulation.
3865 static inline LayoutUnit adjustFloatForSubPixelLayout(float value)
3866 {
3867     return LayoutUnit::fromFloatCeil(value);
3868 }
3869
3870
3871 void RenderBlock::computeInlinePreferredLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth)
3872 {
3873     float inlineMax = 0;
3874     float inlineMin = 0;
3875
3876     RenderStyle* styleToUse = style();
3877     RenderBlock* containingBlock = this->containingBlock();
3878     LayoutUnit cw = containingBlock ? containingBlock->contentLogicalWidth() : LayoutUnit();
3879
3880     // If we are at the start of a line, we want to ignore all white-space.
3881     // Also strip spaces if we previously had text that ended in a trailing space.
3882     bool stripFrontSpaces = true;
3883     RenderObject* trailingSpaceChild = 0;
3884
3885     // Firefox and Opera will allow a table cell to grow to fit an image inside it under
3886     // very specific cirucumstances (in order to match common WinIE renderings).
3887     // Not supporting the quirk has caused us to mis-render some real sites. (See Bugzilla 10517.)
3888     bool allowImagesToBreak = !document().inQuirksMode() || !isTableCell() || !styleToUse->logicalWidth().isIntrinsicOrAuto();
3889
3890     bool autoWrap, oldAutoWrap;
3891     autoWrap = oldAutoWrap = styleToUse->autoWrap();
3892
3893     InlineMinMaxIterator childIterator(this);
3894
3895     // Only gets added to the max preffered width once.
3896     bool addedTextIndent = false;
3897     // Signals the text indent was more negative than the min preferred width
3898     bool hasRemainingNegativeTextIndent = false;
3899
3900     LayoutUnit textIndent = minimumValueForLength(styleToUse->textIndent(), cw);
3901     RenderObject* prevFloat = 0;
3902     bool isPrevChildInlineFlow = false;
3903     bool shouldBreakLineAfterText = false;
3904     while (RenderObject* child = childIterator.next()) {
3905         autoWrap = child->isReplaced() ? child->parent()->style()->autoWrap() :
3906             child->style()->autoWrap();
3907
3908         if (!child->isBR()) {
3909             // Step One: determine whether or not we need to go ahead and
3910             // terminate our current line.  Each discrete chunk can become
3911             // the new min-width, if it is the widest chunk seen so far, and
3912             // it can also become the max-width.
3913
3914             // Children fall into three categories:
3915             // (1) An inline flow object.  These objects always have a min/max of 0,
3916             // and are included in the iteration solely so that their margins can
3917             // be added in.
3918             //
3919             // (2) An inline non-text non-flow object, e.g., an inline replaced element.
3920             // These objects can always be on a line by themselves, so in this situation
3921             // we need to go ahead and break the current line, and then add in our own
3922             // margins and min/max width on its own line, and then terminate the line.
3923             //
3924             // (3) A text object.  Text runs can have breakable characters at the start,
3925             // the middle or the end.  They may also lose whitespace off the front if
3926             // we're already ignoring whitespace.  In order to compute accurate min-width
3927             // information, we need three pieces of information.
3928             // (a) the min-width of the first non-breakable run.  Should be 0 if the text string
3929             // starts with whitespace.
3930             // (b) the min-width of the last non-breakable run. Should be 0 if the text string
3931             // ends with whitespace.
3932             // (c) the min/max width of the string (trimmed for whitespace).
3933             //
3934             // If the text string starts with whitespace, then we need to go ahead and
3935             // terminate our current line (unless we're already in a whitespace stripping
3936             // mode.
3937             //
3938             // If the text string has a breakable character in the middle, but didn't start
3939             // with whitespace, then we add the width of the first non-breakable run and
3940             // then end the current line.  We then need to use the intermediate min/max width
3941             // values (if any of them are larger than our current min/max).  We then look at
3942             // the width of the last non-breakable run and use that to start a new line
3943             // (unless we end in whitespace).
3944             RenderStyle* childStyle = child->style();
3945             float childMin = 0;
3946             float childMax = 0;
3947
3948             if (!child->isText()) {
3949                 // Case (1) and (2).  Inline replaced and inline flow elements.
3950                 if (child->isRenderInline()) {
3951                     // Add in padding/border/margin from the appropriate side of
3952                     // the element.
3953                     float bpm = getBorderPaddingMargin(toRenderInline(child), childIterator.endOfInline);
3954                     childMin += bpm;
3955                     childMax += bpm;
3956
3957                     inlineMin += childMin;
3958                     inlineMax += childMax;
3959
3960                     child->clearPreferredLogicalWidthsDirty();
3961                 } else {
3962                     // Inline replaced elts add in their margins to their min/max values.
3963                     LayoutUnit margins = 0;
3964                     Length startMargin = childStyle->marginStart();
3965                     Length endMargin = childStyle->marginEnd();
3966                     if (startMargin.isFixed())
3967                         margins += adjustFloatForSubPixelLayout(startMargin.value());
3968                     if (endMargin.isFixed())
3969                         margins += adjustFloatForSubPixelLayout(endMargin.value());
3970                     childMin += margins.ceilToFloat();
3971                     childMax += margins.ceilToFloat();
3972                 }
3973             }
3974
3975             if (!child->isRenderInline() && !child->isText()) {
3976                 // Case (2). Inline replaced elements and floats.
3977                 // Go ahead and terminate the current line as far as
3978                 // minwidth is concerned.
3979                 LayoutUnit childMinPreferredLogicalWidth, childMaxPreferredLogicalWidth;
3980                 if (child->isBox() && child->isHorizontalWritingMode() != isHorizontalWritingMode()) {
3981                     RenderBox* childBox = toRenderBox(child);
3982                     LogicalExtentComputedValues computedValues;
3983                     childBox->computeLogicalHeight(childBox->borderAndPaddingLogicalHeight(), 0, computedValues);
3984                     childMinPreferredLogicalWidth = childMaxPreferredLogicalWidth = computedValues.m_extent;
3985                 } else {
3986                     childMinPreferredLogicalWidth = child->minPreferredLogicalWidth();
3987                     childMaxPreferredLogicalWidth = child->maxPreferredLogicalWidth();
3988                 }
3989                 childMin += childMinPreferredLogicalWidth.ceilToFloat();
3990                 childMax += childMaxPreferredLogicalWidth.ceilToFloat();
3991
3992                 bool clearPreviousFloat;
3993                 if (child->isFloating()) {
3994                     clearPreviousFloat = (prevFloat
3995                         && ((prevFloat->style()->floating() == LeftFloat && (childStyle->clear() & CLEFT))
3996                             || (prevFloat->style()->floating() == RightFloat && (childStyle->clear() & CRIGHT))));
3997                     prevFloat = child;
3998                 } else
3999                     clearPreviousFloat = false;
4000
4001                 bool canBreakReplacedElement = !child->isImage() || allowImagesToBreak;
4002                 if ((canBreakReplacedElement && (autoWrap || oldAutoWrap) && (!isPrevChildInlineFlow || shouldBreakLineAfterText)) || clearPreviousFloat) {
4003                     updatePreferredWidth(minLogicalWidth, inlineMin);
4004                     inlineMin = 0;
4005                 }
4006
4007                 // If we're supposed to clear the previous float, then terminate maxwidth as well.
4008                 if (clearPreviousFloat) {
4009                     updatePreferredWidth(maxLogicalWidth, inlineMax);
4010                     inlineMax = 0;
4011                 }
4012
4013                 // Add in text-indent.  This is added in only once.
4014                 if (!addedTextIndent && !child->isFloating()) {
4015                     float ceiledTextIndent = textIndent.ceilToFloat();
4016                     childMin += ceiledTextIndent;
4017                     childMax += ceiledTextIndent;
4018
4019                     if (childMin < 0)
4020                         textIndent = adjustFloatForSubPixelLayout(childMin);
4021                     else
4022                         addedTextIndent = true;
4023                 }
4024
4025                 // Add our width to the max.
4026                 inlineMax += max<float>(0, childMax);
4027
4028                 if (!autoWrap || !canBreakReplacedElement || (isPrevChildInlineFlow && !shouldBreakLineAfterText)) {
4029                     if (child->isFloating())
4030                         updatePreferredWidth(minLogicalWidth, childMin);
4031                     else
4032                         inlineMin += childMin;
4033                 } else {
4034                     // Now check our line.
4035                     updatePreferredWidth(minLogicalWidth, childMin);
4036
4037                     // Now start a new line.
4038                     inlineMin = 0;
4039                 }
4040
4041                 if (autoWrap && canBreakReplacedElement && isPrevChildInlineFlow) {
4042                     updatePreferredWidth(minLogicalWidth, inlineMin);
4043                     inlineMin = 0;
4044                 }
4045
4046                 // We are no longer stripping whitespace at the start of
4047                 // a line.
4048                 if (!child->isFloating()) {
4049                     stripFrontSpaces = false;
4050                     trailingSpaceChild = 0;
4051                 }
4052             } else if (child->isText()) {
4053                 // Case (3). Text.
4054                 RenderText* t = toRenderText(child);
4055
4056                 if (t->isWordBreak()) {
4057                     updatePreferredWidth(minLogicalWidth, inlineMin);
4058                     inlineMin = 0;
4059                     continue;
4060                 }
4061
4062                 if (t->style()->hasTextCombine() && t->isCombineText())
4063                     toRenderCombineText(t)->combineText();
4064
4065                 // Determine if we have a breakable character.  Pass in
4066                 // whether or not we should ignore any spaces at the front
4067                 // of the string.  If those are going to be stripped out,
4068                 // then they shouldn't be considered in the breakable char
4069                 // check.
4070                 bool hasBreakableChar, hasBreak;
4071                 float firstLineMinWidth, lastLineMinWidth;
4072                 bool hasBreakableStart, hasBreakableEnd;
4073                 float firstLineMaxWidth, lastLineMaxWidth;
4074                 t->trimmedPrefWidths(inlineMax,
4075                     firstLineMinWidth, hasBreakableStart, lastLineMinWidth, hasBreakableEnd,
4076                     hasBreakableChar, hasBreak, firstLineMaxWidth, lastLineMaxWidth,
4077                     childMin, childMax, stripFrontSpaces, styleToUse->direction());
4078
4079                 // This text object will not be rendered, but it may still provide a breaking opportunity.
4080                 if (!hasBreak && childMax == 0) {
4081                     if (autoWrap && (hasBreakableStart || hasBreakableEnd)) {
4082                         updatePreferredWidth(minLogicalWidth, inlineMin);
4083                         inlineMin = 0;
4084                     }
4085                     continue;
4086                 }
4087
4088                 if (stripFrontSpaces)
4089                     trailingSpaceChild = child;
4090                 else
4091                     trailingSpaceChild = 0;
4092
4093                 // Add in text-indent.  This is added in only once.
4094                 float ti = 0;
4095                 if (!addedTextIndent || hasRemainingNegativeTextIndent) {
4096                     ti = textIndent.ceilToFloat();
4097                     childMin += ti;
4098                     firstLineMinWidth += ti;
4099
4100                     // It the text indent negative and larger than the child minimum, we re-use the remainder
4101                     // in future minimum calculations, but using the negative value again on the maximum
4102                     // will lead to under-counting the max pref width.
4103                     if (!addedTextIndent) {
4104                         childMax += ti;
4105                         firstLineMaxWidth += ti;
4106                         addedTextIndent = true;
4107                     }
4108
4109                     if (childMin < 0) {
4110                         textIndent = childMin;
4111                         hasRemainingNegativeTextIndent = true;
4112                     }
4113                 }
4114
4115                 // If we have no breakable characters at all,
4116                 // then this is the easy case. We add ourselves to the current
4117                 // min and max and continue.
4118                 if (!hasBreakableChar) {
4119                     inlineMin += childMin;
4120                 } else {
4121                     if (hasBreakableStart) {
4122                         updatePreferredWidth(minLogicalWidth, inlineMin);
4123                     } else {
4124                         inlineMin += firstLineMinWidth;
4125                         updatePreferredWidth(minLogicalWidth, inlineMin);
4126                         childMin -= ti;
4127                     }
4128
4129                     inlineMin = childMin;
4130
4131                     if (hasBreakableEnd) {
4132                         updatePreferredWidth(minLogicalWidth, inlineMin);
4133                         inlineMin = 0;
4134                         shouldBreakLineAfterText = false;
4135                     } else {
4136                         updatePreferredWidth(minLogicalWidth, inlineMin);
4137                         inlineMin = lastLineMinWidth;
4138                         shouldBreakLineAfterText = true;
4139                     }
4140                 }
4141
4142                 if (hasBreak) {
4143                     inlineMax += firstLineMaxWidth;
4144                     updatePreferredWidth(maxLogicalWidth, inlineMax);
4145                     updatePreferredWidth(maxLogicalWidth, childMax);
4146                     inlineMax = lastLineMaxWidth;
4147                     addedTextIndent = true;
4148                 } else {
4149                     inlineMax += max<float>(0, childMax);
4150                 }
4151             }
4152
4153             // Ignore spaces after a list marker.
4154             if (child->isListMarker())
4155                 stripFrontSpaces = true;
4156         } else {
4157             updatePreferredWidth(minLogicalWidth, inlineMin);
4158             updatePreferredWidth(maxLogicalWidth, inlineMax);
4159             inlineMin = inlineMax = 0;
4160             stripFrontSpaces = true;
4161             trailingSpaceChild = 0;
4162             addedTextIndent = true;
4163         }
4164
4165         if (!child->isText() && child->isRenderInline())
4166             isPrevChildInlineFlow = true;
4167         else
4168             isPrevChildInlineFlow = false;
4169
4170         oldAutoWrap = autoWrap;
4171     }
4172
4173     if (styleToUse->collapseWhiteSpace())
4174         stripTrailingSpace(inlineMax, inlineMin, trailingSpaceChild);
4175
4176     updatePreferredWidth(minLogicalWidth, inlineMin);
4177     updatePreferredWidth(maxLogicalWidth, inlineMax);
4178 }
4179
4180 void RenderBlock::computeBlockPreferredLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
4181 {
4182     RenderStyle* styleToUse = style();
4183     bool nowrap = styleToUse->whiteSpace() == NOWRAP;
4184
4185     RenderObject* child = firstChild();
4186     RenderBlock* containingBlock = this->containingBlock();
4187     LayoutUnit floatLeftWidth = 0, floatRightWidth = 0;
4188     while (child) {
4189         // Positioned children don't affect the min/max width
4190         if (child->isOutOfFlowPositioned()) {
4191             child = child->nextSibling();
4192             continue;
4193         }
4194
4195         RenderStyle* childStyle = child->style();
4196         if (child->isFloating() || (child->isBox() && toRenderBox(child)->avoidsFloats())) {
4197             LayoutUnit floatTotalWidth = floatLeftWidth + floatRightWidth;
4198             if (childStyle->clear() & CLEFT) {
4199                 maxLogicalWidth = max(floatTotalWidth, maxLogicalWidth);
4200                 floatLeftWidth = 0;
4201             }
4202             if (childStyle->clear() & CRIGHT) {
4203                 maxLogicalWidth = max(floatTotalWidth, maxLogicalWidth);
4204                 floatRightWidth = 0;
4205             }
4206         }
4207
4208         // A margin basically has three types: fixed, percentage, and auto (variable).
4209         // Auto and percentage margins simply become 0 when computing min/max width.
4210         // Fixed margins can be added in as is.
4211         Length startMarginLength = childStyle->marginStartUsing(styleToUse);
4212         Length endMarginLength = childStyle->marginEndUsing(styleToUse);
4213         LayoutUnit margin = 0;
4214         LayoutUnit marginStart = 0;
4215         LayoutUnit marginEnd = 0;
4216         if (startMarginLength.isFixed())
4217             marginStart += startMarginLength.value();
4218         if (endMarginLength.isFixed())
4219             marginEnd += endMarginLength.value();
4220         margin = marginStart + marginEnd;
4221
4222         LayoutUnit childMinPreferredLogicalWidth, childMaxPreferredLogicalWidth;
4223         if (child->isBox() && child->isHorizontalWritingMode() != isHorizontalWritingMode()) {
4224             RenderBox* childBox = toRenderBox(child);
4225             LogicalExtentComputedValues computedValues;
4226             childBox->computeLogicalHeight(childBox->borderAndPaddingLogicalHeight(), 0, computedValues);
4227             childMinPreferredLogicalWidth = childMaxPreferredLogicalWidth = computedValues.m_extent;
4228         } else {
4229             childMinPreferredLogicalWidth = child->minPreferredLogicalWidth();
4230             childMaxPreferredLogicalWidth = child->maxPreferredLogicalWidth();
4231         }
4232
4233         LayoutUnit w = childMinPreferredLogicalWidth + margin;
4234         minLogicalWidth = max(w, minLogicalWidth);
4235
4236         // IE ignores tables for calculation of nowrap. Makes some sense.
4237         if (nowrap && !child->isTable())
4238             maxLogicalWidth = max(w, maxLogicalWidth);
4239
4240         w = childMaxPreferredLogicalWidth + margin;
4241
4242         if (!child->isFloating()) {
4243             if (child->isBox() && toRenderBox(child)->avoidsFloats()) {
4244                 // Determine a left and right max value based off whether or not the floats can fit in the
4245                 // margins of the object.  For negative margins, we will attempt to overlap the float if the negative margin
4246                 // is smaller than the float width.
4247                 bool ltr = containingBlock ? containingBlock->style()->isLeftToRightDirection() : styleToUse->isLeftToRightDirection();
4248                 LayoutUnit marginLogicalLeft = ltr ? marginStart : marginEnd;
4249                 LayoutUnit marginLogicalRight = ltr ? marginEnd : marginStart;
4250                 LayoutUnit maxLeft = marginLogicalLeft > 0 ? max(floatLeftWidth, marginLogicalLeft) : floatLeftWidth + marginLogicalLeft;
4251                 LayoutUnit maxRight = marginLogicalRight > 0 ? max(floatRightWidth, marginLogicalRight) : floatRightWidth + marginLogicalRight;
4252                 w = childMaxPreferredLogicalWidth + maxLeft + maxRight;
4253                 w = max(w, floatLeftWidth + floatRightWidth);
4254             }
4255             else
4256                 maxLogicalWidth = max(floatLeftWidth + floatRightWidth, maxLogicalWidth);
4257             floatLeftWidth = floatRightWidth = 0;
4258         }
4259
4260         if (child->isFloating()) {
4261             if (childStyle->floating() == LeftFloat)
4262                 floatLeftWidth += w;
4263             else
4264                 floatRightWidth += w;
4265         } else
4266             maxLogicalWidth = max(w, maxLogicalWidth);
4267
4268         child = child->nextSibling();
4269     }
4270
4271     // Always make sure these values are non-negative.
4272     minLogicalWidth = max<LayoutUnit>(0, minLogicalWidth);
4273     maxLogicalWidth = max<LayoutUnit>(0, maxLogicalWidth);
4274
4275     maxLogicalWidth = max(floatLeftWidth + floatRightWidth, maxLogicalWidth);
4276 }
4277
4278 bool RenderBlock::hasLineIfEmpty() const
4279 {
4280     if (!node())
4281         return false;
4282
4283     if (node()->isRootEditableElement())
4284         return true;
4285
4286     if (node()->isShadowRoot() && toShadowRoot(node())->host()->hasTagName(inputTag))
4287         return true;
4288
4289     return false;
4290 }
4291
4292 LayoutUnit RenderBlock::lineHeight(bool firstLine, LineDirectionMode direction, LinePositionMode linePositionMode) const
4293 {
4294     // Inline blocks are replaced elements. Otherwise, just pass off to
4295     // the base class.  If we're being queried as though we're the root line
4296     // box, then the fact that we're an inline-block is irrelevant, and we behave
4297     // just like a block.
4298     if (isReplaced() && linePositionMode == PositionOnContainingLine)
4299         return RenderBox::lineHeight(firstLine, direction, linePositionMode);
4300
4301     if (firstLine && document().styleEngine()->usesFirstLineRules()) {
4302         RenderStyle* s = style(firstLine);
4303         if (s != style())
4304             return s->computedLineHeight();
4305     }
4306
4307     if (m_lineHeight == -1)
4308         m_lineHeight = style()->computedLineHeight();
4309
4310     return m_lineHeight;
4311 }
4312
4313 int RenderBlock::beforeMarginInLineDirection(LineDirectionMode direction) const
4314 {
4315     return direction == HorizontalLine ? marginTop() : marginRight();
4316 }
4317
4318 int RenderBlock::baselinePosition(FontBaseline baselineType, bool firstLine, LineDirectionMode direction, LinePositionMode linePositionMode) const
4319 {
4320     // Inline blocks are replaced elements. Otherwise, just pass off to
4321     // the base class.  If we're being queried as though we're the root line
4322     // box, then the fact that we're an inline-block is irrelevant, and we behave
4323     // just like a block.
4324     if (isInline() && linePositionMode == PositionOnContainingLine) {
4325         // For "leaf" theme objects, let the theme decide what the baseline position is.
4326         // FIXME: Might be better to have a custom CSS property instead, so that if the theme
4327         // is turned off, checkboxes/radios will still have decent baselines.
4328         // FIXME: Need to patch form controls to deal with vertical lines.
4329         if (style()->hasAppearance() && !RenderTheme::theme().isControlContainer(style()->appearance()))
4330             return RenderTheme::theme().baselinePosition(this);
4331
4332         // CSS2.1 states that the baseline of an inline block is the baseline of the last line box in
4333         // the normal flow.  We make an exception for marquees, since their baselines are meaningless
4334         // (the content inside them moves).  This matches WinIE as well, which just bottom-aligns them.
4335         // We also give up on finding a baseline if we have a vertical scrollbar, or if we are scrolled
4336         // vertically (e.g., an overflow:hidden block that has had scrollTop moved).
4337         bool ignoreBaseline = (layer() && layer()->scrollableArea() && (isMarquee() || (direction == HorizontalLine ? (layer()->scrollableArea()->verticalScrollbar() || layer()->scrollableArea()->scrollYOffset())
4338             : (layer()->scrollableArea()->horizontalScrollbar() || layer()->scrollableArea()->scrollXOffset())))) || (isWritingModeRoot() && !isRubyRun());
4339
4340         int baselinePos = ignoreBaseline ? -1 : inlineBlockBaseline(direction);
4341
4342         if (isDeprecatedFlexibleBox()) {
4343             // Historically, we did this check for all baselines. But we can't
4344             // remove this code from deprecated flexbox, because it effectively
4345             // breaks -webkit-line-clamp, which is used in the wild -- we would
4346             // calculate the baseline as if -webkit-line-clamp wasn't used.
4347             // For simplicity, we use this for all uses of deprecated flexbox.
4348             LayoutUnit bottomOfContent = direction == HorizontalLine ? borderTop() + paddingTop() + contentHeight() : borderRight() + paddingRight() + contentWidth();
4349             if (baselinePos > bottomOfContent)
4350                 baselinePos = -1;
4351         }
4352         if (baselinePos != -1)
4353             return beforeMarginInLineDirection(direction) + baselinePos;
4354
4355         return RenderBox::baselinePosition(baselineType, firstLine, direction, linePositionMode);
4356     }
4357
4358     // If we're not replaced, we'll only get called with PositionOfInteriorLineBoxes.
4359     // Note that inline-block counts as replaced here.
4360     ASSERT(linePositionMode == PositionOfInteriorLineBoxes);
4361
4362     const FontMetrics& fontMetrics = style(firstLine)->fontMetrics();
4363     return fontMetrics.ascent(baselineType) + (lineHeight(firstLine, direction, linePositionMode) - fontMetrics.height()) / 2;
4364 }
4365
4366 LayoutUnit RenderBlock::minLineHeightForReplacedRenderer(bool isFirstLine, LayoutUnit replacedHeight) const
4367 {
4368     if (!document().inNoQuirksMode() && replacedHeight)
4369         return replacedHeight;
4370
4371     if (!(style(isFirstLine)->lineBoxContain() & LineBoxContainBlock))
4372         return 0;
4373
4374     return std::max<LayoutUnit>(replacedHeight, lineHeight(isFirstLine, isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes));
4375 }
4376
4377 int RenderBlock::firstLineBoxBaseline() const
4378 {
4379     if (isWritingModeRoot() && !isRubyRun())
4380         return -1;
4381
4382     if (childrenInline()) {
4383         if (firstLineBox())
4384             return firstLineBox()->logicalTop() + style(true)->fontMetrics().ascent(firstRootBox()->baselineType());
4385         else
4386             return -1;
4387     }
4388     else {
4389         for (RenderBox* curr = firstChildBox(); curr; curr = curr->nextSiblingBox()) {
4390             if (!curr->isFloatingOrOutOfFlowPositioned()) {
4391                 int result = curr->firstLineBoxBaseline();
4392                 if (result != -1)
4393                     return curr->logicalTop() + result; // Translate to our coordinate space.
4394             }
4395         }
4396     }
4397
4398     return -1;
4399 }
4400
4401 int RenderBlock::inlineBlockBaseline(LineDirectionMode direction) const
4402 {
4403     if (!style()->isOverflowVisible()) {
4404         // We are not calling RenderBox::baselinePosition here because the caller should add the margin-top/margin-right, not us.
4405         return direction == HorizontalLine ? height() + m_marginBox.bottom() : width() + m_marginBox.left();
4406     }
4407
4408     return lastLineBoxBaseline(direction);
4409 }
4410
4411 int RenderBlock::lastLineBoxBaseline(LineDirectionMode lineDirection) const
4412 {
4413     if (isWritingModeRoot() && !isRubyRun())
4414         return -1;
4415
4416     if (childrenInline()) {
4417         if (!firstLineBox() && hasLineIfEmpty()) {
4418             const FontMetrics& fontMetrics = firstLineStyle()->fontMetrics();
4419             return fontMetrics.ascent()
4420                  + (lineHeight(true, lineDirection, PositionOfInteriorLineBoxes) - fontMetrics.height()) / 2
4421                  + (lineDirection == HorizontalLine ? borderTop() + paddingTop() : borderRight() + paddingRight());
4422         }
4423         if (lastLineBox())
4424             return lastLineBox()->logicalTop() + style(lastLineBox() == firstLineBox())->fontMetrics().ascent(lastRootBox()->baselineType());
4425         return -1;
4426     } else {
4427         bool haveNormalFlowChild = false;
4428         for (RenderBox* curr = lastChildBox(); curr; curr = curr->previousSiblingBox()) {
4429             if (!curr->isFloatingOrOutOfFlowPositioned()) {
4430                 haveNormalFlowChild = true;
4431                 int result = curr->inlineBlockBaseline(lineDirection);
4432                 if (result != -1)
4433                     return curr->logicalTop() + result; // Translate to our coordinate space.
4434             }
4435         }
4436         if (!haveNormalFlowChild && hasLineIfEmpty()) {
4437             const FontMetrics& fontMetrics = firstLineStyle()->fontMetrics();
4438             return fontMetrics.ascent()
4439                  + (lineHeight(true, lineDirection, PositionOfInteriorLineBoxes) - fontMetrics.height()) / 2
4440                  + (lineDirection == HorizontalLine ? borderTop() + paddingTop() : borderRight() + paddingRight());
4441         }
4442     }
4443
4444     return -1;
4445 }
4446
4447 RenderBlock* RenderBlock::firstLineBlock() const
4448 {
4449     RenderBlock* firstLineBlock = const_cast<RenderBlock*>(this);
4450     bool hasPseudo = false;
4451     while (true) {
4452         hasPseudo = firstLineBlock->style()->hasPseudoStyle(FIRST_LINE);
4453         if (hasPseudo)
4454             break;
4455         RenderObject* parentBlock = firstLineBlock->parent();
4456         // We include isRenderButton in this check because buttons are
4457         // implemented using flex box but should still support first-line. The
4458         // flex box spec requires that flex box does not support first-line,
4459         // though.
4460         // FIXME: Remove when buttons are implemented with align-items instead
4461         // of flexbox.
4462         if (firstLineBlock->isReplaced() || firstLineBlock->isFloating()
4463             || !parentBlock || parentBlock->firstChild() != firstLineBlock
4464             || (!parentBlock->isRenderBlockFlow() && !parentBlock->isRenderButton()))
4465             break;
4466         ASSERT_WITH_SECURITY_IMPLICATION(parentBlock->isRenderBlock());
4467         firstLineBlock = toRenderBlock(parentBlock);
4468     }
4469
4470     if (!hasPseudo)
4471         return 0;
4472
4473     return firstLineBlock;
4474 }
4475
4476 static RenderStyle* styleForFirstLetter(RenderObject* firstLetterBlock, RenderObject* firstLetterContainer)
4477 {
4478     RenderStyle* pseudoStyle = firstLetterBlock->getCachedPseudoStyle(FIRST_LETTER, firstLetterContainer->firstLineStyle());
4479     // Force inline display (except for floating first-letters).
4480     pseudoStyle->setDisplay(pseudoStyle->isFloating() ? BLOCK : INLINE);
4481     // CSS2 says first-letter can't be positioned.
4482     pseudoStyle->setPosition(StaticPosition);
4483     return pseudoStyle;
4484 }
4485
4486 // CSS 2.1 http://www.w3.org/TR/CSS21/selector.html#first-letter
4487 // "Punctuation (i.e, characters defined in Unicode [UNICODE] in the "open" (Ps), "close" (Pe),
4488 // "initial" (Pi). "final" (Pf) and "other" (Po) punctuation classes), that precedes or follows the first letter should be included"
4489 static inline bool isPunctuationForFirstLetter(UChar c)
4490 {
4491     CharCategory charCategory = category(c);
4492     return charCategory == Punctuation_Open
4493         || charCategory == Punctuation_Close
4494         || charCategory == Punctuation_InitialQuote
4495         || charCategory == Punctuation_FinalQuote
4496         || charCategory == Punctuation_Other;
4497 }
4498
4499 static inline bool shouldSkipForFirstLetter(UChar c)
4500 {
4501     return isSpaceOrNewline(c) || c == noBreakSpace || isPunctuationForFirstLetter(c);
4502 }
4503
4504 static inline RenderObject* findFirstLetterBlock(RenderBlock* start)
4505 {
4506     RenderObject* firstLetterBlock = start;
4507     while (true) {
4508         // We include isRenderButton in these two checks because buttons are
4509         // implemented using flex box but should still support first-letter.
4510         // The flex box spec requires that flex box does not support
4511         // first-letter, though.
4512         // FIXME: Remove when buttons are implemented with align-items instead
4513         // of flexbox.
4514         bool canHaveFirstLetterRenderer = firstLetterBlock->style()->hasPseudoStyle(FIRST_LETTER)
4515             && firstLetterBlock->canHaveGeneratedChildren()
4516             && (!firstLetterBlock->isFlexibleBox() || firstLetterBlock->isRenderButton());
4517         if (canHaveFirstLetterRenderer)
4518             return firstLetterBlock;
4519
4520         RenderObject* parentBlock = firstLetterBlock->parent();
4521         if (firstLetterBlock->isReplaced() || !parentBlock || parentBlock->firstChild() != firstLetterBlock ||
4522             (!parentBlock->isRenderBlockFlow() && !parentBlock->isRenderButton()))
4523             return 0;
4524         firstLetterBlock = parentBlock;
4525     }
4526
4527     return 0;
4528 }
4529
4530 void RenderBlock::updateFirstLetterStyle(RenderObject* firstLetterBlock, RenderObject* currentChild)
4531 {
4532     RenderObject* firstLetter = currentChild->parent();
4533     RenderObject* firstLetterContainer = firstLetter->parent();
4534     RenderStyle* pseudoStyle = styleForFirstLetter(firstLetterBlock, firstLetterContainer);
4535     ASSERT(firstLetter->isFloating() || firstLetter->isInline());
4536
4537     if (RenderStyle::compare(firstLetter->style(), pseudoStyle) == Reattach) {
4538         // The first-letter renderer needs to be replaced. Create a new renderer of the right type.
4539         RenderBoxModelObject* newFirstLetter;
4540         if (pseudoStyle->display() == INLINE)
4541             newFirstLetter = RenderInline::createAnonymous(&document());
4542         else
4543             newFirstLetter = RenderBlockFlow::createAnonymous(&document());
4544         newFirstLetter->setStyle(pseudoStyle);
4545
4546         // Move the first letter into the new renderer.
4547         LayoutStateDisabler layoutStateDisabler(view());
4548         while (RenderObject* child = firstLetter->firstChild()) {
4549             if (child->isText())
4550                 toRenderText(child)->removeAndDestroyTextBoxes();
4551             firstLetter->removeChild(child);
4552             newFirstLetter->addChild(child, 0);
4553         }
4554
4555         RenderObject* nextSibling = firstLetter->nextSibling();
4556         if (RenderTextFragment* remainingText = toRenderBoxModelObject(firstLetter)->firstLetterRemainingText()) {
4557             ASSERT(remainingText->isAnonymous() || remainingText->node()->renderer() == remainingText);
4558             // Replace the old renderer with the new one.
4559             remainingText->setFirstLetter(newFirstLetter);
4560             newFirstLetter->setFirstLetterRemainingText(remainingText);
4561         }
4562         // To prevent removal of single anonymous block in RenderBlock::removeChild and causing
4563         // |nextSibling| to go stale, we remove the old first letter using removeChildNode first.
4564         firstLetterContainer->virtualChildren()->removeChildNode(firstLetterContainer, firstLetter);
4565         firstLetter->destroy();
4566         firstLetter = newFirstLetter;
4567         firstLetterContainer->addChild(firstLetter, nextSibling);
4568     } else
4569         firstLetter->setStyle(pseudoStyle);
4570
4571     for (RenderObject* genChild = firstLetter->firstChild(); genChild; genChild = genChild->nextSibling()) {
4572         if (genChild->isText())
4573             genChild->setStyle(pseudoStyle);
4574     }
4575 }
4576
4577 static inline unsigned firstLetterLength(const String& text)
4578 {
4579     unsigned length = 0;
4580
4581     // Account for leading spaces and punctuation.
4582     while (length < text.length() && shouldSkipForFirstLetter((text)[length]))
4583         length++;
4584
4585     // Bail if we didn't find a letter
4586     if (text.length() && length == text.length())
4587         return 0;
4588
4589     // Account for first letter.
4590     length++;
4591
4592     // Keep looking for whitespace and allowed punctuation, but avoid
4593     // accumulating just whitespace into the :first-letter.
4594     for (unsigned scanLength = length; scanLength < text.length(); ++scanLength) {
4595         UChar c = (text)[scanLength];
4596
4597         if (!shouldSkipForFirstLetter(c))
4598             break;
4599
4600         if (isPunctuationForFirstLetter(c))
4601             length = scanLength + 1;
4602     }
4603
4604     return length;
4605 }
4606
4607 void RenderBlock::createFirstLetterRenderer(RenderObject* firstLetterBlock, RenderObject* currentChild, unsigned length)
4608 {
4609     ASSERT(length && currentChild->isText());
4610
4611     RenderObject* firstLetterContainer = currentChild->parent();
4612     RenderStyle* pseudoStyle = styleForFirstLetter(firstLetterBlock, firstLetterContainer);
4613     RenderObject* firstLetter = 0;
4614     if (pseudoStyle->display() == INLINE)
4615         firstLetter = RenderInline::createAnonymous(&document());
4616     else
4617         firstLetter = RenderBlockFlow::createAnonymous(&document());
4618     firstLetter->setStyle(pseudoStyle);
4619     firstLetterContainer->addChild(firstLetter, currentChild);
4620
4621     RenderText* textObj = toRenderText(currentChild);
4622
4623     // The original string is going to be either a generated content string or a DOM node's
4624     // string.  We want the original string before it got transformed in case first-letter has
4625     // no text-transform or a different text-transform applied to it.
4626     String oldText = textObj->originalText();
4627     ASSERT(oldText.impl());
4628
4629     // Construct a text fragment for the text after the first letter.
4630     // This text fragment might be empty.
4631     RenderTextFragment* remainingText =
4632         new RenderTextFragment(textObj->node() ? textObj->node() : &textObj->document(), oldText.impl(), length, oldText.length() - length);
4633     remainingText->setStyle(textObj->style());
4634     if (remainingText->node())
4635         remainingText->node()->setRenderer(remainingText);
4636
4637     firstLetterContainer->addChild(remainingText, textObj);
4638     firstLetterContainer->removeChild(textObj);
4639     remainingText->setFirstLetter(firstLetter);
4640     toRenderBoxModelObject(firstLetter)->setFirstLetterRemainingText(remainingText);
4641
4642     // construct text fragment for the first letter
4643     RenderTextFragment* letter =
4644         new RenderTextFragment(remainingText->node() ? remainingText->node() : &remainingText->document(), oldText.impl(), 0, length);
4645     letter->setStyle(pseudoStyle);
4646     firstLetter->addChild(letter);
4647
4648     textObj->destroy();
4649 }
4650
4651 void RenderBlock::updateFirstLetter()
4652 {
4653     if (!document().styleEngine()->usesFirstLetterRules())
4654         return;
4655     // Don't recur
4656     if (style()->styleType() == FIRST_LETTER)
4657         return;
4658
4659     // FIXME: We need to destroy the first-letter object if it is no longer the first child. Need to find
4660     // an efficient way to check for that situation though before implementing anything.
4661     RenderObject* firstLetterBlock = findFirstLetterBlock(this);
4662     if (!firstLetterBlock)
4663         return;
4664
4665     // Drill into inlines looking for our first text child.
4666     RenderObject* currChild = firstLetterBlock->firstChild();
4667     unsigned length = 0;
4668     while (currChild) {
4669         if (currChild->isText()) {
4670             // FIXME: If there is leading punctuation in a different RenderText than
4671             // the first letter, we'll not apply the correct style to it.
4672             length = firstLetterLength(toRenderText(currChild)->originalText());
4673             if (length)
4674                 break;
4675             currChild = currChild->nextSibling();
4676         } else if (currChild->isListMarker()) {
4677             currChild = currChild->nextSibling();
4678         } else if (currChild->isFloatingOrOutOfFlowPositioned()) {
4679             if (currChild->style()->styleType() == FIRST_LETTER) {
4680                 currChild = currChild->firstChild();
4681                 break;
4682             }
4683             currChild = currChild->nextSibling();
4684         } else if (currChild->isReplaced() || currChild->isRenderButton() || currChild->isMenuList())
4685             break;
4686         else if (currChild->style()->hasPseudoStyle(FIRST_LETTER) && currChild->canHaveGeneratedChildren())  {
4687             // We found a lower-level node with first-letter, which supersedes the higher-level style
4688             firstLetterBlock = currChild;
4689             currChild = currChild->firstChild();
4690         } else
4691             currChild = currChild->firstChild();
4692     }
4693
4694     if (!currChild)
4695         return;
4696
4697     // If the child already has style, then it has already been created, so we just want
4698     // to update it.
4699     if (currChild->parent()->style()->styleType() == FIRST_LETTER) {
4700         updateFirstLetterStyle(firstLetterBlock, currChild);
4701         return;
4702     }
4703
4704     if (!currChild->isText() || currChild->isBR())
4705         return;
4706
4707     // Our layout state is not valid for the repaints we are going to trigger by
4708     // adding and removing children of firstLetterContainer.
4709     LayoutStateDisabler layoutStateDisabler(view());
4710
4711     createFirstLetterRenderer(firstLetterBlock, currChild, length);
4712 }
4713
4714 // Helper methods for obtaining the last line, computing line counts and heights for line counts
4715 // (crawling into blocks).
4716 static bool shouldCheckLines(RenderObject* obj)
4717 {
4718     return !obj->isFloatingOrOutOfFlowPositioned()
4719         && obj->isRenderBlock() && obj->style()->height().isAuto()
4720         && (!obj->isDeprecatedFlexibleBox() || obj->style()->boxOrient() == VERTICAL);
4721 }
4722
4723 static int getHeightForLineCount(RenderBlock* block, int l, bool includeBottom, int& count)
4724 {
4725     if (block->style()->visibility() == VISIBLE) {
4726         if (block->childrenInline()) {
4727             for (RootInlineBox* box = block->firstRootBox(); box; box = box->nextRootBox()) {
4728                 if (++count == l)
4729                     return box->lineBottom() + (includeBottom ? (block->borderBottom() + block->paddingBottom()) : LayoutUnit());
4730             }
4731         }
4732         else {
4733             RenderBox* normalFlowChildWithoutLines = 0;
4734             for (RenderBox* obj = block->firstChildBox(); obj; obj = obj->nextSiblingBox()) {
4735                 if (shouldCheckLines(obj)) {
4736                     int result = getHeightForLineCount(toRenderBlock(obj), l, false, count);
4737                     if (result != -1)
4738                         return result + obj->y() + (includeBottom ? (block->borderBottom() + block->paddingBottom()) : LayoutUnit());
4739                 } else if (!obj->isFloatingOrOutOfFlowPositioned())
4740                     normalFlowChildWithoutLines = obj;
4741             }
4742             if (normalFlowChildWithoutLines && l == 0)
4743                 return normalFlowChildWithoutLines->y() + normalFlowChildWithoutLines->height();
4744         }
4745     }
4746
4747     return -1;
4748 }
4749
4750 RootInlineBox* RenderBlock::lineAtIndex(int i) const
4751 {
4752     ASSERT(i >= 0);
4753
4754     if (style()->visibility() != VISIBLE)
4755         return 0;
4756
4757     if (childrenInline()) {
4758         for (RootInlineBox* box = firstRootBox(); box; box = box->nextRootBox())
4759             if (!i--)
4760                 return box;
4761     } else {
4762         for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
4763             if (!shouldCheckLines(child))
4764                 continue;
4765             if (RootInlineBox* box = toRenderBlock(child)->lineAtIndex(i))
4766                 return box;
4767         }
4768     }
4769
4770     return 0;
4771 }
4772
4773 int RenderBlock::lineCount(const RootInlineBox* stopRootInlineBox, bool* found) const
4774 {
4775     int count = 0;
4776
4777     if (style()->visibility() == VISIBLE) {
4778         if (childrenInline())
4779             for (RootInlineBox* box = firstRootBox(); box; box = box->nextRootBox()) {
4780                 count++;
4781                 if (box == stopRootInlineBox) {
4782                     if (found)
4783                         *found = true;
4784                     break;
4785                 }
4786             }
4787         else
4788             for (RenderObject* obj = firstChild(); obj; obj = obj->nextSibling())
4789                 if (shouldCheckLines(obj)) {
4790                     bool recursiveFound = false;
4791                     count += toRenderBlock(obj)->lineCount(stopRootInlineBox, &recursiveFound);
4792                     if (recursiveFound) {
4793                         if (found)
4794                             *found = true;
4795                         break;
4796                     }
4797                 }
4798     }
4799     return count;
4800 }
4801
4802 int RenderBlock::heightForLineCount(int l)
4803 {
4804     int count = 0;
4805     return getHeightForLineCount(this, l, true, count);
4806 }
4807
4808 void RenderBlock::adjustForBorderFit(LayoutUnit x, LayoutUnit& left, LayoutUnit& right) const
4809 {
4810     // We don't deal with relative positioning.  Our assumption is that you shrink to fit the lines without accounting
4811     // for either overflow or translations via relative positioning.
4812     if (style()->visibility() == VISIBLE) {
4813         if (childrenInline()) {
4814             for (RootInlineBox* box = firstRootBox(); box; box = box->nextRootBox()) {
4815                 if (box->firstChild())
4816                     left = min(left, x + static_cast<LayoutUnit>(box->firstChild()->x()));
4817                 if (box->lastChild())
4818                     right = max(right, x + static_cast<LayoutUnit>(ceilf(box->lastChild()->logicalRight())));
4819             }
4820         } else {
4821             for (RenderBox* obj = firstChildBox(); obj; obj = obj->nextSiblingBox()) {
4822                 if (!obj->isFloatingOrOutOfFlowPositioned()) {
4823                     if (obj->isRenderBlockFlow() && !obj->hasOverflowClip())
4824                         toRenderBlock(obj)->adjustForBorderFit(x + obj->x(), left, right);
4825                     else if (obj->style()->visibility() == VISIBLE) {
4826                         // We are a replaced element or some kind of non-block-flow object.
4827                         left = min(left, x + obj->x());
4828                         right = max(right, x + obj->x() + obj->width());
4829                     }
4830                 }
4831             }
4832         }
4833     }
4834 }
4835
4836 void RenderBlock::fitBorderToLinesIfNeeded()
4837 {
4838     if (style()->borderFit() == BorderFitBorder || hasOverrideWidth())
4839         return;
4840
4841     // Walk any normal flow lines to snugly fit.
4842     LayoutUnit left = LayoutUnit::max();
4843     LayoutUnit right = LayoutUnit::min();
4844     LayoutUnit oldWidth = contentWidth();
4845     adjustForBorderFit(0, left, right);
4846
4847     // Clamp to our existing edges. We can never grow. We only shrink.
4848     LayoutUnit leftEdge = borderLeft() + paddingLeft();
4849     LayoutUnit rightEdge = leftEdge + oldWidth;
4850     left = min(rightEdge, max(leftEdge, left));
4851     right = max(left, min(rightEdge, right));
4852
4853     LayoutUnit newContentWidth = right - left;
4854     if (newContentWidth == oldWidth)
4855         return;
4856
4857     setOverrideLogicalContentWidth(newContentWidth);
4858     layoutBlock(false);
4859     clearOverrideLogicalContentWidth();
4860 }
4861
4862 void RenderBlock::clearTruncation()
4863 {
4864     if (style()->visibility() == VISIBLE) {
4865         if (childrenInline() && hasMarkupTruncation()) {
4866             setHasMarkupTruncation(false);
4867             for (RootInlineBox* box = firstRootBox(); box; box = box->nextRootBox())
4868                 box->clearTruncation();
4869         } else {
4870             for (RenderObject* obj = firstChild(); obj; obj = obj->nextSibling()) {
4871                 if (shouldCheckLines(obj))
4872                     toRenderBlock(obj)->clearTruncation();
4873             }
4874         }
4875     }
4876 }
4877
4878 void RenderBlock::setPaginationStrut(LayoutUnit strut)
4879 {
4880     if (!m_rareData) {
4881         if (!strut)
4882             return;
4883         m_rareData = adoptPtr(new RenderBlockRareData());
4884     }
4885     m_rareData->m_paginationStrut = strut;
4886 }
4887
4888 void RenderBlock::setPageLogicalOffset(LayoutUnit logicalOffset)
4889 {
4890     if (!m_rareData) {
4891         if (!logicalOffset)
4892             return;
4893         m_rareData = adoptPtr(new RenderBlockRareData());
4894     }
4895     m_rareData->m_pageLogicalOffset = logicalOffset;
4896 }
4897
4898 void RenderBlock::setBreakAtLineToAvoidWidow(int lineToBreak)
4899 {
4900     ASSERT(lineToBreak >= 0);
4901     if (!m_rareData)
4902         m_rareData = adoptPtr(new RenderBlockRareData());
4903
4904     ASSERT(!m_rareData->m_didBreakAtLineToAvoidWidow);
4905     m_rareData->m_lineBreakToAvoidWidow = lineToBreak;
4906 }
4907
4908 void RenderBlock::setDidBreakAtLineToAvoidWidow()
4909 {
4910     ASSERT(!shouldBreakAtLineToAvoidWidow());
4911
4912     // This function should be called only after a break was applied to avoid widows
4913     // so assert |m_rareData| exists.
4914     ASSERT(m_rareData);
4915
4916     m_rareData->m_didBreakAtLineToAvoidWidow = true;
4917 }
4918
4919 void RenderBlock::clearDidBreakAtLineToAvoidWidow()
4920 {
4921     if (!m_rareData)
4922         return;
4923
4924     m_rareData->m_didBreakAtLineToAvoidWidow = false;
4925 }
4926
4927 void RenderBlock::clearShouldBreakAtLineToAvoidWidow() const
4928 {
4929     ASSERT(shouldBreakAtLineToAvoidWidow());
4930     if (!m_rareData)
4931         return;
4932
4933     m_rareData->m_lineBreakToAvoidWidow = -1;
4934 }
4935
4936 void RenderBlock::absoluteRects(Vector<IntRect>& rects, const LayoutPoint& accumulatedOffset) const
4937 {
4938     // For blocks inside inlines, we go ahead and include margins so that we run right up to the
4939     // inline boxes above and below us (thus getting merged with them to form a single irregular
4940     // shape).
4941     if (isAnonymousBlockContinuation()) {
4942         // FIXME: This is wrong for block-flows that are horizontal.
4943         // https://bugs.webkit.org/show_bug.cgi?id=46781
4944         rects.append(pixelSnappedIntRect(accumulatedOffset.x(), accumulatedOffset.y() - collapsedMarginBefore(),
4945                                 width(), height() + collapsedMarginBefore() + collapsedMarginAfter()));
4946         continuation()->absoluteRects(rects, accumulatedOffset - toLayoutSize(location() +
4947                 inlineElementContinuation()->containingBlock()->location()));
4948     } else
4949         rects.append(pixelSnappedIntRect(accumulatedOffset, size()));
4950 }
4951
4952 void RenderBlock::absoluteQuads(Vector<FloatQuad>& quads, bool* wasFixed) const
4953 {
4954     // For blocks inside inlines, we go ahead and include margins so that we run right up to the
4955     // inline boxes above and below us (thus getting merged with them to form a single irregular
4956     // shape).
4957     if (isAnonymousBlockContinuation()) {
4958         // FIXME: This is wrong for block-flows that are horizontal.
4959         // https://bugs.webkit.org/show_bug.cgi?id=46781
4960         FloatRect localRect(0, -collapsedMarginBefore(),
4961                             width(), height() + collapsedMarginBefore() + collapsedMarginAfter());
4962         quads.append(localToAbsoluteQuad(localRect, 0 /* mode */, wasFixed));
4963         continuation()->absoluteQuads(quads, wasFixed);
4964     } else
4965         quads.append(RenderBox::localToAbsoluteQuad(FloatRect(0, 0, width(), height()), 0 /* mode */, wasFixed));
4966 }
4967
4968 LayoutRect RenderBlock::rectWithOutlineForRepaint(const RenderLayerModelObject* repaintContainer, LayoutUnit outlineWidth) const
4969 {
4970     LayoutRect r(RenderBox::rectWithOutlineForRepaint(repaintContainer, outlineWidth));
4971     if (isAnonymousBlockContinuation())
4972         r.inflateY(collapsedMarginBefore()); // FIXME: This is wrong for block-flows that are horizontal.
4973     return r;
4974 }
4975
4976 RenderObject* RenderBlock::hoverAncestor() const
4977 {
4978     return isAnonymousBlockContinuation() ? continuation() : RenderBox::hoverAncestor();
4979 }
4980
4981 void RenderBlock::updateDragState(bool dragOn)
4982 {
4983     RenderBox::updateDragState(dragOn);
4984     if (continuation())
4985         continuation()->updateDragState(dragOn);
4986 }
4987
4988 RenderStyle* RenderBlock::outlineStyleForRepaint() const
4989 {
4990     return isAnonymousBlockContinuation() ? continuation()->style() : style();
4991 }
4992
4993 void RenderBlock::childBecameNonInline(RenderObject*)
4994 {
4995     makeChildrenNonInline();
4996     if (isAnonymousBlock() && parent() && parent()->isRenderBlock())
4997         toRenderBlock(parent())->removeLeftoverAnonymousBlock(this);
4998     // |this| may be dead here
4999 }
5000
5001 void RenderBlock::updateHitTestResult(HitTestResult& result, const LayoutPoint& point)
5002 {
5003     if (result.innerNode())
5004         return;
5005
5006     if (Node* n = nodeForHitTest()) {
5007         result.setInnerNode(n);
5008         if (!result.innerNonSharedNode())
5009             result.setInnerNonSharedNode(n);
5010         result.setLocalPoint(point);
5011     }
5012 }
5013
5014 LayoutRect RenderBlock::localCaretRect(InlineBox* inlineBox, int caretOffset, LayoutUnit* extraWidthToEndOfLine)
5015 {
5016     // Do the normal calculation in most cases.
5017     if (firstChild())
5018         return RenderBox::localCaretRect(inlineBox, caretOffset, extraWidthToEndOfLine);
5019
5020     LayoutRect caretRect = localCaretRectForEmptyElement(width(), textIndentOffset());
5021
5022     if (extraWidthToEndOfLine) {
5023         if (isRenderBlock()) {
5024             *extraWidthToEndOfLine = width() - caretRect.maxX();
5025         } else {
5026             // FIXME: This code looks wrong.
5027             // myRight and containerRight are set up, but then clobbered.
5028             // So *extraWidthToEndOfLine will always be 0 here.
5029
5030             LayoutUnit myRight = caretRect.maxX();
5031             // FIXME: why call localToAbsoluteForContent() twice here, too?
5032             FloatPoint absRightPoint = localToAbsolute(FloatPoint(myRight, 0));
5033
5034             LayoutUnit containerRight = containingBlock()->x() + containingBlockLogicalWidthForContent();
5035             FloatPoint absContainerPoint = localToAbsolute(FloatPoint(containerRight, 0));
5036
5037             *extraWidthToEndOfLine = absContainerPoint.x() - absRightPoint.x();
5038         }
5039     }
5040
5041     return caretRect;
5042 }
5043
5044 void RenderBlock::addFocusRingRects(Vector<IntRect>& rects, const LayoutPoint& additionalOffset, const RenderLayerModelObject* paintContainer)
5045 {
5046     // For blocks inside inlines, we go ahead and include margins so that we run right up to the
5047     // inline boxes above and below us (thus getting merged with them to form a single irregular
5048     // shape).
5049     if (inlineElementContinuation()) {
5050         // FIXME: This check really isn't accurate.
5051         bool nextInlineHasLineBox = inlineElementContinuation()->firstLineBox();
5052         // FIXME: This is wrong. The principal renderer may not be the continuation preceding this block.
5053         // FIXME: This is wrong for block-flows that are horizontal.
5054         // https://bugs.webkit.org/show_bug.cgi?id=46781
5055         bool prevInlineHasLineBox = toRenderInline(inlineElementContinuation()->node()->renderer())->firstLineBox();
5056         float topMargin = prevInlineHasLineBox ? collapsedMarginBefore() : LayoutUnit();
5057         float bottomMargin = nextInlineHasLineBox ? collapsedMarginAfter() : LayoutUnit();
5058         LayoutRect rect(additionalOffset.x(), additionalOffset.y() - topMargin, width(), height() + topMargin + bottomMargin);
5059         if (!rect.isEmpty())
5060             rects.append(pixelSnappedIntRect(rect));
5061     } else if (width() && height())
5062         rects.append(pixelSnappedIntRect(additionalOffset, size()));
5063
5064     if (!hasOverflowClip() && !hasControlClip()) {
5065         for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
5066             LayoutUnit top = max<LayoutUnit>(curr->lineTop(), curr->top());
5067             LayoutUnit bottom = min<LayoutUnit>(curr->lineBottom(), curr->top() + curr->height());
5068             LayoutRect rect(additionalOffset.x() + curr->x(), additionalOffset.y() + top, curr->width(), bottom - top);
5069             if (!rect.isEmpty())
5070                 rects.append(pixelSnappedIntRect(rect));
5071         }
5072
5073         for (RenderObject* curr = firstChild(); curr; curr = curr->nextSibling()) {
5074             if (!curr->isText() && !curr->isListMarker() && curr->isBox()) {
5075                 RenderBox* box = toRenderBox(curr);
5076                 FloatPoint pos;
5077                 // FIXME: This doesn't work correctly with transforms.
5078                 if (box->layer())
5079                     pos = curr->localToContainerPoint(FloatPoint(), paintContainer);
5080                 else
5081                     pos = FloatPoint(additionalOffset.x() + box->x(), additionalOffset.y() + box->y());
5082                 box->addFocusRingRects(rects, flooredLayoutPoint(pos), paintContainer);
5083             }
5084         }
5085     }
5086
5087     if (inlineElementContinuation())
5088         inlineElementContinuation()->addFocusRingRects(rects, flooredLayoutPoint(additionalOffset + inlineElementContinuation()->containingBlock()->location() - location()), paintContainer);
5089 }
5090
5091 void RenderBlock::computeSelfHitTestRects(Vector<LayoutRect>& rects, const LayoutPoint& layerOffset) const
5092 {
5093     RenderBox::computeSelfHitTestRects(rects, layerOffset);
5094
5095     if (hasHorizontalLayoutOverflow() || hasVerticalLayoutOverflow()) {
5096         for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
5097             LayoutUnit top = max<LayoutUnit>(curr->lineTop(), curr->top());
5098             LayoutUnit bottom = min<LayoutUnit>(curr->lineBottom(), curr->top() + curr->height());
5099             LayoutRect rect(layerOffset.x() + curr->x(), layerOffset.y() + top, curr->width(), bottom - top);
5100             // It's common for this rect to be entirely contained in our box, so exclude that simple case.
5101             if (!rect.isEmpty() && (rects.isEmpty() || !rects[0].contains(rect)))
5102                 rects.append(rect);
5103         }
5104     }
5105 }
5106
5107 RenderBox* RenderBlock::createAnonymousBoxWithSameTypeAs(const RenderObject* parent) const
5108 {
5109     if (isAnonymousColumnsBlock())
5110         return createAnonymousColumnsWithParentRenderer(parent);
5111     if (isAnonymousColumnSpanBlock())
5112         return createAnonymousColumnSpanWithParentRenderer(parent);
5113     return createAnonymousWithParentRendererAndDisplay(parent, style()->display());
5114 }
5115
5116 LayoutUnit RenderBlock::nextPageLogicalTop(LayoutUnit logicalOffset, PageBoundaryRule pageBoundaryRule) const
5117 {
5118     LayoutUnit pageLogicalHeight = pageLogicalHeightForOffset(logicalOffset);
5119     if (!pageLogicalHeight)
5120         return logicalOffset;
5121
5122     // The logicalOffset is in our coordinate space.  We can add in our pushed offset.
5123     LayoutUnit remainingLogicalHeight = pageRemainingLogicalHeightForOffset(logicalOffset);
5124     if (pageBoundaryRule == ExcludePageBoundary)
5125         return logicalOffset + (remainingLogicalHeight ? remainingLogicalHeight : pageLogicalHeight);
5126     return logicalOffset + remainingLogicalHeight;
5127 }
5128
5129 LayoutUnit RenderBlock::pageLogicalTopForOffset(LayoutUnit offset) const
5130 {
5131     RenderView* renderView = view();
5132     LayoutUnit firstPageLogicalTop = isHorizontalWritingMode() ? renderView->layoutState()->m_pageOffset.height() : renderView->layoutState()->m_pageOffset.width();
5133     LayoutUnit blockLogicalTop = isHorizontalWritingMode() ? renderView->layoutState()->m_layoutOffset.height() : renderView->layoutState()->m_layoutOffset.width();
5134
5135     LayoutUnit cumulativeOffset = offset + blockLogicalTop;
5136     RenderFlowThread* flowThread = flowThreadContainingBlock();
5137     if (!flowThread) {
5138         LayoutUnit pageLogicalHeight = renderView->layoutState()->pageLogicalHeight();
5139         if (!pageLogicalHeight)
5140             return 0;
5141         return cumulativeOffset - roundToInt(cumulativeOffset - firstPageLogicalTop) % roundToInt(pageLogicalHeight);
5142     }
5143     return flowThread->pageLogicalTopForOffset(cumulativeOffset);
5144 }
5145
5146 LayoutUnit RenderBlock::pageLogicalHeightForOffset(LayoutUnit offset) const
5147 {
5148     RenderView* renderView = view();
5149     RenderFlowThread* flowThread = flowThreadContainingBlock();
5150     if (!flowThread)
5151         return renderView->layoutState()->m_pageLogicalHeight;
5152     return flowThread->pageLogicalHeightForOffset(offset + offsetFromLogicalTopOfFirstPage());
5153 }
5154
5155 LayoutUnit RenderBlock::pageRemainingLogicalHeightForOffset(LayoutUnit offset, PageBoundaryRule pageBoundaryRule) const
5156 {
5157     RenderView* renderView = view();
5158     offset += offsetFromLogicalTopOfFirstPage();
5159
5160     RenderFlowThread* flowThread = flowThreadContainingBlock();
5161     if (!flowThread) {
5162         LayoutUnit pageLogicalHeight = renderView->layoutState()->m_pageLogicalHeight;
5163         LayoutUnit remainingHeight = pageLogicalHeight - intMod(offset, pageLogicalHeight);
5164         if (pageBoundaryRule == IncludePageBoundary) {
5165             // If includeBoundaryPoint is true the line exactly on the top edge of a
5166             // column will act as being part of the previous column.
5167             remainingHeight = intMod(remainingHeight, pageLogicalHeight);
5168         }
5169         return remainingHeight;
5170     }
5171
5172     return flowThread->pageRemainingLogicalHeightForOffset(offset, pageBoundaryRule);
5173 }
5174
5175 LayoutUnit RenderBlock::adjustForUnsplittableChild(RenderBox* child, LayoutUnit logicalOffset, bool includeMargins)
5176 {
5177     bool checkColumnBreaks = view()->layoutState()->isPaginatingColumns();
5178     bool checkPageBreaks = !checkColumnBreaks && view()->layoutState()->m_pageLogicalHeight;
5179     bool isUnsplittable = child->isUnsplittableForPagination() || (checkColumnBreaks && child->style()->columnBreakInside() == PBAVOID)
5180         || (checkPageBreaks && child->style()->pageBreakInside() == PBAVOID);
5181     if (!isUnsplittable)
5182         return logicalOffset;
5183     LayoutUnit childLogicalHeight = logicalHeightForChild(child) + (includeMargins ? marginBeforeForChild(child) + marginAfterForChild(child) : LayoutUnit());
5184     LayoutUnit pageLogicalHeight = pageLogicalHeightForOffset(logicalOffset);
5185     updateMinimumPageHeight(logicalOffset, childLogicalHeight);
5186     if (!pageLogicalHeight || childLogicalHeight > pageLogicalHeight)
5187         return logicalOffset;
5188     LayoutUnit remainingLogicalHeight = pageRemainingLogicalHeightForOffset(logicalOffset, ExcludePageBoundary);
5189     if (remainingLogicalHeight < childLogicalHeight)
5190         return logicalOffset + remainingLogicalHeight;
5191     return logicalOffset;
5192 }
5193
5194 bool RenderBlock::pushToNextPageWithMinimumLogicalHeight(LayoutUnit& adjustment, LayoutUnit logicalOffset, LayoutUnit minimumLogicalHeight) const
5195 {
5196     // FIXME: multicol will need to do some work here, when we implement support for multiple rows.
5197     return false;
5198 }
5199
5200 void RenderBlock::setPageBreak(LayoutUnit offset, LayoutUnit spaceShortage)
5201 {
5202     if (RenderFlowThread* flowThread = flowThreadContainingBlock())
5203         flowThread->setPageBreak(offsetFromLogicalTopOfFirstPage() + offset, spaceShortage);
5204 }
5205
5206 void RenderBlock::updateMinimumPageHeight(LayoutUnit offset, LayoutUnit minHeight)
5207 {
5208     if (RenderFlowThread* flowThread = flowThreadContainingBlock())
5209         flowThread->updateMinimumPageHeight(offsetFromLogicalTopOfFirstPage() + offset, minHeight);
5210     else if (ColumnInfo* colInfo = view()->layoutState()->m_columnInfo)
5211         colInfo->updateMinimumColumnHeight(minHeight);
5212 }
5213
5214 static inline LayoutUnit calculateMinimumPageHeight(RenderStyle* renderStyle, RootInlineBox* lastLine, LayoutUnit lineTop, LayoutUnit lineBottom)
5215 {
5216     // We may require a certain minimum number of lines per page in order to satisfy
5217     // orphans and widows, and that may affect the minimum page height.
5218     unsigned lineCount = max<unsigned>(renderStyle->hasAutoOrphans() ? 1 : renderStyle->orphans(), renderStyle->hasAutoWidows() ? 1 : renderStyle->widows());
5219     if (lineCount > 1) {
5220         RootInlineBox* line = lastLine;
5221         for (unsigned i = 1; i < lineCount && line->prevRootBox(); i++)
5222             line = line->prevRootBox();
5223
5224         // FIXME: Paginating using line overflow isn't all fine. See FIXME in
5225         // adjustLinePositionForPagination() for more details.
5226         LayoutRect overflow = line->logicalVisualOverflowRect(line->lineTop(), line->lineBottom());
5227         lineTop = min(line->lineTopWithLeading(), overflow.y());
5228     }
5229     return lineBottom - lineTop;
5230 }
5231
5232 void RenderBlock::adjustLinePositionForPagination(RootInlineBox* lineBox, LayoutUnit& delta, RenderFlowThread* flowThread)
5233 {
5234     // FIXME: For now we paginate using line overflow.  This ensures that lines don't overlap at all when we
5235     // put a strut between them for pagination purposes.  However, this really isn't the desired rendering, since
5236     // the line on the top of the next page will appear too far down relative to the same kind of line at the top
5237     // of the first column.
5238     //
5239     // The rendering we would like to see is one where the lineTopWithLeading is at the top of the column, and any line overflow
5240     // simply spills out above the top of the column.  This effect would match what happens at the top of the first column.
5241     // We can't achieve this rendering, however, until we stop columns from clipping to the column bounds (thus allowing
5242     // for overflow to occur), and then cache visible overflow for each column rect.
5243     //
5244     // Furthermore, the paint we have to do when a column has overflow has to be special.  We need to exclude
5245     // content that paints in a previous column (and content that paints in the following column).
5246     //
5247     // For now we'll at least honor the lineTopWithLeading when paginating if it is above the logical top overflow. This will
5248     // at least make positive leading work in typical cases.
5249     //
5250     // FIXME: Another problem with simply moving lines is that the available line width may change (because of floats).
5251     // Technically if the location we move the line to has a different line width than our old position, then we need to dirty the
5252     // line and all following lines.
5253     LayoutRect logicalVisualOverflow = lineBox->logicalVisualOverflowRect(lineBox->lineTop(), lineBox->lineBottom());
5254     LayoutUnit logicalOffset = min(lineBox->lineTopWithLeading(), logicalVisualOverflow.y());
5255     LayoutUnit logicalBottom = max(lineBox->lineBottomWithLeading(), logicalVisualOverflow.maxY());
5256     LayoutUnit lineHeight = logicalBottom - logicalOffset;
5257     updateMinimumPageHeight(logicalOffset, calculateMinimumPageHeight(style(), lineBox, logicalOffset, logicalBottom));
5258     logicalOffset += delta;
5259     lineBox->setPaginationStrut(0);
5260     lineBox->setIsFirstAfterPageBreak(false);
5261     LayoutUnit pageLogicalHeight = pageLogicalHeightForOffset(logicalOffset);
5262     bool hasUniformPageLogicalHeight = !flowThread || flowThread->regionsHaveUniformLogicalHeight();
5263     // If lineHeight is greater than pageLogicalHeight, but logicalVisualOverflow.height() still fits, we are
5264     // still going to add a strut, so that the visible overflow fits on a single page.
5265     if (!pageLogicalHeight || (hasUniformPageLogicalHeight && logicalVisualOverflow.height() > pageLogicalHeight))
5266         // FIXME: In case the line aligns with the top of the page (or it's slightly shifted downwards) it will not be marked as the first line in the page.
5267         // From here, the fix is not straightforward because it's not easy to always determine when the current line is the first in the page.
5268         return;
5269     LayoutUnit remainingLogicalHeight = pageRemainingLogicalHeightForOffset(logicalOffset, ExcludePageBoundary);
5270
5271     int lineIndex = lineCount(lineBox);
5272     if (remainingLogicalHeight < lineHeight || (shouldBreakAtLineToAvoidWidow() && lineBreakToAvoidWidow() == lineIndex)) {
5273         if (shouldBreakAtLineToAvoidWidow() && lineBreakToAvoidWidow() == lineIndex) {
5274             clearShouldBreakAtLineToAvoidWidow();
5275             setDidBreakAtLineToAvoidWidow();
5276         }
5277         // If we have a non-uniform page height, then we have to shift further possibly.
5278         if (!hasUniformPageLogicalHeight && !pushToNextPageWithMinimumLogicalHeight(remainingLogicalHeight, logicalOffset, lineHeight))
5279             return;
5280         if (lineHeight > pageLogicalHeight) {
5281             // Split the top margin in order to avoid splitting the visible part of the line.
5282             remainingLogicalHeight -= min(lineHeight - pageLogicalHeight, max<LayoutUnit>(0, logicalVisualOverflow.y() - lineBox->lineTopWithLeading()));
5283         }
5284         LayoutUnit totalLogicalHeight = lineHeight + max<LayoutUnit>(0, logicalOffset);
5285         LayoutUnit pageLogicalHeightAtNewOffset = hasUniformPageLogicalHeight ? pageLogicalHeight : pageLogicalHeightForOffset(logicalOffset + remainingLogicalHeight);
5286         setPageBreak(logicalOffset, lineHeight - remainingLogicalHeight);
5287         if (((lineBox == firstRootBox() && totalLogicalHeight < pageLogicalHeightAtNewOffset) || (!style()->hasAutoOrphans() && style()->orphans() >= lineIndex))
5288             && !isOutOfFlowPositioned() && !isTableCell())
5289             setPaginationStrut(remainingLogicalHeight + max<LayoutUnit>(0, logicalOffset));
5290         else {
5291             delta += remainingLogicalHeight;
5292             lineBox->setPaginationStrut(remainingLogicalHeight);
5293             lineBox->setIsFirstAfterPageBreak(true);
5294         }
5295     } else if (remainingLogicalHeight == pageLogicalHeight) {
5296         // We're at the very top of a page or column.
5297         if (lineBox != firstRootBox())
5298             lineBox->setIsFirstAfterPageBreak(true);
5299         if (lineBox != firstRootBox() || offsetFromLogicalTopOfFirstPage())
5300             setPageBreak(logicalOffset, lineHeight);
5301     }
5302 }
5303
5304 LayoutUnit RenderBlock::offsetFromLogicalTopOfFirstPage() const
5305 {
5306     LayoutState* layoutState = view()->layoutState();
5307     if (layoutState && !layoutState->isPaginated())
5308         return 0;
5309
5310     RenderFlowThread* flowThread = flowThreadContainingBlock();
5311     if (flowThread)
5312         return flowThread->offsetFromLogicalTopOfFirstRegion(this);
5313
5314     if (layoutState) {
5315         ASSERT(layoutState->renderer() == this);
5316
5317         LayoutSize offsetDelta = layoutState->m_layoutOffset - layoutState->m_pageOffset;
5318         return isHorizontalWritingMode() ? offsetDelta.height() : offsetDelta.width();
5319     }
5320
5321     ASSERT_NOT_REACHED();
5322     return 0;
5323 }
5324
5325 RenderRegion* RenderBlock::regionAtBlockOffset(LayoutUnit blockOffset) const
5326 {
5327     RenderFlowThread* flowThread = flowThreadContainingBlock();
5328     if (!flowThread || !flowThread->hasValidRegionInfo())
5329         return 0;
5330
5331     return flowThread->regionAtBlockOffset(offsetFromLogicalTopOfFirstPage() + blockOffset, true);
5332 }
5333
5334 LayoutUnit RenderBlock::collapsedMarginBeforeForChild(const RenderBox* child) const
5335 {
5336     // If the child has the same directionality as we do, then we can just return its
5337     // collapsed margin.
5338     if (!child->isWritingModeRoot())
5339         return child->collapsedMarginBefore();
5340
5341     // The child has a different directionality.  If the child is parallel, then it's just
5342     // flipped relative to us.  We can use the collapsed margin for the opposite edge.
5343     if (child->isHorizontalWritingMode() == isHorizontalWritingMode())
5344         return child->collapsedMarginAfter();
5345
5346     // The child is perpendicular to us, which means its margins don't collapse but are on the
5347     // "logical left/right" sides of the child box.  We can just return the raw margin in this case.
5348     return marginBeforeForChild(child);
5349 }
5350
5351 LayoutUnit RenderBlock::collapsedMarginAfterForChild(const  RenderBox* child) const
5352 {
5353     // If the child has the same directionality as we do, then we can just return its
5354     // collapsed margin.
5355     if (!child->isWritingModeRoot())
5356         return child->collapsedMarginAfter();
5357
5358     // The child has a different directionality.  If the child is parallel, then it's just
5359     // flipped relative to us.  We can use the collapsed margin for the opposite edge.
5360     if (child->isHorizontalWritingMode() == isHorizontalWritingMode())
5361         return child->collapsedMarginBefore();
5362
5363     // The child is perpendicular to us, which means its margins don't collapse but are on the
5364     // "logical left/right" side of the child box.  We can just return the raw margin in this case.
5365     return marginAfterForChild(child);
5366 }
5367
5368 bool RenderBlock::hasMarginBeforeQuirk(const RenderBox* child) const
5369 {
5370     // If the child has the same directionality as we do, then we can just return its
5371     // margin quirk.
5372     if (!child->isWritingModeRoot())
5373         return child->isRenderBlock() ? toRenderBlock(child)->hasMarginBeforeQuirk() : child->style()->hasMarginBeforeQuirk();
5374
5375     // The child has a different directionality. If the child is parallel, then it's just
5376     // flipped relative to us. We can use the opposite edge.
5377     if (child->isHorizontalWritingMode() == isHorizontalWritingMode())
5378         return child->isRenderBlock() ? toRenderBlock(child)->hasMarginAfterQuirk() : child->style()->hasMarginAfterQuirk();
5379
5380     // The child is perpendicular to us and box sides are never quirky in html.css, and we don't really care about
5381     // whether or not authors specified quirky ems, since they're an implementation detail.
5382     return false;
5383 }
5384
5385 bool RenderBlock::hasMarginAfterQuirk(const RenderBox* child) const
5386 {
5387     // If the child has the same directionality as we do, then we can just return its
5388     // margin quirk.
5389     if (!child->isWritingModeRoot())
5390         return child->isRenderBlock() ? toRenderBlock(child)->hasMarginAfterQuirk() : child->style()->hasMarginAfterQuirk();
5391
5392     // The child has a different directionality. If the child is parallel, then it's just
5393     // flipped relative to us. We can use the opposite edge.
5394     if (child->isHorizontalWritingMode() == isHorizontalWritingMode())
5395         return child->isRenderBlock() ? toRenderBlock(child)->hasMarginBeforeQuirk() : child->style()->hasMarginBeforeQuirk();
5396
5397     // The child is perpendicular to us and box sides are never quirky in html.css, and we don't really care about
5398     // whether or not authors specified quirky ems, since they're an implementation detail.
5399     return false;
5400 }
5401
5402 const char* RenderBlock::renderName() const
5403 {
5404     if (isBody())
5405         return "RenderBody"; // FIXME: Temporary hack until we know that the regression tests pass.
5406
5407     if (isFloating())
5408         return "RenderBlock (floating)";
5409     if (isOutOfFlowPositioned())
5410         return "RenderBlock (positioned)";
5411     if (isAnonymousColumnsBlock())
5412         return "RenderBlock (anonymous multi-column)";
5413     if (isAnonymousColumnSpanBlock())
5414         return "RenderBlock (anonymous multi-column span)";
5415     if (isAnonymousBlock())
5416         return "RenderBlock (anonymous)";
5417     // FIXME: Temporary hack while the new generated content system is being implemented.
5418     if (isPseudoElement())
5419         return "RenderBlock (generated)";
5420     if (isAnonymous())
5421         return "RenderBlock (generated)";
5422     if (isRelPositioned())
5423         return "RenderBlock (relative positioned)";
5424     if (isStickyPositioned())
5425         return "RenderBlock (sticky positioned)";
5426     return "RenderBlock";
5427 }
5428
5429 RenderBlock* RenderBlock::createAnonymousWithParentRendererAndDisplay(const RenderObject* parent, EDisplay display)
5430 {
5431     // FIXME: Do we need to convert all our inline displays to block-type in the anonymous logic ?
5432     EDisplay newDisplay;
5433     RenderBlock* newBox = 0;
5434     if (display == BOX || display == INLINE_BOX) {
5435         // FIXME: Remove this case once we have eliminated all internal users of old flexbox
5436         newBox = RenderDeprecatedFlexibleBox::createAnonymous(&parent->document());
5437         newDisplay = BOX;
5438     } else if (display == FLEX || display == INLINE_FLEX) {
5439         newBox = RenderFlexibleBox::createAnonymous(&parent->document());
5440         newDisplay = FLEX;
5441     } else {
5442         newBox = RenderBlockFlow::createAnonymous(&parent->document());
5443         newDisplay = BLOCK;
5444     }
5445
5446     RefPtr<RenderStyle> newStyle = RenderStyle::createAnonymousStyleWithDisplay(parent->style(), newDisplay);
5447     newBox->setStyle(newStyle.release());
5448     return newBox;
5449 }
5450
5451 RenderBlockFlow* RenderBlock::createAnonymousColumnsWithParentRenderer(const RenderObject* parent)
5452 {
5453     RefPtr<RenderStyle> newStyle = RenderStyle::createAnonymousStyleWithDisplay(parent->style(), BLOCK);
5454     newStyle->inheritColumnPropertiesFrom(parent->style());
5455
5456     RenderBlockFlow* newBox = RenderBlockFlow::createAnonymous(&parent->document());
5457     newBox->setStyle(newStyle.release());
5458     return newBox;
5459 }
5460
5461 RenderBlockFlow* RenderBlock::createAnonymousColumnSpanWithParentRenderer(const RenderObject* parent)
5462 {
5463     RefPtr<RenderStyle> newStyle = RenderStyle::createAnonymousStyleWithDisplay(parent->style(), BLOCK);
5464     newStyle->setColumnSpan(ColumnSpanAll);
5465
5466     RenderBlockFlow* newBox = RenderBlockFlow::createAnonymous(&parent->document());
5467     newBox->setStyle(newStyle.release());
5468     return newBox;
5469 }
5470
5471 #ifndef NDEBUG
5472 void RenderBlock::checkPositionedObjectsNeedLayout()
5473 {
5474     if (!gPositionedDescendantsMap)
5475         return;
5476
5477     if (TrackedRendererListHashSet* positionedDescendantSet = positionedObjects()) {
5478         TrackedRendererListHashSet::const_iterator end = positionedDescendantSet->end();
5479         for (TrackedRendererListHashSet::const_iterator it = positionedDescendantSet->begin(); it != end; ++it) {
5480             RenderBox* currBox = *it;
5481             ASSERT(!currBox->needsLayout());
5482         }
5483     }
5484 }
5485
5486 void RenderBlock::showLineTreeAndMark(const InlineBox* markedBox1, const char* markedLabel1, const InlineBox* markedBox2, const char* markedLabel2, const RenderObject* obj) const
5487 {
5488     showRenderObject();
5489     for (const RootInlineBox* root = firstRootBox(); root; root = root->nextRootBox())
5490         root->showLineTreeAndMark(markedBox1, markedLabel1, markedBox2, markedLabel2, obj, 1);
5491 }
5492
5493 #endif
5494
5495 } // namespace WebCore