/*

 * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 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 "InlineFlowBox.h"

#include "CachedImage.h"

#include "CSSPropertyNames.h"

#include "Document.h"

#include "EllipsisBox.h"

#include "GraphicsContext.h"

#include "InlineTextBox.h"

#include "HitTestResult.h"

#include "RootInlineBox.h"

#include "RenderBlock.h"

#include "RenderInline.h"

#include "RenderLayer.h"

#include "RenderListMarker.h"

#include "RenderTableCell.h"

#include "RootInlineBox.h"

#include "Text.h"

#include <math.h>

using namespace std;

namespace WebCore {

#ifndef NDEBUG

InlineFlowBox::~InlineFlowBox()

{

    if (!m_hasBadChildList)

        for (InlineBox* child = firstChild(); child; child = child->nextOnLine())

            child->setHasBadParent();

}

#endif

int InlineFlowBox::getFlowSpacingWidth()

{

    int totWidth = marginBorderPaddingLeft() + marginBorderPaddingRight();

    for (InlineBox* curr = firstChild(); curr; curr = curr->nextOnLine()) {

        if (curr->isInlineFlowBox())

            totWidth += static_cast<InlineFlowBox*>(curr)->getFlowSpacingWidth();

    }

    return totWidth;

}

void InlineFlowBox::addToLine(InlineBox* child) 

{

    ASSERT(!child->parent());

    ASSERT(!child->nextOnLine());

    ASSERT(!child->prevOnLine());

    checkConsistency();

    child->setParent(this);

    if (!m_firstChild) {

        m_firstChild = child;

        m_lastChild = child;

    } else {

        m_lastChild->setNextOnLine(child);

        child->setPrevOnLine(m_lastChild);

        m_lastChild = child;

    }

    child->setFirstLineStyleBit(m_firstLine);

    if (child->isText())

        m_hasTextChildren = true;

    if (child->renderer()->selectionState() != RenderObject::SelectionNone)

        root()->setHasSelectedChildren(true);

    checkConsistency();

}

void InlineFlowBox::removeChild(InlineBox* child)

{

    checkConsistency();

    if (!m_dirty)

        dirtyLineBoxes();

    root()->childRemoved(child);

    if (child == m_firstChild)

        m_firstChild = child->nextOnLine();

    if (child == m_lastChild)

        m_lastChild = child->prevOnLine();

    if (child->nextOnLine())

        child->nextOnLine()->setPrevOnLine(child->prevOnLine());

    if (child->prevOnLine())

        child->prevOnLine()->setNextOnLine(child->nextOnLine());

    child->setParent(0);

    checkConsistency();

}

void InlineFlowBox::deleteLine(RenderArena* arena)

{

    InlineBox* child = firstChild();

    InlineBox* next = 0;

    while (child) {

        ASSERT(this == child->parent());

        next = child->nextOnLine();

#ifndef NDEBUG

        child->setParent(0);

#endif

        child->deleteLine(arena);

        child = next;

    }

#ifndef NDEBUG

    m_firstChild = 0;

    m_lastChild = 0;

#endif

    removeLineBoxFromRenderObject();

    destroy(arena);

}

void InlineFlowBox::removeLineBoxFromRenderObject()

{

    toRenderInline(renderer())->lineBoxes()->removeLineBox(this);

}

void InlineFlowBox::extractLine()

{

    if (!m_extracted)

        extractLineBoxFromRenderObject();

    for (InlineBox* child = firstChild(); child; child = child->nextOnLine())

        child->extractLine();

}

void InlineFlowBox::extractLineBoxFromRenderObject()

{

    toRenderInline(renderer())->lineBoxes()->extractLineBox(this);

}

void InlineFlowBox::attachLine()

{

    if (m_extracted)

        attachLineBoxToRenderObject();

    for (InlineBox* child = firstChild(); child; child = child->nextOnLine())

        child->attachLine();

}

void InlineFlowBox::attachLineBoxToRenderObject()

{

    toRenderInline(renderer())->lineBoxes()->attachLineBox(this);

}

void InlineFlowBox::adjustPosition(int dx, int dy)

{

    InlineBox::adjustPosition(dx, dy);

    for (InlineBox* child = firstChild(); child; child = child->nextOnLine())

        child->adjustPosition(dx, dy);

    if (m_overflow)

        m_overflow->move(dx, dy);

}

RenderLineBoxList* InlineFlowBox::rendererLineBoxes() const

{

    return toRenderInline(renderer())->lineBoxes();

}

bool InlineFlowBox::onEndChain(RenderObject* endObject)

{

    if (!endObject)

        return false;

    if (endObject == renderer())

        return true;

    RenderObject* curr = endObject;

    RenderObject* parent = curr->parent();

    while (parent && !parent->isRenderBlock()) {

        if (parent->lastChild() != curr || parent == renderer())

            return false;

        curr = parent;

        parent = curr->parent();

    }

    return true;

}

void InlineFlowBox::determineSpacingForFlowBoxes(bool lastLine, RenderObject* endObject)

{

    // All boxes start off open.  They will not apply any margins/border/padding on

    // any side.

    bool includeLeftEdge = false;

    bool includeRightEdge = false;

    // The root inline box never has borders/margins/padding.

    if (parent()) {

        bool ltr = renderer()->style()->direction() == LTR;

        // Check to see if all initial lines are unconstructed.  If so, then

        // we know the inline began on this line (unless we are a continuation).

        RenderLineBoxList* lineBoxList = rendererLineBoxes();

        if (!lineBoxList->firstLineBox()->isConstructed() && !renderer()->isInlineElementContinuation()) {

            if (ltr && lineBoxList->firstLineBox() == this)

                includeLeftEdge = true;

            else if (!ltr && lineBoxList->lastLineBox() == this)

                includeRightEdge = true;

        }

        // In order to determine if the inline ends on this line, we check three things:

        // (1) If we are the last line and we don't have a continuation(), then we can

        // close up.

        // (2) If the last line box for the flow has an object following it on the line (ltr,

        // reverse for rtl), then the inline has closed.

        // (3) The line may end on the inline.  If we are the last child (climbing up

        // the end object's chain), then we just closed as well.

        if (!lineBoxList->lastLineBox()->isConstructed()) {

            RenderInline* inlineFlow = toRenderInline(renderer());

            if (ltr) {

                if (!nextLineBox() &&

                    ((lastLine && !inlineFlow->continuation()) || nextOnLineExists() || onEndChain(endObject)))

                    includeRightEdge = true;

            } else {

                if ((!prevLineBox() || prevLineBox()->isConstructed()) &&

                    ((lastLine && !inlineFlow->continuation()) || prevOnLineExists() || onEndChain(endObject)))

                    includeLeftEdge = true;

            }

        }

    }

    setEdges(includeLeftEdge, includeRightEdge);

    // Recur into our children.

    for (InlineBox* currChild = firstChild(); currChild; currChild = currChild->nextOnLine()) {

        if (currChild->isInlineFlowBox()) {

            InlineFlowBox* currFlow = static_cast<InlineFlowBox*>(currChild);

            currFlow->determineSpacingForFlowBoxes(lastLine, endObject);

        }

    }

}

int InlineFlowBox::placeBoxesHorizontally(int xPos, bool& needsWordSpacing, GlyphOverflowAndFallbackFontsMap& textBoxDataMap)

{

    // Set our x position.

    setX(xPos);

    int leftLayoutOverflow = xPos;

    int rightLayoutOverflow = xPos;

    int leftVisualOverflow = xPos;

    int rightVisualOverflow = xPos;

    int boxShadowLeft;

    int boxShadowRight;

    renderer()->style(m_firstLine)->getBoxShadowHorizontalExtent(boxShadowLeft, boxShadowRight);

    leftVisualOverflow = min(xPos + boxShadowLeft, leftVisualOverflow);

    int startX = xPos;

    xPos += borderLeft() + paddingLeft();

    for (InlineBox* curr = firstChild(); curr; curr = curr->nextOnLine()) {

        if (curr->renderer()->isText()) {

            InlineTextBox* text = static_cast<InlineTextBox*>(curr);

            RenderText* rt = toRenderText(text->renderer());

            if (rt->textLength()) {

                if (needsWordSpacing && isSpaceOrNewline(rt->characters()[text->start()]))

                    xPos += rt->style(m_firstLine)->font().wordSpacing();

                needsWordSpacing = !isSpaceOrNewline(rt->characters()[text->end()]);

            }

            text->setX(xPos);

            int strokeOverflow = static_cast<int>(ceilf(rt->style()->textStrokeWidth() / 2.0f));

            // If letter-spacing is negative, we should factor that into right layout overflow. (Even in RTL, letter-spacing is

            // applied to the right, so this is not an issue with left overflow.

            int letterSpacing = min(0, (int)rt->style(m_firstLine)->font().letterSpacing());

            rightLayoutOverflow = max(xPos + text->width() - letterSpacing, rightLayoutOverflow);

            GlyphOverflowAndFallbackFontsMap::iterator it = textBoxDataMap.find(static_cast<InlineTextBox*>(curr));

            GlyphOverflow* glyphOverflow = it == textBoxDataMap.end() ? 0 : &it->second.second;

            int leftGlyphOverflow = -strokeOverflow - (glyphOverflow ? glyphOverflow->left : 0);

            int rightGlyphOverflow = strokeOverflow - letterSpacing + (glyphOverflow ? glyphOverflow->right : 0);

            int childOverflowLeft = leftGlyphOverflow;

            int childOverflowRight = rightGlyphOverflow;

            for (const ShadowData* shadow = rt->style()->textShadow(); shadow; shadow = shadow->next()) {

                childOverflowLeft = min(childOverflowLeft, shadow->x() - shadow->blur() + leftGlyphOverflow);

                childOverflowRight = max(childOverflowRight, shadow->x() + shadow->blur() + rightGlyphOverflow);

            }

            leftVisualOverflow = min(xPos + childOverflowLeft, leftVisualOverflow);

            rightVisualOverflow = max(xPos + text->width() + childOverflowRight, rightVisualOverflow);

            xPos += text->width();

        } else {

            if (curr->renderer()->isPositioned()) {

                if (curr->renderer()->parent()->style()->direction() == LTR)

                    curr->setX(xPos);

                else

                    // Our offset that we cache needs to be from the edge of the right border box and

                    // not the left border box.  We have to subtract |x| from the width of the block

                    // (which can be obtained from the root line box).

                    curr->setX(root()->block()->width() - xPos);

                continue; // The positioned object has no effect on the width.

            }

            if (curr->renderer()->isRenderInline()) {

                InlineFlowBox* flow = static_cast<InlineFlowBox*>(curr);

                xPos += flow->marginLeft();

                xPos = flow->placeBoxesHorizontally(xPos, needsWordSpacing, textBoxDataMap);

                xPos += flow->marginRight();

                leftLayoutOverflow = min(leftLayoutOverflow, flow->leftLayoutOverflow());

                rightLayoutOverflow = max(rightLayoutOverflow, flow->rightLayoutOverflow());

                leftVisualOverflow = min(leftVisualOverflow, flow->leftVisualOverflow());

                rightVisualOverflow = max(rightVisualOverflow, flow->rightVisualOverflow());

            } else if (!curr->renderer()->isListMarker() || toRenderListMarker(curr->renderer())->isInside()) {

                xPos += curr->boxModelObject()->marginLeft();

                curr->setX(xPos);

                RenderBox* box = toRenderBox(curr->renderer());

                int childLeftOverflow = box->hasOverflowClip() ? 0 : box->leftLayoutOverflow();

                int childRightOverflow = box->hasOverflowClip() ? curr->width() : box->rightLayoutOverflow();

                leftLayoutOverflow = min(xPos + childLeftOverflow, leftLayoutOverflow);

                rightLayoutOverflow = max(xPos + childRightOverflow, rightLayoutOverflow);

                leftVisualOverflow = min(xPos + box->leftVisualOverflow(), leftVisualOverflow);

                rightVisualOverflow = max(xPos + box->rightVisualOverflow(), rightVisualOverflow);

                xPos += curr->width() + curr->boxModelObject()->marginRight();

            }

        }

    }

    xPos += borderRight() + paddingRight();

    setWidth(xPos - startX);

    rightVisualOverflow = max(x() + width() + boxShadowRight, rightVisualOverflow);

    rightLayoutOverflow = max(x() + width(), rightLayoutOverflow);

    setHorizontalOverflowPositions(leftLayoutOverflow, rightLayoutOverflow, leftVisualOverflow, rightVisualOverflow);

    return xPos;

}

void InlineFlowBox::adjustMaxAscentAndDescent(int& maxAscent, int& maxDescent,

                                              int maxPositionTop, int maxPositionBottom)

{

    for (InlineBox* curr = firstChild(); curr; curr = curr->nextOnLine()) {

        // The computed lineheight needs to be extended for the

        // positioned elements

        if (curr->renderer()->isPositioned())

            continue; // Positioned placeholders don't affect calculations.

        if (curr->y() == PositionTop || curr->y() == PositionBottom) {

            int lineHeight = curr->lineHeight(false);

            if (curr->y() == PositionTop) {

                if (maxAscent + maxDescent < lineHeight)

                    maxDescent = lineHeight - maxAscent;

            }

            else {

                if (maxAscent + maxDescent < lineHeight)

                    maxAscent = lineHeight - maxDescent;

            }

            if (maxAscent + maxDescent >= max(maxPositionTop, maxPositionBottom))

                break;

        }

        if (curr->isInlineFlowBox())

            static_cast<InlineFlowBox*>(curr)->adjustMaxAscentAndDescent(maxAscent, maxDescent, maxPositionTop, maxPositionBottom);

    }

}

static int verticalPositionForBox(InlineBox* curr, bool firstLine)

{

    if (curr->renderer()->isText())

        return curr->parent()->y();

    if (curr->renderer()->isBox())

        return toRenderBox(curr->renderer())->verticalPosition(firstLine);

    return toRenderInline(curr->renderer())->verticalPositionFromCache(firstLine);

}

void InlineFlowBox::computeLogicalBoxHeights(int& maxPositionTop, int& maxPositionBottom,

                                             int& maxAscent, int& maxDescent, bool strictMode, GlyphOverflowAndFallbackFontsMap& textBoxDataMap)

{

    if (isRootInlineBox()) {

        // Examine our root box.

        int height = lineHeight(true);

        int baseline = baselinePosition(true);

        if (hasTextChildren() || strictMode) {

            int ascent = baseline;

            int descent = height - ascent;

            if (maxAscent < ascent)

                maxAscent = ascent;

            if (maxDescent < descent)

                maxDescent = descent;

        }

    }

    for (InlineBox* curr = firstChild(); curr; curr = curr->nextOnLine()) {

        if (curr->renderer()->isPositioned())

            continue; // Positioned placeholders don't affect calculations.

        bool isInlineFlow = curr->isInlineFlowBox();

        int lineHeight;

        int baseline;

        Vector<const SimpleFontData*>* usedFonts = 0;

        if (curr->isInlineTextBox()) {

            GlyphOverflowAndFallbackFontsMap::iterator it = textBoxDataMap.find(static_cast<InlineTextBox*>(curr));

            usedFonts = it == textBoxDataMap.end() ? 0 : &it->second.first;

        }

        if (usedFonts) {

            usedFonts->append(curr->renderer()->style(m_firstLine)->font().primaryFont());

            Length parentLineHeight = curr->renderer()->parent()->style()->lineHeight();

            if (parentLineHeight.isNegative()) {

                int baselineToBottom = 0;

                baseline = 0;

                for (size_t i = 0; i < usedFonts->size(); ++i) {

                    int halfLeading = (usedFonts->at(i)->lineSpacing() - usedFonts->at(i)->ascent() - usedFonts->at(i)->descent()) / 2;

                    baseline = max(baseline, halfLeading + usedFonts->at(i)->ascent());

                    baselineToBottom = max(baselineToBottom, usedFonts->at(i)->lineSpacing() - usedFonts->at(i)->ascent() - usedFonts->at(i)->descent() - halfLeading);

                }

                lineHeight = baseline + baselineToBottom;

            } else if (parentLineHeight.isPercent()) {

                lineHeight = parentLineHeight.calcMinValue(curr->renderer()->style()->fontSize());

                baseline = 0;

                for (size_t i = 0; i < usedFonts->size(); ++i) {

                    int halfLeading = (lineHeight - usedFonts->at(i)->ascent() - usedFonts->at(i)->descent()) / 2;

                    baseline = max(baseline, halfLeading + usedFonts->at(i)->ascent());

                }

            } else {

                lineHeight = parentLineHeight.value();

                baseline = 0;

                for (size_t i = 0; i < usedFonts->size(); ++i) {

                    int halfLeading = (lineHeight - usedFonts->at(i)->ascent() - usedFonts->at(i)->descent()) / 2;

                    baseline = max(baseline, halfLeading + usedFonts->at(i)->ascent());

                }

            }

        } else {

            lineHeight = curr->lineHeight(false);

            baseline = curr->baselinePosition(false);

        }

        curr->setY(verticalPositionForBox(curr, m_firstLine));

        if (curr->y() == PositionTop) {

            if (maxPositionTop < lineHeight)

                maxPositionTop = lineHeight;

        } else if (curr->y() == PositionBottom) {

            if (maxPositionBottom < lineHeight)

                maxPositionBottom = lineHeight;

        } else if ((!isInlineFlow || static_cast<InlineFlowBox*>(curr)->hasTextChildren()) || curr->boxModelObject()->hasHorizontalBordersOrPadding() || strictMode) {

            int ascent = baseline - curr->y();

            int descent = lineHeight - ascent;

            if (maxAscent < ascent)

                maxAscent = ascent;

            if (maxDescent < descent)

                maxDescent = descent;

        }

        if (curr->isInlineFlowBox())

            static_cast<InlineFlowBox*>(curr)->computeLogicalBoxHeights(maxPositionTop, maxPositionBottom, maxAscent, maxDescent, strictMode, textBoxDataMap);

    }

}

void InlineFlowBox::placeBoxesVertically(int yPos, int maxHeight, int maxAscent, bool strictMode, int& selectionTop, int& selectionBottom)

{

    if (isRootInlineBox())

        setY(yPos + maxAscent - baselinePosition(true)); // Place our root box.

    for (InlineBox* curr = firstChild(); curr; curr = curr->nextOnLine()) {

        if (curr->renderer()->isPositioned())

            continue; // Positioned placeholders don't affect calculations.

        // Adjust boxes to use their real box y/height and not the logical height (as dictated by

        // line-height).

        bool isInlineFlow = curr->isInlineFlowBox();

        if (isInlineFlow)

            static_cast<InlineFlowBox*>(curr)->placeBoxesVertically(yPos, maxHeight, maxAscent, strictMode, selectionTop, selectionBottom);

        bool childAffectsTopBottomPos = true;

        if (curr->y() == PositionTop)

            curr->setY(yPos);

        else if (curr->y() == PositionBottom)

            curr->setY(yPos + maxHeight - curr->lineHeight(false));

        else {

            if ((isInlineFlow && !static_cast<InlineFlowBox*>(curr)->hasTextChildren()) && !curr->boxModelObject()->hasHorizontalBordersOrPadding() && !strictMode)

                childAffectsTopBottomPos = false;

            int posAdjust = maxAscent - curr->baselinePosition(false);

            curr->setY(curr->y() + yPos + posAdjust);

        }

        int newY = curr->y();

        if (curr->isText() || curr->isInlineFlowBox()) {

            const Font& font = curr->renderer()->style(m_firstLine)->font();

            newY += curr->baselinePosition(false) - font.ascent();

            if (curr->isInlineFlowBox())

                newY -= curr->boxModelObject()->borderTop() + curr->boxModelObject()->paddingTop();

        } else if (!curr->renderer()->isBR()) {

            RenderBox* box = toRenderBox(curr->renderer());

            newY += box->marginTop();

        }

        curr->setY(newY);

        if (childAffectsTopBottomPos) {

            int boxHeight = curr->height();

            selectionTop = min(selectionTop, newY);

            selectionBottom = max(selectionBottom, newY + boxHeight);

        }

    }

    if (isRootInlineBox()) {

        const Font& font = renderer()->style(m_firstLine)->font();

        setY(y() + baselinePosition(true) - font.ascent());

        if (hasTextChildren() || strictMode) {

            selectionTop = min(selectionTop, y());