I've started a pre-RFC following on from PoignardAzur's RustNL survey. I hope we can get the ball rolling again with this language feature.
The HackMD document is here: https://hackmd.io/@clf-6_YiQ-WD4mO9-o2k9A/variadics-pre-rfc. Please leave comments & suggests on HackMD, which I will be checking more frequently!
I'm now heading off to the Edinburgh Fringe for a week, but I might find time to address comments in between performances!
I see that the pre-RFC acknowledges that, but I want to reiterate that Rust already has some building blocks for a trait-based design that would allow being generic over tuples without adding additional syntax for variadic generics: it's the machinery used by the HList trait alongside HCons and HNil from frunk (which is isomorphic to tuples). That's what is used in some languages like Haskell and Purescript as well.
To make this solution work with Rust tuples we need two things. First, a special, compiler-implemented type Cons that builds a tuple from its head and tail (so that a tuple (a, b) desugars to a Cons underneath). Then, we need some provision that disallows taking references to the tail, because in tuples the tail may not be contiguous in memory, and that's the difference between tuples and frunk's hlists. This is probably not more restrictive than variadics because variadics, too, would have to deal with this.
(To expand on that point, the tuple (u16, u32, u16) may reorder the fields for better packing, while frunk's HCons<u16, HCons<u32, HCons<u16, HNil>>> don' t, and that's why you can get a reference to the tail in an hlist but you can't get a &(u32, u16) out of that tuple)
the cons list idea is indeed simple, but is insufficient even in many simple cases:
trait Collapse {
type Res;
}
impl Collapse for () {
type Res = ();
}
impl<T, R: Collapse> Collapse for (T, ..R, T) {
type Res = (T, ..R::Res);
}
the above is one of a good few useful patterns which a cons approach cannot support. in this case, we canāt express that the cons list both starts and finishes with some element. with cons lists generally, itās not impossible to represent something like this, but the language features required to express this using cons lists (not including the cons list implementation itself) are significantly more complex (and are significantly more controversial) than implementing variadic tuples in the way i propose.
also, rustc is not very good at working with deeply nested types, and using cons lists would be a significant regression in performance and expressibility.
note that my suggested algorithm for variadic trait solving (not yet in pre-RFC; iām still ironing out the kinks) takes a lot of inspiration from cons list approaches, but supercharges them to support a wider set of use cases.
Like this!
builtin # unpack($expr)ā ā Perhaps this should be a macro? Or perhaps macros shouldnāt be able to expand to unpack expressions. Either way, should be discussed.. vs ... bikeshed (Iām personally partial to using ... for all variadics, including transitioning rest patterns to it over an edition)let tuple: (..A, ..B) = unimplemented!(); and let tuple: (T, ..A, U, ..B) = unimplemented!(); examples are confusing. Itās obvious that compilation should fail for several reasons, less clear which reason you intended to highlight.Note that elements in tuples aren't laid out consecutively ā a (u8, u16, u8) may have the same layout as (u16, u8, u8), in a way that minimizes padding.
This makes destructuring part of a tuple with rest @ .. potentially more expensive than destructuring part of a slice. It also makes it impossible to destructure part of a tuple with ref rest @ .. (or the equivalent with match ergonomics). And it might make inductively defined algorithms harder to optimize.
An alternative is to provide built-in macros, like std::tuple::{fold, map}, to serve as primitives.
Fundamentally, '@ rest' should not return a tuple of the tail. It is nearly non-viable while maintaining a zero cost philosophy. However, inductive definitions remain possible. I've been playing around myself with working on a zero overhead general purpose generics library, and the technology there applies equally well to this more limited case.
The trick is this: Rather than an inductively defined tuple, we have an inductively defined 'progress system'.
Imagine a setup more like the following:
pub trait ValidTuplePart<Struct> {}
pub trait IsTuple : ValidTuplePart<Self::Struct> {
type Struct;
}
impl ValidTuplePart<TupleEnd> for () {}
impl<A: ?Sized> ValidTuplePart<TupleEnd> for (A,) {}
impl<A: ?Sized> ValidTuplePart<TupleCons<A, TupleEnd>> for (A,) {}
impl<A: ?Sized> IsTuple for (A,) {
type Struct = TupleCons<A, TupleEnd>;
}
impl<A, B: ?Sized> ValidTuplePart<TupleEnd> for (A, B) {}
impl<A, B: ?Sized> ValidTuplePart<TupleCons<B, TupleEnd>> for (A, B) {}
impl<A, B: ?Sized> ValidTuplePart<TupleCons<A, TupleCons<B, TupleEnd>>> for (A, B) {}
impl<A, B: ?Sized> IsTuple for (A, B) {
type Struct = TupleCons<A, TupleCons<B, TupleEnd>>;
}
impl<A, B, C: ?Sized> ValidTuplePart<TupleEnd> for (A, B, C) {}
impl<A, B, C: ?Sized> ValidTuplePart<TupleCons<C, TupleEnd>> for (A, B, C) {}
impl<A, B, C: ?Sized> ValidTuplePart<TupleCons<A, TupleCons<B, TupleCons<C, TupleEnd>>>> for (A, B, C) {}
impl<A, B, C: ?Sized> IsTuple for (A, B, C) {
type Struct = TupleCons<A, TupleCons<B, TupleCons<C, TupleEnd>>>;
}
pub const fn head_offset<
Head: ?Sized,
Tail,
Tuple: ?Sized + ValidTuplePart<TupleCons<Head, Tail>>>() -> isize;
Here, we can just pass around the original or pointers to it, and use head_offset to find the currently relevant field, regardless of the layout order. Writing an ergonomic interface around this for all cases like Rc and such is tricky. But this is sufficient to make it work in a way that after monomorphization and only a tiny bit of inlining things like functions that are actually safe transmutes or offsets, combined the various recursions of these functions should be zero cost.
Slapping inline on those transmutes and offsets should be trivial (though making sure that it optimizes them the same as ordinary field access might require setting some flags maybe?) and teaching the compiler to inline calls when there is a decreasing tuple argument should therefore be sufficient on top of a tiny bit of magic.
It would also benefit from teaching the coherence checker that IsTuple as a bound captures exactly and only the tuple types, so instances for tuple types can be declared in one fell swoop, rather than merely being able to define functions that operate over all tuples.
Explanation of how it is used:
You can recursively go through the fields of a tuple by starting at the IsTuple::Struct type until you reach TupleEnd. At each TupleCons you can locate the current field you want to focus on. Safety guarantees include that if you start at IsTuple::Struct and end at TupleEnd you will have handled all the fields exactly once, fully initializing or deinitializing the entire thing.
Since the head_offset function takes a specific tuple type, reordering tuple fields in memory is fine. It could even be changed into a function that takes an integer index, though that would add a potential complexity around tuples consisting of more than usize elements (obviously a lot of which would have to be ZSTs, and admittedly probably will make most compilers unhappy anyway), as simply iterating up to build the constant passed in would then be unsafe. As its current for is unary, it is a genuine natural number rather than a bounded value. Still, probably best to make sure that mixups like the Rc overflow are avoided upfront rather than simply assume that no such tuples will ever be used, or have (admittedly perhaps const time) panics on overflow.
Reading through this, it made me think that what is needed is a reference type for part of a tuple. (That might be what soundlogic2236 intends too.) A TupleSlice, if you will.
pub struct TupleSlice<'a, const FIRST: usize, const LAST: usize, T> {
data: &'a T
}
It's a (not fat) reference to a tuple, with const generics keeping track of the start and end, and the full type of the original tuple encoded as the T parameter.
The compiler could implement tuple indexing on this type, such as foo.0 turns into foo.data.{0 + START}, and you're forbidden from indexing past LAST.
Since the full tuple type is encoded in it, the layout is unaffected.
Hopefully you can forgive my rough implementation that I wrote a few minutes ago on the playground. But you can implement this manually today if you don't mind implementing it for each size of tuple.
So something like:
impl<'a, const FIRST: usize, const LAST: usize, T> TupleSlice<'a, FIRST, LAST, (T,)> {
fn first(&self) -> &T {
&self.data.0
}
}
impl<'a, const LAST: usize, T, U> TupleSlice<'a, 0, LAST, (T,U)> {
fn first(&self) -> &T {
&self.data.0
}
fn rest(&self) -> TupleSlice<'a, 1, LAST, (T, U)> {
make_slice::<2, LAST, _>(&self.data)
}
}
impl<'a, const LAST: usize, T, U> TupleSlice<'a, 1, LAST, (T,U)> {
fn first(&self) -> &U {
&self.data.1
}
}
fn make_slice<'a, const FIRST: usize, const LAST: usize, T>(data: &'a T) -> TupleSlice<'a, FIRST, LAST, T> {
TupleSlice::<'a, FIRST, LAST, T> { data }
}
A real implementation would do bounds checking, have a split_at(), a last(), etc.
If there was some way to do self.data.{0 + START}, I think you could implement this without the .. syntax extension. Today, you both cannot do the const math on tuple indexing, and you cannot do .0 when you take a completely generic type T you can't do tuple indexing at all, and there's nothing like (..T; N) to capture the size of the tuple.
Since the full tuple type is encoded in it, the layout is unaffected.
Exactly. This is key to making it a zero cost abstraction. I think the inductive structure is useful for making it easier to write trait instances though, and using usizes hits the issue I mentioned in my post.
Readonly slices are pretty easy, but mut or more slices get tricky fast, since they represent exclusive access to noncontinuous portions of memory.
While I gave a 'minimal' interface turning it into your TupleSlice (inductively defined) is pretty easy. first just uses the offset function to find the relevant location using a bit of pointer arithmetic. And like my design your rest is just a transmute, which if inlined should be able to be made zero cost.
Having split_at and last and bounds checking all hit issues though. The fundamental problem for the first two is typing them. While rust is capable of the required type level manipulations for such, the ergonomics of actually using them in most cases won't be very good. And if it is inductively defined bounds checking becomes somewhere between automatically implemented and pointless, since it works out to a recursive call and you have to write the code for "what happens when I call this on TupleEnd" if you permit it at all, and decide what type to return.