Returning iterators and lifetime annotation woes

help
1

Hello everyone!

I've been playing with rust for a short time, and am currently hitting a brick wall while fighting the borrow checker when using the ndarray crate (version 0.7.2). I compiled a minimal example for you to look at.

First version: The ArrayViewMut1 reference and the returned iterator get the same lifetime b' which outlives the lifetime of the reference to the values of the array 'a and the values themselves T.

extern crate ndarray;

use ndarray::{Array2, ArrayViewMut1, Axis};

fn iter_line_elements<'b, 'a: 'b, A: 'a>(line: &'b mut ArrayViewMut1<'a, A>)
        -> Box<Iterator<Item=&'a mut A> + 'b> {
    Box::new(line.iter_mut())
}

fn main() {
    let mut matrix = Array2::from_elem((4, 4), Some(1u32));
    for ref mut col in matrix.axis_iter_mut(Axis(1)) {
        let _ = iter_line_elements(col);

        //Inlining the function works!
        //let _ = Box::new(col.iter_mut()); 
    }
}

rustc's (version 1.14.0) output:

src/main.rs|6 col 19 error 495| cannot infer an appropriate lifetime for autoref due to conflicting requirements
||   |
|| 6 |     Box::new(line.iter_mut())
||   |                   ^^^^^^^^
||   |
|| help: consider using an explicit lifetime parameter as shown: fn iter_line_elements<'a:'b, A: 'a>(line: &'a mut ArrayViewMut1<'a, A>)
||  -> Box<Iterator<Item = &'a mut A>+ 'b>
||  --> src/main.rs:5:1
||   |
|| 5 | fn iter_line_elements<'b, 'a: 'b, A: 'a>(line: &'b mut ArrayViewMut1<'a, A>) -> Box<Iterator<Item=&'a mut A> + 'b> {
||   | ^

Ok, I'm not sure I understand that suggestion, but let's try:

fn iter_line_elements<'b, 'a: 'b, A: 'a>(line: &'a mut ArrayViewMut1<'a, A>)
        -> Box<Iterator<Item=&'a mut A> + 'b> {
    Box::new(line.iter_mut())
}

I deviated slightly from rustc's suggestion as it fails to declare 'b (why?). Now rustc reports the following error, but does not give any suggestions on how to fix that:

src/main.rs|21 col 5 error| borrowed value does not live long enough
||    |
|| 18 |     for ref mut col in matrix.axis_iter_mut(Axis(1)) {
||    |         ----------- borrow occurs here
|| ...
|| 21 |     }
||    |     ^ borrowed value dropped here while still borrowed
||    |
||    = note: values in a scope are dropped in the opposite order they are created

I guess because the lifetimes of the referenced values (within ArrayViewMut) and the reference to the ArrayViewMut struct are the same, the borrow checker assumes that col has to live as long as matrix. Is that correct?
How would I have to change the signature to allow for a successful compilation? I feel that the first version should compile and do not really understand the reason why compilation fails.

Any help would be appreciated!

2

So here's what works for me:

fn iter_line_elements<'b, 'a : 'b, A>(line: &'a mut ArrayViewMut1<A>)
                                         -> Box<Iterator<Item=&'a mut A> + 'b> {
    Box::new(line.iter_mut())
}

As you can see, it's nearly identical to yours. The only difference is that this version does not tie 'A' to the 'a lifetime - instead, it gets its own (unnamed) lifetime (which is my understanding, but I'm a Rust newbie).

The way I read the above is "given a mutable reference to line with lifetime 'a, return an Iterator that in turn yields references to A's with the same lifetime as line, but the iterator itself has a lifetime 'b; lifetime 'b is outlived by (or equal to) 'a, which is the reference to the ArrayViewMut1 itself". In other words, the Iterator cannot outlive the backing ArrayViewMut1, which makes sense.

I'm not sure if my explanation is 100% correct or whether it makes sense, but hope it helps to some degree at least. And, if more experienced Rustaceans want to chime in, I'm all ears.

1 Like
3

Interesting! I wasn't aware of the possibility to (partially) leave out the lifetime parameters in a function.

Your explaination makes sense to me, thanks! Thanks to your explanation I think I also figured out a problem with my first approach:

fn iter_line_elements<'b, 'a: 'b, A: 'a>(line: &'b mut ArrayViewMut1<'a, A>)
        -> Box<Iterator<Item=&'a mut A> + 'b> {
    Box::new(line.iter_mut())
}

My guess would be that the compiler cannot guarantee that line creates an iterator that yields reference that potentially live longer than line itself, even though we know from the broader context.

Moreover, as it turns out (at least for this example) we do not need a second lifetime parameter after all. The following works just fine:

fn iter_line_elements<'a, A>(line: &'a mut ArrayViewMut1<A>)
                                         -> Box<Iterator<Item=&'a mut A> + 'a> {
    Box::new(line.iter_mut())
}

I would also really appreciate if any more experienced can comment on my speculations and vitalyd's expanation. Before I encountered this problem I thought I understood lifetime parameters quite well, now I'm not so sure anymore...

4

We note that it's not possible to create custom types that mirror completely how slices work in rust (&'x mut [A]), so custom view types like ArrayViewMut can be a bit awkward.

We can analyze the parts like this:

line: &'a mut ArrayViewMut1<'b, A>

A mutable reference (lifetime 'a) to a read-write array view which borrows elements of lifetime 'b.

This mutable reference to a view is relatively common, due to the “no custom slices” thing.

'b must be longer than 'a, because we have a reference with scope 'a that points to a reference (view) with scope 'b. The innermost thing must live the longest. Formally said like 'b: 'a (“'b outlives 'a”)

The iter_mut method looks more or less like this:

impl<A, S, D> ArrayBase<S, D> {
    // for ArrayViewMut, S is equal to ViewRepr<&'y mut A>
    fn iter_mut<'x>(&'x mut self) -> IterMut<'x, A>
}

So for your reference to arrayviewmut, you can get an iterator with scope IterMut<'a, A>, because you have an &'a mut ArrayViewMut1<..>. The scope of the iterator can never be longer than the outermost (and shorter or equal) scope, which is 'a, for the mutable case.

There's another way to get an IterMut which is the IntoIterator implementation for array views. This is only applicable if you have a view by value:

// If you have a view by value (not reference)
ArrayViewMut1<'b, A>
// then .into_iter() gives a
IterMut<'b, A>

fn iter_line_elements<'b, A>(line: ArrayViewMut1<'b, A>)
                 -> Box<Iterator<Item=&'b mut A> + 'b> {
    Box::new(line.into_iter())
}

P.S The restriction 'a: 'b in your previous code, combined with the automatic/implicit requirement of 'b: 'a, they combine to require that 'a and 'b are completely equal. (Of course, if a <= b and b <= a, then it must be that a == b).

1 Like
5

As an addition, this nesting rule is particular to mutable references.

If we have:

r: &'a mut GiveReferenceMut<'b, X>
// GiveReferenceMut is something that's a bit like a mutable reference.
// For example a mutable reference iterator..

the innermost things must live the longest. Formally this is X: 'b (because we have mutable references to X), and then the outer layer requires X: 'a (“X outlives 'a”) and 'b: 'a (“'b outlives 'a”)

For mutable references, the rule is that if we access GiveReferenceMut through &'a mut, we can only get a borrow of scope at most 'a, which is always the smaller (or equal) of the scopes 'a and 'b.

The reasoning is simple: Mutable references are a unique access token. We have unique access to the “GiveReferenceMut” only through the scope 'a, so that's the only scope our derived borrows can in turn be guaranteed unique.

Shared references are much simpler:

r: &'a GiveReference<'b, X>
// GiveReference is something that's a bit like a shared reference.
// For example a shared reference iterator..

We still have the rule that the innermost things must live the longest. X: 'b, and X: 'a, and 'b: 'a.

Shared references are implicitly copyable. Even if 'a is much shorter than 'b, we know that for the whole scope of 'b, there are shared references alive that point to values of X. It is of no harm to give out more of these. So through r we can get &'b X references without problem.

1 Like
6

Thank you for your insights, bluss.

I think we mixed up our 'a and 'b. In order to avoid confusion I am going to switch over to 'c and 'd now.
My original defintion was:

fn iter_line_elements<'d, 'c: 'd, A: 'c>(line: &'d mut ArrayViewMut1<'c, A>)
        -> Box<Iterator<Item=&'c mut A> + 'd> {
    Box::new(line.iter_mut())
}

As you said, line: &'d mut ArrayViewMut1<'c, A> implies 'c: 'd, which is also what is stated explicitly in the signature: iter_line_elements<'d, 'c: 'd, A: 'c>.

However, if I understand correctly, 'c == 'd is just a consequence of the definition of iter_mut, i.e. the awkwardness of custom view types that (as you pointed out) restricts the lifetime of iterator references to that of the custom view reference.
Still, even if 'c == 'd, I wonder what exactly the "conflicting requirements" are that rustc mentions. Should rustc not be happy to just let the original values, the ArrayViewMut1, the Iterator, and the values references in the iterator have the same "life span" and let them "die together"? I would now expect an error message that is not local to iter_line_elements like the one mentioned in the original post after applying rustc's suggested changes.

7

I'm not sure how to tie in with your code, but it's not possible for you to return an iterator with &'a mut A elements if you have a &'b mut ArrayViewMut1<'a, A>. You need to return an iterator with element type &'b mut A, the shorter of the two lifetimes.

To put it in another way, the function signature requires that 'a == 'b, but that's not possible.

2 Likes
8

This is a typical place where I would use the into_iter solution.

1 Like
9

Yeah, I got that. I was just wondering why 'a == 'b is not possible, but I guess it is just enforced by the compiler -- not for a strict reason, but because it's probably not what you wanted to express.

In my (non-minimal) case into_iter is not applicable, because in need the ArrayView to be accessible after the call to iter_line_elements. However, that is not a problem, as the solution of vitalyd works in this case:

fn iter_line_elements<'b, 'a : 'b, A>(line: &'a mut ArrayViewMut1<A>)
    -> Box<Iterator<Item=&'a mut A> + 'b> {
    Box::new(line.iter_mut())
}

Thank both of you for your help!

10

I don't know. Is it simply variance + subtyping? A type like &mut X is invariant in the X parameter, which means the type inference is not allowed to “slide” the lifetimes in X to fit.

Note that you can use into_iter in some way, you can call .view_mut() to do the equivalent of reborrowing an array view.

1 Like