1use std::collections::HashMap;
11use std::sync::atomic::{AtomicBool, Ordering as AtomicOrdering};
12use std::sync::{Arc, PoisonError, RwLock};
13
14#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
16pub enum StringOrder {
17 #[default]
19 Text,
20 Token,
22}
23
24#[derive(Debug, Default)]
26pub struct Strings {
27 inner: RwLock<Inner>,
28 order: StringOrder,
29 sealed: AtomicBool,
30}
31
32#[derive(Debug, Default)]
33struct Inner {
34 ids: HashMap<Arc<str>, u32>,
35 texts: Vec<Arc<str>>,
36 payload_bytes: usize,
37 longest_bytes: usize,
38 ranks: Arc<[u32]>,
41}
42
43const RANK_ALL_UP_TO: usize = 1024;
48
49fn rank_stale(ranked: usize, len: usize) -> bool {
52 let unranked = len.saturating_sub(ranked);
53 unranked > 0 && (len <= RANK_ALL_UP_TO || unranked.saturating_mul(8) >= ranked)
54}
55
56#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
63pub struct StringsMemory {
64 pub payload_bytes: usize,
66 pub text_slots_bytes: usize,
68 pub index_entries_bytes: usize,
70 pub index_capacity: usize,
72 pub strings: usize,
74}
75
76impl StringsMemory {
77 #[must_use]
80 pub fn known_retained_bytes(self) -> Option<usize> {
81 self.payload_bytes
82 .checked_add(self.text_slots_bytes)?
83 .checked_add(self.index_entries_bytes)
84 }
85}
86
87impl Strings {
88 #[must_use]
90 pub fn new(order: StringOrder) -> Self {
91 Self {
92 inner: RwLock::default(),
93 order,
94 sealed: AtomicBool::new(false),
95 }
96 }
97
98 #[must_use]
100 pub fn order(&self) -> StringOrder {
101 self.order
102 }
103
104 pub fn preload<'a>(
115 &self,
116 texts: impl IntoIterator<Item = &'a str>,
117 ) -> Result<(), crate::Error> {
118 for (n, t) in texts.into_iter().enumerate() {
119 if self.intern(t)? as usize != n {
120 return Err(crate::Error::internal(
121 "string tokens preloaded out of order: the table must be a prefix of distinct texts",
122 ));
123 }
124 }
125 Ok(())
126 }
127
128 pub fn seal(&self) {
133 self.sealed.store(true, AtomicOrdering::Release);
134 }
135
136 #[must_use]
138 pub fn is_sealed(&self) -> bool {
139 self.sealed.load(AtomicOrdering::Acquire)
140 }
141
142 #[must_use]
144 pub fn lookup(&self, text: &str) -> Option<u32> {
145 self.inner
146 .read()
147 .unwrap_or_else(PoisonError::into_inner)
148 .ids
149 .get(text)
150 .copied()
151 }
152
153 pub fn intern(&self, text: &str) -> Result<u32, crate::Error> {
159 if let Some(&id) = self
160 .inner
161 .read()
162 .unwrap_or_else(PoisonError::into_inner)
163 .ids
164 .get(text)
165 {
166 return Ok(id);
167 }
168 let mut inner = self.inner.write().unwrap_or_else(PoisonError::into_inner);
169 if let Some(&id) = inner.ids.get(text) {
170 return Ok(id);
171 }
172 if self.sealed.load(AtomicOrdering::Acquire) {
173 return Err(crate::Error::unsupported(format!(
174 "the string or name {text:?}, which TLC first meets after start-up: its place in TLC's string order depends on evaluation order (--compat=tlc)"
175 )));
176 }
177 let id = u32::try_from(inner.texts.len())
178 .map_err(|_| crate::Error::unsupported("more than 2^32 distinct strings"))?;
179 let text: Arc<str> = text.into();
180 inner.payload_bytes += text.len();
181 inner.longest_bytes = inner.longest_bytes.max(text.len());
182 inner.texts.push(text.clone());
183 inner.ids.insert(text, id);
184 Ok(id)
185 }
186
187 #[must_use]
189 pub fn text(&self, id: u32) -> Option<Arc<str>> {
190 self.inner
191 .read()
192 .unwrap_or_else(PoisonError::into_inner)
193 .texts
194 .get(id as usize)
195 .cloned()
196 }
197
198 #[must_use]
202 pub fn texts_from(&self, start: usize) -> Vec<Arc<str>> {
203 self.inner
204 .read()
205 .unwrap_or_else(PoisonError::into_inner)
206 .texts
207 .get(start..)
208 .map(<[Arc<str>]>::to_vec)
209 .unwrap_or_default()
210 }
211
212 #[must_use]
214 pub fn cmp(&self, a: u32, b: u32) -> std::cmp::Ordering {
215 if a == b {
216 return std::cmp::Ordering::Equal;
217 }
218 if self.order == StringOrder::Token {
219 return a.cmp(&b);
220 }
221 let inner = self.inner.read().unwrap_or_else(PoisonError::into_inner);
222 match (inner.texts.get(a as usize), inner.texts.get(b as usize)) {
223 (Some(x), Some(y)) => x.cmp(y),
224 _ => a.cmp(&b),
225 }
226 }
227
228 #[must_use]
238 pub fn ranks(&self) -> Arc<[u32]> {
239 {
240 let inner = self.inner.read().unwrap_or_else(PoisonError::into_inner);
241 if !rank_stale(inner.ranks.len(), inner.texts.len()) {
242 return inner.ranks.clone();
243 }
244 }
245 let mut inner = self.inner.write().unwrap_or_else(PoisonError::into_inner);
246 if rank_stale(inner.ranks.len(), inner.texts.len()) {
247 if let Ok(len) = u32::try_from(inner.texts.len()) {
250 let mut order: Vec<u32> = (0..len).collect();
251 if self.order == StringOrder::Text {
252 let texts = &inner.texts;
253 order.sort_unstable_by(|&a, &b| texts[a as usize].cmp(&texts[b as usize]));
254 }
255 let mut ranks = vec![0; order.len()];
256 for (rank, id) in (0u32..).zip(order) {
257 ranks[id as usize] = rank;
258 }
259 inner.ranks = ranks.into();
260 }
261 }
262 inner.ranks.clone()
263 }
264
265 #[must_use]
269 pub fn longest_text_bytes(&self) -> usize {
270 self.inner
271 .read()
272 .unwrap_or_else(PoisonError::into_inner)
273 .longest_bytes
274 }
275
276 #[must_use]
278 pub fn len(&self) -> usize {
279 self.inner
280 .read()
281 .unwrap_or_else(PoisonError::into_inner)
282 .texts
283 .len()
284 }
285
286 #[must_use]
288 pub fn is_empty(&self) -> bool {
289 self.len() == 0
290 }
291
292 #[must_use]
296 pub fn memory_usage(&self) -> StringsMemory {
297 let inner = self.inner.read().unwrap_or_else(PoisonError::into_inner);
298 StringsMemory {
299 payload_bytes: inner.payload_bytes,
300 text_slots_bytes: inner.texts.capacity() * std::mem::size_of::<Arc<str>>(),
301 index_entries_bytes: inner.ids.len()
302 * (std::mem::size_of::<Arc<str>>() + std::mem::size_of::<u32>()),
303 index_capacity: inner.ids.capacity(),
304 strings: inner.texts.len(),
305 }
306 }
307}
308
309#[cfg(test)]
310mod tests {
311 use std::cmp::Ordering;
312
313 use super::*;
314
315 #[test]
316 fn memory_counts_unique_utf8_and_exposes_opaque_index_capacity() {
317 let table = Strings::default();
318 let _ = table.intern("alpha");
319 let _ = table.intern("β");
320 let _ = table.intern("");
321 let before = table.memory_usage();
322 assert_eq!(before.payload_bytes, 7);
323 assert_eq!(before.strings, 3);
324 assert!(before.index_capacity >= 3);
325 assert!(before.text_slots_bytes >= 3 * std::mem::size_of::<Arc<str>>());
326 let reader = table.text(0);
327 let _ = table.intern("alpha");
328 assert_eq!(table.memory_usage(), before, "shared strings count once");
329 drop(reader);
330 {
331 let mut inner = table.inner.write().unwrap_or_else(PoisonError::into_inner);
332 inner.texts.reserve(100);
333 inner.ids.reserve(100);
334 }
335 let after = table.memory_usage();
336 assert_eq!(after.payload_bytes, before.payload_bytes);
337 assert_eq!(after.index_entries_bytes, before.index_entries_bytes);
338 assert!(after.text_slots_bytes > before.text_slots_bytes);
339 assert!(after.index_capacity > before.index_capacity);
340 assert_eq!(
341 after
342 .known_retained_bytes()
343 .and_then(|n| n.checked_sub(after.text_slots_bytes)),
344 before
345 .known_retained_bytes()
346 .and_then(|n| n.checked_sub(before.text_slots_bytes)),
347 "opaque hash bucket bytes are not invented from logical capacity"
348 );
349 }
350
351 #[test]
352 fn a_sealed_table_refuses_new_strings_only() {
353 let t = Strings::new(StringOrder::Token);
354 assert!(t.preload(["zeta", "alpha"]).is_ok());
355 t.seal();
356 assert_eq!(t.intern("alpha").ok(), Some(1));
357 assert!(t.intern("beta").is_err());
358 }
359
360 #[test]
361 fn longest_text_bytes_grows_with_new_texts_only() {
362 let t = Strings::new(StringOrder::Text);
363 assert_eq!(t.longest_text_bytes(), 0);
364 assert!(t.intern("abc").is_ok());
365 assert!(t.intern("\u{e9}").is_ok());
366 assert_eq!(t.longest_text_bytes(), 3);
367 assert!(t.intern("abcdef").is_ok());
368 assert!(t.intern("abc").is_ok());
369 assert_eq!(t.longest_text_bytes(), 6);
370 }
371
372 #[test]
373 fn text_order_ignores_encounter_order() {
374 let t = Strings::new(StringOrder::Text);
375 let (b, a) = (t.intern("b").unwrap_or(0), t.intern("a").unwrap_or(0));
376 assert_eq!(t.cmp(a, b), Ordering::Less);
377 }
378
379 #[test]
383 fn ranks_follow_the_table_order_as_it_grows() {
384 for order in [StringOrder::Text, StringOrder::Token] {
385 let t = Strings::new(order);
386 let mut snapshots = Vec::new();
387 for text in ["m", "c", "x", "", "cc", "b", "\u{e9}", "z", "a", "mm"] {
388 assert!(t.intern(text).is_ok());
389 snapshots.push(t.ranks());
390 }
391 let n = u32::try_from(t.len()).unwrap_or(0);
392 for ranks in &snapshots {
393 for a in 0..n {
394 for b in 0..n {
395 if let (Some(x), Some(y)) = (ranks.get(a as usize), ranks.get(b as usize)) {
396 assert_eq!(x.cmp(y), t.cmp(a, b), "{order:?} {a} {b}");
397 }
398 }
399 }
400 }
401 assert_eq!(snapshots.last().map(|r| r.len()), Some(t.len()));
402 }
403 }
404
405 #[test]
408 fn large_tables_rank_new_strings_in_batches() {
409 let t = Strings::new(StringOrder::Text);
410 for n in (0..2048).rev() {
411 assert!(t.intern(&format!("s{n:05}")).is_ok());
412 }
413 assert_eq!(t.ranks().len(), 2048);
414 assert!(t.intern("a").is_ok());
415 assert_eq!(t.ranks().len(), 2048, "one new string waits");
416 for n in 0..256 {
417 assert!(t.intern(&format!("t{n}")).is_ok());
418 }
419 let ranks = t.ranks();
420 assert_eq!(ranks.len(), t.len());
421 let a = t.lookup("a").unwrap_or(0);
422 assert_eq!(ranks.get(a as usize), Some(&0));
423 }
424
425 #[test]
426 fn token_order_follows_preloaded_encounter_order() {
427 let t = Strings::new(StringOrder::Token);
428 assert!(t.preload(["zeta", "alpha", "mid"]).is_ok());
429 let ids: Vec<u32> = ["alpha", "zeta", "mid", "new"]
430 .iter()
431 .map(|s| t.intern(s).unwrap_or(u32::MAX))
432 .collect();
433 assert_eq!(t.cmp(ids[1], ids[0]), Ordering::Less, "zeta was first");
434 assert_eq!(t.cmp(ids[0], ids[2]), Ordering::Less);
435 assert_eq!(t.cmp(ids[2], ids[3]), Ordering::Less, "runtime names last");
436 assert!(t.preload(["zeta", "alpha"]).is_ok());
439 let late = Strings::new(StringOrder::Token);
440 let _ = late.intern("x");
441 assert!(late.preload(["y"]).is_err());
442 }
443}