Allow Index Keys

[rigelrozanski]

right now iavl panics if there is a no value provided:
https://github.com/tendermint/iavl/blob/master/tree.go#L90

we do however want to be able to store indexes which should be holding no value, right now we can store a single 0 byte, but I think it would be useful to allow either storing nil, or building in some explicit index function

[liamsi]

I think of the IAVL tree basically as a map. There is no obvious reason for me to not allow for nil values but from an application point of view it sounds like misusing the map like an array (if that makes sense). Can you elaborate a little on the use-case?

[rigelrozanski]

Sometimes we want to take advantage of the IAVL sorting to gain the subset of records - for instance in staking we want to hold all the delegations, (key = {delegationAddr, validatorAddr}) and want to be able to access both all the delegations from one delegator, and all the delegations to one validator, we've been doing this by holding an index record with the key {validatorAddr, delegationAddr} in order to sort by validator - this second key however doesn't need to store the record, because once you know of it's existence you can go lookup the first key-value pair. Thus we don't need it to actually have a value, only the key - does this make sense?

[alexanderbez]

Essentially, it's kind of acting like a set right? I don't see anything wrong with storing nil values or an empty byte slice. Just gotta be careful it doesn't break any existing internal API's (e.g. operating a nil value).

[liamsi]

Yeah, I was worried that we'd need to be very careful with handling this case. From looking into how nodes are persisted, this doesn't seem to hold. Hence it should be fine.

[rigelrozanski]

Thinking about this a bit more, there is one kind of weird situation: When you use Get to find a key, if the object is not there we return a value of Nil - so to distinguish this case we would need to also return a found variable which kind of stinks... So it sounds like the better option would be to create special functions which are exclusively used for Indexes which don't have Values?

currently to store an index I'm using an empty byte array ([]byte{}) instead of Nil seems to do the trick

[liamsi]

Hmm, I knew there must be sth weird about how to implement this :-D

So it sounds like the better option would be to create special functions which are exclusively used for Indexes which don't have Values?

I think that is not really optimal, too.

currently to store an index I'm using an empty byte array ([]byte{}) instead of Nil seems to do the trick

This, or somehow else encoding / saying "nope, no value", without introducing another var or function, would be better.

[liamsi]

What if we made your workaround the default behaviour? If you set(key, nil) you will get(key)=[]byte{}? Then, if you try to "get(non-exisiting-key)" you receive nil?
Hmm, then we can't differentiate the case where (for whatever reason) someone uses set(key, []byte{}).

[alexanderbez]

Yeah I agree @liamsi. I'm seeming to be more inclined to not store nil, but []byte{} instead. I see two options of Get(key):

1. You get nil back which means the key does not exist (meaning we'd store []byte{} for keys with nil values).
2. Change the API to also return an error to signify that indeed the key does not exist or it does exist, but just has a nil value.

[rigelrozanski]

If anything we'd wouldn't want an error but a bool found - but this introduces a whole bunch of extra crap everywhere - How about this

• Allow passing in a nil value, which in the store will get actually stored as a nil value (which is the desired functionality we're looking for)
• When Getting from a store, if the record exists but has a value of nil an pass back []byte{} to indicate that is does exist but doesn't contain any information
• Just leave it indistinguishable if you actually save a []byte to the record... when does this actually matter even? Can't think of a time

[alexanderbez]

Ok, so a client will never get nil back from a Get(key) as long as the key exists. It'll only get nil back when the key does not actually exist. I'm ok with that.

[rigelrozanski]

correct

[rigelrozanski]

Additionally we could use []byte(nil) which is distinct from []byte{}

[silasdavis]

Perhaps this is out-of-date, but you can Set(key, []byte{}) which I think acts as the sentinel you need. I don't think we should implicitly convert []byte{} to nil. The current behaviour seems the most elegant in context.

[erikgrinaker]

The current behavior seems to be in line with this discussion: []byte{} values are accepted, but nil is rejected since it is used to signal absence in Get(). This is consistent with recent cleanups in tm-db.