Memory management / Retained Edge Counting
REC is a physical representation, not source semantics. Moth has no source-visible reference counting, and no program can name, observe or request a counter.
REC covers one narrow case: an allocation family whose persistent retained-edge count is only known at runtime, whose edges disappear independently, and cannot be reclaimed precisely enough through affine last-use analysis, inferred cleanup-frontier regions, field-sensitive splitting or declared regions. Accepted design with implementation deferred.
Retained Edge Counting, abbreviated REC, is a selective physical representation for allocation families with unresolved runtime-many persistent retained edges that can disappear independently. The compiler-owned memory planner selects REC only after static and region-based mechanisms have been exhausted.
REC is a physical representation, not source semantics. Moth has no source-visible reference counting, no counter type, no retain or release syntax and no way for a program to observe a count.
The ownership boundary has three layers:
Accepted end-state design with implementation deferred. This page is the canonical technical authority for REC inside the memory model. Sequencing and active work items live in docs/roadmap/roadmap.md. Current implementation support lives in the progress matrix.
Last-use analysis, affine cleanup responsibility and inferred regions handle most values without any runtime bookkeeping. REC covers the remaining narrow case:
> A runtime-dependent number of persistent retained edges can point to one allocation family, those edges can disappear independently, and the narrowest statically proven region would otherwise retain substantial storage materially beyond its useful lifetime.
REC is not general reference counting. It does not count ordinary aliases, it does not establish lifetime legality and it does not permit cycles. Cycles remain legal only inside one declared region, and declared-region-owned allocations are always count-free.
The semantic allocation root that must be kept alive as one unit under the current field-splitting result. A projection may point inside an allocation family while cleanup still targets the family root.
A stored reference that keeps an allocation alive beyond the current expression. Local aliases, parameters, temporary projections and get() borrows are not retained edges.
The set of retained edges owned by one container or aggregate, such as the element edges of one collection.
A retained-edge count that is not statically known because it depends on runtime control flow or data.
A CFG point after which every relevant retained edge into an allocation family is proven gone.
An allocation family with dynamic retained multiplicity whose edges can disappear independently.
The single optional cleanup obligation carried by an owned handle on the current path.
One counted obligation held by a stored retained edge.
REC is the fifth of the six cooperating mechanisms described in the memory overview. This page defines the representation contract and its handoff boundaries. It does not turn semantic facts into physical decisions or ask lowering to reconstruct them.
Builtin fixed and growable collections are Moth's trusted dynamic-storage substrate. Their memory effects are compiler-known.
Each stored value contributes a retained-edge summary. A scalar such as Int can contribute zero obligations. An ordinary heap-backed value can contribute one direct obligation. An inline aggregate that physically stores several handles can contribute several direct obligations from one storage operation. A summary may also describe nested retention, such as the references a stored Holder itself holds, so the compiler knows what a value structurally contains.
Nested or transitive retention summaries are analysis descriptions. REC obligations count actual direct persistent edges between the final allocation families and retention domains. Reachability through a separately allocated child is never counted again.
The compiler-owned memory planner resolves final counted obligations after applicable field-sensitive splitting and physical layout refinement, once the direct family-edge graph for the physical variant is known. A storage operation adds or removes the complete set of direct obligations contributed by the stored value. It does not assume that one element means one edge, and one element may still produce several direct edges when its inline representation stores several handles.
The table describes the successful semantic path. Fallible operations publish their retention effects only at their commit point.
Operation | Retained-edge effect |
|---|---|
| creates a statically bounded temporary alias. It adds no persistent obligation. |
| adds the inserted element's retained-edge obligations |
| removes the replaced element's obligations and adds the new element's obligations |
| removes the stored element's obligations and returns the existing value as a detached stored result |
| removes the obligations contributed by every stored element |
collection destruction | removes all element obligations and destroys the backing-storage domain |
growth or reallocation | replaces backing storage while preserving logical element summaries |
For the initial direct-handle implementation, an element commonly contributes zero or one direct obligation. The semantic vocabulary stays general so aggregate and nested retention can use the same summaries.
Consider a collection of Holder values where each Holder refers to a Blob.
collection -> Holder family -> Blob familyIf Holder is a separately allocated family, the direct family-edge graph is:
collection -> Holder
Holder -> BlobInserting a Holder adds one direct obligation into the Holder family. It does not add a second collection -> Blob obligation. The Blob family is reachable from the collection, but the edge that keeps it alive is owned by Holder, and Holder releases it when Holder is destroyed.
If layout refinement instead places Holder inline in the collection's backing storage and that inline representation contains a Blob handle, the direct graph becomes:
collection storage -> BlobThat is a direct edge from the collection's retention domain, so it does contribute an obligation into the Blob family.
The obligation count therefore follows the post-refinement direct graph, never structural reachability. Counting Blob twice merely because it is transitively reachable from the collection is always wrong.
A builtin collection mutation commits its retained-edge effects atomically on the successful path. A failed operation preserves the original storage topology and the retained-edge obligations that topology holds. An incoming affine responsibility is not part of that topology: it follows the transfer or discharge path planned for the failure outcome. HIR represents these outcomes as explicit control-flow paths, so summary facts must remain exit-specific:
```text success: remove old obligations add new obligations
error: retain the original obligations ```
Invalid-index remove destroys no obligation. A failed fixed-capacity push adds none. A failed set leaves the old element in place. A failed map insertion retains neither the incoming key nor the incoming value. Count changes happen after the operation reaches its semantic commit point.
A fallible operation receives affine responsibility only when last-use analysis proves transfer safe across every relevant outcome. If a failure path still uses the incoming value, the operation receives a borrow. A failed operation commits no retained edge, so no ownership-return protocol is required.
This is ordinary all-path transfer proof, not a bespoke mechanism. When transfer was legal on every outcome, the failure path simply holds an affine obligation that it may discharge normally; the original storage topology is unchanged either way.
Maps retain both stored keys and stored values. Replacing an existing key keeps the stored key and changes only the stored value. The lookup key supplied to an existing-key set, get, contains or remove call remains a temporary borrowed alias unless the operation inserts it as a new stored key.
Operation | Retained-edge effect |
|---|---|
| creates a temporary lookup alias and adds no persistent obligation |
new-key | adds the stored key's obligations and the new value's obligations |
existing-key | keeps the existing stored key, removes the old value's obligations and adds the new value's obligations. The incoming lookup key is not retained |
| removes the stored key's and stored value's obligations. The value becomes a detached stored result, but the stored key does not |
| removes all stored key and value obligations |
map destruction | removes all stored key and value obligations and destroys the backing-storage domain |
Consider a map whose key and value point to the same allocation family:
text = [: large value]
values ~{String = String} = {}
~values.set(text, text)! -- final use of text
removed = ~values.remove("large value")!The new-key insertion creates two direct persistent obligations to the same allocation family, one from the stored key and one from the stored value. Because this was the final use of text, its affine root can be reclassified into exactly one of those two edges. The second edge is a genuinely new obligation.
fresh text root:
affine root = 1
persistent edges = 0
count = 1
after final-use new-key set:
affine root = 0
stored key edge = 1
stored value edge = 1
count = 2
after remove:
stored key edge disappears
stored value edge becomes returned affine root
count = 1Removal drops the stored key obligation and reclassifies the stored value obligation into the returned result's affine root when the caller receives affine responsibility. One removed edge can reclassify into the returned root; the other simply disappears.
The lookup string passed to remove is a temporary borrowed alias. It is not another obligation to the stored family. If the mutation fails, neither stored obligation changes.
The compiler does not recognise user methods by name. A user abstraction earns an equivalent summary by composing builtin effects, and only when analysis proves every relevant edge is killed on every path.
clear |this ~UserIndex|:
~this.values.clear()
this.count = 0
;If values is the only field retaining indexed elements, the compiler may infer that this method kills the whole element-retention domain. A handwritten slot-clearing loop remains valid source, but it receives the strong summary only when the proof succeeds.
Future collection APIs must preserve narrow, analysable destruction effects.
remove returns a detached stored result. It is neither a fresh result nor an ordinary alias return. The existing allocation survives while the collection stops retaining it.
before: collection -> stored value
after: collection -X-> stored value
result -> stored valueThe summary vocabulary preserves this distinction so a caller can receive affine cleanup responsibility, keep a borrowed alias under another owner, or reclassify the removed value's persistent obligations into the returned result. This applies to maps, collections, stacks, queues, deques, caches and other container detachment operations.
Container detachment differs from declared-region extraction or adoption, which would move a declared-region-owned allocation family outside its declared region. It also differs from interior projection detachment, which would separate a field from its containing allocation family. Declared-region extraction and adoption remain forbidden in V1. Interior projection detachment remains deferred until field-sensitive splitting has established separate ownership. The restriction on extraction means moving a declared-region-owned allocation out of its declared region or retroactively detaching an interior projection from its allocation family. It does not prohibit builtin collection or map remove, which kills a container-retained edge and returns the already-stored value under ordinary lifetime rules.
The memory-strategy planner uses this order and stops at the first mechanism that answers. The ladder supplies REC candidates and elision reasons. It does not move strategy ownership into this page.
config.moth contract.Every REC family keeps its statically proven fallback lifetime region. REC can only reclaim that family earlier than the fallback region frontier. If counting did not exist or failed to improve precision, the static region would still make the program collector-free and correct.
The selected representation remains fixed for the allocation family. An uncounted strategy never upgrades to REC at runtime, and an REC-selected strategy never abandons counting or downgrades to an uncounted representation at runtime.
The cleanup-frontier case is the most common elision:
populate(~index)
use(index)
~index.clear()The collection may continue living. If no other live alias or retention domain can retain a target allocation family, clear() can become that family's final cleanup frontier. The collection itself may continue to live. For declared-region-owned storage, clear() kills the declared region's collection edges logically, but the declared region still keeps its allocation storage until declared-region exit and no REC counter applies.
A final cleanup frontier for family A requires proof that:
A from the relevant domains is gone on that pathAA after the pointA long-lived collection may therefore create several inferred epochs, while the collection object and its backing capacity outlive each retained-value epoch.
R_index_epoch_0
population 0
-> first clear
R_index_epoch_1
population 1
-> second clearIndividual remove, set or partial cleanup does not establish a frontier by itself. Uniqueness scans, alias registries and adaptive owner recovery are rejected from the design.
Full-memory-control backends use a two-bit tagged allocation-family handle for heap values that participate in ownership-aware lowering.
bit 0: OWNED
bit 1: RECBits | Meaning |
|---|---|
| uncounted borrowed handle |
| uncounted affine-owned handle |
| REC-managed borrowed handle or counted persistent edge |
| REC-managed affine-owned handle |
The REC bit identifies the target allocation family's physical layout. It does not by itself say that this particular handle contributed one count. A temporary borrowed get() result may carry 10 while adding no obligation. The planner's transition for the operation that stores or removes a persistent edge determines count changes.
A backend masks both bits before recovering the allocation-family base.
family_base = handle & !TAG_MASKInvariants:
10.11.10 while the caller retains 11.11 without changing the counter.The tags belong to the allocation-family handle, not to an arbitrary interior address. A projection must carry the family base alongside its offset, use a canonical handle that can recover the base, or use another representation preserving the same two logical bits and family identity. Masking an arbitrary interior pointer is not sufficient.
The planner selects the layout before code generation. An uncounted allocation is never upgraded to REC at runtime, and a REC-selected allocation never downgrades to an uncounted representation at runtime.
Only REC-selected allocation families carry a counter. There is no global side table and no universal header on affine, inferred-region or declared-region allocations.
+-----------------------+
| REC count word |
+-----------------------+
| allocation-family data|
+-----------------------+u32 on Wasm32 and u64 on ordinary 64-bit native targetsREC is selected because unresolved runtime-many persistent retained edges disappear independently. That selection reason is distinct from the complete physical counter invariant. For one REC-selected allocation family F, the counter carries both the counted persistent-edge obligations and at most one affine-root obligation:
REC count(F) =
live counted persistent-edge obligations(F)
+ optional affine-root obligation(F)The affine-root term is zero or one. Ordinary aliases, parameters, temporary projections and get() results never contribute obligations. Read-only call borrows, statically known region-only edges and declared-region-owned edges also contribute no obligations.
The counter is not the number of source aliases. An affine transfer moves an existing root obligation to another path and causes no count change by itself.
Retained-edge analysis owns the semantic facts for a retention-sensitive operation: which direct persistent edges it creates or removes, their cardinality, outcome-specific commit effects, whole-domain kills and detached stored-result provenance. It does not choose physical counter updates.
For each REC-selected family, the compiler-owned memory planner converts those facts into a concrete transition. Semantic-commit fusion and per-family normalisation are mandatory planner work performed before lowering. The planner applies root-to-edge and edge-to-root reclassification, fuses effects by target family and computes the complete transition before handing it to the backend.
This equation is the normative per-family contract:
delta_count =
created_persistent_edges
- removed_persistent_edges
+ affine_root_after
- affine_root_beforeFor one family F, the terms mean:
created_persistent_edges is the number of direct persistent edges into F that this semantic commit stores.removed_persistent_edges is the number of direct persistent edges into F that this semantic commit removes.affine_root_before is 1 when an owned affine root for F exists on the incoming path, otherwise 0.affine_root_after is 1 when an owned affine root for F exists on the outgoing path, otherwise 0.affine_root_before in {0, 1}
affine_root_after in {0, 1}The conceptual planner handoff has this shape:
pub struct PlannedObligationTransition {
pub family: PhysicalAllocationFamilyId,
pub removed_persistent_edges: u32,
pub created_persistent_edges: u32,
pub affine_root_before: bool,
pub affine_root_after: bool,
}The exact Rust names remain open. The ownership boundary does not. Backend REC lowering receives the planner's transitions and encodes the required tag, counter and destruction operations. It never reconstructs or independently decides a count transition.
Same-family replacement.
A replacement that removes one direct persistent edge and creates another direct persistent edge into the same family has a net-zero transition:
same-family replacement:
removed_persistent_edges = 1
created_persistent_edges = 1
affine root unchanged
delta_count = 0The planner fuses the remove and add at the semantic commit. The backend must never emit a transient decrement-to-zero followed by an increment for this replacement. Destruction is tested only after the complete fused transition for the family is known.
Final-use insertion.
When a final-use affine root is stored as one direct persistent edge, the planner reclassifies that root into the edge:
final-use insertion of one direct edge:
before:
created_persistent_edges = 0
removed_persistent_edges = 0
affine_root_before = 1
after:
created_persistent_edges = 1
removed_persistent_edges = 0
affine_root_after = 0
delta_count = +1 - 1 = 0This one-edge reclassification may have zero net counter traffic. One affine root can replace at most one newly created direct persistent edge. If the operation creates N direct edges, only one can be reclassified and the remaining N - 1 obligations produce the net increase.
Detached results.
When a detached stored result turns one removed direct persistent edge into an affine result root, the planner reclassifies the edge into the result:
detached result of one direct edge:
before:
created_persistent_edges = 0
removed_persistent_edges = 1
affine_root_before = 0
after:
created_persistent_edges = 0
removed_persistent_edges = 0
affine_root_after = 1
delta_count = +1 - 1 = 0This one-edge reclassification may have zero net counter traffic. At most one removed edge can become the returned affine root. If detachment removes N direct edges, the remaining N - 1 obligations disappear and the net delta is 1 - N. If the returned value remains borrowed while another affine root already exists, no edge-to-root reclassification occurs.
Hidden destinations.
Fresh construction into a hidden destination that is known to become one direct persistent edge may start directly with that obligation:
fresh hidden-destination construction:
created_persistent_edges = 1
affine_root_before = 0
affine_root_after = 0
initial count = 1The planner need not create an affine root and then remove it. The backend encodes the planned initial persistent obligation.
An affine transfer moves an existing root obligation between paths. The root remains present before and after the transfer, so the transition has zero count change by itself.
A semantic storage mutation commits its complete obligation delta atomically for each target family. The planner must normalise every effect before lowering and must not model an overwrite as a decrement, a possible destruction and then an increment when the semantic operation replaces one obligation with another obligation to the same family.
same target family F:
old edge removed -1
new edge created +1
---------------------
net transition 0Temporary aliases cannot race the count to zero, because borrow validation already guarantees that a persistent edge or affine root cannot be destroyed while a dependent temporary borrow remains usable. REC relies on that existing proof rather than adding a second safety mechanism.
This table is a shorthand for the planner's normalised per-family transitions. N is the number of direct persistent edges into the target family F that the operation creates or removes. In the common direct-handle case N is 1.
Operation | Counter effect | Handle effect |
|---|---|---|
ordinary local alias | | borrowed alias, no new obligation |
borrowed function call | | callee receives owned bit clear |
affine root transfer | | |
persistent insertion while affine root remains | | stored edge obligations use |
final-use insertion | | one root obligation becomes a stored |
| | returns a temporary |
persistent removal with no returned root | | obligations disappear |
detachment producing an affine root | | one removed obligation becomes an |
detachment while an affine root already remains | | returned value is borrowed |
affine root discharge | | owned path discharged, family destroyed only if the count reaches zero |
overwrite | planner computes one atomic per-family before/after delta | old summary disappears, new summary appears |
whole-domain clear | one release per surviving external counted-edge obligation unless region elision applies | domain obligations disappear |
count reaches zero | destroy exactly once | no usable handles remain |
The one-edge fast path stays cheap and remains the common case:
N = 1 final-use insertion -> 0
N = 1 extraction to root -> 0These 0 results are scoped to N = 1. There is no unconditional general rule that final-use insertion or extraction to an affine root leaves the count unchanged.
blob = load_blob()!
~index.set("a", blob)!
use(blob)
~index.set("b", blob)! -- final use of blobstart:
root
count 1
after "a":
root + one edge
count 2
after final-use "b":
two persistent edges
count 2REC did not replace last-use analysis here. Last-use analysis allowed one obligation to change category from affine root to persistent edge, so the second insertion produced no new count traffic.
A fresh REC allocation returned with affine cleanup responsibility starts at count = 1 with tag 11. One constructed directly into a counted persistent edge may start at count = 1 with stored tag 10, so hidden destination allocation need not create and remove a temporary root.
Keep these terms distinct:
For an REC family, discharge_if_owned discharges the affine-root obligation. It destroys the family only when that discharge makes the count zero.
discharge owned REC root
-> remove one affine-root obligation
-> decrement count by one
if count > 0:
family remains alive
if count == 0:
destroy familyDischarging an owned REC root therefore does not necessarily destroy or free the family. Surviving counted persistent edges keep it alive.
Declared-region ownership affects the target allocation, not every edge whose source happens to live inside a declared region.
Declared region G -> declared-region-owned F
count-free
Declared region G -> external REC F
counted persistent edge into FA retained edge whose target is declared-region-owned needs no counted obligation, because the declared region's hard bulk lifetime already covers it. A retained edge stored inside declared-region-owned storage whose target is an externally owned REC family is an ordinary counted persistent edge into that external family.
A clear() on declared-region-owned storage releases the outgoing REC boundary obligations that the cleared entries held. It does not reclaim the declared-region-owned storage itself, which lives until the region exits.
Declared-region exit runs both steps in order:
release outgoing REC boundary obligations
-> bulk reclaim declared-region-owned storageThe external target is destroyed only if its own count reaches zero. Declared-region count-free semantics never mean that every allocation referenced from a declared region is count-free.
Counted destruction is iterative through a deletion worklist, never recursive through the native or Wasm stack. Reaching zero destroys the family exactly once. Because cycles are legal only inside declared regions and declared-region-owned allocations are count-free, a counted family can never be kept alive by a cycle, and no cycle collector is required.
Mixed cleanup is expected: one inferred-region exit may release counted edges, and one counted destruction may end a family that also owns inferred-region-allocated or declared-region-external storage.
REC may cross Moth function and package boundaries, but only retention-sensitive and cleanup-sensitive operations inspect bit 1 of the REC representation. Read-only calls and temporary-borrow operations do not inspect it and cause no count traffic. Whole-function REC and non-REC specialisation is rejected as a default. Mixed call paths use one body with local tag handling only around retention-sensitive or cleanup-sensitive operations.
REC representation is physical-variant state. One source function may be lowered with a host GC-native representation in one target/profile variant and with the two-bit REC-capable ABI in another, without any difference in source semantics or in its public semantic interface. When the REC state is statically known, local specialisation may remove the corresponding tag test. This does not require whole-function duplication.
Public semantic interfaces describe aliasing, retention, detached stored results, cardinality, whole-domain kills and outcome-sensitive cleanup effects. They stay REC-free: they never expose REC as source semantics, and donor-local family, region, counter and concrete-frontier identities never cross module boundaries.
Ordinary foreign boundaries remain closed and value-only. REC does not create a cross-language shared-reference protocol.
get() borrows cause no counter traffic.These remain for the later implementation plan and benchmarks:
The likely costs may include target-header cache-line writes, small-object overhead and destruction bursts. These choices must not become unmeasured heuristics in source or configuration semantics.