prefixStore does not handle iteration correctly for nil endpoints

[silasdavis]

The KVStore interface defines iteration as over half-open interval of keys with inclusive start key and exclusive start key. Except when a nil end point is given which means iterate the entire range inclusively. When your domain is a prefix then these facts interact with each other to make reverse iteration a little more complex. In this case in order to capture all possible keys you need to pass the underlying iterator a range that will capture keys that do not start with the prefix.

In Tendermint there is an implementation of DB, prefixDB that gets this right, see: https://github.com/tendermint/tendermint/blob/master/libs/db/prefix_db.go#L129-L161

Three parts of the prefixStore implementation are wrong currently.

1. The prefixIterator Domain function: https://github.com/cosmos/cosmos-sdk/blob/develop/store/prefixstore.go#L94-L99. You need to use the end points passed to prefixStore.Iterator you cannot just strip the prefix from the underlying Iterator's domain.

2. The ReverseIterator function is unfortunately not symmetrical WRT the Iterator function - it needs to potential skip the first element and also to become invalid if it iterates past the end of the prefix. The current endpoint is also wrong being greater than prefix rather than less than.

3. ReverseIterator also has what looks like just a typo: https://github.com/cosmos/cosmos-sdk/blob/develop/store/prefixstore.go#L83 - I'm sure the author meant to prefix start

To illustrate 2, suppose we have a prefix 1101, then consider the descending sequence for a reverse iterator:

1110 <- strict upper bound on prefix, but does not start with prefix so not in range
1101111 <- greater than prefix, but still starts with prefix so  in range, this is an open interval to 1110
1101 <- prefix, in range (empty key), but if we use as endpoint will be excluded from iterator (because exclusive end point semantics)
110011111 <- not in range but open interval to 1101
1100 <- endpoint that makes most sense to pass to underlying iterator (we could use 1100111 or 11001111111 but the options never end... so may as well stick with same length)

So the endpoints we need to pass to underlying iterator's ReverseIterator function are 1110 (inclusive) and 1100 (exclusive) in order to be sure to catch everything in the range, but it means we may need to skip first key if 1110 is stored and as soon as we iterate past 1100 we need to invalidate the iterator.

I was hoping I could simplify the logic of prefixDB but didn't find a way to do so meaningfully. Unfortunately prefixDB does a defensive, but unnecessary copy on every key so I have implemented a version that doesn't: https://github.com/silasdavis/burrow/blob/state/storage/prefix_db.go#L67-L93. I have made some stylistic tweaks but it is otherwise the same. I also extracted the logic around the prefix into a Prefix type: https://github.com/silasdavis/burrow/blob/state/storage/prefix.go.

I feel like since there are shared semantics between DB (necessarily, really) and KVStore there ought to be shared code - seeing as this stuff is a little bit finicky. I also have a PR into IAVL that introduces a KeyFormat type: https://github.com/tendermint/iavl/pull/107/files. It seems to me that we could extract the logic for iterating, formatting, and scanning over keys with a possible prefix into a single type that could be shared amonst these implementations. Thought KeyFormat and Prefix might work better as separate concerns.

[mossid]

Thanks for pointing out this.

cpIncr preserves the length of the original slice via padding 0x00. However sdk.PrefixEndBytes doesn't. So if we pass the slice []byte{0xAA, 0xFF, 0xFF} to the both functions, they will return []byte{0xAB, 0x00, 0x00} and []byte{0xAB} respectively.

If we use cpIncr for adjusting the start position, I think it is possible that there are more than one elements we have to skip. For example, let's say the prefix is []byte{0xAA, 0xFF, 0xFF} and we want to reverseiterate over the prefixstore.

cpIncr(prefix) == []byte{0xAB, 0x00, 0x00} == pstart
cpDecr(prefix) == []byte{0xAA, 0xFF, 0xFE} == pend

Possible keys within range(decending order):
[0xAB, 0x00, 0x00]
[0xAB, 0x78]
[0xAB]
[0xAA, 0xFF, 0xFF, 0x11]
[0xAA, 0xFF, 0xFF]
[0xAA, 0xFF, 0xFE, 0x56, 0x78]
[0xAA, 0xFF, 0xFE, 0x56]

Keys those we originally wanted to get:
[0xAA, 0xFF, 0xFF, 0x11]
[0xAA, 0xFF, 0xFF]

The keys those start with [0xAA, 0xFF, 0xFE] are handled correctly on prefixIterator.Next(), but starting with [0xAB] are not because skipOne skips only once.

We can either skip multiple elements until the element starts with the prefix, or modify cpIncr to trim 0x00s, just like as sdk.PrefixEndBytes

I'll make a PR that addresses this issue for SDK but it looks good to check on PrefixDB too.

[silasdavis]

@mossid looks like you are right about the prefixDB implementation, although your example has a slight mistake in it.

The correct thing to do is to take [0xAB] which is a tight lower bound on the set of bytes with prefix [0xAB, 0xFF, 0xFF]. My implementation get this right (though I did not notice cpIncr did not): https://github.com/silasdavis/burrow/blob/state/storage/prefix.go#L24-L50. I've also extracted the iterator logic so it could be shared. Feel free to use this code if you like - it is Apache 2.0.

In your example 0xAB78 > 0xAB0000 lexicographically so comes earlier:

Possible keys within range (descending order):
[0xAB, 0x78]
[0xAB, 0x00, 0x00]
[0xAB, 0x00] <- this is possible with cpIncr
[0xAB]
[0xAA, 0xFF, 0xFF, 0x11]

[alexanderbez]

@mossid please change the label if you believe this should be addressed before game of steaks.