Auto merge of #7450 - benschulz:constellation-timer, r=jdm

Ordering guarantees for timers

This is an rough solution to the issue described in #3396. XHRs still do their own thing and an overall clean up is in order. Before I do that, though, I'd really like someone to sign off on the overall idea.

There's one major difference to what jdm layed out #3396: The timers remain with the window/worker and only the earliest expiring one is coordinated with the dedicated timer thread.
That means both the timer thread and the window/worker have to keep track of which timer expires next, which feels a bit wonky. However, the upshot is that there's no need for communication with the timer thread when a pipeline is frozen, thawed or dropped.

Most relvant parts are
 - the [`TimerScheduler`](https://github.com/servo/servo/commit/6f5f6619586379982321b5de7583d387df184504#diff-74137a6f50ab38e7a1e4d16920a66ce7R73), which is the new per-constellation timer task and
 - the [`ActiveTimers`](https://github.com/servo/servo/commit/6f5f6619586379982321b5de7583d387df184504#diff-86707d952414a2860b78bcf6c1db8e2eR34) which is what's left on the window/worker side.

<!-- Reviewable:start -->
[<img src="https://reviewable.io/review_button.png" height=40 alt="Review on Reviewable"/>](https://reviewable.io/reviews/servo/servo/7450)
<!-- Reviewable:end -->

1 files changed, 277 insertions, 201 deletions

diff --git a/components/script/timers.rs b/components/script/timers.rs
index 1704ba3cbbf..6c982cb1ad4 100644
--- a/components/script/timers.rs
+++ b/components/script/timers.rs
@@ -8,259 +8,335 @@ use dom::bindings::codegen::Bindings::FunctionBinding::Function;
 use dom::bindings::global::global_object_for_js_object;
 use dom::bindings::utils::Reflectable;
 use dom::window::ScriptHelpers;
-use horribly_inefficient_timers;
+use euclid::length::Length;
 use js::jsapi::{HandleValue, Heap, RootedValue};
 use js::jsval::{JSVal, UndefinedValue};
-use script_task::{CommonScriptMsg, ScriptChan, TimerSource};
-use std::borrow::ToOwned;
+use num::traits::Saturating;
+use script_traits::{MsDuration, precise_time_ms};
+use script_traits::{TimerEventChan, TimerEventId, TimerEventRequest, TimerSource};
 use std::cell::Cell;
-use std::cmp;
-use std::collections::HashMap;
+use std::cmp::{self, Ord, Ordering};
 use std::default::Default;
-use std::hash::{Hash, Hasher};
 use std::rc::Rc;
-use std::sync::mpsc::Select;
-use std::sync::mpsc::{Sender, channel};
+use std::sync::mpsc::Sender;
 use util::mem::HeapSizeOf;
 use util::str::DOMString;
-use util::task::spawn_named;
 
-#[derive(JSTraceable, PartialEq, Eq, Copy, Clone, HeapSizeOf)]
-pub struct TimerId(i32);
+#[derive(JSTraceable, PartialEq, Eq, Copy, Clone, HeapSizeOf, Hash, PartialOrd, Ord)]
+pub struct TimerHandle(i32);
 
 #[derive(JSTraceable, HeapSizeOf)]
 #[privatize]
-struct TimerHandle {
-    handle: TimerId,
-    data: TimerData,
-    #[ignore_heap_size_of = "channels are hard"]
-    control_chan: Option<Sender<TimerControlMsg>>,
+pub struct ActiveTimers {
+    #[ignore_heap_size_of = "Defined in std"]
+    timer_event_chan: Box<TimerEventChan + Send>,
+    #[ignore_heap_size_of = "Defined in std"]
+    scheduler_chan: Sender<TimerEventRequest>,
+    next_timer_handle: Cell<TimerHandle>,
+    timers: DOMRefCell<Vec<Timer>>,
+    suspended_since: Cell<Option<MsDuration>>,
+    /// Initially 0, increased whenever the associated document is reactivated
+    /// by the amount of ms the document was inactive. The current time can be
+    /// offset back by this amount for a coherent time across document
+    /// activations.
+    suspension_offset: Cell<MsDuration>,
+    /// Calls to `fire_timer` with a different argument than this get ignored.
+    /// They were previously scheduled and got invalidated when
+    ///  - timers were suspended,
+    ///  - the timer it was scheduled for got canceled or
+    ///  - a timer was added with an earlier callback time. In this case the
+    ///    original timer is rescheduled when it is the next one to get called.
+    expected_event_id: Cell<TimerEventId>,
+    /// The nesting level of the currently executing timer task or 0.
+    nesting_level: Cell<u32>,
 }
 
-#[derive(JSTraceable, Clone)]
-pub enum TimerCallback {
-    StringTimerCallback(DOMString),
-    FunctionTimerCallback(Rc<Function>)
+// Holder for the various JS values associated with setTimeout
+// (ie. function value to invoke and all arguments to pass
+//      to the function when calling it)
+// TODO: Handle rooting during fire_timer when movable GC is turned on
+#[derive(JSTraceable, HeapSizeOf)]
+#[privatize]
+struct Timer {
+    handle: TimerHandle,
+    source: TimerSource,
+    callback: InternalTimerCallback,
+    is_interval: IsInterval,
+    nesting_level: u32,
+    duration: MsDuration,
+    next_call: MsDuration,
 }
 
-impl HeapSizeOf for TimerCallback {
-    fn heap_size_of_children(&self) -> usize {
-        // FIXME: Rc<T> isn't HeapSizeOf and we can't ignore it due to #6870 and #6871
-        0
-    }
+// Enum allowing more descriptive values for the is_interval field
+#[derive(JSTraceable, PartialEq, Copy, Clone, HeapSizeOf)]
+pub enum IsInterval {
+    Interval,
+    NonInterval,
 }
 
-impl Hash for TimerId {
-    fn hash<H: Hasher>(&self, state: &mut H) {
-        let TimerId(id) = *self;
-        id.hash(state);
+impl Ord for Timer {
+    fn cmp(&self, other: &Timer) -> Ordering {
+        match self.next_call.cmp(&other.next_call).reverse() {
+            Ordering::Equal => self.handle.cmp(&other.handle).reverse(),
+            res @ _ => res
+        }
     }
 }
 
-impl TimerHandle {
-    fn cancel(&mut self) {
-        self.control_chan.as_ref().map(|chan| chan.send(TimerControlMsg::Cancel).ok());
-    }
-    fn suspend(&mut self) {
-        self.control_chan.as_ref().map(|chan| chan.send(TimerControlMsg::Suspend).ok());
-    }
-    fn resume(&mut self) {
-        self.control_chan.as_ref().map(|chan| chan.send(TimerControlMsg::Resume).ok());
+impl PartialOrd for Timer {
+    fn partial_cmp(&self, other: &Timer) -> Option<Ordering> {
+        Some(self.cmp(other))
     }
 }
 
-#[derive(JSTraceable, HeapSizeOf)]
-#[privatize]
-pub struct TimerManager {
-    active_timers: DOMRefCell<HashMap<TimerId, TimerHandle>>,
-    next_timer_handle: Cell<i32>,
-}
-
-
-impl Drop for TimerManager {
-    fn drop(&mut self) {
-        for (_, timer_handle) in &mut *self.active_timers.borrow_mut() {
-            timer_handle.cancel();
-        }
+impl Eq for Timer {}
+impl PartialEq for Timer {
+    fn eq(&self, other: &Timer) -> bool {
+        self as *const Timer == other as *const Timer
     }
 }
 
-// Enum allowing more descriptive values for the is_interval field
-#[derive(JSTraceable, PartialEq, Copy, Clone, HeapSizeOf)]
-pub enum IsInterval {
-    Interval,
-    NonInterval,
-}
-
-// Messages sent control timers from script task
-#[derive(JSTraceable, PartialEq, Copy, Clone, Debug)]
-pub enum TimerControlMsg {
-    Cancel,
-    Suspend,
-    Resume
+#[derive(Clone)]
+pub enum TimerCallback {
+    StringTimerCallback(DOMString),
+    FunctionTimerCallback(Rc<Function>),
 }
 
-// Holder for the various JS values associated with setTimeout
-// (ie. function value to invoke and all arguments to pass
-//      to the function when calling it)
-// TODO: Handle rooting during fire_timer when movable GC is turned on
-#[derive(JSTraceable, HeapSizeOf)]
-#[privatize]
-struct TimerData {
-    is_interval: IsInterval,
-    callback: TimerCallback,
-    args: Vec<Heap<JSVal>>
+#[derive(JSTraceable, Clone)]
+enum InternalTimerCallback {
+    StringTimerCallback(DOMString),
+    FunctionTimerCallback(Rc<Function>, Rc<Vec<Heap<JSVal>>>),
 }
 
-impl TimerManager {
-    pub fn new() -> TimerManager {
-        TimerManager {
-            active_timers: DOMRefCell::new(HashMap::new()),
-            next_timer_handle: Cell::new(0)
-        }
+impl HeapSizeOf for InternalTimerCallback {
+    fn heap_size_of_children(&self) -> usize {
+        // FIXME: Rc<T> isn't HeapSizeOf and we can't ignore it due to #6870 and #6871
+        0
     }
+}
 
-    pub fn suspend(&self) {
-        for (_, timer_handle) in &mut *self.active_timers.borrow_mut() {
-            timer_handle.suspend();
-        }
-    }
-    pub fn resume(&self) {
-        for (_, timer_handle) in &mut *self.active_timers.borrow_mut() {
-            timer_handle.resume();
+impl ActiveTimers {
+    pub fn new(timer_event_chan: Box<TimerEventChan + Send>,
+               scheduler_chan: Sender<TimerEventRequest>)
+               -> ActiveTimers {
+        ActiveTimers {
+            timer_event_chan: timer_event_chan,
+            scheduler_chan: scheduler_chan,
+            next_timer_handle: Cell::new(TimerHandle(1)),
+            timers: DOMRefCell::new(Vec::new()),
+            suspended_since: Cell::new(None),
+            suspension_offset: Cell::new(Length::new(0)),
+            expected_event_id: Cell::new(TimerEventId(0)),
+            nesting_level: Cell::new(0),
         }
     }
 
-    #[allow(unsafe_code)]
+    // see https://html.spec.whatwg.org/multipage/#timer-initialisation-steps
     pub fn set_timeout_or_interval(&self,
-                                  callback: TimerCallback,
-                                  arguments: Vec<HandleValue>,
-                                  timeout: i32,
-                                  is_interval: IsInterval,
-                                  source: TimerSource,
-                                  script_chan: Box<ScriptChan + Send>)
-                                  -> i32 {
-        let duration_ms = cmp::max(0, timeout) as u32;
-        let handle = self.next_timer_handle.get();
-        self.next_timer_handle.set(handle + 1);
-
-        // Spawn a new timer task; it will dispatch the `CommonScriptMsg::FireTimer`
-        // to the relevant script handler that will deal with it.
-        let (control_chan, control_port) = channel();
-        let spawn_name = match source {
-            TimerSource::FromWindow(_) if is_interval == IsInterval::Interval => "Window:SetInterval",
-            TimerSource::FromWorker if is_interval == IsInterval::Interval => "Worker:SetInterval",
-            TimerSource::FromWindow(_) => "Window:SetTimeout",
-            TimerSource::FromWorker => "Worker:SetTimeout",
-        }.to_owned();
-        spawn_named(spawn_name, move || {
-            let timeout_port = if is_interval == IsInterval::Interval {
-                horribly_inefficient_timers::periodic(duration_ms)
-            } else {
-                horribly_inefficient_timers::oneshot(duration_ms)
-            };
-            let control_port = control_port;
-
-            let select = Select::new();
-            let mut timeout_handle = select.handle(&timeout_port);
-            unsafe { timeout_handle.add() };
-            let mut control_handle = select.handle(&control_port);
-            unsafe { control_handle.add() };
-
-            loop {
-                let id = select.wait();
-
-                if id == timeout_handle.id() {
-                    timeout_port.recv().unwrap();
-                    if script_chan.send(CommonScriptMsg::FireTimer(source, TimerId(handle))).is_err() {
-                        break;
-                    }
-
-                    if is_interval == IsInterval::NonInterval {
-                        break;
-                    }
-                } else if id == control_handle.id() {
-                    match control_port.recv().unwrap() {
-                        TimerControlMsg::Suspend => {
-                            let msg = control_port.recv().unwrap();
-                            match msg {
-                                TimerControlMsg::Suspend => panic!("Nothing to suspend!"),
-                                TimerControlMsg::Resume => {},
-                                TimerControlMsg::Cancel => {
-                                    break;
-                                },
-                            }
-                        },
-                        TimerControlMsg::Resume => panic!("Nothing to resume!"),
-                        TimerControlMsg::Cancel => {
-                            break;
-                        }
-                    }
+                               callback: TimerCallback,
+                               arguments: Vec<HandleValue>,
+                               timeout: i32,
+                               is_interval: IsInterval,
+                               source: TimerSource)
+                               -> i32 {
+        assert!(self.suspended_since.get().is_none());
+
+        // step 3
+        let TimerHandle(new_handle) = self.next_timer_handle.get();
+        self.next_timer_handle.set(TimerHandle(new_handle + 1));
+
+        let timeout = cmp::max(0, timeout);
+        // step 7
+        let duration = self.clamp_duration(Length::new(timeout as u64));
+        let next_call = self.base_time() + duration;
+
+        let callback = match callback {
+            TimerCallback::StringTimerCallback(code_str) =>
+                InternalTimerCallback::StringTimerCallback(code_str),
+            TimerCallback::FunctionTimerCallback(function) => {
+                // This is a bit complicated, but this ensures that the vector's
+                // buffer isn't reallocated (and moved) after setting the Heap values
+                let mut args = Vec::with_capacity(arguments.len());
+                for _ in 0..arguments.len() {
+                    args.push(Heap::default());
                 }
-            }
-        });
-        let timer_id = TimerId(handle);
-        let timer = TimerHandle {
-            handle: timer_id,
-            control_chan: Some(control_chan),
-            data: TimerData {
-                is_interval: is_interval,
-                callback: callback,
-                args: Vec::with_capacity(arguments.len())
+                for (i, item) in arguments.iter().enumerate() {
+                    args.get_mut(i).unwrap().set(item.get());
+                }
+                InternalTimerCallback::FunctionTimerCallback(function, Rc::new(args))
             }
         };
-        self.active_timers.borrow_mut().insert(timer_id, timer);
-
-        // This is a bit complicated, but this ensures that the vector's
-        // buffer isn't reallocated (and moved) after setting the Heap values
-        let mut timers = self.active_timers.borrow_mut();
-        let mut timer = timers.get_mut(&timer_id).unwrap();
-        for _ in 0..arguments.len() {
-            timer.data.args.push(Heap::default());
-        }
-        for (i, item) in arguments.iter().enumerate() {
-            timer.data.args.get_mut(i).unwrap().set(item.get());
+
+        let timer = Timer {
+            handle: TimerHandle(new_handle),
+            source: source,
+            callback: callback,
+            is_interval: is_interval,
+            duration: duration,
+            // step 6
+            nesting_level: self.nesting_level.get() + 1,
+            next_call: next_call,
+        };
+
+        self.insert_timer(timer);
+
+        let TimerHandle(max_handle) = self.timers.borrow().last().unwrap().handle;
+        if max_handle == new_handle {
+            self.schedule_timer_call();
         }
-        handle
+
+        // step 10
+        new_handle
     }
 
     pub fn clear_timeout_or_interval(&self, handle: i32) {
-        let mut timer_handle = self.active_timers.borrow_mut().remove(&TimerId(handle));
-        match timer_handle {
-            Some(ref mut handle) => handle.cancel(),
-            None => {}
+        let handle = TimerHandle(handle);
+        let was_next = self.is_next_timer(handle);
+
+        self.timers.borrow_mut().retain(|t| t.handle != handle);
+
+        if was_next {
+            self.invalidate_expected_event_id();
+            self.schedule_timer_call();
         }
     }
 
+    // see https://html.spec.whatwg.org/multipage/#timer-initialisation-steps
     #[allow(unsafe_code)]
-    pub fn fire_timer<T: Reflectable>(&self, timer_id: TimerId, this: &T) {
-
-        let (is_interval, callback, args): (IsInterval, TimerCallback, Vec<JSVal>) =
-            match self.active_timers.borrow().get(&timer_id) {
-                Some(timer_handle) =>
-                    (timer_handle.data.is_interval,
-                     timer_handle.data.callback.clone(),
-                     timer_handle.data.args.iter().map(|arg| arg.get()).collect()),
-                None => return,
+    pub fn fire_timer<T: Reflectable>(&self, id: TimerEventId, this: &T) {
+        let expected_id = self.expected_event_id.get();
+        if expected_id != id {
+            debug!("ignoring timer fire event {:?} (expected {:?}", id, expected_id);
+            return;
+        }
+
+        assert!(self.suspended_since.get().is_none());
+
+        let base_time = self.base_time();
+
+        // Since the event id was the expected one, at least one timer should be due.
+        assert!(base_time >= self.timers.borrow().last().unwrap().next_call);
+
+        loop {
+            let timer = {
+                let mut timers = self.timers.borrow_mut();
+
+                if timers.is_empty() || timers.last().unwrap().next_call > base_time {
+                    break;
+                }
+
+                timers.pop().unwrap()
             };
+            let callback = timer.callback.clone();
 
-        match callback {
-            TimerCallback::FunctionTimerCallback(function) => {
-                let arg_handles = args.iter().by_ref().map(|arg| unsafe {
-                    HandleValue::from_marked_location(arg)
-                }).collect();
-                let _ = function.Call_(this, arg_handles, Report);
-            }
-            TimerCallback::StringTimerCallback(code_str) => {
-                let proxy = this.reflector().get_jsobject();
-                let cx = global_object_for_js_object(proxy.get()).r().get_cx();
-                let mut rval = RootedValue::new(cx, UndefinedValue());
-                this.evaluate_js_on_global_with_result(&code_str, rval.handle_mut());
+            // prep for step 6 in nested set_timeout_or_interval calls
+            self.nesting_level.set(timer.nesting_level);
+
+            // step 4.3
+            if timer.is_interval == IsInterval::Interval {
+                let mut timer = timer;
+
+                // step 7
+                timer.duration = self.clamp_duration(timer.duration);
+                // step 8, 9
+                timer.nesting_level += 1;
+                timer.next_call = base_time + timer.duration;
+                self.insert_timer(timer);
             }
+
+            // step 14
+            match callback {
+                InternalTimerCallback::StringTimerCallback(code_str) => {
+                    let proxy = this.reflector().get_jsobject();
+                    let cx = global_object_for_js_object(proxy.get()).r().get_cx();
+                    let mut rval = RootedValue::new(cx, UndefinedValue());
+
+                    this.evaluate_js_on_global_with_result(&code_str, rval.handle_mut());
+                },
+                InternalTimerCallback::FunctionTimerCallback(function, arguments) => {
+                    let arguments: Vec<JSVal> = arguments.iter().map(|arg| arg.get()).collect();
+                    let arguments = arguments.iter().by_ref().map(|arg| unsafe {
+                        HandleValue::from_marked_location(arg)
+                    }).collect();
+
+                    let _ = function.Call_(this, arguments, Report);
+                }
+            };
+
+            self.nesting_level.set(0);
         }
 
-        if is_interval == IsInterval::NonInterval {
-            self.active_timers.borrow_mut().remove(&timer_id);
+        self.schedule_timer_call();
+    }
+
+    fn insert_timer(&self, timer: Timer) {
+        let mut timers = self.timers.borrow_mut();
+        let insertion_index = timers.binary_search(&timer).err().unwrap();
+        timers.insert(insertion_index, timer);
+    }
+
+    fn is_next_timer(&self, handle: TimerHandle) -> bool {
+        match self.timers.borrow().last() {
+            None => false,
+            Some(ref max_timer) => max_timer.handle == handle
         }
     }
+
+    fn schedule_timer_call(&self) {
+        assert!(self.suspended_since.get().is_none());
+
+        let timers = self.timers.borrow();
+
+        if let Some(timer) = timers.last() {
+            let expected_event_id = self.invalidate_expected_event_id();
+
+            let delay = Length::new(timer.next_call.get().saturating_sub(precise_time_ms().get()));
+            let request = TimerEventRequest(self.timer_event_chan.clone(), timer.source,
+                                            expected_event_id, delay);
+            self.scheduler_chan.send(request).unwrap();
+        }
+    }
+
+    pub fn suspend(&self) {
+        assert!(self.suspended_since.get().is_none());
+
+        self.suspended_since.set(Some(precise_time_ms()));
+        self.invalidate_expected_event_id();
+    }
+
+    pub fn resume(&self) {
+        assert!(self.suspended_since.get().is_some());
+
+        let additional_offset = match self.suspended_since.get() {
+            Some(suspended_since) => precise_time_ms() - suspended_since,
+            None => panic!("Timers are not suspended.")
+        };
+
+        self.suspension_offset.set(self.suspension_offset.get() + additional_offset);
+
+        self.schedule_timer_call();
+    }
+
+    fn base_time(&self) -> MsDuration {
+        precise_time_ms() - self.suspension_offset.get()
+    }
+
+    // see step 7 of https://html.spec.whatwg.org/multipage/#timer-initialisation-steps
+    fn clamp_duration(&self, unclamped: MsDuration) -> MsDuration {
+        let ms = if self.nesting_level.get() > 5 {
+            4
+        } else {
+            0
+        };
+
+        cmp::max(Length::new(ms), unclamped)
+    }
+
+    fn invalidate_expected_event_id(&self) -> TimerEventId {
+        let TimerEventId(currently_expected) = self.expected_event_id.get();
+        let next_id = TimerEventId(currently_expected + 1);
+        debug!("invalidating expected timer (was {:?}, now {:?}", currently_expected, next_id);
+        self.expected_event_id.set(next_id);
+        next_id
+    }
 }