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.