where clauses are only elaborated for supertraits, and not other things

Opened by Aaron Turon at 2024-04-17 01:46:12

The following example:

trait Foo<T> {
   fn foo(&self) -> &T;
}

trait Bar<A> where A: Foo<Self> {}

fn foobar<A, B: Bar<A>>(a: &A) -> &B {
   a.foo()
}

fails with "error: type &A does not implement any method in scope named foo".

This UFCS variant

trait Foo<T> {
    fn foo(&self) -> &T;
}

trait Bar<A> where A: Foo<Self> {}

fn foobar<A, B: Bar<A>>(a: &A) -> &B {
    Foo::foo(a)
}

fails with "error: the trait Foo<_> is not implemented for the type A".

cc @nikomatsakis @jroesch

Possibly related to https://github.com/rust-lang/rust/issues/20469 but it is not fixed by where clauses. I'm seeing this on nightly, but was led there from a problem on master.
Aaron Turon at 2015-01-07 00:40:55
Note, this blocks the transition from BorrowFrom to Borrow. Not a blocker for alpha, though.
Aaron Turon at 2015-01-07 00:41:31

Sorry, but I don't see why this should work without an explicit A: Foo<B> bound in the foobar function. trait Bar<A> where A: Foo<Self> is the same as trait Bar<A: Foo<Self>>, so this seems consistent with how bounds have always worked. To show an example with bounds on structs:

#![crate_type = "lib"]

// these two are equivalent
struct Rev1<I> where I: DoubleEndedIterator {
    it: I,
}

struct Rev2<I: DoubleEndedIterator> {
    it: I,
}

// these two don't work because `Rev<I>` doesn't imply that `I: DoubleEndedIterator`
fn foo1<I>(mut rev: Rev1<I>) {
    rev.it.next_back();
}

fn foo2<I>(mut rev: Rev2<I>) {
    rev.it.next_back();
}

// even these won't work unless you explicitly add `I: DoubleEndedIterator` as a bound
fn bar1<I>(mut rev: Rev1<I>) {}
fn bar2<I>(mut rev: Rev2<I>) {}

I skimmed over the where clause RFC, and I didn't see anything about propagating bounds just for traits. Am I missing something?

Jorge Aparicio at 2015-01-07 01:38:05

@japaric My assumption that this would work was based partly on conversations with @nikomatsakis after the initial RFC. In particular, we've discussed that trait Foo: Bar should be equivalent to trait Foo where Self: Bar in most respects, and from that one would further expect other bounds to apply. But currently these are not equivalent:
```
trait Foo<T> {
    fn foo(&self) -> &T;
}

//trait Bar<A> where Self: Foo<A> {}  <--- this produces an error
trait Bar<A>: Foo<A> {}

fn foobar<A, B: Bar<A>>(b: &B) -> &A {
    b.foo()
}
```
That seems inconsistent and I don't know of any good reason for it. (And of course it's a pain to have to rewrite bounds everywhere when those bounds must already hold.)

I do take your point that in general we do not propagate bounds, but I think we want to head toward more propagation, as in http://smallcultfollowing.com/babysteps/blog/2014/07/06/implied-bounds/ -- and I thought we'd already started down this road.
Aaron Turon at 2015-01-07 04:29:26
@japaric It is also my understanding (from conversations with @nikomatsakis) that this should work. It seems related to the generalization of bounds checking.

One of the annoyances I started purging from the compiler is the ParamBounds struct which is still used to store the super traits bounds declared on a trait definition. This is one of (if not the last) place where we still have special treatment of bounds (modulo my open PR). It is my hunch that the bounds checking code introduces all super trait bounds but doesn't do anything with the ones declared in the where clause.

I think this is an important question to resolve generally because like @aturon it was my understanding that any super trait bound should be identical to bounding the Self type with the same bound. I believe Niko and I had talked about needing to make some more reaching changes to support this, and if I recall correctly it was around the computing of super trait bounds.

In my imagined scheme we should probably collect any Self type constraints and introduce them like we have been with super trait bounds. It seems this would be the simplest strategy, and avoids introducing a breaking change for anyone relying on the current behavior (esp. if this isn't resolved pre-1.0).
Jared Roesch at 2015-01-07 09:43:29
I think this is a grey area :) At present we only "elaborate" supertraits (meaning Self : Foo). This case is not a "supertrait". However, limiting ourselves to elaborating supertraits is fairly arbitrary (and, in fact, easily lifted). I can do an experiment in this area if it will speed along the BorrowFrom to Borrow transition. I agree it's not exactly blocking alpha but I'd love to kill the old_orphan_check and old_impl_check "features" (maybe that's unrealistic).
Niko Matsakis at 2015-01-07 10:06:24
@aturon

In particular, we've discussed that trait Foo: Bar should be equivalent to trait Foo where Self: Bar

So I was missing a piece of information.

That seems inconsistent and I don't know of any good reason for it.

I agree with this. But want to point out that this second example is a "supertrait", whereas the first one is not. So having to explicitly add the B: Foo<A> bound in the first case is consistent with today's rules.

I do take your point that in general we do not propagate bounds, but I think we want to head toward more propagation

I'm not opposed to having implied bounds, but I would like it to be implemented in a general way (such that my struct bounds example would also compile), instead of making it more ad hoc ("we only propagate bounds on traits with where-clause bounds that have a Self parameter on either side" or something like that)

@nikomatsakis

I think this is a grey area :) At present we only "elaborate" supertraits (meaning Self : Foo). This case is not a "supertrait".

I agree!

However, limiting ourselves to elaborating supertraits is fairly arbitrary (and, in fact, easily lifted)

I think that at this point in time supertraits are ingrained in rustaceans' minds as something natural even if they are arbitrary. In fact, I just realized that it's a (very) special case of implied bounds.

Thanks everyone for their explanations!
Jorge Aparicio at 2015-01-07 14:10:53

Not sure if it is related, but this doesn't work either:

use std::ops::*;

trait Vector<S> where
    for<'a, 'b> &'a Self: Add<&'b Self>,
    for<'a> &'a Self: Mul<S>,
{
    fn test(&self) {}
}

fn test<S, V: Vector<S>>(v: V) { v.test() }

<anon>:10:36: 10:42 error: the trait `for<'b, 'a> core::ops::Add<&'b V>` is not implemented for the type `&'a V` [E0277]
<anon>:10 fn test<S, V: Vector<S>>(v: V) { v.test() }
                                             ^~~~~~
<anon>:10:36: 10:42 help: see the detailed explanation for E0277
<anon>:10:36: 10:42 error: the trait `for<'a> core::ops::Mul<S>` is not implemented for the type `&'a V` [E0277]
<anon>:10 fn test<S, V: Vector<S>>(v: V) { v.test() }
                                             ^~~~~~

http://is.gd/FgFAWo

This is needed for cgmath to move full to operators, and remove our ugly mul_s-style methods :(

Brendan Zabarauskas at 2015-09-30 06:37:35

@bjz

Same "issue"
Ariel Ben-Yehuda at 2015-09-30 21:25:03
I ran into this issue as well, and was really surprised by it. One situation where it would be very useful is refining traits that are used in higher-kinded trait bounds like in this example: https://gist.github.com/anonymous/e3a8fe834bb383504bb4

If we don't propagate associated type bounds for where clause traits, I don't know how to actually put the bound I need in the linked example on the function: the bound itself is polymorphic over the lifetime, which seems to not be expressible in the grammar. So, it seems that without this propagation there are useful bounds that we can't express.
Russell McClellan at 2015-10-27 02:46:51
@russellmcc what bound are you unable to express precisely?
Niko Matsakis at 2015-10-28 14:37:50
In that example, I want to say that T: for<'a> Iterable<'a, Item=u32>, and in addition to that, for all 'a, <T as Iterable<'a>>::Iter implements the ExactSizeIterable<Item=&'a u32> trait. Unless I'm missing something, that can't currently be expressed. If we weren't talking about higher-kind bounds, I could add another free type variable E: ExactSizeIterable<&'a u32>, and then bound T::Iter=E, but that doesn't work because in this situation E would have to be higher kind, and there's no way to bound equality for higher kinded types that I know of.

Making the trait bounds propagate for associated types would allow me to express the exact same bound in a convenient way, as in my previous example.
Russell McClellan at 2015-10-28 22:42:30
I ran into something like this trying to create an AddAny supertrait, for all the variations of x + y, x + &y, &x + y, and &x + &y. The bounds I put on &Self as the left side of an Add won't propagate. It's pretty surprising to me that T: AddAny doesn't imply all of its transitive constraints, instead of just those on Self. https://users.rust-lang.org/t/traits-with-self-bounds/4033
Josh Stone at 2015-12-22 02:56:36
There's at least one category of non-supertrait where clauses that should be elaborated according to an accepted RFC but are not.

In RFC-0195 there's mention of where clauses on associated types (non-supertrait projections from Self?) being assumptions for user code (which translates to me as 'elaborated').

While the exact syntax of the RFC is unimplemented, current behavior is that the placement of trait bounds on an associated type in both the trait where clause and on the associated type are equivalent. e.g.
```
trait A { type B: C; }
```
and
```
trait A where Self::B: C { type B; }
```
Are the same today with respect to trait bound elaboration.

Thus where clauses on associated types should be elaborated according to the RFC's specification when considered alongside today's behavior (±syntax), but they're currently not. For example, by my understanding, this code on the Rust playground should work, as the From bound could just as well have appeared in a production of RFC-0195's WHERE_CLAUSE for associated types.

Beyond that it's further arbitrary decisions (e.g. I'd like to see the RFC's note on where clauses extended to where clauses on supertrait's associated types), but at the very very least defining a new associated type should be allowed the comforts of elaboration.
soltanmm at 2015-12-24 06:52:56
@soltanmm Your code is placing a restriction on the associated type of a supertrait (where <Self::B as Q>::U: From<usize>), which is not elaborated.
Jonas Schievink at 2015-12-24 10:39:48
@jonas-schievink Please read RFC-0195 and re-read my note to see why I believe that's the wrong behavior.

In particular, this line:

The BOUNDS and WHERE_CLAUSE on associated types are obligations for the implementor of the trait, and assumptions for users of the trait

The WHERE_CLAUSE is among the assumptions user code ought to make. The relevant predicate in the example I gave is a bound on an associated type defined within the trait (or, rather, an associated type within an associated type defined within the trait), which by analogy as given in my previous post should be allowed in the where clause for the trait itself.

The current supertrait-only behavior seems like a cultural momentum phenomenon (or oversight, or what-have-you) rather than something following from the accepted RFCs.
soltanmm at 2015-12-24 20:04:24
Has there been any more discussion on the lang team about this lately? Is this something that is just missing a proper RFC?
Sage Griffin at 2016-06-13 13:06:25
@sgrif There hasn't been any discussion, no. This is also (loosely) related to the implied bounds proposal.

Rather than starting immediately with an RFC, I'd suggest perhaps opening up a discuss thread with some motivating examples/rationale for any change -- or some other way of drawing a bit more visibility. If we can build some consensus there, then we could proceed to an RFC.
Aaron Turon at 2016-06-21 18:02:10
@aturon @sgrif I opened a thread about a motivating example some time ago.
Vinzent Steinberg at 2016-06-22 13:29:54
I ran into the same issue as well: https://users.rust-lang.org/t/creating-alias-for-bounds/7145. As someone relatively new to Rust, It was a bit surprising to see.
Charlie Ozinga at 2016-09-03 06:45:59
Hi, if anyone ran into this problem and was interested in a working solution (or rather hack), I'd like to share mine. The solution is quite complicated, but the high-level code does not get polluted by the boilerplate where clauses, but instead only by annotations. My approach is generation of the where clause by use of a proc_macro, which leads to a slightly better-looking code (and raises another problem described -- and partially solved -- in the gist). https://gist.github.com/p4l1ly/6dbcb40fb3bbb450598876b068762939

As proc_macros are not hygienic, you'll also lose some guarantees...
Pavol Vargovčík at 2018-10-23 11:51:25
any progress?
Jacob Lifshay at 2019-07-21 07:46:23

It seems worth noting that in some cases with associated types you can work around this by duplicating them to trade off verbosity at the definition+impl instead. Taking some examples from this thread:

ex1

-trait ExactSizeIterable<'a> : Iterable<'a> where Self::Iter : ExactSizeIterator {}
+trait ExactSizeIterable<'a> : Iterable<'a, Iter=<Self as ExactSizeIterable<'a>>::Iter> {
+    type Iter: ExactSizeIterator<'a>;
+}

ex2

-trait A where Self::B: Q, <Self::B as Q>::U: From<usize> {
+trait A {
+    type U: From<usize>;
+    type B: Q<U=Self::U>;
 
     fn b() -> Self::B;
 }

arcnmx at 2019-09-10 03:26:19

Interestingly this issue doesn't affect trait aliases. I don't know if it's possible but couldn't the compiler use the same logic to elaborate the where clauses in normal traits? I would expect them to work the same.

#![feature(trait_alias)]

trait Foo<T: ?Sized> {
   fn foo(&self) -> &T;
}

trait Bar<A> where A: Foo<Self> {}

// This doens't compile
// fn foobar_original<A, B: Bar<A>>(a: &A) -> &B {
//   a.foo()
// }

trait BarAlias<A> = Bar<A> where A: Foo<Self>;
// This does compile
fn foobar_alias<A, B: BarAlias<A>>(a: &A) -> &B {
  a.foo()
}

trait BarAliasExt<A>: BarAlias<A> {}
// This also compiles
fn foobar_super<A, B: BarAliasExt<A>>(a: &A) -> &B {
  a.foo()
}

Giacomo Stevanato at 2020-08-28 14:34:50

One other case where this appears (#85243):

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=e13f9ef0a5c88c03fca13d57418f4986
```
pub trait Trait1 {
    fn f();
}

pub trait Trait2 {
    type Type: Trait1;
}

pub trait Trait3 {
    type Type2: Trait2<Type = Self>;
    fn f2() {
        <Self as Trait1>::f();
    }
}
```
I expected to see this compile successfully since in Trait3, Self is guaranteed to implement Trait1 because Self = Trait2::Type and Trait2::Type: Trait1.

Instead, this happened:
```
error[E0277]: the trait bound `Self: Trait1` is not satisfied
```
Jacob Lifshay at 2021-05-13 17:14:39
Would it be feasible to lint and point folks to this issue? Or is that just as hard as elaborating would be?
Josh Stone at 2021-09-10 16:58:04

Another related snippet (I guess). Also not sure if this would be fixed by implied_bounds.

trait Foo: Iterator
where
    Self::Item: Default,
{
}

fn bar<T>(_: T)
where
    T: Foo,
    // Why the necessity of this bound? `Foo` already implies `Item: Default`
    T::Item: Default
{
}

Caio at 2022-04-01 19:36:57

I'm running into this. Specifically something along the lines of:
```
pub trait A {
/// lots of associated types with trait bounds
}

pub trait B : A 
where
/// constrains A's associated types further
{
}
```
For any impl block that is generic over a type that implements B I have to restate the where clause on B (assuming the added bounds on the associated types of A are used). This doesn't scale well as the number of types on A increases.

Is there an idiomatic workaround? The best I could think of is to restate the associated types, but this still seems suboptimal.
Justin Restivo at 2023-03-09 14:48:53
The best I could think of is to restate the associated types, but this still seems suboptimal.

That is the only workaround I know of. I would be very surprised if there was another way.
Jonas Platte at 2023-03-09 16:32:10
As a relatively new Rust user I just ran into this and found it super confusing, and seemingly inconsistent; in fact, I assumed it was a bug and tried upgrading to nightly to see if it went away. I want to emphasize that encountering this in the wild didn't simply feel like another thing that Rust doesn't support (cf. GADTs or arithmetic on type-level constants), but rather it felt strongly like a bug.

As mentioned in the issue title, the distinction is that "bounds on associated type are not super traits", and "only super traits are propagated", but this is not a satisfactory answer from a (this!) user point of view. Indeed, I didn't even have a precise concept of "super trait" in mind before I found the explanation here; the associated-type bound just felt like another bound.

When I ran into this in the wild, I eventually reduced my "real" code to this minimal example (similar to other examples above):
```
trait HasA {
    type A;
    fn get_a(&self) -> Self::A;
}

trait Foo {
    fn foo(&self);
}

trait Helper
where
    Self: HasA,
    Self::A: Foo,
{
}

fn test1<T: Helper>(t: T) {}
```
I was totally baffled that the Self: HasA bound in the definition of Helper propagates but the Self::A: Foo bound does not. Syntactically, they seem to be of the same logical class, as two bounds in the where clause (even if only one of them is a "super trait").

Moreover, it's super confusing that the function test1 here doesn't type check, since usually asserting a bound (here Helper) on an argument lets you make more assumptions about the argument in the body of the function, but here it somehow makes the function fail to type check, even tho the argument isn't even used!!!

It took me an hour+ to reduce my "real" code to this simple illustration of the problem, where my actual usage is more analogous to the following test2 function, which also fails to type check, for the same reason as test1 above:
```
fn test2<T: Helper>(t: T) {
    t.get_a().foo();
}
```
p.s. as mentioned above, apparently this doesn't affect trait aliases, which hopefully means this is easy to fix? Unfortunately, I can't use nightly in my project, or I would just switch to a trait alias, since creating a trait alias was exactly my goal.
Nathan Collins at 2024-01-18 08:44:56

A friend showed me a workaround. It's confusing when described abstractly, so probably better to just read the code below. But in summary: it seems that bounds on types associated with the trait being defined do get propagated, whereas we saw above that bounds on types associated with traits that bound the trait being defined don't get propagated.

Compare M1 and M2 below: here M1 is a copy of the broken code from my previous comment, whereas M2 is a working variation using the workaround:

// Doesn't type check
mod M1 {
    trait HasA {
        type A;
        fn get_a(&self) -> Self::A;
    }

    trait Foo {
        fn foo(&self);
    }

    trait Helper
    where
        // This `HasA` bound on `Self` propagates.
        Self: HasA,
        // This `Foo` bound on `<Self as HasA>::A` doesn't propagate.
        Self::A: Foo,
    {
    }

    // Doesn't type check: the bound `T::A: Foo` is not satisfied!?
    fn test1<T: Helper>(t: T) {}

    // Doesn't type check: same as above.
    fn test2<T: Helper>(t: T) {
        t.get_a().foo();
    }
}

// Variation on `M1` that does type check
mod M2 {
    trait HasA {
        type A;
        fn get_a(&self) -> Self::A;
    }

    trait Foo {
        fn foo(&self);
    }

    // Trick: define a "dummy" associated type `Helper::_A` that is
    // constrained to be equal to the associated type `HasA::A` that we
    // actually want to bound. By bounding `Helper::_A` we then implicitly
    // bound `HasA::A`, since apparently the equality constraint *does*
    // propagate.
    trait Helper: HasA<A = <Self as Helper>::_A> {
        // This `Foo` bound on `<Self as Helper>::_A` does propagate,
        // even tho a `Foo` bound on `<Self as HasA>::A` doesn't :/
        type _A: Foo;
    }

    fn test1<T: Helper>(t: T) {}

    fn test2<T: Helper>(t: T) {
        t.get_a().foo();
    }
}

Nathan Collins at 2024-01-23 02:34:21