Non-exponential Type Safety Pattern Help

help
1

heya, is there a non-exponential, maintainer-friendly way to achieve compile-time safety for this meta-programming problem:

Problem / Scenario

  1. There is a Container of data.
  2. As certain data is inserted into this container, the container should be marked as containing that data.
  3. The Container can be passed to other methods, where the methods have constraints on what data is inside that container.
  4. The method may mutate the Container to add additional data, and in the process, adding / subtracting those data markings.

The methods that would take in the container may have different constraints such as:

fn use_1_add_2(c: Container /* with DataOne */)
    -> Container /* with DataOne and DataTwo */ { /* .. */ }

fn use_1_add_3(c: Container /* with DataOne */)
    -> Container /* with DataOne and DataThree */ { /* .. */ }

fn use_1_2_add_4(c: Container /* with DataOne and DataTwo */)
    -> Container /* DataOne and DataTwo and DataFour */ { /* .. */ }

and it should be completely fine to pass in a container with 1, 2, 3 to use_1_2_add_4, and get a container with 1, 2, 3, 4 out.

Options So Far

The solutions that I know how to do, but are exponential are:

Option 1: Type State per Data

Summary

This can be achieved via a type-state parameter per data, e.g.

struct Container<DataOneMaybe, DataTwoMaybe, /* .. */> {
    data_one: DataOneMaybe,
    data_two: DataTwoMaybe,
    /* .. */
}

impl<DataTwoMaybe> for Container<DataOneSome, DataTwoMaybe> {
    pub fn data_one(&self) -> &DataOne { &self.data_one.0 }
}
impl<DataOneMaybe> for Container<DataOneMaybe, DataTwoSome> {
    pub fn data_two(&self) -> &DataTwo { &self.data_two.0 }
}

where the type state contains:

// DataOneMaybe
struct DataOneNone;
struct DataOneSome(DataOne);
struct DataOneSomeProcessed(DataOneProcessed);

// ditto for DataTwo and so on

Then at compile time we can go:

fn do_work(
    c: Container<DataOneSome, DataTwoSome>
) -> Container<DataOneSomeProcessed, DataTwoSome> {
    // can access c.data_one() and c.data_two()
}

Pros

  • Compile time safe.
  • Code completion shows available methods.

Cons

  • Exponential number of implementations.
  • Type hints in IDE are really long: Container<DataOneSome, DataTwoSome, ReallyLongTypeParameters, MoreLikeThis>.
  • Tedious when there are about 5 data types.
  • Really difficult to maintain.

Notes

  • I've tried doing this with build.rs -- strings are painful, no syntax highlighting.

  • I've also implemented this with a proc macro (better -- but still painful).

    This implementation was exploratory, so the code is highly linear + copy pasted

Option 2: Trait per Data and Combination

Summary

Essentially one type state parameter, with traits attached to the type argument:

struct WithDataOne;
trait WithDataOneT {}
impl WithDataOneT for WithDataOne { /* .. */ }

struct WithDataTwo;
trait WithDataTwoT {}
impl WithDataTwoT for WithDataTwo { /* .. */ }

struct WithDataOneAndTwo;
trait WithDataTwoT: WithDataOneT + WithDataTwoT {}
impl WithDataOneT for WithDataOneAndTwo { /* .. */ }
impl WithDataTwoT for WithDataOneAndTwo { /* .. */ }
impl WithDataOneAndTwoT for WithDataOneAndTwo { /* .. */ }

// trait methods to mutate a Container<One: WithDataOneT, Two> into a Container<WithDataOneAndTwoT>

I didn't go down this track too far -- the number of traits and methods is exponential to the number of data types, and I wasn't sure it was worth the effort.

Option 3: Alter Rust

A bit too meta for me :melting_face:, but perhaps it's not within this generation of language to encode such constraints with less syntax.

Are there other options or better ways to achieve this?
Perhaps this level of compile-time safety is too obsessive.

Thank you

2

I think if you have four possibly contained values and you want type safety, then it's inevitable that there are 16 different types. Otherwise you can't distinguish all cases.

I would likely use type parameters (your Option 1) to solve the problem if I want compile time safety.

Maybe there's a way to provide the implementation in some clever way to reduce impact of monomorphization. But perhaps that's already done automatically (see Polymorphization)?

3 Likes