--fanout: leave out pins a same-net pour on their layer already joins

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,10 @@ 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
+    #: placed by the router's fan-out, not on the board yet: written out
+    generated: bool = False
 
 
 @dataclass
@@ -130,6 +134,8 @@ class Trace(Item):
     layer: int = 0
     half_width: int = 0
     corners: list[IntPoint] = field(default_factory=list)
+    #: placed by the router's fan-out, not on the board yet: written out
+    generated: bool = False
 
     def is_empty(self) -> bool:
         return len(self.corners) < 2

src/freeroute/cli.py

@@ -30,8 +30,11 @@ 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", "rollback", "fanout"}),
+    "exact": frozenset(
+        {"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access",
+         "rollback", "fanout"}
+    ),
     "room": frozenset({"shove", "pack"}),
 }
 
@@ -47,6 +50,7 @@ _FLAG_NAMES = {
     "promote": "--promote-failures",
     "access": "--access-cost",
     "rollback": "--no-rollback",
+    "fanout": "--fanout",
 }
 
 
@@ -183,6 +187,22 @@ def build_parser() -> argparse.ArgumentParser:
         help="grid and exact engines: least distance between the edges of any two via "
         "holes, of one net or two (KiCad's min_hole_to_hole; default 0.25)",
     )
+    parser.add_argument(
+        "--fanout",
+        nargs="?",
+        const="all",
+        choices=["all", "supply"],
+        help="grid and exact engines: before routing, give every fine-pitch pin a stub "
+        "outward past its pad row (and a via to its plane, for a plane net), committed "
+        "as copper so later routes cannot wall it in; --fanout supply: plane pins only",
+    )
+    parser.add_argument(
+        "--fanout-min-pins",
+        type=int,
+        default=32,
+        metavar="N",
+        help="with --fanout: fan out only packages with at least N fine-pitch pins (default 32)",
+    )
     parser.add_argument(
         "--jobs",
         type=int,
@@ -213,6 +233,7 @@ def main(argv: list[str] | None = None) -> int:
             ("promote", args.promote_failures is not None),
             ("access", args.access_cost is not None),
             ("rollback", not args.rollback),
+            ("fanout", bool(args.fanout)),
         )
         if asked
     ]
@@ -248,6 +269,8 @@ def main(argv: list[str] | None = None) -> int:
             "heuristic_weight": args.heuristic_weight,
             "access_cost": args.access_cost or 0.0,
             "hole_to_hole_mm": args.hole_to_hole,
+            "fanout": args.fanout or False,
+            "fanout_min_pins": args.fanout_min_pins,
             "rollback": args.rollback,
         }
     elif args.engine == "grid":
@@ -259,6 +282,8 @@ def main(argv: list[str] | None = None) -> int:
             "resolution": 1 if args.grid_resolution is None else args.grid_resolution,
             "access_cost": args.access_cost or 0.0,
             "hole_to_hole_mm": args.hole_to_hole,
+            "fanout": args.fanout or False,
+            "fanout_min_pins": args.fanout_min_pins,
             "rollback": args.rollback,
         }
     if args.engine == "room":

src/freeroute/route/exact_router.py

@@ -215,7 +215,8 @@ def route_board_exact(
         # connections of one net that end on the same plane cell share its
         # via: write it once, and never on top of a via already on the board
         acc.vias.extend(
-            v for v in dict.fromkeys(vias) if v not in acc.vias and (net_no, v) not in fixed_vias
+            v for v in dict.fromkeys(vias)
+            if v not in acc.vias and not _on_fixed_via(net_no, v, fixed_vias, via_half)
         )
         for box, box_layers in boxes:
             oid = next(owner)
@@ -645,6 +646,15 @@ def _end_in_rule_area(tree, wires, half_width) -> bool:
     return False
 
 
+def _on_fixed_via(net_no, point, fixed_vias, via_half) -> bool:
+    """A routed via that reuses a via already on the board: the grid put it
+    on the fixed via's cell, a little off its centre, and it is not written."""
+    return any(
+        net == net_no and abs(loc.x - point.x) <= via_half and abs(loc.y - point.y) <= via_half
+        for net, loc in fixed_vias
+    )
+
+
 def _copper_boxes(wires, vias, half_width, via_layers, via_half=None):
     via_half = via_half or half_width
     boxes: list[tuple[IntBox, frozenset[int]]] = []

src/freeroute/route/fanout.py

@@ -0,0 +1,229 @@
+"""Fan out fine-pitch pins before routing: commit each pin's way out as copper.
+
+On a dense board the pins of a fine-pitch package get walled in: their own
+neighbours' pads on either side, and other nets' copper that got there first
+across the only way out. Reserving the way out did not help (the reserved
+cells still had to be routed, and lost to congestion there); committing it
+does, which is what a person does by hand.
+
+Each fine-pitch pin of a perimeter package (QFP, QFN, LGA: pads on the edge,
+none inside) gets a straight stub outward, perpendicular to its side of the
+package, just past its pad row. A pin whose net has an inner plane also gets
+a via at the stub's end, staggered between neighbouring pins so their holes
+keep their spacing, and so reaches the plane with nothing left to route.
+Every stub and via is checked exactly against pads, keepouts, the board edge,
+copper already on the board and earlier fan-out, and left out where it would
+not fit. The result goes on the board as fixed copper of its net (marked
+``generated``), so the router starts from the stub's end or the via, and the
+session writes it out with the routes.
+"""
+
+from __future__ import annotations
+
+from dataclasses import dataclass
+import math
+
+from freeroute.board.board import BasicBoard
+from freeroute.board.items import Pin, Trace, Via
+from freeroute.geometry import IntBox, IntPoint
+from freeroute.geometry.polyline import Polyline, PolylineShape, corner_box
+
+# a package is fanned out when it has this many pins and they are this close
+_MIN_PINS = 8
+_FINE_PITCH_FACTOR = 1.2  # neighbour centres within this many (trace + 2 clearance)
+
+
+@dataclass
+class FanoutRules:
+    trace_width: int
+    clearance: int
+    via_half: int
+    via_drill: int
+    hole_to_hole: int
+    edge_clearance: int
+    signal_layers: list[int]
+    via_padstack: str
+    #: smallest package fanned out (a big dense part is where pins get walled in)
+    min_pins: int = 32
+    #: fan out plane pins only (a stub and a via each), as a person would first
+    supply_only: bool = False
+
+
+def plan_fanout(board: BasicBoard, rules: FanoutRules) -> list:
+    """The stubs and vias to put on the board before routing."""
+    half = max(rules.trace_width // 2, 1)
+    # a net may have several plane zones (a main plane and an island)
+    planes: dict[int, list] = {}
+    for z in board.get_conduction_areas():
+        if z.net_nos and not board.layer_structure.arr[z.layer].is_signal:
+            planes.setdefault(z.net_nos[0], []).append(z)
+    # copper pours on the routing layers, by net: a pad inside one is joined
+    # by the fill, and a stub there would take the room its thermal spokes need
+    pours: dict[int, list] = {}
+    for z in board.get_conduction_areas():
+        if z.net_nos and board.layer_structure.arr[z.layer].is_signal:
+            pours.setdefault(z.net_nos[0], []).append(z)
+    placed = _Placed(board, rules)
+    by_net: dict[int, list[Pin]] = {}
+    for pin in board.get_pins():
+        for n in pin.net_nos:
+            by_net.setdefault(n, []).append(pin)
+    items: list = []
+    pitch = 2 * rules.via_half + rules.hole_to_hole
+    for pins in _packages(board, rules).values():
+        centre = IntPoint(
+            sum(p.location.x for p in pins) // len(pins), sum(p.location.y for p in pins) // len(pins)
+        )
+        for k, pin in enumerate(sorted(pins, key=lambda p: (p.location.x, p.location.y))):
+            net = pin.net_nos[0] if pin.net_nos else None
+            if net is None:
+                continue
+            layer = next(layer for layer in pin.layers if layer in rules.signal_layers)
+            if any(z.layer == layer and z.polygon is not None and z.polygon.contains(pin.location)
+                   for z in pours.get(net, [])):
+                continue  # the pour joins it
+            direction = _outward(pin.location, centre)
+            reach = _pad_reach(pin, direction) + rules.clearance + half + rules.trace_width
+            end = _step(pin.location, direction, reach)
+            plane = planes.get(net)
+            partners = [q for q in by_net.get(net, []) if q is not pin]
+            # a signal whose other pins are all on other layers has to change
+            # layer somewhere: do it at the stub's end, away from the pads
+            elsewhere = bool(partners) and all(layer not in q.layers for q in partners)
+            if plane is None and (rules.supply_only or not elsewhere):
+                if not rules.supply_only and placed.stub_fits(pin.location, end, layer, net, half):
+                    items.append(placed.add_stub(pin.location, end, layer, net, half))
+                continue
+            # stagger the via of every other pin along the side outward
+            options = [reach + rules.via_half + rules.clearance + (k % 2) * pitch,
+                       reach + rules.via_half + rules.clearance + ((k + 1) % 2) * pitch]
+            for d in options:
+                at = _step(pin.location, direction, d)
+                if plane is not None and not any(
+                    z.polygon is not None and z.polygon.contains(at) for z in plane
+                ):
+                    continue
+                if placed.stub_fits(pin.location, at, layer, net, half) and placed.via_fits(at, net):
+                    items.append(placed.add_stub(pin.location, at, layer, net, half))
+                    items.append(placed.add_via(at, net))
+                    break
+    return items
+
+
+def _packages(board: BasicBoard, rules: FanoutRules) -> dict[str, list[Pin]]:
+    """Fine-pitch perimeter packages: many single-layer pins, close together."""
+    by_ref: dict[str, list[Pin]] = {}
+    for pin in board.get_pins():
+        if pin.shape is None or not pin.component_ref:
+            continue
+        on = [layer for layer in pin.layers if layer in rules.signal_layers]
+        if len(on) != 1:
+            continue  # through-hole pins change layer for free
+        by_ref.setdefault(pin.component_ref, []).append(pin)
+    fine = _FINE_PITCH_FACTOR * (rules.trace_width + 2 * rules.clearance)
+    out = {}
+    for ref, pins in by_ref.items():
+        if len(pins) < max(rules.min_pins, _MIN_PINS):
+            continue
+        close = sum(
+            1 for p in pins
+            if min(math.hypot(p.location.x - q.location.x, p.location.y - q.location.y)
+                   for q in pins if q is not p) < fine * 2
+        )
+        if close >= len(pins) // 2:
+            out[ref] = pins
+    return out
+
+
+def _outward(point: IntPoint, centre: IntPoint) -> tuple[int, int]:
+    """Away from the package centre, along the nearer axis (its side's normal)."""
+    dx, dy = point.x - centre.x, point.y - centre.y
+    if abs(dx) >= abs(dy):
+        return (1 if dx >= 0 else -1, 0)
+    return (0, 1 if dy >= 0 else -1)
+
+
+def _pad_reach(pin: Pin, direction: tuple[int, int]) -> int:
+    """How far the pad reaches from its centre in ``direction``."""
+    box = pin.shape.bounding_box()
+    if direction[0] > 0:
+        return box.ur.x - pin.location.x
+    if direction[0] < 0:
+        return pin.location.x - box.ll.x
+    if direction[1] > 0:
+        return box.ur.y - pin.location.y
+    return pin.location.y - box.ll.y
+
+
+def _step(point: IntPoint, direction: tuple[int, int], distance: float) -> IntPoint:
+    return IntPoint(point.x + round(direction[0] * distance), point.y + round(direction[1] * distance))
+
+
+class _Placed:
+    """Copper a fan-out stub or via has to clear, growing as fan-out is placed."""
+
+    def __init__(self, board: BasicBoard, rules: FanoutRules) -> None:
+        self.board, self.rules = board, rules
+        self.copper: list[tuple[IntBox, frozenset[int], int]] = []  # box, layers, net
+        for pin in board.get_pins():
+            if pin.shape is not None:
+                net = pin.net_nos[0] if pin.net_nos else -1
+                self.copper.append((pin.shape.bounding_box(), frozenset(pin.layers), net))
+        for net, layers, box in board.get_fixed_copper():
+            self.copper.append((box, layers, net))
+        self.keepouts = [
+            (tile.bounding_box(), o.layer, o.blocks_wires, o.blocks_vias, o.clearance)
+            for o in board.get_obstacle_areas() for tile in o.tiles
+        ]
+        self.holes: list[tuple[IntPoint, int]] = []  # centre, radius
+        for item in board.get_items():
+            if isinstance(item, Via) and item.fixed:
+                self.holes.append((item.location, (item.drill or rules.via_drill) // 2))
+        for pin in board.get_pins():
+            if pin.shape is not None and sum(1 for layer in pin.layers if layer in rules.signal_layers) > 1:
+                b = pin.shape.bounding_box()
+                self.holes.append((pin.location, min(b.ur.x - b.ll.x, b.ur.y - b.ll.y) // 2))
+
+    def _clear(self, box: IntBox, layers: frozenset[int], net: int, kind: str) -> bool:
+        grown = box.offset(self.rules.clearance)
+        for other, other_layers, other_net in self.copper:
+            if other_net != net and layers & other_layers and other.overlaps(grown):
+                return False
+        for kbox, klayer, wires, vias, needs in self.keepouts:
+            if klayer not in layers or not (wires if kind == "wire" else vias):
+                continue
+            if kbox.overlaps(grown if needs else box):
+                return False
+        outline = self.board.outline
+        return outline is None or outline.box_clear(box, self.rules.edge_clearance)
+
+    def stub_fits(self, a: IntPoint, b: IntPoint, layer: int, net: int, half: int) -> bool:
+        boxes = list(PolylineShape(Polyline([a, b]), half).tiles()) + [corner_box(b, half)]
+        return all(self._clear(box, frozenset({layer}), net, "wire") for box in boxes)
+
+    def via_fits(self, at: IntPoint, net: int) -> bool:
+        h = self.rules.via_half
+        box = IntBox(at.x - h, at.y - h, at.x + h, at.y + h)
+        if not self._clear(box, frozenset(self.rules.signal_layers), net, "via"):
+            return False
+        mine = self.rules.via_drill // 2
+        return all(
+            math.hypot(c.x - at.x, c.y - at.y) >= mine + r + self.rules.hole_to_hole
+            for c, r in self.holes
+        )
+
+    def add_stub(self, a: IntPoint, b: IntPoint, layer: int, net: int, half: int) -> Trace:
+        for box in list(PolylineShape(Polyline([a, b]), half).tiles()) + [corner_box(b, half)]:
+            self.copper.append((box, frozenset({layer}), net))
+        return Trace(net_nos=[net], fixed=True, layer=layer, half_width=half, corners=[a, b],
+                     generated=True)
+
+    def add_via(self, at: IntPoint, net: int) -> Via:
+        h = self.rules.via_half
+        box = IntBox(at.x - h, at.y - h, at.x + h, at.y + h)
+        layers = list(self.rules.signal_layers)
+        self.copper.append((box, frozenset(layers), net))
+        self.holes.append((at, self.rules.via_drill // 2))
+        return Via(net_nos=[net], fixed=True, padstack_name=self.rules.via_padstack,
+                   location=at, layers=layers, shape=box, drill=self.rules.via_drill,
+                   generated=True)

src/freeroute/route/grid_router.py

@@ -257,6 +257,7 @@ class GridRouter:
         # an own-net via at the very same cell, which it simply reuses.
         drill = via_drill if via_drill else 2 * self.via_half
         need = drill + max(hole_to_hole, 0)
+        self._via_drill, self._hole_gap, self._hole_need = drill, max(hole_to_hole, 0), need
         reach = math.ceil(need / self.step)
         self._hole_offsets = [
             (dx, dy)
@@ -265,7 +266,10 @@ class GridRouter:
             if (dx or dy) and math.hypot(dx, dy) * self.step < need
         ]
         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:
@@ -299,6 +303,24 @@ 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.
+        self._tht_holes: list[tuple[IntPoint, int]] = []
+        self._tht_block: set[Cell] = set()
+        for pin in board.get_pins():
+            if pin.shape is None or sum(1 for layer in pin.layers if layer in self.layers) < 2:
+                continue
+            box = pin.shape.bounding_box()
+            radius = min(box.ur.x - box.ll.x, box.ur.y - box.ll.y) // 2
+            reach = radius + self._via_drill // 2 + self._hole_gap
+            self._tht_holes.append((pin.location, reach))
+            ring = IntBox(pin.location.x, pin.location.y, pin.location.x, pin.location.y)
+            for cell in self._cells_in_box(ring, reach):
+                self._tht_block.add(cell)
 
     # --- grid helpers -------------------------------------------------------
 
@@ -516,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)
@@ -524,7 +566,16 @@ class GridRouter:
         return nets
 
     def _holes_clear(self, cell: Cell, net_no: int) -> bool:
-        """No via centre within hole-to-hole reach, but an own-net one here."""
+        """No via centre within hole-to-hole reach, but an own-net one here,
+        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
@@ -633,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
@@ -644,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:
@@ -717,7 +772,23 @@ class GridRouter:
             ]
             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)
+        if any(net != net_no and box.overlaps(grown) for box, net in self._static_copper):
+            return False
+        return self._hole_clear_at(point)
+
+    def _hole_clear_at(self, point: IntPoint) -> bool:
+        """Hole spacing measured exactly from ``point`` to every via and
+        through-hole pad (a via moved into a pad is not on its cell's centre)."""
+        need = self._hole_need
+        if self._via_centres is None:  # rebuilt only after vias change
+            self._via_centres = [loc for _net, loc in self._fixed_via_points] + [
+                self._cell_center(c) for c, count in self._via_nets.items() if any(count.values())
+            ]
+        if any(math.hypot(c.x - point.x, c.y - point.y) < need for c in self._via_centres):
+            return False
+        return not any(
+            math.hypot(loc.x - point.x, loc.y - point.y) < reach for loc, reach in self._tht_holes
+        )
 
     def _stub_cells(self, pin_location: IntPoint, cell: Cell, half: int | None = None) -> list[Cell]:
         """Cells where another net's trace would come too close to the stub."""
@@ -993,6 +1064,8 @@ class GridRouter:
         for cell in conn.via_cells:
             count = self._via_nets.setdefault(cell, {})
             count[conn.net_no] = count.get(conn.net_no, 0) + 1
+        if conn.via_cells:
+            self._via_centres = None
         for cell, layer in conn.trace_cells:
             self._cell_owner[(*cell, layer)] = conn.index
         conn.half = half = self._conn_half(conn)
@@ -1071,6 +1144,8 @@ class GridRouter:
             count = self._via_nets.get(cell)
             if count and count.get(conn.net_no):
                 count[conn.net_no] -= 1
+        if conn.via_cells:
+            self._via_centres = None
         conn.via_cells = []
         conn.wires = []
         conn.vias = []
@@ -1285,7 +1360,7 @@ class GridRouter:
                 elif isinstance(item, Trace) and not item.is_empty():
                     boxes = list(PolylineShape(Polyline(item.corners), item.half_width).tiles())
                     boxes += [corner_box(e, item.half_width) for e in (item.corners[0], item.corners[-1])]
-                    piece = _FixedPiece([item.layer], boxes)
+                    piece = _FixedPiece([item.layer], boxes, trace=item)
                 else:
                     continue
                 cache.setdefault(item.net_nos[0], []).append(piece)
@@ -1407,12 +1482,13 @@ def _fixed_joins_zone(piece, zone, plane: bool) -> bool:
 class _FixedPiece:
     """One track or via already on the board, as connectivity."""
 
-    __slots__ = ("layers", "boxes", "via")
+    __slots__ = ("layers", "boxes", "via", "trace")
 
-    def __init__(self, layers, boxes, via=None) -> None:
+    def __init__(self, layers, boxes, via=None, trace=None) -> None:
         self.layers = frozenset(layers)
         self.boxes = boxes
         self.via = via  # the Via item, for a via
+        self.trace = trace  # the Trace item, for a track
 
 
 def _connected_groups(
@@ -1473,11 +1549,28 @@ def _connected_groups(
         groups[root][1].append(zone)
     for k, piece in enumerate(fixed):
         root = find(base + k)
-        if piece.via is not None and root in groups:
+        if root not in groups:
+            continue
+        if piece.via is not None:
             groups[root][0].append(_via_end(piece.via))
+        elif piece.trace is not None:
+            # a track's ends are places a route may start: a fan-out stub's
+            # far end is outside the pad row the pin sat walled in by
+            for end in (piece.trace.corners[0], piece.trace.corners[-1]):
+                groups[root][0].append(_trace_end(piece.trace, end))
     return [groups[r] for r in order]
 
 
+def _trace_end(trace, end: IntPoint) -> Pin:
+    """An end of a fixed track as a place a route may start or end."""
+    from freeroute.geometry.polyline import corner_box
+
+    return Pin(
+        net_nos=list(trace.net_nos), fixed=True, name="track", component_ref="",
+        location=end, layers=[trace.layer], shape=corner_box(end, trace.half_width),
+    )
+
+
 def _via_end(via) -> Pin:
     """A fixed via as a place a route may start or end (not a pad to route)."""
     return Pin(

src/freeroute/route/pipeline.py

@@ -88,6 +88,42 @@ def _dsn_units_per_um(dsn: DsnBoard) -> float:
     return {"um": 1.0, "mm": 0.001, "mil": 1 / 25.4, "inch": 1 / 25400}.get(dsn.unit, 1.0)
 
 
+def _place_fanout(
+    board, dsn, scale, layers, width, clearance, edge, hole_to_hole_mm, mode=True, min_pins=32
+) -> None:
+    """Put the fan-out's stubs and vias on the board, before routing."""
+    from .fanout import FanoutRules, plan_fanout
+
+    via_half = _via_half_board(dsn, scale) or max(width // 2, 1)
+    rules = FanoutRules(
+        trace_width=width,
+        clearance=clearance,
+        via_half=via_half,
+        via_drill=_via_drill_board(dsn, scale) or 2 * via_half,
+        hole_to_hole=_mm_to_board(dsn, scale, hole_to_hole_mm) or 0,
+        edge_clearance=edge or 0,
+        signal_layers=layers or [i for i, layer in enumerate(dsn.layers) if layer.is_signal],
+        via_padstack=_via_padstack(dsn),
+        min_pins=min_pins,
+        supply_only=mode == "supply",
+    )
+    for item in plan_fanout(board, rules):
+        board.insert(item)
+
+
+def _add_generated(result, board) -> None:
+    """The fan-out's copper goes into the session with the routes."""
+    from freeroute.board.items import Trace, Via
+
+    for item in board.get_items():
+        if not getattr(item, "generated", False) or not item.net_nos:
+            continue
+        if isinstance(item, Trace):
+            result.add_wire(item.net_nos[0], item.layer, list(item.corners))
+        elif isinstance(item, Via):
+            result.add_via(item.net_nos[0], item.location)
+
+
 def _via_half_board(dsn: DsnBoard, scale: int) -> int | None:
     """Half the via pad's size in board units, from the DSN's via padstack.
 
@@ -119,6 +155,8 @@ def route_dsn_board(
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
     hole_to_hole_mm: float = 0.25,
+    fanout: bool | str = False,
+    fanout_min_pins: int = 32,
     rollback: bool = True,
 ) -> tuple[RouteResult, int, list[str]]:
     """Route a parsed :class:`DsnBoard`; return the board-unit result, the scale,
@@ -130,6 +168,9 @@ def route_dsn_board(
     edge_clearance_board = _mm_to_board(dsn, scale, edge_clearance_mm)
     width_board = round(_rule_width_dsn(dsn) * scale)
     clearance_board = round(_rule_clearance_dsn(dsn) * scale)
+    if fanout:
+        _place_fanout(board, dsn, scale, layers, width_board, clearance_board,
+                      edge_clearance_board, hole_to_hole_mm, fanout, fanout_min_pins)
     result = route_board(
         board,
         resolution=resolution,
@@ -148,6 +189,7 @@ def route_dsn_board(
         via_drill=_via_drill_board(dsn, scale),
         hole_to_hole=_mm_to_board(dsn, scale, hole_to_hole_mm) or 0,
     )
+    _add_generated(result, board)
     return result, scale, [layer.name for layer in dsn.layers]
 
 
@@ -197,6 +239,8 @@ def build_routing_result(
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
     hole_to_hole_mm: float = 0.25,
+    fanout: bool | str = False,
+    fanout_min_pins: int = 32,
     rollback: bool = True,
 ) -> RoutingResult:
     """Route ``dsn`` (grid track) and convert to a DSN-unit RoutingResult."""
@@ -206,6 +250,8 @@ def build_routing_result(
         route_first=route_first,
         access_cost=access_cost,
         hole_to_hole_mm=hole_to_hole_mm,
+        fanout=fanout,
+        fanout_min_pins=fanout_min_pins,
         rollback=rollback,
     )
     return _to_routing_result(route, dsn, scale, layer_names)
@@ -226,6 +272,8 @@ def route_dsn_board_exact(
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
     hole_to_hole_mm: float = 0.25,
+    fanout: bool | str = False,
+    fanout_min_pins: int = 32,
     rollback: bool = True,
 ) -> tuple[ExactRouteResult, int, list[str]]:
     """Route a parsed :class:`DsnBoard` with the exact-geometry (orthogonal,
@@ -238,6 +286,9 @@ def route_dsn_board_exact(
     edge_clearance_board = _mm_to_board(dsn, scale, edge_clearance_mm)
     width_board = round(_rule_width_dsn(dsn) * scale)
     clearance_board = round(_rule_clearance_dsn(dsn) * scale)
+    if fanout:
+        _place_fanout(board, dsn, scale, layers, width_board, clearance_board,
+                      edge_clearance_board, hole_to_hole_mm, fanout, fanout_min_pins)
     exact = route_board_exact(
         board,
         resolution=resolution,
@@ -259,6 +310,7 @@ def route_dsn_board_exact(
         via_drill=_via_drill_board(dsn, scale),
         hole_to_hole=_mm_to_board(dsn, scale, hole_to_hole_mm) or 0,
     )
+    _add_generated(exact.result, board)
     return exact, scale, [layer.name for layer in dsn.layers]
 
 
@@ -277,6 +329,8 @@ def build_exact_routing_result(
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
     hole_to_hole_mm: float = 0.25,
+    fanout: bool | str = False,
+    fanout_min_pins: int = 32,
     rollback: bool = True,
 ) -> RoutingResult:
     """Route ``dsn`` (exact track) and convert to a DSN-unit RoutingResult."""
@@ -294,6 +348,8 @@ def build_exact_routing_result(
         route_first=route_first,
         access_cost=access_cost,
         hole_to_hole_mm=hole_to_hole_mm,
+        fanout=fanout,
+        fanout_min_pins=fanout_min_pins,
         rollback=rollback,
     )
     return _to_routing_result(exact.result, dsn, scale, layer_names)

tests/route/test_fanout.py

@@ -0,0 +1,78 @@
+"""--fanout: fine-pitch pins get their way out committed before routing."""
+
+from __future__ import annotations
+
+from freeroute.board import build_board
+from freeroute.board.items import Trace, Via
+from freeroute.dsn import parse_dsn
+from freeroute.route.fanout import FanoutRules, plan_fanout
+from freeroute.route.pipeline import route_dsn_board_exact
+
+# a 12-pad package, 3 pads a side at 0.5 mm pitch, over a GND plane on In1;
+# pad 1 (left side, top) is GND, the rest are signals to far connector pads
+_SIDES = {
+    "L": [(-2000, y, 0) for y in (500, 0, -500)],
+    "R": [(2000, y, 0) for y in (500, 0, -500)],
+    "T": [(x, 2000, 90) for x in (-500, 0, 500)],
+    "B": [(x, -2000, 90) for x in (-500, 0, 500)],
+}
+_PADS = [p for side in "LRTB" for p in _SIDES[side]]
+
+
+def _dsn():
+    pins = "\n      ".join(
+        f"(pin {'padv' if r else 'padh'} {i + 1} {x} {y})" for i, (x, y, r) in enumerate(_PADS)
+    )
+    far = " ".join(f"(place C{i} {3000 + 2000 * (i % 5)} {-12000 - 2000 * (i // 5)} front 0)" for i in range(11))
+    nets = "(net GND (pins U1-1))\n    " + "\n    ".join(f"(net S{i} (pins U1-{i + 2} C{i}-1))" for i in range(11))
+    return f"""(pcb pkg (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  -15000 15000  25000 15000  25000 -25000  -15000 -25000  -15000 15000))
+    (plane GND (polygon In1.Cu 0  -14500 14500  24500 14500  24500 -24500  -14500 -24500  -14500 14500))
+    (via "Via[0-3]_450:200_um") (rule (width 150) (clearance 150)))
+  (placement (component Q (place U1 0 0 front 0)) (component P {far}))
+  (library
+    (image Q
+      {pins})
+    (image P (pin padc 1 0 0))
+    (padstack padh (shape (rect F.Cu -400 -125 400 125)) (attach off))
+    (padstack padv (shape (rect F.Cu -125 -400 125 400)) (attach off))
+    (padstack padc (shape (rect F.Cu -500 -500 500 500)) (attach off))
+    (padstack "Via[0-3]_450:200_um" (shape (circle F.Cu 450)) (shape (circle B.Cu 450)) (attach off)))
+  (network {nets}))"""
+
+
+def _rules(dsn):
+    s = dsn.resolution.value
+    return FanoutRules(trace_width=150 * s, clearance=150 * s, via_half=225 * s, via_drill=200 * s,
+                       hole_to_hole=250 * s, edge_clearance=0, signal_layers=[0, 3],
+                       via_padstack="Via[0-3]_450:200_um", min_pins=8)
+
+
+def test_every_pin_gets_a_stub_outward_past_its_pad():
+    dsn = parse_dsn(_dsn())
+    board = build_board(dsn)
+    items = plan_fanout(board, _rules(dsn))
+    stubs = [i for i in items if isinstance(i, Trace)]
+    assert len(stubs) == 12
+    for stub in stubs:
+        a, b = stub.corners
+        pin = next(p for p in board.get_pins() if p.location == a)
+        pad = pin.shape.bounding_box()
+        # outward: the stub ends further from the package centre, outside its pad
+        assert abs(b.x) + abs(b.y) > abs(a.x) + abs(a.y)
+        assert not (pad.ll.x <= b.x <= pad.ur.x and pad.ll.y <= b.y <= pad.ur.y)
+
+
+def test_a_plane_pin_gets_a_via_and_needs_no_route():
+    dsn = parse_dsn(_dsn())
+    board = build_board(dsn)
+    items = plan_fanout(board, _rules(dsn))
+    assert len([i for i in items if isinstance(i, Via)]) == 1
+    exact, _scale, _ = route_dsn_board_exact(dsn, resolution=2, fanout=True, fanout_min_pins=8)
+    gnd = next(i + 1 for i, n in enumerate(dsn.nets) if n.name == "GND")
+    assert not any(f[0] == gnd for f in exact.result.failed)
+    assert exact.drc_clean
+    assert len(exact.result.vias.get(gnd, [])) == 1  # the fan-out's, written out

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

@@ -54,3 +54,83 @@ def test_connections_sharing_a_plane_via_write_it_once():
     vias = exact.result.vias[1]
     assert len(vias) < 8, "no via is shared, so this board no longer tests sharing"
     assert len(set(vias)) == len(vias), "a shared via written more than once"
+
+
+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
+
+    dsn = parse_dsn(dsn_text)
+    s = dsn.resolution.value
+    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=via_drill_um * s, hole_to_hole=250 * s,
+    ), s
+
+
+_THT = """(pcb tht (parser) (resolution um 10) (unit um)
+  (structure (layer F.Cu (type signal)) (layer B.Cu (type signal))
+    (boundary (path pcb 0  0 0  20000 0  20000 -20000  0 -20000  0 0))
+    (via "Via[0-1]_500:300_um") (rule (width 150) (clearance 150)))
+  (placement (component T (place J1 10000 -10000 front 0)))
+  (library (image T (pin tht 1 0 0))
+    (padstack tht (shape (circle F.Cu 1700)) (shape (circle B.Cu 1700)) (attach off))
+    (padstack "Via[0-1]_500:300_um" (shape (circle F.Cu 500)) (shape (circle B.Cu 500)) (attach off)))
+  (network (net SIG (pins J1-1))))"""
+
+
+def test_no_via_goes_near_a_through_hole_pads_hole_even_of_its_own_net():
+    router, s = _router(_THT)
+    pin = router._cell_of(router.board.get_pins()[0].location)
+    assert not router._holes_clear(pin, 1)  # own net, right on the pad
+    far = (pin[0] + 40, pin[1])
+    assert router._holes_clear(far, 1)
+
+
+def test_a_via_in_a_pad_keeps_hole_spacing_from_a_fixed_via():
+    from freeroute.geometry import IntPoint
+
+    text = _THT.replace("(network (net SIG (pins J1-1))))",
+                        "(network (net SIG (pins J1-1)))\n"
+                        "  (wiring (via \"Via[0-1]_500:300_um\"  3000 -3000 (net SIG) (type route))))")
+    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)

tests/test_cli.py

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