Rc<str>: sharing interned strings

Intern strings so repeated text shares one Rc allocation.

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

Return one Rc<str> handle per input string, preserving its text and position, plus the number of distinct strings. Equal strings must share an allocation; unequal strings must not. Equality is exact: preserve case, whitespace, empty strings and Unicode spelling without normalization.

The count refers to distinct interned Rc allocations, not every allocation made by the function. The input Strings, lookup table and output vector also use storage.

What the grader observes

For ["a", "b", "a"], return handles with texts ["a", "b", "a"] and distinct count 2. The first and third handles refer to the same allocation; the second refers to a different one.

After intern returns, the harness records each handle's text, the first output position sharing its allocation, and its strong count. For this example the representative positions are [0, 1, 0], and the counts are [2, 1, 2].

Release the lookup table's handles before returning. Each output handle's strong count should equal that string's number of occurrences. Empty input returns an empty vector and zero distinct strings.

Build the intern table

Use the supplied Interner with a HashMap<String, Rc<str>>. For each word, look it up before allocating a new Rc string. On a hit, clone the stored Rc handle into the output. On a miss, create an Rc<str>, retain a handle in the table and put another in the output.

Rc::clone shares the same bytes; it does not copy the text. The table goes out of scope when the function returns, leaving the output handles alive. The table's String keys are separate storage from the interned text.

Choose the stored string representation

Rc<String> stores a String value in an Rc allocation. A nonempty String normally owns a separate growable byte buffer. Rc<str> instead stores the string bytes directly in the reference-counted allocation and does not retain a String capacity field.

Rc<str> suits this task's fixed-length shared text. This does not make it better for every use: conversion may copy bytes, and the representation does not provide String's growth operations. Rc<String> can provide mutable access under unique ownership, so its capacity is not inherently unusable.

str is dynamically sized. An Rc<str> carries the information needed to locate its text and determine its byte length. Construct it by conversion: let h: Rc<str> = Rc::from(w.as_str());. Rc::new(w) would create Rc<String>, which does not match the output type.

Rc<[T]> similarly shares a fixed-length sequence, while Rc<Vec<T>> retains a Vec header and its separately managed element buffer. Choose based on the operations and ownership you need, rather than a fixed speed ranking.

Fixed length does not mean unchangeable bytes

Rc<str> can provide mutable str access when the ownership conditions allow it. get_mut requires unique ownership without other strong or Weak handles; make_mut can provide copy-on-write access. For example:

use std::rc::Rc;

fn main() {
    let mut text: Rc<str> = Rc::from("hello");
    let original = Rc::clone(&text);
    Rc::make_mut(&mut text).make_ascii_uppercase();
    assert_eq!(&*text, "HELLO");
    assert_eq!(&*original, "hello");
    assert!(!Rc::ptr_eq(&text, &original));
}

A mutable str still has a fixed byte length and must remain valid UTF-8. It cannot grow using String::push_str. This interner does not mutate text: preserving the mapping between each key and its interned value is part of its contract.

Repair both starter problems

The starter stores Rc<String> and tries to place those handles in a Vec<Rc<str>>, causing E0308. It also allocates again for every occurrence, which would break the sharing requirement even after fixing the types.

Keep #![warn(clippy::rc_buffer)]. This opts into an otherwise disabled lint that flags the starter's buffer representation. With warnings denied, it is part of the grading gate. Type errors can prevent Clippy from reaching that lint, so fix the output mismatch as well as the map's stored type.

The submission must compile, preserve the texts, match allocation identity and counts, and pass Clippy with warnings denied.