positions.ts · Source

positions.tspackages/shared/src/positions.tsraw ← src15,878 B← Back to the app
1/**
2 * @factory/shared — fractional (LexoRank-style) position engine.
3 *
4 * ## Why fractional positions
5 *
6 * Blocks, pages, records and properties are ordered by a `position` **string**
7 * that is compared **lexicographically**, never by an array index. Inserting
8 * between two siblings only rewrites the single row that changes; no other
9 * row moves. This is what keeps a 100k-block page cheap to reorder
10 * (ARCHITECTURE.md invariant 4; PRODUCT-SPEC §4 / §8).
11 *
12 * ## Alphabet
13 *
14 * Base-36, lowercase, digits first (10 digits + 26 letters = 36 chars):
15 *
16 *     0123456789abcdefghijklmnopqrstuvwxyz
17 *
18 * (Referred to as "base-32" in older notes; the alphabet string above is the
19 * single source of truth — the code derives `BASE` from its length.)
20 * Digit-first is deliberate: it matches the prisma default position `"a0"`
21 * and keeps generated keys human-readable.
22 *
23 * ## Order model
24 *
25 * Comparison is plain lexicographic with the prefix rule ("a" < "a0" < "a1").
26 * Consequence worth knowing: **the immediate successor of any position `x`
27 * is `x + "0"`** — there is no valid position strictly between `"a"` and
28 * `"a0"`. All other gaps are splittable. Every split by {@link betweenPosition}
29 * adds at most one character in the common case, so positions grow slowly
30 * until {@link needsRebalance} (length > {@link LIMITS.MAX_POSITION_LENGTH})
31 * says the sibling list should be re-spaced with
32 * {@link rebalancePositions}.
33 *
34 * ## Algorithm (`betweenPosition`)
35 *
36 * Walk both strings over their common prefix `P`, then:
37 *
38 * 1. **`a` is a strict prefix of `b`** (`b = P + R`, `R` non-empty): the
39 *    answer is `P + t` where `t` is a balanced *non-empty* string strictly
40 *    smaller than `R` (see {@link beforeMidpoint}). If `R === "0"` the gap is
41 *    empty — `b` is the immediate successor of `a` — and the caller must
42 *    rebalance instead.
43 * 2. **First differing character**, `a[i] < b[i]`:
44 *    - if `idx(b[i]) - idx(a[i]) >= 2`, emit the midpoint character and stop;
45 *    - if the characters are adjacent (`b[i] = a[i]+1`), keep `a[i]` and
46 *      append {@link afterMidpoint} of `a`'s remaining suffix — a balanced
47 *      string strictly greater than that suffix. The result is `> a` and
48 *      automatically `< b`.
49 *
50 * `beforeMidpoint` / `afterMidpoint` are the two "one-sided" midpoints used
51 * above; each adds at most one character per recursion level, so the output
52 * length is bounded by `max(len(a), len(b)) + 1` per split.
53 *
54 * ## Invariants (property-tested in `positions.test.ts`)
55 *
56 * - `comparePositions(a, between(a, b), b)` → strictly `a < mid < b`.
57 * - `between` throws on `a >= b`, invalid positions, empty gaps
58 *   (`b === a + "0"`) and when the result would exceed
59 *   {@link LIMITS.MAX_POSITION_LENGTH}.
60 * - Repeated halving of one gap produces a strictly ordered chain of valid
61 *   positions until rebalance is needed.
62 * - `rebalancePositions` preserves order and always emits positions of
63 *   length ≤ 1 + `ceil(log32(n))`.
64 *
65 * References: LexoRank (https://github.com/facebook/lexorank),
66 * "Fractional Indexing" (https://blog.jcoglan.com/2017/10/12/fractional-indexing/).
67 */
68 
69import { LIMITS } from "./constants.js";
70 
71/** The 36-character alphabet: digits first, then lowercase letters. */
72export const POSITION_ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyz" as const;
73 
74/** A fractional ordering key: any non-empty string over the alphabet. */
75export type Position = string;
76 
77const BASE = POSITION_ALPHABET.length; // 36
78const MAX_LEN = LIMITS.MAX_POSITION_LENGTH; // 64
79const MID = BASE >> 1; // 18 → 'i', the balanced one-char midpoint
80 
81/** True when every character of `p` is in the alphabet and length is legal. */
82export function isValidPosition(p: Position): boolean {
83  if (typeof p !== "string" || p.length === 0 || p.length > MAX_LEN) return false;
84  for (let i = 0; i < p.length; i++) {
85    const c = p.charCodeAt(i);
86    const okDigit = c >= 48 && c <= 57; // 0-9
87    const okLetter = c >= 97 && c <= 122; // a-z
88    if (!okDigit && !okLetter) return false;
89  }
90  return true;
91}
92 
93/**
94 * Lexicographic comparison of two positions. Returns -1, 0 or 1.
95 *
96 * Plain code-unit comparison is correct for our alphabet (single-unit chars,
97 * code-point order == rank order). Shorter prefixes sort first: "a" < "a0".
98 */
99export function comparePositions(a: Position, b: Position): number {
100  if (a === b) return 0;
101  return a < b ? -1 : 1;
102}
103 
104/** Smallest possible position. Used as a virtual lower anchor. */
105export function minPosition(): Position {
106  return POSITION_ALPHABET.charAt(0);
107}
108 
109/**
110 * Largest single-character position. A sentinel meaning "after everything
111 * else" — it is not meant to be assigned to two siblings, so prefer
112 * {@link afterPosition} when appending to a list.
113 */
114export function maxPosition(): Position {
115  return POSITION_ALPHABET.charAt(BASE - 1);
116}
117 
118/**
119 * Generate a fresh position for a new top-level sibling list.
120 *
121 * - No argument → `"a0"` (matches the prisma `@default("a0")`, so newly
122 *   created rows and generated keys agree).
123 * - With `start` → `start + "i"` (alphabet midpoint), strictly greater than
124 *   `start` with room on both sides (used when creating the first element of
125 *   a new container that must sort after an existing marker).
126 *
127 * @throws RangeError if `start` is not a valid position.
128 */
129export function generatePosition(start?: Position): Position {
130  if (start === undefined) return "a0";
131  if (!isValidPosition(start)) {
132    throw new RangeError(`invalid position: ${JSON.stringify(start)}`);
133  }
134  if (start.length >= MAX_LEN) {
135    throw new RangeError(`position at max length, cannot extend: ${start} — rebalance the list`);
136  }
137  return start + POSITION_ALPHABET.charAt(MID);
138}
139 
140/**
141 * A position strictly greater than `p` (append to end of a sibling list).
142 * Appends the alphabet midpoint `'i'`, which keeps maximal headroom below.
143 *
144 * @throws RangeError if `p` is invalid or already at the max length.
145 */
146export function afterPosition(p: Position): Position {
147  if (!isValidPosition(p)) {
148    throw new RangeError(`invalid position: ${JSON.stringify(p)}`);
149  }
150  if (p.length >= MAX_LEN) {
151    throw new RangeError(`position at max length, cannot extend: ${p} — rebalance the list`);
152  }
153  return p + POSITION_ALPHABET.charAt(MID);
154}
155 
156/**
157 * A position strictly less than `p` (prepend to start of a sibling list),
158 * with as much headroom above the result as the layout allows.
159 *
160 * - Last char > "0" → decrement it: `"a0p"` → `"a0o"`.
161 * - Trailing "0"s are dropped, then the new last char is decremented:
162 *   `"a900"` → `"a8"`, `"a0"` → `"9"`.
163 *
164 * @throws RangeError if `p` is invalid or no smaller position exists
165 *   (`p` is `"0"`-like at the bottom of the range).
166 */
167export function beforePosition(p: Position): Position {
168  if (!isValidPosition(p)) {
169    throw new RangeError(`invalid position: ${JSON.stringify(p)}`);
170  }
171  let i = p.length - 1;
172  while (i >= 1 && p.charAt(i) === "0") i--;
173  const idx = POSITION_ALPHABET.indexOf(p.charAt(i));
174  if (idx <= 0) {
175    // `p` is all "0" chars. Shortening by one char yields a valid, smaller
176    // position ("00" → "0"); a single "0" has nothing below it.
177    if (p.length > 1) return p.slice(0, p.length - 1);
178    throw new RangeError(`no position below ${p}`);
179  }
180  return p.slice(0, i) + POSITION_ALPHABET.charAt(idx - 1);
181}
182 
183/**
184 * A position strictly between `a` and `b`. **Requires `a < b`** (throws
185 * otherwise). Returns the shortest balanced position splitting the gap.
186 *
187 * @throws RangeError if `a >= b`, either position is invalid, the gap is
188 *   empty (`b === a + "0"`), or the result would exceed the max length —
189 *   rebalance the sibling list in those cases.
190 */
191export function betweenPosition(a: Position, b: Position): Position {
192  if (!isValidPosition(a) || !isValidPosition(b)) {
193    throw new RangeError("betweenPosition received an invalid position");
194  }
195  if (comparePositions(a, b) !== -1) {
196    throw new RangeError(`betweenPosition requires a < b (got a=${a}, b=${b})`);
197  }
198 
199  const n = a.length;
200  const m = b.length;
201  let i = 0;
202  // Common prefix.
203  while (i < n && i < m && a.charAt(i) === b.charAt(i)) i++;
204 
205  let result: string;
206  if (i === n) {
207    // Case 1: a is a strict prefix of b.  b = P + R, R non-empty.
208    const rest = b.slice(i);
209    if (rest === "0") {
210      // Empty gap: b is the immediate successor of a (a + "0"). There is no
211      // valid position strictly between them — rebalance is required.
212      throw new RangeError(
213        `betweenPosition(${a}, ${b}) is an empty gap (b is the immediate successor of a) — rebalance the list`,
214      );
215    }
216    result = a + beforeMidpoint(rest);
217  } else {
218    // Case 2: first differing character at index i (b cannot be the shorter
219    // string here: a < b and a prefix of b is the only way one is shorter).
220    const ca = POSITION_ALPHABET.indexOf(a.charAt(i));
221    const cb = POSITION_ALPHABET.indexOf(b.charAt(i));
222    if (cb - ca >= 2) {
223      result = a.slice(0, i) + POSITION_ALPHABET.charAt(ca + ((cb - ca) >> 1));
224    } else {
225      // Adjacent characters: keep a[i], descend past a's suffix.
226      result = a.slice(0, i + 1) + afterMidpoint(a.slice(i + 1));
227    }
228  }
229 
230  if (result.length > MAX_LEN) {
231    throw new RangeError(
232      `betweenPosition(${a}, ${b}) exceeds max length ${MAX_LEN} — rebalance the list`,
233    );
234  }
235  return result;
236}
237 
238/**
239 * Balanced non-empty string strictly smaller than `rest` (`rest` non-empty,
240 * `rest !== "0"`). Used for the "a is a prefix of b" case: the gap is
241 * exactly the non-empty `t < rest`.
242 *
243 * Finds the first index `j` with `rest[j] > "0"`:
244 * - `rest` is all "0"s (length ≥ 2): return `rest` minus its last char.
245 * - `rest = 0^j · c · T`, `idx(c) ≥ 2`: return `0^j · char(idx(c) >> 1)`.
246 * - `rest = 0^j · "1" · T`: return `0^j · "0"` (+ recurse into `T` when it
247 *   itself contains a non-zero).
248 */
249function beforeMidpoint(rest: string): string {
250  let j = 0;
251  while (j < rest.length && rest.charAt(j) === "0") j++;
252 
253  if (j === rest.length) {
254    // All zeros, length ≥ 2 guaranteed by the caller ("0" is the empty gap).
255    return rest.slice(0, rest.length - 1);
256  }
257 
258  const cIdx = POSITION_ALPHABET.indexOf(rest.charAt(j));
259  const head = rest.slice(0, j);
260  if (cIdx >= 2) {
261    return head + POSITION_ALPHABET.charAt(cIdx >> 1);
262  }
263  // c === '1'
264  const tail = rest.slice(j + 1);
265  if (tail.length === 0 || isAllZeros(tail)) {
266    return head + "0";
267  }
268  return head + "0" + beforeMidpoint(tail);
269}
270 
271/**
272 * Balanced string strictly greater than `suffix` (which may be empty). Used
273 * for the adjacent-character case: everything `suffix + t` with `t` in this
274 * space sorts between `a` and `b`.
275 *
276 * - empty suffix → the alphabet midpoint `"p"`.
277 * - last char < "z" → replace it with the midpoint between it and "z".
278 * - last char "z" → append `"p"`.
279 */
280function afterMidpoint(suffix: string): string {
281  if (suffix.length === 0) return POSITION_ALPHABET.charAt(MID);
282  // Find the last index whose character can be INCREASED STRICTLY without
283  // exceeding the alphabet max ("z"), then replace it with the midpoint
284  // between it and "z" and drop the tail. Dropping the tail is safe: any
285  // string with that prefix and a character greater than the original (and
286  // any tail) still exceeds the original suffix; the tail-less form is the
287  // minimal such value.
288  //
289  // Strictness matters: the midpoint formula `idx + ((BASE-1-idx)>>1)` is a
290  // no-op for `idx === BASE-2` (the second-to-last char, "y"): its midpoint
291  // to "z" is itself. Increasing such a char in place would return the
292  // suffix UNCHANGED (e.g. betweenPosition("oy","p0") → "oy"), violating
293  // the strict-inside-gap contract — so those chars are skipped. The
294  // threshold `idx <= BASE-3` is exactly the set of chars whose midpoint to
295  // "z" is strictly greater.
296  for (let k = suffix.length - 1; k >= 0; k--) {
297    const idx = POSITION_ALPHABET.indexOf(suffix.charAt(k));
298    if (idx <= BASE - 3) {
299      return suffix.slice(0, k) + POSITION_ALPHABET.charAt(idx + ((BASE - 1 - idx) >> 1));
300    }
301  }
302  // No char can be increased in place ("y"/"z" tail): append the midpoint —
303  // the minimal balanced strictly-greater extension (mirrors afterPosition).
304  return suffix + POSITION_ALPHABET.charAt(MID);
305}
306 
307function isAllZeros(s: string): boolean {
308  for (let i = 0; i < s.length; i++) if (s.charAt(i) !== "0") return false;
309  return true;
310}
311 
312/**
313 * True when the sibling list is unhealthy: any position longer than
314 * {@link LIMITS.MAX_POSITION_LENGTH}. The caller should re-space the list
315 * with {@link rebalancePositions} (the API also does this preemptively at a
316 * softer threshold, e.g. 24 chars, to keep future writes short).
317 */
318export function needsRebalance(positions: readonly Position[]): boolean {
319  for (const p of positions) {
320    if (p.length > MAX_LEN) return true;
321  }
322  return false;
323}
324 
325/**
326 * Re-space a sibling list into short, uniformly spaced positions, preserving
327 * relative order. Returns a map of old position → new position.
328 *
329 * Layout: `"a"` + a fixed-width base-32 encoding of the slot, where the
330 * width is `max(1, ceil(log32(n)))` for `n` slots. Fixed width is required
331 * because lexicographic order with the prefix rule does **not** agree with
332 * variable-width numeric order ("a10" would sort before "aa"). Output length
333 * is at most `1 + width` (≤ 4 chars for up to 32,768 siblings — far beyond
334 * any realistic sibling list).
335 *
336 * The input order is ignored except for detecting duplicates; the *sorted*
337 * order defines slot 0, 1, 2, …. Duplicate positions are rejected — positions
338 * are unique within a sibling list (enforced by the database too).
339 *
340 * @throws RangeError on duplicate or invalid positions.
341 */
342export function rebalancePositions(positions: readonly Position[]): Record<string, string> {
343  for (const p of positions) {
344    if (!isValidPosition(p)) {
345      throw new RangeError(`invalid position: ${JSON.stringify(p)}`);
346    }
347  }
348  const seen = new Set<string>();
349  for (const p of positions) {
350    if (seen.has(p)) throw new RangeError(`duplicate position: ${p}`);
351    seen.add(p);
352  }
353 
354  const n = positions.length;
355  const width = n <= BASE ? 1 : Math.ceil(Math.log(n) / Math.log(BASE));
356  const sorted = [...positions].sort(comparePositions);
357  const mapping: Record<string, string> = {};
358  for (let slot = 0; slot < sorted.length; slot++) {
359    const key = sorted[slot] as string; // slot < length — index is defined
360    mapping[key] = "a" + toFixedWidthBase32(slot, width);
361  }
362  return mapping;
363}
364 
365/** Encode `slot` in base-32, zero-padded to exactly `width` digits. */
366function toFixedWidthBase32(slot: number, width: number): string {
367  let x = slot;
368  const chars: string[] = [];
369  for (let i = 0; i < width; i++) {
370    chars.push(POSITION_ALPHABET.charAt(x % BASE));
371    x = Math.floor(x / BASE);
372  }
373  chars.reverse();
374  return chars.join("");
375}
376 
377/**
378 * Compute the new position of a block moved into a slot defined by its
379 * neighbors (the API batch handler and the editor DnD layer both use this so
380 * the rule lives in one place):
381 *
382 * - `before` + `after` → midpoint between them.
383 * - `before` only → append after it.
384 * - `after` only → prepend before it (midpoint from the lower anchor).
385 * - neither → fresh position `"a0"`.
386 */
387export function positionForSlotNeighbors(
388  before?: Position | null,
389  after?: Position | null,
390): Position {
391  if (before && after) return betweenPosition(before, after);
392  if (before) return afterPosition(before);
393  if (after) return betweenPosition(minPosition(), after);
394  return generatePosition();
395}
396 
397/** Sort a list of positions ascending. */
398export function sortPositions(positions: readonly Position[]): Position[] {
399  return [...positions].sort(comparePositions);
400}
401