1// The conformance suite: the properties every cell system must keep.2//3// Issue #5 §5.4 asks for "an executable property suite; a third system (H3,4// MGRS, a game's district grid) is a registry entry plus a green run". This is5// that suite. It is deliberately made of *properties* rather than examples —6// an example says what one cell did, a property says what the contract is —7// and it is run over geohash, over S2, and over an example third system that8// exists only to prove the contract holds nothing geohash-shaped.9//10// What the suite does NOT assert, and why, because a property suite is only11// honest if its silences are written down:12//13// Winding. A ring's signed area may be either sign. The antimeridian14// unwrap can reverse it for a loop that circles a pole, and15// nothing downstream reads the direction. Non-degeneracy is16// asserted; orientation is not.17// A hard floor. `descendTarget` at maxLevel answers "" in S2 and keeps18// halving in geohash. The systems disagree and the recorded19// behaviour is frozen, so what is asserted is that descent20// *terminates* — the telescope reaches maxLevel in maxLevel21// hops — not what it says once it is there. See22// docs/analysis.md, "the floor asymmetry".23// Boundary probes. "Boundaries are inclusive" is checkable only where a24// system's geometry puts a point exactly on a boundary. A25// rectangle's corner is such a point; an S2 vertex is not,26// because S2 decides containment on a leaf lattice far finer27// than the degrees a vertex round-trips through. Each subject28// declares its own boundary probes, and a subject with none29// says so out loud.3031import assert from "node:assert/strict";32import { describe, it } from "node:test";3334import type { CellID, CellSystem, GroundedCellSystem } from "../cellsystems/contract.ts";35import type { Coordinate, Extent, Ground } from "../cellsystems/ground.ts";36import { surfaceExtent, surfaceWidth } from "../cellsystems/ground.ts";37import { cellPlan } from "../cellsystems/plan.ts";38import { gridCellVisual } from "../cellsystems/visual.ts";39import { ringClosesOn } from "../cellsystems/ring.ts";40import { palette } from "../cellsystems/tokens.ts";4142/** One system on one ground, plus the two things only its author knows. */43export interface ConformanceSubject {44 readonly system: CellSystem;45 readonly ground: Ground;4647 /** A point well inside the ground, used to drive descent. */48 readonly probe: Coordinate;4950 /**51 * What the root's bbox must be, when it is not `surfaceExtent(ground)`:52 * geohash on a plane divides the world square rather than the lens's53 * window, and on an earth-anchored plane the root is the union of the54 * base cells the window intersects. Omitted, the surface is the ground.55 */56 readonly rootExtent?: Extent;5758 /**59 * Points this system's own geometry puts exactly on a cell boundary, as60 * `[cellID, point]` pairs the cell must contain. A system whose containment61 * is decided on a lattice finer than its geometry declares an empty list and62 * explains itself in a comment.63 */64 readonly boundaryProbes: readonly (readonly [CellID, Coordinate])[];65}6667/** The full property suite, as node:test cases. */68export function describeConformance(name: string, subject: ConformanceSubject): void {69 const { system, ground, probe } = subject;70 describe(`conformance: ${name}`, () => {71 const on = system.on(ground);72 const floor = system.maxLevel(ground);73 const sample = sampleCells(on, probe, floor);7475 // --- applicability ---------------------------------------------------7677 it("applies to the ground it is being conformance-tested on", () => {78 assert.equal(system.appliesTo(ground), true);79 assert.ok(floor >= 1, "a system that divides nothing is not a system");80 assert.ok(system.inputLength(ground) >= 1, "the navigator must accept something");81 assert.ok(system.slug.length > 0 && system.name.length > 0 && system.short.length > 0);82 });8384 // --- identity --------------------------------------------------------8586 it("the root is level 0 and its own parent", () => {87 assert.equal(on.level(""), 0, 'the root "" is level 0');88 assert.equal(on.parent(""), "", "there is nothing above the root");89 });9091 it("ids are opaque strings the system alone takes apart", () => {92 for (const id of sample.cells) {93 assert.equal(typeof id, "string");94 const { context, principal } = on.label(id);95 assert.equal(typeof context, "string");96 assert.equal(typeof principal, "string");97 }98 });99100 it("every cell's accent is a palette index, and siblings differ", () => {101 for (const parent of sample.parents) {102 const keys = on.children(parent).map((id) => on.colorKey(id));103 for (const key of keys) {104 assert.ok(Number.isInteger(key) && key >= 0 && key < palette.length,105 `colorKey ${key} is not an index into a ${palette.length}-colour wheel`);106 }107 const neighbours = keys.slice(0, palette.length);108 assert.equal(new Set(neighbours).size, neighbours.length,109 "cells drawn side by side must not share an accent");110 }111 });112113 // --- hierarchy -------------------------------------------------------114115 it("children answer in a stable order, and the ordinal is that order", () => {116 for (const parent of sample.parents) {117 const once = on.children(parent);118 const twice = on.children(parent);119 assert.deepEqual(twice, once, "children() is not allowed to shuffle");120 assert.ok(once.length >= 2, "a level that does not divide is not a level");121 assert.equal(new Set(once).size, once.length, "a child appears once");122 once.forEach((id, at) => {123 assert.equal(on.childIndex(id), at,124 `${id} is child ${at} of ${parent || "the root"} but calls itself ${on.childIndex(id)}`);125 });126 }127 });128129 it("parent and children are inverse, and level counts the hops", () => {130 for (const parent of sample.parents) {131 const level = on.level(parent);132 for (const id of on.children(parent)) {133 assert.equal(on.parent(id), parent, `${id} does not lead back to ${parent || "the root"}`);134 assert.equal(on.level(id), level + 1, `${id} is not one level below its parent`);135 }136 }137 });138139 it("the ancestor chain of every sampled cell reaches the root", () => {140 for (const id of sample.cells) {141 let held = id;142 let hops = 0;143 while (held !== "" && hops <= floor + 1) {144 held = on.parent(held);145 hops++;146 }147 assert.equal(held, "", `${id} does not climb back to the root`);148 assert.equal(hops, on.level(id), `${id} claims a level its chain does not walk`);149 }150 });151152 // --- containment -----------------------------------------------------153154 it("a cell contains its own centre, and its parent contains it too", () => {155 for (const id of sample.cells) {156 if (id === "") continue;157 const centre = on.center(id);158 assert.equal(on.contains(id, centre), true, `${id} does not contain its own centre`);159 assert.equal(on.contains(on.parent(id), centre), true,160 `${on.parent(id) || "the root"} does not contain ${id}'s centre`);161 }162 });163164 it("descent agrees with containment", () => {165 for (const parent of sample.parents) {166 for (const id of on.children(parent)) {167 const centre = on.center(id);168 assert.equal(on.descendTarget(parent, centre), id,169 `descending into ${parent || "the root"} at ${id}'s centre missed it`);170 assert.equal(on.contains(id, centre), true);171 }172 }173 });174175 it("boundaries are inclusive", () => {176 if (subject.boundaryProbes.length === 0) {177 // Declared empty: see the note at the top of this file.178 return;179 }180 for (const [id, at] of subject.boundaryProbes) {181 assert.equal(on.contains(id, at), true,182 `${id} excludes ${JSON.stringify(at)}, which sits on its own boundary`);183 }184 });185186 it("the telescope terminates at maxLevel", () => {187 let id = "";188 for (let hop = 0; hop < floor; hop++) {189 const next = on.descendTarget(id, probe);190 assert.ok(next, `descent stopped at level ${hop}, above the floor of ${floor}`);191 assert.equal(on.level(next), hop + 1, "a descent hop must be exactly one level");192 assert.equal(on.contains(next, probe), true);193 id = next;194 }195 assert.equal(on.level(id), floor, "descending maxLevel times lands on maxLevel");196 });197198 it("locate names the point in this system's own address", () => {199 const row = on.locate(probe);200 assert.ok(row, "a point on the ground has an address");201 assert.ok(row.label.length > 0, "the row is named for the pin card");202 assert.ok(row.value.length > 0);203 });204205 // --- geometry --------------------------------------------------------206207 it("rings close, on the same row, some whole number of worlds over", () => {208 for (const id of sample.geometric) {209 const ring = on.ring(id);210 assert.ok(ring.length >= 4, `${id}'s ring is not a loop`);211 assert.ok(ringClosesOn(ground, ring),212 `${id}'s ring does not close: ${JSON.stringify(ring[0])} → ` +213 `${JSON.stringify(ring[ring.length - 1])}`);214 }215 });216217 // Half a world is the unwrap's own threshold, and it is a bound rather218 // than a strict one on purpose: a cell touching a pole sweeps exactly half219 // the world of longitude in one tessellation step, which is ground and not220 // a seam. Anything past half is the seam, and the ring runs off the surface221 // instead of wrapping — that is the continuity rule, and cellRings() is222 // what cuts the result.223 it("rings stay continuous: no point ever jumps the seam", () => {224 const half = surfaceWidth(ground) / 2;225 for (const id of sample.geometric) {226 const ring = on.ring(id);227 for (let at = 1; at < ring.length; at++) {228 const current = ring[at];229 const previous = ring[at - 1];230 assert.ok(current && previous);231 assert.ok(Math.abs(current[0] - previous[0]) <= half,232 `${id}'s ring jumps ${Math.abs(current[0] - previous[0])} in x at step ${at}: ` +233 "a ring runs off the surface rather than wrapping, and the adapters cut it");234 }235 }236 });237238 it("rings enclose real ground", () => {239 for (const id of sample.geometric) {240 assert.notEqual(signedArea(on.ring(id)), 0, `${id}'s ring encloses nothing`);241 }242 });243244 it("the bbox is the ring's own bounding box", () => {245 for (const id of sample.geometric) {246 const ring = on.ring(id);247 const xs = ring.map((point) => point[0]);248 const ys = ring.map((point) => point[1]);249 const [minimumX, minimumY, maximumX, maximumY] = on.bbox(id);250 assert.ok(minimumX <= Math.min(...xs) + 1e-9 && maximumX >= Math.max(...xs) - 1e-9,251 `${id}'s bbox does not span its own ring in x`);252 assert.ok(minimumY <= Math.min(...ys) + 1e-9 && maximumY >= Math.max(...ys) - 1e-9,253 `${id}'s bbox does not span its own ring in y`);254 }255 });256257 it("the root's bbox is the ground this system divides", () => {258 assert.deepEqual([...on.bbox("")], [...(subject.rootExtent ?? surfaceExtent(ground))]);259 });260261 it("a cell circles at most one pole, and its parent circles the same one", () => {262 for (const id of sample.cells) {263 if (id === "") continue;264 const pole = on.poleContained(id);265 assert.ok(pole === null || pole === "north" || pole === "south");266 if (pole !== null && on.parent(id) !== "") {267 assert.equal(on.poleContained(on.parent(id)), pole,268 `${id} circles the ${pole} pole but ${on.parent(id) || "the root"} does not`);269 }270 }271 for (const parent of sample.parents) {272 // The root is not a cell: it is the whole ground, and a ground with273 // both poles on it cannot answer with one of them.274 if (parent === "") continue;275 for (const pole of ["north", "south"] as const) {276 const claimants = on.children(parent).filter((id) => on.poleContained(id) === pole);277 assert.ok(claimants.length <= 1,278 `${claimants.length} children of ${parent || "the root"} claim the ${pole} pole`);279 }280 }281 });282283 // --- input -----------------------------------------------------------284285 it("normalizing is idempotent", () => {286 const drafts = ["", " ", "!!", ...sample.cells, ...sample.cells.map((id) => id.toUpperCase())];287 for (const draft of drafts) {288 const once = on.normalizeInput(draft);289 assert.equal(on.normalizeInput(once), once, `normalizing "${draft}" twice moved it`);290 }291 });292293 it("parsing is whole or nothing, and never lengthens the address", () => {294 for (const draft of ["", "!", "zzzzzzzzzzzz", "0".repeat(40)]) {295 const parsed = on.parseInput(on.normalizeInput(draft));296 if (parsed === null) continue;297 assert.equal(on.parseInput(parsed), parsed, "a parsed id must parse to itself");298 assert.ok(on.level(parsed) <= floor,299 `parsing "${draft}" answered a cell below the telescope's floor`);300 }301 });302303 it("every holdable id survives the navigator unchanged", () => {304 for (const id of sample.cells) {305 if (on.level(id) > floor) continue;306 assert.equal(on.normalizeInput(id), id, `the field would not keep "${id}"`);307 assert.equal(on.parseInput(id), id, `"${id}" does not parse back to itself`);308 }309 });310311 // --- the plan --------------------------------------------------------312313 it("a plan is deterministic and emits in the frozen order", () => {314 for (const held of sample.held) {315 const once = cellPlan(ground, system, held);316 const twice = cellPlan(ground, system, held);317 assert.deepEqual(twice, once, `the plan for "${held}" is not deterministic`);318 assertPlanOrder(on, floor, held, once);319 }320 });321322 it("style tokens are pure, and a hidden subdivision draws nothing", () => {323 for (const held of sample.held.slice(0, 2)) {324 const plan = cellPlan(ground, system, held);325 for (const cell of plan) {326 for (const subgridVisible of [true, false]) {327 for (const labelled of [true, false]) {328 const options = { subgridVisible, labelled };329 const tokens = gridCellVisual(ground, system, cell, options);330 assert.deepEqual(gridCellVisual(ground, system, cell, options), tokens,331 "the same cell and the same questions must answer the same tokens");332 if (cell.role === "child" && (!subgridVisible || !labelled)) {333 assert.equal(tokens, null, "a child that cannot be read draws nothing at all");334 continue;335 }336 assert.ok(tokens, `${cell.hash} as ${cell.role} draws nothing`);337 assert.ok(tokens.line.widthPx > 0);338 assert.equal(tokens.bare, cell.role === "scope" && subgridVisible);339 assert.equal(tokens.label === null, !labelled || tokens.bare);340 }341 }342 }343 }344 });345346 it("every plan cell carries a closed ring and its own extent", () => {347 for (const held of sample.held) {348 for (const cell of cellPlan(ground, system, held)) {349 assert.ok(ringClosesOn(ground, cell.ring), `${cell.hash} was planned with an open ring`);350 assert.equal(cell.extent.length, 4);351 assert.ok(cell.childIndex >= 0);352 assert.ok(cell.contextDistance >= 0);353 }354 }355 });356 });357}358359/**360 * The plan's emission order, asserted rather than described: the ancestors'361 * neighbours from the root down, then either the held cell as a leaf and362 * nothing after it, or the held cell as a scope followed by its children.363 */364function assertPlanOrder(365 on: GroundedCellSystem,366 floor: number,367 held: CellID,368 plan: readonly { hash: CellID; role: string; contextDistance: number }[],369): void {370 const expected: { hash: CellID; role: string; contextDistance: number }[] = [];371 const chain: CellID[] = [held];372 for (let id = held; id !== ""; ) {373 id = on.parent(id);374 chain.unshift(id);375 }376 for (let depth = 0; depth < chain.length - 1; depth++) {377 const here = chain[depth];378 const selected = chain[depth + 1];379 if (here === undefined || selected === undefined) continue;380 for (const id of on.children(here)) {381 if (id === selected) continue;382 expected.push({ hash: id, role: "neighbor", contextDistance: chain.length - 1 - depth });383 }384 }385 if (held && on.level(held) >= floor) {386 expected.push({ hash: held, role: "leaf", contextDistance: 0 });387 } else {388 if (held) expected.push({ hash: held, role: "scope", contextDistance: 0 });389 for (const id of on.children(held)) {390 expected.push({ hash: id, role: "child", contextDistance: 0 });391 }392 }393 assert.deepEqual(394 plan.map((cell) => ({ hash: cell.hash, role: cell.role, contextDistance: cell.contextDistance })),395 expected,396 `the plan for "${held}" is not in emission order`,397 );398}399400interface Sample {401 /** Every cell the run touches: the descent chain and all its siblings. */402 readonly cells: CellID[];403 /** Cells whose children are exercised as a set. */404 readonly parents: CellID[];405 /** Cells whose ring and bbox are checked — the root has neither. */406 readonly geometric: CellID[];407 /** Held cells to plan from: the root, two depths, and the floor. */408 readonly held: CellID[];409}410411/** The cells one run exercises: enough to be a property, few enough to be a test. */412function sampleCells(on: GroundedCellSystem, probe: Coordinate, floor: number): Sample {413 const chain: CellID[] = [""];414 for (let hop = 0; hop < floor; hop++) {415 const last = chain[chain.length - 1];416 if (last === undefined) break;417 const next = on.descendTarget(last, probe);418 if (!next) break;419 chain.push(next);420 }421 const parents = chain.slice(0, -1);422 const cells = [...new Set([...chain, ...parents.flatMap((id) => on.children(id))])];423 // Ring and bbox work is the expensive half, and no system promises the root424 // a ring — six faces or thirty-two rectangles do not make one loop — so425 // geometry is checked below the root.426 const geometric = cells.filter((id) => id !== "").slice(0, 48);427 const held = [...new Set(428 [0, 1, Math.max(1, Math.floor(floor / 2)), chain.length - 1]429 .map((at) => chain[at])430 .filter((id): id is CellID => id !== undefined),431 )];432 return { cells, parents, geometric, held };433}434435/** Twice the enclosed area, sign and all: zero means the loop encloses nothing. */436function signedArea(ring: readonly Coordinate[]): number {437 let sum = 0;438 for (let at = 0; at < ring.length - 1; at++) {439 const current = ring[at];440 const next = ring[at + 1];441 if (!current || !next) continue;442 sum += current[0] * next[1] - next[0] * current[1];443 }444 return sum;445}