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

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