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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.
use crate::{
ecmascript::types::{
BIGINT_DISCRIMINANT, HeapBigInt, HeapNumber, HeapPrimitive, HeapString,
NUMBER_DISCRIMINANT, OrdinaryObject, STRING_DISCRIMINANT, Value,
},
engine::{Bindable, bindable_handle},
heap::{CompactionLists, HeapMarkAndSweep, PrimitiveHeapAccess, WorkQueues},
};
use ahash::AHasher;
use core::{
cell::RefCell,
hash::{Hash, Hasher},
sync::atomic::{AtomicBool, Ordering},
};
use hashbrown::{HashTable, hash_table::Entry};
use soavec_derive::SoAble;
#[derive(Debug, Default, SoAble)]
pub(crate) struct MapHeapData<'a> {
/// Low-level hash table pointing to keys-values indexes.
pub(super) map_data: RefCell<HashTable<u32>>,
// TODO: Use a ParallelVec to remove one unnecessary allocation.
// key_values: ParallelVec<Option<Value>, Option<Value>>
pub(super) values: Vec<Option<Value<'a>>>,
pub(super) keys: Vec<Option<Value<'a>>>,
pub(super) object_index: Option<OrdinaryObject<'a>>,
/// Flag that lets the Map know if it needs to rehash its primitive keys.
///
/// This happens when an object key needs to be moved in the map_data
/// during garbage collection, and the move results in a primitive key
/// moving as well. The primitive key's hash cannot be calculated during
/// garbage collection due to the heap data being concurrently sweeped on
/// another thread.
needs_primitive_rehashing: AtomicBool,
// TODO: When an non-terminal (start or end) iterator exists for the Map,
// the items in the map cannot be compacted.
// observed: bool;
}
bindable_handle!(MapHeapData);
impl MapHeapData<'_> {
pub(crate) fn with_capacity(new_len: usize) -> Self {
Self {
keys: Vec::with_capacity(new_len),
values: Vec::with_capacity(new_len),
map_data: RefCell::new(HashTable::with_capacity(new_len)),
needs_primitive_rehashing: AtomicBool::new(false),
object_index: None,
}
}
}
impl<'map, 'soa> MapHeapDataMut<'map, 'soa> {
#[inline(always)]
pub(crate) fn clear(&mut self) {
// 3. For each Record { [[Key]], [[Value]] } p of M.[[MapData]], do
// a. Set p.[[Key]] to EMPTY.
// b. Set p.[[Value]] to EMPTY.
self.map_data.get_mut().clear();
self.values.fill(None);
self.keys.fill(None);
}
pub(crate) fn rehash_if_needed_mut(&mut self, arena: &impl PrimitiveHeapAccess) {
if !*self.needs_primitive_rehashing.get_mut() {
return;
}
rehash_map_data(self.keys, self.map_data.get_mut(), arena);
self.needs_primitive_rehashing
.store(false, Ordering::Relaxed);
}
}
impl<'map, 'soa> MapHeapDataRef<'map, 'soa> {
/// ### [24.2.1.5 MapDataSize ( setData )](https://tc39.es/ecma262/#sec-setdatasize)
///
/// The abstract operation MapDataSize takes argument setData (a List of either
/// ECMAScript language values or EMPTY) and returns a non-negative integer.
#[inline(always)]
pub(crate) fn size(&self) -> u32 {
// 1. Let count be 0.
// 2. For each element e of setData, do
// a. If e is not EMPTY, set count to count + 1.
// 3. Return count.
self.map_data.borrow().len() as u32
}
pub(crate) fn entries_len(&self) -> u32 {
self.values.len() as u32
}
}
fn rehash_map_data(
keys: &[Option<Value>],
map_data: &mut HashTable<u32>,
arena: &impl PrimitiveHeapAccess,
) {
let hasher = |value: Value| {
let mut hasher = AHasher::default();
value.unbind().hash(arena, &mut hasher);
hasher.finish()
};
let hashes = {
let hasher = |discriminant: u8| {
let mut hasher = AHasher::default();
discriminant.hash(&mut hasher);
hasher.finish()
};
[
(0u8, hasher(STRING_DISCRIMINANT)),
(1u8, hasher(NUMBER_DISCRIMINANT)),
(2u8, hasher(BIGINT_DISCRIMINANT)),
]
};
for (id, hash) in hashes {
let eq = |equal_hash_index: &u32| {
let value = keys[*equal_hash_index as usize].unwrap();
match id {
0 => HeapString::try_from(value).is_ok(),
1 => HeapNumber::try_from(value).is_ok(),
2 => HeapBigInt::try_from(value).is_ok(),
_ => unreachable!(),
}
};
let mut entries = Vec::new();
while let Ok(entry) = map_data.find_entry(hash, eq) {
entries.push(*entry.get());
entry.remove();
}
entries.iter().for_each(|entry| {
let key = keys[*entry as usize].unwrap();
let key_hash = hasher(key);
let result = map_data.entry(
key_hash,
|equal_hash_index| {
// It should not be possible for there to be an equal item
// in the Map already.
debug_assert_ne!(keys[*equal_hash_index as usize].unwrap(), key);
false
},
|index_to_hash| hasher(keys[*index_to_hash as usize].unwrap()),
);
let Entry::Vacant(result) = result else {
unreachable!();
};
result.insert(*entry);
});
}
}
impl HeapMarkAndSweep for MapHeapDataRef<'_, 'static> {
fn mark_values(&self, queues: &mut WorkQueues) {
let Self {
keys,
values,
object_index,
..
} = self;
object_index.mark_values(queues);
keys.iter().for_each(|value| value.mark_values(queues));
values.iter().for_each(|value| value.mark_values(queues));
}
fn sweep_values(&mut self, _compactions: &CompactionLists) {
unreachable!()
}
}
impl HeapMarkAndSweep for MapHeapDataMut<'_, 'static> {
fn mark_values(&self, _queues: &mut WorkQueues) {
unreachable!()
}
fn sweep_values(&mut self, compactions: &CompactionLists) {
let Self {
object_index,
keys,
values,
needs_primitive_rehashing,
map_data,
} = self;
let map_data = map_data.get_mut();
object_index.sweep_values(compactions);
let hasher = |value: Value| {
let mut hasher = AHasher::default();
if value.try_hash(&mut hasher).is_err() {
// A heap String, Number, or BigInt required rehashing as part
// of moving an Object key inside the HashTable. The heap
// vectors for those data points are currently being sweeped on
// another thread, so we cannot access them right now even if
// we wanted to. This situation should be fairly improbable as
// it requires mixing eg. long string and object values in the
// same Map, so it's not pressing right now. Still, it must be
// handled eventually. We essentially mark the heap hash data
// as "dirty". Any lookup shall then later check this boolean
// and rehash primitive keys if necessary.
needs_primitive_rehashing.store(true, Ordering::Relaxed);
let value = HeapPrimitive::try_from(value).unwrap();
// Return a hash based on the discriminant. This we are likely
// to cause hash collisions but we avoid having to rehash all
// keys; we can just rehash the primitive keys that match the
// discriminant hash.
core::mem::discriminant(&value).hash(&mut hasher);
}
hasher.finish()
};
assert_eq!(keys.len(), values.len());
for index in 0..keys.len() as u32 {
let key = &mut keys[index as usize];
let Some(key) = key else {
// Skip empty slots.
continue;
};
// Sweep value without any concerns.
values[index as usize].sweep_values(compactions);
let old_key = *key;
key.sweep_values(compactions);
let new_key = *key;
if old_key == new_key {
// No identity change, no hash change.
continue;
}
if !new_key.is_object() {
// Non-objects do not change their hash even if their identity
// changes.
continue;
}
// Object changed identity; it must be moved in the map_data.
let old_hash = hasher(old_key);
let new_hash = hasher(new_key);
if let Ok(old_entry) =
map_data.find_entry(old_hash, |equal_hash_index| *equal_hash_index == index)
{
// We do not always find an entry if a previous item has
// shifted ontop of our old hash.
old_entry.remove();
}
let new_entry = map_data.entry(
new_hash,
|equal_hash_index| {
// It's not possible for there to be another hash index that
// holds our item. But! It's possible that we're eg. shifting
// 32 to 30, and then 30 to 29. Thus 32 will happily override
// 30.
values[*equal_hash_index as usize].unwrap() == new_key
},
|index_to_hash| {
let value = values[*index_to_hash as usize].unwrap();
hasher(value)
},
);
match new_entry {
hashbrown::hash_table::Entry::Occupied(mut occupied) => {
// We found an existing entry that points to a
// (necessarily) different slot that contains the same
// value. This value will necessarily be removed later; we
// can just reuse this slot.
*occupied.get_mut() = index;
}
hashbrown::hash_table::Entry::Vacant(vacant) => {
// This is the expected case: We're not overwriting a slot.
vacant.insert(index);
}
}
}
}
}