How to implement a trait for &str and &[&str]

Rust has a pretty powerful type system, but some things are not that easy to express. Follow me on a journey where we try to implement a bit of method overloading by using traits with funny constraints and discover some interesting ways to convince Rust that everything is fine.

tl;dr “Man this is some type system abuse if I I’ve ever seen it. I absolutely love it! It’ll be useful to know this if I ever need it.” (/u/mgattozzi on Reddit)

Note: This post assumes a general understanding of Rust. There will also be some hairy type signatures – don’t be afraid of those! Just skip the parts you don’t understand.

So, let’s get started! Our goal is this: We want to have a function that can take both string slices as well a slice of string slices:

foo("Hello World");
foo(&["Hello", "World"]);

The actual use case is that the string slice can internally be split into subslices – or the user can do it themselves (to make sure it’s correct, or to do it programmatically).

We do this by implementing a new trait¹ ToFoo for both types, so our foo function can take any argument that implements ToFoo and use it to convert it to something it can use:

trait ToFoo {
    fn to_foo(&self) -> Vec<String>;
}

First try

Sounds easy enough, right? Let’s write it down (playpen):

trait ToFoo<'a> {
    fn to_foo(&'a self) -> Vec<String>;
}

impl<'a> ToFoo<'a> for &'a str {
    fn to_foo(&'a self) -> Vec<String> { unimplemented!() }
}

impl<'a, 'b> ToFoo<'a> for &'a [&'b str] {
    fn to_foo(&'a self) -> Vec<String> { unimplemented!() }
}

fn main() {
    println!("{:?}", "yay".to_foo());
    println!("{:?}", (&["yay"]).to_foo());
}

Sorry about the whole 'a noise²! Please ignore this for a minute!

But wait – this doesn’t compile!

no method named `to_foo` found for type `&[&'static str; 1]` in the current scope

Sadly, we implemented our trait on a slice (that &[_] thing), but gave it a &[_; 1]. The difference? &[_; 1] is a reference to an array with a known size. We have two options:

1. Use &["foo"][..] to create a slice with an open range, i.e., all elements.
2. Implement ToFoo for this array type.

The first option is perfectly valid if it is you who writes writes that foo(&["bar"][..]), but what I am aiming for here is to present a nice API to the user of this theoretical library. And I don’t want to tell people to add some magic characters at the end of their argument if I don’t have to!

Sadly, as of Rust 1.16³ we would need to write implementations for all array types we want to support where the type also contains the length of the array! So, one for &[_; 1], another for &[_; 2], and so on. We could do that in a macro, but it’ll just generate a whole bunch of code and it not be very elegant.

Also, shouldn’t it be trivial to represent some &[_, n] as slice? And there are places where that works! Why not here? /u/dbaupp gave a great explanation for this on Reddit: It’s because we want to use a &self method on &[&str], which means we are dealing with a &&[&str]. And since we are starting with &[&str; 1], we can only rely on coercion for the reference, not the inner [&str; 1].

We could implement ToFoo on [&str] however, to leverage the fact that the reference in &["foo"] will trigger deref coercions, which means it finds our impl. Sadly, that does not work for functions or method that take a &T where T: ToFoo. So while we can do ["lorem"].to_foo(), we can’t do foo(&["lorem"]) or even ToFoo::to_foo(&["yay"]) – which is exactly what we want to use this for…

So, let’s try something else instead!

Second try

Rust has a pretty nice collection of conversion traits (see std::convert), and one of them is AsRef, which does “reference-to-reference conversion”. Basically, you give it an &x and it returns a &y of a compatible type to you:

pub trait AsRef<T> where T: ?Sized {
    fn as_ref(&self) -> &T;
}

Note that it is not ... for &T but ... for T and then has a method that takes &self. Okay, here’s a simplified new version (playpen):

trait ToFoo {}

impl<'a> ToFoo for &'a str {}
impl<'a, T> ToFoo for T where T: AsRef<[&'a str]> {}

Aaaand it does not compile:

error[E0119]: conflicting implementations of trait `ToFoo` for type `&str`:
 --> <anon>:4:1
  |
3 | impl<'a> ToFoo for &'a str {}
  | ----------------------------- first implementation here
4 | impl<'a, T> ToFoo for T where T: AsRef<[&'a str]> {}
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `&str`

What? “Conflicting implementation for &str”? Where? Ohhhhh… There’s this impl in std:

impl<'a, T, U> AsRef<U> for &'a T where
    T: AsRef<U> + ?Sized, U: ?Sized

So, Rust is clever enough to see that both &_ and &[_] match that AsRef implementation, but not clever enough differentiate the impl AsRefss to recognize that our second impl ToFoo should only ever work for &[_].

So, the & is the problem, right?

Third time’s the charm

First of all, let’s repeat our trait signature again, so you don’t have to scroll up:

trait ToFoo {
    fn to_foo(&self) -> Vec<String>;
}

Now, let’s implement our trait for str instead of &str. By the way: str is a type that we don’t know the size of – but let’s not get hung up on that now.

impl ToFoo for str {
    fn to_foo(&self) -> Vec<String> { unimplemented!() }
}

See, we’re only ever using &str anyway, as our method is taking &self. No need to worry.

Next: Implement the trait for each T where a reference to it implements AsRef<[&str]>:

impl<'a, T> ToFoo for T where T: AsRef<[&'a str]> {
    fn to_foo(&self) -> Vec<String> { unimplemented!() }
}

It took me quite a while to get to this point. Now, we can use it like this (playpen):

fn foo<'a, T: ToFoo + ?Sized>(_x: &'a T) {
    unimplemented!()
}

(The ?Sized is to allow the str impl.)

Nice!

Finally, you can find the real-life code that uses this pattern in this commit.