Module optimize 

Post-parse optimizer — comprehension_forms.md §10.

Required pass upstream of compilation. Takes an AST and produces a canonical, push-down form with these properties (§10.6):

1. Semantic-preserving. Output produces the same dispense sequence (per §9.2).
2. Idempotent. optimize(optimize(C)) == optimize(C).
3. Decidable termination. Each rewrite strictly decreases a metadata-derived measure or leaves the AST unchanged.
4. Bounds-improving. Peak memory never grows.
5. No rejections. Validity is decided on the tree as written, before any rewrite, and every rewrite keeps a valid tree valid.

R-rule catalog

Priority order: R0a → R0b → R1 → R2 → R3 → R4 → R5 → R6 → R7 (§10.10.5).

• R0a — identity elimination (I1–I5): singleton combinators, trivially-true filter, order(Lex, None).
• R0b — associativity flattening (A1, A2): nested union / cartesian collapse to n-ary form.
• R1 — order(Lex) → ORDER_STREAMING: the IR compiler emits ORDER_STREAMING for order(Lex, _) and ORDER_MATERIALIZE otherwise, carrying the input’s metadata.index_addressable. Not an AST rewrite; recorded in the reducibility catalog as an IR-compilation eligibility.
• R2 — order(c, strategy, Some(n)) → indexed_order: metadata-driven. The working set is the selection, sized by strategy_working_set in metadata.rs’s propagation rule, and ORDER_MATERIALIZE selects positions from its input’s shape when it evaluates.
• R3 — order(filter, Lex, None) → filter(order, Lex, None): AST rewrite. Commute when un-truncated.
• R4 — filter(union(...), p) → union(filter(...)): AST rewrite. Distribute filter into each union child, except under a non-Lex order that ranks the filter’s survivors.
• R5 — per-axis filter pushdown: AST rewrite. Consults the predicate analyzer (§10.9) for factorization; when factorization = PerAxis and every per-axis sub-predicate is total over its axis, splits the filter into per-axis filters wrapping each cartesian child, except under a non-Lex order that ranks the filter’s survivors.
• R6 — chained filter folding (F1): AST rewrite. filter(filter(c, p), q) → filter(c, p && q).
• R7 — order chain folding (O1): AST rewrite. order(order(c, s1, None), s2, t) → order(c, s2, t) when s2 selects from its input’s shape.

Module layout

• finding — ReducibilityFinding, Reduction, ComplexityDelta.
• r0a_identity — I1–I5 elimination.
• r0b_flatten — A1, A2 flattening.
• r3_commute — Lex/filter commute.
• r4_distribute — filter over union.
• r5_factorize — per-axis filter pushdown.
• r6_filter_fold — chained filter folding.
• r7_order_fold — order chain folding.

Re-exports

pub use finding::ComplexityDelta;

pub use finding::Ordering as ComplexityOrdering;

pub use finding::ReducibilityFinding;

pub use finding::Reduction;

pub use finding::RuleId;

Modules

finding

ReducibilityFinding and related types — comprehension_forms.md §10.10.2.

r0a_identity

R0a — identity elimination (comprehension_forms.md §4.2 I1–I5).

r0b_flatten

R0b — associativity flattening (comprehension_forms.md §7.1 A1, A2).

r3_commute

R3 — Lex / filter commute (comprehension_forms.md §7.5 N2).

r4_distribute

R4 — filter distributes over union (comprehension_forms.md §7.3 D1).

r5_factorize

R5 — per-axis filter pushdown (comprehension_forms.md §7.3 D2’s optimizer direction, §10.2 R5).

r6_filter_fold

R6 — chained filter folding (comprehension_forms.md §7.2 F1).

r7_order_fold

R7 — order chain folding (comprehension_forms.md §7.4 O1).

Functions

analyze_reducibility

Reducibility analyzer entry — comprehension_forms.md §10.10.

coord_set_for

Convenience: build a CoordSet from a comprehension’s coordinate names and its computed metadata. R5 uses this when invoking the predicate analyzer.

optimize

Top-level optimizer entry. Applies the R-rule catalog to a fixed point and returns the optimized AST.