Collections in a Region, and the Trivial Hierarchy

Part II has built a memory model out of principles: five strategies narrowed to one region, a Trivial line marking what a region may hold, with for the values it can’t, view types for self-references. All of it is worth nothing if you can’t put a Vec in it. A memory model that only handles fixed-shape data is a paper exercise; real programs grow lists, build strings, and index maps. This last episode of Part II is about making the everyday containers live in a region — and it turns out to force one more real decision.

A growable thing in a grow-once area

Here is the tension in one image. A Vec grows: when it fills up, it allocates a bigger buffer, copies the elements over, and abandons the old one. A region does the opposite — it only ever bumps a pointer forward and never frees an individual allocation; the whole area goes at once when the block ends. How does a container built on reallocation sit inside an area built on never freeing?

The answer is that the two fit together better than they first appear. A region-resident Vec reallocates the way any Vec does — bump a new, bigger buffer, copy the elements, point at the new one — and then simply doesn’t free the old buffer. In a normal allocator that would be a leak. In a region it isn’t: the old buffer is dead space until the block ends, and then it is reclaimed along with everything else, for free, by the one pointer reset. Growth in a region is just “abandon the small buffer, keep bumping.” The region’s refusal to free individually, which looked like a limitation, is exactly what makes a growable container cheap to support.

And the growth is not invisible. A push that might reallocate carries the same region-allocation effect the rest of the model uses — the fact that calling it can consume more of the region is written in its type, not discovered at runtime. The memory cost of growing a list is a thing you can see.

The Trivial hierarchy: what nests in what

The last episode’s Trivial constraint returns here as the rule that decides which containers can go in a region — and, crucially, which can nest inside which. Trivial[R] is defined recursively:

• primitives (int, bool, char, …) are Trivial in any region;
• a region reference &R T is Trivial[R] when T is;
• a Vec[R, T] is Trivial[R] when its element type T is.

Follow that chain and Vec[R, Vec[R, int]] is itself Trivial[R] — a vector of vectors, entirely inside one region, still reclaimed by a single bulk free. The recursion is the whole point: “which collection can nest inside which” is not a separate rulebook, it is just Trivial applied to the element type. A container is region-safe exactly when everything it transitively holds is region-safe, and the type system checks that for free.

The line also says clearly what can’t go in. An owned String — heap-backed, with a Drop — is not Trivial, so it cannot live in a region. That is not a gap; it is the Trivial/Drop split from the previous episode doing its job. For strings the model offers two region-native forms instead: an immutable &R str, a slice living in the region whose substrings and splits are free to share because they all point into the same area; and a mutable StrBuf[R], a thin wrapper over Vec[R, u8] for building text up. Owned, heap-allocated strings still exist — they just aren’t what you reach for inside a region.

One decision: two types, not one clever type

There was a genuine fork in how to offer these containers at all, and it is the most interesting choice in the episode because the obvious answer is not the one Mere took.

The unifying option — the one Rust reaches for — is a single Vec type parameterized by its allocator: Vec[A, T], where A is a global heap allocator in one instantiation and a region allocator in another. One implementation, one API, region-ness selected by a type parameter. It is elegant, and it is what you would write if minimizing code were the goal.

Mere took the other path: two separate types. A region Vec[R, T] that is Trivial and bump-allocated, and an OwnedVec[T] that is heap-backed and has a Drop, with the read-only parts of their API unified behind a Collection trait so callers mostly don’t have to care which they hold.

The reason is the same instinct that has shaped the whole of Part II. An allocator parameter makes the two kinds of vector look the same by threading a runtime choice — which allocator — through the type. But region-ness is not supposed to be a runtime choice; the entire value of a region is that its allocation is only a pointer bump, with no dispatch and no per-value cleanup. Fold owned and region into one type via an allocator, and you have quietly put a Trivial type and a Drop type behind the same name, and blurred the line the last two episodes spent their length drawing. Two types keeps that line sharp: Vec[R, T] is always Trivial, OwnedVec[T] always has cleanup, and they never pretend to be interchangeable. Moving a value between them is an explicit copy, not an implicit allocator swap — the same refusal of hidden conversions the language makes everywhere.

It costs something, and the design notes say so plainly: the standard library now writes push twice. But that is a cost paid once, by the library’s author, and hidden from everyone else behind the shared trait — which is exactly the right place to spend duplication if the alternative is a fuzzier type system for every user. This is the recurring shape of Mere’s choices: prefer more concepts kept distinct over fewer concepts quietly merged, and pay for the distinction in author effort rather than in reader doubt.

Part II, closed

That completes the memory model. It began as a list of five strategies and ended as something smaller and sharper: one region that bump-allocates and bulk-frees; a Trivial line dividing what a region can hold from what with must clean up in LIFO order; view types letting a value safely reference into its own region; and now collections that grow inside a region by abandoning rather than freeing, with a recursive Trivial hierarchy deciding what may nest where. Every piece is explicit in the types, checkable without an escape hatch, and readable off the page — which was the whole point the first episode set out.

Memory answers where values live and when they die. The next part answers a different question the language is just as insistent about making explicit: what is a piece of code allowed to do — touch the network, read the clock, write a file? That is the effect system, and it begins by refusing to let side effects travel for free. Next: passing side effects as values.