Source/WebCore/page/scrolling/ThreadedScrollingTree.cpp - WebKit - Git at Google

 /*
  * Copyright (C) 2014-2015 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  * THE POSSIBILITY OF SUCH DAMAGE.
  */

 #include "config.h"
 #include "ThreadedScrollingTree.h"

 #if ENABLE(ASYNC_SCROLLING) && ENABLE(SCROLLING_THREAD)

 #include "AnimationFrameRate.h"
 #include "AsyncScrollingCoordinator.h"
 #include "Logging.h"
 #include "PlatformWheelEvent.h"
 #include "ScrollingThread.h"
 #include "ScrollingTreeFrameScrollingNode.h"
 #include "ScrollingTreeNode.h"
 #include "ScrollingTreeOverflowScrollProxyNode.h"
 #include "ScrollingTreeScrollingNode.h"
 #include <wtf/RunLoop.h>
 #include <wtf/SetForScope.h>
 #include <wtf/SystemTracing.h>
 #include <wtf/text/TextStream.h>
 #include <wtf/threads/BinarySemaphore.h>

 namespace WebCore {

 ThreadedScrollingTree::ThreadedScrollingTree(AsyncScrollingCoordinator& scrollingCoordinator)
     : m_scrollingCoordinator(&scrollingCoordinator)
     , m_scrollAnimatorEnabled(scrollingCoordinator.scrollAnimatorEnabled())
 {
 }

 ThreadedScrollingTree::~ThreadedScrollingTree()
 {
     // invalidate() should have cleared m_scrollingCoordinator.
     ASSERT(!m_scrollingCoordinator);
 }

 WheelEventHandlingResult ThreadedScrollingTree::handleWheelEvent(const PlatformWheelEvent& wheelEvent, OptionSet<WheelEventProcessingSteps> processingSteps)
 {
     ASSERT(ScrollingThread::isCurrentThread());
     return ScrollingTree::handleWheelEvent(wheelEvent, processingSteps);
 }

 bool ThreadedScrollingTree::handleWheelEventAfterMainThread(const PlatformWheelEvent& wheelEvent, ScrollingNodeID targetNodeID, std::optional<WheelScrollGestureState> gestureState)
 {
     ASSERT(ScrollingThread::isCurrentThread());

     LOG_WITH_STREAM(Scrolling, stream << "ThreadedScrollingTree::handleWheelEventAfterMainThread " << wheelEvent << " node " << targetNodeID << " gestureState " << gestureState);

     Locker locker { m_treeLock };

     bool allowLatching = false;
     OptionSet<WheelEventProcessingSteps> processingSteps;
     if (gestureState.value_or(WheelScrollGestureState::Blocking) == WheelScrollGestureState::NonBlocking) {
         allowLatching = true;
         processingSteps = { WheelEventProcessingSteps::ScrollingThread, WheelEventProcessingSteps::MainThreadForNonBlockingDOMEventDispatch };
     }

     SetForScope disallowLatchingScope(m_allowLatching, allowLatching);
     RefPtr<ScrollingTreeNode> targetNode = nodeForID(targetNodeID);
     auto result = handleWheelEventWithNode(wheelEvent, processingSteps, targetNode.get(), EventTargeting::NodeOnly);
     return result.wasHandled;
 }

 void ThreadedScrollingTree::wheelEventWasProcessedByMainThread(const PlatformWheelEvent& wheelEvent, std::optional<WheelScrollGestureState> gestureState)
 {
     LOG_WITH_STREAM(Scrolling, stream << "ThreadedScrollingTree::wheelEventWasProcessedByMainThread - gestureState " << gestureState);

     ASSERT(isMainThread());

     Locker locker { m_treeLock };
     if (m_receivedBeganEventFromMainThread || !wheelEvent.isGestureStart())
         return;

     setGestureState(gestureState);

     m_receivedBeganEventFromMainThread = true;
     m_waitingForBeganEventCondition.notifyOne();
 }

 void ThreadedScrollingTree::willSendEventToMainThread(const PlatformWheelEvent&)
 {
     ASSERT(ScrollingThread::isCurrentThread());

     Locker locker { m_treeLock };
     m_receivedBeganEventFromMainThread = false;
 }

 void ThreadedScrollingTree::waitForEventToBeProcessedByMainThread(const PlatformWheelEvent& wheelEvent)
 {
     ASSERT(ScrollingThread::isCurrentThread());

     if (!wheelEvent.isGestureStart())
         return;

     Locker locker { m_treeLock };

     static constexpr auto maxAllowableMainThreadDelay = 50_ms;
     auto startTime = MonotonicTime::now();
     auto timeoutTime = startTime + maxAllowableMainThreadDelay;

     bool receivedEvent = m_waitingForBeganEventCondition.waitUntil(m_treeLock, timeoutTime, [&] {
         assertIsHeld(m_treeLock);
         return m_receivedBeganEventFromMainThread;
     });

     if (!receivedEvent) {
         // Timed out, go asynchronous.
         setGestureState(WheelScrollGestureState::NonBlocking);
     }

     LOG_WITH_STREAM(Scrolling, stream << "ThreadedScrollingTree::waitForBeganEventFromMainThread done - timed out " << !receivedEvent << " gesture state is " << gestureState());
 }

 void ThreadedScrollingTree::invalidate()
 {
     // Invalidate is dispatched by the ScrollingCoordinator class on the ScrollingThread
     // to break the reference cycle between ScrollingTree and ScrollingCoordinator when the
     // ScrollingCoordinator's page is destroyed.
     ASSERT(ScrollingThread::isCurrentThread());

     Locker locker { m_treeLock };

     removeAllNodes();
     m_delayedRenderingUpdateDetectionTimer = nullptr;

     // Since this can potentially be the last reference to the scrolling coordinator,
     // we need to release it on the main thread since it has member variables (such as timers)
     // that expect to be destroyed from the main thread.
     RunLoop::main().dispatch([scrollingCoordinator = WTFMove(m_scrollingCoordinator)] {
     });
 }

 void ThreadedScrollingTree::didCommitTree()
 {
     ScrollingThread::dispatch([protectedThis = Ref { *this }]() {
         Locker treeLocker { protectedThis->m_treeLock };
         protectedThis->didCommitTreeOnScrollingThread();
     });
 }

 void ThreadedScrollingTree::didCommitTreeOnScrollingThread()
 {
     ASSERT(ScrollingThread::isCurrentThread());

     auto nodesWithPendingScrollAnimations = std::exchange(m_nodesWithPendingScrollAnimations, { });
     for (const auto& it : nodesWithPendingScrollAnimations) {
         RefPtr targetNode = nodeForID(it.key);
         if (!is<ScrollingTreeScrollingNode>(targetNode))
             continue;

         downcast<ScrollingTreeScrollingNode>(*targetNode).startAnimatedScrollToPosition(it.value.scrollPosition);
     }

     m_nodesWithPendingScrollAnimations.clear();
 }

 bool ThreadedScrollingTree::scrollingTreeNodeRequestsScroll(ScrollingNodeID nodeID, const RequestedScrollData& request)
 {
     if (request.animated == ScrollIsAnimated::Yes) {
         m_nodesWithPendingScrollAnimations.set(nodeID, request);
         return true;
     }
     return false;
 }

 void ThreadedScrollingTree::propagateSynchronousScrollingReasons(const HashSet<ScrollingNodeID>& synchronousScrollingNodes)
 {
     auto propagateStateToAncestors = [&](ScrollingTreeNode& node) {
         ASSERT(is<ScrollingTreeScrollingNode>(node) && !downcast<ScrollingTreeScrollingNode>(node).synchronousScrollingReasons().isEmpty());

         if (is<ScrollingTreeFrameScrollingNode>(node))
             return;

         auto currNode = node.parent();

         while (currNode) {
             if (is<ScrollingTreeScrollingNode>(currNode))
                 downcast<ScrollingTreeScrollingNode>(*currNode).addSynchronousScrollingReason(SynchronousScrollingReason::DescendantScrollersHaveSynchronousScrolling);

             if (is<ScrollingTreeOverflowScrollProxyNode>(currNode)) {
                 currNode = nodeForID(downcast<ScrollingTreeOverflowScrollProxyNode>(*currNode).overflowScrollingNodeID());
                 continue;
             }

             if (is<ScrollingTreeFrameScrollingNode>(currNode))
                 break;

             currNode = currNode->parent();
         }
     };

     m_hasNodesWithSynchronousScrollingReasons = !synchronousScrollingNodes.isEmpty();

     for (auto nodeID : synchronousScrollingNodes) {
         if (auto node = nodeForID(nodeID))
             propagateStateToAncestors(*node);
     }
 }

 bool ThreadedScrollingTree::canUpdateLayersOnScrollingThread() const
 {
     return !m_hasNodesWithSynchronousScrollingReasons;
 }

 void ThreadedScrollingTree::scrollingTreeNodeDidScroll(ScrollingTreeScrollingNode& node, ScrollingLayerPositionAction scrollingLayerPositionAction)
 {
     if (!m_scrollingCoordinator)
         return;

     auto scrollPosition = node.currentScrollPosition();
     if (node.isRootNode())
         setMainFrameScrollPosition(scrollPosition);

     if (isHandlingProgrammaticScroll())
         return;

     std::optional<FloatPoint> layoutViewportOrigin;
     if (is<ScrollingTreeFrameScrollingNode>(node))
         layoutViewportOrigin = downcast<ScrollingTreeFrameScrollingNode>(node).layoutViewport().location();

     auto scrollUpdate = ScrollUpdate { node.scrollingNodeID(), scrollPosition, layoutViewportOrigin, ScrollUpdateType::PositionUpdate, scrollingLayerPositionAction };

     if (RunLoop::isMain()) {
         m_scrollingCoordinator->applyScrollUpdate(WTFMove(scrollUpdate));
         return;
     }

     LOG_WITH_STREAM(Scrolling, stream << "ThreadedScrollingTree::scrollingTreeNodeDidScroll " << node.scrollingNodeID() << " to " << scrollPosition << " triggering main thread rendering update");

     addPendingScrollUpdate(WTFMove(scrollUpdate));

     auto deferrer = WheelEventTestMonitorCompletionDeferrer { wheelEventTestMonitor(), reinterpret_cast<WheelEventTestMonitor::ScrollableAreaIdentifier>(node.scrollingNodeID()), WheelEventTestMonitor::ScrollingThreadSyncNeeded };
     RunLoop::main().dispatch([strongThis = Ref { *this }, deferrer = WTFMove(deferrer)] {
         if (auto* scrollingCoordinator = strongThis->m_scrollingCoordinator.get())
             scrollingCoordinator->scrollingThreadAddedPendingUpdate();
     });
 }

 void ThreadedScrollingTree::scrollingTreeNodeDidStopAnimatedScroll(ScrollingTreeScrollingNode& node)
 {
     if (!m_scrollingCoordinator)
         return;

     LOG_WITH_STREAM(Scrolling, stream << "ThreadedScrollingTree::scrollingTreeNodeDidStopAnimatedScroll " << node.scrollingNodeID());

     auto scrollUpdate = ScrollUpdate { node.scrollingNodeID(), { }, { }, ScrollUpdateType::AnimatedScrollDidEnd };

     if (RunLoop::isMain()) {
         m_scrollingCoordinator->applyScrollUpdate(WTFMove(scrollUpdate));
         return;
     }

     addPendingScrollUpdate(WTFMove(scrollUpdate));

     RunLoop::main().dispatch([strongThis = Ref { *this }] {
         if (auto* scrollingCoordinator = strongThis->m_scrollingCoordinator.get())
             scrollingCoordinator->scrollingThreadAddedPendingUpdate();
     });
 }

 void ThreadedScrollingTree::reportSynchronousScrollingReasonsChanged(MonotonicTime timestamp, OptionSet<SynchronousScrollingReason> reasons)
 {
     auto scrollingCoordinator = m_scrollingCoordinator;
     if (!scrollingCoordinator)
         return;

     RunLoop::main().dispatch([scrollingCoordinator = WTFMove(scrollingCoordinator), timestamp, reasons] {
         scrollingCoordinator->reportSynchronousScrollingReasonsChanged(timestamp, reasons);
     });
 }

 void ThreadedScrollingTree::reportExposedUnfilledArea(MonotonicTime timestamp, unsigned unfilledArea)
 {
     auto scrollingCoordinator = m_scrollingCoordinator;
     if (!scrollingCoordinator)
         return;
     RunLoop::main().dispatch([scrollingCoordinator = WTFMove(scrollingCoordinator), timestamp, unfilledArea] {
         scrollingCoordinator->reportExposedUnfilledArea(timestamp, unfilledArea);
     });
 }

 #if PLATFORM(COCOA)
 void ThreadedScrollingTree::currentSnapPointIndicesDidChange(ScrollingNodeID nodeID, std::optional<unsigned> horizontal, std::optional<unsigned> vertical)
 {
     auto scrollingCoordinator = m_scrollingCoordinator;
     if (!scrollingCoordinator)
         return;

     RunLoop::main().dispatch([scrollingCoordinator = WTFMove(scrollingCoordinator), nodeID, horizontal, vertical] {
         scrollingCoordinator->setActiveScrollSnapIndices(nodeID, horizontal, vertical);
     });
 }
 #endif

 #if PLATFORM(MAC)
 void ThreadedScrollingTree::handleWheelEventPhase(ScrollingNodeID nodeID, PlatformWheelEventPhase phase)
 {
     auto scrollingCoordinator = m_scrollingCoordinator;
     if (!scrollingCoordinator)
         return;

     RunLoop::main().dispatch([scrollingCoordinator = WTFMove(scrollingCoordinator), nodeID, phase] {
         scrollingCoordinator->handleWheelEventPhase(nodeID, phase);
     });
 }

 void ThreadedScrollingTree::setActiveScrollSnapIndices(ScrollingNodeID nodeID, std::optional<unsigned> horizontalIndex, std::optional<unsigned> verticalIndex)
 {
     auto scrollingCoordinator = m_scrollingCoordinator;
     if (!scrollingCoordinator)
         return;

     RunLoop::main().dispatch([scrollingCoordinator = WTFMove(scrollingCoordinator), nodeID, horizontalIndex, verticalIndex] {
         scrollingCoordinator->setActiveScrollSnapIndices(nodeID, horizontalIndex, verticalIndex);
     });
 }
 #endif

 bool ThreadedScrollingTree::scrollingThreadIsActive()
 {
     return hasProcessedWheelEventsRecently() || hasNodeWithActiveScrollAnimations();
 }

 void ThreadedScrollingTree::didScheduleRenderingUpdate()
 {
     m_renderingUpdateWasScheduled = true;
 }

 void ThreadedScrollingTree::willStartRenderingUpdate()
 {
     ASSERT(isMainThread());

     m_renderingUpdateWasScheduled = false;

     if (!scrollingThreadIsActive())
         return;

     tracePoint(ScrollingThreadRenderUpdateSyncStart);

     // Wait for the scrolling thread to acquire m_treeLock. This ensures that any pending wheel events are processed.
     BinarySemaphore semaphore;
     ScrollingThread::dispatch([protectedThis = Ref { *this }, &semaphore]() {
         Locker treeLocker { protectedThis->m_treeLock };
         semaphore.signal();
         protectedThis->waitForRenderingUpdateCompletionOrTimeout();
     });
     semaphore.wait();

     Locker locker { m_treeLock };
     m_state = SynchronizationState::InRenderingUpdate;
 }

 Seconds ThreadedScrollingTree::frameDuration()
 {
     auto displayFPS = nominalFramesPerSecond().value_or(FullSpeedFramesPerSecond);
     return 1_s / (double)displayFPS;
 }

 Seconds ThreadedScrollingTree::maxAllowableRenderingUpdateDurationForSynchronization()
 {
     constexpr double allowableFrameFraction = 0.5;
     return allowableFrameFraction * frameDuration();
 }

 void ThreadedScrollingTree::hasNodeWithAnimatedScrollChanged(bool hasNodeWithAnimatedScroll)
 {
     auto scrollingCoordinator = m_scrollingCoordinator;
     if (!scrollingCoordinator)
         return;

     RunLoop::main().dispatch([scrollingCoordinator = WTFMove(scrollingCoordinator), hasNodeWithAnimatedScroll] {
         scrollingCoordinator->hasNodeWithAnimatedScrollChanged(hasNodeWithAnimatedScroll);
     });
 }

 void ThreadedScrollingTree::serviceScrollAnimations(MonotonicTime currentTime)
 {
     ASSERT(ScrollingThread::isCurrentThread());

     for (auto nodeID : nodesWithActiveScrollAnimations()) {
         RefPtr targetNode = nodeForID(nodeID);
         if (!is<ScrollingTreeScrollingNode>(targetNode))
             continue;

         downcast<ScrollingTreeScrollingNode>(*targetNode).serviceScrollAnimation(currentTime);
     }
 }

 // This code allows the main thread about half a frame to complete its rendering udpate. If the main thread
 // is responsive (i.e. managing to render every frame), then we expect to get a didCompletePlatformRenderingUpdate()
 // within 8ms of willStartRenderingUpdate(). We time this via m_stateCondition, which blocks the scrolling
 // thread (with m_treeLock locked at the start and end) so that we don't handle wheel events while waiting.
 // If the condition times out, we know the main thread is being slow, and allow the scrolling thread to
 // commit layer positions.
 void ThreadedScrollingTree::waitForRenderingUpdateCompletionOrTimeout()
 {
     ASSERT(ScrollingThread::isCurrentThread());
     ASSERT(m_treeLock.isLocked());

     if (m_delayedRenderingUpdateDetectionTimer)
         m_delayedRenderingUpdateDetectionTimer->stop();

     auto currentTime = MonotonicTime::now();
     auto estimatedNextDisplayRefreshTime = std::max(m_lastDisplayDidRefreshTime + frameDuration(), currentTime);
     auto timeoutTime = std::min(currentTime + maxAllowableRenderingUpdateDurationForSynchronization(), estimatedNextDisplayRefreshTime);

     bool becameIdle = m_stateCondition.waitUntil(m_treeLock, timeoutTime, [&] {
         assertIsHeld(m_treeLock);
         return m_state == SynchronizationState::Idle;
     });

     ASSERT(m_treeLock.isLocked());

     if (!becameIdle) {
         m_state = SynchronizationState::Desynchronized;
         // At this point we know the main thread is taking too long in the rendering update,
         // so we give up trying to sync with the main thread and update layers here on the scrolling thread.
         if (canUpdateLayersOnScrollingThread()) {
             // Dispatch to allow for the scrolling thread to handle any outstanding wheel events before we commit layers.
             ScrollingThread::dispatch([protectedThis = Ref { *this }]() {
                 protectedThis->applyLayerPositions();
             });
         }
         tracePoint(ScrollingThreadRenderUpdateSyncEnd, 1);
     } else
         tracePoint(ScrollingThreadRenderUpdateSyncEnd);
 }

 void ThreadedScrollingTree::didCompleteRenderingUpdate()
 {
     renderingUpdateComplete();
 }

 void ThreadedScrollingTree::renderingUpdateComplete()
 {
     ASSERT(isMainThread());

     Locker locker { m_treeLock };

     if (m_state == SynchronizationState::InRenderingUpdate)
         m_stateCondition.notifyOne();

     m_state = SynchronizationState::Idle;
 }

 void ThreadedScrollingTree::scheduleDelayedRenderingUpdateDetectionTimer(Seconds delay)
 {
     ASSERT(ScrollingThread::isCurrentThread());
     ASSERT(m_treeLock.isLocked());

     if (!m_delayedRenderingUpdateDetectionTimer)
         m_delayedRenderingUpdateDetectionTimer = makeUnique<RunLoop::Timer<ThreadedScrollingTree>>(RunLoop::current(), this, &ThreadedScrollingTree::delayedRenderingUpdateDetectionTimerFired);

     m_delayedRenderingUpdateDetectionTimer->startOneShot(delay);
 }

 void ThreadedScrollingTree::delayedRenderingUpdateDetectionTimerFired()
 {
     ASSERT(ScrollingThread::isCurrentThread());

     Locker locker { m_treeLock };
     if (canUpdateLayersOnScrollingThread())
         applyLayerPositionsInternal();
     m_state = SynchronizationState::Desynchronized;
 }

 void ThreadedScrollingTree::displayDidRefreshOnScrollingThread()
 {
     TraceScope tracingScope(ScrollingThreadDisplayDidRefreshStart, ScrollingThreadDisplayDidRefreshEnd, displayID());
     ASSERT(ScrollingThread::isCurrentThread());

     Locker locker { m_treeLock };

     auto now = MonotonicTime::now();
     m_lastDisplayDidRefreshTime = now;
     serviceScrollAnimations(now);

     if (m_state != SynchronizationState::Idle && canUpdateLayersOnScrollingThread())
         applyLayerPositionsInternal();

     switch (m_state) {
     case SynchronizationState::Idle: {
         if (m_renderingUpdateWasScheduled) {
             m_state = SynchronizationState::WaitingForRenderingUpdate;
             constexpr auto maxStartRenderingUpdateDelay = 1_ms;
             scheduleDelayedRenderingUpdateDetectionTimer(maxStartRenderingUpdateDelay);
         }
         break;
     }
     case SynchronizationState::WaitingForRenderingUpdate:
     case SynchronizationState::InRenderingUpdate:
     case SynchronizationState::Desynchronized:
         break;
     }
 }

 void ThreadedScrollingTree::displayDidRefresh(PlatformDisplayID displayID)
 {
     bool scrollingThreadIsActive = this->scrollingThreadIsActive();

     // We're on the EventDispatcher thread or in the ThreadedCompositor thread here.
     tracePoint(ScrollingTreeDisplayDidRefresh, displayID, scrollingThreadIsActive);

     if (displayID != this->displayID())
         return;

     if (!scrollingThreadIsActive)
         return;

     ScrollingThread::dispatch([protectedThis = Ref { *this }]() {
         protectedThis->displayDidRefreshOnScrollingThread();
     });
 }

 void ThreadedScrollingTree::removePendingScrollAnimationForNode(ScrollingNodeID nodeID)
 {
     m_nodesWithPendingScrollAnimations.remove(nodeID);
 }

 bool ThreadedScrollingTree::isScrollingSynchronizedWithMainThread()
 {
     return m_state != SynchronizationState::Desynchronized;
 }

 } // namespace WebCore

 #endif // ENABLE(ASYNC_SCROLLING) && ENABLE(SCROLLING_THREAD)
	/*
	* Copyright (C) 2014-2015 Apple Inc. All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	*
	* THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
	* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
	* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
	* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
	* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
	* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
	* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
	* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
	* THE POSSIBILITY OF SUCH DAMAGE.
	*/

	#include "config.h"
	#include "ThreadedScrollingTree.h"

	#if ENABLE(ASYNC_SCROLLING) && ENABLE(SCROLLING_THREAD)

	#include "AnimationFrameRate.h"
	#include "AsyncScrollingCoordinator.h"
	#include "Logging.h"
	#include "PlatformWheelEvent.h"
	#include "ScrollingThread.h"
	#include "ScrollingTreeFrameScrollingNode.h"
	#include "ScrollingTreeNode.h"
	#include "ScrollingTreeOverflowScrollProxyNode.h"
	#include "ScrollingTreeScrollingNode.h"
	#include <wtf/RunLoop.h>
	#include <wtf/SetForScope.h>
	#include <wtf/SystemTracing.h>
	#include <wtf/text/TextStream.h>
	#include <wtf/threads/BinarySemaphore.h>

	namespace WebCore {

	ThreadedScrollingTree::ThreadedScrollingTree(AsyncScrollingCoordinator& scrollingCoordinator)
	: m_scrollingCoordinator(&scrollingCoordinator)
	, m_scrollAnimatorEnabled(scrollingCoordinator.scrollAnimatorEnabled())
	{
	}

	ThreadedScrollingTree::~ThreadedScrollingTree()
	{
	// invalidate() should have cleared m_scrollingCoordinator.
	ASSERT(!m_scrollingCoordinator);
	}

	WheelEventHandlingResult ThreadedScrollingTree::handleWheelEvent(const PlatformWheelEvent& wheelEvent, OptionSet<WheelEventProcessingSteps> processingSteps)
	{
	ASSERT(ScrollingThread::isCurrentThread());
	return ScrollingTree::handleWheelEvent(wheelEvent, processingSteps);
	}

	bool ThreadedScrollingTree::handleWheelEventAfterMainThread(const PlatformWheelEvent& wheelEvent, ScrollingNodeID targetNodeID, std::optional<WheelScrollGestureState> gestureState)
	{
	ASSERT(ScrollingThread::isCurrentThread());

	LOG_WITH_STREAM(Scrolling, stream << "ThreadedScrollingTree::handleWheelEventAfterMainThread " << wheelEvent << " node " << targetNodeID << " gestureState " << gestureState);

	Locker locker { m_treeLock };

	bool allowLatching = false;
	OptionSet<WheelEventProcessingSteps> processingSteps;
	if (gestureState.value_or(WheelScrollGestureState::Blocking) == WheelScrollGestureState::NonBlocking) {
	allowLatching = true;
	processingSteps = { WheelEventProcessingSteps::ScrollingThread, WheelEventProcessingSteps::MainThreadForNonBlockingDOMEventDispatch };
	}

	SetForScope disallowLatchingScope(m_allowLatching, allowLatching);
	RefPtr<ScrollingTreeNode> targetNode = nodeForID(targetNodeID);
	auto result = handleWheelEventWithNode(wheelEvent, processingSteps, targetNode.get(), EventTargeting::NodeOnly);
	return result.wasHandled;
	}

	void ThreadedScrollingTree::wheelEventWasProcessedByMainThread(const PlatformWheelEvent& wheelEvent, std::optional<WheelScrollGestureState> gestureState)
	{
	LOG_WITH_STREAM(Scrolling, stream << "ThreadedScrollingTree::wheelEventWasProcessedByMainThread - gestureState " << gestureState);

	ASSERT(isMainThread());

	Locker locker { m_treeLock };
	if (m_receivedBeganEventFromMainThread \|\| !wheelEvent.isGestureStart())
	return;

	setGestureState(gestureState);

	m_receivedBeganEventFromMainThread = true;
	m_waitingForBeganEventCondition.notifyOne();
	}

	void ThreadedScrollingTree::willSendEventToMainThread(const PlatformWheelEvent&)
	{
	ASSERT(ScrollingThread::isCurrentThread());

	Locker locker { m_treeLock };
	m_receivedBeganEventFromMainThread = false;
	}

	void ThreadedScrollingTree::waitForEventToBeProcessedByMainThread(const PlatformWheelEvent& wheelEvent)
	{
	ASSERT(ScrollingThread::isCurrentThread());

	if (!wheelEvent.isGestureStart())
	return;

	Locker locker { m_treeLock };

	static constexpr auto maxAllowableMainThreadDelay = 50_ms;
	auto startTime = MonotonicTime::now();
	auto timeoutTime = startTime + maxAllowableMainThreadDelay;

	bool receivedEvent = m_waitingForBeganEventCondition.waitUntil(m_treeLock, timeoutTime, [&] {
	assertIsHeld(m_treeLock);
	return m_receivedBeganEventFromMainThread;
	});

	if (!receivedEvent) {
	// Timed out, go asynchronous.
	setGestureState(WheelScrollGestureState::NonBlocking);
	}

	LOG_WITH_STREAM(Scrolling, stream << "ThreadedScrollingTree::waitForBeganEventFromMainThread done - timed out " << !receivedEvent << " gesture state is " << gestureState());
	}

	void ThreadedScrollingTree::invalidate()
	{
	// Invalidate is dispatched by the ScrollingCoordinator class on the ScrollingThread
	// to break the reference cycle between ScrollingTree and ScrollingCoordinator when the
	// ScrollingCoordinator's page is destroyed.
	ASSERT(ScrollingThread::isCurrentThread());

	Locker locker { m_treeLock };

	removeAllNodes();
	m_delayedRenderingUpdateDetectionTimer = nullptr;

	// Since this can potentially be the last reference to the scrolling coordinator,
	// we need to release it on the main thread since it has member variables (such as timers)
	// that expect to be destroyed from the main thread.
	RunLoop::main().dispatch([scrollingCoordinator = WTFMove(m_scrollingCoordinator)] {
	});
	}

	void ThreadedScrollingTree::didCommitTree()
	{
	ScrollingThread::dispatch([protectedThis = Ref { *this }]() {
	Locker treeLocker { protectedThis->m_treeLock };
	protectedThis->didCommitTreeOnScrollingThread();
	});
	}

	void ThreadedScrollingTree::didCommitTreeOnScrollingThread()
	{
	ASSERT(ScrollingThread::isCurrentThread());

	auto nodesWithPendingScrollAnimations = std::exchange(m_nodesWithPendingScrollAnimations, { });
	for (const auto& it : nodesWithPendingScrollAnimations) {
	RefPtr targetNode = nodeForID(it.key);
	if (!is<ScrollingTreeScrollingNode>(targetNode))
	continue;

	downcast<ScrollingTreeScrollingNode>(*targetNode).startAnimatedScrollToPosition(it.value.scrollPosition);
	}

	m_nodesWithPendingScrollAnimations.clear();
	}

	bool ThreadedScrollingTree::scrollingTreeNodeRequestsScroll(ScrollingNodeID nodeID, const RequestedScrollData& request)
	{
	if (request.animated == ScrollIsAnimated::Yes) {
	m_nodesWithPendingScrollAnimations.set(nodeID, request);
	return true;
	}
	return false;
	}

	void ThreadedScrollingTree::propagateSynchronousScrollingReasons(const HashSet<ScrollingNodeID>& synchronousScrollingNodes)
	{
	auto propagateStateToAncestors = [&](ScrollingTreeNode& node) {
	ASSERT(is<ScrollingTreeScrollingNode>(node) && !downcast<ScrollingTreeScrollingNode>(node).synchronousScrollingReasons().isEmpty());

	if (is<ScrollingTreeFrameScrollingNode>(node))
	return;

	auto currNode = node.parent();

	while (currNode) {
	if (is<ScrollingTreeScrollingNode>(currNode))
	downcast<ScrollingTreeScrollingNode>(*currNode).addSynchronousScrollingReason(SynchronousScrollingReason::DescendantScrollersHaveSynchronousScrolling);

	if (is<ScrollingTreeOverflowScrollProxyNode>(currNode)) {
	currNode = nodeForID(downcast<ScrollingTreeOverflowScrollProxyNode>(*currNode).overflowScrollingNodeID());
	continue;
	}

	if (is<ScrollingTreeFrameScrollingNode>(currNode))
	break;

	currNode = currNode->parent();
	}
	};

	m_hasNodesWithSynchronousScrollingReasons = !synchronousScrollingNodes.isEmpty();

	for (auto nodeID : synchronousScrollingNodes) {
	if (auto node = nodeForID(nodeID))
	propagateStateToAncestors(*node);
	}
	}

	bool ThreadedScrollingTree::canUpdateLayersOnScrollingThread() const
	{
	return !m_hasNodesWithSynchronousScrollingReasons;
	}

	void ThreadedScrollingTree::scrollingTreeNodeDidScroll(ScrollingTreeScrollingNode& node, ScrollingLayerPositionAction scrollingLayerPositionAction)
	{
	if (!m_scrollingCoordinator)
	return;

	auto scrollPosition = node.currentScrollPosition();
	if (node.isRootNode())
	setMainFrameScrollPosition(scrollPosition);

	if (isHandlingProgrammaticScroll())
	return;

	std::optional<FloatPoint> layoutViewportOrigin;
	if (is<ScrollingTreeFrameScrollingNode>(node))
	layoutViewportOrigin = downcast<ScrollingTreeFrameScrollingNode>(node).layoutViewport().location();

	auto scrollUpdate = ScrollUpdate { node.scrollingNodeID(), scrollPosition, layoutViewportOrigin, ScrollUpdateType::PositionUpdate, scrollingLayerPositionAction };

	if (RunLoop::isMain()) {
	m_scrollingCoordinator->applyScrollUpdate(WTFMove(scrollUpdate));
	return;
	}

	LOG_WITH_STREAM(Scrolling, stream << "ThreadedScrollingTree::scrollingTreeNodeDidScroll " << node.scrollingNodeID() << " to " << scrollPosition << " triggering main thread rendering update");

	addPendingScrollUpdate(WTFMove(scrollUpdate));

	auto deferrer = WheelEventTestMonitorCompletionDeferrer { wheelEventTestMonitor(), reinterpret_cast<WheelEventTestMonitor::ScrollableAreaIdentifier>(node.scrollingNodeID()), WheelEventTestMonitor::ScrollingThreadSyncNeeded };
	RunLoop::main().dispatch([strongThis = Ref { *this }, deferrer = WTFMove(deferrer)] {
	if (auto* scrollingCoordinator = strongThis->m_scrollingCoordinator.get())
	scrollingCoordinator->scrollingThreadAddedPendingUpdate();
	});
	}

	void ThreadedScrollingTree::scrollingTreeNodeDidStopAnimatedScroll(ScrollingTreeScrollingNode& node)
	{
	if (!m_scrollingCoordinator)
	return;

	LOG_WITH_STREAM(Scrolling, stream << "ThreadedScrollingTree::scrollingTreeNodeDidStopAnimatedScroll " << node.scrollingNodeID());

	auto scrollUpdate = ScrollUpdate { node.scrollingNodeID(), { }, { }, ScrollUpdateType::AnimatedScrollDidEnd };

	if (RunLoop::isMain()) {
	m_scrollingCoordinator->applyScrollUpdate(WTFMove(scrollUpdate));
	return;
	}

	addPendingScrollUpdate(WTFMove(scrollUpdate));

	RunLoop::main().dispatch([strongThis = Ref { *this }] {
	if (auto* scrollingCoordinator = strongThis->m_scrollingCoordinator.get())
	scrollingCoordinator->scrollingThreadAddedPendingUpdate();
	});
	}

	void ThreadedScrollingTree::reportSynchronousScrollingReasonsChanged(MonotonicTime timestamp, OptionSet<SynchronousScrollingReason> reasons)
	{
	auto scrollingCoordinator = m_scrollingCoordinator;
	if (!scrollingCoordinator)
	return;

	RunLoop::main().dispatch([scrollingCoordinator = WTFMove(scrollingCoordinator), timestamp, reasons] {
	scrollingCoordinator->reportSynchronousScrollingReasonsChanged(timestamp, reasons);
	});
	}

	void ThreadedScrollingTree::reportExposedUnfilledArea(MonotonicTime timestamp, unsigned unfilledArea)
	{
	auto scrollingCoordinator = m_scrollingCoordinator;
	if (!scrollingCoordinator)
	return;
	RunLoop::main().dispatch([scrollingCoordinator = WTFMove(scrollingCoordinator), timestamp, unfilledArea] {
	scrollingCoordinator->reportExposedUnfilledArea(timestamp, unfilledArea);
	});
	}

	#if PLATFORM(COCOA)
	void ThreadedScrollingTree::currentSnapPointIndicesDidChange(ScrollingNodeID nodeID, std::optional<unsigned> horizontal, std::optional<unsigned> vertical)
	{
	auto scrollingCoordinator = m_scrollingCoordinator;
	if (!scrollingCoordinator)
	return;

	RunLoop::main().dispatch([scrollingCoordinator = WTFMove(scrollingCoordinator), nodeID, horizontal, vertical] {
	scrollingCoordinator->setActiveScrollSnapIndices(nodeID, horizontal, vertical);
	});
	}
	#endif

	#if PLATFORM(MAC)
	void ThreadedScrollingTree::handleWheelEventPhase(ScrollingNodeID nodeID, PlatformWheelEventPhase phase)
	{
	auto scrollingCoordinator = m_scrollingCoordinator;
	if (!scrollingCoordinator)
	return;

	RunLoop::main().dispatch([scrollingCoordinator = WTFMove(scrollingCoordinator), nodeID, phase] {
	scrollingCoordinator->handleWheelEventPhase(nodeID, phase);
	});
	}

	void ThreadedScrollingTree::setActiveScrollSnapIndices(ScrollingNodeID nodeID, std::optional<unsigned> horizontalIndex, std::optional<unsigned> verticalIndex)
	{
	auto scrollingCoordinator = m_scrollingCoordinator;
	if (!scrollingCoordinator)
	return;

	RunLoop::main().dispatch([scrollingCoordinator = WTFMove(scrollingCoordinator), nodeID, horizontalIndex, verticalIndex] {
	scrollingCoordinator->setActiveScrollSnapIndices(nodeID, horizontalIndex, verticalIndex);
	});
	}
	#endif

	bool ThreadedScrollingTree::scrollingThreadIsActive()
	{
	return hasProcessedWheelEventsRecently() \|\| hasNodeWithActiveScrollAnimations();
	}

	void ThreadedScrollingTree::didScheduleRenderingUpdate()
	{
	m_renderingUpdateWasScheduled = true;
	}

	void ThreadedScrollingTree::willStartRenderingUpdate()
	{
	ASSERT(isMainThread());

	m_renderingUpdateWasScheduled = false;

	if (!scrollingThreadIsActive())
	return;

	tracePoint(ScrollingThreadRenderUpdateSyncStart);

	// Wait for the scrolling thread to acquire m_treeLock. This ensures that any pending wheel events are processed.
	BinarySemaphore semaphore;
	ScrollingThread::dispatch([protectedThis = Ref { *this }, &semaphore]() {
	Locker treeLocker { protectedThis->m_treeLock };
	semaphore.signal();
	protectedThis->waitForRenderingUpdateCompletionOrTimeout();
	});
	semaphore.wait();

	Locker locker { m_treeLock };
	m_state = SynchronizationState::InRenderingUpdate;
	}

	Seconds ThreadedScrollingTree::frameDuration()
	{
	auto displayFPS = nominalFramesPerSecond().value_or(FullSpeedFramesPerSecond);
	return 1_s / (double)displayFPS;
	}

	Seconds ThreadedScrollingTree::maxAllowableRenderingUpdateDurationForSynchronization()
	{
	constexpr double allowableFrameFraction = 0.5;
	return allowableFrameFraction * frameDuration();
	}

	void ThreadedScrollingTree::hasNodeWithAnimatedScrollChanged(bool hasNodeWithAnimatedScroll)
	{
	auto scrollingCoordinator = m_scrollingCoordinator;
	if (!scrollingCoordinator)
	return;

	RunLoop::main().dispatch([scrollingCoordinator = WTFMove(scrollingCoordinator), hasNodeWithAnimatedScroll] {
	scrollingCoordinator->hasNodeWithAnimatedScrollChanged(hasNodeWithAnimatedScroll);
	});
	}

	void ThreadedScrollingTree::serviceScrollAnimations(MonotonicTime currentTime)
	{
	ASSERT(ScrollingThread::isCurrentThread());

	for (auto nodeID : nodesWithActiveScrollAnimations()) {
	RefPtr targetNode = nodeForID(nodeID);
	if (!is<ScrollingTreeScrollingNode>(targetNode))
	continue;

	downcast<ScrollingTreeScrollingNode>(*targetNode).serviceScrollAnimation(currentTime);
	}
	}

	// This code allows the main thread about half a frame to complete its rendering udpate. If the main thread
	// is responsive (i.e. managing to render every frame), then we expect to get a didCompletePlatformRenderingUpdate()
	// within 8ms of willStartRenderingUpdate(). We time this via m_stateCondition, which blocks the scrolling
	// thread (with m_treeLock locked at the start and end) so that we don't handle wheel events while waiting.
	// If the condition times out, we know the main thread is being slow, and allow the scrolling thread to
	// commit layer positions.
	void ThreadedScrollingTree::waitForRenderingUpdateCompletionOrTimeout()
	{
	ASSERT(ScrollingThread::isCurrentThread());
	ASSERT(m_treeLock.isLocked());

	if (m_delayedRenderingUpdateDetectionTimer)
	m_delayedRenderingUpdateDetectionTimer->stop();

	auto currentTime = MonotonicTime::now();
	auto estimatedNextDisplayRefreshTime = std::max(m_lastDisplayDidRefreshTime + frameDuration(), currentTime);
	auto timeoutTime = std::min(currentTime + maxAllowableRenderingUpdateDurationForSynchronization(), estimatedNextDisplayRefreshTime);

	bool becameIdle = m_stateCondition.waitUntil(m_treeLock, timeoutTime, [&] {
	assertIsHeld(m_treeLock);
	return m_state == SynchronizationState::Idle;
	});

	ASSERT(m_treeLock.isLocked());

	if (!becameIdle) {
	m_state = SynchronizationState::Desynchronized;
	// At this point we know the main thread is taking too long in the rendering update,
	// so we give up trying to sync with the main thread and update layers here on the scrolling thread.
	if (canUpdateLayersOnScrollingThread()) {
	// Dispatch to allow for the scrolling thread to handle any outstanding wheel events before we commit layers.
	ScrollingThread::dispatch([protectedThis = Ref { *this }]() {
	protectedThis->applyLayerPositions();
	});
	}
	tracePoint(ScrollingThreadRenderUpdateSyncEnd, 1);
	} else
	tracePoint(ScrollingThreadRenderUpdateSyncEnd);
	}

	void ThreadedScrollingTree::didCompleteRenderingUpdate()
	{
	renderingUpdateComplete();
	}

	void ThreadedScrollingTree::renderingUpdateComplete()
	{
	ASSERT(isMainThread());

	Locker locker { m_treeLock };

	if (m_state == SynchronizationState::InRenderingUpdate)
	m_stateCondition.notifyOne();

	m_state = SynchronizationState::Idle;
	}

	void ThreadedScrollingTree::scheduleDelayedRenderingUpdateDetectionTimer(Seconds delay)
	{
	ASSERT(ScrollingThread::isCurrentThread());
	ASSERT(m_treeLock.isLocked());

	if (!m_delayedRenderingUpdateDetectionTimer)
	m_delayedRenderingUpdateDetectionTimer = makeUnique<RunLoop::Timer<ThreadedScrollingTree>>(RunLoop::current(), this, &ThreadedScrollingTree::delayedRenderingUpdateDetectionTimerFired);

	m_delayedRenderingUpdateDetectionTimer->startOneShot(delay);
	}

	void ThreadedScrollingTree::delayedRenderingUpdateDetectionTimerFired()
	{
	ASSERT(ScrollingThread::isCurrentThread());

	Locker locker { m_treeLock };
	if (canUpdateLayersOnScrollingThread())
	applyLayerPositionsInternal();
	m_state = SynchronizationState::Desynchronized;
	}

	void ThreadedScrollingTree::displayDidRefreshOnScrollingThread()
	{
	TraceScope tracingScope(ScrollingThreadDisplayDidRefreshStart, ScrollingThreadDisplayDidRefreshEnd, displayID());
	ASSERT(ScrollingThread::isCurrentThread());

	Locker locker { m_treeLock };

	auto now = MonotonicTime::now();
	m_lastDisplayDidRefreshTime = now;
	serviceScrollAnimations(now);

	if (m_state != SynchronizationState::Idle && canUpdateLayersOnScrollingThread())
	applyLayerPositionsInternal();

	switch (m_state) {
	case SynchronizationState::Idle: {
	if (m_renderingUpdateWasScheduled) {
	m_state = SynchronizationState::WaitingForRenderingUpdate;
	constexpr auto maxStartRenderingUpdateDelay = 1_ms;
	scheduleDelayedRenderingUpdateDetectionTimer(maxStartRenderingUpdateDelay);
	}
	break;
	}
	case SynchronizationState::WaitingForRenderingUpdate:
	case SynchronizationState::InRenderingUpdate:
	case SynchronizationState::Desynchronized:
	break;
	}
	}

	void ThreadedScrollingTree::displayDidRefresh(PlatformDisplayID displayID)
	{
	bool scrollingThreadIsActive = this->scrollingThreadIsActive();

	// We're on the EventDispatcher thread or in the ThreadedCompositor thread here.
	tracePoint(ScrollingTreeDisplayDidRefresh, displayID, scrollingThreadIsActive);

	if (displayID != this->displayID())
	return;

	if (!scrollingThreadIsActive)
	return;

	ScrollingThread::dispatch([protectedThis = Ref { *this }]() {
	protectedThis->displayDidRefreshOnScrollingThread();
	});
	}

	void ThreadedScrollingTree::removePendingScrollAnimationForNode(ScrollingNodeID nodeID)
	{
	m_nodesWithPendingScrollAnimations.remove(nodeID);
	}

	bool ThreadedScrollingTree::isScrollingSynchronizedWithMainThread()
	{
	return m_state != SynchronizationState::Desynchronized;
	}

	} // namespace WebCore

	#endif // ENABLE(ASYNC_SCROLLING) && ENABLE(SCROLLING_THREAD)