Search code examples
rustiteratorassociated-types

Pull struct out of associated type returned by iterator


I am implementing a double linked list in rust. I have created an iterator that works fine.

#[derive(Clone, Debug)]
pub struct LLCursor<T: Copy> {
    pub cur: Option<Rc<RefCell<Node<T>>>>,
}

impl<T> IntoIterator for List<T>
where
    T: Clone + Copy,
{
    type Item = Rc<RefCell<Node<T>>>;
    type IntoIter = LLCursor<T>;

    fn into_iter(self) -> Self::IntoIter {
        LLCursor {
            cur: self.head.clone(),
        }
    }
}

impl<T> Iterator for LLCursor<T>
where
    T: Copy,
{
    type Item = Rc<RefCell<Node<T>>>;

    fn next(&mut self) -> Option<Rc<RefCell<Node<T>>>> {
        match self.cur.clone() {
            Some(node) => {
                self.cur = node.borrow().next.clone();
                Some(node)
            }
            None => None,
        }
    }
}

I would like to make a function that can access the contents of the Nodes of the linked list as it is iterated over. Something like this:

pub fn print(self)
where
    List<T>: IntoIterator,
    <List<T> as IntoIterator>::Item: std::fmt::Debug,
{
    for i in self {
        println!("{:?}", Some(i.borrow().clone().item));
    }
}

Error:

error[E0599]: no method named `borrow` found for associated type `<List<T> as IntoIterator>::Item` in the current scope
   --> src/list.rs:90:51
    |
90  |             println!("{:?}", i.borrow().clone().item);
    |                                ^^^^^^ method not found in `<List<T> as IntoIterator>::Item`
    |
    = help: items from traits can only be used if the trait is in scope
    = note: the following trait is implemented but not in scope; perhaps add a `use` for it:
            `use std::borrow::Borrow;`

I understand that i in this context is of type <List<T> as IntoIterator>::Item. I am new to rust so I do not see how it is useful that the iterator returns the associated type in this manner. I would expect i to be of type Option<Rc<RefCell<Node<T>>>>. Is there a way that I can pull this out of the associated type so I am able to access the elements of each individual Node?


Solution

  • None of the iterator code actually requires T: Copy, I suggest you remove it since it is obfuscating your problem. Then, since you know <List<T> as IntoIterator>::Item is actually T, you can use it directly:

    pub fn print(self) where T: Debug {
        for i in self {
            println!("{:?}", i.borrow().item);
        }
    }
    

    I also removed the .clone() when printing since its unnecessary and avoids the T: Clone constraint. See it working on the playground.


    The reason for the error you got is because constraining that List<T>: IntoIterator and Item: Debug does not mean that Item is a Rc<RefCell<_>>. You would need an additional constraint T: Copy for it to deduce the correct IntoIterator implementation. No other implementations exist as far as your demonstrated code shows, but a non-conflicting implementation could in theory exist and the compiler does not make guesses.

    As a side note, constraining on the Self type (here explicitly as List<T>) is pretty uncommon except in traits as you typically know what is needed for Self to satisfy those constraints, and its more descriptive to list that directly. (i.e. if Self needed to be Clone, but you know that Self is Clone if T is Clone, you would use T: Clone as the constraint).