hwcalc_lib 0.2.0

mod eval;
mod fmt;
mod ir;
pub mod lex;
mod parse;

pub use ir::Num;

use parse::Span;

#[cfg(not(any(test, small_max)))]
const RECURSION_LIMIT: usize = 1024;
#[cfg(any(test, small_max))]
const RECURSION_LIMIT: usize = 64;

type Namespace = std::collections::HashMap<Sym, ir::Num>;

#[derive(Default)]
pub struct Context {
    symtab: SymbolTable,
    namespace: Namespace,
}

impl Context {
    /// Parse and evaluate an expression to a number.
    pub fn eval(&mut self, expr: &str) -> Result<Vec<Num>, Error> {
        parse::parse(expr, &mut self.symtab)?
            .into_iter()
            .map(|expr| eval::Evaluator::new(&mut self.namespace).eval(expr))
            .collect::<Result<Vec<ir::Num>, _>>()
            .map_err(Error::from)
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Error {
    pub kind: ErrorKind,
    pub span: Span,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ErrorKind {
    Parse(parse::ErrorKind),
    Eval(eval::ErrorKind),
}

impl std::fmt::Display for ErrorKind {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        match self {
            Self::Parse(k) => k.fmt(f),
            Self::Eval(k) => k.fmt(f),
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Base {
    Bin = 2,
    Oct = 8,
    Dec = 10,
    Hex = 16,
}

impl Base {
    const fn radix(self) -> u8 {
        self as u8
    }

    const fn bits_per_digit(self) -> u8 {
        u8::BITS as u8 - self.radix().leading_zeros() as u8 - 1
    }

    const fn from_prefix(c: char) -> Option<Self> {
        match c {
            'b' => Some(Self::Bin),
            'o' => Some(Self::Oct),
            'd' => Some(Self::Dec),
            'x' => Some(Self::Hex),
            _ => None,
        }
    }

    const fn prefix(self) -> char {
        match self {
            Self::Bin => 'b',
            Self::Oct => 'o',
            Self::Dec => 'd',
            Self::Hex => 'x',
        }
    }

    fn is_digit(self, c: char) -> bool {
        c.is_digit(self.radix().into())
    }

    fn max_digit(self) -> char {
        let r = self.radix().into();
        char::from_digit(r - 1, r).unwrap()
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Sym(u16);

impl Sym {
    const UNDERSCORE: Sym = Sym(0);
}

// TODO avoid storing strings twice
pub struct SymbolTable {
    strings: Vec<String>,
    syms: std::collections::HashMap<String, Sym>,
}

impl Default for SymbolTable {
    fn default() -> Self {
        const PREFILL: &[(&str, Sym)] = &[("_", Sym::UNDERSCORE)];
        SymbolTable {
            strings: PREFILL.iter().map(|(s, _)| (*s).to_string()).collect(),
            syms: PREFILL
                .iter()
                .map(|(s, sy)| ((*s).to_string(), *sy))
                .collect(),
        }
    }
}

impl SymbolTable {
    fn sym(&self, string: &str) -> Option<Sym> {
        self.syms.get(string).copied()
    }

    fn insert(&mut self, string: &str) -> Sym {
        if let Some(sym) = self.sym(string) {
            sym
        } else {
            let sym = Sym(u16::try_from(self.strings.len()).unwrap());
            self.strings.push(string.to_string());
            self.syms.insert(string.to_string(), sym);
            sym
        }
    }
}

#[cfg(test)]
mod test {
    use super::eval::ErrorKind::*;
    use super::Num;

    #[test]
    fn symtab_insert() {
        const A: &str = "a";
        const B: &str = "b";
        let mut st = super::SymbolTable::default();

        assert_eq!(st.sym(A), None);
        let a = st.insert(A);
        assert_eq!(st.sym(A), Some(a));
        assert_eq!(st.insert(A), a);

        assert_eq!(st.sym(B), None);
        let b = st.insert(B);
        assert_ne!(a, b);
        assert_eq!(st.sym(B), Some(b));
        assert_eq!(st.insert(B), b);
    }

    #[test]
    fn symtab_prefill() {
        let st = super::SymbolTable::default();
        assert_eq!(st.sym("_"), Some(super::Sym::UNDERSCORE));
    }

    macro_rules! test_expr {
        ($src:literal $(,$($expected:expr),*)? $(,)?) => {
            let actual = super::Context::default().eval($src).unwrap();
            let expected = &[$($($expected),*)?];
            assert_eq!(actual, expected, "{}", $src);
        };
    }

    macro_rules! test_err {
        ($src:literal, $expected:expr $(,)?) => {
            assert_eq!(
                super::Context::default().eval($src),
                Err($expected),
                "{}",
                $src
            );
        };
    }

    #[test]
    fn empty() {
        test_expr!("");
    }

    #[test]
    fn truncate() {
        // truncate int
        test_expr!("0b1111_1111'u4", Num::u(0b1111).w(4));
        test_expr!("0b1111_1111'i4", Num::i(-1).w(4));
        test_expr!("0b1111_0000'i4", Num::i(0b0000).w(4));
        // truncate frac
        test_expr!("0b1.1111'q.2", Num::q(0b1_11, 0b_100).wf(2));
        // truncate int / frac
        test_expr!("0b1111.1111'q3.2", Num::q(0b111_11, 0b_100).w(3).wf(2));
        // remove all of int
        test_expr!("1'0", Num::n(0).w(0));
        test_expr!("1.uq0", Num::uq(0, 1).w(0));
        // remove all of frac
        test_expr!("1.5'.0", Num::n(1).wf(0));
        test_expr!("1.5uq.0", Num::u(1).wf(0));
        test_expr!("1.5u", Num::u(1).wf(0));
    }

    #[test]
    fn extend() {
        test_expr!("0b1111u4'i8", Num::i(0b1111).w(8));
        test_expr!("0b1111i4'i8", Num::i(-1).w(8));
    }

    #[test]
    fn cast_out_of_range() {
        // too large
        test_err!("1'255'.1", CastWidthOutOfRange.span(0, 8).into());
        // total zero
        test_err!("1'0'.0", CastWidthOutOfRange.span(0, 6).into());
        // signed without sign bit
        test_err!("1uq'0'q", CastWidthOutOfRange.span(0, 7).into());
    }

    #[test]
    fn bin_op_extend() {
        test_expr!("32u8 + 0b1111u4", Num::u(32 + 0b1111).w(8));
        test_expr!("32u8 + 0b1111i4", Num::i(32 - 1).w(8));
        test_expr!("0b10u2 + 0b.011uq.3", Num::uq(0b10_011, 0b1_000).w(2).wf(3));
        // bin op total width too large
        test_err!("1uq255 + 1uq.1", CastWidthOutOfRange.span(0, 14).into());
    }

    #[test]
    fn bin_op_truncate() {
        test_expr!("0b1111u4 + 0b1111u4", Num::u(0b1110).w(4));
    }

    // shift result should always have type of left operand
    #[test]
    fn shift_ty() {
        test_expr!("0b1u << 1i", Num::u(0b10));
        test_expr!("0b11.1q2.1 << 1u1", Num::q(0b11, 1).w(2).wf(1));
        test_expr!("0b1 >> 1q2.2", Num::nd(0b0_1, 0b1_0));
    }

    // pow result should always have type of left operand
    #[test]
    fn pow_ty() {
        test_expr!("2u**2i", Num::u(4));
        test_expr!("3q2.1**2u1", Num::q(9, 1).w(2).wf(1));
        test_expr!("7**3q3.2", Num::n(343));
    }

    #[test]
    fn bin_op_value_too_large() {
        test_err!(
            "0x7fff_ffff_ffff_ffff_ffff_ffff_ffff_ffff_ffff_ffff_ffff_ffff_ffff_ffff_ffff_ffff+1",
            ValueTooLarge.span(0, 83).into(),
        );
    }

    #[test]
    fn assign() {
        test_expr!("a = 5 + 5", Num::n(10));
        test_expr!("a = 5; 10*a", Num::n(5), Num::n(50));
        test_expr!("a = 7 + b = 5 + 5; b", Num::n(17), Num::n(10));
    }

    #[test]
    fn ans() {
        test_err!("_", NameNotFound.span(0, 1).into());
        test_expr!("5; _", Num::n(5), Num::n(5));
        test_expr!("5; 1+_", Num::n(5), Num::n(6));
        test_expr!("5; 1+_; 2*_", Num::n(5), Num::n(6), Num::n(12));
    }

    #[test]
    fn not() {
        test_expr!("!0i", Num::i(-1));
        test_expr!("!(-1u)", Num::u(0));
        test_expr!("!0b0000u4", Num::u(0b1111).w(4));
        test_expr!("!0b1111u4", Num::u(0b0000).w(4));
        test_expr!("!0b0000i4", Num::i(-1).w(4));
        test_expr!("!0b1111i4", Num::i(0b0000).w(4));
        test_expr!("!0b1010.10q4.2", Num::q(0b0101_01, 0b1_00).w(4).wf(2));
    }

    #[test]
    fn not_inf_fix() {
        test_expr!("!0b0", Num::n(0)); // !0b = 0b(1).(1) = 0
        test_expr!("!-1", Num::n(1)); // !-1 = !0b(1).0 = 0b.(1) = 1
        test_expr!("!2.25", Num::nd(-9, 4));
        test_expr!("!-2.25", Num::nd(9, 4));
    }

    #[test]
    fn neg() {
        test_expr!("-0i", Num::i(0));
        test_expr!("-1i", Num::i(-1));
        test_expr!("-1i8", Num::i(255).w(8));
        test_expr!("-7i4", Num::i(-7).w(4));
        test_expr!("-(-7i4)", Num::i(7).w(4));
        test_expr!("-(-8i4)", Num::i(-8).w(4));
    }

    #[test]
    fn add() {
        test_expr!("1u + 5", Num::u(6));
        test_expr!("7i4 + 1", Num::i(-8).w(4));
        test_expr!("255 + 2u8", Num::u(1).w(8));
    }

    #[test]
    fn sub() {
        test_expr!("1i - 5", Num::i(-4));
        test_expr!("1u8 - 5", Num::u(252).w(8));
        test_expr!("1i - 5", Num::i(-4));
        test_expr!("1.5 - 0.5", Num::nd(1, 1));
    }

    #[test]
    fn mul() {
        test_expr!("10u * 5", Num::u(50));
        test_expr!("10u8 * 5u4", Num::u(50).w(8));
        test_expr!("10u4 * 5u4", Num::u(50 & 0b1111).w(4));
        test_expr!("10.2 * 10", Num::nd(102, 1));
    }

    #[test]
    fn div() {
        test_expr!("10u / 2", Num::u(5));
        test_expr!("10u / 3", Num::u(3));
        test_expr!("15u4 / 3", Num::u(5).w(4));
        test_expr!("15i5 / -3", Num::i(-5).w(5));
        test_expr!("10 / 3", Num::nd(10, 3));
    }

    #[test]
    fn div_err() {
        test_err!("1 / 0", DivideByZero.span(0, 5).into());
        test_err!("1 + 1/0", DivideByZero.span(4, 7).into());
        test_err!("1 / 16u4", DivideByZero.span(0, 8).into());
    }

    #[test]
    fn rem() {
        test_expr!("10u % 2", Num::u(0));
        test_expr!("10u % 3", Num::u(1));
        test_expr!("10u % -3", Num::u(1));
        test_expr!("-10i % 3", Num::i(-1));
        test_expr!("-10i8 % 3", Num::i(-1).w(8));
        test_expr!("10.5 % 2", Num::nd(1, 2));
    }

    #[test]
    fn rem_err() {
        test_err!("1 % 0", DivideByZero.span(0, 5).into());
        test_err!("1 + 1%0", DivideByZero.span(4, 7).into());
        test_err!("1 % 16u4", DivideByZero.span(0, 8).into());
    }

    #[test]
    fn and() {
        test_expr!("0b1010u & 0b1100", Num::u(0b1000));
        test_expr!("0b1010.1010 & 0b1100.1100", Num::nd(0b1000_1000, 0b1_0000));
    }

    #[test]
    fn or() {
        test_expr!("0b1010 | 0b1100", Num::n(0b1110));
        test_expr!("0b1010.1010 | 0b1100.1100", Num::nd(0b1110_1110, 0b1_0000));
    }

    #[test]
    fn xor() {
        test_expr!("0b1010u ^ 0b1100", Num::u(0b0110));
        test_expr!("0b1010.1010 ^ 0b1100.1100", Num::nd(0b0110_0110, 0b1_0000));
    }

    #[test]
    fn shift_int() {
        // no shift
        test_expr!("0b1100_1001u >> 0", Num::u(0b1100_1001));
        test_expr!("0b1100_1001u << 0", Num::u(0b1100_1001));
        // positive
        test_expr!("0b1100_1001u >> 4", Num::u(0b1100));
        test_expr!("0b1100_1001u << 4", Num::u(0b1100_1001_0000));
        // negative
        test_expr!("0b1100_1001u << -4", Num::u(0b1100));
        test_expr!("0b1100_1001u >> -4", Num::u(0b1100_1001_0000));
    }

    #[test]
    fn shift_fix() {
        test_expr!("0b1100_1001 >> 4", Num::nd(0b1100_1001, 0b1_0000));
        test_expr!("0b1100.1001 << 4", Num::n(0b1100_1001));
    }

    #[test]
    fn shift_non_integer() {
        test_err!("1 >> 0.5", OperandNonInteger.span(0, 8).into());
        test_err!("1 << 1/3", OperandNonInteger.span(0, 8).into());
    }

    #[test]
    fn shift_large() {
        // maximum shift
        test_expr!("0 << 255", Num::n(0));
        test_expr!("0 << -255", Num::n(0));
        test_expr!("0 >> 255", Num::n(0));
        test_expr!("0 >> -255", Num::n(0));
        // above maximum
        test_err!("0 << 256", OperandTooLarge.span(0, 8).into());
        test_err!("0 << -256", OperandTooLarge.span(0, 9).into());
        test_err!("0 >> 256", OperandTooLarge.span(0, 8).into());
        test_err!("0 >> -256", OperandTooLarge.span(0, 9).into());
        // shift above max value
        test_err!("1 << 255", ValueTooLarge.span(0, 8).into());
    }

    #[test]
    fn pow_int() {
        test_expr!("5**0", Num::n(1));
        test_expr!("0**0", Num::n(1));
        test_expr!("5**2", Num::n(25));
    }

    #[test]
    fn pow_fix() {
        test_expr!("5**-2", Num::nd(1, 25));
        test_expr!("5.5**2", Num::nd(121, 4));
        test_expr!("5.5**-2", Num::nd(4, 121));
    }

    #[test]
    fn pow_non_integer() {
        test_err!("5**2.5", OperandNonInteger.span(0, 6).into());
    }

    #[test]
    fn pow_large() {
        test_err!("2**255", ValueTooLarge.span(0, 6).into());
    }

    #[test]
    fn pow_divide_by_zero() {
        test_err!("0**-1", DivideByZero.span(0, 5).into());
    }

    #[test]
    fn name_not_found() {
        test_err!("5 + nonexistent", NameNotFound.span(4, 15).into());
    }
}