LibWeb: Implement the infrastructure necessary for requestIdleCallback

This includes a bug fix for the event loop processing steps which has
not been merged yet: https://github.com/whatwg/html/pull/7768

6 files changed, 209 insertions, 31 deletions

diff --git a/Userland/Libraries/LibWeb/HTML/EventLoop/EventLoop.cpp b/Userland/Libraries/LibWeb/HTML/EventLoop/EventLoop.cpp
index 67221a5a9c..182f7d040a 100644
--- a/Userland/Libraries/LibWeb/HTML/EventLoop/EventLoop.cpp
+++ b/Userland/Libraries/LibWeb/HTML/EventLoop/EventLoop.cpp
@@ -1,5 +1,6 @@
 /*
  * Copyright (c) 2021, Andreas Kling <kling@serenityos.org>
+ * Copyright (c) 2022, the SerenityOS developers.
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
@@ -90,33 +91,43 @@ void EventLoop::process()
 {
     // An event loop must continually run through the following steps for as long as it exists:
 
-    // 1. Let taskQueue be one of the event loop's task queues, chosen in an implementation-defined manner, with the constraint that the chosen task queue must contain at least one runnable task. If there is no such task queue, then jump to the microtasks step below.
+    // 1. Let oldestTask be null.
+    OwnPtr<Task> oldest_task;
+
+    // 2. Let taskStartTime be the current high resolution time.
+    // FIXME: 'current high resolution time' in hr-time-3 takes a global object,
+    //        the HTML spec has not been updated to reflect this, let's use the shared timer.
+    //        - https://github.com/whatwg/html/issues/7776
+    double task_start_time = unsafe_shared_current_time();
+
+    // 3. Let taskQueue be one of the event loop's task queues, chosen in an implementation-defined manner,
+    //    with the constraint that the chosen task queue must contain at least one runnable task.
+    //    If there is no such task queue, then jump to the microtasks step below.
     auto& task_queue = m_task_queue;
 
-    if (auto oldest_task = task_queue.take_first_runnable()) {
-        // 2. Let oldestTask be the first runnable task in taskQueue, and remove it from taskQueue.
+    // 4. Set oldestTask to the first runnable task in taskQueue, and remove it from taskQueue.
+    oldest_task = task_queue.take_first_runnable();
 
-        // 3. Set the event loop's currently running task to oldestTask.
+    if (oldest_task) {
+        // 5. Set the event loop's currently running task to oldestTask.
         m_currently_running_task = oldest_task.ptr();
 
-        // FIXME: 4. Let taskStartTime be the current high resolution time.
-
-        // 5. Perform oldestTask's steps.
+        // 6. Perform oldestTask's steps.
         oldest_task->execute();
 
-        // 6. Set the event loop's currently running task back to null.
+        // 7. Set the event loop's currently running task back to null.
         m_currently_running_task = nullptr;
     }
 
-    // 7. Microtasks: Perform a microtask checkpoint.
+    // 8. Microtasks: Perform a microtask checkpoint.
     perform_a_microtask_checkpoint();
 
-    // 8. Let hasARenderingOpportunity be false.
+    // 9. Let hasARenderingOpportunity be false.
     [[maybe_unused]] bool has_a_rendering_opportunity = false;
 
-    // FIXME: 9. Let now be the current high resolution time. [HRT]
+    // FIXME: 10. Let now be the current high resolution time. [HRT]
 
-    // FIXME: 10. Report the task's duration by performing the following steps:
+    // FIXME: 11. If oldestTask is not null, then:
 
     // FIXME:     1. Let top-level browsing contexts be an empty set.
 
@@ -124,7 +135,7 @@ void EventLoop::process()
 
     // FIXME:     3. Report long tasks, passing in taskStartTime, now (the end time of the task), top-level browsing contexts, and oldestTask.
 
-    // FIXME: 11. Update the rendering: if this is a window event loop, then:
+    // FIXME: 12. Update the rendering: if this is a window event loop, then:
 
     // FIXME:     1. Let docs be all Document objects whose relevant agent's event loop is this event loop, sorted arbitrarily except that the following conditions must be met:
     //               - Any Document B whose browsing context's container document is A must be listed after A in the list.
@@ -144,9 +155,12 @@ void EventLoop::process()
         return document->browsing_context() && !document->browsing_context()->has_a_rendering_opportunity();
     });
 
-    // 3. If docs is not empty, then set hasARenderingOpportunity to true.
-    if (!docs.is_empty())
+    // 3. If docs is not empty, then set hasARenderingOpportunity to true
+    //    and set this event loop's last render opportunity time to taskStartTime.
+    if (!docs.is_empty()) {
         has_a_rendering_opportunity = true;
+        m_last_render_opportunity_time = task_start_time;
+    }
 
     // FIXME:     4. Unnecessary rendering: Remove from docs all Document objects which meet both of the following conditions:
     //               - The user agent believes that updating the rendering of the Document's browsing context would have no visible effect, and
@@ -185,14 +199,26 @@ void EventLoop::process()
 
     // FIXME:     16. For each fully active Document in docs, update the rendering or user interface of that Document and its browsing context to reflect the current state.
 
-    // FIXME: 12. If all of the following are true
-    //            - this is a window event loop
-    //            - there is no task in this event loop's task queues whose document is fully active
-    //            - this event loop's microtask queue is empty
-    //            - hasARenderingOpportunity is false
-    // FIXME:         then for each Window object whose relevant agent's event loop is this event loop, run the start an idle period algorithm, passing the Window. [REQUESTIDLECALLBACK]
+    // 13. If all of the following are true
+    // - this is a window event loop
+    // - there is no task in this event loop's task queues whose document is fully active
+    // - this event loop's microtask queue is empty
+    // - hasARenderingOpportunity is false
+    // FIXME: has_a_rendering_opportunity is always true
+    if (m_type == Type::Window && !task_queue.has_runnable_tasks() && m_microtask_queue.is_empty() /*&& !has_a_rendering_opportunity*/) {
+        // 1. Set this event loop's last idle period start time to the current high resolution time.
+        m_last_idle_period_start_time = unsafe_shared_current_time();
+
+        // 2. Let computeDeadline be the following steps:
+        // NOTE: instead of passing around a function we use this event loop, which has compute_deadline()
+
+        // 3. For each win of the same-loop windows for this event loop,
+        //    perform the start an idle period algorithm for win with computeDeadline. [REQUESTIDLECALLBACK]
+        for (auto& win : same_loop_windows())
+            win.start_an_idle_period();
+    }
 
-    // FIXME: 13. If this is a worker event loop, then:
+    // FIXME: 14. If this is a worker event loop, then:
 
     // FIXME:     1. If this event loop's agent's single realm's global object is a supported DedicatedWorkerGlobalScope and the user agent believes that it would benefit from having its rendering updated at this time, then:
     // FIXME:        1. Let now be the current high resolution time. [HRT]
@@ -341,4 +367,49 @@ void EventLoop::unregister_environment_settings_object(Badge<EnvironmentSettings
     VERIFY(did_remove);
 }
 
+// https://html.spec.whatwg.org/multipage/webappapis.html#same-loop-windows
+NonnullRefPtrVector<Window> EventLoop::same_loop_windows() const
+{
+    NonnullRefPtrVector<Window> windows;
+    for (auto& document : documents_in_this_event_loop())
+        windows.append(document.window());
+    return windows;
+}
+
+// https://w3c.github.io/hr-time/#dfn-unsafe-shared-current-time
+double EventLoop::unsafe_shared_current_time() const
+{
+    return Time::now_monotonic().to_nanoseconds() / 1e6;
+}
+
+// https://html.spec.whatwg.org/multipage/webappapis.html#event-loop-processing-model:last-idle-period-start-time
+double EventLoop::compute_deadline() const
+{
+    // 1. Let deadline be this event loop's last idle period start time plus 50.
+    auto deadline = m_last_idle_period_start_time + 50;
+    // 2. Let hasPendingRenders be false.
+    auto has_pending_renders = false;
+    // 3. For each windowInSameLoop of the same-loop windows for this event loop:
+    for (auto& window : same_loop_windows()) {
+        // 1. If windowInSameLoop's map of animation frame callbacks is not empty,
+        //    or if the user agent believes that the windowInSameLoop might have pending rendering updates,
+        //    set hasPendingRenders to true.
+        if (window.has_animation_frame_callbacks())
+            has_pending_renders = true;
+        // FIXME: 2. Let timerCallbackEstimates be the result of getting the values of windowInSameLoop's map of active timers.
+        // FIXME: 3. For each timeoutDeadline of timerCallbackEstimates, if timeoutDeadline is less than deadline, set deadline to timeoutDeadline.
+    }
+    // 4. If hasPendingRenders is true, then:
+    if (has_pending_renders) {
+        // 1. Let nextRenderDeadline be this event loop's last render opportunity time plus (1000 divided by the current refresh rate).
+        // FIXME: Hardcoded to 60Hz
+        auto next_render_deadline = m_last_render_opportunity_time + (1000.0 / 60.0);
+        // 2. If nextRenderDeadline is less than deadline, then return nextRenderDeadline.
+        if (next_render_deadline < deadline)
+            return next_render_deadline;
+    }
+    // 5. Return deadline.
+    return deadline;
+}
+
 }
diff --git a/Userland/Libraries/LibWeb/HTML/EventLoop/EventLoop.h b/Userland/Libraries/LibWeb/HTML/EventLoop/EventLoop.h
index 658ff67dae..70c806defa 100644
--- a/Userland/Libraries/LibWeb/HTML/EventLoop/EventLoop.h
+++ b/Userland/Libraries/LibWeb/HTML/EventLoop/EventLoop.h
@@ -55,6 +55,8 @@ public:
 
     NonnullRefPtrVector<DOM::Document> documents_in_this_event_loop() const;
 
+    NonnullRefPtrVector<Window> same_loop_windows() const;
+
     void push_onto_backup_incumbent_settings_object_stack(Badge<EnvironmentSettingsObject>, EnvironmentSettingsObject& environment_settings_object);
     void pop_backup_incumbent_settings_object_stack(Badge<EnvironmentSettingsObject>);
     EnvironmentSettingsObject& top_of_backup_incumbent_settings_object_stack();
@@ -63,6 +65,9 @@ public:
     void register_environment_settings_object(Badge<EnvironmentSettingsObject>, EnvironmentSettingsObject&);
     void unregister_environment_settings_object(Badge<EnvironmentSettingsObject>, EnvironmentSettingsObject&);
 
+    double unsafe_shared_current_time() const;
+    double compute_deadline() const;
+
 private:
     Type m_type { Type::Window };
 
@@ -72,6 +77,11 @@ private:
     // https://html.spec.whatwg.org/multipage/webappapis.html#currently-running-task
     Task* m_currently_running_task { nullptr };
 
+    // https://html.spec.whatwg.org/multipage/webappapis.html#last-render-opportunity-time
+    double m_last_render_opportunity_time { 0 };
+    // https://html.spec.whatwg.org/multipage/webappapis.html#last-idle-period-start-time
+    double m_last_idle_period_start_time { 0 };
+
     JS::VM* m_vm { nullptr };
 
     RefPtr<Core::Timer> m_system_event_loop_timer;
diff --git a/Userland/Libraries/LibWeb/HTML/Window.cpp b/Userland/Libraries/LibWeb/HTML/Window.cpp
index eb50c3514f..33b9a89841 100644
--- a/Userland/Libraries/LibWeb/HTML/Window.cpp
+++ b/Userland/Libraries/LibWeb/HTML/Window.cpp
@@ -27,6 +27,7 @@
 #include <LibWeb/HighResolutionTime/Performance.h>
 #include <LibWeb/Layout/InitialContainingBlock.h>
 #include <LibWeb/Page/Page.h>
+#include <LibWeb/RequestIdleCallback/IdleDeadline.h>
 #include <LibWeb/Selection/Selection.h>
 
 namespace Web::HTML {
@@ -107,6 +108,20 @@ void run_animation_frame_callbacks(DOM::Document&, double)
     request_animation_frame_driver().run();
 }
 
+class IdleCallback : public RefCounted<IdleCallback> {
+public:
+    explicit IdleCallback(Function<JS::Completion(NonnullRefPtr<RequestIdleCallback::IdleDeadline>)> handler)
+        : m_handler(move(handler))
+    {
+    }
+    ~IdleCallback() = default;
+
+    JS::Completion invoke(NonnullRefPtr<RequestIdleCallback::IdleDeadline> deadline) { return m_handler(move(deadline)); }
+
+private:
+    Function<JS::Completion(NonnullRefPtr<RequestIdleCallback::IdleDeadline>)> m_handler;
+};
+
 NonnullRefPtr<Window> Window::create_with_document(DOM::Document& document)
 {
     return adopt_ref(*new Window(document));
@@ -637,4 +652,54 @@ void Window::set_name(String const& name)
     browsing_context()->set_name(name);
 }
 
+// https://w3c.github.io/requestidlecallback/#start-an-idle-period-algorithm
+void Window::start_an_idle_period()
+{
+    // 1. Optionally, if the user agent determines the idle period should be delayed, return from this algorithm.
+    if (!wrapper())
+        return;
+    // 2. Let pending_list be window's list of idle request callbacks.
+    auto& pending_list = m_idle_request_callbacks;
+    // 3. Let run_list be window's list of runnable idle callbacks.
+    auto& run_list = m_runnable_idle_callbacks;
+    run_list.extend(pending_list);
+    // 4. Clear pending_list.
+    pending_list.clear();
+
+    // FIXME: This might not agree with the spec, but currently we use 100% CPU if we keep queueing tasks
+    if (run_list.is_empty())
+        return;
+
+    // 5. Queue a task on the queue associated with the idle-task task source,
+    //    which performs the steps defined in the invoke idle callbacks algorithm with window and getDeadline as parameters.
+    HTML::queue_global_task(HTML::Task::Source::IdleTask, *wrapper(), [window = NonnullRefPtr(*this)]() mutable {
+        window->invoke_idle_callbacks();
+    });
+}
+
+// https://w3c.github.io/requestidlecallback/#invoke-idle-callbacks-algorithm
+void Window::invoke_idle_callbacks()
+{
+    auto& event_loop = main_thread_event_loop();
+    // 1. If the user-agent believes it should end the idle period early due to newly scheduled high-priority work, return from the algorithm.
+    // 2. Let now be the current time.
+    auto now = event_loop.unsafe_shared_current_time();
+    // 3. If now is less than the result of calling getDeadline and the window's list of runnable idle callbacks is not empty:
+    if (now < event_loop.compute_deadline() && !m_runnable_idle_callbacks.is_empty()) {
+        // 1. Pop the top callback from window's list of runnable idle callbacks.
+        auto callback = m_runnable_idle_callbacks.take_first();
+        // 2. Let deadlineArg be a new IdleDeadline whose [get deadline time algorithm] is getDeadline.
+        auto deadline_arg = RequestIdleCallback::IdleDeadline::create();
+        // 3. Call callback with deadlineArg as its argument. If an uncaught runtime script error occurs, then report the exception.
+        auto result = callback->invoke(deadline_arg);
+        if (result.is_error())
+            HTML::report_exception(result);
+        // 4. If window's list of runnable idle callbacks is not empty, queue a task which performs the steps
+        //    in the invoke idle callbacks algorithm with getDeadline and window as a parameters and return from this algorithm
+        HTML::queue_global_task(HTML::Task::Source::IdleTask, *wrapper(), [window = NonnullRefPtr(*this)]() mutable {
+            window->invoke_idle_callbacks();
+        });
+    }
+}
+
 }
diff --git a/Userland/Libraries/LibWeb/HTML/Window.h b/Userland/Libraries/LibWeb/HTML/Window.h
index df519f3977..ea931ca791 100644
--- a/Userland/Libraries/LibWeb/HTML/Window.h
+++ b/Userland/Libraries/LibWeb/HTML/Window.h
@@ -24,6 +24,7 @@
 namespace Web::HTML {
 
 class RequestAnimationFrameCallback;
+class IdleCallback;
 
 class Window final
     : public RefCounted<Window>
@@ -58,6 +59,7 @@ public:
     String prompt(String const&, String const&);
     i32 request_animation_frame(NonnullOwnPtr<Bindings::CallbackType> js_callback);
     void cancel_animation_frame(i32);
+    bool has_animation_frame_callbacks() const { return !m_request_animation_frame_callbacks.is_empty(); }
 
     i32 set_timeout(Bindings::TimerHandler handler, i32 timeout, JS::MarkedVector<JS::Value> arguments);
     i32 set_interval(Bindings::TimerHandler handler, i32 timeout, JS::MarkedVector<JS::Value> arguments);
@@ -115,6 +117,8 @@ public:
     String name() const;
     void set_name(String const&);
 
+    void start_an_idle_period();
+
 private:
     explicit Window(DOM::Document&);
 
@@ -127,6 +131,8 @@ private:
     };
     i32 run_timer_initialization_steps(Bindings::TimerHandler handler, i32 timeout, JS::MarkedVector<JS::Value> arguments, Repeat repeat, Optional<i32> previous_id = {});
 
+    void invoke_idle_callbacks();
+
     // https://html.spec.whatwg.org/multipage/window-object.html#concept-document-window
     WeakPtr<DOM::Document> m_associated_document;
 
@@ -141,6 +147,13 @@ private:
     RefPtr<DOM::Event> m_current_event;
 
     HashMap<i32, NonnullRefPtr<RequestAnimationFrameCallback>> m_request_animation_frame_callbacks;
+
+    // https://w3c.github.io/requestidlecallback/#dfn-list-of-idle-request-callbacks
+    NonnullRefPtrVector<IdleCallback> m_idle_request_callbacks;
+    // https://w3c.github.io/requestidlecallback/#dfn-list-of-runnable-idle-callbacks
+    NonnullRefPtrVector<IdleCallback> m_runnable_idle_callbacks;
+    // https://w3c.github.io/requestidlecallback/#dfn-idle-callback-identifier
+    u32 m_idle_callback_identifier = 0;
 };
 
 void run_animation_frame_callbacks(DOM::Document&, double now);
diff --git a/Userland/Libraries/LibWeb/RequestIdleCallback/IdleDeadline.cpp b/Userland/Libraries/LibWeb/RequestIdleCallback/IdleDeadline.cpp
index 53996f7756..2c296598f6 100644
--- a/Userland/Libraries/LibWeb/RequestIdleCallback/IdleDeadline.cpp
+++ b/Userland/Libraries/LibWeb/RequestIdleCallback/IdleDeadline.cpp
@@ -1,24 +1,43 @@
 /*
  * Copyright (c) 2021, Andreas Kling <kling@serenityos.org>
+ * Copyright (c) 2022, the SerenityOS developers.
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
 
+#include <LibWeb/HTML/EventLoop/EventLoop.h>
 #include <LibWeb/RequestIdleCallback/IdleDeadline.h>
 
 namespace Web::RequestIdleCallback {
 
-NonnullRefPtr<IdleDeadline> IdleDeadline::create(double time_remaining, bool did_timeout)
+NonnullRefPtr<IdleDeadline> IdleDeadline::create(bool did_timeout)
 {
-    return adopt_ref(*new IdleDeadline(time_remaining, did_timeout));
+    return adopt_ref(*new IdleDeadline(did_timeout));
 }
 
-IdleDeadline::IdleDeadline(double time_remaining, bool did_timeout)
-    : m_time_remaining(time_remaining)
-    , m_did_timeout(did_timeout)
+IdleDeadline::IdleDeadline(bool did_timeout)
+    : m_did_timeout(did_timeout)
 {
 }
 
 IdleDeadline::~IdleDeadline() = default;
 
+// https://w3c.github.io/requestidlecallback/#dom-idledeadline-timeremaining
+double IdleDeadline::time_remaining() const
+{
+    auto const& event_loop = HTML::main_thread_event_loop();
+    // 1. Let now be a DOMHighResTimeStamp representing current high resolution time in milliseconds.
+    auto now = event_loop.unsafe_shared_current_time();
+    // 2. Let deadline be the result of calling IdleDeadline's get deadline time algorithm.
+    auto deadline = event_loop.compute_deadline();
+    // 3. Let timeRemaining be deadline - now.
+    auto time_remaining = deadline - now;
+    // 4. If timeRemaining is negative, set it to 0.
+    if (time_remaining < 0)
+        time_remaining = 0;
+    // 5. Return timeRemaining.
+    // NOTE: coarsening to milliseconds
+    return ceil(time_remaining);
+}
+
 }
diff --git a/Userland/Libraries/LibWeb/RequestIdleCallback/IdleDeadline.h b/Userland/Libraries/LibWeb/RequestIdleCallback/IdleDeadline.h
index 5222b3c0ab..3ceda83407 100644
--- a/Userland/Libraries/LibWeb/RequestIdleCallback/IdleDeadline.h
+++ b/Userland/Libraries/LibWeb/RequestIdleCallback/IdleDeadline.h
@@ -1,5 +1,6 @@
 /*
  * Copyright (c) 2021, Andreas Kling <kling@serenityos.org>
+ * Copyright (c) 2022, the SerenityOS developers.
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
@@ -18,16 +19,15 @@ public:
     using WrapperType = Bindings::IdleDeadlineWrapper;
     using AllowOwnPtr = TrueType;
 
-    static NonnullRefPtr<IdleDeadline> create(double time_remaining, bool did_timeout);
+    static NonnullRefPtr<IdleDeadline> create(bool did_timeout = false);
     virtual ~IdleDeadline() override;
 
-    double time_remaining() const { return m_time_remaining; }
+    double time_remaining() const;
     bool did_timeout() const { return m_did_timeout; }
 
 private:
-    IdleDeadline(double time_remaining, bool did_timeout);
+    IdleDeadline(bool did_timeout);
 
-    double m_time_remaining { 0 };
     bool m_did_timeout { false };
 };