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
//! §10.4.2 — the one exotic object that is not an ordinary one, and why it has to be.
//!
//! # What is exotic about an Array
//!
//! One property: `length`. It is not a count kept beside the elements, it is a *property*, and it
//! and the indices are wired to each other in both directions.
//!
//! - Writing an index at or past `length` raises `length` to one past it. That is why `a[5] = 1`
//! on an empty array leaves `a.length` as 6 and four holes behind it.
//! - Writing `length` **deletes** every index at or past the new value, from the top down. That is
//! why `a.length = 0` empties an array, and why it is the idiom for doing so.
//!
//! Neither can be done by an ordinary object, because both happen inside `[[DefineOwnProperty]]`
//! — so §10.4.2 overrides that method and everything else about an Array is ordinary. This module
//! is that override and nothing more.
//!
//! # The half that surprises people
//!
//! Shortening can **fail part way**. §10.4.2.4 deletes from the top down and stops at the first
//! index that refuses — a non-configurable one — leaving `length` at one past *that* index rather
//! than where it was asked to go, and answering `false`. So `a.length = 0` on an array with a
//! frozen element at 3 leaves `length` as 4, and every element above 3 gone. That is not a
//! quirk to be tidied away; it is what the algorithm says, and a test262 test asks.
use super::{DefineOutcome, Heap, ObjectId, PropertyDescriptor, PropertyKey, PropertyKind};
use crate::value::Value;
impl Heap {
/// §10.4.2.1 `[[DefineOwnProperty]]` for an Array.
///
/// Three cases, and the ordinary one is the last: `length`, an index, and everything else.
pub(super) fn define_array_property(
&mut self,
object: ObjectId,
key: PropertyKey,
descriptor: &PropertyDescriptor,
) -> DefineOutcome {
let length_key = self.length_key();
if key == length_key {
return self.set_array_length(object, descriptor);
}
let Some(index) = key.as_array_index() else {
return DefineOutcome::from(self.define_ordinary_property(object, key, descriptor));
};
let (length, writable) = self.array_length(object);
// §10.4.2.1 step 3.b — an index past the end needs `length` to move, and a `length` that
// is not writable is what stops it. `Object.freeze` works on an array through this line.
if index >= length && !writable {
return DefineOutcome::Refused;
}
if !self.define_ordinary_property(object, key, descriptor) {
return DefineOutcome::Refused;
}
if index >= length {
self.write_length(object, index + 1);
}
DefineOutcome::Defined
}
/// §10.4.2.4 `ArraySetLength`.
///
/// The one place step 2's rule is written, which is why this answers a [`DefineOutcome`]
/// rather than a Boolean: a length that is not an integer index is a **RangeError**, and a
/// Boolean cannot say that. `false` means "not allowed", which sloppy code drops on the
/// floor — and a bad length must not be dropped.
fn set_array_length(
&mut self,
object: ObjectId,
descriptor: &PropertyDescriptor,
) -> DefineOutcome {
let Some(value) = descriptor.value else {
// No value, so only the attributes are being changed — `Object.defineProperty(a,
// "length", {writable: false})`, which is how an array is made fixed-length.
let key = self.length_key();
return DefineOutcome::from(self.define_ordinary_property(object, key, descriptor));
};
// §10.4.2.4 step 2 — `ToUint32` and `ToNumber` must agree, or the value is not a length
// at all. `is_sign_negative` rather than `< 0.0`, for the reason `array_index` gives.
let Ok(number) = value.to_number(self) else {
return DefineOutcome::BadLength;
};
let wanted = number as u32;
if f64::from(wanted) != number || number.is_sign_negative() {
return DefineOutcome::BadLength;
}
let (current, writable) = self.array_length(object);
// §10.4.2.4 step 12 — the comparison is with the *current* length, not a blanket
// refusal. `a.length = a.length` is allowed on a fixed-length array; anything else is not.
if !writable && wanted != current {
return DefineOutcome::Refused;
}
// §10.4.2.4 step 12 — a length that is not *smaller* deletes nothing, and the clause says
// so before it says anything about deleting. ViperJS went without the check for a while, on
// the grounds that no index can be at or above an array's own length so the walk finds
// nothing anyway. True, and still wrong: the walk is over every key the object has, so a
// `push` that only ever grows paid a pass over the array it was appending to. Ten thousand
// of them took thirty seconds; with the step, under a tenth of a second.
//
// **This branch cannot be killed by a test, and that is not a gap.** Its two sides answer
// identically for every array a program can build — an index is always below the length,
// so `wanted == current` finds nothing to delete either way. What it decides is cost. It
// was tried without the branch and with the walk made as cheap as it can be, and ten
// thousand pushes still took sixteen seconds: the walk is the cost, not the sort.
let reached = match wanted >= current {
true => wanted,
false => self.delete_above(object, wanted),
};
let length = PropertyDescriptor {
value: Some(Value::Number(f64::from(reached))),
..*descriptor
};
let key = self.length_key();
let stored = self.define_ordinary_property(object, key, &length);
// §10.4.2.4 step 17 — a shortening that could not finish is refused even though `length`
// did move. The array is left in the state the deletions reached, which is a state no
// other operation can produce.
DefineOutcome::from(stored && reached == wanted)
}
/// Delete every index at or above `floor`, from the top down, and answer where it stopped.
///
/// Downwards because §10.4.2.4 step 15 says so, and the order is observable: it stops at the
/// first index that refuses, so the elements *below* a frozen one survive and the ones above
/// it are already gone.
fn delete_above(&mut self, object: ObjectId, floor: u32) -> u32 {
// The keys as *stored* rather than in §10.1.11's order: this sorts what survives the
// filter anyway, and asking for the specification's grouping means three vectors and a
// sort of every key the object has — paid on every write of `length`, which `push` does
// once per element.
let keys: Vec<crate::heap::PropertyKey> = self
.object(object)
.map(|found| found.stored_keys().collect())
.unwrap_or_default();
let mut indices: Vec<u32> = keys
.into_iter()
.filter_map(PropertyKey::as_array_index)
.filter(|index| *index >= floor)
.collect();
indices.sort_unstable();
// §10.4.2.4 steps 17.b to 17.d walk downwards and stop at the first index that refuses, so
// what survives is everything at or below the *highest* one that refuses. Found first and
// deleted afterwards, in one pass: doing it a property at a time is what the specification
// describes and it is quadratic, because each removal shifts the rest and rebuilds the key
// index. The order still decides the answer — it just no longer decides the cost.
let stuck = indices.iter().rev().find(|index| {
let key = self.index_key(**index);
self.object(object)
.and_then(|found| found.get_own_property(key))
.is_some_and(|property| !property.configurable)
});
let reached = match stuck {
Some(index) => index + 1,
None => floor,
};
let doomed: std::collections::HashSet<crate::heap::PropertyKey> = indices
.into_iter()
.filter(|index| *index >= reached)
.map(|index| self.index_key(index))
.collect();
if let Some(found) = self.object_mut(object) {
found.delete_all(&doomed);
}
reached
}
/// The `length` an array holds, and whether it may be changed.
///
/// Every array has one — it is created with it and it cannot be deleted — so an array without
/// one is not a state this heap can be in. Answering zero rather than asserting keeps the
/// method total, and a wrong answer here would be a wrong length rather than a crash.
fn array_length(&mut self, object: ObjectId) -> (u32, bool) {
let key = self.length_key();
let found = self
.object(object)
.and_then(|found| found.get_own_property(key));
match found.map(|property| property.kind) {
Some(PropertyKind::Data {
value: Value::Number(length),
writable,
}) => (length as u32, writable),
_ => (0, true),
}
}
/// Put a new `length` in place, keeping its attributes.
fn write_length(&mut self, object: ObjectId, length: u32) {
let descriptor = PropertyDescriptor {
value: Some(Value::Number(f64::from(length))),
..PropertyDescriptor::EMPTY
};
let key = self.length_key();
self.define_ordinary_property(object, key, &descriptor);
}
/// The interned key `length`, which every array has and every array shares.
pub(crate) fn length_key(&mut self) -> PropertyKey {
PropertyKey::from_units(self, &"length".encode_utf16().collect::<Vec<_>>())
}
/// The key an index is filed under, which is the decimal spelling and nothing else.
pub(crate) fn index_key(&mut self, index: u32) -> PropertyKey {
// A cast. This used to spell the number, encode it to UTF-16 and intern it — DR-0026. The
// `&mut self` stays because every caller has one and changing the signature would be churn
// for nothing.
PropertyKey::from_index(index)
}
/// Put a new Array on the heap — §10.4.2.2 `ArrayCreate`.
///
/// `length` is writable and neither enumerable nor configurable, which is §10.4.2.2 step 6 and
/// is what makes `delete a.length` answer `false` on every array in the language.
pub fn new_array(&mut self, prototype: ObjectId, length: u32) -> ObjectId {
let object = self.new_object(Some(prototype));
if let Some(found) = self.object_mut(object) {
found.array = true;
}
let descriptor = PropertyDescriptor {
value: Some(Value::Number(f64::from(length))),
writable: Some(true),
enumerable: Some(false),
configurable: Some(false),
..PropertyDescriptor::EMPTY
};
let key = self.length_key();
self.define_ordinary_property(object, key, &descriptor);
object
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn an_array_that_somehow_lost_its_length_is_read_as_an_empty_one() {
// `new_array` gives every array a `length` and §10.4.2.2 makes it non-configurable, so
// this is a state no program can reach. The *heap* can hold it, and a guard that answered
// differently would put a wrong length on an array rather than crashing — so it is built
// by hand here, which is the only way to reach it at all.
let mut heap = Heap::new();
let object = heap.new_object(None);
if let Some(found) = heap.object_mut(object) {
found.array = true;
}
// Read as empty and writable, so the first index written behaves exactly as it would on
// an array made the ordinary way: it lands, and the length follows it.
let key = PropertyKey::from_units(&mut heap, &"3".encode_utf16().collect::<Vec<_>>());
let descriptor = PropertyDescriptor {
value: Some(Value::Number(1.0)),
writable: Some(true),
enumerable: Some(true),
configurable: Some(true),
..PropertyDescriptor::EMPTY
};
assert_eq!(
heap.define_property_outcome(object, key, &descriptor),
super::DefineOutcome::Defined
);
// …and the `length` that appeared is one `write_length` created rather than one it
// updated, so it carries §6.1.7.1's defaults instead of §10.4.2.2's. That is only
// reachable from here: on an array made the ordinary way there is always one to update.
assert_eq!(heap.array_length(object), (4, false));
}
}