`Rc<str>`: interning without double indirection

Intern a list of words: every distinct word gets exactly one heap allocation, and every occurrence gets a handle to it.

pub fn intern(words: Vec<String>) -> (Vec<Rc<str>>, usize)

Return one handle per input word, in input order, plus the number of distinct allocations you made.

The grader does not take your word for it. It checks, for every pair of handles, whether Rc::ptr_eq says they are the same allocation, and it reads Rc::strong_count on each one after your function has returned. Two equal words that got separate allocations will fail even though the strings match.

Rc<String> is one pointer too many

Start by counting hops. To read the first byte of an Rc<String> the machine must:

1. follow the Rc handle to the refcount block,
2. read the String header stored inside it (pointer, length, capacity),
3. follow that pointer to the actual bytes.

Two dereferences and two separate allocations, for one string. And a String is a growable buffer — capacity, spare room, the machinery for push_str — none of which you can ever use, because an Rc will not hand you &mut.

Rc<str> collapses that. The refcount block holds the bytes themselves, laid out immediately after the two counters, and the handle is a fat pointer carrying the address plus the length. One allocation, one hop, and no unusable growth machinery. For a table of interned strings — which is exactly what an interner is — this is strictly better on every axis.

The same applies to Rc<[T]> versus Rc<Vec<T>> for shared immutable lookup tables, and to Box<[T]> versus Box<Vec<T>> when you are done growing a vector and want to hand it on. Vec::into_boxed_slice exists for that.

The lint that is the curriculum

The first line of this problem’s file is:

#![warn(clippy::rc_buffer)]

rc_buffer is allow-by-default — clippy will never mention it unless you ask. This problem asks, and since the gate is -D warnings, a warn-level opt-in is enough to make it fail you. Keep the line; it is part of the exercise.

On the starter it produces:

error: usage of `Rc<T>` when `T` is a buffer type
  |     map: HashMap<String, Rc<String>>,
  |                          ^^^^^^^^^^
help: try
  |     map: HashMap<String, Rc<str>>,

Which is a good moment to notice something about lint scope: rc_buffer inspects struct fields and function signatures, not local let annotations. If you had written the same type on a local binding it would have passed silently. Lints see less than you think.

Unsized types behind a pointer

str and [T] are dynamically sized types. You cannot have a bare str local, because the compiler does not know how many bytes to reserve. But you can have one behind any pointer that carries the length alongside the address:

All of the right-hand entries are fat pointers — two words, address plus length. That is the whole mechanism, and it is why Rc<str> needs no special support: Rc<T> was always generic over T: ?Sized.

Construction is by conversion rather than by Rc::new, because Rc::new needs a sized value to move in. Rc::from("hello"), Rc::from(s.as_str()), s.into() where the target type is known, or Rc::from(vec) for Rc<[T]>. Reaching for Rc::new(s) on a String gives you Rc<String> and then E0308 when you try to store it where an Rc<str> was expected — which is exactly the error waiting in the starter.

The price: Rc<str> can never be mutated

Not by get_mut, not by make_mut, not ever. make_mut needs T: Clone and a place to write a T; str is unsized, so there is no such place. The bytes are fixed at construction.

For an interner that is not a limitation, it is the point — interned strings that could change would be a bug. But if you do need shared mutable text you are back to Rc<RefCell<String>>, with the double indirection and the runtime borrow flags, and you should ask whether you really need it.