ffb201a38300d045496402b43a2fb30bb78c75f0
[WebKit-https.git] / Source / WebCore / dom / ContainerNodeAlgorithms.cpp
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  *           (C) 2001 Dirk Mueller (mueller@kde.org)
5  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2015 Apple Inc. All rights reserved.
6  * Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies)
7  * Copyright (C) 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
8  * Copyright (C) 2012 Google Inc. All rights reserved.
9  *
10  * This library is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU Library General Public
12  * License as published by the Free Software Foundation; either
13  * version 2 of the License, or (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18  * Library General Public License for more details.
19  *
20  * You should have received a copy of the GNU Library General Public License
21  * along with this library; see the file COPYING.LIB.  If not, write to
22  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
23  * Boston, MA 02110-1301, USA.
24  */
25
26 #include "config.h"
27 #include "ContainerNodeAlgorithms.h"
28
29 #include "HTMLFrameOwnerElement.h"
30 #include "HTMLTextAreaElement.h"
31 #include "InspectorInstrumentation.h"
32 #include "NoEventDispatchAssertion.h"
33 #include "ShadowRoot.h"
34 #include "TypedElementDescendantIterator.h"
35
36 namespace WebCore {
37
38 static void notifyNodeInsertedIntoDocument(ContainerNode& insertionPoint, Node& node, NodeVector& postInsertionNotificationTargets)
39 {
40     ASSERT(insertionPoint.isConnected());
41     if (node.insertedInto(insertionPoint) == Node::InsertionShouldCallFinishedInsertingSubtree)
42         postInsertionNotificationTargets.append(node);
43
44     if (!is<ContainerNode>(node))
45         return;
46
47     ChildNodesLazySnapshot snapshot(downcast<ContainerNode>(node));
48     while (RefPtr<Node> child = snapshot.nextNode()) {
49         // If we have been removed from the document during this loop, then
50         // we don't want to tell the rest of our children that they've been
51         // inserted into the document because they haven't.
52         if (node.isConnected() && child->parentNode() == &node)
53             notifyNodeInsertedIntoDocument(insertionPoint, *child, postInsertionNotificationTargets);
54     }
55
56     if (!is<Element>(node))
57         return;
58
59     if (RefPtr<ShadowRoot> root = downcast<Element>(node).shadowRoot()) {
60         if (node.isConnected() && root->host() == &node)
61             notifyNodeInsertedIntoDocument(insertionPoint, *root, postInsertionNotificationTargets);
62     }
63 }
64
65 static void notifyNodeInsertedIntoTree(ContainerNode& insertionPoint, Node& node, NodeVector& postInsertionNotificationTargets)
66 {
67     NoEventDispatchAssertion assertNoEventDispatch;
68     ASSERT(!insertionPoint.isConnected());
69
70     if (node.insertedInto(insertionPoint) == Node::InsertionShouldCallFinishedInsertingSubtree)
71         postInsertionNotificationTargets.append(node);
72
73     if (!is<ContainerNode>(node))
74         return;
75
76     for (auto* child = downcast<ContainerNode>(node).firstChild(); child; child = child->nextSibling())
77         notifyNodeInsertedIntoTree(insertionPoint, *child, postInsertionNotificationTargets);
78
79     if (!is<Element>(node))
80         return;
81
82     if (RefPtr<ShadowRoot> root = downcast<Element>(node).shadowRoot())
83         notifyNodeInsertedIntoTree(insertionPoint, *root, postInsertionNotificationTargets);
84 }
85
86 void notifyChildNodeInserted(ContainerNode& insertionPoint, Node& node, NodeVector& postInsertionNotificationTargets)
87 {
88     RELEASE_ASSERT(NoEventDispatchAssertion::isEventDispatchAllowedInSubtree(insertionPoint));
89
90     InspectorInstrumentation::didInsertDOMNode(node.document(), node);
91
92     Ref<Document> protectDocument(node.document());
93     Ref<Node> protectNode(node);
94
95     if (insertionPoint.isConnected())
96         notifyNodeInsertedIntoDocument(insertionPoint, node, postInsertionNotificationTargets);
97     else
98         notifyNodeInsertedIntoTree(insertionPoint, node, postInsertionNotificationTargets);
99 }
100
101 static void notifyNodeRemovedFromDocument(ContainerNode& insertionPoint, Node& node)
102 {
103     ASSERT(insertionPoint.isConnected());
104     node.removedFrom(insertionPoint);
105
106     if (!is<ContainerNode>(node))
107         return;
108
109     ChildNodesLazySnapshot snapshot(downcast<ContainerNode>(node));
110     while (RefPtr<Node> child = snapshot.nextNode()) {
111         // If we have been added to the document during this loop, then we
112         // don't want to tell the rest of our children that they've been
113         // removed from the document because they haven't.
114         if (!node.isConnected() && child->parentNode() == &node)
115             notifyNodeRemovedFromDocument(insertionPoint, *child.get());
116     }
117
118     if (!is<Element>(node))
119         return;
120
121     if (node.document().cssTarget() == &node)
122         node.document().setCSSTarget(nullptr);
123
124     if (RefPtr<ShadowRoot> root = downcast<Element>(node).shadowRoot()) {
125         if (!node.isConnected() && root->host() == &node)
126             notifyNodeRemovedFromDocument(insertionPoint, *root.get());
127     }
128 }
129
130 static void notifyNodeRemovedFromTree(ContainerNode& insertionPoint, Node& node)
131 {
132     NoEventDispatchAssertion assertNoEventDispatch;
133     ASSERT(!insertionPoint.isConnected());
134
135     node.removedFrom(insertionPoint);
136
137     for (Node* child = node.firstChild(); child; child = child->nextSibling())
138         notifyNodeRemovedFromTree(insertionPoint, *child);
139
140     if (!is<Element>(node))
141         return;
142
143     if (RefPtr<ShadowRoot> root = downcast<Element>(node).shadowRoot())
144         notifyNodeRemovedFromTree(insertionPoint, *root);
145 }
146
147 void notifyChildNodeRemoved(ContainerNode& insertionPoint, Node& child)
148 {
149     if (child.isConnected())
150         notifyNodeRemovedFromDocument(insertionPoint, child);
151     else
152         notifyNodeRemovedFromTree(insertionPoint, child);
153 }
154
155 void addChildNodesToDeletionQueue(Node*& head, Node*& tail, ContainerNode& container)
156 {
157     // We have to tell all children that their parent has died.
158     RefPtr<Node> next = nullptr;
159     for (RefPtr<Node> node = container.firstChild(); node; node = next) {
160         ASSERT(!node->m_deletionHasBegun);
161
162         next = node->nextSibling();
163         node->setNextSibling(nullptr);
164         node->setParentNode(nullptr);
165         container.setFirstChild(next.get());
166         if (next)
167             next->setPreviousSibling(nullptr);
168
169         if (!node->refCount()) {
170 #ifndef NDEBUG
171             node->m_deletionHasBegun = true;
172 #endif
173             // Add the node to the list of nodes to be deleted.
174             // Reuse the nextSibling pointer for this purpose.
175             if (tail)
176                 tail->setNextSibling(node.get());
177             else
178                 head = node.get();
179
180             tail = node.get();
181         } else {
182             node->setTreeScopeRecursively(container.document());
183             if (node->isInTreeScope())
184                 notifyChildNodeRemoved(container, *node);
185             ASSERT_WITH_SECURITY_IMPLICATION(!node->isInTreeScope());
186         }
187     }
188
189     container.setLastChild(nullptr);
190 }
191
192 void removeDetachedChildrenInContainer(ContainerNode& container)
193 {
194     // List of nodes to be deleted.
195     Node* head = nullptr;
196     Node* tail = nullptr;
197
198     addChildNodesToDeletionQueue(head, tail, container);
199
200     Node* node;
201     Node* next;
202     while ((node = head)) {
203         ASSERT(node->m_deletionHasBegun);
204
205         next = node->nextSibling();
206         node->setNextSibling(nullptr);
207
208         head = next;
209         if (!next)
210             tail = nullptr;
211
212         if (is<ContainerNode>(*node))
213             addChildNodesToDeletionQueue(head, tail, downcast<ContainerNode>(*node));
214         
215         delete node;
216     }
217 }
218
219 #ifndef NDEBUG
220 static unsigned assertConnectedSubrameCountIsConsistent(ContainerNode& node)
221 {
222     unsigned count = 0;
223
224     if (is<Element>(node)) {
225         if (is<HTMLFrameOwnerElement>(node) && downcast<HTMLFrameOwnerElement>(node).contentFrame())
226             ++count;
227
228         if (ShadowRoot* root = downcast<Element>(node).shadowRoot())
229             count += assertConnectedSubrameCountIsConsistent(*root);
230     }
231
232     for (auto& child : childrenOfType<Element>(node))
233         count += assertConnectedSubrameCountIsConsistent(child);
234
235     // If we undercount there's possibly a security bug since we'd leave frames
236     // in subtrees outside the document.
237     ASSERT(node.connectedSubframeCount() >= count);
238
239     // If we overcount it's safe, but not optimal because it means we'll traverse
240     // through the document in disconnectSubframes looking for frames that have
241     // already been disconnected.
242     ASSERT(node.connectedSubframeCount() == count);
243
244     return count;
245 }
246 #endif
247
248 static void collectFrameOwners(Vector<Ref<HTMLFrameOwnerElement>>& frameOwners, ContainerNode& root)
249 {
250     auto elementDescendants = descendantsOfType<Element>(root);
251     auto it = elementDescendants.begin();
252     auto end = elementDescendants.end();
253     while (it != end) {
254         Element& element = *it;
255         if (!element.connectedSubframeCount()) {
256             it.traverseNextSkippingChildren();
257             continue;
258         }
259
260         if (is<HTMLFrameOwnerElement>(element))
261             frameOwners.append(downcast<HTMLFrameOwnerElement>(element));
262
263         if (ShadowRoot* shadowRoot = element.shadowRoot())
264             collectFrameOwners(frameOwners, *shadowRoot);
265         ++it;
266     }
267 }
268
269 void disconnectSubframes(ContainerNode& root, SubframeDisconnectPolicy policy)
270 {
271 #ifndef NDEBUG
272     assertConnectedSubrameCountIsConsistent(root);
273 #endif
274     ASSERT(root.connectedSubframeCount());
275
276     Vector<Ref<HTMLFrameOwnerElement>> frameOwners;
277
278     if (policy == RootAndDescendants) {
279         if (is<HTMLFrameOwnerElement>(root))
280             frameOwners.append(downcast<HTMLFrameOwnerElement>(root));
281     }
282
283     collectFrameOwners(frameOwners, root);
284
285     if (auto* shadowRoot = root.shadowRoot())
286         collectFrameOwners(frameOwners, *shadowRoot);
287
288     // Must disable frame loading in the subtree so an unload handler cannot
289     // insert more frames and create loaded frames in detached subtrees.
290     SubframeLoadingDisabler disabler(&root);
291
292     bool isFirst = true;
293     for (auto& owner : frameOwners) {
294         // Don't need to traverse up the tree for the first owner since no
295         // script could have moved it.
296         if (isFirst || root.containsIncludingShadowDOM(&owner.get()))
297             owner.get().disconnectContentFrame();
298         isFirst = false;
299     }
300 }
301
302 }