WebCore/rendering/RenderBlock.cpp

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