Curiously Recurring Template Pattern

Hello. Why this code doesn't compile? I think this code declares that Self == T or I'm wrong?

trait Trait1<T: Trait1<T>> {
    fn func1(self) -> T where Self: Sized {
        return self;
    }
}

fn main() {
    
}

No it doesn’t. It requires T to implement Trait1<T>, but Self can be a different type.

Like… if I write

trait Trait1<T: Trait1<T>> {
    fn func1(self) -> T
    where
        Self: Sized;
}

struct Foo;
struct Bar;

impl Trait1<Foo> for Bar { … }

it complains, but all it needs is the additional instance Trait1<Foo> for Foo and then it works.


If you want to require T == Self though, really, you don’t need the generic argument on the trait at all. Just use trait Trait1 { … }. If this doesn’t work for your for some case, feel free to explain your circumstances, and perhaps you’re missing some syntax, like a place to put the right bound you want, or your actual use-case is somehow more complicated than a simple equality constraint.


If you’re interested in ways (or “hacks”) to somwhat express actual type equality constraints in Rust, feel free to look at this example approach I had used (and documented a bit) for a little crate.

2 Likes

you're right :sweat_smile:, I think I'm going crazy with what I'm trying to do. I tried a few differents approches, but each one fails for some reasons. It's my current code and error looks really strange for me:

use anyhow::Result;
use async_trait::async_trait;
use log::error;
use std::sync::Arc;
use tokio::sync::RwLock;

#[async_trait]
pub trait Job<T>
where
    T: Job<T>,
    T: Send + Sync,
{
    async fn job_func(job_state: Arc<RwLock<Self>>) -> Result<()>;

    fn create_job(self, time_step: std::time::Duration) -> Result<tokio_cron_scheduler::Job>
    where
        Self: Sized,
    {
        let job_state = Arc::new(RwLock::new(self));

        let job = tokio_cron_scheduler::Job::new_repeated_async(
            time_step,
            move |_uuid, _job_scheduler| {
                let job_state = job_state.clone();

                return Box::pin(async move {
                    if let Err(err) = T::job_func(job_state).await {
                        error!("{}\n{}", err, err.backtrace());
                    }
                });
            },
        )?;

        return Ok(job);
    }
}

error:

error[E0308]: mismatched types
  --> src\service\job.rs:27:51
   |
8  | pub trait Job<T>
   | ----------------
   | |             |
   | |             expected type parameter
   | found type parameter
...
27 |                     if let Err(err) = T::job_func(job_state).await {
   |                                       ----------- ^^^^^^^^^ expected `Arc<RwLock<T>>`, found `Arc<RwLock<Self>>`
   |                                       |
   |                                       arguments to this function are incorrect
   |
   = note: expected struct `Arc<tokio::sync::RwLock<T>>`
              found struct `Arc<tokio::sync::RwLock<Self>>`
   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters
note: associated function defined here
  --> src\service\job.rs:13:14
   |
13 |     async fn job_func(job_state: Arc<RwLock<Self>>) -> Result<()>;
   |              ^^^^^^^^


So if you want Self and T to be the same, and put Send + Sync bounds on Self, you can just do that:

Something like

pub trait Job
where
    Self: Send + Sync
{ … }    

is possible; though it’s also equivalent to normal supertrait syntax, i.e.

pub trait Job: Send + Sync { … }

In your example code, the Self type also needs to be 'static (as informed by the error message appearing otherwise), so let’s throw that into the mix and it works.

use anyhow::Result;
use async_trait::async_trait;
use log::error;
use std::sync::Arc;
use tokio::sync::RwLock;

#[async_trait]
pub trait Job: Send + Sync + 'static
{
    async fn job_func(job_state: Arc<RwLock<Self>>) -> Result<()>;

    fn create_job(self, time_step: std::time::Duration) -> Result<tokio_cron_scheduler::Job>
    where
        Self: Sized,
    {
        let job_state = Arc::new(RwLock::new(self));

        let job = tokio_cron_scheduler::Job::new_repeated_async(
            time_step,
            move |_uuid, _job_scheduler| {
                let job_state = job_state.clone();

                return Box::pin(async move {
                    if let Err(err) = Self::job_func(job_state).await {
                        error!("{}\n{}", err, err.backtrace());
                    }
                });
            },
        )?;

        return Ok(job);
    }
}
1 Like

I just looked this CRTP stuff to freshen up my Java knowledge again, seems like in that language for example, you’d need to resort to patterns like this to resolve a lack of “supertrait” equivalent for interfaces. And/or maybe it’s to work around the fact that you cannot freely use a “Self” type in arbitrary positions, something you can do in Rust traits.

1 Like

wow, it really works. thank you very much! now it's clear!

Not even remotely close. Yes, CRTP may be used for this, among other things. But it's true raison d'être is to upgrade inheritance inheritance foot gun and turn it into foot howitzer.

Consider something like this:

class Base {
 public:
  template<typename Self>
  auto Reduce(this Self&& self) {
    using TrueSelf = std::remove_cvref_t<Self>;
    typename TrueSelf::Value v1 = self.GetV1();
    typename TrueSelf::Value v2 = self.GetV2();
    return v1 + v2;
  }
};

Now you may not just merely make behavior of an ancestor function depend on the behavior of descendant, but you may even use types from descendant, constants from descendants, etc. Like this:

class IntBased : public Base {
 public:
  using Value = int;
  int GetV1() {
    return 2;
  }
  int GetV2() {
    return 3;
  }
};

class StringBased : public Base {
 public:
  using Value = std::string;
  std::string GetV1() {
    return "Hello, ";
  }
  std::string GetV2() {
    return "World!";
  }
};

Neat, flexible. And incredibly dangerous.

I think this is only true for C++, for other languages like C#, Java etc it won't work. It would work only if you explicit declare GetV1 and GetV2 in your Base, good examples you can check here, in all snippets code. if you want to translate this to Rust, you don't need all this magic with inheritance, because in Rust you can do it just by using Self.

You can introduce and use another class.

You can take any of them and expand like this. In C++ you have to rely on different tricks because C++ still retains some vestigial remnants of direct-to-machine-code compiler of C which means you it's not really easily possible to create two classes which depend on each other. C# and Rust don't have such limitations, but Rust doesn't include inheritance thus footgun doesn't work.

You may only translate one particular application of CRTP that way. More complicted constructs couldn't be translated. Which is not necessarily a bad thing.

The main purpose of templating this[1] in C++ is non-virtual mixins, e.g. something like[2]

struct mixin_comparable
{
 // auto operator <=>(this auto&& self, auto&& that);
    auto operator <  (this auto&& self, auto&& that) { return (self <=> that) <  0; }
    auto operator <= (this auto&& self, auto&& that) { return (self <=> that) <= 0; }
    auto operator == (this auto&& self, auto&& that) { return (self <=> that) == 0; }
    auto operator >= (this auto&& self, auto&& that) { return (self <=> that) >= 0; }
    auto operator >  (this auto&& self, auto&& that) { return (self <=> that) >  0; }
    // this should have `std::forward`s to forward rvalue reference quality, but
    // also there's no need to manually implement the comparison operators;
    // the language already provides a default impl using operator <=>
};

You can do mixins with virtual, but this unnecessarily requires going through virtual dispatch[3]. There's no need to do anything special in Rust on the other hand, beyond using trait method default bodies and Self, since trait method calls are only virtual through a dyn reference (although it does mean the dyn Ord vtable has six entries instead of only one; using a TraitExt pattern or theoretical final methods "fixes" this).

Yes, you can do lots more crazy things with CRTP in C++ due to the unconstrained textual substitution that is templates, much like roughly every feature of C++. But this style of virtual-free mixins is why the pattern was conceptualized, and the TMP style abuses came later. And as you note, it's only really necessary to do this way because of the directed declaration-before-use requirement on C++.

This is a desirable property of Rust — that features are fairly orthogonally constrained to solving specific needs in a (generally[4]) polymorphically verifiable way despite being monomorphized — that C++ lacks. But if using C++ the "intended" way and "just" writing valid code, it's a fairly reasonable language. The thesis of using Rust, though, is that being infallible the way C++ asks is unreasonable, and the compiler helping you when you make mistakes is worth the overhead of extra typing (as in type system, not keyboard). Removing (semi)implicit overhead is a nice bonus.


Yanking this somewhat back onto topic: this is an illustration of the difference of Rust's trait bound generics to C++'s templates, or even to Java / the JVM's polymorphic generics. The main one relevant one here is, of course, the ability to name (and further bound) Self in a trait definition, which names the implementing (i.e. most derived) type, not the dynamic object type. In effect, all traits are effectively CRTP; the actual semidirect "port" of Rust's trait PartialOrd into C++ would be roughly

template<typename Self, typename Rhs = Self>
concept PartialOrd = PartialEq<Self, Rhs> && requires(Self const& self, Rhs const& rhs)
{
    { self <=> rhs } -> /* exposition only concept __ComparesAs */<std::partial_ordering>;
};
template<typename Self, typename Rhs = Self>
requires PartialOrd<Self, Rhs>
struct PartialOrd_traits
{
    friend bool operator <  (Self const& self, Rhs const& rhs)
    { return (self <=> rhs) <  0; }
    friend bool operator <= (Self const& self, Rhs const& rhs)
    { return (self <=> rhs) <= 0; }
    friend bool operator >= (Self const& self, Rhs const& rhs)
    { return (self <=> rhs) >= 0; }
    friend bool operator >  (Self const& self, Rhs const& rhs)
    { return (self <=> rhs) >  0; }
};

This isn't how you'd typically actually use C++ (though circle and/or cppfront may do this kind of pattern and enable method call syntax via C++ UFCS, which Rust would actually call UMCS), but it's the closest "port" of Rust's trait semantics.


  1. "Templating this" is the category covering both CRTP (which is templating this for a class template) and deducing this (which is templating this for a member function template). ↩︎

  2. If you want to imitate trait checking more thoroughly, you can also introduce a concept which describes the mixin requirements instead of leaving it implicit, e.g.

    template<typename Self>
    concept comparison_category = requires(Self self)
    {
        { self <  0 } -> /* exposition only concept boolean-testable */;
        { self <= 0 } -> /* exposition only concept boolean-testable */;
        // … etc
    };
    template<typename Self, typename Rhs>
    concept comparable_with = requires(Self&& self, Rhs&& rhs)
    {
        { std::forward<Self>(self) <=> std::forward<Rhs>(rhs) } -> comparison_category;
    };
    struct mixin_comparable
    {
        template<comparable_with<typename Rhs> typename Self, typename Rhs>
        auto operator< (this Self&& self, Rhs&& that)
        { return (std::forward<Self>(self) <=> std::forward<Rhs>(rhs)) <  0; }
        // … etc
    };
    

    but also, for comparison specifically, just use the builtin operator defaulting and the <compare> concepts. Or use Rust instead, that's good too. ↩︎

  3. And even if the subclass uses final such that method dispatch can be devirtualized, it's no longer standard layout and the object necessarily contains a vtable pointer. Thus virtual mixins aren't "zero cost" (better called "zero runtime overhead" imo). CRTP mixins are zero cost, although they do have developer overhead, in the deferral of typechecking to template instantiation and the opening of the possible complexity space that is templating this. ↩︎

  4. Structs which are too large for the current architecture (for x86, size ≥ 231; for x86_64, size ≥ 248) are post-monomorphization errors, as are const evaluation errors (typically panic!s) in a generic context. I'm arguing for a check --strict or similar which does generic instantiation and checks for these instantiation errors without requiring continuing through to codegen — it seems fairly likely that check will continue to entirely cull unused generic const instantiations in the name of compile time, expecting them to be relatively rare "last resort" errors in practice. (I don't like this, especially given we already explicitly track dependent generic type instantiations in order to always validate their well-formedness even if the monomorphization gets culled, I'd rather const and type behave equivalently here, and not checking type WF is considered unsound, but I concede to practicality here.) ↩︎

4 Likes

in different languages CRTP works different and have different limitations of course it's not possible to extend behaviour in Rust in the same way like in C# (because Rust doesn't have inheritance) or C++ (there are no restrictions at all). And because of limitations produced by different languages you can have different power which CRTP can give you: in C++ it's give you super power but your IDE no longer understands what is happening in your code, because It's imposible to make code analysis if IDE doesn't know anything about what's type are really is. If we talking about more usable languages like C# and Java actually you can achive only really really small piece from that you can achive in C++ (and your superpower on this moment not superpower at all), but it's still help you in some rare cases. On my practice in most cases CRTP used only for cases that like in example that i gave you (without any future inheritsnce like in example which you gave me with AbstractSinglyLinkedListPlus). And if we talking about CRTP in Rust it gives you less opportunities than in C# or Java. And I think explanation from steffahn more suitable in this case because it closer to Rust. And how CAD97 say in C++ it's alternative for virtual and probably it can speedup your programm, but tradeoff is size of your binary file.