Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Tracking issue for specialization (RFC 1210) #31844

Open
nikomatsakis opened this issue Feb 23, 2016 · 222 comments
Open

Tracking issue for specialization (RFC 1210) #31844

nikomatsakis opened this issue Feb 23, 2016 · 222 comments

Comments

@nikomatsakis
Copy link
Contributor

@nikomatsakis nikomatsakis commented Feb 23, 2016

This is a tracking issue for specialization (rust-lang/rfcs#1210).

Major implementation steps:

  • Land #30652 =)
  • Restrictions around lifetime dispatch (currently a soundness hole)
  • default impl (#37653)
  • Integration with associated consts
  • Bounds not always properly enforced (#33017)
  • Should we permit empty impls if parent has no default members? #48444
  • implement "always applicable" impls #48538
  • describe and test the precise cycle conditions around creating the specialization graph (see e.g. this comment, which noted that we have some very careful logic here today)

Unresolved questions from the RFC:

  • Should associated type be specializable at all?
  • When should projection reveal a default type? Never during typeck? Or when monomorphic?
  • Should default trait items be considered default (i.e. specializable)?
  • Should we have default impl (where all items are default) or partial impl (where default is opt-in); see #37653 (comment) for some relevant examples of where default impl is limiting.
  • How should we deal with lifetime dispatchability?

Note that the specialization feature as implemented currently is unsound, which means that it can cause Undefined Behavior without unsafe code. min_specialization avoids most of the pitfalls.

@aturon
Copy link
Member

@aturon aturon commented Feb 24, 2016

Some additional open questions:

  • Should we revisit the orphan rules in the light of specialization? Are there ways to make things more flexible now?
  • Should we extend the "chain rule" in the RFC to something more expressive, like the so-called "lattice rule"?
  • Related to both of the above, how does negative reasoning fit into the story? Can we recover the negative reasoning we need by a clever enough use of specialization/orphan rules, or should we make it more first-class?
@arielb1
Copy link
Contributor

@arielb1 arielb1 commented Feb 24, 2016

I am not sure that specialization changes the orphan rules:

  • The "linking" orphan rules must stay the same, because otherwise you would not have safe linking.
  • I don't think the "future compatibility" orphan rules should change. Adding a non-specializable impl under you would still be a breaking change.

Worse than that, the "future compatibility" orphan rules keep cross-crate specialization under pretty heavy control. Without them, default-impls leaving their methods open becomes much worse.

I never liked explicit negative reasoning. I think the total negative reasoning specialization provides is a nice compromise.

@sgrif
Copy link
Contributor

@sgrif sgrif commented Mar 20, 2016

Should this impl be allowed with specialization as implemented? Or am I missing something?
http://is.gd/3Ul0pe

@sgrif
Copy link
Contributor

@sgrif sgrif commented Mar 20, 2016

Same with this one, would have expected it to compile: http://is.gd/RyFIEl

@sgrif
Copy link
Contributor

@sgrif sgrif commented Mar 20, 2016

Looks like there's some quirks in determining overlap when associated types are involved. This compiles: http://is.gd/JBPzIX, while this effectively identical code doesn't: http://is.gd/0ksLPX

@SergioBenitez
Copy link
Contributor

@SergioBenitez SergioBenitez commented Mar 23, 2016

Here's a piece of code I expected to compile with specialization:

http://is.gd/3BNbfK

#![feature(specialization)]

use std::str::FromStr;

struct Error;

trait Simple<'a> {
    fn do_something(s: &'a str) -> Result<Self, Error>;
}

impl<'a> Simple<'a> for &'a str {
     fn do_something(s: &'a str) -> Result<Self, Error> {
        Ok(s)
    }
}

impl<'a, T: FromStr> Simple<'a> for T {
    fn do_something(s: &'a str) -> Result<Self, Error> {
        T::from_str(s).map_err(|_| Error)
    }
}

fn main() {
    // Do nothing. Just type check.
}

Compilation fails with the compiler citing implementation conflicts. Note that &str doesn't implement FromStr, so there shouldn't be a conflict.

SergioBenitez pushed a commit to SergioBenitez/Rocket that referenced this issue Mar 23, 2016
Sergio Benitez
Experimented with the new impl specialization features of Rust. They work! But
they're not quite there yet. Specifically, I was able to specialize on
`Responder`, but when trying to remove the macro in `FromParam`, it didn't work.
See rust-lang/rust#31844.
@aturon
Copy link
Member

@aturon aturon commented Mar 23, 2016

@sgrif

I had time to look at the first two examples. Here are my notes.

Example 1

First case, you have:

  • FromSqlRow<ST, DB> for T where T: FromSql<ST, DB>
  • FromSqlRow<(ST, SU), DB> for (T, U) where T: FromSqlRow<ST, DB>, U: FromSqlRow<SU, DB>,

The problem is that these impls overlap but neither is more specific than the other:

  • You can potentially have a T: FromSql<ST, DB> where T is not a pair (so it matches the first impl but not the second).
  • You can potentially have a (T, U) where:
    • T: FromSqlRow<ST, DB>,
    • U: FromSqlRow<SU, DB>, but not
    • (T, U): FromSql<(ST, SU), DB>
    • (so the second impl matches, but not the first)
  • The two impls overlap because you can have a (T, U) such that:
    • T: FromSqlRow<ST, DB>
    • U: FromSqlRow<SU, DB>
    • (T, U): FromSql<(ST, SU), DB>

This is the kind of situation that lattice impls would allow -- you'd have to write a third impl for the overlapping case, and say what it should do. Alternatively, negative trait impls might give you a way to rule out overlap or otherwise tweak which matches are possible.

Example 2

You have:

  • Queryable<ST, DB> for T where T: FromSqlRow<ST, DB>
  • Queryable<Nullable<ST>, DB> for Option<T> where T: Queryable<ST, DB>

These overlap because you can have Option<T> where:

  • T: Queryable<ST, DB>
  • Option<T>: FromSqlRow<Nullable<ST>, DB>

But neither impl is more specific:

  • You can have a T such that T: FromSqlRow<ST, DB> but T is not an Option<U> (matches first impl but not second)
  • You can have an Option<T> such that T: Queryable<ST, DB> but not Option<T>: FromSqlRow<Nullable<ST>, DB>
@aturon
Copy link
Member

@aturon aturon commented Mar 23, 2016

@SergioBenitez

Compilation fails with the compiler citing implementation conflicts. Note that &str doesn't implement FromStr, so there shouldn't be a conflict.

The problem is that the compiler is conservatively assuming that &str might come to implement FromStr in the future. That may seem silly for this example, but in general, we add new impls all the time, and we want to protect downstream code from breaking when we add those impls.

This is a conservative choice, and is something we might want to relax over time. You can get the background here:

@sgrif
Copy link
Contributor

@sgrif sgrif commented Mar 23, 2016

Thank you for clarifying those two cases. It makes complete sense now

On Tue, Mar 22, 2016, 6:34 PM Aaron Turon notifications@github.com wrote:

@SergioBenitez https://github.com/SergioBenitez

Compilation fails with the compiler citing implementation conflicts. Note
that &str doesn't implement FromStr, so there shouldn't be a conflict.

The problem is that the compiler is conservatively assuming that &str
might come to implement FromStr in the future. That may seem silly for
this example, but in general, we add new impls all the time, and we want to
protect downstream code from breaking when we add those impls.

This is a conservative choice, and is something we might want to relax
over time. You can get the background here:

http://smallcultfollowing.com/babysteps/blog/2015/01/14/little-orphan-impls/


You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub
#31844 (comment)

@SergioBenitez
Copy link
Contributor

@SergioBenitez SergioBenitez commented Mar 23, 2016

@aturon

The problem is that the compiler is conservatively assuming that &str might come to implement FromStr in the future. That may seem silly for this example, but in general, we add new impls all the time, and we want to protect downstream code from breaking when we add those impls.

Isn't this exactly what specialization is trying to address? With specialization, I would expect that even if an implementation of FromStr for &str were added in the future, the direct implementation of the Simple trait for &str would take precedence.

@sgrif
Copy link
Contributor

@sgrif sgrif commented Mar 23, 2016

@SergioBenitez you need to put default fn in the more general impl. Your
example isn't specializable.

On Tue, Mar 22, 2016, 6:54 PM Sergio Benitez notifications@github.com
wrote:

@aturon https://github.com/aturon

The problem is that the compiler is conservatively assuming that &str
might come to implement FromStr in the future. That may seem silly for this
example, but in general, we add new impls all the time, and we want to
protect downstream code from breaking when we add those impls.

Isn't this exactly what specialization is trying to address? With
specialization, I would expect that even if an implementation of FromStr
for &str were added in the future, the direct implementation for the
trait for &str would take precedence.


You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub
#31844 (comment)

@burdges
Copy link

@burdges burdges commented Apr 1, 2016

I think "default" trait items being automatically considered default sounds confusing. You might want both parametricity for a trait like in Haskell, etc. along side with easing the impls. Also you cannot easily grep for them like you can for default. It's not hard to both type the default keyword and give a default implementation, but they cannot be separated as is. Also, if one wants to clarify the language, then these "default" trait items could be renamed to "trait proposed" items in documentation.

@Stebalien
Copy link
Contributor

@Stebalien Stebalien commented Apr 15, 2016

Note from #32999 (comment): if we do go with the lattice rule (or allow negative constraints), the "use an intermediate trait" trick to prevent further specialization of something will no longer work.

@arielb1
Copy link
Contributor

@arielb1 arielb1 commented Apr 15, 2016

@Stebalien

Why won't it work? The trick limits the specialization to a private trait. You can't specialize the private trait if you can't access it.

@Stebalien
Copy link
Contributor

@Stebalien Stebalien commented Apr 15, 2016

@arielb1 Ah. Good point. In my case, the trait isn't private.

@arielb1
Copy link
Contributor

@arielb1 arielb1 commented Apr 15, 2016

I don't think the "externals can't specialize because orphan forward-compatibility + coherence rulea" reasoning is particularly interesting or useful. Especially when we don't commit to our specific coherence rules.

@burdges
Copy link

@burdges burdges commented May 7, 2016

Is there a way to access an overridden default impl? If so, this could aid in constructing tests. See Design By Contract and libhoare.

@rphmeier
Copy link
Contributor

@rphmeier rphmeier commented May 7, 2016

Allowing projection of default associated types during type-checking will allow enforcing type inequality at compile-time: https://gist.github.com/7c081574958d22f89d434a97b626b1e4

#![feature(specialization)]

pub trait NotSame {}

pub struct True;
pub struct False;

pub trait Sameness {
    type Same;
}

mod internal {
    pub trait PrivSameness {
        type Same;
    }
}

use internal::PrivSameness;

impl<A, B> Sameness for (A, B) {
    type Same = <Self as PrivSameness>::Same;
}

impl<A, B> PrivSameness for (A, B) {
    default type Same = False;
}
impl<A> PrivSameness for (A, A) {
    type Same = True;
}

impl<A, B> NotSame for (A, B) where (A, B): Sameness<Same=False> {}

fn not_same<A, B>() where (A, B): NotSame {}

fn main() {
    // would compile
    not_same::<i32, f32>();

    // would not compile
    // not_same::<i32, i32>();
}

edited per @burdges' comment

@burdges
Copy link

@burdges burdges commented May 7, 2016

Just fyi @rphmeier one should probably avoid is.gd because it does not resolve for Tor users due to using CloudFlare. GitHub works fine with full URLs. And play.rust-lang.org works fine over Tor.

@SimonSapin
Copy link
Contributor

@SimonSapin SimonSapin commented May 7, 2016

@burdges FWIW play.rust-lang.org itself uses is.gd for its "Shorten" button.

It can probably be changed, though: https://github.com/rust-lang/rust-playpen/blob/9777ef59b/static/web.js#L333

@alercah
Copy link
Contributor

@alercah alercah commented Jun 24, 2020

My comment here, specifically item 6, provides a concrete case in the standard library where it may be desirable to have a specialization that is only partly overridable: IndexSet would need a distinct Output type because IndexSet could be implemented without Index, but we probably do not want to allow the two types to coexist with different Output types. Since IndexSet could have a default implementation in terms of IndexMut, it would be reasonable to allow specialization of the index_set method without allowing specialization of Output.

@alercah
Copy link
Contributor

@alercah alercah commented Jun 24, 2020

I have a difficult time with videos, so I can't look up the linked video, however, I do have one question about #[min_specialization]. As-is, there is an rustc_unsafe_specialization_marker attribute on traits like FusedIterator that provide optimization hints, so that they can be specialized on. @matthewjasper wrote:

This is unsound but we allow it in the short term because it can't cause use after frees with purely safe code in the same way as specializing on traits methods can.

I assume that the plan is to implement @aturon's proposal and add a specialization modality for traits such as these (where specialize(T: FusedIterator)). But currently, it appears that any code can specialize on these traits. If it's stabilized as-is, people could write stable specializations that depend on it, meaning that this unsoundness would be stabilized.

Should specialization on these traits also be limited to the standard library, then? Does the standard library derive enough benefit from being able to specialize on them?

@RalfJung
Copy link
Member

@RalfJung RalfJung commented Jun 25, 2020

If it's stabilized as-is, people could write stable specializations that depend on it, meaning that this unsoundness would be stabilized.

It is my understanding that min_specialization as-is is not intended for stabilization.

@matthewjasper
Copy link
Contributor

@matthewjasper matthewjasper commented Jun 28, 2020

I would like to second having some sort of marker on specializing impls. There have been quite a few cases of code in rustc and the standard library not doing what it looks like because there's no way to know that specialization is actually happening:

An unnecessary specialization of Copy:
https://github.com/rust-lang/rust/pull/72707/files#diff-3afa644e1d09503658d661130df65f59L1955

A "Specialization" that isn't:
https://github.com/rust-lang/rust/pull/71321/files#diff-da456bd3af6d94a9693e625ff7303113L1589

An implementation generated by a macro unless a flag is passed overriding a default impl:
https://github.com/rust-lang/rust/pull/73851/files?file-filters%5B%5D=#diff-ebb36dd2ac01b28a3fff54a1382527ddR124

@zserik
Copy link

@zserik zserik commented Jun 28, 2020

@matthewjasper the last link doesn't appear to link to any specific snippet.

@cuviper
Copy link
Member

@cuviper cuviper commented Jun 28, 2020

I'm not sure if this is an explicit goal, but AIUI the fact that specializing impls aren't marked gives you a way to avoid breaking changes on blanket impls. A new default impl<T> Trait for T doesn't conflict with downstream impls -- those just become specializing.

@Lokathor
Copy link
Contributor

@Lokathor Lokathor commented Jun 28, 2020

Could it be a warning only to have it unmarked?

@mark-i-m
Copy link
Member

@mark-i-m mark-i-m commented Jun 28, 2020

There have been quite a few cases of code in rustc and the standard library not doing what it looks like because there's no way to know that specialization is actually happening

My experience with java is similar (though not exactly analogous). It can be hard to find out which subclass of a class is actually running...

@burdges
Copy link

@burdges burdges commented Jun 29, 2020

We'd want some marker on specializable impls too though, also for clarity when reading, right?

We could put the markers in both places, which then improves rustc error or warning messages because they now know if specialization is desired and can point to the other place if it exists.

If an upstream crate adds an impl then, aside from simply upgrading, a downstream crate could employ tricks that permit compiling against both the new and old version, not sure that's beneficial.

@matthewjasper
Copy link
Contributor

@matthewjasper matthewjasper commented Jun 29, 2020

I think that the diff may be too large to show the change. It's pointing to this:

ENCODABLE = custom // (only encodable in metadata)

Re: Blanket impls, they are breaking changes anyway:

  • They might partially overlap a downstream impl, which is not allowed
  • Coherence can assume their non-existence in more subtle ways (which is why reserveration impls were added internally)
  • Specializing impls have to be always applicable, which either means:
    • We break peoples impls (what min_specialization does).
    • We require them to somehow annotate their trait bounds as being always applicable where necessary.
    • We make the always applicable change for them implicitly and potentially introduce subtle runtime bugs when the default impl now applies.
@nikomatsakis
Copy link
Contributor Author

@nikomatsakis nikomatsakis commented Jun 29, 2020

@cuviper actually, I feel like there were still edge cases around adding new blanket impls, even with specialization. I remember I was trying to figure out what it would take to permit us to add a impl<T: Copy> Clone for T { } impI wrote this blog post about it, in any case... but I can't remember now what my conclusion was.

Regardless, we could make it a lint warning to not have an #[override] annotation.

That said, if we could have the user declare which impls they are specializing (no idea how we would do that), it would simplify some things. Right now the compiler has to deduce the relationships between impls and that's always a bit tricky.

One of the pending items we have to do in the chalk project is to try and go back and spell out how specialization should be expressed there.

@dureuill
Copy link

@dureuill dureuill commented Jul 3, 2020

There have been quite a few cases of code in rustc and the standard library not doing what it looks like because there's no way to know that specialization is actually happening

My experience with java is similar (though not exactly analogous). It can be hard to find out which subclass of a class is actually running...

Back in May, I proposed an alternative to specialization on IRLO that doesn't actually rely on overlapping impls, but rather allows a single impl to where match on its type parameter:

impl<R, T> AddAssign<R> for T {
    fn add_assign(&mut self, rhs: R) where match T {
        T: AddAssignSpec<R> => self.add_assign(rhs),
        T: Add<R> + Copy => *self = *self + rhs,
        T: Add<R> + Clone => { let tmp = self.clone() + rhs; *self = tmp; }
    }
}

Crates downstream can then use such impl to implement "specialization", because by convention such impl for trait Trait would first match on types that implement another trait TraitSpec, and downstream types would be able to implement that trait to override the generic behavior:

// Crate upstream
pub trait Foo { fn foo(); }
pub trait FooSpec { fn foo(); }

impl<T> Foo for T {
    fn foo() where T {
        T : FooSpec => T::foo(),
        _ => { println!("generic implementation") }
    }
}

fn foo<T : Foo>(t: T) {
    T::foo()
}

// crate downstream
struct A {}
struct B {}

impl upstream::FooSpec for A {
    fn foo() { println!("Specialized"); }
}

fn main() {
    upstream::foo(A); // prints "specialized"
    upstream::foo(B); // prints "generic"
}

This formulation gives more control to upstream to choose the order of the applicable impls, and as this is part of the trait/function signature, this would appear in documentation. IMO this prevent "impl chasing" to know which branch is actually applicable, as the resolution order is explicit.

This could maybe make the errors around lifetimes and type equality more apparent as only upstream could meet them while implementing the specialization (since downstream is only implementing a "specialization trait".

Drawbacks to this formulation are that it is a very different route than the one in the RFC, and being implemented since 2016, and that at least some people on the thread expressed concerns that it would not be as expressive and/or intuitive as the current specialization feature (I find "matching on types" pretty intuitive, but I'm biased as I propose the formulation).

@the8472
Copy link
Contributor

@the8472 the8472 commented Jul 3, 2020

The match syntax might have another (syntactical) benefit: If it were at some point in the future extended with const-evaluated match guards then one wouldn't need to do type gymnastics to express bounds conditional on const expressions. E.g. one could apply specializations based on size_of, align_of, needs_drop or array sizes.

@nikomatsakis
Copy link
Contributor Author

@nikomatsakis nikomatsakis commented Jul 8, 2020

@dureuill thanks for the info! That is indeed an interesting idea. One concern I have is that it doesn't necessarily solve some of the other anticipated use cases for specialization, especially the "incrementally refining behavior" case as described by @aturon in this blog post. Still, worth keeping in mind.

@Dark-Legion
Copy link

@Dark-Legion Dark-Legion commented Jul 9, 2020

@dureuill The idea is indeed interesting and may have a lot of potential, but alternative isn't always equivalent exchange.
The reason I don't think it is, is that one isn't given the opportunity to fully replace the more general implementation. Also another problem might be the fact that we don't actually have support for all the features present in the where syntax RFC on which your suggestion depends.
The suggestion is intriguing, so maybe it could have it's own RFC as a separate feature rather than an competitor to specialization because both would be useful and I see no reason why they can't live together.

@dureuill
Copy link

@dureuill dureuill commented Jul 12, 2020

@the8472 @nikomatsakis, @Dark-Legion : Thank you for the positive feedback! I try answering some of your remarks in the IRLO thread, since I don't want to be too noisy on the tracking issue (I'm sorry for each of you who expected news on specialization and just found my ramblings 😳).

I may open a separate RFC if I manage to write something publishable. Meanwhile, I'm very open to feedback on the linked IRLO thread. I added a longer example from aturon's blog post, so feel free to comment on that!

hyd-dev added a commit to hyd-dev/rust-hut that referenced this issue Aug 24, 2020
…ion)]

From rust-lang/rust#31844 (comment):
"Note that the specialization feature as implemented currently is unsound, which means that it can cause Undefined Behavior without unsafe code. min_specialization avoids most of the pitfalls."
@kellerkindt
Copy link
Contributor

@kellerkindt kellerkindt commented Sep 11, 2020

I'm also in favour of having some sort of marker on specializing impls.

The 2021 Edition approaches, which allows us to reserve further keywords (like specialize). Looking at the complexity and history of this feature, I don't think it will stabilize before the release of the 2021 Edition (feel free to prove me wrong) which means - in my opinion - playing around with (a) new keyword(s) is reasonable.

Otherwise, the only existing keyword that seems ... well.. suitable as marker, might be super?

Summary by reusing the example of @LLFourn from #31844 (comment):

  • super (already reserved, but it could also be misinterpreted as alternative to default)
super impl<A, T> Extend<A, T> for Vec<A> where T: IntoIterator<Item=A>
  • specialize
specialize impl<A, T> Extend<A, T> for Vec<A> where T: IntoIterator<Item=A>
spec impl<A, T> Extend<A, T> for Vec<A> where T: IntoIterator<Item=A>
override impl<A, T> Extend<A, T> for Vec<A> where T: IntoIterator<Item=A>

already reserved keywords are to be found here

@ssokolow
Copy link

@ssokolow ssokolow commented Sep 11, 2020

or spec (short for specialize like impl is for implement)

"spec" is already more familiar to people as a shorthand for "specification" (eg. "The HTML 5 spec") so I don't think it'd be a good shorthand for "specialize".

@the8472
Copy link
Contributor

@the8472 the8472 commented Sep 11, 2020

override is a reserved keyword, I assume it was intended for functions, so it might be usable for an impl block.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
You can’t perform that action at this time.