oxide_core/heap/
string.rs

1//! String records: flat, or a rope.
2//!
3//! The flat representation is canonical: a string whose code units all fit
4//! in one byte is always `OneByte`, so two records with equal content have
5//! equal representations. A rope is a concatenation of two strings that
6//! flattens on the first use of its units ([`super::Heap::string`]); its
7//! length and width are known without flattening.
8
9use std::cell::{Cell, OnceCell};
10
11use super::arena::Record;
12use super::object::NONE;
13
14#[derive(Clone, Debug, PartialEq, Eq)]
15pub enum StringRepr {
16    OneByte(Box<[u8]>),
17    TwoByte(Box<[u16]>),
18}
19
20impl StringRepr {
21    pub fn from_text(text: &str) -> StringRepr {
22        if text.is_ascii() {
23            return StringRepr::OneByte(text.as_bytes().into());
24        }
25        let units: Vec<u16> = text.encode_utf16().collect();
26        StringRepr::from_units(&units)
27    }
28
29    pub fn from_units(units: &[u16]) -> StringRepr {
30        if units.iter().all(|&unit| unit <= 0xFF) {
31            StringRepr::OneByte(units.iter().map(|&unit| unit as u8).collect())
32        } else {
33            StringRepr::TwoByte(units.into())
34        }
35    }
36
37    pub fn len(&self) -> usize {
38        match self {
39            StringRepr::OneByte(bytes) => bytes.len(),
40            StringRepr::TwoByte(units) => units.len(),
41        }
42    }
43
44    pub fn is_empty(&self) -> bool {
45        self.len() == 0
46    }
47
48    pub fn unit(&self, index: usize) -> u16 {
49        match self {
50            StringRepr::OneByte(bytes) => u16::from(bytes[index]),
51            StringRepr::TwoByte(units) => units[index],
52        }
53    }
54
55    pub fn units(&self) -> impl Iterator<Item = u16> + '_ {
56        (0..self.len()).map(|index| self.unit(index))
57    }
58
59    pub fn content_bytes(&self) -> usize {
60        match self {
61            StringRepr::OneByte(bytes) => bytes.len(),
62            StringRepr::TwoByte(units) => units.len() * 2,
63        }
64    }
65
66    /// Lossy conversion for diagnostics and tests.
67    pub fn to_rust_string(&self) -> String {
68        match self {
69            StringRepr::OneByte(bytes) => bytes.iter().map(|&byte| char::from(byte)).collect(),
70            StringRepr::TwoByte(units) => String::from_utf16_lossy(units),
71        }
72    }
73
74    /// The canonical array index (`0 ..= 2^32 - 2`) this string spells, if any.
75    pub fn array_index(&self) -> Option<u32> {
76        array_index(self.len(), self.units())
77    }
78
79    pub fn content_hash(&self) -> u32 {
80        content_hash(self.units())
81    }
82}
83
84/// The canonical array index (`0 ..= 2^32 - 2`) that `len` units spell, if any.
85pub fn array_index(len: usize, mut units: impl Iterator<Item = u16>) -> Option<u32> {
86    if len == 0 || len > 10 {
87        return None;
88    }
89    let first = units.next()?;
90    if first == u16::from(b'0') {
91        return (len == 1).then_some(0);
92    }
93    let mut value: u64 = 0;
94    for unit in std::iter::once(first).chain(units) {
95        let digit = unit
96            .checked_sub(u16::from(b'0'))
97            .filter(|digit| *digit <= 9)?;
98        value = value * 10 + u64::from(digit);
99    }
100    (value < u64::from(u32::MAX)).then_some(value as u32)
101}
102
103pub fn content_hash(units: impl Iterator<Item = u16>) -> u32 {
104    let mut hash: u32 = 0x811C_9DC5;
105    for unit in units {
106        hash = (hash ^ u32::from(unit)).wrapping_mul(0x0100_0193);
107    }
108    hash
109}
110
111/// What keeps an atom alive besides its holders.
112#[derive(Clone, Copy, PartialEq, Eq, Debug)]
113pub enum AtomKeep {
114    /// Nothing: it lives while a value, shape or unit names it.
115    Weak,
116    /// On `Heap::held_atoms`, until its compilation ends
117    /// ([`super::AtomMode::Hold`]).
118    Held,
119    /// The heap's lifetime ([`super::AtomMode::Pin`]).
120    Pinned,
121}
122
123pub struct StringRecord {
124    /// The units; unset while the record is an unflattened rope (whose
125    /// halves are in `Heap::ropes`).
126    flat: OnceCell<StringRepr>,
127    len: u32,
128    one_byte: bool,
129    born_rope: bool,
130    /// Computed on first use; 0 means not yet computed.
131    hash: Cell<u32>,
132    pub is_atom: bool,
133    /// What keeps an atom alive besides its holders.
134    pub keep: AtomKeep,
135    /// For atoms spelling an array index too large for an immediate
136    /// `PropertyKey`: that index, else [`NONE`].
137    pub array_index: u32,
138}
139
140const _: () = assert!(size_of::<StringRecord>() <= 40);
141
142impl StringRecord {
143    pub fn new(repr: StringRepr) -> Self {
144        let len = repr.len() as u32;
145        let one_byte = matches!(repr, StringRepr::OneByte(_));
146        StringRecord {
147            flat: OnceCell::from(repr),
148            len,
149            one_byte,
150            born_rope: false,
151            hash: Cell::new(0),
152            is_atom: false,
153            keep: AtomKeep::Weak,
154            array_index: NONE,
155        }
156    }
157
158    /// A rope `len` units long; the heap records its halves.
159    pub fn rope(len: u32, one_byte: bool) -> Self {
160        StringRecord {
161            flat: OnceCell::new(),
162            len,
163            one_byte,
164            born_rope: true,
165            hash: Cell::new(0),
166            is_atom: false,
167            keep: AtomKeep::Weak,
168            array_index: NONE,
169        }
170    }
171
172    /// The units. A rope reached through [`super::Heap::string`] is flat.
173    #[inline]
174    pub fn repr(&self) -> &StringRepr {
175        self.flat.get().expect("a flattened string")
176    }
177
178    pub(crate) fn flat(&self) -> Option<&StringRepr> {
179        self.flat.get()
180    }
181
182    pub(crate) fn set_flat(&self, repr: StringRepr) {
183        let _ = self.flat.set(repr);
184    }
185
186    /// The bytes a flattened rope holds, which the heap counts (the arena
187    /// counted the rope as empty).
188    pub(crate) fn flattened_rope_bytes(&self) -> usize {
189        match self.flat.get() {
190            Some(flat) if self.born_rope => flat.content_bytes(),
191            _ => 0,
192        }
193    }
194
195    #[inline]
196    pub fn len(&self) -> usize {
197        self.len as usize
198    }
199
200    #[inline]
201    pub fn is_empty(&self) -> bool {
202        self.len == 0
203    }
204
205    #[inline]
206    pub fn is_one_byte(&self) -> bool {
207        self.one_byte
208    }
209
210    pub fn hash(&self) -> u32 {
211        let cached = self.hash.get();
212        if cached != 0 {
213            return cached;
214        }
215        let hash = self.repr().content_hash().max(1);
216        self.hash.set(hash);
217        hash
218    }
219}
220
221impl Record for StringRecord {
222    fn vacant() -> Self {
223        StringRecord::new(StringRepr::OneByte(Box::new([])))
224    }
225
226    fn extra_bytes(&self) -> usize {
227        match self.flat.get() {
228            Some(flat) if !self.born_rope => flat.content_bytes(),
229            _ => 0,
230        }
231    }
232}
233
234#[cfg(test)]
235mod tests {
236    use super::*;
237
238    #[test]
239    fn representation_is_canonical() {
240        assert_eq!(
241            StringRepr::from_text("abc"),
242            StringRepr::OneByte(b"abc".to_vec().into())
243        );
244        assert_eq!(
245            StringRepr::from_text("caf\u{e9}"),
246            StringRepr::from_units(&[99, 97, 102, 0xE9])
247        );
248        assert!(matches!(
249            StringRepr::from_text("\u{3b1}"),
250            StringRepr::TwoByte(_)
251        ));
252        assert_eq!(StringRepr::from_text("\u{1F600}").len(), 2);
253        assert_eq!(
254            StringRepr::from_text("\u{3b1}x").to_rust_string(),
255            "\u{3b1}x"
256        );
257    }
258
259    #[test]
260    fn array_index_is_canonical_u32_below_max() {
261        let index = |text: &str| StringRepr::from_text(text).array_index();
262        assert_eq!(index("0"), Some(0));
263        assert_eq!(index("10"), Some(10));
264        assert_eq!(index("4294967294"), Some(u32::MAX - 1));
265        assert_eq!(index("4294967295"), None);
266        assert_eq!(index("01"), None);
267        assert_eq!(index(""), None);
268        assert_eq!(index("-1"), None);
269        assert_eq!(index("99999999999"), None);
270    }
271}
oxide_core/heap/string.rs

oxide_core/heap/
string.rs
