1/*
2 * Copyright (C) 2007 Apple Inc. All rights reserved.
3 *           (C) 2008 Nikolas Zimmermann <zimmermann@kde.org>
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 * Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU Library General Public License
16 * along with this library; see the file COPYING.LIB.  If not, write to
17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 *
20 */
21
22#ifndef ContainerNodeAlgorithms_h
23#define ContainerNodeAlgorithms_h
24
25#include "Document.h"
26#include "ElementIterator.h"
27#include "Frame.h"
28#include "HTMLFrameOwnerElement.h"
29#include "InspectorInstrumentation.h"
30#include "NodeTraversal.h"
31#include "ShadowRoot.h"
32#include <wtf/Assertions.h>
33#include <wtf/Ref.h>
34
35namespace WebCore {
36
37class ChildNodeInsertionNotifier {
38public:
39    explicit ChildNodeInsertionNotifier(ContainerNode& insertionPoint)
40        : m_insertionPoint(insertionPoint)
41    {
42    }
43
44    void notify(Node&);
45
46private:
47    void notifyDescendantInsertedIntoDocument(ContainerNode&);
48    void notifyDescendantInsertedIntoTree(ContainerNode&);
49    void notifyNodeInsertedIntoDocument(Node&);
50    void notifyNodeInsertedIntoTree(ContainerNode&);
51
52    ContainerNode& m_insertionPoint;
53    Vector<Ref<Node>> m_postInsertionNotificationTargets;
54};
55
56class ChildNodeRemovalNotifier {
57public:
58    explicit ChildNodeRemovalNotifier(ContainerNode& insertionPoint)
59        : m_insertionPoint(insertionPoint)
60    {
61    }
62
63    void notify(Node&);
64
65private:
66    void notifyDescendantRemovedFromDocument(ContainerNode&);
67    void notifyDescendantRemovedFromTree(ContainerNode&);
68    void notifyNodeRemovedFromDocument(Node&);
69    void notifyNodeRemovedFromTree(ContainerNode&);
70
71    ContainerNode& m_insertionPoint;
72};
73
74namespace Private {
75
76    template<class GenericNode, class GenericNodeContainer>
77    void addChildNodesToDeletionQueue(GenericNode*& head, GenericNode*& tail, GenericNodeContainer&);
78
79}
80
81// Helper functions for TreeShared-derived classes, which have a 'Node' style interface
82// This applies to 'ContainerNode' and 'SVGElementInstance'
83template<class GenericNode, class GenericNodeContainer>
84inline void removeDetachedChildrenInContainer(GenericNodeContainer& container)
85{
86    // List of nodes to be deleted.
87    GenericNode* head = 0;
88    GenericNode* tail = 0;
89
90    Private::addChildNodesToDeletionQueue<GenericNode, GenericNodeContainer>(head, tail, container);
91
92    GenericNode* n;
93    GenericNode* next;
94    while ((n = head) != 0) {
95        ASSERT(n->m_deletionHasBegun);
96
97        next = n->nextSibling();
98        n->setNextSibling(0);
99
100        head = next;
101        if (next == 0)
102            tail = 0;
103
104        if (n->hasChildNodes())
105            Private::addChildNodesToDeletionQueue<GenericNode, GenericNodeContainer>(head, tail, *static_cast<GenericNodeContainer*>(n));
106
107        delete n;
108    }
109}
110
111template<class GenericNode, class GenericNodeContainer>
112inline void appendChildToContainer(GenericNode* child, GenericNodeContainer& container)
113{
114    child->setParentNode(&container);
115
116    GenericNode* lastChild = container.lastChild();
117    if (lastChild) {
118        child->setPreviousSibling(lastChild);
119        lastChild->setNextSibling(child);
120    } else
121        container.setFirstChild(child);
122
123    container.setLastChild(child);
124}
125
126// Helper methods for removeDetachedChildrenInContainer, hidden from WebCore namespace
127namespace Private {
128
129    template<class GenericNode, class GenericNodeContainer, bool dispatchRemovalNotification>
130    struct NodeRemovalDispatcher {
131        static void dispatch(GenericNode&, GenericNodeContainer&)
132        {
133            // no-op, by default
134        }
135    };
136
137    template<class GenericNode, class GenericNodeContainer>
138    struct NodeRemovalDispatcher<GenericNode, GenericNodeContainer, true> {
139        static void dispatch(GenericNode& node, GenericNodeContainer& container)
140        {
141            // Clean up any TreeScope to a removed tree.
142            if (Document* containerDocument = container.ownerDocument())
143                containerDocument->adoptIfNeeded(&node);
144            if (node.inDocument())
145                ChildNodeRemovalNotifier(container).notify(node);
146        }
147    };
148
149    template<class GenericNode>
150    struct ShouldDispatchRemovalNotification {
151        static const bool value = false;
152    };
153
154    template<>
155    struct ShouldDispatchRemovalNotification<Node> {
156        static const bool value = true;
157    };
158
159    template<class GenericNode, class GenericNodeContainer>
160    void addChildNodesToDeletionQueue(GenericNode*& head, GenericNode*& tail, GenericNodeContainer& container)
161    {
162        // We have to tell all children that their parent has died.
163        GenericNode* next = 0;
164        for (GenericNode* n = container.firstChild(); n != 0; n = next) {
165            ASSERT(!n->m_deletionHasBegun);
166
167            next = n->nextSibling();
168            n->setNextSibling(0);
169            n->setParentNode(0);
170            container.setFirstChild(next);
171            if (next)
172                next->setPreviousSibling(0);
173
174            if (!n->refCount()) {
175#ifndef NDEBUG
176                n->m_deletionHasBegun = true;
177#endif
178                // Add the node to the list of nodes to be deleted.
179                // Reuse the nextSibling pointer for this purpose.
180                if (tail)
181                    tail->setNextSibling(n);
182                else
183                    head = n;
184
185                tail = n;
186            } else {
187                Ref<GenericNode> protect(*n); // removedFromDocument may remove remove all references to this node.
188                NodeRemovalDispatcher<GenericNode, GenericNodeContainer, ShouldDispatchRemovalNotification<GenericNode>::value>::dispatch(*n, container);
189            }
190        }
191
192        container.setLastChild(0);
193    }
194
195} // namespace Private
196
197inline void ChildNodeInsertionNotifier::notifyNodeInsertedIntoDocument(Node& node)
198{
199    ASSERT(m_insertionPoint.inDocument());
200    if (Node::InsertionShouldCallDidNotifySubtreeInsertions == node.insertedInto(m_insertionPoint))
201        m_postInsertionNotificationTargets.append(node);
202    if (node.isContainerNode())
203        notifyDescendantInsertedIntoDocument(toContainerNode(node));
204}
205
206inline void ChildNodeInsertionNotifier::notifyNodeInsertedIntoTree(ContainerNode& node)
207{
208    NoEventDispatchAssertion assertNoEventDispatch;
209    ASSERT(!m_insertionPoint.inDocument());
210
211    if (Node::InsertionShouldCallDidNotifySubtreeInsertions == node.insertedInto(m_insertionPoint))
212        m_postInsertionNotificationTargets.append(node);
213    notifyDescendantInsertedIntoTree(node);
214}
215
216inline void ChildNodeInsertionNotifier::notify(Node& node)
217{
218    ASSERT(!NoEventDispatchAssertion::isEventDispatchForbidden());
219
220#if ENABLE(INSPECTOR)
221    InspectorInstrumentation::didInsertDOMNode(&node.document(), &node);
222#endif
223
224    Ref<Document> protectDocument(node.document());
225    Ref<Node> protectNode(node);
226
227    if (m_insertionPoint.inDocument())
228        notifyNodeInsertedIntoDocument(node);
229    else if (node.isContainerNode())
230        notifyNodeInsertedIntoTree(toContainerNode(node));
231
232    for (size_t i = 0; i < m_postInsertionNotificationTargets.size(); ++i)
233        m_postInsertionNotificationTargets[i]->didNotifySubtreeInsertions(&m_insertionPoint);
234}
235
236
237inline void ChildNodeRemovalNotifier::notifyNodeRemovedFromDocument(Node& node)
238{
239    ASSERT(m_insertionPoint.inDocument());
240    node.removedFrom(m_insertionPoint);
241
242    if (node.isContainerNode())
243        notifyDescendantRemovedFromDocument(toContainerNode(node));
244}
245
246inline void ChildNodeRemovalNotifier::notifyNodeRemovedFromTree(ContainerNode& node)
247{
248    NoEventDispatchAssertion assertNoEventDispatch;
249    ASSERT(!m_insertionPoint.inDocument());
250
251    node.removedFrom(m_insertionPoint);
252    notifyDescendantRemovedFromTree(node);
253}
254
255inline void ChildNodeRemovalNotifier::notify(Node& node)
256{
257    if (node.inDocument()) {
258        notifyNodeRemovedFromDocument(node);
259        node.document().notifyRemovePendingSheetIfNeeded();
260    } else if (node.isContainerNode())
261        notifyNodeRemovedFromTree(toContainerNode(node));
262}
263
264enum SubframeDisconnectPolicy {
265    RootAndDescendants,
266    DescendantsOnly
267};
268void disconnectSubframes(ContainerNode& root, SubframeDisconnectPolicy);
269
270inline void disconnectSubframesIfNeeded(ContainerNode& root, SubframeDisconnectPolicy policy)
271{
272    if (!root.connectedSubframeCount())
273        return;
274    disconnectSubframes(root, policy);
275}
276
277} // namespace WebCore
278
279#endif // ContainerNodeAlgorithms_h
280