Skip to main content

tenferro_fft/
lib.rs

1//! FFT extension operations for tenferro.
2//!
3//! This crate is an out-of-tree `ExtensionOp` package with an explicit
4//! [`FftBackend`] capability. [`tenferro_cpu::CpuEngine`] implements the
5//! capability through RustFFT. With the `cuda` feature,
6//! `tenferro_gpu::cuda::CudaEngine` executes the
7//! supported F32/F64/C32/C64 operations through dynamically loaded cuFFT
8//! without implicit transfers or CPU fallback. The vendor call synchronizes at
9//! the cuFFT FFI boundary; subsequent CUDA postprocessing and explicit download
10//! remain stream-managed. Backend choice remains explicit.
11//!
12//! Every operation is declared once in the operation registry (#2552) and
13//! offered on three layers with the same spellings:
14//!
15//! | Layer | Trait | Receiver | Spellings |
16//! |---|---|---|---|
17//! | concrete | [`FftOps`] | anything that implements [`AsView`](tenferro_tensor::AsView) | `x.fft(exec)`, `x.fft_with(&opts, exec)` |
18//! | traced | [`TracedFftOps`] | [`TracedTensor`] | `t.fft()`, `t.fft_with(&opts)` |
19//! | eager (`autodiff`) | `EagerFftOps` | `EagerSession` | `sess.fft(&x)`, `sess.fft_with(&x, &opts)` |
20//!
21//! The operations are `fft`, `ifft`, `rfft`, `irfft` ([`FftOptions`]: `n`,
22//! `axis`, `norm`) and `fftn`, `ifftn`, `rfftn`, `irfftn` ([`FftnOptions`]:
23//! `shape`, `axes`, `norm`). Two exceptions keep their own shape: the
24//! consuming eager transforms `sess.fft_in_place(x, &opts)` /
25//! `sess.ifft_in_place(x, &opts)` (E01) and the plan-cache owner
26//! [`FftExecutor`] (`executor.fft_with(&x, &opts, exec)`, E02). The generated
27//! page `docs/spec/generated/api-ops.md` lists layout handling, errors and
28//! omissions per operation.
29//!
30//! # Cargo features
31//!
32//! | Feature | Enables |
33//! |---|---|
34//! | `autodiff` | The eager layer (`EagerFftOps`) and AD rules. Adds the `tenferro-ad` dependency. |
35//! | `cuda` | CUDA execution through `tenferro-gpu`. |
36//!
37//! For transforms without AD, use [`FftOps`] on concrete tensors; it needs no
38//! `autodiff`.
39//!
40//! # N-dimensional transforms
41//!
42//! `fftn`, `ifftn`, `rfftn` and `irfftn` transform every axis in
43//! [`FftnOptions::axes`] (empty selects them as NumPy does). One declared
44//! axis is the ordinary one-axis transform: it runs the same single backend
45//! call, so `fftn` over `[axis]` equals `fft` along `axis`.
46//!
47//! The normalization of [`FftNorm`] is applied once to the whole transform, not
48//! once per axis: the transform over axes with `P = prod(shape over axes)` is
49//! scaled by `1 / P` in the direction that `Backward`/`Forward` selects, and by
50//! `1 / sqrt(P)` on both sides for `Ortho`. That is also the composition of the
51//! one-axis transforms, whose per-axis factors multiply to the same single
52//! factor.
53//!
54//! With the `cuda` feature, each axis is one `cufftPlanMany` transform of that
55//! one-dimensional length, run over the resident tensor; an n-dimensional
56//! request therefore uses one cuFFT plan per axis and never transfers the
57//! intermediate spectra. A single multi-dimensional cuFFT plan is not used yet.
58//!
59//! # Examples
60//!
61//! Traced: record, compile, run.
62//!
63//! ```
64//! use num_complex::Complex64;
65//! use tenferro_cpu::CpuEngine;
66//! use tenferro_fft::TracedFftOps;
67//! use tenferro_runtime::{ExecutionEngine, GraphCompiler, Runtime, TraceContext};
68//!
69//! let trace = TraceContext::new();
70//! let x = trace.from_vec_col_major(
71//!     vec![4],
72//!     vec![
73//!         Complex64::new(1.0, 0.0),
74//!         Complex64::new(2.0, 0.0),
75//!         Complex64::new(3.0, 0.0),
76//!         Complex64::new(4.0, 0.0),
77//!     ],
78//! )?;
79//! let y = x.fft()?;
80//!
81//! let program = GraphCompiler::new().compile(&y)?;
82//! let mut engine = CpuEngine::serial();
83//! let engine_id = tenferro_cpu::runtime_engine_id()?;
84//! let mut builder = Runtime::builder();
85//! builder.register_engine(tenferro_cpu::runtime_engine_registration(&engine)?)?;
86//! builder.install_extension_module(tenferro_fft::extension_module::<CpuEngine>(engine_id)?)?;
87//! let runtime = builder.build()?;
88//! let prepared = runtime.prepare(&program, &[], &[engine.target()])?;
89//! let out = {
90//!     let mut engines: [&mut dyn ExecutionEngine; 1] = [&mut engine];
91//!     runtime.run(&mut engines, &prepared, &[])?.pop().ok_or("no output")?
92//! }
93//! .into_tensor(&mut engine)?;
94//! assert_eq!(out.shape(), &[4]);
95//! assert_eq!(out.as_slice::<Complex64>()?[0], Complex64::new(10.0, 0.0));
96//! # Ok::<(), Box<dyn std::error::Error>>(())
97//! ```
98//!
99//! Concrete, with options:
100//!
101//! ```
102//! use num_complex::Complex64;
103//! use tenferro_cpu::CpuEngine;
104//! use tenferro_fft::{FftNorm, FftOps, FftOptions};
105//! use tenferro_tensor::Tensor;
106//!
107//! let x = Tensor::from_vec_col_major(vec![4], vec![1.0_f64, 2.0, 3.0, 4.0])?;
108//! let mut engine = CpuEngine::serial();
109//! let out = x.fft(&mut engine)?;
110//! assert_eq!(out.as_slice::<Complex64>()?[0], Complex64::new(10.0, 0.0));
111//!
112//! let ortho = x.fft_with(&FftOptions::default().norm(FftNorm::Ortho), &mut engine)?;
113//! assert_eq!(ortho.as_slice::<Complex64>()?[0], Complex64::new(5.0, 0.0));
114//! # Ok::<(), Box<dyn std::error::Error>>(())
115//! ```
116#![cfg_attr(docsrs, feature(doc_cfg))]
117
118use std::any::Any;
119use std::hash::Hasher;
120use std::num::NonZeroUsize;
121use std::sync::Arc;
122
123#[cfg(feature = "autodiff")]
124use tenferro_ad::semantic_extension::{
125    AdValue, ResidualSpec, SemanticAdError, SemanticExtensionRegistryError,
126    SemanticExtensionRuleSet, SemanticLinearTransposeRequest, SemanticLinearTransposeRule,
127    SemanticLinearizeRequest, SemanticLinearizeResult, SemanticLinearizeRule,
128    SemanticPrimalVjpRequest, SemanticPrimalVjpRule,
129};
130use tenferro_cpu::with_cpu_engine;
131use tenferro_extension_macros::define_extension_runtime;
132#[cfg(feature = "cuda")]
133use tenferro_gpu::cuda::raw::with_cuda_engine;
134#[cfg(feature = "cuda")]
135use tenferro_gpu::cuda::CudaEngine;
136use tenferro_ops::SymDim;
137use tenferro_runtime::extension::{
138    apply, ExtensionCacheStore, ExtensionExecutionContext, ExtensionOp,
139};
140#[cfg(feature = "autodiff")]
141use tenferro_runtime::program::{CoreSemanticOp, ProgramValue, SemanticProgramBuilder};
142use tenferro_runtime::{Error, ErrorPhase, Result, TracedTensor};
143use tenferro_tensor::{CacheStats, DType, Engine, ErrorKind, Tensor, TensorRead};
144
145mod api;
146mod backend;
147mod cache;
148mod cpu;
149#[cfg(feature = "cuda")]
150mod cuda;
151#[cfg(feature = "autodiff")]
152mod eager_ext;
153#[cfg(feature = "autodiff")]
154mod eager_in_place;
155pub mod prelude;
156mod spec;
157
158#[cfg(feature = "autodiff")]
159#[cfg_attr(docsrs, doc(cfg(feature = "autodiff")))]
160pub use api::EagerFftOps;
161pub use api::{FftOps, FftOptions, FftRepr, FftScalar, FftnOptions, TracedFftOps};
162pub use backend::{FftBackend, FftExecutionCache};
163pub use cache::{
164    fft_plan_cache_selector, FftPlanCache, DEFAULT_FFT_PLAN_CACHE_CAPACITY, FFT_PLAN_CACHE_NAME,
165};
166#[cfg(feature = "autodiff")]
167#[cfg_attr(docsrs, doc(cfg(feature = "autodiff")))]
168pub use eager_in_place::EagerFftInPlaceError;
169pub use spec::{FftNorm, FftOperation, FftPlanSpec};
170
171/// Extension family id used by the tenferro FFT extension.
172///
173/// # Examples
174///
175/// ```
176/// assert_eq!(
177///     tenferro_fft::FFT_EXTENSION_FAMILY_ID,
178///     "tenferro-fft.fft.v1"
179/// );
180/// ```
181pub const FFT_EXTENSION_FAMILY_ID: &str = "tenferro-fft.fft.v1";
182
183/// Reusable concrete FFT executor with an explicitly owned backend-neutral cache.
184///
185/// Use this executor for repeated concrete FFT calls that should reuse backend
186/// plans (exception E02). The [`FftOps`] methods stay
187/// one-shot and do not retain hidden process-global, thread-local, or
188/// backend-owned plan state between calls.
189#[derive(Default)]
190pub struct FftExecutor {
191    plans: FftPlanCache,
192}
193
194impl FftExecutor {
195    /// Create an executor from a caller-configured FFT execution cache.
196    pub fn new(plans: FftPlanCache) -> Self {
197        Self { plans }
198    }
199
200    /// Inspect the owned backend-neutral FFT cache.
201    pub const fn plan_cache(&self) -> &FftPlanCache {
202        &self.plans
203    }
204
205    /// Mutably inspect or configure the owned backend-neutral FFT cache.
206    pub fn plan_cache_mut(&mut self) -> &mut FftPlanCache {
207        &mut self.plans
208    }
209
210    /// Snapshot aggregate statistics for every backend cache namespace.
211    pub fn cache_stats(&self) -> CacheStats {
212        self.plans.stats()
213    }
214
215    /// Remove every retained backend plan or workspace from this executor.
216    pub fn clear_cache(&mut self) {
217        self.plans.clear();
218    }
219
220    fn one_axis_with(
221        &mut self,
222        op: &'static str,
223        operation_of: fn(&'static str, DType) -> tenferro_tensor::Result<FftOperation>,
224        input: &Tensor,
225        opts: &FftOptions,
226        exec: &mut dyn Engine,
227    ) -> tenferro_tensor::Result<Tensor> {
228        self.execute(
229            input,
230            operation_of(op, input.dtype())?,
231            op,
232            opts.n,
233            opts.axis,
234            opts.norm,
235            exec,
236        )
237    }
238
239    fn n_axes_with(
240        &mut self,
241        op: &'static str,
242        operation_of: fn(&'static str, DType) -> tenferro_tensor::Result<FftOperation>,
243        input: &Tensor,
244        opts: &FftnOptions,
245        exec: &mut dyn Engine,
246    ) -> tenferro_tensor::Result<Tensor> {
247        let axes = opts.resolved_axes(input.shape().len());
248        self.execute_nd(
249            op,
250            operation_of(op, input.dtype())?,
251            input,
252            opts.shape.as_deref(),
253            &axes,
254            opts.norm,
255            exec,
256        )
257    }
258
259    /// [`FftOps::fft`] (complex, or full spectrum of a real input) reusing this
260    /// executor's plans. Bit-identical to `FftOps::fft_with` on the same input.
261    ///
262    /// # Errors
263    ///
264    /// As [`FftOps::fft`]: `Validation` for an invalid `axis`/`n`,
265    /// `Unsupported` for an unsupported dtype or an engine without an FFT
266    /// capability, or the backend's typed error.
267    ///
268    /// # Examples
269    ///
270    /// ```
271    /// use num_complex::Complex64;
272    /// use tenferro_cpu::CpuEngine;
273    /// use tenferro_fft::{FftExecutor, FftOptions};
274    /// use tenferro_tensor::Tensor;
275    ///
276    /// let mut executor = FftExecutor::default();
277    /// let x = Tensor::from_vec_col_major(vec![4], vec![1.0_f64, 2.0, 3.0, 4.0])?;
278    /// let y = executor.fft_with(&x, &FftOptions::default(), &mut CpuEngine::serial())?;
279    /// assert_eq!(y.as_slice::<Complex64>()?[0], Complex64::new(10.0, 0.0));
280    /// assert!(executor.cache_stats().entries > 0);
281    /// # Ok::<(), tenferro_tensor::Error>(())
282    /// ```
283    pub fn fft_with(
284        &mut self,
285        input: &Tensor,
286        opts: &FftOptions,
287        exec: &mut dyn Engine,
288    ) -> tenferro_tensor::Result<Tensor> {
289        self.one_axis_with(
290            "FftExecutor::fft_with",
291            concrete_fft_operation,
292            input,
293            opts,
294            exec,
295        )
296    }
297
298    /// [`FftOps::ifft`] reusing this executor's plans.
299    ///
300    /// # Errors
301    ///
302    /// As [`FftOps::ifft`]: `Validation` for an invalid `axis`/`n`,
303    /// `Unsupported` for an unsupported dtype or an engine without an FFT
304    /// capability, or the backend's typed error.
305    ///
306    /// # Examples
307    ///
308    /// ```
309    /// use num_complex::Complex64;
310    /// use tenferro_cpu::CpuEngine;
311    /// use tenferro_fft::{FftExecutor, FftOptions};
312    /// use tenferro_tensor::Tensor;
313    ///
314    /// let mut executor = FftExecutor::default();
315    /// let x = Tensor::from_vec_col_major(
316    ///     vec![2],
317    ///     vec![Complex64::new(3.0, 0.0), Complex64::new(-1.0, 0.0)],
318    /// )?;
319    /// let y = executor.ifft_with(&x, &FftOptions::default(), &mut CpuEngine::serial())?;
320    /// assert_eq!(y.as_slice::<Complex64>()?[1], Complex64::new(2.0, 0.0));
321    /// # Ok::<(), tenferro_tensor::Error>(())
322    /// ```
323    pub fn ifft_with(
324        &mut self,
325        input: &Tensor,
326        opts: &FftOptions,
327        exec: &mut dyn Engine,
328    ) -> tenferro_tensor::Result<Tensor> {
329        self.one_axis_with(
330            "FftExecutor::ifft_with",
331            concrete_ifft_operation,
332            input,
333            opts,
334            exec,
335        )
336    }
337
338    /// [`FftOps::rfft`] reusing this executor's plans.
339    ///
340    /// # Errors
341    ///
342    /// As [`FftOps::rfft`]: `Validation` for an invalid `axis`/`n` or a
343    /// non-real input, `Unsupported` for an unsupported dtype or an engine
344    /// without an FFT capability, or the backend's typed error.
345    ///
346    /// # Examples
347    ///
348    /// ```
349    /// use tenferro_cpu::CpuEngine;
350    /// use tenferro_fft::{FftExecutor, FftOptions};
351    /// use tenferro_tensor::Tensor;
352    ///
353    /// let mut executor = FftExecutor::default();
354    /// let x = Tensor::from_vec_col_major(vec![4], vec![1.0_f64, 2.0, 3.0, 4.0])?;
355    /// let y = executor.rfft_with(&x, &FftOptions::default(), &mut CpuEngine::serial())?;
356    /// assert_eq!(y.shape(), &[3]);
357    /// # Ok::<(), tenferro_tensor::Error>(())
358    /// ```
359    pub fn rfft_with(
360        &mut self,
361        input: &Tensor,
362        opts: &FftOptions,
363        exec: &mut dyn Engine,
364    ) -> tenferro_tensor::Result<Tensor> {
365        self.one_axis_with(
366            "FftExecutor::rfft_with",
367            concrete_rfft_operation,
368            input,
369            opts,
370            exec,
371        )
372    }
373
374    /// [`FftOps::irfft`] reusing this executor's plans.
375    ///
376    /// # Errors
377    ///
378    /// As [`FftOps::irfft`]: `Validation` for an invalid `axis`/`n` or a
379    /// complex input, `Unsupported` for an unsupported dtype or an engine
380    /// without an FFT capability, or the backend's typed error.
381    ///
382    /// # Examples
383    ///
384    /// ```
385    /// use num_complex::Complex64;
386    /// use tenferro_cpu::CpuEngine;
387    /// use tenferro_fft::{FftExecutor, FftOptions};
388    /// use tenferro_tensor::Tensor;
389    ///
390    /// let mut executor = FftExecutor::default();
391    /// let x = Tensor::from_vec_col_major(
392    ///     vec![3],
393    ///     vec![Complex64::new(10.0, 0.0), Complex64::new(0.0, 0.0), Complex64::new(-2.0, 0.0)],
394    /// )?;
395    /// let y = executor.irfft_with(&x, &FftOptions::default(), &mut CpuEngine::serial())?;
396    /// assert_eq!(y.shape(), &[4]);
397    /// # Ok::<(), tenferro_tensor::Error>(())
398    /// ```
399    pub fn irfft_with(
400        &mut self,
401        input: &Tensor,
402        opts: &FftOptions,
403        exec: &mut dyn Engine,
404    ) -> tenferro_tensor::Result<Tensor> {
405        self.one_axis_with(
406            "FftExecutor::irfft_with",
407            concrete_irfft_operation,
408            input,
409            opts,
410            exec,
411        )
412    }
413
414    /// [`FftOps::fftn`] reusing this executor's plans.
415    ///
416    /// # Errors
417    ///
418    /// As [`FftOps::fftn`]: `Validation` for an invalid `axes`/`shape`/`n`,
419    /// `Unsupported` for an unsupported dtype or an engine without an N-d FFT
420    /// capability, or the backend's typed error.
421    ///
422    /// # Examples
423    ///
424    /// ```
425    /// use num_complex::Complex64;
426    /// use tenferro_cpu::CpuEngine;
427    /// use tenferro_fft::{FftExecutor, FftnOptions};
428    /// use tenferro_tensor::Tensor;
429    ///
430    /// let mut executor = FftExecutor::default();
431    /// let x = Tensor::from_vec_col_major(vec![2, 2], vec![1.0_f64, 2.0, 3.0, 4.0])?;
432    /// let y = executor.fftn_with(&x, &FftnOptions::default(), &mut CpuEngine::serial())?;
433    /// assert_eq!(y.as_slice::<Complex64>()?[0], Complex64::new(10.0, 0.0));
434    /// # Ok::<(), tenferro_tensor::Error>(())
435    /// ```
436    pub fn fftn_with(
437        &mut self,
438        input: &Tensor,
439        opts: &FftnOptions,
440        exec: &mut dyn Engine,
441    ) -> tenferro_tensor::Result<Tensor> {
442        self.n_axes_with(
443            "FftExecutor::fftn_with",
444            concrete_fft_operation,
445            input,
446            opts,
447            exec,
448        )
449    }
450
451    /// [`FftOps::ifftn`] reusing this executor's plans.
452    ///
453    /// # Errors
454    ///
455    /// As [`FftOps::ifftn`]: `Validation` for an invalid `axes`/`shape`/`n`,
456    /// `Unsupported` for an unsupported dtype or an engine without an N-d FFT
457    /// capability, or the backend's typed error.
458    ///
459    /// # Examples
460    ///
461    /// ```
462    /// use num_complex::Complex64;
463    /// use tenferro_cpu::CpuEngine;
464    /// use tenferro_fft::{FftExecutor, FftnOptions};
465    /// use tenferro_tensor::Tensor;
466    ///
467    /// let mut executor = FftExecutor::default();
468    /// let x = Tensor::from_vec_col_major(vec![1, 2], vec![Complex64::new(3.0, 0.0), Complex64::new(-1.0, 0.0)])?;
469    /// let y = executor.ifftn_with(&x, &FftnOptions::default(), &mut CpuEngine::serial())?;
470    /// assert_eq!(y.as_slice::<Complex64>()?[1], Complex64::new(2.0, 0.0));
471    /// # Ok::<(), tenferro_tensor::Error>(())
472    /// ```
473    pub fn ifftn_with(
474        &mut self,
475        input: &Tensor,
476        opts: &FftnOptions,
477        exec: &mut dyn Engine,
478    ) -> tenferro_tensor::Result<Tensor> {
479        self.n_axes_with(
480            "FftExecutor::ifftn_with",
481            concrete_ifft_operation,
482            input,
483            opts,
484            exec,
485        )
486    }
487
488    /// [`FftOps::rfftn`] reusing this executor's plans.
489    ///
490    /// # Errors
491    ///
492    /// As [`FftOps::rfftn`]: `Validation` for an invalid `axes`/`shape`/`n` or a
493    /// non-real input, `Unsupported` for an unsupported dtype or an engine
494    /// without an N-d FFT capability, or the backend's typed error.
495    ///
496    /// # Examples
497    ///
498    /// ```
499    /// use tenferro_cpu::CpuEngine;
500    /// use tenferro_fft::{FftExecutor, FftnOptions};
501    /// use tenferro_tensor::Tensor;
502    ///
503    /// let mut executor = FftExecutor::default();
504    /// let x = Tensor::from_vec_col_major(vec![2, 4], vec![1.0_f64; 8])?;
505    /// let y = executor.rfftn_with(&x, &FftnOptions::default(), &mut CpuEngine::serial())?;
506    /// assert_eq!(y.shape(), &[2, 3]);
507    /// # Ok::<(), tenferro_tensor::Error>(())
508    /// ```
509    pub fn rfftn_with(
510        &mut self,
511        input: &Tensor,
512        opts: &FftnOptions,
513        exec: &mut dyn Engine,
514    ) -> tenferro_tensor::Result<Tensor> {
515        self.n_axes_with(
516            "FftExecutor::rfftn_with",
517            concrete_rfft_operation,
518            input,
519            opts,
520            exec,
521        )
522    }
523
524    /// [`FftOps::irfftn`] reusing this executor's plans.
525    ///
526    /// # Errors
527    ///
528    /// As [`FftOps::irfftn`]: `Validation` for an invalid `axes`/`shape`/`n` or a
529    /// complex input, `Unsupported` for an unsupported dtype or an engine
530    /// without an N-d FFT capability, or the backend's typed error.
531    ///
532    /// # Examples
533    ///
534    /// ```
535    /// use num_complex::Complex64;
536    /// use tenferro_cpu::CpuEngine;
537    /// use tenferro_fft::{FftExecutor, FftnOptions};
538    /// use tenferro_tensor::Tensor;
539    ///
540    /// let mut executor = FftExecutor::default();
541    /// let mut spectrum = vec![Complex64::new(0.0, 0.0); 6];
542    /// spectrum[0] = Complex64::new(8.0, 0.0);
543    /// let x = Tensor::from_vec_col_major(vec![2, 3], spectrum)?;
544    /// let y = executor.irfftn_with(&x, &FftnOptions::default(), &mut CpuEngine::serial())?;
545    /// assert_eq!(y.as_slice::<f64>()?, &[1.0; 8]);
546    /// # Ok::<(), tenferro_tensor::Error>(())
547    /// ```
548    pub fn irfftn_with(
549        &mut self,
550        input: &Tensor,
551        opts: &FftnOptions,
552        exec: &mut dyn Engine,
553    ) -> tenferro_tensor::Result<Tensor> {
554        self.n_axes_with(
555            "FftExecutor::irfftn_with",
556            concrete_irfft_operation,
557            input,
558            opts,
559            exec,
560        )
561    }
562
563    /// Validate an n-dimensional request and run it through the shared
564    /// extension execution path, which owns the axis loop and the plan cache.
565    #[allow(clippy::too_many_arguments)]
566    fn execute_nd(
567        &mut self,
568        op_name: &'static str,
569        operation: FftOperation,
570        input: &Tensor,
571        shape: Option<&[usize]>,
572        axes: &[isize],
573        norm: FftNorm,
574        session: &mut dyn Engine,
575    ) -> tenferro_tensor::Result<Tensor> {
576        let fft_op = validated_fft_op(
577            op_name,
578            operation,
579            Some(input.dtype()),
580            input.shape().len(),
581            Some(input.shape()),
582            shape,
583            "shape",
584            axes,
585            norm,
586        )?;
587        with_fft_exec_session(session, op_name, |backend| {
588            execute_fft_op(
589                &fft_op,
590                &TensorRead::Tensor(input),
591                backend,
592                FftExecutionCache::caller_owned(&mut self.plans),
593            )
594        })
595    }
596
597    #[allow(clippy::too_many_arguments)]
598    fn execute(
599        &mut self,
600        input: &Tensor,
601        operation: FftOperation,
602        op_name: &'static str,
603        n: Option<usize>,
604        axis: isize,
605        norm: FftNorm,
606        session: &mut dyn Engine,
607    ) -> tenferro_tensor::Result<Tensor> {
608        let spec = concrete_fft_spec(
609            op_name,
610            operation,
611            input.dtype(),
612            input.shape(),
613            n,
614            axis,
615            norm,
616        )?;
617        // The executor calls the concrete backend directly (no internal
618        // session entry); the built-in dispatch only bridges the borrowed
619        // session to its FFT execution capability.
620        with_fft_exec_session(session, op_name, |backend| {
621            backend.execute_fft(
622                input,
623                &spec,
624                FftExecutionCache::caller_owned(&mut self.plans),
625            )
626        })
627    }
628}
629
630#[derive(Debug, thiserror::Error)]
631enum FftError {
632    #[error("{op} does not support dtype {dtype:?}; expected {expected}")]
633    UnsupportedDType {
634        op: &'static str,
635        dtype: DType,
636        expected: &'static str,
637    },
638}
639
640#[derive(Clone, Debug, PartialEq)]
641struct FftOp {
642    operation: FftOperation,
643    /// Validated, non-empty, duplicate-free axes. The last axis is the real
644    /// transform axis of `R2cFull`/`R2cOnesided`/`C2r`, as in NumPy `rfftn`.
645    axes: Vec<usize>,
646    /// One requested length per axis, when the caller supplied them.
647    lengths: Option<Vec<usize>>,
648    norm: FftNorm,
649}
650
651impl FftOp {
652    fn new(
653        operation: FftOperation,
654        axes: Vec<usize>,
655        lengths: Option<Vec<usize>>,
656        norm: FftNorm,
657    ) -> Self {
658        Self {
659            operation,
660            axes,
661            lengths,
662            norm,
663        }
664    }
665
666    /// Single spec for the whole request, used by concrete single-axis backends.
667    fn spec(&self, dtype: DType, shape: &[usize]) -> FftPlanSpec {
668        FftPlanSpec::new(
669            self.operation,
670            self.axes.clone(),
671            self.lengths.clone(),
672            self.norm,
673            dtype,
674            shape.to_vec(),
675        )
676    }
677
678    /// Single-axis spec for the `index`-th declared axis against `shape`.
679    fn step_spec(&self, index: usize, dtype: DType, shape: &[usize]) -> FftPlanSpec {
680        FftPlanSpec::new(
681            self.operation.step_operation(index, self.axes.len()),
682            vec![self.axes[index]],
683            self.lengths.as_ref().map(|lengths| vec![lengths[index]]),
684            self.norm,
685            dtype,
686            shape.to_vec(),
687        )
688    }
689
690    /// Axis application order for the successive one-dimensional transforms.
691    ///
692    /// Complex transforms commute, so they keep the declared order. A real
693    /// forward transform must consume the real input first, and a complex-to-real
694    /// inverse must produce real output last; both name their real axis last, so
695    /// only the forward case needs the rotation.
696    fn execution_order(&self) -> Vec<usize> {
697        let mut order: Vec<usize> = (0..self.axes.len()).collect();
698        if matches!(
699            self.operation,
700            FftOperation::R2cFull | FftOperation::R2cOnesided
701        ) {
702            order.rotate_right(1);
703        }
704        order
705    }
706
707    #[cfg(feature = "autodiff")]
708    fn c2c_adjoint(&self) -> Option<Self> {
709        let operation = match self.operation {
710            FftOperation::C2cForward => FftOperation::C2cInverse,
711            FftOperation::C2cInverse => FftOperation::C2cForward,
712            FftOperation::R2cFull | FftOperation::R2cOnesided | FftOperation::C2r => return None,
713        };
714        Some(Self {
715            operation,
716            axes: self.axes.clone(),
717            lengths: self.lengths.clone(),
718            norm: self.norm.c2c_adjoint(),
719        })
720    }
721}
722
723impl ExtensionOp for FftOp {
724    fn family_id(&self) -> &'static str {
725        FFT_EXTENSION_FAMILY_ID
726    }
727
728    fn payload_hash(&self, hasher: &mut dyn Hasher) {
729        let operation = match self.operation {
730            FftOperation::C2cForward => 0,
731            FftOperation::C2cInverse => 1,
732            FftOperation::R2cOnesided => 2,
733            FftOperation::R2cFull => 3,
734            FftOperation::C2r => 4,
735        };
736        hasher.write_u8(operation);
737        hasher.write_usize(self.axes.len());
738        for axis in &self.axes {
739            hasher.write_usize(*axis);
740        }
741        match &self.lengths {
742            Some(lengths) => {
743                hasher.write_u8(1);
744                for len in lengths {
745                    hasher.write_usize(*len);
746                }
747            }
748            None => hasher.write_u8(0),
749        }
750        let norm = match self.norm {
751            FftNorm::Backward => 0,
752            FftNorm::Forward => 1,
753            FftNorm::Ortho => 2,
754        };
755        hasher.write_u8(norm);
756    }
757
758    fn payload_eq(&self, other: &dyn ExtensionOp) -> bool {
759        other
760            .as_any()
761            .downcast_ref::<FftOp>()
762            .is_some_and(|that| self == that)
763    }
764
765    fn clone_arc(&self) -> Arc<dyn ExtensionOp> {
766        Arc::new(self.clone())
767    }
768
769    fn as_any(&self) -> &dyn Any {
770        self
771    }
772
773    fn input_count(&self) -> usize {
774        1
775    }
776
777    fn output_count(&self) -> usize {
778        1
779    }
780
781    fn semantic_effects(&self) -> tenferro_ops::ext_op::ExtensionEffectDeclaration<'_> {
782        tenferro_ops::ext_op::ExtensionEffectDeclaration::Declared(&[])
783    }
784
785    fn semantic_aliases(&self) -> tenferro_ops::ext_op::ExtensionAliasDeclaration<'_> {
786        tenferro_ops::ext_op::ExtensionAliasDeclaration::AllFresh
787    }
788
789    fn infer_output_meta(
790        &self,
791        ctx: &mut tenferro_ops::ExtensionShapeContext<'_>,
792    ) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
793        let input_dtype = ctx.input_dtype(0)?;
794        let input_shape = ctx.input_shape(0)?;
795        let output_dtype = match self.operation {
796            FftOperation::C2cForward | FftOperation::C2cInverse => {
797                if !matches!(input_dtype, DType::C32 | DType::C64) {
798                    return Err(tensor_unsupported_dtype(
799                        "tenferro-fft",
800                        input_dtype,
801                        "C32 or C64",
802                    ));
803                }
804                input_dtype
805            }
806            FftOperation::R2cFull | FftOperation::R2cOnesided => match input_dtype {
807                DType::F32 => DType::C32,
808                DType::F64 => DType::C64,
809                _ => {
810                    return Err(tensor_unsupported_dtype(
811                        "tenferro-fft",
812                        input_dtype,
813                        "F32 or F64",
814                    ));
815                }
816            },
817            FftOperation::C2r => match input_dtype {
818                DType::C32 => DType::F32,
819                DType::C64 => DType::F64,
820                _ => {
821                    return Err(tensor_unsupported_dtype(
822                        "tenferro-fft",
823                        input_dtype,
824                        "C32 or C64",
825                    ));
826                }
827            },
828        };
829
830        let count = self.axes.len();
831        let mut out_shape = input_shape.to_vec();
832        for (index, &axis) in self.axes.iter().enumerate() {
833            if axis >= input_shape.len() {
834                return Err(tenferro_tensor::Error::axis_out_of_bounds(
835                    "tenferro-fft",
836                    axis,
837                    input_shape.len(),
838                ));
839            }
840            let len = self.lengths.as_ref().map(|lengths| lengths[index]);
841            out_shape[axis] = match self.operation.step_operation(index, count) {
842                FftOperation::C2cForward | FftOperation::C2cInverse => {
843                    transform_len_dim(len, &input_shape[axis])?
844                }
845                FftOperation::R2cFull | FftOperation::R2cOnesided => {
846                    let len = transform_len_dim(len, &input_shape[axis])?;
847                    if self.operation.is_onesided() {
848                        len / 2usize + 1usize
849                    } else {
850                        len
851                    }
852                }
853                FftOperation::C2r => output_dim_c2r(&input_shape[axis], len)?,
854            };
855        }
856
857        Ok(vec![(output_dtype, out_shape)])
858    }
859}
860
861/// Run a concrete FFT body against the built-in FFT execution sessions
862/// carried by `session` (CPU/CUDA/WebGPU), returning a typed capability error
863/// when the session does not expose an FFT execution capability.
864///
865/// This is the built-in dispatch shared by the concrete FFT surface; callers
866/// never downcast themselves (issue #1680 Phase 3). Third-party
867/// [`FftBackend`] implementations remain supported through the SPI trait, but
868/// the concrete op path is built-in-session only.
869fn with_fft_exec_session<X>(
870    session: &mut dyn Engine,
871    op: &'static str,
872    f: impl FnOnce(&mut dyn FftBackend) -> tenferro_tensor::Result<X>,
873) -> tenferro_tensor::Result<X> {
874    // The capability branches are mutually exclusive, so `f` runs exactly
875    // once. Probe the marker first, then re-extract the same exec session and
876    // run the concrete body on it (FnOnce cannot be captured by several
877    // branch closures).
878    if with_cpu_engine(session, |_| ()).is_some() {
879        return with_cpu_engine(session, |exec| f(exec as &mut dyn FftBackend))
880            .expect("marker probe matched a CPU execution session");
881    }
882    #[cfg(feature = "cuda")]
883    if with_cuda_engine(session, |_| ()).is_some() {
884        return with_cuda_engine(session, |exec| f(exec as &mut dyn FftBackend))
885            .expect("marker probe matched a CUDA execution session");
886    }
887    Err(tenferro_tensor::Error::unsupported(
888        op,
889        "selected backend session does not expose an FFT execution capability",
890    ))
891}
892
893fn execute_concrete_fft_op(
894    input: &Tensor,
895    spec: &FftPlanSpec,
896    backend: &mut dyn FftBackend,
897) -> tenferro_tensor::Result<Tensor> {
898    let mut plans = FftPlanCache::with_capacity(NonZeroUsize::MIN);
899    backend.execute_fft(input, spec, FftExecutionCache::caller_owned(&mut plans))
900}
901
902#[allow(clippy::too_many_arguments)]
903fn execute_concrete_fft_read_op(
904    input: &TensorRead<'_>,
905    operation: FftOperation,
906    op_name: &'static str,
907    n: Option<usize>,
908    axis: isize,
909    norm: FftNorm,
910    backend: &mut dyn FftBackend,
911) -> tenferro_tensor::Result<Tensor> {
912    let spec = concrete_fft_spec(
913        op_name,
914        operation,
915        input.dtype(),
916        input.shape(),
917        n,
918        axis,
919        norm,
920    )?;
921    let mut plans = FftPlanCache::with_capacity(NonZeroUsize::MIN);
922    backend.execute_fft_read(
923        input.clone(),
924        &spec,
925        FftExecutionCache::caller_owned(&mut plans),
926    )
927}
928
929#[allow(clippy::too_many_arguments)]
930fn concrete_fft_spec(
931    op: &'static str,
932    operation: FftOperation,
933    input_dtype: DType,
934    input_shape: &[usize],
935    n: Option<usize>,
936    axis: isize,
937    norm: FftNorm,
938) -> tenferro_tensor::Result<FftPlanSpec> {
939    validated_fft_plan_spec(
940        op,
941        operation,
942        input_dtype,
943        input_shape,
944        n.map(|n| [n]).as_ref().map(<[usize; 1]>::as_slice),
945        &[axis],
946        norm,
947    )
948}
949
950/// Validate one FFT request over one or more axes and build its descriptor.
951///
952/// This is the only place that normalizes and de-duplicates axes, checks that
953/// exactly one requested length is supplied per axis, and validates the dtype
954/// and the concrete per-axis transform shapes. The eager executor, the traced
955/// builder, and the extension execution path all reach it, so 1-D and n-D
956/// requests cannot drift apart.
957#[allow(clippy::too_many_arguments)]
958fn validated_fft_op(
959    op: &'static str,
960    operation: FftOperation,
961    dtype: Option<DType>,
962    input_rank: usize,
963    input_shape: Option<&[usize]>,
964    lengths: Option<&[usize]>,
965    length_argument: &'static str,
966    axes: &[isize],
967    norm: FftNorm,
968) -> tenferro_tensor::Result<FftOp> {
969    if input_rank == 0 {
970        return Err(tenferro_tensor::Error::invalid_argument(
971            op,
972            "rank",
973            "FFT requires rank >= 1",
974        ));
975    }
976    if axes.is_empty() {
977        return Err(tenferro_tensor::Error::invalid_argument(
978            op,
979            "axes",
980            "FFT requires at least one axis",
981        ));
982    }
983    let mut normalized = Vec::with_capacity(axes.len());
984    for &axis in axes {
985        let axis = normalize_axis(op, axis, input_rank)?;
986        if normalized.contains(&axis) {
987            return Err(tenferro_tensor::Error::invalid_argument(
988                op,
989                "axes",
990                format!("axis {axis} is repeated"),
991            ));
992        }
993        normalized.push(axis);
994    }
995    if let Some(lengths) = lengths {
996        if lengths.len() != normalized.len() {
997            return Err(tenferro_tensor::Error::invalid_argument(
998                op,
999                length_argument,
1000                format!(
1001                    "expected {} requested lengths for {} axes, got {}",
1002                    normalized.len(),
1003                    normalized.len(),
1004                    lengths.len()
1005                ),
1006            ));
1007        }
1008        if lengths.contains(&0) {
1009            return Err(tenferro_tensor::Error::invalid_argument(
1010                op,
1011                length_argument,
1012                "transform length must be positive",
1013            ));
1014        }
1015    }
1016    if let Some(dtype) = dtype {
1017        validate_operation_dtype(op, operation, dtype)?;
1018    }
1019    let count = normalized.len();
1020    if let Some(shape) = input_shape {
1021        for (index, &axis) in normalized.iter().enumerate() {
1022            let len = lengths.map(|lengths| lengths[index]);
1023            if len.is_none() && shape[axis] == 0 {
1024                return Err(tenferro_tensor::Error::invalid_argument(
1025                    op,
1026                    length_argument,
1027                    "transform length must be positive",
1028                ));
1029            }
1030            match operation.step_operation(index, count) {
1031                FftOperation::C2cForward | FftOperation::C2cInverse => {
1032                    transform_len(shape, axis, len)?;
1033                }
1034                FftOperation::R2cFull | FftOperation::R2cOnesided => {
1035                    transform_len(shape, axis, len)?;
1036                }
1037                FftOperation::C2r => {
1038                    output_shape_c2r(shape, axis, len)?;
1039                }
1040            }
1041        }
1042    }
1043    Ok(FftOp::new(
1044        operation,
1045        normalized,
1046        lengths.map(<[usize]>::to_vec),
1047        norm,
1048    ))
1049}
1050
1051#[allow(clippy::too_many_arguments)]
1052fn validated_fft_plan_spec(
1053    op: &'static str,
1054    operation: FftOperation,
1055    input_dtype: DType,
1056    input_shape: &[usize],
1057    lengths: Option<&[usize]>,
1058    axes: &[isize],
1059    norm: FftNorm,
1060) -> tenferro_tensor::Result<FftPlanSpec> {
1061    let fft_op = validated_fft_op(
1062        op,
1063        operation,
1064        Some(input_dtype),
1065        input_shape.len(),
1066        Some(input_shape),
1067        lengths,
1068        "n",
1069        axes,
1070        norm,
1071    )?;
1072    Ok(fft_op.spec(input_dtype, input_shape))
1073}
1074
1075fn concrete_fft_operation(op: &'static str, dtype: DType) -> tenferro_tensor::Result<FftOperation> {
1076    match dtype {
1077        DType::C32 | DType::C64 => Ok(FftOperation::C2cForward),
1078        DType::F32 | DType::F64 => Ok(FftOperation::R2cFull),
1079        DType::I32 | DType::I64 | DType::Bool | DType::External(_) => {
1080            Err(tensor_unsupported_dtype(op, dtype, "F32, F64, C32, or C64"))
1081        }
1082    }
1083}
1084
1085fn concrete_ifft_operation(
1086    op: &'static str,
1087    dtype: DType,
1088) -> tenferro_tensor::Result<FftOperation> {
1089    match dtype {
1090        DType::C32 | DType::C64 => Ok(FftOperation::C2cInverse),
1091        DType::F32 | DType::F64 | DType::I32 | DType::I64 | DType::Bool | DType::External(_) => {
1092            Err(tensor_unsupported_dtype(op, dtype, "C32 or C64"))
1093        }
1094    }
1095}
1096
1097fn concrete_rfft_operation(
1098    op: &'static str,
1099    dtype: DType,
1100) -> tenferro_tensor::Result<FftOperation> {
1101    match dtype {
1102        DType::F32 | DType::F64 => Ok(FftOperation::R2cOnesided),
1103        DType::C32 | DType::C64 | DType::I32 | DType::I64 | DType::Bool | DType::External(_) => {
1104            Err(tensor_unsupported_dtype(op, dtype, "F32 or F64"))
1105        }
1106    }
1107}
1108
1109fn concrete_irfft_operation(
1110    op: &'static str,
1111    dtype: DType,
1112) -> tenferro_tensor::Result<FftOperation> {
1113    match dtype {
1114        DType::C32 | DType::C64 => Ok(FftOperation::C2r),
1115        DType::F32 | DType::F64 | DType::I32 | DType::I64 | DType::Bool | DType::External(_) => {
1116            Err(tensor_unsupported_dtype(op, dtype, "C32 or C64"))
1117        }
1118    }
1119}
1120
1121fn validate_operation_dtype(
1122    op: &'static str,
1123    operation: FftOperation,
1124    dtype: DType,
1125) -> tenferro_tensor::Result<()> {
1126    let supported = match operation {
1127        FftOperation::C2cForward | FftOperation::C2cInverse | FftOperation::C2r => {
1128            matches!(dtype, DType::C32 | DType::C64)
1129        }
1130        FftOperation::R2cFull | FftOperation::R2cOnesided => {
1131            matches!(dtype, DType::F32 | DType::F64)
1132        }
1133    };
1134    if supported {
1135        Ok(())
1136    } else {
1137        Err(tensor_unsupported_dtype(
1138            op,
1139            dtype,
1140            expected_dtype_description(operation),
1141        ))
1142    }
1143}
1144
1145fn tensor_unsupported_dtype(
1146    op: &'static str,
1147    dtype: DType,
1148    expected: &'static str,
1149) -> tenferro_tensor::Error {
1150    tenferro_tensor::Error::extension(
1151        op,
1152        FFT_EXTENSION_FAMILY_ID,
1153        ErrorKind::Unsupported,
1154        FftError::UnsupportedDType {
1155            op,
1156            dtype,
1157            expected,
1158        },
1159    )
1160}
1161
1162#[cfg(feature = "autodiff")]
1163#[derive(Debug)]
1164struct FftAdRule;
1165
1166#[cfg(feature = "autodiff")]
1167impl SemanticLinearizeRule for FftAdRule {
1168    fn family_id(&self) -> &'static str {
1169        FFT_EXTENSION_FAMILY_ID
1170    }
1171
1172    fn linearize(
1173        &self,
1174        request: SemanticLinearizeRequest<'_>,
1175        builder: &mut SemanticProgramBuilder,
1176    ) -> std::result::Result<SemanticLinearizeResult, SemanticAdError> {
1177        let fft_op = semantic_fft_payload(request.op(), SemanticAdRuleKind::Linearize)?;
1178        if !fft_op.operation.is_c2c() {
1179            return Err(semantic_fft_unsupported(
1180                fft_op.operation,
1181                SemanticAdRuleKind::Linearize,
1182            ));
1183        }
1184        let tangent = match request.tangent_inputs()[0] {
1185            AdValue::Absent => AdValue::Absent,
1186            AdValue::Value(tangent) => {
1187                AdValue::Value(builder.add_extension(Arc::new(fft_op.clone()), &[tangent])?[0])
1188            }
1189        };
1190        Ok(SemanticLinearizeResult::new([tangent], []))
1191    }
1192}
1193
1194#[cfg(feature = "autodiff")]
1195impl SemanticLinearTransposeRule for FftAdRule {
1196    fn family_id(&self) -> &'static str {
1197        FFT_EXTENSION_FAMILY_ID
1198    }
1199
1200    fn residual_mask(&self) -> ResidualSpec {
1201        // The variable-length adjoint path reads primal input 0 as a tensor
1202        // (ShapeOf + PadToMatch against the original input).
1203        ResidualSpec::input(0)
1204    }
1205
1206    fn linear_transpose(
1207        &self,
1208        request: SemanticLinearTransposeRequest<'_>,
1209        builder: &mut SemanticProgramBuilder,
1210    ) -> std::result::Result<Box<[AdValue]>, SemanticAdError> {
1211        Ok([semantic_fft_adjoint(
1212            request.op(),
1213            request.cotangent_outputs()[0],
1214            request.active_inputs()[0],
1215            request.primal_input_value(0)?,
1216            request.residual_mask(),
1217            builder,
1218        )?]
1219        .into())
1220    }
1221}
1222
1223#[cfg(feature = "autodiff")]
1224impl SemanticPrimalVjpRule for FftAdRule {
1225    fn family_id(&self) -> &'static str {
1226        FFT_EXTENSION_FAMILY_ID
1227    }
1228
1229    fn residual_mask(&self) -> ResidualSpec {
1230        ResidualSpec::input(0)
1231    }
1232
1233    fn primal_vjp(
1234        &self,
1235        request: SemanticPrimalVjpRequest<'_>,
1236        builder: &mut SemanticProgramBuilder,
1237    ) -> std::result::Result<Box<[AdValue]>, SemanticAdError> {
1238        Ok([semantic_fft_adjoint(
1239            request.op(),
1240            request.cotangent_outputs()[0],
1241            request.active_inputs()[0],
1242            request.primal_input_value(0)?,
1243            request.residual_mask(),
1244            builder,
1245        )?]
1246        .into())
1247    }
1248}
1249
1250#[cfg(feature = "autodiff")]
1251#[derive(Clone, Copy)]
1252enum SemanticAdRuleKind {
1253    Linearize,
1254    Transpose,
1255}
1256
1257#[cfg(feature = "autodiff")]
1258fn semantic_fft_payload(
1259    op: &dyn ExtensionOp,
1260    role: SemanticAdRuleKind,
1261) -> std::result::Result<&FftOp, SemanticAdError> {
1262    op.as_any().downcast_ref::<FftOp>().ok_or_else(|| {
1263        semantic_fft_unsupported_family(
1264            FFT_EXTENSION_FAMILY_ID,
1265            role,
1266            "FFT semantic AD received an incompatible extension payload",
1267        )
1268    })
1269}
1270
1271#[cfg(feature = "autodiff")]
1272fn semantic_fft_adjoint(
1273    op: &dyn ExtensionOp,
1274    cotangent: AdValue,
1275    active: bool,
1276    primal_input: ProgramValue,
1277    residual_mask: ResidualSpec,
1278    builder: &mut SemanticProgramBuilder,
1279) -> std::result::Result<AdValue, SemanticAdError> {
1280    if !active {
1281        return Ok(AdValue::Absent);
1282    }
1283    let AdValue::Value(cotangent) = cotangent else {
1284        return Ok(AdValue::Absent);
1285    };
1286    let fft_op = semantic_fft_payload(op, SemanticAdRuleKind::Transpose)?;
1287    if !fft_op.operation.is_c2c() {
1288        return Err(semantic_fft_unsupported(
1289            fft_op.operation,
1290            SemanticAdRuleKind::Transpose,
1291        ));
1292    }
1293    let adjoint_op = fft_op
1294        .c2c_adjoint()
1295        .ok_or_else(|| semantic_fft_unsupported(fft_op.operation, SemanticAdRuleKind::Transpose))?;
1296    let adjoint = builder.add_extension(Arc::new(adjoint_op), &[cotangent])?[0];
1297    restore_semantic_c2c_adjoint_input_length(builder, adjoint, primal_input, residual_mask, fft_op)
1298        .map(AdValue::Value)
1299}
1300
1301#[cfg(feature = "autodiff")]
1302fn restore_semantic_c2c_adjoint_input_length(
1303    builder: &mut SemanticProgramBuilder,
1304    adjoint: ProgramValue,
1305    primal_input: ProgramValue,
1306    residual_mask: ResidualSpec,
1307    fft_op: &FftOp,
1308) -> std::result::Result<ProgramValue, SemanticAdError> {
1309    let Some(lengths) = fft_op.lengths.as_ref() else {
1310        return Ok(adjoint);
1311    };
1312    debug_assert!(
1313        residual_mask.declares_input(0),
1314        "fft transpose read primal input 0 as a tensor operand but the residual mask does not \
1315         declare it; declare it in the fft rule's residual mask"
1316    );
1317    let mut adjoint = adjoint;
1318    for (&axis, &transform_len) in fft_op.axes.iter().zip(lengths) {
1319        let input_len = builder
1320            .value_metadata(primal_input)?
1321            .shape()
1322            .get(axis)
1323            .and_then(|extent| extent.as_exact())
1324            .and_then(|dim| match dim {
1325                tenferro_ops::dim_expr::DimExpr::Const(value) => Some(*value),
1326                _ => None,
1327            });
1328        if input_len == Some(transform_len) {
1329            continue;
1330        }
1331
1332        let size = builder.add_op(CoreSemanticOp::ShapeOf { axis }, &[primal_input])?[0];
1333        let truncated =
1334            builder.add_op(CoreSemanticOp::DynamicTruncate { axis }, &[adjoint, size])?[0];
1335        adjoint = builder.add_op(
1336            CoreSemanticOp::PadToMatch { axis },
1337            &[truncated, primal_input],
1338        )?[0];
1339    }
1340    Ok(adjoint)
1341}
1342
1343#[cfg(feature = "autodiff")]
1344fn semantic_fft_unsupported(operation: FftOperation, role: SemanticAdRuleKind) -> SemanticAdError {
1345    semantic_fft_unsupported_family(
1346        fft_ad_family_id(operation),
1347        role,
1348        "FFT operation has no semantic AD rule",
1349    )
1350}
1351
1352#[cfg(feature = "autodiff")]
1353fn semantic_fft_unsupported_family(
1354    family_id: &'static str,
1355    role: SemanticAdRuleKind,
1356    message: impl Into<String>,
1357) -> SemanticAdError {
1358    SemanticAdError::Unsupported {
1359        family_id,
1360        role: match role {
1361            SemanticAdRuleKind::Linearize => {
1362                tenferro_ad::semantic_extension::SemanticAdRuleRole::Linearize
1363            }
1364            SemanticAdRuleKind::Transpose => {
1365                tenferro_ad::semantic_extension::SemanticAdRuleRole::LinearTranspose
1366            }
1367        },
1368        message: message.into(),
1369    }
1370}
1371
1372/// Return the semantic-program FFT extension AD rule set.
1373#[cfg(feature = "autodiff")]
1374///
1375/// # Errors
1376///
1377/// Returns [`SemanticExtensionRegistryError::MalformedFamilyId`] if the FFT
1378/// family identifier is invalid, or
1379/// [`SemanticExtensionRegistryError::DuplicateRule`] if a rule for the family
1380/// and role is already registered.
1381pub fn semantic_ad_rules(
1382) -> std::result::Result<SemanticExtensionRuleSet, SemanticExtensionRegistryError> {
1383    SemanticExtensionRuleSet::new()
1384        .with_linearize(Arc::new(FftAdRule))?
1385        .with_linear_transpose(Arc::new(FftAdRule))?
1386        .with_primal_vjp(Arc::new(FftAdRule))
1387}
1388
1389pub(crate) fn execute_fft_extension_reads_session(
1390    op: &FftOp,
1391    inputs: &[TensorRead<'_>],
1392    ctx: &mut ExtensionExecutionContext<'_, dyn Engine + '_>,
1393) -> tenferro_tensor::Result<Vec<Tensor>> {
1394    let (session, caches) = ctx.parts_mut();
1395    execute_fft_extension_reads_on_session(op, inputs, session, caches)
1396}
1397
1398fn execute_fft_extension_reads_for_capability<B: FftBackend + ?Sized>(
1399    op: &FftOp,
1400    inputs: &[TensorRead<'_>],
1401    session: &mut B,
1402    caches: &mut ExtensionCacheStore,
1403) -> tenferro_tensor::Result<Vec<Tensor>> {
1404    if inputs.len() != 1 {
1405        return Err(tenferro_tensor::Error::invalid_argument(
1406            "tenferro-fft",
1407            "inputs",
1408            format!("expected 1 input, got {}", inputs.len()),
1409        ));
1410    }
1411    Ok(vec![execute_fft_op(
1412        op,
1413        &inputs[0],
1414        session,
1415        FftExecutionCache::engine_owned(caches),
1416    )?])
1417}
1418
1419/// Execute one validated FFT request as successive one-axis backend calls.
1420///
1421/// This is the only axis loop for n-dimensional FFTs: the eager executor
1422/// ([`FftExecutor::fftn`]) and the traced/extension execution path both enter
1423/// here. Each iteration hands the backend a single-axis [`FftPlanSpec`], so the
1424/// backend runs its own plan for that length and dtype (`rustfft`/`realfft` on
1425/// CPU, a one-dimensional `cufftPlanMany` on CUDA) and reuses it from the shared
1426/// plan cache. Nothing here computes a transform: this function owns only the
1427/// axis order, the per-axis operation, and the intermediate shape bookkeeping.
1428fn execute_fft_op<B: FftBackend + ?Sized>(
1429    op: &FftOp,
1430    input: &TensorRead<'_>,
1431    session: &mut B,
1432    mut cache: FftExecutionCache<'_>,
1433) -> tenferro_tensor::Result<Tensor> {
1434    let mut current: Option<Tensor> = None;
1435    for index in op.execution_order() {
1436        let (dtype, shape) = match &current {
1437            Some(tensor) => (tensor.dtype(), tensor.shape().to_vec()),
1438            None => (input.dtype(), input.shape().to_vec()),
1439        };
1440        let spec = op.step_spec(index, dtype, &shape);
1441        let step_name = fft_op_name(spec.operation());
1442        let read = match &current {
1443            Some(tensor) => TensorRead::Tensor(tensor),
1444            None => input.clone(),
1445        };
1446        // The borrowed-view hook rejects an unusable placement before
1447        // canonicalization. An owned tensor keeps the backend's own placement
1448        // contract instead, where a managed CPU tensor is a legal input.
1449        if matches!(&read, TensorRead::View(_)) {
1450            session.validate_fft_read_input(step_name, &read)?;
1451        }
1452        let output = session.execute_fft_read(
1453            read,
1454            &spec,
1455            FftExecutionCache::with_owner(cache.owner(), cache.store_mut()),
1456        )?;
1457        current = Some(output);
1458    }
1459    current.ok_or_else(|| {
1460        tenferro_tensor::Error::invalid_argument(
1461            "tenferro-fft",
1462            "axes",
1463            "FFT requires at least one axis",
1464        )
1465    })
1466}
1467
1468fn execute_fft_extension_reads_on_session(
1469    op: &FftOp,
1470    inputs: &[TensorRead<'_>],
1471    session: &mut dyn Engine,
1472    caches: &mut ExtensionCacheStore,
1473) -> tenferro_tensor::Result<Vec<Tensor>> {
1474    if let Some(result) = with_cpu_engine(session, |session| {
1475        execute_fft_extension_reads_for_capability(op, inputs, session, caches)
1476    }) {
1477        return result;
1478    }
1479    #[cfg(feature = "cuda")]
1480    if let Some(result) = with_cuda_engine(session, |session| {
1481        execute_fft_extension_reads_for_capability(op, inputs, session, caches)
1482    }) {
1483        return result;
1484    }
1485    Err(tenferro_tensor::Error::unsupported(
1486        fft_op_name(op.operation),
1487        "selected backend session does not expose an FFT execution capability",
1488    ))
1489}
1490
1491define_extension_runtime! {
1492    runtime = FftRuntime,
1493    family_id = FFT_EXTENSION_FAMILY_ID,
1494    op_type = FftOp,
1495    execute_in_session = execute_fft_extension_reads_in_session,
1496    session_supported = fft_session_supported,
1497}
1498
1499/// Adapter from the scheduler/`apply_eager` borrowed-session shape to the
1500/// existing FFT session executor. Reuses the same forward kernel already shared
1501/// by the owner and eager paths; do not reimplement it here.
1502fn execute_fft_extension_reads_in_session(
1503    op: &FftOp,
1504    session: &mut dyn Engine,
1505    caches: &mut ExtensionCacheStore,
1506    inputs: &[TensorRead<'_>],
1507) -> tenferro_tensor::Result<Vec<Tensor>> {
1508    let mut ctx = ExtensionExecutionContext::new(session, caches);
1509    execute_fft_extension_reads_session(op, inputs, &mut ctx)
1510}
1511
1512fn fft_session_supported<B: Engine + 'static>(_op: &FftOp) -> bool {
1513    // The session executor routes CPU/CUDA/WebGPU through their FftBackend exec
1514    // sessions; keep scheduler-session admission consistent with the backends
1515    // that `execute_fft_extension_reads_on_session` actually handles.
1516    let type_id = std::any::TypeId::of::<B>();
1517    type_id == std::any::TypeId::of::<tenferro_cpu::CpuEngine>() || {
1518        #[cfg(feature = "cuda")]
1519        {
1520            type_id == std::any::TypeId::of::<CudaEngine>()
1521        }
1522        #[cfg(not(feature = "cuda"))]
1523        {
1524            false
1525        }
1526    }
1527}
1528
1529fn apply_unary_fftn(
1530    op_name: &'static str,
1531    input: &TracedTensor,
1532    operation: FftOperation,
1533    lengths: Option<&[usize]>,
1534    length_argument: &'static str,
1535    axes: &[isize],
1536    norm: FftNorm,
1537) -> Result<TracedTensor> {
1538    let concrete_shape = input.try_concrete_shape();
1539    let op = Arc::new(
1540        validated_fft_op(
1541            op_name,
1542            operation,
1543            Some(input.dtype()),
1544            input.rank(),
1545            concrete_shape.as_deref(),
1546            lengths,
1547            length_argument,
1548            axes,
1549            norm,
1550        )
1551        .map_err(graph_build_fft_error)?,
1552    );
1553    let mut outputs = apply(op, &[input])?;
1554    outputs
1555        .pop()
1556        .ok_or_else(|| Error::Internal("FFT extension declares exactly one output".into()))
1557}
1558
1559/// Re-raise a rejected traced or eager request as a graph-build validation error.
1560///
1561/// The request validator is shared with the concrete path and reports
1562/// `tenferro_tensor` errors; the graph-building surfaces report the same
1563/// validation failure at graph-build time.
1564fn graph_build_fft_error(error: tenferro_tensor::Error) -> Error {
1565    match error {
1566        tenferro_tensor::Error::Validation { op, source } => {
1567            Error::validation(op, ErrorPhase::GraphBuild, source)
1568        }
1569        other => Error::from(other),
1570    }
1571}
1572
1573/// Lengths of a one-axis request, so the one-dimensional entry points are the
1574/// ordinary n-dimensional builder with a single axis.
1575fn single_axis_lengths(n: Option<usize>) -> Option<[usize; 1]> {
1576    n.map(|n| [n])
1577}
1578
1579fn normalize_axis(op: &'static str, axis: isize, rank: usize) -> tenferro_tensor::Result<usize> {
1580    if rank == 0 {
1581        return Err(tenferro_tensor::Error::invalid_argument(
1582            op,
1583            "rank",
1584            "FFT requires rank >= 1",
1585        ));
1586    }
1587    // One shared normalization; the error keeps the caller's signed axis.
1588    tenferro_tensor::normalize_axis(axis, rank)
1589        .map_err(|source| tenferro_tensor::Error::validation(op, source))
1590}
1591
1592/// Build the one-axis operation descriptor used by the eager builder, which
1593/// validates the dtype itself.
1594#[cfg(feature = "autodiff")]
1595#[allow(clippy::too_many_arguments)]
1596fn prepare_runtime_fft_op(
1597    op_name: &'static str,
1598    operation: FftOperation,
1599    rank: usize,
1600    concrete_shape: Option<&[usize]>,
1601    n: Option<usize>,
1602    axis: isize,
1603    norm: FftNorm,
1604) -> Result<FftOp> {
1605    let lengths = single_axis_lengths(n);
1606    validated_fft_op(
1607        op_name,
1608        operation,
1609        None,
1610        rank,
1611        concrete_shape,
1612        lengths.as_ref().map(|lengths| lengths.as_slice()),
1613        "n",
1614        &[axis],
1615        norm,
1616    )
1617    .map_err(graph_build_fft_error)
1618}
1619
1620fn runtime_forward_fft_operation(dtype: DType) -> Result<FftOperation> {
1621    match dtype {
1622        DType::C32 | DType::C64 => Ok(FftOperation::C2cForward),
1623        DType::F32 | DType::F64 => Ok(FftOperation::R2cFull),
1624        DType::I32 | DType::I64 | DType::Bool | DType::External(_) => Err(
1625            runtime_unsupported_dtype("fft", dtype, "F32, F64, C32, or C64"),
1626        ),
1627    }
1628}
1629
1630fn require_runtime_dtype(
1631    op: &'static str,
1632    dtype: DType,
1633    supported: &[DType],
1634    expected: &'static str,
1635) -> Result<()> {
1636    if supported.contains(&dtype) {
1637        Ok(())
1638    } else {
1639        Err(runtime_unsupported_dtype(op, dtype, expected))
1640    }
1641}
1642
1643fn runtime_unsupported_dtype(op: &'static str, dtype: DType, expected: &'static str) -> Error {
1644    Error::extension(
1645        op,
1646        ErrorPhase::GraphBuild,
1647        FFT_EXTENSION_FAMILY_ID,
1648        ErrorKind::Unsupported,
1649        FftError::UnsupportedDType {
1650            op,
1651            dtype,
1652            expected,
1653        },
1654    )
1655}
1656
1657/// Symbolic companion of [`transform_len`].
1658///
1659/// It has to apply the same "transform length must be positive" rule: otherwise
1660/// compile-time preparation publishes a zero extent for an input that the
1661/// concrete path rejects.
1662fn transform_len_dim(n: Option<usize>, input_dim: &SymDim) -> tenferro_tensor::Result<SymDim> {
1663    let len = n.map(SymDim::from).unwrap_or_else(|| input_dim.clone());
1664    if len.constant_value() == Some(0) {
1665        return Err(tenferro_tensor::Error::invalid_argument(
1666            "fft",
1667            "transform length",
1668            "must be positive",
1669        ));
1670    }
1671    Ok(len)
1672}
1673
1674fn expected_dtype_description(operation: FftOperation) -> &'static str {
1675    match operation {
1676        FftOperation::C2cForward | FftOperation::C2cInverse | FftOperation::C2r => "C32 or C64",
1677        FftOperation::R2cFull | FftOperation::R2cOnesided => "F32 or F64",
1678    }
1679}
1680
1681fn fft_op_name(operation: FftOperation) -> &'static str {
1682    match operation {
1683        FftOperation::C2cForward => "fft",
1684        FftOperation::C2cInverse => "ifft",
1685        FftOperation::R2cFull | FftOperation::R2cOnesided => "rfft",
1686        FftOperation::C2r => "irfft",
1687    }
1688}
1689
1690#[cfg(feature = "autodiff")]
1691fn fft_ad_family_id(operation: FftOperation) -> &'static str {
1692    match operation {
1693        FftOperation::C2cForward | FftOperation::C2cInverse => FFT_EXTENSION_FAMILY_ID,
1694        FftOperation::R2cFull | FftOperation::R2cOnesided => "tenferro-fft.rfft.v1",
1695        FftOperation::C2r => "tenferro-fft.irfft.v1",
1696    }
1697}
1698
1699fn output_shape_c2c(
1700    shape: &[usize],
1701    axis: usize,
1702    n: Option<usize>,
1703) -> tenferro_tensor::Result<Vec<usize>> {
1704    let len = transform_len(shape, axis, n)?;
1705    let mut out_shape = shape.to_vec();
1706    out_shape[axis] = len;
1707    Ok(out_shape)
1708}
1709
1710fn output_shape_r2c(
1711    shape: &[usize],
1712    axis: usize,
1713    n: Option<usize>,
1714    onesided: bool,
1715) -> tenferro_tensor::Result<Vec<usize>> {
1716    let len = transform_len(shape, axis, n)?;
1717    let mut out_shape = shape.to_vec();
1718    out_shape[axis] = if onesided { len / 2 + 1 } else { len };
1719    Ok(out_shape)
1720}
1721
1722fn output_shape_c2r(
1723    shape: &[usize],
1724    axis: usize,
1725    n: Option<usize>,
1726) -> tenferro_tensor::Result<Vec<usize>> {
1727    validate_axis("irfft", shape, axis)?;
1728    let input_len = shape[axis];
1729    let len = match n {
1730        Some(len) => len,
1731        None => default_c2r_output_len(input_len)?,
1732    };
1733    if len == 0 {
1734        return Err(tenferro_tensor::Error::invalid_argument(
1735            "irfft",
1736            "output length",
1737            "must be positive",
1738        ));
1739    }
1740    validate_c2r_spectrum_len(input_len, len)?;
1741    let mut out_shape = shape.to_vec();
1742    out_shape[axis] = len;
1743    Ok(out_shape)
1744}
1745
1746fn output_dim_c2r(input_dim: &SymDim, n: Option<usize>) -> tenferro_tensor::Result<SymDim> {
1747    match (input_dim.constant_value(), n) {
1748        (Some(input_len), Some(output_len)) => {
1749            if output_len == 0 {
1750                return Err(tenferro_tensor::Error::invalid_argument(
1751                    "irfft",
1752                    "output length",
1753                    "must be positive",
1754                ));
1755            }
1756            validate_c2r_spectrum_len(input_len, output_len)?;
1757            Ok(SymDim::from(output_len))
1758        }
1759        (Some(input_len), None) => {
1760            let output_len = default_c2r_output_len(input_len)?;
1761            if output_len == 0 {
1762                return Err(tenferro_tensor::Error::invalid_argument(
1763                    "irfft",
1764                    "output length",
1765                    "must be positive",
1766                ));
1767            }
1768            Ok(SymDim::from(output_len))
1769        }
1770        (None, Some(output_len)) => {
1771            if output_len == 0 {
1772                return Err(tenferro_tensor::Error::invalid_argument(
1773                    "irfft",
1774                    "output length",
1775                    "must be positive",
1776                ));
1777            }
1778            Ok(SymDim::from(output_len))
1779        }
1780        (None, None) => Ok((input_dim.clone() - 1usize) * 2usize),
1781    }
1782}
1783
1784fn default_c2r_output_len(input_len: usize) -> tenferro_tensor::Result<usize> {
1785    if input_len == 0 {
1786        return Err(tenferro_tensor::Error::invalid_argument(
1787            "irfft",
1788            "input spectrum axis length",
1789            "must be positive",
1790        ));
1791    }
1792    input_len
1793        .checked_sub(1)
1794        .and_then(|len| len.checked_mul(2))
1795        .ok_or_else(|| {
1796            tenferro_tensor::Error::invalid_argument(
1797                "irfft",
1798                "default output length",
1799                "overflows usize",
1800            )
1801        })
1802}
1803
1804fn validate_c2r_spectrum_len(
1805    input_len: usize,
1806    output_len: usize,
1807) -> tenferro_tensor::Result<usize> {
1808    let expected = output_len / 2 + 1;
1809    if input_len != expected {
1810        return Err(tenferro_tensor::Error::invalid_argument(
1811            "irfft",
1812            "spectrum",
1813            format!(
1814                "one-sided spectrum axis length mismatch: expected {expected} for output length {output_len}, got {input_len}"
1815            ),
1816        ));
1817    }
1818    Ok(expected)
1819}
1820
1821fn transform_len(shape: &[usize], axis: usize, n: Option<usize>) -> tenferro_tensor::Result<usize> {
1822    validate_axis("fft", shape, axis)?;
1823    let len = n.unwrap_or(shape[axis]);
1824    if len == 0 {
1825        return Err(tenferro_tensor::Error::invalid_argument(
1826            "fft",
1827            "transform length",
1828            "must be positive",
1829        ));
1830    }
1831    Ok(len)
1832}
1833
1834fn validate_axis(op: &'static str, shape: &[usize], axis: usize) -> tenferro_tensor::Result<()> {
1835    if axis >= shape.len() {
1836        return Err(tenferro_tensor::Error::axis_out_of_bounds(
1837            op,
1838            axis,
1839            shape.len(),
1840        ));
1841    }
1842    Ok(())
1843}
1844
1845#[cfg(test)]
1846mod concrete_tests;
1847
1848#[cfg(test)]
1849mod nd_tests;
1850
1851#[cfg(test)]
1852mod lib_tests;