/*

 * (C) 1999 Lars Knoll (knoll@kde.org)

 * (C) 2000 Gunnstein Lye (gunnstein@netcom.no)

 * (C) 2000 Frederik Holljen (frederik.holljen@hig.no)

 * (C) 2001 Peter Kelly (pmk@post.com)

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

#include "RangeException.h"

#include "ClientRect.h"

#include "ClientRectList.h"

#include "DocumentFragment.h"

#include "FrameView.h"

#include "HTMLElement.h"

#include "NodeWithIndex.h"

#include "ProcessingInstruction.h"

#include "Text.h"

#include "TextIterator.h"

#include "VisiblePosition.h"

#include "htmlediting.h"

#include "markup.h"

#include "visible_units.h"

#include <stdio.h>

#include <wtf/text/CString.h>

#include <wtf/RefCountedLeakCounter.h>

namespace WebCore {

using namespace std;

#ifndef NDEBUG

static WTF::RefCountedLeakCounter rangeCounter("Range");

#endif

inline Range::Range(PassRefPtr<Document> ownerDocument)

    : m_ownerDocument(ownerDocument)

    , m_start(m_ownerDocument)

    , m_end(m_ownerDocument)

{

#ifndef NDEBUG

    rangeCounter.increment();

#endif

    m_ownerDocument->attachRange(this);

}

PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument)

{

    return adoptRef(new Range(ownerDocument));

}

inline Range::Range(PassRefPtr<Document> ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)

    : m_ownerDocument(ownerDocument)

    , m_start(m_ownerDocument)

    , m_end(m_ownerDocument)

{

#ifndef NDEBUG

    rangeCounter.increment();

#endif

    m_ownerDocument->attachRange(this);

    // Simply setting the containers and offsets directly would not do any of the checking

    // that setStart and setEnd do, so we call those functions.

    ExceptionCode ec = 0;

    setStart(startContainer, startOffset, ec);

    ASSERT(!ec);

    setEnd(endContainer, endOffset, ec);

    ASSERT(!ec);

}

PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)

{

    return adoptRef(new Range(ownerDocument, startContainer, startOffset, endContainer, endOffset));

}

PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument, const Position& start, const Position& end)

{

    // FIXME: we shouldn't be using deprecatedEditingOffset here

    return adoptRef(new Range(ownerDocument, start.node(), start.deprecatedEditingOffset(), end.node(), end.deprecatedEditingOffset()));

}

Range::~Range()

{

    // Always detach (even if we've already detached) to fix https://bugs.webkit.org/show_bug.cgi?id=26044

    m_ownerDocument->detachRange(this);

#ifndef NDEBUG

    rangeCounter.decrement();

#endif

}

Node* Range::startContainer(ExceptionCode& ec) const

{

    if (!m_start.container()) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    return m_start.container();

}

int Range::startOffset(ExceptionCode& ec) const

{

    if (!m_start.container()) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    return m_start.offset();

}

Node* Range::endContainer(ExceptionCode& ec) const

{

    if (!m_start.container()) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    return m_end.container();

}

int Range::endOffset(ExceptionCode& ec) const

{

    if (!m_start.container()) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    return m_end.offset();

}

Node* Range::commonAncestorContainer(ExceptionCode& ec) const

{

    if (!m_start.container()) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    return commonAncestorContainer(m_start.container(), m_end.container());

}

Node* Range::commonAncestorContainer(Node* containerA, Node* containerB)

{

    for (Node* parentA = containerA; parentA; parentA = parentA->parentNode()) {

        for (Node* parentB = containerB; parentB; parentB = parentB->parentNode()) {

            if (parentA == parentB)

                return parentA;

        }

    }

    return 0;

}

bool Range::collapsed(ExceptionCode& ec) const

{

    if (!m_start.container()) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    return m_start == m_end;

}

void Range::setStart(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)

{

    if (!m_start.container()) {

        ec = INVALID_STATE_ERR;

        return;

    }

    if (!refNode) {

        ec = NOT_FOUND_ERR;

        return;

    }

    if (refNode->document() != m_ownerDocument) {

        ec = WRONG_DOCUMENT_ERR;

        return;

    }

    ec = 0;

    Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);

    if (ec)

        return;

    m_start.set(refNode, offset, childNode);

    // check if different root container

    Node* endRootContainer = m_end.container();

    while (endRootContainer->parentNode())

        endRootContainer = endRootContainer->parentNode();

    Node* startRootContainer = m_start.container();

    while (startRootContainer->parentNode())

        startRootContainer = startRootContainer->parentNode();

    if (startRootContainer != endRootContainer)

        collapse(true, ec);

    // check if new start after end

    else if (compareBoundaryPoints(m_start, m_end) > 0)

        collapse(true, ec);

}

void Range::setEnd(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)

{

    if (!m_start.container()) {

        ec = INVALID_STATE_ERR;

        return;

    }

    if (!refNode) {

        ec = NOT_FOUND_ERR;

        return;

    }

    if (refNode->document() != m_ownerDocument) {

        ec = WRONG_DOCUMENT_ERR;

        return;

    }

    ec = 0;

    Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);

    if (ec)

        return;

    m_end.set(refNode, offset, childNode);

    // check if different root container

    Node* endRootContainer = m_end.container();

    while (endRootContainer->parentNode())

        endRootContainer = endRootContainer->parentNode();

    Node* startRootContainer = m_start.container();

    while (startRootContainer->parentNode())

        startRootContainer = startRootContainer->parentNode();

    if (startRootContainer != endRootContainer)

        collapse(false, ec);

    // check if new end before start

    if (compareBoundaryPoints(m_start, m_end) > 0)

        collapse(false, ec);

}

void Range::collapse(bool toStart, ExceptionCode& ec)

{

    if (!m_start.container()) {

        ec = INVALID_STATE_ERR;

        return;

    }

    if (toStart)

        m_end = m_start;

    else

        m_start = m_end;

}

bool Range::isPointInRange(Node* refNode, int offset, ExceptionCode& ec)

{

    if (!m_start.container()) {

        ec = INVALID_STATE_ERR;

        return false;

    }

    if (!refNode) {

        ec = HIERARCHY_REQUEST_ERR;

        return false;

    }

    if (!refNode->attached()) {

        // Firefox doesn't throw an exception for this case; it returns false.

        return false;

    }

    if (refNode->document() != m_ownerDocument) {

        ec = WRONG_DOCUMENT_ERR;

        return false;

    }

    ec = 0;

    checkNodeWOffset(refNode, offset, ec);

    if (ec)

        return false;

    return compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset()) >= 0

        && compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset()) <= 0;

}

short Range::comparePoint(Node* refNode, int offset, ExceptionCode& ec) const

{

    // http://developer.mozilla.org/en/docs/DOM:range.comparePoint

    // This method returns -1, 0 or 1 depending on if the point described by the 

    // refNode node and an offset within the node is before, same as, or after the range respectively.

    if (!m_start.container()) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    if (!refNode) {

        ec = HIERARCHY_REQUEST_ERR;

        return 0;

    }

    if (!refNode->attached() || refNode->document() != m_ownerDocument) {

        ec = WRONG_DOCUMENT_ERR;

        return 0;

    }

    ec = 0;

    checkNodeWOffset(refNode, offset, ec);

    if (ec)

        return 0;

    // compare to start, and point comes before

    if (compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset()) < 0)

        return -1;

    // compare to end, and point comes after

    if (compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset()) > 0)

        return 1;

    // point is in the middle of this range, or on the boundary points

    return 0;

}

Range::CompareResults Range::compareNode(Node* refNode, ExceptionCode& ec) const

{

    // http://developer.mozilla.org/en/docs/DOM:range.compareNode

    // This method returns 0, 1, 2, or 3 based on if the node is before, after,

    // before and after(surrounds), or inside the range, respectively

    if (!refNode) {

        ec = NOT_FOUND_ERR;

        return NODE_BEFORE;

    }

    if (!m_start.container() && refNode->attached()) {

        ec = INVALID_STATE_ERR;

        return NODE_BEFORE;

    }

    if (m_start.container() && !refNode->attached()) {

        // Firefox doesn't throw an exception for this case; it returns 0.

        return NODE_BEFORE;

    }

    if (refNode->document() != m_ownerDocument) {

        // Firefox doesn't throw an exception for this case; it returns 0.

        return NODE_BEFORE;

    }

    Node* parentNode = refNode->parentNode();

    int nodeIndex = refNode->nodeIndex();

    if (!parentNode) {

        // if the node is the top document we should return NODE_BEFORE_AND_AFTER

        // but we throw to match firefox behavior

        ec = NOT_FOUND_ERR;

        return NODE_BEFORE;

    }

    if (comparePoint(parentNode, nodeIndex, ec) < 0) { // starts before

        if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range

            return NODE_BEFORE_AND_AFTER;

        return NODE_BEFORE; // ends before or in the range

    } else { // starts at or after the range start

        if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range

            return NODE_AFTER;

        return NODE_INSIDE; // ends inside the range

    }

}

short Range::compareBoundaryPoints(CompareHow how, const Range* sourceRange, ExceptionCode& ec) const

{

    if (!m_start.container()) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    if (!sourceRange) {

        ec = NOT_FOUND_ERR;

        return 0;

    }

    ec = 0;

    Node* thisCont = commonAncestorContainer(ec);

    if (ec)

        return 0;

    Node* sourceCont = sourceRange->commonAncestorContainer(ec);

    if (ec)

        return 0;

    if (thisCont->document() != sourceCont->document()) {

        ec = WRONG_DOCUMENT_ERR;

        return 0;

    }

    Node* thisTop = thisCont;

    Node* sourceTop = sourceCont;

    while (thisTop->parentNode())

        thisTop = thisTop->parentNode();

    while (sourceTop->parentNode())

        sourceTop = sourceTop->parentNode();

    if (thisTop != sourceTop) { // in different DocumentFragments

        ec = WRONG_DOCUMENT_ERR;

        return 0;

    }

    switch (how) {

        case START_TO_START:

            return compareBoundaryPoints(m_start, sourceRange->m_start);

        case START_TO_END:

            return compareBoundaryPoints(m_end, sourceRange->m_start);

        case END_TO_END:

            return compareBoundaryPoints(m_end, sourceRange->m_end);

        case END_TO_START:

            return compareBoundaryPoints(m_start, sourceRange->m_end);

    }

    ec = SYNTAX_ERR;

    return 0;

}

short Range::compareBoundaryPoints(Node* containerA, int offsetA, Node* containerB, int offsetB)

{

    ASSERT(containerA);

    ASSERT(containerB);

    if (!containerA)

        return -1;

    if (!containerB)

        return 1;

    // see DOM2 traversal & range section 2.5

    // case 1: both points have the same container

    if (containerA == containerB) {

        if (offsetA == offsetB)

            return 0;           // A is equal to B

        if (offsetA < offsetB)

            return -1;          // A is before B

        else

            return 1;           // A is after B

    }

    // case 2: node C (container B or an ancestor) is a child node of A

    Node* c = containerB;

    while (c && c->parentNode() != containerA)

        c = c->parentNode();

    if (c) {

        int offsetC = 0;

        Node* n = containerA->firstChild();

        while (n != c && offsetC < offsetA) {

            offsetC++;

            n = n->nextSibling();

        }

        if (offsetA <= offsetC)

            return -1;              // A is before B

        else

            return 1;               // A is after B

    }

    // case 3: node C (container A or an ancestor) is a child node of B

    c = containerA;

    while (c && c->parentNode() != containerB)

        c = c->parentNode();

    if (c) {

        int offsetC = 0;

        Node* n = containerB->firstChild();

        while (n != c && offsetC < offsetB) {

            offsetC++;

            n = n->nextSibling();

        }

        if (offsetC < offsetB)

            return -1;              // A is before B

        else

            return 1;               // A is after B

    }

    // case 4: containers A & B are siblings, or children of siblings

    // ### we need to do a traversal here instead

    Node* commonAncestor = commonAncestorContainer(containerA, containerB);

    if (!commonAncestor)

        return 0;

    Node* childA = containerA;

    while (childA && childA->parentNode() != commonAncestor)

        childA = childA->parentNode();

    if (!childA)

        childA = commonAncestor;

    Node* childB = containerB;

    while (childB && childB->parentNode() != commonAncestor)

        childB = childB->parentNode();

    if (!childB)

        childB = commonAncestor;

    if (childA == childB)

        return 0; // A is equal to B

    Node* n = commonAncestor->firstChild();

    while (n) {

        if (n == childA)

            return -1; // A is before B

        if (n == childB)

            return 1; // A is after B

        n = n->nextSibling();

    }

    // Should never reach this point.

    ASSERT_NOT_REACHED();

    return 0;

}