1/*
2 * Copyright (C) 2012 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "ScrollingStateTree.h"
28
29#if ENABLE(ASYNC_SCROLLING) || USE(COORDINATED_GRAPHICS)
30
31#include "AsyncScrollingCoordinator.h"
32#include "Logging.h"
33#include "ScrollingStateFixedNode.h"
34#include "ScrollingStateFrameHostingNode.h"
35#include "ScrollingStateFrameScrollingNode.h"
36#include "ScrollingStateOverflowScrollingNode.h"
37#include "ScrollingStatePositionedNode.h"
38#include "ScrollingStateStickyNode.h"
39#include <wtf/text/CString.h>
40#include <wtf/text/TextStream.h>
41
42namespace WebCore {
43
44ScrollingStateTree::ScrollingStateTree(AsyncScrollingCoordinator* scrollingCoordinator)
45 : m_scrollingCoordinator(scrollingCoordinator)
46{
47}
48
49ScrollingStateTree::~ScrollingStateTree() = default;
50
51void ScrollingStateTree::setHasChangedProperties(bool changedProperties)
52{
53#if ENABLE(ASYNC_SCROLLING)
54 bool gainedChangedProperties = !m_hasChangedProperties && changedProperties;
55#endif
56
57 m_hasChangedProperties = changedProperties;
58
59#if ENABLE(ASYNC_SCROLLING)
60 if (gainedChangedProperties && m_scrollingCoordinator)
61 m_scrollingCoordinator->scrollingStateTreePropertiesChanged();
62#endif
63}
64
65Ref<ScrollingStateNode> ScrollingStateTree::createNode(ScrollingNodeType nodeType, ScrollingNodeID nodeID)
66{
67 switch (nodeType) {
68 case ScrollingNodeType::MainFrame:
69 case ScrollingNodeType::Subframe:
70 return ScrollingStateFrameScrollingNode::create(*this, nodeType, nodeID);
71 case ScrollingNodeType::FrameHosting:
72 return ScrollingStateFrameHostingNode::create(*this, nodeID);
73 case ScrollingNodeType::Overflow:
74 return ScrollingStateOverflowScrollingNode::create(*this, nodeID);
75 case ScrollingNodeType::Fixed:
76 return ScrollingStateFixedNode::create(*this, nodeID);
77 case ScrollingNodeType::Sticky:
78 return ScrollingStateStickyNode::create(*this, nodeID);
79 case ScrollingNodeType::Positioned:
80 return ScrollingStatePositionedNode::create(*this, nodeID);
81 }
82 ASSERT_NOT_REACHED();
83 return ScrollingStateFixedNode::create(*this, nodeID);
84}
85
86bool ScrollingStateTree::nodeTypeAndParentMatch(ScrollingStateNode& node, ScrollingNodeType nodeType, ScrollingStateNode* parentNode) const
87{
88 if (node.nodeType() != nodeType)
89 return false;
90
91 return node.parent() == parentNode;
92}
93
94ScrollingNodeID ScrollingStateTree::createUnparentedNode(ScrollingNodeType nodeType, ScrollingNodeID newNodeID)
95{
96 LOG_WITH_STREAM(Scrolling, stream << "ScrollingStateTree " << this << " createUnparentedNode " << newNodeID);
97
98 if (auto* node = stateNodeForID(newNodeID)) {
99 if (node->nodeType() == nodeType) {
100 // If the node exists and is parented, unparent it. It may already be in m_unparentedNodes.
101 unparentNode(newNodeID);
102 return newNodeID;
103 }
104
105#if ENABLE(ASYNC_SCROLLING)
106 // If the type has changed, we need to destroy and recreate the node with a new ID.
107 if (nodeType != node->nodeType()) {
108 unparentChildrenAndDestroyNode(newNodeID);
109 newNodeID = m_scrollingCoordinator->uniqueScrollingNodeID();
110 }
111#endif
112 }
113
114 auto stateNode = createNode(nodeType, newNodeID);
115 addNode(stateNode.get());
116 m_unparentedNodes.add(newNodeID, WTFMove(stateNode));
117 return newNodeID;
118}
119
120ScrollingNodeID ScrollingStateTree::insertNode(ScrollingNodeType nodeType, ScrollingNodeID newNodeID, ScrollingNodeID parentID, size_t childIndex)
121{
122 LOG_WITH_STREAM(Scrolling, stream << "ScrollingStateTree " << this << " insertNode " << newNodeID << " in parent " << parentID << " at " << childIndex);
123 ASSERT(newNodeID);
124
125 if (auto* node = stateNodeForID(newNodeID)) {
126 auto* parent = stateNodeForID(parentID);
127 if (nodeTypeAndParentMatch(*node, nodeType, parent)) {
128 if (!parentID)
129 return newNodeID;
130
131 size_t currentIndex = parent->indexOfChild(*node);
132 if (currentIndex == childIndex)
133 return newNodeID;
134
135 ASSERT(currentIndex != notFound);
136 Ref<ScrollingStateNode> protectedNode(*node);
137 parent->removeChildAtIndex(currentIndex);
138
139 if (childIndex == notFound)
140 parent->appendChild(WTFMove(protectedNode));
141 else
142 parent->insertChild(WTFMove(protectedNode), childIndex);
143
144 return newNodeID;
145 }
146
147#if ENABLE(ASYNC_SCROLLING)
148 // If the type has changed, we need to destroy and recreate the node with a new ID.
149 if (nodeType != node->nodeType())
150 newNodeID = m_scrollingCoordinator->uniqueScrollingNodeID();
151#endif
152
153 // The node is being re-parented. To do that, we'll remove it, and then create a new node.
154 unparentNode(newNodeID);
155 }
156
157 ScrollingStateNode* newNode = nullptr;
158 if (!parentID) {
159 RELEASE_ASSERT(nodeType == ScrollingNodeType::MainFrame);
160 ASSERT(!childIndex || childIndex == notFound);
161 // If we're resetting the root node, we should clear the HashMap and destroy the current children.
162 clear();
163
164 setRootStateNode(ScrollingStateFrameScrollingNode::create(*this, ScrollingNodeType::MainFrame, newNodeID));
165 newNode = rootStateNode();
166 m_hasNewRootStateNode = true;
167 } else {
168 auto* parent = stateNodeForID(parentID);
169 if (!parent) {
170 ASSERT_NOT_REACHED();
171 return 0;
172 }
173
174 if (parentID) {
175 if (auto unparentedNode = m_unparentedNodes.take(newNodeID)) {
176 LOG_WITH_STREAM(Scrolling, stream << "ScrollingStateTree " << this << " insertNode " << newNodeID << " getting node from unparented nodes");
177 newNode = unparentedNode.get();
178 nodeWasReattachedRecursive(*unparentedNode);
179
180 if (childIndex == notFound)
181 parent->appendChild(unparentedNode.releaseNonNull());
182 else
183 parent->insertChild(unparentedNode.releaseNonNull(), childIndex);
184 }
185 }
186
187 if (!newNode) {
188 auto stateNode = createNode(nodeType, newNodeID);
189 newNode = stateNode.ptr();
190 if (childIndex == notFound)
191 parent->appendChild(WTFMove(stateNode));
192 else
193 parent->insertChild(WTFMove(stateNode), childIndex);
194 }
195 }
196
197 addNode(*newNode);
198 return newNodeID;
199}
200
201void ScrollingStateTree::unparentNode(ScrollingNodeID nodeID)
202{
203 if (!nodeID)
204 return;
205
206 LOG_WITH_STREAM(Scrolling, stream << "ScrollingStateTree " << this << " unparentNode " << nodeID);
207
208 // The node may not be found if clear() was recently called.
209 RefPtr<ScrollingStateNode> protectedNode = m_stateNodeMap.get(nodeID);
210 if (!protectedNode)
211 return;
212
213 if (protectedNode == m_rootStateNode)
214 m_rootStateNode = nullptr;
215
216 protectedNode->removeFromParent();
217 m_unparentedNodes.add(nodeID, WTFMove(protectedNode));
218}
219
220void ScrollingStateTree::unparentChildrenAndDestroyNode(ScrollingNodeID nodeID)
221{
222 if (!nodeID)
223 return;
224
225 LOG_WITH_STREAM(Scrolling, stream << "ScrollingStateTree " << this << " unparentChildrenAndDestroyNode " << nodeID);
226
227 // The node may not be found if clear() was recently called.
228 RefPtr<ScrollingStateNode> protectedNode = m_stateNodeMap.take(nodeID);
229 if (!protectedNode)
230 return;
231
232 if (protectedNode == m_rootStateNode)
233 m_rootStateNode = nullptr;
234
235 if (protectedNode->children()) {
236 auto isolatedChildren = protectedNode->takeChildren();
237 for (auto child : *isolatedChildren) {
238 child->removeFromParent();
239 LOG_WITH_STREAM(Scrolling, stream << " moving " << child->scrollingNodeID() << " to unparented nodes");
240 m_unparentedNodes.add(child->scrollingNodeID(), WTFMove(child));
241 }
242 }
243
244 protectedNode->removeFromParent();
245 willRemoveNode(protectedNode.get());
246}
247
248void ScrollingStateTree::detachAndDestroySubtree(ScrollingNodeID nodeID)
249{
250 if (!nodeID)
251 return;
252
253 LOG_WITH_STREAM(Scrolling, stream << "ScrollingStateTree " << this << " detachAndDestroySubtree " << nodeID);
254
255 // The node may not be found if clear() was recently called.
256 auto* node = m_stateNodeMap.take(nodeID);
257 if (!node)
258 return;
259
260 // If the node was unparented, remove it from m_unparentedNodes (keeping it alive until this function returns).
261 auto unparentedNode = m_unparentedNodes.take(nodeID);
262 removeNodeAndAllDescendants(node);
263}
264
265void ScrollingStateTree::clear()
266{
267 if (rootStateNode())
268 removeNodeAndAllDescendants(rootStateNode());
269
270 m_stateNodeMap.clear();
271 m_unparentedNodes.clear();
272}
273
274void ScrollingStateTree::nodeWasReattachedRecursive(ScrollingStateNode& node)
275{
276 // When a node is re-attached, the ScrollingTree is recreating the ScrollingNode from scratch, so we need to set all the dirty bits.
277 node.setAllPropertiesChanged();
278
279 if (auto* children = node.children()) {
280 for (auto& child : *children)
281 nodeWasReattachedRecursive(*child);
282 }
283}
284
285std::unique_ptr<ScrollingStateTree> ScrollingStateTree::commit(LayerRepresentation::Type preferredLayerRepresentation)
286{
287 if (!m_unparentedNodes.isEmpty()) {
288 // We expect temporarily to have unparented nodes when committing when connecting across iframe boundaries, but unparented nodes should not stick around for a long time.
289 LOG(Scrolling, "Committing with %u unparented nodes", m_unparentedNodes.size());
290 }
291
292 // This function clones and resets the current state tree, but leaves the tree structure intact.
293 std::unique_ptr<ScrollingStateTree> treeStateClone = std::make_unique<ScrollingStateTree>();
294 treeStateClone->setPreferredLayerRepresentation(preferredLayerRepresentation);
295
296 if (m_rootStateNode)
297 treeStateClone->setRootStateNode(static_reference_cast<ScrollingStateFrameScrollingNode>(m_rootStateNode->cloneAndReset(*treeStateClone)));
298
299 // Now the clone tree has changed properties, and the original tree does not.
300 treeStateClone->m_hasChangedProperties = m_hasChangedProperties;
301 m_hasChangedProperties = false;
302
303 treeStateClone->m_hasNewRootStateNode = m_hasNewRootStateNode;
304 m_hasNewRootStateNode = false;
305
306 return treeStateClone;
307}
308
309void ScrollingStateTree::setRootStateNode(Ref<ScrollingStateFrameScrollingNode>&& rootStateNode)
310{
311 m_rootStateNode = WTFMove(rootStateNode);
312}
313
314void ScrollingStateTree::addNode(ScrollingStateNode& node)
315{
316 m_stateNodeMap.add(node.scrollingNodeID(), &node);
317}
318
319void ScrollingStateTree::removeNodeAndAllDescendants(ScrollingStateNode* node)
320{
321 auto* parent = node->parent();
322
323 recursiveNodeWillBeRemoved(node);
324
325 if (node == m_rootStateNode)
326 m_rootStateNode = nullptr;
327 else if (parent) {
328 ASSERT(parent->children());
329 ASSERT(parent->children()->find(node) != notFound);
330 if (auto* children = parent->children()) {
331 size_t index = children->find(node);
332 if (index != notFound)
333 children->remove(index);
334 }
335 }
336}
337
338void ScrollingStateTree::recursiveNodeWillBeRemoved(ScrollingStateNode* currNode)
339{
340 currNode->setParent(nullptr);
341 willRemoveNode(currNode);
342
343 if (auto* children = currNode->children()) {
344 for (auto& child : *children)
345 recursiveNodeWillBeRemoved(child.get());
346 }
347}
348
349void ScrollingStateTree::willRemoveNode(ScrollingStateNode* node)
350{
351 m_stateNodeMap.remove(node->scrollingNodeID());
352 setHasChangedProperties();
353}
354
355ScrollingStateNode* ScrollingStateTree::stateNodeForID(ScrollingNodeID scrollLayerID) const
356{
357 if (!scrollLayerID)
358 return nullptr;
359
360 auto it = m_stateNodeMap.find(scrollLayerID);
361 if (it == m_stateNodeMap.end())
362 return nullptr;
363
364 ASSERT(it->value->scrollingNodeID() == scrollLayerID);
365 return it->value;
366}
367
368void ScrollingStateTree::reconcileLayerPositionsRecursive(ScrollingStateNode& currNode, const LayoutRect& layoutViewport, ScrollingLayerPositionAction action)
369{
370 currNode.reconcileLayerPositionForViewportRect(layoutViewport, action);
371
372 if (!currNode.children())
373 return;
374
375 for (auto& child : *currNode.children()) {
376 // Never need to cross frame boundaries, since viewport rect reconciliation is per frame.
377 if (is<ScrollingStateFrameScrollingNode>(child))
378 continue;
379
380 reconcileLayerPositionsRecursive(*child, layoutViewport, action);
381 }
382}
383
384void ScrollingStateTree::reconcileViewportConstrainedLayerPositions(ScrollingNodeID scrollingNodeID, const LayoutRect& layoutViewport, ScrollingLayerPositionAction action)
385{
386 auto* scrollingNode = stateNodeForID(scrollingNodeID);
387 if (!scrollingNode)
388 return;
389
390 reconcileLayerPositionsRecursive(*scrollingNode, layoutViewport, action);
391}
392
393} // namespace WebCore
394
395#ifndef NDEBUG
396void showScrollingStateTree(const WebCore::ScrollingStateTree* tree)
397{
398 if (!tree)
399 return;
400
401 auto rootNode = tree->rootStateNode();
402 if (!rootNode) {
403 WTFLogAlways("Scrolling state tree %p with no root node\n", tree);
404 return;
405 }
406
407 String output = rootNode->scrollingStateTreeAsText(WebCore::ScrollingStateTreeAsTextBehaviorDebug);
408 WTFLogAlways("%s\n", output.utf8().data());
409}
410
411void showScrollingStateTree(const WebCore::ScrollingStateNode* node)
412{
413 if (!node)
414 return;
415
416 showScrollingStateTree(&node->scrollingStateTree());
417}
418
419#endif
420
421#endif // ENABLE(ASYNC_SCROLLING) || USE(COORDINATED_GRAPHICS)
422