Recently, there has been a lot of discussion about some form of "pattern types" or "value-restricted types": types that are just like a base type, but restricted to a narrower set of values. I've been thinking about this for a while, and there are some important subtleties to consider, relating to subtyping.
@oli-obk's post is a good introduction to this feature. The basic idea is that you take a type, say
i32, you take a pattern that matches on that type, say
1..3, and you get a new type, "
i32 that matches the pattern
i32 in 1..3). This allows you to enforce or declare extra invariants at compile-time, without having to manually declare a wrapper struct like the
The big question is, should pattern types use coercion or subtyping? E.g., should
2_i32 coerce to an
i32 in 1..3, or should it already be one? Subtyping is far more powerful:
- Allows seamlessly retrofitting current APIs to return pattern types, with no breaking changes.
- Allows pattern types to implement all the traits of their supertype.
However, subtyping implies variance, and variance is complicated. The following sections all assume that pattern types will use subtyping, and explore the implications.
The variance rules for pattern types should be the same as those for lifetimes.
i32 in 1..3 is a subtype of
i32 (henceforth denoted
(i32 in 1..3) <: i32), that implies:
&(i32 in 1..3) <: &i32
fn(i32) <: fn(i32 in 1..3)
- No relationship (invariance) between
&mut (i32 in 1..3)
This is because a pattern type is strictly more useful than its base type, just like a longer-lived type is more useful than a shorter-lived one.
One of the major features that pattern types bring is safe niches. A "niche" is a bit-pattern the Rust compiler knows a type can't hold, allowing it to do layout optimizations. For example,
Option<NonZeroUsize> is the same size as a
usize. Rust knows the
NonZeroUsize can't be 0, so it uses an all-0 value to represent
struct Wrapper(usize in 1..);
In the above,
Wrapper can have a niche.
Option<Wrapper> can use the same layout optimization as
Option<NonZeroUsize>, for the same reasons. But
Option<usize in 1..> cannot do this optimization. This is because
(usize in 1..) <: usize, and
Option is covariant (
for<T, U <: T> Option<U> <: Option<T>), so
Option<usize in 1..> <: Option<usize>. Therefore,
Option<usize in 1..> and
Option<usize> must have the same layout.
In conclusion, if pattern types are based on subtyping, wrapper types like
NonZeroUsize will still be needed to get layout optimizations, but those wrappers will become implementable in safe library code.
(i32 in 1..3) <: i32,
so (EDIT: not).
i32 in 1..3 implements all of
i32: Eq, therefore
(i32 in 1..3): Eq. So far, so good.
Until you realize that
(i32 in 1..3): Eq implies
(i32 in 1..3): PartialEq<i32 in 1..3>. But there is no
impl PartialEq<i32 in 1..3> for (i32 in 1..3) anywhere in the source code! And trait type parameters are invariant.
I'm not sure how best to solve this conundrum. Perhaps explicit variance annotations could help?
One possibility is to have pattern types that have no values:
i32 in !. These would be subtypes of their base type, and of every other pattern type for that base type, but would also freely coerce to and from the never type
! (this would not be a subtyping coercion). This might help more dead code typecheck.