Tracking Issue for Equivalent and Comparable traits

[conradludgate]

Feature gate: #![feature(comparable_trait)]

This is a tracking issue for adding the Comparable trait to core, to be used by BTreeMap.

See the https://docs.rs/equivalent/latest/equivalent/ trait.

The Equivalent and Comparable traits allow for more generalised accessors for BTreeMap or HashMap than what Borrow + Ord/Borrow + Eq can allow today.

Public API

// core::cmp

pub(crate) trait Equivalent<Q: ?Sized> {
    fn equivalent(&self, key: &Q) -> bool;
}

impl<K: ?Sized, Q: ?Sized> Equivalent<Q> for K
where
    K: Borrow<Q>,
    Q: Eq,
{
}

pub(crate) trait Comparable<Q: ?Sized>: Equivalent<Q> {
    fn compare(&self, key: &Q) -> Ordering;
}

impl<K: ?Sized, Q: ?Sized> Comparable<Q> for K
where
    K: Borrow<Q>,
    Q: Ord,
{
}

// alloc::collections::btree
impl<K, V> BTreeMap<K, V> {
    fn get<Q>(&self, key: &Q) -> Option<&V>
    where
        Q: ?Sized,
        K: Comparable<Q>;
}

Steps / History

(Remember to update the S-tracking-* label when checking boxes.)

• Implementation: introduce the Comparable trait for BTree operations #144506
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• Should we use K: Comparable<Q> or Q: Comparable<K>. Flip K and Q indexmap-rs/equivalent#5

Footnotes

1. https://std-dev-guide.rust-lang.org/feature-lifecycle/stabilization.html ↩

[cuviper]

• Should we use K: Comparable<Q> or Q: Comparable<K>.

The latter is what equivalent currently uses, but as I noted in indexmap-rs/indexmap#253 (comment), it sometimes helps type inference to use the former.

However, this also has an impact on downstream generic impls. Consider:

struct Foo;
impl<T> Equivalent<T> for Foo {
    fn equivalent(&self, _: &T) -> bool { true }
}

struct Bar;
impl<T> Equivalent<Bar> for T {
    fn equivalent(&self, _: &Bar) -> bool { true }
}

With K: Equivalent<Q> (playground), neither of these are allowed:

error[E0119]: conflicting implementations of trait `Equivalent<_>` for type `Foo`
error[E0210]: type parameter `T` must be covered by another type when it appears before the first local type (`Bar`)

But with Q: Equivalent<K> (playground), the first one is allowed -- it avoids the conflict as long as Q (Foo) doesn't implement Eq itself.

This may not be a realistic need, but I encountered it while trying to flip this test around:
https://github.com/indexmap-rs/indexmap/blob/main/tests/equivalent_trait.rs

[Jules-Bertholet]

Q: Comparable<K> allows Q = &dyn Comparable<K>. (IDK how useful that is)