1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
//! String interning
//!
//! A string interner is a data structure that enables strings to be represented as integers
//! in a computer program.
//! Interning strings is often an optimization because only one copy of each distinct string is stored,
//! the string type is smaller and more cache friendly,
//! and string operations like comparisons are faster.
//! The cost of string interning (at least as implemented here) is that once a string is interned,
//! it is never deallocated.
//!
//! When using the [Interner] in this module, strings are interned using the [get_or_intern](Interner::get_or_intern) method.
//! This method returns a _key_.
//! If the same string is interned twice, the same key is returned.
//! The type of the key is fixed for each instance of the interner, and can be any
//! type that implements the [Key] trait.
//! By default the interner uses [std::num::NonZeroU32], which is a 32-bit integer.
//!
//! Given a key, the original string value can be recovered using the [resolve](Interner::resolve) method.
//!
//! ```
//! # use texcraft_stdext::collections::interner::Interner;
//! let mut interner: Interner = Default::default();
//! let hello_1 = interner.get_or_intern("hello");
//! let world_1 = interner.get_or_intern("world");
//! let hello_2 = interner.get_or_intern("hello");
//! assert_eq!(hello_1, hello_2);
//! assert_ne!(hello_1, world_1);
//!
//! assert_eq!(interner.resolve(hello_1), Some("hello"));
//! assert_eq!(interner.resolve(world_1), Some("world"));
//!
//! assert_eq!(interner.get("hello"), Some(hello_1));
//! assert_eq!(interner.get("other"), None);
//! ```
//!
//! The code in the interner is written from scratch, but all aspects of it
//! (the algorithm, the API, even some variable names) are based on Robin Freyler's
//! [string-interner](https://docs.rs/crate/string-interner/latest) crate.
//! For this reason the code is jointly copyrighted between Robin Freyler and the Texcraft contributors.
//!
//! ## The implementation
//!
//! The algorithm is based on the [string-interner](https://docs.rs/crate/string-interner/latest) crate.
//! This algorithm is also separately discovered and discussed in
//! [a post by Mat Klad](https://matklad.github.io/2020/03/22/fast-simple-rust-interner.html).
//!
//! The interner maintains a [String] buffer, and each time a new string is interned it's appended to the buffer.
//! A vector of indices is used to record the position of each string in the buffer.
//! When a new string is added to the buffer, the current length of the buffer (which is the end index
//! of the string in the buffer) is appended to the vector.
//! The key of the string is then the length of the vector when the index is appended.
//! Thus using the key, we can easily find the end index.
//!
//! To recover a string using its key, we get the end index from the vector.
//! We get the start index by getting the end index of the _previous_ string that was interned.
//! Given the process described above, the start index is stored in the vector just before the end index.
//! The recovered string is then the substring of the buffer between these two indices.
//!
//! This handles adding new strings.
//! A key property of the interner is that it also deduplicates strings.
//! The naive way to do this is to maintain a map from strings to keys, and first search
//! in this map for the string.
//! The problem with this approach is that it requires a costly second allocation
//!     of each interned string in this map.
//!
//! The string-interner crate and this module use different approaches to fix this.
//! In the crate, the map is keyed on the interned string's integer key.
//! When performing operations on the map, hash and equality of keys is based on the underlying string.
//!
//! In this module, the map is keyed on the [u64] hash of each string, which is computed outside of the map.
//! There is an edge case in which the hashes of two strings collide.
//! For this reason the value of the map is a linked list of all string keys that have the corresponding hash.
//! When checking if a string exists, we walk the linked list and check if the resolved string for each key
//!     matches.
//! If not, we intern the string and append to the linked list.
//! In the worst case this can result in O(n) lookups, but in reality hash collisions are rare.

use std::collections::hash_map;
use std::collections::HashMap;
use std::hash;
use std::num;

/// String interner.
///
/// See the module documentation for information about this data structure.
#[cfg_attr(feature = "serde", derive(serde::Serialize))]
pub struct Interner<K = num::NonZeroU32, S = hash_map::RandomState> {
    buffer: String,
    ends: Vec<usize>,
    // When deserializing the interner, we reconstruct the deduplication map. We do this because the hash
    // builder in the deserialized interner will in general be different and so the keys of the map
    // will have changed. Additionally this is more efficient.
    #[cfg_attr(feature = "serde", serde(skip))]
    dedup: DeDupMap<K>,
    #[cfg_attr(feature = "serde", serde(skip))]
    hash_builder: S,
}

impl<K, S: Default> Default for Interner<K, S> {
    fn default() -> Self {
        Self {
            buffer: Default::default(),
            ends: Default::default(),
            dedup: Default::default(),
            hash_builder: Default::default(),
        }
    }
}

/// Types implementing this trait can be used as keys in the [Interner].
pub trait Key: Copy + Eq {
    /// Try to create a key from the provided [usize]. The first [usize]
    /// passed to this method will be 0; the second 1; and so on.
    ///
    /// This method is more or less the same as the well-known [`TryFrom<usize>`] trait.
    /// We use a custom trait so that consumers don't have to implement the well-known trait.
    fn try_from_usize(index: usize) -> Option<Self>;
    /// Convert the key into a [usize].
    ///
    /// This method is more or less the same as the well-known [`Into<usize>`] trait.
    /// We use a custom trait so that consumers don't have to implement the well-known trait.
    fn into_usize(self) -> usize;
}

impl Key for num::NonZeroU32 {
    fn try_from_usize(index: usize) -> Option<Self> {
        let u32: u32 = match index.try_into() {
            Ok(u32) => u32,
            Err(_) => return None,
        };
        num::NonZeroU32::new(u32 + 1)
    }

    fn into_usize(self) -> usize {
        self.get() as usize
    }
}

impl<K: Key, S: hash::BuildHasher> Interner<K, S> {
    /// Intern the provided string and return its key.
    pub fn get_or_intern(&mut self, s: &str) -> K {
        // First we check if the string has already been interned.
        let hash = hash(&self.hash_builder, s);
        if let Some(key) = self.get_internal(s, hash) {
            return key;
        }

        // If the string hasn't been interned, we now intern it.
        let key = K::try_from_usize(self.ends.len()).unwrap();
        self.buffer.push_str(s);
        let end = self.buffer.len();
        self.ends.push(end);
        populate_dedup_map(&mut self.dedup, hash, key);
        key
    }

    /// Get the key for the provided string if it has been already been interned.
    ///
    /// This method is useful when the caller only has a shared reference to the interner.
    pub fn get(&self, s: &str) -> Option<K> {
        self.get_internal(s, hash(&self.hash_builder, s))
    }

    fn get_internal(&self, s: &str, hash: u64) -> Option<K> {
        let mut node_or = self.dedup.get(&hash);
        while let Some(node) = node_or {
            if self.resolve(node.key).unwrap() == s {
                return Some(node.key);
            }
            node_or = match &node.next {
                None => None,
                Some(node) => Some(node),
            };
        }
        None
    }

    /// Return the interned string corresponding to the provided key.
    pub fn resolve(&self, k: K) -> Option<&str> {
        let i = k.into_usize().wrapping_sub(1);
        let start = match i.checked_sub(1) {
            None => 0,
            Some(prev_k) => match self.ends.get(prev_k) {
                None => return None,
                Some(start) => *start,
            },
        };
        let end = match self.ends.get(i) {
            None => return None,
            Some(end) => *end,
        };
        Some(&self.buffer[start..end])
    }
}

fn hash<S: hash::BuildHasher>(hash_builder: &S, s: &str) -> u64 {
    hash_builder.hash_one(s)
}

type DeDupMap<K> = HashMap<u64, LinkedList<K>, hash::BuildHasherDefault<SingleU64Hasher>>;

fn populate_dedup_map<K>(map: &mut DeDupMap<K>, hash: u64, key: K) {
    match map.entry(hash) {
        hash_map::Entry::Occupied(mut o) => {
            let first = o.get_mut();
            let second = std::mem::replace(first, LinkedList { key, next: None });
            first.next = Some(Box::new(second));
        }
        hash_map::Entry::Vacant(v) => {
            v.insert(LinkedList { key, next: None });
        }
    };
}

struct LinkedList<K> {
    key: K,
    next: Option<Box<LinkedList<K>>>,
}

/// A hasher that can only hash a single [u64] value, and whose result is simply the [u64] value.
///
/// This hasher is used to make the hashing in the interner's deduplication map a no-op.
/// We use this hasher because the [u64] key for the map is already a hash (of a string),
/// and hashing the value again is wasteful.
///
/// The implementation of this hasher uses safe Rust and performs at least two panic-able checks
/// on the hot path of hashing the value.
/// However when compiled, the entire hasher is completely optimized out, and the
/// hashing function inside the hash map becomes the identity function for the [u64] type.
#[derive(Default)]
struct SingleU64Hasher {
    val: Option<u64>,
}

impl hash::Hasher for SingleU64Hasher {
    #[inline]
    fn finish(&self) -> u64 {
        self.val.unwrap()
    }

    fn write(&mut self, _: &[u8]) {
        panic!("this hasher does not support writing arbitrary bytes, only a single u64 value")
    }

    #[inline]
    fn write_u64(&mut self, i: u64) {
        if self.val.is_some() {
            panic!("this hasher does not support writing multiple u64 values")
        }
        self.val = Some(i)
    }
}

#[cfg(feature = "serde")]
impl<'de, K: Key, S: Default + hash::BuildHasher> serde::Deserialize<'de> for Interner<K, S> {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        #[derive(serde::Deserialize)]
        struct DeserializedInterner {
            buffer: String,
            ends: Vec<usize>,
        }

        let DeserializedInterner { buffer, ends } =
            DeserializedInterner::deserialize(deserializer)?;
        let hash_builder = S::default();
        let mut dedup = DeDupMap::<K>::default();
        dedup.reserve(ends.len());

        let mut start: usize = 0;
        for (i, end) in ends.iter().enumerate() {
            let s = &buffer[start..*end];
            let hash = hash(&hash_builder, s);
            let key = K::try_from_usize(i).unwrap();
            populate_dedup_map(&mut dedup, hash, key);
            start = *end;
        }
        Ok(Self {
            buffer,
            ends,
            dedup,
            hash_builder,
        })
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// A hasher that always returns the same fixed value.
    /// This is use to test hash collisions.
    #[derive(Default)]
    struct FixedHasher;

    impl hash::Hasher for FixedHasher {
        fn finish(&self) -> u64 {
            12
        }

        fn write(&mut self, _: &[u8]) {}
    }

    #[test]
    fn test_hash_collision() {
        let mut interner: Interner<num::NonZeroU32, hash::BuildHasherDefault<FixedHasher>> =
            Default::default();
        let hello_1 = interner.get_or_intern("hello");
        let world_1 = interner.get_or_intern("world");
        let hello_2 = interner.get_or_intern("hello");
        assert_eq!(hello_1, hello_2);
        assert_ne!(hello_1, world_1);

        assert_eq!(interner.resolve(hello_1), Some("hello"));
        assert_eq!(interner.resolve(world_1), Some("world"));
    }

    #[cfg(feature = "serde")]
    #[test]
    fn test_serde() {
        let mut interner: Interner = Default::default();
        let hello_1 = interner.get_or_intern("hello");
        let world_1 = interner.get_or_intern("world");

        let serialized = serde_json::to_string_pretty(&interner).unwrap();
        let mut interner_de: Interner = serde_json::from_str(&serialized).unwrap();
        let hello_2 = interner_de.get_or_intern("hello");
        let world_2 = interner_de.get_or_intern("world");

        assert_eq!(hello_1, hello_2);
        assert_eq!(world_1, world_2);
    }
}