Resolving infinite generic type recursion in traits for pointer types

I'm doing some benchmarking on garbage collected pointer libraries. To do so, I'd like to have a generic trait for working with these pointers, which I'm calling Gc. Here's the full mockup implementation I have so far:

use std::{cell::RefCell, ops::Deref};

pub trait Gc<T>: Deref<Target = T> + Clone {
    fn new(x: T) -> Self;
    fn collect();
}

/// A `MuliRef` is a data structure I'm using for benchmarking.
/// It contains garbage-collected pointers to other `MultiRef`s.
pub struct MultiRef<G: Gc<Self>>(pub RefCell<Vec<G>>);

However, it's actually impossible to instantiate a MultiRef as a value. Here's a broken example:

impl<T> Gc<T> for Rc<T> {
    // blah blah....
}

let m: MultiRef<Rc<_>> = MultiRef(RefCell::new(Vec::new()));

It's impossible to create a type definition for m that is actually resolvable, due to the fact that the type of m once expanded is infinitely long. Is there a way to resolve this?

How about not making the trait generic?

pub trait Gc: Deref + Clone {
    fn new(x: <Self as Deref>::Target) -> Self;
    fn collect();
}

Barring that, you shouldn't put the bound on the struct definition in the first place.

Depending on how complicated your actual use case is, you can potentially use another trait with a generic associated type.

Playground

#![allow(dead_code, unused, clippy::explicit_auto_deref)]

use std::{cell::RefCell, ops::Deref, rc::Rc};

pub trait Gc<T>: Deref<Target = T> + Clone {
    fn new(x: T) -> Self;
    fn collect();
}

/// A "factory" trait that allows you to instantiate an arbitrary type of the pointer via a generic associated type
pub trait Ptr {
    type New<T>: Gc<T>;
}

/// A `MuliRef` is a data structure I'm using for benchmarking.
/// It contains garbage-collected pointers to other `MultiRef`s.
pub struct MultiRef<P: Ptr>(pub RefCell<Vec<P::New<MultiRef<P>>>>);

impl<T> Gc<T> for Rc<T> {
    fn new(x: T) -> Self {
        todo!()
    }

    fn collect() {
        todo!()
    }
}

// Implement the "factory" trait for some type representing each pointer family. For simplicity I'm using the pointer type with a pointee of the unit type, but you could also define an `RcPtr` unit struct or something.
impl Ptr for Rc<()> {
    type New<T> = Rc<T>;
}

fn check() {
    let m: MultiRef<Rc<()>> = MultiRef(RefCell::new(Vec::new()));

    let i: &MultiRef<Rc<()>> = &*m.0.borrow()[0];
}

This would be most useful if you needed multiple kinds of Rc inside MultiRef.

This is exactly what I'm trying to do. Thank you!

Rust GC libraries tend to use the arena concept. Here's a way to model that:

pub trait Arena {
    type Ptr<T>: Deref<Target = T> + Clone;

    fn collect(&self);
    fn alloc<T>(&self, x: T) -> Self::Ptr<T>;
}

pub struct MultiRef<A: Arena>(
    pub RefCell<Vec<A::Ptr<Self>>>);

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.