/*

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

#include "BeforeLoadEvent.h"

#include "Cache.h"

#include "ContainerNodeAlgorithms.h"

#include "DeleteButtonController.h"

#include "EventNames.h"

#include "ExceptionCode.h"

#include "FloatRect.h"

#include "Frame.h"

#include "FrameView.h"

#include "InlineTextBox.h"

#include "InspectorController.h"

#include "MutationEvent.h"

#include "Page.h"

#include "RenderBox.h"

#include "RenderTheme.h"

#include "RootInlineBox.h"

#include "loader.h"

#include <wtf/CurrentTime.h>

#include <wtf/Vector.h>

namespace WebCore {

static void notifyChildInserted(Node*);

static void dispatchChildInsertionEvents(Node*);

static void dispatchChildRemovalEvents(Node*);

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

typedef Vector<RefPtr<Node>, 1> NodeVector;

static NodeCallbackQueue* s_postAttachCallbackQueue;

static size_t s_attachDepth;

static bool s_shouldReEnableMemoryCacheCallsAfterAttach;

static void collectTargetNodes(Node* node, NodeVector& nodes)

{

    if (node->nodeType() != Node::DOCUMENT_FRAGMENT_NODE) {

        nodes.append(node);

        return;

    }

    for (Node* child = node->firstChild(); child; child = child->nextSibling())

        nodes.append(child);

}

void ContainerNode::removeAllChildren()

{

    removeAllChildrenInContainer<Node, ContainerNode>(this);

}

ContainerNode::~ContainerNode()

{

    removeAllChildren();

}

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

{

    // 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, shouldLazyAttach);

    // 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;

    }

    NodeVector targets;

    collectTargetNodes(newChild.get(), targets);

    if (targets.isEmpty())

        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> refChildPreviousSibling = refChild->previousSibling();

    for (NodeVector::const_iterator it = targets.begin(); it != targets.end(); ++it) {

        Node* child = it->get();

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

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

            oldParent->removeChild(child, 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).

        // 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);

        if (prev) {

            ASSERT(m_firstChild != next);

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

            prev->setNextSibling(child);

        } else {

            ASSERT(m_firstChild == next);

            m_firstChild = child;

        }

        child->setParent(this);

        child->setPreviousSibling(prev);

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

        allowEventDispatch();

        // Send notification about the children change.

        childrenChanged(false, refChildPreviousSibling.get(), next.get(), 1);

        notifyChildInserted(child);

        // Add child to the rendering tree.

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

            if (shouldLazyAttach)

                child->lazyAttach();

            else

                child->attach();

        }

        // Now that the child is attached to the render tree, dispatch

        // the relevant mutation events.

        dispatchChildInsertionEvents(child);

    }

    dispatchSubtreeModifiedEvent();

    return true;

}

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

{

    // 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();

    RefPtr<Node> next = oldChild->nextSibling();

    // 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 false;

        // 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();

        childrenChanged(false, prev.get(), next, 1);

        notifyChildInserted(child.get());

        // Add child to the rendering tree

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

            if (shouldLazyAttach)

                child->lazyAttach();

            else

                child->attach();

        }

        // Now that the child is attached to the render tree, dispatch

        // the relevant mutation events.

        dispatchChildInsertionEvents(child.get());

        prev = child;

        child = nextChild.release();

    }

    dispatchSubtreeModifiedEvent();

    return true;

}

void ContainerNode::willRemove()

{

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

        n->willRemove();

    Node::willRemove();

}

static void willRemoveChild(Node* child)

{

    // update auxiliary doc info (e.g. iterators) to note that node is being removed

    child->document()->nodeWillBeRemoved(child);

    child->document()->incDOMTreeVersion();

    // fire removed from document mutation events.

    dispatchChildRemovalEvents(child);

    if (child->attached())

        child->willRemove();

}

static void willRemoveChildren(ContainerNode* container)

{

    container->document()->nodeChildrenWillBeRemoved(container);

    container->document()->incDOMTreeVersion();

    // FIXME: Adding new children from event handlers can cause an infinite loop here.

    for (RefPtr<Node> child = container->firstChild(); child; child = child->nextSibling()) {

        // fire removed from document mutation events.

        dispatchChildRemovalEvents(child.get());

        if (child->attached())

            child->willRemove();

    }

}

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;

    willRemoveChild(child.get());

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

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

        ec = NOT_FOUND_ERR;

        return false;

    }

    document()->removeFocusedNodeOfSubtree(child.get());

    // Events fired when blurring currently focused node 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();

    // Dispatch post-removal mutation events

    childrenChanged(false, prev, next, -1);

    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.

bool ContainerNode::removeChildren()

{

    if (!m_firstChild)

        return false;

    // The container node can be removed from event handlers.

    RefPtr<ContainerNode> protect(this);

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

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

    willRemoveChildren(protect.get());

    // exclude this node when looking for removed focusedNode since only children will be removed

    document()->removeFocusedNodeOfSubtree(this, true);

    forbidEventDispatch();

    Vector<RefPtr<Node> > removedChildren;

    while (RefPtr<Node> n = m_firstChild) {

        Node* next = n->nextSibling();

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

        // removeChild() does this after calling detach(). There is no explanation for

        // this discrepancy between removeChild() and its optimized version removeChildren().

        n->setPreviousSibling(0);

        n->setNextSibling(0);

        n->setParent(0);

        m_firstChild = next;

        if (n == m_lastChild)

            m_lastChild = 0;

        if (n->attached())

            n->detach();

        removedChildren.append(n.release());

    }

    allowEventDispatch();

    size_t removedChildrenCount = removedChildren.size();

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

    childrenChanged(false, 0, 0, -static_cast<int>(removedChildrenCount));

    dispatchSubtreeModifiedEvent();

    for (size_t i = 0; i < removedChildrenCount; ++i) {

        Node* removedChild = removedChildren[i].get();

        if (removedChild->inDocument())

            removedChild->removedFromDocument();

        // removeChild() calls removedFromTree(true) if the child was not in the

        // document. There is no explanation for this discrepancy between removeChild()

        // and its optimized version removeChildren().

    }

    return true;

}

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

{

    // 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 false;

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

        return newChild;

    NodeVector targets;

    collectTargetNodes(newChild.get(), targets);

    if (targets.isEmpty())

        return true;

    // Now actually add the child(ren)

    RefPtr<Node> prev = lastChild();

    for (NodeVector::const_iterator it = targets.begin(); it != targets.end(); ++it) {

        Node* child = it->get();

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

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

            oldParent->removeChild(child, ec);

            if (ec)

                return false;

            // 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();

        child->setParent(this);

        if (m_lastChild) {

            child->setPreviousSibling(m_lastChild);

            m_lastChild->setNextSibling(child);

        } else

            m_firstChild = child;

        m_lastChild = child;

        allowEventDispatch();

        // Send notification about the children change.

        childrenChanged(false, prev.get(), 0, 1);

        notifyChildInserted(child);

        // Add child to the rendering tree

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

            if (shouldLazyAttach)

                child->lazyAttach();

            else

                child->attach();

        }

        // Now that the child is attached to the render tree, dispatch

        // the relevant mutation events.