Justly

这是一个受 Haskell 中 justified-containers 库启发的“justified 容器”库。

简要来说，这个库可能会在你使用索引而不是引用的地方帮助你。

请查看 rustdoc 文档中的 src/lib.rs，以了解 Justly 的主要描述和使用信息。

还可以查看 meta/ 目录，以了解更多有关此仓库结构的信息。

lib.rs:

不需要额外边界检查的集合。

概述

Justly 为 Rust 标准数据结构实现“justified”包装器。一个 justified 容器 是一个其键（如 usize 索引到一个 [Vec]）跟踪其有效性的容器。这有几个主要后果，如下所述。

可信性

Justly 建立在 可信知识 的理念之上：call::Call 代表一个通过名称调用的值，它允许你编码有关该命名实体的 知识，例如 key::Key，一个你知道是有效的索引。如果你维护这些 API 中描述的安全性属性，那么这种知识被称为 可信的，因此你可以依赖它来构建安全的抽象。现在未检查的索引可以真正地安全了！

无需额外检查

“已检查”方法是指执行边界检查的方法，“未检查”方法是指 不安全地 省略了它。在 Justly 中 安全地 省略边界检查的方法被称为 无检查。Rust 编译器尝试在能够证明它们将始终成功的情况下省略检查。Justly 通过提供工具来证明可以省略检查来实现无检查的 API。

需要注意的是，有些检查是绝对必要的！例如，你必须进行运行时测试来确认任意整数索引是否为有效键。Justly 只允许你避免一些额外的检查，这些检查并非绝对必要，但编译器无法证明这一点。但是，一旦你得到了一个类型化的键，它就证明了测试已经完成，无需重复。

此外，从集合 API 获取的大多数索引已经知道是有效键，所以 Justly 只是在其包装 API 中添加了这些信息。

无无效索引

在引用集合中的元素时，Rust 鼓励使用相对于集合的索引，而不是绝对指针。当一个容器是可变的，如果其容量超出，则修改方法可以重新分配容器的存储，从而使对该存储的所有指针无效。因此，相对索引与绝对寻址相比，更容易保持内存安全，因为索引会自动响应容量变化。

然而，相对索引仍然不会自动处理大小变化：任何减小容器大小的操作都必须自然地使引用新边界之外元素的索引无效。

更糟糕的是，由于索引只是裸整数，它们没有任何关于索引与该索引值之间关系的保证。例如，假设我们有一个向量 v，并且我们计算了其中的一些索引 i 和 j。

let mut v = vec![1, 7, 16, 27, 40, 55];

let i = v.iter().enumerate().position(|(k, &v)| k * 10 == v).unwrap();
let j = v.iter().enumerate().position(|(k, &v)| k * 11 == v).unwrap();

println!("{}", v[i]);  // valid (40)
println!("{}", v[j]);  // valid (55)

如果我们从向量中移除一个元素，那么这很容易破坏对索引做出假设的代码：remove 不仅使 j 不可访问，而且还静默地改变了 i 的含义。这就像一个使用后释放的错误。

v.remove(2);

println!("{}", v[i]);  // logic error (55)
println!("{}", v[j]);  // runtime error (panic)

当然，如果我们向向量中添加一个元素，问题会更加严重：它静默地使 j 可访问，但含义也发生了变化。

v.push(68);

println!("{}", v[j]);  // logic error (68)

因此，Justly 将可能使集合键无效的修改方法包装在返回修改后对象的消耗方法中，并附带有关新键与旧键之间关系的信息。

我们使用幻影类型参数来做这件事，因此没有运行时成本。

关于本文档

包装类型和方法使用带有描述其目的的标签进行注释，这些标签用花括号 {…} 标记，以便更容易搜索。

{free}

标记那些曾经需要在原始类型上执行边界检查的方法，但现在无需检查。

{just}

在容器类型上，这意味着该类型是普通容器的包装器，其中某些方法使用类型状态来增加安全性。

在方法上，它标记了我们改变签名的地方，通常是以下两种情况之一：

• 将 self 保留以替换包装类型上的一个 mut 方法，该方法跟踪有关容器的知识

• 添加包装器，如 key::Key 以记录一些有关结果的知识

{like}

链接到原始包装物。

{safe}

标记曾经是不安全（通常为未检查）但现在已安全（意味着检查自由）的项。

待办事项

允许命名无大小的事物

call::Call和link::Link要求T: Sized，但实际上它们并不需要，因为所有其他字段都旨在作为幻影。

分配器支持

为了支持分配器，包装器上应该有一个类型参数，例如A = std::alloc::Global。

隐式解引用

我们对于是否添加允许通过名称隐式调用的Deref和DerefMut的实现感到不安，就像这些为Vec的实现一样。

impl<'name, T> Deref for Vec<'name, T> {
    type Target = Call<'name, vec::Vec<T>>;
    fn deref(&self) -> &Call<'name, vec::Vec<T>> {
        &self.same
    }
}

impl<'name, T> DerefMut for Vec<'name, T> {
    fn deref_mut(
        &mut self,
    ) -> &mut Call<'name, vec::Vec<T>> {
        &mut self.same
    }
}

跟踪容量

在撰写本文时，这些API仅跟踪索引的有效性。这意味着如果std::collections有一个不会更改任何索引的突变方法，我们只需将其转发并保持相同的API，这对可用性可能更好。

然而，原则上我们同样可以跟踪容量。这将反映类型级别上std::collections关于分配的保证，在某些情况下，可以静态地保证代码不会分配。但这将以使用不同的API来处理可能会更改容量的函数的代价。

静态、类型级别的运行时值名称。

名称使用生存期变量表示。关于为什么这样做，请参阅[mod@crate::call]。唯一名称的辅助工具。name ≡ value关系：为动态值定义一个唯一的静态名称。

要创建一个新的名称，我们必须创建一个新的类型级常量，这个常量既是静态的又是唯一的。

通常，“类型常量”想要成为一个存在类型。然而，dyn Trait类型不是静态已知的，而impl Trait类型也不一定是唯一的。幸运的是，我们可以使用等级2全称量化来编写等级1存在量化，这对于生存期变量是允许的。

因此，我们可以将名称写成生存期。这也让我们有时可以跳过编写它，多亏了生存期省略。

为值命名。 name × value关系：将静态名称与动态值配对。集合的常见属性。 {just} {like}:[mod@std::vec] {like}:[mod@std::slice]

Vec<'name, T> 是对命名向量的一种薄包装，Call<'name, std::vec::Vec<T>>，您可以使用 crate::called::Called 特性来创建。

与这个库的典型做法一样，Vec 包装器用跟踪容器状态的版本替换了一些方法，以证明未检查的索引是安全的，并提供了由这些方法支持的一些附加功能。

类型 Slice 和 MutSlice 是类似的对切片的薄包装，同样 ConstPtr 和 MutPtr 是对指针的薄包装。 {like}:std::collections::vec_deque {like}:std::collections::linked_list {like}:std::collections::hash_map {like}:std::collections::btree_map {like}:std::collections::binary_heap 集合中已知的有效键索引。静态证明。