interaction of tuple layout and variadic generics

[nikomatsakis]

@cramertj mentioned in the lang-team sync meeting that they had some concerns about the rules we specified for tuple layout and their interaction with variadic generics. I'm not entirely sure what they had in mind, but I'm opening this issue so that we track it down and figure it out.

(Also, I believe that @sgrif was mentioned as having an interest, and of course I know @eddyb cares about this -- so cc y'all.)

[cramertj]

The rule specified that (u8, u32, u8) would have the same representation as struct Foo(u8, u32, u8); and struct Foo { x: u8, y: u32, z: u8 }. This is a problem if you want to allow tail-borrowing of tuples:

let x = (1u8, 2u32, 3u8);
let (_, y @ ..) = &x;
// y is now `&(u32, u8)`

Tail-borrowing is a pretty convenient tool which would simplify some problems raised by variadic generics. However, it would require that the representation of tuples must contain the representation of its tail. That is, (H, Tail...) can only be represented in memory as (H, Tail...) or (Tail..., H), not (Tail[0], H, Tail[1..]) etc.

Because we want to allow structs field order to be permuted arbitrarily, we don't want to specify that tuple representation and struct representations match, as this would prohibit tail-borrowing variadics.

[hanna-kruppe]

Leaving aside the question of whether the loss of layout optimizations for tuples is acceptable, can you elaborate on how tail borrowing helps with variadic generics? I'm aware of how it's used in rust-lang/rfcs#1582, but your rust-lang/rfcs#1935 instead proposed a conversion from reference-to-tuple to tuple-of-references-to-elements which (as the RFC itself notes) avoids the unfortunate layout implications of tail borrowing, while (AFAICT) providing the same functionality in the end. Is there anything insufficient about that approach?

[cramertj]

@rkruppe The unfortunate thing about that approach is that you always wind up with two trait impls-- one for a reference of tuples which delegates to a tuple of references. It works, but it's vaguely unergonomic. I'm not meaning to express a preference for one approach over another in this thread-- I just wanted to point out that there are valid reasons we might want to avoid specifying the layout of tuples as matching the layout of structs, and that overspecifying at this point could constrain us in future lang design choices.

[sgrif]

@rkruppe Short version (to avoid rehashing the entire RFC here) is that you either end up with coherence issues, poor ergonomics, or the need for additional complex features like mapping over a tuple and generic closures. It also would require ATCs no matter what. Ideally we'd write:

impl Clone for () {
    fn clone(&self) -> Self {
        ()
    }
}

// postfix ... unpacks, prefix collects. `Tail` with no `...` is the tuple of the tail elements
impl<Head, Tail...> Clone for (Head, Tail...)
where
    Head: Clone,
    Tail: Clone,
{
    fn clone(&self) -> Self {
        let (ref head, ref ...tail) = *self;
        (head.clone(), tail.clone()...)
   }
}

instead of

/// postfix ... unpacks, is only valid where `T: Tuple`
impl<Head, Tail> Clone for (Head, Tail...)
where
    Head: Clone,
    Tail: Tuple,
    for<'a> Tail::AsRefs<'a>: TupleClone<Output=Tail>,
{
    fn clone(&self) -> Self {
        let (head, ...tail) = self.as_refs();
        (head.clone, tail.tuple_clone()...)
    }
}

pub trait TupleClone {
    type Output;
    fn tuple_clone(self) -> Self::Output;
}

impl TupleClone for () {
    type Output = Self;
    fn tuple_clone(self) -> Self::Output {
        ()
    }
}

impl<'a, Head, Tail> TupleClone for (&'a Head, Tail...)
where
    Head: Clone,
    Tail: Tuple + TupleClone,
{
    type Output = (Head, Tail::Output...);
    fn tuple_clone(self) -> Self::Clone {
        let (head, ...tail) = self;
        (head.clone(), tail.tuple_clone()...)
    }
}

There was some discussion at the all hands about a possible third option here where ... is purely syntactic, which means that you effectively do get tuple.map, but without the need for generic closures. The main restriction is that you can never reason about the type of the tail, only the type of each element individually. It hasn't been fully explored yet or had an RFC. In that version we'd write:

/// `...` *always* means "expand this for every element"
impl<Elems...> Clone for (Elems,...)
where
    Elems: Clone,...
{
    fn clone(&self) -> Self {
        let (ref elems...) = *self;
        (elems.clone(),...)
    }
}

[scottmcm]

I don't think it's obvious that it's worth making (u8, u32, u8) bigger than the equivalent tuple-struct to allow tail-borrowing. I'd hate for people to start recommending using Tuple(u8, u32, u8) instead "because it's faster". I'm a big fan of the "third option" here.

[comex]

(elems.clone(),...)

In my experience with C++, those "pack expansions" are annoyingly limiting / non-general:

• What if you don't want commas in between the expanded elements? C++ gained fold expressions that allow some other operators in between, but that creates even more complexity, and see later about inconsistency with the rest of the language.
• What if you only want some of the elements?
• What if you want to iterate multiple tuples together? E.g. what does this mean?

  let (ref a...) = a_s;
  let (ref b...) = b_s;
  ((a, b)...)

  In C++, the equivalent syntax works like .zip() (the two tuples must be the same length, and each element of a is paired with one corresponding element of b). But what if you want it to work like .flat_map() (generates all possible pairs of elements)? How do you distinguish the two? In C++, the latter is just impossible to express without a completely different approach, yet that's annoyingly non-general.

Pack expansions in C++ also feel inconsistent with the rest of the language: they're intuitively a kind of iteration, but they look completely different from any of the kinds of iteration you can do at runtime. In my opinion, this outweighs the positives of what's admittedly a neat-looking syntax.

For these reasons, for Rust, I'd personally much prefer an approach based on things like tuple.map, even if it requires generic closures – a feature that has plenty of other use cases anyway.

[strega-nil]

I'm fairly certain any tuple layout that allows tail references would be really inconvenient, and bad. It would require a recursive layout that ends up not only making things like (u8, u32, u8) far larger than necessary, but also things like (u8, u8,u32) larger than necessary (adding 3 bytes of unnecessary padding).

I also don't think your point stands up to practice, @comex - the expansion syntax in C++ is simply pattern matching on lists, with some syntax sugar sprinkled on top, which I don't think is unreasonable. I personally prefer to have parameter packs with the list interface, rather than the iterable interface.

[comex]

I agree that tail references are a bad idea. I think a good solution would be to have magic as_refs, plus generic closures so you could write things like

elems.as_refs().map(|e| e.clone())

I don't know what you mean by "list interface".

---

At the risk of stating the obvious, an important point about the C++ syntax is that parameter packs and tuples have to be two different things. For this to work:

        (elems.clone(),...)

the compiler needs to know that inside the expression elems.clone(), elems is the part that needs to be iterated on, and the rest is to be repeated. Well, in that example there's nothing else that would make sense to iterate, but presumably this would also work, as it does in C++:

        (elems + x,...)

where elems is a pack and x is a regular variable that gets repeated. Thus, you couldn't just use the syntax for any tuple-typed variable; you always have to introduce a pack.

In C++, this is a big limitation because there is no way to go from a tuple to a parameter pack "in place", as opposed to calling something else which then pattern matches to get a parameter pack. In the proposed Rust syntax, there is such a way – for expressions:

        let (ref elems...) = *self;

(Incidentally, there's a proposal to allow similar syntax in C++ to introduce parameter packs.)

Still, there might be cases where you start with a tuple-typed variable, then need to write a second name for a parameter-pack version:

    let my_tuple = get_a_tuple();
    do_something_with(&my_tuple);
    let (my_tuple_pack...) = my_tuple;

In that example, my_tuple and my_tuple_pack refer to essentially the same object, but one is a tuple and one is a pack. IMO that's unnecessarily complicated – it feels very C++-ish, in a bad way.

More importantly, what about types? Presumably the expansion syntax would also work on tuple types, so you could write

struct X<T>;
struct Foo<(Ts...)> {
    xs: (X<Ts>...)
}

But if you have a type 'expression' (say, <A as Trait>::B) which you know is a tuple, and you want to turn that into a parameter pack in place, how would you do that? If you can't, that would be a pretty annoying limitation.

Admittedly, the alternative might be that instead of only being able to use expansion syntax sometimes, you'd never be able to use it. We don't have type lambdas, so there can't be a convenient type version of map. But the inconsistency would still be maddening.

---

By the way, another issue with the syntax is when the intended replacement doesn't contain the variable being iterated on. If you want to replace every element of an unknown-sized tuple with 0, so, e.g., you'd go from (a, b, c, d, e) to (0, 0, 0, 0, 0), how would you express that? You could write something like

   let (elems...) = expr;
   let zeroes = ({&elems; 0}...);

but that's super ugly.

With map, it's trivial:

   let zeroes = elems.map(|_| 0);

[gnzlbg]

For these reasons, for Rust, I'd personally much prefer an approach based on things like tuple.map, even if it requires generic closures – a feature that has plenty of other use cases anyway.

I tend to agree.

On one hand, pack expansion in C++ is a nice primitive because it easily allows implementing std::tuple, type lists, as well as algorithms for those ( map, fold, zip, head, tail, etc.) in the language (is this what you meant by list interface @ubsan ?).

On the other hand, pack expansion has a significant compile-time cost in C++ and people do actually prefer a good list API in practice (e.g. range-v3 tuple_algorithm.hpp). A lot of effort has been invested into making these "list APIs" fast, from compiler intrinsics like the one exposed by std::make_integer_sequence, to full-fledge benchmarking frameworks http://metaben.ch/type/clang++-4.0/fold_left/index.html .

Rust has tuples in the language, and these can be used to implement type-list and similar types (e.g. type-indexed hash tables, etc.). If we can come up with a list API that solves all use cases of pack expansion / fold-expression, while having good compile-times, we probably should do that independently of whether we decide to pursue pack expansion as well or not. A good list API might make pack expansion not worth pursuing, but it isn't an either list API or pack expansion, we could (for better or worse) add both.

---

Also I wouldn't focus on fold-expressions too much. They are a nice ergonomic improvement, but they are not required per-se. Everything that they allow can be emulated with a bit of boiler plate on top of pack expansion, e.g., with pack-expansion one can implement an heterogeneous fold, and a + ... + 0 is just a.fold(0, |a, b| a + b) (assuming the closure is generic, which is something that we want to do anyways).

[hanna-kruppe]

Let's not rehash that whole discussion here, please. Thank you @cramertj and @sgrif for explaining why the tail-reference approach is not obviously completely superseded by another approach.

With that in mind and considering that there's nothing actually specified about struct layout yet that would spill over on tuples, I think we should decouple tuple layout from struct layout to resolve this concern for now. Hopefully we'll get around to nailing down the more contentious parts of struct layout at some point, and when we do that we can also revisit tuple layout, hopefully informed by progress made in the area of variadic generics since then.

[cramertj]

don't think it's obvious that it's worth making (u8, u32, u8) bigger than the equivalent tuple-struct to allow tail-borrowing.

Yes, I agree that it's not obvious. I don't think any direction here is obvious. I'm pointing out that there's a decision here to be made and two options are in conflict, so we should hold off on guaranteeing something in order to avoid forcing our hand elsewhere.

Is anyone blocked by not knowing whether tuples and tuple structs have the same representation? I'm having a hard time imagining a usecase for this, so it seems like an obvious choice to leave this unspecified for now until we've had a (separate!) discussion on how variadics should work.

[crlf0710]

@cramertj Really looking forward to the discussion because concerns about variadic generics has been blocking the stablization of fn_traits for years. Really wish minimal decision could be made to at least unblock the stablization of fn_traits.

[eddyb]

@crlf0710 That's not even that tied to this, IMO. There's no reason we can't allow you writing this:

impl FnOnce(A, B) for Foo {
    type Output = X;
    fn call_once(self, a: A, b: B) -> X {...}
}

Without even changing the definition of the traits in libcore.
There is some bikeshedding to be had wrt FnOnce(...) and type Output = X; vs FnOnce(...) -> X, but other than that, all we need is to expand FnOnce::<(A, B)>::call_once's signature to that of a regular Rust function with 3 arguments, Self, A and B.

I started cleaning up the implementation in this area but got side-tracked. Not sure if it would be easier to mentor someone, or finish it up myself, but I'd be happy to discuss this further (although here it's offtopic).

[crlf0710]

@eddyb could you say more in rust-lang/rust #29625, especially commenting on nagisa's comment rust-lang/rust#29625 (comment) which is written in year 2016? I don't think the situation has changed fundamentally in this 3 yrs, but i'd really really wish it would move forward.