Copyless lookup in BTreeMap

help
1

I was trying to optimize an allocation out of a BTreeMap lookup and ran into problems. BTreeMap::get() looks like it was meant to solve this problem however it requires using the Borrow trait to work. The problem is that Borrow::borrow requires returning a reference, which effectively requires that the value exists in the original type. This doesn't work in my case as there is no useful type I can use.

This is my key type.

#[derive(Clone,Debug,Eq,Ord,PartialEq,PartialOrd)]
pub enum Key {
	Local(usize),
	Pub(String),
}

I wan't to prevent requiring an allocation of the String when doing a lookup, my first thought was something like the following but it doesn't work.

impl<'a> std::borrow::Borrow<KeyRef<'a>> for Key {
	fn borrow(&self) -> KeyRef<'a> {
		match *self {
			Key::Local(id) => KeyRef::Local(id),
			Key::Pub(ref s) => KeyRef::Pub(s),
		}
	}
}

#[derive(Clone,Debug,Eq,Ord,PartialEq,PartialOrd)]
pub enum KeyRef<'a> {
	Local(usize),
	Pub(&'a str),
}

However this fails as Borrow requires returning &T not just T.

error[E0053]: method `borrow` has an incompatible type for trait
  --> src/dict.rs:39:2
   |
39 |     fn borrow(&self) -> KeyRef<'a> {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected reference, found enum `dict::KeyRef`
   |
   = note: expected type `fn(&dict::Key) -> &dict::KeyRef<'a>`
              found type `fn(&dict::Key) -> dict::KeyRef<'a>`

I was wondering if:

  1. There is a solution to prevent allocation in this case.
  2. Is there, or is there a need for, some Borrow-like trait which allows returning any T, rather then only &T? This would allow returning a "compatible" type which doesn't necessarily need to be contained in the "parent" type.
2

Yeah, this is an issue that crops up from time to time. Indeed there’s a need for a trait that allows returning values. There have been some threads here on this before - I’m on mobile or else I’d try to find them :slight_smile:.

In the meantime, can you change your Pub variant to store a Cow<'static, str>? Or you can make it Cow<'a, str> but then the Key enum will gain a lifetime parameter.

3

I have failed to come up with the right keywords. If you could try searching at a better time it would be appreciated.

This doesn't really work in my case as the strings are not static. The lifetime parameter also wouldn't work as there is no reasonable place to bind the lifetime. I could cheat around it via unsafe cast to &'static but would prefer to avoid that.

4

What do you mean exactly? Can you show an example of how you’d query the BTreeMap? Specifically, where does the non-owned string slice that you’d like to use come from?

5

Some more searching turned up Making TRust-DNS faster than BIND9 which seems related.

6

In my case it comes from a large in-memory buffer. I'm using a string located in the buffer to look up something in the map.

What I meant for binding the lifetime is that the object holding the map doesn't have any lifetime and won't be able to have a member which has a lifetime parameter.

7

Yup, that's one of them. Another scenario is this Equivalent trait in the ordered_map crate, which is meant to allow the type of lookup you'd want here.

8

Ah, I see. Using Cow<'static, str> with an unsafe hack to transmute a local Cow to 'static, although unfortunate, seems fairly safe.

9