smol_str/
lib.rs

1#![cfg_attr(not(feature = "std"), no_std)]
2#![cfg_attr(docsrs, feature(doc_cfg))]
3#![debugger_visualizer(gdb_script_file = "gdb_smolstr_printer.py")]
4
5extern crate alloc;
6
7use alloc::{borrow::Cow, boxed::Box, string::String, sync::Arc};
8use core::{
9    borrow::Borrow,
10    cmp::{self, Ordering},
11    convert::Infallible,
12    fmt, hash, iter, mem, ops,
13    str::FromStr,
14};
15
16/// A `SmolStr` is a string type that has the following properties:
17///
18/// * `size_of::<SmolStr>() == 24` (therefore `== size_of::<String>()` on 64 bit platforms)
19/// * `Clone` is `O(1)` (no allocation)
20/// * Strings are stack-allocated if they are:
21///     * Up to 23 bytes long
22///     * Longer than 23 bytes, but substrings of `WS` (see below). Such strings consist
23///       solely of consecutive newlines, followed by consecutive spaces
24/// * If a string does not satisfy the aforementioned conditions, it is heap-allocated
25/// * Additionally, a `SmolStr` can be explicitly created from a `&'static str` without allocation
26///
27/// Unlike `String`, however, `SmolStr` is immutable. The primary use case for
28/// `SmolStr` is a good enough default storage for tokens of typical programming
29/// languages. Strings consisting of a series of newlines, followed by a series of
30/// whitespace are a typical pattern in computer programs because of indentation.
31/// Note that a specialized interner might be a better solution for some use cases.
32///
33/// `WS`: A string of 32 newlines followed by 128 spaces.
34pub struct SmolStr(Repr);
35
36impl SmolStr {
37    /// The maximum byte length of a string that can be stored inline
38    /// without heap allocation.
39    pub const INLINE_CAP: usize = INLINE_CAP;
40
41    /// Constructs an inline variant of `SmolStr`.
42    ///
43    /// This never allocates.
44    ///
45    /// # Panics
46    ///
47    /// Panics if `text.len() > `[`SmolStr::INLINE_CAP`].
48    #[inline]
49    pub const fn new_inline(text: &str) -> SmolStr {
50        assert!(text.len() <= INLINE_CAP); // avoids bounds checks in loop
51
52        let text = text.as_bytes();
53        let mut buf = [0; INLINE_CAP];
54        let mut i = 0;
55        while i < text.len() {
56            buf[i] = text[i];
57            i += 1
58        }
59        SmolStr(Repr::Inline {
60            // SAFETY: We know that `len` is less than or equal to the maximum value of `InlineSize`
61            // as we asserted it.
62            len: unsafe { InlineSize::transmute_from_u8(text.len() as u8) },
63            buf,
64        })
65    }
66
67    /// Constructs a `SmolStr` from a statically allocated string.
68    ///
69    /// This never allocates.
70    #[inline(always)]
71    pub const fn new_static(text: &'static str) -> SmolStr {
72        // NOTE: this never uses the inline storage; if a canonical
73        // representation is needed, we could check for `len() < INLINE_CAP`
74        // and call `new_inline`, but this would mean an extra branch.
75        SmolStr(Repr::Static(text))
76    }
77
78    /// Constructs a `SmolStr` from a `str`, heap-allocating if necessary.
79    #[inline(always)]
80    pub fn new(text: impl AsRef<str>) -> SmolStr {
81        SmolStr(Repr::new(text.as_ref()))
82    }
83
84    /// Returns a `&str` slice of this `SmolStr`.
85    #[inline(always)]
86    pub fn as_str(&self) -> &str {
87        self.0.as_str()
88    }
89
90    /// Returns the length of `self` in bytes.
91    #[inline(always)]
92    pub fn len(&self) -> usize {
93        self.0.len()
94    }
95
96    /// Returns `true` if `self` has a length of zero bytes.
97    #[inline(always)]
98    pub fn is_empty(&self) -> bool {
99        self.0.is_empty()
100    }
101
102    /// Returns `true` if `self` is heap-allocated.
103    #[inline(always)]
104    pub const fn is_heap_allocated(&self) -> bool {
105        matches!(self.0, Repr::Heap(..))
106    }
107
108    /// Constructs a `SmolStr` from a byte slice, returning an error if the slice is not valid
109    /// UTF-8.
110    #[inline]
111    pub fn from_utf8(bytes: &[u8]) -> Result<SmolStr, core::str::Utf8Error> {
112        core::str::from_utf8(bytes).map(SmolStr::new)
113    }
114
115    /// Constructs a `SmolStr` from a byte slice without checking that the bytes are valid UTF-8.
116    ///
117    /// # Safety
118    ///
119    /// `bytes` must be valid UTF-8.
120    #[inline]
121    pub unsafe fn from_utf8_unchecked(bytes: &[u8]) -> SmolStr {
122        // SAFETY: caller guarantees bytes are valid UTF-8
123        SmolStr::new(unsafe { core::str::from_utf8_unchecked(bytes) })
124    }
125}
126
127impl Clone for SmolStr {
128    #[inline]
129    fn clone(&self) -> Self {
130        // hint for faster inline / slower heap clones
131        #[cold]
132        #[inline(never)]
133        fn cold_clone(v: &SmolStr) -> SmolStr {
134            SmolStr(v.0.clone())
135        }
136
137        if self.is_heap_allocated() {
138            return cold_clone(self);
139        }
140
141        // SAFETY: The non-heap variants (`Repr::Inline` and `Repr::Static`) contain only
142        // `Copy` data (a `[u8; 23]` + `InlineSize` enum, or a `&'static str` fat pointer)
143        // and carry no drop glue, so a raw `ptr::read` bitwise copy is sound.
144        // The heap variant (`Repr::Heap`) is excluded above.
145        unsafe { core::ptr::read(self as *const SmolStr) }
146    }
147}
148
149impl Default for SmolStr {
150    #[inline(always)]
151    fn default() -> SmolStr {
152        SmolStr(Repr::Inline { len: InlineSize::_V0, buf: [0; INLINE_CAP] })
153    }
154}
155
156impl ops::Deref for SmolStr {
157    type Target = str;
158
159    #[inline(always)]
160    fn deref(&self) -> &str {
161        self.as_str()
162    }
163}
164
165// region: PartialEq implementations
166
167impl Eq for SmolStr {}
168impl PartialEq<SmolStr> for SmolStr {
169    fn eq(&self, other: &SmolStr) -> bool {
170        match (&self.0, &other.0) {
171            (Repr::Inline { len: l_len, buf: l_buf }, Repr::Inline { len: r_len, buf: r_buf }) => {
172                l_len == r_len && l_buf == r_buf
173            }
174            _ => self.as_str() == other.as_str(),
175        }
176    }
177}
178
179impl PartialEq<str> for SmolStr {
180    #[inline(always)]
181    fn eq(&self, other: &str) -> bool {
182        self.as_str() == other
183    }
184}
185
186impl PartialEq<SmolStr> for str {
187    #[inline(always)]
188    fn eq(&self, other: &SmolStr) -> bool {
189        other == self
190    }
191}
192
193impl<'a> PartialEq<&'a str> for SmolStr {
194    #[inline(always)]
195    fn eq(&self, other: &&'a str) -> bool {
196        self == *other
197    }
198}
199
200impl PartialEq<SmolStr> for &str {
201    #[inline(always)]
202    fn eq(&self, other: &SmolStr) -> bool {
203        *self == other
204    }
205}
206
207impl PartialEq<String> for SmolStr {
208    #[inline(always)]
209    fn eq(&self, other: &String) -> bool {
210        self.as_str() == other
211    }
212}
213
214impl PartialEq<SmolStr> for String {
215    #[inline(always)]
216    fn eq(&self, other: &SmolStr) -> bool {
217        other == self
218    }
219}
220
221impl<'a> PartialEq<&'a String> for SmolStr {
222    #[inline(always)]
223    fn eq(&self, other: &&'a String) -> bool {
224        self == *other
225    }
226}
227
228impl PartialEq<SmolStr> for &String {
229    #[inline(always)]
230    fn eq(&self, other: &SmolStr) -> bool {
231        *self == other
232    }
233}
234// endregion: PartialEq implementations
235
236impl Ord for SmolStr {
237    fn cmp(&self, other: &SmolStr) -> Ordering {
238        self.as_str().cmp(other.as_str())
239    }
240}
241
242impl PartialOrd for SmolStr {
243    fn partial_cmp(&self, other: &SmolStr) -> Option<Ordering> {
244        Some(self.cmp(other))
245    }
246}
247
248impl PartialOrd<str> for SmolStr {
249    fn partial_cmp(&self, other: &str) -> Option<Ordering> {
250        Some(self.as_str().cmp(other))
251    }
252}
253
254impl<'a> PartialOrd<&'a str> for SmolStr {
255    fn partial_cmp(&self, other: &&'a str) -> Option<Ordering> {
256        Some(self.as_str().cmp(*other))
257    }
258}
259
260impl PartialOrd<SmolStr> for &str {
261    fn partial_cmp(&self, other: &SmolStr) -> Option<Ordering> {
262        Some((*self).cmp(other.as_str()))
263    }
264}
265
266impl PartialOrd<String> for SmolStr {
267    fn partial_cmp(&self, other: &String) -> Option<Ordering> {
268        Some(self.as_str().cmp(other.as_str()))
269    }
270}
271
272impl PartialOrd<SmolStr> for String {
273    fn partial_cmp(&self, other: &SmolStr) -> Option<Ordering> {
274        Some(self.as_str().cmp(other.as_str()))
275    }
276}
277
278impl<'a> PartialOrd<&'a String> for SmolStr {
279    fn partial_cmp(&self, other: &&'a String) -> Option<Ordering> {
280        Some(self.as_str().cmp(other.as_str()))
281    }
282}
283
284impl PartialOrd<SmolStr> for &String {
285    fn partial_cmp(&self, other: &SmolStr) -> Option<Ordering> {
286        Some(self.as_str().cmp(other.as_str()))
287    }
288}
289
290impl hash::Hash for SmolStr {
291    fn hash<H: hash::Hasher>(&self, hasher: &mut H) {
292        self.as_str().hash(hasher);
293    }
294}
295
296impl fmt::Debug for SmolStr {
297    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
298        fmt::Debug::fmt(self.as_str(), f)
299    }
300}
301
302impl fmt::Display for SmolStr {
303    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
304        fmt::Display::fmt(self.as_str(), f)
305    }
306}
307
308impl iter::FromIterator<char> for SmolStr {
309    fn from_iter<I: iter::IntoIterator<Item = char>>(iter: I) -> SmolStr {
310        from_char_iter(iter.into_iter())
311    }
312}
313
314#[inline]
315fn from_char_iter(iter: impl Iterator<Item = char>) -> SmolStr {
316    from_buf_and_chars([0; _], 0, iter)
317}
318
319fn from_buf_and_chars(
320    mut buf: [u8; INLINE_CAP],
321    buf_len: usize,
322    mut iter: impl Iterator<Item = char>,
323) -> SmolStr {
324    let min_size = iter.size_hint().0 + buf_len;
325    if min_size > INLINE_CAP {
326        let heap: String =
327            core::str::from_utf8(&buf[..buf_len]).unwrap().chars().chain(iter).collect();
328        if heap.len() <= INLINE_CAP {
329            // size hint lied
330            return SmolStr::new_inline(&heap);
331        }
332        return SmolStr(Repr::Heap(heap.into_boxed_str().into()));
333    }
334    let mut len = buf_len;
335    while let Some(ch) = iter.next() {
336        let size = ch.len_utf8();
337        if size + len > INLINE_CAP {
338            let (min_remaining, _) = iter.size_hint();
339            let mut heap = String::with_capacity(size + len + min_remaining);
340            heap.push_str(core::str::from_utf8(&buf[..len]).unwrap());
341            heap.push(ch);
342            heap.extend(iter);
343            return SmolStr(Repr::Heap(heap.into_boxed_str().into()));
344        }
345        ch.encode_utf8(&mut buf[len..]);
346        len += size;
347    }
348    SmolStr(Repr::Inline {
349        // SAFETY: We know that `len` is less than or equal to the maximum value of `InlineSize`
350        // as we otherwise return early.
351        len: unsafe { InlineSize::transmute_from_u8(len as u8) },
352        buf,
353    })
354}
355
356fn build_from_str_iter<T>(mut iter: impl Iterator<Item = T>) -> SmolStr
357where
358    T: AsRef<str>,
359    String: iter::Extend<T>,
360{
361    let mut len = 0;
362    let mut buf = [0u8; INLINE_CAP];
363    while let Some(slice) = iter.next() {
364        let slice = slice.as_ref();
365        let size = slice.len();
366        if size + len > INLINE_CAP {
367            let mut heap = String::with_capacity(size + len);
368            heap.push_str(core::str::from_utf8(&buf[..len]).unwrap());
369            heap.push_str(slice);
370            heap.extend(iter);
371            return SmolStr(Repr::Heap(heap.into_boxed_str().into()));
372        }
373        buf[len..][..size].copy_from_slice(slice.as_bytes());
374        len += size;
375    }
376    SmolStr(Repr::Inline {
377        // SAFETY: We know that `len` is less than or equal to the maximum value of `InlineSize`
378        // as we otherwise return early.
379        len: unsafe { InlineSize::transmute_from_u8(len as u8) },
380        buf,
381    })
382}
383
384impl iter::FromIterator<String> for SmolStr {
385    fn from_iter<I: iter::IntoIterator<Item = String>>(iter: I) -> SmolStr {
386        build_from_str_iter(iter.into_iter())
387    }
388}
389
390impl<'a> iter::FromIterator<&'a String> for SmolStr {
391    fn from_iter<I: iter::IntoIterator<Item = &'a String>>(iter: I) -> SmolStr {
392        SmolStr::from_iter(iter.into_iter().map(|x| x.as_str()))
393    }
394}
395
396impl<'a> iter::FromIterator<&'a str> for SmolStr {
397    fn from_iter<I: iter::IntoIterator<Item = &'a str>>(iter: I) -> SmolStr {
398        build_from_str_iter(iter.into_iter())
399    }
400}
401
402impl AsRef<str> for SmolStr {
403    #[inline(always)]
404    fn as_ref(&self) -> &str {
405        self.as_str()
406    }
407}
408
409impl AsRef<[u8]> for SmolStr {
410    #[inline(always)]
411    fn as_ref(&self) -> &[u8] {
412        self.as_str().as_bytes()
413    }
414}
415
416#[cfg(feature = "std")]
417#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
418impl AsRef<std::ffi::OsStr> for SmolStr {
419    #[inline(always)]
420    fn as_ref(&self) -> &std::ffi::OsStr {
421        AsRef::<std::ffi::OsStr>::as_ref(self.as_str())
422    }
423}
424
425#[cfg(feature = "std")]
426#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
427impl AsRef<std::path::Path> for SmolStr {
428    #[inline(always)]
429    fn as_ref(&self) -> &std::path::Path {
430        AsRef::<std::path::Path>::as_ref(self.as_str())
431    }
432}
433
434impl From<char> for SmolStr {
435    #[inline]
436    fn from(c: char) -> SmolStr {
437        let mut buf = [0; INLINE_CAP];
438        let len = c.len_utf8();
439        c.encode_utf8(&mut buf);
440        SmolStr(Repr::Inline {
441            // SAFETY: A char is at most 4 bytes, which is always <= INLINE_CAP (23).
442            len: unsafe { InlineSize::transmute_from_u8(len as u8) },
443            buf,
444        })
445    }
446}
447
448impl From<&str> for SmolStr {
449    #[inline]
450    fn from(s: &str) -> SmolStr {
451        SmolStr::new(s)
452    }
453}
454
455impl From<&mut str> for SmolStr {
456    #[inline]
457    fn from(s: &mut str) -> SmolStr {
458        SmolStr::new(s)
459    }
460}
461
462impl From<&String> for SmolStr {
463    #[inline]
464    fn from(s: &String) -> SmolStr {
465        SmolStr::new(s)
466    }
467}
468
469impl From<String> for SmolStr {
470    #[inline(always)]
471    fn from(text: String) -> Self {
472        Self::new(text)
473    }
474}
475
476impl From<Box<str>> for SmolStr {
477    #[inline]
478    fn from(s: Box<str>) -> SmolStr {
479        SmolStr::new(s)
480    }
481}
482
483impl From<Arc<str>> for SmolStr {
484    #[inline]
485    fn from(s: Arc<str>) -> SmolStr {
486        let repr = Repr::new_on_stack(s.as_ref()).unwrap_or(Repr::Heap(s));
487        Self(repr)
488    }
489}
490
491impl<'a> From<Cow<'a, str>> for SmolStr {
492    #[inline]
493    fn from(s: Cow<'a, str>) -> SmolStr {
494        SmolStr::new(s)
495    }
496}
497
498impl From<SmolStr> for Arc<str> {
499    #[inline(always)]
500    fn from(text: SmolStr) -> Self {
501        match text.0 {
502            Repr::Heap(data) => data,
503            _ => text.as_str().into(),
504        }
505    }
506}
507
508impl From<SmolStr> for String {
509    #[inline(always)]
510    fn from(text: SmolStr) -> Self {
511        text.as_str().into()
512    }
513}
514
515impl Borrow<str> for SmolStr {
516    #[inline(always)]
517    fn borrow(&self) -> &str {
518        self.as_str()
519    }
520}
521
522impl FromStr for SmolStr {
523    type Err = Infallible;
524
525    #[inline]
526    fn from_str(s: &str) -> Result<SmolStr, Self::Err> {
527        Ok(SmolStr::from(s))
528    }
529}
530
531const INLINE_CAP: usize = InlineSize::_V23 as usize;
532const N_NEWLINES: usize = 32;
533const N_SPACES: usize = 128;
534const 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                                                                                                                                ";
535const _: () = {
536    assert!(WS.len() == N_NEWLINES + N_SPACES);
537    assert!(WS.as_bytes()[N_NEWLINES - 1] == b'\n');
538    assert!(WS.as_bytes()[N_NEWLINES] == b' ');
539};
540
541/// A [`u8`] with a bunch of niches.
542#[derive(Clone, Copy, Debug, PartialEq)]
543#[repr(u8)]
544enum InlineSize {
545    _V0 = 0,
546    _V1,
547    _V2,
548    _V3,
549    _V4,
550    _V5,
551    _V6,
552    _V7,
553    _V8,
554    _V9,
555    _V10,
556    _V11,
557    _V12,
558    _V13,
559    _V14,
560    _V15,
561    _V16,
562    _V17,
563    _V18,
564    _V19,
565    _V20,
566    _V21,
567    _V22,
568    _V23,
569}
570
571impl InlineSize {
572    /// # Safety
573    ///
574    /// `value` must be in the range `0..=23` (i.e. a valid `InlineSize` discriminant).
575    /// Values outside this range would produce an invalid enum discriminant, which is UB.
576    #[inline(always)]
577    const unsafe fn transmute_from_u8(value: u8) -> Self {
578        debug_assert!(value <= InlineSize::_V23 as u8);
579        // SAFETY: The caller guarantees `value` is a valid discriminant for this
580        // `#[repr(u8)]` enum (0..=23), so the transmute produces a valid `InlineSize`.
581        unsafe { mem::transmute::<u8, Self>(value) }
582    }
583}
584
585#[derive(Clone, Debug)]
586enum Repr {
587    Inline { len: InlineSize, buf: [u8; INLINE_CAP] },
588    Static(&'static str),
589    Heap(Arc<str>),
590}
591
592impl Repr {
593    /// This function tries to create a new Repr::Inline or Repr::Static
594    /// If it isn't possible, this function returns None
595    fn new_on_stack<T>(text: T) -> Option<Self>
596    where
597        T: AsRef<str>,
598    {
599        let text = text.as_ref();
600
601        let len = text.len();
602        if len <= INLINE_CAP {
603            let mut buf = [0; INLINE_CAP];
604            buf[..len].copy_from_slice(text.as_bytes());
605            return Some(Repr::Inline {
606                // SAFETY: We know that `len` is less than or equal to the maximum value of `InlineSize`
607                len: unsafe { InlineSize::transmute_from_u8(len as u8) },
608                buf,
609            });
610        }
611
612        if len <= N_NEWLINES + N_SPACES {
613            let bytes = text.as_bytes();
614            let possible_newline_count = cmp::min(len, N_NEWLINES);
615            let newlines =
616                bytes[..possible_newline_count].iter().take_while(|&&b| b == b'\n').count();
617            let possible_space_count = len - newlines;
618            if possible_space_count <= N_SPACES && bytes[newlines..].iter().all(|&b| b == b' ') {
619                let spaces = possible_space_count;
620                let substring = &WS[N_NEWLINES - newlines..N_NEWLINES + spaces];
621                return Some(Repr::Static(substring));
622            }
623        }
624        None
625    }
626
627    fn new(text: &str) -> Self {
628        Self::new_on_stack(text).unwrap_or_else(|| Repr::Heap(Arc::from(text)))
629    }
630
631    #[inline(always)]
632    fn len(&self) -> usize {
633        match self {
634            Repr::Heap(data) => data.len(),
635            Repr::Static(data) => data.len(),
636            Repr::Inline { len, .. } => *len as usize,
637        }
638    }
639
640    #[inline(always)]
641    fn is_empty(&self) -> bool {
642        match self {
643            Repr::Heap(data) => data.is_empty(),
644            Repr::Static(data) => data.is_empty(),
645            &Repr::Inline { len, .. } => len as u8 == 0,
646        }
647    }
648
649    #[inline]
650    fn as_str(&self) -> &str {
651        match self {
652            Repr::Heap(data) => data,
653            Repr::Static(data) => data,
654            Repr::Inline { len, buf } => {
655                let len = *len as usize;
656                // SAFETY: `len` is an `InlineSize` discriminant (0..=23) which is always
657                // <= INLINE_CAP (23), so `..len` is always in bounds of `buf: [u8; 23]`.
658                let buf = unsafe { buf.get_unchecked(..len) };
659                // SAFETY: All constructors that produce `Repr::Inline` copy from valid
660                // UTF-8 sources (`&str` or char encoding), so `buf[..len]` is valid UTF-8.
661                unsafe { ::core::str::from_utf8_unchecked(buf) }
662            }
663        }
664    }
665}
666
667/// Convert value to [`SmolStr`] using [`fmt::Display`], potentially without allocating.
668///
669/// Almost identical to [`ToString`], but converts to `SmolStr` instead.
670pub trait ToSmolStr {
671    fn to_smolstr(&self) -> SmolStr;
672}
673
674/// [`str`] methods producing [`SmolStr`]s.
675pub trait StrExt: private::Sealed {
676    /// Returns the lowercase equivalent of this string slice as a new [`SmolStr`],
677    /// potentially without allocating.
678    ///
679    /// See [`str::to_lowercase`].
680    #[must_use = "this returns a new SmolStr without modifying the original"]
681    fn to_lowercase_smolstr(&self) -> SmolStr;
682
683    /// Returns the uppercase equivalent of this string slice as a new [`SmolStr`],
684    /// potentially without allocating.
685    ///
686    /// See [`str::to_uppercase`].
687    #[must_use = "this returns a new SmolStr without modifying the original"]
688    fn to_uppercase_smolstr(&self) -> SmolStr;
689
690    /// Returns the ASCII lowercase equivalent of this string slice as a new [`SmolStr`],
691    /// potentially without allocating.
692    ///
693    /// See [`str::to_ascii_lowercase`].
694    #[must_use = "this returns a new SmolStr without modifying the original"]
695    fn to_ascii_lowercase_smolstr(&self) -> SmolStr;
696
697    /// Returns the ASCII uppercase equivalent of this string slice as a new [`SmolStr`],
698    /// potentially without allocating.
699    ///
700    /// See [`str::to_ascii_uppercase`].
701    #[must_use = "this returns a new SmolStr without modifying the original"]
702    fn to_ascii_uppercase_smolstr(&self) -> SmolStr;
703
704    /// Replaces all matches of a &str with another &str returning a new [`SmolStr`],
705    /// potentially without allocating.
706    ///
707    /// See [`str::replace`].
708    #[must_use = "this returns a new SmolStr without modifying the original"]
709    fn replace_smolstr(&self, from: &str, to: &str) -> SmolStr;
710
711    /// Replaces first N matches of a &str with another &str returning a new [`SmolStr`],
712    /// potentially without allocating.
713    ///
714    /// See [`str::replacen`].
715    #[must_use = "this returns a new SmolStr without modifying the original"]
716    fn replacen_smolstr(&self, from: &str, to: &str, count: usize) -> SmolStr;
717}
718
719impl StrExt for str {
720    #[inline]
721    fn to_lowercase_smolstr(&self) -> SmolStr {
722        let len = self.len();
723        if len <= INLINE_CAP {
724            // SAFETY: `to_ascii_lowercase` always converts ASCII to ASCII
725            let (buf, rest) = unsafe { inline_convert_while_ascii(self, u8::to_ascii_lowercase) };
726            from_buf_and_chars(buf, len - rest.len(), rest.chars().flat_map(|c| c.to_lowercase()))
727        } else {
728            self.to_lowercase().into()
729        }
730    }
731
732    #[inline]
733    fn to_uppercase_smolstr(&self) -> SmolStr {
734        let len = self.len();
735        if len <= INLINE_CAP {
736            // SAFETY: `to_ascii_uppercase` always converts ASCII to ASCII
737            let (buf, rest) = unsafe { inline_convert_while_ascii(self, u8::to_ascii_uppercase) };
738            from_buf_and_chars(buf, len - rest.len(), rest.chars().flat_map(|c| c.to_uppercase()))
739        } else {
740            self.to_uppercase().into()
741        }
742    }
743
744    #[inline]
745    fn to_ascii_lowercase_smolstr(&self) -> SmolStr {
746        let len = self.len();
747        if len <= INLINE_CAP {
748            let mut buf = [0u8; INLINE_CAP];
749            buf[..len].copy_from_slice(self.as_bytes());
750            buf[..len].make_ascii_lowercase();
751            SmolStr(Repr::Inline {
752                // SAFETY: `len` is guarded to be <= INLINE_CAP (23), a valid `InlineSize` discriminant.
753                len: unsafe { InlineSize::transmute_from_u8(len as u8) },
754                buf,
755            })
756        } else {
757            self.to_ascii_lowercase().into()
758        }
759    }
760
761    #[inline]
762    fn to_ascii_uppercase_smolstr(&self) -> SmolStr {
763        let len = self.len();
764        if len <= INLINE_CAP {
765            let mut buf = [0u8; INLINE_CAP];
766            buf[..len].copy_from_slice(self.as_bytes());
767            buf[..len].make_ascii_uppercase();
768            SmolStr(Repr::Inline {
769                // SAFETY: `len` is guarded to be <= INLINE_CAP (23), a valid `InlineSize` discriminant.
770                len: unsafe { InlineSize::transmute_from_u8(len as u8) },
771                buf,
772            })
773        } else {
774            self.to_ascii_uppercase().into()
775        }
776    }
777
778    #[inline]
779    fn replace_smolstr(&self, from: &str, to: &str) -> SmolStr {
780        self.replacen_smolstr(from, to, usize::MAX)
781    }
782
783    #[inline]
784    fn replacen_smolstr(&self, from: &str, to: &str, mut count: usize) -> SmolStr {
785        // Fast path for replacing a single ASCII character with another inline.
786        if let [from_u8] = from.as_bytes()
787            && let [to_u8] = to.as_bytes()
788        {
789            // SAFETY: `from` and `to` are single-byte `&str`s. In valid UTF-8, a single-byte
790            // code unit is always in the range 0x00..=0x7F (i.e. ASCII). The closure only
791            // replaces the matching ASCII byte with another ASCII byte, and returns all
792            // other bytes unchanged, so UTF-8 validity is preserved.
793            return if self.len() <= count {
794                unsafe { replacen_1_ascii(self, |b| if b == from_u8 { *to_u8 } else { *b }) }
795            } else {
796                unsafe {
797                    replacen_1_ascii(self, |b| {
798                        if b == from_u8 && count != 0 {
799                            count -= 1;
800                            *to_u8
801                        } else {
802                            *b
803                        }
804                    })
805                }
806            };
807        }
808
809        let mut result = SmolStrBuilder::new();
810        let mut last_end = 0;
811        for (start, part) in self.match_indices(from).take(count) {
812            // SAFETY: `start` is guaranteed to be within the bounds of `self` as per
813            // `match_indices` and last_end is always less than or equal to `start`
814            result.push_str(unsafe { self.get_unchecked(last_end..start) });
815            result.push_str(to);
816            last_end = start + part.len();
817        }
818        // SAFETY: `self.len()` is guaranteed to be within the bounds of `self` and last_end is
819        // always less than or equal to `self.len()`
820        result.push_str(unsafe { self.get_unchecked(last_end..self.len()) });
821        SmolStr::from(result)
822    }
823}
824
825/// # Safety
826///
827/// `map` must satisfy: for every byte `b` in `src`, if `b <= 0x7F` (ASCII) then `map(b)` must
828/// also be `<= 0x7F` (ASCII). If `b > 0x7F` (part of a multi-byte UTF-8 sequence), `map` must
829/// return `b` unchanged. This ensures the output is valid UTF-8 whenever the input is.
830#[inline]
831unsafe fn replacen_1_ascii(src: &str, mut map: impl FnMut(&u8) -> u8) -> SmolStr {
832    if src.len() <= INLINE_CAP {
833        let mut buf = [0u8; INLINE_CAP];
834        for (idx, b) in src.as_bytes().iter().enumerate() {
835            buf[idx] = map(b);
836        }
837        SmolStr(Repr::Inline {
838            // SAFETY: `src` is a `&str` so `src.len()` <= INLINE_CAP <= 23, which is a
839            // valid `InlineSize` discriminant.
840            len: unsafe { InlineSize::transmute_from_u8(src.len() as u8) },
841            buf,
842        })
843    } else {
844        let out = src.as_bytes().iter().map(map).collect();
845        // SAFETY: The caller guarantees `map` only substitutes ASCII bytes with ASCII
846        // bytes and leaves multi-byte UTF-8 continuation bytes untouched, so the
847        // output byte sequence is valid UTF-8.
848        unsafe { String::from_utf8_unchecked(out).into() }
849    }
850}
851
852/// Inline version of std fn `convert_while_ascii`. `s` must have len <= 23.
853///
854/// # Safety
855///
856/// If the input to `convert` is valid ASCII (<= 0x7F),
857/// then the output must be as well.
858#[inline]
859unsafe fn inline_convert_while_ascii(s: &str, convert: fn(&u8) -> u8) -> ([u8; INLINE_CAP], &str) {
860    // Process the input in chunks of 16 bytes to enable auto-vectorization.
861    // Previously the chunk size depended on the size of `usize`,
862    // but on 32-bit platforms with sse or neon is also the better choice.
863    // The only downside on other platforms would be a bit more loop-unrolling.
864    const N: usize = 16;
865
866    debug_assert!(s.len() <= INLINE_CAP, "only for inline-able strings");
867
868    let mut slice = s.as_bytes();
869    let mut out = [0u8; INLINE_CAP];
870    let mut out_slice = &mut out[..slice.len()];
871    let mut is_ascii = [false; N];
872
873    while slice.len() >= N {
874        // SAFETY: The loop condition guarantees `slice.len() >= N`, so `..N` is in bounds.
875        let chunk = unsafe { slice.get_unchecked(..N) };
876        // SAFETY: `out_slice` starts with the same length as `slice` (both derived from
877        // `s.len()`) and both are advanced by the same offset `N` each iteration, so
878        // `out_slice.len() >= N` holds whenever `slice.len() >= N`.
879        let out_chunk = unsafe { out_slice.get_unchecked_mut(..N) };
880
881        for j in 0..N {
882            is_ascii[j] = chunk[j] <= 127;
883        }
884
885        // Auto-vectorization for this check is a bit fragile, sum and comparing against the chunk
886        // size gives the best result, specifically a pmovmsk instruction on x86.
887        // See https://github.com/llvm/llvm-project/issues/96395 for why llvm currently does not
888        // currently recognize other similar idioms.
889        if is_ascii.iter().map(|x| *x as u8).sum::<u8>() as usize != N {
890            break;
891        }
892
893        for j in 0..N {
894            out_chunk[j] = convert(&chunk[j]);
895        }
896
897        // SAFETY: Same reasoning as above — both slices have len >= N at this point.
898        slice = unsafe { slice.get_unchecked(N..) };
899        out_slice = unsafe { out_slice.get_unchecked_mut(N..) };
900    }
901
902    // handle the remainder as individual bytes
903    while !slice.is_empty() {
904        let byte = slice[0];
905        if byte > 127 {
906            break;
907        }
908        // SAFETY: `out_slice` is always the same length as `slice` (both start equal and
909        // are advanced by 1 together), and `slice` is non-empty per the loop condition,
910        // so index 0 and `1..` are in bounds for both.
911        unsafe {
912            *out_slice.get_unchecked_mut(0) = convert(&byte);
913        }
914        slice = unsafe { slice.get_unchecked(1..) };
915        out_slice = unsafe { out_slice.get_unchecked_mut(1..) };
916    }
917
918    unsafe {
919        // SAFETY: We only advanced past bytes that satisfy `b <= 127`, i.e. ASCII bytes.
920        // In UTF-8, ASCII bytes (0x00..=0x7F) are always single-byte code points and
921        // never appear as continuation bytes, so the remaining `slice` starts at a valid
922        // UTF-8 char boundary.
923        let rest = core::str::from_utf8_unchecked(slice);
924        (out, rest)
925    }
926}
927
928impl<T> ToSmolStr for T
929where
930    T: fmt::Display + ?Sized,
931{
932    fn to_smolstr(&self) -> SmolStr {
933        format_smolstr!("{}", self)
934    }
935}
936
937mod private {
938    /// No downstream impls allowed.
939    pub trait Sealed {}
940    impl Sealed for str {}
941}
942
943/// Formats arguments to a [`SmolStr`], potentially without allocating.
944///
945/// See [`alloc::format!`] or [`format_args!`] for syntax documentation.
946#[macro_export]
947macro_rules! format_smolstr {
948    ($($tt:tt)*) => {{
949        let mut w = $crate::SmolStrBuilder::new();
950        ::core::fmt::Write::write_fmt(&mut w, format_args!($($tt)*)).expect("a formatting trait implementation returned an error");
951        w.finish()
952    }};
953}
954
955/// A builder that can be used to efficiently build a [`SmolStr`].
956///
957/// This won't allocate if the final string fits into the inline buffer.
958#[derive(Clone, Default, Debug)]
959pub struct SmolStrBuilder(SmolStrBuilderRepr);
960
961impl PartialEq for SmolStrBuilder {
962    fn eq(&self, other: &Self) -> bool {
963        self.as_str() == other.as_str()
964    }
965}
966
967impl Eq for SmolStrBuilder {}
968
969#[derive(Clone, Debug)]
970enum SmolStrBuilderRepr {
971    Inline { len: usize, buf: [u8; INLINE_CAP] },
972    Heap(String),
973}
974
975impl Default for SmolStrBuilderRepr {
976    #[inline]
977    fn default() -> Self {
978        SmolStrBuilderRepr::Inline { buf: [0; INLINE_CAP], len: 0 }
979    }
980}
981
982impl SmolStrBuilder {
983    /// Creates a new empty [`SmolStrBuilder`].
984    #[must_use]
985    pub const fn new() -> Self {
986        Self(SmolStrBuilderRepr::Inline { buf: [0; INLINE_CAP], len: 0 })
987    }
988
989    /// Creates a new empty [`SmolStrBuilder`] with at least the specified capacity.
990    ///
991    /// If `capacity` is less than or equal to [`SmolStr::INLINE_CAP`], the builder
992    /// will use inline storage and not allocate. Otherwise, it will pre-allocate a
993    /// heap buffer of the requested capacity.
994    #[must_use]
995    pub fn with_capacity(capacity: usize) -> Self {
996        if capacity <= INLINE_CAP {
997            Self::new()
998        } else {
999            Self(SmolStrBuilderRepr::Heap(String::with_capacity(capacity)))
1000        }
1001    }
1002
1003    /// Returns the number of bytes accumulated in the builder so far.
1004    #[inline]
1005    pub fn len(&self) -> usize {
1006        match &self.0 {
1007            SmolStrBuilderRepr::Inline { len, .. } => *len,
1008            SmolStrBuilderRepr::Heap(heap) => heap.len(),
1009        }
1010    }
1011
1012    /// Returns `true` if the builder has a length of zero bytes.
1013    #[inline]
1014    pub fn is_empty(&self) -> bool {
1015        match &self.0 {
1016            SmolStrBuilderRepr::Inline { len, .. } => *len == 0,
1017            SmolStrBuilderRepr::Heap(heap) => heap.is_empty(),
1018        }
1019    }
1020
1021    /// Returns a `&str` slice of the builder's current contents.
1022    #[inline]
1023    pub fn as_str(&self) -> &str {
1024        match &self.0 {
1025            SmolStrBuilderRepr::Inline { len, buf } => {
1026                // SAFETY: `buf[..*len]` was built by prior `push`/`push_str` calls
1027                // that only wrote valid UTF-8, and `*len <= INLINE_CAP` is maintained
1028                // by the inline branch logic.
1029                unsafe { core::str::from_utf8_unchecked(&buf[..*len]) }
1030            }
1031            SmolStrBuilderRepr::Heap(heap) => heap.as_str(),
1032        }
1033    }
1034
1035    /// Builds a [`SmolStr`] from `self`.
1036    #[must_use]
1037    pub fn finish(self) -> SmolStr {
1038        SmolStr(match self.0 {
1039            SmolStrBuilderRepr::Inline { len, buf } => {
1040                debug_assert!(len <= INLINE_CAP);
1041                Repr::Inline {
1042                    // SAFETY: We know that `value.len` is less than or equal to the maximum value of `InlineSize`
1043                    len: unsafe { InlineSize::transmute_from_u8(len as u8) },
1044                    buf,
1045                }
1046            }
1047            SmolStrBuilderRepr::Heap(heap) => Repr::new(&heap),
1048        })
1049    }
1050
1051    /// Appends the given [`char`] to the end of `self`'s buffer.
1052    pub fn push(&mut self, c: char) {
1053        match &mut self.0 {
1054            SmolStrBuilderRepr::Inline { len, buf } => {
1055                let char_len = c.len_utf8();
1056                let new_len = *len + char_len;
1057                if new_len <= INLINE_CAP {
1058                    c.encode_utf8(&mut buf[*len..]);
1059                    *len += char_len;
1060                } else {
1061                    let mut heap = String::with_capacity(new_len);
1062                    // SAFETY: `buf[..*len]` was built by prior `push`/`push_str` calls
1063                    // that only wrote valid UTF-8 (from `char::encode_utf8` or `&str`
1064                    // byte copies), so extending the Vec with these bytes preserves the
1065                    // String's UTF-8 invariant.
1066                    unsafe { heap.as_mut_vec().extend_from_slice(&buf[..*len]) };
1067                    heap.push(c);
1068                    self.0 = SmolStrBuilderRepr::Heap(heap);
1069                }
1070            }
1071            SmolStrBuilderRepr::Heap(h) => h.push(c),
1072        }
1073    }
1074
1075    /// Appends a given string slice onto the end of `self`'s buffer.
1076    pub fn push_str(&mut self, s: &str) {
1077        match &mut self.0 {
1078            SmolStrBuilderRepr::Inline { len, buf } => {
1079                let old_len = *len;
1080                *len += s.len();
1081
1082                // if the new length will fit on the stack (even if it fills it entirely)
1083                if *len <= INLINE_CAP {
1084                    buf[old_len..*len].copy_from_slice(s.as_bytes());
1085                    return; // skip the heap push below
1086                }
1087
1088                let mut heap = String::with_capacity(*len);
1089
1090                // SAFETY: `buf[..old_len]` was built by prior `push`/`push_str` calls
1091                // that only wrote valid UTF-8 (from `char::encode_utf8` or `&str` byte
1092                // copies), so extending the Vec with these bytes preserves the String's
1093                // UTF-8 invariant.
1094                unsafe { heap.as_mut_vec().extend_from_slice(&buf[..old_len]) };
1095                heap.push_str(s);
1096                self.0 = SmolStrBuilderRepr::Heap(heap);
1097            }
1098            SmolStrBuilderRepr::Heap(heap) => heap.push_str(s),
1099        }
1100    }
1101}
1102
1103impl fmt::Write for SmolStrBuilder {
1104    #[inline]
1105    fn write_str(&mut self, s: &str) -> fmt::Result {
1106        self.push_str(s);
1107        Ok(())
1108    }
1109}
1110
1111impl iter::Extend<char> for SmolStrBuilder {
1112    fn extend<I: iter::IntoIterator<Item = char>>(&mut self, iter: I) {
1113        for c in iter {
1114            self.push(c);
1115        }
1116    }
1117}
1118
1119impl<'a> iter::Extend<&'a str> for SmolStrBuilder {
1120    fn extend<I: iter::IntoIterator<Item = &'a str>>(&mut self, iter: I) {
1121        for s in iter {
1122            self.push_str(s);
1123        }
1124    }
1125}
1126
1127impl<'a> iter::Extend<&'a String> for SmolStrBuilder {
1128    fn extend<I: iter::IntoIterator<Item = &'a String>>(&mut self, iter: I) {
1129        for s in iter {
1130            self.push_str(s);
1131        }
1132    }
1133}
1134
1135impl From<SmolStrBuilder> for SmolStr {
1136    fn from(value: SmolStrBuilder) -> Self {
1137        value.finish()
1138    }
1139}
1140
1141#[cfg(feature = "arbitrary")]
1142#[cfg_attr(docsrs, doc(cfg(feature = "arbitrary")))]
1143impl<'a> arbitrary::Arbitrary<'a> for SmolStr {
1144    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> Result<Self, arbitrary::Error> {
1145        let s = <&str>::arbitrary(u)?;
1146        Ok(SmolStr::new(s))
1147    }
1148}
1149
1150#[cfg(feature = "borsh")]
1151#[cfg_attr(docsrs, doc(cfg(feature = "borsh")))]
1152mod borsh;
1153#[cfg(feature = "serde")]
1154#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
1155mod serde;
1156
1157#[test]
1158fn from_buf_and_chars_size_hinted_heap() {
1159    let str = from_buf_and_chars(
1160        *b"abcdefghijklmnopqr00000",
1161        18,
1162        "_0x1x2x3x4x5x6x7x8x9x10x11x12x13".chars(),
1163    );
1164
1165    assert_eq!(str, "abcdefghijklmnopqr_0x1x2x3x4x5x6x7x8x9x10x11x12x13");
1166}
smol_str/lib.rs

smol_str/
lib.rs
