viperjs 0.3.0

An embeddable JavaScript engine in safe Rust, with zero runtime dependencies.
Documentation
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
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
//! The ordinary object — §10.1, the shape almost every object in a program has.
//!
//! An object is three things: a prototype, a flag saying whether properties may still be added,
//! and a collection of properties. Everything else about §10.1 is rules for changing them.
//!
//! # What is here and what is not
//!
//! Every ordinary internal method that does not reach user code. `[[Get]]` and `[[Set]]` are the
//! two that do — an accessor property's getter is a function, and calling it is the VM's job —
//! so they arrive with the interpreter. `[[HasProperty]]`, `[[Delete]]`, `[[GetOwnProperty]]`,
//! `[[DefineOwnProperty]]`, `[[OwnPropertyKeys]]` and the prototype and extensibility methods are
//! all here, and between them they are what the object model *is*.
//!
//! # Why the properties are a `Vec`, and what sits beside it
//!
//! Because §10.1.11 asks for insertion order and a `Vec` has it. Lookup was linear, which this
//! comment used to call the boring implementation and "wrong for an object with a thousand
//! properties — the fix is a map beside the order, or shapes, and both are M8 experiments that
//! need a benchmark first".
//!
//! The benchmark arrived. A linear scan makes *insertion* linear too, so filling an array element
//! by element is quadratic: `a[i] = 1` measured 270 ms for twenty thousand elements, 967 ms for
//! forty, and 3743 ms for eighty — four times the work for twice the elements. That is not a
//! slow engine, it is the wrong shape, and it was bad enough that such a test could not finish
//! inside the conformance harness's budget at all.
//!
//! So there is now a map beside the order, and the `Vec` still *is* the order. The map is not
//! built until an object has more properties than [`INDEXED_ABOVE`], because most objects never
//! do: a hash table on every one of them would cost an allocation each and buy nothing, and
//! DR-0013 counts those allocations. Shapes remain the other answer and remain an M8 experiment —
//! this one is smaller and needed no new representation to get the exponent right.

use crate::heap::buffer::{Buffer, View};
use crate::heap::collection::Collection;
use crate::heap::promise::{Promise, Role};
use crate::heap::{
    ArgumentsMap, Callable, EnvironmentId, Helper, Iteration, Property, PropertyKey, Proxy,
    StringId, SymbolId, Weak,
};
use crate::value::Value;
use std::collections::HashMap;

/// An object on the heap.
///
/// Meaningful only to the [`crate::heap::Heap`] that issued it, on the same terms as [`crate::heap::StringId`].
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ObjectId(pub(crate) usize);

/// Which kind of execution an object holds parked — §27.5.1's or §27.7's.
///
/// The two are the same record parked in the same slot, and they differ in three places: what the
/// call that made them answered with, what resumes them, and what a `return` from the body does.
/// Each of those asks this.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Suspendable {
    /// §27.5.1's generator, resumed by `next`, `return` and `throw`.
    Generator,
    /// §27.7's `async` function context, resumed by a job when a promise settles.
    Async,
    /// §27.6's async generator, which is resumed by both — and is the only one a script can hold.
    ///
    /// A third brand rather than the two together, because it is not the conjunction: an `async`
    /// function's context object is internal and settles one promise, and an async generator is
    /// the object the script was handed and settles one promise *per request*. What they share is
    /// only that a body can be parked, and every object here has that.
    AsyncGenerator,
}

/// What an arrow reaches outward for, captured where it was written — §10.2.3 step 6.
///
/// Two values and not one, because §9.1.1.3's function environment holds both and an arrow gets
/// neither of its own: `this` and `new.target` are looked up through the same walk and answered by
/// the same environment, so an arrow that had captured one and resolved the other could disagree
/// with itself about which call it belongs to. One struct means the pair is captured at one moment
/// or not at all.
// No `PartialEq`: [`Value`] deliberately has none, because JavaScript has three different
// equalities and none of them is a derive.
#[derive(Debug, Clone, Copy)]
pub struct Lexical {
    /// The `this` in force where the arrow was written.
    pub this_value: Value,
    /// The `new.target` in force there — §13.3.12 reaches outward exactly as `this` does, which is
    /// why `() => new.target` inside a constructor answers that constructor and not `undefined`.
    pub new_target: Value,
    /// The `[[HomeObject]]` of the method the arrow was written in, if it was written in one.
    ///
    /// The third thing §9.1.1.3 answers by walking outward, so it is captured with the other two.
    /// `None` for an arrow written outside any method, where `super` is a Syntax Error anyway.
    pub home: Option<ObjectId>,
}

/// One entry in §7.3.28's `[[PrivateElements]]` — a field, a method, or an accessor.
///
/// The kind is carried rather than inferred, because §7.3.31 and §7.3.32 read it: a private *method*
/// refuses assignment where a field accepts it, and an accessor calls a function for both. Told apart
/// by the shape of the value they would otherwise be — a `Value` that happens to be callable is not
/// the same thing as a method, since `#x = function () {}` is a field holding a function.
// No `PartialEq`: [`Value`] has none, because JavaScript has three equalities and none is a derive.
#[derive(Debug, Clone, Copy)]
pub enum PrivateElement {
    /// `#x = 1` — per instance, and the only kind a write may reach.
    Field(Value),
    /// `#m() {}` — **one** function object shared by every instance, which each carries an entry for.
    ///
    /// Shared and not copied, so `new C().m === new C().m` for the function a private method holds; the
    /// per-instance entry is what makes `#m in o` a brand rather than a lookup on a prototype.
    Method(Value),
    /// `get #a() {}` and `set #a(v) {}` — one element with two halves, as §7.3.30 adds it.
    ///
    /// Either half may be `undefined`, and then that direction is a TypeError: a private accessor
    /// with only a getter refuses a write outright rather than silently doing nothing, which is where
    /// it differs from a public one.
    Accessor {
        /// The getter, or `undefined` if only a setter was written.
        getter: Value,
        /// The setter, or `undefined` if only a getter was written.
        setter: Value,
    },
}

impl PrivateElement {
    /// What a read answers with directly, if this kind answers without calling anything.
    ///
    /// `None` for an accessor, whose getter the interpreter has to call — the heap cannot, and that
    /// is the same division `[[Get]]` already makes for a property.
    pub fn value(self) -> Option<Value> {
        match self {
            Self::Field(value) | Self::Method(value) => Some(value),
            Self::Accessor { .. } => None,
        }
    }
}

/// An ordinary object — §10.1.
#[derive(Debug, Default)]
pub struct Object {
    /// `[[Prototype]]` — "an Object or **null**", which is what the `Option` is.
    ///
    /// `None` is `null` and not "not set": an object whose prototype is null is the ordinary
    /// state of `Object.create(null)`, and the chain simply ends there.
    pub(super) prototype: Option<ObjectId>,
    /// `[[Extensible]]` — whether properties may still be added.
    ///
    /// One-way: §10.1.4 can set it false and nothing sets it back. That is what makes
    /// `Object.preventExtensions` a guarantee rather than a suggestion, and it is why
    /// [`Object::prevent_extensions`] takes no argument.
    extensible: bool,
    /// The body this object runs when it is called — its `[[Call]]` internal method.
    ///
    /// `None` for an ordinary object, which is most of them. An object is *callable* exactly when
    /// this is present, which is the whole of what `typeof f === "function"` and "x is not a
    /// function" are asking about.
    ///
    /// Holding the code here rather than in an arena beside it is deliberate: a function object
    /// is the thing that owns its body, and the `Rc` is what lets a closure outlive the call that
    /// made it. See [`Chunk`] for why reference counting is safe for code where DR-0010 rejects
    /// it for values.
    pub(super) call: Option<Callable>,
    /// The environment this function was *written* in — §10.2's `[[Environment]]`.
    ///
    /// A closure is this field. The call that made the function is long gone by the time the
    /// function runs, and the variables it could see are still here because this holds them.
    pub(super) environment: Option<EnvironmentId>,
    /// What an arrow was written beside — §10.2's `[[ThisMode]]` of `lexical`.
    ///
    /// `None` for every function that binds its own, which is all of them but arrows. Present, it
    /// is the same idea as `environment` one field up and for the same reason: the call that made
    /// the arrow is gone by the time the arrow runs, so what it could see has to be *held*
    /// rather than looked for. §9.1.1.3 words it as a function environment with no `[[ThisBinding]]`
    /// whose `ResolveThisBinding` walks outward; the environment that walk arrives at is exactly
    /// the one running when the arrow was made, so recording it here is that walk, done
    /// once and in advance.
    pub(super) lexical: Option<Lexical>,
    /// `[[PrivateElements]]` — §7.3.28's list, and **not** properties.
    ///
    /// A separate list rather than rows in the property table, because a private element is not a
    /// property by any test a program can make: `Object.keys`, `getOwnPropertyNames`,
    /// `getOwnPropertySymbols`, `for...in` and a Proxy trap must all fail to see it. Putting one in
    /// the table would mean teaching every one of those to skip it, and the one that was forgotten
    /// would leak `#x` to a script.
    ///
    /// Keyed by [`SymbolId`] because a Private Name (§6.2.12) needs exactly what a Symbol has and
    /// nothing more: an identity that is itself, freshly minted, with a description only a debugger
    /// would read. The Symbol never reaches the property table, so it cannot be a key by accident,
    /// and nothing a script can write reaches the slot that holds it.
    ///
    /// `None` for every object that has none, which is all of them but instances of a class with a
    /// private element. **Not** boxed, unlike the parameter map and the iteration state beside it:
    /// those box a struct, where the indirection genuinely shrinks the field, and a `Vec` is already
    /// a pointer — so boxing one buys three words back and costs a second allocation for every object
    /// that has any private state at all. `Option<Vec<_>>` also has no discriminant, the null pointer
    /// being the niche.
    pub(super) private: Option<Vec<(SymbolId, PrivateElement)>>,
    /// `[[HomeObject]]` — the object a method was defined *on*, if it is a method.
    ///
    /// `None` for every function that is not one, which is every function expression and every
    /// arrow. What needs it is `super.x`: §9.1.1.3's `GetSuperBase` reads this object's
    /// `[[Prototype]]`, so a method knows where to start looking that is one level above where it was
    /// defined. Unrelated to `this` and deliberately so — a method borrowed by another object keeps
    /// the home it was written in, which is why `super.x` there still reads the original parent.
    pub(super) home: Option<ObjectId>,
    /// Whether this is §10.4.2's exotic Array, whose `length` and indices move each other.
    pub(super) array: bool,
    /// §10.4.4's parameter map, if this is an arguments object.
    ///
    /// `None` for every other object, which is all but one per call that mentions the name. Boxed
    /// so that an object without one pays a pointer rather than a `Vec`: an `Object` sits inline
    /// in the arena, so its size is charged to every object ever made.
    pub(super) arguments: Option<Box<ArgumentsMap>>,
    /// Where this object has got to, if it is an iterator — §23.1.5.1 and §22.1.5.1.
    ///
    /// `None` for everything else. Boxed for the reason the parameter map is: an `Object` sits
    /// inline in the arena, so its size is charged to every object ever made.
    pub(super) iteration: Option<Box<Iteration>>,
    /// The primitive this object *is* a wrapper for — §20.3's `[[BooleanData]]`, §21.1's
    /// `[[NumberData]]` and §22.1's `[[StringData]]`.
    ///
    /// One slot rather than three, because the value in it already says which: a `Value::Boolean`
    /// is a `[[BooleanData]]` and nothing else can be. That is what lets
    /// `Boolean.prototype.valueOf.call(new Number(1))` be the TypeError §20.3.3 asks for without
    /// three fields to keep apart.
    pub(super) primitive: Option<Value>,
    /// `[[DateValue]]` — the time value, in milliseconds since the epoch, if this is a Date.
    ///
    /// Its own field rather than a `Value::Number` in `primitive`, and that is not redundancy: the
    /// slot above is documented to say *which* wrapper it is by the type of the value in it, so a
    /// Number there means `[[NumberData]]` and can mean nothing else. Putting a time value there
    /// would make `new Date()` indistinguishable from `new Number()`, which would let
    /// `Number.prototype.valueOf.call(new Date())` answer instead of throwing, and would make
    /// `JSON.stringify(v, null, aDate)` indent by the epoch.
    ///
    /// Inline rather than boxed, unlike the two maps above, because the payload is one `f64` and a
    /// pointer to it would cost the same eight bytes plus an allocation. It widens every object by
    /// 16 — there is no niche in an `f64`, and NaN cannot stand in for absence because `new
    /// Date(NaN)` is a legal invalid date whose time value *is* NaN. Measured at 176 bytes before
    /// and 192 after; if that matters it is an M8 question, with a number in front of it.
    pub(super) date: Option<f64>,
    /// §25.1.3.1's data block, if this is an `ArrayBuffer`.
    ///
    /// Boxed like the others, and unlike the others it holds no `Value` at all: a buffer is bytes,
    /// so the collector has nothing to follow through one.
    buffer: Option<Box<Buffer>>,
    /// Whether this TypedArray is the one kind that saturates — `Uint8ClampedArray`.
    ///
    /// A flag rather than a tenth [`Element`], because it is not a different *type*: the bytes are
    /// a `Uint8`'s and every read of them is identical. What differs is one conversion on the way
    /// in, §7.1.11 rather than §7.1.9, so the difference belongs beside the write and not beside
    /// the storage.
    pub(super) clamped: bool,
    /// §25.3's view slots, if this is a `DataView`.
    ///
    /// Three `usize`s and an id, so it is inline rather than boxed: a pointer to it would cost as
    /// much as half of it.
    view: Option<View>,
    /// §24.1's `[[MapData]]` or §24.2's `[[SetData]]`, if this is one of those.
    ///
    /// Boxed for the reason the promise is: an `Object` sits inline in the arena, so its size is
    /// charged to every object ever made and a collection is a `Vec` and a count.
    collection: Option<Box<Collection>>,
    /// The six slots §27.2.6 gives a Promise, if this is one.
    ///
    /// Boxed, for the reason the two maps above are: an `Object` sits inline in the arena, so its
    /// size is charged to every object ever made and a promise's two reaction lists are three words
    /// each. `None` is every object that is not a promise, which is what §27.2.5.4 step 2 tests
    /// before it will do anything at all.
    promise: Option<Box<Promise>>,
    /// What a promise resolving function settles, or what a capability executor fills in.
    ///
    /// §27.2.1.3's resolve and reject functions have a `[[Promise]]`, and §27.2.1.5.1's executor has
    /// a `[[Capability]]`. Neither can be a captured variable: a built-in's body is a bare function
    /// pointer holding no state, deliberately, so what the specification captures in a closure is
    /// carried on the function object exactly as it says it is.
    role: Option<Box<Role>>,
    /// §26.1's `[[WeakRefTarget]]` or §26.2's `[[Cells]]`, if this is one of those.
    ///
    /// Boxed for the reason the collection beside it is: an `Object` sits inline in the arena, so
    /// whatever this costs is charged to every object ever made, and a registry is a `Vec`.
    weak: Option<Box<Weak>>,
    /// §27.1.5's Iterator Helper state, if this is one.
    ///
    /// Boxed like the collection beside it, and for the same reason: an `Object` sits inline in
    /// the arena, so whatever this costs is charged to every object ever made.
    helper: Option<Box<Helper>>,
    /// §10.5's `[[ProxyTarget]]` and `[[ProxyHandler]]`, if this is a Proxy.
    ///
    /// Two ids and a discriminant, so it sits inline rather than boxed — a pointer to it would
    /// cost as much as the thing itself.
    proxy: Option<Proxy>,
    /// §22.2.9's slots, if this is a RegExp String Iterator. Inline: five small fields.
    matches: Option<crate::heap::Matches>,
    /// §27.5.1's `[[GeneratorContext]]` — an execution parked in this object, if one is.
    ///
    /// `None` for every object that is not holding one, which is every object so far: nothing
    /// parks yet but a hand-written chunk. Boxed for the reason the collection beside it is — an
    /// `Object` sits inline in the arena, so whatever this costs is charged to every object ever
    /// made, and a suspension owns two `Vec`s and an `Rc`.
    ///
    /// The interpreter's, and deliberately opaque here: what is in it is frames and operands, and
    /// the heap's only business with it is holding it and letting the collector walk it.
    pub(super) suspension: Option<Box<crate::vm::Suspended>>,
    /// Which kind of suspendable execution this object holds, if it is one.
    ///
    /// `None` is "neither a generator nor an `async` function's context", which is what
    /// §27.5.1.2 step 2's `RequireInternalSlot` asks about before it will do anything — so
    /// `Generator.prototype.next.call({})` is a TypeError rather than an answer about an object
    /// that merely looks similar. It stays set once set: a finished generator is still a generator.
    ///
    /// There is deliberately no `[[GeneratorState]]` beside it. Every one of §27.5.1's four states
    /// is a *question about somewhere else* — suspended is "it holds a parked execution", executing
    /// is "a live frame names it", completed is neither — and a field repeating those answers is a
    /// field that can disagree with them. It did: a throw that escaped a generator's body left the
    /// state saying `executing` for ever, because nothing on that path had anywhere to write.
    pub(super) suspendable: Option<Suspendable>,
    /// §22.2.3's internal slots, if this is a regular expression.
    ///
    /// Boxed, because a compiled pattern owns a tree and every object would otherwise carry room
    /// for one.
    regexp: Option<Box<crate::heap::RegExp>>,
    /// §20.5's `[[ErrorData]]`, whose *presence* is the whole of what it says.
    ///
    /// A `bool` and not an `Option<()>` for that reason: the slot holds `undefined` in the
    /// specification and is never read, so what a program can learn from it is only that it is
    /// there. §20.1.3.6 step 7 is the one thing that asks, and it is why
    /// `Object.prototype.toString.call(new TypeError)` is `[object Error]` where an ordinary object
    /// given `Error.prototype` is `[object Object]` — the tag is a question about the object and
    /// not about its prototype chain, which is exactly the distinction the slot exists to make.
    error_data: bool,
    /// The own properties, in the order they were created.
    ///
    /// The order is not incidental — §10.1.11 hands out string keys "in ascending chronological
    /// order of property creation", so this `Vec` *is* that answer for part of the result.
    properties: Vec<(PropertyKey, Property)>,
    /// Where each key sits in `properties`, once there are enough of them to be worth it.
    ///
    /// `None` means "few enough to scan", which is the common case and costs nothing. `Some` is
    /// an exact index: every key in `properties` is in it, mapped to its position. Anything that
    /// disturbs the positions — a delete, which shifts everything after it — either updates this
    /// or rebuilds it, because a stale index would find the wrong property rather than none.
    ///
    /// Boxed so that an object without one pays a pointer rather than a whole hash table. An
    /// `Object` sits inline in the heap's arena, so its size is charged to every object ever
    /// made, live or swept — see [`Heap::footprint`] and DR-0010.
    ///
    /// Measured, because clippy is right to ask: a `HashMap` here makes `Option<Object>` 144 bytes
    /// and a `Box` makes it 104. Most objects never build one, so the forty bytes would be paid by
    /// every object in the program to save a pointer hop for a few.
    #[allow(clippy::box_collection)] // 40 bytes an object, and every object pays — see above
    index: Option<Box<HashMap<PropertyKey, usize>>>,
}

/// How many properties an object may hold before its keys are worth indexing.
///
/// Below this a scan of a short `Vec` beats a hash: the keys are interned, so comparing two is
/// comparing two integers, and eight of those cost less than hashing one. Above it the scan is
/// what makes filling an array quadratic.
///
/// The exact number is not delicate — anything in this region trades the same way, and the cases
/// that hurt have thousands of properties rather than nine.
const INDEXED_ABOVE: usize = 8;

impl Object {
    /// An ordinary object with the given prototype, no properties, and extensible.
    ///
    /// `OrdinaryObjectCreate` (§10.1.12) in the part that concerns the object itself. The
    /// prototype is an argument rather than a default because there is no default: an object
    /// literal gets `Object.prototype`, `Object.create(null)` gets nothing, and neither is more
    /// ordinary than the other.
    pub fn new(prototype: Option<ObjectId>) -> Self {
        Self {
            prototype,
            extensible: true,
            array: false,
            arguments: None,
            iteration: None,
            primitive: None,
            date: None,
            buffer: None,
            view: None,
            clamped: false,
            collection: None,
            promise: None,
            role: None,
            weak: None,
            helper: None,
            proxy: None,
            matches: None,
            suspension: None,
            suspendable: None,
            regexp: None,
            error_data: false,
            call: None,
            environment: None,
            lexical: None,
            private: None,
            home: None,
            properties: Vec::new(),
            index: None,
        }
    }

    /// The parameter map this object joins, if it is an arguments object.
    pub(crate) fn arguments_map(&self) -> Option<&ArgumentsMap> {
        self.arguments.as_deref()
    }

    /// Where this object has got to, if it is an iterator.
    pub fn iteration(&self) -> Option<&Iteration> {
        self.iteration.as_deref()
    }

    /// The same, to be moved on by a step.
    pub fn iteration_mut(&mut self) -> Option<&mut Iteration> {
        self.iteration.as_deref_mut()
    }

    /// Whether this object is something a call may reach — §7.2.3 `IsCallable`, for an object.
    pub fn is_callable(&self) -> bool {
        self.call.is_some()
    }

    /// Whether `new` may reach it — §7.2.4 `IsConstructor`.
    ///
    /// Not the same question: every constructor is callable and most callables are not
    /// constructors. An arrow, a method and a getter each have a `[[Call]]` and no `[[Construct]]`,
    /// which is why `new ({ m() {} }).m` is a TypeError.
    pub fn is_constructor(&self) -> bool {
        self.call.as_ref().is_some_and(super::Callable::constructs)
    }

    /// Whether this is a `Uint8ClampedArray`.
    pub fn is_clamped(&self) -> bool {
        self.clamped
    }

    /// Say that it is — §23.2.5's `Uint8ClampedArray` and nothing else.
    ///
    /// Takes no argument, so it is only ever called for the kind that *is* clamped. Written to take
    /// a Boolean it was called for all nine, and the eight that passed `false` were writing the
    /// value that was already there — which made the field's own default unreachable by any test.
    pub fn set_clamped(&mut self) {
        self.clamped = true;
    }

    /// The window this object is, if it is a `DataView`.
    pub fn view(&self) -> Option<View> {
        self.view
    }

    /// Make this object a `DataView` — §25.3.2.1, which is the only caller.
    pub fn set_view(&mut self, view: View) {
        self.view = Some(view);
    }

    /// The bytes this object holds, if it is an `ArrayBuffer`.
    pub fn buffer(&self) -> Option<&Buffer> {
        self.buffer.as_deref()
    }

    /// The same, to write through or to detach.
    pub fn buffer_mut(&mut self) -> Option<&mut Buffer> {
        self.buffer.as_deref_mut()
    }

    /// Make this object an `ArrayBuffer` — §25.1.3.1, which is the only caller.
    pub fn set_buffer(&mut self, buffer: Buffer) {
        self.buffer = Some(Box::new(buffer));
    }

    /// The entries this object holds, if it is a `Map` or a `Set`.
    ///
    /// `None` for every other object, which is the test every one of §24's methods makes first:
    /// `Map.prototype.get.call({})` is a TypeError rather than `undefined`, because the method is
    /// about the internal slot and not about a shape.
    pub fn collection(&self) -> Option<&Collection> {
        self.collection.as_deref()
    }

    /// The same, to change.
    pub fn collection_mut(&mut self) -> Option<&mut Collection> {
        self.collection.as_deref_mut()
    }

    /// Make this object a `Map` or a `Set` — §24.1.1.1 and §24.2.1.1 step 4.
    pub fn set_collection(&mut self, collection: Collection) {
        self.collection = Some(Box::new(collection));
    }

    /// What this object holds weakly, if it is a `WeakRef` or a `FinalizationRegistry`.
    pub fn weak(&self) -> Option<&Weak> {
        self.weak.as_deref()
    }

    /// The same, to change.
    pub fn weak_mut(&mut self) -> Option<&mut Weak> {
        self.weak.as_deref_mut()
    }

    /// Make this object one of §26's two, which nothing undoes.
    pub fn set_weak(&mut self, weak: Weak) {
        self.weak = Some(Box::new(weak));
    }

    /// The §27.1.5 helper state this object holds, if it is an Iterator Helper.
    pub fn helper(&self) -> Option<&Helper> {
        self.helper.as_deref()
    }

    /// The same, to change — a helper is state that moves as it is walked.
    pub fn helper_mut(&mut self) -> Option<&mut Helper> {
        self.helper.as_deref_mut()
    }

    /// Make this object an Iterator Helper, which nothing undoes.
    pub fn set_helper(&mut self, helper: Helper) {
        self.helper = Some(Box::new(helper));
    }

    /// §22.2.9's walk, if this object is a RegExp String Iterator.
    pub fn matches(&self) -> Option<crate::heap::Matches> {
        self.matches
    }

    /// The same, to move it on.
    pub fn matches_mut(&mut self) -> Option<&mut crate::heap::Matches> {
        self.matches.as_mut()
    }

    /// Make this object one — §22.2.9.1 `CreateRegExpStringIterator`.
    pub fn set_matches(&mut self, matches: crate::heap::Matches) {
        self.matches = Some(matches);
    }

    /// The compiled pattern this object holds, if it is a regular expression — §22.2.3.
    pub fn regexp(&self) -> Option<&crate::heap::RegExp> {
        self.regexp.as_deref()
    }

    /// Whether this object has §20.5's `[[ErrorData]]`.
    pub fn is_error(&self) -> bool {
        self.error_data
    }

    /// Give it that slot — what §20.5.1.1 and §20.5.6.1.1 do when they make an error.
    ///
    /// Separate from making the object because every error is built the ordinary way first and
    /// then marked: ViperJS makes four kinds of error object in three places, and a constructor
    /// that took a flag would be a flag three callers could pass wrongly.
    pub fn make_error(&mut self) {
        self.error_data = true;
    }

    /// Make this object a regular expression, or replace the pattern it already held.
    ///
    /// Replacing is what §22.2.3.1 does: `RegExp.prototype.compile` re-initialises an object that
    /// is already one, and nothing else in the language changes a pattern after it is made.
    pub fn set_regexp(&mut self, regexp: crate::heap::RegExp) {
        self.regexp = Some(Box::new(regexp));
    }

    /// The execution parked in this object, if one is — §27.5.1's `[[GeneratorContext]]`.
    pub(crate) fn suspension(&self) -> Option<&crate::vm::Suspended> {
        self.suspension.as_deref()
    }

    /// Which kind of suspendable this object is, if it is one — and not where it has got to.
    pub(crate) fn suspendable(&self) -> Option<Suspendable> {
        self.suspendable
    }

    /// Whether it is a *generator* — §27.5.1's brand, which is what the three resumptions want.
    pub(crate) fn is_generator(&self) -> bool {
        self.suspendable == Some(Suspendable::Generator)
    }

    /// Whether this is §27.6's async generator — the `RequireInternalSlot` of its three methods.
    pub(crate) fn is_async_generator(&self) -> bool {
        self.suspendable == Some(Suspendable::AsyncGenerator)
    }

    /// The target and handler this object proxies, if it is a Proxy — §10.5.
    pub fn proxy(&self) -> Option<Proxy> {
        self.proxy
    }

    /// The same, to revoke.
    pub fn proxy_mut(&mut self) -> Option<&mut Proxy> {
        self.proxy.as_mut()
    }

    /// Make this object a Proxy, which nothing undoes — revoking empties it rather than removing it.
    pub fn set_proxy(&mut self, proxy: Proxy) {
        self.proxy = Some(proxy);
    }

    /// The promise state this object holds, if it is a promise.
    pub fn promise(&self) -> Option<&Promise> {
        self.promise.as_deref()
    }

    /// The same, to settle.
    pub fn promise_mut(&mut self) -> Option<&mut Promise> {
        self.promise.as_deref_mut()
    }

    /// Make this object a pending promise — §27.2.3.1 step 3, which is the only caller.
    pub(super) fn set_promise(&mut self, promise: Promise) {
        self.promise = Some(Box::new(promise));
    }

    /// What this function object settles or fills in, if it is one of §27.2's.
    pub fn role(&self) -> Option<&Role> {
        self.role.as_deref()
    }

    /// The same, for a capability executor to write into when it is called.
    pub fn role_mut(&mut self) -> Option<&mut Role> {
        self.role.as_deref_mut()
    }

    /// Give this function object the state §27.2 describes as captured.
    pub fn set_role(&mut self, role: Role) {
        self.role = Some(Box::new(role));
    }

    /// The primitive this object wraps, if it wraps one.
    ///
    /// `None` for an ordinary object, which is most of them. What is in it says which kind of
    /// wrapper this is, so a method that requires its own kind matches on the value rather than
    /// asking a flag.
    pub fn primitive(&self) -> Option<Value> {
        self.primitive
    }

    /// The time value this object holds, if it is a Date — `[[DateValue]]`.
    ///
    /// `Some(NaN)` is a Date that is present and invalid, which is a different answer from `None`
    /// for something that is not a Date at all. Every `Date.prototype` method needs to tell those
    /// two apart: the first produces `NaN` or `"Invalid Date"`, the second a TypeError.
    pub fn date_value(&self) -> Option<f64> {
        self.date
    }

    /// Move a Date to another instant — `Date.prototype.setTime` and every other setter.
    ///
    /// The caller must already have established that this *is* a Date, which every setter in §21.4.4
    /// has: each one reads `thisTimeValue` before it computes anything, and a receiver without the
    /// slot has thrown by then. So there is no guard here — a branch no input can reach is a branch
    /// no test can pin, and one written defensively would only look tested.
    pub fn set_date_value(&mut self, value: f64) {
        self.date = Some(value);
    }

    /// The characters this object *is*, if it is a String exotic object — `[[StringData]]`.
    ///
    /// A wrapper around any other primitive answers `None`, which is what keeps `new Number(1)`
    /// from growing a property per digit.
    pub fn string_data(&self) -> Option<StringId> {
        match self.primitive {
            Some(Value::String(data)) => Some(data),
            _ => None,
        }
    }

    /// Whether this is an Array — §10.4.2's exotic object, and the only one there is.
    pub fn is_array(&self) -> bool {
        self.array
    }

    /// `[[GetPrototypeOf]]` (§10.1.1) — the prototype, or `None` for `null`.
    pub fn prototype(&self) -> Option<ObjectId> {
        self.prototype
    }

    /// What this object runs when it is called, if it is callable at all.
    ///
    /// `None` is what `typeof` reads to answer anything but `"function"`, and what a call
    /// expression checks before it does anything else.
    pub fn call(&self) -> Option<&Callable> {
        self.call.as_ref()
    }

    /// The environment this function was written in, if it is a function at all.
    pub fn environment(&self) -> Option<EnvironmentId> {
        self.environment
    }

    /// §7.3.28 `PrivateElementFind` — what this object holds under a Private Name, if anything.
    ///
    /// `None` covers both "no private elements at all" and "none under this name", because nothing
    /// distinguishes them: §7.3.31 `PrivateGet` throws for either, and it is the *same* TypeError.
    pub fn private_element(&self, name: SymbolId) -> Option<PrivateElement> {
        self.private
            .as_ref()?
            .iter()
            .find(|(key, _)| *key == name)
            .map(|(_, value)| *value)
    }

    /// Every private element, for the collector — a value here is reachable and nothing else holds it.
    pub(super) fn private_elements(&self) -> &[(SymbolId, PrivateElement)] {
        match &self.private {
            Some(elements) => elements,
            None => &[],
        }
    }

    /// The object this method was defined on — `[[HomeObject]]`, which is the super base minus a step.
    pub fn home_object(&self) -> Option<ObjectId> {
        self.home
    }

    /// What this function took from around it, if it is an arrow.
    ///
    /// `None` means the function binds `this` from the call, which is every function but an arrow
    /// — and also every non-function, which has no `this` to speak of either way.
    pub fn lexical(&self) -> Option<Lexical> {
        self.lexical
    }

    /// `[[IsExtensible]]` (§10.1.3).
    pub fn is_extensible(&self) -> bool {
        self.extensible
    }

    /// `[[PreventExtensions]]` (§10.1.4) — and there is no way back.
    ///
    /// Always succeeds, which is why it answers nothing: §10.1.4 returns `true` unconditionally.
    /// Existing properties are untouched — this stops *additions*, and a non-extensible object's
    /// configurable properties may still be deleted and redefined.
    pub fn prevent_extensions(&mut self) {
        self.extensible = false;
    }

    /// `[[GetOwnProperty]]` (§10.1.5) — the property filed under `key`, if there is one.
    ///
    /// Own only: nothing here walks the prototype chain, which is the difference between this and
    /// `[[Get]]`, and the difference `Object.hasOwn` exists to expose.
    pub fn get_own_property(&self, key: PropertyKey) -> Option<&Property> {
        let at = self.position(key)?;
        self.properties.get(at).map(|(_, property)| property)
    }

    /// Where `key` sits in `properties`, by whichever means this object has.
    ///
    /// The one place that decides how a key is found. Written twice — once for the scan and once
    /// for the map — the two could disagree about a key and only one of them would be right.
    fn position(&self, key: PropertyKey) -> Option<usize> {
        match &self.index {
            Some(index) => index.get(&key).copied(),
            None => self
                .properties
                .iter()
                .position(|(stored, _)| *stored == key),
        }
    }

    /// Build the index of every key's position, or rebuild one whose positions have moved.
    fn reindex(&mut self) {
        self.index = Some(Box::new(
            self.properties
                .iter()
                .enumerate()
                .map(|(at, (key, _))| (*key, at))
                .collect(),
        ));
    }

    /// Rebuild the key index after the positions have moved, if this object keeps one.
    ///
    /// Both ways of removing a property disturb every position after it, and an index that is
    /// wrong finds a *neighbouring* property rather than finding none — an error that reads as a
    /// plausible value. Asked in one place rather than at each of them: written twice, the second
    /// copy was a condition no program could tell either side of.
    fn reindex_if_kept(&mut self) {
        if self.index.is_some() {
            self.reindex();
        }
    }

    /// File `property` under `key`, replacing whatever was there.
    ///
    /// The write half of `[[DefineOwnProperty]]`, and private because it is only correct after
    /// [`validate`] has agreed. A new key goes on the end, which is what makes the `Vec` the
    /// creation order §10.1.11 asks for.
    pub(super) fn insert(&mut self, key: PropertyKey, property: Property) {
        if let Some(at) = self.position(key) {
            // A key that is already here keeps its place: §10.1.11's order is *creation* order,
            // so writing to a property again must not move it to the end.
            if let Some((_, existing)) = self.properties.get_mut(at) {
                *existing = property;
            }
            return;
        }
        let at = self.properties.len();
        self.properties.push((key, property));
        match &mut self.index {
            // Appending disturbs no existing position, so the index only gains an entry.
            Some(index) => {
                index.insert(key, at);
            }
            None if self.properties.len() > INDEXED_ABOVE => self.reindex(),
            None => {}
        }
    }

    /// `[[Delete]]` (§10.1.10) — remove the own property `key`, if it may be removed.
    ///
    /// A key that is not there answers `true`: deleting nothing succeeds, which is why
    /// `delete o.nothing` is `true` and says nothing about whether `o.nothing` existed.
    pub fn delete(&mut self, key: PropertyKey) -> bool {
        let Some(at) = self.position(key) else {
            return true;
        };
        if !self.properties[at].1.configurable {
            return false;
        }
        self.properties.remove(at);
        // Removing shifts every position after it, so the index is now wrong about all of them —
        // and wrong here means finding a *neighbouring* property rather than finding none, which
        // is the kind of error that reads as a plausible value. Rebuilding costs what the removal
        // already cost.
        self.reindex_if_kept();
        true
    }

    /// Remove every property whose key is in `doomed`, in one pass.
    ///
    /// The same result as calling [`Object::delete`] for each, and not the same cost. A single
    /// removal shifts everything after it and rebuilds the key index, both linear — so removing
    /// `n` properties one at a time is quadratic, and `a.length = 0` on an array of ten thousand
    /// was a hundred million hash inserts. `retain` shifts once and the index is rebuilt once.
    ///
    /// Configurability is **not** checked here: §10.4.2.4 decides which properties may go by
    /// walking them from the top down and stopping at the first that may not, and the answer it
    /// gives depends on that order. The caller has already done it and passes what survived.
    pub(super) fn delete_all(&mut self, doomed: &std::collections::HashSet<PropertyKey>) {
        self.properties.retain(|(key, _)| !doomed.contains(key));
        self.reindex_if_kept();
    }

    /// Every own key in the order they are *stored*, which is not the order §10.1.11 answers.
    ///
    /// For a caller that is going to sort or filter them anyway, and so pays nothing for the
    /// grouping [`Object::own_property_keys`] does. That grouping is three vectors and a sort of
    /// every key an object has, which is a great deal to do to find the few above an index.
    pub(super) fn stored_keys(&self) -> impl Iterator<Item = PropertyKey> + '_ {
        self.properties.iter().map(|(key, _)| *key)
    }

    /// `[[OwnPropertyKeys]]` (§10.1.11) — every own key, in the order the language guarantees.
    ///
    /// Array indices first in ascending numeric order, then every other String key in the order
    /// its property was created. That is why `{b: 1, 2: 2, a: 3, 1: 4}` enumerates as
    /// `1, 2, b, a`, and it is a guarantee rather than an implementation detail: the ordering was
    /// written into the specification in ES2015 because every engine already did it.
    ///
    /// Note *array* index, not integer index. `"4294967295"` is one too large to be an array
    /// index, so it sorts with the strings — the same boundary [`PropertyKey::as_array_index`]
    /// draws, and observable through this.
    /// A String object's characters are *not* among these, because they are not stored and this
    /// cannot make the keys that would name them. [`crate::heap::Heap::own_property_keys`] is the whole answer;
    /// this is the part of it the collector and the engine's own walks need, and neither of those
    /// cares about a character.
    pub fn own_property_keys(&self) -> Vec<PropertyKey> {
        let mut indices: Vec<(u32, PropertyKey)> = Vec::new();
        let mut names: Vec<PropertyKey> = Vec::new();
        // §10.1.11 step 4 — every Symbol key comes after every String one, in the order they were
        // added. A third list rather than a sort, because the order *within* each group is
        // insertion order and a sort would have to be told not to disturb it.
        let mut symbols: Vec<PropertyKey> = Vec::new();
        for (key, _) in &self.properties {
            match (key.as_symbol(), key.as_array_index()) {
                (Some(_), _) => symbols.push(*key),
                (None, Some(index)) => indices.push((index, *key)),
                (None, None) => names.push(*key),
            }
        }
        // Ascending *numeric* order, which is why the index came back as a number: sorting the
        // keys as text would put "10" before "9".
        indices.sort_unstable_by_key(|(index, _)| *index);
        indices
            .into_iter()
            .map(|(_, key)| key)
            .chain(names)
            .chain(symbols)
            .collect()
    }

    /// How many own properties there are.
    ///
    /// For tests and for whatever reports on the heap. Counts every own property, enumerable or
    /// not — `Object.keys().length` is a different and smaller number.
    pub fn property_count(&self) -> usize {
        self.properties.len()
    }
}

/// How far any prototype walk goes before giving up.
///
/// Not a limit the language has: an acyclic chain of a million objects is legal and this would
/// answer wrongly about it. It is a backstop for DR-0002 — a walk that cannot terminate is a hang,
/// and "the cycle check is correct" is exactly the kind of claim that should not be the only thing
/// standing between an engine and one. Every chain a program actually builds is a handful long;
/// the figure is deliberately far above that and deliberately not a guess about correctness.
pub(crate) const MAX_PROTOTYPE_CHAIN: usize = 100_000;

#[cfg(test)]
#[path = "tests.rs"]
mod object_tests;

#[cfg(test)]
mod tests {
    use super::*;
    // Named here rather than at the top of the file: §10.1's internal methods moved next door to
    // `ordinary`, and these are the only rows left that build a descriptor by hand. `Heap` joined
    // them when DR-0026 took it out of `own_property_keys` — a key knows its own index now, so the
    // only thing left in this file wanting a heap is a test that builds one.
    use crate::heap::{Heap, PropertyDescriptor, PropertyKind};

    fn key(heap: &mut Heap, text: &str) -> PropertyKey {
        PropertyKey::from_units(heap, &text.encode_utf16().collect::<Vec<_>>())
    }

    fn data(value: f64) -> PropertyDescriptor {
        PropertyDescriptor {
            value: Some(Value::Number(value)),
            writable: Some(true),
            enumerable: Some(true),
            configurable: Some(true),
            ..PropertyDescriptor::EMPTY
        }
    }

    /// Whether `object` is keeping an index of its keys.
    fn indexed(heap: &Heap, object: ObjectId) -> bool {
        heap.object(object)
            .is_some_and(|found| found.index.is_some())
    }

    #[test]
    fn keys_are_indexed_only_once_there_are_more_of_them_than_it_costs_to_scan() {
        // This test looks at a private field, which the rest of this file's tests are careful not
        // to do — and the reason is the point. The index changes no answer: every question about
        // a property has the same answer whether it was found by a scan or by a hash. So no test
        // written in JavaScript can say when one is built, and a policy nothing can observe is a
        // policy nothing is holding in place.
        let mut heap = Heap::new();
        let object = heap.new_object(None);
        for at in 0..INDEXED_ABOVE {
            let key = key(&mut heap, &format!("k{at}"));
            heap.define_own_property(object, key, &data(at as f64));
            assert!(
                !indexed(&heap, object),
                "{} properties is still few enough to scan",
                at + 1
            );
        }
        // One more than the threshold, and not one fewer: an object holding exactly
        // `INDEXED_ABOVE` is on the cheap side of the trade.
        let over = key(&mut heap, "one-too-many");
        heap.define_own_property(object, over, &data(99.0));
        assert!(indexed(&heap, object));

        // A small object that has something deleted does not acquire one on the way past — the
        // rebuild after a delete is for an index that already exists, not a reason to build one.
        let small = heap.new_object(None);
        let only = key(&mut heap, "only");
        heap.define_own_property(small, only, &data(1.0));
        assert!(
            heap.object_mut(small)
                .is_some_and(|found| found.delete(only))
        );
        assert!(!indexed(&heap, small));
    }

    #[test]
    fn an_indexed_object_finds_every_key_it_still_has_after_a_delete() {
        // The failure this guards against is not "cannot find it" — it is finding the *wrong*
        // one. Removing a property shifts every position after it, so an index left unrebuilt
        // answers each of those keys with its neighbour: a plausible value, not a crash.
        let mut heap = Heap::new();
        let object = heap.new_object(None);
        let count = INDEXED_ABOVE * 3;
        let keys: Vec<_> = (0..count)
            .map(|at| {
                let key = key(&mut heap, &format!("k{at}"));
                heap.define_own_property(object, key, &data(at as f64));
                key
            })
            .collect();
        assert!(indexed(&heap, object));

        // Delete from the front, where the most positions move.
        assert!(
            heap.object_mut(object)
                .is_some_and(|found| found.delete(keys[0]))
        );
        for (at, key) in keys.iter().enumerate().skip(1) {
            let found = heap
                .object(object)
                .and_then(|found| found.get_own_property(*key))
                .map(|property| property.kind);
            assert!(
                matches!(
                    found,
                    Some(PropertyKind::Data {
                        value: Value::Number(number),
                        ..
                    }) if number == at as f64
                ),
                "k{at} answered with the wrong property after a delete shifted it"
            );
        }
        assert!(
            heap.object(object)
                .and_then(|found| found.get_own_property(keys[0]))
                .is_none()
        );
    }
}