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

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