Pre-Pre-RFC: Partially Transitive `From` via removing `From<X> for X`

libs
1

I know this proposal seems super weird. But it makes sense! In fact, in some useful cases, it helps derive From<Z> for X when From<Y> for X and From<Z> for Y are both available. Let me elaborate with a toy example:

pub struct A<X>(X);
impl<X, Y> From<X> for A<Y> where
    Y: From<X>
{
    fn from(value: X) -> Y {
        A(Y::from(value))
    }
}
pub struct B<X>(X);
impl<X, Y> From<X> for B<Y> where
    Y: From<X>
{
    fn from(value: X) -> Y {
        B(Y::from(value))
    }
}

We can notice that A::<B<usize>>::from(0usize) works when From<usize> for usize is implemented.

We also notice that when impl From<X> for X { ... } presents, there will be conflict implementations, because we cannot prevent the X = B<Y> case in impl<X, Y> From<X> for B<X> { ... }, which means another From<B<X>> for B<X>.

2

Implementing this would break stable code, for example:

fn foo(s: impl Into<String>) {
    //... 
}

In stable, the above snippet accepts String values, among others. With your proposal, that would no longer be the case.

2 Likes
3

Don't implement From<X> for X by default doesn't mean we cannot implement it manually. For most types T in std-lib, I agree that From<T> for T is necessary.

4

It does for any type outside of your own crate, due to the orphan rule. Not just for types in stdlib.

And in any case, as I said, it would run afoul of Rust's stability guarantees, i.e. it would break existing code "in the wild".

5 Likes
5

I know what you mean. Every type have let value: X = ...; X::From(value), not only the types defined in std-lib. Can we implement From<X> for X as an auto trait like Sized? For example, make it only applicable to type definitions where no type parameters present.

6

One significant aspect of all auto traits so far is that they are all marker traits i.e. they have no methods. In fact, AFAICT marker (and thus auto) traits have no associated items at all.

This proposal would change that. I'm curious to see how others would feel about that, assuming it's possible at all.

7

If an auto trait or marker trait were to have a method or associated item, how would we choose between different implementations of the same trait for a type? You could do it like specialization, but then you get the exact same soundness issues as specialization. Also you can currently cast away auto traits from trait objects. This only works because auto traits can not affect the vtable due to never having any methods.

2 Likes
8

I'm wondering whether Rust could deliberately allow overlapping implementations/specialization here. The default implementation is so boring that maybe it wouldn't hurt to allow overriding it selectively?

3 Likes
9

There is an even more fundamental reason why transitive From is impossible:

There may be multiple routes to get from one type to another by transitivity. So a "transitivity" impl conflicts not only with other impls, but also with other instances of itself.

Observe the error that rustc gives when we try to write this, even for a custom trait:

trait From2<T> {
    fn from2(value: T) -> Self;
}

impl<A,B,C> From2<A> for C where C: From2<B>, B: From2<A> {
  fn from2(value: A) -> C {
    From2::from2(From2::from2(value))
  }
}

error[E0207]: the type parameter `B` is not constrained by the impl trait, self type, or predicates
 --> src/lib.rs:5:8
  |
5 | impl<A,B,C> From2<A> for C where C: From2<B>, B: From2<A> {
  |        ^ unconstrained type parameter

Because B is unconstrained, there could be multiple types B that would fill in this impl, producing conflicting implementations of From2<A> for C.

14 Likes
10

This would still run into specialization's problems. Consider this example:

struct Foo<'a>(&'a i32);

impl<'a, 'b> From<Foo<'a>> for Foo<'b> {
    fn from(_: Foo<'a>) -> Foo<'b> {
        panic!()
    }
}

When the compiler needs to select an impl for Foo<'??>: From<Foo<'??>> while monomorphizing, the new impl will overlap with impl<T> From<T> for T. However selecting impl<T> From<T> for T will be unsound, as it would allow transmuting lifetimes.

So it seems the new impl should be preferred. However consider this other example:

enum Bar<'a> {
    Normal(&'a i32),
    Static(&'static i32),
}

impl<'a> From<Bar<'static>> for Bar<'a> {
    fn from(bar: Bar<'static>) -> Bar<'a> {
        match bar {
            Bar::Normal(r) => Bar::Static(r),
            Bar::Static(r) => Bar::Static(r),
        }
    }
}

In this example however selecting the new impl would be unsound, since it's valid only when the converted value actually has a 'static lifetime, which cannot be known at monomorphization time.

Ultimately the problem is that impl<T> From<T> for T is not really that "boring" at the type level. It mentions the exact same type T twice, and that's something that cannot be fully checked at monomorphization time (it can only be done modulo lifetimes, but that's enough to cause problems).

4 Likes
11

The status quo is we consciously decided that lifetime can't affect codegen, and it won't change, thus the result of lifetime specialization problem.

But pure theoretically speaking, I think this is possible in a hypothetical Rust. We just need a sound deterministic way to decide arbitrary lifetime relation, so we can actually choose one implementation for each case at mono time (instead of choose one for all case).

This might introduce some weird behavior since it's not clear what relation we choose. But at least it's sound and deterministic :sweat_smile:. It just makes reasoning about program behavior much harder. Totally not a major downside!

1 Like
12

Well, suppose we have a marker trait called Ident. We can do this:

impl From<X> for X where X: Ident {
     fn from(value: X) -> X { value }
}
13

Yes, I agree that there is no confluence principle in From. However, the case I mentioned doesn't involve this problem.

In fact, there are a lot of cases where the path for chained From can be determined. For example, you can refer to the example in my initial post.

14

You mean that it should only work if there is only one path?

This would mean that any library implementing any additional From impl for any type, would be a breaking change. That would be bad.

Also, in cases where there are a lot of From impls, it might be difficult for the compiler to do an exhaustive search to prove that there is no other path, even if that turns out to be true.

3 Likes
15

That would need specialization, something that is currently unstable because it is unsound in the general case, especially when lifetimes get involved. And from what I can see, that's not likely to change any time soon.

Perhaps. But unfortunately not all cases, and that would be required for a blanket impl.

16

I don't see why there is a need to search for other path (not sure which part of the compiler you are talking about).

For a pair of specific types X and Y, there either exists a From<X> for Y or it doesn't. And since From is implemented if and only if there is a unique path between X and Y, the subpaths must also be unique.

17

Clarification: if a person manually implements A -> B -> C and also A -> D -> C, and then tries to use C in a place that needs From<A>, what does the compiler do? Does it say "I saw A -> B -> C first so I'll use that one"? Or "both paths exist, so you can't"? Or is the person somehow prevented from manually implementing both A -> B -> C and A -> D -> C in the first place?

18

No specialization stuff involved!

The thing is, in this alternative implementation, if you have a valid impl From<X> for Y, the implementation is unique.

I'm talking about in our current implementation, many paths are unique, but we cannot make use of it.

19

How can this be possible? What will compiler tell you about following code?

impl From<A> for C {
    fn from(value: A) -> C {
        // make use of From<A> for B
        // make use of From<B> for C
    }
}

impl From<A> for C {
    fn from(value: A) -> C {
        // make use of From<A> for D
        // make use of From<D> for C
    }
}
20

Sorry, when I said "manually implements A -> B -> C", I meant manually implements both From<A> for B and From<B> for C, and does not manually implement From<A> for C. What happens then?