/*

 * 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, 2009, 2010 Apple Inc. All rights reserved.

 * Copyright (C) Research In Motion Limited 2010. 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 "FloatQuad.h"

#include "Frame.h"

#include "FrameView.h"

#include "GraphicsContext.h"

#include "HTMLFormElement.h"

#include "HTMLNames.h"

#include "HitTestResult.h"

#include "InlineTextBox.h"

#include "RenderFlexibleBox.h"

#include "RenderImage.h"

#include "RenderInline.h"

#include "RenderLayer.h"

#include "RenderMarquee.h"

#include "RenderReplica.h"

#include "RenderTableCell.h"

#include "RenderTextFragment.h"

#include "RenderTheme.h"

#include "RenderView.h"

#include "SelectionController.h"

#include "Settings.h"

#include "TransformState.h"

#include <wtf/StdLibExtras.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.   

static const int verticalLineClickFudgeFactor = 3;

using namespace HTMLNames;

struct ColumnInfo : public Noncopyable {

    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;

typedef WTF::HashMap<RenderBlock*, ListHashSet<RenderInline*>*> ContinuationOutlineTableMap;

typedef WTF::HashSet<RenderBlock*> DelayedUpdateScrollInfoSet;

static int gDelayUpdateScrollInfo = 0;

static DelayedUpdateScrollInfoSet* gDelayedUpdateScrollInfoSet = 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_topQuirk = m_bottomQuirk = m_determinedTopQuirk = false;

}

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

RenderBlock::RenderBlock(Node* node)

      : RenderBox(node)

      , m_floatingObjects(0)

      , m_positionedObjects(0)

      , m_continuation(0)

      , m_maxMargin(0)

      , m_lineHeight(-1)

{

    setChildrenInline(true);

}

RenderBlock::~RenderBlock()

{

    delete m_floatingObjects;

    delete m_positionedObjects;

    delete m_maxMargin;

    if (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::destroy()

{

    // Make sure to destroy anonymous children first while they are still connected to the rest of the tree, so that they will

    // properly dirty line boxes that they are removed from. Effects that do :before/:after only on hover could crash otherwise.

    children()->destroyLeftoverChildren();

    // Destroy our continuation before anything other than anonymous children.

    // The reason we don't destroy it before anonymous children is that they may

    // have continuations of their own that are anonymous children of our continuation.

    if (m_continuation) {

        m_continuation->destroy();

        m_continuation = 0;

    }

    if (!documentBeingDestroyed()) {

        if (firstLineBox()) {

            // We can't wait for RenderBox::destroy to clear the selection,

            // because by then we will have nuked the line boxes.

            // FIXME: The SelectionController should be responsible for this when it

            // is notified of DOM mutations.

            if (isSelectionBorder())

                view()->clearSelection();

            // If we are an anonymous block, then our line boxes might have children

            // that will outlast this block. In the non-anonymous block case those

            // children will be destroyed by the time we return from this function.

            if (isAnonymousBlock()) {

                for (InlineFlowBox* box = firstLineBox(); box; box = box->nextLineBox()) {

                    while (InlineBox* childBox = box->firstChild())

                        childBox->remove();

                }

            }

        } else if (isInline() && parent())

            parent()->dirtyLinesFromChangedChild(this);

    }

    m_lineBoxes.deleteLineBoxes(renderArena());

    RenderBox::destroy();

}

void RenderBlock::styleWillChange(StyleDifference diff, const RenderStyle* newStyle)

{

    setReplaced(newStyle->isDisplayReplacedType());

    if (style() && parent() && diff == StyleDifferenceLayout && style()->position() != newStyle->position()) {

        if (newStyle->position() == StaticPosition)

            // Clear our positioned objects list. Our absolutely positioned descendants will be

            // inserted into our containing block's positioned objects list during layout.

            removePositionedObjects(0);

        else if (style()->position() == StaticPosition) {

            // Remove our absolutely positioned descendants from their current containing block.

            // They will be inserted into our positioned objects list during layout.

            RenderObject* cb = parent();

            while (cb && (cb->style()->position() == StaticPosition || (cb->isInline() && !cb->isReplaced())) && !cb->isRenderView()) {

                if (cb->style()->position() == RelativePosition && cb->isInline() && !cb->isReplaced()) {

                    cb = cb->containingBlock();

                    break;

                }

                cb = cb->parent();

            }

            if (cb->isRenderBlock())

                toRenderBlock(cb)->removePositionedObjects(this);

        }

    }

    RenderBox::styleWillChange(diff, newStyle);

}

void RenderBlock::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)

{

    RenderBox::styleDidChange(diff, oldStyle);

    if (!isAnonymousBlock()) {

        // Ensure that all of our continuation blocks pick up the new style.

        for (RenderBlock* currCont = blockElementContinuation(); currCont; currCont = currCont->blockElementContinuation()) {

            RenderBoxModelObject* nextCont = currCont->continuation();

            currCont->setContinuation(0);

            currCont->setStyle(style());

            currCont->setContinuation(nextCont);

        }

    }

    // 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());

            if (style()->specifiesColumns()) {

                if (child->style()->specifiesColumns())

                    newStyle->inheritColumnPropertiesFrom(style());

                if (child->style()->columnSpan())

                    newStyle->setColumnSpan(true);

            }

            newStyle->setDisplay(BLOCK);

            child->setStyle(newStyle.release());

        }

    }

    m_lineHeight = -1;

    // Update pseudos for :before and :after now.

    if (!isAnonymous() && document()->usesBeforeAfterRules() && canHaveChildren()) {

        updateBeforeAfterContent(BEFORE);

        updateBeforeAfterContent(AFTER);

    }

    updateFirstLetter();

}

void RenderBlock::updateBeforeAfterContent(PseudoId pseudoId)

{

    // If this is an anonymous wrapper, then the parent applies its own pseudo-element style to it.

    if (parent() && parent()->createsAnonymousWrapper())

        return;

    return children()->updateBeforeAfterContent(this, pseudoId);

}

RenderBlock* RenderBlock::continuationBefore(RenderObject* beforeChild)

{

    if (beforeChild && beforeChild->parent() == this)

        return this;

    RenderBlock* curr = toRenderBlock(continuation());

    RenderBlock* nextToLast = this;

    RenderBlock* last = this;

    while (curr) {

        if (beforeChild && beforeChild->parent() == curr) {

            if (curr->firstChild() == beforeChild)

                return last;

            return curr;

        }

        nextToLast = last;

        last = curr;

        curr = toRenderBlock(curr->continuation());

    }

    if (!beforeChild && !last->firstChild())

        return nextToLast;

    return last;

}

void RenderBlock::addChildToContinuation(RenderObject* newChild, RenderObject* beforeChild)

{

    RenderBlock* flow = continuationBefore(beforeChild);

    ASSERT(!beforeChild || beforeChild->parent()->isAnonymousColumnSpanBlock() || beforeChild->parent()->isRenderBlock());

    RenderBoxModelObject* beforeChildParent = 0;

    if (beforeChild)

        beforeChildParent = toRenderBoxModelObject(beforeChild->parent());

    else {

        RenderBoxModelObject* cont = flow->continuation();

        if (cont)

            beforeChildParent = cont;

        else

            beforeChildParent = flow;

    }

    if (newChild->isFloatingOrPositioned())

        return beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);

    // A continuation always consists of two potential candidates: a block or an anonymous

    // column span box holding column span children.

    bool childIsNormal = newChild->isInline() || !newChild->style()->columnSpan();

    bool bcpIsNormal = beforeChildParent->isInline() || !beforeChildParent->style()->columnSpan();

    bool flowIsNormal = flow->isInline() || !flow->style()->columnSpan();

    if (flow == beforeChildParent)

        return flow->addChildIgnoringContinuation(newChild, beforeChild);

    // The goal here is to match up if we can, so that we can coalesce and create the

    // minimal # of continuations needed for the inline.

    if (childIsNormal == bcpIsNormal)

        return beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);

    if (flowIsNormal == childIsNormal)

        return flow->addChildIgnoringContinuation(newChild, 0); // Just treat like an append.

    return beforeChildParent->addChildIgnoringContinuation(newChild, beforeChild);

}

void RenderBlock::addChildToAnonymousColumnBlocks(RenderObject* newChild, RenderObject* beforeChild)

{

    ASSERT(!continuation()); // We don't yet support column spans that aren't immediate children of the multi-column block.

    // The goal is to locate a suitable box in which to place our child.

    RenderBlock* beforeChildParent = toRenderBlock(beforeChild ? beforeChild->parent() : lastChild());

    // If the new child is floating or positioned it can just go in that block.

    if (newChild->isFloatingOrPositioned())

        return beforeChildParent->addChildIgnoringAnonymousColumnBlocks(newChild, beforeChild);

    // See if the child can be placed in the box.

    bool newChildHasColumnSpan = newChild->style()->columnSpan() && !newChild->isInline();

    bool beforeChildParentHoldsColumnSpans = beforeChildParent->isAnonymousColumnSpanBlock();

    if (newChildHasColumnSpan == beforeChildParentHoldsColumnSpans)

        return beforeChildParent->addChildIgnoringAnonymousColumnBlocks(newChild, beforeChild);

    if (!beforeChild) {

        // Create a new block of the correct type.

        RenderBlock* newBox = newChildHasColumnSpan ? createAnonymousColumnSpanBlock() : createAnonymousColumnsBlock();

        children()->appendChildNode(this, newBox);

        newBox->addChildIgnoringAnonymousColumnBlocks(newChild, 0);

        return;

    }

    RenderObject* immediateChild = beforeChild;

    bool isPreviousBlockViable = true;

    while (immediateChild->parent() != this) {

        if (isPreviousBlockViable)

            isPreviousBlockViable = !immediateChild->previousSibling();

        immediateChild = immediateChild->parent();

    }

    if (isPreviousBlockViable && immediateChild->previousSibling())

        return toRenderBlock(immediateChild->previousSibling())->addChildIgnoringAnonymousColumnBlocks(newChild, 0); // Treat like an append.

    // Split our anonymous blocks.

    RenderObject* newBeforeChild = splitAnonymousBlocksAroundChild(beforeChild);

    // Create a new anonymous box of the appropriate type.

    RenderBlock* newBox = newChildHasColumnSpan ? createAnonymousColumnSpanBlock() : createAnonymousColumnsBlock();

    children()->insertChildNode(this, newBox, newBeforeChild);

    newBox->addChildIgnoringAnonymousColumnBlocks(newChild, 0);

    return;

}

RenderBlock* RenderBlock::containingColumnsBlock(bool allowAnonymousColumnBlock)

{

    for (RenderObject* curr = this; curr; curr = curr->parent()) {

        if (!curr->isRenderBlock() || curr->isFloatingOrPositioned() || curr->isTableCell() || curr->isRoot() || curr->isRenderView() || curr->hasOverflowClip()

            || curr->isInlineBlockOrInlineTable())

            return 0;

        RenderBlock* currBlock = toRenderBlock(curr);

        if (currBlock->style()->specifiesColumns() && (allowAnonymousColumnBlock || !currBlock->isAnonymousColumnsBlock()))

            return currBlock;

        if (currBlock->isAnonymousColumnSpanBlock())

            return 0;

    }

    return 0;

}

RenderBlock* RenderBlock::clone() const

{

    RenderBlock* o = new (renderArena()) RenderBlock(node());

    o->setStyle(style());

    o->setChildrenInline(childrenInline());

    return o;

}

void RenderBlock::splitBlocks(RenderBlock* fromBlock, RenderBlock* toBlock,

                              RenderBlock* middleBlock,

                              RenderObject* beforeChild, RenderBoxModelObject* oldCont)

{

    // Create a clone of this inline.

    RenderBlock* cloneBlock = clone();

    cloneBlock->setContinuation(oldCont);

    // Now take all of the children from beforeChild to the end and remove

    // them from |this| and place them in the clone.

    if (!beforeChild && isAfterContent(lastChild()))

        beforeChild = lastChild();

    moveChildrenTo(cloneBlock, beforeChild, 0);

    // Hook |clone| up as the continuation of the middle block.

    middleBlock->setContinuation(cloneBlock);

    // We have been reparented and are now under the fromBlock.  We need

    // to walk up our block parent chain until we hit the containing anonymous columns block.

    // Once we hit the anonymous columns block we're done.

    RenderBoxModelObject* curr = toRenderBoxModelObject(parent());

    RenderBoxModelObject* currChild = this;

    while (curr && curr != fromBlock) {

        ASSERT(curr->isRenderBlock() && !curr->isAnonymousBlock());

        RenderBlock* blockCurr = toRenderBlock(curr);

        // Create a new clone.

        RenderBlock* cloneChild = cloneBlock;

        cloneBlock = blockCurr->clone();

        // Insert our child clone as the first child.

        cloneBlock->children()->appendChildNode(cloneBlock, cloneChild);

        // Hook the clone up as a continuation of |curr|.  Note we do encounter

        // anonymous blocks possibly as we walk up the block chain.  When we split an

        // anonymous block, there's no need to do any continuation hookup, since we haven't

        // actually split a real element.

        if (!blockCurr->isAnonymousBlock()) {

            oldCont = blockCurr->continuation();

            blockCurr->setContinuation(cloneBlock);

            cloneBlock->setContinuation(oldCont);

        }

        // Someone may have indirectly caused a <q> to split.  When this happens, the :after content

        // has to move into the inline continuation.  Call updateBeforeAfterContent to ensure that the inline's :after

        // content gets properly destroyed.

        if (document()->usesBeforeAfterRules())

            blockCurr->children()->updateBeforeAfterContent(blockCurr, AFTER);

        // Now we need to take all of the children starting from the first child

        // *after* currChild and append them all to the clone.

        RenderObject* afterContent = isAfterContent(cloneBlock->lastChild()) ? cloneBlock->lastChild() : 0;

        blockCurr->moveChildrenTo(cloneBlock, currChild->nextSibling(), 0, afterContent);

        // Keep walking up the chain.

        currChild = curr;

        curr = toRenderBoxModelObject(curr->parent());

    }

    // Now we are at the columns block level. We need to put the clone into the toBlock.

    toBlock->children()->appendChildNode(toBlock, cloneBlock);

    // Now take all the children after currChild and remove them from the fromBlock

    // and put them in the toBlock.

    fromBlock->moveChildrenTo(toBlock, currChild->nextSibling(), 0);

}

void RenderBlock::splitFlow(RenderObject* beforeChild, RenderBlock* newBlockBox,

                            RenderObject* newChild, RenderBoxModelObject* oldCont)

{

    RenderBlock* pre = 0;

    RenderBlock* block = containingColumnsBlock();

    // Delete our line boxes before we do the inline split into continuations.

    block->deleteLineBoxTree();

    bool madeNewBeforeBlock = false;

    if (block->isAnonymousColumnsBlock()) {

        // We can reuse this block and make it the preBlock of the next continuation.

        pre = block;

        pre->removePositionedObjects(0);

        block = toRenderBlock(block->parent());

    } else {

        // No anonymous block available for use.  Make one.

        pre = block->createAnonymousColumnsBlock();

        pre->setChildrenInline(false);

        madeNewBeforeBlock = true;

    }

    RenderBlock* post = block->createAnonymousColumnsBlock();

    post->setChildrenInline(false);

    RenderObject* boxFirst = madeNewBeforeBlock ? block->firstChild() : pre->nextSibling();

    if (madeNewBeforeBlock)

        block->children()->insertChildNode(block, pre, boxFirst);

    block->children()->insertChildNode(block, newBlockBox, boxFirst);

    block->children()->insertChildNode(block, post, boxFirst);

    block->setChildrenInline(false);

    if (madeNewBeforeBlock)

        block->moveChildrenTo(pre, boxFirst, 0);

    splitBlocks(pre, post, newBlockBox, beforeChild, oldCont);

    // We already know the newBlockBox isn't going to contain inline kids, so avoid wasting

    // time in makeChildrenNonInline by just setting this explicitly up front.

    newBlockBox->setChildrenInline(false);

    // We delayed adding the newChild until now so that the |newBlockBox| would be fully

    // connected, thus allowing newChild access to a renderArena should it need

    // to wrap itself in additional boxes (e.g., table construction).

    newBlockBox->addChild(newChild);

    // Always just do a full layout in order to ensure that line boxes (especially wrappers for images)

    // get deleted properly.  Because objects moves from the pre block into the post block, we want to