Creating mutually exclusive generics, or Excluding specific types from a Generic Parameter

So, I have been building a little library as a coding exercise, and decided to maybe create a "Pair" type.

By Pair, in this context, I mean a pair of numbers, like 2D vectors and 2D coordinates.

To encompass these two possibilities I decided to create a couple marker structs, both implementing a marker trait PairKind to differentiate the implementations of addition and subtraction of Coordinates vs Vectors.

For example, a Pair<Coordinate> plus a Pair<Vector> would return a Pair<Coordinate>,
a Pair<Coordinate> subtracted from another Pair<Coordinate> would return a Pair<Vector>, etc.

As part of all my implementations, I thought it would be a good idea to implement conversions between these kinds of pairs, in case I need to reinterpret between these kinds of pairs.

A prototype of this code would be the following:
impl<T: PairKind, U: PairKind> From<Pair<U>> for Pair<T> { .... }

Now, this implementation would work perfectly in theory, given there wasn't already an impl<T> From<T> for T in the standard library. These implementations do indeed overlap.

Now, given I don't control the standard library, I cannot turn the standard library's implementation into a specialization of my implementation, or in other words, make my implementation a generalization of the standard library's. (AFAIK)

Thus an Idea was born in my head. What If I could force T and U not to be the same?

An implementation as such would not overlap with the existing impl:
impl<T: PairKind, U: PairKind> From<Pair<U>> for Pair<T> where T != U { .... }

One specific way of looking at this idea is creating mutually exclusive generic parameters, where T and U cannot be resolved to the same type.

Another more general way of looking at it is being able to exclude specific types in a generic bound, which in this specific case means excluding whatever type U happens to be, from the generic T.

I have attempted replicating this second idea by creating a "Is" trait, which would only be implemented for "Self == T" and not for any other type.

However, on creating this short snippet of code, which doesn't even encompass the whole idea, using #![feature(negative_impls)], the compiler told me that I couldn't implement both Is<T> and !Is<T> for T, which is not what I was doing at all...

trait Is<T> {}
impl<T> Is<T> for T {}
impl<T,U> !Is<U> for T where U: !Is<T> {}

AFAIK this idea is not negative impls alone, not negative trait bounds alone, nor specialization, nor dependent types.

Am I missing something here?
Has anyone suggested this idea before?
Is this potentially a new (somewhat useless) language feature?

Appreciate any pointers that could get me on my way to figuring this out.

How about introducing your own IntoPair<T> trait that gets implemented for each Pair<U>? You won't be using Into, but at least it'll give you a common way to convert between these pairs.

That's probably what I'll end up using for convenience's sake (or just an intrinsic method), but I imagine this could be occasionally useful in other contexts. I just wondered if any RFC described something similar.

That would be specialization, which has been plagued with soundness issues. The work is still very active, but I wouldn't expect it any time soon.

It is possible to hack something together with typenum, but the trait bounds get complicated quite quickly.

1 Like

This touches on a lot of deep areas of bounds and coherence that are hard to summarize, so largely this will be a collection of links to pursue if you are interested. The TL;DR is -- that's been considered many times, and it is desired, but we're not there yet -- probably not close.

Re: negative_impls,

  • It's the leading edge for disjoint blanket implementations, but
  • Currently they are quite limited and do not influence coherence, however
  • There is an MCP and now an initiative to integrate them into coherence
    • Which you would need for your example
    • However-however, if things haven't changed since the MCP, even this doesn't allow !Trait in a where clause yet. So that is still quite a ways out.

A more general term for basing coherence on what isn't implemented is "negative reasoning". The Rust teams are usually careful about allowing this as it is quite brittle.

A main motivator for having negative trait bounds is mutually exclusive traits. It's been proposed before, and indeed, you can read about the roots of negative_impls in the discussions.

In some of these issues, the ability to say where T != U specifically has come up, to which Niko notes:

we haven't implemented support for equality bounds yet, and for good reasons, so I wouldn't want to officially support inequality bounds. They also have interactions with inference (which is currently driven by unification). (That said, just like region bounds, I suspect we could eventually support these as a kind of "after-the-fact" check, rather than having them inform inference in any way.)

But there is one place where equality bounds are supported today -- in associated type bounds.

fn f<I: Iterator<Item=i32>>(iter: I) { /* ... */ }

So how about incorporating some negative reasoning around those bounds? Two implementations bound on explicit, distinct associated types certainly can't overlap. That has been considered as well:

6 Likes

That is a whole lot of information!
Thank you very much.

1 Like

Others have posted about 2nd half of OP. There is the alternative to the 1st.
Pair maybe does not fit well with generic use. I can't see you writing much
fn foo<T>(a: Pair<T>) or similar function.

Having regular structures CoordinatePair and VectorPair seem more fitting. Any shared implementation can be made with macro. (or composition.)

A PairKind (type marker traits) does not fit well as traits. Traits should be extending functionality, not as a way to classify as distinct.

Don't Rust and many other big libraries use marker traits extensively?

Not any fixed rule saying which way to code, just be on lookout for alternatives.

Copy Send Sized Sync Unpin all add functionality.
Sized being an odd one in that it applied by default. Unless removed;
fn foo<T: ?Sized>(

Gotcha Gotcha. I guess this could be useful to implement a kind of typestate pattern, but I get that other options may be more ergonomic in this situation.

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.