Idea: where expression (as poor man’s specialisation)

language design
1

Let’s get straight to the chase:

pub struct MyVec<T> { /* ... */ }

impl<T> MyVec<T> {
    pub fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        where I: &[T] {
            self.extend_from_slice(iter)
        } else where T: Vec<T> {
            self.extend_from_vec(iter)
        } else {
            self.extend_from_iter(iter.into_iter())
        }
    }

    fn extend_from_iter<I: Iterator<Item = T>>(&mut self, iter: I) {
        where I::IntoIter : ExactSizeIterator {
            self.reserve(iter.len());
        }
        for item in iter {
            self.push(item)
        }
    }
}

Syntax-wise, the where expression would look like if. However, rather than a condition it would take a list of bounds. During monomorphisation body of the expression would be used if the bounds are satisfied and the else path would be taken if they aren’t.

Thanks to limited scope and imperative style, this would avoid most of the complications of specialisation while still offering many of the benefits.

Open question is whether the types of each branch would need to agree. For example, would this be possible:

pub trait PeekableIterator: Iterator { /* ... */ }

impl PeekableIterator for std::iter::Peekable { /* ... */ }

fn peekable<I: Iterator>(iter: I) -> impl PeekableIterator {
    where iter: PeekableIterator {
        iter
    } else {
        iter.peekable()
    }
}

At least initially requiring the same type would be sufficient and allow changes in the future if desired.

A bikeshedding question is whether where and if could be chained together as in where-else-if-else-where-else or whatever. (As an aside, for a while now I wished if and match could chain as in if-else-match without the need for braces and another indentation level around match).

1 Like
2

Same question as Idea: "Maybe Trait" Object and Bounds (an alternative form of specialization) - #16 by scottmcm -- how does this syntax resolve the existing problems that are caused by lifetimes being erased before monomorphization?

3

To be honest I don’t see where the problem is. Conceptually, function with where expressions can be replaced by a generic function with const bool arguments. For example something like the following:

pub fn extend<
    I: IntoIterator<Item = T>,
    const A: bool,
    const B: bool,
>(&mut self, iter: I) {
    if A {
        let iter: &[T] = unsafe { transmute(iter) };
        self.extend_from_slice(iter)
    } else if B {
        let iter: Vec<T> = unsafe { transmute(iter) };
        self.extend_from_vec(iter)
    } else {
        self.extend_from_iter(iter.into_iter())
    }
}

Same goes for linked maybe traits proposal. A <T: ~Trait> can be transformed into <T, const T_impls_Trait: bool>.

4

Well for one the MyVec::extend only compares to concrete types, not trait impls, and does so completely void of lifetimes (I: &[T]).

But I think if there is a "min min specialization" that works and is easier to stabilize than the existing "min specialization," it's one of:

  • it's just Any's API, i.e. downcast to specific types and any not-syntactically-'static types either aren't allowed or always fail to downcast; or
  • it's what I've called "specialization without specialization" — exclusively just conditionally applicable default trait method bodies, and the actual impl block for a type chooses a single one for all covered types.

Current "min specialization" isn't contentious primarily due to syntax or power or breaking some substitution principle, it's problematic due to the subtleties of the always applicable rule. If it were a code coherency issue, we'd just stick specialization restrictions in the orphan rules and be fine, but that's not the core challenge.

This is only true when the where bounds do not capture any input lifetimes. If they are allowed to do so, then this at best makes non-generic functions generic. We don't monomorphize for lifetimes; given fn(&T), the same code is used for 'static and 'tiny lifetimes, and where bounds can require that lifetime to be 'static or outlive some other lifetime; information which the function no longer contains after lifetimes have been erased.

TL;DR: if you specialize on a lifetime, it's unsound. Whatever rules you use to restrict specialization must forbid specializing on lifetimes. The issue is how that works, not anything solvable just by expressing specialization in a different manner.

3 Likes
5 
trait Foo {}
impl Foo for &'static u64 {}

static FOO: u64 = 0;

fn foo(_: impl Foo) {}
fn bar(u: &u64) { foo(u) }

fn main() { foo(&FOO); }

The above doesn’t compile and no one has issues with it. In the same way I don’t see any issues with lifetimes being erased through calls to non-generic functions.

And with transformation I’ve proposed bounds included in where expressions would be propagated up the call chain where all lifetime information is present.

if you specialize on a lifetime, it's unsound.

Do you have an example of that on hand? Bounds would be found to be satisfied only if the compiler sees that lifetimes are satisfied. I don’t see how that could lead to unsoundness. For example, in where I: &[T] compiler should be able to conclude the bound is met since it knows that slice outlives the function call.

6

I'm pretty sure they need to agree. Otherwise something like this is possible:

trait Marker {}

impl Marker for &'static str {}

fn build<T>(_: T) -> impl std::fmt::Debug {
    where T: Marker {
        ()
    } else {
        std::rc::Rc::new(true)
    }
}

fn main() {
    let x = build("foobar");
    // Typeck knows x: () → Send
    // Codegen produces x: Rc<bool> → !Send
    std::thread::spawn(move || println!("{x:?}"));
}

It might be sound when the types need to agree. At least I couldn't think of an example to cause unsoundness for that variant with only safe code.

But there's still the same surprising behavior that all specialization proposals share: As lifetimes are erased, the compiler cannot safely assume that types with lifetimes compare equal during monomorphization:

fn foo<T,U>(x: T, y: U): bool {
    where U: T {
        println!("same");
    } else {
        println!("different");
    } 
}

fn main() {
    foo(1_i32, 2_i32); // would print "same"
    foo("a", "b"); // would print "different"
}

It could also get easy to break assumptions in libraries using where blocks when traits are only implemented for some super-/subtype and coercions occur (see e.g. #85863).

7

Unfortunately it is more subtle than that. This post is a few years old now but it covers the problem: Shipping specialization: a story of soundness · Aaron Turon

There's also this later post on a potential way to support more kinds of specialization while still banning lifetime dispatch: http://smallcultfollowing.com/babysteps/blog/2018/02/09/maximally-minimal-specialization-always-applicable-impls/

2 Likes
8

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