1use std::hash::Hasher;
2
3use omeco::ScoreFunction;
4
5use crate::{
6 ContractionOptimizerOptions, ContractionTree, Error, NestedEinsum, Result, Subscripts,
7};
8
9#[derive(Clone, Debug)]
47pub enum EinsumOptimize {
48 Auto(ContractionOptimizerOptions),
50 False,
60 Nested(NestedEinsum),
62 Path(Vec<(usize, usize)>),
69 Tree(ContractionTree),
79}
80
81impl Default for EinsumOptimize {
82 fn default() -> Self {
84 Self::Auto(default_auto_options())
85 }
86}
87
88#[derive(Clone, Debug)]
89pub(crate) enum EinsumPlanSpec {
90 Auto(ContractionOptimizerOptions),
91 LeftToRight,
92 Path(Vec<(usize, usize)>),
93 FixedPairs(Vec<(usize, usize)>),
94}
95
96#[must_use]
98pub(crate) fn default_auto_options() -> ContractionOptimizerOptions {
99 ContractionOptimizerOptions {
100 score: ScoreFunction::time_optimized(),
101 ..Default::default()
102 }
103}
104
105pub(crate) fn plan_spec_from_optimize(
106 optimize: EinsumOptimize,
107 subscripts: &Subscripts,
108) -> Result<EinsumPlanSpec> {
109 match optimize {
110 EinsumOptimize::Auto(options) => {
111 options.validate()?;
112 Ok(EinsumPlanSpec::Auto(options))
113 }
114 EinsumOptimize::False => Ok(EinsumPlanSpec::LeftToRight),
115 EinsumOptimize::Nested(nested) => {
116 let pairs = nested_to_v1_pairs(&nested, subscripts.inputs.len())?;
117 validate_fixed_pairs(&pairs, subscripts.inputs.len())?;
118 Ok(EinsumPlanSpec::FixedPairs(pairs))
119 }
120 EinsumOptimize::Path(path) => {
121 let _ = jax_path_to_v1_pairs(&path, subscripts.inputs.len())?;
122 Ok(EinsumPlanSpec::Path(path))
123 }
124 EinsumOptimize::Tree(_) => Err(Error::planning(
125 "precomputed contraction tree requires concrete input shapes; use Path or parenthesized notation for symbolic traced einsum",
126 )),
127 }
128}
129
130pub(crate) fn resolve_einsum_strategy_with_spec(
131 optimize: EinsumOptimize,
132 subscripts: &Subscripts,
133 shapes: &[&[usize]],
134) -> Result<(EinsumPlanSpec, ContractionTree)> {
135 match optimize {
136 EinsumOptimize::Tree(tree) => {
137 let pairs = tree_pairs(&tree);
138 let spec = EinsumPlanSpec::FixedPairs(pairs);
139 let tree = resolve_plan_spec(&spec, subscripts, shapes)?;
140 Ok((spec, tree))
141 }
142 optimize => {
143 let spec = plan_spec_from_optimize(optimize, subscripts)?;
144 let tree = resolve_plan_spec(&spec, subscripts, shapes)?;
145 Ok((spec, tree))
146 }
147 }
148}
149
150pub(crate) fn resolve_plan_spec(
151 spec: &EinsumPlanSpec,
152 subscripts: &Subscripts,
153 shapes: &[&[usize]],
154) -> Result<ContractionTree> {
155 match spec {
156 EinsumPlanSpec::Auto(options) => {
157 ContractionTree::optimize_with_options(subscripts, shapes, options)
158 }
159 EinsumPlanSpec::LeftToRight => {
160 let n = subscripts.inputs.len();
165 let pairs: Vec<(usize, usize)> = (0..n.saturating_sub(1))
166 .map(|step| {
167 if step == 0 {
168 (0, 1)
169 } else {
170 (step + 1, n + step - 1)
171 }
172 })
173 .collect();
174 ContractionTree::from_pairs(subscripts, shapes, &pairs)
175 }
176 EinsumPlanSpec::Path(path) => {
177 let pairs = jax_path_to_v1_pairs(path, subscripts.inputs.len())?;
178 ContractionTree::from_pairs(subscripts, shapes, &pairs)
179 }
180 EinsumPlanSpec::FixedPairs(pairs) => ContractionTree::from_pairs(subscripts, shapes, pairs),
181 }
182}
183
184pub(crate) fn hash_einsum_plan_spec(spec: &EinsumPlanSpec, state: &mut dyn Hasher) {
185 match spec {
186 EinsumPlanSpec::Auto(options) => {
187 state.write_u8(0);
188 hash_optimizer_options(options, state);
189 }
190 EinsumPlanSpec::LeftToRight => state.write_u8(1),
191 EinsumPlanSpec::Path(path) => {
192 state.write_u8(2);
193 hash_pairs(path, state);
194 }
195 EinsumPlanSpec::FixedPairs(pairs) => {
196 state.write_u8(3);
197 hash_pairs(pairs, state);
198 }
199 }
200}
201
202pub(crate) fn plan_specs_equal(lhs: &EinsumPlanSpec, rhs: &EinsumPlanSpec) -> bool {
203 match (lhs, rhs) {
204 (EinsumPlanSpec::Auto(lhs), EinsumPlanSpec::Auto(rhs)) => {
205 optimizer_options_equal_by_bits(lhs, rhs)
206 }
207 (EinsumPlanSpec::LeftToRight, EinsumPlanSpec::LeftToRight) => true,
208 (EinsumPlanSpec::Path(lhs), EinsumPlanSpec::Path(rhs)) => lhs == rhs,
209 (EinsumPlanSpec::FixedPairs(lhs), EinsumPlanSpec::FixedPairs(rhs)) => lhs == rhs,
210 _ => false,
211 }
212}
213
214fn tree_pairs(tree: &ContractionTree) -> Vec<(usize, usize)> {
215 (0..tree.step_count())
216 .filter_map(|step| tree.step_pair(step))
217 .collect()
218}
219
220fn validate_fixed_pairs(pairs: &[(usize, usize)], input_count: usize) -> Result<()> {
221 let required_steps = input_count.saturating_sub(1);
222 if pairs.len() != required_steps {
223 return Err(Error::planning(format!(
224 "explicit contraction path for {input_count} operands must have {required_steps} steps, got {}",
225 pairs.len()
226 )));
227 }
228
229 let mut live = vec![false; input_count + pairs.len()];
230 for slot in live.iter_mut().take(input_count) {
231 *slot = true;
232 }
233
234 for (step_idx, &(left, right)) in pairs.iter().enumerate() {
235 let next_idx = input_count + step_idx;
236 if left == right {
237 return Err(Error::planning(format!(
238 "pair ({left}, {right}) must reference two distinct live operands"
239 )));
240 }
241 if left >= next_idx || right >= next_idx {
242 return Err(Error::planning(format!(
243 "pair ({left}, {right}) references non-existent operand"
244 )));
245 }
246 if !live[left] || !live[right] {
247 return Err(Error::planning(format!(
248 "pair ({left}, {right}) references an operand or intermediate that is no longer live"
249 )));
250 }
251
252 live[left] = false;
253 live[right] = false;
254 live[next_idx] = true;
255 }
256
257 let live_count = live.iter().filter(|&&is_live| is_live).count();
258 if live_count != 1 {
259 return Err(Error::planning(format!(
260 "explicit contraction path must leave exactly one live result, got {live_count}"
261 )));
262 }
263
264 Ok(())
265}
266
267fn hash_pairs(pairs: &[(usize, usize)], state: &mut dyn Hasher) {
268 state.write_usize(pairs.len());
269 for &(left, right) in pairs {
270 state.write_usize(left);
271 state.write_usize(right);
272 }
273}
274
275fn hash_optimizer_options(options: &ContractionOptimizerOptions, state: &mut dyn Hasher) {
276 state.write_usize(options.ntrials);
277 state.write_usize(options.niters);
278 state.write_usize(options.betas.len());
279 for value in &options.betas {
280 state.write_u64(value.to_bits());
281 }
282 state.write_u64(options.score.tc_weight.to_bits());
283 state.write_u64(options.score.sc_weight.to_bits());
284 state.write_u64(options.score.rw_weight.to_bits());
285 state.write_u64(options.score.sc_target.to_bits());
286}
287
288fn optimizer_options_equal_by_bits(
289 lhs: &ContractionOptimizerOptions,
290 rhs: &ContractionOptimizerOptions,
291) -> bool {
292 lhs.ntrials == rhs.ntrials
293 && lhs.niters == rhs.niters
294 && f64_slices_equal_by_bits(&lhs.betas, &rhs.betas)
295 && score_functions_equal_by_bits(&lhs.score, &rhs.score)
296}
297
298pub(crate) fn jax_path_to_v1_pairs(
310 jax_path: &[(usize, usize)],
311 input_count: usize,
312) -> Result<Vec<(usize, usize)>> {
313 let required_steps = input_count.saturating_sub(1);
314 if jax_path.len() != required_steps {
315 return Err(Error::planning(format!(
316 "explicit contraction path for {input_count} operands must have {required_steps} steps, got {}",
317 jax_path.len()
318 )));
319 }
320
321 let mut positions: Vec<usize> = (0..input_count).collect();
322 let mut v1_pairs = Vec::with_capacity(jax_path.len());
323
324 for (step, &(pos_a, pos_b)) in jax_path.iter().enumerate() {
325 if pos_a == pos_b {
326 return Err(Error::planning(format!(
327 "path step {step} references the same operand position twice: {pos_a}"
328 )));
329 }
330 let current_len = positions.len();
331 if pos_a >= current_len || pos_b >= current_len {
332 return Err(Error::planning(format!(
333 "path step {step} references operand positions ({pos_a}, {pos_b}) with only {current_len} live operands"
334 )));
335 }
336
337 let (lo, hi) = if pos_a < pos_b {
338 (pos_a, pos_b)
339 } else {
340 (pos_b, pos_a)
341 };
342 let id_a = positions[lo];
343 let id_b = positions[hi];
344 v1_pairs.push((id_a, id_b));
345
346 positions.remove(hi);
347 positions.remove(lo);
348 positions.push(input_count + step);
349 }
350
351 Ok(v1_pairs)
352}
353
354pub(crate) fn nested_to_v1_pairs(
361 nested: &NestedEinsum,
362 input_count: usize,
363) -> Result<Vec<(usize, usize)>> {
364 let mut pairs = Vec::with_capacity(input_count.saturating_sub(1));
365 let mut next_id = input_count;
366 let root_id = walk_nested(nested, input_count, &mut pairs, &mut next_id)?;
367 if input_count == 0 || root_id >= next_id {
368 return Err(Error::planning(
369 "nested einsum did not produce a valid root operand",
370 ));
371 }
372 Ok(pairs)
373}
374
375fn walk_nested(
376 nested: &NestedEinsum,
377 input_count: usize,
378 pairs: &mut Vec<(usize, usize)>,
379 next_id: &mut usize,
380) -> Result<usize> {
381 match nested {
382 NestedEinsum::Leaf(idx) => {
383 if *idx >= input_count {
384 return Err(Error::planning(format!(
385 "nested einsum leaf {idx} is outside 0..{input_count}"
386 )));
387 }
388 Ok(*idx)
389 }
390 NestedEinsum::Node { children, .. } => {
391 let Some(first) = children.first() else {
392 return Err(Error::planning(
393 "nested einsum node must have at least one child",
394 ));
395 };
396 let mut result_id = walk_nested(first, input_count, pairs, next_id)?;
397 for child in &children[1..] {
398 let child_id = walk_nested(child, input_count, pairs, next_id)?;
399 pairs.push((result_id, child_id));
400 result_id = *next_id;
401 *next_id += 1;
402 }
403 Ok(result_id)
404 }
405 }
406}
407
408fn f64_slices_equal_by_bits(lhs: &[f64], rhs: &[f64]) -> bool {
409 lhs.len() == rhs.len()
410 && lhs
411 .iter()
412 .zip(rhs)
413 .all(|(lhs, rhs)| lhs.to_bits() == rhs.to_bits())
414}
415
416fn score_functions_equal_by_bits(lhs: &ScoreFunction, rhs: &ScoreFunction) -> bool {
417 lhs.tc_weight.to_bits() == rhs.tc_weight.to_bits()
418 && lhs.sc_weight.to_bits() == rhs.sc_weight.to_bits()
419 && lhs.rw_weight.to_bits() == rhs.rw_weight.to_bits()
420 && lhs.sc_target.to_bits() == rhs.sc_target.to_bits()
421}
422
423#[cfg(test)]
424mod tests;