Weak references: breaking cycles

Counted owners that own each other in a cycle keep each other alive for ever: a parent owns its children, each child points back at its parent, and when the program lets go of the family, every count is still above zero. A weak reference points at a value without keeping it alive, so one weak link in each cycle lets the whole cycle be freed. This page covers how to make one, how to use one, which may find its value gone, and the other kinds of reference that work the same way. Afterwards you can build counted structures with back-links that do not leak:

mod family;

import stdio use *;
import rcweak use *;
import collections use *;

struct ChildValue {
  pub name &str;
  pub parent Weak[ParentValue];          // the weak half of the cycle
  fn final(self &uni) { print <- "child gone\n"; }
}
alias Child = Rcw[mut, ChildValue];

struct ParentValue {
  pub name &str;
  pub kids List[Child];                  // the strong half: the parent owns its children
  fn final(self &uni) { print <- "parent gone\n"; }
}
alias Parent = Rcw[mut, ParentValue];

fn main() {
  let p = new Parent("Ada", List[Child].empty());
  let w = Weak[ParentValue].of(p);
  p.kids.push(new Child("Byron", w.clone()));

  // A weak reference is asked for an owner, and may answer that there is none
  match p.kids[0usize].parent.upgrade() {
    case let parent Some { print <- p.kids[0usize].name, "'s parent is ", parent.name, "\n"; }
    case is None { print <- "no parent any more\n"; }
  }
}                                        // p goes: its value is freed, cycle and all

It prints:

Byron's parent is Ada
parent gone
child gone

Try this: make the back-link strong, pub parent Rcw[mut, ParentValue];, and hand the child p itself. The program prints the parent's name and nothing more: neither gone line appears, because parent and child hold each other's counts up, and the pair leaks.

What makes a reference weak#

Owning and borrowed references always point at a live value, and may always be used to reach it. A weak reference may not: what weak references of every kind share is that they do not keep their value alive, so before one is used, it must be asked whether its value is still there. That makes it a little like an Option, and a little more: the asking is done by logic that knows how the value's region tracks its values.

For reference counting, the region keeps a second count beside the count of owners: the number of weak references. The value is finalized when its last owner goes, as always, and its memory is kept until its last weak reference goes too, so a weak reference can always look and find that the value has died. There are other ways to stop counted cycles leaking, such as tracing the cycles now and then, but a weak link in each cycle is the common one.

Rcw and Weak#

Cycle-breaking weak references are library code, not a kind of reference built into the language. The rcweak package's region Rcw counts both owners and weak references. An owner is allocated as any other, new Rcw[mut, T](...), and the weak reference is an ordinary struct, Weak[T]:

• Weak[T].of(owner) makes one from an Rcw[mut, T] owner, and Weak[T].none() one that points at nothing. A Weak[T] moves when assigned or passed, and is copied only by w.clone().
• w.upgrade() gives an Option of a new counted owner: Some while the value is alive, and None once it has died. The owner in a Some goes when the Option does.
• w.alive() and w.strong() do the same in two steps. w.strong() of a dead value is a panic at the line calling it.

Once the last owner is gone, a weak reference finds nothing:

mod alone;

import stdio use *;
import rcweak use *;

struct Thing {
  pub n i64;
  fn final(self &uni) { printStr("thing gone\n"); }
}

fn main() i32 {
  var w = Weak[Thing].none();
  {
    let owner = new Rcw[mut, Thing](7);
    w = Weak[Thing].of(owner);
    printStr(if w.alive() { "alive\n"; } else { "dead\n"; });
  }                                        // the last owner goes: the Thing is finalized
  printStr(if w.alive() { "alive\n"; } else { "dead\n"; });
  match w.upgrade() {
    case let o Some { printInt(o.n); }
    case is None { printStr("none\n"); }
  }
  let s = w.strong();                      // a dead value: a panic
  printStr("not reached\n");
  0i32;
}

This prints alive, thing gone, dead and none, and then the w.strong() panics: panic at alone.cone:23: rcweak: strong() of a weak reference whose value has died.

The design has a weak reference matched directly into a borrow of its value, bounded by a lifetime as any borrow is. Not built yet: that pattern match; today a weak reference gives a new counted owner instead, as above. Arc has no weak references yet: Weak is made only from an Rcw owner.

Other references that may find nothing#

Two other regions hand out references that work the same way, each checked by its own region:

• A dynamic arena's keys reach a value only through the arena that made it. They are checked when the program is compiled, so they cost nothing at run time.
• A pool's generational Ref is checked on each use against the slot it names, and finds nothing once its value has been removed, even after another value takes the slot.

Cached weak references#

Not built yet. Imagine a large number of sizable values that cannot all fit in memory at once, but can be reloaded or rebuilt on demand. Weak references could point at such cached values, knowing that the store underneath may unload some at any time to make room for others. Matching on such a weak reference would reload its value if it had been purged, before giving a usable borrow of it.

You can now build counted structures with back-links that free themselves, and use a reference that may find its value gone. Counted values shared by several owners raise one more question: how several owners, perhaps on several threads, can safely change one value. That is what lock permissions are for.