Non-lexical borrow scopes and better treatment of nested method calls

[pnkfelix]

In general, it can be useful to have support for borrows that aren't tied to lexical scopes.

Related links:

• Nested method calls with &mut receivers result in borrowck errors (Nested method calls with &mut receivers result in borrowck errors rust#6268)
  • Internals thread: "Accepting nested method calls with an &mut self receiver"
• Borrow scopes should not always be lexical (borrow scopes should not always be lexical rust#6393)
• Single-entry, multiple-exit regions for borrows (RFC: Single-entry / multiple-exit regions for borrows #396)

UPDATE: The relevant RFCs have been accepted. See rust-lang/rust#43234 to track implementation progress here.

[barosl]

@mike-marcacci pointed out that the single-entry, multiple-exit regions issue also applies to the if let struct. While a code like

if let Some(val) = map.get_mut(&id) {
   /* ... */
} else {
   map.insert(id, new_val);
}

seems "innocent", it is actually just a syntax sugar for the match block, so the borrow lasts until the end of the else block. This particular case could be improved, or at least diagnostics could be, but I'm not sure fixing the specific point without introducing a general solution is a good idea.

[flavius]

What's the state of this feature? Any new plans and/or changes with this?

[steveklabnik]

@flavius basically, the HIR/MIR work needs to be completed first.

[ebiggers]

I would like to see this implemented. I believe I ran into this with the following code which is descending a prefix tree and inserting new nodes:

struct TrieNode {
    bitmask: u32,
    terminal: bool,
    children: Vec<Box<TrieNode>>,
}

impl TrieNode {
    fn new() -> TrieNode {
        TrieNode {
            bitmask: 0,
            terminal: false,
            children: Vec::with_capacity(2),
        }
    }

    fn insert(&mut self, word: &Vec<u8>) {
        let mut node = self;
        for b in word {
            let bit = 1u32 << b;
            let index = (node.bitmask & (bit - 1)).count_ones() as usize;
            if (node.bitmask & bit) == 0 {
                node.children.insert(index, Box::new(TrieNode::new()));
                node.bitmask |= bit;
            }
            node = &mut node.children[index];
        }
        node.terminal = true;
    }
}

The problematic line is this one:

node = &mut node.children[index];

This causes the Rust compiler to spew a page of errors:

test.rs:22:17: 22:30 error: cannot borrow `node.children` as mutable more than once at a time [E0499]
test.rs:22                 node.children.insert(index, Box::new(TrieNode::new()));
               ^~~~~~~~~~~~~
test.rs:22:17: 22:30 help: run `rustc --explain E0499` to see a detailed explanation
test.rs:25:25: 25:38 note: previous borrow of `node.children` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `node.children` until the borrow ends
test.rs:25             node = &mut node.children[index];
                   ^~~~~~~~~~~~~
test.rs:28:6: 28:6 note: previous borrow ends here
test.rs:16     fn insert(&mut self, word: &Vec<u8>) {
...
test.rs:28     }
           ^
test.rs:25:13: 25:45 error: cannot assign to `node` because it is borrowed [E0506]
test.rs:25             node = &mut node.children[index];
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
test.rs:25:25: 25:38 note: borrow of `node` occurs here
test.rs:25             node = &mut node.children[index];
                   ^~~~~~~~~~~~~
test.rs:25:25: 25:38 error: cannot borrow `node.children` as mutable more than once at a time [E0499]
test.rs:25             node = &mut node.children[index];
                   ^~~~~~~~~~~~~
test.rs:25:25: 25:38 help: run `rustc --explain E0499` to see a detailed explanation
test.rs:25:25: 25:38 note: previous borrow of `node.children` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `node.children` until the borrow ends
test.rs:25             node = &mut node.children[index];
                   ^~~~~~~~~~~~~
test.rs:28:6: 28:6 note: previous borrow ends here
test.rs:16     fn insert(&mut self, word: &Vec<u8>) {
...
test.rs:28     }

This can be "fixed" by replacing the line with this:

let tmp = node;
node = &mut tmp.children[index];

In my opinion this adds no value and simply serves as a means of appeasing the borrow checker. The program is correct either way; it seems to be purely a limitation of the borrow checker that it cannot determine this and the programmer has to explicitly add a temporary variable.

I understand there may be concern about making the borrow checker more complicated. However, I feel that usability takes precedence here. It's no secret that writing code the Rust compiler can prove is "safe" is one of the largest barriers to using Rust. Any change that makes the compiler smarter and able to correctly recognize more safe code as safe is, in my opinion, an improvement (at least, provided that it continues to follow well-defined rules).

[arielb1]

@ebiggers

Your issue here is reborrow vs. move, which is distinct from non-lexical borrows. You can also move node using &mut {node}.children[index] (see https://www.reddit.com/r/rust/comments/46rii1/when_to_borrow_move_or_copy/).

[ehiggs]

Is this related to places where matching an option won't compile using as_mut but can be fixed up by using Some(ref mut ...)?

e.g. code like this can fail because foo is still borrowed:

match foo.as_mut() {
    Some(x) => x.bar(), // fn bar(&mut self)
    None => foo = Some(Foo::new(7))
} 

It can be worked around like

match foo {
    Some(ref mut x) => x.bar(),
    None => foo = Some(Foo::new(7))
}

[arielb1]

That's a different issue - non-lexical borrows.

[ehiggs]

@arielb1, ok. Is there an issue for that? It seems like the two chunks of code I pasted should be semantically equivalent. @bluss on IRC pointed me to this one suggesting that it was similar to the issue I faced.

[glaebhoerl]

@arielb1 The title of this issue is "Non-lexical borrow scopes and"...

[bluss]

@ehiggs I wouldn't call that a work around, it's the idiomatic solution.

[arielb1]

@glaebhoerl

Oops wrong RFC - I thought this was copy-vs-move.

[aidanhs]

Think this is related:

fn main() {
    let mut a = 1;
    let c;
    {
        let b = &mut a;
        c = &*b;
    }
    let d = &a;
}

cannot borrow `a` as immutable because it is also borrowed as mutable

[dbrgn]

@aidanhs no, I think that is correct. If you visualize the implicit scopes:

fn main() {
  let mut a = 1;
  { 
    let c;
    {
      let b = &mut a;
      {
        c = &*b;
      }
    }
    let d = &a;
  }
}

...then you can see that you're trying to borrow a while it's still borrowed mutably by b.

While borrowing a mutable reference to a value, that refrence is the only way to access that value at all.

[ebkalderon]

Just curious, what is the current status of this issue? Will work on non-lexical borrows resume now that MIR has landed on Nightly?

[oli-obk]

Not sure if that was intentional or not, but beta and nightly allow the following piece of code to work (not panic at runtime):

use std::cell::RefCell;

fn main() {
    let mut data = RefCell::new(None);
    let inner = if data.borrow().is_none() {
        let d = 1337;
        *data.borrow_mut() = Some(d);
        d
    } else {
        data.borrow().unwrap()
    };
}

(found here: http://stackoverflow.com/questions/40482981/if-condition-remains-borrowed-in-body )

[eddyb]

It was intentional, the previous behavior was a long-standing bug that was only partially fixed before.

[radix]

Can this ticket be closed? I see that all three of the linked issues in the description are closed. If it still needs to be open, is it also still appropriate to have the "postponed" label?

[istankovic]

@radix The issue #29775 was linked to this one and closed at some point, however, I've just checked and it is still relevant. So if this one is to be closed, I suggest to reopen #29775 since it is stil relevant and represents a very basic use case.

[steveklabnik]

Can this ticket be closed?

Why would we close it?

I see that all three of the linked issues in the description are closed.

That's because they're duplicates of this one.

If it still needs to be open, is it also still appropriate to have the "postponed" label?

Yes, as generally this means "we considered it but decided that it's not the right time yet." This is still true, as porting the borrowck to MIR is still a blocker.

[radix]

@steveklabnik I apologize. I was just unclear on the status since recent comments seemed to indicate it, or some parts of it, had been fixed. I also didn't realize that the links in the description were duplicates, I assumed they were dependents. My error. I should have worded my message more carefully. I didn't mean to say that I think it should be closed, just that I was curious about its status.

Thank you for the information.

@istankovic I'm not sure which #29775 you are referring to, as I can't find a reference to that number on this page.

[istankovic]

@radix sorry, I meant rust-lang/rust#29975

[steveklabnik]

@radix it's all good! This is a very long-running and complicated issue, it's very easy to have done that. 😄

[nikomatsakis]

A rather long write-up about nested method calls specifically:

https://internals.rust-lang.org/t/accepting-nested-method-calls-with-an-mut-self-receiver/4588

[SimonSapin]

porting the borrowck to MIR is still a blocker.

What’s the status on this?

---

As far as I can tell, borrows being lexical means not only that some programs need to be more verbose, but also that some programs are impossible (at least with the desired API/characteristics). For example, I just tried to write something like this (reduced here):

pub enum Token {
    Whitespace,
    Ident(String),
    Number(i32),
}

pub struct Parser {
    /* ... */
}

impl Parser {
    pub fn advance_without_skipping_whitespace(&mut self) -> &Token {
        unimplemented!()
    }

    pub fn advance(&mut self) -> &Token {
        loop {
            match self.advance_without_skipping_whitespace() {
                &Token::Whitespace => {}
                result => return result
            }
        }
    }
}

Playpen

… and got this error message:

error[E0499]: cannot borrow `*self` as mutable more than once at a time
  --> <anon>:18:19
   |
18 |             match self.advance_without_skipping_whitespace() {
   |                   ^^^^
   |                   |
   |                   second mutable borrow occurs here
   |                   first mutable borrow occurs here
...
23 |     }
   |     - first borrow ends here

error: aborting due to previous error

The problem is the "first" borrow lasting for the whole function rather than just one iteration of the loop. I think that’s because the borrowed value is (in some code paths) returned, and borrow are lexical? I can’t find a way to rewrite this that compiles in today’s Rust, even tail recursion has the same problem as a loop.

[SimonSapin]

some programs are impossible

That may have been a bit over-dramatic, I found a work-around. (Not returning the result of advance_without_skipping_whitespace(), using break instead of return, and than returning self.current_token() outside the loop.)

But the same kind of issues happen all the time when porting existing parsing code to this new API. Enough that this approach is not viable, I may have to do somewhat-expensive cloning everywhere.

[pnkfelix]

porting the borrowck to MIR is still a blocker.

What’s the status on this?

It is in-progress. Some steps have recently landed, but its not 100% working yet.

[nikomatsakis]

I think we can basically close this in favor of rust-lang/rust#43234