WebCore/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 Apple Inc. All rights reserved.
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Library General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Library General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Library General Public License
  18  * along with this library; see the file COPYING.LIB.  If not, write to
  19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  20  * Boston, MA 02110-1301, USA.
  21  */
  22
  23 #include "config.h"
  24 #include "RenderBlock.h"
  25
  26 #include "Document.h"
  27 #include "Element.h"
  28 #include "Frame.h"
  29 #include "FrameView.h"
  30 #include "GraphicsContext.h"
  31 #include "HTMLNames.h"
  32 #include "HitTestResult.h"
  33 #include "InlineTextBox.h"
  34 #include "RenderImage.h"
  35 #include "RenderReplica.h"
  36 #include "RenderTableCell.h"
  37 #include "RenderTextFragment.h"
  38 #include "RenderTheme.h"
  39 #include "RenderView.h"
  40 #include "SelectionController.h"
  41
  42 using namespace std;
  43 using namespace WTF;
  44 using namespace Unicode;
  45
  46 namespace WebCore {
  47
  48 // Number of pixels to allow as a fudge factor when clicking above or below a line.
  49 // clicking up to verticalLineClickFudgeFactor pixels above a line will correspond to the closest point on the line.
  50 const int verticalLineClickFudgeFactor= 3;
  51
  52 using namespace HTMLNames;
  53
  54 struct ColumnInfo {
  55     ColumnInfo()
  56         : m_desiredColumnWidth(0)
  57         , m_desiredColumnCount(1)
  58         { }
  59     int m_desiredColumnWidth;
  60     unsigned m_desiredColumnCount;
  61     Vector<IntRect> m_columnRects;
  62 };
  63
  64 typedef WTF::HashMap<const RenderBox*, ColumnInfo*> ColumnInfoMap;
  65 static ColumnInfoMap* gColumnInfoMap = 0;
  66
  67 // Our MarginInfo state used when laying out block children.
  68 RenderBlock::MarginInfo::MarginInfo(RenderBlock* block, int top, int bottom)
  69 {
  70     // Whether or not we can collapse our own margins with our children.  We don't do this
  71     // if we had any border/padding (obviously), if we're the root or HTML elements, or if
  72     // we're positioned, floating, a table cell.
  73     m_canCollapseWithChildren = !block->isRenderView() && !block->isRoot() && !block->isPositioned() &&
  74         !block->isFloating() && !block->isTableCell() && !block->hasOverflowClip() && !block->isInlineBlockOrInlineTable();
  75
  76     m_canCollapseTopWithChildren = m_canCollapseWithChildren && (top == 0) && block->style()->marginTopCollapse() != MSEPARATE;
  77
  78     // If any height other than auto is specified in CSS, then we don't collapse our bottom
  79     // margins with our children's margins.  To do otherwise would be to risk odd visual
  80     // effects when the children overflow out of the parent block and yet still collapse
  81     // with it.  We also don't collapse if we have any bottom border/padding.
  82     m_canCollapseBottomWithChildren = m_canCollapseWithChildren && (bottom == 0) &&
  83         (block->style()->height().isAuto() && block->style()->height().value() == 0) && block->style()->marginBottomCollapse() != MSEPARATE;
  84
  85     m_quirkContainer = block->isTableCell() || block->isBody() || block->style()->marginTopCollapse() == MDISCARD ||
  86         block->style()->marginBottomCollapse() == MDISCARD;
  87
  88     m_atTopOfBlock = true;
  89     m_atBottomOfBlock = false;
  90
  91     m_posMargin = m_canCollapseTopWithChildren ? block->maxTopMargin(true) : 0;
  92     m_negMargin = m_canCollapseTopWithChildren ? block->maxTopMargin(false) : 0;
  93
  94     m_selfCollapsingBlockClearedFloat = false;
  95
  96     m_topQuirk = m_bottomQuirk = m_determinedTopQuirk = false;
  97 }
  98
  99 // -------------------------------------------------------------------------------------------------------
 100
 101 RenderBlock::RenderBlock(Node* node)
 102       : RenderFlow(node)
 103       , m_floatingObjects(0)
 104       , m_positionedObjects(0)
 105       , m_maxMargin(0)
 106       , m_overflowHeight(0)
 107       , m_overflowWidth(0)
 108       , m_overflowLeft(0)
 109       , m_overflowTop(0)
 110 {
 111 }
 112
 113 RenderBlock::~RenderBlock()
 114 {
 115     delete m_floatingObjects;
 116     delete m_positionedObjects;
 117     delete m_maxMargin;
 118
 119     if (m_hasColumns)
 120         delete gColumnInfoMap->take(this);
 121 }
 122
 123 void RenderBlock::setStyle(RenderStyle* _style)
 124 {
 125     setReplaced(_style->isDisplayReplacedType());
 126
 127     RenderFlow::setStyle(_style);
 128
 129     // FIXME: We could save this call when the change only affected non-inherited properties
 130     for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
 131         if (child->isAnonymousBlock()) {
 132             RenderStyle* newStyle = new (renderArena()) RenderStyle();
 133             newStyle->inheritFrom(style());
 134             newStyle->setDisplay(BLOCK);
 135             child->setStyle(newStyle);
 136         }
 137     }
 138
 139     m_lineHeight = -1;
 140
 141     // Update pseudos for :before and :after now.
 142     if (!isAnonymous() && canHaveChildren()) {
 143         updateBeforeAfterContent(RenderStyle::BEFORE);
 144         updateBeforeAfterContent(RenderStyle::AFTER);
 145     }
 146     updateFirstLetter();
 147 }
 148
 149 void RenderBlock::addChildToFlow(RenderObject* newChild, RenderObject* beforeChild)
 150 {
 151     // Make sure we don't append things after :after-generated content if we have it.
 152     if (!beforeChild && isAfterContent(lastChild()))
 153         beforeChild = lastChild();
 154
 155     bool madeBoxesNonInline = false;
 156
 157     // If the requested beforeChild is not one of our children, then this is most likely because
 158     // there is an anonymous block box within this object that contains the beforeChild. So
 159     // just insert the child into the anonymous block box instead of here.
 160     if (beforeChild && beforeChild->parent() != this) {
 161         ASSERT(beforeChild->parent());
 162         ASSERT(beforeChild->parent()->isAnonymousBlock());
 163
 164         if (newChild->isInline() || beforeChild->parent()->firstChild() != beforeChild)
 165             beforeChild->parent()->addChild(newChild, beforeChild);
 166         else
 167             addChildToFlow(newChild, beforeChild->parent());
 168
 169         return;
 170     }
 171
 172     // A block has to either have all of its children inline, or all of its children as blocks.
 173     // So, if our children are currently inline and a block child has to be inserted, we move all our
 174     // inline children into anonymous block boxes.
 175     if (m_childrenInline && !newChild->isInline() && !newChild->isFloatingOrPositioned()) {
 176         // This is a block with inline content. Wrap the inline content in anonymous blocks.
 177         makeChildrenNonInline(beforeChild);
 178         madeBoxesNonInline = true;
 179
 180         if (beforeChild && beforeChild->parent() != this) {
 181             beforeChild = beforeChild->parent();
 182             ASSERT(beforeChild->isAnonymousBlock());
 183             ASSERT(beforeChild->parent() == this);
 184         }
 185     } else if (!m_childrenInline && (newChild->isFloatingOrPositioned() || newChild->isInline())) {
 186         // If we're inserting an inline child but all of our children are blocks, then we have to make sure
 187         // it is put into an anomyous block box. We try to use an existing anonymous box if possible, otherwise
 188         // a new one is created and inserted into our list of children in the appropriate position.
 189         RenderObject* afterChild = beforeChild ? beforeChild->previousSibling() : lastChild();
 190
 191         if (afterChild && afterChild->isAnonymousBlock()) {
 192             afterChild->addChild(newChild);
 193             return;
 194         }
 195
 196         if (newChild->isInline()) {
 197             // No suitable existing anonymous box - create a new one.
 198             RenderBlock* newBox = createAnonymousBlock();
 199             RenderContainer::addChild(newBox, beforeChild);
 200             newBox->addChild(newChild);
 201             return;
 202         }
 203     }
 204
 205     RenderContainer::addChild(newChild, beforeChild);
 206     // ### care about aligned stuff
 207
 208     if (madeBoxesNonInline && parent() && isAnonymousBlock())
 209         parent()->removeLeftoverAnonymousBlock(this);
 210     // this object may be dead here
 211 }
 212
 213 static void getInlineRun(RenderObject* start, RenderObject* boundary,
 214                          RenderObject*& inlineRunStart,
 215                          RenderObject*& inlineRunEnd)
 216 {
 217     // Beginning at |start| we find the largest contiguous run of inlines that
 218     // we can.  We denote the run with start and end points, |inlineRunStart|
 219     // and |inlineRunEnd|.  Note that these two values may be the same if
 220     // we encounter only one inline.
 221     //
 222     // We skip any non-inlines we encounter as long as we haven't found any
 223     // inlines yet.
 224     //
 225     // |boundary| indicates a non-inclusive boundary point.  Regardless of whether |boundary|
 226     // is inline or not, we will not include it in a run with inlines before it.  It's as though we encountered
 227     // a non-inline.
 228
 229     // Start by skipping as many non-inlines as we can.
 230     RenderObject * curr = start;
 231     bool sawInline;
 232     do {
 233         while (curr && !(curr->isInline() || curr->isFloatingOrPositioned()))
 234             curr = curr->nextSibling();
 235
 236         inlineRunStart = inlineRunEnd = curr;
 237
 238         if (!curr)
 239             return; // No more inline children to be found.
 240
 241         sawInline = curr->isInline();
 242
 243         curr = curr->nextSibling();
 244         while (curr && (curr->isInline() || curr->isFloatingOrPositioned()) && (curr != boundary)) {
 245             inlineRunEnd = curr;
 246             if (curr->isInline())
 247                 sawInline = true;
 248             curr = curr->nextSibling();
 249         }
 250     } while (!sawInline);
 251 }
 252
 253 void RenderBlock::deleteLineBoxTree()
 254 {
 255     InlineFlowBox* line = m_firstLineBox;
 256     InlineFlowBox* nextLine;
 257     while (line) {
 258         nextLine = line->nextFlowBox();
 259         line->deleteLine(renderArena());
 260         line = nextLine;
 261     }
 262     m_firstLineBox = m_lastLineBox = 0;
 263 }
 264
 265 void RenderBlock::makeChildrenNonInline(RenderObject *insertionPoint)
 266 {
 267     // makeChildrenNonInline takes a block whose children are *all* inline and it
 268     // makes sure that inline children are coalesced under anonymous
 269     // blocks.  If |insertionPoint| is defined, then it represents the insertion point for
 270     // the new block child that is causing us to have to wrap all the inlines.  This
 271     // means that we cannot coalesce inlines before |insertionPoint| with inlines following
 272     // |insertionPoint|, because the new child is going to be inserted in between the inlines,
 273     // splitting them.
 274     ASSERT(isInlineBlockOrInlineTable() || !isInline());
 275     ASSERT(!insertionPoint || insertionPoint->parent() == this);
 276
 277     m_childrenInline = false;
 278
 279     RenderObject *child = firstChild();
 280     if (!child)
 281         return;
 282
 283     deleteLineBoxTree();
 284
 285     while (child) {
 286         RenderObject *inlineRunStart, *inlineRunEnd;
 287         getInlineRun(child, insertionPoint, inlineRunStart, inlineRunEnd);
 288
 289         if (!inlineRunStart)
 290             break;
 291
 292         child = inlineRunEnd->nextSibling();
 293
 294         RenderBlock* box = createAnonymousBlock();
 295         insertChildNode(box, inlineRunStart);
 296         RenderObject* o = inlineRunStart;
 297         while(o != inlineRunEnd)
 298         {
 299             RenderObject* no = o;
 300             o = no->nextSibling();
 301             box->moveChildNode(no);
 302         }
 303         box->moveChildNode(inlineRunEnd);
 304     }
 305
 306 #ifndef NDEBUG
 307     for (RenderObject *c = firstChild(); c; c = c->nextSibling())
 308         ASSERT(!c->isInline());
 309 #endif
 310
 311     repaint();
 312 }
 313
 314 void RenderBlock::removeChild(RenderObject *oldChild)
 315 {
 316     // If this child is a block, and if our previous and next siblings are
 317     // both anonymous blocks with inline content, then we can go ahead and
 318     // fold the inline content back together.
 319     RenderObject* prev = oldChild->previousSibling();
 320     RenderObject* next = oldChild->nextSibling();
 321     bool canDeleteAnonymousBlocks = !documentBeingDestroyed() && !isInline() && !oldChild->isInline() &&
 322                                     !oldChild->continuation() &&
 323                                     (!prev || (prev->isAnonymousBlock() && prev->childrenInline())) &&
 324                                     (!next || (next->isAnonymousBlock() && next->childrenInline()));
 325     if (canDeleteAnonymousBlocks && prev && next) {
 326         // Take all the children out of the |next| block and put them in
 327         // the |prev| block.
 328         prev->setNeedsLayoutAndPrefWidthsRecalc();
 329         RenderObject* o = next->firstChild();
 330         while (o) {
 331             RenderObject* no = o;
 332             o = no->nextSibling();
 333             prev->moveChildNode(no);
 334         }
 335
 336         RenderBlock* nextBlock = static_cast<RenderBlock*>(next);
 337         nextBlock->deleteLineBoxTree();
 338
 339         // Nuke the now-empty block.
 340         next->destroy();
 341     }
 342
 343     RenderFlow::removeChild(oldChild);
 344
 345     RenderObject* child = prev ? prev : next;
 346     if (canDeleteAnonymousBlocks && child && !child->previousSibling() && !child->nextSibling() && !isFlexibleBox()) {
 347         // The removal has knocked us down to containing only a single anonymous
 348         // box.  We can go ahead and pull the content right back up into our
 349         // box.
 350         setNeedsLayoutAndPrefWidthsRecalc();
 351         RenderBlock* anonBlock = static_cast<RenderBlock*>(removeChildNode(child, false));
 352         m_childrenInline = true;
 353         RenderObject* o = anonBlock->firstChild();
 354         while (o) {
 355             RenderObject* no = o;
 356             o = no->nextSibling();
 357             moveChildNode(no);
 358         }
 359
 360         // Delete the now-empty block's lines and nuke it.
 361         anonBlock->deleteLineBoxTree();
 362         anonBlock->destroy();
 363     }
 364 }
 365
 366 int RenderBlock::overflowHeight(bool includeInterior) const
 367 {
 368     if (!includeInterior && hasOverflowClip()) {
 369         int shadowHeight = 0;
 370         for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next)
 371             shadowHeight = max(boxShadow->y + boxShadow->blur, shadowHeight);
 372         int height = m_height + shadowHeight;
 373         if (hasReflection())
 374             height = max(height, reflectionBox().bottom());
 375         return height;
 376     }
 377     return m_overflowHeight;
 378 }
 379
 380 int RenderBlock::overflowWidth(bool includeInterior) const
 381 {
 382     if (!includeInterior && hasOverflowClip()) {
 383         int shadowWidth = 0;
 384         for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next)
 385             shadowWidth = max(boxShadow->x + boxShadow->blur, shadowWidth);
 386         int width = m_width + shadowWidth;
 387         if (hasReflection())
 388             width = max(width, reflectionBox().right());
 389         return width;
 390     }
 391     return m_overflowWidth;
 392 }
 393
 394 int RenderBlock::overflowLeft(bool includeInterior) const
 395 {
 396     if (!includeInterior && hasOverflowClip()) {
 397         int shadowLeft = 0;
 398         for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next)
 399             shadowLeft = min(boxShadow->x - boxShadow->blur, shadowLeft);
 400         int left = shadowLeft;
 401         if (hasReflection())
 402             left = min(left, reflectionBox().x());
 403         return left;
 404     }
 405     return m_overflowLeft;
 406 }
 407
 408 int RenderBlock::overflowTop(bool includeInterior) const
 409 {
 410     if (!includeInterior && hasOverflowClip()) {
 411         int shadowTop = 0;
 412         for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next)
 413             shadowTop = min(boxShadow->y - boxShadow->blur, shadowTop);
 414         int top = shadowTop;
 415         if (hasReflection())
 416             top = min(top, reflectionBox().y());
 417         return top;
 418     }
 419     return m_overflowTop;
 420 }
 421
 422 IntRect RenderBlock::overflowRect(bool includeInterior) const
 423 {
 424     if (!includeInterior && hasOverflowClip()) {
 425         IntRect box = borderBox();
 426         int shadowLeft = 0;
 427         int shadowRight = 0;
 428         int shadowTop = 0;
 429         int shadowBottom = 0;
 430
 431         for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next) {
 432             shadowLeft = min(boxShadow->x - boxShadow->blur, shadowLeft);
 433             shadowRight = max(boxShadow->x + boxShadow->blur, shadowRight);
 434             shadowTop = min(boxShadow->y - boxShadow->blur, shadowTop);
 435             shadowBottom = max(boxShadow->y + boxShadow->blur, shadowBottom);
 436         }
 437
 438         box.move(shadowLeft, shadowTop);
 439         box.setWidth(box.width() - shadowLeft + shadowRight);
 440         box.setHeight(box.height() - shadowTop + shadowBottom);
 441
 442         if (hasReflection()) {
 443             IntRect reflection(reflectionBox());
 444             int reflectTop = min(box.y(), reflection.y());
 445             int reflectBottom = max(box.bottom(), reflection.bottom());
 446             box.setHeight(reflectBottom - reflectTop);
 447             box.setY(reflectTop);
 448
 449             int reflectLeft = min(box.x(), reflection.x());
 450             int reflectRight = max(box.right(), reflection.right());
 451             box.setWidth(reflectRight - reflectLeft);
 452             box.setX(reflectLeft);
 453         }
 454         return box;
 455     }
 456
 457     if (!includeInterior && hasOverflowClip())
 458         return borderBox();
 459     int l = overflowLeft(includeInterior);
 460     int t = min(overflowTop(includeInterior), -borderTopExtra());
 461     return IntRect(l, t, overflowWidth(includeInterior) - l, max(overflowHeight(includeInterior), height() + borderBottomExtra()) - t);
 462 }
 463
 464 bool RenderBlock::isSelfCollapsingBlock() const
 465 {
 466     // We are not self-collapsing if we
 467     // (a) have a non-zero height according to layout (an optimization to avoid wasting time)
 468     // (b) are a table,
 469     // (c) have border/padding,
 470     // (d) have a min-height
 471     // (e) have specified that one of our margins can't collapse using a CSS extension
 472     if (m_height > 0 ||
 473         isTable() || (borderBottom() + paddingBottom() + borderTop() + paddingTop()) != 0 ||
 474         style()->minHeight().isPositive() ||
 475         style()->marginTopCollapse() == MSEPARATE || style()->marginBottomCollapse() == MSEPARATE)
 476         return false;
 477
 478     bool hasAutoHeight = style()->height().isAuto();
 479     if (style()->height().isPercent() && !style()->htmlHacks()) {
 480         hasAutoHeight = true;
 481         for (RenderBlock* cb = containingBlock(); !cb->isRenderView(); cb = cb->containingBlock()) {
 482             if (cb->style()->height().isFixed() || cb->isTableCell())
 483                 hasAutoHeight = false;
 484         }
 485     }
 486
 487     // If the height is 0 or auto, then whether or not we are a self-collapsing block depends
 488     // on whether we have content that is all self-collapsing or not.
 489     if (hasAutoHeight || ((style()->height().isFixed() || style()->height().isPercent()) && style()->height().isZero())) {
 490         // If the block has inline children, see if we generated any line boxes.  If we have any
 491         // line boxes, then we can't be self-collapsing, since we have content.
 492         if (childrenInline())
 493             return !firstLineBox();
 494
 495         // Whether or not we collapse is dependent on whether all our normal flow children
 496         // are also self-collapsing.
 497         for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
 498             if (child->isFloatingOrPositioned())
 499                 continue;
 500             if (!child->isSelfCollapsingBlock())
 501                 return false;
 502         }
 503         return true;
 504     }
 505     return false;
 506 }
 507
 508 void RenderBlock::layout()
 509 {
 510     // Update our first letter info now.
 511     updateFirstLetter();
 512
 513     // Table cells call layoutBlock directly, so don't add any logic here.  Put code into
 514     // layoutBlock().
 515     layoutBlock(false);
 516
 517     // It's safe to check for control clip here, since controls can never be table cells.
 518     if (hasControlClip()) {
 519         // Because of the lightweight clip, there can never be any overflow from children.
 520         m_overflowWidth = m_width;
 521         m_overflowHeight = m_height;
 522         m_overflowLeft = 0;
 523         m_overflowTop = 0;
 524     }
 525 }
 526
 527 void RenderBlock::layoutBlock(bool relayoutChildren)
 528 {
 529     ASSERT(needsLayout());
 530
 531     if (isInline() && !isInlineBlockOrInlineTable()) // Inline <form>s inside various table elements can
 532         return;                                      // cause us to come in here.  Just bail.
 533
 534     if (!relayoutChildren && layoutOnlyPositionedObjects())
 535         return;
 536
 537     IntRect oldBounds;
 538     IntRect oldOutlineBox;
 539     bool checkForRepaint = checkForRepaintDuringLayout();
 540     if (checkForRepaint) {
 541         oldBounds = absoluteClippedOverflowRect();
 542         oldOutlineBox = absoluteOutlineBox();
 543     }
 544
 545     bool hadColumns = m_hasColumns;
 546     if (!hadColumns && !hasReflection())
 547         view()->pushLayoutState(this, IntSize(xPos(), yPos()));
 548     else
 549         view()->disableLayoutState();
 550
 551     int oldWidth = m_width;
 552     int oldColumnWidth = desiredColumnWidth();
 553
 554     calcWidth();
 555     calcColumnWidth();
 556
 557     m_overflowWidth = m_width;
 558     m_overflowLeft = 0;
 559
 560     if (oldWidth != m_width || oldColumnWidth != desiredColumnWidth())
 561         relayoutChildren = true;
 562
 563     clearFloats();
 564
 565     int previousHeight = m_height;
 566     m_height = 0;
 567     m_overflowHeight = 0;
 568
 569     // We use four values, maxTopPos, maxPosNeg, maxBottomPos, and maxBottomNeg, to track
 570     // our current maximal positive and negative margins.  These values are used when we
 571     // are collapsed with adjacent blocks, so for example, if you have block A and B
 572     // collapsing together, then you'd take the maximal positive margin from both A and B
 573     // and subtract it from the maximal negative margin from both A and B to get the
 574     // true collapsed margin.  This algorithm is recursive, so when we finish layout()
 575     // our block knows its current maximal positive/negative values.
 576     //
 577     // Start out by setting our margin values to our current margins.  Table cells have
 578     // no margins, so we don't fill in the values for table cells.
 579     bool isCell = isTableCell();
 580     if (!isCell) {
 581         initMaxMarginValues();
 582
 583         m_topMarginQuirk = style()->marginTop().quirk();
 584         m_bottomMarginQuirk = style()->marginBottom().quirk();
 585
 586         if (element() && element()->hasTagName(formTag) && element()->isMalformed())
 587             // See if this form is malformed (i.e., unclosed). If so, don't give the form
 588             // a bottom margin.
 589             setMaxBottomMargins(0, 0);
 590     }
 591
 592     // For overflow:scroll blocks, ensure we have both scrollbars in place always.
 593     if (scrollsOverflow()) {
 594         if (style()->overflowX() == OSCROLL)
 595             m_layer->setHasHorizontalScrollbar(true);
 596         if (style()->overflowY() == OSCROLL)
 597             m_layer->setHasVerticalScrollbar(true);
 598     }
 599
 600     int repaintTop = 0;
 601     int repaintBottom = 0;
 602     int maxFloatBottom = 0;
 603     if (childrenInline())
 604         layoutInlineChildren(relayoutChildren, repaintTop, repaintBottom);
 605     else
 606         layoutBlockChildren(relayoutChildren, maxFloatBottom);
 607
 608     // Expand our intrinsic height to encompass floats.
 609     int toAdd = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
 610     if (floatBottom() > (m_height - toAdd) && (isInlineBlockOrInlineTable() || isFloatingOrPositioned() || hasOverflowClip() ||
 611                                     (parent() && parent()->isFlexibleBox() || m_hasColumns)))
 612         m_height = floatBottom() + toAdd;
 613
 614     // Now lay out our columns within this intrinsic height, since they can slightly affect the intrinsic height as
 615     // we adjust for clean column breaks.
 616     int singleColumnBottom = layoutColumns();
 617
 618     // Calculate our new height.
 619     int oldHeight = m_height;
 620     calcHeight();
 621     if (oldHeight != m_height) {
 622         if (oldHeight > m_height && maxFloatBottom > m_height && !childrenInline()) {
 623             // One of our children's floats may have become an overhanging float for us. We need to look for it.
 624             for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
 625                 if (child->isBlockFlow() && !child->isFloatingOrPositioned()) {
 626                     RenderBlock* block = static_cast<RenderBlock*>(child);
 627                     if (block->floatBottom() + block->yPos() > m_height)
 628                         addOverhangingFloats(block, -block->xPos(), -block->yPos(), false);
 629                 }
 630             }
 631         }
 632         // We have to rebalance columns to the new height.
 633         layoutColumns(singleColumnBottom);
 634
 635         // If the block got expanded in size, then increase our overflowheight to match.
 636         if (m_overflowHeight > m_height)
 637             m_overflowHeight -= toAdd;
 638         if (m_overflowHeight < m_height)
 639             m_overflowHeight = m_height;
 640     }
 641     if (previousHeight != m_height)
 642         relayoutChildren = true;
 643
 644     // Some classes of objects (floats and fieldsets with no specified heights and table cells) expand to encompass
 645     // overhanging floats.
 646     if (hasOverhangingFloats() && expandsToEncloseOverhangingFloats()) {
 647         m_height = floatBottom();
 648         m_height += borderBottom() + paddingBottom();
 649     }
 650
 651     if ((isCell || isInline() || isFloatingOrPositioned() || isRoot()) && !hasOverflowClip() && !hasControlClip())
 652         addVisualOverflow(floatRect());
 653
 654     layoutPositionedObjects(relayoutChildren || isRoot());
 655
 656     positionListMarker();
 657
 658     // Always ensure our overflow width/height are at least as large as our width/height.
 659     m_overflowWidth = max(m_overflowWidth, m_width);
 660     m_overflowHeight = max(m_overflowHeight, m_height);
 661
 662     if (!hasOverflowClip()) {
 663         for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next) {
 664             m_overflowLeft = min(m_overflowLeft, boxShadow->x - boxShadow->blur);
 665             m_overflowWidth = max(m_overflowWidth, m_width + boxShadow->x + boxShadow->blur);
 666             m_overflowTop = min(m_overflowTop, boxShadow->y - boxShadow->blur);
 667             m_overflowHeight = max(m_overflowHeight, m_height + boxShadow->y + boxShadow->blur);
 668         }
 669
 670         if (hasReflection()) {
 671             m_overflowTop = min(m_overflowTop, reflectionBox().y());
 672             m_overflowHeight = max(m_overflowHeight, reflectionBox().bottom());
 673         }
 674     }
 675
 676     if (!hadColumns && !hasReflection())
 677         view()->popLayoutState();
 678     else
 679         view()->enableLayoutState();
 680
 681     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
 682     // we overflow or not.
 683     if (hasOverflowClip())
 684         m_layer->updateScrollInfoAfterLayout();
 685
 686     // Repaint with our new bounds if they are different from our old bounds.
 687     bool didFullRepaint = false;
 688     if (checkForRepaint)
 689         didFullRepaint = repaintAfterLayoutIfNeeded(oldBounds, oldOutlineBox);
 690     if (!didFullRepaint && repaintTop != repaintBottom && (style()->visibility() == VISIBLE || enclosingLayer()->hasVisibleContent())) {
 691         IntRect repaintRect(m_overflowLeft, repaintTop, m_overflowWidth - m_overflowLeft, repaintBottom - repaintTop);
 692
 693         // FIXME: Deal with multiple column repainting.  We have to split the repaint
 694         // rect up into multiple rects if it spans columns.
 695
 696         repaintRect.inflate(maximalOutlineSize(PaintPhaseOutline));
 697
 698         if (hasOverflowClip()) {
 699             // Adjust repaint rect for scroll offset
 700             int x = repaintRect.x();
 701             int y = repaintRect.y();
 702             layer()->subtractScrollOffset(x, y);
 703             repaintRect.setX(x);
 704             repaintRect.setY(y);
 705
 706             // Don't allow this rect to spill out of our overflow box.
 707             repaintRect.intersect(IntRect(0, 0, m_width, m_height));
 708         }
 709
 710         // Make sure the rect is still non-empty after intersecting for overflow above
 711         if (!repaintRect.isEmpty()) {
 712             repaintRectangle(repaintRect); // We need to do a partial repaint of our content.
 713             if (hasReflection())
 714                 layer()->reflection()->repaintRectangle(repaintRect);
 715         }
 716     }
 717     setNeedsLayout(false);
 718 }
 719
 720 void RenderBlock::adjustPositionedBlock(RenderObject* child, const MarginInfo& marginInfo)
 721 {
 722     if (child->hasStaticX()) {
 723         if (style()->direction() == LTR)
 724             child->setStaticX(borderLeft() + paddingLeft());
 725         else
 726             child->setStaticX(borderRight() + paddingRight());
 727     }
 728
 729     if (child->hasStaticY()) {
 730         int y = m_height;
 731         if (!marginInfo.canCollapseWithTop()) {
 732             child->calcVerticalMargins();
 733             int marginTop = child->marginTop();
 734             int collapsedTopPos = marginInfo.posMargin();
 735             int collapsedTopNeg = marginInfo.negMargin();
 736             if (marginTop > 0) {
 737                 if (marginTop > collapsedTopPos)
 738                     collapsedTopPos = marginTop;
 739             } else {
 740                 if (-marginTop > collapsedTopNeg)
 741                     collapsedTopNeg = -marginTop;
 742             }
 743             y += (collapsedTopPos - collapsedTopNeg) - marginTop;
 744         }
 745         child->setStaticY(y);
 746     }
 747 }
 748
 749 void RenderBlock::adjustFloatingBlock(const MarginInfo& marginInfo)
 750 {
 751     // The float should be positioned taking into account the bottom margin
 752     // of the previous flow.  We add that margin into the height, get the
 753     // float positioned properly, and then subtract the margin out of the
 754     // height again.  In the case of self-collapsing blocks, we always just
 755     // use the top margins, since the self-collapsing block collapsed its
 756     // own bottom margin into its top margin.
 757     //
 758     // Note also that the previous flow may collapse its margin into the top of
 759     // our block.  If this is the case, then we do not add the margin in to our
 760     // height when computing the position of the float.   This condition can be tested
 761     // for by simply calling canCollapseWithTop.  See
 762     // http://www.hixie.ch/tests/adhoc/css/box/block/margin-collapse/046.html for
 763     // an example of this scenario.
 764     int marginOffset = marginInfo.canCollapseWithTop() ? 0 : marginInfo.margin();
 765     m_height += marginOffset;
 766     positionNewFloats();
 767     m_height -= marginOffset;
 768 }
 769
 770 RenderObject* RenderBlock::handleSpecialChild(RenderObject* child, const MarginInfo& marginInfo, CompactInfo& compactInfo, bool& handled)
 771 {
 772     // Handle positioned children first.
 773     RenderObject* next = handlePositionedChild(child, marginInfo, handled);
 774     if (handled) return next;
 775
 776     // Handle floating children next.
 777     next = handleFloatingChild(child, marginInfo, handled);
 778     if (handled) return next;
 779
 780     // See if we have a compact element.  If we do, then try to tuck the compact element into the margin space of the next block.
 781     next = handleCompactChild(child, compactInfo, handled);
 782     if (handled) return next;
 783
 784     // Finally, see if we have a run-in element.
 785     return handleRunInChild(child, handled);
 786 }
 787
 788
 789 RenderObject* RenderBlock::handlePositionedChild(RenderObject* child, const MarginInfo& marginInfo, bool& handled)
 790 {
 791     if (child->isPositioned()) {
 792         handled = true;
 793         child->containingBlock()->insertPositionedObject(child);
 794         adjustPositionedBlock(child, marginInfo);
 795         return child->nextSibling();
 796     }
 797
 798     return 0;
 799 }
 800
 801 RenderObject* RenderBlock::handleFloatingChild(RenderObject* child, const MarginInfo& marginInfo, bool& handled)
 802 {
 803     if (child->isFloating()) {
 804         handled = true;
 805         insertFloatingObject(child);
 806         adjustFloatingBlock(marginInfo);
 807         return child->nextSibling();
 808     }
 809
 810     return 0;
 811 }
 812
 813 RenderObject* RenderBlock::handleCompactChild(RenderObject* child, CompactInfo& compactInfo, bool& handled)
 814 {
 815     // FIXME: We only deal with one compact at a time.  It is unclear what should be
 816     // done if multiple contiguous compacts are encountered.  For now we assume that
 817     // compact A followed by another compact B should simply be treated as block A.
 818     if (child->isCompact() && !compactInfo.compact() && (child->childrenInline() || child->isReplaced())) {
 819         // Get the next non-positioned/non-floating RenderBlock.
 820         RenderObject* next = child->nextSibling();
 821         RenderObject* curr = next;
 822         while (curr && curr->isFloatingOrPositioned())
 823             curr = curr->nextSibling();
 824         if (curr && curr->isRenderBlock() && !curr->isCompact() && !curr->isRunIn()) {
 825             curr->calcWidth(); // So that horizontal margins are correct.
 826
 827             child->setInline(true); // Need to compute the margins/width for the child as though it is an inline, so that it won't try to puff up the margins to
 828                                     // fill the containing block width.
 829             child->calcWidth();
 830             int childMargins = child->marginLeft() + child->marginRight();
 831             int margin = style()->direction() == LTR ? curr->marginLeft() : curr->marginRight();
 832             if (margin >= (childMargins + child->maxPrefWidth())) {
 833                 // The compact will fit in the margin.
 834                 handled = true;
 835                 compactInfo.set(child, curr);
 836                 child->setPos(0,0); // This position will be updated to reflect the compact's
 837                                     // desired position and the line box for the compact will
 838                                     // pick that position up.
 839
 840                 // Remove the child.
 841                 RenderObject* next = child->nextSibling();
 842                 removeChildNode(child);
 843
 844                 // Now insert the child under |curr|.
 845                 curr->insertChildNode(child, curr->firstChild());
 846                 return next;
 847             }
 848             else
 849                 child->setInline(false); // We didn't fit, so we remain a block-level element.
 850         }
 851     }
 852     return 0;
 853 }
 854
 855 void RenderBlock::insertCompactIfNeeded(RenderObject* child, CompactInfo& compactInfo)
 856 {
 857     if (compactInfo.matches(child)) {
 858         // We have a compact child to squeeze in.
 859         RenderObject* compactChild = compactInfo.compact();
 860         int compactXPos = borderLeft() + paddingLeft() + compactChild->marginLeft();
 861         if (style()->direction() == RTL) {
 862             compactChild->calcWidth(); // have to do this because of the capped maxwidth
 863             compactXPos = width() - borderRight() - paddingRight() - marginRight() -
 864                 compactChild->width() - compactChild->marginRight();
 865         }
 866         compactXPos -= child->xPos(); // Put compactXPos into the child's coordinate space.
 867         compactChild->setPos(compactXPos, compactChild->yPos()); // Set the x position.
 868         compactInfo.clear();
 869     }
 870 }
 871
 872 RenderObject* RenderBlock::handleRunInChild(RenderObject* child, bool& handled)
 873 {
 874     // See if we have a run-in element with inline children.  If the
 875     // children aren't inline, then just treat the run-in as a normal
 876     // block.
 877     if (child->isRunIn() && (child->childrenInline() || child->isReplaced())) {
 878         // Get the next non-positioned/non-floating RenderBlock.
 879         RenderObject* curr = child->nextSibling();
 880         while (curr && curr->isFloatingOrPositioned())
 881             curr = curr->nextSibling();
 882         if (curr && (curr->isRenderBlock() && curr->childrenInline() && !curr->isCompact() && !curr->isRunIn())) {
 883             // The block acts like an inline, so just null out its
 884             // position.
 885             handled = true;
 886             child->setInline(true);
 887             child->setPos(0,0);
 888
 889             // Remove the child.
 890             RenderObject* next = child->nextSibling();
 891             removeChildNode(child);
 892
 893             // Now insert the child under |curr|.
 894             curr->insertChildNode(child, curr->firstChild());
 895             return next;
 896         }
 897     }
 898     return 0;
 899 }
 900
 901 void RenderBlock::collapseMargins(RenderObject* child, MarginInfo& marginInfo, int yPosEstimate)
 902 {
 903     // Get our max pos and neg top margins.
 904     int posTop = child->maxTopMargin(true);
 905     int negTop = child->maxTopMargin(false);
 906
 907     // For self-collapsing blocks, collapse our bottom margins into our
 908     // top to get new posTop and negTop values.
 909     if (child->isSelfCollapsingBlock()) {
 910         posTop = max(posTop, child->maxBottomMargin(true));
 911         negTop = max(negTop, child->maxBottomMargin(false));
 912     }
 913
 914     // See if the top margin is quirky. We only care if this child has
 915     // margins that will collapse with us.
 916     bool topQuirk = child->isTopMarginQuirk() || style()->marginTopCollapse() == MDISCARD;
 917
 918     if (marginInfo.canCollapseWithTop()) {
 919         // This child is collapsing with the top of the
 920         // block.  If it has larger margin values, then we need to update
 921         // our own maximal values.
 922         if (!style()->htmlHacks() || !marginInfo.quirkContainer() || !topQuirk)
 923             setMaxTopMargins(max(posTop, maxTopPosMargin()), max(negTop, maxTopNegMargin()));
 924
 925         // The minute any of the margins involved isn't a quirk, don't
 926         // collapse it away, even if the margin is smaller (www.webreference.com
 927         // has an example of this, a <dt> with 0.8em author-specified inside
 928         // a <dl> inside a <td>.
 929         if (!marginInfo.determinedTopQuirk() && !topQuirk && (posTop-negTop)) {
 930             m_topMarginQuirk = false;
 931             marginInfo.setDeterminedTopQuirk(true);
 932         }
 933
 934         if (!marginInfo.determinedTopQuirk() && topQuirk && marginTop() == 0)
 935             // We have no top margin and our top child has a quirky margin.
 936             // We will pick up this quirky margin and pass it through.
 937             // This deals with the <td><div><p> case.
 938             // Don't do this for a block that split two inlines though.  You do
 939             // still apply margins in this case.
 940             m_topMarginQuirk = true;
 941     }
 942
 943     if (marginInfo.quirkContainer() && marginInfo.atTopOfBlock() && (posTop - negTop))
 944         marginInfo.setTopQuirk(topQuirk);
 945
 946     int ypos = m_height;
 947     if (child->isSelfCollapsingBlock()) {
 948         // This child has no height.  We need to compute our
 949         // position before we collapse the child's margins together,
 950         // so that we can get an accurate position for the zero-height block.
 951         int collapsedTopPos = max(marginInfo.posMargin(), child->maxTopMargin(true));
 952         int collapsedTopNeg = max(marginInfo.negMargin(), child->maxTopMargin(false));
 953         marginInfo.setMargin(collapsedTopPos, collapsedTopNeg);
 954
 955         // Now collapse the child's margins together, which means examining our
 956         // bottom margin values as well.
 957         marginInfo.setPosMarginIfLarger(child->maxBottomMargin(true));
 958         marginInfo.setNegMarginIfLarger(child->maxBottomMargin(false));
 959
 960         if (!marginInfo.canCollapseWithTop())
 961             // We need to make sure that the position of the self-collapsing block
 962             // is correct, since it could have overflowing content
 963             // that needs to be positioned correctly (e.g., a block that
 964             // had a specified height of 0 but that actually had subcontent).
 965             ypos = m_height + collapsedTopPos - collapsedTopNeg;
 966     }
 967     else {
 968         if (child->style()->marginTopCollapse() == MSEPARATE) {
 969             m_height += marginInfo.margin() + child->marginTop();
 970             ypos = m_height;
 971         }
 972         else if (!marginInfo.atTopOfBlock() ||
 973             (!marginInfo.canCollapseTopWithChildren()
 974              && (!style()->htmlHacks() || !marginInfo.quirkContainer() || !marginInfo.topQuirk()))) {
 975             // We're collapsing with a previous sibling's margins and not
 976             // with the top of the block.
 977             m_height += max(marginInfo.posMargin(), posTop) - max(marginInfo.negMargin(), negTop);
 978             ypos = m_height;
 979         }
 980
 981         marginInfo.setPosMargin(child->maxBottomMargin(true));
 982         marginInfo.setNegMargin(child->maxBottomMargin(false));
 983
 984         if (marginInfo.margin())
 985             marginInfo.setBottomQuirk(child->isBottomMarginQuirk() || style()->marginBottomCollapse() == MDISCARD);
 986
 987         marginInfo.setSelfCollapsingBlockClearedFloat(false);
 988     }
 989
 990     view()->addLayoutDelta(IntSize(0, yPosEstimate - ypos));
 991     child->setPos(child->xPos(), ypos);
 992     if (ypos != yPosEstimate) {
 993         if (child->shrinkToAvoidFloats())
 994             // The child's width depends on the line width.
 995             // When the child shifts to clear an item, its width can
 996             // change (because it has more available line width).
 997             // So go ahead and mark the item as dirty.
 998             child->setChildNeedsLayout(true, false);
 999
1000         if (!child->avoidsFloats() && child->containsFloats())
1001             child->markAllDescendantsWithFloatsForLayout();
1002
1003         // Our guess was wrong. Make the child lay itself out again.
1004         child->layoutIfNeeded();
1005     }
1006 }
1007
1008 void RenderBlock::clearFloatsIfNeeded(RenderObject* child, MarginInfo& marginInfo, int oldTopPosMargin, int oldTopNegMargin)
1009 {
1010     int heightIncrease = getClearDelta(child);
1011     if (!heightIncrease)
1012         return;
1013
1014     // The child needs to be lowered.  Move the child so that it just clears the float.
1015     view()->addLayoutDelta(IntSize(0, -heightIncrease));
1016     child->setPos(child->xPos(), child->yPos() + heightIncrease);
1017
1018     if (child->isSelfCollapsingBlock()) {
1019         // For self-collapsing blocks that clear, they can still collapse their
1020         // margins with following siblings.  Reset the current margins to represent
1021         // the self-collapsing block's margins only.
1022         marginInfo.setPosMargin(max(child->maxTopMargin(true), child->maxBottomMargin(true)));
1023         marginInfo.setNegMargin(max(child->maxTopMargin(false), child->maxBottomMargin(false)));
1024
1025         // Adjust our height such that we are ready to be collapsed with subsequent siblings.
1026         m_height = child->yPos() - max(0, marginInfo.margin());
1027
1028         // Set a flag that we cleared a float so that we know both to increase the height of the block
1029         // to compensate for the clear and to avoid collapsing our margins with the parent block's
1030         // bottom margin.
1031         marginInfo.setSelfCollapsingBlockClearedFloat(true);
1032     } else
1033         // Increase our height by the amount we had to clear.
1034         m_height += heightIncrease;
1035
1036     if (marginInfo.canCollapseWithTop()) {
1037         // We can no longer collapse with the top of the block since a clear
1038         // occurred.  The empty blocks collapse into the cleared block.
1039         // FIXME: This isn't quite correct.  Need clarification for what to do
1040         // if the height the cleared block is offset by is smaller than the
1041         // margins involved.
1042         setMaxTopMargins(oldTopPosMargin, oldTopNegMargin);
1043         marginInfo.setAtTopOfBlock(false);
1044     }
1045
1046     // If our value of clear caused us to be repositioned vertically to be
1047     // underneath a float, we might have to do another layout to take into account
1048     // the extra space we now have available.
1049     if (child->shrinkToAvoidFloats())
1050         // The child's width depends on the line width.
1051         // When the child shifts to clear an item, its width can
1052         // change (because it has more available line width).
1053         // So go ahead and mark the item as dirty.
1054         child->setChildNeedsLayout(true, false);
1055     if (!child->avoidsFloats() && child->containsFloats())
1056         child->markAllDescendantsWithFloatsForLayout();
1057     child->layoutIfNeeded();
1058 }
1059
1060 int RenderBlock::estimateVerticalPosition(RenderObject* child, const MarginInfo& marginInfo)
1061 {
1062     // FIXME: We need to eliminate the estimation of vertical position, because when it's wrong we sometimes trigger a pathological
1063     // relayout if there are intruding floats.
1064     int yPosEstimate = m_height;
1065     if (!marginInfo.canCollapseWithTop()) {
1066         int childMarginTop = child->selfNeedsLayout() ? child->marginTop() : child->collapsedMarginTop();
1067         yPosEstimate += max(marginInfo.margin(), childMarginTop);
1068     }
1069     return yPosEstimate;
1070 }
1071
1072 void RenderBlock::determineHorizontalPosition(RenderObject* child)
1073 {
1074     if (style()->direction() == LTR) {
1075         int xPos = borderLeft() + paddingLeft();
1076
1077         // Add in our left margin.
1078         int chPos = xPos + child->marginLeft();
1079
1080         // Some objects (e.g., tables, horizontal rules, overflow:auto blocks) avoid floats.  They need
1081         // to shift over as necessary to dodge any floats that might get in the way.
1082         if (child->avoidsFloats()) {
1083             int leftOff = leftOffset(m_height);
1084             if (style()->textAlign() != WEBKIT_CENTER && child->style()->marginLeft().type() != Auto) {
1085                 if (child->marginLeft() < 0)
1086                     leftOff += child->marginLeft();
1087                 chPos = max(chPos, leftOff); // Let the float sit in the child's margin if it can fit.
1088             }
1089             else if (leftOff != xPos) {
1090                 // The object is shifting right. The object might be centered, so we need to
1091                 // recalculate our horizontal margins. Note that the containing block content
1092                 // width computation will take into account the delta between |leftOff| and |xPos|
1093                 // so that we can just pass the content width in directly to the |calcHorizontalMargins|
1094                 // function.
1095                 static_cast<RenderBox*>(child)->calcHorizontalMargins(child->style()->marginLeft(), child->style()->marginRight(), lineWidth(child->yPos()));
1096                 chPos = leftOff + child->marginLeft();
1097             }
1098         }
1099         view()->addLayoutDelta(IntSize(child->xPos() - chPos, 0));
1100         child->setPos(chPos, child->yPos());
1101     } else {
1102         int xPos = m_width - borderRight() - paddingRight() - verticalScrollbarWidth();
1103         int chPos = xPos - (child->width() + child->marginRight());
1104         if (child->avoidsFloats()) {
1105             int rightOff = rightOffset(m_height);
1106             if (style()->textAlign() != WEBKIT_CENTER && child->style()->marginRight().type() != Auto) {
1107                 if (child->marginRight() < 0)
1108                     rightOff -= child->marginRight();
1109                 chPos = min(chPos, rightOff - child->width()); // Let the float sit in the child's margin if it can fit.
1110             } else if (rightOff != xPos) {
1111                 // The object is shifting left. The object might be centered, so we need to
1112                 // recalculate our horizontal margins. Note that the containing block content
1113                 // width computation will take into account the delta between |rightOff| and |xPos|
1114                 // so that we can just pass the content width in directly to the |calcHorizontalMargins|
1115                 // function.
1116                 static_cast<RenderBox*>(child)->calcHorizontalMargins(child->style()->marginLeft(), child->style()->marginRight(), lineWidth(child->yPos()));
1117                 chPos = rightOff - child->marginRight() - child->width();
1118             }
1119         }
1120         view()->addLayoutDelta(IntSize(child->xPos() - chPos, 0));
1121         child->setPos(chPos, child->yPos());
1122     }
1123 }
1124
1125 void RenderBlock::setCollapsedBottomMargin(const MarginInfo& marginInfo)
1126 {
1127     if (marginInfo.canCollapseWithBottom() && !marginInfo.canCollapseWithTop()) {
1128         // Update our max pos/neg bottom margins, since we collapsed our bottom margins
1129         // with our children.
1130         setMaxBottomMargins(max(maxBottomPosMargin(), marginInfo.posMargin()), max(maxBottomNegMargin(), marginInfo.negMargin()));
1131
1132         if (!marginInfo.bottomQuirk())
1133             m_bottomMarginQuirk = false;
1134
1135         if (marginInfo.bottomQuirk() && marginBottom() == 0)
1136             // We have no bottom margin and our last child has a quirky margin.
1137             // We will pick up this quirky margin and pass it through.
1138             // This deals with the <td><div><p> case.
1139             m_bottomMarginQuirk = true;
1140     }
1141 }
1142
1143 void RenderBlock::handleBottomOfBlock(int top, int bottom, MarginInfo& marginInfo)
1144 {
1145     // If our last flow was a self-collapsing block that cleared a float, then we don't
1146     // collapse it with the bottom of the block.
1147     if (!marginInfo.selfCollapsingBlockClearedFloat())
1148         marginInfo.setAtBottomOfBlock(true);
1149     else {
1150         // We have to special case the negative margin situation (where the collapsed
1151         // margin of the self-collapsing block is negative), since there's no need
1152         // to make an adjustment in that case.
1153         if (marginInfo.margin() < 0)
1154             marginInfo.clearMargin();
1155     }
1156
1157     // If we can't collapse with children then go ahead and add in the bottom margin.
1158     if (!marginInfo.canCollapseWithBottom() && !marginInfo.canCollapseWithTop()
1159         && (!style()->htmlHacks() || !marginInfo.quirkContainer() || !marginInfo.bottomQuirk()))
1160         m_height += marginInfo.margin();
1161
1162     // Now add in our bottom border/padding.
1163     m_height += bottom;
1164
1165     // Negative margins can cause our height to shrink below our minimal height (border/padding).
1166     // If this happens, ensure that the computed height is increased to the minimal height.
1167     m_height = max(m_height, top + bottom);
1168
1169     // Always make sure our overflow height is at least our height.
1170     m_overflowHeight = max(m_height, m_overflowHeight);
1171
1172     // Update our bottom collapsed margin info.
1173     setCollapsedBottomMargin(marginInfo);
1174 }
1175
1176 void RenderBlock::layoutBlockChildren(bool relayoutChildren, int& maxFloatBottom)
1177 {
1178     int top = borderTop() + paddingTop();
1179     int bottom = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
1180
1181     m_height = m_overflowHeight = top;
1182
1183     // The margin struct caches all our current margin collapsing state.  The compact struct caches state when we encounter compacts,
1184     MarginInfo marginInfo(this, top, bottom);
1185     CompactInfo compactInfo;
1186
1187     // Fieldsets need to find their legend and position it inside the border of the object.
1188     // The legend then gets skipped during normal layout.
1189     RenderObject* legend = layoutLegend(relayoutChildren);
1190
1191     int previousFloatBottom = 0;
1192     maxFloatBottom = 0;
1193
1194     RenderObject* child = firstChild();
1195     while (child) {
1196         if (legend == child) {
1197             child = child->nextSibling();
1198             continue; // Skip the legend, since it has already been positioned up in the fieldset's border.
1199         }
1200
1201         int oldTopPosMargin = maxTopPosMargin();
1202         int oldTopNegMargin = maxTopNegMargin();
1203
1204         // Make sure we layout children if they need it.
1205         // FIXME: Technically percentage height objects only need a relayout if their percentage isn't going to be turned into
1206         // an auto value.  Add a method to determine this, so that we can avoid the relayout.
1207         if (relayoutChildren || ((child->style()->height().isPercent() || child->style()->minHeight().isPercent() || child->style()->maxHeight().isPercent()) && !isRenderView()))
1208             child->setChildNeedsLayout(true, false);
1209
1210         // If relayoutChildren is set and we have percentage padding, we also need to invalidate the child's pref widths.
1211         if (relayoutChildren && (child->style()->paddingLeft().isPercent() || child->style()->paddingRight().isPercent()))
1212             child->setPrefWidthsDirty(true, false);
1213
1214         // Handle the four types of special elements first.  These include positioned content, floating content, compacts and
1215         // run-ins.  When we encounter these four types of objects, we don't actually lay them out as normal flow blocks.
1216         bool handled = false;
1217         RenderObject* next = handleSpecialChild(child, marginInfo, compactInfo, handled);
1218         if (handled) { child = next; continue; }
1219
1220         // The child is a normal flow object.  Compute its vertical margins now.
1221         child->calcVerticalMargins();
1222
1223         // Do not allow a collapse if the margin top collapse style is set to SEPARATE.
1224         if (child->style()->marginTopCollapse() == MSEPARATE) {
1225             marginInfo.setAtTopOfBlock(false);
1226             marginInfo.clearMargin();
1227         }
1228
1229         // Try to guess our correct y position.  In most cases this guess will
1230         // be correct.  Only if we're wrong (when we compute the real y position)
1231         // will we have to potentially relayout.
1232         int yPosEstimate = estimateVerticalPosition(child, marginInfo);
1233
1234         // Cache our old rect so that we can dirty the proper repaint rects if the child moves.
1235         IntRect oldRect(child->xPos(), child->yPos() , child->width(), child->height());
1236
1237         // Go ahead and position the child as though it didn't collapse with the top.
1238         view()->addLayoutDelta(IntSize(0, child->yPos() - yPosEstimate));
1239         child->setPos(child->xPos(), yPosEstimate);
1240
1241         bool markDescendantsWithFloats = false;
1242         if (yPosEstimate != oldRect.y() && !child->avoidsFloats() && child->containsFloats())
1243             markDescendantsWithFloats = true;
1244         else if (!child->avoidsFloats() || child->shrinkToAvoidFloats()) {
1245             // If an element might be affected by the presence of floats, then always mark it for
1246             // layout.
1247             int fb = max(previousFloatBottom, floatBottom());
1248             if (fb > m_height || fb > yPosEstimate)
1249                 markDescendantsWithFloats = true;
1250         }
1251
1252         if (markDescendantsWithFloats)
1253             child->markAllDescendantsWithFloatsForLayout();
1254
1255         if (child->isRenderBlock())
1256             previousFloatBottom = max(previousFloatBottom, oldRect.y() + static_cast<RenderBlock*>(child)->floatBottom());
1257
1258         bool childNeededLayout = child->needsLayout();
1259         if (childNeededLayout)
1260             child->layout();
1261
1262         // Now determine the correct ypos based off examination of collapsing margin
1263         // values.
1264         collapseMargins(child, marginInfo, yPosEstimate);
1265         int postCollapseChildY = child->yPos();
1266
1267         // Now check for clear.
1268         clearFloatsIfNeeded(child, marginInfo, oldTopPosMargin, oldTopNegMargin);
1269
1270         // We are no longer at the top of the block if we encounter a non-empty child.
1271         // This has to be done after checking for clear, so that margins can be reset if a clear occurred.
1272         if (marginInfo.atTopOfBlock() && !child->isSelfCollapsingBlock())
1273             marginInfo.setAtTopOfBlock(false);
1274
1275         // Now place the child in the correct horizontal position
1276         determineHorizontalPosition(child);
1277
1278         // Update our height now that the child has been placed in the correct position.
1279         m_height += child->height();
1280         if (child->style()->marginBottomCollapse() == MSEPARATE) {
1281             m_height += child->marginBottom();
1282             marginInfo.clearMargin();
1283         }
1284         // If the child has overhanging floats that intrude into following siblings (or possibly out
1285         // of this block), then the parent gets notified of the floats now.
1286         maxFloatBottom = max(maxFloatBottom, addOverhangingFloats(static_cast<RenderBlock *>(child), -child->xPos(), -child->yPos(), !childNeededLayout));
1287
1288         // Update our overflow in case the child spills out the block.
1289         m_overflowTop = min(m_overflowTop, child->yPos() + child->overflowTop(false));
1290         m_overflowHeight = max(m_overflowHeight, m_height + child->overflowHeight(false) - child->height());
1291         m_overflowWidth = max(child->xPos() + child->overflowWidth(false), m_overflowWidth);
1292         m_overflowLeft = min(child->xPos() + child->overflowLeft(false), m_overflowLeft);
1293
1294         // Insert our compact into the block margin if we have one.
1295         insertCompactIfNeeded(child, compactInfo);
1296
1297         view()->addLayoutDelta(IntSize(child->xPos() - oldRect.x(), child->yPos() - oldRect.y()));
1298
1299         // If the child moved, we have to repaint it as well as any floating/positioned
1300         // descendants.  An exception is if we need a layout.  In this case, we know we're going to
1301         // repaint ourselves (and the child) anyway.
1302         if (!selfNeedsLayout() && child->checkForRepaintDuringLayout()) {
1303             int finalChildX = child->xPos();
1304             int finalChildY = child->yPos();
1305             if (finalChildX != oldRect.x() || finalChildY != oldRect.y())
1306                 child->repaintDuringLayoutIfMoved(oldRect);
1307             else if (finalChildY != yPosEstimate || finalChildY != postCollapseChildY) {
1308                 // The child invalidated itself during layout at an intermediate position,
1309                 // but not at its final position. Take care of it now.
1310                 child->repaint();
1311                 child->repaintOverhangingFloats();
1312             }
1313         }
1314
1315         child = child->nextSibling();
1316     }
1317
1318     // Now do the handling of the bottom of the block, adding in our bottom border/padding and
1319     // determining the correct collapsed bottom margin information.
1320     handleBottomOfBlock(top, bottom, marginInfo);
1321 }
1322
1323 bool RenderBlock::layoutOnlyPositionedObjects()
1324 {
1325     if (!posChildNeedsLayout() || normalChildNeedsLayout() || selfNeedsLayout())
1326         return false;
1327
1328     if (!m_hasColumns)
1329         view()->pushLayoutState(this, IntSize(xPos(), yPos()));
1330     else
1331         view()->disableLayoutState();
1332
1333     if (needsPositionedMovementLayout()) {
1334         calcWidth();
1335         calcHeight();
1336     }
1337
1338     // All we have to is lay out our positioned objects.
1339     layoutPositionedObjects(false);
1340
1341     if (!m_hasColumns)
1342         view()->popLayoutState();
1343     else
1344         view()->enableLayoutState();
1345
1346     if (hasOverflowClip())
1347         m_layer->updateScrollInfoAfterLayout();
1348
1349     setNeedsLayout(false);
1350     return true;
1351 }
1352
1353 void RenderBlock::layoutPositionedObjects(bool relayoutChildren)
1354 {
1355     if (m_positionedObjects) {
1356         RenderObject* r;
1357         Iterator end = m_positionedObjects->end();
1358         for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
1359             r = *it;
1360             // When a non-positioned block element moves, it may have positioned children that are implicitly positioned relative to the
1361             // non-positioned block.  Rather than trying to detect all of these movement cases, we just always lay out positioned
1362             // objects that are positioned implicitly like this.  Such objects are rare, and so in typical DHTML menu usage (where everything is
1363             // positioned explicitly) this should not incur a performance penalty.
1364             if (relayoutChildren || (r->hasStaticY() && r->parent() != this && r->parent()->isBlockFlow()))
1365                 r->setChildNeedsLayout(true, false);
1366
1367             // If relayoutChildren is set and we have percentage padding, we also need to invalidate the child's pref widths.
1368             if (relayoutChildren && (r->style()->paddingLeft().isPercent() || r->style()->paddingRight().isPercent()))
1369                 r->setPrefWidthsDirty(true, false);
1370
1371             // We don't have to do a full layout.  We just have to update our position.
1372             if (r->needsPositionedMovementLayoutOnly())
1373                 r->layoutDoingPositionedMovementOnly();
1374             else
1375                 r->layoutIfNeeded();
1376         }
1377     }
1378 }
1379
1380 void RenderBlock::markPositionedObjectsForLayout()
1381 {
1382     if (m_positionedObjects) {
1383         RenderObject* r;
1384         Iterator end = m_positionedObjects->end();
1385         for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
1386             r = *it;
1387             r->setChildNeedsLayout(true);
1388         }
1389     }
1390 }
1391
1392 void RenderBlock::repaintOverhangingFloats(bool paintAllDescendants)
1393 {
1394     // Repaint any overhanging floats (if we know we're the one to paint them).
1395     if (hasOverhangingFloats()) {
1396         // We think that we must be in a bad state if m_floatingObjects is nil at this point, so
1397         // we assert on Debug builds and nil-check Release builds.
1398         ASSERT(m_floatingObjects);
1399         if (!m_floatingObjects)
1400             return;
1401
1402         FloatingObject* r;
1403         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
1404
1405         // FIXME: Avoid disabling LayoutState. At the very least, don't disable it for floats originating
1406         // in this block. Better yet would be to push extra state for the containers of other floats.
1407         view()->disableLayoutState();
1408         for ( ; (r = it.current()); ++it) {
1409             // Only repaint the object if it is overhanging, is not in its own layer, and
1410             // is our responsibility to paint (m_shouldPaint is set). When paintAllDescendants is true, the latter
1411             // condition is replaced with being a descendant of us.
1412             if (r->m_bottom > m_height && (paintAllDescendants && r->m_renderer->isDescendantOf(this) || r->m_shouldPaint) && !r->m_renderer->hasLayer()) {
1413                 r->m_renderer->repaint();
1414                 r->m_renderer->repaintOverhangingFloats();
1415             }
1416         }
1417         view()->enableLayoutState();
1418     }
1419 }
1420
1421 void RenderBlock::paint(PaintInfo& paintInfo, int tx, int ty)
1422 {
1423     tx += m_x;
1424     ty += m_y;
1425
1426     PaintPhase phase = paintInfo.phase;
1427
1428     // Check if we need to do anything at all.
1429     // FIXME: Could eliminate the isRoot() check if we fix background painting so that the RenderView
1430     // paints the root's background.
1431     if (!isInlineFlow() && !isRoot()) {
1432         IntRect overflowBox = overflowRect(false);
1433         overflowBox.inflate(maximalOutlineSize(paintInfo.phase));
1434         overflowBox.move(tx, ty);
1435         if (!overflowBox.intersects(paintInfo.rect))
1436             return;
1437     }
1438
1439     bool useControlClip = phase != PaintPhaseBlockBackground && phase != PaintPhaseSelfOutline && phase != PaintPhaseMask && hasControlClip();
1440
1441     // Push a clip.
1442     if (useControlClip) {
1443         if (phase == PaintPhaseOutline)
1444             paintInfo.phase = PaintPhaseChildOutlines;
1445         else if (phase == PaintPhaseChildBlockBackground) {
1446             paintInfo.phase = PaintPhaseBlockBackground;
1447             paintObject(paintInfo, tx, ty);
1448             paintInfo.phase = PaintPhaseChildBlockBackgrounds;
1449         }
1450         IntRect clipRect(controlClipRect(tx, ty));
1451         if (clipRect.isEmpty())
1452             return;
1453         paintInfo.context->save();
1454         paintInfo.context->clip(clipRect);
1455     }
1456
1457     paintObject(paintInfo, tx, ty);
1458
1459     // Pop the clip.
1460     if (useControlClip) {
1461         paintInfo.context->restore();
1462         if (phase == PaintPhaseOutline) {
1463             paintInfo.phase = PaintPhaseSelfOutline;
1464             paintObject(paintInfo, tx, ty);
1465             paintInfo.phase = phase;
1466         } else if (phase == PaintPhaseChildBlockBackground)
1467             paintInfo.phase = phase;
1468     }
1469 }
1470
1471 void RenderBlock::paintColumns(PaintInfo& paintInfo, int tx, int ty, bool paintingFloats)
1472 {
1473     // We need to do multiple passes, breaking up our child painting into strips.
1474     GraphicsContext* context = paintInfo.context;
1475     int currXOffset = 0;
1476     int currYOffset = 0;
1477     int ruleAdd = borderLeft() + paddingLeft();
1478     int ruleX = 0;
1479     int colGap = columnGap();
1480     const Color& ruleColor = style()->columnRuleColor();
1481     bool ruleTransparent = style()->columnRuleIsTransparent();
1482     EBorderStyle ruleStyle = style()->columnRuleStyle();
1483     int ruleWidth = style()->columnRuleWidth();
1484     bool renderRule = !paintingFloats && ruleStyle > BHIDDEN && !ruleTransparent && ruleWidth <= colGap;
1485     Vector<IntRect>* colRects = columnRects();
1486     unsigned colCount = colRects->size();
1487     for (unsigned i = 0; i < colCount; i++) {
1488         // For each rect, we clip to the rect, and then we adjust our coords.
1489         IntRect colRect = colRects->at(i);
1490         colRect.move(tx, ty);
1491         context->save();
1492
1493         // Each strip pushes a clip, since column boxes are specified as being
1494         // like overflow:hidden.
1495         context->clip(colRect);
1496
1497         // Adjust tx and ty to change where we paint.
1498         PaintInfo info(paintInfo);
1499         info.rect.intersect(colRect);
1500
1501         // Adjust our x and y when painting.
1502         int finalX = tx + currXOffset;
1503         int finalY = ty + currYOffset;
1504         if (paintingFloats)
1505             paintFloats(info, finalX, finalY, paintInfo.phase == PaintPhaseSelection || paintInfo.phase == PaintPhaseTextClip);
1506         else
1507             paintContents(info, finalX, finalY);
1508
1509         // Move to the next position.
1510         if (style()->direction() == LTR) {
1511             ruleX += colRect.width() + colGap / 2;
1512             currXOffset += colRect.width() + colGap;
1513         } else {
1514             ruleX -= (colRect.width() + colGap / 2);
1515             currXOffset -= (colRect.width() + colGap);
1516         }
1517
1518         currYOffset -= colRect.height();
1519
1520         context->restore();
1521
1522         // Now paint the column rule.
1523         if (renderRule && paintInfo.phase == PaintPhaseForeground && i < colCount - 1) {
1524             int ruleStart = ruleX - ruleWidth / 2 + ruleAdd;
1525             int ruleEnd = ruleStart + ruleWidth;
1526             drawBorder(paintInfo.context, tx + ruleStart, ty + borderTop() + paddingTop(), tx + ruleEnd, ty + borderTop() + paddingTop() + contentHeight(),
1527                        style()->direction() == LTR ? BSLeft : BSRight, ruleColor, style()->color(), ruleStyle, 0, 0);
1528         }
1529
1530         ruleX = currXOffset;
1531     }
1532 }
1533
1534 void RenderBlock::paintContents(PaintInfo& paintInfo, int tx, int ty)
1535 {
1536     // Avoid painting descendants of the root element when stylesheets haven't loaded.  This eliminates FOUC.
1537     // It's ok not to draw, because later on, when all the stylesheets do load, updateStyleSelector on the Document
1538     // will do a full repaint().
1539     if (document()->didLayoutWithPendingStylesheets() && !isRenderView())
1540         return;
1541
1542     if (childrenInline())
1543         paintLines(paintInfo, tx, ty);
1544     else
1545         paintChildren(paintInfo, tx, ty);
1546 }
1547
1548 void RenderBlock::paintChildren(PaintInfo& paintInfo, int tx, int ty)
1549 {
1550     PaintPhase newPhase = (paintInfo.phase == PaintPhaseChildOutlines) ? PaintPhaseOutline : paintInfo.phase;
1551     newPhase = (newPhase == PaintPhaseChildBlockBackgrounds) ? PaintPhaseChildBlockBackground : newPhase;
1552
1553     // We don't paint our own background, but we do let the kids paint their backgrounds.
1554     PaintInfo info(paintInfo);
1555     info.phase = newPhase;
1556     info.paintingRoot = paintingRootForChildren(paintInfo);
1557     bool isPrinting = document()->printing();
1558
1559     for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
1560         // Check for page-break-before: always, and if it's set, break and bail.
1561         if (isPrinting && !childrenInline() && child->style()->pageBreakBefore() == PBALWAYS &&
1562             inRootBlockContext() && (ty + child->yPos()) > paintInfo.rect.y() &&
1563             (ty + child->yPos()) < paintInfo.rect.bottom()) {
1564             view()->setBestTruncatedAt(ty + child->yPos(), this, true);
1565             return;
1566         }
1567
1568         if (!child->hasLayer() && !child->isFloating())
1569             child->paint(info, tx, ty);
1570
1571         // Check for page-break-after: always, and if it's set, break and bail.
1572         if (isPrinting && !childrenInline() && child->style()->pageBreakAfter() == PBALWAYS &&
1573             inRootBlockContext() && (ty + child->yPos() + child->height()) > paintInfo.rect.y() &&
1574             (ty + child->yPos() + child->height()) < paintInfo.rect.bottom()) {
1575             view()->setBestTruncatedAt(ty + child->yPos() + child->height() + max(0, child->collapsedMarginBottom()), this, true);
1576             return;
1577         }
1578     }
1579 }
1580
1581 void RenderBlock::paintCaret(PaintInfo& paintInfo, CaretType type)
1582 {
1583     SelectionController* selectionController = type == CursorCaret ? document()->frame()->selectionController() : document()->frame()->dragCaretController();
1584     Node* caretNode = selectionController->start().node();
1585     RenderObject* renderer = caretNode ? caretNode->renderer() : 0;
1586     if (!renderer)
1587         return;
1588     // if caretNode is a block and caret is inside it then caret should be painted by that block
1589     bool cursorInsideBlockCaretNode = renderer->isBlockFlow() && selectionController->isInsideNode();
1590     if ((cursorInsideBlockCaretNode ? renderer : renderer->containingBlock()) == this && selectionController->isContentEditable()) {
1591         if (type == CursorCaret)
1592             document()->frame()->paintCaret(paintInfo.context, paintInfo.rect);
1593         else
1594             document()->frame()->paintDragCaret(paintInfo.context, paintInfo.rect);
1595     }
1596 }
1597
1598 void RenderBlock::paintObject(PaintInfo& paintInfo, int tx, int ty)
1599 {
1600     PaintPhase paintPhase = paintInfo.phase;
1601
1602     // If we're a repositioned run-in or a compact, don't paint background/borders.
1603     bool inlineFlow = isInlineFlow();
1604
1605     // 1. paint background, borders etc
1606     if (!inlineFlow &&
1607         (paintPhase == PaintPhaseBlockBackground || paintPhase == PaintPhaseChildBlockBackground) &&
1608         hasBoxDecorations() && style()->visibility() == VISIBLE) {
1609         paintBoxDecorations(paintInfo, tx, ty);
1610     }
1611
1612     if (paintPhase == PaintPhaseMask && style()->visibility() == VISIBLE) {
1613         paintMask(paintInfo, tx, ty);
1614         return;
1615     }
1616
1617     // We're done.  We don't bother painting any children.
1618     if (paintPhase == PaintPhaseBlockBackground)
1619         return;
1620
1621     // Adjust our painting position if we're inside a scrolled layer (e.g., an overflow:auto div).s
1622     int scrolledX = tx;
1623     int scrolledY = ty;
1624     if (hasOverflowClip())
1625         m_layer->subtractScrollOffset(scrolledX, scrolledY);
1626
1627     // 2. paint contents
1628     if (paintPhase != PaintPhaseSelfOutline) {
1629         if (m_hasColumns)
1630             paintColumns(paintInfo, scrolledX, scrolledY);
1631         else
1632             paintContents(paintInfo, scrolledX, scrolledY);
1633     }
1634
1635     // 3. paint selection
1636     // FIXME: Make this work with multi column layouts.  For now don't fill gaps.
1637     bool isPrinting = document()->printing();
1638     if (!inlineFlow && !isPrinting && !m_hasColumns)
1639         paintSelection(paintInfo, scrolledX, scrolledY); // Fill in gaps in selection on lines and between blocks.
1640
1641     // 4. paint floats.
1642     if (!inlineFlow && (paintPhase == PaintPhaseFloat || paintPhase == PaintPhaseSelection || paintPhase == PaintPhaseTextClip)) {
1643         if (m_hasColumns)
1644             paintColumns(paintInfo, scrolledX, scrolledY, true);
1645         else
1646             paintFloats(paintInfo, scrolledX, scrolledY, paintPhase == PaintPhaseSelection || paintPhase == PaintPhaseTextClip);
1647     }
1648
1649     // 5. paint outline.
1650     if (!inlineFlow && (paintPhase == PaintPhaseOutline || paintPhase == PaintPhaseSelfOutline) && hasOutline() && style()->visibility() == VISIBLE)
1651         RenderObject::paintOutline(paintInfo.context, tx, ty, width(), height(), style());
1652
1653     // 6. paint continuation outlines.
1654     if (!inlineFlow && (paintPhase == PaintPhaseOutline || paintPhase == PaintPhaseChildOutlines)) {
1655         if (continuation() && continuation()->hasOutline() && continuation()->style()->visibility() == VISIBLE) {
1656             RenderFlow* inlineFlow = static_cast<RenderFlow*>(continuation()->element()->renderer());
1657             if (!inlineFlow->hasLayer())
1658                 containingBlock()->addContinuationWithOutline(inlineFlow);
1659             else if (!inlineFlow->firstLineBox())
1660                 inlineFlow->paintOutline(paintInfo.context, tx - xPos() + inlineFlow->containingBlock()->xPos(),
1661                                          ty - yPos() + inlineFlow->containingBlock()->yPos());
1662         }
1663         paintContinuationOutlines(paintInfo, tx, ty);
1664     }
1665
1666     // 7. paint caret.
1667     // If the caret's node's render object's containing block is this block, and the paint action is PaintPhaseForeground,
1668     // then paint the caret.
1669     if (!inlineFlow && paintPhase == PaintPhaseForeground) {
1670         paintCaret(paintInfo, CursorCaret);
1671         paintCaret(paintInfo, DragCaret);
1672     }
1673 }
1674
1675 void RenderBlock::paintFloats(PaintInfo& paintInfo, int tx, int ty, bool preservePhase)
1676 {
1677     if (!m_floatingObjects)
1678         return;
1679
1680     FloatingObject* r;
1681     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
1682     for (; (r = it.current()); ++it) {
1683         // Only paint the object if our m_shouldPaint flag is set.
1684         if (r->m_shouldPaint && !r->m_renderer->hasLayer()) {
1685             PaintInfo currentPaintInfo(paintInfo);
1686             currentPaintInfo.phase = preservePhase ? paintInfo.phase : PaintPhaseBlockBackground;
1687             int currentTX = tx + r->m_left - r->m_renderer->xPos() + r->m_renderer->marginLeft();
1688             int currentTY = ty + r->m_top - r->m_renderer->yPos() + r->m_renderer->marginTop();
1689             r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
1690             if (!preservePhase) {
1691                 currentPaintInfo.phase = PaintPhaseChildBlockBackgrounds;
1692                 r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
1693                 currentPaintInfo.phase = PaintPhaseFloat;
1694                 r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
1695                 currentPaintInfo.phase = PaintPhaseForeground;
1696                 r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
1697                 currentPaintInfo.phase = PaintPhaseOutline;
1698                 r->m_renderer->paint(currentPaintInfo, currentTX, currentTY);
1699             }
1700         }
1701     }
1702 }
1703
1704 void RenderBlock::paintEllipsisBoxes(PaintInfo& paintInfo, int tx, int ty)
1705 {
1706     if (!shouldPaintWithinRoot(paintInfo) || !firstLineBox())
1707         return;
1708
1709     if (style()->visibility() == VISIBLE && paintInfo.phase == PaintPhaseForeground) {
1710         // We can check the first box and last box and avoid painting if we don't
1711         // intersect.
1712         int yPos = ty + firstLineBox()->yPos();;
1713         int h = lastLineBox()->yPos() + lastLineBox()->height() - firstLineBox()->yPos();
1714         if (yPos >= paintInfo.rect.bottom() || yPos + h <= paintInfo.rect.y())
1715             return;
1716
1717         // See if our boxes intersect with the dirty rect.  If so, then we paint
1718         // them.  Note that boxes can easily overlap, so we can't make any assumptions
1719         // based off positions of our first line box or our last line box.
1720         for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
1721             yPos = ty + curr->yPos();
1722             h = curr->height();
1723             if (curr->ellipsisBox() && yPos < paintInfo.rect.bottom() && yPos + h > paintInfo.rect.y())
1724                 curr->paintEllipsisBox(paintInfo, tx, ty);
1725         }
1726     }
1727 }
1728
1729 HashMap<RenderBlock*, RenderFlowSequencedSet*>* continuationOutlineTable()
1730 {
1731     static HashMap<RenderBlock*, RenderFlowSequencedSet*> table;
1732     return &table;
1733 }
1734
1735 void RenderBlock::addContinuationWithOutline(RenderFlow* flow)
1736 {
1737     // We can't make this work if the inline is in a layer.  We'll just rely on the broken
1738     // way of painting.
1739     ASSERT(!flow->layer());
1740
1741     HashMap<RenderBlock*, RenderFlowSequencedSet*>* table = continuationOutlineTable();
1742     RenderFlowSequencedSet* continuations = table->get(this);
1743     if (!continuations) {
1744         continuations = new RenderFlowSequencedSet;
1745         table->set(this, continuations);
1746     }
1747
1748     continuations->add(flow);
1749 }
1750
1751 void RenderBlock::paintContinuationOutlines(PaintInfo& info, int tx, int ty)
1752 {
1753     HashMap<RenderBlock*, RenderFlowSequencedSet*>* table = continuationOutlineTable();
1754     if (table->isEmpty())
1755         return;
1756
1757     RenderFlowSequencedSet* continuations = table->get(this);
1758     if (!continuations)
1759         return;
1760
1761     // Paint each continuation outline.
1762     RenderFlowSequencedSet::iterator end = continuations->end();
1763     for (RenderFlowSequencedSet::iterator it = continuations->begin(); it != end; ++it) {
1764         // Need to add in the coordinates of the intervening blocks.
1765         RenderFlow* flow = *it;
1766         RenderBlock* block = flow->containingBlock();
1767         for ( ; block && block != this; block = block->containingBlock()) {
1768             tx += block->xPos();
1769             ty += block->yPos();
1770         }
1771         ASSERT(block);
1772         flow->paintOutline(info.context, tx, ty);
1773     }
1774
1775     // Delete
1776     delete continuations;
1777     table->remove(this);
1778 }
1779
1780 void RenderBlock::setSelectionState(SelectionState s)
1781 {
1782     if (selectionState() == s)
1783         return;
1784
1785     if (s == SelectionInside && selectionState() != SelectionNone)
1786         return;
1787
1788     if ((s == SelectionStart && selectionState() == SelectionEnd) ||
1789         (s == SelectionEnd && selectionState() == SelectionStart))
1790         m_selectionState = SelectionBoth;
1791     else
1792         m_selectionState = s;
1793
1794     RenderBlock* cb = containingBlock();
1795     if (cb && !cb->isRenderView())
1796         cb->setSelectionState(s);
1797 }
1798
1799 bool RenderBlock::shouldPaintSelectionGaps() const
1800 {
1801     return m_selectionState != SelectionNone && style()->visibility() == VISIBLE && isSelectionRoot();
1802 }
1803
1804 bool RenderBlock::isSelectionRoot() const
1805 {
1806     if (!element())
1807         return false;
1808
1809     // FIXME: Eventually tables should have to learn how to fill gaps between cells, at least in simple non-spanning cases.
1810     if (isTable())
1811         return false;
1812
1813     if (isBody() || isRoot() || hasOverflowClip() || isRelPositioned() ||
1814         isFloatingOrPositioned() || isTableCell() || isInlineBlockOrInlineTable() || hasTransform())
1815         return true;
1816
1817     if (view() && view()->selectionStart()) {
1818         Node* startElement = view()->selectionStart()->element();
1819         if (startElement && startElement->rootEditableElement() == element())
1820             return true;
1821     }
1822
1823     return false;
1824 }
1825
1826 GapRects RenderBlock::selectionGapRects()
1827 {
1828     ASSERT(!needsLayout());
1829
1830     if (!shouldPaintSelectionGaps())
1831         return GapRects();
1832
1833     int tx, ty;
1834     absolutePositionForContent(tx, ty);
1835     if (hasOverflowClip())
1836         layer()->subtractScrollOffset(tx, ty);
1837
1838     int lastTop = -borderTopExtra();
1839     int lastLeft = leftSelectionOffset(this, lastTop);
1840     int lastRight = rightSelectionOffset(this, lastTop);
1841
1842     return fillSelectionGaps(this, tx, ty, tx, ty, lastTop, lastLeft, lastRight);
1843 }
1844
1845 void RenderBlock::paintSelection(PaintInfo& paintInfo, int tx, int ty)
1846 {
1847     if (shouldPaintSelectionGaps() && paintInfo.phase == PaintPhaseForeground) {
1848         int lastTop = -borderTopExtra();
1849         int lastLeft = leftSelectionOffset(this, lastTop);
1850         int lastRight = rightSelectionOffset(this, lastTop);
1851         fillSelectionGaps(this, tx, ty, tx, ty, lastTop, lastLeft, lastRight, &paintInfo);
1852     }
1853 }
1854
1855 GapRects RenderBlock::fillSelectionGaps(RenderBlock* rootBlock, int blockX, int blockY, int tx, int ty,
1856                                         int& lastTop, int& lastLeft, int& lastRight, const PaintInfo* paintInfo)
1857 {
1858     // 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
1859     // fixed).
1860     GapRects result;
1861     if (!isBlockFlow()) // FIXME: Make multi-column selection gap filling work someday.
1862         return result;
1863
1864     if (m_hasColumns || hasTransform()) {
1865         // FIXME: We should learn how to gap fill multiple columns and transforms eventually.
1866         lastTop = (ty - blockY) + height();
1867         lastLeft = leftSelectionOffset(rootBlock, height());
1868         lastRight = rightSelectionOffset(rootBlock, height());
1869         return result;
1870     }
1871
1872     if (childrenInline())
1873         result = fillInlineSelectionGaps(rootBlock, blockX, blockY, tx, ty, lastTop, lastLeft, lastRight, paintInfo);
1874     else
1875         result = fillBlockSelectionGaps(rootBlock, blockX, blockY, tx, ty, lastTop, lastLeft, lastRight, paintInfo);
1876
1877     // Go ahead and fill the vertical gap all the way to the bottom of our block if the selection extends past our block.
1878     if (rootBlock == this && (m_selectionState != SelectionBoth && m_selectionState != SelectionEnd))
1879         result.uniteCenter(fillVerticalSelectionGap(lastTop, lastLeft, lastRight, ty + height() + borderBottomExtra(),
1880                                                     rootBlock, blockX, blockY, paintInfo));
1881     return result;
1882 }
1883
1884 GapRects RenderBlock::fillInlineSelectionGaps(RenderBlock* rootBlock, int blockX, int blockY, int tx, int ty,
1885                                               int& lastTop, int& lastLeft, int& lastRight, const PaintInfo* paintInfo)
1886 {
1887     GapRects result;
1888
1889     bool containsStart = selectionState() == SelectionStart || selectionState() == SelectionBoth;
1890
1891     if (!firstLineBox()) {
1892         if (containsStart) {
1893             // Go ahead and update our lastY to be the bottom of the block.  <hr>s or empty blocks with height can trip this
1894             // case.
1895             lastTop = (ty - blockY) + height();
1896             lastLeft = leftSelectionOffset(rootBlock, height());
1897             lastRight = rightSelectionOffset(rootBlock, height());
1898         }
1899         return result;
1900     }
1901
1902     RootInlineBox* lastSelectedLine = 0;
1903     RootInlineBox* curr;
1904     for (curr = firstRootBox(); curr && !curr->hasSelectedChildren(); curr = curr->nextRootBox()) { }
1905
1906     // Now paint the gaps for the lines.
1907     for (; curr && curr->hasSelectedChildren(); curr = curr->nextRootBox()) {
1908         int selTop =  curr->selectionTop();
1909         int selHeight = curr->selectionHeight();
1910
1911         if (!containsStart && !lastSelectedLine &&
1912             selectionState() != SelectionStart && selectionState() != SelectionBoth)
1913             result.uniteCenter(fillVerticalSelectionGap(lastTop, lastLeft, lastRight, ty + selTop,
1914                                                         rootBlock, blockX, blockY, paintInfo));
1915
1916         if (!paintInfo || ty + selTop < paintInfo->rect.bottom() && ty + selTop + selHeight > paintInfo->rect.y())
1917             result.unite(curr->fillLineSelectionGap(selTop, selHeight, rootBlock, blockX, blockY, tx, ty, paintInfo));
1918
1919         lastSelectedLine = curr;
1920     }
1921
1922     if (containsStart && !lastSelectedLine)
1923         // Selection must start just after our last line.
1924         lastSelectedLine = lastRootBox();
1925
1926     if (lastSelectedLine && selectionState() != SelectionEnd && selectionState() != SelectionBoth) {
1927         // Go ahead and update our lastY to be the bottom of the last selected line.
1928         lastTop = (ty - blockY) + lastSelectedLine->bottomOverflow();
1929         lastLeft = leftSelectionOffset(rootBlock, lastSelectedLine->bottomOverflow());
1930         lastRight = rightSelectionOffset(rootBlock, lastSelectedLine->bottomOverflow());
1931     }
1932     return result;
1933 }
1934
1935 GapRects RenderBlock::fillBlockSelectionGaps(RenderBlock* rootBlock, int blockX, int blockY, int tx, int ty,
1936                                              int& lastTop, int& lastLeft, int& lastRight, const PaintInfo* paintInfo)
1937 {
1938     GapRects result;
1939
1940     // Go ahead and jump right to the first block child that contains some selected objects.
1941     RenderObject* curr;
1942     for (curr = firstChild(); curr && curr->selectionState() == SelectionNone; curr = curr->nextSibling()) { }
1943
1944     for (bool sawSelectionEnd = false; curr && !sawSelectionEnd; curr = curr->nextSibling()) {
1945         SelectionState childState = curr->selectionState();
1946         if (childState == SelectionBoth || childState == SelectionEnd)
1947             sawSelectionEnd = true;
1948
1949         if (curr->isFloatingOrPositioned())
1950             continue; // We must be a normal flow object in order to even be considered.
1951
1952         if (curr->isRelPositioned() && curr->hasLayer()) {
1953             // If the relposition offset is anything other than 0, then treat this just like an absolute positioned element.
1954             // Just disregard it completely.
1955             int x = 0;
1956             int y = 0;
1957             curr->layer()->relativePositionOffset(x, y);
1958             if (x || y)
1959                 continue;
1960         }
1961
1962         bool paintsOwnSelection = curr->shouldPaintSelectionGaps() || curr->isTable(); // FIXME: Eventually we won't special-case table like this.
1963         bool fillBlockGaps = paintsOwnSelection || (curr->canBeSelectionLeaf() && childState != SelectionNone);
1964         if (fillBlockGaps) {
1965             // We need to fill the vertical gap above this object.
1966             if (childState == SelectionEnd || childState == SelectionInside)
1967                 // Fill the gap above the object.
1968                 result.uniteCenter(fillVerticalSelectionGap(lastTop, lastLeft, lastRight,
1969                                                             ty + curr->yPos(), rootBlock, blockX, blockY, paintInfo));
1970
1971             // 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*
1972             // our object.  We know this if the selection did not end inside our object.
1973             if (paintsOwnSelection && (childState == SelectionStart || sawSelectionEnd))
1974                 childState = SelectionNone;
1975
1976             // Fill side gaps on this object based off its state.
1977             bool leftGap, rightGap;
1978             getHorizontalSelectionGapInfo(childState, leftGap, rightGap);
1979
1980             if (leftGap)
1981                 result.uniteLeft(fillLeftSelectionGap(this, curr->xPos(), curr->yPos(), curr->height(), rootBlock, blockX, blockY, tx, ty, paintInfo));
1982             if (rightGap)
1983                 result.uniteRight(fillRightSelectionGap(this, curr->xPos() + curr->width(), curr->yPos(), curr->height(), rootBlock, blockX, blockY, tx, ty, paintInfo));
1984
1985             // Update lastTop to be just underneath the object.  lastLeft and lastRight extend as far as
1986             // they can without bumping into floating or positioned objects.  Ideally they will go right up
1987             // to the border of the root selection block.
1988             lastTop = (ty - blockY) + (curr->yPos() + curr->height());
1989             lastLeft = leftSelectionOffset(rootBlock, curr->yPos() + curr->height());
1990             lastRight = rightSelectionOffset(rootBlock, curr->yPos() + curr->height());
1991         } else if (childState != SelectionNone)
1992             // We must be a block that has some selected object inside it.  Go ahead and recur.
1993             result.unite(static_cast<RenderBlock*>(curr)->fillSelectionGaps(rootBlock, blockX, blockY, tx + curr->xPos(), ty + curr->yPos(),
1994                                                                             lastTop, lastLeft, lastRight, paintInfo));
1995     }
1996     return result;
1997 }
1998
1999 IntRect RenderBlock::fillHorizontalSelectionGap(RenderObject* selObj, int xPos, int yPos, int width, int height, const PaintInfo* paintInfo)
2000 {
2001     if (width <= 0 || height <= 0)
2002         return IntRect();
2003     IntRect gapRect(xPos, yPos, width, height);
2004     if (paintInfo && selObj->style()->visibility() == VISIBLE)
2005         paintInfo->context->fillRect(gapRect, selObj->selectionBackgroundColor());
2006     return gapRect;
2007 }
2008
2009 IntRect RenderBlock::fillVerticalSelectionGap(int lastTop, int lastLeft, int lastRight, int bottomY, RenderBlock* rootBlock,
2010                                               int blockX, int blockY, const PaintInfo* paintInfo)
2011 {
2012     int top = blockY + lastTop;
2013     int height = bottomY - top;
2014     if (height <= 0)
2015         return IntRect();
2016
2017     // Get the selection offsets for the bottom of the gap
2018     int left = blockX + max(lastLeft, leftSelectionOffset(rootBlock, bottomY));
2019     int right = blockX + min(lastRight, rightSelectionOffset(rootBlock, bottomY));
2020     int width = right - left;
2021     if (width <= 0)
2022         return IntRect();
2023
2024     IntRect gapRect(left, top, width, height);
2025     if (paintInfo)
2026         paintInfo->context->fillRect(gapRect, selectionBackgroundColor());
2027     return gapRect;
2028 }
2029
2030 IntRect RenderBlock::fillLeftSelectionGap(RenderObject* selObj, int xPos, int yPos, int height, RenderBlock* rootBlock,
2031                                           int blockX, int blockY, int tx, int ty, const PaintInfo* paintInfo)
2032 {
2033     int top = yPos + ty;
2034     int left = blockX + max(leftSelectionOffset(rootBlock, yPos), leftSelectionOffset(rootBlock, yPos + height));
2035     int width = tx + xPos - left;
2036     if (width <= 0)
2037         return IntRect();
2038
2039     IntRect gapRect(left, top, width, height);
2040     if (paintInfo)
2041         paintInfo->context->fillRect(gapRect, selObj->selectionBackgroundColor());
2042     return gapRect;
2043 }
2044
2045 IntRect RenderBlock::fillRightSelectionGap(RenderObject* selObj, int xPos, int yPos, int height, RenderBlock* rootBlock,
2046                                            int blockX, int blockY, int tx, int ty, const PaintInfo* paintInfo)
2047 {
2048     int left = xPos + tx;
2049     int top = yPos + ty;
2050     int right = blockX + min(rightSelectionOffset(rootBlock, yPos), rightSelectionOffset(rootBlock, yPos + height));
2051     int width = right - left;
2052     if (width <= 0)
2053         return IntRect();
2054
2055     IntRect gapRect(left, top, width, height);
2056     if (paintInfo)
2057         paintInfo->context->fillRect(gapRect, selObj->selectionBackgroundColor());
2058     return gapRect;
2059 }
2060
2061 void RenderBlock::getHorizontalSelectionGapInfo(SelectionState state, bool& leftGap, bool& rightGap)
2062 {
2063     bool ltr = style()->direction() == LTR;
2064     leftGap = (state == RenderObject::SelectionInside) ||
2065               (state == RenderObject::SelectionEnd && ltr) ||
2066               (state == RenderObject::SelectionStart && !ltr);
2067     rightGap = (state == RenderObject::SelectionInside) ||
2068                (state == RenderObject::SelectionStart && ltr) ||
2069                (state == RenderObject::SelectionEnd && !ltr);
2070 }
2071
2072 int RenderBlock::leftSelectionOffset(RenderBlock* rootBlock, int y)
2073 {
2074     int left = leftOffset(y);
2075     if (left == borderLeft() + paddingLeft()) {
2076         if (rootBlock != this)
2077             // The border can potentially be further extended by our containingBlock().
2078             return containingBlock()->leftSelectionOffset(rootBlock, y + yPos());
2079         return left;
2080     }
2081     else {
2082         RenderBlock* cb = this;
2083         while (cb != rootBlock) {
2084             left += cb->xPos();
2085             cb = cb->containingBlock();
2086         }
2087     }
2088
2089     return left;
2090 }
2091
2092 int RenderBlock::rightSelectionOffset(RenderBlock* rootBlock, int y)
2093 {
2094     int right = rightOffset(y);
2095     if (right == (contentWidth() + (borderLeft() + paddingLeft()))) {
2096         if (rootBlock != this)
2097             // The border can potentially be further extended by our containingBlock().
2098             return containingBlock()->rightSelectionOffset(rootBlock, y + yPos());
2099         return right;
2100     }
2101     else {
2102         RenderBlock* cb = this;
2103         while (cb != rootBlock) {
2104             right += cb->xPos();
2105             cb = cb->containingBlock();
2106         }
2107     }
2108     return right;
2109 }
2110
2111 void RenderBlock::insertPositionedObject(RenderObject *o)
2112 {
2113     // Create the list of special objects if we don't aleady have one
2114     if (!m_positionedObjects)
2115         m_positionedObjects = new ListHashSet<RenderObject*>;
2116
2117     m_positionedObjects->add(o);
2118 }
2119
2120 void RenderBlock::removePositionedObject(RenderObject *o)
2121 {
2122     if (m_positionedObjects)
2123         m_positionedObjects->remove(o);
2124 }
2125
2126 void RenderBlock::removePositionedObjects(RenderBlock* o)
2127 {
2128     if (!m_positionedObjects)
2129         return;
2130
2131     RenderObject* r;
2132
2133     Iterator end = m_positionedObjects->end();
2134
2135     Vector<RenderObject*, 16> deadObjects;
2136
2137     for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
2138         r = *it;
2139         if (!o || r->isDescendantOf(o)) {
2140             if (o)
2141                 r->setChildNeedsLayout(true, false);
2142
2143             // It is parent blocks job to add positioned child to positioned objects list of its containing block
2144             // Parent layout needs to be invalidated to ensure this happens.
2145             RenderObject* p = r->parent();
2146             while (p && !p->isRenderBlock())
2147                 p = p->parent();
2148             if (p)
2149                 p->setChildNeedsLayout(true);
2150
2151             deadObjects.append(r);
2152         }
2153     }
2154
2155     for (unsigned i = 0; i < deadObjects.size(); i++)
2156         m_positionedObjects->remove(deadObjects.at(i));
2157 }
2158
2159 void RenderBlock::insertFloatingObject(RenderObject *o)
2160 {
2161     ASSERT(o->isFloating());
2162
2163     // Create the list of special objects if we don't aleady have one
2164     if (!m_floatingObjects) {
2165         m_floatingObjects = new DeprecatedPtrList<FloatingObject>;
2166         m_floatingObjects->setAutoDelete(true);
2167     } else {
2168         // Don't insert the object again if it's already in the list
2169         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2170         FloatingObject* f;
2171         while ( (f = it.current()) ) {
2172             if (f->m_renderer == o) return;
2173             ++it;
2174         }
2175     }
2176
2177     // Create the special object entry & append it to the list
2178
2179     o->layoutIfNeeded();
2180
2181     FloatingObject* newObj = new FloatingObject(o->style()->floating() == FLEFT ? FloatingObject::FloatLeft : FloatingObject::FloatRight);
2182
2183     newObj->m_top = -1;
2184     newObj->m_bottom = -1;
2185     newObj->m_width = o->width() + o->marginLeft() + o->marginRight();
2186     newObj->m_shouldPaint = !o->hasLayer(); // If a layer exists, the float will paint itself.  Otherwise someone else will.
2187     newObj->m_isDescendant = true;
2188     newObj->m_renderer = o;
2189
2190     m_floatingObjects->append(newObj);
2191 }
2192
2193 void RenderBlock::removeFloatingObject(RenderObject *o)
2194 {
2195     if (m_floatingObjects) {
2196         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2197         while (it.current()) {
2198             if (it.current()->m_renderer == o) {
2199                 if (childrenInline())
2200                     markLinesDirtyInVerticalRange(0, it.current()->m_bottom);
2201                 m_floatingObjects->removeRef(it.current());
2202             }
2203             ++it;
2204         }
2205     }
2206 }
2207
2208 bool RenderBlock::positionNewFloats()
2209 {
2210     if (!m_floatingObjects)
2211         return false;
2212
2213     FloatingObject* f = m_floatingObjects->last();
2214
2215     // If all floats have already been positioned, then we have no work to do.
2216     if (!f || f->m_top != -1)
2217         return false;
2218
2219     // Move backwards through our floating object list until we find a float that has
2220     // already been positioned.  Then we'll be able to move forward, positioning all of
2221     // the new floats that need it.
2222     FloatingObject* lastFloat = m_floatingObjects->getPrev();
2223     while (lastFloat && lastFloat->m_top == -1) {
2224         f = m_floatingObjects->prev();
2225         lastFloat = m_floatingObjects->getPrev();
2226     }
2227
2228     int y = m_height;
2229
2230     // The float cannot start above the y position of the last positioned float.
2231     if (lastFloat)
2232         y = max(lastFloat->m_top, y);
2233
2234     // Now walk through the set of unpositioned floats and place them.
2235     while (f) {
2236         // The containing block is responsible for positioning floats, so if we have floats in our
2237         // list that come from somewhere else, do not attempt to position them.
2238         if (f->m_renderer->containingBlock() != this) {
2239             f = m_floatingObjects->next();
2240             continue;
2241         }
2242
2243         RenderObject* o = f->m_renderer;
2244         int _height = o->height() + o->marginTop() + o->marginBottom();
2245
2246         int ro = rightOffset(); // Constant part of right offset.
2247         int lo = leftOffset(); // Constat part of left offset.
2248         int fwidth = f->m_width; // The width we look for.
2249         if (ro - lo < fwidth)
2250             fwidth = ro - lo; // Never look for more than what will be available.
2251
2252         IntRect oldRect(o->xPos(), o->yPos() , o->width(), o->height());
2253
2254         if (o->style()->clear() & CLEFT)
2255             y = max(leftBottom(), y);
2256         if (o->style()->clear() & CRIGHT)
2257             y = max(rightBottom(), y);
2258
2259         if (o->style()->floating() == FLEFT) {
2260             int heightRemainingLeft = 1;
2261             int heightRemainingRight = 1;
2262             int fx = leftRelOffset(y,lo, false, &heightRemainingLeft);
2263             while (rightRelOffset(y,ro, false, &heightRemainingRight)-fx < fwidth) {
2264                 y += min(heightRemainingLeft, heightRemainingRight);
2265                 fx = leftRelOffset(y,lo, false, &heightRemainingLeft);
2266             }
2267             fx = max(0, fx);
2268             f->m_left = fx;
2269             o->setPos(fx + o->marginLeft(), y + o->marginTop());
2270         } else {
2271             int heightRemainingLeft = 1;
2272             int heightRemainingRight = 1;
2273             int fx = rightRelOffset(y,ro, false, &heightRemainingRight);
2274             while (fx - leftRelOffset(y,lo, false, &heightRemainingLeft) < fwidth) {
2275                 y += min(heightRemainingLeft, heightRemainingRight);
2276                 fx = rightRelOffset(y, ro, false, &heightRemainingRight);
2277             }
2278             fx = max(f->m_width, fx);
2279             f->m_left = fx - f->m_width;
2280             o->setPos(fx - o->marginRight() - o->width(), y + o->marginTop());
2281         }
2282
2283         f->m_top = y;
2284         f->m_bottom = f->m_top + _height;
2285
2286         // If the child moved, we have to repaint it.
2287         if (o->checkForRepaintDuringLayout())
2288             o->repaintDuringLayoutIfMoved(oldRect);
2289
2290         f = m_floatingObjects->next();
2291     }
2292     return true;
2293 }
2294
2295 void RenderBlock::newLine(EClear clear)
2296 {
2297     positionNewFloats();
2298     // set y position
2299     int newY = 0;
2300     switch(clear)
2301     {
2302         case CLEFT:
2303             newY = leftBottom();
2304             break;
2305         case CRIGHT:
2306             newY = rightBottom();
2307             break;
2308         case CBOTH:
2309             newY = floatBottom();
2310         default:
2311             break;
2312     }
2313     if (m_height < newY)
2314         m_height = newY;
2315 }
2316
2317 int
2318 RenderBlock::leftOffset() const
2319 {
2320     return borderLeft()+paddingLeft();
2321 }
2322
2323 int
2324 RenderBlock::leftRelOffset(int y, int fixedOffset, bool applyTextIndent,
2325                            int *heightRemaining ) const
2326 {
2327     int left = fixedOffset;
2328     if (m_floatingObjects) {
2329         if ( heightRemaining ) *heightRemaining = 1;
2330         FloatingObject* r;
2331         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2332         for ( ; (r = it.current()); ++it )
2333         {
2334             if (r->m_top <= y && r->m_bottom > y &&
2335                 r->type() == FloatingObject::FloatLeft &&
2336                 r->m_left + r->m_width > left) {
2337                 left = r->m_left + r->m_width;
2338                 if ( heightRemaining ) *heightRemaining = r->m_bottom - y;
2339             }
2340         }
2341     }
2342
2343     if (applyTextIndent && m_firstLine && style()->direction() == LTR) {
2344         int cw=0;
2345         if (style()->textIndent().isPercent())
2346             cw = containingBlock()->availableWidth();
2347         left += style()->textIndent().calcMinValue(cw);
2348     }
2349
2350     //kdDebug( 6040 ) << "leftOffset(" << y << ") = " << left << endl;
2351     return left;
2352 }
2353
2354 int
2355 RenderBlock::rightOffset() const
2356 {
2357     return borderLeft() + paddingLeft() + availableWidth();
2358 }
2359
2360 int
2361 RenderBlock::rightRelOffset(int y, int fixedOffset, bool applyTextIndent,
2362                             int *heightRemaining ) const
2363 {
2364     int right = fixedOffset;
2365
2366     if (m_floatingObjects) {
2367         if (heightRemaining) *heightRemaining = 1;
2368         FloatingObject* r;
2369         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2370         for ( ; (r = it.current()); ++it )
2371         {
2372             if (r->m_top <= y && r->m_bottom > y &&
2373                 r->type() == FloatingObject::FloatRight &&
2374                 r->m_left < right) {
2375                 right = r->m_left;
2376                 if ( heightRemaining ) *heightRemaining = r->m_bottom - y;
2377             }
2378         }
2379     }
2380
2381     if (applyTextIndent && m_firstLine && style()->direction() == RTL) {
2382         int cw=0;
2383         if (style()->textIndent().isPercent())
2384             cw = containingBlock()->availableWidth();
2385         right -= style()->textIndent().calcMinValue(cw);
2386     }
2387
2388     //kdDebug( 6040 ) << "rightOffset(" << y << ") = " << right << endl;
2389     return right;
2390 }
2391
2392 int
2393 RenderBlock::lineWidth(int y) const
2394 {
2395     //kdDebug( 6040 ) << "lineWidth(" << y << ")=" << rightOffset(y) - leftOffset(y) << endl;
2396     int result = rightOffset(y) - leftOffset(y);
2397     return (result < 0) ? 0 : result;
2398 }
2399
2400 int RenderBlock::nextFloatBottomBelow(int height) const
2401 {
2402     if (!m_floatingObjects)
2403         return 0;
2404
2405     int bottom = INT_MAX;
2406     FloatingObject* r;
2407     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2408     for ( ; (r = it.current()); ++it) {
2409         if (r->m_bottom > height)
2410             bottom = min(r->m_bottom, bottom);
2411     }
2412
2413     return bottom == INT_MAX ? 0 : bottom;
2414 }
2415
2416 int
2417 RenderBlock::floatBottom() const
2418 {
2419     if (!m_floatingObjects) return 0;
2420     int bottom=0;
2421     FloatingObject* r;
2422     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2423     for ( ; (r = it.current()); ++it )
2424         if (r->m_bottom>bottom)
2425             bottom=r->m_bottom;
2426     return bottom;
2427 }
2428
2429 IntRect RenderBlock::floatRect() const
2430 {
2431     IntRect result;
2432     if (!m_floatingObjects || hasOverflowClip())
2433         return result;
2434     FloatingObject* r;
2435     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2436     for (; (r = it.current()); ++it) {
2437         if (r->m_shouldPaint && !r->m_renderer->hasLayer()) {
2438             IntRect childRect = r->m_renderer->overflowRect(false);
2439             childRect.move(r->m_left + r->m_renderer->marginLeft(), r->m_top + r->m_renderer->marginTop());
2440             result.unite(childRect);
2441         }
2442     }
2443
2444     return result;
2445 }
2446
2447 int RenderBlock::lowestPosition(bool includeOverflowInterior, bool includeSelf) const
2448 {
2449     int bottom = RenderFlow::lowestPosition(includeOverflowInterior, includeSelf);
2450     if (!includeOverflowInterior && hasOverflowClip())
2451         return bottom;
2452
2453     if (includeSelf && m_overflowHeight > bottom)
2454         bottom = m_overflowHeight;
2455
2456     if (m_positionedObjects) {
2457         RenderObject* r;
2458         Iterator end = m_positionedObjects->end();
2459         for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
2460             r = *it;
2461             // Fixed positioned objects do not scroll and thus should not constitute
2462             // part of the lowest position.
2463             if (r->style()->position() != FixedPosition) {
2464                 // FIXME: Should work for overflow sections too.
2465                 // If a positioned object lies completely to the left of the root it will be unreachable via scrolling.
2466                 // Therefore we should not allow it to contribute to the lowest position.
2467                 if (!isRenderView() || r->xPos() + r->width() > 0 || r->xPos() + r->rightmostPosition(false) > 0) {
2468                     int lp = r->yPos() + r->lowestPosition(false);
2469                     bottom = max(bottom, lp);
2470                 }
2471             }
2472         }
2473     }
2474
2475     if (m_hasColumns) {
2476         Vector<IntRect>* colRects = columnRects();
2477         for (unsigned i = 0; i < colRects->size(); i++)
2478             bottom = max(bottom, colRects->at(i).bottom());
2479         return bottom;
2480     }
2481
2482     if (m_floatingObjects) {
2483         FloatingObject* r;
2484         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2485         for ( ; (r = it.current()); ++it ) {
2486             if (r->m_shouldPaint || r->m_renderer->hasLayer()) {
2487                 int lp = r->m_top + r->m_renderer->marginTop() + r->m_renderer->lowestPosition(false);
2488                 bottom = max(bottom, lp);
2489             }
2490         }
2491     }
2492
2493
2494     if (!includeSelf && lastLineBox()) {
2495         int lp = lastLineBox()->yPos() + lastLineBox()->height();
2496         bottom = max(bottom, lp);
2497     }
2498
2499     return bottom;
2500 }
2501
2502 int RenderBlock::rightmostPosition(bool includeOverflowInterior, bool includeSelf) const
2503 {
2504     int right = RenderFlow::rightmostPosition(includeOverflowInterior, includeSelf);
2505     if (!includeOverflowInterior && hasOverflowClip())
2506         return right;
2507
2508     if (includeSelf && m_overflowWidth > right)
2509         right = m_overflowWidth;
2510
2511     if (m_positionedObjects) {
2512         RenderObject* r;
2513         Iterator end = m_positionedObjects->end();
2514         for (Iterator it = m_positionedObjects->begin() ; it != end; ++it) {
2515             r = *it;
2516             // Fixed positioned objects do not scroll and thus should not constitute
2517             // part of the rightmost position.
2518             if (r->style()->position() != FixedPosition) {
2519                 // FIXME: Should work for overflow sections too.
2520                 // If a positioned object lies completely above the root it will be unreachable via scrolling.
2521                 // Therefore we should not allow it to contribute to the rightmost position.
2522                 if (!isRenderView() || r->yPos() + r->height() > 0 || r->yPos() + r->lowestPosition(false) > 0) {
2523                     int rp = r->xPos() + r->rightmostPosition(false);
2524                     right = max(right, rp);
2525                 }
2526             }
2527         }
2528     }
2529
2530     if (m_hasColumns) {
2531         // This only matters for LTR
2532         if (style()->direction() == LTR)
2533             right = max(columnRects()->last().right(), right);
2534         return right;
2535     }
2536
2537     if (m_floatingObjects) {
2538         FloatingObject* r;
2539         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2540         for ( ; (r = it.current()); ++it ) {
2541             if (r->m_shouldPaint || r->m_renderer->hasLayer()) {
2542                 int rp = r->m_left + r->m_renderer->marginLeft() + r->m_renderer->rightmostPosition(false);
2543                 right = max(right, rp);
2544             }
2545         }
2546     }
2547
2548     if (!includeSelf && firstLineBox()) {
2549         for (InlineRunBox* currBox = firstLineBox(); currBox; currBox = currBox->nextLineBox()) {
2550             int rp = currBox->xPos() + currBox->width();
2551             // If this node is a root editable element, then the rightmostPosition should account for a caret at the end.
2552             // FIXME: Need to find another way to do this, since scrollbars could show when we don't want them to.
2553             if (node()->isContentEditable() && node() == node()->rootEditableElement() && style()->direction() == LTR)
2554                 rp += 1;
2555             right = max(right, rp);
2556         }
2557     }
2558
2559     return right;
2560 }
2561
2562 int RenderBlock::leftmostPosition(bool includeOverflowInterior, bool includeSelf) const
2563 {
2564     int left = RenderFlow::leftmostPosition(includeOverflowInterior, includeSelf);
2565     if (!includeOverflowInterior && hasOverflowClip())
2566         return left;
2567
2568     if (includeSelf && m_overflowLeft < left)
2569         left = m_overflowLeft;
2570
2571     if (m_positionedObjects) {
2572         RenderObject* r;
2573         Iterator end = m_positionedObjects->end();
2574         for (Iterator it = m_positionedObjects->begin(); it != end; ++it) {
2575             r = *it;
2576             // Fixed positioned objects do not scroll and thus should not constitute
2577             // part of the leftmost position.
2578             if (r->style()->position() != FixedPosition) {
2579                 // FIXME: Should work for overflow sections too.
2580                 // If a positioned object lies completely above the root it will be unreachable via scrolling.
2581                 // Therefore we should not allow it to contribute to the leftmost position.
2582                 if (!isRenderView() || r->yPos() + r->height() > 0 || r->yPos() + r->lowestPosition(false) > 0) {
2583                     int lp = r->xPos() + r->leftmostPosition(false);
2584                     left = min(left, lp);
2585                 }
2586             }
2587         }
2588     }
2589
2590     if (m_hasColumns) {
2591         // This only matters for RTL
2592         if (style()->direction() == RTL)
2593             left = min(columnRects()->last().x(), left);
2594         return left;
2595     }
2596
2597     if (m_floatingObjects) {
2598         FloatingObject* r;
2599         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2600         for ( ; (r = it.current()); ++it ) {
2601             if (r->m_shouldPaint || r->m_renderer->hasLayer()) {
2602                 int lp = r->m_left + r->m_renderer->marginLeft() + r->m_renderer->leftmostPosition(false);
2603                 left = min(left, lp);
2604             }
2605         }
2606     }
2607
2608     if (!includeSelf && firstLineBox()) {
2609         for (InlineRunBox* currBox = firstLineBox(); currBox; currBox = currBox->nextLineBox())
2610             left = min(left, (int)currBox->xPos());
2611     }
2612
2613     return left;
2614 }
2615
2616 int
2617 RenderBlock::leftBottom()
2618 {
2619     if (!m_floatingObjects) return 0;
2620     int bottom=0;
2621     FloatingObject* r;
2622     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2623     for ( ; (r = it.current()); ++it )
2624         if (r->m_bottom > bottom && r->type() == FloatingObject::FloatLeft)
2625             bottom=r->m_bottom;
2626
2627     return bottom;
2628 }
2629
2630 int
2631 RenderBlock::rightBottom()
2632 {
2633     if (!m_floatingObjects) return 0;
2634     int bottom=0;
2635     FloatingObject* r;
2636     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2637     for ( ; (r = it.current()); ++it )
2638         if (r->m_bottom>bottom && r->type() == FloatingObject::FloatRight)
2639             bottom=r->m_bottom;
2640
2641     return bottom;
2642 }
2643
2644 void RenderBlock::markLinesDirtyInVerticalRange(int top, int bottom)
2645 {
2646     if (top >= bottom)
2647         return;
2648
2649     RootInlineBox* lowestDirtyLine = lastRootBox();
2650     RootInlineBox* afterLowest = lowestDirtyLine;
2651     while (lowestDirtyLine && lowestDirtyLine->blockHeight() >= bottom) {
2652         afterLowest = lowestDirtyLine;
2653         lowestDirtyLine = lowestDirtyLine->prevRootBox();
2654     }
2655
2656     while (afterLowest && afterLowest->blockHeight() >= top) {
2657         afterLowest->markDirty();
2658         afterLowest = afterLowest->prevRootBox();
2659     }
2660 }
2661
2662 void RenderBlock::clearFloats()
2663 {
2664     // Inline blocks are covered by the isReplaced() check in the avoidFloats method.
2665     if (avoidsFloats() || isRoot() || isRenderView() || isFloatingOrPositioned() || isTableCell()) {
2666         if (m_floatingObjects)
2667             m_floatingObjects->clear();
2668         return;
2669     }
2670
2671     typedef HashMap<RenderObject*, FloatingObject*> RendererToFloatInfoMap;
2672     RendererToFloatInfoMap floatMap;
2673
2674     if (m_floatingObjects) {
2675         if (childrenInline()) {
2676             m_floatingObjects->first();
2677             while (FloatingObject* f = m_floatingObjects->take())
2678                 floatMap.add(f->m_renderer, f);
2679         } else
2680             m_floatingObjects->clear();
2681     }
2682
2683     // Attempt to locate a previous sibling with overhanging floats.  We skip any elements that are
2684     // out of flow (like floating/positioned elements), and we also skip over any objects that may have shifted
2685     // to avoid floats.
2686     bool parentHasFloats = false;
2687     RenderObject *prev = previousSibling();
2688     while (prev && (!prev->isRenderBlock() || prev->avoidsFloats() || prev->isFloatingOrPositioned())) {
2689         if (prev->isFloating())
2690             parentHasFloats = true;
2691          prev = prev->previousSibling();
2692     }
2693
2694     // First add in floats from the parent.
2695     int offset = m_y;
2696     if (parentHasFloats)
2697         addIntrudingFloats(static_cast<RenderBlock *>(parent()),
2698                            parent()->borderLeft() + parent()->paddingLeft(), offset);
2699
2700     int xoffset = 0;
2701     if (prev)
2702         offset -= prev->yPos();
2703     else {
2704         prev = parent();
2705         xoffset += prev->borderLeft() + prev->paddingLeft();
2706     }
2707
2708     // Add overhanging floats from the previous RenderBlock, but only if it has a float that intrudes into our space.
2709     if (!prev->isRenderBlock()) return;
2710     RenderBlock* block = static_cast<RenderBlock *>(prev);
2711
2712     if (block->m_floatingObjects && block->floatBottom() > offset)
2713         addIntrudingFloats(block, xoffset, offset);
2714
2715     if (childrenInline()) {
2716         int changeTop = INT_MAX;
2717         int changeBottom = INT_MIN;
2718         if (m_floatingObjects) {
2719             for (FloatingObject* f = m_floatingObjects->first(); f; f = m_floatingObjects->next()) {
2720                 FloatingObject* oldFloatingObject = floatMap.get(f->m_renderer);
2721                 if (oldFloatingObject) {
2722                     if (f->m_width != oldFloatingObject->m_width || f->m_left != oldFloatingObject->m_left) {
2723                         changeTop = 0;
2724                         changeBottom = max(changeBottom, max(f->m_bottom, oldFloatingObject->m_bottom));
2725                     } else if (f->m_bottom != oldFloatingObject->m_bottom) {
2726                         changeTop = min(changeTop, min(f->m_bottom, oldFloatingObject->m_bottom));
2727                         changeBottom = max(changeBottom, max(f->m_bottom, oldFloatingObject->m_bottom));
2728                     }
2729
2730                     floatMap.remove(f->m_renderer);
2731                     delete oldFloatingObject;
2732                 } else {
2733                     changeTop = 0;
2734                     changeBottom = max(changeBottom, f->m_bottom);
2735                 }
2736             }
2737         }
2738
2739         RendererToFloatInfoMap::iterator end = floatMap.end();
2740         for (RendererToFloatInfoMap::iterator it = floatMap.begin(); it != end; ++it) {
2741             FloatingObject* floatingObject = (*it).second;
2742             if (!floatingObject->m_isDescendant) {
2743                 changeTop = 0;
2744                 changeBottom = max(changeBottom, floatingObject->m_bottom);
2745             }
2746         }
2747         deleteAllValues(floatMap);
2748
2749         markLinesDirtyInVerticalRange(changeTop, changeBottom);
2750     }
2751 }
2752
2753 int RenderBlock::addOverhangingFloats(RenderBlock* child, int xoff, int yoff, bool makeChildPaintOtherFloats)
2754 {
2755     // Prevent floats from being added to the canvas by the root element, e.g., <html>.
2756     if (child->hasOverflowClip() || !child->containsFloats() || child->isRoot())
2757         return 0;
2758
2759     int lowestFloatBottom = 0;
2760
2761     // Floats that will remain the child's responsiblity to paint should factor into its
2762     // visual overflow.
2763     IntRect floatsOverflowRect;
2764     DeprecatedPtrListIterator<FloatingObject> it(*child->m_floatingObjects);
2765     for (FloatingObject* r; (r = it.current()); ++it) {
2766         int bottom = child->yPos() + r->m_bottom;
2767         lowestFloatBottom = max(lowestFloatBottom, bottom);
2768
2769         if (bottom > height()) {
2770             // If the object is not in the list, we add it now.
2771             if (!containsFloat(r->m_renderer)) {
2772                 FloatingObject *floatingObj = new FloatingObject(r->type());
2773                 floatingObj->m_top = r->m_top - yoff;
2774                 floatingObj->m_bottom = r->m_bottom - yoff;
2775                 floatingObj->m_left = r->m_left - xoff;
2776                 floatingObj->m_width = r->m_width;
2777                 floatingObj->m_renderer = r->m_renderer;
2778
2779                 // The nearest enclosing layer always paints the float (so that zindex and stacking
2780                 // behaves properly).  We always want to propagate the desire to paint the float as
2781                 // far out as we can, to the outermost block that overlaps the float, stopping only
2782                 // if we hit a layer boundary.
2783                 if (r->m_renderer->enclosingLayer() == enclosingLayer())
2784                     r->m_shouldPaint = false;
2785                 else
2786                     floatingObj->m_shouldPaint = false;
2787
2788                 // We create the floating object list lazily.
2789                 if (!m_floatingObjects) {
2790                     m_floatingObjects = new DeprecatedPtrList<FloatingObject>;
2791                     m_floatingObjects->setAutoDelete(true);
2792                 }
2793                 m_floatingObjects->append(floatingObj);
2794             }
2795         } else if (makeChildPaintOtherFloats && !r->m_shouldPaint && !r->m_renderer->hasLayer() && r->m_renderer->isDescendantOf(child) && r->m_renderer->enclosingLayer() == child->enclosingLayer())
2796             // The float is not overhanging from this block, so if it is a descendant of the child, the child should
2797             // paint it (the other case is that it is intruding into the child), unless it has its own layer or enclosing
2798             // layer.
2799             // If makeChildPaintOtherFloats is false, it means that the child must already know about all the floats
2800             // it should paint.
2801             r->m_shouldPaint = true;
2802
2803         if (r->m_shouldPaint && !r->m_renderer->hasLayer()) {
2804             IntRect floatOverflowRect = r->m_renderer->overflowRect(false);
2805             floatOverflowRect.move(r->m_left + r->m_renderer->marginLeft(), r->m_top + r->m_renderer->marginTop());
2806             floatsOverflowRect.unite(floatOverflowRect);
2807         }
2808     }
2809     child->addVisualOverflow(floatsOverflowRect);
2810     return lowestFloatBottom;
2811 }
2812
2813 void RenderBlock::addIntrudingFloats(RenderBlock* prev, int xoff, int yoff)
2814 {
2815     // If the parent or previous sibling doesn't have any floats to add, don't bother.
2816     if (!prev->m_floatingObjects)
2817         return;
2818
2819     DeprecatedPtrListIterator<FloatingObject> it(*prev->m_floatingObjects);
2820     for (FloatingObject *r; (r = it.current()); ++it) {
2821         if (r->m_bottom > yoff) {
2822             // The object may already be in our list. Check for it up front to avoid
2823             // creating duplicate entries.
2824             FloatingObject* f = 0;
2825             if (m_floatingObjects) {
2826                 DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2827                 while ((f = it.current())) {
2828                     if (f->m_renderer == r->m_renderer) break;
2829                     ++it;
2830                 }
2831             }
2832             if (!f) {
2833                 FloatingObject *floatingObj = new FloatingObject(r->type());
2834                 floatingObj->m_top = r->m_top - yoff;
2835                 floatingObj->m_bottom = r->m_bottom - yoff;
2836                 floatingObj->m_left = r->m_left - xoff;
2837                 // Applying the child's margin makes no sense in the case where the child was passed in.
2838                 // since his own margin was added already through the subtraction of the |xoff| variable
2839                 // above.  |xoff| will equal -flow->marginLeft() in this case, so it's already been taken
2840                 // into account.  Only apply this code if |child| is false, since otherwise the left margin
2841                 // will get applied twice.
2842                 if (prev != parent())
2843                     floatingObj->m_left += prev->marginLeft();
2844                 floatingObj->m_left -= marginLeft();
2845                 floatingObj->m_shouldPaint = false;  // We are not in the direct inheritance chain for this float. We will never paint it.
2846                 floatingObj->m_width = r->m_width;
2847                 floatingObj->m_renderer = r->m_renderer;
2848
2849                 // We create the floating object list lazily.
2850                 if (!m_floatingObjects) {
2851                     m_floatingObjects = new DeprecatedPtrList<FloatingObject>;
2852                     m_floatingObjects->setAutoDelete(true);
2853                 }
2854                 m_floatingObjects->append(floatingObj);
2855             }
2856         }
2857     }
2858 }
2859
2860 bool RenderBlock::avoidsFloats() const
2861 {
2862     // Floats can't intrude into our box if we have a non-auto column count or width.
2863     return RenderFlow::avoidsFloats() || !style()->hasAutoColumnCount() || !style()->hasAutoColumnWidth();
2864 }
2865
2866 bool RenderBlock::containsFloat(RenderObject* o)
2867 {
2868     if (m_floatingObjects) {
2869         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2870         while (it.current()) {
2871             if (it.current()->m_renderer == o)
2872                 return true;
2873             ++it;
2874         }
2875     }
2876     return false;
2877 }
2878
2879 void RenderBlock::markAllDescendantsWithFloatsForLayout(RenderObject* floatToRemove)
2880 {
2881     setChildNeedsLayout(true);
2882
2883     if (floatToRemove)
2884         removeFloatingObject(floatToRemove);
2885
2886     // Iterate over our children and mark them as needed.
2887     if (!childrenInline()) {
2888         for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
2889             if (isBlockFlow() && !child->isFloatingOrPositioned() &&
2890                 ((floatToRemove ? child->containsFloat(floatToRemove) : child->containsFloats()) || child->shrinkToAvoidFloats()))
2891                 child->markAllDescendantsWithFloatsForLayout(floatToRemove);
2892         }
2893     }
2894 }
2895
2896 int RenderBlock::getClearDelta(RenderObject *child)
2897 {
2898     // There is no need to compute clearance if we have no floats.
2899     if (!containsFloats())
2900         return 0;
2901
2902     // At least one float is present.  We need to perform the clearance computation.
2903     bool clearSet = child->style()->clear() != CNONE;
2904     int bottom = 0;
2905     switch (child->style()->clear()) {
2906         case CNONE:
2907             break;
2908         case CLEFT:
2909             bottom = leftBottom();
2910             break;
2911         case CRIGHT:
2912             bottom = rightBottom();
2913             break;
2914         case CBOTH:
2915             bottom = floatBottom();
2916             break;
2917     }
2918
2919     // We also clear floats if we are too big to sit on the same line as a float (and wish to avoid floats by default).
2920     // FIXME: Note that the remaining space checks aren't quite accurate, since you should be able to clear only some floats (the minimum # needed
2921     // to fit) and not all (we should be using nextFloatBottomBelow and looping).
2922     // Do not allow tables to wrap in quirks or even in almost strict mode
2923     // (ebay on the PLT, finance.yahoo.com in the real world, versiontracker.com forces even almost strict mode not to work)
2924     int result = clearSet ? max(0, bottom - child->yPos()) : 0;
2925     if (!result && child->avoidsFloats() && child->style()->width().isFixed() &&
2926         child->minPrefWidth() > lineWidth(child->yPos()) && child->minPrefWidth() <= availableWidth() &&
2927         document()->inStrictMode())
2928         result = max(0, floatBottom() - child->yPos());
2929     return result;
2930 }
2931
2932 void RenderBlock::addVisualOverflow(const IntRect& r)
2933 {
2934     if (r.isEmpty())
2935         return;
2936     m_overflowLeft = min(m_overflowLeft, r.x());
2937     m_overflowWidth = max(m_overflowWidth, r.right());
2938     m_overflowTop = min(m_overflowTop, r.y());
2939     m_overflowHeight = max(m_overflowHeight, r.bottom());
2940 }
2941
2942 bool RenderBlock::isPointInOverflowControl(HitTestResult& result, int _x, int _y, int _tx, int _ty)
2943 {
2944     if (!scrollsOverflow())
2945         return false;
2946
2947     return layer()->hitTestOverflowControls(result);
2948 }
2949
2950 bool RenderBlock::nodeAtPoint(const HitTestRequest& request, HitTestResult& result, int _x, int _y, int _tx, int _ty, HitTestAction hitTestAction)
2951 {
2952     bool inlineFlow = isInlineFlow();
2953
2954     int tx = _tx + m_x;
2955     int ty = _ty + m_y + borderTopExtra();
2956
2957     if (!inlineFlow && !isRenderView()) {
2958         // Check if we need to do anything at all.
2959         IntRect overflowBox = overflowRect(false);
2960         overflowBox.move(tx, ty);
2961         if (!overflowBox.contains(_x, _y))
2962             return false;
2963     }
2964
2965     if (isPointInOverflowControl(result, _x, _y, tx, ty)) {
2966         if (hitTestAction == HitTestBlockBackground) {
2967             updateHitTestResult(result, IntPoint(_x - tx, _y - ty));
2968             return true;
2969         }
2970         return false;
2971     }
2972
2973      // If we have lightweight control clipping, then we can't have any spillout.
2974     if (!hasControlClip() || controlClipRect(tx, ty).contains(_x, _y)) {
2975         // Hit test descendants first.
2976         int scrolledX = tx;
2977         int scrolledY = ty;
2978         if (hasOverflowClip())
2979             m_layer->subtractScrollOffset(scrolledX, scrolledY);
2980
2981         // Hit test contents if we don't have columns.
2982         if (!m_hasColumns && hitTestContents(request, result, _x, _y, scrolledX, scrolledY, hitTestAction))
2983             return true;
2984
2985         // Hit test our columns if we do have them.
2986         if (m_hasColumns && hitTestColumns(request, result, _x, _y, scrolledX, scrolledY, hitTestAction))
2987             return true;
2988
2989         // Hit test floats.
2990         if (hitTestAction == HitTestFloat && m_floatingObjects) {
2991             if (isRenderView()) {
2992                 scrolledX += static_cast<RenderView*>(this)->frameView()->contentsX();
2993                 scrolledY += static_cast<RenderView*>(this)->frameView()->contentsY();
2994             }
2995
2996             FloatingObject* o;
2997             DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
2998             for (it.toLast(); (o = it.current()); --it) {
2999                 if (o->m_shouldPaint && !o->m_renderer->hasLayer()) {
3000                     int xoffset = scrolledX + o->m_left + o->m_renderer->marginLeft() - o->m_renderer->xPos();
3001                     int yoffset =  scrolledY + o->m_top + o->m_renderer->marginTop() - o->m_renderer->yPos();
3002                     if (o->m_renderer->hitTest(request, result, IntPoint(_x, _y), xoffset, yoffset)) {
3003                         updateHitTestResult(result, IntPoint(_x - xoffset, _y - yoffset));
3004                         return true;
3005                     }
3006                 }
3007             }
3008         }
3009     }
3010
3011     // Now hit test our background.
3012     if (!inlineFlow && (hitTestAction == HitTestBlockBackground || hitTestAction == HitTestChildBlockBackground)) {
3013         int topExtra = borderTopExtra();
3014         IntRect boundsRect(tx, ty - topExtra, m_width, m_height + topExtra + borderBottomExtra());
3015         if (style()->visibility() == VISIBLE && boundsRect.contains(_x, _y)) {
3016             updateHitTestResult(result, IntPoint(_x - tx, _y - ty + topExtra));
3017             return true;
3018         }
3019     }
3020
3021     return false;
3022 }
3023
3024 bool RenderBlock::hitTestColumns(const HitTestRequest& request, HitTestResult& result, int x, int y, int tx, int ty, HitTestAction hitTestAction)
3025 {
3026     // We need to do multiple passes, breaking up our hit testing into strips.
3027     // We can always go left to right, since column contents are clipped (meaning that there
3028     // can't be any overlap).
3029     int currXOffset = 0;
3030     int currYOffset = 0;
3031     int colGap = columnGap();
3032     Vector<IntRect>* colRects = columnRects();
3033     for (unsigned i = 0; i < colRects->size(); i++) {
3034         IntRect colRect = colRects->at(i);
3035         colRect.move(tx, ty);
3036
3037         if (colRect.contains(x, y)) {
3038             // The point is inside this column.
3039             // Adjust tx and ty to change where we hit test.
3040
3041             int finalX = tx + currXOffset;
3042             int finalY = ty + currYOffset;
3043             return hitTestContents(request, result, x, y, finalX, finalY, hitTestAction);
3044         }
3045
3046         // Move to the next position.
3047         if (style()->direction() == LTR)
3048             currXOffset += colRect.width() + colGap;
3049         else
3050             currXOffset -= (colRect.width() + colGap);
3051
3052         currYOffset -= colRect.height();
3053     }
3054
3055     return false;
3056 }
3057
3058 bool RenderBlock::hitTestContents(const HitTestRequest& request, HitTestResult& result, int x, int y, int tx, int ty, HitTestAction hitTestAction)
3059 {
3060     if (childrenInline() && !isTable()) {
3061         // We have to hit-test our line boxes.
3062         if (hitTestLines(request, result, x, y, tx, ty, hitTestAction)) {
3063             updateHitTestResult(result, IntPoint(x - tx, y - ty));
3064             return true;
3065         }
3066     } else {
3067         // Hit test our children.
3068         HitTestAction childHitTest = hitTestAction;
3069         if (hitTestAction == HitTestChildBlockBackgrounds)
3070             childHitTest = HitTestChildBlockBackground;
3071         for (RenderObject* child = lastChild(); child; child = child->previousSibling()) {
3072             // FIXME: We have to skip over inline flows, since they can show up inside RenderTables at the moment (a demoted inline <form> for example).  If we ever implement a
3073             // table-specific hit-test method (which we should do for performance reasons anyway), then we can remove this check.
3074             if (!child->hasLayer() && !child->isFloating() && !child->isInlineFlow() && child->nodeAtPoint(request, result, x, y, tx, ty, childHitTest)) {
3075                 updateHitTestResult(result, IntPoint(x - tx, y - ty));
3076                 return true;
3077             }
3078         }
3079     }
3080
3081     return false;
3082 }
3083
3084 Position RenderBlock::positionForBox(InlineBox *box, bool start) const
3085 {
3086     if (!box)
3087         return Position();
3088
3089     if (!box->object()->element())
3090         return Position(element(), start ? caretMinOffset() : caretMaxOffset());
3091
3092     if (!box->isInlineTextBox())
3093         return Position(box->object()->element(), start ? box->object()->caretMinOffset() : box->object()->caretMaxOffset());
3094
3095     InlineTextBox *textBox = static_cast<InlineTextBox *>(box);
3096     return Position(box->object()->element(), start ? textBox->start() : textBox->start() + textBox->len());
3097 }
3098
3099 Position RenderBlock::positionForRenderer(RenderObject* renderer, bool start) const
3100 {
3101     if (!renderer)
3102         return Position(element(), 0);
3103
3104     Node* node = renderer->element() ? renderer->element() : element();
3105     if (!node)
3106         return Position();
3107
3108     ASSERT(renderer == node->renderer());
3109
3110     int offset = start ? renderer->caretMinOffset() : renderer->caretMaxOffset();
3111
3112     // FIXME: This was a runtime check that seemingly couldn't fail; changed it to an assertion for now.
3113     ASSERT(!node->isCharacterDataNode() || renderer->isText());
3114
3115     return Position(node, offset);
3116 }
3117
3118 VisiblePosition RenderBlock::positionForCoordinates(int x, int y)
3119 {
3120     if (isTable())
3121         return RenderFlow::positionForCoordinates(x, y);
3122
3123     int top = borderTop();
3124     int bottom = top + borderTopExtra() + paddingTop() + contentHeight() + paddingBottom() + borderBottomExtra();
3125
3126     int left = borderLeft();
3127     int right = left + paddingLeft() + contentWidth() + paddingRight();
3128
3129     Node* n = element();
3130
3131     int contentsX = x;
3132     int contentsY = y - borderTopExtra();
3133     if (hasOverflowClip())
3134         m_layer->scrollOffset(contentsX, contentsY);
3135     if (m_hasColumns) {
3136         IntPoint contentsPoint(contentsX, contentsY);
3137         adjustPointToColumnContents(contentsPoint);
3138         contentsX = contentsPoint.x();
3139         contentsY = contentsPoint.y();
3140     }
3141
3142     if (isReplaced()) {
3143         if (y < 0 || y < height() && x < 0)
3144             return VisiblePosition(n, caretMinOffset(), DOWNSTREAM);
3145         if (y >= height() || y >= 0 && x >= width())
3146             return VisiblePosition(n, caretMaxOffset(), DOWNSTREAM);
3147     }
3148
3149     // If we start inside the shadow tree, we will stay inside (even if the point is above or below).
3150     if (!(n && n->isShadowNode()) && !childrenInline()) {
3151         // Don't return positions inside editable roots for coordinates outside those roots, except for coordinates outside
3152         // a document that is entirely editable.
3153         bool isEditableRoot = n && n->rootEditableElement() == n && !n->hasTagName(bodyTag) && !n->hasTagName(htmlTag);
3154
3155         if (y < top || (isEditableRoot && (y < bottom && x < left))) {
3156             if (!isEditableRoot)
3157                 if (RenderObject* c = firstChild()) { // FIXME: This code doesn't make any sense.  This child could be an inline or a positioned element or a float or a compact, etc.
3158                     VisiblePosition p = c->positionForCoordinates(contentsX - c->xPos(), contentsY - c->yPos());
3159                     if (p.isNotNull())
3160                         return p;
3161                 }
3162             if (n) {
3163                 if (Node* sp = n->shadowParentNode())
3164                     n = sp;
3165                 if (Node* p = n->parent())
3166                     return VisiblePosition(p, n->nodeIndex(), DOWNSTREAM);
3167             }
3168             return VisiblePosition(n, 0, DOWNSTREAM);
3169         }
3170
3171         if (y >= bottom || (isEditableRoot && (y >= top && x >= right))) {
3172             if (!isEditableRoot)
3173                 if (RenderObject* c = lastChild()) { // FIXME: This code doesn't make any sense.  This child could be an inline or a positioned element or a float or a compact, ect.
3174                     VisiblePosition p = c->positionForCoordinates(contentsX - c->xPos(), contentsY - c->yPos());
3175                     if (p.isNotNull())
3176                         return p;
3177                 }
3178             if (n) {
3179                 if (Node* sp = n->shadowParentNode())
3180                     n = sp;
3181                 if (Node* p = n->parent())
3182                     return VisiblePosition(p, n->nodeIndex() + 1, DOWNSTREAM);
3183             }
3184             return VisiblePosition(n, 0, DOWNSTREAM);
3185         }
3186     }
3187
3188     if (childrenInline()) {
3189         if (!firstRootBox())
3190             return VisiblePosition(n, 0, DOWNSTREAM);
3191
3192         if (contentsY < firstRootBox()->topOverflow() - verticalLineClickFudgeFactor)
3193             // y coordinate is above first root line box
3194             return VisiblePosition(positionForBox(firstRootBox()->firstLeafChild(), true), DOWNSTREAM);
3195
3196         // look for the closest line box in the root box which is at the passed-in y coordinate
3197         for (RootInlineBox* root = firstRootBox(); root; root = root->nextRootBox()) {
3198             // set the bottom based on whether there is a next root box
3199             if (root->nextRootBox())
3200                 // FIXME: make the break point halfway between the bottom of the previous root box and the top of the next root box
3201                 bottom = root->nextRootBox()->topOverflow();
3202             else
3203                 bottom = root->bottomOverflow() + verticalLineClickFudgeFactor;
3204             // check if this root line box is located at this y coordinate
3205             if (contentsY < bottom && root->firstChild()) {
3206                 InlineBox* closestBox = root->closestLeafChildForXPos(x);
3207                 if (closestBox)
3208                     // pass the box a y position that is inside it
3209                     return closestBox->object()->positionForCoordinates(contentsX, closestBox->m_y);
3210             }
3211         }
3212
3213         if (lastRootBox())
3214             // y coordinate is below last root line box
3215             return VisiblePosition(positionForBox(lastRootBox()->lastLeafChild(), false), DOWNSTREAM);
3216
3217         return VisiblePosition(n, 0, DOWNSTREAM);
3218     }
3219
3220     // See if any child blocks exist at this y coordinate.
3221     if (firstChild() && contentsY < firstChild()->yPos())
3222         return VisiblePosition(n, 0, DOWNSTREAM);
3223     for (RenderObject* renderer = firstChild(); renderer; renderer = renderer->nextSibling()) {
3224         if (renderer->height() == 0 || renderer->style()->visibility() != VISIBLE || renderer->isFloatingOrPositioned())
3225             continue;
3226         RenderObject* next = renderer->nextSibling();
3227         while (next && next->isFloatingOrPositioned())
3228             next = next->nextSibling();
3229         if (next)
3230             bottom = next->yPos();
3231         else
3232             bottom = top + scrollHeight();
3233         if (contentsY >= renderer->yPos() && contentsY < bottom)
3234             return renderer->positionForCoordinates(contentsX - renderer->xPos(), contentsY - renderer->yPos());
3235     }
3236
3237     return RenderFlow::positionForCoordinates(x, y);
3238 }
3239
3240 int RenderBlock::availableWidth() const
3241 {
3242     // If we have multiple columns, then the available width is reduced to our column width.
3243     if (m_hasColumns)
3244         return desiredColumnWidth();
3245     return contentWidth();
3246 }
3247
3248 int RenderBlock::columnGap() const
3249 {
3250     if (style()->hasNormalColumnGap())
3251         return style()->fontDescription().computedPixelSize(); // "1em" is recommended as the normal gap setting. Matches <p> margins.
3252     return static_cast<int>(style()->columnGap());
3253 }
3254
3255 void RenderBlock::calcColumnWidth()
3256 {
3257     // Calculate our column width and column count.
3258     unsigned desiredColumnCount = 1;
3259     int desiredColumnWidth = contentWidth();
3260
3261     // For now, we don't support multi-column layouts when printing, since we have to do a lot of work for proper pagination.
3262     if (document()->printing() || (style()->hasAutoColumnCount() && style()->hasAutoColumnWidth())) {
3263         setDesiredColumnCountAndWidth(desiredColumnCount, desiredColumnWidth);
3264         return;
3265     }
3266
3267     int availWidth = desiredColumnWidth;
3268     int colGap = columnGap();
3269     int colWidth = max(1, static_cast<int>(style()->columnWidth()));
3270     int colCount = max(1, static_cast<int>(style()->columnCount()));
3271
3272     if (style()->hasAutoColumnWidth()) {
3273         if ((colCount - 1) * colGap < availWidth) {
3274             desiredColumnCount = colCount;
3275             desiredColumnWidth = (availWidth - (desiredColumnCount - 1) * colGap) / desiredColumnCount;
3276         } else if (colGap < availWidth) {
3277             desiredColumnCount = availWidth / colGap;
3278             desiredColumnWidth = (availWidth - (desiredColumnCount - 1) * colGap) / desiredColumnCount;
3279         }
3280     } else if (style()->hasAutoColumnCount()) {
3281         if (colWidth < availWidth) {
3282             desiredColumnCount = (availWidth + colGap) / (colWidth + colGap);
3283             desiredColumnWidth = (availWidth - (desiredColumnCount - 1) * colGap) / desiredColumnCount;
3284         }
3285     } else {
3286         // Both are set.
3287         if (colCount * colWidth + (colCount - 1) * colGap <= availWidth) {
3288             desiredColumnCount = colCount;