string_interner/
symbol.rs

1//! Interfaces and types to be used as symbols for the
2//! [`StringInterner`](`crate::StringInterner`).
3//!
4//! The [`StringInterner::get_or_intern`](`crate::StringInterner::get_or_intern`)
5//! method returns `Symbol` types that allow to look-up the original string
6//! using [`StringInterner::resolve`](`crate::StringInterner::resolve`).
7
8use core::num::{NonZeroU16, NonZeroU32, NonZeroUsize};
9
10/// Types implementing this trait can be used as symbols for string interners.
11///
12/// The [`StringInterner::get_or_intern`](`crate::StringInterner::get_or_intern`)
13/// method returns `Symbol` types that allow to look-up the original string
14/// using [`StringInterner::resolve`](`crate::StringInterner::resolve`).
15///
16/// # Note
17///
18/// Optimal symbols allow for efficient comparisons and have a small memory footprint.
19pub trait Symbol: Copy + Eq {
20    /// Creates a symbol from a `usize`.
21    ///
22    /// Returns `None` if `index` is out of bounds for the symbol.
23    fn try_from_usize(index: usize) -> Option<Self>;
24
25    /// Returns the `usize` representation of `self`.
26    fn to_usize(self) -> usize;
27}
28
29/// Creates the symbol `S` from the given `usize`.
30///
31/// # Panics
32///
33/// Panics if the conversion is invalid.
34#[cfg(feature = "backends")]
35#[inline]
36pub(crate) fn expect_valid_symbol<S>(index: usize) -> S
37where
38    S: Symbol,
39{
40    S::try_from_usize(index).expect("encountered invalid symbol")
41}
42
43/// The symbol type that is used by default.
44pub type DefaultSymbol = SymbolU32;
45
46impl Symbol for usize {
47    #[inline]
48    fn try_from_usize(index: usize) -> Option<Self> {
49        Some(index)
50    }
51
52    #[inline]
53    fn to_usize(self) -> usize {
54        self
55    }
56}
57
58macro_rules! gen_symbol_for {
59    (
60        $( #[$doc:meta] )*
61        struct $name:ident($non_zero:ty; $base_ty:ty);
62    ) => {
63        $( #[$doc] )*
64        #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
65        pub struct $name {
66            pub(crate) value: $non_zero,
67        }
68
69        impl $name {
70            pub(crate) fn new(index: $base_ty) -> Option<Self> {
71                <$non_zero>::new((index).wrapping_add(1))
72                    .map(|value| Self { value })
73            }
74        }
75
76        impl Symbol for $name {
77            #[inline]
78            fn try_from_usize(index: usize) -> Option<Self> {
79                Self::new(index as $base_ty)
80            }
81
82            #[inline]
83            fn to_usize(self) -> usize {
84                self.value.get() as usize - 1
85            }
86        }
87    };
88}
89gen_symbol_for!(
90    /// Symbol that is 16-bit in size.
91    ///
92    /// Is space-optimized for used in `Option`.
93    struct SymbolU16(NonZeroU16; u16);
94);
95gen_symbol_for!(
96    /// Symbol that is 32-bit in size.
97    ///
98    /// Is space-optimized for used in `Option`.
99    struct SymbolU32(NonZeroU32; u32);
100);
101gen_symbol_for!(
102    /// Symbol that is the same size as a pointer (`usize`).
103    ///
104    /// Is space-optimized for used in `Option`.
105    struct SymbolUsize(NonZeroUsize; usize);
106);
107
108#[cfg(test)]
109mod tests {
110    use super::*;
111    use core::mem::size_of;
112
113    #[test]
114    fn same_size_as_u32() {
115        assert_eq!(size_of::<DefaultSymbol>(), size_of::<u32>());
116    }
117
118    #[test]
119    fn same_size_as_optional() {
120        assert_eq!(
121            size_of::<DefaultSymbol>(),
122            size_of::<Option<DefaultSymbol>>()
123        );
124    }
125
126    #[test]
127    fn try_from_usize_works() {
128        assert_eq!(
129            SymbolU16::try_from_usize(0),
130            Some(SymbolU16 {
131                value: NonZeroU16::new(1).unwrap()
132            })
133        );
134        assert_eq!(
135            SymbolU16::try_from_usize(u16::MAX as usize - 1),
136            Some(SymbolU16 {
137                value: NonZeroU16::new(u16::MAX).unwrap()
138            })
139        );
140        assert_eq!(SymbolU16::try_from_usize(u16::MAX as usize), None);
141        assert_eq!(SymbolU16::try_from_usize(usize::MAX), None);
142    }
143
144    macro_rules! gen_test_for {
145        ( $test_name:ident: struct $name:ident($non_zero:ty; $base_ty:ty); ) => {
146            #[test]
147            fn $test_name() {
148                for val in 0..10 {
149                    assert_eq!(
150                        <$name>::try_from_usize(val),
151                        Some($name {
152                            value: <$non_zero>::new(val as $base_ty + 1).unwrap()
153                        })
154                    );
155                }
156                assert_eq!(
157                    <$name>::try_from_usize(<$base_ty>::MAX as usize - 1),
158                    Some($name {
159                        value: <$non_zero>::new(<$base_ty>::MAX).unwrap()
160                    })
161                );
162                assert_eq!(<$name>::try_from_usize(<$base_ty>::MAX as usize), None);
163                assert_eq!(<$name>::try_from_usize(<usize>::MAX), None);
164            }
165        };
166    }
167    gen_test_for!(
168        try_from_usize_works_for_u16:
169        struct SymbolU16(NonZeroU16; u16);
170    );
171    gen_test_for!(
172        try_from_usize_works_for_u32:
173        struct SymbolU32(NonZeroU32; u32);
174    );
175    gen_test_for!(
176        try_from_usize_works_for_usize:
177        struct SymbolUsize(NonZeroUsize; usize);
178    );
179}
string_interner/symbol.rs

string_interner/
symbol.rs
