Re: [w3c/IndexedDB] boolean should be a valid key (#76)

I would like to see Boolean become a valid key type in IndexedDB. I have some concerns about where Boolean might appear relative to other key types in the key ordering. I am writing this against the [IndexedDB spec dated 8/1/15](https://www.w3.org/TR/IndexedDB/) but am aware of the [IndexedDB 2 draft](https://w3c.github.io/IndexedDB/).
 
The current IndexedDB key ordering is Number < Date < String < Array. The Booleans could be inserted in one of five places in the existing order. My notes on each option follow.
 
#### 1. Boolean < Number < Date < String < Array
 
Currently, the least value that can be used as a key is -Infinity. If Booleans came first instead of Numbers, the least key value would become Boolean false.
 
More importantly, today a key with array value [1, 2, 3] is immediately followed by [1, 2, 3, -Infinity], meaning there is no key after [1, 2, 3] that comes before [1, 2, 3, -Infinity]. If Booleans were to be the first key type, [1, 2, 3] would instead be immediately followed by [1, 2, 3, false], potentially a breaking change.
 
Code based on the current specification that uses `IDBKeyRange.bound([1, 2, 3], [1, 2, 3, -Infinity], false, true)` to find records equal to [1, 2, 3] would come to spuriously yield records equal to and prefixed with [1, 2, 3, false] and [1, 2, 3, true].
 
The reason such code might not use the simpler `IDBKeyRange.only([1, 2, 3])` for this purpose is because of composite key paths. Consider a composite key path ["a", "b"]. Attempting to find all records with "a" equal to [1, 2, 3] with `IDBKeyRange.only([1, 2, 3])` would yield no results because, with the value of "b" appended, all records with "a" equal to [1, 2, 3] come after `IDBKeyRange.only([1, 2, 3])` in the key ordering. To account for this, the solution is to use a closed upper bound set to the value immediately following [1, 2, 3], which can be calculated using the rules set forth in the specification.
  
#### 2. Number < Boolean < Date < String < Array:
 
If Boolean were inserted between Number and Date, the key value immediately following Infinity would change from being Date(-8640000000000000), [the earliest representable date](http://ecma-international.org/ecma-262/5.1/#sec-15.9.1.1), to being Boolean false. Additionally, the key immediately preceding Date(-8640000000000000) would change from being Infinity to being Boolean true.
 
Attempts by existing code to use ranges like `IDBKeyRange.bound(Infinity, new Date(-8640000000000000), false, true)` to find records with "a" equal to Infinity in composite keys paths ["a", "b"] would come to yield spurious results.
 
#### 3. Number < Date < Boolean < String < Array:
 
If Boolean were inserted between Date and String, the key value immediately following Date(8640000000000000) would change from being the empty String("") to being Boolean false.
 
Attempts by existing code to use ranges like `IDBKeyRange.bound(new Date(8640000000000000), "", false, true)` to find records with "a" equal to Date(8640000000000000) in composite keys paths ["a", "b"] would come to yield spurious results.
 
#### 4. Number < Date < String < Boolean < Array:
 
If the Booleans were inserted between String and Array, I think things look good. While there are still ranges that will yield different lists of records, there are ways to work with this change to the ordering, at least with respect to its interaction with composite key paths.
 
Importantly, inserting Booleans between Strings and Arrays does not result in any case where the key that immediately follows some other key is different from the way it was before. The reason is because there would be no string followed immediately by false in the key ordering; rather, the value immediately following any string in the ordering is always that string juxtaposed with the null character '\0'.
 
One caveat is Internet Explorer / Edge. Neither of these (henceforth IE) [implement array keys](https://developer.microsoft.com/en-us/microsoft-edge/platform/status/indexeddbarraysandmultientrysupport/). A cross-browser workaround is to use String keys with a special array encoding instead of Array keys in IE. If Booleans were inserted between Strings and Arrays, Booleans would follow Arrays (aka Strings) in IE while Booleans would precede Arrays in other browsers.
 
#### 5. Number < Date < String < Array < Boolean:
 
As noted above, the value immediately following any array in the ordering is that array appended with the value -Infinity, e.g. [1, 2, 3] is immediately followed by [1, 2, 3, -Infinity]. Similar to Booleans following Strings, this means introducing Boolean after Array would not change the key that immediately followed any other key, and seems workable.
 
I am wary that where before the ordering terminated with the "infinite" Array keys, the ordering would come to terminate with the finite Boolean keys. This means the greatest key value would come to be  a tangible value, specifically Boolean true. This invites code that actually uses Boolean true as a bound that is assumed to be greater than all others, which could impede adding further new key types after the Booleans in the future.
 
#### Summary
 
If Booleans are to become valid keys, as a general rule, I think they should follow one of the “infinite” key types, either String or Array, so that in no case does the key that immediately follows any other key change. This is so that existing key ranges work as anticipated in association with composite key paths. To ensure that the greatest key value does not have a finite representation, I think I prefer to put the Booleans between the Strings and the Arrays. However, if a future IE is expected to support Boolean keys without also supporting Array keys, there might be an argument for having Boolean follow Array, so that existing hacks to support Arrays in IE continue to work consistently in a world with Boolean keys. Of course, I would much prefer IE to support Array keys.
  
I suggest addressing other potentially indexable key types, such as null, at the same time, to make sure everything plays nice. Changes like this are perilous!
 
Going forward, this kind of issue, where the ordering of one type of key relative to others is relied upon outside of the IndexedDB implementation, could be avoided if the APIs for querying records took separate ranges for each element of a composite key path rather than a single key range for the whole composite key path.
 
[Here is existence proof](https://github.com/alastairpatrick/fluentquery/blob/master/src/range.js) of code that would be impacted by the introduction of Boolean key values as described in the examples above. Its vulnerability to the specification of key ordering is clear in the nextUp function, which is at the top of the linked file at the time of writing. I am sure other applications and libraries would be affected too.
 


-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/w3c/IndexedDB/issues/76#issuecomment-307652956