1use super::*;
2
3#[derive(Clone, Copy)]
4struct LocalEvacuatedSlot {
5 target: AllocSpace,
6 compacted_pos: u32,
7}
8
9struct LocalTailEntry<T: ArenaTypes> {
10 value: NanValue,
11 entry: ArenaEntry<T>,
12 slot: LocalEvacuatedSlot,
13}
14
15enum LocalTailStep<T: ArenaTypes> {
16 Done(NanValue),
17 Taken(LocalTailEntry<T>),
18}
19
20#[derive(Clone, Copy)]
21enum PromoteRewriteSlot {
22 InPlace {
23 space: HeapSpace,
24 raw_index: usize,
25 },
26 Promoted {
27 target: AllocSpace,
28 raw_index: usize,
29 },
30}
31
32struct PromoteTailEntry<T: ArenaTypes> {
33 value: NanValue,
34 entry: ArenaEntry<T>,
35 slot: PromoteRewriteSlot,
36}
37
38enum PromoteTailStep<T: ArenaTypes> {
39 Done(NanValue),
40 Taken(PromoteTailEntry<T>),
41}
42
43impl<T: ArenaTypes> Arena<T> {
44 pub fn truncate_to(&mut self, mark: u32) {
45 self.young_entries.truncate(mark as usize);
46 }
47
48 pub fn collect_young_from_roots(&mut self, mark: u32, roots: &mut [NanValue]) {
49 if self.young_entries.len() <= mark as usize {
50 return;
51 }
52
53 let mut relocated =
54 Self::take_u32_scratch(&mut self.scratch_young, self.young_entries.len());
55 let mut compacted = Vec::with_capacity(self.young_entries.len() - mark as usize);
56
57 for root in roots {
58 *root = self.relocate_young_root(*root, mark, &mut relocated, &mut compacted);
59 }
60
61 self.young_entries.truncate(mark as usize);
62 self.young_entries.extend(compacted);
63 Self::recycle_u32_scratch(&mut self.scratch_young, relocated);
64 }
65
66 pub fn truncate_yard_to(&mut self, mark: u32) {
67 self.yard_entries.truncate(mark as usize);
68 }
69
70 pub fn truncate_handoff_to(&mut self, mark: u32) {
71 self.handoff_entries.truncate(mark as usize);
72 }
73
74 pub fn evacuate_frame_to_yard(
75 &mut self,
76 young_mark: u32,
77 yard_mark: u32,
78 handoff_mark: u32,
79 roots: &mut [NanValue],
80 ) -> (bool, bool) {
81 self.evacuate_frame_locals(young_mark, yard_mark, handoff_mark, roots, AllocSpace::Yard)
82 }
83
84 pub fn evacuate_frame_to_handoff(
85 &mut self,
86 young_mark: u32,
87 yard_mark: u32,
88 handoff_mark: u32,
89 roots: &mut [NanValue],
90 ) -> (bool, bool) {
91 self.evacuate_frame_locals(
92 young_mark,
93 yard_mark,
94 handoff_mark,
95 roots,
96 AllocSpace::Handoff,
97 )
98 }
99
100 fn evacuate_frame_locals(
101 &mut self,
102 young_mark: u32,
103 yard_mark: u32,
104 handoff_mark: u32,
105 roots: &mut [NanValue],
106 young_target: AllocSpace,
107 ) -> (bool, bool) {
108 let mut relocated_young = Self::take_u32_scratch(
109 &mut self.scratch_young,
110 self.young_entries.len().saturating_sub(young_mark as usize),
111 );
112 let mut relocated_yard = Self::take_u32_scratch(
113 &mut self.scratch_yard,
114 self.yard_entries.len().saturating_sub(yard_mark as usize),
115 );
116 let mut relocated_handoff = Self::take_u32_scratch(
117 &mut self.scratch_handoff,
118 self.handoff_entries
119 .len()
120 .saturating_sub(handoff_mark as usize),
121 );
122 let mut compacted_yard =
123 Vec::with_capacity(self.yard_entries.len().saturating_sub(yard_mark as usize));
124 let mut compacted_handoff = Vec::with_capacity(
125 self.handoff_entries
126 .len()
127 .saturating_sub(handoff_mark as usize),
128 );
129
130 for root in roots {
131 *root = self.evacuate_local_root(
132 *root,
133 young_mark,
134 yard_mark,
135 handoff_mark,
136 young_target,
137 &mut relocated_young,
138 &mut relocated_yard,
139 &mut relocated_handoff,
140 &mut compacted_yard,
141 &mut compacted_handoff,
142 );
143 }
144
145 self.young_entries.truncate(young_mark as usize);
146 self.yard_entries.truncate(yard_mark as usize);
147 self.yard_entries.extend(compacted_yard);
148 self.handoff_entries.truncate(handoff_mark as usize);
149 self.handoff_entries.extend(compacted_handoff);
150 self.note_peak_usage();
151 Self::recycle_u32_scratch(&mut self.scratch_young, relocated_young);
152 Self::recycle_u32_scratch(&mut self.scratch_yard, relocated_yard);
153 Self::recycle_u32_scratch(&mut self.scratch_handoff, relocated_handoff);
154
155 (
156 self.yard_entries.len() > yard_mark as usize,
157 self.handoff_entries.len() > handoff_mark as usize,
158 )
159 }
160
161 fn allocate_local_target_slot(
162 target: AllocSpace,
163 yard_mark: u32,
164 handoff_mark: u32,
165 compacted_yard: &mut Vec<ArenaEntry<T>>,
166 compacted_handoff: &mut Vec<ArenaEntry<T>>,
167 ) -> (u32, u32) {
168 match target {
169 AllocSpace::Yard => {
170 let pos = compacted_yard.len() as u32;
171 let idx = Self::encode_yard_index(yard_mark + pos);
172 compacted_yard.push(ArenaEntry::Int(0));
173 (idx, pos)
174 }
175 AllocSpace::Handoff => {
176 let pos = compacted_handoff.len() as u32;
177 let idx = Self::encode_handoff_index(handoff_mark + pos);
178 compacted_handoff.push(ArenaEntry::Int(0));
179 (idx, pos)
180 }
181 AllocSpace::Young => unreachable!("local evacuation target must be yard or handoff"),
182 }
183 }
184
185 fn store_local_target_entry(
186 target: AllocSpace,
187 compacted_pos: u32,
188 entry: ArenaEntry<T>,
189 compacted_yard: &mut [ArenaEntry<T>],
190 compacted_handoff: &mut [ArenaEntry<T>],
191 ) {
192 match target {
193 AllocSpace::Yard => compacted_yard[compacted_pos as usize] = entry,
194 AllocSpace::Handoff => compacted_handoff[compacted_pos as usize] = entry,
195 AllocSpace::Young => unreachable!(),
196 }
197 }
198
199 fn store_local_evacuated_slot(
200 slot: LocalEvacuatedSlot,
201 entry: ArenaEntry<T>,
202 compacted_yard: &mut [ArenaEntry<T>],
203 compacted_handoff: &mut [ArenaEntry<T>],
204 ) {
205 Self::store_local_target_entry(
206 slot.target,
207 slot.compacted_pos,
208 entry,
209 compacted_yard,
210 compacted_handoff,
211 );
212 }
213
214 #[inline(always)]
215 fn rewrite_entry_with<F>(&mut self, entry: ArenaEntry<T>, rewrite: &mut F) -> ArenaEntry<T>
216 where
217 F: FnMut(&mut Arena<T>, NanValue) -> NanValue,
218 {
219 match entry {
220 ArenaEntry::Int(i) => ArenaEntry::Int(i),
221 ArenaEntry::BigInt(b) => ArenaEntry::BigInt(b),
222 ArenaEntry::String(s) => ArenaEntry::String(s),
223 ArenaEntry::Builtin(name) => ArenaEntry::Builtin(name),
224 ArenaEntry::Fn(f) => ArenaEntry::Fn(f),
225 ArenaEntry::Boxed(inner) => ArenaEntry::Boxed(rewrite(self, inner)),
226 ArenaEntry::List(list) => ArenaEntry::List(self.rewrite_list_with(list, rewrite)),
227 ArenaEntry::Tuple(mut items) => {
228 for value in &mut items {
229 *value = rewrite(self, *value);
230 }
231 ArenaEntry::Tuple(items)
232 }
233 ArenaEntry::Vector(mut items) => {
234 for value in &mut items {
235 *value = rewrite(self, *value);
236 }
237 ArenaEntry::Vector(items)
238 }
239 ArenaEntry::Map(mut map) => {
240 map.rewrite_values_mut(|pair| {
241 pair.0 = rewrite(self, pair.0);
242 pair.1 = rewrite(self, pair.1);
243 });
244 ArenaEntry::Map(map)
245 }
246 ArenaEntry::Record {
247 type_id,
248 mut fields,
249 } => {
250 for value in &mut fields {
251 *value = rewrite(self, *value);
252 }
253 ArenaEntry::Record { type_id, fields }
254 }
255 ArenaEntry::Variant {
256 type_id,
257 variant_id,
258 mut fields,
259 } => {
260 for value in &mut fields {
261 *value = rewrite(self, *value);
262 }
263 ArenaEntry::Variant {
264 type_id,
265 variant_id,
266 fields,
267 }
268 }
269 ArenaEntry::Namespace { name, mut members } => {
270 for (_, value) in &mut members {
271 *value = rewrite(self, *value);
272 }
273 ArenaEntry::Namespace { name, members }
274 }
275 }
276 }
277
278 #[inline(always)]
279 fn rewrite_list_with<F>(&mut self, list: ArenaList, rewrite: &mut F) -> ArenaList
280 where
281 F: FnMut(&mut Arena<T>, NanValue) -> NanValue,
282 {
283 match list {
284 ArenaList::Flat { items, start } => ArenaList::Flat {
285 items: Rc::new(
286 items[start..]
287 .iter()
288 .map(|value| rewrite(self, *value))
289 .collect(),
290 ),
291 start: 0,
292 },
293 ArenaList::Prepend { head, tail, len } => ArenaList::Prepend {
294 head: rewrite(self, head),
295 tail: rewrite(self, tail),
296 len,
297 },
298 ArenaList::Concat { left, right, len } => ArenaList::Concat {
299 left: rewrite(self, left),
300 right: rewrite(self, right),
301 len,
302 },
303 ArenaList::Segments {
304 current,
305 rest,
306 start,
307 len,
308 } => ArenaList::Segments {
309 current: rewrite(self, current),
310 rest: Rc::new(
311 rest[start..]
312 .iter()
313 .map(|value| rewrite(self, *value))
314 .collect(),
315 ),
316 start: 0,
317 len,
318 },
319 }
320 }
321
322 pub fn flatten_deep_list(&mut self, value: NanValue) -> NanValue {
324 const FLATTEN_THRESHOLD: usize = 64;
325
326 if !value.is_list() || value.is_empty_list_immediate() {
327 return value;
328 }
329 let len = self.list_len_value(value);
330 if len <= FLATTEN_THRESHOLD {
331 return value;
332 }
333 let elements = self.list_to_vec_value(value);
334 let flat = ArenaList::Flat {
335 items: Rc::new(elements),
336 start: 0,
337 };
338 let index = self.push(ArenaEntry::List(flat));
339 NanValue::new_list(index)
340 }
341
342 #[allow(clippy::too_many_arguments)]
343 fn evacuate_local_root(
344 &mut self,
345 value: NanValue,
346 young_mark: u32,
347 yard_mark: u32,
348 handoff_mark: u32,
349 young_target: AllocSpace,
350 relocated_young: &mut [u32],
351 relocated_yard: &mut [u32],
352 relocated_handoff: &mut [u32],
353 compacted_yard: &mut Vec<ArenaEntry<T>>,
354 compacted_handoff: &mut Vec<ArenaEntry<T>>,
355 ) -> NanValue {
356 let Some(index) = value.heap_index() else {
357 return value;
358 };
359 let (space, _) = Self::decode_index(index);
360 match space {
361 HeapSpace::Young if self.is_young_index_in_region(index, young_mark) => self
362 .evacuate_young_value(
363 value,
364 young_mark,
365 yard_mark,
366 handoff_mark,
367 young_target,
368 relocated_young,
369 relocated_yard,
370 relocated_handoff,
371 compacted_yard,
372 compacted_handoff,
373 ),
374 HeapSpace::Yard if self.is_yard_index_in_region(index, yard_mark) => self
375 .evacuate_yard_value(
376 value,
377 young_mark,
378 yard_mark,
379 handoff_mark,
380 young_target,
381 relocated_young,
382 relocated_yard,
383 relocated_handoff,
384 compacted_yard,
385 compacted_handoff,
386 ),
387 HeapSpace::Handoff if self.is_handoff_index_in_region(index, handoff_mark) => self
388 .evacuate_handoff_value(
389 value,
390 young_mark,
391 yard_mark,
392 handoff_mark,
393 young_target,
394 relocated_young,
395 relocated_yard,
396 relocated_handoff,
397 compacted_yard,
398 compacted_handoff,
399 ),
400 _ => value,
401 }
402 }
403
404 #[allow(clippy::too_many_arguments)]
405 fn evacuate_young_value(
406 &mut self,
407 value: NanValue,
408 young_mark: u32,
409 yard_mark: u32,
410 handoff_mark: u32,
411 young_target: AllocSpace,
412 relocated_young: &mut [u32],
413 relocated_yard: &mut [u32],
414 relocated_handoff: &mut [u32],
415 compacted_yard: &mut Vec<ArenaEntry<T>>,
416 compacted_handoff: &mut Vec<ArenaEntry<T>>,
417 ) -> NanValue {
418 let index = value.heap_index().expect("young value must be heap-backed");
419 let (_, raw_index) = Self::decode_index(index);
420 let relocation_slot = (raw_index - young_mark) as usize;
421 let relocated_index = relocated_young[relocation_slot];
422 if relocated_index != u32::MAX {
423 return value.with_heap_index(relocated_index);
424 }
425
426 let (new_index, compacted_pos) = Self::allocate_local_target_slot(
427 young_target,
428 yard_mark,
429 handoff_mark,
430 compacted_yard,
431 compacted_handoff,
432 );
433 relocated_young[relocation_slot] = new_index;
434
435 let entry = core::mem::replace(
436 &mut self.young_entries[raw_index as usize],
437 ArenaEntry::Int(0),
438 );
439 let new_entry = self.evacuate_local_entry(
440 entry,
441 young_mark,
442 yard_mark,
443 handoff_mark,
444 young_target,
445 relocated_young,
446 relocated_yard,
447 relocated_handoff,
448 compacted_yard,
449 compacted_handoff,
450 );
451 Self::store_local_target_entry(
452 young_target,
453 compacted_pos,
454 new_entry,
455 compacted_yard,
456 compacted_handoff,
457 );
458 value.with_heap_index(new_index)
459 }
460
461 #[allow(clippy::too_many_arguments)]
462 fn evacuate_yard_value(
463 &mut self,
464 value: NanValue,
465 young_mark: u32,
466 yard_mark: u32,
467 handoff_mark: u32,
468 young_target: AllocSpace,
469 relocated_young: &mut [u32],
470 relocated_yard: &mut [u32],
471 relocated_handoff: &mut [u32],
472 compacted_yard: &mut Vec<ArenaEntry<T>>,
473 compacted_handoff: &mut Vec<ArenaEntry<T>>,
474 ) -> NanValue {
475 let index = value.heap_index().expect("yard value must be heap-backed");
476 let (_, raw_index) = Self::decode_index(index);
477 let relocation_slot = (raw_index - yard_mark) as usize;
478 let relocated_index = relocated_yard[relocation_slot];
479 if relocated_index != u32::MAX {
480 return value.with_heap_index(relocated_index);
481 }
482
483 let target = match young_target {
484 AllocSpace::Yard => AllocSpace::Yard,
485 AllocSpace::Handoff => AllocSpace::Handoff,
486 AllocSpace::Young => unreachable!("local evacuation must target yard or handoff"),
487 };
488 let (new_index, compacted_pos) = Self::allocate_local_target_slot(
489 target,
490 yard_mark,
491 handoff_mark,
492 compacted_yard,
493 compacted_handoff,
494 );
495 relocated_yard[relocation_slot] = new_index;
496
497 let entry = core::mem::replace(
498 &mut self.yard_entries[raw_index as usize],
499 ArenaEntry::Int(0),
500 );
501 let new_entry = self.evacuate_local_entry(
502 entry,
503 young_mark,
504 yard_mark,
505 handoff_mark,
506 young_target,
507 relocated_young,
508 relocated_yard,
509 relocated_handoff,
510 compacted_yard,
511 compacted_handoff,
512 );
513 Self::store_local_target_entry(
514 target,
515 compacted_pos,
516 new_entry,
517 compacted_yard,
518 compacted_handoff,
519 );
520 value.with_heap_index(new_index)
521 }
522
523 #[allow(clippy::too_many_arguments)]
524 fn evacuate_handoff_value(
525 &mut self,
526 value: NanValue,
527 young_mark: u32,
528 yard_mark: u32,
529 handoff_mark: u32,
530 young_target: AllocSpace,
531 relocated_young: &mut [u32],
532 relocated_yard: &mut [u32],
533 relocated_handoff: &mut [u32],
534 compacted_yard: &mut Vec<ArenaEntry<T>>,
535 compacted_handoff: &mut Vec<ArenaEntry<T>>,
536 ) -> NanValue {
537 let index = value
538 .heap_index()
539 .expect("handoff value must be heap-backed");
540 let (_, raw_index) = Self::decode_index(index);
541 let relocation_slot = (raw_index - handoff_mark) as usize;
542 let relocated_index = relocated_handoff[relocation_slot];
543 if relocated_index != u32::MAX {
544 return value.with_heap_index(relocated_index);
545 }
546
547 let target = match young_target {
548 AllocSpace::Yard => AllocSpace::Yard,
549 AllocSpace::Handoff => AllocSpace::Handoff,
550 AllocSpace::Young => unreachable!("local evacuation must target yard or handoff"),
551 };
552 let (new_index, compacted_pos) = Self::allocate_local_target_slot(
553 target,
554 yard_mark,
555 handoff_mark,
556 compacted_yard,
557 compacted_handoff,
558 );
559 relocated_handoff[relocation_slot] = new_index;
560
561 let entry = core::mem::replace(
562 &mut self.handoff_entries[raw_index as usize],
563 ArenaEntry::Int(0),
564 );
565 let new_entry = self.evacuate_local_entry(
566 entry,
567 young_mark,
568 yard_mark,
569 handoff_mark,
570 young_target,
571 relocated_young,
572 relocated_yard,
573 relocated_handoff,
574 compacted_yard,
575 compacted_handoff,
576 );
577 Self::store_local_target_entry(
578 target,
579 compacted_pos,
580 new_entry,
581 compacted_yard,
582 compacted_handoff,
583 );
584 value.with_heap_index(new_index)
585 }
586
587 #[allow(clippy::too_many_arguments)]
588 fn take_local_tail_value(
589 &mut self,
590 value: NanValue,
591 young_mark: u32,
592 yard_mark: u32,
593 handoff_mark: u32,
594 young_target: AllocSpace,
595 relocated_young: &mut [u32],
596 relocated_yard: &mut [u32],
597 relocated_handoff: &mut [u32],
598 compacted_yard: &mut Vec<ArenaEntry<T>>,
599 compacted_handoff: &mut Vec<ArenaEntry<T>>,
600 ) -> LocalTailStep<T> {
601 let Some(index) = value.heap_index() else {
602 return LocalTailStep::Done(value);
603 };
604 let (space, raw_index) = Self::decode_index(index);
605
606 match space {
607 HeapSpace::Young if self.is_young_index_in_region(index, young_mark) => {
608 let relocation_slot = (raw_index - young_mark) as usize;
609 let relocated_index = relocated_young[relocation_slot];
610 if relocated_index != u32::MAX {
611 return LocalTailStep::Done(value.with_heap_index(relocated_index));
612 }
613
614 let (new_index, compacted_pos) = Self::allocate_local_target_slot(
615 young_target,
616 yard_mark,
617 handoff_mark,
618 compacted_yard,
619 compacted_handoff,
620 );
621 relocated_young[relocation_slot] = new_index;
622 let entry = core::mem::replace(
623 &mut self.young_entries[raw_index as usize],
624 ArenaEntry::Int(0),
625 );
626 LocalTailStep::Taken(LocalTailEntry {
627 value: value.with_heap_index(new_index),
628 entry,
629 slot: LocalEvacuatedSlot {
630 target: young_target,
631 compacted_pos,
632 },
633 })
634 }
635 HeapSpace::Yard if self.is_yard_index_in_region(index, yard_mark) => {
636 let relocation_slot = (raw_index - yard_mark) as usize;
637 let relocated_index = relocated_yard[relocation_slot];
638 if relocated_index != u32::MAX {
639 return LocalTailStep::Done(value.with_heap_index(relocated_index));
640 }
641
642 let target = match young_target {
643 AllocSpace::Yard => AllocSpace::Yard,
644 AllocSpace::Handoff => AllocSpace::Handoff,
645 AllocSpace::Young => {
646 unreachable!("local evacuation must target yard or handoff")
647 }
648 };
649 let (new_index, compacted_pos) = Self::allocate_local_target_slot(
650 target,
651 yard_mark,
652 handoff_mark,
653 compacted_yard,
654 compacted_handoff,
655 );
656 relocated_yard[relocation_slot] = new_index;
657 let entry = core::mem::replace(
658 &mut self.yard_entries[raw_index as usize],
659 ArenaEntry::Int(0),
660 );
661 LocalTailStep::Taken(LocalTailEntry {
662 value: value.with_heap_index(new_index),
663 entry,
664 slot: LocalEvacuatedSlot {
665 target,
666 compacted_pos,
667 },
668 })
669 }
670 HeapSpace::Handoff if self.is_handoff_index_in_region(index, handoff_mark) => {
671 let relocation_slot = (raw_index - handoff_mark) as usize;
672 let relocated_index = relocated_handoff[relocation_slot];
673 if relocated_index != u32::MAX {
674 return LocalTailStep::Done(value.with_heap_index(relocated_index));
675 }
676
677 let target = match young_target {
678 AllocSpace::Yard => AllocSpace::Yard,
679 AllocSpace::Handoff => AllocSpace::Handoff,
680 AllocSpace::Young => {
681 unreachable!("local evacuation must target yard or handoff")
682 }
683 };
684 let (new_index, compacted_pos) = Self::allocate_local_target_slot(
685 target,
686 yard_mark,
687 handoff_mark,
688 compacted_yard,
689 compacted_handoff,
690 );
691 relocated_handoff[relocation_slot] = new_index;
692 let entry = core::mem::replace(
693 &mut self.handoff_entries[raw_index as usize],
694 ArenaEntry::Int(0),
695 );
696 LocalTailStep::Taken(LocalTailEntry {
697 value: value.with_heap_index(new_index),
698 entry,
699 slot: LocalEvacuatedSlot {
700 target,
701 compacted_pos,
702 },
703 })
704 }
705 _ => LocalTailStep::Done(value),
706 }
707 }
708
709 #[allow(clippy::too_many_arguments)]
710 fn evacuate_local_list(
711 &mut self,
712 list: ArenaList,
713 young_mark: u32,
714 yard_mark: u32,
715 handoff_mark: u32,
716 young_target: AllocSpace,
717 relocated_young: &mut [u32],
718 relocated_yard: &mut [u32],
719 relocated_handoff: &mut [u32],
720 compacted_yard: &mut Vec<ArenaEntry<T>>,
721 compacted_handoff: &mut Vec<ArenaEntry<T>>,
722 ) -> ArenaList {
723 match list {
724 ArenaList::Prepend { head, tail, len } => ArenaList::Prepend {
725 head: self.evacuate_local_root(
726 head,
727 young_mark,
728 yard_mark,
729 handoff_mark,
730 young_target,
731 relocated_young,
732 relocated_yard,
733 relocated_handoff,
734 compacted_yard,
735 compacted_handoff,
736 ),
737 tail: self.evacuate_local_prepend_tail_iterative(
738 tail,
739 young_mark,
740 yard_mark,
741 handoff_mark,
742 young_target,
743 relocated_young,
744 relocated_yard,
745 relocated_handoff,
746 compacted_yard,
747 compacted_handoff,
748 ),
749 len,
750 },
751 other => {
752 let mut rewrite = |arena: &mut Arena<T>, value: NanValue| {
753 arena.evacuate_local_root(
754 value,
755 young_mark,
756 yard_mark,
757 handoff_mark,
758 young_target,
759 relocated_young,
760 relocated_yard,
761 relocated_handoff,
762 compacted_yard,
763 compacted_handoff,
764 )
765 };
766 self.rewrite_list_with(other, &mut rewrite)
767 }
768 }
769 }
770
771 #[allow(clippy::too_many_arguments)]
772 fn evacuate_local_prepend_tail_iterative(
773 &mut self,
774 tail: NanValue,
775 young_mark: u32,
776 yard_mark: u32,
777 handoff_mark: u32,
778 young_target: AllocSpace,
779 relocated_young: &mut [u32],
780 relocated_yard: &mut [u32],
781 relocated_handoff: &mut [u32],
782 compacted_yard: &mut Vec<ArenaEntry<T>>,
783 compacted_handoff: &mut Vec<ArenaEntry<T>>,
784 ) -> NanValue {
785 let mut current = match self.take_local_tail_value(
786 tail,
787 young_mark,
788 yard_mark,
789 handoff_mark,
790 young_target,
791 relocated_young,
792 relocated_yard,
793 relocated_handoff,
794 compacted_yard,
795 compacted_handoff,
796 ) {
797 LocalTailStep::Done(value) => return value,
798 LocalTailStep::Taken(taken) => taken,
799 };
800 let first_value = current.value;
801
802 loop {
803 match current.entry {
804 ArenaEntry::List(ArenaList::Prepend { head, tail, len }) => {
805 let rewritten_head = self.evacuate_local_root(
806 head,
807 young_mark,
808 yard_mark,
809 handoff_mark,
810 young_target,
811 relocated_young,
812 relocated_yard,
813 relocated_handoff,
814 compacted_yard,
815 compacted_handoff,
816 );
817 let next = self.take_local_tail_value(
818 tail,
819 young_mark,
820 yard_mark,
821 handoff_mark,
822 young_target,
823 relocated_young,
824 relocated_yard,
825 relocated_handoff,
826 compacted_yard,
827 compacted_handoff,
828 );
829 match next {
830 LocalTailStep::Done(rewritten_tail) => {
831 Self::store_local_evacuated_slot(
832 current.slot,
833 ArenaEntry::List(ArenaList::Prepend {
834 head: rewritten_head,
835 tail: rewritten_tail,
836 len,
837 }),
838 compacted_yard,
839 compacted_handoff,
840 );
841 return first_value;
842 }
843 LocalTailStep::Taken(next_entry) => {
844 Self::store_local_evacuated_slot(
845 current.slot,
846 ArenaEntry::List(ArenaList::Prepend {
847 head: rewritten_head,
848 tail: next_entry.value,
849 len,
850 }),
851 compacted_yard,
852 compacted_handoff,
853 );
854 current = next_entry;
855 }
856 }
857 }
858 other => {
859 let new_entry = self.evacuate_local_entry(
860 other,
861 young_mark,
862 yard_mark,
863 handoff_mark,
864 young_target,
865 relocated_young,
866 relocated_yard,
867 relocated_handoff,
868 compacted_yard,
869 compacted_handoff,
870 );
871 Self::store_local_evacuated_slot(
872 current.slot,
873 new_entry,
874 compacted_yard,
875 compacted_handoff,
876 );
877 return first_value;
878 }
879 }
880 }
881 }
882
883 #[allow(clippy::too_many_arguments)]
884 fn evacuate_local_entry(
885 &mut self,
886 entry: ArenaEntry<T>,
887 young_mark: u32,
888 yard_mark: u32,
889 handoff_mark: u32,
890 young_target: AllocSpace,
891 relocated_young: &mut [u32],
892 relocated_yard: &mut [u32],
893 relocated_handoff: &mut [u32],
894 compacted_yard: &mut Vec<ArenaEntry<T>>,
895 compacted_handoff: &mut Vec<ArenaEntry<T>>,
896 ) -> ArenaEntry<T> {
897 if let ArenaEntry::List(list) = entry {
898 return ArenaEntry::List(self.evacuate_local_list(
899 list,
900 young_mark,
901 yard_mark,
902 handoff_mark,
903 young_target,
904 relocated_young,
905 relocated_yard,
906 relocated_handoff,
907 compacted_yard,
908 compacted_handoff,
909 ));
910 }
911
912 let mut rewrite = |arena: &mut Arena<T>, value: NanValue| {
913 arena.evacuate_local_root(
914 value,
915 young_mark,
916 yard_mark,
917 handoff_mark,
918 young_target,
919 relocated_young,
920 relocated_yard,
921 relocated_handoff,
922 compacted_yard,
923 compacted_handoff,
924 )
925 };
926 self.rewrite_entry_with(entry, &mut rewrite)
927 }
928
929 fn relocate_young_root(
930 &mut self,
931 value: NanValue,
932 mark: u32,
933 relocated: &mut [u32],
934 compacted: &mut Vec<ArenaEntry<T>>,
935 ) -> NanValue {
936 let Some(index) = value.heap_index() else {
937 return value;
938 };
939 let (space, raw_index) = Self::decode_index(index);
940 if matches!(space, HeapSpace::Young)
941 && raw_index >= mark
942 && raw_index < self.young_entries.len() as u32
943 {
944 return self.relocate_young_value(value, mark, relocated, compacted);
945 }
946 self.rewrite_young_refs_in_place(space, raw_index, mark, relocated, compacted);
947 value
948 }
949
950 fn relocate_young_value(
951 &mut self,
952 value: NanValue,
953 mark: u32,
954 relocated: &mut [u32],
955 compacted: &mut Vec<ArenaEntry<T>>,
956 ) -> NanValue {
957 let Some(index) = value.heap_index() else {
958 return value;
959 };
960 let (space, raw_index) = Self::decode_index(index);
961 if !matches!(space, HeapSpace::Young) || raw_index < mark {
962 return value;
963 }
964
965 let relocation_slot = raw_index as usize;
966 let relocated_index = relocated[relocation_slot];
967 if relocated_index != u32::MAX {
968 return value.with_heap_index(relocated_index);
969 }
970
971 let compacted_pos = compacted.len() as u32;
972 let new_index = Self::encode_index(HeapSpace::Young, mark + compacted_pos);
973 relocated[relocation_slot] = new_index;
974 compacted.push(ArenaEntry::Int(0));
975
976 let entry = core::mem::replace(
977 &mut self.young_entries[raw_index as usize],
978 ArenaEntry::Int(0),
979 );
980 let new_entry = self.relocate_young_entry(entry, mark, relocated, compacted);
981 compacted[compacted_pos as usize] = new_entry;
982 value.with_heap_index(new_index)
983 }
984
985 fn relocate_young_entry(
986 &mut self,
987 entry: ArenaEntry<T>,
988 mark: u32,
989 relocated: &mut [u32],
990 compacted: &mut Vec<ArenaEntry<T>>,
991 ) -> ArenaEntry<T> {
992 let mut rewrite = |arena: &mut Arena<T>, value: NanValue| {
993 arena.relocate_young_value(value, mark, relocated, compacted)
994 };
995 self.rewrite_entry_with(entry, &mut rewrite)
996 }
997
998 fn rewrite_young_refs_in_place(
999 &mut self,
1000 space: HeapSpace,
1001 raw_index: u32,
1002 mark: u32,
1003 relocated: &mut [u32],
1004 compacted: &mut Vec<ArenaEntry<T>>,
1005 ) {
1006 let raw_index = raw_index as usize;
1007 match space {
1008 HeapSpace::Young => {
1009 if raw_index >= self.young_entries.len() || raw_index >= mark as usize {
1010 return;
1011 }
1012 let entry =
1013 core::mem::replace(&mut self.young_entries[raw_index], ArenaEntry::Int(0));
1014 let new_entry = self.rewrite_young_entry(entry, mark, relocated, compacted);
1015 self.young_entries[raw_index] = new_entry;
1016 }
1017 HeapSpace::Yard => {
1018 if raw_index >= self.yard_entries.len() {
1019 return;
1020 }
1021 let entry =
1022 core::mem::replace(&mut self.yard_entries[raw_index], ArenaEntry::Int(0));
1023 let new_entry = self.rewrite_young_entry(entry, mark, relocated, compacted);
1024 self.yard_entries[raw_index] = new_entry;
1025 }
1026 HeapSpace::Handoff => {
1027 if raw_index >= self.handoff_entries.len() {
1028 return;
1029 }
1030 let entry =
1031 core::mem::replace(&mut self.handoff_entries[raw_index], ArenaEntry::Int(0));
1032 let new_entry = self.rewrite_young_entry(entry, mark, relocated, compacted);
1033 self.handoff_entries[raw_index] = new_entry;
1034 }
1035 HeapSpace::Stable => {
1036 if raw_index >= self.stable_entries.len() {
1037 return;
1038 }
1039 let entry =
1040 core::mem::replace(&mut self.stable_entries[raw_index], ArenaEntry::Int(0));
1041 let new_entry = self.rewrite_young_entry(entry, mark, relocated, compacted);
1042 self.stable_entries[raw_index] = new_entry;
1043 }
1044 }
1045 }
1046
1047 fn rewrite_young_entry(
1048 &mut self,
1049 entry: ArenaEntry<T>,
1050 mark: u32,
1051 relocated: &mut [u32],
1052 compacted: &mut Vec<ArenaEntry<T>>,
1053 ) -> ArenaEntry<T> {
1054 let mut rewrite = |arena: &mut Arena<T>, value: NanValue| {
1055 arena.relocate_young_root(value, mark, relocated, compacted)
1056 };
1057 self.rewrite_entry_with(entry, &mut rewrite)
1058 }
1059
1060 fn promote_region_root_to_target(
1061 &mut self,
1062 value: NanValue,
1063 mark: u32,
1064 relocated: &mut [u32],
1065 target: AllocSpace,
1066 ) -> NanValue {
1067 let Some(index) = value.heap_index() else {
1068 return value;
1069 };
1070 let (space, raw_index) = Self::decode_index(index);
1071 if matches!(space, HeapSpace::Young)
1072 && raw_index >= mark
1073 && raw_index < self.young_entries.len() as u32
1074 {
1075 return self.promote_value_to_target(value, mark, relocated, target);
1076 }
1077 self.rewrite_promoted_young_refs_in_place(space, raw_index, mark, relocated, target);
1078 value
1079 }
1080
1081 pub fn promote_young_roots_to_yard(&mut self, mark: u32, roots: &mut [NanValue]) {
1082 if self.young_entries.len() <= mark as usize {
1083 return;
1084 }
1085
1086 let mut relocated =
1087 Self::take_u32_scratch(&mut self.scratch_young, self.young_entries.len());
1088
1089 for root in roots {
1090 *root = self.promote_region_root_to_yard(*root, mark, &mut relocated);
1091 }
1092
1093 self.young_entries.truncate(mark as usize);
1094 Self::recycle_u32_scratch(&mut self.scratch_young, relocated);
1095 }
1096
1097 pub fn promote_young_roots_to_handoff(&mut self, mark: u32, roots: &mut [NanValue]) {
1098 if self.young_entries.len() <= mark as usize {
1099 return;
1100 }
1101
1102 let mut relocated =
1103 Self::take_u32_scratch(&mut self.scratch_young, self.young_entries.len());
1104
1105 for root in roots {
1106 *root = self.promote_region_root_to_handoff(*root, mark, &mut relocated);
1107 }
1108
1109 self.young_entries.truncate(mark as usize);
1110 Self::recycle_u32_scratch(&mut self.scratch_young, relocated);
1111 }
1112
1113 pub fn promote_roots_to_stable(&mut self, roots: &mut [NanValue]) {
1114 let mut relocated_young =
1115 Self::take_u32_scratch(&mut self.scratch_young, self.young_entries.len());
1116 let mut relocated_yard =
1117 Self::take_u32_scratch(&mut self.scratch_yard, self.yard_entries.len());
1118 let mut relocated_handoff =
1119 Self::take_u32_scratch(&mut self.scratch_handoff, self.handoff_entries.len());
1120
1121 for root in roots {
1122 *root = self.promote_value_to_stable(
1123 *root,
1124 &mut relocated_young,
1125 &mut relocated_yard,
1126 &mut relocated_handoff,
1127 );
1128 }
1129 Self::recycle_u32_scratch(&mut self.scratch_young, relocated_young);
1130 Self::recycle_u32_scratch(&mut self.scratch_yard, relocated_yard);
1131 Self::recycle_u32_scratch(&mut self.scratch_handoff, relocated_handoff);
1132 }
1133
1134 pub fn collect_yard_from_roots(&mut self, mark: u32, roots: &mut [NanValue]) {
1135 if self.yard_entries.len() <= mark as usize {
1136 return;
1137 }
1138
1139 let mut relocated = Self::take_u32_scratch(&mut self.scratch_yard, self.yard_entries.len());
1140 let mut compacted = Vec::with_capacity(self.yard_entries.len() - mark as usize);
1141
1142 for root in roots {
1143 *root = self.relocate_yard_root(*root, mark, &mut relocated, &mut compacted);
1144 }
1145
1146 self.yard_entries.truncate(mark as usize);
1147 self.yard_entries.extend(compacted);
1148 Self::recycle_u32_scratch(&mut self.scratch_yard, relocated);
1149 }
1150
1151 pub fn collect_stable_from_roots(&mut self, roots: &mut [NanValue]) {
1152 if self.stable_entries.is_empty() {
1153 return;
1154 }
1155
1156 let mut relocated =
1157 Self::take_u32_scratch(&mut self.scratch_stable, self.stable_entries.len());
1158 let mut compacted = Vec::with_capacity(self.stable_entries.len());
1159
1160 for root in roots {
1161 *root = self.relocate_stable_root(*root, &mut relocated, &mut compacted);
1162 }
1163
1164 self.stable_entries = compacted;
1165 Self::recycle_u32_scratch(&mut self.scratch_stable, relocated);
1166 }
1167
1168 fn promote_region_root_to_yard(
1169 &mut self,
1170 value: NanValue,
1171 mark: u32,
1172 relocated: &mut [u32],
1173 ) -> NanValue {
1174 self.promote_region_root_to_target(value, mark, relocated, AllocSpace::Yard)
1175 }
1176
1177 fn promote_region_root_to_handoff(
1178 &mut self,
1179 value: NanValue,
1180 mark: u32,
1181 relocated: &mut [u32],
1182 ) -> NanValue {
1183 self.promote_region_root_to_target(value, mark, relocated, AllocSpace::Handoff)
1184 }
1185
1186 fn store_promote_rewrite_slot(&mut self, slot: PromoteRewriteSlot, entry: ArenaEntry<T>) {
1187 match slot {
1188 PromoteRewriteSlot::InPlace { space, raw_index } => match space {
1189 HeapSpace::Young => self.young_entries[raw_index] = entry,
1190 HeapSpace::Yard => self.yard_entries[raw_index] = entry,
1191 HeapSpace::Handoff => self.handoff_entries[raw_index] = entry,
1192 HeapSpace::Stable => self.stable_entries[raw_index] = entry,
1193 },
1194 PromoteRewriteSlot::Promoted { target, raw_index } => match target {
1195 AllocSpace::Yard => self.yard_entries[raw_index] = entry,
1196 AllocSpace::Handoff => self.handoff_entries[raw_index] = entry,
1197 AllocSpace::Young => unreachable!("promotion target must be yard or handoff"),
1198 },
1199 }
1200 }
1201
1202 fn take_promote_tail_value(
1203 &mut self,
1204 value: NanValue,
1205 mark: u32,
1206 relocated: &mut [u32],
1207 target: AllocSpace,
1208 ) -> PromoteTailStep<T> {
1209 let Some(index) = value.heap_index() else {
1210 return PromoteTailStep::Done(value);
1211 };
1212 let (space, raw_index) = Self::decode_index(index);
1213
1214 if matches!(space, HeapSpace::Young) && raw_index >= mark {
1215 let relocation_slot = raw_index as usize;
1216 let relocated_index = relocated[relocation_slot];
1217 if relocated_index != u32::MAX {
1218 return PromoteTailStep::Done(value.with_heap_index(relocated_index));
1219 }
1220
1221 let (new_index, target_raw_index) = match target {
1222 AllocSpace::Yard => {
1223 let raw = self.yard_entries.len();
1224 self.yard_entries.push(ArenaEntry::Int(0));
1225 (Self::encode_yard_index(raw as u32), raw)
1226 }
1227 AllocSpace::Handoff => {
1228 let raw = self.handoff_entries.len();
1229 self.handoff_entries.push(ArenaEntry::Int(0));
1230 (Self::encode_handoff_index(raw as u32), raw)
1231 }
1232 AllocSpace::Young => unreachable!("promotion target must be yard or handoff"),
1233 };
1234 relocated[relocation_slot] = new_index;
1235 self.note_peak_usage();
1236 let entry = core::mem::replace(
1237 &mut self.young_entries[raw_index as usize],
1238 ArenaEntry::Int(0),
1239 );
1240 return PromoteTailStep::Taken(PromoteTailEntry {
1241 value: value.with_heap_index(new_index),
1242 entry,
1243 slot: PromoteRewriteSlot::Promoted {
1244 target,
1245 raw_index: target_raw_index,
1246 },
1247 });
1248 }
1249
1250 let raw_index = raw_index as usize;
1251 let entry = match space {
1252 HeapSpace::Young => {
1253 if raw_index >= self.young_entries.len() || raw_index >= mark as usize {
1254 return PromoteTailStep::Done(value);
1255 }
1256 core::mem::replace(&mut self.young_entries[raw_index], ArenaEntry::Int(0))
1257 }
1258 HeapSpace::Yard => {
1259 if raw_index >= self.yard_entries.len() {
1260 return PromoteTailStep::Done(value);
1261 }
1262 core::mem::replace(&mut self.yard_entries[raw_index], ArenaEntry::Int(0))
1263 }
1264 HeapSpace::Handoff => {
1265 if raw_index >= self.handoff_entries.len() {
1266 return PromoteTailStep::Done(value);
1267 }
1268 core::mem::replace(&mut self.handoff_entries[raw_index], ArenaEntry::Int(0))
1269 }
1270 HeapSpace::Stable => {
1271 if raw_index >= self.stable_entries.len() {
1272 return PromoteTailStep::Done(value);
1273 }
1274 core::mem::replace(&mut self.stable_entries[raw_index], ArenaEntry::Int(0))
1275 }
1276 };
1277
1278 PromoteTailStep::Taken(PromoteTailEntry {
1279 value,
1280 entry,
1281 slot: PromoteRewriteSlot::InPlace { space, raw_index },
1282 })
1283 }
1284
1285 fn promote_list_young_refs_to_target(
1286 &mut self,
1287 list: ArenaList,
1288 mark: u32,
1289 relocated: &mut [u32],
1290 target: AllocSpace,
1291 ) -> ArenaList {
1292 match list {
1293 ArenaList::Prepend { head, tail, len } => ArenaList::Prepend {
1294 head: self.promote_region_root_to_target(head, mark, relocated, target),
1295 tail: self.promote_prepend_tail_iterative(tail, mark, relocated, target),
1296 len,
1297 },
1298 other => {
1299 let mut rewrite = |arena: &mut Arena<T>, value: NanValue| {
1300 arena.promote_region_root_to_target(value, mark, relocated, target)
1301 };
1302 self.rewrite_list_with(other, &mut rewrite)
1303 }
1304 }
1305 }
1306
1307 fn promote_prepend_tail_iterative(
1308 &mut self,
1309 tail: NanValue,
1310 mark: u32,
1311 relocated: &mut [u32],
1312 target: AllocSpace,
1313 ) -> NanValue {
1314 let mut current = match self.take_promote_tail_value(tail, mark, relocated, target) {
1315 PromoteTailStep::Done(value) => return value,
1316 PromoteTailStep::Taken(taken) => taken,
1317 };
1318 let first_value = current.value;
1319
1320 loop {
1321 match current.entry {
1322 ArenaEntry::List(ArenaList::Prepend { head, tail, len }) => {
1323 let rewritten_head =
1324 self.promote_region_root_to_target(head, mark, relocated, target);
1325 let next = self.take_promote_tail_value(tail, mark, relocated, target);
1326 match next {
1327 PromoteTailStep::Done(rewritten_tail) => {
1328 self.store_promote_rewrite_slot(
1329 current.slot,
1330 ArenaEntry::List(ArenaList::Prepend {
1331 head: rewritten_head,
1332 tail: rewritten_tail,
1333 len,
1334 }),
1335 );
1336 return first_value;
1337 }
1338 PromoteTailStep::Taken(next_entry) => {
1339 self.store_promote_rewrite_slot(
1340 current.slot,
1341 ArenaEntry::List(ArenaList::Prepend {
1342 head: rewritten_head,
1343 tail: next_entry.value,
1344 len,
1345 }),
1346 );
1347 current = next_entry;
1348 }
1349 }
1350 }
1351 other => {
1352 let new_entry = match current.slot {
1353 PromoteRewriteSlot::Promoted { .. } => {
1354 self.promote_entry_to_target(other, mark, relocated, target)
1355 }
1356 PromoteRewriteSlot::InPlace { .. } => {
1357 self.rewrite_promoted_young_entry(other, mark, relocated, target)
1358 }
1359 };
1360 self.store_promote_rewrite_slot(current.slot, new_entry);
1361 return first_value;
1362 }
1363 }
1364 }
1365 }
1366
1367 fn rewrite_promoted_young_refs_in_place(
1368 &mut self,
1369 space: HeapSpace,
1370 raw_index: u32,
1371 mark: u32,
1372 relocated: &mut [u32],
1373 target: AllocSpace,
1374 ) {
1375 let raw_index = raw_index as usize;
1376 match space {
1377 HeapSpace::Young => {
1378 if raw_index >= self.young_entries.len() || raw_index >= mark as usize {
1379 return;
1380 }
1381 let entry =
1382 core::mem::replace(&mut self.young_entries[raw_index], ArenaEntry::Int(0));
1383 let new_entry = self.rewrite_promoted_young_entry(entry, mark, relocated, target);
1384 self.young_entries[raw_index] = new_entry;
1385 }
1386 HeapSpace::Yard => {
1387 if raw_index >= self.yard_entries.len() {
1388 return;
1389 }
1390 let entry =
1391 core::mem::replace(&mut self.yard_entries[raw_index], ArenaEntry::Int(0));
1392 let new_entry = self.rewrite_promoted_young_entry(entry, mark, relocated, target);
1393 self.yard_entries[raw_index] = new_entry;
1394 }
1395 HeapSpace::Handoff => {
1396 if raw_index >= self.handoff_entries.len() {
1397 return;
1398 }
1399 let entry =
1400 core::mem::replace(&mut self.handoff_entries[raw_index], ArenaEntry::Int(0));
1401 let new_entry = self.rewrite_promoted_young_entry(entry, mark, relocated, target);
1402 self.handoff_entries[raw_index] = new_entry;
1403 }
1404 HeapSpace::Stable => {
1405 if raw_index >= self.stable_entries.len() {
1406 return;
1407 }
1408 let entry =
1409 core::mem::replace(&mut self.stable_entries[raw_index], ArenaEntry::Int(0));
1410 let new_entry = self.rewrite_promoted_young_entry(entry, mark, relocated, target);
1411 self.stable_entries[raw_index] = new_entry;
1412 }
1413 }
1414 }
1415
1416 fn rewrite_promoted_young_entry(
1417 &mut self,
1418 entry: ArenaEntry<T>,
1419 mark: u32,
1420 relocated: &mut [u32],
1421 target: AllocSpace,
1422 ) -> ArenaEntry<T> {
1423 if let ArenaEntry::List(list) = entry {
1424 return ArenaEntry::List(
1425 self.promote_list_young_refs_to_target(list, mark, relocated, target),
1426 );
1427 }
1428
1429 let mut rewrite = |arena: &mut Arena<T>, value: NanValue| {
1430 arena.promote_region_root_to_target(value, mark, relocated, target)
1431 };
1432 self.rewrite_entry_with(entry, &mut rewrite)
1433 }
1434
1435 fn promote_value_to_target(
1436 &mut self,
1437 value: NanValue,
1438 mark: u32,
1439 relocated: &mut [u32],
1440 target: AllocSpace,
1441 ) -> NanValue {
1442 let Some(index) = value.heap_index() else {
1443 return value;
1444 };
1445 let (space, raw_index) = Self::decode_index(index);
1446 if !matches!(space, HeapSpace::Young) || raw_index < mark {
1447 return value;
1448 }
1449
1450 let relocation_slot = raw_index as usize;
1451 let relocated_index = relocated[relocation_slot];
1452 if relocated_index != u32::MAX {
1453 return value.with_heap_index(relocated_index);
1454 }
1455
1456 let new_index = match target {
1457 AllocSpace::Yard => Self::encode_yard_index(self.yard_entries.len() as u32),
1458 AllocSpace::Handoff => Self::encode_handoff_index(self.handoff_entries.len() as u32),
1459 AllocSpace::Young => unreachable!("promotion target must be yard or handoff"),
1460 };
1461 relocated[relocation_slot] = new_index;
1462 match target {
1463 AllocSpace::Yard => self.yard_entries.push(ArenaEntry::Int(0)),
1464 AllocSpace::Handoff => self.handoff_entries.push(ArenaEntry::Int(0)),
1465 AllocSpace::Young => unreachable!(),
1466 }
1467 self.note_peak_usage();
1468
1469 let entry = core::mem::replace(
1470 &mut self.young_entries[raw_index as usize],
1471 ArenaEntry::Int(0),
1472 );
1473 let new_entry = self.promote_entry_to_target(entry, mark, relocated, target);
1474 match target {
1475 AllocSpace::Yard => {
1476 self.yard_entries[(new_index & HEAP_INDEX_MASK_U32) as usize] = new_entry;
1477 }
1478 AllocSpace::Handoff => {
1479 self.handoff_entries[(new_index & HEAP_INDEX_MASK_U32) as usize] = new_entry;
1480 }
1481 AllocSpace::Young => unreachable!(),
1482 }
1483 value.with_heap_index(new_index)
1484 }
1485
1486 #[inline(always)]
1488 fn value_needs_young_promotion(value: NanValue, mark: u32) -> bool {
1489 if let Some(index) = value.heap_index() {
1490 let (space, raw_index) = Self::decode_index(index);
1491 matches!(space, HeapSpace::Young) && raw_index >= mark
1492 } else {
1493 false
1494 }
1495 }
1496
1497 fn promote_entry_to_target(
1498 &mut self,
1499 entry: ArenaEntry<T>,
1500 mark: u32,
1501 relocated: &mut [u32],
1502 target: AllocSpace,
1503 ) -> ArenaEntry<T> {
1504 match &entry {
1508 ArenaEntry::Vector(items) | ArenaEntry::Tuple(items)
1509 if !items.is_empty()
1510 && !items
1511 .iter()
1512 .any(|v| Self::value_needs_young_promotion(*v, mark)) =>
1513 {
1514 return entry;
1515 }
1516 ArenaEntry::Map(map)
1517 if !map.is_empty()
1518 && !map.values().any(|(k, v)| {
1519 Self::value_needs_young_promotion(*k, mark)
1520 || Self::value_needs_young_promotion(*v, mark)
1521 }) =>
1522 {
1523 return entry;
1524 }
1525 _ => {}
1526 }
1527 if let ArenaEntry::List(list) = entry {
1528 return ArenaEntry::List(
1529 self.promote_list_young_refs_to_target(list, mark, relocated, target),
1530 );
1531 }
1532
1533 let mut rewrite = |arena: &mut Arena<T>, value: NanValue| {
1534 arena.promote_region_root_to_target(value, mark, relocated, target)
1535 };
1536 self.rewrite_entry_with(entry, &mut rewrite)
1537 }
1538
1539 fn promote_value_to_stable(
1540 &mut self,
1541 value: NanValue,
1542 relocated_young: &mut [u32],
1543 relocated_yard: &mut [u32],
1544 relocated_handoff: &mut [u32],
1545 ) -> NanValue {
1546 let Some(index) = value.heap_index() else {
1547 return value;
1548 };
1549 let (space, raw_index) = Self::decode_index(index);
1550 match space {
1551 HeapSpace::Young => {
1552 let relocation_slot = raw_index as usize;
1553 let relocated_index = relocated_young[relocation_slot];
1554 if relocated_index != u32::MAX {
1555 return value.with_heap_index(relocated_index);
1556 }
1557
1558 let new_index = Self::encode_stable_index(self.stable_entries.len() as u32);
1559 relocated_young[relocation_slot] = new_index;
1560 self.stable_entries.push(ArenaEntry::Int(0));
1561 self.note_peak_usage();
1562
1563 let entry = self.young_entries[raw_index as usize].clone();
1564 let new_entry = self.promote_entry_to_stable(
1565 entry,
1566 relocated_young,
1567 relocated_yard,
1568 relocated_handoff,
1569 );
1570 self.stable_entries[(new_index & HEAP_INDEX_MASK_U32) as usize] = new_entry;
1571 value.with_heap_index(new_index)
1572 }
1573 HeapSpace::Yard => {
1574 let relocation_slot = raw_index as usize;
1575 let relocated_index = relocated_yard[relocation_slot];
1576 if relocated_index != u32::MAX {
1577 return value.with_heap_index(relocated_index);
1578 }
1579
1580 let new_index = Self::encode_stable_index(self.stable_entries.len() as u32);
1581 relocated_yard[relocation_slot] = new_index;
1582 self.stable_entries.push(ArenaEntry::Int(0));
1583 self.note_peak_usage();
1584
1585 let entry = self.yard_entries[raw_index as usize].clone();
1586 let new_entry = self.promote_entry_to_stable(
1587 entry,
1588 relocated_young,
1589 relocated_yard,
1590 relocated_handoff,
1591 );
1592 self.stable_entries[(new_index & HEAP_INDEX_MASK_U32) as usize] = new_entry;
1593 value.with_heap_index(new_index)
1594 }
1595 HeapSpace::Handoff => {
1596 let relocation_slot = raw_index as usize;
1597 let relocated_index = relocated_handoff[relocation_slot];
1598 if relocated_index != u32::MAX {
1599 return value.with_heap_index(relocated_index);
1600 }
1601
1602 let new_index = Self::encode_stable_index(self.stable_entries.len() as u32);
1603 relocated_handoff[relocation_slot] = new_index;
1604 self.stable_entries.push(ArenaEntry::Int(0));
1605 self.note_peak_usage();
1606
1607 let entry = self.handoff_entries[raw_index as usize].clone();
1608 let new_entry = self.promote_entry_to_stable(
1609 entry,
1610 relocated_young,
1611 relocated_yard,
1612 relocated_handoff,
1613 );
1614 self.stable_entries[(new_index & HEAP_INDEX_MASK_U32) as usize] = new_entry;
1615 value.with_heap_index(new_index)
1616 }
1617 HeapSpace::Stable => value,
1618 }
1619 }
1620
1621 fn promote_entry_to_stable(
1622 &mut self,
1623 entry: ArenaEntry<T>,
1624 relocated_young: &mut [u32],
1625 relocated_yard: &mut [u32],
1626 relocated_handoff: &mut [u32],
1627 ) -> ArenaEntry<T> {
1628 let mut rewrite = |arena: &mut Arena<T>, value: NanValue| {
1629 arena.promote_value_to_stable(value, relocated_young, relocated_yard, relocated_handoff)
1630 };
1631 self.rewrite_entry_with(entry, &mut rewrite)
1632 }
1633
1634 fn relocate_yard_root(
1635 &mut self,
1636 value: NanValue,
1637 mark: u32,
1638 relocated: &mut [u32],
1639 compacted: &mut Vec<ArenaEntry<T>>,
1640 ) -> NanValue {
1641 let Some(index) = value.heap_index() else {
1642 return value;
1643 };
1644 let (space, raw_index) = Self::decode_index(index);
1645 if matches!(space, HeapSpace::Yard)
1646 && raw_index >= mark
1647 && raw_index < self.yard_entries.len() as u32
1648 {
1649 return self.relocate_yard_value(value, mark, relocated, compacted);
1650 }
1651 self.rewrite_yard_refs_in_place(space, raw_index, mark, relocated, compacted);
1652 value
1653 }
1654
1655 fn relocate_yard_value(
1656 &mut self,
1657 value: NanValue,
1658 mark: u32,
1659 relocated: &mut [u32],
1660 compacted: &mut Vec<ArenaEntry<T>>,
1661 ) -> NanValue {
1662 let Some(index) = value.heap_index() else {
1663 return value;
1664 };
1665 let (space, raw_index) = Self::decode_index(index);
1666 if !matches!(space, HeapSpace::Yard) || raw_index < mark {
1667 return value;
1668 }
1669
1670 let relocation_slot = raw_index as usize;
1671 let relocated_index = relocated[relocation_slot];
1672 if relocated_index != u32::MAX {
1673 return value.with_heap_index(relocated_index);
1674 }
1675
1676 let compacted_pos = compacted.len() as u32;
1677 let new_index = Self::encode_yard_index(mark + compacted_pos);
1678 relocated[relocation_slot] = new_index;
1679 compacted.push(ArenaEntry::Int(0));
1680
1681 let entry = core::mem::replace(
1682 &mut self.yard_entries[raw_index as usize],
1683 ArenaEntry::Int(0),
1684 );
1685 let new_entry = self.relocate_yard_entry(entry, mark, relocated, compacted);
1686 compacted[compacted_pos as usize] = new_entry;
1687 value.with_heap_index(new_index)
1688 }
1689
1690 fn relocate_yard_entry(
1691 &mut self,
1692 entry: ArenaEntry<T>,
1693 mark: u32,
1694 relocated: &mut [u32],
1695 compacted: &mut Vec<ArenaEntry<T>>,
1696 ) -> ArenaEntry<T> {
1697 let mut rewrite = |arena: &mut Arena<T>, value: NanValue| {
1698 arena.relocate_yard_value(value, mark, relocated, compacted)
1699 };
1700 self.rewrite_entry_with(entry, &mut rewrite)
1701 }
1702
1703 fn rewrite_yard_refs_in_place(
1704 &mut self,
1705 space: HeapSpace,
1706 raw_index: u32,
1707 mark: u32,
1708 relocated: &mut [u32],
1709 compacted: &mut Vec<ArenaEntry<T>>,
1710 ) {
1711 let raw_index = raw_index as usize;
1712 match space {
1713 HeapSpace::Young => {
1714 if raw_index >= self.young_entries.len() {
1715 return;
1716 }
1717 let entry =
1718 core::mem::replace(&mut self.young_entries[raw_index], ArenaEntry::Int(0));
1719 let new_entry = self.rewrite_yard_entry(entry, mark, relocated, compacted);
1720 self.young_entries[raw_index] = new_entry;
1721 }
1722 HeapSpace::Yard => {
1723 if raw_index >= self.yard_entries.len() || raw_index >= mark as usize {
1724 return;
1725 }
1726 let entry =
1727 core::mem::replace(&mut self.yard_entries[raw_index], ArenaEntry::Int(0));
1728 let new_entry = self.rewrite_yard_entry(entry, mark, relocated, compacted);
1729 self.yard_entries[raw_index] = new_entry;
1730 }
1731 HeapSpace::Handoff => {
1732 if raw_index >= self.handoff_entries.len() {
1733 return;
1734 }
1735 let entry =
1736 core::mem::replace(&mut self.handoff_entries[raw_index], ArenaEntry::Int(0));
1737 let new_entry = self.rewrite_yard_entry(entry, mark, relocated, compacted);
1738 self.handoff_entries[raw_index] = new_entry;
1739 }
1740 HeapSpace::Stable => {
1741 if raw_index >= self.stable_entries.len() {
1742 return;
1743 }
1744 let entry =
1745 core::mem::replace(&mut self.stable_entries[raw_index], ArenaEntry::Int(0));
1746 let new_entry = self.rewrite_yard_entry(entry, mark, relocated, compacted);
1747 self.stable_entries[raw_index] = new_entry;
1748 }
1749 }
1750 }
1751
1752 fn rewrite_yard_entry(
1753 &mut self,
1754 entry: ArenaEntry<T>,
1755 mark: u32,
1756 relocated: &mut [u32],
1757 compacted: &mut Vec<ArenaEntry<T>>,
1758 ) -> ArenaEntry<T> {
1759 let mut rewrite = |arena: &mut Arena<T>, value: NanValue| {
1760 arena.relocate_yard_root(value, mark, relocated, compacted)
1761 };
1762 self.rewrite_entry_with(entry, &mut rewrite)
1763 }
1764
1765 fn relocate_stable_root(
1766 &mut self,
1767 value: NanValue,
1768 relocated: &mut [u32],
1769 compacted: &mut Vec<ArenaEntry<T>>,
1770 ) -> NanValue {
1771 let Some(index) = value.heap_index() else {
1772 return value;
1773 };
1774 if !matches!(Self::decode_index(index).0, HeapSpace::Stable) {
1775 return value;
1776 }
1777 self.relocate_stable_value(value, relocated, compacted)
1778 }
1779
1780 fn relocate_stable_value(
1781 &mut self,
1782 value: NanValue,
1783 relocated: &mut [u32],
1784 compacted: &mut Vec<ArenaEntry<T>>,
1785 ) -> NanValue {
1786 let Some(index) = value.heap_index() else {
1787 return value;
1788 };
1789 let (space, raw_index) = Self::decode_index(index);
1790 if !matches!(space, HeapSpace::Stable) {
1791 return value;
1792 }
1793
1794 let relocation_slot = raw_index as usize;
1795 let relocated_index = relocated[relocation_slot];
1796 if relocated_index != u32::MAX {
1797 return value.with_heap_index(relocated_index);
1798 }
1799
1800 let new_index = Self::encode_stable_index(compacted.len() as u32);
1801 relocated[relocation_slot] = new_index;
1802 compacted.push(ArenaEntry::Int(0));
1803
1804 let entry = core::mem::replace(
1805 &mut self.stable_entries[raw_index as usize],
1806 ArenaEntry::Int(0),
1807 );
1808 let new_entry = self.relocate_stable_entry(entry, relocated, compacted);
1809 compacted[(new_index & HEAP_INDEX_MASK_U32) as usize] = new_entry;
1810 value.with_heap_index(new_index)
1811 }
1812
1813 fn relocate_stable_entry(
1814 &mut self,
1815 entry: ArenaEntry<T>,
1816 relocated: &mut [u32],
1817 compacted: &mut Vec<ArenaEntry<T>>,
1818 ) -> ArenaEntry<T> {
1819 let mut rewrite = |arena: &mut Arena<T>, value: NanValue| {
1820 arena.relocate_stable_value(value, relocated, compacted)
1821 };
1822 self.rewrite_entry_with(entry, &mut rewrite)
1823 }
1824}