Ridgun

The language itself: a compiler that compiles itself, the stable project tool, the specification and the book

FR-COMP-002-compiled-memory-management-cmm.md58 lines · 5.3 KBRaw

1	---
2	id: FR-COMP-002
3	title: Ridgun Memory Management (RMM) — RMM1 (CMM Linear & Conditional) and RMM2 (Assignment & Cascaded Structure Counting)
4	status: implemented
5	priority: must
6	created: 2026-10-19
7	updated: 2026-10-19
8	depends_on: []
9	verified_by: []
10	---
11	# FR-COMP-002 — Ridgun Memory Management (RMM): RMM1 (CMM) and RMM2
12
13	## Statement
14	The `ridgunc` native compiler SHALL manage heap memory deterministically without a tracing Garbage Collector (GC) through Ridgun Memory Management (RMM), structured into two active policies (with RMM3 reserved for a future aggressive optimization pass):
15	1. `RMM1` — Compiled Memory Management (CMM Linear + Conditional):
16	- For statically known control flow over non-nested bindings, the compiler determines the exact last-use statement of every local variable at compile time, emitting `rg_cmm_move` on returned variables, unconditional `rg_cmm_drop` when no compile-time may-aliases remain live, and Conditional CMM pointer-identity guards (`rg_cmm_drop_unless(&mut lv_x, &[&lv_c, ...])`, i.e. `if ptr(x) != ptr(c) { free(x) }`) when branching aliases (`c = choose_list cond a b`) have overlapping lifetimes.
17	2. `RMM2` — Assignment & Cascaded Structure Counting (Anonymous Functions, Nested Containers & Multi-thread):
18	- For dynamic control flow (anonymous functions / higher-order callbacks), nested data structures (`xs = [a, b, ..., z]`, `xs[3] = a`), and multi-threaded sharing:
19	- Primitive scalars (`Int`, `Real`, `Bool`, `Unit`) SHALL NOT be reference-counted.
20	- Heap structures (`List`, `Tuple`, `Adt`, `Tensor`, `Str`) SHALL carry their own counter (`rc`), incremented (`+1`) on variable or slot assignment (`b = a`, `xs[3] = a`), untouched (`+0`) on read-only borrows, moved without decrement on `return`, and decremented (`-1`) at variable death (when not returned).
21	- When a parent structure's counter reaches `0`, it SHALL be destroyed and SHALL decrement (`-1`) each of its direct child structures one by one, recursively freeing any child whose counter reaches `0`.
22
23	## Rationale
24	Pure static liveness (`RMM1` / CMM) eliminates runtime reference counting completely when the execution graph and variable relationships are statically visible at compile time (including static branching such as `c = choose_list cond a b` via pointer-identity guards `ptr(x) != ptr(c)`). When anonymous functions make control flow opaque at compile time or when structures nest inside other structures (`xs = [a..z]`, `xs[3] = a`), `RMM2` provides a unified, leak-free, and use-after-free-proof mechanism across both single-threaded and multi-threaded execution without touching counters on read-only operations or function returns.
25
26	## Functional Specification
27
28	### 1. Policy `RMM1`: Linear & Conditional CMM (`rg_cmm_move`, `rg_cmm_drop`, `rg_cmm_drop_unless`)
29	- For every statement sequence (`EBlock`, `EWhere`, `FnCase`), the compiler SHALL compute the static last-use statement of each local variable `v` and build the compile-time Ancestor May-Alias Table (`RCmmAlias`).
30	- Immediately after the statement containing the last use of any local variable `x`:
31	- Linear CMM (`LivePeers(x) == []`): If no other variable sharing an ancestor with `x` is live after that statement, the compiler SHALL emit `rg_cmm_drop(&mut lv_x)`.
32	- Conditional CMM (`LivePeers(x) == [y_1, ..., y_k]`): If variables `y_1, ..., y_k` sharing a compile-time ancestor with `x` remain live after that statement, the compiler SHALL emit `rg_cmm_drop_unless(&mut lv_x, &[&lv_y1, ...])` (`if ptr(x) != ptr(y_1) && ... { free(x) }`).
33	- On `return v`, the compiler SHALL emit `rg_cmm_move(&mut lv_v)` so the returned variable is transferred without deallocation.
34
35	### 2. Canonical `choose_list` Lifecycle Trace (`RMM1`)
36	Given:
37	```ridgun
38	a = make_a ()
39	b = make_b ()
40	c = choose_list cond a b
41	print_list a
42	consume_list c
43	```
44	- After `c = choose_list cond a b`: `b` has no further uses while `c` is live $\rightarrow$ `rg_cmm_drop_unless(&mut lv_b, &[&lv_c])`.
45	- After `print_list a`: `a` has no further uses while `c` is live $\rightarrow$ `rg_cmm_drop_unless(&mut lv_a, &[&lv_c])`.
46	- After `consume_list c`: `c` has no further uses and no live peers $\rightarrow$ unconditional `rg_cmm_drop(&mut lv_c)`.
47
48	### 3. Policy `RMM2`: Assignment & Cascaded Structure Counting (`CmmBox<T>`)
49	- Primitive types (`Int`, `Real`, `Bool`, `Unit`) are unboxed stack values with no counter.
50	- Heap structures (`CmmBox<T>`) start with `links = 1` upon allocation:
51	- Assigning `b = a` or `xs[3] = a` (or inserting `a` into `xs = [a, b, ..., z]`) increments `a`'s link count by `+1`.
52	- Returning a variable (`return x`) moves `x` without decrementing its link count.
53	- Dropping a non-returned variable decrements its link count by `-1`; when a parent container's link count reaches `0`, it frees the container and decrements (`-1`) each child element one by one, freeing any child whose count reaches `0`.
54
55	## Acceptance Criteria
56	- AC1: `ridgunc` implements `RMM1` (CMM liveness + `RCmmAlias` conditional pointer-identity guards) and `RMM2` (`CmmBox<T>` assignment & cascaded child teardown).
57	- AC2: `cmm_trace_elegir True` produces `(2, 1, 1, 0, 1, 1)`, `cmm_trace_elegir False` produces `(2, 2, 1, 0, 1, 1)`, and `cmm_trace_cascada` passes in `src/test/ridgun/test_core_language.rg`.
58	- AC3: Self-hosted Stage 1 and Stage 2 bootstrap of `ridgunc` and `stable` and all 4 Ridgun test suites pass with 0 errors.