/*

 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in the

 *    documentation and/or other materials provided with the distribution.

 *

 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY

 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR

 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,

 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR

 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY

 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 

 */

#include "config.h"

#include "visible_units.h"

#include "Document.h"

#include "Element.h"

#include "HTMLNames.h"

#include "RenderBlock.h"

#include "RenderLayer.h"

#include "RenderObject.h"

#include "TextBoundaries.h"

#include "TextBreakIterator.h"

#include "TextIterator.h"

#include "VisiblePosition.h"

#include "htmlediting.h"

#include <wtf/unicode/Unicode.h>

namespace WebCore {

using namespace HTMLNames;

using namespace WTF::Unicode;

static int endOfFirstWordBoundaryContext(const UChar* characters, int length)

{

    for (int i = 0; i < length; ) {

        int first = i;

        UChar32 ch;

        U16_NEXT(characters, i, length, ch);

        if (!requiresContextForWordBoundary(ch))

            return first;

    }

    return length;

}

static int startOfLastWordBoundaryContext(const UChar* characters, int length)

{

    for (int i = length; i > 0; ) {

        int last = i;

        UChar32 ch;

        U16_PREV(characters, 0, i, ch);

        if (!requiresContextForWordBoundary(ch))

            return last;

    }

    return 0;

}

enum BoundarySearchContextAvailability { DontHaveMoreContext, MayHaveMoreContext };

typedef unsigned (*BoundarySearchFunction)(const UChar*, unsigned length, unsigned offset, BoundarySearchContextAvailability, bool& needMoreContext);

static VisiblePosition previousBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)

{

    Position pos = c.deepEquivalent();

    Node *n = pos.node();

    if (!n)

        return VisiblePosition();

    Document *d = n->document();

    Node *de = d->documentElement();

    if (!de)

        return VisiblePosition();

    Node *boundary = n->enclosingBlockFlowElement();

    if (!boundary)

        return VisiblePosition();

    bool isContentEditable = boundary->isContentEditable();

    while (boundary && boundary != de && boundary->parentNode() && isContentEditable == boundary->parentNode()->isContentEditable())

        boundary = boundary->parentNode();

    Position start = rangeCompliantEquivalent(Position(boundary, 0));

    Position end = rangeCompliantEquivalent(pos);

    RefPtr<Range> searchRange = Range::create(d);

    Vector<UChar, 1024> string;

    unsigned suffixLength = 0;

    ExceptionCode ec = 0;

    if (requiresContextForWordBoundary(c.characterBefore())) {

        RefPtr<Range> forwardsScanRange(d->createRange());

        forwardsScanRange->setEndAfter(boundary, ec);

        forwardsScanRange->setStart(end.node(), end.deprecatedEditingOffset(), ec);

        TextIterator forwardsIterator(forwardsScanRange.get());

        while (!forwardsIterator.atEnd()) {

            const UChar* characters = forwardsIterator.characters();

            int length = forwardsIterator.length();

            int i = endOfFirstWordBoundaryContext(characters, length);

            string.append(characters, i);

            suffixLength += i;

            if (i < length)

                break;

            forwardsIterator.advance();

        }

    }

    searchRange->setStart(start.node(), start.deprecatedEditingOffset(), ec);

    searchRange->setEnd(end.node(), end.deprecatedEditingOffset(), ec);

    ASSERT(!ec);

    if (ec)

        return VisiblePosition();

    SimplifiedBackwardsTextIterator it(searchRange.get());

    unsigned next = 0;

    bool inTextSecurityMode = start.node() && start.node()->renderer() && start.node()->renderer()->style()->textSecurity() != TSNONE;

    bool needMoreContext = false;

    while (!it.atEnd()) {

        // iterate to get chunks until the searchFunction returns a non-zero value.

        if (!inTextSecurityMode) 

            string.prepend(it.characters(), it.length());

        else {

            // Treat bullets used in the text security mode as regular characters when looking for boundaries

            String iteratorString(it.characters(), it.length());

            iteratorString = iteratorString.impl()->secure('x');

            string.prepend(iteratorString.characters(), iteratorString.length());

        }

        next = searchFunction(string.data(), string.size(), string.size() - suffixLength, MayHaveMoreContext, needMoreContext);

        if (next != 0)

            break;

        it.advance();

    }

    if (needMoreContext) {

        // The last search returned the beginning of the buffer and asked for more context,

        // but there is no earlier text. Force a search with what's available.

        next = searchFunction(string.data(), string.size(), string.size() - suffixLength, DontHaveMoreContext, needMoreContext);

        ASSERT(!needMoreContext);

    }

    if (it.atEnd() && next == 0) {

        pos = it.range()->startPosition();

    } else if (next != 0) {

        Node *node = it.range()->startContainer(ec);

        if ((node->isTextNode() && static_cast<int>(next) <= node->maxCharacterOffset()) || (node->renderer() && node->renderer()->isBR() && !next))

            // The next variable contains a usable index into a text node

            pos = Position(node, next);

        else {

            // Use the character iterator to translate the next value into a DOM position.

            BackwardsCharacterIterator charIt(searchRange.get());

            charIt.advance(string.size() - suffixLength - next);

            pos = charIt.range()->endPosition();

        }

    }

    return VisiblePosition(pos, DOWNSTREAM);

}

static VisiblePosition nextBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)

{

    Position pos = c.deepEquivalent();

    Node *n = pos.node();

    if (!n)

        return VisiblePosition();

    Document *d = n->document();

    Node *de = d->documentElement();

    if (!de)

        return VisiblePosition();

    Node *boundary = n->enclosingBlockFlowElement();

    if (!boundary)

        return VisiblePosition();

    bool isContentEditable = boundary->isContentEditable();

    while (boundary && boundary != de && boundary->parentNode() && isContentEditable == boundary->parentNode()->isContentEditable())

        boundary = boundary->parentNode();

    RefPtr<Range> searchRange(d->createRange());

    Position start(rangeCompliantEquivalent(pos));

    Vector<UChar, 1024> string;

    unsigned prefixLength = 0;

    ExceptionCode ec = 0;

    if (requiresContextForWordBoundary(c.characterAfter())) {

        RefPtr<Range> backwardsScanRange(d->createRange());

        backwardsScanRange->setEnd(start.node(), start.deprecatedEditingOffset(), ec);

        SimplifiedBackwardsTextIterator backwardsIterator(backwardsScanRange.get());

        while (!backwardsIterator.atEnd()) {

            const UChar* characters = backwardsIterator.characters();

            int length = backwardsIterator.length();

            int i = startOfLastWordBoundaryContext(characters, length);

            string.prepend(characters + i, length - i);

            prefixLength += length - i;

            if (i > 0)

                break;

            backwardsIterator.advance();

        }

    }

    searchRange->selectNodeContents(boundary, ec);

    searchRange->setStart(start.node(), start.deprecatedEditingOffset(), ec);

    TextIterator it(searchRange.get(), TextIteratorEmitsCharactersBetweenAllVisiblePositions);

    unsigned next = 0;

    bool inTextSecurityMode = start.node() && start.node()->renderer() && start.node()->renderer()->style()->textSecurity() != TSNONE;

    bool needMoreContext = false;

    while (!it.atEnd()) {

        // Keep asking the iterator for chunks until the search function

        // returns an end value not equal to the length of the string passed to it.

        if (!inTextSecurityMode)

            string.append(it.characters(), it.length());

        else {

            // Treat bullets used in the text security mode as regular characters when looking for boundaries

            String iteratorString(it.characters(), it.length());

            iteratorString = iteratorString.impl()->secure('x');

            string.append(iteratorString.characters(), iteratorString.length());

        }

        next = searchFunction(string.data(), string.size(), prefixLength, MayHaveMoreContext, needMoreContext);

        if (next != string.size())

            break;

        it.advance();

    }

    if (needMoreContext) {

        // The last search returned the end of the buffer and asked for more context,

        // but there is no further text. Force a search with what's available.

        next = searchFunction(string.data(), string.size(), prefixLength, DontHaveMoreContext, needMoreContext);

        ASSERT(!needMoreContext);

    }

    if (it.atEnd() && next == string.size()) {

        pos = it.range()->startPosition();

    } else if (next != prefixLength) {

        // Use the character iterator to translate the next value into a DOM position.

        CharacterIterator charIt(searchRange.get(), TextIteratorEmitsCharactersBetweenAllVisiblePositions);

        charIt.advance(next - prefixLength - 1);

        pos = charIt.range()->endPosition();

        if (*charIt.characters() == '\n') {

            // FIXME: workaround for collapsed range (where only start position is correct) emitted for some emitted newlines (see rdar://5192593)

            VisiblePosition visPos = VisiblePosition(pos);

            if (visPos == VisiblePosition(charIt.range()->startPosition()))

                pos = visPos.next(true).deepEquivalent();

        }

    }

    // generate VisiblePosition, use UPSTREAM affinity if possible

    return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);

}

static bool canHaveCursor(RenderObject* o)

{

    return (o->isText() && toRenderText(o)->linesBoundingBox().height())

        || (o->isBox() && toRenderBox(o)->borderBoundingBox().height());

}

// ---------

static unsigned startWordBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)

{

    ASSERT(offset);

    if (mayHaveMoreContext && !startOfLastWordBoundaryContext(characters, offset)) {

        needMoreContext = true;

        return 0;

    }

    needMoreContext = false;

    int start, end;

    findWordBoundary(characters, length, offset - 1, &start, &end);

    return start;

}

VisiblePosition startOfWord(const VisiblePosition &c, EWordSide side)

{

    // FIXME: This returns a null VP for c at the start of the document

    // and side == LeftWordIfOnBoundary

    VisiblePosition p = c;

    if (side == RightWordIfOnBoundary) {

        // at paragraph end, the startofWord is the current position

        if (isEndOfParagraph(c))

            return c;

        p = c.next();

        if (p.isNull())

            return c;

    }

    return previousBoundary(p, startWordBoundary);

}

static unsigned endWordBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)

{

    ASSERT(offset <= length);

    if (mayHaveMoreContext && endOfFirstWordBoundaryContext(characters + offset, length - offset) == static_cast<int>(length - offset)) {

        needMoreContext = true;

        return length;

    }

    needMoreContext = false;

    int start, end;

    findWordBoundary(characters, length, offset, &start, &end);

    return end;

}

VisiblePosition endOfWord(const VisiblePosition &c, EWordSide side)

{

    VisiblePosition p = c;

    if (side == LeftWordIfOnBoundary) {

        if (isStartOfParagraph(c))

            return c;

        p = c.previous();

        if (p.isNull())

            return c;

    } else if (isEndOfParagraph(c))

        return c;

    return nextBoundary(p, endWordBoundary);

}

static unsigned previousWordPositionBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)

{

    if (mayHaveMoreContext && !startOfLastWordBoundaryContext(characters, offset)) {

        needMoreContext = true;

        return 0;

    }

    needMoreContext = false;

    return findNextWordFromIndex(characters, length, offset, false);

}

VisiblePosition previousWordPosition(const VisiblePosition &c)

{

    VisiblePosition prev = previousBoundary(c, previousWordPositionBoundary);

    return c.honorEditableBoundaryAtOrAfter(prev);

}

static unsigned nextWordPositionBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)

{

    if (mayHaveMoreContext && endOfFirstWordBoundaryContext(characters + offset, length - offset) == static_cast<int>(length - offset)) {

        needMoreContext = true;

        return length;

    }

    needMoreContext = false;

    return findNextWordFromIndex(characters, length, offset, true);

}

VisiblePosition nextWordPosition(const VisiblePosition &c)

{

    VisiblePosition next = nextBoundary(c, nextWordPositionBoundary);    

    return c.honorEditableBoundaryAtOrBefore(next);

}

// ---------

static RootInlineBox *rootBoxForLine(const VisiblePosition &c)

{

    Position p = c.deepEquivalent();

    Node *node = p.node();

    if (!node)

        return 0;

    RenderObject *renderer = node->renderer();

    if (!renderer)

        return 0;

    InlineBox* box;

    int offset;

    c.getInlineBoxAndOffset(box, offset);

    return box ? box->root() : 0;

}

static VisiblePosition positionAvoidingFirstPositionInTable(const VisiblePosition& c)

{

    // return table offset 0 instead of the first VisiblePosition inside the table

    VisiblePosition previous = c.previous();

    if (isLastPositionBeforeTable(previous))

        return previous;

    return c;

}

static VisiblePosition startPositionForLine(const VisiblePosition& c)

{

    if (c.isNull())

        return VisiblePosition();

    RootInlineBox *rootBox = rootBoxForLine(c);

    if (!rootBox) {

        // There are VisiblePositions at offset 0 in blocks without

        // RootInlineBoxes, like empty editable blocks and bordered blocks.

        Position p = c.deepEquivalent();

        if (p.node()->renderer() && p.node()->renderer()->isRenderBlock() && p.deprecatedEditingOffset() == 0)

            return positionAvoidingFirstPositionInTable(c);

        return VisiblePosition();

    }

    // Generated content (e.g. list markers and CSS :before and :after

    // pseudoelements) have no corresponding DOM element, and so cannot be

    // represented by a VisiblePosition.  Use whatever follows instead.

    InlineBox *startBox = rootBox->firstLeafChild();

    Node *startNode;

    while (1) {

        if (!startBox)

            return VisiblePosition();

        RenderObject *startRenderer = startBox->renderer();

        if (!startRenderer)

            return VisiblePosition();

        startNode = startRenderer->node();

        if (startNode)

            break;

        startBox = startBox->nextLeafChild();

    }

    int startOffset = 0;

    if (startBox->isInlineTextBox()) {

        InlineTextBox *startTextBox = static_cast<InlineTextBox *>(startBox);

        startOffset = startTextBox->start();

    }

    VisiblePosition visPos = VisiblePosition(startNode, startOffset, DOWNSTREAM);

    return positionAvoidingFirstPositionInTable(visPos);

}

VisiblePosition startOfLine(const VisiblePosition& c)

{

    VisiblePosition visPos = startPositionForLine(c);

    if (visPos.isNotNull()) {

        // Make sure the start of line is not greater than the given input position.  Else use the previous position to 

        // obtain start of line.  This condition happens when the input position is before the space character at the end 

        // of a soft-wrapped non-editable line. In this scenario, startPositionForLine would incorrectly hand back a position

        // greater than the input position.  This fix is to account for the discrepancy between lines with webkit-line-break:after-white-space 

        // style versus lines without that style, which would break before a space by default. 

        Position p = visPos.deepEquivalent();

        if (p.deprecatedEditingOffset() > c.deepEquivalent().deprecatedEditingOffset() && p.node()->isSameNode(c.deepEquivalent().node())) {

            visPos = c.previous();

            if (visPos.isNull())

                return VisiblePosition();

            visPos = startPositionForLine(visPos);

        }

    }

    return c.honorEditableBoundaryAtOrAfter(visPos);

}

static VisiblePosition endPositionForLine(const VisiblePosition& c)

{

    if (c.isNull())

        return VisiblePosition();

    RootInlineBox *rootBox = rootBoxForLine(c);

    if (!rootBox) {

        // There are VisiblePositions at offset 0 in blocks without

        // RootInlineBoxes, like empty editable blocks and bordered blocks.

        Position p = c.deepEquivalent();

        if (p.node()->renderer() && p.node()->renderer()->isRenderBlock() && p.deprecatedEditingOffset() == 0)

            return c;

        return VisiblePosition();

    }

    // Generated content (e.g. list markers and CSS :before and :after

    // pseudoelements) have no corresponding DOM element, and so cannot be

    // represented by a VisiblePosition.  Use whatever precedes instead.

    Node *endNode;

    InlineBox *endBox = rootBox->lastLeafChild();

    while (1) {

        if (!endBox)

            return VisiblePosition();

        RenderObject *endRenderer = endBox->renderer();

        if (!endRenderer)

            return VisiblePosition();

        endNode = endRenderer->node();

        if (endNode)

            break;

        endBox = endBox->prevLeafChild();

    }

    int endOffset = 1;

    if (endNode->hasTagName(brTag)) {

        endOffset = 0;

    } else if (endBox->isInlineTextBox()) {

        InlineTextBox *endTextBox = static_cast<InlineTextBox *>(endBox);

        endOffset = endTextBox->start();

        if (!endTextBox->isLineBreak())

            endOffset += endTextBox->len();

    }

    return VisiblePosition(endNode, endOffset, VP_UPSTREAM_IF_POSSIBLE);

}

VisiblePosition endOfLine(const VisiblePosition& c)

{

    VisiblePosition visPos = endPositionForLine(c);

    // Make sure the end of line is at the same line as the given input position.  Else use the previous position to 

    // obtain end of line.  This condition happens when the input position is before the space character at the end 

    // of a soft-wrapped non-editable line. In this scenario, endPositionForLine would incorrectly hand back a position

    // in the next line instead. This fix is to account for the discrepancy between lines with webkit-line-break:after-white-space style

    // versus lines without that style, which would break before a space by default. 

    if (!inSameLine(c, visPos)) {

        visPos = c.previous();

        if (visPos.isNull())

            return VisiblePosition();

        visPos = endPositionForLine(visPos);

    }

    return c.honorEditableBoundaryAtOrBefore(visPos);

}

bool inSameLine(const VisiblePosition &a, const VisiblePosition &b)

{

    return a.isNotNull() && startOfLine(a) == startOfLine(b);

}

bool isStartOfLine(const VisiblePosition &p)

{

    return p.isNotNull() && p == startOfLine(p);

}