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 "Frame.h"
27#include "HTMLFrameOwnerElement.h"
28#include "InspectorInstrumentation.h"
29#include "NodeTraversal.h"
30#include <wtf/Assertions.h>
31
32namespace WebCore {
33
34class ChildNodeInsertionNotifier {
35public:
36    explicit ChildNodeInsertionNotifier(ContainerNode* insertionPoint)
37        : m_insertionPoint(insertionPoint)
38    {
39    }
40
41    void notify(Node*);
42
43private:
44    void notifyDescendantInsertedIntoDocument(ContainerNode*);
45    void notifyDescendantInsertedIntoTree(ContainerNode*);
46    void notifyNodeInsertedIntoDocument(Node*);
47    void notifyNodeInsertedIntoTree(ContainerNode*);
48
49    ContainerNode* m_insertionPoint;
50    Vector< RefPtr<Node> > m_postInsertionNotificationTargets;
51};
52
53class ChildNodeRemovalNotifier {
54public:
55    explicit ChildNodeRemovalNotifier(ContainerNode* insertionPoint)
56        : m_insertionPoint(insertionPoint)
57    {
58    }
59
60    void notify(Node*);
61
62private:
63    void notifyDescendantRemovedFromDocument(ContainerNode*);
64    void notifyDescendantRemovedFromTree(ContainerNode*);
65    void notifyNodeRemovedFromDocument(Node*);
66    void notifyNodeRemovedFromTree(ContainerNode*);
67
68    ContainerNode* m_insertionPoint;
69};
70
71namespace Private {
72
73    template<class GenericNode, class GenericNodeContainer>
74    void addChildNodesToDeletionQueue(GenericNode*& head, GenericNode*& tail, GenericNodeContainer*);
75
76}
77
78// Helper functions for TreeShared-derived classes, which have a 'Node' style interface
79// This applies to 'ContainerNode' and 'SVGElementInstance'
80template<class GenericNode, class GenericNodeContainer>
81inline void removeDetachedChildrenInContainer(GenericNodeContainer* container)
82{
83    // List of nodes to be deleted.
84    GenericNode* head = 0;
85    GenericNode* tail = 0;
86
87    Private::addChildNodesToDeletionQueue<GenericNode, GenericNodeContainer>(head, tail, container);
88
89    GenericNode* n;
90    GenericNode* next;
91    while ((n = head) != 0) {
92        ASSERT(n->m_deletionHasBegun);
93
94        next = n->nextSibling();
95        n->setNextSibling(0);
96
97        head = next;
98        if (next == 0)
99            tail = 0;
100
101        if (n->hasChildNodes())
102            Private::addChildNodesToDeletionQueue<GenericNode, GenericNodeContainer>(head, tail, static_cast<GenericNodeContainer*>(n));
103
104        delete n;
105    }
106}
107
108template<class GenericNode, class GenericNodeContainer>
109inline void appendChildToContainer(GenericNode* child, GenericNodeContainer* container)
110{
111    child->setParentOrShadowHostNode(container);
112
113    GenericNode* lastChild = container->lastChild();
114    if (lastChild) {
115        child->setPreviousSibling(lastChild);
116        lastChild->setNextSibling(child);
117    } else
118        container->setFirstChild(child);
119
120    container->setLastChild(child);
121}
122
123// Helper methods for removeDetachedChildrenInContainer, hidden from WebCore namespace
124namespace Private {
125
126    template<class GenericNode, class GenericNodeContainer, bool dispatchRemovalNotification>
127    struct NodeRemovalDispatcher {
128        static void dispatch(GenericNode*, GenericNodeContainer*)
129        {
130            // no-op, by default
131        }
132    };
133
134    template<class GenericNode, class GenericNodeContainer>
135    struct NodeRemovalDispatcher<GenericNode, GenericNodeContainer, true> {
136        static void dispatch(GenericNode* node, GenericNodeContainer* container)
137        {
138            // Clean up any TreeScope to a removed tree.
139            if (Document* containerDocument = container->ownerDocument())
140                containerDocument->adoptIfNeeded(node);
141            if (node->inDocument())
142                ChildNodeRemovalNotifier(container).notify(node);
143        }
144    };
145
146    template<class GenericNode>
147    struct ShouldDispatchRemovalNotification {
148        static const bool value = false;
149    };
150
151    template<>
152    struct ShouldDispatchRemovalNotification<Node> {
153        static const bool value = true;
154    };
155
156    template<class GenericNode, class GenericNodeContainer>
157    void addChildNodesToDeletionQueue(GenericNode*& head, GenericNode*& tail, GenericNodeContainer* container)
158    {
159        // We have to tell all children that their parent has died.
160        GenericNode* next = 0;
161        for (GenericNode* n = container->firstChild(); n != 0; n = next) {
162            ASSERT(!n->m_deletionHasBegun);
163
164            next = n->nextSibling();
165            n->setNextSibling(0);
166            n->setParentOrShadowHostNode(0);
167            container->setFirstChild(next);
168            if (next)
169                next->setPreviousSibling(0);
170
171            if (!n->refCount()) {
172#ifndef NDEBUG
173                n->m_deletionHasBegun = true;
174#endif
175                // Add the node to the list of nodes to be deleted.
176                // Reuse the nextSibling pointer for this purpose.
177                if (tail)
178                    tail->setNextSibling(n);
179                else
180                    head = n;
181
182                tail = n;
183            } else {
184                RefPtr<GenericNode> protect(n); // removedFromDocument may remove remove all references to this node.
185                NodeRemovalDispatcher<GenericNode, GenericNodeContainer, ShouldDispatchRemovalNotification<GenericNode>::value>::dispatch(n, container);
186            }
187        }
188
189        container->setLastChild(0);
190    }
191
192} // namespace Private
193
194inline void ChildNodeInsertionNotifier::notifyNodeInsertedIntoDocument(Node* node)
195{
196    ASSERT(m_insertionPoint->inDocument());
197    RefPtr<Node> protect(node);
198    if (Node::InsertionShouldCallDidNotifySubtreeInsertions == node->insertedInto(m_insertionPoint))
199        m_postInsertionNotificationTargets.append(node);
200    if (node->isContainerNode())
201        notifyDescendantInsertedIntoDocument(toContainerNode(node));
202}
203
204inline void ChildNodeInsertionNotifier::notifyNodeInsertedIntoTree(ContainerNode* node)
205{
206    NoEventDispatchAssertion assertNoEventDispatch;
207    ASSERT(!m_insertionPoint->inDocument());
208
209    if (Node::InsertionShouldCallDidNotifySubtreeInsertions == node->insertedInto(m_insertionPoint))
210        m_postInsertionNotificationTargets.append(node);
211    notifyDescendantInsertedIntoTree(node);
212}
213
214inline void ChildNodeInsertionNotifier::notify(Node* node)
215{
216    ASSERT(!NoEventDispatchAssertion::isEventDispatchForbidden());
217
218#if ENABLE(INSPECTOR)
219    InspectorInstrumentation::didInsertDOMNode(node->document(), node);
220#endif
221
222    RefPtr<Document> protectDocument(node->document());
223    RefPtr<Node> protectNode(node);
224
225    if (m_insertionPoint->inDocument())
226        notifyNodeInsertedIntoDocument(node);
227    else if (node->isContainerNode())
228        notifyNodeInsertedIntoTree(toContainerNode(node));
229
230    for (size_t i = 0; i < m_postInsertionNotificationTargets.size(); ++i)
231        m_postInsertionNotificationTargets[i]->didNotifySubtreeInsertions(m_insertionPoint);
232}
233
234
235inline void ChildNodeRemovalNotifier::notifyNodeRemovedFromDocument(Node* node)
236{
237    ASSERT(m_insertionPoint->inDocument());
238    node->removedFrom(m_insertionPoint);
239
240    if (node->isContainerNode())
241        notifyDescendantRemovedFromDocument(toContainerNode(node));
242}
243
244inline void ChildNodeRemovalNotifier::notifyNodeRemovedFromTree(ContainerNode* node)
245{
246    NoEventDispatchAssertion assertNoEventDispatch;
247    ASSERT(!m_insertionPoint->inDocument());
248
249    node->removedFrom(m_insertionPoint);
250    notifyDescendantRemovedFromTree(node);
251}
252
253inline void ChildNodeRemovalNotifier::notify(Node* node)
254{
255    if (node->inDocument()) {
256        notifyNodeRemovedFromDocument(node);
257        node->document()->notifyRemovePendingSheetIfNeeded();
258    } else if (node->isContainerNode())
259        notifyNodeRemovedFromTree(toContainerNode(node));
260}
261
262class ChildFrameDisconnector {
263public:
264    enum DisconnectPolicy {
265        RootAndDescendants,
266        DescendantsOnly
267    };
268
269    explicit ChildFrameDisconnector(Node* root)
270        : m_root(root)
271    {
272    }
273
274    void disconnect(DisconnectPolicy = RootAndDescendants);
275
276private:
277    void collectFrameOwners(Node* root);
278    void collectFrameOwners(ElementShadow*);
279    void disconnectCollectedFrameOwners();
280
281    Vector<RefPtr<HTMLFrameOwnerElement>, 10> m_frameOwners;
282    Node* m_root;
283};
284
285#ifndef NDEBUG
286unsigned assertConnectedSubrameCountIsConsistent(Node*);
287#endif
288
289inline void ChildFrameDisconnector::collectFrameOwners(Node* root)
290{
291    if (!root->connectedSubframeCount())
292        return;
293
294    if (root->isHTMLElement() && root->isFrameOwnerElement())
295        m_frameOwners.append(toFrameOwnerElement(root));
296
297    for (Node* child = root->firstChild(); child; child = child->nextSibling())
298        collectFrameOwners(child);
299
300    ElementShadow* shadow = root->isElementNode() ? toElement(root)->shadow() : 0;
301    if (shadow)
302        collectFrameOwners(shadow);
303}
304
305inline void ChildFrameDisconnector::disconnectCollectedFrameOwners()
306{
307    // Must disable frame loading in the subtree so an unload handler cannot
308    // insert more frames and create loaded frames in detached subtrees.
309    SubframeLoadingDisabler disabler(m_root);
310
311    for (unsigned i = 0; i < m_frameOwners.size(); ++i) {
312        HTMLFrameOwnerElement* owner = m_frameOwners[i].get();
313        // Don't need to traverse up the tree for the first owner since no
314        // script could have moved it.
315        if (!i || m_root->containsIncludingShadowDOM(owner))
316            owner->disconnectContentFrame();
317    }
318}
319
320inline void ChildFrameDisconnector::disconnect(DisconnectPolicy policy)
321{
322#ifndef NDEBUG
323    assertConnectedSubrameCountIsConsistent(m_root);
324#endif
325
326    if (!m_root->connectedSubframeCount())
327        return;
328
329    if (policy == RootAndDescendants)
330        collectFrameOwners(m_root);
331    else {
332        for (Node* child = m_root->firstChild(); child; child = child->nextSibling())
333            collectFrameOwners(child);
334    }
335
336    disconnectCollectedFrameOwners();
337}
338
339} // namespace WebCore
340
341#endif // ContainerNodeAlgorithms_h
342