Использование HashSet для канонизации объектов в Rust

Я несколько не согласен с @Shepmaster по поводу использования здесь unsafe.

Хотя сейчас это не вызывает проблем, если кто-то в будущем решит изменить использование HashSet, включив в него некоторую обрезку (например, оставить там только сотню авторов), тогда unsafe будет сильно укусить тебя.

В отсутствие серьезной причины производительности я бы просто использовал Rc<XXX>. Вы можете легко использовать псевдоним: type InternedXXX = Rc<XXX>;.

use std::collections::HashSet;
use std::hash::Hash;
use std::rc::Rc;

#[derive(PartialEq, Eq, Debug, Hash, Clone)]
struct CvsNumber(Rc<Vec<u16>>);

fn intern<T:Eq + Hash + Clone>(set: &mut HashSet<T>, item: T) -> T {
    if !set.contains(&item) {
        let dupe = item.clone();
        set.insert(dupe);
        item
    } else {
        set.get(&item).unwrap().clone()
    }
}

fn main() {
    let mut set: HashSet<CvsNumber> = HashSet::new();
    let c1 = CvsNumber(Rc::new(vec![1, 2]));
    let c2 = intern(&mut set, c1);
    let c3 = CvsNumber(Rc::new(vec![1, 2]));
    let c4 = intern(&mut set, c3);
}

Ваш анализ правильный. Конечная проблема заключается в том, что при изменении HashSet компилятор не может гарантировать, что мутации не повлияют на существующие распределения. На самом деле, в целом они могут повлиять на них, если только вы не добавите еще один уровень косвенности, как вы определили.

Это яркий пример места, где unsafe полезно. Вы, программист, можете утверждать, что код будет использоваться только определенным образом, и этот конкретный способ позволит переменной оставаться стабильной при любых мутациях. Вы можете использовать систему типов и видимость модуля, чтобы обеспечить соблюдение этих условий.

Обратите внимание, что String уже вводит выделение кучи. Пока вы не измените String после того, как он будет выделен, вам не нужен дополнительный Box.

Что-то вроде этого выглядит как нормальное начало:

use std::{cell::RefCell, collections::HashSet, mem};

struct EasyInterner(RefCell<HashSet<String>>);

impl EasyInterner {
    fn new() -> Self {
        EasyInterner(RefCell::new(HashSet::new()))
    }

    fn intern<'a>(&'a self, s: &str) -> &'a str {
        let mut set = self.0.borrow_mut();

        if !set.contains(s) {
            set.insert(s.into());
        }

        let interned = set.get(s).expect("Impossible missing string");

        // TODO: Document the pre- and post-conditions that the code must
        // uphold to make this unsafe code valid instead of copying this
        // from Stack Overflow without reading it
        unsafe { mem::transmute(interned.as_str()) }
    }
}

fn main() {
    let i = EasyInterner::new();

    let a = i.intern("hello");
    let b = i.intern("world");
    let c = i.intern("hello");

    // Still strings
    assert_eq!(a, "hello");
    assert_eq!(a, c);
    assert_eq!(b, "world");

    // But with the same address
    assert_eq!(a.as_ptr(), c.as_ptr());
    assert!(a.as_ptr() != b.as_ptr());

    // This shouldn't compile; a cannot outlive the interner
    // let x = {
    //     let i = EasyInterner::new();
    //     let a = i.intern("hello");
    //     a
    // };

    let the_pointer;
    let i = {
        let i = EasyInterner::new();
        {
            // Introduce a scope to contstrain the borrow of `i` for `s`
            let s = i.intern("inner");
            the_pointer = s.as_ptr();
        }
        i // moving i to a new location
          // All outstanding borrows are invalidated
    };

    // but the data is still allocated
    let s = i.intern("inner");
    assert_eq!(the_pointer, s.as_ptr());
}

Однако, может быть гораздо целесообразнее использовать обрешетку типа:

• string_cache, за которым стоят коллективные умственные способности проекта Servo.
• типизированная-арена
• generational-arena