T-BR6H-gs-priority-sorters

Status: open/ready · Impact: medium · Complexity: medium

Goal

Implement soft priority ordering in graph_scheduler::sorters: registered sorters that rank the frontier when it exceeds limit, plus the built-in downstream-propagating sorter D-Q2WR’s pickup order needs. Last task on the v0.1 critical path.

Today

Location	Role today
packages/rust/graph-scheduler/src/sorters.rs	Stubbed by T-ROJC-gs-test-corpus-and-disabled-suites
packages/rust/graph-scheduler/src/schedule.rs	Schedule carrying filters, landed by T-7OJL-gs-eligibility-filters-and-explain
solutions/ontological/lib/model/entities/task/ops/next.ts	Holds the sort chain and the liftSortKeys bubbling this sorter generalizes
docs/planning/decisions/D-Q2WR-task-pickup-order.md	Fixes the lexicographic tuple: priority, then impact, then complexity, then created

Proposed

src/sorters.rs holds the ordering surface.

Item	Shape
Sorter	Trait: name(), compare(&ReadyNode, &ReadyNode) -> Ordering
sorter_fn(name, comparator)	Closure adapter, mirroring filter_fn
WeightRule	SelfOnly / Downstream
priority_weight(graph, rule)	Built-in over attrs.weight, descending
by_key(graph, name, rule, key_fn)	The general form: rank by any Ord key the caller extracts
Schedule::sort(impl Sorter)	Registration; ReadyOptions::order is the call-time equivalent

Both constructors take the graph, and the graph is where WeightRule::Downstream lives: propagation walks descendants, and Sorter::compare(&self, a, b) has no graph to walk. Resolving the propagated key map once at construction — into the owning ByKey<K> the constructors return — keeps the sorter borrowing nothing, so ReadyOptions::order needs no lifetime parameter and a comparison stays a lookup. This is a fourth departure from layered-api.md’s priorityWeight(opts?) sketch, alongside the three T-JVXC-gs-dag-core records.

Sorters are soft. They rank the frontier and the top limit win; a low-ranked node is deferred, never withheld. Ties resolve by add_node insertion order (T-ROJC ratified default R-1), so ordering is deterministic with or without a sorter.

Downstream propagation is max-to-fixed-point, not a sum

WeightRule::Downstream bubbles each descendant’s key to its blockers by taking the maximum over the node’s own key and its transitive descendants’ keys, iterated to a fixed point. A low-impact blocker of high-impact work therefore sorts as high as the work it unblocks, which is the whole point of D-Q2WR’s lift.

This corrects T-ROJC ratified default R-3, which pinned the formula as self + Σ weight(transitive descendants). Two reasons the sum is wrong:

• C-V44L’s first-consumer requirement A is explicit that propagation is over a comparable key, not a scalar weight sum, and that it is always-on rather than an opt-in option. A lexicographic tuple of priority, impact, complexity and created cannot be summed. It can be maximized.
• The single fixture that exercises the rule (F-SORT-down-crit, X at weight 1 blocking Xc at weight 10, against Y at weight 2) cannot tell the two formulas apart: the sum gives X = 11 and the max gives X = 10, and both beat Y = 2. So no fixture is invalidated by the correction, and R-3 was pinned on evidence that did not discriminate.

by_key is the general surface requirement A asks for; priority_weight is the numeric convenience over it. Because the crate is domain-blind, the D-Q2WR tuple itself is supplied by the SDLC adapter in C4 as a key_fn — it is not built in here.

Approach

1. Implement the Sorter trait, sorter_fn, and registration on Schedule, applying the top-limit cut after ordering.
2. Implement by_key with WeightRule::SelfOnly and WeightRule::Downstream, the latter as a max-to-fixed-point propagation over descendants.
3. Implement priority_weight as by_key over attrs.weight.
4. Un-ignore the Layer 5 suite in tests/sorters.rs and make it green.
5. Update T-ROJC’s R-3 row in the fixture corpus to the max formula, since this task is where the contradiction is resolved.

Files to touch

Location	Kind	Change
packages/rust/graph-scheduler/src/sorters.rs	modify	Replace stubs with Sorter, by_key, priority_weight
packages/rust/graph-scheduler/src/schedule.rs	modify	Add sorter registration and the ordered top-limit cut
packages/rust/graph-scheduler/src/lib.rs	modify	Re-export Sorter, sorter_fn, WeightRule, by_key, priority_weight
packages/rust/graph-scheduler/tests/sorters.rs	modify	Remove #[ignore] from the Layer 5 suite

Acceptance criteria

• AC-1: A registered sorter and ReadyOptions::order both rank the frontier, and the top limit nodes are returned.
• AC-2: WeightRule::SelfOnly ranks by the node’s own key.
• AC-3: WeightRule::Downstream propagates by max-to-fixed-point, so a blocker ranks at least as high as anything it unblocks — asserted on a chain more than one edge deep.
• AC-4: by_key accepts any Ord key, demonstrated by a test using a lexicographic tuple rather than a number (first-consumer requirement A).
• AC-5: Ties resolve by insertion order; the same frontier and sorter return the same order on repeated calls.
• AC-6: Every row of T-ROJC’s Layer 5 fixture table passes, with R-3 restated as the max formula, and the suite in tests/sorters.rs has no #[ignore] left.

Out of scope

• Goal-direction (T-8L0G-gs-goal-directed-frontier) and pull (T-0WNK-gs-pull-resolution).
• The D-Q2WR tuple itself. The adapter supplies it as a key_fn in C4; a domain-blind crate does not know what impact or complexity are.
• Anti-starvation or age-based fairness sorters, deferred by D-BPD8.

Dependencies

• T-7OJL-gs-eligibility-filters-and-explain — sorters register on the same Schedule that carries filters, and the batch evaluation order filters depend on is the sorted order.

Depends on

T-7OJL-gs-eligibility-filters-and-explain

---

← Back to Tasks