How to read some of the types like join on Vec

I have being doing rustling exercises and specifically one about iterators where I end up with a following solution:

    #[test]
    fn test_iterate_into_string() {
        let words = vec!["hello", " ", "world"];
        let capitalized_words = words
            .iter()
            .map(|&word| capitalize_first(&word))
            .collect::<Vec<String>>()
            .join("");
        assert_eq!(capitalized_words, "Hello World");
    }

However as I was reading API docs for join made me wondering how to read type signature

pub fn join<Separator>(
    &self,
    sep: Separator
) -> <[T] as Join<Separator>>::Output where
    [T]: Join<Separator>, 

I'm unable to understand what the Output type supposed to be nor following trait documentation for std::slice::join seems to explain much.

Can anyone please help me understand how to read this and to come to conclusion that Output is String ?

Thanks

Look at the docs of Join.

This page documents three impls:

impl<S: Borrow<str>> Join<&str> for [S] {
    type Output = String;
    ...
}

impl<T: Clone, V: Borrow<[T]>> Join<&T> for [V] {
    type Output = Vec<T>;
    ...
}

impl<T: Clone, V: Borrow<[T]>> Join<&[T]> for [V] {
    type Output = Vec<T>;
    ...
}

The first one tells us that you can call .join("string") on a slice of anything that implements Borrow<str>, such as &str or String. The output is a String.

// <[&str] as Join<&str>>::Output = String
assert_eq!(
    vec!["hello", "world"].join(" "),
    "hello world".to_string(),
);
    
// <[String] as Join<&str>>::Output = String
assert_eq!(
    vec!["hello".to_string(), "world".to_string()].join(" "),
    "hello world".to_string(),
);

The second one tells us that you can call .join(&x) on a slice of anything that implements Borrow<[T]> (such as Vec<T> or &[T]), producing a Vec<T>.

// <[Vec<i32>] as Join<&i32>>::Output = Vec<i32>
assert_eq!(
    vec![vec![1], vec![2, 3], vec![4]].join(&999),
    vec![1, 999, 2, 3, 999, 4],
);
    
// <[&[i32]] as Join<&i32>>::Output = Vec<i32>
assert_eq!(
    vec![&[1][..], &[2, 3][..], &[4][..]].join(&999),
    vec![1, 999, 2, 3, 999, 4],
);

The third one tells us you can also call .join(&[x, y, z][..]) on those same types, also producing a Vec<T>.

// <[Vec<i32>] as Join<&[i32]>>::Output = Vec<i32>
assert_eq!(
    vec![vec![1], vec![2, 3], vec![4]].join(&[9, 9][..]),
    vec![1, 9, 9, 2, 3, 9, 9, 4],
);

// <[&[i32]] as Join<&[i32]>>::Output = Vec<i32>
assert_eq!(
    vec![&[1][..], &[2, 3][..], &[4][..]].join(&[9, 9][..]),
    vec![1, 9, 9, 2, 3, 9, 9, 4],
);

Aside: I'm actually surprised that rust is smart enough to see that the first two impls don't overlap. Usually it's pretty conservative with its overlap analysis...

2 Likes

Since there are many elided types involved here, let's step through the type deduction that leads us to precisely this impl.

  1. We are interested in the output type. This is an associated type involving one known trait, Join, and two yet unknown types: T and Separator.
  2. The type for T is also involved in the type of self. This can be seen as the called method is [T]::join. The slice type of self is [String]. So we can already unify T == String.
  3. In the method signature we find that parameter sep also has type Separator. In the invocation we provide a string literal as argument. String literals have the type &'static str so that we can unify Separator == &'static str.
  4. Finally we must resolve [String] as Join<&'static str>, that is find the trait impl for the type [String]. In the documentation of the Join trait we find this fitting impl. Since there must be only one applicable impl, we can confidently say that this is the one we have searched for.
    impl<'_, S> Join<&'_ str> for [S]
    where
        S: Borrow<str>,
    {
        type Output = String;
    }
    
  5. We have found our Output type, which is String.
3 Likes

The first impl has &'static str, the second is &'_ T where T: Clone. These could only overlap if str could overlap with T but the str type is not Clone (it could never be since it is a DST). The same argument for why the second and third impl do not overlap where [U] can also never be Clone.

Well, normally there would be an error like (I couldn't think of a non-primitive standard library type that is a DST to replace str with so I tried the somewhat nonsensical std::num::Wrapping<[i32]>):

error[E0119]: conflicting implementations of trait `Join<&std::num::Wrapping<[i32]>>` for type `[_]`:
  --> src/lib.rs:17:1
   |
9  | impl<T: Clone, V: Borrow<[T]>> Join<&T> for [V] {
   | ----------------------------------------------- first implementation here
...
17 | impl<S: Borrow<std::num::Wrapping<[i32]>>> Join<&std::num::Wrapping<[i32]>> for [S] {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `[_]`
   |
   = note: upstream crates may add a new impl of trait `std::clone::Clone` for type `std::num::Wrapping<[i32]>` in future versions

error: aborting due to previous error

I suspect the only reason it doesn't do this for str is because str is a primitive.


Edit: Oh duh, there is OsStr. However, if I try using that in place of str, then it does compile, so being a primitive type has nothing to do with it...

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