/*

 * Copyright (C) 2000 Lars Knoll (knoll@kde.org)

 * Copyright (C) 2003, 2004, 2006, 2007, 2008, 2009, 2010 Apple Inc. All right reserved.

 * Copyright (C) 2010 Google 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 "BidiResolver.h"

#include "CharacterNames.h"

#include "Hyphenation.h"

#include "InlineIterator.h"

#include "InlineTextBox.h"

#include "Logging.h"

#include "RenderArena.h"

#include "RenderInline.h"

#include "RenderLayer.h"

#include "RenderListMarker.h"

#include "RenderView.h"

#include "TrailingFloatsRootInlineBox.h"

#include "break_lines.h"

#include <wtf/AlwaysInline.h>

#include <wtf/RefCountedLeakCounter.h>

#include <wtf/StdLibExtras.h>

#include <wtf/Vector.h>

#if ENABLE(SVG)

#include "SVGRootInlineBox.h"

#endif

using namespace std;

using namespace WTF;

using namespace Unicode;

namespace WebCore {

// We don't let our line box tree for a single line get any deeper than this.

const unsigned cMaxLineDepth = 200;

static int getBorderPaddingMargin(RenderBoxModelObject* child, bool endOfInline)

{

    bool leftSide = (child->style()->direction() == LTR) ? !endOfInline : endOfInline;

    if (leftSide)

        return child->marginLeft() + child->paddingLeft() + child->borderLeft();

    return child->marginRight() + child->paddingRight() + child->borderRight();

}

static int inlineWidth(RenderObject* child, bool start = true, bool end = true)

{

    unsigned lineDepth = 1;

    int extraWidth = 0;

    RenderObject* parent = child->parent();

    while (parent->isInline() && !parent->isInlineBlockOrInlineTable() && lineDepth++ < cMaxLineDepth) {

        if (start && !child->previousSibling())

            extraWidth += getBorderPaddingMargin(toRenderBoxModelObject(parent), false);

        if (end && !child->nextSibling())

            extraWidth += getBorderPaddingMargin(toRenderBoxModelObject(parent), true);

        child = parent;

        parent = child->parent();

    }

    return extraWidth;

}

static void chopMidpointsAt(LineMidpointState& lineMidpointState, RenderObject* obj, unsigned pos)

{

    if (!lineMidpointState.numMidpoints)

        return;

    InlineIterator* midpoints = lineMidpointState.midpoints.data();

    for (int i = lineMidpointState.numMidpoints - 1; i >= 0; i--) {

        const InlineIterator& point = midpoints[i];

        if (point.obj == obj && point.pos == pos) {

            lineMidpointState.numMidpoints = i;

            break;

        }

    }

}

static void checkMidpoints(LineMidpointState& lineMidpointState, InlineIterator& lBreak)

{

    // Check to see if our last midpoint is a start point beyond the line break.  If so,

    // shave it off the list, and shave off a trailing space if the previous end point doesn't

    // preserve whitespace.

    if (lBreak.obj && lineMidpointState.numMidpoints && !(lineMidpointState.numMidpoints % 2)) {

        InlineIterator* midpoints = lineMidpointState.midpoints.data();

        InlineIterator& endpoint = midpoints[lineMidpointState.numMidpoints - 2];

        const InlineIterator& startpoint = midpoints[lineMidpointState.numMidpoints - 1];

        InlineIterator currpoint = endpoint;

        while (!currpoint.atEnd() && currpoint != startpoint && currpoint != lBreak)

            currpoint.increment();

        if (currpoint == lBreak) {

            // We hit the line break before the start point.  Shave off the start point.

            lineMidpointState.numMidpoints--;

            if (endpoint.obj->style()->collapseWhiteSpace()) {

                if (endpoint.obj->isText()) {

                    // Don't shave a character off the endpoint if it was from a soft hyphen.

                    RenderText* textObj = toRenderText(endpoint.obj);

                    if (endpoint.pos + 1 < textObj->textLength()) {

                        if (textObj->characters()[endpoint.pos+1] == softHyphen)

                            return;

                    } else if (startpoint.obj->isText()) {

                        RenderText *startText = toRenderText(startpoint.obj);

                        if (startText->textLength() && startText->characters()[0] == softHyphen)

                            return;

                    }

                }

                endpoint.pos--;

            }

        }

    }    

}

static void addMidpoint(LineMidpointState& lineMidpointState, const InlineIterator& midpoint)

{

    if (lineMidpointState.midpoints.size() <= lineMidpointState.numMidpoints)

        lineMidpointState.midpoints.grow(lineMidpointState.numMidpoints + 10);

    InlineIterator* midpoints = lineMidpointState.midpoints.data();

    midpoints[lineMidpointState.numMidpoints++] = midpoint;

}

void RenderBlock::appendRunsForObject(int start, int end, RenderObject* obj, InlineBidiResolver& resolver)

{

    if (start > end || obj->isFloating() ||

        (obj->isPositioned() && !obj->style()->hasStaticX() && !obj->style()->hasStaticY() && !obj->container()->isRenderInline()))

        return;

    LineMidpointState& lineMidpointState = resolver.midpointState();

    bool haveNextMidpoint = (lineMidpointState.currentMidpoint < lineMidpointState.numMidpoints);

    InlineIterator nextMidpoint;

    if (haveNextMidpoint)

        nextMidpoint = lineMidpointState.midpoints[lineMidpointState.currentMidpoint];

    if (lineMidpointState.betweenMidpoints) {

        if (!(haveNextMidpoint && nextMidpoint.obj == obj))

            return;

        // This is a new start point. Stop ignoring objects and 

        // adjust our start.

        lineMidpointState.betweenMidpoints = false;

        start = nextMidpoint.pos;

        lineMidpointState.currentMidpoint++;

        if (start < end)

            return appendRunsForObject(start, end, obj, resolver);

    } else {

        if (!haveNextMidpoint || (obj != nextMidpoint.obj)) {

            resolver.addRun(new (obj->renderArena()) BidiRun(start, end, obj, resolver.context(), resolver.dir()));

            return;

        }

        // An end midpoint has been encountered within our object.  We

        // need to go ahead and append a run with our endpoint.

        if (static_cast<int>(nextMidpoint.pos + 1) <= end) {

            lineMidpointState.betweenMidpoints = true;

            lineMidpointState.currentMidpoint++;

            if (nextMidpoint.pos != UINT_MAX) { // UINT_MAX means stop at the object and don't include any of it.

                if (static_cast<int>(nextMidpoint.pos + 1) > start)

                    resolver.addRun(new (obj->renderArena())

                        BidiRun(start, nextMidpoint.pos + 1, obj, resolver.context(), resolver.dir()));

                return appendRunsForObject(nextMidpoint.pos + 1, end, obj, resolver);

            }

        } else

           resolver.addRun(new (obj->renderArena()) BidiRun(start, end, obj, resolver.context(), resolver.dir()));

    }

}

static inline InlineBox* createInlineBoxForRenderer(RenderObject* obj, bool isRootLineBox, bool isOnlyRun = false)

{

    if (isRootLineBox)

        return toRenderBlock(obj)->createAndAppendRootInlineBox();

    if (obj->isText()) {

        InlineTextBox* textBox = toRenderText(obj)->createInlineTextBox();

        // We only treat a box as text for a <br> if we are on a line by ourself or in strict mode

        // (Note the use of strict mode.  In "almost strict" mode, we don't treat the box for <br> as text.)

        if (obj->isBR())

            textBox->setIsText(isOnlyRun || obj->document()->inStrictMode());

        return textBox;

    }

    if (obj->isBox())

        return toRenderBox(obj)->createInlineBox();

    return toRenderInline(obj)->createAndAppendInlineFlowBox();

}

static inline void dirtyLineBoxesForRenderer(RenderObject* o, bool fullLayout)

{

    if (o->isText()) {

        if (o->prefWidthsDirty() && o->isCounter())

            toRenderText(o)->calcPrefWidths(0); // FIXME: Counters depend on this hack. No clue why. Should be investigated and removed.

        toRenderText(o)->dirtyLineBoxes(fullLayout);

    } else

        toRenderInline(o)->dirtyLineBoxes(fullLayout);

}

InlineFlowBox* RenderBlock::createLineBoxes(RenderObject* obj, bool firstLine)

{

    // See if we have an unconstructed line box for this object that is also

    // the last item on the line.

    unsigned lineDepth = 1;

    InlineFlowBox* childBox = 0;

    InlineFlowBox* parentBox = 0;

    InlineFlowBox* result = 0;

    do {

        ASSERT(obj->isRenderInline() || obj == this);

        // Get the last box we made for this render object.

        parentBox = obj->isRenderInline() ? toRenderInline(obj)->lastLineBox() : toRenderBlock(obj)->lastLineBox();

        // If this box is constructed then it is from a previous line, and we need

        // to make a new box for our line.  If this box is unconstructed but it has

        // something following it on the line, then we know we have to make a new box

        // as well.  In this situation our inline has actually been split in two on

        // the same line (this can happen with very fancy language mixtures).

        bool constructedNewBox = false;

        if (!parentBox || parentBox->isConstructed() || parentBox->nextOnLine()) {

            // We need to make a new box for this render object.  Once

            // made, we need to place it at the end of the current line.

            InlineBox* newBox = createInlineBoxForRenderer(obj, obj == this);

            ASSERT(newBox->isInlineFlowBox());

            parentBox = static_cast<InlineFlowBox*>(newBox);

            parentBox->setFirstLineStyleBit(firstLine);

            constructedNewBox = true;

        }

        if (!result)

            result = parentBox;

        // If we have hit the block itself, then |box| represents the root

        // inline box for the line, and it doesn't have to be appended to any parent

        // inline.

        if (childBox)

            parentBox->addToLine(childBox);

        if (!constructedNewBox || obj == this)

            break;

        childBox = parentBox;        

        // If we've exceeded our line depth, then jump straight to the root and skip all the remaining

        // intermediate inline flows.

        obj = (++lineDepth >= cMaxLineDepth) ? this : obj->parent();

    } while (true);

    return result;

}

RootInlineBox* RenderBlock::constructLine(unsigned runCount, BidiRun* firstRun, BidiRun* lastRun, bool firstLine, bool lastLine, RenderObject* endObject)

{

    ASSERT(firstRun);

    InlineFlowBox* parentBox = 0;

    for (BidiRun* r = firstRun; r; r = r->next()) {

        // Create a box for our object.

        bool isOnlyRun = (runCount == 1);

        if (runCount == 2 && !r->m_object->isListMarker())

            isOnlyRun = ((style()->direction() == RTL) ? lastRun : firstRun)->m_object->isListMarker();

        InlineBox* box = createInlineBoxForRenderer(r->m_object, false, isOnlyRun);

        r->m_box = box;

        ASSERT(box);

        if (!box)

            continue;

        // If we have no parent box yet, or if the run is not simply a sibling,

        // then we need to construct inline boxes as necessary to properly enclose the

        // run's inline box.

        if (!parentBox || parentBox->renderer() != r->m_object->parent())

            // Create new inline boxes all the way back to the appropriate insertion point.

            parentBox = createLineBoxes(r->m_object->parent(), firstLine);

        // Append the inline box to this line.

        parentBox->addToLine(box);

        bool visuallyOrdered = r->m_object->style()->visuallyOrdered();

        box->setBidiLevel(visuallyOrdered ? 0 : r->level());

        if (box->isInlineTextBox()) {

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

            text->setStart(r->m_start);

            text->setLen(r->m_stop - r->m_start);

            text->m_dirOverride = r->dirOverride(visuallyOrdered);

            if (r->m_hasHyphen)

                text->setHasHyphen(true);

        }

    }

    // We should have a root inline box.  It should be unconstructed and

    // be the last continuation of our line list.

    ASSERT(lastLineBox() && !lastLineBox()->isConstructed());

    // Set bits on our inline flow boxes that indicate which sides should

    // paint borders/margins/padding.  This knowledge will ultimately be used when

    // we determine the horizontal positions and widths of all the inline boxes on

    // the line.

    lastLineBox()->determineSpacingForFlowBoxes(lastLine, endObject);

    // Now mark the line boxes as being constructed.

    lastLineBox()->setConstructed();

    // Return the last line.

    return lastRootBox();

}

void RenderBlock::computeHorizontalPositionsForLine(RootInlineBox* lineBox, bool firstLine, BidiRun* firstRun, BidiRun* trailingSpaceRun, bool reachedEnd, GlyphOverflowAndFallbackFontsMap& textBoxDataMap)

{

    // First determine our total width.

    int availableWidth = lineWidth(height(), firstLine);

    int totWidth = lineBox->getFlowSpacingWidth();

    bool needsWordSpacing = false;

    unsigned numSpaces = 0;

    ETextAlign textAlign = style()->textAlign();

    for (BidiRun* r = firstRun; r; r = r->next()) {

        if (!r->m_box || r->m_object->isPositioned() || r->m_box->isLineBreak())

            continue; // Positioned objects are only participating to figure out their

                      // correct static x position.  They have no effect on the width.

                      // Similarly, line break boxes have no effect on the width.

        if (r->m_object->isText()) {

            RenderText* rt = toRenderText(r->m_object);

            if (textAlign == JUSTIFY && r != trailingSpaceRun) {

                const UChar* characters = rt->characters();

                for (int i = r->m_start; i < r->m_stop; i++) {

                    UChar c = characters[i];

                    if (c == ' ' || c == '\n' || c == '\t')

                        numSpaces++;

                }

            }

            if (int length = rt->textLength()) {

                if (!r->m_start && needsWordSpacing && isSpaceOrNewline(rt->characters()[r->m_start]))

                    totWidth += rt->style(firstLine)->font().wordSpacing();

                needsWordSpacing = !isSpaceOrNewline(rt->characters()[r->m_stop - 1]) && r->m_stop == length;          

            }

            HashSet<const SimpleFontData*> fallbackFonts;

            GlyphOverflow glyphOverflow;

            int hyphenWidth = 0;

            if (static_cast<InlineTextBox*>(r->m_box)->hasHyphen()) {

                const AtomicString& hyphenString = rt->style()->hyphenString();

                hyphenWidth = rt->style(firstLine)->font().width(TextRun(hyphenString.characters(), hyphenString.length()));

            }

            r->m_box->setWidth(rt->width(r->m_start, r->m_stop - r->m_start, totWidth, firstLine, &fallbackFonts, &glyphOverflow) + hyphenWidth);

            if (!fallbackFonts.isEmpty()) {

                ASSERT(r->m_box->isText());

                GlyphOverflowAndFallbackFontsMap::iterator it = textBoxDataMap.add(static_cast<InlineTextBox*>(r->m_box), make_pair(Vector<const SimpleFontData*>(), GlyphOverflow())).first;

                ASSERT(it->second.first.isEmpty());

                copyToVector(fallbackFonts, it->second.first);

            }

            if ((glyphOverflow.top || glyphOverflow.bottom || glyphOverflow.left || glyphOverflow.right)) {

                ASSERT(r->m_box->isText());

                GlyphOverflowAndFallbackFontsMap::iterator it = textBoxDataMap.add(static_cast<InlineTextBox*>(r->m_box), make_pair(Vector<const SimpleFontData*>(), GlyphOverflow())).first;

                it->second.second = glyphOverflow;

            }

        } else if (!r->m_object->isRenderInline()) {

            RenderBox* renderBox = toRenderBox(r->m_object);

            renderBox->calcWidth();

            r->m_box->setWidth(renderBox->width());

            totWidth += renderBox->marginLeft() + renderBox->marginRight();

        }

        totWidth += r->m_box->width();

    }

    // Armed with the total width of the line (without justification),

    // we now examine our text-align property in order to determine where to position the

    // objects horizontally.  The total width of the line can be increased if we end up

    // justifying text.

    int x = leftOffset(height(), firstLine);

    switch (textAlign) {

        case LEFT:

        case WEBKIT_LEFT:

            // The direction of the block should determine what happens with wide lines.  In

            // particular with RTL blocks, wide lines should still spill out to the left.

            if (style()->direction() == LTR) {

                if (totWidth > availableWidth && trailingSpaceRun)

                    trailingSpaceRun->m_box->setWidth(max(0, trailingSpaceRun->m_box->width() - totWidth + availableWidth));

            } else {

                if (trailingSpaceRun)

                    trailingSpaceRun->m_box->setWidth(0);

                else if (totWidth > availableWidth)

                    x -= (totWidth - availableWidth);

            }

            break;

        case JUSTIFY:

            if (numSpaces && !reachedEnd && !lineBox->endsWithBreak()) {

                if (trailingSpaceRun) {

                    totWidth -= trailingSpaceRun->m_box->width();

                    trailingSpaceRun->m_box->setWidth(0);

                }

                break;

            }

            // fall through

        case TAAUTO:

            numSpaces = 0;

            // for right to left fall through to right aligned

            if (style()->direction() == LTR) {

                if (totWidth > availableWidth && trailingSpaceRun)

                    trailingSpaceRun->m_box->setWidth(max(0, trailingSpaceRun->m_box->width() - totWidth + availableWidth));

                break;

            }

        case RIGHT:

        case WEBKIT_RIGHT:

            // Wide lines spill out of the block based off direction.

            // So even if text-align is right, if direction is LTR, wide lines should overflow out of the right

            // side of the block.

            if (style()->direction() == LTR) {

                if (trailingSpaceRun) {

                    totWidth -= trailingSpaceRun->m_box->width();

                    trailingSpaceRun->m_box->setWidth(0);

                }

                if (totWidth < availableWidth)

                    x += availableWidth - totWidth;

            } else {

                if (totWidth > availableWidth && trailingSpaceRun) {

                    trailingSpaceRun->m_box->setWidth(max(0, trailingSpaceRun->m_box->width() - totWidth + availableWidth));

                    totWidth -= trailingSpaceRun->m_box->width();

                } else

                    x += availableWidth - totWidth;

            }

            break;

        case CENTER:

        case WEBKIT_CENTER:

            int trailingSpaceWidth = 0;

            if (trailingSpaceRun) {

                totWidth -= trailingSpaceRun->m_box->width();

                trailingSpaceWidth = min(trailingSpaceRun->m_box->width(), (availableWidth - totWidth + 1) / 2);

                trailingSpaceRun->m_box->setWidth(max(0, trailingSpaceWidth));

            }

            if (style()->direction() == LTR)

                x += max((availableWidth - totWidth) / 2, 0);

            else

                x += totWidth > availableWidth ? (availableWidth - totWidth) : (availableWidth - totWidth) / 2 - trailingSpaceWidth;

            break;

    }

    if (numSpaces) {

        for (BidiRun* r = firstRun; r; r = r->next()) {

            if (!r->m_box || r == trailingSpaceRun)

                continue;

            int spaceAdd = 0;

            if (r->m_object->isText()) {

                unsigned spaces = 0;

                const UChar* characters = toRenderText(r->m_object)->characters();

                for (int i = r->m_start; i < r->m_stop; i++) {

                    UChar c = characters[i];

                    if (c == ' ' || c == '\n' || c == '\t')

                        spaces++;

                }

                ASSERT(spaces <= numSpaces);

                // Only justify text if whitespace is collapsed.

                if (r->m_object->style()->collapseWhiteSpace()) {

                    spaceAdd = (availableWidth - totWidth) * spaces / numSpaces;

                    static_cast<InlineTextBox*>(r->m_box)->setSpaceAdd(spaceAdd);

                    totWidth += spaceAdd;

                }

                numSpaces -= spaces;

                if (!numSpaces)

                    break;

            }

        }

    }

    // The widths of all runs are now known.  We can now place every inline box (and

    // compute accurate widths for the inline flow boxes).

    needsWordSpacing = false;

    lineBox->placeBoxesHorizontally(x, needsWordSpacing, textBoxDataMap);

}

void RenderBlock::computeVerticalPositionsForLine(RootInlineBox* lineBox, BidiRun* firstRun, GlyphOverflowAndFallbackFontsMap& textBoxDataMap)

{

    setHeight(lineBox->verticallyAlignBoxes(height(), textBoxDataMap));

    lineBox->setBlockHeight(height());

    // Now make sure we place replaced render objects correctly.

    for (BidiRun* r = firstRun; r; r = r->next()) {

        ASSERT(r->m_box);

        if (!r->m_box)

            continue; // Skip runs with no line boxes.

        // Align positioned boxes with the top of the line box.  This is

        // a reasonable approximation of an appropriate y position.

        if (r->m_object->isPositioned())

            r->m_box->setY(height());

        // Position is used to properly position both replaced elements and

        // to update the static normal flow x/y of positioned elements.

        if (r->m_object->isText())

            toRenderText(r->m_object)->positionLineBox(r->m_box);

        else if (r->m_object->isBox())

            toRenderBox(r->m_object)->positionLineBox(r->m_box);

    }

    // Positioned objects and zero-length text nodes destroy their boxes in

    // position(), which unnecessarily dirties the line.

    lineBox->markDirty(false);

}

static inline bool isCollapsibleSpace(UChar character, RenderText* renderer)

{

    if (character == ' ' || character == '\t' || character == softHyphen)

        return true;

    if (character == '\n')

        return !renderer->style()->preserveNewline();

    if (character == noBreakSpace)

        return renderer->style()->nbspMode() == SPACE;

    return false;

}

void RenderBlock::layoutInlineChildren(bool relayoutChildren, int& repaintTop, int& repaintBottom)