Using a returned Iterator


#1

Hi,

I’m trying to write a function that returns an iterator over a large body of data. Below is a simplified version of the function and where it’ll be used.

    pub fn foo<'a>(&'a self) -> &'a Iterator<u16>
    {
        &self.some_huge_array
            .windows(2)
            .enumerate()
            .filter_map(|(i, w)| do_a_thing(i, w))
    }
    
    pub fn bar(&self) -> u16 {
        self.foo()
            .filter(|x| x < 3)
            .take(1)
    }

The issue is that the call to filter in bar requires the iterator it’s called on to be Sized. How can I help the compiler see that foo's return is Sized without writing out FilterMap<Enumerate<...>, ...>?

Thanks!


#2

Compiler errors have led you astray on this one. There are many issues here, and I wouldn’t rank the mismatch in Sized bounds among the top 10. The biggest ones though are:

####bar can’t call foo().filter() because it doesn’t own foo().

foo returns a borrowed type, but the signature of filter is

fn filter<P>(self, predicate: P)
where P: FnMut(&Self::Item) -> bool { ... }

which takes the iterator by value. Almost all iterator methods do, which is nice because it eliminates the issue of iterator invalidation. Incidentally, these self-taking methods are the reason the Sized bound is there. (but to focus on Sized as the issue is missing the forest for the trees)

You cannot return a borrow to a temporary object.

Windows, Enumerate, and FilterMap adapters are constructed on the stack inside foo(), and are gone as soon as the function ends.

Generally speaking, functions that return a type &T must fall into one of two categories:

  • Projections; returning something like &self.member or &self[index]
  • References to static memory; you can borrow static literals like "Hello world" and &0.

The solution

So we see that &Trait is okay for dynamic polymorphism in function arguments, but not so much for function outputs!

A similar issue exists for &str and &[T]; these are great to use as function argument types, but for outputs and temporary values one usually needs to use the owned variants instead (String and Vec<T>). As luck has it, Rust also has an owned variant of &T, called Box, which throws something onto the heap.

The fix is easy:

pub fn foo(&self) -> Box<Iterator<Item=u16>>
{
    Box::new(self.some_huge_array
        .windows(2)
        .enumerate()
        .filter_map(|(i, w)| Some(w[0])))
}

Wellll, almost.

The compiler is still angry with this, because Box<Trait> by default assumes that it is safe for the Box to go on living forever (its type argument is assigned the 'static lifetime). However, this is not the case here, because the iterator is borrowing &self. We need to make sure that the lifetime of the Box’s value is tied to the lifetime of the borrow, by adding a slight bit of unusual syntax: Box<Iterator<Item=u16> + 'a>.

An example that compiles

struct A { some_huge_array: Vec<u16> }

impl A {
    pub fn foo<'a>(&'a self) -> Box<Iterator<Item=u16> + 'a>
    {
        Box::new(self.some_huge_array
            .windows(2)
            .enumerate()
            .filter_map(|(i, w)| Some(w[0])))
    }
    
    pub fn bar(&self) -> u16 {
        self.foo()
            .filter(|&x| x < 3)
            .nth(0)
            .unwrap()
    }
}

fn main() {}

#3

This is a common issue. You can read this to understand it in details.

To make it short, an Iterator is a trait not an object. If you want to return an object you have several choices:

  • the simplest on stable but not the most efficient: box it: return Box<Iterator>
  • the simplest on nightly, use the unstable impl trait feature very efficient as well: use f() -> impl Iterator
  • the fastest on stable but not so simple: you need to wrap your iterator into a custom struct and manually implement Iterator on that struct

#4

Thank you both very much! The compiler did indeed lead me astray :slight_smile: