logigate/tests/routing.test.ts

136 lines
5.2 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, routeAll, 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([])
})
}
})