search

rust-lang / rust

Empowering everyone to build reliable and efficient software.
https://www.rust-lang.org
Other
96.97k stars 12.53k forks source link

Tracking issue for specialization (RFC 1210) #31844

Open nikomatsakis opened 8 years ago

nikomatsakis commented 8 years ago

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

Major implementation steps:

Unresolved questions from the RFC:

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 commented 8 years ago

Some additional open questions:

arielb1 commented 8 years ago

I am not sure that specialization changes the orphan rules:

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 commented 8 years ago

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

sgrif commented 8 years ago

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

sgrif commented 8 years ago

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 commented 8 years ago

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.

aturon commented 8 years ago

@sgrif

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

Example 1

First case, you have:

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

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:

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

But neither impl is more specific:

aturon commented 8 years ago

@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 commented 8 years ago

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 https://github.com/rust-lang/rust/issues/31844#issuecomment-200093757

SergioBenitez commented 8 years ago

@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 commented 8 years ago

@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 https://github.com/rust-lang/rust/issues/31844#issuecomment-200097995

burdges commented 8 years ago

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 commented 8 years ago

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 commented 8 years ago

@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 commented 8 years ago

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

arielb1 commented 8 years ago

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 commented 8 years ago

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 commented 8 years ago

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 commented 8 years ago

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 commented 8 years ago

@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

zitsen commented 8 years ago

use like this(https://is.gd/Ux6FNs):

#![feature(specialization)]
pub trait Foo {}
pub trait Bar: Foo {}
pub trait Baz: Foo {}

pub trait Trait {
    type Item;
}

struct Staff<T> { }

impl<T: Foo> Trait for Staff<T> {
    default type Item = i32;
}

impl<T: Foo + Bar> Trait for Staff<T> {
    type Item = i64;
}

impl<T: Foo + Baz> Trait for Staff<T> {
    type Item = f64;
}

fn main() {
    let _ = Staff { };
}

Error :

error: conflicting implementations of trait `Trait` for type `Staff<_>`: [--explain E0119]
  --> <anon>:20:1
20 |> impl<T: Foo + Baz> Trait for Staff<T> {
   |> ^
note: conflicting implementation is here:
  --> <anon>:16:1
16 |> impl<T: Foo + Bar> Trait for Staff<T> {
   |> ^

error: aborting due to previous error

Does feture specialization support this, and is there any other kind of implementations currently?

aturon commented 8 years ago

@zitsen

These impls are not allowed by the current specialization design, because neither T: Foo + Bar nor T: Foo + Baz is more specialized than the other. That is, if you have some T: Foo + Bar + Baz, it's not clear which impl should "win".

We have some thoughts on a more expressive system that would allow you to also give an impl for T: Foo + Bar + Baz and thus disambiguate, but that hasn't been fully proposed yet.

rphmeier commented 8 years ago

If negative trait bounds trait Baz: !Bar ever land, that could also be used with specialization to prove that the sets of types that implement Bar and those that implement Baz are distinct and individually specializable.

zitsen commented 8 years ago

Seems @rphmeier 's reply is what I exactly want, impls for T: Foo + Bar + Baz would also help.

Just ignore this, I still have something to do with my case, and always exciting for the specialization and other features landing.

Thanks @aturon @rphmeier .

kylewlacy commented 8 years ago

I've been playing around with specialization lately, and I came across this weird case:

#![feature(specialization)]

trait Marker {
    type Mark;
}

trait Foo { fn foo(&self); }

struct Fizz;

impl Marker for Fizz {
    type Mark = ();
}

impl Foo for Fizz {
    fn foo(&self) { println!("Fizz!"); }
}

impl<T> Foo for T
    where T: Marker, T::Mark: Foo
{
    default fn foo(&self) { println!("Has Foo marker!"); }
}

struct Buzz;

impl Marker for Buzz {
    type Mark = Fizz;
}

fn main() {
    Fizz.foo();
    Buzz.foo();
}

Compiler output:

error: conflicting implementations of trait `Foo` for type `Fizz`: [--explain E0119]
  --> <anon>:19:1
19 |> impl<T> Foo for T
   |> ^
note: conflicting implementation is here:
  --> <anon>:15:1
15 |> impl Foo for Fizz {
   |> ^

playpen

I believe that the above should compile, and there's two interesting variations that actually do work-as-intended:

1) Removing the where T::Mark: Fizz bound:

impl<T> Foo for T
    where T: Marker //, T::Mark: Fizz
{
    // ...
}

playpen

2) Adding a "trait bound alias":

trait FooMarker { }
impl<T> FooMarker for T where T: Marker, T::Mark: Foo { }

impl<T> Foo for T where T: FooMarker {
    // ...
}

playpen

(Which doesn't work if Marker is defined in a separate crate (!), see this example repo)

I also believe that this issue might be related to #20400 somehow

EDIT: I've opened an issue about this: #36587

tomaka commented 8 years ago

I'm encountering an issue with specialization. Not sure if it's an implementation problem or a problem in the way specialization is specified.

use std::vec::IntoIter as VecIntoIter;

pub trait ClonableIterator: Iterator {
    type ClonableIter;

    fn clonable(self) -> Self::ClonableIter;
}

impl<T> ClonableIterator for T where T: Iterator {
    default type ClonableIter = VecIntoIter<T::Item>;

    default fn clonable(self) -> VecIntoIter<T::Item> {
        self.collect::<Vec<_>>().into_iter()
    }
}

impl<T> ClonableIterator for T where T: Iterator + Clone {
    type ClonableIter = T;

    #[inline]
    fn clonable(self) -> T {
        self
    }
}

(playpen) (by the way, it would be nice if this code eventually landed in the stdlib one day)

This code fails with:

error: method `clonable` has an incompatible type for trait:
 expected associated type,
    found struct `std::vec::IntoIter` [--explain E0053]
  --> <anon>:14:5
   |>
14 |>     default fn clonable(self) -> VecIntoIter<T::Item> {
   |>     ^

Changing the return value to Self::ClonableIter gives the following error:

error: mismatched types [--explain E0308]
  --> <anon>:15:9
   |>
15 |>         self.collect::<Vec<_>>().into_iter()
   |>         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected associated type, found struct `std::vec::IntoIter`
note: expected type `<T as ClonableIterator>::ClonableIter`
note:    found type `std::vec::IntoIter<<T as std::iter::Iterator>::Item>`

Apparently you can't refer to the concrete type of a defaulted associated type, which I find quite limiting.

Aatch commented 8 years ago

@tomaka it should work, the RFC text has this:

impl<T> Example for T {
    default type Output = Box<T>;
    default fn generate(self) -> Box<T> { Box::new(self) }
}

impl Example for bool {
    type Output = bool;
    fn generate(self) -> bool { self }
}

(https://github.com/rust-lang/rfcs/blob/master/text/1210-impl-specialization.md#the-default-keyword)

Which seems similar enough to your case to be relevant.

rphmeier commented 8 years ago

@aatch that example doesn't seem to compile with the intuitive definition for the example trait: https://play.rust-lang.org/?gist=97ff3c2f7f3e50bd3aef000dbfa2ca4e&version=nightly&backtrace=0

the specialization code explicitly disallows this -- see #33481, which I initially thought was an error but turned out to be a diagnostics issue. My PRs to improve the diagnostics here went unnoticed, and I haven't maintained them to the latest master for quite some time.

Aatch commented 8 years ago

@rphmeier the RFC text suggests that it should be allowed though, that example is copied from it.

nrc commented 8 years ago

I had a play with some code that could benefit from specialization. I strongly think we should go for the lattice rule rather chaining - it feels natural and was the only way to get the flexibility I needed (afaict).

If we went for default on the impl as well as individual items, could we enforce that if any item is overridden then they all must be? That would allow us to reason based on the precise type of a default assoc type (for example) in the other items, which seems like a useful boost in expressivity.

bluss commented 8 years ago

Should the following be allowed? I want to specialize a type so that ArrayVec is Copy when its element type is Copy, and that it otherwise has a destructor. I'm trying to accomplish it by using an internal field that is replaced by specialization.

I hoped this would compile, i.e that it deduces the copyability of ArrayVec<A>'s fields from the field types that are selected by the A: Copy + Array bound (compilable snippet on playground).

impl<A: Copy + Array> Copy for ArrayVec<A>
    //where <A as Repr>::Data: Copy
{ }

The commented-out where clause is not wanted because it exposes a private type Repr in the public interface. (It also ICEs anyway).

Edit: I had forgotten I reported issue #33162 about this already, I'm sorry.

nrc commented 8 years ago

Follow up on my comment, my actual use case:

// Ideal version

trait Scannable {}

impl<T: FromStr> Scannable for T {}
impl<T: FromStr> Scannable for Result<T, ()> {}

// But this doesn't follow from the specialisation rules because Result: !FromStr
// Lattice rule would allow filling in that gap or negative reasoning would allow specifying it.

// Second attempt

trait FromResult {
    type Ok;
    fn from(r: Result<Self::Ok, ()>) -> Self;
}

impl<T> Scannable for T {
    default type Ok = T;
    default fn from(r: Result<T, ()>) -> Self {...} // error can't assume Ok == T, could do this if we had `default impl`
}

impl<T> Scannable for Result<T, ()> {
    type Ok = T;
    default fn from(r: Result<T, ()>) -> Self { r }
}

fn scan_from_str<T: FromResult>(x: &str) -> T
    where <T as FromResult>::Ok: FromStr  // Doesn't hold for T: FromStr because of the default on T::Ok
{ ... }

// Can also add the FromStr bound to FromResult::Ok, but doesn't help

// Third attempt
trait FromResult<Ok> {
    fn from(r: Result<Ok, ()>) -> Self;
}

impl<T> FromResult<T> for T {
    default fn from(r: Result<Self, ()>) -> Self { ... }
}

impl<T> FromResult<T> for Result<T, ()> {
    fn from(r: Result<T, ())>) -> Self { r }
}

fn scan_from_str<U: FromStr, T: FromResult<U>>(x: &str) -> T { ... }

// Error because we can't infer that U == String
let mut x: Result<String, ()> = scan_from_str("dsfsf");
nikomatsakis commented 7 years ago

@tomaka @Aatch

The problem there is that you are not allowed to rely on the value of other default items. So when you have this impl:

impl<T> ClonableIterator for T where T: Iterator {
    default type ClonableIter = VecIntoIter<T::Item>;

    default fn clonable(self) -> VecIntoIter<T::Item> {
    //                           ^^^^^^^^^^^^^^^^^^^^
        self.collect::<Vec<_>>().into_iter()
    }
}

At the spot where I highlighted, clonable is relying on Self::ClonableIter, but because CloneableIter is declared as default, you can't do that. The concern is that someone might specialize and override CloneableIter but not clonable.

We had talked about some possible answers here. One of them was to let you use default to group together items where, if you override one, you must override all:

impl<T> ClonableIterator for T where T: Iterator {
    default {
        type ClonableIter = VecIntoIter<T::Item>;
        fn clonable(self) -> VecIntoIter<T::Item> { ... }
    }
}

This is ok, but a bit "rightward-drift inducing". The default also looks like a naming scope, which it is not. There might be some simpler variant that just lets you toggle between "override-any" (as today) vs "override-all" (what you need).

We had also hoped we could get by by leveraging impl Trait. The idea would be that this most often comes up, as is the case here, when you want to customize the return type of methods. So perhaps if you could rewrite the trait to use impl Trait:

pub trait ClonableIterator: Iterator {
    fn clonable(self) -> impl Iterator;
}

This would effectively be a kind of shorthand when implemented for a default group containing the type and the fn. (I'm not sure if there'd be a way to do that purely in the impl though.)

PS, sorry for the long delay in answering your messages, which I see date from July.

sgrif commented 7 years ago

While impl Trait does help, there is no RFC that has been accepted or implemented which allows it to be used with trait bodies in any form, so looking to it for this RFC feels a bit odd.

giannicic commented 7 years ago

I'm interested in implementing the default impl feature (where all items are default). Would you accept a contribution on that?

aturon commented 7 years ago

@giannicic Definitely! I'd be happy to help mentor the work as well.

marcianx commented 7 years ago

Is there currently a conclusion on whether associated types should be specializable?

The following is a simplification of my use-case, demonstrating a need for specializable associated types. I have a generic data structure, say Foo, which coordinates a collection of container trait objects (&trait::Property). The trait trait::Property is implemented by both Property<T> (backed by Vec<T>) and PropertyBits (backed by BitVec, a bit vector). In generic methods on Foo, I would like to be able to determine the right underlying data structure for T via associated types, but this requires specialization to have a blanket impl for non-special cases as follows.

trait ContainerFor {
    type P: trait::Property;
}

impl<T> ContainerFor for T {
    default type P = Property<T>; // default to the `Vec`-based version
}

impl ContainerFor for bool {
    type P = PropertyBits; // specialize to optimize for space
}

impl Foo {
    fn add<T>(&mut self, name: &str) {
        self.add_trait_obj(name, Box::new(<T as ContainerFor>::P::new())));
    }
    fn get<T>(&mut self, name: &str) -> Option<&<T as ContainerFor>::P> {
        self.get_trait_obj(name).and_then(|prop| prop.downcast::<_>());
    }
}
giannicic commented 7 years ago

Thanks @aturon ! Basically I'm doing the work by adding a new "defaultness" attribute to the ast::ItemKind::Impl struct (and then use the new attribute together with the impl item "defaultness" attribute) but there is also a quick and easy possibility consisting on setting default to all the impl items of the default impl during parsing. To me this isn't a "complete" solution since we lost the information that the "defaultness" is related to the impl and not to each item of the impl, additionally if there is a plan to introduce a partial impl the first solution would already provide an attribute that can be used to store default as well as partial. But just to be sure and not wasting time, what do you think about?

nikomatsakis commented 7 years ago

@giannicic @aturon may I propose we create a specific issue to discuss default impl ?

nikomatsakis commented 7 years ago

Never mind, I created one: https://github.com/rust-lang/rust/issues/37653

gnzlbg commented 7 years ago

Would the lattice rule allow me to, given:

trait Foo {}

trait A {}
trait B {}
trait C {}
// ...

add implementations of Foo for subset of types that implement some combination of A, B, C, ...:

impl Foo for T where T: A { ... }
impl Foo for T where T: B { ... }
impl Foo for T where T: A + B { ... }
impl Foo for T where T: B + C { ... }
// ...

and allow me to "forbid" some combinations, e.g., that A + C should never happen:

impl Foo for T where T: A + C = delete;

?

Context: I landed into wanting this when implementing an ApproxEqual(Shape, Shape) trait for different kinds of shapes (points, cubes, polygons, ...) where these are all traits. I had to work around this by refactoring this into different traits, e.g., ApproxEqualPoint(Point, Point), to avoid conflicting implementations.

nikomatsakis commented 7 years ago

@gnzlbg

and allow me to "forbid" some combinations, e.g., that A + C should never happen:

No, this is not something that the lattice rule would permit. That would be more the domain of "negative reasoning" in some shape or kind.

Context: I landed into wanting this when implementing an ApproxEqual(Shape, Shape) trait for different kinds of shapes (points, cubes, polygons, ...) where these are all traits. I had to work around this by refactoring this into different traits, e.g., ApproxEqualPoint(Point, Point), to avoid conflicting implementations.

So @withoutboats has been promoting the idea of "exclusion groups", where you can declare that a certain set of traits are mutually exclusive (i.e., you can implement at most one of them). I envision this as kind of being like an enum (i.e., the traits are all declared together). I like the idea of this, particularly as (I think!) it helps to avoid some of the more pernicious aspects of negative reasoning. But I feel like more thought is needed on this front -- and also a good writeup that tries to summarize all the "data" floating around about how to think about negative reasoning. Perhaps now that I've (mostly) wrapped up my HKT and specialization series I can think about that...

gnzlbg commented 7 years ago

@nikomatsakis :

So @withoutboats has been promoting the idea of "exclusion groups", where you can declare that a certain set of traits are mutually exclusive (i.e., you can implement at most one of them). I envision this as kind of being like an enum (i.e., the traits are all declared together). I like the idea of this, particularly as (I think!) it helps to avoid some of the more pernicious aspects of negative reasoning. But I feel like more thought is needed on this front -- and also a good writeup that tries to summarize all the "data" floating around about how to think about negative reasoning. Perhaps now that I've (mostly) wrapped up my HKT and specialization series I can think about that...

I thought about exclusions groups while writing this (you mentioned it in the forums the other day), but I don't think they can work since in this particular example not all traits implementations are exclusive. The most trivial example is the Point and Float traits: a Float can be a 1D point, so ApproxEqualPoint(Point, Point) and ApproxEqualFloat(Float, Float) cannot be exclusive. There are other examples like Square and Polygon, or Box | Cube and AABB (axis-aligned bounding box) where the "trait hierarchy" actually needs more complex constraints.

No, this is not something that the lattice rule would permit. That would be more the domain of "negative reasoning" in some shape or kind.

I would at least be able to implement the particular case and put an unimplemented!() in it. That would be enough, but obviously I would like it more if the compiler would statically catch those cases in which I call a function with an unimplemented!() in it (and at this point, we are again in negative reasoning land).

withoutboats commented 7 years ago

@gnzlbg lattice specialization would allow you to make that impl panic, but the idea of doing that makes me :cry:.

The idea of "exclusion groups" is really just negative supertrait bounds. One thing we haven't explored too thoroughly is the notion of reverse polarity specialization - allowing you to write a specialized impl that is of reversed polarity to its less specialized impl. For example, in this case you would just write:

impl<T> !Foo for T where T: A + C { }

I'm not fully sure what the implications of allowing that are. I think it connects to the issues Niko's already highlighted about how specialization is sort of conflating code reuse with polymorphism right now.

glaebhoerl commented 7 years ago

With all this discussion of negative reasoning and negative impls, I feel compelled to bring up the old Haskell idea of "instance chains" again (paper, paper, GHC issue tracker, Rust pre-RFC), as a potential source of inspiration if nothing else.

Essentially the idea is that anywhere you can write a trait impl, you can also write any number of "else if clauses" specifying a different impl that should apply in case the previous one(s) did not, with an optional final "else clause" specifying a negative impl (that is, if none of the clauses for Trait apply, then !Trait applies).

gnzlbg commented 7 years ago

@withoutboats

The idea of "exclusion groups" is really just negative supertrait bounds.

I think that would be enough for my use cases.

I think it connects to the issues Niko's already highlighted about how specialization is sort of conflating code reuse with polymorphism right now.

I don't know if these can be untangled. I want to have:

Covering all cases is hard, but if the compiler forces me to cover all cases: 

trait Foo {}
trait A {}
trait B {}

impl<T> Foo for T where T: A { ... }
impl<T> Foo for T where T: B { ... }
// impl<T> Foo for T where T: A + B { ... }  //< compiler: need to add this impl!

and also gives me negative impls: 

impl<T> !Foo for T where T: A + B { }
impl<T> !Foo for T where T: _ { } // _ => all cases not explicitly covered yet

I would be able to incrementally add impls as I need them and also get nice compiler errors when I try to use a trait with a type for which there is no impl.

I'm not fully sure what the implications of allowing that are.

Niko mentioned that there are problems with negative reasoning. FWIW the only thing negative reasoning is used for in the example above is to state that the user knows that an impl for a particular case is required, but has explicitly decided not to provide an implementation for it.

dtolnay commented 7 years ago

I just hit #33017 and don't see it linked here yet. It is marked as a soundness hole so it would be good to track here.

dtolnay commented 7 years ago

For https://github.com/dtolnay/quote/issues/7 I need something similar to this example from the RFC which doesn't work yet. cc @tomaka @Aatch @rphmeier who commented about this earlier.

trait Example {
    type Output;
    fn generate(self) -> Self::Output;
}

impl<T> Example for T {
    default type Output = Box<T>;
    default fn generate(self) -> Box<T> { Box::new(self) }
}

impl Example for bool {
    type Output = bool;
    fn generate(self) -> bool { self }
}

I stumbled upon the following workaround which gives a way to express the same thing.

#![feature(specialization)]

use std::fmt::{self, Debug};

///////////////////////////////////////////////////////////////////////////////

trait Example: Output {
    fn generate(self) -> Self::Output;
}

/// In its own trait for reasons, presumably.
trait Output {
    type Output: Debug + Valid<Self>;
}

fn main() {
    // true
    println!("{:?}", Example::generate(true));

    // box("s")
    println!("{:?}", Example::generate("s"));
}

///////////////////////////////////////////////////////////////////////////////

/// Instead of `Box<T>` just so the "{:?}" in main() clearly shows the type.
struct MyBox<T: ?Sized>(Box<T>);

impl<T: ?Sized> Debug for MyBox<T>
    where T: Debug
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "box({:?})", self.0)
    }
}

///////////////////////////////////////////////////////////////////////////////

/// Return type of the impl containing `default fn`.
type DefaultOutput<T> = MyBox<T>;

impl Output for bool {
    type Output = bool;
}

impl<T> Example for T where T: Pass {
    default fn generate(self) -> Self::Output {
        T::pass({
            // This is the impl you wish you could write
            MyBox(Box::new(self))
        })
    }
}

impl Example for bool {
    fn generate(self) -> Self::Output {
        self
    }
}

///////////////////////////////////////////////////////////////////////////////
// Magic? Soundness exploit? Who knows?

impl<T: ?Sized> Output for T where T: Debug {
    default type Output = DefaultOutput<T>;
}

trait Valid<T: ?Sized> {
    fn valid(DefaultOutput<T>) -> Self;
}

impl<T: ?Sized> Valid<T> for DefaultOutput<T> {
    fn valid(ret: DefaultOutput<T>) -> Self {
        ret
    }
}

impl<T> Valid<T> for T {
    fn valid(_: DefaultOutput<T>) -> Self {
        unreachable!()
    }
}

trait Pass: Debug {
    fn pass(DefaultOutput<Self>) -> <Self as Output>::Output;
}

impl<T: ?Sized> Pass for T where T: Debug, <T as Output>::Output: Valid<T> {
    fn pass(ret: DefaultOutput<T>) -> <T as Output>::Output {
        <T as Output>::Output::valid(ret)
    }
}
dtolnay commented 7 years ago

I am still working on https://github.com/dtolnay/quote/issues/7 and needed a diamond pattern. Here is my solution. cc @zitsen who asked about this earlier and @aturon and @rphmeier who responded.

#![feature(specialization)]

/// Can't have these impls directly:
///
///  - impl<T> Trait for T
///  - impl<T> Trait for T where T: Clone
///  - impl<T> Trait for T where T: Default
///  - impl<T> Trait for T where T: Clone + Default
trait Trait {
    fn print(&self);
}

fn main() {
    struct A;
    A.print(); // "neither"

    #[derive(Clone)]
    struct B;
    B.print(); // "clone"

    #[derive(Default)]
    struct C;
    C.print(); // "default"

    #[derive(Clone, Default)]
    struct D;
    D.print(); // "clone + default"
}

trait IfClone: Clone { fn if_clone(&self); }
trait IfNotClone { fn if_not_clone(&self); }

impl<T> Trait for T {
    default fn print(&self) {
        self.if_not_clone();
    }
}

impl<T> Trait for T where T: Clone {
    fn print(&self) {
        self.if_clone();
    }
}

impl<T> IfClone for T where T: Clone {
    default fn if_clone(&self) {
        self.clone();
        println!("clone");
    }
}

impl<T> IfClone for T where T: Clone + Default {
    fn if_clone(&self) {
        self.clone();
        Self::default();
        println!("clone + default");
    }
}

impl<T> IfNotClone for T {
    default fn if_not_clone(&self) {
        println!("neither");
    }
}

impl<T> IfNotClone for T where T: Default {
    fn if_not_clone(&self) {
        Self::default();
        println!("default");
    }
}
ipetkov commented 7 years ago

Hit a bug (or at least unexpected behavior from my perspective) with specialization and type inference: #38167