Accepting nested method calls with an `&mut self` receiver


#1

I think the time has come to settle on a fix for the “nested method call” problem. This is a pretty long post talking about it and laying out various bits of background material that I have been collecting to form a complete picture. You may want to skip down to the “Proposal 1” and “Proposal 2” sections toward the end, and then work your way backwards.

Background on the problem

I distinctly recall when this issue started. It was Feb of 2013, as we adopted the so-called IMHTWAMA rules. These new rules basically introduced what is today just “the borrowing system”, but they did have the side-effect that nested method calls like vec.push(vec.len()) often had to be rewritten to introduce a temporary:

let tmp = vec.len();
vec.push(tmp);

Amusingly, I recall that at the time I intended to fix this error “in a few days, when I get chance to whip up a PR”. So… almost four years later… it’s probably time.

That said, you may wonder “why now?” I have two motivations for pursuing this now. The first is that this is a longstanding ergonomic annoyance, and as part of the 2017 Roadmap we aim to eliminate as many of those as we can. The second is that there was a recent bug found in the borrow checker, and in fixing this bug, I found that it exacerbates this problem. Basically we used to incorrectly accept a lot of code that ought to require a temporary to be introduced – but of course the fact that we require this temporary is itself a kind of bug. Seems to me that we can make lemons out of lemonade here if we fix #38899 while also eliminating the need for temporaries.

That said, eliminating the need for temporaries is actually much more subtle than it sounds! I want to talk about the issue here as well as some of the proposals that have been floated for fixing it. I’m sure there are more I’m not familiar with.

The problem here is that vec.push(vec.len()) is effectively desugared as follows:

let arg0 = &mut vec; // autoref of `vec`
let arg1 = vec.len(); // prep the first argument
Vec::push(arg0, arg1); // actual call

As you can see, we first take a mutable reference to vec for arg0. This “locks” vec from being accessed in any other way: but then we try to access it again to call vec.len(). Hence the error.

How can this go wrong?

When you see the code desugared in that way, it should not surprise you that there is in fact a real danger here for code to crash if we just “turned off” this check (if we even could do such a thing). For example, consider this rather artificial Rust program:

let mut v: Vec<String> = vec![format!("Hello, ")];
v[0].push_str({ v.push(format!("foo")); "World!" });
//              ^^^^^^^^^^^^^^^^^^^^^^ sneaky attempt to mutate `v`

The problem is that, when we desugar this, we get:

let mut v: Vec<String> = vec![format!("Hello, ")];
let arg0: &mut String = &mut v[0]; // creates a reference into `v`'s current data array
let arg1: &str = {
    v.push(format!("foo")); // potentially frees `v`'s data array
    "World!"
};
String::push_str(arg0, arg1)

So, to put it another way, as we evaluate the arguments, we are creating references and pointers that we will give to the final function. But evaluating arguments can also have arbitrary side-effects, which might invalidate the references that we prepared for earlier arguments. So we have to be sure to rule that out.

In fact, even when the receiver is just a local variable (e.g., vec.push(vec.len())) we have to be wary. We wouldn’t want it to be possible to give ownership of the receiver away in one of the arguments: vec.push({ send_to_another_thread(vec); ... }). That should still be an error of course.

(Naturally, these complex arguments that are blocks look really artificial, but keep in mind that most of the time when this occurs in practice, the argument is a method or fn call, and that could in principle have arbitrary side-effects.)

Preventing arguments from taking &mut borrows

Speaking a bit more generally, we might also want to prevent people from mutating things in surprising ways, even if it doesn’t strictly prevent a memory safety violation. This happens today as a side-effect of the current overly strict rules, but it might be something we want to preserve. I am not sure about this, though.

Here is an example of the kind of surprising side-effects that I am talking about:

// pretend you could define an inherent method on integers
// for a second, just to keep code snippet simple
impl i32 {
    fn add(&self, v: i32) -> i32 {
        *self + v
    }
    
    fn increment(&mut self, v: i32) -> i32 {
        *self += v;
        *self // returns new value
    }
}

fn foo() {
    let mut x = 0;
    let y = x.add(x.increment(1)); // what result do you expect from this?
    println!("{}", y);
}

If we allowed this code to run, presumably it would print 2. That is, we would evaluate x.increment(1), which updates x to be 1 and returns 1, and then we would call i32::add() with a reference to x. When add reads from that ref (*self) it sees 1, so it returns 2. But that’s not entirely obvious from reading the code. One might also expect it to print 1 – i.e., if add were defined as fn(self) instead of fn(&self), one might expect to first read x (getting 0) then call x.increment(1) (yielding 1) and hence invoke i32::add(0, 1).

One of the proposals I will layout would keep examples like this illegal. Effectively it would forbid an argument from taking a mutable borrow on the receiver, while still permitting shared borrows. Hence vec.push(vec.len()) would type-check, but the code above would not. Others would permit both versions.

It is not entirely obvious to me that the code above should be illegal. Sometimes an &mut self borrow is fine. As an example, the inference engine in Rust (and most things) is based on Tarjan’s union-find algorithm. Part of how union-find works is by performing “path compression”, which means that even when you are doing externally side-effect-free queries, you are actually potentially mutating the data structure. Hence you might have code like set.union(set.find(a), set.find(b)) – all of these operations require an &mut self borrow on set, and yet this code seems perfectly reasonable to me. But OTOH forcing one to use temporaries in such cases seems also OK and helps expose the side-effects.

One can also do kind of crazy things without method calls. Though actually they work out closer to the by-value semantics. For example, one could write this:

fn main() {
    let mut x = 0;
    x += { x += 1; 1 };
    println!("{}", x); // prints 2
}

As you can see, here we start out with x=0. Then we evaluate the argument, yielding a value of 1 and a new value for x (1). Then we execute x += 1 which hence yields 2. (Using overloaded assignment yields the same result, which seems related, but I want to hold off on chasing that thread for a bit.) Note that hence x += <e> is distinct from x = x + <v> if <v> mutates x. Using the x = x + <v> form prints 1, just as the fn(self) version of the code above would do.

Borrowing for the future

This next section describes one way that I have thought about this problem in the past. Currently, when you borrow some data, that borrow takes effect immediately, starting at the point of borrow. One could imagine allowing borrows to take effect at some later point. This is kind of a generalization of non-lexical-lifetimes. As it happens, I don’t think the time is ripe to take this step: we’re still working out what NLL should mean exactly! But it’s an interesting thought experiment and reference point, so I wanted to talk about it.

Let me try to describe what I mean by example. Consider the naively desugared version of vec.push(vec.len()), but with explicit labels for the lifetime of every little part (and also for the lifetime of a borrow):

'call: {
  let v: &'call mut Vec<usize>;
  let l: usize;
  'eval_args: {
    'eval_v: { v = &'call mut vec; }
    'eval_l: { l = vec.len(); }
  }
  'invoke: { Vec::push(v, l); }
}

When I write this out, we can kind of see the problem. When evaluating v = &'call mut v, we take a borrow that lasts until the end of 'call. This naturally includes 'eval_l, which comes on the next line, and hence calling vec.len() is illegal. But we know that we won’t be using v until the actual invocation of Vec::push() at the end – what if we could borrow v for that time instead? Something like this: v = &'invoke mut v. This would make the type of v be &'invoke mut Vec<usize> (which would not include the point where v is declared). In that case, vec is not borrowed yet when we try to call vec.len(), and so we might imagine the code is accepted.

Still, as discussed earlier, when you borrow a path “for the future”, you would still need some restrictions on what can be done with that path. The idea is that we are evaluating the path to a pointer right then and there, so we need to be sure that this pointer remains valid. We wouldn’t want people to send vec to another thread or something.

I haven’t worked out precisely what these rules look like. Presumably the borrow checker would track not only the loans that have taken full effect but also the “future loans” at any given point. For “future loans”, we would permit more operations, but we would still permit some things. At minimum, we must forbid anything that would invalidate the reference, but we might also get stricter, and try to forbid things that would mutate the data that is referred to (while permitting shared references).

In the next section, I’m going to describe two proposals for accepting vec.push(vec.len()) that operate by tweaking how we desugar method calls, intead of changing anything fundamental about the type system. However, I believe both of them are forwards compatible with adopting (some variant of) this more general model in the future. Moreover, this more general model is the only one that would accept “naively desugared” method calls in precisely the same way as using . notation.

Ultimately, if we want to accept vec.push(vec.len()), I believe we have to accept either a more complex desugaring or a more complex type system. It seems to me that the former is a better choice at the time being, but it’d be nice to preserve the way forward for the latter if we should so choose.

Proposal 1: A desugaring-based approach

One way to solve this problem is to modify the desugaring of method calls. To explain it, we first need a notion of “stable paths”. These are basically lvalues where the address to which they evaluate cannot be changed except by moves. A simple example of a stable path is a local variable vec or a field of a local variable. Something like *x where x: Box<i32> is not a stable path: x can be reassigned, which would cause *x to change. Anyway we have to work out the precise definition here; I’m going to be restrictive and limit it to “local variables plus GEP” for now.

So, the first proposal is to alter desugaring of method calls by saying that, if the receiver is an autoref of a “stable lvalue”, then we will desugar by evaluating the receiver last. So, let’s consider our running example of vec.push(vec.len()). Here the receiver is a mutable autoref of vec (i.e., &mut vec, where the &mut is automatically inserted). vec, as a local variable, is a “stable lvalue” (which I’ll define more precisely a bit later), so we would desugar as follows:

let tmp1 = {
  let tmp0 = &vec;
  Vec::len(tmp0)
}; // desugaring of `vec.len()`
let tmp0 = &mut vec; // NB this comes last now
Vec::push(tmp0, tmp1)

This code will not result in an evaluation error. However, this formulation does mean that it would also be legal to “mutate” the receiver in the arguments. In other words, consider our example of x.add(x.increment(1)) from before. Whereas it is now illegal, under this proposal it would be allowed, since the call would desugar to:

let tmp1 = {
  let tmp1 = 1;
  let tmp0 = &mut x;
  i32::increment(tmp0, tmp1)
}; // desugaring of x.increment(1)
let tmp0 = &x;
i32::add(tmp0, tmp1)

As we mentioned earlier, the result would be 2.

I believe that, for autoref’d “stable lvalue” receivers, this reordering is equivalent to saying that we “borrow the receiver for the future”. Moreover, it presumes a more permissive set of those rules, which just enforces the requirements needed to ensure that the address of the “future borrowed” value is stable, but doesn’t aim to prevent mutation of the referent.

Proposal 2: Borrow the receiver as shared first

If we wanted to be more prevent things like x.add(x.increment(1)), we might alter the desugaring in a different way. Again, only for autoref’d “stable lvalue” receivers, we would first take a shared borrow to the receiver that lasts while the other arguments are being evaluated. After they are done, we would evaluate the receiver as in the first proposal. So, iow, vec.push(vec.len()) might be desugared as follows:

let tmp0;
let tmp1; 
'eval_arg: { // block for evaluating arguments
    let tmp2: &'eval_arg Vec<usize> = &vec; // shared borrow of receiver
    tmp1 = vec.len(); // I won't bother with the recursive desugaring here
}
tmp0 = &mut vec; // prepare *actual* receiver
Vec::push(tmp0, tmp1)

The key difference is that (unused) temporary tmp2. It is never used, but it serves to prevent other arguments from mutating vec directly or taking a mutable borrow. (Note that there could still be mutations with a cell/ref-cell.) Since vec.len() is only a shared borrow of vec, there is no error here. But when we examine x.add(x.increment(1)), we see a different story:

let tmp0;
let tmp1;
'eval_arg: {
  let tmp2: &'eval_arg i32 = &x;
  tmp1 = x.increment(1); // ERROR!
}
let tmp0 = &x;
i32::add(tmp0, tmp1)

Now the shared borrow of tmp2 makes evaluating x.increment(1) an error, as we wanted.

I believe this is equivalent to “borrowing for the future”, but with a more restrictive notion of what it means to have a future loan: one which permits shared loans on that future item, but nothing else.

Questions to elaborate upon

Just what constitutes a “stable lvalue” receiver? I chose a simple definition here because I’m too tired from writing this summary to think clearly about the proper one. =)

Do we want to limit ourselves to “autoref” cases? This isn’t really necessary. e.g., should the modified desugaring for . trigger for (&mut vec).push(...) the samer as vec.push(...) and so forth? I suspect we should just have it trigger when it can, regardless of whether the “ref” is automatic or not, but that would have required more work on my part to write up (in particular, it affects the definition of “stable lvalue” somewhat) and I was too lazy.

When would we want to phase this in? If we solve this problem by adjusting the “desugaring”, it might fall out quite naturally by adopting MIR borrowck and changing how we desugar MIR. Right now, the time frame for MIR borrowck isn’t certain, but it shouldn’t be that long. Otherwise we could probably hack this in somewhat easily into old borrowck, but given the fragility of some of the code there (in particular the code for control flow) it makes me nervous.

It’s probably also (past) time to pay some attention to some of the other questions that came up in the MIR desugaring process.

Conclusion

I think the time has come to accept nested method calls. I’d prefer to do this by tweaking the desugaring for now, though I think that “future borrows” might be a nice concept of adopt at some point (after we work out what NLL is). In practice, this basically always strikes with . sugar though so a modified desugaring would be sufficient.

I am not sure whether I prefer proposal 1 or 2. Interestingly, while I think that the desugaring of proposal 2 is more complex, the interpretation of proposal 2 in terms of future loans is simpler, because having a “future loan” in scope is a very similar set of restrictions to have an active shared loan.


cc @arielb1 @eddyb and no doubt many others, who have discussed this issue in the past. I apologize for those places where I’m retreading ground. I had planned to go back and cite / re-read all the older threads but I’ve way exceeded my time allotment here. =) Please do point out things that I have missed.


[lang-team-minutes] Elision 2.0
[Pre-RFC] Unify bindings to callables
[blog post] Nested method calls via two-phase borrowing
[blog post] Nested method calls via two-phase borrowing
#2

Would either proposal apply to explicit UFCS? Vec::push(&mut vec, vec.len())


#3

No, neither of the two concrete proposals support UFCS. However, I discuss a more general variant (“borrowing for the future”) that would support UFCS, and discuss how the concrete proposals should be (I believe) compatible with that. I would prefer not to adopt that more general variant now because I think it is not the time.


#4

Broadly speaking, I think my preference would be to autoref and normalize to UFCS form, then apply a consistent evaluation strategy from there. That is, autoref method calls should be semantically equivalent to explicit UFCS, which as little additional magic as possible (autoref already being plenty of magic to worry about).

If arguments and borrowing were evaluated right-to-left, then I think your Proposal 1 would fall out naturally from UFCS, no? vec.push(vec.len()) -> Vec::push(&mut vec, Vec::len(&vec)) would take &vec and evaluate the length first, then take the &mut vec and call push.

But now I recall past threads where it seems Rust prefers LTR, namely #28160 and these:


#5

Regardless of which order one might prefer, I don’t consider it an option to break backwards compatibility in this way.


#6

(But you are right.)


#7

I agree, but I’m a little sad about it, especially if that means UFCS can’t be equivalent to method calls.


#8

Can’t we just say LTR, except if there’s a self parameter, in which case it’s second-to-right, then first?


#9

That is roughly what I am proposing, except that instead of doing it all the time, it’s only for “trivial” self parameters. I don’t think we should change when side-effects occur for things like foo().bar(baz()) (right now, foo(), then baz(), then bar()).


#10

I was just saying this yesterday.


#11

Great post!

My kneejerk reaction is:

  • We should pursue proposal 2. It can be loosened to proposal 1 in the future, but in the meantime this restriction seems valuable; as you say, forcing you to write temporaries for side-effecting cases seems like a good thing.
  • We should piggy-back this with the move to MIR borrowck. While we need to make this change in order to fix the original bug you mention, that bug has been around since Rust 1.0, and with the change to nested method calls, fixing it shouldn’t cause breakage, so there’s not necessarily a ton of urgency. I’d personally rather use it as additional impetus to push out MIR borrowck (and get that much closer to NLL).

#12

So proposals 1 and 2 are just a desugaring that ultimately does use UFCS. So everything that is possible can be written by hand with UFCS. I think that’s great—I want UFCS to be the universal simple building block, even if it does require more temporaries to accomplish the same thing.


#13

Point taken – with manual temporaries, one can indeed accomplish the same thing.


#14

So I was chatting with @arielb1 and wanted to summarize the proposal he floated in this earlier thread (which @cuviper also cited). It is a more far-reaching alternative that does address this issue, but which also makes changes to the existing evaluation order that may be significant (interestingly, it seems plausible to test this). It has some benefits and some drawbacks.

The proposal is:

Evaluation order for a Rust expression is two pass:

- first evaluate all rvalue subexpressions (left to right)
- then evaluate all lvalue subexpressions (left to right)
    - here, derefs and index impls are assumed to be "pure enough" 
        - *but* index *arguments are evaluated in first pass
    - crucially, autoderefs and autoref are also applied in this second pass

So, for vec.push(vec.len()), there are two subexpressions, vec and vec.len(). vec is an lvalue, so it is not evaluated in the first pass, but vec.len() (an rvalue) is. Then we “evaluate” vec and apply the autoref, and hence we get:

let tmp1 = vec.len(); // naturally this would be recursively expanded
let tmp0 = &mut vec;
Vec::push(tmp0, tmp1)

Note that desugaring to Vec::push(&mut vec, vec.len()) does not work, unless you make the model a bit more complex to treat borrow expressions and things differently.

Index lvalues provide for some subtlety. For example, if x=0 and you evaluate vec[x].push({x += 1}), are you pushing onto vec[0] or vec[1]? Seems like yes, because index arguments are always treated as rvalues, but that’s also kind of surprising.

This is backwards incompatible. For example, if you have x=0 and you evaluate x + { x += 1; 1}, then the block is evaluated first, and hence the final result is 2. That is, we desugar that to:

let tmp1 = { x += 1; 1 };
let tmp0 = x; // just an lvalue, eval during 2nd pass
tmp0 + tmp1

It does however mean that x += ... and x = x + ... are equivalent (not true today).

Interestingly, we could test for backwards compatibility, at least in theory, by generating the MIR both ways and applying some filters. This could be used to detect the impact of said changes.


#15

The main problem with my idea is that it behaves oddly with indexes, such as in:

    vec[i-1].push({vec = vec![vec![]]; i = 1; 0});

Here the new vec and the old i will be used.

OTOH, the main problem with upgradeable borrows is how to integrate it with the borrow checker, which is a different kind of problem.


#16

There’s an additional problem with upgradeable borrows:

// this expression
vec[vec.len()-1].push(0);
// actually desugars to
let tmp0 = Vec::deref_mut(&mut vec);
let tmp1 = <[usize]>::len(Vec::deref(&vec));
let tmp2 = IndexMut::index_mut(tmp0, tmp1);
Vec::push(tmp2, 0);

Here the upgradeable borrow must be threaded through the call to Vec::deref_mut, which is a user-defined function (and therefore might e.g. spawn a new thread). Do we need DerefPure?


#17

I’m not sure you touched on the “Deref Question” – if in the statement vec.push(vec.len()), vec is not a Vec<_> but a MyCustomBox<Vec<_>> which has an evil non-idempotent DerefMut implementation, then what? Proposal 1 alters the order of evaluation here.

(Edit: I think I’m saying the same thing as @arielb1. Maybe DerefPure can eliminate the problem, hopefully there aren’t too many MyCustomBoxes in the wild that would get broken.)


#18

To be more explicit, you mean that upgradable borrows (or “borrowing for the future”, as I was calling it, though it occurs to me that “reservations” might be a clearer term) will still report an error for vec[vec.len() - 1]? I agree, that seems true. (And, more generally, will be true for any deref/index impl.)

This might be ok. I feel like this is a far less common case.


#19

No, the way I had intended the proposal, that case would still error. That would not be considered a “stable lvalue” and hence no reordering would occur in the desugaring.

We could assume derefs to be pure, but it doesn’t solve some of the complex around index arguments, and it would then stray from the notion of “borrow for future” / “reservation” / “upgradable borrows”.


#20

I prefer proposal 2. It just feels correct to allow & but not &mut methods to be called nested