--reserve-escapes: keep a way out open for every fine-pitch pin

Before routing, each crowded pin gets the shortest way from its pad to
open board, found against pads, keepouts and earlier escapes. While the
pin still has connections to route, no other net may put a trace or a
via there, nor within clearance of it; the reservation lifts once the
pin is routed.

src/freeroute/cli.py

@@ -30,8 +30,8 @@ from freeroute.ses import write_ses
 #: which optional flags each engine actually implements. Anything not listed for
 #: an engine is rejected by :func:`_validate` rather than quietly ignored.
 ENGINE_OPTIONS: dict[str, frozenset[str]] = {
-    "grid": frozenset({"rip_up", "max_passes", "seed", "orders", "promote", "access", "rollback"}),
-    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access", "rollback"}),
+    "grid": frozenset({"rip_up", "max_passes", "seed", "orders", "promote", "access", "escapes"}),
+    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access", "escapes"}),
     "room": frozenset({"shove", "pack"}),
 }
 
@@ -46,7 +46,7 @@ _FLAG_NAMES = {
     "orders": "--orders",
     "promote": "--promote-failures",
     "access": "--access-cost",
-    "rollback": "--no-rollback",
+    "escapes": "--reserve-escapes",
 }
 
 
@@ -168,12 +168,10 @@ def build_parser() -> argparse.ArgumentParser:
         "another pin's way out while that pin still has connections to route (default 0: off)",
     )
     parser.add_argument(
-        "--no-rollback",
-        dest="rollback",
-        action="store_false",
-        help="grid and exact engines: keep every rip-up, as before. By default the "
-        "connections a rip-up displaces are rerouted at once and the rip-up is undone "
-        "if fewer connections end up routed",
+        "--reserve-escapes",
+        action="store_true",
+        help="grid and exact engines: before routing, reserve a way out for every fine-pitch "
+        "pin that no other net may use until that pin's connections are routed",
     )
     parser.add_argument(
         "--jobs",
@@ -204,7 +202,7 @@ def main(argv: list[str] | None = None) -> int:
             ("orders", args.orders is not None),
             ("promote", args.promote_failures is not None),
             ("access", args.access_cost is not None),
-            ("rollback", not args.rollback),
+            ("escapes", args.reserve_escapes),
         )
         if asked
     ]
@@ -239,7 +237,7 @@ def main(argv: list[str] | None = None) -> int:
             "resolution": 2 if args.grid_resolution is None else args.grid_resolution,
             "heuristic_weight": args.heuristic_weight,
             "access_cost": args.access_cost or 0.0,
-            "rollback": args.rollback,
+            "reserve_escapes": args.reserve_escapes,
         }
     elif args.engine == "grid":
         options = {
@@ -249,7 +247,7 @@ def main(argv: list[str] | None = None) -> int:
             "edge_clearance_mm": args.edge_clearance,
             "resolution": 1 if args.grid_resolution is None else args.grid_resolution,
             "access_cost": args.access_cost or 0.0,
-            "rollback": args.rollback,
+            "reserve_escapes": args.reserve_escapes,
         }
     if args.engine == "room":
         result = build_rooms_routing_result(

src/freeroute/route/exact_router.py

@@ -98,7 +98,7 @@ def route_board_exact(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
-    rollback: bool = True,
+    reserve_escapes: bool = False,
 ) -> ExactRouteResult:
     """Route ``board`` orthogonally and verify the result with exact geometry.
 
@@ -130,7 +130,7 @@ def route_board_exact(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
-        rollback=rollback,
+        reserve_escapes=reserve_escapes,
     )
     edge = 0 if edge_clearance is None else edge_clearance
     outline = board.outline

src/freeroute/route/grid_router.py

@@ -113,7 +113,6 @@ class _Connection:
         "b_group",
         "a_end",
         "b_end",
-        "path",
     )
 
     def __init__(self, index: int, net_no: int, a: Pin, b: Pin) -> None:
@@ -135,8 +134,6 @@ class _Connection:
         self.b_group: tuple[list[Pin], list] = ([b], [])
         self.a_end: Pin | None = a
         self.b_end: Pin | None = b
-        # the node path last committed, so a rip-up can be undone
-        self.path: list[Node] | None = None
 
 
 class GridRouter:
@@ -162,7 +159,7 @@ class GridRouter:
         seed: int | None = None,
         route_first: frozenset | None = None,
         access_cost: float = 0.0,
-        rollback: bool = True,
+        reserve_escapes: bool = False,
     ) -> None:
         self.board = board
         # Pin access: while a pin still has connections to route, the cells
@@ -172,12 +169,12 @@ class GridRouter:
         self.access_cost = max(float(access_cost), 0.0)
         self._doorways: dict[Node, list[tuple[int, int]]] = {}
         self._pending: dict[int, int] = {}
-        # Rip-up as a transaction: the connections a rip-up route crosses are
-        # rerouted at once, and if fewer connections are routed afterwards
-        # than before, everything goes back as it was. On by default: over
-        # 8 net orders it left 25 to 30 fewer connections unrouted on dense
-        # boards and was never clearly worse.
-        self.rollback = bool(rollback)
+        # Escape reservations: before routing, every crowded (fine-pitch) pin
+        # gets a short way out to open board, and while it still has
+        # connections to route no other net may use those cells (nor come
+        # within clearance of them).
+        self.reserve_escapes = bool(reserve_escapes)
+        self._reserved: dict[Node, list[tuple[int, int]]] = {}
         # None keeps the deterministic order; a seed shuffles which connection
         # routes first, to measure how much a result owes to the order
         self.seed = seed
@@ -381,6 +378,10 @@ class GridRouter:
         node = (*cell, layer)
         if wire_keepout and node in self._keepout:
             return None
+        if self._reserved:
+            for pin_id, owner_net in self._reserved.get(node, ()):
+                if owner_net != net_no and self._pending.get(pin_id, 0) > 0:
+                    return None  # another pin's reserved way out
         pads = self._pad_block.get(node)
         if pads and any(n != net_no for n in pads) and net_no not in self._pad_own.get(node, ()):
             return None
@@ -798,7 +799,6 @@ class GridRouter:
     # --- commit / rip -------------------------------------------------------
 
     def _commit(self, conn: _Connection, path: list[Node]) -> None:
-        conn.path = list(path)
         wire_segs, via_cells = _split_path(path)
         via_cells = list(via_cells)
         if isinstance(conn.a_end, ConductionArea):
@@ -912,7 +912,6 @@ class GridRouter:
         done: set[int] = set()
         for conn in conns:
             for pin in self._group_pins(conn):
-                self._pending[id(pin)] = self._pending.get(id(pin), 0) + 1
                 if id(pin) in done:
                     continue
                 done.add(id(pin))
@@ -930,6 +929,76 @@ class GridRouter:
                 for node in cells:
                     self._doorways.setdefault(node, []).append(claim)
 
+    def _count_pending(self, conns: list[_Connection]) -> None:
+        """How many unrouted connections each pin is an end of."""
+        for conn in conns:
+            for pin in self._group_pins(conn):
+                self._pending[id(pin)] = self._pending.get(id(pin), 0) + 1
+
+    def _reserve_escapes(self, conns: list[_Connection]) -> None:
+        """Give every crowded pin a way out before anything is routed."""
+        blocked: set[Node] = set()  # earlier escapes and their clearance
+        spread = [(0, 0), *self._halo_offsets]
+        seen: set[int] = set()
+        for conn in conns:
+            for pin in self._group_pins(conn):
+                if id(pin) in seen or not self._crowded(pin, conn.net_no):
+                    continue
+                seen.add(id(pin))
+                path = self._escape_path(pin, conn.net_no, conns, blocked)
+                if not path:
+                    continue
+                claim = (id(pin), conn.net_no)
+                for x, y, layer in path:
+                    for dx, dy in spread:
+                        node = (x + dx, y + dy, layer)
+                        if 0 <= node[0] < self.cols and 0 <= node[1] < self.rows:
+                            self._reserved.setdefault(node, []).append(claim)
+                            blocked.add(node)
+
+    def _escape_path(self, pin: Pin, net_no: int, conns, blocked: set[Node]) -> list[Node]:
+        """The shortest way from a pin to a cell clear of other nets' pads,
+        against pads, keepouts and earlier escapes only (breadth first, on
+        the pin's own layers, at most ``2 * _escape_cells`` long)."""
+        starts = [n for n in self._end_nodes(pin, net_no, conns) if n not in blocked]
+        came: dict[Node, Node | None] = dict.fromkeys(starts)
+        frontier = list(starts)
+        limit = 2 * self._escape_cells
+        for _depth in range(limit):
+            nxt: list[Node] = []
+            for node in frontier:
+                if node not in starts and self._open_ground(node, net_no):
+                    path = [node]
+                    while came[path[-1]] is not None:
+                        path.append(came[path[-1]])
+                    return path[::-1]
+                x, y, layer = node
+                for dx, dy in self._neighbours:
+                    n = (x + dx, y + dy, layer)
+                    if n in came or n in blocked:
+                        continue
+                    if not (0 <= n[0] < self.cols and 0 <= n[1] < self.rows):
+                        continue
+                    if not self._static_open(n, net_no):
+                        continue
+                    came[n] = node
+                    nxt.append(n)
+            frontier = nxt
+            if not frontier:
+                break
+        return []
+
+    def _open_ground(self, node: Node, net_no: int) -> bool:
+        """Clear of every other net's pad by a full trace spacing all round."""
+        x, y, layer = node
+        for dx, dy in self._halo_offsets:
+            n = (x + dx, y + dy, layer)
+            if not (0 <= n[0] < self.cols and 0 <= n[1] < self.rows):
+                return False
+            if not self._static_open(n, net_no):
+                return False
+        return True
+
     def _settle(self, conn: _Connection, delta: int) -> None:
         if not self._pending:
             return
@@ -952,8 +1021,12 @@ class GridRouter:
         self._conns = conns
         if not conns:
             return RouteResult(self.half_width)
+        if self.access_cost or self.reserve_escapes:
+            self._count_pending(conns)
         if self.access_cost:
             self._build_doorways(conns)
+        if self.reserve_escapes:
+            self._reserve_escapes(conns)
 
         passes = self.max_passes if self.rip_up else 1
         best_count = -1
@@ -992,41 +1065,11 @@ class GridRouter:
             path = self._search(conn, allow_ripup=True, conns=conns)
             if path is None:
                 return False
-            victims = [conns[i] for i in sorted(self._crossed_owners(path, conn.net_no, conns))]
-            if self.rollback:
-                return self._ripup_transaction(conn, path, victims, conns)
-            for victim in victims:
-                self._rip(victim)
+            for idx in sorted(self._crossed_owners(path, conn.net_no, conns)):
+                self._rip(conns[idx])
         self._commit(conn, path)
         return True
 
-    def _ripup_transaction(self, conn, path, victims, conns) -> bool:
-        """Route ``conn`` through ``victims``, reroute them at once in free
-        space, and undo it all if fewer connections end up routed."""
-        saved = [(v, v.path, v.a_end, v.b_end, v.rip_count) for v in victims]
-        own_rips = conn.rip_count
-        for victim in victims:
-            self._rip(victim)
-        self._commit(conn, path)
-        rerouted = 0
-        for victim in victims:
-            again = self._search(victim, allow_ripup=False, conns=conns)
-            if again is not None:
-                self._commit(victim, again)
-                rerouted += 1
-        if 1 + rerouted >= len(victims):
-            return True  # a gain, or an even trade that may pay off later
-        for victim in victims:
-            if victim.routed:
-                self._rip(victim)
-        self._rip(conn)
-        conn.rip_count = own_rips
-        for victim, old_path, a_end, b_end, rips in saved:
-            victim.a_end, victim.b_end = a_end, b_end
-            self._commit(victim, old_path)
-            victim.rip_count = rips
-        return False
-
     def _build_connections(self) -> list[_Connection]:
         pins_by_net = self._pins_by_net()
         zones_by_net: dict[int, list] = {}
@@ -1230,7 +1273,7 @@ def route_board(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
-    rollback: bool = True,
+    reserve_escapes: bool = False,
 ) -> RouteResult:
     """Convenience wrapper: build a :class:`GridRouter` and route the board."""
     router = GridRouter(
@@ -1249,6 +1292,6 @@ def route_board(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
-        rollback=rollback,
+        reserve_escapes=reserve_escapes,
     )
     return router.route()

src/freeroute/route/pipeline.py

@@ -83,7 +83,7 @@ def route_dsn_board(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
-    rollback: bool = True,
+    reserve_escapes: bool = False,
 ) -> tuple[RouteResult, int, list[str]]:
     """Route a parsed :class:`DsnBoard`; return the board-unit result, the scale,
     and the layer names. ``layers`` restricts routing to those signal-layer
@@ -107,7 +107,7 @@ def route_dsn_board(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
-        rollback=rollback,
+        reserve_escapes=reserve_escapes,
     )
     return result, scale, [layer.name for layer in dsn.layers]
 
@@ -151,7 +151,7 @@ def build_routing_result(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
-    rollback: bool = True,
+    reserve_escapes: bool = False,
 ) -> RoutingResult:
     """Route ``dsn`` (grid track) and convert to a DSN-unit RoutingResult."""
     route, scale, layer_names = route_dsn_board(
@@ -159,7 +159,7 @@ def build_routing_result(
         edge_clearance_mm=edge_clearance_mm, resolution=resolution, seed=seed,
         route_first=route_first,
         access_cost=access_cost,
-        rollback=rollback,
+        reserve_escapes=reserve_escapes,
     )
     return _to_routing_result(route, dsn, scale, layer_names)
 
@@ -178,7 +178,7 @@ def route_dsn_board_exact(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
-    rollback: bool = True,
+    reserve_escapes: bool = False,
 ) -> tuple[ExactRouteResult, int, list[str]]:
     """Route a parsed :class:`DsnBoard` with the exact-geometry (orthogonal,
     DRC-verified) track; return the exact result, the scale, and layer names.
@@ -206,7 +206,7 @@ def route_dsn_board_exact(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
-        rollback=rollback,
+        reserve_escapes=reserve_escapes,
     )
     return exact, scale, [layer.name for layer in dsn.layers]
 
@@ -225,7 +225,7 @@ def build_exact_routing_result(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
-    rollback: bool = True,
+    reserve_escapes: bool = False,
 ) -> RoutingResult:
     """Route ``dsn`` (exact track) and convert to a DSN-unit RoutingResult."""
     exact, scale, layer_names = route_dsn_board_exact(
@@ -241,7 +241,7 @@ def build_exact_routing_result(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
-        rollback=rollback,
+        reserve_escapes=reserve_escapes,
     )
     return _to_routing_result(exact.result, dsn, scale, layer_names)
 

tests/route/test_escapes.py

@@ -0,0 +1,65 @@
+"""--reserve-escapes: a crowded pin keeps a way out until it is routed."""
+
+from __future__ import annotations
+
+from pathlib import Path
+
+from freeroute.board import build_board
+from freeroute.dsn import parse_dsn
+from freeroute.route.grid_router import GridRouter
+from freeroute.route.pipeline import (
+    _rule_clearance_dsn,
+    _rule_width_dsn,
+    build_exact_routing_result,
+)
+
+SMD = (Path(__file__).resolve().parent.parent / "dsn" / "fixtures" / "smd_demo.dsn").read_text()
+
+
+def _router():
+    dsn = parse_dsn(SMD)
+    s = dsn.resolution.value
+    router = GridRouter(
+        build_board(dsn),
+        trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s),
+        orthogonal=True,
+        resolution=2,
+        reserve_escapes=True,
+    )
+    conns = router._build_connections()
+    router._conns = conns
+    router._count_pending(conns)
+    router._reserve_escapes(conns)
+    return router, conns
+
+
+def test_a_reserved_escape_is_closed_to_other_nets_and_open_to_its_own():
+    router, conns = _router()
+    assert router._reserved
+    node, claims = next(iter(router._reserved.items()))
+    pin_id, owner = claims[0]
+    other = next(c.net_no for c in conns if c.net_no != owner)
+    cell, layer = node[:2], node[2]
+    assert router._enter_cost(cell, layer, other, True, conns) is None  # even for rip-up
+    assert router._enter_cost(cell, layer, owner, False, conns) is not None or node in router._keepout
+
+
+def test_the_escape_is_released_once_its_pin_is_routed():
+    router, conns = _router()
+    node, claims = next(iter(router._reserved.items()))
+    other = next(c.net_no for c in conns if c.net_no != claims[0][1])
+    cell, layer = node[:2], node[2]
+    assert router._enter_cost(cell, layer, other, False, conns) is None
+    for c in conns:  # every connection routed: no pin is pending any more
+        router._settle(c, -1)
+    released = router._enter_cost(cell, layer, other, False, conns)
+    reserved, router._reserved = router._reserved, {}
+    assert released == router._enter_cost(cell, layer, other, False, conns)
+    router._reserved = reserved
+
+
+def test_reserving_escapes_loses_nothing_on_the_demo_board():
+    plain = build_exact_routing_result(parse_dsn(SMD), resolution=2)
+    reserved = build_exact_routing_result(parse_dsn(SMD), resolution=2, reserve_escapes=True)
+    assert len(reserved.unrouted) <= len(plain.unrouted)

tests/route/test_rollback.py

@@ -1,43 +0,0 @@
-"""--rollback: a rip-up that loses connections is undone, leaving no trace."""
-
-from __future__ import annotations
-
-from pathlib import Path
-
-import pytest
-
-from freeroute.board import build_board
-from freeroute.dsn import parse_dsn
-from freeroute.route.grid_router import GridRouter
-from freeroute.route.pipeline import _rule_clearance_dsn, _rule_width_dsn, route_dsn_board
-
-FIXTURES = Path(__file__).resolve().parent.parent / "dsn" / "fixtures"
-
-
-def _routed_router(name):
-    dsn = parse_dsn((FIXTURES / name).read_text())
-    s = dsn.resolution.value
-    router = GridRouter(
-        build_board(dsn),
-        trace_width=round(_rule_width_dsn(dsn) * s),
-        clearance=round(_rule_clearance_dsn(dsn) * s),
-        rollback=True,
-    )
-    return router, router.route()
-
-
-@pytest.mark.parametrize("name", ["ripup_needed.dsn", "true_density.dsn", "kicad_routable.dsn"])
-def test_occupancy_only_holds_routed_connections(name):
-    router, _ = _routed_router(name)
-    conns = router._conns
-    assert all(conns[i].routed for i in router._cell_owner.values())
-    assert all(conns[i].routed for i in router._via_owner.values())
-    assert all(conns[i].routed for claims in router._halo.values() for i in claims)
-
-
-@pytest.mark.parametrize("name", ["ripup_needed.dsn", "true_density.dsn", "kicad_routable.dsn"])
-def test_rollback_never_routes_fewer_than_plain_rip_up(name):
-    text = (FIXTURES / name).read_text()
-    plain, _, _ = route_dsn_board(parse_dsn(text), rollback=False)
-    undo, _, _ = route_dsn_board(parse_dsn(text))
-    assert undo.unrouted <= plain.unrouted

tests/test_cli.py

@@ -158,7 +158,7 @@ def test_cli_supported_combinations_are_accepted(tmp_path):
         "orders": ["--orders", "2"],
         "promote": ["--promote-failures", "2"],
         "access": ["--access-cost", "5"],
-        "rollback": ["--no-rollback"],
+        "escapes": ["--reserve-escapes"],
     }
     for engine, options in ENGINE_OPTIONS.items():
         for option in options: