Rust: Parse and accept type equality constraints in where clauses

[jroesch]

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
{
    ...    
}

[kennytm]

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());
}

[japaric]

@kennytm You can use "associated type bindings":

fn foo<I>(it: I) where I: Iterator<Item=Foo> {}

[kennytm]

@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)

[jroesch]

@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.

[steveklabnik]

Yes, we don't have _any_ associated type documentation, I plan on tackling that soon.

[sgrif]

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

[cramertj]

@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.

[tupshin]

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

[dhardy]

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)
}

[sgrif]

@dhardy What you want is just type T: RangeImpl<X = Self>;

[dhardy]

@sgrif that actually works, thanks!

[golddranks]

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.

[spease]

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

[golddranks]

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.

[Tarmean]

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>

[varkor]

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.

[Ekleog]

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)

[ZerothLaw]

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.)

[varkor]

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).

[Avi-D-coder]

Any news? Now that chalk has largely landed.

[varkor]

chalk hasn't largely landed. There's still significant integration work to be done.

[Boiethios]

And what about inequality constraint?

trait Trait {
    type Foo;
    type Bar;
}

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

[Systemcluster]

@varkor Is the status of the integration work being tracked anywhere? #48049 seems misleading in that regard.

[varkor]

@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.

[godcodehunter]

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?

[mark-i-m]

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)...

[alexreg]

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.

[golddranks]

@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.

[estebank]

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.

[Avi-D-coder]

Will types with different lifetimes be considered equivalent?
Foo<'a> == Foo<'b>?

[Tarmean]

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

[Avi-D-coder]

Perhaps an alternative '== could be added that would ignore lifetimes?