138 lines
8.4 KiB
Markdown
138 lines
8.4 KiB
Markdown
|
# Testing Plan (Refined)
|
||
|
|
|
||
|
|
This document defines the comprehensive testing strategy for the `inire` auto-router, ensuring analytic correctness and performance.
|
||
|
|
|
||
|
|
## 1. Unit Tests: Geometry & Components (`inire/geometry`)
|
||
|
|
|
||
|
|
### 1.1. Primitives (`primitives.py`)
|
||
|
|
* **Port Snapping:** Verify that `Port(x, y, orientation)` snaps `x` and `y` to the nearest **1nm** grid point.
|
||
|
|
* **Coordinate Transforms:**
|
||
|
|
* Translate a port by `(dx, dy)`.
|
||
|
|
* Rotate a port by `90`, `180`, `270` degrees around an origin.
|
||
|
|
* Verify orientation wrapping (e.g., $270^\circ + 90^\circ \to 0^\circ$).
|
||
|
|
* **Polygon Creation:**
|
||
|
|
* Generate a polygon from a list of points.
|
||
|
|
* Verify bounding box calculation.
|
||
|
|
* **Property-Based Testing (Hypothesis):**
|
||
|
|
* Verify that any `Port` after transformation remains snapped to the **1nm** grid.
|
||
|
|
* Verify that $Rotate(Rotate(Port, 90), -90)$ returns the original `Port` (up to snapping).
|
||
|
|
|
||
|
|
### 1.2. Component Generation (`components.py`)
|
||
|
|
* **Straight Moves:**
|
||
|
|
* Generate a `Straight(length=10.0, width=2.0)` segment.
|
||
|
|
* Verify the end port is exactly `length` away in the correct orientation.
|
||
|
|
* Verify the resulting polygon's dimensions.
|
||
|
|
* **Edge Case:** $L < 1\mu m$ (below search grid). Verify it still generates a valid 1nm segment.
|
||
|
|
* **Bend90:**
|
||
|
|
* Generate a `Bend90(radius=10.0, width=2.0, direction='CW')`.
|
||
|
|
* Verify the end port's orientation is changed by $-90^\circ$.
|
||
|
|
* Verify the end port's position is exactly `(R, -R)` relative to the start (for $0^\circ \to 270^\circ$).
|
||
|
|
* **Grid Snapping:** Verify that if the bend radius results in a non-1µm aligned port, it is snapped to the nearest **1µm** search grid point (with a warning).
|
||
|
|
* **SBend (Small Offset $O < 2R$):**
|
||
|
|
* Generate an `SBend(offset=5.0, radius=10.0, width=2.0)`.
|
||
|
|
* Verify the total length matches the analytical $L = 2\sqrt{O(2R - O/4)}$ (or equivalent arc-based formula).
|
||
|
|
* Verify the tangent continuity at the junction of the two arcs.
|
||
|
|
* **Edge Case:** $O = 2R$. Verify it either generates two 90-degree bends or fails gracefully with a clear error.
|
||
|
|
* Verify it fails/warns if $O > 2R$.
|
||
|
|
|
||
|
|
### 1.3. Geometric Fidelity
|
||
|
|
* **Arc Resolution (Sagitta):**
|
||
|
|
* Verify that `Bend90` and `SBend` polygons are approximated by segments such that the maximum deviation (sagitta) is within a user-defined tolerance (e.g., 10nm).
|
||
|
|
* Test with varying radii to ensure segment count scales appropriately.
|
||
|
|
|
||
|
|
## 2. Unit Tests: Collision & Cost (`inire/geometry/collision` & `router/cost`)
|
||
|
|
|
||
|
|
### 2.1. Collision Engine
|
||
|
|
* **Pre-dilation Logic:**
|
||
|
|
* Verify that an obstacle (polygon) is correctly dilated by $(W_{max} + C)/2$.
|
||
|
|
* **Heterogeneous Widths:** Verify that a path for Net A (width $W_1$) is dilated by $(W_1 + C)/2$, while Net B (width $W_2$) uses $(W_2 + C)/2$.
|
||
|
|
* **Locked Paths:**
|
||
|
|
* Insert an existing path geometry into the "Static Obstacle" R-Tree.
|
||
|
|
* Verify that the router treats it as an unmovable obstacle and avoids it.
|
||
|
|
* **R-Tree Queries:**
|
||
|
|
* Test intersection detection between two overlapping polygons.
|
||
|
|
* Test non-intersection between adjacent but non-overlapping polygons (exactly $C$ distance apart).
|
||
|
|
* **Safety Zone (2nm):**
|
||
|
|
* Create a port exactly on the edge of an obstacle.
|
||
|
|
* Verify that a "Move" starting from this port is NOT flagged for collision if the intersection occurs within **2nm** of the port.
|
||
|
|
* **Self-Intersection:**
|
||
|
|
* Verify that a path consisting of multiple segments is flagged if it loops back on itself.
|
||
|
|
|
||
|
|
### 2.2. Danger Map & Cost Evaluator
|
||
|
|
* **Danger Map Generation:**
|
||
|
|
* Initialize a map for a $100\mu m \times 100\mu m$ area with a single obstacle.
|
||
|
|
* Verify the cost $g_{proximity}$ matches $k/d^2$ for cells near the obstacle.
|
||
|
|
* Verify cost is $0$ for cells beyond the **Safety Threshold**.
|
||
|
|
* **Memory Check:**
|
||
|
|
* Mock a $20mm \times 20mm$ grid and verify memory allocation stays within limits (e.g., `< 2GB` for standard `uint8` resolution).
|
||
|
|
* **Cost Calculation:**
|
||
|
|
* Verify total cost $f(n)$ correctly sums length, bend penalties ($10 \times$ Manhattan), and proximity costs.
|
||
|
|
|
||
|
|
### 2.3. Robustness & Limits
|
||
|
|
* **Design Bounds:**
|
||
|
|
* Test routing at the extreme edges of the $20mm \times 20mm$ coordinate space.
|
||
|
|
* Verify that moves extending outside the design bounds are correctly pruned or flagged.
|
||
|
|
* **Empty/Invalid Inputs:**
|
||
|
|
* Test with an empty netlist.
|
||
|
|
* Test with start and end ports at the exact same location.
|
||
|
|
|
||
|
|
## 3. Integration Tests: Single-Net A* Search (`inire/router/astar`)
|
||
|
|
|
||
|
|
### 3.1. Open Space Scenarios
|
||
|
|
* **Straight Line:** Route from `(0,0,0)` to `(100,0,0)`. Verify it uses only `Straight` moves.
|
||
|
|
* **Simple Turn:** Route from `(0,0,0)` to `(20,20,90)`. Verify it uses a `Bend90` and `Straight` segments.
|
||
|
|
* **Small S-Bend:** Route with an offset of $5\mu m$ and radius $10\mu m$. Verify it uses the `SBend` component.
|
||
|
|
* **Large S-Bend ($O \ge 2R$):** Route with an offset of $50\mu m$ and radius $10\mu m$. Verify it combines two `Bend90`s and a `Straight` segment.
|
||
|
|
|
||
|
|
### 3.2. Obstacle Avoidance (The "Maze" Tests)
|
||
|
|
* **L-Obstacle:** Place an obstacle blocking the direct path. Verify the router goes around it.
|
||
|
|
* **Narrow Channel:** Create two obstacles with a gap slightly wider than $W_i + C$. Verify the router passes through.
|
||
|
|
* **Dead End:** Create a U-shaped obstacle. Verify the search explores alternatives and fails gracefully if no path exists.
|
||
|
|
|
||
|
|
### 3.3. Snapping & Precision
|
||
|
|
* **Snap-to-Target Lookahead:**
|
||
|
|
* Route to a target at `(100.005, 0, 0)` (not on 1µm grid).
|
||
|
|
* Verify the search reaches the vicinity via the 1µm grid and the final segment bridges the **5nm** gap exactly.
|
||
|
|
* **Grid Alignment:**
|
||
|
|
* Start from a port at `(0.5, 0.5, 0)`. Verify it snaps to the 1µm search grid correctly for the first move expansion.
|
||
|
|
|
||
|
|
### 3.4. Failure Modes
|
||
|
|
* **Unreachable Target:** Create a target completely enclosed by obstacles. Verify the search terminates after exploring all options (or hitting the 50,000 node limit) and returns an invalid result.
|
||
|
|
* **Start/End Collision:** Place a port deep inside an obstacle (beyond the 2nm safety zone). Verify the router identifies the immediate collision and fails gracefully.
|
||
|
|
|
||
|
|
## 4. Integration Tests: Multi-Net PathFinder (`inire/router/pathfinder`)
|
||
|
|
|
||
|
|
### 4.1. Congestion Scenarios
|
||
|
|
* **Parallel Paths:** Route two nets that can both take straight paths. Verify no reroutes occur.
|
||
|
|
* **The "Cross" Test:** Two nets must cross paths in 2D.
|
||
|
|
* Since crossings are illegal, verify the second net finds a detour.
|
||
|
|
* Verify the `Negotiated Congestion` loop increases the cost of the shared region.
|
||
|
|
* **Bottleneck:** Force 3 nets through a channel that only fits 2.
|
||
|
|
* Verify the router returns 2 valid paths and 1 "least bad" path (with collisions flagged).
|
||
|
|
* Verify the `is_valid=False` attribute is set for the failing net.
|
||
|
|
|
||
|
|
### 4.2. Determinism & Performance
|
||
|
|
* **Seed Consistency:** Run the same multi-net problem twice with the same seed; verify identical results (pixel-perfect).
|
||
|
|
* **Node Limit Enforcement:** Trigger a complex search that exceeds **50,000 nodes**. Verify it terminates and returns the best-so-far or failure.
|
||
|
|
* **Timeout:** Verify the session-level timeout stops the process for extremely large problems.
|
||
|
|
|
||
|
|
## 5. Benchmarking & Regression
|
||
|
|
* **Standard Benchmark Suite:** A set of 5-10 layouts with varying net counts (1 to 50).
|
||
|
|
* **Metrics to Track:**
|
||
|
|
* Total wire length.
|
||
|
|
* Total number of bends.
|
||
|
|
* Execution time per net.
|
||
|
|
* Success rate (percentage of nets routed without collisions).
|
||
|
|
* **Node Expansion Rate:** Nodes per second.
|
||
|
|
* **Memory Usage:** Peak RSS during 20x20mm routing.
|
||
|
|
* **Fuzz Testing:**
|
||
|
|
* Generate random obstacles and ports within a 1mm x 1mm area.
|
||
|
|
* Verify that the router never crashes.
|
||
|
|
* Verify that every result marked `is_valid=True` is confirmed collision-free by a high-precision (slow) check.
|
||
|
|
|
||
|
|
## 6. Analytic Correctness Guarantees
|
||
|
|
* **Post-Route Validation:**
|
||
|
|
* Implement an independent `validate_path(path, obstacles, clearance)` function using `shapely`'s most precise intersection tests.
|
||
|
|
* Run this on every test result to ensure the `CollisionEngine` (which uses R-Tree for speed) hasn't missed any edge cases.
|
||
|
|
* **Orientation Check:**
|
||
|
|
* Verify that the final port of every path matches the target orientation exactly $\{0, 90, 180, 270\}$.
|