/**

 * (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 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 "Document.h"

#include "DocumentFragment.h"

#include "ExceptionCode.h"

#include "HTMLElement.h"

#include "HTMLNames.h"

#include "ProcessingInstruction.h"

#include "RangeException.h"

#include "RenderBlock.h"

#include "Text.h"

#include "TextIterator.h"

#include "markup.h"

#include "visible_units.h"

namespace WebCore {

using namespace std;

using namespace HTMLNames;

#ifndef NDEBUG

class RangeCounter {

public:

    static unsigned count;

    ~RangeCounter()

    {

        if (count)

            fprintf(stderr, "LEAK: %u Range\n", count);

    }

};

unsigned RangeCounter::count = 0;

static RangeCounter rangeCounter;

#endif

Range::Range(Document* ownerDocument)

    : m_ownerDocument(ownerDocument)

    , m_startContainer(ownerDocument)

    , m_startOffset(0)

    , m_endContainer(ownerDocument)

    , m_endOffset(0)

    , m_detached(false)

{

#ifndef NDEBUG

    ++RangeCounter::count;

#endif

}

Range::Range(Document* ownerDocument,

              Node* startContainer, int startOffset,

              Node* endContainer, int endOffset)

    : m_ownerDocument(ownerDocument)

    , m_startContainer(ownerDocument)

    , m_startOffset(0)

    , m_endContainer(ownerDocument)

    , m_endOffset(0)

    , m_detached(false)

{

#ifndef NDEBUG

    ++RangeCounter::count;

#endif

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

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

    ExceptionCode ec = 0;

    setStart(startContainer, startOffset, ec);

    ASSERT(ec == 0);

    setEnd(endContainer, endOffset, ec);

    ASSERT(ec == 0);

}

Range::Range(Document* ownerDocument, const Position& start, const Position& end)

    : m_ownerDocument(ownerDocument)

    , m_startContainer(ownerDocument)

    , m_startOffset(0)

    , m_endContainer(ownerDocument)

    , m_endOffset(0)

    , m_detached(false)

{

#ifndef NDEBUG

    ++RangeCounter::count;

#endif

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

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

    ExceptionCode ec = 0;

    setStart(start.node(), start.offset(), ec);

    ASSERT(ec == 0);

    setEnd(end.node(), end.offset(), ec);

    ASSERT(ec == 0);

}

Range::~Range()

{

#ifndef NDEBUG

    --RangeCounter::count;

#endif

}

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

{

    if (m_detached) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    return m_startContainer.get();

}

int Range::startOffset(ExceptionCode& ec) const

{

    if (m_detached) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    return m_startOffset;

}

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

{

    if (m_detached) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    return m_endContainer.get();

}

int Range::endOffset(ExceptionCode& ec) const

{

    if (m_detached) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    return m_endOffset;

}

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

{

    if (m_detached) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    Node *com = commonAncestorContainer(m_startContainer.get(), m_endContainer.get());

    if (!com) //  should never happen

        ec = WRONG_DOCUMENT_ERR;

    return com;

}

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

{

    Node *parentStart;

    for (parentStart = containerA; parentStart; parentStart = parentStart->parentNode()) {

        Node *parentEnd = containerB;

        while (parentEnd && (parentStart != parentEnd))

            parentEnd = parentEnd->parentNode();

        if (parentStart == parentEnd)

            break;

    }

    return parentStart;

}

bool Range::collapsed(ExceptionCode& ec) const

{

    if (m_detached) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    return (m_startContainer == m_endContainer && m_startOffset == m_endOffset);

}

void Range::setStart( Node *refNode, int offset, ExceptionCode& ec)

{

    if (m_detached) {

        ec = INVALID_STATE_ERR;

        return;

    }

    if (!refNode) {

        ec = NOT_FOUND_ERR;

        return;

    }

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

        ec = WRONG_DOCUMENT_ERR;

        return;

    }

    checkNodeWOffset( refNode, offset, ec );

    if (ec)

        return;

    m_startContainer = refNode;

    m_startOffset = offset;

    // check if different root container

    Node* endRootContainer = m_endContainer.get();

    while (endRootContainer->parentNode())

        endRootContainer = endRootContainer->parentNode();

    Node* startRootContainer = m_startContainer.get();

    while (startRootContainer->parentNode())

        startRootContainer = startRootContainer->parentNode();

    if (startRootContainer != endRootContainer)

        collapse(true, ec);

    // check if new start after end

    else if (compareBoundaryPoints(m_startContainer.get(), m_startOffset, m_endContainer.get(), m_endOffset) > 0)

        collapse(true, ec);

}

void Range::setEnd( Node *refNode, int offset, ExceptionCode& ec)

{

    if (m_detached) {

        ec = INVALID_STATE_ERR;

        return;

    }

    if (!refNode) {

        ec = NOT_FOUND_ERR;

        return;

    }

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

        ec = WRONG_DOCUMENT_ERR;

        return;

    }

    checkNodeWOffset( refNode, offset, ec );

    if (ec)

        return;

    m_endContainer = refNode;

    m_endOffset = offset;

    // check if different root container

    Node* endRootContainer = m_endContainer.get();

    while (endRootContainer->parentNode())

        endRootContainer = endRootContainer->parentNode();

    Node* startRootContainer = m_startContainer.get();

    while (startRootContainer->parentNode())

        startRootContainer = startRootContainer->parentNode();

    if (startRootContainer != endRootContainer)

        collapse(false, ec);

    // check if new end before start

    if (compareBoundaryPoints(m_startContainer.get(), m_startOffset, m_endContainer.get(), m_endOffset) > 0)

        collapse(false, ec);

}

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

{

    if (m_detached) {

        ec = INVALID_STATE_ERR;

        return;

    }

    if (toStart) {  // collapse to start

        m_endContainer = m_startContainer;

        m_endOffset = m_startOffset;

    } else {        // collapse to end

        m_startContainer = m_endContainer;

        m_startOffset = m_endOffset;

    }

}

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

{

    if (!refNode) {

        ec = NOT_FOUND_ERR;

        return false;

    }

    if (m_detached && refNode->attached()) {

        ec = INVALID_STATE_ERR;

        return false;

    }

    if (!m_detached && !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;

    }

    checkNodeWOffset(refNode, offset, ec);

    if (ec)

        return false;

    // point is not before the start and not after the end

    if ((compareBoundaryPoints(refNode, offset, m_startContainer.get(), m_startOffset) != -1) && 

        (compareBoundaryPoints(refNode, offset, m_endContainer.get(), m_endOffset) != 1))

        return true;

    else

        return false;

}

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

{

    // 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 (!refNode) {

        ec = NOT_FOUND_ERR;

        return 0;

    }

    if (m_detached && refNode->attached()) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    if (!m_detached && !refNode->attached()) {

        // firefox doesn't throw an exception for this case; it returns -1

        return -1;

    }

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

        ec = WRONG_DOCUMENT_ERR;

        return 0;

    }

    checkNodeWOffset(refNode, offset, ec);

    if (ec)

        return 0;

    // compare to start, and point comes before

    if (compareBoundaryPoints(refNode, offset, m_startContainer.get(), m_startOffset) == -1)

        return -1;

    // compare to end, and point comes after

    else if (compareBoundaryPoints(refNode, offset, m_endContainer.get(), m_endOffset) == 1)

        return 1;

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

    else

        return 0;

}

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

{

    // 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_detached && refNode->attached()) {

        ec = INVALID_STATE_ERR;

        return NODE_BEFORE;

    }

    if (!m_detached && !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();

    unsigned 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) == -1) { // starts before

        if (comparePoint(parentNode, nodeIndex + 1, ec) == 1) // 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) == 1) // 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_detached) {

        ec = INVALID_STATE_ERR;

        return 0;

    }

    if (!sourceRange) {

        ec = NOT_FOUND_ERR;

        return 0;

    }

    Node *thisCont = commonAncestorContainer(ec);

    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_startContainer.get(), m_startOffset,

                                      sourceRange->startContainer(ec), sourceRange->startOffset(ec) );

        break;

    case START_TO_END:

        return compareBoundaryPoints( m_startContainer.get(), m_startOffset,

                                      sourceRange->endContainer(ec), sourceRange->endOffset(ec) );

        break;

    case END_TO_END:

        return compareBoundaryPoints( m_endContainer.get(), m_endOffset,

                                      sourceRange->endContainer(ec), sourceRange->endOffset(ec) );

        break;

    case END_TO_START:

        return compareBoundaryPoints( m_endContainer.get(), m_endOffset,

                                      sourceRange->startContainer(ec), sourceRange->startOffset(ec) );

        break;

    default:

        ec = SYNTAX_ERR;

        return 0;

    }

}

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

{

    ASSERT(containerA && 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

    }