Skip to main content

tenferro_ad/
semantic_transform.rs

1//! Whole-program automatic differentiation over semantic SSA programs.
2
3mod core_dynamic;
4mod core_indexing;
5mod core_reductions;
6mod core_structural;
7
8use std::collections::{HashMap, HashSet};
9
10use tenferro_ops::{dim_expr::DimExpr, ShapeExtent};
11use tenferro_runtime::program::{
12    CoreSemanticOp, FrozenProgram, ProgramBuildError, ProgramFinishError, ProgramImport,
13    ProgramInputSpec, ProgramQueryError, ProgramValue, ProgramValueMetadata, SemanticOpRef,
14    SemanticProgramBuilder,
15};
16use tenferro_runtime::{CompareDir, DType, DotGeneralConfig};
17
18use crate::semantic_extension::{AdValue, SemanticAdError, SemanticExtensionRuleSet};
19use core_dynamic::{dynamic_shape_vjp, linearize_dynamic_shape};
20use core_indexing::{indexing_vjp, linearize_indexing};
21use core_reductions::{linearize_nonlinear_reduction, nonlinear_reduction_vjp};
22use core_structural::{concatenate_vjp, linearize_concatenate, pad_vjp, slice_vjp};
23
24/// Semantic AD transform role used by typed diagnostics.
25#[derive(Clone, Copy, Debug, PartialEq, Eq)]
26pub enum SemanticTransformRole {
27    /// Forward-mode linearization.
28    Jvp,
29    /// Reverse-mode transposition.
30    Vjp,
31}
32
33/// Failures produced by whole-program semantic AD.
34#[derive(Debug, thiserror::Error)]
35pub enum SemanticAdTransformError {
36    /// An activity mask did not match the corresponding ordered value list.
37    #[error("semantic {role:?} {field} expects {expected} entries, got {actual}")]
38    ActivityArity {
39        /// Transform role.
40        role: SemanticTransformRole,
41        /// Invalid mask.
42        field: &'static str,
43        /// Required entry count.
44        expected: usize,
45        /// Supplied entry count.
46        actual: usize,
47    },
48    /// An active core operation has not yet been admitted to semantic AD.
49    #[error("semantic {role:?} does not support active core operation {op}")]
50    UnsupportedCore {
51        /// Transform role.
52        role: SemanticTransformRole,
53        /// Bounded operation diagnostic.
54        op: String,
55    },
56    /// A future semantic operation variant is unknown to this transform.
57    #[error("semantic {role:?} does not support this semantic operation variant")]
58    UnsupportedOperationVariant {
59        /// Transform role.
60        role: SemanticTransformRole,
61    },
62    /// Active derivative metadata is outside the admitted exact-shape subset.
63    #[error("semantic {role:?} does not support derivative metadata: {message}")]
64    UnsupportedMetadata {
65        /// Transform role.
66        role: SemanticTransformRole,
67        /// Bounded metadata diagnostic.
68        message: String,
69    },
70    /// Source-program metadata could not be queried.
71    #[error("semantic AD source-program query failed: {0}")]
72    Query(#[from] ProgramQueryError),
73    /// Destination semantic-program construction failed.
74    #[error("semantic AD program construction failed: {0}")]
75    Build(#[from] ProgramBuildError),
76    /// An extension-owned semantic AD rule failed.
77    #[error("semantic extension AD failed: {0}")]
78    Extension(#[from] SemanticAdError),
79    /// The transformed program could not be frozen atomically.
80    #[error("semantic AD program finalization failed: {0}")]
81    Finish(#[from] ProgramFinishError),
82    /// The semantic AD transform cache could not be accessed.
83    #[error("semantic AD transform cache failed: {0}")]
84    Cache(#[source] tenferro_runtime::Error),
85}
86
87/// One frozen derivative program plus ordered derivative input/output maps.
88///
89/// Original primal inputs retain their source order. Active derivative seed
90/// inputs are appended in source order. Program outputs contain only active
91/// derivative values, also in source order; `None` records an inactive value.
92#[derive(Clone, Debug)]
93pub struct SemanticAdProgram {
94    frozen: FrozenProgram,
95    derivative_input_indices: Box<[Option<usize>]>,
96    derivative_output_indices: Box<[Option<usize>]>,
97}
98
99struct ValueShapePlan {
100    shape: Vec<DimExpr>,
101    dynamic_axes: Vec<usize>,
102}
103
104impl SemanticAdProgram {
105    /// Borrow the frozen derivative program.
106    pub const fn frozen(&self) -> &FrozenProgram {
107        &self.frozen
108    }
109
110    /// Return transformed-program input indices for ordered derivative seeds.
111    pub fn derivative_input_indices(&self) -> &[Option<usize>] {
112        &self.derivative_input_indices
113    }
114
115    /// Return transformed-program output indices for ordered derivatives.
116    pub fn derivative_output_indices(&self) -> &[Option<usize>] {
117        &self.derivative_output_indices
118    }
119
120    /// Consume this result and return the frozen derivative program.
121    pub fn into_frozen(self) -> FrozenProgram {
122        self.frozen
123    }
124
125    pub(crate) fn with_input_prefix_bindings_from(
126        &self,
127        source: &FrozenProgram,
128    ) -> Result<Self, ProgramFinishError> {
129        Ok(Self {
130            frozen: self.frozen.with_input_prefix_bindings_from(source)?,
131            derivative_input_indices: self.derivative_input_indices.clone(),
132            derivative_output_indices: self.derivative_output_indices.clone(),
133        })
134    }
135}
136
137/// Build a forward-mode derivative program.
138///
139/// `active_inputs` follows source-program input order. Each active input gets
140/// one appended tangent seed. The result maps source outputs to compact
141/// derivative-program outputs.
142///
143/// # Errors
144///
145/// Returns [`SemanticAdTransformError::ActivityArity`] for a mask-length
146/// mismatch, [`SemanticAdTransformError::Extension`] for a rejected extension
147/// rule, or the corresponding `Query`, `Build`, `Finish`, or unsupported
148/// operation/metadata variant for failures encountered during transformation.
149pub fn semantic_jvp(
150    input: &FrozenProgram,
151    active_inputs: &[bool],
152    rules: &SemanticExtensionRuleSet,
153) -> Result<SemanticAdProgram, SemanticAdTransformError> {
154    validate_activity(
155        SemanticTransformRole::Jvp,
156        "active_inputs",
157        input.program.inputs().len(),
158        active_inputs.len(),
159    )?;
160    let mut builder = SemanticProgramBuilder::new();
161    let values = import_source(input, &mut builder)?;
162    let mut tangents = HashMap::new();
163    let mut derivative_input_indices = vec![None; input.program.inputs().len()];
164    let mut next_input = input.program.inputs().len();
165    for (index, source) in input.program.inputs().iter().copied().enumerate() {
166        if active_inputs[index] {
167            let imported_source = values[&source];
168            let tangent = builder.input(ProgramInputSpec::from_metadata(
169                builder.value_metadata(imported_source)?.clone(),
170            ))?;
171            derivative_input_indices[index] = Some(next_input);
172            next_input += 1;
173            tangents.insert(source, AdValue::Value(tangent));
174        } else {
175            tangents.insert(source, AdValue::Absent);
176        }
177    }
178
179    let live = source_output_liveness(input);
180    for operation in input.program.operations() {
181        let tangent_inputs: Vec<_> = operation
182            .inputs()
183            .iter()
184            .map(|value| tangents.get(value).copied().unwrap_or(AdValue::Absent))
185            .collect();
186        let active_outputs: Vec<_> = operation
187            .outputs()
188            .iter()
189            .map(|value| live.contains(value))
190            .collect();
191        let tangent_outputs = if tangent_inputs
192            .iter()
193            .all(|value| matches!(value, AdValue::Absent))
194        {
195            vec![AdValue::Absent; operation.outputs().len()].into_boxed_slice()
196        } else {
197            match operation.op() {
198                SemanticOpRef::Extension(_) => rules
199                    .linearize_operation(
200                        operation,
201                        &mapped_values(operation.inputs(), &values),
202                        &mapped_values(operation.outputs(), &values),
203                        &tangent_inputs,
204                        &active_outputs,
205                        &mut builder,
206                    )?
207                    .tangent_outputs()
208                    .into(),
209                SemanticOpRef::Core(op) => linearize_core(
210                    op,
211                    &mapped_values(operation.inputs(), &values),
212                    &tangent_inputs,
213                    &mut builder,
214                )?,
215                _ => {
216                    return Err(SemanticAdTransformError::UnsupportedOperationVariant {
217                        role: SemanticTransformRole::Jvp,
218                    });
219                }
220            }
221        };
222        for (source, tangent) in operation.outputs().iter().copied().zip(tangent_outputs) {
223            tangents.insert(source, tangent);
224        }
225    }
226
227    let outputs = input
228        .program
229        .outputs()
230        .iter()
231        .map(|value| tangents.get(value).copied().unwrap_or(AdValue::Absent))
232        .collect();
233    finish_derivative(builder, derivative_input_indices, outputs)
234}
235
236/// Build a reverse-mode derivative program using extension semantic rules.
237///
238/// `active_inputs` selects requested source-input cotangents and
239/// `active_outputs` selects source outputs that receive appended cotangent
240/// seeds. Both masks follow source order.
241///
242/// # Errors
243///
244/// Returns [`SemanticAdTransformError::ActivityArity`] for a mask-length
245/// mismatch, [`SemanticAdTransformError::Extension`] for a rejected extension
246/// rule, or the corresponding `Query`, `Build`, `Finish`, or unsupported
247/// operation/metadata variant for failures encountered during transformation.
248pub fn semantic_vjp(
249    input: &FrozenProgram,
250    active_inputs: &[bool],
251    active_outputs: &[bool],
252    rules: &SemanticExtensionRuleSet,
253) -> Result<SemanticAdProgram, SemanticAdTransformError> {
254    semantic_vjp_with_saved_outputs(input, active_inputs, active_outputs, rules, &[])
255        .map(|(program, _)| program)
256}
257
258// Execution-only specialization: saved primal values are coefficients of the
259// VJP, not new differentiation targets. Keep the unspecialized derivative
260// program for functional gradients so higher-order AD retains their producers.
261pub(crate) fn semantic_vjp_with_saved_outputs(
262    input: &FrozenProgram,
263    active_inputs: &[bool],
264    active_outputs: &[bool],
265    rules: &SemanticExtensionRuleSet,
266    saved_outputs: &[usize],
267) -> Result<(SemanticAdProgram, Vec<usize>), SemanticAdTransformError> {
268    validate_activity(
269        SemanticTransformRole::Vjp,
270        "active_inputs",
271        input.program.inputs().len(),
272        active_inputs.len(),
273    )?;
274    validate_activity(
275        SemanticTransformRole::Vjp,
276        "active_outputs",
277        input.program.outputs().len(),
278        active_outputs.len(),
279    )?;
280    let mut builder = SemanticProgramBuilder::new();
281    let mut values = import_source(input, &mut builder)?;
282    let forward_active = requested_input_reachability(input, active_inputs);
283    let mut cotangents = HashMap::new();
284    let mut derivative_input_indices = vec![None; input.program.outputs().len()];
285    let mut next_input = input.program.inputs().len();
286    for (index, source) in input.program.outputs().iter().copied().enumerate() {
287        if active_outputs[index] {
288            let imported_source = values[&source];
289            let cotangent = builder.input(ProgramInputSpec::from_metadata(
290                builder.value_metadata(imported_source)?.clone(),
291            ))?;
292            derivative_input_indices[index] = Some(next_input);
293            next_input += 1;
294            accumulate_cotangent(&mut builder, &mut cotangents, source, cotangent)?;
295        }
296    }
297
298    let mut saved_input_indices = Vec::with_capacity(saved_outputs.len());
299    for &output_index in saved_outputs {
300        // INVARIANT: the eager caller supplies indices of the residual roots it
301        // appended to this source program, never user-provided indices.
302        let source = input.program.outputs()[output_index];
303        let imported = values[&source];
304        let saved = builder.input(ProgramInputSpec::from_metadata(
305            builder.value_metadata(imported)?.clone(),
306        ))?;
307        saved_input_indices.push(next_input);
308        next_input += 1;
309        values.insert(source, saved);
310    }
311
312    let operations: Vec<_> = input.program.operations().collect();
313    for operation in operations.into_iter().rev() {
314        let cotangent_outputs: Vec<_> = operation
315            .outputs()
316            .iter()
317            .map(|value| {
318                cotangents
319                    .get(value)
320                    .copied()
321                    .map_or(AdValue::Absent, AdValue::Value)
322            })
323            .collect();
324        if cotangent_outputs
325            .iter()
326            .all(|value| matches!(value, AdValue::Absent))
327        {
328            continue;
329        }
330        let active_operation_inputs: Vec<_> = operation
331            .inputs()
332            .iter()
333            .map(|value| forward_active.contains(value))
334            .collect();
335        if active_operation_inputs.iter().all(|active| !active) {
336            continue;
337        }
338        let cotangent_inputs = match operation.op() {
339            SemanticOpRef::Extension(op) => {
340                if rules.lookup_primal_vjp(op.family_id()).is_some() {
341                    rules.primal_vjp_operation(
342                        operation,
343                        &mapped_values(operation.inputs(), &values),
344                        &mapped_values(operation.outputs(), &values),
345                        &cotangent_outputs,
346                        &active_operation_inputs,
347                        &mut builder,
348                    )?
349                } else {
350                    let inactive_tangents = vec![AdValue::Absent; operation.inputs().len()];
351                    let active_operation_outputs: Vec<_> = cotangent_outputs
352                        .iter()
353                        .map(|value| matches!(value, AdValue::Value(_)))
354                        .collect();
355                    let linearized = rules.linearize_operation(
356                        operation,
357                        &mapped_values(operation.inputs(), &values),
358                        &mapped_values(operation.outputs(), &values),
359                        &inactive_tangents,
360                        &active_operation_outputs,
361                        &mut builder,
362                    )?;
363                    rules.linear_transpose_operation(
364                        operation,
365                        &mapped_values(operation.inputs(), &values),
366                        &mapped_values(operation.outputs(), &values),
367                        &cotangent_outputs,
368                        &active_operation_inputs,
369                        linearized.residuals(),
370                        &mut builder,
371                    )?
372                }
373            }
374            SemanticOpRef::Core(op) => vjp_core(
375                op,
376                &mapped_values(operation.inputs(), &values),
377                &mapped_values(operation.outputs(), &values),
378                &cotangent_outputs,
379                &active_operation_inputs,
380                &mut builder,
381            )?,
382            _ => {
383                return Err(SemanticAdTransformError::UnsupportedOperationVariant {
384                    role: SemanticTransformRole::Vjp,
385                });
386            }
387        };
388        for (source, cotangent) in operation.inputs().iter().copied().zip(cotangent_inputs) {
389            if let AdValue::Value(cotangent) = cotangent {
390                accumulate_cotangent(&mut builder, &mut cotangents, source, cotangent)?;
391            }
392        }
393    }
394
395    let outputs = input
396        .program
397        .inputs()
398        .iter()
399        .enumerate()
400        .map(|(index, value)| {
401            if active_inputs[index] {
402                cotangents
403                    .get(value)
404                    .copied()
405                    .map_or(AdValue::Absent, AdValue::Value)
406            } else {
407                AdValue::Absent
408            }
409        })
410        .collect();
411    Ok((
412        finish_derivative(builder, derivative_input_indices, outputs)?,
413        saved_input_indices,
414    ))
415}
416
417fn import_source(
418    input: &FrozenProgram,
419    builder: &mut SemanticProgramBuilder,
420) -> Result<HashMap<ProgramValue, ProgramValue>, SemanticAdTransformError> {
421    let mut source_values = input.program.inputs().to_vec();
422    source_values.extend(
423        input
424            .program
425            .operations()
426            .flat_map(|operation| operation.outputs().iter().copied()),
427    );
428    // The import keeps the source's symbolic extents and only re-attaches the
429    // bindings, so a rule that emits a literal length (pad, slice, concatenate)
430    // reads it from the binding rather than making the whole derivative program
431    // concrete. `Reshape`/`BroadcastInDim` payloads therefore stay symbolic, and the
432    // final import maps these inputs back onto the live traced values.
433    let imported = builder.import(ProgramImport {
434        program: input.program.as_ref(),
435        bindings: Some(&input.bindings),
436        roots: &source_values,
437        input_map: &[],
438    })?;
439    Ok(source_values
440        .into_iter()
441        .zip(imported.roots().iter().copied())
442        .collect())
443}
444
445fn mapped_values(
446    source: &[ProgramValue],
447    values: &HashMap<ProgramValue, ProgramValue>,
448) -> Vec<ProgramValue> {
449    source.iter().map(|value| values[value]).collect()
450}
451
452fn source_output_liveness(input: &FrozenProgram) -> HashSet<ProgramValue> {
453    let mut live: HashSet<_> = input.program.outputs().iter().copied().collect();
454    let operations: Vec<_> = input.program.operations().collect();
455    for operation in operations.into_iter().rev() {
456        if operation
457            .outputs()
458            .iter()
459            .any(|output| live.contains(output))
460        {
461            live.extend(operation.inputs().iter().copied());
462        }
463    }
464    live
465}
466
467fn requested_input_reachability(
468    input: &FrozenProgram,
469    active_inputs: &[bool],
470) -> HashSet<ProgramValue> {
471    let mut active: HashSet<_> = input
472        .program
473        .inputs()
474        .iter()
475        .copied()
476        .zip(active_inputs.iter().copied())
477        .filter_map(|(value, is_active)| is_active.then_some(value))
478        .collect();
479    for operation in input.program.operations() {
480        if operation
481            .inputs()
482            .iter()
483            .any(|value| active.contains(value))
484        {
485            active.extend(operation.outputs().iter().copied());
486        }
487    }
488    active
489}
490
491fn accumulate_cotangent(
492    builder: &mut SemanticProgramBuilder,
493    cotangents: &mut HashMap<ProgramValue, ProgramValue>,
494    source: ProgramValue,
495    cotangent: ProgramValue,
496) -> Result<(), ProgramBuildError> {
497    let combined = if let Some(existing) = cotangents.get(&source).copied() {
498        builder.add_op(CoreSemanticOp::Add, &[existing, cotangent])?[0]
499    } else {
500        cotangent
501    };
502    cotangents.insert(source, combined);
503    Ok(())
504}
505
506fn linearize_core(
507    op: &CoreSemanticOp,
508    primal_inputs: &[ProgramValue],
509    tangent_inputs: &[AdValue],
510    builder: &mut SemanticProgramBuilder,
511) -> Result<Box<[AdValue]>, SemanticAdTransformError> {
512    let output = match op {
513        CoreSemanticOp::Add => add_ad_values(builder, tangent_inputs[0], tangent_inputs[1])?,
514        CoreSemanticOp::Sub => sub_ad_values(builder, tangent_inputs[0], tangent_inputs[1])?,
515        CoreSemanticOp::Mul => {
516            let lhs = multiply_ad_value(builder, tangent_inputs[0], primal_inputs[1])?;
517            let rhs = multiply_ad_value(builder, tangent_inputs[1], primal_inputs[0])?;
518            add_ad_values(builder, lhs, rhs)?
519        }
520        CoreSemanticOp::Div => {
521            let lhs = divide_ad_value(builder, tangent_inputs[0], primal_inputs[1])?;
522            let rhs_numerator = multiply_ad_value(builder, tangent_inputs[1], primal_inputs[0])?;
523            let denominator =
524                builder.add_op(CoreSemanticOp::Mul, &[primal_inputs[1], primal_inputs[1]])?[0];
525            let rhs = divide_ad_value(builder, rhs_numerator, denominator)?;
526            sub_ad_values(builder, lhs, rhs)?
527        }
528        CoreSemanticOp::Pow => {
529            let lhs = if matches!(tangent_inputs[0], AdValue::Value(_)) {
530                let one = one_like(builder, primal_inputs[1], SemanticTransformRole::Jvp)?;
531                let exponent_minus_one =
532                    builder.add_op(CoreSemanticOp::Sub, &[primal_inputs[1], one])?[0];
533                let power = builder
534                    .add_op(CoreSemanticOp::Pow, &[primal_inputs[0], exponent_minus_one])?[0];
535                let coefficient =
536                    builder.add_op(CoreSemanticOp::Mul, &[primal_inputs[1], power])?[0];
537                multiply_ad_value(builder, tangent_inputs[0], coefficient)?
538            } else {
539                AdValue::Absent
540            };
541            let rhs = if matches!(tangent_inputs[1], AdValue::Value(_)) {
542                let log = builder.add_op(CoreSemanticOp::Log, &[primal_inputs[0]])?[0];
543                let power =
544                    builder.add_op(CoreSemanticOp::Pow, &[primal_inputs[0], primal_inputs[1]])?[0];
545                let coefficient = builder.add_op(CoreSemanticOp::Mul, &[log, power])?[0];
546                multiply_ad_value(builder, tangent_inputs[1], coefficient)?
547            } else {
548                AdValue::Absent
549            };
550            add_ad_values(builder, lhs, rhs)?
551        }
552        CoreSemanticOp::DotGeneral { config } => {
553            linearize_dot_general(builder, primal_inputs, tangent_inputs, config)?
554        }
555        CoreSemanticOp::Abs => {
556            let input_dtype = builder.value_metadata(primal_inputs[0])?.dtype();
557            let sign = builder.add_op(CoreSemanticOp::Sign, &[primal_inputs[0]])?[0];
558            let coefficient = if is_complex_dtype(input_dtype) {
559                builder.add_op(CoreSemanticOp::Conj, &[sign])?[0]
560            } else {
561                sign
562            };
563            let tangent = multiply_ad_value(builder, tangent_inputs[0], coefficient)?;
564            convert_ad_value(builder, tangent, input_dtype, abs_output_dtype(input_dtype))?
565        }
566        CoreSemanticOp::Sign => linearize_sign(builder, primal_inputs[0], tangent_inputs[0])?,
567        CoreSemanticOp::Maximum | CoreSemanticOp::Minimum => {
568            linearize_extrema(builder, op, primal_inputs, tangent_inputs)?
569        }
570        CoreSemanticOp::Select => select_ad_values(
571            builder,
572            primal_inputs[0],
573            tangent_inputs[1],
574            tangent_inputs[2],
575        )?,
576        CoreSemanticOp::Clamp => linearize_clamp(builder, primal_inputs, tangent_inputs)?,
577        CoreSemanticOp::Neg | CoreSemanticOp::Conj => {
578            unary_ad_value(builder, op.clone(), tangent_inputs[0])?
579        }
580        CoreSemanticOp::Exp
581        | CoreSemanticOp::Log
582        | CoreSemanticOp::Sin
583        | CoreSemanticOp::Cos
584        | CoreSemanticOp::Tanh
585        | CoreSemanticOp::Sqrt
586        | CoreSemanticOp::Rsqrt
587        | CoreSemanticOp::Expm1
588        | CoreSemanticOp::Log1p
589        | CoreSemanticOp::Erf => {
590            linearize_analytic_unary(builder, op, primal_inputs[0], tangent_inputs[0])?
591        }
592        CoreSemanticOp::Transpose { .. }
593        | CoreSemanticOp::Reshape { .. }
594        | CoreSemanticOp::BroadcastInDim { .. }
595        | CoreSemanticOp::ReduceSum { .. }
596        | CoreSemanticOp::ExtractDiag { .. }
597        | CoreSemanticOp::EmbedDiag { .. }
598        | CoreSemanticOp::Tril { .. }
599        | CoreSemanticOp::Triu { .. }
600        | CoreSemanticOp::Slice(_)
601        | CoreSemanticOp::Pad(_)
602        | CoreSemanticOp::Reverse { .. } => {
603            linearize_unary_core(builder, op.clone(), primal_inputs, tangent_inputs[0])?
604        }
605        CoreSemanticOp::ReduceSumSquares { axes } => core_reductions::linearize_sum_squares(
606            builder,
607            primal_inputs[0],
608            tangent_inputs[0],
609            axes,
610        )?,
611        CoreSemanticOp::Concatenate { axis, input_count } => {
612            linearize_concatenate(builder, primal_inputs, tangent_inputs, *axis, *input_count)?
613        }
614        CoreSemanticOp::Gather(_)
615        | CoreSemanticOp::GatherDynamicSliceSizes { .. }
616        | CoreSemanticOp::Scatter(_)
617        | CoreSemanticOp::DynamicSlice { .. }
618        | CoreSemanticOp::DynamicUpdateSlice => {
619            linearize_indexing(builder, op, primal_inputs, tangent_inputs)?
620        }
621        CoreSemanticOp::DynamicTruncate { .. } | CoreSemanticOp::PadToMatch { .. } => {
622            linearize_dynamic_shape(builder, op, primal_inputs, tangent_inputs[0])?
623        }
624        CoreSemanticOp::Convert { from, to } => {
625            if is_differentiable_dtype(*from) && is_differentiable_dtype(*to) {
626                linearize_unary_core(builder, op.clone(), primal_inputs, tangent_inputs[0])?
627            } else {
628                AdValue::Absent
629            }
630        }
631        CoreSemanticOp::ReduceProd { .. }
632        | CoreSemanticOp::ReduceMax { .. }
633        | CoreSemanticOp::ReduceMin { .. } => {
634            linearize_nonlinear_reduction(builder, op, primal_inputs, tangent_inputs[0])?
635        }
636        CoreSemanticOp::Rem => linearize_rem(builder, primal_inputs, tangent_inputs)?,
637        CoreSemanticOp::Compare(_)
638        | CoreSemanticOp::ShapeOf { .. }
639        | CoreSemanticOp::Constant { .. } => AdValue::Absent,
640        _ => return Err(unsupported_core(SemanticTransformRole::Jvp, op)),
641    };
642    Ok([output].into())
643}
644
645// These direct semantic VJPs consume outputs, unlike the lower-level linear
646// transpose adapters, whose residual contract exposes only their inputs.
647pub(crate) fn eager_core_residual_spec(
648    op: &tenferro_ops::std_tensor_op::StdTensorOp,
649) -> crate::semantic_extension::ResidualSpec {
650    use tenferro_ops::std_tensor_op::StdTensorOp;
651    match op {
652        StdTensorOp::Exp | StdTensorOp::Tanh => crate::semantic_extension::ResidualSpec::output(0),
653        _ => tenferro_ops::ad::primitive_residual_spec(op).unwrap_or_default(),
654    }
655}
656
657fn vjp_core(
658    op: &CoreSemanticOp,
659    primal_inputs: &[ProgramValue],
660    primal_outputs: &[ProgramValue],
661    cotangent_outputs: &[AdValue],
662    active_inputs: &[bool],
663    builder: &mut SemanticProgramBuilder,
664) -> Result<Box<[AdValue]>, SemanticAdTransformError> {
665    let cotangent = cotangent_outputs[0];
666    let inputs = match op {
667        CoreSemanticOp::Add => vec![
668            active_cotangent(builder, cotangent, active_inputs[0], primal_inputs[0])?,
669            active_cotangent(builder, cotangent, active_inputs[1], primal_inputs[1])?,
670        ],
671        CoreSemanticOp::Sub => {
672            let negated = unary_ad_value(builder, CoreSemanticOp::Neg, cotangent)?;
673            vec![
674                active_cotangent(builder, cotangent, active_inputs[0], primal_inputs[0])?,
675                normalize_ad_value(builder, negated, active_inputs[1], primal_inputs[1])?,
676            ]
677        }
678        CoreSemanticOp::Mul => {
679            let rhs_coefficient = conjugate_if_complex(builder, primal_inputs[1])?;
680            let lhs_coefficient = conjugate_if_complex(builder, primal_inputs[0])?;
681            let lhs = multiply_ad_value(builder, cotangent, rhs_coefficient)?;
682            let rhs = multiply_ad_value(builder, cotangent, lhs_coefficient)?;
683            vec![
684                normalize_ad_value(builder, lhs, active_inputs[0], primal_inputs[0])?,
685                normalize_ad_value(builder, rhs, active_inputs[1], primal_inputs[1])?,
686            ]
687        }
688        CoreSemanticOp::Div => {
689            let rhs_coefficient = conjugate_if_complex(builder, primal_inputs[1])?;
690            let lhs = divide_ad_value(builder, cotangent, rhs_coefficient)?;
691            let lhs_coefficient = conjugate_if_complex(builder, primal_inputs[0])?;
692            let denominator =
693                builder.add_op(CoreSemanticOp::Mul, &[rhs_coefficient, rhs_coefficient])?[0];
694            let rhs = multiply_ad_value(builder, cotangent, lhs_coefficient)?;
695            let rhs = divide_ad_value(builder, rhs, denominator)?;
696            let rhs = unary_ad_value(builder, CoreSemanticOp::Neg, rhs)?;
697            vec![
698                normalize_ad_value(builder, lhs, active_inputs[0], primal_inputs[0])?,
699                normalize_ad_value(builder, rhs, active_inputs[1], primal_inputs[1])?,
700            ]
701        }
702        CoreSemanticOp::Pow => {
703            let lhs = if active_inputs[0] {
704                let one = one_like(builder, primal_inputs[1], SemanticTransformRole::Vjp)?;
705                let exponent_minus_one =
706                    builder.add_op(CoreSemanticOp::Sub, &[primal_inputs[1], one])?[0];
707                let power = builder
708                    .add_op(CoreSemanticOp::Pow, &[primal_inputs[0], exponent_minus_one])?[0];
709                let coefficient =
710                    builder.add_op(CoreSemanticOp::Mul, &[primal_inputs[1], power])?[0];
711                let coefficient = conjugate_if_complex(builder, coefficient)?;
712                multiply_ad_value(builder, cotangent, coefficient)?
713            } else {
714                AdValue::Absent
715            };
716            let rhs = if active_inputs[1] {
717                let log = builder.add_op(CoreSemanticOp::Log, &[primal_inputs[0]])?[0];
718                let power =
719                    builder.add_op(CoreSemanticOp::Pow, &[primal_inputs[0], primal_inputs[1]])?[0];
720                let coefficient = builder.add_op(CoreSemanticOp::Mul, &[log, power])?[0];
721                let coefficient = conjugate_if_complex(builder, coefficient)?;
722                multiply_ad_value(builder, cotangent, coefficient)?
723            } else {
724                AdValue::Absent
725            };
726            vec![
727                normalize_ad_value(builder, lhs, active_inputs[0], primal_inputs[0])?,
728                normalize_ad_value(builder, rhs, active_inputs[1], primal_inputs[1])?,
729            ]
730        }
731        CoreSemanticOp::DotGeneral { config } => {
732            dot_general_vjp(builder, primal_inputs, cotangent, active_inputs, config)?
733        }
734        CoreSemanticOp::Abs => {
735            let input_dtype = builder.value_metadata(primal_inputs[0])?.dtype();
736            let output_dtype = abs_output_dtype(input_dtype);
737            let cotangent = convert_ad_value(builder, cotangent, output_dtype, input_dtype)?;
738            let sign = builder.add_op(CoreSemanticOp::Sign, &[primal_inputs[0]])?[0];
739            let cotangent = multiply_ad_value(builder, cotangent, sign)?;
740            vec![normalize_ad_value(
741                builder,
742                cotangent,
743                active_inputs[0],
744                primal_inputs[0],
745            )?]
746        }
747        CoreSemanticOp::Sign => vec![AdValue::Absent],
748        CoreSemanticOp::Maximum | CoreSemanticOp::Minimum => {
749            extrema_vjp(builder, op, primal_inputs, cotangent, active_inputs)?
750        }
751        CoreSemanticOp::Select => {
752            let (on_true, on_false) = split_select_cotangent(
753                builder,
754                primal_inputs[0],
755                cotangent,
756                active_inputs[1],
757                active_inputs[2],
758            )?;
759            vec![
760                AdValue::Absent,
761                normalize_ad_value(builder, on_true, active_inputs[1], primal_inputs[1])?,
762                normalize_ad_value(builder, on_false, active_inputs[2], primal_inputs[2])?,
763            ]
764        }
765        CoreSemanticOp::Clamp => clamp_vjp(builder, primal_inputs, cotangent, active_inputs)?,
766        CoreSemanticOp::Neg => {
767            let negated = unary_ad_value(builder, CoreSemanticOp::Neg, cotangent)?;
768            vec![normalize_ad_value(
769                builder,
770                negated,
771                active_inputs[0],
772                primal_inputs[0],
773            )?]
774        }
775        CoreSemanticOp::Conj => {
776            let conjugated = unary_ad_value(builder, CoreSemanticOp::Conj, cotangent)?;
777            vec![normalize_ad_value(
778                builder,
779                conjugated,
780                active_inputs[0],
781                primal_inputs[0],
782            )?]
783        }
784        CoreSemanticOp::Exp
785        | CoreSemanticOp::Log
786        | CoreSemanticOp::Sin
787        | CoreSemanticOp::Cos
788        | CoreSemanticOp::Tanh
789        | CoreSemanticOp::Sqrt
790        | CoreSemanticOp::Rsqrt
791        | CoreSemanticOp::Expm1
792        | CoreSemanticOp::Log1p
793        | CoreSemanticOp::Erf => {
794            let coefficient = match op {
795                CoreSemanticOp::Exp => primal_outputs[0],
796                CoreSemanticOp::Tanh => {
797                    let y = primal_outputs[0];
798                    let square = builder.add_op(CoreSemanticOp::Mul, &[y, y])?[0];
799                    let one = one_like(builder, y, SemanticTransformRole::Vjp)?;
800                    builder.add_op(CoreSemanticOp::Sub, &[one, square])?[0]
801                }
802                _ => analytic_unary_coefficient(
803                    builder,
804                    op,
805                    primal_inputs[0],
806                    SemanticTransformRole::Vjp,
807                )?,
808            };
809            let coefficient = conjugate_if_complex(builder, coefficient)?;
810            let cotangent = multiply_ad_value(builder, cotangent, coefficient)?;
811            vec![normalize_ad_value(
812                builder,
813                cotangent,
814                active_inputs[0],
815                primal_inputs[0],
816            )?]
817        }
818        CoreSemanticOp::Transpose { perm } => {
819            let transposed = unary_ad_value(
820                builder,
821                CoreSemanticOp::Transpose {
822                    perm: inverse_permutation(perm),
823                },
824                cotangent,
825            )?;
826            primary_cotangent(builder, transposed, active_inputs, primal_inputs, false)?
827        }
828        CoreSemanticOp::Reshape { .. } => {
829            let reshaped = reshape_ad_value_to_input(builder, cotangent, primal_inputs[0])?;
830            primary_cotangent(builder, reshaped, active_inputs, primal_inputs, false)?
831        }
832        CoreSemanticOp::BroadcastInDim { dims, .. } => {
833            let reduced =
834                transpose_broadcast(builder, cotangent, primal_inputs[0], dims.as_slice())?;
835            primary_cotangent(builder, reduced, active_inputs, primal_inputs, false)?
836        }
837        CoreSemanticOp::Convert { from, to } => {
838            let converted = if is_differentiable_dtype(*from) && is_differentiable_dtype(*to) {
839                unary_ad_value(
840                    builder,
841                    CoreSemanticOp::Convert {
842                        from: *to,
843                        to: *from,
844                    },
845                    cotangent,
846                )?
847            } else {
848                AdValue::Absent
849            };
850            primary_cotangent(builder, converted, active_inputs, primal_inputs, false)?
851        }
852        CoreSemanticOp::ReduceSum { axes } => {
853            let input_shape = value_shape_plan(
854                builder,
855                primal_inputs[0],
856                SemanticTransformRole::Vjp,
857                "reduce-sum input",
858            )?;
859            let dims: Vec<usize> = (0..input_shape.shape.len())
860                .filter(|axis| !axes.contains(axis))
861                .collect();
862            let broadcast =
863                broadcast_ad_value_in_dim_to_shape(builder, cotangent, &input_shape, dims)?;
864            let broadcast = truncate_ad_value_to_dynamic_axes(
865                builder,
866                broadcast,
867                primal_inputs[0],
868                &input_shape.dynamic_axes,
869            )?;
870            primary_cotangent(builder, broadcast, active_inputs, primal_inputs, false)?
871        }
872        CoreSemanticOp::ReduceSumSquares { axes } => core_reductions::sum_squares_vjp(
873            builder,
874            primal_inputs[0],
875            cotangent,
876            active_inputs[0],
877            axes,
878        )?,
879        CoreSemanticOp::ExtractDiag { axis_a, axis_b } => {
880            let embedded = unary_ad_value(
881                builder,
882                CoreSemanticOp::EmbedDiag {
883                    axis_a: if axis_a < axis_b { *axis_a } else { axis_a - 1 },
884                    axis_b: *axis_b,
885                },
886                cotangent,
887            )?;
888            let padded = match embedded {
889                AdValue::Absent => AdValue::Absent,
890                AdValue::Value(value) => {
891                    let value = builder.add_op(
892                        CoreSemanticOp::PadToMatch { axis: *axis_a },
893                        &[value, primal_inputs[0]],
894                    )?[0];
895                    AdValue::Value(
896                        builder.add_op(
897                            CoreSemanticOp::PadToMatch { axis: *axis_b },
898                            &[value, primal_inputs[0]],
899                        )?[0],
900                    )
901                }
902            };
903            primary_cotangent(builder, padded, active_inputs, primal_inputs, false)?
904        }
905        CoreSemanticOp::EmbedDiag { axis_a, axis_b } => {
906            let source_axis = if axis_b <= axis_a {
907                axis_a + 1
908            } else {
909                *axis_a
910            };
911            let extracted = unary_ad_value(
912                builder,
913                CoreSemanticOp::ExtractDiag {
914                    axis_a: source_axis,
915                    axis_b: *axis_b,
916                },
917                cotangent,
918            )?;
919            primary_cotangent(builder, extracted, active_inputs, primal_inputs, false)?
920        }
921        CoreSemanticOp::Tril { .. }
922        | CoreSemanticOp::Triu { .. }
923        | CoreSemanticOp::Reverse { .. } => {
924            let transformed = unary_ad_value(builder, op.clone(), cotangent)?;
925            primary_cotangent(builder, transformed, active_inputs, primal_inputs, false)?
926        }
927        CoreSemanticOp::Slice(config) => slice_vjp(
928            builder,
929            primal_inputs[0],
930            cotangent,
931            active_inputs[0],
932            config,
933        )?,
934        CoreSemanticOp::Pad(config) => pad_vjp(
935            builder,
936            primal_inputs[0],
937            cotangent,
938            active_inputs[0],
939            config,
940        )?,
941        CoreSemanticOp::Concatenate { axis, input_count } => concatenate_vjp(
942            builder,
943            primal_inputs,
944            cotangent,
945            active_inputs,
946            *axis,
947            *input_count,
948        )?,
949        CoreSemanticOp::Gather(_)
950        | CoreSemanticOp::GatherDynamicSliceSizes { .. }
951        | CoreSemanticOp::Scatter(_)
952        | CoreSemanticOp::DynamicSlice { .. }
953        | CoreSemanticOp::DynamicUpdateSlice => {
954            indexing_vjp(builder, op, primal_inputs, cotangent, active_inputs)?
955        }
956        CoreSemanticOp::DynamicTruncate { .. } | CoreSemanticOp::PadToMatch { .. } => {
957            dynamic_shape_vjp(builder, op, primal_inputs, cotangent, active_inputs)?
958        }
959        CoreSemanticOp::ReduceProd { .. }
960        | CoreSemanticOp::ReduceMax { .. }
961        | CoreSemanticOp::ReduceMin { .. } => {
962            nonlinear_reduction_vjp(builder, op, primal_inputs, cotangent, active_inputs[0])?
963        }
964        CoreSemanticOp::Rem => rem_vjp(builder, primal_inputs, cotangent, active_inputs)?,
965        CoreSemanticOp::Compare(_) => vec![AdValue::Absent, AdValue::Absent],
966        CoreSemanticOp::ShapeOf { .. } => vec![AdValue::Absent],
967        CoreSemanticOp::Constant { .. } => Vec::new(),
968        _ => return Err(unsupported_core(SemanticTransformRole::Vjp, op)),
969    };
970    Ok(inputs.into_boxed_slice())
971}
972
973fn linearize_unary_core(
974    builder: &mut SemanticProgramBuilder,
975    op: CoreSemanticOp,
976    primal_inputs: &[ProgramValue],
977    tangent: AdValue,
978) -> Result<AdValue, ProgramBuildError> {
979    let AdValue::Value(tangent) = tangent else {
980        return Ok(AdValue::Absent);
981    };
982    let mut inputs = Vec::with_capacity(primal_inputs.len());
983    inputs.push(tangent);
984    inputs.extend_from_slice(&primal_inputs[1..]);
985    Ok(AdValue::Value(builder.add_op(op, &inputs)?[0]))
986}
987
988fn linearize_dot_general(
989    builder: &mut SemanticProgramBuilder,
990    primal_inputs: &[ProgramValue],
991    tangent_inputs: &[AdValue],
992    config: &DotGeneralConfig,
993) -> Result<AdValue, SemanticAdTransformError> {
994    validate_dot_general_metadata(builder, primal_inputs, config, SemanticTransformRole::Jvp)?;
995    let mut terms = Vec::with_capacity(2);
996    if let AdValue::Value(tangent) = tangent_inputs[0] {
997        terms.push(
998            builder.add_op(
999                CoreSemanticOp::DotGeneral {
1000                    config: config.clone(),
1001                },
1002                &[tangent, primal_inputs[1]],
1003            )?[0],
1004        );
1005    }
1006    if let AdValue::Value(tangent) = tangent_inputs[1] {
1007        terms.push(
1008            builder.add_op(
1009                CoreSemanticOp::DotGeneral {
1010                    config: config.clone(),
1011                },
1012                &[primal_inputs[0], tangent],
1013            )?[0],
1014        );
1015    }
1016    let mut terms = terms.into_iter();
1017    let Some(mut result) = terms.next() else {
1018        return Ok(AdValue::Absent);
1019    };
1020    for term in terms {
1021        result = builder.add_op(CoreSemanticOp::Add, &[result, term])?[0];
1022    }
1023    Ok(AdValue::Value(result))
1024}
1025
1026fn dot_general_vjp(
1027    builder: &mut SemanticProgramBuilder,
1028    primal_inputs: &[ProgramValue],
1029    cotangent: AdValue,
1030    active_inputs: &[bool],
1031    config: &DotGeneralConfig,
1032) -> Result<Vec<AdValue>, SemanticAdTransformError> {
1033    let (lhs_rank, rhs_rank) =
1034        validate_dot_general_metadata(builder, primal_inputs, config, SemanticTransformRole::Vjp)?;
1035    let lhs_free = dot_general_free_dims(
1036        lhs_rank,
1037        &config.lhs_contracting_dims,
1038        &config.lhs_batch_dims,
1039        SemanticTransformRole::Vjp,
1040    )?;
1041    let rhs_free = dot_general_free_dims(
1042        rhs_rank,
1043        &config.rhs_contracting_dims,
1044        &config.rhs_batch_dims,
1045        SemanticTransformRole::Vjp,
1046    )?;
1047    let AdValue::Value(cotangent) = cotangent else {
1048        return Ok(vec![AdValue::Absent, AdValue::Absent]);
1049    };
1050    let mut result = vec![AdValue::Absent, AdValue::Absent];
1051
1052    if active_inputs[0] {
1053        let rhs = conjugate_if_complex(builder, primal_inputs[1])?;
1054        let (transpose_config, perm) =
1055            dot_general_transpose_plan_for_lhs(config, lhs_rank, rhs_rank, &lhs_free, &rhs_free)?;
1056        let value = builder.add_op(
1057            CoreSemanticOp::DotGeneral {
1058                config: transpose_config,
1059            },
1060            &[cotangent, rhs],
1061        )?[0];
1062        let value = transpose_if_needed(builder, value, &perm)?;
1063        result[0] = normalize_ad_value(builder, AdValue::Value(value), true, primal_inputs[0])?;
1064    }
1065    if active_inputs[1] {
1066        let lhs = conjugate_if_complex(builder, primal_inputs[0])?;
1067        let (transpose_config, perm) =
1068            dot_general_transpose_plan_for_rhs(config, lhs_rank, rhs_rank, &lhs_free, &rhs_free)?;
1069        let value = builder.add_op(
1070            CoreSemanticOp::DotGeneral {
1071                config: transpose_config,
1072            },
1073            &[lhs, cotangent],
1074        )?[0];
1075        let value = transpose_if_needed(builder, value, &perm)?;
1076        result[1] = normalize_ad_value(builder, AdValue::Value(value), true, primal_inputs[1])?;
1077    }
1078    Ok(result)
1079}
1080
1081fn validate_dot_general_metadata(
1082    builder: &SemanticProgramBuilder,
1083    primal_inputs: &[ProgramValue],
1084    config: &DotGeneralConfig,
1085    role: SemanticTransformRole,
1086) -> Result<(usize, usize), SemanticAdTransformError> {
1087    let lhs_rank = builder.value_metadata(primal_inputs[0])?.shape().len();
1088    let rhs_rank = builder.value_metadata(primal_inputs[1])?.shape().len();
1089    config
1090        .validate_dims_with_ranks(lhs_rank, rhs_rank)
1091        .map_err(|error| SemanticAdTransformError::UnsupportedMetadata {
1092            role,
1093            message: format!(
1094                "invalid dot_general dimensions for ranks {lhs_rank} and {rhs_rank}: {error}"
1095            ),
1096        })?;
1097    Ok((lhs_rank, rhs_rank))
1098}
1099
1100fn dot_general_free_dims(
1101    rank: usize,
1102    contracting: &[usize],
1103    batch: &[usize],
1104    role: SemanticTransformRole,
1105) -> Result<Vec<usize>, SemanticAdTransformError> {
1106    let mut bound = vec![false; rank];
1107    for &axis in batch.iter().chain(contracting) {
1108        let Some(slot) = bound.get_mut(axis) else {
1109            return Err(SemanticAdTransformError::UnsupportedMetadata {
1110                role,
1111                message: format!("dot_general axis {axis} is out of bounds for rank {rank}"),
1112            });
1113        };
1114        *slot = true;
1115    }
1116    Ok((0..rank).filter(|axis| !bound[*axis]).collect())
1117}
1118
1119fn dot_general_transpose_plan_for_lhs(
1120    config: &DotGeneralConfig,
1121    lhs_rank: usize,
1122    rhs_rank: usize,
1123    lhs_free: &[usize],
1124    rhs_free: &[usize],
1125) -> Result<(DotGeneralConfig, Vec<usize>), SemanticAdTransformError> {
1126    let batch_count = config.lhs_batch_dims.len();
1127    let output_rank = lhs_free.len() + rhs_free.len() + batch_count;
1128    let rhs_free_positions = (lhs_free.len()..lhs_free.len() + rhs_free.len()).collect();
1129    let rhs_contracting_order = dot_general_free_dims(
1130        rhs_rank,
1131        rhs_free,
1132        &config.rhs_batch_dims,
1133        SemanticTransformRole::Vjp,
1134    )?;
1135    let mut result_order = lhs_free.to_vec();
1136    for rhs_axis in rhs_contracting_order {
1137        let Some(pair) = config
1138            .rhs_contracting_dims
1139            .iter()
1140            .position(|&axis| axis == rhs_axis)
1141        else {
1142            return Err(dot_general_transpose_metadata_error(format!(
1143                "rhs contracting axis {rhs_axis} has no lhs pair"
1144            )));
1145        };
1146        result_order.push(config.lhs_contracting_dims[pair]);
1147    }
1148    result_order.extend(config.lhs_batch_dims.iter().copied());
1149    Ok((
1150        DotGeneralConfig {
1151            lhs_contracting_dims: rhs_free_positions,
1152            rhs_contracting_dims: rhs_free.into(),
1153            lhs_batch_dims: (lhs_free.len() + rhs_free.len()..output_rank).collect(),
1154            rhs_batch_dims: config.rhs_batch_dims.clone(),
1155        },
1156        permutation_to_original_order(lhs_rank, &result_order)?,
1157    ))
1158}
1159
1160fn dot_general_transpose_plan_for_rhs(
1161    config: &DotGeneralConfig,
1162    lhs_rank: usize,
1163    rhs_rank: usize,
1164    lhs_free: &[usize],
1165    rhs_free: &[usize],
1166) -> Result<(DotGeneralConfig, Vec<usize>), SemanticAdTransformError> {
1167    let batch_count = config.lhs_batch_dims.len();
1168    let lhs_contracting_order = dot_general_free_dims(
1169        lhs_rank,
1170        lhs_free,
1171        &config.lhs_batch_dims,
1172        SemanticTransformRole::Vjp,
1173    )?;
1174    let mut result_order = Vec::with_capacity(rhs_rank);
1175    for lhs_axis in lhs_contracting_order {
1176        let Some(pair) = config
1177            .lhs_contracting_dims
1178            .iter()
1179            .position(|&axis| axis == lhs_axis)
1180        else {
1181            return Err(dot_general_transpose_metadata_error(format!(
1182                "lhs contracting axis {lhs_axis} has no rhs pair"
1183            )));
1184        };
1185        result_order.push(config.rhs_contracting_dims[pair]);
1186    }
1187    result_order.extend(rhs_free.iter().copied());
1188    result_order.extend(config.rhs_batch_dims.iter().copied());
1189    let output_rank = lhs_free.len() + rhs_free.len() + batch_count;
1190    Ok((
1191        DotGeneralConfig {
1192            lhs_contracting_dims: lhs_free.into(),
1193            rhs_contracting_dims: (0..lhs_free.len()).collect(),
1194            lhs_batch_dims: config.lhs_batch_dims.clone(),
1195            rhs_batch_dims: (lhs_free.len() + rhs_free.len()..output_rank).collect(),
1196        },
1197        permutation_to_original_order(rhs_rank, &result_order)?,
1198    ))
1199}
1200
1201fn permutation_to_original_order(
1202    rank: usize,
1203    result_order: &[usize],
1204) -> Result<Vec<usize>, SemanticAdTransformError> {
1205    let mut permutation = vec![0; rank];
1206    for (result_axis, &original_axis) in result_order.iter().enumerate() {
1207        let Some(slot) = permutation.get_mut(original_axis) else {
1208            return Err(dot_general_transpose_metadata_error(format!(
1209                "dot_general transpose axis {original_axis} is out of bounds for rank {rank}"
1210            )));
1211        };
1212        *slot = result_axis;
1213    }
1214    Ok(permutation)
1215}
1216
1217fn transpose_if_needed(
1218    builder: &mut SemanticProgramBuilder,
1219    value: ProgramValue,
1220    permutation: &[usize],
1221) -> Result<ProgramValue, ProgramBuildError> {
1222    if permutation
1223        .iter()
1224        .enumerate()
1225        .all(|(axis, &mapped)| axis == mapped)
1226    {
1227        Ok(value)
1228    } else {
1229        Ok(builder.add_op(
1230            CoreSemanticOp::Transpose {
1231                perm: permutation.to_vec(),
1232            },
1233            &[value],
1234        )?[0])
1235    }
1236}
1237
1238fn dot_general_transpose_metadata_error(message: String) -> SemanticAdTransformError {
1239    SemanticAdTransformError::UnsupportedMetadata {
1240        role: SemanticTransformRole::Vjp,
1241        message,
1242    }
1243}
1244
1245fn primary_cotangent(
1246    builder: &mut SemanticProgramBuilder,
1247    cotangent: AdValue,
1248    active_inputs: &[bool],
1249    primal_inputs: &[ProgramValue],
1250    normalize: bool,
1251) -> Result<Vec<AdValue>, SemanticAdTransformError> {
1252    let mut result = vec![AdValue::Absent; primal_inputs.len()];
1253    if active_inputs.first().copied().unwrap_or(false) {
1254        result[0] = if normalize {
1255            normalize_ad_value(builder, cotangent, true, primal_inputs[0])?
1256        } else {
1257            cotangent
1258        };
1259    }
1260    Ok(result)
1261}
1262
1263fn inverse_permutation(perm: &[usize]) -> Vec<usize> {
1264    let mut inverse = vec![0; perm.len()];
1265    for (axis, mapped) in perm.iter().copied().enumerate() {
1266        inverse[mapped] = axis;
1267    }
1268    inverse
1269}
1270
1271fn reshape_ad_value_to_input(
1272    builder: &mut SemanticProgramBuilder,
1273    value: AdValue,
1274    primal_input: ProgramValue,
1275) -> Result<AdValue, SemanticAdTransformError> {
1276    let shape = value_shape_plan(
1277        builder,
1278        primal_input,
1279        SemanticTransformRole::Vjp,
1280        "reshape input",
1281    )?;
1282    let reshaped = reshape_ad_value_to_shape(builder, value, &shape)?;
1283    truncate_ad_value_to_dynamic_axes(builder, reshaped, primal_input, &shape.dynamic_axes)
1284}
1285
1286/// Whether `value`'s `axis` is known to have extent 1.
1287///
1288/// The rule has to decide whether a broadcast expanded a singleton axis, so it
1289/// needs the length itself. A program imported for the transform keeps its symbolic
1290/// extents, so the answer comes from the binding when the declaration is symbolic;
1291/// the emitted payload still uses the symbolic expression.
1292fn axis_is_known_singleton(
1293    builder: &SemanticProgramBuilder,
1294    value: ProgramValue,
1295    axis: usize,
1296) -> bool {
1297    builder.resolved_extent(value, axis).is_ok_and(|extent| {
1298        matches!(
1299            extent,
1300            ShapeExtent::Exact(DimExpr::Const(1)) | ShapeExtent::UpperBound(DimExpr::Const(1))
1301        )
1302    })
1303}
1304
1305fn transpose_broadcast(
1306    builder: &mut SemanticProgramBuilder,
1307    value: AdValue,
1308    primal_input: ProgramValue,
1309    dims: &[usize],
1310) -> Result<AdValue, SemanticAdTransformError> {
1311    let AdValue::Value(mut value) = value else {
1312        return Ok(AdValue::Absent);
1313    };
1314    let input_shape = value_shape_plan(
1315        builder,
1316        primal_input,
1317        SemanticTransformRole::Vjp,
1318        "broadcast input",
1319    )?;
1320    let output_shape = value_shape_plan(
1321        builder,
1322        value,
1323        SemanticTransformRole::Vjp,
1324        "broadcast cotangent",
1325    )?;
1326    let input_rank = input_shape.shape.len();
1327    let output_rank = output_shape.shape.len();
1328    let metadata_error = |message| SemanticAdTransformError::UnsupportedMetadata {
1329        role: SemanticTransformRole::Vjp,
1330        message,
1331    };
1332    if dims.len() != input_rank {
1333        return Err(metadata_error(format!(
1334            "broadcast dims length {} does not match input rank {input_rank}",
1335            dims.len()
1336        )));
1337    }
1338    let mut seen = HashSet::with_capacity(dims.len());
1339    for (input_axis, &output_axis) in dims.iter().enumerate() {
1340        if output_axis >= output_rank {
1341            return Err(metadata_error(format!(
1342                "broadcast dims[{input_axis}] = {output_axis} is out of bounds for output rank {output_rank}"
1343            )));
1344        }
1345        if !seen.insert(output_axis) {
1346            return Err(metadata_error(format!(
1347                "broadcast dims[{input_axis}] = {output_axis} duplicates an earlier output axis"
1348            )));
1349        }
1350    }
1351    // INVARIANT: these repeated membership and position scans are bounded by tensor rank;
1352    // replace them with axis maps only if unusually high-rank tensors make this measurable.
1353    let mut reduce_axes: Vec<_> = (0..output_rank)
1354        .filter(|axis| !dims.contains(axis))
1355        .collect();
1356    reduce_axes.extend(
1357        dims.iter()
1358            .copied()
1359            .enumerate()
1360            .filter_map(|(input_axis, output_axis)| {
1361                (input_shape.shape[input_axis] != output_shape.shape[output_axis]
1362                    && axis_is_known_singleton(builder, primal_input, input_axis))
1363                .then_some(output_axis)
1364            }),
1365    );
1366    reduce_axes.sort_unstable();
1367    reduce_axes.dedup();
1368    if !reduce_axes.is_empty() {
1369        value = builder.add_op(
1370            CoreSemanticOp::ReduceSum {
1371                axes: reduce_axes.clone(),
1372            },
1373            &[value],
1374        )?[0];
1375    }
1376
1377    let remaining_output_axes: Vec<_> = (0..output_rank)
1378        .filter(|axis| !reduce_axes.contains(axis))
1379        .collect();
1380    let perm: Vec<_> = dims
1381        .iter()
1382        .copied()
1383        .filter(|axis| !reduce_axes.contains(axis))
1384        .map(|axis| {
1385            remaining_output_axes
1386                .iter()
1387                .position(|candidate| *candidate == axis)
1388                .ok_or_else(|| {
1389                    metadata_error(format!(
1390                        "broadcast output axis {axis} did not survive cotangent reduction"
1391                    ))
1392                })
1393        })
1394        .collect::<Result<_, _>>()?;
1395    if perm.iter().copied().ne(0..perm.len()) {
1396        value = builder.add_op(CoreSemanticOp::Transpose { perm }, &[value])?[0];
1397    }
1398    if builder.value_metadata(value)?.shape() != builder.value_metadata(primal_input)?.shape() {
1399        value = reshape_value_to_shape(builder, value, &input_shape)?;
1400    }
1401    value =
1402        truncate_value_to_dynamic_axes(builder, value, primal_input, &input_shape.dynamic_axes)?;
1403    Ok(AdValue::Value(value))
1404}
1405
1406fn exact_value_shape(
1407    builder: &SemanticProgramBuilder,
1408    value: ProgramValue,
1409    role: SemanticTransformRole,
1410    field: &'static str,
1411) -> Result<Vec<tenferro_ops::dim_expr::DimExpr>, SemanticAdTransformError> {
1412    exact_shape(builder.value_metadata(value)?.shape(), role, field)
1413}
1414
1415fn is_differentiable_dtype(dtype: DType) -> bool {
1416    matches!(dtype, DType::F32 | DType::F64 | DType::C32 | DType::C64)
1417}
1418
1419fn is_complex_dtype(dtype: DType) -> bool {
1420    matches!(dtype, DType::C32 | DType::C64)
1421}
1422
1423fn abs_output_dtype(dtype: DType) -> DType {
1424    match dtype {
1425        DType::C32 => DType::F32,
1426        DType::C64 => DType::F64,
1427        other => other,
1428    }
1429}
1430
1431fn add_ad_values(
1432    builder: &mut SemanticProgramBuilder,
1433    lhs: AdValue,
1434    rhs: AdValue,
1435) -> Result<AdValue, ProgramBuildError> {
1436    match (lhs, rhs) {
1437        (AdValue::Absent, value) | (value, AdValue::Absent) => Ok(value),
1438        (AdValue::Value(lhs), AdValue::Value(rhs)) => Ok(AdValue::Value(
1439            builder.add_op(CoreSemanticOp::Add, &[lhs, rhs])?[0],
1440        )),
1441    }
1442}
1443
1444fn sub_ad_values(
1445    builder: &mut SemanticProgramBuilder,
1446    lhs: AdValue,
1447    rhs: AdValue,
1448) -> Result<AdValue, ProgramBuildError> {
1449    match (lhs, rhs) {
1450        (AdValue::Absent, AdValue::Absent) => Ok(AdValue::Absent),
1451        (value, AdValue::Absent) => Ok(value),
1452        (AdValue::Absent, AdValue::Value(rhs)) => Ok(AdValue::Value(
1453            builder.add_op(CoreSemanticOp::Neg, &[rhs])?[0],
1454        )),
1455        (AdValue::Value(lhs), AdValue::Value(rhs)) => Ok(AdValue::Value(
1456            builder.add_op(CoreSemanticOp::Sub, &[lhs, rhs])?[0],
1457        )),
1458    }
1459}
1460
1461fn unary_ad_value(
1462    builder: &mut SemanticProgramBuilder,
1463    op: CoreSemanticOp,
1464    value: AdValue,
1465) -> Result<AdValue, ProgramBuildError> {
1466    match value {
1467        AdValue::Absent => Ok(AdValue::Absent),
1468        AdValue::Value(value) => Ok(AdValue::Value(builder.add_op(op, &[value])?[0])),
1469    }
1470}
1471
1472fn multiply_ad_value(
1473    builder: &mut SemanticProgramBuilder,
1474    value: AdValue,
1475    coefficient: ProgramValue,
1476) -> Result<AdValue, ProgramBuildError> {
1477    match value {
1478        AdValue::Absent => Ok(AdValue::Absent),
1479        AdValue::Value(value) => Ok(AdValue::Value(
1480            builder.add_op(CoreSemanticOp::Mul, &[value, coefficient])?[0],
1481        )),
1482    }
1483}
1484
1485fn divide_ad_value(
1486    builder: &mut SemanticProgramBuilder,
1487    value: AdValue,
1488    denominator: ProgramValue,
1489) -> Result<AdValue, ProgramBuildError> {
1490    match value {
1491        AdValue::Absent => Ok(AdValue::Absent),
1492        AdValue::Value(value) => Ok(AdValue::Value(
1493            builder.add_op(CoreSemanticOp::Div, &[value, denominator])?[0],
1494        )),
1495    }
1496}
1497
1498fn convert_ad_value(
1499    builder: &mut SemanticProgramBuilder,
1500    value: AdValue,
1501    from: DType,
1502    to: DType,
1503) -> Result<AdValue, ProgramBuildError> {
1504    if from == to {
1505        return Ok(value);
1506    }
1507    unary_ad_value(builder, CoreSemanticOp::Convert { from, to }, value)
1508}
1509
1510fn select_ad_values(
1511    builder: &mut SemanticProgramBuilder,
1512    condition: ProgramValue,
1513    on_true: AdValue,
1514    on_false: AdValue,
1515) -> Result<AdValue, SemanticAdTransformError> {
1516    match (on_true, on_false) {
1517        (AdValue::Absent, AdValue::Absent) => Ok(AdValue::Absent),
1518        (AdValue::Value(on_true), AdValue::Value(on_false)) => Ok(AdValue::Value(
1519            builder.add_op(CoreSemanticOp::Select, &[condition, on_true, on_false])?[0],
1520        )),
1521        (AdValue::Value(on_true), AdValue::Absent) => {
1522            let zero = zero_constant_like(builder, on_true, SemanticTransformRole::Jvp)?;
1523            Ok(AdValue::Value(
1524                builder.add_op(CoreSemanticOp::Select, &[condition, on_true, zero])?[0],
1525            ))
1526        }
1527        (AdValue::Absent, AdValue::Value(on_false)) => {
1528            let zero = zero_constant_like(builder, on_false, SemanticTransformRole::Jvp)?;
1529            Ok(AdValue::Value(
1530                builder.add_op(CoreSemanticOp::Select, &[condition, zero, on_false])?[0],
1531            ))
1532        }
1533    }
1534}
1535
1536fn split_select_cotangent(
1537    builder: &mut SemanticProgramBuilder,
1538    condition: ProgramValue,
1539    cotangent: AdValue,
1540    true_active: bool,
1541    false_active: bool,
1542) -> Result<(AdValue, AdValue), SemanticAdTransformError> {
1543    if !true_active && !false_active {
1544        return Ok((AdValue::Absent, AdValue::Absent));
1545    }
1546    let AdValue::Value(cotangent) = cotangent else {
1547        return Ok((AdValue::Absent, AdValue::Absent));
1548    };
1549    let zero = zero_constant_like(builder, cotangent, SemanticTransformRole::Vjp)?;
1550    let on_true = if true_active {
1551        AdValue::Value(builder.add_op(CoreSemanticOp::Select, &[condition, cotangent, zero])?[0])
1552    } else {
1553        AdValue::Absent
1554    };
1555    let on_false = if false_active {
1556        AdValue::Value(builder.add_op(CoreSemanticOp::Select, &[condition, zero, cotangent])?[0])
1557    } else {
1558        AdValue::Absent
1559    };
1560    Ok((on_true, on_false))
1561}
1562
1563fn linearize_extrema(
1564    builder: &mut SemanticProgramBuilder,
1565    op: &CoreSemanticOp,
1566    primal_inputs: &[ProgramValue],
1567    tangent_inputs: &[AdValue],
1568) -> Result<AdValue, SemanticAdTransformError> {
1569    let output = builder.add_op(op.clone(), primal_inputs)?[0];
1570    let lhs_eq_output = builder.add_op(
1571        CoreSemanticOp::Compare(CompareDir::Eq),
1572        &[primal_inputs[0], output],
1573    )?[0];
1574    let rhs_eq_output = builder.add_op(
1575        CoreSemanticOp::Compare(CompareDir::Eq),
1576        &[primal_inputs[1], output],
1577    )?[0];
1578    let lhs = balanced_extrema_contribution(
1579        builder,
1580        tangent_inputs[0],
1581        lhs_eq_output,
1582        rhs_eq_output,
1583        SemanticTransformRole::Jvp,
1584    )?;
1585    let rhs = balanced_extrema_contribution(
1586        builder,
1587        tangent_inputs[1],
1588        rhs_eq_output,
1589        lhs_eq_output,
1590        SemanticTransformRole::Jvp,
1591    )?;
1592    Ok(add_ad_values(builder, lhs, rhs)?)
1593}
1594
1595fn extrema_vjp(
1596    builder: &mut SemanticProgramBuilder,
1597    op: &CoreSemanticOp,
1598    primal_inputs: &[ProgramValue],
1599    cotangent: AdValue,
1600    active_inputs: &[bool],
1601) -> Result<Vec<AdValue>, SemanticAdTransformError> {
1602    let output = builder.add_op(op.clone(), primal_inputs)?[0];
1603    let lhs_eq_output = builder.add_op(
1604        CoreSemanticOp::Compare(CompareDir::Eq),
1605        &[primal_inputs[0], output],
1606    )?[0];
1607    let rhs_eq_output = builder.add_op(
1608        CoreSemanticOp::Compare(CompareDir::Eq),
1609        &[primal_inputs[1], output],
1610    )?[0];
1611    let lhs = balanced_extrema_contribution(
1612        builder,
1613        cotangent,
1614        lhs_eq_output,
1615        rhs_eq_output,
1616        SemanticTransformRole::Vjp,
1617    )?;
1618    let rhs = balanced_extrema_contribution(
1619        builder,
1620        cotangent,
1621        rhs_eq_output,
1622        lhs_eq_output,
1623        SemanticTransformRole::Vjp,
1624    )?;
1625    Ok(vec![
1626        normalize_ad_value(builder, lhs, active_inputs[0], primal_inputs[0])?,
1627        normalize_ad_value(builder, rhs, active_inputs[1], primal_inputs[1])?,
1628    ])
1629}
1630
1631fn balanced_extrema_contribution(
1632    builder: &mut SemanticProgramBuilder,
1633    active: AdValue,
1634    self_eq_output: ProgramValue,
1635    other_eq_output: ProgramValue,
1636    role: SemanticTransformRole,
1637) -> Result<AdValue, SemanticAdTransformError> {
1638    let AdValue::Value(active) = active else {
1639        return Ok(AdValue::Absent);
1640    };
1641    let zero = zero_constant_like(builder, active, role)?;
1642    let selected = builder.add_op(CoreSemanticOp::Select, &[self_eq_output, active, zero])?[0];
1643    let one = one_like(builder, active, role)?;
1644    let two = builder.add_op(CoreSemanticOp::Add, &[one, one])?[0];
1645    let half = builder.add_op(CoreSemanticOp::Div, &[selected, two])?[0];
1646    Ok(AdValue::Value(
1647        builder.add_op(CoreSemanticOp::Select, &[other_eq_output, half, selected])?[0],
1648    ))
1649}
1650
1651/// `rem(x, y) = x - trunc(x / y) * y`, so away from its discontinuities (`y == 0`, and an exact
1652/// integer quotient, where the derivative jumps) it is linear in `x` with slope `1` and in `y`
1653/// with slope `-trunc(x / y)`. The discontinuities are a measure-zero set and are left
1654/// undefined rather than given a one-sided value.
1655fn linearize_rem(
1656    builder: &mut SemanticProgramBuilder,
1657    primal_inputs: &[ProgramValue],
1658    tangent_inputs: &[AdValue],
1659) -> Result<AdValue, SemanticAdTransformError> {
1660    if !rem_has_real_derivative(builder, primal_inputs)? {
1661        return Ok(AdValue::Absent);
1662    }
1663    let lhs = tangent_inputs[0];
1664    let rhs = if matches!(tangent_inputs[1], AdValue::Value(_)) {
1665        let coefficient = trunc_quotient(builder, primal_inputs)?;
1666        let scaled = multiply_ad_value(builder, tangent_inputs[1], coefficient)?;
1667        unary_ad_value(builder, CoreSemanticOp::Neg, scaled)?
1668    } else {
1669        AdValue::Absent
1670    };
1671    Ok(add_ad_values(builder, lhs, rhs)?)
1672}
1673
1674/// The reverse rule of `rem`: `d/dx = 1`, `d/dy = -trunc(x / y)`.
1675fn rem_vjp(
1676    builder: &mut SemanticProgramBuilder,
1677    primal_inputs: &[ProgramValue],
1678    cotangent: AdValue,
1679    active_inputs: &[bool],
1680) -> Result<Vec<AdValue>, SemanticAdTransformError> {
1681    if !rem_has_real_derivative(builder, primal_inputs)? {
1682        return Ok(vec![AdValue::Absent, AdValue::Absent]);
1683    }
1684    let lhs = active_cotangent(builder, cotangent, active_inputs[0], primal_inputs[0])?;
1685    let rhs = if active_inputs[1] {
1686        let coefficient = trunc_quotient(builder, primal_inputs)?;
1687        let scaled = multiply_ad_value(builder, cotangent, coefficient)?;
1688        unary_ad_value(builder, CoreSemanticOp::Neg, scaled)?
1689    } else {
1690        AdValue::Absent
1691    };
1692    Ok(vec![
1693        normalize_ad_value(builder, lhs, active_inputs[0], primal_inputs[0])?,
1694        normalize_ad_value(builder, rhs, active_inputs[1], primal_inputs[1])?,
1695    ])
1696}
1697
1698/// Whether `rem`'s inputs carry a differentiable dtype.
1699///
1700/// `rem` is defined for the real and integer dtypes only (`SameNumeric` minus complex), so a
1701/// float input differentiates and an integer input takes the non-differentiable branch instead
1702/// of a derivative that has no dtype to live in.
1703fn rem_has_real_derivative(
1704    builder: &mut SemanticProgramBuilder,
1705    primal_inputs: &[ProgramValue],
1706) -> Result<bool, SemanticAdTransformError> {
1707    Ok(matches!(
1708        builder.value_metadata(primal_inputs[0])?.dtype(),
1709        DType::F32 | DType::F64
1710    ))
1711}
1712
1713/// `trunc(x / y)` in the core vocabulary: `rem(q, 1.0)` is `q`'s fractional part (the remainder
1714/// takes the dividend's sign), so `q - rem(q, 1.0)` truncates toward zero.
1715fn trunc_quotient(
1716    builder: &mut SemanticProgramBuilder,
1717    primal_inputs: &[ProgramValue],
1718) -> Result<ProgramValue, SemanticAdTransformError> {
1719    let quotient = builder.add_op(CoreSemanticOp::Div, &[primal_inputs[0], primal_inputs[1]])?[0];
1720    let one = one_like(builder, quotient, SemanticTransformRole::Jvp)?;
1721    let fraction = builder.add_op(CoreSemanticOp::Rem, &[quotient, one])?[0];
1722    Ok(builder.add_op(CoreSemanticOp::Sub, &[quotient, fraction])?[0])
1723}
1724
1725fn linearize_clamp(
1726    builder: &mut SemanticProgramBuilder,
1727    primal_inputs: &[ProgramValue],
1728    tangent_inputs: &[AdValue],
1729) -> Result<AdValue, SemanticAdTransformError> {
1730    let masks = clamp_masks(builder, primal_inputs)?;
1731    let input = mask_ad_value(
1732        builder,
1733        tangent_inputs[0],
1734        &[masks[0], masks[1]],
1735        SemanticTransformRole::Jvp,
1736    )?;
1737    let lower = mask_ad_value(
1738        builder,
1739        tangent_inputs[1],
1740        &[masks[2], masks[3]],
1741        SemanticTransformRole::Jvp,
1742    )?;
1743    let upper = mask_ad_value(
1744        builder,
1745        tangent_inputs[2],
1746        &[masks[4]],
1747        SemanticTransformRole::Jvp,
1748    )?;
1749    let input_and_lower = add_ad_values(builder, input, lower)?;
1750    Ok(add_ad_values(builder, input_and_lower, upper)?)
1751}
1752
1753fn clamp_vjp(
1754    builder: &mut SemanticProgramBuilder,
1755    primal_inputs: &[ProgramValue],
1756    cotangent: AdValue,
1757    active_inputs: &[bool],
1758) -> Result<Vec<AdValue>, SemanticAdTransformError> {
1759    let masks = clamp_masks(builder, primal_inputs)?;
1760    let input = mask_ad_value(
1761        builder,
1762        cotangent,
1763        &[masks[0], masks[1]],
1764        SemanticTransformRole::Vjp,
1765    )?;
1766    let lower = mask_ad_value(
1767        builder,
1768        cotangent,
1769        &[masks[2], masks[3]],
1770        SemanticTransformRole::Vjp,
1771    )?;
1772    let upper = mask_ad_value(builder, cotangent, &[masks[4]], SemanticTransformRole::Vjp)?;
1773    Ok(vec![
1774        normalize_ad_value(builder, input, active_inputs[0], primal_inputs[0])?,
1775        normalize_ad_value(builder, lower, active_inputs[1], primal_inputs[1])?,
1776        normalize_ad_value(builder, upper, active_inputs[2], primal_inputs[2])?,
1777    ])
1778}
1779
1780fn clamp_masks(
1781    builder: &mut SemanticProgramBuilder,
1782    primal_inputs: &[ProgramValue],
1783) -> Result<[ProgramValue; 5], ProgramBuildError> {
1784    let input = primal_inputs[0];
1785    let lower = primal_inputs[1];
1786    let upper = primal_inputs[2];
1787    let input_gt_lower =
1788        builder.add_op(CoreSemanticOp::Compare(CompareDir::Gt), &[input, lower])?[0];
1789    let input_lt_upper =
1790        builder.add_op(CoreSemanticOp::Compare(CompareDir::Lt), &[input, upper])?[0];
1791    let lower_gt_input =
1792        builder.add_op(CoreSemanticOp::Compare(CompareDir::Gt), &[lower, input])?[0];
1793    let lower_lt_upper =
1794        builder.add_op(CoreSemanticOp::Compare(CompareDir::Lt), &[lower, upper])?[0];
1795    let max_input_lower = builder.add_op(CoreSemanticOp::Maximum, &[input, lower])?[0];
1796    let upper_lt_max_input_lower = builder.add_op(
1797        CoreSemanticOp::Compare(CompareDir::Lt),
1798        &[upper, max_input_lower],
1799    )?[0];
1800    Ok([
1801        input_gt_lower,
1802        input_lt_upper,
1803        lower_gt_input,
1804        lower_lt_upper,
1805        upper_lt_max_input_lower,
1806    ])
1807}
1808
1809fn mask_ad_value(
1810    builder: &mut SemanticProgramBuilder,
1811    active: AdValue,
1812    conditions: &[ProgramValue],
1813    role: SemanticTransformRole,
1814) -> Result<AdValue, SemanticAdTransformError> {
1815    let AdValue::Value(active) = active else {
1816        return Ok(AdValue::Absent);
1817    };
1818    let zero = zero_constant_like(builder, active, role)?;
1819    let mut value = active;
1820    for condition in conditions {
1821        value = builder.add_op(CoreSemanticOp::Select, &[*condition, value, zero])?[0];
1822    }
1823    Ok(AdValue::Value(value))
1824}
1825
1826fn linearize_analytic_unary(
1827    builder: &mut SemanticProgramBuilder,
1828    op: &CoreSemanticOp,
1829    primal_input: ProgramValue,
1830    tangent: AdValue,
1831) -> Result<AdValue, SemanticAdTransformError> {
1832    if matches!(tangent, AdValue::Absent) {
1833        return Ok(AdValue::Absent);
1834    }
1835    let coefficient =
1836        analytic_unary_coefficient(builder, op, primal_input, SemanticTransformRole::Jvp)?;
1837    Ok(multiply_ad_value(builder, tangent, coefficient)?)
1838}
1839
1840fn linearize_sign(
1841    builder: &mut SemanticProgramBuilder,
1842    primal_input: ProgramValue,
1843    tangent: AdValue,
1844) -> Result<AdValue, SemanticAdTransformError> {
1845    let AdValue::Value(tangent_value) = tangent else {
1846        return Ok(AdValue::Absent);
1847    };
1848    let input_dtype = builder.value_metadata(primal_input)?.dtype();
1849    if !is_complex_dtype(input_dtype) {
1850        return Ok(AdValue::Absent);
1851    }
1852
1853    let zero = zero_constant_like(builder, primal_input, SemanticTransformRole::Jvp)?;
1854    let zero_mask = builder.add_op(
1855        CoreSemanticOp::Compare(CompareDir::Eq),
1856        &[primal_input, zero],
1857    )?[0];
1858    let sign = builder.add_op(CoreSemanticOp::Sign, &[primal_input])?[0];
1859    let abs = builder.add_op(CoreSemanticOp::Abs, &[primal_input])?[0];
1860    let output_dtype = abs_output_dtype(input_dtype);
1861    let complex_abs = builder.add_op(
1862        CoreSemanticOp::Convert {
1863            from: output_dtype,
1864            to: input_dtype,
1865        },
1866        &[abs],
1867    )?[0];
1868    let one = one_like(builder, complex_abs, SemanticTransformRole::Jvp)?;
1869    let safe_abs = builder.add_op(CoreSemanticOp::Select, &[zero_mask, one, complex_abs])?[0];
1870    let safe_sign = builder.add_op(CoreSemanticOp::Select, &[zero_mask, zero, sign])?[0];
1871    let conj_sign = builder.add_op(CoreSemanticOp::Conj, &[safe_sign])?[0];
1872
1873    let abs_tangent_complex = multiply_ad_value(builder, AdValue::Value(tangent_value), conj_sign)?;
1874    let abs_tangent = convert_ad_value(builder, abs_tangent_complex, input_dtype, output_dtype)?;
1875    let abs_tangent = convert_ad_value(builder, abs_tangent, output_dtype, input_dtype)?;
1876    let tangent_over_abs = divide_ad_value(builder, AdValue::Value(tangent_value), safe_abs)?;
1877    let sign_times_abs_tangent = multiply_ad_value(builder, abs_tangent, safe_sign)?;
1878    let correction = divide_ad_value(builder, sign_times_abs_tangent, safe_abs)?;
1879    let derivative = sub_ad_values(builder, tangent_over_abs, correction)?;
1880    let zero_derivative = zero_constant_like(builder, tangent_value, SemanticTransformRole::Jvp)?;
1881    select_ad_values(
1882        builder,
1883        zero_mask,
1884        AdValue::Value(zero_derivative),
1885        derivative,
1886    )
1887}
1888
1889fn analytic_unary_coefficient(
1890    builder: &mut SemanticProgramBuilder,
1891    op: &CoreSemanticOp,
1892    primal_input: ProgramValue,
1893    role: SemanticTransformRole,
1894) -> Result<ProgramValue, SemanticAdTransformError> {
1895    let coefficient = match op {
1896        CoreSemanticOp::Exp | CoreSemanticOp::Expm1 => {
1897            builder.add_op(CoreSemanticOp::Exp, &[primal_input])?[0]
1898        }
1899        CoreSemanticOp::Log => {
1900            let one = one_like(builder, primal_input, role)?;
1901            builder.add_op(CoreSemanticOp::Div, &[one, primal_input])?[0]
1902        }
1903        CoreSemanticOp::Sin => builder.add_op(CoreSemanticOp::Cos, &[primal_input])?[0],
1904        CoreSemanticOp::Cos => {
1905            let sin = builder.add_op(CoreSemanticOp::Sin, &[primal_input])?[0];
1906            builder.add_op(CoreSemanticOp::Neg, &[sin])?[0]
1907        }
1908        CoreSemanticOp::Tanh => {
1909            let tanh = builder.add_op(CoreSemanticOp::Tanh, &[primal_input])?[0];
1910            let square = builder.add_op(CoreSemanticOp::Mul, &[tanh, tanh])?[0];
1911            let one = one_like(builder, primal_input, role)?;
1912            builder.add_op(CoreSemanticOp::Sub, &[one, square])?[0]
1913        }
1914        CoreSemanticOp::Sqrt => {
1915            let sqrt = builder.add_op(CoreSemanticOp::Sqrt, &[primal_input])?[0];
1916            let twice = builder.add_op(CoreSemanticOp::Add, &[sqrt, sqrt])?[0];
1917            let one = one_like(builder, primal_input, role)?;
1918            builder.add_op(CoreSemanticOp::Div, &[one, twice])?[0]
1919        }
1920        CoreSemanticOp::Rsqrt => {
1921            let rsqrt = builder.add_op(CoreSemanticOp::Rsqrt, &[primal_input])?[0];
1922            let negated = builder.add_op(CoreSemanticOp::Neg, &[rsqrt])?[0];
1923            let twice = builder.add_op(CoreSemanticOp::Add, &[primal_input, primal_input])?[0];
1924            builder.add_op(CoreSemanticOp::Div, &[negated, twice])?[0]
1925        }
1926        CoreSemanticOp::Log1p => {
1927            let one = one_like(builder, primal_input, role)?;
1928            let denominator = builder.add_op(CoreSemanticOp::Add, &[primal_input, one])?[0];
1929            builder.add_op(CoreSemanticOp::Div, &[one, denominator])?[0]
1930        }
1931        CoreSemanticOp::Erf => {
1932            // d erf(x) = 2/sqrt(pi) * exp(-x^2)
1933            let square = builder.add_op(CoreSemanticOp::Mul, &[primal_input, primal_input])?[0];
1934            let negated = builder.add_op(CoreSemanticOp::Neg, &[square])?[0];
1935            let gaussian = builder.add_op(CoreSemanticOp::Exp, &[negated])?[0];
1936            let scale = real_float_constant_like(
1937                builder,
1938                primal_input,
1939                std::f64::consts::FRAC_2_SQRT_PI,
1940                role,
1941            )?;
1942            builder.add_op(CoreSemanticOp::Mul, &[scale, gaussian])?[0]
1943        }
1944        _ => return Err(unsupported_core(role, op)),
1945    };
1946    Ok(coefficient)
1947}
1948
1949fn one_like(
1950    builder: &mut SemanticProgramBuilder,
1951    anchor: ProgramValue,
1952    role: SemanticTransformRole,
1953) -> Result<ProgramValue, SemanticAdTransformError> {
1954    let metadata = builder.value_metadata(anchor)?.clone();
1955    let dtype = metadata.dtype();
1956    let bytes = match dtype {
1957        DType::F32 => 1.0_f32.to_le_bytes().to_vec(),
1958        DType::F64 => 1.0_f64.to_le_bytes().to_vec(),
1959        DType::C32 => {
1960            let mut bytes = 1.0_f32.to_le_bytes().to_vec();
1961            bytes.extend_from_slice(&0.0_f32.to_le_bytes());
1962            bytes
1963        }
1964        DType::C64 => {
1965            let mut bytes = 1.0_f64.to_le_bytes().to_vec();
1966            bytes.extend_from_slice(&0.0_f64.to_le_bytes());
1967            bytes
1968        }
1969        _ => {
1970            return Err(SemanticAdTransformError::UnsupportedMetadata {
1971                role,
1972                message: format!("cannot construct a differentiable one for {dtype:?}"),
1973            });
1974        }
1975    };
1976    let scalar = builder.add_op(CoreSemanticOp::Constant { dtype, bytes }, &[])?[0];
1977    broadcast_scalar_like(builder, scalar, anchor, &metadata, role, "one-like anchor")
1978}
1979
1980/// Broadcast a rank-0 `scalar` to `anchor`'s (possibly dynamic) shape.
1981fn broadcast_scalar_like(
1982    builder: &mut SemanticProgramBuilder,
1983    scalar: ProgramValue,
1984    anchor: ProgramValue,
1985    metadata: &ProgramValueMetadata,
1986    role: SemanticTransformRole,
1987    what: &'static str,
1988) -> Result<ProgramValue, SemanticAdTransformError> {
1989    if metadata.shape().is_empty() {
1990        Ok(scalar)
1991    } else {
1992        let shape = shape_plan(metadata.shape(), role, what)?;
1993        let value = broadcast_value_in_dim_to_shape(builder, scalar, &shape, Vec::new())?;
1994        Ok(truncate_value_to_dynamic_axes(
1995            builder,
1996            value,
1997            anchor,
1998            &shape.dynamic_axes,
1999        )?)
2000    }
2001}
2002
2003/// Build the real constant `value` shaped like a real floating `anchor`.
2004fn real_float_constant_like(
2005    builder: &mut SemanticProgramBuilder,
2006    anchor: ProgramValue,
2007    value: f64,
2008    role: SemanticTransformRole,
2009) -> Result<ProgramValue, SemanticAdTransformError> {
2010    let metadata = builder.value_metadata(anchor)?.clone();
2011    let dtype = metadata.dtype();
2012    let bytes = match dtype {
2013        DType::F32 => (value as f32).to_le_bytes().to_vec(),
2014        DType::F64 => value.to_le_bytes().to_vec(),
2015        _ => {
2016            return Err(SemanticAdTransformError::UnsupportedMetadata {
2017                role,
2018                message: format!("cannot construct a real floating constant for {dtype:?}"),
2019            });
2020        }
2021    };
2022    let scalar = builder.add_op(CoreSemanticOp::Constant { dtype, bytes }, &[])?[0];
2023    broadcast_scalar_like(
2024        builder,
2025        scalar,
2026        anchor,
2027        &metadata,
2028        role,
2029        "real-constant anchor",
2030    )
2031}
2032
2033/// Build a true dtype-aware zero shaped like `anchor`.
2034///
2035/// A zero synthesized as `x - x` or `x + (-x)` evaluates to `NaN` when `x` is
2036/// non-finite, so emission sites that need an additive identity for masked-out
2037/// values must materialize a `Constant` zero instead of deriving it from the
2038/// active value.
2039fn zero_constant_like(
2040    builder: &mut SemanticProgramBuilder,
2041    anchor: ProgramValue,
2042    role: SemanticTransformRole,
2043) -> Result<ProgramValue, SemanticAdTransformError> {
2044    let metadata = builder.value_metadata(anchor)?.clone();
2045    let dtype = metadata.dtype();
2046    let bytes = match dtype {
2047        DType::F32 => 0.0_f32.to_le_bytes().to_vec(),
2048        DType::F64 => 0.0_f64.to_le_bytes().to_vec(),
2049        DType::I32 => 0_i32.to_le_bytes().to_vec(),
2050        DType::I64 => 0_i64.to_le_bytes().to_vec(),
2051        DType::Bool => vec![0],
2052        DType::C32 => {
2053            let mut bytes = 0.0_f32.to_le_bytes().to_vec();
2054            bytes.extend_from_slice(&0.0_f32.to_le_bytes());
2055            bytes
2056        }
2057        DType::C64 => {
2058            let mut bytes = 0.0_f64.to_le_bytes().to_vec();
2059            bytes.extend_from_slice(&0.0_f64.to_le_bytes());
2060            bytes
2061        }
2062        // INVARIANT: the semantic AD catalog is closed to the preset scalars,
2063        // so an externally defined dtype cannot reach a constant emission.
2064        DType::External(_) => unreachable!("the AD catalog is closed to the presets"),
2065    };
2066    let scalar = builder.add_op(CoreSemanticOp::Constant { dtype, bytes }, &[])?[0];
2067    if metadata.shape().is_empty() {
2068        return Ok(scalar);
2069    }
2070    let shape = shape_plan(metadata.shape(), role, "zero-like anchor")?;
2071    let zero = broadcast_value_in_dim_to_shape(builder, scalar, &shape, Vec::new())?;
2072    Ok(truncate_value_to_dynamic_axes(
2073        builder,
2074        zero,
2075        anchor,
2076        &shape.dynamic_axes,
2077    )?)
2078}
2079
2080fn active_cotangent(
2081    builder: &mut SemanticProgramBuilder,
2082    cotangent: AdValue,
2083    active: bool,
2084    primal_input: ProgramValue,
2085) -> Result<AdValue, SemanticAdTransformError> {
2086    normalize_ad_value(builder, cotangent, active, primal_input)
2087}
2088
2089fn normalize_ad_value(
2090    builder: &mut SemanticProgramBuilder,
2091    value: AdValue,
2092    active: bool,
2093    primal_input: ProgramValue,
2094) -> Result<AdValue, SemanticAdTransformError> {
2095    if !active {
2096        return Ok(AdValue::Absent);
2097    }
2098    let AdValue::Value(mut value) = value else {
2099        return Ok(AdValue::Absent);
2100    };
2101    let target_metadata = builder.value_metadata(primal_input)?.clone();
2102    let value_metadata = builder.value_metadata(value)?.clone();
2103    let target_shape = shape_plan(
2104        target_metadata.shape(),
2105        SemanticTransformRole::Vjp,
2106        "primal input",
2107    )?;
2108    let value_shape = shape_plan(
2109        value_metadata.shape(),
2110        SemanticTransformRole::Vjp,
2111        "cotangent",
2112    )?;
2113    if value_shape.shape.len() < target_shape.shape.len() {
2114        return Err(SemanticAdTransformError::UnsupportedMetadata {
2115            role: SemanticTransformRole::Vjp,
2116            message: "cotangent rank is smaller than its primal-input rank".into(),
2117        });
2118    }
2119    let leading = value_shape.shape.len() - target_shape.shape.len();
2120    let mut axes: Vec<_> = (0..leading).collect();
2121    axes.extend(
2122        target_shape
2123            .shape
2124            .iter()
2125            .zip(value_shape.shape.iter().skip(leading))
2126            .enumerate()
2127            .filter_map(|(axis, (target, actual))| {
2128                // `axis` indexes the primal input; `axis + leading` is the cotangent
2129                // axis it was broadcast into.
2130                (target != actual && axis_is_known_singleton(builder, primal_input, axis))
2131                    .then_some(axis + leading)
2132            }),
2133    );
2134    if !axes.is_empty() {
2135        value = builder.add_op(CoreSemanticOp::ReduceSum { axes }, &[value])?[0];
2136    }
2137    if builder.value_metadata(value)?.shape() != target_metadata.shape() {
2138        value = reshape_value_to_shape(builder, value, &target_shape)?;
2139    }
2140    value =
2141        truncate_value_to_dynamic_axes(builder, value, primal_input, &target_shape.dynamic_axes)?;
2142    let value_dtype = builder.value_metadata(value)?.dtype();
2143    if value_dtype != target_metadata.dtype() {
2144        value = builder.add_op(
2145            CoreSemanticOp::Convert {
2146                from: value_dtype,
2147                to: target_metadata.dtype(),
2148            },
2149            &[value],
2150        )?[0];
2151    }
2152    Ok(AdValue::Value(value))
2153}
2154
2155fn exact_shape(
2156    shape: &[tenferro_ops::ShapeExtent<tenferro_ops::dim_expr::DimExpr>],
2157    role: SemanticTransformRole,
2158    field: &'static str,
2159) -> Result<Vec<tenferro_ops::dim_expr::DimExpr>, SemanticAdTransformError> {
2160    shape
2161        .iter()
2162        .map(|extent| {
2163            extent.as_exact().cloned().ok_or_else(|| {
2164                SemanticAdTransformError::UnsupportedMetadata {
2165                    role,
2166                    message: format!("{field} has a bounded or unknown extent"),
2167                }
2168            })
2169        })
2170        .collect()
2171}
2172
2173fn value_shape_plan(
2174    builder: &SemanticProgramBuilder,
2175    value: ProgramValue,
2176    role: SemanticTransformRole,
2177    field: &'static str,
2178) -> Result<ValueShapePlan, SemanticAdTransformError> {
2179    shape_plan(builder.value_metadata(value)?.shape(), role, field)
2180}
2181
2182fn shape_plan(
2183    shape: &[ShapeExtent<DimExpr>],
2184    role: SemanticTransformRole,
2185    field: &'static str,
2186) -> Result<ValueShapePlan, SemanticAdTransformError> {
2187    let mut planned_shape = Vec::with_capacity(shape.len());
2188    let mut dynamic_axes = Vec::new();
2189    for (axis, extent) in shape.iter().enumerate() {
2190        match extent {
2191            ShapeExtent::Exact(expression) => planned_shape.push(expression.clone()),
2192            ShapeExtent::UpperBound(expression) => {
2193                planned_shape.push(expression.clone());
2194                dynamic_axes.push(axis);
2195            }
2196            ShapeExtent::Unknown => {
2197                return Err(SemanticAdTransformError::UnsupportedMetadata {
2198                    role,
2199                    message: format!("{field} has an unknown extent without an upper bound"),
2200                });
2201            }
2202        }
2203    }
2204    Ok(ValueShapePlan {
2205        shape: planned_shape,
2206        dynamic_axes,
2207    })
2208}
2209
2210/// Literal axis lengths of `value`, for the rules that must emit them.
2211///
2212/// Programs imported for the transform keep their symbolic extents, so a value
2213/// that carries a binding reads its concrete shape from the binding instead of
2214/// forcing the whole transformed program to become concrete.
2215pub(super) fn bounded_usize_shape(
2216    builder: &SemanticProgramBuilder,
2217    value: ProgramValue,
2218    field: &'static str,
2219    accept_upper_bound: bool,
2220) -> Result<Vec<usize>, SemanticAdTransformError> {
2221    let extents = builder.resolved_extents(value)?;
2222    let lengths = extents
2223        .iter()
2224        .map(|extent| match extent {
2225            ShapeExtent::Exact(DimExpr::Const(value)) => Some(*value),
2226            ShapeExtent::UpperBound(DimExpr::Const(value)) if accept_upper_bound => Some(*value),
2227            _ => None,
2228        })
2229        .collect::<Option<Vec<_>>>();
2230    if let Some(lengths) = lengths {
2231        return Ok(lengths);
2232    }
2233    let expected = if accept_upper_bound {
2234        "constant exact or upper-bound extents"
2235    } else {
2236        "concrete extents"
2237    };
2238    Err(SemanticAdTransformError::UnsupportedMetadata {
2239        role: SemanticTransformRole::Vjp,
2240        message: format!("{field} requires {expected}"),
2241    })
2242}
2243
2244fn reshape_ad_value_to_shape(
2245    builder: &mut SemanticProgramBuilder,
2246    value: AdValue,
2247    shape: &ValueShapePlan,
2248) -> Result<AdValue, ProgramBuildError> {
2249    match value {
2250        AdValue::Absent => Ok(AdValue::Absent),
2251        AdValue::Value(value) => Ok(AdValue::Value(reshape_value_to_shape(
2252            builder, value, shape,
2253        )?)),
2254    }
2255}
2256
2257fn reshape_value_to_shape(
2258    builder: &mut SemanticProgramBuilder,
2259    value: ProgramValue,
2260    shape: &ValueShapePlan,
2261) -> Result<ProgramValue, ProgramBuildError> {
2262    let mut inputs = vec![value];
2263    let to_shape = builder.translate_input_shape_payload(&shape.shape, &mut inputs);
2264    Ok(builder.add_op(CoreSemanticOp::Reshape { to_shape }, &inputs)?[0])
2265}
2266
2267fn broadcast_ad_value_in_dim_to_shape(
2268    builder: &mut SemanticProgramBuilder,
2269    value: AdValue,
2270    shape: &ValueShapePlan,
2271    dims: Vec<usize>,
2272) -> Result<AdValue, ProgramBuildError> {
2273    match value {
2274        AdValue::Absent => Ok(AdValue::Absent),
2275        AdValue::Value(value) => Ok(AdValue::Value(broadcast_value_in_dim_to_shape(
2276            builder, value, shape, dims,
2277        )?)),
2278    }
2279}
2280
2281fn broadcast_value_in_dim_to_shape(
2282    builder: &mut SemanticProgramBuilder,
2283    value: ProgramValue,
2284    shape: &ValueShapePlan,
2285    dims: Vec<usize>,
2286) -> Result<ProgramValue, ProgramBuildError> {
2287    let mut inputs = vec![value];
2288    let shape = builder.translate_input_shape_payload(&shape.shape, &mut inputs);
2289    Ok(builder.add_op(CoreSemanticOp::BroadcastInDim { shape, dims }, &inputs)?[0])
2290}
2291
2292fn truncate_ad_value_to_dynamic_axes(
2293    builder: &mut SemanticProgramBuilder,
2294    value: AdValue,
2295    shape_source: ProgramValue,
2296    dynamic_axes: &[usize],
2297) -> Result<AdValue, SemanticAdTransformError> {
2298    let AdValue::Value(value) = value else {
2299        return Ok(AdValue::Absent);
2300    };
2301    Ok(AdValue::Value(truncate_value_to_dynamic_axes(
2302        builder,
2303        value,
2304        shape_source,
2305        dynamic_axes,
2306    )?))
2307}
2308
2309fn truncate_value_to_dynamic_axes(
2310    builder: &mut SemanticProgramBuilder,
2311    mut value: ProgramValue,
2312    shape_source: ProgramValue,
2313    dynamic_axes: &[usize],
2314) -> Result<ProgramValue, ProgramBuildError> {
2315    for &axis in dynamic_axes {
2316        let size = builder.add_op(CoreSemanticOp::ShapeOf { axis }, &[shape_source])?[0];
2317        value = builder.add_op(CoreSemanticOp::DynamicTruncate { axis }, &[value, size])?[0];
2318    }
2319    Ok(value)
2320}
2321
2322fn conjugate_if_complex(
2323    builder: &mut SemanticProgramBuilder,
2324    value: ProgramValue,
2325) -> Result<ProgramValue, ProgramBuildError> {
2326    if matches!(
2327        builder.value_metadata(value)?.dtype(),
2328        DType::C32 | DType::C64
2329    ) {
2330        Ok(builder.add_op(CoreSemanticOp::Conj, &[value])?[0])
2331    } else {
2332        Ok(value)
2333    }
2334}
2335
2336fn finish_derivative(
2337    builder: SemanticProgramBuilder,
2338    derivative_input_indices: Vec<Option<usize>>,
2339    values: Vec<AdValue>,
2340) -> Result<SemanticAdProgram, SemanticAdTransformError> {
2341    let mut outputs = Vec::new();
2342    let derivative_output_indices = values
2343        .into_iter()
2344        .map(|value| match value {
2345            AdValue::Absent => None,
2346            AdValue::Value(value) => {
2347                let index = outputs.len();
2348                outputs.push(value);
2349                Some(index)
2350            }
2351        })
2352        .collect();
2353    let frozen = builder.finish(&outputs)?;
2354    let frozen = prune_dead_derivative_operations(frozen)?;
2355    let frozen = cancel_double_neg_derivative_operations(frozen)?;
2356    Ok(SemanticAdProgram {
2357        frozen,
2358        derivative_input_indices: derivative_input_indices.into_boxed_slice(),
2359        derivative_output_indices,
2360    })
2361}
2362
2363fn prune_dead_derivative_operations(
2364    frozen: FrozenProgram,
2365) -> Result<FrozenProgram, SemanticAdTransformError> {
2366    let mut roots = frozen.program.inputs().to_vec();
2367    let output_offset = roots.len();
2368    roots.extend_from_slice(frozen.program.outputs());
2369
2370    let mut builder = SemanticProgramBuilder::new();
2371    let imported = builder.import(ProgramImport {
2372        program: frozen.program.as_ref(),
2373        bindings: Some(&frozen.bindings),
2374        input_map: &[],
2375        roots: &roots,
2376    })?;
2377    let outputs = imported.roots()[output_offset..].to_vec();
2378    Ok(builder.finish(&outputs)?)
2379}
2380
2381fn cancel_double_neg_derivative_operations(
2382    frozen: FrozenProgram,
2383) -> Result<FrozenProgram, SemanticAdTransformError> {
2384    let operations = frozen.program.operations().collect::<Vec<_>>();
2385    if operations.iter().any(|operation| {
2386        !operation.effects().is_empty()
2387            || !operation.shape_guards().is_empty()
2388            || !matches!(operation.op(), SemanticOpRef::Core(_))
2389    }) {
2390        return Ok(frozen);
2391    }
2392
2393    let mut builder = SemanticProgramBuilder::new();
2394    let imported = builder.import(ProgramImport {
2395        program: frozen.program.as_ref(),
2396        bindings: Some(&frozen.bindings),
2397        input_map: &[],
2398        roots: frozen.program.inputs(),
2399    })?;
2400    let mut values = frozen
2401        .program
2402        .inputs()
2403        .iter()
2404        .copied()
2405        .zip(imported.roots().iter().copied())
2406        .collect::<HashMap<_, _>>();
2407    let mut neg_inputs = HashMap::<ProgramValue, ProgramValue>::new();
2408    let mut changed = false;
2409
2410    for operation in operations {
2411        let inputs = operation
2412            .inputs()
2413            .iter()
2414            .copied()
2415            .map(|value| {
2416                values.get(&value).copied().ok_or_else(|| {
2417                    SemanticAdTransformError::UnsupportedMetadata {
2418                        role: SemanticTransformRole::Jvp,
2419                        message: "derivative simplifier saw an unmapped value".into(),
2420                    }
2421                })
2422            })
2423            .collect::<Result<Vec<_>, _>>()?;
2424        let SemanticOpRef::Core(op) = operation.op() else {
2425            unreachable!("non-core operations returned above");
2426        };
2427
2428        if matches!(op, CoreSemanticOp::Neg) {
2429            let input = inputs[0];
2430            if let Some(inner) = neg_inputs.get(&input).copied() {
2431                values.insert(operation.outputs()[0], inner);
2432                changed = true;
2433                continue;
2434            }
2435            let output = builder.add_op(CoreSemanticOp::Neg, &[input])?[0];
2436            neg_inputs.insert(output, input);
2437            values.insert(operation.outputs()[0], output);
2438            continue;
2439        }
2440
2441        let outputs = builder.add_op(op.clone(), &inputs)?;
2442        for (source, output) in operation
2443            .outputs()
2444            .iter()
2445            .copied()
2446            .zip(outputs.iter().copied())
2447        {
2448            values.insert(source, output);
2449        }
2450    }
2451
2452    if !changed {
2453        return Ok(frozen);
2454    }
2455
2456    let outputs = frozen
2457        .program
2458        .outputs()
2459        .iter()
2460        .copied()
2461        .map(|value| {
2462            values.get(&value).copied().ok_or_else(|| {
2463                SemanticAdTransformError::UnsupportedMetadata {
2464                    role: SemanticTransformRole::Jvp,
2465                    message: "derivative simplifier saw an unmapped output".into(),
2466                }
2467            })
2468        })
2469        .collect::<Result<Vec<_>, _>>()?;
2470    prune_dead_derivative_operations(builder.finish(&outputs)?)
2471}
2472
2473fn validate_activity(
2474    role: SemanticTransformRole,
2475    field: &'static str,
2476    expected: usize,
2477    actual: usize,
2478) -> Result<(), SemanticAdTransformError> {
2479    if expected == actual {
2480        Ok(())
2481    } else {
2482        Err(SemanticAdTransformError::ActivityArity {
2483            role,
2484            field,
2485            expected,
2486            actual,
2487        })
2488    }
2489}
2490
2491fn unsupported_core(role: SemanticTransformRole, op: &CoreSemanticOp) -> SemanticAdTransformError {
2492    SemanticAdTransformError::UnsupportedCore {
2493        role,
2494        op: format!("{op:?}"),
2495    }
2496}