Rollback on by default; --no-rollback keeps every rip-up

Over 8 net orders it left 25 to 30 fewer connections unrouted on the
dense sense boards and 16 to 18 fewer on two PCBench boards, and was
never clearly worse. KiCad DRC on the sense harness: 41 opens to 28.

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"}),
-    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access"}),
+    "grid": frozenset({"rip_up", "max_passes", "seed", "orders", "promote", "access", "rollback"}),
+    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access", "rollback"}),
     "room": frozenset({"shove", "pack"}),
 }
 
@@ -46,6 +46,7 @@ _FLAG_NAMES = {
     "orders": "--orders",
     "promote": "--promote-failures",
     "access": "--access-cost",
+    "rollback": "--no-rollback",
 }
 
 
@@ -166,6 +167,14 @@ def build_parser() -> argparse.ArgumentParser:
         help="grid and exact engines: extra cost for a route to pass where it would close "
         "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",
+    )
     parser.add_argument(
         "--jobs",
         type=int,
@@ -195,6 +204,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),
         )
         if asked
     ]
@@ -229,6 +239,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,
         }
     elif args.engine == "grid":
         options = {
@@ -238,6 +249,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,
         }
     if args.engine == "room":
         result = build_rooms_routing_result(

src/freeroute/route/exact_router.py

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

src/freeroute/route/grid_router.py

@@ -113,6 +113,7 @@ class _Connection:
         "b_group",
         "a_end",
         "b_end",
+        "path",
     )
 
     def __init__(self, index: int, net_no: int, a: Pin, b: Pin) -> None:
@@ -134,6 +135,8 @@ 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:
@@ -159,6 +162,7 @@ class GridRouter:
         seed: int | None = None,
         route_first: frozenset | None = None,
         access_cost: float = 0.0,
+        rollback: bool = True,
     ) -> None:
         self.board = board
         # Pin access: while a pin still has connections to route, the cells
@@ -168,6 +172,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)
         # 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
@@ -788,6 +798,7 @@ 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):
@@ -981,11 +992,41 @@ class GridRouter:
             path = self._search(conn, allow_ripup=True, conns=conns)
             if path is None:
                 return False
-            for idx in sorted(self._crossed_owners(path, conn.net_no, conns)):
-                self._rip(conns[idx])
+            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)
         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] = {}
@@ -1189,6 +1230,7 @@ def route_board(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    rollback: bool = True,
 ) -> RouteResult:
     """Convenience wrapper: build a :class:`GridRouter` and route the board."""
     router = GridRouter(
@@ -1207,5 +1249,6 @@ def route_board(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        rollback=rollback,
     )
     return router.route()

src/freeroute/route/pipeline.py

@@ -83,6 +83,7 @@ def route_dsn_board(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    rollback: bool = True,
 ) -> 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
@@ -106,6 +107,7 @@ def route_dsn_board(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        rollback=rollback,
     )
     return result, scale, [layer.name for layer in dsn.layers]
 
@@ -149,6 +151,7 @@ def build_routing_result(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    rollback: bool = True,
 ) -> RoutingResult:
     """Route ``dsn`` (grid track) and convert to a DSN-unit RoutingResult."""
     route, scale, layer_names = route_dsn_board(
@@ -156,6 +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,
     )
     return _to_routing_result(route, dsn, scale, layer_names)
 
@@ -174,6 +178,7 @@ def route_dsn_board_exact(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    rollback: bool = True,
 ) -> 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.
@@ -201,6 +206,7 @@ def route_dsn_board_exact(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        rollback=rollback,
     )
     return exact, scale, [layer.name for layer in dsn.layers]
 
@@ -219,6 +225,7 @@ def build_exact_routing_result(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    rollback: bool = True,
 ) -> RoutingResult:
     """Route ``dsn`` (exact track) and convert to a DSN-unit RoutingResult."""
     exact, scale, layer_names = route_dsn_board_exact(
@@ -234,6 +241,7 @@ def build_exact_routing_result(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        rollback=rollback,
     )
     return _to_routing_result(exact.result, dsn, scale, layer_names)
 

tests/route/test_rollback.py

@@ -0,0 +1,43 @@
+"""--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,6 +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"],
     }
     for engine, options in ENGINE_OPTIONS.items():
         for option in options: