Bumping a transitive dependency breaks a build

[mathstuf]

I work on the git-checks crate and an update to rayon-core:1.4.0 broke the build somehow with this build error:

error[E0277]: the trait bound `str: std::cmp::PartialOrd<std::string::String>` is not satisfied
  --> src/checks/lfs_pointer.rs:32:27
   |
32 |             } else if key < &old_key {
   |                           ^ can't compare `str` with `std::string::String`
   |
   = help: the trait `std::cmp::PartialOrd<std::string::String>` is not implemented for `str`
   = note: required because of the requirements on the impl of `std::cmp::PartialOrd<&std::string::String>` for `&str`

I've set up commits which show the error with just a change in Cargo.lock: working build broken build. Why would updating rayon-core, a dependency only by transitivity, break the build of the git-checks crate?

This happens when using any compiler from 1.17.0 (the minimum Rust version of git-checks) through nightly. I'll try and push back to older Rust versions to see if this worked before.

Originally filed in rayon-rs/rayon#542.

[mathstuf]

It happens back to 1.13.0 as well. 1.12.0 fails because of ? usage in arrayvec.

[mathstuf]

A simple case of just a library depending on rayon (or rayon-core) doesn't reproduce the problem. I'll try and trim down even more.

[mathstuf]

Actually it does as soon as I add the extern crate rayon. Bisecting the dependency tree to find the real culprit.

[mathstuf]

OK, this project breaks:

[package]
name = "dep-break"
version = "0.1.0"
authors = ["Ben Boeckel <mathstuf@gmail.com>"]

[dependencies]
arrayvec = "~0.3"

extern crate arrayvec;
pub fn cmp(p: String, n: &str) -> bool {
    n < &p
}

Changing it to arrayvec = "~0.2" works again. Bisecting arrayvec now.

[mathstuf]

Cc: @bluss

[mathstuf]

Bisected to bluss/arrayvec@0c8f467.

[cuviper]

As I noted on the rayon bug, it does work if you explicitly dereference like n < &*p, so this would seem to be a problem with deref coercion.

I guess the most relevant part of that bisected commit is:

impl<A: Array<Item=u8>> PartialOrd<ArrayString<A>> for str

[mathstuf]

Indeed, commenting out that instance also gets a working build.

[cuviper]

A self-contained reproducer:
https://play.rust-lang.org/?gist=f56aa402ac77885767d6dc4231d0125d&version=stable

use std::cmp::Ordering;

struct Foo;

impl PartialEq<Foo> for str {
    fn eq(&self, _: &Foo) -> bool {
        true
    }
}

impl PartialOrd<Foo> for str {
    fn partial_cmp(&self, _: &Foo) -> Option<Ordering> {
        Some(Ordering::Equal)
    }
}

pub fn cmp(p: String, n: &str) -> bool {
    n < &p
}

[cuviper]

This Foo example fails all the way back to rustc 1.0.0. So maybe this is expected behavior, but it seems really unfortunate that this can't infer that we want PartialOrd<str> for str.
(especially when that's broken from afar, from a new impl in a totally separate crate!)

[mathstuf]

It seems like the deref coersion is "pushing" from the potential impls of PartialOrd on the left hand side rather than looking through available Deref implementations of the right hand side (which makes more sense to me, but I don't know the compiler internals) and it fails once a PartialOrd is found without a matching Deref when it should instead continue the search.