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