/*

 * Copyright (C) 2004, 2005, 2006, 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 "Position.h"

#include "CSSComputedStyleDeclaration.h"

#include "CharacterNames.h"

#include "Logging.h"

#include "PositionIterator.h"

#include "RenderBlock.h"

#include "Text.h"

#include "TextIterator.h"

#include "VisiblePosition.h"

#include "htmlediting.h"

#include "visible_units.h"

#include <stdio.h>

#include <wtf/text/CString.h>

namespace WebCore {

using namespace HTMLNames;

static Node* nextRenderedEditable(Node* node)

{

    while (1) {

        node = node->nextEditable();

        if (!node)

            return 0;

        RenderObject* renderer = node->renderer();

        if (!renderer)

            continue;

        if ((renderer->isBox() && toRenderBox(renderer)->inlineBoxWrapper()) || (renderer->isText() && toRenderText(renderer)->firstTextBox()))

            return node;

    }

    return 0;

}

static Node* previousRenderedEditable(Node* node)

{

    while (1) {

        node = node->previousEditable();

        if (!node)

            return 0;

        RenderObject* renderer = node->renderer();

        if (!renderer)

            continue;

        if ((renderer->isBox() && toRenderBox(renderer)->inlineBoxWrapper()) || (renderer->isText() && toRenderText(renderer)->firstTextBox()))

            return node;

    }

    return 0;

}

Position::Position(PassRefPtr<Node> anchorNode, int offset)

    : m_anchorNode(anchorNode)

    , m_offset(offset)

    , m_anchorType(anchorTypeForLegacyEditingPosition(m_anchorNode.get(), m_offset))

    , m_isLegacyEditingPosition(true)

{

}

Position::Position(PassRefPtr<Node> anchorNode, AnchorType anchorType)

    : m_anchorNode(anchorNode)

    , m_offset(0)

    , m_anchorType(anchorType)

    , m_isLegacyEditingPosition(false)

{

    ASSERT(anchorType != PositionIsOffsetInAnchor);

}

Position::Position(PassRefPtr<Node> anchorNode, int offset, AnchorType anchorType)

    : m_anchorNode(anchorNode)

    , m_offset(offset)

    , m_anchorType(anchorType)

    , m_isLegacyEditingPosition(false)

{

    ASSERT(anchorType == PositionIsOffsetInAnchor);

}

void Position::moveToPosition(PassRefPtr<Node> node, int offset)

{

    ASSERT(anchorType() == PositionIsOffsetInAnchor || m_isLegacyEditingPosition);

    m_anchorNode = node;

    m_offset = offset;

    if (m_isLegacyEditingPosition)

        m_anchorType = anchorTypeForLegacyEditingPosition(m_anchorNode.get(), m_offset);

}

void Position::moveToOffset(int offset)

{

    ASSERT(anchorType() == PositionIsOffsetInAnchor || m_isLegacyEditingPosition);

    m_offset = offset;

    if (m_isLegacyEditingPosition)

        m_anchorType = anchorTypeForLegacyEditingPosition(m_anchorNode.get(), m_offset);

}

Node* Position::containerNode() const

{

    if (!m_anchorNode)

        return 0;

    switch (anchorType()) {

    case PositionIsOffsetInAnchor:

        return m_anchorNode.get();

    case PositionIsBeforeAnchor:

    case PositionIsAfterAnchor:

        return m_anchorNode->parentNode();

    }

    ASSERT_NOT_REACHED();

    return 0;

}

int Position::computeOffsetInContainerNode() const

{

    if (!m_anchorNode)

        return 0;

    switch (anchorType()) {

    case PositionIsOffsetInAnchor:

        return std::min(lastOffsetInNode(m_anchorNode.get()), m_offset);

    case PositionIsBeforeAnchor:

        return m_anchorNode->nodeIndex();

    case PositionIsAfterAnchor:

        return m_anchorNode->nodeIndex() + 1;

    }

    ASSERT_NOT_REACHED();

    return 0;

}

Node* Position::computeNodeBeforePosition() const

{

    if (!m_anchorNode)

        return 0;

    switch (anchorType()) {

    case PositionIsOffsetInAnchor:

        return m_anchorNode->childNode(m_offset - 1); // -1 converts to childNode((unsigned)-1) and returns null.

    case PositionIsBeforeAnchor:

        return m_anchorNode->previousSibling();

    case PositionIsAfterAnchor:

        return m_anchorNode.get();

    }

    ASSERT_NOT_REACHED();

    return 0;

}

Node* Position::computeNodeAfterPosition() const

{

    if (!m_anchorNode)

        return 0;

    switch (anchorType()) {

    case PositionIsOffsetInAnchor:

        return m_anchorNode->childNode(m_offset);

    case PositionIsBeforeAnchor:

        return m_anchorNode.get();

    case PositionIsAfterAnchor:

        return m_anchorNode->nextSibling();

    }

    ASSERT_NOT_REACHED();

    return 0;

}

Position::AnchorType Position::anchorTypeForLegacyEditingPosition(Node* anchorNode, int offset)

{

    if (anchorNode && editingIgnoresContent(anchorNode)) {

        if (offset == 0)

            return Position::PositionIsBeforeAnchor;

        return Position::PositionIsAfterAnchor;

    }

    return Position::PositionIsOffsetInAnchor;

}

// FIXME: This method is confusing (does it return anchorNode() or containerNode()?) and should be renamed or removed

Element* Position::element() const

{

    Node* n = anchorNode();

    while (n && !n->isElementNode())

        n = n->parentNode();

    return static_cast<Element*>(n);

}

PassRefPtr<CSSComputedStyleDeclaration> Position::computedStyle() const

{

    Element* elem = element();

    if (!elem)

        return 0;

    return WebCore::computedStyle(elem);

}

Position Position::previous(PositionMoveType moveType) const

{

    Node* n = node();

    if (!n)

        return *this;

    int o = m_offset;

    // FIXME: Negative offsets shouldn't be allowed. We should catch this earlier.

    ASSERT(o >= 0);

    if (o > 0) {

        Node* child = n->childNode(o - 1);

        if (child)

            return lastDeepEditingPositionForNode(child);

        // There are two reasons child might be 0:

        //   1) The node is node like a text node that is not an element, and therefore has no children.

        //      Going backward one character at a time is correct.

        //   2) The old offset was a bogus offset like (<br>, 1), and there is no child.

        //      Going from 1 to 0 is correct.

        switch (moveType) {

        case CodePoint:

            return Position(n, o - 1);

        case Character:

            return Position(n, uncheckedPreviousOffset(n, o));

        case BackwardDeletion:

            return Position(n, uncheckedPreviousOffsetForBackwardDeletion(n, o));

        }

    }

    Node* parent = n->parentNode();

    if (!parent)

        return *this;

    return Position(parent, n->nodeIndex());

}

Position Position::next(PositionMoveType moveType) const

{

    ASSERT(moveType != BackwardDeletion);

    Node* n = node();

    if (!n)

        return *this;

    int o = m_offset;

    // FIXME: Negative offsets shouldn't be allowed. We should catch this earlier.

    ASSERT(o >= 0);

    Node* child = n->childNode(o);

    if (child || (!n->hasChildNodes() && o < lastOffsetForEditing(n))) {

        if (child)

            return firstDeepEditingPositionForNode(child);

        // There are two reasons child might be 0:

        //   1) The node is node like a text node that is not an element, and therefore has no children.

        //      Going forward one character at a time is correct.

        //   2) The new offset is a bogus offset like (<br>, 1), and there is no child.

        //      Going from 0 to 1 is correct.

        return Position(n, (moveType == Character) ? uncheckedNextOffset(n, o) : o + 1);

    }

    Node* parent = n->parentNode();

    if (!parent)

        return *this;

    return Position(parent, n->nodeIndex() + 1);

}

int Position::uncheckedPreviousOffset(const Node* n, int current)

{

    return n->renderer() ? n->renderer()->previousOffset(current) : current - 1;

}

int Position::uncheckedPreviousOffsetForBackwardDeletion(const Node* n, int current)

{

    return n->renderer() ? n->renderer()->previousOffsetForBackwardDeletion(current) : current - 1;

}

int Position::uncheckedNextOffset(const Node* n, int current)

{

    return n->renderer() ? n->renderer()->nextOffset(current) : current + 1;

}

bool Position::atFirstEditingPositionForNode() const

{

    if (isNull())

        return true;

    return m_offset <= 0;

}

bool Position::atLastEditingPositionForNode() const

{

    if (isNull())

        return true;

    return m_offset >= lastOffsetForEditing(node());

}

// A position is considered at editing boundary if one of the following is true:

// 1. It is the first position in the node and the next visually equivalent position

//    is non editable.

// 2. It is the last position in the node and the previous visually equivalent position

//    is non editable.

// 3. It is an editable position and both the next and previous visually equivalent

//    positions are both non editable.

bool Position::atEditingBoundary() const

{

    Position nextPosition = downstream(CanCrossEditingBoundary);

    if (atFirstEditingPositionForNode() && nextPosition.isNotNull() && !nextPosition.node()->isContentEditable())

        return true;

    Position prevPosition = upstream(CanCrossEditingBoundary);

    if (atLastEditingPositionForNode() && prevPosition.isNotNull() && !prevPosition.node()->isContentEditable())

        return true;

    return nextPosition.isNotNull() && !nextPosition.node()->isContentEditable()

        && prevPosition.isNotNull() && !prevPosition.node()->isContentEditable();

}

bool Position::atStartOfTree() const

{

    if (isNull())

        return true;

    return !node()->parentNode() && m_offset <= 0;

}

bool Position::atEndOfTree() const

{

    if (isNull())

        return true;

    return !node()->parentNode() && m_offset >= lastOffsetForEditing(node());

}

int Position::renderedOffset() const

{

    if (!node()->isTextNode())

        return m_offset;

    if (!node()->renderer())

        return m_offset;

    int result = 0;

    RenderText *textRenderer = toRenderText(node()->renderer());

    for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {

        int start = box->start();

        int end = box->start() + box->len();

        if (m_offset < start)

            return result;

        if (m_offset <= end) {

            result += m_offset - start;

            return result;

        }

        result += box->len();

    }

    return result;

}

// return first preceding DOM position rendered at a different location, or "this"

Position Position::previousCharacterPosition(EAffinity affinity) const

{

    if (isNull())

        return Position();

    Node *fromRootEditableElement = node()->rootEditableElement();

    bool atStartOfLine = isStartOfLine(VisiblePosition(*this, affinity));

    bool rendered = isCandidate();

    Position currentPos = *this;

    while (!currentPos.atStartOfTree()) {

        currentPos = currentPos.previous();

        if (currentPos.node()->rootEditableElement() != fromRootEditableElement)

            return *this;

        if (atStartOfLine || !rendered) {

            if (currentPos.isCandidate())

                return currentPos;

        } else if (rendersInDifferentPosition(currentPos))

            return currentPos;

    }

    return *this;

}

// return first following position rendered at a different location, or "this"

Position Position::nextCharacterPosition(EAffinity affinity) const

{

    if (isNull())

        return Position();

    Node *fromRootEditableElement = node()->rootEditableElement();

    bool atEndOfLine = isEndOfLine(VisiblePosition(*this, affinity));

    bool rendered = isCandidate();

    Position currentPos = *this;

    while (!currentPos.atEndOfTree()) {

        currentPos = currentPos.next();

        if (currentPos.node()->rootEditableElement() != fromRootEditableElement)

            return *this;

        if (atEndOfLine || !rendered) {

            if (currentPos.isCandidate())

                return currentPos;

        } else if (rendersInDifferentPosition(currentPos))

            return currentPos;

    }

    return *this;

}

// Whether or not [node, 0] and [node, lastOffsetForEditing(node)] are their own VisiblePositions.

// If true, adjacent candidates are visually distinct.

// FIXME: Disregard nodes with renderers that have no height, as we do in isCandidate.

// FIXME: Share code with isCandidate, if possible.

static bool endsOfNodeAreVisuallyDistinctPositions(Node* node)

{

    if (!node || !node->renderer())

        return false;

    if (!node->renderer()->isInline())

        return true;

    // Don't include inline tables.

    if (node->hasTagName(tableTag))

        return false;

    // There is a VisiblePosition inside an empty inline-block container.

    return node->renderer()->isReplaced() && canHaveChildrenForEditing(node) && toRenderBox(node->renderer())->height() != 0 && !node->firstChild();

}

static Node* enclosingVisualBoundary(Node* node)

{

    while (node && !endsOfNodeAreVisuallyDistinctPositions(node))

        node = node->parentNode();

    return node;

}

// upstream() and downstream() want to return positions that are either in a

// text node or at just before a non-text node.  This method checks for that.

static bool isStreamer(const PositionIterator& pos)

{

    if (!pos.node())

        return true;

    if (isAtomicNode(pos.node()))

        return true;

    return pos.atStartOfNode();

}

// This function and downstream() are used for moving back and forth between visually equivalent candidates.

// For example, for the text node "foo     bar" where whitespace is collapsible, there are two candidates 

// that map to the VisiblePosition between 'b' and the space.  This function will return the left candidate 

// and downstream() will return the right one.

// Also, upstream() will return [boundary, 0] for any of the positions from [boundary, 0] to the first candidate

// in boundary, where endsOfNodeAreVisuallyDistinctPositions(boundary) is true.

Position Position::upstream(EditingBoundaryCrossingRule rule) const

{

    Node* startNode = node();

    if (!startNode)

        return Position();

    // iterate backward from there, looking for a qualified position

    Node* boundary = enclosingVisualBoundary(startNode);

    PositionIterator lastVisible = *this;

    PositionIterator currentPos = lastVisible;

    bool startEditable = startNode->isContentEditable();

    Node* lastNode = startNode;

    bool boundaryCrossed = false;

    for (; !currentPos.atStart(); currentPos.decrement()) {

        Node* currentNode = currentPos.node();

        // Don't check for an editability change if we haven't moved to a different node,

        // to avoid the expense of computing isContentEditable().

        if (currentNode != lastNode) {

            // Don't change editability.

            bool currentEditable = currentNode->isContentEditable();

            if (startEditable != currentEditable) {

                if (rule == CannotCrossEditingBoundary)

                    break;

                boundaryCrossed = true;

            }

            lastNode = currentNode;

        }

        // If we've moved to a position that is visually distinct, return the last saved position. There 

        // is code below that terminates early if we're *about* to move to a visually distinct position.

        if (endsOfNodeAreVisuallyDistinctPositions(currentNode) && currentNode != boundary)

            return lastVisible;

        // skip position in unrendered or invisible node

        RenderObject* renderer = currentNode->renderer();

        if (!renderer || renderer->style()->visibility() != VISIBLE)

            continue;

        if (rule == CanCrossEditingBoundary && boundaryCrossed) {

            lastVisible = currentPos;

            break;

        }

        // track last visible streamer position

        if (isStreamer(currentPos))

            lastVisible = currentPos;

        // Don't move past a position that is visually distinct.  We could rely on code above to terminate and 

        // return lastVisible on the next iteration, but we terminate early to avoid doing a nodeIndex() call.

        if (endsOfNodeAreVisuallyDistinctPositions(currentNode) && currentPos.atStartOfNode())

            return lastVisible;

        // Return position after tables and nodes which have content that can be ignored.

        if (editingIgnoresContent(currentNode) || isTableElement(currentNode)) {

            if (currentPos.atEndOfNode())

                return lastDeepEditingPositionForNode(currentNode);