`Rc<T>`: shared ownership by reference counting

Run a tiny acquire/release protocol over shared definitions and report both the answers and the sharing.

pub fn share_report(defs: Vec<Vec<i64>>, refs: Vec<usize>) -> (Vec<i64>, Vec<usize>)

Wrap each definition in an Rc<Vec<i64>>. Then walk refs in order and apply the first rule that matches:

Return (the pushed values, the final strong count of every definition) — measured with every handle you are still holding alive.

usize::MAX is 18446744073709551615 and arrives from the test data verbatim; the JSON layer does not round it through a float.

Why Rc exists

Everything you have written so far had exactly one owner. That works astonishingly often, and where it works you should keep doing it. But some shapes genuinely have no single owner:

• a node with two parents in a DAG,
• a string interned once and referred to from a thousand places,
• a configuration table read by several independent subsystems,
• a cache entry that must outlive whichever request happened to create it.

You could give one of them ownership and hand the rest & references — but then you need a lifetime that outlives all of them, and you are back to designing a scope around a data structure. Rc<T> — reference counted — says instead: there are several owners, and the value dies when the last one does.

The mechanism, exactly

Rc::new(v) heap-allocates a small block containing two counters and v itself. The Rc handle you hold is one pointer to that block.

Rc::clone(&a) copies the pointer and increments the strong counter. It does not touch v. That is why cloning an Rc<Vec<i64>> of a million elements is a couple of instructions while cloning the Vec itself is a million-element copy.

Dropping an Rc decrements the counter. When it reaches zero, v is dropped and the block is freed. Rc::strong_count(&a) reads the counter, which is what makes the sharing observable — and therefore testable.

Two conventions worth adopting now. Write Rc::clone(&a) rather than a.clone(), even though they are identical: the associated-function form makes it visible at the call site that you are copying a pointer, not the data. Clippy has a lint for it, clone_on_ref_ptr — and it is allow-by-default, so the gate here will not enforce it and plenty of production code writes .clone(). Learn the reasoning, not the rule.

And note that the counter increment is a plain, non-atomic += 1. That is exactly why Rc is neither Send nor Sync, and why the cross-thread version is called Arc and costs more. Try to move an Rc into a thread and the compiler stops you; that is the single best demonstration in the language of a data race caught at compile time.

The dead end you should walk into on purpose

The starter contains a first draft that does not compile:

let owned: Vec<i64> = *defs[r];

error[E0507]: cannot move out of an `Rc`
  |
  |     let owned: Vec<i64> = *defs[r];
  |                           ^^^^^^^^ move occurs because value has type
  |                           `Vec<i64>`, which does not implement `Copy`

Of course it cannot. If it could, the other handles would be pointing at a hole. Note the contrast with the previous items: *boxed does move the value out, because a Box has exactly one owner and the compiler special-cases it. Rc has many, so * on an Rc can only ever borrow. You do not need the value out of the Rc at all here — defs[r].iter() derefs straight through.

Now spend one minute on the other dead end, because it sets up the second half of this track. Add a line that tries to change a shared definition:

defs[r].push(0);

error[E0596]: cannot borrow data in an `Rc` as mutable
  = help: trait `DerefMut` is required to modify through a dereference,
          but it is not implemented for `Rc<Vec<i64>>`

Read that carefully: Rc hands out &T and only &T. It cannot hand out &mut T, because it has no idea how many other handles exist. So an Rc on its own gives you sharing without mutation — and a very large fraction of the rest of this track is about what to do when you need both. Do not go looking for the answer yet. Delete the line and finish the problem.

Three lints that live here

• rc_clone_in_vec_init (default-on). vec![Rc::new(x); 3] does not make three values. vec![v; n] clones v, and cloning an Rc clones the handle — so you get one allocation with three handles pointing at it, and every “independent” slot aliases. Build the vector with a loop or (0..3).map(|_| Rc::new(x.clone())).collect().
• redundant_allocation (default-on). Rc<Box<T>> is two hops to reach one value, and the Box buys nothing an Rc did not already provide.
• rc_buffer (allow-by-default). Rc<String> and Rc<Vec<T>> are also double indirection — you will meet the fix, Rc<str> and Rc<[T]>, later in this track. This problem uses Rc<Vec<i64>> deliberately, because the definitions are what you were handed.

  Loading visualization…