Auto merge of #22049 - ferjm:timeranges, r=jdm

Implement TimeRanges interface

- [X] `./mach build -d` does not report any errors
- [X] `./mach test-tidy` does not report any errors
- [X] There are tests for these changes

Spec: https://html.spec.whatwg.org/multipage/media.html#time-ranges

<!-- Reviewable:start -->
---
This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/servo/servo/22049)
<!-- Reviewable:end -->

9 files changed, 281 insertions, 28 deletions

diff --git a/components/script/dom/mod.rs b/components/script/dom/mod.rs
index 88b50d54f2f..0c901a02d15 100644
--- a/components/script/dom/mod.rs
+++ b/components/script/dom/mod.rs
@@ -458,6 +458,7 @@ pub mod text;
 pub mod textcontrol;
 pub mod textdecoder;
 pub mod textencoder;
+pub mod timeranges;
 pub mod touch;
 pub mod touchevent;
 pub mod touchlist;
diff --git a/components/script/dom/timeranges.rs b/components/script/dom/timeranges.rs
new file mode 100644
index 00000000000..aab121c8a7f
--- /dev/null
+++ b/components/script/dom/timeranges.rs
@@ -0,0 +1,173 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+use dom::bindings::cell::DomRefCell;
+use dom::bindings::codegen::Bindings::TimeRangesBinding;
+use dom::bindings::codegen::Bindings::TimeRangesBinding::TimeRangesMethods;
+use dom::bindings::error::{Error, Fallible};
+use dom::bindings::num::Finite;
+use dom::bindings::reflector::{Reflector, reflect_dom_object};
+use dom::bindings::root::DomRoot;
+use dom::window::Window;
+use dom_struct::dom_struct;
+use std::fmt;
+
+#[derive(JSTraceable, MallocSizeOf)]
+struct TimeRange {
+    start: f64,
+    end: f64,
+}
+
+impl TimeRange {
+    pub fn union(&mut self, other: &TimeRange) {
+        self.start = f64::min(self.start, other.start);
+        self.end = f64::max(self.end, other.end);
+    }
+
+    fn contains(&self, time: f64) -> bool {
+        self.start <= time && time < self.end
+    }
+
+    fn is_overlapping(&self, other: &TimeRange) -> bool {
+        // This also covers the case where `self` is entirely contained within `other`,
+        // for example: `self` = [2,3) and `other` = [1,4).
+        self.contains(other.start) || self.contains(other.end) || other.contains(self.start)
+    }
+
+    fn is_contiguous(&self, other: &TimeRange) -> bool {
+        other.start == self.end || other.end == self.start
+    }
+
+    pub fn is_before(&self, other: &TimeRange) -> bool {
+        other.start >= self.end
+    }
+}
+
+impl fmt::Debug for TimeRange {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
+        write!(fmt, "[{},{})", self.start, self.end)
+    }
+}
+
+#[derive(Debug)]
+pub enum TimeRangesError {
+    EndOlderThanStart,
+    OutOfRange,
+}
+
+#[derive(Debug, JSTraceable, MallocSizeOf)]
+pub struct TimeRangesContainer {
+    ranges: Vec<TimeRange>,
+}
+
+impl TimeRangesContainer {
+    pub fn new() -> Self {
+        Self {
+            ranges: Vec::new(),
+        }
+    }
+
+    pub fn len(&self) -> u32 {
+        self.ranges.len() as u32
+    }
+
+    pub fn start(&self, index: u32) -> Result<f64, TimeRangesError> {
+        self.ranges.get(index as usize).map(|r| r.start).ok_or(TimeRangesError::OutOfRange)
+    }
+
+    pub fn end(&self, index: u32) -> Result<f64, TimeRangesError> {
+        self.ranges.get(index as usize).map(|r| r.end).ok_or(TimeRangesError::OutOfRange)
+    }
+
+    pub fn add(&mut self, start: f64, end: f64) -> Result<(), TimeRangesError> {
+        if start > end {
+            return Err(TimeRangesError::EndOlderThanStart);
+        }
+
+        let mut new_range = TimeRange { start, end };
+
+        // For each present range check if we need to:
+        // - merge with the added range, in case we are overlapping or contiguous,
+        // - insert in place, we are completely, not overlapping and not contiguous
+        //   in between two ranges.
+        let mut idx = 0;
+        while idx < self.ranges.len() {
+            if new_range.is_overlapping(&self.ranges[idx]) || new_range.is_contiguous(&self.ranges[idx]) {
+                // The ranges are either overlapping or contiguous,
+                // we need to merge the new range with the existing one.
+                new_range.union(&self.ranges[idx]);
+                self.ranges.remove(idx);
+            } else if new_range.is_before(&self.ranges[idx]) &&
+                (idx == 0 || self.ranges[idx - 1].is_before(&new_range)) {
+                // We are exactly after the current previous range and before the current
+                // range, while not overlapping with none of them.
+                // Or we are simply at the beginning.
+                self.ranges.insert(idx, new_range);
+                return Ok(());
+            } else {
+                idx += 1;
+            }
+        }
+
+        // Insert at the end.
+        self.ranges.insert(idx, new_range);
+
+        Ok(())
+    }
+}
+
+#[dom_struct]
+pub struct TimeRanges {
+    reflector_: Reflector,
+    ranges: DomRefCell<TimeRangesContainer>,
+}
+
+//XXX(ferjm) We'll get warnings about unused methods until we use this
+//           on the media element implementation.
+#[allow(dead_code)]
+impl TimeRanges {
+    fn new_inherited() -> TimeRanges {
+        Self {
+            reflector_: Reflector::new(),
+            ranges: DomRefCell::new(TimeRangesContainer::new()),
+        }
+    }
+
+    pub fn new(window: &Window) -> DomRoot<TimeRanges> {
+        reflect_dom_object(
+            Box::new(TimeRanges::new_inherited()),
+            window,
+            TimeRangesBinding::Wrap,
+        )
+    }
+}
+
+impl TimeRangesMethods for TimeRanges {
+    // https://html.spec.whatwg.org/multipage/#dom-timeranges-length
+    fn Length(&self) -> u32 {
+        self.ranges.borrow().len()
+    }
+
+    // https://html.spec.whatwg.org/multipage/#dom-timeranges-start
+    fn Start(&self, index: u32) -> Fallible<Finite<f64>> {
+        self.ranges
+            .borrow()
+            .start(index)
+            .map(Finite::wrap)
+            .map_err(|_| {
+                Error::IndexSize
+            })
+    }
+
+    // https://html.spec.whatwg.org/multipage/#dom-timeranges-end
+    fn End(&self, index: u32) -> Fallible<Finite<f64>> {
+        self.ranges
+            .borrow()
+            .end(index)
+            .map(Finite::wrap)
+            .map_err(|_| {
+                Error::IndexSize
+            })
+    }
+}
diff --git a/components/script/dom/webidls/TimeRanges.webidl b/components/script/dom/webidls/TimeRanges.webidl
new file mode 100644
index 00000000000..58390f98596
--- /dev/null
+++ b/components/script/dom/webidls/TimeRanges.webidl
@@ -0,0 +1,12 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+// https://html.spec.whatwg.org/multipage#time-ranges
+
+[Exposed=Window]
+interface TimeRanges {
+  readonly attribute unsigned long length;
+  [Throws] double start(unsigned long index);
+  [Throws] double end(unsigned long index);
+};
diff --git a/components/script/test.rs b/components/script/test.rs
index b907404da0b..5dd75edad8f 100644
--- a/components/script/test.rs
+++ b/components/script/test.rs
@@ -62,3 +62,7 @@ pub mod size_of {
 pub mod srcset {
     pub use dom::htmlimageelement::{parse_a_srcset_attribute, ImageSource, Descriptor};
 }
+
+pub mod timeranges {
+    pub use dom::timeranges::TimeRangesContainer;
+}
diff --git a/tests/unit/script/lib.rs b/tests/unit/script/lib.rs
index f8ffcaee26f..157531474d4 100644
--- a/tests/unit/script/lib.rs
+++ b/tests/unit/script/lib.rs
@@ -13,6 +13,8 @@
 #[cfg(test)] mod headers;
 #[cfg(test)] mod htmlareaelement;
 #[cfg(test)] mod htmlimageelement;
+#[cfg(test)] mod timeranges;
+
 
 /**
 ```compile_fail,E0277
diff --git a/tests/unit/script/timeranges.rs b/tests/unit/script/timeranges.rs
new file mode 100644
index 00000000000..3b2eaacf741
--- /dev/null
+++ b/tests/unit/script/timeranges.rs
@@ -0,0 +1,87 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+use script::test::timeranges::TimeRangesContainer;
+
+fn check(time_ranges: &TimeRangesContainer, expected: &'static str) {
+    assert_eq!(
+        format!("{:?}", time_ranges),
+        format!("TimeRangesContainer {{ ranges: [{}] }}", expected)
+    );
+}
+
+#[test]
+fn initial_state() {
+    let time_ranges = TimeRangesContainer::new();
+    assert_eq!(time_ranges.len(), 0);
+    assert!(time_ranges.start(0).is_err());
+    assert!(time_ranges.end(0).is_err());
+}
+
+#[test]
+fn error_if_start_is_older_than_end() {
+    let mut time_ranges = TimeRangesContainer::new();
+    assert!(time_ranges.add(2., 1.).is_err());
+}
+
+#[test]
+fn single_range() {
+    let mut time_ranges = TimeRangesContainer::new();
+    time_ranges.add(1., 2.).unwrap();
+    check(&time_ranges, "[1,2)");
+    assert_eq!(time_ranges.start(0).unwrap(), 1.);
+    assert_eq!(time_ranges.end(0).unwrap(), 2.);
+}
+
+#[test]
+fn add_order() {
+    let mut time_ranges_a = TimeRangesContainer::new();
+    for range in vec![(0., 2.), (3., 4.), (5., 100.)].iter() {
+        time_ranges_a.add(range.0, range.1).unwrap();
+    }
+    let expected = "[0,2), [3,4), [5,100)";
+    check(&time_ranges_a, expected);
+
+    let mut time_ranges_b = TimeRangesContainer::new();
+    // Add the values in time_ranges_a to time_ranges_b in reverse order.
+    for i in (0..time_ranges_a.len()).rev() {
+        time_ranges_b
+            .add(
+                time_ranges_a.start(i).unwrap(),
+                time_ranges_a.end(i).unwrap(),
+            )
+            .unwrap();
+    }
+    check(&time_ranges_b, expected);
+}
+
+#[test]
+fn add_overlapping() {
+    let mut time_ranges = TimeRangesContainer::new();
+
+    time_ranges.add(0., 2.).unwrap();
+    time_ranges.add(10., 11.).unwrap();
+    check(&time_ranges, "[0,2), [10,11)");
+
+    time_ranges.add(0., 2.).unwrap();
+    check(&time_ranges, "[0,2), [10,11)");
+
+    time_ranges.add(2., 3.).unwrap();
+    check(&time_ranges, "[0,3), [10,11)");
+
+    time_ranges.add(2., 6.).unwrap();
+    check(&time_ranges, "[0,6), [10,11)");
+
+    time_ranges.add(9., 10.).unwrap();
+    check(&time_ranges, "[0,6), [9,11)");
+
+    time_ranges.add(8., 10.).unwrap();
+    check(&time_ranges, "[0,6), [8,11)");
+
+    time_ranges.add(-1., 7.).unwrap();
+    check(&time_ranges, "[-1,7), [8,11)");
+
+    time_ranges.add(6., 9.).unwrap();
+    check(&time_ranges, "[-1,11)");
+}
diff --git a/tests/wpt/metadata/html/dom/interfaces.https.html.ini b/tests/wpt/metadata/html/dom/interfaces.https.html.ini
index c91f174f474..749f4ee5890 100644
--- a/tests/wpt/metadata/html/dom/interfaces.https.html.ini
+++ b/tests/wpt/metadata/html/dom/interfaces.https.html.ini
@@ -10034,33 +10034,6 @@
   [TextTrackCue interface: attribute onexit]
     expected: FAIL
 
-  [TimeRanges interface: existence and properties of interface object]
-    expected: FAIL
-
-  [TimeRanges interface object length]
-    expected: FAIL
-
-  [TimeRanges interface object name]
-    expected: FAIL
-
-  [TimeRanges interface: existence and properties of interface prototype object]
-    expected: FAIL
-
-  [TimeRanges interface: existence and properties of interface prototype object's "constructor" property]
-    expected: FAIL
-
-  [TimeRanges interface: existence and properties of interface prototype object's @@unscopables property]
-    expected: FAIL
-
-  [TimeRanges interface: attribute length]
-    expected: FAIL
-
-  [TimeRanges interface: operation start(unsigned long)]
-    expected: FAIL
-
-  [TimeRanges interface: operation end(unsigned long)]
-    expected: FAIL
-
   [TimeRanges must be primary interface of document.createElement("video").buffered]
     expected: FAIL
 
diff --git a/tests/wpt/mozilla/meta/MANIFEST.json b/tests/wpt/mozilla/meta/MANIFEST.json
index 660848e2586..42349d2c34f 100644
--- a/tests/wpt/mozilla/meta/MANIFEST.json
+++ b/tests/wpt/mozilla/meta/MANIFEST.json
@@ -27054,7 +27054,7 @@
    "testharness"
   ],
   "mozilla/interfaces.html": [
-   "9d262c595c6cbb624bc8acb9ef2ae26622154004",
+   "fba582932f67521659378db241b6d52a3ada250d",
    "testharness"
   ],
   "mozilla/interfaces.js": [
diff --git a/tests/wpt/mozilla/tests/mozilla/interfaces.html b/tests/wpt/mozilla/tests/mozilla/interfaces.html
index 9d262c595c6..fba582932f6 100644
--- a/tests/wpt/mozilla/tests/mozilla/interfaces.html
+++ b/tests/wpt/mozilla/tests/mozilla/interfaces.html
@@ -202,6 +202,7 @@ test_interfaces([
   "Text",
   "TextDecoder",
   "TextEncoder",
+  "TimeRanges",
   "Touch",
   "TouchEvent",
   "TouchList",