rsp2k
a6aa1991a1
The router began as a port of FreeRouting and has grown its own engine (negotiated congestion, tree nets, exact checks, axis escapes), and 'freeroute' was one letter from the project it no longer follows. The package, module and command are now rpmroute; the freeroute command stays as an alias, and the RPMROUTE / RPMROUTE_ORACLE_JAVA variables fall back to the old FREEROUTE names. Version 2026.10.07. Routing is unchanged: a PCBench board routes to a byte-identical session either way.
99 lines
4.1 KiB
Python
99 lines
4.1 KiB
Python
"""Tests for the exact ShapeSearchTree spatial index."""
|
|
|
|
from __future__ import annotations
|
|
|
|
from rpmroute.board import ShapeSearchTree, TreeShape
|
|
from rpmroute.geometry import IntBox
|
|
|
|
|
|
def shape(owner, net, layer, box, routed=False):
|
|
return TreeShape(owner, net, frozenset({layer}), box, routed=routed)
|
|
|
|
|
|
def test_insert_and_overlapping_exact():
|
|
tree = ShapeSearchTree(bucket_size=100)
|
|
tree.insert(shape(0, 1, 0, IntBox(0, 0, 50, 50)))
|
|
tree.insert(shape(1, 2, 0, IntBox(200, 200, 250, 250)))
|
|
# a query box overlapping only the first shape
|
|
hit = tree.overlapping(IntBox(40, 40, 60, 60))
|
|
assert [s.owner for s in hit] == [0]
|
|
# a query far from everything
|
|
assert tree.overlapping(IntBox(1000, 1000, 1010, 1010)) == []
|
|
|
|
|
|
def test_touching_boxes_do_not_overlap_but_do_intersect():
|
|
tree = ShapeSearchTree(bucket_size=100)
|
|
tree.insert(shape(0, 1, 0, IntBox(0, 0, 10, 10)))
|
|
# shares the edge x=10 -> intersection is 1-D (found by broad phase)
|
|
assert len(tree.overlapping(IntBox(10, 0, 20, 10))) == 1
|
|
|
|
|
|
def test_remove_owner():
|
|
tree = ShapeSearchTree(bucket_size=100)
|
|
tree.insert(shape(0, 1, 0, IntBox(0, 0, 50, 50)))
|
|
tree.insert(shape(0, 1, 0, IntBox(60, 0, 90, 50))) # same owner, 2 tiles
|
|
tree.insert(shape(1, 2, 0, IntBox(0, 0, 50, 50)))
|
|
tree.remove_owner(0)
|
|
assert all(s.owner == 1 for s in tree.all_shapes())
|
|
assert len(tree.all_shapes()) == 1
|
|
|
|
|
|
def test_clearance_conflict_respects_the_clearance_gap():
|
|
tree = ShapeSearchTree(bucket_size=1000)
|
|
tree.insert(shape(0, 1, 0, IntBox(0, 0, 100, 100), routed=True))
|
|
# a net-2 box exactly `clearance` (20) to the right -> allowed (touching)
|
|
ok = IntBox(120, 0, 200, 100)
|
|
assert not tree.clearance_conflict(ok, net_no=2, layer=0, clearance=20)
|
|
# one unit closer -> conflict
|
|
bad = IntBox(119, 0, 200, 100)
|
|
assert tree.clearance_conflict(bad, net_no=2, layer=0, clearance=20)
|
|
# same net never conflicts
|
|
assert not tree.clearance_conflict(bad, net_no=1, layer=0, clearance=20)
|
|
# different layer never conflicts
|
|
assert not tree.clearance_conflict(bad, net_no=2, layer=1, clearance=20)
|
|
|
|
|
|
def test_has_violation_ignores_static_pad_pairs():
|
|
tree = ShapeSearchTree(bucket_size=1000)
|
|
# two different-net *static* pads closer than clearance -> not a routing DRC
|
|
tree.insert(shape(0, 1, 0, IntBox(0, 0, 10, 10), routed=False))
|
|
tree.insert(shape(1, 2, 0, IntBox(11, 0, 20, 10), routed=False))
|
|
assert tree.has_violation(clearance=20) is None
|
|
# 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)
|