boa_engine/builtins/set/
ordered_set.rs

1//! Implements a set type that preserves insertion order.
2
3use crate::{JsData, JsValue, builtins::map::ordered_map::MapKey, object::JsObject};
4use boa_gc::{Finalize, Trace, custom_trace};
5use indexmap::IndexSet;
6use std::fmt::Debug;
7
8/// A type wrapping `indexmap::IndexSet`
9#[derive(Default, Clone, Finalize, JsData)]
10pub struct OrderedSet {
11    inner: IndexSet<MapKey>,
12    lock: u32,
13    empty_count: usize,
14}
15
16unsafe impl Trace for OrderedSet {
17    custom_trace!(this, mark, {
18        for v in &this.inner {
19            if let MapKey::Key(v) = v {
20                mark(v);
21            }
22        }
23    });
24}
25
26impl Debug for OrderedSet {
27    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
28        self.inner.fmt(formatter)
29    }
30}
31
32impl OrderedSet {
33    /// Creates a new empty `OrderedSet`.
34    #[must_use]
35    pub fn new() -> Self {
36        Self::default()
37    }
38
39    /// Creates a new empty `OrderedSet` with the specified capacity.
40    #[must_use]
41    pub fn with_capacity(capacity: usize) -> Self {
42        Self {
43            inner: IndexSet::with_capacity(capacity),
44            lock: 0,
45            empty_count: 0,
46        }
47    }
48
49    /// Return the number of elements in the set, including empty elements.
50    ///
51    /// Computes in **O(1)** time.
52    #[must_use]
53    pub fn full_len(&self) -> usize {
54        self.inner.len()
55    }
56
57    /// Return the number of elements in the set.
58    ///
59    /// Computes in **O(1)** time.
60    #[must_use]
61    pub fn len(&self) -> usize {
62        self.inner.len() - self.empty_count
63    }
64
65    /// Returns true if the set contains no elements.
66    ///
67    /// Computes in **O(1)** time.
68    #[must_use]
69    pub fn is_empty(&self) -> bool {
70        self.inner.len() == 0
71    }
72
73    /// Insert a value pair in the set.
74    ///
75    /// If an equivalent value already exists in the set, returns `false` leaving
76    /// original value in the set and without altering its insertion order.
77    ///
78    /// If no equivalent value existed in the set, returns `true` and inserts
79    /// the new value at the end of the set.
80    ///
81    /// Computes in **O(1)** time (amortized average).
82    pub fn add(&mut self, value: JsValue) -> bool {
83        self.inner.insert(MapKey::Key(value))
84    }
85
86    /// Delete the `value` from the set and return true if successful
87    ///
88    /// Return `false` if `value` is not in set.
89    ///
90    /// Computes in **O(n)** time (average).
91    pub fn delete(&mut self, value: &JsValue) -> bool {
92        if self.lock == 0 {
93            self.inner.shift_remove(value)
94        } else if self.inner.contains(value) {
95            self.inner.insert(MapKey::Empty(self.empty_count));
96            self.empty_count += 1;
97            self.inner.swap_remove(value)
98        } else {
99            false
100        }
101    }
102
103    /// Removes all elements in the set, while preserving its capacity.
104    #[inline]
105    pub fn clear(&mut self) {
106        self.inner.clear();
107        self.inner.shrink_to_fit();
108        self.empty_count = 0;
109    }
110
111    /// Checks if a given value is present in the set
112    ///
113    /// Return `true` if `value` is present in set, false otherwise.
114    ///
115    /// Computes in **O(n)** time (average).
116    #[must_use]
117    pub fn contains(&self, value: &JsValue) -> bool {
118        self.inner.contains(value)
119    }
120
121    /// Get a key-value pair by index
122    /// Valid indices are 0 <= `index` < `self.len()`
123    /// Computes in O(1) time.
124    #[must_use]
125    pub fn get_index(&self, index: usize) -> Option<&JsValue> {
126        if let MapKey::Key(value) = self.inner.get_index(index)? {
127            Some(value)
128        } else {
129            None
130        }
131    }
132
133    /// Return an iterator over the values of the set, in their order
134    pub fn iter(&self) -> impl Iterator<Item = &JsValue> {
135        self.inner.iter().filter_map(|v| {
136            if let MapKey::Key(v) = v {
137                Some(v)
138            } else {
139                None
140            }
141        })
142    }
143
144    /// Increases the lock counter and returns a lock object that will decrement the counter when dropped.
145    ///
146    /// This allows objects to be removed from the set during iteration without affecting the indexes until the iteration has completed.
147    pub(crate) fn lock(&mut self) {
148        self.lock += 1;
149    }
150
151    /// Decreases the lock counter and, if 0, removes all empty entries.
152    pub(crate) fn unlock(&mut self) {
153        self.lock -= 1;
154        if self.lock == 0 {
155            self.inner.retain(|k| matches!(k, MapKey::Key(_)));
156            self.empty_count = 0;
157        }
158    }
159}
160
161pub(crate) struct SetLock<'a>(&'a JsObject<OrderedSet>);
162
163impl<'a> SetLock<'a> {
164    pub(crate) fn new(js_object: &'a JsObject<OrderedSet>) -> Self {
165        js_object.borrow_mut().data_mut().lock();
166        Self(js_object)
167    }
168}
169
170impl Drop for SetLock<'_> {
171    fn drop(&mut self) {
172        self.0.borrow_mut().data_mut().unlock();
173    }
174}
boa_engine/builtins/set/ordered_set.rs

boa_engine/builtins/set/
ordered_set.rs
