Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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 spellingMeaning
given Data, given[] Data, [] DataIndependent unique ownership of named Data
given[x, y] T, [x, y] TPermission derived from the listed places
shared T, shared[] TIndependent shared ownership
shared[x, y] TSharing from the listed places
![x, y] TMutable 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:

surface_inline_type_example [src]
struct Worker {
    fn self.consume(input: type T) {}
}

lowers to this core declaration:

core_inline_type_example [src]
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 formReceiver 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:

surface_generic_permission_example [src]
struct Worker {
    fn self!edit[type T](value: !T) { (); }
}

has the following explicit core signature (fresh names are illustrative):

core_generic_permission_example [src]
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:

explicit_generated_permission_call [src]
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.

Property source and tests

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.

Property source and tests

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.

Property source and tests

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:

classes_point_example [src]
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:

DeclarationPredicateMeaning
class Foo { }ClassAffine data; may have a destructor; cannot be shared as a value
struct Foo { }StructShareable data with mutable fields; no destructor
shared struct Foo { }SharedCopyable 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:

ClassDecl [src]
#[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):

FieldDecl [src]
#[term($?atomic $name : $ty ;)]
pub struct FieldDecl {
    pub atomic: Atomic,
    pub name: FieldId,
    pub ty: Ty,
}
Atomic [src]
#[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.

Property source and tests

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:

simple_function_example [src]
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:

ClassDecl [src]
#[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:

FieldDecl [src]
#[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:

MethodDecl [src]
#[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:

Env [src]
#[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:

check_program::check_program [src]
(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:

check_method::check_method [src]
(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:

check_body::block [src]
(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_block::place [src]
(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:

type_statements_with_final_ty::cons [src]
(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_statement::let [src]
(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 type ty. The live_after.overwritten(&id) removes p from the live set, since p doesn’t exist yet while the RHS is being evaluated.

  • env.push_local_variable(&id, ty) – Add p to 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 in p. (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:

type_expr::new [src]
(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:

  1. Looking up the struct Point to find its fields: x: Int, y: Int.
  2. Checking that the argument count matches the field count (2 = 2).
  3. Creating a temporary variable to represent the object under construction.
  4. Invoking type_field_exprs_as to type each argument against the corresponding field type – 22 against Int, 44 against Int. Both succeed via the integer typing rule:
type_expr::constant [src]
----------------------------------- ("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:

VariableType
selfgiven Main
pPoint

Typing the return expression 0

The final statement in the block is 0 – an expression statement. It is typed by this rule:

type_statement::expr [src]
(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):

PlaceExpr [src]
#[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:

Place [src]
#[term($var $*projections)]
pub struct Place {
    pub var: Var,
    pub projections: Vec<Projection>,
}

A projection is a field access:

Projection [src]
#[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:

Access [src]
#[term]
#[derive(Copy, Default)]
#[customize(parse, debug)]
pub enum Access {
    #[default]
    #[grammar(.share)]
    SharePlace,

    Gv,

    #[grammar(!)]
    Mt,

    #[grammar(.drop)]
    Drop,
}
AccessMeaning
place→Move the value, or duplicate it when shared
place or place.shareShare 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:

giving_a_value [src]
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:

type_expr::give place [src]
(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 of d in 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 [src]
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:

move_place::give [src]
(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:

move_place::copy [src]
(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:

giving_a_value_twice_is_error [src]
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:

giving_a_field [src]
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:

giving_field_then_whole_is_error [src]
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:

giving_whole_then_field_is_error [src]
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.

Property source and tests

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:

shared_classes_are_copyable [src]
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 typesgiven[d1, d2] is unique?
Any pair of given Wrapper and ![source] WrapperYes
Any pair containing shared Wrapper or shared[source] WrapperNo

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.

Property source and tests

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:

sharing_a_value [src]
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::share value [src]
(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 type ty.

  • 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:

ClassPredicate [src]
#[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,
}
DeclarationPredicateShareable?
class Foo { }ClassNo
struct Foo { }StructYes
shared struct Foo { }SharedAlready shared

The prove_is_struct judgment delegates to the general predicate-proving machinery:

prove_is_struct::is [src]
(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:

move_place::copy [src]
(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:

shared_classes_always_shared [src]
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:

given_classes_cannot_be_shared [src]
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:

sharing_is_idempotent [src]
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 struct means values of T can be shared as values.
  • T is unique means access must remain exclusive: this includes unique owners and mutable leases. It does not imply ownership.
  • T is shared means values of T are shared and can be duplicated. This includes values obtained by sharing a place; it does not require ownership.
  • T is owned means 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 typesgiven[d1, d2] is owned?
Any pair of given Wrapper and shared WrapperYes
Any pair containing shared[source] Wrapper or ![source] WrapperNo

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.

Property source and tests

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.

Property source and tests

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.

Property source and tests

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:

ExpressionOperationResulting permission
foo or foo.shareShare the place fooshared[foo]
foo→.shareGive the value from foo, then share that valueshared[]
new Foo().shareShare a newly created valueshared[]

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:

simple_borrow [src]
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:

type_expr::share place [src]
(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:

access_ty::share [src]
(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:

VariableType
selfgiven Main
fooFoo
barshared[foo] Foo

Sharing foo.i must be compatible with every live variable’s type. The judgment env_permits_access performs these checks:

env_permits_access::env_permits_access [src]
(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:

Lien [src]
#[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:

liens::perm-shared [src]
----------------------------------- ("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:

lien_permit_access::shared [src]
(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 [src]
shared_place_permits_access(shared_place: Place, access: Access, accessed_place: Place,) => ()

The three rules permit different accesses:

  • share-share allows sharing any place. Reads are compatible with reads.
  • share-mutation allows mutable access or dropping only when the accessed place is disjoint from the shared place.
  • share-give allows 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:

mutation_through_ref_is_error [src]
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:

giving_field_while_refd_is_error [src]
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:

liveness_cancels_restrictions [src]
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 [src]
mut_place_permits_access(leased_place: Place, access: Access, accessed_place: Place,) => ()
  • lease-mutation permits sharing, mutable access, or dropping only for places disjoint from the leased place.
  • lease-give permits giving places disjoint from or a prefix of the leased place, preserving dependencies when a prefix moves.

This example fails:

mut_borrow_blocks_read [src]
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:

disjoint_access_is_fine [src]
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:

transitive_restrictions [src]
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 typesgiven[d1, d2] is mut?
![source1] Wrapper, ![source2] WrapperYes
![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 mutNo

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.

Property source and tests

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:

ViewSatisfies shared?Satisfies mut?
shared[source], where source is uniquely ownedYesNo
shared[lease], where lease: ![source] WrapperYesNo
shared[lease.field], through a mutable container leaseYesNo
shared ![source], after cancelling a dead intermediate leaseYesNo

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.

Property source and tests

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.

Property source and tests

Access constraints

AccessPermissionLienPermits sharing the origin?Permits mutating the origin?
place or place.shareshared[place]Lien::Share(place)YesNo
place!![place]Lien::Mt(place)NoNo

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.

Property source and tests

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.

Property source and tests

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.

Property source and tests

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.

Property source and tests

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:

subtyping_given_invisible [src]
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:

subtyping_ref_composition_given [src]
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_as::type_expr_as [src]
(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 = expr checks that the expression’s type is a subtype of T.
  • 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:

sub::sub-classes [src]
(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:

subtyping_different_classes_fail [src]
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:

RedLinkSource permissionMeaning
(empty chain)givenUnique ownership
SharedsharedShared 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] (where d is live) → one chain: [ShareLive(d)]. A single place-sharing link.

  • ![d] (where d is live) → 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:

subtyping_field_through_ref [src]
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:

subtyping_ref_shared_absorbs [src]
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:

subtyping_ref_through_mut [src]
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:

sub_perms::sub_red_perms [src]
(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) => ())
  1. Reduce both permissions to RedPerms
  2. For every chain in the subtype’s RedPerm, find a matching chain in the supertype’s RedPerm

“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:

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:

subtyping_perm_erasure_ref_int [src]
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:

subtyping_perm_erasure_int_to_ref [src]
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:

sub::sub-shared-classes [src]
(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:

subtyping_shared_class_copy_params [src]
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:

subtyping_non_copy_params_block_erasure [src]
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:

  1. Decompose each type into permission + base type
  2. Reduce each permission to a RedPerm (a set of RedChains)
  3. 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.

Property source and tests

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:

place_ordering_ref_subplace [src]
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:

place_ordering_mut_subplace [src]
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:

place_ordering_reverse_fails [src]
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:

red_chain_sub_chain::(shared[place]::P) vs (shared[place]::P) [src]
(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:

red_chain_sub_chain::(mut::P) vs (mut::P) [src]
(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:

place_ordering_set_subset [src]
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:

place_ordering_dropping_source_fails [src]
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:

place_ordering_both_dimensions [src]
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:

place_ordering_both_dimensions_mut [src]
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 aType of bDuplicate x: given[a, b] Data?
shared Datashared DataYes
shared Datagiven DataNo
given Datashared DataNo
given Datagiven DataNo

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 originsDuplicate?
shared[source1] Data, shared[source2] DataYes
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.

Property source and tests

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:

copy_perm_shared_subtype_ref [src]
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:

copy_perm_ref_not_subtype_shared [src]
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:

copy_perm_shared_subtype_shared_mut [src]
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:

copy_perm_ref_subtype_shared_mut [src]
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:

red_chain_sub_chain::(shared[place]::P) vs (shared[]::mut::P) [src]
(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:

copy_perm_shared_mut_not_subtype_ref [src]
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:

copy_perm_ref_shared_absorbs [src]
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:

copy_perm_ref_mut_composes [src]
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:

copy_perm_mut_not_subtype_ref [src]
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:

copy_perm_given_not_subtype_shared [src]
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:

SubSuperHolds?Why
givengivenYesSame permission
sharedsharedYesSame permission
givensharedNoCan’t pretend unique is shared
sharedgivenNoCan’t pretend shared is unique
sharedshared[d]YesIndependent ownership satisfies a place dependency
shared[d]sharedNoA place dependency cannot become ownership
shared[d1]shared[d1, d2]YesFewer sources = more specific
shared[d1, d2]shared[d1]NoCan’t drop a possible origin
shared[d]shared ![d]YesSharing the place is stronger than sharing a lease
shared ![d]shared[d]NoShared 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:

PermissionCopy?Owned?Restricts environment?
sharedyesyesno
shared[d]yesnod cannot be modified
shared ![d]yesnod 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:

liveness_dead_mut_cancels [src]
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:

  1. d is created with type given Data
  2. p: ![d] Data – a mutable lease of d
  3. q: ![p] Data – a mutable lease of p (a re-borrow)
  4. r: ![d] Data – we want q→ 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:

liveness_live_mut_no_cancel [src]
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:

red_chain_sub_chain::(mut-dead::P) vs Q ~~> (P) vs Q [src]
(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:

  1. The place must be dead (encoded by the Mtd variant)
  2. The type of the dead place must be shareable – prove_is_struct(env.place_ty(place_dead))
  3. 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

red_chain_sub_chain::(shared-dead[place]::P) vs Q ~~> (shared[]::P) vs Q [src]
(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:

liveness_dead_ref_promotes [src]
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:

liveness_live_ref_no_promote [src]
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:

liveness_return_cancels [src]
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):

liveness_ref_shared_no_cancel [src]
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:

liveness_both_places_dead_cancels [src]
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:

liveness_all_places_must_be_dead [src]
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

OperationApplies toResultConditions
CancellationMtd(place)Drop the linkPlace dead, type shareable, tail is mut
PromotionShareDead(place)Replace with SharedPlace 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:

interp_point_example [src]
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:

Alloc [src]
/// 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:

Word [src]
/// 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:

Flags [src]
/// 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:

Pointer [src]
/// 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:

TypedValue [src]
/// 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:

StackFrame [src]
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:

Interpreter [src]
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:

interp_arithmetic [src]
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:

interp_method_calls [src]
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:

PermissionBehavior
Unique ownershipTransfer ownership and uninitialize the source
Independent shared ownershipDuplicate; increment refcounts of owning boxed handles
Sharing from a placeDuplicate without gaining ownership of the origin
Mutable leasePreserve mutable access through a lease indirection

Giving uniquely owned data transfers it:

interp_give_given [src]
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:

interp_give_shared [src]
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 flagsResult
GivenSharedPlace; no ownership transfer or refcount increment
SharedOwnedSharedOwned; increment the refcount
SharedPlaceSharedPlace; no refcount increment

Sharing a uniquely owned place leaves the original usable:

interp_ref_given [src]
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:

interp_ref_shared [src]
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:

interp_share_recursive [src]
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 permissionBehavior
Unique ownershipRun cleanup, drop owned fields, and uninitialize
Independent shared ownershipRelease owning handles, decrementing refcounts
Sharing from a place or a mutable leaseLeave the origin’s data intact

Dropping a place-dependent shared view does not drop its origin:

interp_drop_borrowed_noop [src]
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:

interp_conditional_true [src]
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)]"#]]
);
interp_conditional_false [src]
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 for n initially uninitialized elements.
  • array_write[T, P](a, i, v) writes an element through mutable permission P.
  • array_give[T, P, Q](a, i) gives an element with permission P through array permission Q.
  • array_drop[T, P, Q](a, from, to) drops a range of elements through array permission Q, with element permission P.
  • array_capacity[T, P](a) returns the capacity through array permission P.

The program supplies the generic arguments explicitly. For example, array_write[Int, ![a]](a!, 0, 10) writes through a mutable lease of a.

interp_array_new_and_get [src]
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![[r#"
        Output: Trace: enter Main.main
        Output: Trace:   let _1_a = array_new [Int](3) ;
        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:

interp_array_int_is_copy [src]
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![[r#"
        Output: Trace: enter Main.main
        Output: Trace:   let _1_a = array_new [Int](1) ;
        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:

interp_array_class_shared_no_move [src]
// 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![[r#"
        Output: Trace: enter Main.main
        Output: Trace:   let _1_a = array_new [Data](1) ;
        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:

interp_array_class_elements [src]
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![[r#"
        Output: Trace: enter Main.main
        Output: Trace:   let _1_a = array_new [Data](2) ;
        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:

interp_array_shared_refcount [src]
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![[r#"
        Output: Trace: enter Main.main
        Output: Trace:   let _1_a = array_new [Int](2) ;
        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_shared changes ownership flags during value sharing.
  • and_copy_shared_fields accounts for duplication of owning boxed handles.
  • and_share_fields_owned_elsewhere handles place sharing: it produces SharedPlace from unique handles, but increments the count when duplicating an existing SharedOwned handle.

Reference counts track owning handles, not every shared access to a place.

Uniquely owned arrays

Without value sharing, giving an array transfers its ownership:

interp_array_given_move [src]
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![[r#"
        Output: Trace: enter Main.main
        Output: Trace:   let _1_a = array_new [Int](2) ;
        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:

interp_array_drop_frees [src]
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![[r#"
        Output: Trace: enter Main.main
        Output: Trace:   let _1_a = array_new [Data](2) ;
        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 returns given.

  • 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 from from..to (exclusive) in a way that depends on the permission P. If from >= to, this is a no-op.

    • If P is given (i.e., prove_is_given(P) — the permission alone, not P T), then the value is dropped.
    • Else this is a no-op.
    • Note: the dispatch checks P, not P T. Even if T is a copy type (e.g., a shared class), P = given means “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.
  • 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 at index. The behavior is determined by composing P with the element’s runtime flags — not by classifying the static type P T. The interpreter translates P into an owner_operms (given→Given, mut→MutRef, shared→Shared, ref→Borrowed), then calls object_value_to_data on the element with type T and that owner_operms. For boxed elements, the runtime Flags word is read and composed via with_projection_flags: runtime Shared always wins (producing a shared copy with rc++), runtime Given passes through the owner_operms. The result type is P 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, the MutRef points 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 typed ref[x] T. When array_give accesses such an element with P = 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 earlier P is shared ↔ A is shared assertion 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.F where P is an accessible place of type class and F is a field
  • a field P[i] where P is an accessible place of type tuple and i is a tuple index

Note that elements of arrays are not accessible places.

Definition: whole place. An accessible place P is a whole place if

  • P and all accessible places that extend P are 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 a ref to the array. Normal safe code cannot modify memory through ref.
  • array_give[Data, mut[a], ref[a]](a.ref, 0) — produces a mut[a] Data (a mutable reference to an element) through only a ref to the array. Normal safe code cannot obtain mut access through ref. The returned mut ref 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 to given_from[a]? Only when the field b is declared with given permission (or no permission prefix). The Mv expansion rule in redperms.rs replaces given_from[place] with the permission of place. So given_from[a.b] reduces to the permission of a.b, which composes the permission of a with the declared permission of field b. If a: mut[x] Foo and b: shared Bar, then a.b has permission shared (mut applied to shared = shared), so given_from[a.b] ≠ given_from[a] (which would be mut[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. Current array_set already has “ignore previous value” semantics.
  • Rename given_from → given — skipped. The parser prefix ambiguity between given and given_from[...] is unresolved and not worth the risk. Keeping given_from[places] as-is.
  • Remove Flags::Dropped — replaced all uses of Flags::Dropped with Word::Uninitialized. Removed Dropped from the Flags enum. Added try_read_flags() helper that returns Option<Flags> (None for uninitialized, Some(flags) for live values). Callers now check for Word::Uninitialized before calling expect_flags(). Error messages are “access of uninitialized value” uniformly. Note: and_drop_fields still 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 pred syntax — flipped both Predicate::Parameter and Predicate::Variance grammar from #[grammar($v0($v1))] to #[grammar($v1 is $v0)]. All predicates now use consistent param is pred syntax (e.g., P is mut, T is relative, T is atomic). Added is to KEYWORDS. Updated all test programs and where clauses. 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, A parameters to array_give — array_give[T, P, A](array, index). No grammar annotation change needed — $[v0] already parses a Vec<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 against A Array[T], return P T.
  • Add P, A parameters to array_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 against A Array[T] (no mut requirement — loosened from current mut).
  • Add A parameter to array_write — array_write[T, A](array, index, value). Same — no grammar annotation change. Type system: require A is mut via prove_is_mut(A), check array expression against A Array[T].
  • Add A parameter to array_capacity — array_capacity[T, A](array). Same — no grammar annotation change. Type system: check array expression against A 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 explicit P = given
  • array_drop_element, array_drop_class_element — should keep drop semantics with P = given
  • array_capacity_given, array_capacity_shared, array_capacity_ref — should all work with A is ref

Phase 3: Poly-permission semantics

Implement dispatch on P for array_give and array_drop. Add range semantics to array_drop.

  • array_give dispatches on P + runtime flags — The interpreter translates P into owner_operms via perm_to_operms(P), then calls the standard 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 overrides to Shared, runtime Given passes 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 to give_place which dispatches on the final operms. The earlier object_value_to_data_from_ty (which derived operms from the static type, ignoring runtime flags) was deleted. The P is shared ↔ A is shared assertion was invalidated by the subtyping scenario and removed.
  • array_drop dispatches on P — given → actually drop each element in range, else → no-op. Dispatch uses prove_is_given(P) (the permission alone, not P T). Even copy types like shared class are dropped when P=given — needed to avoid leaking refcounts on boxed fields inside shared classes.
  • array_drop range semantics — changed grammar from (array, index) to (array, from, to), drops elements in from..to range (exclusive) in forward order. from >= to is a no-op. All existing single-index array_drop(a, i) calls rewritten to array_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 a mut[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_drop with from >= to is a no-op ✅

  • array_drop_shared_class_element_is_noop — shared class (Pt) elements: array_drop[Pt, given, ...] is a no-op since given Pt is shared ✅

  • array_give_ref_of_shared_is_shared — P = ref[shared_place] where the place is shared. The type system normalizes ref[shared_place] to shared before substitution, so P arrives as shared and 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_copy already used P = shared explicitly after Phase 3. Verified refcount lifecycle. No change needed.

  • Fix ref-array test intent — ref_array_give_int_element, ref_array_give_class_element updated to use P = ref[a] explicitly. ref_array_of_shared_arrays updated to use element type shared Array[Int] (matching test name) with P = ref[outer]. Key behavioral changes: ref_array_give_class_element now correctly shows d = ref [a] Data (borrowed copy, element stays initialized); ref_array_of_shared_arrays correctly shows got = shared Array { ... } (shared copy via runtime flags).

  • Runtime-vs-static mismatch test — array_give_ref_of_runtime_shared_element: stores a shared array into a ref[dummy] Array[Int]-typed slot, gives with P = 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 of object_value_to_data_from_ty and the switch to runtime-flag-based dispatch.

  • Verify “freed” test snapshots — refcount_reaches_zero_frees_allocation and shared_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_drop on some or all elements, then drop the array. Uses Array[Array[Int]] so inner arrays are boxed with separate heap allocations that survive the outer’s scrub. Flat element types (like class 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 — added DropBody enum (None | Block(Vec<Statement>)) with Default derive to ClassDeclBoundData. Grammar: drop { stmts } after methods. Updated all destructuring sites. Added 3 parser tests.

4b: Type checker ✅

  • Type-check drop body — added check_drop_body judgment to classes.rs. For given class: type-checks with self: given Class[...]. For class (share) and shared class: introduces a universal perm variable P with P is shared assumed, then type-checks with self: P Class[...]. This means the drop body can read fields (via .ref or .give which copies) but cannot mutate or move fields. Added open_universal_perm_var() helper to Env. 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].give because Projection::Index is for tuples only. Added test array_index_not_accessible_place. Note: formality-core parses kind keywords as ty and perm (not type and perm), so generic class tests must use [ty T] not [type T].

4c: Interpreter ✅

  • Bool type and operators — added Bool to TypeName (shared class, always copyable, 1 word, Word::Int representation). Added true/false as Expr variants with KEYWORDS. Added BinaryOp enum (Add, Sub, Ge, Le, Eq, Ne) with a single Expr::BinaryOp(lhs, op, rhs) variant. Type rules grouped into “arithmetic” (Int→Int) and “comparison” (Int→Bool). Changed Expr::If condition from Int to Bool. Updated 5 existing tests. Note: bare > and < omitted due to parser prefix ambiguity with >=/<= in formality-core; the restricted set is sufficient.
  • is_last_ref intrinsic — added is_last_ref[perm A](value: A T) -> Bool as Expr::IsLastRef. Type system accepts any value, returns Bool. Interpreter: for boxed types returns refcount == 1, for non-boxed types returns false.
  • Execute drop body — drop_value checks 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 via is_value_whole). Drop body runs BEFORE field-by-field cleanup. self type: given class → self: given Class[...], else → self: ref[magic] Class[...] using synthetic Var::Magic. Fixed drop_place for flat types to route through drop_value so drop body fires on explicit .drop. Added Access::Drop type rule.
  • Whole-place drop — implemented as is_value_whole check inside drop_value rather than as a separate end-of-scope mechanism. For flat types, checks all words for Uninitialized. For boxed types, checks flags word. Partially-moved classes: drop body is skipped, but traverse_value + and_drop_fields still cleans up each field individually (uninitialized fields are skipped by try_read_flags returning None). This simpler approach works because and_drop_fields already handles uninitialized boxed fields gracefully.
  • Array elements are not accessible places — already implemented (find_object_fields returns 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 with drop { print(self.x) }, verify drop body runs on scope exit
  • drop_body_self_not_whole — class with drop body that moves one field; verify remaining fields are individually dropped, no infinite recursion
  • partially_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 pattern Iterator.drop relies on (self.vec.data.give then self.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 — Vec class with drop { array_drop[T, given, ref[self]](self.data.ref, 0, self.len.give) }, verify elements are dropped when vec goes out of scope
  • shared_class_drop_gets_ref_self — shared class with drop body, verify self: ref Class
  • drop_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_ref returns true
  • is_last_ref_false_when_shared — boxed object with two handles, is_last_ref returns 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_get test (was ignored, used outdated syntax). Fresh test vec_push_and_get_given uses the target signatures from the design doc. Also vec_push_increments_len for basic push. All pass end-to-end.
  • Vec iter and next — vec_iter_and_next tests consuming iteration: creates Vec, pushes 3 items, creates iterator, calls next() once. Iterator.drop cleans up remaining elements (prints 20, 30). Verified elements moved out and cleanup correct.
  • Shared Vec access — shared_vec_get with P = shared: elements are shared copies, array_drop is no-op, Vec.drop with is_last_ref only cleans up on final handle.
  • Ref Vec access — ref_vec_get with P = 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_ref true, 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:

  1. call_method double-wrapped this_ty: The method’s this_decl.perm was 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 type mut[v] Vec[T], but call_method added another mut[v] on top → mut[v] mut[v] Vec[T]. Fixed by using this.ty directly.

  2. is_mut_ref_type used prove_is_mut which failed on out-of-scope places: Inside a method, prove_is_mut(env, mut[v] Vec[T]) tries to resolve place v in the method’s env, but v is from the calling scope. Changed to structural pattern matching: matches!(ty, Ty::ApplyPerm(Perm::Mt(_), inner)) && !is_shared_type(inner). The !is_shared_type guard is needed because mut[x] Int is NOT stored as a MutRef — copy types are always inline.

  3. give_place with MutRef operms on copy types: When accessing self.start.give through a mut ref (Iterator.next), the operms were MutRef but the field type was Int (copy). give_place blindly 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_type with prove_is_mut — The interpreter’s is_mut_ref_type uses structural pattern matching (Ty::ApplyPerm(Perm::Mt(_), inner) where inner is not copy) instead of the type system’s prove_is_mut judgment. This divergence exists because prove_is_mut on Perm::Mt(places) resolves each place’s type via env.place_ty(place), but inside a method body the places (e.g., v in mut[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 to prove_mut_predicate that recognizes Perm::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 use assert_interpret_only! (interpreter-only, no type checking) because the type checker doesn’t yet support the permission patterns Vec uses (generic perm P self, given_from[self] return types, where-clause dispatch). As the type checker gains support for these features, migrate tests to assert_interpret! (type-check AND execute). Only keep assert_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_drop uninitializes element slots through A 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 type T (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 length
  • ArrayCapacity[T](array: Array[T]) -> uint, returns the capacity that the array was created with
  • ArrayGive[T](array: Array[T], index) -> given[array] T, gets an element from the array
  • ArrayDrop[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 → 1
  • Tuple(0) (i.e., ()) → 0
  • A class → 1 (for the flags word if unique, 0 if shared) + sum of size_of for 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.give
  • place.ref
  • place.mut
  • place.drop

Each begins by evaluating the place which results in a Perm and a Pointer:

  • the Perm represents the most restrictive we have passed through. If at any point we access an uninitialized flags the interpreter faults.
  • the Pointer identifiers 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:

  • give examines the Flags
    • Given => copy the fields to the destination and then mark the Flags as Uninitialized
    • Shared => copy the fields to the destination, set the flags to Shared, and then apply the share operation to them (see below)
    • Borrowed => copy the fields to the destination, set the flags to Borrowed
    • Mut => create a MutRef with the pointer
  • ref examines the Flags
    • Shared => copy the fields to the destination, set the flags to Shared, and then apply the share operation to them (see below)
    • Given | Borrowed | Mut => copy the fields to the destination, set the flags to Borrowed
  • mut examines the Flags
    • Shared | Borrowed => fault
    • Given | Mut => create a MutRef value
  • drop examines the Flags
    • Given => drop fields recursively
    • Shared => 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 to Shared and apply the share operation to the fields
  • If the flags are Shared or Borrowed, 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.

There are two distinct operations that involve sharing:

  1. convert_to_shared — in-place conversion from Given to Shared ownership. Called by Expr::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.

  2. share_op — duplication accounting. Called when a Shared value is copied (by place.give or place.ref on 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

  1. ArrayNew — allocates [Int(1), Int(length), elements...]. Refcount starts at 1.
  2. value.share — flips flags Given→Shared via convert_to_shared. Refcount stays 1.
  3. place.give on Shared — copies the value, calls share_op which increments refcount. Each additional copy adds 1.
  4. 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:

  1. Write/update mdbook chapter describing the feature or change
  2. Write tests (interpreter tests using assert_interpret!, type system tests using assert_ok!/assert_err!) that express the expected behavior
  3. Implement until the tests pass

The mdbook chapters to write/update:

  • md/interpreter.md (existing) — describes the Alloc/Word/Pointer/Flags/TypedValue memory model, with word-level walkthrough and access mode table.
  • md/wip/unsafe.md (this doc) — eventually becomes a real chapter covering Array[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 memory
  • Word { Int, Flags, Uninitialized } — individual memory words
  • Flags { Uninitialized, Given, Shared, Borrowed } — permission flags for unique objects
  • Pointer { index, offset } — position within an allocation
  • TypedValue { 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.md into 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 parameter T)
  • 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 word
    • ArraySet[T](array, index, value) — write element at computed offset
    • ArrayGive[T](array, index) — read element via give semantics
    • ArrayDrop[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.