positions.test.ts

positions.test.tspackages/shared/src/positions.test.tsraw ← src11,857 B← Back to the app
1import { describe, expect, it } from "vitest";
2import * as fc from "fast-check";
3 
4import {
5  POSITION_ALPHABET,
6  afterPosition,
7  beforePosition,
8  betweenPosition,
9  comparePositions,
10  generatePosition,
11  isValidPosition,
12  maxPosition,
13  minPosition,
14  needsRebalance,
15  positionForSlotNeighbors,
16  rebalancePositions,
17  sortPositions,
18} from "./positions.js";
19import { LIMITS } from "./constants.js";
20 
21// Arbitrary: valid position strings over the alphabet.
22const positionArb = fc
23  .stringOf(fc.constantFrom(...Array.from(POSITION_ALPHABET)), { minLength: 1, maxLength: 8 })
24  .map((s) => s);
25 
26// Arbitrary strictly-ordered pair (a < b) with a non-empty gap (immediate
27// successors are un-splittable by design — rebalance instead).
28const orderedPairArb: fc.Arbitrary<[string, string]> = fc
29  .tuple(positionArb, positionArb)
30  .filter(([a, b]) => a !== b)
31  .map(([a, b]): [string, string] => (a < b ? [a, b] : [b, a]))
32  .filter(([lo, hi]) => hi !== lo + "0");
33 
34describe("comparePositions", () => {
35  it("orders by content with prefix rule", () => {
36    const sorted = sortPositions(["a", "a0", "a1", "aa", "b", "0", "z9"]);
37    expect(sorted).toEqual(["0", "a", "a0", "a1", "aa", "b", "z9"]);
38  });
39 
40  it("is a total order (property)", () => {
41    fc.assert(
42      fc.property(positionArb, positionArb, (a, b) => {
43        const ab = comparePositions(a, b);
44        const ba = comparePositions(b, a);
45        expect(ab * ba).toBeLessThanOrEqual(0);
46        if (a === b) expect(ab).toBe(0);
47      }),
48    );
49  });
50});
51 
52describe("minPosition / maxPosition", () => {
53  it("min < max", () => {
54    expect(comparePositions(minPosition(), maxPosition())).toBe(-1);
55  });
56 
57  it("min/max are valid single characters", () => {
58    expect(isValidPosition(minPosition())).toBe(true);
59    expect(isValidPosition(maxPosition())).toBe(true);
60    expect(minPosition()).toBe("0");
61    expect(maxPosition()).toBe("z");
62  });
63});
64 
65describe("generatePosition", () => {
66  it("defaults to a0 (matches prisma @default)", () => {
67    expect(generatePosition()).toBe("a0");
68  });
69 
70  it("with start: result is valid and strictly greater", () => {
71    fc.assert(
72      fc.property(positionArb, (start) => {
73        const p = generatePosition(start);
74        expect(isValidPosition(p)).toBe(true);
75        expect(comparePositions(start, p)).toBe(-1);
76      }),
77    );
78  });
79 
80  it("distinct starts yield distinct positions (uniqueness)", () => {
81    // 180 distinct starts (the full period of (i % 36, i % 10)).
82    const starts: string[] = [];
83    for (let i = 0; i < 180; i++) starts.push(`${POSITION_ALPHABET[i % 36]}${i % 10}`);
84    expect(new Set(starts).size).toBe(180);
85    const seen = new Set<string>();
86    for (const s of starts) {
87      const p = generatePosition(s);
88      expect(seen.has(p)).toBe(false);
89      seen.add(p);
90    }
91  });
92 
93  it("throws on invalid start", () => {
94    expect(() => generatePosition("ABC!")).toThrow(RangeError);
95  });
96});
97 
98describe("afterPosition / beforePosition", () => {
99  it("after > p and before < p (property)", () => {
100    fc.assert(
101      fc.property(positionArb, (p) => {
102        const after = afterPosition(p);
103        expect(comparePositions(p, after)).toBe(-1);
104      }),
105    );
106    fc.assert(
107      fc.property(
108        positionArb.filter((p) => p !== "0"),
109        (p) => {
110          const before = beforePosition(p);
111          expect(comparePositions(before, p)).toBe(-1);
112        },
113      ),
114    );
115  });
116 
117  it("before(after(p)) lands strictly between p and after(p)", () => {
118    for (const p of ["a0", "a0i", "5", "zz", "1"]) {
119      const b = beforePosition(afterPosition(p));
120      expect(comparePositions(p, b)).toBe(-1);
121      expect(comparePositions(b, afterPosition(p))).toBe(-1);
122    }
123  });
124 
125  it("beforePosition strips trailing zeros and decrements", () => {
126    expect(beforePosition("a0")).toBe("9");
127    expect(beforePosition("a900")).toBe("a8");
128    expect(beforePosition("a0p")).toBe("a0o");
129    expect(beforePosition("00")).toBe("0");
130  });
131 
132  it("throws when nothing is below", () => {
133    expect(() => beforePosition("0")).toThrow(RangeError);
134  });
135});
136 
137describe("betweenPosition", () => {
138  it("throws when a >= b", () => {
139    expect(() => betweenPosition("b", "a")).toThrow(RangeError);
140    expect(() => betweenPosition("a", "a")).toThrow(RangeError);
141  });
142 
143  it("throws on invalid positions", () => {
144    expect(() => betweenPosition("aB", "c")).toThrow(RangeError);
145    expect(() => betweenPosition("", "a")).toThrow(RangeError);
146  });
147 
148  it("throws on the empty gap (immediate successor)", () => {
149    expect(() => betweenPosition("a", "a0")).toThrow(/empty gap/);
150    expect(() => betweenPosition("a0", "a00")).toThrow(/empty gap/);
151  });
152 
153  it("orders correctly for hand-picked cases", () => {
154    const cases: Array<[string, string]> = [
155      ["a", "b"],
156      ["a0", "b0"],
157      ["a", "a0i"],
158      ["a0", "a1"],
159      ["az", "b"],
160      ["a", "zzzz"],
161      ["9", "a"],
162    ];
163    for (const [a, b] of cases) {
164      const mid = betweenPosition(a, b);
165      expect(isValidPosition(mid)).toBe(true);
166      expect(comparePositions(a, mid)).toBe(-1);
167      expect(comparePositions(mid, b)).toBe(-1);
168    }
169  });
170 
171  it("result stays strictly inside the gap (property)", () => {
172    fc.assert(
173      fc.property(orderedPairArb, ([a, b]) => {
174        const mid = betweenPosition(a, b);
175        expect(isValidPosition(mid)).toBe(true);
176        expect(comparePositions(a, mid)).toBe(-1);
177        expect(comparePositions(mid, b)).toBe(-1);
178      }),
179      { numRuns: 500 },
180    );
181  });
182 
183  it("result is shorter than or near the inputs (bounded growth)", () => {
184    fc.assert(
185      fc.property(orderedPairArb, ([a, b]) => {
186        const mid = betweenPosition(a, b);
187        expect(mid.length).toBeLessThanOrEqual(Math.max(a.length, b.length) + 1);
188      }),
189      { numRuns: 500 },
190    );
191  });
192 
193  it("repeated halving 100× stays valid until rebalance is needed", () => {
194    // Alternate halving from both ends of the gap (the strategy the API uses
195    // when many blocks are inserted between the same two neighbors). Each
196    // halving adds ≤1 char, so 100 halvings stay far under the 64-char
197    // rebalance bound.
198    let lo = "0";
199    let hi = "z";
200    const positions: string[] = [lo, hi];
201    let halvings = 0;
202 
203    for (let step = 0; step < 100; step++) {
204      if (needsRebalance(positions)) break;
205      const mid = betweenPosition(lo, hi);
206      positions.push(mid);
207      expect(isValidPosition(mid)).toBe(true);
208      expect(comparePositions(lo, mid)).toBe(-1);
209      expect(comparePositions(mid, hi)).toBe(-1);
210      // Alternate which side we descend into.
211      if (step % 2 === 0) hi = mid;
212      else lo = mid;
213      halvings++;
214    }
215 
216    // All 100 halvings succeed — lengths stay far below the hard bound.
217    expect(halvings).toBe(100);
218    expect(positions.every((p) => p.length <= LIMITS.MAX_POSITION_LENGTH)).toBe(true);
219    expect(Math.max(...positions.map((p) => p.length))).toBeLessThanOrEqual(32);
220  });
221 
222  it("single-side descent halts at the empty gap (rebalance signal)", () => {
223    // Repeatedly halving only the upper half of (a0, b0) eventually reaches
224    // the immediate-successor gap ("x", "x0"), where the engine must refuse
225    // — that is the signal for rebalancePositions.
226    const lo = "a0";
227    let hi = "b0";
228    const positions = [lo, hi];
229    let steps = 0;
230    for (let step = 0; step < 50; step++) {
231      if (needsRebalance(positions)) break;
232      let mid: string;
233      try {
234        mid = betweenPosition(lo, hi);
235      } catch {
236        break; // empty gap reached
237      }
238      positions.push(mid);
239      hi = mid;
240      steps++;
241    }
242    expect(steps).toBeGreaterThan(5);
243    expect(positions.every((p) => p.length <= LIMITS.MAX_POSITION_LENGTH)).toBe(true);
244    // After a rebalance the same list is short again.
245    const mapping = rebalancePositions(positions);
246    for (const next of Object.values(mapping)) {
247      expect(next.length).toBeLessThanOrEqual(4);
248    }
249  });
250 
251  it("throws when the result would exceed max length", () => {
252    // a and b are both at the max length (64); splitting the adjacent
253    // "a…z" / "b…0" gap needs a 65-char result → the engine refuses.
254    const a = "a" + "z".repeat(LIMITS.MAX_POSITION_LENGTH - 1);
255    const b = "b" + "0".repeat(LIMITS.MAX_POSITION_LENGTH - 1);
256    expect(isValidPosition(a)).toBe(true);
257    expect(isValidPosition(b)).toBe(true);
258    expect(() => betweenPosition(a, b)).toThrow(/max length/);
259  });
260});
261 
262describe("needsRebalance / rebalancePositions", () => {
263  it("needsRebalance is false for short positions", () => {
264    expect(needsRebalance(["a0", "a1", "az", "b0"])).toBe(false);
265  });
266 
267  it("needsRebalance is true once any position exceeds 64 chars", () => {
268    expect(needsRebalance(["a0", "a".repeat(65)])).toBe(true);
269  });
270 
271  it("rebalance restores short positions while preserving order", () => {
272    // Build a long list of positions by inserting midpoints repeatedly
273    // (stop when the one-sided descent reaches the empty gap — exactly the
274    // situation where a rebalance is needed).
275    const positions: string[] = [];
276    // A distinct ascending chain (generatePosition() with no arg always
277    // returns "a0" — five of those would be duplicates and rebalance rejects
278    // them; chain the cursor so each step is strictly greater).
279    let cursor: string | undefined;
280    for (let i = 0; i < 5; i++) {
281      cursor = generatePosition(cursor);
282      positions.push(cursor);
283    }
284    const lo = "c0";
285    let hi = "d0";
286    while (positions.length < 40) {
287      if (needsRebalance([lo, hi])) break;
288      let mid: string;
289      try {
290        mid = betweenPosition(lo, hi);
291      } catch {
292        break; // empty gap — rebalance time
293      }
294      positions.push(mid);
295      hi = mid;
296    }
297    const mapping = rebalancePositions(positions);
298 
299    // One entry per distinct old position.
300    expect(Object.keys(mapping).length).toBe(new Set(positions).size);
301 
302    // New positions are short.
303    for (const next of Object.values(mapping)) {
304      expect(next.length).toBeLessThanOrEqual(4);
305      expect(isValidPosition(next)).toBe(true);
306    }
307 
308    // Order preserved: sorting old positions and mapping keeps the order.
309    const oldSorted = sortPositions(positions);
310    const newSorted = oldSorted.map((p) => mapping[p] as string);
311    expect(newSorted).toEqual([...newSorted].sort());
312  });
313 
314  it("fixed-width encoding keeps lex order == slot order (no a10<aa bug)", () => {
315    const n = 100; // width 2 (36 slots per width-1)
316    const olds = Array.from({ length: n }, (_, i) =>
317      generatePosition(`s${String(i).padStart(3, "0")}`),
318    );
319    const mapping = rebalancePositions(olds);
320    const values = sortPositions(olds).map((p) => mapping[p] as string);
321    expect(values).toEqual([...values].sort());
322    expect(new Set(values).size).toBe(n);
323    for (const v of values) expect(v.length).toBeLessThanOrEqual(3);
324  });
325 
326  it("rejects duplicates and invalid positions", () => {
327    expect(() => rebalancePositions(["a0", "a0"])).toThrow(/duplicate/);
328    expect(() => rebalancePositions(["A0"])).toThrow(RangeError);
329  });
330});
331 
332describe("positionForSlotNeighbors", () => {
333  it("midpoint when both neighbors are given", () => {
334    const p = positionForSlotNeighbors("a0", "b0");
335    expect(comparePositions("a0", p)).toBe(-1);
336    expect(comparePositions(p, "b0")).toBe(-1);
337  });
338 
339  it("appends after `before` only", () => {
340    const p = positionForSlotNeighbors("az", null);
341    expect(comparePositions("az", p)).toBe(-1);
342  });
343 
344  it("prepends before `after` only", () => {
345    const p = positionForSlotNeighbors(null, "a5");
346    expect(comparePositions(p, "a5")).toBe(-1);
347  });
348 
349  it("fresh position when neither", () => {
350    expect(positionForSlotNeighbors(null, null)).toBe("a0");
351  });
352});
353