/*

 * 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 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 "RenderTableCell.h"

#include "RenderTextFragment.h"

#include "RenderTheme.h"

#include "RenderView.h"

#include "SelectionController.h"

#include "TextStream.h"

#if PLATFORM(SYMBIAN)

#include "WebCoreFrameBridge.h"

#endif

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;

// 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) {

        ColumnInfoMap::iterator it = gColumnInfoMap->find(this);

        delete it->second;

        gColumnInfoMap->remove(it);

    }

}

void RenderBlock::setStyle(RenderStyle* _style)

{

    setReplaced(_style->isDisplayReplacedType());

    RenderFlow::setStyle(_style);

#if PLATFORM(SYMBIAN)

    //Notify the view of the writing direction

    if (isBody())

        view()->frameView()->frame()->bridge()->setWritingDirectionRtl(style()->direction() == RTL);

#endif

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

            RenderStyle* newStyle = new (renderArena()) RenderStyle();

            newStyle->inheritFrom(style());

            newStyle->setDisplay(BLOCK);

            child->setStyle(newStyle);

        }

    }

    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 most likely because

    // there is an anonymous block box within this object that contains the beforeChild. So

    // just insert the child into the anonymous block box instead of here.

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

        ASSERT(beforeChild->parent());

        ASSERT(beforeChild->parent()->isAnonymousBlock());

        if (newChild->isInline()) {

            beforeChild->parent()->addChild(newChild,beforeChild);

            return;

        }

        else if (beforeChild->parent()->firstChild() != beforeChild)

            return beforeChild->parent()->addChild(newChild, beforeChild);

        else

            return addChildToFlow(newChild, beforeChild->parent());

    }

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

    {

        // 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.

        if (newChild->isInline()) {

            if (beforeChild) {

                if (beforeChild->previousSibling() && beforeChild->previousSibling()->isAnonymousBlock()) {

                    beforeChild->previousSibling()->addChild(newChild);

                    return;

                }

            }

            else {

                if (lastChild() && lastChild()->isAnonymousBlock()) {

                    lastChild()->addChild(newChild);

                    return;

                }

            }

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

    deleteLineBoxTree();

    RenderObject *child = firstChild();

    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

}

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()) {

        if (ShadowData* boxShadow = style()->boxShadow())

            return m_height + max(boxShadow->y + boxShadow->blur, 0);

        return m_height;

    }

    return m_overflowHeight;

}

int RenderBlock::overflowWidth(bool includeInterior) const

{

    if (!includeInterior && hasOverflowClip()) {

        if (ShadowData* boxShadow = style()->boxShadow())

            return m_width + max(boxShadow->x + boxShadow->blur, 0);

        return m_width;

    }

    return m_overflowWidth;

}

int RenderBlock::overflowLeft(bool includeInterior) const

{

    if (!includeInterior && hasOverflowClip()) {

        if (ShadowData* boxShadow = style()->boxShadow())

            return min(boxShadow->x - boxShadow->blur, 0);

        return 0;

    }

    return m_overflowLeft;

}

int RenderBlock::overflowTop(bool includeInterior) const

{

    if (!includeInterior && hasOverflowClip()) {

        if (ShadowData* boxShadow = style()->boxShadow())

            return min(boxShadow->y - boxShadow->blur, 0);

        return 0;

    }

    return m_overflowTop;

}

IntRect RenderBlock::overflowRect(bool includeInterior) const

{

    if (!includeInterior && hasOverflowClip()) {

        IntRect box = borderBox();

        if (ShadowData* boxShadow = style()->boxShadow()) {

            int shadowLeft = min(boxShadow->x - boxShadow->blur, 0);

            int shadowRight = max(boxShadow->x + boxShadow->blur, 0);

            int shadowTop = min(boxShadow->y - boxShadow->blur, 0);

            int shadowBottom = max(boxShadow->y + boxShadow->blur, 0);

            box.move(shadowLeft, shadowTop);

            box.setWidth(box.width() - shadowLeft + shadowRight);

            box.setHeight(box.height() - shadowTop + shadowBottom);

        }

        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 = checkForRepaintDuringLayout();

    if (checkForRepaint) {

        oldBounds = absoluteClippedOverflowRect();

        oldOutlineBox = absoluteOutlineBox();

    }