Problem

At EuroRust 2023 Nathanial Lattimer presented a talk about "Rust, but Verify - Compile-Time Authorization". This talk demonstrated how to use type states to address common authorization problems. As part of the solution the talk introduced a type level list of already checked authorizations, which later can be used to allow accessing certain functions.

The talk used the following construct for a type level list:

use std::marker::PhantomData;

struct TList<T, C> {
    element: PhantomData<T>,
    tail: C,
}

which is essentially a classic HList, with the minor difference that it doesn't store any data. A list of elements can then be represented as:

struct FeatureA;
struct FeatureB;

let my_list: TList<FeatureA, TList<FeatureB, ()>> = TList {
    element: PhantomData::<FeatureA>,
    tail: TList {
        element: PhantomData::<FeatureB>,
        tail: () // We use `()` to signal the end of the list
    },
};

To use this construct for authorization, we need to check, at compile time, whether or not a certain type is contained in the type level list. The presenter uses the following trait setup for that:

trait Has<T> {};

fn must_have_feature_b<T: Has<FeatureB>>(t: T) {
    // some implementation that requires a user
    // that is allowed to use `FeatureB`
}

This requires to have two implementations of Has<T> for TList:

• One for the case that the T parameter of the TList struct matches T, i.e. the current element is T
• One for the case that the C parameter of the TList struct implements Has<T>, i.e. the tail of the list contains T

This would leave us with the following trait implementations:

impl<T, C> Has<T> for TList<T, C> {} // `T` is the current element
impl<T, C, O> Has<T> for TList<O, C> 
where C: Has<T> // The tail contains `T`
{} 

Now these implementations have a problem: They are considered overlapping by the rust compiler. The compiler is correct about that, as there could be a case where our list contains a certain feature twice. For the presented use-case of authorization this does not really matter, as we only care whether or not something is contained, not how often something is contained. The presenter chose the unstable #[marker_trait] feature to workaround this problem.

Solution

It's possible to implement a solution to this problem using stable Rust. We can use associated types in combination with some helper types and a helper trait to construct non-overlapping implementations here.

The problem part about the presented setup is that it requires two distinct trait implementations. Overall we are just interested in knowing whether or not a certain type is contained in our list. We can combine our two existing implementations by saying: It should implement the trait if the current element is the T or any of the tail elements is T. To express this in a single implementation we need to restructure our trait setup slightly:

• Instead of only implementing our marker trait when the list contains a certain element, we always implement the trait
• We use an associated type to signal whether or not the element is contained. This requires two additional types Yes and No.
• We combine the associated type with the tail of the list with the result of the current comparison. This requires an additional trait implemented for all combinations of Yes and No.

The new trait definition looks like this:

trait Has<T> {
    type HasIt;
}

where the associated type HasIt represents whether or not an element T is contained in our list. We then use the following two types as associated types to signal that:

/// The element is in the list
struct Yes;
/// The element is not in the list
struct No;

Now we introduce an additional trait, which allows us to combine two instances of these two types. This essentially represents a type level "or" operation. This results in the following code:

/// Represents the combination of two result types
trait Combine<T> {
    type R;
}

/// Explicitly list all 4 possible combinations
impl Combine<Yes> for Yes {
    type R = Yes;
}
impl Combine<Yes> for No {
    type R = Yes;
}
impl Combine<No> for Yes {
    type R = Yes;
}
impl Combine<No> for No {
    type R = No;
}

Now we need to provide implementations of our Has<T> trait for all relevant types which are used as type argument to TList. This are the types FeatureA, FeatureB, () in our example.

impl Has<FeatureA> for FeatureA {
    type HasIt = Yes;
}

impl Has<FeatureA> for FeatureB {
    type HasIt = No;
}

impl Has<FeatureA> for () {
    type HasIt = No;
}

Now we can write a single implementation for our TList type, which basically just uses the existing Has<T> implementations on all type parameters and combines the result via the Combine trait:

impl<T, C, S> Has<S> for TList<T, C>
where
    C: Has<S>,
    T: Has<S>,
    T::HasIt: Combine<C::HasIt>,
{
    type HasIt = <<T as Has<S>>::HasIt as Combine<<C as Has<S>>::HasIt>>::R;
}

Let's use our example type TList<FeatureA, TList<FeatureB, ()>> and see how that implementation would work for searching for FeatureB:

1. For the outer TList type we use T = FeatureA, C = TList<FeatureB, ()> and S = FeatureB
2. Evaluating the first where bound TList<FeatureB, ()>: Has<FeatureB> requires to check the implementation of the inner TList type:
   1. For the inner TList type we use T = FeatureB, C = () and S = FeatureB.
   2. Evaluating the first where bound (): Has<FeatureB> results in a Has<FeatureB, HasIt = No> implementation
   3. Evaluating the second where bound FeatureB: Has<FeatureB> results in a Has<FeatureB, HasIt = Yes> implementation
   4. The third trait bound ensures that we can combine these two results
   5. Evaluating the associated type means that we evaluate <<FeatureB as Has<FeatureB>>::HasIt as Combine<<C as Has<FeatureB>>::HasIt>>::R. This can be done by replacing both Has<FeatureB> instances with the results from step 2.2 and 2.3: <Yes as Combine<No>>>:R, which in turn evaluates to Yes according to our lookup setup presented earlier.
3. Evaluating the second where bound FeatureA: Has<FeatureB> results in a Has<FeatureB, HasIt = No> implementation
4. The third trait bound ensures that we can combine the results from step 2 and 3.
5. Evaluating the associated type on the outer trait impl means that we evaluate <<FeatureA as Has<FeatureB>>::HasIt as Combine<<TList<FeatureB, ()> as Has<FeatureB>>::HasIt>>::R. By using the results from step 3 and 2.5 we get the following simplified expression: <No as Combine<Yes>>::R, which in turn evaluates to Yes.

Finally we need to adjust the places where we actually perform the checks whether the list contains a certain type to check the associated type instead:

fn must_have_feature_b<T: Has<FeatureB, HasIt = Yes>>(t: T) {
    // some implementation that requires a user
    // that is allowed to use `FeatureB`
}

If you want to play around with the presented solution, try out the following Playground

A generalized version of this pattern is used by diesel to ensure GROUP BY clauses and SELECT clauses are compatible.

You can support my work by sponsoring me on Github