Make opaque root scanning truly constraint-based
[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 "InspectorInstrumentation.h"
31 #include "NoEventDispatchAssertion.h"
32 #include "ShadowRoot.h"
33
34 namespace WebCore {
35
36 static void notifyNodeInsertedIntoTree(ContainerNode& insertionPoint, ContainerNode&, NodeVector& postInsertionNotificationTargets);
37 static void notifyNodeInsertedIntoDocument(ContainerNode& insertionPoint, Node&, NodeVector& postInsertionNotificationTargets);
38 static void notifyNodeRemovedFromTree(ContainerNode& insertionPoint, ContainerNode&);
39 static void notifyNodeRemovedFromDocument(ContainerNode& insertionPoint, Node&);
40
41 static void notifyDescendantInsertedIntoDocument(ContainerNode& insertionPoint, ContainerNode& node, NodeVector& postInsertionNotificationTargets)
42 {
43     ChildNodesLazySnapshot snapshot(node);
44     while (RefPtr<Node> child = snapshot.nextNode()) {
45         // If we have been removed from the document during this loop, then
46         // we don't want to tell the rest of our children that they've been
47         // inserted into the document because they haven't.
48         if (node.inDocument() && child->parentNode() == &node)
49             notifyNodeInsertedIntoDocument(insertionPoint, *child, postInsertionNotificationTargets);
50     }
51
52     if (!is<Element>(node))
53         return;
54
55     if (RefPtr<ShadowRoot> root = downcast<Element>(node).shadowRoot()) {
56         if (node.inDocument() && root->host() == &node)
57             notifyNodeInsertedIntoDocument(insertionPoint, *root, postInsertionNotificationTargets);
58     }
59 }
60
61 static void notifyDescendantInsertedIntoTree(ContainerNode& insertionPoint, ContainerNode& node, NodeVector& postInsertionNotificationTargets)
62 {
63     for (Node* child = node.firstChild(); child; child = child->nextSibling()) {
64         if (is<ContainerNode>(*child))
65             notifyNodeInsertedIntoTree(insertionPoint, downcast<ContainerNode>(*child), postInsertionNotificationTargets);
66     }
67
68     if (ShadowRoot* root = node.shadowRoot())
69         notifyNodeInsertedIntoTree(insertionPoint, *root, postInsertionNotificationTargets);
70 }
71
72 void notifyNodeInsertedIntoDocument(ContainerNode& insertionPoint, Node& node, NodeVector& postInsertionNotificationTargets)
73 {
74     ASSERT(insertionPoint.inDocument());
75     if (node.insertedInto(insertionPoint) == Node::InsertionShouldCallFinishedInsertingSubtree)
76         postInsertionNotificationTargets.append(node);
77     if (is<ContainerNode>(node))
78         notifyDescendantInsertedIntoDocument(insertionPoint, downcast<ContainerNode>(node), postInsertionNotificationTargets);
79 }
80
81 void notifyNodeInsertedIntoTree(ContainerNode& insertionPoint, ContainerNode& node, NodeVector& postInsertionNotificationTargets)
82 {
83     NoEventDispatchAssertion assertNoEventDispatch;
84     ASSERT(!insertionPoint.inDocument());
85
86     if (node.insertedInto(insertionPoint) == Node::InsertionShouldCallFinishedInsertingSubtree)
87         postInsertionNotificationTargets.append(node);
88     notifyDescendantInsertedIntoTree(insertionPoint, node, postInsertionNotificationTargets);
89 }
90
91 void notifyChildNodeInserted(ContainerNode& insertionPoint, Node& node, NodeVector& postInsertionNotificationTargets)
92 {
93     ASSERT_WITH_SECURITY_IMPLICATION(!NoEventDispatchAssertion::isEventDispatchForbidden());
94
95     InspectorInstrumentation::didInsertDOMNode(node.document(), node);
96
97     Ref<Document> protectDocument(node.document());
98     Ref<Node> protectNode(node);
99
100     if (insertionPoint.inDocument())
101         notifyNodeInsertedIntoDocument(insertionPoint, node, postInsertionNotificationTargets);
102     else if (is<ContainerNode>(node))
103         notifyNodeInsertedIntoTree(insertionPoint, downcast<ContainerNode>(node), postInsertionNotificationTargets);
104 }
105
106 void notifyNodeRemovedFromDocument(ContainerNode& insertionPoint, Node& node)
107 {
108     ASSERT(insertionPoint.inDocument());
109     node.removedFrom(insertionPoint);
110
111     if (!is<ContainerNode>(node))
112         return;
113     ChildNodesLazySnapshot snapshot(node);
114     while (RefPtr<Node> child = snapshot.nextNode()) {
115         // If we have been added to the document during this loop, then we
116         // don't want to tell the rest of our children that they've been
117         // removed from the document because they haven't.
118         if (!node.inDocument() && child->parentNode() == &node)
119             notifyNodeRemovedFromDocument(insertionPoint, *child.get());
120     }
121
122     if (!is<Element>(node))
123         return;
124
125     if (node.document().cssTarget() == &node)
126         node.document().setCSSTarget(nullptr);
127
128     if (RefPtr<ShadowRoot> root = downcast<Element>(node).shadowRoot()) {
129         if (!node.inDocument() && root->host() == &node)
130             notifyNodeRemovedFromDocument(insertionPoint, *root.get());
131     }
132 }
133
134 void notifyNodeRemovedFromTree(ContainerNode& insertionPoint, ContainerNode& node)
135 {
136     NoEventDispatchAssertion assertNoEventDispatch;
137     ASSERT(!insertionPoint.inDocument());
138
139     node.removedFrom(insertionPoint);
140
141     for (Node* child = node.firstChild(); child; child = child->nextSibling()) {
142         if (is<ContainerNode>(*child))
143             notifyNodeRemovedFromTree(insertionPoint, downcast<ContainerNode>(*child));
144     }
145
146     if (!is<Element>(node))
147         return;
148
149     if (RefPtr<ShadowRoot> root = downcast<Element>(node).shadowRoot())
150         notifyNodeRemovedFromTree(insertionPoint, *root.get());
151 }
152
153 void notifyChildNodeRemoved(ContainerNode& insertionPoint, Node& child)
154 {
155     if (!child.inDocument()) {
156         if (is<ContainerNode>(child))
157             notifyNodeRemovedFromTree(insertionPoint, downcast<ContainerNode>(child));
158         return;
159     }
160     notifyNodeRemovedFromDocument(insertionPoint, child);
161     child.document().notifyRemovePendingSheetIfNeeded();
162 }
163
164 void addChildNodesToDeletionQueue(Node*& head, Node*& tail, ContainerNode& container)
165 {
166     // We have to tell all children that their parent has died.
167     Node* next = nullptr;
168     for (auto* node = container.firstChild(); node; node = next) {
169         ASSERT(!node->m_deletionHasBegun);
170
171         next = node->nextSibling();
172         node->setNextSibling(nullptr);
173         node->setParentNode(nullptr);
174         container.setFirstChild(next);
175         if (next)
176             next->setPreviousSibling(nullptr);
177
178         if (!node->refCount()) {
179 #ifndef NDEBUG
180             node->m_deletionHasBegun = true;
181 #endif
182             // Add the node to the list of nodes to be deleted.
183             // Reuse the nextSibling pointer for this purpose.
184             if (tail)
185                 tail->setNextSibling(node);
186             else
187                 head = node;
188
189             tail = node;
190         } else {
191             Ref<Node> protect(*node); // removedFromDocument may remove remove all references to this node.
192             if (Document* containerDocument = container.ownerDocument())
193                 containerDocument->adoptIfNeeded(*node);
194             if (node->isInTreeScope())
195                 notifyChildNodeRemoved(container, *node);
196         }
197     }
198
199     container.setLastChild(nullptr);
200 }
201
202 void removeDetachedChildrenInContainer(ContainerNode& container)
203 {
204     // List of nodes to be deleted.
205     Node* head = nullptr;
206     Node* tail = nullptr;
207
208     addChildNodesToDeletionQueue(head, tail, container);
209
210     Node* node;
211     Node* next;
212     while ((node = head)) {
213         ASSERT(node->m_deletionHasBegun);
214
215         next = node->nextSibling();
216         node->setNextSibling(nullptr);
217
218         head = next;
219         if (!next)
220             tail = nullptr;
221
222         if (is<ContainerNode>(*node))
223             addChildNodesToDeletionQueue(head, tail, downcast<ContainerNode>(*node));
224         
225         delete node;
226     }
227 }
228
229 #ifndef NDEBUG
230 static unsigned assertConnectedSubrameCountIsConsistent(ContainerNode& node)
231 {
232     unsigned count = 0;
233
234     if (is<Element>(node)) {
235         if (is<HTMLFrameOwnerElement>(node) && downcast<HTMLFrameOwnerElement>(node).contentFrame())
236             ++count;
237
238         if (ShadowRoot* root = downcast<Element>(node).shadowRoot())
239             count += assertConnectedSubrameCountIsConsistent(*root);
240     }
241
242     for (auto& child : childrenOfType<Element>(node))
243         count += assertConnectedSubrameCountIsConsistent(child);
244
245     // If we undercount there's possibly a security bug since we'd leave frames
246     // in subtrees outside the document.
247     ASSERT(node.connectedSubframeCount() >= count);
248
249     // If we overcount it's safe, but not optimal because it means we'll traverse
250     // through the document in disconnectSubframes looking for frames that have
251     // already been disconnected.
252     ASSERT(node.connectedSubframeCount() == count);
253
254     return count;
255 }
256 #endif
257
258 static void collectFrameOwners(Vector<Ref<HTMLFrameOwnerElement>>& frameOwners, ContainerNode& root)
259 {
260     auto elementDescendants = descendantsOfType<Element>(root);
261     auto it = elementDescendants.begin();
262     auto end = elementDescendants.end();
263     while (it != end) {
264         Element& element = *it;
265         if (!element.connectedSubframeCount()) {
266             it.traverseNextSkippingChildren();
267             continue;
268         }
269
270         if (is<HTMLFrameOwnerElement>(element))
271             frameOwners.append(downcast<HTMLFrameOwnerElement>(element));
272
273         if (ShadowRoot* shadowRoot = element.shadowRoot())
274             collectFrameOwners(frameOwners, *shadowRoot);
275         ++it;
276     }
277 }
278
279 void disconnectSubframes(ContainerNode& root, SubframeDisconnectPolicy policy)
280 {
281 #ifndef NDEBUG
282     assertConnectedSubrameCountIsConsistent(root);
283 #endif
284     ASSERT(root.connectedSubframeCount());
285
286     Vector<Ref<HTMLFrameOwnerElement>> frameOwners;
287
288     if (policy == RootAndDescendants) {
289         if (is<HTMLFrameOwnerElement>(root))
290             frameOwners.append(downcast<HTMLFrameOwnerElement>(root));
291     }
292
293     collectFrameOwners(frameOwners, root);
294
295     // Must disable frame loading in the subtree so an unload handler cannot
296     // insert more frames and create loaded frames in detached subtrees.
297     SubframeLoadingDisabler disabler(root);
298
299     bool isFirst = true;
300     for (auto& owner : frameOwners) {
301         // Don't need to traverse up the tree for the first owner since no
302         // script could have moved it.
303         if (isFirst || root.containsIncludingShadowDOM(&owner.get()))
304             owner.get().disconnectContentFrame();
305         isFirst = false;
306     }
307 }
308
309 }