Borrowed References

Note: The check for changing the shape of a collection does not tell two lists of one type apart, and does not follow a global changed by a function whose body the compiler cannot read when that function is handed nothing that reaches the collection.

References work differently than other types. The basic idea is simple: references carry an address that points to some value in memory. Using this reference, we can access or change the value the reference points to.

For example:

mut a = 3;
imm ref = &mut a;   // ref holds a reference to a's contents
imm val = *ref;     // val is now 3
*ref = 4;           // a is now set to 4

The & operator borrows a mutable reference to the variable a, effectively pointing to the value it holds. The * (de-referencing) operator is used to obtain and then change the value pointed to by the reference.

References are useful, as they support:

• Shared access to the same value. Multiple references may point to the same value. Any of them can see (and possibly change) the latest value at that address. If one reference changes a value, another sees the updated value. By contrast, values copied around between functions do not work this way: changing a copy leaves the original value unchanged.
• Performance efficiency. For non-trivial data structures, it is faster to pass around a reference to the data rather than making a full copy for each function that needs it.
• Access to dynamically-allocated values. Values that have been allocated from a region (as opposed to local or global variables) are only accessible via references. We will talk about region-managed references later.

As the name suggests, borrowed references point to values that already exist in memory. A common scenario is when we have some existing value and, for some limited lexical scope, we want a reference able to work with that value. A borrowed reference is ideal for this requirement because:

• Borrowed references may point to nearly any value accessible to program logic, including any variable, locked value, field, array element, function, method, or any value pointed at by another reference. This versatility makes it possible to create polymorphic functions or methods that work with referred-to values no matter which region they were allocated in.
• A borrowed reference is as fast as any reference can be, as it never incurs any of the runtime bookkeeping cost borne by region-managed references.

Creating a Borrowed Reference#

Here are several ways to borrow a reference to some existing value.

Borrowing from a variable#

Place the ampersand operator in front of any variable's name to create a borrowed reference that points to the value held by that variable. This works equally well on any global, local or parameter variable:

imm glovar = 2;
fn func(parm i32) {
	mut localvar = 3;
	imm ref1 = &glovar;    // ref1's type: &i32
	imm ref2 = &parm;      // ref2's type: &i32
	imm ref3 = &localvar;  // ref3's type: &i32
}

Borrowing from another reference#

To explicitly create a borrowed reference out of some other reference, place the ampersand operator in front of a de-referenced reference:

imm borref = &*someref;    // Borrow from someref

More often, however, borrowing a reference from an existing reference happens implicitly, as part of a function (or method) call or assignment. This happens when the receiver is given a region-managed reference but expects a borrowed reference. So long as the value type (and permission) match, the borrow is performed automatically.

// This function accepts a borrowed reference
fn incr(nbr &i32) {
  *nbr + 1;
}

fn main() {
  imm allocref = new So[i32](1);   // An owning reference pointing to an allocated value of 1
  incr(allocref);         // Coerces the So reference to a borrowed reference
}

The owning reference is borrowed from, not moved: it is frozen while the borrow is still to be used, may be lent again after, and still ends its value at the end of its own scope. The lend is a borrow exactly as if it were written out, so for a So owner a, both(a, a) handing one call a &mut and a & of it is refused as both(&mut *a, &*a) is, and so is a.absorb(a), lending a to a self &mut method while moving it in as the argument. That holds whatever permission the borrow asks for, &uni included, when the owner is its value's only holder (a So reference, or a Rc one not yet shared), so fn f(p &uni Point) may be called twice with one owner. A shared owner, such as a Rc[mut, T] reference, cannot lend a &uni.

Because any reference may be safely coerced to a borrowed reference, functions and methods typically accept borrowed references as parameters. This capability is what makes possible the benefits mentioned earlier:

• Functions and methods can be polymorphic across regions and permissions at no cost
• Using borrowed references avoids the runtime performance overhead of reference counting (for the Rc region) and reference tracing (for a tracing GC region) within these functions.

Referring to a field or array element#

A borrowed reference may point to a value within some composite value, such as a field in a struct or an element in an array. Again, all we need to do is apply the ampersand operator:

imm ref1 = &apoint.x;   // a field within a struct
imm ref2 = &vec[a];     // an element within an array

This kind of internal borrow is quite powerful, as it supports:

• Internal reference chains. One can reference values within values within values, by chaining together fields or indexing:

  imm ref3 = &vec[3].point.x;
  

  Parentheses should be used, where needed, to clearly demark where an internal reference chain ends.

• A type's own indexing operator. Where the indexed value's type declares a `&[]` method, that method decides what a reference to one of its elements is, and it is called with the borrowed reference evaluated so far as self:

  imm ref4 = &mut list[key];  // passes &mut list as self to list's `&[]` method
  

  A plain &list[key] passes the read-only &list, which a `&[]` method declared with self &mut does not accept. For such a type, list[key] is the read-only way to reach an element.

  A method name after the dot operator is not such a case. The ampersand applies to the whole term, so the method is called first and the ampersand is then applied to what it returned — a temporary, which lives to the end of its statement, or longer where a variable's initializer borrows it (see Borrowing a temporary below). To call a method on a borrowed reference, borrow it explicitly: (&pointer).someref(key).

• Auto-dereferencing a reference source. When an internal reference expression begins with a reference as the source, it is automatically dereferenced:

  // pointref is a reference to a Point structure
  imm ref3 = &pointref.x;   // equivalent to:  &(*pointref).x
  

  The source may be a reference to a reference, to any depth: every level is dereferenced (Implicit De-referencing).

Pattern-matching and each loops#

A plain each borrows each item to read it. One obtains mutable references during each iteration by walking a source that lends them, mutItems() (Each and Iteration):

// increment every number in list
each x in list.mutItems() {
  ++*x;   // x is a mutable reference
}

Pattern matching borrows by using a borrowed reference with the required permission as the source (Pattern Matching).

Permissions#

A reference permission may be specified when a reference is borrowed. The permission governs what may be done with the reference: May we read its value? May we change its value? May we make a copy of the reference?

This permission is specified after the ampersand operator. If none is specified, ro is assumed.

mut a = 3;
imm ref = &mut a;   // Creates a mutable borrowed reference to a's value
*ref = 4;           // a is now set to 4

The permission requested for the borrowed reference must be allowed by the source we are borrowing from. For example, a mutable borrowed reference may not be obtained from an immutable variable.

Permission mechanics are rich enough to be more fully covered on their own page.

Lifetime Constraints#

Every borrowed reference has a lifetime constraint implicitly imposed on it. This lifetime constraint indicates how long the borrowed reference can stay alive before it must expire.

• A reference borrowed from a global variable or function is granted the global lifetime, written 'static. This means it can last for as long as it wants.
• A borrowed reference passed in as a parameter comes from the caller: it outlives the function, so it may be returned, but it may not be stored in a global variable, which may outlive the caller. Where the signature names lifetimes, it may be returned only as a lifetime it is written with, or one the signature's where clause or types order shorter (see lifetime annotations).
• A reference borrowed from a local variable has its lifetime constrained to the block where the borrow took place. The compiler prohibits it from surviving beyond the end of the block. A parameter passed by value, self taken by value, and whatever an owner passed by value owns belong to the function, as its local variables do: a borrow of them may be used anywhere in the function, but never returned or stored outside it.
• A reference borrowed through another borrowed reference has the lifetime of what that reference points at, not of the variable holding it. So a field of what a borrowed parameter points at may be borrowed and returned, even through a local variable the parameter was copied into, a mut one too, so long as it holds nothing shorter-lived.

A value chosen by an if, a match or a block has the lifetime of the shortest-lived value it could give.

This example demonstrates the importance of this lifetime constraint to memory safety:

fn getval() i32 {
  mut ref &i32;
  {
    imm a = 5;
    ref = &a;  // Bad idea! This violates the lifetime constraint
	}
  *ref;   // Oops!
}

The scope of the variable a lasts only for the duration of the inner block. So when we are done executing that block, the variable a ceases to exist. However, when we try copying the borrowed reference into ref, we effectively extend its life beyond the scope it was created in and beyond the life of the value it points to. When we then dereference it, we are trying to retrieve a value that is no longer there. That's a memory safety hazard we must avoid.

The compiler protects against this by refusing it: a may not go out of scope while ref still holds a borrow of it and is used again afterwards. The store ref = &a is not itself the error. A variable's lifetime is that of whatever it holds now, so it may hold borrows of different lifetimes over its life, and had ref been used only inside the inner block, the function would be fine. What a variable holds may not be used after its source is gone, nor returned from the function, nor stored where it would outlive its source: a borrowed reference may only be stored in a place that outlives the function (a global, or what a parameter points at) when its own lifetime is at least as long as that place's.

A borrow is followed wherever it is held. A variable holding a value that contains a borrow — in a struct's field, an Option, an Rc — has the lifetime of that borrow, whatever the value's type, so returning the value, or storing it where it would outlive what it borrows, is refused:

struct R { pub n i64; }
struct H { pub r &R; }

fn inStruct() H {
  imm x = new So[R](4);
  new H(&*x);                   // Error: the returned value carries a borrow of x
}
fn inOption() Option[&R] {
  imm x = new So[R](4);
  Some[&R](&*x);                // Error, the same
}
fn inRc() Rc[H] {
  imm x = new So[R](4);
  new Rc[H](new H(&*x));        // Error, the same
}

The lifetime is enforced across calls as well. A borrow returned through a call keeps the lifetime of what the call was handed, and a borrow handed to a call that could store it somewhere that outlives the function (through a &mut parameter, say) is refused, as is one the call stores into a local that is used after the borrow's source ends:

struct Holder {
  pub r &i32;
  pub fn set(self &mut, r &i32) { self.r = r; }
}
fn id(p &i32) &i32 { p; }

fn throughCall() &i32 {
  imm a = 5;
  id(&a);                       // Error: a belongs to this function
}
fn viaParam(h &mut Holder) {
  imm x = 1;
  h.set(&x);                    // Error: the call could keep the borrow of x in h
}
fn refstore(slot &mut &i32, v &i32) { *slot = v; }
fn intoLocal() i32 {
  imm i = 5;
  mut a = &i;
  {
    imm b = 10;                 // Error: b ends while a, used again below, may hold a borrow of it
    refstore(&mut a, &b);
  }
  *a;
}

Most of the time, the compiler has all the information it needs to infer and enforce lifetime constraints. However, sometimes it needs help in the form of lifetime annotations.

Borrowing a temporary#

A temporary — a value a call or a literal makes that no variable holds — dies at the end of the statement that made it (see finalizers). Where a variable's initializer borrows one, it lives longer instead, to the end of the variable's block, as Rust extends it, so the borrow may be used for as long as the variable can be:

imm r = &make();          // the temporary lives to the end of the block
imm n = &make().count;    // so does this one, of which n borrows a field
imm o &R = makeOwner();   // and an owner lent as a borrow
imm t = (&make(), 1);     // and one borrowed in a tuple, array or variant literal
imm u = if c { &make(); } else { &other(); };  // and one an arm's value borrows

An if's or a match's arm, and a block, whose value is in such a place extends what its value borrows the same way: only the arm that runs makes its temporary, which then lives to the end of the variable's block. Nothing else extends a temporary: one passed to a function, a method's receiver, one in a statement of an arm before its value. Any other temporary may be borrowed too, and lives to the end of its statement: passed to a function (show(&make())), or a method's receiver taken by reference (make().count()). A variable holding a borrow of such a temporary may not be used after its statement, nor may the borrow be returned or stored away.

show(&make());              // the temporary lives to the end of this statement
imm p = pick(makeOwner());   // fine while p is not used again;
p.count;                     // but refused here: the owner died with the statement above

Freezing access to the source of a borrow#

When a borrowed reference is created, its source is a named variable, or a temporary as above. That source either holds or points to the value we are borrowing a pointer to. When we borrow from the source, we are not just gaining access to the value, we are also gaining some or all of its access permissions. To preserve the borrowed reference's guarantees, its source is frozen while the borrowed reference is still to be used. How much is frozen depends on how the source is reached.

A source reached as uni — a local variable, which the stack alone owns, a field of one, or what a uni reference points at — has no other reference to it, so a borrow that promises it unique or unchanging may be given more than the source can share, and the source waits until it is given back (see "From 'uni'"):

• While a read-only borrow (&, &ro, &imm) is still to be used, its source may be read, and borrowed read-only again, but not changed, moved, or ended.
• While an exclusive borrow (&uni, &mut1) is still to be used, its source may not be touched at all except through the borrow: it may not be read, borrowed, changed, moved, or ended.
• A mutable borrow (&mut) is an alias loan, as a borrow of a source reached through a shared path is (below): mut is shared mutable, so the source may be read, changed, and borrowed again while the borrow is still to be used, as one more alias of the value, and any number of &mut borrows of it may be held at once, in one call, in locals and in structs. What the source cannot give while another reference may change it is refused: moving it, sending it, lending it &uni or &imm, ending it, replacing it whole (its old value finalized). A change of its shape — a collection reshaped, an enum given another variant — while a borrow into it is still to be used is refused too, by the rule for shape-changing values below.
• An &opaq borrow, which reads and writes nothing, only keeps its source from being moved, replaced whole, or ended.

A source reached through a shared path — through a mut or ro reference (&mut *p, &p.x for a parameter p &mut Point), through a Rc[mut, T] or other aliasable owner, or a field reached through one — may already be read and changed by other references, since mut is shared. Freezing it against reading or writing would protect nothing, so a &mut or &ro borrow of it only needs it to stay alive:

• The owner it is reached through may not be moved, replaced, changed where it is held, or ended, and may not be borrowed mutably where it is held.
• It may not be borrowed &uni or &imm, which promise what the live borrow could break. (A shared path cannot lend either today in any case: an owner held in a field of a &mut parameter's value or of a Rc[mut, T]'s, h.app for app So[App], lends &mut and & and no more.)
• An &imm borrow of it still forbids changing it, and an &opaq borrow is as above.

fn bump(p &mut Point) {
  imm x = &mut p.x;
  p.x = 7;           // Ok: p's point is shared mutable, so x does not freeze it
  *x = *x + 1;
}

"Still to be used" means until the borrow's last use, not the end of its block. Once nothing will use the borrow again, the source is free, even in the middle of the block that made it. The last use may be on any path the program can take: a later iteration of a loop, or the code after it, is a use too. A copy of a borrowed reference, and any value holding one — a struct, an Option, an array or a list it was put in, by building the value, by storing into it, or by a call handed a &mut of it that may store the borrow there — keeps the source frozen exactly as the borrow does, until that value's last use. A value whose type has a final method that may read the borrow uses it again when it dies. "Ended" covers the source going out of scope, being moved away (passed to a function that takes it, or assigned to another variable), and being replaced whole (assigned or swapped).

fn freeze(n i32) i32 {
  mut k = n;
  imm r = &mut k;
  *r = 5;
  imm m = k;         // Ok: r is not used again (and a read would be let through beside it)
  imm s = &k;
  imm t = k;         // Ok: a read-only borrow still lets k be read
  k = 6;             // Error: s is used again below, and may not see k change
  *s + m + t;
}

fn aliases(n i32) i32 {
  mut k = n;
  imm a = &mut k;
  imm b = &mut k;    // Ok: a 'mut' borrow of a local is an alias loan, so several may be held
  *a = 5;
  k = *b + 1;        // Ok: k is one more alias of the value
  *a + *b;
}

Borrowing one field of a struct freezes that field, and the whole struct with it, but leaves the struct's other fields free. Borrowing an element of an array freezes the whole array, since the compiler cannot tell one index from another. Borrowing through a borrowed reference (&mut *r) keeps frozen whatever r itself froze, while the new borrow is still to be used; what r points at is reached through a shared path, as above, unless r is uni.

An enum follows the collection rule (below). A reference into the payload of an enum's variant — the binding of case imm c Circle on a reference — is a borrow into the enum, through a mut or ro reference from anywhere (a parameter, a field reached through a reference, a reference a variable holds) as well as a borrow of a local made where it is matched. It is allowed, and refused only if something could change which variant the enum holds while it is still to be used: the enum stored over whole or swapped, through the same name or another, or handed to a call whose body (or what it calls) does either, or whose body the compiler cannot read. Writing a field within the variant, by the binding or by the enum's name, or a field the variants share, is not a change. A &mut borrow of a local is an alias loan and is asked the same; a read-only borrow of a local is frozen, as above, and a uni, imm or mut1 reference has no other name to change it, so neither is asked. A name narrowed by a test, if s is Circle, is followed the same way (flow typing). A value owned by an Rc is another owner of the value, and no loan stands for the other owners: where none can store another variant (Rc[imm, T]) the binding is a copy of the owner typed as the variant, and where one could (mut, ro) it is refused (see variant type partial matches).

A borrow a method returns#

A borrow returned by a function or method is a borrow of what it was handed: every borrowed reference in a signature without lifetime annotations shares one lifetime (see lifetimes), so the returned borrow keeps each borrowed argument frozen, as if it were that borrow itself, until its last use. For a method, that is its receiver. Where the signature names lifetimes, it keeps frozen only the arguments whose lifetimes the result may hold, and of an argument whose own borrow's lifetime it may not hold, only what that argument holds in the lifetimes it may: a Cursor['a]'s next returning Option[&'a R] keeps frozen what the cursor holds, not the cursor (see lifetime annotations). An element taken from a local list borrows the list read-only, so the list may be read while the element is used, but not pushed onto, since a push may move every element:

mut list = List[Point].empty();
list.push(new Point(1, 2));
imm first = list[0usize];      // borrows list, read-only
imm n = list.len();            // Ok: list may still be read
list.push(new Point(3, 4));    // Error: first is used again below
first.x;

A method returning a mutable borrow (&mut list[0usize], list.viewMut()) holds an alias loan on its receiver: the receiver may be read, lent again and written while the borrow is used, and a change of its shape — a push, which may move what the borrow points into — is what is refused. A struct that wraps a collection (a method of it lends an element) is held the same way, except that a change to the collection inside it through the struct's own field (w.entities.push(x)) is refused where the loan is, as it always was: the shape check asks about the struct, and a push to what it holds is not a change of the struct's shape.

The arguments of one call are all used by it, so none may touch what an earlier one borrowed in a way that borrow forbids: f(&uni v, v.len()) is an error, while two &mut (or a &mut and a &) of one source in one call are not: f(&mut v, &mut v), step(&w, &mut w.entities[0usize]). The borrow a method call makes of its receiver is mutable and waits for the call, meeting the arguments as a read-only borrow would, so v.push(v.len()) reads v first and then pushes, as does v.push(takeLast(&mut v)), which works the argument out before the push.

A container may declare that the borrows it hands out need no loan on it, because it never moves what it lent. An arena's allocations are fresh and stay where they are, so the arena declares NoLoanMut: while an allocation is used, the arena may be allocated from again, borrowed, and read, but not moved, replaced, or ended. A container of values that never change could declare NoLoanRead for the read-only borrows it lends. (The names are provisional. The compiler takes the container's word for it.)

mut a = Arena.empty();
imm p = a.alloc(new Point(1, 2));
imm q = a.alloc(new Point(3, 4));  // Ok: allocations loan nothing of a
consume(a);                    // Error: p is used again below, and a would take it away
p.x + q.x;

An owning reference used where a borrowed one is wanted lends what it owns: after imm b &Point = u, for u a So[Point], u may not be moved while b is still to be used.

A borrow carried inside a value a call returns is held the same way: the Option a pool's get returns holds a borrow into the pool, which waits for it:

mut p = Pool[Pt].empty();
imm r = p.add(new Pt(7));
imm o = p.get(r);              // an Option holding a borrow into p
p.add(new Pt(8));              // Error: o is used again below
match o { case imm e Some { e.x; } else { 0; } }

Elements of a collection and changing its shape#

The resizable collections (List, Deque, String, Dict, OrderedDict, Set and Pool) each declare ShapeChanging: they may move their elements when they change, and so may a type that wraps one. Why a push waits for a borrow of an element is explained with the collections. This section is how the compiler enforces that wait when the collection is not simply a local variable.

A read-only borrow of an element of a local collection freezes it, as above. A collection reached through a path other references share (a &mut parameter, a Rc[mut, T] owner, a field of self) may be borrowed from freely. The borrow is allowed, and refused only if something could reshape the collection while the borrow is still to be used. That has two parts, and both are enforced.

A change through the same name. A borrow that a method of the collection returns (an element, a cursor, a view), or that a free function handed a reference to the collection returns, is an alias loan of the path the collection was reached through, while the borrow is still to be used. The path may be read, lent and written, but its shape may not be changed, by a push, a clear or a store over it. Each of these is refused at the push (error 1339):

import collections use *;

struct Pt { pub x i64; pub y i64; }

fn f(l &mut List[Pt], p Pt) i64 {
  imm e = l[0usize];
  l.push(p);                    // Error: e is used again below
  e.x;
}

fn g(dq &mut Deque[i64]) {
  mut it = dq.items();          // a cursor
  dq.push(9);                   // Error: it is used again below
  it.next();
}

struct Holder {
  items List[Pt];
  fn h(self &mut, p Pt) i64 {  // the same through a field of self
    imm e = items[0usize];
    items.push(p);              // Error
    e.x;
  }
}

A borrow that may write (&mut l[0usize], l.viewMut()) is an alias loan the same way, and so is a read-only one. Either lets the path be read, lent again and written, and refuses only a change of its shape, by the same name or by another:

fn grow(l &mut List[Pt], p Pt) i64 {
  imm e = &mut l[0usize];
  imm n = l.len();              // Ok: the path may be read,
  l.set(1usize, p);             // and an element written in place
  e.x = e.x + 1;
  e.x + i64.from(n);            // (a l.push(p) anywhere above would be an Error)
}

Shape-changing types of your own#

A type does not have to declare ShapeChanging to be one: the compiler finds it from the type's methods, whatever the type declares. A type changes shape when one method writes storage the type owns (a raw pointer, or a field that holds one, such as a list) and one returns a borrow. So Bag below changes shape, and so does a struct that holds a Bag:

struct Bag {
  items List[Pt];
  fn first(self &) &Pt { items[0usize]; }
  fn add(self &mut, p Pt) { items.push(p); }
}
fn bagAdd(bag &mut Bag, p Pt) i64 {
  imm e = bag.first();
  bag.add(p);                   // Error: e is used again below
  e.x;
}

struct Shelf {
  bag Bag;
  fn first(self &) &Pt { bag.first(); }
  fn add(self &mut, p Pt) { bag.add(p); }
}
fn shelfAdd(s &mut Shelf, p Pt) i64 {
  imm e = s.first();
  s.add(p);                     // Error, the same
  e.x;
}

Writing a number (a cursor that advances, a count) reshapes nothing, and neither does writing an element in place, so a type whose only writes are those does not change shape:

struct Counter {
  items List[Pt];
  at usize;
  fn current(self &) &Pt { items[at]; }
  fn advance(self &mut) { at = at + 1usize; }
}
fn count(a &mut Counter, b &mut Counter) i64 {
  imm e = a.current();
  b.advance();                  // Ok: advance writes only a position
  e.x;
}

Code the compiler cannot read counts as writing: an extern function, a virtual call, a function pointer, and a function of another package whose body its include file leaves out. That is why the include file records the types its package's compile found shape-changing.

Declaring ShapeChanging only asserts what the compiler finds, so a type that declares it and has no such methods is refused (error 1338):

struct Reader is ShapeChanging {   // Error: it lends a borrow, and nothing writes its storage
  items List[Pt];
  fn first(self &) &Pt { items[0usize]; }
}

A type of your own that is not built on a collection changes shape when a method, or a free function of its module that takes it by reference, lends a borrow of it, and one writes storage it owns. fn first(c &Cell) &i64 and fn grow(c &mut Cell) beside the struct Cell are enough. Code in another module reaches the type only through its public methods and fields.

import libc;

struct Cell { ptr *i64; }
fn first(c &Cell) &i64 { c.ptr as &i64; }
fn grow(c &mut Cell) { c.ptr = libc.realloc(c.ptr as *u8, 64usize) as *i64; }

fn cellGrow(a &mut Cell, b &mut Cell) i64 {
  imm e = first(a);
  grow(b);                      // Error: e is used again below
  *e;
}

When a call could reshape a collection#

A change through another name. The second part of the rule: another, different reference to the same collection, or a call that could make one, leaves the element dangling, so a change through it is refused too. The compiler asks of every call made while such a borrow is still to be used, or is being handed to a call, whether the call could reshape the collection. It never goes by a method's name. A call could, when:

1. it is a method taking the collection writable whose body, or anything its body calls,
   • writes a field of the collection (clear, pop and truncate each write the length), or
   • runs a finalizer of an element, which frees what the element owns (set on a List[String] finalizes the String it replaces, so a view of that String's bytes held through another name dangles; on a List[i64], whose element has no finalizer, it reshapes nothing), or
   • moves an element that owns something out of the storage and does not put it back;
2. it is handed a value that can reach a collection of that type (as a field, an element, a variant, a pointer, a reference or an owner) by a path it may write, and its body, or what it calls, reshapes one; or
3. it is handed nothing that reaches one and reshapes one through a global.

Moving elements about within the storage (swap, sortBy) destroys none and moves none out, and the bytes a String element owns stay where they are, so a view of them stays good. Writing an element that has no finalizer in place, l[i] = v on numbers, reshapes nothing.

A function whose body the compiler cannot read (an extern function, a call through a function pointer or a trait, a function of another package that is no generic and no inline) is assumed to reshape whatever it is handed that reaches the collection. A read-only reference (& or &imm) cannot write what it reaches, and a value the function owns whole, a local, cannot be the collection reached through a reference, so neither makes a call one that could.

All of these are refused when the borrow is still to be used afterwards (error 1339):

fn clearOther(l &mut List[Pt], m &mut List[Pt]) i64 {
  imm e = l[0usize];
  m.clear();                    // Error: clear writes the length (so do pop and truncate)
  e.x;
}

fn setString(l &mut List[String], m &mut List[String], s String) usize {
  imm t = l[0usize].view();
  m.set(0usize, s);             // Error: set finalizes the String it replaces
  t.len;
}

fn bump(q &mut List[Pt], p Pt) { q.push(p); }

fn viaCall(l &mut List[Pt], m &mut List[Pt], p Pt) i64 {
  imm e = l[0usize];
  bump(m, p);                   // Error: bump is handed a list and pushes
  e.x;
}

mut pool List[Pt];
fn @initpure init() { pool = List[Pt].empty(); }
fn resetPool() { pool.clear(); }

fn viaGlobal(l &mut List[Pt]) i64 {
  imm e = l[0usize];
  resetPool();                  // Error: resetPool clears a list through a global
  e.x;
}

extern fn elsewhere(q &mut List[Pt]);

fn viaExtern(l &mut List[Pt], m &mut List[Pt]) i64 {
  imm e = l[0usize];
  elsewhere(m);                 // Error: its body is not visible, so it is assumed to reshape
  e.x;
}

And these reshape nothing, so they are accepted:

fn setNum(l &mut List[i64], m &mut List[i64]) i64 {
  imm e = l[0usize];
  m.set(0usize, 9i64);          // Ok: a number has no finalizer
  *e;
}

fn swapStr(l &mut List[String], m &mut List[String]) usize {
  imm t = l[0usize].view();
  m.swap(0usize, 1usize);       // Ok: the bytes of each String stay where they are
  t.len;
}

fn readOnly(l &mut List[Pt], m &List[Pt]) i64 {
  imm e = l[0usize];
  e.x + i64.from(m.len());      // Ok: a read-only reference cannot write
}

fn ownedLocal(l &mut List[Pt], p Pt) i64 {
  imm e = l[0usize];
  mut mine = List[Pt].empty();
  mine.push(p);                 // Ok: a local list is not the one reached through l
  e.x + mine[0usize].x;
}

Two names for one collection can arise in several ways. Each of these is refused at the push (p is a value to push, and the push through the second name moves the element e points at):

• A parameter. Two &mut parameters, which the caller may have made one list.
• A field of self. A borrow of one field, and a push through other.items in a method, other being the same value.
• A Rc[mut, T] owner. The owner copied, so two names hold the one list.
• An arena allocation held by name. A list allocated in an arena and held by two names.
• A reference made from a pointer. Two references made from one pointer.

struct Bag2 {
  items List[Pt];
  fn fb(self &mut, other &mut Bag2, p Pt) i64 {
    imm e = items[0usize];
    other.items.push(p);        // Error: other may be self
    e.x;
  }
}

fn fa(l &mut List[Pt], m &mut List[Pt], p Pt) i64 {
  imm e = l[0usize];
  m.push(p);                    // Error: m may be l
  e.x;
}

fn fc(p Pt) i64 {
  imm l = new Rc[mut, List[Pt]](List[Pt].empty());
  imm l2 = l;
  imm e = l[0usize];
  l2.push(p);                   // Error
  e.x;
}

fn fd(a &mut Arena, p Pt) i64 {
  imm l = a.alloc(List[Pt].empty());
  imm l2 = l;
  imm e = l[0usize];
  l2.push(p);                   // Error
  e.x;
}

fn fe(ptr *List[Pt], p Pt) i64 {
  imm l = ptr as &mut List[Pt];
  imm l2 = ptr as &mut List[Pt];
  imm e = l[0usize];
  l2.push(p);                   // Error
  e.x;
}

A borrow handed to the very call beside the reference that changes it is refused too, for the caller may have made out and x one string:

fn appendBoth(out &mut String, x &String) {
  out.append(x.view());         // Error: x's view is in use while out may change shape
}

Stores#

A store is asked as a call is, for it is no call but could do the same. While such a borrow is still to be used, an assignment or a swap through another name is refused when it replaces the collection whole (*m = List[String].empty();), a struct holding one, or an element that owns something, or a field of one, found by indexing the collection (m[0usize] = s finalizes the old String, so a view of its bytes dangles). So is a store over a field that owns the collection through an owning reference (So, Rc, Arc, or a region a program declares), and a store over the whole struct that holds it. These are refused with error 1426:

struct Item { pub n i64; }
struct Ship { pub fuel i64; pub vec So[List[Item]]; }

fn whole(l &mut List[String], m &mut List[String]) usize {
  imm t = l[0usize].view();
  *m = List[String].empty();    // Error: the old list is freed
  t.len;
}

fn elem(l &mut List[String], m &mut List[String], s String) usize {
  imm t = l[0usize].view();
  m[0usize] = s;                // Error: the old String is finalized
  t.len;
}

fn field(a &mut Ship, b &mut Ship) i64 {
  imm e = a.vec[0usize];
  b.vec = new So[List[Item]](List[Item].empty());   // Error: the list the owner held is freed
  e.n;
}

fn wholeShip(a &mut Ship, b &mut Ship, s Ship) i64 {
  imm e = a.vec[0usize];
  *b = s;                       // Error, the same
  e.n;
}

Writing an element that owns nothing in place is not refused, nor is replacing a field of an element through the reference that borrowed the element, nor a field of some other struct that holds a String:

fn setPt(l &mut List[Pt], m &mut List[Pt], p Pt) i64 {
  imm e = l[0usize];
  m[0usize] = p;                // Ok: a Pt owns nothing
  e.x;
}

fn fieldOfElem(l &mut List[Pt]) i64 {
  imm e = &mut l[0usize];
  e.x = 12;                     // Ok: a field of the element, through the borrow
  e.x;
}

struct Log { pub log String; pub n i64; }

fn otherStruct(l &mut List[String], g &mut Log, s String) usize {
  imm t = l[0usize].view();
  g.log = s;                    // Ok: that String is not an element of l
  t.len;
}

The cures#

A refusal is cured in one of three ways, each of which keeps the borrow:

• Make the source &imm, which nothing may write (x &imm String).
• Make the receiver &uni, which no other name reaches (out &uni String). A &uni reference passed to a call that wants a &uni is borrowed from, so a method taking self &uni may be called twice.
• Copy what is needed out first, so that no borrow is left to wait.

fn appendImm(out &mut String, x &imm String) { out.append(x.view()); }
fn appendUni(out &uni String, x &String) { out.append(x.view()); }

fn appendCopy(out &mut String, x &String) {
  imm c = String.from(x.view());
  out.append(c.view());
}

fn twice(s &uni String, x &String) {
  appendUni(s, x);
  appendUni(s, x);              // Ok: the first call borrowed from s, and has given it back
}

What the check does not follow#

The check does not tell two values of one type apart. A function handed a List[Pt] that reshapes one is taken to reshape the one an element was borrowed from, even when the compiler could show they differ, as for a list freshly allocated in the function. (A list the function owns whole, a plain local, is the exception, as above.)

fn ownedFresh(l &mut List[Pt], p Pt) i64 {
  imm e = l[0usize];
  imm m = new So[List[Pt]](List[Pt].empty());
  bump(&mut *m, p);            // refused, though m cannot be l
  e.x;
}

Nor is a global followed that a function whose body is not visible changes, while that function is handed nothing that reaches the collection. Such a call is taken to reshape nothing, whereas the same change made by a function the compiler can read is refused.

Reference Operations#

The de-referencing and comparison operators may be directly applied to references.

De-referencing#

The most common use of references is to access and work with the value it points to. Accessing this value is called de-referencing. To explicitly de-reference, use the * operator. Within expressions, dereferencing retrieves the value the reference points to. Used to the left of an assignment operator, dereferencing changes that value.

mut count = 3;
imm ref = &mut count;
imm val = *ref;  // val is now 3
*ref = 4;        // ref now points to the value of 4 (in count)

De-referencing is only permitted if the reference's permission allows it. Certain permissions, such as opaq and the locked permissions, disallow de-referencing.

Comparison#

A reference stands in for its value everywhere else, and comparison is no exception. == and != on two references compare the values they refer to, using the value type's own == (a number's, an enum's, or one a struct declares). The ordering operators (<, <=, >, >=) compare the values too. A reference may also be compared with a value, on either side, when the value copies freely (a number, a bool, a char, a plain struct): the borrow is read through, as it is for any operator (Implicit De-referencing). A reference to a type that moves, such as a String or a struct with a finalizer, is not read through against a value, since that would take the value out of the borrow:

mut a = 5;
mut b = 5;
imm ref1 = &a;
imm ref2 = &b;
if ref1 == ref2 {   // true: both refer to a 5
		// do some stuff
}
if ref1 == 5 {     // true: a reference against a value is read through
}
if 4 < ref2 {       // and so is a value against a reference
}

A value type that offers no == (or no ordering operator) cannot be compared through a reference either. Two slices compare their elements, one by one. Comparing what two virtual references refer to is not yet implemented.

To ask instead whether two references point to the same place, use the identity operator ===, or its negation !==. Identity reads nothing through either reference, so it works whatever the value type is, and even for an opaq reference. Both references must have the same type. Two slices are identical when they view the same elements with the same length:

if ref1 === ref2 {  // false: a and b are different variables
}
if ref1 === &a {    // true
}

References have no order of their own. A pointer does: its comparison operators work on the pointer itself, never on what it points to, and on a pointer === means the same as ==.

Reference Handling#

References are values. As such, they can be stored and passed around a program. Whether such transfers are simple copies or moves depends on the reference's permission: a reference having the uni permission can itself be moved, or it can be borrowed from, which is the reborrow. Passing a &uni variable to a call or binding that wants a borrowed reference (&, &imm, &mut or &uni: an argument, a method's receiver, a local's type) implicitly borrows from it, a fresh and shorter loan, instead of handing over the reference itself. The borrow is exactly what &mut *r (or &uni *r) written out would be: the reference is frozen as for any borrow, so it may not be used while the borrow is, and it may be used again once that borrow's last use is behind it ("Borrowed reference recovery"). A result derived from the borrow keeps the reference frozen while that result lives, and the callee cannot keep the borrow past the caller's own storage. So a function taking r &uni Point may pass r to a &uni Point or a &mut Point parameter twice, and a method taking self &uni may call the type's self &uni, self & and self &mut methods, one after another, and then read its fields. A &uni slice is borrowed from the same way, whether it is passed to a &uni, &mut or & slice, or is the receiver of one of its own methods, so s.len() + s.len() and while i < s.len() work on a &uni slice:

fn fill(q &uni Point) { q.x = q.x + 10; }
fn twice(p &uni Point) {
  fill(p);       // fill borrows from p for the call
  fill(p);       // and p is still there, still unique, to borrow from again
  imm q &uni Point = p;   // a &uni local borrows from p
  q.x = 0;
  p.y = 1;       // allowed: q's last use is behind us
}

A part of a &uni slice is borrowed from in the same way: &uni s[a..<b], &uni s[a..] and &uni s[i] are loans of part of what s reaches, so s is frozen while the sub-slice or element is used. A local holding a &uni that the function was lent, such as a cursor (mut cur = p, reassigned as it walks along), can be handed back, and so can a borrow from it: it holds the caller's reference, so what is borrowed from it lasts as long as that does. A borrow of the function's own value, however it came to be held in the local, cannot be handed back.

A slice's elements are not told apart, so two parts of one slice are two borrows of the same place. One call may not be handed a &uni of an element or sub-slice beside any other borrow of the same slice (a second element, a sub-slice, the whole slice, a &, &mut or &imm), even when the indexes or ranges differ, because the call would reach the part through two paths while a unique reference promises there is one. Distinct fields of a struct are apart. A &mut or & slice, whose references may alias anyway, may be handed two &mut or two & of one element. The parts of an owner's array or of a &uni slice are reached uniquely, and two &mut of one element are refused there, as two of one field are.

fn two(a &uni i64, b &uni i64) {}
fn byIndex(s &uni Array[i64]) { two(&uni s[0usize], &uni s[1usize]); }  // Error: the elements are not told apart
fn byField(p &uni Pair) { two(&uni p.a, &uni p.b); }        // Ok: distinct fields

fn walk(p &uni Array[i64], k i64) &uni Array[i64] {
  mut cur = p;
  mut i i64 = 0;
  while i < k {
    cur = &uni cur[1..];   // a sub-slice, borrowed from the cursor
    i = i + 1;
  }
  cur;                      // the caller's slice, narrowed: allowed
}

Reference transfers also check reference type information to ensure everyone is in agreement about what you can do with any passed-around reference.

Even though references are typed values, they do sometimes get some special treatment to make them more convenient to use, particularly to enable them to act as stand-ins for the values they point to.

Reference Method Definitions#

Methods may be defined that accept references as the type for self. However, importantly, such methods must be defined as part of the value type's collection of methods. Thus, if we want to define a method that works on a reference to a Point, that method must be defined within the collection of methods for the Point type:

struct Point {
  // .. other Point methods here

  // method that accepts a reference to a Point
  pub fn normalize(self &mut Point) {
    imm len = self.len;
    x /= len;
    y /= len;
    z /= len;
  }
}

Implicit De-referencing#

Since a reference is generally understood to be a stand-in for the value it references, de-referencing often happens implicitly. For example, when the dot operator is applied to a reference to access a field, the reference is automatically de-referenced:

imm y = ref.y; // equivalent to: (*ref).y

Automatic de-referencing might also happen when applying a method to a reference. For example:

imm pos = ref.abs;    // pos is 4. Equivalent to: (*ref).abs
imm sum = ref + 4.;   // sum is 0. Equivalent to *ref + 4.

With methods, the decision on whether or not to implicitly de-reference depends on what is supported by implemented methods. If an existing method can accept the reference as a reference, it is used. If not, the reference is de-referenced before applying the method.

A field or a method called by name, or an index, reaches through every level of reference: a reference to a reference (&&Pt, &&&Pt, &mut &Pt), an owner behind a borrow (&So[Pt]), a slice or a virtual reference behind one. This is what the closure of iter().filter(...) sees, a borrow of the borrowed item:

imm big = pts.iter().filter(p => p.x > 5).count();   // p is &&Pt: p.x is (**p).x
imm n = rr.len();                                     // rr is &&&Pt: (***rr).len()

The outermost level wins a name. A method the outer reference or owner itself declares is used before the receiver is read through any further: the identity test === on two &&Pt asks whether the outer references are the same place, not whether the &Pt they hold point at one. A struct that holds a reference and declares its own len has that one called, never the held value's. A raw pointer is not read through: its own operators are used, and it is dereferenced with * (Pointers).

The access is exactly what the dereferences written out would give: r.x is (**r).x. Each borrow keeps its own permission, so through r & &mut Pt a write r.x = 9 is allowed as (**r).x = 9 is, and through &mut &Pt it is refused, as it is written out, since the inner level only reads. An owner reached through a & lends only & (Freezing access to the source of a borrow, above): through r &So[Pt], r.x = 9 and a self &mut method are refused.

An operator's other operand is read through the same way. A reference on either side of an operator, or on the right of a compound assignment, gives the operator the value it refers to, so a variable that borrows a number takes part in arithmetic and comparison like the number:

imm total = sum + ref;     // equivalent to: sum + *ref
sum += ref;                // equivalent to: sum += *ref
imm bigger = ref > 3;      // equivalent to: *ref > 3
imm same = ref == other;   // two references: the values are compared, not the places

This is a copy of a value that copies freely: a number, a bool, a char, or a plain struct with no finalizer. It never moves a value out of a borrow, so a borrowed String (or any type that moves) is not read through this way, and keeps whatever its own operators accept. As with a method, an operator that accepts the reference itself is used as it is before any reading through is tried. The * stays wherever it means something more than reading: an explicit copy (imm y = *x), a store through the reference (*x = 4), or a function's argument.

Nullable References#

References only ever point to valid values. However, it is possible to explicitly declare and use nullable references, much like any other nullable value.

imm ref4 ?&imm i32;		 // nullable reference to an integer

In addition to pointing to a valid value, a nullable reference may also have the value Null, which means the reference does not point to any valid value. To ensure safety, access to a nullable reference's value is only possible if the code first ensures the reference does not have the value of Null:

// This condition is true only if maybePoint is not null ...
if maybePoint {
  imm point = *maybePoint; // ... allowing us to obtain its value
}
imm point2 = *maybePoint;    // **ERROR** We don't know if maybePoint is null here

Note: A special optimization ensures that nullable references are the same size as regular references.

Array and Virtual References#

In addition to regular references, there are also special-purpose "fat" references which are handled somewhat differently:

• Array references point to a collection of identically-typed elements. These elements are contiguous in memory with the reference pointing to the first element. The number of elements is carried as part of the array reference. Such references may be indexed and are subject to bounds checks.
• Virtual references offer an abstract view of some value instantiated by one of several variant types. In addition to pointing at the value's data, the reference also points to runtime type information that facilitates field access or method dispatch.