Idea: `where match` clauses

Hello everyone,

I wanted to share an idea I had about a formulation for specialization that wouldn't rely on overlapping impls. Given how much work has been put into specialization and how advanced design and implementation are, I don't believe this alternative formulation should be considered now, but I wanted to share it in the hope it would be useful nevertheless.

So, currently specialization relies on having overlapping impls where a "more specific" one can be chosen. In this alternative, there is no "more specifc" impls, and overlapping impls always result in an error like in today's Rust.

Rather, it allows to specify several distinct implementations when declaring an impl<T>, so that the correct implementation is chosen depending on the bounds on T or its concrete value. To do so, we allow a new syntactical construct, where match that allows matching on "type patterns".

For an example, let's consider the AddAssign trait from the specialization RFC:

trait AddAssign<Rhs=Self> {
    fn add_assign(&mut self, rhs: Rhs);
}

And the various specialized impls, using where match:

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

In this example, we where match on the T generic parameter, which allows us to choose an implementation of the AddAssign trait depending on the bounds on T.

In each "arm" of the match, we have a classic pattern => impl, where pattern is a new kind of pattern, a "type pattern", and impl is the contents of the item being defined (here, the contents of the trait implementation). The T type is evaluated against each pattern in each arm, and the selected implementation is the one of the first arm whose pattern matches T.

So, for instance, in the example above, if T implements the AddAssignSpec<R> trait, then the first implementation, that actually delegates to this AddAssignSpec<R> trait, is selected. This allows for specialization, as a type that wishes to specialize its behavior with regard to AddAssign just needs to implement AddAssignSpec<R>, and this impl will be chosen even if the type is Clone or Copy. The AddAssignSpec<R> trait is a regular, good old trait that requires implementing fn add_assign(&mut self, rhs: R). If the type does not implements AddAssignSpec<R>, the next pattern is evaluated, and so the impl is chosen if the type is Add<R> + Copy. If the type is not Add<R> + Copy, the third implementation is chosen if the type is Add<R> + Clone. Finally, if the type is none of the above, pattern matching fails, and compilation fails.

Now, I did not try to formalize what kinds of type patterns would be allowed for matching, but I guess a first list would be:

  • A concrete type, e.g. u32
  • A free identifier name (in the example above, T) with or without bounds (T alone matches anything).
  • _ (matches anything, not very different from T without bounds, but cannot appear on the right side)
  • Lifetimes appearing in types would not be allowed to be different from '_ (or elided), as matching on the lifetime would be error-prone (and I heard it might be hard on codegen too :sweat_smile:)

A where match clause could appear in trait implementations, in functions definitions or in trait definition.

For example, the example above could be rewritten more concisely as:

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; }
    }
}

The second motivational example in the RFC is that of the Extend trait, and could be rewritten as follows:

pub trait Extend<A> {
    fn extend<T>(&mut self, iterable: T) where T: IntoIterator<Item=A>;
}

impl<A> Extend<A> for Vec<A> {
    fn extend<T>(&mut self, iterable: T) where match T {
        T: ExtendSpec<Vec<A>> =>  iterable.extend(&mut self),
        &'_ [A] =>  { /* optimized implementation */ }
        T: TrustedLen => { self.reserve(iterable.size_hint().1.unwrap()); for x in iterable { self.push(x) } }
        T: IntoIterator<Item=A> => for x in iterable { self.push(x) }
    }
}

Again, a type can specifically opt-in specialization by implementing the trait ExtendSpec<Vec<A>>. Otherwise, if it isn't done, then if the type is &'_ [A], we can implement an optimized implementation (that the RFC doesn't provide and I'm too lazy to implement myself). Importantly, in this block, the iterable variable is known to be of type &'_ [A], which allows to use its methods etc. etc. Otherwise, we have yet another impl if T is TrustedLen, and finally the "default" impl if T is IntoIterator<Item=A>.

The specialization RFC allows to define "default partial trait implementations" for some types. This is possible with where match clauses, by allowing them in trait definitions.

Using again the example from the specialization RFC:

trait Add<Rhs=Self> {
    type Output;
    fn add(self, rhs: Rhs) -> Self::Output;
    fn add_assign(&mut self, rhs: Rhs) where match Self {
        T : Copy => { *self = *self + rhs; }
        T : Clone => { let tmp = self.clone() + rhs; *self = tmp; }
        _ => impl;
    }
   }
}

In this example, we provide some default implementations for add_assign, under some conditions. If the type is Copy, we provide the first implementation as default implementation. This doesn't force a Copy type to use this implementation, though, they can still manually redefine add_assign in their trait implementation. If the type is not Copy nor Clone, we use the _ => impl arm, where the impl keyword indicates that there is no default implementation provided and that, while types are allowed to implement this type, they should provide an implementation of the add_assign function. It is important not to forget that arm, as otherwise only Copy or Clone types would be able to implement the add_assign function.

So, what do you think? Has something like this already been suggested before (I couldn't find anything with a cursory search in internals)? Certainly there are 1000s of reasons why this design would not work in practice, but I thought the idea was cool, as I really like matching on values in rust, it is a very expressive construct, and so I thought it would be nice to be able to do the same on types.

As I said, I don't expect this to influence the language in any capacity, but feel free to discuss!

One issue with this solution is that it doesn't work across crate boundaries. I.e. a downstream crate can't specialize a trait impl. Also, simply disallowing 'a doesn't work becuse there are more subtle ways to specialize based on a lifetime. For example, woud (T, T) specialize (T, U,) if so, it would require lifetime equality. But this particular issue plauges the current implementation of specialization. (You can use min_specialization for a sound subset)

Besides that, I like this formulation.

4 Likes

This also seems to strongly imply disjoint / mutually exclusive impls, which are very much in the "maybe someday" pile because lang design is hard. See: https://github.com/rust-lang/rfcs/pull/1148#issuecomment-165425724. It's probably for the best that they're separate from specialization.

1 Like

One issue with this solution is that it doesn't work across crate boundaries. I.e. a downstream crate can't specialize a trait impl.

My answer to this is the practice of having a TraitSpec trait for any Trait that has a blanket implementation. Is that not enough?

// 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 {}

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

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

I believe this does make it work again, though it's not nearly as intuitive or self-explanatory as the current proposal's "just write default impl if you want to allow specializations". I'm also not sure this would compose well when there's more than two crates involved. Besides, cross-crate specialization is arguably the use case for making specialization a first-class built-in feature, since basic specialization use cases within a single crate can already be worked around in pretty much exactly the same way.

2 Likes

Yes, of course, this is a hard issue, one for which I don't personally hope to ever find a solution... We could forbid anything that implies type equality (e.g., matching on (T, T)), but I'm not sure this is enough.

Or, we could allow them in the pattern, but fail the comparison for anything that requires lifetime equality.

Or just "bite the bullet" and pass lifetime information to codegen. But now this is an orthogonal matter.

1 Like

I think until specialization is reasonably fleshed out, we shouldn't start designing and adding largely overlapping features.

2 Likes