cold_string/
lib.rs

1#![allow(rustdoc::bare_urls)]
2#![doc = include_str!("../README.md")]
3#![allow(unknown_lints, unexpected_cfgs)]
4#![allow(unstable_name_collisions)]
5#![no_std]
6
7extern crate alloc;
8
9#[cfg(test)]
10extern crate std;
11
12use alloc::{
13    borrow::{Cow, ToOwned},
14    boxed::Box,
15    str::Utf8Error,
16    string::String,
17};
18use core::{
19    cmp::Ordering,
20    fmt,
21    hash::{Hash, Hasher},
22    iter::FromIterator,
23    ops::Deref,
24    str,
25};
26
27#[cfg(test)]
28use core::{mem, ptr};
29
30mod arc;
31mod encoded;
32mod heap;
33mod vint;
34
35pub use crate::arc::ArcColdString;
36pub use crate::arc::ArcColdString16;
37pub use crate::arc::ArcColdString32;
38pub use crate::arc::ArcColdString8;
39use crate::encoded::Encoded;
40
41#[cfg(feature = "rkyv")]
42mod rkyv;
43
44/// Compact representation of immutable UTF-8 strings. Optimized for memory usage and struct packing.
45///
46/// # Example
47/// ```
48/// let s = cold_string::ColdString::new("qwerty");
49/// assert_eq!(s.as_str(), "qwerty");
50/// ```
51/// ```
52/// use core::mem::size_of;
53/// use cold_string::ColdString;
54///
55/// assert_eq!(size_of::<ColdString>(), size_of::<usize>());
56/// assert_eq!(size_of::<Option<ColdString>>(), size_of::<ColdString>());
57/// ```
58#[repr(transparent)]
59pub struct ColdString {
60    /// The first byte of `encoded` is the "tag" and it determines the type:
61    /// - 10xxxxxx: an encoded address for the heap. To decode, 10 is set to 00 and swapped
62    ///   with the LSB bits of the tag byte. The address is always a multiple of 4 (`HEAP_ALIGN`).
63    /// - 11111xxx: xxx is the length in range 0..=7, followed by length UTF-8 bytes.
64    /// - xxxxxxxx (valid UTF-8): 8 UTF-8 bytes.
65    ///
66    /// The exception is if `encoded` is `usize::MAX`, which represents one word of NUL bytes.
67    encoded: Encoded<()>,
68}
69
70impl ColdString {
71    /// Convert a slice of bytes into a [`ColdString`].
72    ///
73    /// A [`ColdString`] is a contiguous collection of bytes (`u8`s) that is valid [`UTF-8`](https://en.wikipedia.org/wiki/UTF-8).
74    /// This method converts from an arbitrary contiguous collection of bytes into a
75    /// [`ColdString`], failing if the provided bytes are not `UTF-8`.
76    ///
77    /// # Examples
78    /// ### Valid UTF-8
79    /// ```
80    /// # use cold_string::ColdString;
81    /// let bytes = [240, 159, 166, 128, 240, 159, 146, 175];
82    /// let compact = ColdString::from_utf8(&bytes).expect("valid UTF-8");
83    ///
84    /// assert_eq!(compact, "🦀💯");
85    /// ```
86    ///
87    /// ### Invalid UTF-8
88    /// ```
89    /// # use cold_string::ColdString;
90    /// let bytes = [255, 255, 255];
91    /// let result = ColdString::from_utf8(&bytes);
92    ///
93    /// assert!(result.is_err());
94    /// ```
95    pub fn from_utf8<B: AsRef<[u8]>>(v: B) -> Result<Self, Utf8Error> {
96        Ok(Self::new(str::from_utf8(v.as_ref())?))
97    }
98
99    /// Converts a vector of bytes to a [`ColdString`] without checking that the string contains
100    /// valid UTF-8.
101    ///
102    /// See the safe version, [`ColdString::from_utf8`], for more details.
103    ///
104    /// # Examples
105    ///
106    /// Basic usage:
107    ///
108    /// ```
109    /// # use cold_string::ColdString;
110    /// // some bytes, in a vector
111    /// let sparkle_heart = [240, 159, 146, 150];
112    ///
113    /// let sparkle_heart = unsafe {
114    ///     ColdString::from_utf8_unchecked(&sparkle_heart)
115    /// };
116    ///
117    /// assert_eq!("💖", sparkle_heart);
118    /// ```
119    ///
120    /// # Safety
121    ///
122    /// `v` must contain valid UTF-8.
123    pub unsafe fn from_utf8_unchecked<B: AsRef<[u8]>>(v: B) -> Self {
124        Self::new(str::from_utf8_unchecked(v.as_ref()))
125    }
126
127    /// Creates a new [`ColdString`] from any type that implements `AsRef<str>`.
128    /// If the string is at most `core::mem::size_of::<usize>()` bytes, then it
129    /// will be inlined on the stack.
130    pub fn new<T: AsRef<str>>(x: T) -> Self {
131        let s = x.as_ref();
132        Self {
133            encoded: Encoded::new(s, ()),
134        }
135    }
136
137    /// Creates a new inline [`ColdString`] from `&'static str` at compile time.
138    ///
139    /// In a dynamic context you can use the method [`ColdString::new()`].
140    ///
141    /// # Panics
142    /// The string must be at most `core::mem::size_of::<usize>()`. Creating
143    /// a [`ColdString`] larger than that is not supported.
144    ///
145    ///
146    /// # Examples
147    /// ```
148    /// use cold_string::ColdString;
149    ///
150    /// const DEFAULT_NAME: ColdString = ColdString::new_inline_const("cold");
151    /// ```
152    #[rustversion::since(1.61)]
153    #[inline]
154    pub const fn new_inline_const(s: &str) -> Self {
155        Self {
156            encoded: Encoded::new_inline_const(s),
157        }
158    }
159
160    /// Returns `true` if the string bytes are inlined.
161    #[inline]
162    pub fn is_inline(&self) -> bool {
163        self.encoded.is_inline()
164    }
165
166    /// Returns the length of this `ColdString`, in bytes, not [`char`]s or
167    /// graphemes. In other words, it might not be what a human considers the
168    /// length of the string.
169    ///
170    /// # Examples
171    ///
172    /// ```
173    /// use cold_string::ColdString;
174    ///
175    /// let a = ColdString::from("foo");
176    /// assert_eq!(a.len(), 3);
177    ///
178    /// let fancy_f = String::from("ƒoo");
179    /// assert_eq!(fancy_f.len(), 4);
180    /// assert_eq!(fancy_f.chars().count(), 3);
181    /// ```
182    #[inline]
183    pub fn len(&self) -> usize {
184        self.encoded.len()
185    }
186
187    /// Returns a byte slice of this `ColdString`'s contents.
188    ///
189    /// The inverse of this method is [`from_utf8`].
190    ///
191    /// [`from_utf8`]: String::from_utf8
192    ///
193    /// # Examples
194    ///
195    /// ```
196    /// let s = cold_string::ColdString::from("hello");
197    ///
198    /// assert_eq!(&[104, 101, 108, 108, 111], s.as_bytes());
199    /// ```
200    #[inline]
201    pub fn as_bytes(&self) -> &[u8] {
202        self.encoded.as_bytes()
203    }
204
205    /// Returns a string slice containing the entire [`ColdString`].
206    ///
207    /// # Examples
208    /// ```
209    /// let s = cold_string::ColdString::new("hello");
210    ///
211    /// assert_eq!(s.as_str(), "hello");
212    /// ```
213    #[inline]
214    pub fn as_str(&self) -> &str {
215        unsafe { str::from_utf8_unchecked(self.as_bytes()) }
216    }
217
218    /// Returns `true` if this `ColdString` has a length of zero, and `false` otherwise.
219    ///
220    /// # Examples
221    ///
222    /// ```
223    /// let v = cold_string::ColdString::new("");
224    /// assert!(v.is_empty());
225    /// ```
226    #[inline]
227    pub fn is_empty(&self) -> bool {
228        self.len() == 0
229    }
230}
231
232impl Default for ColdString {
233    fn default() -> Self {
234        Self::new("")
235    }
236}
237
238impl Deref for ColdString {
239    type Target = str;
240    fn deref(&self) -> &str {
241        self.as_str()
242    }
243}
244
245impl Drop for ColdString {
246    fn drop(&mut self) {
247        if !self.is_inline() {
248            // SAFETY: a non-inline `ColdString` uniquely owns its allocation.
249            unsafe { self.encoded.deallocate() }
250        }
251    }
252}
253
254impl Clone for ColdString {
255    fn clone(&self) -> Self {
256        if self.is_inline() {
257            Self {
258                encoded: self.encoded,
259            }
260        } else {
261            Self::new(self.as_str())
262        }
263    }
264}
265
266impl PartialEq for ColdString {
267    fn eq(&self, other: &Self) -> bool {
268        self.encoded.addr() == other.encoded.addr() || self.as_bytes() == other.as_bytes()
269    }
270}
271
272impl Eq for ColdString {}
273
274impl Hash for ColdString {
275    fn hash<H: Hasher>(&self, state: &mut H) {
276        self.as_str().hash(state)
277    }
278}
279
280impl fmt::Debug for ColdString {
281    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
282        fmt::Debug::fmt(self.as_str(), f)
283    }
284}
285
286impl fmt::Display for ColdString {
287    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
288        fmt::Display::fmt(self.as_str(), f)
289    }
290}
291
292impl From<&str> for ColdString {
293    fn from(s: &str) -> Self {
294        Self::new(s)
295    }
296}
297
298impl From<String> for ColdString {
299    fn from(s: String) -> Self {
300        Self::new(&s)
301    }
302}
303
304impl From<ColdString> for String {
305    fn from(s: ColdString) -> Self {
306        s.as_str().to_owned()
307    }
308}
309
310impl From<ColdString> for Cow<'_, str> {
311    #[inline]
312    fn from(s: ColdString) -> Self {
313        Self::Owned(s.into())
314    }
315}
316
317impl<'a> From<&'a ColdString> for Cow<'a, str> {
318    #[inline]
319    fn from(s: &'a ColdString) -> Self {
320        Self::Borrowed(s)
321    }
322}
323
324impl<'a> From<Cow<'a, str>> for ColdString {
325    fn from(cow: Cow<'a, str>) -> Self {
326        Self::new(cow)
327    }
328}
329
330impl From<Box<str>> for ColdString {
331    #[inline]
332    #[track_caller]
333    fn from(b: Box<str>) -> Self {
334        Self::new(&b)
335    }
336}
337
338impl FromIterator<char> for ColdString {
339    fn from_iter<I: IntoIterator<Item = char>>(iter: I) -> Self {
340        Self::new(iter.into_iter().collect::<String>())
341    }
342}
343
344unsafe impl Send for ColdString {}
345unsafe impl Sync for ColdString {}
346
347impl core::borrow::Borrow<str> for ColdString {
348    fn borrow(&self) -> &str {
349        self.as_str()
350    }
351}
352
353impl PartialEq<str> for ColdString {
354    fn eq(&self, other: &str) -> bool {
355        self.as_str() == other
356    }
357}
358
359impl PartialEq<ColdString> for str {
360    fn eq(&self, other: &ColdString) -> bool {
361        other.eq(self)
362    }
363}
364
365impl PartialEq<&str> for ColdString {
366    fn eq(&self, other: &&str) -> bool {
367        self.eq(*other)
368    }
369}
370
371impl PartialEq<ColdString> for &str {
372    fn eq(&self, other: &ColdString) -> bool {
373        other.eq(*self)
374    }
375}
376
377impl AsRef<str> for ColdString {
378    #[inline]
379    fn as_ref(&self) -> &str {
380        self.as_str()
381    }
382}
383
384impl AsRef<[u8]> for ColdString {
385    #[inline]
386    fn as_ref(&self) -> &[u8] {
387        self.as_bytes()
388    }
389}
390
391impl Ord for ColdString {
392    fn cmp(&self, other: &Self) -> Ordering {
393        self.as_str().cmp(other.as_str())
394    }
395}
396
397impl PartialOrd for ColdString {
398    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
399        Some(self.cmp(other))
400    }
401}
402
403impl alloc::str::FromStr for ColdString {
404    type Err = core::convert::Infallible;
405    fn from_str(s: &str) -> Result<ColdString, Self::Err> {
406        Ok(ColdString::new(s))
407    }
408}
409
410#[cfg(feature = "serde")]
411impl serde::Serialize for ColdString {
412    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
413        serializer.serialize_str(self.as_str())
414    }
415}
416
417#[cfg(feature = "serde")]
418impl<'de> serde::Deserialize<'de> for ColdString {
419    fn deserialize<D: serde::Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
420        let s = String::deserialize(d)?;
421        Ok(ColdString::new(&s))
422    }
423}
424
425#[cfg(test)]
426trait TestString:
427    Clone + Default + fmt::Debug + Eq + Hash + PartialEq<str> + for<'a> PartialEq<&'a str>
428{
429    fn new(s: &str) -> Self;
430    fn from_utf8(bytes: &[u8]) -> Result<Self, Utf8Error>;
431    fn new_inline(s: &str) -> Self;
432    fn is_inline(&self) -> bool;
433    fn is_empty(&self) -> bool;
434    fn len(&self) -> usize;
435    fn as_bytes(&self) -> &[u8];
436    fn as_str(&self) -> &str;
437    fn encoded_addr(&self) -> usize;
438}
439
440#[cfg(test)]
441impl TestString for ColdString {
442    fn new(s: &str) -> Self {
443        Self::new(s)
444    }
445
446    fn from_utf8(bytes: &[u8]) -> Result<Self, Utf8Error> {
447        Self::from_utf8(bytes)
448    }
449
450    fn new_inline(s: &str) -> Self {
451        Self::new_inline_const(s)
452    }
453
454    fn is_inline(&self) -> bool {
455        self.is_inline()
456    }
457
458    fn is_empty(&self) -> bool {
459        self.is_empty()
460    }
461
462    fn len(&self) -> usize {
463        self.len()
464    }
465
466    fn as_bytes(&self) -> &[u8] {
467        self.as_bytes()
468    }
469
470    fn as_str(&self) -> &str {
471        self.as_str()
472    }
473
474    fn encoded_addr(&self) -> usize {
475        self.encoded.addr()
476    }
477}
478
479#[cfg(test)]
480impl<A: arc::RefCount> TestString for arc::ArcColdStringInner<A> {
481    fn new(s: &str) -> Self {
482        Self::new(s)
483    }
484
485    fn from_utf8(bytes: &[u8]) -> Result<Self, Utf8Error> {
486        Self::from_utf8(bytes)
487    }
488
489    fn new_inline(s: &str) -> Self {
490        Self::new_inline_const(s)
491    }
492
493    fn is_inline(&self) -> bool {
494        self.is_inline()
495    }
496
497    fn is_empty(&self) -> bool {
498        self.is_empty()
499    }
500
501    fn len(&self) -> usize {
502        self.len()
503    }
504
505    fn as_bytes(&self) -> &[u8] {
506        self.as_bytes()
507    }
508
509    fn as_str(&self) -> &str {
510        self.as_str()
511    }
512
513    fn encoded_addr(&self) -> usize {
514        self.encoded_addr()
515    }
516}
517
518#[cfg(test)]
519macro_rules! each_string {
520    ($test:ident $(, $arg:expr)*) => {
521        $test::<ColdString>($($arg),*);
522        $test::<ArcColdString>($($arg),*);
523        $test::<ArcColdString8>($($arg),*);
524        $test::<ArcColdString16>($($arg),*);
525        $test::<ArcColdString32>($($arg),*);
526    };
527}
528
529#[cfg(all(test, feature = "serde"))]
530mod serde_tests {
531    use super::*;
532    use serde_test::{assert_tokens, Token};
533
534    fn assert_serde<T>(s: &'static str)
535    where
536        T: TestString + serde::Serialize + for<'de> serde::Deserialize<'de>,
537    {
538        assert_tokens(&T::new(s), &[Token::Str(s)]);
539    }
540
541    #[test]
542    fn test_serde_cold_string_inline() {
543        each_string!(assert_serde, "ferris");
544    }
545
546    #[test]
547    fn test_serde_cold_string_heap() {
548        let long_str = "This is a significantly longer string for heap testing";
549        each_string!(assert_serde, long_str);
550    }
551}
552
553#[cfg(test)]
554mod tests {
555    use super::*;
556    use core::hash::BuildHasher;
557    use hashbrown::hash_map::DefaultHashBuilder;
558
559    fn assert_layout<T: TestString>() {
560        assert_eq!(mem::size_of::<T>(), mem::size_of::<usize>());
561        assert_eq!(mem::size_of::<Option<T>>(), mem::size_of::<T>());
562    }
563
564    #[test]
565    fn test_layout() {
566        each_string!(assert_layout);
567    }
568
569    fn assert_default<T: TestString>() {
570        assert!(T::default().is_empty());
571        assert_eq!(T::default().len(), 0);
572        assert_eq!(T::default(), "");
573        assert_eq!(T::default(), T::new(""));
574    }
575
576    #[test]
577    fn test_default() {
578        each_string!(assert_default);
579    }
580
581    fn assert_utf8_validation<T: TestString>() {
582        for valid in ["", "🦀", "valid UTF-8 🦀 longer than one word"] {
583            assert_eq!(T::from_utf8(valid.as_bytes()).unwrap().as_str(), valid);
584        }
585
586        for invalid in [
587            &[0x80][..],
588            &[0xff][..],
589            &[0xc0, 0x80][..],
590            &[0xe2, 0x82][..],
591        ] {
592            assert!(T::from_utf8(invalid).is_err());
593        }
594    }
595
596    #[test]
597    fn test_utf8_validation() {
598        each_string!(assert_utf8_validation);
599    }
600
601    fn assert_correct<T: TestString>(s: &str)
602    where
603        str: PartialEq<T>,
604        for<'a> &'a str: PartialEq<T>,
605    {
606        let cs = T::new(s);
607        assert_eq!(s.len() <= mem::size_of::<usize>(), cs.is_inline());
608        assert_eq!(cs.len(), s.len());
609        assert_eq!(cs.as_bytes(), s.as_bytes());
610        assert_eq!(cs.as_str().as_bytes(), s.as_bytes());
611        assert_eq!(cs.clone(), cs);
612        let bh = DefaultHashBuilder::new();
613        let mut hasher1 = bh.build_hasher();
614        cs.hash(&mut hasher1);
615        let mut hasher2 = bh.build_hasher();
616        cs.clone().hash(&mut hasher2);
617        assert_eq!(hasher1.finish(), hasher2.finish());
618        assert_eq!(cs, s);
619        assert_eq!(s, cs);
620        assert_eq!(cs, *s);
621        assert_eq!(*s, cs);
622        let opt_s = Some(cs.clone());
623        assert_eq!(opt_s, Some(T::new(s)));
624        assert!(opt_s.is_some());
625    }
626
627    #[test]
628    fn it_works() {
629        for s in [
630            "1",
631            "12",
632            "123",
633            "1234",
634            "12345",
635            "123456",
636            "1234567",
637            "12345678",
638            "123456789",
639            str::from_utf8(&[240, 159, 146, 150]).unwrap(),
640            "✅",
641            "❤️",
642            "🦀💯",
643            "🦀",
644            "💯",
645            "abcd",
646            "test",
647            "",
648            "\0",
649            "\0\0",
650            "\0\0\0",
651            "\0\0\0\0",
652            "\0\0\0\0\0\0\0",
653            "\0\0\0\0\0\0\0\0",
654            "1234567",
655            "12345678",
656            "longer test",
657            str::from_utf8(&[103, 39, 240, 145, 167, 156, 194, 165]).unwrap(),
658            "AaAa0 ® ",
659            str::from_utf8(&[240, 158, 186, 128, 240, 145, 143, 151]).unwrap(),
660        ] {
661            each_string!(assert_correct, s);
662        }
663    }
664
665    fn char_from_leading_byte(b: u8) -> Option<char> {
666        match b {
667            0x00..=0x7F => Some(b as char),
668            0xC2..=0xDF => str::from_utf8(&[b, 0x91]).unwrap().chars().next(),
669            0xE0 => str::from_utf8(&[b, 0xA0, 0x91]).unwrap().chars().next(),
670            0xE1..=0xEC | 0xEE..=0xEF => str::from_utf8(&[b, 0x91, 0xA5]).unwrap().chars().next(),
671            0xED => str::from_utf8(&[b, 0x80, 0x91]).unwrap().chars().next(),
672            0xF0 => str::from_utf8(&[b, 0x90, 0x91, 0xA5])
673                .unwrap()
674                .chars()
675                .next(),
676            0xF1..=0xF3 => str::from_utf8(&[b, 0x91, 0xA5, 0x82])
677                .unwrap()
678                .chars()
679                .next(),
680            0xF4 => str::from_utf8(&[b, 0x80, 0x91, 0x82])
681                .unwrap()
682                .chars()
683                .next(),
684            _ => None,
685        }
686    }
687
688    #[test]
689    fn test_edges() {
690        let width = mem::size_of::<usize>();
691        for len in [width - 1, width, width + 1] {
692            for first_byte in 0u8..=255 {
693                let first_char = match char_from_leading_byte(first_byte) {
694                    Some(c) => c,
695                    None => continue,
696                };
697
698                let mut s = String::with_capacity(len);
699                s.push(first_char);
700
701                while s.len() < len {
702                    let c = core::char::from_digit((len - s.len()) as u32, 10).unwrap();
703                    s.push(c);
704                }
705
706                each_string!(assert_correct, &s);
707            }
708        }
709    }
710
711    fn assert_unaligned_placement<T: TestString>() {
712        for s_content in ["torture", "tor", "tortures", "tort", "torture torture"] {
713            let mut buffer = [0u8; 32];
714            for offset in 0..8 {
715                unsafe {
716                    let dst = buffer.as_mut_ptr().add(offset).cast::<T>();
717                    let s = T::new(s_content);
718                    ptr::write_unaligned(dst, s);
719                    let recovered = ptr::read_unaligned(dst);
720                    assert_eq!(recovered.as_str(), s_content);
721                }
722            }
723        }
724    }
725
726    #[test]
727    fn test_unaligned_placement() {
728        each_string!(assert_unaligned_placement);
729    }
730
731    #[test]
732    fn ensure_zero_repr() {
733        assert!(str::from_utf8(&Encoded::<()>::WORD_NUL_MAP.to_ne_bytes()).is_err());
734    }
735
736    fn assert_const_word_nul<T: TestString>() {
737        let nul = str::from_utf8(&encoded::WORD_NUL).unwrap();
738        let const_value = T::new_inline(nul);
739        let non_const = T::new(nul);
740        let cloned = non_const.clone();
741        assert_eq!(const_value.encoded_addr(), non_const.encoded_addr());
742        assert_eq!(const_value.encoded_addr(), cloned.encoded_addr());
743        // The sentinel returns a slice into the shared word-sized NUL array.
744        assert_eq!(
745            &const_value.as_str().as_bytes()[0] as *const u8,
746            (&encoded::WORD_NUL) as *const u8
747        );
748    }
749
750    #[test]
751    fn test_const_word_nul() {
752        each_string!(assert_const_word_nul);
753    }
754}
cold_string/lib.rs

cold_string/
lib.rs
