Use variable-length string positions for the shopping list #30

New issue

Closed

opened 2026-10-12 15:24:32 +02:00 by michielbdejong · 0 comments

michielbdejong commented

2026-10-12 15:24:32 +02:00

Owner

Follow-up to #22 and #25.

Background

The shopping list currently uses integer positions and renumbers every item after a drag. In a captured four-item example, moving Coffee to the front on one replica and Milk to the end on another made both replicas rewrite all four positions. This causes unnecessary overlapping writes. The default localeCompare ID tie-breaker also differs between English and Danish.

NextGraph's pinned source uses observed-remove RDF transactions. Concurrent scalar replacements can retain different literals; the current exactly-one-position shape could then exclude the item. This is source-backed analysis, not a completed native replication experiment.

The Matrix discussion favors an unordered RDF set of item records with hidden ordering metadata, avoiding a serialized whole-list JSON array, fixed slot columns for a variable-length list, and RDF predecessor/linked-list relationships.

References:

Moving Elements in List CRDTs: https://martin.kleppmann.com/papers/list-move-papoc20.pdf
The Art of the Fugue: https://arxiv.org/abs/2305.00583
position-strings: https://github.com/mweidner037/position-strings

Implementation instructions

Change the canonical position datatype from integer to variable-length ordered string. Use a tested generator (position-strings) with distinct replica/source identities, rather than floats or hand-written midpoint strings.
Add at the end by generating a key after the last item. Reorder by generating a fresh key between the destination neighbors, updating only the moved item. Keep stable RDF subject identities and the existing UI.
Use a fixed code-unit/ASCII comparator for rank strings and ID tie-breaks.
Handle competing moves explicitly: permit concurrent position strings in the RDF shape, choose their lexicographically greatest rank for display (rightmost concurrent move wins), and replace all observed ranks on a subsequent move. This avoids hiding an item merely because two placements survive a merge. It is a deterministic policy, not physical-time last-writer-wins.
Preserve existing integer-position data through a clearly separated compatibility read shape and migration to string ranks. Preserve existing order for an integer-only list; do not silently discard records. Document that old integer-writing clients must be upgraded.
Update the authored Atomic JSON-AD shopping schema and generated ORM types, documentation, lockfile, and tests. Main now generates NextGraph schemas directly; preserve that pipeline and do not reintroduce ShEx. Add explicit unordered string-set and legacy read-datatype mappings as needed, with converter validation and tests. Verify actual ORM writes touch only the moved item; test same-gap insertion, insertion between concurrent keys, same-item competing ranks, legacy migration, and deterministic ordering.
Run unit/type/build/browser validation and merge the finished PR. Distinguish fixture/prototype results from native offline replication; do not claim the latter without running it.

The position generator alone is not a complete move CRDT. Membership/delete behavior remains NextGraph's existing semantics, and concurrent title edits are outside this ordering change.

Follow-up to #22 and #25. ## Background The shopping list currently uses integer positions and renumbers every item after a drag. In a captured four-item example, moving Coffee to the front on one replica and Milk to the end on another made both replicas rewrite all four positions. This causes unnecessary overlapping writes. The default localeCompare ID tie-breaker also differs between English and Danish. NextGraph's pinned source uses observed-remove RDF transactions. Concurrent scalar replacements can retain different literals; the current exactly-one-position shape could then exclude the item. This is source-backed analysis, not a completed native replication experiment. The Matrix discussion favors an unordered RDF set of item records with hidden ordering metadata, avoiding a serialized whole-list JSON array, fixed slot columns for a variable-length list, and RDF predecessor/linked-list relationships. References: - Moving Elements in List CRDTs: https://martin.kleppmann.com/papers/list-move-papoc20.pdf - The Art of the Fugue: https://arxiv.org/abs/2305.00583 - position-strings: https://github.com/mweidner037/position-strings ## Implementation instructions 1. Change the canonical position datatype from integer to variable-length ordered string. Use a tested generator (position-strings) with distinct replica/source identities, rather than floats or hand-written midpoint strings. 2. Add at the end by generating a key after the last item. Reorder by generating a fresh key between the destination neighbors, updating only the moved item. Keep stable RDF subject identities and the existing UI. 3. Use a fixed code-unit/ASCII comparator for rank strings and ID tie-breaks. 4. Handle competing moves explicitly: permit concurrent position strings in the RDF shape, choose their lexicographically greatest rank for display (rightmost concurrent move wins), and replace all observed ranks on a subsequent move. This avoids hiding an item merely because two placements survive a merge. It is a deterministic policy, not physical-time last-writer-wins. 5. Preserve existing integer-position data through a clearly separated compatibility read shape and migration to string ranks. Preserve existing order for an integer-only list; do not silently discard records. Document that old integer-writing clients must be upgraded. 6. Update the authored Atomic JSON-AD shopping schema and generated ORM types, documentation, lockfile, and tests. Main now generates NextGraph schemas directly; preserve that pipeline and do not reintroduce ShEx. Add explicit unordered string-set and legacy read-datatype mappings as needed, with converter validation and tests. Verify actual ORM writes touch only the moved item; test same-gap insertion, insertion between concurrent keys, same-item competing ranks, legacy migration, and deterministic ordering. 7. Run unit/type/build/browser validation and merge the finished PR. Distinguish fixture/prototype results from native offline replication; do not claim the latter without running it. The position generator alone is not a complete move CRDT. Membership/delete behavior remains NextGraph's existing semantics, and concurrent title edits are outside this ordering change.

michielbdejong referenced this issue from a pull request that will close it,

2026-10-12 15:59:48 +02:00

Use string position keys for shopping list ordering #33

michielbdejong closed this issue

2026-10-12 16:38:21 +02:00

michielbdejong referenced this issue from a commit

2026-10-12 16:38:22 +02:00

Merge pull request #33: Use string position keys