Skip to main content

tenferro_einsum/planning/
tree.rs

1use std::collections::{HashMap, HashSet};
2use std::fmt;
3use std::mem::{size_of, size_of_val};
4
5use omeco::{
6    CodeOptimizer, EinCode as OmecoEinCode, Initializer, NestedEinsum, ScoreFunction, TreeSA,
7};
8
9use crate::cache::{saturating_sum, vec_of_vec_retained_bytes, vec_retained_bytes};
10use crate::planning::plan::{compile_step_plans, DiagPlan, GemmPlan, ReducePlan, StepPlan};
11use crate::syntax::subscripts::Subscripts;
12use crate::util::{build_size_dict, intermediate_subs};
13use crate::{Error, Result};
14
15/// A single step in the contraction sequence.
16#[derive(Clone)]
17pub(crate) struct ContractionStep {
18    pub(crate) left: usize,
19    pub(crate) right: usize,
20}
21
22/// Public options for automatic contraction-path optimization.
23///
24/// The default planner uses TreeSA with a greedy initializer and zero annealing
25/// iterations. This keeps the public API on a single optimizer family while
26/// making the default behavior effectively "greedy-only".
27///
28/// # Determinism
29///
30/// While annealing is disabled (`niters == 0` or empty `betas`, as in the
31/// default), the planned path is a function of the subscripts and shapes
32/// alone: the same spec yields the same path in every process and on every
33/// call. With an annealing schedule the path comes from omeco's TreeSA, whose
34/// annealing is seeded but whose greedy initializer (omeco 0.2.6) breaks ties
35/// in `HashMap` order, so annealed paths are not guaranteed to agree across
36/// processes.
37#[derive(Debug, Clone)]
38pub struct ContractionOptimizerOptions {
39    /// Inverse-temperature schedule for TreeSA.
40    pub betas: Vec<f64>,
41    /// Number of independent TreeSA trials.
42    pub ntrials: usize,
43    /// Annealing iterations per temperature level.
44    pub niters: usize,
45    /// Score function used by TreeSA.
46    pub score: ScoreFunction,
47}
48
49impl Default for ContractionOptimizerOptions {
50    fn default() -> Self {
51        Self {
52            betas: Vec::new(),
53            ntrials: 1,
54            niters: 0,
55            score: ScoreFunction::default(),
56        }
57    }
58}
59
60impl ContractionOptimizerOptions {
61    fn to_treesa(&self) -> TreeSA {
62        TreeSA::new(
63            self.betas.clone(),
64            self.ntrials,
65            self.niters,
66            Initializer::Greedy,
67            self.score.clone(),
68        )
69    }
70
71    /// Whether TreeSA would run any annealing iteration.
72    pub(crate) fn anneals(&self) -> bool {
73        self.niters > 0 && !self.betas.is_empty()
74    }
75
76    pub(crate) fn validate(&self) -> Result<()> {
77        if self.ntrials == 0 {
78            return Err(Error::planning(
79                "contraction optimizer ntrials must be at least 1",
80            ));
81        }
82        if self.betas.iter().any(|value| value.is_nan()) {
83            return Err(Error::planning(
84                "contraction optimizer betas must not contain NaN",
85            ));
86        }
87        if self.score.tc_weight.is_nan()
88            || self.score.sc_weight.is_nan()
89            || self.score.rw_weight.is_nan()
90            || self.score.sc_target.is_nan()
91        {
92            return Err(Error::planning(
93                "contraction optimizer score fields must not contain NaN",
94            ));
95        }
96        Ok(())
97    }
98}
99
100/// Contraction tree determining pairwise contraction order for N-ary einsum.
101///
102/// When contracting more than two tensors, the order in which pairwise
103/// contractions are performed significantly affects performance.
104/// `ContractionTree` encodes this order as a binary tree.
105///
106/// # Optimization
107///
108/// Use [`ContractionTree::optimize`] for automatic cost-based optimization
109/// (e.g., greedy algorithm based on tensor sizes), or
110/// [`ContractionTree::from_pairs`] for manual specification.
111#[derive(Clone)]
112pub struct ContractionTree {
113    /// Original subscripts.
114    pub(crate) subscripts: Subscripts,
115    /// Steps in the contraction (empty for single-tensor case).
116    pub(crate) steps: Vec<ContractionStep>,
117    /// Label → dimension size mapping.
118    pub(crate) size_dict: HashMap<u32, usize>,
119    /// Subscripts for each operand (0..input_count from input, then intermediates).
120    pub(crate) operand_subs: Vec<Vec<u32>>,
121    /// Pre-compiled step plans (cached to avoid recomputation per execute call).
122    pub(crate) step_plans: Vec<StepPlan>,
123}
124
125impl fmt::Debug for ContractionTree {
126    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
127        f.debug_struct("ContractionTree")
128            .field("input_count", &self.subscripts.inputs.len())
129            .field("output_rank", &self.subscripts.output.len())
130            .field("steps_len", &self.steps.len())
131            .field("size_dict_len", &self.size_dict.len())
132            .field("operand_subs_len", &self.operand_subs.len())
133            .field("step_plans_len", &self.step_plans.len())
134            .finish_non_exhaustive()
135    }
136}
137
138impl ContractionTree {
139    /// Automatically compute an optimized contraction order.
140    ///
141    /// Uses a cost-based heuristic (greedy algorithm) to determine
142    /// the pairwise contraction sequence that minimizes total operation count.
143    /// The path is deterministic: for fixed subscripts and shapes it is the
144    /// same in every process (see [`ContractionOptimizerOptions`]).
145    ///
146    /// # Arguments
147    ///
148    /// * `subscripts` — Einsum subscripts for all tensors
149    /// * `shapes` — Shape of each input tensor
150    ///
151    /// # Examples
152    ///
153    /// ```rust
154    /// use tenferro_einsum::{ContractionTree, Subscripts};
155    ///
156    /// let subs = Subscripts::parse("abcdef,bf,cf,df,ef->f").unwrap();
157    /// let shapes = [&[2, 3, 2, 4, 3, 9][..], &[3, 9], &[2, 9], &[4, 9], &[3, 9]];
158    /// let tree = ContractionTree::optimize(&subs, &shapes).unwrap();
159    /// assert_eq!(tree.step_count(), 4);
160    /// // Equal-cost candidates are broken by operand index, never by hashing.
161    /// let again = ContractionTree::optimize(&subs, &shapes).unwrap();
162    /// for step in 0..tree.step_count() {
163    ///     assert_eq!(tree.step_pair(step), again.step_pair(step));
164    /// }
165    /// ```
166    ///
167    /// # Errors
168    ///
169    /// Returns [`Error::Validation`] when subscripts and shapes have different
170    /// ranks or incompatible dimensions, or [`Error::Planning`] when no valid
171    /// contraction order can be constructed.
172    pub fn optimize(subscripts: &Subscripts, shapes: &[&[usize]]) -> Result<Self> {
173        Self::optimize_with_options(subscripts, shapes, &ContractionOptimizerOptions::default())
174    }
175
176    /// Automatically compute an optimized contraction order with explicit
177    /// planner options.
178    ///
179    /// For three or more operands with an annealing schedule (`niters > 0`
180    /// and non-empty `betas`), this routes planning through TreeSA using the
181    /// provided configuration. Without annealing, including the default
182    /// options, TreeSA would return its greedy initializer unchanged, so the
183    /// deterministic greedy planner runs directly and the path is identical in
184    /// every process. One or two operands need no ordering search; their trees
185    /// are built directly after validating the options.
186    ///
187    /// # Errors
188    ///
189    /// Returns [`Error::Validation`] for rank, shape, or dimension mismatches,
190    /// or [`Error::Planning`] when planner options such as `ntrials` are
191    /// invalid or no contraction order can be constructed.
192    pub fn optimize_with_options(
193        subscripts: &Subscripts,
194        shapes: &[&[usize]],
195        options: &ContractionOptimizerOptions,
196    ) -> Result<Self> {
197        options.validate()?;
198        let input_count = subscripts.inputs.len();
199        if input_count <= 1 {
200            return Self::from_pairs(subscripts, shapes, &[]);
201        }
202        if input_count == 2 {
203            return Self::from_pairs(subscripts, shapes, &[(0, 1)]);
204        }
205
206        let size_dict = build_size_dict(subscripts, shapes, None)?;
207        // Without annealing TreeSA returns its greedy initializer unchanged,
208        // and omeco 0.2.6's greedy breaks ties in per-process `HashMap` order
209        // (#1963), so the deterministic greedy plans this case directly.
210        let pairs = if !options.anneals() {
211            optimize_self_greedy_pairs(subscripts, &size_dict)?
212        } else if let Some(omeco_pairs) = optimize_omeco_pairs(subscripts, &size_dict, options)? {
213            omeco_pairs
214        } else {
215            optimize_self_greedy_pairs(subscripts, &size_dict)?
216        };
217        Self::from_pairs(subscripts, shapes, &pairs)
218    }
219
220    /// Manually build a contraction tree from a pairwise contraction sequence.
221    ///
222    /// Each pair `(i, j)` specifies which two tensors (or intermediate results)
223    /// to contract next. Intermediate results are assigned indices starting
224    /// from the number of input tensors.
225    ///
226    /// # Arguments
227    ///
228    /// * `subscripts` — Einsum subscripts for all tensors
229    /// * `shapes` — Shape of each input tensor
230    /// * `pairs` — Ordered list of pairwise contractions
231    ///
232    /// # Examples
233    ///
234    /// ```rust
235    /// use tenferro_einsum::{ContractionTree, Subscripts};
236    ///
237    /// // Three tensors: A[ij] B[jk] C[kl] -> D[il]
238    /// // Contract B and C first, then A with the result:
239    /// let subs = Subscripts::new(&[&[0, 1], &[1, 2], &[2, 3]], &[0, 3]);
240    /// let shapes = [&[3, 4][..], &[4, 5], &[5, 6]];
241    /// let tree = ContractionTree::from_pairs(
242    ///     &subs,
243    ///     &shapes,
244    ///     &[(1, 2), (0, 3)],  // B*C -> T(index=3), then A*T -> D
245    /// ).unwrap();
246    /// ```
247    ///
248    /// # Errors
249    ///
250    /// Returns [`Error::Planning`] when the pair count, operand indices, or
251    /// intermediate sequence is invalid, or [`Error::Validation`] when the
252    /// supplied shapes do not match the subscripts.
253    pub fn from_pairs(
254        subscripts: &Subscripts,
255        shapes: &[&[usize]],
256        pairs: &[(usize, usize)],
257    ) -> Result<Self> {
258        let input_count = subscripts.inputs.len();
259        let required_steps = input_count.saturating_sub(1);
260        if pairs.len() != required_steps {
261            return Err(Error::planning(format!(
262                "explicit contraction path for {input_count} operands must have {required_steps} steps, got {}",
263                pairs.len()
264            )));
265        }
266        let size_dict = build_size_dict(subscripts, shapes, None)?;
267
268        let mut operand_subs: Vec<Vec<u32>> = subscripts.inputs.clone();
269        let mut live = vec![false; input_count + pairs.len()];
270        for slot in live.iter_mut().take(input_count) {
271            *slot = true;
272        }
273        let mut steps = Vec::new();
274
275        for (step_idx, &(left, right)) in pairs.iter().enumerate() {
276            let next_idx = input_count + step_idx;
277            if left == right {
278                return Err(Error::planning(format!(
279                    "pair ({left}, {right}) must reference two distinct live operands"
280                )));
281            }
282            if left >= next_idx || right >= next_idx {
283                return Err(Error::planning(format!(
284                    "pair ({left}, {right}) references non-existent operand"
285                )));
286            }
287            if !live[left] || !live[right] {
288                return Err(Error::planning(format!(
289                    "pair ({left}, {right}) references an operand or intermediate that is no longer live"
290                )));
291            }
292
293            // Labels needed by other live operands + final output
294            let mut needed: HashSet<u32> = subscripts.output.iter().copied().collect();
295            for (idx, subs) in operand_subs.iter().enumerate() {
296                if idx != left && idx != right && live[idx] {
297                    needed.extend(subs.iter().copied());
298                }
299            }
300
301            let new_subs = intermediate_subs(&operand_subs[left], &operand_subs[right], &needed);
302            operand_subs.push(new_subs);
303            live[left] = false;
304            live[right] = false;
305            live[next_idx] = true;
306            steps.push(ContractionStep { left, right });
307        }
308
309        let live_count = live.iter().filter(|&&is_live| is_live).count();
310        if live_count != 1 {
311            return Err(Error::planning(format!(
312                "explicit contraction path must leave exactly one live result, got {live_count}"
313            )));
314        }
315
316        let mut tree = Self {
317            subscripts: subscripts.clone(),
318            steps,
319            size_dict,
320            operand_subs,
321            step_plans: Vec::new(),
322        };
323        tree.step_plans = compile_step_plans(&tree)?;
324        Ok(tree)
325    }
326
327    /// Return the number of pairwise contraction steps in this tree.
328    ///
329    /// # Examples
330    ///
331    /// ```rust
332    /// use tenferro_einsum::{ContractionTree, Subscripts};
333    ///
334    /// let subs = Subscripts::new(&[&[0, 1], &[1, 2], &[2, 3]], &[0, 3]);
335    /// let tree = ContractionTree::from_pairs(
336    ///     &subs,
337    ///     &[&[2, 2], &[2, 2], &[2, 2]],
338    ///     &[(1, 2), (0, 3)],
339    /// )
340    /// .unwrap();
341    /// assert_eq!(tree.step_count(), 2);
342    /// ```
343    #[must_use]
344    pub fn step_count(&self) -> usize {
345        self.steps.len()
346    }
347
348    pub(crate) fn label_size(&self, label: u32) -> Option<usize> {
349        self.size_dict.get(&label).copied()
350    }
351
352    pub(crate) fn output_shape(&self) -> Vec<usize> {
353        self.subscripts
354            .output
355            .iter()
356            .filter_map(|label| self.label_size(*label))
357            .collect()
358    }
359
360    /// Return the operand indices for a pairwise contraction step.
361    ///
362    /// The returned indices refer to the original inputs (`0..input_count`) and
363    /// then to intermediates (`input_count..`) produced by earlier steps.
364    ///
365    /// # Examples
366    ///
367    /// ```rust
368    /// use tenferro_einsum::{ContractionTree, Subscripts};
369    ///
370    /// let subs = Subscripts::new(&[&[0, 1], &[1, 2], &[2, 3]], &[0, 3]);
371    /// let tree = ContractionTree::from_pairs(
372    ///     &subs,
373    ///     &[&[2, 2], &[2, 2], &[2, 2]],
374    ///     &[(1, 2), (0, 3)],
375    /// )
376    /// .unwrap();
377    /// assert_eq!(tree.step_pair(0), Some((1, 2)));
378    /// ```
379    #[must_use]
380    pub fn step_pair(&self, step_idx: usize) -> Option<(usize, usize)> {
381        self.steps.get(step_idx).map(|step| (step.left, step.right))
382    }
383
384    /// Return the `(lhs, rhs, output)` subscripts for a pairwise step.
385    ///
386    /// The output subscripts are the intermediate labels preserved after the
387    /// contraction, or the final output labels on the last step.
388    ///
389    /// # Examples
390    ///
391    /// ```rust
392    /// use tenferro_einsum::{ContractionTree, Subscripts};
393    ///
394    /// let subs = Subscripts::new(&[&[0, 1], &[1, 2], &[2, 3]], &[0, 3]);
395    /// let tree = ContractionTree::from_pairs(
396    ///     &subs,
397    ///     &[&[2, 2], &[2, 2], &[2, 2]],
398    ///     &[(1, 2), (0, 3)],
399    /// )
400    /// .unwrap();
401    /// let (lhs, rhs, out) = tree.step_subscripts(0).unwrap();
402    /// assert_eq!(lhs, &[1, 2]);
403    /// assert_eq!(rhs, &[2, 3]);
404    /// assert_eq!(out, &[1, 3]);
405    /// ```
406    #[must_use]
407    pub fn step_subscripts(&self, step_idx: usize) -> Option<(&[u32], &[u32], &[u32])> {
408        let input_count = self.subscripts.inputs.len();
409        let step = self.steps.get(step_idx)?;
410        let result_idx = input_count + step_idx;
411        let output_subs = if step_idx + 1 == self.steps.len() {
412            &self.subscripts.output
413        } else {
414            &self.operand_subs[result_idx]
415        };
416        Some((
417            &self.operand_subs[step.left],
418            &self.operand_subs[step.right],
419            output_subs,
420        ))
421    }
422
423    /// Return the precomputed lowering plan for one pairwise contraction step.
424    ///
425    /// # Examples
426    ///
427    /// ```rust
428    /// use tenferro_einsum::{ContractionTree, Subscripts};
429    ///
430    /// let subs = Subscripts::new(&[&[0, 1], &[1, 2]], &[0, 2]);
431    /// let tree = ContractionTree::from_pairs(&subs, &[&[2, 3], &[3, 4]], &[(0, 1)]).unwrap();
432    ///
433    /// assert_eq!(tree.step_plan(0).unwrap().gemm().m(), 2);
434    /// ```
435    #[must_use]
436    pub fn step_plan(&self, step_idx: usize) -> Option<crate::lowering::PairwiseStepPlan<'_>> {
437        self.step_plans
438            .get(step_idx)
439            .map(crate::lowering::PairwiseStepPlan::new)
440    }
441
442    #[doc(hidden)]
443    #[must_use]
444    pub(crate) fn retained_bytes_for_cache_stats(&self) -> usize {
445        saturating_sum([
446            size_of::<Self>(),
447            subscripts_retained_bytes(&self.subscripts),
448            self.steps
449                .capacity()
450                .saturating_mul(size_of::<ContractionStep>()),
451            self.size_dict
452                .capacity()
453                .saturating_mul(size_of::<u32>().saturating_add(size_of::<usize>())),
454            vec_of_vec_retained_bytes(&self.operand_subs),
455            self.step_plans
456                .capacity()
457                .saturating_mul(size_of::<StepPlan>()),
458            saturating_sum(self.step_plans.iter().map(step_plan_retained_bytes)),
459        ])
460    }
461}
462
463fn subscripts_retained_bytes(subscripts: &Subscripts) -> usize {
464    saturating_sum([
465        vec_of_vec_retained_bytes(&subscripts.inputs),
466        vec_retained_bytes(&subscripts.output),
467    ])
468}
469
470fn reduce_plan_retained_bytes(plan: &ReducePlan) -> usize {
471    saturating_sum([
472        vec_retained_bytes(&plan.original_subs),
473        vec_retained_bytes(&plan.kept_subs),
474        vec_retained_bytes(&plan.out_shape),
475    ])
476}
477
478fn diag_plan_retained_bytes(plan: &DiagPlan) -> usize {
479    saturating_sum([
480        vec_retained_bytes(&plan.stages),
481        saturating_sum(plan.stages.iter().map(|stage| {
482            saturating_sum([
483                vec_retained_bytes(&stage.axis_pairs),
484                vec_retained_bytes(&stage.result_subs),
485            ])
486        })),
487        vec_retained_bytes(&plan.result_subs),
488    ])
489}
490
491fn gemm_plan_retained_bytes(plan: &GemmPlan) -> usize {
492    saturating_sum([
493        plan.reduce_a.as_ref().map_or(0, reduce_plan_retained_bytes),
494        plan.reduce_b.as_ref().map_or(0, reduce_plan_retained_bytes),
495        vec_retained_bytes(&plan.subs_a),
496        vec_retained_bytes(&plan.subs_b),
497        vec_retained_bytes(&plan.lo_modes),
498        vec_retained_bytes(&plan.ro_modes),
499        vec_retained_bytes(&plan.sum_modes),
500        vec_retained_bytes(&plan.lo_sizes),
501        vec_retained_bytes(&plan.ro_sizes),
502        vec_retained_bytes(&plan.sum_sizes),
503        vec_retained_bytes(&plan.batch_sizes),
504        vec_retained_bytes(&plan.target_a),
505        vec_retained_bytes(&plan.target_b),
506        vec_retained_bytes(&plan.c_gemm_shape),
507        vec_retained_bytes(&plan.expanded_shape),
508        vec_retained_bytes(&plan.canonical_modes),
509        vec_retained_bytes(&plan.a_gemm_shape),
510        vec_retained_bytes(&plan.b_gemm_shape),
511    ])
512}
513
514fn step_plan_retained_bytes(plan: &StepPlan) -> usize {
515    saturating_sum([
516        plan.diag_a.as_ref().map_or(0, diag_plan_retained_bytes),
517        plan.diag_b.as_ref().map_or(0, diag_plan_retained_bytes),
518        plan.strict_binary.as_ref().map_or(0, size_of_val),
519        gemm_plan_retained_bytes(&plan.gemm),
520    ])
521}
522
523fn optimize_omeco_pairs(
524    subscripts: &Subscripts,
525    size_dict: &HashMap<u32, usize>,
526    options: &ContractionOptimizerOptions,
527) -> Result<Option<Vec<(usize, usize)>>> {
528    #[cfg(test)]
529    tests::OMECO_CALLS.with(|count| count.set(count.get() + 1));
530    let code = OmecoEinCode::new(subscripts.inputs.clone(), subscripts.output.clone());
531    let optimizer = options.to_treesa();
532    let Some(nested) = optimizer.optimize(&code, size_dict) else {
533        return Ok(None);
534    };
535
536    let mut next_operand = subscripts.inputs.len();
537    let mut pairs = Vec::with_capacity(subscripts.inputs.len().saturating_sub(1));
538    nested_to_pairs(&nested, &mut next_operand, &mut pairs)?;
539    Ok(Some(pairs))
540}
541
542fn nested_to_pairs(
543    nested: &NestedEinsum<u32>,
544    next_operand: &mut usize,
545    pairs: &mut Vec<(usize, usize)>,
546) -> Result<usize> {
547    match nested {
548        NestedEinsum::Leaf { tensor_index } => Ok(*tensor_index),
549        NestedEinsum::Node { args, .. } => {
550            if args.len() != 2 {
551                return Err(Error::planning(format!(
552                    "omeco returned non-binary contraction node with {} children",
553                    args.len()
554                )));
555            }
556            let left = nested_to_pairs(&args[0], next_operand, pairs)?;
557            let right = nested_to_pairs(&args[1], next_operand, pairs)?;
558            pairs.push((left, right));
559            let result_idx = *next_operand;
560            *next_operand += 1;
561            Ok(result_idx)
562        }
563    }
564}
565
566fn build_operand_label_sets(operand_subs: &[Vec<u32>]) -> Vec<HashSet<u32>> {
567    operand_subs
568        .iter()
569        .map(|subs| subs.iter().copied().collect())
570        .collect()
571}
572
573fn build_needed_label_counts(
574    output_subs: &[u32],
575    available: &[usize],
576    operand_label_sets: &[HashSet<u32>],
577) -> HashMap<u32, usize> {
578    let mut counts = HashMap::new();
579    for &label in output_subs {
580        counts.entry(label).or_insert(1);
581    }
582    for &idx in available {
583        add_labels_to_counts(&mut counts, &operand_label_sets[idx]);
584    }
585    counts
586}
587
588fn add_labels_to_counts(counts: &mut HashMap<u32, usize>, labels: &HashSet<u32>) {
589    for &label in labels {
590        *counts.entry(label).or_insert(0) += 1;
591    }
592}
593
594fn remove_labels_from_counts(counts: &mut HashMap<u32, usize>, labels: &HashSet<u32>) {
595    for &label in labels {
596        match counts.get(&label).copied() {
597            Some(1) => {
598                counts.remove(&label);
599            }
600            Some(count) => {
601                counts.insert(label, count - 1);
602            }
603            None => {}
604        }
605    }
606}
607
608fn candidate_label_is_needed(
609    label: u32,
610    left: usize,
611    right: usize,
612    operand_label_sets: &[HashSet<u32>],
613    needed_label_counts: &HashMap<u32, usize>,
614) -> bool {
615    let mut selected_count = 0;
616    if operand_label_sets[left].contains(&label) {
617        selected_count += 1;
618    }
619    if operand_label_sets[right].contains(&label) {
620        selected_count += 1;
621    }
622    needed_label_counts.get(&label).copied().unwrap_or(0) > selected_count
623}
624
625fn collect_candidate_intermediate_subs(
626    subs_left: &[u32],
627    subs_right: &[u32],
628    left: usize,
629    right: usize,
630    operand_label_sets: &[HashSet<u32>],
631    needed_label_counts: &HashMap<u32, usize>,
632    output: &mut Vec<u32>,
633) {
634    output.clear();
635    for &label in subs_left.iter().chain(subs_right.iter()) {
636        if candidate_label_is_needed(label, left, right, operand_label_sets, needed_label_counts)
637            && !output.contains(&label)
638        {
639            output.push(label);
640        }
641    }
642}
643
644#[derive(Clone, Copy)]
645struct CandidateCostContext<'a> {
646    operand_label_sets: &'a [HashSet<u32>],
647    needed_label_counts: &'a HashMap<u32, usize>,
648    size_dict: &'a HashMap<u32, usize>,
649}
650
651fn candidate_contraction_cost(
652    subs_left: &[u32],
653    subs_right: &[u32],
654    left: usize,
655    right: usize,
656    context: CandidateCostContext<'_>,
657    candidate_subs: &mut Vec<u32>,
658) -> Result<usize> {
659    collect_candidate_intermediate_subs(
660        subs_left,
661        subs_right,
662        left,
663        right,
664        context.operand_label_sets,
665        context.needed_label_counts,
666        candidate_subs,
667    );
668    let mut cost = 1usize;
669    for &label in candidate_subs.iter() {
670        let size = context.size_dict.get(&label).copied().ok_or_else(|| {
671            Error::planning(format!(
672                "unknown size for label {label} in contraction cost"
673            ))
674        })?;
675        cost = cost.saturating_mul(size);
676    }
677    Ok(cost.max(1))
678}
679
680/// Deterministic greedy contraction order.
681///
682/// Each step contracts the connected pair (sharing at least one label) whose
683/// result is smallest, the size counting every label still needed after the
684/// pair: by another operand or by the output. Ties go to the smallest
685/// `(left, right)` operand index pair, where an intermediate takes the next
686/// index after all existing operands. When no remaining operands share a
687/// label, the two smallest indices form an outer product.
688///
689/// This is the greedy rule of omeco's `tree_greedy` with `alpha = 0` and
690/// `temperature = 0` (omeco, MIT, <https://github.com/GiggleLiu/omeco>, which
691/// ports `OMEinsumContractionOrders.jl`), with the deterministic vertex and
692/// tie ordering adopted upstream after omeco 0.2.6. omeco 0.2.6 iterates a
693/// `HashMap` to break ties, so its path differed between processes (#1963);
694/// tenferro plans its default (non-annealing) path here instead, until an
695/// omeco release carries the fix (<https://github.com/GiggleLiu/omeco/issues/44>). Only the
696/// pairs whose operands changed are re-scored after each step, because the
697/// cost of any other pair is unaffected by the merge.
698fn optimize_self_greedy_pairs(
699    subscripts: &Subscripts,
700    size_dict: &HashMap<u32, usize>,
701) -> Result<Vec<(usize, usize)>> {
702    use std::cmp::Reverse;
703    use std::collections::{BTreeMap, BTreeSet, BinaryHeap};
704
705    #[cfg(test)]
706    tests::SELF_GREEDY_CALLS.with(|count| count.set(count.get() + 1));
707    let input_count = subscripts.inputs.len();
708    let available: Vec<usize> = (0..input_count).collect();
709    let mut operand_subs: Vec<Vec<u32>> = subscripts.inputs.clone();
710    let mut operand_label_sets = build_operand_label_sets(&operand_subs);
711    let mut needed_label_counts =
712        build_needed_label_counts(&subscripts.output, &available, &operand_label_sets);
713    let mut live: BTreeSet<usize> = available.into_iter().collect();
714    let mut label_owners: BTreeMap<u32, BTreeSet<usize>> = BTreeMap::new();
715    for (operand, labels) in operand_label_sets.iter().enumerate() {
716        for &label in labels {
717            label_owners.entry(label).or_default().insert(operand);
718        }
719    }
720
721    let mut candidate_subs = Vec::new();
722    let mut heap: BinaryHeap<Reverse<(usize, usize, usize)>> = BinaryHeap::new();
723    let mut score = |left: usize,
724                     right: usize,
725                     operand_subs: &[Vec<u32>],
726                     operand_label_sets: &[HashSet<u32>],
727                     needed_label_counts: &HashMap<u32, usize>|
728     -> Result<Reverse<(usize, usize, usize)>> {
729        let cost = candidate_contraction_cost(
730            &operand_subs[left],
731            &operand_subs[right],
732            left,
733            right,
734            CandidateCostContext {
735                operand_label_sets,
736                needed_label_counts,
737                size_dict,
738            },
739            &mut candidate_subs,
740        )?;
741        Ok(Reverse((cost, left, right)))
742    };
743
744    let mut initial_pairs = BTreeSet::new();
745    for owners in label_owners.values() {
746        for &left in owners {
747            for &right in owners.range(left + 1..) {
748                initial_pairs.insert((left, right));
749            }
750        }
751    }
752    for (left, right) in initial_pairs {
753        heap.push(score(
754            left,
755            right,
756            &operand_subs,
757            &operand_label_sets,
758            &needed_label_counts,
759        )?);
760    }
761
762    let mut pairs: Vec<(usize, usize)> = Vec::with_capacity(input_count.saturating_sub(1));
763    while live.len() > 1 {
764        let mut chosen = None;
765        while let Some(Reverse((_, left, right))) = heap.pop() {
766            if live.contains(&left) && live.contains(&right) {
767                chosen = Some((left, right));
768                break;
769            }
770        }
771        let (left, right) = match chosen {
772            Some(pair) => pair,
773            None => {
774                let mut smallest = live.iter().copied();
775                match (smallest.next(), smallest.next()) {
776                    (Some(left), Some(right)) => (left, right),
777                    _ => break,
778                }
779            }
780        };
781        pairs.push((left, right));
782
783        let mut new_subs = Vec::new();
784        collect_candidate_intermediate_subs(
785            &operand_subs[left],
786            &operand_subs[right],
787            left,
788            right,
789            &operand_label_sets,
790            &needed_label_counts,
791            &mut new_subs,
792        );
793        let new_idx = operand_subs.len();
794        let new_label_set: HashSet<u32> = new_subs.iter().copied().collect();
795        remove_labels_from_counts(&mut needed_label_counts, &operand_label_sets[left]);
796        remove_labels_from_counts(&mut needed_label_counts, &operand_label_sets[right]);
797        add_labels_to_counts(&mut needed_label_counts, &new_label_set);
798        for operand in [left, right] {
799            for label in &operand_label_sets[operand] {
800                if let Some(owners) = label_owners.get_mut(label) {
801                    owners.remove(&operand);
802                }
803            }
804        }
805        let mut neighbors = BTreeSet::new();
806        for &label in &new_subs {
807            let owners = label_owners.entry(label).or_default();
808            neighbors.extend(owners.iter().copied());
809            owners.insert(new_idx);
810        }
811        live.remove(&left);
812        live.remove(&right);
813        live.insert(new_idx);
814        operand_subs.push(new_subs);
815        operand_label_sets.push(new_label_set);
816        for neighbor in neighbors {
817            heap.push(score(
818                neighbor,
819                new_idx,
820                &operand_subs,
821                &operand_label_sets,
822                &needed_label_counts,
823            )?);
824        }
825    }
826
827    Ok(pairs)
828}
829
830#[cfg(test)]
831mod tests;