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.

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 HashMap with trait Hash
• struct BTreeMap with trait Ord

Sample codes

1. 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?
}

1. 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

1. the strictest way Only allow casting of T <-> T + Impl, &T <-> &(T + Impl), and &mut T <-> &mut(T + Impl) This is just a better newtype pattern.

2. the most detailed way Disable implementation casting from HashMap<K + Hash use HashImpl1, _> to HashMap<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

1. disable implementation casting on HashMap

   #[disable_impl_casting]
   pub struct HashMap<K, V> {}
   

2. disable implementation casting on HashMap with K

   pub struct HashMap<#[disable_impl_casting(all)]K: Hash, V> {}
   

3. disable external impl of Hash In 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

1. different implementation the Key with a different Hash implementation

   impl 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);
   

2. inner different implementation the inner type of Key with a different Hash implementation

   impl 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);
   

3. indirect implementation the inner type of Key with a different Display implementation but affects Hash of Key

   struct 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);
   

Analyzing Whether Existing Forum Proposals Can Solve the Three Issues Above

• Named impl with Implementation Selection Variant TODO
• [Pre-RFC] Selectable Trait Implementations TODO
• [Pre-RFC] Scoped impl Trait for Type TODO