--history-cost: PathFinder's history term in the rip-up search (off by default)

Each cell a rip-up route pushes through another net's copper gets this much more expensive for every later search. Measured on the TerraHawk sense board it helped one flow and hurt another (grid unrouted 44 -> 37 at 1.0 on the production DSN; DRC-unconnected 41 -> 53 on a stripped copy), and a single run swings by about ten on small changes either way, so it stays off until a benchmark over several boards and orders shows a real gain.
2026-09-27 14:43:00 -06:00
30 changed files with 102 additions and 2771 deletions
@@ -20,7 +20,3 @@ htmlcov/
 # Editor / OS
 .DS_Store
 *.swp
 # Benchmark inputs and results: board lists name local, often private, designs
 /bench/boards*.txt
 /bench/results/
@@ -1,206 +0,0 @@
 """Route boards under several connection orders and compare variants fairly.
 One routing run says little: which connection routes first moves a result by
 ten connections either way on a crowded board. This runs every board with
 every variant under the same seeds (``--seed``), so variant A and variant B
 face the same order on seed 3, and compares them seed by seed.
    uv run python bench/bench.py BOARDS -v base= -v hist1="--history-cost 1" \\
        --seeds 6 --jobs 4 --out bench/results/hist.jsonl
 BOARDS is a text file, one board per line: a name, a DSN path and any flags
 that board always needs, e.g.
    sense  /path/to/charge-sense.dsn  --edge-clearance 0.5
    # comments and blank lines are ignored
 A variant is ``NAME=FLAGS``, or ``NAME@SRC=FLAGS`` to run the code under SRC
 (a worktree's ``src`` directory) rather than the installed package. The first
 variant is the baseline. Results are appended to --out as JSON lines, and runs
 already in it are skipped, so an interrupted benchmark picks up where it left
 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
 import sys
 import tempfile
 import threading
 import time
 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")
 def parse_boards(path: Path) -> list[tuple[str, Path, list[str]]]:
    boards = []
    for line in path.read_text().splitlines():
        words = shlex.split(line, comments=True)
        if not words:
            continue
        if len(words) < 2:
            raise SystemExit(f"{path}: want 'name path [flags]', got {line!r}")
        dsn = Path(words[1]).expanduser()
        if not dsn.is_file():
            raise SystemExit(f"{path}: no such DSN {dsn}")
        boards.append((words[0], dsn, words[2:]))
    return boards
 def parse_variant(spec: str) -> tuple[str, str | None, list[str]]:
    head, sep, flags = spec.partition("=")
    if not sep or not head:
        raise SystemExit(f"variant {spec!r}: want NAME=FLAGS or NAME@SRC=FLAGS")
    name, _, src = head.partition("@")
    if src and not (Path(src) / "freeroute").is_dir():
        raise SystemExit(f"variant {name}: {src} has no freeroute package")
    return name, src or None, shlex.split(flags)
 def run_one(board, variant, seed: int, timeout: float) -> dict:
    name, dsn, board_flags = board
    vname, src, flags = variant
    env = dict(os.environ)
    if src:
        env["PYTHONPATH"] = src + os.pathsep + env.get("PYTHONPATH", "")
    with tempfile.TemporaryDirectory() as tmp:
        cmd = [
            sys.executable, "-m", "freeroute.cli", str(dsn), "-do", f"{tmp}/out.ses",
            *board_flags, *flags, "--seed", str(seed),
        ]
        start = time.monotonic()
        proc = subprocess.Popen(
            cmd, env=env, stdout=subprocess.DEVNULL, stderr=subprocess.PIPE, text=True
        )
        expired = threading.Event()
        def expire() -> None:
            expired.set()
            proc.kill()
        timer = threading.Timer(timeout, expire)
        timer.start()
        err = proc.stderr.read()
        # reap it here rather than through Popen, to keep its peak memory
        _, wstatus, usage = os.wait4(proc.pid, 0)
        timer.cancel()
        proc.returncode = os.waitstatus_to_exitcode(wstatus)
        proc.stderr.close()
        status = "timeout" if expired.is_set() else (
            "ok" if proc.returncode == 0 else f"exit {proc.returncode}"
        )
        rss_mb = round(usage.ru_maxrss / 1024)
        secs = round(time.monotonic() - start, 1)
    missing = NOT_ROUTED.search(err)
    zone = TO_ZONE.search(err)
    return {
        "board": name, "variant": vname, "seed": seed, "status": status,
        "unrouted": int(missing.group(1)) if missing else 0,
        "to_zone": int(zone.group(1)) if zone else 0,
        "secs": secs, "rss_mb": rss_mb,
        "tail": err.strip().splitlines()[-1] if status != "ok" and err.strip() else "",
    }
 def mean_sd(xs: list[float]) -> tuple[float, float]:
    m = sum(xs) / len(xs)
    sd = math.sqrt(sum((x - m) ** 2 for x in xs) / (len(xs) - 1)) if len(xs) > 1 else 0.0
    return m, sd
 def report(rows: list[dict], boards, variants) -> None:
    ok = {(r["board"], r["variant"], r["seed"]): r for r in rows if r["status"] == "ok"}
    base = variants[0][0]
    print(f"\nunrouted per board (lower is better), baseline {base!r}\n")
    print(f"{'board':14} {'variant':14} {'n':>3} {'mean':>6} {'sd':>5} {'min':>4} {'max':>4}"
          f" {'secs':>6}   vs baseline, seed by seed")
    for bname, _, _ in boards:
        for vname, _, _ in variants:
            runs = sorted((k[2], r) for k, r in ok.items() if k[:2] == (bname, vname))
            if not runs:
                print(f"{bname:14} {vname:14}   no finished runs")
                continue
            xs = [r["unrouted"] for _, r in runs]
            m, sd = mean_sd(xs)
            t, _ = mean_sd([r["secs"] for _, r in runs])
            line = (f"{bname:14} {vname:14} {len(xs):>3} {m:>6.1f} {sd:>5.1f} {min(xs):>4}"
                    f" {max(xs):>4} {t:>6.0f}")
            if vname != base:
                diffs = [r["unrouted"] - ok[(bname, base, s)]["unrouted"]
                         for s, r in runs if (bname, base, s) in ok]
                if diffs:
                    dm, dsd = mean_sd(diffs)
                    se = dsd / math.sqrt(len(diffs)) if len(diffs) > 1 else float("inf")
                    better = sum(d < 0 for d in diffs)
                    worse = sum(d > 0 for d in diffs)
                    # a difference inside two standard errors is not a finding
                    verdict = ("better" if dm < 0 else "worse") if abs(dm) > 2 * se else "no clear change"
                    line += (f"   {dm:+.1f} ± {se:.1f}  ({better} better, {worse} worse,"
                             f" {len(diffs) - better - worse} same)  {verdict}")
            print(line)
    failed = [r for r in rows if r["status"] != "ok"]
    for r in failed:
        print(f"FAILED {r['board']} {r['variant']} seed {r['seed']}: {r['status']} {r['tail']}")
 def main(argv: list[str] | None = None) -> int:
    ap = argparse.ArgumentParser(description=__doc__.split("\n\n")[0])
    ap.add_argument("boards", type=Path, help="board list: name, DSN path, flags")
    ap.add_argument("-v", "--variant", action="append", required=True,
                    help="NAME=FLAGS or NAME@SRC=FLAGS; the first is the baseline")
    ap.add_argument("--seeds", type=int, default=6, help="orders per board and variant")
    ap.add_argument("--first-seed", type=int, default=0)
    ap.add_argument("--jobs", type=int, default=4, help="runs at once")
    ap.add_argument("--timeout", type=float, default=1800, help="seconds per run")
    ap.add_argument("--out", type=Path, required=True, help="JSON lines, appended")
    ap.add_argument("--report-only", action="store_true", help="summarise --out, run nothing")
    args = ap.parse_args(argv)
    boards = parse_boards(args.boards)
    variants = [parse_variant(v) for v in args.variant]
    if len({v[0] for v in variants}) != len(variants):
        raise SystemExit("variant names must differ")
    seeds = range(args.first_seed, args.first_seed + args.seeds)
    rows: list[dict] = []
    if args.out.exists():
        rows = [json.loads(line) for line in args.out.read_text().splitlines() if line.strip()]
    done = {(r["board"], r["variant"], r["seed"]) for r in rows if r["status"] == "ok"}
    todo = [(b, v, s) for b in boards for v in variants for s in seeds
            if (b[0], v[0], s) not in done]
    if not args.report_only and todo:
        args.out.parent.mkdir(parents=True, exist_ok=True)
        print(f"{len(todo)} runs, {args.jobs} at a time", file=sys.stderr)
        # retried runs replace their earlier failure
        rows = [r for r in rows if (r["board"], r["variant"], r["seed"]) in done]
        with ThreadPoolExecutor(args.jobs) as pool, args.out.open("w") as out:
            for r in rows:
                out.write(json.dumps(r) + "\n")
            futures = [pool.submit(run_one, b, v, s, args.timeout) for b, v, s in todo]
            for n, fut in enumerate(as_completed(futures), 1):
                r = fut.result()
                rows.append(r)
                out.write(json.dumps(r) + "\n")
                out.flush()
                print(f"[{n}/{len(todo)}] {r['board']} {r['variant']} seed {r['seed']}:"
                      f" {r['status']} unrouted {r['unrouted']} ({r['secs']}s,"
                      f" {r['rss_mb']} MB)", file=sys.stderr)
    wanted = {(b[0], v[0], s) for b in boards for v in variants for s in seeds}
    rows = [r for r in rows if (r["board"], r["variant"], r["seed"]) in wanted]
    report(rows, boards, variants)
    return 1 if any(r["status"] != "ok" for r in rows) or len(rows) < len(wanted) else 0
 if __name__ == "__main__":
    raise SystemExit(main())
@@ -1,296 +0,0 @@
 """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,
    _rule_clearance_dsn,
    _rule_width_dsn,
    _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,
 ) -> 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,
    )
    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)
    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("--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)
    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())
@@ -70,27 +70,6 @@ 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)]
@@ -23,7 +23,6 @@ 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
@@ -32,16 +31,13 @@ from freeroute.geometry.polygon_shape import PolygonShape
 from .board import BasicBoard
 from .clearance import ClearanceMatrix
-from .items import ConductionArea, ObstacleArea, Pin, Trace, Via
+from .items import ConductionArea, ObstacleArea, Pin
 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`."""
@@ -60,7 +56,6 @@ 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
@@ -338,20 +333,10 @@ 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.
@@ -476,52 +461,6 @@ 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)}
@@ -76,11 +76,6 @@ 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
@@ -114,13 +109,6 @@ 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
    #: placed by the router's fan-out, not on the board yet: written out
    generated: bool = False
@dataclass
@@ -134,8 +122,6 @@ class Trace(Item):
    layer: int = 0
    half_width: int = 0
    corners: list[IntPoint] = field(default_factory=list)
    #: placed by the router's fan-out, not on the board yet: written out
    generated: bool = False
    def is_empty(self) -> bool:
        return len(self.corners) < 2
@@ -50,8 +50,6 @@ 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
@@ -131,8 +129,6 @@ 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):
@@ -140,10 +136,6 @@ 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
@@ -151,17 +143,6 @@ class ShapeSearchTree:
                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:
@@ -197,13 +178,6 @@ 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
@@ -19,7 +19,6 @@ import argparse
 import sys
 from freeroute.dsn.reader import parse_dsn
 from freeroute.route.orders import best_of_orders, promote_failures
 from freeroute.route.pipeline import (
    build_exact_routing_result,
    build_rooms_routing_result,
@@ -30,11 +29,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", "promote", "access", "rollback", "fanout"}),
+    "grid": frozenset({"rip_up", "max_passes"}),
-    "exact": frozenset(
+    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes"}),
        {"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access",
         "rollback", "fanout"}
    ),
    "room": frozenset({"shove", "pack"}),
 }
@@ -45,12 +41,6 @@ _FLAG_NAMES = {
    "diagonal": "--diagonal",
    "rip_up": "--no-rip-up",
    "max_passes": "-mp/--max-passes",
    "seed": "--seed",
    "orders": "--orders",
    "promote": "--promote-failures",
    "access": "--access-cost",
    "rollback": "--no-rollback",
    "fanout": "--fanout",
 }
@@ -136,6 +126,14 @@ def build_parser() -> argparse.ArgumentParser:
        help="exact engine: weighted A* (W >= 1); larger is faster, routes at most "
        "W times the shortest length (default 1)",
    )
    parser.add_argument(
        "--history-cost",
        type=float,
        default=None,
        metavar="H",
        help="exact engine: extra cost added to a cell each time connections fight over it "
        "(PathFinder's history term), so later routes avoid hotspots; default 0 (off)",
    )
    parser.add_argument(
        "--edge-clearance",
        type=float,
@@ -143,72 +141,6 @@ def build_parser() -> argparse.ArgumentParser:
        help="copper to board-edge clearance in mm, e.g. KiCad's min_copper_edge_clearance "
        "(the DSN does not carry it); default 0: copper only has to stay inside the outline",
    )
    parser.add_argument(
        "--seed",
        type=int,
        metavar="N",
        help="grid and exact engines: shuffle the order connections are routed in; "
        "the same seed gives the same result (default: fewer-pin nets first)",
    )
    parser.add_argument(
        "--orders",
        type=int,
        metavar="N",
        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(
        "--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(
        "--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(
        "--fanout",
        nargs="?",
        const="all",
        choices=["all", "supply"],
        help="grid and exact engines: before routing, give every fine-pitch pin a stub "
        "outward past its pad row (and a via to its plane, for a plane net), committed "
        "as copper so later routes cannot wall it in; --fanout supply: plane pins only",
    )
    parser.add_argument(
        "--fanout-min-pins",
        type=int,
        default=32,
        metavar="N",
        help="with --fanout: fan out only packages with at least N fine-pitch pins (default 32)",
    )
    parser.add_argument(
        "--jobs",
        type=int,
        metavar="J",
        help="processes for --orders (default: one per order, up to the CPU count)",
    )
    return parser
@@ -228,12 +160,6 @@ def main(argv: list[str] | None = None) -> int:
            ("diagonal", args.diagonal),
            ("rip_up", args.no_rip_up),
            ("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),
            ("rollback", not args.rollback),
            ("fanout", bool(args.fanout)),
        )
        if asked
    ]
@@ -255,64 +181,30 @@ def main(argv: list[str] | None = None) -> int:
    rip_up = not args.no_rip_up
    max_passes = args.max_passes if args.max_passes is not None else 10
    if args.orders is not None and args.orders < 1:
        parser.error("--orders must be at least 1")
    if args.engine == "exact":
-        options = {
+        result = build_exact_routing_result(
-            "layers": layers,
+            dsn,
-            "shove": args.shove,
+            layers=layers,
-            "diagonal": args.diagonal,
+            shove=args.shove,
-            "rip_up": rip_up,
+            diagonal=args.diagonal,
-            "max_passes": max_passes,
+            rip_up=rip_up,
-            "edge_clearance_mm": args.edge_clearance,
+            max_passes=max_passes,
-            "resolution": 2 if args.grid_resolution is None else args.grid_resolution,
+            edge_clearance_mm=args.edge_clearance,
-            "heuristic_weight": args.heuristic_weight,
+            resolution=2 if args.grid_resolution is None else args.grid_resolution,
-            "access_cost": args.access_cost or 0.0,
+            heuristic_weight=args.heuristic_weight,
-            "hole_to_hole_mm": args.hole_to_hole,
+            history_cost=0.0 if args.history_cost is None else args.history_cost,
-            "fanout": args.fanout or False,
+        )
-            "fanout_min_pins": args.fanout_min_pins,
+    elif args.engine == "room":
            "rollback": args.rollback,
        }
    elif args.engine == "grid":
        options = {
            "layers": layers,
            "rip_up": rip_up,
            "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,
            "hole_to_hole_mm": args.hole_to_hole,
            "fanout": args.fanout or False,
            "fanout_min_pins": args.fanout_min_pins,
            "rollback": args.rollback,
        }
    if args.engine == "room":
        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
        )
        counts = ", ".join(f"{'default' if s is None else s}: {m}" for s, (m, _z) in tried)
        print(
            f"freeroute: tried {len(tried)} orders, kept "
            f"{'the default order' if kept is None else f'--seed {kept}'} (unrouted {counts})",
            file=sys.stderr,
        )
    elif args.engine == "exact":
        result = build_exact_routing_result(dsn, seed=args.seed, **options)
    else:
-        result = build_routing_result(dsn, seed=args.seed, **options)
+        result = build_routing_result(
            dsn, layers=layers, rip_up=rip_up, max_passes=max_passes,
            edge_clearance_mm=args.edge_clearance,
            resolution=1 if args.grid_resolution is None else args.grid_resolution,
        )
    ses_text = write_ses(dsn, result)
    missing = [u for u in result.unrouted if not u[3]]
@@ -322,14 +214,6 @@ 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:",
@@ -27,8 +27,6 @@ __all__ = [
    "NetPin",
    "Net",
    "NetClass",
    "WiringVia",
    "WiringWire",
    "Keepout",
    "DsnBoard",
 ]
@@ -188,26 +186,6 @@ 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."""
@@ -219,9 +197,6 @@ 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``)
@@ -9,8 +9,6 @@ tolerant ``skip_scope`` behaviour.
 from __future__ import annotations
 import re
 from .model import (
    ClearanceRule,
    ComponentPlace,
@@ -27,8 +25,6 @@ from .model import (
    Pin,
    Resolution,
    WidthRule,
    WiringVia,
    WiringWire,
 )
 from .sexp import SExp, parse
 from .shapes import Shape, read_area, read_shape
@@ -485,26 +481,12 @@ 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, _declared_quote(text))
+    top = parse(text)
    if top.head != "pcb":
        raise DsnParseError(
            f"not a Specctra DSN file: expected top-level '(pcb ...)', got '({top.head} ...)'"
@@ -533,45 +515,11 @@ def parse_dsn(text: str) -> DsnBoard:
            _read_placement(it, board)
        elif head == "network":
            _read_network(it, board)
-        elif head == "wiring":
+        # `wiring` and unknown scopes are intentionally ignored for now.
            _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
@@ -31,7 +31,7 @@ from dataclasses import dataclass, field
 import math
 from freeroute.board.board import BasicBoard
-from freeroute.board.items import Pin, Via
+from freeroute.board.items import Pin
 from freeroute.board.search_tree import ShapeSearchTree, TreeShape
 from freeroute.geometry import (
    IntBox,
@@ -42,7 +42,6 @@ from freeroute.geometry import (
    segment_octagon,
    shove_segment,
 )
 from freeroute.geometry.polyline import corner_box
 from .grid_router import RouteResult, route_board
@@ -95,13 +94,7 @@ def route_board_exact(
    edge_clearance: int | None = None,
    resolution: int = 1,
    heuristic_weight: float = 1.0,
-    seed: int | None = None,
+    history_cost: float = 0.0,
    route_first: frozenset | None = None,
    access_cost: float = 0.0,
    rollback: 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.
@@ -130,13 +123,7 @@ def route_board_exact(
        edge_clearance=edge_clearance,
        resolution=resolution,
        heuristic_weight=heuristic_weight,
-        seed=seed,
+        history_cost=history_cost,
        route_first=route_first,
        access_cost=access_cost,
        rollback=rollback,
        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
@@ -155,10 +142,6 @@ def route_board_exact(
        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
@@ -170,54 +153,35 @@ def route_board_exact(
            box = tile.bounding_box()
            if not box.is_empty():
                tree.insert(
-                    TreeShape(
+                    TreeShape(next(owner), -1, frozenset({obstacle.layer}), box, blocks=blocks)
                        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)
    # 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)
    for (net_no, wires, vias), ends in sorted(
        zip(result.connections, ends_list, strict=False), key=lambda c: c[0][0]
    ):
-        wire_half = net_half.get(net_no, half_width)
+        boxes = _copper_boxes(wires, vias, half_width, via_layers, via_half)
-        boxes = _copper_boxes(wires, vias, wire_half, via_layers, via_half)
+        wire_count = len(_copper_boxes(wires, [], half_width, via_layers, via_half))
        wire_count = len(_copper_boxes(wires, [], wire_half, via_layers, via_half))
        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 _end_in_rule_area(tree, wires, wire_half) or (
+        ) or (outline is not None and not all(outline.box_clear(b, edge) for b, _ in boxes)):
            outline is not None and not all(outline.box_clear(b, edge) for b, _ in boxes)
        ):
            rejected.append((net_no, *ends))
            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)
-        # connections of one net that end on the same plane cell share its
+        acc.vias.extend(vias)
        # 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 in boxes:
            oid = next(owner)
            tree.insert(TreeShape(oid, net_no, box_layers, box, routed=True))
@@ -267,17 +231,6 @@ 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)
@@ -635,26 +588,6 @@ 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_boxes(wires, vias, half_width, via_layers, via_half=None):
    via_half = via_half or half_width
    boxes: list[tuple[IntBox, frozenset[int]]] = []
@@ -1,229 +0,0 @@
 """Fan out fine-pitch pins before routing: commit each pin's way out as copper.
 On a dense board the pins of a fine-pitch package get walled in: their own
 neighbours' pads on either side, and other nets' copper that got there first
 across the only way out. Reserving the way out did not help (the reserved
 cells still had to be routed, and lost to congestion there); committing it
 does, which is what a person does by hand.
 Each fine-pitch pin of a perimeter package (QFP, QFN, LGA: pads on the edge,
 none inside) gets a straight stub outward, perpendicular to its side of the
 package, just past its pad row. A pin whose net has an inner plane also gets
 a via at the stub's end, staggered between neighbouring pins so their holes
 keep their spacing, and so reaches the plane with nothing left to route.
 Every stub and via is checked exactly against pads, keepouts, the board edge,
 copper already on the board and earlier fan-out, and left out where it would
 not fit. The result goes on the board as fixed copper of its net (marked
 ``generated``), so the router starts from the stub's end or the via, and the
 session writes it out with the routes.
 """
 from __future__ import annotations
 from dataclasses import dataclass
 import math
 from freeroute.board.board import BasicBoard
 from freeroute.board.items import Pin, Trace, Via
 from freeroute.geometry import IntBox, IntPoint
 from freeroute.geometry.polyline import Polyline, PolylineShape, corner_box
 # a package is fanned out when it has this many pins and they are this close
 _MIN_PINS = 8
 _FINE_PITCH_FACTOR = 1.2  # neighbour centres within this many (trace + 2 clearance)
@dataclass
 class FanoutRules:
    trace_width: int
    clearance: int
    via_half: int
    via_drill: int
    hole_to_hole: int
    edge_clearance: int
    signal_layers: list[int]
    via_padstack: str
    #: smallest package fanned out (a big dense part is where pins get walled in)
    min_pins: int = 32
    #: fan out plane pins only (a stub and a via each), as a person would first
    supply_only: bool = False
 def plan_fanout(board: BasicBoard, rules: FanoutRules) -> list:
    """The stubs and vias to put on the board before routing."""
    half = max(rules.trace_width // 2, 1)
    # a net may have several plane zones (a main plane and an island)
    planes: dict[int, list] = {}
    for z in board.get_conduction_areas():
        if z.net_nos and not board.layer_structure.arr[z.layer].is_signal:
            planes.setdefault(z.net_nos[0], []).append(z)
    # copper pours on the routing layers, by net: a pad inside one is joined
    # by the fill, and a stub there would take the room its thermal spokes need
    pours: dict[int, list] = {}
    for z in board.get_conduction_areas():
        if z.net_nos and board.layer_structure.arr[z.layer].is_signal:
            pours.setdefault(z.net_nos[0], []).append(z)
    placed = _Placed(board, rules)
    by_net: dict[int, list[Pin]] = {}
    for pin in board.get_pins():
        for n in pin.net_nos:
            by_net.setdefault(n, []).append(pin)
    items: list = []
    pitch = 2 * rules.via_half + rules.hole_to_hole
    for pins in _packages(board, rules).values():
        centre = IntPoint(
            sum(p.location.x for p in pins) // len(pins), sum(p.location.y for p in pins) // len(pins)
        )
        for k, pin in enumerate(sorted(pins, key=lambda p: (p.location.x, p.location.y))):
            net = pin.net_nos[0] if pin.net_nos else None
            if net is None:
                continue
            layer = next(layer for layer in pin.layers if layer in rules.signal_layers)
            if any(z.layer == layer and z.polygon is not None and z.polygon.contains(pin.location)
                   for z in pours.get(net, [])):
                continue  # the pour joins it
            direction = _outward(pin.location, centre)
            reach = _pad_reach(pin, direction) + rules.clearance + half + rules.trace_width
            end = _step(pin.location, direction, reach)
            plane = planes.get(net)
            partners = [q for q in by_net.get(net, []) if q is not pin]
            # a signal whose other pins are all on other layers has to change
            # layer somewhere: do it at the stub's end, away from the pads
            elsewhere = bool(partners) and all(layer not in q.layers for q in partners)
            if plane is None and (rules.supply_only or not elsewhere):
                if not rules.supply_only and placed.stub_fits(pin.location, end, layer, net, half):
                    items.append(placed.add_stub(pin.location, end, layer, net, half))
                continue
            # stagger the via of every other pin along the side outward
            options = [reach + rules.via_half + rules.clearance + (k % 2) * pitch,
                       reach + rules.via_half + rules.clearance + ((k + 1) % 2) * pitch]
            for d in options:
                at = _step(pin.location, direction, d)
                if plane is not None and not any(
                    z.polygon is not None and z.polygon.contains(at) for z in plane
                ):
                    continue
                if placed.stub_fits(pin.location, at, layer, net, half) and placed.via_fits(at, net):
                    items.append(placed.add_stub(pin.location, at, layer, net, half))
                    items.append(placed.add_via(at, net))
                    break
    return items
 def _packages(board: BasicBoard, rules: FanoutRules) -> dict[str, list[Pin]]:
    """Fine-pitch perimeter packages: many single-layer pins, close together."""
    by_ref: dict[str, list[Pin]] = {}
    for pin in board.get_pins():
        if pin.shape is None or not pin.component_ref:
            continue
        on = [layer for layer in pin.layers if layer in rules.signal_layers]
        if len(on) != 1:
            continue  # through-hole pins change layer for free
        by_ref.setdefault(pin.component_ref, []).append(pin)
    fine = _FINE_PITCH_FACTOR * (rules.trace_width + 2 * rules.clearance)
    out = {}
    for ref, pins in by_ref.items():
        if len(pins) < max(rules.min_pins, _MIN_PINS):
            continue
        close = sum(
            1 for p in pins
            if min(math.hypot(p.location.x - q.location.x, p.location.y - q.location.y)
                   for q in pins if q is not p) < fine * 2
        )
        if close >= len(pins) // 2:
            out[ref] = pins
    return out
 def _outward(point: IntPoint, centre: IntPoint) -> tuple[int, int]:
    """Away from the package centre, along the nearer axis (its side's normal)."""
    dx, dy = point.x - centre.x, point.y - centre.y
    if abs(dx) >= abs(dy):
        return (1 if dx >= 0 else -1, 0)
    return (0, 1 if dy >= 0 else -1)
 def _pad_reach(pin: Pin, direction: tuple[int, int]) -> int:
    """How far the pad reaches from its centre in ``direction``."""
    box = pin.shape.bounding_box()
    if direction[0] > 0:
        return box.ur.x - pin.location.x
    if direction[0] < 0:
        return pin.location.x - box.ll.x
    if direction[1] > 0:
        return box.ur.y - pin.location.y
    return pin.location.y - box.ll.y
 def _step(point: IntPoint, direction: tuple[int, int], distance: float) -> IntPoint:
    return IntPoint(point.x + round(direction[0] * distance), point.y + round(direction[1] * distance))
 class _Placed:
    """Copper a fan-out stub or via has to clear, growing as fan-out is placed."""
    def __init__(self, board: BasicBoard, rules: FanoutRules) -> None:
        self.board, self.rules = board, rules
        self.copper: list[tuple[IntBox, frozenset[int], int]] = []  # box, layers, net
        for pin in board.get_pins():
            if pin.shape is not None:
                net = pin.net_nos[0] if pin.net_nos else -1
                self.copper.append((pin.shape.bounding_box(), frozenset(pin.layers), net))
        for net, layers, box in board.get_fixed_copper():
            self.copper.append((box, layers, net))
        self.keepouts = [
            (tile.bounding_box(), o.layer, o.blocks_wires, o.blocks_vias, o.clearance)
            for o in board.get_obstacle_areas() for tile in o.tiles
        ]
        self.holes: list[tuple[IntPoint, int]] = []  # centre, radius
        for item in board.get_items():
            if isinstance(item, Via) and item.fixed:
                self.holes.append((item.location, (item.drill or rules.via_drill) // 2))
        for pin in board.get_pins():
            if pin.shape is not None and sum(1 for layer in pin.layers if layer in rules.signal_layers) > 1:
                b = pin.shape.bounding_box()
                self.holes.append((pin.location, min(b.ur.x - b.ll.x, b.ur.y - b.ll.y) // 2))
    def _clear(self, box: IntBox, layers: frozenset[int], net: int, kind: str) -> bool:
        grown = box.offset(self.rules.clearance)
        for other, other_layers, other_net in self.copper:
            if other_net != net and layers & other_layers and other.overlaps(grown):
                return False
        for kbox, klayer, wires, vias, needs in self.keepouts:
            if klayer not in layers or not (wires if kind == "wire" else vias):
                continue
            if kbox.overlaps(grown if needs else box):
                return False
        outline = self.board.outline
        return outline is None or outline.box_clear(box, self.rules.edge_clearance)
    def stub_fits(self, a: IntPoint, b: IntPoint, layer: int, net: int, half: int) -> bool:
        boxes = list(PolylineShape(Polyline([a, b]), half).tiles()) + [corner_box(b, half)]
        return all(self._clear(box, frozenset({layer}), net, "wire") for box in boxes)
    def via_fits(self, at: IntPoint, net: int) -> bool:
        h = self.rules.via_half
        box = IntBox(at.x - h, at.y - h, at.x + h, at.y + h)
        if not self._clear(box, frozenset(self.rules.signal_layers), net, "via"):
            return False
        mine = self.rules.via_drill // 2
        return all(
            math.hypot(c.x - at.x, c.y - at.y) >= mine + r + self.rules.hole_to_hole
            for c, r in self.holes
        )
    def add_stub(self, a: IntPoint, b: IntPoint, layer: int, net: int, half: int) -> Trace:
        for box in list(PolylineShape(Polyline([a, b]), half).tiles()) + [corner_box(b, half)]:
            self.copper.append((box, frozenset({layer}), net))
        return Trace(net_nos=[net], fixed=True, layer=layer, half_width=half, corners=[a, b],
                     generated=True)
    def add_via(self, at: IntPoint, net: int) -> Via:
        h = self.rules.via_half
        box = IntBox(at.x - h, at.y - h, at.x + h, at.y + h)
        layers = list(self.rules.signal_layers)
        self.copper.append((box, frozenset(layers), net))
        self.holes.append((at, self.rules.via_drill // 2))
        return Via(net_nos=[net], fixed=True, padstack_name=self.rules.via_padstack,
                   location=at, layers=layers, shape=box, drill=self.rules.via_drill,
                   generated=True)
@@ -1,98 +0,0 @@
 """Route one board in several connection orders at once and keep the best.
 Which connection routes first moves the result on a crowded board by several
 connections either way, and no single order wins everywhere. Routing a few
 orders in parallel processes and keeping the one that leaves the fewest
 connections unrouted costs cores, not wall time.
 Without a seed the candidates are the default order and seeds 0 to N-2, so the
 result is never worse than a plain run. With seed S they are seeds S to S+N-1.
 Ties go to the earlier candidate, so the choice is deterministic.
 """
 from __future__ import annotations
 from concurrent.futures import ProcessPoolExecutor
 import os
 from freeroute.dsn import parse_dsn
 from freeroute.ses import RoutingResult
 from .pipeline import build_exact_routing_result, build_routing_result
 def candidate_seeds(orders: int, seed: int | None = None) -> list[int | None]:
    orders = max(int(orders), 1)
    if seed is None:
        return [None, *range(orders - 1)]
    return list(range(seed, seed + orders))
 def score(result: RoutingResult) -> tuple[int, int]:
    """Connections left open, then those left to a zone fill: lower is better."""
    missing = sum(1 for u in result.unrouted if not u[3])
    return missing, len(result.unrouted) - missing
 def route_once(dsn_text: str, engine: str, options: dict, seed: int | None) -> RoutingResult:
    dsn = parse_dsn(dsn_text)
    if engine == "exact":
        return build_exact_routing_result(dsn, seed=seed, **options)
    if engine == "grid":
        return build_routing_result(dsn, seed=seed, **options)
    raise ValueError(f"routing orders are not supported by the {engine} engine")
 def best_of_orders(
    dsn_text: str,
    engine: str,
    options: dict,
    *,
    orders: int,
    seed: int | None = None,
    jobs: int | None = None,
 ) -> tuple[RoutingResult, int | None, list[tuple[int | None, tuple[int, int]]]]:
    """Route ``orders`` orders and return the best result, the seed that made
    it (None for the default order), and every candidate's seed and score."""
    seeds = candidate_seeds(orders, seed)
    if len(seeds) == 1:
        result = route_once(dsn_text, engine, options, seeds[0])
        return result, seeds[0], [(seeds[0], score(result))]
    jobs = max(1, min(jobs or os.cpu_count() or 1, len(seeds)))
    with ProcessPoolExecutor(jobs) as pool:
        futures = [pool.submit(route_once, dsn_text, engine, options, s) for s in seeds]
        results = [f.result() for f in futures]
    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
@@ -12,8 +12,6 @@ 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
@@ -36,25 +34,6 @@ 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
@@ -74,56 +53,6 @@ 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 _place_fanout(
    board, dsn, scale, layers, width, clearance, edge, hole_to_hole_mm, mode=True, min_pins=32
 ) -> None:
    """Put the fan-out's stubs and vias on the board, before routing."""
    from .fanout import FanoutRules, plan_fanout
    via_half = _via_half_board(dsn, scale) or max(width // 2, 1)
    rules = FanoutRules(
        trace_width=width,
        clearance=clearance,
        via_half=via_half,
        via_drill=_via_drill_board(dsn, scale) or 2 * via_half,
        hole_to_hole=_mm_to_board(dsn, scale, hole_to_hole_mm) or 0,
        edge_clearance=edge or 0,
        signal_layers=layers or [i for i, layer in enumerate(dsn.layers) if layer.is_signal],
        via_padstack=_via_padstack(dsn),
        min_pins=min_pins,
        supply_only=mode == "supply",
    )
    for item in plan_fanout(board, rules):
        board.insert(item)
 def _add_generated(result, board) -> None:
    """The fan-out's copper goes into the session with the routes."""
    from freeroute.board.items import Trace, Via
    for item in board.get_items():
        if not getattr(item, "generated", False) or not item.net_nos:
            continue
        if isinstance(item, Trace):
            result.add_wire(item.net_nos[0], item.layer, list(item.corners))
        elif isinstance(item, Via):
            result.add_via(item.net_nos[0], item.location)
 def _via_half_board(dsn: DsnBoard, scale: int) -> int | None:
    """Half the via pad's size in board units, from the DSN's via padstack.
@@ -151,13 +80,6 @@ def route_dsn_board(
    layers: list[int] | None = None,
    rip_up: bool = True,
    max_passes: int = 10,
    seed: int | None = None,
    route_first: frozenset | None = None,
    access_cost: float = 0.0,
    hole_to_hole_mm: float = 0.25,
    fanout: bool | str = False,
    fanout_min_pins: int = 32,
    rollback: bool = True,
 ) -> tuple[RouteResult, int, list[str]]:
    """Route a parsed :class:`DsnBoard`; return the board-unit result, the scale,
    and the layer names. ``layers`` restricts routing to those signal-layer
@@ -168,9 +90,6 @@ def route_dsn_board(
    edge_clearance_board = _mm_to_board(dsn, scale, edge_clearance_mm)
    width_board = round(_rule_width_dsn(dsn) * scale)
    clearance_board = round(_rule_clearance_dsn(dsn) * scale)
    if fanout:
        _place_fanout(board, dsn, scale, layers, width_board, clearance_board,
                      edge_clearance_board, hole_to_hole_mm, fanout, fanout_min_pins)
    result = route_board(
        board,
        resolution=resolution,
@@ -181,15 +100,7 @@ def route_dsn_board(
        layers=layers,
        rip_up=rip_up,
        max_passes=max_passes,
        seed=seed,
        route_first=route_first,
        access_cost=access_cost,
        rollback=rollback,
        net_widths=_net_widths_board(dsn, scale),
        via_drill=_via_drill_board(dsn, scale),
        hole_to_hole=_mm_to_board(dsn, scale, hole_to_hole_mm) or 0,
    )
    _add_generated(result, board)
    return result, scale, [layer.name for layer in dsn.layers]
@@ -203,9 +114,6 @@ 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] = []
@@ -213,7 +121,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=net_width, coords=coords))
+                result.add_wire(name, RoutedWire(layer=layer_name, width=width_dsn, coords=coords))
    for net_no, locations in route.vias.items():
        name = numbers_to_names.get(net_no, str(net_no))
        for loc in locations:
@@ -221,9 +129,6 @@ 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
@@ -235,24 +140,11 @@ def build_routing_result(
    rip_up: bool = True,
    max_passes: int = 10,
    edge_clearance_mm: float | None = None,
    seed: int | None = None,
    route_first: frozenset | None = None,
    access_cost: float = 0.0,
    hole_to_hole_mm: float = 0.25,
    fanout: bool | str = False,
    fanout_min_pins: int = 32,
    rollback: bool = True,
 ) -> RoutingResult:
    """Route ``dsn`` (grid track) and convert to a DSN-unit RoutingResult."""
    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,
+        edge_clearance_mm=edge_clearance_mm, resolution=resolution,
        route_first=route_first,
        access_cost=access_cost,
        hole_to_hole_mm=hole_to_hole_mm,
        fanout=fanout,
        fanout_min_pins=fanout_min_pins,
        rollback=rollback,
    )
    return _to_routing_result(route, dsn, scale, layer_names)
@@ -262,19 +154,13 @@ def route_dsn_board_exact(
    *,
    resolution: int = 1,
    heuristic_weight: float = 1.0,
    history_cost: float = 0.0,
    edge_clearance_mm: float | None = None,
    layers: list[int] | None = None,
    max_passes: int = 10,
    rip_up: bool = True,
    shove: bool = False,
    diagonal: bool = False,
    seed: int | None = None,
    route_first: frozenset | None = None,
    access_cost: float = 0.0,
    hole_to_hole_mm: float = 0.25,
    fanout: bool | str = False,
    fanout_min_pins: int = 32,
    rollback: bool = True,
 ) -> tuple[ExactRouteResult, int, list[str]]:
    """Route a parsed :class:`DsnBoard` with the exact-geometry (orthogonal,
    DRC-verified) track; return the exact result, the scale, and layer names.
@@ -286,13 +172,11 @@ def route_dsn_board_exact(
    edge_clearance_board = _mm_to_board(dsn, scale, edge_clearance_mm)
    width_board = round(_rule_width_dsn(dsn) * scale)
    clearance_board = round(_rule_clearance_dsn(dsn) * scale)
    if fanout:
        _place_fanout(board, dsn, scale, layers, width_board, clearance_board,
                      edge_clearance_board, hole_to_hole_mm, fanout, fanout_min_pins)
    exact = route_board_exact(
        board,
        resolution=resolution,
        heuristic_weight=heuristic_weight,
        history_cost=history_cost,
        via_half=_via_half_board(dsn, scale),
        edge_clearance=edge_clearance_board,
        trace_width=width_board,
@@ -302,15 +186,7 @@ def route_dsn_board_exact(
        rip_up=rip_up,
        shove=shove,
        diagonal=diagonal,
        seed=seed,
        route_first=route_first,
        access_cost=access_cost,
        rollback=rollback,
        net_widths=_net_widths_board(dsn, scale),
        via_drill=_via_drill_board(dsn, scale),
        hole_to_hole=_mm_to_board(dsn, scale, hole_to_hole_mm) or 0,
    )
    _add_generated(exact.result, board)
    return exact, scale, [layer.name for layer in dsn.layers]
@@ -319,19 +195,13 @@ def build_exact_routing_result(
    *,
    resolution: int = 1,
    heuristic_weight: float = 1.0,
    history_cost: float = 0.0,
    layers: list[int] | None = None,
    shove: bool = False,
    diagonal: bool = False,
    rip_up: bool = True,
    max_passes: int = 10,
    edge_clearance_mm: float | None = None,
    seed: int | None = None,
    route_first: frozenset | None = None,
    access_cost: float = 0.0,
    hole_to_hole_mm: float = 0.25,
    fanout: bool | str = False,
    fanout_min_pins: int = 32,
    rollback: bool = True,
 ) -> RoutingResult:
    """Route ``dsn`` (exact track) and convert to a DSN-unit RoutingResult."""
    exact, scale, layer_names = route_dsn_board_exact(
@@ -344,13 +214,7 @@ def build_exact_routing_result(
        edge_clearance_mm=edge_clearance_mm,
        resolution=resolution,
        heuristic_weight=heuristic_weight,
-        seed=seed,
+        history_cost=history_cost,
        route_first=route_first,
        access_cost=access_cost,
        hole_to_hole_mm=hole_to_hole_mm,
        fanout=fanout,
        fanout_min_pins=fanout_min_pins,
        rollback=rollback,
    )
    return _to_routing_result(exact.result, dsn, scale, layer_names)
@@ -515,10 +515,6 @@ 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
@@ -60,9 +60,6 @@ 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)."""
@@ -254,37 +254,3 @@ 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 != []
@@ -62,37 +62,3 @@ 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)
@@ -156,26 +156,3 @@ 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 == "'"
@@ -1,78 +0,0 @@
 """--fanout: fine-pitch pins get their way out committed before routing."""
 from __future__ import annotations
 from freeroute.board import build_board
 from freeroute.board.items import Trace, Via
 from freeroute.dsn import parse_dsn
 from freeroute.route.fanout import FanoutRules, plan_fanout
 from freeroute.route.pipeline import route_dsn_board_exact
 # a 12-pad package, 3 pads a side at 0.5 mm pitch, over a GND plane on In1;
 # pad 1 (left side, top) is GND, the rest are signals to far connector pads
 _SIDES = {
    "L": [(-2000, y, 0) for y in (500, 0, -500)],
    "R": [(2000, y, 0) for y in (500, 0, -500)],
    "T": [(x, 2000, 90) for x in (-500, 0, 500)],
    "B": [(x, -2000, 90) for x in (-500, 0, 500)],
 }
 _PADS = [p for side in "LRTB" for p in _SIDES[side]]
 def _dsn():
    pins = "\n      ".join(
        f"(pin {'padv' if r else 'padh'} {i + 1} {x} {y})" for i, (x, y, r) in enumerate(_PADS)
    )
    far = " ".join(f"(place C{i} {3000 + 2000 * (i % 5)} {-12000 - 2000 * (i // 5)} front 0)" for i in range(11))
    nets = "(net GND (pins U1-1))\n    " + "\n    ".join(f"(net S{i} (pins U1-{i + 2} C{i}-1))" for i in range(11))
    return f"""(pcb pkg (parser) (resolution um 10) (unit um)
  (structure
    (layer F.Cu (type signal)) (layer In1.Cu (type power)) (layer In2.Cu (type power))
    (layer B.Cu (type signal))
    (boundary (path pcb 0  -15000 15000  25000 15000  25000 -25000  -15000 -25000  -15000 15000))
    (plane GND (polygon In1.Cu 0  -14500 14500  24500 14500  24500 -24500  -14500 -24500  -14500 14500))
    (via "Via[0-3]_450:200_um") (rule (width 150) (clearance 150)))
  (placement (component Q (place U1 0 0 front 0)) (component P {far}))
  (library
    (image Q
      {pins})
    (image P (pin padc 1 0 0))
    (padstack padh (shape (rect F.Cu -400 -125 400 125)) (attach off))
    (padstack padv (shape (rect F.Cu -125 -400 125 400)) (attach off))
    (padstack padc (shape (rect F.Cu -500 -500 500 500)) (attach off))
    (padstack "Via[0-3]_450:200_um" (shape (circle F.Cu 450)) (shape (circle B.Cu 450)) (attach off)))
  (network {nets}))"""
 def _rules(dsn):
    s = dsn.resolution.value
    return FanoutRules(trace_width=150 * s, clearance=150 * s, via_half=225 * s, via_drill=200 * s,
                       hole_to_hole=250 * s, edge_clearance=0, signal_layers=[0, 3],
                       via_padstack="Via[0-3]_450:200_um", min_pins=8)
 def test_every_pin_gets_a_stub_outward_past_its_pad():
    dsn = parse_dsn(_dsn())
    board = build_board(dsn)
    items = plan_fanout(board, _rules(dsn))
    stubs = [i for i in items if isinstance(i, Trace)]
    assert len(stubs) == 12
    for stub in stubs:
        a, b = stub.corners
        pin = next(p for p in board.get_pins() if p.location == a)
        pad = pin.shape.bounding_box()
        # outward: the stub ends further from the package centre, outside its pad
        assert abs(b.x) + abs(b.y) > abs(a.x) + abs(a.y)
        assert not (pad.ll.x <= b.x <= pad.ur.x and pad.ll.y <= b.y <= pad.ur.y)
 def test_a_plane_pin_gets_a_via_and_needs_no_route():
    dsn = parse_dsn(_dsn())
    board = build_board(dsn)
    items = plan_fanout(board, _rules(dsn))
    assert len([i for i in items if isinstance(i, Via)]) == 1
    exact, _scale, _ = route_dsn_board_exact(dsn, resolution=2, fanout=True, fanout_min_pins=8)
    gnd = next(i + 1 for i, n in enumerate(dsn.nets) if n.name == "GND")
    assert not any(f[0] == gnd for f in exact.result.failed)
    assert exact.drc_clean
    assert len(exact.result.vias.get(gnd, [])) == 1  # the fan-out's, written out
@@ -1,108 +0,0 @@
 """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
@@ -1,42 +0,0 @@
 """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}
@@ -1,78 +0,0 @@
 """--orders: route several connection orders and keep the best."""
 from __future__ import annotations
 from pathlib import Path
 from freeroute.cli import main
 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.
 RIPUP = (FIXTURES / "ripup_needed.dsn").read_text()
 GREEDY = {"rip_up": False}
 def test_the_default_order_is_always_a_candidate_without_a_seed():
    assert candidate_seeds(1) == [None]
    assert candidate_seeds(4) == [None, 0, 1, 2]
    assert candidate_seeds(3, seed=7) == [7, 8, 9]
 def test_keeps_the_order_that_leaves_the_fewest_unrouted():
    assert score(route_once(RIPUP, "grid", GREEDY, None)) == (1, 0)
    result, kept, tried = best_of_orders(RIPUP, "grid", GREEDY, orders=3, jobs=2)
    assert kept == 1
    assert score(result) == (0, 0)
    assert tried == [(None, (1, 0)), (0, (1, 0)), (1, (0, 0))]
 def test_ties_go_to_the_earlier_candidate():
    # every order routes this board fully, so the default order is kept
    _, kept, tried = best_of_orders(RIPUP, "grid", {}, orders=3, jobs=3)
    assert kept is None
    assert all(s == (0, 0) for _, s in tried)
 def test_cli_orders_writes_the_best_session(tmp_path, capsys):
    out = tmp_path / "best.ses"
    rc = main([str(FIXTURES / "ripup_needed.dsn"), "--no-rip-up", "--orders", "3", "-do", str(out)])
    assert rc == 0
    err = capsys.readouterr().err
    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
@@ -164,88 +164,3 @@ def test_cli_names_the_connections_it_could_not_route(tmp_path, capsys):
    assert main([str(dsn), "--engine", "exact", "-do", str(tmp_path / "out.ses")]) == 0
    err = capsys.readouterr().err
    assert "1 connection(s) not routed" in err and "N: A-1 to B-1" in err
 # --- inner plane layers (a 4-layer board with a GND plane on In1.Cu) --------
 def _four_layer_dsn():
    return """(pcb four (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 -30000  0 -30000  0 0))
    (plane GND (polygon In1.Cu 0  500 -500  29500 -500  29500 -29500  500 -29500  500 -500))
    (via "Via[0-3]_600:300_um") (rule (width 250) (clearance 150)))
  (placement
    (component S (place G1 5000 -5000 front 0) (place G2 25000 -5000 front 0)
                 (place G3 15000 -25000 front 0) (place A 5000 -15000 front 0) (place B 25000 -15000 front 0))
    (component T (place GT 15000 -15000 front 0)))
  (library
    (image S (pin smd 1 0 0))
    (image T (pin tht 1 0 0))
    (padstack smd (shape (rect F.Cu -300 -300 300 300)) (attach off))
    (padstack tht (shape (circle F.Cu 1000)) (shape (circle B.Cu 1000)) (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 G2-1 G3-1 GT-1)) (net SIG (pins A-1 B-1))))"""
 def test_smd_pads_reach_an_inner_plane_by_their_own_via():
    dsn = parse_dsn(_four_layer_dsn())
    result, scale, names = route_dsn_board_exact(dsn)
    gnd = next(i + 1 for i, n in enumerate(dsn.nets) if n.name == "GND")
    sig = next(i + 1 for i, n in enumerate(dsn.nets) if n.name == "SIG")
    assert len(result.result.vias.get(gnd, [])) == 3  # one per SMD pad, none for the THT pad
    for _layer, pts in result.result.wires.get(gnd, []):  # stubs, not tracks across the board
        length = sum(abs(q.x - p.x) + abs(q.y - p.y) for p, q in zip(pts, pts[1:], strict=False))
        assert length < 3000 * scale  # under 3 mm: a stub to its via
    assert sig in result.result.routed_net_numbers  # signals still route on the outer layers
    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
    board = build_board(parse_dsn(_four_layer_dsn()))
    plane = [z for z in board.get_conduction_areas() if z.name == "GND"]
    gnd_pins = [p for p in board.get_pins() if p.component_ref in ("G1", "G2", "G3", "GT")]
    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"
@@ -1,43 +0,0 @@
 """--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 i in router._via_owner.values())
    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
@@ -264,19 +264,6 @@ def test_larger_board_still_connects_its_multipin_nets():
    assert len(result.routed_net_numbers) == multi_pin == 4
 def test_a_seed_is_repeatable_and_does_change_the_order():
    # The benchmark samples seeds to measure how much a result owes to the
    # routing order. A seed that changed nothing would make every sample the
    # same run and report no spread at all.
    text = (FIXTURES / "kicad_routable.dsn").read_text()
    default = _wire_key(route_dsn_board(parse_dsn(text))[0])
    runs = {s: route_dsn_board(parse_dsn(text), seed=s)[0] for s in range(4)}
    again = route_dsn_board(parse_dsn(text), seed=1)[0]
    assert _wire_key(again) == _wire_key(runs[1])
    assert any(_wire_key(r) != default for r in runs.values())
    assert all(r.unrouted == 0 for r in runs.values())
 # --- oracle parity ----------------------------------------------------------
@@ -1,136 +0,0 @@
 """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)
@@ -154,12 +154,6 @@ def test_cli_supported_combinations_are_accepted(tmp_path):
        "diagonal": ["--diagonal"],
        "rip_up": ["--no-rip-up"],
        "max_passes": ["-mp", "4"],
        "seed": ["--seed", "3"],
        "orders": ["--orders", "2"],
        "promote": ["--promote-failures", "2"],
        "access": ["--access-cost", "5"],
        "rollback": ["--no-rollback"],
        "fanout": ["--fanout"],
    }
    for engine, options in ENGINE_OPTIONS.items():
        for option in options:
@@ -128,7 +128,7 @@ wheels = [
 [[package]]
 name = "freeroute"
-version = "2026.7.14"
+version = "0.1.0"
 source = { editable = "." }
 [package.dev-dependencies]