Skip to content

fix(search): correct backward AOD rectangle source mapping #460

@Jason-Ludmir

Description

@Jason-Ludmir

Summary

Backward-direction bus contexts in BusContext.from_tree were building rectangle source coordinates from canonical bus source indices rather than direction-resolved lane endpoints. This caused valid backward movers to be excluded from pos_to_loc, so rectangle construction failed and moves were split into singleton steps even when a parallel rectangle was legal.

Impact

  • Valid parallel backward moves can be incorrectly split.
  • The planner can emit less parallel move programs than the hardware supports.
  • Tuning scoring weights (e.g. very large w_d) does not fix the behavior because candidate construction is wrong before scoring/ranking can help.

Reproduction

  1. Run uv run python debug/steane_physical_impl.py --gif.
  2. Inspect the move sequence around backward word-bus moves (bus_id=9, Direction.BACKWARD).
  3. Observe rows that are lane-group compatible and collision-free getting emitted as separate move statements.

Root Cause

  • BusContext.from_tree computed candidate source locations from static bus index sets.
  • For backward direction, executable source coordinates differ from forward-side canonical indices.
  • pos_to_loc therefore missed real movers and is_valid_rect(...) returned false on otherwise valid rectangles.

Proposed Fix

  • Build source locations from actual LaneAddress -> get_endpoints(...) resolution, which is direction aware.
  • Track src_to_lane mapping and use it when converting rectangles back to lane sets.
  • Keep collision checks source-based using the resolved lane endpoint mapping.

Validation

  • Add regression test: test_from_tree_backward_word_bus_uses_backward_sources.
  • Confirm search generator tests pass.
  • Confirm the Steane debug program merges the two backward rows into one move layer at logical stage.

Acceptance Criteria

  • Backward bus contexts include real backward source coordinates in pos_to_loc.
  • Compatible backward row movers can be emitted in one rectangle moveset.
  • Regression test covers this scenario and passes.
  • Existing search generator tests remain green.

Metadata

Metadata

Assignees

Labels

area: LaneArea: issues related to bloqade-lanes, static lane definitions, scheduling, and constraints.category: bugCategory: this is a bug or something isn't working as expected.

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions