Rustで動的型付けっぽいKeyは作れるのか?

なぜまたこんなことを?

RustでHashSetやMapのKeyはHash+Eqである必要がある。ここで、Tで縛るのではなく、左記の条件を実対していればいかなるEntityでもKeyとして使うことのできるようにできるのかな?というのがそもそものとっかかり。

Envelopeを作る

通常hash関数は、fn hash<H: Hasher>(&self, state: &mut H) となっている。通常はこれで問題ないのだが、今回の場合、KeyをBoxに詰める必要があり、関数にGenericsが入っているとコンパイルエラーになってしまう。またfn hash(&self,state:&mut dyn Hasher)とした場合、元のhash関数を呼び出す場合に、サイズが確定できずこれもまたコンパイルエラーになる。従って以下のようなEnvelopeを作った。

use std::hash::Hasher;

pub struct Envelope<'a>(&'a mut dyn Hasher);

impl<'a, H: Hasher> From<&'a mut H> for Envelope<'a> {
	fn from(value: &'a mut H) -> Self {
		Self(value)
	}
}

impl<'a> Hasher for Envelope<'a> {
	fn finish(&self) -> u64 {
		self.0.finish()
	}

	fn write(&mut self, bytes: &[u8]) {
		self.0.write(bytes);
	}
}

ただ単に、Hasherの参照を取っている形。ただしこれで型を固定できる

AnyKey Trait

続いて、元となる型に対するRequirementを定義する

AnyKeyとなるには、Hash+Eqである必要がある。またeqを行うのにdown_castを必要とするため、Anyも必要になってくるので以下の通りになる

use crate::envelope::Envelope;
use std::any::{Any, TypeId};
use std::hash::Hash;

pub trait AnyKey {
	fn as_any(&self) -> &dyn Any;
	fn dyn_eq(&self, other: &dyn AnyKey) -> bool;
	fn dyn_hash(&self, hasher: &mut Envelope);

	fn type_id(&self) -> TypeId;
}

impl<T> AnyKey for T
where
	T: Any + Eq + Hash,
{
	fn as_any(&self) -> &dyn Any {
		self
	}
	fn dyn_eq(&self, other: &dyn AnyKey) -> bool {
		if let Some(o) = other.as_any().downcast_ref::<T>() {
			self == o
		} else {
			false
		}
	}

	fn dyn_hash(&self, hasher: &mut Envelope) {
		self.hash(hasher);
	}

	fn type_id(&self) -> TypeId {
		self.as_any().type_id()
	}
}

Key型を作る

いくら様々な型をとれるとは言っても元となるHash/MapのKeyは型 TをFixする必要がある。なので、底に対応するためにKey型を作っていこう

use crate::any_key::AnyKey;
use crate::envelope::Envelope;
use std::hash::{Hash, Hasher};

pub struct Key(Box<dyn AnyKey>);

impl Key {
	pub fn from_key<T: AnyKey + 'static>(key: T) -> Self {
		Self(Box::new(key) as Box<dyn AnyKey>)
	}
}

impl PartialEq for Key {
	fn eq(&self, other: &Self) -> bool {
		self.0.dyn_eq(other.0.as_ref())
	}
}

impl Eq for Key {}

impl Hash for Key {
	fn hash<H: Hasher>(&self, state: &mut H) {
		let mut envelope = Envelope::from(state);

		self.0.type_id().hash(&mut envelope);
		self.0.dyn_hash(&mut envelope);
	}
}

やってることはそんなに難しくなく、AnyKeyの実装に転送して結果を戻している。

実際使ってみる

それでは実際に使ってみよう

use crate::key::Key;
use std::any::Any;
use std::collections::HashSet;

pub mod any_key;
pub mod envelope;
mod key;

fn main() {
	let mut set: HashSet<Key> = HashSet::new();

	let a = 42;
	let b = &a as &dyn Any;

	dbg!(set.insert(Key::from_key("hello")));
	dbg!(set.insert(Key::from_key("hello".to_string())));
	dbg!(set.insert(Key::from_key(42i8)));
	dbg!(set.insert(Key::from_key(42i32)));

	println!("repeat again");

	dbg!(set.insert(Key::from_key("hello")));
	dbg!(set.insert(Key::from_key("hello".to_string())));
	dbg!(set.insert(Key::from_key(42i8)));
	dbg!(set.insert(Key::from_key(42i32)));
}

結果は以下の通り

[alt/src/main.rs:15:2] set.insert(Key::from_key("hello")) = true
[alt/src/main.rs:16:2] set.insert(Key::from_key("hello".to_string())) = true
[alt/src/main.rs:17:2] set.insert(Key::from_key(42i8)) = true
[alt/src/main.rs:18:2] set.insert(Key::from_key(42i32)) = true
repeat again
[alt/src/main.rs:22:2] set.insert(Key::from_key("hello")) = false
[alt/src/main.rs:23:2] set.insert(Key::from_key("hello".to_string())) = false
[alt/src/main.rs:24:2] set.insert(Key::from_key(42i8)) = false
[alt/src/main.rs:25:2] set.insert(Key::from_key(42i32)) = false

型が違うと、値が一致していても別のKeyとして扱われるようにしてある。(この辺は実装次第)

所感

普通であれば、使う可能性のある方をenumでまとめて一つのKeyとすることが定石となっている。enumであれば、元となる型をパターンマッチで容易に取得できる。

今回は、Rustの枠の中で動的型付けっぽいキーを作成することができるか気になり実際に実装してみた所比較的うまくいった気がする。とはいえAnyに投げて判定なのでパフォーマンスはそれほど稼げないだろうし、ほぼ完全にTypeEraseしてしまうことからダウンキャストする必要があるのなら、簡単なメタデータを付与しておく必要があると思う。