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