Rust struct field generic over Deref<Target=Self>

user_14888790 0
Viewed 272

I'm trying to build Rust code that manipulates a recursive (tree-like) data structure. Naively, one could define it as

struct ALinkedList {
    value: i32,
    next: Option<Box<Self>>
}

To experiment with different memory layouts and separate algorithm design from storage, I'd like to generalize the definition to something like

struct ALinkedList<D: Deref<Target=Self>> {
    value: i32,
    next: Option<D>
}

but when trying to construct an instance of ALinkedList, I get

64 |     let t: ALinkedList<Box<_>> = ALinkedList{value: 0, next: Some(Box::new(ALinkedList{value: 0, next: None}))};
   |            ^^^^^^^^^^^^^^^^^^^ cyclic type of infinite size

My questions are:

  1. Is it possible to make these recursive type definitions work in Rust?
  2. If not, what other design patterns can I use to represent a tree-like struct without hardcoding how its children are stored and dereferenced in memory?
rust
1 Answers

Unfortunately Rust can't deal with infinitely deep generics currently.

There's a way around using GAT (Generic Associated Types), unfortunately still nightly-only (playground):

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

struct ALinkedList<A: Allocator> {
    value: i32,
    next: Option<A::Allocated<Self>>
}
impl<A: Allocator> ALinkedList<A> {
    fn set_next(&mut self, next: Self) {
        self.next = Some(next.into()) // create a new allocation via From
    }
}

trait Allocator {
    type Allocated<T>: Deref<Target=T> + From<T>;
}

struct BoxAllocator;
impl Allocator for BoxAllocator {
    type Allocated<T> = Box<T>;
}

fn main() {
    let mut t: ALinkedList<BoxAllocator> = ALinkedList{value: 0, next: Some(Box::new(ALinkedList{value: 0, next: None}))};
    t.set_next(ALinkedList{value: 1, next: None});
}
user_26047080
Related