Cell<T>: mutation by moving values in and out

Count arrivals during a graph walk, using Cell<u32> to update counters through shared references.

pub fn visit_counts(edges: Vec<(usize, usize)>, start: usize) -> Vec<u32>

Nodes are numbered from zero. The output length is one more than the largest index appearing in edges or start, even if that node is unreachable. Each pair (a, b) is a directed edge from a to b. Preserve duplicate edges and keep each node's outgoing edges in input order.

Begin by arriving at start. On every arrival:

1. Check whether this is the node's first arrival.
2. Increment its counter, including on revisits.
3. Only on the first arrival, recursively visit its outgoing neighbours in order.

Return all counters in node-index order. Unreachable nodes stay at zero. With no edges and start == 2, the result is [0, 0, 1]. A self-loop (0, 0) starting at zero gives [2]: the initial arrival expands the edge, and the second arrival increments the count without expanding again.

Assume indices leave room for adding one, counts fit in u32, and the graph fits in memory and the available recursion stack. Cycles do not cause repeated expansion because each reached node expands only once.

Keep shared access to the graph

The exercise's walk function takes &[Node]. A plain u32 field cannot be assigned through that shared reference, so the starter reports E0594 at nodes[i].visits += 1.

Change Node::visits to Cell<u32> and adapt its initialization, reads and increments. Keep the shared-slice traversal API and use the count itself to identify first arrivals; no separate visited set is needed.

This is a constraint of the exercise, not a rule that graph traversal always requires interior mutability. A different design can pass a mutable slice recursively by reborrowing it, provided conflicting borrows are not kept alive across the recursive call.

Copy a value out, then replace it

Cell supports replacing a value through &Cell<T>. For a copyable value, get() returns a copy, so no reference to the stored value remains borrowed. set() writes a replacement. This makes small counters a useful application:

use std::cell::Cell;

fn arrive(visits: &Cell<u32>) -> bool {
    let first = visits.get() == 0;
    visits.update(|count| count + 1);
    first
}

fn main() {
    let visits = Cell::new(0);
    assert!(arrive(&visits));
    assert!(!arrive(&visits));
    assert_eq!(visits.get(), 2);
}

Check first before incrementing. Checking afterward would make the initial arrival look like a revisit and prevent the traversal from following edges. update is available from Rust 1.88; set(get() + 1) also works here.

Useful operations include:

Cell<String> supports replacement but not get(), because String is not Copy. Calling get() on it reports E0599 with an explanation of the missing bound. Read that explanation rather than treating every E0599 as a misspelling.

What Cell does and does not guarantee

Shared access to a cell does not provide a safe borrowed reference to its contents. With exclusive access, however, get_mut(&mut self) does return &mut T. For example, a locally owned mutable Cell<Vec<_>> can be edited in place:

use std::cell::Cell;

fn main() {
    let mut values = Cell::new(vec![1, 2]);
    values.get_mut().push(3);
    assert_eq!(values.into_inner(), [1, 2, 3]);
}

Through a shared reference, one option for a Cell<Vec<_>> is to take the vector, edit it, then put it back. Between those calls the cell contains an empty vector. Code called during that interval can observe the temporary state, and a panic before replacement can leave it there. RefCell is useful when you instead need checked borrowing of the stored value in place.

Cell has no runtime borrow counter, but that does not mean every operation involving it is panic-free. An update closure, a Default implementation used by take, or a destructor run by set may panic. swap also rejects partially overlapping cells that unsafe code can construct.

A Cell<T> has the same size and alignment as T; this is not a promise that every operation has identical performance to direct field access. It is not a thread-safe shared counter: Cell<T> is not Sync. Ownership can be transferred between threads when T: Send, but sharing updates between threads requires a suitable synchronization type.

Finally, input order determines the traversal sequence, but not these final counts. Every edge whose source is reached contributes one arrival at its destination, plus the initial arrival at start. Keep the prescribed walk to practice the shared-reference API; counts alone cannot reveal its order.