Proposal: const specialization

language design
1

As far as I understand, the primary issue blocking specialization is lifetimes. They cannot affect the runtime behaviour of the program, so we cannot rely on the exact inferred lifetimes for trait resolution. Thus specialization on lifetimes is hard to impossible to implement soundly, and everything which can lead to lifetime specialization is also blocked. For example, we cannot specialize on types in general, because those types can have lifetimes, leading to lifetime specialization.

However, I don't see how specializing on the values of const generic parameters could lead to lifetime specialization, in the current implementation. Currently it's impossible to provide arbitrary types to const generic parameters, only bool, char and integers can be used. As far as I can tell, this makes it impossible to cause lifetime specialization using const specialization: the types are specific, and while the expressions for constants could, in principle, contain lifetime-generic types, the values of the constants cannot depend on it (because it's impossible to define different values of a constant for different instantiations of lifetime parameters).

This is a significantly restricted subset of min_specialization. I couldn't find any somewhat-recent status for min_specialization, but I heard that it also had some soundness issues.

The motivation for const_specialization is making array types more useful. Currently many core traits (Default, Distribution<[_;_]>, Serialize/Deserialize) in the stdlib and libraries are not implemented for arrays. The reason, I believe, is because those traits were already unconditionally implemented for [T; 0] for any T, but for [T; N] would require extra trait bounds on T. This means that the array impls cannot be added backwards-compatibly without some form of specialization. This is a source of frustration for use cases where fixed-sized arrays are common, like various kinds of low-level binary protocols. The proposal is to make that specific use possible.

The primary objection to this feature that I can see is that it is unclear whether it will fit as-is in the future final design of specialization, whether it would require some syntactic or semantic changes, or even whether full specialization will ever be possible. In my eyes the motivation for const specialization is strong enough to warrant it even if the larger design requires a different approach. Also, so far I haven't seen any radically different specialization designs, so it feels like the discussion is over the soundness and implementation of the feature rather than its basic syntax and capabilities.

Some future additions to const generics would also be at odds with this minimal const_specialization. For example, there would likely be conflicts if the type of constants could be arbitrary (or even just &str for any lifetimes). Since constants are always 'static, this doesn't immediately look like a blocking conflict, but perhaps some more complex group of generic types and traits could still cause the issue. Overall, it would mean that only one of those features could be stabilized without solving full specialization. Imho since zero-sized arrays is such a common and basic issue, it should take priority over complex const expressions, but I can see the converse arguments.

7 Likes
2

Specialization on const generics shouldn't need to conflict with extending what types can be put into const generics in any way; we can simply enough restrict the set of const generic types valid to specialize on separately from the set of types allowed in const generics.

More interesting is that the current angle on providing a workable framework for specialization is that there must always be an unambiguous most applicable implementation. Thus, just

struct Array<T, const N: usize>([T; N]);

impl<T: Default, const N: usize> Default for Array<T, N> {
    default fn default() -> Self {
        Self(array::from_fn(|_| T::default()))
    }
}

impl<T> Default for Array<T, 0> {
    fn default() -> Self {
        Self([])
    }
}

is not allowed; the compiler doesn't know which implementation to use for Array<impl Default, 0>, as neither implementation is a proper subset of the other implementation. To allow partially overlapping implementations, you need to (make both impls specializable with default and) add a third implementation which specializes both implementations and covers the overlap, i.e.

impl<T: Default> Default for Array<T, 0> {
    fn default() -> Self {
        Self([])
    }
}

but whoops, this is specializing on T: Default now, not just on specific const generic values. As such, this implementation isn't always applicable, and thus even with #![feature(specialization)] won't compile.

Per the always applicable rule (2018), distinct implementations A and B can be soundly allowed to overlap if

  1. one of them specializes the other; or
  2. for all potential types in the intersection, there exists some implementation C which specializes both A and B;

and (for both cases[1]) the specializing implementation is always applicable[2].

What the case of implementations for [T; 0] is some way to say that the second implementation specializes the first without the use of a lattice intersection implementation (2016). As noted in the always applicable blog post, while the specialization RFC defines the specializes relationship as just "clearly more specific" refining implementations, any partial ordering of implementations to establish an application order is sufficient to maintain coherence.

If made painfully explicit with bikeshed-avoidance attributes, this could be expressed as

#[specializable]
impl<T: Default, const N: usize> Default for [T; N] {
    fn default() -> Self { array::from_fn(|_| T::default()) }
}

#[specializes(impl<T: Default, const N: usize> for [T; N])]
impl<T> Default for [T; 0] {
    fn default() -> Self { [] }
}

We would still need to require the specializing implementation to be unambiguously always applicable (i.e. is fully generic w.r.t. lifetimes and does not bound nor repeat any generics of any kind[3]), but explicitly introducing the specializes relationship/ordering removes the requirement that the specializing implementation be more constrained than the implementation it specializes.

Potentially this ordering could be inferred from the fact that the specialized implementation uses default fn and the specializing implementation does not. Unfortunately, this most likely makes it a breaking change to make an implementation specializable. Additionally, it doesn't allow further specialization of such an implementation, and explicit impl ordering potentially enables more implementations to be always applicable (see prior footnote).

For the case where bounds don't differ between the overlapping implementations and the specializing implementation just sets a specific const value, "if specialization" can already be done, e.g.

impl<T, const N: usize> MyType<T, N> {
    fn do_stuff(&self) {
        // should trivially be constant folded and eliminate dead arms
        match N {
            0 => self.do_stuff_0(),
            1 => self.do_stuff_1(),
            _ => self.do_stuff_n(),
        }
    }
}

  1. The blog post only explicitly puts the always applicable rule on lattice impls, but it needs to apply just the same to normal specializing implementations, and in fact the example used to show why the always applicable rule is necessary is itself a simple specialization rather than a lattice specialization. ↩︎

  2. Strictly speaking, the specializing implementation only needs to be always applicable within the set of types which it is specializing for. This means that a specializing implementation does not need to be completely restricted to not have any explicit bounds; it just needs to not have any bounds not present in the implementation(s) it specializes. ↩︎

  3. The absence of bounds/repetition only truly matters for lifetime and type generics, as (as you note) const generics aren't able to cover lifetimes which get erased, and are fully known all the way through to codegen dispatch. Just applying the rule to const generics as well is easier initially and doesn't prevent the array implementations, which just want to specialize for for<T> [T; 0]. ↩︎

3 Likes
3

Hmm, I don't think that we should solve the Default problem via specialization at all. I'd much rather be able to have one impl for N == 0 and one impl for N > 0, in such a way that the compiler knows that it's exhaustive and thus I can use [impl Default; N] for any N.

So that problem pushes me to something more like patterns, like how match x { 0 => (), 1.. => () } is accepted today because we know that's exhaustive.

4 Likes
4

Something like this?

impl<T> Default for [T; 0] {...}

impl<T: Default, const N @ 1..: usize> Default for [T; N] {...}

Must it be exhaustive though, or just non-overlapping?
(e.g. we might like to forbid 0 in array_windows<const N @ 1..: usize>.)

6 Likes
5

If not using specialization, the compiler still has to go the other direction and prove that impl<T> for [T; 0] and impl<T: Default, const N: usize in 1..> for [T; N] together are sufficient to prove that for<T: Default, const N: usize> [T; N]: Default.

Pattern exhautiveness is a thing that the compiler already knows how to do; that's why using patterns to introduce value niches into types is interesting. But it's still something new to teach the compiler to do; it currently won't accept impls for both Const<true> and Const<false> as sufficient to satisfy for<const B: bool> Const<B>.

cc @Boxy, @eddyb, @oli-obk on pattern types.

2 Likes
6

Absolutely, yeah.

I was just thinking that at least if it's phrased as patterns it's something we know how to do reliably and semver-ly, not something we'd need a research project to even get a plan. (Wheras with where N > 0 and where N == 0 we intentionally don't try to treat as exhaustive as expressions in control flow or match arm conditions.)

7

Ok, I was sure that someone would explain why my suggestion can't work. Thank you! It's nice that there is now a specific topic which records it.

I don't think that works in general. Rust doesn't currently have flow typing and range analysis. This means that I wouldn't be able to use different specific types in a branch, at least not without extra checks and possible panics. Example:

fn frobnicate<T>(x: &mut MyType<T, 2>) { .. }

impl<T, const N: usize> MyType<T, N> {
    fn do_stuff(&mut self) {
        // should trivially be constant folded and eliminate dead arms
        match N {
            2 => frobnicate(self),//<- doesn't compile, need a fallible conversion
            _ => self.do_stuff(),
        }
    }
}

Love it! It's much nicer than ordinary specialization, since it's obvious what values of N this impl applies to.

1 Like
8

Ooh, I like it. This is also what [T]::as_chunks needs.

(Though I might lean towards const N: usize @ 1.., since I've been pondering having types on bindings in normal patterns too, where I think I'd want it next to the binding, rather than anywhere in a pattern.)

1 Like
9

but can't you internally transform n == 0 and n > 0 into matching Z and S(m)?

I mean, integers could totally de treated as inductive data types for the purpose of pattern matching

(by the way, tuples could too)

10

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.