Internal compiler error: "entered unreachable code: we captured two identical projections"

[nathanwhit]

This bug popped up in CI on a project of ours. This does not reproduce on stable, but does reproduce on nightly and the latest beta (1.56.0-beta.4). Bisection shows that nightly-2021-09-26 was the first build with the regression. Further bisection points to 6867dd2 being the commit that introduced the regression. If I had to guess from the PRs in the rollup I'd say #89208 seems the most likely, since it touched the code around the error source.

Code

use std::borrow::Cow;

pub type Block = [u8];
pub type BlockAncestorBlock<'a> = Cow<'a, [u8]>;

enum Fork {
    Local,
    Foreign,
}

pub struct BlockHeader<'a> {
    pub block: Cow<'a, Block>,
}

pub struct PairedFork<'a>
{
    local_head_block: Option<BlockAncestorBlock<'a>>,
    foreign_head_block: Option<BlockAncestorBlock<'a>>,
}

impl<'a> Iterator for PairedFork<'a>
{
    type Item = (BlockHeader<'a>, BlockHeader<'a>);

    fn next(&mut self) -> Option<Self::Item> {
        let tuplify = |prev_header: Option<BlockHeader<'a>>| match prev_header {
            Some(block_header) => (
                Some(Cow::Owned(Vec::from(block_header.block))),
                Some(block_header),
            ),
            None => (None, None),
        };
        let mut advance = |fork: Fork| {
            let PairedFork {
                local_head_block,
                foreign_head_block,
            } = self;
            let (next_block, header) = tuplify(None);
            match fork {
                Fork::Local => self.local_head_block = next_block,
                Fork::Foreign => self.foreign_head_block = next_block,
            };
            header
        };
        None
    }
}

Meta

rustc --version --verbose:

rustc 1.57.0-nightly (25ec82738 2021-10-05)
binary: rustc
commit-hash: 25ec8273855fde2d72ae877b397e054de5300e10
commit-date: 2021-10-05
host: x86_64-unknown-linux-gnu
release: 1.57.0-nightly
LLVM version: 13.0.0

Error output

thread 'rustc' panicked at 'internal error: entered unreachable code: we captured two identical projections: capture1 = CapturedPlace { place: Place { base_ty: &mut PairedFork<'a>, base: Upvar(UpvarId(HirId { owner: DefId(0:24 ~ regression[aef9]::{impl#0}::next), local_id: 2 };`self`;DefId(0:26 ~ regression[aef9]::{impl#0}::next::{closure#1}))), projections: [Projection { ty: PairedFork<'a>, kind: Deref }, Projection { ty: std::option::Option<std::borrow::Cow<'a, [u8]>>, kind: Field(1, 0) }] }, info: CaptureInfo { capture_kind_expr_id: Some(HirId { owner: DefId(0:24 ~ regression[aef9]::{impl#0}::next), local_id: 91 }), path_expr_id: Some(HirId { owner: DefId(0:24 ~ regression[aef9]::{impl#0}::next), local_id: 91 }), capture_kind: ByRef(UpvarBorrow(MutBorrow, '_#30r)) }, mutability: Mut }, capture2 = CapturedPlace { place: Place { base_ty: &mut PairedFork<'a>, base: Upvar(UpvarId(HirId { owner: DefId(0:24 ~ regression[aef9]::{impl#0}::next), local_id: 2 };`self`;DefId(0:26 ~ regression[aef9]::{impl#0}::next::{closure#1}))), projections: [Projection { ty: PairedFork<'a>, kind: Deref }, Projection { ty: std::option::Option<std::borrow::Cow<'_, [u8]>>, kind: Field(1, 0) }] }, info: CaptureInfo { capture_kind_expr_id: Some(HirId { owner: DefId(0:24 ~ regression[aef9]::{impl#0}::next), local_id: 54 }), path_expr_id: Some(HirId { owner: DefId(0:24 ~ regression[aef9]::{impl#0}::next), local_id: 54 }), capture_kind: ByRef(UpvarBorrow(MutBorrow, '_#27r)) }, mutability: Mut }', compiler/rustc_typeck/src/check/upvar.rs:665:17

Backtrace

stack backtrace:
   0: rust_begin_unwind
             at /rustc/25ec8273855fde2d72ae877b397e054de5300e10/library/std/src/panicking.rs:517:5
   1: core::panicking::panic_fmt
             at /rustc/25ec8273855fde2d72ae877b397e054de5300e10/library/core/src/panicking.rs:100:14
   2: alloc::slice::<impl [T]>::sort_by::{{closure}}
   3: alloc::slice::merge_sort
   4: rustc_typeck::check::upvar::<impl rustc_typeck::check::fn_ctxt::FnCtxt>::compute_min_captures
   5: rustc_typeck::check::upvar::<impl rustc_typeck::check::fn_ctxt::FnCtxt>::analyze_closure
   6: rustc_hir::intravisit::walk_stmt
   7: rustc_hir::intravisit::walk_block
   8: rustc_hir::intravisit::walk_body
   9: rustc_infer::infer::InferCtxtBuilder::enter
  10: rustc_typeck::check::typeck
  11: rustc_query_system::dep_graph::graph::DepGraph<K>::with_task
  12: rustc_data_structures::stack::ensure_sufficient_stack
  13: rustc_query_system::query::plumbing::try_execute_query
  14: <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::typeck
  15: rustc_typeck::check::typeck
  16: rustc_query_system::dep_graph::graph::DepGraph<K>::with_task
  17: rustc_data_structures::stack::ensure_sufficient_stack
  18: rustc_query_system::query::plumbing::try_execute_query
  19: <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::typeck
  20: rustc_data_structures::sync::par_for_each_in
  21: rustc_typeck::check::typeck_item_bodies
  22: rustc_query_system::dep_graph::graph::DepGraph<K>::with_task
  23: rustc_data_structures::stack::ensure_sufficient_stack
  24: rustc_query_system::query::plumbing::try_execute_query
  25: <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::typeck_item_bodies
  26: rustc_session::utils::<impl rustc_session::session::Session>::time
  27: rustc_typeck::check_crate
  28: rustc_interface::passes::analysis
  29: rustc_query_system::dep_graph::graph::DepGraph<K>::with_task
  30: rustc_data_structures::stack::ensure_sufficient_stack
  31: rustc_query_system::query::plumbing::try_execute_query
  32: <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::analysis
  33: rustc_interface::queries::<impl rustc_interface::interface::Compiler>::enter
  34: rustc_span::with_source_map
  35: scoped_tls::ScopedKey<T>::set

query stack during panic:
#0 [typeck] type-checking `<impl at src/main.rs:21:1: 47:2>::next`
#1 [typeck] type-checking `<impl at src/main.rs:21:1: 47:2>::next::{closure#0}`
end of query stack

[nathanwhit]

@rustbot label: +regression-from-stable-to-beta

[FabianWolff]

Reduced:

pub struct S<'a> {
    o: Option<&'a i32>,
}

fn foo(s: &mut S) {
    || {
        let S { o } = s;
        s.o = None;
    };
}

[nbdd0121]

This assertion is indeed introduced in #89208. The two captures have the same place but different CaptureInfo.

cc @wesleywiser @nikomatsakis

[nikomatsakis]

Interesting. It's a bit hard to imagine how #89208 could have introduced this, since that just sorts a list. Fascinating! Maybe somebody from @rust-lang/wg-rfc-2229 has a clue?

[FabianWolff]

Actually, it's not at all hard to imagine, because #89208 introduced the following:

rust/compiler/rustc_typeck/src/check/upvar.rs

Lines 665 to 668 in d480cef

	unreachable!(
	"we captured two identical projections: capture1 = {:?}, capture2 = {:?}",
	capture1, capture2
	);

The projections are actually the same, but the types differ in regions, which probably means that this comment is wrong:

rust/compiler/rustc_typeck/src/check/upvar.rs

Lines 619 to 622 in d480cef

	// We do not need to look at the `Projection.ty` fields here because at each
	// step of the iteration, the projections will either be the same and therefore
	// the types must be as well or the current projection will be different and
	// we will return the result of comparing the field indexes.

[nbdd0121]

Yeah, I just checked and the region of the match is an inferenced variable and s.o = None gives an concrete ReFree instead.

[apiraino]

Assigning priority as discussed in the Zulip thread of the Prioritization Working Group.

@rustbot label -I-prioritize +P-critical

[nbdd0121]

Did some analysis:

• We cannot just replace the unreachable!() with Ordering::Equal. This will create two mutable references in edition 2021 and fail borrowck. Pre-2018 the places do get merged later so the issue isn't exposed.
• None of the upvar code makes use of the region info, and writeback will erase it anyway. So I think the fix should just be have the region erased when inserting/looking up from capture_information.

@wesleywiser I can submit a PR if you haven't started

[wesleywiser]

@nbdd0121 I just started looking at it but if you have a solution, go for it! Happy to review your PR 🙂

[arora-aman]

• None of the upvar code makes use of the region info, and writeback will erase it anyway. So I think the fix should just be have the region erased when inserting/looking up from capture_information.

@nbdd0121 I'm not sure about region code that much but regionchk uses the regions created:
https://github.com/rust-lang/rust/blob/master/compiler/rustc_typeck/src/check/regionck.rs#L788-L793

I think at one point mentioned getting rid of the region field entirely in UpvarBorrow, but since it wasn't required the discussion didn't proceed.

Also it's more like this is a bug of the capture analysis than the sorting. We should never have two same places going into min capture in the list.

[nbdd0121]

I was thinking about erasing the region from PlaceWithHirIds (i.e. the key of capture_information). But it turns out that's used later to create upvar tuple... So I switched capture_information from HashMap to a linear vec looked up with custom eq fn instead.