How to compose mutable Iterators?

Question

Editor's note: This code example is from a version of Rust prior to 1.0 and is not syntactically valid Rust 1.0 code. Updated versions of this code produce different errors, but the answers still contain valuable information.

I would like to make an iterator that generates a stream of prime numbers. My general thought process was to wrap an iterator with successive filters so for example you start with

let mut n = (2..N)

Then for each prime number you mutate the iterator and add on a filter

let p1 = n.next()
n = n.filter(|&x| x%p1 !=0) 
let p2 = n.next()
n = n.filter(|&x| x%p2 !=0) 

I am trying to use the following code, but I can not seem to get it to work

struct Primes {
    base: Iterator<Item = u64>,
}

impl<'a> Iterator for Primes<'a> {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let p = self.base.next();
        match p {
            Some(n) => {
                let prime = n.clone();
                let step = self.base.filter(move |&: &x| {x%prime!=0});
                self.base = &step as &Iterator<Item = u64>;
                Some(n)                
            },
            _ => None
        }        
    }
}

I have toyed with variations of this, but I can't seem to get lifetimes and types to match up. Right now the compiler is telling me

1. I can't mutate self.base
2. the variable prime doesn't live long enough

Here is the error I am getting

solution.rs:16:17: 16:26 error: cannot borrow immutable borrowed content `*self.base` as mutable
solution.rs:16         let p = self.base.next();
                                                     ^~~~~~~~~
solution.rs:20:28: 20:37 error: cannot borrow immutable borrowed content `*self.base` as mutable
solution.rs:20                 let step = self.base.filter(move |&: &x| {x%prime!=0});
                                                                ^~~~~~~~~
solution.rs:21:30: 21:34 error: `step` does not live long enough
solution.rs:21                 self.base = &step as &Iterator<Item = u64>;
                                                                  ^~~~
solution.rs:15:39: 26:6 note: reference must be valid for the lifetime 'a as defined on the block at 15:38...
solution.rs:15     fn next(&mut self) -> Option<u64> {
solution.rs:16         let p = self.base.next();
solution.rs:17         match p {
solution.rs:18             Some(n) => {
solution.rs:19                 let prime = n.clone();
solution.rs:20                 let step = self.base.filter(move |&: &x| {x%prime!=0});
                                     ...
solution.rs:20:71: 23:14 note: ...but borrowed value is only valid for the block suffix following statement 1 at 20:70
solution.rs:20                 let step = self.base.filter(move |&: &x| {x%prime!=0});
solution.rs:21                 self.base = &step as &Iterator<Item = u64>;
solution.rs:22                 Some(n)                
solution.rs:23             },
error: aborting due to 3 previous errors

Why won't Rust let me do this?

Answer 1

Here is a working version:

struct Primes<'a> {
    base: Option<Box<Iterator<Item = u64> + 'a>>,
}

impl<'a> Iterator for Primes<'a> {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let p = self.base.as_mut().unwrap().next();
        p.map(|n| {
            let base = self.base.take();
            let step = base.unwrap().filter(move |x| x % n != 0);
            self.base = Some(Box::new(step));
            n
        })
    }
}

impl<'a> Primes<'a> {
    #[inline]
    pub fn new<I: Iterator<Item = u64> + 'a>(r: I) -> Primes<'a> {
        Primes {
            base: Some(Box::new(r)),
        }
    }
}

fn main() {
    for p in Primes::new(2..).take(32) {
        print!("{} ", p);
    }
    println!("");
}

I'm using a Box<Iterator> trait object. Boxing is unavoidable because the internal iterator must be stored somewhere between next() calls, and there is nowhere you can store reference trait objects.

I made the internal iterator an Option. This is necessary because you need to replace it with a value which consumes it, so it is possible that the internal iterator may be "absent" from the structure for a short time. Rust models absence with Option. Option::take replaces the value it is called on with None and returns whatever was there. This is useful when shuffling non-copyable objects around.

Note, however, that this sieve implementation is going to be both memory and computationally inefficient - for each prime you're creating an additional layer of iterators which takes heap space. Also the depth of stack when calling next() grows linearly with the number of primes, so you will get a stack overflow on a sufficiently large number:

fn main() {
    println!("{}", Primes::new(2..).nth(10000).unwrap());
}

Running it:

% ./test1 

thread '<main>' has overflowed its stack
zsh: illegal hardware instruction (core dumped)  ./test1