Rust expression order of evaluation

[arielb1]

This is my writeup of issue 28160. Discussion is (and may still be) split between the locations.

Currently, the order of evaluation in Rust is undefined, and even inconsistent between borrow-checking an translation (that is unsound, of course). As part of the MIR work, we have an opportunity to define a consistent order of evaluation.

The order-of-evaluation of expressions is one of the ugliest corners in imperative language design. To these who have not seen it before, the issue is: in a complicated expression, for example

    *foo[bar()].baz(widget(), gadget()) = getit();

in which order do the functions run (that’s it, suppose each function printed its name, what will gets printed?). Note that this also includes overloaded autoderefs (these should not have side-effects, but they still can). C famously leaves this unspecified, even leaving many cases (like the infamous i = i++) as UB. This is not an option in Rust - program execution should be deterministic. Nondeterminism is Not An Option.

Pure left-to-right evaluation does not work

In Rust, the borrow checker makes the issue more annoying. For example, the simple expression

    a[i] += a[j];

is naïvely desugared into the code

    *IndexMut::index_mut(&mut a, i) += a[j];

If we evaluate left-to-right, a is borrowed mutably for the evaluation of the RHS, which conflicts with the access of a[j]. This is obviously not an acceptable situation.

Even if we didn’t have the borrow-checker, Rust’s expression-orientation can combine with this to cause subtle bugs. One example basically encountered by @eddyb is:

        self.balance -= self.data_cost(packet_len);

where data_cost is defined as

    fn data_cost(&mut self, packet_len: u64) -> u64 {
        self.do_surcharges();
        self.packet_len * self.cost_per_byte()
    }

    fn do_surcharges(&mut self) {
        if self.data_sent > self.low_limit {
            self.balance -= self.packet_surcharge();
        }
    }

This code is desugared to

    self.balance = self.balance - self.data_cost(packet_len);

While this code has an effect that is probably better for humanity than the alternative, the operator’s accountants may have a different view of things.

Solutions

Given that the problem is left-to-right evaluation, switching to right-to-left evaluation may seem like an obvious solution. However, function chaining foo.bar().baz() is done left-to-right, which will result in evaluation order alternating between right-to-left and left-to-right. While this is the most common order of technical writing in my language, I must admit it has significant understandability disadvantages ;-).

One potential solution I have thought of is based on the fact that the problems occur when one of the arguments of an operator is an lvalue. Now lvalues in Rust take the form of a base, which is a local or an rvalue, followed by field accesses, indexing, and dereferences (Rust regards dereferences as lvalue-to-lvalue operations - see my comment on github for more explanation). Indexing (built-in as well as overloaded) also takes an additional rvalue argument (the index).

Now, given its component rvalues, evaluating an lvalue does not really have side effects - dereferencing and indexing can be overloaded, but side effects in them are discouraged, and anyway they don’t have annoying borrow-checker effects. My rule handles most of the examples given to it excellently, and all others I have seen decently.

[arielb1]

Details

One proposal that mostly maintains LTR and handles x[i] = x[j]

Definitions

An lvalue expression is basically the current rustc lvalue expression.

Unresolved Question: do we include overloaded index/deref in index/deref lvalues? this makes more code compile but could be confusing in some cases?

LVALUE_EXPR = 
       MUTABILITY RVALUE_EXPR           - temporary
       | LVALUE_EXPR . FIELD            - field access
       | LVALUE_EXPR [ RVALUE_EXPR ]    - indexing (including overloaded?)
       | *MUTABILITY LVALUE_EXPR        - deref
       | LOCAL                          - local variable

Evaluating an expression “to an lvalue” is just evaluating all the rvalue-expressions in it. Note that after an expression is evaluated to an lvalue, finalizing its evaluation can still read memory and possibly run user code (if we allow overloaded derefs/indexing).

Evaluating an expression “to an rvalue” is just standard evaluation.

To evaluate an expression with a receiver, that’s it “LHS = RHS”, “LHS OP= RHS”, “LHS.foo(ARG1, ARG2)”, first the pre-final-autoref receiver is evaluated to an lvalue, then the other operands are evaluated to rvalues, then the receiver evaluation is finalized and autoref-ed if needed.

Unresolved question: should this happen with by-value-self taking methods too? Provide an example for and against.

Examples

Simple assignment

x[I] = x[J];
// equiv
let i = I;
let rhs = x[J];
x[I] = rhs;

Simple function call

a.b.f(a.b.g(), a.b.h())
// equiv
let arg0 = a.b.g();
let arg1 = a.b.h();
a.b.f(arg0, arg1); // potentially with overloaded autoderef

Changing receiver

(*boxed).push({
    mem::replace(&mut boxed, Box::new(vec![])).len()
})
// equiv
let arg0 = mem::replace(&mut boxed, Box::new(vec![])).len();
Vec::push(&mut *boxed, arg0); // this can be surprising, I guess.

Changing receiver, deep

let y = Vec::new();
(***boxed).get({boxed=&&&y; 42})
// equiv
let y = Vec::new();
let ix = {boxed=&&&y; 42};
<[u8]>::get(&<Vec<u8> as Deref>::deref(&***boxed), ix)

Cutting your own receiver

let boxed: Box<&[u8]> = get();
boxed.get({drop(boxed); 4})
// equiv
let boxed: Box<&[u8]> = get();
let ix = { drop(boxed); 4 };
<[u8]>::get(&**boxed) //~ ERROR use of moved value

Cutting your own receiver, by-value

let a: &mut [u32] = &mut [1,2];
let b: &mut [u32] = &mut [3,4];
let c;
a.get_mut({a=b; c=a; 1})
// equiv
let ix = {a=b; c=a; 1}
<&mut [u32]>::get_mut(a, ix) //~ ERROR use of moved value

Chained function call

a.b().c().d()
// equiv
let t0 = a.b(); // this is an rvalue
let t1 = t0.c();
let t2 = t1.d();

Pushing length

x[ix()].push(x[0].len());
// equiv
let index = ix();
let arg0 = x[0].len();
x[index].push(arg0);

Pushing length, via function

x.get_mut().push(x[0].len());
// equiv
let t0 = x.get_mut();
let len = x[0].len(); //~ ERROR cannot borrow
t0.push(len);

Simple assign-op

dirty |= SOMETHING_MODIFYING_DIRTY;
// equiv
let rhs = SOMETHING_MODIFYING_DIRTY;
dirty = dirty | rhs;

Advantages

Most code should compile and do something sane.

Disadvantages

Indexing/deref is handled somewhat differently from normal methods. If we don’t allow overloaded deref/indexing, they can behave differently from primitive deref/indexing. If we do, their order-of-evaluation can be somewhat confusing.

The handling of coercions needs to be thought about - if they can occur in the middle of an lvalue, they can break it. It would be nice if someone who knows them could provide an example.

This also changes order-of-evaluation, which could subtly break existing code.

Coercions

Could someone help me there (@eddyb, you know these best)

Lvalues and deref

With the borrow checker, overloaded deref as well as deref of &mut references is very similar to an operation on lvalues, turning an 'a Ptr<T> (or 'a &'b mut T) into an 'a T.

This is actually not totally precise: references can be “leaked”. A by-value &'a mut T can be transformed to an 'a mut T. This is similar to a turning a by-value Box<T> into an 'static mut T (the latter transformation is not automatic, as it has the unfortunate side-effect effect of leaking memory), but is a good model in many cases (this “leak” functionality is somewhat confusing).

Dereference of &T always uses the “leak” functionality, but that is less confusing as &T is Copy.

[arielb1]

More Disadvantages

This is relatively complicated and there are probably highly confusing examples. Also, this is not as backwards-compatible as possible, even occasionally causing unneeded subtle breakage.

Unresolved Question

What counts as an lvalue position for this? Do by-value method calls count? Address-of? Dereference?

[Diggsey]

Alternative: define order in terms of method calls only. Everything else is defined via a desugaring to a method call.

eg. a.f(x, y, z): arguments are evaluated left to right, with this evaluated last, ie x, y, z, a.

Assignment desugars to the assignment trait form: a += b -> a.add_assign(b)

This works on the basis that usually the thing being mutated is the this parameter, and any more complicated rule (such as one which depends on lvalues) will probably do more harm than good - after all you can always solve borrowck errors by rewriting slightly to make evaluation order explicit.

[arielb1]

That has the unfortunate consequence of making evaluation alternate between right-to-left and left-to-right.

[llogiq]

I still think all of those are degenerate cases. If the outcome of your expression is different based on order of evaluation, you are knowingly creating a footgun. It is my humble opinion that we should remove those cases; i.e. Rust shouldn’t be a language for code golf, but for writing good code.

Therefore I propose making such expressions a hard error in the compiler – this rules out all nondeterminism and naturally leads to more readable code. Failing that, we should at least provide a lint.

[td_]

The proposed evaluation order seems to produce the most sensible result, even though it's rather confusing. I wanted to claim that simply evaluating the entire receiver last would be a less opaque alternative, but I expect expressions in the receiver to be evaluated first as much as possible.

@arielb1

Unresolved question: should this happen with by-value-self taking methods too? Provide an example for and against.

I don't know if it impacts soundness at all, but my intuitive expection is that all method calls would be evaluated in the same order, so if its possible they should be the same I think.

@llogiq

I still think all of those are degenerate cases. If the outcome of your expression is different based on order of evaluation, you are knowingly creating a footgun. It is my humble opinion that we should remove those cases; i.e. Rust shouldn't be a language for code golf, but for writing good code.

This isn't possible.

First, it's not possible to have the entire outcome of the expression be restricted without purity. Taking this absurd code as an example, what is printed to stdout is determined by the order of evaluation, and there's no way to make this expression illegal without making useful expressions illegal:

    let mut x = "Hello";
    {
        println!("{}", x);
        x = "World";
        vec![0]
    }.push({
        println!("{}", x);
        1
    })

However, more seriously (and arielb1 alludes to this in the first post), the subtyping relation between lifetimes is determined by the order expressions are evaluated in. Depending on the order of evaluation, a[i] += a[j] is either an overlapping lifetime error or it isn't.

[llogiq]

@td_

there's no way to make this expression illegal without making useful expressions illegal

Are you sure about that? All examples I've seen so far belong in an underhanded Rust contest, not in production code. All of them could have been rewritten to make the order of evaluation clear, mostly by introducing additional statements.

Until someone shows me a useful expression that cannot be expressed in Rust without relying on the order of evaluation, I stand by my point.

@td_

However, more seriously (and arielb1 alludes to this in the first post), the subtyping relation between lifetimes is determined by the order expressions are evaluated in. Depending on the order of evaluation, a[i] += a[j] is either an overlapping lifetime error or it isn't.

This is also a moot point if the order of evaluation does not affect the result. As for your example, I think it must be an overlapping lifetime error, mostly because you're both mutably and immutably borrowing a.

[td_]

@llogiq

Are you sure about that? All examples I've seen so far belong in an underhanded Rust contest, not in production code. All of them could have been rewritten to make the order of evaluation clear, mostly by introducing additional statements.

Until someone shows me a useful expression that cannot be expressed in Rust without relying on the order of evaluation, I stand by my point.

But what rules would you add to Rust's type system to make the example above an illegal expression?

@llogiq

This is also a moot point if the order of evaluation does not affect the result. As for your example, I think it must be an overlapping lifetime error, mostly because you're both mutably and immutably borrowing a.

Today that code does not have a lifetime error. Both of these snippets work fine, and I don't see why they shouldn't.

    let mut a = [1, 2]; // <a as Index>::Output is Copy
    a[0] += a[1];

    let mut a = [Box::new(1), Box::new(2)]; // <a as Index>::Output is Clone
    a[0] = a[1].clone();

[llogiq]

Today that code does not have a lifetime error.

Ok, it appears I overstepped here. &mut a[i] += &a[j] should be a lifetime error, though. So if the code after Deref coercion fails to appease borrowck, it won't compile today, no matter the evaluation order.

But what rules would you add to Rust's type system to make the example above an illegal expression?

typeck doesn't have enough information to rule out such expressions. However, it's possible to find functions/operations that mutate a value using a modified ExprUseVisitor, and forbidding those within a sub-scope of expressions that read and modify the same value.

[td_]

@llogiq

Ok, it appears I overstepped here. &mut a[i] += &a[j] should be a lifetime error, though. So if the code after Deref coercion fails to appease borrowck, it won't compile today, no matter the evaluation order.

I don't know what you mean by "if the code after Deref coercion fails to appease borrowck". The lhs of += is taken as &mut T whereas the rhs is taken as T. Evaluation order is essential to determine if this works or not. If the index expression on the lhs is evaluated prior the evaluation of the rhs, that &mut T has a lifetime which includes the entire evaluation of the rhs expression, which would cause overlapping lifetime errors. If on the other hand, the rhs is evaluated before that index expression in the lhs, there is no overlapping lifetime.

There is nothing different about the evaluation order within an expression like this and the evaluation order within a block expression. Surely you wouldn't say that the order of statements inside a block should not affect how that block is evaluated.

[petrochenkov]

I’m curious how much code actually breaks with strict L to R.
I’ve grepped the Rust codebase and found only a dozen of a[i] = a[j] patterns and exactly zero a[i] OP= a[j] patterns.
Considering this, personally, I’d sacrifice a[i] = a[j] / a[i] OP= a[j] (the workaround is very simple anyway) in favor of The Simplest Possible Evaluation Order Ever, but unfortunately it’s too late now (at least for =).

[llogiq]

Thank you for pointing that out. I don’t think it is too late, however, as evaluation order was deliberately unspecified, so code that depends on it is by definition erroneous.

[llogiq]

@td_

There is nothing different about the evaluation order within an expression like this and the evaluation order within a block expression.

I beg to differ. The evaluation order within a block expression is specified.

[arielb1]

Therefore I propose making such expressions a hard error in the compiler – this rules out all nondeterminism and naturally leads to more readable code. Failing that, we should at least provide a lint.

Unfortunately, derefs are everywhere and are not required to be pure (but hopefully nobody relies on the order of evaluation of impure derefs).

Until someone shows me a useful expression that cannot be expressed in Rust without relying on the order of evaluation, I stand by my point.

It is my intent that every expression is equivalent to one that is independent of the order of evaluation. However, a sane order-of-evaluation is important for ergonomics (also, not breaking every non-trivial Rust crate in the world).

I don't know if it impacts soundness at all, but my intuitive expection is that all method calls would be evaluated in the same order, so if its possible they should be the same I think.

This can't impact soundness as borrow checking will be done after simplification. I would prefer to do it for by-value method calls too.

Ok, it appears I overstepped here. &mut a[i] += &a[j] should be a lifetime error, though. So if the code after Deref coercion fails to appease borrowck, it won't compile today, no matter the evaluation order.

That is indeed a lifetime error under my rules. &mut a[i] is an rvalue, so it is evaluated in one piece, before &a[j].

Thank you for pointing that out. I don't think it is too late, however, as evaluation order was deliberately unspecified, so code that depends on it is by definition erroneous.

The order of evaluation should be reasonable. I think "left to right, dereferences are evaluated as late as possible" is a reasonable rule.

[td_]

@llogiq

I beg to differ. The evaluation order within a block expression is specified.

It's not officially specified, but there exists an order in which the operations are taken to be performed during typeck, borrowck, and code generation (which seem to differ (!)). Lifetime analysis will reach a different result depending on the order of evaluation, so the order of evaluation needs to be specified.

---

@arielb1 Is there a reason that the taking a reference of the self parameter couldn't be delayed for methods as well? Consider this:

    struct Foo(i32);

    impl Foo {
        fn incr(&mut self, n: i32) { self.0 += n }
        fn double(&mut self) { self.incr(self.0) }
    }

There is a overlapping lifetime error in double() even though incr() can't mutate self until after the borrow of self.0 has ended. This is the kind of analysis that makes borrowck seem oppressive and unproductive to new users.

[arielb1]

@td_

When non-commutative operations are done, the result of a program’s execution depends on the evaluation order. The lack of “upgrading” borrows does make this much more annoying issue, as mutable borrows do not commute with the common (pure and therefore commutative) immutably-borrowing query-like actions.

In fact, code like you presented is one of the primary motivations for the change. self is an lvalue. It has no rvalue components (rvalue base and/or indexes), so the entirety of its (trivial) evaluation will occur after the argument’s.

[arielb1]

@petrochenkov

We will probably pick a variant of either the rvalue-first or receiver-last evaluation order. @eddyb does not like the receiver-last evaluation order as it makes complicated expressions evaluate in a rather unnatural order (*foo.pop() += foo.len();).

[nikomatsakis]

@arielb1 first, thanks for opening this thread. I’ve been meaning to follow up on this topic but it’s nice to have some of the details written up by somebody else.

My feeling is that we should keep the evaluation order LTR where possible, but overall it should be relatively easy to predict. Thus complex orderings that “mostly” preserve LTR seems (to me) to be overall less good than just saying “assignments are RTL”.

The interaction with overloaded operators is also an important question. It is not clear to me that self.balance -= x and self.balance = self.balance - x should always be equivalent. They are certainly distinct with overloaded operators, since one desugars into an &mut self operator (or at least that is the proposed desugaring). I think we should strive that the builtin operations can be modeled using overloaded versions, which would imply that self.balance -= foo() will “read” the current value of self.balance only after foo() is evaluated (unlike self.balance = self.balance - foo()). Subtle, but they you go. (I imagine that all languages which desugar -= specially can encounter a similar situation.)

[dckc]

Is the “define order in terms of method calls only” proposal (from @Diggsey) still in play? If not, what was the argument against it?