Dup-Indexer

创建一个没有额外内存分配的非重复值向量，即使对于像 String 和 Vec 这样的 ref 值也是如此。每次插入都返回插入值的 usize 索引。完成时，可以使用整个向量。

这种方法对于创建唯一值的向量很有用，例如唯一字符串列表或唯一对象列表，然后使用向量中的值的索引作为唯一标识符，例如在 protobuf 消息中。

此 crate 中有两个对象

• DupIndexer<T> - 使用 insert(value: T) 添加值，其中 value 在每次调用时所有权被移动到索引器中。这对于插入后不再需要值的情况很有用，或者对于实现 Copy 的值。
• DupIndexerRefs<T: Deref> - 使用 insert_owned(value: T) 和/或 insert_ref(value: &T::Target)，要么通过所有权转移插入（就像 DupIndexer 一样），要么通过引用插入，并且只有当值不在索引中时才复制该值。这仅适用于 String/&str 对，或者可以为其自定义类型实现。

示例

use dup_indexer::{DupIndexer, DupIndexerRefs};

fn main() {
  let mut di = DupIndexerRefs::new();
  assert_eq!(di.insert_owned("hello".to_string()), 0);
  assert_eq!(di.insert_ref("world"), 1);
  assert_eq!(di.insert_ref("hello"), 0);
  assert_eq!(di.into_vec(), vec!["hello", "world"]);
  
  // with strings
  let mut di = DupIndexer::new();
  assert_eq!(di.insert("hello".to_string()), 0);
  assert_eq!(di.insert("world".to_string()), 1);
  assert_eq!(di.insert("hello".to_string()), 0);
  assert_eq!(di.into_vec(), vec!["hello", "world"]);

  // with i32
  let mut di = DupIndexer::with_capacity(10);
  assert_eq!(di.insert(42), 0);
  assert_eq!(di.insert(13), 1);
  assert_eq!(di.insert(42), 0);
  assert_eq!(di[1], 13); // use it as a read-only vector
  assert_eq!(di.into_iter().collect::<Vec<_>>(), vec![42, 13]);

  //
  // with custom enum
  //
  #[derive(Debug, Eq, PartialEq, Hash, Clone)]
  enum Value {
    Str(String),
    Int(i32),
  }

  // All values inside the Value enum implement PtrRead
  unsafe impl dup_indexer::PtrRead for Value {}

  let mut di: DupIndexer<Value> = DupIndexer::new();
  assert_eq!(di.insert(Value::Str("foo".to_string())), 0);
  assert_eq!(di.insert(Value::Int(42)), 1);
  assert_eq!(di.insert(Value::Str("foo".to_string())), 0);
  assert_eq!(di[1], Value::Int(42));
  assert_eq!(
    di.into_vec(),
    vec![Value::Str("foo".to_string()), Value::Int(42)]
  );
}

实现

DupIndexer 按插入顺序在向量中保持插入的值。它还在查找映射 HashMap<T, usize> 中跟踪插入的值，其中 T 是插入值的类型。这意味着插入的值必须实现 Hash 和 Eq。

像整型、浮点型、布尔型、字符型这样的值类型以及任何像 &str 这样的引用都不会引起问题，因为它们可以复制到向量和查找映射容器中。然而，像 String 和 Vec 这样的不可复制的具有内存分配的类型不能同时被两个容器拥有。为了解决这个问题，DupIndexer 创建了值的浅拷贝，并将其存储在哈希映射中，而原始值则放入向量中。

use std::collections::hash_map::{Entry, HashMap};
use std::mem::ManuallyDrop;
use std::hash::Hash;

pub unsafe trait PtrRead {}

pub struct DupIndexer<T> {
  values: Vec<T>,
  lookup: HashMap<ManuallyDrop<T>, usize>,
}

impl<T: Hash + Eq + PtrRead> DupIndexer<T> {
  pub fn insert(&mut self, value: T) -> usize {
    let dup_value = ManuallyDrop::new(unsafe { std::ptr::read(&value) });
    match self.lookup.entry(dup_value) {
      Entry::Occupied(entry) => *entry.get(),
      Entry::Vacant(entry) => {
        let index = self.values.len();
        entry.insert(index);
        self.values.push(value);
        index
      }
    }
  }
}

这样，哈希映射拥有浅拷贝，向量拥有原始值。在后续调用中，新值将检查哈希映射是否存在重复项。完成后，用户使用 .into_vec() 消耗具有键的向量，而哈希映射则在丢弃实际键之前被丢弃。

安全性

DupIndexerRefs 假定它是安全的，因为只要 String 本身没有修改，即使 String 对象存储在可能调整大小的 Vec<String> 中，对 String 的解引用（&str）就是有效的。

类似地，DupIndexer 是安全的，因为哈希映射只保留在拥有它时由 ptr:read 创建的原始值的副本，而且值永远不会被修改。一些类型，如 Box 可能会复杂一些，因此为了安全性/让 Miri 满意，这个库有一个不安全的 PtrRead 标记特质，大多数基本类型都实现了它。

Miri 通过了所有测试，但如果 T 是 Box<i32>，则会失败。当测试尝试插入重复值时，我会看到以下 Miri 警告。如果您知道这是否真的是一个问题以及如何修复它，请告诉我。

❯ cargo +nightly miri test

    --> .../.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:1328:23
     |
1328 |         PartialEq::eq(&**self, &**other)
     |                       ^^^^^^^
     |                       |
     |                       trying to retag from <170684> for SharedReadOnly permission at alloc64636[0x0], but that tag does not exist in the borrow stack for this location
     |                       this error occurs as part of retag at alloc64636[0x0..0x4]
     |
     = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
     = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <170684> was created by a Unique retag at offsets [0x0..0x4]
    --> src/lib.rs:49:17
     |
49   |                 entry.insert(index);
     |                 ^^^^^^^^^^^^^^^^^^^
help: <170684> was later invalidated at offsets [0x0..0x4] by a Unique retag
    --> src/lib.rs:50:34
     |
50   |                 self.values.push(value);
     |                                  ^^^^^

开发

• 这个项目更容易与 just 开发，它是对 make 的现代替代品。使用 cargo install just 安装它。
• 要获取可用命令的列表，请运行 just。
• 要运行测试，请使用 just test。
• 在执行 git push 时，它将执行一些验证，包括 cargo fmt、cargo clippy 和 cargo test。使用 git push --no-verify 来跳过这些检查。
• 要运行基准测试，使用 just bench。
• 要使用 Miri 进行测试，使用 just miri（注意，由于上述问题，其中一个测试被禁用）。

许可证

以下任一许可证下授权：

• Apache License, Version 2.0（《LICENSE-APACHE》或https://apache.ac.cn/licenses/LICENSE-2.0）
• MIT 许可证（《LICENSE-MIT》或http://opensource.org/licenses/MIT）根据您的选择。

贡献

除非您明确表示，否则根据 Apache-2.0 许可证定义的，您有意提交的工作中的任何贡献都应如上双重许可，不附加任何额外条款或条件。