# variadic generics attempt #80973022
* Feature Name: (`variadic_tuples`)
* Start Date: (fill me in with today's date, YYYY-MM-DD)
* RFC PR: [rust-lang/rfcs#0000](https://github.com/rust-lang/rfcs/pull/0000)
* Rust Issue: [rust-lang/rust#0000](https://github.com/rust-lang/rust/issues/0000)
# Summary
[summary]: #summary
Implement a solution for minimal-surface-area variadic generics
by extending the responsibility of tuples to arbitrary arities:
```rust
#![feature(variadic_tuples, tuple_trait)]
trait FrobTuple {
fn frobnicate() -> usize;
}
impl FrobTuple for () {
fn frobnicate() -> usize {
0
}
}
impl<T, R: Tuple> FrobTuple for (T, ..R) {
fn frobnicate() -> usize {
1 + R::frobnicate()
}
}
type Frobbable = (u8, u16, u32, u64, u128);
assert_eq!(Frobbable::frobnicate(), 5);
```
# Motivation
[motivation]: #motivation
Across the Rust ecosystem,
[there](https://docs.rs/bevy_ecs/latest/bevy_ecs/query/trait.WorldQuery.html#impl-WorldQuery-for-(F0,))
[are](https://docs.rs/diesel/latest/diesel/prelude/trait.Queryable.html#impl-Queryable%3CRecord%3C(ST0,)%3E,+Pg%3E-for-(T0,))
[many](https://docs.rs/leptos/latest/leptos/ev/trait.EventHandler.html#impl-EventHandler-for-(A,))
[examples](https://doc.rust-lang.org/stable/std/hash/trait.Hash.html#impl-Hash-for-(T,))
of traits implemented for tuples of varying (but never *arbitrary*) arity.
Macros ease the pain of these implementations somewhat,
but, [as Alice Cecile explained for Olivier Faure](https://poignardazur.github.io/2024/05/25/report-on-rustnl-variadics/#do-we-really-need-variadics),
this situation is far from ergonomically robust:
> * It produces terrible error messages.
> * The compile times cost is high.
> * Code using this pattern is hard to read and review.
> * Its documentation is terrible.
Additionally, there are many APIs which could very elegantly be expressed as variadic functions,
but, due to the lack of variadic support are either macros
(like the [`futures::join`](https://docs.rs/futures/latest/futures/macro.join.html) macro)
or functions taking two parameters
(like, well, the [`futures::join`](https://docs.rs/futures/latest/futures/future/fn.join.html) function).
Note that the case for `futures::join` [used to be](https://github.com/rust-lang/futures-rs/issues/2215)
so problematic (even disregarding the poor ergonomics) that the project had separate `join{3..=5}` functions.
This kind of API fragmentation is difficult to teach, difficult to maintain, and difficult to use.
Official Rust documentation is not shy about the need for variadic generics,
between rustdoc's internal `doc(fake_variadic)` attribute [(seen here)](https://doc.rust-lang.org/stable/std/primitive.tuple.html#impl-Debug-for-(T,))
and [this wording](https://doc.rust-lang.org/stable/std/primitive.tuple.html#trait-implementations-1) in the primitive `tuple` documentation:
> Due to a temporary restriction in Rust’s type system,
> the following traits are only implemented on tuples of arity 12 or less.
> In the future, this may change:
The list of people who want variadics doesn't end there either:
* [`std::iter::zip`](https://doc.rust-lang.org/stable/core/iter/fn.zip.html)
* [`futures::select`](https://docs.rs/futures/latest/futures/macro.select.html),
and (of course) [`futures::select`](https://docs.rs/futures/latest/futures/future/fn.select.html)
* [A mirror for Rust](https://soasis.org/posts/a-mirror-for-rust-a-plan-for-generic-compile-time-introspection-in-rust/)
(JeanHeyd Meneide) got people excited about compile-time introspection, but without variadic generics,
the MVP there uses some hacks involving const generics which are seriously limited.
* [`itertools::iproduct`](https://docs.rs/itertools/latest/itertools/macro.iproduct.html)
* Lots of parser combinators in `winnow` and similar projects:
- [`alt`](https://docs.rs/winnow/latest/winnow/combinator/fn.alt.html)
- [`permutation`](https://docs.rs/winnow/latest/winnow/combinator/fn.permutation.html)
- [`Parser` itself](https://docs.rs/winnow/latest/winnow/trait.Parser.html)
* The ECS folks want variadics for their dynamic machinations:
- [`bevy_ecs`'s `insert`](https://docs.rs/bevy_ecs/latest/bevy_ecs/system/struct.EntityCommands.html#method.insert)
- [`bevy_reflect::Tuple`](https://docs.rs/bevy_reflect/latest/bevy_reflect/trait.Tuple.html)
- [`shipyard::World::add_entity`](https://docs.rs/shipyard/latest/shipyard/struct.World.html#method.add_entity)
- [`hecs::World::spawn`](https://docs.rs/hecs/latest/hecs/struct.World.html#method.spawn)
- [The whole `legion::storage` module](https://docs.rs/legion/latest/legion/storage/index.html)
could be cleaned up with
[one particularly egregious example](https://docs.rs/legion/latest/legion/storage/trait.ConsFlatten.html)
* There are a handful of homogenous methods which could do with taking a variable number of arguments,
something that this RFC endorses. Note that these improvements would be purely ergonomic,
and wouldn't express anything a const-generic array parameter couldn't.
- `std::cmp::min` and `std::cmp::max`
# Guide-level explanation
[guide-level-explanation]: #guide-level-explanation
Variadic tuples extend the behavior and utility of tuples to an arbitrary number of elements.
## Interpolation
This necessarily includes support for interpolating tuples at the type and value levels.
### Composition of tuple types
The elements of one tuple can be "unpacked" to be stored inline within another tuple
with the new `..T` (spread) type operator.
The definition of tuples is extended such that their elements are either "inline" or "unpacked":
```rust
// `T`, then all the elements from `A`
type Prepend<A, T> = (T, ..A);
// all the elements from `A`, then `T`
type Append<A, T> = (..A, T);
// all the elements from `A`, then all the elements from `B`
type Concat<A, B> = (..A, ..B);
// `Identity1<A> == A`
type Identity1<A> = (..A,);
// This is identical to the above; notice the lack of a trailing comma.
type Identity2<A> = (..A);
// ERROR: the spread operator cannot be used outside of a tuple!
type Identity3<A> = ..A;
```
Note that the spreading does not recursively flatten tuples, so `(..(A, (), B))`
can be simplified to `(A, (), B)`, not `(A, B)`.
For unpacking to be well formed, operands must only implement the (currently unstable) `Tuple` trait:
```rust
// ERROR: `u8` cannot be unpacked because it is not a tuple!
type Unpacked = (..u8);
```
### Composition of tuple values
A key difference of this RFC compared to those prior, is that it does not propose any new syntax for composition and destructuring of tuple values.
Instead the following interface is requested for `core` and `std`:
```rust
pub mod tuple {
pub fn concat<A: Tuple, B: Tuple>(a: A, b: B) -> (..A, ..B);
pub fn prepend<R: Tuple, T>(rest: R, first: T) -> (T, ..R) ;
pub fn append<R: Tuple, T>(rest: R, last: T) -> (..R, T);
}
```
> [!note]
> The rules and definitions outlined later in this RFC are sufficient to (`unsafe`ly) implement these functions
> with no additional support from the language.
> Equally, they could be compiler intrinsics which would likely improve compilation speed.
>
> Either way, [a reference implementation](#appy-ref-stdlib-tuple) is provided in the RFC appendices.
## Inference
Binding to an arbitrary number of generics, then is a simple as imposing a bound on `Tuple`.
The compiler can perform the inference required to fit variadic types against eachother:
```rust
fn split_first<T, R: Tuple>(_tuple: (T, ..R)) -> (T, R) {
todo!()
}
// ERROR: expected a tuple with 1 or more element, found one with 0 elements.
let (t, r) = split_first(());
// The `R` type parameter is inferred to be `()`.
let (t, r) = split_first((A,));
```
## Induction
For more complex usages, traits can be implemented [inductively][induction] for tuples of varying lengths.
We can define some number of finite _base cases_ and a recursive _inductive step_
which extends the applicability of the implementations to arbitrary arity:
```rust
trait AllTuples {}
// (1) --- a base case for length 0 (unit) tuples
impl AllTuples for () {}
// (2) --- the inductive step for tuples with length |R| + 1
impl<T, R: Tuple> AllTuples for (T, ..R) {}
fn all_tuples<T: AllTuples>() {}
fn any_tuple<T: Tuple>() {
// Even though `T: Tuple` does not trivially imply `T: AllTuples`,
// The compiler is nevertheless (very loosely) able to figure it out:
//
// 1. It finds that impl (2) holds for any tuple with 1.. elements
// but not for the unit tuple, so we additionally have to check
// for an impl matching that case.
// 2. Then, it finds impl (1) does hold for the unit tuple.
// 3. Therefore, `T: AllTuples` must hold exhaustively
// over all possible tuple values of `T`.
//
// So we can deduce (using both impls) that `T: AllTuples`
// always holds given `T: Tuple` and so the call compiles.
//
// Note that since the "truth" of the `T: AllTuples` bound
// relies on two distinct impls, resolving the bound
// has *no effect on inference*.
all_tuples::<T>()
}
```
[induction]: https://en.wikipedia.org/wiki/Mathematical_induction
# Reference-level explanation
[reference-level-explanation]: #reference-level-explanation
## Syntax
The tuple type syntax is extended to the following:
> _TupleElem_ :\
> [_Type_]\
> | `..` [_Type_]
>
> _TupleType_ :\
> `(` `)`\
> | `(` `..` [_Type_] `)`\
> | `(` ( _TupleElem_ `,` )<sup>+</sup> _TupleElem_<sup>?</sup> `)`
[_Type_]: https://doc.rust-lang.org/reference/types.html#type-expressions
## Morphology
A tuple can be conceptualised syntactically as a heterogenously typed sequence of *elements*,
where each element takes one of the following forms:
- Inline, like both the `A` and `B` in `(A, B)`.
- Unpacked, like the `A` in `(..A, B)`.
This sequence of elements can be decomposed semantically into a heterogenously typed list of *fields*
under the following scheme:
- Inline elements correspond directly to fields.
- Unpacked elements "flatten" their constituent fields directly into their encompassing tuple.
Take, for example, the following decomposition of a tuple type into its elements and fields:
```text
elements: 0 1 2 3
| | ┌──────┴──────┐ |
(A, B, ..(C, D, ..()), E)
| | | | |
fields: 0 1 2 3 4
```
> [!note]
> Once tuples are constructed, elements are a purely conceptual aid.
> The compiler is free to eagerly unpack and restructure
> elements as it pleases.
Also consider the type of `tup` in the following case:
```rust
fn variadic<R1: Tuple, R2: Tuple>(tup: (A, ..R1, B, ..R2, C)) {
dbg!(tup.1);
let (v, .., u) = tup;
}
```
It is clear from the above definitions that `tup` has five elements but the types of its fields are less clear.
`tup.0` is surely `A` but once we reach the `..R1` element, things become more hazy.
### Rigidity
[rigidity]: #rigidity
To formalize this, let us define _tuple-rigid_ types like the `R1` and `R2` above:
* Asking "Is this type tuple-rigid?" is only relevant for types which implement `Tuple`.
* Tuple-rigid types are types whose (tuple) fields cannot be enumerated within a particular environment.[^tuple-rigid-parenv]
* That is, types which cannot be comprehensively normalized (yet).
* Put another way, tuple-rigid types 'just don't know' what their fields are.
* In this context, they are similar to _rigid aliases_ with the notable distinguishing inclusion of type parameters.
[^tuple-rigid-parenv]: See [the unresolved questions][unresolved-questions] for a discussion of this wording.
### Field Index & Position
[field-indices]: #field-index-position
With rigidity in mind, we can re-define tuple field access:
* All fields of a tuple have either both a position and an index, or neither;
both properties are unique within any given tuple.
* Tuple indexing (like `tup.0`) uses a field's index while pattern matching (like `(_, ..) = tup`) uses a field's position.
* A field index is an ordinal index, allocated from left to right to all known fields, after normalization.
- As a result, tuple-rigid elements are _not allocated any field indices_.
- In the above example, therefore, `tup.0` is `A`, `tup.1` is `B` and `tup.2` is `C`.
* A field's position is a pair of distances, measured in number of fields, from the head and tail of the tuple respectively.
- One or both of these distances may not be known because the field is 'flanked' by a tuple-rigid element,
so this can be conceptualised like `(Option<usize>, Option<usize>)`.
- Pattern matching a field compares the corresponding positional distance with the field's place in the pattern,
so in the above decomposition, `v` is `A` and `u` is `C`.
- As an unfortunate corollary, `B` is inaccessible through pattern matching.
* These rules aren't perfect. See [the unresolved questions][unresolved-questions].
A complex example fully elaborated (`-` marks non-applicability):
```
element index: 0 1 2 3 4
| | ┌──────┴──────┐ ┌─┴─┐ ┌───┴──┐
(A, B, ..(..R1, C, D), ..R2, ..(E, F))
| | └─┬─┘ | | └─┬─┘ | |
field index: 0 1 (*) 2 3 (*) 4 5
field pos. head: 0 1 - - - -
field pos. tail: - - - - 1 0
(*) conceptually, there may be fields here, but they are not directly accessible.
```
> [!note]
> The compiler must be careful to respect field indices through the many modes of compilation.
> During monomorphization, fields are "discovered" as generic tuple-rigid types are instantiated with rigid types.
> The compiler must ensure that the intent of the user does not change as new fields are discovered.
## Variadics in the type system
### Analytical fundamentals
Recall the definition for [tuple-rigid types][rigidity] defined earlier.
Understanding tuple-rigidity is essential to modelling variadic inference.
Fewer and fewer types are considered tuple-rigid as compilation progresses,
loosely mirroring
[the compiler's `TypingMode` enum](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_infer/infer/canonical/ir/enum.TypingMode.html):
* During coherence, we are very coarse and conservative, ensuring for soundness that
* During analysis, something else.
* In post-analysis, no types are tuple-rigid.
### Coherence
#### Double rigidity rule
One particular issue comes during impl-wfck.
Under the stated model, we accept the following:
```rust
trait Foo {}
impl<T: Tuple, U: Tuple> Foo for (..T, ..U) {}
```
And yet it's obvious that `T == (); U == (u8,)` and vice versa both defer to the same impl (with different generic parameters).
It's possible that in the future we could (for example) unambiguously constrain `U == ()`,
but there doesn't seem to be any benefit to allowing this.
Instead, we can consider `T` and `U` unconstrained and report an [`E0207`](https://doc.rust-lang.org/error_codes/E0207.html),
leaving us with the following error[^drr-message] for the above example:
```
error[E0207]: the type parameter `T` is not constrained by the impl trait, self type, or predicates
--> src/lib.rs:3:6
|
3 | impl<T: Tuple, U: Tuple> Foo for (..T, ..U) {}
| ^ unconstrained type parameter
|
= note: tuples containing more than one tuple-rigid element do not constrain any parameters referenced between them
```
The explanation for `E0207` should be extended accordingly.
<details>
<summary>Algorithmic details</summary>
<br />
In the compiler, this algorithm could look very roughly like the following.
This should augment the current search for constrained parameters in
[`rustc_hir_analysis::constrained_generic_params`](https://github.com/rust-lang/rust/blob/master/compiler/rustc_hir_analysis/src/constrained_generic_params.rs#L65):
```rust
let Some(head) = tuple.position(|el| el.is_unpacked_and_tuple_rigid()) else {
// Fallback to structural search (current implementation).
visit_all(tuple);
return;
};
let tail = tuple.rposition(|el| el.is_unpacked_and_tuple_rigid()).unwrap();
if head == tail {
// There's just one tuple-rigid element. Treat it as normal.
visit_all(tuple);
} else {
// There's more than one tuple-rigid element. Only constrain the edges around them.
visit_all(tuple.take(head).chain(tuple.skip(tail + 1)));
}
```
We get lucky that the only types which can be spread during impl-wfck are tuples, parameters, and aliases,
so we can distinguish tuple-rigid types structurally, without invoking any heavy machinery.
---
</details>
[^drr-message]: This doesn't really feel like a particularly satisfying error message. Any suggestions?
***TODO — SATISFYING PROOF***
### Candidate Selection
# Drawbacks
[drawbacks]: #drawbacks
* This feature adds significant complexity (and subtlety) to a type system which some users are already overwhelmed by.
* It is hard to say without benchmarking which would have the worse effect on compile times,
between the macro-dependent "fake variadics" currently in the wild
(increasing code complexity, mostly only when they are explicitly used),
or the implementation of this language feature
(increasing compiler complexity, perhaps even when left unused).
* The change to the formulation of tuple types violates several implicit assumptions in Rust today: ***TODO***
# Rationale and alternatives
[rationale-and-alternatives]: #rationale-and-alternatives
## Axioms of design
This RFC aims to..[^two-dots]
[^two-dots]: Yes. I'm using two dots for my ellipses. I'm that petty.
### introduce as few new language constructs as possible
* This is an MVP. We don't need the full gamut of ergonomic and usability improvements yet.
We need a foundation for variadic generics in the type system;
we can be conservative.
* We don't want to burden the Rust project, language, and developers with sweeping changes
where existing concepts suffice.
### be versatile
* A lot of people, doing a lot of different things, want variadic generics to work well.
We need a flexible implementation to ensure everyone is happy.
* We should provide composable fundamentals which people can build on in library code.
### do things the Rust way
* No post-monomorphization errors. Zero-cost abstractions leveraging the type system.
## Common conclusions
These are propositions which are frequently referenced in the following discussions.
### Post monomorphization errors
[no-post-mono]: #post-monomorphization-errors
Rust has taken a firm stance against post-monomorphization errors.[^monomorphization-invariant]
The compiler can only emit PMEs when..
* it hits the type-level recursion limit,
* it encounters a panic during CTFE,
* something else?
Variadic generic implementations (especially those discussed in [the prior art section][prior-art])
are often "lazy", in that they don't resolve constraints imposed by variadic parameters until monomorphization time.
This implementation must be careful to ensure generic items are consistent with their monomorphized counterparts.
[^monomorphization-invariant]: See, for instance, [the next-gen trait solver invariants](https://rustc-dev-guide.rust-lang.org/solve/invariants.html#generic-goals-and-their-instantiations-have-the-same-result-).
### Variadic moves
[no-variadic-moves]: #no-variadic-moves
Currently, the compiler reserves the right to freely and arbitrarily compose the layouts of tuple types.
For instance, there's no guarantee that `(A, B, C)` has a layout which is remotely comparable to `(B, C)`.
More concretely, according to a recent nightly[^so-called-latest-nightly] by virtue of
[a very useful trick from Ralf Jung's blog](https://www.ralfj.de/blog/2020/04/04/layout-debugging.html):
```yaml
# the layout of `(u16, u8, u32)`
# the `u16` field, the `u8` field, 1 byte of padding, and then the `u32` field
┌─────────┬───────────┬─────┬─────┬───────────────────────┐
│ byte │ 0 | 1 │ 2 │ 3 │ 4 | 5 | 6 | 7 │
├─────────┼───────────┼─────┼─────┼───────────────────────┤
│ meaning │ u16 │ u8 │ ... │ u32 │
└─────────┴───────────┴─────┴─────┴───────────────────────┘
# for comparison, the layout of `(u8, u32)`
# the `u8` field, 3 bytes of padding, and then the `u32` field
┌─────────┬─────┬─────────────────┬───────────────────────┐
│ byte │ 0 │ 1 | 2 | 3 │ 4 | 5 | 6 | 7 │
├─────────┼─────┼─────────────────┼───────────────────────┤
│ meaning │ u8 │ ... padding ... │ u32 │
└─────────┴─────┴─────────────────┴───────────────────────┘
```
We can see clearly that between the two tuple types, the `u8` field "moves" two bytes.
Rust assumes — for very good reasons — that (modulo calling convention), all uses of a particular type have the same layout.
For this reason, moving fields out of tuples variadically (e.g. with support from a `..` pattern)
might require arbitrary shuffles of tuple fields and so
is not necessarily $\mathcal{O}(1)$ as with all other moves, but ends up $\mathcal{O}(n)$.
Variadic moves are deemed prohibitively inefficient and as such,
this RFC includes no such first-class support for such an operation.
Prior art here includes [this UCG discussion](https://github.com/rust-lang/unsafe-code-guidelines/issues/105).
## Alternatives for the elements of this RFC
### Type interpolation syntax
There are many options for writing the spread operator; they have been ranked in reverse order of preference:
1. `T...`. The triple dot syntax has merit considering it matches C-variadic arguments,
but equally may be conflated with that analagous but unrelated syntax.
2. `T..` is (1) except avoids the C-style `...` in favour of Rust-style ellipses (`..`).
It's also quicker to type. The argument that
3. `...T` is preferred to (1) because since Rust is read left-to-right.
Placing the demarcating token at the front of the syntax generally improves readability.
This also has consistency with typescript et al. and their spread support.
4. `..T` combines the benefits of both (2) and (3).
### Field indexing
Recall the motivating example for [field indexing][field-indices] above.
```rust
fn variadic<R1: Tuple, R2: Tuple>(tup: (A, ..R1, B, ..R2, C)) {
dbg!(tup.1);
let (v, .., u) = &tup;
}
```
There are other designs to consider which do not involve distinguishing indices and positions:
* We could intepret `tup.1` as the first field of `R1` but we are
immediately presented with the possibility that `R1 == ()` and it has no first field.
* Equally, suggesting `tup.1` should be the first field of `R1` or `B` if it is empty
makes the type of `tup.1` unnameable and meaningless
(we could know _at the most_ that it were `Sized`).
Regardless, this only moves the problem one field down; we certainly could never access `C` with this design.
* We could instead choose to reject `tup.1` and so on, allowing only `tup.0` to be a valid field access.
This is the least ambiguous but also the most inexpressive option
as we could at best only read the value of the `A` field.
These solutions all have significant flaws and so this RFC proposes the index/position split above:
* This solution ensures `A`, `B`, and `C` are all accessible.
* It's a slightly artificial definition, but still preserves backcompat.
* It is expected type inference will help out in the general case, ensuring users are aware of what they're plucking.
### Implementation syntax
#### `union impl`
The explicit decision was made in this RFC not to introduce new syntax for inductive impls.
Something like the following could be implemented:
```rust
trait Foo {}
union impl Foo for () {}
union impl<T, R: Tuple> Foo for (T, ..R) {}
```
This would probably allow us more efficient trait resolution, as well as improved clarity-of-implementation.
However, if we modify our example, its not so clear (from the compiler's perspective)
what is it we're actually `union`-ing:
```rust
trait Bar<T: Tuple> {}
union impl Bar<()> for ! {}
union impl Bar<T, R: Tuple> for ! {}
```
We could instead try modifying usage sites:
```rust
trait Bar<T: Tuple> {}
impl Bar<union ()> for ! {}
impl<T, R: Tuple> Bar<union (T, ..R)> for ! {}
```
But we can still make things harder for poor little `rustc`:
```rust
// where do we put `union` here..
trait Baz<T: Tuple> {}
trait Qux {}
impl Qux for ! {}
impl<Q: Qux> Baz<()> for Q {}
impl<T, R: Tuple> Baz<(T, ..R)> for ! {}
// this should still work because `!: Baz<()>` is still true,
// but the impls are not so directly comparable.
```
The benefits are woolly and the concept is pretty brittle too, so this RFC has discarded it.
#### Unification via specialization
```rust
trait RevTuple {
type Rev: Tuple;
}
impl RevTuple for () {
type Rev = ();
}
impl<T, R: Tuple> RevTuple for (T, ..R) {
type Rev = (..<R as RevTuple>::Rev, T);
}
```
> [!caution]
> Specialization is not coming any time soon.
> There are other good reasons to want to reject this idea,
> but the burden of implementation alone makes it infeasible.
With traditional specialization, we would be able to do something like the following:
```rust
trait Foo {
fn foo() -> usize;
}
default impl<T: T
```
```rust
trait Foo {
fn foo() -> usize;
}
impl<T: Tuple> Foo for T {
fn foo() -> usize {
static if T == () {
0
} else {
1
}
}
}
```
This gets us some of the way, but it's still not clear how we would loop over
### `static for`
`static for` is a suggestion for a kind of compile-time loop unrolling which would enable
interaction with variadic generics:
```rust
fn variadic<T: Tuple>(tup: T) {
static for field in tup {
dbg!(field);
}
}
// such that
variadic((1u8, 2u16, 3u32));
// monomorphizes to the equivalent of
fn variadic(tup: (u8, u16, u32)) {
dbg!(tup.0);
dbg!(tup.1);
dbg!(tup.2);
}
```
This certainly looks simpler than the recursion-heavy approach above,
but it also could not compile.
Nowhere did we impose a `Debug` bound on any element of `T`, and so `dbg!(field)` is certainly invalid in the general case.
Things quickly get uncharted too when we want to map tuples, as with `std::iter::zip` and `std::cmp::max`.
There's no such type-`for` we can leverage or implement easily and so we're still left with needing a recursive trait definition.
Utilmately, there's no way to leverage `static for` to any significant degree
without some other pretty powerful (and far overreaching) language features[^static-for-dependencies].
[^static-for-dependencies]:
Many are outlined in [Jules Bertholet's design sketch][bertholet-sketch] but none seem fully appropriate.
## Tuple trait distributivity
Many prior variadic proposals have needed explicit syntax for binding against lists of types satisfying some bounds, e.g.
```rust
fn debug_all<T: (..Debug)>(ts: T) {
todo!()
}
```
We're left with the complementary problem to `static for` in that we have clever syntax for a variadic type,
but no way to iterate over its values without making the syntax redundant. We might as well do:
```rust
trait DebugAll: Tuple {
fn dbg(&self);
}
impl DebugAll for () {
fn dbg(&self) {}
}
impl<T, R: DebugAll> for (T, ..R) {
fn dbg(&self) {
}
}
```
# Prior art
[prior-art]: #prior-art
## Analysis of variadic generics in other languages
### Varargs
Baseline support for variadic parameters is present in many languages (often called "varargs").
These are nearly always composed as a single list of arguments written inline at the end of the argument list.
Implementations of this feature are largely split into two categories:
* Untyped ([C-style](https://en.cppreference.com/w/c/language/variadic))
- Rust [already has support](https://doc.rust-lang.org/reference/items/external-blocks.html#variadic-functions)
for this type of parameter in `extern` blocks.
- These are problematic for use in Rust because they are not type-checked during compilation[^c-var-monster]
(i.e. they are inherently unsafe).
* Typed ([C#-style](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/method-parameters#params-modifier))
- While typed variadic parameters are safe,
they provide very little benefit over simply taking a collection of values as an argument, as they are required to be homogenously typed.
- They are better suited languages with polymorphic typing by default
since inheritence can mock heterogenously typed collections.
Regardless, varargs do not support the kinds of operations [people want to do at compile time][motivation]
and allow for a form of function overloading
which is separate from (and likely more controversial than) the features proposed in this RFC.
[^c-var-monster]: Have a look at [this example](https://c.godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,selection:(endColumn:1,endLineNumber:14,positionColumn:1,positionLineNumber:14,selectionStartColumn:1,selectionStartLineNumber:14,startColumn:1,startLineNumber:14),source:'%23include+%3Cstdio.h%3E%0A%23include+%3Cstdarg.h%3E%0A%0Aint+problematic_variadic(int+count,+...)+%7B%0A++++va_list+args%3B%0A++++va_start(args,+count)%3B%0A%0A++++for+(int+i+%3D+0%3B+i+%3C+count%3B+i%2B%2B)+%7B%0A++++++++int+x+%3D+va_arg(args,+int)%3B%0A++++++++printf(%22%25i+:%3D+%25i%5Cn%22,+i,+x)%3B%0A++++%7D%0A++++va_end(args)%3B%0A%7D%0A%0Aint+main()+%7B%0A++++problematic_variadic(2,%0A++++++++//+passing+an+int+is+fine!!%0A++++++++10,%0A++++++++//+passing+a+float+is+dangerous!!%0A++++++++10.0f)%3B%0A%7D%0A'),l:'5',n:'1',o:'C+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:cg141,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'0',intel:'0',libraryCode:'0',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,libs:!(),options:'',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+gcc+14.1+(Editor+%231)',t:'0'),(h:output,i:(compilerName:'x86-64+gcc+14.1',editorid:1,fontScale:14,fontUsePx:'0',j:1,wrap:'1'),l:'5',n:'0',o:'Output+of+x86-64+gcc+14.1+(Compiler+%231)',t:'0')),k:50,l:'4',n:'0',o:'',s:1,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4) as a pointer towards how things can go wrong.
### [Parameter packs (C++)](https://en.cppreference.com/w/cpp/language/parameter_pack)
Parameter packs are a maximal implementation of variadic generics,
providing the algebraic fundamentals required for many [complex compile-time operations](https://stackoverflow.com/questions/17178075/how-do-i-reverse-the-order-of-element-types-in-a-tuple-type).
Resolution of variadic parameter packs happens as part of monomorphization (because they are tied to `template`s).
If we follow this paradigm, our implementation of variadic generics will inevitably be as brittle
and prone to evoking post-monomorphization errors as C++ templates are.
so this approach to implementation is unfavourable.[^bad-cpp-variadics]
[D also has support for variadic templates](https://dlang.org/articles/variadic-function-templates.html#d-solutions)
in much the same capacity with a good deal less historical fulsomeness.
It can be said, however, that the recursive design of variadic generics outlined in this RFC
is reminiscent of the style of many C++ and D variadic usage patterns, and so should be familiar for migrating developers.
Compare a fitting C++ algorithm:
```cpp
constexpr int tuple_len()
{
return 0;
}
template<typename T, typename... Ts>
constexpr int tuple_len(T, Ts... rest)
{
return 1 + tuple_len(rest...);
}
```
With the corresponding Rust:
```rust
trait TupleLen {
const LEN: usize;
}
impl TupleLen for () {
const LEN: usize = 0;
}
impl<T, R: Tuple> TupleLen for (T, ..R) {
const LEN: usize = 1 + <R as TupleLen>::LEN;
}
```
[^bad-cpp-variadics]: See also [the relevant RFC appendix](#appy-cpp-spread) on C++'s spread syntax.
### [comptime (Zig)](https://ziglang.org/documentation/master/#comptime)
Variadic generics fall out naturally from Zig's comptime analysis:
because the language supports "types as first class values" (unconstrained higher-kinded types),
procedural generation of custom tuple types is easy.
With the stabilization of GATs two years ago, Rust has adopted its own model of constrained higher-kinded types.
GATs have a rigid interface which promotes "algebraic", pure manipulation of types.
Any model of comptime for Rust priviledged enough to support variadic generics
necessarily defies this precedent by providing unrestrained access for messing with the type system,
While comptime is not a detrimental feature in its own right,
it is fundamentally incompatible with Rust's current design and philosophy
and leads to the same kind of post-monomorphization tragedies [outlined above](#parameter-packs-c).
## Partial implementations in stable Rust
### [`frunk`](https://docs.rs/frunk)
* Provides a cons list approach to implementing variadic generics.
* Construction of nested tuples is made ergonomic through macros.
* [The `HCons::sculpt` method](https://docs.rs/frunk/latest/frunk/hlist/struct.HCons.html#method.sculpt)
provides structural morphing for tuples to a limited degree.
* Unpacking, interpolation & concatenation of multiple variadic tuples is not possible.
* Cons-based approaches are a tradeoff:
- They are _very_ well understood theoretically, and used widely.
- On the other hand, they
- With a cons list like `cons(A, cons(B, cons(C, nil)))`,
explicit care must be taken when interacting with reverse-chirality cons lists like `snoc(snoc(snoc(nil, A), B), C)`
(to borrow notation from Coq) and "favouritism" is shown towards one orientation.
For instance, [`HCons::prepend`](https://docs.rs/frunk/latest/frunk/hlist/struct.HCons.html#method.prepend)
is a very simple method, but the commensurable `HCons::append` does not exist (but can be implemented with some hassle).
- Its not clear how the self-similar shape of cons lists would interact with layout calculations in the compiler.
* Due to the lack of language support, the library is even more trait and recursion heavy than this PR,
impacting compile times and complexity.
## RFCs
> [!tip]
> Closed discussions are demarcated with a ticked checkbox.
* [x] (2017-02-22) [Conservative variadic functions](https://github.com/rust-lang/rfcs/pull/1921)
(sgrif)
* [x] (2017-02-28) [Tuple-Based variadic generics](https://github.com/rust-lang/rfcs/pull/1935)
(cramertj)
* [x] (2019-05-22) [Add generalized arity tuples](https://github.com/rust-lang/rfcs/pull/2702)
(Woyten)
* [x] (2019-10-02) [Variadic tuples](https://github.com/rust-lang/rfcs/pull/2775)
(fredericvauchelles)
* [x] (2016-05-17) [Tuple cons cell syntax](https://github.com/canndrew/rfcs/blob/tuple-cons-cell/text/0000-tuple-cons-cell.md)
(canndrew)
## Pre-RFCs & Sketches
* (2013-10) [Draft RFC: variadic generics](https://github.com/rust-lang/rfcs/issues/376)
(eddyb)
* (2017-09) [Support flattening of tuples](https://github.com/rust-lang/rfcs/issues/2138)
(Nokel81)
* (2018-07) [Idea for minimal variadic type parameters](https://internals.rust-lang.org/t/idea-for-minimal-variadic-type-parameters/7686)
(tmccombs)
* (2019-09) [Brainstorming: variadic & type expressions](https://internals.rust-lang.org/t/brainstorming-variadic-type-expressions/10935)
(lordan)
* (2023-06) [Variadic generics design sketch][bertholet-sketch]
(Jules Bertholet)
* (2023-07) [`static for` and `static if` to manipulate variadic generics](https://internals.rust-lang.org/t/static-for-and-static-if-to-manipulate-variadic-generics/19230)
(xmh0511)
* (2023-09) [A madman's guide to variadic generics](https://internals.rust-lang.org/t/a-madmans-guide-to-variadic-generics/19605)
(outdated)
(soqb)
* (2023-10) [Pre-RFC: Array expansion syntax](https://internals.rust-lang.org/t/pre-rfc-array-expansion-syntax/13490)
(nwn)
## Previous Analyses
* (2021-01-30) [Analysing variadics, and how to add them to Rust](https://poignardazur.github.io/2021/01/30/variadic-generics/)
(PoignardAzur)
* (2022-04-03) [rust-variadics-background](https://github.com/alice-i-cecile/rust-variadics-background)
(Alice Cecile)
* (2023-11-08) [Variadic generics, again](https://poignardazur.github.io/2023/11/08/time-for-variadic-generics/)
(PoignardAzur)
* (2024-05-25) [Report on variadic generics discussion at RustNL][faure-rustnl]
(PoignardAzur, various contributors)
[bertholet-sketch]: https://hackmd.io/@Jules-Bertholet/HJFy6uzDh
[faure-rustnl]: https://poignardazur.github.io/2024/05/25/report-on-rustnl-variadics/
## Special Thanks
This RFC is building on the work of many other contributors,
and I would particularly like recognise the following contributors who have yet walked this accursed path:
* [PoignardAzur](https://github.com/PoignardAzur/) for their undying commitment to getting variadics moving,
and for being excited and dilligent enough about the feature to conduct [a survey on it at RustNL 2024][faure-rustnl].
* [Jules Bertholet](https://github.com/Jules-Bertholet) for their [variadics design sketch](bertholet-sketch)
which serves as an invaluable comparison of different prior designs.
* [Alice Cecile](https://github.com/alice-i-cecile) whose work for [Bevy](https://github.com/bevyengine/bevy)
exposed especially tenderly what we miss out on without variadics.
* [eddyb](https://github.com/eddyb) for getting the ball rolling, all those *(eleven!)* years ago.
# Unresolved questions
[unresolved-questions]: #unresolved-questions
* [ ] What syntax (if any) should eventually be stabilised for composing and destructuring tuple values, without introducing performance footguns?
* [ ] What should the exact rules be for considering an element to be [tuple-rigid][field-indices]?
Common sense suggests anything eager deep normalization could reveal, but perhaps that's overzealous.
If these rules change, it might reorder field indices, and cause breakages.
The rules would have to be changed over an edition boundary.
# Future possibilities
[future-possibilities]: #future-possibilities
> [!tip]
> Remember, and this goes for [the appendices][appies] as well, that future possibilities are not part of the RFC proper.
> Discussion of these suggestions is welcome but only in moderation.
> Progress on this issue should not be hampered by orthogonal analysis.
>
> As with any feature which lurks in the rustc cultural zeitgeist for more than a decade,
> there are quite a lot of future possibilities on the cards.
> This section aims to analyze them exhaustively,
> but equally some may be incompatible with others.
>
> For ease of review, they are split into the categories based on likelihood.
## Limbo
> [!note]
> These features are all but required at some point down the line,
> but their designs are still out of scope and unfinished under this RFC.
>
> There's a lot of syntax sugar here, but they do open things up here and there.
### Variadic functions
[variadic-funcs]: #variadic-functions
Should function parameters be permitted to be variadic like the following?
```rust
// Tentatively suggested syntax:
fn many_args<T: Tuple>(..args: T) { }
// Alternative syntax:
fn many_args<T: Tuple>(args: ..T) { }
// Or even.. this:
fn many_args<T: Tuple>((args @ ..): T) { }
```
Note that (as written) this allows the following form of overloading, and so may become problematic:
```rust
trait Overload: Tuple { }
impl Overload for (u8,) { }
impl Overload for (i8,) { }
impl Overload for (u8, i8) { }
fn overloaded<T: Overload>(..params: T) { }
```
It's also non-trivial to resolve the ABI concerns of these functions.
#### Parser Ambiguity
Discerning readers might be aware that as written there's a syntax conflict
between variadic parameter binding (`..ident`) and the range-to pattern (`..VALUE`) in parameters.
Unless pattern types are stabilised, though, there is no possible way
to make a top-level range-to pattern compile in a function parameter
(because they are always refutable) so the syntax above _could_ be reserved without breakage:
```rust
const MAX: i32 = i32::MAX;
// ERROR: exclusive range missing `i32::MAX`
fn foo(..MAX: i32) {}
```
Equally, irrefutable range patterns are always equivalent to wildcard patterns[^range-wildcard-equality-lint]
(which are more common and easier to digest), so this is somewhat unlikely to cause confusion.
[^range-wildcard-equality-lint]: Is there a reason (other than lack of interest/attention) that
[we don't already lint](https://play.rust-lang.org/?edition=2021&gist=c79d4a137c2afaf18598135522846f06) in this case?
### Variadic closures
On the other hand, it would also be natural to use the unpacking operator for something like `fn(..T) -> U`.
Though on its own, this is not useful since there's neither a way to declare function as accepting variadic parameters,
nor the syntax for calling one.
Therefore, it might be useful to allow this syntax (at an intermediary stage) for closures only.
This would likely be less controversial than allowing full-fat variadic functions
as closures already behave rather more subtly, and don't have the same ABI concerns.
This would enable some powerful (but perhaps unfavourable) patterns:
```rust
trait CurryOnce {
type Arg;
type Next;
fn cur(self, arg: Self::Arg) -> Self::Next;
}
// impl for 1 param:
impl<A, U, F> CurryOnce for F
where
F: FnOnce(A) -> U
{
type Arg = A;
type Next = U;
fn cur(self, arg: A) -> U {
self(arg)
}
}
// impl for 2.. params:
impl<A, B, U, R: Tuple, F> CurryOnce for F
where
F: FnOnce(A, B, ..R) -> U
{
type Arg = A;
type Next = impl FnOnce(B, ..R) -> U;
fn cur(self, a: A) -> Self::Next {
// Proposed syntax:
move |b: B, ..rest: R| {
// NB: repeated variadic construction is a performance footgun,
// but this is a toy example:
let args = std::tuple::concat((a, b), rest);
self.call_once(args)
}
}
}
let sum = |a: u8, b: u16, c: u32| a as usize + b as usize + c as usize;
assert_eq!(sum.cur(1).cur(2).cur(3), 6);
```
This would also get us along the way to unclogging the fn-traits and `"rust-call"` ABI (***TODO: justify***).
### Inline rest binding
Let's say we want to use our shiny new variadic generics to improve `std::iter::zip`.
Here's a naïve approach (method bodies omitted to better illustrate our problem):
```rust
pub struct Zip<T>(T);
pub trait Zippable {
type Zipped: Tuple;
}
impl Zippable for () {
type Zipped = ();
}
impl<T: IntoIterator, R: Zippable> Zippable for (T, ..R) {
type Zipped = (T::IntoIter, ..R::Zipped);
}
impl Iterator for Zip<()> {
type Item = ();
}
impl<T: Iterator, R> Iterator for Zip<(T, ..R)> where Zip<R>: Iterator<Item = R> {
type Item = (T::Item, ..R::Item);
}
pub fn zip<T: Zippable>(iters: T) -> Zip<T::Zipped>;
```
Unfortunately, this implementation is not remotely compatible with `std::iter::zip`:
1. `zip` has gone from binding two parameters to binding one (that happens to be a variadic tuple).
2. Correspondingly, `zip` now has one generic parameter, not two.
3. The structure of the `Zip` type has also changed in a similar way.
Sure, we could assume [variadic functions][variadic-funcs] are supported but we are still left with (2) and (3).
To circumvent this, we could introduce rest bindings on generic parameters like so:
```rust
// Here, `T: Tuple` is a proposition, not an assumption.
// We could require the annotation for explicitness,
// but that does feel a bit redundant.
struct Zip<..T>(T);
// ✂️..
// Here, though, we need more granularity on the bounds for `T`,
// and we also need to introduce some syntax to spread type arguments over variadic parameter lists.
// This should be reminiscent of rest binding for variadic closures.
pub fn zip<..T: Zippable>(..iters: T) -> Zip<..T::Zipped>;
```
This way, existing usages like `zip::<Vec<u8>, [u16; 2]>(vec![0], [1, 2])` could continue to compile.
Exact details are not the responsibility of this RFC, but some provisional points are outlined here:
* There's no need to require variadic bindings come last in the parameter list, as is often touted,
but it must not be followed by any defaulted parameters (for ambiguity's sake).
## Malebolge
> [!warning]
> These ideas aren't very well realised.
### Relax the `Sized` requirement on tuples
Under this RFC, the responsibility of tuples grows to encapsulate a much broader responsibility;
not just a container for heterogenous values, tuples become an all-purpose container for heterogenous types.
Yet, they universally would still require all but the last field to be `Sized`.
If, through one of various means, we could allow more than one field to be unsized,
we would open up possible types like `(str, [u8], dyn Debug)` which seem like useful abstractions in their own right.
### Tuple struct field spreading
Under this RFC, variadic values are limited to being stored in traditional tuple types.
If we want to do something more specific, like interact with `repr(C)`, we'll need something like the following.
Note that it's possible support for this could be mocked with clever use of a cons-based approach
but it wouldn't be a perfect mirror, and this syntax in particular is consistent and probably wouldn't go amiss:
```rust
#[repr(C)]
struct FfiTuple<R: Tuple>(..R);
// 🤨 maybe even..
#[repr(packed)]
struct SmallTuple<R: Tuple>(..R);
```
### Tail borrowing
This RFC does not propose any support for binding the tuple rest _pattern_ (`..`) to an identifier.
This is because of the [stated issues with variadic moves][no-variadic-moves] and their unpredictable and expensive
effects on layout.
The same issue infects borrows: we can't easily take a reference to part of a tuple like we can with, say, a slice.
What [has been suggested](https://github.com/rust-lang/rfcs/issues/376#issuecomment-58464680)
is using `ref ident` with rest patterns to bind not a reference to a tuple, but a tuple of references, e.g.
```rust
let tup: (A, B, C, D) = todo!();
// The type of `rest` here is not `&(B, C, D)`
// but instead `(&B, &C, &D)`.
let (first, ref rest @ ..) = tup;
```
This kind of pattern isn't subject to the same layout trickery
since `(&A, &B, &C, &D)` is effectively[^reference-tuple-pattern-layout-woe] comparable to a `[&_; 4]`.
This doesn't really seem that useful though. There's no way to use this recursively;
if we tried, we'd end up with `&&&&D` which feels problematic.
We certainly want some ergonomics for tuples-of-references eventually as this is expected to be a common pattern,
but it's not quite clear what that would look like.
[^reference-tuple-pattern-layout-woe]:
This isn't a particularly difficult property for the compiler to guarantee,
but it's not actually formally specified yet.
\
Also note that fat pointers are not an issue
since the references all hail from values on the stack which are always `Sized`.
## The Inferno
> [!caution]
> These ideas don't constitute anything serious yet. It's not obvious we'd actually want these;
> everything here is highly speculative, poorly fleshed out, and should be treated appropriately.
### Interoperability with arrays
***TODO**
### Parameter packs
***TODO + MAYBE MOVE?***
### Compile time introspection
***TODO (WITH NOTE NOT TO WAX TOO POETIC; DON'T WANT TO ATTRACT THE WRONG ATTENTION)***
### Liquid typing & `const` match
With the introduction of refinement types for supporting pattern types,
it seems not infeasible to provide syntax for matching on compile-time constructs,
like `const`s and `type`s, rather than runtime values:
```rust
fn foo<const N: usize>() {
// match is guaranteed to execute at monomorphization time.
const match N {
0 => println!("zero.."),
_ => println!("not zero!"),
}
}
```
It's no secret that the trait based approach outlined in this RFC is pretty palavorous.
Perhaps we could leverage some kind of specialization-style type matching to improve the situation:
```rust
const fn frob<T: Tuple>() -> usize {
// totally made up and very improbable syntax:
const match T {
() => 0,
// Note that because this match happens at compile time,
// and on types rather than values,
// this isn't really a variadic move!
(A, R @ ..) => 1 + frob::<R>(),
}
}
```
#### Generic Patterns
Equally, patterns themselves pose an interesting proposition.
While patterns today have limited impact on inference and must be a single rigid[^all-patterns-are-rigid] type,
there are syntactic forms which could match any one of many types.
The relevant example here are tuple patterns with a rest operator.
Something like the following could one day be possible, although its impacts on typing are very poorly defined:
```rust
const fn frob_by_value(a: impl Tuple) -> usize {
// even more made up syntax:
match a {
() => 0,
(_, ..)
}
}
```
[^all-patterns-are-rigid]: I tried initially to find a way around this, but [the compiler even correctly dismisses
`StructuralPartialEq` opaque types](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2024&gist=d544852432f87f04da3c1893af51be48).
# Appendices
[appies]: #appendices
<details name="appy-ref-stdlib-tuple">
<summary>A reference implementation of the <code>std::tuple</code> module:</summary>
<br />
A key issue here is avoiding [variadic moves][no-variadic-moves].
A naive implementation for `concat` which recursively calls a relatively simple `prepend` or `append` is unacceptably slow
since it may require reconstituting the entire tuple for every insertion,
making the algorithm $\mathcal{O}(n^2)$.
Instead we provide a bespoke (and unwieldy) implementation of `concat`, constructing the combined tuple in place using `MaybeUninit` and pulling elements from `ManuallyDrop` source tuples (which are destructured in place).
Hence, we stay $\mathcal{O}(n)$.
```rust
#![feature(variadic_tuples, tuple_trait)]
use std::mem::{ManuallyDrop, MaybeUninit};
/// Reads the value of the field in `tup`
/// immediately after the fields contributed by `A`
/// (i.e. the one with type `T`).
///
/// # Safety
/// The field is read by copy, but this is a semantic move.
/// Care must be taken to ensure UB is not triggered by reusing the value
/// (hence the `ManuallyDrop`).
unsafe fn read_in_place<A: Tuple, T, B: Tuple>(
tup: &ManuallyDrop<(..A, T, ..B)>,
) -> T {
// NB: the `..A` element of `(..A, T, ..B)` is tuple-rigid
// and therefore the `.0` field is `T`.
let field: *const T = &raw const tup.0;
// SAFETY: the caller contract ensures the field's value
// is not reused to exhibit UB, and `field` is definitely
// pointing to a valid `T`.
unsafe { field.read() }
}
/// Writes a value to the field in `tup`
/// immediately after the fields contributed by `A`
/// (i.e. the one with type `T`).
fn write_in_place<A: Tuple, T, B: Tuple>(
tup: &mut MaybeUninit<(..A, T, ..B)>,
t: T,
) -> T {
// NB: the `..A` element of `(..A, T, ..B)` is tuple-rigid
// and therefore the `.0` field is `T`.
// SAFETY: we only use the dereferenced ptr place to write-only borrow one of its fields.
let field: *mut T = unsafe { &raw mut (*tup.as_mut_ptr()).0 };
// SAFETY: raw borrow of `MaybeUninit` field ensures `field` is valid-for-writes.
unsafe { field.write(t) }
}
pub fn concat<A: Tuple, B: Tuple>(a: A, b: B) -> (..A, ..B) {
/// Writes to a partially initialized tuple (_the destination_),
/// from another tuple (_the source_).
///
/// The source is always a strict subsequence of the fields in the destination.
///
/// Let us give proper definitions to the type parameters involved here:
/// * `Self` is _the infix_
/// which is the part of the source which we'll write to the destination.
/// * `IA` is _the inner prefix_
/// which holds fields which come before the infix in the source.
/// * `OA` is _the outer prefix_
/// which holds fields which come before the source in the destination.
/// * `OB` is _the outer suffix_
/// which holds fields which come after the source in the destination.
///
/// In summary:
/// * _the infix_ is `Self`
/// * _the source_ is `(..IA, ..Self)`
/// * _the destination_ is `(..OA, ..IA, ..Self, ..OB)`
/// * Note there is no "inner suffix" because the way we recurse
/// through the structure of the tuple does not require it.
///
/// The (complex) design of this trait is to preserve the structure of
/// both the source and the destination as we recurse,
/// avoiding expensive layout shuffles.
unsafe trait Unpack<OA: Tuple, OB: Tuple, IA: Tuple>: Tuple {
/// Initializes the the infix of `dst` from the `src` tuple.
///
/// # Safety
/// The infix is semantically moved out of the source.
/// Care must be taken to ensure UB is not triggered by reusing it.
unsafe fn write(dst: &mut MaybeUninit<(..OA, ..IA, ..Self, ..OB)>, src: &ManuallyDrop<(..IA, ..Self)>);
}
// SAFETY: This is the trivial implementation for a unit infix.
unsafe impl<OA: Tuple, OB: Tuple, IA: Tuple> Unpack<OA, OB, IA> for () {
unsafe fn write(dst: &mut MaybeUninit<(..OA, ..IA, ..OB)>, src: &ManuallyDrop<IA>) {
// The infix is the unit tuple; we have nothing to write.
}
}
// SAFETY:
// * This initializes the infix by inductive recursion.
// * See (1) and (2) in the implementation of `write`.
unsafe impl<OA: Tuple, OB: Tuple, IA: Tuple, T, IB: Tuple> Unpack<OA, OB, IA> for (T, ..IB) {
#[inline]
unsafe fn write(dst: &mut MaybeUninit<(..OA, ..IA, ..Self, ..OB)>, src: &ManuallyDrop<(..IA, ..Self)>) {
// SAFETY: We don't use this field again. See the shift at (2).
let t = unsafe { read_in_place::<SA, T, SB>(src) };
// NB (1): The first field of the infix is now initialized.
write_in_place::<(..OA, ..IA), T, (..IB, OB)>(dst, t);
// NB (2):
// * This recursive call initializes all other fields of the infix.
// * Notice how the types of the `src` and `dst` arguments do not change,
// but the `Unpack` traitref does, so this points to a different function.
// * In particular, the infix has changed from `(T, ..IB)` to `IB`
// which implies eventually we will call the base case,
// initializing every remaining field of the infix along the way.
// * Correspondingly, the inner prefix has changed from `IA` to `(..IA, T)`
// to preserve the types of `src` and `dst`.
// * In this way, we have effectively "shifted the cursor"
// one field to towards the back, allowing us to recurse.
<IB as Unpack<OA, OB, (..IA, T)>>::write(dst, src)
}
}
/// A safe wrapper for `Unpack::write` which uses the whole `src` tuple as the infix.
fn unpack<A: Tuple, B: Tuple, T: Tuple>(
dst: &mut MaybeUninit<(..A, ..T, ..B)>,
src: T,
) {
let ref src = ManuallyDrop::new(src);
// SAFETY: `src` is never used again.
unsafe { <T as Unpack<A, B, ()>>::write(dst, src) }
}
let mut dst = MaybeUninit::<(..A, ..B)>::uninit();
unpack::<(), B, A>(dst, a);
unpack::<A, (), B>(dst, b);
// SAFETY:
// * `dst` is `MaybeUninit<(..A, ..B)>`.
// * The first `unpack` call above writes `A` to the start of `dst`.
// * The second `unpack` call above writes `B` after `A` to `dst`.
// * Therefore, the whole of `dst` is initialized correctly.
unsafe { dst.assume_init() }
}
pub fn prepend<R: Tuple, T>(rest: R, first: T) -> (T, ..R) {
concat((first,), rest)
}
pub fn append<R: Tuple, T>(rest: R, last: T) -> (..R, T) {
concat(rest, (last,))
}
```
</details>
---
<details name="appy-cpp-spread">
<summary>A discussion of issues with C++ spread syntax:</summary>
<br />
It should also be noted, variadics in C++ are a bit of a mess.
A mixture of strained compatibility with C[^cpp-oxford-variadic] and inflexible design
means much of their functionality is through hard coded behaviour and special-cased syntax.
The C++ spread operator (`...`) is overloaded to manage all of the following responsibilities:
* [C-style varargs](https://en.cppreference.com/w/cpp/language/variadic_arguments) (`void f(int, ...)`)
* [Template parameter pack bindings](https://en.cppreference.com/w/cpp/language/pack)
(`template<typename... Args>`) under one of:
- `typename`
- `class`
- [any constraint concept](https://en.cppreference.com/w/cpp/language/constraints)
* [Function parameter pack bindings](https://en.cppreference.com/w/cpp/language/pack) (`void f(Args... args)`)
* [Pack expansion in argument lists, initializer lists, and template argument lists](https://en.cppreference.com/w/cpp/language/pack#Function_argument_lists) (`args...`)
* [Pack indexing](https://en.cppreference.com/w/cpp/language/pack_indexing) (`args...[n]`)
* [Four different kinds of fold expression](https://en.cppreference.com/w/cpp/language/fold):
- unary right-associative (`args || ...`)
- unary left-associative (`... || args`)
- binary right-associative (`0 + ... + args`)
- binary left-associative (`args + ... + 0`)
- (note there is a particular snafu with this syntax in that in `a + ... + b`,
`a` and `b` are syntactically equivalent but semantically distinct)
* [Four different kinds of lambda capture](https://en.cppreference.com/w/cpp/language/lambda#Lambda_capture)
- simple by-copy (`[args...] {}`)
- simple by-reference (`[&args...] {}`)
- by-copy with initializer (`[...args = std::move(args)] {}`)
- by-reference with initializer (`[&...args = std::move(args)] {}`)
- (why do the ellipses move..?!)
* [Dynamic exception specification](https://en.cppreference.com/w/cpp/language/pack#Dynamic_exception_specifications)
(`throw(Args...)`)
* [the `sizeof...` operator](https://en.cppreference.com/w/cpp/language/sizeof...)
which — as may not come as a surprise by now — has effectively nothing semantically in common with the `sizeof` operator.
* [Pack expansion in attribute lists](https://en.cppreference.com/w/cpp/language/pack#Attribute_list) (`[[attr(args)...]]`)
* [Variadic using declarations](https://en.cppreference.com/w/cpp/language/using_declaration) (`using Args::method...`)
* [Variadic friend declarations](https://en.cppreference.com/w/cpp/language/friend) (`friend Args::Nested...`)
It goes without saying we want something for Rust which is a little less 'seat-of-the-pants'.
[^cpp-oxford-variadic]: Leading to the horribly awkward but wonderfully named [_Oxford variadic comma_](https://eisenwave.github.io/cpp-proposals/oxford-variadic-comma.html) proposal.
</details>
<!-- final footnotes -->
[^so-called-latest-nightly]: Turns out to be `rustc 1.86.0-nightly (ed43cbcb8 2025-01-21)`.
Sign in with Wallet
Connect another wallet