-
Notifications
You must be signed in to change notification settings - Fork 8
Expand file tree
/
Copy pathcollection.js
More file actions
3508 lines (3376 loc) · 223 KB
/
Copy pathcollection.js
File metadata and controls
3508 lines (3376 loc) · 223 KB
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
/**
* Collection module — Set, Map, HASH (dynamic string-keyed objects).
*
* Set: type=8, open addressing hash table. Entries: [hash|seq:8, key:8] (16B each).
* Map: type=9, same but entries: [hash|seq:8, key:8, val:8] (24B each).
* HASH: type=7, same layout as Map but uses content-based string hash + equality.
* Every table additionally carries an i32 HASH LANE (cap × 4 B) AFTER the entry
* region — the only thing probes walk (see probeStart) — so allocations are
* cap × (entrySize + 4) bytes; entry offsets and iteration are unchanged.
*
* @module collection
*/
import { typed, asF64, asI64, asI32, NULL_NAN, UNDEF_NAN, TOMB_NAN, temp, tempI32, tempI64, allocPtr, undefExpr, mkPtrIR, ptrTypeEq, elemStore, elemLoad, extractF64Bits } from '../src/ir.js'
import { emit, deps, call, storedValue } from '../src/bridge.js'
import { valTypeOf } from '../src/kind.js'
import { VAL, lookupValType } from '../src/reps.js'
import { hasOwnContinue, isBlockBody, isLiteralStr } from '../src/ast.js'
import { ctx, inc, PTR, LAYOUT, registerGetter, declGlobal } from '../src/ctx.js'
import { STR_INTERN_BIT, STR_HCACHE_BIT, ssoBitI64Hex, encodePtrHi, i64Hex } from '../layout.js'
import { ssoEncode } from './string.js'
import { ERR } from '../err-codes.js'
const SSO_BIT_I64 = ssoBitI64Hex()
// NaN-box bits of the SSO string 'length' — computed once; see the STRING
// arm in __dyn_get_t_h and __length's property-fallback arm (module/core.js).
// ssoEncode('length') never returns null (6 ASCII).
export const LENGTH_SSO_I64 = (() => { const e = ssoEncode('length'); return i64Hex((BigInt(encodePtrHi(4, e.aux) >>> 0) << 32n) | BigInt(e.offset)) })()
// Exported for module/core.js's __region_exit (region-arena design, Slice 1):
// the round-loop's own `dirty`/`snapshots` bookkeeping is a Set/Map of func-node
// (ARRAY) pointers that must be relocated in lockstep with the tree itself — the
// region copy builds a same-shaped SET/MAP at the compacted target using these
// exact stride/capacity constants, mirroring __sclone_rec's SET/MAP branch.
export const SET_ENTRY = 16 // hash + key
export const MAP_ENTRY = 24 // hash + key + value
export const INIT_CAP = 8 // initial capacity (must be power of 2)
// __dyn_props global-table membership filter (see __dyn_props_filter's declGlobal
// comment). offExpr is an i32 WAT expr for the offset key. Mix folds the offset's
// mid bits (allocations are 8-byte aligned, so raw low bits are useless) down to
// a 6-bit bucket in a 64-bit bitset — never-false-negative, no false-negative risk
// from collisions (a collision just makes the filter's "maybe present" wider).
const dynPropsFilterBitIR = (offExpr) =>
`(i64.shl (i64.const 1) (i64.extend_i32_u (i32.and (i32.xor (i32.shr_u ${offExpr} (i32.const 3)) (i32.shr_u ${offExpr} (i32.const 9))) (i32.const 63))))`
// Set the filter bit for an offset key that was just inserted into the global table.
export const dynPropsFilterSetIR = (offExpr) =>
`(global.set $__dyn_props_filter (i64.or (global.get $__dyn_props_filter) ${dynPropsFilterBitIR(offExpr)}))`
// True (i32) when the filter bit is clear — i.e. offExpr is PROVEN never inserted,
// safe to skip the __ihash_get_local probe entirely. False (bit set) means "maybe
// present, maybe a collision" — falls through to the real probe.
export const dynPropsFilterMissIR = (offExpr) =>
`(i64.eqz (i64.and (global.get $__dyn_props_filter) ${dynPropsFilterBitIR(offExpr)}))`
// The post-init high-water mark (see module/core.js's __heap_reset) as a WAT operand —
// everything at/above it is EPHEMERAL (this compile's own arena, wiped by `_clear`);
// everything below it is DURABLE (module-init state, survives `_clear` forever). Falls
// back to a literal 0 (every offset reads as "ephemeral") when the module has no
// `__heap_reset` global at all (no allocator, or shared memory, whose reset is a plain
// HEAP.START rewind with no high-water-mark concept — see core.js). Read at
// template-EXPANSION time (thunked callers only — see durableFwdLogIR/heapResetWat
// consumers), so it observes the FINAL declaration state, not whatever was true when
// collection.js's own module body first ran.
//
// DURABLE-RECEIVER POLICY (dyn-props twin of the above): a receiver allocated
// at/below __heap_reset outlives `_clear()`, but a sidecar installed for it at
// RUNTIME lives in the round's arena — the surviving header slot then dangles
// across `_clear()` and the next round corrupts reused memory. So runtime
// dyn-prop writes on a durable receiver (off < __heap_reset) route to the
// GLOBAL __dyn_props table instead — __clear resets it, so prop lifetime
// matches storage lifetime. Init-time writes still land in durable sidecars
// (__heap_reset is seeded to data-end until __start's tail captures the
// post-init top, so off >= __heap_reset holds throughout init). Every read/
// write/delete/enumerate site that consults a header sidecar gates on this —
// see module/object.js's emitEnumerateObject and module/json.js's __json_obj
// for the array-IR / WAT-string twins that merge in the global table for
// durable receivers.
export const heapResetWat = () => ctx.scope.globals.has('__heap_reset') ? '(global.get $__heap_reset)' : '(i32.const 0)'
// A growable ARRAY/HASH/SET/MAP relocates by leaving a forwarding header behind
// (cap=-1 sentinel at off-4, new offset at off-8 — see layout.js's followForwardingWat).
// That is only safe WITHIN one compile round: `_clear()` rewinds the arena but never
// zeroes memory, so a forward written into a DURABLE header (offOld < __heap_reset,
// i.e. the block predates this round) permanently points at an EPHEMERAL target that
// the next round's allocations silently overwrite — any later chase through the
// durable alias then lands on garbage or goes OOB (.work/todo.md groundtruth archive,
// "array-growth forwarding is not _clear-safe"). Growing an EPHEMERAL block needs no
// protection: everything reachable from it is ephemeral too, so the whole chain (old
// header, new header, and every durable-side reference to it — there are none, by
// construction) is reclaimed together at `_clear()`.
//
// Fix: at the grow/shift site, BEFORE writing the forward (while off/len/cap — the
// header's pre-relocation state — are still live locals), log the durable→ephemeral
// transition to a small resettable side-table (module/core.js's __durable_fwd_log/
// __durable_fwd_heal) instead of (or rather: in addition to, so the in-round chase
// still works) trusting the header alone. `_clear()` then HEALS each logged header
// back to its exact pre-relocation (len, cap) — undoing the forward mark, so the
// durable block reverts to self-contained, non-forwarding, and correct (its own
// element/entry cells were never touched by the relocation; only the header words
// were). This keeps followForwardingWat/__ptr_offset_fwd (the hot chase, ~25% of
// self-host compile ticks) completely UNTOUCHED — the check only runs on the already-
// cold relocation path, and the heal sweep only runs inside `_clear()`, bounded by
// however many durable relocations happened that round (0 in the overwhelmingly
// common case).
//
// Checks BOTH ends, not just "is off durable": a fresh `__alloc_hdr`/`__alloc_hdr_n`
// target (grow, genUpsert/genUpsertGrow) is unconditionally ephemeral whenever the
// source-durable check can even fire (any allocation live past `__start`'s tail-
// capture is by construction >= the now-final `__heap_reset`), so newOff's own check
// is redundant there — but `.shift()`'s "new" header is just `off + 8`, a position
// INSIDE the same block, not a fresh allocation: ordinarily still durable (shifting a
// durable array is legitimate, persistent state and must NOT be undone at `_clear`),
// and only crosses into ephemeral in the one-in-8-bytes edge case where `off` sits
// exactly at `__heap_reset - 8`. Requiring both conditions everywhere makes the
// invariant self-evidently correct at every call site instead of relying on a
// per-caller argument about what its "new" offset can be.
// Emits nothing at all (not even a call site) when there's no `__heap_reset` to compare
// against — shared memory's `__clear` is a plain rewind-to-HEAP.START with no high-water
// mark (core.js), so EVERYTHING resets uniformly there and no state is ever "durable" to
// begin with (a separate, pre-existing, documented gap — see core.js's shared-memory
// `__clear` comment). Testing `ctx.scope.globals.has('__heap_reset')` directly (not just
// deferring to heapResetWat()'s own `(i32.const 0)` fallback, which would still emit an
// always-false-but-present call) matters for self-host inclusion: array.js's/
// collection.js's deps() edges declare '__durable_fwd_log' unconditionally at every grow/
// shift site, so core.js must ALSO unconditionally register the function whenever those
// sites exist — but core.js only defines __durable_fwd_log/__durable_fwd_heal in the
// owned-memory branch (they need __heap/__heap_reset, which shared memory doesn't have).
// A shared-memory build reaching this function with the fallback would therefore
// reference a never-registered stdlib name, tripping assemble.js's `internal: stdlib
// '__durable_fwd_log' was requested but never registered` sanity check.
export const durableFwdLogIR = (off, newOff, len, cap) => {
if (!ctx.scope.globals.has('__heap_reset')) return ''
return `
(if (i32.and (i32.lt_u (local.get $${off}) ${heapResetWat()}) (i32.ge_u (local.get $${newOff}) ${heapResetWat()}))
(then (call $__durable_fwd_log (local.get $${off}) (local.get $${len}) (local.get $${cap}))))`
}
// Value-write sibling of durableFwdLogIR: an EPHEMERAL boxed value stored into a
// DURABLE collection slot dangles across `_clear` (the corpus-wide warm trap — a
// durable memo dict handing round-1 node arrays into round-2's tree). Log the slot
// so `__durable_slot_heal` (wired into `__clear`) overwrites it with `undefined` —
// the pointed-at data dies with the arena, so entry-death is the only sound
// semantics. `slotLocal`+`byteOff` name the value slot; `valLocal` holds the boxed
// bits (i64). Same shared-memory gate as durableFwdLogIR (no watermark, no sweep).
export const durableSlotLogIR = (slotLocal, byteOff, valLocal) => {
if (!ctx.scope.globals.has('__heap_reset')) return ''
const addr = byteOff ? `(i32.add (local.get $${slotLocal}) (i32.const ${byteOff}))` : `(local.get $${slotLocal})`
return `
(if (i32.and (i32.lt_u ${addr} ${heapResetWat()}) (call $__is_eph_bits (local.get $${valLocal})))
(then (call $__durable_slot_log ${addr} (i32.const 0))))`
}
// ENTRY-insert variant: a NEW entry inserted into DURABLE table storage is
// round state regardless of what the key/value are — a fresh instance would not
// have the entry at all, and an ephemeral KEY can't even be value-healed (probes
// and enumeration would hash/compare the dangling box; measured: warm round 2
// hashed 15.5 MB of garbage-length "strings" where round 1 hashed 415 KB — the
// whole 2× warm-vs-fresh gap). Log the ENTRY base with bit0 set plus the table
// storage base; the heal turns the entry into a zombie — key ← TOMB_NAN
// (unforgeable, deref-free in every eq family), value ← undefined, table len
// decremented — that probes pass over and __coll_order/len-sized iterations
// skip. The slot stays occupied until the table grows (zombies never resurrect:
// nothing eq-matches TOMB_NAN). Entry addresses are 8-aligned → bit0 is free.
export const durableEntryLogIR = (slotLocal, offLocal) => {
if (!ctx.scope.globals.has('__heap_reset')) return ''
return `
(if (i32.lt_u (local.get $${slotLocal}) ${heapResetWat()})
(then (call $__durable_slot_log (i32.or (local.get $${slotLocal}) (i32.const 1)) (local.get $${offLocal}))))`
}
// Clamp to the >=2 convention (0=empty slot, 1=tombstone) — shared by every hash
// producer (SSO mix, byte-FNV, __jp_str, buildInternTable) so they all clamp identically.
const clampHash = (h) => (h <= 1 ? (h + 2) | 0 : h)
// SSO mix: 7 ops over the packed NaN-box lo/hi (see __str_hash's SSO branch,
// module/collection.js below, for the WAT twin — both MUST compute the same value).
// lo = offset (payload bits 0-31), hi = aux masked to bits 0-12 (length + char 4-5
// tail — SSO_BIT itself is excluded by the mask, so hi only carries discriminating
// content). Replaces the old 6-iteration per-char FNV loop with a fixed-cost mix.
const ssoMix = (lo, hi) => {
let h = Math.imul(hi ^ 0x9E3779B9, 0x85EBCA6B)
h = Math.imul(lo ^ h, 0xC2B2AE35)
h = (h ^ (h >>> 15)) | 0
return clampHash(h) >>> 0
}
// Byte-FNV-1a over UTF-8-ish bytes (charCodeAt & 0xFF — ASCII-only callers guarantee
// codepoint < 0x80, so this equals the byte value). Heap strings (>6 bytes or non-ASCII)
// keep this; __str_hash's heap branch and buildInternTable's static-intern prehash both
// compute the identical function — see module/string.js bind('str') and internProbeWat.
const byteFnv = (str) => {
let h = 0x811c9dc5 | 0
for (let i = 0; i < str.length; i++) h = Math.imul(h ^ (str.charCodeAt(i) & 0xFF), 0x01000193) | 0
return clampHash(h)
}
// Compile-time hash for an ASCII string LITERAL — must equal __str_hash's runtime
// result for the same content: ≤6-ASCII strings are ALWAYS SSO (module/string.js header
// invariant), so they use the new ssoMix; longer/non-ASCII strings stay on heap and use
// byte-FNV. Callers (litKeyHash below, module/core.js, module/array.js, module/json.js)
// pass ASCII content — non-ASCII goes through the runtime __str_hash path instead.
export function strHashLiteral(str) {
const sso = ssoEncode(str)
if (sso) return ssoMix(sso.offset | 0, sso.aux & 0x1FFF)
return byteFnv(str)
}
const HASH_BUF = new ArrayBuffer(8)
const HASH_F64 = new Float64Array(HASH_BUF)
const HASH_U32 = new Uint32Array(HASH_BUF)
export function numHashLiteral(n) {
if (Object.is(n, 0) || Object.is(n, -0)) return 2
HASH_F64[0] = n
const h = (HASH_U32[0] ^ HASH_U32[1]) | 0
return h <= 1 ? (h + 2) | 0 : h
}
function numConstLiteral(expr) {
if (typeof expr === 'number' && Number.isFinite(expr)) return expr
if (Array.isArray(expr) && expr[0] == null && typeof expr[1] === 'number' && Number.isFinite(expr[1])) return expr[1]
return null
}
// Compile-time probe hash for a LITERAL collection/property key, else null. A numeric
// constant → numHashLiteral; an ASCII string literal → strHashLiteral. The string case is
// ASCII-only on purpose: strHashLiteral's byte-FNV branch folds `charCodeAt(i) & 0xFF`,
// which equals __str_hash / __map_hash (FNV-1a over the UTF-8 bytes) ONLY for code points
// < 0x80 — a non-ASCII literal would fold a different hash than its stored key and silently
// miss, so it falls back to the runtime hash. (The ≤6-ASCII branch uses the SSO mix instead —
// still ASCII-only, since ssoEncode itself rejects non-ASCII and returns null.) Lets
// `m.get("if")` / `m.has("x")` skip the per-access __map_hash call.
const ASCII_KEY = /^[\x00-\x7f]*$/
const litKeyHash = (key) => {
const num = numConstLiteral(key)
if (num != null) return numHashLiteral(num)
if (isLiteralStr(key) && ASCII_KEY.test(key[1])) return strHashLiteral(key[1])
return null
}
// Key-equality expressions for probe templates — run only after a LANE hash hit
// (the probe skeleton compares hashes; these decide the hit). The inline
// `storedKey == queryKey` bit-eq decides the overwhelmingly-common identity case
// — interned/SSO literals and the same heap pointer are bit-equal — WITHOUT the
// __str_eq / __same_value_zero call frame. Sound for both: bit-equality implies
// string-equality and SameValueZero (the only cross-bit-pattern equals — +0/-0,
// distinct NaN payloads — fall through to the full compare, never the reverse).
const keyEq = (fullEq) =>
`(if (result i32)
(i64.eq (i64.load (i32.add (local.get $slot) (i32.const 8))) (local.get $key))
(then (i32.const 1))
(else ${fullEq}))`
const strEqG = keyEq('(call $__str_eq (i64.load (i32.add (local.get $slot) (i32.const 8))) (local.get $key))')
const sameValueZeroEqG = keyEq('(call $__same_value_zero (i64.load (i32.add (local.get $slot) (i32.const 8))) (local.get $key))')
const bitEq = '(i64.eq (i64.load (i32.add (local.get $slot) (i32.const 8))) (local.get $key))'
// HASH-LANE probe. Entries keep the classic layout ([hash|seq:8][key:8][val:8] —
// iteration, heal, durable logs, delete-shift and clones are untouched), but a
// parallel i32 HASH LANE (cap × 4 B, zero-filled, AFTER the entry region) is what
// probes WALK: one 4-byte load per step, 16 hash checks per cache line where the
// 24-byte entry stride gave 2-3, and a miss chain touches an 8 kB lane instead of
// sweeping a 48 kB table through L1 (the wordcount-vs-C probe-footprint gap).
// Empty ⇔ lane word 0 (hash clamp keeps real hashes ≥ 2); healed zombies KEEP
// their stale hash in the lane and are passed by the key compare exactly as the
// entry-walk passed them. $ls walks the lane ($lb/$end its bounds); $slot (the
// entry address) derives only on a hash hit / at the insert slot. Every table
// alloc pays entrySize+4 per slot; the entry region offsets are unchanged.
export const LANE = 4
const probeStart = (entrySize, idxExpr = '(i32.and (local.get $h) (i32.sub (local.get $cap) (i32.const 1)))') =>
`(local.set $lb (i32.add (local.get $off) (i32.mul (local.get $cap) (i32.const ${entrySize}))))
(local.set $end (i32.add (local.get $lb) (i32.shl (local.get $cap) (i32.const 2))))
(local.set $ls (i32.add (local.get $lb) (i32.shl ${idxExpr} (i32.const 2))))`
const probeNext = () =>
`(local.set $ls (i32.add (local.get $ls) (i32.const 4)))
(if (i32.ge_u (local.get $ls) (local.get $end)) (then (local.set $ls (local.get $lb))))`
// entry address of the lane cursor's slot
const slotFromLane = (entrySize) =>
`(local.set $slot (i32.add (local.get $off)
(i32.mul (i32.shr_u (i32.sub (local.get $ls) (local.get $lb)) (i32.const 2)) (i32.const ${entrySize}))))`
// probe-loop locals shared by every template
const laneLocals = '(local $lb i32) (local $ls i32) (local $hw i32)'
// cap-tries exhausted with no remembered zombie: rescan for any TOMB key via
// the shared cold helper (an all-zombies-with-foreign-hashes table —
// durable-heal-heavy warm embedders only; the lane probe only notices zombies
// on a hash hit). $__zomb_scan falls back to slot 0 when the table is truly
// full of live keys, which the 75%-load grow makes unreachable.
const zombieRescan = (entrySize) => `(if (i32.eqz (local.get $zb)) (then
(local.set $zb (call $__zomb_scan (local.get $off) (local.get $cap) (i32.const ${entrySize})))
(local.set $zbl (i32.add (local.get $lb)
(i32.shl (i32.div_u (i32.sub (local.get $zb) (local.get $off)) (i32.const ${entrySize})) (i32.const 2))))))`
// Store a fresh entry's hash word, packing a monotonic insertion sequence
// (global $__seq) into its free high 32 bits. The hash itself only ever occupies
// the low 32 (always ≥2), so "empty slot ⇔ word==0" and the i32.wrap_i64
// home-bucket math are untouched; rehash/back-shift copy the whole word, so the
// sequence rides along for free. Iteration reads it back (via __coll_order) to
// restore JS insertion order. Emitted only on the insert-new branch — updates
// keep the original entry (and its sequence) in place.
const seqStore = `(i64.store (local.get $slot)
(i64.or (i64.extend_i32_u (local.get $h)) (i64.shl (i64.extend_i32_u (global.get $__seq)) (i64.const 32))))
(global.set $__seq (i32.add (global.get $__seq) (i32.const 1)))`
/** Generate upsert (add/set) probe for a growable collection (Set/Map). hasVal: store
* value at slot+16. hasExt: emit EXTERNAL fallthrough (call $__ext_set on non-matching
* type). Gated off → type mismatch just returns coll unchanged.
*
* The table grows at 75% load by allocating a 2× table, rehashing, and forward-marking
* the old header (cap=-1 sentinel, new offset at -8) — the array growth idiom. The boxed
* pointer the caller holds is returned UNCHANGED; future ops resolve it through
* __ptr_offset, which follows the chain. This is why Set/Map (held in caller locals, and
* possibly aliased) forward rather than remint like HASH (whose pointer lives in a single
* owner's propsPtr slot that genUpsertGrow can rewrite). */
function genUpsert(name, entrySize, hashFn, eqExpr, expectedType, hasVal, hasExt) {
const valParam = hasVal ? '(param $val i64) ' : ''
const slotLog = hasVal ? durableSlotLogIR('slot', 16, 'val') : ''
const storeVal = hasVal ? `\n (i64.store (i32.add (local.get $slot) (i32.const 16)) (local.get $val))${slotLog}` : ''
const onMatch = hasVal
? `(then\n (i64.store (i32.add (local.get $slot) (i32.const 16)) (local.get $val))${slotLog}\n (br $done))`
: `(then (br $done))`
const rehashVal = hasVal
? `\n (i64.store (i32.add (local.get $newslot) (i32.const 16)) (i64.load (i32.add (local.get $oldslot) (i32.const 16))))`
: ''
const extBranch = hasVal
? '(then (call $__ext_set (local.get $coll) (local.get $key) (local.get $val)) drop)'
: '(then (nop))'
const tExpr = `(i32.wrap_i64 (i64.and (i64.shr_u (local.get $coll) (i64.const ${LAYOUT.TAG_SHIFT})) (i64.const ${LAYOUT.TAG_MASK})))`
const typeGuard = hasExt
? `(if (i32.ne ${tExpr} (i32.const ${expectedType})) (then (if (i32.eq ${tExpr} (i32.const ${PTR.EXTERNAL})) ${extBranch}) (return (local.get $coll))))`
: `(if (i32.ne ${tExpr} (i32.const ${expectedType})) (then (return (local.get $coll))))`
return `(func $${name} (param $coll i64) (param $key i64) ${valParam}(result i64)
(local $off i32) (local $cap i32) (local $h i32) (local $end i32) (local $slot i32)
(local $size i32) (local $newptr i32) (local $newcap i32) (local $i i32)
(local $oldslot i32) (local $newidx i32) (local $newslot i32) (local $zb i32) (local $ztr i32)
${laneLocals} (local $zbl i32) (local $nlb i32)
${typeGuard}
(local.set $off (i32.wrap_i64 (i64.and (local.get $coll) (i64.const ${LAYOUT.OFFSET_MASK}))))
(local.set $cap (i32.load (i32.sub (local.get $off) (i32.const 4))))
;; the cap load IS the forward check: -1 sentinel hops via the cold helper,
;; the live path pays zero extra — the per-probe __ptr_offset call drops
(if (i32.eq (local.get $cap) (i32.const -1))
(then
(local.set $off (call $__ptr_offset_fwd (local.get $off)))
(local.set $cap (i32.load (i32.sub (local.get $off) (i32.const 4))))))
(local.set $size (i32.load (i32.sub (local.get $off) (i32.const 8))))
;; Grow at 75% load (size*4 >= cap*3): 2× table, rehash, forward-mark old header.
(if (i32.ge_s (i32.mul (local.get $size) (i32.const 4)) (i32.mul (local.get $cap) (i32.const 3)))
(then
(local.set $newcap (i32.shl (local.get $cap) (i32.const 1)))
(local.set $newptr (call $__alloc_hdr_n (i32.const 0) (local.get $newcap) (i32.const ${entrySize + LANE})))
(local.set $nlb (i32.add (local.get $newptr) (i32.mul (local.get $newcap) (i32.const ${entrySize}))))
(i64.store (i32.sub (local.get $newptr) (i32.const 16)) (i64.load (i32.sub (local.get $off) (i32.const 16))))
(local.set $i (i32.const 0))
(block $rd (loop $rl
(br_if $rd (i32.ge_s (local.get $i) (local.get $cap)))
(local.set $oldslot (i32.add (local.get $off) (i32.mul (local.get $i) (i32.const ${entrySize}))))
(if (i64.ne (i64.load (local.get $oldslot)) (i64.const 0))
(then
(local.set $h (call ${hashFn} (i64.load (i32.add (local.get $oldslot) (i32.const 8)))))
(local.set $newidx (i32.and (local.get $h) (i32.sub (local.get $newcap) (i32.const 1))))
(block $ins (loop $probe2
(local.set $newslot (i32.add (local.get $newptr) (i32.mul (local.get $newidx) (i32.const ${entrySize}))))
(br_if $ins (i64.eqz (i64.load (local.get $newslot))))
(local.set $newidx (i32.and (i32.add (local.get $newidx) (i32.const 1)) (i32.sub (local.get $newcap) (i32.const 1))))
(br $probe2)))
(i64.store (local.get $newslot) (i64.load (local.get $oldslot)))
(i64.store (i32.add (local.get $newslot) (i32.const 8)) (i64.load (i32.add (local.get $oldslot) (i32.const 8))))${rehashVal}
(i32.store (i32.add (local.get $nlb) (i32.shl (local.get $newidx) (i32.const 2))) (local.get $h))
(i32.store (i32.sub (local.get $newptr) (i32.const 8))
(i32.add (i32.load (i32.sub (local.get $newptr) (i32.const 8))) (i32.const 1)))))
(local.set $i (i32.add (local.get $i) (i32.const 1)))
(br $rl)))
${durableFwdLogIR('off', 'newptr', 'size', 'cap')}
(i32.store (i32.sub (local.get $off) (i32.const 8)) (local.get $newptr))
(i32.store (i32.sub (local.get $off) (i32.const 4)) (i32.const -1))
(local.set $off (local.get $newptr))
(local.set $cap (local.get $newcap))))
(local.set $h (call ${hashFn} (local.get $key)))
${probeStart(entrySize)}
;; zombie-aware LANE probe (durable-slot heal, TOMB_NAN keys): a zombie keeps
;; its stale hash in the lane, so it is only NOTICED on a hash hit (key reads
;; TOMB) — reuse still catches the dominant re-insert-same-key case, and the
;; cap-tries fallback rescans for any zombie before giving up.
(block $done (loop $probe
(local.set $hw (i32.load (local.get $ls)))
(if (i32.eqz (local.get $hw))
(then
(if (local.get $zb)
(then (local.set $slot (local.get $zb)) (local.set $ls (local.get $zbl)))
(else ${slotFromLane(entrySize)}))
${seqStore}
(i32.store (local.get $ls) (local.get $h))
(i64.store (i32.add (local.get $slot) (i32.const 8)) (local.get $key))${durableEntryLogIR('slot', 'off')}${storeVal}
(i32.store (i32.sub (local.get $off) (i32.const 8))
(i32.add (i32.load (i32.sub (local.get $off) (i32.const 8))) (i32.const 1)))
(br $done)))
(if (i32.eq (local.get $hw) (local.get $h))
(then
${slotFromLane(entrySize)}
(if (i64.eq (i64.load (i32.add (local.get $slot) (i32.const 8))) (i64.const ${TOMB_NAN}))
(then (if (i32.eqz (local.get $zb))
(then (local.set $zb (local.get $slot)) (local.set $zbl (local.get $ls)))))
(else (if ${eqExpr} ${onMatch})))))
${probeNext()}
(local.set $ztr (i32.add (local.get $ztr) (i32.const 1)))
(if (i32.ge_s (local.get $ztr) (local.get $cap))
(then
${zombieRescan(entrySize)}
(local.set $slot (local.get $zb))
(local.set $ls (local.get $zbl))
${seqStore}
(i32.store (local.get $ls) (local.get $h))
(i64.store (i32.add (local.get $slot) (i32.const 8)) (local.get $key))${durableEntryLogIR('slot', 'off')}${storeVal}
(i32.store (i32.sub (local.get $off) (i32.const 8))
(i32.add (i32.load (i32.sub (local.get $off) (i32.const 8))) (i32.const 1)))
(br $done)))
(br $probe)))
(local.get $coll))`
}
/** Generate lookup probe function.
* wantValue=true: return slot value, missing => `undefined` (UNDEF_NAN) — a
* missing Map entry / object property reads as `undefined` in JS, never null.
* wantValue=false: return i32 0/1 existence flag.
* hasExt: emit EXTERNAL fallthrough (delegate to __ext_prop/__ext_has). */
function genLookup(name, entrySize, hashFn, eqExpr, expectedType, wantValue, hasExt) {
const rt = wantValue ? 'i64' : 'i32'
const onEmpty = wantValue
? `(return (i64.const ${UNDEF_NAN}))`
: '(return (i32.const 0))'
const onFound = wantValue
? '(return (i64.load (i32.add (local.get $slot) (i32.const 16))))'
: '(return (i32.const 1))'
const notFound = wantValue
? `(i64.const ${UNDEF_NAN})`
: '(i32.const 0)'
const tExpr = `(i32.wrap_i64 (i64.and (i64.shr_u (local.get $coll) (i64.const ${LAYOUT.TAG_SHIFT})) (i64.const ${LAYOUT.TAG_MASK})))`
const typeGuard = hasExt
? `(if (i32.ne ${tExpr} (i32.const ${expectedType})) (then (if (i32.eq ${tExpr} (i32.const ${PTR.EXTERNAL}))
(then (return ${wantValue
? '(call $__ext_prop (local.get $coll) (local.get $key))'
: '(call $__ext_has (local.get $coll) (local.get $key))'}))
(else ${onEmpty}))))`
: `(if (i32.ne ${tExpr} (i32.const ${expectedType})) (then ${onEmpty}))`
// SET/MAP/HASH all grow by forward-marking the old header (genUpsert / genUpsertGrow
// with forward=true), so a boxed pointer may be stale → resolve through the chain.
const offExpr = '(call $__ptr_offset (local.get $coll))'
return `(func $${name} (param $coll i64) (param $key i64) (result ${rt})
(local $off i32) (local $cap i32) (local $h i32) (local $end i32) (local $slot i32) (local $tries i32)
${laneLocals}
${typeGuard}
(local.set $off ${offExpr})
(local.set $cap (i32.load (i32.sub (local.get $off) (i32.const 4))))
(local.set $h (call ${hashFn} (local.get $key)))
${probeStart(entrySize)}
(block $done (loop $probe
(local.set $hw (i32.load (local.get $ls)))
(if (i32.eqz (local.get $hw)) (then ${onEmpty}))
(if (i32.eq (local.get $hw) (local.get $h))
(then
${slotFromLane(entrySize)}
(if ${eqExpr} (then ${onFound}))))
${probeNext()}
(local.set $tries (i32.add (local.get $tries) (i32.const 1)))
(br_if $done (i32.ge_s (local.get $tries) (local.get $cap)))
(br $probe)))
${notFound})`
}
/** Generate delete probe function. Backward-shift deletion: after removing an entry,
* pull back any following entry whose home slot lies outside the opened gap, so the
* "empty slot ⇒ end of probe chain" invariant holds without tombstones. Returns 1 if
* the key was present (and len decremented), 0 otherwise. Home slots are recomputed
* from the stored hash (low 32 bits), so no rehash of the key is needed during the shift. */
function genDelete(name, entrySize, hashFn, eqExpr, expectedType) {
// for-in enum cache invalidation (core.js __hash_keys_ro / object.js
// emitEnumerateObject): delete is the one key-set change the cache's
// (off, len) key can miss — a later insert restores the cached len with a
// different key set. Unconditional clear (not off-compare): the OBJECT-arm
// cache is keyed by SIDECAR off, but a durable receiver's runtime props live
// in per-object hashes under __dyn_props whose offs the cache never sees —
// a delete there must still invalidate. HASH deletes are cold; SET/MAP
// tables never feed enumeration, so only the HASH instance pays.
const enumcInval = expectedType === PTR.HASH
? `(global.set $__enumc_off (i32.const 0))
`
: ''
return `(func $${name} (param $coll i64) (param $key i64) (result i32)
(local $off i32) (local $cap i32) (local $h i32) (local $end i32) (local $slot i32) (local $tries i32)
(local $i i32) (local $j i32) (local $k i32) (local $n i32)
${laneLocals} (local $li i32) (local $lj i32)
(if (i32.ne (call $__ptr_type (local.get $coll)) (i32.const ${expectedType})) (then (return (i32.const 0))))
(local.set $off (i32.wrap_i64 (i64.and (local.get $coll) (i64.const ${LAYOUT.OFFSET_MASK}))))
(local.set $cap (i32.load (i32.sub (local.get $off) (i32.const 4))))
;; the cap load IS the forward check: -1 sentinel hops via the cold helper,
;; the live path pays zero extra — the per-probe __ptr_offset call drops
(if (i32.eq (local.get $cap) (i32.const -1))
(then
(local.set $off (call $__ptr_offset_fwd (local.get $off)))
(local.set $cap (i32.load (i32.sub (local.get $off) (i32.const 4))))))
(local.set $h (call ${hashFn} (local.get $key)))
${probeStart(entrySize)}
(block $found
(block $absent (loop $probe
(local.set $hw (i32.load (local.get $ls)))
(if (i32.eqz (local.get $hw)) (then (br $absent)))
(if (i32.eq (local.get $hw) (local.get $h))
(then
${slotFromLane(entrySize)}
(if ${eqExpr} (then (br $found)))))
${probeNext()}
(local.set $tries (i32.add (local.get $tries) (i32.const 1)))
(br_if $absent (i32.ge_s (local.get $tries) (local.get $cap)))
(br $probe)))
(return (i32.const 0)))
;; $slot holds the entry to remove ($ls its lane word). Walk forward; move back
;; any entry whose home is not cyclically within (i, j], else it would become
;; unreachable from its home. The lane word travels with each moved entry.
(local.set $i (local.get $slot))
(local.set $j (local.get $slot))
(local.set $li (local.get $ls))
(local.set $lj (local.get $ls))
(block $stop (loop $shift
(local.set $j (i32.add (local.get $j) (i32.const ${entrySize})))
(local.set $lj (i32.add (local.get $lj) (i32.const 4)))
(if (i32.ge_u (local.get $lj) (local.get $end))
(then (local.set $j (local.get $off)) (local.set $lj (local.get $lb))))
(br_if $stop (i64.eqz (i64.load (local.get $j))))
;; Empty slot ends the cluster (load < 100%). A 100%-full table has none — lookups
;; tolerate that via the $tries<cap bound, so delete must too: after $cap advances $j
;; has cycled back to the gap origin; stop and clear the final gap.
(local.set $n (i32.add (local.get $n) (i32.const 1)))
(br_if $stop (i32.ge_u (local.get $n) (local.get $cap)))
(local.set $k (i32.add (local.get $off)
(i32.mul (i32.and (i32.wrap_i64 (i64.load (local.get $j))) (i32.sub (local.get $cap) (i32.const 1))) (i32.const ${entrySize}))))
(if (i32.le_u (local.get $i) (local.get $j))
(then (br_if $shift (i32.and (i32.lt_u (local.get $i) (local.get $k)) (i32.le_u (local.get $k) (local.get $j)))))
(else (br_if $shift (i32.or (i32.lt_u (local.get $i) (local.get $k)) (i32.le_u (local.get $k) (local.get $j))))))
(memory.copy (local.get $i) (local.get $j) (i32.const ${entrySize}))
(i32.store (local.get $li) (i32.load (local.get $lj)))
(local.set $i (local.get $j))
(local.set $li (local.get $lj))
(br $shift)))
(i64.store (local.get $i) (i64.const 0))
(i64.store (i32.add (local.get $i) (i32.const 8)) (i64.const 0))
(i32.store (local.get $li) (i32.const 0))
${enumcInval}(i32.store (i32.sub (local.get $off) (i32.const 8))
(i32.sub (i32.load (i32.sub (local.get $off) (i32.const 8))) (i32.const 1)))
(i32.const 1))`
}
/** Generate growable upsert. Grows table at 75% load, rehashes, then inserts.
* strict=true: reject wrong type.
* strict=false: EXTERNAL → __ext_set, other non-HASH types → __dyn_set (global props).
* The non-strict fallback is critical for untyped variables (e.g. arrays from
* Object.create) that receive property writes — without it writes silently vanish. */
function genUpsertGrow(name, entrySize, hashFn, eqExpr, typeConst, strict = false, hasExt = false, forward = false) {
const nonHashFallback = hasExt
? `(if (i32.eq (call $__ptr_type (local.get $obj)) (i32.const ${PTR.EXTERNAL}))
(then (call $__ext_set (local.get $obj) (local.get $key) (local.get $val)) drop)
(else (call $__dyn_set (local.get $obj) (local.get $key) (local.get $val)) drop))`
: `(call $__dyn_set (local.get $obj) (local.get $key) (local.get $val)) drop`
const typeGuard = strict
? `(if (i32.ne (call $__ptr_type (local.get $obj)) (i32.const ${typeConst}))
(then (return (local.get $obj))))`
: `(if (i32.ne (call $__ptr_type (local.get $obj)) (i32.const ${typeConst}))
(then
${nonHashFallback}
(return (local.get $obj))))`
return `(func $${name} (param $obj i64) (param $key i64) (param $val i64) (result i64)
(local $off i32) (local $cap i32) (local $h i32) (local $end i32) (local $slot i32)
(local $size i32) (local $newptr i32) (local $newcap i32) (local $i i32)
(local $oldslot i32) (local $newidx i32) (local $newslot i32) (local $zb i32) (local $ztr i32)
${laneLocals} (local $zbl i32) (local $nlb i32)
${typeGuard}
(local.set $off (i32.wrap_i64 (i64.and (local.get $obj) (i64.const ${LAYOUT.OFFSET_MASK}))))
(local.set $cap (i32.load (i32.sub (local.get $off) (i32.const 4))))
;; the cap load IS the forward check: -1 sentinel hops via the cold helper,
;; the live path pays zero extra — the per-probe __ptr_offset call drops
(if (i32.eq (local.get $cap) (i32.const -1))
(then
(local.set $off (call $__ptr_offset_fwd (local.get $off)))
(local.set $cap (i32.load (i32.sub (local.get $off) (i32.const 4))))))
(local.set $size (i32.load (i32.sub (local.get $off) (i32.const 8))))
;; Grow if load factor > 75%: size * 4 >= cap * 3
(if (i32.ge_s (i32.mul (local.get $size) (i32.const 4)) (i32.mul (local.get $cap) (i32.const 3)))
(then
(local.set $newcap (i32.shl (local.get $cap) (i32.const 1)))
(local.set $newptr (call $__alloc_hdr_n (i32.const 0) (local.get $newcap) (i32.const ${entrySize + LANE})))
(local.set $nlb (i32.add (local.get $newptr) (i32.mul (local.get $newcap) (i32.const ${entrySize}))))
(local.set $i (i32.const 0))
(block $rd (loop $rl
(br_if $rd (i32.ge_s (local.get $i) (local.get $cap)))
(local.set $oldslot (i32.add (local.get $off) (i32.mul (local.get $i) (i32.const ${entrySize}))))
(if (i64.ne (i64.load (local.get $oldslot)) (i64.const 0))
(then
(local.set $h (call ${hashFn} (i64.load (i32.add (local.get $oldslot) (i32.const 8)))))
(local.set $newidx (i32.and (local.get $h) (i32.sub (local.get $newcap) (i32.const 1))))
(block $ins (loop $probe2
(local.set $newslot (i32.add (local.get $newptr) (i32.mul (local.get $newidx) (i32.const ${entrySize}))))
(br_if $ins (i64.eqz (i64.load (local.get $newslot))))
(local.set $newidx (i32.and (i32.add (local.get $newidx) (i32.const 1)) (i32.sub (local.get $newcap) (i32.const 1))))
(br $probe2)))
(i64.store (local.get $newslot) (i64.load (local.get $oldslot)))
(i64.store (i32.add (local.get $newslot) (i32.const 8)) (i64.load (i32.add (local.get $oldslot) (i32.const 8))))
(i64.store (i32.add (local.get $newslot) (i32.const 16)) (i64.load (i32.add (local.get $oldslot) (i32.const 16))))
(i32.store (i32.add (local.get $nlb) (i32.shl (local.get $newidx) (i32.const 2))) (local.get $h))
(i32.store (i32.sub (local.get $newptr) (i32.const 8))
(i32.add (i32.load (i32.sub (local.get $newptr) (i32.const 8))) (i32.const 1)))))
(local.set $i (i32.add (local.get $i) (i32.const 1)))
(br $rl)))
${forward
// Forward-mark the old header (cap=-1 sentinel at -4, new offset at -8) and
// keep the boxed pointer the caller holds: any alias resolves through
// __ptr_offset. This preserves JS reference identity for a grown dict held in
// multiple places (e.g. ctx.core.emit), which remint cannot. Log the pre-grow
// (off, size, cap) first (durableFwdLogIR — no-op unless $off predates this
// round) so `_clear` can heal a durable header instead of leaving it forwarded
// at an ephemeral target that the next round overwrites.
? `${durableFwdLogIR('off', 'newptr', 'size', 'cap')}
(i32.store (i32.sub (local.get $off) (i32.const 8)) (local.get $newptr))
(i32.store (i32.sub (local.get $off) (i32.const 4)) (i32.const -1))
(local.set $off (local.get $newptr))
(local.set $cap (local.get $newcap))`
// Remint: hand back a fresh boxed pointer. Only safe when a single owner
// (a local threaded via the return, or the global __dyn_props) is updated.
: `(local.set $off (local.get $newptr))
(local.set $cap (local.get $newcap))
(local.set $obj (i64.reinterpret_f64 (call $__mkptr (i32.const ${typeConst}) (i32.const 0) (local.get $newptr))))`}))
;; Insert/update
(local.set $h (call ${hashFn} (local.get $key)))
${probeStart(entrySize)}
;; zombie-aware LANE probe (durable-slot heal, TOMB_NAN keys) — see genUpsert.
(block $done (loop $probe
(local.set $hw (i32.load (local.get $ls)))
(if (i32.eqz (local.get $hw))
(then
(if (local.get $zb)
(then (local.set $slot (local.get $zb)) (local.set $ls (local.get $zbl)))
(else ${slotFromLane(entrySize)}))
${seqStore}
(i32.store (local.get $ls) (local.get $h))
(i64.store (i32.add (local.get $slot) (i32.const 8)) (local.get $key))${durableEntryLogIR('slot', 'off')}
(i64.store (i32.add (local.get $slot) (i32.const 16)) (local.get $val))${durableSlotLogIR('slot', 16, 'val')}
(i32.store (i32.sub (local.get $off) (i32.const 8))
(i32.add (i32.load (i32.sub (local.get $off) (i32.const 8))) (i32.const 1)))
(br $done)))
(if (i32.eq (local.get $hw) (local.get $h))
(then
${slotFromLane(entrySize)}
(if (i64.eq (i64.load (i32.add (local.get $slot) (i32.const 8))) (i64.const ${TOMB_NAN}))
(then (if (i32.eqz (local.get $zb))
(then (local.set $zb (local.get $slot)) (local.set $zbl (local.get $ls)))))
(else (if ${eqExpr}
(then
(i64.store (i32.add (local.get $slot) (i32.const 16)) (local.get $val))${durableSlotLogIR('slot', 16, 'val')}
(br $done)))))))
${probeNext()}
(local.set $ztr (i32.add (local.get $ztr) (i32.const 1)))
(if (i32.ge_s (local.get $ztr) (local.get $cap))
(then
${zombieRescan(entrySize)}
(local.set $slot (local.get $zb))
(local.set $ls (local.get $zbl))
${seqStore}
(i32.store (local.get $ls) (local.get $h))
(i64.store (i32.add (local.get $slot) (i32.const 8)) (local.get $key))${durableEntryLogIR('slot', 'off')}
(i64.store (i32.add (local.get $slot) (i32.const 16)) (local.get $val))${durableSlotLogIR('slot', 16, 'val')}
(i32.store (i32.sub (local.get $off) (i32.const 8))
(i32.add (i32.load (i32.sub (local.get $off) (i32.const 8))) (i32.const 1)))
(br $done)))
(br $probe)))
(local.get $obj))`
}
/** RMW slot upsert — genUpsertGrow's exact machinery (grow + forward-mark +
* zombie-aware probe) returning the entry's VALUE SLOT ADDRESS instead of
* storing a value: `o[k] = f(o[k])` fusion (emit-assign.js) hashes and probes
* ONCE for the read-modify-write instead of a full get + set pair. On insert
* the value seeds `undefined` (what a plain read of a missing key yields) and
* the entry-log runs, so the caller's later __slot_write is an ordinary value
* update. Sound across growth because the caller's BOX never changes: the old
* header forward-marks and the returned address points into the new table.
* Returns 0 unless the receiver is a live HASH — caller falls back to the
* generic dyn read/write pair. */
function genSlotUpsert(name, entrySize, hashFn, eqExpr) {
return `(func $${name} (param $obj i64) (param $key i64) (result i32)
(local $off i32) (local $cap i32) (local $h i32) (local $end i32) (local $slot i32)
(local $size i32) (local $newptr i32) (local $newcap i32) (local $i i32)
(local $oldslot i32) (local $newidx i32) (local $newslot i32) (local $zb i32) (local $ztr i32)
(local $kaux i32) (local $koff i32)
${laneLocals} (local $zbl i32) (local $nlb i32)
(if (i32.ne (call $__ptr_type (local.get $obj)) (i32.const ${PTR.HASH}))
(then (return (i32.const 0))))
(local.set $off (i32.wrap_i64 (i64.and (local.get $obj) (i64.const ${LAYOUT.OFFSET_MASK}))))
(local.set $cap (i32.load (i32.sub (local.get $off) (i32.const 4))))
;; the cap load IS the forward check: -1 sentinel hops via the cold helper,
;; the live path pays zero extra — the per-probe __ptr_offset call drops
(if (i32.eq (local.get $cap) (i32.const -1))
(then
(local.set $off (call $__ptr_offset_fwd (local.get $off)))
(local.set $cap (i32.load (i32.sub (local.get $off) (i32.const 4))))))
(local.set $size (i32.load (i32.sub (local.get $off) (i32.const 8))))
(if (i32.ge_s (i32.mul (local.get $size) (i32.const 4)) (i32.mul (local.get $cap) (i32.const 3)))
(then
(local.set $newcap (i32.shl (local.get $cap) (i32.const 1)))
(local.set $newptr (call $__alloc_hdr_n (i32.const 0) (local.get $newcap) (i32.const ${entrySize + LANE})))
(local.set $nlb (i32.add (local.get $newptr) (i32.mul (local.get $newcap) (i32.const ${entrySize}))))
(local.set $i (i32.const 0))
(block $rd (loop $rl
(br_if $rd (i32.ge_s (local.get $i) (local.get $cap)))
(local.set $oldslot (i32.add (local.get $off) (i32.mul (local.get $i) (i32.const ${entrySize}))))
(if (i64.ne (i64.load (local.get $oldslot)) (i64.const 0))
(then
(local.set $h (call ${hashFn} (i64.load (i32.add (local.get $oldslot) (i32.const 8)))))
(local.set $newidx (i32.and (local.get $h) (i32.sub (local.get $newcap) (i32.const 1))))
(block $ins (loop $probe2
(local.set $newslot (i32.add (local.get $newptr) (i32.mul (local.get $newidx) (i32.const ${entrySize}))))
(br_if $ins (i64.eqz (i64.load (local.get $newslot))))
(local.set $newidx (i32.and (i32.add (local.get $newidx) (i32.const 1)) (i32.sub (local.get $newcap) (i32.const 1))))
(br $probe2)))
(i64.store (local.get $newslot) (i64.load (local.get $oldslot)))
(i64.store (i32.add (local.get $newslot) (i32.const 8)) (i64.load (i32.add (local.get $oldslot) (i32.const 8))))
(i64.store (i32.add (local.get $newslot) (i32.const 16)) (i64.load (i32.add (local.get $oldslot) (i32.const 16))))
(i32.store (i32.add (local.get $nlb) (i32.shl (local.get $newidx) (i32.const 2))) (local.get $h))
(i32.store (i32.sub (local.get $newptr) (i32.const 8))
(i32.add (i32.load (i32.sub (local.get $newptr) (i32.const 8))) (i32.const 1)))))
(local.set $i (i32.add (local.get $i) (i32.const 1)))
(br $rl)))
${durableFwdLogIR('off', 'newptr', 'size', 'cap')}
(i32.store (i32.sub (local.get $off) (i32.const 8)) (local.get $newptr))
(i32.store (i32.sub (local.get $off) (i32.const 4)) (i32.const -1))
(local.set $off (local.get $newptr))
(local.set $cap (local.get $newcap))))
${hashFn === '$__str_hash' ? `;; tiered $__str_hash: the two FAST arms inline — SSO arithmetic mix and
;; the heap lazy-hash-cell load, one of which the dictionary-count hot path
;; pays per probe. Cold shapes (interned statics, uncached walk — and the
;; one-in-4G SSO mix that hashes to 0) call the helper, which recomputes
;; identically. Gates mirror $__str_hash's own exactly.
(local.set $kaux (i32.wrap_i64 (i64.and (i64.shr_u (local.get $key) (i64.const ${LAYOUT.AUX_SHIFT})) (i64.const ${LAYOUT.AUX_MASK}))))
(local.set $h (i32.const 0))
(if (i32.eq (i32.wrap_i64 (i64.and (i64.shr_u (local.get $key) (i64.const ${LAYOUT.TAG_SHIFT})) (i64.const ${LAYOUT.TAG_MASK}))) (i32.const ${PTR.STRING}))
(then
(local.set $koff (i32.wrap_i64 (i64.and (local.get $key) (i64.const ${LAYOUT.OFFSET_MASK}))))
(if (i32.shr_u (local.get $kaux) (i32.const 14))
(then
(local.set $h (i32.mul
(i32.xor (local.get $koff) (i32.mul (i32.xor (i32.and (local.get $kaux) (i32.const 0x1FFF)) (i32.const 0x9E3779B9)) (i32.const 0x85EBCA6B)))
(i32.const 0xC2B2AE35)))
(local.set $h (i32.xor (local.get $h) (i32.shr_u (local.get $h) (i32.const 15))))
;; $__str_hash's post-mix clamp, replicated EXACTLY (i32.le_s — it
;; shifts every NEGATIVE-signed hash by 2, not just 0/1): the
;; tiered value must be bit-equal to the helper's return and to
;; the lazy hash cells (they cache post-clamp values).
(if (i32.le_s (local.get $h) (i32.const 1))
(then (local.set $h (i32.add (local.get $h) (i32.const 2))))))
(else
(if (i32.and (i32.ge_u (local.get $koff) (i32.const 8))
(i32.eq (i32.and (local.get $kaux) (i32.const ${LAYOUT.SLICE_BIT | STR_HCACHE_BIT})) (i32.const ${STR_HCACHE_BIT})))
(then (local.set $h (i32.load (i32.sub (local.get $koff) (i32.const 8))))))))))
(if (i32.eqz (local.get $h)) (then (local.set $h (call ${hashFn} (local.get $key)))))`
: `(local.set $h (call ${hashFn} (local.get $key)))`}
${probeStart(entrySize)}
(block $done (loop $probe
(local.set $hw (i32.load (local.get $ls)))
(if (i32.eqz (local.get $hw))
(then
(if (local.get $zb)
(then (local.set $slot (local.get $zb)) (local.set $ls (local.get $zbl)))
(else ${slotFromLane(entrySize)}))
${seqStore}
(i32.store (local.get $ls) (local.get $h))
(i64.store (i32.add (local.get $slot) (i32.const 8)) (local.get $key))${durableEntryLogIR('slot', 'off')}
(i64.store (i32.add (local.get $slot) (i32.const 16)) (i64.const ${UNDEF_NAN}))
(i32.store (i32.sub (local.get $off) (i32.const 8))
(i32.add (i32.load (i32.sub (local.get $off) (i32.const 8))) (i32.const 1)))
(br $done)))
(if (i32.eq (local.get $hw) (local.get $h))
(then
${slotFromLane(entrySize)}
(if (i64.eq (i64.load (i32.add (local.get $slot) (i32.const 8))) (i64.const ${TOMB_NAN}))
(then (if (i32.eqz (local.get $zb))
(then (local.set $zb (local.get $slot)) (local.set $zbl (local.get $ls)))))
(else (if ${eqExpr} (then (br $done)))))))
${probeNext()}
(local.set $ztr (i32.add (local.get $ztr) (i32.const 1)))
(if (i32.ge_s (local.get $ztr) (local.get $cap))
(then
${zombieRescan(entrySize)}
(local.set $slot (local.get $zb))
(local.set $ls (local.get $zbl))
${seqStore}
(i32.store (local.get $ls) (local.get $h))
(i64.store (i32.add (local.get $slot) (i32.const 8)) (local.get $key))${durableEntryLogIR('slot', 'off')}
(i64.store (i32.add (local.get $slot) (i32.const 16)) (i64.const ${UNDEF_NAN}))
(i32.store (i32.sub (local.get $off) (i32.const 8))
(i32.add (i32.load (i32.sub (local.get $off) (i32.const 8))) (i32.const 1)))
(br $done)))
(br $probe)))
(i32.add (local.get $slot) (i32.const 16)))`
}
// Fresh non-escaping HASH upsert. The compiler proves this dictionary is used
// only by computed get/RMW sites: no delete (therefore no tombstones), no
// enumeration (therefore no insertion-order sequence), and no escape across a
// heap reset (therefore no durable forwarding/slot logs). Keep the standard
// HASH layout so ordinary strict lookups remain compatible, but make the hot
// upsert the textbook open-addressing loop emitted by C.
function genEphemeralSlotUpsert(name, entrySize) {
return `(func $${name} (param $obj i64) (param $key i64) (result i32)
(local $off i32) (local $cap i32) (local $size i32) (local $h i32) (local $kaux i32) (local $koff i32)
(local $i i32) (local $idx i32) (local $slot i32) (local $hw i32)
(local $lb i32) (local $ls i32) (local $end i32)
(local $oldlb i32) (local $oldslot i32)
(local $newptr i32) (local $newcap i32) (local $newlb i32) (local $newslot i32)
(local.set $off (i32.wrap_i64 (i64.and (local.get $obj) (i64.const ${LAYOUT.OFFSET_MASK}))))
(local.set $cap (i32.load (i32.sub (local.get $off) (i32.const 4))))
(if (i32.eq (local.get $cap) (i32.const -1))
(then
(local.set $off (call $__ptr_offset_fwd (local.get $off)))
(local.set $cap (i32.load (i32.sub (local.get $off) (i32.const 4))))))
(local.set $size (i32.load (i32.sub (local.get $off) (i32.const 8))))
(if (i32.ge_s (i32.shl (local.get $size) (i32.const 2)) (i32.mul (local.get $cap) (i32.const 3)))
(then
(local.set $newcap (i32.shl (local.get $cap) (i32.const 1)))
(local.set $newptr (call $__alloc_hash_eph (i32.const 0) (local.get $newcap)))
(local.set $oldlb (i32.add (local.get $off) (i32.mul (local.get $cap) (i32.const ${entrySize}))))
(local.set $newlb (i32.add (local.get $newptr) (i32.mul (local.get $newcap) (i32.const ${entrySize}))))
(local.set $i (i32.const 0))
(block $rd (loop $rl
(br_if $rd (i32.ge_s (local.get $i) (local.get $cap)))
(local.set $h (i32.load (i32.add (local.get $oldlb) (i32.shl (local.get $i) (i32.const 2)))))
(if (local.get $h)
(then
(local.set $oldslot (i32.add (local.get $off) (i32.mul (local.get $i) (i32.const ${entrySize}))))
(local.set $idx (i32.and (local.get $h) (i32.sub (local.get $newcap) (i32.const 1))))
(block $ins (loop $pl2
(local.set $ls (i32.add (local.get $newlb) (i32.shl (local.get $idx) (i32.const 2))))
(br_if $ins (i32.eqz (i32.load (local.get $ls))))
(local.set $idx (i32.and (i32.add (local.get $idx) (i32.const 1)) (i32.sub (local.get $newcap) (i32.const 1))))
(br $pl2)))
(local.set $newslot (i32.add (local.get $newptr) (i32.mul (local.get $idx) (i32.const ${entrySize}))))
(i64.store (local.get $newslot) (i64.load (local.get $oldslot)))
(i64.store offset=8 (local.get $newslot) (i64.load offset=8 (local.get $oldslot)))
(i64.store offset=16 (local.get $newslot) (i64.load offset=16 (local.get $oldslot)))
(i32.store (local.get $ls) (local.get $h))))
(local.set $i (i32.add (local.get $i) (i32.const 1)))
(br $rl)))
(i32.store (i32.sub (local.get $newptr) (i32.const 8)) (local.get $size))
(i32.store (i32.sub (local.get $off) (i32.const 8)) (local.get $newptr))
(i32.store (i32.sub (local.get $off) (i32.const 4)) (i32.const -1))
(local.set $off (local.get $newptr))
(local.set $cap (local.get $newcap))))
;; Cached/tiny string hash fast paths inline (same contract as __str_hash).
(local.set $kaux (i32.wrap_i64 (i64.and (i64.shr_u (local.get $key) (i64.const ${LAYOUT.AUX_SHIFT})) (i64.const ${LAYOUT.AUX_MASK}))))
(local.set $koff (i32.wrap_i64 (i64.and (local.get $key) (i64.const ${LAYOUT.OFFSET_MASK}))))
(local.set $h (i32.const 0))
(if (i32.eq (i32.wrap_i64 (i64.and (i64.shr_u (local.get $key) (i64.const ${LAYOUT.TAG_SHIFT})) (i64.const ${LAYOUT.TAG_MASK}))) (i32.const ${PTR.STRING}))
(then
(if (i32.shr_u (local.get $kaux) (i32.const 14))
(then
(local.set $h (i32.mul
(i32.xor (local.get $koff) (i32.mul (i32.xor (i32.and (local.get $kaux) (i32.const 0x1FFF)) (i32.const 0x9E3779B9)) (i32.const 0x85EBCA6B)))
(i32.const 0xC2B2AE35)))
(local.set $h (i32.xor (local.get $h) (i32.shr_u (local.get $h) (i32.const 15))))
(if (i32.le_s (local.get $h) (i32.const 1)) (then (local.set $h (i32.add (local.get $h) (i32.const 2))))))
(else
(if (i32.and (i32.ge_u (local.get $koff) (i32.const 8))
(i32.eq (i32.and (local.get $kaux) (i32.const ${LAYOUT.SLICE_BIT | STR_HCACHE_BIT})) (i32.const ${STR_HCACHE_BIT})))
(then (local.set $h (i32.load (i32.sub (local.get $koff) (i32.const 8))))))))))
(if (i32.eqz (local.get $h)) (then (local.set $h (call $__str_hash (local.get $key)))))
(local.set $lb (i32.add (local.get $off) (i32.mul (local.get $cap) (i32.const ${entrySize}))))
(local.set $end (i32.add (local.get $lb) (i32.shl (local.get $cap) (i32.const 2))))
(local.set $idx (i32.and (local.get $h) (i32.sub (local.get $cap) (i32.const 1))))
(local.set $ls (i32.add (local.get $lb) (i32.shl (local.get $idx) (i32.const 2))))
(block $done (loop $probe
(local.set $hw (i32.load (local.get $ls)))
(if (i32.eqz (local.get $hw))
(then
(local.set $slot (i32.add (local.get $off) (i32.mul (local.get $idx) (i32.const ${entrySize}))))
(i64.store (local.get $slot) (i64.extend_i32_u (local.get $h)))
(i64.store offset=8 (local.get $slot) (local.get $key))
(i64.store offset=16 (local.get $slot) (i64.const ${UNDEF_NAN}))
(i32.store (local.get $ls) (local.get $h))
(i32.store (i32.sub (local.get $off) (i32.const 8)) (i32.add (local.get $size) (i32.const 1)))
(br $done)))
(if (i32.eq (local.get $hw) (local.get $h))
(then
(local.set $slot (i32.add (local.get $off) (i32.mul (local.get $idx) (i32.const ${entrySize}))))
(br_if $done
(if (result i32)
(i64.eq (i64.load offset=8 (local.get $slot)) (local.get $key))
(then (i32.const 1))
(else (call $__str_eq (i64.load offset=8 (local.get $slot)) (local.get $key)))))))
(local.set $idx (i32.and (i32.add (local.get $idx) (i32.const 1)) (i32.sub (local.get $cap) (i32.const 1))))
(local.set $ls (i32.add (local.get $ls) (i32.const 4)))
(if (i32.ge_u (local.get $ls) (local.get $end)) (then (local.set $ls (local.get $lb))))
(br $probe)))
(i32.add (local.get $slot) (i32.const 16)))`
}
// Capacity-planned sibling: analysis proved all inserted keys originate from
// one finite domain and allocated ≥4× that domain, so growth/forwarding and the
// size counter are unreachable. capHint folds the header load for a fixed-size
// domain; zero retains the dynamic-domain form.
function genEphemeralFixedSlot(name, entrySize) {
return `(func $${name} (param $obj i64) (param $key i64) (param $capHint i32) (result i32)
(local $off i32) (local $cap i32) (local $h i32) (local $kaux i32) (local $koff i32)
(local $idx i32) (local $slot i32) (local $hw i32) (local $lb i32) (local $ls i32) (local $end i32)
(local.set $off (i32.wrap_i64 (i64.and (local.get $obj) (i64.const ${LAYOUT.OFFSET_MASK}))))
(local.set $cap (local.get $capHint))
(if (i32.eqz (local.get $cap))
(then (local.set $cap (i32.load (i32.sub (local.get $off) (i32.const 4))))))
(local.set $kaux (i32.wrap_i64 (i64.and (i64.shr_u (local.get $key) (i64.const ${LAYOUT.AUX_SHIFT})) (i64.const ${LAYOUT.AUX_MASK}))))
(local.set $koff (i32.wrap_i64 (i64.and (local.get $key) (i64.const ${LAYOUT.OFFSET_MASK}))))
(local.set $h (i32.const 0))
(if (i32.eq (i32.wrap_i64 (i64.and (i64.shr_u (local.get $key) (i64.const ${LAYOUT.TAG_SHIFT})) (i64.const ${LAYOUT.TAG_MASK}))) (i32.const ${PTR.STRING}))
(then
(if (i32.shr_u (local.get $kaux) (i32.const 14))
(then
(local.set $h (i32.mul
(i32.xor (local.get $koff) (i32.mul (i32.xor (i32.and (local.get $kaux) (i32.const 0x1FFF)) (i32.const 0x9E3779B9)) (i32.const 0x85EBCA6B)))
(i32.const 0xC2B2AE35)))
(local.set $h (i32.xor (local.get $h) (i32.shr_u (local.get $h) (i32.const 15))))
(if (i32.le_s (local.get $h) (i32.const 1)) (then (local.set $h (i32.add (local.get $h) (i32.const 2))))))
(else
(if (i32.and (i32.ge_u (local.get $koff) (i32.const 8))
(i32.eq (i32.and (local.get $kaux) (i32.const ${LAYOUT.SLICE_BIT | STR_HCACHE_BIT})) (i32.const ${STR_HCACHE_BIT})))
(then (local.set $h (i32.load (i32.sub (local.get $koff) (i32.const 8))))))))))
(if (i32.eqz (local.get $h)) (then (local.set $h (call $__str_hash (local.get $key)))))
(local.set $lb (i32.add (local.get $off) (i32.mul (local.get $cap) (i32.const ${entrySize}))))
(local.set $end (i32.add (local.get $lb) (i32.shl (local.get $cap) (i32.const 2))))
(local.set $idx (i32.and (local.get $h) (i32.sub (local.get $cap) (i32.const 1))))
(local.set $ls (i32.add (local.get $lb) (i32.shl (local.get $idx) (i32.const 2))))
(block $done (loop $probe
(local.set $hw (i32.load (local.get $ls)))
(if (i32.eqz (local.get $hw))
(then
(local.set $slot (i32.add (local.get $off) (i32.mul (local.get $idx) (i32.const ${entrySize}))))
(i64.store (local.get $slot) (i64.extend_i32_u (local.get $h)))
(i64.store offset=8 (local.get $slot) (local.get $key))
(i64.store offset=16 (local.get $slot) (i64.const ${UNDEF_NAN}))
(i32.store (local.get $ls) (local.get $h))
(br $done)))
(if (i32.eq (local.get $hw) (local.get $h))
(then
(local.set $slot (i32.add (local.get $off) (i32.mul (local.get $idx) (i32.const ${entrySize}))))
(br_if $done
(if (result i32) (i64.eq (i64.load offset=8 (local.get $slot)) (local.get $key))
(then (i32.const 1))
(else (call $__str_eq (i64.load offset=8 (local.get $slot)) (local.get $key)))))))
(local.set $idx (i32.and (i32.add (local.get $idx) (i32.const 1)) (i32.sub (local.get $cap) (i32.const 1))))
(local.set $ls (i32.add (local.get $ls) (i32.const 4)))
(if (i32.ge_u (local.get $ls) (local.get $end)) (then (local.set $ls (local.get $lb))))
(br $probe)))
(i32.add (local.get $slot) (i32.const 16)))`
}
function genLookupStrict(name, entrySize, hashFn, eqExpr, expectedType, missing = UNDEF_NAN) {
return `(func $${name} (param $coll i64) (param $key i64) (result i64)
(local $off i32) (local $cap i32) (local $h i32) (local $end i32) (local $slot i32) (local $tries i32)
${laneLocals}
(if (i32.ne
(i32.wrap_i64 (i64.and (i64.shr_u (local.get $coll) (i64.const ${LAYOUT.TAG_SHIFT})) (i64.const ${LAYOUT.TAG_MASK})))
(i32.const ${expectedType}))
(then (return (i64.const ${missing}))))
(local.set $off (i32.wrap_i64 (i64.and (local.get $coll) (i64.const ${LAYOUT.OFFSET_MASK}))))
(local.set $cap (i32.load (i32.sub (local.get $off) (i32.const 4))))
;; the cap load IS the forward check: -1 sentinel hops via the cold helper,
;; the live path pays zero extra — the per-probe __ptr_offset call drops
(if (i32.eq (local.get $cap) (i32.const -1))
(then
(local.set $off (call $__ptr_offset_fwd (local.get $off)))
(local.set $cap (i32.load (i32.sub (local.get $off) (i32.const 4))))))
(local.set $h (call ${hashFn} (local.get $key)))
${probeStart(entrySize)}
(block $done (loop $probe
(local.set $hw (i32.load (local.get $ls)))
(if (i32.eqz (local.get $hw))
(then (return (i64.const ${missing}))))
(if (i32.eq (local.get $hw) (local.get $h))
(then
${slotFromLane(entrySize)}
(if ${eqExpr}
(then (return (i64.load (i32.add (local.get $slot) (i32.const 16))))))))
${probeNext()}
(local.set $tries (i32.add (local.get $tries) (i32.const 1)))
(br_if $done (i32.ge_s (local.get $tries) (local.get $cap)))
(br $probe)))
(i64.const ${missing}))`
}
// wantValue=true (default): return the slot value, missing → `missing` (i64). wantValue=false:
// return an i32 0/1 existence flag (for `.has`). Mirrors genLookup's two-mode shape, prehashed.
function genLookupStrictPrehashed(name, entrySize, eqExpr, expectedType, missing = UNDEF_NAN, hasExt = false, wantValue = true) {
const rt = wantValue ? 'i64' : 'i32'
const onEmpty = wantValue ? `(return (i64.const ${missing}))` : '(return (i32.const 0))'
const onFound = wantValue ? '(return (i64.load (i32.add (local.get $slot) (i32.const 16))))' : '(return (i32.const 1))'
const notFound = wantValue ? `(i64.const ${missing})` : '(i32.const 0)'