Skip to main content

tenferro_linalg/ad/
semantic.rs

1// Solve residual policy reference: PyTorch 8dd3b763, FunctionsManual.cpp,
2// linalg_solve_backward (saved LU/pivots for gB, saved X for gA).
3// Emission below reuses tenferro's existing prepared-solve and cotangent helpers.
4use std::collections::{HashMap, HashSet};
5use std::sync::Arc;
6
7use computegraph::traits::GraphOperation;
8use computegraph::types::{LocalValueId, OperationRole, ValueKey, ValueRef};
9use tenferro_ad::semantic_extension::{
10    AdValue, ResidualSpec, SemanticAdError, SemanticAdRuleRole, SemanticExtensionRegistryError,
11    SemanticExtensionRuleSet, SemanticLinearTransposeRequest, SemanticLinearTransposeRule,
12    SemanticLinearizeRequest, SemanticLinearizeResult, SemanticLinearizeRule,
13};
14use tenferro_ops::ad::PrimitiveRuleBuilder;
15use tenferro_ops::ad::PrimitiveTransposeInput;
16use tenferro_ops::dim_expr::DimExpr;
17use tenferro_ops::input_key::TensorInputKey;
18use tenferro_ops::shape_extent::ShapeExtent;
19use tenferro_ops::std_tensor_op::StdTensorOp;
20use tenferro_ops::{ShapeGuardContext, SymDim, TensorMeta};
21use tenferro_runtime::program::{
22    CoreSemanticOp, ProgramValue, ProgramValueMetadata, SemanticProgramBuilder,
23};
24
25use super::LinalgAdRule;
26use crate::extension::{LinalgExtensionOp, LinalgOp};
27use crate::LINALG_EXTENSION_FAMILY_ID;
28
29/// Return the linalg semantic-program AD rule set.
30///
31/// # Errors
32///
33/// Returns [`SemanticExtensionRegistryError::MalformedFamilyId`] if the linalg
34/// family identifier is invalid, or
35/// [`SemanticExtensionRegistryError::DuplicateRule`] if a semantic rule role
36/// is already registered.
37///
38/// # Examples
39///
40/// ```rust
41/// let rules = tenferro_linalg::semantic_ad_rules().unwrap();
42/// assert!(rules
43///     .lookup_linearize(tenferro_linalg::LINALG_EXTENSION_FAMILY_ID)
44///     .is_some());
45/// assert!(rules
46///     .lookup_linear_transpose(tenferro_linalg::LINALG_EXTENSION_FAMILY_ID)
47///     .is_some());
48/// assert!(rules
49///     .lookup_primal_vjp(tenferro_linalg::LINALG_EXTENSION_FAMILY_ID)
50///     .is_none());
51/// ```
52pub fn semantic_ad_rules() -> Result<SemanticExtensionRuleSet, SemanticExtensionRegistryError> {
53    SemanticExtensionRuleSet::new()
54        .with_linearize(Arc::new(LinalgAdRule))?
55        .with_linear_transpose(Arc::new(LinalgAdRule))
56}
57
58impl SemanticLinearizeRule for LinalgAdRule {
59    fn family_id(&self) -> &'static str {
60        LINALG_EXTENSION_FAMILY_ID
61    }
62
63    fn linearize(
64        &self,
65        request: SemanticLinearizeRequest<'_>,
66        builder: &mut SemanticProgramBuilder,
67    ) -> Result<SemanticLinearizeResult, SemanticAdError> {
68        let op = semantic_linalg_op(request.op(), SemanticAdRuleRole::Linearize)?;
69        if matches!(op.op(), LinalgOp::HouseholderQrThinQ { .. }) {
70            return Err(SemanticAdError::Unsupported {
71                family_id: LINALG_EXTENSION_FAMILY_ID,
72                role: SemanticAdRuleRole::Linearize,
73                message: "internal thin-Q residual is not differentiable".into(),
74            });
75        }
76        if matches!(op.op(), LinalgOp::LuFactor | LinalgOp::SvdFull) {
77            // These value-only operations can appear inside a differentiable
78            // composite (for example, `solve` uses `LuFactor` outputs as
79            // prepared-solve residuals).  Returning absent tangents lets the
80            // composite rule differentiate through the primal inputs without
81            // pretending that the factorization outputs are differentiable.
82            // A caller requesting those outputs directly still observes that
83            // no derivative output was produced, while VJP rejects their
84            // unsupported transpose below.
85            return Ok(SemanticLinearizeResult::new(
86                std::iter::repeat_n(AdValue::Absent, request.primal_outputs().len()),
87                [],
88            ));
89        }
90        let legacy = LegacyInvocation::new(
91            request.primal_inputs(),
92            request.primal_outputs(),
93            request.active_outputs(),
94            builder,
95        )?;
96        let seed_values: Vec<_> = request
97            .tangent_inputs()
98            .iter()
99            .copied()
100            .map(AdValue::value)
101            .collect();
102        let tangent_inputs: Vec<_> = seed_values
103            .iter()
104            .enumerate()
105            .map(|(index, value)| value.map(|_| index))
106            .collect();
107        let mut emitted = SemanticRuleBuilder::with_seeds(
108            &seed_values,
109            &legacy.external_values,
110            &legacy.shape_sources,
111            builder,
112            SemanticAdRuleRole::Linearize,
113        );
114        let tangent_outputs = LinalgAdRule
115            .linearize(
116                op,
117                &mut emitted,
118                &legacy.input_keys,
119                &legacy.output_keys,
120                &tangent_inputs,
121                &mut legacy.context.clone(),
122            )
123            .map_err(|error| legacy_error(SemanticAdRuleRole::Linearize, error))?;
124        let locals = emitted.finish()?;
125        Ok(SemanticLinearizeResult::new(
126            tangent_outputs.into_iter().map(|value| {
127                value
128                    .and_then(|local| locals.get(local).copied().flatten())
129                    .map_or(AdValue::Absent, AdValue::Value)
130            }),
131            [],
132        ))
133    }
134}
135
136impl SemanticLinearTransposeRule for LinalgAdRule {
137    fn family_id(&self) -> &'static str {
138        LINALG_EXTENSION_FAMILY_ID
139    }
140
141    fn residual_mask(&self) -> ResidualSpec {
142        // The linalg family is one rule across solve/eigen/qr ops whose
143        // transposes collectively read every operand: triangular solve reads
144        // both inputs plus the solution output, and the linearize+fragment
145        // path can consume any input/output value (svd reads outputs 0-2,
146        // eigh/qr read outputs 0-1).
147        // ponytail: family-level mask; per-op masks would require splitting
148        // `LinalgAdRule` per op.
149        ResidualSpec::all_inputs().with_all_outputs()
150    }
151
152    fn linear_transpose(
153        &self,
154        request: SemanticLinearTransposeRequest<'_>,
155        builder: &mut SemanticProgramBuilder,
156    ) -> Result<Box<[AdValue]>, SemanticAdError> {
157        let primal_inputs = (0..request.primal_input_count())
158            .map(|index| request.primal_input_value(index))
159            .collect::<Result<Vec<_>, _>>()?;
160        let primal_outputs = (0..request.primal_output_count())
161            .map(|index| request.primal_output_value(index))
162            .collect::<Result<Vec<_>, _>>()?;
163        let op = semantic_linalg_op(request.op(), SemanticAdRuleRole::LinearTranspose)?;
164        match op.op() {
165            LinalgOp::TriangularSolve {
166                left_side,
167                lower,
168                transpose_a,
169                unit_diagonal,
170            } => semantic_triangular_solve_transpose(
171                &primal_inputs,
172                &primal_outputs,
173                request.cotangent_outputs(),
174                request.active_inputs(),
175                request.residual_mask(),
176                builder,
177                left_side,
178                lower,
179                transpose_a,
180                unit_diagonal,
181            ),
182            LinalgOp::LuSolvePrepared {
183                transpose_a,
184                conjugate_a,
185            } => {
186                let active_inputs = lu_solve_prepared_transpose_active_inputs(
187                    request.active_inputs(),
188                    SemanticAdRuleRole::LinearTranspose,
189                )?;
190                let mut result = vec![AdValue::Absent; 4];
191                let (a_cotangent, b_cotangent) = semantic_prepared_solve_transpose(
192                    builder,
193                    SemanticPreparedSolve {
194                        op: "lu_solve_prepared",
195                        a: primal_inputs[0],
196                        packed_lu: primal_inputs[1],
197                        pivots: primal_inputs[2],
198                        solution: primal_outputs.first().copied(),
199                    },
200                    request.cotangent_outputs(),
201                    (active_inputs[0], active_inputs[3]),
202                    transpose_a,
203                    conjugate_a,
204                )?;
205                result[0] = a_cotangent;
206                result[3] = b_cotangent;
207                Ok(result.into_boxed_slice())
208            }
209            // The fused solve saves its own factors as outputs 1 and 2, so the
210            // adjoint solve reuses them instead of refactoring `a`. The factor
211            // outputs carry no cotangent (see the `LuFactor` linearize rule).
212            LinalgOp::LuFactorSolve => {
213                let active_inputs = request.active_inputs();
214                let (Some(&a_active), Some(&b_active), Some(&packed_lu), Some(&pivots)) = (
215                    active_inputs.first(),
216                    active_inputs.get(1),
217                    primal_outputs.get(1),
218                    primal_outputs.get(2),
219                ) else {
220                    return Err(semantic_internal(
221                        SemanticAdRuleRole::LinearTranspose,
222                        "lu_factor_solve transpose expected inputs (a, b) and outputs (x, lu, pivots)",
223                    ));
224                };
225                let (a_cotangent, b_cotangent) = semantic_prepared_solve_transpose(
226                    builder,
227                    SemanticPreparedSolve {
228                        op: "lu_factor_solve",
229                        a: primal_inputs[0],
230                        packed_lu,
231                        pivots,
232                        solution: primal_outputs.first().copied(),
233                    },
234                    request.cotangent_outputs(),
235                    (a_active, b_active),
236                    false,
237                    false,
238                )?;
239                Ok(vec![a_cotangent, b_cotangent].into_boxed_slice())
240            }
241            LinalgOp::FullPivLuSolve { .. } => semantic_custom_transpose(
242                request.op(),
243                &primal_inputs,
244                &primal_outputs,
245                request.cotangent_outputs(),
246                request.active_inputs(),
247                builder,
248                SemanticAdRuleRole::LinearTranspose,
249            ),
250            LinalgOp::Solve => semantic_custom_transpose(
251                request.op(),
252                &primal_inputs,
253                &primal_outputs,
254                request.cotangent_outputs(),
255                request.active_inputs(),
256                builder,
257                SemanticAdRuleRole::LinearTranspose,
258            ),
259            LinalgOp::LuFactor | LinalgOp::SvdFull | LinalgOp::HouseholderQrThinQ { .. } => {
260                Err(SemanticAdError::Unsupported {
261                    family_id: LINALG_EXTENSION_FAMILY_ID,
262                    role: SemanticAdRuleRole::LinearTranspose,
263                    message: format!("semantic linear transpose is unsupported for {:?}", op.op()),
264                })
265            }
266            _ => semantic_linearized_transpose(
267                request.op(),
268                &primal_inputs,
269                &primal_outputs,
270                request.cotangent_outputs(),
271                request.active_inputs(),
272                builder,
273            ),
274        }
275    }
276}
277
278fn lu_solve_prepared_transpose_active_inputs(
279    active_inputs: &[bool],
280    role: SemanticAdRuleRole,
281) -> Result<[bool; 4], SemanticAdError> {
282    let active_inputs: [bool; 4] = active_inputs.try_into().map_err(|_| {
283        semantic_internal(
284            role,
285            format!(
286                "lu_solve_prepared semantic transpose expected 4 active inputs, got {}",
287                active_inputs.len()
288            ),
289        )
290    })?;
291    // Packed LU may be an active intermediate when `solve` lowers through
292    // factorization. Pivot and parity slots remain non-cotangent-producing
293    // residuals.
294    Ok([active_inputs[0], false, false, active_inputs[3]])
295}
296
297/// Primal values of one prepared LU solve `op(A) x = b`.
298struct SemanticPreparedSolve {
299    op: &'static str,
300    a: ProgramValue,
301    packed_lu: ProgramValue,
302    pivots: ProgramValue,
303    solution: Option<ProgramValue>,
304}
305
306/// Cotangents `(gA, gB)` of a prepared LU solve `op(A) x = b`.
307///
308/// `gB = op(A)^{-H} gX` is one prepared solve against the saved factors with
309/// both flags flipped, and `gA = -op(gB x^H)` reads the saved solution
310/// (PyTorch `linalg_solve_backward`).
311fn semantic_prepared_solve_transpose(
312    builder: &mut SemanticProgramBuilder,
313    primal: SemanticPreparedSolve,
314    cotangent_outputs: &[AdValue],
315    (a_active, b_active): (bool, bool),
316    transpose_a: bool,
317    conjugate_a: bool,
318) -> Result<(AdValue, AdValue), SemanticAdError> {
319    let Some(ct) = cotangent_outputs.first().copied().and_then(AdValue::value) else {
320        return Ok((AdValue::Absent, AdValue::Absent));
321    };
322    if !a_active && !b_active {
323        return Ok((AdValue::Absent, AdValue::Absent));
324    }
325    let rhs_cotangent = builder.add_extension(
326        Arc::new(LinalgExtensionOp::new(LinalgOp::LuSolvePrepared {
327            transpose_a: !transpose_a,
328            conjugate_a: !conjugate_a,
329        })),
330        &[primal.a, primal.packed_lu, primal.pivots, ct],
331    )?[0];
332    let a_cotangent = if a_active {
333        let solution = primal.solution.ok_or_else(|| {
334            semantic_internal(
335                SemanticAdRuleRole::LinearTranspose,
336                format!("{} transpose requires its primal solution", primal.op),
337            )
338        })?;
339        let rank = builder.value_metadata(primal.a)?.shape().len();
340        let matrix_cotangent = semantic_solve_matrix_cotangent(
341            builder,
342            rhs_cotangent,
343            solution,
344            true,
345            transpose_a,
346            rank,
347        )?;
348        AdValue::Value(if conjugate_a {
349            conjugate_if_complex(builder, matrix_cotangent)?
350        } else {
351            matrix_cotangent
352        })
353    } else {
354        AdValue::Absent
355    };
356    let b_cotangent = if b_active {
357        AdValue::Value(rhs_cotangent)
358    } else {
359        AdValue::Absent
360    };
361    Ok((a_cotangent, b_cotangent))
362}
363
364#[allow(clippy::too_many_arguments)]
365fn semantic_triangular_solve_transpose(
366    primal_inputs: &[ProgramValue],
367    primal_outputs: &[ProgramValue],
368    cotangent_outputs: &[AdValue],
369    active_inputs: &[bool],
370    residual_mask: ResidualSpec,
371    builder: &mut SemanticProgramBuilder,
372    left_side: bool,
373    lower: bool,
374    transpose_a: bool,
375    unit_diagonal: bool,
376) -> Result<Box<[AdValue]>, SemanticAdError> {
377    let role = SemanticAdRuleRole::LinearTranspose;
378    if primal_inputs.len() != 2
379        || primal_outputs.len() != 1
380        || cotangent_outputs.len() != 1
381        || active_inputs.len() != 2
382    {
383        return Err(semantic_internal(
384            role,
385            "triangular_solve semantic transpose received malformed arity",
386        ));
387    }
388    let Some(ct) = cotangent_outputs.first().copied().and_then(AdValue::value) else {
389        return Ok(vec![AdValue::Absent; 2].into_boxed_slice());
390    };
391
392    let mut result = vec![AdValue::Absent; 2];
393    if !active_inputs[0] && !active_inputs[1] {
394        return Ok(result.into_boxed_slice());
395    }
396
397    let matrix_rank = builder.value_metadata(primal_inputs[0])?.shape().len();
398    let rhs_rank = builder.value_metadata(primal_inputs[1])?.shape().len();
399    if matrix_rank < 2 || rhs_rank < 2 {
400        return Err(semantic_internal(
401            role,
402            "triangular_solve semantic transpose expects matrix operands",
403        ));
404    }
405    if matrix_rank != rhs_rank {
406        return Err(semantic_internal(
407            role,
408            "triangular_solve semantic transpose expects equal-rank operands",
409        ));
410    }
411
412    let conjugated_a = conjugate_if_complex(builder, primal_inputs[0])?;
413    debug_assert!(
414        residual_mask.declares_input(0),
415        "linalg triangular_solve transpose read primal input 0 as a tensor operand but the \
416         residual mask does not declare it; declare it in the linalg rule's residual mask"
417    );
418    let rhs_cotangent = builder.add_extension(
419        Arc::new(LinalgExtensionOp::new(LinalgOp::TriangularSolve {
420            left_side,
421            lower,
422            transpose_a: !transpose_a,
423            unit_diagonal,
424        })),
425        &[conjugated_a, ct],
426    )?[0];
427
428    if active_inputs[1] {
429        result[1] = AdValue::Value(rhs_cotangent);
430    }
431    if active_inputs[0] {
432        debug_assert!(
433            residual_mask.declares_output(0),
434            "linalg triangular_solve transpose read primal output 0 as a tensor operand but the \
435             residual mask does not declare it; declare it in the linalg rule's residual mask"
436        );
437        let matrix_cotangent = semantic_solve_matrix_cotangent(
438            builder,
439            rhs_cotangent,
440            primal_outputs[0],
441            left_side,
442            transpose_a,
443            matrix_rank,
444        )?;
445        let k = if unit_diagonal {
446            if lower {
447                -1
448            } else {
449                1
450            }
451        } else {
452            0
453        };
454        let projected = if lower {
455            builder.add_op(CoreSemanticOp::Tril { k }, &[matrix_cotangent])?[0]
456        } else {
457            builder.add_op(CoreSemanticOp::Triu { k }, &[matrix_cotangent])?[0]
458        };
459        result[0] = AdValue::Value(projected);
460    }
461
462    Ok(result.into_boxed_slice())
463}
464
465fn semantic_linearized_transpose(
466    op: &dyn tenferro_ad::extension::ExtensionOp,
467    primal_inputs: &[ProgramValue],
468    primal_outputs: &[ProgramValue],
469    cotangent_outputs: &[AdValue],
470    active_inputs: &[bool],
471    builder: &mut SemanticProgramBuilder,
472) -> Result<Box<[AdValue]>, SemanticAdError> {
473    let legacy = LegacyInvocation::new(
474        primal_inputs,
475        primal_outputs,
476        &cotangent_outputs
477            .iter()
478            .map(|value| matches!(value, AdValue::Value(_)))
479            .collect::<Vec<_>>(),
480        builder,
481    )?;
482    let tangent_inputs: Vec<_> = active_inputs
483        .iter()
484        .copied()
485        .enumerate()
486        .map(|(index, active)| active.then_some(index))
487        .collect();
488    let mut fragment = SemanticLinearFragmentBuilder::with_seed_count(primal_inputs.len());
489    let tangent_outputs = LinalgAdRule
490        .linearize(
491            op,
492            &mut fragment,
493            &legacy.input_keys,
494            &legacy.output_keys,
495            &tangent_inputs,
496            &mut legacy.context.clone(),
497        )
498        .map_err(|error| legacy_error(SemanticAdRuleRole::LinearTranspose, error))?;
499    fragment.transpose_linear_fragment(
500        &tangent_outputs,
501        cotangent_outputs,
502        active_inputs,
503        &legacy.external_values,
504        &legacy.shape_sources,
505        builder,
506    )
507}
508
509fn semantic_custom_transpose(
510    op: &dyn tenferro_ad::extension::ExtensionOp,
511    primal_inputs: &[ProgramValue],
512    primal_outputs: &[ProgramValue],
513    cotangent_outputs: &[AdValue],
514    active_inputs: &[bool],
515    builder: &mut SemanticProgramBuilder,
516    role: SemanticAdRuleRole,
517) -> Result<Box<[AdValue]>, SemanticAdError> {
518    let legacy = LegacyInvocation::new(
519        primal_inputs,
520        primal_outputs,
521        &vec![true; primal_outputs.len()],
522        builder,
523    )?;
524    let seed_values: Vec<_> = cotangent_outputs
525        .iter()
526        .copied()
527        .map(AdValue::value)
528        .collect();
529    let cotangents: Vec<_> = seed_values
530        .iter()
531        .enumerate()
532        .map(|(index, value)| value.map(|_| index))
533        .collect();
534    let transpose_inputs: Vec<_> = legacy
535        .input_keys
536        .iter()
537        .cloned()
538        .map(PrimitiveTransposeInput::Residual)
539        .collect();
540    let mut emitted = SemanticRuleBuilder::with_seeds(
541        &seed_values,
542        &legacy.external_values,
543        &legacy.shape_sources,
544        builder,
545        role,
546    );
547    let cotangent_inputs = LinalgAdRule
548        .linear_transpose(
549            op,
550            &mut emitted,
551            &cotangents,
552            &transpose_inputs,
553            active_inputs,
554            &mut legacy.context.clone(),
555        )
556        .map_err(|error| legacy_error(role, error))?;
557    let locals = emitted.finish()?;
558    Ok(cotangent_inputs
559        .into_iter()
560        .map(|value| {
561            value
562                .and_then(|local| locals.get(local).copied().flatten())
563                .map_or(AdValue::Absent, AdValue::Value)
564        })
565        .collect())
566}
567
568struct LegacyInvocation {
569    context: ShapeGuardContext,
570    input_keys: Vec<ValueKey<StdTensorOp>>,
571    output_keys: Vec<ValueKey<StdTensorOp>>,
572    external_values: HashMap<ValueKey<StdTensorOp>, ProgramValue>,
573    shape_sources: Vec<ProgramValue>,
574}
575
576impl LegacyInvocation {
577    fn new(
578        primal_inputs: &[ProgramValue],
579        primal_outputs: &[ProgramValue],
580        active_outputs: &[bool],
581        builder: &SemanticProgramBuilder,
582    ) -> Result<Self, SemanticAdError> {
583        let values: Vec<_> = primal_inputs
584            .iter()
585            .chain(primal_outputs)
586            .copied()
587            .collect();
588        let metadata: Vec<_> = values
589            .iter()
590            .copied()
591            .map(|value| builder.value_metadata(value).cloned())
592            .collect::<Result<_, _>>()?;
593        let symbolic_inputs = synthetic_input_shapes(&metadata);
594        let symbolic_input_refs: Vec<_> = symbolic_inputs.iter().map(Vec::as_slice).collect();
595        let mut context = ShapeGuardContext::default();
596        let mut external_values = HashMap::new();
597        let keys: Vec<_> = values
598            .iter()
599            .copied()
600            .enumerate()
601            .map(|(index, value)| {
602                let key = ValueKey::Input(TensorInputKey::User {
603                    id: u64::try_from(index + 1).expect("small semantic AD invocation"),
604                });
605                context.insert_metadata(
606                    key.clone(),
607                    legacy_metadata(&metadata[index], &symbolic_input_refs),
608                );
609                external_values.insert(key.clone(), value);
610                key
611            })
612            .collect();
613        let input_count = primal_inputs.len();
614        let input_keys = keys[..input_count].to_vec();
615        let output_keys = keys[input_count..].to_vec();
616        let active_values: HashSet<_> = output_keys
617            .iter()
618            .zip(active_outputs)
619            .filter(|(_, active)| **active)
620            .map(|(key, _)| key.clone())
621            .collect();
622        context = context.with_linearize_active_values(Arc::new(active_values));
623        Ok(Self {
624            context,
625            input_keys,
626            output_keys,
627            external_values,
628            shape_sources: values,
629        })
630    }
631}
632
633fn legacy_metadata(metadata: &ProgramValueMetadata, input_shapes: &[&[SymDim]]) -> TensorMeta {
634    let extents = metadata
635        .shape()
636        .iter()
637        .cloned()
638        .map(|extent| extent.map(|dim| SymDim::from_dim_expr(&dim, input_shapes)))
639        .collect();
640    TensorMeta::with_extents(metadata.dtype(), extents)
641}
642
643fn synthetic_input_shapes(metadata: &[ProgramValueMetadata]) -> Vec<Vec<SymDim>> {
644    let mut ranks = Vec::<usize>::new();
645    for expression in metadata
646        .iter()
647        .flat_map(ProgramValueMetadata::shape)
648        .filter_map(ShapeExtent::bound_expr)
649    {
650        collect_input_ranks(expression, &mut ranks);
651    }
652    ranks
653        .into_iter()
654        .enumerate()
655        .map(|(input, rank)| {
656            (0..rank)
657                .map(|axis| {
658                    SymDim::tensor_axis(
659                        u64::try_from(input + 1).expect("small semantic input index"),
660                        axis,
661                    )
662                })
663                .collect()
664        })
665        .collect()
666}
667
668fn collect_input_ranks(expression: &DimExpr, ranks: &mut Vec<usize>) {
669    match expression {
670        DimExpr::Const(_) => {}
671        DimExpr::InputDim { input_idx, axis } => {
672            if ranks.len() <= *input_idx {
673                ranks.resize(*input_idx + 1, 0);
674            }
675            ranks[*input_idx] = ranks[*input_idx].max(*axis + 1);
676        }
677        DimExpr::Add(lhs, rhs)
678        | DimExpr::Sub(lhs, rhs)
679        | DimExpr::Mul(lhs, rhs)
680        | DimExpr::FloorDiv(lhs, rhs)
681        | DimExpr::Min(lhs, rhs)
682        | DimExpr::Max(lhs, rhs) => {
683            collect_input_ranks(lhs, ranks);
684            collect_input_ranks(rhs, ranks);
685        }
686    }
687}
688
689#[derive(Clone, Debug)]
690enum SemanticLinearFragmentOp {
691    Core(CoreSemanticOp),
692    Extension(Arc<dyn tenferro_ad::extension::ExtensionOp>),
693    Unsupported(String),
694}
695
696#[derive(Clone)]
697enum SemanticLinearFragmentInput {
698    External(ValueKey<StdTensorOp>),
699    Local(LocalValueId),
700}
701
702impl From<ValueRef<StdTensorOp>> for SemanticLinearFragmentInput {
703    fn from(value: ValueRef<StdTensorOp>) -> Self {
704        match value {
705            ValueRef::External(key) => Self::External(key),
706            ValueRef::Local(local) => Self::Local(local),
707        }
708    }
709}
710
711struct SemanticLinearFragmentOperation {
712    operation: SemanticLinearFragmentOp,
713    inputs: Vec<SemanticLinearFragmentInput>,
714    role: OperationRole,
715    outputs: Vec<LocalValueId>,
716}
717
718fn semantic_linear_fragment_op(operation: &StdTensorOp) -> SemanticLinearFragmentOp {
719    match operation {
720        StdTensorOp::Extension(extension) => {
721            SemanticLinearFragmentOp::Extension(Arc::clone(extension))
722        }
723        core => CoreSemanticOp::try_from(core).map_or_else(
724            |_| SemanticLinearFragmentOp::Unsupported(format!("{core:?}")),
725            SemanticLinearFragmentOp::Core,
726        ),
727    }
728}
729
730struct SemanticRuleBuilder<'a, 'builder> {
731    next_local: usize,
732    locals: Vec<Option<ProgramValue>>,
733    external_values: &'a HashMap<ValueKey<StdTensorOp>, ProgramValue>,
734    shape_sources: &'a [ProgramValue],
735    builder: &'builder mut SemanticProgramBuilder,
736    role: SemanticAdRuleRole,
737    error: Option<SemanticAdError>,
738}
739
740impl<'a, 'builder> SemanticRuleBuilder<'a, 'builder> {
741    fn with_seeds(
742        seeds: &[Option<ProgramValue>],
743        external_values: &'a HashMap<ValueKey<StdTensorOp>, ProgramValue>,
744        shape_sources: &'a [ProgramValue],
745        builder: &'builder mut SemanticProgramBuilder,
746        role: SemanticAdRuleRole,
747    ) -> Self {
748        Self {
749            next_local: seeds.len(),
750            locals: seeds.to_vec(),
751            external_values,
752            shape_sources,
753            builder,
754            role,
755            error: None,
756        }
757    }
758
759    fn finish(self) -> Result<Vec<Option<ProgramValue>>, SemanticAdError> {
760        if let Some(error) = self.error {
761            Err(error)
762        } else {
763            Ok(self.locals)
764        }
765    }
766}
767
768impl PrimitiveRuleBuilder for SemanticRuleBuilder<'_, '_> {
769    fn add_operation(
770        &mut self,
771        operation: StdTensorOp,
772        inputs: Vec<ValueRef<StdTensorOp>>,
773        _role: OperationRole,
774    ) -> Vec<LocalValueId> {
775        let output_count = GraphOperation::output_count(&operation);
776        let outputs: Vec<_> = (self.next_local..self.next_local + output_count).collect();
777        self.next_local += output_count;
778        self.locals.resize(self.next_local, None);
779        if self.error.is_none() {
780            let fragment_op = semantic_linear_fragment_op(&operation);
781            let fragment_inputs: Vec<_> = inputs.into_iter().map(Into::into).collect();
782            let emitted = resolve_semantic_linear_fragment_inputs(
783                &fragment_inputs,
784                self.external_values,
785                &self.locals,
786                self.role,
787            )
788            .and_then(|resolved| {
789                emit_semantic_linear_fragment_operation(
790                    &fragment_op,
791                    &resolved,
792                    self.shape_sources,
793                    self.builder,
794                    None,
795                    self.role,
796                )
797            });
798            match emitted {
799                Ok(values) => {
800                    if values.len() != outputs.len() {
801                        self.error = Some(semantic_internal(
802                            self.role,
803                            format!(
804                                "semantic linalg AD operation emitted {} outputs for {} slots",
805                                values.len(),
806                                outputs.len()
807                            ),
808                        ));
809                    } else {
810                        for (local, value) in outputs.iter().copied().zip(values.iter().copied()) {
811                            self.locals[local] = Some(value);
812                        }
813                    }
814                }
815                Err(error) => {
816                    self.error = Some(error);
817                }
818            }
819        }
820        outputs
821    }
822}
823
824/// Op-local semantic linear fragment used by the manifest's
825/// `LinearizeThenTranspose` route. General linalg decomposition VJPs remain
826/// derived by transposing their emitted linearization, but the fragment stores
827/// semantic core ops or extension payloads instead of replaying legacy
828/// `StdTensorOp` graphs into the destination builder.
829struct SemanticLinearFragmentBuilder {
830    seed_count: usize,
831    next_local: usize,
832    operations: Vec<SemanticLinearFragmentOperation>,
833}
834
835impl SemanticLinearFragmentBuilder {
836    fn with_seed_count(seed_count: usize) -> Self {
837        Self {
838            seed_count,
839            next_local: seed_count,
840            operations: Vec::new(),
841        }
842    }
843
844    fn transpose_linear_fragment(
845        &self,
846        tangent_outputs: &[Option<LocalValueId>],
847        cotangent_outputs: &[AdValue],
848        active_inputs: &[bool],
849        external_values: &HashMap<ValueKey<StdTensorOp>, ProgramValue>,
850        shape_sources: &[ProgramValue],
851        builder: &mut SemanticProgramBuilder,
852    ) -> Result<Box<[AdValue]>, SemanticAdError> {
853        let role = SemanticAdRuleRole::LinearTranspose;
854        let mut fixed_ops = FixedCoreOps::default();
855        let fixed_locals = self.emit_fixed_primal_ops(
856            external_values,
857            shape_sources,
858            builder,
859            &mut fixed_ops,
860            role,
861        )?;
862        let mut cotangents = HashMap::<LocalValueId, ProgramValue>::new();
863        for (tangent, cotangent) in tangent_outputs
864            .iter()
865            .copied()
866            .zip(cotangent_outputs.iter().copied())
867        {
868            if let (Some(tangent), AdValue::Value(cotangent)) = (tangent, cotangent) {
869                accumulate_local_cotangent(builder, &mut cotangents, tangent, cotangent)?;
870            }
871        }
872        for operation in self.operations.iter().rev() {
873            let Some(active_mask) = linear_active_mask(&operation.role) else {
874                continue;
875            };
876            if !active_mask.iter().any(|active| *active) {
877                continue;
878            }
879            let output_cotangents: Vec<_> = operation
880                .outputs
881                .iter()
882                .map(|output| cotangents.remove(output))
883                .collect();
884            if output_cotangents.iter().all(Option::is_none) {
885                continue;
886            }
887            let context = SemanticLinearFragmentTransposeContext {
888                fragment: self,
889                external_values,
890                fixed_locals: &fixed_locals,
891                shape_sources,
892                role,
893            };
894            let input_cotangents = transpose_semantic_linear_fragment_operation(
895                operation,
896                &output_cotangents,
897                active_mask,
898                &context,
899                builder,
900                &mut fixed_ops,
901            )?;
902            for ((input, active), cotangent) in operation
903                .inputs
904                .iter()
905                .zip(active_mask)
906                .zip(input_cotangents)
907            {
908                if !active {
909                    continue;
910                }
911                let (SemanticLinearFragmentInput::Local(input), Some(cotangent)) =
912                    (input, cotangent)
913                else {
914                    return Err(semantic_internal(
915                        role,
916                        "linear linalg fragment has a non-local active input",
917                    ));
918                };
919                accumulate_local_cotangent(builder, &mut cotangents, *input, cotangent)?;
920            }
921        }
922        Ok(active_inputs
923            .iter()
924            .copied()
925            .enumerate()
926            .map(|(input, active)| {
927                if active {
928                    cotangents
929                        .remove(&input)
930                        .map_or(AdValue::Absent, AdValue::Value)
931                } else {
932                    AdValue::Absent
933                }
934            })
935            .collect())
936    }
937
938    fn emit_fixed_primal_ops(
939        &self,
940        external_values: &HashMap<ValueKey<StdTensorOp>, ProgramValue>,
941        shape_sources: &[ProgramValue],
942        builder: &mut SemanticProgramBuilder,
943        fixed_ops: &mut FixedCoreOps,
944        role: SemanticAdRuleRole,
945    ) -> Result<Vec<Option<ProgramValue>>, SemanticAdError> {
946        let mut locals = vec![None; self.next_local];
947        for operation in &self.operations {
948            if linear_active_mask(&operation.role)
949                .is_some_and(|mask| mask.iter().any(|active| *active))
950            {
951                continue;
952            }
953            let inputs = resolve_semantic_linear_fragment_inputs(
954                &operation.inputs,
955                external_values,
956                &locals,
957                role,
958            )?;
959            let outputs = emit_semantic_linear_fragment_operation(
960                &operation.operation,
961                &inputs,
962                shape_sources,
963                builder,
964                Some(&mut *fixed_ops),
965                role,
966            )?;
967            for (local, value) in operation
968                .outputs
969                .iter()
970                .copied()
971                .zip(outputs.iter().copied())
972            {
973                locals[local] = Some(value);
974            }
975        }
976        Ok(locals)
977    }
978}
979
980impl PrimitiveRuleBuilder for SemanticLinearFragmentBuilder {
981    fn add_operation(
982        &mut self,
983        operation: StdTensorOp,
984        inputs: Vec<ValueRef<StdTensorOp>>,
985        role: OperationRole,
986    ) -> Vec<LocalValueId> {
987        let output_count = GraphOperation::output_count(&operation);
988        let outputs: Vec<_> = (self.next_local..self.next_local + output_count).collect();
989        self.next_local += output_count;
990        self.operations.push(SemanticLinearFragmentOperation {
991            operation: semantic_linear_fragment_op(&operation),
992            inputs: inputs.into_iter().map(Into::into).collect(),
993            role,
994            outputs: outputs.clone(),
995        });
996        outputs
997    }
998}
999
1000fn linear_active_mask(role: &OperationRole) -> Option<&[bool]> {
1001    match role {
1002        OperationRole::Primary => None,
1003        OperationRole::Linearized { active_mask } => Some(active_mask),
1004    }
1005}
1006
1007/// Core operations one linear-transpose call has emitted on fixed (primal)
1008/// values, so a structurally identical request reuses the earlier value.
1009///
1010/// A rule's linearization and the generic pullback of its matrix products both
1011/// emit transposes of the same fixed factors: `linearize_eigh_values` builds
1012/// `V^H` and `V^T` from one `V`, and `transpose_matrix_dot` adjoints the fixed
1013/// operand again. Every core semantic operation is pure, so reusing an equal
1014/// `(op, inputs)` result is exact. Scope is one transpose call: values emitted
1015/// for different extension operations are never shared through this memo.
1016#[derive(Default)]
1017struct FixedCoreOps {
1018    emitted: Vec<FixedCoreOp>,
1019}
1020
1021struct FixedCoreOp {
1022    op: CoreSemanticOp,
1023    inputs: Box<[ProgramValue]>,
1024    outputs: Box<[ProgramValue]>,
1025}
1026
1027impl FixedCoreOps {
1028    fn add_op(
1029        &mut self,
1030        builder: &mut SemanticProgramBuilder,
1031        op: CoreSemanticOp,
1032        inputs: &[ProgramValue],
1033    ) -> Result<Box<[ProgramValue]>, SemanticAdError> {
1034        if let Some(emitted) = self
1035            .emitted
1036            .iter()
1037            .find(|emitted| emitted.op == op && *emitted.inputs == *inputs)
1038        {
1039            return Ok(emitted.outputs.clone());
1040        }
1041        let outputs = builder.add_op(op.clone(), inputs)?;
1042        self.emitted.push(FixedCoreOp {
1043            op,
1044            inputs: inputs.into(),
1045            outputs: outputs.clone(),
1046        });
1047        Ok(outputs)
1048    }
1049
1050    /// Adjoint of a fixed matrix operand. A real `x` that this memo produced as
1051    /// the leading-axes transpose of `y` adjoints back to `y` itself instead of
1052    /// a second transpose.
1053    fn matrix_adjoint(
1054        &mut self,
1055        builder: &mut SemanticProgramBuilder,
1056        value: ProgramValue,
1057        rank: usize,
1058    ) -> Result<ProgramValue, SemanticAdError> {
1059        let mut perm: Vec<_> = (0..rank).collect();
1060        perm.swap(0, 1);
1061        let complex = matches!(
1062            builder.value_metadata(value)?.dtype(),
1063            tenferro_tensor::DType::C32 | tenferro_tensor::DType::C64
1064        );
1065        if !complex
1066            && let Some(source) = self.emitted.iter().find_map(|emitted| {
1067                match (&emitted.op, &*emitted.inputs, &*emitted.outputs) {
1068                    (CoreSemanticOp::Transpose { perm: emitted_perm }, [source], [output])
1069                        if *output == value && *emitted_perm == perm =>
1070                    {
1071                        Some(*source)
1072                    }
1073                    _ => None,
1074                }
1075            })
1076        {
1077            return Ok(source);
1078        }
1079        let value = if complex {
1080            self.add_op(builder, CoreSemanticOp::Conj, &[value])?[0]
1081        } else {
1082            value
1083        };
1084        Ok(self.add_op(builder, CoreSemanticOp::Transpose { perm }, &[value])?[0])
1085    }
1086}
1087
1088struct SemanticLinearFragmentTransposeContext<'a> {
1089    fragment: &'a SemanticLinearFragmentBuilder,
1090    external_values: &'a HashMap<ValueKey<StdTensorOp>, ProgramValue>,
1091    fixed_locals: &'a [Option<ProgramValue>],
1092    shape_sources: &'a [ProgramValue],
1093    role: SemanticAdRuleRole,
1094}
1095
1096fn resolve_semantic_linear_fragment_inputs(
1097    inputs: &[SemanticLinearFragmentInput],
1098    external_values: &HashMap<ValueKey<StdTensorOp>, ProgramValue>,
1099    locals: &[Option<ProgramValue>],
1100    role: SemanticAdRuleRole,
1101) -> Result<Vec<ProgramValue>, SemanticAdError> {
1102    inputs
1103        .iter()
1104        .map(|input| match input {
1105            SemanticLinearFragmentInput::External(key) => external_values.get(key).copied(),
1106            SemanticLinearFragmentInput::Local(local) => locals.get(*local).copied().flatten(),
1107        })
1108        .collect::<Option<_>>()
1109        .ok_or_else(|| {
1110            semantic_internal(
1111                role,
1112                "semantic linalg linear fragment references an unavailable fixed value",
1113            )
1114        })
1115}
1116
1117fn emit_semantic_linear_fragment_operation(
1118    operation: &SemanticLinearFragmentOp,
1119    inputs: &[ProgramValue],
1120    shape_sources: &[ProgramValue],
1121    builder: &mut SemanticProgramBuilder,
1122    fixed_ops: Option<&mut FixedCoreOps>,
1123    role: SemanticAdRuleRole,
1124) -> Result<Box<[ProgramValue]>, SemanticAdError> {
1125    match operation {
1126        SemanticLinearFragmentOp::Extension(extension) => {
1127            Ok(builder.add_extension(Arc::clone(extension), inputs)?)
1128        }
1129        SemanticLinearFragmentOp::Core(core) => {
1130            let fragment_core = core.clone();
1131            let (core, inputs) =
1132                localize_shape_expressions(core.clone(), inputs, shape_sources, builder, role)
1133                    .map_err(|error| match error {
1134                        SemanticAdError::Invariant {
1135                            family_id,
1136                            role,
1137                            message,
1138                        } => SemanticAdError::Invariant {
1139                            family_id,
1140                            role,
1141                            message: format!(
1142                                "{message}; linear fragment operation {fragment_core:?}"
1143                            ),
1144                        },
1145                        other => other,
1146                    })?;
1147            match fixed_ops {
1148                Some(fixed_ops) => fixed_ops.add_op(builder, core, &inputs),
1149                None => Ok(builder.add_op(core, &inputs)?),
1150            }
1151        }
1152        SemanticLinearFragmentOp::Unsupported(operation) => Err(semantic_internal(
1153            role,
1154            format!("linalg AD emitted a non-semantic standard operation {operation}"),
1155        )),
1156    }
1157}
1158
1159fn localize_shape_expressions(
1160    operation: CoreSemanticOp,
1161    data_inputs: &[ProgramValue],
1162    shape_sources: &[ProgramValue],
1163    builder: &SemanticProgramBuilder,
1164    role: SemanticAdRuleRole,
1165) -> Result<(CoreSemanticOp, Vec<ProgramValue>), SemanticAdError> {
1166    let mut inputs = data_inputs.to_vec();
1167    let operation = match operation {
1168        CoreSemanticOp::Reshape { to_shape } => CoreSemanticOp::Reshape {
1169            to_shape: localize_dims(
1170                &to_shape,
1171                data_inputs,
1172                shape_sources,
1173                1,
1174                &mut inputs,
1175                builder,
1176                role,
1177            )?,
1178        },
1179        CoreSemanticOp::BroadcastInDim { shape, dims } => CoreSemanticOp::BroadcastInDim {
1180            shape: localize_dims(
1181                &shape,
1182                data_inputs,
1183                shape_sources,
1184                1,
1185                &mut inputs,
1186                builder,
1187                role,
1188            )?,
1189            dims,
1190        },
1191        CoreSemanticOp::GatherDynamicSliceSizes {
1192            offset_dims,
1193            collapsed_slice_dims,
1194            start_index_map,
1195            index_vector_dim,
1196            slice_sizes,
1197        } => CoreSemanticOp::GatherDynamicSliceSizes {
1198            offset_dims,
1199            collapsed_slice_dims,
1200            start_index_map,
1201            index_vector_dim,
1202            slice_sizes: localize_dims(
1203                &slice_sizes,
1204                data_inputs,
1205                shape_sources,
1206                2,
1207                &mut inputs,
1208                builder,
1209                role,
1210            )?,
1211        },
1212        other => other,
1213    };
1214    Ok((operation, inputs))
1215}
1216
1217fn localize_dims(
1218    dims: &[DimExpr],
1219    data_inputs: &[ProgramValue],
1220    shape_sources: &[ProgramValue],
1221    fixed_data_arity: usize,
1222    operation_inputs: &mut Vec<ProgramValue>,
1223    builder: &SemanticProgramBuilder,
1224    role: SemanticAdRuleRole,
1225) -> Result<Vec<DimExpr>, SemanticAdError> {
1226    dims.iter()
1227        .map(|dim| {
1228            localize_dim(
1229                dim,
1230                data_inputs,
1231                shape_sources,
1232                fixed_data_arity,
1233                operation_inputs,
1234                builder,
1235                role,
1236            )
1237        })
1238        .collect()
1239}
1240
1241fn localize_dim(
1242    dim: &DimExpr,
1243    data_inputs: &[ProgramValue],
1244    shape_sources: &[ProgramValue],
1245    fixed_data_arity: usize,
1246    operation_inputs: &mut Vec<ProgramValue>,
1247    builder: &SemanticProgramBuilder,
1248    role: SemanticAdRuleRole,
1249) -> Result<DimExpr, SemanticAdError> {
1250    let binary = |lhs: &DimExpr,
1251                  rhs: &DimExpr,
1252                  constructor: fn(Box<DimExpr>, Box<DimExpr>) -> DimExpr,
1253                  operation_inputs: &mut Vec<ProgramValue>|
1254     -> Result<DimExpr, SemanticAdError> {
1255        Ok(constructor(
1256            Box::new(localize_dim(
1257                lhs,
1258                data_inputs,
1259                shape_sources,
1260                fixed_data_arity,
1261                operation_inputs,
1262                builder,
1263                role,
1264            )?),
1265            Box::new(localize_dim(
1266                rhs,
1267                data_inputs,
1268                shape_sources,
1269                fixed_data_arity,
1270                operation_inputs,
1271                builder,
1272                role,
1273            )?),
1274        ))
1275    };
1276    match dim {
1277        DimExpr::Const(value) => Ok(DimExpr::Const(*value)),
1278        DimExpr::InputDim { input_idx, axis } => {
1279            // Legacy linalg rules express shape dimensions in invocation
1280            // coordinates. Shape-aware primitive helpers append explicit
1281            // shape operands after the primitive's fixed data operands and
1282            // remap their dimensions into those local operand coordinates.
1283            // Keep those two coordinate spaces distinct; rank compatibility
1284            // cannot disambiguate them.
1285            let source = if *input_idx >= fixed_data_arity {
1286                data_inputs
1287                    .get(*input_idx)
1288                    .copied()
1289                    .or_else(|| shape_sources.get(*input_idx).copied())
1290            } else {
1291                shape_sources.get(*input_idx).copied()
1292            }
1293            .ok_or_else(|| {
1294                    semantic_internal(
1295                        role,
1296                        format!(
1297                            "linalg AD symbolic shape input {input_idx} is out of bounds for {} operation inputs and {} primal shape sources",
1298                            data_inputs.len(),
1299                            shape_sources.len()
1300                        ),
1301                    )
1302                })?;
1303            let rank = builder.value_metadata(source)?.shape().len();
1304            if *axis >= rank {
1305                return Err(semantic_internal(
1306                    role,
1307                    format!(
1308                        "linalg AD symbolic shape axis {axis} is out of bounds for source rank {rank}"
1309                    ),
1310                ));
1311            }
1312            let input_idx = operation_inputs
1313                .iter()
1314                .position(|value| *value == source)
1315                .unwrap_or_else(|| {
1316                    operation_inputs.push(source);
1317                    operation_inputs.len() - 1
1318                });
1319            debug_assert!(
1320                input_idx < data_inputs.len() + shape_sources.len(),
1321                "localized shape source must be an operation input"
1322            );
1323            Ok(DimExpr::InputDim {
1324                input_idx,
1325                axis: *axis,
1326            })
1327        }
1328        DimExpr::Add(lhs, rhs) => binary(lhs, rhs, DimExpr::Add, operation_inputs),
1329        DimExpr::Sub(lhs, rhs) => binary(lhs, rhs, DimExpr::Sub, operation_inputs),
1330        DimExpr::Mul(lhs, rhs) => binary(lhs, rhs, DimExpr::Mul, operation_inputs),
1331        DimExpr::FloorDiv(lhs, rhs) => binary(lhs, rhs, DimExpr::FloorDiv, operation_inputs),
1332        DimExpr::Min(lhs, rhs) => binary(lhs, rhs, DimExpr::Min, operation_inputs),
1333        DimExpr::Max(lhs, rhs) => binary(lhs, rhs, DimExpr::Max, operation_inputs),
1334    }
1335}
1336
1337fn transpose_semantic_linear_fragment_operation(
1338    operation: &SemanticLinearFragmentOperation,
1339    cotangent_outputs: &[Option<ProgramValue>],
1340    active_mask: &[bool],
1341    context: &SemanticLinearFragmentTransposeContext<'_>,
1342    builder: &mut SemanticProgramBuilder,
1343    fixed_ops: &mut FixedCoreOps,
1344) -> Result<Vec<Option<ProgramValue>>, SemanticAdError> {
1345    let Some(cotangent) = cotangent_outputs.first().copied().flatten() else {
1346        return Ok(vec![None; operation.inputs.len()]);
1347    };
1348    let fixed = |index: usize| {
1349        if active_mask.get(index).copied().unwrap_or(false) {
1350            None
1351        } else {
1352            match operation.inputs.get(index) {
1353                Some(SemanticLinearFragmentInput::External(key)) => {
1354                    context.external_values.get(key).copied()
1355                }
1356                Some(SemanticLinearFragmentInput::Local(local)) => {
1357                    context.fixed_locals.get(*local).copied().flatten()
1358                }
1359                None => None,
1360            }
1361        }
1362    };
1363    let unary = |value| Ok(vec![Some(value)]);
1364    match &operation.operation {
1365        SemanticLinearFragmentOp::Core(CoreSemanticOp::Add) => Ok(active_mask
1366            .iter()
1367            .map(|active| active.then_some(cotangent))
1368            .collect()),
1369        SemanticLinearFragmentOp::Core(CoreSemanticOp::Sub) => {
1370            let rhs = builder.add_op(CoreSemanticOp::Neg, &[cotangent])?[0];
1371            Ok(vec![
1372                active_mask[0].then_some(cotangent),
1373                active_mask[1].then_some(rhs),
1374            ])
1375        }
1376        SemanticLinearFragmentOp::Core(CoreSemanticOp::Neg) => {
1377            let value = builder.add_op(CoreSemanticOp::Neg, &[cotangent])?[0];
1378            unary(value)
1379        }
1380        SemanticLinearFragmentOp::Core(CoreSemanticOp::Conj) => {
1381            let value = builder.add_op(CoreSemanticOp::Conj, &[cotangent])?[0];
1382            unary(value)
1383        }
1384        SemanticLinearFragmentOp::Core(CoreSemanticOp::Mul) => {
1385            transpose_mul(cotangent, active_mask, &fixed, builder, context.role)
1386        }
1387        SemanticLinearFragmentOp::Core(CoreSemanticOp::Div) => {
1388            transpose_div(cotangent, active_mask, &fixed, builder, context.role)
1389        }
1390        SemanticLinearFragmentOp::Core(CoreSemanticOp::DotGeneral { config }) => {
1391            transpose_matrix_dot(
1392                cotangent,
1393                config,
1394                active_mask,
1395                &fixed,
1396                builder,
1397                fixed_ops,
1398                context.role,
1399            )
1400        }
1401        SemanticLinearFragmentOp::Core(CoreSemanticOp::ReduceSum { axes }) => {
1402            transpose_reduce_sum(context, operation, cotangent, axes, active_mask, builder)
1403        }
1404        SemanticLinearFragmentOp::Core(CoreSemanticOp::Transpose { perm }) => {
1405            let mut inverse = vec![0; perm.len()];
1406            for (output_axis, input_axis) in perm.iter().copied().enumerate() {
1407                inverse[input_axis] = output_axis;
1408            }
1409            let value =
1410                builder.add_op(CoreSemanticOp::Transpose { perm: inverse }, &[cotangent])?[0];
1411            unary(value)
1412        }
1413        SemanticLinearFragmentOp::Core(CoreSemanticOp::Convert { from, to }) => {
1414            let value = builder.add_op(
1415                CoreSemanticOp::Convert {
1416                    from: *to,
1417                    to: *from,
1418                },
1419                &[cotangent],
1420            )?[0];
1421            unary(value)
1422        }
1423        SemanticLinearFragmentOp::Core(CoreSemanticOp::ExtractDiag { axis_a, axis_b }) => {
1424            let value = builder.add_op(
1425                CoreSemanticOp::EmbedDiag {
1426                    axis_a: *axis_a,
1427                    axis_b: *axis_b,
1428                },
1429                &[cotangent],
1430            )?[0];
1431            unary(value)
1432        }
1433        SemanticLinearFragmentOp::Core(CoreSemanticOp::EmbedDiag { axis_a, axis_b }) => {
1434            let value = builder.add_op(
1435                CoreSemanticOp::ExtractDiag {
1436                    axis_a: *axis_a,
1437                    axis_b: *axis_b,
1438                },
1439                &[cotangent],
1440            )?[0];
1441            unary(value)
1442        }
1443        SemanticLinearFragmentOp::Core(CoreSemanticOp::Tril { k }) => {
1444            let value = builder.add_op(CoreSemanticOp::Tril { k: *k }, &[cotangent])?[0];
1445            unary(value)
1446        }
1447        SemanticLinearFragmentOp::Core(CoreSemanticOp::Triu { k }) => {
1448            let value = builder.add_op(CoreSemanticOp::Triu { k: *k }, &[cotangent])?[0];
1449            unary(value)
1450        }
1451        SemanticLinearFragmentOp::Extension(extension) => transpose_linalg_extension(
1452            extension.as_ref(),
1453            operation,
1454            cotangent,
1455            active_mask,
1456            context.external_values,
1457            context.fixed_locals,
1458            builder,
1459        ),
1460        SemanticLinearFragmentOp::Unsupported(operation) => Err(semantic_internal(
1461            context.role,
1462            format!("unsupported linear linalg fragment operation {operation}"),
1463        )),
1464        other => Err(semantic_internal(
1465            context.role,
1466            format!("unsupported linear linalg fragment operation {other:?}"),
1467        )),
1468    }
1469}
1470
1471fn transpose_reduce_sum(
1472    context: &SemanticLinearFragmentTransposeContext<'_>,
1473    operation: &SemanticLinearFragmentOperation,
1474    cotangent: ProgramValue,
1475    axes: &[usize],
1476    active_mask: &[bool],
1477    builder: &mut SemanticProgramBuilder,
1478) -> Result<Vec<Option<ProgramValue>>, SemanticAdError> {
1479    if operation.inputs.len() != 1 || active_mask.len() != 1 {
1480        return Err(semantic_internal(
1481            context.role,
1482            "linear reduce_sum fragment has malformed arity",
1483        ));
1484    }
1485    if !active_mask[0] {
1486        return Ok(vec![None]);
1487    }
1488    let mut cache = HashMap::new();
1489    let input_shape = semantic_linear_fragment_value_shape(
1490        context.fragment,
1491        &operation.inputs[0],
1492        context.external_values,
1493        context.shape_sources,
1494        builder,
1495        context.role,
1496        &mut cache,
1497    )?
1498    .ok_or_else(|| {
1499        semantic_internal(
1500            context.role,
1501            "linear reduce_sum fragment is missing input shape metadata",
1502        )
1503    })?;
1504    if axes.iter().any(|axis| *axis >= input_shape.len()) {
1505        return Err(semantic_internal(
1506            context.role,
1507            format!(
1508                "linear reduce_sum axis is out of bounds for input rank {}",
1509                input_shape.len()
1510            ),
1511        ));
1512    }
1513    let dims: Vec<_> = (0..input_shape.len())
1514        .filter(|axis| !axes.contains(axis))
1515        .collect();
1516    let mut inputs = vec![cotangent];
1517    let shape = localize_dims(
1518        &input_shape,
1519        &[cotangent],
1520        context.shape_sources,
1521        1,
1522        &mut inputs,
1523        builder,
1524        context.role,
1525    )?;
1526    Ok(vec![Some(
1527        builder.add_op(CoreSemanticOp::BroadcastInDim { shape, dims }, &inputs)?[0],
1528    )])
1529}
1530
1531fn semantic_linear_fragment_value_shape(
1532    fragment: &SemanticLinearFragmentBuilder,
1533    value: &SemanticLinearFragmentInput,
1534    external_values: &HashMap<ValueKey<StdTensorOp>, ProgramValue>,
1535    shape_sources: &[ProgramValue],
1536    builder: &SemanticProgramBuilder,
1537    role: SemanticAdRuleRole,
1538    cache: &mut HashMap<LocalValueId, Option<Vec<DimExpr>>>,
1539) -> Result<Option<Vec<DimExpr>>, SemanticAdError> {
1540    match value {
1541        SemanticLinearFragmentInput::External(key) => {
1542            let source = external_values.get(key).copied().ok_or_else(|| {
1543                semantic_internal(
1544                    role,
1545                    "semantic linalg linear-fragment shape references missing external value",
1546                )
1547            })?;
1548            source_shape(source, shape_sources, builder, role).map(Some)
1549        }
1550        SemanticLinearFragmentInput::Local(local) => semantic_linear_fragment_local_shape(
1551            fragment,
1552            *local,
1553            external_values,
1554            shape_sources,
1555            builder,
1556            role,
1557            cache,
1558        ),
1559    }
1560}
1561
1562fn semantic_linear_fragment_local_shape(
1563    fragment: &SemanticLinearFragmentBuilder,
1564    local: LocalValueId,
1565    external_values: &HashMap<ValueKey<StdTensorOp>, ProgramValue>,
1566    shape_sources: &[ProgramValue],
1567    builder: &SemanticProgramBuilder,
1568    role: SemanticAdRuleRole,
1569    cache: &mut HashMap<LocalValueId, Option<Vec<DimExpr>>>,
1570) -> Result<Option<Vec<DimExpr>>, SemanticAdError> {
1571    if let Some(cached) = cache.get(&local) {
1572        return Ok(cached.clone());
1573    }
1574    let shape = if local < fragment.seed_count {
1575        let source = shape_sources.get(local).copied().ok_or_else(|| {
1576            semantic_internal(
1577                role,
1578                format!("semantic linalg linear-fragment seed local {local} has no shape source"),
1579            )
1580        })?;
1581        Some(source_shape(source, shape_sources, builder, role)?)
1582    } else {
1583        let (operation, output_index) = fragment
1584            .operations
1585            .iter()
1586            .find_map(|operation| {
1587                operation
1588                    .outputs
1589                    .iter()
1590                    .position(|output| *output == local)
1591                    .map(|index| (operation, index))
1592            })
1593            .ok_or_else(|| {
1594                semantic_internal(
1595                    role,
1596                    format!(
1597                        "semantic linalg linear-fragment local {local} has no producing operation"
1598                    ),
1599                )
1600            })?;
1601        semantic_linear_fragment_operation_output_shape(
1602            fragment,
1603            operation,
1604            output_index,
1605            external_values,
1606            shape_sources,
1607            builder,
1608            role,
1609            cache,
1610        )?
1611    };
1612    cache.insert(local, shape.clone());
1613    Ok(shape)
1614}
1615
1616fn source_shape(
1617    source: ProgramValue,
1618    shape_sources: &[ProgramValue],
1619    builder: &SemanticProgramBuilder,
1620    role: SemanticAdRuleRole,
1621) -> Result<Vec<DimExpr>, SemanticAdError> {
1622    let index = shape_sources
1623        .iter()
1624        .position(|candidate| *candidate == source)
1625        .ok_or_else(|| {
1626            semantic_internal(role, "shape source is not part of the linalg invocation")
1627        })?;
1628    let rank = builder.value_metadata(source)?.shape().len();
1629    Ok(DimExpr::input_shape(index, rank))
1630}
1631
1632#[allow(clippy::too_many_arguments)]
1633fn semantic_linear_fragment_operation_output_shape(
1634    fragment: &SemanticLinearFragmentBuilder,
1635    operation: &SemanticLinearFragmentOperation,
1636    output_index: usize,
1637    external_values: &HashMap<ValueKey<StdTensorOp>, ProgramValue>,
1638    shape_sources: &[ProgramValue],
1639    builder: &SemanticProgramBuilder,
1640    role: SemanticAdRuleRole,
1641    cache: &mut HashMap<LocalValueId, Option<Vec<DimExpr>>>,
1642) -> Result<Option<Vec<DimExpr>>, SemanticAdError> {
1643    let input_shape = |input_index: usize,
1644                       cache: &mut HashMap<LocalValueId, Option<Vec<DimExpr>>>|
1645     -> Result<Option<Vec<DimExpr>>, SemanticAdError> {
1646        let input = operation.inputs.get(input_index).ok_or_else(|| {
1647            semantic_internal(
1648                role,
1649                "semantic linalg linear-fragment shape requested missing operation input",
1650            )
1651        })?;
1652        semantic_linear_fragment_value_shape(
1653            fragment,
1654            input,
1655            external_values,
1656            shape_sources,
1657            builder,
1658            role,
1659            cache,
1660        )
1661    };
1662    match &operation.operation {
1663        SemanticLinearFragmentOp::Extension(extension) => {
1664            let linalg = semantic_linalg_op(extension.as_ref(), role)?;
1665            match linalg.op() {
1666                LinalgOp::LuFactor => match output_index {
1667                    0 => input_shape(0, cache),
1668                    1 => Ok(input_shape(0, cache)?.map(|shape| {
1669                        let (rows, cols, batch) =
1670                            semantic_linear_fragment_matrix_shape_parts(&shape);
1671                        let mut pivots_shape =
1672                            vec![DimExpr::Min(Box::new(rows.clone()), Box::new(cols.clone()))];
1673                        pivots_shape.extend_from_slice(batch);
1674                        pivots_shape
1675                    })),
1676                    2 => Ok(input_shape(0, cache)?.map(|shape| shape[2..].to_vec())),
1677                    _ => Ok(None),
1678                },
1679                LinalgOp::LuSolvePrepared { .. } => input_shape(3, cache),
1680                // The eigenvalue-value rule re-emits `Eigh` inside the linear
1681                // fragment to reach the eigenvectors, so the fragment shape
1682                // resolver must describe both outputs: the eigenvector matrix
1683                // keeps the input shape, and the eigenvalues drop the column
1684                // axis of the matrix core.
1685                LinalgOp::Eigh { .. } => match output_index {
1686                    0 => Ok(input_shape(0, cache)?.map(|shape| {
1687                        shape
1688                            .into_iter()
1689                            .enumerate()
1690                            .filter_map(|(axis, dim)| (axis != 1).then_some(dim))
1691                            .collect()
1692                    })),
1693                    1 => input_shape(0, cache),
1694                    _ => Ok(None),
1695                },
1696                _ => Ok(None),
1697            }
1698        }
1699        SemanticLinearFragmentOp::Core(CoreSemanticOp::ExtractDiag { axis_a, axis_b }) => {
1700            Ok(input_shape(0, cache)?
1701                .map(|shape| extract_diag_shape(&shape, *axis_a, *axis_b))
1702                .transpose()?)
1703        }
1704        SemanticLinearFragmentOp::Core(CoreSemanticOp::ReduceSum { axes }) => {
1705            Ok(input_shape(0, cache)?.map(|shape| {
1706                shape
1707                    .into_iter()
1708                    .enumerate()
1709                    .filter_map(|(axis, dim)| (!axes.contains(&axis)).then_some(dim))
1710                    .collect()
1711            }))
1712        }
1713        SemanticLinearFragmentOp::Core(
1714            CoreSemanticOp::Convert { .. }
1715            | CoreSemanticOp::Neg
1716            | CoreSemanticOp::Conj
1717            // Hadamard products in a linalg linear fragment keep the operand
1718            // shape; the eigenvalue path emits one before its reduction, and the
1719            // transposed reduction needs that shape to restore the operands.
1720            | CoreSemanticOp::Mul
1721            | CoreSemanticOp::Tril { .. }
1722            | CoreSemanticOp::Triu { .. },
1723        ) => input_shape(0, cache),
1724        SemanticLinearFragmentOp::Core(CoreSemanticOp::Transpose { perm }) => {
1725            Ok(input_shape(0, cache)?
1726                .map(|shape| perm.iter().map(|axis| shape[*axis].clone()).collect()))
1727        }
1728        _ => Ok(None),
1729    }
1730}
1731
1732fn semantic_linear_fragment_matrix_shape_parts(
1733    shape: &[DimExpr],
1734) -> (&DimExpr, &DimExpr, &[DimExpr]) {
1735    (&shape[0], &shape[1], &shape[2..])
1736}
1737
1738fn extract_diag_shape(
1739    shape: &[DimExpr],
1740    axis_a: usize,
1741    axis_b: usize,
1742) -> Result<Vec<DimExpr>, SemanticAdError> {
1743    if axis_a >= shape.len() || axis_b >= shape.len() || axis_a == axis_b {
1744        return Err(semantic_internal(
1745            SemanticAdRuleRole::LinearTranspose,
1746            "extract_diag shape derivation received invalid axes",
1747        ));
1748    }
1749    let diagonal = DimExpr::Min(
1750        Box::new(shape[axis_a].clone()),
1751        Box::new(shape[axis_b].clone()),
1752    );
1753    let mut output = Vec::with_capacity(shape.len() - 1);
1754    for (axis, dim) in shape.iter().enumerate() {
1755        if axis == axis_b {
1756            continue;
1757        }
1758        if axis == axis_a {
1759            output.push(diagonal.clone());
1760        } else {
1761            output.push(dim.clone());
1762        }
1763    }
1764    Ok(output)
1765}
1766
1767fn transpose_mul(
1768    cotangent: ProgramValue,
1769    active_mask: &[bool],
1770    fixed: &impl Fn(usize) -> Option<ProgramValue>,
1771    builder: &mut SemanticProgramBuilder,
1772    role: SemanticAdRuleRole,
1773) -> Result<Vec<Option<ProgramValue>>, SemanticAdError> {
1774    let mut result = vec![None; 2];
1775    for input in 0..2 {
1776        if !active_mask[input] {
1777            continue;
1778        }
1779        let coefficient = fixed(1 - input).ok_or_else(|| {
1780            semantic_internal(role, "linear multiply is missing its fixed coefficient")
1781        })?;
1782        let coefficient = conjugate_if_complex(builder, coefficient)?;
1783        result[input] = Some(builder.add_op(CoreSemanticOp::Mul, &[cotangent, coefficient])?[0]);
1784    }
1785    Ok(result)
1786}
1787
1788fn transpose_div(
1789    cotangent: ProgramValue,
1790    active_mask: &[bool],
1791    fixed: &impl Fn(usize) -> Option<ProgramValue>,
1792    builder: &mut SemanticProgramBuilder,
1793    role: SemanticAdRuleRole,
1794) -> Result<Vec<Option<ProgramValue>>, SemanticAdError> {
1795    let mut result = vec![None; 2];
1796    if active_mask[0] {
1797        let denominator = fixed(1).ok_or_else(|| {
1798            semantic_internal(role, "linear divide is missing its fixed denominator")
1799        })?;
1800        let denominator = conjugate_if_complex(builder, denominator)?;
1801        result[0] = Some(builder.add_op(CoreSemanticOp::Div, &[cotangent, denominator])?[0]);
1802    }
1803    if active_mask[1] {
1804        let numerator = fixed(0).ok_or_else(|| {
1805            semantic_internal(role, "linear divide is missing its fixed numerator")
1806        })?;
1807        let denominator = fixed(1).ok_or_else(|| {
1808            semantic_internal(role, "linear divide is missing its fixed denominator")
1809        })?;
1810        let square = builder.add_op(CoreSemanticOp::Mul, &[denominator, denominator])?[0];
1811        let coefficient = builder.add_op(CoreSemanticOp::Div, &[numerator, square])?[0];
1812        let coefficient = conjugate_if_complex(builder, coefficient)?;
1813        let value = builder.add_op(CoreSemanticOp::Mul, &[cotangent, coefficient])?[0];
1814        result[1] = Some(builder.add_op(CoreSemanticOp::Neg, &[value])?[0]);
1815    }
1816    Ok(result)
1817}
1818
1819fn transpose_matrix_dot(
1820    cotangent: ProgramValue,
1821    config: &tenferro_tensor::DotGeneralConfig,
1822    active_mask: &[bool],
1823    fixed: &impl Fn(usize) -> Option<ProgramValue>,
1824    builder: &mut SemanticProgramBuilder,
1825    fixed_ops: &mut FixedCoreOps,
1826    role: SemanticAdRuleRole,
1827) -> Result<Vec<Option<ProgramValue>>, SemanticAdError> {
1828    let rank = 2 + config.lhs_batch_dims.len();
1829    let expected_batch: Vec<_> = (2..rank).collect();
1830    if config.lhs_contracting_dims.as_slice() != [1]
1831        || config.rhs_contracting_dims.as_slice() != [0]
1832        || config.lhs_batch_dims.as_slice() != expected_batch.as_slice()
1833        || config.rhs_batch_dims.as_slice() != expected_batch.as_slice()
1834    {
1835        return Err(semantic_internal(
1836            role,
1837            "linalg AD emitted an unsupported dot-general configuration",
1838        ));
1839    }
1840    let mut result = vec![None; 2];
1841    if active_mask[0] {
1842        let rhs = fixed(1).ok_or_else(|| {
1843            semantic_internal(role, "linear matrix product is missing its fixed rhs")
1844        })?;
1845        let rhs_h = fixed_ops.matrix_adjoint(builder, rhs, rank)?;
1846        result[0] = Some(
1847            builder.add_op(
1848                CoreSemanticOp::DotGeneral {
1849                    config: config.clone(),
1850                },
1851                &[cotangent, rhs_h],
1852            )?[0],
1853        );
1854    }
1855    if active_mask[1] {
1856        let lhs = fixed(0).ok_or_else(|| {
1857            semantic_internal(role, "linear matrix product is missing its fixed lhs")
1858        })?;
1859        let lhs_h = fixed_ops.matrix_adjoint(builder, lhs, rank)?;
1860        result[1] = Some(
1861            builder.add_op(
1862                CoreSemanticOp::DotGeneral {
1863                    config: config.clone(),
1864                },
1865                &[lhs_h, cotangent],
1866            )?[0],
1867        );
1868    }
1869    Ok(result)
1870}
1871
1872fn semantic_solve_matrix_cotangent(
1873    builder: &mut SemanticProgramBuilder,
1874    rhs_cotangent: ProgramValue,
1875    solution: ProgramValue,
1876    left_side: bool,
1877    transpose_a: bool,
1878    rank: usize,
1879) -> Result<ProgramValue, SemanticAdError> {
1880    let negative_rhs_cotangent = builder.add_op(CoreSemanticOp::Neg, &[rhs_cotangent])?[0];
1881    let solution_h = matrix_adjoint(builder, solution, rank)?;
1882    let config = semantic_matrix_multiply_config(rank)?;
1883    let matrix_cotangent = if left_side {
1884        builder.add_op(
1885            CoreSemanticOp::DotGeneral {
1886                config: config.clone(),
1887            },
1888            &[negative_rhs_cotangent, solution_h],
1889        )?[0]
1890    } else {
1891        builder.add_op(
1892            CoreSemanticOp::DotGeneral { config },
1893            &[solution_h, negative_rhs_cotangent],
1894        )?[0]
1895    };
1896    if transpose_a {
1897        semantic_matrix_transpose(builder, matrix_cotangent, rank)
1898    } else {
1899        Ok(matrix_cotangent)
1900    }
1901}
1902
1903fn semantic_matrix_multiply_config(
1904    rank: usize,
1905) -> Result<tenferro_tensor::DotGeneralConfig, SemanticAdError> {
1906    if rank < 2 {
1907        return Err(semantic_internal(
1908            SemanticAdRuleRole::LinearTranspose,
1909            "matrix multiply semantic helper expects rank >= 2",
1910        ));
1911    }
1912    let batch_dims: Vec<usize> = (2..rank).collect();
1913    Ok(tenferro_tensor::DotGeneralConfig {
1914        lhs_contracting_dims: [1].as_slice().into(),
1915        rhs_contracting_dims: [0].as_slice().into(),
1916        lhs_batch_dims: batch_dims.clone().iter().copied().collect(),
1917        rhs_batch_dims: batch_dims.iter().copied().collect(),
1918    })
1919}
1920
1921fn semantic_matrix_transpose(
1922    builder: &mut SemanticProgramBuilder,
1923    value: ProgramValue,
1924    rank: usize,
1925) -> Result<ProgramValue, SemanticAdError> {
1926    if rank < 2 {
1927        return Err(semantic_internal(
1928            SemanticAdRuleRole::LinearTranspose,
1929            "matrix transpose semantic helper expects rank >= 2",
1930        ));
1931    }
1932    let mut perm: Vec<_> = (0..rank).collect();
1933    perm.swap(0, 1);
1934    Ok(builder.add_op(CoreSemanticOp::Transpose { perm }, &[value])?[0])
1935}
1936
1937fn matrix_adjoint(
1938    builder: &mut SemanticProgramBuilder,
1939    value: ProgramValue,
1940    rank: usize,
1941) -> Result<ProgramValue, SemanticAdError> {
1942    let value = conjugate_if_complex(builder, value)?;
1943    let mut perm: Vec<_> = (0..rank).collect();
1944    perm.swap(0, 1);
1945    Ok(builder.add_op(CoreSemanticOp::Transpose { perm }, &[value])?[0])
1946}
1947
1948fn conjugate_if_complex(
1949    builder: &mut SemanticProgramBuilder,
1950    value: ProgramValue,
1951) -> Result<ProgramValue, SemanticAdError> {
1952    if matches!(
1953        builder.value_metadata(value)?.dtype(),
1954        tenferro_tensor::DType::C32 | tenferro_tensor::DType::C64
1955    ) {
1956        Ok(builder.add_op(CoreSemanticOp::Conj, &[value])?[0])
1957    } else {
1958        Ok(value)
1959    }
1960}
1961
1962fn transpose_linalg_extension(
1963    extension: &dyn tenferro_ad::extension::ExtensionOp,
1964    operation: &SemanticLinearFragmentOperation,
1965    cotangent: ProgramValue,
1966    active_mask: &[bool],
1967    external_values: &HashMap<ValueKey<StdTensorOp>, ProgramValue>,
1968    fixed_locals: &[Option<ProgramValue>],
1969    builder: &mut SemanticProgramBuilder,
1970) -> Result<Vec<Option<ProgramValue>>, SemanticAdError> {
1971    let role = SemanticAdRuleRole::LinearTranspose;
1972    let linalg = semantic_linalg_op(extension, role)?;
1973    if !matches!(
1974        linalg.op(),
1975        LinalgOp::TriangularSolve { .. }
1976            | LinalgOp::LuSolvePrepared { .. }
1977            | LinalgOp::FullPivLuSolve { .. }
1978            | LinalgOp::Solve
1979            | LinalgOp::HouseholderQrAppendTangent
1980    ) {
1981        return Err(semantic_internal(
1982            role,
1983            format!(
1984                "linear linalg fragment contains unsupported extension {:?}",
1985                linalg.op()
1986            ),
1987        ));
1988    }
1989    let mut context = ShapeGuardContext::default();
1990    let mut fixed_values = HashMap::new();
1991    let mut keys = Vec::with_capacity(operation.inputs.len());
1992    let mut shape_sources = Vec::with_capacity(operation.inputs.len());
1993    for (index, (input, active)) in operation.inputs.iter().zip(active_mask).enumerate() {
1994        let key = ValueKey::Input(TensorInputKey::User {
1995            id: 10_000 + u64::try_from(index).expect("small linalg extension arity"),
1996        });
1997        let value = if *active {
1998            cotangent
1999        } else {
2000            match input {
2001                SemanticLinearFragmentInput::External(key) => external_values.get(key).copied(),
2002                SemanticLinearFragmentInput::Local(local) => {
2003                    fixed_locals.get(*local).copied().flatten()
2004                }
2005            }
2006            .ok_or_else(|| {
2007                semantic_internal(role, "linear solve fragment is missing a fixed operand")
2008            })?
2009        };
2010        let metadata = builder.value_metadata(value)?.clone();
2011        let symbolic_shapes = synthetic_input_shapes(std::slice::from_ref(&metadata));
2012        let symbolic_shape_refs: Vec<_> = symbolic_shapes.iter().map(Vec::as_slice).collect();
2013        context.insert_metadata(
2014            key.clone(),
2015            legacy_metadata(&metadata, &symbolic_shape_refs),
2016        );
2017        if !active {
2018            fixed_values.insert(key.clone(), value);
2019        }
2020        shape_sources.push(value);
2021        keys.push(key);
2022    }
2023    let inputs: Vec<_> = keys
2024        .iter()
2025        .cloned()
2026        .map(PrimitiveTransposeInput::Residual)
2027        .collect();
2028    let mut emitted = SemanticRuleBuilder::with_seeds(
2029        &[Some(cotangent)],
2030        &fixed_values,
2031        &shape_sources,
2032        builder,
2033        role,
2034    );
2035    let outputs = LinalgAdRule
2036        .linear_transpose(
2037            extension,
2038            &mut emitted,
2039            &[Some(0)],
2040            &inputs,
2041            active_mask,
2042            &mut context,
2043        )
2044        .map_err(|error| legacy_error(role, error))?;
2045    let locals = emitted.finish()?;
2046    Ok(outputs
2047        .into_iter()
2048        .map(|output| output.and_then(|local| locals.get(local).copied().flatten()))
2049        .collect())
2050}
2051
2052fn accumulate_local_cotangent(
2053    builder: &mut SemanticProgramBuilder,
2054    cotangents: &mut HashMap<LocalValueId, ProgramValue>,
2055    local: LocalValueId,
2056    cotangent: ProgramValue,
2057) -> Result<(), SemanticAdError> {
2058    if let Some(existing) = cotangents.get_mut(&local) {
2059        *existing = builder.add_op(CoreSemanticOp::Add, &[*existing, cotangent])?[0];
2060    } else {
2061        cotangents.insert(local, cotangent);
2062    }
2063    Ok(())
2064}
2065
2066fn semantic_linalg_op(
2067    op: &dyn tenferro_ad::extension::ExtensionOp,
2068    role: SemanticAdRuleRole,
2069) -> Result<&LinalgExtensionOp, SemanticAdError> {
2070    op.as_any()
2071        .downcast_ref::<LinalgExtensionOp>()
2072        .ok_or_else(|| SemanticAdError::Unsupported {
2073            family_id: LINALG_EXTENSION_FAMILY_ID,
2074            role,
2075            message: "linalg semantic AD received an incompatible payload".into(),
2076        })
2077}
2078
2079fn legacy_error(role: SemanticAdRuleRole, error: tenferro_ops::ad::ADRuleError) -> SemanticAdError {
2080    SemanticAdError::Rule {
2081        family_id: LINALG_EXTENSION_FAMILY_ID,
2082        role,
2083        source: Box::new(error),
2084    }
2085}
2086
2087fn semantic_internal(role: SemanticAdRuleRole, message: impl Into<String>) -> SemanticAdError {
2088    SemanticAdError::Invariant {
2089        family_id: LINALG_EXTENSION_FAMILY_ID,
2090        role,
2091        message: message.into(),
2092    }
2093}
2094
2095#[cfg(test)]
2096mod tests {
2097    use super::*;
2098    use tenferro_runtime::program::ProgramInputSpec;
2099    use tenferro_tensor::DType;
2100
2101    #[test]
2102    fn recorded_broadcast_prefers_primal_shape_source_over_rank_compatible_data_input() {
2103        let mut builder = SemanticProgramBuilder::new();
2104        let _row_anchor = builder
2105            .input(ProgramInputSpec::new(DType::F64, [DimExpr::Const(3)]))
2106            .unwrap();
2107        let _col_anchor = builder
2108            .input(ProgramInputSpec::new(DType::F64, [DimExpr::Const(2)]))
2109            .unwrap();
2110        let matrix = builder
2111            .input(ProgramInputSpec::new(
2112                DType::F64,
2113                [
2114                    DimExpr::InputDim {
2115                        input_idx: 0,
2116                        axis: 0,
2117                    },
2118                    DimExpr::InputDim {
2119                        input_idx: 1,
2120                        axis: 0,
2121                    },
2122                ],
2123            ))
2124            .unwrap();
2125        let vector = builder
2126            .input(ProgramInputSpec::new(
2127                DType::F64,
2128                [DimExpr::Min(
2129                    Box::new(DimExpr::InputDim {
2130                        input_idx: 0,
2131                        axis: 0,
2132                    }),
2133                    Box::new(DimExpr::InputDim {
2134                        input_idx: 1,
2135                        axis: 0,
2136                    }),
2137                )],
2138            ))
2139            .unwrap();
2140
2141        let (operation, inputs) = localize_shape_expressions(
2142            CoreSemanticOp::BroadcastInDim {
2143                shape: vec![
2144                    DimExpr::InputDim {
2145                        input_idx: 0,
2146                        axis: 0,
2147                    },
2148                    DimExpr::InputDim {
2149                        input_idx: 0,
2150                        axis: 1,
2151                    },
2152                ],
2153                dims: vec![1],
2154            },
2155            &[vector],
2156            &[matrix],
2157            &builder,
2158            SemanticAdRuleRole::Linearize,
2159        )
2160        .unwrap();
2161
2162        assert_eq!(inputs, vec![vector, matrix]);
2163        assert_eq!(
2164            operation,
2165            CoreSemanticOp::BroadcastInDim {
2166                shape: vec![
2167                    DimExpr::InputDim {
2168                        input_idx: 1,
2169                        axis: 0,
2170                    },
2171                    DimExpr::InputDim {
2172                        input_idx: 1,
2173                        axis: 1,
2174                    },
2175                ],
2176                dims: vec![1],
2177            }
2178        );
2179    }
2180
2181    #[test]
2182    fn linalg_residual_mask_declares_all_inputs_and_outputs() {
2183        // The linalg family is one rule across solve/eigen/qr ops. SVD reads
2184        // outputs 0-2 and eigh/qr read outputs 0-1 as tensor residuals, so the
2185        // mask must declare every input and output (issue #1665 step 5).
2186        let mask = LinalgAdRule.residual_mask();
2187        assert!(mask.declares_input(0));
2188        assert!(mask.declares_input(1));
2189        assert!(mask.declares_output(0));
2190        assert!(mask.declares_output(1));
2191        assert!(mask.declares_output(2));
2192    }
2193}