boa/builtins/map/

ordered_map.rs

use crate::{
    gc::{custom_trace, Finalize, Trace},
    object::JsObject,
    JsValue,
};
use indexmap::{Equivalent, IndexMap};
use std::{
    collections::hash_map::RandomState,
    fmt::Debug,
    hash::{BuildHasher, Hash, Hasher},
};

#[derive(PartialEq, Eq, Clone, Debug)]
enum MapKey {
    Key(JsValue),
    Empty(usize), // Necessary to ensure empty keys are still unique.
}

// This ensures that a MapKey::Key(value) hashes to the same as value. The derived PartialEq implementation still holds.
#[allow(clippy::derive_hash_xor_eq)]
impl Hash for MapKey {
    fn hash<H: Hasher>(&self, state: &mut H) {
        match self {
            MapKey::Key(v) => v.hash(state),
            MapKey::Empty(e) => e.hash(state),
        }
    }
}

impl Equivalent<MapKey> for JsValue {
    fn equivalent(&self, key: &MapKey) -> bool {
        match key {
            MapKey::Key(v) => v == self,
            _ => false,
        }
    }
}

/// A newtype wrapping indexmap::IndexMap
#[derive(Clone)]
pub struct OrderedMap<V, S = RandomState> {
    map: IndexMap<MapKey, Option<V>, S>,
    lock: u32,
    empty_count: usize,
}

impl<V: Trace, S: BuildHasher> Finalize for OrderedMap<V, S> {}
unsafe impl<V: Trace, S: BuildHasher> Trace for OrderedMap<V, S> {
    custom_trace!(this, {
        for (k, v) in this.map.iter() {
            if let MapKey::Key(key) = k {
                mark(key);
            }
            mark(v);
        }
    });
}

impl<V: Debug> Debug for OrderedMap<V> {
    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
        self.map.fmt(formatter)
    }
}

impl<V> Default for OrderedMap<V> {
    fn default() -> Self {
        Self::new()
    }
}

impl<V> OrderedMap<V> {
    pub fn new() -> Self {
        OrderedMap {
            map: IndexMap::new(),
            lock: 0,
            empty_count: 0,
        }
    }

    pub fn with_capacity(capacity: usize) -> Self {
        OrderedMap {
            map: IndexMap::with_capacity(capacity),
            lock: 0,
            empty_count: 0,
        }
    }

    /// Return the number of key-value pairs in the map, including empty values.
    ///
    /// Computes in **O(1)** time.
    pub fn full_len(&self) -> usize {
        self.map.len()
    }

    /// Gets the number of key-value pairs in the map, not including empty values.
    ///
    /// Computes in **O(1)** time.
    pub fn len(&self) -> usize {
        self.map.len() - self.empty_count
    }

    /// Returns true if the map contains no elements.
    ///
    /// Computes in **O(1)** time.
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Insert a key-value pair in the map.
    ///
    /// If an equivalent key already exists in the map: the key remains and
    /// retains in its place in the order, its corresponding value is updated
    /// with `value` and the older value is returned inside `Some(_)`.
    ///
    /// If no equivalent key existed in the map: the new key-value pair is
    /// inserted, last in order, and `None` is returned.
    ///
    /// Computes in **O(1)** time (amortized average).
    pub fn insert(&mut self, key: JsValue, value: V) -> Option<V> {
        self.map.insert(MapKey::Key(key), Some(value)).flatten()
    }

    /// Remove the key-value pair equivalent to `key` and return
    /// its value.
    ///
    /// Like `Vec::remove`, the pair is removed by shifting all of the
    /// elements that follow it, preserving their relative order.
    /// **This perturbs the index of all of those elements!**
    ///
    /// Return `None` if `key` is not in map.
    ///
    /// Computes in **O(n)** time (average).
    pub fn remove(&mut self, key: &JsValue) -> Option<V> {
        if self.lock == 0 {
            self.map.shift_remove(key).flatten()
        } else if self.map.contains_key(key) {
            self.map.insert(MapKey::Empty(self.empty_count), None);
            self.empty_count += 1;
            self.map.swap_remove(key).flatten()
        } else {
            None
        }
    }

    /// Removes all elements from the map and resets the counter of
    /// empty entries.
    pub fn clear(&mut self) {
        self.map.clear();
        self.map.shrink_to_fit();
        self.empty_count = 0
    }

    /// Return a reference to the value stored for `key`, if it is present,
    /// else `None`.
    ///
    /// Computes in **O(1)** time (average).
    pub fn get(&self, key: &JsValue) -> Option<&V> {
        self.map.get(key).map(Option::as_ref).flatten()
    }

    /// Get a key-value pair by index.
    ///
    /// Valid indices are 0 <= index < self.full_len().
    ///
    /// Computes in O(1) time.
    pub fn get_index(&self, index: usize) -> Option<(&JsValue, &V)> {
        if let (MapKey::Key(key), Some(value)) = self.map.get_index(index)? {
            Some((key, value))
        } else {
            None
        }
    }

    /// Return an iterator over the key-value pairs of the map, in their order
    pub fn iter(&self) -> impl Iterator<Item = (&JsValue, &V)> {
        self.map.iter().filter_map(|o| {
            if let (MapKey::Key(key), Some(value)) = o {
                Some((key, value))
            } else {
                None
            }
        })
    }

    /// Return `true` if an equivalent to `key` exists in the map.
    ///
    /// Computes in **O(1)** time (average).
    pub fn contains_key(&self, key: &JsValue) -> bool {
        self.map.contains_key(key)
    }

    /// Increases the lock counter and returns a lock object that will decrement the counter when dropped.
    ///
    /// This allows objects to be removed from the map during iteration without affecting the indexes until the iteration has completed.
    pub(crate) fn lock(&mut self, map: JsObject) -> MapLock {
        self.lock += 1;
        MapLock(map)
    }

    /// Decreases the lock counter and, if 0, removes all empty entries.
    fn unlock(&mut self) {
        self.lock -= 1;
        if self.lock == 0 {
            self.map.retain(|k, _| matches!(k, MapKey::Key(_)));
            self.empty_count = 0;
        }
    }
}

/// Increases the lock count of the map for the lifetime of the guard. This should not be dropped until iteration has completed.
#[derive(Debug, Trace)]
pub(crate) struct MapLock(JsObject);

impl Clone for MapLock {
    fn clone(&self) -> Self {
        let mut map = self.0.borrow_mut();
        let map = map.as_map_mut().expect("MapLock does not point to a map");
        map.lock(self.0.clone())
    }
}

impl Finalize for MapLock {
    fn finalize(&self) {
        let mut map = self.0.borrow_mut();
        let map = map.as_map_mut().expect("MapLock does not point to a map");
        map.unlock();
    }
}