NLL iterating and updating &mut fails for non-local Place.

[pnkfelix]

Spawned off of discussion with @ecstatic-morse and their work on PR #61787

There is a dataflow subroutine for Borrows, kill_borrows_on_place, added in PR #56649 to resolve #46589. kill_borrows_on_place reads from the on_entry field of BlockSets (even though I am pretty sure no one was ever supposed to do so; its inclusion in this part of the API was a wart):

rust/src/librustc_mir/dataflow/impls/borrows.rs

Lines 205 to 214 in f0c2bdf

	// Otherwise, look at all borrows that are live and if they conflict with the assignment
	// into our place then we can kill them.
	let mut borrows = sets.on_entry.clone();
	let _ = borrows.union(sets.gen_set);
	for borrow_index in borrows.iter() {
	let borrow_data = &self.borrows()[borrow_index];
	debug!(
	"kill_borrows_on_place: borrow_index={:?} borrow_data={:?}",
	borrow_index, borrow_data,
	);

I think this was written with the assumption that sets.on_entry.clone().union(sets.gen_set) (aka on-entry U gen-set) would represent an upper-bound on the things that should be in the kill set. (And then the subsequent loop determines which of those things to actually put into the kill set.)

The problem with that is that when we are computing the transfer-function initially, on_entry is going to be the empty-set, at least for almost all basic blocks. That all you have to work with in dataflow. So you end up with a kill-set here that is an under-approximation to what it should actually be, if you are assuming that we're supposed to start with the complete (post dataflow) on-entry and combine that with gen-set to get the upper bound on what to use for the kill-set.

Why hasn't this been a problem for us so far? Well, here's my theory:

1. With respect to soundness: if the kill-set for Borrows is a subset of what it should "truly be", then I think the compiler ends up treating borrows as living longer than they should, and so it ends up detecting conflicts that are not actually there, and so the compiler rejects code that you might have other expected it to accept.

2. With respect to expressiveness: We don't actually get into the problematic part of kill_borrows_on_place as often as you might think, because there's a special dodge at the start of the function:

rust/src/librustc_mir/dataflow/impls/borrows.rs

Lines 196 to 203 in f0c2bdf

	// Handle the `Place::Local(..)` case first and exit early.
	if let Place::Base(PlaceBase::Local(local)) = place {
	if let Some(borrow_indices) = self.borrow_set.local_map.get(&local) {
	debug!("kill_borrows_on_place: borrow_indices={:?}", borrow_indices);
	sets.kill_all(borrow_indices);
	return;
	}
	}

---

You combine the two points made above, and you end up with things like the following example: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=3d29327853729ec280799760d5e58003

Click to see the example Rust code

struct List<T> {
    value: T,
    next: Option<Box<List<T>>>,
}


fn to_refs1<T>(mut list: &mut List<T>) -> Vec<&mut T> {
    let mut result = vec![];
    loop {
        result.push(&mut list.value);
        if let Some(n) = list.next.as_mut() {
            list = n;
        } else {
            return result;
        }
    }
}

fn to_refs2<T>(mut list: (&mut List<T>,)) -> Vec<&mut T> {
    let mut result = vec![];
    loop {
        result.push(&mut (list.0).value);
        if let Some(n) = (list.0).next.as_mut() {
            list.0 = n;
        } else {
            return result;
        }
    }
}

(In that example, to_refs2 is basically the same as to_refs1, except that its wrapped in a unary tuple (T,). I think the intention is that if to_refs1 is accepted, then so should to_refs2. But NLL currently accepts to_refs1 and )

[pnkfelix]

I'm not 100% sure what action is best here. I think my game plan is roughly:

• Double-check the hypothesis that on_entry is always the null-set for this part of the code.
  • If true, then removing its usage from that part of the code. (That should allow @ecstatic-morse to revise PR rustc_mir: Hide initial block state when defining transfer functions #61787 so that the statement_effect methods and friends no longer read from on_entry
• Experiment with computing the "correct" kill-set. My assumption is that doing so will increase the number of programs we accept. Hopefully it will do so without exposing soundness bugs elsewhere.
  • But even if its correct, the question will be whether we can afford, computation time-wise,. to do it in the compiler. I am currently assuming that the reason for this loop over on-entry U gen-set is to avoid trying to loop over the whole universe of bits here.
  • (Update: This is covered in PR Kill conflicting borrows of places with projections. #62010; it avoids looping over the whole universe of bits by mapping the place to its base and then feeding that into the local-to-borrows map.)
• (Also it would be good to try to evaluate whether this is even worth doing. Maybe no one cares about this oversight.)

[pnkfelix]

cc @davidtwco

[ecstatic-morse]

Currently, in the "special dodge", we loop over all borrows of that same local. Could we simply filter that list using places_conflict when we have a projection to a field?

[pnkfelix]

@ecstatic-morse I'm not sure if I understood the question, but: to support the "special dodge", we specifically build up a local_map that maps each local to all of the borrows of that local.

We don't have an analogous map for all places in a given MIR. (and I suspect we do not want to pay the time+memory expense of building up such a map.)

[pnkfelix]

or are you saying we should map each place to its base local, and then feed that into the local_map for the basis for the filter here? I hadn't considered whether that could work.

[ecstatic-morse]

Ah, so borrow_set.local_map only contains the borrows of exactly local, not local.field?

[pnkfelix]

(I think the local_map[local] does contain borrows for local.field as well as local, so this may be a reasonable way forward to computing a more complete kill-set and thus get a more accurate transfer-function for the dataflow here.)