Unexpected borrowck error when returning an impl Trait

[as-cii]

The following playground highlights the issue: https://play.rust-lang.org/?gist=cf6be643e3a2fb6d69ac835cec890ad2&version=nightly&mode=debug&edition=2015

fn main() {
    let mut v = Vec::new();
    let x = good(v.iter().cloned());
    let y = bad(v.iter().cloned()); // if you comment out this line, it compiles.
    v.push(3);
}

fn good<I: Iterator<Item = usize>>(x: I) -> std::vec::IntoIter<usize> {
    x.collect::<Vec<usize>>().into_iter()
}

fn bad<I: Iterator<Item = usize>>(x: I) -> impl Iterator<Item = usize> {
    x.collect::<Vec<usize>>().into_iter()
}

error[E0502]: cannot borrow `v` as mutable because it is also borrowed as immutable
 --> src/main.rs:5:5
  |
4 |     let y = bad(v.iter().cloned()); // if you comment out this line, it compiles.
  |                 - immutable borrow occurs here
5 |     v.push(3);
  |     ^ mutable borrow occurs here
6 | }
  | - immutable borrow ends here

We have two implementations of the same function that are equivalent, except that one returns an impl Iterator while the other returns a concrete type. Calling the version that returns impl Trait seems to incorrectly tie the lifetime of the return value to the function's argument.

We have tested this on:

• rustc 1.28.0
• rustc 1.29.0-beta4
• rustc 1.30.0-nightly (b202882 2018-08-16)

/cc: @nathansobo

[memoryruins]

Thanks for the report and example @as-cii!
Tagging as A-NLL since it could potentially be fixed extending NLL, which currently also errors when enabled.

Similar issue #53528

[pnkfelix]

The root cause of the issue here is that during the compilation of fn main, the borrow-checker assumes that y (an impl Iterator) has a destructor, and so the time at which y is dropped is significant.

We can observe the compiler's respecting that significance by applying a similar workaround to the one I applied to #53528: drop y before trying to mutate v (play):

#![feature(nll)]
#![allow(unused_variables)]

fn main() {
    let mut v = Vec::new();
    let x = good(v.iter().cloned());
    let y = bad(v.iter().cloned());
    drop(y);
    v.push(3);
}

fn good<I: Iterator<Item = usize>>(x: I) -> std::vec::IntoIter<usize> {
    x.collect::<Vec<usize>>().into_iter()
}

fn bad<I: Iterator<Item = usize>>(x: I) -> impl Iterator<Item = usize> {
    x.collect::<Vec<usize>>().into_iter()
}

Or even just processing the iterator y in a by-value for-loop also seems to suffice (play):

#![feature(nll)]
#![allow(unused_variables)]

fn main() {
    let mut v = Vec::new();
    let x = good(v.iter().cloned());
    let y = bad(v.iter().cloned());
    for _ in y { }
    v.push(3);
}

fn good<I: Iterator<Item = usize>>(x: I) -> std::vec::IntoIter<usize> {
    x.collect::<Vec<usize>>().into_iter()
}

fn bad<I: Iterator<Item = usize>>(x: I) -> impl Iterator<Item = usize> {
    x.collect::<Vec<usize>>().into_iter()
}

---

However, unlike #53528 where I could imagine a future language extension that "fixes" #53528, I don't think the compiler's reasoning is overly conservative in this case, at least for this code as written.

Explanation: Part of the idea of impl Iterator in return type is that the function implementation should be free to revise the type it chooses in the future. In particular, a future version of the bad function could swap in an Iterator implementation that has a destructor where that destructor mutates the original iterator x, like so (play):

#![feature(nll)]
#![allow(unused_variables, unused_mut)]

use std::fmt;

fn main() {
    let mut v = vec![1, 2, 3, 4];
    {
        let x = good(v.iter().cloned());
        let mut y = bad(v.iter().cloned());
        
        // even trying to exhaust `y` will not suffice unless we actually
        // *consume* it (and thus run its destructor):
        for (i, elem) in y.by_ref().enumerate() {
            println!("processing y[{}]: {:?}", i, elem);
        }
        println!("`y` is \"exhausted\" here, but not dead.");

        println!("this is where you wanted to push");
        // v.push(5);
        
        println!("end of block");
    }
}

fn good<I: Iterator<Item = usize>>(x: I) -> std::vec::IntoIter<usize> {
    x.collect::<Vec<usize>>().into_iter()
}


fn bad<I: Iterator<Item = usize>>(x: I) -> impl Iterator<Item = usize> {
    // x.collect::<Vec<usize>>().into_iter()
    return DeadHands { iter: x, limit: 2 };
    
    /// An iterator that yields at most `self.limit` items from given `iter`.
    struct DeadHands<I: Iterator> where I::Item: fmt::Debug {
        iter: I,
        limit: usize 
    }
    impl<I: Iterator> Drop for DeadHands<I> where I::Item: fmt::Debug {
        fn drop(&mut self) {
            for elem in self.iter.by_ref() {
                println!("accessing elem {:?} from *original* iterator", elem)
            }
        }
    }
    impl<I: Iterator> Iterator for DeadHands<I> where I::Item: fmt::Debug {
        type Item = I::Item;
        fn next(&mut self) -> Option<I::Item> {
            if self.limit > 0 {
                self.limit -= 1;
                self.iter.next()
            } else {
                None
            }
        }
    }

}

when one runs the above code in the playground, it prints:

processing y[0]: 1
processing y[1]: 2
`y` is "exhausted" here, but not dead.
this is where you wanted to push
end of block
accessing elem 3 from *original* iterator
accessing elem 4 from *original* iterator

thus illustrating that the destructor is holding onto the originally given iterator and doing stuff with it after the point in the control flow where you wished to mutate v.

[pnkfelix]

See also discussion on rust-lang/rfcs#1951 about which lifetimes are in scope for impl Trait; note especially that type parameters make their lifetimes implicity in scope for an impl Trait in return position.

• (As far as I can tell, there's no way to specify that a given type parameter is not in scope for an impl Trait in return position, which I think could be an interesting way to deal with the problem described here. After all, your original implementation of fn bad didn't actually have a dependence between the returned impl Iterator and the given argument iterator x: I, and so it presents an interesting case where our rules for impl Iterator are "too" flexible...)
• An alternative approach would be to use Box<Trait> instead of impl Trait, which then ensures that even the lifetimes from x: I are not in scope.

[pnkfelix]

My current plan is to close this issue as "not a bug" based on the reasoning given in #53450 (comment) ; basically, I think the problems here are issues with the expressiveness of impl Trait, and not problems with NLL nor borrow-checking.

(This bug does not currently have a milestone, priority, nor NLL-label attached to it. If I see push back against closing the issue, then I'll we'll need to fill those in in some manner. But since I expect to close this, I am not inclined to tag it with any further labels nor milestones.)

[eddyb]

If you use the explicit version of impl Trait (note that the syntax is unstable and in flux), it works:

#![feature(existential_type)]

fn main() {
    let mut v = Vec::new();
    let x = good(v.iter().cloned());
    let y = bad(v.iter().cloned()); // if you comment out this line, it compiles.
    v.push(3);
}

fn good<I: Iterator<Item = usize>>(x: I) -> std::vec::IntoIter<usize> {
    x.collect::<Vec<usize>>().into_iter()
}

existential type Foo: Iterator<Item = usize>;

fn bad<I: Iterator<Item = usize>>(x: I) -> Foo {
    x.collect::<Vec<usize>>().into_iter()
}

[pnkfelix]

Okay now that I've seen that our future plans include a way to specify the existential here with more explicit control over which lifetimes could be in the concrete type, I'm going to close this ticket as "not a bug."

(See also #42940)