Stream: t-compiler/wg-nll

Topic: #53189 optimize `check_if_reassignment_to_immutable_state`


nikomatsakis (Aug 08 2018 at 16:10, on Zulip):

@Santiago Pastorino how much do you know about the MoveData setup?

Santiago Pastorino (Aug 08 2018 at 16:25, on Zulip):

from the top of my head nothing

Santiago Pastorino (Aug 08 2018 at 16:25, on Zulip):

but I have already done something with it ... don't remember

Santiago Pastorino (Aug 08 2018 at 16:25, on Zulip):

need to check the definition

nikomatsakis (Aug 08 2018 at 16:26, on Zulip):

the idea is that we find paths which are used within the MIR (i.e., Places)

nikomatsakis (Aug 08 2018 at 16:26, on Zulip):

and we assign them a MovePathIndex

nikomatsakis (Aug 08 2018 at 16:27, on Zulip):

actually i'd like to use them (or something similar) for everything

nikomatsakis (Aug 08 2018 at 16:27, on Zulip):

but right we only use them for computing which values have been initialized etc

nikomatsakis (Aug 08 2018 at 16:27, on Zulip):

these indices are then used in the bitset

nikomatsakis (Aug 08 2018 at 16:27, on Zulip):

in particular, if you have a path like a.b.c there will be a MovePathIndex (MPI) for that path; these are in a tree, so you can go to the MPI for the parent (a.b) and its parent (a)

nikomatsakis (Aug 08 2018 at 16:28, on Zulip):

we make MPIs for each path that is used in the source

nikomatsakis (Aug 08 2018 at 16:28, on Zulip):

well, almost

nikomatsakis (Aug 08 2018 at 16:28, on Zulip):

in particular, there are some paths where you cannot move individual fields out

nikomatsakis (Aug 08 2018 at 16:28, on Zulip):

for example, you cannot move a field from an enum, or from the referent of a &T , or from a struct that implements Drop

nikomatsakis (Aug 08 2018 at 16:28, on Zulip):

in those cases there is no MPI for the path

nikomatsakis (Aug 08 2018 at 16:28, on Zulip):

because any attempt to move from such a path would be an error

nikomatsakis (Aug 08 2018 at 16:29, on Zulip):

I mention this because when you have an assignment like a = foo, we need to map a to an MPI to look up whether it has already been initialized or not

nikomatsakis (Aug 08 2018 at 16:29, on Zulip):

in the "simplified version" that I initially proposed, this lookup would be infallible, because there is always an MPI for every local variable

nikomatsakis (Aug 08 2018 at 16:30, on Zulip):

but if we want to permit something like

let x: (u32, u32);

x.0 = 22;
x.1 = 44;
nikomatsakis (Aug 08 2018 at 16:30, on Zulip):

then we would be looking up the MPI for x.0 (and all of its parents, I think)

nikomatsakis (Aug 08 2018 at 16:31, on Zulip):

(actually i'm not 100% sure how that works, I have to double check, I thought that we only propagated the bits for the paths like x.0, but maybe we assign a bit for every MPI? have to check)

nikomatsakis (Aug 08 2018 at 16:31, on Zulip):

anyway, point is, that might be fallible

nikomatsakis (Aug 08 2018 at 16:31, on Zulip):

I'm actually in favor still of doing the simplified thing that matches AST borrow ck

nikomatsakis (Aug 08 2018 at 16:31, on Zulip):

and opening an issue to do a full extension

nikomatsakis (Aug 08 2018 at 16:31, on Zulip):

to do it right will require a bit more work anyway

nikomatsakis (Aug 10 2018 at 10:10, on Zulip):

@Santiago Pastorino do you think you'll have time to poke at this? I'm tempted to take a stab at it myself to see how much it helps

Santiago Pastorino (Aug 10 2018 at 12:44, on Zulip):

yes

Santiago Pastorino (Aug 10 2018 at 12:44, on Zulip):

I have time today for sure

Santiago Pastorino (Aug 10 2018 at 19:42, on Zulip):

hey @nikomatsakis back

Santiago Pastorino (Aug 10 2018 at 19:42, on Zulip):

so, I've made a couple of tests

Santiago Pastorino (Aug 10 2018 at 19:42, on Zulip):

but I was reading what you wrote in the issue

Santiago Pastorino (Aug 10 2018 at 19:42, on Zulip):

in particular this part

Santiago Pastorino (Aug 10 2018 at 19:42, on Zulip):

It iterates over all initialized paths and checks that the path being assigned to (e.g., x.0 in the third example) is disjoint from all of them:

Santiago Pastorino (Aug 10 2018 at 19:42, on Zulip):

not sure I follow the meaning of that

Santiago Pastorino (Aug 10 2018 at 19:43, on Zulip):

and also, it seems very different to what the error talks about

Santiago Pastorino (Aug 10 2018 at 19:43, on Zulip):

the error says

Santiago Pastorino (Aug 10 2018 at 19:43, on Zulip):

cannot mutably borrow field of immutable binding

Santiago Pastorino (Aug 10 2018 at 19:43, on Zulip):

which I'm not even sure if it's correct

Santiago Pastorino (Aug 10 2018 at 19:44, on Zulip):

I need to read the comments of the issue

Santiago Pastorino (Aug 10 2018 at 19:47, on Zulip):

I've read the stuff, ok I see why the mut thing, but the borrow word in the error sounds weird to me

Santiago Pastorino (Aug 10 2018 at 19:47, on Zulip):

is that a borrow?

Santiago Pastorino (Aug 10 2018 at 19:47, on Zulip):

I mean, accessing an entry of a pair

Santiago Pastorino (Aug 10 2018 at 19:48, on Zulip):

and anyway I still don't get the phrase anyway It iterates over all initialized paths and checks that the path being assigned to (e.g., x.0 in the third example) is disjoint from all of them:

Santiago Pastorino (Aug 10 2018 at 19:49, on Zulip):

I mean, I think I get it but I can't make sense of that

Santiago Pastorino (Aug 10 2018 at 19:49, on Zulip):

you mean that the algorithm iterates over .0 and .1 and check that the thing being assigned in this case .0 is disjoint in this case? which of course is not?

Santiago Pastorino (Aug 10 2018 at 19:50, on Zulip):

I don't see how that makes sense to cover reassignments of immutable things

nikomatsakis (Aug 10 2018 at 19:58, on Zulip):

hey @Santiago Pastorino

nikomatsakis (Aug 10 2018 at 19:58, on Zulip):

sorry, was in a call

nikomatsakis (Aug 10 2018 at 19:59, on Zulip):

ok so what the code does now

nikomatsakis (Aug 10 2018 at 19:59, on Zulip):

it has a complete list of all things that have ever been assigned up until this point

Santiago Pastorino (Aug 10 2018 at 19:59, on Zulip):

I was reading again and I think I got it :)

nikomatsakis (Aug 10 2018 at 19:59, on Zulip):

ah ok :)

nikomatsakis (Aug 10 2018 at 19:59, on Zulip):

I think the actual diff needed here is not very large

nikomatsakis (Aug 10 2018 at 19:59, on Zulip):

depending which alternative we opt for

Santiago Pastorino (Aug 10 2018 at 20:00, on Zulip):

we are not going to allow in this PR x.0 = 1; x.1 = 2; and stuff like that, right?

nikomatsakis (Aug 10 2018 at 20:00, on Zulip):

I'm personally leaning that way

nikomatsakis (Aug 10 2018 at 20:00, on Zulip):

it seems just a bit easier

nikomatsakis (Aug 10 2018 at 20:00, on Zulip):

it may be a larger diff though :)

nikomatsakis (Aug 10 2018 at 20:00, on Zulip):

just because the code is a bit oriented towards accepting that

nikomatsakis (Aug 10 2018 at 20:01, on Zulip):

anyway I feel like I'd rather support x.0 = 1 properly

nikomatsakis (Aug 10 2018 at 20:01, on Zulip):

I regret that we permit you to do that (at least, without having initialized x first) at all

nikomatsakis (Aug 10 2018 at 20:01, on Zulip):

(i.e., we now accept it, so long as x is mut)

nikomatsakis (Aug 10 2018 at 20:01, on Zulip):

but not much we can do about that

nikomatsakis (Aug 10 2018 at 20:01, on Zulip):

no need to break code

Santiago Pastorino (Aug 10 2018 at 20:02, on Zulip):

I regret that we permit you to do that (at least, without having initialized x first) at all

permit to do what?

nikomatsakis (Aug 10 2018 at 20:03, on Zulip):

we permit this today:

let mut x: (u32, u32);
x.0 = 1; x.1 = 2;

but only if x is mut

nikomatsakis (Aug 10 2018 at 20:03, on Zulip):

we do not permit you to use x later

nikomatsakis (Aug 10 2018 at 20:03, on Zulip):

that is, you can use x.0 but not x

nikomatsakis (Aug 10 2018 at 20:04, on Zulip):

in other words, if x is mut, we let you initialize "field by field", but we never recognize that x is fully initialized

Santiago Pastorino (Aug 10 2018 at 20:04, on Zulip):

I see

Santiago Pastorino (Aug 10 2018 at 20:04, on Zulip):

even this ...

Santiago Pastorino (Aug 10 2018 at 20:04, on Zulip):
let x: (u32, u32);
x.0 = 1; x.1 = 2;
Santiago Pastorino (Aug 10 2018 at 20:04, on Zulip):

should work

nikomatsakis (Aug 10 2018 at 20:06, on Zulip):

well

nikomatsakis (Aug 10 2018 at 20:06, on Zulip):

eventually I think yes

nikomatsakis (Aug 10 2018 at 20:06, on Zulip):

but it doesn't today (i.e., with the AST-based checker)

Santiago Pastorino (Aug 10 2018 at 20:06, on Zulip):

:+1:

nikomatsakis (Aug 10 2018 at 20:06, on Zulip):

it does with the MIR-based checker today

Santiago Pastorino (Aug 10 2018 at 20:07, on Zulip):

so

Santiago Pastorino (Aug 10 2018 at 20:07, on Zulip):
#![feature(nll)]

fn main() {
    let x: (u32, u32);

    x.0 = 22;
}
Santiago Pastorino (Aug 10 2018 at 20:07, on Zulip):

why should that fail?

Santiago Pastorino (Aug 10 2018 at 20:08, on Zulip):

just to keep the AST behavior for now?

nikomatsakis (Aug 10 2018 at 20:08, on Zulip):

it's easier? :)

nikomatsakis (Aug 10 2018 at 20:08, on Zulip):

I'm not sure that it should

Santiago Pastorino (Aug 10 2018 at 20:08, on Zulip):

but weren't you saying that this case is already working?

Santiago Pastorino (Aug 10 2018 at 20:08, on Zulip):

:P

nikomatsakis (Aug 10 2018 at 20:08, on Zulip):

well

nikomatsakis (Aug 10 2018 at 20:09, on Zulip):
#![feature(nll)]

fn main() {
    let x: (u32, u32);
    x.0 = 22;
    x.1 = 44;
    drop(x); // ERROR
}
Santiago Pastorino (Aug 10 2018 at 20:09, on Zulip):

the thing is that x doesn't work later?

nikomatsakis (Aug 10 2018 at 20:09, on Zulip):

"working"

Santiago Pastorino (Aug 10 2018 at 20:09, on Zulip):

yes

Santiago Pastorino (Aug 10 2018 at 20:09, on Zulip):

I see

nikomatsakis (Aug 10 2018 at 20:09, on Zulip):

but yes

Santiago Pastorino (Aug 10 2018 at 20:10, on Zulip):

so ... to be 100% clear

Santiago Pastorino (Aug 10 2018 at 20:10, on Zulip):

the rules we want to implement are ...

Santiago Pastorino (Aug 10 2018 at 20:10, on Zulip):

if x is not mut, we can't assign twice, it doesn't matter if the parts are disjoint

nikomatsakis (Aug 10 2018 at 20:11, on Zulip):

well

nikomatsakis (Aug 10 2018 at 20:11, on Zulip):

I am vacillating :)

nikomatsakis (Aug 10 2018 at 20:11, on Zulip):

but that is what I said

nikomatsakis (Aug 10 2018 at 20:11, on Zulip):

I am looking briefly at the code now

Santiago Pastorino (Aug 10 2018 at 20:11, on Zulip):

if x is mut it just works?

nikomatsakis (Aug 10 2018 at 20:12, on Zulip):

there are some annoying complications to consider

nikomatsakis (Aug 10 2018 at 20:12, on Zulip):

e.g.

nikomatsakis (Aug 10 2018 at 20:12, on Zulip):
union Foo { a: u32, b: u32 }

fn main() {
    let foo: Foo;

    foo.a = 22;
    foo.b = 44; // Error?
}
nikomatsakis (Aug 10 2018 at 20:13, on Zulip):

(that is, if we want to support this)

nikomatsakis (Aug 10 2018 at 20:13, on Zulip):

this is why the code was written with that naive loop, I think

Santiago Pastorino (Aug 10 2018 at 20:13, on Zulip):

hmmm

nikomatsakis (Aug 10 2018 at 20:13, on Zulip):

so yes I personally lean towards implementing the existing AST behavior, which is easy to get right

nikomatsakis (Aug 10 2018 at 20:13, on Zulip):

and then filing a follow-up issue to support "partial initialization" better

Santiago Pastorino (Aug 10 2018 at 20:14, on Zulip):

:+1:

Santiago Pastorino (Aug 10 2018 at 20:14, on Zulip):

so ... you proposed two ideas if I've read correctly

Santiago Pastorino (Aug 10 2018 at 20:14, on Zulip):
Distinguish the case of assignment directly to an immutable local (x = ...) from any other place.

    For assignments to an immutable local, we find the move-path-index and just check the "ever initialized" bit directly.
    For assignments to any other place, we use the self.access_place method with LocalMutationIsAllowed::No (unlike now, where we use ExceptUpvars).
Santiago Pastorino (Aug 10 2018 at 20:14, on Zulip):

and

Santiago Pastorino (Aug 10 2018 at 20:14, on Zulip):
    Find the move path corresponding to the place being assigned
        If there is no precise match, that is an error (e.g., assigning to a single field of a drop struct)
    If there is a precise match, check its bit
nikomatsakis (Aug 10 2018 at 20:15, on Zulip):

yes

nikomatsakis (Aug 10 2018 at 20:15, on Zulip):

well

nikomatsakis (Aug 10 2018 at 20:15, on Zulip):

the second one...

nikomatsakis (Aug 10 2018 at 20:16, on Zulip):

if this is an assignment to an immutable local,

nikomatsakis (Aug 10 2018 at 20:16, on Zulip):

then in fact you are guaranteed that it has a MPI bit

nikomatsakis (Aug 10 2018 at 20:16, on Zulip):

because all locals have MPI bits

Santiago Pastorino (Aug 10 2018 at 20:20, on Zulip):

unsure what the last thing means

nikomatsakis (Aug 10 2018 at 20:21, on Zulip):

there are these "move paths" that are used to track what is initialized

nikomatsakis (Aug 10 2018 at 20:21, on Zulip):

each has a MovePathIndex (or MPI)

nikomatsakis (Aug 10 2018 at 20:21, on Zulip):

we create them for all the places that we see in the source

nikomatsakis (Aug 10 2018 at 20:21, on Zulip):

or, most of them

nikomatsakis (Aug 10 2018 at 20:21, on Zulip):

but not for just any old Place

nikomatsakis (Aug 10 2018 at 20:22, on Zulip):

so if you want to check if some place has been initialized, you do something like:

let x = move_data.mpi(place); // converts the place to an mpi
check-if-the-bit-x-is-set
nikomatsakis (Aug 10 2018 at 20:22, on Zulip):

except that the first step is sometimes "fallible"

nikomatsakis (Aug 10 2018 at 20:22, on Zulip):

...but not for local variables

nikomatsakis (Aug 10 2018 at 20:23, on Zulip):

https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/move_paths/struct.MovePathLookup.html#method.find_local

nikomatsakis (Aug 10 2018 at 20:24, on Zulip):

that method will give you the MovePathIndex for a local variable

nikomatsakis (Aug 10 2018 at 20:26, on Zulip):

then something like

nikomatsakis (Aug 10 2018 at 20:28, on Zulip):
let mpi = self.move_data.rev_lookup.find_local(local);
let is_initialized =
  self.move_data.init_path_map[mpi]
    .iter()
    .any(|init_index| flow_state.ever_inits.contains(&init_index));
nikomatsakis (Aug 10 2018 at 20:28, on Zulip):

bit more complex than I thought...

nikomatsakis (Aug 10 2018 at 20:28, on Zulip):

so, what's happening there:

nikomatsakis (Aug 10 2018 at 20:29, on Zulip):

for every initialization, we create an index (the init_index)

nikomatsakis (Aug 10 2018 at 20:29, on Zulip):

then we have a map from each variable to all the initializations that correspond to it

nikomatsakis (Aug 10 2018 at 20:29, on Zulip):

so e.g. if you had

let (x, y);

x = 44; // this gets an InitIndex, say 0
y = 44;  // this gets an InitIndex, say 1
nikomatsakis (Aug 10 2018 at 20:29, on Zulip):

and there is a map that would say x -> [0], y -> [1]

nikomatsakis (Aug 10 2018 at 20:32, on Zulip):

let me know if this is making any sense at all :)

nikomatsakis (Aug 10 2018 at 20:32, on Zulip):

it seems clear we need some more chapters in the rustc-guide...

Jake Goulding (Aug 10 2018 at 20:49, on Zulip):

and then filing a follow-up issue to support "partial initialization" better

I think that's https://github.com/rust-lang/rust/issues/21232

nikomatsakis (Aug 10 2018 at 22:22, on Zulip):

https://github.com/rust-lang/rust/pull/53258

Santiago Pastorino (Aug 11 2018 at 00:05, on Zulip):

on other front ...

Santiago Pastorino (Aug 11 2018 at 00:05, on Zulip):
commit 63c32b891da049cf20d0693b5e122a8937c8e67b
Author: Santiago Pastorino <spastorino@gmail.com>
Date:   Fri Aug 10 16:34:35 2018 -0300

    Add test showing that re-assigning to immutable in nll fails

diff --git a/src/test/ui/nll/reassignment-to-immutable.rs b/src/test/ui/nll/reassignment-to-immutable.rs
new file mode 100644
index 0000000000..07046cf2a2
--- /dev/null
+++ b/src/test/ui/nll/reassignment-to-immutable.rs
@@ -0,0 +1,19 @@
+// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(nll)]
+
+fn main() {
+    let x: (u32, u32);
+    x = (1, 2);
+    x = (3, 4);
+    //~^ ERROR cannot assign twice to immutable variable `x` [E0384]
+    drop(x);
+}
diff --git a/src/test/ui/nll/reassignment-to-immutable.stderr b/src/test/ui/nll/reassignment-to-immutable.stderr
new file mode 100644
index 0000000000..31716050f7
--- /dev/null
+++ b/src/test/ui/nll/reassignment-to-immutable.stderr
@@ -0,0 +1,13 @@
+error[E0384]: cannot assign twice to immutable variable `x`
+  --> $DIR/reassignment-to-immutable.rs:16:5
+   |
+LL |     let x: (u32, u32);
+   |         - consider changing this to `mut x`
+LL |     x = (1, 2);
+   |     ---------- first assignment to `x`
+LL |     x = (3, 4);
+   |     ^^^^^^^^^^ cannot assign twice to immutable variable
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0384`.
Santiago Pastorino (Aug 11 2018 at 00:06, on Zulip):

@nikomatsakis forgot to share that if you want to avoid typing that code :P

nikomatsakis (Aug 11 2018 at 00:34, on Zulip):

I was thinking a few more tests would probably be good actually

nikomatsakis (Aug 11 2018 at 00:34, on Zulip):

in particular, my changes didn't really break anything :)

Santiago Pastorino (Aug 11 2018 at 12:37, on Zulip):

cool

Last update: Nov 21 2019 at 13:25UTC