positions.ts · Source

positions.tsapps/api/src/lib/positions.tsraw ← lib6,908 B← Back to the app
1/**
2 * Fractional (LexoRank-style) positions over base-62 strings.
3 *
4 * A position `S` maps to the value  v(S) = Σ digit(i) / 62^(i+1)  ∈ (0, 1).
5 * This ordering is exactly lexicographic order (proved by the prefix
6 * property: v(S+c) = v(S) + c/62^len(S) + … and the first-difference
7 * property), which is also PostgreSQL/byte string order for ASCII — so
8 * `ORDER BY position` works without any cast.
9 *
10 * `between(a, b)` computes the midpoint on a fixed grid of 62^L cells and
11 * grows L (precision) until the two neighbours are not adjacent cells.
12 * Nesting to arbitrary depth therefore works; the only failure mode is a
13 * gap beyond 128 digits of precision, which throws and asks for a rebalance
14 * (callers fall back to {@link rebalancePositions}).
15 *
16 * `between(a)` (append after `a`) is the hot path for "add block at the
17 * END of the page" — the single most common mutation. It is a cheap,
18 * non-converging extension (`a` + midpoint char), NOT a midpoint toward the
19 * grid top: the latter converges on the top in one digit per append and
20 * exhausts MAX_PRECISION after ~127 appends (a 93-page / 16K-word paste
21 * 500'd with "position too close to the top"). With the extension rule the
22 * append position keeps ~half the alphabet of headroom *below* the new
23 * sibling, so interleaved inserts after an appended tail still split
24 * normally, and even a million straight appends only lengthen the position
25 * by ~17 characters.
26 */
27 
28const ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
29const ALPHABET_SET = new Set(ALPHABET);
30const BASE = 62n;
31export const MAX_PRECISION = 128;
32/** Midpoint digit of the alphabet (31 → 'V'): the append extension char. */
33const MID_INDEX = 31;
34 
35/** Validate a position string: non-empty base-62, bounded length. */
36export function isValid(s: string): boolean {
37  if (typeof s !== "string" || s.length === 0 || s.length > 512) return false;
38  for (const ch of s) if (!ALPHABET_SET.has(ch)) return false;
39  return true;
40}
41 
42/** Lexicographic compare (== positional order): -1 | 0 | 1. */
43export function compare(a: string, b: string): -1 | 0 | 1 {
44  if (a === b) return 0;
45  return a < b ? -1 : 1;
46}
47 
48/** Decode a position to (digits-as-base62-integer, length). */
49function decode(s: string): { v: bigint; len: number } {
50  let v = 0n;
51  for (const ch of s) v = v * BASE + BigInt(ALPHABET.indexOf(ch));
52  return { v, len: s.length };
53}
54 
55/** Encode an integer as exactly `len` base-62 digits (zero-padded). */
56export function encodeFixed(v: bigint, len: number): string {
57  let out = "";
58  for (let i = len - 1; i >= 0; i--) {
59    out = ALPHABET.charAt(Number(v % BASE)) + out;
60    v /= BASE;
61  }
62  return out;
63}
64 
65/**
66 * A position strictly between `a` and `b` (positional order).
67 * - both omitted → first position "A"
68 * - only `b`     → a position before `b`
69 * - only `a`     → a position after `a`
70 * Throws RangeError when the gap is beyond 128 digits of precision.
71 */
72export function between(a?: string, b?: string): string {
73  if (!a && !b) return "A";
74 
75  if (a && !b) {
76    // Append after `a` (the "add at end of the page" hot path): extend
77    // `a` with one midpoint char — `a + 'V'`. The previous rule took the
78    // midpoint between `a` and the grid TOP, which converged on "zzzz…"
79    // (one more z per append) and exhausted MAX_PRECISION after ~127
80    // appends: every large paste (93 pages / ~400 blocks) 500'd with
81    // "position too close to the top". The extension is strictly greater
82    // than `a` (prefix property), keeps ~half the alphabet of headroom
83    // BELOW the new sibling (inserts after an appended tail still split
84    // via the midpoint rules), and N straight appends add only N chars —
85    // ~17 chars for a million inserts.
86    if (a.length >= MAX_PRECISION) {
87      throw new RangeError("position at max length — rebalance required");
88    }
89    return a + ALPHABET.charAt(MID_INDEX);
90  }
91 
92  if (!a) {
93    // Before `b`: midpoint between 0 and v(b).
94    // (Unreachable unless both were omitted — handled above; type guard.)
95    if (!b) return "A";
96    const { v: bv, len: lb } = decode(b);
97    for (let L = lb; L <= MAX_PRECISION; L++) {
98      const scale = BASE ** BigInt(L);
99      const b2 = bv * (scale / BASE ** BigInt(lb));
100      if (b2 > 1n) {
101        let mid = b2 / 2n;
102        if (mid <= 0n) mid = 1n;
103        if (mid < b2) return encodeFixed(mid, L);
104      }
105    }
106    throw new RangeError("position too close to the bottom — rebalance required");
107  }
108 
109  // Both sides: midpoint with growing precision.
110  // (Unreachable unless `b` was omitted — that case exits above; type guard.)
111  if (!b) return "A";
112  const { v: av, len: la } = decode(a);
113  const { v: bv, len: lb } = decode(b);
114  if (compare(a, b) >= 0) throw new RangeError("between(a, b): a must sort before b");
115 
116  for (let L = Math.max(la, lb); L <= MAX_PRECISION; L++) {
117    const scale = BASE ** BigInt(L);
118    const a2 = av * (scale / BASE ** BigInt(la));
119    const b2 = bv * (scale / BASE ** BigInt(lb));
120    if (b2 - a2 > 1n) {
121      const mid = (a2 + b2) / 2n;
122      if (mid > a2 && mid < b2) return encodeFixed(mid, L);
123    }
124  }
125  throw new RangeError("positions too close — rebalance required");
126}
127 
128/** First position for a fresh tree. */
129export function first(): string {
130  return "A";
131}
132 
133/**
134 * Re-space a sibling list that ran out of positional headroom (positions
135 * converged to 128-digit neighbours, so `between` can no longer split).
136 *
137 * `positions` must be the sibling list in ASCENDING order (as
138 * `ORDER BY position` returns it). The result is one new position per
139 * entry, equal in length and evenly spread across the 62^L grid (L = the
140 * smallest precision with ≥ n·2 free cells, so every fresh position keeps
141 * room for future inserts around it). Order and duplicates are preserved:
142 * two rows that already share a position (a pre-existing corruption) get
143 * adjacent slots, so the rebalance doubles as a repair.
144 *
145 * Callers run this inside the same transaction that hit the RangeError and
146 * rewrite the whole sibling list — one indexed UPDATEs batch, no reindex
147 * of other pages (the positions are scoped to this page/parent).
148 */
149export function rebalancePositions(positions: readonly string[]): string[] {
150  const n = positions.length;
151  if (n === 0) return [];
152  // Smallest grid with at least 2 cells per row (≥1 spare on each side).
153  // For any JS-sized list (n ≤ 2^53) this converges at L ≤ ~25; the
154  // MAX_PRECISION guard below rejects only absurdly large inputs.
155  let L = 1;
156  while (BASE ** BigInt(L) < BigInt(n) * 2n) L += 1;
157  if (L > MAX_PRECISION) throw new RangeError("sibling list too large to rebalance");
158  const scale = BASE ** BigInt(L);
159  const step = scale / BigInt(n);
160  const out: string[] = [];
161  for (let i = 0; i < n; i++) {
162    out.push(encodeFixed(BigInt(i) * step + step / 2n, L));
163  }
164  return out;
165}
166