Box, Rc and RefCell

Smart pointers · Lesson 39

A smart pointer is a value that owns data somewhere else, lets you reach it as if it were the value itself, and cleans it up when it goes out of scope. Box<T> is one owner on the heap. Rc<T> is several owners with a count. RefCell<T> lets you change something through a shared reference, by checking the borrowing rules when the program runs. Together they cover the cases where ownership really is shared. Most programs need them in a few places; the rest of the time a plain value or a reference does the job.

Coming from GoGo has no owning pointer types: a *T is a plain pointer, and the garbage collector frees what nobody can reach. Copying a pointer is how you share, and every holder may change the value. Most Go pointers, passed to a function that uses them for the call, become a plain &T or &mut T in Rust. Rc<T> is for the sharing that remains, with the owners counted, and read-only until you add a RefCell. Drop does the job defer does, tied to the value instead of the function.

Coming from KotlinEvery object reference is already shared, and the JVM frees an object when nothing can reach it. Rc<T> is that sharing as an opt-in, with a count you can read, and a value inside an Rc is read-only until you add a RefCell. Box<T> is the other case: one owner, no sharing.

Coming from PythonCPython frees most objects by counting references, which is what Rc does, but it counts every name for you and lets any name change the object. In Rust you ask for the count (Rc), and you ask for the right to change shared data (RefCell). A cycle is collected by Python's cycle collector, and is not by Rc. Most of what you share by passing a name to a function is a plain & in Rust.

Coming from TypeScriptObjects are shared by reference and freed by the garbage collector, and any name may change the object. Rc<T> is that sharing made explicit, with a count and read-only access, and RefCell<T> is the way to change a shared value. Box<T> is the one-owner case that JavaScript has no word for.

Coming from JavaEvery object variable is already a shared reference, freed by the garbage collector when unreachable. Rc<T> is an opt-in version with a visible count, and a value in an Rc is read-only until you add a RefCell. The JVM also reclaims reference cycles; Rc does not. You never need WeakReference to break a cycle in Java; Weak<T> is how you write a back-pointer that does not keep its target alive.

Coming from C#A class instance is already a shared reference that the garbage collector frees when unreachable. Rc<T> is that sharing as an opt-in, with a count, read-only until you add a RefCell. Box<T> is the single owner; Weak<T> is the WeakReference that does not keep the value alive.

Coming from CIn C you share a value by copying its pointer and decide by hand who calls free. An Rc<T> is that pattern with the count and the free written once, in the type, so the value is freed when the last owner goes. A Box<T> is one malloc with one owner, freed when it goes out of scope.

Coming from C++Box<T> is std::unique_ptr<T>, but a moved-from Rust box cannot be used at all (a compile error), where a moved-from unique_ptr is a null pointer that you may dereference by mistake (undefined behaviour). Arc<T> is std::shared_ptr<T>, and Rc<T> is closest to shared_ptr<const T> with a count that is never atomic: the standard library offers no such pointer to ask for, and Rust makes the choice in the type. Weak<T> is std::weak_ptr<T>.

The quick comparison

Rustsrc/main.rsRun ↗Copy

use std::cell::RefCell;
use std::rc::Rc;

fn main() {
    // one list with two owners: a count of owners, and no copy of the list
    let log = Rc::new(RefCell::new(Vec::new()));
    let other = Rc::clone(&log);

    log.borrow_mut().push("from log");
    other.borrow_mut().push("from other");

    println!("log: {}", log.borrow().join(", "));
    println!("same list: {}", Rc::ptr_eq(&log, &other));
}

$ cargo run

log: from log, from other
same list: true

GoKotlinPythonTypeScriptJavaC#CC++

Copy

package main

import (
  "fmt"
  "strings"
)

type Log struct{ lines []string }

func main() {
  // a pointer is already shared: copying it copies the address
  log := &Log{}
  other := log

  log.lines = append(log.lines, "from log")
  other.lines = append(other.lines, "from other")

  fmt.Println("log:", strings.Join(log.lines, ", "))
  fmt.Println("same list:", log == other)
}

$ go run main.go

log: from log, from other
same list: true

fun main() {
    // every object is already a shared reference
    val log = mutableListOf<String>()
    val other = log

    log.add("from log")
    other.add("from other")

    println("log: ${log.joinToString(", ")}")
    println("same list: ${log === other}")
}

$ kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar

log: from log, from other
same list: true

# every object is already a shared reference
log = []
other = log

log.append("from log")
other.append("from other")

print("log:", ", ".join(log))
print("same list:", str(log is other).lower())

$ python3 main.py

log: from log, from other
same list: true

// every object is already a shared reference
const log: string[] = [];
const other = log;

log.push("from log");
other.push("from other");

console.log("log:", log.join(", "));
console.log("same list:", log === other);

$ tsc --strict --module nodenext --types node main.ts && node main.js

log: from log, from other
same list: true

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        // every object is already a shared reference
        List<String> log = new ArrayList<>();
        List<String> other = log;

        log.add("from log");
        other.add("from other");

        System.out.println("log: " + String.join(", ", log));
        System.out.println("same list: " + (log == other));
    }
}

$ javac Main.java && java Main

log: from log, from other
same list: true

// every object is already a shared reference
var log = new List<string>();
var other = log;

log.Add("from log");
other.Add("from other");

Console.WriteLine($"log: {string.Join(", ", log)}");
var same = ReferenceEquals(log, other) ? "true" : "false";
Console.WriteLine($"same list: {same}");

$ dotnet run

log: from log, from other
same list: true

#include <stdio.h>
#include <stdlib.h>

struct Log {
    const char *lines[8];
    int count;
};

int main(void) {
    // two pointers to one struct; nothing counts the owners
    struct Log *log = calloc(1, sizeof *log);
    struct Log *other = log;

    log->lines[log->count++] = "from log";
    other->lines[other->count++] = "from other";

    printf("log: ");
    for (int i = 0; i < log->count; i++) {
        printf("%s%s", i ? ", " : "", log->lines[i]);
    }
    printf("\n");
    printf("same list: %s\n", log == other ? "true" : "false");

    free(log); // exactly once, and only because we remembered
    return 0;
}

$ gcc -Wall -Wextra main.c -o main && ./main

log: from log, from other
same list: true

#include <iostream>
#include <memory>
#include <string>
#include <vector>

int main() {
    // shared_ptr counts its owners, as Rc does; unlike Rc, every owner may change the list
    auto log = std::make_shared<std::vector<std::string>>();
    auto other = log;

    log->push_back("from log");
    other->push_back("from other");

    std::cout << "log: ";
    for (size_t i = 0; i < log->size(); i++) {
        std::cout << (i ? ", " : "") << (*log)[i];
    }
    std::cout << "\n";
    std::cout << "same list: " << (log == other ? "true" : "false") << "\n";
}

$ g++ -std=c++20 -Wall -Wextra main.cpp -o main && ./main

log: from log, from other
same list: true

What's different

• A smart pointer owns data that lives elsewhere (usually the heap), derefs to it, so *b and b.method() reach the data, and runs Drop to free it. Box<T> has one owner, Rc<T> has several and counts them, and the value is freed when the count reaches zero.
• Rc::clone(&a) copies a pointer and adds one to the count. It does not copy the data. Rc::ptr_eq(&a, &b) says whether two Rcs point at the same allocation.
• An Rc gives out only shared references, because several owners may be reading. To change the value you wrap it in RefCell<T>, which checks the borrowing rules when the program runs: a second borrow_mut() while one is alive panics instead of failing to compile.
• Two Rcs that own each other never reach zero, so neither is freed. Make one of the links a Weak<T>, which does not count as an owner and gives back None once the value is gone. Rc is for one thread; Arc is the version that threads may share.

Gotcha

Changing a value through a shared Rc

Looks fine: in Go, Kotlin, Python, TypeScript, Java, C#, C and C++ it runs fine. Rust won't compile it.

Works in Go. In Rust it's just a rule.Works in Kotlin. In Rust it's just a rule.Works in Python. In Rust it's just a rule.Works in TypeScript. In Rust it's just a rule.Works in Java. In Rust it's just a rule.Works in C#. In Rust it's just a rule.Works in C. In Rust it's just a rule.Works in C++. In Rust it's just a rule.

Rustsrc/main.rs✗ won't compileCopy

use std::rc::Rc;

struct Counter {
    hits: u32,
}

fn main() {
    let a = Rc::new(Counter { hits: 0 });
    let b = Rc::clone(&a);

    a.hits += 1;
    b.hits += 1;
    println!("hits: {}", a.hits);
}

Go✓Kotlin✓Python✓TypeScript✓Java✓C#✓C✓C++✓

Copy

package main

import "fmt"

type Counter struct{ Hits int }

func main() {
  a := &Counter{}
  b := a

  a.Hits++
  b.Hits++
  fmt.Println("hits:", a.Hits)
}

$ go run main.go✓ runs

hits: 2

class Counter(var hits: Int)

fun main() {
    val a = Counter(0)
    val b = a

    a.hits++
    b.hits++
    println("hits: ${a.hits}")
}

$ kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar✓ runs

hits: 2

class Counter:
    def __init__(self):
        self.hits = 0


a = Counter()
b = a

a.hits += 1
b.hits += 1
print("hits:", a.hits)

$ python3 main.py✓ runs

hits: 2

class Counter {
  hits = 0;
}

const a = new Counter();
const b = a;

a.hits += 1;
b.hits += 1;
console.log("hits:", a.hits);

$ tsc --strict --module nodenext --types node main.ts && node main.js✓ runs

hits: 2

class Counter {
    int hits = 0;
}

public class Main {
    public static void main(String[] args) {
        Counter a = new Counter();
        Counter b = a;

        a.hits++;
        b.hits++;
        System.out.println("hits: " + a.hits);
    }
}

$ javac Main.java && java Main✓ runs

hits: 2

var a = new Counter();
var b = a;

a.Hits++;
b.Hits++;
Console.WriteLine($"hits: {a.Hits}");

class Counter
{
    public int Hits;
}

$ dotnet run✓ runs

hits: 2

#include <stdio.h>
#include <stdlib.h>

struct Counter {
    int hits;
};

int main(void) {
    struct Counter *a = calloc(1, sizeof *a);
    struct Counter *b = a;

    a->hits++;
    b->hits++;
    printf("hits: %d\n", a->hits);

    free(a);
    return 0;
}

$ gcc -Wall -Wextra main.c -o main && ./main✓ runs

hits: 2

#include <iostream>
#include <memory>

struct Counter {
    int hits = 0;
};

int main() {
    auto a = std::make_shared<Counter>();
    auto b = a;

    a->hits++;
    b->hits++;
    std::cout << "hits: " << a->hits << "\n";
}

$ g++ -std=c++20 -Wall -Wextra main.cpp -o main && ./main✓ runs

hits: 2

What does the compiler say? Guess first, then open.

$ cargo buildWhat is E0594?

error[E0594]: cannot assign to data in an `Rc`
  --> src/main.rs:11:5
   |
11 |     a.hits += 1;
   |     ^^^^^^^^^^^ cannot assign
   |
   = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `Rc<Counter>`

error[E0594]: cannot assign to data in an `Rc`
  --> src/main.rs:12:5
   |
12 |     b.hits += 1;
   |     ^^^^^^^^^^^ cannot assign
   |
   = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `Rc<Counter>`

What happens in Go

Go runs this and prints hits: 2. Both names are the same pointer and either may change the struct. Nothing checks who else is using it.

What happens in Kotlin

Kotlin runs this and prints hits: 2. a and b are two references to one object, and a var property can be changed through either.

What happens in Python

Python prints hits: 2. b = a makes a second name for the same object.

What happens in TypeScript

Prints hits: 2. a and b refer to one object and either may change its field.

What happens in Java

Java runs this and prints hits: 2. b = a copies the reference, not the object.

What happens in C#

C# runs this and prints hits: 2. A class instance is shared by reference.

What happens in C

C runs this and prints hits: 2. Two pointers to one struct, with nothing to say who may write.

What happens in C++

C++ runs this and prints hits: 2. A std::shared_ptr<Counter> counts its owners as Rc does and lets every owner change the value. The read-only form is shared_ptr<const Counter>, which is what Rc<Counter> is.

What Rust sees

Rc<Counter> hands out only shared references (&Counter), because any other owner may be reading the value at the same time. a.hits += 1 needs a unique one (&mut), and the Rc has no way to give it.

Why Rust says no

This is the borrowing rule from earlier lessons, applied to owners: any number of readers, or one writer. The compiler cannot know how many owners an Rc has, because the count changes while the program runs, so Rc never hands out &mut, even to a single owner. When you do need to change shared data, RefCell moves the same check to run time, as fixed.rs does: it allows the write when no other borrow is alive, and panics when one is.

The fix

Compiles and runs.

Rust, fixedsrc/main.rsRun ↗Copy

use std::cell::RefCell;
use std::rc::Rc;

struct Counter {
    hits: u32,
}

fn main() {
    let a = Rc::new(RefCell::new(Counter { hits: 0 }));
    let b = Rc::clone(&a);

    a.borrow_mut().hits += 1;
    b.borrow_mut().hits += 1;
    println!("hits: {}", a.borrow().hits);
}

$ cargo run

hits: 2

The toolkit

Outputs on this page come from Linux on 64-bit ARM with Rust 1.99.1, built in debug mode.

What makes a pointer smart

A reference (&T) borrows a value that someone else owns. A smart pointer is a struct that owns the data it points to, usually on the heap; implements Deref, so *p and p.method() reach the data; and implements Drop, so the data is cleaned up when the pointer goes out of scope. Common traits teaches Deref and Drop; this page uses them.

Rustsrc/main.rsRun ↗Copy

struct Noisy(&'static str);

impl Drop for Noisy {
    fn drop(&mut self) {
        println!("drop {}", self.0);
    }
}

fn main() {
    let value = Noisy("value");
    let r = &value; // a reference reaches the value and owns nothing
    println!("through r: {}", r.0);
    {
        let b = Box::new(Noisy("boxed")); // owns a value on the heap
        println!("through b: {}", b.0); // reaches it like a reference
        println!("size_of &Noisy: {}", size_of::<&Noisy>());
        println!("size_of Box<Noisy>: {}", size_of::<Box<Noisy>>());
    } // b goes: its Noisy is dropped and the heap memory freed
    println!("after the block");
} // r goes and nothing happens; value is dropped here

$ cargo run

through r: value
through b: boxed
size_of &Noisy: 8
size_of Box<Noisy>: 8
drop boxed
after the block
drop value

r owns nothing, so nothing happens when it goes. b’s Noisy is dropped at the closing brace of its block. By that definition this page has two smart pointers and three types that go with them:

• Box<T>: one owner, the value on the heap.
• Rc<T>: several owners, counted. Read-only.
• Cell<T> and RefCell<T> change a value through a shared reference. They are not pointers: only the guards RefCell::borrow returns deref.
• Weak<T> is a link that does not count as an owner. It does not deref: you upgrade() it to an Rc first (check-no-deref.fail.rs).

Because Box and Rc implement Deref, you rarely write the *. A method of the value works on the pointer, and a &Box<String> or &Rc<String> is accepted where a &str is wanted:

Rustsrc/main.rsRun ↗Copy

use std::rc::Rc;

fn shout(text: &str) -> String {
    text.to_uppercase()
}

fn main() {
    let boxed = Box::new(String::from("boxed"));
    let shared = Rc::new(String::from("shared"));

    // methods of the String inside are reachable directly
    println!("len: {} and {}", boxed.len(), shared.len());

    // &Box<String> and &Rc<String> become &String, then &str
    println!("{} and {}", shout(&boxed), shout(&shared));

    // * steps through one pointer by hand
    let inner: &String = &*shared;
    println!("inner: {inner}");
}

$ cargo run

len: 5 and 6
BOXED and SHARED
inner: shared

Box<T>: one owner, on the heap

Ownership introduced Box::new and two reasons to use it. Here is the first with numbers, and a third.

A type that contains itself. An expression tree holds expressions. Written directly, the compiler cannot give Expr a size:

Rustsrc/main.rs✗ won't compileCopy

enum Expr {
    Num(i64),
    Add(Expr, Expr),
}

fn main() {
    let e = Expr::Add(Expr::Num(1), Expr::Num(2));
    let _ = e;
}

$ cargo buildWhat is E0072?

error[E0072]: recursive type `Expr` has infinite size
 --> src/main.rs:1:1
  |
1 | enum Expr {
  | ^^^^^^^^^
2 |     Num(i64),
3 |     Add(Expr, Expr),
  |         ---- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
3 |     Add(Box<Expr>, Expr),
  |         ++++    +

A Box<Expr> is one pointer, whatever it points at, so the size is known:

Rustsrc/main.rsRun ↗Copy

enum Expr {
    Num(i64),
    Add(Box<Expr>, Box<Expr>),
    Neg(Box<Expr>),
}

fn eval(e: &Expr) -> i64 {
    match e {
        Expr::Num(n) => *n,
        Expr::Add(a, b) => eval(a) + eval(b),
        Expr::Neg(a) => -eval(a),
    }
}

fn main() {
    // 1 + -(2 + 3)
    let e = Expr::Add(
        Box::new(Expr::Num(1)),
        Box::new(Expr::Neg(Box::new(Expr::Add(
            Box::new(Expr::Num(2)),
            Box::new(Expr::Num(3)),
        )))),
    );
    println!("eval: {}", eval(&e));
    println!("size_of Box<Expr>: {}", size_of::<Box<Expr>>());
    println!("size_of Expr: {}", size_of::<Expr>());
}

$ cargo run

eval: -4
size_of Box<Expr>: 8
size_of Expr: 24

An Expr is 24 bytes however deep the tree is; the depth lives on the heap.

Coming from Go

Go writes the pointer field itself; Box adds one owner and an automatic free.

Gomain.goCopy

package main

import "fmt"

// the field is a pointer you write yourself; nil ends the tree
type Expr struct {
  Value       int
  Left, Right *Expr
}

func main() {
  tree := &Expr{1, &Expr{2, nil, nil}, &Expr{3, nil, nil}}
  fmt.Println("left child:", tree.Left.Value)
}

$ go run main.go

left child: 2

Coming from Java, Kotlin or C#

In your language a class field already holds a reference, so a class can contain another of itself. A Rust struct stores its fields inline, so the pointer is written as Box.

Coming from Java

JavaMain.javaCopy

public class Main {
    // a field of class type is a reference, so a class can hold another of itself
    static class Expr {
        int value;
        Expr left, right;

        Expr(int value, Expr left, Expr right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        Expr tree = new Expr(1, new Expr(2, null, null), new Expr(3, null, null));
        System.out.println("left child: " + tree.left.value);
    }
}

$ javac Main.java && java Main

left child: 2

Coming from Kotlin

KotlinMain.ktCopy

// a class property holds a reference, so a class can hold another of itself
class Expr(val value: Int, val left: Expr?, val right: Expr?)

fun main() {
    val tree = Expr(1, Expr(2, null, null), Expr(3, null, null))
    println("left child: ${tree.left?.value}")
}

$ kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar

left child: 2

Coming from C#

A C# struct is inline too, and cannot contain itself:

C#Program.cs✗ won't compileCopy

// a struct stores its fields inline, so it cannot contain itself
struct Expr
{
    public int Value;
    public Expr Left;
    public Expr Right;
}

class Program
{
    static void Main()
    {
        var e = new Expr();
        System.Console.WriteLine(e.Value);
    }
}

$ dotnet run

Program.cs(5,17): error CS0523: Struct member 'Expr.Left' of type 'Expr' causes a cycle in the struct layout

A pointer that can be absent. A box is never null, so the compiler uses the null address for None. The Option docs guarantee this for Option<Box<U>> and Option<&U>:

Rustsrc/main.rsRun ↗Copy

use std::rc::Rc;

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

fn main() {
    println!("Box<i32>: {}", size_of::<Box<i32>>());
    println!("Option<Box<i32>>: {}", size_of::<Option<Box<i32>>>());
    println!("Option<&i32>: {}", size_of::<Option<&i32>>());
    println!("Option<Rc<i32>>: {}", size_of::<Option<Rc<i32>>>());
    println!("i32: {}", size_of::<i32>());
    println!("Option<i32>: {}", size_of::<Option<i32>>());
    println!("Option<u64>: {}", size_of::<Option<u64>>());
    println!("Node: {}", size_of::<Node>());

    let list = Node {
        value: 1,
        next: Some(Box::new(Node {
            value: 2,
            next: None,
        })),
    };
    println!("second: {:?}", list.next.as_ref().map(|n| n.value));
}

$ cargo run

Box<i32>: 8
Option<Box<i32>>: 8
Option<&i32>: 8
Option<Rc<i32>>: 8
i32: 4
Option<i32>: 8
Option<u64>: 16
Node: 16
second: Some(2)

Option<Box<i32>> is as big as the box. Option<u64> needs a separate tag and doubles. Option<Box<Node>> is how a linked list says “the next node, or the end”.

A chain of boxes is also freed by a chain of calls: dropping a box drops its node, which drops the next box. A long list can run out of stack:

Rustsrc/main.rs! exits with code -6Run ↗Copy

struct Node {
    value: u32,
    next: Option<Box<Node>>,
}

fn main() {
    let mut head: Option<Box<Node>> = None;
    for value in 0..1_000_000 {
        head = Some(Box::new(Node { value, next: head }));
    }

    let mut len = 0;
    let mut at = &head;
    while let Some(node) = at {
        len += 1;
        at = &node.next;
    }
    println!(
        "built a list of {len}, top value {}",
        head.as_ref().map_or(0, |n| n.value)
    );
} // head is dropped here: one Box frees the next, which frees the next, ...

$ cargo run

built a list of 1000000, top value 999999

thread 'main' (1) has overflowed its stack
fatal runtime error: stack overflow, aborting

This is a debug build. Compiled by hand with rustc -O in the same image it overflowed too, but this runner builds debug only, so no release run is shown. The first exercise fixes it. For Box<dyn Shape>, see Trait objects.

Rc<T>: several owners

Ownership showed the count with a Drop. Here is what the count means for the data:

Rustsrc/main.rsRun ↗Copy

use std::rc::Rc;

fn main() {
    let mut a = Rc::new(vec![1, 2, 3]);
    println!("owners: {}", Rc::strong_count(&a));
    println!("size_of Rc<Vec<i32>>: {}", size_of::<Rc<Vec<i32>>>());

    {
        let b = Rc::clone(&a); // a second owner of the same Vec
        println!("owners: {}", Rc::strong_count(&a));
        println!("same Vec: {}", Rc::ptr_eq(&a, &b));
        println!("same buffer: {}", a.as_ptr() == b.as_ptr());
        println!("get_mut while shared: {:?}", Rc::get_mut(&mut a));
    } // b goes: the count drops, the Vec stays

    println!("owners: {}", Rc::strong_count(&a));
    println!("get_mut when alone: {:?}", Rc::get_mut(&mut a));

    let copy: Vec<i32> = (*a).clone(); // this one really copies the numbers
    println!("copy has its own buffer: {}", copy.as_ptr() != a.as_ptr());
}

$ cargo run

owners: 1
size_of Rc<Vec<i32>>: 8
owners: 2
same Vec: true
same buffer: true
get_mut while shared: None
owners: 1
get_mut when alone: Some([1, 2, 3])
copy has its own buffer: true

• Rc::clone copied an 8-byte pointer and added one to the count. a and b have the same buffer.
• (*a).clone() is the other thing, a new Vec with its own buffer.
• Rc::get_mut gives a &mut only while there is no other Rc or Weak (check-get-mut-weak.rs).

An Rc hands out only shared references, so the gotcha near the top is an error: a.hits += 1 needs a &mut. A lone Rc is read-only too (check-rc-single.fail.rs): the compiler cannot see the count, which changes at run time. Moving the value out is refused as well, which Box allowed (check-table.rs):

Rustsrc/main.rs✗ won't compileCopy

use std::rc::Rc;

fn main() {
    let shared = Rc::new(String::from("x"));
    let owned: String = *shared;
    println!("{owned}");
}

$ cargo buildWhat is E0507?

error[E0507]: cannot move out of an `Rc`
 --> src/main.rs:5:25
  |
5 |     let owned: String = *shared;
  |                         ^^^^^^^ move occurs because value has type `String`, which does not implement the `Copy` trait
  |
help: consider removing the dereference here
  |
5 -     let owned: String = *shared;
5 +     let owned: String = shared;
  |
help: consider cloning the value if the performance cost is acceptable
  |
5 -     let owned: String = *shared;
5 +     let owned: String = shared.clone();

You can also stop sharing before a change. Rc::make_mut gives a &mut, and if other owners exist it first copies the value for this one:

Rustsrc/main.rsRun ↗Copy

use std::rc::Rc;

fn main() {
    let mut mine = Rc::new(vec![1, 2, 3]);
    let theirs = Rc::clone(&mine);
    println!("owners: {}", Rc::strong_count(&mine));

    // Rc::make_mut: change the value; if others share it, copy it first
    Rc::make_mut(&mut mine).push(4);
    println!("mine: {:?}", mine);
    println!("theirs: {:?}", theirs);
    println!(
        "owners now: {} and {}",
        Rc::strong_count(&mine),
        Rc::strong_count(&theirs)
    );
    println!("same Vec: {}", Rc::ptr_eq(&mine, &theirs));

    // alone, it changes the value in place
    drop(theirs);
    let before = Rc::as_ptr(&mine);
    Rc::make_mut(&mut mine).push(5);
    println!("mine: {:?}", mine);
    println!("same allocation: {}", Rc::as_ptr(&mine) == before);
}

$ cargo run

owners: 2
mine: [1, 2, 3, 4]
theirs: [1, 2, 3]
owners now: 1 and 1
same Vec: false
mine: [1, 2, 3, 4, 5]
same allocation: true

theirs kept the old Vec and mine got its own. Once alone, mine changed in place (same allocation: true). It needs T: Clone and copies the whole value the first time, so it suits data read by many and rarely changed. If owners must see each other’s changes, RefCell is next.

Cell and RefCell: change it through a shared reference

Mutable borrows gave the rule: any number of readers, or one writer. Interior mutability keeps the rule and checks it at run time, in types that change their contents through &self.

Cell<T> never lends a reference into its value. get copies out, set and replace put a new one in. That needs no bookkeeping, and Cell<u32> is 4 bytes:

Rustsrc/main.rsRun ↗Copy

use std::cell::Cell;

struct Page {
    title: String,
    views: Cell<u32>,
}

impl Page {
    fn show(&self) -> String {
        self.views.set(self.views.get() + 1); // &self, yet the count changes
        format!("{} (view {})", self.title, self.views.get())
    }
}

fn main() {
    let page = Page {
        title: String::from("Home"),
        views: Cell::new(0),
    };
    println!("{}", page.show());
    println!("{}", page.show());
    println!("replace returns the old value: {}", page.views.replace(10));
    println!("views: {}", page.views.get());
    println!("size_of Cell<u32>: {}", size_of::<Cell<u32>>());
}

$ cargo run

Home (view 1)
Home (view 2)
replace returns the old value: 2
views: 10
size_of Cell<u32>: 4

get needs T: Copy: on a Cell<String> it is a compile error, and you replace or take instead.

RefCell<T> lends references, and counts the loans. borrow() and borrow_mut() return guards, and the loan lasts until the guard is dropped:

Rustsrc/main.rsRun ↗Copy

use std::cell::RefCell;

fn main() {
    let list = RefCell::new(vec![1, 2]); // not `mut`: it is changed through &
    list.borrow_mut().push(3);
    println!("list: {:?}", list.borrow());

    let reader = list.borrow(); // a shared borrow, alive until `reader` goes
    println!("second reader ok: {}", list.try_borrow().is_ok());
    println!("writer ok: {}", list.try_borrow_mut().is_ok());
    println!("the refusal: {:?}", list.try_borrow_mut().err());
    drop(reader);
    println!("writer ok now: {}", list.try_borrow_mut().is_ok());

    println!("size_of RefCell<()>: {}", size_of::<RefCell<()>>());
    println!("size_of Vec<i32>: {}", size_of::<Vec<i32>>());
    println!(
        "size_of RefCell<Vec<i32>>: {}",
        size_of::<RefCell<Vec<i32>>>()
    );
}

$ cargo run

list: [1, 2, 3]
second reader ok: true
writer ok: false
the refusal: Some(BorrowMutError)
writer ok now: true
size_of RefCell<()>: 8
size_of Vec<i32>: 24
size_of RefCell<Vec<i32>>: 32

The counter costs space: RefCell<()> is 8 bytes, a RefCell<Vec<i32>> is 32, the 24-byte Vec plus that counter. try_borrow_mut gives Err(BorrowMutError) rather than a panic. The unchecked version compiles, and fails when it runs:

Rustsrc/main.rs! panics at runtimeRun ↗Copy

use std::cell::RefCell;

fn main() {
    let list = RefCell::new(vec![1, 2]);
    let first = list.borrow_mut();
    println!("first borrow is alive: {}", first.len());
    let second = list.borrow_mut(); // compiles; fails when it runs
    println!("never printed: {}", second.len());
}

$ cargo run

first borrow is alive: 2

thread 'main' (1) panicked at src/main.rs:7:23:
RefCell already borrowed
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

That is the trade: a violation is a panic at run time, where &mut makes it a compile error. Use them where the program is correct but the compiler cannot see why, such as a cache behind &self (the memo exercise).

Rc<RefCell<T>>: shared and changeable

Put the two together and every owner can change the value, one at a time. Closures are the usual reason: each listener below is a Box<dyn Fn>, which may only read what it captured, yet all add to one record:

Rustsrc/main.rsRun ↗Copy

use std::cell::RefCell;
use std::rc::Rc;

fn main() {
    // what the listeners saw; every listener must be able to add to it
    let seen = Rc::new(RefCell::new(Vec::new()));

    let mut listeners: Vec<Box<dyn Fn(&str)>> = Vec::new();
    for name in ["audit", "mail"] {
        let seen = Rc::clone(&seen); // each closure owns a share
        listeners.push(Box::new(move |event| {
            seen.borrow_mut().push(format!("{name}: {event}"));
        }));
    }

    for event in ["login", "logout"] {
        for listener in &listeners {
            listener(event);
        }
    }

    println!("owners: {}", Rc::strong_count(&seen));
    println!(
        "size_of RefCell<Vec<String>>: {}",
        size_of::<RefCell<Vec<String>>>()
    );
    for line in seen.borrow().iter() {
        println!("{line}");
    }
}

$ cargo run

owners: 3
size_of RefCell<Vec<String>>: 32
audit: login
mail: login
audit: logout
mail: logout

let seen = Rc::new(RefCell::new(Vec::new())); each closure captures Rc::clone(&seen)

Three owners, one Vec. The closures really live in the boxes of listeners; their pointers are drawn here beside the variable. The counts and the borrow flag sit beside the Vec. A RefCell> is 32 bytes: the flag and the 24-byte Vec. The order of the cells is not promised.

When will you write this? Less often than tutorials suggest, so ask first who the one owner is. A function that needs the data for a while takes & or &mut; an ID or an index often replaces a second owner (Ownership’s advice); parts that report results can send them on a channel. Rc<RefCell<T>> is right when the sharing is part of the program’s shape:

• closures or callbacks that each change the same state, as above (Closures);
• a tree or graph whose nodes point back (the next sections);
• a test double that records the calls made to it while the code under test owns it.

Its costs: mistakes become panics, such as a borrow() held across a call that writes:

Rustsrc/main.rs! panics at runtimeRun ↗Copy

use std::cell::RefCell;
use std::rc::Rc;

fn main() {
    let log = Rc::new(RefCell::new(vec![String::from("start")]));
    let also_log = Rc::clone(&log);

    // the borrow() lasts for the whole loop
    for line in log.borrow().iter() {
        println!("saw: {line}");
        also_log.borrow_mut().push(format!("after {line}"));
    }
}

$ cargo run

saw: start

thread 'main' (1) panicked at src/main.rs:11:18:
RefCell already borrowed
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Finish the read first, as here:

Rustsrc/main.rsRun ↗Copy

use std::cell::RefCell;
use std::rc::Rc;

fn main() {
    let log = Rc::new(RefCell::new(vec![String::from("start")]));
    let also_log = Rc::clone(&log);

    // copy the lines out; the borrow ends at the semicolon
    let lines: Vec<String> = log.borrow().clone();
    for line in &lines {
        println!("saw: {line}");
        also_log.borrow_mut().push(format!("after {line}"));
    }
    println!("log: {:?}", log.borrow());
}

$ cargo run

saw: start
log: ["start", "after start"]

It works on one thread only (below), and ownership is no longer visible in the types. The borrow checker lesson shows how to restructure.

Passing an Rc around

A function that only reads takes a &Config; &Rc<Config> derefs to it. Take an Rc<Config> only when the function keeps a share, and the caller writes Rc::clone(&config):

Rustsrc/main.rsRun ↗Copy

use std::rc::Rc;

struct Config {
    name: String,
}

struct Worker {
    config: Rc<Config>, // keeps its own share
}

// reads only: a plain reference is enough, and works for any owner
fn describe(config: &Config) -> String {
    format!("config {}", config.name)
}

// keeps a share: takes an Rc by value, so the caller decides to clone
fn hire(config: Rc<Config>) -> Worker {
    Worker { config }
}

fn main() {
    let config = Rc::new(Config {
        name: String::from("prod"),
    });
    println!("{}", describe(&config)); // &Rc<Config> becomes &Config
    println!("owners: {}", Rc::strong_count(&config));

    let a = hire(Rc::clone(&config));
    let b = hire(Rc::clone(&config));
    println!("owners: {}", Rc::strong_count(&config));
    println!("{} and {}", describe(&a.config), describe(&b.config));
}

$ cargo run

config prod
owners: 1
owners: 3
config prod and config prod

Rc::clone(&x) says “another owner”; x.clone() reads like a data copy.

Cycles and Weak<T>

Cycles are not exotic: a child that holds its parent, a doubly linked list. Two Rcs that own each other never reach zero. This program makes one, with a Drop that prints:

Rustsrc/main.rsRun ↗Copy

use std::cell::RefCell;
use std::rc::Rc;

struct Node {
    name: &'static str,
    other: RefCell<Option<Rc<Node>>>,
}

impl Drop for Node {
    fn drop(&mut self) {
        println!("drop {}", self.name);
    }
}

fn node(name: &'static str) -> Rc<Node> {
    Rc::new(Node {
        name,
        other: RefCell::new(None),
    })
}

fn main() {
    let probe;
    {
        let a = node("a");
        let b = node("b");
        *a.other.borrow_mut() = Some(Rc::clone(&b)); // a owns b
        *b.other.borrow_mut() = Some(Rc::clone(&a)); // b owns a
        println!(
            "owners of a: {}, owners of b: {}",
            Rc::strong_count(&a),
            Rc::strong_count(&b)
        );
        probe = Rc::downgrade(&a);
    } // a and b go; each count falls from 2 to 1, not to 0
    println!(
        "after the block, a is still alive: {}",
        probe.upgrade().is_some()
    );
}

$ cargo run

owners of a: 2, owners of b: 2
after the block, a is still alive: true

No drop line appears. The nodes are unreachable from the program, and still alive (upgrade found one). Leaking is allowed, and nothing reclaims a cycle. A Weak<T> is a link that does not count as an owner. upgrade() gives Some(Rc<T>) while the value lives, and None after. A parent owns its children; a child points back with a Weak:

Rustsrc/main.rsRun ↗Copy

use std::cell::RefCell;
use std::rc::{Rc, Weak};

struct Node {
    name: &'static str,
    parent: RefCell<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}

impl Drop for Node {
    fn drop(&mut self) {
        println!("drop {}", self.name);
    }
}

fn node(name: &'static str) -> Rc<Node> {
    Rc::new(Node {
        name,
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(Vec::new()),
    })
}

fn main() {
    let leaf = node("leaf");
    println!(
        "leaf parent: {:?}",
        leaf.parent.borrow().upgrade().map(|p| p.name)
    );
    {
        let root = node("root");
        root.children.borrow_mut().push(Rc::clone(&leaf)); // the parent owns the child
        *leaf.parent.borrow_mut() = Rc::downgrade(&root); // the child only points back
        println!(
            "root: strong {}, weak {}",
            Rc::strong_count(&root),
            Rc::weak_count(&root)
        );
        println!(
            "leaf: strong {}, weak {}",
            Rc::strong_count(&leaf),
            Rc::weak_count(&leaf)
        );
        println!(
            "leaf parent: {:?}",
            leaf.parent.borrow().upgrade().map(|p| p.name)
        );
    } // root goes: its count was 1, so it is dropped now
    println!(
        "leaf parent: {:?}",
        leaf.parent.borrow().upgrade().map(|p| p.name)
    );
    println!("leaf: strong {}", Rc::strong_count(&leaf));
}

$ cargo run

leaf parent: None
root: strong 1, weak 1
leaf: strong 2, weak 0
leaf parent: Some("root")
drop root
leaf parent: None
leaf: strong 1
drop leaf

root owns leaf; leaf.parent is a Weak pointing back

The counts are the ones the program printed. leaf has two owners, the variable and root's children. root has one, so it is freed when the variable goes, and the Weak then upgrades to None.

The other fix is not to point back at all: keep an index or an ID, as Ownership shows.

Across threads: Arc<T>

An Rc updates its count without protection, so two threads could corrupt it. The compiler refuses to send one to a thread:

Rustsrc/main.rs✗ won't compileCopy

use std::rc::Rc;
use std::thread;

fn main() {
    let numbers = Rc::new(vec![1, 2, 3]);
    let for_thread = Rc::clone(&numbers);
    let handle = thread::spawn(move || println!("in the thread: {:?}", for_thread));
    handle.join().unwrap();
    println!("in main: {:?}", numbers);
}

$ cargo buildWhat is E0277?

error[E0277]: `Rc<Vec<i32>>` cannot be sent between threads safely
 --> src/main.rs:7:32
  |
7 |     let handle = thread::spawn(move || println!("in the thread: {:?}", for_thread));
  |                  ------------- -------^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |                  |             |
  |                  |             `Rc<Vec<i32>>` cannot be sent between threads safely
  |                  |             within this `{closure@src/main.rs:7:32: 7:39}`
  |                  required by a bound introduced by this call
  |
  = help: within `{closure@src/main.rs:7:32: 7:39}`, the trait `Send` is not implemented for `Rc<Vec<i32>>`
note: required because it's used within this closure
 --> src/main.rs:7:32
  |
7 |     let handle = thread::spawn(move || println!("in the thread: {:?}", for_thread));
  |                                ^^^^^^^
  ... (notes pointing into the standard library trimmed)

Send marks the types that may move to another thread (Reading signatures; the trait is in Send and Sync). Arc<T> is the same API with an atomic count. thread::spawn runs a closure on a new thread and join waits for it (Threads):

Rustsrc/main.rsRun ↗Copy

use std::sync::Arc;
use std::thread;

fn main() {
    let numbers = Arc::new(vec![1, 2, 3]);
    let for_thread = Arc::clone(&numbers); // the same call, with an atomic count
    let handle = thread::spawn(move || println!("in the thread: {:?}", for_thread));
    handle.join().unwrap();
    println!("in main: {:?}", numbers);
    println!("owners: {}", Arc::strong_count(&numbers));
}

$ cargo run

in the thread: [1, 2, 3]
in main: [1, 2, 3]
owners: 1

A RefCell<i32> can move to another thread, but two threads cannot share one: Sync marks types that may be shared, and RefCell lacks it. The thread-safe Rc<RefCell<T>> is Arc<Mutex<T>> (Shared state). A Mutex<T> is a lock that owns the data it guards, with one writer at a time. A second thread that asks while it is held waits its turn (check-mutex-wait.rs). The same thread asking twice does not get a RefCell-style panic you can rely on: the lock docs say it might deadlock.

Which one?

You want	Use
one owner, on the heap (recursive type, large value)	Box<T>
several owners, one thread, read-only	Rc<T>
several owners, several threads, read-only	Arc<T>
change a Copy value through &	Cell<T>
change any value through &, checked when it runs	RefCell<T>
change a value from several threads	Mutex<T> (a lock around the data), usually inside an Arc
several owners, one thread, changeable	Rc<RefCell<T>>
several owners, several threads, changeable	Arc<Mutex<T>>
a link that must not keep the value alive	Weak<T>

check-table.rs asserts a fact for each row (a RefCell refuses a writer while a reader is alive, four threads add up to 4 under a Mutex, and so on). “One thread, read-only” is shown by rc-thread.fail.rs and rc-write.fail.rs.

Translating from what you know

Coming from Go, Java, Kotlin, C#, Python or TypeScript

In your language an object (in Go, a pointer) is already shared by assignment, and a mutable one can be changed through any name. Three things differ:

• Most sharing is a call. Passing an object to a function that uses it for the call is a plain & or &mut. Rc is for what remains: several owners, none outliving the others in a way the compiler can see.
• Changing is a second choice. Rc is read-only; RefCell adds change, and a second writer panics.
• Cycles are yours to avoid. The programs below show a collector reclaiming one.

Coming from Go

Go has no owning pointer types: *T is a plain pointer, and the collector frees what is unreachable. defer runs at the end of a function; Drop when the value’s scope ends, which can be earlier. Go 1.24 added a weak package (release notes). The collector reclaims a cycle:

Gomain.goCopy

package main

import (
  "fmt"
  "runtime"
  "weak"
)

type Node struct{ other *Node }

func makeCycle() weak.Pointer[Node] {
  a := &Node{}
  b := &Node{}
  a.other = b
  b.other = a
  return weak.Make(a) // does not keep a alive
}

func main() {
  w := makeCycle()
  runtime.GC()
  fmt.Println("cycle collected:", w.Value() == nil)
}

$ go run main.go

cycle collected: true

In Go	In Rust
f(p), p used only during the call	&T or &mut T, no smart pointer
q := p, kept	Rc::clone(&p): counted, read-only
q.field = 1 through any copy	Rc<RefCell<T>>: q.borrow_mut().field = 1
Next *Node, nil ends the list	Option<Box<Node>> (an optional argument is Option<&T>)
defer f.Close()	Drop on the value
weak.Make(p), w.Value()	Rc::downgrade(&p), w.upgrade()
a pointer shared by goroutines, a sync.Mutex beside it	Arc<Mutex<T>>, the data inside the lock. Rc<RefCell<T>> is the same idea for one thread, which Go need not tell apart

Coming from Java, Kotlin or C#

Your collector reclaims a cycle by itself, so you never need WeakReference for that. Each program below builds a cycle, keeps one weak reference, and collects. System.gc() is a request, so Java and Kotlin ask up to twenty times; .NET’s GC.Collect() forces a blocking collection, but the cycle must be unreachable first, hence NoInlining.

WeakReference has the shape of Weak, not the timing: get() returns null only after a collection has run, while upgrade() returns None the instant the last Rc drops. Weak is for back-pointers; WeakReference is usually for caches. WeakHashMap and SoftReference have no std counterpart; the nearest is a HashMap<K, Weak<V>> whose dead entries you remove yourself.

Coming from Java

JavaMain.javaCopy

import java.lang.ref.WeakReference;

public class Main {
    static class Node {
        Node other;
    }

    static WeakReference<Node> makeCycle() {
        Node a = new Node();
        Node b = new Node();
        a.other = b;
        b.other = a;
        return new WeakReference<>(a); // does not keep a alive
    }

    public static void main(String[] args) throws InterruptedException {
        WeakReference<Node> weak = makeCycle();
        for (int i = 0; i < 20 && weak.get() != null; i++) {
            System.gc(); // a request, so ask a few times
            Thread.sleep(50);
        }
        System.out.println("cycle collected: " + (weak.get() == null));
    }
}

$ javac Main.java && java Main

cycle collected: true

In Java	In Rust
List<String> other = log;	Rc::clone(&log)
log.add(x) through any reference	log.borrow_mut().push(x)
new WeakReference<>(a), get()	Rc::downgrade(&a), upgrade()
a field that may be null	Option<Rc<T>> or Option<Box<T>>
try (var r = open()) { ... }	Drop on the value, no block (Common traits)
synchronized around shared data	Arc<Mutex<T>>

Coming from Kotlin

KotlinMain.ktCopy

import java.lang.ref.WeakReference

class Node {
    var other: Node? = null
}

fun makeCycle(): WeakReference<Node> {
    val a = Node()
    val b = Node()
    a.other = b
    b.other = a
    return WeakReference(a) // does not keep a alive
}

fun main() {
    val weak = makeCycle()
    var i = 0
    while (i < 20 && weak.get() != null) {
        System.gc() // a request, so ask a few times
        Thread.sleep(50)
        i++
    }
    println("cycle collected: ${weak.get() == null}")
}

$ kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar

cycle collected: true

In Kotlin	In Rust
val other = log	Rc::clone(&log)
log.add(x) through any reference	log.borrow_mut().push(x)
WeakReference(a), get()	Rc::downgrade(&a), upgrade()
var next: Node? = null	next: Option<Box<Node>>
r.use { ... }	Drop on the value, no block

Coming from C#

C#Program.csCopy

using System.Runtime.CompilerServices;

var weak = MakeCycle();
GC.Collect();
GC.WaitForPendingFinalizers();
GC.Collect();
Console.WriteLine($"cycle collected: {!weak.IsAlive}");

[MethodImpl(MethodImplOptions.NoInlining)]
static WeakReference MakeCycle()
{
    var a = new Node();
    var b = new Node();
    a.Other = b;
    b.Other = a;
    return new WeakReference(a); // does not keep a alive
}

class Node
{
    public Node? Other;
}

$ dotnet run

cycle collected: True

In C#	In Rust
var other = log;	Rc::clone(&log)
log.Add(x) through any reference	log.borrow_mut().push(x)
new WeakReference(a), IsAlive	Rc::downgrade(&a), upgrade()
Node? Next	Option<Box<Node>>
using var r = Open();	Drop on the value
lock (gate) { ... }	Arc<Mutex<T>>

Coming from Python

CPython frees most objects as Rc does, by counting, and adds a cycle collector. Both are in this program:

Pythonmain.pyCopy

import gc
import weakref


class Node:
    def __init__(self, name):
        self.name = name
        self.other = None

    def __del__(self):
        print("freed", self.name)


def make_cycle():
    a = Node("a")
    b = Node("b")
    a.other = b
    b.other = a
    return weakref.ref(a)  # does not keep a alive


gc.disable()  # keep the automatic cycle collector out of the way

lone = Node("lone")
del lone  # the count falls to zero: freed on the spot, like an Rc
print("after del lone")

ref = make_cycle()  # each node is still referenced by the other
print("after make_cycle: a and b not freed, weakref alive:", ref() is not None)
found = gc.collect()  # the cycle collector finds them
print("gc.collect found garbage:", found > 0)
print("weakref alive now:", ref() is not None)

$ python3 main.py

freed lone
after del lone
after make_cycle: a and b not freed, weakref alive: True
freed a
freed b
gc.collect found garbage: True
weakref alive now: False

lone was freed the moment its count fell to zero. The pair waited for gc.collect(); Rust has no collector to wait for. sys.getrefcount reads one higher than Rc::strong_count, because passing the object adds a temporary reference, and weakref.ref works only on some objects, where Weak<T> takes any T:

Pythonmain.pyCopy

import sys
import weakref

a = []
print("getrefcount, one name:", sys.getrefcount(a))  # the call's own argument counts too
b = a
print("getrefcount, two names:", sys.getrefcount(a))

for value in ([1], 5):
    try:
        weakref.ref(value)
    except TypeError as e:
        print("weakref.ref fails:", e)

$ python3 main.py

getrefcount, one name: 2
getrefcount, two names: 3
weakref.ref fails: cannot create weak reference to 'list' object
weakref.ref fails: cannot create weak reference to 'int' object

In Python	In Rust
f(a), a used only during the call	&T or &mut T, no smart pointer
b = a, kept in a field	Rc::clone(&a), read-only
b.items.append(x) through any name	b.borrow_mut().push(x) on an Rc<RefCell<..>>
weakref.ref(a), ref()	Rc::downgrade(&a), upgrade()
__del__	Drop. CPython runs __del__ at count zero, as above; Rust runs drop where the owner’s scope ends. A cycle waits for gc in Python and leaks in Rust

Coming from TypeScript

V8 reclaims a cycle. Node exposes gc() only when asked, so the program asks from inside (the first lines), and waits a turn of the event loop because a WeakRef target lives until the current job ends:

TypeScriptmain.tsCopy

import * as v8 from "node:v8";
import * as vm from "node:vm";

// node only exposes gc() when asked; this asks from inside the program
v8.setFlagsFromString("--expose-gc");
const gc: () => void = vm.runInNewContext("gc");

class Node {
  other: Node | null = null;
}

function makeCycle(): WeakRef<Node> {
  const a = new Node();
  const b = new Node();
  a.other = b;
  b.other = a;
  return new WeakRef(a); // does not keep a alive
}

async function main() {
  const weak = makeCycle();
  // a WeakRef's target is kept alive until the current job ends
  await new Promise((resolve) => setTimeout(resolve, 0));
  gc();
  console.log("cycle collected:", weak.deref() === undefined);
}

main();

$ tsc --strict --module nodenext --types node main.ts && node main.js

cycle collected: true

WeakRef is not an exact Weak: deref() gives undefined only once the collector has run, while upgrade() gives None the instant the last strong count drops.

In TypeScript	In Rust
f(a), a used only during the call	&T or &mut T, no smart pointer
const b = a;, kept in a field	Rc::clone(&a), read-only
b.items.push(x) through any name	b.borrow_mut().push(x) on an Rc<RefCell<..>>
new WeakRef(a), deref()	Rc::downgrade(&a), upgrade()
WeakMap<object, V>	no counterpart: key by an ID

Coming from C

C has no smart pointers: you malloc, share by copying the pointer, and decide by hand who calls free. An Rc is that discipline written once, in the type. This program does by hand what Rc does:

Cmain.cCopy

#include <stdio.h>
#include <stdlib.h>

// What Rc does, written by hand: a count next to the value, and a free when it hits zero.
struct Shared {
    int count;
    int value;
};

struct Shared *shared_new(int value) {
    struct Shared *s = malloc(sizeof *s);
    s->count = 1;
    s->value = value;
    return s;
}

struct Shared *shared_clone(struct Shared *s) {
    s->count++;
    return s;
}

void shared_drop(struct Shared *s) {
    s->count--;
    if (s->count == 0) {
        printf("count is zero: freeing\n");
        free(s);
    }
}

int main(void) {
    struct Shared *a = shared_new(7);
    struct Shared *b = shared_clone(a);
    printf("owners: %d\n", a->count);
    shared_drop(b);
    printf("owners: %d\n", a->count);
    shared_drop(a);
    return 0;
}

$ gcc -Wall -Wextra main.c -o main && ./main

owners: 2
owners: 1
count is zero: freeing

Forget a shared_drop and it leaks. Call one too many and the extra call reads freed memory (AddressSanitizer: heap-use-after-free):

Cmain.c! fails at runtimeCopy

#include <stdio.h>
#include <stdlib.h>

// What Rc does, written by hand: a count next to the value, and a free when it hits zero.
struct Shared {
    int count;
    int value;
};

struct Shared *shared_new(int value) {
    struct Shared *s = malloc(sizeof *s);
    s->count = 1;
    s->value = value;
    return s;
}

struct Shared *shared_clone(struct Shared *s) {
    s->count++;
    return s;
}

void shared_drop(struct Shared *s) {
    s->count--;
    if (s->count == 0) {
        printf("count is zero: freeing\n");
        free(s);
    }
}

int main(void) {
    struct Shared *a = shared_new(7);
    struct Shared *b = shared_clone(a);
    printf("owners: %d\n", a->count);
    shared_drop(b);
    printf("owners: %d\n", a->count);
    shared_drop(a);
    shared_drop(a); // one call too many: the count was already zero
    return 0;
}

$ gcc -fsanitize=address -g main.c -o main && ./main

owners: 2
owners: 1
count is zero: freeing
=================================================================
==1==ERROR: AddressSanitizer: heap-use-after-free on address 0x············ at pc 0x············ bp 0x············ sp 0x············
READ of size 4 at 0x············ thread T0
    #0 0x············ in shared_drop main.c:23
    #1 0x············ in main main.c:37
    #2 0x············  (/lib/aarch64-linux-gnu/libc.so.6+0x22258)
    #3 0x············ in __libc_start_main (/lib/aarch64-linux-gnu/libc.so.6+0x22338)
    #4 0x············ in _start (main+0xb2c)

0x············ is located 0 bytes inside of 8-byte region [0x············,0x············)
freed by thread T0 here:
    #0 0x············ in free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:52
    #1 0x············ in shared_drop main.c:26
    #2 0x············ in main main.c:36
    #3 0x············  (/lib/aarch64-linux-gnu/libc.so.6+0x22258)
    #4 0x············ in __libc_start_main (/lib/aarch64-linux-gnu/libc.so.6+0x22338)
    #5 0x············ in _start (main+0xb2c)

previously allocated by thread T0 here:
    #0 0x············ in malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69
    #1 0x············ in shared_new main.c:11
    #2 0x············ in main main.c:31
    #3 0x············  (/lib/aarch64-linux-gnu/libc.so.6+0x22258)
    #4 0x············ in __libc_start_main (/lib/aarch64-linux-gnu/libc.so.6+0x22338)
    #5 0x············ in _start (main+0xb2c)

SUMMARY: AddressSanitizer: heap-use-after-free main.c:23 in shared_drop
Shadow bytes around the buggy address:
  0x············: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x············: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x············: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x············: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x············: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x············: fa fa[fd]fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x············: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x············: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x············: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x············: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x············: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==1==ABORTING

In C	In Rust
malloc, one owner, free	Box::new(x), freed by Drop
a struct with a count field, as above	Rc<T>
NULL for “no next node”	None in an Option<Box<T>>, as wide as the pointer (niche.rs)
a pointer the code must not free	a reference &T, or a Weak<T>
a pthread_mutex_t beside the data	Arc<Mutex<T>>, the data inside the lock

Coming from C++

Box<T> is std::unique_ptr<T>, and the difference is the move. A moved-from unique_ptr is specified to be null, so a == nullptr is true. Dereferencing it is undefined behaviour (here it crashed), and nothing at compile time stops the line:

C++main.cpp! fails at runtimeCopy

#include <iostream>
#include <memory>

int main() {
    auto a = std::make_unique<int>(5);
    auto b = std::move(a);
    std::cout << "b: " << *b << "\n";
    std::cout << "a is null: " << (a == nullptr ? "true" : "false") << "\n";
    std::cout << "a: " << *a << "\n"; // compiles; undefined behaviour (it crashed here)
}

$ g++ -std=c++20 -Wall -Wextra main.cpp -o main && ./main

b: 5
a is null: true

Rust refuses it before the program runs:

Rustsrc/main.rs✗ won't compileCopy

fn main() {
    let a = Box::new(5);
    let b = a;
    println!("b: {b}");
    println!("a: {a}");
}

$ cargo buildWhat is E0382?

error[E0382]: borrow of moved value: `a`
 --> src/main.rs:5:19
  |
2 |     let a = Box::new(5);
  |         - move occurs because `a` has type `Box<i32>`, which does not implement the `Copy` trait
3 |     let b = a;
  |             - value moved here
4 |     println!("b: {b}");
5 |     println!("a: {a}");
  |                   ^ value borrowed here after move
  |
help: consider cloning the value if the performance cost is acceptable
  |
3 |     let b = a.clone();
  |              ++++++++

To be fair, a unique_ptr<Node> list crashes the same way when its head is freed (a destructor recursion a million deep); a loop, as in the exercise, is the fix there too:

C++main.cpp! fails at runtimeCopy

#include <iostream>
#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> next;
};

int main() {
    std::unique_ptr<Node> head;
    for (int i = 0; i < 1000000; i++) {
        auto node = std::make_unique<Node>();
        node->value = i;
        node->next = std::move(head);
        head = std::move(node);
    }
    std::cout << "built" << std::endl;
    head.reset(); // each ~Node frees the next one: a recursion a million deep
    std::cout << "freed\n";
}

$ g++ -std=c++20 -Wall -Wextra main.cpp -o main && ./main

built

std::shared_ptr must be safe to copy from different threads (cppreference), so its count is atomic in practice: that is Arc. The standard has no non-atomic shared pointer you can ask for. libstdc++ skips the atomics by itself while the process has one thread (it reads glibc’s __libc_single_threaded; see atomicity.h), and Boost has local_shared_ptr. In C++ the cheap path is a run-time property of the process; Rust makes it a type, and an Rc cannot cross to another thread.

Rc<T> is read-only; its counterpart is shared_ptr<const T>. C++ makes read-only sharing the opt-in, Rust the reverse:

C++main.cpp✗ won't compileCopy

#include <memory>

int main() {
    std::shared_ptr<const int> c = std::make_shared<int>(1);
    *c = 2; // a shared_ptr<const T> is read-only, as an Rc<T> is
}

$ g++ -std=c++20 -Wall -Wextra main.cpp -o main && ./main

main.cpp: In function ‘int main()’:
main.cpp:5:8: error: assignment of read-only location ‘((std::__shared_ptr_access<const int, __gnu_cxx::_S_atomic, false, false>*)(& c))->std::__shared_ptr_access<const int, __gnu_cxx::_S_atomic, false, false>::operator*()’
    5 |     *c = 2; // a shared_ptr<const T> is read-only, as an Rc<T> is
      |     ~~~^~~

Cycles leak with shared_ptr as with Rc, and weak_ptr is the fix, as Weak is:

C++main.cppCopy

#include <iostream>
#include <memory>
#include <string>
#include <vector>

struct Leaky {
    explicit Leaky(std::string n) : name(n) {}
    std::string name;
    std::shared_ptr<Leaky> other;
    ~Leaky() { std::cout << "freed " << name << "\n"; }
};

struct Tree {
    explicit Tree(std::string n) : name(n) {}
    std::string name;
    std::weak_ptr<Tree> parent;
    std::vector<std::shared_ptr<Tree>> children;
    ~Tree() { std::cout << "freed " << name << "\n"; }
};

int main() {
    {
        auto a = std::make_shared<Leaky>("a");
        auto b = std::make_shared<Leaky>("b");
        a->other = b;
        b->other = a;
        std::cout << "owners of a: " << a.use_count() << "\n";
    }
    std::cout << "after the cycle's block: a and b not freed\n";

    {
        auto root = std::make_shared<Tree>("root");
        auto leaf = std::make_shared<Tree>("leaf");
        root->children.push_back(leaf);
        leaf->parent = root; // weak_ptr: does not count
        std::cout << "owners of root: " << root.use_count() << "\n";
    }
    std::cout << "after the tree's block\n";
}

$ g++ -std=c++20 -Wall -Wextra main.cpp -o main && ./main

owners of a: 2
after the cycle's block: a and b not freed
owners of root: 1
freed root
freed leaf
after the tree's block

shared_from_this() on an object no shared_ptr owns throws at run time. Rust needs no helper class: a method can take self: &Rc<Self>, and Rc::new_cyclic hands a value its own Weak while it is built:

C++main.cppCopy

#include <iostream>
#include <memory>

struct Widget : std::enable_shared_from_this<Widget> {
    std::shared_ptr<Widget> share() { return shared_from_this(); }
};

int main() {
    auto owned = std::make_shared<Widget>();
    std::cout << "owners: " << owned->share().use_count() << "\n";

    Widget on_stack; // not owned by any shared_ptr
    try {
        on_stack.share();
    } catch (const std::bad_weak_ptr &e) {
        std::cout << "thrown at run time: bad_weak_ptr\n";
    }
}

$ g++ -std=c++20 -Wall -Wextra main.cpp -o main && ./main

owners: 2
thrown at run time: bad_weak_ptr

Rustsrc/main.rsRun ↗Copy

use std::rc::{Rc, Weak};

struct Widget {
    id: u32,
    me: Weak<Widget>, // a link to itself, filled in while it is built
}

impl Widget {
    // the receiver says: only callable on a Widget that is inside an Rc
    fn share(self: &Rc<Self>) -> Rc<Widget> {
        Rc::clone(self)
    }
}

fn main() {
    let w = Rc::new_cyclic(|me| Widget {
        id: 7,
        me: me.clone(),
    });
    let again = w.share();
    println!("id: {}, owners: {}", again.id, Rc::strong_count(&w));
    println!("own weak link upgrades: {}", w.me.upgrade().is_some());
}

$ cargo run

id: 7, owners: 2
own weak link upgrades: true

In C++	In Rust
std::make_unique<T>(x)	Box::new(x)
std::shared_ptr<T>, atomic count	Arc<T>
std::make_shared<T>(x)	Rc::new(x): counts beside the value, one allocation (Ownership)
std::shared_ptr<const T>	Rc<T>
std::weak_ptr<T>, lock()	Weak<T>, upgrade(): an Option<Rc<T>> you must match
enable_shared_from_this	self: &Rc<Self>, or Rc::new_cyclic
a mutable member in a const method	Cell or RefCell behind &self (the memo exercise)
unique_ptr<FILE, decltype(&fclose)>, a custom deleter	a type with Drop (Common traits)

Going deeper

Rc<str>: a shared string

A pointer to a str, a slice or a dyn Trait is two words (Trait objects). Sizes for this 64-bit runner:

Rustsrc/main.rsRun ↗Copy

use std::fmt::Debug;
use std::rc::Rc;
use std::sync::Arc;

fn main() {
    println!("Box<i32>: {}", size_of::<Box<i32>>());
    println!("Box<str>: {}", size_of::<Box<str>>());
    println!("Box<[i32]>: {}", size_of::<Box<[i32]>>());
    println!("Rc<str>: {}", size_of::<Rc<str>>());
    println!("Arc<str>: {}", size_of::<Arc<str>>());
    println!("Box<dyn Debug>: {}", size_of::<Box<dyn Debug>>());

    let name: Rc<str> = Rc::from("shared text"); // one allocation, no String capacity
    let other = Rc::clone(&name);
    println!("{name} / {other}, owners: {}", Rc::strong_count(&name));
}

$ cargo run

Box<i32>: 8
Box<str>: 16
Box<[i32]>: 16
Rc<str>: 16
Arc<str>: 16
Box<dyn Debug>: 16
shared text / shared text, owners: 2

Rc<str> is a shared string with no spare capacity. It suits text many owners read and nobody changes; cloning it copies no bytes. An Rc<String> points at a String, which points at its text; an Rc<str> holds the text itself.

Practice

Try it

Each exercise has checks in main. Replace the todo!() calls and run until it prints all checks passed. The starters compile and stop at the first todo!().

A stack of boxed nodes

Finish Stack: push, pop, peek, an in-place reverse that relinks the nodes, and a Drop that frees them in a loop. Real code would use a Vec; a list is the smallest program that needs Option<Box<_>>, take() and a custom Drop. Option::take moves a box out of a field you hold by &mut. The checks count allocations and frees: a reverse that builds new nodes fails, a pop that leaks fails, and a million nodes must drop without overflowing the stack.

Starterexercises/linked-stack.rsCopy

use std::alloc::{GlobalAlloc, Layout, System};
use std::sync::atomic::{AtomicUsize, Ordering};

// Counts allocations and frees, so the checks can tell "moved the nodes" from "built
// new ones" and "freed them" from "leaked them". You do not need to read it.
static ALLOCATED: AtomicUsize = AtomicUsize::new(0);
static FREED: AtomicUsize = AtomicUsize::new(0);

struct Counting;

unsafe impl GlobalAlloc for Counting {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        ALLOCATED.fetch_add(1, Ordering::Relaxed);
        unsafe { System.alloc(layout) }
    }
    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
        FREED.fetch_add(1, Ordering::Relaxed);
        unsafe { System.dealloc(ptr, layout) }
    }
}

#[global_allocator]
static COUNTING: Counting = Counting;

fn allocated() -> usize {
    ALLOCATED.load(Ordering::Relaxed)
}

fn freed() -> usize {
    FREED.load(Ordering::Relaxed)
}

struct Node {
    value: u32,
    next: Option<Box<Node>>,
}

/// A stack of numbers: a chain of boxed nodes, newest first.
struct Stack {
    head: Option<Box<Node>>,
}

impl Stack {
    fn new() -> Stack {
        Stack { head: None }
    }

    /// Put `value` on top.
    fn push(&mut self, value: u32) {
        todo!("a new Node whose `next` is the old head (take it with `self.head.take()`)")
    }

    /// Remove and return the top, or None when empty.
    fn pop(&mut self) -> Option<u32> {
        todo!("take the head; the new head is its `next`")
    }

    /// The top, without removing it.
    fn peek(&self) -> Option<&u32> {
        todo!("as_ref() on the head, then look at the node's value")
    }

    /// Turn the stack upside down by relinking the nodes it already has.
    fn reverse(&mut self) {
        todo!("walk the chain with take(), pointing each node's `next` at the one before it")
    }
}

impl Drop for Stack {
    // Dropping a Box drops the node inside it, which drops the next Box, and so on:
    // one stack frame per node. Free the nodes in a loop instead.
    fn drop(&mut self) {}
}

fn main() {
    // push, peek and pop
    let (a_pop, f_pop) = (allocated(), freed());
    let mut s = Stack::new();
    assert_eq!(s.pop(), None);
    assert_eq!(s.peek(), None);
    for v in [1, 2, 3] {
        s.push(v);
    }
    assert_eq!(s.peek(), Some(&3));
    assert_eq!(s.pop(), Some(3));
    assert_eq!(s.pop(), Some(2));
    assert_eq!(s.pop(), Some(1));
    assert_eq!(s.pop(), None);
    assert_eq!(
        allocated() - a_pop,
        freed() - f_pop,
        "pop must free the node it removes"
    );

    // reverse moves the nodes it has: no new allocation
    let mut s = Stack::new();
    for v in 1..=5 {
        s.push(v);
    }
    let before = allocated();
    s.reverse();
    assert_eq!(
        allocated(),
        before,
        "reverse must relink the nodes, not build new ones"
    );
    let popped: Vec<u32> = std::iter::from_fn(|| s.pop()).collect();
    assert_eq!(popped, [1, 2, 3, 4, 5]);

    // an empty stack and a one-node stack reverse to themselves
    let mut s = Stack::new();
    s.reverse();
    assert_eq!(s.pop(), None);
    s.push(9);
    s.reverse();
    assert_eq!(s.pop(), Some(9));

    // dropping a stack frees every node
    let (a0, f0) = (allocated(), freed());
    {
        let mut s = Stack::new();
        for v in 0..10 {
            s.push(v);
        }
    }
    assert_eq!(allocated() - a0, 10);
    assert_eq!(freed() - f0, 10, "every node must be freed");

    // and a long stack is freed without one stack frame per node
    {
        let mut s = Stack::new();
        for v in 0..1_000_000 {
            s.push(v);
        }
    }

    println!("all checks passed");
}

Open in the Rust Playground ↗Run it first: it stops at todo!() with not yet implemented and a hint, and the compiler warns that the parameter is unused. Both are expected. Replace the todo!() with your code and run it again until it prints all checks passed.

Show a solution

One solutionexercises/linked-stack.solution.rsRun ↗Copy

use std::alloc::{GlobalAlloc, Layout, System};
use std::sync::atomic::{AtomicUsize, Ordering};

// Counts allocations and frees, so the checks can tell "moved the nodes" from "built
// new ones" and "freed them" from "leaked them". You do not need to read it.
static ALLOCATED: AtomicUsize = AtomicUsize::new(0);
static FREED: AtomicUsize = AtomicUsize::new(0);

struct Counting;

unsafe impl GlobalAlloc for Counting {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        ALLOCATED.fetch_add(1, Ordering::Relaxed);
        unsafe { System.alloc(layout) }
    }
    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
        FREED.fetch_add(1, Ordering::Relaxed);
        unsafe { System.dealloc(ptr, layout) }
    }
}

#[global_allocator]
static COUNTING: Counting = Counting;

fn allocated() -> usize {
    ALLOCATED.load(Ordering::Relaxed)
}

fn freed() -> usize {
    FREED.load(Ordering::Relaxed)
}

struct Node {
    value: u32,
    next: Option<Box<Node>>,
}

/// A stack of numbers: a chain of boxed nodes, newest first.
struct Stack {
    head: Option<Box<Node>>,
}

impl Stack {
    fn new() -> Stack {
        Stack { head: None }
    }

    /// Put `value` on top.
    fn push(&mut self, value: u32) {
        let next = self.head.take();
        self.head = Some(Box::new(Node { value, next }));
    }

    /// Remove and return the top, or None when empty.
    fn pop(&mut self) -> Option<u32> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.value
        })
    }

    /// The top, without removing it.
    fn peek(&self) -> Option<&u32> {
        self.head.as_ref().map(|node| &node.value)
    }

    /// Turn the stack upside down by relinking the nodes it already has.
    fn reverse(&mut self) {
        let mut rest = self.head.take();
        let mut reversed = None;
        while let Some(mut node) = rest {
            rest = node.next.take();
            node.next = reversed;
            reversed = Some(node);
        }
        self.head = reversed;
    }
}

impl Drop for Stack {
    // Dropping a Box drops the node inside it, which drops the next Box, and so on:
    // one stack frame per node. Free the nodes in a loop instead.
    fn drop(&mut self) {
        let mut rest = self.head.take();
        while let Some(mut node) = rest {
            rest = node.next.take();
        }
    }
}

fn main() {
    // push, peek and pop
    let (a_pop, f_pop) = (allocated(), freed());
    let mut s = Stack::new();
    assert_eq!(s.pop(), None);
    assert_eq!(s.peek(), None);
    for v in [1, 2, 3] {
        s.push(v);
    }
    assert_eq!(s.peek(), Some(&3));
    assert_eq!(s.pop(), Some(3));
    assert_eq!(s.pop(), Some(2));
    assert_eq!(s.pop(), Some(1));
    assert_eq!(s.pop(), None);
    assert_eq!(
        allocated() - a_pop,
        freed() - f_pop,
        "pop must free the node it removes"
    );

    // reverse moves the nodes it has: no new allocation
    let mut s = Stack::new();
    for v in 1..=5 {
        s.push(v);
    }
    let before = allocated();
    s.reverse();
    assert_eq!(
        allocated(),
        before,
        "reverse must relink the nodes, not build new ones"
    );
    let popped: Vec<u32> = std::iter::from_fn(|| s.pop()).collect();
    assert_eq!(popped, [1, 2, 3, 4, 5]);

    // an empty stack and a one-node stack reverse to themselves
    let mut s = Stack::new();
    s.reverse();
    assert_eq!(s.pop(), None);
    s.push(9);
    s.reverse();
    assert_eq!(s.pop(), Some(9));

    // dropping a stack frees every node
    let (a0, f0) = (allocated(), freed());
    {
        let mut s = Stack::new();
        for v in 0..10 {
            s.push(v);
        }
    }
    assert_eq!(allocated() - a0, 10);
    assert_eq!(freed() - f0, 10, "every node must be freed");

    // and a long stack is freed without one stack frame per node
    {
        let mut s = Stack::new();
        for v in 0..1_000_000 {
            s.push(v);
        }
    }

    println!("all checks passed");
}

$ cargo run

all checks passed

Parents own children

A parent owns its children through Rc; a child points back with a Weak (Rc::downgrade makes one, upgrade follows it). The starter’s Person has plain fields, but add_child only receives &Rc<Person>, so it can reach them only through &. Choose the field types (hint: RefCell<Weak<Person>>, because the Weak itself is what gets replaced), update person, and write add_child, parent_of, child_count and path. The checks read the strong and weak counts and count drops, so a strong pointer upward fails.

Starterexercises/family-tree.rsCopy

#![forbid(unsafe_code)]

use std::cell::Cell;
use std::rc::{Rc, Weak};

/// A person in a family tree. Parents own their children; a child only points back.
struct Person {
    name: String,
    parent: Weak<Person>,
    children: Vec<Rc<Person>>,
    dropped: Rc<Cell<u32>>, // shared count of how many Persons have been freed
}

impl Drop for Person {
    fn drop(&mut self) {
        self.dropped.set(self.dropped.get() + 1);
    }
}

fn person(name: &str, dropped: &Rc<Cell<u32>>) -> Rc<Person> {
    Rc::new(Person {
        name: name.to_string(),
        parent: Weak::new(),
        children: Vec::new(),
        dropped: Rc::clone(dropped),
    })
}

/// Make `child` one of `parent`'s children, and `parent` the parent of `child`.
/// You only hold `&Rc<Person>`, so the two fields above cannot be changed as they are:
/// first change their types (and `person`), then fill this in.
fn add_child(parent: &Rc<Person>, child: &Rc<Person>) {
    todo!(
        "wrap the fields in RefCell: RefCell<Weak<Person>> is a weak link you can point somewhere else through &"
    )
}

/// The parent of `person`, if it is still alive.
fn parent_of(person: &Person) -> Option<Rc<Person>> {
    todo!("upgrade the weak link")
}

/// How many children `person` has.
fn child_count(person: &Person) -> usize {
    todo!("the length of the children list")
}

/// The names from the oldest known ancestor down to this person, joined with '/'.
fn path(person: &Person) -> String {
    todo!("walk up with parent_of, then join the names top-down")
}

fn main() {
    let dropped = Rc::new(Cell::new(0));
    let root = person("root", &dropped);
    let mid = person("mid", &dropped);
    let leaf = person("leaf", &dropped);

    add_child(&root, &mid);
    add_child(&mid, &leaf);

    // the parent owns the child; the child must not own the parent
    assert_eq!(Rc::strong_count(&root), 1);
    assert_eq!(Rc::weak_count(&root), 1);
    assert_eq!(Rc::strong_count(&mid), 2);
    assert_eq!(Rc::strong_count(&leaf), 2);

    assert_eq!(path(&root), "root");
    assert_eq!(path(&mid), "root/mid");
    assert_eq!(path(&leaf), "root/mid/leaf");
    assert_eq!(child_count(&root), 1);
    assert_eq!(
        parent_of(&leaf).map(|p| p.name.clone()),
        Some("mid".to_string())
    );

    // dropping the root frees only the root: `mid` is still held by this function
    drop(root);
    assert_eq!(dropped.get(), 1);
    assert!(parent_of(&mid).is_none());
    assert_eq!(path(&leaf), "mid/leaf");

    // dropping the last owner of each frees the rest, and nothing is left over
    drop(mid);
    assert_eq!(dropped.get(), 2);
    drop(leaf);
    assert_eq!(dropped.get(), 3, "every person must be freed");

    println!("all checks passed");
}

Open in the Rust Playground ↗Run it first: it stops at todo!() with not yet implemented and a hint, and the compiler warns that the parameter is unused. Both are expected. Replace the todo!() with your code and run it again until it prints all checks passed.

Show a solution

One solutionexercises/family-tree.solution.rsRun ↗Copy

#![forbid(unsafe_code)]

use std::cell::{Cell, RefCell};
use std::rc::{Rc, Weak};

/// A person in a family tree. Parents own their children; a child only points back.
struct Person {
    name: String,
    parent: RefCell<Weak<Person>>,
    children: RefCell<Vec<Rc<Person>>>,
    dropped: Rc<Cell<u32>>, // shared count of how many Persons have been freed
}

impl Drop for Person {
    fn drop(&mut self) {
        self.dropped.set(self.dropped.get() + 1);
    }
}

fn person(name: &str, dropped: &Rc<Cell<u32>>) -> Rc<Person> {
    Rc::new(Person {
        name: name.to_string(),
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(Vec::new()),
        dropped: Rc::clone(dropped),
    })
}

/// Make `child` one of `parent`'s children, and `parent` the parent of `child`.
fn add_child(parent: &Rc<Person>, child: &Rc<Person>) {
    parent.children.borrow_mut().push(Rc::clone(child));
    *child.parent.borrow_mut() = Rc::downgrade(parent);
}

/// The parent of `person`, if it is still alive.
fn parent_of(person: &Person) -> Option<Rc<Person>> {
    person.parent.borrow().upgrade()
}

/// How many children `person` has.
fn child_count(person: &Person) -> usize {
    person.children.borrow().len()
}

/// The names from the oldest known ancestor down to this person, joined with '/'.
fn path(person: &Person) -> String {
    match parent_of(person) {
        Some(parent) => format!("{}/{}", path(&parent), person.name),
        None => person.name.clone(),
    }
}

fn main() {
    let dropped = Rc::new(Cell::new(0));
    let root = person("root", &dropped);
    let mid = person("mid", &dropped);
    let leaf = person("leaf", &dropped);

    add_child(&root, &mid);
    add_child(&mid, &leaf);

    // the parent owns the child; the child must not own the parent
    assert_eq!(Rc::strong_count(&root), 1);
    assert_eq!(Rc::weak_count(&root), 1);
    assert_eq!(Rc::strong_count(&mid), 2);
    assert_eq!(Rc::strong_count(&leaf), 2);

    assert_eq!(path(&root), "root");
    assert_eq!(path(&mid), "root/mid");
    assert_eq!(path(&leaf), "root/mid/leaf");
    assert_eq!(child_count(&root), 1);
    assert_eq!(
        parent_of(&leaf).map(|p| p.name.clone()),
        Some("mid".to_string())
    );

    // dropping the root frees only the root: `mid` is still held by this function
    drop(root);
    assert_eq!(dropped.get(), 1);
    assert!(parent_of(&mid).is_none());
    assert_eq!(path(&leaf), "mid/leaf");

    // dropping the last owner of each frees the rest, and nothing is left over
    drop(mid);
    assert_eq!(dropped.get(), 2);
    drop(leaf);
    assert_eq!(dropped.get(), 3, "every person must be freed");

    println!("all checks passed");
}

$ cargo run

all checks passed

A memo behind &self

Collatz::steps takes &self because callers share one Collatz, and a cache is state nobody asked to see. It remembers answers in a RefCell and counts computed numbers in a Cell; the RefCell is not about several owners. The checks catch a missing cache and a borrow_mut held across the recursive call. The file forbids unsafe.

Starterexercises/memo.rsCopy

#![forbid(unsafe_code)]

use std::cell::{Cell, RefCell};
use std::collections::HashMap;

/// Counts the steps the Collatz sequence takes to reach 1 (halve an even number,
/// triple an odd one and add 1), and remembers every answer it works out.
struct Collatz {
    known: RefCell<HashMap<u64, u32>>,
    computed: Cell<u32>, // how many numbers were worked out, rather than found in `known`
}

impl Collatz {
    fn new() -> Collatz {
        Collatz {
            known: RefCell::new(HashMap::new()),
            computed: Cell::new(0),
        }
    }

    /// Steps from `n` to 1. Takes `&self`: callers share one Collatz.
    fn steps(&self, n: u64) -> u32 {
        todo!(
            "look in `known` first; otherwise bump `computed`, recurse, and store the answer. Do not keep a borrow of `known` alive across the recursive call"
        )
    }
}

fn main() {
    let c = Collatz::new();
    assert_eq!(c.steps(1), 0);
    assert_eq!(c.computed.get(), 1);

    // 27 takes 111 steps and passes through 112 different numbers, 1 among them
    let c = Collatz::new();
    assert_eq!(c.steps(27), 111);
    assert_eq!(c.computed.get(), 112);

    // asking again finds everything in the memo
    assert_eq!(c.steps(27), 111);
    assert_eq!(
        c.computed.get(),
        112,
        "the second call must use the stored answers"
    );

    // 54 is 27 doubled: one new number
    assert_eq!(c.steps(54), 112);
    assert_eq!(c.computed.get(), 113);

    // a long chain works too: 525 numbers, so 525 nested calls
    assert_eq!(c.steps(837799), 524);

    println!("all checks passed");
}

Open in the Rust Playground ↗Run it first: it stops at todo!() with not yet implemented and a hint, and the compiler warns that the parameter is unused. Both are expected. Replace the todo!() with your code and run it again until it prints all checks passed.

Show a solution

One solutionexercises/memo.solution.rsRun ↗Copy

#![forbid(unsafe_code)]

use std::cell::{Cell, RefCell};
use std::collections::HashMap;

/// Counts the steps the Collatz sequence takes to reach 1 (halve an even number,
/// triple an odd one and add 1), and remembers every answer it works out.
struct Collatz {
    known: RefCell<HashMap<u64, u32>>,
    computed: Cell<u32>, // how many numbers were worked out, rather than found in `known`
}

impl Collatz {
    fn new() -> Collatz {
        Collatz {
            known: RefCell::new(HashMap::new()),
            computed: Cell::new(0),
        }
    }

    /// Steps from `n` to 1. Takes `&self`: callers share one Collatz.
    fn steps(&self, n: u64) -> u32 {
        let cached = self.known.borrow().get(&n).copied();
        if let Some(steps) = cached {
            return steps;
        }
        self.computed.set(self.computed.get() + 1);
        let steps = if n == 1 {
            0
        } else if n % 2 == 0 {
            1 + self.steps(n / 2)
        } else {
            1 + self.steps(3 * n + 1)
        };
        self.known.borrow_mut().insert(n, steps);
        steps
    }
}

fn main() {
    let c = Collatz::new();
    assert_eq!(c.steps(1), 0);
    assert_eq!(c.computed.get(), 1);

    // 27 takes 111 steps and passes through 112 different numbers, 1 among them
    let c = Collatz::new();
    assert_eq!(c.steps(27), 111);
    assert_eq!(c.computed.get(), 112);

    // asking again finds everything in the memo
    assert_eq!(c.steps(27), 111);
    assert_eq!(
        c.computed.get(),
        112,
        "the second call must use the stored answers"
    );

    // 54 is 27 doubled: one new number
    assert_eq!(c.steps(54), 112);
    assert_eq!(c.computed.get(), 113);

    // a long chain works too: 525 numbers, so 525 nested calls
    assert_eq!(c.steps(837799), 524);

    println!("all checks passed");
}

$ cargo run

all checks passed

Read more

• The Rust Book, chapter 15: Smart Pointers, with Box, Rc, RefCell and reference cycles.
• The standard library: Box, Rc, Weak, Cell, RefCell.
• Rust by Example: Box, stack and heap and Rc.
• Errors: E0072, E0277, E0594, or this site’s index.