Rollup merge of #62528 - SimonSapin:concat, r=alexcrichton

Add joining slices of slices with a slice separator, not just a single item

https://github.com/rust-lang/rust/issues/27747#issuecomment-294525391
> It's kinda annoying to be able to join strings with a str (which can have multiple chars), but joining a slice of slices, you can only join with a single element.

This turns out to be fixable, with some possible inference regressions.

# TL;DR

Related trait(s) are unstable and tracked at https://github.com/rust-lang/rust/issues/27747, but the `[T]::join` method that is being extended here is already stable.

Example use of the new insta-stable functionality:

```rust
let nested: Vec<Vec<Foo>> = /* … */;
let separator: &[Foo] = /* … */;  // Previously: could only be a single &Foo
nested.join(separator)
```

Complete API affected by this PR, after changes:

```rust
impl<T> [T] {
    pub fn concat<Item: ?Sized>(&self) -> <Self as Concat<Item>>::Output
        where Self: Concat<Item>
    {
        Concat::concat(self)
    }
    pub fn join<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
        where Self: Join<Separator>
    {
        Join::join(self, sep)
    }
}

// The `Item` parameter is only useful for the the slice-of-slices impl.
pub trait Concat<Item: ?Sized> {
    type Output;
    fn concat(slice: &Self) -> Self::Output;
}

pub trait Join<Separator> {
    type Output;
    fn join(slice: &Self, sep: Separator) -> Self::Output;
}

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

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

// New functionality here!
impl<T: Clone, V: Borrow<[T]>> Join<&'_ [T]> for [V] {
    type Output = Vec<T>;
}

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

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

# Details

After https://github.com/rust-lang/rust/pull/62403 but before this PR, the API is:

```rust
impl<T> [T] {
    pub fn concat<Separator: ?Sized>(&self) -> T::Output
        where T: SliceConcat<Separator>
    {
        SliceConcat::concat(self)
    }

    pub fn join<Separator: ?Sized>(&self, sep: &Separator) -> T::Output
        where T: SliceConcat<Separator>
    {
        SliceConcat::join(self, sep)
    }
}

pub trait SliceConcat<Separator: ?Sized>: Sized {
    type Output;
    fn concat(slice: &[Self]) -> Self::Output;
    fn join(slice: &[Self], sep: &Separator) -> Self::Output;
}

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

impl<S: Borrow<str>> SliceConcat<str> for S {
    type Output = String;
}
```

By adding a trait impl we should be able to accept a slice of `T` as the separator, as an alternative to a single `T` value.

In a `some_slice.join(some_separator)` call, trait resolution will pick an impl or the other based on the type of `some_separator`. In `some_slice.concat()` however there is no separator, so this call would become ambiguous. Some regression in type inference or trait resolution may be acceptable on principle, but requiring a turbofish for every single call to `concat` isn’t great.

The solution to that is splitting the `SliceConcat` trait into two `Concat` and `Join` traits, one for each eponymous method. Only `Join` would gain a new impl, so that `some_slice.concat()` would not become ambiguous.

Now, at the trait level the `Concat` trait does not need a `Separator` parameter anymore. However, simply removing it causes one of the impls not to be accepted anymore:

```rust
error[E0207]: the type parameter `T` is not constrained by the impl trait, self type, or predicates
  --> src/liballoc/slice.rs:608:6
    |
608 | impl<T: Clone, V: Borrow<[T]>> Concat for [V] {
    |      ^ unconstrained type parameter
```

This makes sense: if `[V]::concat` is a method that is itself not generic, then its return type (which is the `Concat::Output` associated type) needs to be determined based on solely `V`. And although there is no such type in the standard library, there is nothing stopping another crate from defining a `V` type that implements both `Borrow<[Foo]>` and `Borrow<[Bar]>`. It might not be a good idea, but it’s possible. Both would apply here, and there would be no way to determine `T`.

This could be a warning sign that this API is too generic. Perhaps we’d be better off having one less type variable, and only implement `Concat for [&'_ [T]]` and `Concat for [Vec<T>]` etc. However this aspect of `[V]::concat` is already stable, so we’re stuck with it.

The solution is to keep a dummy type parameter on the `Concat` trait. That way, if a type has multiple `Borrow<[_]>` impls, it’ll end up with multiple corresponding `Concat<_>` impls.

In `impl<S: Borrow<str>> Concat<str> for [S]`, the second occurrence of `str` is not meaningful. It could be any type. As long as there is only once such type with an applicable impl, trait resolution will be appeased without demanding turbofishes.

# Joining strings with `char`

For symmetry I also tried adding this impl (because why not):

```rust
impl<S: Borrow<str>> Join<char> for [S] {
    type Output = String;
}
```

This immediately caused an inference regression in a dependency of rustc:

```rust
error[E0277]: the trait bound `std::string::String: std::borrow::Borrow<[std::string::String]>` is not satisfied
   --> /home/simon/.cargo/registry/src/github.com-1ecc6299db9ec823/getopts-0.2.19/src/lib.rs:595:37
    |
595 |             row.push_str(&desc_rows.join(&desc_sep));
    |                                     ^^^^ the trait `std::borrow::Borrow<[std::string::String]>` is not implemented for `std::string::String`
    |
    = help: the following implementations were found:
              <std::string::String as std::borrow::Borrow<str>>
    = note: required because of the requirements on the impl of `std::slice::Join<&std::string::String>` for `[std::string::String]`
```

In the context of this code, two facts are known:

* `desc_rows` is a `Vec<String>`
* `desc_sep` is a `String`

Previously the first fact alone reduces the resolution of `join` to only one solution, where its argument it expected to be `&str`. Then, `&String` is coerced to `&str`.

With the new `Join` impl, the first fact leavs two applicable impls where the separator can be either `&str` or `char`. But `&String` is neither of these things. It appears that possible coercions are not accounted for, in the search for a solution in trait resolution.

I have not included this new impl in this PR. It’s still possible to add later, but the `getopts` breakage does not need to block the rest of the PR. And the functionality easy for end-user to duplicate: `slice_of_strings.join(&*char_separator.encode_utf8(&mut [0_u8, 4]))`

The `&*` part of that last code snippet is another case of the same issue: `encode_utf8` returns `&mut str` which can be coerced to `&str`, but isn’t when trait resolution is ambiguous.

2 files changed, 96 insertions, 29 deletions

diff --git a/src/liballoc/slice.rs b/src/liballoc/slice.rs
index bc4ae167984..881d499c074 100644
--- a/src/liballoc/slice.rs
+++ b/src/liballoc/slice.rs
@@ -494,10 +494,10 @@ impl<T> [T] {
     /// assert_eq!([[1, 2], [3, 4]].concat(), [1, 2, 3, 4]);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn concat<Separator: ?Sized>(&self) -> T::Output
-        where T: SliceConcat<Separator>
+    pub fn concat<Item: ?Sized>(&self) -> <Self as Concat<Item>>::Output
+        where Self: Concat<Item>
     {
-        SliceConcat::concat(self)
+        Concat::concat(self)
     }
 
     /// Flattens a slice of `T` into a single value `Self::Output`, placing a
@@ -508,12 +508,13 @@ impl<T> [T] {
     /// ```
     /// assert_eq!(["hello", "world"].join(" "), "hello world");
     /// assert_eq!([[1, 2], [3, 4]].join(&0), [1, 2, 0, 3, 4]);
+    /// assert_eq!([[1, 2], [3, 4]].join(&[0, 0][..]), [1, 2, 0, 0, 3, 4]);
     /// ```
     #[stable(feature = "rename_connect_to_join", since = "1.3.0")]
-    pub fn join<Separator: ?Sized>(&self, sep: &Separator) -> T::Output
-        where T: SliceConcat<Separator>
+    pub fn join<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
+        where Self: Join<Separator>
     {
-        SliceConcat::join(self, sep)
+        Join::join(self, sep)
     }
 
     /// Flattens a slice of `T` into a single value `Self::Output`, placing a
@@ -528,10 +529,10 @@ impl<T> [T] {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     #[rustc_deprecated(since = "1.3.0", reason = "renamed to join")]
-    pub fn connect<Separator: ?Sized>(&self, sep: &Separator) -> T::Output
-        where T: SliceConcat<Separator>
+    pub fn connect<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
+        where Self: Join<Separator>
     {
-        SliceConcat::join(self, sep)
+        Join::join(self, sep)
     }
 
 }
@@ -578,30 +579,63 @@ impl [u8] {
 // Extension traits for slices over specific kinds of data
 ////////////////////////////////////////////////////////////////////////////////
 
-/// Helper trait for [`[T]::concat`](../../std/primitive.slice.html#method.concat)
-/// and [`[T]::join`](../../std/primitive.slice.html#method.join)
+/// Helper trait for [`[T]::concat`](../../std/primitive.slice.html#method.concat).
+///
+/// Note: the `Item` type parameter is not used in this trait,
+/// but it allows impls to be more generic.
+/// Without it, we get this error:
+///
+/// ```error
+/// error[E0207]: the type parameter `T` is not constrained by the impl trait, self type, or predica
+///    --> src/liballoc/slice.rs:608:6
+///     |
+/// 608 | impl<T: Clone, V: Borrow<[T]>> Concat for [V] {
+///     |      ^ unconstrained type parameter
+/// ```
+///
+/// This is because there could exist `V` types with multiple `Borrow<[_]>` impls,
+/// such that multiple `T` types would apply:
+///
+/// ```
+/// # #[allow(dead_code)]
+/// pub struct Foo(Vec<u32>, Vec<String>);
+///
+/// impl std::borrow::Borrow<[u32]> for Foo {
+///     fn borrow(&self) -> &[u32] { &self.0 }
+/// }
+///
+/// impl std::borrow::Borrow<[String]> for Foo {
+///     fn borrow(&self) -> &[String] { &self.1 }
+/// }
+/// ```
 #[unstable(feature = "slice_concat_trait", issue = "27747")]
-pub trait SliceConcat<Separator: ?Sized>: Sized {
+pub trait Concat<Item: ?Sized> {
     #[unstable(feature = "slice_concat_trait", issue = "27747")]
     /// The resulting type after concatenation
     type Output;
 
     /// Implementation of [`[T]::concat`](../../std/primitive.slice.html#method.concat)
     #[unstable(feature = "slice_concat_trait", issue = "27747")]
-    fn concat(slice: &[Self]) -> Self::Output;
+    fn concat(slice: &Self) -> Self::Output;
+}
+
+/// Helper trait for [`[T]::join`](../../std/primitive.slice.html#method.join)
+#[unstable(feature = "slice_concat_trait", issue = "27747")]
+pub trait Join<Separator> {
+    #[unstable(feature = "slice_concat_trait", issue = "27747")]
+    /// The resulting type after concatenation
+    type Output;
 
     /// Implementation of [`[T]::join`](../../std/primitive.slice.html#method.join)
     #[unstable(feature = "slice_concat_trait", issue = "27747")]
-    fn join(slice: &[Self], sep: &Separator) -> Self::Output;
+    fn join(slice: &Self, sep: Separator) -> Self::Output;
 }
 
-#[unstable(feature = "slice_concat_ext",
-           reason = "trait should not have to exist",
-           issue = "27747")]
-impl<T: Clone, V: Borrow<[T]>> SliceConcat<T> for V {
+#[unstable(feature = "slice_concat_ext", issue = "27747")]
+impl<T: Clone, V: Borrow<[T]>> Concat<T> for [V] {
     type Output = Vec<T>;
 
-    fn concat(slice: &[Self]) -> Vec<T> {
+    fn concat(slice: &Self) -> Vec<T> {
         let size = slice.iter().map(|slice| slice.borrow().len()).sum();
         let mut result = Vec::with_capacity(size);
         for v in slice {
@@ -609,14 +643,19 @@ impl<T: Clone, V: Borrow<[T]>> SliceConcat<T> for V {
         }
         result
     }
+}
+
+#[unstable(feature = "slice_concat_ext", issue = "27747")]
+impl<T: Clone, V: Borrow<[T]>> Join<&T> for [V] {
+    type Output = Vec<T>;
 
-    fn join(slice: &[Self], sep: &T) -> Vec<T> {
+    fn join(slice: &Self, sep: &T) -> Vec<T> {
         let mut iter = slice.iter();
         let first = match iter.next() {
             Some(first) => first,
             None => return vec![],
         };
-        let size = slice.iter().map(|slice| slice.borrow().len()).sum::<usize>() + slice.len() - 1;
+        let size = slice.iter().map(|v| v.borrow().len()).sum::<usize>() + slice.len() - 1;
         let mut result = Vec::with_capacity(size);
         result.extend_from_slice(first.borrow());
 
@@ -628,6 +667,29 @@ impl<T: Clone, V: Borrow<[T]>> SliceConcat<T> for V {
     }
 }
 
+#[unstable(feature = "slice_concat_ext", issue = "27747")]
+impl<T: Clone, V: Borrow<[T]>> Join<&[T]> for [V] {
+    type Output = Vec<T>;
+
+    fn join(slice: &Self, sep: &[T]) -> Vec<T> {
+        let mut iter = slice.iter();
+        let first = match iter.next() {
+            Some(first) => first,
+            None => return vec![],
+        };
+        let size = slice.iter().map(|v| v.borrow().len()).sum::<usize>() +
+            sep.len() * (slice.len() - 1);
+        let mut result = Vec::with_capacity(size);
+        result.extend_from_slice(first.borrow());
+
+        for v in iter {
+            result.extend_from_slice(sep);
+            result.extend_from_slice(v.borrow())
+        }
+        result
+    }
+}
+
 ////////////////////////////////////////////////////////////////////////////////
 // Standard trait implementations for slices
 ////////////////////////////////////////////////////////////////////////////////
diff --git a/src/liballoc/str.rs b/src/liballoc/str.rs
index 37a1046d094..9a1342c30d5 100644
--- a/src/liballoc/str.rs
+++ b/src/liballoc/str.rs
@@ -37,7 +37,7 @@ use core::unicode::conversions;
 
 use crate::borrow::ToOwned;
 use crate::boxed::Box;
-use crate::slice::{SliceConcat, SliceIndex};
+use crate::slice::{Concat, Join, SliceIndex};
 use crate::string::String;
 use crate::vec::Vec;
 
@@ -71,17 +71,22 @@ pub use core::str::SplitAsciiWhitespace;
 #[stable(feature = "str_escape", since = "1.34.0")]
 pub use core::str::{EscapeDebug, EscapeDefault, EscapeUnicode};
 
-#[unstable(feature = "slice_concat_ext",
-           reason = "trait should not have to exist",
-           issue = "27747")]
-impl<S: Borrow<str>> SliceConcat<str> for S {
+/// Note: `str` in `Concat<str>` is not meaningful here.
+/// This type parameter of the trait only exists to enable another impl.
+#[unstable(feature = "slice_concat_ext", issue = "27747")]
+impl<S: Borrow<str>> Concat<str> for [S] {
     type Output = String;
 
-    fn concat(slice: &[Self]) -> String {
-        Self::join(slice, "")
+    fn concat(slice: &Self) -> String {
+        Join::join(slice, "")
     }
+}
+
+#[unstable(feature = "slice_concat_ext", issue = "27747")]
+impl<S: Borrow<str>> Join<&str> for [S] {
+    type Output = String;
 
-    fn join(slice: &[Self], sep: &str) -> String {
+    fn join(slice: &Self, sep: &str) -> String {
         unsafe {
             String::from_utf8_unchecked( join_generic_copy(slice, sep.as_bytes()) )
         }