rt: gc_drops finalizes a droppable value that reaches itself (a cycle, or a drop capturing its own value), one per collection, each once; before, each waited for the other forever; spec 6.15.3, drop_gc_cycle.zc, drop_gc_self_capture.zc, design doc lists what landed

5 files changed, 42 insertions, 5 deletions

diff --git a/docs/SPEC.md b/docs/SPEC.md
index 1aa135a..1b07ae0 100644
--- a/docs/SPEC.md
+++ b/docs/SPEC.md
@@ -995,7 +995,7 @@ rt.put_n(*heap(15).drop(fn() { rt.put_s(" bye "); rt.put_n(*this); }));   // 15
 let guard = drop(heap(0), fn() { unlock(); });                            // unlocks at block end
 ```
 6.15.2 a value dies, and its drop runs, where 6.5 frees it: at the end of its owner's block or an early exit, at `rt.free`, when its owner is reassigned (6.8.5), or with its container, whose drop runs before its children's. a new value assigned to the owner can have its own drop set on the next statement, like a declaration's. a value with a drop that nothing holds (a temporary) dies at the end of its full statement, with hint: value with drop is never bound; it drops at the end of this statement. an owned local with a drop is not "never used" (6.5.2): holding it is its use.
-6.15.3 the collector runs the drop of an unreachable value after its sweep, never during it, and at most once: the value is kept until a later collection finds it unreachable again. a drop that stores `this` somewhere reachable keeps the value alive, and its drop does not run again. there is no collection at exit, so collector-owned values are not dropped then. a freed block forgets its drop, so a block reused at the same address has none.
+6.15.3 the collector runs the drop of an unreachable value after its sweep, never during it, and at most once: the value is kept until a later collection finds it unreachable again. a drop that stores `this` somewhere reachable keeps the value alive, and its drop does not run again. among unreachable values, one reached by another waits until that one has dropped (parent first); values that reach each other (a cycle, or a drop that captures its own value) have nothing outside to drop first, so one of them drops per collection, in an unspecified order, each once. there is no collection at exit, so collector-owned values are not dropped then. a freed block forgets its drop, so a block reused at the same address has none.
 6.15.4 copying a value with a drop into an actor message is error: x: has drop and can't be copied into a message. `spawn` copies the whole vm into the worker process, so both processes hold an owned value that is live at the call and both run its drop: hint: x: has drop and is live at spawn; the worker's copy drops it too.
 6.15.5 nothing moves out of a value with a drop, whose drop may need what it holds. a field or element of it is a borrowed projection and can't be given away (error: a borrowed projection cannot transfer ownership; transfer its owner), and `pop` on an array that has a drop, or on an array field of a value with a drop, is error: a: can't move out of a value with drop. there is no `take`. borrowing a child is fine, and an array without a drop hands out its elements with `pop` as before, drops and all.
 
diff --git a/docs/design/destructors.md b/docs/design/destructors.md
index 0691228..7d0c950 100644
--- a/docs/design/destructors.md
+++ b/docs/design/destructors.md
@@ -179,4 +179,5 @@ untyped `rt.new(n)` blocks take a drop like any other value, so there is no sepa
 - `gc_drops`: drops of marked values are marked (to a fixpoint); each unmarked value whose drop hasn't run gets `F_FINAL` and is kept with what it reaches; a candidate reached by another candidate waits for a later collection, so parents drop before children.
 - o3: `rt.o3_enter`/`rt.o3_leave` around `o3 { }` blocks and calls from normal code into o3 functions; `gc` inside sets `gc_pending`, the outermost leave runs it.
 - compiler: `heap(e)`, the three drop forms (a closure there gets `this`), the struct `drop` method as type drop (`set_tdrop` after `new(T)` and `heap`), set-once and set-early on locals, temporaries held in a hidden slot until the statement ends with a hint, the actor `send` check, the o3 errors.
-- not yet: reassigning an owner that still holds a value (still error 6.8.5, not the free-with-hint), the no-move-out-of-a-droppable rule, the spawn hint, memreport's `(drop)` marker, `break`/`continue` out of an `o3 { }` block (they skip `o3_leave`), o3 methods called from normal code through a method call, and a cycle of unreachable droppable values (each reaches the other, so neither is finalized).
+- since: reassigning an `m` owner frees the old value with a hint (6.8.5; `reassign_free` in analyzer.zc, which frees without freevar's clearing store, since a captured local's slot holds its cell); `pop` on an array with a drop, or an array field of one, is refused (6.15.5; fields were already borrowed projections); the spawn hint on `x.spawn()` of a mailbox struct (`spawn_hint`); memreport's `(drop)` marker; `break`/`continue` out of an `o3 { }` block call `o3_leave` for each block they leave (`lpo3`, the depth each loop began at); an o3 receiver method called from normal code enters and leaves the region (`methcall`); a candidate that reaches itself in `gc_drops` (`F_CYCLE`, a cycle or a drop capturing its value) drops now, one per collection.
+- not yet: first users (file descriptors in `std.Host`, processes in `actor.zc`).
diff --git a/src/runtime/rt.zc b/src/runtime/rt.zc
index 3d448b0..906e56a 100644
--- a/src/runtime/rt.zc
+++ b/src/runtime/rt.zc
@@ -427,7 +427,7 @@ const int F_SHARE = 8;
 // p[-4] bits for drops (docs/design/destructors.md): the value has a drop in the side
 // table (dtab), its drop has run (it never runs again), and the collector found it
 // unreachable and runs its drop once the sweep is over.
-const int F_HASDROP = 16, F_DROPPED = 32, F_FINAL = 64;
+const int F_HASDROP = 16, F_DROPPED = 32, F_FINAL = 64, F_CYCLE = 128;	// F_CYCLE: during gc_drops only, a candidate its own contents reach
 int o3_depth, gc_pending;
 // flags live in these bits; the size class is above them.
 const int F_LOW = 65535;
@@ -1415,7 +1415,8 @@ int o3_leave() {
 // the collector's part, between mark and sweep. the drops of live values are kept;
 // an unreachable value with a drop that hasn't run is kept for one more cycle and
 // flagged F_FINAL, unless another such value reaches it (its parent drops first and
-// it waits for a later collection). nothing runs user code here.
+// it waits for a later collection) and it doesn't reach itself (a cycle drops one
+// value per collection). nothing runs user code here.
 int gc_drops() {
 	int i, again = 1; word k;
 	while (again) {
@@ -1436,6 +1437,7 @@ int gc_drops() {
 			k[-4] = k[-4] | F_FINAL;
 			markrange(k, k + k[-5] - HDR); mark(dtab[i * 3 + 1] - 1); mark(dtab[i * 3 + 2] - 1);
 			drain();
+			if ((k[-4] & 7) != 1) k[-4] = k[-4] | F_CYCLE;	// what it reaches (or its drop) reaches it back: a cycle
 		}
 		i++;
 	}
@@ -1443,7 +1445,11 @@ int gc_drops() {
 	while (i < dt_cap) {
 		k = dtab[i * 3];
 		if (k > 1 && (k[-4] & F_FINAL)) {
-			if ((k[-4] & 7) == 1) mark(k); else k[-4] = k[-4] & ~F_FINAL;	// reached from another candidate: later
+			// reached from another candidate: later. one in a cycle has nothing outside it
+			// to drop first, so it drops now (it is marked, so kept), and the rest of the
+			// cycle in later collections, one each, never twice
+			if ((k[-4] & 7) == 1) mark(k); else if (!(k[-4] & F_CYCLE)) k[-4] = k[-4] & ~F_FINAL;
+			k[-4] = k[-4] & ~F_CYCLE;
 		}
 		i++;
 	}
diff --git a/tests/conformance/6-ownership/drop_gc_cycle.zc b/tests/conformance/6-ownership/drop_gc_cycle.zc
new file mode 100644
index 0000000..01db6b8
--- /dev/null
+++ b/tests/conformance/6-ownership/drop_gc_cycle.zc
@@ -0,0 +1,23 @@
+// expect: 0 1 2 2 0/
+// destructors 6.15.3: two unreachable values with drops that reach each other are finalized one per collection (each is in a cycle, so nothing outside it drops first), each exactly once, then freed
+include rt;
+int n;
+word g;
+struct node { node* other; int v; void drop() { n++; } }
+unchecked fn make() {
+	node* a = rt.new(node); node* b = rt.new(node);
+	a.v = 1; b.v = 2; a.other = b; b.other = a;
+	g = a;
+	return 0;
+}
+fn main() {
+	make();
+	rt.gc(); rt.put_n(n); rt.put_c(32);
+	g = 0;
+	rt.gc(); rt.put_n(n); rt.put_c(32);
+	rt.gc(); rt.put_n(n); rt.put_c(32);
+	rt.gc(); rt.gc(); rt.put_n(n); rt.put_c(32);
+	rt.put_n(rt.dcount); rt.put_c(10);	// both entries are gone with their blocks
+	return 0;
+}
+// zc0: skip
diff --git a/tests/conformance/6-ownership/drop_gc_self_capture.zc b/tests/conformance/6-ownership/drop_gc_self_capture.zc
new file mode 100644
index 0000000..444211d
--- /dev/null
+++ b/tests/conformance/6-ownership/drop_gc_self_capture.zc
@@ -0,0 +1,7 @@
+// expect: drop 3 0/
+// destructors 6.15.3: a value its own drop reaches (the closure captures it) is a cycle of one, so the collector still finalizes it once, then frees it
+include rt;
+word g;
+unchecked fn make() { word p = heap(3); word q = p; p.drop = fn() { rt.put_s("drop "); rt.put_n(*q); rt.put_c(32); }; g = p; return 0; }
+fn main() { make(); g = 0; rt.gc(); rt.gc(); rt.gc(); rt.put_n(rt.dcount); rt.put_c(10); return 0; }
+// zc0: skip