SliceExt: More flexible binary_search_by and binary_search_by_key

[pnkfelix]

Someone in #rust-beginners asked why the following code (or something similar) does not compile (playpen):

#[derive(Debug)]
struct Assignment {
    topic: String,
    partition: i32,
}

fn main() {
    let xs = vec![
        Assignment { topic: "abc".into(), partition: 1 },
        Assignment { topic: "def".into(), partition: 2 },
        Assignment { topic: "ghi".into(), partition: 3 },
    ];

    let key: &str = "abc";
    let r = xs.binary_search_by_key(&key, |e| &e.topic);
    println!("{:?}", r.map(|i| (i, &xs[i])));
}

The answer, AFAICT, is that the signature for the fn binary_search_by and fn binary_search_by_key methods in SliceExt are a bit more restrictive to their callers than warranted.

Here is their current signature:

#[unstable(feature = "core_slice_ext",
           reason = "stable interface provided by `impl [T]` in later crates",
           issue = "32110")]
#[allow(missing_docs)] // documented elsewhere
pub trait SliceExt {
    type Item;
    ...
    #[stable(feature = "core", since = "1.6.0")]
    fn binary_search_by<F>(&self, f: F) -> Result<usize, usize>
        where F: FnMut(&Self::Item) -> Ordering;
    #[stable(feature = "slice_binary_search_by_key", since = "1.10.0")]
    fn binary_search_by_key<B, F>(&self, b: &B, f: F) -> Result<usize, usize>
        where F: FnMut(&Self::Item) -> B,
              B: Ord;
    ...
}

Some things to note:

• The methods are stable, but the trait (and its impl on [T]) are not. This may mean we have room to breathe here.

• The reason the code is not compiling, as I understand it, is that the bounds on the F type parameter have their lifetimes elided and can be expanded effectively to this:

  F: for <'b> FnMut(&'b Self::Item) -> B,

• The bound above on F is actually quite a strict restriction on the closure F. It is saying that the closure cannot assume that the given reference to an item will live any longer than the invocation of that closure.

  • The reality about how the binary search procedure works means that in practice one can assume something stronger: one can assume that the references passed to the callback actually live as long as the self reference of the overall binary search invocation.

  • In other words, I am suggesting that the signature could (and perhaps should) look like this:

    fn binary_search_by_key<'a, B, F>(&'a self, b: &B, f: F) -> Result<usize, usize>
    where F: FnMut(&'a Self::Item) -> B, B: Ord, Self::Item: 'a;

  • In this revised signature, the lifetime of each Self::Item reference is quite long-lived.

  • This is enough to allow the original code posted to #rust-beginners to compile.

I have a demonstration of the above in the playpen here: https://is.gd/ocGRgw

---

I am pretty sure that if we can make the above change to the signature of fn binary_search_by_key, we probably should.

• We should probably leave the signature of fn binary_search_by alone, since I am not convinced there is much benefit to generalizing that, though it should, theoretically speaking, be possible to make a test case that would only start compile with an analogous generalization.
  • (As demonstrated in the playpen https://is.gd/ocGRgw , both methods can be implemented in terms of an appropriately generalized binary_search_by.)

The only question I have at this point is if we can make the change e.g. in 1.11 or 1.12, if 1.10 is released as is.

(I suspect we can make the change. If I understand the stability rules correctly, no one is allowed to implement or even extend the SliceExt trait outside of libstd, so in changing the signature of a method like this is only going to affect the code making calls to these methods, and I think that the change suggested here will only make code start compiling; it shouldn't cause any code to stop compiling. Unless I am overlooking some subtle time inference issue or some other problem...)

Cc #32110

[pnkfelix]

cc #33018

[sfackler]

This change seems reasonable to me - cc @rust-lang/libs

[brson]

This is an easy change to make - just make the change as suggested and add the original example as a test case.

[alexcrichton]

Yeah we're definitely well within our rights here to assume that no one else is implementing this trait, so in that sense we're fine. This also looks to me like it should be a backwards-compatible modification in terms of not actually causing any code to stop compiling.

In that sense I'm all for it as well! I'd like to run crater just to be extra sure of course, but I'd be willing to r+.

In terms of scheduling, this won't make 1.10 to be released tomorrow, and it'll definitely get in 1.12 if we land it in the next 6 weeks. We could backport to 1.11 if we really wanted, but it may not be worth it.

[creativcoder]

I'd like to work on this as my first contribution to rust std lib.

[brson]

@creativcoder You got it!