A T depends on every connection between its copper and its group

Anchoring a T only on the connection whose copper it touched missed the
connections that tie that copper to the T's own group. When one of those
was ripped, the T stayed routed but cut off: on charge-sense freeroute
counted 15 unrouted while KiCad found 27 opens. Routed connections of a net
form a forest, so the path back is unique; the T now depends on all of it.
KiCad's opens and freeroute's count agree again (18 against 17, the extra
one a GND pour island left to the fill).

bench/bench.py

@@ -24,9 +24,11 @@ off. Exits non-zero if any run crashed or timed out.
 from __future__ import annotations
 
 import argparse
+from concurrent.futures import ThreadPoolExecutor, as_completed
 import json
 import math
 import os
+from pathlib import Path
 import re
 import shlex
 import subprocess
@@ -34,8 +36,6 @@ import sys
 import tempfile
 import threading
 import time
-from concurrent.futures import ThreadPoolExecutor, as_completed
-from pathlib import Path
 
 NOT_ROUTED = re.compile(r"freeroute: (\d+) connection\(s\) not routed")
 TO_ZONE = re.compile(r"freeroute: (\d+) more connection\(s\) left to a zone fill")

bench/diagnose.py

@@ -0,0 +1,310 @@
+"""Why did each connection fail? Sort the failures of one exact-engine run.
+
+    uv run python bench/diagnose.py board.dsn --edge-clearance 0.5 [--json out.json]
+
+Every connection the exact engine leaves unrouted lands in one bucket:
+
+rejected    the grid routed it, the exact geometry check refused its copper
+alone       it cannot be routed even on a board with no other routes: the
+            pads, keepouts or the grid itself are the limit, not congestion
+walled-in   in the routed board one of its pins has no way out: a flood from
+            the pin's end cells through free cells stops short (pin access)
+congestion  both pins can get out, but no free path joins them
+
+The board state is the one the result came from (the best pass), rebuilt by
+replaying that pass's paths. Diagnostic only: it reaches into the router.
+"""
+
+from __future__ import annotations
+
+import argparse
+from collections import Counter
+import json
+from pathlib import Path
+import sys
+
+from freeroute.board import build_board
+from freeroute.board.search_tree import ShapeSearchTree
+from freeroute.dsn import parse_dsn
+from freeroute.geometry.octagon import overlaps_2d
+from freeroute.route import grid_router
+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,
+)
+
+# a pin whose free neighbourhood holds fewer nodes than this is walled in
+FLOOD_LIMIT = 200
+
+
+def _capture_router():
+    """Patch GridRouter so the instance route_board_exact builds, and the paths
+    of its best pass, can be read back afterwards."""
+    seen: dict = {}
+    original_commit = GridRouter._commit
+    original_snapshot = GridRouter._snapshot
+
+    def commit(self, conn, path):
+        original_commit(self, conn, path)
+        self._diag_paths[conn.index] = (list(path), conn.a_end, conn.b_end)
+
+    def snapshot(self, conns):
+        self._diag_best = {c.index: self._diag_paths[c.index] for c in conns if c.routed}
+        seen["router"] = self
+        return original_snapshot(self, conns)
+
+    def init(self, *args, **kwargs):
+        original_init(self, *args, **kwargs)
+        self._diag_paths = {}
+        self._diag_best = {}
+        seen["kwargs"] = kwargs
+        seen["args"] = args
+
+    original_init = GridRouter.__init__
+    GridRouter.__init__ = init
+    GridRouter._commit = commit
+    GridRouter._snapshot = snapshot
+    return seen
+
+
+def _capture_conflicts() -> list:
+    """Record each exact-check refusal: the copper box, its kind, and the
+    shape it came too close to. The check stops at a connection's first
+    conflict, so refusals and rejected connections line up in order."""
+    log: list = []
+    original = ShapeSearchTree.clearance_conflict
+
+    def conflict(self, box, net_no, layer, clearance, kind="wire"):
+        hit = original(self, box, net_no, layer, clearance, kind)
+        if hit:
+            # the shape that tripped the check, found the way the check does
+            other = None
+            expanded = box.offset(clearance)
+            for s in self.overlapping(expanded):
+                if s.net_no == net_no or not s.on_layer(layer):
+                    continue
+                if s.blocks != "all" and s.blocks != kind + "s":
+                    continue
+                if not s.clearance:
+                    if s.tile.overlaps(box):
+                        other = s
+                        break
+                    continue
+                if (s.exact is not None and overlaps_2d(s.exact, expanded)) or (
+                    s.exact is None and s.tile.overlaps(expanded)
+                ):
+                    other = s
+                    break
+            log.append((net_no, kind, layer, box, clearance, other))
+        return hit
+
+    ShapeSearchTree.clearance_conflict = conflict
+    return log
+
+
+def _wall_name(wall, names) -> str:
+    if isinstance(wall, str):
+        if wall.startswith("fixed copper of net "):
+            net = int(wall.rsplit(" ", 1)[1])
+            return f"fixed copper of {names.get(net, net)}"
+        return wall
+    return names.get(wall, "pads/keepouts")
+
+
+def _gap(a, b) -> int:
+    dx = max(b.ll.x - a.ur.x, a.ll.x - b.ur.x, 0)
+    dy = max(b.ll.y - a.ur.y, a.ll.y - b.ur.y, 0)
+    return max(dx, dy)
+
+
+def _fresh(seen) -> GridRouter:
+    router = grid_router.GridRouter(*seen["args"], **seen["kwargs"])
+    router._conns = router._build_connections()
+    return router
+
+
+def _static_wall(router: GridRouter, node) -> str:
+    """What static copper closes a node: a keepout, copper already on the
+    board (a fixed via or track, by net), or a pad."""
+    if node in router._keepout:
+        return "keepout"
+    fixed = getattr(router, "_diag_fixed", None)
+    if fixed is None:
+        fixed = router._diag_fixed = {}
+        margin = router.clearance + router.half_width
+        for net, layers, box in router.board.get_fixed_copper():
+            for cell in router._cells_in_box(box, margin):
+                for layer in layers:
+                    fixed[(*cell, layer)] = net
+    net = fixed.get(node)
+    if net is not None:
+        return f"fixed copper of net {net}"
+    return "pads"
+
+
+def _flood(router: GridRouter, pin, net_no: int, conns) -> tuple[int, Counter]:
+    """How many nodes a pin can reach through free cells (up to FLOOD_LIMIT),
+    and which other nets' copper bounds the region."""
+    walls: Counter = Counter()
+    # the search starts on every end node unconditionally (it may leave one
+    # inside a wire keepout by a via), so the flood does too
+    start = list(router._end_nodes(pin, net_no, conns))
+    seen = set(start)
+    frontier = list(start)
+    while frontier and len(seen) < FLOOD_LIMIT:
+        x, y, layer = frontier.pop()
+        steps = [(x + dx, y + dy, layer) for dx, dy in router._neighbours]
+        if router._via_placeable((x, y), net_no, conns):
+            steps += [(x, y, other) for other in router.layers if other != layer]
+        elif len(seen) == 1:
+            # the pin's own exit is a via that other copper leaves no room for
+            via_nodes = [(*c, lay) for c in router._via_cells((x, y)) for lay in router.layers]
+            for owner in router._crossed_owners(via_nodes, net_no, conns):
+                walls[conns[owner].net_no] += 1
+        for n in steps:
+            if n in seen or not (0 <= n[0] < router.cols and 0 <= n[1] < router.rows):
+                continue
+            if router._enter_cost(n[:2], n[2], net_no, False, conns) is None:
+                # trace, via footprint or clearance halo, as rip-up sees them
+                owners = router._crossed_owners([n], net_no, conns)
+                for owner in owners:
+                    walls[conns[owner].net_no] += 1
+                if not owners:
+                    walls[_static_wall(router, n)] += 1
+                continue
+            seen.add(n)
+            frontier.append(n)
+    return len(seen), walls
+
+
+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,
+) -> dict:
+    dsn = parse_dsn(dsn_text)
+    names = {i + 1: n.name for i, n in enumerate(dsn.nets)}
+    scale = max(dsn.resolution.value, 1)
+    seen = _capture_router()
+    conflicts = _capture_conflicts()
+    exact = route_board_exact(
+        build_board(dsn),
+        trace_width=round(_rule_width_dsn(dsn) * scale),
+        clearance=round(_rule_clearance_dsn(dsn) * scale),
+        via_half=_via_half_board(dsn, scale),
+        edge_clearance=_mm_to_board(dsn, scale, edge_clearance_mm),
+        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
+    grid_failed = {(c.net_no, *_ends_of(c)) for c in routed._conns if c.index not in best}
+
+    # 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
+        state._commit(conns[idx], path)
+    empty = _fresh(seen)
+    # refusals in the order the check made them, one per rejected connection
+    per_net: dict[int, list] = {}
+    for net_no, kind, layer, box, clearance, other in conflicts:
+        if other is None:
+            what = "?"
+        elif other.net_no == -1:
+            what = "keepout" if other.clearance else "rule area"
+        else:
+            what = ("trace/via of " if other.routed else "pad of ") + names.get(other.net_no, "?")
+        need = clearance if other is None or other.clearance else 0
+        short = (need - _gap(box, other.tile)) / scale / 1000 if other is not None else 0
+        per_net.setdefault(net_no, []).append(
+            {"copper": kind, "layer": layer, "against": what, "short_mm": round(short, 4)}
+        )
+    by_key = {(c.net_no, *_ends_of(c)): c for c in conns}
+
+    rows = []
+    for failure in exact.result.failed:
+        net_no, a, b = failure[0], failure[1], failure[2]
+        zone = failure[3] if len(failure) > 3 else ""
+        if zone:
+            continue  # left to a zone fill, not a failure
+        key = (net_no, a, b)
+        row = {"net": names.get(net_no, str(net_no)), "a": a, "b": b}
+        conn = by_key.get(key)
+        if key not in grid_failed:
+            row["kind"] = "rejected"
+            if per_net.get(net_no):
+                row["conflict"] = per_net[net_no].pop(0)
+        elif conn is None:
+            row["kind"] = "unknown"
+        elif empty._search(empty._conns[conn.index], allow_ripup=False, conns=empty._conns) is None:
+            row["kind"] = "alone"
+        else:
+            walled = []
+            for end, group in ((a, conn.a_group), (b, conn.b_group)):
+                for pin in group[0][:1]:  # a group's first pin is its route end
+                    reach, walls = _flood(state, pin, net_no, conns)
+                    if reach < FLOOD_LIMIT:
+                        walled.append({
+                            "pin": end, "reach": reach,
+                            "walls": [
+                                _wall_name(n, names) for n, _ in walls.most_common(4)
+                            ],
+                        })
+            row["kind"] = "walled-in" if walled else "congestion"
+            if walled:
+                row["walled"] = walled
+        rows.append(row)
+    return {"failures": rows, "counts": dict(Counter(r["kind"] for r in rows))}
+
+
+def main(argv: list[str] | None = None) -> int:
+    ap = argparse.ArgumentParser(description=__doc__.split("\n\n")[0])
+    ap.add_argument("dsn", type=Path)
+    ap.add_argument("--edge-clearance", type=float, metavar="MM")
+    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)
+    for row in report["failures"]:
+        extra = ""
+        for w in row.get("walled", []):
+            extra += f"  [{w['pin']} reaches {w['reach']} cells, walled by {', '.join(w['walls'])}]"
+        if "conflict" in row:
+            c = row["conflict"]
+            extra += (f"  [{c['copper']} on layer {c['layer']} {c['short_mm']} mm too close"
+                      f" to {c['against']}]")
+        print(f"{row['kind']:11} {row['net']}: {row['a']} to {row['b']}{extra}")
+    total = sum(report["counts"].values())
+    print(f"\n{total} failed: " + ", ".join(f"{k} {v}" for k, v in sorted(report["counts"].items())),
+          file=sys.stderr)
+    if args.json:
+        args.json.write_text(json.dumps(report, indent=1))
+    return 0
+
+
+if __name__ == "__main__":
+    raise SystemExit(main())

bench/drc_check.sh

@@ -0,0 +1,67 @@
+#!/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/board.py

@@ -70,6 +70,27 @@ class BasicBoard:
     def get_traces(self) -> list[Trace]:
         return [it for it in self._items if isinstance(it, Trace)]
 
+    def get_fixed_copper(self) -> list[tuple[int, frozenset[int], IntBox]]:
+        """Copper already routed on the board (the DSN's ``wiring``), as
+        ``(net, layers, box)``. A track is its segments, its corners and the
+        round caps at its ends (as squares); a via is its largest pad."""
+        from freeroute.geometry.polyline import Polyline, PolylineShape, corner_box
+
+        out: list[tuple[int, frozenset[int], IntBox]] = []
+        for item in self._items:
+            if not item.fixed or not item.net_nos:
+                continue
+            net = item.net_nos[0]
+            if isinstance(item, Trace) and not item.is_empty():
+                layers = frozenset({item.layer})
+                for box in PolylineShape(Polyline(item.corners), item.half_width).tiles():
+                    out.append((net, layers, box))
+                for end in (item.corners[0], item.corners[-1]):
+                    out.append((net, layers, corner_box(end, item.half_width)))
+            elif isinstance(item, Via) and item.shape is not None:
+                out.append((net, frozenset(item.layers), item.shape.bounding_box()))
+        return out
+
     def get_vias(self) -> list[Via]:
         return [it for it in self._items if isinstance(it, Via)]
 

src/freeroute/board/build.py

@@ -12,9 +12,10 @@ 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 its
+Pad geometry: a rectangle pad becomes an exact :class:`IntBox`; a circle pad a
-bounding box (documented approximation pending an exact circle tile); a convex
+16-sided :class:`Simplex` drawn just outside it (its corners stand out by 2% of
-polygon pad an exact :class:`Simplex`. Every pad is placed centred on its pin
+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
 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).
@@ -23,6 +24,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
@@ -31,13 +33,16 @@ from freeroute.geometry.polygon_shape import PolygonShape
 
 from .board import BasicBoard
 from .clearance import ClearanceMatrix
-from .items import ConductionArea, ObstacleArea, Pin
+from .items import ConductionArea, ObstacleArea, Pin, Trace, Via
 from .layer import Layer, LayerStructure
 from .net import Nets
 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`."""
@@ -56,6 +61,7 @@ def build_board(dsn: DsnBoard) -> BasicBoard:
     _insert_keepouts(dsn, board, transform)
     _insert_image_keepouts(dsn, board, transform)
     _insert_zones(dsn, board, transform, nets)
+    _insert_wiring(dsn, board, transform, nets)
     return board
 
 
@@ -244,7 +250,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 IntBox(cx - r, cy - r, cx + r, cy + r)
+        return _circle_tile(cx, cy, r)
     if isinstance(shape, Rectangle):
         x0, y0, x1, y1 = shape.coords[:4]
         corners = [(x0, y0), (x1, y0), (x1, y1), (x0, y1)]
@@ -263,15 +269,65 @@ 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))))
-    if len(pts) >= 3:
+    # An oval's padded corners are not in outline order, and a mirrored
-        simplex = Simplex.from_corners(pts)
+    # part reverses the winding: take the convex hull, then either winding.
-        if not simplex.is_empty():
+    hull = _convex_hull(pts)
-            return simplex
+    if len(hull) >= 3:
+        for corners in (hull, hull[::-1]):
+            simplex = Simplex.from_corners(corners)
+            if not simplex.is_empty():
+                return simplex
     xs = [p.x for p in pts] or [0]
     ys = [p.y for p in pts] or [0]
     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):
@@ -281,7 +337,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 IntBox(cx - r, cy - r, cx + r, cy + r)  # bounding-box approximation
+        return _circle_tile(cx, cy, r)
     if isinstance(shape, (Polygon, Path)):
         coords = shape.coords
         pts = [
@@ -333,10 +389,20 @@ def _insert_keepouts(dsn: DsnBoard, board: BasicBoard, transform: CoordinateTran
                     tiles=tiles,
                     blocks_wires=keepout.kind != "via_keepout",
                     blocks_vias=keepout.kind != "wire_keepout",
+                    clearance=not is_rule_area(keepout.area.name),
                 )
             )
 
 
+#: a structure keepout named with this prefix is a KiCad rule area (mckicad
+#: names them on export); it is checked for overlap only
+RULE_AREA_PREFIX = "rule_area"
+
+
+def is_rule_area(name: str | None) -> bool:
+    return bool(name) and name.startswith(RULE_AREA_PREFIX)
+
+
 def _area_border_tiles(shape: Shape, transform: CoordinateTransform) -> list:
     """Convex board tiles covering a keepout border shape.
 
@@ -461,6 +527,52 @@ def _placed_area_tiles(shape: Shape, place, transform: CoordinateTransform) -> l
     return [tile for tile in PolygonShape(pts).split_to_convex() if not tile.is_empty()]
 
 
+def _insert_wiring(dsn: DsnBoard, board: BasicBoard, transform: CoordinateTransform, nets) -> None:
+    """Tracks and vias already on the board, as fixed copper of their nets."""
+    layer_no = {layer.name: i for i, layer in enumerate(dsn.layers)}
+    signal_layers = [i for i, layer in enumerate(dsn.layers) if layer.is_signal]
+    numbers = {net.name: net.net_number for net in nets}
+    for wire in dsn.wires:
+        if wire.net not in numbers or wire.layer not in layer_no:
+            continue
+        c = wire.coords
+        corners = [transform.dsn_to_board_point(c[i], c[i + 1]) for i in range(0, len(c) - 1, 2)]
+        if len(corners) < 2:
+            continue
+        board.insert(
+            Trace(
+                net_nos=[numbers[wire.net]], fixed=True, layer=layer_no[wire.layer],
+                half_width=max(round(transform.dsn_to_board(wire.width / 2)), 1), corners=corners,
+            )
+        )
+    for via in dsn.vias:
+        padstack = dsn.padstack(via.padstack)
+        if via.net not in numbers or padstack is None or not padstack.shapes:
+            continue
+        layers: set[int] = set()
+        for shape in padstack.shapes:
+            if shape.layer in ("signal", "pcb"):
+                layers.update(signal_layers)
+            elif shape.layer in layer_no:
+                layers.add(layer_no[shape.layer])
+        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,
+                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),
+            )
+        )
+
+
 def _insert_zones(dsn: DsnBoard, board: BasicBoard, transform: CoordinateTransform, nets) -> None:
     """Each DSN plane as a ConductionArea of its net on its layer."""
     layer_no = {layer.name: i for i, layer in enumerate(dsn.layers)}

src/freeroute/board/items.py

@@ -76,6 +76,11 @@ class ObstacleArea(Item):
     #: tracks" rule area, where vias are allowed), via_keepout only vias
     blocks_wires: bool = True
     blocks_vias: bool = True
+    #: False for a KiCad rule area: copper may not overlap it but may touch
+    #: it, since KiCad's DRC applies no clearance to a rule area. Every other
+    #: keepout may stand for copper (a net tie, a track kept as it is), so it
+    #: keeps the clearance unless named as a rule area.
+    clearance: bool = True
 
     def is_obstacle(self) -> bool:
         return True
@@ -109,6 +114,11 @@ class Via(Item):
 
     padstack_name: str = ""
     location: IntPoint = field(default_factory=lambda: IntPoint(0, 0))
+    #: layer indices the via's pads occupy, and the largest pad as a box
+    layers: list[int] = field(default_factory=list)
+    shape: object = None
+    #: drill diameter in board units, when the padstack name gives it
+    drill: int = 0
 
 
 @dataclass

src/freeroute/board/search_tree.py

@@ -18,7 +18,7 @@ from __future__ import annotations
 
 from dataclasses import dataclass
 
-from freeroute.geometry import IntBox, Simplex, overlaps_2d, segment_octagon
+from freeroute.geometry import IntBox, IntPoint, Simplex, overlaps_2d, segment_octagon, segment_slab
 
 __all__ = ["TreeShape", "ShapeSearchTree"]
 
@@ -50,6 +50,8 @@ class TreeShape:
     #: which copper a keepout tile stops: "all", "wires" (a wire_keepout,
     #: vias allowed) or "vias" (a via_keepout)
     blocks: str = "all"
+    #: False for a rule area: copper may touch it, only overlap counts
+    clearance: bool = True
 
     def on_layer(self, layer: int) -> bool:
         return layer in self.layers
@@ -61,7 +63,9 @@ 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
+        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)
         return segment_octagon(a, b, half_width + clearance)
 
 
@@ -129,6 +133,8 @@ class ShapeSearchTree:
 
         Uses a strict 2-D overlap of the ``clearance``-expanded box, so tiles
         exactly ``clearance`` apart (touching after expansion) are allowed.
+        A rule area (``clearance=False``) only has to be clear of the copper
+        itself.
         """
         expanded = box.offset(clearance)
         for shape in self.overlapping(expanded):
@@ -136,6 +142,10 @@ class ShapeSearchTree:
                 continue
             if shape.blocks != "all" and shape.blocks != kind + "s":
                 continue  # a wire-only keepout does not stop a via, and so on
+            if not shape.clearance:
+                if shape.tile.overlaps(box):
+                    return True
+                continue
             if shape.exact is not None:
                 if overlaps_2d(shape.exact, expanded):
                     return True
@@ -143,6 +153,36 @@ 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):
+            if shape.clearance or not shape.on_layer(layer):
+                continue
+            if shape.blocks != "all" and shape.blocks != kind + "s":
+                continue
+            if shape.tile.overlaps(box):
+                return True
+        return False
+
     def clearance_conflict_shape(
         self, region, net_no: int, layer: int
     ) -> bool:
@@ -169,6 +209,8 @@ 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):
@@ -178,6 +220,13 @@ class ShapeSearchTree:
                     continue  # static input pair (e.g. pad vs pad) — not a routing DRC
                 if not (shape.layers & other.layers):
                     continue
+                if not (shape.clearance and other.clearance):
+                    # a rule area: only an overlap is a violation
+                    mine = shape.exact if shape.exact is not None else shape.tile
+                    theirs = other.exact if other.exact is not None else other.tile
+                    if overlaps_2d(mine, theirs):
+                        return shape
+                    continue
                 if shape.exact is None and other.exact is None:
                     if other.tile.overlaps(expanded):  # byte-identical box path
                         return shape

src/freeroute/cli.py

@@ -19,7 +19,7 @@ import argparse
 import sys
 
 from freeroute.dsn.reader import parse_dsn
-from freeroute.route.orders import best_of_orders
+from freeroute.route.orders import best_of_orders, promote_failures
 from freeroute.route.pipeline import (
     build_exact_routing_result,
     build_rooms_routing_result,
@@ -30,8 +30,8 @@ from freeroute.ses import write_ses
 #: which optional flags each engine actually implements. Anything not listed for
 #: an engine is rejected by :func:`_validate` rather than quietly ignored.
 ENGINE_OPTIONS: dict[str, frozenset[str]] = {
-    "grid": frozenset({"rip_up", "max_passes", "seed", "orders"}),
+    "grid": frozenset({"rip_up", "max_passes", "seed", "orders", "promote", "access", "negotiate", "rollback", "tree"}),
-    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders"}),
+    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access", "negotiate", "rollback", "tree"}),
     "room": frozenset({"shove", "pack"}),
 }
 
@@ -44,6 +44,11 @@ _FLAG_NAMES = {
     "max_passes": "-mp/--max-passes",
     "seed": "--seed",
     "orders": "--orders",
+    "promote": "--promote-failures",
+    "access": "--access-cost",
+    "negotiate": "--negotiate",
+    "rollback": "--no-rollback",
+    "tree": "--no-tree",
 }
 
 
@@ -150,6 +155,53 @@ def build_parser() -> argparse.ArgumentParser:
         help="grid and exact engines: route N connection orders in parallel and keep the "
         "one leaving the fewest connections unrouted (the default order is one of them)",
     )
+    parser.add_argument(
+        "--promote-failures",
+        type=int,
+        metavar="R",
+        help="grid and exact engines: up to R rounds, each routing the connections that "
+        "failed so far first; keeps the best round",
+    )
+    parser.add_argument(
+        "--access-cost",
+        type=float,
+        metavar="C",
+        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",
+        action="store_false",
+        help="grid and exact engines: keep every rip-up, as before. By default the "
+        "connections a rip-up displaces are rerouted at once and the rip-up is undone "
+        "if fewer connections end up routed",
+    )
+    parser.add_argument(
+        "--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,
+        default=0.25,
+        metavar="MM",
+        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(
         "--jobs",
         type=int,
@@ -177,6 +229,11 @@ def main(argv: list[str] | None = None) -> int:
             ("max_passes", args.max_passes is not None),
             ("seed", args.seed is not None),
             ("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),
         )
         if asked
     ]
@@ -210,6 +267,11 @@ def main(argv: list[str] | None = None) -> int:
             "edge_clearance_mm": args.edge_clearance,
             "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,
+            "rollback": args.rollback,
+            "tree_nets": args.tree_nets,
         }
     elif args.engine == "grid":
         options = {
@@ -218,12 +280,25 @@ def main(argv: list[str] | None = None) -> int:
             "max_passes": max_passes,
             "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,
+            "rollback": args.rollback,
+            "tree_nets": args.tree_nets,
         }
     if args.engine == "room":
         result = build_rooms_routing_result(
             dsn, layers=layers, shove=args.shove, pack=args.pack,
             edge_clearance_mm=args.edge_clearance,
         )
+    elif args.promote_failures and args.promote_failures > 1:
+        if args.orders:
+            parser.error("--orders and --promote-failures cannot be combined")
+        result, rounds = promote_failures(
+            dsn_text, args.engine, options, rounds=args.promote_failures, seed=args.seed
+        )
+        counts = ", ".join(str(m) for m, _z in rounds)
+        print(f"freeroute: {len(rounds)} rounds, unrouted {counts}; kept the best", file=sys.stderr)
     elif args.orders and args.orders > 1:
         result, kept, tried = best_of_orders(
             dsn_text, args.engine, options, orders=args.orders, seed=args.seed, jobs=args.jobs
@@ -247,6 +322,14 @@ def main(argv: list[str] | None = None) -> int:
         print(f"freeroute: {len(missing)} connection(s) not routed:", file=sys.stderr)
         for net, a, b, _zone in missing:
             print(f"  {net}: {a} to {b}", file=sys.stderr)
+    if result.narrowed:
+        print(
+            f"freeroute: {len(result.narrowed)} connection(s) of a wider net class only fitted "
+            "at the default width; their nets are written at the default width:",
+            file=sys.stderr,
+        )
+        for net, a, b in result.narrowed:
+            print(f"  {net}: {a} to {b}", file=sys.stderr)
     if in_zone:
         print(
             f"freeroute: {len(in_zone)} more connection(s) left to a zone fill that may join them:",

src/freeroute/dsn/model.py

@@ -27,6 +27,8 @@ __all__ = [
     "NetPin",
     "Net",
     "NetClass",
+    "WiringVia",
+    "WiringWire",
     "Keepout",
     "DsnBoard",
 ]
@@ -186,6 +188,26 @@ class Keepout:
     kind: str = "keepout"  # keepout | via_keepout | wire_keepout | place_keepout
 
 
+@dataclass
+class WiringWire:
+    """A track already on the board: ``(wire (path LAYER WIDTH x y ...) (net N))``."""
+
+    net: str
+    layer: str
+    width: float
+    coords: list[float] = field(default_factory=list)
+
+
+@dataclass
+class WiringVia:
+    """A via already on the board: ``(via PADSTACK x y (net N))``."""
+
+    net: str
+    padstack: str
+    x: float
+    y: float
+
+
 @dataclass
 class DsnBoard:
     """The fully parsed DSN file."""
@@ -197,6 +219,9 @@ class DsnBoard:
     layers: list[Layer] = field(default_factory=list)
     #: copper zones, as planes of a net
     planes: list[Plane] = field(default_factory=list)
+    #: copper already routed (the ``wiring`` scope), kept fixed
+    wires: list[WiringWire] = field(default_factory=list)
+    vias: list[WiringVia] = field(default_factory=list)
     #: bounding-box boundary shape (layer ``pcb``), if present
     boundary: Shape | None = None
     #: outline shapes (layer ``signal``)

src/freeroute/dsn/reader.py

@@ -9,6 +9,8 @@ tolerant ``skip_scope`` behaviour.
 
 from __future__ import annotations
 
+import re
+
 from .model import (
     ClearanceRule,
     ComponentPlace,
@@ -25,6 +27,8 @@ from .model import (
     Pin,
     Resolution,
     WidthRule,
+    WiringVia,
+    WiringWire,
 )
 from .sexp import SExp, parse
 from .shapes import Shape, read_area, read_shape
@@ -481,12 +485,26 @@ def _read_network(node: SExp, board: DsnBoard) -> None:
 # --- top level ---------------------------------------------------------------
 
 
+_STRING_QUOTE = re.compile(r"\(\s*string_quote\s+(\S)\s*\)")
+
+
+def _declared_quote(text: str) -> str:
+    """The quote character the file declares in ``(string_quote X)``.
+
+    Only that character opens a string. Without a declaration both kinds are
+    accepted, as before: KiCad declares ``"`` and then writes a bare ``'``
+    where a value is a single quote mark, e.g. a keycap part number.
+    """
+    found = _STRING_QUOTE.search(text[:4096])
+    return found.group(1) if found else "\"'"
+
+
 def parse_dsn(text: str) -> DsnBoard:
     """Parse DSN ``text`` into a :class:`DsnBoard`.
 
     Raises :class:`DsnParseError` if the top-level scope is not ``(pcb ...)``.
     """
-    top = parse(text)
+    top = parse(text, _declared_quote(text))
     if top.head != "pcb":
         raise DsnParseError(
             f"not a Specctra DSN file: expected top-level '(pcb ...)', got '({top.head} ...)'"
@@ -515,11 +533,45 @@ def parse_dsn(text: str) -> DsnBoard:
             _read_placement(it, board)
         elif head == "network":
             _read_network(it, board)
-        # `wiring` and unknown scopes are intentionally ignored for now.
+        elif head == "wiring":
+            _read_wiring(it, board)
+        # unknown scopes are ignored
 
     return board
 
 
+def _read_wiring(node: SExp, board: DsnBoard) -> None:
+    """Tracks and vias already on the board. They stay where they are: the
+    router treats them as copper of their net that other nets keep clear of."""
+    for it in node.items:
+        if not isinstance(it, SExp):
+            continue
+        net_scope = it.child("net")
+        net = _first_value(net_scope) if net_scope is not None else None
+        if not net:
+            continue  # netless copper would need a keepout, not a wire
+        if it.head == "wire":
+            path = it.child("path") or it.child("polyline_path")
+            vals = [v.text for v in path.values()] if path is not None else []
+            if len(vals) < 6:
+                continue
+            try:
+                width = float(vals[1])
+                coords = [float(v) for v in vals[2:]]
+            except ValueError:
+                continue
+            board.wires.append(WiringWire(net=net, layer=vals[0], width=width, coords=coords))
+        elif it.head == "via":
+            vals = [v.text for v in it.values()]
+            if len(vals) < 3:
+                continue
+            try:
+                x, y = float(vals[1]), float(vals[2])
+            except ValueError:
+                continue
+            board.vias.append(WiringVia(net=net, padstack=vals[0], x=x, y=y))
+
+
 def _read_plane(node: SExp):
     """``(plane <net> (polygon <layer> <width> x y ...))`` -> :class:`Plane`."""
     from .model import Plane

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
+from .octagon import ceil_sqrt2, overlaps_2d, segment_octagon, segment_slab
 from .point import IntPoint, Point, RationalPoint, point, rational_point
 from .polygon import Polygon
 from .polygon_shape import PolygonShape
@@ -59,5 +59,6 @@ __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", "overlaps_2d"]
+__all__ = ["ceil_sqrt2", "segment_octagon", "segment_slab", "overlaps_2d"]
 
 
 def ceil_sqrt2(radius: int) -> int:
@@ -82,6 +82,46 @@ 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

@@ -31,17 +31,20 @@ from dataclasses import dataclass, field
 import math
 
 from freeroute.board.board import BasicBoard
-from freeroute.board.items import Pin
+from freeroute.board.items import Pin, Via
 from freeroute.board.search_tree import ShapeSearchTree, TreeShape
 from freeroute.geometry import (
     IntBox,
     IntPoint,
     Polyline,
     PolylineShape,
+    Simplex,
     segment_box,
     segment_octagon,
+    segment_slab,
     shove_segment,
 )
+from freeroute.geometry.polyline import corner_box
 
 from .grid_router import RouteResult, route_board
 
@@ -95,6 +98,14 @@ def route_board_exact(
     resolution: int = 1,
     heuristic_weight: float = 1.0,
     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,
 ) -> ExactRouteResult:
     """Route ``board`` orthogonally and verify the result with exact geometry.
 
@@ -124,6 +135,14 @@ def route_board_exact(
         resolution=resolution,
         heuristic_weight=heuristic_weight,
         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,
     )
     edge = 0 if edge_clearance is None else edge_clearance
     outline = board.outline
@@ -141,7 +160,13 @@ 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:
-            tree.insert(TreeShape(next(owner), net, pin_layers, box))
+            # 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))
+    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():
+            tree.insert(TreeShape(next(owner), net, on, box))
     for obstacle in board.get_obstacle_areas():
         if obstacle.layer not in signal_layers:
             continue
@@ -153,38 +178,81 @@ def route_board_exact(
             box = tile.bounding_box()
             if not box.is_empty():
                 tree.insert(
-                    TreeShape(next(owner), -1, frozenset({obstacle.layer}), box, blocks=blocks)
+                    TreeShape(
+                        next(owner), -1, frozenset({obstacle.layer}), box,
+                        blocks=blocks, clearance=obstacle.clearance,
+                    )
                 )
 
     via_layers = frozenset(signal_layers)
     accepted: dict[int, _Accepted] = {}
+    fixed_vias = {
+        (item.net_nos[0], item.location)
+        for item in board.get_items()
+        if isinstance(item, Via) and item.fixed and item.net_nos
+    }
 
     # Verify connection by connection, so one conflicting segment of a
     # 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)
-    for (net_no, wires, vias), ends in sorted(
+    anchors_list = getattr(result, "connection_anchors", None) or [()] * len(result.connections)
-        zip(result.connections, ends_list, strict=False), key=lambda c: c[0][0]
+    # 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],
     ):
-        boxes = _copper_boxes(wires, vias, half_width, via_layers, via_half)
+        if any(a in dropped_at for a in anchors):
-        wire_count = len(_copper_boxes(wires, [], half_width, via_layers, via_half))
+            dropped_at.add(pos)
-        if any(
-            tree.clearance_conflict(
-                box, net_no, layer, clearance, "wire" if i < wire_count else "via"
-            )
-            for i, (box, box_layers) in enumerate(boxes)
-            for layer in box_layers
-        ) or (outline is not None and not all(outline.box_clear(b, edge) for b, _ in boxes)):
             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))
+        if any(
+            (
+                tree.segment_conflict(*seg, wire_half, net_no, layer, clearance)
+                if seg is not None
+                else 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 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
+            )
+        ):
+            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:
             acc = accepted[net_no] = _Accepted(wires=[], vias=[])
         acc.wires.extend(wires)
-        acc.vias.extend(vias)
+        # connections of one net that end on the same plane cell share its
-        for box, box_layers in boxes:
+        # 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 not _on_fixed_via(net_no, v, fixed_vias, via_half)
+        )
+        for box, box_layers, seg in pieces:
             oid = next(owner)
-            tree.insert(TreeShape(oid, net_no, box_layers, box, routed=True))
+            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)
@@ -231,6 +299,17 @@ def route_board_exact(
     for net_no, acc in accepted.items():
         clean.wires[net_no] = acc.wires
         clean.vias[net_no] = acc.vias
+    # shove and the diagonal pass lay copper at the default width: nets they
+    # recovered, and nets whose traces shove pushed aside
+    reshaped = (set(accepted) - accepted_before_recovery) | {
+        net for net, acc in accepted.items() if acc.shove_count
+    }
+    if diagonal:
+        reshaped = set(accepted)
+    clean.net_half = {
+        net: half for net, half in net_half.items() if net in accepted and net not in reshaped
+    }
+    clean.narrowed = list(result.narrowed)
 
     drc_clean = tree.has_violation(clearance) is None
     return ExactRouteResult(result=clean, tree=tree, drc_clean=drc_clean, shoves=shoves)
@@ -588,6 +667,47 @@ def _net_boxes(result, net_no, half_width, via_layers, via_half=None):
     )
 
 
+def _end_in_rule_area(tree, wires, half_width) -> bool:
+    """A wire's tiles stop at its end points, but a track ends in a round cap
+    half its width beyond them. Against other copper the pad or via there
+    covers it; a rule area has no clearance to absorb it, so check it."""
+    for layer, points in wires:
+        for end in (points[0], points[-1]):
+            if tree.rule_area_overlap(corner_box(end, half_width), layer):
+                return True
+    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_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]]] = []
@@ -600,6 +720,19 @@ 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/orders.py

@@ -65,3 +65,34 @@ def best_of_orders(
     scores = [score(r) for r in results]
     best = min(range(len(seeds)), key=lambda i: (scores[i], i))
     return results[best], seeds[best], list(zip(seeds, scores, strict=True))
+
+
+def promote_failures(
+    dsn_text: str,
+    engine: str,
+    options: dict,
+    *,
+    rounds: int,
+    seed: int | None = None,
+) -> tuple[RoutingResult, list[tuple[int, int]]]:
+    """Route, then route again with every connection that has failed so far
+    moved to the front, keeping the rest in their order. Returns the best
+    round's result and every round's score.
+
+    The promoted set only grows, so a connection that failed once keeps its
+    early place and two groups cannot take turns failing. Stops early when a
+    round routes everything or fails nothing new."""
+    numbers = {n.name: i + 1 for i, n in enumerate(parse_dsn(dsn_text).nets)}
+    first: frozenset = frozenset()
+    best: RoutingResult | None = None
+    scores: list[tuple[int, int]] = []
+    for _ in range(max(int(rounds), 1)):
+        result = route_once(dsn_text, engine, {**options, "route_first": first}, seed)
+        scores.append(score(result))
+        if best is None or scores[-1] < score(best):
+            best = result
+        failed = {(numbers.get(name), a, b) for name, a, b, zone in result.unrouted if not zone}
+        if not failed or failed <= first:
+            break
+        first = first | failed
+    return best, scores

src/freeroute/route/pipeline.py

@@ -12,6 +12,8 @@ to DSN units (dividing by the resolution) for the SES ``(wire (path ...))`` and
 
 from __future__ import annotations
 
+import re
+
 from freeroute.board import build_board
 from freeroute.dsn import DsnBoard, parse_dsn
 from freeroute.ses import RoutedVia, RoutedWire, RoutingResult, write_ses
@@ -34,6 +36,25 @@ def _rule_width_dsn(dsn: DsnBoard) -> float:
     return rules[0].value if rules else _DEFAULT_WIDTH_DSN
 
 
+def _net_widths_board(dsn: DsnBoard, scale: int) -> dict[int, int]:
+    """Track width of every net whose class asks for more than the default,
+    in board units, by net number (build_board numbers nets in DSN order)."""
+    default = _rule_width_dsn(dsn)
+    by_name: dict[str, float] = {}
+    for net_class in dsn.net_classes:
+        if not net_class.width_rules:
+            continue
+        width = net_class.width_rules[0].value
+        if width > default:
+            for name in net_class.net_names:
+                by_name[name] = max(by_name.get(name, 0.0), width)
+    return {
+        i + 1: round(by_name[net.name] * scale)
+        for i, net in enumerate(dsn.nets)
+        if net.name in by_name
+    }
+
+
 def _rule_clearance_dsn(dsn: DsnBoard) -> float:
     for rule in dsn.structure_rules.clearance_rules:
         if not rule.class_pairs:  # the layer-wide default clearance
@@ -53,6 +74,20 @@ def _mm_to_board(dsn: DsnBoard, scale: int, value_mm: float | None) -> int | Non
     return round(value_mm / unit_mm * scale)
 
 
+def _via_drill_board(dsn: DsnBoard, scale: int) -> int | None:
+    """The via's drill in board units, from KiCad's padstack name
+    (``Via[0-1]_600:300_um`` is a 600 um pad with a 300 um drill); None when
+    the name does not say, and the pad size stands in for it."""
+    match = re.search(r"_([\d.]+):([\d.]+)_um", _via_padstack(dsn))
+    if not match:
+        return None
+    return round(float(match.group(2)) * _dsn_units_per_um(dsn) * scale)
+
+
+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 _via_half_board(dsn: DsnBoard, scale: int) -> int | None:
     """Half the via pad's size in board units, from the DSN's via padstack.
 
@@ -81,6 +116,12 @@ def route_dsn_board(
     rip_up: bool = True,
     max_passes: int = 10,
     seed: int | None = None,
+    route_first: frozenset | None = None,
+    access_cost: float = 0.0,
+    negotiate: int = 0,
+    hole_to_hole_mm: float = 0.25,
+    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
@@ -102,6 +143,14 @@ def route_dsn_board(
         rip_up=rip_up,
         max_passes=max_passes,
         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,
     )
     return result, scale, [layer.name for layer in dsn.layers]
 
@@ -116,6 +165,9 @@ def _to_routing_result(route, dsn: DsnBoard, scale: int, layer_names: list[str])
     result = RoutingResult()
     for net_no, segments in route.wires.items():
         name = numbers_to_names.get(net_no, str(net_no))
+        # its class's width when every connection of the net went in at it
+        half = getattr(route, "net_half", {}).get(net_no)
+        net_width = 2 * half / scale if half else width_dsn
         for layer_index, path in segments:
             layer_name = layer_names[layer_index] if layer_index < len(layer_names) else "F.Cu"
             coords: list[float] = []
@@ -123,7 +175,7 @@ def _to_routing_result(route, dsn: DsnBoard, scale: int, layer_names: list[str])
                 coords.append(point.x / scale)
                 coords.append(point.y / scale)
             if len(coords) >= 4:
-                result.add_wire(name, RoutedWire(layer=layer_name, width=width_dsn, coords=coords))
+                result.add_wire(name, RoutedWire(layer=layer_name, width=net_width, coords=coords))
     for net_no, locations in route.vias.items():
         name = numbers_to_names.get(net_no, str(net_no))
         for loc in locations:
@@ -131,6 +183,9 @@ def _to_routing_result(route, dsn: DsnBoard, scale: int, layer_names: list[str])
     result.unrouted = [
         (numbers_to_names.get(n, str(n)), a, b, zone) for n, a, b, zone in getattr(route, "failed", [])
     ]
+    result.narrowed = [
+        (numbers_to_names.get(n, str(n)), a, b) for n, a, b in getattr(route, "narrowed", [])
+    ]
     return result
 
 
@@ -143,11 +198,23 @@ def build_routing_result(
     max_passes: int = 10,
     edge_clearance_mm: float | None = None,
     seed: int | None = None,
+    route_first: frozenset | None = None,
+    access_cost: float = 0.0,
+    negotiate: int = 0,
+    hole_to_hole_mm: float = 0.25,
+    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(
         dsn, layers=layers, rip_up=rip_up, max_passes=max_passes,
         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,
+        rollback=rollback,
+        tree_nets=tree_nets,
     )
     return _to_routing_result(route, dsn, scale, layer_names)
 
@@ -164,6 +231,12 @@ def route_dsn_board_exact(
     shove: bool = False,
     diagonal: bool = False,
     seed: int | None = None,
+    route_first: frozenset | None = None,
+    access_cost: float = 0.0,
+    negotiate: int = 0,
+    hole_to_hole_mm: float = 0.25,
+    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.
@@ -189,6 +262,14 @@ def route_dsn_board_exact(
         shove=shove,
         diagonal=diagonal,
         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,
     )
     return exact, scale, [layer.name for layer in dsn.layers]
 
@@ -205,6 +286,12 @@ def build_exact_routing_result(
     max_passes: int = 10,
     edge_clearance_mm: float | None = None,
     seed: int | None = None,
+    route_first: frozenset | None = None,
+    access_cost: float = 0.0,
+    negotiate: int = 0,
+    hole_to_hole_mm: float = 0.25,
+    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(
@@ -218,6 +305,12 @@ def build_exact_routing_result(
         resolution=resolution,
         heuristic_weight=heuristic_weight,
         seed=seed,
+        route_first=route_first,
+        access_cost=access_cost,
+        negotiate=negotiate,
+        hole_to_hole_mm=hole_to_hole_mm,
+        rollback=rollback,
+        tree_nets=tree_nets,
     )
     return _to_routing_result(exact.result, dsn, scale, layer_names)
 

src/freeroute/route/room_router.py

@@ -515,6 +515,10 @@ def route_board_rooms(
         pin_layers = frozenset(layer for layer in pin.layers if layer in signal_layers)
         if pin_layers:
             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():
+            tree.insert(TreeShape(next(owner), net, on, box))
     for obstacle in board.get_obstacle_areas():
         if obstacle.layer not in signal_layers:
             continue

src/freeroute/ses/model.py

@@ -60,6 +60,9 @@ class RoutingResult:
     #: connections the router could not make: (net name, one end, other end,
     #: the zone both ends sit in or "") -- a zone's fill may join the latter
     unrouted: list[tuple[str, str, str, str]] = field(default_factory=list)
+    #: connections of a wider net class that only fitted at the default width
+    #: (net name, one end, other end); their net is written at the default
+    narrowed: list[tuple[str, str, str]] = field(default_factory=list)
 
     def net(self, name: str, *, create: bool = False) -> RoutedNet | None:
         """Return the :class:`RoutedNet` with ``name`` (creating it if asked)."""

tests/board/test_build.py

@@ -254,3 +254,37 @@ def test_via_size_comes_from_the_via_padstack():
     from freeroute.route.pipeline import _via_half_board
 
     assert _via_half_board(parse_dsn(_PAD_DSN), 10) == 3000   # 0.6 mm via, board units
+
+
+# --- rule areas: overlap only ------------------------------------------------
+
+_CHANNEL_DSN = """(pcb channel.dsn
+  (parser (string_quote ")) (resolution um 10) (unit um)
+  (structure
+    (layer F.Cu (type signal)) (layer B.Cu (type signal))
+    (boundary (path pcb 0  0 0  40000 0  40000 -30000  0 -30000  0 0))
+    (keepout "{name}top" (polygon signal 0  18000 0  22000 0  22000 -14750  18000 -14750))
+    (keepout "{name}bottom" (polygon signal 0  18000 -15250  22000 -15250  22000 -30000  18000 -30000))
+    (rule (width 250) (clearance 150)))
+  (placement (component P (place P1 5000 -15000 front 0) (place P2 35000 -15000 front 0)))
+  (library (image P (pin pad 1 0 0)) (padstack pad (shape (circle F.Cu 600)) (attach off)))
+  (network (net N (pins P1-1 P2-1))))"""
+
+
+def test_a_keepout_named_rule_area_takes_no_clearance():
+    named = _areas(_CHANNEL_DSN.format(name="rule_area_"))
+    plain = _areas(_CHANNEL_DSN.format(name=""))
+    assert named and not any(a.clearance for a in named)
+    assert plain and all(a.clearance for a in plain)
+
+
+def _route_channel(name):
+    from freeroute.route.pipeline import build_exact_routing_result
+
+    return build_exact_routing_result(parse_dsn(_CHANNEL_DSN.format(name=name)), resolution=2)
+
+
+def test_a_trace_may_run_beside_a_rule_area_closer_than_clearance():
+    # the 0.5 mm channel fits a 0.25 mm trace, but not with 0.15 mm each side
+    assert _route_channel("rule_area_").unrouted == []
+    assert _route_channel("").unrouted != []

tests/board/test_search_tree.py

@@ -62,3 +62,37 @@ def test_has_violation_ignores_static_pad_pairs():
     # a routed trace of net 3 within clearance of pad net 1 -> violation
     tree.insert(shape(2, 3, 0, IntBox(11, 0, 20, 10), routed=True))
     assert tree.has_violation(clearance=20) is not None
+
+
+def test_a_rule_area_conflicts_only_on_overlap():
+    tree = ShapeSearchTree()
+    tree.insert(TreeShape(1, -1, frozenset({0}), IntBox(100, 0, 200, 100), clearance=False))
+    near = IntBox(0, 0, 95, 100)  # 5 short of the area, well inside clearance 50
+    over = IntBox(0, 0, 105, 100)
+    assert not tree.clearance_conflict(near, 7, 0, 50)
+    assert tree.clearance_conflict(over, 7, 0, 50)
+
+
+def test_an_ordinary_keepout_still_needs_clearance():
+    tree = ShapeSearchTree()
+    tree.insert(TreeShape(1, -1, frozenset({0}), IntBox(100, 0, 200, 100)))
+    assert tree.clearance_conflict(IntBox(0, 0, 95, 100), 7, 0, 50)
+
+
+def test_the_routed_board_check_treats_a_rule_area_the_same_way():
+    tree = ShapeSearchTree()
+    tree.insert(TreeShape(1, -1, frozenset({0}), IntBox(100, 0, 200, 100), clearance=False))
+    tree.insert(TreeShape(2, 7, frozenset({0}), IntBox(0, 0, 95, 100), routed=True))
+    assert tree.has_violation(50) is None
+    tree.insert(TreeShape(3, 7, frozenset({0}), IntBox(150, 0, 160, 100), routed=True))
+    assert tree.has_violation(50) is not None
+
+
+
+def test_rule_area_overlap_sees_only_rule_areas():
+    tree = ShapeSearchTree()
+    tree.insert(TreeShape(1, -1, frozenset({0}), IntBox(100, 0, 200, 100), clearance=False))
+    tree.insert(TreeShape(2, -1, frozenset({0}), IntBox(300, 0, 400, 100)))
+    assert tree.rule_area_overlap(IntBox(90, 40, 110, 60), 0)
+    assert not tree.rule_area_overlap(IntBox(290, 40, 310, 60), 0)
+    assert not tree.rule_area_overlap(IntBox(90, 40, 110, 60), 1)

tests/dsn/test_reader.py

@@ -156,3 +156,26 @@ def test_unplaced_component_has_no_coords():
     place = board.placements[0].places[0]
     assert place.name == "U9"
     assert place.x is None and place.y is None
+
+
+# --- string_quote ----------------------------------------------------------
+
+_QUOTED = """(pcb q.dsn
+  (parser (string_quote {q}) (space_in_quoted_tokens on))
+  (resolution um 10) (unit um)
+  (structure (layer F.Cu (type signal)) (boundary (path pcb 0 0 0 1000 0 1000 1000 0 1000 0 0)))
+  (placement (component "SW1" (place SW1 100 100 front 0 (PN {pn}))))
+  (library)
+  (network)
+)"""
+
+
+def test_a_bare_apostrophe_is_an_atom_when_the_file_quotes_with_double_quotes():
+    # KiCad declares " and writes a keycap's part number as a bare '
+    board = parse_dsn(_QUOTED.format(q='"', pn="'"))
+    assert board.parser.string_quote == '"'
+
+
+def test_the_declared_quote_character_is_the_one_that_opens_strings():
+    board = parse_dsn(_QUOTED.format(q="'", pn="'10k 1%'").replace('"SW1"', "'SW1'"))
+    assert board.parser.string_quote == "'"

tests/route/test_axis_escapes.py

@@ -0,0 +1,113 @@
+"""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_fixed_wiring.py

@@ -0,0 +1,108 @@
+"""Tracks and vias already on the board (the DSN's wiring) are fixed copper."""
+
+from __future__ import annotations
+
+from freeroute.board import build_board
+from freeroute.dsn import parse_dsn
+from freeroute.route.pipeline import route_dsn_board_exact
+
+_DSN = """(pcb wired (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:300_um") (rule (width 250) (clearance 200)))
+  (placement (component S (place A1 5000 -10000 front 0) (place A2 25000 -10000 front 0)))
+  (library
+    (image S (pin smd 1 0 0))
+    (padstack smd (shape (rect F.Cu -400 -400 400 400)) (attach off))
+    (padstack "Via[0-1]_600:300_um" (shape (circle F.Cu 600)) (shape (circle B.Cu 600)) (attach off)))
+  (network (net SIG (pins A1-1 A2-1)) (net GND))
+  (wiring
+    (wire (path F.Cu 400  15000 0  15000 -20000) (net GND) (type route))
+    (via "Via[0-1]_600:300_um"  8000 -14000 (net GND) (type route))))"""
+
+
+def test_wiring_is_read_with_its_nets():
+    dsn = parse_dsn(_DSN)
+    assert [(w.net, w.layer, w.width) for w in dsn.wires] == [("GND", "F.Cu", 400.0)]
+    assert [(v.net, v.x, v.y) for v in dsn.vias] == [("GND", 8000.0, -14000.0)]
+
+
+def test_wiring_is_fixed_copper_and_not_a_connection_to_route():
+    board = build_board(parse_dsn(_DSN))
+    copper = board.get_fixed_copper()
+    gnd = next(n.net_number for n in board.nets if n.name == "GND")
+    assert copper and all(net == gnd for net, _, _ in copper)
+    assert not any(gnd in p.net_nos for p in board.get_pins())
+
+
+def test_other_nets_route_around_a_fixed_track():
+    dsn = parse_dsn(_DSN)
+    exact, scale, names = route_dsn_board_exact(dsn, resolution=2)
+    sig = next(i + 1 for i, n in enumerate(dsn.nets) if n.name == "SIG")
+    assert sig in exact.result.routed_net_numbers
+    assert exact.drc_clean
+    wall = 15000 * scale
+    for layer, pts in exact.result.wires.get(sig, []):
+        if names[layer] != "F.Cu":
+            continue
+        for p, q in zip(pts, pts[1:], strict=False):
+            assert not (min(p.x, q.x) < wall < max(p.x, q.x)), "crossed the GND track on F.Cu"
+
+
+# --- fixed wiring as connectivity ------------------------------------------
+
+_FANOUT = """(pcb fanout (parser) (resolution um 10) (unit um)
+  (structure
+    (layer F.Cu (type signal)) (layer In1.Cu (type power)) (layer In2.Cu (type power))
+    (layer B.Cu (type signal))
+    (boundary (path pcb 0  0 0  30000 0  30000 -20000  0 -20000  0 0))
+    (plane GND (polygon In1.Cu 0  500 -500  29500 -500  29500 -19500  500 -19500  500 -500))
+    (via "Via[0-3]_600:300_um") (rule (width 150) (clearance 150)))
+  (placement (component S (place G1 5000 -10000 front 0) (place A 10000 -10000 front 0)
+                          (place B 25000 -11500 back 0)))
+  (library
+    (image S (pin smd 1 0 0))
+    (padstack smd (shape (rect F.Cu -300 -300 300 300)) (attach off))
+    (padstack "Via[0-3]_600:300_um" (shape (circle F.Cu 600)) (shape (circle B.Cu 600)) (attach off)))
+  (network (net GND (pins G1-1)) (net SIG (pins A-1 B-1)))
+  (wiring
+    (wire (path F.Cu 150  5000 -10000  5000 -11500) (net GND) (type route))
+    (via "Via[0-3]_600:300_um"  5000 -11500 (net GND) (type route))
+    (wire (path F.Cu 150  10000 -10000  10000 -11500) (net SIG) (type route))
+    (via "Via[0-3]_600:300_um"  10000 -11500 (net SIG) (type route))
+    (wire (path F.Cu 300  2000 -2000  8000 -2000) (net GND) (type route))))"""
+
+
+def test_a_pad_fanned_out_to_its_plane_needs_no_route():
+    dsn = parse_dsn(_FANOUT)
+    exact, _scale, _names = route_dsn_board_exact(dsn, resolution=2)
+    gnd = next(i + 1 for i, n in enumerate(dsn.nets) if n.name == "GND")
+    assert exact.result.failed == []
+    assert not exact.result.vias.get(gnd) and not exact.result.wires.get(gnd)
+
+
+def test_a_fanned_out_signal_is_routed_from_its_via():
+    # B is on the bottom face, level with A's fan-out via: starting from that
+    # via on B.Cu is the cheapest way, and needs no via of its own
+    dsn = parse_dsn(_FANOUT)
+    exact, scale, names = route_dsn_board_exact(dsn, resolution=2)
+    sig = next(i + 1 for i, n in enumerate(dsn.nets) if n.name == "SIG")
+    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_grid_exact_agreement.py

@@ -0,0 +1,284 @@
+"""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

@@ -0,0 +1,65 @@
+"""--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_net_widths.py

@@ -0,0 +1,42 @@
+"""Net classes wider than the default are routed at their width where it fits."""
+
+from __future__ import annotations
+
+from freeroute.dsn import parse_dsn
+from freeroute.route.pipeline import build_exact_routing_result
+
+_BOARD = """(pcb widths (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))
+    {keepouts}
+    (rule (width 150) (clearance 150)))
+  (placement (component S (place P1 2000 -5000 front 0) (place P2 18000 -5000 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))
+    (class Power PWR (rule (width 400) (clearance 150)))))"""
+
+# two keepouts leave a 0.65 mm channel: room for 0.15 mm (0.45), not for 0.4 mm (0.7)
+_CHANNEL = (
+    '(keepout "" (polygon F.Cu 0  9000 0  11000 0  11000 -4675  9000 -4675))\n'
+    '    (keepout "" (polygon F.Cu 0  9000 -5325  11000 -5325  11000 -10000  9000 -10000))'
+)
+
+
+def _route(keepouts=""):
+    return build_exact_routing_result(parse_dsn(_BOARD.format(keepouts=keepouts)), resolution=2)
+
+
+def test_a_wider_class_is_routed_and_written_at_its_width():
+    result = _route()
+    assert result.unrouted == [] and result.narrowed == []
+    widths = {w.width for net in result.nets for w in net.wires}
+    assert widths == {400.0}
+
+
+def test_a_wider_class_that_does_not_fit_falls_back_to_the_default():
+    result = _route(_CHANNEL)
+    assert result.unrouted == []
+    assert [net for net, _a, _b in result.narrowed] == ["PWR"]
+    widths = {w.width for net in result.nets for w in net.wires}
+    assert widths == {150.0}

tests/route/test_orders.py

@@ -5,7 +5,13 @@ from __future__ import annotations
 from pathlib import Path
 
 from freeroute.cli import main
-from freeroute.route.orders import best_of_orders, candidate_seeds, route_once, score
+from freeroute.route.orders import (
+    best_of_orders,
+    candidate_seeds,
+    promote_failures,
+    route_once,
+    score,
+)
 
 FIXTURES = Path(__file__).resolve().parent.parent / "dsn" / "fixtures"
 # Greedy (no rip-up), the default order strands a net here and seeds 1 to 3 do not.
@@ -42,3 +48,31 @@ def test_cli_orders_writes_the_best_session(tmp_path, capsys):
     assert "tried 3 orders, kept --seed 1" in err
     assert "not routed" not in err
     assert out.read_text().startswith("(session")
+
+
+def test_promoting_the_failed_connection_routes_it():
+    best, rounds = promote_failures(RIPUP, "grid", GREEDY, rounds=3)
+    assert rounds == [(1, 0), (0, 0)]  # stops once nothing fails
+    assert score(best) == (0, 0)
+
+
+def test_nothing_promoted_is_the_plain_order():
+    plain = route_once(RIPUP, "grid", {}, None)
+    empty = route_once(RIPUP, "grid", {"route_first": frozenset()}, None)
+    assert plain == empty
+
+
+def test_cli_promote_failures(tmp_path, capsys):
+    out = tmp_path / "p.ses"
+    rc = main(
+        [
+            str(FIXTURES / "ripup_needed.dsn"),
+            "--no-rip-up",
+            "--promote-failures",
+            "3",
+            "-do",
+            str(out),
+        ]
+    )
+    assert rc == 0
+    assert "2 rounds, unrouted 1, 0" in capsys.readouterr().err

tests/route/test_real_board_geometry.py

@@ -51,19 +51,22 @@ def test_routes_keep_edge_clearance_at_a_rounded_corner():
                 assert outline.edge_distance(p) >= half + 500 * scale - 1
 
 
-@pytest.mark.parametrize(("resolution", "escape"), [(1, 2), (4, 5)])
+@pytest.mark.parametrize("resolution", [1, 4])
-def test_every_pin_of_a_half_millimetre_pitch_row_escapes(resolution, escape):
+def test_every_pin_of_a_half_millimetre_pitch_row_escapes(resolution):
     # 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 1 the 0.4 mm grid misses most bands; at 4 its
+    # wide. At resolution 4 the 0.1 mm columns cannot miss it. At resolution
-    # 0.1 mm columns cannot, and every pin gets out, as the JAR manages.
+    # 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).
     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) == escape
+    assert len(result.routed_net_numbers) == 5
+    assert result.drc_clean
 
 
 def test_resolution_one_has_no_halo_so_the_grid_is_unchanged():
@@ -202,6 +205,18 @@ def test_smd_pads_reach_an_inner_plane_by_their_own_via():
     assert all(names[layer] in ("F.Cu", "B.Cu") for segs in result.result.wires.values() for layer, _ in segs)
 
 
+def test_a_pad_outside_the_plane_routes_to_it():
+    # G1 sits left of a plane that covers only the right half, so its route
+    # has to reach the plane's cells: those ends are the plane, not a pin
+    dsn_text = _four_layer_dsn().replace(
+        "(plane GND (polygon In1.Cu 0  500 -500  29500 -500  29500 -29500  500 -29500  500 -500))",
+        "(plane GND (polygon In1.Cu 0  15000 -500  29500 -500  29500 -29500  15000 -29500  15000 -500))",
+    )
+    result, _scale, _names = route_dsn_board_exact(parse_dsn(dsn_text))
+    gnd = next(i + 1 for i, n in enumerate(parse_dsn(dsn_text).nets) if n.name == "GND")
+    assert gnd in result.result.routed_net_numbers
+
+
 def test_a_through_hole_pad_inside_a_plane_needs_no_route():
     from freeroute.route.grid_router import _connected_groups
 
@@ -211,3 +226,29 @@ def test_a_through_hole_pad_inside_a_plane_needs_no_route():
     groups = _connected_groups(gnd_pins, plane, frozenset(id(z) for z in plane))
     hub = next(g for g in groups if g[1])
     assert [p.component_ref for p in hub[0]] == ["GT"]
+
+
+def test_a_pad_inside_a_via_keepout_reaches_the_plane_by_a_via_outside_it():
+    # a sensor's GND pad: vias are forbidden under the body, so the route
+    # has to leave on the top layer and drop to the plane past the keepout
+    dsn = parse_dsn("""(pcb repro (parser) (resolution um 10) (unit um)
+  (structure
+    (layer F.Cu (type signal)) (layer In1.Cu (type power)) (layer In2.Cu (type power))
+    (layer B.Cu (type signal))
+    (boundary (path pcb 0  0 0  20000 0  20000 -20000  0 -20000  0 0))
+    (plane GND (polygon In1.Cu 0  500 -500  19500 -500  19500 -19500  500 -19500  500 -500))
+    (via_keepout "" (polygon signal 0  8500 -8500  11500 -8500  11500 -11500  8500 -11500  8500 -8500))
+    (via "Via[0-3]_600:300_um") (rule (width 150) (clearance 150)))
+  (placement (component S (place G1 10000 -10000 front 0)))
+  (library
+    (image S (pin smd 1 0 0))
+    (padstack smd (shape (rect F.Cu -175 -300 175 300)) (attach off))
+    (padstack "Via[0-3]_600:300_um" (shape (circle F.Cu 600)) (shape (circle B.Cu 600)) (attach off)))
+  (network (net GND (pins G1-1))))""")
+    exact, scale, _names = route_dsn_board_exact(dsn, resolution=2)
+    assert exact.result.failed == []
+    (via,) = exact.result.vias[1]
+    half = 300 * scale  # the via's radius
+    outside = (via.x + half <= 8500 * scale or via.x - half >= 11500 * scale
+               or via.y - half >= -8500 * scale or via.y + half <= -11500 * scale)
+    assert outside, f"via at {via} is inside the via keepout"

tests/route/test_rollback.py

@@ -0,0 +1,43 @@
+"""--rollback: a rip-up that loses connections is undone, leaving no trace."""
+
+from __future__ import annotations
+
+from pathlib import Path
+
+import pytest
+
+from freeroute.board import build_board
+from freeroute.dsn import parse_dsn
+from freeroute.route.grid_router import GridRouter
+from freeroute.route.pipeline import _rule_clearance_dsn, _rule_width_dsn, route_dsn_board
+
+FIXTURES = Path(__file__).resolve().parent.parent / "dsn" / "fixtures"
+
+
+def _routed_router(name):
+    dsn = parse_dsn((FIXTURES / name).read_text())
+    s = dsn.resolution.value
+    router = GridRouter(
+        build_board(dsn),
+        trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s),
+        rollback=True,
+    )
+    return router, router.route()
+
+
+@pytest.mark.parametrize("name", ["ripup_needed.dsn", "true_density.dsn", "kicad_routable.dsn"])
+def test_occupancy_only_holds_routed_connections(name):
+    router, _ = _routed_router(name)
+    conns = router._conns
+    assert all(conns[i].routed for i in router._cell_owner.values())
+    assert all(conns[i].routed for claims in router._via_claims.values() for i in claims)
+    assert all(conns[i].routed for claims in router._halo.values() for i in claims)
+
+
+@pytest.mark.parametrize("name", ["ripup_needed.dsn", "true_density.dsn", "kicad_routable.dsn"])
+def test_rollback_never_routes_fewer_than_plain_rip_up(name):
+    text = (FIXTURES / name).read_text()
+    plain, _, _ = route_dsn_board(parse_dsn(text), rollback=False)
+    undo, _, _ = route_dsn_board(parse_dsn(text))
+    assert undo.unrouted <= plain.unrouted

tests/route/test_straight_pin_exits.py

@@ -0,0 +1,58 @@
+"""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

@@ -0,0 +1,170 @@
+"""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/route/test_via_spacing.py

@@ -0,0 +1,136 @@
+"""Vias keep hole-to-hole spacing, even within one net."""
+
+from __future__ import annotations
+
+import itertools
+import math
+
+from freeroute.dsn import parse_dsn
+from freeroute.route.pipeline import route_dsn_board_exact
+
+# four GND pads 0.5 mm apart over a GND plane: each drops a via to the plane
+_DSN = """(pcb holes (parser) (resolution um 10) (unit um)
+  (structure
+    (layer F.Cu (type signal)) (layer In1.Cu (type power)) (layer In2.Cu (type power))
+    (layer B.Cu (type signal))
+    (boundary (path pcb 0  0 0  20000 0  20000 -20000  0 -20000  0 0))
+    (plane GND (polygon In1.Cu 0  500 -500  19500 -500  19500 -19500  500 -19500  500 -500))
+    (via "Via[0-3]_500:300_um") (rule (width 150) (clearance 150)))
+  (placement (component S (place G1 9000 -10000 front 0) (place G2 9500 -10000 front 0)
+                          (place G3 10000 -10000 front 0) (place G4 10500 -10000 front 0)))
+  (library
+    (image S (pin smd 1 0 0))
+    (padstack smd (shape (rect F.Cu -150 -300 150 300)) (attach off))
+    (padstack "Via[0-3]_500:300_um" (shape (circle F.Cu 500)) (shape (circle B.Cu 500)) (attach off)))
+  (network (net GND (pins G1-1 G2-1 G3-1 G4-1))))"""
+
+
+def test_a_nets_own_vias_keep_hole_to_hole_spacing():
+    dsn = parse_dsn(_DSN)
+    exact, scale, _ = route_dsn_board_exact(dsn, resolution=2)
+    assert exact.result.failed == []
+    vias = exact.result.vias[1]
+    assert len(set(vias)) == len(vias), "a via written twice"
+    need = (300 + 250) * scale  # drill + 0.25 mm, centre to centre
+    for a, b in itertools.combinations(vias, 2):
+        assert math.hypot(a.x - b.x, a.y - b.y) >= need, f"vias at {a} and {b} too close"
+
+
+def test_connections_sharing_a_plane_via_write_it_once():
+    # eight GND pads 0.4 mm apart: the hole spacing makes several of them
+    # end on the same plane via, which must come out once, not once each
+    pads = " ".join(f"(place G{i} {9000 + 400 * i} -10000 front 0)" for i in range(8))
+    pins = " ".join(f"G{i}-1" for i in range(8))
+    dsn = parse_dsn(
+        _DSN.replace(
+            "(place G1 9000 -10000 front 0) (place G2 9500 -10000 front 0)\n"
+            "                          (place G3 10000 -10000 front 0) (place G4 10500 -10000 front 0)",
+            pads,
+        )
+        .replace("(pins G1-1 G2-1 G3-1 G4-1)", f"(pins {pins})")
+        .replace("(rect F.Cu -150 -300 150 300)", "(rect F.Cu -125 -300 125 300)")
+    )
+    exact, _scale, _ = route_dsn_board_exact(dsn, resolution=2)
+    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

@@ -156,6 +156,11 @@ def test_cli_supported_combinations_are_accepted(tmp_path):
         "max_passes": ["-mp", "4"],
         "seed": ["--seed", "3"],
         "orders": ["--orders", "2"],
+        "promote": ["--promote-failures", "2"],
+        "access": ["--access-cost", "5"],
+        "negotiate": ["--negotiate", "2"],
+        "rollback": ["--no-rollback"],
+        "tree": ["--no-tree"],
     }
     for engine, options in ENGINE_OPTIONS.items():
         for option in options: