Repository: rust-lang/rust
File: library/alloc/src/collections/btree/map.rs (Rust)

Code before:
            unsafe { ptr::write(k_mut, k) };
            unsafe { ptr::write(v_mut, v) };

            remove_next_on_drop.forget_next = false;
        }
    }

    /// Forgets the next element's key and value from the `BTreeMap`.
    ///
    /// The element's key and value does not run its destructor. The cursor position is
    /// unchanged (before the forgotten element).
    fn forget_next_key_and_value(&mut self) {
        let current = match self.current.take() {
            Some(current) => current,
            None => return,
        };

        if current.reborrow().next_kv().is_err() {
            self.current = Some(current);
            return;
        }

        let mut emptied_internal_root = false;
        if let Ok(next_kv) = current.next_kv() {
            let ((_, val), pos) =
                next_kv.remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone());
            // Don't run destructor on next element's value
            mem::forget(val);
            self.current = Some(pos);
            *self.length -= 1;
            if emptied_internal_root {
                // SAFETY: This is safe since current does not point within the now
                // empty root node.
                let root = unsafe { self.root.reborrow().as_mut().unwrap() };
                root.pop_internal_level(self.alloc.clone());
            }
        }
    }

    /// Inserts a new key-value pair into the map in the gap that the
    /// cursor is currently pointing to.
    ///
    /// After the insertion the cursor will be pointing at the gap before the
    /// newly inserted element.
    ///
    /// # Safety
    ///
    /// You must ensure that the `BTreeMap` invariants are maintained.
    /// Specifically:
    ///
    /// * The key of the newly inserted element must be unique in the tree.

Review comment (suggestion):
`remove_kv_tracking` may panic and drop the key and value, tbh this is very complicated and makes me think it could be better for `with_next()` instead of calling `forget_next[_key_and]_value`, to transmute the cursor reference type from `&mut CursorMut<K, V>` to `&mut CursorMut<K, ManuallyDrop<V>>` and then just call `remove_next`. that said, idk if that would be sound, asking on Zulip: [#t-libs > could we use transmute tricks in the impl of BTreeMap? @ 💬](https://rust-lang.zulipchat.com/#narrow/channel/219381-t-libs/topic/could.20we.20use.20transmute.20tricks.20in.20the.20impl.20of.20BTreeMap.3F/near/573194674)

Code after:
    /// After the insertion the cursor will be pointing at the gap after the
    /// newly inserted element.
    ///
    /// # Safety
    ///
    /// You must ensure that the `BTreeMap` invariants are maintained.
    /// Specifically:
    ///
    /// * The key of the newly inserted element must be unique in the tree.
    /// * All keys in the tree must remain in sorted order.
    #[unstable(feature = "btree_cursors", issue = "107540")]
    pub unsafe fn insert_before_unchecked(&mut self, key: K, value: V) {
        let edge = match self.current.take() {
            None => {
                // SAFETY: We have no other reference to the tree.
                match unsafe { self.root.reborrow() } {
                    root @ None => {
                        // Tree is empty, allocate a new root.
                        let mut node = NodeRef::new_leaf(self.alloc.clone());
                        // SAFETY: We don't touch the root while the handle is alive.
                        let handle = unsafe { node.borrow_mut().push_with_handle(key, value) };
                        *root = Some(node.forget_type());
                        *self.length += 1;
                        self.current = Some(handle.right_edge());
                        return;
                    }
                    Some(root) => root.borrow_mut().last_leaf_edge(),
                }
            }
            Some(current) => current,
        };

        let handle = edge.insert_recursing(key, value, self.alloc.clone(), |ins| {
            drop(ins.left);
            // SAFETY: The handle to the newly inserted value is always on a
            // leaf node, so adding a new root node doesn't invalidate it.
            let root = unsafe { self.root.reborrow().as_mut().unwrap() };
            root.push_internal_level(self.alloc.clone()).push(ins.kv.0, ins.kv.1, ins.right)
        });
        self.current = Some(handle.right_edge());
        *self.length += 1;
    }

    /// Inserts a new key-value pair into the map in the gap that the
    /// cursor is currently pointing to.
    ///
    /// After the insertion the cursor will be pointing at the gap before the
    /// newly inserted element.
    ///
    /// If the inserted key is not greater than the key before the cursor
    /// (if any), or if it not less than the key after the cursor (if any),