rsp2k
a6aa1991a1
The router began as a port of FreeRouting and has grown its own engine (negotiated congestion, tree nets, exact checks, axis escapes), and 'freeroute' was one letter from the project it no longer follows. The package, module and command are now rpmroute; the freeroute command stays as an alias, and the RPMROUTE / RPMROUTE_ORACLE_JAVA variables fall back to the old FREEROUTE names. Version 2026.10.07. Routing is unchanged: a PCBench board routes to a byte-identical session either way.
322 lines
12 KiB
Python
322 lines
12 KiB
Python
"""Tests for the multi-layer grid maze router and the DSN -> SES pipeline.
|
|
|
|
Fast tests assert the routing invariants (traces connect their pads, stay on
|
|
valid layers, stay in bounds, vias sit at real layer transitions, no same-layer
|
|
crossing between nets). Oracle-gated tests check connectivity parity against the
|
|
reference FreeRouting JAR.
|
|
|
|
Fixtures: ``simple_2net.dsn`` (single-layer routable) and ``crossing_2net.dsn``
|
|
(a full-width NET_A wall that NET_B must cross, forcing a via).
|
|
"""
|
|
|
|
from __future__ import annotations
|
|
|
|
from pathlib import Path
|
|
import sys
|
|
|
|
import pytest
|
|
|
|
from rpmroute.board import build_board
|
|
from rpmroute.dsn import parse_dsn
|
|
from rpmroute.dsn.sexp import parse
|
|
from rpmroute.route import route, route_dsn_board
|
|
from rpmroute.ses.writer import ses_scale
|
|
|
|
sys.path.insert(0, str(Path(__file__).resolve().parent.parent))
|
|
|
|
FIXTURES = Path(__file__).resolve().parent.parent / "dsn" / "fixtures"
|
|
SIMPLE = FIXTURES / "simple_2net.dsn"
|
|
CROSSING = FIXTURES / "crossing_2net.dsn"
|
|
RIPUP = FIXTURES / "ripup_needed.dsn"
|
|
|
|
|
|
def _wire_key(result):
|
|
"""A hashable snapshot of a routing result for determinism checks."""
|
|
return {
|
|
net: [(layer, [(p.x, p.y) for p in pts]) for layer, pts in segs]
|
|
for net, segs in result.wires.items()
|
|
}
|
|
|
|
|
|
def _network_out(ses_text: str):
|
|
root = parse(ses_text)
|
|
network = root.child("routes").child("network_out")
|
|
return network.children("net")
|
|
|
|
|
|
def _net_scopes(ses_text: str):
|
|
result = {}
|
|
for net in _network_out(ses_text):
|
|
name = net.values()[0].text
|
|
result[name] = {"wires": net.children("wire"), "vias": net.children("via")}
|
|
return result
|
|
|
|
|
|
def _wire_layer_and_coords(wire):
|
|
path = wire.child("path")
|
|
vals = [v.text for v in path.values()]
|
|
nums = [float(v) for v in vals[2:]]
|
|
coords = list(zip(nums[0::2], nums[1::2], strict=False))
|
|
return vals[0], coords
|
|
|
|
|
|
def _orient(a, b, c):
|
|
return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
|
|
|
|
|
|
def _segments_properly_cross(p1, p2, p3, p4) -> bool:
|
|
d1 = _orient(p3, p4, p1)
|
|
d2 = _orient(p3, p4, p2)
|
|
d3 = _orient(p1, p2, p3)
|
|
d4 = _orient(p1, p2, p4)
|
|
return ((d1 > 0) != (d2 > 0)) and ((d3 > 0) != (d4 > 0))
|
|
|
|
|
|
# --- single-layer / no-crossing case ----------------------------------------
|
|
|
|
|
|
def test_simple_board_routes_both_nets_without_vias():
|
|
result, _, _ = route_dsn_board(parse_dsn(SIMPLE.read_text()))
|
|
assert result.routed_net_numbers == {1, 2}
|
|
assert result.via_count() == 0 # no crossing -> no layer change needed
|
|
|
|
|
|
def test_pipeline_emits_valid_ses_with_both_nets():
|
|
ses = route(SIMPLE.read_text())
|
|
assert parse(ses).head == "session"
|
|
nets = _net_scopes(ses)
|
|
assert set(nets) == {"NET_A", "NET_B"}
|
|
assert all(n["wires"] for n in nets.values())
|
|
|
|
|
|
def test_simple_trace_endpoints_sit_on_the_net_pads():
|
|
# Pad centres in DSN units, scaled to the SES's resolution units.
|
|
k = ses_scale(parse_dsn(SIMPLE.read_text()))
|
|
pads = {
|
|
net: {(x * k, y * k) for x, y in centres}
|
|
for net, centres in {
|
|
"NET_A": {(20000.0, -20000.0), (180000.0, -20000.0)},
|
|
"NET_B": {(20000.0, -60000.0), (180000.0, -60000.0)},
|
|
}.items()
|
|
}
|
|
for net_name, scope in _net_scopes(route(SIMPLE.read_text())).items():
|
|
endpoints = set()
|
|
for wire in scope["wires"]:
|
|
_, coords = _wire_layer_and_coords(wire)
|
|
endpoints.add(coords[0])
|
|
endpoints.add(coords[-1])
|
|
assert endpoints == pads[net_name]
|
|
|
|
|
|
# --- multi-layer crossing case ----------------------------------------------
|
|
|
|
|
|
def test_greedy_single_layer_strands_a_net_on_the_crossing_board():
|
|
# greedy (no rip-up) on one layer: NET_A's straight wall strands NET_B
|
|
result, _, _ = route_dsn_board(parse_dsn(CROSSING.read_text()), layers=[0], rip_up=False)
|
|
assert len(result.routed_net_numbers) < 2
|
|
assert result.via_count() == 0
|
|
|
|
|
|
def test_multilayer_routes_the_crossing_board_with_a_via():
|
|
result, _, _ = route_dsn_board(parse_dsn(CROSSING.read_text()))
|
|
assert result.routed_net_numbers == {1, 2} # both nets connect
|
|
assert result.via_count() >= 1 # the crossing net changes layers
|
|
|
|
|
|
def test_crossing_ses_contains_a_via():
|
|
ses = route(CROSSING.read_text())
|
|
nets = _net_scopes(ses)
|
|
assert set(nets) == {"NET_A", "NET_B"}
|
|
total_vias = sum(len(n["vias"]) for n in nets.values())
|
|
assert total_vias >= 1
|
|
|
|
|
|
def test_vias_sit_at_real_layer_transitions():
|
|
# every via location must be shared by two wire segments of the same net on
|
|
# different layers (i.e. a genuine layer transition of that net's path).
|
|
result, _, _ = route_dsn_board(parse_dsn(CROSSING.read_text()))
|
|
for net_no, locations in result.vias.items():
|
|
segments = result.wires.get(net_no, [])
|
|
for via in locations:
|
|
point = (via.x, via.y)
|
|
layers_touching = {
|
|
layer for layer, pts in segments if any((p.x, p.y) == point for p in pts)
|
|
}
|
|
assert len(layers_touching) >= 2, "via not at a layer transition"
|
|
|
|
|
|
def test_via_endpoints_come_from_the_net_pads_across_layers():
|
|
# the crossing net's overall path still starts and ends on its two pads
|
|
result, _, _ = route_dsn_board(parse_dsn(CROSSING.read_text()))
|
|
board = build_board(parse_dsn(CROSSING.read_text()))
|
|
pins_by_net: dict[int, set[tuple[int, int]]] = {}
|
|
for pin in board.get_pins():
|
|
for net_no in pin.net_nos:
|
|
pins_by_net.setdefault(net_no, set()).add((pin.location.x, pin.location.y))
|
|
for net_no, segments in result.wires.items():
|
|
all_points = [(p.x, p.y) for _, pts in segments for p in pts]
|
|
endpoints = {all_points[0], all_points[-1]}
|
|
assert endpoints == pins_by_net[net_no]
|
|
|
|
|
|
# --- rip-up-and-retry (single-layer congestion) -----------------------------
|
|
|
|
|
|
def test_greedy_strands_a_net_on_the_congested_board():
|
|
# ripup_needed has one signal layer (no vias); greedy net order strands NET_B
|
|
result, _, _ = route_dsn_board(parse_dsn(RIPUP.read_text()), rip_up=False)
|
|
assert result.unrouted >= 1
|
|
assert len(result.routed_net_numbers) < 2
|
|
assert result.via_count() == 0 # single signal layer -> vias impossible
|
|
|
|
|
|
def test_ripup_connects_all_on_the_congested_board():
|
|
result, _, _ = route_dsn_board(parse_dsn(RIPUP.read_text()), rip_up=True)
|
|
assert result.unrouted == 0
|
|
assert result.routed_net_numbers == {1, 2} # rip-up reroutes to connect both
|
|
assert result.via_count() == 0
|
|
|
|
|
|
def test_ripup_result_is_deterministic():
|
|
a, _, _ = route_dsn_board(parse_dsn(RIPUP.read_text()), rip_up=True)
|
|
b, _, _ = route_dsn_board(parse_dsn(RIPUP.read_text()), rip_up=True)
|
|
assert _wire_key(a) == _wire_key(b)
|
|
|
|
|
|
def test_ripup_endpoints_still_on_pads_and_no_same_layer_crossing():
|
|
result, _, _ = route_dsn_board(parse_dsn(RIPUP.read_text()), rip_up=True)
|
|
board = build_board(parse_dsn(RIPUP.read_text()))
|
|
pins_by_net: dict[int, set[tuple[int, int]]] = {}
|
|
for pin in board.get_pins():
|
|
for net_no in pin.net_nos:
|
|
pins_by_net.setdefault(net_no, set()).add((pin.location.x, pin.location.y))
|
|
per_layer: dict[int, list[tuple[int, list]]] = {}
|
|
for net_no, segments in result.wires.items():
|
|
pts = [(p.x, p.y) for _, seg in segments for p in seg]
|
|
assert {pts[0], pts[-1]} == pins_by_net[net_no] # endpoints on pads
|
|
for layer, seg in segments:
|
|
per_layer.setdefault(layer, []).append((net_no, [(p.x, p.y) for p in seg]))
|
|
for entries in per_layer.values():
|
|
for i in range(len(entries)):
|
|
net_i, poly_i = entries[i]
|
|
for j in range(i + 1, len(entries)):
|
|
net_j, poly_j = entries[j]
|
|
if net_i == net_j:
|
|
continue
|
|
for a in range(len(poly_i) - 1):
|
|
for b in range(len(poly_j) - 1):
|
|
assert not _segments_properly_cross(
|
|
poly_i[a], poly_i[a + 1], poly_j[b], poly_j[b + 1]
|
|
)
|
|
|
|
|
|
# --- cross-net invariants ---------------------------------------------------
|
|
|
|
|
|
def test_no_two_nets_cross_on_the_same_layer():
|
|
result, _, _ = route_dsn_board(parse_dsn(CROSSING.read_text()))
|
|
per_layer: dict[int, list[tuple[int, list]]] = {}
|
|
for net_no, segments in result.wires.items():
|
|
for layer, pts in segments:
|
|
coords = [(p.x, p.y) for p in pts]
|
|
per_layer.setdefault(layer, []).append((net_no, coords))
|
|
for entries in per_layer.values():
|
|
for i in range(len(entries)):
|
|
net_i, poly_i = entries[i]
|
|
for j in range(i + 1, len(entries)):
|
|
net_j, poly_j = entries[j]
|
|
if net_i == net_j:
|
|
continue
|
|
for a in range(len(poly_i) - 1):
|
|
for b in range(len(poly_j) - 1):
|
|
assert not _segments_properly_cross(
|
|
poly_i[a], poly_i[a + 1], poly_j[b], poly_j[b + 1]
|
|
), "different nets cross on the same layer"
|
|
|
|
|
|
def test_traces_stay_within_the_board_outline():
|
|
for path in (SIMPLE, CROSSING):
|
|
k = ses_scale(parse_dsn(path.read_text()))
|
|
ses = route(path.read_text())
|
|
for scope in _net_scopes(ses).values():
|
|
for wire in scope["wires"]:
|
|
_, coords = _wire_layer_and_coords(wire)
|
|
for x, y in coords:
|
|
assert 0 <= x <= 200000 * k
|
|
assert -80000 * k <= y <= 0
|
|
|
|
|
|
def test_traces_stay_on_valid_layers():
|
|
ses = route(CROSSING.read_text())
|
|
for scope in _net_scopes(ses).values():
|
|
for wire in scope["wires"]:
|
|
layer, _ = _wire_layer_and_coords(wire)
|
|
assert layer in {"Top", "Bottom"}
|
|
|
|
|
|
def test_larger_board_still_connects_its_multipin_nets():
|
|
# regression: rip-up must not lose coverage on the real board. It has 4
|
|
# multi-pin nets, all of which the router connects.
|
|
dsn = parse_dsn((FIXTURES / "kicad_routable.dsn").read_text())
|
|
result, _, _ = route_dsn_board(dsn)
|
|
multi_pin = sum(1 for n in dsn.nets if len(n.pins) >= 2)
|
|
assert len(result.routed_net_numbers) == multi_pin == 4
|
|
|
|
|
|
def test_a_seed_is_repeatable_and_does_change_the_order():
|
|
# The benchmark samples seeds to measure how much a result owes to the
|
|
# routing order. A seed that changed nothing would make every sample the
|
|
# same run and report no spread at all.
|
|
text = (FIXTURES / "kicad_routable.dsn").read_text()
|
|
default = _wire_key(route_dsn_board(parse_dsn(text))[0])
|
|
runs = {s: route_dsn_board(parse_dsn(text), seed=s)[0] for s in range(4)}
|
|
again = route_dsn_board(parse_dsn(text), seed=1)[0]
|
|
assert _wire_key(again) == _wire_key(runs[1])
|
|
assert any(_wire_key(r) != default for r in runs.values())
|
|
assert all(r.unrouted == 0 for r in runs.values())
|
|
|
|
|
|
# --- oracle parity ----------------------------------------------------------
|
|
|
|
|
|
@pytest.mark.oracle
|
|
def test_connectivity_parity_on_congested_board():
|
|
from oracle import HAS_ORACLE, route_dsn, routed_net_set
|
|
|
|
if not HAS_ORACLE:
|
|
pytest.skip("FreeRouting oracle unavailable")
|
|
our_nets = routed_net_set(route(RIPUP.read_text()))
|
|
assert our_nets == {"NET_A", "NET_B"} # rpmroute connects both via rip-up
|
|
oracle_nets = routed_net_set(route_dsn(RIPUP, max_passes=3, timeout=300))
|
|
if not oracle_nets:
|
|
# the reference JAR does not route this synthetic single-signal-layer
|
|
# board (it expects a routing/via layer); rpmroute's rip-up connecting
|
|
# both nets is already asserted above and by the fast tests.
|
|
pytest.skip("reference JAR routed nothing on the synthetic single-layer board")
|
|
assert oracle_nets <= our_nets # rip-up matches the JAR's connectivity
|
|
|
|
|
|
@pytest.mark.oracle
|
|
def test_connectivity_parity_on_crossing_board():
|
|
from oracle import HAS_ORACLE, route_dsn, routed_net_set
|
|
|
|
if not HAS_ORACLE:
|
|
pytest.skip("FreeRouting oracle unavailable")
|
|
our_nets = routed_net_set(route(CROSSING.read_text()))
|
|
oracle_nets = routed_net_set(route_dsn(CROSSING, max_passes=3, timeout=300))
|
|
assert oracle_nets, "oracle routed nothing on a routable board"
|
|
assert oracle_nets <= our_nets # rpmroute connects every net the JAR does
|
|
|
|
|
|
@pytest.mark.oracle
|
|
def test_connectivity_parity_on_simple_board():
|
|
from oracle import HAS_ORACLE, route_dsn, routed_net_set
|
|
|
|
if not HAS_ORACLE:
|
|
pytest.skip("FreeRouting oracle unavailable")
|
|
our_nets = routed_net_set(route(SIMPLE.read_text()))
|
|
oracle_nets = routed_net_set(route_dsn(SIMPLE, max_passes=3, timeout=300))
|
|
assert oracle_nets, "oracle routed nothing on a routable board"
|
|
assert oracle_nets <= our_nets
|