Compile-time set operations for tuples

I would like to check at compile time if a tuple is a subset of another wrt to their types.

For example:

is_subset::<((A,B), (A,B,C))>(); // compile to no-op
is_subset::<((A,B), (A,C))>(); // should not compile

In C++ this could be done with variadic templates. How can I achieve this in Rust?

AFAIK this is not possible, at least not without writing tons of macro boilerplate. What are you trying to achieve?

Might be impossible, depending on the precise constraints of what is to be achieved. Sometimes allowing for type inference to deduce extra information can help with such things; and some nighty features, particularly marker traits and/or specialization, might help.

It’s also not clear what you want to use this check for. You probably want to do something that relies on the is_subset property in order to work, but then the problem of pulling off implementing that thing might be the main challenge, at least as hard, possibly (but not necessarily) harder to pull off using trait implementation and/or macro trickery than the original is_subset implementation in the first place.

A good minimal example of what kind of operation one needs to find a way to implement in order to also make is_subset work: It need to at least be possible to create an operation like

is_one_of<A, B, C>(); // fails
is_one_of<A, A, B>(); // compiles
is_one_of<A, B, A>(); // compiles

that checks whether the first argument is one of the other two types. I also believe that this kind of thing might be one of the main hurdles, as it has a specialization-like quality to it.

I want to split access to a database-like structure which holds elements of many different types such that the left view can only access certain selected types (check is_subset) and the right view can access the complement types (check is_disjoint). A bit similar to slice::split_mut but with types instead of indices. I have some machinery to do those checks at runtime, but was wondering if it is also possible at compile-time to avoid the runtime overhead.

The is_one_of already exists (at leasts for a set of traits) in static_assertions::assert_impl_one - Rust

This sounds like you are confusing a tuple projection (of fields/elements) with types. Or is it guaranteed that every field of such a tuple is going to be a different type? What should happen if it's not the case?

My database does guarantee that internally and I can do those checks at runtime with the help of Type::of::<A> and the corresponding set operations.

For example at the moment it looks like this as very rough pseudo code:

struct Db {...};
db.push(43i32); // store some i32
db.push(2.4f32); // store some f32
fn split<A>(db: &Db) -> (DbView, DbView) {...}
struct DbView { allow: TypeSet, disallow: TypeSet, db: *mut Db }
let (left, right) = db.split::<i32>(); // left can only access i32
                                       // right can access everything else
left.get::<i32>(); // OK
left.get::<f32>(); // panic!
right.get::<i32>(); // panic!
right.get::<f32>(); // OK

And I am wondering if something like this is possible:

fn split<A>(db: &Db) -> (DbView<A, ()>, DbView<(), A>) {...}
struct DbView<ALLOW, DISALLOW> { db: *mut Db }
let (left, right) = db.split::<i32>();
left.get::<i32>(); // OK
left.get::<f32>(); // ERR does not compile
right.get::<i32>(); // ERR does not compile
right.get::<f32>(); // OK

The general idea being that DbView can hand out &mut and I can guarantee that there are no &mut pointing to the same item.

This looks interesting but I am not sure how that could be changed to a is_one_of with exact type check instead of "trait implementation".

I think at the very least it needs to be possible to have is_equal::<A,B>(). I found a post which says this is possible "with specialization", but not sure what that means. I also found the lhlist crate which seems to use a technique for a similar problem, but that requires to "pre-declare" all types so that some macro can create some annotations for those types.

This sounds very similar to what the specs crate did for implementors of their System trait.

The general premise is that you've got an ECS and want a way to access the storage for different components with different levels of mutability and pass all the different component storages in as a tuple. For example, the physics system might accept a (Mut<Position>, Ref<Velocity>), which is the equivalent of accepting (&mut Position, &Velocity) but for operating on bulk data. The Mut and Ref wrappers would guarantee shared/exclusive access for all entities with those components.

Here's some very cursed macro + const monomorphization hackery that implements this Rust Playground

Note that this needs to do a bunch of sketchy things:

  • it requires the const_type_id feature, which has a bunch of problems and might even be unsound
  • it does a transmute of TypeId to u128 just to compare them. It might not be needed when TypeId will get back its const PartialEq implementation (currently removed along will all the other const impls due to some implementation flaws)

This is just for demonstration purposes of what could be possible in the future. Please don't use this in production.

As far as I can tell from the source code specs (and also legion and bevy) are doing these access checks at runtime. Which make sense the way systems are scheduled as "dynamic" functions. I am wondering if it is also possible to do them at compile time.

"const type id" looks very interesting, although it is unfortunately not ready for production.

May I ask why you transmute TypeId to an u128 although the source shows that is uses u64?

I'm using nightly and it has recently been changed to use a u128

The above could perhaps be fixed if the compiler gains a way to be consistent about type equality.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.