generics - 如何使用通用方法参数创建可散列特征对象/特征对象？

Question

我有一些结构同时实现了 Hash和 MyTrait .我将它们用作 &MyTrait特征对象。

现在我要 &MyTrait也实现 Hash .我尝试了几件事:

天真，trait MyTrait: Hash {} :

the trait `MyTrait` cannot be made into an object

然后我尝试了这个:

impl Hash for MyTrait {
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        // ...
    }
}

但我需要委托(delegate)给 hash self具体类型的方法， 我认为。

所以天真的下一步是把它放在 MyTrait 上:

fn my_hash<H: Hasher>(&self, hasher: &mut H);

这让我回到第一点。

我读了一些关于使用特征对象而不是泛型参数的内容，这听起来很聪明，所以我把它放在 MyTrait 上。

fn my_hash(&self, hasher: &mut H);

然后我需要实际实现这一点。最好不要为每个特征手工:

impl<T: 'static + Hash> MyTrait for T {
    fn as_any(&self) -> &Any {
        self as &Any
    }

    fn my_hash(&self, hasher: &mut Hasher) {
        self.as_any().downcast_ref::<T>().unwrap().hash(hasher)
    }
}

但随后

the trait bound `std::hash::Hasher: std::marker::Sized` is not satisfied
`std::hash::Hasher` does not have a constant size known at compile-time

所以我不得不沮丧 Hasher …

如果向下转型 Hasher就是这样，我需要一个通用参数H可以转换为 Any Hasher ， 咱们试试吧:

trait AnyHasher {
    fn as_any(&self) -> &Any;
}

impl<H: 'static + Hasher> AnyHasher for H {
    fn as_any(&self) -> &Any {
        self as &Any
    }
}

然后垂头丧气

impl<T: 'static + Hash, H: 'static + Hasher> MyTrait for T {
    // ...
    fn my_hash(&self, hasher: &mut AnyHasher) {
        let h = hasher.as_any().downcast_ref::<H>().unwrap();
        self.as_any().downcast_ref::<T>().unwrap().hash(h)
    }
}

可惜

the type parameter `H` is not constrained by the impl trait, self type, or predicates

我想这是真的，但后来我被卡住了。 (到目前为止，这似乎有点荒谬)。

这能做到吗？如果是这样，如何？

我之前问过 PartialEq for trait objects ，这很困难，因为需要 trait 对象的具体类型信息。这是通过向下转换解决的，但我没有设法在这里应用该解决方案。

Answer 1

我不是 Rust 专家，但在我看来，您试图将 Rust 变成 Java(不要生气:我真的很喜欢 Java)。

How can I create hashable trait objects?

您不想创建 trait 对象的哈希表(这很容易)，您想要创建一个不是 trait 对象的 trait 的哈希表，这就是您遇到困难的原因。

问题

我总结一下:您有一些实现特征的各种结构 MyTrait , Hash和 Eq ，并且您想将这些混合结构放入单个哈希表中作为 TunedMyTrait特征对象。这需要 TunedMyTrait成为 Hash的子特征和 Eq .但是 MyTrait可以成为特征对象， TunedMyTrait不能。

我相信你知道为什么，但我会尽量让其他读者明白，使用 this valuable resource . (用我自己的话来说，不要害羞，如果您认为不清楚，请编辑它。)特征对象依赖于称为“对象安全”的东西(请参阅 the RFC 255 )。 “对象安全”意味着:特性的所有方法都必须是对象安全的。

Rust 对堆栈进行了大量使用，因此它必须知道它所能知道的一切的大小。在借用检查器之后，这是 Rust 的困难和优点之一。 trait 对象有类型和大小:它是某种“胖”指针，包含有关具体类型的信息。每个方法调用都委托(delegate)给具体类型，使用 vtable的方法。我没有详细介绍，但是这个委托(delegate)可能会出现一些问题，并且创建了“安全检查”来避免这些问题。这里:

方法fn eq(&self, other: &Rhs) -> bool哪里Rhs = Self不是对象安全的，因为在运行时，Rhs被抹去，因此具体类型和大小为other不知道。

方法fn hash<H: Hasher>(&self, hasher: &mut H)不是对象安全的，因为 vtable并非为每种混凝土类型而构建 H .

解决方案

好的。 MyTrait是一个特征对象，但 TunedMyTrait不是。然而只有 TunedMyTrait对象可能是哈希表的有效键。你能做什么？

您可以像以前一样尝试破解对象安全机制。您找到了破解方法 PartialEq (通过类型转换尝试， How to test for equality between trait objects? )，你现在有另一个来自@Boiethios 的黑客(它基本上使散列成为一个非通用函数)。如果你最终实现了目标，我可以想象代码的 future 读者:“天哪，这家伙想做什么？”或(更糟):“我不确定它的作用，但我很确定如果……它会运行得更快”。你已经破坏了语言的保护，你的代码很可能会产生比你试图解决的问题更糟糕的问题。这让我想起了这样的讨论: Get generic type of class at runtime .进而？你会用这段代码做什么？

或者你可以讲道理。有一些可能性:您使用带有真正相同具体类型的键的哈希表，您将 MyTrait 装箱。对象，您使用枚举...可能还有其他方法(如上所述，我不是 Rust 专家)。

不要误会我的意思:破解一门语言真的很有趣，有助于深入理解它的机制和限制(注意:如果你没有问这个问题，我就不会仔细研究 DST 和 trait 对象，因此我谢谢你)。但是如果你打算做一些严肃的事情，你必须是认真的:Rust 不是 Java...

编辑

I want to compare and hash objects that are runtime-polymorphic.

这并不难，但你也想把它们放在 HashMap 中，这就是问题所在。

我会给你另一个见解。基本上，您知道哈希表是一个桶数组。 Rust 使用开放寻址来解决哈希冲突(特别是:罗宾汉哈希)，这意味着每个桶将包含 0 或 1 对 (key, value) .当您 put a pair (key, value) in an empty bucket ，元组 (key, value)写入缓冲区数组，位置 pair_start + index * sizeof::<K, V>() ，根据 the definition of offset .很明显，你需要大小对。

如果您可以使用 trait 对象，您将拥有一个大小合适的胖指针。但由于已经说明的原因，这是不可能的。我提出的所有想法都集中在这一点上:有大小的键(假设值已经大小了)。混凝土类型:明显尺寸。装箱:指针的大小。枚举:最大元素的大小+标签的大小+填充。

拳击的基本例子

警告:我努力在互联网上找到一个例子，但没有找到任何东西。所以我决定从头开始创建一个基本的拳击示例，但我不确定这是正确的方法。如果需要，请评论或编辑。

首先，向您的 trait 添加一个方法，该方法标识实现 MyTrait 的任何具体类型的每个实例。与 可比 和 可散列值，比方说 id返回 i64 的方法:

trait MyTrait {
    fn id(&self) -> i64; // any comparable and hashable type works instead of i64
}

Foo和 Bar具体类型将实现此方法(此处给出的实现完全是愚蠢的):

struct Foo(u32);

impl MyTrait for Foo {
    fn id(&self) -> i64 {
        -(self.0 as i64)-1 // negative to avoid collisions with Bar
    }
}

struct Bar(String);

impl MyTrait for Bar {
    fn id(&self) -> i64 {
        self.0.len() as i64 // positive to avoid collisions with Foo
    }
}

现在，我们必须实现 Hash和 Eq ，为了把 MyTrait在 HashMap .但是如果我们为 MyTrait 做这件事，我们得到了一个不能是 trait 对象的 trait，因为 MyTrait没有大小。让我们为 Box<Trait> 实现它，其大小为:

impl Hash for Box<MyTrait> {
    fn hash<H>(&self, state: &mut H) where H: Hasher {
        self.id().hash(state)
    }
}

impl PartialEq for Box<MyTrait> {
    fn eq(&self, other: &Box<MyTrait>) -> bool {
        self.id() == other.id()
    }
}

impl Eq for Box<MyTrait> {}

我们使用了 id实现方法 eq和 hash .

现在，想想 Box<MyTrait> : 1.它是大小; 2.它实现了 Hash和 Eq .这意味着它可以用作 HashMap 的 key 。 :

fn main() {
    let foo = Foo(42);
    let bar = Bar("answer".into());
    let mut my_map = HashMap::<Box<MyTrait>, i32>::new();
    my_map.insert(Box::new(foo), 1);
    my_map.insert(Box::new(bar), 2);

    println!("{:?}", my_map.get(&(Box::new(Foo(42)) as Box<MyTrait>)));
    println!("{:?}", my_map.get(&(Box::new(Foo(41)) as Box<MyTrait>)));
    println!("{:?}", my_map.get(&(Box::new(Bar("answer".into())) as Box<MyTrait>)));
    println!("{:?}", my_map.get(&(Box::new(Bar("question".into())) as Box<MyTrait>)));

}

输出:

    Some(1)
    None
    Some(2)
    None

试试看: https://play.integer32.com/?gist=85edc6a92dd50bfacf2775c24359cd38&version=stable

我不确定它是否解决了您的问题，但我真的不知道您要做什么...