logigate/tests/routing.test.ts

271 lines
9.9 KiB
TypeScript
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

import { describe, expect, it } from 'vitest'
import { shapeOf, type Pt } from '../app/lib/logic/geometry'
import { createProject, lookup } from '../app/lib/logic/ops'
import { circuitRoutes, findCrossings, planHops, routeAll, WIRE_H, type Box, type Routed } from '../app/lib/logic/routing'
/** Every pair of segments from different nets that lie on the same line and overlap. */
function overlaps(routes: Routed[]) {
const segs: { net: string; h: boolean; c: number; lo: number; hi: number }[] = []
for (const r of routes) {
for (let i = 0; i < r.draw.length - 1; i++) {
const [ax, ay] = r.draw[i]!
const [bx, by] = r.draw[i + 1]!
if (ax === bx && ay === by) continue
const h = ay === by
segs.push({ net: r.net, h, c: h ? ay : ax, lo: h ? Math.min(ax, bx) : Math.min(ay, by), hi: h ? Math.max(ax, bx) : Math.max(ay, by) })
}
}
const bad: string[] = []
for (let i = 0; i < segs.length; i++) {
for (let j = i + 1; j < segs.length; j++) {
const p = segs[i]!
const q = segs[j]!
if (p.net === q.net || p.h !== q.h || Math.abs(p.c - q.c) > 1e-9) continue
if (Math.min(p.hi, q.hi) - Math.max(p.lo, q.lo) > 1e-9) bad.push(`${p.net} / ${q.net} on ${p.h ? 'row' : 'column'} ${p.c}`)
}
}
return bad
}
const square = (r: Routed) => r.draw.every((p, i) => i === 0 || p[0] === r.draw[i - 1]![0] || p[1] === r.draw[i - 1]![1])
describe('routing', () => {
const p = createProject({ examples: true })
const get = lookup(p)
for (const def of p.components) {
it(`${def.name}: no two signals share a line, every wire stays square and ends on its pins`, () => {
const shapes = new Map(def.nodes.map(n => [n.id, shapeOf(n, get)]))
const routes = circuitRoutes(def, shapes)
expect(routes).toHaveLength(def.wires.length)
expect(overlaps(routes)).toEqual([])
for (const r of routes) {
expect(square(r), r.id).toBe(true)
expect(r.draw[0]).toEqual(r.grid[0])
expect(r.draw.at(-1)).toEqual(r.grid.at(-1))
expect(r.grid.every(([x, y]) => Number.isInteger(x) && Number.isInteger(y))).toBe(true)
}
})
}
it('moves an auto-routed wire off a line another signal already uses', () => {
// Two wires from different sources whose usual vertical step would share column 5.
const routes = routeAll(
[
{ id: 'a', net: 'n1', a: [0, 0], b: [10, 6] },
{ id: 'b', net: 'n2', a: [0, 2], b: [10, 8] },
],
[],
[],
)
expect(overlaps(routes)).toEqual([])
expect(routes[0]!.grid).toEqual([[0, 0], [5, 0], [5, 6], [10, 6]])
expect(routes[1]!.grid[1]![0]).not.toBe(5)
})
it('keeps hand-placed corners and draws a clashing wire on its own lane', () => {
const routes = routeAll(
[
{ id: 'a', net: 'n1', a: [0, 0], b: [10, 0], pts: [[2, 0], [2, 4], [8, 4], [8, 0]] },
{ id: 'b', net: 'n2', a: [0, 4], b: [10, 4], pts: [[1, 4], [9, 4]] },
],
[],
[],
)
expect(routes[0]!.grid).toEqual([[0, 0], [2, 0], [2, 4], [8, 4], [8, 0], [10, 0]])
expect(overlaps(routes)).toEqual([])
expect(routes.every(square)).toBe(true)
})
it('lets wires of the same signal share a line', () => {
const routes = routeAll(
[
{ id: 'a', net: 'n1', a: [0, 0], b: [10, 6] },
{ id: 'b', net: 'n1', a: [0, 0], b: [10, 8] },
],
[],
[],
)
expect(routes[0]!.draw).toEqual(routes[0]!.grid)
expect(routes[1]!.draw).toEqual(routes[1]!.grid)
})
it('finds crossings between different signals only', () => {
const routes = routeAll(
[
{ id: 'h', net: 'n1', a: [0, 3], b: [10, 3] },
{ id: 'v', net: 'n2', a: [5, 0], b: [6, 8], pts: [[5, 0], [5, 8]] },
{ id: 'v2', net: 'n1', a: [0, 3], b: [8, 9], pts: [[7, 3], [7, 9]] },
],
[],
[],
)
const c = findCrossings(routes)
// v2 shares h's line (same signal), so it hops over v as well; nothing hops over its own signal.
expect(c.map(x => [routes[x.wire]!.id, x.x])).toEqual([['h', 5], ['v2', 5]])
})
})
describe('tidy routing', () => {
// An adder's outputs S0..S3 (rows 0..3) to output pins Y0..Y3 placed higher
// up (rows -4, -2, 0, 2), so Y3 sits level with S2. Reported after "Tidy all wires".
const inputs = [0, 1, 2, 3].map(i => ({ id: `w${i}`, net: `S${i}`, a: [0, i] as Pt, b: [14, -4 + 2 * i] as Pt }))
it('steps the wires in source order and never lays one on another signal’s row', () => {
const routes = routeAll(inputs, [], [], { tidy: true })
expect(overlaps(routes)).toEqual([])
// Drawn exactly as routed: nothing had to be moved onto a side lane.
for (const r of routes) expect(r.draw).toEqual(r.grid)
const cols = routes.map(r => r.grid[1]![0])
expect(cols).toEqual([...cols].sort((a, b) => a - b))
expect(new Set(cols).size).toBe(4)
})
})
describe('tidy routing on every example', () => {
const p = createProject({ examples: true })
const get = lookup(p)
for (const def of p.components) {
it(`${def.name}: tidy wiring keeps every signal on its own lines`, () => {
const shapes = new Map(def.nodes.map(n => [n.id, shapeOf(n, get)]))
const routes = circuitRoutes({ ...def, wires: def.wires.map(w => ({ ...w, pts: undefined })) }, shapes, { tidy: true })
expect(overlaps(routes)).toEqual([])
})
}
})
/** Segments of a route that run through the inside of a part (its edges, where pins sit, are fine). */
function throughParts(r: Routed, boxes: Box[]): number {
let n = 0
for (let i = 0; i < r.grid.length - 1; i++) {
const [ax, ay] = r.grid[i]!
const [bx, by] = r.grid[i + 1]!
const lx = Math.min(ax, bx)
const hx = Math.max(ax, bx)
const ly = Math.min(ay, by)
const hy = Math.max(ay, by)
for (const b of boxes) {
const hit = ly === hy ? ly > b.y && ly < b.y + b.h && hx > b.x && lx < b.x + b.w : lx > b.x && lx < b.x + b.w && hy > b.y && ly < b.y + b.h
if (hit) n++
}
}
return n
}
describe('lines and parts', () => {
const p = createProject({ examples: true })
const get = lookup(p)
for (const tidy of [false, true]) {
it(`no wire runs over or under a part, on any example${tidy ? ' (tidy)' : ''}`, () => {
for (const def of p.components) {
const shapes = new Map(def.nodes.map(n => [n.id, shapeOf(n, get)]))
const boxes = def.nodes.filter(n => n.kind !== 'note').map(n => {
const b = shapes.get(n.id)!.body
return { x: n.x + b.x, y: n.y + b.y, w: b.w, h: b.h }
})
const routes = circuitRoutes({ ...def, wires: def.wires.map(w => ({ ...w, pts: undefined })) }, shapes, { tidy })
for (const r of routes) expect(throughParts(r, boxes), `${def.name}: ${r.id}`).toBe(0)
}
})
}
it('goes around a part in the way, keeping off its edges', () => {
const part = { x: 4, y: -3, w: 4, h: 6 }
const [r] = routeAll([{ id: 'w', net: 'n', a: [0, 0], b: [14, 0] }], [part], [])
expect(throughParts(r!, [part])).toBe(0)
// Not along the part's top or bottom edge either.
expect(r!.grid.some(([, y]) => y === -3 || y === 3)).toBe(false)
})
it('finds a way around a whole wall of parts', () => {
const wall = [-12, -6, 0, 6].map(y => ({ x: 5, y, w: 3, h: 6 }))
const [r] = routeAll([{ id: 'w', net: 'n', a: [0, 1], b: [14, 1] }], wall, [])
expect(throughParts(r!, wall)).toBe(0)
expect(r!.grid.at(-1)).toEqual([14, 1])
})
})
describe('cables', () => {
const CABLE = 0.47 // half the width of a 4-wire ribbon, in grid units
it('keeps two cables of different signals a column apart, where wires could sit side by side', () => {
// Both want column 5 for their vertical step.
const ends = (h?: number) =>
routeAll(
[
{ id: 'c1', net: 'n1', a: [0, 0], b: [10, 6], h },
{ id: 'c2', net: 'n2', a: [0, 2], b: [10, 8], h },
],
[],
[],
).map(r => r.grid[1]![0])
const [w1, w2] = ends()
expect(Math.abs(w2! - w1!)).toBe(1)
const [c1, c2] = ends(CABLE)
expect(Math.abs(c2! - c1!)).toBeGreaterThanOrEqual(2)
})
it('a second cable of one signal branches off the first, like a wire', () => {
const routes = routeAll(
[
{ id: 'c1', net: 'bus', a: [0, 0], b: [12, 8], h: CABLE },
{ id: 'c2', net: 'bus', a: [0, 0], b: [20, 10], h: CABLE },
],
[],
[],
)
const [first, second] = routes.map(r => r.grid)
// On its own it would turn at column 10; it follows the first down column 6 instead.
expect(first!.slice(0, 3)).toEqual([[0, 0], [6, 0], [6, 8]])
expect(second!.slice(0, 3)).toEqual(first!.slice(0, 3))
expect(second!.at(-1)).toEqual([20, 10])
})
})
describe('hops', () => {
const H = 0.47
it('a wire jumps over a cable, as wide as the cable', () => {
const routes = routeAll(
[
{ id: 'cable', net: 'c', a: [5, -6], b: [6, 6], pts: [[5, -6], [5, 6]], h: H },
{ id: 'wire', net: 'w', a: [0, 0], b: [10, 0] },
],
[],
[],
)
const hops = planHops(routes)
expect(hops.has(0)).toBe(false)
const [hop] = [...hops.get(1)!.values()][0]!
expect(hop!.hi - hop!.lo).toBeGreaterThanOrEqual(2 * (H + WIRE_H))
})
it('a vertical wire jumps sideways over a horizontal cable', () => {
const routes = routeAll(
[
{ id: 'cable', net: 'c', a: [0, 0], b: [10, 0], h: H },
{ id: 'wire', net: 'w', a: [5, -6], b: [6, 6], pts: [[5, -6], [5, 6]] },
],
[],
[],
)
const hops = planHops(routes)
expect(hops.has(0)).toBe(false)
expect(hops.get(1)?.size).toBe(1)
})
it('two plain wires: the horizontal one hops; nothing hops over its own signal', () => {
const routes = routeAll(
[
{ id: 'h', net: 'n1', a: [0, 3], b: [10, 3] },
{ id: 'v', net: 'n2', a: [5, 0], b: [6, 8], pts: [[5, 0], [5, 8]] },
{ id: 'v2', net: 'n1', a: [0, 3], b: [8, 9], pts: [[7, 3], [7, 9]] },
],
[],
[],
)
const hops = planHops(routes)
expect([...hops.keys()].map(k => routes[k]!.id).sort()).toEqual(['h', 'v2'])
})
})