pijul/sanakirja - Change W26CFMAQOXMUK4ZOJMAN4SMBXMWFQHO7HCTEVW73FQSRMJZFGJIQC

Improving safety of cursors

Created by pmeunier on February 4, 2021

W26CFMAQOXMUK4ZOJMAN4SMBXMWFQHO7HCTEVW73FQSRMJZFGJIQC

Dependencies

In channels

main

Change contents

Replacement in sanakirja-core/src/btree/put.rs at line 37 [5.3448]

B:BD[5.4538] → [6.70:118]

        cursor.pointer < cursor.first_rc_level,

[5.4538]

[5.4587]

        cursor.pointer() < cursor.first_rc_level,

Replacement in sanakirja-core/src/btree/put.rs at line 80 [5.3448]

B:BD[7.304] → [7.304:341]

∅:D[7.341] → [8.30:70]

B:BD[5.5516] → [8.30:70]

                cursor.pointer -= 1;
                if cursor.pointer > 0 {

[7.304]

[8.70]

                cursor.pop();
                if cursor.pointer() > 0 {

Replacement in sanakirja-core/src/btree/put.rs at line 86 [5.3448]

B:BD[8.215] → [8.215:279]

                        cursor.pointer < cursor.first_rc_level,

[8.215]

[8.279]

                        cursor.pointer() < cursor.first_rc_level,

Replacement in sanakirja-core/src/btree/put.rs at line 117 [5.3448]

B:BD[7.470] → [7.470:507]

∅:D[7.507] → [8.533:573]

B:BD[5.7373] → [8.533:573]

                cursor.pointer -= 1;
                if cursor.pointer > 0 {

[7.470]

[8.573]

                cursor.pop();
                if cursor.pointer() > 0 {

Replacement in sanakirja-core/src/btree/put.rs at line 123 [5.3448]

B:BD[8.746] → [8.746:810]

                        cursor.pointer < cursor.first_rc_level,

[8.746]

[8.810]

                        cursor.pointer() < cursor.first_rc_level,

Replacement in sanakirja-core/src/btree/put.rs at line 151 [5.3448]
B:BD[9.956] → [9.956:980]
```
        cursor.pointer,
```
[9.956]
[9.980]
```
        cursor.pointer(),
```
Replacement in sanakirja-core/src/btree/put.rs at line 154 [5.3448]
∅:D[7.651] → [5.7700:7748]
∅:D[9.1017] → [5.7700:7748]
∅:D[8.1107] → [5.7700:7748]
B:BD[5.7700] → [5.7700:7748]
```
    if cursor.pointer < cursor.first_rc_level {
```
[9.1017]
[5.7748]
```
    if cursor.pointer() < cursor.first_rc_level {
```
Replacement in sanakirja-core/src/btree/put.rs at line 156 [5.3448]
B:BD[5.7814] → [5.7814:7852]
```
        free[cursor.pointer] = freed;
```
[5.7814]
[5.7852]
```
        free[cursor.pointer()] = freed;
```
Replacement in sanakirja-core/src/btree/put.rs at line 161 [5.3448]
∅:D[10.92] → [7.652:705]
B:BD[5.7865] → [7.652:705]
```
        if cursor.pointer == cursor.first_rc_level {
```
[10.92]
[5.7918]
```
        if cursor.pointer() == cursor.first_rc_level {
```
Replacement in sanakirja-core/src/btree/put.rs at line 163 [5.3448]
B:BD[5.7958] → [7.706:748]
```
            free[cursor.pointer] = freed;
```
[5.7958]
[5.8113]
```
            free[cursor.pointer()] = freed;
```

Replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 107 [11.27023]

B:BD[11.30069] → [11.30069:30106]

B:BD[11.30106] → [3.192:253]

∅:D[3.253] → [11.30168:30203]

B:BD[11.30168] → [11.30168:30203]

        core::slice::from_raw_parts(
            page.data.as_ptr().add(HDR) as *const L::Offset,
            n0 as usize,
        )

[11.30069]

[11.30203]

        core::slice::from_raw_parts(page.data.as_ptr().add(HDR) as *const L::Offset, n0 as usize)

Deletion in sanakirja-core/src/btree/page_unsized/put.rs at line 112 [11.27023]
B:BD[11.30307] → [3.254:255]

Replacement in sanakirja-core/src/btree/mod.rs at line 392 [5.45735]

B:BD[4.318] → [4.318:471]

pub fn drop<T: AllocPage, K: Representable+?Sized, V: Representable+?Sized, P: BTreePage<K, V>>(txn: &mut T, db: Db_<K, V, P>) -> Result<(), T::Error> {

[4.318]

[4.471]

pub fn drop<
    T: AllocPage,
    K: Representable + ?Sized,
    V: Representable + ?Sized,
    P: BTreePage<K, V>,
>(
    txn: &mut T,
    db: Db_<K, V, P>,
) -> Result<(), T::Error> {

Replacement in sanakirja-core/src/btree/mod.rs at line 404 [5.45735]

B:BD[4.519] → [4.519:660]

fn drop_<T: AllocPage, K: Representable+?Sized, V: Representable+?Sized, P: BTreePage<K, V>>(txn: &mut T, p: Page) -> Result<(), T::Error> {

[4.519]

[4.660]

fn drop_<T: AllocPage, K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>>(
    txn: &mut T,
    p: Page,
) -> Result<(), T::Error> {

Replacement in sanakirja-core/src/btree/mod.rs at line 417 [5.45735]
B:BD[4.922] → [4.922:948]
```
            return Ok(())
```
[4.922]
[4.948]
```
            return Ok(());
```
Deletion in sanakirja-core/src/btree/del.rs at line 13 [5.52511]
B:BD[5.53046] → [5.53046:53074]
```
use core::mem::MaybeUninit;
```
Replacement in sanakirja-core/src/btree/del.rs at line 47 [5.52511]
B:BD[5.53969] → [5.53969:53998]
```
    let p0 = cursor.pointer;
```
[5.53969]
[5.53998]
```
    let p0 = cursor.pointer();
```
Replacement in sanakirja-core/src/btree/del.rs at line 54 [5.52511]
B:BD[12.16452] → [12.16452:16469]
```
        unsafe {
```
[12.16452]
[12.16469]
```
        let (delk, delv, _) = unsafe {
```

Replacement in sanakirja-core/src/btree/del.rs at line 56 [5.52511]

B:BD[12.16509] → [12.16509:16753]

            let (delk, delv, _) =
                P::unchecked_current(txn, cur.page.as_page(), cur.cursor.as_ref().unwrap());
            for o in delk.page_offsets().chain(delv.page_offsets()) {
                txn.incr_rc(o)?;
            }

[12.16509]

[12.16753]

            P::unchecked_current(txn, cur.page.as_page(), cur.cursor.as_ref().unwrap())
        };
        for o in delk.page_offsets().chain(delv.page_offsets()) {
            txn.incr_rc(o)?;

Replacement in sanakirja-core/src/btree/del.rs at line 74 [5.52511]
∅:D[12.17134] → [5.55653:55678]
B:BD[5.55653] → [5.55653:55678]
∅:D[13.31882] → [5.55678:55709]
B:BD[5.55678] → [5.55678:55709]
```
    cursor.pointer -= 1;
    while cursor.pointer > 0 {
```
[12.17134]
[12.17136]
```
    cursor.pop();
    while cursor.pointer() > 0 {
```
Replacement in sanakirja-core/src/btree/del.rs at line 96 [5.52511]
∅:D[14.31108] → [5.59562:59591]
∅:D[2.2591] → [5.59562:59591]
∅:D[12.17869] → [5.59562:59591]
B:BD[5.59562] → [5.59562:59591]
```
        cursor.pointer -= 1;
```
[2.2591]
[5.59591]
```
        cursor.pop()
```

Replacement in sanakirja-core/src/btree/del.rs at line 140 [5.52511]

B:BD[14.31480] → [14.31480:31524]

        cur.page, cursor.pointer, left_page

[14.31480]

[14.31524]

        cur.page,
        cursor.pointer(),
        left_page

Deletion in sanakirja-core/src/btree/del.rs at line 145 [5.52511]
B:BD[5.61472] → [5.61472:61501]
```
        cursor.pointer += 1;
```
Replacement in sanakirja-core/src/btree/del.rs at line 148 [5.52511]
∅:D[13.32574] → [5.61639:61708]
B:BD[5.61639] → [5.61639:61708]
```
        cursor.stack[cursor.pointer] = MaybeUninit::new(PageCursor {
```
[13.32574]
[5.61708]
```
        cursor.push(PageCursor {
```

Replacement in sanakirja-core/src/btree/del.rs at line 153 [5.52511]

B:BD[5.61776] → [15.8628:8691]

    debug!("find_min: cursor.pointer = {:?}", cursor.pointer);

[5.61776]

    debug!("find_min: cursor.pointer = {:?}", cursor.pointer());

Replacement in sanakirja-core/src/btree/del.rs at line 168 [5.52511]

∅:D[2.2827] → [12.18598:18674]

B:BD[12.18598] → [12.18598:18674]

    let curs0 = unsafe { &mut *cursor.stack[cursor.pointer].as_mut_ptr() };

[2.2827]

[14.31983]

    let is_rc = cursor.pointer() >= cursor.first_rc_level;
    let del_at_internal = p0 < cursor.pointer();
    let ref mut curs0 = cursor.last();

Replacement in sanakirja-core/src/btree/del.rs at line 172 [5.52511]
B:BD[14.32220] → [14.32220:32269]
```
    if cursor.pointer >= cursor.first_rc_level {
```
[14.32069]
[14.32269]
```
    if is_rc {
```
Replacement in sanakirja-core/src/btree/del.rs at line 185 [5.52511]
∅:D[12.18853] → [14.32790:32819]
B:BD[14.32790] → [14.32790:32819]
```
    if p0 < cursor.pointer {
```
[12.18853]
[14.32819]
```
    if del_at_internal {
```

Replacement in sanakirja-core/src/btree/del.rs at line 187 [5.52511]

B:BD[14.32866] → [14.32866:32883]

B:BD[14.32883] → [12.18854:18936]

∅:D[12.18936] → [14.32960:33148]

B:BD[14.32960] → [14.32960:33148]

        unsafe {
            let (k, v, _) = P::unchecked_current(txn, curs0.page.as_page(), &c0);
            if cursor.pointer >= cursor.first_rc_level {
                for o in (&*k).page_offsets().chain((&*v).page_offsets()) {
                    txn.incr_rc(o)?;
                }

[14.32866]

[14.33148]

        let (k, v, _) = unsafe { P::unchecked_current(txn, curs0.page.as_page(), &c0) };
        if is_rc {
            for o in (&*k).page_offsets().chain((&*v).page_offsets()) {
                txn.incr_rc(o)?;

Deletion in sanakirja-core/src/btree/del.rs at line 192 [5.52511]
B:BD[14.33162] → [2.2828:2889]
```
            deleted = Some(P::save_deleted_leaf_entry(k, v))
```
Insertion in sanakirja-core/src/btree/del.rs at line 193 [5.52511]
[14.33306]
[14.33306]
```
        deleted = Some(P::save_deleted_leaf_entry(k, v))
```

Replacement in sanakirja-core/src/btree/del.rs at line 198 [5.52511]

B:BD[14.33374] → [14.33374:33435]

            mutable: cursor.pointer < cursor.first_rc_level,

[14.33374]

[14.33435]

            mutable: cursor.pointer() < cursor.first_rc_level,

Replacement in sanakirja-core/src/btree/del.rs at line 224 [5.52511]
∅:D[12.19536] → [14.33726:33754]
B:BD[5.62136] → [14.33726:33754]
```
    let p = cursor.pointer;
```
[12.19536]
[14.33754]
```
    let p = cursor.pointer();
```
Replacement in sanakirja-core/src/btree/del.rs at line 278 [5.52511]
∅:D[12.20246] → [14.34379:34437]
B:BD[14.34379] → [14.34379:34437]
```
    let mutable = cursor.pointer < cursor.first_rc_level;
```
[12.20246]
[14.34437]
```
    let mutable = cursor.pointer() < cursor.first_rc_level;
```
Replacement in sanakirja-core/src/btree/del.rs at line 319 [5.52511]
B:BD[14.35718] → [14.35718:35756]
```
            if cursor.pointer == p0 {
```
[14.35718]
[2.3165]
```
            if cursor.pointer() == p0 {
```
Replacement in sanakirja-core/src/btree/del.rs at line 345 [5.52511]
B:BD[14.36543] → [14.36543:36581]
```
            if cursor.pointer == p0 {
```
[14.36543]
[14.36581]
```
            if cursor.pointer() == p0 {
```

Replacement in sanakirja-core/src/btree/del.rs at line 374 [5.52511]

B:BD[12.20503] → [9.10411:10492]

            if cursor.pointer + 1 >= cursor.first_rc_level && !split_key_is_k0 {

[12.20503]

[14.37710]

            if cursor.pointer() + 1 >= cursor.first_rc_level && !split_key_is_k0 {

Replacement in sanakirja-core/src/btree/del.rs at line 382 [5.52511]

B:BD[14.37905] → [14.37905:37991]

    if cursor.pointer < cursor.first_rc_level {
        free[cursor.pointer] = freed;

[14.37905]

[5.62825]

    if cursor.pointer() < cursor.first_rc_level {
        free[cursor.pointer()] = freed;

Replacement in sanakirja-core/src/btree/del.rs at line 385 [5.52511]

B:BD[5.62831] → [12.20583:20653]

    modify_rc(txn, &last_op, cursor.pointer, cursor.first_rc_level)?;

[5.62831]

[14.38150]

    modify_rc(txn, &last_op, cursor.pointer(), cursor.first_rc_level)?;

Replacement in sanakirja-core/src/btree/cursor.rs at line 41 [5.63682]

∅:D[11.51806] → [12.24668:24741]

∅:D[9.11010] → [12.24668:24741]

B:BD[12.24668] → [12.24668:24741]

    pub stack: [core::mem::MaybeUninit<PageCursor<K, V, P>>; N_CURSORS],

[9.11010]

[5.65137]

    // Invariant: all items up to (and including) stack[pointer],
    // except possibly 0, are initialised.
    stack: [core::mem::MaybeUninit<PageCursor<K, V, P>>; N_CURSORS],

Replacement in sanakirja-core/src/btree/cursor.rs at line 45 [5.63682]

B:BD[5.65168] → [5.65168:65192]

    pub pointer: usize,

[5.65168]

[5.65192]

    pointer: usize,
}
impl<K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>>
    core::ops::Index<usize> for Cursor<K, V, P>
{
    type Output = PageCursor<K, V, P>;
    fn index(&self, i: usize) -> &PageCursor<K, V, P> {
        assert!(i <= self.pointer);
        unsafe { &*self.stack.index(i).as_ptr() }
    }
}
impl<K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>>
    core::ops::IndexMut<usize> for Cursor<K, V, P>
{
    fn index_mut(&mut self, i: usize) -> &mut PageCursor<K, V, P> {
        assert!(i <= self.pointer);
        unsafe { &mut *self.stack.index_mut(i).as_mut_ptr() }
    }

Insertion in sanakirja-core/src/btree/cursor.rs at line 72 [5.63682]

[5.65498]

            cursor: None,
        });
        stack[0] = MaybeUninit::new(PageCursor {
            page: CowPage::null(),

Insertion in sanakirja-core/src/btree/cursor.rs at line 83 [5.63682]

[5.65645]

    }
    pub fn push(&mut self, p: PageCursor<K, V, P>) {
        self.pointer += 1;
        self.stack[self.pointer] = MaybeUninit::new(p)

Insertion in sanakirja-core/src/btree/cursor.rs at line 89 [5.63682]

[5.65651]


    pub fn last(&mut self) -> &mut PageCursor<K, V, P> {
        unsafe { &mut *self.stack[self.pointer].as_mut_ptr() }
    }

Insertion in sanakirja-core/src/btree/cursor.rs at line 100 [5.63682]

[5.65883]

[12.25008]

    pub fn pointer(&self) -> usize {
        self.pointer
    }
    pub fn pop(&mut self) {
        self.pointer -= 1
    }

Improving safety of cursors

Dependencies

In channels

Change contents

Replacement in sanakirja-core/src/btree/put.rs at line 37 [5.3448]

Replacement in sanakirja-core/src/btree/put.rs at line 80 [5.3448]

Replacement in sanakirja-core/src/btree/put.rs at line 86 [5.3448]

Replacement in sanakirja-core/src/btree/put.rs at line 117 [5.3448]

Replacement in sanakirja-core/src/btree/put.rs at line 123 [5.3448]

Replacement in sanakirja-core/src/btree/put.rs at line 151 [5.3448]

Replacement in sanakirja-core/src/btree/put.rs at line 154 [5.3448]

Replacement in sanakirja-core/src/btree/put.rs at line 156 [5.3448]

Replacement in sanakirja-core/src/btree/put.rs at line 161 [5.3448]

Replacement in sanakirja-core/src/btree/put.rs at line 163 [5.3448]

Replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 107 [11.27023]

Deletion in sanakirja-core/src/btree/page_unsized/put.rs at line 112 [11.27023]

Replacement in sanakirja-core/src/btree/mod.rs at line 392 [5.45735]

Replacement in sanakirja-core/src/btree/mod.rs at line 404 [5.45735]

Replacement in sanakirja-core/src/btree/mod.rs at line 417 [5.45735]

Deletion in sanakirja-core/src/btree/del.rs at line 13 [5.52511]

Replacement in sanakirja-core/src/btree/del.rs at line 47 [5.52511]

Replacement in sanakirja-core/src/btree/del.rs at line 54 [5.52511]

Replacement in sanakirja-core/src/btree/del.rs at line 56 [5.52511]

Replacement in sanakirja-core/src/btree/del.rs at line 74 [5.52511]

Replacement in sanakirja-core/src/btree/del.rs at line 96 [5.52511]

Replacement in sanakirja-core/src/btree/del.rs at line 140 [5.52511]

Deletion in sanakirja-core/src/btree/del.rs at line 145 [5.52511]

Replacement in sanakirja-core/src/btree/del.rs at line 148 [5.52511]

Replacement in sanakirja-core/src/btree/del.rs at line 153 [5.52511]

Replacement in sanakirja-core/src/btree/del.rs at line 168 [5.52511]

Replacement in sanakirja-core/src/btree/del.rs at line 172 [5.52511]

Replacement in sanakirja-core/src/btree/del.rs at line 185 [5.52511]

Replacement in sanakirja-core/src/btree/del.rs at line 187 [5.52511]

Deletion in sanakirja-core/src/btree/del.rs at line 192 [5.52511]

Insertion in sanakirja-core/src/btree/del.rs at line 193 [5.52511]