rssn_advanced/

lib.rs

//! # rssn-advanced
//!
//! **rssn-advanced** is the symbolic computation engine of the
//! [rssn](https://github.com/Apich-Organization/rssn) project.  It provides a
//! hash-consed expression DAG, a [Cranelift](https://cranelift.dev/)-backed JIT
//! compiler, heuristic and e-graph simplification, multi-architecture inline-asm
//! presets, and a flat `extern "C"` API for embedding in C/C++ and other languages.
//!
//! ---
//!
//! ## Architecture
//!
//! | Module | Role |
//! |--------|------|
//! | [`dag`] | Hash-consed expression DAG — the canonical, deduplicated store for all symbolic nodes |
//! | [`ast`] | Lightweight local tree projection of a DAG subgraph via relative `i32` pointers |
//! | [`parser`] | `nom`-based infix parser: `"x^2 + 2*x + 1"` → DAG root |
//! | [`jit`] *(feature: `cranelift-jit`)* | Cranelift JIT; emits scalar `f64` closures and 2-row ILP batch functions |
//! | [`heuristic`] | Configurable greedy/beam simplifier with a pluggable [`heuristic::rule_registry::RuleRegistry`] |
//! | [`egraph`] | Lightweight equality saturation over the DAG (no `egg` dependency) |
//! | [`custom`] | Unified custom-operator system — one [`custom::descriptor::CustomOpDescriptor`] wires into JIT + simplifier + e-graph |
//! | [`simd`] | Slice-level batch arithmetic using the inline-asm presets |
//! | [`asm_presets`] | Hand-written `f64×2` / `f64×4` kernels for `x86_64` (SSE2/AVX2/AES-NI), `AArch64` (NEON/crypto), riscv64 (RVV/Zkn) |
//! | [`ffi`] | Flat `extern "C"` surface generated by `cbindgen`; includes a fiber-backed async bridge |
//! | [`parallel`] | Fiber-based parallel simplification via the `dtact` runtime |
//! | [`storage`] | Disk-backed DAG spillover and a frequency-based hot-node cache |
//! | [`error`] | Cold-path error types and the `rssn_error!` macro |
//!
//! ---
//!
//! ## Quick start
//!
//! ### Parse and evaluate
//!
//! ```rust
//! use rssn_advanced::dag::builder::DagBuilder;
//! use rssn_advanced::parser::expr::parse_expression;
//!
//! let mut builder = DagBuilder::new();
//! // parse_expression(input, &mut builder) -> Result<DagNodeId, ParseError>
//! let root = parse_expression("x^2 + 2*x + 1", &mut builder).unwrap();
//! let _ = root;
//! ```
//!
//! ### JIT-compile and bulk-evaluate
//!
//! ```rust
//! # // cfg guard: skip when cranelift-jit feature is absent
//! # #[cfg(not(feature = "cranelift-jit"))] fn main() {}
//! # #[cfg(feature = "cranelift-jit")] fn main() {
//! use rssn_advanced::dag::builder::DagBuilder;
//! use rssn_advanced::parser::expr::parse_expression;
//! use rssn_advanced::ast::convert::dag_to_ast;
//! use rssn_advanced::jit::compiler::JitCompiler;
//!
//! let mut builder = DagBuilder::new();
//! let root = parse_expression("x^2 + 2*x + 1", &mut builder).unwrap();
//!
//! let mut compiler = JitCompiler::try_new().unwrap();
//! let ast = dag_to_ast(builder.arena(), root);
//! let f   = compiler.compile(&ast).unwrap();
//!
//! // CompiledExprFn = extern "C" fn(*const f64) -> f64
//! assert_eq!(f([3.0_f64].as_ptr()), 16.0); // (3+1)^2
//!
//! // 2-row ILP batch path; returns None if expression is not vectorizable
//! let _batch = compiler.compile_batch_f64x2(&ast).unwrap();
//! # }
//! ```
//!
//! ### Register a custom operator
//!
//! ```rust
//! # // cfg guard: skip when cranelift-jit feature is absent
//! # #[cfg(not(feature = "cranelift-jit"))] fn main() {}
//! # #[cfg(feature = "cranelift-jit")] fn main() {
//! use std::sync::Arc;
//! use rssn_advanced::dag::builder::DagBuilder;
//! use rssn_advanced::custom::descriptor::{CustomOpDescriptor, CustomOpRegistry, EvalFn};
//! use rssn_advanced::egraph::egraph::{EGraph, EGraphConfig};
//! use rssn_advanced::jit::compiler::JitCompiler;
//!
//! extern "C" fn my_relu(x: f64) -> f64 { x.max(0.0) }
//!
//! let mut builder = DagBuilder::new();
//! // intern_function returns the FnId used to identify this operator
//! let fn_id = builder.intern_function("relu");
//!
//! let desc = CustomOpDescriptor::builder(fn_id, "relu", EvalFn::Arity1(my_relu))
//!     .vectorizable()   // safe to duplicate in the 2-row ILP batch path
//!     .cost(1.0)
//!     .build();
//!
//! let mut reg = CustomOpRegistry::new();
//! reg.register(desc).unwrap();
//! let reg = Arc::new(reg);
//!
//! // Wire into the JIT (registers the eval_fn pointer)
//! let mut compiler = JitCompiler::try_new().unwrap();
//! reg.apply_to_jit(&mut compiler);
//!
//! // Wire into the heuristic simplifier
//! let _rule_reg = reg.build_rule_registry();
//!
//! // Wire into the e-graph saturation engine
//! {
//!     let mut egraph = EGraph::new(&mut builder, EGraphConfig::default());
//!     reg.apply_to_egraph(&mut egraph);
//! }
//! # }
//! ```
//!
//! ---
//!
//! ## Performance
//!
//! Benchmark: bulk evaluation of N = 1,000,000 rows, best of 5 runs.
//! Hardware: Dell Latitude 5400, Intel i7-8665U @ 1.90 GHz (laptop-class, 16 MB L3),
//! Fedora Linux 44, kernel 6.19.  Compared against hand-optimised `NumPy` 1.x
//! (BLAS-linked, SIMD-enabled).
//!
//! | Expression | JIT bulk | JIT batch | `NumPy` | Speedup (bulk / batch) |
//! |------------|--------:|----------:|------:|-----------------------:|
//! | `x + y + 10.0` (trivial baseline) | 1.87 ns | 1.13 ns | 2.82 ns | **1.5× / 2.5×** |
//! | `(x-y)^4` — degree-4 polynomial   | 2.73 ns | 1.28 ns | 19.21 ns | **7× / 15×** |
//! | cubic surface (10 terms, 3 vars)  | 3.73 ns | 1.77 ns | 75.75 ns | **20× / 43×** |
//! | rational expression w/ CSE        | 2.53 ns | 1.27 ns | 15.91 ns | **6× / 13×** |
//!
//! **Why the gap grows with complexity:** `NumPy` allocates one `f64[N]` scratch array
//! per arithmetic operation.  A 10-term expression at N = 10⁶ creates ~200 MB of
//! temporaries that thrash L3 cache.  The JIT keeps every intermediate value in a
//! CPU register across the full expression, paying exactly one memory round-trip
//! per input column.
//!
//! **Honest caveats:**
//! - Numbers are from a single laptop; server CPUs with larger L3 caches will show a
//!   smaller gap for simple expressions.
//! - The batch path unrolls 2 rows for ILP but does **not** emit wide-vector AVX/AVX-512
//!   instructions; the [`asm_presets`] / [`simd`] paths are faster for fixed-width kernels.
//! - Cranelift's code quality is good but not hand-tuned; `gcc -O3` / LLVM can sometimes
//!   produce tighter loops for simple expressions.
//!
//! ---
//!
//! ## Feature flags
//!
//! | Flag | Default | Effect |
//! |------|:-------:|--------|
//! | `cranelift-jit` | **on** | Enables the [`jit`] module, JIT compilation, and the batch-evaluate path |
//!
//! Disable with `--no-default-features` for embedded or size-constrained targets.
//! The parser, DAG, heuristic simplifier, e-graph, and SIMD presets are all
//! available without the JIT feature.
//!
//! ---
//!
//! ## Known limitations
//!
//! - **Parser scope:** handles `+`, `-`, `*`, `/`, `^`, `%`, unary negation, and
//!   registered named functions.  Transcendentals (`sin`, `exp`, …) must be
//!   registered as custom operators.
//! - **Single-threaded JIT context:** compilation requests from multiple threads
//!   serialise on a global `Mutex`.
//! - **No GPU or BLAS integration.**
//! - **`asm_presets` on Windows:** some NEON / RVV paths are x86/AArch64/riscv64
//!   specific; the scalar fallback is always available.
//! - **e-graph extractor is greedy:** the current cost-minimising extractor uses a
//!   greedy bottom-up pass; optimal extraction is NP-hard and not yet implemented.
#![doc(
    html_logo_url = "https://raw.githubusercontent.com/Apich-Organization/rssn/refs/heads/dev/doc/logo.png"
)]
#![doc(
    html_favicon_url = "https://raw.githubusercontent.com/Apich-Organization/rssn/refs/heads/dev/doc/favicon.ico"
)]
// -------------------------------------------------------------------------
// Rust Lint Configuration: rssn-advanced
// -------------------------------------------------------------------------

// -------------------------------------------------------------------------
// LEVEL 1: CRITICAL ERRORS (Deny)
// -------------------------------------------------------------------------
#![deny(
    // Rust Compiler Errors
    dead_code,
    unreachable_code,
    improper_ctypes_definitions,
    future_incompatible,
    nonstandard_style,
    rust_2018_idioms,
    clippy::perf,
    clippy::correctness,
    clippy::suspicious,
    clippy::unwrap_used,
    clippy::expect_used,
    clippy::indexing_slicing,
    clippy::arithmetic_side_effects,
    clippy::missing_safety_doc,
    clippy::same_item_push,
    clippy::implicit_clone,
    clippy::all,
    clippy::pedantic,
    warnings,
    missing_docs,
    clippy::nursery,
    clippy::single_call_fn,
)]
// -------------------------------------------------------------------------
// LEVEL 2: STYLE WARNINGS (Warn)
// -------------------------------------------------------------------------
#![warn(
    clippy::dbg_macro,
    warnings,
    clippy::todo,
    clippy::unnecessary_safety_comment
)]
// -------------------------------------------------------------------------
// LEVEL 3: ALLOW/IGNORABLE (Allow)
// -------------------------------------------------------------------------
#![allow(
    unsafe_code,
    clippy::inline_always,
    clippy::restriction,
    clippy::cast_possible_truncation,
    clippy::cast_sign_loss,
    clippy::items_after_statements,
    clippy::too_long_first_doc_paragraph,
    clippy::non_send_fields_in_send_ty,
    unused_doc_comments,
    clippy::empty_line_after_outer_attr,
    clippy::empty_line_after_doc_comments
)]

// =========================================================================
// Module Declarations
// =========================================================================

/// Inline-assembly preset suite (AVX2 / AES-NI / scalar fallback).
///
/// Each preset is a 4-lane `f64` kernel emitted via `core::arch::asm!`
/// — no reliance on auto-vectorization. Used by both `simd` (slice
/// wrappers) and indirectly by `jit` (peephole patterns). Lives at the
/// crate root so neither subsystem has to feature-gate the other.
pub mod asm_presets;

/// Cold-path error infrastructure.
///
/// Hosts the `rssn_error!` macro and the module-level error enums.
/// Replaces the previous ad-hoc `unwrap()` / `expect()` / `assert_eq!`
/// pattern with `#[cold] #[inline(never)]` constructors so that error
/// handling stays off the hot path.
pub mod error;

/// Zero-copy borrowed containers and `bincode-next` `BorrowDecode` glue.
///
/// `BorrowedSlice` / `BorrowedArena` decode by `take_bytes` directly off
/// the input buffer, and `MmapBuffer` provides file-backed storage with
/// 8-byte aligned bytes for safe reinterpretation as `&[T: Pod]`.
pub mod zerocopy;

/// Fiber-based task runtime built on `dtact`.
///
/// Replaces `std::thread::spawn` with lightweight fibers throughout the
/// crate. `parallel_for_each` is the workhorse used by `parallel::solver`
/// and `ffi::async_bridge`.
pub mod runtime;

/// Allocator-light shared utilities (worklist traversals, helpers).
pub mod util;

/// Global DAG (Directed Acyclic Graph) storage for symbolic expressions.
///
/// Provides hash-consed, structurally-shared storage for all symbol nodes.
/// The DAG serves as the canonical representation — all expression data
/// ultimately lives here, deduplicated via structural hashing.
pub mod dag;

/// Local AST (Abstract Syntax Tree) projection for computation.
///
/// Projects a subgraph of the global DAG into a stack-local tree using
/// relative pointers (`i32` / `i64`). This provides an algorithm-friendly
/// tree view without duplicating the underlying metadata.
pub mod ast;

/// Symbolic expression parser.
///
/// Parses mathematical expressions (e.g. `"x^2 + 2*x + 1"`) into the
/// global DAG using `nom`-based combinators with precedence climbing.
pub mod parser;

/// JIT compilation pipeline for symbolic derivation rules.
///
/// Compiles algebraic rewrite rules (add, mul, div, custom) into native
/// machine code via Cranelift. Gated behind the `jit` feature (alias
/// `cranelift-jit` kept for backward compatibility).
#[cfg(feature = "jit")]
pub mod jit;

/// Parallel computation engine.
///
/// Exploits commutativity to split expressions into independent chunks
/// for async parallel simplification, with staged global merging.
pub mod parallel;

/// Streaming storage and dynamic caching.
///
/// Provides disk-backed spillover for large DAGs and a dynamic hotspot
/// table that tracks intermediate result frequency for auto-eviction.
pub mod storage;

/// Heuristic search toolbox for NP-hard pattern matching.
///
/// A configurable "knob-based" engine that allows controlled approximate
/// simplification when exact methods hit symbol explosion.
pub mod heuristic;

/// Lightweight E-graph for equality saturation.
///
/// Implements equality saturation over the hash-consed DAG without importing
/// the heavy `egg` crate. Uses a path-compressed union-find directly over
/// [`dag::node::DagNodeId`] values, and extracts the minimum-cost
/// representative after each saturation run.
pub mod egraph;

/// SIMD-optimized preset function library.
///
/// Hardware-accelerated batch operations (arithmetic, hashing) with
/// runtime feature detection and scalar fallback.
pub mod simd;

/// Unified custom-operator extension system.
///
/// A single [`custom::descriptor::CustomOpDescriptor`] bundles every
/// pipeline-facing property of a user-defined operator: JIT eval function,
/// batch-vectorisability flag, heuristic simplification rules, and e-graph
/// rewrite rules.  Register descriptors into a
/// [`custom::descriptor::CustomOpRegistry`], then call the three integration
/// methods to wire the operator into all pipeline stages simultaneously:
///
/// - `registry.apply_to_jit(&mut compiler)` — feeds `eval_fn` pointers to
///   the JIT and enables the 2-row ILP batch path for vectorizable operators.
/// - `registry.build_rule_registry()` — produces a [`heuristic::rule_registry::RuleRegistry`]
///   from all attached [`custom::descriptor::SimplifyRule`]s.
/// - `registry.apply_to_egraph(&mut egraph)` — injects all
///   [`custom::descriptor::EGraphRule`]s into an [`egraph::egraph::EGraph`].
///
/// See the [crate-level "Register a custom operator" example](crate) for a
/// runnable end-to-end demonstration.
///
/// C/C++ callers use the `rssn_custom_op_*` family in [`ffi::c_api`].
pub mod custom;

/// C/C++ Foreign Function Interface.
///
/// Exposes a flat, `extern "C"` API surface via `cbindgen`-compatible
/// types and opaque handles. Includes an async bridge for multi-language
/// integration.
pub mod ffi;

#[cfg_attr(miri, ignore)]
mod readme {
    #![doc = include_str!("../README.md")]
}