TreeMap: find_with is surprising

[olivren]

As far as I understand, the merged PR #15220 introduces the methods find_with and find_mut_with on TreeMap, in order to provide a general solution to the problem of finding an equivalent string key. In particular, these methods make it possible to search a TreeMap using String keys to be searched without performing an allocation, using t.find_with(|k| "test".cmp(&k.as_slice()).

I see an issue here : this method only works if the logic of the closure passed as an argument is exactly the same than the logic used to provide the natural ordering of the keys. Using a different logic in the comparision closure does not work as expected, and gives random result.

The documentation on these methods don't warn about this very strong restriction, and instead they present a wrong use of the API : using these methods to find a string by performing case insensitive comparisions. It happens that the provided example works as expected, but it is easy to modify this example such that the search does not find the expected result.

Here is a variation of the provided example:

extern crate collections;
fn main() {
    use std::ascii::StrAsciiExt;

    let mut t = collections::treemap::TreeMap::new();
    t.insert("a1", "a1");
    t.insert("A2", "a2");

    let ua_key = "a1";
    let ua = t.find_with(|&k| {
       ua_key.cmp(&k.to_ascii_lower().as_slice())
    });

    println!("{}", ua);
}

This prints None.

[olivren]

As the provided example was part of the PR, I think the author of this change didn't realize that such a strong restriction exists on this method. I don't think it's just a documentation issue.

My opinion is that these methods have too much potential for being misused, compared to their benefits (saving one allocation), and that we should remove them.

[thestinger]

Avoiding the memory allocation is important and is a feature provided by C++. It could be done by adding yet another trait... but it won't work well with the current trait coherence rules.

[olivren]

Well, could we achieve this by passing a "conversion" closure instead of a "comparision" closure ?

Something along the lines of :

fn find_convert<'a, T>(&'a self, T: &key, f: |&K| -> &T) -> Option<&'a V>

That could be used like t.find_convert("test", |k| k.as_slice()).

(Sorry I'm pretty sure I got the lifetimes and references wrong, but the idea is here).

[thestinger]

@olivier-renaud: No, that's not enough. You're only considering one special case. In C++, and with this method in Rust, you can use a rope type to perform a lookup in a tree storing String keys. The C++ way relies on operator< allowing any number of overloads.

[olivren]

@thestinger ok, I see the problem now. Indeed, the design of find_with seems reasonable given this use case.

cc @vhbit and @alexcrichton, who worked on the original PR. Maybe they will have some ideas to alleviate the problem.

[alexcrichton]

I'm fine with updating the documentation, but an interface such as this is quite powerful and I don't think that we should consider removing it. No safe action can be taken to trigger memory unsafety, which is what really matters, and in general Rust can't do much in preventing logic errors outside of the typesystem.

[vhbit]

Simplified example in #15749

[thestinger]

I consider this fixed by the documentation update in #15749.