language: TypeScript
7.37 KB / 200 lines / 171 loc
import * as fc from "fast-check";
import { expect, test } from "vitest";
import type { Command, CommandOf, OperationContext } from "../src/operations";
import { invokeCommand } from "../src/operations";
import { xform } from "../src/transformation";
import type { PileData } from "../src/types";
type Store = OperationContext["store"];
class FakeContext implements OperationContext {
store: Store;
constructor() {
this.store = {
piles: [] as PileData[],
activePileIndex: 0,
get activePile(): PileData {
return this.piles[this.activePileIndex]!;
},
insertPile(pileIndex: number): void {
this.piles.splice(pileIndex, 0, { name: "", cards: [], pickedCardIndex: 0 });
},
};
}
makeCard(id: number) {
return { id };
}
prettyState() {
return {
// FIXME names diverge after removeEmptyPile x spliceCards
// names: this.store.piles.map(({ name }) => name),
piles: this.store.piles.map(({ cards }) => cards.map(({ id }) => id)),
};
}
}
function runOps(initialPiles: number[][], ...ops: Command[]) {
const ctx = new FakeContext();
for (const [i, cards] of initialPiles.entries()) {
ctx.store.insertPile(i);
ctx.store.piles[i]!.name = `${i}`;
ctx.store.piles[i]!.cards = cards.map((id) => ({ id }));
}
for (const op of ops) invokeCommand(ctx, op);
return ctx;
}
const DEFAULT_PILES = [[], [10, 11, 12], [20, 21, 22], [30]];
test.each([
// All possible 3 pile moves.
{ numPiles: 3, a: [0, 1], b: [0, 1], expected: [1, 0, 2] },
{ numPiles: 3, a: [0, 1], b: [0, 2], expected: [1, 0, 2] }, // or [1, 2, 0]
{ numPiles: 3, a: [0, 1], b: [1, 0], expected: [1, 0, 2] },
{ numPiles: 3, a: [0, 1], b: [1, 2], expected: [0, 2, 1] },
{ numPiles: 3, a: [0, 1], b: [2, 0], expected: [2, 1, 0] },
{ numPiles: 3, a: [0, 1], b: [2, 1], expected: [2, 1, 0] },
{ numPiles: 3, a: [0, 2], b: [0, 2], expected: [1, 2, 0] },
{ numPiles: 3, a: [0, 2], b: [1, 0], expected: [1, 2, 0] },
{ numPiles: 3, a: [0, 2], b: [1, 2], expected: [2, 1, 0] }, // or [2, 0, 1]
{ numPiles: 3, a: [0, 2], b: [2, 0], expected: [2, 1, 0] },
{ numPiles: 3, a: [0, 2], b: [2, 1], expected: [2, 1, 0] },
{ numPiles: 3, a: [1, 0], b: [1, 0], expected: [1, 0, 2] },
{ numPiles: 3, a: [1, 0], b: [1, 2], expected: [1, 0, 2] }, // or [0, 2, 1]
{ numPiles: 3, a: [1, 0], b: [2, 0], expected: [1, 2, 0] }, // or [2, 1, 0]
{ numPiles: 3, a: [1, 0], b: [2, 1], expected: [1, 0, 2] },
{ numPiles: 3, a: [1, 2], b: [1, 2], expected: [0, 2, 1] },
{ numPiles: 3, a: [1, 2], b: [2, 0], expected: [2, 0, 1] },
{ numPiles: 3, a: [1, 2], b: [2, 1], expected: [0, 2, 1] },
{ numPiles: 3, a: [2, 0], b: [2, 0], expected: [2, 0, 1] },
{ numPiles: 3, a: [2, 0], b: [2, 1], expected: [2, 0, 1] }, // or [2, 1, 0]
{ numPiles: 3, a: [2, 1], b: [2, 1], expected: [0, 2, 1] },
] as const)("movePile($a) x movePile($b) #%$ -> $expected", ({ numPiles, a, b, expected }) => {
const opA: Command = ["movePile", ...a];
const opB: Command = ["movePile", ...b];
const initial = Array.from({ length: numPiles }, () => []);
const [aPrime, bPrime] = xform(opA, opB);
const ctxA = runOps(initial, opA, ...bPrime);
const ctxB = runOps(initial, opB, ...aPrime);
const pilesA = ctxA.store.piles.map(({ name }) => parseInt(name));
const pilesB = ctxB.store.piles.map(({ name }) => parseInt(name));
expect(pilesA).toEqual(expected);
expect(pilesB).toEqual(expected);
});
test.each([
{ initial: DEFAULT_PILES, aSrc: [1, 2], aDest: [2, 0], bSrc: [1, 1], bDest: [1, 2] },
{ initial: DEFAULT_PILES, aSrc: [2, 0], aDest: [1, 1], bSrc: [1, 1], bDest: [1, 0] },
{ initial: DEFAULT_PILES, aSrc: [1, 0], aDest: [1, 1], bSrc: [2, 0], bDest: [1, 1] },
{ initial: DEFAULT_PILES, aSrc: [2, 0], aDest: [3, 0], bSrc: [1, 0], bDest: [3, 0] },
] as const)("moveCard($aSrc, $aDest) x moveCard($bSrc, $bDest) #%$", (params) => {
const { initial, aSrc, aDest, bSrc, bDest } = params;
const a: Command = ["moveCard", aSrc, aDest];
const b: Command = ["moveCard", bSrc, bDest];
const [aPrime, bPrime] = xform(a, b);
const ctxA = runOps(initial, a, ...bPrime);
const ctxB = runOps(initial, b, ...aPrime);
expect(ctxA.prettyState()).toEqual(ctxB.prettyState());
});
const moveCardArb: fc.Arbitrary<CommandOf<"moveCard">> = fc
// Map over nat instead of a structural approach to get a uniform sampling.
.tuple(
// Any card can be a source.
fc.nat(DEFAULT_PILES.reduce((acc, xs) => acc + xs.length, 0) - 1),
// We can also move to the end of a pile, but cannot move to the end of
// the same pile or to the source location.
fc.nat(DEFAULT_PILES.reduce((acc, xs) => acc + xs.length + 1, 0) - 3),
)
.map(([srcIters, destIters]) => {
let [srcPile, srcCard] = [0, -1];
for (let i = -1; i < srcIters; i++) {
srcCard++;
while (srcCard >= DEFAULT_PILES[srcPile]!.length) {
srcCard = 0;
srcPile++;
}
}
let [destPile, destCard] = [0, -1];
for (let i = -1; i < destIters; i++) {
do {
destCard++;
while (destCard >= DEFAULT_PILES[destPile]!.length + (srcPile === destPile ? 0 : 1)) {
destCard = 0;
destPile++;
}
} while (srcPile === destPile && srcCard === destCard);
}
return ["moveCard", [srcPile, srcCard], [destPile, destCard]];
});
const createPileArb: fc.Arbitrary<CommandOf<"createPile">> = fc
.nat(DEFAULT_PILES.length)
.map((i) => ["createPile", i]);
const removeEmptyPileArb: fc.Arbitrary<CommandOf<"removeEmptyPile">> = fc
.nat(DEFAULT_PILES.length - 1)
.filter((i) => DEFAULT_PILES[i]!.length === 0)
.map((i) => ["removeEmptyPile", i]);
const movePileArb: fc.Arbitrary<CommandOf<"movePile">> = fc
.tuple(fc.nat(DEFAULT_PILES.length - 1), fc.nat(DEFAULT_PILES.length - 1))
.filter(([src, dest]) => src !== dest)
.map(([src, dest]) => ["movePile", src, dest]);
const namePileArb: fc.Arbitrary<CommandOf<"namePile">> = fc
.record({ pile: fc.nat(DEFAULT_PILES.length - 1), name: fc.string() })
.map(({ pile, name }) => ["namePile", pile, name]);
const spliceCardsArb: fc.Arbitrary<CommandOf<"spliceCards">> = fc
.nat(DEFAULT_PILES.length - 1)
.chain((pileIndex) => {
const size = DEFAULT_PILES[pileIndex]!.length;
return fc.nat(size).chain((cardIndex) => {
return fc.nat(size - cardIndex).chain((deleteCount) => {
return fc
.array(fc.nat(9), { maxLength: 2 })
.map((cardIds) => ["spliceCards", pileIndex, cardIndex, deleteCount, cardIds]);
});
});
});
const commandArbitrariesByName = {
moveCard: { arbitrary: moveCardArb, weight: 2 },
createPile: createPileArb,
removeEmptyPile: removeEmptyPileArb,
movePile: movePileArb,
namePile: namePileArb,
spliceCards: { arbitrary: spliceCardsArb, weight: 2 },
} satisfies { [K in Command[0]]: any };
const commandArb: fc.Arbitrary<Command> = fc.oneof(...Object.values(commandArbitrariesByName));
test("convergence property after crossing xform", () => {
fc.assert(
fc.property(fc.record({ a: commandArb, b: commandArb }), ({ a, b }) => {
const [aPrime, bPrime] = xform(a, b);
// FIXME Not dependent on which op is client or server.
// expect([bPrime, aPrime]).toEqual(xform(b, a));
// TODO check for noops
const ctxA = runOps(DEFAULT_PILES, a, ...bPrime);
const ctxB = runOps(DEFAULT_PILES, b, ...aPrime);
expect(ctxA.prettyState()).toEqual(ctxB.prettyState());
}),
{ numRuns: 1000 },
);
});