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#[cfg(feature = "autodiff")]
145use tenferro_tensor::{PadConfig, SliceConfig};
146
147mod api;
148mod backend;
149mod cache;
150mod cpu;
151#[cfg(feature = "cuda")]
152mod cuda;
153#[cfg(feature = "autodiff")]
154mod eager_ext;
155#[cfg(feature = "autodiff")]
156mod eager_in_place;
157pub mod prelude;
158mod spec;
159
160#[cfg(feature = "autodiff")]
161#[cfg_attr(docsrs, doc(cfg(feature = "autodiff")))]
162pub use api::EagerFftOps;
163pub use api::{FftOps, FftOptions, FftRepr, FftScalar, FftnOptions, TracedFftOps};
164pub use backend::{FftBackend, FftExecutionCache};
165pub use cache::{
166    fft_plan_cache_selector, FftPlanCache, DEFAULT_FFT_PLAN_CACHE_CAPACITY, FFT_PLAN_CACHE_NAME,
167};
168#[cfg(feature = "autodiff")]
169#[cfg_attr(docsrs, doc(cfg(feature = "autodiff")))]
170pub use eager_in_place::EagerFftInPlaceError;
171pub use spec::{FftNorm, FftOperation, FftPlanSpec};
172
173/// Extension family id used by the tenferro FFT extension.
174///
175/// # Examples
176///
177/// ```
178/// assert_eq!(
179///     tenferro_fft::FFT_EXTENSION_FAMILY_ID,
180///     "tenferro-fft.fft.v1"
181/// );
182/// ```
183pub const FFT_EXTENSION_FAMILY_ID: &str = "tenferro-fft.fft.v1";
184
185/// Reusable concrete FFT executor with an explicitly owned backend-neutral cache.
186///
187/// Use this executor for repeated concrete FFT calls that should reuse backend
188/// plans (exception E02). The [`FftOps`] methods stay
189/// one-shot and do not retain hidden process-global, thread-local, or
190/// backend-owned plan state between calls.
191#[derive(Default)]
192pub struct FftExecutor {
193    plans: FftPlanCache,
194}
195
196impl FftExecutor {
197    /// Create an executor from a caller-configured FFT execution cache.
198    pub fn new(plans: FftPlanCache) -> Self {
199        Self { plans }
200    }
201
202    /// Inspect the owned backend-neutral FFT cache.
203    pub const fn plan_cache(&self) -> &FftPlanCache {
204        &self.plans
205    }
206
207    /// Mutably inspect or configure the owned backend-neutral FFT cache.
208    pub fn plan_cache_mut(&mut self) -> &mut FftPlanCache {
209        &mut self.plans
210    }
211
212    /// Snapshot aggregate statistics for every backend cache namespace.
213    pub fn cache_stats(&self) -> CacheStats {
214        self.plans.stats()
215    }
216
217    /// Remove every retained backend plan or workspace from this executor.
218    pub fn clear_cache(&mut self) {
219        self.plans.clear();
220    }
221
222    fn one_axis_with(
223        &mut self,
224        op: &'static str,
225        operation_of: fn(&'static str, DType) -> tenferro_tensor::Result<FftOperation>,
226        input: &Tensor,
227        opts: &FftOptions,
228        exec: &mut dyn Engine,
229    ) -> tenferro_tensor::Result<Tensor> {
230        self.execute(
231            input,
232            operation_of(op, input.dtype())?,
233            op,
234            opts.n,
235            opts.axis,
236            opts.norm,
237            exec,
238        )
239    }
240
241    fn n_axes_with(
242        &mut self,
243        op: &'static str,
244        operation_of: fn(&'static str, DType) -> tenferro_tensor::Result<FftOperation>,
245        input: &Tensor,
246        opts: &FftnOptions,
247        exec: &mut dyn Engine,
248    ) -> tenferro_tensor::Result<Tensor> {
249        let axes = opts.resolved_axes(input.shape().len());
250        self.execute_nd(
251            op,
252            operation_of(op, input.dtype())?,
253            input,
254            opts.shape.as_deref(),
255            &axes,
256            opts.norm,
257            exec,
258        )
259    }
260
261    /// [`FftOps::fft`] (complex, or full spectrum of a real input) reusing this
262    /// executor's plans. Bit-identical to `FftOps::fft_with` on the same input.
263    ///
264    /// # Errors
265    ///
266    /// As [`FftOps::fft`]: `Validation` for an invalid `axis`/`n`,
267    /// `Unsupported` for an unsupported dtype or an engine without an FFT
268    /// capability, or the backend's typed error.
269    ///
270    /// # Examples
271    ///
272    /// ```
273    /// use num_complex::Complex64;
274    /// use tenferro_cpu::CpuEngine;
275    /// use tenferro_fft::{FftExecutor, FftOptions};
276    /// use tenferro_tensor::Tensor;
277    ///
278    /// let mut executor = FftExecutor::default();
279    /// let x = Tensor::from_vec_col_major(vec![4], vec![1.0_f64, 2.0, 3.0, 4.0])?;
280    /// let y = executor.fft_with(&x, &FftOptions::default(), &mut CpuEngine::serial())?;
281    /// assert_eq!(y.as_slice::<Complex64>()?[0], Complex64::new(10.0, 0.0));
282    /// assert!(executor.cache_stats().entries > 0);
283    /// # Ok::<(), tenferro_tensor::Error>(())
284    /// ```
285    pub fn fft_with(
286        &mut self,
287        input: &Tensor,
288        opts: &FftOptions,
289        exec: &mut dyn Engine,
290    ) -> tenferro_tensor::Result<Tensor> {
291        self.one_axis_with(
292            "FftExecutor::fft_with",
293            concrete_fft_operation,
294            input,
295            opts,
296            exec,
297        )
298    }
299
300    /// [`FftOps::ifft`] reusing this executor's plans.
301    ///
302    /// # Errors
303    ///
304    /// As [`FftOps::ifft`]: `Validation` for an invalid `axis`/`n`,
305    /// `Unsupported` for an unsupported dtype or an engine without an FFT
306    /// capability, or the backend's typed error.
307    ///
308    /// # Examples
309    ///
310    /// ```
311    /// use num_complex::Complex64;
312    /// use tenferro_cpu::CpuEngine;
313    /// use tenferro_fft::{FftExecutor, FftOptions};
314    /// use tenferro_tensor::Tensor;
315    ///
316    /// let mut executor = FftExecutor::default();
317    /// let x = Tensor::from_vec_col_major(
318    ///     vec![2],
319    ///     vec![Complex64::new(3.0, 0.0), Complex64::new(-1.0, 0.0)],
320    /// )?;
321    /// let y = executor.ifft_with(&x, &FftOptions::default(), &mut CpuEngine::serial())?;
322    /// assert_eq!(y.as_slice::<Complex64>()?[1], Complex64::new(2.0, 0.0));
323    /// # Ok::<(), tenferro_tensor::Error>(())
324    /// ```
325    pub fn ifft_with(
326        &mut self,
327        input: &Tensor,
328        opts: &FftOptions,
329        exec: &mut dyn Engine,
330    ) -> tenferro_tensor::Result<Tensor> {
331        self.one_axis_with(
332            "FftExecutor::ifft_with",
333            concrete_ifft_operation,
334            input,
335            opts,
336            exec,
337        )
338    }
339
340    /// [`FftOps::rfft`] reusing this executor's plans.
341    ///
342    /// # Errors
343    ///
344    /// As [`FftOps::rfft`]: `Validation` for an invalid `axis`/`n` or a
345    /// non-real input, `Unsupported` for an unsupported dtype or an engine
346    /// without an FFT capability, or the backend's typed error.
347    ///
348    /// # Examples
349    ///
350    /// ```
351    /// use tenferro_cpu::CpuEngine;
352    /// use tenferro_fft::{FftExecutor, FftOptions};
353    /// use tenferro_tensor::Tensor;
354    ///
355    /// let mut executor = FftExecutor::default();
356    /// let x = Tensor::from_vec_col_major(vec![4], vec![1.0_f64, 2.0, 3.0, 4.0])?;
357    /// let y = executor.rfft_with(&x, &FftOptions::default(), &mut CpuEngine::serial())?;
358    /// assert_eq!(y.shape(), &[3]);
359    /// # Ok::<(), tenferro_tensor::Error>(())
360    /// ```
361    pub fn rfft_with(
362        &mut self,
363        input: &Tensor,
364        opts: &FftOptions,
365        exec: &mut dyn Engine,
366    ) -> tenferro_tensor::Result<Tensor> {
367        self.one_axis_with(
368            "FftExecutor::rfft_with",
369            concrete_rfft_operation,
370            input,
371            opts,
372            exec,
373        )
374    }
375
376    /// [`FftOps::irfft`] reusing this executor's plans.
377    ///
378    /// # Errors
379    ///
380    /// As [`FftOps::irfft`]: `Validation` for an invalid `axis`/`n` or a
381    /// complex input, `Unsupported` for an unsupported dtype or an engine
382    /// without an FFT capability, or the backend's typed error.
383    ///
384    /// # Examples
385    ///
386    /// ```
387    /// use num_complex::Complex64;
388    /// use tenferro_cpu::CpuEngine;
389    /// use tenferro_fft::{FftExecutor, FftOptions};
390    /// use tenferro_tensor::Tensor;
391    ///
392    /// let mut executor = FftExecutor::default();
393    /// let x = Tensor::from_vec_col_major(
394    ///     vec![3],
395    ///     vec![Complex64::new(10.0, 0.0), Complex64::new(0.0, 0.0), Complex64::new(-2.0, 0.0)],
396    /// )?;
397    /// let y = executor.irfft_with(&x, &FftOptions::default(), &mut CpuEngine::serial())?;
398    /// assert_eq!(y.shape(), &[4]);
399    /// # Ok::<(), tenferro_tensor::Error>(())
400    /// ```
401    pub fn irfft_with(
402        &mut self,
403        input: &Tensor,
404        opts: &FftOptions,
405        exec: &mut dyn Engine,
406    ) -> tenferro_tensor::Result<Tensor> {
407        self.one_axis_with(
408            "FftExecutor::irfft_with",
409            concrete_irfft_operation,
410            input,
411            opts,
412            exec,
413        )
414    }
415
416    /// [`FftOps::fftn`] reusing this executor's plans.
417    ///
418    /// # Errors
419    ///
420    /// As [`FftOps::fftn`]: `Validation` for an invalid `axes`/`shape`/`n`,
421    /// `Unsupported` for an unsupported dtype or an engine without an N-d FFT
422    /// capability, or the backend's typed error.
423    ///
424    /// # Examples
425    ///
426    /// ```
427    /// use num_complex::Complex64;
428    /// use tenferro_cpu::CpuEngine;
429    /// use tenferro_fft::{FftExecutor, FftnOptions};
430    /// use tenferro_tensor::Tensor;
431    ///
432    /// let mut executor = FftExecutor::default();
433    /// let x = Tensor::from_vec_col_major(vec![2, 2], vec![1.0_f64, 2.0, 3.0, 4.0])?;
434    /// let y = executor.fftn_with(&x, &FftnOptions::default(), &mut CpuEngine::serial())?;
435    /// assert_eq!(y.as_slice::<Complex64>()?[0], Complex64::new(10.0, 0.0));
436    /// # Ok::<(), tenferro_tensor::Error>(())
437    /// ```
438    pub fn fftn_with(
439        &mut self,
440        input: &Tensor,
441        opts: &FftnOptions,
442        exec: &mut dyn Engine,
443    ) -> tenferro_tensor::Result<Tensor> {
444        self.n_axes_with(
445            "FftExecutor::fftn_with",
446            concrete_fft_operation,
447            input,
448            opts,
449            exec,
450        )
451    }
452
453    /// [`FftOps::ifftn`] reusing this executor's plans.
454    ///
455    /// # Errors
456    ///
457    /// As [`FftOps::ifftn`]: `Validation` for an invalid `axes`/`shape`/`n`,
458    /// `Unsupported` for an unsupported dtype or an engine without an N-d FFT
459    /// capability, or the backend's typed error.
460    ///
461    /// # Examples
462    ///
463    /// ```
464    /// use num_complex::Complex64;
465    /// use tenferro_cpu::CpuEngine;
466    /// use tenferro_fft::{FftExecutor, FftnOptions};
467    /// use tenferro_tensor::Tensor;
468    ///
469    /// let mut executor = FftExecutor::default();
470    /// let x = Tensor::from_vec_col_major(vec![1, 2], vec![Complex64::new(3.0, 0.0), Complex64::new(-1.0, 0.0)])?;
471    /// let y = executor.ifftn_with(&x, &FftnOptions::default(), &mut CpuEngine::serial())?;
472    /// assert_eq!(y.as_slice::<Complex64>()?[1], Complex64::new(2.0, 0.0));
473    /// # Ok::<(), tenferro_tensor::Error>(())
474    /// ```
475    pub fn ifftn_with(
476        &mut self,
477        input: &Tensor,
478        opts: &FftnOptions,
479        exec: &mut dyn Engine,
480    ) -> tenferro_tensor::Result<Tensor> {
481        self.n_axes_with(
482            "FftExecutor::ifftn_with",
483            concrete_ifft_operation,
484            input,
485            opts,
486            exec,
487        )
488    }
489
490    /// [`FftOps::rfftn`] reusing this executor's plans.
491    ///
492    /// # Errors
493    ///
494    /// As [`FftOps::rfftn`]: `Validation` for an invalid `axes`/`shape`/`n` or a
495    /// non-real input, `Unsupported` for an unsupported dtype or an engine
496    /// without an N-d FFT capability, or the backend's typed error.
497    ///
498    /// # Examples
499    ///
500    /// ```
501    /// use tenferro_cpu::CpuEngine;
502    /// use tenferro_fft::{FftExecutor, FftnOptions};
503    /// use tenferro_tensor::Tensor;
504    ///
505    /// let mut executor = FftExecutor::default();
506    /// let x = Tensor::from_vec_col_major(vec![2, 4], vec![1.0_f64; 8])?;
507    /// let y = executor.rfftn_with(&x, &FftnOptions::default(), &mut CpuEngine::serial())?;
508    /// assert_eq!(y.shape(), &[2, 3]);
509    /// # Ok::<(), tenferro_tensor::Error>(())
510    /// ```
511    pub fn rfftn_with(
512        &mut self,
513        input: &Tensor,
514        opts: &FftnOptions,
515        exec: &mut dyn Engine,
516    ) -> tenferro_tensor::Result<Tensor> {
517        self.n_axes_with(
518            "FftExecutor::rfftn_with",
519            concrete_rfft_operation,
520            input,
521            opts,
522            exec,
523        )
524    }
525
526    /// [`FftOps::irfftn`] reusing this executor's plans.
527    ///
528    /// # Errors
529    ///
530    /// As [`FftOps::irfftn`]: `Validation` for an invalid `axes`/`shape`/`n` or a
531    /// complex input, `Unsupported` for an unsupported dtype or an engine
532    /// without an N-d FFT capability, or the backend's typed error.
533    ///
534    /// # Examples
535    ///
536    /// ```
537    /// use num_complex::Complex64;
538    /// use tenferro_cpu::CpuEngine;
539    /// use tenferro_fft::{FftExecutor, FftnOptions};
540    /// use tenferro_tensor::Tensor;
541    ///
542    /// let mut executor = FftExecutor::default();
543    /// let mut spectrum = vec![Complex64::new(0.0, 0.0); 6];
544    /// spectrum[0] = Complex64::new(8.0, 0.0);
545    /// let x = Tensor::from_vec_col_major(vec![2, 3], spectrum)?;
546    /// let y = executor.irfftn_with(&x, &FftnOptions::default(), &mut CpuEngine::serial())?;
547    /// assert_eq!(y.as_slice::<f64>()?, &[1.0; 8]);
548    /// # Ok::<(), tenferro_tensor::Error>(())
549    /// ```
550    pub fn irfftn_with(
551        &mut self,
552        input: &Tensor,
553        opts: &FftnOptions,
554        exec: &mut dyn Engine,
555    ) -> tenferro_tensor::Result<Tensor> {
556        self.n_axes_with(
557            "FftExecutor::irfftn_with",
558            concrete_irfft_operation,
559            input,
560            opts,
561            exec,
562        )
563    }
564
565    /// Validate an n-dimensional request and run it through the shared
566    /// extension execution path, which owns the axis loop and the plan cache.
567    #[allow(clippy::too_many_arguments)]
568    fn execute_nd(
569        &mut self,
570        op_name: &'static str,
571        operation: FftOperation,
572        input: &Tensor,
573        shape: Option<&[usize]>,
574        axes: &[isize],
575        norm: FftNorm,
576        session: &mut dyn Engine,
577    ) -> tenferro_tensor::Result<Tensor> {
578        let fft_op = validated_fft_op(
579            op_name,
580            operation,
581            Some(input.dtype()),
582            input.shape().len(),
583            Some(input.shape()),
584            shape,
585            "shape",
586            axes,
587            norm,
588        )?;
589        with_fft_exec_session(session, op_name, |backend| {
590            execute_fft_op(
591                &fft_op,
592                &TensorRead::Tensor(input),
593                backend,
594                FftExecutionCache::caller_owned(&mut self.plans),
595            )
596        })
597    }
598
599    #[allow(clippy::too_many_arguments)]
600    fn execute(
601        &mut self,
602        input: &Tensor,
603        operation: FftOperation,
604        op_name: &'static str,
605        n: Option<usize>,
606        axis: isize,
607        norm: FftNorm,
608        session: &mut dyn Engine,
609    ) -> tenferro_tensor::Result<Tensor> {
610        let spec = concrete_fft_spec(
611            op_name,
612            operation,
613            input.dtype(),
614            input.shape(),
615            n,
616            axis,
617            norm,
618        )?;
619        // The executor calls the concrete backend directly (no internal
620        // session entry); the built-in dispatch only bridges the borrowed
621        // session to its FFT execution capability.
622        with_fft_exec_session(session, op_name, |backend| {
623            backend.execute_fft(
624                input,
625                &spec,
626                FftExecutionCache::caller_owned(&mut self.plans),
627            )
628        })
629    }
630}
631
632#[derive(Debug, thiserror::Error)]
633enum FftError {
634    #[error("{op} does not support dtype {dtype:?}; expected {expected}")]
635    UnsupportedDType {
636        op: &'static str,
637        dtype: DType,
638        expected: &'static str,
639    },
640}
641
642#[derive(Clone, Debug, PartialEq)]
643struct FftOp {
644    operation: FftOperation,
645    /// Validated, non-empty, duplicate-free axes. The last axis is the real
646    /// transform axis of `R2cFull`/`R2cOnesided`/`C2r`, as in NumPy `rfftn`.
647    axes: Vec<usize>,
648    /// One requested length per axis, when the caller supplied them.
649    lengths: Option<Vec<usize>>,
650    norm: FftNorm,
651}
652
653impl FftOp {
654    fn new(
655        operation: FftOperation,
656        axes: Vec<usize>,
657        lengths: Option<Vec<usize>>,
658        norm: FftNorm,
659    ) -> Self {
660        Self {
661            operation,
662            axes,
663            lengths,
664            norm,
665        }
666    }
667
668    /// Single spec for the whole request, used by concrete single-axis backends.
669    fn spec(&self, dtype: DType, shape: &[usize]) -> FftPlanSpec {
670        FftPlanSpec::new(
671            self.operation,
672            self.axes.clone(),
673            self.lengths.clone(),
674            self.norm,
675            dtype,
676            shape.to_vec(),
677        )
678    }
679
680    /// Single-axis spec for the `index`-th declared axis against `shape`.
681    fn step_spec(&self, index: usize, dtype: DType, shape: &[usize]) -> FftPlanSpec {
682        FftPlanSpec::new(
683            self.operation.step_operation(index, self.axes.len()),
684            vec![self.axes[index]],
685            self.lengths.as_ref().map(|lengths| vec![lengths[index]]),
686            self.norm,
687            dtype,
688            shape.to_vec(),
689        )
690    }
691
692    /// Axis application order for the successive one-dimensional transforms.
693    ///
694    /// Complex transforms commute, so they keep the declared order. A real
695    /// forward transform must consume the real input first, and a complex-to-real
696    /// inverse must produce real output last; both name their real axis last, so
697    /// only the forward case needs the rotation.
698    fn execution_order(&self) -> Vec<usize> {
699        let mut order: Vec<usize> = (0..self.axes.len()).collect();
700        if matches!(
701            self.operation,
702            FftOperation::R2cFull | FftOperation::R2cOnesided
703        ) {
704            order.rotate_right(1);
705        }
706        order
707    }
708
709    #[cfg(feature = "autodiff")]
710    fn c2c_adjoint(&self) -> Option<Self> {
711        let operation = match self.operation {
712            FftOperation::C2cForward => FftOperation::C2cInverse,
713            FftOperation::C2cInverse => FftOperation::C2cForward,
714            FftOperation::R2cFull | FftOperation::R2cOnesided | FftOperation::C2r => return None,
715        };
716        Some(Self {
717            operation,
718            axes: self.axes.clone(),
719            lengths: self.lengths.clone(),
720            norm: self.norm.c2c_adjoint(),
721        })
722    }
723}
724
725impl ExtensionOp for FftOp {
726    fn family_id(&self) -> &'static str {
727        FFT_EXTENSION_FAMILY_ID
728    }
729
730    fn payload_hash(&self, hasher: &mut dyn Hasher) {
731        let operation = match self.operation {
732            FftOperation::C2cForward => 0,
733            FftOperation::C2cInverse => 1,
734            FftOperation::R2cOnesided => 2,
735            FftOperation::R2cFull => 3,
736            FftOperation::C2r => 4,
737        };
738        hasher.write_u8(operation);
739        hasher.write_usize(self.axes.len());
740        for axis in &self.axes {
741            hasher.write_usize(*axis);
742        }
743        match &self.lengths {
744            Some(lengths) => {
745                hasher.write_u8(1);
746                for len in lengths {
747                    hasher.write_usize(*len);
748                }
749            }
750            None => hasher.write_u8(0),
751        }
752        let norm = match self.norm {
753            FftNorm::Backward => 0,
754            FftNorm::Forward => 1,
755            FftNorm::Ortho => 2,
756        };
757        hasher.write_u8(norm);
758    }
759
760    fn payload_eq(&self, other: &dyn ExtensionOp) -> bool {
761        other
762            .as_any()
763            .downcast_ref::<FftOp>()
764            .is_some_and(|that| self == that)
765    }
766
767    fn clone_arc(&self) -> Arc<dyn ExtensionOp> {
768        Arc::new(self.clone())
769    }
770
771    fn as_any(&self) -> &dyn Any {
772        self
773    }
774
775    fn input_count(&self) -> usize {
776        1
777    }
778
779    fn output_count(&self) -> usize {
780        1
781    }
782
783    fn semantic_effects(&self) -> tenferro_ops::ext_op::ExtensionEffectDeclaration<'_> {
784        tenferro_ops::ext_op::ExtensionEffectDeclaration::Declared(&[])
785    }
786
787    fn semantic_aliases(&self) -> tenferro_ops::ext_op::ExtensionAliasDeclaration<'_> {
788        tenferro_ops::ext_op::ExtensionAliasDeclaration::AllFresh
789    }
790
791    fn infer_output_meta(
792        &self,
793        ctx: &mut tenferro_ops::ExtensionShapeContext<'_>,
794    ) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
795        let input_dtype = ctx.input_dtype(0)?;
796        let input_shape = ctx.input_shape(0)?;
797        let output_dtype = match self.operation {
798            FftOperation::C2cForward | FftOperation::C2cInverse => {
799                if !matches!(input_dtype, DType::C32 | DType::C64) {
800                    return Err(tensor_unsupported_dtype(
801                        "tenferro-fft",
802                        input_dtype,
803                        "C32 or C64",
804                    ));
805                }
806                input_dtype
807            }
808            FftOperation::R2cFull | FftOperation::R2cOnesided => match input_dtype {
809                DType::F32 => DType::C32,
810                DType::F64 => DType::C64,
811                _ => {
812                    return Err(tensor_unsupported_dtype(
813                        "tenferro-fft",
814                        input_dtype,
815                        "F32 or F64",
816                    ));
817                }
818            },
819            FftOperation::C2r => match input_dtype {
820                DType::C32 => DType::F32,
821                DType::C64 => DType::F64,
822                _ => {
823                    return Err(tensor_unsupported_dtype(
824                        "tenferro-fft",
825                        input_dtype,
826                        "C32 or C64",
827                    ));
828                }
829            },
830        };
831
832        let count = self.axes.len();
833        let mut out_shape = input_shape.to_vec();
834        for (index, &axis) in self.axes.iter().enumerate() {
835            if axis >= input_shape.len() {
836                return Err(tenferro_tensor::Error::axis_out_of_bounds(
837                    "tenferro-fft",
838                    axis,
839                    input_shape.len(),
840                ));
841            }
842            let len = self.lengths.as_ref().map(|lengths| lengths[index]);
843            out_shape[axis] = match self.operation.step_operation(index, count) {
844                FftOperation::C2cForward | FftOperation::C2cInverse => {
845                    transform_len_dim(len, &input_shape[axis])?
846                }
847                FftOperation::R2cFull | FftOperation::R2cOnesided => {
848                    let len = transform_len_dim(len, &input_shape[axis])?;
849                    if self.operation.is_onesided() {
850                        len / 2usize + 1usize
851                    } else {
852                        len
853                    }
854                }
855                FftOperation::C2r => output_dim_c2r(&input_shape[axis], len)?,
856            };
857        }
858
859        Ok(vec![(output_dtype, out_shape)])
860    }
861}
862
863/// Run a concrete FFT body against the built-in FFT execution sessions
864/// carried by `session` (CPU/CUDA/WebGPU), returning a typed capability error
865/// when the session does not expose an FFT execution capability.
866///
867/// This is the built-in dispatch shared by the concrete FFT surface; callers
868/// never downcast themselves (issue #1680 Phase 3). Third-party
869/// [`FftBackend`] implementations remain supported through the SPI trait, but
870/// the concrete op path is built-in-session only.
871fn with_fft_exec_session<X>(
872    session: &mut dyn Engine,
873    op: &'static str,
874    f: impl FnOnce(&mut dyn FftBackend) -> tenferro_tensor::Result<X>,
875) -> tenferro_tensor::Result<X> {
876    // The capability branches are mutually exclusive, so `f` runs exactly
877    // once. Probe the marker first, then re-extract the same exec session and
878    // run the concrete body on it (FnOnce cannot be captured by several
879    // branch closures).
880    if with_cpu_engine(session, |_| ()).is_some() {
881        return with_cpu_engine(session, |exec| f(exec as &mut dyn FftBackend))
882            .expect("marker probe matched a CPU execution session");
883    }
884    #[cfg(feature = "cuda")]
885    if with_cuda_engine(session, |_| ()).is_some() {
886        return with_cuda_engine(session, |exec| f(exec as &mut dyn FftBackend))
887            .expect("marker probe matched a CUDA execution session");
888    }
889    Err(tenferro_tensor::Error::unsupported(
890        op,
891        "selected backend session does not expose an FFT execution capability",
892    ))
893}
894
895fn execute_concrete_fft_op(
896    input: &Tensor,
897    spec: &FftPlanSpec,
898    backend: &mut dyn FftBackend,
899) -> tenferro_tensor::Result<Tensor> {
900    let mut plans = FftPlanCache::with_capacity(NonZeroUsize::MIN);
901    backend.execute_fft(input, spec, FftExecutionCache::caller_owned(&mut plans))
902}
903
904#[allow(clippy::too_many_arguments)]
905fn execute_concrete_fft_read_op(
906    input: &TensorRead<'_>,
907    operation: FftOperation,
908    op_name: &'static str,
909    n: Option<usize>,
910    axis: isize,
911    norm: FftNorm,
912    backend: &mut dyn FftBackend,
913) -> tenferro_tensor::Result<Tensor> {
914    let spec = concrete_fft_spec(
915        op_name,
916        operation,
917        input.dtype(),
918        input.shape(),
919        n,
920        axis,
921        norm,
922    )?;
923    let mut plans = FftPlanCache::with_capacity(NonZeroUsize::MIN);
924    backend.execute_fft_read(
925        input.clone(),
926        &spec,
927        FftExecutionCache::caller_owned(&mut plans),
928    )
929}
930
931#[allow(clippy::too_many_arguments)]
932fn concrete_fft_spec(
933    op: &'static str,
934    operation: FftOperation,
935    input_dtype: DType,
936    input_shape: &[usize],
937    n: Option<usize>,
938    axis: isize,
939    norm: FftNorm,
940) -> tenferro_tensor::Result<FftPlanSpec> {
941    validated_fft_plan_spec(
942        op,
943        operation,
944        input_dtype,
945        input_shape,
946        n.map(|n| [n]).as_ref().map(<[usize; 1]>::as_slice),
947        &[axis],
948        norm,
949    )
950}
951
952/// Validate one FFT request over one or more axes and build its descriptor.
953///
954/// This is the only place that normalizes and de-duplicates axes, checks that
955/// exactly one requested length is supplied per axis, and validates the dtype
956/// and the concrete per-axis transform shapes. The eager executor, the traced
957/// builder, and the extension execution path all reach it, so 1-D and n-D
958/// requests cannot drift apart.
959#[allow(clippy::too_many_arguments)]
960fn validated_fft_op(
961    op: &'static str,
962    operation: FftOperation,
963    dtype: Option<DType>,
964    input_rank: usize,
965    input_shape: Option<&[usize]>,
966    lengths: Option<&[usize]>,
967    length_argument: &'static str,
968    axes: &[isize],
969    norm: FftNorm,
970) -> tenferro_tensor::Result<FftOp> {
971    if input_rank == 0 {
972        return Err(tenferro_tensor::Error::invalid_argument(
973            op,
974            "rank",
975            "FFT requires rank >= 1",
976        ));
977    }
978    if axes.is_empty() {
979        return Err(tenferro_tensor::Error::invalid_argument(
980            op,
981            "axes",
982            "FFT requires at least one axis",
983        ));
984    }
985    let mut normalized = Vec::with_capacity(axes.len());
986    for &axis in axes {
987        let axis = normalize_axis(op, axis, input_rank)?;
988        if normalized.contains(&axis) {
989            return Err(tenferro_tensor::Error::invalid_argument(
990                op,
991                "axes",
992                format!("axis {axis} is repeated"),
993            ));
994        }
995        normalized.push(axis);
996    }
997    if let Some(lengths) = lengths {
998        if lengths.len() != normalized.len() {
999            return Err(tenferro_tensor::Error::invalid_argument(
1000                op,
1001                length_argument,
1002                format!(
1003                    "expected {} requested lengths for {} axes, got {}",
1004                    normalized.len(),
1005                    normalized.len(),
1006                    lengths.len()
1007                ),
1008            ));
1009        }
1010        if lengths.contains(&0) {
1011            return Err(tenferro_tensor::Error::invalid_argument(
1012                op,
1013                length_argument,
1014                "transform length must be positive",
1015            ));
1016        }
1017    }
1018    if let Some(dtype) = dtype {
1019        validate_operation_dtype(op, operation, dtype)?;
1020    }
1021    let count = normalized.len();
1022    if let Some(shape) = input_shape {
1023        for (index, &axis) in normalized.iter().enumerate() {
1024            let len = lengths.map(|lengths| lengths[index]);
1025            if len.is_none() && shape[axis] == 0 {
1026                return Err(tenferro_tensor::Error::invalid_argument(
1027                    op,
1028                    length_argument,
1029                    "transform length must be positive",
1030                ));
1031            }
1032            match operation.step_operation(index, count) {
1033                FftOperation::C2cForward | FftOperation::C2cInverse => {
1034                    transform_len(shape, axis, len)?;
1035                }
1036                FftOperation::R2cFull | FftOperation::R2cOnesided => {
1037                    transform_len(shape, axis, len)?;
1038                }
1039                FftOperation::C2r => {
1040                    output_shape_c2r(shape, axis, len)?;
1041                }
1042            }
1043        }
1044    }
1045    Ok(FftOp::new(
1046        operation,
1047        normalized,
1048        lengths.map(<[usize]>::to_vec),
1049        norm,
1050    ))
1051}
1052
1053#[allow(clippy::too_many_arguments)]
1054fn validated_fft_plan_spec(
1055    op: &'static str,
1056    operation: FftOperation,
1057    input_dtype: DType,
1058    input_shape: &[usize],
1059    lengths: Option<&[usize]>,
1060    axes: &[isize],
1061    norm: FftNorm,
1062) -> tenferro_tensor::Result<FftPlanSpec> {
1063    let fft_op = validated_fft_op(
1064        op,
1065        operation,
1066        Some(input_dtype),
1067        input_shape.len(),
1068        Some(input_shape),
1069        lengths,
1070        "n",
1071        axes,
1072        norm,
1073    )?;
1074    Ok(fft_op.spec(input_dtype, input_shape))
1075}
1076
1077fn concrete_fft_operation(op: &'static str, dtype: DType) -> tenferro_tensor::Result<FftOperation> {
1078    match dtype {
1079        DType::C32 | DType::C64 => Ok(FftOperation::C2cForward),
1080        DType::F32 | DType::F64 => Ok(FftOperation::R2cFull),
1081        DType::I32 | DType::I64 | DType::Bool | DType::External(_) => {
1082            Err(tensor_unsupported_dtype(op, dtype, "F32, F64, C32, or C64"))
1083        }
1084    }
1085}
1086
1087fn concrete_ifft_operation(
1088    op: &'static str,
1089    dtype: DType,
1090) -> tenferro_tensor::Result<FftOperation> {
1091    match dtype {
1092        DType::C32 | DType::C64 => Ok(FftOperation::C2cInverse),
1093        DType::F32 | DType::F64 | DType::I32 | DType::I64 | DType::Bool | DType::External(_) => {
1094            Err(tensor_unsupported_dtype(op, dtype, "C32 or C64"))
1095        }
1096    }
1097}
1098
1099fn concrete_rfft_operation(
1100    op: &'static str,
1101    dtype: DType,
1102) -> tenferro_tensor::Result<FftOperation> {
1103    match dtype {
1104        DType::F32 | DType::F64 => Ok(FftOperation::R2cOnesided),
1105        DType::C32 | DType::C64 | DType::I32 | DType::I64 | DType::Bool | DType::External(_) => {
1106            Err(tensor_unsupported_dtype(op, dtype, "F32 or F64"))
1107        }
1108    }
1109}
1110
1111fn concrete_irfft_operation(
1112    op: &'static str,
1113    dtype: DType,
1114) -> tenferro_tensor::Result<FftOperation> {
1115    match dtype {
1116        DType::C32 | DType::C64 => Ok(FftOperation::C2r),
1117        DType::F32 | DType::F64 | DType::I32 | DType::I64 | DType::Bool | DType::External(_) => {
1118            Err(tensor_unsupported_dtype(op, dtype, "C32 or C64"))
1119        }
1120    }
1121}
1122
1123fn validate_operation_dtype(
1124    op: &'static str,
1125    operation: FftOperation,
1126    dtype: DType,
1127) -> tenferro_tensor::Result<()> {
1128    let supported = match operation {
1129        FftOperation::C2cForward | FftOperation::C2cInverse | FftOperation::C2r => {
1130            matches!(dtype, DType::C32 | DType::C64)
1131        }
1132        FftOperation::R2cFull | FftOperation::R2cOnesided => {
1133            matches!(dtype, DType::F32 | DType::F64)
1134        }
1135    };
1136    if supported {
1137        Ok(())
1138    } else {
1139        Err(tensor_unsupported_dtype(
1140            op,
1141            dtype,
1142            expected_dtype_description(operation),
1143        ))
1144    }
1145}
1146
1147fn tensor_unsupported_dtype(
1148    op: &'static str,
1149    dtype: DType,
1150    expected: &'static str,
1151) -> tenferro_tensor::Error {
1152    tenferro_tensor::Error::extension(
1153        op,
1154        FFT_EXTENSION_FAMILY_ID,
1155        ErrorKind::Unsupported,
1156        FftError::UnsupportedDType {
1157            op,
1158            dtype,
1159            expected,
1160        },
1161    )
1162}
1163
1164#[cfg(feature = "autodiff")]
1165#[derive(Debug)]
1166struct FftAdRule;
1167
1168#[cfg(feature = "autodiff")]
1169impl SemanticLinearizeRule for FftAdRule {
1170    fn family_id(&self) -> &'static str {
1171        FFT_EXTENSION_FAMILY_ID
1172    }
1173
1174    fn linearize(
1175        &self,
1176        request: SemanticLinearizeRequest<'_>,
1177        builder: &mut SemanticProgramBuilder,
1178    ) -> std::result::Result<SemanticLinearizeResult, SemanticAdError> {
1179        // Every FFT operation is real-linear, so its tangent is the same transform.
1180        let fft_op = semantic_fft_payload(request.op(), SemanticAdRuleKind::Linearize)?;
1181        let tangent = match request.tangent_inputs()[0] {
1182            AdValue::Absent => AdValue::Absent,
1183            AdValue::Value(tangent) => {
1184                AdValue::Value(builder.add_extension(Arc::new(fft_op.clone()), &[tangent])?[0])
1185            }
1186        };
1187        Ok(SemanticLinearizeResult::new([tangent], []))
1188    }
1189}
1190
1191#[cfg(feature = "autodiff")]
1192impl SemanticLinearTransposeRule for FftAdRule {
1193    fn family_id(&self) -> &'static str {
1194        FFT_EXTENSION_FAMILY_ID
1195    }
1196
1197    fn residual_mask(&self) -> ResidualSpec {
1198        // The variable-length adjoint path reads primal input 0 as a tensor
1199        // (ShapeOf + PadToMatch against the original input).
1200        ResidualSpec::input(0)
1201    }
1202
1203    fn linear_transpose(
1204        &self,
1205        request: SemanticLinearTransposeRequest<'_>,
1206        builder: &mut SemanticProgramBuilder,
1207    ) -> std::result::Result<Box<[AdValue]>, SemanticAdError> {
1208        Ok([semantic_fft_adjoint(
1209            request.op(),
1210            request.cotangent_outputs()[0],
1211            request.active_inputs()[0],
1212            request.primal_input_value(0)?,
1213            request.residual_mask(),
1214            builder,
1215        )?]
1216        .into())
1217    }
1218}
1219
1220#[cfg(feature = "autodiff")]
1221impl SemanticPrimalVjpRule for FftAdRule {
1222    fn family_id(&self) -> &'static str {
1223        FFT_EXTENSION_FAMILY_ID
1224    }
1225
1226    fn residual_mask(&self) -> ResidualSpec {
1227        ResidualSpec::input(0)
1228    }
1229
1230    fn primal_vjp(
1231        &self,
1232        request: SemanticPrimalVjpRequest<'_>,
1233        builder: &mut SemanticProgramBuilder,
1234    ) -> std::result::Result<Box<[AdValue]>, SemanticAdError> {
1235        Ok([semantic_fft_adjoint(
1236            request.op(),
1237            request.cotangent_outputs()[0],
1238            request.active_inputs()[0],
1239            request.primal_input_value(0)?,
1240            request.residual_mask(),
1241            builder,
1242        )?]
1243        .into())
1244    }
1245}
1246
1247#[cfg(feature = "autodiff")]
1248#[derive(Clone, Copy)]
1249enum SemanticAdRuleKind {
1250    Linearize,
1251    Transpose,
1252}
1253
1254#[cfg(feature = "autodiff")]
1255fn semantic_fft_payload(
1256    op: &dyn ExtensionOp,
1257    role: SemanticAdRuleKind,
1258) -> std::result::Result<&FftOp, SemanticAdError> {
1259    op.as_any().downcast_ref::<FftOp>().ok_or_else(|| {
1260        semantic_fft_unsupported_family(
1261            FFT_EXTENSION_FAMILY_ID,
1262            role,
1263            "FFT semantic AD received an incompatible extension payload",
1264        )
1265    })
1266}
1267
1268#[cfg(feature = "autodiff")]
1269fn semantic_fft_adjoint(
1270    op: &dyn ExtensionOp,
1271    cotangent: AdValue,
1272    active: bool,
1273    primal_input: ProgramValue,
1274    residual_mask: ResidualSpec,
1275    builder: &mut SemanticProgramBuilder,
1276) -> std::result::Result<AdValue, SemanticAdError> {
1277    if !active {
1278        return Ok(AdValue::Absent);
1279    }
1280    let AdValue::Value(cotangent) = cotangent else {
1281        return Ok(AdValue::Absent);
1282    };
1283    let fft_op = semantic_fft_payload(op, SemanticAdRuleKind::Transpose)?;
1284    let adjoint = match fft_op.operation {
1285        FftOperation::C2cForward | FftOperation::C2cInverse => {
1286            let adjoint_op = fft_op.c2c_adjoint().ok_or_else(|| {
1287                semantic_fft_unsupported(fft_op.operation, SemanticAdRuleKind::Transpose)
1288            })?;
1289            builder.add_extension(Arc::new(adjoint_op), &[cotangent])?[0]
1290        }
1291        FftOperation::R2cFull | FftOperation::R2cOnesided => {
1292            semantic_r2c_adjoint(builder, fft_op, cotangent, primal_input)?
1293        }
1294        FftOperation::C2r => {
1295            // The cotangent already has every transform length as its extent.
1296            let forward = FftOp::new(
1297                FftOperation::R2cOnesided,
1298                fft_op.axes.clone(),
1299                None,
1300                fft_op.norm.c2c_adjoint(),
1301            );
1302            let spectrum = builder.add_extension(Arc::new(forward), &[cotangent])?[0];
1303            semantic_double_mirrored_bins(builder, fft_op, spectrum, primal_input)?
1304        }
1305    };
1306    restore_semantic_adjoint_input_length(builder, adjoint, primal_input, residual_mask, fft_op)
1307        .map(AdValue::Value)
1308}
1309
1310/// Adjoint of a real-to-complex transform under `<a, b> = Re(conj(a) * b)`.
1311///
1312/// The forward map is `y = s * F x` restricted to the returned bins, so the
1313/// adjoint is `x_bar = Re(s * F^H y_bar)` with `y_bar` read as a full spectrum.
1314/// A one-sided `y_bar` is zero-padded on the real axis to the full transform
1315/// length: the negative-frequency bins were not returned, so they carry no
1316/// cotangent.
1317#[cfg(feature = "autodiff")]
1318fn semantic_r2c_adjoint(
1319    builder: &mut SemanticProgramBuilder,
1320    fft_op: &FftOp,
1321    cotangent: ProgramValue,
1322    primal_input: ProgramValue,
1323) -> std::result::Result<ProgramValue, SemanticAdError> {
1324    let mut spectrum = cotangent;
1325    if fft_op.operation.is_onesided() {
1326        let (index, real_axis) = semantic_fft_real_axis(fft_op);
1327        let transform_len = match &fft_op.lengths {
1328            Some(lengths) => lengths[index],
1329            None => semantic_fft_concrete_extent(builder, primal_input, real_axis, fft_op)?,
1330        };
1331        let missing_bins = transform_len - (transform_len / 2 + 1);
1332        if missing_bins > 0 {
1333            let rank = builder.value_metadata(cotangent)?.shape().len();
1334            let mut edge_padding_high = vec![0; rank];
1335            edge_padding_high[real_axis] = i64::try_from(missing_bins).map_err(|_| {
1336                semantic_fft_unsupported_family(
1337                    fft_ad_family_id(fft_op.operation),
1338                    SemanticAdRuleKind::Transpose,
1339                    "rfft transform length does not fit in i64",
1340                )
1341            })?;
1342            spectrum = builder.add_op(
1343                CoreSemanticOp::Pad(PadConfig {
1344                    edge_padding_low: vec![0; rank],
1345                    edge_padding_high,
1346                    interior_padding: vec![0; rank],
1347                }),
1348                &[spectrum],
1349            )?[0];
1350        }
1351    }
1352    // The cotangent already has every transform length as its extent.
1353    let inverse = FftOp::new(
1354        FftOperation::C2cInverse,
1355        fft_op.axes.clone(),
1356        None,
1357        fft_op.norm.c2c_adjoint(),
1358    );
1359    let complex = builder.add_extension(Arc::new(inverse), &[spectrum])?[0];
1360    let from = builder.value_metadata(complex)?.dtype();
1361    let to = builder.value_metadata(primal_input)?.dtype();
1362    Ok(builder.add_op(CoreSemanticOp::Convert { from, to }, &[complex])?[0])
1363}
1364
1365/// Finish the adjoint of a complex-to-real transform under
1366/// `<a, b> = Re(conj(a) * b)`, given `spectrum = s * rfft(x_bar)`.
1367///
1368/// The output is `x = s * Re(sum_k c_k z_k e^{+2 pi i j k / L})` over the
1369/// one-sided bins, with `c_k = 2` for every bin that stands for itself and its
1370/// conjugate mirror and `c_k = 1` for DC and, at even `L`, Nyquist (whose
1371/// imaginary parts the transform ignores). The adjoint is therefore
1372/// `z_bar = c * spectrum`; the one-sided transform of a real signal is already
1373/// real at DC and Nyquist.
1374#[cfg(feature = "autodiff")]
1375fn semantic_double_mirrored_bins(
1376    builder: &mut SemanticProgramBuilder,
1377    fft_op: &FftOp,
1378    spectrum: ProgramValue,
1379    primal_input: ProgramValue,
1380) -> std::result::Result<ProgramValue, SemanticAdError> {
1381    let (index, real_axis) = semantic_fft_real_axis(fft_op);
1382    // `spectrum` has the primal input shape except on the resized complex
1383    // axes; read it from the primal input, whose extents the program binds.
1384    let rank = builder.value_metadata(primal_input)?.shape().len();
1385    let mut limits = Vec::with_capacity(rank);
1386    for axis in 0..rank {
1387        limits.push(semantic_fft_concrete_extent(
1388            builder,
1389            primal_input,
1390            axis,
1391            fft_op,
1392        )?);
1393    }
1394    if let Some(lengths) = &fft_op.lengths {
1395        for (&axis, &len) in fft_op.axes.iter().zip(lengths).take(index) {
1396            limits[axis] = len;
1397        }
1398    }
1399    let bins = limits[real_axis];
1400    let transform_len = match &fft_op.lengths {
1401        Some(lengths) => lengths[index],
1402        // The default irfft length `2 * (bins - 1)`.
1403        None => 2 * (bins - 1),
1404    };
1405    let mirrored_bins = transform_len - bins;
1406    if mirrored_bins == 0 {
1407        return Ok(spectrum);
1408    }
1409    // Add the bins 1..=mirrored_bins once more instead of building a weight tensor.
1410    let mut starts = vec![0; rank];
1411    starts[real_axis] = 1;
1412    limits[real_axis] = 1 + mirrored_bins;
1413    let mirrored = builder.add_op(
1414        CoreSemanticOp::Slice(SliceConfig {
1415            starts,
1416            limits,
1417            strides: vec![1; rank],
1418        }),
1419        &[spectrum],
1420    )?[0];
1421    let mut edge_padding_low = vec![0; rank];
1422    edge_padding_low[real_axis] = 1;
1423    let mut edge_padding_high = vec![0; rank];
1424    // One trailing Nyquist bin at even length, none at odd length.
1425    edge_padding_high[real_axis] = i64::from(transform_len.is_multiple_of(2));
1426    let mirrored = builder.add_op(
1427        CoreSemanticOp::Pad(PadConfig {
1428            edge_padding_low,
1429            edge_padding_high,
1430            interior_padding: vec![0; rank],
1431        }),
1432        &[mirrored],
1433    )?[0];
1434    Ok(builder.add_op(CoreSemanticOp::Add, &[spectrum, mirrored])?[0])
1435}
1436
1437/// Index and axis of the real transform: the last declared axis, as in `rfftn`.
1438#[cfg(feature = "autodiff")]
1439fn semantic_fft_real_axis(fft_op: &FftOp) -> (usize, usize) {
1440    let index = fft_op.axes.len() - 1;
1441    (index, fft_op.axes[index])
1442}
1443
1444/// Literal extent of `value` on `axis`, which the real-transform adjoints need
1445/// because the half-spectrum bin weights depend on the parity of the length.
1446#[cfg(feature = "autodiff")]
1447fn semantic_fft_concrete_extent(
1448    builder: &SemanticProgramBuilder,
1449    value: ProgramValue,
1450    axis: usize,
1451    fft_op: &FftOp,
1452) -> std::result::Result<usize, SemanticAdError> {
1453    // A bound extent can still be an unfolded expression such as `8 / 2 + 1`
1454    // (the extent of an rfft output), so evaluate any input-free expression.
1455    match builder.resolved_extent(value, axis)? {
1456        tenferro_ops::ShapeExtent::Exact(extent) if extent.max_input_idx().is_none() => {
1457            extent.eval(&[]).map_err(|error| {
1458                semantic_fft_unsupported_family(
1459                    fft_ad_family_id(fft_op.operation),
1460                    SemanticAdRuleKind::Transpose,
1461                    format!("extent on axis {axis} does not evaluate: {error}"),
1462                )
1463            })
1464        }
1465        _ => Err(semantic_fft_unsupported_family(
1466            fft_ad_family_id(fft_op.operation),
1467            SemanticAdRuleKind::Transpose,
1468            format!("real FFT adjoint requires a concrete extent on axis {axis}"),
1469        )),
1470    }
1471}
1472
1473#[cfg(feature = "autodiff")]
1474fn restore_semantic_adjoint_input_length(
1475    builder: &mut SemanticProgramBuilder,
1476    adjoint: ProgramValue,
1477    primal_input: ProgramValue,
1478    residual_mask: ResidualSpec,
1479    fft_op: &FftOp,
1480) -> std::result::Result<ProgramValue, SemanticAdError> {
1481    let Some(lengths) = fft_op.lengths.as_ref() else {
1482        return Ok(adjoint);
1483    };
1484    debug_assert!(
1485        residual_mask.declares_input(0),
1486        "fft transpose read primal input 0 as a tensor operand but the residual mask does not \
1487         declare it; declare it in the fft rule's residual mask"
1488    );
1489    let mut adjoint = adjoint;
1490    // The adjoint's literal shape, advanced by every restore step: a slice names a
1491    // literal limit on every axis, and a pad step changes what the next step sees.
1492    let mut adjoint_extents = concrete_extents(builder, adjoint)?;
1493    for (index, (&axis, &transform_len)) in fft_op.axes.iter().zip(lengths).enumerate() {
1494        // The one-sided spectrum of an irfft already has its input extent.
1495        if fft_op.operation.step_operation(index, lengths.len()) == FftOperation::C2r {
1496            continue;
1497        }
1498        // A bound extent can still be an unfolded expression such as `8 / 2 + 1`,
1499        // so resolve it like the real-transform adjoints do.
1500        let input_len = match builder.resolved_extent(primal_input, axis)? {
1501            tenferro_ops::ShapeExtent::Exact(tenferro_ops::dim_expr::DimExpr::Const(value)) => {
1502                Some(value)
1503            }
1504            _ => None,
1505        };
1506        if input_len == Some(transform_len) {
1507            continue;
1508        }
1509
1510        // A zero-padded transform leaves the adjoint longer than the input; one
1511        // static slice publishes the input extent, where the dynamic pair below
1512        // publishes `max(n, extent)` (#2648).
1513        if let Some(input_len) = input_len {
1514            if transform_len > input_len {
1515                if let Some(limits) = adjoint_extents.as_mut() {
1516                    limits[axis] = input_len;
1517                    let rank = limits.len();
1518                    adjoint = builder.add_op(
1519                        CoreSemanticOp::Slice(SliceConfig {
1520                            starts: vec![0; rank],
1521                            limits: limits.clone(),
1522                            strides: vec![1; rank],
1523                        }),
1524                        &[adjoint],
1525                    )?[0];
1526                    continue;
1527                }
1528            }
1529        }
1530
1531        let size = builder.add_op(CoreSemanticOp::ShapeOf { axis }, &[primal_input])?[0];
1532        let truncated =
1533            builder.add_op(CoreSemanticOp::DynamicTruncate { axis }, &[adjoint, size])?[0];
1534        adjoint = builder.add_op(
1535            CoreSemanticOp::PadToMatch { axis },
1536            &[truncated, primal_input],
1537        )?[0];
1538        // The dynamic pair restores the runtime extent, but publishes a bound; keep
1539        // tracking the literal shape only while the axis length is known.
1540        match input_len {
1541            Some(input_len) => {
1542                if let Some(limits) = adjoint_extents.as_mut() {
1543                    limits[axis] = input_len;
1544                }
1545            }
1546            None => adjoint_extents = None,
1547        }
1548    }
1549    Ok(adjoint)
1550}
1551
1552/// Literal extents of `value`, or `None` when any of them is not a constant.
1553///
1554/// A `SliceConfig` names a literal limit for every axis, so a slice-based restore
1555/// needs the whole shape, not only the resized axis.
1556#[cfg(feature = "autodiff")]
1557fn concrete_extents(
1558    builder: &SemanticProgramBuilder,
1559    value: ProgramValue,
1560) -> std::result::Result<Option<Vec<usize>>, SemanticAdError> {
1561    let mut extents = Vec::new();
1562    for extent in builder.resolved_extents(value)? {
1563        match extent {
1564            tenferro_ops::ShapeExtent::Exact(tenferro_ops::dim_expr::DimExpr::Const(value)) => {
1565                extents.push(value);
1566            }
1567            _ => return Ok(None),
1568        }
1569    }
1570    Ok(Some(extents))
1571}
1572
1573#[cfg(feature = "autodiff")]
1574fn semantic_fft_unsupported(operation: FftOperation, role: SemanticAdRuleKind) -> SemanticAdError {
1575    semantic_fft_unsupported_family(
1576        fft_ad_family_id(operation),
1577        role,
1578        "FFT operation has no semantic AD rule",
1579    )
1580}
1581
1582#[cfg(feature = "autodiff")]
1583fn semantic_fft_unsupported_family(
1584    family_id: &'static str,
1585    role: SemanticAdRuleKind,
1586    message: impl Into<String>,
1587) -> SemanticAdError {
1588    SemanticAdError::Unsupported {
1589        family_id,
1590        role: match role {
1591            SemanticAdRuleKind::Linearize => {
1592                tenferro_ad::semantic_extension::SemanticAdRuleRole::Linearize
1593            }
1594            SemanticAdRuleKind::Transpose => {
1595                tenferro_ad::semantic_extension::SemanticAdRuleRole::LinearTranspose
1596            }
1597        },
1598        message: message.into(),
1599    }
1600}
1601
1602/// Return the semantic-program FFT extension AD rule set.
1603#[cfg(feature = "autodiff")]
1604///
1605/// # Errors
1606///
1607/// Returns [`SemanticExtensionRegistryError::MalformedFamilyId`] if the FFT
1608/// family identifier is invalid, or
1609/// [`SemanticExtensionRegistryError::DuplicateRule`] if a rule for the family
1610/// and role is already registered.
1611pub fn semantic_ad_rules(
1612) -> std::result::Result<SemanticExtensionRuleSet, SemanticExtensionRegistryError> {
1613    SemanticExtensionRuleSet::new()
1614        .with_linearize(Arc::new(FftAdRule))?
1615        .with_linear_transpose(Arc::new(FftAdRule))?
1616        .with_primal_vjp(Arc::new(FftAdRule))
1617}
1618
1619pub(crate) fn execute_fft_extension_reads_session(
1620    op: &FftOp,
1621    inputs: &[TensorRead<'_>],
1622    ctx: &mut ExtensionExecutionContext<'_, dyn Engine + '_>,
1623) -> tenferro_tensor::Result<Vec<Tensor>> {
1624    let (session, caches) = ctx.parts_mut();
1625    execute_fft_extension_reads_on_session(op, inputs, session, caches)
1626}
1627
1628fn execute_fft_extension_reads_for_capability<B: FftBackend + ?Sized>(
1629    op: &FftOp,
1630    inputs: &[TensorRead<'_>],
1631    session: &mut B,
1632    caches: &mut ExtensionCacheStore,
1633) -> tenferro_tensor::Result<Vec<Tensor>> {
1634    if inputs.len() != 1 {
1635        return Err(tenferro_tensor::Error::invalid_argument(
1636            "tenferro-fft",
1637            "inputs",
1638            format!("expected 1 input, got {}", inputs.len()),
1639        ));
1640    }
1641    Ok(vec![execute_fft_op(
1642        op,
1643        &inputs[0],
1644        session,
1645        FftExecutionCache::engine_owned(caches),
1646    )?])
1647}
1648
1649/// Execute one validated FFT request as successive one-axis backend calls.
1650///
1651/// This is the only axis loop for n-dimensional FFTs: the eager executor
1652/// ([`FftExecutor::fftn`]) and the traced/extension execution path both enter
1653/// here. Each iteration hands the backend a single-axis [`FftPlanSpec`], so the
1654/// backend runs its own plan for that length and dtype (`rustfft`/`realfft` on
1655/// CPU, a one-dimensional `cufftPlanMany` on CUDA) and reuses it from the shared
1656/// plan cache. Nothing here computes a transform: this function owns only the
1657/// axis order, the per-axis operation, and the intermediate shape bookkeeping.
1658fn execute_fft_op<B: FftBackend + ?Sized>(
1659    op: &FftOp,
1660    input: &TensorRead<'_>,
1661    session: &mut B,
1662    mut cache: FftExecutionCache<'_>,
1663) -> tenferro_tensor::Result<Tensor> {
1664    let mut current: Option<Tensor> = None;
1665    for index in op.execution_order() {
1666        let (dtype, shape) = match &current {
1667            Some(tensor) => (tensor.dtype(), tensor.shape().to_vec()),
1668            None => (input.dtype(), input.shape().to_vec()),
1669        };
1670        let spec = op.step_spec(index, dtype, &shape);
1671        let step_name = fft_op_name(spec.operation());
1672        let read = match &current {
1673            Some(tensor) => TensorRead::Tensor(tensor),
1674            None => input.clone(),
1675        };
1676        // The borrowed-view hook rejects an unusable placement before
1677        // canonicalization. An owned tensor keeps the backend's own placement
1678        // contract instead, where a managed CPU tensor is a legal input.
1679        if matches!(&read, TensorRead::View(_)) {
1680            session.validate_fft_read_input(step_name, &read)?;
1681        }
1682        let output = session.execute_fft_read(
1683            read,
1684            &spec,
1685            FftExecutionCache::with_owner(cache.owner(), cache.store_mut()),
1686        )?;
1687        current = Some(output);
1688    }
1689    current.ok_or_else(|| {
1690        tenferro_tensor::Error::invalid_argument(
1691            "tenferro-fft",
1692            "axes",
1693            "FFT requires at least one axis",
1694        )
1695    })
1696}
1697
1698fn execute_fft_extension_reads_on_session(
1699    op: &FftOp,
1700    inputs: &[TensorRead<'_>],
1701    session: &mut dyn Engine,
1702    caches: &mut ExtensionCacheStore,
1703) -> tenferro_tensor::Result<Vec<Tensor>> {
1704    if let Some(result) = with_cpu_engine(session, |session| {
1705        execute_fft_extension_reads_for_capability(op, inputs, session, caches)
1706    }) {
1707        return result;
1708    }
1709    #[cfg(feature = "cuda")]
1710    if let Some(result) = with_cuda_engine(session, |session| {
1711        execute_fft_extension_reads_for_capability(op, inputs, session, caches)
1712    }) {
1713        return result;
1714    }
1715    Err(tenferro_tensor::Error::unsupported(
1716        fft_op_name(op.operation),
1717        "selected backend session does not expose an FFT execution capability",
1718    ))
1719}
1720
1721define_extension_runtime! {
1722    runtime = FftRuntime,
1723    family_id = FFT_EXTENSION_FAMILY_ID,
1724    op_type = FftOp,
1725    execute_in_session = execute_fft_extension_reads_in_session,
1726    session_supported = fft_session_supported,
1727}
1728
1729/// Adapter from the scheduler/`apply_eager` borrowed-session shape to the
1730/// existing FFT session executor. Reuses the same forward kernel already shared
1731/// by the owner and eager paths; do not reimplement it here.
1732fn execute_fft_extension_reads_in_session(
1733    op: &FftOp,
1734    session: &mut dyn Engine,
1735    caches: &mut ExtensionCacheStore,
1736    inputs: &[TensorRead<'_>],
1737) -> tenferro_tensor::Result<Vec<Tensor>> {
1738    let mut ctx = ExtensionExecutionContext::new(session, caches);
1739    execute_fft_extension_reads_session(op, inputs, &mut ctx)
1740}
1741
1742fn fft_session_supported<B: Engine + 'static>(_op: &FftOp) -> bool {
1743    // The session executor routes CPU/CUDA/WebGPU through their FftBackend exec
1744    // sessions; keep scheduler-session admission consistent with the backends
1745    // that `execute_fft_extension_reads_on_session` actually handles.
1746    let type_id = std::any::TypeId::of::<B>();
1747    type_id == std::any::TypeId::of::<tenferro_cpu::CpuEngine>() || {
1748        #[cfg(feature = "cuda")]
1749        {
1750            type_id == std::any::TypeId::of::<CudaEngine>()
1751        }
1752        #[cfg(not(feature = "cuda"))]
1753        {
1754            false
1755        }
1756    }
1757}
1758
1759fn apply_unary_fftn(
1760    op_name: &'static str,
1761    input: &TracedTensor,
1762    operation: FftOperation,
1763    lengths: Option<&[usize]>,
1764    length_argument: &'static str,
1765    axes: &[isize],
1766    norm: FftNorm,
1767) -> Result<TracedTensor> {
1768    let concrete_shape = input.try_concrete_shape();
1769    let op = Arc::new(
1770        validated_fft_op(
1771            op_name,
1772            operation,
1773            Some(input.dtype()),
1774            input.rank(),
1775            concrete_shape.as_deref(),
1776            lengths,
1777            length_argument,
1778            axes,
1779            norm,
1780        )
1781        .map_err(graph_build_fft_error)?,
1782    );
1783    let mut outputs = apply(op, &[input])?;
1784    outputs
1785        .pop()
1786        .ok_or_else(|| Error::Internal("FFT extension declares exactly one output".into()))
1787}
1788
1789/// Re-raise a rejected traced or eager request as a graph-build validation error.
1790///
1791/// The request validator is shared with the concrete path and reports
1792/// `tenferro_tensor` errors; the graph-building surfaces report the same
1793/// validation failure at graph-build time.
1794fn graph_build_fft_error(error: tenferro_tensor::Error) -> Error {
1795    match error {
1796        tenferro_tensor::Error::Validation { op, source } => {
1797            Error::validation(op, ErrorPhase::GraphBuild, source)
1798        }
1799        other => Error::from(other),
1800    }
1801}
1802
1803/// Lengths of a one-axis request, so the one-dimensional entry points are the
1804/// ordinary n-dimensional builder with a single axis.
1805fn single_axis_lengths(n: Option<usize>) -> Option<[usize; 1]> {
1806    n.map(|n| [n])
1807}
1808
1809fn normalize_axis(op: &'static str, axis: isize, rank: usize) -> tenferro_tensor::Result<usize> {
1810    if rank == 0 {
1811        return Err(tenferro_tensor::Error::invalid_argument(
1812            op,
1813            "rank",
1814            "FFT requires rank >= 1",
1815        ));
1816    }
1817    // One shared normalization; the error keeps the caller's signed axis.
1818    tenferro_tensor::normalize_axis(axis, rank)
1819        .map_err(|source| tenferro_tensor::Error::validation(op, source))
1820}
1821
1822/// Build the one-axis operation descriptor used by the eager builder, which
1823/// validates the dtype itself.
1824#[cfg(feature = "autodiff")]
1825#[allow(clippy::too_many_arguments)]
1826fn prepare_runtime_fft_op(
1827    op_name: &'static str,
1828    operation: FftOperation,
1829    rank: usize,
1830    concrete_shape: Option<&[usize]>,
1831    n: Option<usize>,
1832    axis: isize,
1833    norm: FftNorm,
1834) -> Result<FftOp> {
1835    let lengths = single_axis_lengths(n);
1836    validated_fft_op(
1837        op_name,
1838        operation,
1839        None,
1840        rank,
1841        concrete_shape,
1842        lengths.as_ref().map(|lengths| lengths.as_slice()),
1843        "n",
1844        &[axis],
1845        norm,
1846    )
1847    .map_err(graph_build_fft_error)
1848}
1849
1850fn runtime_forward_fft_operation(dtype: DType) -> Result<FftOperation> {
1851    match dtype {
1852        DType::C32 | DType::C64 => Ok(FftOperation::C2cForward),
1853        DType::F32 | DType::F64 => Ok(FftOperation::R2cFull),
1854        DType::I32 | DType::I64 | DType::Bool | DType::External(_) => Err(
1855            runtime_unsupported_dtype("fft", dtype, "F32, F64, C32, or C64"),
1856        ),
1857    }
1858}
1859
1860fn require_runtime_dtype(
1861    op: &'static str,
1862    dtype: DType,
1863    supported: &[DType],
1864    expected: &'static str,
1865) -> Result<()> {
1866    if supported.contains(&dtype) {
1867        Ok(())
1868    } else {
1869        Err(runtime_unsupported_dtype(op, dtype, expected))
1870    }
1871}
1872
1873fn runtime_unsupported_dtype(op: &'static str, dtype: DType, expected: &'static str) -> Error {
1874    Error::extension(
1875        op,
1876        ErrorPhase::GraphBuild,
1877        FFT_EXTENSION_FAMILY_ID,
1878        ErrorKind::Unsupported,
1879        FftError::UnsupportedDType {
1880            op,
1881            dtype,
1882            expected,
1883        },
1884    )
1885}
1886
1887/// Symbolic companion of [`transform_len`].
1888///
1889/// It has to apply the same "transform length must be positive" rule: otherwise
1890/// compile-time preparation publishes a zero extent for an input that the
1891/// concrete path rejects.
1892fn transform_len_dim(n: Option<usize>, input_dim: &SymDim) -> tenferro_tensor::Result<SymDim> {
1893    let len = n.map(SymDim::from).unwrap_or_else(|| input_dim.clone());
1894    if len.constant_value() == Some(0) {
1895        return Err(tenferro_tensor::Error::invalid_argument(
1896            "fft",
1897            "transform length",
1898            "must be positive",
1899        ));
1900    }
1901    Ok(len)
1902}
1903
1904fn expected_dtype_description(operation: FftOperation) -> &'static str {
1905    match operation {
1906        FftOperation::C2cForward | FftOperation::C2cInverse | FftOperation::C2r => "C32 or C64",
1907        FftOperation::R2cFull | FftOperation::R2cOnesided => "F32 or F64",
1908    }
1909}
1910
1911fn fft_op_name(operation: FftOperation) -> &'static str {
1912    match operation {
1913        FftOperation::C2cForward => "fft",
1914        FftOperation::C2cInverse => "ifft",
1915        FftOperation::R2cFull | FftOperation::R2cOnesided => "rfft",
1916        FftOperation::C2r => "irfft",
1917    }
1918}
1919
1920#[cfg(feature = "autodiff")]
1921fn fft_ad_family_id(operation: FftOperation) -> &'static str {
1922    match operation {
1923        FftOperation::C2cForward | FftOperation::C2cInverse => FFT_EXTENSION_FAMILY_ID,
1924        FftOperation::R2cFull | FftOperation::R2cOnesided => "tenferro-fft.rfft.v1",
1925        FftOperation::C2r => "tenferro-fft.irfft.v1",
1926    }
1927}
1928
1929fn output_shape_c2c(
1930    shape: &[usize],
1931    axis: usize,
1932    n: Option<usize>,
1933) -> tenferro_tensor::Result<Vec<usize>> {
1934    let len = transform_len(shape, axis, n)?;
1935    let mut out_shape = shape.to_vec();
1936    out_shape[axis] = len;
1937    Ok(out_shape)
1938}
1939
1940fn output_shape_r2c(
1941    shape: &[usize],
1942    axis: usize,
1943    n: Option<usize>,
1944    onesided: bool,
1945) -> tenferro_tensor::Result<Vec<usize>> {
1946    let len = transform_len(shape, axis, n)?;
1947    let mut out_shape = shape.to_vec();
1948    out_shape[axis] = if onesided { len / 2 + 1 } else { len };
1949    Ok(out_shape)
1950}
1951
1952fn output_shape_c2r(
1953    shape: &[usize],
1954    axis: usize,
1955    n: Option<usize>,
1956) -> tenferro_tensor::Result<Vec<usize>> {
1957    validate_axis("irfft", shape, axis)?;
1958    let input_len = shape[axis];
1959    let len = match n {
1960        Some(len) => len,
1961        None => default_c2r_output_len(input_len)?,
1962    };
1963    if len == 0 {
1964        return Err(tenferro_tensor::Error::invalid_argument(
1965            "irfft",
1966            "output length",
1967            "must be positive",
1968        ));
1969    }
1970    validate_c2r_spectrum_len(input_len, len)?;
1971    let mut out_shape = shape.to_vec();
1972    out_shape[axis] = len;
1973    Ok(out_shape)
1974}
1975
1976fn output_dim_c2r(input_dim: &SymDim, n: Option<usize>) -> tenferro_tensor::Result<SymDim> {
1977    match (input_dim.constant_value(), n) {
1978        (Some(input_len), Some(output_len)) => {
1979            if output_len == 0 {
1980                return Err(tenferro_tensor::Error::invalid_argument(
1981                    "irfft",
1982                    "output length",
1983                    "must be positive",
1984                ));
1985            }
1986            validate_c2r_spectrum_len(input_len, output_len)?;
1987            Ok(SymDim::from(output_len))
1988        }
1989        (Some(input_len), None) => {
1990            let output_len = default_c2r_output_len(input_len)?;
1991            if output_len == 0 {
1992                return Err(tenferro_tensor::Error::invalid_argument(
1993                    "irfft",
1994                    "output length",
1995                    "must be positive",
1996                ));
1997            }
1998            Ok(SymDim::from(output_len))
1999        }
2000        (None, Some(output_len)) => {
2001            if output_len == 0 {
2002                return Err(tenferro_tensor::Error::invalid_argument(
2003                    "irfft",
2004                    "output length",
2005                    "must be positive",
2006                ));
2007            }
2008            Ok(SymDim::from(output_len))
2009        }
2010        (None, None) => Ok((input_dim.clone() - 1usize) * 2usize),
2011    }
2012}
2013
2014fn default_c2r_output_len(input_len: usize) -> tenferro_tensor::Result<usize> {
2015    if input_len == 0 {
2016        return Err(tenferro_tensor::Error::invalid_argument(
2017            "irfft",
2018            "input spectrum axis length",
2019            "must be positive",
2020        ));
2021    }
2022    input_len
2023        .checked_sub(1)
2024        .and_then(|len| len.checked_mul(2))
2025        .ok_or_else(|| {
2026            tenferro_tensor::Error::invalid_argument(
2027                "irfft",
2028                "default output length",
2029                "overflows usize",
2030            )
2031        })
2032}
2033
2034fn validate_c2r_spectrum_len(
2035    input_len: usize,
2036    output_len: usize,
2037) -> tenferro_tensor::Result<usize> {
2038    let expected = output_len / 2 + 1;
2039    if input_len != expected {
2040        return Err(tenferro_tensor::Error::invalid_argument(
2041            "irfft",
2042            "spectrum",
2043            format!(
2044                "one-sided spectrum axis length mismatch: expected {expected} for output length {output_len}, got {input_len}"
2045            ),
2046        ));
2047    }
2048    Ok(expected)
2049}
2050
2051fn transform_len(shape: &[usize], axis: usize, n: Option<usize>) -> tenferro_tensor::Result<usize> {
2052    validate_axis("fft", shape, axis)?;
2053    let len = n.unwrap_or(shape[axis]);
2054    if len == 0 {
2055        return Err(tenferro_tensor::Error::invalid_argument(
2056            "fft",
2057            "transform length",
2058            "must be positive",
2059        ));
2060    }
2061    Ok(len)
2062}
2063
2064fn validate_axis(op: &'static str, shape: &[usize], axis: usize) -> tenferro_tensor::Result<()> {
2065    if axis >= shape.len() {
2066        return Err(tenferro_tensor::Error::axis_out_of_bounds(
2067            op,
2068            axis,
2069            shape.len(),
2070        ));
2071    }
2072    Ok(())
2073}
2074
2075#[cfg(test)]
2076mod concrete_tests;
2077
2078#[cfg(test)]
2079mod nd_tests;
2080
2081#[cfg(test)]
2082mod lib_tests;