docs: revise destructors draft to acorn's rulings (drop on any heap value, heap() builtin, gc runs drops)

1 files changed, 117 insertions, 66 deletions

diff --git a/docs/design/destructors.md b/docs/design/destructors.md
index 151ecca..36c9f20 100644
--- a/docs/design/destructors.md
+++ b/docs/design/destructors.md
@@ -1,55 +1,98 @@
-# destructors on heap objects (draft)
+# destructors on heap values (draft)
 
-status: design draft, no compiler code. it parks `return defer x;` and covers that use case with owned results instead. section numbers refer to `docs/SPEC.md` at `d728a06`.
+status: design draft, no compiler code. revised to acorn's rulings on the nine questions of the first draft. it parks `return defer x;` and covers that use case with owned results and drops on values instead. section numbers refer to `docs/SPEC.md` at `d728a06`.
 
 ## the problem
 
-an owned heap object can stand for something outside the heap: a file descriptor, a socket, a lock, a native buffer, a registration in a table. today the analyzer frees the memory at scope end (6.5.1, `rt.recycle`), and the collector reclaims what nobody owns (6.9.3). neither one closes the outside resource. the caller has to remember a `defer close(x);`, and a function that opens something can't hand the cleanup up to its caller. acorn's `return defer` idea was meant to fill that gap. a destructor fills it more directly: the cleanup belongs to the type, so it follows the object wherever ownership goes.
+an owned heap value can stand for something outside the heap: a file descriptor, a socket, a lock, a native buffer, a registration in a table. today the analyzer frees the memory at scope end (6.5.1, `rt.recycle`), and the collector reclaims what nobody owns (6.9.3). neither one closes the outside resource. the caller has to remember a `defer close(x);`, and a function that opens something can't hand the cleanup up to its caller. a drop fills that gap: the cleanup is attached to the value, so it follows the value wherever ownership goes.
 
-## 1. declaration: one destructor per type
+## 1. heap(v): boxing any value
 
-proposal: a method named `drop` with no parameters and no result, declared in the struct body.
+`heap(v)` is a new builtin. it copies any value into a fresh owned heap slot sized to it and returns a pointer to that slot.
 
 ```zc
-struct file {
-    int fd;
-    void drop() { os.close(this.fd); }
-}
+int*.u    a = heap(10);                                  // one word
+char*.u   s = heap("hi");                                // string block, len 2
+foo*.u    f = heap((struct foo) { .bar = 4, .baz = p }); // struct block
 ```
 
-- each struct type has at most one `drop` (error: file: has more than one drop). a generic struct's `drop` is compiled once per instance, like its other methods (2.13.1).
-- `this` is borrowed (`.m`) inside `drop`. the body may read fields and call functions, but it can't give `this` away, store it in a global, or free it (error: drop can't give this away). the runtime frees the block after `drop` returns, as it does now.
-- `drop` is never called by name (error: drop is called by the runtime, not directly). an early close is `rt.free(x)`, which runs it.
-- a child owned by a field (`own`, `w[-2] == p`) is dropped after its parent's `drop` returns, in field order. this matches `release`/`recycle`, which already walk the children after the parent is marked going. so the parent's `drop` still sees live children.
-- types with no `drop` stay as they are.
+- **size.** the slot is sized to the value: one word for a scalar (`int`, `word`, pointer, fn), `len + 1` bytes rounded up for a string (the bytes are copied, `len(s)` works on the result), and `sizeof(T)` for a struct literal or struct value. the size is fixed at the call; "dynamic" means it follows the argument, not that the block grows.
+- **ownership.** the result is fresh with tag `.u` (6.1), like `rt.new`. bind it to an `m` local and it is freed at block end; return it and the caller owns it. pointer fields inside a boxed struct are copied as plain words: `heap` doesn't take ownership of what they point to.
+- **type.** `heap(e)` where `e : T` has type `T*.u`. a string literal gives `char*.u`. the block carries `T`'s type record, so typed frees, the collector walk and `drop` (below) work on it.
+- `heap` of an already-owned pointer boxes the pointer word, not the object it points to. it is not a move.
 
-alternatives, briefly:
-- `~file() { ... }` (c++ style). needs a new token form and reads as foreign next to the rest of zc.
-- `dtor file(file*.m f) { ... }` as a top-level item. this works for types declared elsewhere, but it splits the type and allows duplicates across units.
-- a parse word registered by a library (7.2), like actor. nice for the compiler size, but every free path needs the hook anyway, so it buys little.
-- a per-object callback (`rt.on_free(p, fn)`). flexible, but costs a word on every object or a side table, and it can't be checked statically. it could still be offered later for untyped `new(n)` blocks.
+## 2. drop: attaching cleanup to a value
 
-## 2. when it runs
+any heap value can have a drop, not only structs: `heap` slots, `rt.new` blocks (typed or raw), strings, arrays. a drop is a `fn()` with no parameters and no result. inside it, `this` is the value (borrowed, `.m`).
 
-`drop` runs exactly once, at the moment the object dies:
+three forms, all setting the same thing:
+
+```zc
+let g = drop(heap(0), fn() { unlock(); });    // call form, returns the value
+let x = new(int).drop(fn() { std.put_s("one two buckle my shoe"); });  // method form, returns the value
+let y = new(int); y.drop = fn() { std.put_n(*this); };                  // statement form
+```
+
+- `drop(v, f)` and `v.drop(f)` return `v` itself, with `v`'s type and tag, so they chain and can be passed along. `v.drop = f;` is a statement and has no value.
+- **set once.** a value's drop can be set only once (error: x: drop is already set).
+- **set early.** the drop must be set before the value is first read, reassigned or passed anywhere (error: x: drop set after the value was used). this is checked statically by the analyzer on the owning local; in practice the drop is set right at the allocation or on the next statement. this rule keeps every reader of the value seeing the same cleanup and means no copy of the pointer can escape without it.
+- **type default.** a struct body may still declare a `drop` method. it is the default drop for every value of that type:
+
+  ```zc
+  struct file {
+      int fd;
+      void drop() { os.close(this.fd); }
+  }
+  ```
+
+  a per-value drop on such a value is an error, the same as setting it twice (see open question 1).
+- `this` can be read and passed to borrowing calls, but not freed. storing it somewhere reachable revives the value (section 6).
+- a drop is never called by hand. an early close is `rt.free(x)`, which runs it.
+
+example (this is the spec example):
+
+```zc
+std.put_n(*heap(15).drop(fn() { std.put_s("i'm free as a bird! "); std.put_n(*this); }));
+```
+
+prints `15`, then `i'm free as a bird! 15`: the temporary is dropped at the end of the statement, after `put_n` returns. note the `*`: `drop` returns the pointer, so without it `put_n` would print an address.
+
+## 3. when it runs
+
+a drop runs exactly once, when the value dies:
 - an `m` local reaches the end of its block or an early exit (`return`, `break`, `continue`), in the same reverse declaration order as today's inserted frees (6.5.1).
 - an explicit `rt.free(x)` or `rt.recycle(x)`.
-- a temporary held in a hidden frame slot (6.5.4) is freed after its full expression.
+- **temporaries.** a value nothing holds (a temporary in a hidden frame slot, 6.5.4) dies at the end of its full statement. so
+
+  ```zc
+  heap(0).drop = fn() { unlock(); };   // unlocks right away: nothing holds it
+  ```
+
+  unlocks immediately. the scope guard idiom binds it:
+
+  ```zc
+  let guard = drop(heap(0), fn() { unlock(); });   // unlocks at block end
+  ```
+
+  the analyzer gives a hint when a value with a drop is never bound (hint: value with drop is never bound; it drops at the end of this statement).
 - a container is freed and its children go with it (6.5.3, 6.8.6). a `T[?]` of droppable elements drops them in index order. `pop` hands the element out fresh, so the container no longer drops it.
-- the collector reclaims an unowned object (section 5).
+- the owner is reassigned (section 4).
+- the collector reclaims an unowned value (section 6).
+
+**order: parent before children.** a child owned by a field (`own`, `w[-2] == p`) is dropped after its parent's drop returns, in field order. this matches `release`/`recycle`, which already walk the children after the parent is marked going, so the parent's drop still sees live children.
 
-## 3. moves transfer the duty
+## 4. ownership and moves
 
-the analyzer already proves that an owner is freed once: giving a value away (`.d` parameter, store into a global or container, `return`) makes the local dead (6.9.2), and the dead local isn't freed. `drop` rides on that same path, so it inherits the guarantee. no runtime flag is needed.
+the analyzer already proves that an owner is freed once: giving a value away (`.d` parameter, store into a global or container, `return`) makes the local dead (6.9.2), and the dead local isn't freed. drops ride on that same path, so they inherit the guarantee. no runtime flag is needed for checked code.
 
-- **partial moves.** zc fields carry no tags (2.12.2), and a field's child is owned through `own`. moving a child out (`word c = p.child; p.child = 0;`) is what code does today. proposal: moving out of a field of a droppable struct is allowed only by swapping in a replacement (`take(p.child)` sets the field to 0 and returns the old value fresh). the parent's `drop` must handle a null field. a direct field read that leaves the field still pointing at a moved child is an error when the parent type has a `drop` (error: p.child: moved out of a type with drop; use take). without that rule the parent's child walk would drop the child a second time.
-- **conditional moves.** 6.10.1 already handles a value given away on one path: the compiler frees it on the other paths on their way into the join. `drop` runs at that inserted free. a loop can't give a value away on a path that comes back around (6.10.2), so there is no "maybe moved" state at runtime, and no drop flag is needed.
-- **reassigning an owner.** today overwriting a still-owning variable is an error (6.8.5: overwriting it would leak it). keep that error. the alternative, dropping the old value implicitly on assignment, is c++-like and hides a side effect in `x = y;`. open question 3.
+- **no moving children out.** moving a child out of a value that has a drop (`word c = p.child;` used as an owner, or giving `p.child` away) is an error (error: p.child: can't move out of a value with drop). the parent's drop may depend on that child, and moving it out would leave the drop with a dangling or missing field. there is no `take(p.field)`. borrowing a child (`.m`) is fine.
+- **conditional moves.** 6.10.1 already handles a value given away on one path: the compiler frees it on the other paths on their way into the join. the drop runs at that inserted free. a loop can't give a value away on a path that comes back around (6.10.2), so there is no "maybe moved" state at runtime.
+- **reassigning an owner** (changes 6.8.5). overwriting a still-owning variable is no longer an error: the old value is freed, running its drop, before the new value is stored. the analyzer gives a hint (hint: x: reassigning frees the old value). `x = x.next` style self-reference is evaluated first: the right side is computed, then the old value is freed, then stored.
 - **aliases and borrows** never drop. only the owner's death does.
 
-## 4. returning an owned value
+## 5. returning an owned value
 
-a function that returns a `.u` result gives the caller the object, and with it the drop. the caller's scope end runs it:
+a function that returns a `.u` result gives the caller the value, and with it the drop:
 
 ```zc
 file*.u open_log() { file*.u f = rt.new(file); f.fd = os.open("log"); return f; }
@@ -60,62 +103,70 @@ fn main() {
 }   // log's drop closes the fd here
 ```
 
-this covers what `return defer x;` was for. the cleanup is written once on the type instead of at each return, the handoff shows up in the result type, and passing it along further is just another `return`. `return f();` hands the object up because a call to an owned-result function is fresh (6.1). if the caller binds it to an `m` local instead, the drop runs at that local's block end. this is the same as zcoder's proposed rule for `return defer`, so the semantics don't change for that use case.
+this covers what `return defer x;` was for. `return f();` hands the value up because a call to an owned-result function is fresh (6.1). a cleanup with no object behind it uses a guard value:
 
-a cleanup with no object behind it (a log line at the caller's scope end, say) still needs a carrier: a tiny struct with a `drop`. that is the price of parking `return defer`. open question 4.
+```zc
+int*.u locked() { lock(); return drop(heap(0), fn() { unlock(); }); }
+
+fn main() {
+    let g = locked();
+    ...
+}   // unlocks here
+```
+
+so no extra feature is needed. `return defer` stays parked.
 
-## 5. the collector
+## 6. the collector
 
-objects reachable only through globals, plain pointers, or unchecked code belong to the collector (6.9.3). the collector reclaims them whenever a sweep happens to run. so their `drop` runs late, or never if the program exits first. rule: **a resource that must be closed on time has to be owned by a checked local or by an owned chain from one.** the docs should say so plainly, and memdebug can warn (section 7).
+values reachable only through globals, plain pointers, or unchecked code belong to the collector (6.9.3). the collector **does** run their drops, but only when a sweep happens to reclaim them, so the drop runs late. rule: **a resource that must be closed on time has to be owned by a checked local or by an owned chain from one.** the docs say so plainly, and memdebug can warn (section 8).
 
-- **when it runs.** proposal: the sweep never runs user code. `gc()` gathers unmarked live objects whose type has a `drop` onto a finalize list instead of calling `bfree`. those blocks keep their state, so they stay out of the free lists. after `gc_active` is cleared, the runtime calls each `drop` and then frees the block. running user code mid-sweep would let it call `new` (which could reuse a block the sweep hasn't reached) or store pointers into blocks that are about to go.
-- **order.** within one sweep, finalize order is the heap address order of the sweep walk, so it is effectively unspecified. a parent and its owned child are both unmarked. the parent runs first, and its children follow through the normal walk, because the collector frees the parent and the parent's release frees the children. two unrelated unreachable objects have no defined order, and a `drop` must not assume the other is still open.
-- **resurrection.** a `drop` that stores `this` (or a child) somewhere reachable would bring it back to life. the static rule in section 1 forbids giving `this` away, but unchecked code inside `drop` could still do it. proposal: an object is finalized at most once. a header bit `F_DROPPED` is set before the call. if a later mark finds the object alive, it stays alive, but its `drop` won't run again. under memdebug, finding a dropped object reachable at the next sweep prints `zy: object revived by drop from line N`.
-- **shared objects** (`F_SHARE`) have no single owner. `free` and `release` skip them today. their `drop` runs only from the collector.
+- **after the sweep.** the sweep itself never runs user code. `gc()` puts unmarked live values that have a drop onto a finalize list instead of calling `bfree`; those blocks keep their state and stay out of the free lists. after `gc_active` is cleared, the runtime runs each drop, then frees the block. running user code mid-sweep would let it call `new` (reusing a block the sweep hasn't reached) or store pointers into blocks that are about to go.
+- **at most once.** a header bit `F_DROPPED` is set just before the drop is called. a value with `F_DROPPED` set never runs its drop again, on any path (collector, `rt.free`, a double free without memdebug).
+- **resurrection.** a drop that stores `this` (or a child) somewhere reachable, a global or a live container, keeps the value alive: after the drop returns, the runtime checks whether the block was reached again and, if so, does not free it. the value is then an ordinary live value with `F_DROPPED` set: it is usable, it is reclaimed by a later sweep or free once unreachable again, but its drop does not run a second time. under memdebug, finding a dropped value alive at the next sweep prints `zy: value revived by drop from line N`. the simplest implementation: the finalize list is itself a root for the next mark; a finalized block is only freed by the following sweep if it is still unmarked.
+- **order.** within one sweep, finalize order is the heap address order of the sweep walk, so it is unspecified. a parent and its owned child are both unmarked; the parent's drop runs first and its children follow through its release, keeping parent-before-children. two unrelated unreachable values have no defined order, and a drop must not assume the other is still open.
+- **shared values** (`F_SHARE`) have no single owner. `free` and `release` skip them today. their drop runs only from the collector.
+- **no final sweep at exit.** at a normal exit, collector-owned values are left to the os; their drops don't run.
 
-## 6. interactions
+## 7. interactions
 
 ### defer
-at a scope end, the order is: the block's defers (newest first, 4.14.2), then the inserted frees of the block's `m` locals in reverse declaration order, each running its `drop`. this keeps 4.14.7 true: a deferred statement sees its locals still alive. so `defer flush(log);` runs before `log`'s drop closes it. an explicit `defer rt.free(x);` runs `drop` at the defer's point, and the local isn't freed again.
+at a scope end, the order is: the block's defers (newest first, 4.14.2), then the inserted frees of the block's `m` locals in reverse declaration order, each running its drop. a deferred statement sees its locals still alive (4.14.7). an explicit `defer rt.free(x);` runs the drop at the defer's point, and the local isn't freed again.
 
 ### o3 regions
-o3 changes speed, not meaning (4.10.1), so drop calls stay. two notes: an o3 untyped `rt.new(n)` is `new_oz` with no type stamp, so it can't have a drop. and an inserted free in an o3 function of a type with a `drop` is a call out of the region, which will cost inlining in the llvm/x86 tiers. that's acceptable, since droppable objects are rarely in hot loops. the optimiser must not reorder a drop past another side effect.
+o3 changes speed, not meaning (4.10.1), so drop calls stay. an inserted free of a value that may have a drop is a call out of the region, which costs inlining in the llvm/x86 tiers; acceptable, since droppable values are rarely in hot loops. the optimiser must not reorder a drop past another side effect.
 
 ### unchecked and unbounded
-unchecked code has no inserted frees (6.12). what it allocates belongs to the collector or to an explicit `rt.free`. an explicit `rt.free` in unchecked code still runs `drop` (the runtime does it, not the analyzer). unbounded affects only index checks, so it has no effect here. the runtime itself is unchecked and unbounded, so it can't depend on the analyzer to drop anything for it.
+unchecked code has no inserted frees (6.12). what it allocates belongs to the collector or to an explicit `rt.free`, which still runs the drop (the runtime does it, not the analyzer). the set-once and set-early rules can't be checked in unchecked code; there the runtime refuses a second set (trap) and the set-early rule is the programmer's job. unbounded affects only index checks.
 
 ### traps and exit
-- a runtime trap (exit 2) does not unwind. no defers run today, so no drops run either. resources are left to the os. this matches defer.
-- a normal exit (main returns, or `rt.exit`): main's scope-end frees run their drops before exit, as usual. objects still held by globals or the collector are **not** finalized at exit by default (no final sweep). open question 6.
-- a trap inside a `drop` is a trap like any other.
+- a runtime trap (exit 2) does not unwind. no defers and no drops run. resources are left to the os.
+- a normal exit (main returns, or `rt.exit`): main's scope-end frees run their drops as usual. collector-owned values are not finalized (no final sweep).
+- a trap inside a drop is a trap like any other.
 
 ### recycle, quarantine, memdebug
-- `free` → `release` leaves the block quarantined until a sweep (6.9.3). `drop` runs before the quarantine, while the object is still fully valid: the header is still live, and `len` and indexing work. that is because `release` clears `n` when it marks the block quarantined.
-- `recycle` and `recycle_leaf`: run `drop` before the child walk. `recycle_leaf` is the fast path for leaf types. a type with a `drop` gets no `recycle_leaf`; the compiler routes it to the general free instead (see the cost section).
-- double free under memdebug is caught by `quar(p)` before `drop`, so a double free never runs `drop` twice. without memdebug a double free of a released block finds `n == 0` and a cleared state, and `drop` is skipped by checking `F_DROPPED`.
-- `memdebug scrub` fills the payload after `drop`, never before.
-- new: `rt.memreport()` marks leaked objects whose type has a `drop` (`leak: line N W words (drop: file)`), since those are leaked resources, not just leaked words.
+- `free` → `release` runs the drop before the quarantine, while the value is still fully valid (header live, `len` and indexing work), since `release` clears `n` when it quarantines the block.
+- `recycle` and `recycle_leaf`: run the drop before the child walk. a value that may have a drop doesn't take the `recycle_leaf` fast path.
+- double free under memdebug is caught by `quar(p)` before the drop. without memdebug, `F_DROPPED` stops a second run.
+- `memdebug scrub` fills the payload after the drop, never before.
+- `rt.memreport()` marks leaked values that have a drop (`leak: line N W words (drop)`), since those are leaked resources, not just leaked words.
+
+### raw blocks
+untyped `rt.new(n)` blocks take a drop like any other value, so there is no separate `rt.on_free` hook.
 
 ### actors
-- `spawn` snapshots the whole vm into a worker process. every owned object in the snapshot is copied too, so the worker's owners drop their copies, and the parent drops its own. a `drop` that closes an fd would then close it twice, once per process. the fd is duplicated across the fork, so the os is fine, but a drop that commits or deletes something external would act twice. proposal: an `actor`-safe marker is not needed yet. document that a droppable object must not be live across `spawn` unless its drop is idempotent per process, and have the analyzer warn on a live droppable local at a `spawn` call (hint level, 4.12).
-- messages copy their typed object graphs (ACTOR.md). the sender keeps and drops its graph; the receiver's copy is a new owner with its own drop. a copied fd handle is just an integer, which is wrong for real resources. proposal: a type with a `drop` can't be sent by copy (error: file: has drop and can't be copied into a message). sending it by move, when actor gains move sends, transfers the duty to the receiver and makes the sender's local dead, as for any `.d` give-away.
+- **messages.** copying a value with a drop into an actor message is a hard error (error: x: has drop and can't be copied into a message). a copied fd handle is just an integer, and two drops would close or commit twice. sending it by move, when actors gain move sends, transfers the duty to the receiver and makes the sender's local dead.
+- `spawn` snapshots the whole vm into a worker process, so both processes hold and drop their copies. document that a droppable value must not be live across `spawn` unless its drop is safe to run once per process; the analyzer gives a hint on a live droppable local at a `spawn` call (4.12).
 - a worker exiting normally runs its main-level drops, like any program.
 
-## 7. cost
+## 8. cost
 
-- **types without drop pay nothing.** whether a type has a `drop` is known when the type is compiled. the type record (`p[-1]`) gains one field: the drop address, or 0. the compiler emits drop calls only for frees whose static type has a drop. every other free keeps today's code, including `recycle_leaf`. untyped `new(n)` and `new_oz` blocks have no type record, so they never drop.
-- **free/release/recycle.** the runtime still has to handle frees where the static type isn't known (unchecked `rt.free`, children found by the walk, the collector). each of those adds one load and test: `t = p[-1]; if (t > 0 && t[DROP]) ...`, which is cheap next to the existing `scan_ptr` walk. the `F_DROPPED` bit takes one free header flag; a header bit audit should confirm which one.
-- **the collector.** one extra test per unmarked object in the sweep, plus a finalize list that grows like the mark stack (`reserve_mark`).
-- **genome.** the parser adds about one method name check and one type record field. the analyzer adds the `take`/partial-move rule and the actor send check. the runtime adds the drop test in three places and the finalize list in `gc`. a rough guess is a few hundred words. the compiler itself defines no droppable types, so it runs no drops. zc-lines should measure the fixpoint once code exists.
+- **where the drop lives.** a type default lives in the type record (`p[-1]`, one new field: drop address or 0). a per-value drop needs per-value storage. proposal: a header flag `F_HASDROP` plus a side table keyed by block address (open hash), so values without a drop pay nothing in size. the type default needs no table entry. see open question 2.
+- **values without drop pay one test.** the runtime's free paths (unchecked `rt.free`, children found by the walk, the collector) add one load and test: `if (hdr & F_HASDROP || (t = p[-1]) > 0 && t[DROP]) ...`, cheap next to `scan_ptr`. where the analyzer can see that a local never had a drop set and its type has no default, it emits today's free code, including `recycle_leaf`.
+- **header bits.** `F_HASDROP` and `F_DROPPED` take two free header flags; a header bit audit should confirm which.
+- **the collector.** one extra test per unmarked block in the sweep, a finalize list that grows like the mark stack (`reserve_mark`), and one extra mark root.
+- **genome.** the parser adds `heap`, the three drop forms, and the type-default method. the analyzer adds set-once/set-early, the no-move-out rule, the never-bound hint, the reassignment free, and the actor send check. the runtime adds the drop test in three places, the side table, and the finalize list. a rough guess is several hundred words; zc-lines should measure the fixpoint once code exists.
 
 ## open questions for acorn
 
-1. is `drop` as a method name right, or do you prefer `~T()` or a separate top-level `dtor` item?
-2. should `drop` see live children (parent first, as proposed), or should children drop first, like c++ members?
-3. reassigning a still-owning variable: keep the error (6.8.5), or drop the old value implicitly?
-4. with `return defer` parked, is a small carrier struct with a `drop` good enough for cleanups that have no object behind them?
-5. partial moves: is the `take(p.field)` rule acceptable, or should droppable types simply forbid moving children out?
-6. at a normal exit, should the runtime run one last sweep so collector-owned objects get their drop, or leave them to the os (faster exit, as proposed)?
-7. collector finalization: finalize after the sweep with a once-only `F_DROPPED` bit, as proposed, or forbid `drop` on objects that can reach the collector at all?
-8. actors: hard error on sending a droppable type by copy, and only a hint on a live droppable at `spawn`. too strict, or not strict enough?
-9. should untyped blocks get an opt-in callback (`rt.on_free`), or stay drop-free for good?
+1. a struct with a type-level `drop`: should a per-value drop be an error (as written), replace the default, or run in addition to it?
+2. per-value drop storage: side table keyed by address (no size cost, one hash lookup per drop) or an extra header word on every block (fast, costs memory everywhere)?