Generics programming using soa-derive

[Alexandre425]

Hi, apologies for not being able to infer this from the documentation and code, I am not very experienced with these topics. Also, sorry if I get any terms wrong, either way, my question is the following:

Say I have a generic struct that is meant to include various types of SoAs. What trait bounds am I meant to use? Should T be a Cheese or a CheeseVec?

pub struct SparseSet<T: ?> {
    dense: Vec<EntID>,
    sparse: Vec<u32>,
    data: ?,
}

From my understanding of the documentation, you are meant to apply the trait bound StructOfArray, making T a CheeseVec. However, that trait does not implement the usual methods (insert, pop, etc.), which would mean I can't do generic implementations. Is that the case, or did I miss something?

If T is a SoA, how do I get the original type, for declaring function parameter types? For example, the function get makes use of the sparse array to determine if an entity exists, after which it's meant to return the associated data, in this case a Cheese. What should ? be here, i.e. how do I get Cheese from CheeseVec in a generic way?

/// Gets the data associated with the entity from the set
pub fn get(&self, ent_id: EntID) -> Result<&?, Error> {
    self.ent_exists(ent_id)
        .then(|| &self.data[self.sparse[ent_id] as usize])
        .ok_or(Error::EntityNotInSet)
}

Thank you.

[Alexandre425]

I made some progress in realizing the type refers to the derived CheeseVec, and so my implementation now looks like this:

pub struct SparseSet<T: StructOfArray> {
    dense: Vec<EntID>,
    sparse: Vec<u32>,
    data: <T as StructOfArray>::Type,
}

However, this still will not allow me to have generic implementations, as the following errors:

pub fn new() -> Self {
    Self {
        dense: Vec::new(),
        sparse: Vec::new(),
        data: <T as StructOfArray>::Type::new(),
    }
}

error[E0599]: no function or associated item named new found for associated type <T as StructOfArray>::Type in the current scope

Do I have any alternatives? Any trait that implements the methods I need, so that I can have generic implementations?

[Luthaf]

Hey! I never used this code in a generic context, so I'm not sure if there is a workaround for the lack of associated methods.

StructOfArray::Type was added by @mikialex who wanted to do something similar in #24/#25. Maybe they have more idea about how to achieve this?

[Alexandre425]

I see, I did find that PR, that commit was what helped me figure out part of it. If @mikialex can let me know if they've ever done generic implementations using their contribution, that would be really helpful. Otherwise I suppose I will look for an alternative, macros perhaps.

[mobiusklein]

I took a stab at this, but I ran into issues with lifetimes on associated types.

pub trait SoAVec<'a, T: StructOfArray>: 'a {
    type Ref<'t> where 'a: 't;

    fn get<'t>(&'t self, index: usize) -> Option<Self::Ref<'t>> where 'a: 't;

    fn index<'t>(&'t self, index: usize) -> Self::Ref<'t> where 'a: 't
    ...
}

impl<'a> SoAVec<'a, Particle> for ParticleVec {
    type Ref<'t> = ParticleRef<'t> where 'a: 't;

    fn get<'t>(&'t self, index: usize) -> Option<Self::Ref<'t>> where 'a: 't {
        self.get(index)
    }

    fn index<'t>(&'t self, index: usize) -> Self::Ref<'t> where 'a: 't {
        self.index(index)
    }
   ...
}

This looks like it works just fine until I try to use it in a mutable context, due to reborrowing, I think.

This compiles:

fn example<'a, V: StructOfArray, T: SoAVec<'a, V>>(vec: &'a T) -> Option<T::Ref<'a>> where T::Ref<'a>: PartialOrd {
    let mut indices: Vec<_> = (0..vec.len()).collect();
    indices.sort_by(|j, k| {
        let a = vec.index(*j);
        let b = vec.index(*k);
        a.partial_cmp(&b).unwrap()
    });
    let i = indices.iter().position(|x| *x == 0).unwrap();
    vec.get(i)
}

This does not:

fn example<'a, V: StructOfArray, T: SoAVec<'a, V>>(vec: &'a mut T) -> Option<T::Ref<'a>> where T::Ref<'a>: PartialOrd {
    let mut indices: Vec<_> = (0..vec.len()).collect();
    indices.sort_by(|j, k| {
        let a = vec.index(*j); // Error here: argument requires that `vec` is borrowed for `'a`, `vec` does not live long enough
        let b = vec.index(*k);
        a.partial_cmp(&b).unwrap()
    });
    let i = indices.iter().position(|x| *x == 0).unwrap();
    vec.get(i)
}

If I use the real type though, everything is fine! Even when I use the trait method instead of the direct implementation:

fn iter_max_concrete<'a>(vec: &'a mut ParticleVec) -> Option<<ParticleVec as SoAVec<'a, Particle>>::Ref<'a>> {
    let mut indices: Vec<_> = (0..vec.len()).collect();
    indices.sort_by(|j, k| {
        let a = <ParticleVec as SoAVec<'a, Particle>>::index(&vec, *j);
        let b = <ParticleVec as SoAVec<'a, Particle>>::index(&vec, *k);
        a.partial_cmp(&b).unwrap()
    });
    let i = indices.iter().position(|x| *x == 0).unwrap();
    vec.get(i)
}

It's as though the compiler somehow relaxes the lifetime constraints given by the concrete implementation of index given by <usize as SoAIndex>, and then propagates that through all calls to it, but that relaxed constraint is not visible syntactically. Am I missing something tricky about how SoAIndex is implemented?

[Luthaf]

So it seems that the issue is actually in the PartialOrd bound: changing it from T::Ref<'a>: PartialOrd to where for <'t> T::Ref<'t>: PartialOrd makes the code compile. Intuitively, you need T::Ref to be PartialOrd for any lifetime, including the one of the closure, and not just for the 'a lifetime.

As a separate point, I'm not sure I understand why you wrote the trait with a lifetime parameter, instead of using GAT?

// current
pub trait SoAVec<'a, T: StructOfArray>: 'a {
    type Ref<'t> where 'a: 't;
    fn get<'t>(&'t self, index: usize) -> Option<Self::Ref<'t>> where 'a: 't;
}

// GAT
pub trait SoAVec<T: StructOfArray> {
    type Ref<'a> where Self: 'a;
    fn get(&'_ self, index: usize) -> Option<Self::Ref<'_>> {
}

[mobiusklein]

Thank you for demonstrating for<'t> , I hadn't seen that syntax used in practice, and reminding me that I didn't need to express a lifetime bound w.r.t. another lifetime, but a type in the context of an associated type.

I had put a lifetime on SoAVec in order to "satisfy" the compiler that there was a lifetime available to constrain another GAT with a lifetime bound.

The top level trait I had written, slightly modified after adding your suggested changes.

pub trait SoATypes: StructOfArray + Sized {
    type Ref<'t> where Self: 't;
    type RefMut<'t> where Self: 't;

    type Ptr;
    type PtrMut;

    type Iter<'t>: Iterator<Item=Self::Ref<'t>> where Self: 't;
    type Slice<'t>: SoASlice<
        't,
        Self,
        Ref<'t> = Self::Ref<'t>,
        Iter<'t> = Self::Iter<'t>,
        Ptr = Self::Ptr,
    > where Self: 't;

    type SliceMut<'t>: SoASliceMut<
        't,
        Self,
        Ref<'t> = Self::Ref<'t>,
        Iter<'t> = Self::Iter<'t>,
        RefMut<'t> = Self::RefMut<'t>,
        IterMut<'t> = Self::IterMut<'t>,
        Ptr = Self::Ptr,
        PtrMut = Self::PtrMut,
    > where Self: 't;
    type IterMut<'t>: Iterator<Item=Self::RefMut<'t>> where Self: 't;

    type Vec<'t>: SoAVec<
        Self,
        Ref<'t> = Self::Ref<'t>,
        RefMut<'t> = Self::RefMut<'t>,
        Ptr = Self::Ptr,
        PtrMut = Self::PtrMut,
        Slice<'t> = Self::Slice<'t>
    > where Self: 't;
}

I initially didn't put a lifetime on the SoAVec trait since it "owns" its data, but I needed to be able to specify a lifetime on its Ref GAT in order to express that it is the same type as SoATypes::Ref across all types in the system. I don't see another way around it right now.

The for<'t> mechanism fixes the ownership lifetime issue for SoAVec, although I'm still puzzled about why. I'll try to experiment more.

I might be better off decoupling the types such that there isn't one unifying trait and abandon the idea that all Ref of the same StructOfArray type's presentations are the same type, for expediency.