Any tricks for generic overlap with references?

[cuviper]

In short, I want Index<&Q> and Index<Idx> for IndexMap, but I can't find a way to constrain this to convince the compiler that they are distinct. Since &T is fundamental, and we don't have negative impls, maybe it's just not possible.

---

For IndexMap<K, V, S>, we currently have a few indexing methods, roughly:

impl<K, V, S> IndexMap<K, V, S> {
    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
    where
        Q: Hash + Equivalent<K>;
    pub fn get_index(&self, index: usize) -> Option<(&K, &V)>;
}

impl<'a, K, V, Q: ?Sized, S> Index<&'a Q> for IndexMap<K, V, S>
where
    Q: Hash + Equivalent<K>,
    K: Hash + Eq,
    S: BuildHasher, 
{
    type Output = V;
    fn index(&self, key: &'a Q) -> &V;
}

I would like to add Index<usize> too, and this seems OK:

impl<K, V, S> Index<usize> for IndexMap<K, V, S> {
    type Output = V;
    fn index(&self, index: usize) -> &V;
}

But going even further, I would like to make the index type generic, both in the API and how we store it in the data structure. For example, rustc often uses u32 indexes for its data types that it asserts will never get too big for that.

So, add a parameter IndexMap<K, V, S, Idx> and use that instead of usize everywhere, e.g.:

trait AsIndex { ... }
impl<K, V, S, Idx: AsIndex> Index<Idx> for IndexMap<K, V, S, Idx> {
    type Output = V;
    fn index(&self, index: Idx) -> &V;
}

Now the compiler says this conflicts with Index<&Q>, because Idx could be a reference itself. Is there any way I can constrain these to make them definitely distinct?

Here's a simplified playground.

[RustyYato]

No, unfortunately you can't constrain Idx to not be a reference, exactly because it is a fundamental type. One way around this is to newtype either the reference or the Idx version, (whichever is less common).

Another way to accomplish the same thing is to implement AsIndex for &_ and go through that, I think this will be more successful. This way &_ just works. (This is kind of how Index works for slices). Like so:

Rust Playground

[cuviper]

@RustyYato

Another way to accomplish the same thing is to implement AsIndex for &_ and go through that, I think this will be more successful. This way &_ just works.

That's a promising start!

One caveat is that I do want Idx to be a parameter on the container, and it should only accept indexes of that type (or hash-lookup &Q). This is for type safety, so you can have IndexSet<Foo, FooIndex> and IndexSet<Bar, BarIndex> and not allow indexes to cross into the wrong set. Plus, in the actual implementation we do store the real index in the hash table, so it's not just a phantom like I wrote in my playground example.

I think maybe the answer is that we don't really need to provide Index<Idx> generically. We can provide the common cases, Index<usize> for IndexSet<T, usize> and Index<u32> for IndexSet<T, u32>, and then users with a newtype index can implement their own Index<FooIndex> for IndexSet<Foo, FooIndex> easily enough. The inherent fn get_index will change to Idx, so custom Index is just a small wrapper on that with an unwrap/expect.

@RustyYato

(This is kind of how Index works for slices).

I haven't really though about this before, but is SliceIndex actually needed for coherence? Or is it just structured this way to help share code?