How to create a reference agnostic trait that allows to iterate over nested structures

I want to create a struct that points to references within a large long lived array within my program. The idea is to not copy any data, but to iterate over existing memory as much as possible.
Furthermore I want to implement a trait for iterators over instances of this struct that allows me to iterate over all references that are held within all instances in the vector.
I also want this trait to be agnostic to the fact if I an iterator over borrowed data or over owned data (for convenience and since this is also the case for most standard library methods (like e.g. map) that work on iterators)
I tried to implement it like so:

use std::borrow::Borrow;

struct ArrayReferences<'r> {
    refs: Vec<&'r f32>,
}

trait GetArrayIterator<'s> {
    fn get_array_iterator(self) -> impl Iterator<Item = &'s f32>;
}

impl<'r, I> GetArrayIterator<'r> for I
    where I: Iterator, I::Item: Borrow<ArrayReferences<'r>> + 'r
{
    fn get_array_iterator(self) -> impl Iterator<Item = &'r f32>
    {
        self.flat_map(|array_refs| {
            array_refs.borrow().refs.iter().map(|y| *y)
        })
    }
}


enum Options {
    A,
    B,
}

fn main() {
    let long_lived_array = [1.0f32, 2.0, 3.0];

    let v = vec![
        ArrayReferences { refs: vec![&long_lived_array[0]] },
        ArrayReferences { refs: vec![&long_lived_array[1]] },
        ArrayReferences { refs: vec![&long_lived_array[2]] },
    ];

    match Options::A {
        Options::A => {
            let iter = v.iter().get_array_iterator();
            for i in iter {
                println!("{}", *i);
            }
        },
        Options::B => {
            let iter = v.into_iter().get_array_iterator();
            for i in iter {
                println!("{}", *i);
            }
        },
        _ => panic!(),
    };
}

However I get an error within the flat map closure:

cannot return value referencing function parameter `array_refs`
returns a value referencing data owned by the current function

Related information:

  * main.rs#17,13: `array_refs` is borrowed here
  * main.rs#17,56: use `.collect()` to allocate the iterator: `.collect::<Vec<_>>()`

 (rustc E0515)

As far as I understand this error tells me that array_refs (the closure argument) does not have a lifetime that extends beyond the closure, while I am returning an iterator that points to data owned by array_refs. However I would expect I::Item: Borrow<ArrayReferences<'r>> + 'r to clearly convey to the compiler that array_refs has lifetime 'r and hence tie it to the lifetime of the item in the returned iterator. However this clearly doesn't work and I can't, for the life of me, figure out how to convey the correct lifetimes to the compiler. Do I somehow have to annotate lifetimes within the closure? Do I have to create my own iterator type (similar to what map or flat_map does) to achieve the desired behaviour?

Note that I'm not interested in a solution that simply works here, this is more of an academic question do help me understand how one handles difficult situations with lifetimes and iterators like this one.

The fundamental problem is that .borrow() returns a reference that borrows from its receiver, i.e. array_refs, and array_refs is a local variable there, so you end up returning something that borrows from that local variable. You'll need to change trait to e.g. Into, so that the result of the equivalent to .borrow() does not borrow from the receiver.

I struggled with this for a few days and of course I figure it out a few minutes after posting it :sweat_smile:. You're right, but the solution is not Into I think. The fundamental problem is that the flat_map closure takes ownership of the iterator item and drops it at the end of the closure. What it should do instead is borrow the iterator item and suddenly everything works, i.e. like this

use std::borrow::Borrow;

struct ArrayReferences<'r> {
    refs: Vec<&'r f32>,
}

trait GetArrayIterator<'s> {
    fn get_array_iterator(self) -> impl Iterator<Item = &'s f32>;
}

impl<'r, I, R> GetArrayIterator<'r> for I
    where I: Iterator<Item = &'r R>,
          R: Borrow<ArrayReferences<'r>> + 'r
{
    fn get_array_iterator(self) -> impl Iterator<Item = &'r f32>
    {
        self.flat_map(|x| {
            x.borrow().refs.iter().map(|y| *y)
        })
    }
}


enum Options {
    A,
    B,
    C,
    D,
}

fn main() {
    let long_lived_array = [1.0f32, 2.0, 3.0];

    let v = vec![
        ArrayReferences { refs: vec![&long_lived_array[0]] },
        ArrayReferences { refs: vec![&long_lived_array[1]] },
        ArrayReferences { refs: vec![&long_lived_array[2]] },
    ];

    match Options::A {
        Options::A => {
            let iter = v.iter().get_array_iterator();
            for i in iter {
                println!("{}", *i);
            }
        },
        Options::B => {
            let iter = v.into_iter().get_array_iterator();
            for i in iter {
                println!("{}", *i);
            }
        },
        _ => panic!(),
    };
}

Except that's not true. In reality option B (i.e. the into_iter line) doesn't work anymore because it doesn't match the Item = &'r R requirement of the trait bounds. But as it turns out, it doesn't make sense to give the iterator ownership over the data anyway, cause it would be dropped before I can use the iterator I'm returning with the function get_array_iterator. If anything a into_array_iterator function would make sense, similar to the iter and into_iter methods of the vector type.

As so often, when the compiler doesn't like it, you might end up not wanting to do it anyway.

Thanks for your response.

If you implement IntoIterator<IntoIter=Copied<Iter<'a, &'f f32>>> for &'a ArrayReferences<'r> you can call flatten on any iterable of references. Is this an option?

EDIT:

I also want this trait to be agnostic to the fact if I an iterator over borrowed data or over owned data

Then the owned case needs to deal with lifetimes. If you add IntoIterator<IntoIter=vec::IntoIter<&'r f32>> you might already cover all practical cases. You can cover both cases with the IntoIter<Item=&'r f32> trait bound. Or do you need the extra abstraction?

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.