Structured Type Parameters

language design
1

I very often run into situations like this.

The first problem:

Repeatedly defining generic parameters.

trait CoordinationStrategy<'a: 'b, 'b, T: Token, D: Direction> {
    type Runner: RunStrategy<'a, 'b, T, D>;
    fn run(runner: Self::Runner) -> <Self::Runner as RunStrategy<'a, 'b, T, D>>::Result;
}
trait RunStrategy<'a: 'b, 'b, T: Token, D: Direction> {
    type Result: RunResult;
}
trait RunResult {}
...

struct CoordinatorA<'a: 'b, 'b, T: Token, D: Direction> {
    ...
}
impl<'a: 'b, 'b, T: Token, D: Direction> CoordinationStrategy<'a, 'b, T, D> for CoordinatorA<'a, 'b, T, D> {
    type Runner = RunnerA<'a, 'b, T, D>;
    ...
}


struct RunnerA<'a: 'b, 'b, T: Token, D: Direction> {
    ...
}
impl<'a: 'b, 'b, T: Token, D: Direction> RunStrategy<'a, 'b, T, D> for RunnerA<'a, 'b, T, D> {
}

Code like this is probably 80% of what I spend my time on at this point, because it is so difficult to change (and because the remaining parts of Rust are mostly very concise). I want to use generics because without them I would have even more duplicate code, but in my opinion they are not developer friendly yet.

There are a few problems with this syntax, one is that we have to redefine the generic parameters we are using in each impl we want to use them. This doesn't scale well as we can see here. It may be fine for one or two type parameters, but at some point you are just repeating these same characters everywhere.

<'a: 'b, 'b, T: Token, D: Direction>

So whenever the parameters change, we need to go to all places using them and change them, which may be arbitrarily many.

(Search and replace sounds like the solution, and it helps, but you still have to step through each occurrence and decide if the change is actually correct depending on the context, because you may be using the same parameter signature with different meanings. It is not a good solution. If you are still not convinced, then why do we use functions at all? we could just copy/paste the code everywhere and search and replace changes.)

The second problem:

repeatedly referencing type parameters. A similar problem to the first one occurs when passing type parameters to a type or function:

RunStrategy<'a, 'b, T, D> for RunnerA<'a, 'b, T, D>

Again, having to change this twice for each implementation using these parameters takes a lot of time where your brain is basically stalling the whole time.

The third problem:

referencing associated types of traits.

<Self::Runner as RunnerStrategy<'a, 'b, T, D>>::Result

There is no way to shorten this, and it also scales with the depth of the reference, so you could imagine something like

<<Self::Runner as RunnerStrategy<'a, 'b, T, D>>::Result as RunResult<'a, 'b, T, D>>::OkType

Combined with the repeated generic parameters this becomes a major part of the code which is very difficult to maintain.

Ideas for solutions:

The first problem would be solved if you could have an identifier for a type parameter definition, kind of like a compile time type parameter structure:

(I didn't think about the syntax too much, open to suggestions)

params CoordRun = <'a: 'b, 'b, T: Token, D: Direction>;

now we could replace all generic parameter definitions with its name.

To solve the second problem, we could reference the type parameters of the current implementation with a keyword:

trait CoordinationStrategy<CoordRun> {
    type Runner: RunStrategy<Self.params>;
    fn run_ok(runner: Self::Runner) -> <<Self::Runner as RunnerStrategy<Self.params>>::Result as RunResult<Self.params>::OkType;
}

I.e. here we reference the type parameters to the trait with Self.params. In an implementation of the trait, where Self would not refer to the trait but the type implementing it, this could be replaced with CoordinationStrategy.params:

impl<CoordRun> CoordinationStrategy<CoordRun> for CoordinatorA<CoordRun> {
    type Runner = RunnerA<CoordinationStrategy.params>; // CoordRun also works here
    ...
}

So here, CoordinatorA could also take other parameters but we can still reference the parameters to CoordinationStrategy independently. Also using CoordRun in this case would be sufficient, because they are equal to the params of CoordinationStrategy.

The point of having a name for referencing the current trait's parameters or the current type's parameters is to have one place less to change when the parameters change. In a trait where the trait's type parameters are used many times and you end up changing their name eventually, it is nice not having to change each reference to them too.

Earlier I mentioned that CoordinatorA could also take other parameters next to CoordRun. This raises the question, how do we combine type parameter structs with "atomic" type parameters? I imagine a type parameter struct could be used just as an atomic type parameter:

impl<CoordRun, T> CoordinationStrategy<CoordRun> for CoordinatorA<CoordRun, T> {
    type Runner = RunnerA<CoordRun>;
    ...
}

Notice also that even though CoordRun contains a parameter named T, we can still use that name because we reference the T in CoordRun with CoordRun.T.

So it is also possible to use parts of a type parameter struct in an implementation. Nesting type parameter structs also comes naturally:

params Time = <CoordRun.D, S: Step>; // equivalent to <D: Direction, S: Step>
params Exec = <CoordRun, Time, Log>;

Basically anything possible with atomic type parameters should be possible with type parameters referenced inside a type param struct, so also extending their trait bounds:

params Time = <CoordRun.D: StepDirection, S: Step>; // = <D: Direction + StepDirection, S: Step>

Also the evaluation of this syntax should basically simply expand the names to the actual inner parameters, so as far as I can tell there would not be anything new possible with this, it is just that the same thing can be achieved with less code complexity.

Moving on to the third problem, referencing associated types of traits. Here the problem is, we can't use an associated type of a trait directly, because a type could implement multiple traits which each use the same name for an associated type. But we can define a scoped alias referring to an associated type:

trait CoordinationStrategy<CoordRun> {
    type Runner: RunStrategy<Self.params>;
    alias Result = <Self::Runner as RunnerStrategy<Self.params>>::Result;
    alias OkType = <Self::Result as RunResult<Self.params>::OkType;
    fn run(runner: Self::Runner) -> Self::Result;
    fn run_ok(runner: Self::Runner) -> Self::OkType;
    ...
}

Now it is very easy to use these associated types somewhere in our trait structure as often as we like and changing them all is very quick.

With all of this the code from the beginning becomes this:

params CoordRun = <'a: 'b, 'b, T: Token, D: Direction>;

trait CoordinationStrategy<CoordRun> {
    type Runner: RunStrategy<Self.params>;
    alias Result = <Self::Runner as RunStrategy<Self.params>>::Result;
    fn run(runner: Self::Runner) -> Self::Result;
}
trait RunStrategy<CoordRun> {
    type Result: RunResult;
}
trait RunResult {}
...

struct CoordinatorA<CoordRun> {
    ...
}
impl<CoordRun> CoordinationStrategy<CoordRun> for CoordinatorA<CoordRun> {
    type Runner = RunnerA<CoordRun>;
    ...
}

struct RunnerA<CoordRun> {
    ...
}
impl<CoordRun> RunStrategy<CoordRun> for RunnerA<CoordRun> {
}

Which does not only scale better but is also more readable.

I think a system similar to this would make generics much easier to use in Rust. Hopefully this little write-up helps.

5 Likes
2

Maybe the final reserved keyword could be used instead of alias, since it means "this class defines this method/static and no subclass can override it" in some other languages (Java, C++). final could also be used for all the other trait associated items.

For example, instead of your proposal:

trait CoordinationStrategy<CoordRun> {
    type Runner: RunStrategy<Self.params>;
    alias Result = <Self::Runner as RunStrategy<Self.params>>::Result;
    fn run(runner: Self::Runner) -> Self::Result;
}

it'd be this

trait CoordinationStrategy<CoordRun> {
    type Runner: RunStrategy<Self.params>;
    final type Result = <Self::Runner as RunStrategy<Self.params>>::Result;
    fn run(runner: Self::Runner) -> Self::Result;
}
1 Like
3

A few notes.

Actually there is. I learnt that trick from the proptest crate.

type ResultFor<'a, 'b, T, D, Ty> = <Ty as RunnerStrategy<'a, 'b, T, D>>::Result;

Similarly, one can rewrite this

<<Self::Runner as RunnerStrategy<'a, 'b, T, D>>::Result as RunResult<'a, 'b, T, D>>::OkType

into this

type OkTypeFor<'a, 'b, T, D, Ty> = <ResultFor<'a, 'b, T, D, Ty> as RunResult<'a, 'b, T, D>>::OkType

You can already do something similar today, though not as pretty, and you cannot hide the lifetimes (which is arguably a benefit):

trait CoordRun {
    type T: Token;
    type D: Direction;
}

trait CoordinationStrategy<Params: CoordRun> {
    type Runner: RunStrategy<Params>;
    fn run_ok(runner: Self::Runner) -> <<Self::Runner as RunnerStrategy<Params>>::Result as RunResult<Params>::OkType;
}

What was a reference to the parameters T, D in your code would become Params::T, Params::D.

It's not pretty, and I have a hunch that it will cause downstream problems (associated types in Rust don't play nice with some other features, like trait objects and impl traits), but you can already do it.

In general, you should really ponder whether you need all those generics in your API. Rust is quite generic-averse, it's not Java. You will get a much more complex API with complex parameters and bounds. You won't really be able to encapsulate the implementation details. If the generics leak into your public API, it is very easy to cause a blowup in code size and compile times. Generic structs can cause issues with orphan rules.

While generics are often the best solution, if you can make your API specific, maybe with some duplication and macros, then you should generally prefer it.

7 Likes
4

Neat, I didn't realize this trick. Already helps me a lot in my library.

About creating a trait:

this helps when you are dealing with multiple type parameters, but unfortunately it doesn't help with lifetimes. Earlier I did this because I usually had one lifetime at most, but since I needed multiple lifetimes I found no way to counter repetition. If there were something like associated lifetimes we could put them into a trait and implement that for some type we use to parameterize the generic items.

So along the lines of

trait CoordRun {
    type T: Token;
    type D: Direction;
    lifetime 'a: Self::'b;
    lifetime 'b;
}
struct CoordRunParams<'a: 'b, 'b, T: Token, D: Direction> {
    _ty: std::marker::PhantomData<(&'a T, &'b D)>,
}
impl<'a: 'b, 'b, T: Token, D: Direction> CoordRun for CoordRunParams<'a, 'b, T, D> {
    type T = T;
    type D = D;
    lifetime 'a = 'a;
    lifetime 'b = 'b;
}
type CoordRunA<'a: 'b, 'b> = CoordRunParams<'a, 'b, TokenA, DirectionA>;
...
let runner = RunnerA::<CoordRunA>::new(); // lifetime elision?

But this doesn't work and we would need to do:

trait CoordRun<'a: 'b, 'b> {
    type T: Token;
    type D: Direction;
}

And thus anything expecting a generic CoordRun would need to declare 'a: 'g, 'g to parameterize it.

struct RunnerA<'a: 'b, 'b, P: CoordRun<'a, 'b>> {
    ...
}

So possibly something akin to associated lifetimes would solve this? Because still, if you are using CoordRun a lot and the lifetimes change, you must go to each occurrence like this

<'a: 'b, 'b, P: CoordRun<'a, 'b>>

or

CoordRun::<'a, 'b>::Item

and change it, while for the types you can just change the definition of CoordRun.

1 Like
5

Lifetimes put strong restrictions on the way an API can be used in Rust. For this reason it is generally believed that lifetime parameters must be very explicit and in your face. Lifetime elision rules are an exception, with the understanding that the actual lifetimes can be uniquely and easily reconstructed.

The thing you want seems also very closely related to GATs. Despite the optimism in the blog post, they are still not stable, and I'm not sure how much longer it will take. In any case associated lifetimes look more complex and problematic than more simple GATs, e.g. it's unclear to me how they would interfere with type inference.

For these reasons I wouldn't count on seeing associated lifetimes in the language anywhere in the next few years. AFAIK there is even no accepted RFC to do such a thing, although I remember seeing some discussions about the possibility.

Generally the way to deal with lifetime proliferation is to use owned types, or to push some data to the function's caller. While possible and sometimes useful, lifetimes on structs are generally an antipattern. Generally they are on optimization which allow to avoid extra clones via borrows. They do come with a load of problems though, so you should really ponder whether they are worth the pain, or whether you can just live with owned data and some extra clones. Remember that Rc and Arc can make the cost of cloning negligible in many use cases.

For example, I don't see the lifetimes used inside of the trait and type definitions that you provided.

1 Like
6

They're part of RFC 0195.

2 Likes
7

Thanks, I knew I saw them in some popular place. Looks dead in the water, though. Nothing like associated livetimes is currently in the language, even for impl blocks, and they would certainly require a separate rfc.

1 Like
8

Isn't that a case for Contexts and capabilities in Rust - Tyler Mandry ?
I know, this doesn't answer your immediate problem.

1 Like
9

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.