1 files changed, 144 insertions, 0 deletions
diff --git a/bytecode/src/heap.rs b/bytecode/src/heap.rs
new file mode 100644
index 0000000..f1b9d81
--- /dev/null
+++ b/bytecode/src/heap.rs
@@ -0,0 +1,144 @@
+use crate::value::Value;
+use std::error::Error;
+
+pub const NUM_LOCALS: usize = 8;
+
+pub struct Heap {
+    pub buf: Vec<u64>,
+    free_ptr: usize,
+    last_live: usize,
+    pub locals: [Value; NUM_LOCALS],
+}
+
+impl Heap {
+    pub fn new() -> Heap {
+        Heap {
+            buf: Vec::new(),
+            free_ptr: 0,
+            last_live: 0,
+            locals: [Value(0); NUM_LOCALS],
+        }
+    }
+
+    fn forwarded(&self, p: usize) -> bool {
+        let Some(q) = Value(self.buf[p]).to_pointer() else {
+            return false;
+        };
+        return (self.free_ptr < self.buf.len() / 2) == (q < self.buf.len() / 2);
+    }
+
+    fn alloc_size(&self, p: usize) -> usize {
+        usize::try_from(self.buf[p - 1] >> 1).expect("using 32 bits in 2024 LULW")
+    }
+
+    fn simple_alloc(&mut self, size: usize) -> usize {
+        self.buf[self.free_ptr] = u64::try_from(size).expect("how even??") << 1;
+        let p = self.free_ptr + 1;
+        self.free_ptr += size + 1;
+        p
+    }
+
+    fn process_gc_value(&mut self, val: Value) -> Value {
+        let Some(p) = val.to_pointer() else {
+            return val;
+        };
+        if self.forwarded(p) {
+            return Value(self.buf[p]);
+        }
+
+        let size = self.alloc_size(p);
+
+        // Allocate space in the new buffer.
+        let q = self.simple_alloc(size);
+
+        // Write forwarding pointer.
+        let first_val = Value(self.buf[p]);
+        self.buf[p] = Value::from_pointer(q).repr();
+
+        // Copy values, recursively modifying pointers.
+        self.buf[q] = self.process_gc_value(first_val).repr();
+        for i in 1..size {
+            self.buf[q + i] = self.process_gc_value(Value(self.buf[p + i])).repr();
+        }
+
+        Value::from_pointer(q)
+    }
+
+    fn collect_garbage(&mut self) {
+        if self.free_ptr < 2 * self.last_live {
+            return;
+        }
+
+        // Swap the heaps.
+        if self.free_ptr < self.buf.len() / 2 {
+            self.free_ptr = self.buf.len() / 2;
+        } else {
+            self.free_ptr = 0;
+        }
+
+        for i in 0..self.locals.len() {
+            self.locals[i] = self.process_gc_value(self.locals[i]);
+        }
+        if self.free_ptr < self.buf.len() / 2 {
+            self.last_live = self.free_ptr;
+        } else {
+            self.last_live = self.free_ptr - self.buf.len() / 2;
+        }
+    }
+
+    fn more_space(&mut self, size_hint: usize) {
+        let current_size = self.buf.len() / 2;
+        let mut new_size = current_size * 2;
+        if new_size == 0 {
+            new_size = 1;
+        }
+        while new_size <= current_size + size_hint {
+            new_size *= 2;
+        }
+
+        let active;
+        if self.free_ptr < current_size {
+            active = &self.buf[..current_size];
+        } else {
+            active = &self.buf[current_size..];
+            self.free_ptr -= current_size;
+        }
+
+        let mut new_buf = Vec::with_capacity(new_size * 2);
+        new_buf.extend_from_slice(active);
+        new_buf.resize(new_size * 2, 0);
+        self.buf = new_buf;
+    }
+
+    pub fn alloc(&mut self, size: i64) -> Result<usize, Box<dyn Error>> {
+        if size <= 0 {
+            return Err(Box::from("alloc of zero size"));
+        }
+        let usize = usize::try_from(size).expect("32 bits in 2024 LULW");
+        self.collect_garbage();
+        if self.free_ptr + usize + 1 >= self.buf.len() / 2 {
+            self.more_space(usize);
+        }
+
+        let p = self.simple_alloc(usize::try_from(size).expect("using 32 bits in 2024 LULW"));
+        for i in 0..usize {
+            self.buf[p + i] = 0;
+        }
+        Ok(p)
+    }
+
+    pub fn peek(&self, p: usize) -> Result<Value, Box<dyn Error>> {
+        if p >= self.buf.len() {
+            return Err(Box::from("peek: out of range"));
+        }
+        Ok(Value(self.buf[p]))
+    }
+
+    pub fn poke(&mut self, p: usize, val: Value) -> Result<(), Box<dyn Error>> {
+        if p >= self.buf.len() {
+            return Err(Box::from("poke: out of range"));
+        }
+        self.buf[p] = val.repr();
+        Ok(())
+    }
+}