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.
Add diagonal_win.dsn: a 45-degree pin-to-pin net with a keepout placed inside the
diagonal's bounding box but clear of the true thin copper. Orthogonal routing
connects it with a Manhattan-length staircase (1600000); diagonal routing
replaces that with a single 45-degree trace at the ideal hypotenuse length
(1131371) -- a 29% reduction -- DRC-clean via the search tree and via an
independent reconstruction of the emitted 45-degree copper's clearance octagon.
test_exact_clearance_is_load_bearing shows the keepout overlaps the coarse
bounding box but not the exact octagon, so the exact clearance (not the box) is
what lets the diagonal route. Determinism, endpoints-on-pads, valid SES, and
diagonal-off-equals-orthogonal (additive, over four fixtures) are covered.
Add channel_pack.dsn: three nets whose pads spread wider than a wall gap, so they
must converge and pack into lanes. Plain room routing (shove on or off) drops >= 1
net under every net ordering; the packer connects all three under every ordering,
DRC-clean (search tree and independent emitted-copper check).
The falsifiable boundary test sweeps the gap width for N=3 and N=4 and asserts the
packer connects all N iff the gap meets the geometric feasibility width
(N-1)*(width+clearance) + 2*(half_width+clearance), never routes fewer than greedy
below it, and never false-packs. Determinism, endpoints-on-pads, valid SES, and
pack=False-equals-default (additive) are covered.
Add true_density.dsn: NET_C is a full-height wall on the sole signal layer,
so plain room routing drops a net under every net ordering (an order-independent
obstruction, verified over all permutations), unlike rooms_shove_channel whose
plain drop fits under a reorder.
Test that shove recovers nothing on this board (shoves == 0, same routed set as
plain) while staying DRC-clean, and that the only difference from the recoverable
shove_channel is the wall's span. shove relocates a blocker into existing free
space; where the wall leaves no headroom there is nowhere to relocate to, so it
cannot manufacture density. The recover/fail boundary is the free-space boundary.
_shove_recover_room clobbered a net's _Accepted with a fresh one whose
wire_owners held only the just-recovered wire, while its wires list (the
shared result.wires[net_no]) already held earlier committed connections.
That left wire_owners shorter than the parallel wires list, so a later
net's shove either removed the wrong wire's copper from the search tree
(a silent different-net short: copper stayed in the emitted SES but
vanished from the tree, and has_violation falsely certified it clean) or
raised IndexError and aborted the whole route.
Reuse the net's existing _Accepted on recovery so wire_owners stays
parallel to wires. Fixes both the silent DRC violation and the crash
sibling without touching the DRC-clean or determinism invariants.
Also correct the overstated "density win" framing of the shove_channel
fixture: its plain-routing net drop is an artifact of greedy net order,
not a density limit (the same board routes both nets with zero shoves
under a reorder or with the cosmetic seals removed). Reframed the test
and docstring; the genuine sub-cell win remains the wide_door occupancy
packing (shoves == 0).
Regression tests assert the invariant against the emitted output
directly (reconstructed copper tiles), not just the tree that the bug
fooled, plus determinism, no-crash, and the ordering-artifact bound.
rooms_shove_channel is the headline density win: a sealed NET_A wall
leaves no top<->bottom door, so plain room routing drops NET_C; with
shove=True NET_A is nudged aside and both nets route, DRC-clean and
deterministic. rooms_wide_door seats two nets through one wide gap at
distinct projected gate points with no shove.
Cover the occupancy-aware projection math directly, assert the four
foundation fixtures stay byte-identical under shove=True (shoves==0), and
extend the room DRC-clean parametrize with both new fixtures.
Adds narrow_channel.dsn: a keepout wall with a narrow gap positioned off the
routing grid, so no grid cell centre falls inside the gap's free centreline.
The exact/grid track drops the net (cell quantization can't fit a centreline
in the channel); the continuous room track routes it. This is the headline
result that continuous free-space beats the grid.
Tests: the room router's output is DRC-clean (exact has_violation is None) on
simple/crossing/kicad/narrow_channel; it connects simple/crossing (with a via)
and all four multi-pin KiCad nets; traces are orthogonal and end on pads; and
the continuity contrast asserts exact routes 0 while rooms routes 1, both
clean. Oracle-gated connectivity parity on simple/crossing.
Adds shove_needed.dsn: one signal layer (no vias), where NET_A routes as
a straight wall that boxes NET_C out under greedy ordering. Tests assert
the contrast: without shove NET_C is dropped (result still DRC-clean, just
incomplete); with shove NET_A is moved aside and both nets connect, the
exact has_violation check is clean, endpoints stay on pads, and the result
is deterministic. Regression tests confirm shove is a no-op on the simple/
crossing/ripup/kicad boards (same connectivity, DRC-clean, zero shoves).
Oracle-gated parity is included (skips when the JAR cannot route the
synthetic single-layer board).
Adds ripup_needed.dsn: one signal layer (B.Cu is a power plane, so vias
are impossible) with two nets whose greedy order strands NET_B, but where
rip-up reroutes NET_A around NET_B to connect both.
Tests: greedy (rip_up=False) leaves >= 1 connection unrouted with no vias;
rip-up connects all with no vias; the result is deterministic across
re-runs; rip-up keeps endpoints on pads and produces no same-layer cross
between nets (ripped traces leave no orphaned occupancy). The crossing
board's single-layer test now targets the greedy path explicitly, and a
regression test asserts the real KiCad board still connects all four of
its multi-pin nets. Oracle-gated parity added for the congested board.
Adds crossing_2net.dsn: NET_A is a full-width horizontal wall and NET_B's
pins sit above and below it, so single-layer routing cannot connect NET_B
but two-layer routing succeeds by dipping to the other layer through vias.
Tests assert the multi-layer invariants: single-layer routing leaves a net
unrouted with no vias; multi-layer connects both nets with >= 1 via; the
SES contains a via scope; every via sits at a real layer transition of its
net's path; trace/via endpoints still land on the pads; traces stay on
valid layers and within the outline; and no two different nets cross on the
same layer. Oracle-gated parity tests cover the simple and crossing boards.
Implements a working autorouter and the Java-free replacement for the
freerouting.jar step: dsn_text -> parse_dsn -> build_board -> route ->
write_ses.
GridRouter is a single-layer A* maze search over a uniform occupancy
grid: a cell is blocked by another net's pad (inflated by clearance +
half trace width) or a keepout; each net's ratsnest is connected pin to
pin; a routed trace then blocks other nets. The cell path becomes a
trace polyline whose endpoints are the exact pin locations. Board-unit
paths are converted back to DSN units for the SES (wire (path ...))
scopes.
This is an MVP, not a port of FreeRouting's expansion-room maze:
free-space rooms, rip-up-and-retry, multi-layer via search, and shove
are deferred (they raise quality/coverage, not the connectivity
milestone). It reaches connectivity on boards whose nets route on one
layer without crossing.
Adds tests/dsn/fixtures/simple_2net.dsn (a guaranteed-routable 2-net
board). Invariant tests: both nets route, the emitted SES parses, every
trace stays on a valid layer and within the board outline, and every
routed net's trace endpoints sit exactly on its two pads. An oracle-gated
test asserts connectivity parity with the reference FreeRouting JAR on
the simple board.
FreeRouting ships no unit tests for its geometry/router, so there is no
value-level oracle to port against. This adds a dev/test-only harness that runs
the reference JAR to route a DSN, letting freeroute's output be diffed against
the reference implementation — the router phase will assert connectivity parity
(same nets routed) via routed_net_set().
- tests/oracle.py: locate Java 21+ and a freerouting JAR (env overrides:
FREEROUTE_ORACLE_JAVA, FREEROUTING_JAR), route a DSN, and extract routed
connectivity from the SES. requires_oracle skips when no JVM/JAR is present,
so the suite stays Java-free.
- tests/test_oracle.py: routes a routable board end-to-end and checks the
connectivity extraction.
- tests/dsn/fixtures/kicad_routable.dsn: a real KiCad pcbnew-exported DSN
(Arduino_Mega template, path sanitized) that actually routes — the smd_demo
fixture leaves its nets unrouted.
- pyproject: pythonpath=["tests"] so the harness imports as `oracle`.
Specctra's SpecCharASCII includes / and *, and an Identifier may start with /,
so KiCad emits hierarchical net names such as /*52 and /53. The tokenizer
treated any /* as a block-comment start and raised 'unterminated comment' when
no */ followed — rejecting real KiCad DSN. Match FreeRouting's JFlex rule-order
resolution: /* is a comment only when a closing */ exists; otherwise it is an
ordinary name run. Validated against a KiCad 10.0.4 pcbnew-exported DSN (78 nets
incl. /*52, /53).
Ports the read path of FreeRouting's io/specctra/parser package to a
Java-free Python implementation:
- tokenizer: S-expression lexer mirroring SpecctraFileDescription.flex
(comments, quoted strings, the string_quote IGNORE_QUOTE directive,
case-insensitive keywords, and hash-prefixed names)
- sexp: nested S-expression tree builder
- shapes: rect/circle/polygon/path plus area-with-holes scopes
- model: typed dataclasses for layers, padstacks, images, placements,
nets, net classes, rules, keepouts
- reader: recursive-descent scope readers producing a DsnBoard, one
_read_* function per FreeRouting read_scope method
46 pytest cases cover the tokenizer, tree, shapes, and end-to-end
parsing against hand-crafted fixtures modeled on FreeRouting's own
test DSN files. Parses 90 of 91 upstream fixtures (the one failure is
a binary OLE file, not text DSN).
rsp2k