The Hashtable Problem: A Litmus Test for External Impl Proposals
Any proposal aiming to relax the orphan rule or enable external trait implementations must address the hashtable problem. I met the problem when I wrote my own Named Impl Draft. I selected a solution but it breaked by the indirect implementation sample.
Explain
The earliest article is The "Hashtable Problem" from nikomatsakis at 2011-12:
There is a danger with typeclasses only on functions because they permit a lack of coherence. This danger is particularly acute with collections, where the definition of a particular interface---such as hashable or ord---may be used in structuring the data structure. This renders the data structure corrupt when used with a different implementation.
Also there is a comment from @nikomatsakis 2017-2:
We called it the hashtable problem because – imagine you had a hashtable with keys to type K that is built up using one impl of Hash, but then you pass that hashtable to another module, where a distinct Hash impl is in scope. It’s going to be pandemonium. What that e-mail proposed was to solve this by making the impl “part of the type”, in a sense. At the end of the day it seemed like a lot of complexity and we opted against it – but there are real costs. I’m not sure of the best fix here.
The problem affects:
- struct
HashMapwith traitHash - struct
BTreeMapwith traitOrd
Sample codes
- example in typical scoped impl
let mut map = HashMap::<i32, &'static str>::new();
map.insert(42, "the answer to the universe"); // default hash of i32
{
use AnotherHashForI32 as impl Hash for i32;
let found = map.get(&42); // a different hash of i32, can we find the answer?
}
- example in typical named impl
let mut map = HashMap::<i32, &'static str>::new();
map.insert(42, "the answer to the universe"); // default hash of i32
let altmap = &map as &HashMap<i32 + Hash use AnotherHashForI32, &'static str>;
let found = altmap.get(&(42 as (i32 + Hash use AnotherHashForI32))); // a different hash of i32, can we find the answer?
Where is the problem from?
let key = 42;
let mut map = HashMap::<i32, &'static str>::new();
map.insert(key, "the answer to the universe"); // default hash of i32
let found = map.get(&key); // ok
let altkey = key as (i32 + Hash use AnotherHashForI32);
let mut altmap = HashMap::<i32 + Hash use AnotherHashForI32, &'static str>::new();
altmap.insert(altkey, "the answer to the universe"); // a different hash of i32
let found = altmap.get(&altkey); // ok
The code above works fine.
The problem is from the type casting of the container:
let altmap = &map as &HashMap<i32 + Hash use AnotherHashForI32, &'static str>;
With scoped impl, there are also implicitly type casting:
let mut map = HashMap::<i32, &'static str>::new();
map.insert(42, "the answer to the universe");
{
use AnotherHashForI32 as impl Hash for i32;
let found = map.get(&42); // `map` is casted, and `&42` is casted
}
Solutions (partly)
-
the strictest way
Only allow casting ofT <-> T + Impl,&T <-> &(T + Impl), and&mut T <-> &mut(T + Impl)
This is just a better newtype pattern. -
the most detailed way
Disable implementation casting fromHashMap<K + Hash use HashImpl1, _>toHashMap<K + Hash use HashImpl2, _>pub struct HashMap<#[disable_impl_casting(Hash)]K: Hash, V> {}Unsolved problems:
- inner different implementation
HashMap<(i32 + Hash use HashImpl1, i32), _> - indirect implements
- inner different implementation
-
disable implementation casting on
HashMap#[disable_impl_casting] pub struct HashMap<K, V> {} -
disable implementation casting on
HashMapwithKpub struct HashMap<#[disable_impl_casting(all)]K: Hash, V> {} -
disable external impl of
HashIn My Named impl draft, this is selected:#[disable_named_impl(exist_default)] pub trait Hash {}Unsolved problems:
- indirect implementation
Progressive Hashtable Violations via External Impls
-
different implementation the Key with a different
Hashimplementationimpl Hash for i32 use AlterHash { fn hash<H: Hasher>(&self, state: &mut H) { self.hash(state); 8.hash(state); } } let map = HashMap::<i32, i32>::new(); map.insert(42, 42); type AltKey = i32 + Hash use AlterHash; let altmap = &map as &HashMap<AltKey, i32>; let altkey = 42 as AltKey; let found = altmap.get(&altkey); -
inner different implementation the inner type of Key with a different
Hashimplementationimpl Hash for i32 use AlterHash { fn hash<H: Hasher>(&self, state: &mut H) { self.hash(state); 8.hash(state); } } let map = HashMap::<(i32,), i32>::new(); map.insert((42,), 42); type AltKey = (i32 + Hash use AlterHash,); let altmap = &map as &HashMap<AltKey, i32>; let altkey = (42,) as AltKey; let found = altmap.get(&altkey); -
indirect implementation the inner type of Key with a different
Displayimplementation but affectsHashof Keystruct Key<T: Display>(T); impl<T: Display> Hash for Key<T> { fn hash<H: Hasher>(&self, state: &mut H) { format!("{}", self.0).hash(state); } } impl Display for i32 use AlterDisplay { fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result { write!(f, "I32AlterDisplay") } } let map = HashMap::<Key<i32>, i32>::new(); map.insert(Key(42), 42); type AltKey = Key<i32 + Display use AlterDisplay>; let altmap = &map as &HashMap<AltKey, i32>; let altkey = Key(42) as AltKey; let found = altmap.get(&altkey);