RenderBlock.cpp

/*
 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
 *           (C) 1999 Antti Koivisto (koivisto@kde.org)
 *           (C) 2007 David Smith (catfish.man@gmail.com)
 * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 */

#include "config.h"
#include "RenderBlock.h"

#include "Document.h"
#include "Element.h"
#include "Frame.h"
#include "FrameView.h"
#include "GraphicsContext.h"
#include "HTMLNames.h"
#include "HitTestResult.h"
#include "InlineTextBox.h"
#include "RenderImage.h"
#include "RenderMarquee.h"
#include "RenderReplica.h"
#include "RenderTableCell.h"
#include "RenderTextFragment.h"
#include "RenderTheme.h"
#include "RenderView.h"
#include "SelectionController.h"

using namespace std;
using namespace WTF;
using namespace Unicode;

namespace WebCore {

// Number of pixels to allow as a fudge factor when clicking above or below a line.
// clicking up to verticalLineClickFudgeFactor pixels above a line will correspond to the closest point on the line.   
const int verticalLineClickFudgeFactor= 3;

using namespace HTMLNames;

struct ColumnInfo {
    ColumnInfo()
        : m_desiredColumnWidth(0)
        , m_desiredColumnCount(1)
        { }
    int m_desiredColumnWidth;
    unsigned m_desiredColumnCount;
    Vector<IntRect> m_columnRects;
};

typedef WTF::HashMap<const RenderBox*, ColumnInfo*> ColumnInfoMap;
static ColumnInfoMap* gColumnInfoMap = 0;

typedef WTF::HashMap<const RenderBlock*, HashSet<RenderBox*>*> PercentHeightDescendantsMap;
static PercentHeightDescendantsMap* gPercentHeightDescendantsMap = 0;

typedef WTF::HashMap<const RenderBox*, HashSet<RenderBlock*>*> PercentHeightContainerMap;
static PercentHeightContainerMap* gPercentHeightContainerMap = 0;

// Our MarginInfo state used when laying out block children.
RenderBlock::MarginInfo::MarginInfo(RenderBlock* block, int top, int bottom)
{
    // Whether or not we can collapse our own margins with our children.  We don't do this
    // if we had any border/padding (obviously), if we're the root or HTML elements, or if
    // we're positioned, floating, a table cell.
    m_canCollapseWithChildren = !block->isRenderView() && !block->isRoot() && !block->isPositioned() &&
        !block->isFloating() && !block->isTableCell() && !block->hasOverflowClip() && !block->isInlineBlockOrInlineTable();

    m_canCollapseTopWithChildren = m_canCollapseWithChildren && (top == 0) && block->style()->marginTopCollapse() != MSEPARATE;

    // If any height other than auto is specified in CSS, then we don't collapse our bottom
    // margins with our children's margins.  To do otherwise would be to risk odd visual
    // effects when the children overflow out of the parent block and yet still collapse
    // with it.  We also don't collapse if we have any bottom border/padding.
    m_canCollapseBottomWithChildren = m_canCollapseWithChildren && (bottom == 0) &&
        (block->style()->height().isAuto() && block->style()->height().value() == 0) && block->style()->marginBottomCollapse() != MSEPARATE;
    
    m_quirkContainer = block->isTableCell() || block->isBody() || block->style()->marginTopCollapse() == MDISCARD || 
        block->style()->marginBottomCollapse() == MDISCARD;

    m_atTopOfBlock = true;
    m_atBottomOfBlock = false;

    m_posMargin = m_canCollapseTopWithChildren ? block->maxTopMargin(true) : 0;
    m_negMargin = m_canCollapseTopWithChildren ? block->maxTopMargin(false) : 0;

    m_selfCollapsingBlockClearedFloat = false;
    
    m_topQuirk = m_bottomQuirk = m_determinedTopQuirk = false;
}

// -------------------------------------------------------------------------------------------------------

RenderBlock::RenderBlock(Node* node)
      : RenderFlow(node)
      , m_floatingObjects(0)
      , m_positionedObjects(0)
      , m_maxMargin(0)
      , m_overflowHeight(0)
      , m_overflowWidth(0)
      , m_overflowLeft(0)
      , m_overflowTop(0)
{
}

RenderBlock::~RenderBlock()
{
    delete m_floatingObjects;
    delete m_positionedObjects;
    delete m_maxMargin;
    
    if (m_hasColumns)
        delete gColumnInfoMap->take(this);

    if (gPercentHeightDescendantsMap) {
        if (HashSet<RenderBox*>* descendantSet = gPercentHeightDescendantsMap->take(this)) {
            HashSet<RenderBox*>::iterator end = descendantSet->end();
            for (HashSet<RenderBox*>::iterator descendant = descendantSet->begin(); descendant != end; ++descendant) {
                HashSet<RenderBlock*>* containerSet = gPercentHeightContainerMap->get(*descendant);
                ASSERT(containerSet);
                if (!containerSet)
                    continue;
                ASSERT(containerSet->contains(this));
                containerSet->remove(this);
                if (containerSet->isEmpty()) {
                    gPercentHeightContainerMap->remove(*descendant);
                    delete containerSet;
                }
            }
            delete descendantSet;
        }
    }
}

void RenderBlock::styleWillChange(RenderStyle::Diff diff, const RenderStyle* newStyle)
{
    setReplaced(newStyle->isDisplayReplacedType());
    RenderFlow::styleWillChange(diff, newStyle);
}

void RenderBlock::styleDidChange(RenderStyle::Diff diff, const RenderStyle* oldStyle)
{
    RenderFlow::styleDidChange(diff, oldStyle);

    // FIXME: We could save this call when the change only affected non-inherited properties
    for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
        if (child->isAnonymousBlock()) {
            RefPtr<RenderStyle> newStyle = RenderStyle::create();
            newStyle->inheritFrom(style());
            newStyle->setDisplay(BLOCK);
            child->setStyle(newStyle.release());
        }
    }

    m_lineHeight = -1;

    // Update pseudos for :before and :after now.
    if (!isAnonymous() && canHaveChildren()) {
        updateBeforeAfterContent(RenderStyle::BEFORE);
        updateBeforeAfterContent(RenderStyle::AFTER);
    }
    updateFirstLetter();
}

void RenderBlock::addChildToFlow(RenderObject* newChild, RenderObject* beforeChild)
{
    // Make sure we don't append things after :after-generated content if we have it.
    if (!beforeChild && isAfterContent(lastChild()))
        beforeChild = lastChild();

    bool madeBoxesNonInline = false;

    // If the requested beforeChild is not one of our children, then this is because
    // there is an anonymous container within this object that contains the beforeChild.
    if (beforeChild && beforeChild->parent() != this) {
        RenderObject* anonymousChild = beforeChild->parent();
        ASSERT(anonymousChild);

        while (anonymousChild->parent() != this)
            anonymousChild = anonymousChild->parent();

        ASSERT(anonymousChild->isAnonymous());

        if (anonymousChild->isAnonymousBlock()) {
            // Insert the child into the anonymous block box instead of here.
            if (newChild->isInline() || beforeChild->parent()->firstChild() != beforeChild)
                beforeChild->parent()->addChild(newChild, beforeChild);
            else
                addChildToFlow(newChild, beforeChild->parent());
            return;
        }

        ASSERT(anonymousChild->isTable());
        if (newChild->isTableCol() && newChild->style()->display() == TABLE_COLUMN_GROUP
                || newChild->isRenderBlock() && newChild->style()->display() == TABLE_CAPTION
                || newChild->isTableSection()
                || newChild->isTableRow()
                || newChild->isTableCell()) {
            // Insert into the anonymous table.
            anonymousChild->addChild(newChild, beforeChild);
            return;
        }

        // Go on to insert before the anonymous table.
        beforeChild = anonymousChild;
    }

    // A block has to either have all of its children inline, or all of its children as blocks.
    // So, if our children are currently inline and a block child has to be inserted, we move all our
    // inline children into anonymous block boxes.
    if (m_childrenInline && !newChild->isInline() && !newChild->isFloatingOrPositioned()) {
        // This is a block with inline content. Wrap the inline content in anonymous blocks.
        makeChildrenNonInline(beforeChild);
        madeBoxesNonInline = true;

        if (beforeChild && beforeChild->parent() != this) {
            beforeChild = beforeChild->parent();
            ASSERT(beforeChild->isAnonymousBlock());
            ASSERT(beforeChild->parent() == this);
        }
    } else if (!m_childrenInline && (newChild->isFloatingOrPositioned() || newChild->isInline())) {
        // If we're inserting an inline child but all of our children are blocks, then we have to make sure
        // it is put into an anomyous block box. We try to use an existing anonymous box if possible, otherwise
        // a new one is created and inserted into our list of children in the appropriate position.
        RenderObject* afterChild = beforeChild ? beforeChild->previousSibling() : lastChild();

        if (afterChild && afterChild->isAnonymousBlock()) {
            afterChild->addChild(newChild);
            return;
        }

        if (newChild->isInline()) {
            // No suitable existing anonymous box - create a new one.
            RenderBlock* newBox = createAnonymousBlock();
            RenderContainer::addChild(newBox, beforeChild);
            newBox->addChild(newChild);
            return;
        }
    }

    RenderContainer::addChild(newChild, beforeChild);
    // ### care about aligned stuff

    if (madeBoxesNonInline && parent() && isAnonymousBlock())
        parent()->removeLeftoverAnonymousBlock(this);
    // this object may be dead here
}

static void getInlineRun(RenderObject* start, RenderObject* boundary,
                         RenderObject*& inlineRunStart,
                         RenderObject*& inlineRunEnd)
{
    // Beginning at |start| we find the largest contiguous run of inlines that
    // we can.  We denote the run with start and end points, |inlineRunStart|
    // and |inlineRunEnd|.  Note that these two values may be the same if
    // we encounter only one inline.
    //
    // We skip any non-inlines we encounter as long as we haven't found any
    // inlines yet.
    //
    // |boundary| indicates a non-inclusive boundary point.  Regardless of whether |boundary|
    // is inline or not, we will not include it in a run with inlines before it.  It's as though we encountered
    // a non-inline.
    
    // Start by skipping as many non-inlines as we can.
    RenderObject * curr = start;
    bool sawInline;
    do {
        while (curr && !(curr->isInline() || curr->isFloatingOrPositioned()))
            curr = curr->nextSibling();
        
        inlineRunStart = inlineRunEnd = curr;
        
        if (!curr)
            return; // No more inline children to be found.
        
        sawInline = curr->isInline();
        
        curr = curr->nextSibling();
        while (curr && (curr->isInline() || curr->isFloatingOrPositioned()) && (curr != boundary)) {
            inlineRunEnd = curr;
            if (curr->isInline())
                sawInline = true;
            curr = curr->nextSibling();
        }
    } while (!sawInline);
}

void RenderBlock::deleteLineBoxTree()
{
    InlineFlowBox* line = m_firstLineBox;
    InlineFlowBox* nextLine;
    while (line) {
        nextLine = line->nextFlowBox();
        line->deleteLine(renderArena());
        line = nextLine;
    }
    m_firstLineBox = m_lastLineBox = 0;
}

void RenderBlock::makeChildrenNonInline(RenderObject *insertionPoint)
{    
    // makeChildrenNonInline takes a block whose children are *all* inline and it
    // makes sure that inline children are coalesced under anonymous
    // blocks.  If |insertionPoint| is defined, then it represents the insertion point for
    // the new block child that is causing us to have to wrap all the inlines.  This
    // means that we cannot coalesce inlines before |insertionPoint| with inlines following
    // |insertionPoint|, because the new child is going to be inserted in between the inlines,
    // splitting them.
    ASSERT(isInlineBlockOrInlineTable() || !isInline());
    ASSERT(!insertionPoint || insertionPoint->parent() == this);

    m_childrenInline = false;

    RenderObject *child = firstChild();
    if (!child)
        return;

    deleteLineBoxTree();

    while (child) {
        RenderObject *inlineRunStart, *inlineRunEnd;
        getInlineRun(child, insertionPoint, inlineRunStart, inlineRunEnd);

        if (!inlineRunStart)
            break;

        child = inlineRunEnd->nextSibling();

        RenderBlock* box = createAnonymousBlock();
        insertChildNode(box, inlineRunStart);
        RenderObject* o = inlineRunStart;
        while(o != inlineRunEnd)
        {
            RenderObject* no = o;
            o = no->nextSibling();
            box->moveChildNode(no);
        }
        box->moveChildNode(inlineRunEnd);
    }

#ifndef NDEBUG
    for (RenderObject *c = firstChild(); c; c = c->nextSibling())
        ASSERT(!c->isInline());
#endif

    repaint();
}

void RenderBlock::removeChild(RenderObject *oldChild)
{
    // If this child is a block, and if our previous and next siblings are
    // both anonymous blocks with inline content, then we can go ahead and
    // fold the inline content back together.
    RenderObject* prev = oldChild->previousSibling();
    RenderObject* next = oldChild->nextSibling();
    bool canDeleteAnonymousBlocks = !documentBeingDestroyed() && !isInline() && !oldChild->isInline() && 
                                    !oldChild->continuation() && 
                                    (!prev || (prev->isAnonymousBlock() && prev->childrenInline())) &&
                                    (!next || (next->isAnonymousBlock() && next->childrenInline()));
    if (canDeleteAnonymousBlocks && prev && next) {
        // Take all the children out of the |next| block and put them in
        // the |prev| block.
        prev->setNeedsLayoutAndPrefWidthsRecalc();
        RenderObject* o = next->firstChild();
        while (o) {
            RenderObject* no = o;
            o = no->nextSibling();
            prev->moveChildNode(no);
        }
 
        RenderBlock* nextBlock = static_cast<RenderBlock*>(next);
        nextBlock->deleteLineBoxTree();
        
        // Nuke the now-empty block.
        next->destroy();
    }

    RenderFlow::removeChild(oldChild);

    RenderObject* child = prev ? prev : next;
    if (canDeleteAnonymousBlocks && child && !child->previousSibling() && !child->nextSibling() && !isFlexibleBox()) {
        // The removal has knocked us down to containing only a single anonymous
        // box.  We can go ahead and pull the content right back up into our
        // box.
        setNeedsLayoutAndPrefWidthsRecalc();
        RenderBlock* anonBlock = static_cast<RenderBlock*>(removeChildNode(child, false));
        m_childrenInline = true;
        RenderObject* o = anonBlock->firstChild();
        while (o) {
            RenderObject* no = o;
            o = no->nextSibling();
            moveChildNode(no);
        }

        // Delete the now-empty block's lines and nuke it.
        anonBlock->deleteLineBoxTree();
        anonBlock->destroy();
    }
}

int RenderBlock::overflowHeight(bool includeInterior) const
{
    if (!includeInterior && hasOverflowClip()) {
        int shadowHeight = 0;
        for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next)
            shadowHeight = max(boxShadow->y + boxShadow->blur, shadowHeight);
        int height = m_height + shadowHeight;
        if (hasReflection())
            height = max(height, reflectionBox().bottom());
        return height;
    }
    return m_overflowHeight;
}

int RenderBlock::overflowWidth(bool includeInterior) const
{
    if (!includeInterior && hasOverflowClip()) {
        int shadowWidth = 0;
        for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next)
            shadowWidth = max(boxShadow->x + boxShadow->blur, shadowWidth);
        int width = m_width + shadowWidth;
        if (hasReflection())
            width = max(width, reflectionBox().right());
        return width;
    }
    return m_overflowWidth;
}

int RenderBlock::overflowLeft(bool includeInterior) const
{
    if (!includeInterior && hasOverflowClip()) {
        int shadowLeft = 0;
        for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next)
            shadowLeft = min(boxShadow->x - boxShadow->blur, shadowLeft);
        int left = shadowLeft;
        if (hasReflection())
            left = min(left, reflectionBox().x());
        return left;
    }
    return m_overflowLeft;
}

int RenderBlock::overflowTop(bool includeInterior) const
{
    if (!includeInterior && hasOverflowClip()) {
        int shadowTop = 0;
        for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next)
            shadowTop = min(boxShadow->y - boxShadow->blur, shadowTop);
        int top = shadowTop;
        if (hasReflection())
            top = min(top, reflectionBox().y());
        return top;
    }
    return m_overflowTop;
}

IntRect RenderBlock::overflowRect(bool includeInterior) const
{
    if (!includeInterior && hasOverflowClip()) {
        IntRect box = borderBox();
        int shadowLeft = 0;
        int shadowRight = 0;
        int shadowTop = 0;
        int shadowBottom = 0;

        for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next) {
            shadowLeft = min(boxShadow->x - boxShadow->blur, shadowLeft);
            shadowRight = max(boxShadow->x + boxShadow->blur, shadowRight);
            shadowTop = min(boxShadow->y - boxShadow->blur, shadowTop);
            shadowBottom = max(boxShadow->y + boxShadow->blur, shadowBottom);
        }

        box.move(shadowLeft, shadowTop);
        box.setWidth(box.width() - shadowLeft + shadowRight);
        box.setHeight(box.height() - shadowTop + shadowBottom);

        if (hasReflection()) {
            IntRect reflection(reflectionBox());
            int reflectTop = min(box.y(), reflection.y());
            int reflectBottom = max(box.bottom(), reflection.bottom());
            box.setHeight(reflectBottom - reflectTop);
            box.setY(reflectTop);
            
            int reflectLeft = min(box.x(), reflection.x());
            int reflectRight = max(box.right(), reflection.right());
            box.setWidth(reflectRight - reflectLeft);
            box.setX(reflectLeft);
        }
        return box;
    }

    if (!includeInterior && hasOverflowClip())
        return borderBox();
    int l = overflowLeft(includeInterior);
    int t = min(overflowTop(includeInterior), -borderTopExtra());
    return IntRect(l, t, overflowWidth(includeInterior) - l, max(overflowHeight(includeInterior), height() + borderBottomExtra()) - t);
}

bool RenderBlock::isSelfCollapsingBlock() const
{
    // We are not self-collapsing if we
    // (a) have a non-zero height according to layout (an optimization to avoid wasting time)
    // (b) are a table,
    // (c) have border/padding,
    // (d) have a min-height
    // (e) have specified that one of our margins can't collapse using a CSS extension
    if (m_height > 0 ||
        isTable() || (borderBottom() + paddingBottom() + borderTop() + paddingTop()) != 0 ||
        style()->minHeight().isPositive() || 
        style()->marginTopCollapse() == MSEPARATE || style()->marginBottomCollapse() == MSEPARATE)
        return false;

    bool hasAutoHeight = style()->height().isAuto();
    if (style()->height().isPercent() && !style()->htmlHacks()) {
        hasAutoHeight = true;
        for (RenderBlock* cb = containingBlock(); !cb->isRenderView(); cb = cb->containingBlock()) {
            if (cb->style()->height().isFixed() || cb->isTableCell())
                hasAutoHeight = false;
        }
    }

    // If the height is 0 or auto, then whether or not we are a self-collapsing block depends
    // on whether we have content that is all self-collapsing or not.
    if (hasAutoHeight || ((style()->height().isFixed() || style()->height().isPercent()) && style()->height().isZero())) {
        // If the block has inline children, see if we generated any line boxes.  If we have any
        // line boxes, then we can't be self-collapsing, since we have content.
        if (childrenInline())
            return !firstLineBox();
        
        // Whether or not we collapse is dependent on whether all our normal flow children
        // are also self-collapsing.
        for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
            if (child->isFloatingOrPositioned())
                continue;
            if (!child->isSelfCollapsingBlock())
                return false;
        }
        return true;
    }
    return false;
}

void RenderBlock::layout()
{
    // Update our first letter info now.
    updateFirstLetter();

    // Table cells call layoutBlock directly, so don't add any logic here.  Put code into
    // layoutBlock().
    layoutBlock(false);
    
    // It's safe to check for control clip here, since controls can never be table cells.
    if (hasControlClip()) {
        // Because of the lightweight clip, there can never be any overflow from children.
        m_overflowWidth = m_width;
        m_overflowHeight = m_height;
        m_overflowLeft = 0;
        m_overflowTop = 0;
    }
}

void RenderBlock::layoutBlock(bool relayoutChildren)
{
    ASSERT(needsLayout());

    if (isInline() && !isInlineBlockOrInlineTable()) // Inline <form>s inside various table elements can
        return;                                      // cause us to come in here.  Just bail.

    if (!relayoutChildren && layoutOnlyPositionedObjects())
        return;

    IntRect oldBounds;
    IntRect oldOutlineBox;
    bool checkForRepaint = m_everHadLayout && checkForRepaintDuringLayout();
    if (checkForRepaint) {
        oldBounds = absoluteClippedOverflowRect();
        oldOutlineBox = absoluteOutlineBox();
    }

    bool hadColumns = m_hasColumns;
    if (!hadColumns && !hasReflection())
        view()->pushLayoutState(this, IntSize(xPos(), yPos()));
    else
        view()->disableLayoutState();

    int oldWidth = m_width;
    int oldColumnWidth = desiredColumnWidth();

    calcWidth();
    calcColumnWidth();

    m_overflowWidth = m_width;
    m_overflowLeft = 0;

    if (oldWidth != m_width || oldColumnWidth != desiredColumnWidth())
        relayoutChildren = true;

    clearFloats();

    int previousHeight = m_height;
    m_height = 0;
    m_overflowHeight = 0;

    // We use four values, maxTopPos, maxPosNeg, maxBottomPos, and maxBottomNeg, to track
    // our current maximal positive and negative margins.  These values are used when we
    // are collapsed with adjacent blocks, so for example, if you have block A and B
    // collapsing together, then you'd take the maximal positive margin from both A and B
    // and subtract it from the maximal negative margin from both A and B to get the
    // true collapsed margin.  This algorithm is recursive, so when we finish layout()
    // our block knows its current maximal positive/negative values.
    //
    // Start out by setting our margin values to our current margins.  Table cells have
    // no margins, so we don't fill in the values for table cells.
    bool isCell = isTableCell();
    if (!isCell) {
        initMaxMarginValues();

        m_topMarginQuirk = style()->marginTop().quirk();
        m_bottomMarginQuirk = style()->marginBottom().quirk();

        Node* node = element();
        if (node && node->hasTagName(formTag) && static_cast<HTMLFormElement*>(node)->isMalformed()) {
            // See if this form is malformed (i.e., unclosed). If so, don't give the form
            // a bottom margin.
            setMaxBottomMargins(0, 0);
        }
    }

    // For overflow:scroll blocks, ensure we have both scrollbars in place always.
    if (scrollsOverflow()) {
        if (style()->overflowX() == OSCROLL)
            m_layer->setHasHorizontalScrollbar(true);
        if (style()->overflowY() == OSCROLL)
            m_layer->setHasVerticalScrollbar(true);
    }

    int repaintTop = 0;
    int repaintBottom = 0;
    int maxFloatBottom = 0;
    if (childrenInline())
        layoutInlineChildren(relayoutChildren, repaintTop, repaintBottom);
    else
        layoutBlockChildren(relayoutChildren, maxFloatBottom);

    // Expand our intrinsic height to encompass floats.
    int toAdd = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
    if (floatBottom() > (m_height - toAdd) && (isInlineBlockOrInlineTable() || isFloatingOrPositioned() || hasOverflowClip() ||
                                    (parent() && parent()->isFlexibleBox() || m_hasColumns)))
        m_height = floatBottom() + toAdd;
    
    // Now lay out our columns within this intrinsic height, since they can slightly affect the intrinsic height as
    // we adjust for clean column breaks.
    int singleColumnBottom = layoutColumns();

    // Calculate our new height.
    int oldHeight = m_height;
    calcHeight();
    if (oldHeight != m_height) {
        if (oldHeight > m_height && maxFloatBottom > m_height && !childrenInline()) {
            // One of our children's floats may have become an overhanging float for us. We need to look for it.
            for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
                if (child->isBlockFlow() && !child->isFloatingOrPositioned()) {
                    RenderBlock* block = static_cast<RenderBlock*>(child);
                    if (block->floatBottom() + block->yPos() > m_height)
                        addOverhangingFloats(block, -block->xPos(), -block->yPos(), false);
                }
            }
        }
        // We have to rebalance columns to the new height.
        layoutColumns(singleColumnBottom);

        // If the block got expanded in size, then increase our overflowheight to match.
        if (m_overflowHeight > m_height)
            m_overflowHeight -= toAdd;
        if (m_overflowHeight < m_height)
            m_overflowHeight = m_height;
    }
    if (previousHeight != m_height)
        relayoutChildren = true;

    // Some classes of objects (floats and fieldsets with no specified heights and table cells) expand to encompass
    // overhanging floats.
    if (hasOverhangingFloats() && expandsToEncloseOverhangingFloats()) {
        m_height = floatBottom();
        m_height += borderBottom() + paddingBottom();
    }

    if ((isCell || isInline() || isFloatingOrPositioned() || isRoot()) && !hasOverflowClip() && !hasControlClip())
        addVisualOverflow(floatRect());

    layoutPositionedObjects(relayoutChildren || isRoot());

    positionListMarker();

    // Always ensure our overflow width/height are at least as large as our width/height.
    m_overflowWidth = max(m_overflowWidth, m_width);
    m_overflowHeight = max(m_overflowHeight, m_height);

    if (!hasOverflowClip()) {
        for (ShadowData* boxShadow = style()->boxShadow(); boxShadow; boxShadow = boxShadow->next) {
            m_overflowLeft = min(m_overflowLeft, boxShadow->x - boxShadow->blur);
            m_overflowWidth = max(m_overflowWidth, m_width + boxShadow->x + boxShadow->blur);
            m_overflowTop = min(m_overflowTop, boxShadow->y - boxShadow->blur);
            m_overflowHeight = max(m_overflowHeight, m_height + boxShadow->y + boxShadow->blur);
        }
        
        if (hasReflection()) {
            m_overflowTop = min(m_overflowTop, reflectionBox().y());
            m_overflowHeight = max(m_overflowHeight, reflectionBox().bottom());
        }
    }

    if (!hadColumns && !hasReflection())
        view()->popLayoutState();
    else
        view()->enableLayoutState();

    // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
    // we overflow or not.
    if (hasOverflowClip())
        m_layer->updateScrollInfoAfterLayout();

    // Repaint with our new bounds if they are different from our old bounds.
    bool didFullRepaint = false;
    if (checkForRepaint)
        didFullRepaint = repaintAfterLayoutIfNeeded(oldBounds, oldOutlineBox);
    if (!didFullRepaint && repaintTop != repaintBottom && (style()->visibility() == VISIBLE || enclosingLayer()->hasVisibleContent())) {
        IntRect repaintRect(m_overflowLeft, repaintTop, m_overflowWidth - m_overflowLeft, repaintBottom - repaintTop);

        // FIXME: Deal with multiple column repainting.  We have to split the repaint
        // rect up into multiple rects if it spans columns.

        repaintRect.inflate(maximalOutlineSize(PaintPhaseOutline));
        
        if (hasOverflowClip()) {
            // Adjust repaint rect for scroll offset
            int x = repaintRect.x();
            int y = repaintRect.y();
            layer()->subtractScrolledContentOffset(x, y);
            repaintRect.setX(x);
            repaintRect.setY(y);

            // Don't allow this rect to spill out of our overflow box.
            repaintRect.intersect(IntRect(0, 0, m_width, m_height));
        }

        // Make sure the rect is still non-empty after intersecting for overflow above
        if (!repaintRect.isEmpty()) {
            repaintRectangle(repaintRect); // We need to do a partial repaint of our content.
            if (hasReflection())
                layer()->reflection()->repaintRectangle(repaintRect);
        }
    }
    setNeedsLayout(false);
}

void RenderBlock::adjustPositionedBlock(RenderObject* child, const MarginInfo& marginInfo)
{
    if (child->hasStaticX()) {
        if (style()->direction() == LTR)
            child->setStaticX(borderLeft() + paddingLeft());
        else
            child->setStaticX(borderRight() + paddingRight());
    }

    if (child->hasStaticY()) {
        int y = m_height;
        if (!marginInfo.canCollapseWithTop()) {
            child->calcVerticalMargins();
            int marginTop = child->marginTop();
            int collapsedTopPos = marginInfo.posMargin();
            int collapsedTopNeg = marginInfo.negMargin();
            if (marginTop > 0) {
                if (marginTop > collapsedTopPos)
                    collapsedTopPos = marginTop;
            } else {
                if (-marginTop > collapsedTopNeg)
                    collapsedTopNeg = -marginTop;
            }
            y += (collapsedTopPos - collapsedTopNeg) - marginTop;
        }
        child->setStaticY(y);
    }
}

void RenderBlock::adjustFloatingBlock(const MarginInfo& marginInfo)
{
    // The float should be positioned taking into account the bottom margin
    // of the previous flow.  We add that margin into the height, get the
    // float positioned properly, and then subtract the margin out of the
    // height again.  In the case of self-collapsing blocks, we always just
    // use the top margins, since the self-collapsing block collapsed its
    // own bottom margin into its top margin.
    //
    // Note also that the previous flow may collapse its margin into the top of
    // our block.  If this is the case, then we do not add the margin in to our
    // height when computing the position of the float.   This condition can be tested
    // for by simply calling canCollapseWithTop.  See
    // http://www.hixie.ch/tests/adhoc/css/box/block/margin-collapse/046.html for
    // an example of this scenario.
    int marginOffset = marginInfo.canCollapseWithTop() ? 0 : marginInfo.margin();
    m_height += marginOffset;
    positionNewFloats();
    m_height -= marginOffset;
}

RenderObject* RenderBlock::handleSpecialChild(RenderObject* child, const MarginInfo& marginInfo, CompactInfo& compactInfo, bool& handled)
{
    // Handle positioned children first.
    RenderObject* next = handlePositionedChild(child, marginInfo, handled);
    if (handled) return next;
    
    // Handle floating children next.
    next = handleFloatingChild(child, marginInfo, handled);
    if (handled) return next;

    // 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.
    next = handleCompactChild(child, compactInfo, handled);
    if (handled) return next;

    // Finally, see if we have a run-in element.
    return handleRunInChild(child, handled);
}


RenderObject* RenderBlock::handlePositionedChild(RenderObject* child, const MarginInfo& marginInfo, bool& handled)
{
    if (child->isPositioned()) {
        handled = true;
        child->containingBlock()->insertPositionedObject(child);
        adjustPositionedBlock(child, marginInfo);
        return child->nextSibling();
    }

    return 0;
}

RenderObject* RenderBlock::handleFloatingChild(RenderObject* child, const MarginInfo& marginInfo, bool& handled)
{
    if (child->isFloating()) {
        handled = true;
        insertFloatingObject(child);
        adjustFloatingBlock(marginInfo);
        return child->nextSibling();
    }
    
    return 0;
}

RenderObject* RenderBlock::handleCompactChild(RenderObject* child, CompactInfo& compactInfo, bool& handled)
{
    // FIXME: We only deal with one compact at a time.  It is unclear what should be
    // done if multiple contiguous compacts are encountered.  For now we assume that
    // compact A followed by another compact B should simply be treated as block A.
    if (child->isCompact() && !compactInfo.compact() && (child->childrenInline() || child->isReplaced())) {
        // Get the next non-positioned/non-floating RenderBlock.
        RenderObject* next = child->nextSibling();
        RenderObject* curr = next;
        while (curr && curr->isFloatingOrPositioned())
            curr = curr->nextSibling();
        if (curr && curr->isRenderBlock() && !curr->isCompact() && !curr->isRunIn()) {
            curr->calcWidth(); // So that horizontal margins are correct.
                               
            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
                                    // fill the containing block width.
            child->calcWidth();
            int childMargins = child->marginLeft() + child->marginRight();
            int margin = style()->direction() == LTR ? curr->marginLeft() : curr->marginRight();
            if (margin >= (childMargins + child->maxPrefWidth())) {
                // The compact will fit in the margin.
                handled = true;
                compactInfo.set(child, curr);
                child->setPos(0,0); // This position will be updated to reflect the compact's
                                    // desired position and the line box for the compact will
                                    // pick that position up.
                
                // Remove the child.
                RenderObject* next = child->nextSibling();
                removeChildNode(child);
                
                // Now insert the child under |curr|.
                curr->insertChildNode(child, curr->firstChild());
                return next;
            }
            else
                child->setInline(false); // We didn't fit, so we remain a block-level element.
        }
    }
    return 0;
}

void RenderBlock::insertCompactIfNeeded(RenderObject* child, CompactInfo& compactInfo)
{
    if (compactInfo.matches(child)) {
        // We have a compact child to squeeze in.
        RenderObject* compactChild = compactInfo.compact();
        int compactXPos = borderLeft() + paddingLeft() + compactChild->marginLeft();
        if (style()->direction() == RTL) {
            compactChild->calcWidth(); // have to do this because of the capped maxwidth
            compactXPos = width() - borderRight() - paddingRight() - marginRight() -
                compactChild->width() - compactChild->marginRight();
        }
        compactXPos -= child->xPos(); // Put compactXPos into the child's coordinate space.
        compactChild->setPos(compactXPos, compactChild->yPos()); // Set the x position.
        compactInfo.clear();
    }
}

RenderObject* RenderBlock::handleRunInChild(RenderObject* child, bool& handled)
{
    // See if we have a run-in element with inline children.  If the
    // children aren't inline, then just treat the run-in as a normal
    // block.
    if (child->isRunIn() && (child->childrenInline() || child->isReplaced())) {
        // Get the next non-positioned/non-floating RenderBlock.
        RenderObject* curr = child->nextSibling();
        while (curr && curr->isFloatingOrPositioned())
            curr = curr->nextSibling();
        if (curr && (curr->isRenderBlock() && curr->childrenInline() && !curr->isCompact() && !curr->isRunIn())) {
            // The block acts like an inline, so just null out its
            // position.
            handled = true;
            child->setInline(true);
            child->setPos(0,0);
            
            // Remove the child.
            RenderObject* next = child->nextSibling();
            removeChildNode(child);
            
            // Now insert the child under |curr|.
            curr->insertChildNode(child, curr->firstChild());
            return next;
        }
    }
    return 0;
}

void RenderBlock::collapseMargins(RenderObject* child, MarginInfo& marginInfo, int yPosEstimate)
{
    // Get our max pos and neg top margins.
    int posTop = child->maxTopMargin(true);
    int negTop = child->maxTopMargin(false);

    // For self-collapsing blocks, collapse our bottom margins into our
    // top to get new posTop and negTop values.
    if (child->isSelfCollapsingBlock()) {
        posTop = max(posTop, child->maxBottomMargin(true));
        negTop = max(negTop, child->maxBottomMargin(false));
    }
    
    // See if the top margin is quirky. We only care if this child has
    // margins that will collapse with us.
    bool topQuirk = child->isTopMarginQuirk() || style()->marginTopCollapse() == MDISCARD;

    if (marginInfo.canCollapseWithTop()) {
        // This child is collapsing with the top of the
        // block.  If it has larger margin values, then we need to update
        // our own maximal values.
        if (!style()->htmlHacks() || !marginInfo.quirkContainer() || !topQuirk)
            setMaxTopMargins(max(posTop, maxTopPosMargin()), max(negTop, maxTopNegMargin()));

        // The minute any of the margins involved isn't a quirk, don't
        // collapse it away, even if the margin is smaller (www.webreference.com
        // has an example of this, a <dt> with 0.8em author-specified inside
        // a <dl> inside a <td>.
        if (!marginInfo.determinedTopQuirk() && !topQuirk && (posTop-negTop)) {
            m_topMarginQuirk = false;
            marginInfo.setDeterminedTopQuirk(true);
        }