| #![no_std] | |
| extern crate alloc; | |
| use alloc::{borrow::Cow, boxed::Box, string::String, sync::Arc}; | |
| use core::{ | |
| borrow::Borrow, | |
| cmp::{self, Ordering}, | |
| convert::Infallible, | |
| fmt, hash, iter, | |
| mem::transmute, | |
| ops::Deref, | |
| str::FromStr, | |
| }; | |
| /// A `SmolStr` is a string type that has the following properties: | |
| /// | |
| /// * `size_of::<SmolStr>() == 24` (therefor `== size_of::<String>()` on 64 bit platforms) | |
| /// * `Clone` is `O(1)` | |
| /// * Strings are stack-allocated if they are: | |
| /// * Up to 23 bytes long | |
| /// * Longer than 23 bytes, but substrings of `WS` (see below). Such strings consist | |
| /// solely of consecutive newlines, followed by consecutive spaces | |
| /// * If a string does not satisfy the aforementioned conditions, it is heap-allocated | |
| /// * Additionally, a `SmolStr` can be explicitely created from a `&'static str` without allocation | |
| /// | |
| /// Unlike `String`, however, `SmolStr` is immutable. The primary use case for | |
| /// `SmolStr` is a good enough default storage for tokens of typical programming | |
| /// languages. Strings consisting of a series of newlines, followed by a series of | |
| /// whitespace are a typical pattern in computer programs because of indentation. | |
| /// Note that a specialized interner might be a better solution for some use cases. | |
| /// | |
| /// `WS`: A string of 32 newlines followed by 128 spaces. | |
| #[derive(Clone)] | |
| pub struct SmolStr(Repr); | |
| impl SmolStr { | |
| #[deprecated = "Use `new_inline` instead"] | |
| pub const fn new_inline_from_ascii(len: usize, bytes: &[u8]) -> SmolStr { | |
| assert!(len <= INLINE_CAP); | |
| const ZEROS: &[u8] = &[0; INLINE_CAP]; | |
| let mut buf = [0; INLINE_CAP]; | |
| macro_rules! s { | |
| ($($idx:literal),*) => ( $(s!(set $idx);)* ); | |
| (set $idx:literal) => ({ | |
| let src: &[u8] = [ZEROS, bytes][($idx < len) as usize]; | |
| let byte = src[$idx]; | |
| let _is_ascii = [(); 128][byte as usize]; | |
| buf[$idx] = byte | |
| }); | |
| } | |
| s!(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22); | |
| SmolStr(Repr::Inline { | |
| len: unsafe { transmute(len as u8) }, | |
| buf, | |
| }) | |
| } | |
| /// Constructs inline variant of `SmolStr`. | |
| /// | |
| /// Panics if `text.len() > 23`. | |
| #[inline] | |
| pub const fn new_inline(text: &str) -> SmolStr { | |
| assert!(text.len() <= INLINE_CAP); // avoids checks in loop | |
| let mut buf = [0; INLINE_CAP]; | |
| let mut i = 0; | |
| while i < text.len() { | |
| buf[i] = text.as_bytes()[i]; | |
| i += 1 | |
| } | |
| SmolStr(Repr::Inline { | |
| len: unsafe { transmute(text.len() as u8) }, | |
| buf, | |
| }) | |
| } | |
| /// Constructs a `SmolStr` from a statically allocated string. | |
| /// | |
| /// This never allocates. | |
| #[inline(always)] | |
| pub const fn new_static(text: &'static str) -> SmolStr { | |
| // NOTE: this never uses the inline storage; if a canonical | |
| // representation is needed, we could check for `len() < INLINE_CAP` | |
| // and call `new_inline`, but this would mean an extra branch. | |
| SmolStr(Repr::Static(text)) | |
| } | |
| pub fn new<T>(text: T) -> SmolStr | |
| where | |
| T: AsRef<str>, | |
| { | |
| SmolStr(Repr::new(text)) | |
| } | |
| #[inline(always)] | |
| pub fn as_str(&self) -> &str { | |
| self.0.as_str() | |
| } | |
| #[allow(clippy::inherent_to_string_shadow_display)] | |
| #[inline(always)] | |
| pub fn to_string(&self) -> String { | |
| use alloc::borrow::ToOwned; | |
| self.as_str().to_owned() | |
| } | |
| #[inline(always)] | |
| pub fn len(&self) -> usize { | |
| self.0.len() | |
| } | |
| #[inline(always)] | |
| pub fn is_empty(&self) -> bool { | |
| self.0.is_empty() | |
| } | |
| #[inline(always)] | |
| pub const fn is_heap_allocated(&self) -> bool { | |
| matches!(self.0, Repr::Heap(..)) | |
| } | |
| fn from_char_iter<I: iter::Iterator<Item = char>>(mut iter: I) -> SmolStr { | |
| let (min_size, _) = iter.size_hint(); | |
| if min_size > INLINE_CAP { | |
| let heap: String = iter.collect(); | |
| return SmolStr(Repr::Heap(heap.into_boxed_str().into())); | |
| } | |
| let mut len = 0; | |
| let mut buf = [0u8; INLINE_CAP]; | |
| while let Some(ch) = iter.next() { | |
| let size = ch.len_utf8(); | |
| if size + len > INLINE_CAP { | |
| let (min_remaining, _) = iter.size_hint(); | |
| let mut heap = String::with_capacity(size + len + min_remaining); | |
| heap.push_str(core::str::from_utf8(&buf[..len]).unwrap()); | |
| heap.push(ch); | |
| heap.extend(iter); | |
| return SmolStr(Repr::Heap(heap.into_boxed_str().into())); | |
| } | |
| ch.encode_utf8(&mut buf[len..]); | |
| len += size; | |
| } | |
| SmolStr(Repr::Inline { | |
| len: unsafe { transmute(len as u8) }, | |
| buf, | |
| }) | |
| } | |
| } | |
| impl Default for SmolStr { | |
| #[inline(always)] | |
| fn default() -> SmolStr { | |
| SmolStr(Repr::Inline { | |
| len: InlineSize::_V0, | |
| buf: [0; INLINE_CAP], | |
| }) | |
| } | |
| } | |
| impl Deref for SmolStr { | |
| type Target = str; | |
| #[inline(always)] | |
| fn deref(&self) -> &str { | |
| self.as_str() | |
| } | |
| } | |
| impl PartialEq<SmolStr> for SmolStr { | |
| fn eq(&self, other: &SmolStr) -> bool { | |
| self.as_str() == other.as_str() | |
| } | |
| } | |
| impl Eq for SmolStr {} | |
| impl PartialEq<str> for SmolStr { | |
| fn eq(&self, other: &str) -> bool { | |
| self.as_str() == other | |
| } | |
| } | |
| impl PartialEq<SmolStr> for str { | |
| fn eq(&self, other: &SmolStr) -> bool { | |
| other == self | |
| } | |
| } | |
| impl<'a> PartialEq<&'a str> for SmolStr { | |
| fn eq(&self, other: &&'a str) -> bool { | |
| self == *other | |
| } | |
| } | |
| impl<'a> PartialEq<SmolStr> for &'a str { | |
| fn eq(&self, other: &SmolStr) -> bool { | |
| *self == other | |
| } | |
| } | |
| impl PartialEq<String> for SmolStr { | |
| fn eq(&self, other: &String) -> bool { | |
| self.as_str() == other | |
| } | |
| } | |
| impl PartialEq<SmolStr> for String { | |
| fn eq(&self, other: &SmolStr) -> bool { | |
| other == self | |
| } | |
| } | |
| impl<'a> PartialEq<&'a String> for SmolStr { | |
| fn eq(&self, other: &&'a String) -> bool { | |
| self == *other | |
| } | |
| } | |
| impl<'a> PartialEq<SmolStr> for &'a String { | |
| fn eq(&self, other: &SmolStr) -> bool { | |
| *self == other | |
| } | |
| } | |
| impl Ord for SmolStr { | |
| fn cmp(&self, other: &SmolStr) -> Ordering { | |
| self.as_str().cmp(other.as_str()) | |
| } | |
| } | |
| impl PartialOrd for SmolStr { | |
| fn partial_cmp(&self, other: &SmolStr) -> Option<Ordering> { | |
| Some(self.cmp(other)) | |
| } | |
| } | |
| impl hash::Hash for SmolStr { | |
| fn hash<H: hash::Hasher>(&self, hasher: &mut H) { | |
| self.as_str().hash(hasher); | |
| } | |
| } | |
| impl fmt::Debug for SmolStr { | |
| fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
| fmt::Debug::fmt(self.as_str(), f) | |
| } | |
| } | |
| impl fmt::Display for SmolStr { | |
| fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
| fmt::Display::fmt(self.as_str(), f) | |
| } | |
| } | |
| impl iter::FromIterator<char> for SmolStr { | |
| fn from_iter<I: iter::IntoIterator<Item = char>>(iter: I) -> SmolStr { | |
| let iter = iter.into_iter(); | |
| Self::from_char_iter(iter) | |
| } | |
| } | |
| fn build_from_str_iter<T>(mut iter: impl Iterator<Item = T>) -> SmolStr | |
| where | |
| T: AsRef<str>, | |
| String: iter::Extend<T>, | |
| { | |
| let mut len = 0; | |
| let mut buf = [0u8; INLINE_CAP]; | |
| while let Some(slice) = iter.next() { | |
| let slice = slice.as_ref(); | |
| let size = slice.len(); | |
| if size + len > INLINE_CAP { | |
| let mut heap = String::with_capacity(size + len); | |
| heap.push_str(core::str::from_utf8(&buf[..len]).unwrap()); | |
| heap.push_str(slice); | |
| heap.extend(iter); | |
| return SmolStr(Repr::Heap(heap.into_boxed_str().into())); | |
| } | |
| buf[len..][..size].copy_from_slice(slice.as_bytes()); | |
| len += size; | |
| } | |
| SmolStr(Repr::Inline { | |
| len: unsafe { transmute(len as u8) }, | |
| buf, | |
| }) | |
| } | |
| impl iter::FromIterator<String> for SmolStr { | |
| fn from_iter<I: iter::IntoIterator<Item = String>>(iter: I) -> SmolStr { | |
| build_from_str_iter(iter.into_iter()) | |
| } | |
| } | |
| impl<'a> iter::FromIterator<&'a String> for SmolStr { | |
| fn from_iter<I: iter::IntoIterator<Item = &'a String>>(iter: I) -> SmolStr { | |
| SmolStr::from_iter(iter.into_iter().map(|x| x.as_str())) | |
| } | |
| } | |
| impl<'a> iter::FromIterator<&'a str> for SmolStr { | |
| fn from_iter<I: iter::IntoIterator<Item = &'a str>>(iter: I) -> SmolStr { | |
| build_from_str_iter(iter.into_iter()) | |
| } | |
| } | |
| impl AsRef<str> for SmolStr { | |
| #[inline(always)] | |
| fn as_ref(&self) -> &str { | |
| self.as_str() | |
| } | |
| } | |
| impl From<&str> for SmolStr { | |
| #[inline] | |
| fn from(s: &str) -> SmolStr { | |
| SmolStr::new(s) | |
| } | |
| } | |
| impl From<&mut str> for SmolStr { | |
| #[inline] | |
| fn from(s: &mut str) -> SmolStr { | |
| SmolStr::new(s) | |
| } | |
| } | |
| impl From<&String> for SmolStr { | |
| #[inline] | |
| fn from(s: &String) -> SmolStr { | |
| SmolStr::new(s) | |
| } | |
| } | |
| impl From<String> for SmolStr { | |
| #[inline(always)] | |
| fn from(text: String) -> Self { | |
| Self::new(text) | |
| } | |
| } | |
| impl From<Box<str>> for SmolStr { | |
| #[inline] | |
| fn from(s: Box<str>) -> SmolStr { | |
| SmolStr::new(s) | |
| } | |
| } | |
| impl From<Arc<str>> for SmolStr { | |
| #[inline] | |
| fn from(s: Arc<str>) -> SmolStr { | |
| let repr = Repr::new_on_stack(s.as_ref()).unwrap_or_else(|| Repr::Heap(s)); | |
| Self(repr) | |
| } | |
| } | |
| impl<'a> From<Cow<'a, str>> for SmolStr { | |
| #[inline] | |
| fn from(s: Cow<'a, str>) -> SmolStr { | |
| SmolStr::new(s) | |
| } | |
| } | |
| impl From<SmolStr> for Arc<str> { | |
| #[inline(always)] | |
| fn from(text: SmolStr) -> Self { | |
| match text.0 { | |
| Repr::Heap(data) => data, | |
| _ => text.as_str().into(), | |
| } | |
| } | |
| } | |
| impl From<SmolStr> for String { | |
| #[inline(always)] | |
| fn from(text: SmolStr) -> Self { | |
| text.as_str().into() | |
| } | |
| } | |
| impl Borrow<str> for SmolStr { | |
| #[inline(always)] | |
| fn borrow(&self) -> &str { | |
| self.as_str() | |
| } | |
| } | |
| impl FromStr for SmolStr { | |
| type Err = Infallible; | |
| #[inline] | |
| fn from_str(s: &str) -> Result<SmolStr, Self::Err> { | |
| Ok(SmolStr::from(s)) | |
| } | |
| } | |
| #[cfg(feature = "arbitrary")] | |
| impl<'a> arbitrary::Arbitrary<'a> for SmolStr { | |
| fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> Result<Self, arbitrary::Error> { | |
| let s = <&str>::arbitrary(u)?; | |
| Ok(SmolStr::new(s)) | |
| } | |
| } | |
| const INLINE_CAP: usize = 23; | |
| const N_NEWLINES: usize = 32; | |
| const N_SPACES: usize = 128; | |
| const WS: &str = | |
| "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n "; | |
| const _: () = { | |
| assert!(WS.len() == N_NEWLINES + N_SPACES); | |
| assert!(WS.as_bytes()[N_NEWLINES - 1] == b'\n'); | |
| assert!(WS.as_bytes()[N_NEWLINES] == b' '); | |
| }; | |
| #[derive(Clone, Copy, Debug)] | |
| #[repr(u8)] | |
| enum InlineSize { | |
| _V0 = 0, | |
| _V1, | |
| _V2, | |
| _V3, | |
| _V4, | |
| _V5, | |
| _V6, | |
| _V7, | |
| _V8, | |
| _V9, | |
| _V10, | |
| _V11, | |
| _V12, | |
| _V13, | |
| _V14, | |
| _V15, | |
| _V16, | |
| _V17, | |
| _V18, | |
| _V19, | |
| _V20, | |
| _V21, | |
| _V22, | |
| _V23, | |
| } | |
| #[derive(Clone, Debug)] | |
| enum Repr { | |
| Heap(Arc<str>), | |
| Static(&'static str), | |
| Inline { | |
| len: InlineSize, | |
| buf: [u8; INLINE_CAP], | |
| }, | |
| } | |
| impl Repr { | |
| /// This function tries to create a new Repr::Inline or Repr::Static | |
| /// If it isn't possible, this function returns None | |
| fn new_on_stack<T>(text: T) -> Option<Self> | |
| where | |
| T: AsRef<str>, | |
| { | |
| let text = text.as_ref(); | |
| let len = text.len(); | |
| if len <= INLINE_CAP { | |
| let mut buf = [0; INLINE_CAP]; | |
| buf[..len].copy_from_slice(text.as_bytes()); | |
| return Some(Repr::Inline { | |
| len: unsafe { transmute(len as u8) }, | |
| buf, | |
| }); | |
| } | |
| if len <= N_NEWLINES + N_SPACES { | |
| let bytes = text.as_bytes(); | |
| let possible_newline_count = cmp::min(len, N_NEWLINES); | |
| let newlines = bytes[..possible_newline_count] | |
| .iter() | |
| .take_while(|&&b| b == b'\n') | |
| .count(); | |
| let possible_space_count = len - newlines; | |
| if possible_space_count <= N_SPACES && bytes[newlines..].iter().all(|&b| b == b' ') { | |
| let spaces = possible_space_count; | |
| let substring = &WS[N_NEWLINES - newlines..N_NEWLINES + spaces]; | |
| return Some(Repr::Static(substring)); | |
| } | |
| } | |
| None | |
| } | |
| fn new<T>(text: T) -> Self | |
| where | |
| T: AsRef<str>, | |
| { | |
| Self::new_on_stack(text.as_ref()).unwrap_or_else(|| Repr::Heap(text.as_ref().into())) | |
| } | |
| #[inline(always)] | |
| fn len(&self) -> usize { | |
| match self { | |
| Repr::Heap(data) => data.len(), | |
| Repr::Static(data) => data.len(), | |
| Repr::Inline { len, .. } => *len as usize, | |
| } | |
| } | |
| #[inline(always)] | |
| fn is_empty(&self) -> bool { | |
| match self { | |
| Repr::Heap(data) => data.is_empty(), | |
| Repr::Static(data) => data.is_empty(), | |
| Repr::Inline { len, .. } => *len as u8 == 0, | |
| } | |
| } | |
| #[inline] | |
| fn as_str(&self) -> &str { | |
| match self { | |
| Repr::Heap(data) => data, | |
| Repr::Static(data) => data, | |
| Repr::Inline { len, buf } => { | |
| let len = *len as usize; | |
| let buf = &buf[..len]; | |
| unsafe { ::core::str::from_utf8_unchecked(buf) } | |
| } | |
| } | |
| } | |
| } | |
| /// Convert value to [`SmolStr`] using [`fmt::Display`], potentially without allocating. | |
| /// | |
| /// Almost identical to [`ToString`], but converts to `SmolStr` instead. | |
| pub trait ToSmolStr { | |
| fn to_smolstr(&self) -> SmolStr; | |
| } | |
| /// Formats arguments to a [`SmolStr`], potentially without allocating. | |
| /// | |
| /// See [`alloc::format!`] or [`format_args!`] for syntax documentation. | |
| #[macro_export] | |
| macro_rules! format_smolstr { | |
| ($($tt:tt)*) => {{ | |
| use ::core::fmt::Write; | |
| let mut w = $crate::Writer::new(); | |
| w.write_fmt(format_args!($($tt)*)).expect("a formatting trait implementation returned an error"); | |
| $crate::SmolStr::from(w) | |
| }}; | |
| } | |
| #[doc(hidden)] | |
| pub struct Writer { | |
| inline: [u8; INLINE_CAP], | |
| heap: String, | |
| len: usize, | |
| } | |
| impl Writer { | |
| #[must_use] | |
| pub const fn new() -> Self { | |
| Writer { | |
| inline: [0; INLINE_CAP], | |
| heap: String::new(), | |
| len: 0, | |
| } | |
| } | |
| } | |
| impl fmt::Write for Writer { | |
| fn write_str(&mut self, s: &str) -> fmt::Result { | |
| // if currently on the stack | |
| if self.len <= INLINE_CAP { | |
| let old_len = self.len; | |
| self.len += s.len(); | |
| // if the new length will fit on the stack (even if it fills it entirely) | |
| if self.len <= INLINE_CAP { | |
| self.inline[old_len..self.len].copy_from_slice(s.as_bytes()); | |
| return Ok(()); // skip the heap push below | |
| } | |
| self.heap.reserve(self.len); | |
| // copy existing inline bytes over to the heap | |
| unsafe { | |
| self.heap | |
| .as_mut_vec() | |
| .extend_from_slice(&self.inline[..old_len]); | |
| } | |
| } | |
| self.heap.push_str(s); | |
| Ok(()) | |
| } | |
| } | |
| impl From<Writer> for SmolStr { | |
| fn from(value: Writer) -> Self { | |
| SmolStr(if value.len <= INLINE_CAP { | |
| Repr::Inline { | |
| len: unsafe { transmute(value.len as u8) }, | |
| buf: value.inline, | |
| } | |
| } else { | |
| Repr::new(value.heap) | |
| }) | |
| } | |
| } | |
| impl<T> ToSmolStr for T | |
| where | |
| T: fmt::Display + ?Sized, | |
| { | |
| fn to_smolstr(&self) -> SmolStr { | |
| format_smolstr!("{}", self) | |
| } | |
| } | |
| #[cfg(feature = "serde")] | |
| mod serde { | |
| use alloc::{string::String, vec::Vec}; | |
| use core::fmt; | |
| use serde::de::{Deserializer, Error, Unexpected, Visitor}; | |
| use crate::SmolStr; | |
| // https://github.com/serde-rs/serde/blob/629802f2abfd1a54a6072992888fea7ca5bc209f/serde/src/private/de.rs#L56-L125 | |
| fn smol_str<'de: 'a, 'a, D>(deserializer: D) -> Result<SmolStr, D::Error> | |
| where | |
| D: Deserializer<'de>, | |
| { | |
| struct SmolStrVisitor; | |
| impl<'a> Visitor<'a> for SmolStrVisitor { | |
| type Value = SmolStr; | |
| fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result { | |
| formatter.write_str("a string") | |
| } | |
| fn visit_str<E>(self, v: &str) -> Result<Self::Value, E> | |
| where | |
| E: Error, | |
| { | |
| Ok(SmolStr::from(v)) | |
| } | |
| fn visit_borrowed_str<E>(self, v: &'a str) -> Result<Self::Value, E> | |
| where | |
| E: Error, | |
| { | |
| Ok(SmolStr::from(v)) | |
| } | |
| fn visit_string<E>(self, v: String) -> Result<Self::Value, E> | |
| where | |
| E: Error, | |
| { | |
| Ok(SmolStr::from(v)) | |
| } | |
| fn visit_bytes<E>(self, v: &[u8]) -> Result<Self::Value, E> | |
| where | |
| E: Error, | |
| { | |
| match core::str::from_utf8(v) { | |
| Ok(s) => Ok(SmolStr::from(s)), | |
| Err(_) => Err(Error::invalid_value(Unexpected::Bytes(v), &self)), | |
| } | |
| } | |
| fn visit_borrowed_bytes<E>(self, v: &'a [u8]) -> Result<Self::Value, E> | |
| where | |
| E: Error, | |
| { | |
| match core::str::from_utf8(v) { | |
| Ok(s) => Ok(SmolStr::from(s)), | |
| Err(_) => Err(Error::invalid_value(Unexpected::Bytes(v), &self)), | |
| } | |
| } | |
| fn visit_byte_buf<E>(self, v: Vec<u8>) -> Result<Self::Value, E> | |
| where | |
| E: Error, | |
| { | |
| match String::from_utf8(v) { | |
| Ok(s) => Ok(SmolStr::from(s)), | |
| Err(e) => Err(Error::invalid_value( | |
| Unexpected::Bytes(&e.into_bytes()), | |
| &self, | |
| )), | |
| } | |
| } | |
| } | |
| deserializer.deserialize_str(SmolStrVisitor) | |
| } | |
| impl serde::Serialize for SmolStr { | |
| fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> | |
| where | |
| S: serde::Serializer, | |
| { | |
| self.as_str().serialize(serializer) | |
| } | |
| } | |
| impl<'de> serde::Deserialize<'de> for SmolStr { | |
| fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> | |
| where | |
| D: serde::Deserializer<'de>, | |
| { | |
| smol_str(deserializer) | |
| } | |
| } | |
| } |