math_symbols/

lib.rs

//! Named symbols for use in compute algebra systems. Symbol names are
//! stored centrally such that copies are cheap and need little
//! memory.
//!
//! # Example
//!
//! ```rust
//! use math_symbols::*;
//!
//! // Define a number of symbols with variable name equal to symbol name
//! symbols!(x, y, z);
//! assert_eq!(x.name(), "x");
//! assert_eq!(y.name(), "y");
//! assert_eq!(z.name(), "z");
//!
//! // Symbols are identified by their names
//! let xx = Symbol::new("x");
//! assert_eq!(x, xx);
//!
//! // Symbols are ordered by their creation time
//! assert!(x < y);
//!
//! // We can generate symbol names dynamically. The allocated
//! // memory will be leaked if and only if a new symbol has to be created.
//! for i in 0..5 {
//!     // leaks memory
//!     let xi = Symbol::new(format!("x{i}"));
//! }
//!
//! for i in 0..5 {
//!     // does not leak any additional memory
//!     let xi = Symbol::new(format!("x{i}"));
//! }
//! ```
//! # Features
//!
//! - `serde` adds support for (de)serialisation with
//!   [serde](https://serde.rs/)
//! - By default each symbol is internally stored in a `u32`. Hence,
//!   the total number of symbols is limited to 2^32. The features `u8,
//!   u16, u64, u128, usize` enable symbols `Symbolu8, Symbolu16,
//!   Symbolu64, Symbolu128, Symbolusize`, and macros `symbols_u8,
//!   symbols_u16, symbols_u64, symbols_u128, symbols_usize` for the
//!   corresponding storage type.
//!
//! # Similar crates
//!
//! - [symbol](https://crates.io/crates/symbol)
//! - [symbolica](https://symbolica.io) uses a similar symbol storage mechanism.
//!
use std::{
    borrow::Cow,
    fmt::{self, Display},
    sync::{LazyLock, Mutex},
};

use ahash::AHashMap;
use append_only_vec::AppendOnlyVec;
use paste::paste;

#[macro_export]
macro_rules! impl_symbol {
    ( $( $t:tt ),* ) => {
        $(
            paste! {
                #[derive(Debug, Default)]
                struct [<SymbolRegister $t>] {
                    names: AppendOnlyVec<&'static str>,
                    indices: Mutex<AHashMap<&'static str, $t>>,
                }

                impl [<SymbolRegister $t>] {
                    fn new() -> Self {
                        Self {
                            names: AppendOnlyVec::new(),
                            indices: Mutex::new(AHashMap::new()),
                        }
                    }

                    fn name(&self, idx: usize) -> &'static str {
                        &self.names[idx]
                    }

                    fn idx<S>(&self, name: S) -> $t
                    where
                        S: AsRef<str> + Leak<&'static str>,
                    {
                        let mut indices = self.indices.lock().unwrap();
                        if let Some(idx) = indices.get(name.as_ref()) {
                            return *idx;
                        }
                        let name = name.leak();
                        let new_idx = self.names.len() as _;
                        indices.insert(name, new_idx);
                        // Here, we are still protected by the mutex.
                        // this is necessary to ensure to synchronise the position
                        // inserted into `indices` with the length of `names`
                        self.names.push(name);
                        new_idx
                    }
                }

                static [<SYMBOL_REGISTER_ $t:upper>]: LazyLock<[<SymbolRegister $t>]> =
                    LazyLock::new(|| [<SymbolRegister $t>]::new());

                /// A symbol
                #[derive(Copy, Clone, Debug, Default, Eq, PartialEq, Ord, PartialOrd, Hash)]
                #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
                #[cfg_attr(feature = "serde", serde(transparent))]
                pub struct [<Symbol $t>] {
                    #[cfg_attr(
                        feature = "serde",
                        serde(
                            serialize_with = "serialize_sym_" $t,
                            deserialize_with = "deserialize_sym_"  $t
                        )
                    )]
                    idx: $t,
                }

                impl [<Symbol $t>] {
                    /// Construct a symbol with the given name
                    pub fn new<S>(name: S) -> Self
                    where S: AsRef<str> + Leak<&'static str>,
                    {
                        let idx = [<SYMBOL_REGISTER_ $t:upper>].idx(name);
                        Self { idx }
                    }

                    /// Construct a symbol with the given name from a boxed string
                    pub fn new_from_box(name: Box<str>) -> Self {
                        let inner: &'static str = Box::leak(name);
                        let idx = [<SYMBOL_REGISTER_ $t:upper>].idx(inner);
                        Self { idx }
                    }

                    /// Construct a symbol with the given name from a string slice
                    ///
                    /// If no symbol with the same name is known, this
                    /// will require an allocation and leak the
                    /// allocated memory. Prefer [new](Self::new) for
                    /// string slices with `static` lifetimes.
                    pub fn new_from_str<'a>(name: &'a str) -> Self {
                        Self::new(StrWrapper(name))
                    }

                    /// Get the symbol's name
                    pub fn name(&self) -> &'static str {
                        [<SYMBOL_REGISTER_ $t:upper>].name(self.idx as _)
                    }
                }

                impl Display for [<Symbol $t>] {
                    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
                        write!(f, "{}", [<SYMBOL_REGISTER_ $t:upper>].name(self.idx as _))
                    }
                }

                #[cfg(feature = "serde")]
                fn [<serialize_sym_ $t>]<S: serde::Serializer>(
                    sym: &$t,
                    s: S,
                ) -> Result<S::Ok, S::Error> {
                    use serde::Serialize;
                    let sym = [<Symbol $t>] { idx: *sym };
                    let name = sym.name();
                    str::serialize(name, s)
                }

                #[cfg(feature = "serde")]
                fn [<deserialize_sym_ $t>]<'de, D: serde::Deserializer<'de>>(
                    d: D,
                ) -> Result<$t, D::Error> {
                    use serde::Deserialize;
                    let name = String::deserialize(d)?;
                    let s = [<Symbol $t>]::new(name);
                    Ok(s.idx)
                }
            }
        )*
    };
}

#[cfg(feature = "u8")]
impl_symbol!(u8);

#[cfg(feature = "u16")]
impl_symbol!(u16);

#[cfg(feature = "u32")]
impl_symbol!(u32);

#[cfg(feature = "u64")]
impl_symbol!(u64);

#[cfg(feature = "u128")]
impl_symbol!(u128);

#[cfg(feature = "usize")]
impl_symbol!(usize);

#[cfg(feature = "u32")]
pub type Symbol = Symbolu32;

/// A type that can be leaked into a `T`
pub trait Leak<T> {
    fn leak(self) -> T;
}

impl Leak<&'static str> for &'static str {
    fn leak(self) -> &'static str {
        self
    }
}

impl Leak<&'static str> for String {
    fn leak(self) -> &'static str {
        String::leak(self)
    }
}

impl Leak<&'static str> for Cow<'static, str> {
    fn leak(self) -> &'static str {
        match self {
            Cow::Borrowed(s) => s,
            Cow::Owned(s) => s.leak(),
        }
    }
}

/// Construct variables with the same variable and symbol name
#[cfg(feature = "u32")]
#[macro_export]
macro_rules! symbols {
    ( $( $x:ident ),* ) => {
        $(
            let $x = $crate::Symbol::new(stringify!($x));
        )*
    };
}

// TODO: put this inside `impl_symbol!`

/// Construct variables with the same variable and symbol name
#[cfg(feature = "u8")]
#[macro_export]
macro_rules! symbols_u8 {
    ( $( $x:ident ),* ) => {
        $(
            let $x = $crate::Symbolu8::new(stringify!($x));
        )*
    };
}

/// Construct variables with the same variable and symbol name
#[cfg(feature = "u16")]
#[macro_export]
macro_rules! symbols_u16 {
    ( $( $x:ident ),* ) => {
        $(
            let $x = $crate::Symbolu16::new(stringify!($x));
        )*
    };
}

/// Construct variables with the same variable and symbol name
#[cfg(feature = "u32")]
#[macro_export]
macro_rules! symbols_u32 {
    ( $( $x:ident ),* ) => {
        $(
            let $x = $crate::Symbolu32::new(stringify!($x));
        )*
    };
}

/// Construct variables with the same variable and symbol name
#[cfg(feature = "u64")]
#[macro_export]
macro_rules! symbols_u64 {
    ( $( $x:ident ),* ) => {
        $(
            let $x = $crate::Symbolu64::new(stringify!($x));
        )*
    };
}

#[cfg(feature = "u128")]
/// Construct variables with the same variable and symbol name
#[macro_export]
macro_rules! symbols_u128 {
    ( $( $x:ident ),* ) => {
        $(
            let $x = $crate::Symbolu128::new(stringify!($x));
        )*
    };
}

/// Construct variables with the same variable and symbol name
#[cfg(feature = "usize")]
#[macro_export]
macro_rules! symbols_usize {
    ( $( $x:ident ),* ) => {
        $(
            let $x = $crate::Symbolusize::new(stringify!($x));
        )*
    };
}

struct StrWrapper<'a>(&'a str);

impl<'a> Leak<&'static str> for StrWrapper<'a> {
    fn leak(self) -> &'static str {
        self.0.to_owned().leak()
    }
}

impl<'a> AsRef<str> for StrWrapper<'a> {
    fn as_ref(&self) -> &str {
        &self.0
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn symbol() {
        symbols!(x, y, z);
        assert_eq!(x.name(), "x");
        assert_eq!(y.name(), "y");
        assert_eq!(z.name(), "z");
        let xx = Symbol::new("x");
        assert_eq!(xx.name(), "x");
    }

    #[test]
    fn owned() {
        symbols!(x);
        let xx = Symbol::new("x".to_owned());
        assert_eq!(xx, x);
    }

    #[test]
    fn owned_box() {
        symbols!(x);
        let xx = Symbol::new_from_box("x".to_owned().into_boxed_str());
        assert_eq!(xx, x);
    }

    #[test]
    fn cow() {
        let x = Symbol::new(Cow::Owned("x".to_owned()));
        assert_eq!(x.name(), "x");
        let xx = Symbol::new(Cow::Borrowed("x"));
        assert_eq!(xx, x);
    }

    #[cfg(feature = "u8")]
    #[test]
    fn symbol_u8() {
        symbols_u8!(x, y, z);
        assert_eq!(x.name(), "x");
        assert_eq!(y.name(), "y");
        assert_eq!(z.name(), "z");
        let xx = Symbolu8::new("x");
        assert_eq!(xx.name(), "x");
    }

    #[test]
    fn symbol_str() {
        symbols!(x);
        let xx = {
            let x = "x".to_owned();
            Symbol::new_from_str(&x)
        };
        assert_eq!(x, xx);
    }
}