Break cycle on trait associated type

[grom]

trait Trait {
    type T;
    fn get(&mut self) -> Self::T;
}

I have implementers that want to do this

struct A;
impl Trait for A {
    type T = Box<dyn Trait>; // <-- what goes in Trait<T = ...>

Technically I want a Box<dyn Trait<T = Box<dyn Trait<T = Box<dyn Trait<T = .... on and on. Something tells me there is no way to resolve this logically, and therefore impossible for the compiler anyway. Will just have to settle on one possible return type in A::get(&mut self) -> Box<dyn Trait>. I just wanted the option to use an enum instead of Box later on.

[nerditation]

unfortunately, it is not expressible in rust's type system.

if you think the associated type Trait::T as a "type function" (or, "endofunctors" of Type -> Type), what you want is the fixed point of this "function".

in rust, we don't have higher kinded types (e.g. like haskell), associated types are really ony analogous to type functions, we cannot do what haskell can parametrically:

newtype Fix f = Fix (f (Fix f))

instead, rust associated types is ad-hoc (not a "total" type function, defined "point-wise"). I don't know what's your use case is like, but this is probably not what you want (it compiles though):

struct Fixed;
type BoxedTrait = Box<dyn Trait<T = Fixed>>;

impl Trait for Fixed {
    type T = Self;
    //...
}

impl Trait for BoxedTrait {
    type T = Self;
}

[jendrikw]

How do you plan on using the trait? Because safely doing that would run into similar issues, so I'm curious what you had in mind.

[grom]

trait Handle {
    fn handle(&self, event: &Event) -> Vec<Effect>;
}

trait Add {
    type Inner: Handle;
    fn add<'a>(&mut self, path: &'a Path, inner: Self::Inner) -> Option<Self::Inner>;
}

enum Extracted<T, T2> { This(T), Deeper(T2) }
trait Extract {
    type Inner;
    fn extract<'a>(self, path: &'a Path) -> Option<Extracted<Self, Self::Inner>> where Self: Sized;
}

struct Node<H, H2>(H, Vec<H2>);

The idea is to impl Handle for specific root types of Node

impl<H2> Handle for Node<N1, H2> { ... }
impl<H2> Handle for Node<N2, H2> { ... }
impl<H2> Handle for Node<N3, H2> { ... }
...

I want to organize the nodes into a graph data structures where they can decorate each other as implementers of Handle. A Node wrapped in a Node wrapped in a Node wrapped in a Node, etc. Passing events into the root of this graph will bubble up the events based on the structure of the graph and the returned Vec<Effect> will get treated by each Node it visits on the way back down as if applying middleware.

So I need the Node(s) to have the ability to dynamically modify their own structure. I do not want to treat each node as an explicit type with a vec that I know I can modify. At most I want to only give basic list like abilities to the nodes. Add and Extract (remove and return). I also need a Wrap. But Wrap can be achieved as a Add + Extract.

n1 -> n2 -> n5 -> n6
         -> n4

Let's say n5 wants to wrap itself in a nk. First we extract n5 from n2 by returning Effect::ExtractHandle(Path) from n5 in response to some event.
Path is a data structure that is used to traverse the graph. And n5 will construct a Path that will lead back to itself: enum Path { Here(HandleMatcher), Next(Box<Path>), AStar(HandleMatcher) }

we end up with this

(returned n5 -> n6) <- n1 -> n2 
                                -> n4

then outside the graph some calling code (with system resources and permissions that can be shared with nodes it constructs) will wrap n5 with nk

nk -> n5 -> n6

and add it back to the graph using the same path it used to Extract

n1 -> n2 -> nk -> n5 -> n6
         -> n4

[jendrikw]

I'm sorry, I don't quite see where this relates to your initial post? Which of Handle and Add corresponds to Trait?

[grom]

Then I don't understand your question. There is an overarching design that dictates I create an Extract trait the way I described it. The original post boils down an issue I am having in implementing it.

[grom]

For now I've come away with this unsatisfying solution

trait NodeHandle: Handle {
    fn extract<'a>(&mut self, path: &'a Path) -> Option<Extracted<Box<dyn NodeHandle>>>;
    // fn add..
    // other related graph methods
}

impl Handle for Box<dyn NodeHandle> {
    fn handle(&self, event: &Event) -> Vec<Effect> {
        self.as_ref().handle(event)
    }
}

impl NodeHandle for Box<dyn NodeHandle> {
    fn extract<'a>(&mut self, path: &'a Path) -> Option<Extracted<Box<dyn NodeHandle>>> {
        self.as_mut().extract(path)
    }
    // fn add..
    // other related graph methods
}

So when I eventually want to do enums instead of dynamic dispatch I would have to modify the code and comment out old boxed implementations and replace the trait and implementations with

trait NodeHandle: Handle {
    fn extract<'a>(&mut self, path: &'a Path) -> Option<Extracted<TheEnum>>;
    // fn add..
    // other related graph methods
}

and other pointer alternatives

trait NodeHandle: Handle {
    fn extract<'a>(&mut self, path: &'a Path) -> Option<Extracted<&'some_lifetime_outside_of_graph mut dyn NodeHandle>>;
    // fn add..
    // other related graph methods
}

trait NodeHandle: Handle {
    fn extract<'a>(&mut self, path: &'a Path) -> Option<Extracted<Rc<NodeHandle>>>;
    // fn add..
    // other related graph methods
}