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