Fractional Rank Algorithm

Custom ordering of Lists, Tasks, and Steps is persisted with fractional index keys rather than integer positions, so a reorder updates only the moved row. The algorithm lives in src/lib/rank/.

The functions in src/lib/rank/ and what they build on:

flowchart LR
  Gen["generateKeyBetween(prev, next)"] --> JFI["jittered-fractional-indexing"]
  GenN["generateNKeysBetween(prev, next, n)"] --> JFI
  Gen --> Jitter["getRandomBit<br/>(jitter.ts)"]
  GenN --> Jitter
  Rebal["rebalanceSegment<br/>(rebalance.ts)"] --> GenN
  NeedsR["needsRebalance(rank, threshold)"] --> Rebal
  Cmp["compareRanks(a, b)"] --> Sort["renderSortMode<br/>(sort-modes.ts)"]
  Gen --> Rank[("rank columns:<br/>lists, groups, tasks, steps")]

API (src/lib/rank/index.ts)

• generateKeyBetween(prev, next) — produce a key that sorts strictly between two existing keys (either may be null for the ends). Inserting at the top of a List means generateKeyBetween(null, firstRank).
• generateNKeysBetween(prev, next, n) — produce n evenly distributed keys between two bounds (bulk insert / backfill).
• compareRanks(a, b) — total order over rank strings.
• needsRebalance(rank, threshold = REBALANCE_THRESHOLD) — flag keys that have grown too long after many in-between insertions; REBALANCE_THRESHOLD is 64.
• src/lib/rank/jitter.ts (getRandomBit) — adds a small random suffix so two clients inserting at the same position offline produce distinct keys, avoiding collisions on replay.

The decision flow for placing a row between two neighbors, including the rebalance branch:

flowchart TD
  Drop["drop between prev and next"] --> Ends{"prev or next<br/>null (an end)?"}
  Ends -->|top| Top["generateKeyBetween(null, firstRank)"]
  Ends -->|bottom| Bot["generateKeyBetween(lastRank, null)"]
  Ends -->|middle| Mid["generateKeyBetween(prev, next)"]
  Top --> Check
  Bot --> Check
  Mid --> Check{"needsRebalance(rank)<br/>length > 64?"}
  Check -->|no| Done["persist single rank"]
  Check -->|yes| Reb["rebalanceSegment<br/>generateNKeysBetween(prev, next, n)"]
  Reb --> Done

Persistence

rank columns on lists, groups, tasks, and steps store the keys (migrations 0007_add_list_rank.sql, 0008_add_step_rank.sql). Ordering scope follows the domain rules: per-List for Tasks, per-Task for Steps, per-User for Lists and Groups (Product Brief §5.2). src/lib/rank/backfill.ts (run via scripts/backfill-ranks.mjs) assigns keys to pre-existing rows; src/lib/rank/sort-modes.ts maps the sort menu’s temporary orderings.

Sorting (importance / alphabetical / due date / created) produces a temporary view; drag-and-drop sets the persisted fractional order (spec 007).

Related: System Views & Sort Menus and the sidebar ordering UI (deferred guides).