ICE with recursive type using GAT.

[tmccombs]

Code

#![feature(generic_associated_types)]
use std::rc::Rc;
use std::ops::Deref;

trait PointerFamily {
    type Pointer<T>: Deref<Target=T> + Sized;
    
    fn new<T>(obj: T) -> Self::Pointer<T>;
}

#[derive(Debug)]
struct RcFamily;

impl PointerFamily for RcFamily {
    type Pointer<T> = Rc<T>;
    
    fn new<T>(obj: T) -> Rc<T> {
        Rc::new(obj)
    }
}

#[derive(Debug)]
enum Node<T, P: PointerFamily> where P::Pointer<Node<T, P>>: Sized {
    Cons(T, P::Pointer<Node<T, P>>),
    Nil
}

type List<T, P> = <P as PointerFamily>::Pointer<Node<T, P>>;
type RcList<T> = List<T, RcFamily>;
type RcNode<T> = Node<T, RcFamily>;

impl<T, P: PointerFamily> Node<T, P> where P::Pointer<Node<T, P>>: Sized {
    fn new() -> P::Pointer<Self> {
        P::new(Self::Nil)
    }
    
    fn cons(head: T, tail: P::Pointer<Self>) -> P::Pointer<Self> {
        P::new(Self::Cons(head, tail))
    }
}

fn main() {
    let mut list: RcList<i32> = RcNode::<i32>::new();
    list = RcNode::<i32>::cons(1, list);
    //println!("{:?}", list);
    
}

Meta

rustc --version --verbose:

note: rustc 1.56.0-nightly (a6ece5615 2021-08-03) running on x86_64-unknown-linux-gnu

note: compiler flags: -C embed-bitcode=no -C codegen-units=1 -C debuginfo=2 --crate-type bin

Error output

   Compiling playground v0.0.1 (/playground)
warning: value assigned to `list` is never read
  --> src/main.rs:44:5
   |
44 |     list = RcNode::<i32>::cons(1, list);
   |     ^^^^
   |
   = note: `#[warn(unused_assignments)]` on by default
   = help: maybe it is overwritten before being read?

error: internal compiler error: compiler/rustc_codegen_llvm/src/context.rs:812:17: failed to get layout for `&rc::RcBox<Node<i32, RcFamily>>`: the type `Node<i32, RcFamily>` has an unknown layout

Backtrace

thread 'rustc' panicked at 'Box<dyn Any>', compiler/rustc_errors/src/lib.rs:1034:9
stack backtrace:
   0: std::panicking::begin_panic
   1: std::panic::panic_any
   2: rustc_errors::HandlerInner::bug
   3: rustc_errors::Handler::bug
   4: rustc_middle::ty::context::tls::with_opt
   5: rustc_middle::util::bug::opt_span_bug_fmt
   6: rustc_middle::util::bug::bug_fmt
   7: <rustc_codegen_llvm::context::CodegenCx as rustc_target::abi::LayoutOf>::spanned_layout_of
   8: core::ops::function::impls::<impl core::ops::function::FnMut<A> for &mut F>::call_mut
   9: <core::iter::adapters::chain::Chain<A,B> as core::iter::traits::iterator::Iterator>::fold
  10: <alloc::vec::Vec<T> as alloc::vec::spec_from_iter::SpecFromIter<T,I>>::from_iter
  11: <rustc_target::abi::call::FnAbi<&rustc_middle::ty::TyS> as rustc_middle::ty::layout::FnAbiExt<C>>::new_internal
  12: <rustc_target::abi::call::FnAbi<&rustc_middle::ty::TyS> as rustc_middle::ty::layout::FnAbiExt<C>>::of_instance
  13: rustc_codegen_llvm::mono_item::<impl rustc_codegen_ssa::traits::declare::PreDefineMethods for rustc_codegen_llvm::context::CodegenCx>::predefine_fn
  14: rustc_codegen_llvm::base::compile_codegen_unit::module_codegen
  15: rustc_query_system::dep_graph::graph::DepGraph<K>::with_task
  16: rustc_codegen_llvm::base::compile_codegen_unit
  17: rustc_codegen_ssa::base::codegen_crate
  18: <rustc_codegen_llvm::LlvmCodegenBackend as rustc_codegen_ssa::traits::backend::CodegenBackend>::codegen_crate
  19: rustc_interface::passes::QueryContext::enter
  20: rustc_interface::queries::Queries::ongoing_codegen
  21: rustc_interface::queries::<impl rustc_interface::interface::Compiler>::enter
  22: rustc_span::with_source_map
  23: rustc_interface::interface::create_compiler_and_run
  24: scoped_tls::ScopedKey<T>::set

[jackh726]

Minimized a bit

#![feature(generic_associated_types)]

trait PointerFamily {
    type Pointer<T>;
}

struct Rc<T>(Box<T>);
struct RcFamily;

impl PointerFamily for RcFamily {
    type Pointer<T> = Rc<T>;
}

#[allow(dead_code)]
enum Node<T, P: PointerFamily> where P::Pointer<Node<T, P>>: Sized {
    Cons(P::Pointer<Node<T, P>>),
}

fn main() {
    let _list: <RcFamily as PointerFamily>::Pointer<Node<i32, RcFamily>>;
}

[jackh726]

Okay so this works:

Cons(<RcFamily as PointerFamily>::Pointer<Node<T>>, T),

this fails:

Cons(T, <RcFamily as PointerFamily>::Pointer<Node<T>>),

[jackh726]

Another even more minimized example

#![feature(generic_associated_types)]

trait PointerFamily {
    type Pointer<T>;
}

struct RcFamily;

impl PointerFamily for RcFamily {
    type Pointer<T> = Box<T>;
}

enum Node<T> where <RcFamily as PointerFamily>::Pointer<Node<T>>: Sized {
    //Cons(<RcFamily as PointerFamily>::Pointer<Node<T>>, T),
    Cons(T, <RcFamily as PointerFamily>::Pointer<Node<T>>),
}

fn main() {
    let _list: Box<Node<i32>>;
}

Okay, so ultimately, this ends up being very similar to #80626.

At some point or another, depending on specific variations of this test, we require that Node<T> is Sized. This is hairy (I'll get to that shortly), but basically, we can't. This is a problem, and we run into a layout error here:

rust/compiler/rustc_middle/src/ty/layout.rs

Line 574 in ae90dcf

_ => return Err(LayoutError::Unknown(unsized_part)),

We probably should be giving a smarter error here; enums should always be sized.

Okay, so now to explain why we can't prove that Node<T> is Sized:
So Node looks like

enum Node<T> where <RcFamily as PointerFamily>::Pointer<Node<T>>: Sized {
    Cons(T, <RcFamily as PointerFamily>::Pointer<Node<T>>),
}

to prove this is Sized, we only have to prove that <RcFamily as PointerFamily>::Pointer<Node<T>> is Sized. Let's imagine the where clause wasn't there. Then, it might be obvious that we could get a recursive cycle (it's a bit complicated, but we do). However, supposedly that where clause is supposed to help us, right? Well...no.

There's a few problems here. But one problem is that when we collect the size predicates, we try to eagerly normalize them here. That alone isn't a problem, but it means we can't use that where clause. But, to normalize, we have to check that RcFamily: PointerFamily, we also require that T: Sized, so Node<T>: Sized; so, even projecting gives us problems!

A simple solution here is to change the associated type definition to be type Pointer<T: ?Sized>;

I'm not sure removing the eager normalization call above would itself be enough. We theoretically can normalize, we specifically don't want to (and anywhere else that tries will run into more problems; this includes if the param_env attempts to normalize before proving the sized predicate!).

[Alexendoo]

No longer ICEs since #85868

[jackh726]

Woah. Unexpected.