271 lines
9.9 KiB
TypeScript
271 lines
9.9 KiB
TypeScript
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'])
|
||
})
|
||
})
|