Parse and accept type equality constraints in where clauses

Opened by Jared Roesch at 2024-08-28 22:08:06

Implement the missing type equality constraint specified in the RFC.

The example from the RFC:

fn sum<I:Iterator>(i: I) -> int
  where I::E == int
{
    ...    
}

Implement the missing type equality constraint specified in RFC 135.

Examples
```
fn sum<I: Iterator>(_: I) -> i32
where
 I::Item == i32 // or `I::Item = i32`
{
 // ... 
}
```
León Orell Valerian Liehr at 2024-02-21 05:58:39

Edit: Obsoleted, see the next few comments.

Now that associated type for common traits has been landed on nightly while this issue is still open, it becomes impossible to use an iterator of a concrete type. Before this is fixed, here is a workaround (but I think this could be simplified):

#![feature(associated_types)]

struct CustomStruct {
    this: int,
    that: int,
}

fn do_something(i: int) {
    println!("{}", i);
}

// Old code
#[cfg(target_os="none")]
fn foo_old<I>(mut iter: I) where I: Iterator<CustomStruct> {
    for obj in iter {
        do_something(obj.this + obj.that);
    }
}

// New code, but doesn't work due to #20041.
/*
fn foo_new<I>(mut iter: I) where I: Iterator, <I as Iterator>::Item = CustomStruct {
    for obj in iter {
        do_something(obj.this + obj.that);
    }
}
*/

// Workaround code, inspired by http://redd.it/2r2fbl
trait Is<Sized? A> { fn this(&self) -> &A; }
impl<Sized? A> Is<A> for A { fn this(&self) -> &A { self } }
fn workaround_20041<A, B: Is<A>>(a: &B) -> &A { a.this() }

fn foo_workaround<I>(mut iter: I) where I: Iterator, <I as Iterator>::Item: Is<CustomStruct> {
    for obj in iter {
        let obj = workaround_20041::<CustomStruct, _>(&obj);
        do_something(obj.this + obj.that);
    }
}

fn main() {
    foo_workaround(vec![CustomStruct { this: 11111, that: 22222 }].into_iter());
}

</details>

kennytm at 2015-01-04 19:11:02

@kennytm You can use "associated type bindings":
```
fn foo(it: I) where I: Iterator<Item=Foo> {}
```
Jorge Aparicio at 2015-01-04 19:23:57
@japaric : Oh nice, thanks. Found this buried deeply in https://github.com/rust-lang/rfcs/blob/master/text/0195-associated-items.md#constraining-associated-types (hintupdate guidehint)
kennytm at 2015-01-04 21:38:58
@kennytm @steveklabnik would the one to talk to about the docs. It is probably a good idea to do that. Full equality constraints should be coming soon after 1.0.
Jared Roesch at 2015-01-08 21:38:34
Yes, we don't have any associated type documentation, I plan on tackling that soon.
Steve Klabnik at 2015-01-09 00:12:25
I don't think associated type bindings are quite the same as this, since they aren't taken into account for determining overlapping impls (which appears to have been intentional) http://is.gd/em2JNT
Sage Griffin at 2015-08-30 20:55:48
@sgrif Doesn't that make this a kind of duplicate of https://github.com/rust-lang/rfcs/pull/1672?

Edit: obviously with semantic differences, but I believe they allow for expressing the same types of bounds.
Taylor Cramer at 2017-01-27 20:35:14
I just ran into this limitation pretty hard while trying to do type level operations on HLists. Any work planned?

The only possible workaround I see is this bitrotted brilliant abomination https://github.com/freebroccolo/unify.rs
Tupshin Harper at 2017-02-04 01:39:01

<details> <summary>Show question (answered below)</summary> Taking this idea further (`where` on associated types), I want to do the following:

/// Helper trait for creating implementations of `RangeImpl`.
pub trait SampleRange: PartialOrd {
    type T: RangeImpl where T::X == Self;
}

/// Helper trait handling actual range sampling.
pub trait RangeImpl {
    /// The type sampled by this implementation.
    type X: PartialOrd;
    
    /// Construct self.
    /// 
    /// This should not be called directly. `Range::new` asserts that
    /// `low < high` before calling this.
    fn new(low: Self::X, high: Self::X) -> Self;
    
    /// Sample a value.
    fn sample<R: Rng+?Sized>(&self, rng: &mut R) -> Self::X;
}

The latter trait on its own does all the work. The first one is just there to make the following work without explicitly specifying the type implementing RangeImpl.

#[derive(Clone, Copy, Debug)]
pub struct Range<T: RangeImpl> {
    inner: T,
}

pub fn range<X: SampleRange, R: Rng+?Sized>(low: X, high: X, rng: &mut R) -> X {
    assert!(low < high, "distributions::range called with low >= high");
    Range { inner: X::T::new(low, high) }.sample(rng)
}

</details>

Diggory Hardy at 2017-08-05 17:09:36

@dhardy What you want is just type T: RangeImpl<X = Self>;
Sage Griffin at 2017-08-05 17:16:14
@sgrif that actually works, thanks!
Diggory Hardy at 2017-08-05 17:26:27
I would very much like to see this happen. Writing highly generic code is a pain, if you can't rename associated types inside traits, and this helps to do it, by asserting that a simple associated type is the same type as some monstrous thing: type TableQuery and where Self::TableQuery == <<Self::DbTable as HasTable>::Table as AsQuery>::Query.
Pyry Kontio at 2017-09-02 13:28:28
I recently ran into this:

where T: num::Num<FromStrRadixError = ParseIntError> works where T::FromStrRadixErr = std::num::ParseIntError doesn't

I don't fully understand the difference here

Issue I filed for num that helped me: https://github.com/rust-num/num/issues/331
spease at 2017-09-03 21:43:00
The difference is that direct equals assertions between types are not allowed, but it's possible to write trait bounds like "type Foo must have trait Qux, and that Qux's associated type must be this type Bar". This allows writing equals relations in an indirect way.

I don't know if there is any expressivity difference, but direct equality would be certainly easier to grasp.
Pyry Kontio at 2017-09-04 02:35:27
I'd like to add an additional use case. Currently this code compiles:
```
mod upstream {
 pub trait Foo<A> {
 fn execute(self) -> A;
 }
}

mod impl_one {
 use super::upstream::*;
 struct OneS;
 impl Foo<OneS> for String {
 fn execute(self) -> OneS {
 OneS {}
 }
 }
}

use upstream::*;
fn main(){
 let a = "foo".to_string().execute();
}
```
However if another implementation for string is added anywhere we get an inference error:
```
mod impl_two {
 use super::upstream::*;
 struct TwoS ;
 impl Foo<TwoS> for String {
 fn execute(self) -> TwoS {
 TwoS {}
 }
 }
}
```
error[E0282]: type annotations needed --> .\Scratch.rs:30:9 | 30 | let a = "foo".to_string().execute(); | ^ | | | consider giving a a type | cannot infer type for _

error: aborting due to previous error

I think this is a pretty strong sign that the code should have required a type annotation in the first place. Type equality constraints would be a good solution to proof that there will be no implementations for String, giving the nicer type inference:
```
mod impl_one {
 use super::upstream::*;
 struct OneS;
 impl <O> Foo<O> for String
 where O == OneS {
 fn execute(self) -> OneS {
 OneS {}
 }
 }
}
```
Iirc it isn't possible to solve this via a library because the inferred type would be something like O: EqT<OneS>
Tarmean at 2018-01-20 12:24:24
This currently seems blocked on some issues with the trait system (see https://github.com/rust-lang/rust/pull/22074#issuecomment-73678356 and https://github.com/rust-lang/rust/pull/39158#discussion_r98083316).

Barring that, there seem to be a few places where type equality constraints are not handled properly (they're actually mostly accounted for already, so it may not be a huge task to finish them off). Here are the steps I can see that need to be taken to implement this feature once the normalisation issues are sorted out:
1. Remove the error for equality constraints: https://github.com/rust-lang/rust/blob/566905030380151f90708fa340312c9ca2c6056c/src/librustc_passes/ast_validation.rs#L401-L406
2. Add the correct predicates here: https://github.com/rust-lang/rust/blob/566905030380151f90708fa340312c9ca2c6056c/src/librustc_typeck/collect.rs#L1536-L1538
3. The compiler is currently inconsistent about whether equality constraints are of the form A = B or A == B. The former seems more consistent with constraints not in where clauses. In this case, change these to single =: https://github.com/rust-lang/rust/blob/566905030380151f90708fa340312c9ca2c6056c/src/librustdoc/html/format.rs#L204-L209
4. Remove the ability to use == in equality constraints here: https://github.com/rust-lang/rust/blob/566905030380151f90708fa340312c9ca2c6056c/src/libsyntax/parse/parser.rs#L4832-L4833
5. Add a warning suggesting to use = instead of == if the latter is encountered in a where clause.
6. Add tests for equality constraints.
varkor at 2018-01-26 12:06:14

I think this can be more or less emulated with a helper trait (didn't check all possible variations of it, though):

trait Is {
    type Type;
    fn into(self) -> Self::Type;
}

impl<T> Is for T {
    type Type = T;
    fn into(self) -> Self::Type {
        self
    }
}

fn foo<T, U>(t: T) -> U
where T: Is<Type = U>
{ t.into() }

fn main() {
    let _: u8 = foo(1u8);
    // Doesn't compile:
    //let _: u16 = foo(1u8);
}

(playground link)

Léo Gaspard at 2018-08-21 05:11:23

I'd like to work on this. From my understanding, before beginning work, I'll need to consider the type system implications and effects, and detail those for approval, correct? (Issue #39158 has been resolved and merged.)
Tyler J. Laing at 2018-10-18 16:39:52
I suspect it's better to wait until the chalk integration has been completed, as this is easily implemented in chalk but is nontrivial with the current trait system (see https://github.com/rust-lang/rust/pull/22074#issuecomment-73678356 and https://github.com/rust-lang/rust/pull/39158#discussion_r98083316 for some details).
varkor at 2018-10-18 17:33:50
Any news? Now that chalk has largely landed.
Avi Dessauer at 2019-02-28 02:56:59
chalk hasn't largely landed. There's still significant integration work to be done.
varkor at 2019-02-28 09:39:04

And what about inequality constraint?

trait Trait {
    type Foo;
    type Bar;
}

struct Struct<T>(T) where T: Trait, T::Foo != T::Bar;

Félix at 2019-02-28 12:16:46

@varkor Is the status of the integration work being tracked anywhere? #48049 seems misleading in that regard.
Chris at 2019-06-30 06:50:50
@Systemcluster: probably the most relevant issue to track now is https://github.com/rust-lang/rust/issues/60471, but I don't think there's been much progress on it recently.
varkor at 2019-06-30 13:16:32
I am trying implement generalized traversing algorithm around graph and trees. So for homogeneous graphs i want restrict trait TraverseableNode like Self::Item == Self. But currently it is impossible, so in what stage is this feature now?
Dmitry Opokin at 2019-12-10 12:08:33
If my understanding is correct, it is in a large class of features blocked on chalk (the experimental trait solver), so I wouldn't expect this feature to be available for years (at the current pace, anyway)...
mark at 2019-12-10 16:39:04
I don't think the Chalk integration that would be required for this is that far off (we're talking months more than years, if I'm not mistaken)... but yes, the current pace is not so fast. Would be great to get an update from the Chalk folks, but understandably they're quite busy.
Alexander Regueiro at 2019-12-10 17:36:23
@Fihtangolz It's possible to emulate this feature using where clauses with trait bounds cleverly. You can define a trait:
```
trait TypeEquals {
 type Other;
}
```
And then implement it for stuff you want to test equality of:
```
impl TypeEquals for Node {
 type Other = Self;
}
```
And then use it in where clauses:
```
where <Node as TraversableNode>::Item: TypeEquals<Other=Node>
```
Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=739f581462096c2fecb2998fc3e74ccc

For example, Diesel uses this workaround pervasively. Support for type equality would tremendously help with wrangling with its complicated types.

Since you are already able to emulate this, maybe this could be implemented as a some kind of a sugar in the current compiler? But then again, waiting for a chalk implementation would be just a whole lot cleaner.
Pyry Kontio at 2019-12-11 03:58:44
Tagging diagnostics for the subset handled in https://github.com/rust-lang/rust/issues/20041#issuecomment-68645136: when we can translate to associated type syntax constraint, we should suggest that.

Update: #70908 handles this now.
Esteban Kuber at 2020-04-06 20:21:37
Will types with different lifetimes be considered equivalent? Foo<'a> == Foo<'b>?
Avi Dessauer at 2020-09-05 18:37:10
From a naive perspective, P==Q would imply that P is assignable by Q and Q assignable by P.

This would imply that type parameters must be invariant and so C<a1, ... an> == C<b1, ...bn> would imply a1==b1, ..., an == bn
Tarmean at 2020-09-05 18:57:17
Perhaps an alternative '== could be added that would ignore lifetimes?
Avi Dessauer at 2020-09-05 19:17:29
@Avi-D-coder, would that be useful for anything? I don't think you can do anything with two arbitrary types when you know that they only differ in lifetimes. The only case I can think of is if you already know that Foo_1=Foo<A,'a> and Foo_2=Foo<B,b'>. But in that case you would just check A=B rather than Foo_1==Foo_2.
nturton at 2020-12-30 16:20:17
@nturton The goal is to know a type and it's lifetimes are covariant. https://rust-lang.zulipchat.com/#narrow/stream/144729-wg-traits/topic/Experimenting.20with.20covariant.20associated.20types.2E

I have a detailed blog post on my use-case coming at some point.
Avi Dessauer at 2020-12-30 16:40:54

A working demo of simple type equality bounds in stable Rust:

Rust Playground

use std::marker::PhantomData;

trait TyEq {}

impl<T> TyEq for (T, T) {}

fn require_ty_eq<A, B>() where (A, B): TyEq {}

struct Z;
struct S<N>(PhantomData<N>);

fn compiles() {
    require_ty_eq::<Z, Z>();
    require_ty_eq::<S<Z>, S<Z>>();
}

fn does_not_compile() {
    require_ty_eq::<S<Z>, S<S<Z>>>();
}

Scott J Maddox at 2021-04-16 05:14:54

https://github.com/rust-lang/rust/pull/91208:
<img width="1118" alt="Screen Shot 2021-11-24 at 5 50 50 PM" src="https://user-images.githubusercontent.com/1606434/143359609-614d9c13-3a5f-4abe-867d-1720213aaf33.png">
Esteban Kuber at 2021-11-25 01:51:32
@rustbot label +T-lang +I-lang-nominated +S-tracking-design-concerns +S-tracking-unimplemented

(@jackh726 says that niko has had some concerns regarding arbitrary where clause equality constraints.)
Felix S Klock II at 2022-03-04 15:14:19
We discussed this in the lang-team meeting today. I am indeed concerned about general T = U constraints, for the reasons expressed in the minutes, but we were thinking that perhaps we could accept a more limited form of where T::Item = U or <T as Iterator>::Item = U, which would be equivalent to today's T: Iterator<Item = U>... thoughts?
Niko Matsakis at 2022-03-09 01:19:32
Accepting where T::Item = U I think is pretty easy and should only require changes at the ast and hir levels. Once astconv is called, we store a ProjectionPredicate for that.
Jack Huey at 2022-03-09 14:21:46
When was it decided to use single = instead of double == for these constraints? I'd strongly prefer the latter. With where T: Iterator<Item = U>, I see that T is an Iterator, with its Item type assigned to U, not unlike the syntax for default type parameters. And with where <T as Iterator>::Item == U, I see that we are imposing a boolean predicate on the two types. But with where <T as Iterator>::Item = U, we seem to assign a type to the projection, which seems as odd to me as assigning f() = 123.

To me, it ultimately comes down to the symmetry of the operator. <T as Iterator>::Item == U is equivalent to U == <T as Iterator>::Item, and this is clarified by the equality syntax. Conversely, T: Iterator<Item = U> is not equivalent to T: Iterator, and this is clarified by the assignment syntax. This indication of symmetry would be especially useful in bounds such as <T as Foo>::Assoc == <T as Bar>::Assoc, where currently we must write an unwieldy T: Foo<Assoc = <T as Bar>::Assoc>. So why should we use a single = in these top-level bounds?
Matthew House at 2022-04-27 20:19:25

A working demo of simple type equality bounds in stable Rust:

Rust Playground

use std::marker::PhantomData;

trait TyEq {}

impl<T> TyEq for (T, T) {}

fn require_ty_eq<A, B>() where (A, B): TyEq {}

struct Z;
struct S<N>(PhantomData<N>);

fn compiles() {
    require_ty_eq::<Z, Z>();
    require_ty_eq::<S<Z>, S<Z>>();
}

fn does_not_compile() {
    require_ty_eq::<S<Z>, S<S<Z>>>();
}

@scottjmaddox But this constraint only works on Sized types? any idea to relax this?

Ireina at 2022-11-26 06:09:37

But this constraint only works on Sized types? any idea to relax this?

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=40979a4328a4157253dbf78f501e213c
Jules Bertholet at 2022-11-26 14:33:59

The TyEq "working demo" doesn't really work though:

#![allow(unused)]

trait TyEq {}

impl<T: ?Sized> TyEq for (*const T, *const T) {}

fn convert<In, Out>(x: In) -> Out
where
    (*const In, *const Out): TyEq,
{
    // error[E0308]: mismatched types
    x
}

Most of the time, working around the lack of type equality constraint isn't too hard, but in more complicated cases it's still a problem:

struct Something<F: Foo>(F);
impl<F: Foo> Something {
    fn new<B>(b: B) -> Self
    where
        Wrap<B> == F,
    {
        Something(Wrap(b))
    }
}

The only recourse here seems to be to pass in Wrap instead of B.

Diggory Hardy at 2023-01-13 14:27:58

A simple workaround

trait TyEq<T> {
    fn rw(self) -> T;
    fn rwi(x: T) -> Self;
}

impl<T> TyEq<T> for T {
    fn rw(self) -> T {
        self
    }
    fn rwi(x: T) -> Self {
        x
    }
}

fn f<T, U>(x: T) -> U where T: TyEq<U> { // ... where T == U
    x.rw()
}

fn g<T, U>(x: T) -> U where U: TyEq<T> { // ... where U == T
    U::rwi(x)
}

Windabove at 2024-05-13 04:16:39

Most of the time, working around the lack of type equality constraint isn't too hard, but in more complicated cases it's still a problem

Actually, isn't as much of a problem, at least in the example posed. Here's a full example:
```
trait TyEq
where
 Self: From<Self::Type> + Into<Self::Type>,
 Self::Type: From<Self> + Into<Self>,
{
 type Type;
}

impl<T> TyEq for T {
 type Type = T;
}

struct Wrap(B);

trait Foo {}
struct Something<F: Foo>(F);
impl<F: Foo> Something<F> {
 fn new(b: B) -> Self
 where
 Wrap: TyEq<Type = F>, // or F: TyEq<Type = Wrap>, or both
 {
 Something(Wrap(b).into())
 }
}
```
One quirk of this approach is that it's not commutative. So F: TyEq<Type = Wrap> by itself does not imply Wrap: TyEq<Type = F> and vice versa (it has to hold, the compiler just has no idea). Which isn't a bad thing necessarily, and can be exploited for fun and profit (mandatory visible type applications, anyone?).

Another quirk in this particular implementation is that all types have to be Sized. Which is not that terrible of a limitation, but can be slightly annoying to deal with.

Not at all surprising at the end of the day, but not something you'd necessarily expect from a true equality constraint either.
Nikolay Yakimov at 2024-08-28 22:08:06

Examples