Invalid Reverse Iterator Seek Test

[VannaDii]

It seems the test for iterator#seek() on reverse iterator is invalid. This test uses make which batches three items with keys one, two, three, then creates an iterator with { reverse: true, limit: 1 }, then attempts to seek to key three! expecting to find it and for the key to be three.

Possibly invalid assumptions:

1. Items are stored in the order they are received: { reverse: true, limit: 1 }
2. Key seeking is done by subset matching: three! != three but does start with three

Possible changes:

1. Remove { limit: 1 } to seek all items in reverse and tolerate the subset match
2. Correct the seek('three!') call to be seek('three')

If both changes are made then this test passes. Am I missing some reason why this is a valid test?

[vweevers]

Following LevelDB logic, forwards seeks land on the target, or the key after it. In reverse mode, we reversed that logic: a backwards seek lands on the target or the key before it.

[VannaDii]

@vweevers that makes sense, however, it also makes assumption 1 - items are stored in the order received. It seems problematic to impose this storage rule on the underlying persistence layer, no?

Also, in this case, the key provided to seek doesn't exist at all, it was never put.

[vweevers]

Also, in this case, the key provided to seek doesn't exist at all, it was never put.

I'll rephrase: seeks land on the target or - if that key does not exist - the key after/before it.

Items are sorted lexicographically. In this case, the inserted keys one, two, three sort as one, three, two. If you imagine the key three! in between them, they sort as one, three, three!, two. Seeking backwards to three! would land on three! if that key existed, but it doesn't, so it lands on three.

[VannaDii]

Ahhh, I see now. Thank you for that explanation. This might be a good explanation to add to the iterator documentation? I'll close this issue. Sorry for the trouble.

[vweevers]

No trouble at all.

[VannaDii]

Wait, but doesn't limit: 1 mean that only two would be retrieved in reverse landing the seek on undefined?

[vweevers]

The limit applies to the total number of items retrieved, not to what's on disk. It does a seek first, then from it where landed, retrieves items until the limit is reached.