Shared permissions
Some permissions are shared.
Any shared permission can be duplicated.
This is expressed by the predicate P is shared, which includes sharing from
places as well as independent shared ownership.
Here are three examples of shared permissions in Dada,
and understanding how they relate to each other
is key to understanding permission comparison.
Examples of shared permissions
shared, also written shared[], means independent shared ownership.
Such a value can be duplicated freely
and lives as long as any copy exists.
It places no restrictions on the environment.
shared[d] means sharing from the place d.
It can be duplicated freely, but depends on d.
While the shared result is live, d cannot be modified.
shared ![d] – a composed permission.
This is the result of sharing a lease:
you take a mutable lease ![d]
and share the resulting value, for example with lease→.share.
The result is shared (because the outer shared makes it so),
but it still restricts d
(because the underlying lease is active).
Giving from alternative origins: duplication requires shared origins
For an ordinary non-shared struct, a value with permission
given[p1, ..., pn] may be duplicated only if every possible originating
place has a type satisfying the shared predicate.
An origin is a place listed in given: x: given[a, b] Data
means that x could have been given from a or from b. These are alternative
origins of one value, not two values stored in x. Giving a shared value can
duplicate it; giving a uniquely owned value transfers ownership. Uncertainty
about which occurred cannot grant permission to duplicate a unique value.
For struct Data {}, the examples are:
Type of a | Type of b | Duplicate x: given[a, b] Data? |
|---|---|---|
shared Data | shared Data | Yes |
shared Data | given Data | No |
given Data | shared Data | No |
given Data | given Data | No |
Duplication here means using x→ twice. The first give must preserve x
for the second; finding just one shared alternative does not justify that.
Origins can also be field places: given[d1.field, d2.field] Data, or
nested places such as d1.inner.field. The type of the complete place
matters. A unique container can hold a declared shared Data field;
conversely, accessing a Data field through a shared container is shared
even though its declaration does not say shared. The same four-way table
applies to those effective field types, including nested projections.
SharedPlace origins
A share also satisfies shared, even though it is borrowed rather than owned.
For example, with d1: shared[source1] Data and d2: shared[source2] Data, a value
x: given[d1, d2] Data can be given twice. Here d1 and d2 are the
possible origins; source1 and source2 are the referents those origins borrow.
| Types of the two origins | Duplicate? |
|---|---|
shared[source1] Data, shared[source2] Data | Yes |
shared[source1] Data, shared Data (either order) | Yes |
shared[source1] Data, given Data (either order) | No |
shared[source1] Data, ![source2] Data (either order) | No |
These cases also work with projected origins, both when a reference is stored
in a field of a unique container and when a field is accessed through a borrowed
container. The distinction matters: the origin may be d1.field, while the
reference dependency leads to a separate source1.
The separate given_from_preserves_origin_dependencies property documents
the borrowing restrictions retained by surviving duplicates.
Candidate lemma
Let C be an ordinary non-generic class that is not itself shared. In a
well-formed environment, for a nonempty list of valid places p1, ..., pn,
proving given[p1, ..., pn] C is shared requires proving that the type
of every pi satisfies shared. In particular, one uniquely owned C
alternative prevents duplication, regardless of its position in the list.
This is a candidate formulation, not a proved theorem. The tests exercise two
origins of an empty ordinary class, using concrete given, shared, share, and mut
permissions. They cover both mixed orders, both uniform cases, and initialized
locals as well as parameters with alternative origins. Field and nested-field
matrices cover declared field permissions and permissions inherited from the
container. Each matrix case first verifies that giving once is permitted,
then checks whether giving twice succeeds or fails specifically at the give.
Scope
This property concerns duplication of given values, not every predicate
or every permission constructor. shared is the predicate for duplicability;
it does not require full ownership. The tests cover owned and borrowed shared origins.
Types such as Int are independently duplicable and are outside the class
assumption above. Mutation through alternative origins is a separate property.
How they relate
These three form a subtyping chain:
shared <: shared[d] <: shared ![d]
Each step adds more restrictions while remaining shared.
shared <: shared[d]
An independently shared value can stand in wherever sharing from d is expected.
Giving an owned shared copy is safe –
they get what they need (read access),
and the extra restriction on d
(not modifying it while the shared result is live)
is harmlessly conservative:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) {
let s: shared Data = new Data().share;
let r: shared[d] Data = s→;
();
}
}
"#
);
The value s has type shared Data.
The target r expects shared[d] Data.
Since shared <: shared[d], this works.
shared[d] is NOT <: shared
The reverse doesn’t hold – a place dependency cannot become independent ownership:
crate::assert_err!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) {
let r: shared[d] Data = d.share;
let s: shared Data = r→;
();
}
}
"#,
expect_test::expect!["judgment had no applicable rules: `check_program { program: struct Data { } struct Main { fn test (given self d : given Data) → () { let r : shared [d] Data = d . share ; let s : shared Data = r → ; () ; } } }`"]
);
shared[d] </: shared –
the shared value depends on d being available.
A shared value makes no such assumption.
If we allowed this,
the “shared” value could outlive d.
shared <: shared ![d]
A shared value can also stand in for a shared lease.
The shared lease restricts d;
a shared value doesn’t need d at all,
so the restriction is harmlessly extra:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) {
let s: shared Data = new Data().share;
let r: shared ![d] Data = s→;
();
}
}
"#
);
shared[d] <: shared ![d]
Sharing from a place can stand in for a shared lease from the same place:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) {
let r: shared[d] Data = d.share;
let sm: shared ![d] Data = r→;
();
}
}
"#
);
Both shared[d] and shared ![d] are shared
and both restrict d.
The difference is what they say about the object –
shared[d] grants read access to the object,
while shared ![d] allows the possibility
that another ![d] holder could mutate the object.
Since sharing the place provides a stronger guarantee,
it’s a subtype.
The chain comparison rule for this is:
(if place_b.is_prefix_of(place_a))
(red_chain_sub_chain(env, tail_a, tail_b) => ())
--- ("(shared[place]::P) vs (shared[]::mut::P)")
(red_chain_sub_chain(
env,
Head(RedLink::ShareLive(place_a) | RedLink::ShareDead(place_a), Tail(tail_a)),
Head(RedLink::Shared, Head(RedLink::Mtl(place_b) | RedLink::Mtd(place_b), Tail(tail_b))),
) => ())
shared ![d] is NOT <: shared[d]
The reverse fails:
crate::assert_err!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) {
let p: ![d] Data = d!;
let sm: shared ![d] Data = p.share;
let r: shared[d] Data = sm→;
();
}
}
"#,
expect_test::expect!["judgment had no applicable rules: `check_program { program: struct Data { } struct Main { fn test (given self d : given Data) → () { let p : ! [d] Data = d ! ; let sm : shared ! [d] Data = p . share ; let r : shared [d] Data = sm → ; () ; } } }`"]
);
shared ![d] </: shared[d] –
a shared lease can coexist with mutation of the object,
while direct sharing from the place cannot.
Treating a shared lease as direct sharing
would falsely promise immutability.
How composition works
Permissions compose with Perm::Apply –
written as P Q in the grammar,
meaning “apply permission P to something with permission Q.”
The result depends on whether the inner permission is shared.
Shared permissions absorb: shared[p] shared == shared
When you share a place containing independently shared data, the place dependency is redundant:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self) {
let d: shared Data = new Data().share;
let r = d.share;
let s: shared Data = r→;
();
}
}
"#
);
The expression d.share has type shared[d] shared Data.
But d has type shared Data,
so the composed permission shared[d] shared
reduces to just shared –
the result remains independently shared.
Internally, this is the append_chain rule:
when the right-hand side of a composition is shared,
the left-hand side is discarded.
The inner shared permission determines the resulting access.
Non-shared composes: shared[p] ![d]
When the inner permission is not shared, composition creates a genuine chain. Sharing a place containing a lease retains the lease dependency:
crate::assert_ok!(
r#"
struct Data { }
struct Main {
fn test(given self) {
let d: given Data = new Data();
let p: ![d] Data = d!;
let q: shared[p] ![d] Data = p.share;
();
}
}
"#
);
Here p.share creates shared[p] ![d] Data –
a chain of two links.
The permission records that you shared the place p,
which itself was leased from d.
What happens when you want to use this value
depends on whether p is still alive –
the Liveness and cancellation chapter
explains how dead links are resolved during comparison.
![d] is not shared
A mutable lease ![d] is not shared –
it provides exclusive mutable access,
which can’t be duplicated:
crate::assert_err!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) {
let p: ![d] Data = d!;
let q: shared[d] Data = p→;
();
}
}
"#,
expect_test::expect!["judgment had no applicable rules: `check_program { program: struct Data { } struct Main { fn test (given self d : given Data) → () { let p : ! [d] Data = d ! ; let q : shared [d] Data = p → ; () ; } } }`"]
);
![d] </: shared[d] –
a lease grants exclusive mutation rights,
while sharing the place only grants read access.
These are incomparable: neither is a subtype of the other.
Similarly, given (unique ownership) is not comparable
to any of the shared permissions:
crate::assert_err!(
r#"
struct Data { }
struct Main {
fn test(given self, d: given Data) {
let s: shared Data = d→;
();
}
}
"#,
expect_test::expect!["judgment had no applicable rules: `check_program { program: struct Data { } struct Main { fn test (given self d : given Data) → () { let s : shared Data = d → ; () ; } } }`"]
);
given </: shared –
unique ownership and shared ownership
represent fundamentally different memory models.
The full permission landscape
Here’s how all the permissions relate:
| Sub | Super | Holds? | Why |
|---|---|---|---|
given | given | Yes | Same permission |
shared | shared | Yes | Same permission |
given | shared | No | Can’t pretend unique is shared |
shared | given | No | Can’t pretend shared is unique |
shared | shared[d] | Yes | Independent ownership satisfies a place dependency |
shared[d] | shared | No | A place dependency cannot become ownership |
shared[d1] | shared[d1, d2] | Yes | Fewer sources = more specific |
shared[d1, d2] | shared[d1] | No | Can’t drop a possible origin |
shared[d] | shared ![d] | Yes | Sharing the place is stronger than sharing a lease |
shared ![d] | shared[d] | No | Shared lease doesn’t guarantee immutability |
The shared permissions (shared, shared[d], shared ![d])
form a chain within this landscape.
The non-shared permissions (given, ![d]) are incomparable
with the shared permissions.
Summary
The shared permissions form a hierarchy:
| Permission | Copy? | Owned? | Restricts environment? |
|---|---|---|---|
shared | yes | yes | no |
shared[d] | yes | no | d cannot be modified |
shared ![d] | yes | no | d cannot be modified |
Subtyping: shared <: shared[d] <: shared ![d].
Composition: applying a permission to something shared just gives you the shared permission back. Applying a permission to something non-shared creates a genuine chain that requires further analysis to resolve.
The non-shared permissions (given, ![d])
sit outside this hierarchy –
they are incomparable with the shared permissions.