Dada Formal Model
This book documents the formal model for the Dada programming language. The model is implemented in Rust using formality-core and defines Dada’s type system, including its permission-based ownership model.
The code examples in this book are extracted from executable tests.
cargo test --all --workspace checks their expected outcomes, including programs
that should be rejected. Interpreter-only tests deliberately bypass type checking.
The book build extracts examples and formal rules; it does not run the tests.
Throughout the book, we will also reference the formal rules from the model’s source code using anchors like ClassDecl.
Surface syntax and core judgments
Programs enter through surface::parse_program: the surface parser constructs an
AST, desugaring judgments lower it to core, and the core checker and interpreter
operate on that result. Every program assertion helper follows this path,
including interpreter-only tests that deliberately skip checking.
The two grammars share concrete permissions and places. Surface declarations, expressions, types, and binders have their own ASTs. Lowering walks those terms structurally; it does not print text and parse it again.
Both grammars use the Unicode arrow → for return types, as in
fn identity(given self, value: given Int) → Int { value→; }, and for giving a
place’s value. The same arrow appears in surface receiver declarations and
dotless calls. The ASCII spelling -> is not accepted.
Permission spelling
| Surface spelling | Meaning |
|---|---|
given Data, given[] Data, [] Data | Independent unique ownership of named Data |
given[x, y] T, [x, y] T | Permission derived from the listed places |
shared T, shared[] T | Independent shared ownership |
shared[x, y] T | Sharing from the listed places |
![x, y] T | Mutable access from the listed places |
The surface type shorthand [places] T lowers to given[places] T.
With nonempty origins, this permission derives its capabilities from the origin
types; it does not necessarily imply uniqueness or ownership. The annotation
describes a type and does not move a value. Empty origins instead give the
independent permission: [] T lowers to given T.
Empty mutable origins are invalid. Bare !T in a function parameter instead
introduces a fresh permission variable constrained by is mut.
Classes, structs, and predicates
class declares uniquely tracked data that may have a destructor. struct
declares shareable data, and shared struct declares value data that is copyable
when its generic arguments are shared (including the case with no arguments).
Structs cannot have nonempty destructor bodies.
The predicates unique and shared describe exclusivity and duplication;
owned describes independence from borrowed origins. Unique ownership is the
conjunction P is unique, P is owned. The shareability predicate is T is struct.
given names a permission, not a declaration category or predicate: use class
for affine declarations and the two constraints above for unique ownership.
mut and boxed retain their separate meanings.
Parameter defaults
Only the outermost permission of an input is implicit. When Data names a
class or struct, x: Data means x: any Data; each occurrence introduces its
own fresh permission variable. A bare type variable is different: x: T
means x: given T and introduces no permission binder. Here given is the
identity permission: it preserves the full type supplied for T, including
that type’s permission. This applies to method type parameters, including those
declared inline, and enclosing class type parameters. Write x: any T to
introduce a separate permission variable, or x: !T to introduce one constrained
by is mut.
Explicit permissions such as given Data,
P Data, [source] Data, and [] Data keep their stated meaning and introduce
no permission binder. In particular, x: [] Data explicitly requires ownership.
For a parameter x: Array[Data], only the permission on Array is introduced.
The element type remains owned. Field types, return types, local annotations,
and nested type arguments retain the identity default given. To require
ownership of a named input type explicitly, write x: given Data.
Inline type declarations
An input value: type T declares a method type parameter T and uses it as the
input type. It introduces one type argument at calls, with no separate
permission argument. This surface declaration:
struct Worker {
fn self.consume(input: type T) {}
}
lowers to this core declaration:
struct Worker {
fn consume[perm P, type T](P self, input: T) {}
}
The receiver’s generated permission comes first, followed by the inline type
parameter. These snippets are checked together by an assert_desugars! test.
The new type parameter is in scope throughout the method signature and body,
including earlier inputs, the return type, and where clauses. It may shadow
a type parameter of the enclosing class. An inline declaration cannot reuse
another method generic’s name: two inline declarations of T, or an inline
T alongside an explicit method generic named T, are rejected.
Inline type declarations are supported only as direct inputs. Forms such as
any type T, !type T, and Array[type T] do not introduce binders, nor do return
types, fields, or local annotations. Once declared, T can appear
inside other types or use ordinary input sugar such as any T and !T.
Core keeps all type parameters in the explicit generic list.
Receiver declarations
Surface declarations can put the receiver before the method name:
| Declaration form | Receiver permission |
|---|---|
fn self.foo(...) | A fresh permission variable |
fn self!foo(...) | A fresh permission variable constrained by is mut |
fn self→foo(...) | Explicit given, with no new permission binder |
The receiver is omitted from the parentheses in these forms. Explicit generics
follow the method name, as in fn self!foo[type T](value: T).
Both grammars also accept an explicit permission and self as the first
parameter: fn foo(given self, ...) or fn foo[perm P](P self, ...).
Other explicit permissions, such as shared self, given[x] self, and
![x] self, use the same form. Core requires this explicit receiver form.
The former parameter-list receivers self, any self, self!, and self→
are rejected.
The declaration fn self.foo(...) is permission-generic. A call through
value.foo[...](...) shares the receiver place; the declaration prefix does
not fix the receiver permission to sharing.
For example, this surface declaration:
struct Worker {
fn self!edit[type T](value: !T) { (); }
}
has the following explicit core signature (fresh names are illustrative):
struct Worker {
fn edit[type T, perm Receiver, perm Input](Receiver self, value: Input T)
where Receiver is mut, Input is mut { (); }
}
These snippets are the two sides of an assert_desugars! test. It lowers the
surface program and compares its AST with the independently parsed core program,
ignoring bound-variable names. This checks the expansion itself; type checking
and interpretation have separate tests.
Calls supply all generic arguments
There is no generic argument inference. All explicitly declared generics come
first. The generated suffix starts with the receiver permission, if any, then
visits inputs from left to right, interleaving inline type parameters and generated
permission parameters. A bare type-variable input adds no permission slot, and
an explicit permission adds none either. Thus
fn self!mix[type A](left: type T, data: Data, right: type U) takes generic arguments
for A, the receiver permission, T, the permission on data, and U, in that
order. Calls must supply every argument, including the generated suffix:
let worker = new Worker();
let value = new Data();
worker!edit[Data, ![worker], ![value]](value!);
The checker resolves the actual method before checking argument count and kinds.
An incorrect list reports the expanded signature and associates generic slots
with the receiver or inputs that use them. The entry method has no caller-supplied
generic arguments, so its receiver is explicitly owned: fn main(given self),
or the equivalent surface form fn self→main().
Place origins written in call arguments belong to the caller, even when the
callee uses the same names for its receiver, inputs, or locals.
Surface method calls may omit the dot after a place’s ! or → access.
For example, vec!push[![vec]](value) lowers to
vec!.push[![vec]](value), and vec→iter[given]() lowers to
vec→.iter[given](). Both spellings are accepted in surface; core keeps the
dotted form. This changes only call spelling: all generic arguments are still
explicit. The receiver must be a place, including a projected place such as
vec.field[0]; calls on other expressions continue to use a dot.
Tuple expressions
Both grammars separate tuple elements with commas, as in (x, y), and allow a
trailing comma. () is unit. Both (x) and (x,) are singleton tuples;
parentheses do not introduce a grouping expression.
In surface, (vec!, iter, ()) has three separate elements, while
(vec!iter(),) has one element: a method call using vec! as its receiver.
Places and values
A bare place or place.share shares from that place. place→ gives its value;
place! creates a mutable lease. place→.share first gives, then shares the value
independently. The outer independent permission does not erase dependencies in
nested field or element types. drop place; is a statement; it cannot be used
where an expression is required.
Value sharing keeps its dot: write place→.share. share is an operation,
not a callable method, so place→share() and place→.share() are invalid.
Core is the explicit language used by the judgments. Its source renderer emits
explicit receiver permissions, named generic binders, and dotted calls.
Named input types have explicit permissions; bare type variables remain bare
because they add no permission binder. Rendered programs can therefore enter
through surface parsing again while preserving the core AST. Core remains a subset
of surface. Diagnostic Debug output is separate and is not a source
serialization format.
Signature sugar keeps calls explicit
Receiver and input permission sugar introduce fresh permission parameters. Calls
supply those permissions after explicit generics, receiver first and inputs
left to right. Inline type T declarations add type parameters at their input’s
position in that same generated suffix, without a permission parameter for T.
These complete programs exercise lowering, checking, and
interpretation together, including dotless !/→ calls; no inference fills
omitted arguments.
Receiver permissions have valid origins
Receiver permissions obey the same origin well-formedness rules as input permissions. They may name later inputs, but cannot name missing variables. Checking a receiver permission does not add a variance requirement to its enclosing class type. A boundary test also rejects noncanonical empty origins constructed by mutating a valid surface-lowered program.
Generic call arguments preserve caller origin identities
Places supplied inside type or permission arguments belong to the caller.
Receiver, input, and local names in the callee must not capture those places,
including when a class generic is instantiated before a method generic.
These surface programs cover input-name collisions, caller self, projected
class-generic origins, crossed input names, and names resembling internal
temporaries. Returned permissions retain their dependency on caller storage.
Classes and structs
Dada programs declare classes and structs. Each declaration has a name, fields,
and methods. Here is a simple struct Point with two Int fields:
crate::assert_ok!(
r#"
struct Point {
x: Int;
y: Int;
}
struct Main {
fn test(given self) → Int {
let p = new Point(22, 44);
p.x→;
}
}
"#
);
The entry type Main is special only by convention – the model checks every method.
Each method has a receiver (self) with a permission (here, given, written given self)
and a body that is type-checked against the declared return type.
New instances are created with new Point(22, 44),
providing values for each field in declaration order.
Fields are accessed with dot notation (p.x).
Declaration categories
Three declaration forms select a class predicate in the model:
| Declaration | Predicate | Meaning |
|---|---|---|
class Foo { } | Class | Affine data; may have a destructor; cannot be shared as a value |
struct Foo { } | Struct | Shareable data with mutable fields; no destructor |
shared struct Foo { } | Shared | Copyable when its generic arguments are shared; no destructor |
Int is a built-in shared struct type, so its values can be freely copied.
A plain class keeps ownership uniquely tracked and allows a destructor.
Declaring a struct opts into sharing and rules out a destructor; declaring a
shared struct also makes values copyable without an explicit sharing operation
when all of its generic arguments are shared (automatically true with no arguments).
The checker rejects nonempty drop bodies on either struct form.
We will return to class predicates as we explore the permission system.
Grammar
The core grammar uses ClassDecl for all three declaration categories:
#[term($class_predicate $name $binder)]
pub struct ClassDecl {
pub name: ValueId,
pub class_predicate: ClassPredicate,
pub binder: Binder<ClassDeclBoundData>,
}
#[term($:where $,predicates { $*fields $*methods $?drop_body })]
pub struct ClassDeclBoundData {
pub predicates: Vec<Predicate>,
pub fields: Vec<FieldDecl>,
pub methods: Vec<MethodDecl>,
pub drop_body: DropBody,
}
/// Optional drop body for a class. When present, the statements are executed
/// when an owned handle to the class is dropped. Default is an empty block
/// (no drop body), which is semantically equivalent to `drop { }`.
#[term(drop $block)]
#[derive(Default)]
pub struct DropBody {
pub block: Block,
}
The #[term(...)] attributes define the parsing grammar using formality-core conventions:
$? is an optional element, $* means zero-or-more, $, means comma-separated,
and $:where means the keyword where appears only if the list is non-empty.
Binder introduces generic parameters that are in scope for the bound data.
Each field has a name and a type,
and can optionally be declared atomic
(which affects variance – more on this later):
#[term($?atomic $name : $ty ;)]
pub struct FieldDecl {
pub atomic: Atomic,
pub name: FieldId,
pub ty: Ty,
}
#[term]
#[derive(Default)]
pub enum Atomic {
#[default]
#[grammar(nonatomic)]
No,
#[grammar(atomic)]
Yes,
}
Only classes have destructors
A class may define a nonempty drop body. A struct or shared struct may not:
independent sharing requires data without a destructor. Empty drop {} is
represented identically to an absent body and is accepted for every category.
These paired programs use the same body and differ only in declaration kind.
A simple function
We’re going to walk through how the type checker handles a very simple program, step by step. Here is the complete program:
crate::assert_ok!(
r#"
struct Point {
x: Int;
y: Int;
}
struct Main {
fn test(given self) → Int {
let p = new Point(22, 44);
0;
}
}
"#
);
Nothing very exciting happens here –
we create a Point and then return 0.
But working through this example introduces
the basic machinery that everything else builds on:
the environment, places, types,
and – most importantly – how the type checker
is structured as a set of judgment functions
with inference rules.
Grammar declarations
The formal model represents programs using Rust structs
annotated with #[term], a macro from formality-core.
Each #[term] struct defines both the abstract syntax
and a textual grammar (the $-prefixed patterns).
A declaration contains a name, a category (class, struct, or shared struct), and a binder wrapping the fields and methods:
#[term($class_predicate $name $binder)]
pub struct ClassDecl {
pub name: ValueId,
pub class_predicate: ClassPredicate,
pub binder: Binder<ClassDeclBoundData>,
}
#[term($:where $,predicates { $*fields $*methods $?drop_body })]
pub struct ClassDeclBoundData {
pub predicates: Vec<Predicate>,
pub fields: Vec<FieldDecl>,
pub methods: Vec<MethodDecl>,
pub drop_body: DropBody,
}
/// Optional drop body for a class. When present, the statements are executed
/// when an owned handle to the class is dropped. Default is an empty block
/// (no drop body), which is semantically equivalent to `drop { }`.
#[term(drop $block)]
#[derive(Default)]
pub struct DropBody {
pub block: Block,
}
A field declaration is a name and a type:
#[term($?atomic $name : $ty ;)]
pub struct FieldDecl {
pub atomic: Atomic,
pub name: FieldId,
pub ty: Ty,
}
A method declaration contains a name and a binder
wrapping the receiver (this), parameters, return type, predicates, and body:
#[term(fn $name $binder)]
pub struct MethodDecl {
pub name: MethodId,
pub binder: Binder<MethodDeclBoundData>,
}
#[term]
#[customize(parse, debug)]
pub struct MethodDeclBoundData {
pub this: ThisDecl,
pub inputs: Vec<LocalVariableDecl>,
pub output: Ty,
pub predicates: Vec<Predicate>,
pub body: MethodBody,
}
The environment
The type checker’s job is to walk through each statement in a method body
and track what it knows about each variable.
This information is stored in the environment (Env),
which maps variables to their types:
#[derive(Clone, Ord, Eq, PartialEq, PartialOrd, Hash)]
pub struct Env {
program: Arc<Program>,
universe: Universe,
in_scope_vars: Vec<Variable>,
local_variables: Map<Var, Ty>,
assumptions: Set<Predicate>,
fresh: usize,
}
The key field for now is local_variables,
which maps each variable to its type.
(We’ll explain the other fields as they become relevant.)
Judgments and inference rules
The type system is defined as a collection of judgment functions.
Each judgment function is defined with the judgment_fn! macro
and contains one or more inference rules.
An inference rule has premises above a horizontal line
and a conclusion below it.
The conclusion holds when all the premises are satisfied.
For example, an inference rule with the conclusion
check_program(program) => () means
“the program type-checks successfully.”
The premises above the line specify what must be true
for that conclusion to hold.
How type checking begins
Type checking begins with the check_program judgment,
which checks that every declaration in the program is well-formed:
(for_all(decl in program.decls.clone())
(check_decl(program, decl) => ()))
----------------------- ("check_program")
(check_program(program) => ())
The sole premise uses for_all to require that
check_decl succeeds for each declaration.
In our example, the program has two declarations (Point and Main),
so the premise is satisfied when both declarations check successfully.
For each declaration, check_class checks the fields and then each method.
Let’s look at the rule for check_method:
(let MethodDecl { name: _, binder } = decl)
(let (env, vars, MethodDeclBoundData { this, inputs, output, predicates, body }) =
env.open_universally(binder))
(let env = env.add_assumptions(
vars.iter()
.flat_map(|v| vec![VarianceKind::Relative.apply(v), VarianceKind::Atomic.apply(v)])
.collect::<Vec<_>>(),
))
(check_predicates(env, predicates) => ())
(let env = env.add_assumptions(predicates))
(let ThisDecl { perm: this_perm } = &this)
(let this_ty = Ty::apply_perm(this_perm, class_ty))
(let env = env.push_local_variable(This, this_ty)?)
(let env = env.push_local_variable_decls(inputs)?)
(check_perm(env, this_perm) => ())
(for_all(input in inputs)
(let LocalVariableDecl { name: _, ty } = input)
(check_type(env, ty) => ()))
(check_type(env, output) => ())
(check_body(env, output, body) => ())
----------------------------------- ("check_method")
(check_method(class_ty, env, decl) => ())
For our example, the method declaration for test specifies given self,
so the premises compute the type given Main
and push it into the environment as self.
If there were other parameters, they’d be pushed too.
Once the environment is ready,
the final premise invokes the check_body judgment:
(let live_after = LivePlaces::default())
(can_type_expr_as(env, live_after, block, output) => ())
----------------------------------- ("block")
(check_body(env, output, MethodBody::Block(block)) => ())
The “block” rule applies to our example
(the “trusted” rule handles built-in methods with no body).
Its premises initialize live_after to the empty set –
nothing is live after the method body returns –
and then require that can_type_expr_as succeeds,
checking that the body can be typed as the declared return type (Int).
Typing a block
The body of a method is a block expression,
so type_expr dispatches to type_block:
(type_statements(env, live_after, statements) => (env, ty))
----------------------------------- ("place")
(type_block(env, live_after, Block { statements }) => (env, ty))
A block is a sequence of statements,
so this delegates to type_statements,
which walks through statements one at a time:
(let live = live_after.before(statements))
(type_statement(env, live, statement) => (env, ty))
(type_statements_with_final_ty(env, live_after, statements, ty) => (env, ty))
----------------------------------- ("cons")
(type_statements_with_final_ty(env, live_after, Cons(statement, statements), _ty) => (env, ty))
The type of the last statement becomes the type of the block.
Notice the first premise: live_after.before(&statements).
Every judgment in the type system carries a live_after parameter –
the set of variables that are live (i.e., used later in the program).
In this chapter, nothing interesting happens with liveness
because we never use our variables again.
We’ll explain liveness in detail in the Giving chapter,
where it determines whether a value is moved or copied.
Typing let p = new Point(22, 44)
The let statement is handled by this rule:
(type_expr(env, live_after.clone().overwritten(id), &**expr) => (env, ty)) // [1]
(let env = env.push_local_variable(id, ty)?)
(let env = env.with_in_flight_stored_to(id))
----------------------------------- ("let")
(type_statement(env, live_after, Statement::Let(id, Ascription::NoTy, expr)) => (env, Ty::unit()))
The rule has three premises:
-
type_expr(env, live_after.overwritten(&id), ...) => (env, ty)– Type the right-hand side expression (new Point(22, 44)) and produce its typety. Thelive_after.overwritten(&id)removespfrom the live set, sincepdoesn’t exist yet while the RHS is being evaluated. -
env.push_local_variable(&id, ty)– Addpto the environment with the type produced by the first premise. -
env.with_in_flight_stored_to(&id)– Record that the result of the expression is now stored inp. (We’ll explain “in-flight” values in a later chapter – for now, just think of it as “the result of the expression flows into the variable”.)
Typing new Point(22, 44)
The new expression is typed by the following rule:
(let class_decl = env.program().class_named(class_name)?)
(let ClassDeclBoundData { predicates, fields, methods: _, drop_body: _ } = class_decl.binder.instantiate_with(parameters)?)
(if fields.len() == exprs.len())
(let this_ty = NamedTy::new(class_name, parameters))
(prove_predicates(env, predicates) => ())
(let (env, temp_var) = env.push_fresh_variable(this_ty))
(type_field_exprs_as(env, live_after, temp_var, exprs, fields) => env)
(let env = env.with_place_in_flight(temp_var))
(let env = env.pop_fresh_variable(temp_var))
----------------------------------- ("new")
(type_expr(env, live_after, Expr::New(class_name, parameters, exprs)) => (env, this_ty))
The premises require:
- Looking up the struct
Pointto find its fields:x: Int,y: Int. - Checking that the argument count matches the field count (2 = 2).
- Creating a temporary variable to represent the object under construction.
- Invoking
type_field_exprs_asto type each argument against the corresponding field type –22againstInt,44againstInt. Both succeed via the integer typing rule:
----------------------------------- ("constant")
(type_expr(env, _live_after, Expr::Integer(_)) => (env, Ty::int()))
The “constant” rule has no premises –
the conclusion type_expr(env, _, Expr::Integer(_)) => (env, Ty::int())
holds unconditionally.
Any integer literal has type Int.
The conclusion of the “new” rule gives us the type Point.
After the let
After typing let p = new Point(22, 44), the environment becomes:
| Variable | Type |
|---|---|
self | given Main |
p | Point |
Typing the return expression 0
The final statement in the block is 0 – an expression statement.
It is typed by this rule:
(type_expr(env, live_after, expr) => (env, ty))
(let (env, temp) = env.push_fresh_variable_with_in_flight(ty))
(env_permits_access(env, live_after, Access::Drop, temp) => env)
(parameter_permits_access(env, ty, Access::Drop, temp) => env)
(let env = env.pop_fresh_variable(temp))
----------------------------------- ("expr")
(type_statement(env, live_after, Statement::Expr(expr)) => (env, ty))
The first premise types the expression 0,
yielding type Int (by the “constant” rule shown above).
The remaining premises check that both the environment and the type
permit dropping the temporary value.
For Int, dropping is trivially permitted.
The type of the last statement (Int) becomes the type of the block.
Back in check_body, the can_type_expr_as premise
checks this against the declared return type Int –
subtyping succeeds, and the method type-checks successfully.
What about p?
You may have noticed that we never use p.
We create a Point, bind it to p, and then ignore it.
The type checker is fine with this –
p is never referenced after the let,
so it’s not in the live set and the type checker simply ignores it.
In the next chapter, we’ll see what happens when variables are live – and how liveness determines whether a value is moved or copied.
Giving
In the previous chapter, we walked through a program that created a value and ignored it. Now we’ll see what happens when you actually use a value – and how the type checker decides whether that’s allowed.
Place expressions
In Dada, values are accessed through place expressions like d→.
A place expression combines a place (a variable, possibly with field projections)
and an access mode (what you want to do with the value):
#[term($place $access)]
#[customize(parse, debug)]
pub struct PlaceExpr {
pub place: Place,
pub access: Access,
}
A place is a variable with zero or more field projections:
#[term($var $*projections)]
pub struct Place {
pub var: Var,
pub projections: Vec<Projection>,
}
A projection is a field access:
#[term]
#[customize(parse)]
pub enum Projection {
#[grammar(. $v0 $!)]
#[cast]
Field(FieldId),
#[grammar([ $v0 ] $!)]
Index(usize),
}
The access mode determines what kind of access is being performed:
#[term]
#[derive(Copy, Default)]
#[customize(parse, debug)]
pub enum Access {
#[default]
#[grammar(.share)]
SharePlace,
Gv,
#[grammar(!)]
Mt,
#[grammar(.drop)]
Drop,
}
| Access | Meaning |
|---|---|
place→ | Move the value, or duplicate it when shared |
place or place.share | Share the place; the result depends on that place |
place! | Mutably borrow the place |
drop place; | Drop the value (statement) |
Sharing a value expression, such as new Data().share or place→.share,
instead gives the resulting value an independent shared permission.
The Sharing values chapter explains that operation;
Sharing places explains the place-dependent form.
We’ll start with giving, spelled →.
Giving a value
If you are familiar with Rust,
giving is analogous to a move.
When you give a value, you transfer ownership of it.
The following program creates a Data value and gives it away as the return value:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self) → Data {
let d = new Data();
d→;
}
}
"#
);
The give place rule
A place expression like d→ is typed by this rule:
(access_permitted(env, live_after, Access::Gv, place) => env)
(let ty = env.place_ty(place)?)
(move_place(env, live_after, place, ty) => env)
----------------------------------- ("give place")
(type_expr(env, live_after, PlaceExpr { access: Access::Gv, place }) => (env, ty))
The rule has three premises:
-
access_permitted(env, ..., Access::Gv, &place) => env– Check that giving this place is permitted. This verifies that no other live variable holds a conflicting access constraint on the place. (In this simple example, nothing does.) The judgment returns an updated environment. -
env.place_ty(&place)– Look up the type ofdin the environment:Data. -
move_place(&env, &live_after, &place, &ty) => env– Decide whether to move or copy the value, returning an updated environment that reflects the result. This is where liveness matters.
Liveness
In the previous chapter, we mentioned that every judgment
carries a live_after parameter – the set of places
that are used later in the program.
Nothing interesting happened with liveness there
because we never used our variables again.
Now it becomes central.
How liveness is computed
Recall the type_statements_with_final_ty rule
that walks through a block’s statements.
Its first premise is live_after.before(&statements),
which computes what’s live before the current statement
by scanning forward through the remaining statements:
flowchart LR
subgraph block ["{ s_0 ; s_1 ; s_2 }"]
s0["s_0"] --> s1["s_1"] --> s2["s_2"]
end
block --> after
after["... more code ..."]
after -. "live_after = L<br/>(vars used by ...)" .-> block
s2 -. "L(s_2) = <br> L ∪ vars used by s_2" .-> s1
s1 -. "L(s_1) = <br> L(s_2) ∪ vars used by s_1" .-> s0
live_after captures what the code after the block needs.
But a block isn’t atomic – it has internal structure.
So when processing s_0, the type checker extends live_after
by scanning forward through the remaining statements [s_1, s_2]
and collecting every place they reference.
This tells each judgment which places are still needed
and which are free to be moved.
The move_place judgment
The move_place judgment uses liveness to decide
whether giving a place moves or copies its value:
move_place(env: Env, live_after: LivePlaces, place: Place, ty: Ty,) => Env
Notice the return type: move_place takes an Env and returns an updated Env.
Many judgments in the type system work this way –
they thread the environment through,
and the returned environment reflects any changes
(like marking a place as moved).
The judgment has two rules. Which one applies depends on whether the place is live.
The “give” rule applies when the place is not live afterward –
no later code needs this place, so the value can be moved.
Its premise env.with_place_in_flight(&place) produces
a new environment where the place is marked as moved:
(if !live_after.is_live(place))
(let env = env.with_place_in_flight(place))
----------------------------------- ("give")
(move_place(env, live_after, place, _ty) => env)
The “copy” rule applies when the place is still live –
later code will use it, so the value must stay.
Its premise requires prove_is_shared,
which succeeds for types like Int or shared struct types.
If the type isn’t copyable, this premise fails and the type check fails:
(if live_after.is_live(place))!
(prove_is_shared(env, ty) => ())
----------------------------------- ("copy")
(move_place(env, _live_after, _place, ty) => env)
Applying it to d→
In our example:
let d = new Data();
d→;
When the type checker reaches d→,
live_after is {} – nothing comes after the method returns.
So d is not live, the “give” rule applies,
and the returned environment has d marked as in-flight (moved).
Giving a value twice is an error
Once a value has been given away, it is gone. Trying to use it again is an error:
crate::assert_err!(
r#"
struct Data { }
struct Main {
fn test(given self) → Data {
let d = new Data();
d→;
d→;
}
}
"#,
expect_test::expect![[r#"
the rule "give" at (expressions.rs) failed because
condition evaluted to false: `!live_after.is_live(place)`
live_after = LivePlaces { accessed: {d}, traversed: {} }
place = d"#]]
);
This time, when we process the first d→,
the remaining statement is the second d→, which references d.
So d is live, and the “copy” rule fires instead.
But Data is an ordinary struct, so it doesn’t satisfy prove_is_shared –
the type check fails.
This is the same principle as Rust’s move semantics – after a move, the original binding is no longer valid.
Giving a field
You can give individual fields from an object. After giving a field, that specific field is no longer available, but other fields remain accessible:
crate::assert_ok!(
r#"
struct Data { }
struct Pair {
a: Data;
b: Data;
}
struct Main {
fn test(given self) → Data {
let p = new Pair(new Data(), new Data());
p.a→;
p.b→;
}
}
"#
);
When processing p.a→, the live set includes p.b
(because the next statement references it),
but p.a is not live – nothing after this point uses p.a.
So the “give” rule fires for p.a.
Then when processing p.b→, nothing is live afterward,
so the “give” rule fires again for p.b.
Giving a field and then the whole value is an error
If you give away a field, the whole value is now incomplete, so you can’t give the whole thing:
crate::assert_err!(
r#"
struct Data { }
struct Pair {
a: Data;
b: Data;
}
struct Main {
fn test(given self) → Pair {
let p = new Pair(new Data(), new Data());
p.a→;
p→;
}
}
"#,
expect_test::expect![[r#"
the rule "give" at (expressions.rs) failed because
condition evaluted to false: `!live_after.is_live(place)`
live_after = LivePlaces { accessed: {p}, traversed: {} }
place = p . a"#]]
);
When processing p.a→, the next statement is p→,
which references p. Since p.a overlaps with p,
the liveness check is_live(p.a) returns true –
p.a is live because p (which includes p.a) will be used.
The “copy” rule fires, Data isn’t copyable, and the check fails.
Conversely, if you give the whole value, you can’t access its fields afterward:
crate::assert_err!(
r#"
struct Data { }
struct Pair {
a: Data;
b: Data;
}
struct Main {
fn test(given self) → Data {
let p = new Pair(new Data(), new Data());
p→;
p.a→;
}
}
"#,
expect_test::expect![[r#"
the rule "give" at (expressions.rs) failed because
condition evaluted to false: `!live_after.is_live(place)`
live_after = LivePlaces { accessed: {p . a}, traversed: {} }
place = p"#]]
);
Here, when processing p→, the next statement references p.a.
Since p is a prefix of p.a, is_live(p) returns true.
Same result: the “copy” rule fires, Pair isn’t copyable, failure.
Giving also preserves dependencies on the transferred value:
Moves preserve dependencies
Moving a value to a new place preserves dependencies on that value. Existing shared borrows remain associated with the transferred value and continue to restrict conflicting accesses at its new location. These restrictions follow subsequent transfers too, and cease when the dependent borrows are no longer live.
Candidate lemma: place relocation preserves typing
For a supported ownership transfer from place p to a fresh place q,
consistently substitute q for the prefix p in dependent types and the
relevant typing context. Thus p.field becomes q.field, while unrelated
places are unchanged. The candidate preservation claim is that dependent
values remain well-typed, with corresponding access restrictions at q.
Scope and assumptions
This is a candidate formulation, not a proved theorem. It assumes a permitted move of an initialized value and removal of access to the transferred source. Liveness and dependent places must be interpreted in the updated context. Assignment to an existing destination additionally requires that replacing its previous value is permitted; freshness alone does not cover that case.
The tests below check static dependency tracking for shared borrows, including whole-value and field transfers. They do not establish that runtime mutable reference pointers survive relocation, or cover every partially moved aggregate.
Evidence
The five tests check that a borrow remains usable after transfer, a dead borrow releases restrictions, discarding a needed referent is rejected, a second transfer retargets the dependency, and overwriting its final destination is rejected while the borrow remains live. Error snapshots record the current diagnostics; the property concerns acceptance and rejection for these reasons.
Shared structs are copyable
Shared struct values are always shared and can be given multiple times.
Int is a built-in shared struct, so this works fine:
crate::assert_ok!(
r#"
struct Main {
fn test(given self) → Int {
let x = 22;
x→;
x→;
}
}
"#
);
When processing the first x→, the second x→ references x,
so x is live. The “copy” rule fires – but this time Int is a shared struct type,
so prove_is_shared succeeds, and the value is copied rather than moved.
Giving from alternative origins: every origin must satisfy unique
given[p1, ..., pn] satisfies unique only when every possible originating
place has a type satisfying unique. One unique alternative cannot establish
the predicate for a value whose actual origin could instead be shared.
For an ordinary non-shared Wrapper, with reference origins borrowing from
uniquely owned source1 and source2:
| Origin types | given[d1, d2] is unique? |
|---|---|
Any pair of given Wrapper and ![source] Wrapper | Yes |
Any pair containing shared Wrapper or shared[source] Wrapper | No |
Here unique is the predicate, not the ability to write given: shared values
also support given, which can duplicate them. A given/mut pair satisfies
unique without satisfying either owned or mut uniformly. Failure to prove
shared alone does not prove unique for alternative origins.
Projected origins
The same requirement applies to full place types such as d1.field and
d1.inner.field, including permissions inherited from their containers and
permissions stored on fields. A unique container can still contain a shared
field, which prevents an all-unique classification when it is an origin.
Candidate lemma and evidence
For a well-formed environment and nonempty list of valid places, the mv unique
rule proves given[p1, ..., pn] is unique from the unique predicate on every
place’s type. The mut => unique implication is compatible with this obligation:
establishing a mutable lease still requires the relevant origins to qualify.
This candidate statement has not been proved as a theorem.
Tests call a method requiring P is unique in complete Dada programs. All direct
pairs of given/mut/shared/place sharing origins are covered, with selected contrasting
pairs in both orders for fields, nested fields, and stored-field permissions.
Every negative program first compiles with only that requirement removed.
These tests establish examples of static classification, not a universal
complement relation between unique and shared, or runtime move correctness.
Sharing values
In the previous chapter,
we saw that giving a non-copyable value moves it –
after a give, the original is gone.
We also saw that shared struct types like Int are copyable
and can be given multiple times.
But what about ordinary structs?
What if you want to use a value in multiple places
without giving up ownership?
That’s what sharing is for.
Sharing a value
Sharing a value expression, such as new Data().share or d→.share, converts
unique (given) ownership to independent shared ownership, shared[].
The shorter permission spelling shared means the same thing.
Once shared, a value can be freely copied:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self) → shared Data {
let d = new Data();
let s = d→.share;
s→;
s→;
}
}
"#
);
Compare this with the giving a value twice
example from the previous chapter, which failed.
The difference is .share –
it transforms the Data value so that subsequent gives copy rather than move.
Sharing a place directly is a different operation. d and d.share both yield
shared[d] Data, keeping a dependency on d. To share its value independently,
write d→.share: first give the value, then share it. The Sharing places
chapter explains place dependencies.
The share value rule
The type checker handles sharing a value with this rule:
(type_expr(env, live_after, &**expr) => (env, ty))
(prove_is_struct(env, ty) => ())
----------------------------------- ("share value")
(type_expr(env, live_after, Expr::ShareValue(expr)) => (env, Ty::apply_perm(Perm::Shared, ty)))
The rule has two premises:
-
type_expr(env, ..., &*expr) => (env, ty)– Type-check the inner expression, producing a typety. -
prove_is_struct(&env, &ty) => ()– Verify that the type is allowed to be shared. Not all types can be shared – classes cannot.
If both premises succeed,
the result type is shared ty –
the original type wrapped with the shared[] permission. Dependencies already
present in the inner type still matter; for example, sharing a mutable lease
does not remove the lease’s origin.
Shareability and declaration categories
Whether a type can be shared depends on its class predicate. The three declaration forms select these predicates:
#[term]
#[derive(Copy, Default)]
pub enum ClassPredicate {
/// Uniquely tracked affine data. Only classes may have a destructor.
#[default]
#[grammar(class)]
Class,
/// Data that can be shared independently. It has no destructor.
#[grammar(struct)]
Struct,
/// Always-shared value data. Individual fields cannot be mutated.
#[grammar(shared struct)]
Shared,
}
| Declaration | Predicate | Shareable? |
|---|---|---|
class Foo { } | Class | No |
struct Foo { } | Struct | Yes |
shared struct Foo { } | Shared | Already shared |
The prove_is_struct judgment delegates
to the general predicate-proving machinery:
(prove_predicate(env, Predicate::struct_(a)) => ())
---------------------------- ("is")
(prove_is_struct(env, a) => ())
For a struct like Data, the Struct declaration category permits value
sharing. Neither structs nor shared structs may have a destructor; the checker
rejects a nonempty drop body on either form.
Shared values are copyable
Once a value is shared,
the move_place judgment from the giving chapter
treats it differently.
Recall that move_place has two rules – “give” (move) and “copy”.
The “copy” rule requires prove_is_shared:
(if live_after.is_live(place))!
(prove_is_shared(env, ty) => ())
----------------------------------- ("copy")
(move_place(env, _live_after, _place, ty) => env)
A shared Data type satisfies prove_is_shared
because any shared permission can be duplicated.
So when you write s→ on a shared value,
the “copy” rule fires and the value is copied rather than moved.
This is why the example above works –
both s→ expressions copy the shared value.
Shared structs and generic arguments
In the previous chapter, we saw that Int values
can be given multiple times.
That’s because Int is a shared struct type –
it has the Shared class predicate,
which means it is always shared and copyable
without needing an explicit .share:
crate::assert_ok!(
r#"
shared struct Point {
x: Int;
y: Int;
}
struct Main {
fn test(given self) → Point {
let p = new Point(22, 44);
p→;
p→;
}
}
"#
);
Shared structs with no generic arguments, such as Int, are always copyable.
A generic shared struct additionally requires all its arguments to be shared;
an owned, unique type argument can prevent copying.
Their fields cannot be individually mutated.
Ordinary structs have mutable fields and require value sharing to become
copyable. Classes retain affine ownership.
Classes cannot be shared as values
A class may have a destructor and cannot be independently shared as a value. Attempting that conversion is an error:
crate::assert_err!(
r#"
class Resource { }
struct Main {
fn test(given self) → shared Resource {
let r = new Resource();
r→.share;
}
}
"#,
expect_test::expect![[r#"
the rule "struct" at (predicates.rs) failed because
pattern `true` did not match value `false`"#]]
);
The prove_is_struct premise fails
because Resource has the Class predicate,
which does not satisfy Resource is struct.
Sharing is idempotent
Sharing an already-shared value is fine – it’s a no-op:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self) → shared Data {
let d = new Data();
d→.share.share;
}
}
"#
);
The inner .share produces shared Data.
The outer .share checks prove_is_struct on shared Data,
which succeeds because a shared permission is always shareable.
The result is still shared Data –
applying shared to an already-shared type normalizes
to the same type.
Struct, unique, shared, and owned
These predicates describe different properties:
T is structmeans values ofTcan be shared as values.T is uniquemeans access must remain exclusive: this includes unique owners and mutable leases. It does not imply ownership.T is sharedmeans values ofTare shared and can be duplicated. This includes values obtained by sharing a place; it does not require ownership.T is ownedmeans fully owned, with no origin dependencies.
For fully owned shared values, write both constraints:
where T is shared, T is owned. For unique ownership, write
where T is unique, T is owned; there is no separate given predicate.
The permission shared[] describes independent sharing; shared[d] describes
sharing from the place d. Any shared permission can be duplicated. Thus
shared Data is both shared and owned, while shared[d] Data is shared without
being owned.
An ordinary owned Data can be shareable without already being shared.
A declaration category describes the data type; a permission describes access
to a particular value.
Giving from alternative origins: ownership requires owned origins
given[p1, ..., pn] satisfies owned when every possible originating
place has an owned type. An owned shared value qualifies just as a unique owner
does; a borrowed alternative cannot be ignored merely because another origin
is owned.
For an ordinary non-shared Wrapper, with borrowed origins referring to
uniquely owned source1 and source2:
| Origin types | given[d1, d2] is owned? |
|---|---|
Any pair of given Wrapper and shared Wrapper | Yes |
Any pair containing shared[source] Wrapper or ![source] Wrapper | No |
Consequently, given/shared alternatives can be owned even though they are
neither uniformly shared nor uniformly unique. Ownership, duplication, and
the mut predicate describe different capabilities.
The complete place type matters
Origins may be fields, nested fields, or fields storing references inside unique containers. The ownership of the container alone does not prove that its stored reference is owned. The table assumes genuinely borrowed references: the model can treat a reference to an owned shared value as owned, because that shared ownership is retained. Reference syntax alone does not decide this predicate.
Candidate lemma and evidence
For a well-formed environment and nonempty list of valid places, the mv owned
rule proves given[p1, ..., pn] is owned from ownership of each place’s
type. Conversely, such a derivation through that rule requires every premise.
This is a candidate lemma, not a proof of preservation during execution.
Tests use complete Dada programs calling a method requiring P is owned.
All concrete given/shared/shared/mut pairs are checked for direct origins; selected
contrasting pairs in both orders cover fields, nested fields, and stored-field
permissions. Every negative program compiles when only its owned requirement
is removed. The class is ordinary and non-generic, avoiding independently shared
value types such as Int as the result. Generic assumptions and runtime cleanup
are outside this evidence.
Unique ownership requires both exclusivity and ownership
P is unique includes mutable leases as well as unique owners, while
P is owned includes shared owners as well as unique owners. Requiring both
admits independent unique ownership and excludes either shared ownership or
mutable leasing alone. There is no separate given predicate.
The accepted program forwards both assumptions through a generic method, checks an ownership-only disjunction, and executes the returned result. Rejected programs remove one assumption or pass a concrete shared owner or mutable lease. These are examples supporting the conjunction, not a proof that all permission combinations have been characterized.
Independent sharing
shared and shared[] are equivalent. Neither introduces a place dependency.
Independent sharing is owned and duplicable
shared and shared[] denote the same permission: a shared value with no
origin dependency. Such a permission satisfies both shared and owned, and
does not satisfy the exclusive/unique predicate. These complete programs test
the empty-origin spelling through surface lowering and generic calls. Bare
places and explicit .share retain their origin; giving then sharing creates
independent shared ownership.
Sharing places
In the giving chapter, we saw how → transfers ownership.
Sometimes you want to read a value while leaving it in its original place.
A bare place expression, such as foo, shares that place. You can write the
same operation explicitly as foo.share.
Sharing a place and sharing a value
Both operations create shared values, but they record different dependencies:
| Expression | Operation | Resulting permission |
|---|---|---|
foo or foo.share | Share the place foo | shared[foo] |
foo→.share | Give the value from foo, then share that value | shared[] |
new Foo().share | Share a newly created value | shared[] |
shared[], also written shared, introduces no place dependency. Sharing a
place preserves its origin in the permission. Permissions in the underlying
type can introduce further dependencies; composing permissions does not erase
those restrictions. See Sharing values.
A simple example
This program creates a Foo, shares its place, and then uses both the original
and the shared result:
crate::assert_ok!(
r#"
struct Data { }
struct Foo {
i: Data;
}
struct Main {
fn test(given self) {
let foo = new Foo(new Data());
let bar = foo.share;
let i = foo.i.share;
bar→;
();
}
}
"#
);
After foo.share, we can still read foo.i. Reading shared data does not
prevent other reads. Let’s walk through how the checker handles this.
Typing foo.share
The checker uses the share place rule:
(access_permitted(env, live_after, Access::SharePlace, place) => env)
(let ty_place = env.place_ty(place)?)
(let ty = Ty::apply_perm(Perm::share_from(set![place]), ty_place.strip_perm()))
----------------------------------- ("share place")
(type_expr(env, live_after, PlaceExpr { access: Access::SharePlace, place }) => (env, ty))
First, access_permitted(env, ..., Access::SharePlace, place) checks the liens
of live variables for conflicting accesses. Then env.place_ty(place) finds
the place’s type. The result applies shared[foo] to the underlying type,
with the outer permission stripped: shared[foo] Foo.
The corresponding access_ty rule constructs the same type:
(let perm = Perm::share_from(set![place]))
----------------------------------- ("share")
(access_ty(_env, Access::SharePlace, place, ty) => Ty::apply_perm(perm, ty.strip_perm()))
The permission records which place was shared. While the resulting value
is live, the checker restricts changes to foo that would invalidate it.
How access control works
When the checker reaches foo.i.share, the environment contains:
| Variable | Type |
|---|---|
self | given Main |
foo | Foo |
bar | shared[foo] Foo |
Sharing foo.i must be compatible with every live variable’s type.
The judgment env_permits_access performs these checks:
(let live_var_tys: Vec<Ty> = live_after.vars().iter().map(|var| env.var_ty(var).unwrap()).cloned().collect())
(parameters_permit_access(env, live_var_tys, access, place) => env)
(accessed_place_permits_access(env, live_after, access, place) => env)
-------------------------------- ("env_permits_access")
(env_permits_access(env, live_after, access, place) => env)
Here bar is live because bar→ appears later, so the checker includes its
shared[foo] Foo type.
Liens
A lien is an access constraint embedded in a type:
#[term]
pub enum Lien {
Share(Place),
Mt(Place),
}
Lien::Share(place) records that the place is shared.
Lien::Mt(place) records a mutable borrow of the place.
The liens judgment extracts these constraints from permissions:
----------------------------------- ("perm-shared")
(liens(_env, Perm::Shared) => ())
For Perm::SharedFrom(places), it creates a Lien::Share for each origin,
as well as the dependencies inherited from that origin’s type.
For example, shared[foo] Foo yields Lien::Share(foo).
Independent shared[] introduces no origin lien.
What sharing permits
The shared rule checks a sharing lien against an access:
(shared_place_permits_access(place, access, accessed_place) => ())
-------------------------------- ("shared")
(lien_permit_access(env, Lien::Share(place), access, accessed_place) => env)
It delegates to:
shared_place_permits_access(shared_place: Place, access: Access, accessed_place: Place,) => ()
The three rules permit different accesses:
share-shareallows sharing any place. Reads are compatible with reads.share-mutationallows mutable access or dropping only when the accessed place is disjoint from the shared place.share-giveallows giving a place that is disjoint from or a prefix of the shared place. Moving a prefix preserves dependencies at the destination.
These checks govern sharing a place. Sharing a value with expr.share instead
checks the inner expression, proves its type shareable, and applies shared[].
For foo→.share, the inner foo→ must pass the giving checks first.
In our example, foo.i.share is checked against Lien::Share(foo).
The share-share rule succeeds because sharing the whole object is compatible
with sharing one of its fields.
Mutation through shared data is an error
Sharing a place grants read access. A mutable borrow of an overlapping field conflicts with a live shared use:
crate::assert_err!(
r#"
struct Data { }
struct Foo {
i: Data;
}
struct Main {
fn test(given self) {
let foo = new Foo(new Data());
let bar = foo.share;
let i = foo.i!;
bar→;
();
}
}
"#,
expect_test::expect![[r#"
the rule "share-mutation" at (accesses.rs) failed because
condition evaluted to false: `place_disjoint_from(accessed_place, shared_place)`
accessed_place = foo . i
shared_place = foo"#]]
);
The share-mutation rule requires foo.i to be disjoint from the shared place
foo. It is a sub-place of foo, so the check fails. While the shared use is
live, the original data cannot be mutated through foo or its fields.
Giving a field of shared data is an error
Similarly, you cannot give away a field of a place with a live shared use:
crate::assert_err!(
r#"
struct Data { }
struct Foo {
i: Data;
}
struct Main {
fn test(given self) {
let foo = new Foo(new Data());
let bar = foo.share;
let i = foo.i→;
bar→;
();
}
}
"#,
expect_test::expect![[r#"
the rule "share-give" at (accesses.rs) failed because
condition evaluted to false: `place_disjoint_from_or_prefix_of(accessed_place, shared_place)`
accessed_place = foo . i
shared_place = foo"#]]
);
foo.i is neither disjoint from nor a prefix of foo, so share-give fails.
Giving just that field would leave the original object partially moved while
bar still depends on the whole object.
The prefix exception permits moving the whole object. After
let moved = foo→, a live shared use of foo depends on moved, and a shared
use of foo.i depends on moved.i. The checker updates dependent types to
preserve those restrictions. The Moves preserve dependencies
property documents this behavior and
its tested scope.
Liveness cancels restrictions
Liens matter while the variable carrying them is live: later code might still use it. Once that variable has no further uses, its restrictions vanish:
crate::assert_ok!(
r#"
struct Data { }
struct Foo {
i: Data;
}
struct Main {
fn test(given self) {
let foo = new Foo(new Data());
let bar = foo!;
let i = foo.i.share;
();
}
}
"#
);
Here bar mutably borrows foo, but the program then shares foo.i.
A live mutable borrow would block this access. However, bar is never used
after let i = ..., so its type ![foo] Foo is absent from the checker’s set
of live types. Its lien no longer blocks sharing the field.
This resembles Rust’s non-lexical lifetimes: an access constraint can end at last use rather than at the end of the enclosing scope.
Mutable borrows are more restrictive
A mutable lien blocks all overlapping accesses, including sharing:
mut_place_permits_access(leased_place: Place, access: Access, accessed_place: Place,) => ()
lease-mutationpermits sharing, mutable access, or dropping only for places disjoint from the leased place.lease-givepermits giving places disjoint from or a prefix of the leased place, preserving dependencies when a prefix moves.
This example fails:
crate::assert_err!(
r#"
struct Data { }
struct Foo {
i: Data;
}
struct Main {
fn test(given self) {
let foo = new Foo(new Data());
let bar = foo!;
let i = foo.i.share;
bar→;
();
}
}
"#,
expect_test::expect![[r#"
the rule "lease-mutation" at (accesses.rs) failed because
condition evaluted to false: `place_disjoint_from(accessed_place, leased_place)`
accessed_place = foo . i
leased_place = foo"#]]
);
bar is live because bar→ occurs later. Its Lien::Mt(foo) is active, and
foo.i overlaps foo, so the attempt to share the field is rejected.
Disjoint access is fine
Sharing or mutably borrowing foo does not prevent accessing unrelated data:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self) {
let foo = new Data();
let other = new Data();
let bar = foo.share;
other→;
bar→;
();
}
}
"#
);
bar shares foo, creating Lien::Share(foo). Giving other is permitted
because other and foo are disjoint variables.
Transitive restrictions
Sharing a place also preserves dependencies in that place’s type:
crate::assert_err!(
r#"
struct Data { }
struct Foo {
i: Data;
}
struct Main {
fn test(given self) {
let p = new Foo(new Data());
let q = p!;
let r = q.share;
let i = p.i.share;
r→;
();
}
}
"#,
expect_test::expect![[r#"
the rule "lease-mutation" at (accesses.rs) failed because
condition evaluted to false: `place_disjoint_from(accessed_place, leased_place)`
accessed_place = p . i
leased_place = p"#]]
);
Here q has type ![p] Foo and r has type shared[q] Foo. The liens of
r include both Lien::Share(q) and the Lien::Mt(p) inherited from q.
Consequently, p.i.share is rejected by lease-mutation: p.i overlaps p.
Although q has no further uses after let r, the live variable r still
carries the transitive dependency on p.
Giving a value can preserve a mutable borrow, but only when all possible origins supply the required capability:
Giving from alternative origins: every origin must satisfy mut
The permission given[p1, ..., pn] satisfies the mut predicate only
when every possible originating place has a type satisfying mut. For the
ordinary class used here, this means that every alternative supplies a mutable
borrow (a lease), rather than merely permitting some form of mutation.
A lease is different from a unique owner
The current mut predicate distinguishes mutable borrowing from unique
ownership. A given Wrapper permits field assignment but does not satisfy
mut. Therefore, testing x.value = 42 alone would not establish this property.
The tests instead pass x to a method requiring P is mut, with
P = given[d1, d2].
For struct Wrapper { value: Int; }:
| Origin types | given[d1, d2] is mut? |
|---|---|
![source1] Wrapper, ![source2] Wrapper | Yes |
![source1] Wrapper, given Wrapper (either order) | No |
![source1] Wrapper, shared[source2] Wrapper (either order) | No |
![source1] Wrapper, shared Wrapper (either order) | No |
Any pair with neither origin satisfying mut | No |
Here d1 and d2 are the possible originating places; source1 and source2
are independent referents. Giving from an owner does not by itself turn the
result into a lease. Likewise, failure to prove shared does not prove mut.
Projected origins
The obligation concerns the full type of each originating place, including
d1.field and d1.inner.field. A field accessed through a mutable borrow
can satisfy mut. A unique container may also store a mutable reference in
a field; in that case the field’s type, not the container’s ownership, matters.
A projected origin containing a shared reference cannot supply a mutable lease.
Candidate lemma and evidence
For a well-formed environment and a nonempty list of valid places, a derivation
of given[p1, ..., pn] is mut entails a derivation that the type of each
pi satisfies mut. Conversely, those premises suffice through the model’s
mv mut rule. This is a candidate lemma, not a theorem proved by these tests.
Four groups cover all pairs of given, mut, shared, and share origins:
direct places, fields, nested fields, and permission-parameterized fields stored
in unique containers. Every test contains a complete Dada program calling a
method with an explicit P is mut requirement. Only the mut/mut pair
should compile with that requirement.
Each rejecting test first checks that the same program compiles with just
where P is mut removed. This isolates the requirement from the validity of
the signature, projected places, and argument passing. The error snapshot then
records the rejection with the requirement present. Referents remain live
through the call. These are end-to-end type-checking tests, with no direct
calls to predicate-proving functions.
This property concerns static predicate classification, not general assignment permission, runtime alias safety, or arbitrary generic predicate assumptions.
A shared borrow does not grant a mutable lease
Borrowing with share produces a shared view. It does not satisfy mut, even
when the borrowed place itself holds a mutable lease. A caller cannot pass that
view to a method requiring P is mut merely because the underlying owner or
lease permits mutation.
For an ordinary non-shared Wrapper, these examples distinguish the view
from the place it borrows:
| View | Satisfies shared? | Satisfies mut? |
|---|---|---|
shared[source], where source is uniquely owned | Yes | No |
shared[lease], where lease: ![source] Wrapper | Yes | No |
shared[lease.field], through a mutable container lease | Yes | No |
shared ![source], after cancelling a dead intermediate lease | Yes | No |
The lifetime of the intermediate lease does not upgrade the view. When the
lease is dead, the view can be coerced to shared ![source]; the shared
component remains. When the lease stays live, it can be passed to a method
requiring mut after the view’s final use. Its predicate remains true throughout;
the view temporarily restricts access to it.
Candidate lemma and evidence
For concrete permissions and an ordinary non-shared struct, adding a shared
view by share does not derive the mut predicate from the underlying place’s
mut predicate. Eliminating a dead intermediate place preserves that shared
component. This is a candidate lemma about static permission classification,
not a proved theorem about arbitrary generic assumptions or runtime aliases.
Each example constructs its view in a complete Dada program and passes it to
a method requiring either shared (accepted) or mut (rejected). The cases
cover a unique owner, a live lease, a dead lease, explicit cancellation, and a
projected field. Each rejection has a control with only its mut requirement
removed. The live-lease cases also pass the original lease to a method requiring
mut after the view’s last use. Referents remain live throughout the calls.
Giving preserves the origins’ borrowing dependencies
A value with permission given[p1, ..., pn] retains borrowing
dependencies from every possible originating place’s type. Giving that value
to another binding does not erase those dependencies. Duplicating it, when
permitted, leaves each live duplicate subject to the same restrictions.
For example, if d1: shared[source1.field] Data and
d2: shared[source2.field] Data, then a live value with permission
given[d1, d2] protects both possible referents from mutation. Even after
d1, d2, the original value, and one duplicate have their last uses, a
surviving duplicate still protects both fields. For mut origins, the
surviving value blocks reads as well as mutations of the referents.
The origins are d1 and d2; their referents are source1.field and
source2.field. given inherits the origins’ dependencies rather than
creating fresh borrows of the origin bindings. Those bindings need not stay
live. Origins can also be projected places such as d1.field storing a place sharing.
Disjoint sibling fields remain accessible. Once the last dependent value has its final use, the borrowing restrictions cease. If the referent itself is moved to a new binding while a dependent value stays live, its restrictions follow the new place, as in the separate move-dependency property.
Candidate lemma and evidence
In a well-formed environment, the liens of the permission
given[p1, ..., pn] are the union of the liens obtained from the types of
those places. No additional lien on an origin is introduced by given
itself. For a permitted transfer to a fresh binding, the resulting live value
retains those referent obligations, accounting for any place substitutions.
This is a candidate static preservation lemma, not a proved theorem.
Complete Dada programs check both alternative referents separately, projected
origins with stored refs, disjoint siblings, and access after the surviving
value’s final use. Initialized local examples transfer a mutable borrow
through given after its origin’s last use; paired examples check the
same restriction before and after relocating the referent. The duplication
cases were extracted from given_from_duplication_requires_shared_origins.
These examples use ordinary non-shared structs. They concern static access restrictions, not runtime mutable-pointer relocation, scope-exit cleanup, or every permission composition and generic type.
Access constraints
| Access | Permission | Lien | Permits sharing the origin? | Permits mutating the origin? |
|---|---|---|---|---|
place or place.share | shared[place] | Lien::Share(place) | Yes | No |
place! | ![place] | Lien::Mt(place) | No | No |
The checker extracts liens from live types, compares the affected places for overlap, and uses liveness to release restrictions after the last use.
Returning values from calls
A method can return ownership directly with → given Data, including by giving
one of its owned parameters. Its return permission can also name its receiver
or parameters. For example, given[x] describes a value given from parameter
x, while shared[x] describes sharing from it. At a call site, the checker
resolves these permissions before removing the temporary bindings used for the
arguments.
The following properties describe separate cases of that process. Each property
has its own test module; call_returns groups them without asserting a broader
soundness theorem. Here, “remains borrowed” means that a live returned value
continues to restrict conflicting accesses to its referents in the caller.
Ownership can escape a call
A method declaring → given Data can return x→ from a parameter
x: given Data, or self→ from a given self receiver. The caller can
then pass the returned value to a method requiring given Data: ownership
survives the disappearance of the parameter binding. With two given
parameters, either can supply the owned result.
Ownership can also escape when the declared return permission names a
parameter: given[x] resolves to given when x receives a given
argument. An explicit given return promises ownership directly; it need
not name which parameter supplied the value.
The same applies to given[self] and to given[x, y] when both
arguments are given. A receiver named self in the caller does not change
which binding the callee’s return permission denotes, even when the caller’s
receiver is borrowed.
Evidence and scope
Complete Dada programs with explicit given returns move a named argument,
the receiver itself, or the first or second of two given arguments into the
result. The two-argument cases use separate methods with fixed choices; they
do not test branch-dependent moves. Consumer calls check that each returned
value is usable as given after the call, then execute that transfer.
The given examples cover a receiver, a named argument, and two possible
given origins. Their receiver examples create a fresh result with the
receiver’s permission; their named-argument examples return the argument
itself. Field reads print 42 after the call; separate consumer calls check
that the result satisfies given.
Every program is type-checked and interpreted from Main.main. Snapshots
check the executed calls, printed field values where present, successful
completion, and an empty final heap. The borrowed-caller example invokes a
generic shared receiver with shared[caller], so it exercises the call from an
actual borrowed receiver.
These tests cover ordinary non-shared structs and given arguments. They
provide static and runtime evidence for these programs, not a preservation
theorem or coverage of every owned permission, type, or cleanup path.
Borrows of consumed arguments cannot escape a call
A call cannot return a borrow whose referent is a uniquely owned argument
destroyed when the call returns. For an ordinary non-shared Data, passing
d→ to a parameter x: given Data does not permit the call to return
shared[x] Data. The caller’s former ownership of d does not keep that consumed
argument alive.
Every possible referent in the return permission must survive. A return type
shared[x, y] Data is rejected when either argument is consumed in this way,
even when the method body returns only a borrow of the other argument.
The contrasting case passes d.share to the same generic method. The returned
borrow can then refer to d, which remains in the caller, instead of depending
on the temporary parameter binding. Merely naming a parameter in the return
permission does not make its borrow invalid.
Evidence and scope
Complete Dada programs check a consumed receiver, a named argument, two
consumed arguments, and one borrowed argument paired with a consumed one.
A positive/negative pair uses the identical generic method returning shared[x]
and changes its argument from d.share to d→ (and the corresponding
permission argument). Both programs attempt to read the result’s integer field
with print(result.n→); the borrowed-argument program type-checks and
executes, printing 42, while the given-argument program is rejected at the
call. The other rejected calls
report dangling borrows even when their results are unused.
This property concerns static rejection of borrows of destroyed given
arguments. It does not claim that references to all owned values must be
rejected: shared ownership can survive independently. The evidence uses
ordinary non-shared structs. Execution of the valid control does not prove
general runtime destruction behavior or cover every permission composition.
Forwarded borrows keep their referents borrowed
When a method returns a borrow through one of its borrowed parameters, the caller’s referent remains borrowed while the returned value is live. The method parameter need not remain in scope: resolving the return permission carries its borrowing dependency back to the caller’s referent.
A shared borrow returned through a shared-borrowed argument permits another shared borrow of the referent but prevents mutable access. A mutable borrow returned through a mutably borrowed argument prevents both shared and mutable access to the referent. Disjoint fields remain accessible, and the restrictions cease after the returned value’s last use. Returning a shared view through a mutable argument can retain the underlying mutable borrowing restrictions; that composition is covered in the alternative-referent property.
Evidence and scope
Complete Dada programs forward shared borrows through a named parameter and
a receiver, then read an integer field through the returned value with
print(result.n→). Both programs type-check, execute, and print 42.
Paired accepting and rejecting programs check access to a single
caller-owned referent while the returned borrow is live and after its last
use. A projected mutable-borrow example checks that a disjoint sibling field
remains accessible. All accepting programs execute successfully, return
unit, and leave no live allocations; rejecting programs assert the static
borrowing conflict.
These tests use ordinary non-shared structs and single-origin return
permissions. They demonstrate static access restrictions and successful
execution for these examples, not a proved preservation theorem or all
runtime pointer behavior. Alternative return origins are covered by
all_possible_return_referents_remain_borrowed.
All possible return referents remain borrowed
When a method’s return signature names several possible borrowed origins, each corresponding caller referent remains borrowed while the returned value is live. This restriction follows the signature even when the method body always returns a borrow of its first argument.
Here x and y are the callee’s parameter bindings; d1 and d2 are the
caller’s referents. Returning shared[x, y] or ![x, y] through borrowed
arguments must retain the dependencies on both d1 and d2 after the call’s
temporary bindings disappear. The callee’s use of x alone does not let the
caller disregard y’s declared contribution to the result.
Evidence and scope
Complete Dada programs check each referent independently for shared returns, mutable returns, and shared returns through mutable arguments. A live shared result prevents discarding either referent; a live result returned through mutable arguments prevents mutably reborrowing either referent. Each rejection has a control performing the same access after the result’s last use. Another control consumes both referents after the result’s last use.
The standalone d1→; and d2→; statements discard their values.
Their rejection does not say that every move is forbidden: a move into a new
binding can relocate a referent and its borrowing dependencies, as described
by moves_preserve_dependencies.
All accepting programs type-check and execute. Shared field reads print 42
from the first argument, and the mutable result prints 43 after assignment.
Every accepting program returns unit and leaves no live allocations.
These snapshots observe the referent actually returned; the rejection tests
separately establish static borrowing restrictions on both possible referents.
These examples use ordinary non-shared structs and two direct borrowed arguments. They provide static and runtime evidence for these programs, not a proof for arbitrary signatures, all runtime choices, or pointer relocation.
Static and runtime evidence
These properties use complete programs to check acceptance and rejection. Accepted programs also run through the interpreter with output, result, and heap snapshots. Rejected programs use checker-error snapshots; they are not executed. The separate runtime normalization module contains direct frame tests that inspect the returned value’s type and verify that method bindings do not leak into the caller. Those tests check their type declarations but evaluate the individual calls directly, without type-checking them. The same module also has two end-to-end examples that type-check and run complete programs, covering an owned field returned to a borrowed caller and nested calls forwarding a borrow. The direct frame assertions and the end-to-end examples provide different kinds of evidence.
The static result accounts for all possibilities in a return signature. The interpreter’s result type describes the value actually returned. Keeping these observations separate helps distinguish conservative borrowing restrictions from the runtime choice of referent.
Subtyping
In the previous chapters,
we saw how types carry permissions
and how sharing a place creates a permission such as shared[place].
But we glossed over an important question:
what happens when a value’s type doesn’t exactly match
what’s expected?
That’s where subtyping comes in. Subtyping lets one type stand in for another when the substitution is safe.
A motivating example
Here’s a simple function that creates a Data value
and returns it:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self) → Data {
let d: given Data = new Data();
d→;
}
}
"#
);
The annotation let d: given Data makes the permission explicit,
but the return type is just Data – no permission written.
These match because given is the default permission for return types,
fields, local annotations, and nested type arguments.
In those positions, Data means given Data. An outermost surface input type
that names a class or struct instead introduces a fresh permission variable.
A bare type variable T retains the identity permission given, preserving
the type supplied for T without a separate permission parameter. See
Surface syntax.
So both sides are given Data, and subtyping is trivially satisfied.
But what about less trivial cases? Consider a function that shares a place and returns the result:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) → shared[d] Data {
d.share;
}
}
"#
);
The expression d.share creates a shared value
with type shared[d] Data.
The return type is also shared[d] Data – an exact match.
But internally, the type checker needs to verify
that the permission shared[d] on the expression’s type
is compatible with the permission shared[d] on the return type.
That verification happens through permission reduction –
a process we’ll explain in this chapter.
When subtyping happens
Subtyping is invoked through the type_expr_as judgment,
which checks that an expression’s type is a subtype
of some expected type:
(type_expr(env, live_after, expr) => (env, ty))
(sub(env, live_after, ty, as_ty) => ())
-------------------------------- ("type_expr_as")
(type_expr_as(env, live_after, expr, as_ty) => env)
The judgment first computes the expression’s type with type_expr,
then calls sub to verify it’s a subtype of the expected type.
This happens in three situations:
- Return types – the body of a method is checked against the declared return type.
- Let bindings with type annotations –
let x: T = exprchecks that the expression’s type is a subtype ofT. - Method arguments and field initialization – each argument’s type must be a subtype of the declared parameter type.
Type subtyping: same declaration required
Dada has no inheritance hierarchy –
there’s no equivalent of Java’s extends or Rust’s trait objects.
Subtyping only works between types with the same declared type name.
The difference is always in the permissions.
The sub judgment handles this through the “sub-classes” rule:
(if let Ty::NamedTy(NamedTy { name: name_a, parameters: parameters_a }) = ty_a)
(if let Ty::NamedTy(NamedTy { name: name_b, parameters: parameters_b }) = ty_b)
(if name_a == name_b)!
(sub_perms(env, live_after, perm_a, perm_b) => ())
(let variances = env.variances(name_a)?)
(if parameters_a.len() == variances.len())
(if parameters_b.len() == variances.len())
(for_all(triple in izip!(variances, parameters_a, parameters_b))
(let (v, pa, pb) = triple)
(sub_generic_parameter(env, live_after, v, perm_a, pa, perm_b, pb) => ()))
------------------------------- ("sub-classes")
(sub(env, live_after, PermTy(perm_a, ty_a), PermTy(perm_b, ty_b)) => ())
The rule requires matching declared type names
and then delegates to sub_perms
for the permission comparison.
Different declarations are incompatible
If the declared type names don’t match, subtyping fails:
crate::assert_err!(
r#"
struct Foo { }
struct Bar { }
struct Main {
fn test(given self) {
let f = new Foo();
let b: Bar = f→;
();
}
}
"#,
expect_test::expect!["judgment had no applicable rules: `check_program { program: struct Foo { } struct Bar { } struct Main { fn test (given self) → () { let f = new Foo () ; let b : Bar = f → ; () ; } } }`"]
);
There is no rule that can prove Foo <: Bar –
the “sub-classes” rule requires name_a == name_b,
and Foo and Bar are different names.
Reduced permissions
The sub_perms judgment doesn’t compare permissions directly.
Instead, it first reduces each permission
into a canonical form called a RedPerm,
then compares the reduced forms.
Why not compare permissions directly? Because permissions as written in source code have structure – composition, place sets, liveness dependencies – that makes direct comparison impractical. Reduction normalizes all of this into a uniform representation.
What is a RedPerm?
A RedPerm is a set of RedChains.
Each RedChain is a sequence of RedLinks.
Links are the atomic building blocks of reduced permissions:
| RedLink | Source permission | Meaning |
|---|---|---|
| (empty chain) | given | Unique ownership |
Shared | shared | Shared ownership (copy) |
ShareLive(place) | shared[place] | Sharing origin is live |
ShareDead(place) | shared[place] | Sharing origin is dead |
Mtl(place) | ![place] | Mutable lease, place is live |
Mtd(place) | ![place] | Mutable lease, place is dead |
Notice the live/dead distinction:
shared[d] reduces to ShareLive(d) if d is still used later in the program,
and ShareDead(d) if it isn’t.
The same for ![d] → Mtl(d) or Mtd(d).
This distinction matters for permission comparison –
dead permissions can be cancelled or promoted,
as we’ll see in the
Liveness and cancellation chapter.
Reducing simple permissions
The simplest reductions are direct translations:
-
given→ one chain:[](the empty chain). No links – just ownership. This is the identity permission. -
shared→ one chain:[Shared]. A single link indicating shared ownership. -
shared[d](wheredis live) → one chain:[ShareLive(d)]. A single place-sharing link. -
 → one chain:[Mtl(d)]. A single mutable lease link.
Multi-place permissions become multiple chains
When a permission mentions multiple places,
it produces one chain per place.
This is why RedPerm is a set of chains:
shared[d1, d2]→ two chains:{ [ShareLive(d1)], [ShareLive(d2)] }.
The set representation means that
shared[d1, d2] describes a permission
that may share from d1 or d2 (or both).
For the subtype to hold,
every chain in the subtype’s RedPerm
must be matched by some chain in the supertype’s RedPerm.
Composition: how permissions combine
Permissions combine when you access a field
through a shared value or a mutable lease.
If r has type shared[d] Outer
and Outer has a field i: Inner,
then the place r.i has type shared[d] Inner –
the shared[d] permission wraps the field’s type.
Using bare r.i as an expression additionally shares that place, producing
shared[r.i] Inner; expanding that origin retains the dependency on d.
Internally, this creates a composed permission:
Perm::Apply(shared[d], given) – the outer shared[d] applied
to the field’s given permission.
How does reduction handle this?
The append_chain rule
When reducing a composed permission P Q,
the type checker reduces P and Q separately,
then appends the chains using append_chain.
The rule has two cases:
-
If the right-hand chain is shared (
Shared,ShareLive, etc.): the left-hand side is discarded. Copy permissions absorb anything applied to them. -
If the right-hand chain is NOT copy (
given,Mtl, etc.): the chains are concatenated into a longer chain.
Example: shared[d] applied to given
Consider accessing a field through a shared value:
crate::assert_ok!(
r#"
struct Inner { }
struct Outer {
i: Inner;
}
struct Main {
fn test(given self, d: given Outer) → shared[d] Inner {
let r: shared[d] Outer = d.share;
r.i→;
}
}
"#
);
The place r.i has type shared[d] Inner –
but internally, the field i has type Inner (which is given Inner),
and accessing it through r: shared[d] Outer composes them.
Reduction of the composed permission:
shared[d]→[ShareLive(d)]given→[](empty chain, not copy)- Append:
[ShareLive(d)]++[]=[ShareLive(d)]
The given disappears.
Since the empty chain represents identity,
appending it to anything is a no-op.
This is why shared[d] given Inner and shared[d] Inner are equivalent –
given is the identity permission.
Example: shared[w] applied to shared (copy absorbs)
Now consider a field whose type is a shared struct:
crate::assert_ok!(
r#"
shared struct Point {
x: Int;
y: Int;
}
struct Wrapper {
p: Point;
}
struct Main {
fn test(given self, w: given Wrapper) → Point {
let r: shared[w] Wrapper = w.share;
r.p→;
}
}
"#
);
The field p has type Point, which is a shared struct.
Accessing r.p through r: shared[w] Wrapper
composes shared[w] with shared (the permission of Point).
Reduction:
shared[w]→[ShareLive(w)]shared→[Shared](copy!)- Append:
[ShareLive(w)]++[Shared]→[Shared]
The shared[w] is discarded.
Because shared is a copy permission,
the append_chain rule drops the left-hand side entirely.
The result is just [Shared] – plain shared ownership.
This makes intuitive sense: if the field is already shared (freely copyable), sharing its container adds no restriction. You just get a shared copy.
That’s why r.p→ has type Point (i.e., shared Point)
even though we accessed it through a shared place –
the shared[w] was absorbed by the shared.
Example: shared[p] applied to ![d]
Now consider sharing a place containing a mutable lease:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self) {
let d: given Data = new Data();
let p: ![d] Data = d!;
let q: shared[p] ![d] Data = p.share;
();
}
}
"#
);
The expression p.share has type shared[p] Data,
and p has type ![d] Data.
If we were to access a field of this value,
the composed permission would be Apply(shared[p], ![d]).
Reduction:
shared[p]→[ShareLive(p)]![d]→[Mtl(d)](not copy!)- Append:
[ShareLive(p)]++[Mtl(d)]=[ShareLive(p), Mtl(d)]
This is a genuine two-link chain.
The ![d] is not copy, so it doesn’t absorb –
the chain records both links.
This chain means “sharing from p,
which is itself a mutable lease from d.”
Whether this chain can match some target permission
depends on liveness and cancellation rules –
if p is dead, reduction produces ShareDead(p), which may be resolved.
That’s covered in the
Liveness and cancellation chapter.
How comparison works
The sub_perms judgment ties it all together:
(red_perm(env, live_after, perm_a) => red_perm_a)
(red_perm(env, live_after, perm_b) => red_perm_b)
(for_all(red_chain_a in red_perm_a.chains.clone())
(red_chain_sub_perm(env, red_chain_a, red_perm_b) => ()))
--- ("sub_red_perms")
(sub_perms(env, live_after, perm_a, perm_b) => ())
- Reduce both permissions to
RedPerms - For every chain in the subtype’s
RedPerm, find a matching chain in the supertype’sRedPerm
“Matching” means red_chain_sub_chain –
a judgment with rules for each kind of link comparison.
The Subtypes and subpermissions chapter
walks through these rules in detail:
- Place ordering –
shared[d.f] <: shared[d]because sub-places are more specific. - Copy permissions –
shared <: shared[d]because independent ownership satisfies a place dependency. - Liveness and cancellation – dead links can be dropped or promoted during comparison.
Shared structs and permission distribution
Shared structs get a special subtyping rule. Because a shared struct’s direct fields must already be shared (copy) types, the outer permission only matters insofar as it affects the type parameters.
Consider Int – a shared struct with no type parameters:
crate::assert_ok!(
r#"
struct Main {
fn test(given self) → Int {
let x: shared[self] Int = 0;
x→;
}
}
"#
);
shared[self] Int <: Int – sharing an Int still yields an Int.
This works in both directions:
crate::assert_ok!(
r#"
struct Main {
fn test(given self) → Int {
let x: Int = 0;
let y: shared[self] Int = x→;
y→;
}
}
"#
);
Int <: shared[self] Int also holds.
The “sub-shared-classes” rule
The rule that makes this work is:
(if let Ty::NamedTy(NamedTy { name: name_a, parameters: parameters_a }) = ty_a)
(if let Ty::NamedTy(NamedTy { name: name_b, parameters: parameters_b }) = ty_b)
(if name_a == name_b)
(if let true = env.is_shared_ty(name_a)?)!
(if parameters_a.len() == parameters_b.len())
(for_all(pair in parameters_a.iter().zip(parameters_b))
(let (pa, pb) = pair)
(sub(env, live_after, perm_a.apply_to_parameter(pa), perm_b.apply_to_parameter(pb)) => ()))
------------------------------- ("sub-shared-classes")
(sub(env, live_after, PermTy(perm_a, ty_a), PermTy(perm_b, ty_b)) => ())
For shared structs, the rule distributes the outer permission
into the type parameters.
To check A SharedStruct[B] <: X SharedStruct[Y],
it checks A B <: X Y for each parameter pair.
The key insight: when a shared struct has zero type parameters
(like Int), there’s nothing to distribute into.
The for_all over parameters is vacuously true –
so the subtyping holds regardless of what permissions A and X are.
The outer permission is irrelevant because there are no type parameters
for it to affect.
Shared structs with copy parameters
The same rule extends to shared structs with parameters, as long as those parameters are copy types:
crate::assert_ok!(
r#"
shared struct Point {
x: Int;
y: Int;
}
struct Main {
fn test(given self) → Point {
let p: shared Point = new Point(1, 2);
p→;
}
}
"#
);
shared Point <: Point works because
the rule distributes: it checks shared Int <: given Int
for each parameter.
Since Int is itself a shared struct with no parameters,
that check is vacuously true.
Non-copy parameters block erasure
But if a shared struct wraps a non-copy type, the outer permission matters – it distributes into the type parameter and changes the meaning:
crate::assert_err!(
r#"
shared struct Box[type T] {
value: T;
}
struct Data { }
struct Main {
fn test(given self, d: given Data) → Box[Data] {
let b: shared[d] Box[Data] = new Box[Data](new Data());
b→;
}
}
"#,
expect_test::expect!["judgment had no applicable rules: `check_program { program: shared struct Box [type] { value : ^type0_0 ; } struct Data { } struct Main { fn test (given self d : given Data) → Box[Data] { let b : shared [d] Box[Data] = new Box [Data] (new Data ()) ; b → ; } } }`"]
);
shared[d] Box[Data] </: Box[Data] fails because
the rule distributes: it needs shared[d] Data <: Data.
But Data is an ordinary struct (not a shared struct),
so shared[d] cannot be erased.
Sharing Data from a place preserves a dependency that owned Data does not have.
Summary
Subtyping in Dada operates on permissions, not inheritance hierarchies. Two types are related by subtyping only when they name the same declaration, and the key question is whether one permission can stand in for another.
The process:
- Decompose each type into permission + base type
- Reduce each permission to a
RedPerm(a set ofRedChains) - Compare chain by chain – every chain in the subtype must match some chain in the supertype
Composition flattens through append_chain:
copy permissions absorb anything applied to them,
while non-copy permissions concatenate into longer chains.
Shared structs get special treatment:
permissions distribute into type parameters,
and shared structs with no parameters (like Int)
make the permission check vacuous.
Given preserves a generic type’s permissions
given is the identity permission. A bare type-variable input defaults to
given T, whether the variable belongs to its class or its method. Neither
spelling requires a relative bound or introduces a permission argument.
A nonidentity shared permission still requires the relative bound; the paired
declarations test that distinction through the surface pipeline.
Instantiating T with shared Data or ![value] Data preserves that
permission through a bare-T identity method. The complete
programs use the returned values: sharing remains duplicable, and a returned
mutable borrow can update its referent. The caller and callee deliberately
reuse the input name value, checking that type-argument origins remain in
the caller’s scope. Dropping a referent before the returned borrow’s last use
is rejected.
Empty-origin shorthand [] T also makes the identity permission explicit
and requires no generated permission argument at a call.
Subtypes and subpermissions
In the previous chapter,
we saw how subtyping works:
the type checker reduces permissions to RedPerms
(sets of RedChains)
and then compares them chain by chain.
This chapter dives into the red_chain_sub_chain judgment –
the rules that determine whether one chain
can stand in for another.
The topics:
- Place ordering – how sub-places and place sets create a partial order on permissions.
- Copy permissions –
the three copy permissions (
shared,shared[d],shared ![d]), how they relate, and how they compose. - Liveness and cancellation – how dead links are resolved during comparison.
Place ordering
Permissions in Dada carry places – they record where sharing or a mutable lease originates. These places create a natural ordering on permissions: more specific places are subtypes of less specific ones.
There are two dimensions to this ordering: sub-places (field projections) and place sets (multiple sources).
Sub-place ordering
Sharing a field restricts a smaller place than sharing the whole object.
Sharing d.left leaves more of d available for other accesses:
crate::assert_ok!(
r#"
struct Data {
left: given Data;
right: given Data;
}
struct Main {
fn test(given self, d: given Data) {
let r: shared[d] Data = d.left.share;
();
}
}
"#
);
The expression d.left.share has type shared[d.left] Data,
but the annotation on r expects shared[d] Data.
This works because d is a prefix of d.left –
a value shared from d.left depends on a place within d.
The same principle applies to mutable leases:
crate::assert_ok!(
r#"
struct Data {
left: given Data;
right: given Data;
}
struct Main {
fn test(given self, d: given Data) {
let r: ![d] Data = d.left!;
();
}
}
"#
);
![d.left] <: ![d] –
a lease of a field is a subtype of a lease of the parent.
The reverse fails
Going the other direction doesn’t work.
Sharing all of d cannot promise a dependency only on d.left:
crate::assert_err!(
r#"
struct Data {
left: given Data;
right: given Data;
}
struct Main {
fn test(given self, d: given Data) {
let r: shared[d.left] Data = d.share;
();
}
}
"#,
expect_test::expect![[r#"
the rule "(shared[place]::P) vs (shared[place]::P)" at (redperms.rs) failed because
condition evaluted to false: `place_b.is_prefix_of(place_a)`
place_b = d . left
place_a = d"#]]
);
shared[d] </: shared[d.left] –
d.left is not a prefix of d,
so the prefix check fails.
The rule
The chain comparison rule that handles sub-places is:
(if place_b.is_prefix_of(place_a))
(red_chain_sub_chain(env, tail_a, tail_b) => ())
--- ("(shared[place]::P) vs (shared[place]::P)")
(red_chain_sub_chain(
env,
Head(RedLink::ShareLive(place_a) | RedLink::ShareDead(place_a), Tail(tail_a)),
Head(RedLink::ShareLive(place_b) | RedLink::ShareDead(place_b), Tail(tail_b)),
) => ())
It requires place_b.is_prefix_of(&place_a) –
the supertype’s place must be a prefix of (or equal to)
the subtype’s place.
There’s an analogous rule for mut:
(if place_b.is_prefix_of(place_a))
(red_chain_sub_chain(env, tail_a, tail_b) => ())
--- ("(mut::P) vs (mut::P)")
(red_chain_sub_chain(
env,
Head(RedLink::Mtl(place_a) | RedLink::Mtd(place_a), Tail(tail_a)),
Head(RedLink::Mtl(place_b) | RedLink::Mtd(place_b), Tail(tail_b)),
) => ())
Place sets
Permissions can mention multiple places.
shared[d1, d2] means “a value shared from d1 or d2” –
which means both d1 and d2 must be kept unmodified.
A permission that restricts fewer places is a subtype of one that restricts more:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self, d1: given Data, d2: given Data) {
let r: shared[d1, d2] Data = d1.share;
();
}
}
"#
);
shared[d1] <: shared[d1, d2] –
the subtype restricts d1;
the supertype restricts both d1 and d2.
The supertype is more restrictive,
so it’s safe to use the subtype in its place.
This might feel backwards at first,
but think about it from the caller’s perspective:
if you hold a shared[d1, d2] Data,
you know not to modify d1 or d2.
If the actual value only depends on d1,
that’s fine – you’re being extra careful
by also avoiding modifications to d2.
Dropping a source fails
The reverse doesn’t work – you cannot discard a possible sharing origin:
crate::assert_err!(
r#"
struct Data { }
struct Main {
fn test(given self, d1: given Data, d2: given Data) {
let r: shared[d1, d2] Data = d1.share;
let s: shared[d1] Data = r→;
();
}
}
"#,
expect_test::expect![[r#"
the rule "(shared[place]::P) vs (shared[place]::P)" at (redperms.rs) failed because
condition evaluted to false: `place_b.is_prefix_of(place_a)`
place_b = d1
place_a = d2"#]]
);
shared[d1, d2] </: shared[d1] –
the value might depend on d2,
and the target type doesn’t protect d2 from modification.
How place sets work in the rules
Internally, a permission like shared[d1, d2]
is represented as a RedPerm with multiple chains –
one chain ShareLive(d1) and another chain ShareLive(d2).
For the subtype to hold,
every chain in the subtype
must match some chain in the supertype.
When checking shared[d1] <: shared[d1, d2]:
the subtype has one chain ShareLive(d1).
The supertype has two chains: ShareLive(d1) and ShareLive(d2).
The single chain matches ShareLive(d1) in the supertype. Done.
When checking shared[d1, d2] <: shared[d1]:
the subtype has two chains: ShareLive(d1) and ShareLive(d2).
ShareLive(d1) matches, but ShareLive(d2) has no match in the supertype.
The check fails.
Combining both dimensions
Sub-places and place sets compose naturally. Here’s a case that uses both:
crate::assert_ok!(
r#"
struct Data {
left: given Data;
right: given Data;
}
struct Main {
fn test(given self, d: given Data) {
let r: shared[d.left, d.right] Data = d.left.share;
let s: shared[d] Data = r→;
();
}
}
"#
);
shared[d.left, d.right] <: shared[d] –
both d.left and d.right are sub-places of d,
so both chains satisfy the prefix check.
The same holds for leases:
crate::assert_ok!(
r#"
struct Data {
left: given Data;
right: given Data;
}
struct Main {
fn test(given self, d: given Data) {
let r: ![d.left, d.right] Data = d.left!;
let s: ![d] Data = r→;
();
}
}
"#
);
![d.left, d.right] <: ![d] works by the same logic.
Shared permissions
Some permissions are shared.
Any shared permission can be duplicated.
This is expressed by the predicate P is shared, which includes sharing from
places as well as independent shared ownership.
Here are three examples of shared permissions in Dada,
and understanding how they relate to each other
is key to understanding permission comparison.
Examples of shared permissions
shared, also written shared[], means independent shared ownership.
Such a value can be duplicated freely
and lives as long as any copy exists.
It places no restrictions on the environment.
shared[d] means sharing from the place d.
It can be duplicated freely, but depends on d.
While the shared result is live, d cannot be modified.
shared ![d] – a composed permission.
This is the result of sharing a lease:
you take a mutable lease ![d]
and share the resulting value, for example with lease→.share.
The result is shared (because the outer shared makes it so),
but it still restricts d
(because the underlying lease is active).
Giving from alternative origins: duplication requires shared origins
For an ordinary non-shared struct, a value with permission
given[p1, ..., pn] may be duplicated only if every possible originating
place has a type satisfying the shared predicate.
An origin is a place listed in given: x: given[a, b] Data
means that x could have been given from a or from b. These are alternative
origins of one value, not two values stored in x. Giving a shared value can
duplicate it; giving a uniquely owned value transfers ownership. Uncertainty
about which occurred cannot grant permission to duplicate a unique value.
For struct Data {}, the examples are:
Type of a | Type of b | Duplicate x: given[a, b] Data? |
|---|---|---|
shared Data | shared Data | Yes |
shared Data | given Data | No |
given Data | shared Data | No |
given Data | given Data | No |
Duplication here means using x→ twice. The first give must preserve x
for the second; finding just one shared alternative does not justify that.
Origins can also be field places: given[d1.field, d2.field] Data, or
nested places such as d1.inner.field. The type of the complete place
matters. A unique container can hold a declared shared Data field;
conversely, accessing a Data field through a shared container is shared
even though its declaration does not say shared. The same four-way table
applies to those effective field types, including nested projections.
SharedPlace origins
A share also satisfies shared, even though it is borrowed rather than owned.
For example, with d1: shared[source1] Data and d2: shared[source2] Data, a value
x: given[d1, d2] Data can be given twice. Here d1 and d2 are the
possible origins; source1 and source2 are the referents those origins borrow.
| Types of the two origins | Duplicate? |
|---|---|
shared[source1] Data, shared[source2] Data | Yes |
shared[source1] Data, shared Data (either order) | Yes |
shared[source1] Data, given Data (either order) | No |
shared[source1] Data, ![source2] Data (either order) | No |
These cases also work with projected origins, both when a reference is stored
in a field of a unique container and when a field is accessed through a borrowed
container. The distinction matters: the origin may be d1.field, while the
reference dependency leads to a separate source1.
The separate given_from_preserves_origin_dependencies property documents
the borrowing restrictions retained by surviving duplicates.
Candidate lemma
Let C be an ordinary non-generic class that is not itself shared. In a
well-formed environment, for a nonempty list of valid places p1, ..., pn,
proving given[p1, ..., pn] C is shared requires proving that the type
of every pi satisfies shared. In particular, one uniquely owned C
alternative prevents duplication, regardless of its position in the list.
This is a candidate formulation, not a proved theorem. The tests exercise two
origins of an empty ordinary class, using concrete given, shared, share, and mut
permissions. They cover both mixed orders, both uniform cases, and initialized
locals as well as parameters with alternative origins. Field and nested-field
matrices cover declared field permissions and permissions inherited from the
container. Each matrix case first verifies that giving once is permitted,
then checks whether giving twice succeeds or fails specifically at the give.
Scope
This property concerns duplication of given values, not every predicate
or every permission constructor. shared is the predicate for duplicability;
it does not require full ownership. The tests cover owned and borrowed shared origins.
Types such as Int are independently duplicable and are outside the class
assumption above. Mutation through alternative origins is a separate property.
How they relate
These three form a subtyping chain:
shared <: shared[d] <: shared ![d]
Each step adds more restrictions while remaining shared.
shared <: shared[d]
An independently shared value can stand in wherever sharing from d is expected.
Giving an owned shared copy is safe –
they get what they need (read access),
and the extra restriction on d
(not modifying it while the shared result is live)
is harmlessly conservative:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) {
let s: shared Data = new Data().share;
let r: shared[d] Data = s→;
();
}
}
"#
);
The value s has type shared Data.
The target r expects shared[d] Data.
Since shared <: shared[d], this works.
shared[d] is NOT <: shared
The reverse doesn’t hold – a place dependency cannot become independent ownership:
crate::assert_err!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) {
let r: shared[d] Data = d.share;
let s: shared Data = r→;
();
}
}
"#,
expect_test::expect!["judgment had no applicable rules: `check_program { program: struct Data { } struct Main { fn test (given self d : given Data) → () { let r : shared [d] Data = d . share ; let s : shared Data = r → ; () ; } } }`"]
);
shared[d] </: shared –
the shared value depends on d being available.
A shared value makes no such assumption.
If we allowed this,
the “shared” value could outlive d.
shared <: shared ![d]
A shared value can also stand in for a shared lease.
The shared lease restricts d;
a shared value doesn’t need d at all,
so the restriction is harmlessly extra:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) {
let s: shared Data = new Data().share;
let r: shared ![d] Data = s→;
();
}
}
"#
);
shared[d] <: shared ![d]
Sharing from a place can stand in for a shared lease from the same place:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) {
let r: shared[d] Data = d.share;
let sm: shared ![d] Data = r→;
();
}
}
"#
);
Both shared[d] and shared ![d] are shared
and both restrict d.
The difference is what they say about the object –
shared[d] grants read access to the object,
while shared ![d] allows the possibility
that another ![d] holder could mutate the object.
Since sharing the place provides a stronger guarantee,
it’s a subtype.
The chain comparison rule for this is:
(if place_b.is_prefix_of(place_a))
(red_chain_sub_chain(env, tail_a, tail_b) => ())
--- ("(shared[place]::P) vs (shared[]::mut::P)")
(red_chain_sub_chain(
env,
Head(RedLink::ShareLive(place_a) | RedLink::ShareDead(place_a), Tail(tail_a)),
Head(RedLink::Shared, Head(RedLink::Mtl(place_b) | RedLink::Mtd(place_b), Tail(tail_b))),
) => ())
shared ![d] is NOT <: shared[d]
The reverse fails:
crate::assert_err!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) {
let p: ![d] Data = d!;
let sm: shared ![d] Data = p.share;
let r: shared[d] Data = sm→;
();
}
}
"#,
expect_test::expect!["judgment had no applicable rules: `check_program { program: struct Data { } struct Main { fn test (given self d : given Data) → () { let p : ! [d] Data = d ! ; let sm : shared ! [d] Data = p . share ; let r : shared [d] Data = sm → ; () ; } } }`"]
);
shared ![d] </: shared[d] –
a shared lease can coexist with mutation of the object,
while direct sharing from the place cannot.
Treating a shared lease as direct sharing
would falsely promise immutability.
How composition works
Permissions compose with Perm::Apply –
written as P Q in the grammar,
meaning “apply permission P to something with permission Q.”
The result depends on whether the inner permission is shared.
Shared permissions absorb: shared[p] shared == shared
When you share a place containing independently shared data, the place dependency is redundant:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self) {
let d: shared Data = new Data().share;
let r = d.share;
let s: shared Data = r→;
();
}
}
"#
);
The expression d.share has type shared[d] shared Data.
But d has type shared Data,
so the composed permission shared[d] shared
reduces to just shared –
the result remains independently shared.
Internally, this is the append_chain rule:
when the right-hand side of a composition is shared,
the left-hand side is discarded.
The inner shared permission determines the resulting access.
Non-shared composes: shared[p] ![d]
When the inner permission is not shared, composition creates a genuine chain. Sharing a place containing a lease retains the lease dependency:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self) {
let d: given Data = new Data();
let p: ![d] Data = d!;
let q: shared[p] ![d] Data = p.share;
();
}
}
"#
);
Here p.share creates shared[p] ![d] Data –
a chain of two links.
The permission records that you shared the place p,
which itself was leased from d.
What happens when you want to use this value
depends on whether p is still alive –
the Liveness and cancellation chapter
explains how dead links are resolved during comparison.
![d] is not shared
A mutable lease ![d] is not shared –
it provides exclusive mutable access,
which can’t be duplicated:
crate::assert_err!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) {
let p: ![d] Data = d!;
let q: shared[d] Data = p→;
();
}
}
"#,
expect_test::expect!["judgment had no applicable rules: `check_program { program: struct Data { } struct Main { fn test (given self d : given Data) → () { let p : ! [d] Data = d ! ; let q : shared [d] Data = p → ; () ; } } }`"]
);
![d] </: shared[d] –
a lease grants exclusive mutation rights,
while sharing the place only grants read access.
These are incomparable: neither is a subtype of the other.
Similarly, given (unique ownership) is not comparable
to any of the shared permissions:
crate::assert_err!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) {
let s: shared Data = d→;
();
}
}
"#,
expect_test::expect!["judgment had no applicable rules: `check_program { program: struct Data { } struct Main { fn test (given self d : given Data) → () { let s : shared Data = d → ; () ; } } }`"]
);
given </: shared –
unique ownership and shared ownership
represent fundamentally different memory models.
The full permission landscape
Here’s how all the permissions relate:
| Sub | Super | Holds? | Why |
|---|---|---|---|
given | given | Yes | Same permission |
shared | shared | Yes | Same permission |
given | shared | No | Can’t pretend unique is shared |
shared | given | No | Can’t pretend shared is unique |
shared | shared[d] | Yes | Independent ownership satisfies a place dependency |
shared[d] | shared | No | A place dependency cannot become ownership |
shared[d1] | shared[d1, d2] | Yes | Fewer sources = more specific |
shared[d1, d2] | shared[d1] | No | Can’t drop a possible origin |
shared[d] | shared ![d] | Yes | Sharing the place is stronger than sharing a lease |
shared ![d] | shared[d] | No | Shared lease doesn’t guarantee immutability |
The shared permissions (shared, shared[d], shared ![d])
form a chain within this landscape.
The non-shared permissions (given, ![d]) are incomparable
with the shared permissions.
Summary
The shared permissions form a hierarchy:
| Permission | Copy? | Owned? | Restricts environment? |
|---|---|---|---|
shared | yes | yes | no |
shared[d] | yes | no | d cannot be modified |
shared ![d] | yes | no | d cannot be modified |
Subtyping: shared <: shared[d] <: shared ![d].
Composition: applying a permission to something shared just gives you the shared permission back. Applying a permission to something non-shared creates a genuine chain that requires further analysis to resolve.
The non-shared permissions (given, ![d])
sit outside this hierarchy –
they are incomparable with the shared permissions.
Liveness and cancellation
In the previous sub-chapters, we saw how permissions are compared structurally – place ordering and the copy permission hierarchy. But those rules assume all origin places are still live.
What happens when an origin place is dead – no longer used by later code?
Dead links in a RedChain can be cancelled or promoted,
which enables subtyping relationships
that wouldn’t hold for live links.
This is Dada’s equivalent of Rust’s non-lexical lifetimes (NLL) –
access constraints can end at the last use,
not when it goes out of scope.
A motivating example: re-borrowing
Consider a function that re-borrows a lease:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self) {
let d = new Data();
let p: ![d] Data = d!;
let q: ![p] Data = p!;
let r: ![d] Data = q→;
();
}
}
"#
);
Here’s what happens step by step:
dis created with typegiven Datap: ![d] Data– a mutable lease ofdq: ![p] Data– a mutable lease ofp(a re-borrow)r: ![d] Data– we wantq→to have type![d] Data
The expression q→ has type ![p] Data.
But r expects ![d] Data.
How can ![p] ![d] become ![d]?
When we reduce ![p], the permission for q→,
we get the chain [Mtd(p)] –
p is dead because q→ is the last expression,
and p is never used again.
Chain expansion follows p’s type (![d] Data),
appending Mtl(d) to get [Mtd(p), Mtl(d)].
The target ![d] reduces to [Mtl(d)].
Comparing [Mtd(p), Mtl(d)] vs [Mtl(d)]:
the cancellation rule fires –
since p is dead, the Mtd(p) link is dropped,
and comparison continues with the tail [Mtl(d)] vs [Mtl(d)],
which succeeds.
But not when the place is live
If p is still used after the assignment, cancellation is blocked:
crate::assert_err!(
r#"
struct Data {
fn read[perm P](P self) { (); }
}
struct Main {
fn test(given self) {
let d = new Data();
let p: ![d] Data = d!;
let q: ![p] Data = p!;
let r: ![d] Data = q→;
p→.read[![d]]();
}
}
"#,
expect_test::expect![[r#"
the rule "(mut::P) vs (mut::P)" at (redperms.rs) failed because
condition evaluted to false: `place_b.is_prefix_of(place_a)`
place_b = d
place_a = p"#]]
);
Here p appears in p→.read[...]() after q→,
so p is live at the point where q→ is evaluated.
The chain becomes [Mtl(p), Mtl(d)] (live, not dead) –
and there is no rule to cancel a live Mtl link.
The assignment to r: ![d] Data fails.
The two cancellation operations
Dead links are resolved by two rules in red_chain_sub_chain:
Cancellation: dropping a dead mut link
(let ty_dead = env.place_ty(place_dead)?)
(prove_is_struct(env, ty_dead) => ())
(prove_is_mut(env, tail_a) => ())
(red_chain_sub_chain(env, tail_a, red_chain_b) => ())
--- ("(mut-dead::P) vs Q ~~> (P) vs Q")
(red_chain_sub_chain(env, Head(RedLink::Mtd(place_dead), Tail(tail_a)), red_chain_b) => ())
When the chain starts with Mtd(place) (a dead mutable lease),
the rule drops it and continues comparing the tail against the target.
Three conditions must hold:
- The place must be dead (encoded by the
Mtdvariant) - The type of the dead place must be shareable –
prove_is_struct(env.place_ty(place_dead)) - The tail must be mut-based –
prove_is_mut(tail_a)
The shareable check ensures it’s safe to silently release the lease. The tail check ensures we’re cancelling a lien on top of another lease, not an owned permission.
Promotion: resolving a dead sharing origin
(let ty_dead = env.place_ty(place_dead)?)
(prove_is_struct(env, ty_dead) => ())
(prove_is_mut(env, tail_a) => ())
(red_chain_sub_chain(env, Head(RedLink::Shared, Tail(tail_a)), red_chain_b) => ())
--- ("(shared-dead[place]::P) vs Q ~~> (shared[]::P) vs Q")
(red_chain_sub_chain(env, Head(RedLink::ShareDead(place_dead), Tail(tail_a)), red_chain_b) => ())
When the chain starts with ShareDead(place) (sharing from a dead place),
the rule replaces it with Shared
and continues comparing.
As with mutable cancellation, the dead place’s type must be shareable and the tail must be mut-based. Promotion removes the dependency on this intermediate place while retaining the mutable lease in the tail. It does not turn sharing from an owned place into independent ownership.
Here’s an example of promotion in action:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self) {
let d = new Data();
let p: ![d] Data = d!;
let q: shared[p] Data = p.share;
let r: shared ![d] Data = q→;
();
}
}
"#
);
The expression q→ has type shared[p] ![d] Data.
The target r expects shared ![d] Data.
Since p is dead, the chain [ShareDead(p), Mtl(d)]
promotes ShareDead(p) to Shared,
giving [Shared, Mtl(d)] which matches shared ![d].
If p were still live, promotion wouldn’t happen:
crate::assert_err!(
r#"
struct Data {
fn read[perm P](P self) { (); }
}
struct Main {
fn test(given self) {
let d = new Data();
let p: ![d] Data = d!;
let q: shared[p] Data = p.share;
let r: shared ![d] Data = q→;
p→.read[![d]]();
}
}
"#,
expect_test::expect![[r#"
the rule "(shared[place]::P) vs (shared[]::mut::P)" at (redperms.rs) failed because
condition evaluted to false: `place_b.is_prefix_of(place_a)`
place_b = d
place_a = p"#]]
);
With p live, the chain is [ShareLive(p), Mtl(d)] –
the ShareLive variant has no promotion rule,
and the comparison fails.
A practical pattern: re-borrowing in functions
Liveness-based cancellation enables a common pattern – re-borrowing inside a function and returning the result:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn reborrow(given self, d: ![self] Data) → ![self] Data {
let p: ![d] Data = d!;
p→;
}
}
"#
);
The parameter d: ![self] Data is a mutable lease from self.
Inside the function, d! creates ![d] Data –
a re-borrow. When we return p→,
its type is ![d] Data.
The return type expects ![self] Data.
Since d is dead at the return point
(it’s a parameter that’s not used after p→),
the Mtd(d) link cancels,
and the chain collapses to ![self].
Without liveness-based cancellation, re-borrowing would be useless – you could never return a value that was transiently borrowed through a local.
What cancellation cannot do
Not all dead links can be resolved. There are important limits on when cancellation and promotion apply.
Shared-to-leased conversion is blocked
Cancellation can resolve links within a permission chain, but it cannot change the nature of a permission from shared (copy) to leased (exclusive):
crate::assert_err!(
r#"
struct Data { }
struct Main {
fn test(given self) {
let d = new Data();
let p: ![d] Data = d!;
let q: shared[p] ![d] Data = p.share;
let r: ![d] Data = q→;
();
}
}
"#,
expect_test::expect!["judgment had no applicable rules: `check_program { program: struct Data { } struct Main { fn test (given self) → () { let d = new Data () ; let p : ! [d] Data = d ! ; let q : shared [p] ! [d] Data = p . share ; let r : ! [d] Data = q → ; () ; } } }`"]
);
The expression q→ has type shared[p] ![d] Data.
Even though p is dead,
the chain [ShareDead(p), Mtl(d)] cannot become [Mtl(d)].
Why? Promotion converts ShareDead(p) to Shared,
giving [Shared, Mtl(d)] – a shared lease.
But ![d] reduces to [Mtl(d)] – an exclusive lease.
shared ![d] is not a subtype of ![d].
This reflects a real safety invariant: sharing from a place (even one that is now dead) permits duplication – multiple copies may exist. You can’t recover exclusive access from something that was shared.
Multi-place permissions: all places must be dead
When a permission mentions multiple places,
like shared[p, q], reduction produces one chain per place.
For cancellation to resolve all of them,
every place must be dead:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self) {
let d = new Data();
let p: shared[d] Data = d.share;
let q: shared[d] Data = d.share;
let r: shared[p, q] shared[d] Data = p.share;
let s: shared[d] Data = r→;
();
}
}
"#
);
Both p and q are dead at the point of r→,
so both ShareDead(p) and ShareDead(q) chains can be resolved.
But if even one place is still live:
crate::assert_err!(
r#"
struct Data { }
struct Main {
fn test(given self) {
let d = new Data();
let p: shared[d] Data = d.share;
let q: shared[d] Data = d.share;
let r: shared[p, q] shared[d] Data = p.share;
let s: shared[d] Data = r→;
q→;
}
}
"#,
expect_test::expect!["judgment had no applicable rules: `check_program { program: struct Data { } struct Main { fn test (given self) → () { let d = new Data () ; let p : shared [d] Data = d . share ; let q : shared [d] Data = d . share ; let r : shared [p, q] shared [d] Data = p . share ; let s : shared [d] Data = r → ; q → ; } } }`"]
);
Here q is used after r→ (in q→),
so q is live at the point where r→ is evaluated.
The chain ShareLive(q) (live, not dead) has no cancellation rule,
and the comparison fails –
even though p is dead and its chain could be resolved.
How liveness is computed
Liveness is computed backwards through the program. Starting from the end of the function body (where nothing is live), the analysis walks statements in reverse, tracking which places are accessed or traversed.
A place is live if:
- It or any overlapping place is accessed later, or
- It is a prefix of a place that gets assigned to later
A place is dead if it is not live – no future code reads from it or any of its sub-places.
This backward analysis means liveness depends on what comes after a given point in the program. The same variable can be live at one point and dead at another.
The type system threads LivePlaces through the checking process:
when sub_perms is called, it receives the set of places
that are live after the current expression.
This is what determines whether a shared[d] or ![d]
reduces to the live variant (ShareLive/Mtl)
or the dead variant (ShareDead/Mtd).
Summary
| Operation | Applies to | Result | Conditions |
|---|---|---|---|
| Cancellation | Mtd(place) | Drop the link | Place dead, type shareable, tail is mut |
| Promotion | ShareDead(place) | Replace with Shared | Place dead, type shareable, tail is mut |
Key constraints:
- Only dead links can be cancelled or promoted
- The dead place’s type must be shareable
- The tail of the chain must be mut-based
- Shared-to-leased conversion is never possible
- Multi-place permissions require all places to be dead
- Liveness is computed backwards from end of function
Running a program
The previous chapters showed how the type checker verifies a program.
The interpreter evaluates the resulting core program, producing a value and a
memory snapshot. Program assertions parse surface syntax and lower it to core
before interpretation. assert_interpret! also checks the program;
assert_interpret_only! deliberately skips the checker for runtime tests.
Here is a program that creates a Point and returns it:
crate::assert_interpret!(
r#"
struct Point {
x: Int;
y: Int;
}
struct Main {
fn main(given self) → Point {
let p = new Point(22, 44);
p→;
}
}
"#,
expect_test::expect![[r#"
Output: Trace: enter Main.main
Output: Trace: let _1_p = new Point (22, 44) ;
Output: Trace: _1_p = Point { x: 22, y: 44 }
Output: Trace: _1_p → ;
Output: Trace: exit Main.main => Point { x: 22, y: 44 }
Result: Ok: Point { x: 22, y: 44 }
Alloc 0x06: [Int(22), Int(44)]"#]]
);
The interpreter creates a Main() instance and calls its main method.
The result is Point { x: 22, y: 44 }.
The memory model
Memory is a collection of flat allocations. Each allocation contains words, without type tags or named field maps:
/// A flat array of words representing a value in memory.
#[derive(Debug, Clone, PartialEq, Eq)]
struct Alloc {
data: Vec<Word>,
}
Words represent scalar values, flags, pointers, mutable leases, array metadata, or uninitialized storage:
/// A single word of memory.
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
enum Word {
Int(i64),
Flags(Flags),
Pointer(Pointer),
Lease(Pointer),
RefCount(i64),
Capacity(usize),
Uninitialized,
}
The flags on a boxed handle record its runtime ownership:
/// Permission flag for unique objects.
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
enum Flags {
/// Indicates that the data here is fully owned.
Given,
/// Indicates that the data here has shared ownership.
SharedOwned,
/// Indicates that the data here is a borrowed reference.
SharedPlace,
}
Given: the handle owns its data uniquely.SharedOwned: the handle participates in shared ownership.SharedPlace: the handle shares data owned elsewhere, without owning it.
An uninitialized slot is a Word::Uninitialized, not a flag variant.
A pointer identifies an allocation and an offset within it:
/// Identifies a position within an allocation.
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
struct Pointer {
index: usize,
offset: usize,
}
Object layout
Inline objects contain only their fields. For example, a Point with two
integer fields occupies two words, regardless of its declaration category:
Point value:
+-------------------+
| Int(22) | <- x
| Int(44) | <- y
+-------------------+
There is no per-object flags word for inline classes and structs. Boxed types such as
Array[T] instead have a two-word wrapper [Flags, Pointer], whose pointer
leads to a separate heap allocation. A mutable lease uses a single
Lease(Pointer) word to reach its origin’s data.
An Int or Bool is one word. Unit () has no words. Nested inline fields are
laid out consecutively; a field’s type determines its size.
Types flow through evaluation, not memory
An ObjectValue pairs a pointer with the type needed to interpret its words:
/// A pointer paired with the type needed to interpret the words.
/// For boxed types (e.g., arrays, leases), this will be a pointer to a pointer.
/// For inline objects, this will be a pointer to the object data.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ObjectValue {
pointer: Pointer,
ty: Ty,
}
The stack frame maps variables to these typed values:
pub struct StackFrame {
env: Env,
variables: Vec<(Var, Pointer)>,
}
When traversing a place, the interpreter combines the static type with any boxed flags and mutable lease indirections encountered along the path. The resulting effective permissions determine whether access moves, duplicates, or mutably borrows the data.
The interpreter and stack frames
The interpreter holds the program, a typing environment used to classify types, and the allocations:
pub struct Interpreter<'a> {
program: &'a Program,
allocs: Vec<Alloc>,
output: String,
indent: usize,
/// Monotonically increasing counter for alpha-renaming method bodies.
/// Each method invocation gets a unique ID so renamed variables
/// (e.g., `_1_self`, `_2_self`) never collide, even across sequential
/// calls at the same stack depth.
next_call_id: usize,
}
Each method call creates a new StackFrame, evaluates the body, and cleans up
its locals and temporaries when returning.
Walking through evaluation
Main in the example has no fields, so its inline value occupies zero words.
Evaluating new Point(22, 44) first creates integer arguments and then builds
the flat object [Int(22), Int(44)]. Field x begins at offset zero and field
y at offset one.
p→ gives the object. For a uniquely owned value, the interpreter copies the
words into result storage and uninitializes the source. Returning transfers
the result out of the callee’s frame. The test snapshot retains only the final
Point allocation; it does not expose temporary storage as part of the result.
Arithmetic
The interpreter supports integer arithmetic:
crate::assert_interpret!(
r#"
struct Main {
fn main(given self) → Int {
let x = 10;
let y = 20;
x→ + y→;
}
}
"#,
expect_test::expect![[r#"
Output: Trace: enter Main.main
Output: Trace: let _1_x = 10 ;
Output: Trace: _1_x = 10
Output: Trace: let _1_y = 20 ;
Output: Trace: _1_y = 20
Output: Trace: _1_x → + _1_y → ;
Output: Trace: exit Main.main => 30
Result: Ok: 30
Alloc 0x08: [Int(30)]"#]]
);
Method calls
The receiver’s type determines which method to call. The interpreter evaluates the receiver and arguments, creates the callee’s frame, and evaluates its body:
crate::assert_interpret!(
r#"
struct Adder {
a: Int;
b: Int;
fn sum(given self) → Int {
self.a→ + self.b→;
}
}
struct Main {
fn main(given self) → Int {
let adder = new Adder(3, 4);
adder→.sum();
}
}
"#,
expect_test::expect![[r#"
Output: Trace: enter Main.main
Output: Trace: let _1_adder = new Adder (3, 4) ;
Output: Trace: _1_adder = Adder { a: 3, b: 4 }
Output: Trace: _1_adder → . sum () ;
Output: Trace: enter Adder.sum
Output: Trace: _2_self . a → + _2_self . b → ;
Output: Trace: exit Adder.sum => 7
Output: Trace: exit Main.main => 7
Result: Ok: 7
Alloc 0x0a: [Int(7)]"#]]
);
For adder→.sum(), adder→ is evaluated first. Its value becomes self in the
new frame. Generic arguments are supplied explicitly in the core call.
Place and value operations at runtime
The checker verifies that accesses are permitted. The interpreter executes those operations using effective permissions. Accessing uninitialized storage faults, allowing runtime tests to expose errors that the checker should reject.
Giving a place
place→ copies the value’s words into result storage. Its effective permissions
determine what happens to ownership:
| Permission | Behavior |
|---|---|
| Unique ownership | Transfer ownership and uninitialize the source |
| Independent shared ownership | Duplicate; increment refcounts of owning boxed handles |
| Sharing from a place | Duplicate without gaining ownership of the origin |
| Mutable lease | Preserve mutable access through a lease indirection |
Giving uniquely owned data transfers it:
crate::assert_interpret!(
r#"
struct Data { x: Int; }
struct Main {
fn main(given self) → Data {
let d = new Data(42);
d→;
}
}
"#,
expect_test::expect![[r#"
Output: Trace: enter Main.main
Output: Trace: let _1_d = new Data (42) ;
Output: Trace: _1_d = Data { x: 42 }
Output: Trace: _1_d → ;
Output: Trace: exit Main.main => Data { x: 42 }
Result: Ok: Data { x: 42 }
Alloc 0x05: [Int(42)]"#]]
);
Giving independently shared data can be repeated:
crate::assert_interpret_only!(
r#"
struct Data { x: Int; }
struct Main {
fn main(given self) → Data {
let d = new Data(42);
let s = d→.share;
let x1 = s→;
let x2 = s→;
print(x1→);
x2→;
}
}
"#,
expect_test::expect![[r#"
Output: Trace: enter Main.main
Output: Trace: let _1_d = new Data (42) ;
Output: Trace: _1_d = Data { x: 42 }
Output: Trace: let _1_s = _1_d → . share ;
Output: Trace: _1_s = shared Data { x: 42 }
Output: Trace: let _1_x1 = _1_s → ;
Output: Trace: _1_x1 = shared Data { x: 42 }
Output: Trace: let _1_x2 = _1_s → ;
Output: Trace: _1_x2 = shared Data { x: 42 }
Output: Trace: print(_1_x1 →) ;
Output: -----> shared Data { x: 42 }
Output: Trace: _1_x2 → ;
Output: Trace: exit Main.main => shared Data { x: 42 }
Result: Ok: shared Data { x: 42 }
Alloc 0x0d: [Int(42)]"#]]
);
Sharing a place
place and place.share make the same shared access. The source stays intact.
For boxed handles in the copied result, the flags determine ownership accounting:
| Source flags | Result |
|---|---|
Given | SharedPlace; no ownership transfer or refcount increment |
SharedOwned | SharedOwned; increment the refcount |
SharedPlace | SharedPlace; no refcount increment |
Sharing a uniquely owned place leaves the original usable:
crate::assert_interpret!(
r#"
struct Data { x: Int; }
struct Main {
fn main(given self) → Data {
let d = new Data(42);
print(d.share);
d→;
}
}
"#,
expect_test::expect![[r#"
Output: Trace: enter Main.main
Output: Trace: let _1_d = new Data (42) ;
Output: Trace: _1_d = Data { x: 42 }
Output: Trace: print(_1_d . share) ;
Output: -----> shared [_1_d] Data { x: 42 }
Output: Trace: _1_d → ;
Output: Trace: exit Main.main => Data { x: 42 }
Result: Ok: Data { x: 42 }
Alloc 0x07: [Int(42)]"#]]
);
Sharing a place containing independently shared data retains that ownership:
crate::assert_interpret_only!(
r#"
struct Data { x: Int; }
struct Main {
fn main(given self) → Data {
let d = new Data(42);
let s = d→.share;
s.share;
}
}
"#,
expect_test::expect![[r#"
Output: Trace: enter Main.main
Output: Trace: let _1_d = new Data (42) ;
Output: Trace: _1_d = Data { x: 42 }
Output: Trace: let _1_s = _1_d → . share ;
Output: Trace: _1_s = shared Data { x: 42 }
Output: Trace: _1_s . share ;
Output: Trace: exit Main.main => shared Data { x: 42 }
Result: Ok: shared Data { x: 42 }
Alloc 0x07: [Int(42)]"#]]
);
For inline data, the interpreter copies the fields. The result type carries the shared permission; nested boxed fields receive the ownership treatment shown above.
Sharing a value
expr.share, when the operand is a value expression, shares the evaluated
value. To give an existing place’s value and share it independently, write
d→.share. Bare d.share instead shares the place.
The value operation applies shared[] to the result type and changes owned
boxed handles from Given to SharedOwned. It does not create a second handle,
so it does not increment refcounts. Already shared handles need no conversion.
Sharing does not invent ownership of data reached through SharedPlace or a
mutable lease; dependencies in the inner type remain relevant.
The operation visits nested fields:
crate::assert_interpret_only!(
r#"
struct Inner { x: Int; }
struct Outer { inner: Inner; }
struct Main {
fn main(given self) → Outer {
let o = new Outer(new Inner(1));
o→.share;
}
}
"#,
expect_test::expect![[r#"
Output: Trace: enter Main.main
Output: Trace: let _1_o = new Outer (new Inner (1)) ;
Output: Trace: _1_o = Outer { inner: Inner { x: 1 } }
Output: Trace: _1_o → . share ;
Output: Trace: exit Main.main => shared Outer { inner: Inner { x: 1 } }
Result: Ok: shared Outer { inner: Inner { x: 1 } }
Alloc 0x06: [Int(1)]"#]]
);
Inline fields have no flags to flip. Their permissions follow the result type; owned boxed fields encountered during traversal are converted to shared ownership.
Dropping a place
Dropping releases any ownership held at a place:
| Effective permission | Behavior |
|---|---|
| Unique ownership | Run cleanup, drop owned fields, and uninitialize |
| Independent shared ownership | Release owning handles, decrementing refcounts |
| Sharing from a place or a mutable lease | Leave the origin’s data intact |
Dropping a place-dependent shared view does not drop its origin:
crate::assert_interpret!(
r#"
struct Data { x: Int; }
struct Main {
fn main(given self) → () {
let d = new Data(42);
let r = d.share;
drop r;
print(r→);
();
}
}
"#,
expect_test::expect![[r#"
Output: Trace: enter Main.main
Output: Trace: let _1_d = new Data (42) ;
Output: Trace: _1_d = Data { x: 42 }
Output: Trace: let _1_r = _1_d . share ;
Output: Trace: _1_r = shared [_1_d] Data { x: 42 }
Output: Trace: drop _1_r ;
Output: Trace: print(_1_r →) ;
Output: -----> shared [_1_d] Data { x: 42 }
Output: Trace: () ;
Output: Trace: exit Main.main => ()
Result: Ok: ()"#]]
);
The example also records the model’s current behavior for explicitly dropping such a view: this place operation is a no-op, so the view can still be used. Frame cleanup separately clears temporary storage.
Mutably borrowing a place
place! creates a Lease(Pointer) word pointing at the place’s data. Its type
records ![place]. Traversing the lease grants mutable access to that data;
shared effective permissions reject mutable access. Dropping the lease does
not drop the origin’s value.
Conditionals
The if expression evaluates a condition and selects a branch. Since it
returns unit, these examples communicate a result through assignment:
crate::assert_interpret!(
r#"
struct Main {
fn main(given self) → Int {
let result = 0;
if true { result = 42; } else { result = 0; };
result→;
}
}
"#,
expect_test::expect![[r#"
Output: Trace: enter Main.main
Output: Trace: let _1_result = 0 ;
Output: Trace: _1_result = 0
Output: Trace: if true { _1_result = 42 ; } else { _1_result = 0 ; } ;
Output: Trace: _1_result = 42 ;
Output: Trace: _1_result = 42
Output: Trace: _1_result → ;
Output: Trace: exit Main.main => 42
Result: Ok: 42
Alloc 0x08: [Int(42)]"#]]
);
crate::assert_interpret!(
r#"
struct Main {
fn main(given self) → Int {
let result = 0;
if false { result = 42; } else { result = 99; };
result→;
}
}
"#,
expect_test::expect![[r#"
Output: Trace: enter Main.main
Output: Trace: let _1_result = 0 ;
Output: Trace: _1_result = 0
Output: Trace: if false { _1_result = 42 ; } else { _1_result = 99 ; } ;
Output: Trace: _1_result = 99 ;
Output: Trace: _1_result = 99
Output: Trace: _1_result → ;
Output: Trace: exit Main.main => 99
Result: Ok: 99
Alloc 0x08: [Int(99)]"#]]
);
Arrays
Array[T] is the model’s heap-allocation primitive. Its two-word wrapper points
to a refcounted backing allocation:
Array[T] wrapper:
+-------------------+
| Flags(Given) |
| Pointer(alloc) |
+-------------------+
Backing allocation:
+-------------------+
| RefCount(1) |
| Capacity(n) |
| element 0 words |
| element 1 words |
| ... |
+-------------------+
Each element occupies size_of(T) words. An inline Data { x: Int } element
occupies one integer word, just like Int; an element that is itself boxed has
its own flags and pointer wrapper. Element types come from the array’s type,
not from tags stored in the backing allocation.
Creating and accessing arrays
The built-in operations are:
array_new[T](n)allocates capacity forninitially uninitialized elements.array_write[T, P](a, i, v)writes an element through mutable permissionP.array_give[T, P, Q](a, i)gives an element with permissionPthrough array permissionQ.array_drop[T, P, Q](a, from, to)drops a range of elements through array permissionQ, with element permissionP.array_capacity[T, P](a)returns the capacity through array permissionP.
The program supplies the generic arguments explicitly. For example,
array_write[Int, ![a]](a!, 0, 10) writes through a mutable lease of a.
crate::assert_interpret_only!(
r#"
struct Main {
fn main(given self) → Int {
let a = array_new[Int](3);
array_write[Int, ![a]](a!, 0, 10);
array_write[Int, ![a]](a!, 1, 20);
array_write[Int, ![a]](a!, 2, 30);
print(array_give[Int, given, shared[a]](a.share, 0));
print(array_give[Int, given, shared[a]](a.share, 1));
array_give[Int, given, given](a→, 2);
}
}
"#,
expect_test::expect ;
Output: Trace: _1_a = Array { flag: Given, rc: 1, ⚡, ⚡, ⚡ }
Output: Trace: array_write [Int, ! [_1_a]](_1_a ! , 0 , 10) ;
Output: Trace: array_write [Int, ! [_1_a]](_1_a ! , 1 , 20) ;
Output: Trace: array_write [Int, ! [_1_a]](_1_a ! , 2 , 30) ;
Output: Trace: print(array_give [Int, given, shared [_1_a]](_1_a . share , 0)) ;
Output: -----> 10
Output: Trace: print(array_give [Int, given, shared [_1_a]](_1_a . share , 1)) ;
Output: -----> 20
Output: Trace: array_give [Int, given, given](_1_a → , 2) ;
Output: Trace: exit Main.main => 30
Result: Ok: 30
Alloc 0x1c: [Int(30)]"#]]
);
Duplicating or moving elements
Giving an Int element duplicates its value:
crate::assert_interpret_only!(
r#"
struct Main {
fn main(given self) → Int {
let a = array_new[Int](1);
array_write[Int, ![a]](a!, 0, 42);
let x = array_give[Int, given, shared[a]](a.share, 0);
let y = array_give[Int, given, shared[a]](a.share, 0);
print(x→);
y→;
}
}
"#,
expect_test::expect ;
Output: Trace: _1_a = Array { flag: Given, rc: 1, ⚡ }
Output: Trace: array_write [Int, ! [_1_a]](_1_a ! , 0 , 42) ;
Output: Trace: let _1_x = array_give [Int, given, shared [_1_a]](_1_a . share , 0) ;
Output: Trace: _1_x = 42
Output: Trace: let _1_y = array_give [Int, given, shared [_1_a]](_1_a . share , 0) ;
Output: Trace: _1_y = 42
Output: Trace: print(_1_x →) ;
Output: -----> 42
Output: Trace: _1_y → ;
Output: Trace: exit Main.main => 42
Result: Ok: 42
Alloc 0x14: [Int(42)]"#]]
);
The array’s effective permissions propagate to element accesses. Access through
an independently shared array duplicates elements and accounts for any nested
owning boxed handles, even if a nested handle’s stored flag is Given:
// Shared array: class elements are accessed with shared semantics —
// giving an element produces a shared copy, element remains available.
crate::assert_interpret_only!(
r#"
struct Data { x: Int; }
struct Main {
fn main(given self) → Data {
let a = array_new[Data](1);
array_write[Data, ![a]](a!, 0, new Data(42));
let s = a→.share;
let x = array_give[Data, shared, shared[s]](s.share, 0);
print(x→);
// Element still available — shared, no move.
array_give[Data, shared, shared](s→, 0);
}
}
"#,
expect_test::expect ;
Output: Trace: _1_a = Array { flag: Given, rc: 1, Data { x: ⚡ } }
Output: Trace: array_write [Data, ! [_1_a]](_1_a ! , 0 , new Data (42)) ;
Output: Trace: let _1_s = _1_a → . share ;
Output: Trace: _1_s = shared Array { flag: SharedOwned, rc: 1, Data { x: 42 } }
Output: Trace: let _1_x = array_give [Data, shared, shared [_1_s]](_1_s . share , 0) ;
Output: Trace: _1_x = shared Data { x: 42 }
Output: Trace: print(_1_x →) ;
Output: -----> shared Data { x: 42 }
Output: Trace: array_give [Data, shared, shared](_1_s → , 0) ;
Output: Trace: exit Main.main => shared Data { x: 42 }
Result: Ok: shared Data { x: 42 }
Alloc 0x15: [Int(42)]"#]]
);
This is the same permission propagation used for fields. Inline struct elements can be duplicated repeatedly through shared access:
crate::assert_interpret_only!(
r#"
struct Data { x: Int; }
struct Main {
fn main(given self) → Data {
let a = array_new[Data](2);
array_write[Data, ![a]](a!, 0, new Data(42));
array_write[Data, ![a]](a!, 1, new Data(99));
print(array_give[Data, given, shared[a]](a.share, 0));
array_give[Data, given, given](a→, 1);
}
}
"#,
expect_test::expect ;
Output: Trace: _1_a = Array { flag: Given, rc: 1, Data { x: ⚡ }, Data { x: ⚡ } }
Output: Trace: array_write [Data, ! [_1_a]](_1_a ! , 0 , new Data (42)) ;
Output: Trace: array_write [Data, ! [_1_a]](_1_a ! , 1 , new Data (99)) ;
Output: Trace: print(array_give [Data, given, shared [_1_a]](_1_a . share , 0)) ;
Output: -----> Data { x: 42 }
Output: Trace: array_give [Data, given, given](_1_a → , 1) ;
Output: Trace: exit Main.main => Data { x: 99 }
Result: Ok: Data { x: 99 }
Alloc 0x16: [Int(99)]"#]]
);
Sharing and reference counting
A new array has a Given handle and refcount one. a→.share converts the handle
to SharedOwned without changing that count. Duplicating the independently
shared handle increments it:
crate::assert_interpret_only!(
r#"
struct Main {
fn main(given self) → Int {
let a = array_new[Int](2);
array_write[Int, ![a]](a!, 0, 10);
array_write[Int, ![a]](a!, 1, 20);
let s = a→.share;
let b = s→;
drop s;
print(array_give[Int, given, shared[b]](b.share, 0));
array_give[Int, given, shared](b→, 1);
}
}
"#,
expect_test::expect ;
Output: Trace: _1_a = Array { flag: Given, rc: 1, ⚡, ⚡ }
Output: Trace: array_write [Int, ! [_1_a]](_1_a ! , 0 , 10) ;
Output: Trace: array_write [Int, ! [_1_a]](_1_a ! , 1 , 20) ;
Output: Trace: let _1_s = _1_a → . share ;
Output: Trace: _1_s = shared Array { flag: SharedOwned, rc: 1, 10, 20 }
Output: Trace: let _1_b = _1_s → ;
Output: Trace: _1_b = shared Array { flag: SharedOwned, rc: 2, 10, 20 }
Output: Trace: drop _1_s ;
Output: Trace: print(array_give [Int, given, shared [_1_b]](_1_b . share , 0)) ;
Output: -----> 10
Output: Trace: array_give [Int, given, shared](_1_b → , 1) ;
Output: Trace: exit Main.main => 20
Result: Ok: 20
Alloc 0x19: [Int(20)]"#]]
);
In this example, let b = s→ creates the second owning handle. Dropping s
decrements the count to one; b keeps the backing allocation alive.
The implementation distinguishes conversion from duplication:
and_convert_given_to_sharedchanges ownership flags during value sharing.and_copy_shared_fieldsaccounts for duplication of owning boxed handles.and_share_fields_owned_elsewherehandles place sharing: it producesSharedPlacefrom unique handles, but increments the count when duplicating an existingSharedOwnedhandle.
Reference counts track owning handles, not every shared access to a place.
Uniquely owned arrays
Without value sharing, giving an array transfers its ownership:
crate::assert_interpret_only!(
r#"
struct Main {
fn main(given self) → Int {
let a = array_new[Int](2);
array_write[Int, ![a]](a!, 0, 10);
array_write[Int, ![a]](a!, 1, 20);
let b = a→;
array_give[Int, given, given](b→, 0);
}
}
"#,
expect_test::expect ;
Output: Trace: _1_a = Array { flag: Given, rc: 1, ⚡, ⚡ }
Output: Trace: array_write [Int, ! [_1_a]](_1_a ! , 0 , 10) ;
Output: Trace: array_write [Int, ! [_1_a]](_1_a ! , 1 , 20) ;
Output: Trace: let _1_b = _1_a → ;
Output: Trace: _1_b = Array { flag: Given, rc: 1, 10, 20 }
Output: Trace: array_give [Int, given, given](_1_b → , 0) ;
Output: Trace: exit Main.main => 10
Result: Ok: 10
Alloc 0x12: [Int(10)]"#]]
);
let b = a→ moves the uniquely owned array, leaving a uninitialized.
Dropping arrays
Releasing the final owning handle drops initialized elements and frees the backing allocation:
crate::assert_interpret_only!(
r#"
struct Data { x: Int; }
struct Main {
fn main(given self) → Int {
let a = array_new[Data](2);
array_write[Data, ![a]](a!, 0, new Data(1));
array_write[Data, ![a]](a!, 1, new Data(2));
drop a;
0;
}
}
"#,
expect_test::expect ;
Output: Trace: _1_a = Array { flag: Given, rc: 1, Data { x: ⚡ }, Data { x: ⚡ } }
Output: Trace: array_write [Data, ! [_1_a]](_1_a ! , 0 , new Data (1)) ;
Output: Trace: array_write [Data, ! [_1_a]](_1_a ! , 1 , new Data (2)) ;
Output: Trace: drop _1_a ;
Output: Trace: 0 ;
Output: Trace: exit Main.main => 0
Result: Ok: 0
Alloc 0x11: [Int(0)]"#]]
);
The model represents freed storage with Uninitialized words. The final heap
snapshot contains only the result integer, with no live array allocation.
Work in progress
- Soundness assessment: predicate vocabulary migration implemented; constructor, scope, drop, destructor, and branch fixes pending.
- Test organization: discussion proposal; migration not started.
- Var-pop normalization: preceding implementation plan.
- Vec: implementation history and remaining follow-ups.
- Unsafe code: historical design notes; see its status caveat.
Vocabulary as of September 25, 2026: shared replaces the former copy predicate;
use shared together with owned for the former narrower shared predicate.
Any shared permission can be duplicated. The full workspace suite passes
(627 model tests and 7 mdBook preprocessor tests).
Vec and array design
Status update (September 25, 2026): predicate names and interpreter helper names
have been migrated from copy to shared. Historical implementation notes and
open Vec follow-ups remain below. Explicit-drop and destructor behavior is under
review in the soundness assessment; its agreed
intent supersedes older drop descriptions here, and the fixes remain pending.
We are working our way towards the following design which will cover a “partially initialize” array type called Vec (the full Vec in the standard library would be expected to support more features, but this is enough for now). I’m also assuming all indices are in-bounds and a few other details.
Goal: Vector class
class Vec[type T] {
data: Array[T]
len: Int
fn push[perm P](P self, value: given T) where P is mut {
array_write[T, mut[self.data]](self.data.mut, self.len.give, value.give)
self.len = self.len.give + 1
}
fn get[perm P](P self, index: Int) -> given_from[self] T {
let data: given_from[self.data] Array[T] = self.data.give # P=given: moves data out, self not-whole, Vec.drop won't run.
# P=ref/shared: copies, self stays whole, Vec.drop runs but is
# harmless (is_last_ref guards cleanup, array_drop is no-op).
let len: Int = self.len.give
array_drop[T, given_from[self], ref[data]](data.ref, 0, index.give)
array_drop[T, given_from[self], ref[data]](data.ref, index.give + 1, len.give)
array_give[T, given_from[self], ref[data]](data.ref, index.give)
}
fn iter[perm P](P self) -> Iterator[P, T] {
new Iterator[P, T](self.give, 0)
}
drop {
if is_last_ref[ref[self.data]](self.data.ref) {
array_drop[T, given, ref[self]](self.data.ref, 0, self.len.give)
} else {}
}
}
class Iterator[perm P, type T] {
vec: P Vec[T]
start: Int
fn next[perm I](I self) -> P T
where
I is mut,
{
let index = self.start.give
self.start = self.start.give + 1
array_give[T, P, ref[self.vec.data]](self.vec.data.ref, index.give)
}
drop {
let data = self.vec.data.give # subtle: disables vec dtor
let start = self.start.give
let len = self.vec.len.give
# free the elements not yet iterated over:
array_drop[T, P, ref[data]](data.ref, start.give, len.give)
}
}
Key points
boxed classes
A boxed class indicates a class whose memory is stored in the heap. Boxed classes permit recursion, internal mutation with mutexes etc, and cheaper data movement. Currently the only boxed class is the built-in Array, but we expect to change this later.
A boxed-class is represented as a pointer along with flags that, in the real thing, will be stored in the low-bits of the pointer:
- dropped – the value has been moved or dropped
- given – sole ownership
- shared – shared ownership (refcount > 1)
- ref – a borrow (no ownership)
Note that a mut ref is different and always stored as a pointer to the object data, independent of whether it refers to a boxed class or a regular class.
Boxed class layout is:
[ref-count, fields...]
Dropping a owned boxed class decrements the ref-count and, if it is zero, drops the fields.
Array[T] type semantics
The Array[T] is a special boxed class that carries inline data:
[ref-count, capacity, elements...]
Dropping a owned array decrements the ref-count and, if it is zero, frees the array. IT DOES NOT DROP THE ELEMENTS, users are expected to drop those elements themselves. This is because array elements may not be initialized at all times.
Arrays support the following intrinsic, unsafe operations
-
array_new[type T](capacity: Int) -> given Array[T], returns a fresh owned uninitialized array. No permission parameter — always returnsgiven. -
array_capacity[type T, perm A](array: A Array[T]) -> Int where A is ref, returns capacity of an array -
array_write[type T, perm A](array: A Array[T], index: Int, value: given T) where A is mut, writes the value to the given index; any previous value is ignored -
array_drop[type T, perm P, perm A](array: A Array[T], from: Int, to: Int) where A is ref, drops elements fromfrom..to(exclusive) in a way that depends on the permissionP. Iffrom >= to, this is a no-op.- If
Pis given (i.e.,prove_is_given(P)— the permission alone, notP T), then the value is dropped. - Else this is a no-op.
- Note: the dispatch checks
P, notP T. Even ifTis a copy type (e.g., ashared class),P = givenmeans “I own these elements, clean them up.” This is needed to avoid leaks: a shared class with boxed fields (e.g.,shared class Wrapper { data: Array[Int] }) still needs its boxed fields’ refcounts decremented.
- If
-
array_give[type T, perm P, perm A](array: A Array[T], index: Int) -> P T where A is ref, reads and returns the element atindex. The behavior is determined by composingPwith the element’s runtime flags — not by classifying the static typeP T. The interpreter translatesPinto anowner_operms(given→Given, mut→MutRef, shared→Shared, ref→Borrowed), then callsobject_value_to_dataon the element with typeTand thatowner_operms. For boxed elements, the runtimeFlagsword is read and composed viawith_projection_flags: runtimeSharedalways wins (producing a shared copy with rc++), runtimeGivenpasses through the owner_operms. The result type isP T. The four effective behaviors:- Given + runtime Given: the value is moved and the source is uninitialized.
- MutRef + runtime Given: a mutable reference to the element’s fields is created. For boxed types, this dereferences through the
[Flags, Pointer]wrapper to point at the object data. For flat (non-boxed) types, theMutRefpoints directly into the array allocation at the element’s offset. - Shared (either from P or runtime Shared override): the element’s words are copied out, and then any boxed fields within the copy are transitioned to shared (flags set to
Shared, refcount incremented). Flat (non-boxed) fields are just copied — there is no refcount to touch. - Borrowed + runtime Given: the element’s words are copied out, and then any boxed fields within the copy have their flags set to
Borrowed. Flat fields are just copied.
Subtyping note: Because
shared ≤ ref, a shared value can be stored in a slot typedref[x] T. Whenarray_giveaccesses such an element withP = ref, the runtime Shared flags override the static Borrowed owner_operms, correctly producing a shared copy (rc++) instead of a borrow. This avoids a refcount leak that would occur if the static type alone determined the operation. The earlierP is shared ↔ A is sharedassertion was invalidated by this scenario and has been removed.
Implementation note: array_give_element calls perm_to_operms(P) to translate the permission into ObjectPerms, then delegates to the standard object_value_to_data (with the element’s raw type T, not P T) followed by give_place. This reuses the existing place access operations (give_place for given/shared, mut_place for mut, ref_place for ref) without any array-specific dispatch logic. No separate object_value_to_data_from_ty is needed — the same object_value_to_data used for normal place resolution handles array elements correctly when given the right owner_operms.
The semantics of drop and give are setup to support a “poly-permission” operation like Vec.get above. The array_drop calls in get are no-ops when P is not given, but they are present so that a single function body works correctly across all permissions — in the given case, they actually destroy the elements we don’t want.
Note that the return type given_from[self] T in Vec.get is effectively equivalent to P — given_from[place] picks up the permission of the place, so given_from[self] where self: P Vec[T] becomes P T. It is written as given_from[self] because it conveys the intent more clearly: “you get whatever permission you had on self.”
“drop” sections – defining custom destructors
A drop section in a class is a special optional section. The type of self in the drop body depends on the class predicate:
given class→self: given Class[...](sole ownership)class(default, i.e. share) →self: ref Class[...]shared class→self: ref Class[...]
When a drop body executes, self is treated as not whole even though all its fields are initialized. This means the whole-place drop logic will drop each field individually rather than dropping self as a unit (which would recursively invoke the drop body again). There is no special “post-drop-body field cleanup” step — the individual field drops are a consequence of the existing whole-place rules applied to a self that is never whole.
Partial moves and field access: Moving a field out of a struct makes the struct not-whole, but other initialized fields remain accessible. Reading a field of a partially-moved struct is legal as long as that specific field has not been moved. The whole-place rules only govern dropping, not reading. The type checker already supports this — liveness is tracked at the place level (e.g., self.vec.data and self.vec.len are independent places), so moving one field doesn’t invalidate sibling fields. No new type-checker feature is needed for the Iterator.drop pattern (self.vec.data.give then self.vec.len.give).
Places always require an access mode: A bare place (e.g., x, self.len) is never valid as an expression. Every use of a place as a value must go through an access mode: .give, .ref, .mut, or .drop. This applies to local variables, function parameters, and field accesses alike. For example, self.len.give (not self.len), index.give (not index).
is_last_ref primitive
is_last_ref[perm A](value: A T) -> Bool is a built-in intrinsic expression (like array_new, etc.). It accepts any ref value — e.g., is_last_ref[ref[self.data]](self.data.ref). It returns a Bool — a new built-in type that needs to be added to TypeName alongside Int. For boxed types (currently only arrays), it returns true if the refcount is 1 (i.e., this is the last owned handle). For non-boxed types, it always returns false — there is no refcount to check, and the caller cannot assume sole ownership. Under a garbage collector, is_last_ref always returns false — elements are collected independently.
Note: if/else already exists as Expr::If.
Executing “drop”
The drop for a class is executed whenever any owned handle to an instance of that class is dropped — not just the last reference. The type of self depends on the class predicate: given class gets self: given Class[...], while class (default) and shared class get self: ref Class[...]. For the non-given cases, ref is the lowest common denominator: shared is a subpermission of ref, so self: ref Class is valid for any owned handle to a share/shared class.
For classes like Vec that manage owned resources, the drop body uses is_last_ref to conditionally clean up only when this is the final handle:
drop {
if is_last_ref[ref[self.data]](self.data.ref) {
array_drop[T, given, ref[self]](self.data.ref, 0, self.len.give)
} else {}
}
When is_last_ref is false (other handles remain, or under GC), the drop body skips element cleanup — another handle will do it, or the GC will collect the elements independently.
Dropping local variables
When a function/block terminates, it drops all values found in “whole” places. A whole value is a value where no part has been moved.
Definition: accessible place. An accessible place is either
- a local variable
X - a field
P.FwherePis an accessible place of type class andFis a field - a field
P[i]wherePis an accessible place of type tuple andiis a tuple index
Note that elements of arrays are not accessible places.
Definition: whole place. An accessible place P is a whole place if
Pand all accessible places that extendPare initialized- This is the one place in the interpreter that we “branch” on uninitialized data. The compiler would be expected to track this statically or with extra flags on the stack as needed.
Example. Consider this function
class Vec[type T] {
data: Array[T]
index: Int
fn example(given self) {
# point A
let data = self.data.give
# point B
}
drop {
# ...
}
}
For the function example, the accessible places are self, self.data, and self.index.
At point A, self is a whole place. If the function were to return at point A, then self would be dropped. This would cause the drop code to execute, since we are dropping a Vec.
At point B, self.data has been moved, and hence self is not a whole place. self would not be dropped and hence its drop code would not run. self.index is a whole accessible place and would be dropped (but dropping an Int is a no-op).
FAQ
Q: Why does Vec.get call array_drop on all elements except the one being returned? Isn’t that wasteful for ref/shared?
The function body is polymorphic over P. When P is given, those array_drop calls actually destroy the elements we don’t want (we’re consuming the vec). When P is ref or shared, the array_drop calls are no-ops. The alternative would be separate implementations per permission, but one body that works for all permissions is simpler and correct.
Q: What does given_from[self] mean as a return type?
given_from[place] picks up the permission of the place. So given_from[self] where self: P Vec[T] is effectively P T. It’s written as given_from[self] rather than P because it conveys intent more clearly: “you get whatever permission you had on self.”
Q: How does the drop body avoid infinite recursion? If self is whole at the end of the drop body, wouldn’t whole-place dropping invoke the drop body again?
In a drop body, self is treated as not whole even though all its fields are initialized. This means the whole-place logic drops each field individually rather than dropping self as a unit. No special mechanism — just the existing whole-place rules applied to a self that is never whole.
Q: Why doesn’t Iterator.drop use is_last_ref, like Vec.drop does?
Because the poly-permission P already handles all cases correctly. Vec.drop needs is_last_ref because it runs on every handle drop (shared handles each trigger the drop body), so it must guard element cleanup to avoid double-free. Iterator.drop doesn’t have this problem: its array_drop[T, P, ...] dispatches on the permission the iterator was created with. When P = given, the iterator owns the elements and array_drop drops them. When P = shared or P = ref, array_drop is a no-op — the iterator doesn’t own the elements. No runtime guard is needed because the static permission already encodes ownership.
Q: In Iterator.drop, moving self.vec.data out disables Vec.drop. But what about the array backing itself?
The local data is whole at end of scope, so it gets dropped normally: refcount decremented, backing freed if zero. Any elements not covered by the array_drop(data.ref, start, len) call (i.e., elements before start that were already iterated and consumed) are already gone — they were moved out by next(). So the cleanup is complete: array_drop handles un-iterated elements, and dropping data frees the backing.
Q: When P = shared, doesn’t array_drop being a no-op cause leaks in Iterator.drop?
No. When P = shared, the iterator doesn’t own the vec — self.vec is shared Vec[T]. So self.vec.data.give produces a shared copy of the array (incrementing its refcount), not a move. self.vec stays whole, the array_drop call is a no-op, and the shared data copy just gets its refcount decremented at end of scope. Vec.drop runs on every handle being dropped, but the is_last_ref check means element cleanup only happens when the final handle is dropped. The “disables vec dtor” comment in Iterator.drop is only operative in the P = given case.
Q: What does array_drop with P = given actually do to each element? Shallow uninitialize, or full recursive drop?
Full recursive drop. If the element’s class has a drop { } section, that body runs (and then fields are individually dropped via the not-whole self rule). If it has no drop { } section, it behaves as if it had an empty drop {} — fields are individually dropped directly. This recurses all the way down through nested classes.
Q: What does .give do on a borrowed or shared value?
.give always gives the full permissions you have on a value. If you have given, it moves. If you have shared, it produces a shared copy (rc++). If you have ref, it produces a ref copy. You can always .give a value — it’s not restricted to owned data. This is why self.vec.data.give in Iterator.drop works for all permissions P: when P = given it moves the array out (disabling Vec.drop), when P = shared it produces a shared copy, when P = ref it produces a ref copy. In the non-given cases, self.vec remains whole, but the dtor is harmless — dropping a shared handle runs the drop body, but is_last_ref guards ensure cleanup only happens on the final owned handle. Dropping a ref handle is a no-op (borrows don’t own anything).
Q: In Vec.get with P = given, who frees the array backing allocation?
The local data holds the array after self.data.give. At end of scope, data is whole, so it gets dropped: refcount decremented, backing freed. The built-in array drop handles the backing allocation. The elements in the array are the user’s responsibility — that’s what the array_drop and array_give calls in the method body handle.
Q: What is .share in array.give.share? Is it an access mode?
No. .share is an expression-level operation (Expr::Share), not a place access mode. It operates on values, not places — that’s why we write array.give.share: first .give converts the place to a value, then .share converts that value from given to shared ownership. The access modes (.give, .ref, .mut, .drop) operate on places; .share is a separate expression form already in the grammar.
Q: Can drop bodies access class-level generic parameters?
Yes. Drop bodies have access to the class’s generic parameters (e.g., P and T in Iterator[perm P, type T]), just like any method on the class. This is why Iterator.drop can pass P to array_drop.
Q: How can array intrinsics bypass normal permission rules? Aren’t some of these operations obviously unsound?
Yes — array operations are unsafe intrinsics that deliberately violate the permission rules safe code must follow. Specific examples:
array_drop[T, given, ref[a]](a.ref, 0, 3)— drops and uninitializes element slots through only arefto the array. Normal safe code cannot modify memory throughref.array_give[Data, mut[a], ref[a]](a.ref, 0)— produces amut[a] Data(a mutable reference to an element) through only arefto the array. Normal safe code cannot obtainmutaccess throughref. The returnedmutref is a pointer directly at the object data for the element.array_write[T, mut[a]](a.mut, 0, value)— overwrites an element slot without dropping the previous value. Normal safe code would drop the old value first.
The A is ref / A is mut constraints are the minimum the type system enforces on the caller, but the operations themselves bypass normal permission rules internally. Soundness is the caller’s responsibility — e.g., Vec must ensure it never hands out two mut refs to the same element, never reads an uninitialized slot, etc. A full “unsafe effects” system to describe and constrain what unsafe operations can do is future work.
Q: How does the interpreter compute element offsets in arrays?
The interpreter already has size_of(env, ty) which returns the number of words a type occupies. Array element access computes ARRAY_ELEMENTS_OFFSET + index * element_size. This is internal interpreter machinery — user code (like Vec) just passes integer indices to array intrinsics and the interpreter handles offset calculation.
Q: What happens when array_drop is called with from >= to (empty or inverted range)?
It’s a no-op. This naturally arises in Vec.get when index == len - 1, producing array_drop(..., index + 1, len) where from == to.
Q: How does the interpreter decide which array_give/array_drop behavior to use?
For array_give, the interpreter translates P into owner_operms via perm_to_operms, then calls object_value_to_data on the element with its raw type T and that owner_operms. For boxed elements, the runtime Flags word is composed with owner_operms via with_projection_flags — runtime Shared always wins, runtime Given passes through. This means the runtime state can override the static permission: a shared value in a ref-typed slot correctly produces a shared copy, not a borrow. For flat types (no runtime flags), the type classification determines operms. The result is then passed to give_place, which dispatches on the final operms. For array_drop, the interpreter checks just P via prove_is_given(P) — if the permission is given, elements are dropped regardless of T.
Q: Why does array_drop dispatch on just P while array_give uses runtime flags?
array_give uses runtime flags (via object_value_to_data) because the operation on a boxed element must respect the element’s actual ownership state. A shared value stored in a ref-typed slot (valid via subtyping shared ≤ ref) must produce a shared copy (rc++), not a borrow — otherwise the refcount increment would never be undone and the refcount would leak. The runtime flags capture the true ownership state that the static type may have lost.
array_drop checks just P because the question is different: “should I clean up these elements?” If P = given, the caller owns the elements and must clean them up — even if T is a copy type like a shared class. A shared class with boxed fields (e.g., shared class Wrapper { data: Array[Int] }) still needs its boxed fields’ refcounts decremented.
Q: In Vec.get with P = given, the array has uninitialized trailing slots (capacity > len). Is that a problem when the array is dropped?
No. Dropping the array just decrements the refcount, and when it hits zero, the entire backing allocation is scrubbed (all words set to Word::Uninitialized). This does not inspect or iterate over element contents — it’s a bulk uninitialize of the raw memory. Trailing uninitialized slots are harmless; they get overwritten with the same Word::Uninitialized value they already had.
Random notes to check on
given_from[a.b] Foo– can this be contracted togiven_from[a]? Only when the fieldbis declared withgivenpermission (or no permission prefix). TheMvexpansion rule inredperms.rsreplacesgiven_from[place]with the permission ofplace. Sogiven_from[a.b]reduces to the permission ofa.b, which composes the permission ofawith the declared permission of fieldb. Ifa: mut[x] Fooandb: shared Bar, thena.bhas permissionshared(mut applied to shared = shared), sogiven_from[a.b]≠given_from[a](which would bemut[x]). The existing reduction rules handle this correctly — no special case needed.
Implementation plan
Implementation follows a TDD approach: write or update tests first to express intent, then implement until they pass. Each phase produces a working, all-tests-passing state. Tests that don’t yet match intent are fixed in the phase where the feature that enables correct behavior lands.
Agent workflow: Complete ONE phase at a time. After each phase, commit the work, run cargo test --all --all-targets to confirm 100% of tests pass (0 failures, 0 ignored unless pre-existing), and stop. Do not begin the next phase. A human must review the completed phase and explicitly approve before the next phase begins. This is a hard rule — never do more than one phase without human-in-the-loop review. Each phase should be a separate commit (or small series of commits).
Phase 1: Standalone renames and syntax ✅
No semantic changes. Clears the deck so subsequent code matches the doc’s notation.
- Rename
array_set→array_write— pure rename across grammar, interpreter, type system, and all tests. Currentarray_setalready has “ignore previous value” semantics. -
Rename— skipped. The parser prefix ambiguity betweengiven_from→givengivenandgiven_from[...]is unresolved and not worth the risk. Keepinggiven_from[places]as-is. - Remove
Flags::Dropped— replaced all uses ofFlags::DroppedwithWord::Uninitialized. RemovedDroppedfrom theFlagsenum. Addedtry_read_flags()helper that returnsOption<Flags>(Nonefor uninitialized,Some(flags)for live values). Callers now check forWord::Uninitializedbefore callingexpect_flags(). Error messages are “access of uninitialized value” uniformly. Note:and_drop_fieldsstill silently skips uninitialized boxed values rather than erroring — this is needed because the interpreter’s end-of-scope cleanup drops ALL variables unconditionally without checking wholeness. Phase 4’s whole-place checks will allow this to become an error. - Scrub entire array backing on refcount zero — when an array’s refcount reaches 0, all words in the backing allocation (header + elements) are set to
Word::Uninitialized. Freed arrays now disappear completely from heap snapshots. Updated 44 test snapshots. -
param is predsyntax — flipped bothPredicate::ParameterandPredicate::Variancegrammar from#[grammar($v0($v1))]to#[grammar($v1 is $v0)]. All predicates now use consistentparam is predsyntax (e.g.,P is mut,T is relative,T is atomic). Addedisto KEYWORDS. Updated all test programs andwhereclauses. Class predicates (given class,shared class) are unchanged.
Phase 2: Permission parameter plumbing ✅
Add P and A parameters to array ops. Loosen access requirements. Keep current behavior — all existing call sites pass P = given (or equivalent).
- Add
P,Aparameters toarray_give—array_give[T, P, A](array, index). No grammar annotation change needed —$[v0]already parses aVec<Parameter>as a comma-separated list inside brackets. The interpreter/type-checker code that destructures the parameter list changes from expecting 1 element to expecting 3. Interpreter: extract P and A from parameters but dispatch only on P=given (move, current behavior). Type system: accept 3 type parameters, check array expression againstA Array[T], returnP T. - Add
P,Aparameters toarray_drop—array_drop[T, P, A](array, index). Same as above — no grammar annotation change for the bracket params. Keep single-index for now. Interpreter: extract P, dispatch only on P=given (drop, current behavior). Type system: check array expression againstA Array[T](no mut requirement — loosened from currentmut). - Add
Aparameter toarray_write—array_write[T, A](array, index, value). Same — no grammar annotation change. Type system: requireA is mutviaprove_is_mut(A), check array expression againstA Array[T]. - Add
Aparameter toarray_capacity—array_capacity[T, A](array). Same — no grammar annotation change. Type system: check array expression againstA Array[T](accepts any perm).
TDD notes: Update all existing test call sites from array_give[T](...) to array_give[T, given, ref[a]](...) etc. Tests should pass with identical behavior since P=given matches current semantics. Key tests to watch:
array_give_given_class_moves_out— should keep move semantics with explicitP = givenarray_drop_element,array_drop_class_element— should keep drop semantics withP = givenarray_capacity_given,array_capacity_shared,array_capacity_ref— should all work withA is ref
Phase 3: Poly-permission semantics
Implement dispatch on P for array_give and array_drop. Add range semantics to array_drop.
-
array_givedispatches on P + runtime flags — The interpreter translatesPintoowner_opermsviaperm_to_operms(P), then calls the standardobject_value_to_dataon the element with its raw typeTand thatowner_operms. For boxed elements, the runtimeFlagsword is composed withowner_opermsviawith_projection_flags— runtimeSharedalways overrides toShared, runtimeGivenpasses through the owner_operms. This correctly handles subtyping: a shared value stored in a ref-typed slot produces a shared copy (rc++), not a leaked borrow. The result is passed togive_placewhich dispatches on the finaloperms. The earlierobject_value_to_data_from_ty(which derived operms from the static type, ignoring runtime flags) was deleted. TheP is shared ↔ A is sharedassertion was invalidated by the subtyping scenario and removed. -
array_dropdispatches on P — given → actually drop each element in range, else → no-op. Dispatch usesprove_is_given(P)(the permission alone, notP T). Even copy types likeshared classare dropped when P=given — needed to avoid leaking refcounts on boxed fields inside shared classes. -
array_droprange semantics — changed grammar from(array, index)to(array, from, to), drops elements infrom..torange (exclusive) in forward order.from >= tois a no-op. All existing single-indexarray_drop(a, i)calls rewritten toarray_drop(a, i, i + 1). Updated type system, interpreter, liveness, and all tests.
TDD notes — tests written and passing:
-
array_give_p_mut—array_give[Data, mut[a], ref[a]](a.ref, 0)returns amut[a] Data✅ -
array_give_p_shared—array_give[Array[Int], shared, ref[outer]](outer.ref, 0)returns a shared copy, rc incremented ✅ -
array_give_p_ref—array_give[Array[Int], ref[outer], ref[outer]](outer.ref, 0)returns a borrowed copy ✅ -
array_drop_p_shared_is_noop—array_drop[Data, shared, ref[a]](a.ref, 0, 1)does nothing, element still accessible ✅ -
array_drop_p_given_range—array_drop[Data, given, ref[a]](a.ref, 0, 3)drops elements 0, 1, 2 ✅ -
array_give_p_given_int_is_copy— giving an Int element with P=given copies without uninitializing ✅ -
array_drop_empty_range_is_noop—array_dropwithfrom >= tois a no-op ✅ -
array_drop_shared_class_element_is_noop— shared class (Pt) elements:array_drop[Pt, given, ...]is a no-op sincegiven Ptis shared ✅ -
array_give_ref_of_shared_is_shared—P = ref[shared_place]where the place is shared. The type system normalizesref[shared_place]tosharedbefore substitution, soParrives assharedand the shared branch fires. This tests that a ref to a shared place correctly resolves to shared semantics.
class Data {}
fn head[perm P](array: P Array[Data]) -> P Data
where
P is ref,
{
array_give[Data, P, ref[array]](array.ref, 0)
}
fn main() {
let array: given Array[Data] = array_new[Data](1)
array_write[Data, mut[array]](array.mut, 0, new Data())
let shared_array = array.give.share
let elem0 = head[ref[shared_array]](shared_array.ref)
# elem0 should be `shared Data`, not `ref Data`
}
Phase 3.5: Test rewrite
Rewrite existing tests to use the new array op signatures and express their intended semantics now that poly-permission and range ops are available.
-
Restore shared-array test intent —
shared_array_give_class_is_shared_copyalready usedP = sharedexplicitly after Phase 3. Verified refcount lifecycle. No change needed. -
Fix ref-array test intent —
ref_array_give_int_element,ref_array_give_class_elementupdated to useP = ref[a]explicitly.ref_array_of_shared_arraysupdated to use element typeshared Array[Int](matching test name) withP = ref[outer]. Key behavioral changes:ref_array_give_class_elementnow correctly showsd = ref [a] Data(borrowed copy, element stays initialized);ref_array_of_shared_arrayscorrectly showsgot = shared Array { ... }(shared copy via runtime flags). -
Runtime-vs-static mismatch test —
array_give_ref_of_runtime_shared_element: stores a shared array into aref[dummy] Array[Int]-typed slot, gives withP = ref[outer]. Demonstrates that runtime Shared flags override static ref operms, producing a shared copy (rc++) instead of a borrowed copy (which would leak the refcount). This test motivated the deletion ofobject_value_to_data_from_tyand the switch to runtime-flag-based dispatch. -
Verify “freed” test snapshots —
refcount_reaches_zero_frees_allocationandshared_array_all_refs_dropped_frees: backing allocations absent from heap ✅.nested_array_all_refs_freed: inner array backing (Alloc 0x03) correctly remains — arrays don’t drop their elements, so the inner array handle is scrubbed without being properly dropped. Updated comment to document this as expected leak behavior. -
Intentional leak tests — tests that deliberately skip
array_dropon some or all elements, then drop the array. UsesArray[Array[Int]]so inner arrays are boxed with separate heap allocations that survive the outer’s scrub. Flat element types (likeclass Data { x: Int }) are stored inline and don’t produce separate allocations to leak.array_leak_all_elements— create array of 2 inner arrays, drop outer without dropping elements. Both inner backing allocations remain as orphans.array_leak_some_elements— drop element 0 of a 2-element array, skip element 1, drop outer. Element 1’s backing allocation remains.
TDD notes: This phase produces no new features — only test corrections that reflect the capabilities added in Phase 3 (poly-permission dispatch, range semantics). Do NOT add tests for Phase 4 features (drop sections, is_last_ref) or adjust snapshots to account for them. All tests should pass before and after, but the snapshots change to reflect correct behavior enabled by Phase 3. Use UPDATE_EXPECT=1 after verifying each test’s intent is right.
Phase 4: Drop sections
Grammar, type checking, and interpreter support for drop { ... } blocks and whole-place drop semantics.
4a: Grammar ✅
-
drop { ... }in ClassDecl — addedDropBodyenum (None|Block(Vec<Statement>)) withDefaultderive toClassDeclBoundData. Grammar:drop { stmts }after methods. Updated all destructuring sites. Added 3 parser tests.
4b: Type checker ✅
- Type-check drop body — added
check_drop_bodyjudgment toclasses.rs. Forgiven class: type-checks withself: given Class[...]. Forclass(share) andshared class: introduces a universal perm variablePwithP is sharedassumed, then type-checks withself: P Class[...]. This means the drop body can read fields (via.refor.givewhich copies) but cannot mutate or move fields. Addedopen_universal_perm_var()helper toEnv. Tests:drop_body_prints_field,given_class_drop_body_can_move,share_class_drop_body_cannot_move_field,share_class_drop_body_cannot_mut_field,shared_class_drop_body_ref_self,empty_drop_body,drop_body_accesses_class_generics. - Array elements are not accessible places — confirmed the type checker already rejects
array[i].givebecauseProjection::Indexis for tuples only. Added testarray_index_not_accessible_place. Note: formality-core parses kind keywords astyandperm(nottypeandperm), so generic class tests must use[ty T]not[type T].
4c: Interpreter ✅
-
Booltype and operators — addedBooltoTypeName(shared class, always copyable, 1 word,Word::Intrepresentation). Addedtrue/falseasExprvariants with KEYWORDS. AddedBinaryOpenum (Add,Sub,Ge,Le,Eq,Ne) with a singleExpr::BinaryOp(lhs, op, rhs)variant. Type rules grouped into “arithmetic” (Int→Int) and “comparison” (Int→Bool). ChangedExpr::Ifcondition fromInttoBool. Updated 5 existing tests. Note: bare>and<omitted due to parser prefix ambiguity with>=/<=in formality-core; the restricted set is sufficient. -
is_last_refintrinsic — addedis_last_ref[perm A](value: A T) -> BoolasExpr::IsLastRef. Type system accepts any value, returnsBool. Interpreter: for boxed types returnsrefcount == 1, for non-boxed types returnsfalse. - Execute drop body —
drop_valuechecks if value is an owned class with a non-empty drop body. Only runs for owned handles (given/shared), not borrowed. Only runs if value is “whole” (all fields initialized viais_value_whole). Drop body runs BEFORE field-by-field cleanup.selftype:given class→self: given Class[...], else →self: ref[magic] Class[...]using syntheticVar::Magic. Fixeddrop_placefor flat types to route throughdrop_valueso drop body fires on explicit.drop. AddedAccess::Droptype rule. - Whole-place drop — implemented as
is_value_wholecheck insidedrop_valuerather than as a separate end-of-scope mechanism. For flat types, checks all words forUninitialized. For boxed types, checks flags word. Partially-moved classes: drop body is skipped, buttraverse_value+and_drop_fieldsstill cleans up each field individually (uninitialized fields are skipped bytry_read_flagsreturningNone). This simpler approach works becauseand_drop_fieldsalready handles uninitialized boxed fields gracefully. - Array elements are not accessible places — already implemented (
find_object_fieldsreturns empty vec for arrays).
Tests written and passing:
class_with_drop_body— drop body runs on scope exit ✅drop_body_runs_on_give— drop body runs on explicit.drop✅drop_body_runs_on_every_shared_handle— two shared copies produce two drop runs ✅is_last_ref_true_when_sole_owner— boxed object with refcount 1 ✅is_last_ref_false_when_shared— shared array with refcount 2 ✅drop_body_with_is_last_ref— Vec-like conditional cleanup pattern ✅bool_true_false_literals— true/false display correctly ✅comparison_operators— all 6 comparisons work ✅subtraction— basic subtraction ✅partially_moved_class_drops_remaining_fields— drop body skipped, remaining fields cleaned ✅partial_move_then_read_other_field— Iterator.drop pattern works ✅drop_body_accesses_class_generics— full Vec+Item pattern with nested drops ✅
TDD notes — tests to write before implementing:
class_with_drop_body— simple class withdrop { print(self.x) }, verify drop body runs on scope exitdrop_body_self_not_whole— class with drop body that moves one field; verify remaining fields are individually dropped, no infinite recursionpartially_moved_class_drops_fields— move one field out of a class, verify remaining fields drop at scope exit but the class drop body does NOT run (self not whole)partial_move_then_read_other_field— move one field out of a struct, then read a different field with.give. Verify the read succeeds. This is the patternIterator.droprelies on (self.vec.data.givethenself.vec.len.give). Already works in the interpreter (field projection is pure pointer arithmetic, no wholeness check), but worth an explicit test.vec_drop_cleans_elements—Vecclass withdrop { array_drop[T, given, ref[self]](self.data.ref, 0, self.len.give) }, verify elements are dropped when vec goes out of scopeshared_class_drop_gets_ref_self— shared class with drop body, verifyself: ref Classdrop_runs_on_every_handle— shared class with drop body, create two shared handles, verify drop body runs twice (once per handle drop)is_last_ref_true_when_sole_owner— boxed object with one handle,is_last_refreturns trueis_last_ref_false_when_shared— boxed object with two handles,is_last_refreturns false on first drop, true on second
Phase 5: Integration — Vec as a test program ✅
Write the full Vec and Iterator from the design doc as a test program that exercises the entire stack.
- Vec push and get — replaced the old
vector_push_and_gettest (was ignored, used outdated syntax). Fresh testvec_push_and_get_givenuses the target signatures from the design doc. Alsovec_push_increments_lenfor basic push. All pass end-to-end. - Vec iter and next —
vec_iter_and_nexttests consuming iteration: creates Vec, pushes 3 items, creates iterator, callsnext()once. Iterator.drop cleans up remaining elements (prints 20, 30). Verified elements moved out and cleanup correct. - Shared Vec access —
shared_vec_getwithP = shared: elements are shared copies,array_dropis no-op, Vec.drop withis_last_refonly cleans up on final handle. - Ref Vec access —
ref_vec_getwithP = ref[v]: elements are borrows, Vec remains intact. - Vec drop lifecycle —
vec_drop_cleans_all_elements: push 3 items, let Vec go out of scope. Drop body runs,is_last_reftrue, all elements cleaned (prints 100, 200, 300). Heap is clean.
Implementation notes — interpreter fixes required:
Three interpreter bugs were found and fixed to make the Vec tests work:
-
call_methoddouble-wrappedthis_ty: The method’sthis_decl.permwas applied on top of the receiver’s type, which already carried the correct permission from the access mode. E.g.,v.mut.push[mut[v]]()produced receiver typemut[v] Vec[T], butcall_methodadded anothermut[v]on top →mut[v] mut[v] Vec[T]. Fixed by usingthis.tydirectly. -
is_mut_ref_typeusedprove_is_mutwhich failed on out-of-scope places: Inside a method,prove_is_mut(env, mut[v] Vec[T])tries to resolve placevin the method’s env, butvis from the calling scope. Changed to structural pattern matching:matches!(ty, Ty::ApplyPerm(Perm::Mt(_), inner)) && !is_shared_type(inner). The!is_shared_typeguard is needed becausemut[x] Intis NOT stored as a MutRef — copy types are always inline. -
give_placewith MutRef operms on copy types: When accessingself.start.givethrough a mut ref (Iterator.next), the operms were MutRef but the field type was Int (copy).give_placeblindly created a MutRef, but Int fields are stored inline, not through MutRef pointers. Fixed: if the type is shared, produce a ref copy instead of a MutRef.
Snapshot improvement: array_give_p_mut snapshot now correctly displays Data { x: 42 } instead of <unexpected: Int(42)> — the structural is_mut_ref_type correctly identifies and dereferences MutRef types during display.
Call site syntax: Method calls require the receiver to use an access mode: v.mut.push[mut[v]](...), v.give.get[given](...), v.ref.get[ref[v]](...). This matches the language rule that places always require an access mode.
Future work
-
Reunify
is_mut_ref_typewithprove_is_mut— The interpreter’sis_mut_ref_typeuses structural pattern matching (Ty::ApplyPerm(Perm::Mt(_), inner)where inner is not copy) instead of the type system’sprove_is_mutjudgment. This divergence exists becauseprove_is_mutonPerm::Mt(places)resolves each place’s type viaenv.place_ty(place), but inside a method body the places (e.g.,vinmut[v]) refer to the calling context and are not in the method’s env. Possible fixes: (a) enrich the method env with calling-context information, (b) add a simpler “structural” rule toprove_mut_predicatethat recognizesPerm::Mt(_)as always mut without checking places, or (c) propagate where-clause assumptions into the interpreter’s env. Each has trade-offs — this should be revisited when the interpreter and type system are more integrated. -
Move Vec tests to
assert_interpret!— Most Vec tests currently useassert_interpret_only!(interpreter-only, no type checking) because the type checker doesn’t yet support the permission patterns Vec uses (generic permP self,given_from[self]return types, where-clause dispatch). As the type checker gains support for these features, migrate tests toassert_interpret!(type-check AND execute). Only keepassert_interpret_only!for tests that specifically exercise unsafe/UB patterns. -
Design unsafe effects — array operations are currently “magic” intrinsics that bypass normal permission rules (e.g.,
array_dropuninitializes element slots throughA is ref). A proper unsafe effects system would describe and constrain what unsafe operations can do. Not needed for the current Vec milestone, but important for the broader language design.
Unsafe code
Status (September 25, 2026): historical design sketch, not a description of all
current syntax or runtime layouts. See Vec implementation notes for
array implementation history and the soundness assessment
for current drop/destructor decisions and pending fixes. The current predicate
shared replaces copy; any shared permission can be duplicated. This vocabulary
change does not implement the outstanding unsafe-code or soundness work.
Levels of classes
give class(can be given)share class(can be shared, the default)shared class(already shared)
Memory representation of values
We have two classes of values
- unique – these are give classes, share classes, and shared classes that have a type parameter which is unique
- shared – these are shared classes, integers, flags, characters (when we add those)
Unsafe primitives
There is a built-in type
Array[T]– stores a ref count, a length, and N elements of typeT(elements are initially uninitialized)
Array[T] is a share class and offers the following built-in operations (special expressions):
ArrayNew[T](length: uint) -> Array[T], allocates an array of the given lengthArrayCapacity[T](array: Array[T]) -> uint, returns the capacity that the array was created withArrayGive[T](array: Array[T], index) -> given[array] T, gets an element from the arrayArrayDrop[T](array: ref Array[T], index), drops an element from the array (recursively drops the element, marks slot uninitialized)ArraySet[T](array: Array[T], index, value: given T), initializes an element from the array for first time
Type sizes
size_of[T]() is a built-in expression that returns the number of Words needed to store a value of type T. It takes a single type parameter and no arguments. It type-checks to Int.
The interpreter evaluates size_of[T]() as:
Int→ 1Tuple(0)(i.e.,()) → 0- A class → 1 (for the flags word if unique, 0 if shared) + sum of
size_offor each field’s type - Other (including
Array[T]once added) → 1
The real system has more complex layout rules obviously.
Unique values
Unique values are 4-aligned and begin with a flags field:
+--------------+
| flags |
| ...fields... |
+--------------+
Shared values
Shared values are just stored as a sequence of fields. No flags are needed because they are always copied out.
Representing in the interpreter
We will have a Alloc struct like
struct Alloc {
data: Vec<Word>
}
enum Word {
Int(isize),
Array(Pointer),
MutRef(Pointer),
Flags(Flags),
Uninitialized,
}
struct Pointer {
index: usize,
offset: usize,
}
enum Flags {
// Indicates that the value is uninitialized
Uninitialized,
// Unique ownership
Given,
// Shared ownership
Shared,
// Copied fields from value stored elsewhere, either `ref` or `shared mut`
Borrowed,
}
All values, including arrays, use the same Alloc struct. An Array[T] allocation stores the ref count and length as the first two words, followed by the elements:
+------------------+
| Int(refcount) |
| Int(length) |
| element 0 | \
| ... | > each element is size_of[T]() words
| element N-1 | /
+------------------+
Place operations
There are four operations on places:
place.giveplace.refplace.mutplace.drop
Each begins by evaluating the place which results in a Perm and a Pointer:
- the
Permrepresents the most restrictive we have passed through. If at any point we access an uninitialized flags the interpreter faults. - the
Pointeridentifiers the location in memory that the place is stored
The Perm can be one of
enum Perm {
Given,
Shared,
Borrowed,
Mut,
}
The operations then proceed as follows:
giveexamines theFlagsGiven=> copy the fields to the destination and then mark the Flags asUninitializedShared=> copy the fields to the destination, set the flags toShared, and then apply the share operation to them (see below)Borrowed=> copy the fields to the destination, set the flags toBorrowedMut=> create aMutRefwith the pointer
refexamines theFlagsShared=> copy the fields to the destination, set the flags toShared, and then apply the share operation to them (see below)Given|Borrowed|Mut=> copy the fields to the destination, set the flags toBorrowed
mutexamines theFlagsShared|Borrowed=> faultGiven|Mut=> create aMutRefvalue
dropexamines theFlagsGiven=> drop fields recursivelyShared=> apply “drop shared” operation (see below)Borrowed|Mut=> no-op
The “drop shared” operation
When dropping a shared value, we visit its fields and check their type:
- for a give|share class, we recursively apply drop shared to its fields
- for an
Array[T], decrement the ref count; if it reaches zero, recursively drop all initialized elements and free the array - for a borrowed class | mut-ref, no-op
- for int | flags, ignore
The “share operation” (duplication accounting)
When a shared value is duplicated (by place.give or place.ref on a Shared value), we apply share_op to the copy to account for the new references:
- for a given|shared class, we recursively apply share op to its fields
- for an
Array[T], inc the ref count - for a borrowed class | mut-ref, no-op
- for int | flags, ignore
Converting to shared (in-place)
When value.share converts a value from Given to Shared, we apply convert_to_shared to recursively flip flags:
- for a given|shared class, flip flags Given→Shared, then recurse into fields
- for an
Array[T], flip flags Given→Shared (no refcount change — no duplication) - for a borrowed class | mut-ref, no-op
- for int | flags, ignore
Value operations
There is one operation on values:
value.share
This operates on a value that has already been copied to a destination. It converts the value from unique to shared ownership:
- If the flags are
Given, set them toSharedand apply the share operation to the fields - If the flags are
SharedorBorrowed, no-op (already shared or borrowed)
Array reference counting
Arrays are share class types. The ref count (stored at offset 0 of the array allocation) tracks how many live references exist.
Two share-related operations
There are two distinct operations that involve sharing:
-
convert_to_shared— in-place conversion from Given to Shared ownership. Called byExpr::Share(i.e.,value.share). Recursively flips flags from Given→Shared on nested class fields. For arrays: just flips the value’s flags, no refcount change. No duplication occurs. -
share_op— duplication accounting. Called when a Shared value is copied (byplace.giveorplace.refon a Shared value). For arrays: increments the refcount. For classes: recurses into fields to account for nested duplications.
The distinction matters because Expr::Share converts in place (one reference → one reference, no refcount change), while place.give on Shared duplicates the value (one reference → two references, refcount must increase).
Lifecycle
- ArrayNew — allocates
[Int(1), Int(length), elements...]. Refcount starts at 1. - value.share — flips flags Given→Shared via
convert_to_shared. Refcount stays 1. - place.give on Shared — copies the value, calls
share_opwhich increments refcount. Each additional copy adds 1. - drop (Given or Shared) — decrements refcount. If zero: recursively drop all initialized elements, then free the array allocation.
Implementation plan
Approach: doc-driven, test-driven
Each step follows the same rhythm:
- Write/update mdbook chapter describing the feature or change
- Write tests (interpreter tests using
assert_interpret!, type system tests usingassert_ok!/assert_err!) that express the expected behavior - Implement until the tests pass
The mdbook chapters to write/update:
md/interpreter.md(existing) — describes theAlloc/Word/Pointer/Flags/TypedValuememory model, with word-level walkthrough and access mode table.md/wip/unsafe.md(this doc) — eventually becomes a real chapter coveringArray[T],size_of, and the unsafe primitives.
Step 1: Remove PointerOps ✅
Removed TypeName::Pointer and all 6 PointerOps expression variants. Compiles and existing tests pass.
Step 2: Add size_of[T]() ✅
Added Expr::SizeOf(Vec<Parameter>) with #[grammar(size_of $[v0] ( ))]. Type-checks to Int. Interpreter computes word count: 1 for Int, flags + fields for classes, 0 for unit. 6 interpreter tests.
Step 3: Restructure interpreter memory model ✅
Replaced Value/ValueData/ObjectData/ObjectFlag with flat word-based memory:
Alloc { data: Vec<Word> }— flat word arrays, no type tags in memoryWord { Int, Flags, Uninitialized }— individual memory wordsFlags { Uninitialized, Given, Shared, Borrowed }— permission flags for unique objectsPointer { index, offset }— position within an allocationTypedValue { pointer, ty }— types flow through evaluation, not stored on allocations
Object layout: [Flags, field0_words..., field1_words...] for unique classes, [field0_words...] for shared classes (no flags word). Field access uses type-driven offset computation. Display: flag: Given (was Owned), flag: Borrowed (was Ref), shared classes omit flag entirely.
Step 4: Implement place operations (give/ref/mut/drop) ✅
Implemented flags-dependent place operations (give/ref/drop) dispatching on Given/Shared/Borrowed/Uninitialized. Added UB faulting — interpreter bails on all undefined behavior to enable fuzzing the type checker for soundness. Removed Access::Sh — share is now exclusively a value operation (Expr::Share), users write d.give.share. Added prove_is_shareable check to Expr::Share typing rule. Mut is stubbed (bail on use).
Step 4b: Doc/code review cleanup ✅
Reviewed interpreter.md + unsafe.md against the implementation. Fixed share_op ordering (flag flip before recurse) and break/return control flow (introduced Outcome enum, anyhow::Error reserved for UB faults). Remaining items tracked in WIP.md.
Step 5: Add Array[T] to grammar and implement operations
- Doc: expand
md/wip/unsafe.mdinto a proper chapter — motivating example (building a simple Vec), then walk through ArrayNew/Initialize/Get/Drop. - Tests first: write interpreter tests — create array, initialize elements, read them back, drop elements. Test out-of-bounds faults. Test uninitialized read faults.
- Add
TypeName::Array(with one type parameterT) - Add 5 Array expression variants:
ArrayNew[T](expr),ArrayCapacity[T](expr),ArrayGive[T](expr, expr),ArrayDrop[T](expr, expr),ArraySet[T](expr, expr, expr) - Add Array keyword entries
- Add type-checking rules for all 5 operations
- Add match arms in type system (
env.rs,liveness.rs,places.rs,types.rs) - Interpreter implementation:
ArrayNew[T](length)— allocate[Int(1), Int(length), Uninitialized...]ArrayCapacity[T](array)— read length wordArraySet[T](array, index, value)— write element at computed offsetArrayGive[T](array, index)— read element via give semanticsArrayDrop[T](array, index)— recursively drop element, mark slot uninitialized
- Goal: arrays work end-to-end
Step 6: Implement reference counting for arrays
- Doc: add section to array chapter on sharing and ref counting — walk through what happens when an array is shared, how ref count increments/decrements, when elements get dropped.
- Tests first: write interpreter tests — shared array survives after original dropped, array freed when last reference dropped, elements recursively dropped on array free.
- Share operation increments array ref count
- Drop-shared decrements ref count, frees when zero
- Goal: array ref counting works correctly
FAQ
Why not have a specialized ArrayAlloc instead of using generic Alloc?
We use a single Alloc type for all allocations, with arrays storing their ref count and length as the first two words by convention. A specialized ArrayAlloc would be more type-safe in the interpreter, but we expect to add more ref-counted allocation kinds in the future (e.g., a Box-like type that carries just a ref count + value). Keeping one uniform allocation pool with layout-by-convention is simpler and more extensible than adding a new allocation variant for each kind.