How do I name a type that constrains an associated type of a generic parameter to Self?

help
1

I'm writing code that has taken the following shape:

use std::marker::PhantomData;
use std::ptr::NonNull;

trait Trait {
    type T;
    // ...  
}
struct C<T> {
    field: std::vec::Vec<T>,
}
impl<T> Trait for C<T> {
    type T = T;
    //...
}

struct A<B: Trait<T = Self>>(NonNull<B>, PhantomData<B>);

And now, I'd like to actually use my A using C as the generic parameter. type T = A<C<Self>>; represents what I want, except using Self in a type alias isn't allowed. How do I give a name to the type I want, i.e. "an A using C"?

I'm trying to use this type as a field in another struct, so, I need some way to name the type. However, in my (currently limited) knowledge of Rust, it doesn't seem syntactically possible to actually apply A to C. (It may be possible to apply A to a trait object type or something, but, what I'm actually implementing is basically just a tree-based data structure so anything that's going to compile to extra indirect calls is not usable.)

2

What are you trying to do? The code snippet by itself doesn't make the intent very clear.

3

Sorry, struggling with discourse, accidentally hit enter before asking my question. I'm currently updating the post. Sorry! Alright, it's a real question now :stuck_out_tongue:

4

Trying to satisfy the bounds leads to an infinitely recursive type, A<C<A<C<A<C<A<C<A<C<....>>>>>>>>>>.

What's the practical thing you're trying to accomplish?

5

Yes, I'm trying to define a tree-like datastructure, so an infinitely recursive type is expected. I believe Rust is capable of dealing with such functional datastructures... just maybe not quite as what I'm doing with associated type bounds?

(I just changed my example C.field to an array of Ts, to make it clearer that my recursive type doesn't necessarily imply an infinite physical chain of As & Cs)

6

You'll need some sort of indirection, something like a Option<Box<Node>>.

struct Node<T> {
    left: Option<Box<Self>>,
    right: Option<Box<Self>>,
    value: T,
}

See also the documentation here.

(I haven't tried to connect this back to your OP, but have to leave the keyboard for now I'm afraid.)

7

Thanks! I'm aware of Box and the like, however they don't solve the problem of type recursion in a bounded associated type. My example does posses the necessary indirection, in that A only contains a pointer to other data.

8

Can you provide a more complete example that attempts to utilize the bound? The recursive bound won't work, but there may be a practical solution to what you're trying to achieve. (T never bottoms out, and there is no name for such an infinite type; types must resolve at compile time.)

(You don't need to edit your OP; forum conversations tend to flow more linearly.)

9

If you are trying to define a tree of types, then you will have to do it recursively, practically using a unit or uninhabited type as the base case (the point being that there has to be a base case). For example, a type-level binary tree might look like this:

trait TreeNode {
    type Left: TreeNode;
    type Right: TreeNode;
    
    fn print(indent: usize);
}

struct Nil;

impl TreeNode for Nil {
    type Left = Nil;
    type Right = Nil;
    
    fn print(indent: usize) {
        println!("{: >width$}", "Nil", width = indent * 4);
    }
}

impl<L, R> TreeNode for (L, R)
where
    L: TreeNode,
    R: TreeNode,
{
    type Left = L;
    type Right = R;
    
    fn print(indent: usize) {
        println!("{: >width$}", "Node", width = indent * 4);
        L::print(indent + 1);
        R::print(indent + 1);
    }
}
3 Likes
10

Ah yeah, if Rust doesn't support recursion in bounds like this, then that's just the answer to the question. Oh well. I suspect this is an obvious consequence of monomorphization, but clearly I need to spend more time thinking about it :P.

Thanks for the help! (And also thanks for offer to help with practical solutions, but I'll explore alternatives on my own for a while :smiley:)

11

Rust does support recursion in types, but you left out the base case.

12

Hmm yeah, there may be a way to avoid the issue I'm running into by explicitly drawing out the type-level tree like this; it's clear here how that in this construction, every type will have a finite "name". It's somewhat different from my current approach, but if I abandon it I'll look further into this. Thanks for the suggestion!

13

I'm not clear on what this means. Is there a trait implementation that could be added to my example that would allow me to define an "A<C<Self>>"? As I understand it, no "base case" (that would cause the type to have a finite non-recursive "name") exists, for my purposes... for example, what if the runtime structure of the objects I was creating was a graph containing cycles?

(I'm not actually interested in modeling cycles with types. Just trying to understand whether it's possible or not to solve my problem anywhere close to along the lines that I was originally trying.)

14

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.