Nightly regression - Option::cloned method resolution

[CAD97]

unic-ucd-normal (and thus the supercrate unic) was compiling on rustc 1.21.0-nightly (e26688824 2017-08-27) but fails on rustc 1.21.0-nightly (c11f689d2 2017-08-29). (This is with the unpublished version at https://github.com/behnam/rust-unic/tree/master/unic/ucd/normal only.)
Passing build & Failing build

   Compiling unic-ucd-normal v0.5.0 (file:///D:/Christopher/Documents/Code/Rust/rust-unic/unic/ucd/normal)
error[E0034]: multiple applicable items in scope
  --> unic\ucd\normal\src\lib.rs:63:65
   |
63 |         canonical_composition(a).and_then(|table| table.find(b).cloned())
   |                                                                 ^^^^^^ multiple `cloned` found
   |
   = note: candidate #1 is defined in an impl for the type `std::option::Option<&_>`
   = note: candidate #2 is defined in an impl for the type `std::option::Option<&mut _>`

This appears to be #43738 (tracking) / #43705 (impl) that is causing this. Note that we do not have #![feature(option_ref_mut_cloned)] (it didn't exist until today(?)).

Small reproduction in #44208 (comment)

[Mark-Simulacrum]

Nominating for @rust-lang/libs. Not sure if we can do much about this -- I'd expect this not to happen, as mutability shouldn't be inferred in most cases? A smaller example would definitely be helpful.

[CAD97]

@Mark-Simulacrum I got one! It's a bit weird...

https://play.rust-lang.org/?gist=ca256a29f753fe800b3a5673f4a7efa7&version=stable

trait DataTable<V> {
    fn find(&self, needle: char) -> Option<V>;
}

impl<'a, V> DataTable<&'a V> for &'a [(char, V)] {
    fn find(&self, needle: char) -> Option<&'a V> {
        self.binary_search_by_key(&needle, |&(k, _)| k)
            .map(|idx| &self[idx].1)
            .ok()
    }
}

impl DataTable<()> for &'static [(char, char)] {
    fn find(&self, _: char) -> Option<()> {
        Some(())
    }
}

fn main() {
    static TABLE: &[(char, char)] = &[('a', 'a')];
    let x: Option<char> = TABLE.find('a').cloned();
}

It seems to be caused by the two impls here, as removing the second eliminates the error (which is why I was having trouble finding a small reproduction)

[EDITED with smaller example. Previous]

(If anyone is curious why we have [(char, V)] and [(char, char)] as DataTables, the reason is that the former is a mapping from char to some value, while the latter is range-based inclusion set. I'm in the process of changing the tuple to a dedicated inclusive range type.)

[behnam]

It looks like the actual ambiguity is cause by having implementations for both (char, V) and (char, char) types, and is not actually about ref vs mut-ref; BUT, the error detection is confused and errs on the latter, instead of the former. It seems like this confusion could be the bug that needs to be fixed here.

[alexcrichton]

The libs team discussed this yesterday and @aturon volunteered to investigate this issue. In the meantime though we decided that we probably aren't going to revert.

[Mark-Simulacrum]

@aturon Any updates? This is due to land in 1.22 (which releases next week). If not, perhaps we can reassign.

[CAD97]

Using the case in #44208 (comment), it still causes an error on beta/nightly but not on stable:

   Compiling playground v0.0.1 (file:///playground)
error[E0034]: multiple applicable items in scope
  --> src/main.rs:21:43
   |
21 |     let x: Option<char> = TABLE.find('a').cloned();
   |                                           ^^^^^^ multiple `cloned` found
   |
   = note: candidate #1 is defined in an impl for the type `std::option::Option<&_>`
   = note: candidate #2 is defined in an impl for the type `std::option::Option<&mut _>`

error: aborting due to previous error

error: Could not compile `playground`.

[Mark-Simulacrum]

Right, because stable doesn't yet have the regression -- it will once 1.22 (current beta) is released next Thursday.

[aturon]

@Mark-Simulacrum thanks much for checking in. I don't have the cycles to look into this at the moment. @eddyb or @arielb1, would one of you mind?

[eddyb]

IIRC @arielb1 made some changes in the recent past to method resolution, not sure if they're related.

[arielb1]

@aturon

This is caused by #43705, normal expected inference breakage.

[CAD97]

There's more to it than just an added fn. This case should not be offered std::option::Option::<&mut _>::cloned as an option.

Using a reproduction case as simple as I was able to make it: https://play.rust-lang.org/?gist=73317abb09e9e9b3469eb32d6a7d2545&version=beta

trait DataTable<V> {
    fn find(&self, needle: char) -> Option<V>;
}

impl<'a, V> DataTable<&'a V> for &'a [(char, V)] {
    fn find(&self, _: char) -> Option<&'a V> {
        None
    }
}

impl DataTable<()> for &'static [(char, char)] {
    fn find(&self, _: char) -> Option<()> {
        None
    }
}

fn main() {
    static TABLE: &[(char, char)] = &[('a', 'a')];
    let x: Option<char> = TABLE.find('a').cloned();
}

Run as is, we get

error[E0034]: multiple applicable items in scope
  --> src/main.rs:19:43
   |
19 |     let x: Option<char> = TABLE.find('a').cloned();
   |                                           ^^^^^^ multiple `cloned` found
   |
   = note: candidate #1 is defined in an impl for the type `std::option::Option<&_>`
   = note: candidate #2 is defined in an impl for the type `std::option::Option<&mut _>`

Comment out the second impl block, lines 11-15, it compiles fine.

Comment out the first impl block, lines 5-9, and we get

error[E0599]: no method named `cloned` found for type `std::option::Option<()>` in the current scope
  --> src/main.rs:19:43
   |
19 |     let x: Option<char> = TABLE.find('a').cloned();
   |                                           ^^^^^^
   |
   = note: the method `cloned` exists but the following trait bounds were not satisfied:
           `&mut std::option::Option<()> : std::iter::Iterator`

For completion, removing the call to .cloned() and the type specification for let x, we get

error[E0283]: type annotations required: cannot resolve `&[(char, char)]: DataTable<_>`
  --> src/main.rs:19:19
   |
19 |     let x = TABLE.find('a');
   |       

The type annotation on let x existing or not does not change the compiler output.

---

Because the two impls DataTable<&'a V> for &'a [(char, V)] and DataTable<()> for &'static [(char, char)] exist, ((&'static [('a', 'a')]) as DataTable<_>).find('a') is ambiguous. The resulting type should be Option<&char> or Option<()> depending on which DataTable impl is used. Option::cloned is only impl'd once, and only on Option<&char>, not Option<()>. More importantly, there is no mutable reference anywhere, so the compiler tripping up and suggesting Option<&mut _> makes no sense.

Whatever the issue is, it's more than the interface evolving to have multiple options. These two options should not both be considered in this case. Something with resolution must be going wrong to suggest the Option<&mut _> impl when there is no mutable reference anywhere.

[CAD97]

I have made a repro case of what I believe to be the same root issue (occurring on stable) without the stdlib fn call: https://play.rust-lang.org/?gist=1d1adac4824aa2241dc1c6bd3d38f8f8&version=stable (previously https://play.rust-lang.org/?gist=0faa6d4304f76c72d6941934c02edd97&version=stable)

struct Container<T> {
    inner: T,
}

impl<T> Container<&'static T> {
    fn do_something(&self) {
        println!("Container<&'a T>::do_something");
    }
}

impl<'a, T> Container<&'a mut T> {
    fn do_something(&self) {
        println!("Container<&'a mut T>::do_something");
    }
}

trait Issue<T> {
    fn make_container(&self) -> Container<T>;
}

impl<T> Issue<&'static T> for &'static T {
    fn make_container(&self) -> Container<&'static T> {
        Container { inner: &self }
    }
}

impl Issue<()> for &'static char {
    fn make_container(&self) -> Container<()> {
        Container { inner: () }
    }
}

fn main() {
    static ARR: &char = &'a';
    let _ = ARR.make_container().do_something();
}

Compiling gives us:

error[E0034]: multiple applicable items in scope
  --> src/main.rs:35:34
   |
35 |     let _ = ARR.make_container().do_something();
   |                                  ^^^^^^^^^^^^ multiple `do_something` found
   |
note: candidate #1 is defined in an impl for the type `Container<&'static _>`
  --> src/main.rs:6:5
   |
6  | /     fn do_something(&self) {
7  | |         println!("Container<&'a T>::do_something");
8  | |     }
   | |_____^
note: candidate #2 is defined in an impl for the type `Container<&mut _>`
  --> src/main.rs:12:5
   |
12 | /     fn do_something(&self) {
13 | |         println!("Container<&'a mut T>::do_something");
14 | |     }
   | |_____^

OK, we have conflicting impls for Container<&'static _> and Container<&mut _>, do we? Let's delete the one for Container<&'static _> then!

error[E0277]: the trait bound `&char: Issue<&mut _>` is not satisfied
  --> src/main.rs:35:17
   |
35 |     let _ = ARR.make_container().do_something();
   |                 ^^^^^^^^^^^^^^ the trait `Issue<&mut _>` is not implemented for `&char`
   |
   = help: the following implementations were found:
             <&'static char as Issue<()>>

I can open a new issue or rewrite the OP to focus on this issue directly if desired. If someone else wants to take a go at simplifying this repro down more, please do take a stab at it; I was unable to remove anything more while still reproing this behavior.

[CAD97]

Given that the inference issue is preexisting for this strange case and the regression is merely from expanding the available fn on Option, my vote is to release 1.22 as is, but to investigate this as an issue on its own right. #43705 merely opened another door to the preexisting inference issue.

[arielb1]

@CAD97

In (every version of) Rust, type inference does not consider active trait requirements when resolving type ambiguities, only inference variables (i.e. method lookup is done on Container<_>, ignoring the fact that we know &'static char: Issue<_>). This is an annoying limitation, but just removing it would add too much unpredictability.

[eddyb]

@arielb1 Could we use it only in case of ambiguity?

[arielb1]

@eddyb

That would be fragile - a predicate-saatisfying method could still shadow a valid method. Inference being guided only by type variables is a nice compromise.

[Mark-Simulacrum]

https://crates.io/crates/rabble v0.4.1 is broken by this, cc @andrewjstone

log: http://cargobomb-reports.s3.amazonaws.com/stable-1.21.0-beta-1.22.0-beta.3/beta-2017-11-13/reg/rabble-0.4.1/log.txt

[andrewjstone]

I actually worked around this on a branch for rabble a few months ago but haven't merged it in. I will say, I didn't really understand what the problem was as I'm no expert in inference, but it was fixable in a hacky sort of way. https://github.com/andrewjstone/rabble/compare/histogram#diff-12d610bc541176e32ea0df8d15d0a369

[Mark-Simulacrum]

@aturon Do you want to look into this or should we just close it? Nothing is really going to change here I think since this is on stable anyway -- might be a bug in the compiler, though.

[Mark-Simulacrum]

I believe @arielb1 believes that this isn't really a bug, and that the cause is known. As such, I'm going to close. Please comment if that's not the correct conclusion to draw from the discussion above.