indexing is invariant with respect to key

[nikomatsakis]

The [] operator is treated as invariant with respect to the key type. We should allow subtyping, I think. Consider this example:

#![allow(warnings)]

use std::collections::HashMap;
use std::ops::Index;

fn test<'long, 'short>(map: HashMap<&'long String, u32>, key: &'short String) -> u32 {
    // works: 
    // *map.get(&key).unwrap()
    
    // works:
    // *Index::index(&map, &key)
    
    // does not work, but should:
    map[&key]
}

fn main() {}

Indexing is by-value, so really it should be fine to "upcast" the key.

For reference, there are many workarounds. The example shows 2, but another is to "upcast" the map:

{ let map: &HashMap<&'short String, u32> = &map; map[&key]; }

[arielb1]

This should be fixed by rust-lang/rfcs#2147 if that is implemented

[jackh726]

I reassigned this to wg-traits; nowadays we do a lot around the typesystem

[jackh726]

We talked about this in the types triage meeting today. We decided that this would be a nice enhancement, and really only needs someone to put in the time to implement it. But it's not on our roadmap.

[compiler-errors]

Mentor instructions:

This seems pretty easy to do, though it needs some consideration for where to actually place the modifications, some testing, and some research into (and subsequent fixing of) whether this affects other operators such as + -- I believe it does based off of my cursory investigation into this issue. We'll also possibly need to run crater, though I doubt this affects inference heavily so I don't expect to see much there.

Anywho, the simple steps are:

• determine the discrepancy between type-checking the index operator and type-checking methods
• fix the problem with the lifetime of the index's LHS not being shortened
• generalize the fix to other operators as needed (binops and indexmut come to mind)
• add relevant tests, queue up a crater run if needed
• analyze the crater run if needed
• land, profit 🎉

I've embedded what I think is an accurate description of the issue here, though you're welcome to not look at it if you want to work out this issue alone. I don't recommend going through the investigation alone, but just in case, I've nested the explanation.

Specifically, the way that autoderef works for the index operator differs from the way that method probing and subsequent confirmation works. For method probe, the self ty ("receiver") of a method call always is "generalized" by supertyping it against a fresh inference variable. This means that instead of thinking of Index::index(&map, &key) as being equivalent to <HashMap<&'long String, u32> as Index<_>>::index(...), it instead looks more like <HashMap<&'1 String, u32>>::index(&map, &key) where 'long: '1.

We instantiate no such fresh inference variable for the LHS of the index operator, and instead pass the type of the thing being indexed directly into the final steps of method confirmation. Thus the 'long lifetime stays in the method call we end up with, and we are required to relate 'short = 'long. So map[&key] turns into something like: <HashMap<&'long String, u32> as Index<_>>::index(&map, &key). In fact, if you try that on playground, you can see it reproduces the exact same issue.

Interestingly, this is also due to the fact that we're passing &key, and not key into the index's RHS. That means that we end up using this implementation of Borrow, which requires strict type equality between the type and the key.

[ekuecks]

@rustbot claim

[ekuecks]

This is now fixed on master, presumably by NLL Stabilization, cc @compiler-errors