Test: a pad inside a via keepout reaches the plane past it

A start that was already a plane end joined the plane at once, with no
check that its via fits: under a sensor's via keepout the via went in
the pad and the exact check refused it. A via leaving or reaching a
walled-in pin goes in that pin's pad, but was only checked at the grid
cell's centre; it is now checked exactly at the pin against via
keepouts and other nets' pads and fixed copper.

src/freeroute/route/grid_router.py

@@ -311,6 +311,9 @@ class GridRouter:
         self._via_edge_block: set[Cell] = set()
         # wire keepouts as boxes, to check a pin stub the way the exact engine will
         self._keepout_boxes: dict[int, list[tuple[IntBox, bool]]] = {}
+        # via keepouts as boxes, and other copper a via in a pad must clear
+        self._via_keepout_boxes: list[tuple[IntBox, bool]] = []
+        self._static_copper: list[tuple[IntBox, int]] | None = None
         # pin end nodes no wire can reach without entering a keepout
         self._via_only: set[Node] = set()
         if outline is not None:
@@ -360,6 +363,8 @@ class GridRouter:
                             self._keepout.add((*cell, item.layer))
                         if item.blocks_vias:
                             self._via_keepout.add((*cell, item.layer))
+                    if item.blocks_vias:
+                        self._via_keepout_boxes.append((box, item.clearance))
 
     def _rasterize_fixed_copper(self) -> None:
         """Tracks and vias already on the board: copper of their net, which
@@ -452,7 +457,14 @@ class GridRouter:
         goals = self._group_ends(conn.b_group, conn.net_no, conns)
         if not starts or not goals:
             return None
-        common = sorted(set(starts) & set(goals))
+        # A start that is already an end joins at once, except that ending on
+        # a plane there needs a via: one that cannot be placed (a via keepout,
+        # another net's pad) is no end, and the search goes on from there.
+        common = [
+            n for n in sorted(set(starts) & set(goals))
+            if not isinstance(goals[n], ConductionArea)
+            or self._via_placeable((n[0], n[1]), conn.net_no, conns)
+        ]
         if common:
             conn.a_end, conn.b_end = starts[common[0]], goals[common[0]]
             return [common[0]]
@@ -485,6 +497,12 @@ class GridRouter:
                 ok = via_ok.get(cell)
                 if ok is None:
                     ok = via_ok[cell] = self._via_placeable(cell, net_no, conns)
+                # a via leaving or reaching a walled-in pin goes in its pad
+                # (see _commit), so it has to fit there exactly
+                for node, ends in ((source, starts), (target, goals)):
+                    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:
                     self._relax(source, target, g_via, goal_cell, g_score, came_from, open_heap)
                 continue
@@ -548,6 +566,29 @@ class GridRouter:
     # copper too, or a stub ends up closer than clearance to a trace in the
     # cell beside it.
 
+    def _walled(self, node: Node) -> bool:
+        """A pin end no wire may leave or reach: only a via in its pad will do."""
+        return node in self._keepout or node in self._via_only
+
+    def _via_fits_at(self, point: IntPoint, net_no: int) -> bool:
+        """A via centred exactly on ``point`` clears every via keepout and all
+        other nets' pads and fixed copper (what a via in a pad must meet)."""
+        via = IntBox(point.x - self.via_half, point.y - self.via_half,
+                     point.x + self.via_half, point.y + self.via_half)
+        grown = via.offset(self.clearance)
+        for box, needs in self._via_keepout_boxes:
+            if box.overlaps(grown if needs else via):
+                return False
+        if self._static_copper is None:
+            copper = [
+                (p.shape.bounding_box(), p.net_nos[0] if p.net_nos else -1)
+                for p in self.board.get_pins()
+                if p.shape is not None and any(layer in self.layers for layer in p.layers)
+            ]
+            copper += [(box, net) for net, _, box in self.board.get_fixed_copper()]
+            self._static_copper = copper
+        return not any(net != net_no and box.overlaps(grown) for box, net in self._static_copper)
+
     def _stub_cells(self, pin_location: IntPoint, cell: Cell) -> list[Cell]:
         """Cells where another net's trace would come too close to the stub."""
         from freeroute.board.outline import _point_segment

tests/route/test_real_board_geometry.py

@@ -223,3 +223,29 @@ def test_a_through_hole_pad_inside_a_plane_needs_no_route():
     groups = _connected_groups(gnd_pins, plane, frozenset(id(z) for z in plane))
     hub = next(g for g in groups if g[1])
     assert [p.component_ref for p in hub[0]] == ["GT"]
+
+
+def test_a_pad_inside_a_via_keepout_reaches_the_plane_by_a_via_outside_it():
+    # a sensor's GND pad: vias are forbidden under the body, so the route
+    # has to leave on the top layer and drop to the plane past the keepout
+    dsn = parse_dsn("""(pcb repro (parser) (resolution um 10) (unit um)
+  (structure
+    (layer F.Cu (type signal)) (layer In1.Cu (type power)) (layer In2.Cu (type power))
+    (layer B.Cu (type signal))
+    (boundary (path pcb 0  0 0  20000 0  20000 -20000  0 -20000  0 0))
+    (plane GND (polygon In1.Cu 0  500 -500  19500 -500  19500 -19500  500 -19500  500 -500))
+    (via_keepout "" (polygon signal 0  8500 -8500  11500 -8500  11500 -11500  8500 -11500  8500 -8500))
+    (via "Via[0-3]_600:300_um") (rule (width 150) (clearance 150)))
+  (placement (component S (place G1 10000 -10000 front 0)))
+  (library
+    (image S (pin smd 1 0 0))
+    (padstack smd (shape (rect F.Cu -175 -300 175 300)) (attach off))
+    (padstack "Via[0-3]_600:300_um" (shape (circle F.Cu 600)) (shape (circle B.Cu 600)) (attach off)))
+  (network (net GND (pins G1-1))))""")
+    exact, scale, _names = route_dsn_board_exact(dsn, resolution=2)
+    assert exact.result.failed == []
+    (via,) = exact.result.vias[1]
+    half = 300 * scale  # the via's radius
+    outside = (via.x + half <= 8500 * scale or via.x - half >= 11500 * scale
+               or via.y - half >= -8500 * scale or via.y + half <= -11500 * scale)
+    assert outside, f"via at {via} is inside the via keepout"