Trait constraints solver with GAT and recursive types

help
#1

Hello,

I was playing with the GAT by implementing recursive structures with generic pointer types. So far it worked well with my first attempt (a linked list, ListA) but then I tried implementing a binary tree (not shown here) and it complained about overflowing when resolving the Sized constraint for the pointer type.

I created a "simpler" version of the problem by implementing another list type (ListB). It seems the recursion is stopped when using Option<PF::Pointer<Self>>, but if someone creates a custom enum (which i needed for the tree) the solver cannot understand that "whatever T is, PF::Pointer<T> is Sized) and recurse infinitely.

Can someone explain it ? Is it a solver "bug", or is it intended (maybe Option satisfies some properties which allow the compiler to compile) ?

Here is the code and a playground link.

PS: the PhantomData import is an artefact of my various attempts to make ListB work ^^

#![feature(generic_associated_types)]

use std::{
    ops::Deref,
    sync::Arc,
    marker::PhantomData,
};

enum ArcFamily {}
enum BoxFamily {}

trait PointerFamily {
    type Pointer<T> : Deref<Target=T> + From<T> + Sized;
}

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

impl PointerFamily for ArcFamily {
    type Pointer<T> = Arc<T>;
}

type ListA<T, PF: PointerFamily> = Option<PF::Pointer<ListAElement<T, PF>>>;
struct ListAElement<T, PF: PointerFamily> {
    data: T,
    next: ListA<T, PF>,
}

enum ListB<T, PF: PointerFamily>
{
    Empty,
    Cons(PF::Pointer<ListBElement<T, PF>>),
}
struct ListBElement<T, PF: PointerFamily> {
    data: T,
    next: ListB<T, PF>,
}

fn main() {
    let la: ListA<i32, BoxFamily> = None;
    let lb: ListB<i32, BoxFamily> = ListB::Empty;
}

(Playground)

#2

Without having looked at the code in any detail at all (besides the place the error message pointed at), it appears that this workaround – that @quinedot presented recently in a similar-ish situation – works here, too.

struct Dummy<T>(T);

enum ListB<T, PF: PointerFamily>
{
    Empty,
    Cons(Dummy<PF::Pointer<ListBElement<T, PF>>>),
}

(playground)

In particular, this also means: yes, it’s a bug!

2 Likes
#3

Thank you, I though it was not the same problem but it was ^^"
At least there is a workaround :+1: