Auto merge of #8506 - nox:finish-ranges, r=dzbarsky

Properly propagate changes when range or trees are mutated

Does the same thing as #6817, but storing Range instances directly in their start and end containers.

Cc @dzbarsky

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

1 files changed, 336 insertions, 56 deletions

diff --git a/components/script/dom/range.rs b/components/script/dom/range.rs
index 58200ee35f2..03db51ba0d8 100644
--- a/components/script/dom/range.rs
+++ b/components/script/dom/range.rs
@@ -16,14 +16,17 @@ use dom::bindings::inheritance::Castable;
 use dom::bindings::inheritance::{CharacterDataTypeId, NodeTypeId};
 use dom::bindings::js::{JS, MutHeap, Root, RootedReference};
 use dom::bindings::reflector::{Reflector, reflect_dom_object};
-use dom::bindings::trace::RootedVec;
+use dom::bindings::trace::{JSTraceable, RootedVec};
+use dom::bindings::weakref::{WeakRef, WeakRefVec};
 use dom::characterdata::CharacterData;
 use dom::document::Document;
 use dom::documentfragment::DocumentFragment;
-use dom::node::Node;
+use dom::node::{Node, UnbindContext};
 use dom::text::Text;
-use std::cell::Cell;
+use js::jsapi::JSTracer;
+use std::cell::{Cell, UnsafeCell};
 use std::cmp::{Ord, Ordering, PartialEq, PartialOrd};
+use util::mem::HeapSizeOf;
 use util::str::DOMString;
 
 #[dom_struct]
@@ -52,10 +55,15 @@ impl Range {
                start_container: &Node, start_offset: u32,
                end_container: &Node, end_offset: u32)
                -> Root<Range> {
-        reflect_dom_object(box Range::new_inherited(start_container, start_offset,
-                                                    end_container, end_offset),
-                           GlobalRef::Window(document.window()),
-                           RangeBinding::Wrap)
+        let range = reflect_dom_object(box Range::new_inherited(start_container, start_offset,
+                                                                end_container, end_offset),
+                                       GlobalRef::Window(document.window()),
+                                       RangeBinding::Wrap);
+        start_container.ranges().push(WeakRef::new(&range));
+        if start_container != end_container {
+            end_container.ranges().push(WeakRef::new(&range));
+        }
+        range
     }
 
     // https://dom.spec.whatwg.org/#dom-range
@@ -121,19 +129,31 @@ impl Range {
     }
 
     // https://dom.spec.whatwg.org/#concept-range-bp-set
-    pub fn set_start(&self, node: &Node, offset: u32) {
-        self.start.set(node, offset);
-        if !(self.start <= self.end) {
-            self.end.set(node, offset);
+    fn set_start(&self, node: &Node, offset: u32) {
+        if &self.start.node != node {
+            if self.start.node == self.end.node {
+                node.ranges().push(WeakRef::new(&self));
+            } else if &self.end.node == node {
+                self.StartContainer().ranges().remove(self);
+            } else {
+                node.ranges().push(self.StartContainer().ranges().remove(self));
+            }
         }
+        self.start.set(node, offset);
     }
 
     // https://dom.spec.whatwg.org/#concept-range-bp-set
-    pub fn set_end(&self, node: &Node, offset: u32) {
-        self.end.set(node, offset);
-        if !(self.end >= self.start) {
-            self.start.set(node, offset);
+    fn set_end(&self, node: &Node, offset: u32) {
+        if &self.end.node != node {
+            if self.end.node == self.start.node {
+                node.ranges().push(WeakRef::new(&self));
+            } else if &self.start.node == node {
+                self.EndContainer().ranges().remove(self);
+            } else {
+                node.ranges().push(self.EndContainer().ranges().remove(self));
+            }
         }
+        self.end.set(node, offset);
     }
 
     // https://dom.spec.whatwg.org/#dom-range-comparepointnode-offset
@@ -206,7 +226,7 @@ impl RangeMethods for Range {
         unreachable!();
     }
 
-    // https://dom.spec.whatwg.org/#dom-range-setstartnode-offset
+    // https://dom.spec.whatwg.org/#dom-range-setstart
     fn SetStart(&self, node: &Node, offset: u32) -> ErrorResult {
         if node.is_doctype() {
             // Step 1.
@@ -215,13 +235,17 @@ impl RangeMethods for Range {
             // Step 2.
             Err(Error::IndexSize)
         } else {
-            // Step 3-4.
+            // Step 3.
             self.set_start(node, offset);
+            if !(self.start <= self.end) {
+                // Step 4.
+                self.set_end(node, offset);
+            }
             Ok(())
         }
     }
 
-    // https://dom.spec.whatwg.org/#dom-range-setendnode-offset
+    // https://dom.spec.whatwg.org/#dom-range-setend
     fn SetEnd(&self, node: &Node, offset: u32) -> ErrorResult {
         if node.is_doctype() {
             // Step 1.
@@ -230,59 +254,63 @@ impl RangeMethods for Range {
             // Step 2.
             Err(Error::IndexSize)
         } else {
-            // Step 3-4.
+            // Step 3.
             self.set_end(node, offset);
+            if !(self.end >= self.start) {
+                // Step 4.
+                self.set_start(node, offset);
+            }
             Ok(())
         }
     }
 
-    // https://dom.spec.whatwg.org/#dom-range-setstartbeforenode
+    // https://dom.spec.whatwg.org/#dom-range-setstartbefore
     fn SetStartBefore(&self, node: &Node) -> ErrorResult {
         let parent = try!(node.GetParentNode().ok_or(Error::InvalidNodeType));
         self.SetStart(parent.r(), node.index())
     }
 
-    // https://dom.spec.whatwg.org/#dom-range-setstartafternode
+    // https://dom.spec.whatwg.org/#dom-range-setstartafter
     fn SetStartAfter(&self, node: &Node) -> ErrorResult {
         let parent = try!(node.GetParentNode().ok_or(Error::InvalidNodeType));
         self.SetStart(parent.r(), node.index() + 1)
     }
 
-    // https://dom.spec.whatwg.org/#dom-range-setendbeforenode
+    // https://dom.spec.whatwg.org/#dom-range-setendbefore
     fn SetEndBefore(&self, node: &Node) -> ErrorResult {
         let parent = try!(node.GetParentNode().ok_or(Error::InvalidNodeType));
         self.SetEnd(parent.r(), node.index())
     }
 
-    // https://dom.spec.whatwg.org/#dom-range-setendafternode
+    // https://dom.spec.whatwg.org/#dom-range-setendafter
     fn SetEndAfter(&self, node: &Node) -> ErrorResult {
         let parent = try!(node.GetParentNode().ok_or(Error::InvalidNodeType));
         self.SetEnd(parent.r(), node.index() + 1)
     }
 
-    // https://dom.spec.whatwg.org/#dom-range-collapsetostart
+    // https://dom.spec.whatwg.org/#dom-range-collapse
     fn Collapse(&self, to_start: bool) {
         if to_start {
-            self.end.set(&self.StartContainer(), self.StartOffset());
+            self.set_end(&self.StartContainer(), self.StartOffset());
         } else {
-            self.start.set(&self.EndContainer(), self.EndOffset());
+            self.set_start(&self.EndContainer(), self.EndOffset());
         }
     }
 
-    // https://dom.spec.whatwg.org/#dom-range-selectnodenode
+    // https://dom.spec.whatwg.org/#dom-range-selectnode
     fn SelectNode(&self, node: &Node) -> ErrorResult {
         // Steps 1, 2.
         let parent = try!(node.GetParentNode().ok_or(Error::InvalidNodeType));
         // Step 3.
         let index = node.index();
         // Step 4.
-        self.start.set(&parent, index);
+        self.set_start(&parent, index);
         // Step 5.
-        self.end.set(&parent, index + 1);
+        self.set_end(&parent, index + 1);
         Ok(())
     }
 
-    // https://dom.spec.whatwg.org/#dom-range-selectnodecontentsnode
+    // https://dom.spec.whatwg.org/#dom-range-selectnodecontents
     fn SelectNodeContents(&self, node: &Node) -> ErrorResult {
         if node.is_doctype() {
             // Step 1.
@@ -291,13 +319,13 @@ impl RangeMethods for Range {
         // Step 2.
         let length = node.len();
         // Step 3.
-        self.start.set(node, 0);
+        self.set_start(node, 0);
         // Step 4.
-        self.end.set(node, length);
+        self.set_end(node, length);
         Ok(())
     }
 
-    // https://dom.spec.whatwg.org/#dom-range-compareboundarypointshow-sourcerange
+    // https://dom.spec.whatwg.org/#dom-range-compareboundarypoints
     fn CompareBoundaryPoints(&self, how: u16, other: &Range)
                              -> Fallible<i16> {
         if how > RangeConstants::END_TO_START {
@@ -342,7 +370,7 @@ impl RangeMethods for Range {
                    &self.EndContainer(), self.EndOffset())
     }
 
-    // https://dom.spec.whatwg.org/#dom-range-ispointinrangenode-offset
+    // https://dom.spec.whatwg.org/#dom-range-ispointinrange
     fn IsPointInRange(&self, node: &Node, offset: u32) -> Fallible<bool> {
         match self.compare_point(node, offset) {
             Ok(Ordering::Less) => Ok(false),
@@ -356,7 +384,7 @@ impl RangeMethods for Range {
         }
     }
 
-    // https://dom.spec.whatwg.org/#dom-range-comparepointnode-offset
+    // https://dom.spec.whatwg.org/#dom-range-comparepoint
     fn ComparePoint(&self, node: &Node, offset: u32) -> Fallible<i16> {
         self.compare_point(node, offset).map(|order| {
             match order {
@@ -410,12 +438,10 @@ impl RangeMethods for Range {
         }
 
         if end_node == start_node {
-            if let Some(text) = start_node.downcast::<CharacterData>() {
-                // Step 4.1.
-                let clone = start_node.CloneNode(true);
-                // Step 4.2.
-                let text = text.SubstringData(start_offset, end_offset - start_offset);
-                clone.downcast::<CharacterData>().unwrap().SetData(text.unwrap());
+            if let Some(cdata) = start_node.downcast::<CharacterData>() {
+                // Steps 4.1-2.
+                let data = cdata.SubstringData(start_offset, end_offset - start_offset).unwrap();
+                let clone = cdata.clone_with_data(data, &start_node.owner_doc());
                 // Step 4.3.
                 try!(fragment.upcast::<Node>().AppendChild(&clone));
                 // Step 4.4
@@ -429,13 +455,11 @@ impl RangeMethods for Range {
 
         if let Some(child) = first_contained_child {
             // Step 13.
-            if let Some(text) = child.downcast::<CharacterData>() {
+            if let Some(cdata) = child.downcast::<CharacterData>() {
                 assert!(child == start_node);
-                // Step 13.1.
-                let clone = start_node.CloneNode(true); // CharacterData has no children.
-                // Step 13.2
-                let text = text.SubstringData(start_offset, start_node.len() - start_offset);
-                clone.downcast::<CharacterData>().unwrap().SetData(text.unwrap());
+                // Steps 13.1-2.
+                let data = cdata.SubstringData(start_offset, start_node.len() - start_offset).unwrap();
+                let clone = cdata.clone_with_data(data, &start_node.owner_doc());
                 // Step 13.3.
                 try!(fragment.upcast::<Node>().AppendChild(&clone));
             } else {
@@ -466,13 +490,11 @@ impl RangeMethods for Range {
 
         if let Some(child) = last_contained_child {
             // Step 16.
-            if let Some(text) = child.downcast::<CharacterData>() {
+            if let Some(cdata) = child.downcast::<CharacterData>() {
                 assert!(child == end_node);
-                // Step 16.1.
-                let clone = end_node.CloneNode(true); // CharacterData has no children.
-                // Step 16.2.
-                let text = text.SubstringData(0, end_offset);
-                clone.downcast::<CharacterData>().unwrap().SetData(text.unwrap());
+                // Steps 16.1-2.
+                let data = cdata.SubstringData(0, end_offset).unwrap();
+                let clone = cdata.clone_with_data(data, &start_node.owner_doc());
                 // Step 16.3.
                 try!(fragment.upcast::<Node>().AppendChild(&clone));
             } else {
@@ -839,10 +861,12 @@ impl BoundaryPoint {
         }
     }
 
-    fn set(&self, node: &Node, offset: u32) {
-        debug_assert!(!node.is_doctype());
-        debug_assert!(offset <= node.len());
+    pub fn set(&self, node: &Node, offset: u32) {
         self.node.set(node);
+        self.set_offset(offset);
+    }
+
+    pub fn set_offset(&self, offset: u32) {
         self.offset.set(offset);
     }
 }
@@ -900,3 +924,259 @@ fn bp_position(a_node: &Node, a_offset: u32,
         Some(Ordering::Less)
     }
 }
+
+pub struct WeakRangeVec {
+    cell: UnsafeCell<WeakRefVec<Range>>,
+}
+
+#[allow(unsafe_code)]
+impl WeakRangeVec {
+    /// Create a new vector of weak references.
+    pub fn new() -> Self {
+        WeakRangeVec { cell: UnsafeCell::new(WeakRefVec::new()) }
+    }
+
+    /// Whether that vector of ranges is empty.
+    pub fn is_empty(&self) -> bool {
+        unsafe { (*self.cell.get()).is_empty() }
+    }
+
+    /// Used for steps 2.1-2. when inserting a node.
+    /// https://dom.spec.whatwg.org/#concept-node-insert
+    pub fn increase_above(&self, node: &Node, offset: u32, delta: u32) {
+        self.map_offset_above(node, offset, |offset| offset + delta);
+    }
+
+    /// Used for steps 4-5. when removing a node.
+    /// https://dom.spec.whatwg.org/#concept-node-remove
+    pub fn decrease_above(&self, node: &Node, offset: u32, delta: u32) {
+        self.map_offset_above(node, offset, |offset| offset - delta);
+    }
+
+    /// Used for steps 2-3. when removing a node.
+    /// https://dom.spec.whatwg.org/#concept-node-remove
+    pub fn drain_to_parent(&self, context: &UnbindContext, child: &Node) {
+        if self.is_empty() {
+            return;
+        }
+
+        let offset = context.index();
+        let parent = context.parent;
+        unsafe {
+            let mut ranges = &mut *self.cell.get();
+
+            ranges.update(|entry| {
+                let range = entry.root().unwrap();
+                if &range.start.node == parent || &range.end.node == parent {
+                    entry.remove();
+                }
+                if &range.start.node == child {
+                    range.start.set(context.parent, offset);
+                }
+                if &range.end.node == child {
+                    range.end.set(context.parent, offset);
+                }
+            });
+
+            (*context.parent.ranges().cell.get()).extend(ranges.drain(..));
+        }
+    }
+
+    /// Used for steps 7.1-2. when normalizing a node.
+    /// https://dom.spec.whatwg.org/#dom-node-normalize
+    pub fn drain_to_preceding_text_sibling(&self, node: &Node, sibling: &Node, length: u32) {
+        if self.is_empty() {
+            return;
+        }
+
+        unsafe {
+            let mut ranges = &mut *self.cell.get();
+
+            ranges.update(|entry| {
+                let range = entry.root().unwrap();
+                if &range.start.node == sibling || &range.end.node == sibling {
+                    entry.remove();
+                }
+                if &range.start.node == node {
+                    range.start.set(sibling, range.StartOffset() + length);
+                }
+                if &range.end.node == node {
+                    range.end.set(sibling, range.EndOffset() + length);
+                }
+            });
+
+            (*sibling.ranges().cell.get()).extend(ranges.drain(..));
+        }
+    }
+
+    /// Used for steps 7.3-4. when normalizing a node.
+    /// https://dom.spec.whatwg.org/#dom-node-normalize
+    pub fn move_to_text_child_at(&self,
+                                 node: &Node, offset: u32,
+                                 child: &Node, new_offset: u32) {
+        unsafe {
+            let child_ranges = &mut *child.ranges().cell.get();
+
+            (*self.cell.get()).update(|entry| {
+                let range = entry.root().unwrap();
+
+                let node_is_start = &range.start.node == node;
+                let node_is_end = &range.end.node == node;
+
+                let move_start = node_is_start && range.StartOffset() == offset;
+                let move_end = node_is_end && range.EndOffset() == offset;
+
+                let remove_from_node = move_start && move_end ||
+                                       move_start && !node_is_end ||
+                                       move_end && !node_is_start;
+
+                let already_in_child = &range.start.node == child || &range.end.node == child;
+                let push_to_child = !already_in_child && (move_start || move_end);
+
+                if remove_from_node {
+                    let ref_ = entry.remove();
+                    if push_to_child {
+                        child_ranges.push(ref_);
+                    }
+                } else if push_to_child {
+                    child_ranges.push(WeakRef::new(&range));
+                }
+
+                if move_start {
+                    range.start.set(child, new_offset);
+                }
+                if move_end {
+                    range.end.set(child, new_offset);
+                }
+            });
+        }
+    }
+
+    /// Used for steps 8-11. when replacing character data.
+    /// https://dom.spec.whatwg.org/#concept-cd-replace
+    pub fn replace_code_units(&self,
+                              node: &Node, offset: u32,
+                              removed_code_units: u32, added_code_units: u32) {
+        self.map_offset_above(node, offset, |range_offset| {
+            if range_offset <= offset + removed_code_units {
+                offset
+            } else {
+                range_offset + added_code_units - removed_code_units
+            }
+        });
+    }
+
+    /// Used for steps 7.2-3. when splitting a text node.
+    /// https://dom.spec.whatwg.org/#concept-text-split
+    pub fn move_to_following_text_sibling_above(&self,
+                                                node: &Node, offset: u32,
+                                                sibling: &Node) {
+        unsafe {
+            let sibling_ranges = &mut *sibling.ranges().cell.get();
+
+            (*self.cell.get()).update(|entry| {
+                let range = entry.root().unwrap();
+                let start_offset = range.StartOffset();
+                let end_offset = range.EndOffset();
+
+                let node_is_start = &range.start.node == node;
+                let node_is_end = &range.end.node == node;
+
+                let move_start = node_is_start && start_offset > offset;
+                let move_end = node_is_end && end_offset > offset;
+
+                let remove_from_node = move_start && move_end ||
+                                       move_start && !node_is_end ||
+                                       move_end && !node_is_start;
+
+                let already_in_sibling =
+                    &range.start.node == sibling || &range.end.node == sibling;
+                let push_to_sibling = !already_in_sibling && (move_start || move_end);
+
+                if remove_from_node {
+                    let ref_ = entry.remove();
+                    if push_to_sibling {
+                        sibling_ranges.push(ref_);
+                    }
+                } else if push_to_sibling {
+                    sibling_ranges.push(WeakRef::new(&range));
+                }
+
+                if move_start {
+                    range.start.set(sibling, start_offset - offset);
+                }
+                if move_end {
+                    range.end.set(sibling, end_offset - offset);
+                }
+            });
+        }
+    }
+
+    /// Used for steps 7.4-5. when splitting a text node.
+    /// https://dom.spec.whatwg.org/#concept-text-split
+    pub fn increment_at(&self, node: &Node, offset: u32) {
+        unsafe {
+            (*self.cell.get()).update(|entry| {
+                let range = entry.root().unwrap();
+                if &range.start.node == node && offset == range.StartOffset() {
+                    range.start.set_offset(offset + 1);
+                }
+                if &range.end.node == node && offset == range.EndOffset() {
+                    range.end.set_offset(offset + 1);
+                }
+            });
+        }
+    }
+
+    /// Used for steps 9.1-2. when splitting a text node.
+    /// https://dom.spec.whatwg.org/#concept-text-split
+    pub fn clamp_above(&self, node: &Node, offset: u32) {
+        self.map_offset_above(node, offset, |_| offset);
+    }
+
+    fn map_offset_above<F: FnMut(u32) -> u32>(&self, node: &Node, offset: u32, mut f: F) {
+        unsafe {
+            (*self.cell.get()).update(|entry| {
+                let range = entry.root().unwrap();
+                let start_offset = range.StartOffset();
+                if &range.start.node == node && start_offset > offset {
+                    range.start.set_offset(f(start_offset));
+                }
+                let end_offset = range.EndOffset();
+                if &range.end.node == node && end_offset > offset {
+                    range.end.set_offset(f(end_offset));
+                }
+            });
+        }
+    }
+
+    fn push(&self, ref_: WeakRef<Range>) {
+        unsafe {
+            (*self.cell.get()).push(ref_);
+        }
+    }
+
+    fn remove(&self, range: &Range) -> WeakRef<Range> {
+        unsafe {
+            let ranges = &mut *self.cell.get();
+            let position = ranges.iter().position(|ref_| {
+                ref_ == range
+            }).unwrap();
+            ranges.swap_remove(position)
+        }
+    }
+}
+
+#[allow(unsafe_code)]
+impl HeapSizeOf for WeakRangeVec {
+    fn heap_size_of_children(&self) -> usize {
+        unsafe { (*self.cell.get()).heap_size_of_children() }
+    }
+}
+
+#[allow(unsafe_code)]
+impl JSTraceable for WeakRangeVec {
+    fn trace(&self, _: *mut JSTracer) {
+        unsafe { (*self.cell.get()).retain_alive() }
+    }
+}