summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2026-11-20 15:26:44 -0800
committerCliff Click <cliffc@acm.org>2026-11-20 15:26:44 -0800
commitc201515eeb2e99cb6f0e820459662affc047c2ce (patch)
tree28750086af8c788f4614d6a8b2a82df4a413e00a
parent4f0cc22dafcdea877fe4ab137523a5944f754126 (diff)
downloadSimple-c201515eeb2e99cb6f0e820459662affc047c2ce.tar.gz
Simple-c201515eeb2e99cb6f0e820459662affc047c2ce.zip
Basic first implementationch33
Walk a Call Graph DAG. Find allocation sites; find uses for those objects; move the allocation to the common shared call point. Limited in all sorts of ways.
-rw-r--r--chapter33/README.md87
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/codegen/Allocation.java397
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java15
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/ConstantNode.java1
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/FunNode.java2
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java1
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/Node.java5
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/ParmNode.java2
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/StartNode.java2
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/SummaryNode.java1
-rw-r--r--chapter33/src/test/java/com/seaofnodes/simple/Chapter33Test.java223
-rw-r--r--chapter33/src/test/java/com/seaofnodes/simple/PhaseTest.java2
-rw-r--r--docs/automatic-memory-management-survey.md777
-rw-r--r--docs/roadmap.md85
-rw-r--r--skills/chapter25-codex-notes.md76
15 files changed, 1652 insertions, 24 deletions
diff --git a/chapter33/README.md b/chapter33/README.md
index 486f02d3..e3a19026 100644
--- a/chapter33/README.md
+++ b/chapter33/README.md
@@ -4,10 +4,89 @@ English | [日本語](README.ja.md)
[Previous: Chapter 32 — Compiler Internal Speedups](../chapter32/README.md)
-This chapter will explore automatic memory management. The design is still
-open; no memory-management changes have been implemented yet. It starts from
-the complete, runnable Chapter 32 compiler, libraries, examples, and tests.
-The speedup measurements remain in [Chapter 32](../chapter32/README.md).
+This chapter starts automatic memory management with an allocation-lifetime
+analysis. It runs after Opto and field-layout finalization, before TypeCheck.
+It reports where storage must live; allocation and machine code still use the
+existing runtime. The [design survey](../docs/automatic-memory-management-survey.md)
+records the language decisions. Chapter 32's
+[speedup measurements](../chapter32/README.md) remain there.
+
+## First allocation plans
+
+Four small examples in [Chapter33Test](src/test/java/com/seaofnodes/simple/Chapter33Test.java)
+exercise the first cut:
+
+| Example | Allocation destination |
+|---|---|
+| Make a temporary and pass it to a reader | Current function frame |
+| Return a Box containing a Thing through two factories | Caller-supplied result storage for both objects |
+| Assign a newly allocated Thing to an argument's field | Storage that lives long enough for that argument |
+| Call one factory twice and store into different arguments | Separate destinations for the two calls |
+
+The analysis walks the call DAG once. It discovers callees on entry and builds
+each function's summary on exit. Within a body it follows control, memory, and
+references, skipping arithmetic and offset expressions. Control anchors expose
+allocations even when only scalar uses remain; reference uses expose raw-address
+conversions without walking the arithmetic that consumes them. Sorting is confined
+to the debug dump. Parameters name symbolic storage owners;
+returning or storing a fresh reference adds destination requirements. Composing
+a call substitutes its actual arguments and keeps its fresh allocations distinct
+from other calls to the same factory. Private callee scratch stays in the
+callee's summary.
+
+Within one summary, a worklist propagates requirements through object fields.
+For example, returning a Box retains its Thing too. This local closure does
+not repeat the call-graph traversal. Stores are conservative weak updates:
+overwriting a field does not yet release the earlier value's lifetime constraint.
+
+The ASCII dump shows callees first, then their callers:
+
+```text
++-- make_noInline
+| [result] new#352:Test.Thing (8 bytes)
+| [result] new#381:Test.Box (8 bytes)
+| .child --> new#352:Test.Thing
+`-- return -> new#381:Test.Box
+
++-- forward_noInline
+| call#219 -> make_noInline
+| [result] call#219/new#352:Test.Thing (8 bytes)
+| [result] call#219/new#381:Test.Box (8 bytes)
+| .child --> call#219/new#352:Test.Thing
+`-- return -> call#219/new#381:Test.Box
+```
+
+`frame` means scratch for that function; `result` means the caller's result
+destination; `static` means program lifetime. `arg3` names storage associated
+with argument input 3 (ordinary class functions use input 2 for their hidden
+receiver). `arg3 & arg4` requires a destination satisfying both owners; it does
+not arbitrarily pick one. Node numbers help correlate this output with the IR.
+These are ownership constraints, not assigned physical stack offsets.
+
+Run a poster child and print its plan:
+
+```sh
+make -j8 test CLASS=Chapter33Test METHOD=testAllocationFactoryGraph "TEST_JAVA_OPTS=-XX:ActiveProcessorCount=2 -Dsimple.alloc.dump=true"
+```
+
+The first cut rejects plans for loops, recursive calls, opaque/indirect calls,
+variable-size allocations, raw address conversions, and reference origins that
+it cannot trace, including pointer-valued field loads. A rejected function is
+printed as `REJECT`, never as a usable partial plan. Scalar field reads and
+writes do not themselves introduce retained references.
+
+Normal compilation records those rejections and continues with the existing
+allocator. `-Dsimple.alloc.check=true` rejects compilation if any function lacks
+a supported plan; tests can also require an individual summary to be supported.
+The pass does not yet insert hidden destination arguments, stack reservations,
+or reclamation. The proposed inline-object and growing-array syntax is not
+implemented by this analysis experiment.
+
+[Allocation.java](src/main/java/com/seaofnodes/simple/codegen/Allocation.java)
+contains the walk, one summary class, and one storage-site class. Comments mark
+the next work: loop and SCC destinations, field-path origins, bin packing,
+free lists, and parallel growth areas. No new IR nodes or serialized contracts
+are introduced yet.
## Build and use this chapter
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/codegen/Allocation.java b/chapter33/src/main/java/com/seaofnodes/simple/codegen/Allocation.java
new file mode 100644
index 00000000..0c4feeee
--- /dev/null
+++ b/chapter33/src/main/java/com/seaofnodes/simple/codegen/Allocation.java
@@ -0,0 +1,397 @@
+package com.seaofnodes.simple.codegen;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.util.SB;
+import java.util.*;
+
+/** First allocation-lifetime experiment. Builds plans, not machine allocations.
+ * One DFS of the call DAG: discover callees on entry, compose their symbolic
+ * summaries on exit. No call-tree expansion, caller rewalk, or IR mutation.
+ * Within a summary, reference edges propagate destination requirements with a
+ * small worklist. A rejected summary is never a usable allocation plan.
+ */
+public final class Allocation {
+ private final Summary[] _summaries;
+ private final ArrayList<Summary> _postorder = new ArrayList<>();
+
+ // Destination bits: result, static storage, then Call/Parm input indices.
+ private static final int RESULT=0, STATIC=1;
+
+ /** One abstract storage object. Imported allocations are distinct per call
+ * site; a parameter denotes borrowed storage, not an allocation to move. */
+ public static final class Site {
+ public final NewNode _allocation; // null for a formal or static storage
+ public final int _arg; // >=2: Parm index, -1: static, 0: fresh
+ public final String _name;
+ public final long _bytes; // snapshot before later IR rewrites
+ public final BitSet _owners = new BitSet();
+ public final HashMap<String,HashSet<Site>> _fields = new HashMap<>();
+
+ private Site(NewNode allocation, int arg, String name) {
+ _allocation=allocation; _arg=arg; _name=name;
+ _bytes=allocation!=null && allocation.size()._type instanceof TypeInteger size && size.isConstant()
+ ? size.value() : -1;
+ if( arg>=2 ) _owners.set(arg);
+ if( arg==-1 ) _owners.set(STATIC);
+ }
+
+ public String destination() {
+ if( _owners.isEmpty() ) return "frame";
+ SB sb = new SB();
+ for( int i=_owners.nextSetBit(0); i>=0; i=_owners.nextSetBit(i+1) )
+ sb.p(i==RESULT ? "result" : i==STATIC ? "static" : "arg"+i).p(" & ");
+ return sb.unchar(3).toString();
+ }
+ }
+
+ /** Symbolic summary, with separate destinations for separate arguments.
+ * Object fields are weak updates: all stored references remain possible.
+ * The first cut rejects pointer loads rather than guessing their origin. */
+
+ // Per-function summary; allocation sites; failure reasons
+ public static final class Summary {
+ public final FunNode _fun;
+ public final ArrayList<Site> _sites = new ArrayList<>();
+ public final HashSet<Site> _returns = new HashSet<>();
+ public String _reject;
+ private byte _state; // 0 pre/unseen, 1 mid/active DFS, 2 post/complete
+ // All allocation-interesting Nodes; Calls, Stores, News, Ptr ops
+ private final ArrayList<Node> _nodes = new ArrayList<>();
+ // Just the Calls
+ private final ArrayList<CallNode> _calls = new ArrayList<>();
+ // Pointer expression -> possible storage objects, in this function's vocabulary.
+ private final IdentityHashMap< Node,HashSet<Site>> _values = new IdentityHashMap<>();
+ // Call -> returned storage after substituting actuals and importing effects once.
+ private final IdentityHashMap<CallNode,HashSet<Site>> _results = new IdentityHashMap<>();
+ private final BitSet _resolving = new BitSet();
+ private final Site _static = new Site(null,-1,"static");
+
+ private Summary(FunNode fun) { _fun=fun; }
+ // Hit the end of summary findings with no errors.
+ public boolean supported() { return _state==2 && _reject==null; }
+ // Throw or return valid summary
+ public Summary requireSupported() {
+ if( !supported() ) throw new IllegalStateException("Allocation "+_fun.label()+": "+_reject);
+ return this;
+ }
+ // Collect first rejection
+ private void reject(String why) { if( _reject==null ) _reject=why; }
+ }
+
+ public Allocation(CodeGen code) {
+ _summaries = new Summary[code._linker._len];
+ for( FunNode fun : code._linker )
+ if( fun!=null && !fun.isDead() && !fun._type.isHigh() )
+ _summaries[fun.sig().fidx()] = new Summary(fun);
+ for( Summary sum : _summaries )
+ if( sum!=null )
+ visit(sum);
+ }
+
+ public Summary summary(String name) {
+ for( Summary sum : _summaries )
+ if( sum!=null && name.equals(sum._fun._name) ) return sum;
+ throw new IllegalArgumentException("No allocation summary for "+name);
+ }
+
+ public void requireSupported() {
+ for( Summary sum : _postorder )
+ sum.requireSupported();
+ }
+
+ private void visit(Summary sum) {
+ if( sum._state==2 ) return; // Post-order, done
+ // Mid-visit, so found a Call Graph cycle, i.e. recursion
+ if( sum._state==1 ) {
+ // Recursive SCC/mega-call work goes here; do not expand a call tree.
+ sum.reject("recursive call component");
+ return;
+ }
+ // Was pre-order, now mid-order
+ sum._state=1;
+ if( sum._fun._extern || sum._fun.summary()!=null ) {
+ sum.reject("opaque body: allocation contract unavailable");
+ } else {
+ // Collection interesting function body and call sites
+ collect(sum);
+ for( CallNode call : sum._calls ) {
+ Summary callee = target(call);
+ if( callee==null ) sum.reject("opaque or indirect call #"+call._nid);
+ else {
+ // Recursive walk Call Graph DAG
+ visit(callee);
+ // If some callee is rejected, so is this caller
+ if( callee._reject!=null )
+ sum.reject("call #"+call._nid+" -> "+callee._fun.label()+": "+callee._reject);
+ }
+ }
+ if( sum._reject==null )
+ build(sum);
+ }
+ // Postder
+ sum._state=2;
+ _postorder.add(sum);
+ }
+
+ private Summary target(CallNode call) {
+ if( !(call.fptr()._type instanceof TypeFunPtr fp) || !fp.isConstant() ) return null;
+ int idx=fp.fidx();
+ return idx>=0 && idx<_summaries.length ? _summaries[idx] : null;
+ }
+
+ // Follow control, memory, and references, not arithmetic/offset expressions.
+ // Find allocations at control anchors too: their only remaining use might
+ // be a scalar load or a raw address buried under arithmetic. Don't walk into
+ // other functions, so no following linked Calls or Parms.
+ private void collect(Summary sum) {
+ BitSet seen = new BitSet();
+ ArrayDeque<Node> work = new ArrayDeque<>();
+ // Start from the return
+ work.push(sum._fun.ret());
+ // Repeat until entire function is walked
+ while( !work.isEmpty() ) {
+ Node n = work.pop();
+ if( seen.get(n._nid) ) continue; // Been there, done that
+ seen.set(n._nid);
+ // Add to function body
+ sum._nodes.add(n);
+ if( n instanceof CFGNode )
+ for( Node use : n._outputs )
+ if( use instanceof NewNode alloc && alloc.ctrl()==n ||
+ use instanceof ParmNode parm && parm.fun()==sum._fun )
+ work.push(use);
+ // Reference uses stay within this function; Parm call links and
+ // constant/global anchors are boundaries. In particular, find raw
+ // conversions without following their scalar arithmetic users.
+ if( !n.isFunLeaf() || n instanceof ParmNode )
+ for( Node use : n._outputs )
+ if( use instanceof PtrToIntNode || pointer(use) && !use.isFunLeaf() )
+ work.push(use);
+ if( n.isFunLeaf() ) continue;
+ if( n instanceof CallNode call ) sum._calls.add(call);
+ // Iteration/winner destinations go here. Until then reject loops,
+ // even when a flow-insensitive union would appear to fit a frame.
+ if( n instanceof LoopNode ) sum.reject("loop destinations not implemented");
+ if( n instanceof PtrToIntNode ) sum.reject("raw address escapes lifetime tracking #"+n._nid);
+
+ // CLInit accesses static state, not caller parameters. Its body is
+ // analyzed separately; stores publishing local objects to static
+ // state already give those objects the static destination. Do not
+ // mistake an own-class initialization guard for recursive calling.
+ if( n instanceof CallEndNode cend ) { work.push(cend.call()); continue; }
+
+ // Walk selected edges. We can skip pure-data ops, but need to
+ // walk both control and memory at least.
+ for( Node in : n._inputs )
+ if( in!=null && (in instanceof CFGNode || in.isMem() ||
+ in._type instanceof TypeMem || pointer(in) || in instanceof NewNode) )
+ work.push(in);
+ }
+ }
+
+ // Post-order work during the Call Graph visit
+ private void build(Summary sum) {
+ for( Node n : sum._nodes ) {
+ // Gather allocation sites
+ if( n instanceof NewNode alloc ) {
+ if( !(alloc.size()._type instanceof TypeInteger size) || !size.isConstant() )
+ sum.reject("variable-size allocation #"+alloc._nid);
+ Site site = new Site(alloc,0,"new#"+alloc._nid+":"+alloc._ts._name);
+ if( TypeStruct.startsClzPrefix(alloc._ts._name) ) site._owners.set(STATIC);
+ sum._sites.add(site);
+ sum._values.put(alloc,set(site));
+ }
+ if( n instanceof ParmNode parm && pointer(parm) ) {
+ if( parm.fun()!=sum._fun ) sum.reject("foreign parameter #"+parm._nid);
+ Site site = new Site(null,parm._idx,"arg"+parm._idx+":"+parm.label());
+ sum._sites.add(site);
+ sum._values.put(parm,set(site));
+ }
+ }
+ for( CallNode call : sum._calls ) compose(sum,call);
+ for( Node n : sum._nodes ) {
+ if( n instanceof StoreNode store && pointer(store.val()) ) {
+ Set<Site> dst = refs(sum,store.ptr()), src=refs(sum,store.val());
+ edge(dst, store._name, src);
+ }
+ }
+ sum._returns.addAll(refs(sum,sum._fun.ret().expr()));
+ for( Site site : sum._returns ) site._owners.set(RESULT);
+ if( !sum._static._fields.isEmpty() ) sum._sites.add(sum._static);
+
+ // Local closure only: an object retained in a destination retains its
+ // referenced objects there too. Cyclic object graphs need no DAG rewalk.
+ ArrayDeque<Site> work=new ArrayDeque<>(sum._sites);
+ while( !work.isEmpty() ) {
+ Site src = work.pop();
+ for( Set<Site> values : src._fields.values() )
+ for( Site dst : values ) {
+ int before = dst._owners.cardinality();
+ dst._owners.or(src._owners); // Union owners set
+ if( dst._owners.cardinality() != before ) work.push(dst);
+ }
+ }
+ // Bin packing goes here: fixed destinations become caller landing zones.
+ // Free-list work goes here: only after checking remaining usable aliases.
+ // Parallel growing tips go here: one owner may need several storage areas.
+ }
+
+ // n has pointer type
+ private static boolean pointer(Node n) {
+ return n!=null && (n._type instanceof TypeMemPtr || n._type instanceof TypePtr);
+ }
+
+ // One element Set of Site
+ private static HashSet<Site> set(Site site) {
+ HashSet<Site> set = new HashSet<>(); set.add(site); return set;
+ }
+
+ private static void edge(Set<Site> dst, String field, Set<Site> src) {
+ if( src.isEmpty() ) return;
+ for( Site site : dst )
+ site._fields.computeIfAbsent(field,k -> new HashSet<>()).addAll(src);
+ }
+
+
+ // Which storage objects can this pointer expression denote? This resolves
+ // pointer VALUE flow, not the fields reachable through the pointer. A Phi
+ // unions possible targets; casts/views preserve targets; a call result uses
+ // compose's caller-side targets. New/Parm targets were seeded by build.
+ // Example: refs(cond ? a : b) = {site(a), site(b)}.
+ // build() uses these sets to add Store edges, then propagates owner requirements
+ // through that separate object graph. Object cycles are handled there;
+ // _resolving rejects cyclic SSA values (loop Phi support is future work).
+ private HashSet<Site> refs(Summary sum, Node n) {
+ if( !pointer(n) ) return new HashSet<>();
+ HashSet<Site> old = sum._values.get(n);
+ if( old!=null ) return old;
+ HashSet<Site> values = new HashSet<>();
+ if( sum._resolving.get(n._nid) ) {
+ sum.reject("cyclic reference value #"+n._nid);
+ return values;
+ }
+ sum._resolving.set(n._nid);
+ if( n instanceof ConstantNode ) {
+ // Zero/null carries no storage obligation. Other constant objects
+ // have static backing; references loaded from them are not guessed.
+ if( n._type!=Type.NIL && n._type!=TypeInteger.ZERO ) values.add(sum._static);
+ } else if( n instanceof ProjNode proj && proj.in(0) instanceof NewNode alloc && proj._idx==0 ) {
+ Set<Site> sites = sum._values.get(alloc);
+ if( sites==null ) sum.reject("foreign allocation #"+alloc._nid);
+ else values.addAll(sites);
+ } else if( n instanceof ProjNode proj && proj.in(0) instanceof CallEndNode end && proj._idx==2 ) {
+ values.addAll(compose(sum,end.call()));
+ } else if( n instanceof PhiNode phi && !(phi instanceof ParmNode) ) {
+ for( int i=1; i<n.nIns(); i++ )
+ if( !phi.region().in(i)._type.isHigh() ) values.addAll(refs(sum,n.in(i)));
+ } else if( n instanceof ReadOnlyNode || n instanceof GuardNode ||
+ n instanceof ConstructNode || n instanceof InitViewNode || n instanceof ConvertNode ) {
+ values.addAll(refs(sum,n.in(1)));
+ } else if( n instanceof ArrayInitNode ) {
+ values.addAll(refs(sum,n.in(2)));
+ } else {
+ // Field-path/array-element origins go here. A parameter's child may
+ // have a different owner; never silently substitute the base owner.
+ sum.reject("reference origin "+n.getClass().getSimpleName()+" #"+n._nid);
+ }
+ sum._resolving.clear(n._nid);
+ sum._values.put(n,values);
+ return values;
+ }
+
+ // Apply an already-built callee summary to this particular call. Translate
+ // callee Sites into caller Sites: formal -> refs(actual), static -> static,
+ // escaping allocation -> fresh Site tagged with this call. This copies
+ // analysis objects, not runtime objects or IR. Private callee scratch stays
+ // in the callee. A second call gets distinct Sites for its fresh allocations.
+ // Then translate field edges and returned targets through the same map.
+ // For helper(h) { h.c = new Thing; }, calling helper(a) adds a.c -> call/new.
+ // The map values are SETS because an actual may select several objects.
+ // Callee result/argument owner bits are relative to its signature; do not
+ // copy them into the caller. build's closure derives the caller's owners
+ // from the translated edges and uses of the result. Only static is absolute.
+ private HashSet<Site> compose(Summary sum, CallNode call) {
+ HashSet<Site> result=sum._results.get(call);
+ if( result!=null ) return result;
+ result=new HashSet<>();
+ sum._results.put(call,result);
+ Summary callee=target(call);
+ if( callee==null || !callee.supported() ) {
+ sum.reject("unavailable allocation summary at call #"+call._nid);
+ return result;
+ }
+ IdentityHashMap<Site,HashSet<Site>> map=new IdentityHashMap<>();
+ map.put(callee._static,set(sum._static));
+ // Establish all substitutions first, so forward/cyclic field edges can
+ // be copied without depending on Site visitation order.
+ for( Site site : callee._sites ) {
+ if( site._arg>=2 ) {
+ if( site._arg>=call.nIns()-1 ) {
+ sum.reject("missing argument at call #"+call._nid);
+ map.put(site,new HashSet<>());
+ } else map.put(site,refs(sum,call.arg(site._arg)));
+ } else if( site._allocation!=null && !site._owners.isEmpty() ) {
+ Site copy=new Site(site._allocation,0,"call#"+call._nid+"/"+site._name);
+ // Return/argument owners are substituted by edges in this caller.
+ if( site._owners.get(STATIC) ) copy._owners.set(STATIC);
+ sum._sites.add(copy);
+ map.put(site,set(copy));
+ }
+ }
+ // Retention effects exist even when the function returns a scalar.
+ for( Site site : callee._sites ) {
+ Set<Site> dst=map.get(site);
+ if( dst==null ) continue;
+ for( var field : site._fields.entrySet() ) for( Site child : field.getValue() ) {
+ Set<Site> src=map.get(child);
+ if( src==null ) sum.reject("unmapped retained storage at call #"+call._nid);
+ else edge(dst,field.getKey(),src);
+ }
+ }
+ for( Site site : callee._returns ) {
+ Set<Site> returned=map.get(site);
+ if( returned==null ) sum.reject("unmapped returned storage at call #"+call._nid);
+ else result.addAll(returned);
+ }
+ return result;
+ }
+
+ @Override public String toString() {
+ StringBuilder out = new StringBuilder("Allocation destinations (analysis only; no stack lowering)\n");
+ for( Summary sum : _postorder ) {
+ out.append("\n+-- ").append(sum._fun.label()).append("\n");
+ ArrayList<CallNode> calls=new ArrayList<>(sum._calls);
+ calls.sort(Comparator.comparingInt(n -> n._nid));
+ for( CallNode call : calls ) {
+ Summary callee=target(call);
+ out.append("| call#").append(call._nid).append(" -> ")
+ .append(callee==null ? "?" : callee._fun.label()).append("\n");
+ }
+ if( !sum.supported() ) {
+ out.append("`-- REJECT: ").append(sum._reject).append("\n");
+ continue; // Do not display a partial plan as a safe placement.
+ }
+ ArrayList<Site> sites=new ArrayList<>(sum._sites);
+ sites.sort(Comparator.comparing(s -> s._name));
+ for( Site site : sites ) {
+ out.append("| [").append(site.destination()).append("] ").append(site._name);
+ if( site._allocation!=null ) out.append(" (").append(site._bytes).append(" bytes)");
+ out.append("\n");
+ // Stable debugging order belongs here, not in the analysis maps.
+ ArrayList<String> edges=new ArrayList<>();
+ for( var field : site._fields.entrySet() ) for( Site child : field.getValue() )
+ edges.add("| ."+field.getKey()+" --> "+child._name+"\n");
+ Collections.sort(edges);
+ for( String edge : edges ) out.append(edge);
+ }
+ out.append("`-- return");
+ ArrayList<String> returns=new ArrayList<>();
+ for( Site site : sum._returns ) returns.add(site._name);
+ Collections.sort(returns);
+ for( String name : returns ) out.append(" -> ").append(name);
+ out.append("\n");
+ }
+ return out.toString();
+ }
+}
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter33/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index 51a6a197..f38305b2 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -27,6 +27,7 @@ public class CodeGen {
Opto, // SCCP, numeric modes, seed the peephole worklist
IterPostOpto, // Peepholes and inlining using SCCP results
FinalizeIR, // Field layout, offset cleanup, function/CU roots
+ Allocation, // Symbolic allocation destinations; analysis only
TypeCheck, // Last check for bad programs
Serialize, // Save ideal IR, including opaque class initialization
Lower, // Expand checked class initialization to ordinary IR
@@ -196,6 +197,7 @@ public class CodeGen {
step(target, Phase.IterPostOpto, this::iterPostOpto, dump);
// Field layouts; field symbols become constant offsets
step(target, Phase.FinalizeIR, this::finalizeIR, dump);
+ step(target, Phase.Allocation, this::allocation, dump);
// Final error check - bad programs fail here
step(target, Phase.TypeCheck, this::typeCheck, dump);
// Save reloadable ideal IR for a later seperate compilation
@@ -518,7 +520,18 @@ public class CodeGen {
// ---------------------------
// Last check for bad programs
- public CodeGen typeCheck() { return phase(Phase.TypeCheck, _phase==Phase.FinalizeIR, () -> TypeCheck.run(this)); }
+ public Allocation _allocation;
+ public CodeGen allocation() {
+ return phase(Phase.Allocation, _phase==Phase.FinalizeIR, () -> {
+ _allocation = new Allocation(this);
+ if( Boolean.getBoolean("simple.alloc.dump") ) System.out.print(_allocation);
+ if( Boolean.getBoolean("simple.alloc.check") ) _allocation.requireSupported();
+ });
+ }
+ public CodeGen typeCheck() {
+ if( _phase==Phase.FinalizeIR ) allocation();
+ return phase(Phase.TypeCheck, _phase==Phase.Allocation, () -> TypeCheck.run(this));
+ }
// ---------------------------
// TypeCheck queued surviving CLInits during its existing error walk.
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 0569f352..be22e68a 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -86,6 +86,7 @@ public class ConstantNode extends TypeNode {
}
@Override public boolean isConst() { return true; }
+ @Override public boolean isFunLeaf() { return true; }
@Override public Type compute() { return _con; }
@Override public Node idealize() { return null; }
}
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/FunNode.java
index 8b6b347e..632b5fb4 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/FunNode.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/FunNode.java
@@ -83,6 +83,8 @@ public class FunNode extends RegionNode {
}
public ParmNode rpc() { return parm(0); }
+ @Override public boolean isFunLeaf() { return true; }
+
// An unloaded body's Summary is constructed before every other user.
public SummaryNode summary() { return nOuts()>0 && out(0) instanceof SummaryNode summary ? summary : null; }
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java
index 82053fd8..5e803510 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java
@@ -41,6 +41,7 @@ public class FunPtrNode extends TypeNode {
}
@Override public boolean isConst() { return true; }
+ @Override public boolean isFunLeaf() { return true; }
@Override public Type compute() {
ReturnNode ret = ret();
if( ret == null ) return _con;
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter33/src/main/java/com/seaofnodes/simple/node/Node.java
index ad4f47e0..3688d6ea 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -154,6 +154,11 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
public boolean isConst() { return false; }
+ // Stop a backward, function-local input walk here. Entry/caller links,
+ // constant anchors, and opaque summaries are not part of the local body.
+ // This is not a CFG-exit or serialization-boundary predicate.
+ public boolean isFunLeaf() { return false; }
+
// ------------------------------------------------------------------------
// Graph Node & Edge manipulation
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/ParmNode.java
index aea402f6..c61d87b7 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/ParmNode.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/ParmNode.java
@@ -49,6 +49,8 @@ public class ParmNode extends PhiNode {
public FunNode fun() { return (FunNode)in(0); }
+ @Override public boolean isFunLeaf() { return true; }
+
// The hidden constructor receiver has private memory for checking reads.
// Only borrowed source parameters need an initially empty field promise.
private Type declaredBound() {
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 36583884..bfabbb92 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -35,6 +35,8 @@ public class StartNode extends LoopNode implements MultiNode {
@Override public Tag serialTag() { return Tag.Start; }
public Type arg() { return _arg; }
+ @Override public boolean isFunLeaf() { return true; }
+
@Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) {
return p.p(label());
}
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/SummaryNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/SummaryNode.java
index 5b945457..07e16eae 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/SummaryNode.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/SummaryNode.java
@@ -20,6 +20,7 @@ public class SummaryNode extends CFGNode implements MultiNode {
}
@Override public String label() { return "Summary"; }
+ @Override public boolean isFunLeaf() { return true; }
@Override public boolean blockHead() { return true; }
@Override public Type compute() {
if( in(0)._type.isHigh() ) return TypeTuple.STATE.dual();
diff --git a/chapter33/src/test/java/com/seaofnodes/simple/Chapter33Test.java b/chapter33/src/test/java/com/seaofnodes/simple/Chapter33Test.java
new file mode 100644
index 00000000..ff313c7e
--- /dev/null
+++ b/chapter33/src/test/java/com/seaofnodes/simple/Chapter33Test.java
@@ -0,0 +1,223 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.*;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+/** Small allocation poster children. Keep calls visible: this tests summaries,
+ * not whether an inliner happens to put the allocations in the right function. */
+public class Chapter33Test {
+ private static final String THING = """
+ struct Thing {
+ i64 x;
+ new Thing = { i64 x -> self.x=x; };
+ };
+ val read_noInline = { Thing t -> t.x; };
+ """;
+
+ private static CodeGen compile(String source) {
+ return new CodeGen(source).driver(CodeGen.Phase.TypeCheck);
+ }
+
+ private static List<Allocation.Site> allocations(Allocation.Summary sum, String type) {
+ sum.requireSupported();
+ var sites = new ArrayList<Allocation.Site>();
+ for( var site : sum._sites )
+ if( site._allocation!=null && site._allocation._ts._name.endsWith("."+type) )
+ sites.add(site);
+ return sites;
+ }
+
+ // 1. A call borrows a temporary. The caller can reclaim it on return.
+ @Test public void testAllocationLocalFrame() {
+ CodeGen code = compile(THING+"""
+ val work_noInline = { i64 n ->
+ val t=new Thing(n);
+ return read_noInline(t);
+ };
+ return work_noInline(arg);
+ """);
+ var sites = allocations(code._allocation.summary("work_noInline"),"Thing");
+ assertEquals(1,sites.size());
+ assertEquals("frame",sites.get(0).destination());
+ assertEquals("17",Eval2.eval(code,17));
+ }
+
+ // 2. A factory returns a graph through another factory. Both objects need
+ // result destinations, but the final consuming caller owns them locally.
+ @Test public void testAllocationFactoryGraph() {
+ CodeGen code=compile(THING+"""
+ struct Box {
+ Thing child;
+ new Box = { Thing child -> self.child=child; };
+ };
+ val make_noInline = { i64 n -> new Box(new Thing(n)); };
+ val forward_noInline = { i64 n -> make_noInline(n); };
+ val use_noInline = { Box b -> b.child.x; };
+ val work_noInline = { i64 n -> use_noInline(forward_noInline(n)); };
+ return work_noInline(arg);
+ """);
+ for( String name : new String[]{"make_noInline","forward_noInline"} ) {
+ var sum = code._allocation.summary(name);
+ assertEquals("result",allocations(sum,"Box" ).get(0).destination());
+ assertEquals("result",allocations(sum,"Thing").get(0).destination());
+ }
+ var work = code._allocation.summary("work_noInline");
+ assertEquals("frame",allocations(work,"Box" ).get(0).destination());
+ assertEquals("frame",allocations(work,"Thing").get(0).destination());
+ assertEquals("23",Eval2.eval(code,23));
+ }
+
+ private static final String HOLDER = """
+ struct Holder { Thing !c = new Thing(0); };
+ """;
+
+ // 3. A fresh reference escapes through a parameter, not the return value.
+ @Test public void testAllocationStoreThroughArgument() {
+ CodeGen code=compile(THING+HOLDER+"""
+ val fill_noInline = { !Holder h, i64 n -> h.c = new Thing(n); return n; };
+ val work_noInline = { i64 n ->
+ val h = new Holder;
+ fill_noInline(h,n);
+ return h.c.x;
+ };
+ return work_noInline(arg);
+ """);
+ var fill = allocations(code._allocation.summary("fill_noInline"),"Thing");
+ assertEquals(1,fill.size());
+ assertEquals("arg3",fill.get(0).destination()); // arg2 is the class receiver
+ for( var site : allocations(code._allocation.summary("work_noInline"),"Thing") )
+ assertEquals("frame",site.destination());
+ assertEquals("31",Eval2.eval(code,31));
+ }
+
+ // 4. One shared factory, two call sites, two unrelated destinations.
+ @Test public void testAllocationSeparateDestinations() {
+ CodeGen code=compile(THING+HOLDER+"""
+ val make_noInline = { i64 n -> new Thing(n); };
+ val fill_noInline = { !Holder a, !Holder b, i64 n ->
+ a.c = make_noInline(n);
+ b.c = make_noInline(n+1);
+ return n;
+ };
+ val a = new Holder, b = new Holder;
+ fill_noInline(a,b,arg);
+ return a.c.x*10+b.c.x;
+ """);
+ var sites=allocations(code._allocation.summary("fill_noInline"),"Thing");
+ assertEquals(2,sites.size());
+ assertNotEquals(sites.get(0)._name,sites.get(1)._name);
+ var destinations=new ArrayList<String>();
+ for( var site : sites ) destinations.add(site.destination());
+ Collections.sort(destinations);
+ assertEquals(List.of("arg3","arg4"),destinations);
+ assertEquals("45",Eval2.eval(code,4));
+ String dump=code._allocation.toString();
+ assertTrue(dump.contains("[arg3]"));
+ assertTrue(dump.contains(".c -->"));
+ assertTrue(dump.indexOf("+-- make_noInline\n") < dump.indexOf("+-- fill_noInline\n"));
+ }
+
+ // A join requires BOTH possible owners; it must not pick whichever input
+ // happens to be visited first. Alias actual arguments at a call as well.
+ @Test public void testAllocationConditionalAndAliasedOwners() {
+ CodeGen code=compile(THING+HOLDER+"""
+ val fill_noInline = { !Holder a, !Holder b, i64 n ->
+ val h=n ? a : b;
+ h.c=new Thing(n);
+ return n;
+ };
+ val a=new Holder, b=new Holder;
+ fill_noInline(a,b,arg);
+ fill_noInline(a,a,arg+1);
+ return a.c.x;
+ """);
+ var sites=allocations(code._allocation.summary("fill_noInline"),"Thing");
+ assertEquals(1,sites.size());
+ assertEquals("arg3 & arg4",sites.get(0).destination());
+ assertEquals("8",Eval2.eval(code,7));
+ }
+
+ @Test public void testAllocationBorrowAndObjectCycle() {
+ CodeGen borrow=compile(THING+"""
+ val choose_noInline={ Thing a, Thing b, i64 n -> n ? a : b; };
+ return read_noInline(choose_noInline(new Thing(arg),new Thing(arg+1),arg));
+ """);
+ var choose=borrow._allocation.summary("choose_noInline").requireSupported();
+ assertEquals(2,choose._returns.size());
+ var destinations=new ArrayList<String>();
+ for( var site : choose._returns ) {
+ assertNull(site._allocation);
+ destinations.add(site.destination());
+ }
+ Collections.sort(destinations);
+ assertEquals(List.of("result & arg3","result & arg4"),destinations);
+ assertEquals("1",Eval2.eval(borrow,0));
+
+ CodeGen cycle=compile("""
+ struct Link { Link? !next; i64 x; new Link={ i64 n -> x=n; }; };
+ val cycle_noInline={ i64 n ->
+ val a=new Link(n), b=new Link(n+1);
+ a.next=b;
+ b.next=a;
+ return a;
+ };
+ return cycle_noInline(arg).x;
+ """);
+ var sites=allocations(cycle._allocation.summary("cycle_noInline"),"Link");
+ assertEquals(2,sites.size());
+ for( var site : sites ) assertEquals("result",site.destination());
+ assertEquals("9",Eval2.eval(cycle,9));
+ }
+
+ // Scalar results must not hide allocations when arithmetic is skipped.
+ @Test public void testAllocationScalarArrayUse() {
+ CodeGen code=compile("""
+ val work_noInline={ i64 n ->
+ val a=new i64[2];
+ a[0]=n;
+ return a[n&1]+n*n;
+ };
+ return work_noInline(arg);
+ """);
+ var sum=code._allocation.summary("work_noInline").requireSupported();
+ int arrays=0;
+ for( var site : sum._sites )
+ if( site._allocation!=null && site._allocation._ts.isAry() ) {
+ arrays++;
+ assertEquals("frame",site.destination());
+ }
+ assertEquals(1,arrays);
+ assertEquals("25",Eval2.eval(code,5));
+ assertEquals("20",Eval2.eval(code,4));
+ }
+
+ // Make unsupported plans explicit, without replacing existing TypeCheck
+ // diagnostics or changing the allocator used by older chapter tests.
+ @Test public void testAllocationRejectedPlans() {
+ String[] sources={
+ "val bad_noInline={ i64 n -> n ? bad_noInline(n-1) : 0; }; return bad_noInline(arg);",
+ "val bad_noInline={ i64 n -> i64 s=0; while(n>0) { s+=n; n--; } return s; }; return bad_noInline(arg);",
+ "val bad_noInline={ i64 n -> new int[n]; }; return bad_noInline(arg);",
+ THING+HOLDER+"val bad_noInline={ Holder h -> h.c; }; return bad_noInline(new Holder);",
+ "{ i64 -> i64 } native=\"C\"; val bad_noInline={ i64 n -> native(n); }; return bad_noInline(arg);",
+ "val bad_noInline={ -> val a=new int[2]; i64 raw=a; return raw+17; }; return bad_noInline();",
+ "val bad_noInline={ int[] a -> i64 raw=a; return raw+17; }; return bad_noInline(new int[2]);"
+ };
+ String[] reasons={"recursive", "loop destinations", "variable-size", "LoadNode", "opaque", "raw address", "raw address"};
+ for( int i=0; i<sources.length; i++ ) {
+ CodeGen code=compile(sources[i]);
+ var sum=code._allocation.summary("bad_noInline");
+ assertFalse(sum.supported());
+ assertTrue(sum._reject,sum._reject.contains(reasons[i]));
+ try { sum.requireSupported(); fail("Rejected plan was usable"); }
+ catch( IllegalStateException expected ) {
+ assertTrue(expected.getMessage().contains(reasons[i]));
+ }
+ assertTrue(code._allocation.toString().contains("REJECT:"));
+ }
+ }
+}
diff --git a/chapter33/src/test/java/com/seaofnodes/simple/PhaseTest.java b/chapter33/src/test/java/com/seaofnodes/simple/PhaseTest.java
index 6505009d..b94b4f2c 100644
--- a/chapter33/src/test/java/com/seaofnodes/simple/PhaseTest.java
+++ b/chapter33/src/test/java/com/seaofnodes/simple/PhaseTest.java
@@ -27,7 +27,7 @@ public class PhaseTest {
code.driver(Phase.TypeCheck); // A repeated request does not rerun anything.
assertEquals("45",Eval2.eval(code,10));
code.driver(Phase.LocalSched);
- assertEquals("Parse Iter Opto IterPostOpto FinalizeIR TypeCheck LoopTree Unlink Schedule LocalSched",
+ assertEquals("Parse Iter Opto IterPostOpto FinalizeIR Allocation TypeCheck LoopTree Unlink Schedule LocalSched",
String.join(" ",phases));
assertNull(code._serial);
assertNull(code._mach);
diff --git a/docs/automatic-memory-management-survey.md b/docs/automatic-memory-management-survey.md
index ffbc631c..925fb6a2 100644
--- a/docs/automatic-memory-management-survey.md
+++ b/docs/automatic-memory-management-survey.md
@@ -1,7 +1,367 @@
# Automatic memory management: design survey
-Research notes for Chapter 33, 2026-11-16. These are candidates for discussion,
-not a selected design.
+Research notes for Chapter 33, begun 2026-11-16. The base design below records
+agreed decisions. The survey and discussion that follow retain alternatives
+and earlier reasoning, including positions subsequently revised. None of the
+new runtime memory-management behavior is implemented yet. Chapter 33 now has
+an analysis-only allocation pass and small poster-child tests; see its
+[README](../chapter33/README.md#first-allocation-plans) for the supported subset.
+
+## Agreed base design — 2026-11-17
+
+Placement and array-growth decisions updated 2026-11-18. Embedded objects,
+references, and array layouts reviewed and accepted 2026-11-19; see the
+[detailed design below](#agreed-design-embedded-objects-values-and-references).
+
+- Reject programs whose lifetime safety the compiler cannot establish. Common
+ cases should need little annotation; diagnostics must identify the lifetime
+ conflict and offer a sensible restructuring or longer-lifetime choice.
+- The compiler manages ordinary stack-like lifetimes. `region`, declared only
+ at file top level, names an additional growable storage area with program
+ lifetime and no language-level size bound. Labeled scopes name lexical
+ allocation destinations, not separate growable areas. `new T(args)` infers
+ placement; `new(destination) T(args)` selects a region or lexical destination.
+ Destinations may pass through functions; the compiler must establish the
+ lexical relationship from definition to use. Transferred or independently
+ object-owned region lifetimes are not selected.
+- Free lists populated by `delete` are compiler-managed and never user-named.
+ They are distinct from allocation regions; reuse must preserve both type
+ compatibility and the requested storage lifetime.
+- Reclaiming lexical storage
+ requires proof that no usable references into it survive. This includes stale
+ references to deleted objects and references recoverable from retained fields
+ or permitted historical pointer values. Deleting an object does not discharge
+ any reference's lifetime obligation. Dead pointer bits need not be erased;
+ they must be unusable after reclamation. If safety cannot be proved, reject
+ reclamation or the enclosing lifetime arrangement. Earlier discussion of
+ named lexical pools and explicit pool deletion predates the region/scope
+ distinction; no explicit region-delete syntax has been selected.
+- Infer safe reclamation boundaries through factory layers, while letting the
+ programmer explicitly choose better groups of objects that die together.
+ Returned allocations may be assigned to caller-owned storage; retaining an
+ allocation in another object can require its storage to live at least as
+ long as that retaining object's region. Extending a borrowed object's lifetime
+ is not implicitly authorized by these allocation-destination choices.
+- Apparent unbounded growth in an inferred region is a compile-time error,
+ never a warning. A cheap explicit annotation chooses either the default
+ stack destination or an appropriate pool for that growth. Choosing the default
+ stack explicitly acknowledges retention there; it does not promise bounded
+ space or cause earlier reclamation. Choosing a pool likewise still requires
+ lifetime safety. For this growth check, repetition is significant when a loop
+ has an unknown trip bound, a known upper bound greater than 10, or involves
+ recursion. Loops bounded by at most 10 iterations are exempt from requiring
+ a growth annotation on that account. The check concerns accumulating storage,
+ not a blanket ban on allocation in large loops. This is a language check,
+ not an optional profiling report or a check whose result depends on optimizer
+ success. Syntax and details of the bound analysis remain to be specified.
+- Support the common make-and-test loop: reclaim rejected candidates each
+ iteration and retain the winner on loop exit, where analysis establishes
+ that rejected candidates do not escape. The winning exit alone must not force
+ every candidate to accumulate in an enclosing region. This applies to
+ automatic reclamation and does not require explicit delete. The compiler
+ mechanism for retaining the winning allocation graph remains to be chosen.
+- Classes explicitly opt into being deletable; the spelling is undecided.
+ `delete` permits storage recycling rather than immediately invalidating the
+ storage. Automatic reclamation still governs the enclosing region's lifetime.
+- Arrays are never user-deletable. Their storage follows automatic lifetimes.
+ A container's obsolete backing storage may be internally recycled only when
+ the compiler proves no usable references into it survive. This is distinct
+ from class-slot recycling with permitted stale references after `delete`.
+- `new E[N]` creates a fixed-length array, with N possibly computed at runtime.
+ `new E[]` starts empty and permits append with `es += elem`. Access and
+ indexed assignment are checked against the current length and do not extend
+ it. The creating scope's end finishes growth through all aliases, while the
+ storage can outlive that scope under allocation-destination inference.
+ Braces can explicitly delimit growth; an earlier end can be inferred.
+ Finishing fixes length, not element mutability. Physical placement can reserve
+ fixed allocations ahead of a growing tail without moving their construction
+ effects. Standard growable containers use embedded small vectors; arraylets
+ and dedicated address-space reservations remain optional alternatives.
+- Reads after deletion remain memory- and type-safe, but may observe permitted
+ historical values. Reuse may change any field, including final fields.
+ Mixed incarnations are possible; stale references do not require a particular
+ free-list policy or force an otherwise effect-free unused allocation to run.
+ Comparing an old reference with a replacement allocation may return equal.
+- Ordinary construction rules still apply to new objects: uninitialized fields
+ cannot be read, including indirectly through other objects. Recycled storage
+ must remain safely readable: free-list metadata is separate from readable
+ fields, and deletion/recycling must not clear fields to invalid values.
+- Disallow storing incomplete references into deletable objects. This applies
+ during their construction too, whether allocation returns fresh or recycled
+ storage. In particular, an incomplete constructor `self` cannot be stored in
+ a deletable object. A constructor may store a completed child; nested
+ allocation itself is not forbidden. More precise proofs may relax this rule
+ later, but are not required by the base design.
+- Disallow deletion through an incomplete reference, including `delete(self)`
+ while the constructor's receiver is incomplete. This avoids directly making
+ unfinished storage available for recycling.
+- Deleting an occupied slot makes it available; deleting an already available
+ slot does nothing. Deleting through an old alias after reuse deletes the
+ current occupant, whose references then acquire post-delete guarantees.
+ No incarnation check is required to diagnose the programmer's mistake.
+- Deletion of a slot currently under construction does nothing, including
+ deletion through an old completed alias. Construction tracking need only
+ exist during construction: use a short stack of pointers to active
+ constructions, checked by delete. The
+ availability bookkeeping must prevent duplicate free-list entries.
+- Writes through stale references are ordinary checked Stores to the referenced
+ slot and may modify its current occupant. A valid reference to that occupant
+ must observe those writes under ordinary memory semantics. Historical-read
+ permissions do not justify ignoring a potentially aliasing stale Store.
+ Final-field assignment restrictions, read-only access, region-lifetime checks,
+ and the prohibition on storing incomplete references remain in force.
+- Constructors for deletable classes use potentially already escaped storage,
+ with ordinary aliasable field memory from construction entry. Constructors
+ for non-deletable classes retain the existing private-construction model.
+ Incompleteness and private storage are separate properties: deletable `self`
+ remains incomplete until this construction satisfies its initialization
+ obligations, even though old aliases can access the storage.
+
+### Why deletable objects cannot retain incomplete references
+
+A recycled object initially contains valid old fields. That fact does not
+justify overwriting one of them with a reference into an unfinished, genuinely
+fresh object. A stale alias to the recycled object would expose that unfinished
+object as if it were complete.
+
+Schematic counterexample:
+
+```text
+// oldLink is complete; Link is deletable.
+delete(oldLink)
+
+// Root receives genuinely fresh storage.
+root = new Root {
+ link = new Link(self) // reuses oldLink's slot
+ helper() // reads oldLink.parent.required
+ required = some_prior_thing
+}
+
+// Link's constructor:
+new Link(parent) {
+ self.parent = parent // REJECT: parent is an incomplete Root
+}
+```
+
+The Store makes a fresh, uninitialized `Root.required` reachable through the
+completed view `oldLink`. Historical-value permissions do not authorize reading
+an invalid representation. Rejecting that Store preserves the safety promised
+to stale references without requiring runtime incarnation tracking.
+
+The earlier example with a back-reference into an already valid recycled parent
+can be physically safe. The base rule deliberately rejects it if that reference
+is still classified as incomplete. Proving continuous validity of old contents
+separately from completion of the new incarnation is a possible later refinement.
+
+### Why deletable constructors use aliasable memory
+
+An old completed reference can write a mutable field of the recycled object
+while its new constructor runs. No incomplete reference needs to escape:
+
+```text
+p = new Thing { x = 1; } // mutable x; Thing is deletable
+delete(p)
+q = new Thing {
+ x = 2;
+ overwriteOld(); // writes p.x = 3
+ print(self.x);
+}
+```
+
+If q reuses p's slot, the read through self must observe 3. Updating public
+memory in overwriteOld while forwarding 2 from unchanged private constructor
+memory would be incorrect. Constructor Stores and calls therefore participate
+in the ordinary field-memory chains from the start, including after inlining
+and through separately compiled effect summaries. Calls proven not to affect
+the field can still permit forwarding. Peepholes must not infer disjointness
+merely because pointers come from distinct recycling allocations.
+
+Old field contents do not satisfy the new incarnation's definite-initialization
+requirements. Keep construction-completeness tracking separate from memory
+privacy. Cliff suggested that withholding TMP._one might select the needed
+aliasing behavior; this is an implementation candidate to audit, not a claim
+that changing one flag is sufficient across TypeMem, constructor summaries,
+publication, and initialization checks.
+
+We choose this aliasable-memory model rather than mandatory retention of all
+constructor field values followed by bulk publication, or a blanket prohibition
+on writing other same-class objects during construction. Linked-list splicing
+after construction remains ordinary mutation. Publishing incomplete self into
+a deletable neighbor remains rejected by the separate incomplete-reference
+rule. Any later relaxation requires an additional completion proof.
+
+For final fields after publication, ordinary memory-chain reasoning can forward
+the new constructor's value to an old alias when equality is established; that
+is a permitted stale-read result. The earlier example of equal pointers with
+historical final-field values was not a new semantic obstacle. Implementation
+still needs an audit of freshness assumptions and memory-dependent value facts.
+
+### Function lifetime contracts — 2026-11-18
+
+Contracts describe lifetime relationships between arguments, results, and
+retained storage. Ordinary function definitions infer these relationships;
+separately compiled metadata exposes them to callers.
+
+- Borrowing an argument for the duration of a call does not retain it afterward.
+ Mutation is independent: sum and in-place sort can have the same lifetime
+ contract while having different memory effects.
+- A returned reference into an argument's reachable storage does not extend
+ that storage's lifetime. If the result can come from either of two arguments,
+ the caller must account for both possibilities unless it can establish which
+ applies. The arguments need not belong to the same pool.
+- Fresh results can be constructed in a caller-selected destination, with that
+ relationship propagated through factory wrappers. References retained inside
+ the new result must satisfy its destination's lifetime constraints.
+- Retaining an argument through another argument, a global, or a result is an
+ explicit part of the contract. A void result does not imply non-retention.
+- Each call must satisfy the contract, and each implementation must satisfy
+ the promises its callers use. An indirect-call interface has a common contract
+ that every permissible target must satisfy.
+- At an opaque callback interface, unspecified argument retention defaults to
+ borrowing only for the call. Retention requires an explicit contract there;
+ ordinary visible definitions can infer it. Implementations are checked against
+ this default, rather than callers blindly assuming it. Result borrowing and
+ fresh-result destinations still need their own specified or inferred rules.
+
+Functions may be specialized according to how arguments are treated. Cliff
+explicitly identifies this as an optimization, not a language design choice.
+Specialization must preserve the contract and observable behavior; program
+legality must not depend on whether specialization or inlining occurs. Exact
+syntax for retention and growth contracts, analysis representation, and metadata
+encoding remain open. Returned-borrow syntax is settled below.
+
+Native functions use the same lifetime contracts as other external functions.
+Their FFI wrapper type, written in Simple, states the borrowing, retention,
+result-lifetime, and allocation-destination promises on which Simple callers
+rely. There is no separate native lifetime mechanism. For a Simple implementation
+the compiler can check those promises against its body; for native code the
+FFI declaration is trusted. A mismatch is a bug in the binding contract or its
+implementation, not a reason to weaken the ordinary call-site lifetime rules.
+
+#### Returned-borrow syntax and FFI boundary — agreed 2026-11-19
+
+`from` introduces a result's borrowed-storage origin in a function type.
+Only arguments named in the `from` clause require parameter names; all other
+arguments may remain unnamed. For example:
+
+```text
+{ (*Complex)[] as, (*Complex)[] -> Complex from as }
+{ (*Complex)[] as, (*Complex)[] bs -> Complex from (as | bs) }
+```
+
+The first signature permits returning an interior reference such as `&as[i]`.
+The second permits either argument as the source; their lifetimes need not
+be equal. The caller accounts for all possible sources unless it can establish
+which source applies. Names in `from` must resolve to named parameters of that
+signature; no separate declaration of lifetime variables is required.
+
+For a Complex containing only numeric coordinates, returning `*Complex`
+copies the value and requires no borrowed-result relationship:
+
+```text
+{ (*Complex)[], (*Complex)[] -> *Complex }
+```
+
+Copies of object values containing reference fields still preserve those
+references' lifetime obligations. A written contract is checked against the
+body, not trusted, and does not silently extend allocations to make it fit.
+Visible bodies infer relationships when omitted; separately compiled metadata
+preserves inferred contracts. This syntax is agreed but not implemented.
+
+For now, FFI functions may not directly return borrowed interior references
+into Simple objects. Array-oriented native adapters can return an index or
+range; Simple performs checked access and forms the reference, making its
+origin visible to the compiler. Bindings returning interior field references
+are deferred until a use case warrants revisiting the restriction. This limits
+the available FFI contracts without introducing a separate lifetime system.
+
+### Still open
+
+The delete/recycling policy is largely settled above. Remaining language-design
+questions concern the automatic lifetime system:
+
+Cliff wants to settle these language choices before designing the analysis.
+"How are we tracking this?" is explicitly deferred: representation of lifetime
+constraints, path-sensitive escape information, loop-exit winners, recursive
+summaries, and reclamation checkpoints are not selected implementation designs.
+First settle the programmer-visible ownership and lifetime rules below.
+
+- Allocation-destination analysis: implement the agreed inferred placement,
+ named lexical scopes, top-level regions, and destination forwarding through
+ factories. The source-level choice is settled; tracking it remains deferred.
+- Apply the agreed growth threshold (unknown loop bound, bound greater than 10,
+ or recursion) to repeated allocation that accumulates in an inferred owner,
+ distinguishing temporary storage reclaimed each iteration or activation.
+ Specify stable bound analysis and how loop-exit winners retain storage without
+ retaining failed candidates. Apply the selected destination syntax through
+ factories without annotating every helper.
+ Errors should identify the accumulating allocation, retaining owner, and
+ repetition, then show the explicit destination choices.
+- References across regions: allowed stores, returns, and retained views;
+ proving that reclamation leaves no accessible dangling storage, including
+ historical pointer values permitted after delete. The safety obligation is
+ settled; its enforcement remains part of the deferred analysis design.
+- Remaining function-contract syntax and enforcement: returned-borrow `from`
+ syntax is settled above; retention, destination, and growth interface
+ spellings remain. Implement the agreed relationships
+ and borrowing default across direct calls, separate compilation, and indirect
+ calls, including the written FFI types for native functions. Define useful
+ diagnostics and rewrite paths when a proof fails.
+- Array-layout details: spell selectable length widths and construction/append
+ for the combined struct-and-tail type. Fixed-buffer notation, embedded object
+ access, and scope-based finishing are settled below. Any shrinking or
+ reconstruction operations need explicit reference-validity rules; they are
+ not implied by append or whole-object assignment.
+
+Implementation obligations, rather than new permission to change semantics:
+
+- Audit optimizer freshness assumptions, historical reads, pointer equality,
+ and initialization tracking under aliasable construction.
+- Implement real array bounds checks, eliminating them only with adequate
+ proofs. Cliff notes the current unchecked accesses; memory safety is an
+ intended guarantee, not a claim about the current compiler.
+- Specify concrete syntax and runtime metadata for the agreed lifetime and
+ recycling rules after the remaining lifetime choices are settled.
+
+### Node-construction check — 2026-11-17
+
+Cliff asked whether Simple's IR Nodes actually have recursive constructors,
+rather than merely nested constructor expressions in argument lists. Inspection
+of Chapter 33's Java sources found:
+
+- The ideal-IR constructors inspected do not construct other Nodes. The base
+ [Node constructor](../chapter33/src/main/java/com/seaofnodes/simple/node/Node.java)
+ creates its edge arrays and installs use edges. Constructor worklist additions
+ enqueue work rather than running peepholes recursively.
+- Some machine constructors do construct other concrete Node classes. For example,
+ [NegFX86](../chapter33/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NegFX86.java)
+ creates a ConstantNode and FltX86 inside its constructor body. ExtendX86,
+ ExtendARM, and ExtendRISC create projection/parameter nodes in delegating
+ constructor arguments. No path back into the same concrete Node constructor
+ was found in this inspection; this is not a whole-program proof.
+- `new AddNode(new MulNode(...), ...)` finishes constructing its argument before
+ entering AddNode's constructor. Reserving/protecting the outer pool slot after
+ argument evaluation avoids making that expression overlap pool construction.
+- Cyclic graph topology is distinct from recursive construction. Completed
+ Nodes can be wired into cycles afterward; deleting cyclic graph nodes need
+ not be forbidden merely to simplify construction tracking.
+- A Simple port has a separate publication issue: Node's base constructor calls
+ `n.addUse(this)` on its inputs before the concrete subclass finishes.
+ CallNode also registers itself in the global call list. If these containers
+ are deletable, they cannot retain the incomplete receiver under the base
+ rule. Moving reverse-edge wiring and registration after full construction
+ provides a straightforward rewrite, without banning graph cycles.
+
+A pool-wide busy bit cannot identify which slot is under construction. Ignoring
+all deletions in that pool while busy would be a broader semantic policy than
+the agreed per-slot rule. With at most one active construction per class-pool,
+a nullable current-slot pointer suffices to identify that object. Reentrant
+construction can instead use temporary constructor-frame records; delete can
+search those records, with cost proportional to active construction depth.
+Cliff accepted a short stack of construction pointers as the base approach;
+the single-pointer case remains a possible optimization.
+
+## Original survey
There are several approaches worth inspecting. For Simple, I would give the closest attention to inferred regions, Lobster-style ownership inference with an RC fallback, and ownership of whole object graphs. Goose is particularly useful because it shows how much cheaper memory management can become when the language constrains storage layout and lifetimes together.
@@ -432,3 +792,416 @@ Without `delete` the rules are as-is. With delete some things change:
nested iner-locking allocations.
--------------------------------------------------------
+
+## Follow-up: syntax choices — 2026-11-18
+
+There are several choices, but most should appear only where inference needs
+help. Here is the inventory, with illustrative spellings, not proposed final
+grammar.
+
+### 1. Allocation destination
+
+Keep ordinary allocation unchanged:
+
+```text
+new Thing(args) // inferred destination
+new Thing(args) in pool // explicit destination
+new Thing(args) in stack // explicitly accept default-stack retention
+```
+
+We need to decide whether destination selection attaches to one allocation,
+a surrounding block, or both. A block default would avoid repeating
+annotations, but must propagate sensibly through factory calls. Also, `stack`
+must mean the appropriate owning frame, not necessarily the frame executing
+`new`.
+
+### 2. Pool declaration and lifetime
+
+We need a way to declare a global or lexical pool and name it as a destination.
+Separate choices include:
+
+- Whether a pool serves one class or multiple types.
+- How to request a dedicated growth space.
+- Whether lexical exit is sufficient initially, or we also expose explicit
+ early reclamation.
+
+These can largely be library operations, although the compiler must understand
+their lifetime effects.
+
+### 3. Growing arrays and finishing
+
+We need to distinguish an in-place growing array from an ordinary fixed-length
+array. For example:
+
+```text
+val a = new Pixel[grow];
+a.push(pixel);
+finish(a);
+```
+
+The choices are:
+
+- A type suffix versus a constructor or builder type.
+- Whether append uses ordinary method syntax.
+- Whether `finish(a)` is a statement, or returns a fixed-length view:
+ `val b = finish(a)`.
+
+I lean toward a finish operation usable without introducing another name. It
+changes growth permission for the storage, including aliases; it does not make
+elements read-only. Existing `~` access syntax should remain separate.
+
+Appending inline objects also needs a way to construct the new element directly
+in its slot, without requiring an intermediate object and copy.
+
+### 4. Inline versus separately stored objects
+
+This is the biggest layout syntax choice. For illustration:
+
+```text
+inline Complex position; // object occupies this field's storage
+Complex other; // existing reference field
+```
+
+Should embedding be chosen per field/type use, declared as a default on
+`Complex`, or both? Per-use choice seems necessary: the same type may be
+embedded in one place and shared through a reference elsewhere.
+
+Arrays need the same distinction:
+
+```text
+Complex[] // array of references, under existing conventions
+(inline Complex)[] // array containing Complex objects
+```
+
+Those parentheses are illustrative. Whatever spelling we choose must clearly
+distinguish embedding the elements from embedding the array descriptor or a
+fixed-capacity array.
+
+### 5. Value access versus interior-reference access
+
+For embedded objects, we need to distinguish:
+
+```text
+copy of a[i]
+reference to a[i]
+```
+
+Whether those become `copy(a[i])`, `&a[i]`, an explicit reference type, or
+contextual operations is undecided. We also need assignment rules: does
+assigning an inline object copy its fields, and what happens to existing
+interior references?
+
+Container-and-index handles can probably be ordinary library types. We should
+not make the same syntax silently alternate between a direct reference and a
+handle.
+
+### 6. Lifetime and growth contracts
+
+Most relationships should be inferred, but external functions and explicit
+interfaces need spellings for:
+
+- Result borrows storage from an argument.
+- Argument may be retained in another argument or pool.
+- Fresh result uses the caller's destination.
+- Function may grow an array, only access it, or finish it.
+
+These belong in function types or associated declarations. The existing `^`
+already denotes incomplete references; I would keep that distinct from lifetime
+relationships.
+
+### 7. Deletable classes
+
+We need a class qualifier and an operation:
+
+```text
+deletable struct Thing { ... };
+delete(p);
+```
+
+The exact spelling is small compared with the rules already settled. It should
+be apparent from the type that instances permit recycling.
+
+I would choose inline/reference/value syntax first. It determines field
+declarations, array element types, construction, assignment, and function
+signatures. Allocation destinations and finish syntax are comparatively
+independent and can stay lightweight.
+
+## Agreed design: embedded objects, values, and references
+
+Proposed 2026-11-18; reviewed and accepted in full by Cliff on 2026-11-19,
+including the fixed-buffer notation. This resolves syntax items (4) and (5)
+and builds on the restored [struct-value notes](roadmap.md#struct-values).
+None of this is implemented yet; the examples describe the accepted direction,
+not programs accepted by the current parser. Array-length and trailing-array
+extensions agreed on 2026-11-19 follow at the end of this section.
+
+### Objects have storage; references identify storage
+
+Keep `T` as the existing reference type for a struct. Use `*T`, pronounced
+"contents of T", for its object value. A field of type `*T` embeds the object;
+a local or argument of that type has value semantics. Registers and scalar
+replacement remain implementation choices when an address is not observable.
+
+```text
+struct Complex { f64 x, y; };
+struct Example {
+ Complex ref; // reference to separately owned storage
+ *Complex value; // two embedded coordinates
+};
+```
+
+Embedding is chosen at the type use, not forced on every use of the class.
+An embedding cycle with no intervening reference is rejected: it would require
+an infinitely sized object. Existing access and binding modifiers remain
+independent of reference-versus-value representation.
+
+### Contents, addresses, and copying
+
+An addressable expression denotes a storage location. Reading that expression
+in a value context obtains its value; assignment writes the destination
+location; address-taking obtains a reference to the location. This distinction
+lets field access avoid first copying the whole enclosing object.
+
+```text
+Complex p = new Complex(args); // construct storage and obtain a reference
+Complex q = p; // copy reference; same target
+*Complex v = *p; // initialize a new object by copying contents
+*Complex w = v; // another object copy
+Complex r = &v; // borrow v's existing storage; no allocation
+*p = v; // copy contents into p's existing target
+```
+
+`*p` denotes the target object; `&v` denotes its address. Taking an address
+requires existing addressable storage, not an arbitrary temporary expression.
+Give a temporary a named owner before borrowing it. Nullable references must
+be proven non-null before dereferencing, following the existing safety rules.
+
+No implicit conversion changes a reference into an object copy or an object
+into a reference. `p = v` and `v = p` are type errors. A value copy copies
+embedded values recursively and copies reference fields as references; it
+does not clone the reachable object graph. Those copied references retain
+their original lifetime obligations.
+
+Field access and method syntax remain uniform: `p.x`, `v.x`, `p.len()`, and
+`v.len()`. A method on an addressable object uses that object's storage as its
+receiver; the call does not silently copy the receiver. Retaining that receiver
+is governed by the ordinary function lifetime contract.
+
+Preserve the useful binding distinction from the roadmap:
+
+```text
+holder.*c // contents of the reference field: *(holder.c)
+(*holder).c // field c of the object referenced by holder
+```
+
+These are not the same operation. Ordinary prefix `*holder.c` binds as
+`*(holder.c)`, with field selection preceding prefix dereference. The `.*`
+form makes the field being dereferenced explicit. Dereferencing an already
+inline value is an error. The old tentative alternative `ref.c = val.*c`
+would therefore not be adopted: it cannot implicitly turn a reference
+assignment into an object assignment.
+
+### Construction and assignment are separate
+
+Use `new *T(args)` for constructing an object value directly in its
+destination, alongside `new T(args)` for constructing storage and returning
+a reference. Value results may be constructed in caller-provided storage;
+the language need not require a temporary allocation and copy.
+
+Copy initialization can initialize final fields. Assignment into an existing
+object can write only fields permitted at that program point. Thus `*p = v`
+is not a back door for changing final fields or writing through read-only
+references. Initially reject whole-object assignment when it would overwrite
+protected fields; do not silently skip them.
+
+Whole-object assignment preserves the destination's identity and addresses of
+its embedded fields. Existing interior references observe the resulting normal
+field updates. Semantically obtain the source value before writing the
+destination so overlapping copies do not corrupt the source. Assignment does
+not rerun constructors or perform user-defined copy callbacks.
+
+Ending an object's lifetime and reconstructing its storage is a separate
+operation, not an alternative interpretation of assignment. In particular,
+reusing a removed vector element's slot must not invalidate surviving interior
+references or silently bypass final-field rules. General reconstruction syntax
+is outside this proposal.
+
+### Arrays distinguish element layout from element access
+
+```text
+Complex[] refs; // array of Complex references
+(*Complex)[] objects; // array of embedded Complex objects
+var a = new *Complex[N]; // allocate embedded element storage
+```
+
+Elements must still be completely initialized before exposure; the final line
+is a layout sketch, not permission to omit required initialization. Array
+initializers and append must support construction or copy initialization into
+the element destination. Only initialized elements contribute to visible length.
+
+For an embedded-element array:
+
+```text
+*Complex v = a[i]; // copy the element's value
+Complex p = &a[i]; // borrow the element's fixed storage
+a[i].x = 3; // update in place
+a[i] = v; // whole-object assignment, subject to permissions
+```
+
+For `Complex[]`, `refs[i]` copies a reference, not a Complex. For `int[]`,
+`a[i]` produces an integer value. Indexing itself therefore remains uniform;
+the element type determines what is copied in a value context. Bounds checks
+apply before access or address-taking.
+
+Use `&V` as the type of a reference to storage holding
+a value of type V. `&(*Complex)` is the existing `Complex` reference type;
+`&int` references an integer slot; `&Complex` references a slot that itself
+holds a Complex reference. This permits primitive and reference-slot borrowing
+without inventing wrapper objects. Nested references carry the corresponding
+storage lifetime constraints at each level.
+
+### Interior references borrow the actual backing storage
+
+`&a[i]` has a lifetime bounded by that particular array, not by a container
+that happens to point to it. `&owner.value` is bounded by the owner's storage.
+Creating a reference does not transfer ownership, allocate a copy, or extend
+the source lifetime. Several references may alias; no blanket exclusive-borrow
+rule is proposed. Access permissions and memory-effect rules still apply.
+
+A function returning such a reference exposes that origin in its lifetime
+contract. Functions can infer it; external declarations must state it. Exact
+contract spelling remains item (6). Ordinary direct references need not carry
+a runtime owner pointer merely because the checker tracks their origin.
+
+An array never moves. A vector may select a different backing array. A direct
+reference returned into the old array continues to identify the old element;
+replacement does not retarget it. The old storage cannot be reclaimed or
+recycled while that reference remains usable. Such a reference is not a promise
+to follow the vector's current logical element.
+
+An interface promising a stable reference to a current container element must
+instead prevent conflicting relocation during the reference's usable lifetime,
+or use a representation that preserves element storage. The implementer chooses
+the contract; it must not depend on whether this particular append happened to
+fit within capacity. Proven non-relocating operations can be allowed.
+
+A `(container, index)` handle is an ordinary library value with explicitly
+different behavior: it resolves the current storage and checks the current
+length on access. Removal or reordering may change which element it identifies;
+it does not promise persistent element identity.
+
+### Embedded small vectors
+
+The descriptor is an embedded object. Its small fixed buffer also needs an
+embedded layout. The accepted extension of the same type notation is:
+
+```text
+T[4] // reference to an array with fixed extent 4
+*(T[4]) // the fixed array itself, embedded in its owner
+(*T)[4] // reference to an array of four embedded T objects
+```
+
+The parentheses distinguish embedding the array from embedding its elements.
+An embedded array followed by other storage needs a statically known extent;
+a dynamic trailing array is the additional layout described below. The fixed
+extent can make a stored length redundant. Bounds checks still apply. This
+fixed-buffer spelling was accepted on 2026-11-19 and is not part of the older
+recovered notes.
+
+A Node can then embed vector descriptors and small arrays of Node references.
+Reading a small element needs no separately allocated descriptor or backing
+array. Overflow uses a backing pointer. Initially the fixed buffer and overflow
+pointer can coexist; sharing their bytes would require a safely discriminated
+layout, which is not needed to obtain the main indirection savings.
+
+Reference-valued `get` returns the stored Node reference and does not borrow
+the vector slot. Value-valued `get` copies the embedded element. Direct slot
+borrowing should be a separately named library operation with an explicit
+storage contract; current indexing syntax need not gain overloads to implement
+the first vector library.
+
+### Interaction with delete
+
+An embedded object cannot be independently deleted: its storage belongs to its
+owner, not to a separately recyclable slot. This must be checked from allocation
+origin even if a borrowed reference has nominal type T and T permits deletion.
+Deleting the containing object, when permitted, affects the whole slot.
+
+Consequently, an embedded child of a deletable owner inherits the possibility
+of stale aliases and reconstruction, even if the child's nominal class is not
+deletable. Its constructor cannot assume private memory merely from that class.
+The prohibition on publishing incomplete references into deletable storage
+also applies through embedded fields. Final-field reads through old interior
+references follow the containing slot's post-delete rules.
+
+Likewise, recycling a vector's old backing storage requires proving that no
+usable references remain, including references recoverable through permitted
+historical fields of a deletable owner. Merely replacing its backing pointer
+does not establish that proof.
+
+These are necessary consequences of embedding in recyclable storage, not a
+proposal to weaken the existing type-safety or initialization guarantees.
+
+### Array length is separate from element storage
+
+Agreed addition, 2026-11-19: an embedded array's logical length and its element
+data are separate layout components. Embedding must not force a four-byte
+length header immediately before every buffer. A containing object can carry
+the length separately from the inline elements. Fixed-buffer extent, a
+container's used length, and any overflow capacity remain distinct quantities.
+
+For `*(T[4])`, the array extent is the constant four. Constant propagation can
+fold uses of that extent. Eliminating the redundant physical length field is
+future work (possibly dead-field elimination); it is not part of the current
+implementation task. A vector using that buffer can still have a separate
+changing used length between zero and four.
+
+Lengths need not occupy four bytes. A short-string representation can select
+a one-byte unsigned length, for example. Each array representation has a known
+maximum element count; an unsigned one-byte length supports a maximum of 255.
+Allocation and growth must respect that maximum as well as any applicable
+storage capacity. Preventing length wrap or truncation is a consequence of
+enforcing the maximum, not a separate array rule. The length's storage width
+is part of the layout contract, and access must use that representation.
+The exact declaration spelling and conversions
+between layouts remain to be specified; a universal four-byte header must not
+be assumed by the design.
+
+### A uniform struct with an array tail
+
+Agreed addition, 2026-11-19: support a single object containing fixed named
+fields followed by a variable-length array tail. The object supports named
+field access and array access; no separately allocated backing array or wrapper
+is required. The tail is physically last and may grow until finalized under
+the same scope-based growth rules as other in-place growing arrays.
+
+The older roadmap's field notation is a useful syntax candidate, not a newly
+settled spelling:
+
+```text
+struct ShortText {
+ // Other fixed named fields may precede the tail.
+ u8 #; // compact logical length
+ u8 []; // trailing byte elements in this same object
+};
+```
+
+An unsigned one-byte length gives this representation a known maximum of 255
+elements; a wider length can support a larger maximum. An open tail has a
+changing length up to that maximum, rather than a fixed declared element count.
+Named fields retain their offsets while the tail extends. Newly
+appended elements must be initialized before becoming accessible. Indexing is
+checked against the current logical length.
+
+Finalization ends tail growth without moving the object or making its mutable
+fields read-only. The resulting storage can survive the creating scope when
+its inferred or explicit destination permits that lifetime. Interior references
+remain tied to the same storage. The layout planner must preserve room for
+physical growth; this type cannot silently relocate merely because a container
+with replaceable backing storage could do so.
+
+This generalizes embedded arrays to a dynamic final field. It does not permit
+arbitrary variable-sized fields followed by other fields, and it does not add
+array deletion. How to spell construction and append for the combined type,
+and whether any combined type may independently opt into class deletion,
+remain explicit follow-up questions; neither follows just from the layout.
diff --git a/docs/roadmap.md b/docs/roadmap.md
index 075780ad..e012eae3 100644
--- a/docs/roadmap.md
+++ b/docs/roadmap.md
@@ -372,6 +372,12 @@ design candidate, independent of compact pointer storage.
### Structs with trailing arrays
+Chapter 33 selected the combined struct-and-array layout on 2026-11-19:
+fixed named fields followed by a tail that can grow until finalized. Length
+and element storage are separate layout components, and length widths may be
+smaller than four bytes. See the [accepted design](automatic-memory-management-survey.md#array-length-is-separate-from-element-storage).
+The declarations below remain syntax sketches, not implemented features.
+
Allow named fields followed by an array length and inline element storage:
```simple
@@ -392,10 +398,10 @@ overhead. Arrays with different length representations would be distinct
types, with explicit conversions and capacity checks. The spelling and
alignment rules remain to be decided.
-Growing such an object requires a replacement allocation. An extra level of
-indirection, as in a growable-buffer wrapper, instead preserves the wrapper's
-identity. Specify ownership before treating a growing call as consuming or
-freeing its receiver.
+The selected in-place growth model preserves the object's address while its
+tail grows, then fixes its extent at finalization. It requires suitable growth
+space. A wrapper with replaceable backing storage remains a separate container
+choice; it cannot silently replace an object's stable-storage promise.
### String libraries
@@ -418,13 +424,66 @@ buffer helpers provide the basic builder and formatting operations.
### Struct values
-Allow a struct to be stored inline in another object, array, or argument list
-rather than always through a reference. A proposed `*Complex` or `inline`
-spelling would place both coordinates of `struct Complex { f64 x,y; };`
-directly in the containing value.
+The original "Structs can be inlined" proposal below is restored from commit
+`69e4a21f71aca4954469063387063434af35e679`, before the roadmap cleanup.
+Its examples retain the original syntax and proposed pointer size. The current
+Chapter 33 design allows interior references bounded by their storage's
+lifetime, superseding the older address-taking restriction below. The placement
+of `*` reflects what it binds to; the original spellings are preserved.
+
+Cliff accepted the expanded [object/value/reference design](automatic-memory-management-survey.md#agreed-design-embedded-objects-values-and-references)
+on 2026-11-19, including `*(T[4])` for embedded fixed buffers. That design is
+the current decision; the historical proposal below remains for its examples.
+
+Structs are normally by-reference, but can be converted to by-value by using
+the `*` operator, pronounced "contents of" (this name might be changed to
+e.g. `inline`).
+
+This is a name-space change only, you cannot take the address of the internal
+struct without entirely consuming its lifetime. No "escaping".
+
+```java
+// 2 64-bit words, no other overheads
+struct Complex { f64 x,y; val len = { ->Math.sqrt(x*x+y*y); }; };
-Define whole-value copying, reference-to-value conversion, and assignment
-through an existing reference. A value must not silently become a reference
-or expose an interior address with an invalid lifetime. Decide how consuming
-an enclosing object's lifetime could permit such an address. Keep method
-syntax uniform and define the calling convention for by-value arguments.
+// Current Simple rules: always by-reference
+struct ByRef {
+ !Complex !c; // 4-byte pointer to a Complex
+};
+print(new ByRef.c.y); // Lookup requires 1 extra memory load from ref to c
+
+// New behavior: by value (inlining a struct)
+// The '*' syntax indicator can be something else, e.g. a keyword "inline"
+// I am pronouncing '*' as "contents of"
+struct ByValue {
+ *!Complex !c; // c is inlined, full 16 bytes into ByValue
+};
+print(new ByValue.c.y); // x,y inlined into ByValue, no extra memory load
+
+// Mixing Refs and Struct Values. Basically, a ref can be converted
+// to a value by taking the "contents of" the ref, and values cannot
+// be *converted* to a ref, although they can be copied over a ref.
+ref. c = val.c; // Error, mixing refs and values
+ref.*c = val.c; // Allowed, whole structure copy. Does not allocate, requires ref.c not-null
+val. c = ref.c; // Error, mixing refs and values
+val. c = *ref.c; // Allowed, whole structure copy
+ref. c = ref.c; // Allowed, pointer copy
+val. c = val.c; // Allowed, whole structure copy.
+val *c = val.c; // Error, cannot take "contents of" a value
+
+// Alternative syntax, to avoid the "contents of" being on LHS and field applying to being on RHS:
+ref.c = val.*c; // Assign into ref.c the "contents of" val.c
+
+// Arrays of inlined structures
+var ary = new *Complex[99]; // Array of 99 !Complex !objects, inlined
+
+// Calling methods has the same syntax
+ref.c.len();
+val.c.len();
+
+// Function arguments use the same typing, so can pass-by-value
+val math.sin = { *Complex c -> ... }; // Passes a complex by value
+math.sin(ref.*c); // Requires de-reference to pass by value
+math.sin(val. c); // Pass by value
+
+```
diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md
index 5ba1943c..2c327292 100644
--- a/skills/chapter25-codex-notes.md
+++ b/skills/chapter25-codex-notes.md
@@ -37,9 +37,77 @@ callers promise no initialized fields. No new passes or backward demand walks.
Cliff closed Chapter 32 and requested `ch32` rebased onto `main`, then a new
complete snapshot on branch `ch33`. Continue in `chapter33/`. Cliff selected
-automatic memory management as the next topic, with the design still open.
-The latest request is cleanup and preparation for that task, not implementation.
-Do not treat earlier roadmap sketches as a chosen lifetime mechanism.
+automatic memory management as the next topic. On 2026-11-19 Cliff requested
+the first analysis pass after Opto and before TypeCheck, few new classes,
+ASCII debugging, conservative rejections, and 3-4 poster children. The agreed decisions and remaining
+questions are in [the survey's base design](../docs/automatic-memory-management-survey.md#agreed-base-design--2026-11-17).
+The initial implementation is `codegen/Allocation.java`, after FinalizeIR and
+before TypeCheck. One call-DAG DFS composes symbolic summaries in postorder;
+local reference-edge closure uses a worklist. Four poster children and boundary
+checks live in Chapter33Test. The phase is analysis-only: existing allocation
+lowering is unchanged. `simple.alloc.dump` prints ASCII, `simple.alloc.check`
+requires all plans to be supported; otherwise unsupported summaries record a
+rejection without blocking the existing allocator. Loops, SCCs, variable sizes,
+opaque calls, raw addresses, and unresolved pointer-load origins are deferred.
+No new language syntax or serialized lifetime summaries are implemented yet.
+Update 2026-11-19: Cliff accepted the entire
+[embedded-object design](../docs/automatic-memory-management-survey.md#agreed-design-embedded-objects-values-and-references),
+including `*T` object values, `&` interior references, and `*(T[4])` embedded
+fixed buffers. Length and element storage are separate layout components;
+length widths may be smaller than four bytes. Each array representation has a
+known maximum element count; preventing length wrap follows from enforcing
+that maximum, rather than being the primary semantic rule. Removing constant length fields
+is future work, not an implementation request. A uniform struct with fixed
+named fields and a growing final array tail is also selected; exact tail and
+length-width syntax remains open. The tail grows until scope-based finishing.
+Placement uses `new(destination) T(args)`; `region` declarations are top-level
+only and denote program-lifetime storage with no language-level size bound.
+Labeled scopes supply lexical destinations. Free lists from delete are compiler
+internals, not user-visible pools. These distinctions supersede older pool
+terminology below. `new E[]` begins growth, `es += e` appends, and the creating
+scope's end finishes growth without necessarily ending storage lifetime.
+Obsolete backing arrays can be internally recycled only after proving no usable
+references survive; arrays still have no user delete operation.
+Classes opt into deletion/recycling; stale reads remain type-safe but can see
+historical field values, including finals. Incomplete references cannot be
+stored into deletable objects, including during construction. Arrays are never
+deletable; do not reintroduce array delete/reuse free lists. Non-moving growable
+arrays are a separate requested discussion topic. Deletable
+constructors use ordinary aliasable memory from entry, while non-deletable
+constructors retain private memory. Keep initialization obligations separate
+from storage privacy; withholding TMP._one is a suggested implementation route
+to audit, not a verified sufficient change. Preserve these decisions; older
+discussion in the survey includes superseded assumptions.
+Do not treat other roadmap sketches as chosen mechanisms.
+Pools have global or shorter lexical lifetimes (2026-11-18 decision), rather
+than transferred/object-owned lifetimes. Global pools retain their storage.
+Pool reclamation requires proving all usable references gone, including stale
+references after object delete and reachable historical pointer values. Object
+delete never waives the region-lifetime proof. Analysis design remains deferred.
+Function lifetime contracts infer borrowing, result origins/destinations, and
+retention for ordinary definitions; opaque callback interfaces default to
+borrowing arguments for the call, with retention explicit and implementations
+checked. Result contracts remain necessary. Specializing functions by argument
+treatment is an optional optimization, never a condition of language legality.
+Native functions use the same external lifetime contracts: their written Simple
+FFI type supplies trusted promises that the native implementation must honor.
+No separate native lifetime mechanism is needed; mismatches are binding or
+implementation bugs.
+Returned-borrow syntax agreed 2026-11-19: function result `T from arg`, or
+`T from (a | b)` for alternative origins. Only arguments mentioned in `from`
+need names in the function type; other parameters may remain unnamed. `T` is
+a struct reference, while `*T` is an object value. Bodies infer contracts or
+are checked against written ones; annotations do not silently extend storage.
+For now FFI cannot directly return borrowed interior references into Simple
+objects. Native array adapters return indices/ranges and Simple constructs
+checked interior references. Field-reference FFI returns are deferred.
+Apparent unbounded growth under inferred lifetimes must be an error, never a
+warning or merely a report. The user fixes it with a cheap explicit choice of
+the default stack destination or an appropriate pool. Neither annotation waives
+lifetime safety. Growth-check repetition means an unknown loop bound, a known
+upper bound greater than 10, or recursion; small bounded loops are exempt on
+that account. Support make-and-test loops retaining only the winner, where
+failed candidates provably do not escape. Syntax and implementation remain open.
Preserve Chapter 32's compiler and performance narrative.
The test commands and invariants below also apply to Chapter 33.
@@ -332,6 +400,8 @@ and a small game with graphics, keyboard input, and sound.
## Collaboration preferences
+- Avoid Java streams; Cliff finds ordinary loops easier to read, including in tests.
+
- For densely keyed integer maps, use indexed `Ary<T>` storage rather than
`HashMap<Integer,T>`.
- Build with Make alone; Maven must never be required. Cliff prefers few tests: