# A non-overlapping type level contains operation for heterogeneous lists

# 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`

:

- For the outer
`TList`

type we use`T = FeatureA`

,`C = TList<FeatureB, ()>`

and`S = FeatureB`

- Evaluating the first where bound
`TList<FeatureB, ()>: Has<FeatureB>`

requires to check the implementation of the inner`TList`

type:- For the inner
`TList`

type we use`T = FeatureB`

,`C = ()`

and`S = FeatureB`

. - Evaluating the first where bound
`(): Has<FeatureB>`

results in a`Has<FeatureB, HasIt = No>`

implementation - Evaluating the second where bound
`FeatureB: Has<FeatureB>`

results in a`Has<FeatureB, HasIt = Yes>`

implementation - The third trait bound ensures that we can combine these two results
- 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.

- For the inner
- Evaluating the second where bound
`FeatureA: Has<FeatureB>`

results in a`Has<FeatureB, HasIt = No>`

implementation - The third trait bound ensures that we can combine the results from step 2 and 3.
- 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