Permissions: what a reference may do

Two threads changing one value at the same moment is a data race: the value ends up half one change and half the other, and the bug appears only now and then. Cone prevents it before the program runs, with a permission on every reference that says what it may do: read, change, be copied, cross to another thread. This page covers the static permissions, the ones the compiler checks alone, and how a reference passes from one to another. Afterwards you can choose the permission each reference needs, and know why the compiler accepts it:

mod readings;

import stdio use *;
import collections use *;
import thread;

fn total(readings Uni[List[i64]]) i64 {
  var sum = 0i64;
  each r in readings.iter() { sum += *r; }
  sum;
}

fn main() {
  // A new owner is uni: the one and only way to the list
  let readings = new Uni[List[i64]](4);
  readings.push(12);
  readings.push(7);
  readings.push(30);

  // So it may move to another thread: nobody is left behind to race with it
  let worker = thread.start(readings, &total);
  let sum i64 = worker.join();
  print <- "total: ", sum, "\n";
}

It prints:

total: 49

Try this: change both Uni[List[i64]] to Rc[mut, List[i64]], an owner that may be copied and changed through every copy. The compiler refuses to start the thread: Error 1194: start requires A is Sendable, and Rc[mut, List] is not Sendable: it is an owner whose permission, mut, is not race-safe: only a uni, imm or opaq reference may be shared with or sent to another thread.

A permission belongs to a reference#

The Guide met let and var on variables (let and var): they say whether the variable can be given a new value. A permission on a reference says what may be done with the reference: whether the value it points at may be read or changed, and whether the reference may be copied or sent. The two are separate, which is easiest to see when a variable holds a reference:

let fixed = 1;
var counter = 2;
let ref1 = &imm fixed;     // a let variable holding an imm reference
var ref3 = &imm fixed;     // a var variable holding an imm reference
let ref2 = &mut counter;   // a let variable holding a mut reference
var ref4 = &mut counter;   // a var variable holding a mut reference

Because of the variable's var, ref3 and ref4 may be changed to hold a different reference, and ref1 and ref2 may not. Because of the reference's mut, the values that ref2 and ref4 point at may be changed through them, and the ones ref1 and ref3 point at may not:

ref3 = &imm other;   // Ok: the variable is var
ref2 = &mut other;   // Error 1017: You do not have permission to modify lval (the variable is let)
*ref4 = 5;           // Ok: the reference is mut
*ref1 = 5;           // Error 1017: You do not have permission to modify lval (the reference is imm)

A borrow can only ask for what its source allows: &imm of a var variable is refused (Error 1034: Borrowed reference cannot obtain this permission), since the variable may change while the borrow promises it will not.

The static permissions#

There are two kinds of permission. A static permission is a keyword, written in lower case, whose guarantees the compiler enforces entirely by itself, so it costs nothing while the program runs, and a reference can move from one static permission to another (below). A lock permission is a library type, named as types are, with its first letter alone capitalized: Arc[Mutex, T], Arc[Rwlock, T], Rc[Rwcell, T]. Its guarantees are kept partly by the compiler and partly by a lock taken while the program runs, and only an owning reference in a region can carry one; Lock permissions, in the regions half of this part, has them. This page is about the static ones, and there are six:

uni

A uni (unique) reference may read and change its value, and it is the only reference to that value there is. Because of that one restriction it is governed by moves: passing it to another variable, function or thread leaves it unusable where it was. In return it may hop from thread to thread with no runtime cost at all, the fastest way to hand changeable data to another thread, as the readings above did. It is the natural permission for something new, which starts with one reference (or a graph of values reached through one), and it can later become shared, changeable or unchanging. Knowing a reference is unique can also make code faster. A new owning reference is uni unless it says otherwise.

imm

An imm (immutable) reference may read its value but never change it, and promises that nothing else will change it either. Any number of imm references may point at the same value, on any number of threads, since a value nobody changes cannot be raced on.

mut

A mut (mutable) reference may read and change its value, and any number of them may point at the same value and change it at any time. The price is that they all stay on one thread. A mut reference may also 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 (an enum's variant).

mut1

A mut1 reference, 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. Like mut, its references stay on one thread, and it is refused on a type that never changes.

ro

A ro (read-only) reference may read its value but not change it. That sounds like imm, and is not the same: imm guarantees that no reference anywhere changes the value, which is what makes it safe to share between threads, while ro promises only that this reference will not, and other mut references may. So a ro reference may not be shared with another thread. Of the borrows, only imm, opaq and uni ones may cross to another thread, and only one that lasts the whole program (Race condition safety).

What ro is for is taking a reference of nearly any permission: a function that promises only to read accepts a borrow of a value whoever else can change it. That is why a borrow written with no permission, &T, is ro, except to a type that declares it never changes.

opaq

An opaq (opaque) reference may neither read nor change what it points at. It suits a reference to a function, or to an opaque value, where reaching the value makes no sense, and since it touches nothing it may be shared with any thread.

How permissions rule out data races#

A data race needs three things at once: two references to one value, on two threads, and at least one of them changing it. Each permission removes one of the three, in its own way. uni allows no second reference. imm allows no change. mut, mut1 and ro allow both, and so keep every reference on one thread. opaq reaches nothing. And where many threads really must change one value, a lock permission lets only one reach it at a time. The compiler checks every reference that crosses to another thread against these rules, whatever region the value is in; What may cross a thread has the full rules for sending and sharing. Not checked yet: a var global reached from several threads, and a value that crosses by a route that does not ask, such as a raw pointer cast or an extern call.

The same permissions keep a single thread honest too. Since a uni or imm reference promises that nothing else is changing the value under it, code holding one can rely on the value staying as it last saw it, and the compiler can use that to make the code faster.

Changing a reference's permission#

A copy of a reference normally keeps the original's permission, which is usually what keeps its promises. In some cases a copy with a different permission is just as safe.

To ro#

A ro reference may be borrowed from a reference of any permission but opaq. Promising only to read can never break another reference's promise, which is what makes ro the right parameter for a function that only reads.

From uni, for a while#

A value with one uni reference sometimes needs several for a while. A borrow gives them, temporarily, until the borrow's last use. A &mut borrow is shared and mutable, so while it is still to be used its source becomes one more mut alias of the value: 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 (What a borrow leaves its source free to do). A &uni or &imm borrow, which promises more, freezes the source against reading and changing too. Once the borrows' last use is behind it, the source is unique again, and usable in every way:

let uniref = new Uni[i32](5);
let bref1 &mut i32 = uniref;     // the owner lends a 'mut' borrow
let bref2 = bref1;               // shared with another borrow
*uniref = 6;                     // Ok: uniref is one more 'mut' alias while the borrows are to be used
consume(uniref);                 // Error 1168: 'uniref' is borrowed mutably, and that borrow is used again
                                 //   below. It may not be moved until after that last use.
*bref2 = *bref1 + 1;             // the borrows' last use
consume(uniref);                 // Ok: uniref is unique again (and the value it hands over is 7)

A source reached as uni, which is what a local variable is, 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. An owning reference lent as a borrow, as in the example, freezes its source the same way; lent as a &uni, it is borrowed from too, not moved, and finalized at its own scope's end.

What such a borrow shares is the value the uni reference points at. 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; }
let uniref = new Rc[i32](5);
let other = share(&uniref);     // Error 1013: a borrowed Rc[i32] is not a borrowed Rc[mut, i32]

From uni, for good#

A uni owning reference can also become shared for good, by moving it into an owning reference of a shared permission, mut or imm. The uni reference is consumed by the move, and what is left is a shareable reference, which may be copied:

let ref = new Rc[i32](5);           // a new owner: uni
let shared Rc[mut, i32] = ref;      // moved into a shared, mutable owner
let also = shared;                  // two owners of the same value
*also = 7;                          // either may change it
*ref;                               // Error 1048: This variable's value has been moved out.

This trip is normally one way. Once shared, a reference cannot safely become uni again, nor a mut one imm: as mut it can never cross to another thread, and as imm it can never be changed. Not built yet: moving a uni owner into a borrowed reference of a shared permission, let newref &mut i32 = ref;, is meant to be the same permanent move. Today it borrows instead, and ref stays usable; only a move into an owning type, as above, consumes it.

Getting a permission back#

Not every transition is for good. In some circumstances a lost permission can safely be recovered:

• When a borrow ends. Borrowing moves to a new permission only for the borrow's life. After the borrow's last use, the source has its own permission back: a uni borrowed as mut or imm is uni again, and so is any reference borrowed as ro. 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: the call is lent a fresh, shorter borrow of it instead of the reference itself, the caller is frozen meanwhile, and has its reference, still unique, once that borrow's last use is behind it (Passing a borrow on):

  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);
  }
  

• Not built yet: pure method calls. Calling a method on an object held through a uni reference, without losing it to the method by a move and without borrowing, will be possible when the method is pure and no other argument of the call is a mut or ro reference. Pure functions are not built yet.
• Not built yet: recover blocks, below.

Recover blocks#

Not built yet. A recover block will turn a permission back the other way: any mutable permission made inside it can be recovered as any permission, and any read-only one as any read-only permission or opaq. That is useful for:

• making a shared, mutable structure inside the block and receiving it back as a uni reference;
• making a cyclic structure that never changes: build it shared and mutable inside the block, and recover it as imm;
• turning uni into mut for a stretch of complex changes, and returning it as uni again;
• taking a mutable field out of a uni value as a uni of its own.

It is meant to read like this, for the third case:

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

To make the reverse transition safe, the block may reach no mut, ro or lock reference from outside it, local or global, and may call only pure functions. Then no reference made inside can leak out, every alias made inside ends inside, and whatever the block returns is known to be unique.

When a struct's fields are references#

A struct whose fields are references and the permissions on those references affect each other, both ways:

• Permissions are infectious. The permission of a field's reference can impose itself on the whole struct.
• Viewpoint adaptation. The permission of a reference to the struct can restrict what any field's reference allows.

Permissions are infectious#

Take a car whose fields are references:

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

Since engine is a uni reference, which moves, the whole Car moves (Which types move): if any part of a value moves, so does the value. And since owner is a mut reference, which must stay on its thread, so must any Car, and any reference to one. That holds for every permission that keeps to one thread: mut, ro and Rwcell.

Viewpoint adaptation#

Now take a read-only borrow of a Car:

fn handleCar(car &Car) {
  if car.owner.age < 18 {
    car.owner.age = 18;       // Error 1017: You do not have permission to modify lval
  }
}

The owner field is a mut reference, but the reference to the car is not, and without permission to change the Car there is no permission to change anything reached through it either. That is viewpoint adaptation: the permission you get is what every reference on the way allows. To read a value, every reference on the path must allow reading; to change it, every one must allow changing. A borrowed reference held in a field is no exception: through a &Car, car.owner reads and lends only &, so calling a self &mut method on it is refused too (Error 1034: Borrowed reference cannot obtain this permission: it is held in a place reached through a reference that only reads). 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's own declared permission takes part the same way: what governs access to it is derived from both the field's permission and the struct value's. A field declares none by default, which means var, so the struct value's permission alone decides. One declared let, pub let id i32, is not writable even through a &mut to the struct (Error 1017: You do not have permission to modify lval).

An owning field is no exception either. For app Uni[App] in a struct Holder, through a &Holder the field lends only &, so a self &mut method cannot be called on h.app. Through a &mut Holder or an Rc[mut, Holder] it lends &mut and &, but not &uni or &imm, since another name for the same holder could replace the owner while the loan is in use. A &mut borrow of what the owner owns is allowed, and a call or a store that could replace the owner while it is still to be used is refused (An owner stored over).

A uni field is stricter. A shared reference cannot see through a uni one, since that would share what is supposed to be unique, and "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 (Error 1490: The `&uni` field `engine` cannot be seen through a `&` reference: that reference could be another name for what holds the field). The same holds for a &uni held as an element of an array or a tuple: it is seen only through uni references, or from an array or tuple held by value.

The engine can be seen only when the car reference is uni too, or the Car is held by value, with no other name to reach it. By the design, the owner should then be out of sight, since it is shared and mutable: moving that uni Car to another thread would scatter mut references to the same Person across threads. Not built yet: seeing through a field of a different permission is refused only for a uni field, so today a &uni Car can still read what its mut owner field points at.

Externally isolated graphs#

It would be safe to move the car to another thread if every mut reference to its owner travelled with it. What that needs is a graph of values that is externally isolated: draw a line around it, and only one reference crosses the line from outside, the owning uni reference to its root. Inside, several references may reach the same node, but none comes from outside. Not built yet: the way to build and work on one is the recover block: turn the uni root into mut inside the block, see and change every shared, mutable node, read or take values out of them, and return the root as uni again.

A type that never changes: Immutable#

Rarely needed, but worth knowing: 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 by itself. The body of text, str, declares it, and any struct may, struct Money is Immutable {..}. It has two separate effects:

• 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 var 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.len; }   // s is &imm str
let a = new Rc[str](view);            // Rc[imm, str]
let b = a;                            // copied, not moved: a is still held
fn change(s &mut str) {}              // Error 1297: str declares Immutable, so nothing changes it
                                      //   through a reference: 'mut' is refused.

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.

You can now pick the permission each reference needs, read a race-safety error as the rule it enforces, and lend a unique value without losing it. One question remains for every borrow: how long it lives. The compiler usually works that out, and the next page is about the few places it needs to be told.