Using `impl Trait` for monomorphized heterogenous collections

language design
#1

I increasingly find myself using [&dyn Trait] slices for "lists" of heterogenous types.

As const generics continue to mature, lately I've been wondering if these same cases could be handled monomorphically by combining const generics with impl Trait.

Instead of the receiver of such an argument operating over a slice, it could be an array of const generic size, where the specific types used by the caller, index-by-index, are all known by the compiler, but the receiver sees only impl Trait for each member.

Is there already some exploration of this general idea in an existing document/issue I may have missed?

[Analysis / Pre-RFC] Variadic generics in Rust
#2

So effectively [impl Trait; N] would be a limited form of abstraction over tuple lengths.

i.e. you'd monomorphize for (A, B, C, D) (for whatever types, in whatever number) and work with it as-if it were a slice, with iteration that gets transformed into working on each type.

It can't work with just [impl Trait], as that already implies a singular type, but I could see this as a first-step into working with tuples generically. Even ignoring the particular syntax, all of the ways of interacting with slices only work for actual homogeneous slices, and so wouldn't work with a heterogeneous tuple.

1 Like
#3

Desugaring to a tuple is definitely a great model for it!

It can't work with just [impl Trait] , as that already implies a singular type

This has some interesting implications: [impl Trait; N] can therefore only implement a subset of the traits that are possible with [T; N]. For example, it can't impl AsRef<[impl Trait]>.

However, the main "array-like" thing I'd like out of [impl Trait; N] would be:

impl<'a, const N: usize> IntoIterator for &'a [impl Trait; N] {
  type Item = &'a impl Trait;
  ...
}

It seems like that sort of thing should be possible?

#4

It'd have to be an iterator over &dyn Trait if it's going to be a real iterator implementation.

You can say that a for loop over this type "desugars" as a bunch of monomorphized copies for each element rather than by using the iterator trait, which is mostly how heterogeneous tuple pack proposals go.

This can't in any way pretend to be a slice because it isn't, it needs completely different interaction to monomorphize rather than iterate a homogenous slice.

Syntax something like pack: impl... Trait could work if all you ever want to do with parameter packs is monomorphized-for-loop over them or forward them on, but I know people want to be forward-compatible with more.

Also, [impl Trait; N] already works for a singular type: Rust Playground

1 Like
#5

I could imagine something like (&T0, &T1) -> [&U; 2] where T0: CoerceUnsize<U>, T1: CoerceUnsize<U>, but I don't see how it could reasonably work from an array -- if I had an [impl Trait; N] I would be able to pass it to other things expecting a normal array of the same type, which it wouldn't be if it actually was different types under the hood.

2 Likes
#6

I'm not sure what you mean by "array of the same type". There's no explicit type parameter in the definition: just a trait, and a constant size bound.

Do you mean would an array of [T; N] where T impls Trait satisfy an [impl Trait; N] type definition / constraint? If so, my short answer is yes.

In terms of what would be syntactically allowed for an [impl Trait; N] literal, I'm mostly thinking of cases which are presently allowed under &[&dyn Trait], just with the dispatch handled ahead-of-time/monomorphized instead of being dispatched dynamically

I think it would also potentially unlock some scenarios along those lines which aren't presently possible, namely non-reference cases.

#7

I suppose I'm proposing some "magic" Iterator implementation only the compiler can provide which is only possible with a full map of the types known a priori and otherwise can't be written with Rust syntax today.

:+1:

Yeah exactly, this seems like a case which is possible to model with an Iterator, but not with a slice.

Or to put it another way, I think [impl Trait; N] is possible, but I don't think [impl Trait] is..

#8

It's confusing to use [impl Trait; N] as a syntax for a new thing, when it's already valid syntax:

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=aeb5359076ad067ef9f0f5641b2d0a8e

use std::fmt::Debug;

fn foo<const N: usize>(arr: [impl Debug; N]) -> [impl Debug; N] {
    println!("{:?}", arr);
    arr
}

fn main() {
    dbg!(&foo([0, 1, 2])[..]);
}

I turn the array into a slice in dbg!(&foo([0, 1, 2])[..]); to demonstrate that it would be a breaking change to repurpose this syntax for that.

8 Likes
#9

Didn't realize it's already valid, so good point

#10

Could this be solved with a auto trait and proc-macros? I'm not that familiar with Proc-Macros but if we had some auto trait like

trait Tuple {
    const size() -> usize;
    ...
}

We could write functions that take a variety of tuples with a syntax like this:

fn receiver<T>(tuple : T) where T : impl Tuple;

Then that function could use some sort of macro to iterate through the tuple.

tuple_for_match!(tuple, {
    impl Number(x) => ...,
    impl Debug(x) => ...,
})

I'm not familiar enough with proc-macros to know if this expansion in functionality is even possible though.

#11

see frunk for generic anonomous "tuples" and enums

4 Likes
#12

This is probably the confusion here -- I can already take or return [impl Trait; N], which has all the normal homogeneity requirements of a normal array, so I don't think it's reasonable to change that to sometimes do something very different.

I see this as two different parts:

  • Variadic generics, so one can write things like [T;N]::map for tuples.
  • Generic closures, so one can conveniently write the lambda that such a method would need.

That said, have you tried to see what happens with the via-dyn Trait versions when unrolled and inlined? I don't remember whether LLVM can devirtualize calls for us...

#13

Will take a look. That'd be exciting.

#14

Last I heard LLVM was "bad" at this but I might be wrong here. (I know a lot of clang's devirtualization happens in the frontend at any rate...)

#15

The following works in nightly:

fn foo (elems: &'_ List![impl Debug])
{
    elems.for_each(|elem| {
        dbg!(elem);
    });
}

fn main ()
{
    let _: List![i32, &str, bool] = list![42, "hi", true];
    foo(&list![42, "hi", true]);
    foo(&[27, 0]);
    foo(&vec![27, 0][..]);
}
5 Likes
#16

That's pretty clever with the tuple recursion. Did I accidentally type internals.lisp-lang.org into my browser this morning? :stuck_out_tongue:

I'm still a bit confused as to why it names things SomeDynTrait – it seems to me it avoids dynamic dispatch, after all?

2 Likes
#17

Well, it does prevent the dynamic dispatch at the foo function, but my definition of for_each still uses dynamic dispatch since there is no sugar for generic closures. But if using a custom trait instead of the Fn family, and maybe a macro to instantiate those, one could use:

trait GenericFnMut<DynTrait : ?Sized> {
    fn call_mut<Arg> (self: &'_ mut Self, arg: &'_ Arg)
    where
        Arg : Unsize<DynTrait>, // Poor man's genericity over traits.
    ;
}

instead of FnMut(&'_ DynTrait) (again, an implementor of this trait will end up relying on dyn dispatch to use the Unsize bound, but at that point it should be trivial for the optimizer to remove the dyn dispatch).

Or, if dealing with a fixed set of traits to handle (e.g., through helper macros):

trait GenericFnMutDebug {
    fn call_mut (self: &'_ mut Self, arg: &'_ impl Debug)
    ;
}
#18

See Representing closed trait objects as enums

#19

It's worth noting that one limitation of this proposal is that each slot of the "array" would be necessarily restricted to the type that was originally assigned to it. For instance, if you have

let x: [impl Debug; 3] = ["these", 3u16, false];

Then, since monomorphized, you wouldn't by able to do x[1] = true, since the layout of the whole would have to change to accommodate it.

2 Likes
#20

Possible layout was discussed in anonymous enums thread, but the discussion finished with enum impl Trait rather than simple impl Trait. However, I don't remember why.