ForEach stops short

[lukechampine]

(same issue as #429, but now reproducible.)

bucket.ForEach sometimes fails to iterate over the entire bucket if an element has been deleted during the same transaction. Technically, this is a Cursor issue, not a Bucket issue; Cursor.first is placing the Cursor at a bad node, causing Cursor.keyValue to return nil and ForEach to terminate early. Code in question:

func (c *Cursor) first() {
    for {
        var ref = &c.stack[len(c.stack)-1]
        if ref.isLeaf() {
            break
        }
        var pgid pgid
        if ref.node != nil {
            pgid = ref.node.inodes[ref.index].pgid // <- problem occurs here
        } else {
            pgid = ref.page.branchPageElement(uint16(ref.index)).pgid
        }
        p, n := c.bucket.pageNode(pgid)
        c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
        // ^this elemRef now has a count of 0
    }
}

It seems like ref.node.inodes can contain an entry referencing a deleted node. These entries are removed by node.rebalance, but rebalancing only happens at the end of a transaction. I tried deleting the entry manually (immediately after node.del), but this caused panics elsewhere. Alternatively, instead of deleting from inodes, we could skip over the bad index. This is the approach used on our fork: https://github.com/NebulousLabs/bolt/pull/1/files

After much trial and error I was able to create a program+database that reproduces this issue. Strangely, when I copy the contents of the bucket to a fresh DB, the issue disappears. I suspect the DB may have some strange properties that are contributing to the problem.

DB: http://pixeldra.in/u/RcC9Kv
Program: http://pixeldra.in/u/0LYHeh

[rhcarvalho]

@benbjohnson this issue can be closed. It was mentioned in the PR above, but GitHub didn't understand "Fixes A, B" 😎