sim_lib_lang_javascript/
collections.rs

1//! ECMAScript collection policy composed over shared sequence semantics.
2
3use crate::JavascriptValue;
4use sim_lib_sequence::{
5    OrderedSet, OrderedSetIter, OrderedTable, OrderedTableIter, SparseSequence,
6};
7use std::collections::BTreeMap;
8
9const MAX_ARRAY_LENGTH: usize = u32::MAX as usize;
10
11/// A unique ECMAScript Symbol identity.
12#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
13pub struct JavascriptSymbol {
14    id: u64,
15    description: Option<String>,
16}
17impl JavascriptSymbol {
18    /// Stable identity allocated by a registry.
19    pub fn id(&self) -> u64 {
20        self.id
21    }
22    /// Optional descriptive text; it never participates in identity.
23    pub fn description(&self) -> Option<&str> {
24        self.description.as_deref()
25    }
26}
27
28/// Realm-local allocator and global-symbol registry.
29#[derive(Clone, Debug, Default)]
30pub struct JavascriptSymbolRegistry {
31    next: u64,
32    globals: BTreeMap<String, JavascriptSymbol>,
33}
34impl JavascriptSymbolRegistry {
35    /// Allocate a fresh symbol.
36    pub fn symbol(&mut self, description: Option<String>) -> JavascriptSymbol {
37        let symbol = JavascriptSymbol {
38            id: self.next,
39            description,
40        };
41        self.next += 1;
42        symbol
43    }
44    /// Return the stable `Symbol.for` identity for `key`.
45    pub fn symbol_for(&mut self, key: impl Into<String>) -> JavascriptSymbol {
46        let key = key.into();
47        if let Some(symbol) = self.globals.get(&key) {
48            return symbol.clone();
49        }
50        let symbol = self.symbol(Some(key.clone()));
51        self.globals.insert(key, symbol.clone());
52        symbol
53    }
54    /// Recover the `Symbol.for` key, if any.
55    pub fn key_for(&self, symbol: &JavascriptSymbol) -> Option<&str> {
56        self.globals
57            .iter()
58            .find_map(|(key, value)| (value == symbol).then_some(key.as_str()))
59    }
60}
61
62/// Failure from a bounded collection method.
63#[derive(Clone, Debug, Eq, PartialEq)]
64pub enum JavascriptCollectionError {
65    /// A sparse or explicit index is outside the collection.
66    Index,
67    /// The caller's explicit work bound was exhausted.
68    Limit,
69}
70
71/// ECMAScript array with explicit holes distinct from `undefined`.
72#[derive(Clone, Debug, PartialEq)]
73pub struct JavascriptArray {
74    elements: SparseSequence<JavascriptValue>,
75}
76impl Default for JavascriptArray {
77    fn default() -> Self {
78        Self::sparse(0)
79    }
80}
81impl JavascriptArray {
82    /// Construct a dense array.
83    pub fn dense(values: Vec<JavascriptValue>) -> Self {
84        let mut elements = SparseSequence::new(MAX_ARRAY_LENGTH);
85        for (index, value) in values.into_iter().enumerate() {
86            elements
87                .set(index, value)
88                .expect("a materialized vector has a valid JavaScript array length");
89        }
90        Self { elements }
91    }
92    /// Construct with an explicit length and holes.
93    pub fn sparse(length: usize) -> Self {
94        assert!(
95            length <= MAX_ARRAY_LENGTH,
96            "invalid JavaScript array length"
97        );
98        let mut elements = SparseSequence::new(MAX_ARRAY_LENGTH);
99        elements.set_len(length).expect("length was checked");
100        Self { elements }
101    }
102    /// ECMAScript length.
103    pub fn len(&self) -> usize {
104        self.elements.len()
105    }
106    /// Whether length is zero.
107    pub fn is_empty(&self) -> bool {
108        self.elements.is_empty()
109    }
110    /// Read an own indexed element; holes remain distinguishable.
111    pub fn get(&self, index: usize) -> Option<&JavascriptValue> {
112        self.elements.get(index)
113    }
114    /// Set an index, growing through holes as JavaScript arrays do.
115    pub fn set(&mut self, index: usize, value: JavascriptValue) {
116        self.elements
117            .set(index, value)
118            .expect("invalid JavaScript array index");
119    }
120    /// Set the ECMAScript length, creating holes or deleting truncated values.
121    pub fn set_len(&mut self, length: usize) -> Result<(), JavascriptCollectionError> {
122        self.elements
123            .set_len(length)
124            .map_err(|_| JavascriptCollectionError::Index)
125    }
126    /// Append and return the new length.
127    pub fn push(&mut self, value: JavascriptValue) -> usize {
128        self.set(self.len(), value);
129        self.len()
130    }
131    /// Remove and return the last element (`undefined` and a hole both return `None` at this policy seam).
132    pub fn pop(&mut self) -> Option<JavascriptValue> {
133        let index = self.len().checked_sub(1)?;
134        let value = self.elements.remove(index);
135        self.elements
136            .set_len(index)
137            .expect("shrinking an array length is valid");
138        value
139    }
140    /// JavaScript array iterator: holes are observed as `undefined`.
141    pub fn values(&self) -> JavascriptIterator {
142        JavascriptIterator::new(
143            (0..self.len())
144                .map(|index| {
145                    self.get(index)
146                        .cloned()
147                        .unwrap_or(JavascriptValue::Undefined)
148                })
149                .collect(),
150        )
151    }
152    /// Bounded `forEach`; callbacks skip holes.
153    pub fn for_each(
154        &self,
155        max_visits: usize,
156        mut f: impl FnMut(&JavascriptValue, usize),
157    ) -> Result<(), JavascriptCollectionError> {
158        for (visit, (index, value)) in self.elements.occupied_in(..).enumerate() {
159            if visit >= max_visits {
160                return Err(JavascriptCollectionError::Limit);
161            }
162            f(value, index);
163        }
164        Ok(())
165    }
166    /// Bounded `map`; callbacks skip holes and holes are retained.
167    pub fn map(
168        &self,
169        max_visits: usize,
170        mut f: impl FnMut(&JavascriptValue, usize) -> JavascriptValue,
171    ) -> Result<Self, JavascriptCollectionError> {
172        let visits = self.elements.occupied_len();
173        if visits > max_visits {
174            return Err(JavascriptCollectionError::Limit);
175        }
176        let mut out = Self::sparse(self.len());
177        for (index, value) in self.elements.occupied_in(..) {
178            out.set(index, f(value, index));
179        }
180        Ok(out)
181    }
182    /// Bounded `filter`; callbacks skip holes and the result is dense.
183    pub fn filter(
184        &self,
185        max_visits: usize,
186        mut f: impl FnMut(&JavascriptValue, usize) -> bool,
187    ) -> Result<Self, JavascriptCollectionError> {
188        let mut out = Self::default();
189        let mut visits = 0;
190        for (i, value) in self.elements.occupied_in(..) {
191            visits += 1;
192            if visits > max_visits {
193                return Err(JavascriptCollectionError::Limit);
194            }
195            if f(value, i) {
196                out.push(value.clone());
197            }
198        }
199        Ok(out)
200    }
201}
202
203/// Insertion-ordered ECMAScript Map using SameValueZero-style scalar keys.
204#[derive(Debug)]
205pub struct JavascriptMap {
206    entries: OrderedTable<JavascriptValue, JavascriptValue, SameValueZero>,
207}
208impl Default for JavascriptMap {
209    fn default() -> Self {
210        Self {
211            entries: OrderedTable::new(SameValueZero),
212        }
213    }
214}
215impl Clone for JavascriptMap {
216    fn clone(&self) -> Self {
217        let copy = Self::default();
218        for (key, value) in self.entries.iter() {
219            copy.entries.insert(key, value);
220        }
221        copy
222    }
223}
224impl PartialEq for JavascriptMap {
225    fn eq(&self, other: &Self) -> bool {
226        self.entries.iter().collect::<Vec<_>>() == other.entries.iter().collect::<Vec<_>>()
227    }
228}
229impl JavascriptMap {
230    /// Insert or replace without changing insertion position.
231    pub fn set(&mut self, key: JavascriptValue, value: JavascriptValue) {
232        self.entries.insert(key, value);
233    }
234    /// Lookup a value.
235    pub fn get(&self, key: &JavascriptValue) -> Option<JavascriptValue> {
236        self.entries.get(key)
237    }
238    /// Delete a key.
239    pub fn delete(&mut self, key: &JavascriptValue) -> bool {
240        self.entries.remove(key).is_some()
241    }
242    /// Entry count.
243    pub fn len(&self) -> usize {
244        self.entries.len()
245    }
246    /// Whether empty.
247    pub fn is_empty(&self) -> bool {
248        self.entries.is_empty()
249    }
250    /// Insertion-ordered entries.
251    pub fn entries(&self) -> OrderedTableIter<JavascriptValue, JavascriptValue> {
252        self.entries.iter()
253    }
254}
255
256/// Insertion-ordered ECMAScript Set.
257#[derive(Debug)]
258pub struct JavascriptSet {
259    values: OrderedSet<JavascriptValue, SameValueZero>,
260}
261impl Default for JavascriptSet {
262    fn default() -> Self {
263        Self {
264            values: OrderedSet::new(SameValueZero),
265        }
266    }
267}
268impl Clone for JavascriptSet {
269    fn clone(&self) -> Self {
270        let copy = Self::default();
271        for value in self.values.iter() {
272            copy.values.insert(value);
273        }
274        copy
275    }
276}
277impl PartialEq for JavascriptSet {
278    fn eq(&self, other: &Self) -> bool {
279        self.values.iter().collect::<Vec<_>>() == other.values.iter().collect::<Vec<_>>()
280    }
281}
282impl JavascriptSet {
283    /// Add a value with SameValueZero uniqueness.
284    pub fn add(&mut self, value: JavascriptValue) {
285        self.values.insert(value);
286    }
287    /// Membership query.
288    pub fn has(&self, value: &JavascriptValue) -> bool {
289        self.values.contains(value)
290    }
291    /// Delete a value.
292    pub fn delete(&mut self, value: &JavascriptValue) -> bool {
293        self.values.remove(value)
294    }
295    /// Value count.
296    pub fn len(&self) -> usize {
297        self.values.len()
298    }
299    /// Whether empty.
300    pub fn is_empty(&self) -> bool {
301        self.values.is_empty()
302    }
303    /// Insertion-ordered values.
304    pub fn values(&self) -> JavascriptIterator {
305        JavascriptIterator::live(self.values.iter())
306    }
307}
308
309/// One iterator result cell.
310#[derive(Clone, Debug, PartialEq)]
311pub struct JavascriptIteratorResult {
312    /// Produced value, absent after completion.
313    pub value: Option<JavascriptValue>,
314    /// ECMAScript `done` flag.
315    pub done: bool,
316}
317/// Bounded, stateful ECMAScript iterator cell.
318#[derive(Clone, Debug)]
319pub struct JavascriptIterator {
320    source: JavascriptIteratorSource,
321}
322#[derive(Clone)]
323enum JavascriptIteratorSource {
324    Snapshot(std::vec::IntoIter<JavascriptValue>),
325    Live(OrderedSetIter<JavascriptValue>),
326}
327impl std::fmt::Debug for JavascriptIteratorSource {
328    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
329        formatter.write_str(match self {
330            Self::Snapshot(_) => "Snapshot",
331            Self::Live(_) => "Live",
332        })
333    }
334}
335impl JavascriptIterator {
336    /// Build an iterator over an owned snapshot.
337    pub fn new(values: Vec<JavascriptValue>) -> Self {
338        Self {
339            source: JavascriptIteratorSource::Snapshot(values.into_iter()),
340        }
341    }
342    fn live(values: OrderedSetIter<JavascriptValue>) -> Self {
343        Self {
344            source: JavascriptIteratorSource::Live(values),
345        }
346    }
347    /// Execute the iterator protocol's `next` method.
348    pub fn next_result(&mut self) -> JavascriptIteratorResult {
349        let value = match &mut self.source {
350            JavascriptIteratorSource::Snapshot(values) => values.next(),
351            JavascriptIteratorSource::Live(values) => values.next(),
352        };
353        if let Some(value) = value {
354            JavascriptIteratorResult {
355                value: Some(value),
356                done: false,
357            }
358        } else {
359            JavascriptIteratorResult {
360                value: None,
361                done: true,
362            }
363        }
364    }
365}
366#[derive(Clone, Copy, Debug, Default)]
367struct SameValueZero;
368impl sim_lib_sequence::KeyEquivalence<JavascriptValue> for SameValueZero {
369    fn equivalent(&self, left: &JavascriptValue, right: &JavascriptValue) -> bool {
370        match (left, right) {
371            (JavascriptValue::Number(a), JavascriptValue::Number(b)) => {
372                a == b || (a.is_nan() && b.is_nan())
373            }
374            _ => left == right,
375        }
376    }
377}
378
379#[cfg(test)]
380mod tests {
381    use super::*;
382    #[test]
383    fn arrays_preserve_holes_and_iterators_materialize_undefined() {
384        let mut a = JavascriptArray::sparse(2);
385        a.set(1, JavascriptValue::Number(2.));
386        assert_eq!(a.map(1, |v, _| v.clone()).unwrap().get(0), None);
387        let mut it = a.values();
388        assert_eq!(it.next_result().value, Some(JavascriptValue::Undefined));
389        assert!(!it.next_result().done);
390        assert!(it.next_result().done);
391    }
392    #[test]
393    fn array_callbacks_skip_holes_and_length_truncation_deletes_values() {
394        let mut array = JavascriptArray::sparse(4);
395        array.set(1, JavascriptValue::Number(1.));
396        array.set(3, JavascriptValue::Number(3.));
397        let mut visited = Vec::new();
398        array.for_each(2, |_, index| visited.push(index)).unwrap();
399        assert_eq!(visited, vec![1, 3]);
400        assert_eq!(array.get(0), None);
401
402        array.set_len(2).unwrap();
403        assert_eq!(array.len(), 2);
404        assert_eq!(array.get(1), Some(&JavascriptValue::Number(1.)));
405        assert_eq!(array.get(3), None);
406        array.set_len(4).unwrap();
407        assert_eq!(array.get(3), None);
408    }
409    #[test]
410    fn map_nan_keys_match_themselves() {
411        let mut m = JavascriptMap::default();
412        m.set(
413            JavascriptValue::Number(f64::NAN),
414            JavascriptValue::Number(1.),
415        );
416        m.set(
417            JavascriptValue::Number(f64::NAN),
418            JavascriptValue::Number(2.),
419        );
420        assert_eq!(m.len(), 1);
421        assert_eq!(
422            m.get(&JavascriptValue::Number(f64::NAN)),
423            Some(JavascriptValue::Number(2.))
424        );
425    }
426    #[test]
427    fn set_positive_and_negative_zero_are_the_same_key() {
428        let mut s = JavascriptSet::default();
429        s.add(JavascriptValue::Number(-0.));
430        s.add(JavascriptValue::Number(0.));
431        assert_eq!(s.len(), 1);
432    }
433    #[test]
434    fn map_replacement_keeps_position() {
435        let mut map = JavascriptMap::default();
436        map.set(
437            JavascriptValue::String("first".into()),
438            JavascriptValue::Number(1.),
439        );
440        map.set(
441            JavascriptValue::String("second".into()),
442            JavascriptValue::Number(2.),
443        );
444        map.set(
445            JavascriptValue::String("first".into()),
446            JavascriptValue::Number(3.),
447        );
448
449        assert_eq!(
450            map.entries().collect::<Vec<_>>(),
451            vec![
452                (
453                    JavascriptValue::String("first".into()),
454                    JavascriptValue::Number(3.)
455                ),
456                (
457                    JavascriptValue::String("second".into()),
458                    JavascriptValue::Number(2.)
459                ),
460            ]
461        );
462    }
463    #[test]
464    fn set_delete_then_reinsert_moves_to_the_end() {
465        let mut set = JavascriptSet::default();
466        set.add(JavascriptValue::String("first".into()));
467        set.add(JavascriptValue::String("second".into()));
468        assert!(set.delete(&JavascriptValue::String("first".into())));
469        set.add(JavascriptValue::String("first".into()));
470
471        let mut values = set.values();
472        assert_eq!(
473            values.next_result().value,
474            Some(JavascriptValue::String("second".into()))
475        );
476        assert_eq!(
477            values.next_result().value,
478            Some(JavascriptValue::String("first".into()))
479        );
480    }
481    #[test]
482    fn collection_iterators_visit_entries_added_during_iteration() {
483        let mut map = JavascriptMap::default();
484        map.set(
485            JavascriptValue::String("first".into()),
486            JavascriptValue::Number(1.),
487        );
488        let mut entries = map.entries();
489        assert_eq!(
490            entries.next().unwrap().0,
491            JavascriptValue::String("first".into())
492        );
493        map.set(
494            JavascriptValue::String("second".into()),
495            JavascriptValue::Number(2.),
496        );
497        assert_eq!(
498            entries.next().unwrap().0,
499            JavascriptValue::String("second".into())
500        );
501
502        let mut set = JavascriptSet::default();
503        set.add(JavascriptValue::String("first".into()));
504        let mut values = set.values();
505        assert_eq!(
506            values.next_result().value,
507            Some(JavascriptValue::String("first".into()))
508        );
509        set.add(JavascriptValue::String("second".into()));
510        assert_eq!(
511            values.next_result().value,
512            Some(JavascriptValue::String("second".into()))
513        );
514    }
515    #[test]
516    fn symbols_have_identity_and_registry_keys() {
517        let mut r = JavascriptSymbolRegistry::default();
518        assert_ne!(r.symbol(Some("x".into())), r.symbol(Some("x".into())));
519        let s = r.symbol_for("x");
520        assert_eq!(s, r.symbol_for("x"));
521        assert_eq!(r.key_for(&s), Some("x"));
522    }
523}
sim_lib_lang_javascript/collections.rs

sim_lib_lang_javascript/
collections.rs
