Weak References

On this page

Cycle-breaking Weak References
Rcw and Weak
Cached or memo-ized Weak References
First-class Arenas
ECS-based Pools

Note: Cached weak references are not implemented. Nor is a pattern match on a weak reference that produces a borrowed reference: a weak reference gives a new counted owner instead. The &arena mut 5 allocation and the Arena['a] and ArenaRef+'a' spellings below are not implemented; the arena package's DynArena hands out keys. How a value is allocated in a dynamic region such as an arena or a pool is an open design question: the packages allocate with a.alloc(value), new a[T](...) and p.add(value), and no other spelling is read.

Owning and borrowed references always point to live objects, and may always be directly used to manipulate the objects they point to. This is not true for weak references. Although there are many varieties of weak references, what they share in common is the idea that they do not keep alive the object they point to. sTherefore, we have to confirm whether the weak reference still points to a live object before accessing it.

Weak references may sound like a bit like a nullable references, however there is additional intelligent logic that runs alongside the liveness check. Let's examine different kinds of weak references and explain the value they add to various region strategies.

Cycle-breaking Weak References#

As mentioned earlier, one of the disadvantages of the reference counting region strategy is that they can leak memory whenever a data structure has cyclic references. Essentially, cyclic references prevent reference counts from ever decrementing to zero. This can cause useless islands of data, no longer accessible by the program, to persist in memory forever.

There are several good solutions for preventing cycle-based leaks. The most common involves the injection of at least one weak reference in every data structure cycle. Unlike normal references, weak references won't keep the object it points to alive. It accomplishes this using a separate weak reference counter which behaves a bit differently than the "strong" reference count

The downside of a weak reference is that you need to pattern match on it before you can use it, to ensure the object is still there. As with many weak references, a successful pattern match produces a lifetime-constrained borrowed reference which can be then be used to work with the object it points to.

Rcw and Weak#

Today, cycle-breaking weak references are library code, not a kind of reference, and a weak reference is asked for a new counted owner rather than pattern matched into a borrow. The rcweak package's region Rcw counts both strong owners and weak references. A strong owner is allocated as any other, new Rcw[mut, T](...). The weak reference is an ordinary struct, Weak[T].

Weak[T].of(owner) makes one from an Rcw[mut, T] owner. 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 object 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 object is a panic at the line calling it.

The object is finalized when its last strong owner goes, and its memory is freed when its last weak reference goes too. In this family, the child holds a weak reference to its parent, so the parent's counted owners are the only thing that keep it alive:

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

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

struct ParentValue {
  pub name i64;
  pub kids List[Child];
  fn final(self &uni) { printStr("parent gone\n"); }
}
alias Parent = Rcw[mut, ParentValue];

fn main() i32 {
  imm p = new Parent(1, List[Child].empty());
  imm w = Weak[ParentValue].of(p);
  p.kids.push(new Child(2, w.clone()));
  match p.kids[0usize].parent.upgrade() {  // an Option of a new counted owner
    case imm owner Some { printInt(owner.name); printStr("\n"); }
    case is None { printStr("dead\n"); }
  }
  printStr(if w.alive() { "alive\n"; } else { "dead\n"; });
  0i32;
}

This prints 1 and alive. When main ends, p's last owner goes, so parent gone and child gone follow; the child's weak reference did not hold the parent up.

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

import stdio use *;
import rcweak use *;

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

fn main() i32 {
  mut w = Weak[Thing].none();
  {
    imm 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 imm o Some { printInt(o.n); }
    case is None { printStr("none\n"); }
  }
  imm s = w.strong();                      // a dead object: a panic
  printStr("not reached\n");
  0i32;
}

This prints alive, thing gone, dead and none, and then the w.strong() panics.

Cached or memo-ized Weak References#

Imagine we want memory access to a large number of sizable objects. Due to memory constraints, we may not be able to fit all of them in memory at the same time, but we can readily reload or reconstruct them on demand. In this situation, we can use weak references to point to such cached objects, knowing that the underlying system store may automatically unload some objects at any time to reclaim space for other objects.

Pattern-matching on such a weak reference reloads the object, if it has been purged, before producing a usable borrowed reference to the now-live object.

First-class Arenas#

The sizeable performance advantage of arena regions, is offset by their inability to reclaim memory until the entire arena is freed. This means memory waste and determinism worsen steadily the longer a program runs. This can be particularly problematic when using a global arena whose lifetime lasts for the lifetime of the program.

Dynamic (first-class) arenas offer a nice solution to this problem. A dynamic arena may be created at any time, used to allocate a bunch of temporary objects, and then destroyed soon after, when we have no further need for any of those objects. Short-lived arenas offer the same performance advantage, but dramatically improve determinism and memory efficiency.

If object references obtained from a dynamic arena never need to live longer the lifetime of the scope where they were obtained, we can just produce a borrowed reference for every object allocated within the dynamic arena. However, if we need either the object references or the dynamic arena to span multiple lifetime scopes, borrowed references may be too restrictive.

Weak references may be used to solve this flexible lifetime requirement. Every request to allocate a new object in the arena returns a weak reference. We know the object is still alive as long as the arena is alive, so to access the object, we only need to prove the arena is still there:

mut arena = Arena.empty();     // A new dynamic arena
imm objref = &arena mut 5;  // Allocate a new i32 object in the new arena region
arena[objref] = 2;          // Change the value of the object

The arena package's DynArena is the form built today: every request to allocate a new object in the arena returns a key, a reference of the arena's own brand, &'=a mut T, which reaches nothing on its own (a dynamic arena):

import stdio use *;
import arena use *;

fn main() i32 {
  mut ar = DynArena.empty();      // A new dynamic arena
  imm objref = ar.alloc(5i64);    // Allocate a new i64 object in it: a key
  ar[objref] = 2;                 // Change the value of the object
  printInt(*ar[objref]);          // 2
  printStr("\n");
  0i32;
}

Although it may look like we are "indexing" the arena by an object reference, there is no runtime indexing logic taking place. This construction simply allows the compiler to verify at compile-time that the arena is still alive, and therefore the object reference is still valid.

The compiler can also verify that the object reference came from that arena, as both share the same hidden lifetime information. This lifetime information must be explicitly noted should one wish to pass the arena or object references to other functions or methods:

fn dowork(arena Arena['a], objref ArenaRef+'a') { ... }

Built today, the brand is written '=a on the arena and on the key:

import stdio use *;
import arena use *;

fn dowork(ar &mut DynArena['=a], key &'=a mut i64) {
  ar[key] = ar[key] + 1;
}

fn main() i32 {
  mut ar = DynArena.empty();
  imm objref = ar.alloc(2i64);
  dowork(&mut ar, objref);        // the same lifetime '=a names both
  printInt(*ar[objref]);          // 3
  printStr("\n");
  0i32;
}

Notice that same lifetime annotation is specified for both the arena and the object reference. This ensures use of dynamic arena references is always safe.

ECS-based Pools#

With games, we often want to create pool-allocated entities that we can deterministically kill at any time, much like single-owner objects. However, we also want other entities to be able to refer to them over an extended period of time (e.g., one character following or tracking another). The lifetime constraints of borrowed references make them unsuitable for these shared references, as they need to survive beyond the scope they are created in. An owning reference is also unsuitable, as the entity it points to could be destroyed at any time, leaving unsafe or invalid reference(s) behind.

The solution is once again to use weak references for these shared references. The weak reference is interrogated to see if it still points to the same live object. If so, a borrowed reference is produced allowing access to the object. Under the covers the weak reference determines whether the same object is alive, using some technique like generational indexing, a variation on reference counting, or subscription lists.

The pool package's Pool[T] uses generational indexing. Adding a value hands out a Ref[T], a slot and a generation, which owns nothing and is copied freely, and the pool checks it on each use: p.get(r) answers Some borrow of the value, or None once the value has been removed (the generational Pool):

import stdio use *;
import pool use *;

struct Npc { pub hp i64; pub target Ref[Npc]; }

fn main() i32 {
  mut world = Pool[Npc].empty();
  imm orc = world.add(new Npc(10, Ref[Npc].none()));
  imm elf = world.add(new Npc(8, orc));          // the elf follows the orc
  match world.get(world[elf].target) {
    case imm t Some { printInt(t.hp); printStr("\n"); }
    case is None { printStr("target gone\n"); }
  }
  world.remove(orc);                             // the orc dies
  match world.get(world[elf].target) {
    case imm t Some { printInt(t.hp); printStr("\n"); }
    case is None { printStr("target gone\n"); }
  }
  0i32;
}

This prints 10 and then target gone.