Skip to main content

tenferro_einsum/
extension.rs

1use std::any::Any;
2use std::collections::hash_map::DefaultHasher;
3use std::collections::HashMap;
4#[cfg(feature = "autodiff")]
5use std::collections::HashSet;
6use std::hash::{Hash, Hasher};
7use std::sync::Arc;
8
9use computegraph::graph::GraphBuilder;
10use computegraph::types::ValueRef;
11#[cfg(feature = "autodiff")]
12use tenferro_ad::semantic_extension::{
13    AdValue, ResidualSpec, SemanticAdError, SemanticAdRuleRole, SemanticExtensionRegistryError,
14    SemanticExtensionRuleSet, SemanticLinearTransposeRequest, SemanticLinearTransposeRule,
15    SemanticLinearizeRequest, SemanticLinearizeResult, SemanticLinearizeRule,
16    SemanticPrimalVjpRequest, SemanticPrimalVjpRule,
17};
18use tenferro_extension_macros::define_extension_runtime;
19#[cfg(feature = "autodiff")]
20use tenferro_ops::dim_expr::DimExpr;
21use tenferro_ops::ext_op::{
22    ExtensionLoweringError, ExtensionLoweringResult, ExtensionOp, ExtensionStandardLowering,
23};
24use tenferro_ops::std_tensor_op::StdTensorOp;
25use tenferro_ops::sym_dim::SymDim;
26#[cfg(feature = "autodiff")]
27use tenferro_ops::ShapeExtent;
28use tenferro_runtime::extension::{ExtensionCacheKey, ExtensionExecutionContext};
29#[cfg(feature = "autodiff")]
30use tenferro_runtime::program::{
31    CoreSemanticOp, ProgramValue, ProgramValueMetadata, SemanticProgramBuilder,
32};
33use tenferro_tensor::{DType, Engine, Error as TensorError, Tensor, TensorRead};
34
35#[cfg(feature = "autodiff")]
36use crate::broadcast::{broadcast_axis_reduce, classify_dim_exprs, UndecidedBroadcastAxis};
37use crate::broadcast::{merge_broadcast_extent, ExtentMerge};
38use crate::builder::build_einsum_graph;
39use crate::cache::{
40    einsum_subscripts_retained_bytes, saturating_sum, vec_retained_bytes,
41    EINSUM_EXTENSION_FAMILY_ID, EINSUM_RUNTIME_PLANS_CACHE,
42};
43#[cfg(test)]
44use crate::optimize::default_auto_options;
45#[cfg(feature = "autodiff")]
46use crate::optimize::jax_path_to_v1_pairs;
47use crate::optimize::{hash_einsum_plan_spec, plan_specs_equal, resolve_plan_spec, EinsumPlanSpec};
48#[cfg(feature = "autodiff")]
49use crate::util::map_label_occurrences;
50use crate::{
51    ContractionTree, EinsumSubscripts, Error as EinsumError, Result as EinsumResult, Subscripts,
52};
53
54/// Standard einsum extension payload.
55///
56/// This mirrors the current `tenferro.einsum.v1` payload shape. Runtime-owned
57/// execution goes through [`EinsumRuntime`].
58#[derive(Clone)]
59pub(crate) struct EinsumExtensionOp {
60    subscripts: EinsumSubscripts,
61    plan_spec: EinsumPlanSpec,
62    output_shape_hint: Option<Vec<SymDim>>,
63    allow_broadcast: bool,
64}
65
66impl std::fmt::Debug for EinsumExtensionOp {
67    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
68        f.debug_struct("EinsumExtensionOp")
69            .field("subscripts", &self.subscripts)
70            .field("plan_spec", &self.plan_spec)
71            .field("output_shape_hint", &self.output_shape_hint)
72            .field("allow_broadcast", &self.allow_broadcast)
73            .finish()
74    }
75}
76
77impl EinsumExtensionOp {
78    /// Create an einsum extension payload without a precomputed plan.
79    #[must_use]
80    #[cfg(test)]
81    pub(crate) fn new(subscripts: EinsumSubscripts) -> Self {
82        Self::with_plan_spec(subscripts, EinsumPlanSpec::Auto(default_auto_options()))
83    }
84
85    #[must_use]
86    pub(crate) fn with_plan_spec(subscripts: EinsumSubscripts, plan_spec: EinsumPlanSpec) -> Self {
87        Self {
88            subscripts,
89            plan_spec,
90            output_shape_hint: None,
91            allow_broadcast: false,
92        }
93    }
94
95    pub(crate) fn with_plan_spec_and_broadcast(
96        subscripts: EinsumSubscripts,
97        plan_spec: EinsumPlanSpec,
98        allow_broadcast: bool,
99    ) -> Self {
100        let mut op = Self::with_plan_spec(subscripts, plan_spec);
101        op.allow_broadcast = allow_broadcast;
102        op
103    }
104
105    /// Create an einsum extension payload with an explicit output shape hint.
106    #[must_use]
107    #[cfg(any(feature = "autodiff", test))]
108    pub(crate) fn with_output_shape_hint(
109        subscripts: EinsumSubscripts,
110        output_shape_hint: Vec<SymDim>,
111        plan_spec: EinsumPlanSpec,
112    ) -> Self {
113        let mut op = Self::with_plan_spec(subscripts, plan_spec);
114        op.output_shape_hint = Some(output_shape_hint);
115        op
116    }
117
118    #[must_use]
119    #[cfg(feature = "autodiff")]
120    pub(crate) fn with_output_shape_hint_and_broadcast(
121        subscripts: EinsumSubscripts,
122        output_shape_hint: Vec<SymDim>,
123        plan_spec: EinsumPlanSpec,
124        allow_broadcast: bool,
125    ) -> Self {
126        let mut op = Self::with_plan_spec_and_broadcast(subscripts, plan_spec, allow_broadcast);
127        op.output_shape_hint = Some(output_shape_hint);
128        op
129    }
130
131    /// Return the canonical subscripts.
132    #[must_use]
133    pub(crate) fn subscripts(&self) -> &EinsumSubscripts {
134        &self.subscripts
135    }
136
137    /// Return the shape-independent planning policy.
138    #[must_use]
139    pub(crate) fn plan_spec(&self) -> &EinsumPlanSpec {
140        &self.plan_spec
141    }
142
143    #[must_use]
144    #[cfg(feature = "autodiff")]
145    pub(crate) fn allow_broadcast(&self) -> bool {
146        self.allow_broadcast
147    }
148}
149
150impl ExtensionOp for EinsumExtensionOp {
151    fn family_id(&self) -> &'static str {
152        EINSUM_EXTENSION_FAMILY_ID
153    }
154
155    fn payload_hash(&self, hasher: &mut dyn Hasher) {
156        hasher.write_usize(self.subscripts.inputs.len());
157        for input in &self.subscripts.inputs {
158            hasher.write_usize(input.len());
159            for label in input {
160                hasher.write_u32(*label);
161            }
162        }
163        hasher.write_usize(self.subscripts.output.len());
164        for label in &self.subscripts.output {
165            hasher.write_u32(*label);
166        }
167        hash_einsum_plan_spec(self.plan_spec(), hasher);
168        hasher.write_u8(u8::from(self.allow_broadcast));
169        if let Some(shape) = &self.output_shape_hint {
170            hasher.write_usize(shape.len());
171            for dim in shape {
172                match dim.constant_value() {
173                    Some(value) => {
174                        hasher.write_u8(1);
175                        hasher.write_usize(value);
176                    }
177                    None => hasher.write_u8(0),
178                }
179            }
180        } else {
181            hasher.write_usize(usize::MAX);
182        }
183    }
184
185    fn payload_eq(&self, other: &dyn ExtensionOp) -> bool {
186        other.as_any().downcast_ref::<Self>().is_some_and(|that| {
187            self.subscripts == that.subscripts
188                && plan_specs_equal(self.plan_spec(), that.plan_spec())
189                && self.output_shape_hint == that.output_shape_hint
190                && self.allow_broadcast == that.allow_broadcast
191        })
192    }
193
194    fn clone_arc(&self) -> Arc<dyn ExtensionOp> {
195        Arc::new(self.clone())
196    }
197
198    fn as_any(&self) -> &dyn Any {
199        self
200    }
201
202    fn input_count(&self) -> usize {
203        self.subscripts.inputs.len()
204    }
205
206    fn output_count(&self) -> usize {
207        1
208    }
209
210    fn semantic_effects(&self) -> tenferro_ops::ext_op::ExtensionEffectDeclaration<'_> {
211        tenferro_ops::ext_op::ExtensionEffectDeclaration::Declared(&[])
212    }
213
214    fn semantic_aliases(&self) -> tenferro_ops::ext_op::ExtensionAliasDeclaration<'_> {
215        tenferro_ops::ext_op::ExtensionAliasDeclaration::AllFresh
216    }
217
218    fn infer_output_meta(
219        &self,
220        ctx: &mut tenferro_ops::ExtensionShapeContext<'_>,
221    ) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
222        let input_dtypes = (0..self.input_count())
223            .map(|input| ctx.input_dtype(input))
224            .collect::<Result<Vec<_>, _>>()?;
225        let input_shapes = (0..self.input_count())
226            .map(|input| ctx.input_shape(input).map(<[_]>::to_vec))
227            .collect::<Result<Vec<_>, _>>()?;
228
229        let mut label_dims: HashMap<u32, SymDim> = HashMap::new();
230        for (labels, shape) in self.subscripts.inputs.iter().zip(input_shapes.iter()) {
231            if labels.len() != shape.len() {
232                return Err(TensorError::rank_mismatch(
233                    "einsum",
234                    labels.len(),
235                    shape.len(),
236                ));
237            }
238            let mut operand_dims: HashMap<u32, SymDim> = HashMap::new();
239            for (&label, dim) in labels.iter().zip(shape.iter()) {
240                // INVARIANT: a label repeated inside one operand is a diagonal,
241                // never a broadcast, so its extents stay equal even when
242                // `allow_broadcast` admits a size-1 broadcast between operands.
243                if let Some(existing) = operand_dims.get(&label) {
244                    ctx.require_equal(existing.clone(), dim.clone())?;
245                    continue;
246                }
247                operand_dims.insert(label, dim.clone());
248                if let Some(existing) = label_dims.get_mut(&label) {
249                    match merge_broadcast_extent(existing, dim, self.allow_broadcast) {
250                        ExtentMerge::Merged(merged) => *existing = merged,
251                        ExtentMerge::RequireEqual => {
252                            ctx.require_equal(existing.clone(), dim.clone())?;
253                        }
254                    }
255                } else {
256                    label_dims.insert(label, dim.clone());
257                }
258            }
259        }
260
261        let output_shape = match &self.output_shape_hint {
262            Some(shape) if shape.iter().all(|dim| dim.constant_value().is_some()) => shape.clone(),
263            _ => self
264                .subscripts
265                .output
266                .iter()
267                .map(|label| label_dims.get(label).cloned())
268                .collect::<Option<Vec<_>>>()
269                .ok_or_else(|| {
270                    TensorError::invalid_argument(
271                        "einsum",
272                        "output labels",
273                        "must be present in input metadata",
274                    )
275                })?,
276        };
277        if output_shape.len() != self.subscripts.output.len() {
278            return Err(TensorError::rank_mismatch(
279                "einsum",
280                self.subscripts.output.len(),
281                output_shape.len(),
282            ));
283        }
284        if let Some(external) = input_dtypes
285            .iter()
286            .find(|dtype| matches!(dtype, DType::External(_)))
287        {
288            return Err(TensorError::unsupported_dtype(
289                "einsum",
290                *external,
291                "einsum takes preset scalars only; an externally defined scalar is not supported",
292            ));
293        }
294        Ok(vec![(
295            promote_dtypes(input_dtypes.iter().copied()),
296            output_shape,
297        )])
298    }
299
300    fn lower_to_standard_ops(
301        &self,
302        builder: &mut GraphBuilder<StdTensorOp>,
303        inputs: &[ValueRef<StdTensorOp>],
304        input_dtypes: &[DType],
305        input_shapes: &[&[SymDim]],
306    ) -> ExtensionLoweringResult {
307        if inputs.len() != self.input_count()
308            || input_dtypes.len() != self.input_count()
309            || input_shapes.len() != self.input_count()
310        {
311            return Err(ExtensionLoweringError::new(format!(
312                "einsum extension expects {} inputs, got values={}, dtypes={}, shapes={}",
313                self.input_count(),
314                inputs.len(),
315                input_dtypes.len(),
316                input_shapes.len()
317            )));
318        }
319
320        let Some(shapes) = concrete_sym_shape_slices(input_shapes) else {
321            return Ok(ExtensionStandardLowering::Unsupported);
322        };
323        let shape_refs: Vec<&[usize]> = shapes.iter().map(Vec::as_slice).collect();
324        let subs = Subscripts::from(&self.subscripts);
325        let tree = resolve_plan_spec(self.plan_spec(), &subs, &shape_refs).map_err(|source| {
326            ExtensionLoweringError::from_source_with_kind(source.kind(), source)
327        })?;
328        let output = build_einsum_graph(builder, &tree, inputs, &shapes).map_err(|source| {
329            ExtensionLoweringError::from_source_with_kind(source.kind(), source)
330        })?;
331        Ok(ExtensionStandardLowering::Lowered(vec![output]))
332    }
333}
334
335fn concrete_sym_shape_slices(input_shapes: &[&[SymDim]]) -> Option<Vec<Vec<usize>>> {
336    input_shapes
337        .iter()
338        .map(|shape| {
339            shape
340                .iter()
341                .map(SymDim::constant_value)
342                .collect::<Option<Vec<_>>>()
343        })
344        .collect()
345}
346
347/// Return the semantic-program einsum extension AD rules.
348#[cfg(feature = "autodiff")]
349///
350/// # Errors
351///
352/// Returns [`SemanticExtensionRegistryError::MalformedFamilyId`] for an
353/// invalid family identifier, or
354/// [`SemanticExtensionRegistryError::DuplicateRule`] for a duplicate role.
355pub fn semantic_ad_rules(
356) -> std::result::Result<SemanticExtensionRuleSet, SemanticExtensionRegistryError> {
357    SemanticExtensionRuleSet::new()
358        .with_linearize(Arc::new(EinsumAdRule))?
359        .with_linear_transpose(Arc::new(EinsumAdRule))?
360        .with_primal_vjp(Arc::new(EinsumAdRule))
361}
362
363#[derive(Debug)]
364#[cfg(feature = "autodiff")]
365struct EinsumAdRule;
366
367#[cfg(feature = "autodiff")]
368impl SemanticLinearizeRule for EinsumAdRule {
369    fn family_id(&self) -> &'static str {
370        EINSUM_EXTENSION_FAMILY_ID
371    }
372
373    fn linearize(
374        &self,
375        request: SemanticLinearizeRequest<'_>,
376        builder: &mut SemanticProgramBuilder,
377    ) -> std::result::Result<SemanticLinearizeResult, SemanticAdError> {
378        let op = semantic_einsum_payload(request.op(), SemanticAdRuleRole::Linearize)?;
379        if !request.active_outputs()[0] {
380            return Ok(SemanticLinearizeResult::new([AdValue::Absent], []));
381        }
382        let mut terms = Vec::new();
383        for (active_idx, tangent) in request.tangent_inputs().iter().copied().enumerate() {
384            let AdValue::Value(tangent) = tangent else {
385                continue;
386            };
387            let inputs: Vec<_> = request
388                .primal_inputs()
389                .iter()
390                .copied()
391                .enumerate()
392                .map(|(input_idx, primal)| {
393                    if input_idx == active_idx {
394                        tangent
395                    } else {
396                        primal
397                    }
398                })
399                .collect();
400            terms.push(builder.add_extension(Arc::new(op.clone()), &inputs)?[0]);
401        }
402        let tangent = semantic_sum_terms(builder, terms)?;
403        Ok(SemanticLinearizeResult::new([tangent], []))
404    }
405}
406
407#[cfg(feature = "autodiff")]
408impl SemanticLinearTransposeRule for EinsumAdRule {
409    fn family_id(&self) -> &'static str {
410        EINSUM_EXTENSION_FAMILY_ID
411    }
412
413    fn residual_mask(&self) -> ResidualSpec {
414        // The einsum VJP reads every non-active operand as a tensor operand
415        // (conjugate + contract with the cotangent); which operands are read
416        // depends on the active-input configuration, so all inputs are
417        // declared. The output is only used for its shape.
418        ResidualSpec::all_inputs()
419    }
420
421    fn linear_transpose(
422        &self,
423        request: SemanticLinearTransposeRequest<'_>,
424        builder: &mut SemanticProgramBuilder,
425    ) -> std::result::Result<Box<[AdValue]>, SemanticAdError> {
426        let primal_inputs = (0..request.primal_input_count())
427            .map(|index| request.primal_input_value(index))
428            .collect::<Result<Vec<_>, _>>()?;
429        let primal_output_metadata = request.primal_output_meta(0)?;
430        semantic_einsum_vjp(
431            request.op(),
432            &primal_inputs,
433            primal_output_metadata,
434            request.cotangent_outputs(),
435            request.active_inputs(),
436            request.residual_mask(),
437            builder,
438        )
439    }
440}
441
442#[cfg(feature = "autodiff")]
443impl SemanticPrimalVjpRule for EinsumAdRule {
444    fn family_id(&self) -> &'static str {
445        EINSUM_EXTENSION_FAMILY_ID
446    }
447
448    fn residual_mask(&self) -> ResidualSpec {
449        // Same operand set as the linear transpose: every non-active input is
450        // read as a tensor; the output only for its shape.
451        ResidualSpec::all_inputs()
452    }
453
454    fn primal_vjp(
455        &self,
456        request: SemanticPrimalVjpRequest<'_>,
457        builder: &mut SemanticProgramBuilder,
458    ) -> std::result::Result<Box<[AdValue]>, SemanticAdError> {
459        let primal_inputs = (0..request.primal_input_count())
460            .map(|index| request.primal_input_value(index))
461            .collect::<Result<Vec<_>, _>>()?;
462        let primal_output_metadata = request.primal_output_meta(0)?;
463        semantic_einsum_vjp(
464            request.op(),
465            &primal_inputs,
466            primal_output_metadata,
467            request.cotangent_outputs(),
468            request.active_inputs(),
469            request.residual_mask(),
470            builder,
471        )
472    }
473}
474
475#[cfg(feature = "autodiff")]
476fn semantic_einsum_vjp(
477    payload: &dyn ExtensionOp,
478    primal_inputs: &[ProgramValue],
479    primal_output_metadata: &ProgramValueMetadata,
480    cotangent_outputs: &[AdValue],
481    active_inputs: &[bool],
482    residual_mask: ResidualSpec,
483    builder: &mut SemanticProgramBuilder,
484) -> std::result::Result<Box<[AdValue]>, SemanticAdError> {
485    let op = semantic_einsum_payload(payload, SemanticAdRuleRole::LinearTranspose)?;
486    let input_count = op.subscripts.inputs.len();
487    let AdValue::Value(cotangent) = cotangent_outputs[0] else {
488        return Ok(vec![AdValue::Absent; input_count].into_boxed_slice());
489    };
490    let primal_input_shapes = primal_inputs
491        .iter()
492        .copied()
493        .map(|value| semantic_value_shape(builder, value))
494        .collect::<std::result::Result<Vec<_>, _>>()?;
495    let cotangent_shape = semantic_metadata_shape(primal_output_metadata)?;
496
497    let input_labels = &op.subscripts.inputs;
498    let output_labels = &op.subscripts.output;
499    let mut result = Vec::with_capacity(input_count);
500    for active_idx in 0..input_count {
501        if !active_inputs[active_idx] {
502            result.push(AdValue::Absent);
503            continue;
504        }
505        let mut available_labels: HashSet<u32> = output_labels.iter().copied().collect();
506        for (input_idx, labels) in input_labels.iter().enumerate() {
507            if input_idx != active_idx {
508                available_labels.extend(labels.iter().copied());
509            }
510        }
511        let summed_labels =
512            broadcast_summed_labels(builder, op, active_idx, primal_inputs, cotangent)?;
513        // Dropping a label from the VJP einsum's output sums the cotangent over
514        // it; the remap below broadcasts the axis back to the active extent.
515        let vjp_output_labels: Vec<u32> = input_labels[active_idx]
516            .iter()
517            .copied()
518            .filter(|label| available_labels.contains(label) && !summed_labels.contains(label))
519            .collect();
520        let mut vjp_input_labels = vec![output_labels.clone()];
521        let mut vjp_inputs = vec![cotangent];
522        let mut vjp_input_shapes = vec![cotangent_shape.clone()];
523        for input_idx in 0..input_count {
524            if input_idx == active_idx {
525                continue;
526            }
527            vjp_input_labels.push(input_labels[input_idx].clone());
528            vjp_input_shapes.push(primal_input_shapes[input_idx].clone());
529            debug_assert!(
530                residual_mask.declares_input(input_idx),
531                "einsum transpose read primal input {input_idx} as a tensor operand but the \
532                 residual mask does not declare it; declare it in the einsum rule's residual mask"
533            );
534            vjp_inputs.push(semantic_conjugate_if_complex(
535                builder,
536                primal_inputs[input_idx],
537            )?);
538        }
539        let vjp_op = semantic_vjp_einsum_op(
540            op,
541            active_idx,
542            EinsumSubscripts {
543                inputs: vjp_input_labels,
544                output: vjp_output_labels.clone(),
545            },
546            &vjp_input_shapes,
547        )?;
548        let mut input_cotangent = builder.add_extension(Arc::new(vjp_op), &vjp_inputs)?[0];
549        if vjp_output_labels != input_labels[active_idx] {
550            input_cotangent = semantic_broadcast_einsum_vjp(
551                builder,
552                input_cotangent,
553                &vjp_output_labels,
554                &input_labels[active_idx],
555                primal_input_shapes[active_idx].clone(),
556            )?;
557        }
558        result.push(AdValue::Value(input_cotangent));
559    }
560    Ok(result.into_boxed_slice())
561}
562
563/// Labels of the active operand that a singleton broadcast separates from the
564/// VJP einsum's output extent (see [`AxisCotangent`]): the VJP einsum sums
565/// them out and the result is broadcast back to the active operand's shape.
566///
567/// Extents are resolved against the shapes bound to the program inputs, so an
568/// eager graph (symbolic metadata, concrete bindings) decides from the bound
569/// lengths.
570#[cfg(feature = "autodiff")]
571fn broadcast_summed_labels(
572    builder: &SemanticProgramBuilder,
573    op: &EinsumExtensionOp,
574    active_idx: usize,
575    primal_inputs: &[ProgramValue],
576    cotangent: ProgramValue,
577) -> std::result::Result<HashSet<u32>, SemanticAdError> {
578    let mut summed = HashSet::new();
579    if !op.allow_broadcast() {
580        return Ok(summed);
581    }
582    let exact_extents = |value: ProgramValue| {
583        builder.resolved_extents(value).map(|extents| {
584            extents
585                .into_iter()
586                .map(|extent| match extent {
587                    ShapeExtent::Exact(expr) => Some(expr),
588                    ShapeExtent::UpperBound(_) | ShapeExtent::Unknown => None,
589                })
590                .collect::<Vec<_>>()
591        })
592    };
593    let input_extents = primal_inputs
594        .iter()
595        .map(|&value| exact_extents(value))
596        .collect::<std::result::Result<Vec<_>, _>>()?;
597    let output_extents = exact_extents(cotangent)?;
598
599    let subscripts = &op.subscripts;
600    for (axis, (&label, active)) in subscripts.inputs[active_idx]
601        .iter()
602        .zip(&input_extents[active_idx])
603        .enumerate()
604    {
605        let peer_operands = subscripts
606            .inputs
607            .iter()
608            .zip(&input_extents)
609            .enumerate()
610            .filter(|&(input_idx, _)| input_idx != active_idx)
611            .map(|(_, (labels, extents))| (labels.as_slice(), extents.as_slice()))
612            .chain(std::iter::once((
613                subscripts.output.as_slice(),
614                output_extents.as_slice(),
615            )));
616        let peers = peer_operands.flat_map(|(labels, extents)| {
617            labels
618                .iter()
619                .zip(extents)
620                .filter(move |&(&peer_label, _)| peer_label == label)
621                .map(move |(_, extent)| classify_dim_exprs(active.as_ref(), extent.as_ref()))
622        });
623        match broadcast_axis_reduce(peers) {
624            Ok(decision) => {
625                if decision.sums_label_out() {
626                    summed.insert(label);
627                }
628            }
629            Err(UndecidedBroadcastAxis) => {
630                return Err(semantic_einsum_unsupported(format!(
631                    "einsum VJP cannot decide whether axis {axis} of input {active_idx} \
632                     (extent {active:?}) was singleton-broadcast: another extent of the same \
633                     label is not provably equal to it or 1, and the gradient must sum the \
634                     cotangent over the axis exactly when it was broadcast"
635                )));
636            }
637        }
638    }
639    Ok(summed)
640}
641
642#[cfg(feature = "autodiff")]
643fn semantic_vjp_einsum_op(
644    primal_op: &EinsumExtensionOp,
645    active_idx: usize,
646    subscripts: EinsumSubscripts,
647    input_shapes: &[Vec<DimExpr>],
648) -> std::result::Result<EinsumExtensionOp, SemanticAdError> {
649    let plan_spec =
650        vjp_plan_spec_for_active(primal_op.plan_spec(), primal_op.input_count(), active_idx)?;
651    let sym_shapes: Vec<Vec<SymDim>> = input_shapes
652        .iter()
653        .enumerate()
654        .map(|(input_idx, shape)| {
655            let tensor_id = u64::MAX - input_idx as u64;
656            shape
657                .iter()
658                .enumerate()
659                .map(|(axis, dim)| match dim {
660                    DimExpr::Const(value) => SymDim::from(*value),
661                    _ => SymDim::tensor_axis(tensor_id, axis),
662                })
663                .collect()
664        })
665        .collect();
666    if let Some(concrete_shapes) = concrete_sym_shapes(&sym_shapes) {
667        let shape_refs: Vec<&[usize]> = concrete_shapes.iter().map(Vec::as_slice).collect();
668        let raw_subscripts = Subscripts::from(&subscripts);
669        let _tree = resolve_plan_spec(&plan_spec, &raw_subscripts, &shape_refs)
670            .map_err(|source| semantic_einsum_unsupported(source.to_string()))?;
671    }
672    Ok(EinsumExtensionOp::with_plan_spec_and_broadcast(
673        subscripts,
674        plan_spec,
675        primal_op.allow_broadcast(),
676    ))
677}
678
679#[cfg(feature = "autodiff")]
680fn semantic_value_shape(
681    builder: &SemanticProgramBuilder,
682    value: ProgramValue,
683) -> std::result::Result<Vec<DimExpr>, SemanticAdError> {
684    semantic_metadata_shape(builder.value_metadata(value)?)
685}
686
687#[cfg(feature = "autodiff")]
688fn semantic_metadata_shape(
689    metadata: &ProgramValueMetadata,
690) -> std::result::Result<Vec<DimExpr>, SemanticAdError> {
691    metadata
692        .shape()
693        .iter()
694        .map(|extent| {
695            extent.bound_expr().cloned().ok_or_else(|| {
696                semantic_einsum_unsupported(
697                    "einsum semantic AD requires a symbolic expression for every extent",
698                )
699            })
700        })
701        .collect()
702}
703
704#[cfg(feature = "autodiff")]
705fn semantic_conjugate_if_complex(
706    builder: &mut SemanticProgramBuilder,
707    value: ProgramValue,
708) -> std::result::Result<ProgramValue, SemanticAdError> {
709    if matches!(
710        builder.value_metadata(value)?.dtype(),
711        DType::C32 | DType::C64
712    ) {
713        Ok(builder.add_op(CoreSemanticOp::Conj, &[value])?[0])
714    } else {
715        Ok(value)
716    }
717}
718
719#[cfg(feature = "autodiff")]
720fn semantic_broadcast_einsum_vjp(
721    builder: &mut SemanticProgramBuilder,
722    cotangent: ProgramValue,
723    cotangent_labels: &[u32],
724    input_labels: &[u32],
725    shape: Vec<DimExpr>,
726) -> std::result::Result<ProgramValue, SemanticAdError> {
727    let dims = map_label_occurrences(cotangent_labels, input_labels).ok_or_else(|| {
728        semantic_einsum_unsupported(format!(
729            "einsum VJP cannot remap labels {cotangent_labels:?} into {input_labels:?}"
730        ))
731    })?;
732    // `shape` names program inputs because it came from value metadata; the
733    // broadcast names only its own inputs, so translate it and pass the referenced
734    // program inputs as shape references.
735    let mut inputs = vec![cotangent];
736    let shape = builder.translate_input_shape_payload(&shape, &mut inputs);
737    let broadcast = builder.add_op(CoreSemanticOp::BroadcastInDim { shape, dims }, &inputs)?[0];
738    semantic_project_repeated_labels(builder, broadcast, input_labels)
739}
740
741#[cfg(feature = "autodiff")]
742fn semantic_project_repeated_labels(
743    builder: &mut SemanticProgramBuilder,
744    cotangent: ProgramValue,
745    labels: &[u32],
746) -> std::result::Result<ProgramValue, SemanticAdError> {
747    let mut result = cotangent;
748    let mut first_axis_by_label = HashMap::new();
749    for (axis_b, label) in labels.iter().copied().enumerate() {
750        let Some(&axis_a) = first_axis_by_label.get(&label) else {
751            first_axis_by_label.insert(label, axis_b);
752            continue;
753        };
754        let extracted =
755            builder.add_op(CoreSemanticOp::ExtractDiag { axis_a, axis_b }, &[result])?[0];
756        result = builder.add_op(CoreSemanticOp::EmbedDiag { axis_a, axis_b }, &[extracted])?[0];
757    }
758    Ok(result)
759}
760
761#[cfg(feature = "autodiff")]
762fn semantic_sum_terms(
763    builder: &mut SemanticProgramBuilder,
764    terms: Vec<ProgramValue>,
765) -> std::result::Result<AdValue, SemanticAdError> {
766    let mut terms = terms.into_iter();
767    let Some(mut sum) = terms.next() else {
768        return Ok(AdValue::Absent);
769    };
770    for term in terms {
771        sum = builder.add_op(CoreSemanticOp::Add, &[sum, term])?[0];
772    }
773    Ok(AdValue::Value(sum))
774}
775
776#[cfg(feature = "autodiff")]
777fn semantic_einsum_payload(
778    op: &dyn ExtensionOp,
779    role: SemanticAdRuleRole,
780) -> std::result::Result<&EinsumExtensionOp, SemanticAdError> {
781    op.as_any()
782        .downcast_ref::<EinsumExtensionOp>()
783        .ok_or_else(|| SemanticAdError::Unsupported {
784            family_id: EINSUM_EXTENSION_FAMILY_ID,
785            role,
786            message: "einsum semantic AD received an incompatible payload".into(),
787        })
788}
789
790#[cfg(feature = "autodiff")]
791fn semantic_einsum_unsupported(message: impl Into<String>) -> SemanticAdError {
792    SemanticAdError::Unsupported {
793        family_id: EINSUM_EXTENSION_FAMILY_ID,
794        role: SemanticAdRuleRole::LinearTranspose,
795        message: message.into(),
796    }
797}
798
799#[cfg(feature = "autodiff")]
800fn vjp_plan_spec_for_active(
801    primal_plan: &EinsumPlanSpec,
802    input_count: usize,
803    active_idx: usize,
804) -> std::result::Result<EinsumPlanSpec, SemanticAdError> {
805    if active_idx >= input_count {
806        return Err(semantic_einsum_unsupported(format!(
807            "einsum VJP active input {active_idx} is outside {input_count} inputs"
808        )));
809    }
810
811    match primal_plan {
812        EinsumPlanSpec::Auto(options) => Ok(EinsumPlanSpec::Auto(options.clone())),
813        EinsumPlanSpec::LeftToRight => Ok(EinsumPlanSpec::LeftToRight),
814        EinsumPlanSpec::Path(path) => {
815            let pairs = jax_path_to_v1_pairs(path, input_count).map_err(|err| {
816                semantic_einsum_unsupported(format!(
817                    "failed to inherit einsum Path plan for VJP active input {active_idx}: {err}"
818                ))
819            })?;
820            derive_vjp_fixed_pairs(&pairs, input_count, active_idx).map(EinsumPlanSpec::FixedPairs)
821        }
822        EinsumPlanSpec::FixedPairs(pairs) => {
823            derive_vjp_fixed_pairs(pairs, input_count, active_idx).map(EinsumPlanSpec::FixedPairs)
824        }
825    }
826}
827
828#[cfg(feature = "autodiff")]
829fn derive_vjp_fixed_pairs(
830    primal_pairs: &[(usize, usize)],
831    input_count: usize,
832    active_idx: usize,
833) -> std::result::Result<Vec<(usize, usize)>, SemanticAdError> {
834    if input_count == 0 {
835        return Err(semantic_einsum_unsupported(
836            "einsum VJP cannot derive a plan for zero primal inputs",
837        ));
838    }
839    if active_idx >= input_count {
840        return Err(semantic_einsum_unsupported(format!(
841            "einsum VJP active input {active_idx} is outside {input_count} inputs"
842        )));
843    }
844    let required_steps = input_count.saturating_sub(1);
845    if primal_pairs.len() != required_steps {
846        return Err(semantic_einsum_unsupported(format!(
847            "einsum VJP cannot inherit explicit plan for active input {active_idx}: \
848             expected {required_steps} primal steps for {input_count} inputs, got {}",
849            primal_pairs.len()
850        )));
851    }
852    if input_count == 1 {
853        return Ok(Vec::new());
854    }
855
856    let children = fixed_pair_children(primal_pairs, input_count, active_idx)?;
857    let mut primal_to_vjp = vec![None; input_count];
858    let mut next_vjp_input = 1;
859    for (input_idx, slot) in primal_to_vjp.iter_mut().enumerate() {
860        if input_idx != active_idx {
861            *slot = Some(next_vjp_input);
862            next_vjp_input += 1;
863        }
864    }
865
866    let root = input_count + primal_pairs.len() - 1;
867    let mut pairs = Vec::with_capacity(required_steps);
868    let final_id = emit_vjp_adjoint(
869        root,
870        0,
871        &children,
872        input_count,
873        active_idx,
874        &primal_to_vjp,
875        &mut pairs,
876    )?;
877    let expected_final = input_count + pairs.len() - 1;
878    if final_id != expected_final || pairs.len() != required_steps {
879        return Err(semantic_einsum_unsupported(format!(
880            "einsum VJP plan derivation for active input {active_idx} produced an invalid \
881             tree: final id {final_id}, expected {expected_final}, steps {}",
882            pairs.len()
883        )));
884    }
885    Ok(pairs)
886}
887
888#[cfg(feature = "autodiff")]
889fn fixed_pair_children(
890    pairs: &[(usize, usize)],
891    input_count: usize,
892    active_idx: usize,
893) -> std::result::Result<Vec<Option<(usize, usize)>>, SemanticAdError> {
894    let mut live = vec![false; input_count + pairs.len()];
895    for slot in live.iter_mut().take(input_count) {
896        *slot = true;
897    }
898    let mut children = vec![None; input_count + pairs.len()];
899
900    for (step_idx, &(left, right)) in pairs.iter().enumerate() {
901        let next_idx = input_count + step_idx;
902        if left == right {
903            return Err(invalid_vjp_plan_error(
904                active_idx,
905                format!("pair ({left}, {right}) references the same operand"),
906            ));
907        }
908        if left >= next_idx || right >= next_idx {
909            return Err(invalid_vjp_plan_error(
910                active_idx,
911                format!("pair ({left}, {right}) references a non-existent operand"),
912            ));
913        }
914        if !live[left] || !live[right] {
915            return Err(invalid_vjp_plan_error(
916                active_idx,
917                format!("pair ({left}, {right}) references an operand that is no longer live"),
918            ));
919        }
920
921        live[left] = false;
922        live[right] = false;
923        live[next_idx] = true;
924        children[next_idx] = Some((left, right));
925    }
926
927    let live_count = live.iter().filter(|&&is_live| is_live).count();
928    if live_count != 1 {
929        return Err(invalid_vjp_plan_error(
930            active_idx,
931            format!("explicit plan leaves {live_count} live operands"),
932        ));
933    }
934
935    Ok(children)
936}
937
938#[cfg(feature = "autodiff")]
939fn emit_vjp_adjoint(
940    node: usize,
941    cotangent_id: usize,
942    children: &[Option<(usize, usize)>],
943    input_count: usize,
944    active_idx: usize,
945    primal_to_vjp: &[Option<usize>],
946    pairs: &mut Vec<(usize, usize)>,
947) -> std::result::Result<usize, SemanticAdError> {
948    if node < input_count {
949        return if node == active_idx {
950            Ok(cotangent_id)
951        } else {
952            Err(invalid_vjp_plan_error(
953                active_idx,
954                format!("adjoint walk reached inactive leaf {node}"),
955            ))
956        };
957    }
958
959    let (left, right) = children.get(node).and_then(|child| *child).ok_or_else(|| {
960        invalid_vjp_plan_error(active_idx, format!("missing children for node {node}"))
961    })?;
962    let left_has_active = subtree_contains_active(left, children, input_count, active_idx)?;
963    let right_has_active = subtree_contains_active(right, children, input_count, active_idx)?;
964    match (left_has_active, right_has_active) {
965        (true, false) => {
966            let sibling_id = emit_vjp_subtree(
967                right,
968                children,
969                input_count,
970                active_idx,
971                primal_to_vjp,
972                pairs,
973            )?;
974            let next = push_vjp_pair(cotangent_id, sibling_id, input_count, pairs);
975            emit_vjp_adjoint(
976                left,
977                next,
978                children,
979                input_count,
980                active_idx,
981                primal_to_vjp,
982                pairs,
983            )
984        }
985        (false, true) => {
986            let sibling_id = emit_vjp_subtree(
987                left,
988                children,
989                input_count,
990                active_idx,
991                primal_to_vjp,
992                pairs,
993            )?;
994            let next = push_vjp_pair(cotangent_id, sibling_id, input_count, pairs);
995            emit_vjp_adjoint(
996                right,
997                next,
998                children,
999                input_count,
1000                active_idx,
1001                primal_to_vjp,
1002                pairs,
1003            )
1004        }
1005        (true, true) => Err(invalid_vjp_plan_error(
1006            active_idx,
1007            format!("both children of node {node} contain the active input"),
1008        )),
1009        (false, false) => Err(invalid_vjp_plan_error(
1010            active_idx,
1011            format!("neither child of node {node} contains the active input"),
1012        )),
1013    }
1014}
1015
1016#[cfg(feature = "autodiff")]
1017fn emit_vjp_subtree(
1018    node: usize,
1019    children: &[Option<(usize, usize)>],
1020    input_count: usize,
1021    active_idx: usize,
1022    primal_to_vjp: &[Option<usize>],
1023    pairs: &mut Vec<(usize, usize)>,
1024) -> std::result::Result<usize, SemanticAdError> {
1025    if node < input_count {
1026        return primal_to_vjp[node].ok_or_else(|| {
1027            invalid_vjp_plan_error(
1028                active_idx,
1029                format!("sibling subtree unexpectedly reached active leaf {node}"),
1030            )
1031        });
1032    }
1033
1034    let (left, right) = children.get(node).and_then(|child| *child).ok_or_else(|| {
1035        invalid_vjp_plan_error(active_idx, format!("missing children for node {node}"))
1036    })?;
1037    let left_id = emit_vjp_subtree(
1038        left,
1039        children,
1040        input_count,
1041        active_idx,
1042        primal_to_vjp,
1043        pairs,
1044    )?;
1045    let right_id = emit_vjp_subtree(
1046        right,
1047        children,
1048        input_count,
1049        active_idx,
1050        primal_to_vjp,
1051        pairs,
1052    )?;
1053    Ok(push_vjp_pair(left_id, right_id, input_count, pairs))
1054}
1055
1056#[cfg(feature = "autodiff")]
1057fn push_vjp_pair(
1058    left: usize,
1059    right: usize,
1060    n_vjp_inputs: usize,
1061    pairs: &mut Vec<(usize, usize)>,
1062) -> usize {
1063    pairs.push((left, right));
1064    n_vjp_inputs + pairs.len() - 1
1065}
1066
1067#[cfg(feature = "autodiff")]
1068fn subtree_contains_active(
1069    node: usize,
1070    children: &[Option<(usize, usize)>],
1071    input_count: usize,
1072    active_idx: usize,
1073) -> std::result::Result<bool, SemanticAdError> {
1074    if node < input_count {
1075        return Ok(node == active_idx);
1076    }
1077    let (left, right) = children.get(node).and_then(|child| *child).ok_or_else(|| {
1078        invalid_vjp_plan_error(active_idx, format!("missing children for node {node}"))
1079    })?;
1080    Ok(
1081        subtree_contains_active(left, children, input_count, active_idx)?
1082            || subtree_contains_active(right, children, input_count, active_idx)?,
1083    )
1084}
1085
1086#[cfg(feature = "autodiff")]
1087fn invalid_vjp_plan_error(active_idx: usize, reason: String) -> SemanticAdError {
1088    semantic_einsum_unsupported(format!(
1089        "einsum VJP cannot inherit explicit plan for active input {active_idx}: {reason}"
1090    ))
1091}
1092
1093#[cfg(feature = "autodiff")]
1094fn concrete_sym_shapes(shapes: &[Vec<SymDim>]) -> Option<Vec<Vec<usize>>> {
1095    shapes
1096        .iter()
1097        .map(|shape| shape.iter().map(SymDim::constant_value).collect())
1098        .collect()
1099}
1100
1101define_extension_runtime! {
1102    runtime = EinsumRuntime,
1103    family_id = EINSUM_EXTENSION_FAMILY_ID,
1104    op_type = EinsumExtensionOp,
1105    execute_in_session = execute_einsum_extension_reads_in_session,
1106    session_supported = einsum_session_supported,
1107}
1108
1109pub(crate) fn execute_einsum_extension_session_reads(
1110    op: &EinsumExtensionOp,
1111    inputs: &[TensorRead<'_>],
1112    ctx: &mut ExtensionExecutionContext<'_, dyn Engine + '_>,
1113) -> tenferro_tensor::Result<Vec<Tensor>> {
1114    if inputs.is_empty() {
1115        return Err(tenferro_tensor::Error::invalid_argument(
1116            "einsum_extension",
1117            "inputs",
1118            "einsum requires at least one input tensor",
1119        ));
1120    }
1121
1122    let shapes: Vec<Vec<usize>> = inputs.iter().map(|input| input.shape().to_vec()).collect();
1123    let shape_refs: Vec<&[usize]> = shapes.iter().map(Vec::as_slice).collect();
1124    let subs = Subscripts::from(op.subscripts());
1125    let tree = cached_runtime_tree(ctx, op.subscripts(), op.plan_spec(), &shapes, || {
1126        resolve_plan_spec(op.plan_spec(), &subs, &shape_refs)
1127    })?;
1128    let output = crate::eager::eager_einsum_exec_read(ctx.backend_mut(), inputs, &tree)?;
1129    Ok(vec![output])
1130}
1131
1132/// Adapter from the scheduler/`apply_eager` borrowed-session shape to the
1133/// eager session executor. Reuses the existing forward kernel; reimplementing
1134/// it here is explicitly out of scope for issue #1665.
1135fn execute_einsum_extension_reads_in_session(
1136    op: &EinsumExtensionOp,
1137    session: &mut dyn Engine,
1138    caches: &mut tenferro_runtime::ExtensionCacheStore,
1139    inputs: &[TensorRead<'_>],
1140) -> tenferro_tensor::Result<Vec<Tensor>> {
1141    let mut ctx = ExtensionExecutionContext::new(session, caches);
1142    execute_einsum_extension_session_reads(op, inputs, &mut ctx)
1143}
1144
1145fn einsum_session_supported<B: tenferro_tensor::Engine + 'static>(_op: &EinsumExtensionOp) -> bool {
1146    // The session executor runs the same forward kernel on any backend session
1147    // below (the einsum execution only needs elementwise/dot session ops), so
1148    // CPU and CUDA sessions both qualify for `apply_eager`'s native path.
1149    let type_id = std::any::TypeId::of::<B>();
1150    type_id == std::any::TypeId::of::<tenferro_cpu::CpuEngine>() || {
1151        #[cfg(feature = "cuda")]
1152        {
1153            type_id == std::any::TypeId::of::<tenferro_gpu::cuda::CudaEngine>()
1154        }
1155        #[cfg(not(feature = "cuda"))]
1156        {
1157            false
1158        }
1159    }
1160}
1161
1162#[derive(Clone)]
1163struct RuntimeTreeCacheKeyData {
1164    subscripts: EinsumSubscripts,
1165    shapes: Vec<Vec<usize>>,
1166    plan_spec: EinsumPlanSpec,
1167}
1168
1169impl RuntimeTreeCacheKeyData {
1170    fn new(
1171        subscripts: &EinsumSubscripts,
1172        shapes: &[Vec<usize>],
1173        plan_spec: &EinsumPlanSpec,
1174    ) -> Self {
1175        Self {
1176            subscripts: subscripts.clone(),
1177            shapes: shapes.to_vec(),
1178            plan_spec: plan_spec.clone(),
1179        }
1180    }
1181
1182    fn matches_runtime_tree(
1183        &self,
1184        subscripts: &EinsumSubscripts,
1185        shapes: &[Vec<usize>],
1186        plan_spec: &EinsumPlanSpec,
1187    ) -> bool {
1188        self.subscripts == *subscripts
1189            && self.shapes.as_slice() == shapes
1190            && plan_specs_equal(&self.plan_spec, plan_spec)
1191    }
1192
1193    fn retained_bytes(&self) -> usize {
1194        saturating_sum([
1195            einsum_subscripts_retained_bytes(&self.subscripts),
1196            saturating_sum(self.shapes.iter().map(vec_retained_bytes)),
1197            plan_spec_retained_bytes(&self.plan_spec),
1198        ])
1199    }
1200}
1201
1202struct CachedRuntimeTree {
1203    key_data: RuntimeTreeCacheKeyData,
1204    tree: Arc<ContractionTree>,
1205}
1206
1207fn cached_runtime_tree<B: Engine + ?Sized>(
1208    ctx: &mut ExtensionExecutionContext<'_, B>,
1209    subscripts: &EinsumSubscripts,
1210    plan_spec: &EinsumPlanSpec,
1211    shapes: &[Vec<usize>],
1212    build: impl FnOnce() -> EinsumResult<ContractionTree>,
1213) -> tenferro_tensor::Result<Arc<ContractionTree>> {
1214    let plan_hash = plan_spec_hash(plan_spec);
1215    let key = ExtensionCacheKey::new(
1216        EINSUM_EXTENSION_FAMILY_ID,
1217        EINSUM_RUNTIME_PLANS_CACHE,
1218        runtime_tree_cache_discriminator(subscripts, shapes, plan_hash),
1219    );
1220    if let Some(cached) = ctx.caches_mut().get::<CachedRuntimeTree>(&key) {
1221        let key_data = &cached.key_data;
1222        if key_data.matches_runtime_tree(subscripts, shapes, plan_spec) {
1223            return Ok(Arc::clone(&cached.tree));
1224        }
1225    }
1226
1227    let tree = Arc::new(build().map_err(einsum_runtime_error)?);
1228    let key_data = RuntimeTreeCacheKeyData::new(subscripts, shapes, plan_spec);
1229    let retained_bytes = saturating_sum([
1230        key_data.retained_bytes(),
1231        tree.retained_bytes_for_cache_stats(),
1232    ]);
1233    ctx.caches_mut().put(
1234        key,
1235        CachedRuntimeTree {
1236            key_data,
1237            tree: Arc::clone(&tree),
1238        },
1239        retained_bytes,
1240    );
1241    Ok(tree)
1242}
1243
1244fn einsum_runtime_error(error: EinsumError) -> tenferro_tensor::Error {
1245    error.into_tensor_error("einsum_extension")
1246}
1247
1248fn runtime_tree_cache_discriminator(
1249    subscripts: &EinsumSubscripts,
1250    shapes: &[Vec<usize>],
1251    plan_hash: u64,
1252) -> u64 {
1253    let mut hasher = DefaultHasher::new();
1254    subscripts.hash(&mut hasher);
1255    shapes.hash(&mut hasher);
1256    plan_hash.hash(&mut hasher);
1257    hasher.finish()
1258}
1259
1260fn plan_spec_hash(plan_spec: &EinsumPlanSpec) -> u64 {
1261    let mut hasher = DefaultHasher::new();
1262    hash_einsum_plan_spec(plan_spec, &mut hasher);
1263    hasher.finish()
1264}
1265
1266fn plan_spec_retained_bytes(plan_spec: &EinsumPlanSpec) -> usize {
1267    match plan_spec {
1268        EinsumPlanSpec::Auto(options) => saturating_sum([
1269            std::mem::size_of::<EinsumPlanSpec>(),
1270            vec_retained_bytes(&options.betas),
1271        ]),
1272        EinsumPlanSpec::LeftToRight => std::mem::size_of::<EinsumPlanSpec>(),
1273        EinsumPlanSpec::Path(path) | EinsumPlanSpec::FixedPairs(path) => saturating_sum([
1274            std::mem::size_of::<EinsumPlanSpec>(),
1275            vec_retained_bytes(path),
1276        ]),
1277    }
1278}
1279
1280fn promote_dtypes(dtypes: impl IntoIterator<Item = DType>) -> DType {
1281    dtypes
1282        .into_iter()
1283        .reduce(tenferro_tensor::validate::promote_dtype)
1284        .unwrap_or(DType::F64)
1285}
1286
1287#[cfg(test)]
1288mod tests;