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

bench/diagnose.py

@@ -32,10 +32,8 @@ from freeroute.route.exact_router import route_board_exact
 from freeroute.route.grid_router import GridRouter, _ends_of
 from freeroute.route.pipeline import (
     _mm_to_board,
-    _net_widths_board,
     _rule_clearance_dsn,
     _rule_width_dsn,
-    _via_drill_board,
     _via_half_board,
 )
 
@@ -185,8 +183,7 @@ def _flood(router: GridRouter, pin, net_no: int, conns) -> tuple[int, Counter]:
 
 def diagnose(
     dsn_text: str, edge_clearance_mm: float | None, resolution: int = 2, shove: bool = False,
-    access_cost: float = 0.0, hole_to_hole_mm: float = 0.25, seed: int | None = None,
-    negotiate: int = 0,
+    access_cost: float = 0.0,
 ) -> dict:
     dsn = parse_dsn(dsn_text)
     names = {i + 1: n.name for i, n in enumerate(dsn.nets)}
@@ -202,12 +199,6 @@ def diagnose(
         resolution=resolution,
         shove=shove,
         access_cost=access_cost,
-        seed=seed,
-        negotiate=negotiate,
-        # the product's configuration: net-class widths and hole spacing
-        net_widths=_net_widths_board(dsn, scale),
-        via_drill=_via_drill_board(dsn, scale),
-        hole_to_hole=_mm_to_board(dsn, scale, hole_to_hole_mm) or 0,
     )
     routed = seen["router"]
     best = routed._diag_best
@@ -215,8 +206,6 @@ def diagnose(
 
     # the board as the best pass left it
     state = _fresh(seen)
-    # pins on turned pads leave along their pad's axis: replay with the same exits
-    state._axis_exits = dict(routed._axis_exits)
     conns = state._conns
     for idx, (path, a_end, b_end) in best.items():
         conns[idx].a_end, conns[idx].b_end = a_end, b_end
@@ -281,14 +270,11 @@ def main(argv: list[str] | None = None) -> int:
     ap.add_argument("--grid-resolution", type=int, default=2, metavar="K")
     ap.add_argument("--shove", action="store_true", help="as mckicad routes")
     ap.add_argument("--access-cost", type=float, default=0.0)
-    ap.add_argument("--seed", type=int, help="route in this shuffled order, as bench.py does")
-    ap.add_argument("--negotiate", type=int, default=0, metavar="N", help="as the router's --negotiate")
-    ap.add_argument("--hole-to-hole", type=float, default=0.25, metavar="MM")
     ap.add_argument("--json", type=Path, help="also write the full table here")
     args = ap.parse_args(argv)
 
     report = diagnose(args.dsn.read_text(), args.edge_clearance, args.grid_resolution, args.shove,
-                      args.access_cost, args.hole_to_hole, args.seed, args.negotiate)
+                      args.access_cost)
     for row in report["failures"]:
         extra = ""
         for w in row.get("walled", []):

bench/drc_check.sh

@@ -1,67 +0,0 @@
-#!/usr/bin/env bash
-# Route one KiCad board with freeroute and judge the result with KiCad's DRC.
-#
-#   bench/drc_check.sh [--keep] <board.kicad_pcb> <out-dir> [freeroute args...]
-#
-# Copies the board (and its .kicad_pro) into <out-dir>, strips its tracks and
-# vias unless --keep is given (then they reach the router as fixed wiring),
-# exports the DSN through mckicad, routes, applies the session, and runs DRC
-# with zones refilled at every severity. Prints one line: time, copper added,
-# shorts, opens, hole problems (whatever severity the board gives them) and
-# the other errors. The source board is never touched.
-#
-# FREEROUTE (default: this checkout's .venv/bin/freeroute) and MCK (default
-# ~/claude/mckicad) pick the builds to judge.
-set -euo pipefail
-keep=0
-if [[ "${1:-}" == "--keep" ]]; then keep=1; shift; fi
-src="$1"; out="$2"; shift 2
-here="$(cd "$(dirname "$0")/.." && pwd)"
-FREEROUTE="${FREEROUTE:-$here/.venv/bin/freeroute}"
-MCK="${MCK:-$HOME/claude/mckicad}"
-rm -rf "$out"; mkdir -p "$out"
-cp "${src%.kicad_pcb}.kicad_pro" "$out/board.kicad_pro" 2>/dev/null || true
-
-if [[ $keep == 1 ]]; then
-    cp "$src" "$out/board.kicad_pcb"
-else
-    (cd "$MCK" && uv run --no-sync python - "$src" "$out/board.kicad_pcb" <<'EOF'
-import sys
-from mckicad.utils.sexp_tree import parse
-text = open(sys.argv[1]).read()
-spans = sorted((c.span for c in parse(text).children if c.tag in ("segment", "arc", "via")), reverse=True)
-for a, b in spans:
-    text = text[:a] + text[b:]
-open(sys.argv[2], "w").write(text)
-EOF
-    )
-fi
-
-(cd "$MCK" && uv run --no-sync python -c "
-from mckicad.utils.freerouting import FreeRoutingEngine
-assert FreeRoutingEngine().export_dsn_from_kicad('$out/board.kicad_pcb', '$out/board.dsn', {})") \
-    >/dev/null 2>&1 || { echo "$out: DSN export failed"; exit 1; }
-
-start=$(date +%s.%N)
-"$FREEROUTE" "$out/board.dsn" -do "$out/board.ses" "$@" >"$out/route.log" 2>&1 || true
-secs=$(python3 -c "print(round($(date +%s.%N)-$start,1))")
-[[ -s "$out/board.ses" ]] || { echo "$out: no session ($(tail -1 "$out/route.log"))"; exit 1; }
-
-(cd "$MCK" && uv run --no-sync python -c "
-from mckicad.utils.ses_apply import apply_ses_to_board as a
-r = a('$out/board.kicad_pcb', '$out/board.ses', '$out/board.kicad_pcb')
-print(r['segments_added'], r['vias_added'])" 2>/dev/null) >"$out/apply.txt"
-
-kicad-cli pcb drc --refill-zones --format json --severity-all \
-    -o "$out/drc.json" "$out/board.kicad_pcb" >/dev/null 2>&1 || true
-python3 - "$out" "$secs" <<'EOF'
-import collections, json, sys
-out, secs = sys.argv[1:]
-seg, via = open(f"{out}/apply.txt").read().split()
-d = json.load(open(f"{out}/drc.json"))
-errors = collections.Counter(v["type"] for v in d["violations"] if v.get("severity") == "error")
-other = collections.Counter(v["type"] for v in d["violations"] if v.get("severity") != "error")
-holes = {k: errors.pop(k, 0) + other.get(k, 0) for k in ("holes_co_located", "hole_to_hole")}
-print(f"{out}: {secs}s  {seg} seg {via} via  shorts {errors.pop('shorting_items', 0)}  "
-      f"opens {len(d.get('unconnected_items', []))}  holes {holes}  errors {dict(errors)}")
-EOF

src/freeroute/board/build.py

@@ -12,10 +12,9 @@ model. It mirrors what FreeRouting's ``Structure.create_board`` / ``Library`` /
 * padstacks x placement -> :class:`Pin` items
 * keepouts -> :class:`ObstacleArea` items
 
-Pad geometry: a rectangle pad becomes an exact :class:`IntBox`; a circle pad a
-16-sided :class:`Simplex` drawn just outside it (its corners stand out by 2% of
-the radius, where the bounding box's stood out by 41%); a convex polygon pad an
-exact :class:`Simplex`. Every pad is placed centred on its pin
+Pad geometry: a rectangle pad becomes an exact :class:`IntBox`; a circle pad its
+bounding box (documented approximation pending an exact circle tile); a convex
+polygon pad an exact :class:`Simplex`. Every pad is placed centred on its pin
 location, so it contains that location by construction. Component rotation is
 applied to the pin position; the pad tile itself is not rotated (irrelevant to
 the containment invariant, and pads are centre-symmetric in practice).
@@ -250,7 +249,7 @@ def _placed_pad_tile(shape: Shape, place, dsn_pin, transform: CoordinateTransfor
         r = round(transform.dsn_to_board(shape.diameter / 2))
         cx = round(transform.dsn_to_board(centre.x))
         cy = round(transform.dsn_to_board(centre.y))
-        return _circle_tile(cx, cy, r)
+        return IntBox(cx - r, cy - r, cx + r, cy + r)
     if isinstance(shape, Rectangle):
         x0, y0, x1, y1 = shape.coords[:4]
         corners = [(x0, y0), (x1, y0), (x1, y1), (x0, y1)]
@@ -269,12 +268,8 @@ def _placed_pad_tile(shape: Shape, place, dsn_pin, transform: CoordinateTransfor
     for x, y in corners:
         p = _to_board_offset(place, x, y, dsn_pin.rotation)
         pts.append(IntPoint(round(transform.dsn_to_board(p.x)), round(transform.dsn_to_board(p.y))))
-    # An oval's padded corners are not in outline order, and a mirrored
-    # part reverses the winding: take the convex hull, then either winding.
-    hull = _convex_hull(pts)
-    if len(hull) >= 3:
-        for corners in (hull, hull[::-1]):
-            simplex = Simplex.from_corners(corners)
+    if len(pts) >= 3:
+        simplex = Simplex.from_corners(pts)
         if not simplex.is_empty():
             return simplex
     xs = [p.x for p in pts] or [0]
@@ -282,52 +277,6 @@ def _placed_pad_tile(shape: Shape, place, dsn_pin, transform: CoordinateTransfor
     return IntBox(min(xs), min(ys), max(xs), max(ys))
 
 
-_CIRCLE_SIDES = 16
-
-
-def _circle_tile(cx: int, cy: int, r: int):
-    """A polygon around the circle, every side touching it. A square around a
-    big round pad (a mounting hole) puts phantom copper in its corners that
-    blocks legal routes past it; this stays outside the circle, so the router
-    is still never closer than KiCad measures."""
-    if r < 8:
-        return IntBox(cx - r, cy - r, cx + r, cy + r)
-    reach = r / math.cos(math.pi / _CIRCLE_SIDES)
-    corners = []
-    for k in range(_CIRCLE_SIDES):
-        a = (k + 0.5) * 2 * math.pi / _CIRCLE_SIDES
-        dx, dy = reach * math.cos(a), reach * math.sin(a)
-        # round away from the centre so the polygon never cuts into the circle
-        corners.append(IntPoint(cx + math.copysign(math.ceil(abs(dx)), dx),
-                                cy + math.copysign(math.ceil(abs(dy)), dy)))
-    corners = [IntPoint(int(p.x), int(p.y)) for p in corners]
-    for winding in (corners, corners[::-1]):
-        simplex = Simplex.from_corners(winding)
-        if not simplex.is_empty():
-            return simplex
-    return IntBox(cx - r, cy - r, cx + r, cy + r)
-
-
-def _convex_hull(pts: list[IntPoint]) -> list[IntPoint]:
-    """The convex hull of ``pts`` counter-clockwise, collinear points dropped."""
-    ps = sorted({(p.x, p.y) for p in pts})
-    if len(ps) < 3:
-        return [IntPoint(x, y) for x, y in ps]
-
-    def cross(o, a, b):
-        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
-
-    def half(points):
-        out: list[tuple[int, int]] = []
-        for p in points:
-            while len(out) >= 2 and cross(out[-2], out[-1], p) <= 0:
-                out.pop()
-            out.append(p)
-        return out[:-1]
-
-    return [IntPoint(x, y) for x, y in half(ps) + half(ps[::-1])]
-
-
 def _pad_tile(shape: Shape, transform: CoordinateTransform):
     """A board-relative pad tile from a DSN padstack shape (centred near origin)."""
     if isinstance(shape, Rectangle):
@@ -337,7 +286,7 @@ def _pad_tile(shape: Shape, transform: CoordinateTransform):
         r = round(transform.dsn_to_board(shape.diameter / 2))
         cx = round(transform.dsn_to_board(shape.center_x))
         cy = round(transform.dsn_to_board(shape.center_y))
-        return _circle_tile(cx, cy, r)
+        return IntBox(cx - r, cy - r, cx + r, cy + r)  # bounding-box approximation
     if isinstance(shape, (Polygon, Path)):
         coords = shape.coords
         pts = [

src/freeroute/board/items.py

@@ -119,6 +119,8 @@ class Via(Item):
     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
@@ -132,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/board/search_tree.py

@@ -18,7 +18,7 @@ from __future__ import annotations
 
 from dataclasses import dataclass
 
-from freeroute.geometry import IntBox, IntPoint, Simplex, overlaps_2d, segment_octagon, segment_slab
+from freeroute.geometry import IntBox, Simplex, overlaps_2d, segment_octagon
 
 __all__ = ["TreeShape", "ShapeSearchTree"]
 
@@ -63,9 +63,7 @@ class TreeShape:
         segment swept by ``half_width + clearance`` (exact integer superset)."""
         if self.seg is None:
             return self.tile.offset(clearance)
-        a, b, half_width = self.seg[-3:]
-        if self.seg[0] == "slab":  # a slanted pin exit, at any angle
-            return segment_slab(a, b, half_width + clearance)
+        a, b, half_width = self.seg
         return segment_octagon(a, b, half_width + clearance)
 
 
@@ -153,25 +151,6 @@ class ShapeSearchTree:
                 return True
         return False
 
-    def segment_conflict(
-        self, a: IntPoint, b: IntPoint, half_width: int, net_no: int, layer: int,
-        clearance: int, kind: str = "wire",
-    ) -> bool:
-        """:meth:`clearance_conflict` for a slanted segment, checked on its
-        exact swept copper instead of its bounding box (which would reach the
-        neighbouring pads of a pin leaving along its turned pad's axis)."""
-        copper = segment_slab(a, b, half_width)
-        grown = segment_slab(a, b, half_width + clearance)
-        for shape in self.overlapping(grown.bounding_box()):
-            if shape.net_no == net_no or not shape.on_layer(layer):
-                continue
-            if shape.blocks != "all" and shape.blocks != kind + "s":
-                continue
-            other = shape.exact if shape.exact is not None else shape.tile
-            if overlaps_2d(copper if not shape.clearance else grown, other):
-                return True
-        return False
-
     def rule_area_overlap(self, box: IntBox, layer: int, kind: str = "wire") -> bool:
         """True if ``box`` overlaps a rule area on ``layer`` that stops ``kind``."""
         for shape in self.overlapping(box):
@@ -209,8 +188,6 @@ class ShapeSearchTree:
         overlap). Static pad-vs-pad spacing in the source design is not counted.
         """
         for shape in self.all_shapes():
-            if not shape.routed:
-                continue  # a pair with routed copper is checked from that side
             expanded = shape.tile.offset(clearance)
             grown = None  # exact clearance region, built lazily only for diagonals
             for other in self.overlapping(expanded):

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", "negotiate", "rollback", "tree"}),
-    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access", "negotiate", "rollback", "tree"}),
+    "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"}),
 }
 
@@ -46,9 +49,8 @@ _FLAG_NAMES = {
     "orders": "--orders",
     "promote": "--promote-failures",
     "access": "--access-cost",
-    "negotiate": "--negotiate",
     "rollback": "--no-rollback",
-    "tree": "--no-tree",
+    "fanout": "--fanout",
 }
 
 
@@ -169,14 +171,6 @@ 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(
-        "--negotiate",
-        type=int,
-        metavar="N",
-        help="grid and exact engines: before routing, N rounds of negotiation on the empty "
-        "board, where routes may share space at a price that rises where they compete; "
-        "the contested cells then cost extra in the real routing (default 0: off)",
-    )
     parser.add_argument(
         "--no-rollback",
         dest="rollback",
@@ -185,15 +179,6 @@ def build_parser() -> argparse.ArgumentParser:
         "connections a rip-up displaces are rerouted at once and the rip-up is undone "
         "if fewer connections end up routed",
     )
-    parser.add_argument(
-        "--no-tree",
-        dest="tree_nets",
-        action="store_false",
-        help="grid and exact engines: join a multi-pin net's pins as a chain in pin "
-        "order, each connection ending on one chosen pin, as before. By default they are "
-        "paired by a minimum spanning tree and a connection may end on copper its net "
-        "has already routed",
-    )
     parser.add_argument(
         "--hole-to-hole",
         type=float,
@@ -202,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,
@@ -231,9 +232,8 @@ 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),
-            ("negotiate", args.negotiate is not None),
             ("rollback", not args.rollback),
-            ("tree", not args.tree_nets),
+            ("fanout", bool(args.fanout)),
         )
         if asked
     ]
@@ -268,10 +268,10 @@ 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,
-            "negotiate": args.negotiate or 0,
             "hole_to_hole_mm": args.hole_to_hole,
+            "fanout": args.fanout or False,
+            "fanout_min_pins": args.fanout_min_pins,
             "rollback": args.rollback,
-            "tree_nets": args.tree_nets,
         }
     elif args.engine == "grid":
         options = {
@@ -281,10 +281,10 @@ 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,
-            "negotiate": args.negotiate or 0,
             "hole_to_hole_mm": args.hole_to_hole,
+            "fanout": args.fanout or False,
+            "fanout_min_pins": args.fanout_min_pins,
             "rollback": args.rollback,
-            "tree_nets": args.tree_nets,
         }
     if args.engine == "room":
         result = build_rooms_routing_result(

src/freeroute/geometry/__init__.py

@@ -21,7 +21,7 @@ from .direction import Direction, IntDirection
 from .float_point import FloatPoint
 from .limits import CRIT_DOUBLE, CRIT_INT
 from .line import Line
-from .octagon import ceil_sqrt2, overlaps_2d, segment_octagon, segment_slab
+from .octagon import ceil_sqrt2, overlaps_2d, segment_octagon
 from .point import IntPoint, Point, RationalPoint, point, rational_point
 from .polygon import Polygon
 from .polygon_shape import PolygonShape
@@ -59,6 +59,5 @@ __all__ = [
     "shove_segment",
     "ceil_sqrt2",
     "segment_octagon",
-    "segment_slab",
     "overlaps_2d",
 ]

src/freeroute/geometry/octagon.py

@@ -29,7 +29,7 @@ from .line import Line
 from .point import IntPoint
 from .simplex import Simplex
 
-__all__ = ["ceil_sqrt2", "segment_octagon", "segment_slab", "overlaps_2d"]
+__all__ = ["ceil_sqrt2", "segment_octagon", "overlaps_2d"]
 
 
 def ceil_sqrt2(radius: int) -> int:
@@ -82,46 +82,6 @@ def segment_octagon(a: IntPoint, b: IntPoint, radius: int) -> Simplex:
     return Simplex.get_instance(lines)
 
 
-def segment_slab(a: IntPoint, b: IntPoint, radius: int) -> Simplex:
-    """Convex cover of segment ``a``-``b`` swept by ``radius``, at any angle.
-
-    The rectangle along the segment, ``radius`` either side, with flush ends
-    like :func:`polyline.segment_box`: the ends of a trace leg sit on a pad or
-    on the square corner tile of the next leg, which cover them. Corners are
-    rounded away from the middle and the radius gets one unit more, so the
-    side bounds never under-report, and it stays tight for a slanted segment
-    off the 45-degree lines (a pin leaving along its pad's axis on a part
-    turned 30 degrees).
-    """
-    dx, dy = b.x - a.x, b.y - a.y
-    length = math.hypot(dx, dy)
-    r = max(radius, 0) + 1
-    if length == 0:
-        return Simplex.from_corners([
-            IntPoint(a.x - r, a.y - r), IntPoint(a.x + r, a.y - r),
-            IntPoint(a.x + r, a.y + r), IntPoint(a.x - r, a.y + r),
-        ])
-    ux, uy = dx / length, dy / length
-    nx, ny = -uy, ux
-    mx, my = (a.x + b.x) / 2, (a.y + b.y) / 2
-
-    def out(x: float, y: float) -> IntPoint:
-        return IntPoint(math.ceil(x) if x >= mx else math.floor(x),
-                        math.ceil(y) if y >= my else math.floor(y))
-
-    corners = [
-        out(a.x + nx * r, a.y + ny * r),
-        out(b.x + nx * r, b.y + ny * r),
-        out(b.x - nx * r, b.y - ny * r),
-        out(a.x - nx * r, a.y - ny * r),
-    ]
-    for winding in (corners, corners[::-1]):
-        slab = Simplex.from_corners(winding)
-        if not slab.is_empty():
-            return slab
-    return Simplex(())
-
-
 def overlaps_2d(shape_a, shape_b) -> bool:
     """True if the two convex tiles share 2-D area (a real clearance overlap).
 

src/freeroute/route/exact_router.py

@@ -38,10 +38,8 @@ from freeroute.geometry import (
     IntPoint,
     Polyline,
     PolylineShape,
-    Simplex,
     segment_box,
     segment_octagon,
-    segment_slab,
     shove_segment,
 )
 from freeroute.geometry.polyline import corner_box
@@ -100,9 +98,7 @@ def route_board_exact(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
-    negotiate: int = 0,
     rollback: bool = True,
-    tree_nets: bool = True,
     net_widths: dict[int, int] | None = None,
     via_drill: int | None = None,
     hole_to_hole: int = 0,
@@ -137,9 +133,7 @@ def route_board_exact(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
-        negotiate=negotiate,
         rollback=rollback,
-        tree_nets=tree_nets,
         net_widths=net_widths,
         via_drill=via_drill,
         hole_to_hole=hole_to_hole,
@@ -160,9 +154,7 @@ def route_board_exact(
         net = pin.net_nos[0] if pin.net_nos else -1
         pin_layers = frozenset(layer for layer in pin.layers if layer in signal_layers)
         if pin_layers:
-            # a rotated pad is checked against its outline, not its box
-            exact = pin.shape if _is_rotated(pin.shape) else None
-            tree.insert(TreeShape(next(owner), net, pin_layers, box, exact=exact))
+            tree.insert(TreeShape(next(owner), net, pin_layers, box))
     for net, copper_layers, box in board.get_fixed_copper():
         on = frozenset(layer for layer in copper_layers if layer in signal_layers)
         if on and not box.is_empty():
@@ -196,43 +188,25 @@ def route_board_exact(
     # 25-pin supply net costs that one connection, not the whole net.
     rejected: list[tuple[int, str, str]] = []
     ends_list = result.connection_ends or [("?", "?", "")] * len(result.connections)
-    anchors_list = getattr(result, "connection_anchors", None) or [()] * len(result.connections)
     # each net is checked at the width it will be written at: its class's
     # when all of its connections went in at that, else the default
     net_half = dict(result.net_half)
-    # a connection that ended on another's copper (a T into its net's tree)
-    # dangles if that one is dropped, so it is dropped too; connections come
-    # in commit order, anchors first
-    dropped_at: set[int] = set()
-    for pos, ((net_no, wires, vias), ends, anchors) in sorted(
-        enumerate(zip(result.connections, ends_list, anchors_list, strict=False)),
-        key=lambda c: c[1][0][0],
+    for (net_no, wires, vias), ends in sorted(
+        zip(result.connections, ends_list, strict=False), key=lambda c: c[0][0]
     ):
-        if any(a in dropped_at for a in anchors):
-            dropped_at.add(pos)
-            rejected.append((net_no, *ends))
-            continue
         wire_half = net_half.get(net_no, half_width)
-        pieces = _copper_pieces(wires, vias, wire_half, via_layers, via_half)
-        boxes = [(box, box_layers) for box, box_layers, _ in pieces]
-        wire_count = len(_copper_pieces(wires, [], wire_half, via_layers, via_half))
+        boxes = _copper_boxes(wires, vias, wire_half, via_layers, via_half)
+        wire_count = len(_copper_boxes(wires, [], wire_half, via_layers, via_half))
         if any(
-            (
-                tree.segment_conflict(*seg, wire_half, net_no, layer, clearance)
-                if seg is not None
-                else tree.clearance_conflict(
+            tree.clearance_conflict(
                 box, net_no, layer, clearance, "wire" if i < wire_count else "via"
             )
-            )
-            for i, (box, box_layers, seg) in enumerate(pieces)
+            for i, (box, box_layers) in enumerate(boxes)
             for layer in box_layers
         ) or _end_in_rule_area(tree, wires, wire_half) or (
-            outline is not None and not _inside_outline(
-                outline, boxes[:wire_count], vias, (via_half or wire_half) + edge, edge
-            )
+            outline is not None and not all(outline.box_clear(b, edge) for b, _ in boxes)
         ):
             rejected.append((net_no, *ends))
-            dropped_at.add(pos)
             continue  # exact-clearance conflict -> drop (may be recovered by shove)
         acc = accepted.get(net_no)
         if acc is None:
@@ -244,15 +218,9 @@ def route_board_exact(
             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, seg in pieces:
+        for box, box_layers in boxes:
             oid = next(owner)
-            if seg is None:
             tree.insert(TreeShape(oid, net_no, box_layers, box, routed=True))
-            else:  # a slanted pin exit: its exact copper, rebuilt for the DRC check
-                tree.insert(TreeShape(
-                    oid, net_no, box_layers, box, routed=True,
-                    exact=segment_slab(*seg, wire_half), seg=("slab", *seg, wire_half),
-                ))
             acc.owners.append(oid)
 
     accepted_before_recovery = set(accepted)
@@ -687,27 +655,6 @@ def _on_fixed_via(net_no, point, fixed_vias, via_half) -> bool:
     )
 
 
-def _copper_pieces(wires, vias, half_width, via_layers, via_half=None):
-    """Like :func:`_copper_boxes`, but a slanted wire segment (a pin leaving
-    along a turned pad's axis) comes with its end points, so it can be checked
-    on its exact copper: ``(box, layers, (a, b) or None)``."""
-    via_half = via_half or half_width
-    pieces: list[tuple[IntBox, frozenset[int], tuple | None]] = []
-    for layer, points in wires:
-        on = frozenset({layer})
-        for a, b in zip(points, points[1:], strict=False):
-            if a.x == b.x or a.y == b.y:
-                pieces.append((segment_box(a, b, half_width), on, None))
-            else:
-                pieces.append((segment_slab(a, b, half_width).bounding_box(), on, (a, b)))
-        for c in points[1:-1]:
-            pieces.append((corner_box(c, half_width), on, None))
-    for loc in vias:
-        vbox = IntBox(loc.x - via_half, loc.y - via_half, loc.x + via_half, loc.y + via_half)
-        pieces.append((vbox, via_layers, None))
-    return pieces
-
-
 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]]] = []
@@ -720,19 +667,6 @@ def _copper_boxes(wires, vias, half_width, via_layers, via_half=None):
     return boxes
 
 
-def _inside_outline(outline, wire_boxes, vias, via_reach, edge) -> bool:
-    """Copper inside the board, ``edge`` from its outline. A via is round, as
-    the grid and KiCad take it: its square box would reach past a chamfered
-    corner where the via itself does not."""
-    return all(outline.box_clear(b, edge) for b, _ in wire_boxes) and all(
-        outline.point_clear(v, via_reach) for v in vias
-    )
-
-
-def _is_rotated(shape) -> bool:
-    return isinstance(shape, Simplex) and not shape.is_int_box()
-
-
 def _net_pins(board: BasicBoard, net_no: int, signal_layers) -> list[Pin]:
     return [
         pin

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/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.
 
@@ -118,10 +154,10 @@ def route_dsn_board(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
-    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
+    fanout: bool | str = False,
+    fanout_min_pins: int = 32,
     rollback: bool = True,
-    tree_nets: 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
@@ -132,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,
@@ -145,13 +184,12 @@ def route_dsn_board(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
-        negotiate=negotiate,
         rollback=rollback,
-        tree_nets=tree_nets,
         net_widths=_net_widths_board(dsn, scale),
         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]
 
 
@@ -200,10 +238,10 @@ def build_routing_result(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
-    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
+    fanout: bool | str = False,
+    fanout_min_pins: int = 32,
     rollback: bool = True,
-    tree_nets: bool = True,
 ) -> RoutingResult:
     """Route ``dsn`` (grid track) and convert to a DSN-unit RoutingResult."""
     route, scale, layer_names = route_dsn_board(
@@ -211,10 +249,10 @@ def build_routing_result(
         edge_clearance_mm=edge_clearance_mm, resolution=resolution, seed=seed,
         route_first=route_first,
         access_cost=access_cost,
-        negotiate=negotiate,
         hole_to_hole_mm=hole_to_hole_mm,
+        fanout=fanout,
+        fanout_min_pins=fanout_min_pins,
         rollback=rollback,
-        tree_nets=tree_nets,
     )
     return _to_routing_result(route, dsn, scale, layer_names)
 
@@ -233,10 +271,10 @@ def route_dsn_board_exact(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
-    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
+    fanout: bool | str = False,
+    fanout_min_pins: int = 32,
     rollback: bool = True,
-    tree_nets: 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.
@@ -248,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,
@@ -264,13 +305,12 @@ def route_dsn_board_exact(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
-        negotiate=negotiate,
         rollback=rollback,
-        tree_nets=tree_nets,
         net_widths=_net_widths_board(dsn, scale),
         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]
 
 
@@ -288,10 +328,10 @@ def build_exact_routing_result(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
-    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
+    fanout: bool | str = False,
+    fanout_min_pins: int = 32,
     rollback: bool = True,
-    tree_nets: bool = True,
 ) -> RoutingResult:
     """Route ``dsn`` (exact track) and convert to a DSN-unit RoutingResult."""
     exact, scale, layer_names = route_dsn_board_exact(
@@ -307,10 +347,10 @@ def build_exact_routing_result(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
-        negotiate=negotiate,
         hole_to_hole_mm=hole_to_hole_mm,
+        fanout=fanout,
+        fanout_min_pins=fanout_min_pins,
         rollback=rollback,
-        tree_nets=tree_nets,
     )
     return _to_routing_result(exact.result, dsn, scale, layer_names)
 

tests/route/test_axis_escapes.py

@@ -1,113 +0,0 @@
-"""Pins of a fine-pitch part turned off the grid axes leave along their pads.
-
-A QFN at 45 degrees has no straight exit: every horizontal or vertical step
-from a pin passes its neighbours closer than the clearance (0.35 mm away on
-each axis at 0.5 mm pitch). The grid leaves along the pad's own axis first,
-past the pin row, and the exact engine checks that slanted leg on its exact
-copper. Found on th-eda's lift ESC, where a QFN-24 at 45 degrees left 15
-connections unroutable on an empty board.
-"""
-
-from __future__ import annotations
-
-import math
-
-import pytest
-
-from freeroute.board import build_board
-from freeroute.dsn import parse_dsn
-from freeroute.geometry import IntPoint, overlaps_2d, segment_slab
-from freeroute.route.grid_router import GridRouter
-from freeroute.route.pipeline import (
-    _rule_clearance_dsn,
-    _rule_width_dsn,
-    _via_half_board,
-    build_exact_routing_result,
-)
-
-
-def _qfn_side_dsn(rotation: float) -> str:
-    """Two rows of five 0.25 x 0.8 mm pads at 0.5 mm pitch (one side of a
-    QFN and its opposite side), turned by ``rotation``; each pin of the top
-    row is its own net, routed to a pad 4.5 mm out, the pads fanned 1.5 mm
-    apart."""
-    cx, cy = 100000, -100000
-    t = math.radians(rotation)
-    out = (-math.sin(t), math.cos(t))  # the pads' outward axis after turning
-    along = (math.cos(t), math.sin(t))  # the pin row
-    pins, targets, nets = [], [], []
-    for i in range(5):
-        x = -1000 + 500 * i
-        pins += [f"(pin P {i + 1} {x} 1000)", f"(pin P {i + 6} {x} -1000)"]
-        px = cx + x * math.cos(t) - 1000 * math.sin(t)
-        py = cy + x * math.sin(t) + 1000 * math.cos(t)
-        spread = 1500 * (i - 2) - x  # fan the far pads out to 1.5 mm apart
-        tx = px + 4500 * out[0] + spread * along[0]
-        ty = py + 4500 * out[1] + spread * along[1]
-        targets.append(f"(place T{i + 1} {round(tx)} {round(ty)} front 0)")
-        nets.append(f"(net N{i} (pins U1-{i + 1} T{i + 1}-1))")
-    return f"""(pcb qfn (parser) (resolution um 10) (unit um)
-  (structure
-    (layer F.Cu (type signal)) (layer B.Cu (type signal))
-    (boundary (path pcb 0  115000 -115000  85000 -115000  85000 -85000  115000 -85000
-      115000 -115000))
-    (via "Via[0-1]_450:200_um")
-    (rule (width 150) (clearance 150)))
-  (placement
-    (component Q (place U1 {cx} {cy} front {rotation}))
-    (component T {" ".join(targets)}))
-  (library
-    (image Q {" ".join(pins)})
-    (image T (pin t 1 0 0))
-    (padstack P (shape (rect F.Cu -125 -400 125 400)) (attach off))
-    (padstack t (shape (rect F.Cu -300 -300 300 300)) (attach off))
-    (padstack "Via[0-1]_450:200_um" (shape (circle F.Cu 450)) (shape (circle B.Cu 450))
-      (attach off)))
-  (network {" ".join(nets)}))"""
-
-
-@pytest.mark.parametrize("rotation", [45, 30, -45])
-def test_a_turned_fine_pitch_part_gets_its_pins_out(rotation):
-    result = build_exact_routing_result(parse_dsn(_qfn_side_dsn(rotation)), resolution=2, shove=True)
-    assert result.unrouted == []
-
-
-def test_the_exit_runs_along_the_pad_axis_and_clears_the_neighbours():
-    dsn = parse_dsn(_qfn_side_dsn(45))
-    s = dsn.resolution.value
-    board = build_board(dsn)
-    router = GridRouter(
-        board,
-        trace_width=round(_rule_width_dsn(dsn) * s),
-        clearance=round(_rule_clearance_dsn(dsn) * s),
-        via_half=_via_half_board(dsn, s),
-        orthogonal=True,
-    )
-    pins = {p.name: p for p in board.get_pins() if p.component_ref == "U1"}
-    pin = pins["3"]
-    exit_point = router._axis_exit(pin)
-    assert exit_point is not None
-    dx, dy = exit_point.x - pin.location.x, exit_point.y - pin.location.y
-    assert abs(abs(dx) - abs(dy)) <= 2  # along the 45-degree axis
-    leg = segment_slab(pin.location, exit_point, router.half_width + router.clearance)
-    for name in ("2", "4"):
-        assert not overlaps_2d(leg, pins[name].shape)
-
-
-def test_a_pad_on_the_grid_axes_keeps_the_usual_exits():
-    dsn = parse_dsn(_qfn_side_dsn(0))
-    s = dsn.resolution.value
-    board = build_board(dsn)
-    router = GridRouter(board, trace_width=round(_rule_width_dsn(dsn) * s),
-                        clearance=round(_rule_clearance_dsn(dsn) * s), via_half=_via_half_board(dsn, s))
-    pin = next(p for p in board.get_pins() if p.component_ref == "U1" and p.name == "3")
-    assert router._axis_exit(pin) is None
-
-
-def test_a_slanted_slab_is_tight_where_a_bounding_box_is_not():
-    slab = segment_slab(IntPoint(0, 0), IntPoint(10000, 10000), 750)
-    # a point beside the diagonal but inside its bounding box
-    from freeroute.geometry import IntBox
-
-    assert not overlaps_2d(slab, IntBox(8000, 0, 8100, 100))
-    assert overlaps_2d(slab, IntBox(4900, 4900, 5100, 5100))

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_grid_exact_agreement.py

@@ -1,284 +0,0 @@
-"""The grid must not believe copper legal that the exact check then refuses.
-
-Each case is one way the two used to disagree on roomba-ESP12E: a rotated oval
-pad modelled as an inflated box (and opened to its own net), a via shared by
-two connections of a net losing its footprint when one of them is ripped, and
-a wider net class searched as if it were the default width.
-"""
-
-from __future__ import annotations
-
-import math
-
-import pytest
-
-from freeroute.board import build_board
-from freeroute.dsn import parse_dsn
-from freeroute.geometry import IntBox, Simplex
-from freeroute.route.grid_router import GridRouter
-from freeroute.route.pipeline import (
-    _rule_clearance_dsn,
-    _rule_width_dsn,
-    _via_half_board,
-    build_exact_routing_result,
-)
-
-# --- rotated oval pads -------------------------------------------------------
-
-
-def _socket_dsn(rotation: float, layout: str) -> str:
-    """A 1x4 2.54 mm socket strip (rect pin 1, oval pins 2-4) at ``rotation``,
-    each pin its own net, routed to a small SMD pad 0.9 mm away."""
-    cx, cy = 100000, -100000
-    t = math.radians(rotation)
-    ax = (math.cos(t), math.sin(t))
-    perp = (-math.sin(t), math.cos(t))
-    places = []
-    for i in range(4):
-        px, py = cx + 2540 * i * ax[0], cy + 2540 * i * ax[1]
-        side = 1 if i % 2 == 0 else -1
-        if layout == "y":
-            tx, ty = px, py + side * 9000
-        else:
-            tx, ty = px + side * 8000 * perp[0], py + side * 8000 * perp[1]
-        places.append(f"(place T{i + 1} {round(tx)} {round(ty)} front 0)")
-    nets = " ".join(f"(net N{i} (pins P3-{i + 1} T{i + 1}-1))" for i in range(4))
-    return f"""(pcb socket (parser) (resolution um 10) (unit um)
-  (structure
-    (layer F.Cu (type signal)) (layer B.Cu (type signal))
-    (boundary (path pcb 0  125000 -115000  85000 -115000  85000 -75000  125000 -75000
-      125000 -115000))
-    (via "Via[0-1]_800:400_um")
-    (rule (width 300) (clearance 250)))
-  (placement
-    (component S (place P3 {cx} {cy} front {rotation}))
-    (component T {" ".join(places)}))
-  (library
-    (image S (pin R 1 0 0) (pin O 2 2540 0) (pin O 3 5080 0) (pin O 4 7620 0))
-    (image T (pin t 1 0 0))
-    (padstack O (shape (path F.Cu 1727.2 0 -152.4 0 152.4))
-      (shape (path B.Cu 1727.2 0 -152.4 0 152.4)) (attach off))
-    (padstack R (shape (rect F.Cu -863.6 -1016 863.6 1016))
-      (shape (rect B.Cu -863.6 -1016 863.6 1016)) (attach off))
-    (padstack t (shape (rect F.Cu -500 -500 500 500)) (attach off))
-    (padstack "Via[0-1]_800:400_um" (shape (circle F.Cu 800)) (shape (circle B.Cu 800))
-      (attach off)))
-  (network {nets}
-    (class c N0 N1 N2 N3 (circuit (use_via "Via[0-1]_800:400_um"))
-      (rule (width 300) (clearance 250)))))"""
-
-
-def test_a_rotated_oval_pad_is_its_outline_not_its_bounding_box():
-    board = build_board(parse_dsn(_socket_dsn(60, "y")))
-    oval = next(p for p in board.get_pins() if p.component_ref == "P3" and p.name == "2")
-    assert isinstance(oval.shape, Simplex) and not oval.shape.is_int_box()
-    box = oval.shape.bounding_box()
-    assert oval.shape.contains(oval.location)
-    assert not oval.shape.contains(box.ll) and not oval.shape.contains(box.ur)
-
-
-@pytest.mark.parametrize("layout", ["y", "perp"])
-def test_routes_leaving_a_rotated_socket_pass_the_exact_check(layout):
-    result = build_exact_routing_result(
-        parse_dsn(_socket_dsn(60, layout)), resolution=2, shove=True
-    )
-    assert result.unrouted == []
-
-
-# --- a via two connections share --------------------------------------------
-
-_SHARED_VIA = """(pcb shared (parser) (resolution um 10) (unit um)
-  (structure
-    (layer Top (type signal)) (layer Bottom (type signal))
-    (boundary (path pcb 0  0 0  20000 0  20000 -20000  0 -20000  0 0))
-    (via "Via[0-1]_800:400_um")
-    (rule (width 300) (clearance 250)))
-  (library
-    (padstack p (shape (rect Top -400 -400 400 400)) (attach off))
-    (padstack "Via[0-1]_800:400_um" (shape (circle Top 800)) (shape (circle Bottom 800))
-      (attach off))
-    (image PAD (pin p 1 0 0)))
-  (placement (component PAD
-    (place G1 3000 -5000 front 0) (place G2 3000 -15000 front 0)
-    (place G3 17000 -10000 front 0) (place S1 3000 -10000 front 0)
-    (place S2 17000 -3000 front 0)))
-  (network (net GND (pins G1-1 G2-1 G3-1)) (net SIG (pins S1-1 S2-1))))"""
-
-
-def _line(a, b, layer):
-    (x, y), (x1, y1) = a, b
-    out = [(x, y, layer)]
-    while x != x1:
-        x += 1 if x1 > x else -1
-        out.append((x, y, layer))
-    while y != y1:
-        y += 1 if y1 > y else -1
-        out.append((x, y, layer))
-    return out
-
-
-def test_a_shared_via_keeps_its_footprint_when_one_user_is_ripped():
-    dsn = parse_dsn(_SHARED_VIA)
-    s = dsn.resolution.value
-    router = GridRouter(
-        build_board(dsn),
-        trace_width=round(_rule_width_dsn(dsn) * s),
-        clearance=round(_rule_clearance_dsn(dsn) * s),
-        via_half=_via_half_board(dsn, s),
-    )
-    conns = router._conns = router._build_connections()
-    gnd = [c for c in conns if len({c.a.component_ref, c.b.component_ref} & {"G1", "G2", "G3"})]
-    sig = next(c for c in conns if c not in gnd)
-    first, second = gnd
-    g3 = router._cell_of(next(p for p in router.board.get_pins() if p.component_ref == "G3").location)
-    via = (g3[0] - 10, g3[1])
-
-    def through_via(conn):
-        a, b = router._cell_of(conn.a.location), router._cell_of(conn.b.location)
-        return _line(a, via, 0) + _line(via, b, 1)
-
-    router._commit(first, through_via(first))
-    router._commit(second, through_via(second))
-    footprint = [c for c in router._via_cells(via) if c != via]
-    router._rip(first)
-
-    assert second.routed and via in second.via_cells
-    assert all(router._via_claims.get(c) == [second.index] for c in footprint)
-    # another net still keeps its distance from the via that is left
-    assert all(router._enter_cost_base(c, 0, sig.net_no, False, conns) is None for c in footprint)
-
-
-def test_a_route_through_a_shared_via_rips_every_user():
-    """Two connections of a net share a via. Another net routed through it
-    in rip-up mode has to rip both, or the one left keeps its via under the
-    new trace and the exact check throws one of them out."""
-    dsn = parse_dsn(_SHARED_VIA)
-    s = dsn.resolution.value
-    router = GridRouter(
-        build_board(dsn),
-        trace_width=round(_rule_width_dsn(dsn) * s),
-        clearance=round(_rule_clearance_dsn(dsn) * s),
-        via_half=_via_half_board(dsn, s),
-    )
-    conns = router._conns = router._build_connections()
-    gnd = [c for c in conns if len({c.a.component_ref, c.b.component_ref} & {"G1", "G2", "G3"})]
-    sig = next(c for c in conns if c not in gnd)
-    first, second = gnd
-    g3 = router._cell_of(next(p for p in router.board.get_pins() if p.component_ref == "G3").location)
-    via = (g3[0] - 10, g3[1])
-
-    def through_via(conn):
-        a, b = router._cell_of(conn.a.location), router._cell_of(conn.b.location)
-        return _line(a, via, 0) + _line(via, b, 1)
-
-    router._commit(first, through_via(first))
-    router._commit(second, through_via(second))
-    # the via's copper alone: footprint cells no trace or trace halo covers
-    crossing = [
-        node
-        for c in router._via_cells(via)
-        for node in ((*c, 0), (*c, 1))
-        if node not in router._cell_owner and node not in router._halo
-    ]
-    assert crossing
-
-    assert router._crossed_owners(crossing, sig.net_no, conns) == {first.index, second.index}
-
-
-# --- a wider net class --------------------------------------------------------
-
-_WIDE = """(pcb wide (parser) (resolution um 10) (unit um)
-  (structure
-    (layer F.Cu (type signal))
-    (boundary (path pcb 0  0 0  20000 0  20000 -10000  0 -10000  0 0))
-    (rule (width 300) (clearance 250)))
-  (placement (component S (place P1 2000 -5000 front 0) (place P2 18000 -5000 front 0)
-     (place Q1 10000 {ylo} front 0) (place Q2 10000 {yhi} front 0)
-     (place Q3 10000 -1000 front 0) (place Q4 10000 -9000 front 0)))
-  (library (image S (pin pad 1 0 0)) (padstack pad (shape (rect F.Cu -600 -600 600 600)) (attach off)))
-  (network (net PWR (pins P1-1 P2-1)) (net SIG (pins Q1-1 Q3-1)) (net SIG2 (pins Q2-1 Q4-1))
-    (class Power PWR (rule (width 500) (clearance 250)))))"""
-
-
-@pytest.mark.parametrize("resolution", [1, 2])
-@pytest.mark.parametrize("gap", [900, 1000, 1075])
-def test_a_wide_net_past_pads_it_does_not_fit_between_is_not_refused(gap, resolution):
-    # 0.3 mm fits the gap between the two pads, 0.5 mm does not: the grid
-    # must see that, rather than lay it wide and have the exact check drop it
-    ylo, yhi = -5000 - gap // 2 - 600, -5000 + gap // 2 + 600
-    result = build_exact_routing_result(
-        parse_dsn(_WIDE.format(ylo=ylo, yhi=yhi)), resolution=resolution
-    )
-    assert result.unrouted == []
-
-
-def _wide_router():
-    dsn = parse_dsn(_WIDE.format(ylo=-6050, yhi=-3950))
-    s = dsn.resolution.value
-    pwr = next(i for i, net in enumerate(dsn.nets, 1) if net.name == "PWR")
-    return GridRouter(
-        build_board(dsn),
-        trace_width=round(_rule_width_dsn(dsn) * s),
-        clearance=round(_rule_clearance_dsn(dsn) * s),
-        resolution=2,
-        net_widths={pwr: 5000},
-    ), pwr
-
-
-def test_a_wide_trace_keeps_clear_of_a_default_one_at_the_grid_diagonal():
-    router, _pwr = _wide_router()
-    # 0.5 mm against 0.3 mm needs 0.25 + 0.25 + 0.15 = 0.65 mm between centres,
-    # on either axis, since the exact check compares boxes
-    need = 2500 + router.clearance + router.half_width
-    for dx, dy in [(2, 2), (2, 1), (1, 2)]:
-        assert max(dx, dy) * router.step < need
-        assert (dx, dy) in router._halo_for(2500)
-
-
-def test_a_wide_rip_up_route_counts_what_its_extra_width_crosses():
-    router, pwr_net = _wide_router()
-    conns = router._conns = router._build_connections()
-    pwr = next(c for c in conns if c.net_no == pwr_net)
-    other = next(c for c in conns if c.net_no != pwr_net)
-    # a default-width trace two cells from the wide route's path
-    x, y = 20, 5
-    router._commit(other, _line((x - 3, y + 2), (x + 3, y + 2), 0))
-    path = _line((x - 3, y), (x + 3, y), 0)
-    spread = router._spread_for(2500)
-    assert other.index not in router._crossed_owners(path, pwr.net_no, conns)
-    assert other.index in router._crossed_owners(path, pwr.net_no, conns, spread)
-
-
-def test_a_pad_cell_check_uses_the_rotated_outline():
-    board = build_board(parse_dsn(_socket_dsn(60, "y")))
-    router = GridRouter(board, trace_width=3000, clearance=2500, resolution=2)
-    oval = next(p for p in board.get_pins() if p.component_ref == "P3" and p.name == "2")
-    box = oval.shape.bounding_box()
-    margin = router.clearance + router.half_width
-    exact = set(router._pad_cells(oval.shape, box, margin))
-    boxed = set(router._cells_in_box(box, margin))
-    assert exact < boxed
-    for cell in boxed - exact:
-        c = router._cell_center(cell)
-        square = IntBox(c.x - margin, c.y - margin, c.x + margin, c.y + margin)
-        assert oval.shape.intersection(square).dimension() != 2
-
-
-def test_a_via_by_a_chamfered_corner_is_judged_round():
-    """The grid keeps a via's centre its radius plus the edge clearance from
-    the outline. The exact check used the via's square, whose corner reaches
-    past a 45-degree chamfer where the round via does not."""
-    from freeroute.board.outline import BoardOutline
-    from freeroute.geometry import IntBox, IntPoint
-    from freeroute.route.exact_router import _inside_outline
-
-    # a 10 mm square with its lower-left corner cut at 45 degrees
-    outline = BoardOutline([IntPoint(*p) for p in
-                            [(30, 0), (100, 0), (100, 100), (0, 100), (0, 30)]])
-    half, edge = 4, 1
-    via = IntPoint(19, 20)  # its centre 6.4 from the chamfer x + y = 30
-    square = IntBox(via.x - half, via.y - half, via.x + half, via.y + half)
-    assert not outline.box_clear(square, edge)  # the square's corner: 0.7 away
-    assert _inside_outline(outline, [], [via], half + edge, edge)
-    # 4.2 from the chamfer: the round via itself is too close
-    assert not _inside_outline(outline, [], [IntPoint(18, 18)], half + edge, edge)

tests/route/test_negotiate.py

@@ -1,65 +0,0 @@
-"""--negotiate: PathFinder-style rounds on the empty board before routing."""
-
-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 _router(name, negotiate):
-    dsn = parse_dsn((FIXTURES / name).read_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),
-        negotiate=negotiate,
-    )
-
-
-def test_negotiation_leaves_the_board_empty_and_the_ends_as_they_were():
-    router = _router("true_density.dsn", 3)
-    conns = router._conns = router._build_connections()
-    ends = [(c.a_end, c.b_end) for c in conns]
-    router._negotiate(list(conns), conns)
-    assert router._history  # a dense board has contested cells
-    assert not router._cell_owner and not router._halo and not router._via_claims
-    assert not any(c.routed for c in conns)
-    assert [(c.a_end, c.b_end) for c in conns] == ends
-    assert router._present is None
-
-
-def test_sharing_is_priced_only_for_other_nets():
-    router = _router("true_density.dsn", 1)
-    node = (3, 4, 0)
-    router._history[node] = 2.0
-    router._present, router._present_cost = {node: {7: 1, 9: 2}}, 0.5
-    assert router._congestion(node, 7) == pytest.approx(2.5)  # one other net
-    assert router._congestion(node, 5) == pytest.approx(3.0)  # two other nets
-    router._present = None
-    assert router._congestion(node, 5) == pytest.approx(2.0)  # history only, after
-
-
-@pytest.mark.parametrize("name", ["ripup_needed.dsn", "true_density.dsn", "kicad_routable.dsn"])
-def test_negotiated_routing_keeps_the_occupancy_honest(name):
-    """Only routed connections hold cells afterwards, as without negotiation."""
-    router = _router(name, 3)
-    router.route()
-    conns = router._conns
-    assert all(conns[i].routed for i in router._cell_owner.values())
-    assert all(conns[i].routed for claims in router._halo.values() for i in claims)
-
-
-def test_option_reaches_the_router_and_is_off_by_default():
-    text = (FIXTURES / "kicad_routable.dsn").read_text()
-    plain, _, _ = route_dsn_board(parse_dsn(text))
-    again, _, _ = route_dsn_board(parse_dsn(text), negotiate=0)
-    assert plain.unrouted == again.unrouted

tests/route/test_real_board_geometry.py

@@ -51,22 +51,19 @@ def test_routes_keep_edge_clearance_at_a_rounded_corner():
                 assert outline.edge_distance(p) >= half + 500 * scale - 1
 
 
-@pytest.mark.parametrize("resolution", [1, 4])
-def test_every_pin_of_a_half_millimetre_pitch_row_escapes(resolution):
+@pytest.mark.parametrize(("resolution", "escape"), [(1, 2), (4, 5)])
+def test_every_pin_of_a_half_millimetre_pitch_row_escapes(resolution, escape):
     # Five 0.3 mm pads at 0.5 mm pitch, each wired to its own pad 8 mm away.
     # Between two neighbours a trace's centre has a legal band only 0.15 mm
-    # wide. At resolution 4 the 0.1 mm columns cannot miss it. At resolution
-    # 1 the 0.4 mm grid misses most bands, but a stub leaves its pin straight
-    # along the band and jogs to the column only past the pads, so every pin
-    # gets out there too, as the JAR manages (only 2 did before).
+    # wide. At resolution 1 the 0.4 mm grid misses most bands; at 4 its
+    # 0.1 mm columns cannot, and every pin gets out, as the JAR manages.
     places = " ".join(f"(place R{i} {6000 + 500 * i} -6000 front 0)" for i in range(5))
     places += " " + " ".join(f"(place F{i} {6000 + 500 * i} -14000 front 0)" for i in range(5))
     nets = " ".join(f"(net N{i} (pins R{i}-1 F{i}-1))" for i in range(5))
     result, _, _ = route_dsn_board_exact(
         parse_dsn(_dsn(f"(component P {places})", nets)), resolution=resolution
     )
-    assert len(result.routed_net_numbers) == 5
-    assert result.drc_clean
+    assert len(result.routed_net_numbers) == escape
 
 
 def test_resolution_one_has_no_halo_so_the_grid_is_unchanged():

tests/route/test_rollback.py

@@ -31,7 +31,7 @@ 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 claims in router._via_claims.values() for i in claims)
+    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)
 
 

tests/route/test_straight_pin_exits.py

@@ -1,58 +0,0 @@
-"""Pins of a 1.27 mm pitch row routed at 1.0 mm (the RN2483 module on the
-TTN Enschede mote). A trace centre has to stay within 0.06 mm of a pin's
-centreline to pass its neighbours, which no grid column hits, so a route
-leaves each pin straight along that line and only jogs to its column once
-past the pads. FreeRouting routes this row in full the same way."""
-
-from __future__ import annotations
-
-import pytest
-
-from freeroute.board import build_board
-from freeroute.board.items import Pin
-from freeroute.dsn import parse_dsn
-from freeroute.geometry import IntPoint
-from freeroute.route.grid_router import GridRouter
-from freeroute.route.pipeline import route_dsn_board_exact
-
-
-def _row(x0: int, pins: int = 6, skew: int = 3000) -> str:
-    places = " ".join(f"(place R{i} {x0 + 1270 * i} -5000 front 0)" for i in range(pins))
-    places += " " + " ".join(
-        f"(place T{i} {x0 + 1270 * i + skew} -15000 front 0)" for i in range(pins)
-    )
-    nets = " ".join(f"(net N{i} (pins R{i}-1 T{i}-1))" for i in range(pins))
-    return f"""(pcb t (parser) (resolution um 10) (unit um)
-  (structure (layer F.Cu (type signal)) (layer B.Cu (type signal))
-    (boundary (path pcb 0 0 0 30000 0 30000 -20000 0 -20000 0 0))
-    (via "Via[0-1]_600:400_um") (rule (width 1000) (clearance 200)))
-  (placement (component P {places}))
-  (library (image P (pin pad 1 0 0))
-    (padstack pad (shape (rect F.Cu -508 -762 508 762)) (attach off))
-    (padstack "Via[0-1]_600:400_um" (shape (circle F.Cu 600)) (shape (circle B.Cu 600))
-      (attach off)))
-  (network {nets}))"""
-
-
-@pytest.mark.parametrize("x0", [5000, 5150, 5300])
-def test_every_pin_of_a_row_leaves_straight_and_routes(x0):
-    # three offsets of the row against the grid; before, 2 or 3 of 6 routed
-    result, _, _ = route_dsn_board_exact(parse_dsn(_row(x0)), resolution=2)
-    assert len(result.routed_net_numbers) == 6
-    assert result.drc_clean
-
-
-def test_a_walled_in_pin_may_escape_to_the_column_either_side():
-    # two pins side by side leaving the same way can then jog apart
-    board = build_board(parse_dsn(_row(5000)))
-    router = GridRouter(board, trace_width=10000, clearance=2000, orthogonal=True, resolution=2)
-    router._conns = router._build_connections()
-    pin = next(
-        p for p in board.get_items()
-        if isinstance(p, Pin) and p.location == IntPoint(50000 + 2 * 12700, -50000)
-    )
-    net = pin.net_nos[0]
-    cx, cy = router._cell_of(pin.location)
-    nodes = router._escape_nodes(pin, net, router._conns, [0], (cx, cy))
-    columns = {x for x, y, _ in nodes if y != cy}
-    assert {cx - 1, cx, cx + 1} <= columns

tests/route/test_tree_nets.py

@@ -1,170 +0,0 @@
-"""Multi-pin nets: spanning-tree pairs, and connections that end on copper
-their net has already routed (a T into the tree)."""
-
-from __future__ import annotations
-
-import pytest
-
-from freeroute.board import build_board
-from freeroute.dsn import parse_dsn
-from freeroute.route import exact_router
-from freeroute.route.grid_router import GridRouter, RouteResult
-from freeroute.route.pipeline import _rule_clearance_dsn, _rule_width_dsn
-
-# P1 and P2 are nearest each other, so the tree pairs them first; P3 sits
-# under the middle of that leg, 50 mm below it and 90 mm from either pin.
-TEE = """(pcb "tee.dsn"
-  (parser (string_quote ") (space_in_quoted_tokens on) (host_cad "t") (host_version "1"))
-  (resolution um 10)
-  (unit um)
-  (structure
-    (layer F.Cu (type signal) (property (index 0)))
-    (boundary (path pcb 0  0 0  200000 0  200000 -100000  0 -100000  0 0))
-    (rule (width 2000) (clearance 2000))
-  )
-  (library
-    (padstack Rect_Pad (shape (rect F.Cu -1000 -1000 1000 1000)) (attach off))
-    (image PAD (pin Rect_Pad 1 0 0))
-  )
-  (placement
-    (component PAD
-      (place P1 60000 -20000 front 0)
-      (place P2 140000 -20000 front 0)
-      (place P3 100000 -70000 front 0)
-    )
-  )
-  (network
-    (net N (pins P1-1 P2-1 P3-1))
-    (class default (rule (width 2000) (clearance 2000)))
-  )
-  (wiring)
-)
-"""
-
-
-def _router(tree_nets=True, text=TEE):
-    dsn = parse_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),
-        orthogonal=True,
-        tree_nets=tree_nets,
-    )
-
-
-def test_pairs_follow_a_spanning_tree_not_the_pin_order():
-    router = _router()
-    conns = router._build_connections()
-    pairs = [(c.a.component_ref, c.b.component_ref) for c in conns]
-    assert pairs == [("P1", "P2"), ("P1", "P3")]
-    chain = _router(tree_nets=False)._build_connections()
-    assert [(c.a.component_ref, c.b.component_ref) for c in chain] == [("P1", "P2"), ("P2", "P3")]
-
-
-def test_the_third_pin_tees_into_the_first_leg():
-    router = _router()
-    result = router.route()
-    first, second = router._conns
-    assert result.unrouted == 0
-    # the second connection starts on the first one's copper, mid-leg
-    start = second.path[0]
-    assert start in first.copper and second.a_end is None
-    assert second.anchors == {first.index}
-    assert router._dependents[first.index] == {second.index}
-    assert abs(router._cell_center(start[:2]).x - 1_000_000) <= router.step
-    # and so its copper is the 50 mm drop, not 90 mm back to a pin
-    assert len(second.path) < len(router._conns[0].path)
-
-
-def test_without_trees_each_connection_ends_on_a_pin():
-    router = _router(tree_nets=False)
-    router.route()
-    assert all(c.anchors == frozenset() for c in router._conns)
-    assert all(c.a_end is not None and c.b_end is not None for c in router._conns)
-
-
-def test_ripping_an_anchor_takes_what_hangs_on_it():
-    router = _router()
-    router.route()
-    first, second = router._conns
-    victims = router._with_dependents([first], router._conns)
-    assert victims == [first, second]  # anchors first, as committed
-    for victim in victims:
-        router._rip(victim)
-    assert not first.routed and not second.routed
-    assert not router._dependents.get(first.index)
-    assert not router._cell_owner
-
-
-def test_the_snapshot_lists_anchors_before_what_hangs_on_them():
-    router = _router()
-    result = router.route()
-    assert result.connection_anchors == [(), (0,)]
-
-
-def test_the_exact_engine_drops_a_tee_whose_anchor_it_rejects(monkeypatch):
-    """A connection teed onto copper the exact check refuses would dangle."""
-    dsn = parse_dsn(TEE)
-    board = build_board(dsn)
-    real = exact_router.route_board
-
-    def grid_then_spoil(*args, **kwargs):
-        result: RouteResult = real(*args, **kwargs)
-        assert result.connection_anchors == [(), (0,)]
-        # move the first leg off the board edge so the exact check rejects it
-        net, wires, vias = result.connections[0]
-        result.connections[0] = (net, [(layer, [type(p)(p.x, p.y + 2_000_000) for p in pts])
-                                       for layer, pts in wires], vias)
-        return result
-
-    monkeypatch.setattr(exact_router, "route_board", grid_then_spoil)
-    s = dsn.resolution.value
-    exact = exact_router.route_board_exact(
-        board,
-        trace_width=round(_rule_width_dsn(dsn) * s),
-        clearance=round(_rule_clearance_dsn(dsn) * s),
-    )
-    assert len(exact.result.failed) == 2  # the leg and the T hanging on it
-    assert not exact.result.wires
-
-
-@pytest.mark.parametrize("tree_nets", [True, False])
-def test_occupancy_stays_honest(tree_nets):
-    router = _router(tree_nets)
-    router.route()
-    conns = router._conns
-    assert all(conns[i].routed for i in router._cell_owner.values())
-    for anchor, hanging in router._dependents.items():
-        for i in hanging:
-            assert conns[i].routed and conns[anchor].routed
-
-
-# P1-P2 along the top, P3 far off to the lower right, P4 just under the
-# middle of the P1-P2 leg.
-CHAIN_TEE = TEE.replace(
-    """      (place P3 100000 -70000 front 0)
-""",
-    """      (place P3 190000 -90000 front 0)
-      (place P4 100000 -40000 front 0)
-""",
-).replace("(pins P1-1 P2-1 P3-1)", "(pins P1-1 P2-1 P3-1 P4-1)")
-
-
-def test_a_tee_depends_on_every_connection_back_to_its_group():
-    """Joined as P1-P2, P2-P3, P3-P4, P4's connection tees onto P1-P2 copper,
-    which reaches P3's group only through P2-P3. Ripping P2-P3 must take the T
-    too, or it would be counted routed while cut off from P3."""
-    router = _router(text=CHAIN_TEE)
-    conns = router._conns = router._build_connections()
-    groups = {c.a.component_ref: c.a_group for c in conns}
-    groups.update({c.b.component_ref: c.b_group for c in conns})
-    for conn, (a, b) in zip(conns, (("P1", "P2"), ("P2", "P3"), ("P3", "P4")), strict=True):
-        conn.a_group, conn.b_group = groups[a], groups[b]
-    for conn in conns:
-        assert router._try_route(conn, conns)
-    first, second, third = conns
-    assert third.path[0] in first.copper  # the T lands on the far leg
-    assert third.anchors == {first.index, second.index}
-    assert router._with_dependents([second], conns) == [second, third]

tests/test_cli.py

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