Generic type recursion in linked list or tree structure

Hi,
I have two structs in Rust like follows:

pub struct Node {
    flag: Flag,
    inner: Mutex<NodeInner>,
}

pub struct NodeInner {
    size: usize,
    child: Option<Box<Node>>,
}

These form a structure similar to a linked list. Now I want to make the Mutex generic so that users can choose any lock they want to use. The code would look something like this:

pub struct Node<Lock: MyLock<NodeInner<Lock>>> {
    flag: Flag,
    inner: Lock,
}

pub struct NodeInner<Lock: MyLock<NodeInner<Lock>>> {
    size: usize,
    child: Option<Box<Node<Lock>>>,
}

In which the MyLock<T> is a trait to abstract the lock.
However, this is obviously ugly and will introduces a recursive problem with the generic parameters, such as:

let a = Node<Mutex<NodeInner<Mutex....>>>::new();

If I want to implement this abstraction correctly, how should I go about it?

sounds like a use case for GAT, you first define the trait (MyLock<T> in your example) as the interface for the lock types, then you also need a trait with GAT as bound for the generic type parameter, something like:

/// the abstraction
trait MyLock<T> {
    //....
}
/// the "selector"
trait LockSelector {
    type Lock<T>: MyLock<T>;
}
/// usage:
pub struct Node<S: LockSelector> {
    flag: Flag,
    inner: S::Lock<NodeInner<S>>,
}
pub struct NodeInner<S: LockSelector> {
    size: usize,
    child: Option<Box<Node<S>>>,
}
// example:  std::sync::Mutex
impl<T> MyLock<T> for Mutex<T> {
    //...
}
/// selector or tag for std::sync::Mutex
struct StdMutexSelector;
impl LockSelector for StdMutexSelector {
    type Lock<T> = Mutex<T>;
}
// usage
let a = Node::<StdMutexSelector>::new();
5 Likes

This is a viable solution and it has resolved my issue. Thank you very much! I learned a lot from your answer.

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.