Rollup merge of #135073 - joshtriplett:bstr, r=BurntSushi

Implement `ByteStr` and `ByteString` types

Approved ACP: https://github.com/rust-lang/libs-team/issues/502
Tracking issue: https://github.com/rust-lang/rust/issues/134915

These types represent human-readable strings that are conventionally,
but not always, UTF-8. The `Debug` impl prints non-UTF-8 bytes using
escape sequences, and the `Display` impl uses the Unicode replacement
character.

This is a minimal implementation of these types and associated trait
impls. It does not add any helper methods to other types such as `[u8]`
or `Vec<u8>`.

I've omitted a few implementations of `AsRef`, `AsMut`, and `Borrow`,
when those would be the second implementation for a type (counting the
`T` impl), to avoid potential inference failures. We can attempt to add
more impls later in standalone commits, and run them through crater.

In addition to the `bstr` feature, I've added a `bstr_internals` feature
for APIs provided by `core` for use by `alloc` but not currently
intended for stabilization.

This API and its implementation are based *heavily* on the `bstr` crate
by Andrew Gallant (`@BurntSushi).`

r? `@BurntSushi`

13 files changed, 1412 insertions, 14 deletions

diff --git a/library/alloc/src/bstr.rs b/library/alloc/src/bstr.rs
new file mode 100644
index 00000000000..61e61019b50
--- /dev/null
+++ b/library/alloc/src/bstr.rs
@@ -0,0 +1,702 @@
+//! The `ByteStr` and `ByteString` types and trait implementations.
+
+// This could be more fine-grained.
+#![cfg(not(no_global_oom_handling))]
+
+use core::borrow::{Borrow, BorrowMut};
+#[unstable(feature = "bstr", issue = "134915")]
+pub use core::bstr::ByteStr;
+use core::bstr::{impl_partial_eq, impl_partial_eq_n, impl_partial_eq_ord};
+use core::cmp::Ordering;
+use core::ops::{
+    Deref, DerefMut, DerefPure, Index, IndexMut, Range, RangeFrom, RangeFull, RangeInclusive,
+    RangeTo, RangeToInclusive,
+};
+#[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+use core::str::FromStr;
+use core::{fmt, hash};
+
+#[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+use crate::borrow::{Cow, ToOwned};
+#[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+use crate::boxed::Box;
+#[cfg(not(no_rc))]
+use crate::rc::Rc;
+use crate::string::String;
+#[cfg(all(not(no_rc), not(no_sync), target_has_atomic = "ptr"))]
+use crate::sync::Arc;
+use crate::vec::Vec;
+
+/// A wrapper for `Vec<u8>` representing a human-readable string that's conventionally, but not
+/// always, UTF-8.
+///
+/// Unlike `String`, this type permits non-UTF-8 contents, making it suitable for user input,
+/// non-native filenames (as `Path` only supports native filenames), and other applications that
+/// need to round-trip whatever data the user provides.
+///
+/// A `ByteString` owns its contents and can grow and shrink, like a `Vec` or `String`. For a
+/// borrowed byte string, see [`ByteStr`](../../std/bstr/struct.ByteStr.html).
+///
+/// `ByteString` implements `Deref` to `&Vec<u8>`, so all methods available on `&Vec<u8>` are
+/// available on `ByteString`. Similarly, `ByteString` implements `DerefMut` to `&mut Vec<u8>`,
+/// so you can modify a `ByteString` using any method available on `&mut Vec<u8>`.
+///
+/// The `Debug` and `Display` implementations for `ByteString` are the same as those for `ByteStr`,
+/// showing invalid UTF-8 as hex escapes or the Unicode replacement character, respectively.
+#[unstable(feature = "bstr", issue = "134915")]
+#[repr(transparent)]
+#[derive(Clone)]
+#[doc(alias = "BString")]
+pub struct ByteString(pub Vec<u8>);
+
+impl ByteString {
+    #[inline]
+    pub(crate) fn as_bytes(&self) -> &[u8] {
+        &self.0
+    }
+
+    #[inline]
+    pub(crate) fn as_bytestr(&self) -> &ByteStr {
+        ByteStr::new(&self.0)
+    }
+
+    #[inline]
+    pub(crate) fn as_mut_bytestr(&mut self) -> &mut ByteStr {
+        ByteStr::from_bytes_mut(&mut self.0)
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Deref for ByteString {
+    type Target = Vec<u8>;
+
+    #[inline]
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl DerefMut for ByteString {
+    #[inline]
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut self.0
+    }
+}
+
+#[unstable(feature = "deref_pure_trait", issue = "87121")]
+unsafe impl DerefPure for ByteString {}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl fmt::Debug for ByteString {
+    #[inline]
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt::Debug::fmt(self.as_bytestr(), f)
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl fmt::Display for ByteString {
+    #[inline]
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt::Display::fmt(self.as_bytestr(), f)
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl AsRef<[u8]> for ByteString {
+    #[inline]
+    fn as_ref(&self) -> &[u8] {
+        &self.0
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl AsRef<ByteStr> for ByteString {
+    #[inline]
+    fn as_ref(&self) -> &ByteStr {
+        self.as_bytestr()
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl AsMut<[u8]> for ByteString {
+    #[inline]
+    fn as_mut(&mut self) -> &mut [u8] {
+        &mut self.0
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl AsMut<ByteStr> for ByteString {
+    #[inline]
+    fn as_mut(&mut self) -> &mut ByteStr {
+        self.as_mut_bytestr()
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Borrow<[u8]> for ByteString {
+    #[inline]
+    fn borrow(&self) -> &[u8] {
+        &self.0
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Borrow<ByteStr> for ByteString {
+    #[inline]
+    fn borrow(&self) -> &ByteStr {
+        self.as_bytestr()
+    }
+}
+
+// `impl Borrow<ByteStr> for Vec<u8>` omitted to avoid inference failures
+// `impl Borrow<ByteStr> for String` omitted to avoid inference failures
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl BorrowMut<[u8]> for ByteString {
+    #[inline]
+    fn borrow_mut(&mut self) -> &mut [u8] {
+        &mut self.0
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl BorrowMut<ByteStr> for ByteString {
+    #[inline]
+    fn borrow_mut(&mut self) -> &mut ByteStr {
+        self.as_mut_bytestr()
+    }
+}
+
+// `impl BorrowMut<ByteStr> for Vec<u8>` omitted to avoid inference failures
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Default for ByteString {
+    fn default() -> Self {
+        ByteString(Vec::new())
+    }
+}
+
+// Omitted due to inference failures
+//
+// #[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+// #[unstable(feature = "bstr", issue = "134915")]
+// impl<'a, const N: usize> From<&'a [u8; N]> for ByteString {
+//     #[inline]
+//     fn from(s: &'a [u8; N]) -> Self {
+//         ByteString(s.as_slice().to_vec())
+//     }
+// }
+//
+// #[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+// #[unstable(feature = "bstr", issue = "134915")]
+// impl<const N: usize> From<[u8; N]> for ByteString {
+//     #[inline]
+//     fn from(s: [u8; N]) -> Self {
+//         ByteString(s.as_slice().to_vec())
+//     }
+// }
+//
+// #[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+// #[unstable(feature = "bstr", issue = "134915")]
+// impl<'a> From<&'a [u8]> for ByteString {
+//     #[inline]
+//     fn from(s: &'a [u8]) -> Self {
+//         ByteString(s.to_vec())
+//     }
+// }
+//
+// #[unstable(feature = "bstr", issue = "134915")]
+// impl From<Vec<u8>> for ByteString {
+//     #[inline]
+//     fn from(s: Vec<u8>) -> Self {
+//         ByteString(s)
+//     }
+// }
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl From<ByteString> for Vec<u8> {
+    #[inline]
+    fn from(s: ByteString) -> Self {
+        s.0
+    }
+}
+
+// Omitted due to inference failures
+//
+// #[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+// #[unstable(feature = "bstr", issue = "134915")]
+// impl<'a> From<&'a str> for ByteString {
+//     #[inline]
+//     fn from(s: &'a str) -> Self {
+//         ByteString(s.as_bytes().to_vec())
+//     }
+// }
+//
+// #[unstable(feature = "bstr", issue = "134915")]
+// impl From<String> for ByteString {
+//     #[inline]
+//     fn from(s: String) -> Self {
+//         ByteString(s.into_bytes())
+//     }
+// }
+
+#[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+#[unstable(feature = "bstr", issue = "134915")]
+impl<'a> From<&'a ByteStr> for ByteString {
+    #[inline]
+    fn from(s: &'a ByteStr) -> Self {
+        ByteString(s.0.to_vec())
+    }
+}
+
+#[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+#[unstable(feature = "bstr", issue = "134915")]
+impl<'a> From<ByteString> for Cow<'a, ByteStr> {
+    #[inline]
+    fn from(s: ByteString) -> Self {
+        Cow::Owned(s)
+    }
+}
+
+#[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+#[unstable(feature = "bstr", issue = "134915")]
+impl<'a> From<&'a ByteString> for Cow<'a, ByteStr> {
+    #[inline]
+    fn from(s: &'a ByteString) -> Self {
+        Cow::Borrowed(s.as_bytestr())
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl FromIterator<char> for ByteString {
+    #[inline]
+    fn from_iter<T: IntoIterator<Item = char>>(iter: T) -> Self {
+        ByteString(iter.into_iter().collect::<String>().into_bytes())
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl FromIterator<u8> for ByteString {
+    #[inline]
+    fn from_iter<T: IntoIterator<Item = u8>>(iter: T) -> Self {
+        ByteString(iter.into_iter().collect())
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl<'a> FromIterator<&'a str> for ByteString {
+    #[inline]
+    fn from_iter<T: IntoIterator<Item = &'a str>>(iter: T) -> Self {
+        ByteString(iter.into_iter().collect::<String>().into_bytes())
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl<'a> FromIterator<&'a [u8]> for ByteString {
+    #[inline]
+    fn from_iter<T: IntoIterator<Item = &'a [u8]>>(iter: T) -> Self {
+        let mut buf = Vec::new();
+        for b in iter {
+            buf.extend_from_slice(b);
+        }
+        ByteString(buf)
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl<'a> FromIterator<&'a ByteStr> for ByteString {
+    #[inline]
+    fn from_iter<T: IntoIterator<Item = &'a ByteStr>>(iter: T) -> Self {
+        let mut buf = Vec::new();
+        for b in iter {
+            buf.extend_from_slice(&b.0);
+        }
+        ByteString(buf)
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl FromIterator<ByteString> for ByteString {
+    #[inline]
+    fn from_iter<T: IntoIterator<Item = ByteString>>(iter: T) -> Self {
+        let mut buf = Vec::new();
+        for mut b in iter {
+            buf.append(&mut b.0);
+        }
+        ByteString(buf)
+    }
+}
+
+#[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+#[unstable(feature = "bstr", issue = "134915")]
+impl FromStr for ByteString {
+    type Err = core::convert::Infallible;
+
+    #[inline]
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        Ok(ByteString(s.as_bytes().to_vec()))
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Index<usize> for ByteString {
+    type Output = u8;
+
+    #[inline]
+    fn index(&self, idx: usize) -> &u8 {
+        &self.0[idx]
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Index<RangeFull> for ByteString {
+    type Output = ByteStr;
+
+    #[inline]
+    fn index(&self, _: RangeFull) -> &ByteStr {
+        self.as_bytestr()
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Index<Range<usize>> for ByteString {
+    type Output = ByteStr;
+
+    #[inline]
+    fn index(&self, r: Range<usize>) -> &ByteStr {
+        ByteStr::from_bytes(&self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Index<RangeInclusive<usize>> for ByteString {
+    type Output = ByteStr;
+
+    #[inline]
+    fn index(&self, r: RangeInclusive<usize>) -> &ByteStr {
+        ByteStr::from_bytes(&self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Index<RangeFrom<usize>> for ByteString {
+    type Output = ByteStr;
+
+    #[inline]
+    fn index(&self, r: RangeFrom<usize>) -> &ByteStr {
+        ByteStr::from_bytes(&self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Index<RangeTo<usize>> for ByteString {
+    type Output = ByteStr;
+
+    #[inline]
+    fn index(&self, r: RangeTo<usize>) -> &ByteStr {
+        ByteStr::from_bytes(&self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Index<RangeToInclusive<usize>> for ByteString {
+    type Output = ByteStr;
+
+    #[inline]
+    fn index(&self, r: RangeToInclusive<usize>) -> &ByteStr {
+        ByteStr::from_bytes(&self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl IndexMut<usize> for ByteString {
+    #[inline]
+    fn index_mut(&mut self, idx: usize) -> &mut u8 {
+        &mut self.0[idx]
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl IndexMut<RangeFull> for ByteString {
+    #[inline]
+    fn index_mut(&mut self, _: RangeFull) -> &mut ByteStr {
+        self.as_mut_bytestr()
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl IndexMut<Range<usize>> for ByteString {
+    #[inline]
+    fn index_mut(&mut self, r: Range<usize>) -> &mut ByteStr {
+        ByteStr::from_bytes_mut(&mut self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl IndexMut<RangeInclusive<usize>> for ByteString {
+    #[inline]
+    fn index_mut(&mut self, r: RangeInclusive<usize>) -> &mut ByteStr {
+        ByteStr::from_bytes_mut(&mut self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl IndexMut<RangeFrom<usize>> for ByteString {
+    #[inline]
+    fn index_mut(&mut self, r: RangeFrom<usize>) -> &mut ByteStr {
+        ByteStr::from_bytes_mut(&mut self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl IndexMut<RangeTo<usize>> for ByteString {
+    #[inline]
+    fn index_mut(&mut self, r: RangeTo<usize>) -> &mut ByteStr {
+        ByteStr::from_bytes_mut(&mut self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl IndexMut<RangeToInclusive<usize>> for ByteString {
+    #[inline]
+    fn index_mut(&mut self, r: RangeToInclusive<usize>) -> &mut ByteStr {
+        ByteStr::from_bytes_mut(&mut self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl hash::Hash for ByteString {
+    #[inline]
+    fn hash<H: hash::Hasher>(&self, state: &mut H) {
+        self.0.hash(state);
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Eq for ByteString {}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl PartialEq for ByteString {
+    #[inline]
+    fn eq(&self, other: &ByteString) -> bool {
+        self.0 == other.0
+    }
+}
+
+macro_rules! impl_partial_eq_ord_cow {
+    ($lhs:ty, $rhs:ty) => {
+        #[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+        #[allow(unused_lifetimes)]
+        #[unstable(feature = "bstr", issue = "134915")]
+        impl<'a> PartialEq<$rhs> for $lhs {
+            #[inline]
+            fn eq(&self, other: &$rhs) -> bool {
+                let other: &[u8] = (&**other).as_ref();
+                PartialEq::eq(self.as_bytes(), other)
+            }
+        }
+
+        #[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+        #[allow(unused_lifetimes)]
+        #[unstable(feature = "bstr", issue = "134915")]
+        impl<'a> PartialEq<$lhs> for $rhs {
+            #[inline]
+            fn eq(&self, other: &$lhs) -> bool {
+                let this: &[u8] = (&**self).as_ref();
+                PartialEq::eq(this, other.as_bytes())
+            }
+        }
+
+        #[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+        #[allow(unused_lifetimes)]
+        #[unstable(feature = "bstr", issue = "134915")]
+        impl<'a> PartialOrd<$rhs> for $lhs {
+            #[inline]
+            fn partial_cmp(&self, other: &$rhs) -> Option<Ordering> {
+                let other: &[u8] = (&**other).as_ref();
+                PartialOrd::partial_cmp(self.as_bytes(), other)
+            }
+        }
+
+        #[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+        #[allow(unused_lifetimes)]
+        #[unstable(feature = "bstr", issue = "134915")]
+        impl<'a> PartialOrd<$lhs> for $rhs {
+            #[inline]
+            fn partial_cmp(&self, other: &$lhs) -> Option<Ordering> {
+                let this: &[u8] = (&**self).as_ref();
+                PartialOrd::partial_cmp(this, other.as_bytes())
+            }
+        }
+    };
+}
+
+// PartialOrd with `Vec<u8>` omitted to avoid inference failures
+impl_partial_eq!(ByteString, Vec<u8>);
+// PartialOrd with `[u8]` omitted to avoid inference failures
+impl_partial_eq!(ByteString, [u8]);
+// PartialOrd with `&[u8]` omitted to avoid inference failures
+impl_partial_eq!(ByteString, &[u8]);
+// PartialOrd with `String` omitted to avoid inference failures
+impl_partial_eq!(ByteString, String);
+// PartialOrd with `str` omitted to avoid inference failures
+impl_partial_eq!(ByteString, str);
+// PartialOrd with `&str` omitted to avoid inference failures
+impl_partial_eq!(ByteString, &str);
+impl_partial_eq_ord!(ByteString, ByteStr);
+impl_partial_eq_ord!(ByteString, &ByteStr);
+// PartialOrd with `[u8; N]` omitted to avoid inference failures
+impl_partial_eq_n!(ByteString, [u8; N]);
+// PartialOrd with `&[u8; N]` omitted to avoid inference failures
+impl_partial_eq_n!(ByteString, &[u8; N]);
+impl_partial_eq_ord_cow!(ByteString, Cow<'_, ByteStr>);
+impl_partial_eq_ord_cow!(ByteString, Cow<'_, str>);
+impl_partial_eq_ord_cow!(ByteString, Cow<'_, [u8]>);
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Ord for ByteString {
+    #[inline]
+    fn cmp(&self, other: &ByteString) -> Ordering {
+        Ord::cmp(&self.0, &other.0)
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl PartialOrd for ByteString {
+    #[inline]
+    fn partial_cmp(&self, other: &ByteString) -> Option<Ordering> {
+        PartialOrd::partial_cmp(&self.0, &other.0)
+    }
+}
+
+#[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+#[unstable(feature = "bstr", issue = "134915")]
+impl ToOwned for ByteStr {
+    type Owned = ByteString;
+
+    #[inline]
+    fn to_owned(&self) -> ByteString {
+        ByteString(self.0.to_vec())
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl TryFrom<ByteString> for String {
+    type Error = crate::string::FromUtf8Error;
+
+    #[inline]
+    fn try_from(s: ByteString) -> Result<Self, Self::Error> {
+        String::from_utf8(s.0)
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl<'a> TryFrom<&'a ByteString> for &'a str {
+    type Error = crate::str::Utf8Error;
+
+    #[inline]
+    fn try_from(s: &'a ByteString) -> Result<Self, Self::Error> {
+        crate::str::from_utf8(s.0.as_slice())
+    }
+}
+
+// Additional impls for `ByteStr` that require types from `alloc`:
+
+#[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+#[unstable(feature = "bstr", issue = "134915")]
+impl Clone for Box<ByteStr> {
+    #[inline]
+    fn clone(&self) -> Self {
+        Self::from(Box::<[u8]>::from(&self.0))
+    }
+}
+
+#[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+#[unstable(feature = "bstr", issue = "134915")]
+impl<'a> From<&'a ByteStr> for Cow<'a, ByteStr> {
+    #[inline]
+    fn from(s: &'a ByteStr) -> Self {
+        Cow::Borrowed(s)
+    }
+}
+
+#[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+#[unstable(feature = "bstr", issue = "134915")]
+impl From<Box<[u8]>> for Box<ByteStr> {
+    #[inline]
+    fn from(s: Box<[u8]>) -> Box<ByteStr> {
+        // SAFETY: `ByteStr` is a transparent wrapper around `[u8]`.
+        unsafe { Box::from_raw(Box::into_raw(s) as _) }
+    }
+}
+
+#[cfg(not(test))] // https://github.com/rust-lang/rust/issues/135100
+#[unstable(feature = "bstr", issue = "134915")]
+impl From<Box<ByteStr>> for Box<[u8]> {
+    #[inline]
+    fn from(s: Box<ByteStr>) -> Box<[u8]> {
+        // SAFETY: `ByteStr` is a transparent wrapper around `[u8]`.
+        unsafe { Box::from_raw(Box::into_raw(s) as _) }
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+#[cfg(not(no_rc))]
+impl From<Rc<[u8]>> for Rc<ByteStr> {
+    #[inline]
+    fn from(s: Rc<[u8]>) -> Rc<ByteStr> {
+        // SAFETY: `ByteStr` is a transparent wrapper around `[u8]`.
+        unsafe { Rc::from_raw(Rc::into_raw(s) as _) }
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+#[cfg(not(no_rc))]
+impl From<Rc<ByteStr>> for Rc<[u8]> {
+    #[inline]
+    fn from(s: Rc<ByteStr>) -> Rc<[u8]> {
+        // SAFETY: `ByteStr` is a transparent wrapper around `[u8]`.
+        unsafe { Rc::from_raw(Rc::into_raw(s) as _) }
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+#[cfg(all(not(no_rc), not(no_sync), target_has_atomic = "ptr"))]
+impl From<Arc<[u8]>> for Arc<ByteStr> {
+    #[inline]
+    fn from(s: Arc<[u8]>) -> Arc<ByteStr> {
+        // SAFETY: `ByteStr` is a transparent wrapper around `[u8]`.
+        unsafe { Arc::from_raw(Arc::into_raw(s) as _) }
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+#[cfg(all(not(no_rc), not(no_sync), target_has_atomic = "ptr"))]
+impl From<Arc<ByteStr>> for Arc<[u8]> {
+    #[inline]
+    fn from(s: Arc<ByteStr>) -> Arc<[u8]> {
+        // SAFETY: `ByteStr` is a transparent wrapper around `[u8]`.
+        unsafe { Arc::from_raw(Arc::into_raw(s) as _) }
+    }
+}
+
+// PartialOrd with `Vec<u8>` omitted to avoid inference failures
+impl_partial_eq!(ByteStr, Vec<u8>);
+// PartialOrd with `String` omitted to avoid inference failures
+impl_partial_eq!(ByteStr, String);
+impl_partial_eq_ord_cow!(&'a ByteStr, Cow<'a, ByteStr>);
+impl_partial_eq_ord_cow!(&'a ByteStr, Cow<'a, str>);
+impl_partial_eq_ord_cow!(&'a ByteStr, Cow<'a, [u8]>);
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl<'a> TryFrom<&'a ByteStr> for String {
+    type Error = core::str::Utf8Error;
+
+    #[inline]
+    fn try_from(s: &'a ByteStr) -> Result<Self, Self::Error> {
+        Ok(core::str::from_utf8(&s.0)?.into())
+    }
+}
diff --git a/library/alloc/src/lib.rs b/library/alloc/src/lib.rs
index b4f08debc93..28e4217e303 100644
--- a/library/alloc/src/lib.rs
+++ b/library/alloc/src/lib.rs
@@ -102,6 +102,8 @@
 #![feature(async_fn_traits)]
 #![feature(async_iterator)]
 #![feature(box_uninit_write)]
+#![feature(bstr)]
+#![feature(bstr_internals)]
 #![feature(clone_to_uninit)]
 #![feature(coerce_unsized)]
 #![feature(const_eval_select)]
@@ -228,6 +230,8 @@ mod boxed {
     pub use std::boxed::Box;
 }
 pub mod borrow;
+#[unstable(feature = "bstr", issue = "134915")]
+pub mod bstr;
 pub mod collections;
 #[cfg(all(not(no_rc), not(no_sync), not(no_global_oom_handling)))]
 pub mod ffi;
diff --git a/library/core/src/bstr.rs b/library/core/src/bstr.rs
new file mode 100644
index 00000000000..74e07f3d242
--- /dev/null
+++ b/library/core/src/bstr.rs
@@ -0,0 +1,581 @@
+//! The `ByteStr` type and trait implementations.
+
+use crate::borrow::{Borrow, BorrowMut};
+use crate::cmp::Ordering;
+use crate::ops::{
+    Deref, DerefMut, DerefPure, Index, IndexMut, Range, RangeFrom, RangeFull, RangeInclusive,
+    RangeTo, RangeToInclusive,
+};
+use crate::{fmt, hash};
+
+/// A wrapper for `&[u8]` representing a human-readable string that's conventionally, but not
+/// always, UTF-8.
+///
+/// Unlike `&str`, this type permits non-UTF-8 contents, making it suitable for user input,
+/// non-native filenames (as `Path` only supports native filenames), and other applications that
+/// need to round-trip whatever data the user provides.
+///
+/// For an owned, growable byte string buffer, use
+/// [`ByteString`](../../std/bstr/struct.ByteString.html).
+///
+/// `ByteStr` implements `Deref` to `[u8]`, so all methods available on `[u8]` are available on
+/// `ByteStr`.
+///
+/// # Representation
+///
+/// A `&ByteStr` has the same representation as a `&str`. That is, a `&ByteStr` is a wide pointer
+/// which includes a pointer to some bytes and a length.
+///
+/// # Trait implementations
+///
+/// The `ByteStr` type has a number of trait implementations, and in particular, defines equality
+/// and comparisons between `&ByteStr`, `&str`, and `&[u8]`, for convenience.
+///
+/// The `Debug` implementation for `ByteStr` shows its bytes as a normal string, with invalid UTF-8
+/// presented as hex escape sequences.
+///
+/// The `Display` implementation behaves as if the `ByteStr` were first lossily converted to a
+/// `str`, with invalid UTF-8 presented as the Unicode replacement character: �
+///
+#[unstable(feature = "bstr", issue = "134915")]
+#[repr(transparent)]
+#[doc(alias = "BStr")]
+pub struct ByteStr(pub [u8]);
+
+impl ByteStr {
+    /// Creates a `ByteStr` slice from anything that can be converted to a byte slice.
+    ///
+    /// This is a zero-cost conversion.
+    ///
+    /// # Example
+    ///
+    /// You can create a `ByteStr` from a byte array, a byte slice or a string slice:
+    ///
+    /// ```
+    /// # #![feature(bstr)]
+    /// # use std::bstr::ByteStr;
+    /// let a = ByteStr::new(b"abc");
+    /// let b = ByteStr::new(&b"abc"[..]);
+    /// let c = ByteStr::new("abc");
+    ///
+    /// assert_eq!(a, b);
+    /// assert_eq!(a, c);
+    /// ```
+    #[inline]
+    #[unstable(feature = "bstr", issue = "134915")]
+    pub fn new<B: ?Sized + AsRef<[u8]>>(bytes: &B) -> &Self {
+        ByteStr::from_bytes(bytes.as_ref())
+    }
+
+    #[doc(hidden)]
+    #[unstable(feature = "bstr_internals", issue = "none")]
+    #[inline]
+    pub fn from_bytes(slice: &[u8]) -> &Self {
+        // SAFETY: `ByteStr` is a transparent wrapper around `[u8]`, so we can turn a reference to
+        // the wrapped type into a reference to the wrapper type.
+        unsafe { &*(slice as *const [u8] as *const Self) }
+    }
+
+    #[doc(hidden)]
+    #[unstable(feature = "bstr_internals", issue = "none")]
+    #[inline]
+    pub fn from_bytes_mut(slice: &mut [u8]) -> &mut Self {
+        // SAFETY: `ByteStr` is a transparent wrapper around `[u8]`, so we can turn a reference to
+        // the wrapped type into a reference to the wrapper type.
+        unsafe { &mut *(slice as *mut [u8] as *mut Self) }
+    }
+
+    #[doc(hidden)]
+    #[unstable(feature = "bstr_internals", issue = "none")]
+    #[inline]
+    pub fn as_bytes(&self) -> &[u8] {
+        &self.0
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Deref for ByteStr {
+    type Target = [u8];
+
+    #[inline]
+    fn deref(&self) -> &[u8] {
+        &self.0
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl DerefMut for ByteStr {
+    #[inline]
+    fn deref_mut(&mut self) -> &mut [u8] {
+        &mut self.0
+    }
+}
+
+#[unstable(feature = "deref_pure_trait", issue = "87121")]
+unsafe impl DerefPure for ByteStr {}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl fmt::Debug for ByteStr {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "\"")?;
+        for chunk in self.utf8_chunks() {
+            for c in chunk.valid().chars() {
+                match c {
+                    '\0' => write!(f, "\\0")?,
+                    '\x01'..='\x7f' => write!(f, "{}", (c as u8).escape_ascii())?,
+                    _ => write!(f, "{}", c.escape_debug())?,
+                }
+            }
+            write!(f, "{}", chunk.invalid().escape_ascii())?;
+        }
+        write!(f, "\"")?;
+        Ok(())
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl fmt::Display for ByteStr {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fn fmt_nopad(this: &ByteStr, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+            for chunk in this.utf8_chunks() {
+                f.write_str(chunk.valid())?;
+                if !chunk.invalid().is_empty() {
+                    f.write_str("\u{FFFD}")?;
+                }
+            }
+            Ok(())
+        }
+
+        let Some(align) = f.align() else {
+            return fmt_nopad(self, f);
+        };
+        let nchars: usize = self
+            .utf8_chunks()
+            .map(|chunk| chunk.valid().len() + if chunk.invalid().is_empty() { 0 } else { 1 })
+            .sum();
+        let padding = f.width().unwrap_or(0).saturating_sub(nchars);
+        let fill = f.fill();
+        let (lpad, rpad) = match align {
+            fmt::Alignment::Left => (0, padding),
+            fmt::Alignment::Right => (padding, 0),
+            fmt::Alignment::Center => {
+                let half = padding / 2;
+                (half, half + padding % 2)
+            }
+        };
+        for _ in 0..lpad {
+            write!(f, "{fill}")?;
+        }
+        fmt_nopad(self, f)?;
+        for _ in 0..rpad {
+            write!(f, "{fill}")?;
+        }
+
+        Ok(())
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl AsRef<[u8]> for ByteStr {
+    #[inline]
+    fn as_ref(&self) -> &[u8] {
+        &self.0
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl AsRef<ByteStr> for ByteStr {
+    #[inline]
+    fn as_ref(&self) -> &ByteStr {
+        self
+    }
+}
+
+// `impl AsRef<ByteStr> for [u8]` omitted to avoid widespread inference failures
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl AsRef<ByteStr> for str {
+    #[inline]
+    fn as_ref(&self) -> &ByteStr {
+        ByteStr::new(self)
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl AsMut<[u8]> for ByteStr {
+    #[inline]
+    fn as_mut(&mut self) -> &mut [u8] {
+        &mut self.0
+    }
+}
+
+// `impl AsMut<ByteStr> for [u8]` omitted to avoid widespread inference failures
+
+// `impl Borrow<ByteStr> for [u8]` omitted to avoid widespread inference failures
+
+// `impl Borrow<ByteStr> for str` omitted to avoid widespread inference failures
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Borrow<[u8]> for ByteStr {
+    #[inline]
+    fn borrow(&self) -> &[u8] {
+        &self.0
+    }
+}
+
+// `impl BorrowMut<ByteStr> for [u8]` omitted to avoid widespread inference failures
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl BorrowMut<[u8]> for ByteStr {
+    #[inline]
+    fn borrow_mut(&mut self) -> &mut [u8] {
+        &mut self.0
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl<'a> Default for &'a ByteStr {
+    fn default() -> Self {
+        ByteStr::from_bytes(b"")
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl<'a> Default for &'a mut ByteStr {
+    fn default() -> Self {
+        ByteStr::from_bytes_mut(&mut [])
+    }
+}
+
+// Omitted due to inference failures
+//
+// #[unstable(feature = "bstr", issue = "134915")]
+// impl<'a, const N: usize> From<&'a [u8; N]> for &'a ByteStr {
+//     #[inline]
+//     fn from(s: &'a [u8; N]) -> Self {
+//         ByteStr::from_bytes(s)
+//     }
+// }
+//
+// #[unstable(feature = "bstr", issue = "134915")]
+// impl<'a> From<&'a [u8]> for &'a ByteStr {
+//     #[inline]
+//     fn from(s: &'a [u8]) -> Self {
+//         ByteStr::from_bytes(s)
+//     }
+// }
+
+// Omitted due to slice-from-array-issue-113238:
+//
+// #[unstable(feature = "bstr", issue = "134915")]
+// impl<'a> From<&'a ByteStr> for &'a [u8] {
+//     #[inline]
+//     fn from(s: &'a ByteStr) -> Self {
+//         &s.0
+//     }
+// }
+//
+// #[unstable(feature = "bstr", issue = "134915")]
+// impl<'a> From<&'a mut ByteStr> for &'a mut [u8] {
+//     #[inline]
+//     fn from(s: &'a mut ByteStr) -> Self {
+//         &mut s.0
+//     }
+// }
+
+// Omitted due to inference failures
+//
+// #[unstable(feature = "bstr", issue = "134915")]
+// impl<'a> From<&'a str> for &'a ByteStr {
+//     #[inline]
+//     fn from(s: &'a str) -> Self {
+//         ByteStr::from_bytes(s.as_bytes())
+//     }
+// }
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl hash::Hash for ByteStr {
+    #[inline]
+    fn hash<H: hash::Hasher>(&self, state: &mut H) {
+        self.0.hash(state);
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Index<usize> for ByteStr {
+    type Output = u8;
+
+    #[inline]
+    fn index(&self, idx: usize) -> &u8 {
+        &self.0[idx]
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Index<RangeFull> for ByteStr {
+    type Output = ByteStr;
+
+    #[inline]
+    fn index(&self, _: RangeFull) -> &ByteStr {
+        self
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Index<Range<usize>> for ByteStr {
+    type Output = ByteStr;
+
+    #[inline]
+    fn index(&self, r: Range<usize>) -> &ByteStr {
+        ByteStr::from_bytes(&self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Index<RangeInclusive<usize>> for ByteStr {
+    type Output = ByteStr;
+
+    #[inline]
+    fn index(&self, r: RangeInclusive<usize>) -> &ByteStr {
+        ByteStr::from_bytes(&self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Index<RangeFrom<usize>> for ByteStr {
+    type Output = ByteStr;
+
+    #[inline]
+    fn index(&self, r: RangeFrom<usize>) -> &ByteStr {
+        ByteStr::from_bytes(&self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Index<RangeTo<usize>> for ByteStr {
+    type Output = ByteStr;
+
+    #[inline]
+    fn index(&self, r: RangeTo<usize>) -> &ByteStr {
+        ByteStr::from_bytes(&self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Index<RangeToInclusive<usize>> for ByteStr {
+    type Output = ByteStr;
+
+    #[inline]
+    fn index(&self, r: RangeToInclusive<usize>) -> &ByteStr {
+        ByteStr::from_bytes(&self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl IndexMut<usize> for ByteStr {
+    #[inline]
+    fn index_mut(&mut self, idx: usize) -> &mut u8 {
+        &mut self.0[idx]
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl IndexMut<RangeFull> for ByteStr {
+    #[inline]
+    fn index_mut(&mut self, _: RangeFull) -> &mut ByteStr {
+        self
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl IndexMut<Range<usize>> for ByteStr {
+    #[inline]
+    fn index_mut(&mut self, r: Range<usize>) -> &mut ByteStr {
+        ByteStr::from_bytes_mut(&mut self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl IndexMut<RangeInclusive<usize>> for ByteStr {
+    #[inline]
+    fn index_mut(&mut self, r: RangeInclusive<usize>) -> &mut ByteStr {
+        ByteStr::from_bytes_mut(&mut self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl IndexMut<RangeFrom<usize>> for ByteStr {
+    #[inline]
+    fn index_mut(&mut self, r: RangeFrom<usize>) -> &mut ByteStr {
+        ByteStr::from_bytes_mut(&mut self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl IndexMut<RangeTo<usize>> for ByteStr {
+    #[inline]
+    fn index_mut(&mut self, r: RangeTo<usize>) -> &mut ByteStr {
+        ByteStr::from_bytes_mut(&mut self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl IndexMut<RangeToInclusive<usize>> for ByteStr {
+    #[inline]
+    fn index_mut(&mut self, r: RangeToInclusive<usize>) -> &mut ByteStr {
+        ByteStr::from_bytes_mut(&mut self.0[r])
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Eq for ByteStr {}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl PartialEq<ByteStr> for ByteStr {
+    #[inline]
+    fn eq(&self, other: &ByteStr) -> bool {
+        &self.0 == &other.0
+    }
+}
+
+#[doc(hidden)]
+#[macro_export]
+#[unstable(feature = "bstr_internals", issue = "none")]
+macro_rules! impl_partial_eq {
+    ($lhs:ty, $rhs:ty) => {
+        #[allow(unused_lifetimes)]
+        impl<'a> PartialEq<$rhs> for $lhs {
+            #[inline]
+            fn eq(&self, other: &$rhs) -> bool {
+                let other: &[u8] = other.as_ref();
+                PartialEq::eq(self.as_bytes(), other)
+            }
+        }
+
+        #[allow(unused_lifetimes)]
+        impl<'a> PartialEq<$lhs> for $rhs {
+            #[inline]
+            fn eq(&self, other: &$lhs) -> bool {
+                let this: &[u8] = self.as_ref();
+                PartialEq::eq(this, other.as_bytes())
+            }
+        }
+    };
+}
+
+#[doc(hidden)]
+#[unstable(feature = "bstr_internals", issue = "none")]
+pub use impl_partial_eq;
+
+#[doc(hidden)]
+#[macro_export]
+#[unstable(feature = "bstr_internals", issue = "none")]
+macro_rules! impl_partial_eq_ord {
+    ($lhs:ty, $rhs:ty) => {
+        $crate::bstr::impl_partial_eq!($lhs, $rhs);
+
+        #[allow(unused_lifetimes)]
+        #[unstable(feature = "bstr", issue = "134915")]
+        impl<'a> PartialOrd<$rhs> for $lhs {
+            #[inline]
+            fn partial_cmp(&self, other: &$rhs) -> Option<Ordering> {
+                let other: &[u8] = other.as_ref();
+                PartialOrd::partial_cmp(self.as_bytes(), other)
+            }
+        }
+
+        #[allow(unused_lifetimes)]
+        #[unstable(feature = "bstr", issue = "134915")]
+        impl<'a> PartialOrd<$lhs> for $rhs {
+            #[inline]
+            fn partial_cmp(&self, other: &$lhs) -> Option<Ordering> {
+                let this: &[u8] = self.as_ref();
+                PartialOrd::partial_cmp(this, other.as_bytes())
+            }
+        }
+    };
+}
+
+#[doc(hidden)]
+#[unstable(feature = "bstr_internals", issue = "none")]
+pub use impl_partial_eq_ord;
+
+#[doc(hidden)]
+#[macro_export]
+#[unstable(feature = "bstr_internals", issue = "none")]
+macro_rules! impl_partial_eq_n {
+    ($lhs:ty, $rhs:ty) => {
+        #[allow(unused_lifetimes)]
+        #[unstable(feature = "bstr", issue = "134915")]
+        impl<const N: usize> PartialEq<$rhs> for $lhs {
+            #[inline]
+            fn eq(&self, other: &$rhs) -> bool {
+                let other: &[u8] = other.as_ref();
+                PartialEq::eq(self.as_bytes(), other)
+            }
+        }
+
+        #[allow(unused_lifetimes)]
+        #[unstable(feature = "bstr", issue = "134915")]
+        impl<const N: usize> PartialEq<$lhs> for $rhs {
+            #[inline]
+            fn eq(&self, other: &$lhs) -> bool {
+                let this: &[u8] = self.as_ref();
+                PartialEq::eq(this, other.as_bytes())
+            }
+        }
+    };
+}
+
+#[doc(hidden)]
+#[unstable(feature = "bstr_internals", issue = "none")]
+pub use impl_partial_eq_n;
+
+// PartialOrd with `[u8]` omitted to avoid inference failures
+impl_partial_eq!(ByteStr, [u8]);
+// PartialOrd with `&[u8]` omitted to avoid inference failures
+impl_partial_eq!(ByteStr, &[u8]);
+// PartialOrd with `str` omitted to avoid inference failures
+impl_partial_eq!(ByteStr, str);
+// PartialOrd with `&str` omitted to avoid inference failures
+impl_partial_eq!(ByteStr, &str);
+// PartialOrd with `[u8; N]` omitted to avoid inference failures
+impl_partial_eq_n!(ByteStr, [u8; N]);
+// PartialOrd with `[u8; N]` omitted to avoid inference failures
+impl_partial_eq_n!(ByteStr, &[u8; N]);
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl Ord for ByteStr {
+    #[inline]
+    fn cmp(&self, other: &ByteStr) -> Ordering {
+        Ord::cmp(&self.0, &other.0)
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl PartialOrd for ByteStr {
+    #[inline]
+    fn partial_cmp(&self, other: &ByteStr) -> Option<Ordering> {
+        PartialOrd::partial_cmp(&self.0, &other.0)
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl<'a> TryFrom<&'a ByteStr> for &'a str {
+    type Error = crate::str::Utf8Error;
+
+    #[inline]
+    fn try_from(s: &'a ByteStr) -> Result<Self, Self::Error> {
+        crate::str::from_utf8(&s.0)
+    }
+}
+
+#[unstable(feature = "bstr", issue = "134915")]
+impl<'a> TryFrom<&'a mut ByteStr> for &'a mut str {
+    type Error = crate::str::Utf8Error;
+
+    #[inline]
+    fn try_from(s: &'a mut ByteStr) -> Result<Self, Self::Error> {
+        crate::str::from_utf8_mut(&mut s.0)
+    }
+}
diff --git a/library/core/src/clone.rs b/library/core/src/clone.rs
index ec1aed53eaf..00300328b64 100644
--- a/library/core/src/clone.rs
+++ b/library/core/src/clone.rs
@@ -311,6 +311,16 @@ unsafe impl CloneToUninit for crate::ffi::CStr {
     }
 }
 
+#[unstable(feature = "bstr", issue = "134915")]
+unsafe impl CloneToUninit for crate::bstr::ByteStr {
+    #[inline]
+    #[cfg_attr(debug_assertions, track_caller)]
+    unsafe fn clone_to_uninit(&self, dst: *mut u8) {
+        // SAFETY: ByteStr is a `#[repr(transparent)]` wrapper around `[u8]`
+        unsafe { self.as_bytes().clone_to_uninit(dst) }
+    }
+}
+
 /// Implementations of `Clone` for primitive types.
 ///
 /// Implementations that cannot be described in Rust
diff --git a/library/core/src/lib.rs b/library/core/src/lib.rs
index f58eab3b1b1..01ed3cc69a2 100644
--- a/library/core/src/lib.rs
+++ b/library/core/src/lib.rs
@@ -111,6 +111,8 @@
 #![feature(array_ptr_get)]
 #![feature(asm_experimental_arch)]
 #![feature(bigint_helper_methods)]
+#![feature(bstr)]
+#![feature(bstr_internals)]
 #![feature(const_carrying_mul_add)]
 #![feature(const_eval_select)]
 #![feature(core_intrinsics)]
@@ -336,6 +338,8 @@ pub mod ascii;
 pub mod asserting;
 #[unstable(feature = "async_iterator", issue = "79024")]
 pub mod async_iter;
+#[unstable(feature = "bstr", issue = "134915")]
+pub mod bstr;
 pub mod cell;
 pub mod char;
 pub mod ffi;
diff --git a/library/core/tests/bstr.rs b/library/core/tests/bstr.rs
new file mode 100644
index 00000000000..5fecd0a4084
--- /dev/null
+++ b/library/core/tests/bstr.rs
@@ -0,0 +1,54 @@
+#![feature(bstr)]
+
+use core::ByteStr;
+
+#[test]
+fn test_debug() {
+    assert_eq!(
+        r#""\0\x01\x02\x03\x04\x05\x06\x07\x08\t\n\x11\x12\r\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f \x7f\x80\x81\xfe\xff""#,
+        format!("{:?}", ByteStr::new(b"\0\x01\x02\x03\x04\x05\x06\x07\x08\t\n\x11\x12\r\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f \x7f\x80\x81\xfe\xff")),
+    );
+}
+
+#[test]
+fn test_display() {
+    let b1 = ByteStr::new("abc");
+    let b2 = ByteStr::new(b"\xf0\x28\x8c\xbc");
+
+    assert_eq!(&format!("{b1}"), "abc");
+    assert_eq!(&format!("{b2}"), "�(��");
+
+    assert_eq!(&format!("{b1:<7}!"), "abc    !");
+    assert_eq!(&format!("{b1:>7}!"), "    abc!");
+    assert_eq!(&format!("{b1:^7}!"), "  abc  !");
+    assert_eq!(&format!("{b1:^6}!"), " abc  !");
+    assert_eq!(&format!("{b1:-<7}!"), "abc----!");
+    assert_eq!(&format!("{b1:->7}!"), "----abc!");
+    assert_eq!(&format!("{b1:-^7}!"), "--abc--!");
+    assert_eq!(&format!("{b1:-^6}!"), "-abc--!");
+
+    assert_eq!(&format!("{b2:<7}!"), "�(��   !");
+    assert_eq!(&format!("{b2:>7}!"), "   �(��!");
+    assert_eq!(&format!("{b2:^7}!"), " �(��  !");
+    assert_eq!(&format!("{b2:^6}!"), " �(�� !");
+    assert_eq!(&format!("{b2:-<7}!"), "�(��---!");
+    assert_eq!(&format!("{b2:->7}!"), "---�(��!");
+    assert_eq!(&format!("{b2:-^7}!"), "-�(��--!");
+    assert_eq!(&format!("{b2:-^6}!"), "-�(��-!");
+
+    assert_eq!(&format!("{b1:<2}!"), "abc!");
+    assert_eq!(&format!("{b1:>2}!"), "abc!");
+    assert_eq!(&format!("{b1:^2}!"), "abc!");
+    assert_eq!(&format!("{b1:-<2}!"), "abc!");
+    assert_eq!(&format!("{b1:->2}!"), "abc!");
+    assert_eq!(&format!("{b1:-^2}!"), "abc!");
+
+    assert_eq!(&format!("{b2:<3}!"), "�(��!");
+    assert_eq!(&format!("{b2:>3}!"), "�(��!");
+    assert_eq!(&format!("{b2:^3}!"), "�(��!");
+    assert_eq!(&format!("{b2:^2}!"), "�(��!");
+    assert_eq!(&format!("{b2:-<3}!"), "�(��!");
+    assert_eq!(&format!("{b2:->3}!"), "�(��!");
+    assert_eq!(&format!("{b2:-^3}!"), "�(��!");
+    assert_eq!(&format!("{b2:-^2}!"), "�(��!");
+}
diff --git a/library/std/src/bstr.rs b/library/std/src/bstr.rs
new file mode 100644
index 00000000000..dd491771628
--- /dev/null
+++ b/library/std/src/bstr.rs
@@ -0,0 +1,4 @@
+//! The `ByteStr` and `ByteString` types and trait implementations.
+
+#[unstable(feature = "bstr", issue = "134915")]
+pub use alloc::bstr::{ByteStr, ByteString};
diff --git a/library/std/src/lib.rs b/library/std/src/lib.rs
index 39f234e4ba6..acb3a0578e5 100644
--- a/library/std/src/lib.rs
+++ b/library/std/src/lib.rs
@@ -320,6 +320,8 @@
 // Library features (core):
 // tidy-alphabetical-start
 #![feature(array_chunks)]
+#![feature(bstr)]
+#![feature(bstr_internals)]
 #![feature(c_str_module)]
 #![feature(char_internals)]
 #![feature(clone_to_uninit)]
@@ -581,6 +583,8 @@ pub mod f64;
 pub mod thread;
 pub mod ascii;
 pub mod backtrace;
+#[unstable(feature = "bstr", issue = "134915")]
+pub mod bstr;
 pub mod collections;
 pub mod env;
 pub mod error;
diff --git a/src/tools/linkchecker/main.rs b/src/tools/linkchecker/main.rs
index 570b2c374c0..19340b5d07a 100644
--- a/src/tools/linkchecker/main.rs
+++ b/src/tools/linkchecker/main.rs
@@ -50,6 +50,29 @@ const LINKCHECK_EXCEPTIONS: &[(&str, &[&str])] = &[
     ("alloc/slice/trait.Concat.html", &["#method.concat"]),
     ("alloc/slice/index.html", &["#method.concat", "#method.join"]),
     ("alloc/vec/struct.Vec.html", &["#method.sort_by_key", "#method.sort_by_cached_key"]),
+    ("alloc/bstr/struct.ByteStr.html", &[
+        "#method.to_ascii_uppercase",
+        "#method.to_ascii_lowercase",
+        "core/slice::sort_by_key",
+        "core\\slice::sort_by_key",
+        "#method.sort_by_cached_key",
+        "#method.sort_by_key"
+    ]),
+    ("alloc/bstr/struct.ByteString.html", &[
+        "#method.to_ascii_uppercase",
+        "#method.to_ascii_lowercase",
+        "core/slice::sort_by_key",
+        "core\\slice::sort_by_key",
+        "#method.sort_by_cached_key",
+        "#method.sort_by_key"
+    ]),
+    ("core/bstr/struct.ByteStr.html", &[
+        "#method.to_ascii_uppercase",
+        "#method.to_ascii_lowercase",
+        "core/bstr/slice::sort_by_key",
+        "core\\bstr\\slice::sort_by_key",
+        "#method.sort_by_cached_key"
+    ]),
     ("core/primitive.str.html", &["#method.to_ascii_uppercase", "#method.to_ascii_lowercase"]),
     ("core/primitive.slice.html", &["#method.to_ascii_uppercase", "#method.to_ascii_lowercase",
                                     "core/slice::sort_by_key", "core\\slice::sort_by_key",
diff --git a/tests/ui/associated-types/associated-types-in-ambiguous-context.stderr b/tests/ui/associated-types/associated-types-in-ambiguous-context.stderr
index c5260adbed4..88db3611719 100644
--- a/tests/ui/associated-types/associated-types-in-ambiguous-context.stderr
+++ b/tests/ui/associated-types/associated-types-in-ambiguous-context.stderr
@@ -40,14 +40,14 @@ LL | type X = std::ops::Deref::Target;
    |
 help: use fully-qualified syntax
    |
+LL | type X = <ByteStr as Deref>::Target;
+   |          ~~~~~~~~~~~~~~~~~~~~~~~~~~
+LL | type X = <ByteString as Deref>::Target;
+   |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 LL | type X = <CString as Deref>::Target;
    |          ~~~~~~~~~~~~~~~~~~~~~~~~~~
 LL | type X = <IoSlice<'_> as Deref>::Target;
    |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-LL | type X = <IoSliceMut<'_> as Deref>::Target;
-   |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-LL | type X = <OsString as Deref>::Target;
-   |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~
      and N other candidates
 
 error: aborting due to 5 previous errors
diff --git a/tests/ui/consts/too_generic_eval_ice.stderr b/tests/ui/consts/too_generic_eval_ice.stderr
index b48be16a24c..3cc4377514a 100644
--- a/tests/ui/consts/too_generic_eval_ice.stderr
+++ b/tests/ui/consts/too_generic_eval_ice.stderr
@@ -32,13 +32,13 @@ LL |         [5; Self::HOST_SIZE] == [6; 0]
    = help: the following other types implement trait `PartialEq<Rhs>`:
              `&[T]` implements `PartialEq<Vec<U, A>>`
              `&[T]` implements `PartialEq<[U; N]>`
+             `&[u8; N]` implements `PartialEq<ByteStr>`
+             `&[u8; N]` implements `PartialEq<ByteString>`
+             `&[u8]` implements `PartialEq<ByteStr>`
+             `&[u8]` implements `PartialEq<ByteString>`
              `&mut [T]` implements `PartialEq<Vec<U, A>>`
              `&mut [T]` implements `PartialEq<[U; N]>`
-             `[T; N]` implements `PartialEq<&[U]>`
-             `[T; N]` implements `PartialEq<&mut [U]>`
-             `[T; N]` implements `PartialEq<[U; N]>`
-             `[T; N]` implements `PartialEq<[U]>`
-           and 3 others
+           and 11 others
 
 error: aborting due to 4 previous errors
 
diff --git a/tests/ui/inference/issue-72616.stderr b/tests/ui/inference/issue-72616.stderr
index 02c92c1c11d..a26f9a1ff56 100644
--- a/tests/ui/inference/issue-72616.stderr
+++ b/tests/ui/inference/issue-72616.stderr
@@ -6,11 +6,14 @@ LL |         if String::from("a") == "a".try_into().unwrap() {}
    |                              |
    |                              type must be known at this point
    |
-   = note: multiple `impl`s satisfying `String: PartialEq<_>` found in the `alloc` crate:
-           - impl PartialEq for String;
-           - impl<'a, 'b> PartialEq<&'a str> for String;
-           - impl<'a, 'b> PartialEq<Cow<'a, str>> for String;
-           - impl<'a, 'b> PartialEq<str> for String;
+   = note: cannot satisfy `String: PartialEq<_>`
+   = help: the following types implement trait `PartialEq<Rhs>`:
+             `String` implements `PartialEq<&str>`
+             `String` implements `PartialEq<ByteStr>`
+             `String` implements `PartialEq<ByteString>`
+             `String` implements `PartialEq<Cow<'_, str>>`
+             `String` implements `PartialEq<str>`
+             `String` implements `PartialEq`
 help: try using a fully qualified path to specify the expected types
    |
 LL |         if String::from("a") == <&str as TryInto<T>>::try_into("a").unwrap() {}
diff --git a/tests/ui/inference/issue-72690.stderr b/tests/ui/inference/issue-72690.stderr
index 6391672f861..2d09f667ae2 100644
--- a/tests/ui/inference/issue-72690.stderr
+++ b/tests/ui/inference/issue-72690.stderr
@@ -15,6 +15,7 @@ LL |     String::from("x".as_ref());
    |                      ^^^^^^
    |
    = note: multiple `impl`s satisfying `str: AsRef<_>` found in the following crates: `core`, `std`:
+           - impl AsRef<ByteStr> for str;
            - impl AsRef<OsStr> for str;
            - impl AsRef<Path> for str;
            - impl AsRef<[u8]> for str;
@@ -41,6 +42,7 @@ LL |     |x| String::from("x".as_ref());
    |                          ^^^^^^
    |
    = note: multiple `impl`s satisfying `str: AsRef<_>` found in the following crates: `core`, `std`:
+           - impl AsRef<ByteStr> for str;
            - impl AsRef<OsStr> for str;
            - impl AsRef<Path> for str;
            - impl AsRef<[u8]> for str;
@@ -57,6 +59,7 @@ LL |     let _ = "x".as_ref();
    |         ^       ------ type must be known at this point
    |
    = note: multiple `impl`s satisfying `str: AsRef<_>` found in the following crates: `core`, `std`:
+           - impl AsRef<ByteStr> for str;
            - impl AsRef<OsStr> for str;
            - impl AsRef<Path> for str;
            - impl AsRef<[u8]> for str;
@@ -83,6 +86,7 @@ LL |     String::from("x".as_ref());
    |                      ^^^^^^
    |
    = note: multiple `impl`s satisfying `str: AsRef<_>` found in the following crates: `core`, `std`:
+           - impl AsRef<ByteStr> for str;
            - impl AsRef<OsStr> for str;
            - impl AsRef<Path> for str;
            - impl AsRef<[u8]> for str;
@@ -109,6 +113,7 @@ LL |     String::from("x".as_ref());
    |                      ^^^^^^
    |
    = note: multiple `impl`s satisfying `str: AsRef<_>` found in the following crates: `core`, `std`:
+           - impl AsRef<ByteStr> for str;
            - impl AsRef<OsStr> for str;
            - impl AsRef<Path> for str;
            - impl AsRef<[u8]> for str;
@@ -135,6 +140,7 @@ LL |     String::from("x".as_ref());
    |                      ^^^^^^
    |
    = note: multiple `impl`s satisfying `str: AsRef<_>` found in the following crates: `core`, `std`:
+           - impl AsRef<ByteStr> for str;
            - impl AsRef<OsStr> for str;
            - impl AsRef<Path> for str;
            - impl AsRef<[u8]> for str;
@@ -161,6 +167,7 @@ LL |     String::from("x".as_ref());
    |                      ^^^^^^
    |
    = note: multiple `impl`s satisfying `str: AsRef<_>` found in the following crates: `core`, `std`:
+           - impl AsRef<ByteStr> for str;
            - impl AsRef<OsStr> for str;
            - impl AsRef<Path> for str;
            - impl AsRef<[u8]> for str;
@@ -187,6 +194,7 @@ LL |     String::from("x".as_ref());
    |                      ^^^^^^
    |
    = note: multiple `impl`s satisfying `str: AsRef<_>` found in the following crates: `core`, `std`:
+           - impl AsRef<ByteStr> for str;
            - impl AsRef<OsStr> for str;
            - impl AsRef<Path> for str;
            - impl AsRef<[u8]> for str;
@@ -213,6 +221,7 @@ LL |     String::from("x".as_ref());
    |                      ^^^^^^
    |
    = note: multiple `impl`s satisfying `str: AsRef<_>` found in the following crates: `core`, `std`:
+           - impl AsRef<ByteStr> for str;
            - impl AsRef<OsStr> for str;
            - impl AsRef<Path> for str;
            - impl AsRef<[u8]> for str;