/**

 * This file is part of the DOM implementation for KDE.

 *

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

 *           (C) 1999 Antti Koivisto (koivisto@kde.org)

 *           (C) 2001 Dirk Mueller (mueller@kde.org)

 * Copyright (C) 2004, 2005, 2006 Apple Computer, Inc.

 *

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

#include "DeleteButtonController.h"

#include "Document.h"

#include "Editor.h"

#include "EventNames.h"

#include "ExceptionCode.h"

#include "FrameView.h"

#include "InlineTextBox.h"

#include "MutationEvent.h"

#include "RenderTheme.h"

#include "RootInlineBox.h"

#include "SystemTime.h"

#include <wtf/Vector.h>

namespace WebCore {

using namespace EventNames;

static void dispatchChildInsertionEvents(Node*, ExceptionCode&);

static void dispatchChildRemovalEvents(Node*, ExceptionCode&);

typedef Vector<std::pair<NodeCallback, Node*> > NodeCallbackQueue;

static NodeCallbackQueue* s_postAttachCallbackQueue = 0;

static size_t s_attachDepth = 0;

ContainerNode::ContainerNode(Document* doc)

    : EventTargetNode(doc), m_firstChild(0), m_lastChild(0)

{

}

void ContainerNode::removeAllChildren()

{

    // Avoid deep recursion when destroying the node tree.

    static bool alreadyInsideDestructor; 

    bool topLevel = !alreadyInsideDestructor;

    if (topLevel)

        alreadyInsideDestructor = true;

    // List of nodes to be deleted.

    static Node* head;

    static Node* tail;

    // We have to tell all children that their parent has died.

    Node* n;

    Node* next;

    for (n = m_firstChild; n != 0; n = next) {

        ASSERT(!n->m_deletionHasBegun);

        next = n->nextSibling();

        n->setPreviousSibling(0);

        n->setNextSibling(0);

        n->setParent(0);

        if (!n->refCount()) {

#ifndef NDEBUG

            n->m_deletionHasBegun = true;

#endif

            // Add the node to the list of nodes to be deleted.

            // Reuse the nextSibling pointer for this purpose.

            if (tail)

                tail->setNextSibling(n);

            else

                head = n;

            tail = n;

        } else if (n->inDocument())

            n->removedFromDocument();

    }

    // Only for the top level call, do the actual deleting.

    if (topLevel) {

        while ((n = head) != 0) {

            ASSERT(n->m_deletionHasBegun);

            next = n->nextSibling();

            n->setNextSibling(0);

            head = next;

            if (next == 0)

                tail = 0;

            delete n;

        }

        alreadyInsideDestructor = false;

        m_firstChild = 0;

        m_lastChild = 0;

    }

}

ContainerNode::~ContainerNode()

{

    removeAllChildren();

}

Node* ContainerNode::virtualFirstChild() const

{

    return m_firstChild;

}

Node* ContainerNode::virtualLastChild() const

{

    return m_lastChild;

}

bool ContainerNode::insertBefore(PassRefPtr<Node> newChild, Node* refChild, ExceptionCode& ec)

{

    // Check that this node is not "floating".

    // If it is, it can be deleted as a side effect of sending mutation events.

    ASSERT(refCount() || parent());

    ec = 0;

    // insertBefore(node, 0) is equivalent to appendChild(node)

    if (!refChild)

        return appendChild(newChild, ec);

    // Make sure adding the new child is OK.

    checkAddChild(newChild.get(), ec);

    if (ec)

        return false;

    // NOT_FOUND_ERR: Raised if refChild is not a child of this node

    if (refChild->parentNode() != this) {

        ec = NOT_FOUND_ERR;

        return false;

    }

    bool isFragment = newChild->nodeType() == DOCUMENT_FRAGMENT_NODE;

    // If newChild is a DocumentFragment with no children; there's nothing to do.

    // Just return true

    if (isFragment && !newChild->firstChild())

        return true;

    // Now actually add the child(ren)

    if (refChild->previousSibling() == newChild || refChild == newChild) // nothing to do

        return true;

    RefPtr<Node> next = refChild;

    RefPtr<Node> child = isFragment ? newChild->firstChild() : newChild;

    while (child) {

        RefPtr<Node> nextChild = isFragment ? child->nextSibling() : 0;

        // If child is already present in the tree, first remove it from the old location.

        if (Node* oldParent = child->parentNode())

            oldParent->removeChild(child.get(), ec);

        if (ec)

            return 0;

        // FIXME: After sending the mutation events, "this" could be destroyed.

        // We can prevent that by doing a "ref", but first we have to make sure

        // that no callers call with ref count == 0 and parent = 0 (as of this

        // writing, there are definitely callers who call that way).

        // Due to arbitrary code running in response to a DOM mutation event it's

        // possible that "next" is no longer a child of "this".

        // It's also possible that "child" has been inserted elsewhere.

        // In either of those cases, we'll just stop.

        if (next->parentNode() != this)

            break;

        if (child->parentNode())

            break;

        ASSERT(!child->nextSibling());

        ASSERT(!child->previousSibling());

        // Add child before "next".

        forbidEventDispatch();

        Node* prev = next->previousSibling();

        ASSERT(m_lastChild != prev);

        next->setPreviousSibling(child.get());

        if (prev) {

            ASSERT(m_firstChild != next);

            ASSERT(prev->nextSibling() == next);

            prev->setNextSibling(child.get());

        } else {

            ASSERT(m_firstChild == next);

            m_firstChild = child.get();

        }

        child->setParent(this);

        child->setPreviousSibling(prev);

        child->setNextSibling(next.get());

        allowEventDispatch();

        // Dispatch the mutation events.

        dispatchChildInsertionEvents(child.get(), ec);

        // Add child to the rendering tree.

        if (attached() && !child->attached() && child->parent() == this)

            child->attach();

        child = nextChild.release();

    }

    document()->setDocumentChanged(true);

    dispatchSubtreeModifiedEvent();

    return true;

}

bool ContainerNode::replaceChild(PassRefPtr<Node> newChild, Node* oldChild, ExceptionCode& ec)

{

    // Check that this node is not "floating".

    // If it is, it can be deleted as a side effect of sending mutation events.

    ASSERT(refCount() || parent());

    ec = 0;

    if (oldChild == newChild) // nothing to do

        return true;

    // Make sure replacing the old child with the new is ok

    checkReplaceChild(newChild.get(), oldChild, ec);

    if (ec)

        return false;

    // NOT_FOUND_ERR: Raised if oldChild is not a child of this node.

    if (!oldChild || oldChild->parentNode() != this) {

        ec = NOT_FOUND_ERR;

        return false;

    }

    RefPtr<Node> prev = oldChild->previousSibling();

    // Remove the node we're replacing

    RefPtr<Node> removedChild = oldChild;

    removeChild(oldChild, ec);

    if (ec)

        return false;

    // FIXME: After sending the mutation events, "this" could be destroyed.

    // We can prevent that by doing a "ref", but first we have to make sure

    // that no callers call with ref count == 0 and parent = 0 (as of this

    // writing, there are definitely callers who call that way).

    bool isFragment = newChild->nodeType() == DOCUMENT_FRAGMENT_NODE;

    // Add the new child(ren)

    RefPtr<Node> child = isFragment ? newChild->firstChild() : newChild;

    while (child) {

        // If the new child is already in the right place, we're done.

        if (prev && (prev == child || prev == child->previousSibling()))

            break;

        // For a fragment we have more children to do.

        RefPtr<Node> nextChild = isFragment ? child->nextSibling() : 0;

        // Remove child from its old position.

        if (Node* oldParent = child->parentNode())

            oldParent->removeChild(child.get(), ec);

        if (ec)

            return 0;

        // Due to arbitrary code running in response to a DOM mutation event it's

        // possible that "prev" is no longer a child of "this".

        // It's also possible that "child" has been inserted elsewhere.

        // In either of those cases, we'll just stop.

        if (prev && prev->parentNode() != this)

            break;

        if (child->parentNode())

            break;

        ASSERT(!child->nextSibling());

        ASSERT(!child->previousSibling());

        // Add child after "prev".

        forbidEventDispatch();

        Node* next;

        if (prev) {

            next = prev->nextSibling();

            ASSERT(m_firstChild != next);

            prev->setNextSibling(child.get());

        } else {

            next = m_firstChild;

            m_firstChild = child.get();

        }

        if (next) {

            ASSERT(m_lastChild != prev);

            ASSERT(next->previousSibling() == prev);

            next->setPreviousSibling(child.get());

        } else {

            ASSERT(m_lastChild == prev);

            m_lastChild = child.get();

        }

        child->setParent(this);

        child->setPreviousSibling(prev.get());

        child->setNextSibling(next);

        allowEventDispatch();

        // Dispatch the mutation events

        dispatchChildInsertionEvents(child.get(), ec);

        // Add child to the rendering tree

        if (attached() && !child->attached() && child->parent() == this)

            child->attach();

        prev = child;

        child = nextChild.release();

    }

    // ### set style in case it's attached

    document()->setDocumentChanged(true);

    dispatchSubtreeModifiedEvent();

    return true;

}

void ContainerNode::willRemove()

{

    for (Node *n = m_firstChild; n != 0; n = n->nextSibling())

        n->willRemove();

    EventTargetNode::willRemove();

}

static ExceptionCode willRemoveChild(Node *child)

{

    ExceptionCode ec = 0;

    // fire removed from document mutation events.

    dispatchChildRemovalEvents(child, ec);

    if (ec)

        return ec;

    if (child->attached())

        child->willRemove();

    return 0;

}

bool ContainerNode::removeChild(Node* oldChild, ExceptionCode& ec)

{

    // Check that this node is not "floating".

    // If it is, it can be deleted as a side effect of sending mutation events.

    ASSERT(refCount() || parent());

    ec = 0;

    // NO_MODIFICATION_ALLOWED_ERR: Raised if this node is readonly.

    if (isReadOnlyNode()) {

        ec = NO_MODIFICATION_ALLOWED_ERR;

        return false;

    }

    // NOT_FOUND_ERR: Raised if oldChild is not a child of this node.

    if (!oldChild || oldChild->parentNode() != this) {

        ec = NOT_FOUND_ERR;

        return false;

    }

    RefPtr<Node> child = oldChild;

    // dispatch pre-removal mutation events

    if (document()->hasListenerType(Document::DOMNODEREMOVED_LISTENER)) {

        EventTargetNodeCast(child.get())->dispatchEvent(new MutationEvent(DOMNodeRemovedEvent, true, false,

            this, String(), String(), String(), 0), ec, true);

        if (ec)

            return false;

    }

    ec = willRemoveChild(child.get());

    if (ec)

        return false;

    // Mutation events might have moved this child into a different parent.

    if (child->parentNode() != this) {

        ec = NOT_FOUND_ERR;

        return false;

    }

    // FIXME: After sending the mutation events, "this" could be destroyed.

    // We can prevent that by doing a "ref", but first we have to make sure

    // that no callers call with ref count == 0 and parent = 0 (as of this

    // writing, there are definitely callers who call that way).

    forbidEventDispatch();

    // Remove from rendering tree

    if (child->attached())

        child->detach();

    // Remove the child

    Node *prev, *next;

    prev = child->previousSibling();

    next = child->nextSibling();

    if (next)

        next->setPreviousSibling(prev);

    if (prev)

        prev->setNextSibling(next);

    if (m_firstChild == child)

        m_firstChild = next;

    if (m_lastChild == child)

        m_lastChild = prev;

    child->setPreviousSibling(0);

    child->setNextSibling(0);

    child->setParent(0);

    allowEventDispatch();

    document()->setDocumentChanged(true);

    // Dispatch post-removal mutation events

    dispatchSubtreeModifiedEvent();

    if (child->inDocument())

        child->removedFromDocument();

    else

        child->removedFromTree(true);

    return child;

}

// this differs from other remove functions because it forcibly removes all the children,

// regardless of read-only status or event exceptions, e.g.

void ContainerNode::removeChildren()

{

    Node *n;

    if (!m_firstChild)

        return;

    // do any prep work needed before actually starting to detach

    // and remove... e.g. stop loading frames, fire unload events

    for (n = m_firstChild; n; n = n->nextSibling())

        willRemoveChild(n);

    forbidEventDispatch();

    while ((n = m_firstChild) != 0) {

        Node *next = n->nextSibling();

        n->ref();

        // Remove the node from the tree before calling detach or removedFromDocument (4427024, 4129744)

        n->setPreviousSibling(0);

        n->setNextSibling(0);

        n->setParent(0);

        m_firstChild = next;

        if (n == m_lastChild)

            m_lastChild = 0;

        if (n->attached())

            n->detach();

        if (n->inDocument())

            n->removedFromDocument();

        n->deref();

    }

    allowEventDispatch();

    // Dispatch a single post-removal mutation event denoting a modified subtree.

    dispatchSubtreeModifiedEvent();

}

bool ContainerNode::appendChild(PassRefPtr<Node> newChild, ExceptionCode& ec)

{

    // Check that this node is not "floating".

    // If it is, it can be deleted as a side effect of sending mutation events.

    ASSERT(refCount() || parent());

    ec = 0;

    // Make sure adding the new child is ok

    checkAddChild(newChild.get(), ec);

    if (ec)

        return 0;

    if (newChild == m_lastChild) // nothing to do

        return newChild;

    bool isFragment = newChild->nodeType() == DOCUMENT_FRAGMENT_NODE;

    // If newChild is a DocumentFragment with no children.... there's nothing to do.

    // Just return the document fragment

    if (isFragment && !newChild->firstChild())

        return true;

    // Now actually add the child(ren)

    RefPtr<Node> child = isFragment ? newChild->firstChild() : newChild;

    while (child) {

        // For a fragment we have more children to do.

        RefPtr<Node> nextChild = isFragment ? child->nextSibling() : 0;

        // If child is already present in the tree, first remove it

        if (Node* oldParent = child->parentNode()) {

            oldParent->removeChild(child.get(), ec);

            if (ec)

                return 0;

            // If the child has a parent again, just stop what we're doing, because

            // that means someone is doing something with DOM mutation -- can't re-parent

            // a child that already has a parent.

            if (child->parentNode())

                break;

        }

        // Append child to the end of the list

        forbidEventDispatch();