What is the most idiomatic/best way to abstract over many optional and independent capabilities of types via traits?

help
1

Hi there!

I recently asked this question on StackOverflow but haven't gotten any answer so far. Since this is something that can be discussed about (and SO is no place for this discussion), I thought asking here too would be a good idea! I'm really interested in your opinions on that, because I'm really not sure. Here is the full question copied:

I want to abstract over a variety of different list data structures. My abstraction should be fairly flexible. I want a "base trait" (let's call it List) that represents the minimal interface required from all data structures. But there are optional capabilities the data structures could offer, which are independent from each other:

  • Some data structures allow mutation, while others only provide a read-only interface. This is something which is fairly common for Rust traits: the pair Trait and TraitMut (e.g. Index and IndexMut).
  • Some data structures provide a capability "foo".
  • Some data structures provide a capability "bar".

Initially, this seems easy: provide the traits List, ListMut, FooList and BarList where the latter three have List as super trait. Like this:

trait List {
    fn num_elements(&self) -> usize;
}

trait ListMut: List {
    fn clear(&mut self);
}

trait FooList: List {
    fn num_foos(&self) -> usize;
}

trait BarList: List {
    fn num_bars(&self) -> usize;
}

This works fine for the methods above. But the important part is that there are methods that require multiple capabilities. For example:

  • add_foo(&mut self): requires the mutability and the capability "foo"!
  • add_foo_and_bar(&mut self): requires mutability and the capabilities "foo" and "bar".
  • ... and more: imagine there is a function for each combination of requirements.

Where should the methods with multiple requirements live?

One Trait per Combination of Capabilities

One way would be to additionally create a trait for each combination of optional requirements:

  • FooListMut
  • BarListMut
  • FooBarList
  • FooBarListMut

These traits would have appropriate super trait bounds and could house the methods with multiple requirements. There are two problems with this:

  • The number of traits would grow exponentially with the number of optional capabilities. Yes, there would only need to be as many traits as methods, but it can still lead to a very chaotic API with loads of traits where most traits only contain one/a small number of methods.
  • There is no way (I think) to force types that implement ListMut and FooList to also implement FooListMut. Thus, functions would probably need to add more bounds. This trait system would give implementors flexibility I might not want to give them.

where Self bounds on methods

One could also add where Self: Trait bounds to methods. For example:

trait FooList: List {
    // ...

    fn add_foo(&mut self) 
    where 
        Self: ListMut;
}

This also works, but has two important disadvantages:

  • Implementors of FooList that don't implement ListMut would need to dummy implement add_foo (usually with unreachable!()) because the Rust compiler still requires it.
  • It is not clear where to put the methods. add_foo could also live inside ListMut with the bound being where Self: FooList. This makes the trait API more confusing.

Define Capabilities via associated types/consts

In this solution, there would only be one trait. (Note that in the following code, dummy types are used. Ideally, this would be an associated const instead of type, but we cannot use consts in trait bounds yet, so dummy types it is.)

trait Bool {}
enum True {}
enum False {}
impl Bool for True {}
impl Bool for False {}


trait List {
    type SupportsMut: Bool;
    type SupportsFoo: Bool;
    type SupportsBar: Bool;
    
    fn add_foo(&mut self) 
    where 
        Self: List<SupportsMut = True, SupportsBar = True>;

    // ...
}

This solves two problems: for one, we know that if Mut and Foo are supported, that we can use add_foo (in contrast to the first solution, where a data structure could implement ListMut and FooList but not FooListMut). Also, since all methods live in one trait, there it's not unclear anymore where a method should live.

But:

  • Implementors still might need to add a bunch of unreachable!() implementations as by the last solution.
  • It is more noisy to bound for certain capabilities. One could add trait ListMut: List<SupportsMut = True> (the same for foo and bar) as trait alias (with blanket impl) to make this a bit better, though.

Something else?

The three solutions so far are what I can think of. One could combine them somehow, of course. Or maybe there is a completely different solution even?

Are there clear advantages of one solution over the other solutions? Have they important semantic differences? Is one of these considered more idiomatic by the community? Have there been previous discussions about this? Which one should be preferred?

2

The issue with what you want is that there does not seem to be a default implementation for your add_foo-like methods.

In that case, there needs to be:

  • either a trait expressing whether such methods have been implemented (your One Trait per Combination of Capabilities), since

    (or even less if a combination of traits had multiple associated methods)

  • or implicitly delegating it to runtime with your aforementioned unreachable!s.

Imagine the following situation: someone has some type X : Foo, and after a refactoring, they realise they can also have X : ListMut, because they want to have access to both Foo and ListMut methods, but add_foo may not be really needed for their usecase.

  • with the unreachable!() road, they can just "forget" to implement it and everything is fine, until it turns out they may actually need add_foo and the program can now panic!.

  • with the "added trait" road, they can happily use their structure, until it turns out they may actually need add_foo, and the program will not compile that part of the code until they implement that behavior.

  • with the road you seem to be suggesting (requiring a RFC), you would need something along the lines of

    trait ListMut + Foo {
    fn add_foo (self: &'_ mut Self);
}

    And now the problem is that you would not be allowing the programmer to have X : ListMut + Foo unless they implemented add_foo, making the situation too restrictive.

Conclusion

When default methods (with Self : bounds) are not possible, using extra traits is the way to go, since it best expresses the optional nature of the additional behavior.

3

Thanks for your input!

Reading your text, I noticed that the main problem really seems to be whether methods like add_foo should be considered additional behavior or behavior that is implicitly part of "offering "foo" and Mut". You make a point that it's probably best to see it as additional behavior that should live in its own trait.

Again, I'm not sure if what you describe is "too restrictive". Maybe it's what I want.

I guess that this underlying question of whether add_foo is additional or a part of Foo + Mut cannot be answered for such a dummy example, but might be different for each actual real world use case. For this purpose, I have another example, which is still simplified but matches the semantics of my real code a lot better:

Not so dummy example

Again, we have a List base trait and the capability Mut. Thinking about doubly linked vs singly linked lists, let's have a second capability called Backwards, which means that the list can be traversed backwards. To refer to elements in the list, say we have this opaque type Handle (often also called cursor) which can be set by the list implementation (this would be a wrapper around a pointer to one list node). This all in code:

trait List {
    type Value;
    type Handle;
    fn first_element(&self) -> Option<Self::Handle>;
    fn next_element(&self, h: Self::Handle) -> Option<Self::Handle>;
    fn value_of(&self, h: Self::Handle) -> &Self::Value;
}

We also have the following methods, which are shown here with the "One trait per combination of capabilities" solution:

trait ListMut: List {
    fn insert_after(&mut self, h: Self::Handle, value: Self::Value);
}

trait BackwardsList: List {
    fn previous_element(&self, h: Self::Handle) -> Option<Self::Handle>;
}

trait BackwardsListMut: ListMut + BackwardsList {
    fn insert_before(&mut self, h: Self::Handle, value: Self::Value);
}

Let's ask the question again: should insert_before be in a separate trait because we think of it as additional capability? Or is it more natural to require insert_before to be implemented if BackwardsList and ListMut are also implemented?

In this particular example, I would say the latter: from a users perspective, there is no reason not to be able to call insert_before if you already know that ListMut and BackwardsList are implemented. It seems like a necessary consequence to me. What do you think?

4

Make that it's own trait, that way if someone makes a type that conditionally implements ListMut and BackwardsList they can conditionally implement BackwardsListMut correctly.

For example if someo e was making a generic wrapper type for Lists and wanted to forward the implementations of these traits.

Another thing you could do is

trait ListMut: List {
    fn insert_after(&mut self, h: Self::Handle, value: Self::Value);
}

trait BackwardsList: List {
    fn previous_element(&self, h: Self::Handle) -> Option<Self::Handle>;

    fn insert_before(&mut self, h: Self::Handle, value: Self::Value)
    where Self: ListMut;
}

But this doesn't provide a nice way to implement wrapper types, so I would try and avoid it.

5

Why does the latter solution does not provide a nice way to implement wrapper types?

struct Wrapper<L>(L);

impl<L: List> List for Wrapper<L> { ... }
impl<L: ListMut> ListMut for Wrapper<L> { ... }

impl<L: BackwardsList> BackwardsList for Wrapper<L> {
    fn previous_element(&self, h: Self::Handle) -> Option<Self::Handle> {
        self.0.previous_element(h)
    }

    fn insert_before(&mut self, h: Self::Handle, value: Self::Value)
    where 
        Self: ListMut,
    {
        self.0.insert_before(h, value)
    }
}

This works, right? Or am I missing any disadvantage?

And just to be clear, in my previous post (where I explained the new example), I showed the "one trait per capability combination" solution. The solution "where Self bounds" was shown by @RustyYato here (alternatively, the method insert_before could live in ListMut with a where Self: BackwardsList bound). The last solution I see, is to define the capability "Backwards" via a associated type:

trait List {
    // See the first post for the definition of `Bool`, `True` and `False`
    type SupportsBackwards: Bool;  

    // As before:
    type Value;
    type Handle;
    fn first_element(&self) -> Option<Self::Handle>;
    fn next_element(&self, h: Self::Handle) -> Option<Self::Handle>;
    fn value_of(&self, h: Self::Handle) -> &Self::Value;

    // This is new: 
    fn previous_element(&self, h: Self::Handle) -> Option<Self::Handle>
    where 
        Self: List<SupportsBackwards = True>;
}

trait ListMut: List {
    // As before:
    fn insert_after(&mut self, h: Self::Handle, value: Self::Value);

    // This is new:
    fn insert_before(&mut self, h: Self::Handle, value: Self::Value)
    where 
        Self: List<SupportsBackwards = True>;
}

This reduces the number of traits to 2. It also makes it impossible to not implement insert_before if the type also implements insert_after and previous_element. Which, as I said, is what one wants in this case, I think.

6

If you have more complicated wrappers which conditionally implements ListBackwards then things can get a bit complicated unless you have separate traits. That said, I may just be overthinking it.

Also Instead of using an associated type, you could use a trait

trait Backwards: List {}

trait List { fn prev() where Self: Backwards; }

trait ListMut { fn prev_mut() where Self: Backwards; }

This plays better with the Rust type system. (Rust gets confused by Self: List inside of ListMut sometimes) This also makes it easier to implement List.

7

I'd be very interested in an example! I just can't imagine the problem you are thinking about right now, I think.

That's a possibility I didn't consider so far. Interesting! Thanks for that, I might try this in my real code base.

I'm still interested in hearing more peoples' opinions on the matter btw :slight_smile:

8

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.