Skip to main content

dive_core/
strings.rs

1//! The global, append-only string table.
2//!
3//! Ids are assigned on first encounter. The default profile orders strings by
4//! their UTF-8 bytes ([`StringOrder::Text`]), so ids carry no order there.
5//! Under `--compat=tlc` strings compare by intern token
6//! ([`StringOrder::Token`]), which reproduces `UniqueString.compareTo`: the
7//! id is the token, so the table must first be fed TLC's startup encounter
8//! order with [`Strings::preload`].
9
10use std::collections::HashMap;
11use std::sync::atomic::{AtomicBool, Ordering as AtomicOrdering};
12use std::sync::{Arc, PoisonError, RwLock};
13
14/// How strings compare.
15#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
16pub enum StringOrder {
17    /// By UTF-8 bytes: the default profile's canonical order.
18    #[default]
19    Text,
20    /// By intern token, in encounter order: TLC's order.
21    Token,
22}
23
24/// The string table.
25#[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    /// The dense rank of each id below `ranks.len()` in the table's order
39    /// among those ids ([`Strings::ranks`]).
40    ranks: Arc<[u32]>,
41}
42
43/// Up to this many strings, [`Strings::ranks`] ranks every new string at
44/// once; past it, only once the unranked ids reach an eighth of the ranked
45/// ones, so ranking a table that grows one string at a time costs a
46/// constant factor over sorting it once.
47const RANK_ALL_UP_TO: usize = 1024;
48
49/// Whether [`Strings::ranks`] should re-rank `len` ids of which `ranked`
50/// are ranked.
51fn 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/// Known storage and opaque index capacity of an append-only string table.
57///
58/// Text payload is counted once, even though the index, text vector and callers
59/// share each string. Arc control blocks, allocator overhead and the physical
60/// `HashMap` bucket allocation are not exposed by stable standard-library APIs.
61/// The rank index ([`Strings::ranks`]), which heaps share, is not counted.
62#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
63pub struct StringsMemory {
64    /// Unique UTF-8 payload bytes, excluding Arc control blocks.
65    pub payload_bytes: usize,
66    /// Allocated text-vector slots, including unused capacity.
67    pub text_slots_bytes: usize,
68    /// Live index key/value object bytes, excluding padding and vacant buckets.
69    pub index_entries_bytes: usize,
70    /// Logical `HashMap` capacity; this is not a physical bucket-byte count.
71    pub index_capacity: usize,
72    /// Unique strings retained by the table.
73    pub strings: usize,
74}
75
76impl StringsMemory {
77    /// A lower bound on dynamic retained bytes, or `None` on arithmetic overflow.
78    /// The containing [`Strings`] object itself is excluded.
79    #[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    /// An empty table with the given order.
89    #[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    /// The order strings compare in.
99    #[must_use]
100    pub fn order(&self) -> StringOrder {
101        self.order
102    }
103
104    /// Interns `texts` in the given order, so that under
105    /// [`StringOrder::Token`] they compare in that order. Call it before
106    /// anything else is interned: TLC's tokens are assigned in its startup
107    /// encounter order (configuration, built-ins, lexer tokens, semantic
108    /// names), and `dive-model`'s binder records that order.
109    ///
110    /// # Errors
111    /// `texts` repeats a string, or the table already holds strings that are
112    /// not a prefix of `texts`, so the tokens would not be TLC's; or more
113    /// than `u32::MAX` strings.
114    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    /// Refuses every later new string: under [`StringOrder::Token`] a string
129    /// TLC first meets during the search gets a token that depends on what
130    /// TLC evaluated before it, so after [`Strings::preload`] the run seals
131    /// the table rather than guess the order.
132    pub fn seal(&self) {
133        self.sealed.store(true, AtomicOrdering::Release);
134    }
135
136    /// Whether this table refuses every name absent from its current domain.
137    #[must_use]
138    pub fn is_sealed(&self) -> bool {
139        self.sealed.load(AtomicOrdering::Acquire)
140    }
141
142    /// The id of `text` if the table already holds it, never assigning one.
143    #[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    /// The id of `text`, assigning one if it is new.
154    ///
155    /// # Errors
156    /// More than `u32::MAX` strings; a new string after [`Strings::seal`]
157    /// (unsupported).
158    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    /// The text of an id.
188    #[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    /// The texts of the ids from `start` on, in id order, under one read
199    /// lock: a worker's heap copies them once instead of locking the table
200    /// on every comparison ([`crate::heap::Heap::cmp`]).
201    #[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    /// Compares two ids in the table's order: by text, or by token.
213    #[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    /// The dense rank of each id in the table's order, for the ids below
229    /// the result's length: comparing two ranks compares the two strings
230    /// as [`Strings::cmp`] does.
231    ///
232    /// Ranks are rebuilt here, not on every intern, so the ids interned
233    /// since the last rebuild may lie past the result; the caller compares
234    /// those by text. Interning shifts ranks but never reorders two ids
235    /// that were ranked together, so an earlier result still orders every
236    /// pair it covers.
237    #[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            // Ids are issued as `u32`, so their count fits unless the
248            // table is full; a full table keeps its earlier ranks.
249            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    /// The UTF-8 length of the longest text in the table so far. The table
266    /// is append-only, so every id it has issued names a text at most this
267    /// long: it bounds the work of one scan over any one current string.
268    #[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    /// The number of strings.
277    #[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    /// Whether the table is empty.
287    #[must_use]
288    pub fn is_empty(&self) -> bool {
289        self.len() == 0
290    }
291
292    /// Measures known dynamic storage without counting shared text twice.
293    /// The index's opaque bucket allocation is reported as logical capacity,
294    /// rather than inventing a physical byte count from that capacity.
295    #[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    /// Ranks order every pair they cover as [`Strings::cmp`] does, also
380    /// after strings are interned between and around ranked ones, and an
381    /// earlier rank copy stays valid for the pairs it covers.
382    #[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    /// Past [`RANK_ALL_UP_TO`] strings, a few new strings stay unranked
406    /// until enough accumulate, and ranking then covers them all.
407    #[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        // Preloading again with the same prefix is fine; after other names
437        // it is refused.
438        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}