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 ↩

[Bwallker]

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.

[Bwallker]

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.

[Bwallker]

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.

[jeffparsons]

I assume this is a non-starter for performance reasons, but the most "natural" feeling interface for me would be one that can point to all real elements and all points between/next to them (including start/end). There would then be convenience methods for skipping over whatever you're not interested in so you can stay in "element space" or "gap space" if you only care about one or the other most of the time.

But again, I imagine this would make the API too slow because the compiler couldn't optimise away visiting all the gaps — does that sound right?

(Edit: if this doesn't make sense, I'd be happy to sketch what I imagine would be the core API, and what would be the optional convenience layers.)

(Edit2: or you could have separate cursor types for when you're pointing at an element vs a gap, and have the navigation functions consume self and convert between them where relevant. I think that would be on par for performance with the current design?)

[clarfonthey]

Honestly, the kind of modification I was thinking of was to leverage the existing Entry API for mutable cursors, and to simply take ownership of the cursor during certain operations that might cause the entry to become vacant, returning an entry instead of just modifying the occupied entry.

[lf-]

I have been implementing a TCP segment reordering buffer (where you're storing ranges and they wrap around u32::MAX).

So I have been looking into building a wrapping iterator over a BTreeMap and it seems that implementing a wrapping mutating cursor based on this is surprisingly nontrivial: you'd have to ... somehow ... swap between a &mut BTreeMap (to create a new CursorMut when you wrap) and a CursorMut and when you get rid of the CursorMut to replace it, put the &mut BTreeMap back. This is kind of nonobvious how to do when hand rolling a generator as one does while writing these things.

I guess my feedback on this API is that it might need a function to move it back to the start or to a specified element.

[finnbear]

Can we document the potential hazard that BTreeMap::upper_bound does the opposite of C++'s map::upper_bound?

In other words, when porting C++ to Rust,

• map::lower_bound -> BTreeMap::lower_bound(Bound::Included(...))
• map::upper_bound -> BTreeMap::lower_bound(Bound::Excluded(...))

FWIW, I'm strongly in favor of both API's 🚀

[Amanieu]

Can we document the potential hazard that BTreeMap::upper_bound does the opposite of C++'s map::upper_bound?

Are you sure about this? They should map the same way.

upper_bound returns the last element below the given bound, which should match what C++'s upper_bound does.

[finnbear]

Are you sure about this? They should map the same way.

I'm more confused than I am sure, but I still get the impression that there is a hazard when porting C++ to Rust.

C++ upper_bound docs say that it "Returns an iterator pointing to the first element in the container whose key is considered to go after k."

Rust BTreeMap::upper_bound docs say that it "Returns a Cursor pointing at the last element that is below the given bound."

So, here are the results on an example map:

k1 -> v1
k2 -> v2
k3 -> v3
k4 -> v4
k5 -> v5

// C++
.upper_bound("k3") = "v4" // notably the same as .lower_bound(Bound::Excluded("k3")) in Rust
.lower_bound("k3") = "v3"

// Rust
.upper_bound(Bound::Excluded("k3")) = "v2"
.upper_bound(Bound::Included("k3")) = "v3"
.lower_bound(Bound::Excluded("k3")) = "v4"
.lower_bound(Bound::Included("k3")) = "v3"

My code

Online C++

#include 
#include 

int main ()
{
  std::map mymap;
  std::map::iterator itlow,itup;

  mymap[1]=1;
  mymap[2]=2;
  mymap[3]=3;
  mymap[4]=4;
  mymap[5]=5;
  
  itup=mymap.upper_bound (3);
  std::cout << itup->first << ' ' << itup->second << '\n';
  
  itlow=mymap.lower_bound (3);
  std::cout << itlow->first << ' ' << itlow->second << '\n';
  

  return 0;
}

Rust Playground

#![feature(btree_cursors)]

fn main() {
    use std::collections::BTreeMap;
    use std::ops::Bound;
    
    let mut a = BTreeMap::new();
    a.insert("k1", "v1");
    a.insert("k2", "v2");
    a.insert("k3", "v3");
    a.insert("k4", "v4");
    a.insert("k5", "v5");
    let cursor = a.upper_bound(Bound::Excluded(&"k3"));
    println!("upper exc {:?}", cursor.key());
     let cursor = a.upper_bound(Bound::Included(&"k3"));
    println!("upper inc {:?}", cursor.key());
    let cursor = a.lower_bound(Bound::Excluded(&"k3"));
    println!("lower exc {:?}", cursor.key());
     let cursor = a.lower_bound(Bound::Included(&"k3"));
    println!("lower inc {:?}", cursor.key());
}

@Amanieu thoughts?

[Amanieu]

I see, you are indeed correct.

---

Considering the feedback received so far, I am wondering if changing Cursors to represent a point between 2 elements rather than pointing at one element would be better:

• This avoids the need for a ghost element, since even in an empty tree there exists a point which has no previous or next element.
• lower_bound/upper_bound naturally end up pointing between 2 elements, which is less confusing.
• Moving over a value with move_prev/move_next can return an Option<(&K, &mut V)> which results in a more natural Rust API.

Let me know if this sounds promising, and I'll try and sketch out a new API with this design.

[finnbear]

Let me know if this sounds promising

It's hard to say which is better without some short before & after code examples i.e. to do X, you do Y with the old API and Z with the new API (if you wanted, the examples could also show how to accomplish the same thing in C++ or other languages). For now, it sounds plausible but not necessarily better or worse.

Anyway, after realizing the confusion, the API's were both intuitive and useful for the porting I was doing today and the only thing I'm asking for is for the docs to point out the porting hazard (alternatively, the function names could be changed to avoid matching those used in C++).

[Amanieu]

Here's an API sketch for a cursor that resides at a point between 2 elements. Elements are read by "passing over" them with a cursor.

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 next(&mut self) -> Option<(&'a K, &'a V)>;
    fn prev(&mut 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 next(&mut self) -> Option<(&K, &mut V)>;
    fn prev(&mut self) -> Option<(&K, &mut V)>;

    unsafe fn next_with_mut_key(&mut self) -> Option<(&mut K, &mut V)>;
    unsafe fn prev_with_mut_key(&mut self) -> Option<(&mut K, &mut V)>;

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

    fn peek_next_mut(&mut self) -> Option<(&K, &mut V)>;
    fn peek_prev_mut(&mut self) -> Option<(&K, &mut V)>;

    unsafe fn peek_next_with_mut_key(&mut self) -> Option<(&mut K, &mut V)>;
    unsafe fn peek_prev_with_mut_key(&mut self) -> Option<(&mut K, &mut V)>;

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

    // Inserts at current point, cursor is moved to before the inserted element.
    fn insert_after(&mut self, key: K, value: V);
    // Inserts at current point, cursor is moved to after the inserted element.
    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_next(&mut self) -> Option<(K, V)>;
    fn remove_prev(&mut self) -> Option<(K, V)>;
}

[clarfonthey]

Conceptually, I think that I do like this API more, but I still think that the combinatorical explosion of options here could be more easily avoided by integrating properly with the Entry API. Namely, if instead of having the options for the various combinations of whether you're inserting, mutating the key, etc. you could just leverage the existing Entry API with the ability to do key mutation.

Essentially, the position of the cursor between the elements is still unchanged. But rather than making the cursor this all-powerful entity, we give it equal footing with other various elements.

To accomplish this, I propose a particular sleight of hand. We retain the meaning of a "gap" as the position in the map between elements. A vacant entry points to a particular gap, and an occupied entry points to a particular element and its adjacent gaps. When mutating a key for either kind of entry, you must uphold that the entry upholds the Ord invariant for the map. So, you can nudge it around within its entry fine, but you can't leave it.

By leaving the semantics of the key specifically in the entry and requiring the entry for mutation of elements, the semantics of all the various mutable methods becomes more clear. Here's what the conceptual API would look like:

type Position = /* we'll talk about this later */;

impl<'a, K, V> Cursor<'a, K, V> { // and `CursorMut`
    // looks around the cursor
    fn peek_next(&self) -> Option<(&K, &V)>;
    fn peek_prev(&self) -> Option<(&K, &V)>;

    // move the cursor
    fn next(&mut self) -> Position;
    fn prev(&mut self) -> Position;
}
    
impl<'a, K, V> CursorMut<'a, K, V> {
    // attempts to insert at this spot in the cursor
    fn insert(self, key: K) -> Result<VacantEntry<'a, K, V>, CursorMut<'a, K, V>>;
    unsafe fn insert_unchecked(self, key: K) -> VacantEntry<'a, K, V>;

    // mutates around the cursor
    fn enter_next(&mut self) -> Option<OccupiedEntry<'_, K, V>>;
    fn enter_prev(&mut self) -> Option<OccupiedEntry<'_, K, V>>;
}

impl<'a, K, V> OccupiedEntry<'a, K, V> { // and `VacantEntry` and `Entry` too
    // requires upholding invariants mentioned
    unsafe fn key_mut(&mut self) -> &mut K;
}

impl<'a, K, V> VacantEntry<'a, K, V> {
    // if we want the ability to convert back into a cursor
    fn seek_elsewhere(self) -> (K, CursorMut<'a, K, V>);
    fn insert_and_seek_after(self, value: V) -> CursorMut<'a, K, V>;
    fn insert_and_seek_before(self, value: V) -> CursorMut<'a, K, V>;
}

Part of the reason why I think VacantEntry should have mutable access to the key is because it aligns well with the idea of entries being positions in the map associated with owned keys, which may or may not be inserted.

Note the bit I said about Position. I don't think that it's right to return a mutable value when mutating the cursor, mostly because we'd want all mutation to go through entries instead. I personally think it makes the most sense to return Option<&K> just because inspecting the key is really what you care most about, although since we're going to be providing the key anyway, we might as well also provide the value.

That's the bit I'm fuzziest on. But the rest is my basic idea on how to use entries to solve the complexity and the semantics. We don't need any weird insert_after or insert_before because we require converting a cursor into an entry, not simply borrowing it. I list some potential methods we could add to VacantEntry to allow converting back, but those weren't super thought out. My thought process is that the last step someone will probably want to take for the entry API is inserting, since you need to poke around to ensure you're satisfying invariants before you actually do the insert anyway.

[clarfonthey]

A side note on the naming of upper_bound and lower_bound conflicting with C++: why not just abandon that scheme altogether, then? We could go with something like seek_before and seek_after which would be (IMHO) unambiguously clear and is different enough from the status quo to avoid passive mistakes.

[clarfonthey]

While I'm not familiar enough with the cursor code to refactor everything to only point between elements, I did submit #112896 which adds the key_mut API to the entry types. One point I bring up in the PR which I think is worth mentioning here is that this kind of feature might deserve separation from this actual cursor API into its own tracking issue, since IMHO the cursor API and key mutation are concerns that should be separated. Would love to know what the folks following this thread think about this, and also would appreciate any additional feedback on the API I've proposed which integrates more with the entry API.

[SvizelPritula]

I'd like to also comment on the method names, if I can.

I've participated in several programming competitions in C++, where binary searches and searches on binary trees are common. Every time I've had to perform one, I had to stare at the documentation for several minutes, struggling to figure out what lower_bound and upper_bound does. (Granted, this is partially a fault of the docs.) I always wished C++ had gone with four seperate methods: find_last_less, find_first_greater_or_equal, find_last_less_or_equal and find_first_greater.

Rust's current upper_bound and lower_bound methods are significantly easier to understand and remember, but I also feel it would be easier to understand if they were called seek_last (or maybe find_last?) and seek_first.

[zacknewman]

The new commit causes an illegal instruction in debug mode but not release. I'm sure below can be reduced further, but here is an example.

[zack@laptop src]$ uname -a
Linux laptop 6.7.2-arch1-1 #1 SMP PREEMPT_DYNAMIC Fri, 26 Jan 2024 19:10:20 +0000 x86_64 GNU/Linux
[zack@laptop src]$ cargo version
cargo 1.77.0-nightly (7bb7b5395 2024-01-20)
[zack@laptop src]$ cargo run
   Compiling foo v0.1.0 (/home/zack/projects/foo)
    Finished dev [unoptimized + debuginfo] target(s) in 0.17s
     Running `/home/zack/projects/foo/target/debug/foo`
thread 'main' panicked at /rustc/635124704849eeead4e3a7bb6e663c5351571d93/library/alloc/src/collections/btree/navigate.rs:601:48:
called `Option::unwrap()` on a `None` value
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Illegal instruction (core dumped)

#![feature(btree_cursors)]
extern crate alloc;
use alloc::collections::BTreeMap;
use core::{cmp::Ordering, ops::Bound};
#[derive(Eq, PartialEq)]
struct ClosedInterval {
    min: usize,
    max: usize,
}
impl PartialOrd<Self> for ClosedInterval {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
impl Ord for ClosedInterval {
    /// The order is defined such that sets are equal to themselves.
    /// A set is greater than all proper subsets.
    /// Otherwise we simply order by `max`.
    ///
    /// For example [2, 3] = [2, 3] < [1, 3] < [1, 4] < [0, 5] < [1, 6].
    fn cmp(&self, other: &Self) -> Ordering {
        match self.min.cmp(&other.min) {
            Ordering::Less => {
                if self.max >= other.max {
                    Ordering::Greater
                } else {
                    Ordering::Less
                }
            }
            Ordering::Equal => self.max.cmp(&other.max),
            Ordering::Greater => {
                if self.max > other.max {
                    Ordering::Greater
                } else {
                    Ordering::Less
                }
            }
        }
    }
}
fn main() {
    let mut map = BTreeMap::new();
    insert(&mut map, ClosedInterval { min: 1, max: 4 });
    insert(&mut map, ClosedInterval { min: 4, max: 6 });
}
fn insert(map: &mut BTreeMap<ClosedInterval, ()>, key: ClosedInterval) {
    let mut cursor = map.lower_bound_mut(Bound::Included(&key));
    if let Some(ge) = cursor.peek_next() {
        if *ge.0 >= key {
            return;
        }
    }
    while let Some(lt) = cursor.prev() {
        if key > *lt.0 {
            cursor.remove_prev();
        } else {
            break;
        }
    }
    // Causes an illegal instruction.
    let _x = cursor.insert_after(key, ());
}

[zacknewman]

Chalk me up as one of the "weirdos" that thought the old API made sense, lol. For example the new description for lower_bound is "Returns a Cursor pointing to the first gap above the given bound". So if I have a map that includes key, then lower_bound(Bound::Included(&key)) should return a cursor "pointing to the first gap above key" (emphasis added). Wouldn't this imply that cursor.peek_prev() returns key since it's you know "above" key? The below example illustrates it's cursor.peek_next() that returns key.

#![feature(btree_cursors)]
extern crate alloc;
use alloc::collections::BTreeMap;
use core::ops::Bound;
fn main() {
    let mut map = BTreeMap::new();
    map.insert(1i32, 1i32);
    map.insert(2i32, 2i32);
    map.insert(3i32, 3i32);
    // Cursor should be "above" 2, shouldn't `peek_prev` return it?
    assert!(map
        .lower_bound(Bound::Included(&2i32))
        .peek_prev()
        .map_or(false, |tup| 1i32 == *tup.0));
    // Cursor should be "above" 2, shouldn't `peek_next` return 3?
    assert!(map
        .lower_bound(Bound::Included(&2i32))
        .peek_next()
        .map_or(false, |tup| 2i32 == *tup.0));
}

Similarly upper_bound states "Returns a Cursor pointing at the last gap below the given bound". So if I have a map that includes key, then upper_bound(Bound::Included(&key)) should return a cursor "pointing to the last gap below key" (emphasis added). Wouldn't this imply that cursor.peek_next() returns key since it's you know "below" key? The below example illustrates it's cursor.peek_prev() that returns key.

#![feature(btree_cursors)]
extern crate alloc;
use alloc::collections::BTreeMap;
use core::ops::Bound;
fn main() {
    let mut map = BTreeMap::new();
    map.insert(1i32, 1i32);
    map.insert(2i32, 2i32);
    map.insert(3i32, 3i32);
    // Cursor should be "below" 2, shouldn't `peek_prev` return 1?
    assert!(map
        .upper_bound(Bound::Included(&2i32))
        .peek_prev()
        .map_or(false, |tup| 2i32 == *tup.0));
    // Cursor should be "below" 2, shouldn't `peek_next` return it?
    assert!(map
        .upper_bound(Bound::Included(&2i32))
        .peek_next()
        .map_or(false, |tup| 3i32 == *tup.0));
}

Because of my confusion, I'm struggling refactoring some code that used the old API. I have a specialized wrapper type, SupersetMap around BTreeMap whose keys are sets. The order required for these sets is such that in addition to conforming to Ord, a set is strictly greater than all proper subsets. A consequence of this is that a superset of a set, A, exists iff the first value greater than or equal to A is a superset of A. The way insert was implemented before was the following:

/// `(key, value)` is inserted iff there doesn't already
/// exist a `K` that is a superset of `key`.
/// In the event `(key, value)` will be inserted, all `(K, V)`s
/// where the `K` is a subset of `key` are first removed before
/// inserting.
pub fn insert(&mut self, key: K, value: V) -> bool {
    // Since the only way to `insert` a `(K, V)` is via this function,
    // the following is true:
    // The smallest value greater than or equal to `key` will be a superset
    // of `key` iff there exists a superset of `key`.
    // This means that we simply have to check this one value to decide
    // if `(key, value)` needs to be inserted; furthermore, in the event `(key, value)`
    // does need to be inserted, we only have to traverse backwards until
    // the beginning of `map` or a `K` is not a subset of `key`
    // removing all `(K, V)`s where the `K` is a subset before we insert `(key, value)`.
    let mut cursor = self.map.lower_bound_mut(Bound::Included(&key));
    if let Some(ge) = cursor.key() {
        if ge.is_superset(&key) {
            return false;
        }
    }
    cursor.move_prev();
    while let Some(lt) = cursor.key() {
        if key.is_proper_superset(lt) {
            cursor.remove_current_and_move_back();
        } else {
            break;
        }
    }
    // If `key` already existed in the map, then cursor
    // would begin pointing at it. Since `Set::is_superset`
    // returns true when both values are the same, we would
    // immediately return from this function. This guarantees
    // that `key` is unique before inserting.
    // Since we only move to smaller values and each time we do
    // we remove said value (or stop), the insert of `key` will occur after
    // all smaller values and before larger values ensuring the sorted
    // order of `map` is retained.
    // Note that due to the requirements of `SetOrd`, a `K` that
    // `is_proper_superset` of another `K` is also strictly greater.
    cursor.insert_after(key, value).unwrap_or_else(
        |_| panic!("there is a bug in how keys implement Ord or Set or there is a bug in BTreeMap")
    );
    true
}

I tried re-writing this using the new API, but I don't get the correct result:

pub fn insert(&mut self, key: K, value: V) -> bool {
    let mut cursor = self.map.lower_bound_mut(Bound::Included(&key));
    // Based on the perceived behavior of `lower_bound_mut` with an included bound,
    // `peek_next` should give `key` iff it is exists; otherwise the first value strictly
    // greater than it will be returned.
    if let Some(ge) = cursor.peek_next() {
        if ge.0.is_superset(&key) {
            return false;
        }
    }
    while let Some(lt) = cursor.prev() {
        if key.is_proper_superset(lt.0) {
            cursor.remove_next();
        } else {
            break;
        }
    }
    cursor.insert_after(key, value).unwrap_or_else(
        |_| panic!("there is a bug in how keys implement Ord or Set or there is a bug in BTreeMap")
    );
    true
}

I'd appreciate any assistance.

[jonhoo]

I've been using this for some performance optimization stuff at $WORK, and have been able to reap some significant performance improvements from it that I'm excited to be able to land when this stabilizes. A few observations from that experimentation:

1. I really missed having this on BTreeSet
2. The naming of insert_before and insert_after threw me for a bit because I (incorrectly) assumed that it'd be correct to change a peek_next() + insert_after() combo into a next() + insert_before() combo. Whereas in reality the latter requires a call to .prev() and the s/after/before/ does not actually make a difference for where the item is inserted. I don't have a proposal for a better name that could have avoided that misunderstanding though. It was obvious after reading the docs, I just wish the method name had given me a clue.
3. I am observing that peek_next() + remove_next()/next() is faster than next() + remove_prev(), which was quite surprising to me. I don't know if this relates to how the CursorMut traverses internally, but I've verified it now with multiple benchmarks (admittedly internally in my codebase).
4. Implementing your own "insert at the right position" loop with this leads to a bit of awkwardness when you arrive at the last element. Specifically, the if r.is_some() inside this:

   loop {
       match cursor.next().map(|(next_key, _)| next_key.cmp(&new_key)) {
           Some(Ordering::Less) => {
               // keep walking
               continue;
           }
           Some(Ordering::Equal) => {
               // don't overwrite
               break;
           }
           r @ Some(_) | r @ None => {
               if r.is_some() {
                   cursor.prev();
               }
               cursor.insert_before(next_key, ()).unwrap();
               break;
           }
       }
   }

   (or I can match on None as a separate branch instead).
   Either way, the need for that prev() is a little odd, and also comes with a performance penalty based on my measurements at least. So I wonder whether it might make sense for .prev() to do nothing the first time it's called after .next() yields None? Or something? It's just a weird-corner case of the new by-gap cursor movement (which I otherwise like!).

[Amanieu]

The new commit causes an illegal instruction in debug mode but not release. I'm sure below can be reduced further, but here is an example.

Should be fixed by #120505.

[zacknewman]

I've been using this for some performance optimization stuff at $WORK, and have been able to reap some significant performance improvements from it that I'm excited to be able to land when this stabilizes. A few observations from that experimentation:

1. I really missed having this on BTreeSet

Same, but it is planned for this API to be added.

2. The naming of insert_before and insert_after threw me for a bit because I (incorrectly) assumed that it'd be correct to change a peek_next() + insert_after() combo into a next() + insert_before() combo. Whereas in reality the latter requires a call to .prev() and the s/after/before/ does not actually make a difference for where the item is inserted. I don't have a proposal for a better name that could have avoided that misunderstanding though. It was obvious after reading the docs, I just wish the method name had given me a clue.

It was not obvious to me.

4. Implementing your own "insert at the right position" loop with this leads to a bit of awkwardness when you arrive at the last element. Specifically, the if r.is_some() inside this:

loop {
    match cursor.next().map(|(next_key, _)| next_key.cmp(&new_key)) {
        Some(Ordering::Less) => {
            // keep walking
            continue;
        }
        Some(Ordering::Equal) => {
            // don't overwrite
            break;
        }
        r @ Some(_) | r @ None => {
            if r.is_some() {
                cursor.prev();
            }
            cursor.insert_before(next_key, ()).unwrap();
            break;
        }
    }
}

(or I can match on None as a separate branch instead).
Either way, the need for that prev() is a little odd, and also comes with a performance penalty based on my measurements at least. So I wonder whether it might make sense for .prev() to do nothing the first time it's called after .next() yields None? Or something? It's just a weird-corner case of the new by-gap cursor movement (which I otherwise like!).

Thank you for this. That answers my plea for help. Specifically insert needed to become:

pub fn insert(&mut self, key: K, value: V) -> bool {
    let mut cursor = self.map.lower_bound_mut(Bound::Included(&key));
    if let Some(ge) = cursor.peek_next() {
        if ge.0.is_superset(&key) {
            return false;
        }
    }
    loop {
        match cursor.prev() {
            None => break,
            Some(lt) => {
                if key.is_proper_superset(lt.0) {
                    cursor.remove_next();
                } else {
                    cursor.next();
                    break;
                }
            }
        }
    }
    cursor.insert_before(key, value).unwrap_or_else(|_| panic!("there is a bug in how SetOrd is implemented or a bug in BTreeMap"));
    true
}

which is not quite as nice as it was before:

pub fn insert(&mut self, key: K, value: V) -> bool {
    let mut cursor = self.map.lower_bound_mut(Bound::Included(&key));
    if let Some(ge) = cursor.key() {
        if ge.is_superset(&key) {
            return false;
        }
    }
    cursor.move_prev();
    while let Some(lt) = cursor.key() {
        if key.is_proper_superset(lt) {
            cursor.remove_current_and_move_back();
        } else {
            break;
        }
    }
    cursor.insert_after(key, value).unwrap_or_else(
        |_| panic!("there is a bug in how keys implement Ord or Set or there is a bug in BTreeMap")
    );
    true
}

[momvart]

Chalk me up as one of the "weirdos" that thought the old API made sense, lol.

I have the same problem. I was also confused by how bounds are interpreted. I think the term "above" is misleading. Finally, after quite a bit of time I came up with the following rules.

let mut a = BTreeMap::new();
a.insert(1, "a");
a.insert(2, "b");
a.insert(3, "c");
a.insert(4, "d");

// a: [1, 2, 3, 4]
// The range of Included(&2) to Unbounded:      [.. , 2 , ..]
//              [2, +∞)                             ---------
let cursor = a.lower_bound(Bound::Included(&2));
// The actual cursor:                           [1 , 2 , 3 , ..]
//                                                 ^
assert_eq!(cursor.peek_prev(), Some((&1, &"a")));
assert_eq!(cursor.peek_next(), Some((&2, &"b")));
// The range of Excluded(&2) to Unbounded:      [.. , 2 , ..]
//              (2, +∞)                                 -----
let cursor = a.lower_bound(Bound::Excluded(&2));
// The actual cursor:                           [1 , 2 , 3 , ..]
//                                                     ^
assert_eq!(cursor.peek_prev(), Some((&2, &"b")));
assert_eq!(cursor.peek_next(), Some((&3, &"c")));
// Conclusion: for lower_bound, the next node of the cursor is within the range.

// The range of Unbounded to Included(&3):      [.. , 3 , ..]
//              (-∞, 3]                         ---------
let cursor = a.upper_bound(Bound::Included(&3));
// The actual cursor:                           [.. , 2 , 3 , 4]
//                                                          ^
assert_eq!(cursor.peek_prev(), Some((&3, &"c")));
assert_eq!(cursor.peek_next(), Some((&4, &"d")));
// The range of Unbounded to Excluded(&3):      [.. , 3 , ..]
//              (-∞, 3)                         -----
let cursor = a.upper_bound(Bound::Excluded(&3));
// The actual cursor:                           [.. , 2 , 3 , 4]
//                                                      ^
assert_eq!(cursor.peek_prev(), Some((&2, &"b")));
assert_eq!(cursor.peek_next(), Some((&3, &"c")));
// Conclusion: for upper_bound, the previous node of the cursor is within the range.

[Amanieu]

Feel free to submit a PR if you think you can make the documentation better. We can further refine the wording in that PR.

[ripytide]

I had a go at improving some of the documentation in #120936

[GrigorenkoPV]

Sorry, I did not read the entire discussion. Could anyone, please, briefly summarize why the decision was made to enable key mutation via a separate CursorMutKey and not via unsafe methods on CursorMut?

[terrorfisch]

@GrigorenkoPV according to the 8ee9693 commit message:

The ability to mutate keys is also factored out into a separate
CursorMutKey type which is unsafe to create. This makes the API easier
to use since it avoids duplicated versions of each method with and
without key mutation.

Maybe there is more discussion somewhere?

I think one should explore a Key<'a, K>(&'a mut K) type which implements Deref<Target=K> and has a unsafe fn get_mut(&mut self) -> &mut K method.