Static Permissions

Note: The recover block is not implemented, so a permission transition cannot be undone that way, and an externally-isolated graph cannot be built with one. Nor can a uni reference be kept through a call of a pure method, since pure functions are not implemented. Seeing through a field of a different permission is refused only for a uni field: a &uni reference to a Car can read what its mut field points at. Nor is the permanent transition of a uni reference enforced as the example of a permanent transition below shows it: assigned to a &mut i32 variable, the reference is borrowed, not moved, and the source stays usable; only a transition to an owning type, Rc[mut, i32], consumes it.

Every reference's type specifies a permission which controls what may, and may not, be done with that reference. Permissions affect such capabilities as the reference's right to view (or modify) the value it points to, create multiple copies of that reference, and use locks or atomics for synchronizing access to the reference's value.

The primary purpose of permissions is to improve program safety by preventing data races, where multiple concurrent threads step on each other when trying to access the same value. Each permission uses a different strategy to make it impossible for multiple threads to perform lifetime-overlapping atomic transactions on the same value.

Prudent use of permissions can also help make code easier to understand and improve execution performance.

There are two kinds of permissions:

• Static. The safety guarantees for static permissions are enforced entirely by the compiler. This means there is no runtime overhead to use static permissions. Static permissions facilitate permission transitions, as described later. Each is a keyword, written in lower case: uni, mut.
• Lock. The safety guarantees for locked permissions are enforced by a combination of compiler and runtime (lock) mechanisms. To access the value pointed at by a locked reference, one must first acquire the lock. This is done by borrowing a reference. Only region-managed references can specify a lock permission. Each is a library type, named as types are, its first letter alone capitalized: Arc[Mutex, T], Arc[Rwlock, T], Rc[Rwcell, T].

This page focuses only on static permissions. Lock permissions are discussed later.

List of Permissions#

There are only six static permissions:

uni

The uni (unique) permission is quite versatile. It may be used to view or mutate the value it points to. It may hop safely from thread to thread without any runtime penalty, making it the fastest way to move mutable data from one thread to another.

The name, "unique", signals its one restriction: there can only be one active reference to its value at a time. Because of this, its use is governed by move semantics. The reference may be moved to another variable, function, or thread, but doing so makes it inaccessible at its former home.

uni is ideal when we start off only needing one reference to a value (or isolated graph). It allows us to safely move a value's reference around between scopes and threads. Later we can transition it to shared mutable or immutable. Performance optimization benefits may also result from knowing the reference is unique.

imm

The imm (immutable) permission declares that a reference's value will never change. Multiple references may point to the same immutable value, even across multiple threads. An imm reference may view its value, but not alter it.

mut

The mut (mutable) permission allows multiple references to freely access or change the same value at any time. However, all references to the same value are restricted to a single thread.

A mut reference may store another variant over an enum's value. A reference narrowed into one of its variants is refused if that could happen while it is used (Match).

mut1

The mut1 permission, like mut, may read and change its value, and may be copied. It differs in one way: a reference into the payload of an enum's variant taken through it is never asked whether another name could change the variant, as through uni and imm, since nothing else can (Match). Like mut, its references stay on one thread, and it is refused on a type that never changes.

ro

A ro (readonly) reference may read, but not modify, the value it points to. This may sound like imm, but it is not the same. imm guarantees that no other mutable reference to the same object exists, making it safe to share between threads. ro makes no such guarantee. Therefore, ro references cannot be safely shared with another thread, a borrow that lasts the whole program included: of the borrows, only imm, opaq and uni ones may cross to another thread, and only that long (Race condition safety).

The primary use for ro rests in how it allows a function to take in a reference of nearly any permission, simply by promising not to change the value the reference points at. This polymorphic flexibility is why a borrowed reference's default permission is ro, if no permission is explicitly specified, except to a type that declares it never changes.

opaq

An opaq (opaque) reference may never be used to read or modify the value it points to. This restriction is useful for references to functions or opaque values, where it makes no sense to access the value they point to.

A Type That Never Changes: Immutable#

A type may declare that nothing ever changes it through a reference, with the marker Immutable, which a type declares and the compiler never grants: the body of text str declares it, and any struct may, struct Money is Immutable {..}. It has two effects, and they are separate.

• The default permission is imm. A reference to the type written with no permission is imm: &str is &imm str, a method's self & is &imm, and an owner in a region that copies, written without a permission, is imm too, so Rc[str] is Rc[imm, str] and its owners are copied, where Rc[T] of an ordinary type is uni and moves. imm may still be written, and so may ro and opaq. A borrow made with & from a place that cannot be borrowed as imm (a mut variable) is ro, as it is for any type.
• The permissions that write through a shared path are refused. mut, mut1 and a lock permission (Rc[Rwcell, str]) on the type are an error that names Immutable, so there is no &mut str. uni is not refused: it is the one holder's, a finalizer receives its self as &uni, and Rc[uni, str] is a unique owner that moves.

fn length(s &str) usize {..}          // s is &imm str
imm a = new Rc[str](view);            // Rc[imm, str]
imm b = a;                            // copied, not moved: a is still held
imm m &mut str = ..;                  // ** ILLEGAL! str is Immutable **

The marker is a promise the compiler holds a reference to, not a check of the type's own fields: a struct declaring it is trusted not to write its own fields through a uni or a variable's name.

Variable vs. Reference Permissions#

Initially, it may feel confusing, distinguishing the role of a permission on a reference vs. on a variable, particularly if the variable holds a reference. Quite simply, a variable's permission governs whether you can give the variable a new value. A reference's permission governs what you can do with the reference. These are separable concerns.

To illustrate this, consider these variations:

imm ref1 = &imm x;
imm ref2 = &mut x;
mut ref3 = &imm x;
mut ref4 = &mut x;

Because of the mut variable permission, ref3 and ref4 may be changed to hold a different reference. ref1 and ref2 cannot.

ref1 = &imm x;   // ** ILLEGAL! the ref1 variable cannot be changed **
ref2 = &mut x;   // ** ILLEGAL! the ref2 variable cannot be changed **
ref3 = &imm x;   // ok
ref4 = &mut x;   // ok

In contrast, because of the mut reference permission, the references in ref2 and ref4 may be changed to point to a different value. The values pointed to by ref1 and ref3 cannot be altered.

*ref1 = 5;   // ** ILLEGAL! The value pointed at by ref1 cannot be changed **
*ref2 = 5;   // ok
*ref3 = 5;   // ** ILLEGAL! The value pointed at by ref3 cannot be changed **
*ref4 = 5;   // ok

Permission Transitions#

A new copy of a reference typically has the same permission as the original reference, which is often necessary to preserve the reference's safety guarantees. In certain cases, however, we may safely create a reference copy carrying a different permission.

To 'ro'#

It is safe to borrow a ro reference from a reference of any permission other than opaq. This quality is what makes it attractive for functions to polymorphically accept ro references to any values they do not intend to modify.

From 'uni'#

At some point in the lifetime of a uni reference's value, one may need to transition to allowing multiple, shared references to that value. On a temporary basis (until the borrow's last use), this transition may be accomplished by using borrowed references.

Using borrowed references does make it possible to temporarily transition a uni reference to some shared reference permission. A mut borrowed reference is shared mutable, so its source becomes one more mut alias of the value while the borrow is still to be used: the source may be read, changed and borrowed again (any number of &mut borrows may be held at once), and only what needs the source unique is refused — moving it, sending it, lending it &uni or &imm, ending it (Freezing access to the source of a borrow). A &uni or &imm borrow, which promises more, freezes the source against reading and changing too. Once the borrowed references' last use is behind it, the original source is unique, and usable in every way again:

imm uniref = new So[i32](5);
imm bref1 &mut i32 = uniref;     // Coerce owning reference to a 'mut' borrowed reference
imm bref2 = bref1;               // Share with another borrowed reference
*uniref = 6;                     // Allowed: uniref is one more 'mut' alias while 'bref1' and 'bref2' are still to be used
consume(uniref);                 // Error, uniref may not be moved while 'bref1' and 'bref2' are still to be used (the same call is allowed below)
*bref2 = *bref1 + 1;             // The borrowed references' last use
consume(uniref);                 // Allowed, since the borrowed references are not used again

A source reached as uni is what a local variable is, and it is frozen as just described. A source reached through a shared mut or ro path, such as what a &mut parameter points at, is only kept alive while a borrow of it is still to be used (Freezing access to the source of a borrow). An owning reference coerced to a borrowed one, as in the example, freezes its source the same way. Coerced to a &uni, it is borrowed from too, not moved, and it is finalized at its own scope's end.

What such a borrow shares is the value the uni reference points to. A borrow of the uni reference itself keeps that reference's permission: it may not be seen as a borrow of a shared owning reference, because reading through it would copy out a second owner of a value promised unique.

fn share(b &Rc[mut, i32]) Rc[mut, i32] { *b; }
imm uniref = new Rc[i32](5);
imm other = share(&uniref);     // ** ILLEGAL! A borrowed Rc[i32] is not a borrowed Rc[mut, i32] **

It is also possible to permanently transition a uni reference to references holding shared permissions, such as mut or imm. This is accomplished by moving the `uni` reference value to a reference that holds a shared permission. The original uni reference is consumed (because of move semantics), leaving us with a new sharable reference, from which copies can be made.

imm ref = new Rc[i32](5);        // Allocate new value, return 'uni' reference
imm newref1 &mut i32 = ref;      // Move reference to newref with 'mut' permission
imm newref2 &mut i32 = newref1;  // Two 'mut' references to the same object
*newref2 = *newref1;             // Either reference may be used (but not ref any longer)

The transition of an region-managed reference from uni to a shared permission reference is normally a one way trip. Once this transition has happened, you cannot safely transition a mut reference back to a uni reference (or even to an imm reference). The reference is now "frozen" to the restrictions of its new permission: As mut, it can never be shared across threads. As imm, it can never be altered.

Shape-changing values under mut#

Some values can change shape. A resizable collection (a list, a dictionary, a string) may move all of its elements to a bigger block when it grows, and an enum may be given another variant. A borrow into one is a borrow into storage that such a change would leave dangling, or read as the wrong type. A mut reference is shared, so another name may make that change while the borrow is in use. The rule is the same for a collection and for an enum: an element borrowed through one, or a reference narrowed from an enum to one of its variants, is allowed, and is refused only if something could change the shape while the borrow is still to be used.

For a collection, a read-only borrow of an element of a local list holds the list against a change. The list may be read, but a push waits for the borrow's last use:

mut list = List[i32].empty();
list.push(10);
list.push(20);
imm first = list[0usize];     // borrows list, read-only
imm n = list.len();           // fine: the list may be read
list.push(30);                // **ERROR** first is used again below
print <- *first;

A mutable borrow of an element is one more alias of the elements. Until its last use the collection may still be read and written in place, but not reshaped by a push, a clear or a pop:

mut list = List[i32].empty();
list.push(10);
list.push(20);
imm e = &mut list[0usize];
imm n = list.len();           // fine: read while the mutable borrow is live
list.set(1usize, 5);          // fine: written in place
*e = 7;                       // the last use of e
list.push(30);                // fine: the borrow is over

This leaves the list holding 7, 5 and 30. A collection reached through a shared path is treated the same way: the borrow lets the path be read, lent and written as any alias does, and a change of the collection's shape, by the same name or another, is refused (why a push waits for a borrow of an element).

For an enum, nothing is frozen. Narrowing a reference into one of the enum's variants is allowed, and the fields of the variant may be written through it. What is refused is storing another variant over the enum, by the same name or another, or handing it to a call that might, while the narrowed reference is still to be used:

fn grow(s &mut Shape) {
  match s {
    case mut c Circle { c.radius = 2; }   // Ok: nothing changes the variant while c is used
    else {}
  }
}
fn restart(s &mut Shape) i32 {
  match s {
    case mut c Circle {
      c.radius = 2;
      *s = Shape.Rect(1, 2, 3);   // **ERROR** c is used again below
      c.radius;
    }
    else { 0; }
  }
}

The same store after the narrowed reference's last use is fine, which is how a state machine moves to its next state. Match and borrowed references say what is and is not refused.

Permission Recovery#

Permission transitions are not actually always a one-way trip. Under certain circumstances, it is possible to safely recover "lost" permissions.

• Borrowed reference recovery. Borrowing a reference temporarily transitions to a new permission. After the borrowed reference's last use, the original permission on the source reference is restored. So, a uni can be borrowed as mut or imm. After the borrowed references' last use, you once again have the original uni reference. Similarly, one can borrow as ro and get back the original reference's permission later. A borrowed &uni reference (or slice) passed where a borrowed reference is wanted — &, &imm, &mut or &uni, as an argument, a method's receiver or a variable's type — is recovered the same way: instead of handing over the reference itself, the call is lent a fresh, shorter borrow of it. The caller is frozen meanwhile, and has the reference, still unique, once that borrow's last use is behind it:

  fn peek(r &R) {..}
  fn bump(r &mut R) {..}
  fn twice(r &uni R) {
    peek(r);          // lends a fresh, shorter borrow: r is still ours
    bump(r);
    peek(r);
  }
  

• Pure method calls Sometimes it is polymorphically convenient to be able to call a method on an object where we have a uni reference, and we don't want the calling function to lose the object to the called method due to move semantics and we don't want to borrow. This is possible to do if the called method is pure, and no other arguments to the method call have mut or ro references.
• Recovery blocks With this feature, described below, it is possible to unwind a some permission transition that happens inside the block for any value returned by the block.

Recover Blocks#

The recover block is a helpful way to transition a permission backwards. Any mutable permission can be recovered as any permission. Similarly, any readonly permission can be recovered as any read-only permission or opaque. This is useful for many situations:

• Create some shared, mutable object inside the block and receive it back as a uni reference.
• Create a cyclic immutable data structure. Inside the block, create a shared, mutable data structure and then recover it as imm.
• Temporarily transition uni to mut, perform complex mutable operations on it and return it as uni again.
• Extract a mutable field from a uni and return it as an uni.

This example demonstrates the third scenario:

recover {
  imm ref1 = uniref as &mut i32;
  imm ref2 = ref1;
  *ref1 = 5;
  ref2 as &uni i32;
}

The recover block imposes several restrictions in order to ensure the reverse transition is safe:

• You have no access to any mut, ro or lock permission reference/object outside the recover block, whether local or global.
• Any functions you call must be pure.

These restrictions exist to stop unsafe references from leaking out of the recover block. Given that created reference aliases expire within the block, we know any returned reference is unique.

When struct fields are references#

There is a symbiotic, two-way relationship between the attributes of a composite type (like a struct) and the permissions on its field references:

• Permissions are infectious. When struct fields are references, the permissions of those references can infect the properties of the struct type.
• Viewpoint adaptation. Conversely, the permissions on some reference to the composite type can restrict the permissions we effectively get on any field's reference.

Let's go into detail on both these phenomena.

Permissions are infectious#

Let's say we define a new struct type with fields that are references:

struct Car {
  pub engine &uni Engine;
  pub owner &mut Person;
}

Since the engine field is a uni reference, move semantics apply not only to the engine field, but also to any value of type Car! If any part of a type has move semantics, the whole type does as well.

Similarly, since the owner field is a mut reference, that permission forbids the reference from being shared across multiple threads. If the field must remain thread-local, so must any Car value (or reference to a Car value). This principle applies to all the thread-local permissions: mut, ro and Rwcell.

Viewpoint Adaptation#

Using the example above, let's imagine we have a borrowed reference to a Car:

fn handleCar(car &Car) {
  if car.owner.age < 18 {
    car.owner.age = 18;         // illegal mutation
  }
}

Even though the car owner field is mutable, the reference we have to car is not. If we don't have permission to mutate Car, we also can't use the car reference to mutate any object that Car points at.

This is called viewpoint adaptation: the permissions we get are the intersection of all permissions we need to go through to get to the object we want. To read the value, all references must grant permission to read. To mutate the value, all reference must grant permission to mutate. A borrowed reference held in a field is no exception either: through a &Car, car.owner reads and lends only &, owner being a &mut Person, so car.owner.age = 18 is refused, and so is calling a self &mut method on it. A method that changes what a &mut field points at takes self &mut; one declared self & may only read through it. Through a &mut Car, or a Car held by value, owner keeps its own permission. (A field that is a &uni reference is another matter, below.) An owning field, such as app So[App] in a struct Holder, is no exception: through a &Holder, h.app lends only &, so a self &mut method cannot be called on it. Through a &mut Holder or a Rc[mut, Holder] it lends &mut and &, but not &uni or &imm, for another name for the same holder could replace the owner while the loan is in use.

Sadly, this also mean that our car reference cannot see anything about the engine. A shared reference cannot see through a uni reference, because that would effectively be sharing what is supposed to be a unique reference. "Shared" here includes &mut: through a &Car or a &mut Car, car.engine is an error, however it is used — read, lent, written or copied out into a local — because another name for the same Car could reach the engine too. The same holds for a &uni held as an array element or a tuple element: it is seen only through uni references, or from an array or tuple held by value.

We can only see engine if our car reference is also uni (or the Car is held by value, with no other name to reach it). But if we do that, then we can no longer see anything about the owner because it is shared, mutable. It would violate the guarantee of uni to move this reference to another thread, if this could result in mut references to the same Person sprinkled across several threads.

Externally-isolated graphs#

Wouldn't it be nice if we could somehow guarantee that when we moved car from one thread to another, that all mutable references to owner would travel with it? If we could guarantee this, it would be safe to perform the move.

In effect, what we want to be able to do is have a graph of multiple objects that is externally isolated, so that we could draw a boundary line around the graph of nodes and there is only pointer into that graph that originates outside that graph. This would be the owning uni reference to the graph's root node. Within the graph could be multiple references to the same node, but none of them originate from outside the boundary line.

To accomplish this, and have visibility into shared references inside the graph, use the recover block as described above. Transition the original uni reference to mut inside the block. Now, we can see and mutate all shared, mutable nodes, including reading or extracting values from them. When done, the block can safely return the original reference as uni.