Issues constraining implementation lifetimes on type without lifetime parameter

Question

I'm trying to implement a BST in Rust (for HW3 in this lovely intro to Rust), and I'm running into errors with lifetimes, and how to constrain lifetimes for types that are related to types without a lifetime.

#[derive(Debug)]
pub struct BST<T>
    where T: Ord
{
    root: Option<Box<Node<T>>>,
}

// A couple dozen lines of BST stuff

impl<'a, T> IntoIterator for BST<T>
    where T: Ord
{
    type Item = T;
    type IntoIter = BSTIter<'a, T>; // <- my intuition is that I should
                                        // be able to say "BSTIter lives as
                                        // long as BST."

    fn into_iter(&'a mut self) -> BSTIter<'a, T> {
        BSTIter::new(&mut self)
    }
}


pub struct BSTIter<'a, T: 'a>
    where T: Ord + 'a
{
    bst: &'a mut BST<T>,
    node_list: Vec<&'a Node<T>>, // this is where the need for a lifetime on
                                 // BSTIter comes from
}


impl<'a, T> BSTIter<'a, T>
    where T: Ord
{
    fn new(&mut bst: BST<T>) -> BSTIter<'a, T> {
        let traverse_stack = Vec::new();
        if let Some(ref x) = bst.root {
            traverse_stack.push(x);
        }
        BSTIter {
            bst: bst,
            node_list: traverse_stack,
        }
    }
}


impl<'a, T> Iterator for BSTIter<'a, T>
    where T: Ord
{
    type Item = T;

    fn next(&mut self) -> Option<T> {
        // BST iteration details
    }
}

As it stands, this code spits out the error

error[E0207]: the lifetime parameter `'a` is not constrained by the impl trait, self type, or predicates
   --> src/lib.rs:117:7
    |
117 | impl<'a, T> IntoIterator for BST <T> where T: Ord {
    |      ^^ unconstrained lifetime parameter

If the IntoIterator trait didn't require me to specify type IntoIterator = BSTIter, the implementation block could just have an into_iter method signature of into_iter<'a>(&'a mut self) -> BSTIter<'a, T>. Since I need to specify the lifetime for BSTIter, it seems like I need to specify a lifetime for the entire BST type. Again, my instinct says that I shouldn't have to specify a lifetime on BST to be able to create an iterator for it.

I realize the two solutions to this are likely one (or both) of

1. There's a language feature that helps me get around this
2. Somewhere along the way, my code became very much not idiomatic Rust

If I could get help on either how to make the above code snippet work, or how I should be approaching these lifetime and ownership details in general, it would be very much appreciated!

Answer 1

You've misunderstood the purpose and usage of IntoIterator. It converts a value into an iterator; consuming the value in the process. However, your iterator is attempting to return references to the collection. You cannot return references into the iterator, so it makes no sense to consume the tree, transferring ownership to the iterator.

The fact that you've called it BSTIter instead of BSTIntoIter shows promise; as that's the idiomatic name for an iterator that returns references.

You want to implement IntoIterator for &'a BST<T>, not BST<T>. You could also implement it for BST<T>, but then you'd want to yield T, not &T.

After fixing that, there's lots of compiler errors: mismatched types all throughout the code, incorrect method signatures in traits (fn into_iter(self) is all you are allowed), for some reason there's a mutable reference to the tree, variables aren't mutable when they should be....

#[derive(Debug)]
struct Node<T>(Option<Box<T>>);

#[derive(Debug)]
pub struct BST<T>
    where T: Ord
{
    root: Option<Box<Node<T>>>,
}

impl<'a, T> IntoIterator for &'a BST<T>
    where T: Ord
{
    type Item = T;
    type IntoIter = BSTIter<'a, T>;
    fn into_iter(self) -> BSTIter<'a, T> {
        BSTIter::new(self)
    }
}

pub struct BSTIter<'a, T: 'a>
    where T: Ord + 'a
{
    bst: &'a BST<T>,
    node_list: Vec<&'a Node<T>>,
}

impl<'a, T> BSTIter<'a, T>
    where T: Ord
{
    fn new(bst: &'a BST<T>) -> BSTIter<'a, T> {
        let mut traverse_stack = Vec::new();
        if let Some(ref x) = bst.root {
            traverse_stack.push(&**x);
        }
        BSTIter {
            bst: bst,
            node_list: traverse_stack,
        }
    }
}

impl<'a, T> Iterator for BSTIter<'a, T>
    where T: Ord
{
    type Item = T;

    fn next(&mut self) -> Option<T> {
        None
    }
}

fn main() {}