Understanding memory
The previous chapter showed the rules: .copy(), mut
and &, sink, using. This one shows what is behind them: where a value
lives, who owns it, and when its memory is freed. Weaver has no garbage
collector, no lifetimes to write, and counts references only where the code
says that a value is shared. These pages are how that holds together.
Every memory model answers the same question: who frees, and when?
| Language | Who frees | When |
|---|---|---|
| C | the programmer | wherever they think it is over: leaks, double frees, use after free |
| C++, Rust | the compiler | at the end of the owner’s scope; Rust checks that no reference outlives it, through lifetimes |
| Swift | the reference count | at the last release, known only when the program runs |
| Java, Go | the garbage collector | later, in a pause or a background thread |
| Weaver | the compiler | at the end of the owner’s scope; at the last release for what is declared shared |
Weaver frees like C++ and Rust, at a point that reads in the text. It needs no lifetimes, because a reference never outlives the call or the block that made it, and it falls back on counting only where the code declares a value shared.
Where a value lives
Section titled “Where a value lives”A value is made of parts. Scalars, and records or tuples made only of
scalars, live in place: in a variable’s slot on the stack, or inside the
value that contains them. What can grow, the characters of a String, the
elements of an array, the entries of a Map, lives in a block on the
heap, which the value holds by a pointer.
Copying a value without a heap part costs what moving it costs, a few bytes: Weaver copies those freely, without anything written. Everything below is about blocks: who owns them, and when they are freed.
One owner, freed at the end of its scope
Section titled “One owner, freed at the end of its scope”Every block has one owner: a binding, a parameter received with sink,
or the value that contains it. The block is freed when its owner’s scope
ends, in the reverse order of the bindings, as C++ destroys its objects:
fn longest(path: String): Int ! IoError { val text = Fs.readText(path)! // allocates text val lines = text.split("\n") // allocates lines return lines.map(l => l.byteLen()).max() ?? 0} // frees lines, then textThat nesting is the whole proof. On one thread, a caller’s scope encloses its callee’s, and a block’s encloses its inner blocks’. A value borrowed from an inner scope, a parameter, a loop variable, a lambda called during a call, is therefore always alive while it is borrowed. Rust needs lifetimes to prove the same thing about references that may be stored anywhere; in Weaver, a reference is never stored in an object nor returned, so the scopes are enough.
A resource follows the same rule, and makes it visible: here each release is printed.
import weaver.io.print
/// A resource that says when it is released.type Probe = { name: String }
impl Disposable for Probe { fn dispose(sink self) { print(" release ${self.name}") }}
fn keep(using p: Probe) { print(" keep() has ${p.name}")}
fn main() { using a = Probe{name: "a"} print("block starts") { using b = Probe{name: "b"} using c = Probe{name: "c"} print("block ends") } using d = Probe{name: "d"} keep(d) print("main ends")}block startsblock ends release c release b keep() has d release dmain ends release ad is given up to keep, which becomes its owner: it is released at the
end of keep, not of main. Memory moves the same way, only silently.
An assignment moves or borrows, never copies
Section titled “An assignment moves or borrows, never copies”val b = a never duplicates a block. What it does depends on whether a is
used afterwards:
.copy().import weaver.io.print
fn main() { val draft = mut ["intro"] val book = mut draft // draft is not used again: its block moves to book book.push("body") val backup = book.copy() // a second block, written in the text book.push("index") print("${backup}") print("${book}")}["intro", "body"]["intro", "body", "index"]Add a later read of draft, print("${draft}") at the end, and book
can no longer own the block: it borrows it, and modifying it is refused,
with the fix:
main.wft:5:24: the binding is modified, and its value is another's: write `.copy()` (memory-model.md)This is why a modification is never seen “at a distance”: two names never designate the same block when one of them can write to it. And a copy is never hidden in an assignment, where it would cost a whole block without a trace: adding a read further down turns a move into a borrow, and a write into an error, never into a silent copy.
Calls: read, modify, give up
Section titled “Calls: read, modify, give up”A parameter says what the callee does with the argument, and the call says it again when the argument is modified:
sink changes its owner.| Parameter | Call | The callee | The block |
|---|---|---|---|
u: User |
show(u) |
reads it | stays the caller’s, not copied |
xs: mut Int[] |
grow(&xs) |
modifies its content in place | stays the caller’s |
sink xs: String[] |
keep(xs) |
owns it | freed by the callee, or passed on |
-
mutmodifies, never replaces.xs.push(x)andxs[i] = vchange the content the caller lent;xs = []is refused, so that a caller’s variable never changes behind its back:`xs` is a `mut` parameter: its content is modified, the value is not replaced; return the new value, which the caller stores -
Giving up what you still use is an error. Passing a value as
sinkand reading it afterwards would read a block the callee may have freed:the value is given up while it still serves: write `.copy()` (memory-model.md)
The signature is all the compiler needs to know about a callee. Whether code compiles, and where its frees and copies go, never depend on another function’s body: changing a body never breaks its callers, and a call through a contract or a lambda follows the same rules.
Results: given up or lent
Section titled “Results: given up or lent”A result is either given up to the caller, : T, which then owns it, or
lent, : yield T, a part of the receiver that the caller reads in place:
import weaver.io.print
type Page = { title: String, words: String[] }
impl Page { /// Lent: the caller reads the title in place, without a copy. fn title(self): yield String = self.title
/// Given up: a new string, which the caller owns. fn heading(self): String = "# ${self.title}"}
fn main() { val p = Page{title: "Memory", words: []} print(p.title()) print(p.heading())}Memory# MemoryReturning a part of something only borrowed, fn title(self): String = self.title, would give up a block that self still owns; the compiler
asks for .copy(), or for the result to be declared lent. A lent result
is tied to its source like any borrow: it is read, passed on, or copied,
not kept once the source changes.
Views work the same way. data[a..b] is a slice of data’s block, without
a copy; modifying data while the view still serves is refused:
the binding reads a place modified while it serves: write `.copy()` (memory-model.md)Frozen parts: sharing that the compiler finds
Section titled “Frozen parts: sharing that the compiler finds”A compiler, a tree transformer or a JSON mapper builds values out of parts of others: a name taken from one node into another. Copying the string at each store would be a waste, when nobody ever modifies it.
So the compiler looks at what the code does with each field. A field that no code modifies in place is frozen, and a frozen part is shared by count rather than copied: storing it elsewhere costs one increment. No annotation is written; the compiler sees it in the package that declares the type.
A count is the price of sharing, paid where a part is actually shared. A buffer that one value owns, a decoder’s output or a parser’s stack, is written in place, and never copied behind the code’s back: a block that is written is never shared. That is where Weaver differs from Swift, where any array may be shared, and any write may copy it.
Identity: values declared shared
Section titled “Identity: values declared shared”Sometimes several holders must see one value: a node that others point
to, a cache, a model that views observe. Weaver says so on the place:
shared mut T is one value, which every holder designates and modifies. It
is counted, and freed at its last release.
A back edge, a child pointing to its parent, would make a cycle of counts
that never reaches zero. It is weak: it designates the value without
keeping it, and reading it says whether the value still exists.
import weaver.io.print
/// A folder: its children kept, its parent only designated.type Folder = { name: String, children: (shared mut Folder)[], weak parent: Folder? }
fn add(parent: shared mut Folder, name: shared String): shared mut Folder { val child: shared mut Folder = Folder{name, children: [], parent: weak parent} parent.children.push(child) return child}
fn path(f: shared mut Folder): String = if f.parent is Some(p) { "${path(p)}/${f.name}" } else { f.name.copy() }
fn main() { val root: shared mut Folder = Folder{name: "home", children: [], parent: None} val docs = add(root, "docs") val draft = add(docs, "draft") print(path(draft))
val same = docs same.name = "papers" // one value: every holder sees it print("${path(draft)}, same folder: ${same === docs}") print("${root.children[0].children.len()} folder in ${root.children[0].name}")}home/docs/drafthome/papers/draft, same folder: true1 folder in papers=== asks whether two holders designate the same value; == compares
values. A shared mut value stays on its task: values that tasks share go
through the objects of concurrency,
Shared, Mutex, an actor.
Graphs without counts: arenas
Section titled “Graphs without counts: arenas”A graph that one owner holds, a syntax tree, a scene, a document, does not
need a count per node. An arena type owns a region where its nodes
live; they designate each other by ref Node, an index into the region.
The nodes are freed all at once, with the object.
ref is an index into the object's region, checked when it is used.import weaver.io.print
type Node = { name: String, children: ref Node[], parent: ref Node? }
arena type Tree = { root: ref Node? }
fn main() { var t = Tree{root: None} val r = t.add(Node{name: "root", children: [], parent: None}) val c = t.add(Node{name: "child", children: [], parent: r}) t[r].children.push(c) t.root = r val up = t[c].parent ?? r print("${t[r].name} has ${t[r].children.len()} child") print("${t[c].name}'s parent is ${t[up].name}")}root has 1 childchild's parent is rootBetween tasks
Section titled “Between tasks”A value passed to another task is given up or copied, never shared mutably: as a task’s argument, a lambda’s capture, a channel’s message. Counts stay ordinary on one thread; only a block that crosses to another task is marked shared, and its count becomes atomic. Most blocks never leave their thread, and pay nothing for the others.
Seeing the costs
Section titled “Seeing the costs”Nothing above is hidden from the reader of the code:
- In the editor,
wv lspwrites at the end of a line what it costs:heapwhen it may allocate,copywhen it copies a block,rc nfor its counts. - In the code,
@assert(noalloc)and@assert(nocopy)turn a cost into a compile error, checked through every function the code calls:
@assert(noalloc)fn total(xs: Int[]): Int { var s = 0 for x in xs { s += x } return s}
@assert(noalloc)fn label(n: Int): String = "n = ${n}"main.wft:9:1: `label` is declared `@assert(noalloc)`, but allocates: `strAppend` → `reserve` → `newBlock` → `wv_sys_alloc`total reads its array where it lies, and allocates nothing; label
builds a string, and the error shows the path down to the allocation.
In short
Section titled “In short”| Situation | What happens | Cost |
|---|---|---|
| scalars, records of scalars | copied in place | a few bytes |
| a block, one owner | freed at the end of the owner’s scope | none beyond the allocation |
val b = a, a not used again |
moved | none |
val b = a, a still used |
borrowed, read only | none |
.copy() |
a second block | written in the text |
a parameter, mut or not |
borrowed | none |
sink |
given up: the callee frees it | none |
| a frozen part stored twice | shared by count | an increment |
shared mut, weak |
one value, counted; weak back edges | a count per holder |
arena type |
a region freed at once | an index check |
| a block that crosses tasks | marked shared | atomic counts |
The memory model of the reference has the exact rules, and the design document, the revised model, the reasons behind each of them.