implement rcu using an amazing quantity of unsafe ops

5 files changed, 312 insertions, 74 deletions

diff --git a/src/rust-azure b/src/rust-azure
-Subproject d4575343780e925221e97d9ab21ebcdf37fe9c3
+Subproject 0e8a08bf861ae4d6271920e16bfd0022bd2aad7
diff --git a/src/servo/dom/base.rs b/src/servo/dom/base.rs
index 61af39f19cf..eed4ed3e5f2 100644
--- a/src/servo/dom/base.rs
+++ b/src/servo/dom/base.rs
@@ -1,4 +1,4 @@
-import dom::rcu::methods;
+import dom::rcu::{scope, writer_methods};
 import gfx::geom::{au, size};
 import layout::base::box;
 import util::tree;
@@ -6,10 +6,6 @@ import util::tree;
 enum node_data = {
     tree: tree::fields<node>,
     kind: node_kind,
-
-    // Points to the primary box.  Note that there may be multiple
-    // boxes per DOM node.
-    mut box: option<box>,
 };
 
 enum node_kind {
@@ -17,17 +13,13 @@ enum node_kind {
     nk_img(size<au>)
 }
 
-type node = rcu::handle<node_data>;
+// The rd_aux data is a (weak) pointer to the primary box.  Note that
+// there may be multiple boxes per DOM node.
+type node = rcu::handle<node_data, box>;
 
-impl of tree::tree for node {
-    fn tree_fields() -> tree::fields<node> {
-        ret self.get().tree;
+impl methods for scope<node_data, box> {
+    fn new_node(+k: node_kind) -> node {
+        self.handle(node_data({tree: tree::empty(),
+                               kind: k}))
     }
 }
-
-fn new_node(+k: node_kind) -> node {
-    rcu::handle(node_data({tree: tree::empty(),
-                           kind: k,
-                           mut box: none}))
-}
-
diff --git a/src/servo/dom/rcu.rs b/src/servo/dom/rcu.rs
index 2473156ca2f..05b5fcee0bf 100644
--- a/src/servo/dom/rcu.rs
+++ b/src/servo/dom/rcu.rs
@@ -1,15 +1,245 @@
-enum handle<T> {
-    _handle(@T)
+import ptr::extensions;
+
+export handle;
+export reader_methods;
+export writer_methods;
+export scope;
+
+type scope_data<T:send,A> = {
+    mut layout_active: bool,
+    mut free_list: [handle<T,A>],
+    mut first_dirty: handle<T,A>
+};
+
+resource scope_rsrc<T:send,A>(d: scope_data<T,A>) {
+    unsafe {
+        for d.free_list.each { |h| free_handle(h); }
+    }
+}
+
+type scope<T:send,A> = @scope_rsrc<T,A>;
+
+type handle_data<T:send,A> = {mut rd_ptr: *T,
+                              mut wr_ptr: *T,
+                              mut rd_aux: *A,
+                              mut next_dirty: handle<T,A>};
+enum handle<T:send,A> {
+    _handle(*handle_data<T,A>)
+}
+
+impl private_methods<T:send,A> for handle<T,A> {
+    fn rd_ptr() -> *T unsafe { (**self).rd_ptr }
+    fn wr_ptr() -> *T unsafe { (**self).wr_ptr }
+    fn rd_aux() -> *A unsafe { (**self).rd_aux }
+    fn next_dirty() -> handle<T,A> unsafe { (**self).next_dirty }
+
+    fn set_rd_ptr(t: *T) unsafe { (**self).rd_ptr = t; }
+    fn set_wr_ptr(t: *T) unsafe { (**self).wr_ptr = t; }
+    fn set_rd_aux(t: *A) unsafe { (**self).rd_aux = t; }
+    fn set_next_dirty(+h: handle<T,A>) unsafe { (**self).next_dirty = h; }
+
+    fn is_null() -> bool { (*self).is_null() }
+    fn is_not_null() -> bool { (*self).is_not_null() }
 }
 
-impl methods<T> for handle<T> {
-    fn get() -> @T { *self }
+impl reader_methods<T:send,A> for handle<T,A> {
+    fn rd<U>(f: fn(T) -> U) -> U unsafe {
+        f(*self.rd_ptr())
+    }
+
+    fn has_aux() -> bool unsafe {
+        self.rd_aux().is_not_null()
+    }
+
+    fn set_aux(p: @A) unsafe {
+        (**self).rd_aux = ptr::addr_of(*p);
+    }
 
-    fn with(f: fn(T)) {
-        f(**self)
+    fn aux<U>(f: fn(A) -> U) -> U unsafe {
+        // warning: do not use if has_aux() is false!
+        f(*self.rd_aux())
     }
 }
 
-fn handle<T:copy>(t: T) -> handle<T> {
-    _handle(@t)
+impl private_methods<T:send,A> for scope<T,A> {
+    fn clone(v: *T) -> *T unsafe {
+        let n: *mut T =
+            unsafe::reinterpret_cast(
+                libc::calloc(sys::size_of::<T>(), 1u));
+
+        // n.b.: this assignment will run the drop glue for <T,A>.
+        // *Hopefully* the fact that everything is initialized to NULL
+        // by calloc will make this ok.  We may have to make the take
+        // glue be tolerant.
+        *n = unsafe{*v};
+
+        ret unsafe::reinterpret_cast(n);
+    }
+}
+
+unsafe fn free<T:send>(t: *T) {
+    let _x <- *unsafe::reinterpret_cast::<*T,*mut T>(t);
+    libc::free(unsafe::reinterpret_cast(t));
+}
+
+unsafe fn free_handle<T:send,A>(h: handle<T,A>) {
+    free(h.rd_ptr());
+    if h.wr_ptr() != h.rd_ptr() { free(h.wr_ptr()); }
+}
+
+fn null_handle<T:send,A>() -> handle<T,A> {
+    _handle(ptr::null())
+}
+
+fn scope<T:send,A>() -> scope<T,A> {
+    @scope_rsrc({mut layout_active: false,
+                 mut free_list: [],
+                 mut first_dirty: null_handle()})
+}
+
+impl writer_methods<T:send,A> for scope<T,A> {
+    fn reader_forked() {
+        assert !self.layout_active;
+        assert self.first_dirty.is_null();
+        self.layout_active = true;
+    }
+
+    fn reader_joined() unsafe {
+        assert self.layout_active;
+
+        if self.first_dirty.is_not_null() {
+            let mut handle = self.first_dirty;
+            while (*handle).is_not_null() {
+                free(handle.rd_ptr());
+
+                handle.set_rd_ptr(handle.wr_ptr());
+                let next_handle = handle.next_dirty();
+                handle.set_next_dirty(null_handle());
+                handle = next_handle;
+            }
+            self.first_dirty = null_handle();
+        }
+
+        self.layout_active = false;
+    }
+
+    fn wr<U>(h: handle<T,A>, f: fn(T) -> U) -> U unsafe {
+        if self.layout_active {
+            if h.rd_ptr() == h.wr_ptr() {
+                h.set_wr_ptr(self.clone(h.rd_ptr()));
+                h.set_next_dirty(self.first_dirty);
+                self.first_dirty = h;
+            }
+        }
+        f(*h.wr_ptr())
+    }
+
+    fn handle(v: T) -> handle<T,A> unsafe {
+        let d: *handle_data<T,A> =
+            unsafe::reinterpret_cast(
+                libc::malloc(sys::size_of::<handle_data<T,A>>()));
+        (*d).rd_ptr = self.clone(ptr::addr_of(v));
+        (*d).wr_ptr = (*d).rd_ptr;
+        (*d).rd_aux = ptr::null();
+        (*d).next_dirty = null_handle();
+        let h = _handle(d);
+        self.free_list += [h];
+        ret h;
+    }
 }
+
+#[cfg(test)]
+mod test {
+
+    type animal = {name: str, species: species};
+    enum species {
+        chicken(~chicken),
+        bull(~bull)
+    }
+    type chicken = {mut eggs_per_day:uint};
+    type bull = {mut horns:uint};
+
+    type processed = {flag: bool};
+
+    type animal_scope = scope<animal, processed>;
+
+    #[test]
+    fn handles_get_freed() {
+        let s: animal_scope = scope();
+        s.handle({name:"henrietta", species:chicken(~{mut eggs_per_day:22u})});
+        s.handle({name:"ferdinand", species:bull(~{mut horns:3u})});
+    }
+
+    fn describe(a: animal) -> str {
+        let s = alt a.species {
+          chicken(c) { #fmt["chicken who lays %u eggs per day",
+                            c.eggs_per_day] }
+          bull(c) { #fmt["bull with %u horns", c.horns] }
+        };
+        #fmt["%s, the %s", a.name, s]
+    }
+
+    fn mutate(a: animal) {
+        alt a.species {
+          chicken(c) { c.eggs_per_day += 1u; }
+          bull(c) { c.horns += 1u; }
+        }
+    }
+
+    fn read_characteristic(a: animal) -> uint {
+        alt a.species {
+          chicken(c) { c.eggs_per_day }
+          bull(c) { c.horns }
+        }
+    }
+
+    #[test]
+    fn interspersed_execution() {
+        let s: animal_scope = scope();
+        let henrietta =
+            s.handle({name:"henrietta",
+                      species:chicken(~{mut eggs_per_day:0u})});
+        let ferdinand =
+            s.handle({name:"ferdinand",
+                      species:bull(~{mut horns:0u})});
+
+        let iter1 = 3u;
+        let iter2 = 22u;
+        let read_port = comm::port();
+        let read_chan = comm::chan(read_port);
+
+        // fire up a reader task
+        uint::range(0u, iter1) { |i|
+            s.reader_forked();
+            let wait_chan = task::spawn_listener {|wait_port|
+                uint::range(0u, iter2) { |_i|
+                    comm::send(read_chan, henrietta.rd(describe));
+                    comm::send(read_chan, ferdinand.rd(describe));
+                    comm::recv(wait_port);
+                }
+            };
+
+            let hrc = henrietta.rd(read_characteristic);
+            assert hrc == (i * iter2);
+
+            let frc = ferdinand.rd(read_characteristic);
+            assert frc == i * iter2;
+
+            let exp1 = henrietta.rd(describe);
+            let exp2 = ferdinand.rd(describe);
+
+            uint::range(0u, iter2) { |_i|
+                assert exp1 == comm::recv(read_port);
+                s.wr(henrietta, mutate);
+                assert exp2 == comm::recv(read_port);
+                s.wr(ferdinand, mutate);
+                comm::send(wait_chan, ());
+            }
+            s.reader_joined();
+        }
+
+        assert henrietta.rd(read_characteristic) == iter1 * iter2;
+        assert ferdinand.rd(read_characteristic) == iter1 * iter2;
+    }
+
+}
\ No newline at end of file
diff --git a/src/servo/layout/base.rs b/src/servo/layout/base.rs
index 1c226a964d9..ecd4c33305a 100644
--- a/src/servo/layout/base.rs
+++ b/src/servo/layout/base.rs
@@ -1,35 +1,41 @@
-import dom::base::{nk_img, node_data, node_kind, node, new_node};
+import dom::base::{nk_div, nk_img, node_data, node_kind, node};
 import dom::rcu;
-import dom::rcu::methods;
+import dom::rcu::reader_methods;
 import gfx::geom;
 import gfx::geom::{size, rect, point, au};
 import util::{tree};
 
-enum box = @{
-    tree: tree::fields<box>,
+enum box = {
+    tree: tree::fields<@box>,
     node: node,
     mut bounds: geom::rect<au>
 };
 
-impl of tree::tree for box {
-    fn tree_fields() -> tree::fields<box> {
-        ret self.tree;
+impl of tree::tree for node {
+    fn with_tree_fields<R>(f: fn(tree::fields<node>) -> R) -> R {
+        f(self.rd { |f| f.tree })
     }
 }
 
-fn new_box(n: node) -> box {
-    box(@{tree: tree::empty(),
+impl of tree::tree for @box {
+    fn with_tree_fields<R>(f: fn(tree::fields<@box>) -> R) -> R {
+        f(self.tree)
+    }
+}
+
+fn new_box(n: node) -> @box {
+    @box({tree: tree::empty(),
           node: n,
           mut bounds: geom::zero_rect_au()})
 }
 
-fn linked_box(n: node) -> box {
+fn linked_box(n: node) -> @box {
     let b = new_box(n);
-    n.box = some(b);
+    n.set_aux(b);
     ret b;
 }
 
-fn reflow_block(root: box, available_width: au) {
+fn reflow_block(root: @box, available_width: au) {
     // Root here is the root of the reflow, not necessarily the doc as
     // a whole.
     //
@@ -38,7 +44,8 @@ fn reflow_block(root: box, available_width: au) {
     // - generates root.bounds.origin for each child
     // - and recursively computes the bounds for each child
 
-    alt root.node.get().kind {
+    let k = root.node.rd() { |r| r.kind };
+    alt k {
       nk_img(size) {
         root.bounds.size = size;
         ret;
@@ -62,6 +69,8 @@ fn reflow_block(root: box, available_width: au) {
 
 #[cfg(test)]
 mod test {
+    import dom::base::{nk_img, node_data, node_kind, node, methods};
+    import dom::rcu::scope;
 
     /*
     use sdl;
@@ -79,7 +88,7 @@ mod test {
     }
     */
 
-    fn flat_bounds(root: box) -> [geom::rect<au>] {
+    fn flat_bounds(root: @box) -> [geom::rect<au>] {
         let mut r = [];
         for tree::each_child(root) {|c|
             r += flat_bounds(c);
@@ -89,10 +98,12 @@ mod test {
 
     #[test]
     fn do_layout() {
-        let n0 = new_node(nk_img(size(au(10),au(10))));
-        let n1 = new_node(nk_img(size(au(10),au(15))));
-        let n2 = new_node(nk_img(size(au(10),au(20))));
-        let n3 = new_node(nk_div);
+        let s = scope();
+
+        let n0 = s.new_node(nk_img(size(au(10),au(10))));
+        let n1 = s.new_node(nk_img(size(au(10),au(15))));
+        let n2 = s.new_node(nk_img(size(au(10),au(20))));
+        let n3 = s.new_node(nk_div);
 
         tree::add_child(n3, n0);
         tree::add_child(n3, n1);
diff --git a/src/servo/util/tree.rs b/src/servo/util/tree.rs
index 2dba99ed699..1fa7448dc3c 100644
--- a/src/servo/util/tree.rs
+++ b/src/servo/util/tree.rs
@@ -1,4 +1,4 @@
-type fields<T> = @{
+type fields<T> = {
     mut parent: option<T>,
     mut first_child: option<T>,
     mut last_child: option<T>,
@@ -7,59 +7,62 @@ type fields<T> = @{
 };
 
 iface tree {
-    fn tree_fields() -> fields<self>;
+    fn with_tree_fields<R>(f: fn(fields<self>) -> R) -> R;
 }
 
 fn each_child<T:copy tree>(
     node: T, f: fn(T) -> bool) {
 
-    let mut p = node.tree_fields().first_child;
+    let mut p = node.with_tree_fields { |f| f.first_child };
     loop {
         alt p {
           none { ret; }
           some(c) {
             if !f(c) { ret; }
-            p = c.tree_fields().next_sibling;
+            p = c.with_tree_fields { |f| f.next_sibling };
           }
         }
     }
 }
 
 fn empty<T>() -> fields<T> {
-    @{mut parent: none,
-      mut first_child: none,
-      mut last_child: none,
-      mut prev_sibling: none,
-      mut next_sibling: none}
+    {mut parent: none,
+     mut first_child: none,
+     mut last_child: none,
+     mut prev_sibling: none,
+     mut next_sibling: none}
 }
 
 fn add_child<T:copy tree>(
     node: T, child: T) {
 
-    let child_tf = child.tree_fields();
-    alt child_tf.parent {
-      some(_) { fail "Already has a parent"; }
-      none { child_tf.parent = some(node); }
-    }
+    child.with_tree_fields { |child_tf|
+        alt child_tf.parent {
+          some(_) { fail "Already has a parent"; }
+          none { child_tf.parent = some(node); }
+        }
 
-    assert child_tf.prev_sibling == none;
-    assert child_tf.next_sibling == none;
-
-    let node_tf = node.tree_fields();
-    alt node_tf.last_child {
-      none {
-        node_tf.first_child = some(child);
-      }
-
-      some(lc) {
-        let lc_tf = lc.tree_fields();
-        assert lc_tf.next_sibling == none;
-        lc_tf.next_sibling = some(child);
-        child_tf.prev_sibling = some(lc);
-      }
+        assert child_tf.prev_sibling == none;
+        assert child_tf.next_sibling == none;
+
+        node.with_tree_fields { |node_tf|
+            alt node_tf.last_child {
+              none {
+                node_tf.first_child = some(child);
+              }
+
+              some(lc) {
+                lc.with_tree_fields { |lc_tf|
+                    assert lc_tf.next_sibling == none;
+                    lc_tf.next_sibling = some(child);
+                }
+                child_tf.prev_sibling = some(lc);
+              }
+            }
+
+            node_tf.last_child = some(child);
+        }
     }
-
-    node_tf.last_child = some(child);
 }
 
 #[cfg(test)]
@@ -70,7 +73,9 @@ mod test {
     };
 
     impl of tree for dummy {
-        fn tree_fields() -> fields<dummy> { self.fields }
+        fn with_tree_fields<R>(f: fn(fields<dummy>) -> R) -> R {
+            f(self.fields)
+        }
     }
 
     fn new_dummy(v: uint) -> dummy {