ShiboSoftwareDev/i-wan

routing/ThroughViaFanoutAutorouter.ts

import {
	AutoroutingPipelineSolver,
	type Obstacle,
	type SimpleRouteBus,
	type SimpleRouteConnection,
	type SimpleRouteJson,
	type SimplifiedPcbTrace,
} from "@tscircuit/capacity-autorouter";
import { FanoutSolver, type FanoutBusSpec } from "@tscircuit/fanout-solver";

type FanoutDirection = "left" | "right" | "up" | "down";
type Point = { x: number; y: number };
type Bounds = { minX: number; maxX: number; minY: number; maxY: number };
type RoutePoint = SimplifiedPcbTrace["route"][number];
type AutorouterEventMap = {
	complete: { type: "complete"; traces: SimplifiedPcbTrace[] };
	error: { type: "error"; error: Error };
	progress: {
		type: "progress";
		steps: number;
		progress: number;
		phase?: string;
		iterationsPerSecond?: number;
	};
};

const OUTER_LAYERS = ["top", "bottom"] as const;
const FANOUT_PADDING_MM = 1;
const LOCAL_FANOUT_PADDING_MM = 0.5;
const ROUTING_CLEARANCE_MM = 0.15;
const VIA_TO_PAD_ROUTING_CLEARANCE_MM = 0.155;

const getOuterLayerRoutingProblem = (
	input: SimpleRouteJson,
): SimpleRouteJson => ({
	...input,
	// Route with guard-band above the board's 0.10 mm DRC rule.
	// This compensates for the autorouter/core geometry-grid mismatch without
	// changing the physical board constraint or biasing any path/via location.
	defaultObstacleMargin: Math.max(
		input.defaultObstacleMargin ?? 0,
		ROUTING_CLEARANCE_MM,
	),
	minTraceToPadEdgeClearance: Math.max(
		input.minTraceToPadEdgeClearance ?? 0,
		ROUTING_CLEARANCE_MM,
	),
	minViaEdgeToPadEdgeClearance: Math.max(
		input.minViaEdgeToPadEdgeClearance ?? 0,
		VIA_TO_PAD_ROUTING_CLEARANCE_MM,
	),
	// The physical board remains four-layer. Presenting only the two outer
	// copper layers to the routing solvers means every emitted top/bottom
	// transition is interpreted by tscircuit as a full-stack L1-L4 via.
	layerCount: 2,
	buses: input.buses?.map((bus) => ({
		...bus,
		allowedLayers: bus.allowedLayers?.filter((layer) =>
			OUTER_LAYERS.includes(layer as (typeof OUTER_LAYERS)[number]),
		),
	})),
	obstacles: input.obstacles.flatMap((obstacle): Obstacle[] => {
		const layers = OUTER_LAYERS.filter((layer) =>
			obstacle.layers.includes(layer),
		);
		if (layers.length === 0) return [];
		const zLayers = layers.map((layer) => (layer === "top" ? 0 : 1));
		return [{ ...obstacle, layers: [...layers], zLayers, __zLayers: zLayers }];
	}),
});

const getObstacleGroups = (obstacles: Obstacle[]) => {
	const groups = new Map<string, Obstacle[]>();
	for (const obstacle of obstacles) {
		if (!obstacle.componentId) continue;
		const group = groups.get(obstacle.componentId) ?? [];
		group.push(obstacle);
		groups.set(obstacle.componentId, group);
	}
	return groups;
};

const getBounds = (obstacles: Obstacle[]): Bounds => ({
	minX: Math.min(
		...obstacles.map((obstacle) => obstacle.center.x - obstacle.width / 2),
	),
	maxX: Math.max(
		...obstacles.map((obstacle) => obstacle.center.x + obstacle.width / 2),
	),
	minY: Math.min(
		...obstacles.map((obstacle) => obstacle.center.y - obstacle.height / 2),
	),
	maxY: Math.max(
		...obstacles.map((obstacle) => obstacle.center.y + obstacle.height / 2),
	),
});

const expandBounds = (bounds: Bounds, padding: number): Bounds => ({
	minX: bounds.minX - padding,
	maxX: bounds.maxX + padding,
	minY: bounds.minY - padding,
	maxY: bounds.maxY + padding,
});

const pointIsInBounds = (point: Point, bounds: Bounds) =>
	point.x >= bounds.minX &&
	point.x <= bounds.maxX &&
	point.y >= bounds.minY &&
	point.y <= bounds.maxY;

const getOutwardDirection = (point: Point, center: Point): FanoutDirection => {
	const dx = point.x - center.x;
	const dy = point.y - center.y;
	if (Math.abs(dx) >= Math.abs(dy)) return dx < 0 ? "left" : "right";
	return dy < 0 ? "down" : "up";
};

const getQfnSupplyRailTokens = (input: SimpleRouteJson) => {
	const qfnBounds = [...getObstacleGroups(input.obstacles).values()]
		.filter((componentObstacles) => componentObstacles.length >= 20)
		.map(getBounds);
	const supplyRailTokens = new Set<string>();
	for (const connection of input.connections) {
		if (connection.pointsToConnect.length < 2) continue;
		const qfnPadCounts = qfnBounds.map((bounds) => {
			const padLocations = new Set(
				connection.pointsToConnect
					.filter((point) => pointIsInBounds(point, bounds))
					.map((point) => `${point.x.toFixed(6)}:${point.y.toFixed(6)}`),
			);
			return padLocations.size;
		});
		// Supply rails usually feed a small group of QFN supply pads. The ground
		// return has many more package pads and is already handled by the board's
		// inner ground plane, so keep it in the global same-net tree.
		const totalQfnPadCount = qfnPadCounts.reduce(
			(total, padCount) => total + padCount,
			0,
		);
		if (totalQfnPadCount >= 2 && totalQfnPadCount <= 4) {
			supplyRailTokens.add(connection.name);
		}
	}
	return supplyRailTokens;
};

const connectionMatchesNetToken = (
	connection: SimpleRouteConnection,
	netTokens: Set<string>,
) =>
	[
		connection.name,
		connection.rootConnectionName,
		connection.netConnectionName,
		connection.__netConnectionName,
		...(connection.mergedConnectionNames ?? []),
		...(connection.__rootConnectionNames ?? []),
	].some((token) => token !== undefined && netTokens.has(token));

/**
 * Apply one coordinated fanout-solver operation to each QFN-like device. The
 * buses and their directions come entirely from package geometry and
 * connectivity; there are no authored via coordinates, route points, or
 * per-pin direction overrides.
 */
const addQfnFanout = (
	input: SimpleRouteJson,
	supplyRailTokens: Set<string>,
) => {
	let output = input;
	const fanoutPrefixes = new Map<string, SimplifiedPcbTrace>();
	const obstacleGroups = getObstacleGroups(input.obstacles);
	const applyFanout = ({
		componentId,
		candidates,
		sharedBoundary,
		escapeLayers,
		busLabel,
		termination = { type: "boundary" },
	}: {
		componentId: string;
		candidates: Array<{
			direction: FanoutDirection;
			connection: SimpleRouteConnection;
		}>;
		sharedBoundary: Bounds;
		escapeLayers: Array<(typeof OUTER_LAYERS)[number]>;
		busLabel: string;
		termination?: NonNullable<FanoutBusSpec["termination"]>;
	}) => {
		if (candidates.length === 0) return;
		const fanoutConnections = candidates.map(({ connection }) => connection);
		const buses: FanoutBusSpec[] = (["left", "right", "up", "down"] as const)
			.map((direction) => ({
				busId: `${componentId}-${busLabel}-${direction}`,
				connectionNames: candidates
					.filter((candidate) => candidate.direction === direction)
					.map(({ connection }) => connection.name),
				direction,
				termination,
			}))
			.filter((bus) => bus.connectionNames.length > 0);

		const fanoutSolver = new FanoutSolver(
			{
				...output,
				connections: fanoutConnections,
				buses: buses as SimpleRouteBus[],
			},
			{
				buses,
				sourceComponentId: componentId,
				escapeLayers,
				sharedBoundary,
				allowSameNetMerges: true,
				compactBusTracks: true,
				singleLayerPushAndShove: true,
				singleLayerAdaptiveExits: true,
				borderDistribution: "preserve",
			},
		);
		fanoutSolver.solve();
		if (fanoutSolver.failed) {
			throw new Error(
				`Coordinated QFN ${busLabel} fanout failed for ${componentId}: ${fanoutSolver.error}`,
			);
		}

		const fanoutOutput = fanoutSolver.getOutputSimpleRouteJson();
		const priorTraceIds = new Set(
			(output.traces ?? []).map((trace) => trace.pcb_trace_id),
		);
		for (const connection of fanoutConnections) {
			const prefix = fanoutOutput.traces?.find(
				(trace) =>
					trace.connection_name === connection.name &&
					!priorTraceIds.has(trace.pcb_trace_id),
			);
			if (!prefix) {
				throw new Error(
					`Coordinated QFN ${busLabel} fanout did not emit a prefix for ${connection.name}`,
				);
			}
			fanoutPrefixes.set(connection.name, prefix);
		}
		const routedNames = new Set(
			fanoutConnections.map(({ name }) => name),
		);
		const untouchedConnections = output.connections.filter(
			({ name }) => !routedNames.has(name),
		);
		output = {
			...fanoutOutput,
			connections: [...fanoutOutput.connections, ...untouchedConnections],
			buses: output.buses,
		};
	};

	for (const [componentId, componentObstacles] of obstacleGroups) {
		// On this board the two QFNs are the only top-side packages with at least
		// twenty component-tagged copper obstacles. Escape every connected pad on
		// each QFN in one coordinated, geometry-derived operation.
		if (componentObstacles.length < 20) continue;

		const componentBounds = getBounds(componentObstacles);
		const fanoutBounds = expandBounds(componentBounds, FANOUT_PADDING_MM);
		const componentCenter = {
			x: (componentBounds.minX + componentBounds.maxX) / 2,
			y: (componentBounds.minY + componentBounds.maxY) / 2,
		};
		const allCandidates: Array<{
			direction: FanoutDirection;
			connection: SimpleRouteConnection;
			destinationLayer: string;
			isLocal: boolean;
		}> = [];
		const candidatePadLocations = new Set<string>();

		for (const connection of output.connections) {
			// Multi-point nets are collected separately below; this pass handles
			// ordinary point-to-point package connections only.
			if (connection.pointsToConnect.length !== 2) continue;
			const sourcePointIndex = connection.pointsToConnect.findIndex((point) =>
				pointIsInBounds(point, componentBounds),
			);
			if (sourcePointIndex < 0) continue;
			const sourcePoint = connection.pointsToConnect[sourcePointIndex];
			const destinationPoint = connection.pointsToConnect[1 - sourcePointIndex];
			if (!sourcePoint || !destinationPoint) continue;
			const padLocationKey = `${sourcePoint.x.toFixed(6)}:${sourcePoint.y.toFixed(6)}`;
			// A single physical pad may appear in several logical two-point traces.
			// Escape that copper location once; Pipeline 9 keeps the other same-net
			// branches connected to the preloaded trace.
			if (candidatePadLocations.has(padLocationKey)) continue;
			candidatePadLocations.add(padLocationKey);
			const direction = getOutwardDirection(sourcePoint, componentCenter);
			const destinationLayer =
				"layer" in destinationPoint
					? destinationPoint.layer
					: (destinationPoint.layers.find((layer) =>
							OUTER_LAYERS.includes(
								layer as (typeof OUTER_LAYERS)[number],
							),
						) ?? "top");
			allCandidates.push({
				direction,
				connection,
				destinationLayer,
				// A compact secondary escape is useful for the cluster of adjacent
				// bypass parts beside the package's left edge. Other directions
				// retain the wider coordinated boundary, which gives their global
				// continuations more room to meet the preloaded prefix.
				isLocal:
					direction === "left" &&
					destinationLayer === "bottom" &&
					Math.hypot(
						destinationPoint.x - sourcePoint.x,
						destinationPoint.y - sourcePoint.y,
					) <= 3,
			});
		}

		const localFanoutBounds = expandBounds(
			componentBounds,
			LOCAL_FANOUT_PADDING_MM,
		);
		for (const layer of OUTER_LAYERS) {
			applyFanout({
				componentId,
				candidates: allCandidates.filter(
					(candidate) =>
						candidate.isLocal && candidate.destinationLayer === layer,
				),
				sharedBoundary: localFanoutBounds,
				escapeLayers: [layer],
				busLabel: `local-${layer}`,
			});
		}
		// Split a merged QFN supply tree into one solver-owned branch per supply
		// pad. Each branch is escaped to the shared top-layer boundary before the
		// global same-net solver runs, keeping its vias outside the fine-pitch pad
		// field without authoring any route point or via coordinate.
		const supplyCandidates: Array<{
			direction: FanoutDirection;
			connection: SimpleRouteConnection;
		}> = [];
		const rewrittenConnections: SimpleRouteConnection[] = [];
		for (const connection of output.connections) {
			if (!connectionMatchesNetToken(connection, supplyRailTokens)) {
				rewrittenConnections.push(connection);
				continue;
			}
			const componentPoints = connection.pointsToConnect.filter((point) =>
				pointIsInBounds(point, componentBounds),
			);
			if (componentPoints.length === 0) {
				rewrittenConnections.push(connection);
				continue;
			}
			const componentPointSet = new Set(componentPoints);
			const remainingPoints = connection.pointsToConnect.filter(
				(point) => !componentPointSet.has(point),
			);
			const anchorPoint = remainingPoints[0];
			if (!anchorPoint) {
				rewrittenConnections.push(connection);
				continue;
			}
			if (remainingPoints.length >= 2) {
				rewrittenConnections.push({
					...connection,
					pointsToConnect: remainingPoints,
				});
			}
			for (const [pointIndex, point] of componentPoints.entries()) {
				const supplyConnection: SimpleRouteConnection = {
					...connection,
					name: `${connection.name}__supply_${componentId}_${pointIndex}`,
					rootConnectionName:
						connection.rootConnectionName ?? connection.name,
					netConnectionName:
						connection.netConnectionName ??
						connection.rootConnectionName ??
						connection.name,
					pointsToConnect: [point, anchorPoint],
				};
				rewrittenConnections.push(supplyConnection);
				supplyCandidates.push({
					direction: getOutwardDirection(point, componentCenter),
					connection: supplyConnection,
				});
			}
		}
		output = { ...output, connections: rewrittenConnections };
		applyFanout({
			componentId,
			candidates: supplyCandidates,
			sharedBoundary: fanoutBounds,
			escapeLayers: ["top"],
			busLabel: "supply",
		});
		applyFanout({
			componentId,
			candidates: allCandidates.filter((candidate) => !candidate.isLocal),
			sharedBoundary: fanoutBounds,
			escapeLayers: ["top"],
			busLabel: "external",
		});
	}

	return { routingProblem: output, fanoutPrefixes };
};

const reverseRoute = (route: RoutePoint[]): RoutePoint[] =>
	route.toReversed().map((point) => {
		if (point.route_type === "via") {
			return {
				...point,
				from_layer: point.to_layer,
				to_layer: point.from_layer,
			};
		}
		if (point.route_type !== "wire") return point;
		const { start_pcb_port_id, end_pcb_port_id, ...rest } = point;
		return {
			...rest,
			...(end_pcb_port_id ? { start_pcb_port_id: end_pcb_port_id } : {}),
			...(start_pcb_port_id ? { end_pcb_port_id: start_pcb_port_id } : {}),
		};
	});

const routeEndsTouch = (first: RoutePoint, second: RoutePoint) => {
	// The downstream DRC improver snaps fanout exits to its 1 µm geometry grid.
	const endpointToleranceMm = 0.01;
	if (
		(first.route_type !== "wire" && first.route_type !== "via") ||
		(second.route_type !== "wire" && second.route_type !== "via")
	) {
		return false;
	}
	return (
		Math.abs(first.x - second.x) <= endpointToleranceMm &&
		Math.abs(first.y - second.y) <= endpointToleranceMm &&
		(first.route_type === "via" ||
			second.route_type === "via" ||
			first.layer === second.layer)
	);
};

const joinFanoutPrefix = (
	completion: SimplifiedPcbTrace,
	prefix: SimplifiedPcbTrace,
): SimplifiedPcbTrace => {
	const completionStart = completion.route[0];
	const completionEnd = completion.route.at(-1);
	const prefixStart = prefix.route[0];
	const prefixEnd = prefix.route.at(-1);
	if (!completionStart || !completionEnd || !prefixStart || !prefixEnd) {
		throw new Error(
			`Cannot join empty fanout route ${completion.connection_name}`,
		);
	}

	if (routeEndsTouch(prefixEnd, completionStart)) {
		return {
			...completion,
			route: [...prefix.route, ...completion.route.slice(1)],
		};
	}
	if (routeEndsTouch(prefixEnd, completionEnd)) {
		return {
			...completion,
			route: [...completion.route, ...reverseRoute(prefix.route).slice(1)],
		};
	}
	// Pipeline 9 can absorb a short preloaded local fanout into its final route
	// and return a complete source-to-destination trace instead of a route that
	// begins at the fanout exit. In that case the original pad endpoint proves
	// that the prefix is already represented and must not be concatenated again.
	if (
		routeEndsTouch(prefixStart, completionStart) ||
		routeEndsTouch(prefixStart, completionEnd)
	) {
		return completion;
	}
	throw new Error(
		`Global route for ${completion.connection_name} does not meet its fanout prefix`,
	);
};

const fanoutPrefixTouchesTrace = (
	completion: SimplifiedPcbTrace,
	prefix: SimplifiedPcbTrace,
) => {
	const prefixEnd = prefix.route.at(-1);
	const completionStart = completion.route[0];
	const completionEnd = completion.route.at(-1);
	return Boolean(
		prefixEnd &&
			((completionStart && routeEndsTouch(prefixEnd, completionStart)) ||
				(completionEnd && routeEndsTouch(prefixEnd, completionEnd))),
	);
};

class ThroughViaFanoutAutorouter {
	readonly input: SimpleRouteJson;
	isRouting = false;

	private readonly solver: AutoroutingPipelineSolver;
	private readonly fanoutPrefixes: Map<string, SimplifiedPcbTrace>;
	private readonly eventHandlers: {
		[K in keyof AutorouterEventMap]: Array<
			(event: AutorouterEventMap[K]) => void
		>;
	} = { complete: [], error: [], progress: [] };
	private timeoutId: ReturnType<typeof setTimeout> | undefined;
	private cycleCount = 0;

	constructor(input: SimpleRouteJson) {
		this.input = input;
		const supplyRailTokens = getQfnSupplyRailTokens(input);
		const outerLayerProblem = getOuterLayerRoutingProblem(input);
		const { routingProblem, fanoutPrefixes } = addQfnFanout(
			outerLayerProblem,
			supplyRailTokens,
		);
		this.fanoutPrefixes = fanoutPrefixes;
		this.solver = new AutoroutingPipelineSolver(routingProblem, {
			// The optional expander only widens already-routed power nets. It can
			// exhaust its fixed iteration budget on this board; the trace-width
			// solver has already applied the requested per-net widths.
			powerTraceExpansion: { onlyConnectionNames: [] },
		});
	}

	on<K extends keyof AutorouterEventMap>(
		eventName: K,
		callback: (event: AutorouterEventMap[K]) => void,
	) {
		this.eventHandlers[eventName].push(callback as never);
	}

	start() {
		if (this.isRouting) return;
		this.isRouting = true;
		this.cycleCount = 0;
		this.timeoutId = setTimeout(() => this.runCycle(), 0);
	}

	stop() {
		this.isRouting = false;
		if (this.timeoutId !== undefined) clearTimeout(this.timeoutId);
		this.timeoutId = undefined;
	}

	solveSync(): SimplifiedPcbTrace[] {
		this.solver.solve();
		if (this.solver.failed) {
			throw new Error(this.solver.error ?? "Outer-layer autorouting failed");
		}
		return this.getFinalTraces();
	}

	private getFinalTraces() {
		const completions = this.solver.getOutputSimplifiedPcbTraces();
		const unmatchedPrefixes = new Map(this.fanoutPrefixes);
		const traces = completions.map((completion) => {
			const directPrefix = unmatchedPrefixes.get(completion.connection_name);
			const matchingPrefix = directPrefix
				? ([completion.connection_name, directPrefix] as const)
				: [...unmatchedPrefixes].find(([, prefix]) =>
						fanoutPrefixTouchesTrace(completion, prefix),
					);
			if (!matchingPrefix) return completion;
			unmatchedPrefixes.delete(matchingPrefix[0]);
			return joinFanoutPrefix(completion, matchingPrefix[1]);
		});
		if (unmatchedPrefixes.size > 0) {
			throw new Error(
				`Global routes did not meet ${unmatchedPrefixes.size} fanout prefix(es): ${[
					...unmatchedPrefixes.keys(),
				].join(", ")}`,
			);
		}
		return traces;
	}

	private emit<K extends keyof AutorouterEventMap>(
		eventName: K,
		event: AutorouterEventMap[K],
	) {
		for (const callback of this.eventHandlers[eventName]) callback(event);
	}

	private runCycle() {
		if (!this.isRouting) return;
		try {
			if (this.solver.failed) {
				this.isRouting = false;
				this.emit("error", {
					type: "error",
					error: new Error(
						this.solver.error ?? "Outer-layer autorouting failed",
					),
				});
				return;
			}
			if (this.solver.solved) {
				this.isRouting = false;
				this.emit("complete", {
					type: "complete",
					traces: this.getFinalTraces(),
				});
				return;
			}

			const startedAt = Date.now();
			const startingIterations = this.solver.iterations;
			while (
				Date.now() - startedAt < 200 &&
				!this.solver.solved &&
				!this.solver.failed
			) {
				this.solver.step();
			}
			const elapsedMs = Math.max(1, Date.now() - startedAt);
			this.cycleCount++;
			this.emit("progress", {
				type: "progress",
				steps: this.cycleCount,
				progress: this.solver.progress,
				phase: this.solver.getCurrentPhase(),
				iterationsPerSecond:
					((this.solver.iterations - startingIterations) / elapsedMs) * 1000,
			});
			this.timeoutId = setTimeout(() => this.runCycle(), 0);
		} catch (error) {
			this.isRouting = false;
			this.emit("error", {
				type: "error",
				error: error instanceof Error ? error : new Error(String(error)),
			});
		}
	}
}

export const throughViaFanoutAutorouter = {
	local: true,
	groupMode: "subcircuit" as const,
	algorithmFn: async (simpleRouteJson: SimpleRouteJson) =>
		new ThroughViaFanoutAutorouter(simpleRouteJson),
};