Can't overload indexing for arrays

[tarsa]

Following code compiled in Rust 1.24.1, but fails to compile under Rust 1.25.0:

use std::ops;

struct MyIndex(bool);

impl ops::Index<MyIndex> for [String; 2] {
    type Output = String;

    fn index(&self, index: MyIndex) -> &String {
        match index.0 {
            false => &self[0],
            true => &self[1],
        }
    }
}

fn main() {
  let a = [String::from("ala"), String::from("ma kota")];
  println!("{}", a[MyIndex(false)]);
}

Terminal session:

$ rustup toolchain list
stable-x86_64-unknown-linux-gnu
1.24.1-x86_64-unknown-linux-gnu (default)
$ rustup default stable-x86_64-unknown-linux-gnu
info: using existing install for 'stable-x86_64-unknown-linux-gnu'
info: default toolchain set to 'stable-x86_64-unknown-linux-gnu'

  stable-x86_64-unknown-linux-gnu unchanged - rustc 1.25.0 (84203cac6 2018-03-25)

$ rustc aaa.rs
error[E0308]: mismatched types
  --> aaa.rs:10:28
   |
10 |             false => &self[0],
   |                            ^ expected struct `MyIndex`, found integral variable
   |
   = note: expected type `MyIndex`
              found type `{integer}`

error[E0308]: mismatched types
  --> aaa.rs:11:27
   |
11 |             true => &self[1],
   |                           ^ expected struct `MyIndex`, found integral variable
   |
   = note: expected type `MyIndex`
              found type `{integer}`

error: aborting due to 2 previous errors

$ rustup default 1.24.1-x86_64-unknown-linux-gnu
info: using existing install for '1.24.1-x86_64-unknown-linux-gnu'
info: default toolchain set to '1.24.1-x86_64-unknown-linux-gnu'

  1.24.1-x86_64-unknown-linux-gnu unchanged - rustc 1.24.1 (d3ae9a9e0 2018-02-27)

$ rustc aaa.rs
$ ./aaa 
ala

[nikomatsakis]

Can we get a bisection? I remember there being some PRs that changed indexing of built-in types to work with impls though, so I suspect that is the cause.

cc @rust-lang/release

[nikomatsakis]

triage: P-high

Regression, perhaps legit, but we need to see why.

[pietroalbini]

Bisected this, the regression is in #47167. cc @ivanbakel @nikomatsakis

[nikomatsakis]

@pietroalbini thanks! That's the PR I was thinking of, I believe.

[nikomatsakis]

Sigh. This was missing a T-compiler tag, so it was overlooked.

[nikomatsakis]

Ok, so, I tracked down what's going on. The answer is that we have no impls of Index for [T; N] types, only for [T]. Ordinarily, when you do &self[0], what happens is that we "autoderef" self down to the type [String; 2] and then we unsize that to [String]. At the point, the indexing impls defined for [String] kick in. But now, with this new impl, we are failing to proceed that far, and instead stopping at the impl for [String; 2] (which is defined for Index<MyIndex>).

As a workaround, the code can be fixed by doing the unsize to [String] by hand:

impl ops::Index<MyIndex> for [String; 2] {
    type Output = String;

    fn index(&self, index: MyIndex) -> &String {
        let this: &[String] = self;
        match index.0 {
            false => &this[0],
            true => &this[1],
        }
    }
}

The question is, is this the desired behavior? It seems like when we search for matching impls we are not taking the type of the index into account. Looking at the code, I can't quite see why that is. It seems like we have the info we need, we're just choosing to ignore it. I'm experimenting. For reference, this is the function that checks for whether [] should stop at a given autoderef:

rust/src/librustc_typeck/check/mod.rs

Lines 2352 to 2358 in 90463a6

	fn try_index_step(&self,
	expr: &hir::Expr,
	base_expr: &hir::Expr,
	autoderef: &Autoderef<'a, 'gcx, 'tcx>,
	needs: Needs,
	index_ty: Ty<'tcx>)
	-> Option<(/*index type*/ Ty<'tcx>, /*element type*/ Ty<'tcx>)>

The index_ty argument appears to be the type of index input (in this instance, it is an unresolved integer variable). But when we actually check to see if the trait is implemented, we choose to ignore that information:

rust/src/librustc_typeck/check/mod.rs

Lines 2382 to 2384 in 90463a6

	let input_ty = self.next_ty_var(TypeVariableOrigin::AutoDeref(base_expr.span));
	let method = self.try_overloaded_place_op(
	expr.span, self_ty, &[input_ty], needs, PlaceOp::Index);

Perhaps this is meant to be analogous to foo.bar(baz), where the type of baz is not used?

[nikomatsakis]

Still, this diff makes the test pass:

diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index db859e4205..ef5599f82b 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -2381,9 +2381,8 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
             // If some lookup succeeds, write callee into table and extract index/element
             // type from the method signature.
             // If some lookup succeeded, install method in table
-            let input_ty = self.next_ty_var(TypeVariableOrigin::AutoDeref(base_expr.span));
             let method = self.try_overloaded_place_op(
-                expr.span, self_ty, &[input_ty], needs, PlaceOp::Index);
+                expr.span, self_ty, &[index_ty], needs, PlaceOp::Index);

             let result = method.map(|ok| {
                 debug!("try_index_step: success, using overloaded indexing");
@@ -2418,7 +2417,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
                 self.apply_adjustments(base_expr, adjustments);

                 self.write_method_call(expr.hir_id, method);
-                (input_ty, self.make_overloaded_place_return_type(method).ty)
+                (index_ty, self.make_overloaded_place_return_type(method).ty)
             });
             if result.is_some() {
                 return result;

[nikomatsakis]

Now we just have to decide if we want to do that. I'll also want to check the other implications. I'm going to make a branch and start a ./x.py test to see if things break (I can't imagine what would, but you never know).

[nikomatsakis]

The main complication seems to be that we regress some of the helpful error messages around indexing.

[nikomatsakis]

Nominating for discussion in the lang-team meeting. There is a bit a question here about what behavior we want. Let me summarize:

• Currently, when you have foo[bar], we resolve it as follows:
  • figure out the type of foo (A) and bar (I):
  • autoderef A; for each type T that results:
    • check whether there is an impl of T: Index<U> for some U
      • if so, halt the autoderef loop and add an obligation T: Index<I>

Note that the index type I is not considered when we decide where to stop the autoderef loop. In the case of this example, that type is a "integral variable". The problem that results is that we first consider whether [String; 2]: Index<U> for some U — and we find that it does (for U=MyIndex) so we stop the loop. But then the obligation [String; 2]: Index<{integral}> cannot be proven and fails.

The change I made is this:

• When you have foo[bar], we resolve it as follows:
  • figure out the type of foo (A) and bar (I):
  • autoderef A; for each type T that results:
    • check whether there is an impl of T: Index<I> 👀 change: use the type I here now!
      • if so, halt the autoderef loop and add an obligation T: Index<I>

What happens as a result is that we do not halt the autoderef loop at [String; 2], because we are searching for [String; 2]: Index<{integral}> and that has no impls — and we proceed to [String]. We then succeed.

This seems good to me, but I wanted to run it by @rust-lang/lang. The current branch we probably don't want to land because the diagnostic impact is ungreat: there are many examples where people are using the wrong index type. As a result, the autoderef loop never finds any match, but the error we report says that the type is "not indexable" — where the correct thing to say is "not indexable by a value of type X". My plan was to modify the diagnostics to check if there are any index impls (just not for this index type) and change the wording in that case.

[eddyb]

Didn't we want to use the index type from the impl to enable coercing the index?

[nikomatsakis]

@eddyb that is indeed one of the questions here. We do not presently.

[nikomatsakis]

(At least that's what I remember, I can reconfirm.)

[nikomatsakis]

We discussed this in the @rust-lang/lang meeting last week but didn't come to a firm conclusion. Previously, the language was basically so that foo[bar] and foo.get(bar) type-check in a very similar way -- we use the type of foo (and not bar) to select how many auto-derefs to insert (and which trait to use, in the case of get). This leads to (in some cases) suboptimal decisions, but choosing to take the type of bar into account in the foo[bar] case also has some downsides.

One notable downside has to do with coercions. Consider the following example (which does not compile today):

use std::collections::HashMap;

fn main() {
    let map = HashMap::new();
    map.insert("foo", "bar");
    let x = &format!("foo");
    let y = map[x];
}

Here, the expected key is an &str, but we give a &String. This example does not compile today, but -- with the current setup of type-checking -- it could compile. We have roughly the information we would need at our fingertips, though we are not currently using it.

In contrast, if we make this change, we would be searching for an impl of Index<&String>, vs Index<_> for anything (of course, hash maps are complicated by the Borrow trait, and actually I'm a bit surprised that this doesn't work today — I guess the Borrow trait goes rather the other way). In particular, we would not be searching for an index impl that the given index is coercible to but rather for an exact match. We may not want to codify that behavior.

Part of the context here is that we are hoping, once the trait system impl is overhauled for chalk etc, to make more progress on being smarter about coercions and so forth, and so it may not make sense to make any changes to the core type system until we have those pieces in place, for fear of locking ourselves in (we are already, of course, locked in to the current behavior to a large extent).

A counterpoint was raised by @joshtriplett, who pointed out that this existing code had stopped compiling, albeit as a result of a bugfix, and so we ought to do what we can to keep it working. In general, I agree with this sentiment, but this specific area of change is the sort that we do consider permissible -- in particular, bug fixes etc, and specifically where the existing code can be made to work with small tweaks (here, adding a self.as_slice()[0] work work, for example, or converting to a fully qualified path like <[String] as Index>::index(...)).

[nikomatsakis]

I'm going to bump this down from P-high to P-medium.

triage: P-medium

[nikomatsakis]

@rfcbot fcp close

I propose that we do not take action to fix this -- it does mean that the code above regressed, but arguably it is behaving "to spec" now, and I am nervous that changing the behavior here will close doors we might prefer to keep open for now (see summary here).

[rfcbot]

Team member @nikomatsakis has proposed to close this. The next step is review by the rest of the tagged teams:

• @aturon
• @cramertj
• @eddyb
• @joshtriplett
• @nikomatsakis
• @nrc
• @pnkfelix
• @scottmcm
• @withoutboats

No concerns currently listed.

Once a majority of reviewers approve (and none object), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[rfcbot]

The final comment period, with a disposition to close, as per the review above, is now complete.