positions.test.ts

positions.test.tsapps/api/src/lib/__tests__/positions.test.tsraw ← __tests__7,337 B← Back to the app
1import { describe, expect, it } from "vitest";
2import { between, compare, first, isValid, rebalancePositions } from "../positions.js";
3 
4describe("positions (base-62 fractional)", () => {
5  it("first() and between() with no neighbours give canonical start/end", () => {
6    expect(first()).toBe("A");
7    expect(between()).toBe("A");
8    const afterA = between("A");
9    expect(compare("A", afterA)).toBe(-1);
10  });
11 
12  it("between(a, b) always returns a position strictly between", () => {
13    const a = "B";
14    const b = "Z";
15    const mid = between(a, b);
16    expect(compare(a, mid)).toBe(-1);
17    expect(compare(mid, b)).toBe(-1);
18  });
19 
20  it("generates a sortable chain of 100 successive insertions", () => {
21    let prev: string | undefined;
22    let next: string | undefined;
23    const positions: string[] = [];
24    // repeatedly insert between the last two to create a descending staircase
25    for (let i = 0; i < 100; i++) {
26      const p = between(prev, next);
27      positions.push(p);
28      prev = p;
29    }
30    // every consecutive pair is strictly ordered
31    for (let i = 0; i < positions.length - 1; i++) {
32      expect(compare(positions[i]!, positions[i + 1]!)).toBe(-1);
33    }
34  });
35 
36  it("handles deep nesting: 50 levels of between(first, next)", () => {
37    let a: string | undefined;
38    let b: string | undefined;
39    for (let depth = 0; depth < 50; depth++) {
40      const mid = between(a, b);
41      expect(isValid(mid)).toBe(true);
42      if (a && b) {
43        expect(compare(a, mid)).toBe(-1);
44        expect(compare(mid, b)).toBe(-1);
45      }
46      a = mid;
47      b = undefined;
48    }
49    // still a valid, ordered chain
50    expect(isValid(a!)).toBe(true);
51  });
52 
53  it("grows precision as needed when neighbours are adjacent cells", () => {
54    // "0" and "1" are adjacent on the 1-digit grid; between must extend precision
55    const mid = between("0", "1");
56    expect(compare("0", mid)).toBe(-1);
57    expect(compare(mid, "1")).toBe(-1);
58    // and again between 0 and that midpoint (twice-adjacent)
59    const mid2 = between("0", mid);
60    expect(compare("0", mid2)).toBe(-1);
61    expect(compare(mid2, mid)).toBe(-1);
62  });
63 
64  it("before(a) positions sort below a, after(b) sort above b", () => {
65    const before = between(undefined, "A");
66    expect(compare(before, "A")).toBe(-1);
67    const after = between("A");
68    expect(compare("A", after)).toBe(-1);
69  });
70 
71  it("compare is a total order (antisymmetric, transitive)", () => {
72    const xs = ["0", "1", "A", "A0", "AA", "a", "z", "Z", "9z"];
73    for (const x of xs) {
74      expect(compare(x, x)).toBe(0);
75    }
76    for (const x of xs) {
77      for (const y of xs) {
78        if (x === y) continue;
79        const c = compare(x, y);
80        expect([-1, 1]).toContain(c);
81        expect(compare(y, x)).toBe(-c as -1 | 1);
82      }
83    }
84  });
85 
86  it("isValid accepts base-62 strings and rejects garbage", () => {
87    expect(isValid("A")).toBe(true);
88    expect(isValid("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz")).toBe(true);
89    expect(isValid("")).toBe(false);
90    expect(isValid("A B")).toBe(false);
91    expect(isValid("A!")).toBe(false);
92    expect(isValid(".")).toBe(false);
93  });
94 
95  it("random insertions stay globally ordered (stress: 300 inserts)", () => {
96    const pool: string[] = ["A"];
97    for (let i = 0; i < 300; i++) {
98      const idx = Math.floor(Math.random() * pool.length);
99      const a = idx > 0 ? pool[idx - 1] : undefined;
100      const b = idx < pool.length ? pool[idx] : undefined;
101      const p = between(a, b);
102      pool.splice(idx, 0, p);
103    }
104    for (let i = 0; i < pool.length - 1; i++) {
105      expect(compare(pool[i]!, pool[i + 1]!)).toBe(-1);
106      expect(pool[i] !== pool[i + 1]).toBe(true);
107    }
108  });
109 
110  it("throws when a must sort before b is violated", () => {
111    expect(() => between("Z", "A")).toThrow(RangeError);
112  });
113 
114  it("append (between(a)) extends with a midpoint char instead of converging on the top", () => {
115    // The old rule took the midpoint between `a` and the grid top, which
116    // converged on "zzzz…" (one more z per append) and threw after ~127
117    // appends — the 93-page/16K-word paste 500. The new rule appends one
118    // midpoint char per call: strictly greater than `a`, no convergence,
119    // and the top ("zzz…") is never approached.
120    expect(between("A")).toBe("AV");
121    expect(between("AV")).toBe("AVV");
122    // 127 appends from "A": length grows 1 → 128, every step strictly
123    // ordered, and the tail never converges toward "z" (last char = 'V').
124    let a = "A";
125    for (let i = 0; i < 127; i++) {
126      const next = between(a);
127      expect(compare(a, next)).toBe(-1);
128      expect(next.endsWith("V")).toBe(true);
129      a = next;
130    }
131    expect(a.length).toBe(128);
132    // At the documented precision cap the engine asks for a rebalance
133    // (the service layer performs it in-transaction and retries).
134    expect(() => between(a)).toThrow(RangeError);
135  });
136 
137  it("append then insert-after-appended-tail still splits (headroom below)", () => {
138    // Append twice, then insert BETWEEN the last two — the midpoint rule must
139    // find room below the tail (the old top-midpoint rule left none).
140    const p1 = between(undefined); // "A"
141    const p2 = between(p1); // "AV"
142    const p3 = between(p2); // "AVV"
143    const mid = between(p2, p3);
144    expect(compare(p2, mid)).toBe(-1);
145    expect(compare(mid, p3)).toBe(-1);
146  });
147 
148  it("rebalancePositions produces an evenly spaced, strictly ordered list", () => {
149    // Simulated exhausted list: consecutive appends under the NEW rule until
150    // the precision cap, hand rebalancePositions an ascending run and check
151    // the result (the service calls this when between() throws).
152    const input: string[] = [];
153    let a: string | undefined;
154    while (true) {
155      try {
156        a = between(a);
157      } catch {
158        break;
159      }
160      input.push(a!);
161    }
162    expect(input.length).toBe(128);
163    const fresh = rebalancePositions(input);
164    expect(fresh.length).toBe(128);
165    const len = fresh[0]!.length;
166    for (const p of fresh) {
167      expect(isValid(p)).toBe(true);
168      expect(p.length).toBe(len); // one uniform grid precision
169    }
170    for (let i = 0; i < fresh.length - 1; i++) {
171      expect(compare(fresh[i]!, fresh[i + 1]!)).toBe(-1);
172    }
173    // Every fresh slot is splittable: the neighbours have room to split.
174    const mid = between(fresh[1]!, fresh[2]!);
175    expect(compare(fresh[1]!, mid)).toBe(-1);
176    expect(compare(mid, fresh[2]!)).toBe(-1);
177  });
178 
179  it("rebalancePositions repairs duplicate positions into adjacent slots", () => {
180    const fresh = rebalancePositions(["A", "A", "A"]);
181    expect(fresh.length).toBe(3);
182    for (let i = 0; i < fresh.length - 1; i++) {
183      expect(compare(fresh[i]!, fresh[i + 1]!)).toBe(-1);
184    }
185  });
186 
187  it("rebalancePositions edge cases", () => {
188    expect(rebalancePositions([])).toEqual([]);
189    // A single row gets the one cell of the smallest grid (L=1).
190    expect(rebalancePositions(["A"])).toEqual(["V"]);
191    // 10k duplicate positions → 10k distinct ordered slots, no throw.
192    const fresh = rebalancePositions(new Array(10_000).fill("A"));
193    expect(fresh.length).toBe(10_000);
194    for (let i = 0; i < fresh.length - 1; i++) {
195      expect(compare(fresh[i]!, fresh[i + 1]!)).toBe(-1);
196    }
197  });
198});
199