使用 HashSet 规范化 Rust 中的对象

Question

作为一项教育练习，我正在考虑将 cvs-fast-export 移植到 Rust。

它的基本操作方式是将多个CVS主文件解析成中间形式，然后对中间形式进行分析，目的是将其转化为git快速导出流。

解析时要做的事情之一是将中间形式的公共部分转换为规范表示。一个激励性的例子是提交作者。一个 CVS 存储库可能有数十万个单独的文件提交，但可能只有不到一千个作者。因此，当您从文件中解析作者时，在解析输入作者的位置时使用实习 table ，它将为您提供指向规范版本的指针，如果以前没有看到它，则会创建一个新版本。（我也听说过这叫做雾化或实习）。然后该指针存储在中间对象上。

我第一次尝试在 Rust 中做类似的事情尝试使用 HashSet 作为实习 table。注意这里使用的是 CVS 版本号而不是作者，这只是一个 digit 的序列，例如 1.2.3.4，表示为 Vec.

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

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

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

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

失败 error[E0499]: cannot borrow 'set' as mutable more than once at a time。这很公平，如果您在获得引用后添加更多项目，HashSet 不保证对其键的引用有效。 C 版本小心地保证了这一点。要得到这个保证，我觉得HashSet应该超过Box<T>。但是我无法向借阅检查器解释此的生命周期。

我在这里采用的所有权模型是实习 table 拥有数据的规范版本，并分发参考资料。只要实习 table 存在，引用就应该有效。我们应该能够在不使旧引用失效的情况下向实习 table 添加新内容。我认为我的问题的根源在于我对如何以符合 Rust 所有权模型的方式编写该合约的接口感到困惑。

我以有限的 Rust 知识看到的解决方案是：

做两遍，在第一遍构建一个 HashSet，然后冻结它并在第二遍使用引用。这意味着额外的临时存储（有时是大量的）。
不安全

有没有人有更好的主意？

Answer 1

您的分析是正确的。最终的问题是，当修改 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项目的集体脑力。
typed-arena
generational-arena

Answer 2

我有点不同意@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 规范化 Rust 中的对象

Using a HashSet to canonicalize objects in Rust

rust

hashset

canonicalization