MIR-borrowck: ICE: could not find BorrowIndexs for region scope

[pnkfelix]

There are many tests in compile-fail/borrowck/ that ICE with the same failure: "could not find BorrowIndexes for region scope ..."

• You can see list of such tests in the discrepancy spreadsheet.
• But for ease of reference, I am also transcribing that list into the first comment on this issue.

My suspicion is that all of these are arising due to dataflow attempting to look up a region in a const-promoted MIR fragment (e.g. for the body of a closure is the common case, I think). Before promotion the MIR in question had references to regions that actually corresponded to some borrow within the same MIR. (And originally MIR-borrowck was running before const-promotion, which is why I did not address the problem during the original development.)

But someone should of course confirm the above hypothesis.

Assuming that hypothesis holds, the next step would be to actually fix the problem in some reasonable way. One way would be to rewrite the MIR during promotion, replacing the regions in question. But another, probably simpler (and more efficient) way to fix this could be to just make the dataflow code assume that such regions always correspond to something that spans the entirety of the MIR being analyzed. (That fix definitely requires that we confirm the above hypothesis is the only reason this ICE is arising.)

[pnkfelix]

Transcription of relevant tests according to the discrepancy spreadsheet. (caveat: data is based on out-of-date pnkfelix/mir-borrowck4 branch)

tests failing with ICE: could not find BorrowIndexes for region scope ...
borrowck-argument.rs
borrowck-assign-to-andmut-in-borrowed-loc.rs
borrowck-borrow-mut-base-ptr-in-aliasable-loc.rs
borrowck-borrowed-uniq-rvalue-2.rs
borrowck-for-loop-head-linkage.rs
borrowck-insert-during-each.rs
borrowck-issue-14498.rs
borrowck-loan-of-static-data-issue-27616.rs
borrowck-move-mut-base-ptr.rs
borrowck-move-subcomponent.rs
borrowck-ref-mut-of-imm.rs
borrowck-use-in-index-lvalue.rs
borrowck-use-uninitialized-in-cast-trait.rs
borrowck-use-uninitialized-in-cast.rs
borrowck-vec-pattern-tail-element-loan.rs

[pnkfelix]

I am going to focus on this bug.

[pnkfelix]

Hmm. Well, it was not hard to address the const-promoted case, but it turns out that is not the only case where this issue is arising.

In particular, the test borrowck-assign-to-andmut-in-borrowed-loc.rs generates the following MIR:

// MIR for `main`
// source = Fn(NodeId(29))
// pass_name = CleanEndRegions
// disambiguator = before

fn main() -> () {
    let mut _0: ();                      // return pointer
    scope 1 {
        let mut _1: isize;               // "x" in scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:23:9: 23:14
        scope 3 {
            let mut _2: S<'31_0rs>;      // "y" in scope 3 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:26:13: 26:18
            scope 5 {
                let _5: S<'31_1rs>;      // "z" in scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:27:13: 27:14
            }
            scope 6 {
            }
        }
        scope 4 {
        }
    }
    scope 2 {
    }
    let mut _3: &'31_0rs mut isize;
    let mut _4: &'31_0rs mut isize;
    let mut _6: &'31_0rs mut S<'31_0rs>;
    let mut _7: &'31_0rs mut S<'31_0rs>;
    let mut _8: (isize, bool);
    let mut _9: (isize, bool);

    bb0: {
        StorageLive(_1);                 // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:23:9: 23:14
        _1 = const 1isize;               // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:23:17: 23:18
        EndRegion('3s);                  // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:23:17: 23:18
        EndRegion('4s);                  // scope 0 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:22:11: 31:2
        EndRegion('4ds);                 // scope 0 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:22:11: 31:2
        StorageLive(_2);                 // scope 3 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:26:13: 26:18
        StorageLive(_3);                 // scope 3 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:26:34: 26:40
        StorageLive(_4);                 // scope 3 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:26:34: 26:40
        EndRegion('8s);                  // scope 3 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:26:39: 26:40
        _4 = &'31_0rs mut _1;            // scope 3 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:26:34: 26:40
        _3 = &'31_0rs mut (*_4);         // scope 3 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:26:34: 26:40
        EndRegion('9s);                  // scope 3 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:26:34: 26:40
        _2 = S<'31_0rs> { pointer: _3 }; // scope 3 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:26:21: 26:42
        EndRegion('10s);                 // scope 3 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:26:21: 26:42
        StorageDead(_3);                 // scope 3 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:26:42: 26:42
        EndRegion('11s);                 // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:25:5: 30:6
        StorageDead(_4);                 // scope 3 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:26:43: 26:43
        EndRegion('11ds);                // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:25:5: 30:6
        StorageLive(_5);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:27:13: 27:14
        EndRegion('14s);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:27:17: 27:34
        StorageLive(_6);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:27:35: 27:41
        StorageLive(_7);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:27:35: 27:41
        EndRegion('15s);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:27:40: 27:41
        _7 = &'31_0rs mut _2;            // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:27:35: 27:41
        _6 = &'31_0rs mut (*_7);         // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:27:35: 27:41
        EndRegion('16s);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:27:35: 27:41
        _5 = const copy_borrowed_ptr(_6) -> bb1; // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:27:17: 27:42
    }

    bb1: {
        EndRegion('17s);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:27:17: 27:42
        StorageDead(_6);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:27:42: 27:42
        EndRegion('18s);                 // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:25:5: 30:6
        StorageDead(_7);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:27:43: 27:43
        EndRegion('18ds);                // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:25:5: 30:6
        EndRegion('22s);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:28:23: 28:24
        EndRegion('19s);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:28:10: 28:11
        EndRegion('20s);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:28:10: 28:19
        EndRegion('21s);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:28:9: 28:19
        _8 = CheckedAdd((*(_2.0: &'31_0rs mut isize)), const 1isize); // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:28:9: 28:24
        assert(!(_8.1: bool), "attempt to add with overflow") -> bb2; // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:28:9: 28:24
    }

    bb2: {
        (*(_2.0: &'31_0rs mut isize)) = (_8.0: isize); // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:28:9: 28:24
        EndRegion('23s);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:28:9: 28:24
        EndRegion('24s);                 // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:25:5: 30:6
        EndRegion('24ds);                // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:25:5: 30:6
        EndRegion('28s);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:29:23: 29:24
        EndRegion('25s);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:29:10: 29:11
        EndRegion('26s);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:29:10: 29:19
        EndRegion('27s);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:29:9: 29:19
        _9 = CheckedAdd((*(_5.0: &'31_1rs mut isize)), const 1isize); // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:29:9: 29:24
        assert(!(_9.1: bool), "attempt to add with overflow") -> bb3; // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:29:9: 29:24
    }

    bb3: {
        (*(_5.0: &'31_1rs mut isize)) = (_9.0: isize); // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:29:9: 29:24
        EndRegion('29s);                 // scope 5 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:29:9: 29:24
        EndRegion('30s);                 // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:25:5: 30:6
        EndRegion('30ds);                // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:25:5: 30:6
        _0 = ();                         // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:25:5: 30:6
        EndRegion('31_1rs);              // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:25:5: 30:6
        StorageDead(_5);                 // scope 3 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:30:6: 30:6
        EndRegion('31_0rs);              // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:25:5: 30:6
        StorageDead(_2);                 // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:30:6: 30:6
        EndRegion('31s);                 // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:25:5: 30:6
        EndRegion('32s);                 // scope 1 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:25:5: 30:6
        EndRegion('33_0rs);              // scope 0 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:22:11: 31:2
        StorageDead(_1);                 // scope 0 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:31:2: 31:2
        EndRegion('33s);                 // scope 0 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:22:11: 31:2
        EndRegion('34s);                 // scope 0 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:22:11: 31:2
        EndRegion('34ds);                // scope 0 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:22:11: 31:2
        EndRegion('34as);                // scope 0 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:22:1: 31:2
        goto -> bb4;                     // scope 0 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:31:2: 31:2
    }

    bb4: {
        EndRegion('34cs);                // scope 0 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:22:1: 31:2
        return;                          // scope 0 at ../src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs:31:2: 31:2
    }
}

The problem that I can see in the above MIR is that the region denoted by '31_1rs has no direct borrows. Instead we see it appear in a couple of cast expressions, of the form(_5.0: &'31_1rs mut isize).

Was this an oversight in the borrows-dataflow? Should casts to a type have "gen-bits" for all the regions that appear in the target type?

Update: On further reflection the latter suggestion does not seem to make all that much sense. At the very least, the borrows-dataflow is meant to track the actual kind and location of the borrow ... but the regions at the surface of a type do not necessarily map back to any specific borrow that we can see at this point in the analysis.

[pnkfelix]

Had discussion with @arielb1 (transcribed in details below) who convinced me the right direction here is to remove the assert (and skip attempting to update the flow state in these cases).

user	message
arielby	pnkfelix: re, gh44828
	why are you getting errors related to '31_1rs?
pnkfelix	arielby: because there is an EndRegion('31_1rs)
	arielby: and the code is conservatively panicking since it does not expect to see EndRegions for regions that have no borrows.
arielby	so I suppose the reasoning that regions must have borrows was incorrect
	because, as you can see, regions don't need to have borrows
pnkfelix	arielby: so I am trying to work through the logic of what should actually be happening here. (e.g. maybe the EndRegion should just be ignored, or eliminated earlier on)
arielby	becaues of subtyping
	pnkfelix: nah
	the code is
	z = copy(&mut y);
	right
	let z = copy(&mut y); ...
pnkfelix	arielby: yep
arielby	and regionck happily assigns z a region shorter than the &mut y
	because it can
	the &mut y is forced to live for longer than needed because of the lifetime constraint in copy_borrowed_ptr
	if a region doesn't appear in any borrow
	that just means borrowck doesn't need to care about it
	regionck still does, but because we know it succeeded, we know all of its constraints held
pnkfelix	so then do you think I can kill this part of the clean_end_regins visitor : https://github.com/rust-lang/rust/blob/master/src/librustc_mir/transform/clean_end_regions.rs#L70 ?
arielby	I mean, we could pick a different consistent region assignment
	if we wanted
	that squashes all regions to the nearest containing borrow
	and it wouldn't matter to borrowck
	but there's no reason to do it
	pnkfelix: that depends on whether you want the code to be type-checkable as a unit
	or you only care about borrow-checking
pnkfelix	hmm
arielby	e.g. I think MIR validation might care about "free" regions
pnkfelix	okay I think I know what I'll do about this then.
arielby	just remove the assert?
pnkfelix	well my plan was instead to have the EndRegion know whether it is in a function that has a borrow, vs a function that just uses the region in types
arielby	why do you care?
pnkfelix	arielby: because I am irrationally attached to the assert.
arielby	I don't see any reason the assert is connected to soundness
	and as it appears, removing the assert has its problems
pnkfelix	arielby: The assert occurs in a lookup associated with processing EndRegion
	arielby: so I interpret "remove the assert" as "let the lookup silently fail"
arielby	where's the assert?
pnkfelix	arielby: which is the right thing to do at least in the case of regions whose borrows solely occurred within MIR expressions that have been const-promoted...
arielby	pnkfelix: I mean
	if you don't care about a region
	you don't care about its EndRegions
	while computing dataflow
	so you don't need to track anything
pnkfelix	arielby: the main place where the assert fires s here: https://github.com/rust-lang/rust/blob/master/src/librustc_mir/dataflow/impls/borrows.rs#L126
arielby	found it
	if a region has 0 borrows, borrowck doesn't care about it
	you don't need the assert
pnkfelix	arielby: so by "silently fail", I also mean "skip attempting to kill any bits"
arielby	umm it's an index
pnkfelix	which is the kind of thing that is fine to do as long as we understand all the cases where it is arising.
arielby	self.region_map.entry(region).or_insert(FxHashSet())
	from a "soundness" POV, if it fails
	that just means there's a region without any borrows pointing to it
	which is, well, not a problem
	and there are no borrows to end
	so we should just not end any borrow
	or just do the or_insert thing also for EndRegion statements
pnkfelix	arielby: I think the basic issue is that you are making the point that the code will be correct by definition ("we want to track borrows. If we see no borrows, then we have nothing to update")
arielby	while?
pnkfelix	arielby: I wanted to understand the situations where regions are ending up in EndRegion statements and yet have no borrows.
	arielby: you have pointed out one that is obvious in hindsight (subtyping)
arielby	sure I can see why that would be interesting
	but subtyping is a good enough reason to remove the assert
	because if you allow "subtyping" as a possibility, it's hard to distinguish from other cases
pnkfelix	arielby: anyway, I think I agree with you that just removing the assert (and declaring the code correct by definition) is both a small and obviously correct PR.
	arielby: and that if I actually do want to undertake the aforementioned exercise, it is something I can do independently of such a PR.
arielby	sure
pnkfelix	arielby: so I will just do that.
arielby	+1

[arielb1]

For the record, the case we found was this:

rust/src/test/compile-fail/borrowck/borrowck-assign-to-andmut-in-borrowed-loc.rs

Lines 1 to 31 in 67ed489

	// Copyright 2012 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.
	// Test that assignments to an `&mut` pointer which is found in a
	// borrowed (but otherwise non-aliasable) location is illegal.
	struct S<'a> {
	pointer: &'a mut isize
	}
	fn copy_borrowed_ptr<'a>(p: &'a mut S<'a>) -> S<'a> {
	S { pointer: &mut *p.pointer }
	}
	fn main() {
	let mut x = 1;
	{
	let mut y = S { pointer: &mut x };
	let z = copy_borrowed_ptr(&mut y);
	*y.pointer += 1; //~ ERROR cannot assign
	*z.pointer += 1;
	}
	}