14 个版本
| 0.5.6 | 2024 年 7 月 23 日 |
|---|---|
| 0.5.4 | 2024 年 4 月 5 日 |
| 0.5.3 | 2024 年 3 月 2 日 |
| 0.5.0 | 2023 年 10 月 11 日 |
| 0.3.0 | 2023 年 7 月 4 日 |
#629 in 算法
265 每月下载量
用于 3 个 crate（通过 hydroflow）
225KB
5.5K SLoC
lattices Crate
lattices crate 提供了便捷且可组合的晶格类型。您也可以通过几个简单的特质来实现自定义晶格。
晶格是一个非常强大的数学概念，它可以极大地简化分布式计算的复杂性。它们与分布式系统中实际发生的事情非常吻合：消息可以无序或重复到达。但是，如果数据被表示为晶格，则所有机器只需通过合并数据就可以始终达到相同的结果。晶格目前在分布式系统中的一种流行用法是作为无冲突复制的数据类型（CRDT）的数据基础。
晶格还允许我们利用CALM定理的力量：“一个程序如果且仅如果是单调的，它才有统一的、无需协调的分布式实现。”晶格状态总是单调的，这意味着在晶格状态下构建的分布式系统的任何部分都可以自由分布，无需协调开销。Hydro项目的目标是允许用户编写可以自动扩展和轻松分布的程序。
有关晶格和单调性的底层数学的更多信息，请参阅Hydroflow 书籍中的晶格数学部分和Hydroflow 论文（2021年）的第二章。
请参阅lattice rustdocs。
晶格
lattices 提供了常见晶格类型的实现
Min<T>和Max<T>- 完全有序格。set_union::SetUnion<T>- 标量值的集合格。- [
map_union::MapUnion<K, Lat>] - 嵌套格值的标量键。 union_find::UnionFind<K>- 标量值的集合的并部分。VecUnion<Lat>- 增长的Vec，类似于MapUnion<<usize, Lat>>，但没有缺失条目。WithBot<Lat>- 将格用Option包装，其中None是新的下界值。WithTop<Lat>- 将格用Option包装，其中None是新的 上界 值。- [
Pair<LatA, LatB>] - 两个嵌套格的乘积。 - [
DomPair<LatKey, LatVal>]* - 一个版本对，其中LatKey占据LatVal的优势。 Conflict<T>* - 向域T添加一个“冲突”上界。合并不等T的结果为上界。- [
Point<T, *>]* - 一个不能与任何不等值合并的单个“点格”值。 ()- “单位”格，一个只有单位()作为域中唯一值的“点格”。
特殊实现，不一定遵守所有格属性，但在某些情况下仍然有用。
此外，可以通过实现以下特性来创建自定义格。
特性
通过实现以 Merge 开头的特性之一，类型成为格。这些特性已经为所有提供的格类型实现。
Merge
主要特性是Merge，它定义了一个格合并函数（又称“连接”或“最小上界”）。实现者必须定义Merge::merge方法，该方法将合并操作原地执行到&mut self。如果self被修改（即值在格偏序中变大），则该方法必须返回true，否则（即other小于self）返回false。还提供了Merge::merge_owned函数，用于合并两个所有者值。
merge方法必须是结合的、交换的和幂等的。编译器不会检查这些属性，但实现者可以使用test::check_lattice_properties方法来检查这些属性。
PartialOrd、LatticeOrd和NaiveLatticeOrd
Rust已经有一个针对偏序的特型PartialOrd，该特型应该在格类型上实现。但是，该特型不是针对格偏序的，因此我们提供了LatticeOrd<Rhs>: PartialOrd<Rhs>标记特型，以表示当PartialOrd实现是格偏序时。`LatticeOrd`必须始终与`Merge`函数一致。
此外，对于实现了`Merge`和`Clone`的所有格类型，提供了密封的NaiveLatticeOrd特型。此特型提供了一种naive_cmp方法，该方法直接从`Merge`函数推导出格顺序。然而，实现通常较慢且效率低下。
实现者应使用test::check_partial_ord_properties方法检查其`PartialOrd`实现，并使用test::check_lattice_ord确保偏序与从`Merge`推导出的`NaiveLatticeOrd`顺序一致。
格From
LatticeFrom与std::convert::From特质等价，但特定于格。应仅在相同格类型的不同表示之间实现LatticeFrom，例如在set_union::SetUnionBTreeSet和set_union::SetUnionHashSet之间。对于复合格（嵌套格类型的格），对于这些嵌套格，应递归地实现LatticeFrom。
IsBot、IsTop和Default
下界（⊥）严格小于所有其他值。上界（⊤）严格大于所有其他值。IsBot::is_bot和IsTop::is_top分别确定一个格实例是否为上界或下界。
对于格类型，Default::default()必须创建一个下界值。IsBot::is_bot(&Default::default())对于所有格类型应始终返回true。
原子化
Atomize::atomize将格点转换为多个较小的格点。当将这些“原子”合并在一起时，它们将形成原始格点。有关更精确的语义，请参阅文档。
深度揭示
DeepReveal允许对格中底层数据的递归“揭示”。特别适用于揭示嵌套格。
依赖关系
~3–11MB
~123K SLoC