seq_runtime/
stack.rs

1//! Tagged Stack Implementation
2//!
3//! This module implements the stack using a contiguous array of 40-byte StackValue entries.
4//! Each StackValue has the layout: { slot0: discriminant, slot1-4: payload }
5//!
6//! The Stack type is a pointer to the "current position" (where next push goes).
7//! - Push: store at *sp, return sp + 1
8//! - Pop: return sp - 1, read from *(sp - 1)
9
10use crate::tagged_stack::StackValue;
11use crate::value::Value;
12use std::sync::Arc;
13
14/// Stack: A pointer to the current position in a contiguous array of StackValue.
15///
16/// Points to where the next value would be pushed.
17/// sp - 1 points to the top value, sp - 2 to second, etc.
18pub type Stack = *mut StackValue;
19
20/// Discriminant values matching codegen
21pub const DISC_INT: u64 = 0;
22pub const DISC_FLOAT: u64 = 1;
23pub const DISC_BOOL: u64 = 2;
24pub const DISC_STRING: u64 = 3;
25pub const DISC_VARIANT: u64 = 4;
26pub const DISC_MAP: u64 = 5;
27pub const DISC_QUOTATION: u64 = 6;
28pub const DISC_CLOSURE: u64 = 7;
29pub const DISC_CHANNEL: u64 = 8;
30
31/// Convert a Value to a StackValue for pushing onto the tagged stack
32#[inline]
33pub fn value_to_stack_value(value: Value) -> StackValue {
34    match value {
35        Value::Int(i) => StackValue {
36            slot0: DISC_INT,
37            slot1: i as u64,
38            slot2: 0,
39            slot3: 0,
40            slot4: 0,
41        },
42        Value::Float(f) => StackValue {
43            slot0: DISC_FLOAT,
44            slot1: f.to_bits(),
45            slot2: 0,
46            slot3: 0,
47            slot4: 0,
48        },
49        Value::Bool(b) => StackValue {
50            slot0: DISC_BOOL,
51            slot1: if b { 1 } else { 0 },
52            slot2: 0,
53            slot3: 0,
54            slot4: 0,
55        },
56        Value::String(s) => {
57            // SeqString has: ptr, len, capacity, global
58            // Store these in slots 1-4
59            let (ptr, len, capacity, global) = s.into_raw_parts();
60            StackValue {
61                slot0: DISC_STRING,
62                slot1: ptr as u64,
63                slot2: len as u64,
64                slot3: capacity as u64,
65                slot4: if global { 1 } else { 0 },
66            }
67        }
68        Value::Variant(v) => {
69            let ptr = Arc::into_raw(v) as u64;
70            StackValue {
71                slot0: DISC_VARIANT,
72                slot1: ptr,
73                slot2: 0,
74                slot3: 0,
75                slot4: 0,
76            }
77        }
78        Value::Map(m) => {
79            let ptr = Box::into_raw(m) as u64;
80            StackValue {
81                slot0: DISC_MAP,
82                slot1: ptr,
83                slot2: 0,
84                slot3: 0,
85                slot4: 0,
86            }
87        }
88        Value::Quotation { wrapper, impl_ } => StackValue {
89            slot0: DISC_QUOTATION,
90            slot1: wrapper as u64,
91            slot2: impl_ as u64,
92            slot3: 0,
93            slot4: 0,
94        },
95        Value::Closure { fn_ptr, env } => {
96            // Arc<[Value]> is a fat pointer - use Box to store it
97            let env_box = Box::new(env);
98            let env_ptr = Box::into_raw(env_box) as u64;
99            StackValue {
100                slot0: DISC_CLOSURE,
101                slot1: fn_ptr as u64,
102                slot2: env_ptr,
103                slot3: 0,
104                slot4: 0,
105            }
106        }
107        Value::Channel(ch) => {
108            // Store Arc<ChannelData> as raw pointer
109            let ptr = Arc::into_raw(ch) as u64;
110            StackValue {
111                slot0: DISC_CHANNEL,
112                slot1: ptr,
113                slot2: 0,
114                slot3: 0,
115                slot4: 0,
116            }
117        }
118    }
119}
120
121/// Convert a StackValue back to a Value
122///
123/// # Safety
124/// The StackValue must contain valid data for its discriminant
125#[inline]
126pub unsafe fn stack_value_to_value(sv: StackValue) -> Value {
127    unsafe {
128        match sv.slot0 {
129            DISC_INT => Value::Int(sv.slot1 as i64),
130            DISC_FLOAT => Value::Float(f64::from_bits(sv.slot1)),
131            DISC_BOOL => Value::Bool(sv.slot1 != 0),
132            DISC_STRING => {
133                use crate::seqstring::SeqString;
134                let ptr = sv.slot1 as *const u8;
135                let len = sv.slot2 as usize;
136                let capacity = sv.slot3 as usize;
137                let global = sv.slot4 != 0;
138                Value::String(SeqString::from_raw_parts(ptr, len, capacity, global))
139            }
140            DISC_VARIANT => {
141                use crate::value::VariantData;
142                let arc = Arc::from_raw(sv.slot1 as *const VariantData);
143                Value::Variant(arc)
144            }
145            DISC_MAP => {
146                use crate::value::MapKey;
147                use std::collections::HashMap;
148                let boxed = Box::from_raw(sv.slot1 as *mut HashMap<MapKey, Value>);
149                Value::Map(boxed)
150            }
151            DISC_QUOTATION => Value::Quotation {
152                wrapper: sv.slot1 as usize,
153                impl_: sv.slot2 as usize,
154            },
155            DISC_CLOSURE => {
156                // Unbox the Arc<[Value]> that we boxed in value_to_stack_value
157                let env_box = Box::from_raw(sv.slot2 as *mut Arc<[Value]>);
158                Value::Closure {
159                    fn_ptr: sv.slot1 as usize,
160                    env: *env_box,
161                }
162            }
163            DISC_CHANNEL => {
164                use crate::value::ChannelData;
165                let arc = Arc::from_raw(sv.slot1 as *const ChannelData);
166                Value::Channel(arc)
167            }
168            _ => panic!("Invalid discriminant: {}", sv.slot0),
169        }
170    }
171}
172
173/// Clone a StackValue from LLVM IR - reads from src pointer, writes to dst pointer.
174/// This is the FFI-callable version for inline codegen that avoids ABI issues
175/// with passing large structs by value.
176///
177/// # Safety
178/// Both src and dst pointers must be valid and properly aligned StackValue pointers.
179#[unsafe(no_mangle)]
180pub unsafe extern "C" fn patch_seq_clone_value(src: *const StackValue, dst: *mut StackValue) {
181    unsafe {
182        let sv = &*src;
183        let cloned = clone_stack_value(sv);
184        *dst = cloned;
185    }
186}
187
188/// Clone a StackValue, handling reference counting for heap types.
189///
190/// # Cloning Strategy by Type
191/// - **Int, Float, Bool, Quotation**: Bitwise copy (no heap allocation)
192/// - **String**: Deep copy to a new global (refcounted) string. This is necessary
193///   because the source may be an arena-allocated string that would become invalid
194///   when the arena resets. Global strings are heap-allocated with Arc refcounting.
195/// - **Variant**: Arc refcount increment (O(1), shares underlying data)
196/// - **Map**: Deep clone of the HashMap and all contained values
197/// - **Closure**: Deep clone of the Arc<[Value]> environment
198/// - **Channel**: Arc refcount increment (O(1), shares underlying sender/receiver)
199///
200/// # Safety
201/// The StackValue must contain valid data for its discriminant.
202#[inline]
203pub unsafe fn clone_stack_value(sv: &StackValue) -> StackValue {
204    unsafe {
205        match sv.slot0 {
206            DISC_INT | DISC_FLOAT | DISC_BOOL | DISC_QUOTATION => *sv,
207            DISC_STRING => {
208                // Deep copy: arena strings may become invalid, so always create a global string
209                let ptr = sv.slot1 as *const u8;
210                let len = sv.slot2 as usize;
211                debug_assert!(!ptr.is_null(), "String pointer is null");
212                // Read the string content without taking ownership
213                let slice = std::slice::from_raw_parts(ptr, len);
214                // Validate UTF-8 in debug builds, skip in release for performance
215                #[cfg(debug_assertions)]
216                let s = std::str::from_utf8(slice).expect("Invalid UTF-8 in string clone");
217                #[cfg(not(debug_assertions))]
218                let s = std::str::from_utf8_unchecked(slice);
219                // Clone to a new global string
220                let cloned = crate::seqstring::global_string(s.to_string());
221                let (new_ptr, new_len, new_cap, new_global) = cloned.into_raw_parts();
222                StackValue {
223                    slot0: DISC_STRING,
224                    slot1: new_ptr as u64,
225                    slot2: new_len as u64,
226                    slot3: new_cap as u64,
227                    slot4: if new_global { 1 } else { 0 },
228                }
229            }
230            DISC_VARIANT => {
231                use crate::value::VariantData;
232                let ptr = sv.slot1 as *const VariantData;
233                debug_assert!(!ptr.is_null(), "Variant pointer is null");
234                debug_assert!(
235                    (ptr as usize).is_multiple_of(std::mem::align_of::<VariantData>()),
236                    "Variant pointer is misaligned"
237                );
238                let arc = Arc::from_raw(ptr);
239                let cloned = Arc::clone(&arc);
240                std::mem::forget(arc);
241                StackValue {
242                    slot0: DISC_VARIANT,
243                    slot1: Arc::into_raw(cloned) as u64,
244                    slot2: 0,
245                    slot3: 0,
246                    slot4: 0,
247                }
248            }
249            DISC_MAP => {
250                // Deep clone the map
251                use crate::value::MapKey;
252                use std::collections::HashMap;
253                let ptr = sv.slot1 as *mut HashMap<MapKey, Value>;
254                debug_assert!(!ptr.is_null(), "Map pointer is null");
255                debug_assert!(
256                    (ptr as usize).is_multiple_of(std::mem::align_of::<HashMap<MapKey, Value>>()),
257                    "Map pointer is misaligned"
258                );
259                let boxed = Box::from_raw(ptr);
260                let cloned = boxed.clone();
261                std::mem::forget(boxed);
262                StackValue {
263                    slot0: DISC_MAP,
264                    slot1: Box::into_raw(cloned) as u64,
265                    slot2: 0,
266                    slot3: 0,
267                    slot4: 0,
268                }
269            }
270            DISC_CLOSURE => {
271                // The env is stored as Box<Arc<[Value]>>
272                let env_box_ptr = sv.slot2 as *mut Arc<[Value]>;
273                debug_assert!(!env_box_ptr.is_null(), "Closure env pointer is null");
274                debug_assert!(
275                    (env_box_ptr as usize).is_multiple_of(std::mem::align_of::<Arc<[Value]>>()),
276                    "Closure env pointer is misaligned"
277                );
278                let env_arc = &*env_box_ptr;
279                let cloned_env = Arc::clone(env_arc);
280                // Box the cloned Arc
281                let new_env_box = Box::new(cloned_env);
282                StackValue {
283                    slot0: DISC_CLOSURE,
284                    slot1: sv.slot1,
285                    slot2: Box::into_raw(new_env_box) as u64,
286                    slot3: 0,
287                    slot4: 0,
288                }
289            }
290            DISC_CHANNEL => {
291                // Arc refcount increment - O(1) clone
292                use crate::value::ChannelData;
293                let ptr = sv.slot1 as *const ChannelData;
294                debug_assert!(!ptr.is_null(), "Channel pointer is null");
295                let arc = Arc::from_raw(ptr);
296                let cloned = Arc::clone(&arc);
297                std::mem::forget(arc);
298                StackValue {
299                    slot0: DISC_CHANNEL,
300                    slot1: Arc::into_raw(cloned) as u64,
301                    slot2: 0,
302                    slot3: 0,
303                    slot4: 0,
304                }
305            }
306            _ => panic!("Invalid discriminant for clone: {}", sv.slot0),
307        }
308    }
309}
310
311/// Drop a StackValue, decrementing refcounts for heap types
312///
313/// # Safety
314/// The StackValue must contain valid data for its discriminant.
315#[inline]
316pub unsafe fn drop_stack_value(sv: StackValue) {
317    unsafe {
318        match sv.slot0 {
319            DISC_INT | DISC_FLOAT | DISC_BOOL | DISC_QUOTATION => {
320                // No heap allocation, nothing to drop
321            }
322            DISC_STRING => {
323                // Reconstruct SeqString and let it drop
324                use crate::seqstring::SeqString;
325                let ptr = sv.slot1 as *const u8;
326                let len = sv.slot2 as usize;
327                let capacity = sv.slot3 as usize;
328                let global = sv.slot4 != 0;
329                let _ = SeqString::from_raw_parts(ptr, len, capacity, global);
330                // SeqString::drop will free global strings, ignore arena strings
331            }
332            DISC_VARIANT => {
333                use crate::value::VariantData;
334                let _ = Arc::from_raw(sv.slot1 as *const VariantData);
335            }
336            DISC_MAP => {
337                use crate::value::MapKey;
338                use std::collections::HashMap;
339                let _ = Box::from_raw(sv.slot1 as *mut HashMap<MapKey, Value>);
340            }
341            DISC_CLOSURE => {
342                // Unbox and drop the Arc<[Value]>
343                let _ = Box::from_raw(sv.slot2 as *mut Arc<[Value]>);
344            }
345            DISC_CHANNEL => {
346                use crate::value::ChannelData;
347                let _ = Arc::from_raw(sv.slot1 as *const ChannelData);
348            }
349            _ => panic!("Invalid discriminant for drop: {}", sv.slot0),
350        }
351    }
352}
353
354// ============================================================================
355// Core Stack Operations
356// ============================================================================
357
358/// Push a value onto the stack
359///
360/// Stores the value at the current stack pointer and returns sp + 1.
361///
362/// # Safety
363/// Stack pointer must be valid and have room for the value.
364#[inline]
365pub unsafe fn push(stack: Stack, value: Value) -> Stack {
366    unsafe {
367        let sv = value_to_stack_value(value);
368        *stack = sv;
369        stack.add(1)
370    }
371}
372
373/// Push a StackValue directly onto the stack
374///
375/// # Safety
376/// Stack pointer must be valid and have room for the value.
377#[inline]
378pub unsafe fn push_sv(stack: Stack, sv: StackValue) -> Stack {
379    unsafe {
380        *stack = sv;
381        stack.add(1)
382    }
383}
384
385/// Pop a value from the stack
386///
387/// Returns (new_sp, value) where new_sp = sp - 1.
388///
389/// # Safety
390/// Stack must not be at base (must have at least one value).
391#[inline]
392pub unsafe fn pop(stack: Stack) -> (Stack, Value) {
393    unsafe {
394        let new_sp = stack.sub(1);
395        let sv = *new_sp;
396        (new_sp, stack_value_to_value(sv))
397    }
398}
399
400/// Pop a StackValue directly from the stack
401///
402/// # Safety
403/// Stack must not be at base and must have at least one value.
404#[inline]
405pub unsafe fn pop_sv(stack: Stack) -> (Stack, StackValue) {
406    unsafe {
407        let new_sp = stack.sub(1);
408        let sv = *new_sp;
409        (new_sp, sv)
410    }
411}
412
413/// Pop two values from the stack (for binary operations)
414///
415/// Returns (new_sp, a, b) where a was below b on stack.
416/// Stack effect: ( a b -- ) returns (a, b)
417///
418/// # Safety
419/// Stack must have at least two values.
420#[inline]
421pub unsafe fn pop_two(stack: Stack, _op_name: &str) -> (Stack, Value, Value) {
422    unsafe {
423        let (sp, b) = pop(stack);
424        let (sp, a) = pop(sp);
425        (sp, a, b)
426    }
427}
428
429/// Pop three values from the stack (for ternary operations)
430///
431/// # Safety
432/// Stack must have at least three values.
433#[inline]
434pub unsafe fn pop_three(stack: Stack, _op_name: &str) -> (Stack, Value, Value, Value) {
435    unsafe {
436        let (sp, c) = pop(stack);
437        let (sp, b) = pop(sp);
438        let (sp, a) = pop(sp);
439        (sp, a, b, c)
440    }
441}
442
443/// Peek at the top value without removing it
444///
445/// # Safety
446/// Stack must have at least one value.
447#[inline]
448pub unsafe fn peek(stack: Stack) -> Value {
449    unsafe {
450        let sv = *stack.sub(1);
451        // Don't consume - need to clone for heap types
452        stack_value_to_value(clone_stack_value(&sv))
453    }
454}
455
456/// Peek at the raw StackValue without removing it
457///
458/// # Safety
459/// Stack must have at least one value.
460#[inline]
461pub unsafe fn peek_sv(stack: Stack) -> StackValue {
462    unsafe { *stack.sub(1) }
463}
464
465/// Check if stack is empty (at base pointer)
466/// Note: With tagged stack, we need to compare against base, not null
467#[inline]
468pub fn is_empty(_stack: Stack) -> bool {
469    // For now, assume stack is never truly empty in valid programs
470    // The caller should track base pointer if needed
471    false
472}
473
474// ============================================================================
475// FFI Stack Operations
476// ============================================================================
477
478/// Duplicate the top value on the stack: ( a -- a a )
479///
480/// # Safety
481/// Stack must have at least one value.
482#[unsafe(no_mangle)]
483pub unsafe extern "C" fn patch_seq_dup(stack: Stack) -> Stack {
484    unsafe {
485        let sv = peek_sv(stack);
486        let cloned = clone_stack_value(&sv);
487        push_sv(stack, cloned)
488    }
489}
490
491/// Drop the top value from the stack: ( a -- )
492///
493/// # Safety
494/// Stack must have at least one value.
495#[inline]
496pub unsafe fn drop_top(stack: Stack) -> Stack {
497    unsafe {
498        let (new_sp, sv) = pop_sv(stack);
499        drop_stack_value(sv);
500        new_sp
501    }
502}
503
504/// Alias for drop to avoid LLVM keyword conflicts
505///
506/// # Safety
507/// Stack must have at least one value.
508#[unsafe(no_mangle)]
509pub unsafe extern "C" fn patch_seq_drop_op(stack: Stack) -> Stack {
510    unsafe { drop_top(stack) }
511}
512
513/// Push an arbitrary Value onto the stack (for LLVM codegen)
514///
515/// # Safety
516/// Stack pointer must be valid and have room for the value.
517#[allow(improper_ctypes_definitions)]
518#[unsafe(no_mangle)]
519pub unsafe extern "C" fn patch_seq_push_value(stack: Stack, value: Value) -> Stack {
520    unsafe { push(stack, value) }
521}
522
523/// Swap the top two values: ( a b -- b a )
524///
525/// # Safety
526/// Stack must have at least two values.
527#[unsafe(no_mangle)]
528pub unsafe extern "C" fn patch_seq_swap(stack: Stack) -> Stack {
529    unsafe {
530        let ptr_b = stack.sub(1);
531        let ptr_a = stack.sub(2);
532        let a = *ptr_a;
533        let b = *ptr_b;
534        *ptr_a = b;
535        *ptr_b = a;
536        stack
537    }
538}
539
540/// Copy the second value to the top: ( a b -- a b a )
541///
542/// # Safety
543/// Stack must have at least two values.
544#[unsafe(no_mangle)]
545pub unsafe extern "C" fn patch_seq_over(stack: Stack) -> Stack {
546    unsafe {
547        let sv_a = *stack.sub(2);
548        let cloned = clone_stack_value(&sv_a);
549        push_sv(stack, cloned)
550    }
551}
552
553/// Rotate the top three values: ( a b c -- b c a )
554///
555/// # Safety
556/// Stack must have at least three values.
557#[unsafe(no_mangle)]
558pub unsafe extern "C" fn patch_seq_rot(stack: Stack) -> Stack {
559    unsafe {
560        let ptr_c = stack.sub(1);
561        let ptr_b = stack.sub(2);
562        let ptr_a = stack.sub(3);
563        let a = *ptr_a;
564        let b = *ptr_b;
565        let c = *ptr_c;
566        *ptr_a = b;
567        *ptr_b = c;
568        *ptr_c = a;
569        stack
570    }
571}
572
573/// Remove the second value: ( a b -- b )
574///
575/// # Safety
576/// Stack must have at least two values.
577#[unsafe(no_mangle)]
578pub unsafe extern "C" fn patch_seq_nip(stack: Stack) -> Stack {
579    unsafe {
580        let ptr_b = stack.sub(1);
581        let ptr_a = stack.sub(2);
582        let a = *ptr_a;
583        let b = *ptr_b;
584        drop_stack_value(a);
585        *ptr_a = b;
586        stack.sub(1)
587    }
588}
589
590/// Copy top value below second value: ( a b -- b a b )
591///
592/// # Safety
593/// Stack must have at least two values.
594#[unsafe(no_mangle)]
595pub unsafe extern "C" fn patch_seq_tuck(stack: Stack) -> Stack {
596    unsafe {
597        let ptr_b = stack.sub(1);
598        let ptr_a = stack.sub(2);
599        let a = *ptr_a;
600        let b = *ptr_b;
601        let b_clone = clone_stack_value(&b);
602        *ptr_a = b;
603        *ptr_b = a;
604        push_sv(stack, b_clone)
605    }
606}
607
608/// Duplicate top two values: ( a b -- a b a b )
609///
610/// # Safety
611/// Stack must have at least two values.
612#[unsafe(no_mangle)]
613pub unsafe extern "C" fn patch_seq_2dup(stack: Stack) -> Stack {
614    unsafe {
615        let sv_a = *stack.sub(2);
616        let sv_b = *stack.sub(1);
617        let a_clone = clone_stack_value(&sv_a);
618        let b_clone = clone_stack_value(&sv_b);
619        let sp = push_sv(stack, a_clone);
620        push_sv(sp, b_clone)
621    }
622}
623
624/// Drop top three values: ( a b c -- )
625///
626/// # Safety
627/// Stack must have at least three values.
628#[unsafe(no_mangle)]
629pub unsafe extern "C" fn patch_seq_3drop(stack: Stack) -> Stack {
630    unsafe {
631        let (sp, sv_c) = pop_sv(stack);
632        let (sp, sv_b) = pop_sv(sp);
633        let (sp, sv_a) = pop_sv(sp);
634        drop_stack_value(sv_c);
635        drop_stack_value(sv_b);
636        drop_stack_value(sv_a);
637        sp
638    }
639}
640
641/// Pick: Copy the nth value to the top
642/// ( ... xn ... x1 x0 n -- ... xn ... x1 x0 xn )
643///
644/// # Safety
645/// Stack must have at least n+1 values (plus the index value).
646///
647/// # Panics
648/// - If the top value is not an Int
649/// - If n is negative
650/// - If n exceeds the current stack depth
651#[unsafe(no_mangle)]
652pub unsafe extern "C" fn patch_seq_pick_op(stack: Stack) -> Stack {
653    unsafe {
654        // Get n from top of stack
655        let (sp, n_val) = pop(stack);
656        let n_raw = match n_val {
657            Value::Int(i) => i,
658            _ => panic!("pick: expected Int"),
659        };
660
661        // Bounds check: n must be non-negative
662        if n_raw < 0 {
663            panic!("pick: index cannot be negative (got {})", n_raw);
664        }
665        let n = n_raw as usize;
666
667        // Check stack depth to prevent out-of-bounds access
668        let base = get_stack_base();
669        let depth = (sp as usize - base as usize) / std::mem::size_of::<StackValue>();
670        if n >= depth {
671            panic!(
672                "pick: index {} exceeds stack depth {} (need at least {} values)",
673                n,
674                depth,
675                n + 1
676            );
677        }
678
679        // Get the value at depth n (0 = top after popping n)
680        let sv = *sp.sub(n + 1);
681        let cloned = clone_stack_value(&sv);
682        push_sv(sp, cloned)
683    }
684}
685
686/// Roll: Rotate n+1 items, bringing the item at depth n to the top
687/// ( x_n x_(n-1) ... x_1 x_0 n -- x_(n-1) ... x_1 x_0 x_n )
688///
689/// # Safety
690/// Stack must have at least n+1 values (plus the index value).
691///
692/// # Panics
693/// - If the top value is not an Int
694/// - If n is negative
695/// - If n exceeds the current stack depth
696#[unsafe(no_mangle)]
697pub unsafe extern "C" fn patch_seq_roll(stack: Stack) -> Stack {
698    unsafe {
699        // Get n from top of stack
700        let (sp, n_val) = pop(stack);
701        let n_raw = match n_val {
702            Value::Int(i) => i,
703            _ => panic!("roll: expected Int"),
704        };
705
706        // Bounds check: n must be non-negative
707        if n_raw < 0 {
708            panic!("roll: index cannot be negative (got {})", n_raw);
709        }
710        let n = n_raw as usize;
711
712        if n == 0 {
713            return sp;
714        }
715        if n == 1 {
716            return patch_seq_swap(sp);
717        }
718        if n == 2 {
719            return patch_seq_rot(sp);
720        }
721
722        // Check stack depth to prevent out-of-bounds access
723        let base = get_stack_base();
724        let depth = (sp as usize - base as usize) / std::mem::size_of::<StackValue>();
725        if n >= depth {
726            panic!(
727                "roll: index {} exceeds stack depth {} (need at least {} values)",
728                n,
729                depth,
730                n + 1
731            );
732        }
733
734        // General case: save item at depth n, shift others, put saved at top
735        let src_ptr = sp.sub(n + 1);
736        let saved = *src_ptr;
737
738        // Shift items down: memmove from src+1 to src, n items
739        std::ptr::copy(src_ptr.add(1), src_ptr, n);
740
741        // Put saved item at top (sp - 1)
742        *sp.sub(1) = saved;
743
744        sp
745    }
746}
747
748/// Clone a stack segment
749///
750/// Clones `count` StackValues from src to dst, handling refcounts.
751///
752/// # Safety
753/// Both src and dst must be valid stack pointers with sufficient space for count values.
754pub unsafe fn clone_stack_segment(src: Stack, dst: Stack, count: usize) {
755    unsafe {
756        for i in 0..count {
757            let sv = *src.sub(count - i);
758            let cloned = clone_stack_value(&sv);
759            *dst.add(i) = cloned;
760        }
761    }
762}
763
764// ============================================================================
765// Coroutine-Local Stack Base Tracking (for spawn)
766// ============================================================================
767//
768// IMPORTANT: We use May's coroutine_local! instead of thread_local! because
769// May coroutines can migrate between OS threads. Using thread_local would cause
770// STACK_BASE to be lost when a coroutine is moved to a different thread.
771
772use std::cell::Cell;
773
774// Use coroutine-local storage that moves with the coroutine
775may::coroutine_local!(static STACK_BASE: Cell<usize> = Cell::new(0));
776
777/// Set the current strand's stack base (called at strand entry)
778///
779/// # Safety
780/// Base pointer must be a valid stack pointer for the current strand.
781#[unsafe(no_mangle)]
782pub unsafe extern "C" fn patch_seq_set_stack_base(base: Stack) {
783    STACK_BASE.with(|cell| {
784        cell.set(base as usize);
785    });
786}
787
788/// Get the current strand's stack base
789#[inline]
790pub fn get_stack_base() -> Stack {
791    STACK_BASE.with(|cell| cell.get() as *mut StackValue)
792}
793
794/// Clone the current stack for spawning a child strand
795///
796/// Allocates a new stack buffer and copies all values from the current stack.
797/// Returns a pointer to the first value in the new stack (like Stack convention).
798///
799/// # Safety
800/// - Current stack must have a valid base set via set_stack_base
801/// - sp must point to a valid position within the current stack
802#[unsafe(no_mangle)]
803pub unsafe extern "C" fn clone_stack(sp: Stack) -> Stack {
804    unsafe {
805        let (new_sp, _base) = clone_stack_with_base(sp);
806        new_sp
807    }
808}
809
810/// Clone the current stack for spawning, returning both base and sp.
811///
812/// This is used by spawn to create a copy of the parent's stack for the child strand.
813/// Returns (new_sp, new_base) so the spawn mechanism can set STACK_BASE for the child.
814///
815/// # Safety
816/// Current stack must have a valid base set via set_stack_base and sp must point to a valid position.
817pub unsafe fn clone_stack_with_base(sp: Stack) -> (Stack, Stack) {
818    let base = get_stack_base();
819    if base.is_null() {
820        panic!("clone_stack: stack base not set");
821    }
822
823    // Calculate depth (number of values on stack)
824    let depth = unsafe { sp.offset_from(base) as usize };
825
826    if depth == 0 {
827        // Empty stack - still need to allocate a buffer
828        use crate::tagged_stack::{DEFAULT_STACK_CAPACITY, TaggedStack};
829        let new_stack = TaggedStack::new(DEFAULT_STACK_CAPACITY);
830        let new_base = new_stack.base;
831        std::mem::forget(new_stack); // Don't drop - caller owns memory
832        return (new_base, new_base);
833    }
834
835    // Allocate new stack with capacity for at least the current depth
836    use crate::tagged_stack::{DEFAULT_STACK_CAPACITY, TaggedStack};
837    let capacity = depth.max(DEFAULT_STACK_CAPACITY);
838    let new_stack = TaggedStack::new(capacity);
839    let new_base = new_stack.base;
840    std::mem::forget(new_stack); // Don't drop - caller owns memory
841
842    // Clone all values from base to sp
843    unsafe {
844        for i in 0..depth {
845            let sv = &*base.add(i);
846            let cloned = clone_stack_value(sv);
847            *new_base.add(i) = cloned;
848        }
849    }
850
851    // Return both sp and base
852    unsafe { (new_base.add(depth), new_base) }
853}
854
855// ============================================================================
856// Short Aliases for Internal/Test Use
857// ============================================================================
858
859pub use patch_seq_2dup as two_dup;
860pub use patch_seq_3drop as three_drop;
861pub use patch_seq_dup as dup;
862pub use patch_seq_nip as nip;
863pub use patch_seq_over as over;
864pub use patch_seq_pick_op as pick;
865pub use patch_seq_roll as roll;
866pub use patch_seq_rot as rot;
867pub use patch_seq_swap as swap;
868pub use patch_seq_tuck as tuck;
869
870// ============================================================================
871// Stack Allocation Helpers
872// ============================================================================
873
874/// Allocate a new stack with default capacity.
875/// Returns a pointer to the base of the stack (where first push goes).
876///
877/// # Note
878/// The returned stack is allocated but not tracked.
879/// The memory will be leaked when the caller is done with it.
880/// This is used for temporary stacks in quotation calls and tests.
881pub fn alloc_stack() -> Stack {
882    use crate::tagged_stack::TaggedStack;
883    let stack = TaggedStack::with_default_capacity();
884    let base = stack.base;
885    std::mem::forget(stack); // Don't drop - caller owns memory
886    base
887}
888
889/// Allocate a new test stack and set it as the stack base
890/// This is used in tests that need clone_stack to work
891#[cfg(test)]
892pub fn alloc_test_stack() -> Stack {
893    let stack = alloc_stack();
894    unsafe { patch_seq_set_stack_base(stack) };
895    stack
896}
897
898/// Dump all values on the stack (for REPL debugging)
899///
900/// Prints all stack values in a readable format, then clears the stack.
901/// Returns the stack base (empty stack).
902///
903/// # Safety
904/// - Stack base must have been set via set_stack_base
905/// - sp must be a valid stack pointer
906/// - All stack values between base and sp must be valid
907#[unsafe(no_mangle)]
908pub unsafe extern "C" fn patch_seq_stack_dump(sp: Stack) -> Stack {
909    let base = get_stack_base();
910    if base.is_null() {
911        eprintln!("[stack.dump: base not set]");
912        return sp;
913    }
914
915    let depth = (sp as usize - base as usize) / std::mem::size_of::<StackValue>();
916
917    if depth == 0 {
918        println!("[]");
919    } else {
920        print!("[");
921        for i in 0..depth {
922            if i > 0 {
923                print!(", ");
924            }
925            unsafe {
926                let sv = *base.add(i);
927                print_stack_value(&sv);
928            }
929        }
930        println!("]");
931
932        // Drop all heap-allocated values to prevent memory leaks
933        for i in 0..depth {
934            unsafe {
935                let sv = *base.add(i);
936                drop_stack_value(sv);
937            }
938        }
939    }
940
941    // Return base (empty stack)
942    base
943}
944
945/// Print a stack value in a readable format
946///
947/// # Safety Requirements
948/// The StackValue must be valid and not previously dropped. For strings,
949/// the pointer (slot1) must point to valid, readable memory of length slot2.
950/// This is guaranteed when called from stack.dump on freshly computed values.
951fn print_stack_value(sv: &StackValue) {
952    match sv.slot0 {
953        DISC_INT => print!("{}", sv.slot1 as i64),
954        DISC_FLOAT => print!("{}", f64::from_bits(sv.slot1)),
955        DISC_BOOL => print!("{}", if sv.slot1 != 0 { "true" } else { "false" }),
956        DISC_STRING => {
957            let ptr = sv.slot1 as *const u8;
958            let len = sv.slot2 as usize;
959            // Safety: We trust the stack value is valid. The pointer was allocated
960            // by SeqString and hasn't been freed yet (we print before dropping).
961            // Additional defensive checks for null/zero-length.
962            if ptr.is_null() || len == 0 {
963                print!("\"\"");
964            } else if len > 10_000_000 {
965                // Sanity check: reject unreasonably large strings (likely corruption)
966                print!("<string:invalid length {}>", len);
967            } else {
968                unsafe {
969                    let slice = std::slice::from_raw_parts(ptr, len);
970                    if let Ok(s) = std::str::from_utf8(slice) {
971                        print!("\"{}\"", s);
972                    } else {
973                        print!("<string:{} bytes, non-utf8>", len);
974                    }
975                }
976            }
977        }
978        DISC_VARIANT => print!("<variant>"),
979        DISC_MAP => print!("<map>"),
980        DISC_QUOTATION => print!("<quotation>"),
981        DISC_CLOSURE => print!("<closure>"),
982        DISC_CHANNEL => print!("<channel>"),
983        _ => print!("<unknown:{}>", sv.slot0),
984    }
985}
986
987/// Macro to create a test stack
988#[macro_export]
989macro_rules! test_stack {
990    () => {{
991        use $crate::tagged_stack::StackValue;
992        static mut BUFFER: [StackValue; 256] = unsafe { std::mem::zeroed() };
993        unsafe { BUFFER.as_mut_ptr() }
994    }};
995}
seq_runtime/stack.rs

seq_runtime/
stack.rs
