Is this a Curiously Recurring Template Pattern?

I was experimenting with Rust's generic trait system to see what's possible and wrote the code below which is similar to one of the snippets on this post by @nikomatsakis.

First define a type Matryoshka (as in the dolls) which just takes a generic type and owns one instance of it.

struct Matryoshka<T> {
    x: T,
}

Then define a trait Onion, which just means the objects are layered: you can peel a layer or pile on a layer.

trait Onion<T> {
    fn pile(self) -> Matryoshka<Matryoshka<T>>;
    fn peel(self) -> T;
}

impl<T> Onion<T> for Matryoshka<T> {
    fn pile(self) -> Matryoshka<Matryoshka<T>> {
        Matryoshka::<Matryoshka<T>> { x: self }
    }
    fn peel(self) -> T {
        self.x
    }
}

To my surprise, this code compiles and works fine. The examples here really demonstrate what is happening: Playground.

However, I would like to learn more about what are the hidden costs that I'm not aware of. How would you recommend benchmarking this code? My initial goal was to implement this using C++ templates (so far I've failed), and I'm really curious to know what are the pros and cons of Rust when it comes to such a construction.

Is there a simpler or more efficient way of implementing this? One thing I'm not super happy about is that not only the implementation of Onion, but even its definition involves the type Matryoshka, which if possible I'd like to abstract away. Is there away to do so?

If Rust had generic associated types, you'd be able to do:

trait Onion<T> {
    type Wrapper<U>;
    fn pile(self) -> Self::Wrapper<Self::Wrapper<T>>;
    fn peel(self) -> T;
}

impl<T> Onion<T> for Matryoshka<T> {
    type Wrapper<U> = Matryoshka<U>;
    fn pile(self) -> Self::Wrapper<Self::Wrapper<T>> { ... }
    fn peel(self) -> T { ... }
}

I believe GATs are in the works, but aren't currently in the language.

2 Likes

Building upon @asymmetrikon's version you could do:

struct Matryoshka<T>(T);

trait Onion<T> {
    type Wrapper;
    fn pile(self) -> Self::Wrapper;
    fn peel(self) -> T;
}

impl<T> Onion<T> for Matryoshka<T> {
    type Wrapper = Matryoshka<Self>;
    
    fn pile(self) -> Self::Wrapper {
        Matryoshka(self)
    }
    fn peel(self) -> T {
        self.0
    }
}
3 Likes

Ah, here's why it works:

  • impl<T> Onion<T> for Matryoshka<T>, this means that for any type which is contained in a Matryoshka you can call the following functions (pile and peel) on the Matryoshka.
  • Therefore, pile will allow us to wrap the contents in another Matryoshka because it falls under the implementation generic over T, but only if we can somehow produce a Matryoshka, which in this case is self.
  • Peel on the other hand is okay with anything being returned, therefore it doesn't have to produce a Matryoshka, so it can just unwrap our Matryoshka

As to why you get the same size for every Matryoshka we pile: What else would there be to store at runtime? Rust has no built in reflection so there's no type data, and the compiler is free to optimize away.

As to making it a nicer model, while keeping the Onion<T> trait mostly intact: Ack! This is mostly identical to @leudz's implementation, I just added a few checks to make sure you can't return an illogical value.

use std::ops::Deref;

struct Matryoshka<T>(T);

//You could use a marker trait if you would like to prevent actual Derefing
impl<T> Deref for Matryoshka<T> {
    type Target = T;
    fn deref(&self) -> &T {
        &self.0
    }
}

trait Onion<T>: Deref<Target = T> + Sized {
    type Wrapper: Deref<Target = Self>;
    fn pile(self) -> Self::Wrapper;
    fn peel(self) -> T;
}

impl<T> Onion<T> for Matryoshka<T> {
    type Wrapper = Matryoshka<Matryoshka<T>>;
    fn pile(self) -> Self::Wrapper {
        Matryoshka(self)
    }
    fn peel(self) -> T {
        self.0
    }
}

There are not too many as far as I'm aware of, they're just functions that are called by moving a Self into them. The only cost you could incur is a compilation time cost if you repeat it say, 1000 times?

I'm not 100% familiar with templates, all that I know is that they're kind of fake generics, in that the typename passed is essentially copy/pasted everywhere it's referenced and hope for no errors...

2 Likes

Sure, why wouldn't it?

This doesn't appear to be related to the Curiously Recurring Template Pattern, though. CRTP has to do with inheriting from a base class parameterized with Self. Rust doesn't have classes or inheritance, so the idiom really doesn't translate. My understanding is that it's mostly used for two things: 1) to achieve compile time polymorphism in ways that Rust supports natively through traits, and 2) to do clever things with inheritance, which Rust doesn't have at all.

You just have a struct that contains a generic T and can be wrapped and unwrapped. Unless I am missing something, this would work fine in C++ without CRTP, or without inheritance at all, really.

2 Likes

I agree with @trentj.

The CRTP is when you have a type Derived that inherits from Base<Derived>. For example

class Base {
    virtual void foo() = 0;
    void call_foo_twice() {
        foo();
        foo();
    }

    Wrapper<Base> wrap() const {
        return { *this };
    }
}

This snippet showcases a couple of use cases:

  • call_foo_twice must use dynamic dispatch to call foo.
  • wrap is forced to return Wrapper<Base>. For derived types, however, it might be more preferable to return Wrapper<Derived>.

The CRTP fixes these problems by letting the type of Derived be known:

template<typename Derived>
class Base {
    virtual void foo() = 0;
    void call_foo_twice() {
        Derived& derived = static_cast<Derived&>(*this);
        foo();
        foo();
    }

    Wrapper<Derived> wrap() const {
        Derived& derived = static_cast<const Derived&>(*this);
        return { derived };
    }
}

But in rust, we don't use base classes for dynamic polymorphism. We use traits. When you implement a trait, you already know the Self type: (which is effectively the "zeroth" type parameter to every trait)

trait Trait {
    fn foo(&mut self);
    fn call_foo_twice(&mut self) {
        self.foo(); // <-- this is statically dispatched
        self.foo();
    }

    fn wrap(self) -> Wrapper<Self> { // <-- we can name Self
        Wrapper(self)
    }
}

So by and large, Rust doesn't need the CRTP.

4 Likes