fix: orderable has incorrect sort results depending on capitalization

[DanRibbens]

What?

The results when querying orderable collections can be incorrect due to how the underlying database handles sorting when capitalized letters are introduced.

Why?

The original fractional indexing logic uses base 62 characters to maximize the amount of data per character. This optimization saves a few characters of text in the database but fails to return accurate results when mixing uppercase and lowercase characters.

How?

Instead we can use base 36 values instead (0-9,a-z) so that all databases handle the sort consistently without needing to introduce collation or other alternate solutions.

Fixes #12397

[r1tsuu]

lgtm

[GermanJablo]

I find it quite curious that the library doesn't throw an error if it receives parameters in another base. That's good, but there's a problem.

To make sure this works, I copied the library's tests in base 64 and tried to see their output when converting to base 36. If the parameters have capital letters, it's possible the output will too.

it('generateKeyBetween', () => { expect(generateKeyBetween('a0', 'a1')).toBe('a0i') expect(generateKeyBetween('aA', 'aa')).toBe('a0') expect(generateKeyBetween(null, null)).toBe('a0') expect(generateKeyBetween(null, 'a0')).toBe('Zz') // WHAT?? expect(generateKeyBetween(null, 'Zz')).toBe('Zy') // Ups! expect(generateKeyBetween('a0', null)).toBe('a1') expect(generateKeyBetween('a1', null)).toBe('a2') expect(generateKeyBetween('a0', 'a1')).toBe('a0i') expect(generateKeyBetween('a1', 'a2')).toBe('a1i') expect(generateKeyBetween('a0V', 'a1')).toBe('a0i') expect(generateKeyBetween('Zz', 'a0')).toBe('Zzi') // Ups! expect(generateKeyBetween('Zz', 'a1')).toBe('a0') expect(generateKeyBetween(null, 'Y00')).toBe('Xzzz') // Ups! expect(generateKeyBetween('bzz', null)).toBe('c000') expect(generateKeyBetween('a0', 'a0V')).toBe('a00i') expect(generateKeyBetween('a0', 'a0G')).toBe('a00i') expect(generateKeyBetween('b125', 'b129')).toBe('b127') expect(generateKeyBetween('a0', 'a1V')).toBe('a1') expect(generateKeyBetween('Zz', 'a01')).toBe('a0') expect(generateKeyBetween(null, 'a0V')).toBe('a0') expect(generateKeyBetween(null, 'b999')).toBe('b99') })

The four assertions with comments have capital letters in the output. The one that puzzles me the most is the first one (generateKeyBetween(null, 'a0'), because it doesn't even have capital letters in the parameters. So it seems like a bug in the algorithm.

It may be that this PR reduces the likelihood of new capitals appearing, and if people who already have capitals reorder a lot, several may disappear. But there are no guarantees.

[GermanJablo]

Let's track this: rocicorp/fractional-indexing#22

[github-actions]

🚀 This is included in version v3.43.0