NLL + impl Trait: Borrow checker error on else branch

[andreytkachenko]

Here is an example:

#![feature(nll)]

#[derive(Default)]
struct X(Vec<u32>);

impl X {
    // error will gone if uncomment
    // fn get_iter(&self) -> Option<std::slice::Iter<'_, u32>> {
    fn get_iter(&self) -> Option<impl Iterator<Item = &u32>> { 
        Some(self.0.iter())
    }
    
    fn push(&mut self, x: u32) {
        self.0.push(x);
    }
}

fn main() {
    let mut tmp = X::default();

    if let Some(xx) = tmp.get_iter() { // `xx` holds the reference to `tmp`
        for t in xx {
            println!("{:?}", t);
        }

        // but here `xx` is dropped
    } else {
        tmp.push(1); // ERROR: cannot borrow `tmp` as mutable because it is also borrowed as immutable
        // why tmp is still borrowed here?
    };
}

here is the error:

error[E0502]: cannot borrow `tmp` as mutable because it is also borrowed as immutable
  --> src/main.rs:26:9
   |
19 |     if let Some(xx) = tmp.get_iter() { // `xx` holds the reference to `tmp`
   |                       --- immutable borrow occurs here
...
26 |         tmp.push(1); // ERROR: cannot borrow `tmp` as mutable because it is also borrowed as immutable
   |         ^^^^^^^^^^^ mutable borrow occurs here

[memoryruins]

	ast	#![feature(nll)]
-> Option<impl Iterator<Item = &u32>>	error	error
-> Option<std::slice::Iter<'_, u32>>	error	compiles

rust version 1.30.0-nightly (f8d34596f 2018-08-30)

[nikomatsakis]

Hmm my guess is that this has something to do with the variance of impl Iterator<Item = &32> (invariant) vs Iter<'_, u32> (variant), but I could be wrong. Nice find @andreytkachenko, thanks for the bug report. We'll see what we can do...

[pnkfelix]

discussed at meeting. assigning to self to investigate root cause.

[pnkfelix]

I've started looking at this

While comparing the log output when compiling the two variants, I noticed this difference:

Working variant with std::slice::Iter:

borrow_check::nll::renumber: visit_region(region=ReScope(Node(ItemLocalId(103))), location=bb2[2])
borrow_check::nll::renumber: renumber_regions(value=ReScope(Node(ItemLocalId(103))))

non-working variant with impl Iterator

borrow_check::nll::renumber: visit_region(region=ReScope(Destruction(ItemLocalId(104))), location=bb2[2])
borrow_check::nll::renumber: renumber_regions(value=ReScope(Destruction(ItemLocalId(104))))

This led me to wonder: could we be forced to keep the region alive because the impl Iterator might reference it when it is dropped?

It was easy enough to make a variant example that tried to model this (play):

#![feature(nll)]

#[derive(Default)]
struct X(Vec<u32>);

struct DropIter<'a, X: 'a>(std::slice::Iter<'a, X>);

// (just delegates to underlying iterator)
impl<'a, X> Iterator for DropIter<'a, X> {
    type Item = &'a X;
    fn next(&mut self) -> Option<&'a X> { self.0.next() }
}

impl<'a, X> Drop for DropIter<'a, X> {
    fn drop(&mut self) { /* no-op, but code below cannot use that knowledge */ }
}

impl X {
    // error will gone if uncomment
    // fn get_iter(&self) -> Option<std::slice::Iter<'_, u32>> { Some(self.0.iter()) }
    fn get_iter(&self) -> Option<DropIter<'_, u32>> { Some(DropIter(self.0.iter())) }

    fn push(&mut self, x: u32) {
        self.0.push(x);
    }
}

fn main() {
    let mut tmp = X::default();

    if let Some(xx) = tmp.get_iter() { // `xx` holds the reference to `tmp`
        for t in xx {
            println!("{:?}", t);
        }

    } else {
        tmp.push(1); // ERROR: cannot borrow `tmp` as mutable because it is also borrowed as immutable
    };
}

and indeed, when we wrap the iterator in a Drop struct, it causes the same error that was observed with impl Iterator...

So now my new questions:

• Why is this being kept alive for so long in this case?
• Is this an artifact of how we model a lifetime that has to strictly outlive another lifetime?

[pnkfelix]

Ah, I think I know what's going on: Since DropIter has a destructor, the borrow-checker's internal model of the code says that it needs to be prepared to run that destructor when it drops an Option<DropIter>.

That reasoning is applied for both the Some and None variants of the Option.

Therefore, on the else branch, the compiler keeps the lifetime of the borrow alive long enough so that it will be around for the drop of the None value.

This leads us to the following workaround for the problem as described: if you explicitly bind and then drop the None value, that gives the borrow-checker enough info for it to let the code pass through (play):

#![feature(nll)]

#[derive(Default)]
struct X(Vec<u32>);

struct DropIter<'a, X: 'a>(std::slice::Iter<'a, X>);

// (just delegates to underlying iterator)
impl<'a, X> Iterator for DropIter<'a, X> {
    type Item = &'a X;
    fn next(&mut self) -> Option<&'a X> { self.0.next() }
}

impl<'a, X> Drop for DropIter<'a, X> {
    fn drop(&mut self) { println!("dropped here"); }
}

impl X {
    // error will gone if uncomment
    // fn get_iter(&self) -> Option<std::slice::Iter<'_, u32>> { Some(self.0.iter()) }
    fn get_iter(&self) -> Option<DropIter<'_, u32>> { Some(DropIter(self.0.iter())) }

    fn push(&mut self, x: u32) {
        self.0.push(x);
    }
}

fn main() {
    let mut tmp = X::default();
    tmp.push(1);

    println!("before if let");
    match tmp.get_iter() { // `xx` holds the reference to `tmp`
        Some(xx) => {
            println!("before then for loop");
            for t in xx {
                println!("{:?}", t);
            }

            // but here `xx` is dropped
            println!("end of then")
        }
        xx @ None => {
            drop(xx); // this tells borrow-checker to release the borrow of tmp
            tmp.push(1);
            println!("end of else")
        }
    }
    println!("after if let");
}

[pnkfelix]

and likewise here is that same workaround being applied to the original example (play):

#![feature(nll)]

#[derive(Default)]
struct X(Vec<u32>);

impl X {
    // error will gone if uncomment
    // fn get_iter(&self) -> Option<std::slice::Iter<'_, u32>> {
    fn get_iter(&self) -> Option<impl Iterator<Item = &u32>> {
        Some(self.0.iter())
    }
    
    fn push(&mut self, x: u32) {
        self.0.push(x);
    }
}

fn main() {
    let mut tmp = X::default();

    match tmp.get_iter() { // `xx` holds the reference to `tmp`
        Some(xx) => {
            for t in xx {
                println!("{:?}", t);
            }
        }
        xx @ None => {
            drop(xx); // expliciltly drop `None` so borrow-checker releases tmp
            tmp.push(1);
        }
    };
}

[pnkfelix]

(In case its not clear, the compiler wants to keep the borrows of the Option<impl Iterator> alive until its drop point because any potential destructor attached to the impl Iterator might do something with those borrows. See #53450 (comment) for an example of such interaction on a different example where it is a valid concern for the compiler to have.)

---

Having said all that, I vaguely recall some discussion (perhaps elsewhere in this github repo) where people were suggesting that we could be smarter and have the compiler figure out that in cases like Option<T>, the type variable T is only relevant to the Option::Some variant; if a match (or if let, etc) gets into the Option::None case, then the compiler hypothetically could soundly conclude that there are no longer any T's as part of the value that was matched upon.

I haven't yet been able to find a reference for that discussion, but I'd like to link it here when/if I do...

• Update this is the discussion I was thinking of: [nll] attr-0.1.0 regression #53569 (comment). Namely, the idea that we can know that the drop of Result<ThingWithDtor, ThingWithoutDtor>::Err does not actually have a destructor.

But apart from that, I think that the above comments I wrote serve as an explanation for the bug.

[pnkfelix]

It might also help if the compiler actually said in its diagnostic that the compiler's reasoning includes the fact that it thinks that the drop is relevant.

We actually do print out such information if we have a named local to refer to, like in the following (play):

#![feature(nll)]

#[derive(Default)]
struct X(Vec<u32>);

impl X {
    // error will gone if uncomment
    // fn get_iter(&self) -> Option<std::slice::Iter<'_, u32>> {
    fn get_iter(&self) -> Option<impl Iterator<Item = &u32>> {
        Some(self.0.iter())
    }
    
    fn push(&mut self, x: u32) {
        self.0.push(x);
    }
}

fn main() {
    let mut tmp = X::default();

    match tmp.get_iter() { // `xx` holds the reference to `tmp`
        Some(xx) => {
            for t in xx {
                println!("{:?}", t);
            }
        }
        _yy @ None => {
            tmp.push(1);
        }
        
    };
}

where the compiler prints the following diagnostics:

error[E0502]: cannot borrow `tmp` as mutable because it is also borrowed as immutable
  --> src/main.rs:28:13
   |
21 |     match tmp.get_iter() { // `xx` holds the reference to `tmp`
   |           --- immutable borrow occurs here
...
28 |             tmp.push(1);
   |             ^^^^^^^^^^^ mutable borrow occurs here
...
31 |     };
   |     - borrow later used here, when `_yy` is dropped

So maybe we should consider doing the same for anonymous temporaries in cases like this...? (Is there a bug open for that?)

---

Incidentally, I'm a little surprise that the span points to line 31 (the end of the whole match) for the drop point of _yy. I would have expected it to point to line 29, the end of that one match arm. (I do not think this is an observable semantic difference between the two points being printed, but in terms of UX it seesm much clearer to act like the drop happens as part of the arm where _yy itself gets bound.)

[pnkfelix]

Taking off of the RC2 milestone since I believe NLL is behaving in the manner we expect here (see #53528 (comment)), but also tagging as NLL-deferred in light of the suggestion I posed about future enhancements to our handling of enum variants that don't reference type parameters (see #53528 (comment) )

[pnkfelix]

Actually, lets nominate this and talk about it with the NLL team; namely, this is the only follow-up question:

Having said all that, I vaguely recall some discussion (perhaps elsewhere in this github repo) where people were suggesting that we could be smarter and have the compiler figure out that in cases like Option<T>, the type variable T is only relevant to the Option::Some variant; if a match (or if let, etc) gets into the Option::None case, then the compiler hypothetically could soundly conclude that there are no longer any T's as part of the value that was matched upon.

and if we are interested in investigating such an extension to NLL, we should open a dedicated issue to it rather than piggy-backing.

(Note that this is not nominated for T-compiler. The I-nominated label should be removed after the next NLL meeting.)

[pnkfelix]

(The aforementioned discussion of variant-sensitive-drop-analysis-extension was here: #53569 (comment))

[pnkfelix]

but now that i've delved more deeply into #53569, I think it might be covering a dual problem...?

Namely, the idea on #53569 is about dealing about a borrow into variant A when the sole Drop impl is attached to variant B.

But this bug (#53528) is currently musing about dealing a drop of variant B where B cannot possibly carry any state associated with the borrows taken from variant A.

(In other words, these may not really be related at all...)

[pnkfelix]

Discussed at WG-nll meeting. We collectively decided that this is currently a "wont fix", but its a very interesting problem and a possible avenue for future extensions to Rust's static analysis.

[nikomatsakis]

I'd like to add my summary of what is going on. Specifically, the problem is that the temporary value created by the call to get_iter is a Option<impl Iterator>, and we are not able to see that -- by the time we get to the drop -- the only time that the value will not already have been dropped is when it is None, and hence that the drop is a no-op. It's plausible that we can track this sort of information, but it's not something we had thought hard about before.