Use a BTreeMap for Document::animation_frame_list (fixes #9834)

The callbacks must stay ordered.

4 files changed, 66 insertions, 10 deletions

diff --git a/components/script/dom/bindings/trace.rs b/components/script/dom/bindings/trace.rs
index a318ca00cb5..7bfb6978ee6 100644
--- a/components/script/dom/bindings/trace.rs
+++ b/components/script/dom/bindings/trace.rs
@@ -70,7 +70,7 @@ use serde::{Deserialize, Serialize};
 use smallvec::SmallVec;
 use std::boxed::FnBox;
 use std::cell::{Cell, UnsafeCell};
-use std::collections::{HashMap, HashSet};
+use std::collections::{BTreeMap, HashMap, HashSet};
 use std::ffi::CString;
 use std::hash::{BuildHasher, Hash};
 use std::intrinsics::return_address;
@@ -246,6 +246,16 @@ impl<K, V, S> JSTraceable for HashMap<K, V, S>
     }
 }
 
+impl<K: Ord + JSTraceable, V: JSTraceable> JSTraceable for BTreeMap<K, V> {
+    #[inline]
+    fn trace(&self, trc: *mut JSTracer) {
+        for (k, v) in self {
+            k.trace(trc);
+            v.trace(trc);
+        }
+    }
+}
+
 impl<A: JSTraceable, B: JSTraceable> JSTraceable for (A, B) {
     #[inline]
     fn trace(&self, trc: *mut JSTracer) {
diff --git a/components/script/dom/document.rs b/components/script/dom/document.rs
index a1e256dede1..501ad242305 100644
--- a/components/script/dom/document.rs
+++ b/components/script/dom/document.rs
@@ -98,10 +98,10 @@ use std::ascii::AsciiExt;
 use std::borrow::ToOwned;
 use std::boxed::FnBox;
 use std::cell::{Cell, Ref, RefMut};
-use std::collections::HashMap;
 use std::collections::hash_map::Entry::{Occupied, Vacant};
+use std::collections::{BTreeMap, HashMap};
 use std::default::Default;
-use std::iter::FromIterator;
+use std::mem;
 use std::ptr;
 use std::rc::Rc;
 use std::sync::Arc;
@@ -185,7 +185,7 @@ pub struct Document {
     /// https://html.spec.whatwg.org/multipage/#list-of-animation-frame-callbacks
     /// List of animation frame callbacks
     #[ignore_heap_size_of = "closures are hard"]
-    animation_frame_list: DOMRefCell<HashMap<u32, Box<FnBox(f64)>>>,
+    animation_frame_list: DOMRefCell<BTreeMap<u32, Box<FnBox(f64)>>>,
     /// Tracks all outstanding loads related to this document.
     loader: DOMRefCell<DocumentLoader>,
     /// The current active HTML parser, to allow resuming after interruptions.
@@ -1248,11 +1248,8 @@ impl Document {
 
     /// https://html.spec.whatwg.org/multipage/#run-the-animation-frame-callbacks
     pub fn run_the_animation_frame_callbacks(&self) {
-        let animation_frame_list;
-        {
-            let mut list = self.animation_frame_list.borrow_mut();
-            animation_frame_list = Vec::from_iter(list.drain());
-        }
+        let animation_frame_list =
+            mem::replace(&mut *self.animation_frame_list.borrow_mut(), BTreeMap::new());
         let performance = self.window.Performance();
         let performance = performance.r();
         let timing = performance.Now();
@@ -1590,7 +1587,7 @@ impl Document {
             asap_scripts_set: DOMRefCell::new(vec![]),
             scripting_enabled: Cell::new(true),
             animation_frame_ident: Cell::new(0),
-            animation_frame_list: DOMRefCell::new(HashMap::new()),
+            animation_frame_list: DOMRefCell::new(BTreeMap::new()),
             loader: DOMRefCell::new(doc_loader),
             current_parser: Default::default(),
             reflow_timeout: Cell::new(None),
diff --git a/tests/wpt/mozilla/meta/MANIFEST.json b/tests/wpt/mozilla/meta/MANIFEST.json
index b12f912b49e..476af1d52a0 100644
--- a/tests/wpt/mozilla/meta/MANIFEST.json
+++ b/tests/wpt/mozilla/meta/MANIFEST.json
@@ -5562,6 +5562,12 @@
             "url": "/_mozilla/mozilla/collections.html"
           }
         ],
+        "mozilla/deterministic-raf.html": [
+          {
+            "path": "mozilla/deterministic-raf.html",
+            "url": "/_mozilla/mozilla/deterministic-raf.html"
+          }
+        ],
         "mozilla/documentElement.html": [
           {
             "path": "mozilla/documentElement.html",
diff --git a/tests/wpt/mozilla/tests/mozilla/deterministic-raf.html b/tests/wpt/mozilla/tests/mozilla/deterministic-raf.html
new file mode 100644
index 00000000000..441664829a1
--- /dev/null
+++ b/tests/wpt/mozilla/tests/mozilla/deterministic-raf.html
@@ -0,0 +1,43 @@
+<!doctype html>
+<meta charset="utf-8">
+<title></title>
+<script src="/resources/testharness.js"></script>
+<script src="/resources/testharnessreport.js"></script>
+<script>
+    async_test(function (t) {
+        var i = 0;
+        var log = [];
+        var loopB_ended = false;
+
+        var loopA = function () {
+            log.push("A");
+            if (i++ < 5) {
+                requestAnimationFrame(loopA);
+            } else {
+                assert_true(loopB_ended);
+                t.step(function () {
+                    assert_array_equals(log,
+                                        ["A", "B", "A", "B", "A", "B", "A", "B", "A", "B", "A"]);
+                });
+                t.done();
+            }
+        };
+
+        var loopB = function () {
+            log.push("B");
+            if (i < 5) {
+                requestAnimationFrame(loopB);
+            } else {
+                assert_false(loopB_ended);
+                loopB_ended = true;
+                t.step(function () {
+                    assert_array_equals(log,
+                                        ["A", "B", "A", "B", "A", "B", "A", "B", "A", "B"]);
+                });
+            }
+        };
+
+        loopA();
+        loopB();
+    }, "Concurrent requestAnimationFrame loops are deterministic");
+</script>