/*

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

 * Copyright (C) 2004, 2006, 2007 Apple Inc. All right 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 "bidi.h"

#include "CharacterNames.h"

#include "Document.h"

#include "Element.h"

#include "FrameView.h"

#include "InlineTextBox.h"

#include "Logging.h"

#include "RenderArena.h"

#include "RenderLayer.h"

#include "RenderListMarker.h"

#include "RenderView.h"

#include "break_lines.h"

#include <wtf/AlwaysInline.h>

#include <wtf/Vector.h>

#if PLATFORM(SYMBIAN)

#include "Frame.h"

#include "WebCoreFrameBridge.h"

#include "oom.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;

class BidiIterator {

public:

    BidiIterator()

        : block(0)

        , obj(0)

        , pos(0)

    {

    }

    BidiIterator(RenderBlock* b, RenderObject* o, unsigned p)

        : block(b)

        , obj(o)

        , pos(p)

    {

    }

    void increment(BidiResolver<BidiIterator, BidiRun>& state);

    bool atEnd() const;

    UChar current() const;

    WTF::Unicode::Direction direction() const;

    RenderBlock* block;

    RenderObject* obj;

    unsigned int pos;

};

// Used to track a list of chained bidi runs.

static BidiRun* sFirstBidiRun;

static BidiRun* sLastBidiRun;

static BidiRun* sLogicallyLastBidiRun;

static int sBidiRunCount;

// Midpoint globals.  The goal is not to do any allocation when dealing with

// these midpoints, so we just keep an array around and never clear it.  We track

// the number of items and position using the two other variables.

static Vector<BidiIterator>* smidpoints;

static unsigned sNumMidpoints;

static unsigned sCurrMidpoint;

static bool betweenMidpoints;

static bool isLineEmpty = true;

static bool previousLineBrokeCleanly = true;

static int numSpaces;

static int getBPMWidth(int childValue, Length cssUnit)

{

    if (!cssUnit.isIntrinsicOrAuto())

        return (cssUnit.isFixed() ? cssUnit.value() : childValue);

    return 0;

}

static int getBorderPaddingMargin(RenderObject* child, bool endOfInline)

{

    RenderStyle* cstyle = child->style();

    int result = 0;

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

    result += getBPMWidth((leftSide ? child->marginLeft() : child->marginRight()),

                          (leftSide ? cstyle->marginLeft() :

                           cstyle->marginRight()));

    result += getBPMWidth((leftSide ? child->paddingLeft() : child->paddingRight()),

                          (leftSide ? cstyle->paddingLeft() :

                           cstyle->paddingRight()));

    result += leftSide ? child->borderLeft() : child->borderRight();

    return result;

}

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 && parent->firstChild() == child)

            extraWidth += getBorderPaddingMargin(parent, false);

        if (end && parent->lastChild() == child)

            extraWidth += getBorderPaddingMargin(parent, true);

        child = parent;

        parent = child->parent();

    }

    return extraWidth;

}

#ifndef NDEBUG

WTFLogChannel LogWebCoreBidiRunLeaks =  { 0x00000000, "", WTFLogChannelOn };

struct BidiRunCounter { 

    static int count; 

    ~BidiRunCounter() 

    { 

        if (count)

            LOG(WebCoreBidiRunLeaks, "LEAK: %d BidiRun\n", count);

    }

};

int BidiRunCounter::count = 0;

static BidiRunCounter bidiRunCounter;

static bool inBidiRunDestroy;

#endif

void BidiRun::destroy(RenderArena* renderArena)

{

#ifndef NDEBUG

    inBidiRunDestroy = true;

#endif

    delete this;

#ifndef NDEBUG

    inBidiRunDestroy = false;

#endif

    // Recover the size left there for us by operator delete and free the memory.

    renderArena->free(*(size_t *)this, this);

}

void* BidiRun::operator new(size_t sz, RenderArena* renderArena) throw()

{

#ifndef NDEBUG

    ++BidiRunCounter::count;

#endif

    return renderArena->allocate(sz);

}

void BidiRun::operator delete(void* ptr, size_t sz)

{

#ifndef NDEBUG

    --BidiRunCounter::count;

#endif

    ASSERT(inBidiRunDestroy);

    // Stash size where destroy() can find it.

    *(size_t*)ptr = sz;

}

template <>

void BidiState::deleteRuns()

{

    emptyRun = true;

    if (!m_firstRun)

        return;

    BidiRun* curr = m_firstRun;

    while (curr) {

        BidiRun* s = curr->next();

        curr->destroy(curr->obj->renderArena());

        curr = s;

    }

    m_firstRun = 0;

    m_lastRun = 0;

    m_runCount = 0;

}

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

inline bool operator==(const BidiIterator& it1, const BidiIterator& it2)

{

    return it1.pos == it2.pos && it1.obj == it2.obj;

}

inline bool operator!=(const BidiIterator& it1, const BidiIterator& it2)

{

    return it1.pos != it2.pos || it1.obj != it2.obj;

}

static inline RenderObject* bidiNext(RenderBlock* block, RenderObject* current, BidiState& bidi,

                                     bool skipInlines = true, bool* endOfInline = 0)

{

    RenderObject* next = 0;

    bool oldEndOfInline = endOfInline ? *endOfInline : false;

    if (endOfInline)

        *endOfInline = false;

    while (current) {

        next = 0;

        if (!oldEndOfInline && !current->isFloating() && !current->isReplaced() && !current->isPositioned()) {

            next = current->firstChild();

            if (next && bidi.adjustEmbedding() && next->isInlineFlow()) {

                EUnicodeBidi ub = next->style()->unicodeBidi();

                if (ub != UBNormal) {

                    TextDirection dir = next->style()->direction();

                    Direction d = (ub == Embed

                        ? (dir == RTL ? RightToLeftEmbedding : LeftToRightEmbedding)

                        : (dir == RTL ? RightToLeftOverride : LeftToRightOverride));

                    bidi.embed(d);

                }

            }

        }

        if (!next) {

            if (!skipInlines && !oldEndOfInline && current->isInlineFlow()) {

                next = current;

                if (endOfInline)

                    *endOfInline = true;

                break;

            }

            while (current && current != block) {

                if (bidi.adjustEmbedding() && current->isInlineFlow() && current->style()->unicodeBidi() != UBNormal)

                    bidi.embed(PopDirectionalFormat);

                next = current->nextSibling();

                if (next) {

                    if (bidi.adjustEmbedding() && next->isInlineFlow()) {

                        EUnicodeBidi ub = next->style()->unicodeBidi();

                        if (ub != UBNormal) {

                            TextDirection dir = next->style()->direction();

                            Direction d = (ub == Embed

                                ? (dir == RTL ? RightToLeftEmbedding: LeftToRightEmbedding)

                                : (dir == RTL ? RightToLeftOverride : LeftToRightOverride));

                            bidi.embed(d);

                        }

                    }

                    break;

                }

                current = current->parent();

                if (!skipInlines && current && current != block && current->isInlineFlow()) {

                    next = current;

                    if (endOfInline)

                        *endOfInline = true;

                    break;

                }

            }

        }

        if (!next)

            break;

        if (next->isText() || next->isBR() || next->isFloating() || next->isReplaced() || next->isPositioned()

            || ((!skipInlines || !next->firstChild()) // Always return EMPTY inlines.

                && next->isInlineFlow()))

            break;

        current = next;

    }

    return next;

}

static RenderObject* bidiFirst(RenderBlock* block, BidiState& bidi, bool skipInlines = true )

{

    if (!block->firstChild())

        return 0;

    RenderObject* o = block->firstChild();

    if (o->isInlineFlow()) {

        if (bidi.adjustEmbedding()) {

            EUnicodeBidi ub = o->style()->unicodeBidi();

            if (ub != UBNormal) {

                TextDirection dir = o->style()->direction();

                Direction d = (ub == Embed

                    ? (dir == RTL ? RightToLeftEmbedding : LeftToRightEmbedding)

                    : (dir == RTL ? RightToLeftOverride : LeftToRightOverride));

                bidi.embed(d);

            }

        }

        if (skipInlines && o->firstChild())

            o = bidiNext(block, o, bidi, skipInlines);

        else

            return o; // Never skip empty inlines.

    }

    if (o && !o->isText() && !o->isBR() && !o->isReplaced() && !o->isFloating() && !o->isPositioned())

        o = bidiNext(block, o, bidi, skipInlines);

    return o;

}

inline void BidiIterator::increment(BidiState& bidi)

{

    if (!obj)

        return;

    if (obj->isText()) {

        pos++;

        if (pos >= static_cast<RenderText *>(obj)->textLength()) {

            obj = bidiNext(block, obj, bidi);

            pos = 0;

        }

    } else {

        obj = bidiNext(block, obj, bidi);

        pos = 0;

    }

}

inline bool BidiIterator::atEnd() const

{

    return !obj;

}

UChar BidiIterator::current() const

{

    if (!obj || !obj->isText())

        return 0;

    RenderText* text = static_cast<RenderText*>(obj);

    if (!text->characters())

        return 0;

    return text->characters()[pos];

}

ALWAYS_INLINE Direction BidiIterator::direction() const

{

    if (!obj)

        return OtherNeutral;

    if (obj->isListMarker())

        return obj->style()->direction() == LTR ? LeftToRight : RightToLeft;

    if (!obj->isText())

        return OtherNeutral;

    RenderText* renderTxt = static_cast<RenderText*>(obj);

    if (pos >= renderTxt->textLength())

        return OtherNeutral;

    return Unicode::direction(renderTxt->characters()[pos]);

}

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

template <>

inline void BidiState::addRun(BidiRun* bidiRun)

{

    if (!m_firstRun)

        m_firstRun = bidiRun;

    else

        m_lastRun->m_next = bidiRun;

    m_lastRun = bidiRun;

    m_runCount++;

    sLogicallyLastBidiRun = bidiRun;

    // Compute the number of spaces in this run,

    if (bidiRun->obj && bidiRun->obj->isText()) {

        RenderText* text = static_cast<RenderText*>(bidiRun->obj);

        if (text->characters()) {

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

                UChar c = text->characters()[i];

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

                    numSpaces++;

            }

        }

    }

}

static void chopMidpointsAt(RenderObject* obj, unsigned pos)

{

    if (!sNumMidpoints)

        return;

    BidiIterator* midpoints = smidpoints->data();

    for (unsigned i = 0; i < sNumMidpoints; i++) {

        const BidiIterator& point = midpoints[i];

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

            sNumMidpoints = i;

            break;

        }

    }

}

static void checkMidpoints(BidiIterator& lBreak, BidiState& bidi)

{

    // 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 && sNumMidpoints && sNumMidpoints%2 == 0) {

        BidiIterator* midpoints = smidpoints->data();

        BidiIterator& endpoint = midpoints[sNumMidpoints-2];

        const BidiIterator& startpoint = midpoints[sNumMidpoints-1];

        BidiIterator currpoint = endpoint;

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

            currpoint.increment(bidi);

        if (currpoint == lBreak) {

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

            sNumMidpoints--;

            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 = static_cast<RenderText*>(endpoint.obj);

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

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

                            return;

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

                        RenderText *startText = static_cast<RenderText*>(startpoint.obj);

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

                            return;

                    }

                }

                endpoint.pos--;

            }

        }

    }    

}

static void addMidpoint(const BidiIterator& midpoint)

{

    if (!smidpoints)

        return;

    if (smidpoints->size() <= sNumMidpoints)

        smidpoints->resize(sNumMidpoints + 10);

    BidiIterator* midpoints = smidpoints->data();

    midpoints[sNumMidpoints++] = midpoint;

}

static void appendRunsForObject(int start, int end, RenderObject* obj, BidiState& bidi)

{

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

        (obj->isPositioned() && !obj->hasStaticX() && !obj->hasStaticY() && !obj->container()->isInlineFlow()))

        return;

    bool haveNextMidpoint = (smidpoints && sCurrMidpoint < sNumMidpoints);

    BidiIterator nextMidpoint;

    if (haveNextMidpoint)

        nextMidpoint = smidpoints->at(sCurrMidpoint);

    if (betweenMidpoints) {

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

            return;

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

        // adjust our start.

        betweenMidpoints = false;

        start = nextMidpoint.pos;

        sCurrMidpoint++;

        if (start < end)

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

    }

    else {

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

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

            return;

        }

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

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

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

            betweenMidpoints = true;

            sCurrMidpoint++;

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

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

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

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

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

            }

        }

        else

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

    }

}

template <>

void BidiState::appendRun()

{

    if (emptyRun || eor.atEnd())

        return;

    bool b = m_adjustEmbedding;

    m_adjustEmbedding = false;

    int start = sor.pos;

    RenderObject *obj = sor.obj;

    while (obj && obj != eor.obj && obj != endOfLine.obj) {

        appendRunsForObject(start, obj->length(), obj, *this);        

        start = 0;

        obj = bidiNext(sor.block, obj, *this);

    }

    if (obj) {

        unsigned pos = obj == eor.obj ? eor.pos : UINT_MAX;

        if (obj == endOfLine.obj && endOfLine.pos <= pos) {

            reachedEndOfLine = true;