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

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.