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.

[jonas-schievink]

When the compiler only finds a single applicable impl, it eagerly selects it, which drives type inference forward. In this case, that infers the right-hand side to be &str, which will trigger the deref coercion. When there are more impls in scope (and apparently just doing extern crate x; pulls all impls from x into scope), this doesn't happen and the right hand side stays an uninferred type variable that is then unified with the &String on the right-hand side, which then causes the PartialOrd<String> not implemented error.

So I think this is just an unpleasant interaction of the above behaviour and the orphan rules, which allow such an impl to be written in the first place (both PartialOrd and str are from a different crate).

[mathstuf]

Hmm, OK. We've fixed it by using .as_str() in our codebase (more explicit than &*). Was hoping it could go back to the old way, but it's not a big deal for our instance.

[jonas-schievink]

Closing as not-a-bug