Implement Hash on IndexMap and IndexSet

[lucab]

I'm currently looking into embedding an IndexMap into a larger recursive enum (which looks pretty similar to this). However I hit a blocker on my journey, as the type-checker complains that IndexMap does not implement Hash (duh).

While I think in theory it is quite unlikely to have a usecase where an IndexMap is used as an hashable key, the type system is technically correct on this. Would a PR to derive Hash on all the relevant types up to IndexMap+IndexSet be welcome here? For reference, within stdlib BTreeMap implements it but HashMap doesn't.

[cuviper]

See the closed #67 -- the main challenge is that Hash needs to be consistent with Eq.

[lucab]

Meh, I should have searched better. Also, I was too naïf so I have now retitled this.

[bluss]

I'm going to close this as there is no use case proposed for hashing the indexmap nor an algorithm that it should use. If I read the original report correctly, the map is embedded into a bigger type and it's entirely possible for you to define a domain specific hash and equality for that specific case.

[lucab]

@bluss glad that you are back! As an afterthought related to this, I was wondering if PartialEq should behave like the BTreeSet one instead, by taking item-order into account too?

[cuviper]

You can also use Iterator::eq to compare in order.

[lucab]

Sure, but I am talking about the commonly-used comparison, which is a potential hazard for anybody actually relying on insertion order for semantics.
As a quite common usecase for an example, let's take "de-duplicated ordered policy rules":

extern crate indexmap; // 1.0.2

// Policy: subject - verb - object
type Policies = indexmap::IndexSet<(&'static str, &'static str, &'static str)>;

fn main() {
    let mut rules1 = Policies::new();
    rules1.insert(("user", "allow", "ssh"));
    rules1.insert(("user", "deny", "ssh"));

    let mut rules2 = Policies::new();
    rules2.insert(("user", "deny", "ssh"));
    rules2.insert(("user", "allow", "ssh"));

    // This does not panic right now.
    assert_eq!(rules1, rules2)
}

[bluss]

@lucab What you're saying makes sense, but a guiding tenet here has been to be a drop-in HashMap replacement, and this would break with that. I think this means that by default, indexmap will not implement your suggestion. You could use indexmap to implement it for your own policies collection, and we could provide an ordered comparison method.