Why can't the Rust compiler infer the T type parameter in this BTreeMap::range call?

help
1

When I try to compile this code in Rust Playground using the default settings, I get the following error:

use std::collections::BTreeMap;
use std::ops::Bound::{Included, Excluded};

pub fn get_range(map: &BTreeMap<String, i32>, start: &str, end: &str) -> Vec<(String, i32)> {
    map
    .range((Included(start), Excluded(end)))
    .map(|(k, v)| (k.clone(), v.clone()))
    .collect()
}


pub fn main() {
    let map = BTreeMap::from_iter(vec![
        ("cherry".to_string(), 3),
        ("apple".to_string(), 1),
        ("banana".to_string(), 2),
    ]);

    let range = get_range(&map, "apple", "cherry");
    println!("Range [apple, cherry): {:?}", range);

}

Exited with status 101

Standard Error

   Compiling playground v0.0.1 (/playground)
error[E0283]: type annotations needed
    --> src/main.rs:6:6
     |
   6 |     .range((Included(start), Excluded(end)))
     |      ^^^^^ cannot infer type of the type parameter `T` declared on the method `range`
     |
     = note: cannot satisfy `_: Ord`
note: required by a bound in `BTreeMap::<K, V, A>::range`
    --> /playground/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/collections/btree/map.rs:1429:12
     |
1427 |     pub fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V>
     |            ----- required by a bound in this associated function
1428 |     where
1429 |         T: Ord,
     |            ^^^ required by this bound in `BTreeMap::<K, V, A>::range`
help: consider specifying the generic arguments
     |
   6 |     .range::<T, (Bound<&str>, Bound<&str>)>((Included(start), Excluded(end)))
     |           +++++++++++++++++++++++++++++++++

error[E0283]: type annotations needed
    --> src/main.rs:6:6
     |
   6 |     .range((Included(start), Excluded(end)))
     |      ^^^^^ cannot infer type of the type parameter `T` declared on the method `range`
     |
     = note: multiple `impl`s satisfying `String: Borrow<_>` found in the following crates: `alloc`, `core`:
             - impl Borrow<str> for String;
             - impl<T> Borrow<T> for T
               where T: ?Sized;
note: required by a bound in `BTreeMap::<K, V, A>::range`
    --> /playground/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/collections/btree/map.rs:1430:12
     |
1427 |     pub fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V>
     |            ----- required by a bound in this associated function
...
1430 |         K: Borrow<T> + Ord,
     |            ^^^^^^^^^ required by this bound in `BTreeMap::<K, V, A>::range`
help: consider specifying the generic arguments
     |
   6 |     .range::<T, (Bound<&str>, Bound<&str>)>((Included(start), Excluded(end)))
     |           +++++++++++++++++++++++++++++++++

For more information about this error, try `rustc --explain E0283`.
error: could not compile `playground` (bin "playground") due to 2 previous errors

When i modify the range call to this: range::<str, _>((Included(start), Excluded(end))). The code runs successfully.

Standard Output

Range [apple, cherry): [("apple", 1), ("banana", 2)]

I do not really understand the compiler reasoning. In my opinion, it should be clear from the trait bounds of the range method that the T parameter can only be a str in this case.

Am I missing something? Would the compiler see it differently? Could someone help me with this?

2

I believe this is because there is more than one possibility for this bound to be satisfied:

pub fn range<T, R>(&self, range: R) -> Range<'_, K, V>
where
    T: Ord + ?Sized,
    K: Borrow<T> + Ord, // <--- for your example: `String: Borrow<T>`
    R: RangeBounds<T>,

// Applicable implementations elsewhere
impl<T> Borrow<T> for T where T: ?Sized { ... }
impl Borrow<str> for String { ... }

Namely, T = String or T = str satisfies String: Borrow<T> for an unknown T. The compiler doesn't do an exhaustive search and stops instead of trying both possibilities. In contrast, if K = i32 like in the example here, there is only one applicable Borrow implementation (with T = i32).

Why not just "try harder"? Compile time for one, but additionally: it makes more things break when adding new implementations of traits. Adding trait implementations is supposed to be a non-major-breaking change in many cases, but this behavior of "if there's only one implementation, choose it" causes the addition of implementations to cause significant breakage in practice, because what used to be inferred now causes errors like your OP.

I.e. it's undesirable for inference to be too strong, as it can cause code stagnation. (Some feel the "only one implementation" behavior is already too strong.)

3

Thank you for your answer. However, if start and end are of type String, shouldn't the T parameter also be explicitly declared as String?

Because in this case, the compiler infers that T is a String(correctly) even without a specific type declaration. This range((Included(start.to_string()), Excluded(end.to_string()))) compiles and runs fine for me.

4

You're correct that my reply doesn't explain why that compiles. In that case I think it's because we have

// Applicable to `(Bound<&str>, Bound<&str>)` with `T = &str`
// Applicable to `(Bound<String>, Bound<String>)` with `T = String`
impl<T> RangeBounds<T> for (Bound<T>, Bound<T>)

// Applicable to `(Bound<&str>, Bound<&str>)` with `T = str`
// (Not applicable to `(Bound<String>, Bound<String>)`)
impl<'a, T> RangeBounds<T> for (Bound<&'a T>, Bound<&'a T>)
where
    T: 'a + ?Sized,

I.e. another "only one applicable implementation" route that has a single possibility.

5

Here's a playground that demonstrates how adding implementations of the traits that the "one applicable implementation" inference behavior is relying on can cause breakage of the i32 and String use cases.

6

I think I understand now. Thank you very much for your help.