Syntax bikeshed: specializable bounds

language design
1

I'm finally about to sit down and power out the blog post I've been promising for way too long now on my conceptual system for specialization safety which should be both fully sound and allow all possible sound specializations (that are resilient in the face of semver compatible upstream changes) to be implemented. But I need some syntax to use while discussing the semantics, so here I am, asking for ideas.

1. Specialization-safe traits

Traits which can be specialized on MUST be marked as distinct from standard traits, such that they can be treated differently to ensure the safety of specialization. The easy answer is #[specializable] trait, but a keyword like virtual trait (not virtual as in dynamic dispatch, but virtual as in generic code can test for its presence) or contextual keyword like spec trait are much less noisy.

The case for using a keyword gets even stronger when you also consider…

2. Distinguishing between "baseline" and "added" supertraits

When specializing on e.g. trait TrustedIterator, you have a baseline generic T: Iterator that you want to upgrade to trusting. The bound differential between impl TrustedIterator and impl Iterator must be specialization safe.

When specializing on e.g. trait ExactSizeSpec, you still have a baseline generic T: Iterator, but you now want to upgrade to T: ExactSizeIterator. The bound differential between impl ExactSizeSpec and (still) impl Iterator must be specialization safe and must satisfy the requirements for T: ExactSizeIterator.[1]

The default kind of supertrait bound could go either way. We could look to whichever is the conservative choice, which I think is an "added" supertrait, but I'm not confident in if changing supertrait kinds is an API compatible change (i.e. that going from "added" to "baseline" supertrait only relaxes requirements on downstream). As for which is more common, all of the practical examples I can think of have zero to one of either kind. (But limiting to exactly one by syntactically privileging the first supertrait feels wrong, especially since we decided against privileging upcasts to the first supertrait.)

Also note that while I'm focusing on supertrait bounds, since I expect those to be the most common given a pattern of non-specialization standard traits and specialization marker subtraits, but all bounds in a spec trait declaration will need to be marked as "baseline" or "added."

  • default "baseline" explicit "added": spec trait ExactSizeSpec: Iterator + spec ExactSizeIterator
  • explicit "baseline" default "added": spec trait ExactSizeSpec: default Iterator + ExactSizeIterator

spec for an "added" supertrait mirrors the spec keyword on the trait item itself and emphasizes that bounds towards satisfying that supertrait must be specialization safe. But I'm not super enthused about this option, since it's not immediately obvious which supertrait kind should be "the specialization supertrait," as both kinds of supertrait have notable special properties for supporting specialization.

default for a "baseline" trait emphasizes the specialization use case of starting with the default bound(s) already satisfied before performing further specializing. Or this keyword could be final, which could be directly tied to…

3. Non-relaxable bounds

One notable wrinkle to specialization is that required bounds in a crate are allowed to be relaxed — it's API compatible to replace impl<T: Eq> PartialEq for Ty<T> with impl<T: PartialEq> PartialEq for Ty<T>.

For trait impls, this isn't all that much of an issue — it means that non-specialization-safe T: Eq doesn't satisfy a "baseline" Ty<T>: PartialEq, but you can always add an explicit Ty<T>: PartialEq bound with no functional change except specialization access.[2]

For generic type names, however, this becomes relevant. The "just works" solution is implied bounds that remain unsatisfied except for naming the type name which implies those bounds. The simple and straightforward solution is to mark the type itself as having minimal bounds on generics that won't ever be further relaxed. But these don't mix well, as there is no way to mark one generic as known minimal but leave another as relaxable.

final struct S<T: Trait> works to mark the struct generics as finalized, thus minimally bounded, but is directly confusable with saying that all fields are known final. Any of T: final Trait, T: default Trait, T: spec Trait, or T: virtual Trait could be justified, depending on how exactly the naming is explained (does it name what or why the modifier exists) when we mark the bound itself.[2:1]

The generic bounds of generic default fn also face the same question about relaxation. But in their case I think it's clear that they have to work like trait methods, where strengthening or relaxing the bounds on the method is semver breaking.

And then I think the final bit of necessary syntax…

4. Impl specialization

The current nightly syntax of default fn to opt in a function to being specialized works well and makes sense to me, even if the likely meaning of default impl is "default" in a different way.

I'd just suggest adding override as a required keyword (already reserved) for functions which specialize a default fn impl, or final if it's not intended to be further specialized.

However, there is a further wrinkle. If the override specializes from a baseline of the impl block with default fn, then that impl block of the default impl is made non-relaxable. If the override specializes from the baseline traits, the override loses access to bounds available to the default impl and almost certainly becomes an improper specialization[3].

My initial choices

Having written this out, but not heard anyone else's opinions yet, I think I'm leaning towards:

  1. spec trait Trait, read as "specializable trait Trait."
  2. spec trait ExactSizeSpec: default Iterator + ExactSizeIterator, read as "… refining specialization base trait Iterator and supertrait ExactSizeIterator."
  3. T: default Bound, read as "T implementing specialization base trait Bound" and making T: Bound an implied bound when Ty<T> is present.
  4. Privilege crate-local specialization, allowing it to specialize the specific impl bounds, as in a local setting, relaxing the default impl and making the override no longer specialization safe is a local error that can then be fixed without breaking anyone. Also, due to the orphan rules (which still apply to override impls[4]), the cases where this would actually come up cross-crate seems exceptionally rare.[5]

I hope that reasonably covers the syntactic needs of specialization. Do you agree with my choices, or do you have additional insight to offer?

To push myself to hopefully actually finish the blog post, I'm also putting a date on it: by next Sunday for part one (providing specialization bounds) and a week from that for part two (utilizing specialization).

(Aside: I mentioned having this conceptual system offhand at RustConf All Hands, and got a "doubt it's actually complete and sound, but go for it" there. I've been delaying since… stupid executive dysfunction.)

  1. Minor note: the impl ExactSizeIterator bounds don't actually have to be specialization safe, just the subset required by ExactSizeSpec. I expect this to be a common pattern in practice, e.g. impl<T: Step> ExactSizeIterator for Range<T> and then impl<T: TrustedStep> ExactSizeSpec for Range<T>. ↩︎

  2. T: spec Sized will be an awkward specification. But hopefully unnecessary, since as a specialization safe trait, it's should always allowed to add a Sized bound in a downstream specialization. ↩︎ ↩︎

  3. A specialization which is not satisfied only by a proper subset of the specialized impl. ↩︎

  4. There's an argument to be made that inherent default fn should act like a trait method for the purpose of override orphan rules, allowing impl Foreign<Local> { override fn … }. This would need to be decided before specialization to determine if the generic bounds on the fn itself are relaxable ↩︎

  5. For the rare case that actually needs it, we can allow default bounds on impl blocks to specify the bounds that can be used as a specialization base. ↩︎

8 Likes
2

For a library writer that is not very familiar with specialization like me, I wonder is it suggested that I mark all non-seal public traits in my library (that is not "weird" enough to make specialization not safe) as "specializable"? Since as far as I understand, it is much like a library-user's choice to decide whether to specialize a trait. Could you clarify this a bit more?

4 Likes
3

You seem to be talking entirely only about syntax changes and semver issues. I’m failing to see how this would allow for sound specialization. Could you explain how specialization-safe traits would be restricted to allow for sound specialization? That is, what code patterns would be allowed for normal traits but disallowed for specialization-safe traits?

In case you’re not already aware, here’s example code that shows that specialization is unsound: Rust Playground

1 Like
4

I'm going to get into a lot more detail in the promised blog post, but in short, spec trait can only have impls which are specialization safe, which is roughly equivalent to the "always applicable" rule, with the addition that the base can be a non-specialization-safe set of bounds.

Almost certainly not. A specialization safe trait has its potential impls restricted such that they cannot be potentially dependent on lifetime bounds, which excludes a lot of reasonable shapes. Plus, it's always possible to make a specialization marker subtrait for enabling specialization of some opt-in subset, where going the other direction is significantly less doable.

I know it's awkward looking at just syntax without semantics, but detailing the complete semantics really will take a whole decent length blog post to cover everything needed. I'm hopefully going to get it written for real this time.

2 Likes
5

Since you explicitly asked on syntax choice: I'm skeptical on using default as a keyword here:

  • It overlaps/conflicts with Default::default, so a default keyword might cause conflicts here and require writing r#default in many places.
  • When reading default, the first thing I think about is the Default trait, not anything related to specialization.

Alternative suggestions (you already tried describing it with some of these words):

  • refine, refines or refined
  • base, based
  • replace, replaces
  • extend, extends

Even using spec again could be an option, thus making it clear they are related [1]

  1. We already have some keywords with differing (but related) meaning depending on where they are used. For example: unsafe. ↩︎

1 Like
6

It can be a weak keyword. For example we already can write let macro_rules = 1;.

(And I don't really think OP meant to bikeshed keyword naming when they mentioned syntax choice...)

2 Likes
7

Thank you for your explanation! However, I'm still a little bit confused.

it's always possible to make a specialization marker subtrait for enabling specialization of some opt-in subset, where going the other direction is significantly less doable.

Would you mind giving an example if possible? Let's take the TrustedIterator and Iterator as an example. If std provides Iterator (not marked with specialization safe), and library user defines TrustedIterator. There is a function foo that is not controlled by the library user (like in a 3rd library):

fn foo(iter: impl Iterator);

If the user wants this function to invoke specialized methods when passing trusted iterator, can the "specialization marker subtrait" approach handle this requirement?

I know it takes time to write a full blog post, and it's OK to answer my confusion after the blog is done. Anyway, I understand this whole work is very challenging and thank you for your wonderful work again :slight_smile:

8

I'm wondering if what's happening here is that a specialization isn't so much a sort of trait, as a relationship between a type/trait and a supertrait.

As such, I'd expect the syntax to be attribute-based but contain the name of the supertrait:

#[specializes(Iterator)]
pub trait TrustedLen: ExactSizeIterator {}

#[specializes(Default)]
pub trait AllBitsZeroDefault {}

because the marker could realistically be used for types too (so as to be able to specialize on a particular type), and you could use the same attribute there. (I can't offhand think of any examples of specializing on just a single type, but there are almost certainly uses for it.)

There are some awkward cases, such as that of specializing on Copy, but I suspect that one's impossible to resolve whilst maintaining backwards compatibility (and because of that, Rust is moving in the direction of using a TrivialClone trait instead, which could be interpreted as a specialization of Clone but doesn't have to be for soundness).

9

I was browsing this thread, and I must say this example puzzles me. I do understand why this example is failing, but is it because of specialization? I don't get why the compiler accepts this function in first place:

fn call_spec_method<T>(x: T) -> &'static i32 {
    x.spec_method()
}

When you have not specified anywhere that T must implement SpecTrait. If you add the bound:

fn call_spec_method<T: SpecTrait>(x: T) -> &'static i32 {
    x.spec_method()
}

The compiler does properly reasons about x not living long enough even across the several specialization layers and only accepts correct implementations

1 Like
10

SpecTrait is implemented for all types T. I don't see the issue here.

11

I see now. I actually didn't know Rust automatically assumed every generic has every trait in the current scope. This seems like a compiler bug rather than a limitation of specialization, given that in this case call_spec_method<T> and call_spec_method<T> where T: SpecTrait should be equivalent but they aren't.

12

Sorry, but I don’t understand what you mean here. Rust definitely doesn’t assume that.

13

I meant every trait with a blanket implementation.

14

I tried running your example with and without the trait bounds and they give the same result though.

15

since I expect those to be the most common given a pattern of non-specialization standard traits and specialization marker subtraits

Some of the current specializations are not subtraits because that imposes too many constraints, especially on adapters where the struct itself has looser bounds than the trait impl. This might be a consequence of min_specialization, idk if that would still apply to whatever you have in mind.

I fail to grok these slightly abstract examples. Can you point at some existing specializations and show how their new syntax would look like?

Also, is the proposed syntax to add more information/constraints or will it just rephrase things that are already there?

Tangent: are you aware of

16

The problem is that compiler cannot reason with lifetimes when specialization interacts with implied bounds. For correct code this makes no difference, but the original theemathas' example can be made to work with explicit bounds. Work in the sense that the compiler does detect the attempt to promote the temporal lifetime to 'static.

17

I'm just curious, did someone investigate what would it take to actually pass the information about lifetimes down in order do choose correct implementations? How much work is it?

18

IIRC, it is an implementation design decision (unsure on the language design side) that lifetimes are erased by then. The alternative is to generate umpteen copies of any lifetime-mentioning function and let the linker deduplicate things later. Since codegen is already one of the more expensive parts of the pipeline, I can see why it was done. I don't know if the opportunity cost for specialization was known at the time of that decision though.

19

Actually, it's not about passing the information down takes too much work. It's that there's just not enough information. The language can only specify restraints with form 'a: 'b, thus the compiler only checks that all lifetime's restraints can be satisified, without actually choosing a specific "real lifetime" for each liftime. The only exceptions are that with 'a : 'b, 'b : 'a you can derive 'a = 'b.

But that's hardly enough. Consider this simple example:

fn run<'a>(s: &'a str) { /* ... */ }

let h: &'static str = "hello";
run(h);

The language does not see run(h) as run::<'static>(h) but as run::<'_1>(h), where 'static : '_1. Then the constraint solver see this is (obviously) satisfiable, then it stops. '_1 being 'static and not being 'static is equally valid. So you can't specialize your behaviour on that.

And simply saying "we always deduce it as longest lifetime possible" won't work, since lifetime does not have a total order, so you can't really say "longest liftime". And it's not like we always want longest lifetime possible anyway. (contravariance exists).

4 Likes
20

Not previously, but that's a good movement imo, as specialization is still a good ways off. It's probably blocked on the new trait solver in practice, at least. "Any downcasting" is a nice trick that covers most of min_specialization, and it'd be nice to be able to do so for potentially-non-'static generics as well, which I think will probably need to become possible to replace libcore's specialization usage with it.

The proposal will add "specialization safety" as a concept. No existing traits except Sized will be specialization safe, and only traits marked as being for specialization will be such.

The entire concept boils down to basically:
"Precise[1] specialization on arbitrary trait coherence is unsound, as trait satisfaction can rely on information which isn't available to impl selection. So how do we define a trait that can safely be specialized on, i.e. one whose impl requirements can only rely on information available to impl selection, while also allowing specialization to give access to?"

The answer, when the question is framed that way, and considering the existing TrustedTrait and TraitSpec patterns for specialization-like patterns, becomes pretty clear that a new class of traits fits the problem well. The difficulty is in actually figuring out exactly what a specialization trait is allowed to rely on, and how to maintain that functionality bridge back to the typical traits.

If we started Rust from scratch, would more traits just be specialization-safe? Very potentially; Copy should have been[2], and at least refinement traits like ExactSizeIterator are a decent candidate, as requiring its impl to only add specialization safe bounds on top of the Iterator impl's bounds seems reasonable.

It sort of is, and it sort of isn't. The "specialization trait" itself is a trait in that it's a name that can be used as a type generic bound that is opt-in by types to be satisfied. But it's also a relation between traits, because for specialization to be useful in practice, a generic likely needs to have some bound to be used in the baseline case, and some additional functional bound to be utilized in the specialized case.

But what about baseline traits that have bound requirements of their own? Those need a syntax for supplying those as baseline bounds to specialization traits in addition to the supertrait bound. Or should they be implied baseline bounds here (even though they aren't implied bounds for other impls)?

It's easier to list the baseline bounds in the list of bounds, even though they need to be set apart in some manner.

I kind of want to separate discussion of providing specializable bounds from providing specializations, since they're technically orthogonal concerns, and I'm a big proponent of the "expression" syntax for specialization over the "item" syntax (though I still think the latter should be available). And that's also a decent bit of new syntax to propose. But a full example of specialization in practice is indeed useful.

Example: TrivialClone specialization of clone_from_slice:

// SAFETY: `Clone::clone` is a simple copy
unsafe spec trait TrivialClone: default Clone {}

// impl blocks for TrivialClone are checked by the language
// to only use the same impl bounds as the type's Clone impl,
// `spec trait` bounds like on TrivialClone itself,
// and bounds present on the type (sometimes; complicated)
expression specialization 
impl<T> [T] {
    pub fn clone_from_slice(&mut self, src: &[T])
    where T: Clone {
        assert_eq!(self.len(), src.len());

        // only specialization-safe bounds are allowed in expression where
        where T: TrivialClone {
            let len = self.len();
            let src = src.as_ptr()
            let dst = self.as_mut_ptr();
            // TODO: drop *self or add TrivialDrop bound
            unsafe { ptr::copy_nonoverlapping(src, dst, len) };
        } else {
            for i in 0..self.len() {
                self[i] = src[i];
            }
        }
    }
}
item specialization 
impl<T> [T] {
    pub default fn clone_from_slice(&mut self, src: &[T])
    where T: Clone {
        assert_eq!(self.len(), src.len());
        for i in 0..self.len() {
            self[i] = src[i];
        }
    }

    override fn clone_from_slice(&mut self, src: &[T])
    // can only add specialization-safe bounds to default fn
    where T: Clone + TrivialClone {
        assert_eq!(self.len(), src.len());
        let len = self.len();
        let src = src.as_ptr()
        let dst = self.as_mut_ptr();
        // TODO: drop *self or add TrivialDrop bound
        unsafe { ptr::copy_nonoverlapping(src, dst, len) };
    }
}

Example: specialization of FromIterator for Vec

// SAFETY: Iterator::size_hint is accurate
pub unsafe spec trait TrustedLen: default Iterator {}

pub spec trait TrustedExactLen: default TrustedLen + ExactSizeIterator {}
impl<I: TrustedExactLen> ExactSizeIterator for I {
    fn len(&self) -> usize {
        let (lower, upper) = self.size_hint();
        debug_assert_eq!(upper, Some(lower));
        lower
    }
}
expression specialization 
impl<T> FromIterator<T> for Vec<T> {
    fn from_iter<I>(iter: I) -> Self
    where I: IntoIterator<Item = T> {
        // type equality is a specialization safe bound
        where I = vec::IntoIter<T> {
            // iter tycks as vec::IntoIter in this scope only
            // TODO: shrink if len < cap / 2
            Vec::from(iter) // why isn't this an existing impl
        } else
        // spec traits are specialization safe bounds
        where I: TrustedExactLen {
            let mut v = Vec::with_capacity(iter.len());
            iter.for_each(|item| unsafe {
                v.push_within_capacity(iter).unwrap_unchecked();
            });
            v
        } else {
            let size_hint = iter.size_hint();
            match iter.next() {
                None => Vec::new(),
                Some(first) => {
                    // TODO: small vecs are dumb
                    let mut v = Vec::with_capacity(size_hint.0);
                    v.push(first);
                    v.extend(iter);
                    v
                }
            }
        }
    }
}
item specialization 
impl<T> FromIterator<T> for Vec<T> {
    default fn from_iter<I>(iter: I) -> Self
    where I: IntoIterator<Item = T> {
        let size_hint = iter.size_hint();
        match iter.next() {
            None => Vec::new(),
            Some(first) => {
                // TODO: small vecs are dumb
                let mut v = Vec::with_capacity(size_hint.0);
                v.push(first);
                v.extend(iter);
                v
            }
        }
    }

    override fn from_iter<I>(iter: I) -> Self
    // spec traits are specialization safe bounds
    where I: IntoIterator<Item = T> + TrustedExactLen {
        let mut v = Vec::with_capacity(iter.len());
        iter.for_each(|item| unsafe {
            v.push_within_capacity(iter).unwrap_unchecked();
        });
        v
    }

    // type substitution is specialization safe refinement
    final fn from_iter(iter: vec::IntoIter<T>) -> Self {
        // TODO: shrink if len < cap / 2
        Vec::from(iter)
    }
}

The discussion here has clarified my thinking on the syntax and the blog post should be better off for it. Based on my drafting work so far, I think I can just use the item specialization syntax (that's basically the existing nightly syntax) for my examples and just put the expression specialization syntax in the follow up post. Expression specialization's main benefit is trivializing one of the semver concerns with item specialization, but that needs to be addressed for spec trait impls anyway, so it effectively ends up just being sugar over the semantics of item specialization.

I'm on track for a Sunday release of the blog post. Hopefully I don't miss anything and this actually can pave a path towards sound specialization.

  1. You could make full specialization "sound" if you are liberal with the "specialization is just for manual as-if optimization" juice, allow specialization to be a best-effort feature that randomly just doesn't happen, and be very careful to only call the more general implementation in potentially ambiguous cases. That's not a great solution. ↩︎

  2. I have a convoluted way in which Copy can be made specialization-safe over an edition boundary, but it's an ugly ugly hack compared to just using TrivialClone. ↩︎

4 Likes