Reorganize tree ref / node traits

rustc is no longer happy with

    impl<NR:TreeNodeRef<N>,N:TreeNode<NR>> TreeUtils for NR

13 files changed, 287 insertions, 198 deletions

diff --git a/src/components/main/css/matching.rs b/src/components/main/css/matching.rs
index b1712d286eb..fedc0c856fd 100644
--- a/src/components/main/css/matching.rs
+++ b/src/components/main/css/matching.rs
@@ -11,7 +11,7 @@ use layout::incremental;
 use script::dom::node::{AbstractNode, LayoutView};
 use newcss::complete::CompleteSelectResults;
 use newcss::select::{SelectCtx, SelectResults};
-use servo_util::tree::TreeUtils;
+use servo_util::tree::TreeNodeRef;
 
 pub trait MatchMethods {
     fn restyle_subtree(&self, select_ctx: &SelectCtx);
diff --git a/src/components/main/layout/aux.rs b/src/components/main/layout/aux.rs
index d63df74c53d..459106e3b39 100644
--- a/src/components/main/layout/aux.rs
+++ b/src/components/main/layout/aux.rs
@@ -9,7 +9,7 @@ use layout::incremental::RestyleDamage;
 
 use newcss::complete::CompleteSelectResults;
 use script::dom::node::{AbstractNode, LayoutView};
-use servo_util::tree::TreeUtils;
+use servo_util::tree::TreeNodeRef;
 
 /// Data that layout associates with a node.
 pub struct LayoutData {
diff --git a/src/components/main/layout/block.rs b/src/components/main/layout/block.rs
index e78bc87f158..ef191d4697a 100644
--- a/src/components/main/layout/block.rs
+++ b/src/components/main/layout/block.rs
@@ -18,7 +18,7 @@ use geom::rect::Rect;
 use gfx::display_list::DisplayList;
 use gfx::geometry::Au;
 use gfx::geometry;
-use servo_util::tree::{TreeNodeRef, TreeUtils};
+use servo_util::tree::TreeNodeRef;
 
 pub struct BlockFlowData {
     /// Data common to all flows.
diff --git a/src/components/main/layout/box_builder.rs b/src/components/main/layout/box_builder.rs
index 5ea78c8a0fe..b49c368833d 100644
--- a/src/components/main/layout/box_builder.rs
+++ b/src/components/main/layout/box_builder.rs
@@ -30,7 +30,7 @@ use script::dom::element::*;
 use script::dom::node::{AbstractNode, CommentNodeTypeId, DoctypeNodeTypeId};
 use script::dom::node::{ElementNodeTypeId, LayoutView, TextNodeTypeId};
 use servo_util::range::Range;
-use servo_util::tree::{TreeNodeRef, TreeNode, TreeUtils};
+use servo_util::tree::{TreeNodeRef, TreeNode};
 
 pub struct LayoutTreeBuilder {
     root_flow: Option<FlowContext>,
diff --git a/src/components/main/layout/float.rs b/src/components/main/layout/float.rs
index 2a2758d4aab..64d0c1c5cd3 100644
--- a/src/components/main/layout/float.rs
+++ b/src/components/main/layout/float.rs
@@ -15,7 +15,7 @@ use geom::rect::Rect;
 use gfx::display_list::DisplayList;
 use gfx::geometry::Au;
 use gfx::geometry;
-use servo_util::tree::{TreeNodeRef, TreeUtils};
+use servo_util::tree::TreeNodeRef;
 
 pub struct FloatFlowData {
     /// Data common to all flows.
diff --git a/src/components/main/layout/flow.rs b/src/components/main/layout/flow.rs
index 6dc7e9409dc..1da6655ef70 100644
--- a/src/components/main/layout/flow.rs
+++ b/src/components/main/layout/flow.rs
@@ -43,7 +43,7 @@ use geom::rect::Rect;
 use gfx::display_list::DisplayList;
 use gfx::geometry::Au;
 use script::dom::node::{AbstractNode, LayoutView};
-use servo_util::tree::{TreeNode, TreeNodeRef, TreeUtils};
+use servo_util::tree::{TreeNode, TreeNodeRef};
 
 /// The type of the formatting context and data specific to each context, such as line box
 /// structures or float lists.
@@ -164,8 +164,50 @@ impl TreeNodeRef<FlowData> for FlowContext {
             TableFlow(info) => callback(info),
         }
     }
+
+    fn parent_node(node: &FlowData) -> Option<FlowContext> {
+        node.parent
+    }
+
+    fn first_child(node: &FlowData) -> Option<FlowContext> {
+        node.first_child
+    }
+
+    fn last_child(node: &FlowData) -> Option<FlowContext> {
+        node.last_child
+    }
+
+    fn prev_sibling(node: &FlowData) -> Option<FlowContext> {
+        node.prev_sibling
+    }
+
+    fn next_sibling(node: &FlowData) -> Option<FlowContext> {
+        node.next_sibling
+    }
+
+    fn set_parent_node(node: &mut FlowData, new_parent_node: Option<FlowContext>) {
+        node.parent = new_parent_node
+    }
+
+    fn set_first_child(node: &mut FlowData, new_first_child: Option<FlowContext>) {
+        node.first_child = new_first_child
+    }
+
+    fn set_last_child(node: &mut FlowData, new_last_child: Option<FlowContext>) {
+        node.last_child = new_last_child
+    }
+
+    fn set_prev_sibling(node: &mut FlowData, new_prev_sibling: Option<FlowContext>) {
+        node.prev_sibling = new_prev_sibling
+    }
+
+    fn set_next_sibling(node: &mut FlowData, new_next_sibling: Option<FlowContext>) {
+        node.next_sibling = new_next_sibling
+    }
 }
 
+impl TreeNode<FlowContext> for FlowData { }
+
 /// Data common to all flows.
 ///
 /// FIXME: We need a naming convention for pseudo-inheritance like this. How about
@@ -196,48 +238,6 @@ pub struct FlowData {
     is_inorder: bool,
 }
 
-impl TreeNode<FlowContext> for FlowData {
-    fn parent_node(&self) -> Option<FlowContext> {
-        self.parent
-    }
-
-    fn first_child(&self) -> Option<FlowContext> {
-        self.first_child
-    }
-
-    fn last_child(&self) -> Option<FlowContext> {
-        self.last_child
-    }
-
-    fn prev_sibling(&self) -> Option<FlowContext> {
-        self.prev_sibling
-    }
-
-    fn next_sibling(&self) -> Option<FlowContext> {
-        self.next_sibling
-    }
-
-    fn set_parent_node(&mut self, new_parent_node: Option<FlowContext>) {
-        self.parent = new_parent_node
-    }
-
-    fn set_first_child(&mut self, new_first_child: Option<FlowContext>) {
-        self.first_child = new_first_child
-    }
-
-    fn set_last_child(&mut self, new_last_child: Option<FlowContext>) {
-        self.last_child = new_last_child
-    }
-
-    fn set_prev_sibling(&mut self, new_prev_sibling: Option<FlowContext>) {
-        self.prev_sibling = new_prev_sibling
-    }
-
-    fn set_next_sibling(&mut self, new_next_sibling: Option<FlowContext>) {
-        self.next_sibling = new_next_sibling
-    }
-}
-
 pub struct BoxIterator {
     priv boxes: ~[RenderBox],
     priv index: uint,
diff --git a/src/components/main/layout/inline.rs b/src/components/main/layout/inline.rs
index 3a4f8122dfe..d6a6c5dc2a2 100644
--- a/src/components/main/layout/inline.rs
+++ b/src/components/main/layout/inline.rs
@@ -21,7 +21,7 @@ use newcss::values::{CSSTextAlignLeft, CSSTextAlignCenter, CSSTextAlignRight, CS
 use newcss::units::{Em, Px, Pt};
 use newcss::values::{CSSLineHeightNormal, CSSLineHeightNumber, CSSLineHeightLength, CSSLineHeightPercentage};
 use servo_util::range::Range;
-use servo_util::tree::{TreeNodeRef, TreeUtils};
+use servo_util::tree::TreeNodeRef;
 use extra::container::Deque;
 use extra::ringbuf::RingBuf;
 
diff --git a/src/components/main/layout/layout_task.rs b/src/components/main/layout/layout_task.rs
index 73f9e5c9556..c107d6a3e3f 100644
--- a/src/components/main/layout/layout_task.rs
+++ b/src/components/main/layout/layout_task.rs
@@ -41,7 +41,7 @@ use script::script_task::{ReflowCompleteMsg, ScriptChan, SendEventMsg};
 use servo_msg::constellation_msg::{ConstellationChan, PipelineId};
 use servo_net::image_cache_task::{ImageCacheTask, ImageResponseMsg};
 use servo_net::local_image_cache::LocalImageCache;
-use servo_util::tree::{TreeNodeRef, TreeUtils};
+use servo_util::tree::TreeNodeRef;
 use servo_util::time::{ProfilerChan, profile};
 use servo_util::time;
 use extra::url::Url;
diff --git a/src/components/script/dom/document.rs b/src/components/script/dom/document.rs
index 043eec3646a..5ba1b10a90d 100644
--- a/src/components/script/dom/document.rs
+++ b/src/components/script/dom/document.rs
@@ -18,7 +18,7 @@ use dom::htmltitleelement::HTMLTitleElement;
 
 use js::jsapi::{JS_AddObjectRoot, JS_RemoveObjectRoot, JSObject, JSContext, JSVal};
 use js::glue::RUST_OBJECT_TO_JSVAL;
-use servo_util::tree::{TreeNodeRef, TreeUtils};
+use servo_util::tree::TreeNodeRef;
 
 use std::cast;
 use std::ptr;
diff --git a/src/components/script/dom/htmldocument.rs b/src/components/script/dom/htmldocument.rs
index 52c15fc36cf..b839f0c4960 100644
--- a/src/components/script/dom/htmldocument.rs
+++ b/src/components/script/dom/htmldocument.rs
@@ -13,7 +13,7 @@ use dom::window::Window;
 
 use js::jsapi::{JSObject, JSContext};
 
-use servo_util::tree::TreeUtils;
+use servo_util::tree::TreeNodeRef;
 
 use std::libc;
 use std::ptr;
diff --git a/src/components/script/dom/node.rs b/src/components/script/dom/node.rs
index bee3dac63d7..1f53bb2ac09 100644
--- a/src/components/script/dom/node.rs
+++ b/src/components/script/dom/node.rs
@@ -24,7 +24,7 @@ use std::uint;
 use js::jsapi::{JSObject, JSContext};
 use js::rust::Compartment;
 use netsurfcss::util::VoidPtrLike;
-use servo_util::tree::{TreeNode, TreeNodeRef, TreeUtils};
+use servo_util::tree::{TreeNode, TreeNodeRef};
 
 //
 // The basic Node structure
@@ -177,41 +177,39 @@ impl<View> Clone for AbstractNode<View> {
     }
 }
 
-impl<View> TreeNode<AbstractNode<View>> for Node<View> {
-    fn parent_node(&self) -> Option<AbstractNode<View>> {
-        self.parent_node
+impl<View> TreeNodeRef<Node<View>> for AbstractNode<View> {
+    fn parent_node(node: &Node<View>) -> Option<AbstractNode<View>> {
+        node.parent_node
     }
-    fn first_child(&self) -> Option<AbstractNode<View>> {
-        self.first_child
+    fn first_child(node: &Node<View>) -> Option<AbstractNode<View>> {
+        node.first_child
     }
-    fn last_child(&self) -> Option<AbstractNode<View>> {
-        self.last_child
+    fn last_child(node: &Node<View>) -> Option<AbstractNode<View>> {
+        node.last_child
     }
-    fn prev_sibling(&self) -> Option<AbstractNode<View>> {
-        self.prev_sibling
+    fn prev_sibling(node: &Node<View>) -> Option<AbstractNode<View>> {
+        node.prev_sibling
     }
-    fn next_sibling(&self) -> Option<AbstractNode<View>> {
-        self.next_sibling
+    fn next_sibling(node: &Node<View>) -> Option<AbstractNode<View>> {
+        node.next_sibling
     }
 
-    fn set_parent_node(&mut self, new_parent_node: Option<AbstractNode<View>>) {
-        self.parent_node = new_parent_node
+    fn set_parent_node(node: &mut Node<View>, new_parent_node: Option<AbstractNode<View>>) {
+        node.parent_node = new_parent_node
     }
-    fn set_first_child(&mut self, new_first_child: Option<AbstractNode<View>>) {
-        self.first_child = new_first_child
+    fn set_first_child(node: &mut Node<View>, new_first_child: Option<AbstractNode<View>>) {
+        node.first_child = new_first_child
     }
-    fn set_last_child(&mut self, new_last_child: Option<AbstractNode<View>>) {
-        self.last_child = new_last_child
+    fn set_last_child(node: &mut Node<View>, new_last_child: Option<AbstractNode<View>>) {
+        node.last_child = new_last_child
     }
-    fn set_prev_sibling(&mut self, new_prev_sibling: Option<AbstractNode<View>>) {
-        self.prev_sibling = new_prev_sibling
+    fn set_prev_sibling(node: &mut Node<View>, new_prev_sibling: Option<AbstractNode<View>>) {
+        node.prev_sibling = new_prev_sibling
     }
-    fn set_next_sibling(&mut self, new_next_sibling: Option<AbstractNode<View>>) {
-        self.next_sibling = new_next_sibling
+    fn set_next_sibling(node: &mut Node<View>, new_next_sibling: Option<AbstractNode<View>>) {
+        node.next_sibling = new_next_sibling
     }
-}
 
-impl<View> TreeNodeRef<Node<View>> for AbstractNode<View> {
     // FIXME: The duplication between `with_base` and `with_mut_base` is ugly.
     fn with_base<R>(&self, callback: &fn(&Node<View>) -> R) -> R {
         self.transmute(callback)
@@ -222,6 +220,8 @@ impl<View> TreeNodeRef<Node<View>> for AbstractNode<View> {
     }
 }
 
+impl<View> TreeNode<AbstractNode<View>> for Node<View> { }
+
 impl<'self, View> AbstractNode<View> {
     // Unsafe accessors
 
diff --git a/src/components/script/html/hubbub_html_parser.rs b/src/components/script/html/hubbub_html_parser.rs
index 2409d4c0a6a..005f6d6dbbd 100644
--- a/src/components/script/html/hubbub_html_parser.rs
+++ b/src/components/script/html/hubbub_html_parser.rs
@@ -63,7 +63,7 @@ use servo_msg::constellation_msg::SubpageId;
 use servo_net::image_cache_task::ImageCacheTask;
 use servo_net::image_cache_task;
 use servo_net::resource_task::{Done, Load, Payload, ResourceTask};
-use servo_util::tree::TreeUtils;
+use servo_util::tree::TreeNodeRef;
 use servo_util::url::make_url;
 use extra::url::Url;
 use extra::future::{Future, from_port};
diff --git a/src/components/util/tree.rs b/src/components/util/tree.rs
index eebf91fa10f..3b4aba07cc5 100644
--- a/src/components/util/tree.rs
+++ b/src/components/util/tree.rs
@@ -4,204 +4,293 @@
 
 //! Helper functions for garbage collected doubly-linked trees.
 
-/// The basic trait. This function is meant to encapsulate a clonable reference to a tree node.
-pub trait TreeNodeRef<N> : Clone {
+// Macros to make add_child etc. less painful to write.
+// Code outside this module should instead implement TreeNode
+// and use its default methods.
+priv macro_rules! get(
+    ($node:expr, $fun:ident) => (
+        TreeNodeRef::$fun::<Node,Self>($node)
+    )
+)
+
+priv macro_rules! set(
+    ($node:expr, $fun:ident, $val:expr) => (
+        TreeNodeRef::$fun::<Node,Self>($node, $val)
+    )
+)
+
+pub struct ChildIterator<Ref> {
+    priv current: Option<Ref>,
+}
+
+impl<Node, Ref: TreeNodeRef<Node>> Iterator<Ref> for ChildIterator<Ref> {
+    fn next(&mut self) -> Option<Ref> {
+        if self.current.is_none() {
+            return None;
+        }
+
+        // FIXME: Do we need two clones here?
+        let x = self.current.get_ref().clone();
+        self.current = x.with_base(|n| TreeNodeRef::next_sibling::<Node, Ref>(n));
+        Some(x.clone())
+    }
+}
+
+// FIXME: Do this without precomputing a vector of refs.
+// Easy for preorder; harder for postorder.
+pub struct TreeIterator<Ref> {
+    priv nodes: ~[Ref],
+    priv index: uint,
+}
+
+impl<Ref> TreeIterator<Ref> {
+    priv fn new(nodes: ~[Ref]) -> TreeIterator<Ref> {
+        TreeIterator {
+            nodes: nodes,
+            index: 0,
+        }
+    }
+}
+
+impl<Ref: Clone> Iterator<Ref> for TreeIterator<Ref> {
+    fn next(&mut self) -> Option<Ref> {
+        if self.index >= self.nodes.len() {
+            None
+        } else {
+            let v = self.nodes[self.index].clone();
+            self.index += 1;
+            Some(v)
+        }
+    }
+}
+
+/// A type implementing TreeNodeRef<Node> is a clonable reference to an underlying
+/// node type Node.
+///
+/// We have to define both ref and node operations in the same trait, which makes
+/// the latter more annoying to call (as static methods).  But we provide non-static
+/// proxies in trait TreeNode below.
+pub trait TreeNodeRef<Node>: Clone {
+
+    // Fundamental operations on refs.
+
     /// Borrows this node as immutable.
-    fn with_base<R>(&self, callback: &fn(&N) -> R) -> R;
+    fn with_base<R>(&self, callback: &fn(&Node) -> R) -> R;
 
     /// Borrows this node as mutable.
-    fn with_mut_base<R>(&self, callback: &fn(&mut N) -> R) -> R;
-}
+    fn with_mut_base<R>(&self, callback: &fn(&mut Node) -> R) -> R;
+
+
+    // Fundamental operations on nodes.
 
-/// The contents of a tree node.
-pub trait TreeNode<NR> {
     /// Returns the parent of this node.
-    fn parent_node(&self) -> Option<NR>;
+    fn parent_node(node: &Node) -> Option<Self>;
 
     /// Returns the first child of this node.
-    fn first_child(&self) -> Option<NR>;
+    fn first_child(node: &Node) -> Option<Self>;
 
     /// Returns the last child of this node.
-    fn last_child(&self) -> Option<NR>;
+    fn last_child(node: &Node) -> Option<Self>;
 
     /// Returns the previous sibling of this node.
-    fn prev_sibling(&self) -> Option<NR>;
+    fn prev_sibling(node: &Node) -> Option<Self>;
 
     /// Returns the next sibling of this node.
-    fn next_sibling(&self) -> Option<NR>;
+    fn next_sibling(node: &Node) -> Option<Self>;
 
     /// Sets the parent of this node.
-    fn set_parent_node(&mut self, new_parent: Option<NR>);
+    fn set_parent_node(node: &mut Node, new_parent: Option<Self>);
 
     /// Sets the first child of this node.
-    fn set_first_child(&mut self, new_first_child: Option<NR>);
+    fn set_first_child(node: &mut Node, new_first_child: Option<Self>);
 
     /// Sets the last child of this node.
-    fn set_last_child(&mut self, new_last_child: Option<NR>);
+    fn set_last_child(node: &mut Node, new_last_child: Option<Self>);
 
     /// Sets the previous sibling of this node.
-    fn set_prev_sibling(&mut self, new_prev_sibling: Option<NR>);
+    fn set_prev_sibling(node: &mut Node, new_prev_sibling: Option<Self>);
 
     /// Sets the next sibling of this node.
-    fn set_next_sibling(&mut self, new_next_sibling: Option<NR>);
-}
-
-/// A set of helper functions useful for operating on trees.
-pub trait TreeUtils {
-    /// Returns true if this node is disconnected from the tree or has no children.
-    fn is_leaf(&self) -> bool;
-
-    /// Adds a new child to the end of this node's list of children.
-    ///
-    /// Fails unless `new_child` is disconnected from the tree.
-    fn add_child(&self, new_child: Self);
-
-    /// Removes the given child from this node's list of children.
-    ///
-    /// Fails unless `child` is a child of this node. (FIXME: This is not yet checked.)
-    fn remove_child(&self, child: Self);
-
-    /// Iterates over all children of this node.
-    fn each_child(&self, callback: &fn(Self) -> bool) -> bool;
-
-    /// Iterates over this node and all its descendants, in preorder.
-    fn traverse_preorder(&self, callback: &fn(Self) -> bool) -> bool;
+    fn set_next_sibling(node: &mut Node, new_next_sibling: Option<Self>);
 
-    /// Iterates over this node and all its descendants, in postorder.
-    fn traverse_postorder(&self, callback: &fn(Self) -> bool) -> bool;
 
-    /// Like traverse_preorder but calls 'prune' first on each node.  If it returns true then we
-    /// skip the whole subtree but continue iterating.
-    ///
-    /// 'prune' is a separate function a) for compatibility with the 'for' protocol,
-    /// b) so that the postorder version can still prune before traversing.
-    fn traverse_preorder_prune(&self, prune: &fn(&Self) -> bool, callback: &fn(Self) -> bool) -> bool;
+    // The tree utilities, operating on refs mostly.
 
-    /// Like traverse_postorder but calls 'prune' first on each node.  If it returns true then we
-    /// skip the whole subtree but continue iterating.
-    ///
-    /// NB: 'prune' is called *before* traversing children, even though this is a
-    /// postorder traversal.
-    fn traverse_postorder_prune(&self, prune: &fn(&Self) -> bool, callback: &fn(Self) -> bool) -> bool;
-}
-
-impl<NR:TreeNodeRef<N>,N:TreeNode<NR>> TreeUtils for NR {
+    /// Returns true if this node is disconnected from the tree or has no children.
     fn is_leaf(&self) -> bool {
         do self.with_base |this_node| {
-            this_node.first_child().is_none()
+            (get!(this_node, first_child)).is_none()
         }
     }
 
-    fn add_child(&self, new_child: NR) {
+    /// Adds a new child to the end of this node's list of children.
+    ///
+    /// Fails unless `new_child` is disconnected from the tree.
+    fn add_child(&self, new_child: Self) {
         do self.with_mut_base |this_node| {
             do new_child.with_mut_base |new_child_node| {
-                assert!(new_child_node.parent_node().is_none());
-                assert!(new_child_node.prev_sibling().is_none());
-                assert!(new_child_node.next_sibling().is_none());
+                assert!((get!(new_child_node, parent_node)).is_none());
+                assert!((get!(new_child_node, prev_sibling)).is_none());
+                assert!((get!(new_child_node, next_sibling)).is_none());
 
-                match this_node.last_child() {
-                    None => this_node.set_first_child(Some(new_child.clone())),
+                match get!(this_node, last_child) {
+                    None => set!(this_node, set_first_child, Some(new_child.clone())),
                     Some(last_child) => {
                         do last_child.with_mut_base |last_child_node| {
-                            assert!(last_child_node.next_sibling().is_none());
-                            last_child_node.set_next_sibling(Some(new_child.clone()));
-                            new_child_node.set_prev_sibling(Some(last_child.clone()));
+                            assert!((get!(last_child_node, next_sibling)).is_none());
+                            set!(last_child_node, set_next_sibling, Some(new_child.clone()));
+                            set!(new_child_node, set_prev_sibling, Some(last_child.clone()));
                         }
                     }
                 }
 
-                this_node.set_last_child(Some(new_child.clone()));
-                new_child_node.set_parent_node(Some((*self).clone()));
+                set!(this_node, set_last_child, Some(new_child.clone()));
+                set!(new_child_node, set_parent_node, Some((*self).clone()));
             }
         }
     }
 
-    fn remove_child(&self, child: NR) {
+    /// Removes the given child from this node's list of children.
+    ///
+    /// Fails unless `child` is a child of this node. (FIXME: This is not yet checked.)
+    fn remove_child(&self, child: Self) {
         do self.with_mut_base |this_node| {
             do child.with_mut_base |child_node| {
-                assert!(child_node.parent_node().is_some());
+                assert!((get!(child_node, parent_node)).is_some());
 
-                match child_node.prev_sibling() {
-                    None => this_node.set_first_child(child_node.next_sibling()),
+                match get!(child_node, prev_sibling) {
+                    None => set!(this_node, set_first_child, get!(child_node, next_sibling)),
                     Some(prev_sibling) => {
                         do prev_sibling.with_mut_base |prev_sibling_node| {
-                            prev_sibling_node.set_next_sibling(child_node.next_sibling());
+                            set!(prev_sibling_node, set_next_sibling, get!(child_node, next_sibling));
                         }
                     }
                 }
 
-                match child_node.next_sibling() {
-                    None => this_node.set_last_child(child_node.prev_sibling()),
+                match get!(child_node, next_sibling) {
+                    None => set!(this_node, set_last_child, get!(child_node, prev_sibling)),
                     Some(next_sibling) => {
                         do next_sibling.with_mut_base |next_sibling_node| {
-                            next_sibling_node.set_prev_sibling(child_node.prev_sibling());
+                            set!(next_sibling_node, set_prev_sibling, get!(child_node, prev_sibling));
                         }
                     }
                 }
 
-                child_node.set_prev_sibling(None);
-                child_node.set_next_sibling(None);
-                child_node.set_parent_node(None);
+                set!(child_node, set_prev_sibling, None);
+                set!(child_node, set_next_sibling, None);
+                set!(child_node, set_parent_node,  None);
             }
         }
     }
 
-    fn each_child(&self, callback: &fn(NR) -> bool) -> bool {
-        let mut maybe_current = self.with_base(|n| n.first_child());
-        while !maybe_current.is_none() {
-            let current = maybe_current.get_ref().clone();
-            if !callback(current.clone()) {
-                break;
-            }
-
-            maybe_current = current.with_base(|n| n.next_sibling());
+    /// Iterates over all children of this node.
+    fn children(&self) -> ChildIterator<Self> {
+        ChildIterator {
+            current: self.with_base(|n| get!(n, first_child)),
         }
+    }
 
-        true
+    /// Iterates over this node and all its descendants, in preorder.
+    fn traverse_preorder(&self) -> TreeIterator<Self> {
+        self.traverse_preorder_prune(|_| false)
     }
 
-    fn traverse_preorder_prune(&self, prune: &fn(&NR) -> bool, callback: &fn(NR) -> bool) -> bool {
-        // prune shouldn't mutate, so don't clone
-        if prune(self) {
-            return true;
-        }
+    /// Iterates over this node and all its descendants, in postorder.
+    fn traverse_postorder(&self) -> TreeIterator<Self> {
+        self.traverse_postorder_prune(|_| false)
+    }
 
-        if !callback((*self).clone()) {
-            return false;
-        }
+    /// Like traverse_preorder but calls 'prune' first on each node.  If it returns true then we
+    /// skip the whole subtree but continue iterating.
+    fn traverse_preorder_prune(&self, prune: &fn(&Self) -> bool) -> TreeIterator<Self> {
+        let mut nodes = ~[];
+        gather(self, &mut nodes, false, prune);
+        TreeIterator::new(nodes)
+    }
 
-        for self.each_child |kid| {
-            // FIXME: Work around rust#2202. We should be able to pass the callback directly.
-            if !kid.traverse_preorder_prune(|a| prune(a), |a| callback(a)) {
-                return false;
-            }
-        }
+    /// Like traverse_postorder but calls 'prune' first on each node.  If it returns true then we
+    /// skip the whole subtree but continue iterating.
+    ///
+    /// NB: 'prune' is called *before* traversing children, even though this is a
+    /// postorder traversal.
+    fn traverse_postorder_prune(&self, prune: &fn(&Self) -> bool) -> TreeIterator<Self> {
+        let mut nodes = ~[];
+        gather(self, &mut nodes, true, prune);
+        TreeIterator::new(nodes)
+    }
+}
 
-        true
+priv fn gather<Node, Ref: TreeNodeRef<Node>>(cur: &Ref, refs: &mut ~[Ref],
+                                             postorder: bool, prune: &fn(&Ref) -> bool) {
+    // prune shouldn't mutate, so don't clone
+    if prune(cur) {
+        return;
     }
 
-    fn traverse_postorder_prune(&self, prune: &fn(&NR) -> bool, callback: &fn(NR) -> bool) -> bool {
-        // prune shouldn't mutate, so don't clone
-        if prune(self) {
-            return true;
-        }
+    if !postorder {
+        refs.push(cur.clone());
+    }
+    for kid in cur.children() {
+        // FIXME: Work around rust#2202. We should be able to pass the callback directly.
+        gather(&kid, refs, postorder, |a| prune(a))
+    }
+    if postorder {
+        refs.push(cur.clone());
+    }
+}
 
-        for self.each_child |kid| {
-            // FIXME: Work around rust#2202. We should be able to pass the callback directly.
-            if !kid.traverse_postorder_prune(|a| prune(a), |a| callback(a)) {
-                return false;
-            }
-        }
 
-        callback((*self).clone())
+/// Access the fields of a node without a static TreeNodeRef method call.
+/// If you make an impl TreeNodeRef<Node> for Ref then you should also make
+/// impl TreeNode<Ref> for Node with an empty body.
+pub trait TreeNode<Ref: TreeNodeRef<Self>> {
+    /// Returns the parent of this node.
+    fn parent_node(&self) -> Option<Ref> {
+        TreeNodeRef::parent_node::<Self,Ref>(self)
     }
 
-    fn traverse_preorder(&self, callback: &fn(NR) -> bool) -> bool {
-        self.traverse_preorder_prune(|_| false, callback)
+    /// Returns the first child of this node.
+    fn first_child(&self) -> Option<Ref> {
+        TreeNodeRef::first_child::<Self,Ref>(self)
     }
 
-    fn traverse_postorder(&self, callback: &fn(NR) -> bool) -> bool {
-        self.traverse_postorder_prune(|_| false, callback)
+    /// Returns the last child of this node.
+    fn last_child(&self) -> Option<Ref> {
+        TreeNodeRef::last_child::<Self,Ref>(self)
+    }
+
+    /// Returns the previous sibling of this node.
+    fn prev_sibling(&self) -> Option<Ref> {
+        TreeNodeRef::prev_sibling::<Self,Ref>(self)
     }
-}
 
+    /// Returns the next sibling of this node.
+    fn next_sibling(&self) -> Option<Ref> {
+        TreeNodeRef::next_sibling::<Self,Ref>(self)
+    }
+
+    /// Sets the parent of this node.
+    fn set_parent_node(&mut self, new_parent: Option<Ref>) {
+        TreeNodeRef::set_parent_node::<Self,Ref>(self, new_parent)
+    }
+
+    /// Sets the first child of this node.
+    fn set_first_child(&mut self, new_first_child: Option<Ref>) {
+        TreeNodeRef::set_first_child::<Self,Ref>(self, new_first_child)
+    }
+
+    /// Sets the last child of this node.
+    fn set_last_child(&mut self, new_last_child: Option<Ref>) {
+        TreeNodeRef::set_last_child::<Self,Ref>(self, new_last_child)
+    }
+
+    /// Sets the previous sibling of this node.
+    fn set_prev_sibling(&mut self, new_prev_sibling: Option<Ref>) {
+        TreeNodeRef::set_prev_sibling::<Self,Ref>(self, new_prev_sibling)
+    }
+
+    /// Sets the next sibling of this node.
+    fn set_next_sibling(&mut self, new_next_sibling: Option<Ref>) {
+        TreeNodeRef::set_next_sibling::<Self,Ref>(self, new_next_sibling)
+    }
+}