Cursor inconsistent when mixing cursor.Delete() with Put() in same transaction

[thatguystone]

This one is probably best described with a (failing) test case:

func TestCursor_DeleteInAddTransaction(t *testing.T) {
    db := NewTestDB()
    defer db.Close()

    const count = 10

    db.Update(func(tx *bolt.Tx) error {
        b, _ := tx.CreateBucket([]byte("widgets"))
        for i := 0; i < count; i++ {
            k := make([]byte, 8)
            binary.BigEndian.PutUint64(k, uint64(i))
            b.Put(k, make([]byte, 100))
        }

        c := b.Cursor()
        for key, _ := c.First(); key != nil; key, _ = c.Next() {
            if err := c.Delete(); err != nil {
                return err
            }
        }

        return nil
    })

    db.View(func(tx *bolt.Tx) error {
        b := tx.Bucket([]byte("widgets"))
        equals(t, 0, b.Stats().KeyN)
        return nil
    })
}

It should delete all of the inserted keys, but instead, the following keys remain: 1, 3, 5, 7, 9.

This also seems to be the case when there's a pre-existing set of keys and a single key is put (for example):

func TestCursor_DeleteMultipleTransactions(t *testing.T) {
    db := NewTestDB()
    defer db.Close()

    const count = 10

    db.Update(func(tx *bolt.Tx) error {
        b, _ := tx.CreateBucket([]byte("widgets"))
        for i := 0; i < count; i++ {
            k := make([]byte, 8)
            binary.BigEndian.PutUint64(k, uint64(i))
            b.Put(k, make([]byte, 100))
        }
        return nil
    })

    db.Update(func(tx *bolt.Tx) error {
        b := tx.Bucket([]byte("widgets"))

        k := make([]byte, 8)
        binary.BigEndian.PutUint64(k, uint64(0))
        b.Put(k, make([]byte, 100))

        c := b.Cursor()
        for key, _ := c.First(); key != nil; key, _ = c.Next() {
            if err := c.Delete(); err != nil {
                return err
            }
        }

        return nil
    })

    db.View(func(tx *bolt.Tx) error {
        b := tx.Bucket([]byte("widgets"))
        c := b.Cursor()
        for key, _ := c.First(); key != nil; key, _ = c.Next() {
            u := binary.BigEndian.Uint64(key)
            fmt.Println(u)
        }

        equals(t, 0, b.Stats().KeyN)
        return nil
    })
}

[flowchartsman]

My first thought when looking at this was the bit in the docs about cursors:

Changing data while traversing with a cursor may cause it to be invalidated
and return unexpected keys and/or values. You must reposition your cursor
after mutating data.

So, I changed c.Next() in your example to c.First(), and it passed:

        c := b.Cursor()
        for key, _ := c.First(); key != nil; key, _ = c.First() {
            if err := c.Delete(); err != nil {
                return err
            }
        }

But then, I split it into two updates and kept the c.Next(), and this also passed:

    db.Update(func(tx *bolt.Tx) error {
        b, _ := tx.CreateBucket([]byte("widgets"))
        for i := 0; i < count; i++ {
            k := make([]byte, 8)
            binary.BigEndian.PutUint64(k, uint64(i))
            b.Put(k, make([]byte, 100))
        }
        return nil
    })

    db.Update(func(tx *bolt.Tx) error {
        b := tx.Bucket([]byte("widgets"))
        c := b.Cursor()
        for key, _ := c.First(); key != nil; key, _ = c.Next() {
            if err := c.Delete(); err != nil {
                return err
            }
        }

        return nil
    })

Now I am somewhat confused. Curious to learn what's going on.

[benbjohnson]

@thatguystone thanks for submitting the issue. I've been out of town and couldn't respond. @alaska is correct with his reference to the docs. The issue is that the Tx doesn't track its cursors. When you update pages via Put() or Delete(), new in-memory pages get built but the cursor is still pointing to the old mmap'd pages.

When you call Cursor.First(), the cursor traverses from the bucket's current root page so that's why calling that will reset the cursor. Calling Cursor.Next() will move forward based on the page the cursor is currently pointing to (which may be an old mmap page).

The alternative is to have the Tx track and update all it's cursors whenever a page is changed but that causes huge overhead. There's a Cursor.Delete() method that you can use instead to properly maintain the current page.

[benbjohnson]

Oh, sorry, I misread the code. I didn't realize you were already using Cursor.Delete().