The previous two commits on this bug fixed two ordering assumptions in
the RETRY loop of _allocateWithTransportCostMatrix(): resetting $inf at
the start of each attempt, and splicing unallocated task indices out of
@requests in descending order (removing a lower index first would shift
the position of any higher index still waiting to be removed).
This is a third instance of the same underlying problem, a few lines
earlier in the loop that compacts the working cost matrix $m before
that splice runs. @unallocated is built by iterating over agents (item
rows), pushing the column index Munkres assigned to each row that
turned out infeasible - and Munkres' row-to-column assignment is a
permutation, not a monotonic function of the row index, so
@unallocated is no more reliably sorted here than it was for the
splice.
That compaction loop scans matrix columns in ascending order and
advances a single pointer into @unallocated, expecting to meet each
entry in that same ascending order. When @unallocated arrives out of
order, the pointer never catches up: columns that should have been
dropped are left in place, and the columns after them are never
shifted left to fill the gap. From that point on, $m no longer lines
up with @requests, which *is* correctly reduced by the splice - so on
the next retry pass a hold's transport cost gets evaluated using a
different hold's matrix row. Depending on the exact misalignment, this
can silently drop a fillable hold from the queue while a genuinely
available item sits unused, or fill a hold via the wrong-cost item.
It didn't show up in the "many holds" regression test added earlier on
this bug, because that test's transport cost matrix is uniform (every
disabled pair costs the same); this defect only surfaces once the
columns competing for a scarce item have distinct costs.
Sort @unallocated once, ascending, and use that copy for the
compaction pass; reverse it for the splice, which needs descending
order.
Test plan:
1. Run the new t/db_dependent/HoldsQueue/RetryAllocationOrdering.t -
it calls _allocateWithTransportCostMatrix() directly with a small
hand-built scarce transport cost matrix and a pinned srand() (the
specific item-to-branch permutation needed to trigger the bug
depends on the shuffle() inside the routine). Reverting just this
patch makes 3 of its 6 subtests fail: the L2 pickup hold is dropped
even though an available item could have filled it.
2. Run t/db_dependent/HoldsQueue/TransportCostOptimizations.t to
confirm no regression in the existing retry-loop coverage.
Signed-off-by: Pedro Amorim <pedro.amorim@openfifth.co.uk>
7a10a59e3d