Working with various lengths of 'array-like' tuple structs

I've come to realize that if I want to accomplish grouping of semi-homogenous items in a space-efficient, stack-allocated, 'array-like', yet fixed-layout form (i.e. not [Box<dyn CommonTraits>; N] or [EnumWithCommonTraits; N]), one solution is to write custom tuple structs for each anticipated number of items:

pub struct ThreeItems<T1, T2, T3> (T1, T2, T3)
where
    T1: CommonTraits,
    T2: CommonTraits,
    T3: CommonTraits;

For which it's straightforward to implement the things I'd like to see a collection do such as iterators or indexing. I was especially happy to find that Iterator<Item = &'a dyn mut CommonTraits> works, giving the magic of dyn Trait without requiring a Box, woohoo!

But I just don't want to deal with the whole copy/paste/rename/add process any more than I have to, especially since I've got a few use cases for this concept... so macros! The biggest problem (I think) comes in incrementing the generic types T1/T2/T3/T4/etc. as I'm pretty sure I've run across the issue of being unable to concatenate 'T' with an int to create a valid token within a macro before. Though calling make_tuple_struct!(SixItems; T1, T2, T3, T4, T5, T6) etc. would still be a heck of a lot better.

Does anyone have any thoughts or good references where something similar may have already been done? Also, I worry there may come issues with trying to actually generate and use a container for N known items at runtime. But I'm hopeful that the number and series of types it contains can be hidden behind an impl ContainerTrait, or else only create/use/drop the struct within the context of a single run function scope so the cluster of generics never needs to be seen.

The thing that's really nagging at me with this is that any permutation of T1/T2/.../T42 has a fixed number of items, max alignment, and (taking into account alignments) a total required size. A tuple struct with generics lets the compiler work out all the details, but with evaluatable const generics it seems this may be possible in a more generic sense.

There is an alternate solution, which doesn't won't work very well for most of my use cases, using const generics to make arrays for all possible types that implement some CommonTraits:

pub struct DenseGroup<const N1: usize, const N2: usize> {
    type1s: [Struct1; N1],
    type2s: [Struct2; N2],
    // for all possible structs that implement the desired common traits.
}

This would end up way too complex for several of my cases, particularly where each struct has its own generics which strongly change its size, for which I'd have to make separate arrays for every combination of generics for every struct, yikes!

When you run into the identifier concatenation problem, the solution it to use the crate β€œpaste”.

3 Likes

The next problem with their approach is it's not possible to generate a stream of unique identifiers. That means you end up writing something like this monstrosity and only be able to work with a finite number of elements:

impl_foo!();
impl_foo!(A);
impl_foo!(A, B);
impl_foo!(A, B, C);
impl_foo!(A, B, C, D);

I've seen crates do fancy things using cons lists to store a homogeneous list of items.

A good example of this is the tuple_list crate where they map tuples like (A, B, C, D) to (A, (B, (C, (D, ())))). The example in their crate docs looks quite similar to your CommonTraits problem.

Example Code
trait PlusOne {
    fn plus_one(&mut self);
}

impl PlusOne for i32    { fn plus_one(&mut self) { *self += 1; } }
impl PlusOne for bool   { fn plus_one(&mut self) { *self = !*self; } }
impl PlusOne for String { fn plus_one(&mut self) { self.push('1'); } }
 
// Now we have to implement trait for an empty tuple,
// thus defining initial condition.
impl PlusOne for () {
    fn plus_one(&mut self) {}
}
 
// Now we can implement trait for a non-empty tuple list,
// thus defining recursion and supporting tuple lists of arbitrary length.
impl<Head, Tail> PlusOne for (Head, Tail) where
    Head: PlusOne,
    Tail: PlusOne + TupleList,
{
    fn plus_one(&mut self) {
        self.0.plus_one();
        self.1.plus_one();
    }
}

// `tuple_list!` as a helper macro used to create
// tuple lists from a list of arguments.
use tuple_list::tuple_list;
 
// Now we can use our trait on tuple lists.
let mut tuple_list = tuple_list!(2, false, String::from("abc"));
tuple_list.plus_one();
 
// tuple_list! macro also allows us to unpack tuple lists
let tuple_list!(a, b, c) = tuple_list;
assert_eq!(a, 3);
assert_eq!(b, true);
assert_eq!(&c, "abc1");
1 Like

Ahh thank you! The tuple_list crate has some great ideas! Pushing the FP concepts of head/tail into the generics seems to do some rather nice things for usability. Though anything that saves having to write out twelve structs, twelve impls, twelve iterator wrapper structs, and twelve impl Iterators is a win!

Though I assume if I wanted to implement indexing on a tuple list it would have to work out such that a_tuple_list[5] would invoke a recursive call to the tails or otherwise loop to result in calling a_tuple_list.1?.1?.1?.1?.0 (or could also prepend a length check for early return of None).

You'll probably want to use a macro (e.g. get!(my_list[5])) which does all that for you. It's impossible to implement the Index trait for a homogeneous collection because it requires the return type to be the same regardless of the index. (okay, you could hack around this with Any and downcasting, but that's gonna be ugly)

I could also see a case for some sort of ConstIndex trait in the future that lets you do something like this.

trait ConstIndex<const Index: usize> {
    type Output;

    fn get(&self) -> &Self::Output;
}

impl<A> ConstIndex<0> for (A,) { ... }
impl<A, B> ConstIndex<0> for (A, B) { ... }
impl<A, B> ConstIndex<1> for (A, B) { ... }
impl<A, B, C> ConstIndex<0> for (A, B, C) { ... }
impl<A, B, C> ConstIndex<1> for (A, B, C) { ... }
impl<A, B, C> ConstIndex<2> for (A, B, C) { ... }

let items = (2, false, String::from("abc")); // Note: Not using tuple_list

let first: &i32 = items.get::<0>();
let last: &String = items.get::<2>();
let index_out_of_bounds = items.get::<42>(); // Compile Error

I imagine an equivalent for tuple_list would be implemented recursively, but would compile to &foo.1.1.1.1.0 once inlining kicks in because the type and index are known at compile time.

That's handled by returning &dyn CommonTraits / &dyn mut CommonTraitsMut. I lost the playground link I had for testing it, but I had a three element tuple struct successfully iterating over arbitrary combinations of fixed concrete types [f64; N] (for various sizes N), for each of which I had implemented some arbitrary operations (sum, product, whatever). The structs this will hold are far larger than is nice for Copy, but all the values I want access to are floats or fixed arrays of floats, so should work nicely having lots of immutable references.

Though now I'm realizing I should do a much more thorough check of mutable iteration and the problem of splitting field borrows... Can it successfully return &mut self.0 from the outermost pair and afterwards also step into the tail and repeat the process, or would the second borrow attempt see field 1 as already borrowed mutably? The end goal will be to be able to set up parallel mutable iteration, so I probably need to keep an eye toward being able to divide and conquer, as well.

I wrote a few traits for iterating over tuples because of this thread. Perhaps you’re interested in taking a look. A use-case with trait-objects looks as follows, but the framework can (probably) easily be used to support a heterogeneous set of types implementing Borrow<T> or AsRef<T> and/or their mutable counterparts.

// EXAMPLE APPLICATION

use std::fmt;

trait SomeTrait: fmt::Debug {}
fn main() {
    let mut x = (A, B);

    for v in x.iter::<dyn SomeTrait>() {
        // v: &dyn SomeTrait
        dbg!(v);
    }

    for v in x.iter_mut::<dyn SomeTrait>() {
        // v: &mut dyn SomeTrait
        dbg!(v);
    }

    for v in x.into_iter::<dyn SomeTrait>() {
        // v: Box<dyn SomeTrait>
        dbg!(v);
    }
}

#[derive(Debug)]
struct A;
#[derive(Debug)]
struct B;

impl SomeTrait for A {}
impl SomeTrait for B {}

impl TraitObject for dyn SomeTrait + '_ {}
impl<'t, S: SomeTrait + 't> Convert<S> for dyn SomeTrait + 't {
    fn convert_owned(x: S) -> Self::TargetOwned {
        Box::new(x)
    }

    fn convert_ref(x: &S) -> &Self::TargetRef {
        x
    }

    fn convert_mut(x: &mut S) -> &mut Self::TargetRef {
        x
    }
}

#[derive(Debug)]
struct A;
#[derive(Debug)]
struct B;

impl SomeTrait for A {}
impl SomeTrait for B {}

impl TraitObject for dyn SomeTrait + '_ {}
impl<'t, S: SomeTrait + 't> Convert<S> for dyn SomeTrait + 't {
    fn convert_owned(x: S) -> Self::TargetOwned {
        Box::new(x)
    }

    fn convert_ref(x: &S) -> &Self::TargetRef {
        x
    }

    fn convert_mut(x: &mut S) -> &mut Self::TargetRef {
        x
    }
}

(playground)

3 Likes

I also tried my hand at this:

struct A(usize);
struct B(usize);
struct C(usize);

impl AsRef<usize> for A { fn as_ref(&self)->&usize { &self.0 } }
impl AsRef<usize> for B { fn as_ref(&self)->&usize { &self.0 } }
impl AsRef<usize> for C { fn as_ref(&self)->&usize { &self.0 } }

impl AsMut<usize> for A { fn as_mut(&mut self)->&mut usize { &mut self.0 } }
impl AsMut<usize> for B { fn as_mut(&mut self)->&mut usize { &mut self.0 } }
impl AsMut<usize> for C { fn as_mut(&mut self)->&mut usize { &mut self.0 } }

impl Into<usize> for A { fn into(self)->usize { self.0 } }
impl Into<usize> for B { fn into(self)->usize { self.0 } }
impl Into<usize> for C { fn into(self)->usize { self.0 } }

fn main() {
    let mut x = (A(3), B(5), C(7));
    for i in IntoIterAs::<&usize>::into_iter_as(&x) {
        dbg!(i);
    }


    for i in IntoIterAs::<&mut usize>::into_iter_as(&mut x) {
        *i *= 2;
        dbg!(i);
    }
    
    
    for i in IntoIterAs::<usize>::into_iter_as(x) {
        dbg!(i);
    }

}

Playground

1 Like

Damn, there is so much good stuff here!! Thanks to everyone for the input!

Also, this is a very interesting region for understanding compile vs. runtime checks. In theory ANY tuple could iterate and index for ANYTHING it might contain - you would just need a runtime pre-filter for iterating or to add an additional type check for accessing an index, and wrong uses would just produce a lot of immediate None values. The real question is the most usable or efficient way to encode those in the type system checks, for which I now have a lot of good sources for options on the macro and interface fronts.

This will definitely take me a while to process, but this gives me plenty of ideas to work with, thanks again!

Actually, both of these setups have brought up interesting questions on relations between traits...

@2e71828 yours sets up IntoIterAs, IterAs, and IterAsMut traits, but then your actual uses are only via IntoIterAs with the ref/mut appearing to follow solely from the chosen type. Does the type given to IntoIterAs actually work through to use the other traits, or is some other magic handling that? At some point you stop implementing anything beyond IntoIterAs; is that truly all that's needed?

And @steffahn you give a single access point of Convert<S>: ConversionTargets with minimal generic types and without explicitly requiring ConvertRef/ConvertShared/ConvertMut. It appears the crossover is handled by implementing the whole lot for T, allowing Convert<S> to use all the sub-traits but without having to bring all sub-trait-generics into that top level trait. Am I interpreting the relationship between all the pieces correctly?

There are blanket implementations for IterAs and IterAsMut that delegate to the IntoIterAs implementation on references. I used IntoIterAs in the examples because the compiler couldn't figure out the type I was trying to iterate over. This also works, and would perhaps have been a better example:

fn main() {
    let mut x = (A(3), B(5), C(7));
    for i in x.iter_as() {
        let i: &usize = i;
        dbg!(i);
    }

    for i in x.iter_as_mut() {
        let i: &mut usize = i;
        *i *= 2;
        dbg!(i);
    }
    
    
    for i in x.into_iter_as() {
        let i: usize = i;
        dbg!(i);
    }
}
1 Like

Ahh, that explains why I was also able to get (&x).into_iter_as() and (&mut x).into_iter_as() to work, but not x.into_iter_as() until a type was given which could be inferred from. Nifty!

Oh, and .iter_as()/.iter_as_mut() both remain accessible and operate on a plain x, very nice!

I'm getting closer on the direct indexing side (playground), but I just don't really like that as a solution. I think that for indexing it might be better to just enable appropriately constructed tuples to give [&dyn Trait; N]. I won't need mutable access by index as I think iter/filter/map is preferable. Also, macros to make match arms for tuple structs seem like more of a pain than they're worth. Though, going to an array of references doesn't solve the macro issue of having to get self.0, self.1, etc. (playground)

Also, the even more direct attempt to implement std::ops::Index has issues with an unconstrained type parameter (playground)