submilli_engine/codegen/
bigint_pool.rs

1//! Compile-time pool for large bigint literals (those outside ±2^53 - 1).
2//! Each distinct literal becomes a passive data segment of little-endian u64 limbs;
3//! `BigIntPool::lookup` returns `None` for small literals that skip the pool.
4
5use std::collections::BTreeMap;
6
7use crate::codegen::{internal_failure, wasm_u32};
8use crate::compiler_error::CompilerFailure;
9
10#[derive(Clone, Debug)]
11pub struct BigIntLiteral {
12    /// Dedup key; no `n` suffix or leading sign.
13    pub digits: String,
14    /// Always `1`; negation is applied at runtime.
15    pub sign: i8,
16    pub limbs_le: Vec<u64>,
17}
18
19#[derive(Clone, Copy, Debug)]
20pub struct BigIntEntry {
21    /// Index passed to `array.new_data` for this literal.
22    pub data_idx: u32,
23    pub limb_count: u32,
24    pub sign: i8,
25}
26
27#[derive(Default, Clone, Debug)]
28pub struct BigIntPool {
29    /// Distinct large literals in first-appearance order. Each
30    /// becomes its own passive data segment.
31    pub literals: Vec<BigIntLiteral>,
32    text_to_idx: BTreeMap<String, usize>,
33}
34
35impl BigIntPool {
36    pub(crate) fn intern_digits(&mut self, digits: &str) -> Result<Option<usize>, CompilerFailure> {
37        const SAFE_INTEGER_MAX: u64 = (1u64 << 53) - 1;
38        check_decimal_digits(digits)?;
39        if digits
40            .parse::<u64>()
41            .is_ok_and(|value| value <= SAFE_INTEGER_MAX)
42        {
43            return Ok(None);
44        }
45        if let Some(&existing) = self.text_to_idx.get(digits) {
46            return Ok(Some(existing));
47        }
48        let limbs_le = decimal_to_limbs(digits);
49        let idx = self.literals.len();
50        self.literals.push(BigIntLiteral {
51            digits: digits.to_string(),
52            sign: 1,
53            limbs_le,
54        });
55        self.text_to_idx.insert(digits.to_string(), idx);
56        Ok(Some(idx))
57    }
58
59    /// Returns `None` if the value is within the safe-integer range (wasn't pooled).
60    pub fn lookup(&self, digits: &str) -> Result<Option<BigIntEntry>, CompilerFailure> {
61        let Some(&idx) = self.text_to_idx.get(digits) else {
62            return Ok(None);
63        };
64        let lit = self.literal(idx)?;
65        Ok(Some(BigIntEntry {
66            data_idx: wasm_u32(idx)?,
67            limb_count: wasm_u32(lit.limbs_le.len())?,
68            sign: lit.sign,
69        }))
70    }
71
72    fn literal(&self, idx: usize) -> Result<&BigIntLiteral, CompilerFailure> {
73        self.literals
74            .get(idx)
75            .ok_or_else(|| internal_failure("a bigint literal pool index is out of range"))
76    }
77
78    pub fn is_empty(&self) -> bool {
79        self.literals.is_empty()
80    }
81
82    /// Little-endian byte payload for the literal at `idx` — body of its passive data segment.
83    pub fn le_bytes(&self, idx: usize) -> Result<Vec<u8>, CompilerFailure> {
84        Ok(self
85            .literal(idx)?
86            .limbs_le
87            .iter()
88            .flat_map(|w| w.to_le_bytes())
89            .collect())
90    }
91}
92
93/// The lexer emits sign-free decimal digits; anything else is corrupt typed input.
94fn check_decimal_digits(digits: &str) -> Result<(), CompilerFailure> {
95    if digits.is_empty() || !digits.bytes().all(|byte| byte.is_ascii_digit()) {
96        return Err(internal_failure(
97            "a bigint literal is not a sign-free decimal digit string",
98        ));
99    }
100    Ok(())
101}
102
103// intern_digits validates a nonempty ASCII decimal string before calling; BigUint
104// parsing has no digit/empty-input error for that language and no fixed-width limit.
105fn decimal_to_limbs(digits: &str) -> Vec<u64> {
106    use num_bigint::BigUint;
107    use num_traits::Zero;
108    let value: BigUint = digits
109        .parse()
110        .expect("validated decimal digits parse as BigUint");
111    if value.is_zero() {
112        return Vec::new();
113    }
114    value.to_u64_digits()
115}
116
117#[cfg(test)]
118mod tests {
119    use super::{BigIntPool, decimal_to_limbs};
120    use crate::compiler_error::CompilerFailure;
121
122    #[test]
123    fn small_round_trip() {
124        let limbs = decimal_to_limbs("18446744073709551616");
125        assert_eq!(limbs, vec![0, 1]);
126    }
127
128    #[test]
129    fn one_bit_under_two_limbs() {
130        let limbs = decimal_to_limbs("18446744073709551615");
131        assert_eq!(limbs, vec![u64::MAX]);
132    }
133
134    #[test]
135    fn very_large() {
136        let limbs = decimal_to_limbs("1267650600228229401496703205376");
137        // 2^100 = 2^64 * 2^36 = limb[1] = 2^36, limb[0] = 0.
138        assert_eq!(limbs, vec![0, 1u64 << 36]);
139    }
140
141    #[test]
142    fn corrupt_literals_and_indices_are_internal_failures() {
143        let mut pool = BigIntPool::default();
144        // Signs are never part of the lexer's digits, including `i64::MIN`'s.
145        for digits in ["-9223372036854775808", "", "12a", "+5"] {
146            assert!(
147                matches!(
148                    pool.intern_digits(digits),
149                    Err(CompilerFailure::Internal { .. })
150                ),
151                "{digits:?}"
152            );
153        }
154        assert_eq!(pool.intern_digits("9007199254740991").unwrap(), None);
155        assert_eq!(pool.intern_digits("9007199254740992").unwrap(), Some(0));
156        assert!(pool.lookup("9007199254740992").unwrap().is_some());
157        assert!(pool.lookup("1").unwrap().is_none());
158        assert!(pool.le_bytes(1).is_err());
159        pool.literals.clear();
160        assert!(pool.lookup("9007199254740992").is_err());
161    }
162}
submilli_engine/codegen/bigint_pool.rs

submilli_engine/codegen/
bigint_pool.rs
