Equiv and HashMap need a better interface

[alexcrichton]

Right now we have find_equiv, but nothing else on the hash map implementation that we have. We have received a few PRs for adding more *_equiv methods, and we need to decide how these are going to work out.

I envision one of three routes to take:

1. Purge *_equiv and figure out a better way of not allocating when looking up in maps with keys of ~str
2. Remove everything except find_equiv
3. Make *_equiv variants of all functions.

[lifthrasiir]

Some thought on the HashMap design: How about making HashMap accept an optional comparator for arguments? Every method in HashMap starts with finding the slot by some key, so that's what really has to be refactored. So the HashMap signature may read HashMap<K, V, ArgKey = K, ArgComp = Eq<K>>, and there would be an adapter from the Eq-based HashMap to the Equiv-based HashMap:

impl<K:Hash+Eq,V> HashMap<K,V,K,Eq<K>> {
    pub fn into_equiv<ArgKey>(self) -> HashMap<K,V,ArgKey,Equiv<ArgKey>> { ... }
}

This won't change the casual use of Eq-based HashMaps (always constructed using new method), and Map and MutableMap traits won't change. Moreover, since it is just a matter of changing searches by key such adaptor methods do not incur much cost (no rehashing, for example). As long as ArgKey is easy to infer, this design is far better than the current one in my opinion.

[nikomatsakis]

@pcwalton has an interesting use case for Equiv-based lookups: in servo they have a hashtable that is constructed using a case-insensitive hash, but then they do case-sensitive lookups using a different equality comparator. This use case cannot be accommodated by having a comparator per map.

If we had completed DST (#6308), then I was thinking that we could have a hashtable intended for DST keys. The main difference would be that this table's insert() method would take ~K and not K, and find() and friends would take &K as today. In this case, K would be str or [u8] (or possibly user-defined structs with a last field that is DS). It would be a shame to require a distinct hashtable, but I imagine we could abstract out most of the implementation. I don't yet see how we can have a single hash that takes both non-pointer keys (Foo) and DST keys (str).

There was a previous proposal (now closed, I think) to just only have the _equiv family of functions. Perhaps we were in undue haste to close that.

[zkamsler]

If types that implemented Eq were Equiv to itself, then the _equiv versions would be a strict superset of the standard ones. The only things that require the actual key type are the methods that may insert a new value (which is admittedly quite a few). C++14 does a similar thing by templatizing many of the methods of the stl containers (e.g. http://en.cppreference.com/w/cpp/container/map/find).

But with a more complex signature, it may less easy to understand, with somewhat less specific error messages if there are compiler errors. It also depends on the assumption that the key-equivalent hashes to the same value as the key itself, which is likely but not certain.

impl<T:Eq> Equiv<T> for T {
    fn equiv(&self, other: &T) -> bool { self.eq(other) }
}

[aturon]

cc me

[aturon]

A further note on the option of providing only equiv-style methods:

In some sense, methods like find_equiv are generalizations of find, but the current trait system makes it so that you cannot usefully do impl<T> Equiv<T> for T. (Once you do that you can't provide further impls of Equiv.)

If @nikomatsakis's where clause proposal lands, I wonder if we could provide such an impl using a multi-parameter version of Equiv. That way, we could give only methods that use the Equiv approach, but they would work even when you're using the key type itself, eliminating the API redundancy.

The signature would look something like:

fn find<'a, Q>(&'a self, k: &Q) -> Option<&'a V>
    where Q: Hash<S>, () : Equiv<K, Q>

using the trick of encoding multiparameter typeclasses via impls on the unit type.

We'd also have impl<T> Equiv<T, T> for (), so that this find is usable in the same way the current find is -- thus merging the find and find_equiv functionality.

But as @zkamsler says (and @pcwalton pointed out elsewhere), this makes the signature for basic HashMap operations harder to understand. So we trade complexity in API size for complexity in signatures.

---

Another possibility might be to provide an additional type parameter to the HashMap itself -- basically, a type for borrowed keys. If we could make this default to &K, it would be hidden most of the time. But this would let you specify that you want a HashMap with String keys but using &str for lookups. With sufficient hiding/defaulting of this extra parameter, we could make the default case look just like the current interface. (This is somewhat similar to @lifthrasiir's suggestion above, I think.) This would allow us to drop the _equiv methods in favor of the normal ones.

If that's too complex, yet another option would be to use something like the above generic implementation internally, but expose multiple instances of it. Something like: GenericHashMap which takes OwnedKey and BorrowedKey type parameters, and HashMap which takes K and sets OwnedKey = K and BorrowedKey = &K. We could then provide e.g. DSTHashMap.

---

One other thing: methods like find_or_insert currently take an owned key, which is discarded if the key is already in the map. An alternative that covers most use-cases would be to require K to be Clone, take &K, and then clone() only when needed. Since the motivation for _equiv methods is mainly to avoid having to allocate (i.e. .find(&key.to_string())), we should strive for a solution that works for find_or_insert as well.