Deterministic truncated path sets: lib-level canonical ReductionPath order for pred path --all (CLI + MCP)

[isPANN]

Background

pred path <S> <T> --all (and the MCP find_path tool) enumerate reduction paths, sort them, truncate to --max-paths (default 20), and return the survivors as both text and JSON. Two independent problems make the returned set non-deterministic across builds:

1. Length-only sort leaves a build-dependent order. find_paths_up_to discovery order depends on inventory/link iteration, so paths of equal length keep an unstable order.

   • MCP problemreductions-cli/src/mcp/tools.rs:303 still does all_paths.sort_by_key(|p| p.len()) then truncate(max_paths) — length alone is not a total order.
   • CLI problemreductions-cli/src/commands/graph.rs (path_all) was given a (len, name+variant signature) tiebreak in Give pred path --all real Big-O output: delete the O(<raw expr>) fallback and JSON text rendering #1079, but as a CLI-local closure, so the MCP sibling stays broken and the ordering definition is duplicated.
   • The pred path --all OOMs/hangs: big_o_normal_form exponentially expands composed overhead expressions #1069 regression test selects "the" path with a third ordering, min_by_key(|p| p.to_string()) — and ReductionPath's Display collapses consecutive same-name variant-cast steps, so it is not even a valid total order over distinct paths.

2. Truncation picks a discovery-dependent subset. Both consumers fetch only find_paths_up_to(..., max_paths + 1), then sort, then truncate. When the total path count exceeds the cap, which paths are fetched — hence which survive — depends on discovery order regardless of how the fetched set is later sorted. Example: KSatisfiability → QUBO has 108 paths; the default cap returns 20, and which 20 is not reproducible across builds.

This undermines the milestone's determinism requirement (docs/design/symbolic-growth-domain.md, Quality requirements: "identical output across platforms … golden files").

Objective

Make the truncated path set returned by pred path --all and the MCP find_path tool reproducible across builds, from one shared definition of canonical path order.

Interface (Input → Output)

• New lib API on ReductionPath (src/rules/graph.rs): a canonical total-order key, e.g. pub fn canonical_key(&self) -> Vec<(&'static str, String)> built from every step's name + its (already-ordered) variant BTreeMap — not Display/type_names (both drop or collapse variants). Optionally impl Ord for ReductionPath on (len, canonical_key).
• path_all (CLI) and the MCP find_path handler both: fetch the complete path set (bounded — see recommendations), sort by (len, canonical_key), then truncate. Delete the CLI-local path_signature closure and the MCP length-only sort_by_key.
• The pred path --all OOMs/hangs: big_o_normal_form exponentially expands composed overhead expressions #1069 test selector switches to canonical_key; regenerate the golden fixture if it changes.

Technical recommendations (non-binding)

• To make the subset (not just its order) reproducible, sort-then-truncate must run over the full candidate set, so fetch all paths before truncating. Guard blowup on hub nodes with the existing bounded enumeration (find_paths_up_to with a high internal ceiling, or find_all_paths with the same MAX_INTERMEDIATE_NODES bound used by find_dominated_rules); document the ceiling and log/note when it is hit rather than silently truncating by discovery order.
• Keep each test < 5 s.

Verification

1. cargo test green with a new test that builds the KSat→QUBO candidate set, sorts+truncates it, then does the same to a reversed copy of the input, and asserts the two truncated results are identical (name+variant sequences equal) — proving order-independence of both the ordering and the surviving subset.
2. grep -n 'sort_by_key(|p| p.len())' problemreductions-cli/src/mcp/tools.rs returns nothing, and grep -n 'canonical_key' src/rules/graph.rs returns the new API — proving the length-only sibling was replaced by the shared key.
3. pred path KSat QUBO --all --json and the MCP find_path tool return the same 20-path set (by name+variant sequence) for the same inputs.

Negative control: the reversed-input test in (1), run against a length-only sort (the current MCP code), fails (different truncated subset) — proving the test detects the non-determinism the canonical key fixes.

Dependencies

Depends on #1079 (introduced the CLI tiebreak this generalizes). Milestone: Symbolic Growth Domain & Pareto Search.