fix(lib/trie): Implement `TrieIterator` for `InMemoryTrie`

[EclesioMeloJunior]

Changes

• Remove the usage of sortedKeys
• While under a transaction compare the next key acquire from the state with the one acquire from the upserts from the current transaction, the lower one is returned

Tests

go test -run ^TestNextKeysUsingDifferentTransactions$ github.com/ChainSafe/gossamer/lib/runtime/storage
go test -run ^TestNextKeysWhitinSameTransaction$ github.com/ChainSafe/gossamer/lib/runtime/storage

Issues

• Related to https://github.com/ChainSafe/gossamer/issues/4057

[dimartiro]

@EclesioMeloJunior I think there could be an issue with this approach.

Let's say we have a trie with these keys:

"acc:abc123:ddd"
"acc:abc123:eee"

If we start a transaction and delete the key acc:abc123:ddd, if we ask for the nextKey of acc:abc123 during that transaction, this will return acc:abc123:ddd even if it is deleted, because we are using the underlying trie to get the nextKey and we are not ignoring the deleted keys during this transaction.

In my opinion, this could be challenging to solve without knowing the full keys list or without adding a function in the trie to ignore keys while calculating the nextKey, which, I think, is not the responsibility of the trie.

I suggest temporarily keeping the sortedKeys approach for the main trie and transactions, because this will be solved in the middle term when we start using lazy loading and the blockchainDB overlays will use an inMemoryDB that will allow us to 'simulate' a similar behavior we had when we were using the trie snapshots.

Here is a test you can use to debug what I'm saying:

func TestNextKeysAfterDeletingKeys(t *testing.T) {
    ts := NewTrieState(inmemory_trie.NewEmptyTrie())

    keys := [][]byte{
        []byte("acc:abc123:ddd"),
        []byte("acc:abc123:eee"),
        []byte("acc:abc123:fff"),
    }

    for _, key := range keys {
        require.NoError(t, ts.Put(key, []byte("0x10")))
    }

    ts.StartTransaction()
    require.NoError(t, ts.Delete([]byte("acc:abc123:ddd")))

    prefix := []byte("acc:abc123")
    nextKey := ts.NextKey(prefix)

    require.NotNil(t, nextKey)
    require.Equal(t, []byte("acc:abc123:eee"), nextKey)

    ts.CommitTransaction()
}