Struggling with trait impls

These impls literally cannot ever overlap, and yet rustc won't accept them: Rust Playground

What's going on here? Why does rustc refuse this perfectly sound code? (Note that this doesn't work with unstable specialization either, so it's not an issue of specialization.)

impl<X, T> DataSource<X> for Foo<T> where T: DataSource<X>, X: OverridableKind {
    fn get_values(&self) -> X::Values {
        self.v.iter().flat_map(|x| x.get_values()).collect()
    }
}

impl<X, T> DataSource<X> for Foo<T> where T: DataSource<X>, X: Kind<Values=Option<X>> {
    fn get_values(&self) -> X::Values {
        self.v.iter().flat_map(|x| x.get_value()).next()
    }
}
1 Like

This is https://github.com/rust-lang/rust/issues/20400, which is unlikely to get fixed in the near future.

6 Likes

Do you perhaps know what makes it such a difficult fix?

According to @jschievink's 2019 comment on that issue, the proposed RFC that would fix this is on hold until chalk integration is completed.

See also @withoutboats' comment withdrawing the RFC proposal:

I'm proposing we postpone this and #1658 for a later date, when chalk is up and running, and we can put forward a unified proposal for how to expand the negative reasoning performed by our coherence system.

I still want something like this RFC someday, but keeping this RFC open is not tracking progress toward that goal at all, and I think these two RFCs will want to be majorly revised into a single proposal.

1 Like

How the first comment does it is how I'd rather it worked. But yes, I do have a boilerplatey workaround for it.
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=634be52b8e32e2d80ace1c64ee622cbf

trait Foo {
    type Sum;
    fn summ(self) -> Self::Sum;
}

impl<T> Foo for T
where
    T: IntoIterator,
    T: FooHelper<T::Item>,
{
    type Sum = T::SumImpl;
    fn summ(self) -> T::SumImpl {
        self.summ_impl()
    }
}

trait FooHelper<Item> {
    type SumImpl;
    fn summ_impl(self) -> Self::SumImpl;
}

impl<T> FooHelper<(u32, u32)> for T
where
    T: IntoIterator<Item = (u32, u32)>,
{
    type SumImpl = u32;
    
    fn summ_impl(self) -> u32 {
        self.into_iter().map(|(a, b)| a + b).sum()
    }
}
impl<T> FooHelper<u32> for T
where
    T: IntoIterator<Item = u32>,
{
    type SumImpl = u32;
    
    fn summ_impl(self) -> u32 {
        self.into_iter().sum()
    }
}
impl<'a, T> FooHelper<&'a str> for T
where
    T: IntoIterator<Item = &'a str>,
{
    type SumImpl = u32;
    
    fn summ_impl(self) -> u32 {
        self.into_iter().map(|x| x.len() as u32).sum()
    }
}

fn main() {
    dbg!([(3, 5), (8, 13)].summ());
    dbg!([3, 5, 8, 13, 21].summ());
    dbg!(["hello", "world"].summ());
}

This doesn't show the super cool one where the helper trait also takes the full generic of the thing.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=182204f1b06e9dc3eb08b610c3ff5a76

Still not sure how this thing works, considering the first comment doesn't work.

1 Like

Well, your statement about taking issue 20400 as a joke and my desire to show the simpler iteration of the workaround were the reasons why I showed that example.

Context: We were talking on discord, and this is the message where I linked the solution to the first comment in this thread.

The simpler iteration doesn't show something that may as well be considered a direct desugaring of the first comment in issue 20400.

The fact that there is something that can be considered a direct desugaring in the language today is what makes issue 20400 a joke.

If issue 20400 could be closed by implementing the thing as desugaring into this hack, the point about waiting for chalk and whatnot would be effectively moot.

I disagree that it's is a good idea to use a desugaring (desugaring is a purely syntactic concept). That approach very quickly reaches surprising limitations, like that the code in your original comment won't work, since the mutually exclusive associated type for OverridableKind is in a supertrait (it can't just be desugared).

I don't understand why you're calling the issue a joke just because there is a potential solution for it.

1 Like

In case others would like a presentation less specific to the OP: The workaround presented for a bound on trait Trait with associated type A is to define a helper trait with two type parameters, <X: Trait<A=Y>, Y>.

trait Trait { type A; }
// We wish we could...
//    impl<T: Trait<A=u8>> TargetTrait for SomethingInvolving<T> {}
//    impl<T: Trait<A=()>> TargetTrait for SomethingInvolving<T> {}
// We'll simuluate it with:
trait Helper<X: Trait<A=Y>, Y> { /* mirrors TargetTrait */ }

Because the associated type is an input in this Helper trait, it can support multiple implementations which differ by Y. Basically it works by putting the associated type in a place that coherence checks, so that you can prove to the coherence checker that everything is, in fact, non-overlapping.

Then, you can can have a (single) blanket implementation bound on the Helper trait instead of on Trait.

impl<T: Trait<A>, A> TargetTrait for SomethingInvolving<T>
where
    Self: Helper<T, A>
{ /* Just defer to `Helper::*` as the implementation */ }

Whenever you want to add more impls for more associated types of Trait, you have to impl the Helper trait instead. If you want consumers of your library to be able to do this, you'll have to expose the Helper trait too. But implementations that aren't bound on the Trait with an associated type can't rely on the Helper trait, naturally, and thus they have to implement directly:

impl TargetTrait for SomethingInvolving<TypeThatDoesNotImplTrait> {}
impl TargetTrait for SomethingElseEntirely {}

So it definitely goes beyond syntax. You also don't get any other effects of making coherence associated-type-aware, like a way to make disjoint traits. And probably other things I haven't thought of.

I could see this being a crate of some sort to support some use-cases, but not really part of the language as-is.


Incidentally, in the example as I've written it, the implementations of TargetTrait we wish we could write are non-breaking by today's definition (T is covered). But those for Helper are breaking (blanket implementations as we have exposed T in the trait). I haven't thought through if the former being allowed should be considered breaking, but it's something else to consider.


To answer this more directly, coherence explicitly ignores "outputs" such as associated types for now. And beyond that, limitations on negative reasoning to avoid changes being breaking and maintain crate compatibility.

There's a desire to improve the situation, including this specific case; however it's easy for negative reasoning to go too far and cause problems, so they're being very careful about new developments in that area. They want a comprehensive approach as well, not a use-case specific approach. There's also a lot of interactions with accepted and implemented or partially implemented RFCs, such as auto-traits and specialization.

Much more related reading here.

2 Likes

So, if this was the accepted desugaring, you wouldn't get negative reasoning, is what you're saying?

That comment was more pointing out that just because this work-around exists today doesn't mean that you can also "work around to" the larger things like disjoint traits -- those things giving the Rust teams pause in e.g. RFC 1672. I.e. it doesn't invalidate their concerns.

(Clearly a desugaring wouldn't add any new negative reasoning to the language, but as noted, this approach can't be applied as purely a desugaring without producing code that fails to compile in some cases anyway. Aside from being undesirable generally, that makes it a breaking change.)

Disjoint traits requires negative reasoning, so this doesn't inherently add disjoint traits. Sounds like a good compromise. Surely there's a way to make this accepted as if it were "desugared", but without the drawbacks of actual desugaring and without the benefits or drawbacks of negative reasoning?

It seems like there's general support for some kind of solution to this problem, but the details need to be worked out and someone needs to volunteer to do the work. That discussion more properly belongs on IRLO than here; perhaps you'd like top start a thread there.

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.