Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

borrow scopes should not always be lexical #6393

Closed
metajack opened this issue May 10, 2013 · 44 comments

Comments

Projects
None yet
@metajack
Copy link
Contributor

commented May 10, 2013

If you borrow immutably in an if test, the borrow lasts for the whole if expression. This means that mutable borrows in the clauses will cause the borrow checker to fail.

This can also happen when borrowing in the match expression, and needing a mutable borrow in one of the arms.

See here for an example where the if borrows boxes, which causes the nearest upwards @mut to freeze. Then remove_child() which needs to borrow mutably conflicts.

https://github.com/mozilla/servo/blob/master/src/servo/layout/box_builder.rs#L387-L411

Updated example from @Wyverald

fn main() {
    let mut vec = vec!();
    
    match vec.first() {
        None => vec.push(5),
        Some(v) => unreachable!(),
    }
}

@ghost ghost assigned nikomatsakis May 10, 2013

@metajack

This comment has been minimized.

Copy link
Contributor Author

commented May 10, 2013

nominating for production ready

@nikomatsakis

This comment has been minimized.

Copy link
Contributor

commented May 10, 2013

I would call this either well-defined or backwards-compat.

@nikomatsakis

This comment has been minimized.

@metajack

This comment has been minimized.

Copy link
Contributor Author

commented May 16, 2013

The code got reorganized, but here is the specific appeasement of the borrow checker i had to do:

metajack/servo@5324cab

metajack/servo@7234635

@nikomatsakis

This comment has been minimized.

Copy link
Contributor

commented May 20, 2013

After some discussion, it's clear that the real problem here is that the borrow checker makes no effort to track aliases, but rather always relies on the region system to determine when a borrow goes out of scope. I am reluctant to change this, at least not in the short term, because there are a number of other outstanding issues I'd like to address first and any changes would be a significant modification to the borrow checker. See issue #6613 for another related example and a somewhat detailed explanation.

@cscott

This comment has been minimized.

Copy link

commented May 20, 2013

I wonder if we could improve the error messages to make it more clear what's going on? Lexical scopes are relatively easy to understand, but in the examples of this issue that I've stumbled across it was by no means obvious what was going on.

@graydon

This comment has been minimized.

Copy link
Contributor

commented May 23, 2013

just a bug, removing milestone/nomination.

@graydon

This comment has been minimized.

Copy link
Contributor

commented May 23, 2013

accepted for far future milestone

@cmr

This comment has been minimized.

Copy link
Member

commented Jul 21, 2013

triage bump

@nikomatsakis

This comment has been minimized.

Copy link
Contributor

commented Sep 12, 2013

I've had some thoughts about the best way to fix this. My basic plan is that we would have a notion of when a value "escapes". It will take some work to formalize that notion. Basically, when a borrowed pointer is created, we will then track whether it has escaped. When the pointer is dead, if it is has not escaped, this can be considered to kill the loan. This basic idea covers cases like "let p = &...; use-p-a-bit-but-never-again; expect-loan-to-be-expired-here;" Part of the analysis will be a rule that indicates when a return value that contains a borrowed pointer can be considered not to have escaped yet. This would cover cases like "match table.find(...) { ... None => { expect-table-not-to-be-loaned-here; } }"

The most interesting part of all this is the escaping rules, of course. I think that the rules would have to take into account the formal definition of the function, and in particular to take advantage of the knowledge bound lifetimes give us. For example, most escape analyses would consider a pointer p to escape if they see a call like foo(p). But we would not necessarily have to do so. If the function were declared as:

fn foo<'a>(x: &'a T) { ... }

then in fact we know that foo does not hold on to p for any longer than the lifetime a. However, a function like bar would have to be considered as escaping:

fn bar<'a>(x: &'a T, y: &mut &'a T)

So presumably the escaping rules would have to consider whether the bound lifetime appeared in a mutable location or not. This is effectively a form of type-based alias analysis. Similar reasoning I think applies to function return values. Hence find ought to be considered to return a non-escaped result:

fn find<'a>(&'a self, k: &K) -> Option<&'a V>

The reason here is that because 'a is bound on find, it cannot appear in the Self or K type parameters, and hence we know it can't be stored in those, and it does not appear in any mutable locations. (Note that we can apply the same inference algorithm as is used today and which will be used as part of the fix for #3598 to tell us whether lifetimes appears in a mutable location)

Another way to think about this is not that the loan is expired early, but rather that the scope of a loan begins (typically) as tied to the borrowed variable and not the full lifetime, and is only promoted to the full lifetime when the variable escapes.

Reborrows are a slight complication, but they can be handled in various ways. A reborrow is when you borrow the contents of a borrowed pointer -- they happen all the time because the compiler inserts them automatically into almost every method call. Consider a borowed pointer let p = &v and a reborrow like let q = &*p. It'd be nice if when q was dead, you could use p again -- and if both p and q were dead, you could use v again (presuming neither p nor q escapes). The complication here is that if q escapes, p must be considered escaped up until the lifetime of q expires. But I think that this falls out somewhat naturally from how we handle it today: that is, the compiler notes that q has borrowed p for (initially) the lifetime "q" (that is, of the variable itself) and if q should escape, that would be promoted to the full lexical lifetime. I guess the tricky part is in the dataflow, knowing where to insert the kills -- we can't insert the kill for p right away when p goes dead if it is reborrowed. Oh well, I'll not waste more time on this, it seems do-able, and at worst there are simpler solutions that would be adequate for common situations (e.g., consider p to have escaped for the full lifetime of q, regardless of whether the q loan escapes or not).

Anyway, more thought is warranted, but I'm starting to see how this could work. I'm still reluctant to embark on any extensions like this until #2202 and #8624 are fixed, those being the two known problems with borrowck. I'd also like to have more progress on a soundness proof before we go about extending the system. The other extension that is on the timeline is #6268.

@toffaletti

This comment has been minimized.

Copy link
Contributor

commented Sep 30, 2013

I believe I've run into this bug. My use-case and work-around attempts:

https://gist.github.com/toffaletti/6770126

@ezyang

This comment has been minimized.

Copy link
Contributor

commented Dec 16, 2013

Here's another example of this bug (I think):

use std::util;

enum List<T> {
    Cons(T, ~List<T>),
    Nil
}

fn find_mut<'a,T>(prev: &'a mut ~List<T>, pred: |&T| -> bool) -> Option<&'a mut ~List<T>> {
    match prev {
        &~Cons(ref x, _) if pred(x) => {}, // NB: can't return Some(prev) here
        &~Cons(_, ref mut rs) => return find_mut(rs, pred),
        &~Nil => return None
    };
    return Some(prev)
}

I'd like to write:

fn find_mut<'a,T>(prev: &'a mut ~List<T>, pred: |&T| -> bool) -> Option<&'a mut ~List<T>> {
    match prev {
        &~Cons(ref x, _) if pred(x) => return Some(prev),
        &~Cons(_, ref mut rs) => return find_mut(rs, pred),
        &~Nil => return None
    }
}

reasoning that the x borrow goes dead as soon as we finish evaluating the predicate, but of course, the borrow extends for the entire match right now.

@nikomatsakis

This comment has been minimized.

Copy link
Contributor

commented Feb 10, 2014

I've had more thoughts about how to code this up. My basic plan is that for each loan there would be two bits: an escaped version and a non-escaped version. Initially we add the non-escaped version. When a reference escapes, we add the escaped bits. When a variable (or temporary, etc) goes dead, we kill the non-escaped bits -- but leave the escaped bits (if set) untouched. I believe this covers all major examples.

@flaper87

This comment has been minimized.

Copy link
Contributor

commented Feb 10, 2014

@arjantop

This comment has been minimized.

Copy link
Contributor

commented Feb 13, 2014

Does this issue cover this?

use std::io::{MemReader, EndOfFile, IoResult};

fn read_block<'a>(r: &mut Reader, buf: &'a mut [u8]) -> IoResult<&'a [u8]> {
    match r.read(buf) {
        Ok(len) => Ok(buf.slice_to(len)),
        Err(err) => {
            if err.kind == EndOfFile {
                Ok(buf.slice_to(0))
            } else {
                Err(err)
            }
        }
    }
}

fn main() {
    let mut buf = [0u8, ..2];
    let mut reader = MemReader::new(~[67u8, ..10]);
    let mut block = read_block(&mut reader, buf);
    loop {
        //process block
        block = read_block(&mut reader, buf); //error here
}
@lilyball

This comment has been minimized.

Copy link
Contributor

commented Feb 25, 2014

cc me

nikomatsakis referenced this issue in nrc/rust Mar 18, 2014

Allow inheritance between structs.
No subtyping, no interaction with traits. Partially addresses rust-lang#9912.
@nikomatsakis

This comment has been minimized.

Copy link
Contributor

commented Apr 15, 2014

Good examples in #9113

@pnkfelix

This comment has been minimized.

Copy link
Member

commented Apr 24, 2014

cc me

@SergioBenitez

This comment has been minimized.

Copy link
Contributor

commented May 20, 2014

I could be mistaken, but the following code seems to be hitting this bug as well:

struct MyThing<'r> {
  int_ref: &'r int,
  val: int
}

impl<'r> MyThing<'r> {
  fn new(int_ref: &'r int, val: int) -> MyThing<'r> {
    MyThing {
      int_ref: int_ref,
      val: val
    }
  }

  fn set_val(&'r mut self, val: int) {
    self.val = val;
  }
}


fn main() {
  let to_ref = 10;
  let mut thing = MyThing::new(&to_ref, 30);
  thing.set_val(50);

  println!("{}", thing.val);
}

Ideally, the mutable borrow caused by calling set_val would end as soon as the function returns. Note that removing the 'int_ref' field from the struct (and associated code) causes the issue to go away. The behavior is inconsistent.

@userxfce

This comment has been minimized.

Copy link

commented Apr 5, 2015

For the case: "let p = &...; use-p-a-bit-but-never-again; expect-loan-to-be-expired-here;" I would find acceptable for now a kill(p) instruction to manually declare end of scope for that borrow. Later versions could simply ignore this instruction if it is not needed or flag it as an error if re-use of p is detected after it.

@userxfce

This comment has been minimized.

Copy link

commented Apr 5, 2015

/* (wanted) */
/*
fn main() {

    let mut x = 10;

    let y = &mut x;

    println!("x={}, y={}", x, *y);

    *y = 11;

    println!("x={}, y={}", x, *y);
}
*/

/* had to */
fn main() {

    let mut x = 10;
    {
        let y = &x;

        println!("x={}, y={}", x, *y);
    }

    {
        let y = &mut x;

        *y = 11;
    }

    let y = &x;

    println!("x={}, y={}", x, *y);
}
@seanmonstar

This comment has been minimized.

Copy link
Contributor

commented Apr 5, 2015

There's the drop() method in the prelude that does that. But doesn't seem
to help with mutable borrows.

On Sun, Apr 5, 2015, 1:41 PM axeoth notifications@github.com wrote:

/* (wanted) _//_fn main() { let mut x = 10; let y = &mut x; println!("x={}, y={}", x, y); *y = 11; println!("x={}, y={}", x, *y);}/
/* had to */fn main() {

let mut x = 10;
{
    let y = &x;

    println!("x={}, y={}", x, *y);
}

{
    let y = &mut x;

    *y = 11;
}

let y = &x;

println!("x={}, y={}", x, *y);

}


Reply to this email directly or view it on GitHub
#6393 (comment).

@nikomatsakis

This comment has been minimized.

Copy link
Contributor

commented Apr 16, 2015

Closing in favor of rust-lang/rfcs#811

@vitiral

This comment has been minimized.

Copy link
Contributor

commented Sep 2, 2016

@metajack the link for your original code is a 404. Can you include it inline for people reading this bug?

@metajack

This comment has been minimized.

Copy link
Contributor Author

commented Sep 2, 2016

@metajack

This comment has been minimized.

Copy link
Contributor Author

commented Sep 2, 2016

Or rather, that's the workaround I used when I filed this bug. The original code before that change seems to be this:
https://github.com/servo/servo/blob/7267f806a7817e48b0ac0c9c4aa23a8a0d288b03/src/servo/layout/box_builder.rs#L387-L399

I'm not sure how relevant these specific examples are now since they were pre-Rust 1.0.

@vitiral

This comment has been minimized.

Copy link
Contributor

commented Sep 2, 2016

@metajack it would be great to have an ultra simple (post 1.0) example in the top of this issue. This issue is now part of rust-lang/rfcs#811

@jethrogb

This comment has been minimized.

Copy link
Contributor

commented Sep 2, 2016

fn main() {
    let mut nums=vec![10i,11,12,13];
    *nums.get_mut(nums.len()-2)=2;
}
@metajack

This comment has been minimized.

Copy link
Contributor Author

commented Sep 2, 2016

I think what I was complaining about was something like this:
https://is.gd/yfxUfw

That particular case appears to work now.

@Wyverald

This comment has been minimized.

Copy link

commented Jan 11, 2017

@vitiral An example in today's Rust that I believe applies:

fn main() {
    let mut vec = vec!();
    
    match vec.first() {
        None => vec.push(5),
        Some(v) => unreachable!(),
    }
}

The None arm fails borrowck.

Curiously, if you don't try to capture int in the Some arm (ie. use Some(_)), it compiles.

@vitiral

This comment has been minimized.

Copy link
Contributor

commented Jan 11, 2017

@wyverland oh ya, I hit that just yesterday, pretty annoying.

@metajack can you edit the first post to include that example?

@nikomatsakis

This comment has been minimized.

Copy link
Contributor

commented Dec 21, 2017

It's not yet hit nightly, but I just want to say that this now compiles:

#![feature(nll)]

fn main() {
    let mut vec = vec!();

    match vec.first() {
        None => vec.push(5),
        Some(v) => unreachable!(),
    }
}

nivkner added a commit to nivkner/rust that referenced this issue Feb 8, 2018

nivkner added a commit to nivkner/rust that referenced this issue Feb 16, 2018

nivkner added a commit to nivkner/rust that referenced this issue Mar 17, 2018

nivkner added a commit to nivkner/rust that referenced this issue Mar 17, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.