Tracking Issue for BTreeMap cursors

[Amanieu]

Feature gate: #![feature(btree_cursors)]

ACP: rust-lang/libs-team#141

This is a tracking issue for the Cursor and CursorMut types for BTreeMap.

A Cursor is like an iterator, except that it can freely seek back-and-forth, and can safely mutate the tree during iteration. This is because the lifetime of its yielded references is tied to its own lifetime, instead of just the underlying tree. A cursor either points to an element in the tree, or to a "ghost" non-element that is logically located after the last element and before the first element.

Public API

impl<K, V> BTreeMap<K, V> {
    fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
    where
        K: Borrow<Q> + Ord,
        Q: Ord;
    fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
    where
        K: Borrow<Q> + Ord,
        Q: Ord;
    fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
    where
        K: Borrow<Q> + Ord,
        Q: Ord;
    fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
    where
        K: Borrow<Q> + Ord,
        Q: Ord;
}

struct Cursor<'a, K: 'a, V: 'a>;

impl<'a, K, V> Cursor<'a, K, V> {
    fn move_next(&mut self);
    fn move_prev(&mut self);

    fn key(&self) -> Option<&'a K>;
    fn value(&self) -> Option<&'a V>;
    fn key_value(&self) -> Option<(&'a K, &'a V)>;

    fn peek_next(&self) -> Option<(&'a K, &'a V)>;
    fn peek_prev(&self) -> Option<(&'a K, &'a V)>;
}

struct CursorMut<'a, K: 'a, V: 'a>;

impl<'a, K, V> CursorMut<'a, K, V> {
    fn move_next(&mut self);
    fn move_prev(&mut self);

    fn key(&self) -> Option<&K>;
    fn value(&self) -> Option<&V>;
    fn value_mut(&mut self) -> Option<&mut V>;
    fn key_value(&self) -> Option<(&K, &V)>;
    fn key_value_mut(&self) -> Option<(&K, &mut V)>;

    unsafe fn key_mut_unchecked(&mut self) -> Option<&mut K>;

    fn peek_next(&self) -> Option<(&K, &V)>;
    fn peek_prev(&self) -> Option<(&K, &V)>;

    fn as_cursor(&self) -> Cursor<'_, K, V>;

    fn insert_after(&mut self, key: K, value: V);
    fn insert_before(&mut self, key: K, value: V);

    unsafe fn insert_after_unchecked(&mut self, key: K, value: V);
    unsafe fn insert_before_unchecked(&mut self, key: K, value: V);

    fn remove_current(&mut self) -> Option<(K, V)>;
    fn remove_current_and_move_back(&mut self) -> Option<(K, V)>;
}

Steps / History

• Implementation: Implement cursors for BTreeMap #105641
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• None yet.

Footnotes

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

[BenBwall]

The key method on the Cursor and CursorMut types should be unsafe. If the key is interiorly mutable you could mutate it through the shared reference and break the invariants of BtreeMap. For example if the key is of type Cell<u32> I could call key.set and change the value from 1 to 1 billion and break potentially both the "Key must be unique" and "Key must be correctly ordered" invariants of BTreeMap.

[parasyte]

As I understand it, the BTreeMap invariants are not safety invariants. If the key is changed from underneath the map, it can lead to bugs. But crucially not to memory safety violations.

The standard library docs make this distinction clear:

It is a logic error for a key to be modified in such a way that the key’s ordering relative to any other key, as determined by the Ord trait, changes while it is in the map. This is normally only possible through Cell, RefCell, global state, I/O, or unsafe code. The behavior resulting from such a logic error is not specified, but will be encapsulated to the BTreeMap that observed the logic error and not result in undefined behavior. This could include panics, incorrect results, aborts, memory leaks, and non-termination.

[BenBwall]

But the key_mut_unchecked method on CursorMut is unsafe because you might break the invariants of BTreeMap

[parasyte]

Unless there is a memory safety invariant with &mut K, I don't think it needs to be unsafe. A counterexample is BTreeMap::get_key_value(), which is safe to call, even if the key has interior mutability.

[Amanieu]

The invariant here is that if a function receives a BTreeMap<K, V> where K is a type with a "trusted" Ord implementation (such as usize) then it is guaranteed that the items in the BTreeMap will be in correctly sorted order.

[BenBwall]

You should clarify this in the docs. It's not really clear why key_mut_unchecked is unsafe reading the docs IMO

[parasyte]

FWIW, I agree that the docs are unclear. Copied directly from rust-lang/libs-team#141:

    /// Returns a mutable reference to the of the element that the cursor is
    /// currently pointing to.
    ///
    /// This can be used to modify the key, but you must ensure that the
    /// `BTreeMap` invariants are maintained. Specifically:
    ///
    /// * The key must remain unique within the tree.
    /// * The key must remain in sorted order with regards to other elements in
    ///   the tree.
    unsafe fn key_mut_unchecked(&mut self) -> Option<&mut K>;

This does not explain what exactly is "unchecked". It appears to just repeat the invariants listed in the BTreeMap docs, which claim there is no possibility of UB by breaking them.

[clarfonthey]

So, I've been trying to create my own "range map" using this API and it feels… extremely clunky to me. Since I'm mostly working with the mutable API, I'll be talking about CursorMut specifically, but I suppose that some of these can apply to Cursor as well:

The handling of "ghost elements" is extremely clunky to me. From what I understand, these only can show up at the beginning and end of the map, since all entries into the API are via lower_bound and upper_bound which by their nature will "snap" to an existing, non-element. Personally, what would make the most sense to me is to require the cursor to always point to a valid element and return an entry-like enum for the lower_bound and upper_bound methods. This way, you can still distinguish between whether you're at the edges of the map on the initial creation of the cursor while not having to handle this case for all other uses of the cursor.

In that line of reasoning, I think that move_next and move_prev would be best if they simply returned a boolean (or other sentinel value) stating whether the move was successful, simply staying at the last or first element in the map rather than potentially moving into a ghost state.

While I think that the guarantees for the key_mut_unchecked method are poorly documented as others have mentioned, I appreciate the addition of it and personally use it myself. The only issue is having to handle the Option every time like mentioned.

[Amanieu]

There are several advantages in having a ghost element:

• Insertion at a certain position "just works" after a lower_bound/upper_bound lookup, even if the tree is empty.
• After removing the last element, the cursor must still point to something.
• move_next/move_prev returning a bool is somewhat redundant given that .get() already returns an option.

With that said, I can see how it can be hard to work with. I'd be happy to try out a better API if you want to sketch one out.