Keep a route's own vias apart while it is searched

Committed vias were checked for hole spacing, but a route's own vias are
not committed until it is done, so a route hopping layers (more of them
on 6 layers) could put two of its vias 0.41 mm apart, as th-eda's
6-layer flight controller showed. A via is now also checked against
layer changes earlier on its own route.

src/freeroute/board/build.py

@@ -23,6 +23,7 @@ the containment invariant, and pads are centre-symmetric in practice).
 from __future__ import annotations
 
 import math
+import re
 
 from freeroute.dsn.model import DsnBoard
 from freeroute.dsn.shapes import Circle, Path, Polygon, Rectangle, Shape
@@ -38,6 +39,9 @@ from .transform import CoordinateTransform
 
 __all__ = ["build_board"]
 
+# DSN units per micrometre, for drills KiCad gives in um in via padstack names
+_DSN_PER_UM = {"um": 1.0, "mm": 0.001, "mil": 1 / 25.4, "inch": 1 / 25400}
+
 
 def build_board(dsn: DsnBoard) -> BasicBoard:
     """Construct a :class:`BasicBoard` from a parsed :class:`DsnBoard`."""
@@ -503,10 +507,15 @@ def _insert_wiring(dsn: DsnBoard, board: BasicBoard, transform: CoordinateTransf
         location = transform.dsn_to_board_point(via.x, via.y)
         pad = _pad_tile(max(padstack.shapes, key=_shape_extent), transform)
         box = pad.bounding_box()
+        drill = re.search(r"_([\d.]+):([\d.]+)_um", via.padstack)
+        drill_board = (
+            round(transform.dsn_to_board(float(drill.group(2)) * _DSN_PER_UM.get(dsn.unit, 1.0)))
+            if drill else 0
+        )
         board.insert(
             Via(
                 net_nos=[numbers[via.net]], fixed=True, padstack_name=via.padstack,
-                location=location, layers=sorted(layers or signal_layers),
+                drill=drill_board, location=location, layers=sorted(layers or signal_layers),
                 shape=IntBox(box.ll.x + location.x, box.ll.y + location.y,
                              box.ur.x + location.x, box.ur.y + location.y),
             )

src/freeroute/board/items.py

@@ -117,6 +117,8 @@ class Via(Item):
     #: layer indices the via's pads occupy, and the largest pad as a box
     layers: list[int] = field(default_factory=list)
     shape: object = None
+    #: drill diameter in board units, when the padstack name gives it
+    drill: int = 0
 
 
 @dataclass

src/freeroute/route/grid_router.py

@@ -268,6 +268,8 @@ class GridRouter:
         self._via_nets: dict[Cell, dict[int, int]] = {}  # routed via centres
         self._via_centres: list[IntPoint] | None = None  # cache for _hole_clear_at
         self._fixed_vias: dict[Cell, int] = {}
+        # fixed vias sit anywhere, not on cell centres: exact hole checks
+        self._fixed_holes: list[tuple[IntPoint, int]] = []
         self._fixed_via_points: set[tuple[int, IntPoint]] = set()
 
         if layers is None:
@@ -301,6 +303,9 @@ class GridRouter:
             if isinstance(item, Via) and item.fixed and item.net_nos:
                 self._fixed_vias[self._cell_of(item.location)] = item.net_nos[0]
                 self._fixed_via_points.add((item.net_nos[0], item.location))
+                # its own drill, from KiCad's padstack name (Via[0-3]_500:250_um)
+                reach = self._via_drill // 2 + (item.drill or self._via_drill) // 2 + self._hole_gap
+                self._fixed_holes.append((item.location, reach))
         # Through-hole pads have holes too, and a route changes layer at one
         # for free, so no via (of any net) goes within hole spacing of one.
         # The DSN has no drill for a pad; its smaller half size stands in.
@@ -533,6 +538,26 @@ class GridRouter:
                     return False
         return self._holes_clear(cell, net_no)
 
+    def _near_path_via(self, node: Node, cell: Cell, came_from: dict) -> bool:
+        """A layer change earlier on the route that reaches ``node`` sits
+        within hole spacing of ``cell`` (and is not the same through via).
+        Committed vias are checked elsewhere; a route's own are not yet
+        committed while it is searched. Looks back far enough to cover the
+        hole spacing twice over, not along the whole route."""
+        limit = 4 * (math.ceil(self._hole_need / self.step) + 1)
+        need = self._hole_need / self.step
+        steps = 0
+        while node in came_from and steps < limit:
+            prev = came_from[node]
+            changes_layer = prev[:2] == node[:2] and prev[2] != node[2]
+            if changes_layer and node[:2] != cell and (
+                math.hypot(node[0] - cell[0], node[1] - cell[1]) < need
+            ):
+                return True
+            node = prev
+            steps += 1
+        return False
+
     def _via_nets_at(self, cell: Cell) -> set[int]:
         nets = {net for net, n in self._via_nets.get(cell, {}).items() if n > 0}
         fixed = self._fixed_vias.get(cell)
@@ -545,6 +570,12 @@ class GridRouter:
         and no through-hole pad's hole within reach at all."""
         if cell in self._tht_block:
             return False
+        if self._fixed_holes:
+            here = self._cell_center(cell)
+            for loc, reach in self._fixed_holes:
+                d = math.hypot(loc.x - here.x, loc.y - here.y)
+                if d < reach and d > self.step:  # beyond its own cell: too close
+                    return False
         if self._via_nets_at(cell) - {net_no}:
             return False
         cx, cy = cell
@@ -653,6 +684,8 @@ class GridRouter:
                     pin = ends.get(node)
                     if ok and isinstance(pin, Pin) and self._walled(node):
                         ok = self._via_fits_at(pin.location, net_no)
+                if ok and self._near_path_via(source, cell, came_from):
+                    ok = False  # too close to a via earlier on this same route
                 if ok:
                     self._relax(source, target, g_via, goal_cell, g_score, came_from, open_heap)
                 continue
@@ -664,6 +697,8 @@ class GridRouter:
                     ok = via_ok.get(cell)
                     if ok is None:
                         ok = via_ok[cell] = self._via_placeable(cell, net_no, conns)
+                    if ok and self._near_path_via(current, cell, came_from):
+                        ok = False
                 else:
                     ok = True
                 if ok:

tests/route/test_fixed_wiring.py

@@ -91,3 +91,18 @@ def test_a_fanned_out_signal_is_routed_from_its_via():
     assert sig in exact.result.routed_net_numbers
     assert not exact.result.vias.get(sig), "the fan-out via is already there"
     assert {names[layer] for layer, _ in exact.result.wires[sig]} == {"B.Cu"}
+
+
+def test_the_session_never_repeats_copper_already_on_the_board():
+    # the JAR writes the DSN's wiring back into its session, and an applier
+    # then adds it a second time on top of itself; freeroute writes only
+    # what it routed
+    from freeroute.route.pipeline import build_exact_routing_result
+
+    fixed_vias = {(5000.0, -11500.0), (10000.0, -11500.0)}
+    fixed_paths = {(5000.0, -10000.0, 5000.0, -11500.0), (10000.0, -10000.0, 10000.0, -11500.0),
+                   (2000.0, -2000.0, 8000.0, -2000.0)}
+    result = build_exact_routing_result(parse_dsn(_FANOUT), resolution=2)
+    for net in result.nets:
+        assert not {(v.x, v.y) for v in net.vias} & fixed_vias
+        assert not {tuple(w.coords) for w in net.wires} & fixed_paths

tests/route/test_via_spacing.py

@@ -56,7 +56,7 @@ def test_connections_sharing_a_plane_via_write_it_once():
     assert len(set(vias)) == len(vias), "a shared via written more than once"
 
 
-def _router(dsn_text):
+def _router(dsn_text, via_drill_um=300):
     from freeroute.board import build_board
     from freeroute.route.grid_router import GridRouter
     from freeroute.route.pipeline import _rule_clearance_dsn, _rule_width_dsn
@@ -66,7 +66,7 @@ def _router(dsn_text):
     return GridRouter(
         build_board(dsn), trace_width=round(_rule_width_dsn(dsn) * s),
         clearance=round(_rule_clearance_dsn(dsn) * s), resolution=2, orthogonal=True,
-        via_drill=300 * s, hole_to_hole=250 * s,
+        via_drill=via_drill_um * s, hole_to_hole=250 * s,
     ), s
 
 
@@ -98,3 +98,39 @@ def test_a_via_in_a_pad_keeps_hole_spacing_from_a_fixed_via():
     router, s = _router(text)
     assert not router._hole_clear_at(IntPoint(3400 * s, -3000 * s))  # 0.4 mm < 0.55 mm
     assert router._hole_clear_at(IntPoint(3600 * s, -3000 * s))
+
+
+def test_hole_spacing_from_a_fixed_via_is_measured_from_where_it_really_is():
+    # a fixed via off the grid with its own 0.25 mm drill, and the router's
+    # via a smaller 0.2 mm one (the flight controller's case): a new via needs
+    # its centre 0.1 + 0.125 + 0.25 = 0.475 mm away, measured exactly, where
+    # one rule for all vias gave 0.2 + 0.25 = 0.45 from the cell centres
+    text = _THT.replace("(network (net SIG (pins J1-1))))",
+                        "(network (net SIG (pins J1-1)) (net GND))\n"
+                        "  (wiring (via \"Via[0-1]_500:250_um\"  3030 -3030 (net GND) (type route))))")
+    text = text.replace(
+        '(attach off)))\n  (network',
+        '(attach off))\n    (padstack "Via[0-1]_500:250_um" (shape (circle F.Cu 500)) '
+        '(shape (circle B.Cu 500)) (attach off)))\n  (network',
+    )
+    router, s = _router(text, via_drill_um=200)
+    via = next(v for v in router.board.get_items() if getattr(v, "drill", 0))
+    assert via.drill == 250 * s
+    loc = via.location
+    for cell in [(x, y) for x in range(router.cols) for y in range(router.rows)]:
+        c = router._cell_center(cell)
+        d = math.hypot(c.x - loc.x, c.y - loc.y)
+        if router.step * 1.5 < d < 470 * s:
+            assert not router._holes_clear(cell, 1), f"{d / s:.0f} um from the fixed via"
+        elif 560 * s < d < 700 * s and cell not in router._tht_block:
+            assert router._holes_clear(cell, 1)
+
+
+def test_a_route_keeps_its_own_vias_apart():
+    # a route that changed layer at (10, 10) may not change layer again one
+    # cell away; the same cell is the same through via, and far is fine
+    router, _s = _router(_THT)
+    came_from = {(10, 10, 1): (10, 10, 0), (11, 10, 1): (10, 10, 1), (12, 10, 1): (11, 10, 1)}
+    assert router._near_path_via((12, 10, 1), (11, 10), came_from)
+    assert not router._near_path_via((12, 10, 1), (10, 10), came_from)
+    assert not router._near_path_via((12, 10, 1), (40, 10), came_from)