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