Background
src/rules/analysis.rs detects redundant reduction rules: a direct edge is redundant if some composite path dominates it on every size field. To compare overheads it carries its own ~200-line polynomial machinery (Monomial, NormalizedPoly, normalize_polynomial, poly_leq, monomial_dominated_by, prepare_expr_for_comparison) — a third, independent expansion-and-compare implementation, which rejects exp/log/sqrt outright and returns Unknown for anything with negative coefficients. The growth domain (#1075) now provides one trusted dominance order used by Big-O rendering (#1078); redundancy analysis should use the same one — one comparison semantics everywhere, and another few hundred lines of bespoke machinery deleted.
Full design (shared overview for this batch): docs/design/symbolic-growth-domain.md, section M3 (former feature F5).
Objective
Rewire compare_overhead to growth dominance and delete the bespoke polynomial machinery from analysis.rs. find_dominated_rules's semantics are unchanged. Close #15's sibling loose end in this file (the canonical_form call already stubbed by #1078).
Interface (Input → Output)
pub fn compare_overhead(primitive: &ReductionOverhead, composite: &ReductionOverhead) -> ComparisonStatus — signature and the ComparisonStatus enum unchanged. Per common field: Dominated iff the composite's growth is dominated-or-equal by the primitive's on every common field (composite ≤ primitive); NotDominated if worse on any field; Unknown only when a field's growth is Growth::Unknown.
- Deleted:
Monomial, NormalizedPoly, normalize_polynomial, poly_leq, monomial_dominated_by, prepare_expr_for_comparison.
Technical recommendations (non-binding)
- Fields present in one overhead but not the other keep today's skip semantics — don't change the common-field logic, only the per-field comparison.
- New capability for free: the one
log-carrying overhead and subtraction-carrying overheads become comparable (the old machinery returned Unknown or errored on them); expect the dominated-rule report to gain decisions, not lose them.
Verification
cargo test analysis green, with unit tests updated to the new semantics; at least one existing Unknown case that involved log or subtraction now yields a decided status (Dominated/NotDominated) — assert the specific pair and status in a test.
- Run the redundancy sanity check (
cargo run --example detect_redundant_rules if present, otherwise the topology-sanity-check redundancy skill path) before and after the change: every rule reported as dominated before is still reported as dominated after (no lost detections); newly decided pairs are listed in the PR description with a one-line justification each.
grep -n "NormalizedPoly\|normalize_polynomial\|poly_leq" src/rules/analysis.rs returns nothing and check 1–2 pass — proving the machinery was replaced, not renamed.
Negative control: a unit test where the composite is strictly worse on one common field (e.g. primitive num_vertices = n^2 vs composite num_vertices = n^3, all other fields equal) asserts NotDominated — a comparison rewire that accidentally inverts the direction or ignores a field fails it.
Dependencies
Depends on #1075 and #1078. Milestone: Symbolic Growth Domain & Pareto Search. When this lands, close #15 with a comment linking docs/design/symbolic-growth-domain.md (the asymptotic-search half of #15 is closed by the Pareto-front issue).
Background
src/rules/analysis.rsdetects redundant reduction rules: a direct edge is redundant if some composite path dominates it on every size field. To compare overheads it carries its own ~200-line polynomial machinery (Monomial,NormalizedPoly,normalize_polynomial,poly_leq,monomial_dominated_by,prepare_expr_for_comparison) — a third, independent expansion-and-compare implementation, which rejectsexp/log/sqrtoutright and returnsUnknownfor anything with negative coefficients. The growth domain (#1075) now provides one trusted dominance order used by Big-O rendering (#1078); redundancy analysis should use the same one — one comparison semantics everywhere, and another few hundred lines of bespoke machinery deleted.Full design (shared overview for this batch):
docs/design/symbolic-growth-domain.md, section M3 (former feature F5).Objective
Rewire
compare_overheadto growth dominance and delete the bespoke polynomial machinery fromanalysis.rs.find_dominated_rules's semantics are unchanged. Close #15's sibling loose end in this file (thecanonical_formcall already stubbed by #1078).Interface (Input → Output)
pub fn compare_overhead(primitive: &ReductionOverhead, composite: &ReductionOverhead) -> ComparisonStatus— signature and theComparisonStatusenum unchanged. Per common field:Dominatediff the composite's growth is dominated-or-equal by the primitive's on every common field (composite ≤ primitive);NotDominatedif worse on any field;Unknownonly when a field's growth isGrowth::Unknown.Monomial,NormalizedPoly,normalize_polynomial,poly_leq,monomial_dominated_by,prepare_expr_for_comparison.Technical recommendations (non-binding)
log-carrying overhead and subtraction-carrying overheads become comparable (the old machinery returnedUnknownor errored on them); expect the dominated-rule report to gain decisions, not lose them.Verification
cargo test analysisgreen, with unit tests updated to the new semantics; at least one existingUnknowncase that involvedlogor subtraction now yields a decided status (Dominated/NotDominated) — assert the specific pair and status in a test.cargo run --example detect_redundant_rulesif present, otherwise thetopology-sanity-check redundancyskill path) before and after the change: every rule reported as dominated before is still reported as dominated after (no lost detections); newly decided pairs are listed in the PR description with a one-line justification each.grep -n "NormalizedPoly\|normalize_polynomial\|poly_leq" src/rules/analysis.rsreturns nothing and check 1–2 pass — proving the machinery was replaced, not renamed.Negative control: a unit test where the composite is strictly worse on one common field (e.g. primitive
num_vertices = n^2vs compositenum_vertices = n^3, all other fields equal) assertsNotDominated— a comparison rewire that accidentally inverts the direction or ignores a field fails it.Dependencies
Depends on #1075 and #1078. Milestone: Symbolic Growth Domain & Pareto Search. When this lands, close #15 with a comment linking
docs/design/symbolic-growth-domain.md(the asymptotic-search half of #15 is closed by the Pareto-front issue).