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 rust-lang/rfcs#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:
rust-num/num#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 #22074 (comment) and #39158 (comment)).

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:

   rust/src/librustc_passes/ast_validation.rs

   Lines 401 to 406 in 5669050

   	for predicate in &g.where_clause.predicates {
   	if let WherePredicate::EqPredicate(ref predicate) = *predicate {
   	self.err_handler().span_err(predicate.span, "equality constraints are not yet \
   	supported in where clauses (#20041)");
   	}
   	}

2. Add the correct predicates here:
   

   rust/src/librustc_typeck/collect.rs

   Lines 1536 to 1538 in 5669050

   	&hir::WherePredicate::EqPredicate(..) => {
   	// FIXME(#20041)
   	}

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 =:
   

   rust/src/librustdoc/html/format.rs

   Lines 204 to 209 in 5669050

   	&clean::WherePredicate::EqPredicate { ref lhs, ref rhs } => {
   	if f.alternate() {
   	clause.push_str(&format!("{:#} == {:#}", lhs, rhs));
   	} else {
   	clause.push_str(&format!("{} == {}", lhs, rhs));
   	}

4. Remove the ability to use == in equality constraints here:
   

   rust/src/libsyntax/parse/parser.rs

   Lines 4832 to 4833 in 5669050

   	// FIXME: Decide what should be used here, `=` or `==`.
   	} else if self.eat(&token::Eq) || self.eat(&token::EqEq) {

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 #22074 (comment) and #39158 (comment) 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;