clvmr 0.18.0

use crate::error::{EvalErr, Result};
use crate::number::{Malachite, Number, malachite_number_from_u8, number_from_u8};
use chia_bls::{G1Element, G2Element};
use std::borrow::Borrow;
use std::collections::HashSet;
use std::fmt;
use std::hash::Hash;
use std::hash::Hasher;
use std::ops::Deref;

#[cfg(feature = "allocator-debug")]
use rand::RngCore;

#[cfg(feature = "allocator-debug")]
use rand;

const MAX_NUM_ATOMS: usize = 62500000;
const MAX_NUM_PAIRS: usize = 62500000;
const NODE_PTR_IDX_BITS: u32 = 26;
const NODE_PTR_IDX_MASK: u32 = (1 << NODE_PTR_IDX_BITS) - 1;

#[cfg(feature = "allocator-debug")]
#[derive(Clone, Copy)]
struct AllocatorReference {
    fingerprint: u32,
    version: u32,
}

#[cfg(feature = "allocator-debug")]
#[derive(Clone, Copy)]
pub struct NodePtr(u32, AllocatorReference);

#[cfg(feature = "allocator-debug")]
impl Hash for NodePtr {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.0.hash(state);
    }
}

#[cfg(feature = "allocator-debug")]
impl PartialEq for NodePtr {
    fn eq(&self, other: &Self) -> bool {
        if self.1.fingerprint != u32::MAX && other.1.fingerprint != u32::MAX {
            assert_eq!(
                self.1.fingerprint, other.1.fingerprint,
                "NodePtr from different allocators are not allowed be be compared"
            );
        }
        self.0.eq(&other.0)
    }
}

#[cfg(feature = "allocator-debug")]
impl Eq for NodePtr {}

#[cfg(not(feature = "allocator-debug"))]
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct NodePtr(u32);

impl fmt::Debug for NodePtr {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("NodePtr")
            .field(&self.object_type())
            .field(&self.index())
            .finish()
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum ObjectType {
    // The low bits form an index into the pair_vec
    Pair,
    // The low bits form an index into the atom_vec
    Bytes,
    // The low bits are the atom itself (unsigned integer, 26 bits)
    SmallAtom,
}

// The top 6 bits of the NodePtr indicate what type of object it is
impl NodePtr {
    pub const NIL: Self = Self::new(ObjectType::SmallAtom, 0);

    #[cfg(not(feature = "allocator-debug"))]
    const fn new(object_type: ObjectType, index: usize) -> Self {
        debug_assert!(index <= NODE_PTR_IDX_MASK as usize);
        NodePtr(((object_type as u32) << NODE_PTR_IDX_BITS) | (index as u32))
    }

    #[cfg(feature = "allocator-debug")]
    const fn new(object_type: ObjectType, index: usize) -> Self {
        debug_assert!(index <= NODE_PTR_IDX_MASK as usize);
        NodePtr(
            ((object_type as u32) << NODE_PTR_IDX_BITS) | (index as u32),
            AllocatorReference {
                fingerprint: u32::MAX,
                version: 0,
            },
        )
    }

    #[cfg(feature = "allocator-debug")]
    const fn new_debug(object_type: ObjectType, index: usize, ar: AllocatorReference) -> Self {
        debug_assert!(index <= NODE_PTR_IDX_MASK as usize);
        NodePtr(
            ((object_type as u32) << NODE_PTR_IDX_BITS) | (index as u32),
            ar,
        )
    }

    pub fn is_atom(self) -> bool {
        matches!(
            self.object_type(),
            ObjectType::Bytes | ObjectType::SmallAtom
        )
    }

    pub fn is_pair(self) -> bool {
        self.object_type() == ObjectType::Pair
    }

    /// This is an advanced API that exposes implementation details.
    /// Returns the internal representation of this node
    pub fn object_type(self) -> ObjectType {
        match self.0 >> NODE_PTR_IDX_BITS {
            0 => ObjectType::Pair,
            1 => ObjectType::Bytes,
            2 => ObjectType::SmallAtom,
            _ => unreachable!(),
        }
    }

    /// This is an advanced API that exposes implementation details.
    /// Returns a dense index of low numbers for the specific ObjectType
    pub fn index(self) -> u32 {
        self.0 & NODE_PTR_IDX_MASK
    }
}

impl Default for NodePtr {
    fn default() -> Self {
        Self::NIL
    }
}

#[derive(PartialEq, Debug)]
pub enum SExp {
    Atom,
    Pair(NodePtr, NodePtr),
}

#[derive(Clone, Copy, Debug)]
struct AtomBuf {
    start: u32,
    end: u32,
}

impl AtomBuf {
    pub fn len(&self) -> usize {
        (self.end - self.start) as usize
    }
}

#[derive(Clone, Copy, Debug)]
pub struct IntPair {
    first: NodePtr,
    rest: NodePtr,
}

// this represents a specific (former) state of an allocator. This can be used
// to restore an allocator to a previous state. It cannot be used to re-create
// the state from some other allocator.
pub struct Checkpoint {
    inner: TransparentCheckpoint,
    ghost_atoms: usize,
    ghost_pairs: usize,
    ghost_heap: usize,
}

pub struct TransparentCheckpoint {
    u8s: u32,
    pairs: u32,
    atoms: u32,
}

#[derive(Debug, Clone, Copy, Eq, PartialEq)]
pub enum NodeStatus {
    /// The node was created before we took the checkpoint, it will still be
    /// valid after restoring the allocator state to the checkpoint.
    Before,
    /// This node was created after we took the checkpoint. It also refers to
    /// data that was created after the checkpoint. Every aspect of this node will
    /// become invalid after restoring the allocator to the checkpoint.
    AfterNewBytes,
    /// This node was created after the checkpoint, but it's referencing data
    /// from the heap that was allocated before the checkpoint. This is a case
    /// that can happen with substr() on a value from the environment. The node
    /// will become invalid, but the underlying data won't, so we could create a
    /// new node referencing the same data, after restoring the allocator to the
    /// checkpoint.
    AfterOldBytes { start: u32, end: u32 },
}

/// Result of restoring to a transparent checkpoint while considering a return value.
#[derive(Debug)]
pub enum MaybeRestore {
    /// Restore performed; return value unchanged (still valid).
    NoReplace,
    /// Restore performed; caller must replace stack top with this node.
    Replace(NodePtr),
    /// Restore not performed (return value not materializable); checkpoint still valid.
    Aborted,
}

pub enum NodeVisitor<'a> {
    Buffer(&'a [u8]),
    U32(u32),
    Pair(NodePtr, NodePtr),
}

#[derive(Debug, Clone, Copy, Eq)]
pub enum Atom<'a> {
    Borrowed(&'a [u8]),
    U32([u8; 4], usize),
}

impl Hash for Atom<'_> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.as_ref().hash(state)
    }
}

impl PartialEq for Atom<'_> {
    fn eq(&self, other: &Atom) -> bool {
        self.as_ref().eq(other.as_ref())
    }
}

impl AsRef<[u8]> for Atom<'_> {
    fn as_ref(&self) -> &[u8] {
        match self {
            Self::Borrowed(bytes) => bytes,
            Self::U32(bytes, len) => &bytes[4 - len..],
        }
    }
}

impl Deref for Atom<'_> {
    type Target = [u8];

    fn deref(&self) -> &Self::Target {
        self.as_ref()
    }
}

impl Borrow<[u8]> for Atom<'_> {
    fn borrow(&self) -> &[u8] {
        self.as_ref()
    }
}

#[derive(Debug)]
pub struct Allocator {
    // this is effectively a grow-only stack where atoms are allocated. Atoms
    // are immutable, so once they are created, they will stay around until the
    // program completes
    u8_vec: Vec<u8>,

    // storage for all pairs (positive indices)
    pair_vec: Vec<IntPair>,

    // storage for all atoms (negative indices).
    // node index -1 refers to index 0 in this vector, -2 refers to 1 and so
    // on.
    atom_vec: Vec<AtomBuf>,

    // the atom_vec may not grow past this
    heap_limit: usize,

    // the ghost counters are pretend atoms/pairs, that were optimized out. We
    // still account for them to not affect the limits of atoms and pairs. Those
    // limits must stay the same for consensus purpose.
    // For example, a "small atom", which is allocated in-place in the NodePtr.
    ghost_atoms: usize,
    ghost_pairs: usize,
    ghost_heap: usize,

    // these counters track the largest number of allocations. It's used to
    // indicate the memory pressure caused by running a CLVM program. They don't
    // take "ghost" atoms and pairs into account for this reason.
    #[cfg(feature = "counters")]
    max_atom_count: usize,
    #[cfg(feature = "counters")]
    max_pair_count: usize,
    #[cfg(feature = "counters")]
    max_heap_size: usize,

    // Cache of already-validated G1/G2 points, keyed by raw bytes.
    // Using raw bytes instead of NodePtr since NodePtrs can be invalidated
    // by restore_checkpoint() inside softfork guards.
    validated_g1_points: HashSet<[u8; 48]>,
    validated_g2_points: HashSet<[u8; 96]>,

    #[cfg(feature = "allocator-debug")]
    fingerprint: u32,

    // the number of atoms and pairs at different versions
    #[cfg(feature = "allocator-debug")]
    versions: Vec<(u32, u32)>,
}

impl Default for Allocator {
    fn default() -> Self {
        Self::new()
    }
}

pub fn fits_in_small_atom(v: &[u8]) -> Option<u32> {
    if !v.is_empty()
        && (v.len() > 4
        || (v.len() == 1 && v[0] == 0)
        // a 1-byte buffer of 0 is not the canonical representation of 0
        || (v[0] & 0x80) != 0
        // if the top bit is set, it's a negative number (i.e. not positive)
        || (v[0] == 0 && (v[1] & 0x80) == 0)
        // if the buffer is 4 bytes, the top byte can't use more than 2 bits.
        // otherwise the integer won't fit in 26 bits
        || (v.len() == 4 && v[0] > 0x03))
    {
        // if the top byte is a 0 but the top bit of the next byte is not set,
        // that's a redundant leading zero. i.e. not canonical representation
        None
    } else {
        let mut ret: u32 = 0;
        for b in v {
            ret <<= 8;
            ret |= *b as u32;
        }
        Some(ret)
    }
}

pub fn len_for_value(val: u32) -> usize {
    if val == 0 {
        0
    } else if val < 0x80 {
        1
    } else if val < 0x8000 {
        2
    } else if val < 0x800000 {
        3
    } else if val < 0x80000000 {
        4
    } else {
        5
    }
}

impl Allocator {
    pub fn new() -> Self {
        Self::new_limited(u32::MAX as usize)
    }

    pub fn new_limited(heap_limit: usize) -> Self {
        // we have a maximum of 4 GiB heap, because pointers are 32 bit unsigned
        assert!(heap_limit <= u32::MAX as usize);

        let mut r = Self {
            u8_vec: Vec::new(),
            pair_vec: Vec::new(),
            atom_vec: Vec::new(),
            heap_limit,
            // initialize this to 2 to behave as if we had allocated atoms for
            // nil() and one(), like we used to
            ghost_atoms: 2,
            ghost_pairs: 0,
            // compensate for the one() we used to allocate unconditionally
            ghost_heap: 1,
            validated_g1_points: HashSet::new(),
            validated_g2_points: HashSet::new(),
            #[cfg(feature = "counters")]
            max_atom_count: 0,
            #[cfg(feature = "counters")]
            max_pair_count: 0,
            #[cfg(feature = "counters")]
            max_heap_size: 0,

            #[cfg(feature = "allocator-debug")]
            fingerprint: rand::rng().next_u32() & 0x7fffffff,

            #[cfg(feature = "allocator-debug")]
            versions: Vec::new(),
        };
        r.u8_vec.reserve(1024 * 1024);
        r.atom_vec.reserve(256);
        r.pair_vec.reserve(256);
        r
    }

    #[cfg(feature = "allocator-debug")]
    fn validate_node(&self, n: NodePtr) {
        if n.1.fingerprint == u32::MAX {
            assert!(matches!(n.object_type(), ObjectType::SmallAtom));
            return;
        }

        assert_eq!(
            n.1.fingerprint, self.fingerprint,
            "using a NodePtr on the wrong Allocator"
        );
        // if n.1.version is equal to self.versions.len() it means no
        // restore_checkpoint() has been called since this NodePtr was created
        let version = n.1.version as usize;
        if version < self.versions.len() {
            // self.versions contains the number of atoms (.0) and pairs (.1) at
            // the specific version
            match n.object_type() {
                ObjectType::Bytes => {
                    assert!(
                        n.index() < self.versions[version].0,
                        "NodePtr (atom) was invalidated by restore_checkpoint()"
                    );
                }
                ObjectType::Pair => {
                    assert!(
                        n.index() < self.versions[version].1,
                        "NodePtr (pair) was invalidated by restore_checkpoint()"
                    );
                }
                ObjectType::SmallAtom => {}
            }
        }
    }

    #[inline(always)]
    #[cfg(not(feature = "allocator-debug"))]
    fn mk_node(&self, t: ObjectType, idx: usize) -> NodePtr {
        NodePtr::new(t, idx)
    }

    #[inline(always)]
    #[cfg(feature = "allocator-debug")]
    fn mk_node(&self, t: ObjectType, idx: usize) -> NodePtr {
        NodePtr::new_debug(
            t,
            idx,
            AllocatorReference {
                fingerprint: self.fingerprint,
                version: self.versions.len() as u32,
            },
        )
    }

    /// create a checkpoint for the current state of the allocator. This can be
    /// used to go back to an earlier allocator state by passing the Checkpoint
    /// to restore_checkpoint().
    pub fn checkpoint(&self) -> Checkpoint {
        Checkpoint {
            inner: self.transparent_checkpoint(),
            ghost_atoms: self.ghost_atoms,
            ghost_pairs: self.ghost_pairs,
            ghost_heap: self.ghost_heap,
        }
    }

    pub fn restore_checkpoint(&mut self, cp: &Checkpoint) {
        self.restore_transparent_checkpoint(&cp.inner);
        self.ghost_atoms = cp.ghost_atoms;
        self.ghost_pairs = cp.ghost_pairs;
        self.ghost_heap = cp.ghost_heap;
    }

    /// create a checkpoint for the current state of the allocator. This is used
    /// to free all atoms and pairs allocated after this point, without
    /// affecting counters. i.e. as if they are still allocated
    pub fn transparent_checkpoint(&self) -> TransparentCheckpoint {
        TransparentCheckpoint {
            u8s: self.u8_vec.len() as u32,
            pairs: self.pair_vec.len() as u32,
            atoms: self.atom_vec.len() as u32,
        }
    }

    /// A transparent checkpoint works the same as a regular one but it doesn't
    /// restore the counters. The atoms and pair being removed are still counted.
    pub fn restore_transparent_checkpoint(&mut self, cp: &TransparentCheckpoint) {
        // if any of these asserts fire, it means we're trying to restore to
        // a state that has already been "long-jumped" passed (via another
        // restore to an earlier state). You can only restore backwards in time,
        // not forwards.
        assert!(self.u8_vec.len() >= cp.u8s as usize);
        assert!(self.pair_vec.len() >= cp.pairs as usize);
        assert!(self.atom_vec.len() >= cp.atoms as usize);
        self.ghost_heap += self.u8_vec.len() - cp.u8s as usize;
        self.ghost_pairs += self.pair_vec.len() - cp.pairs as usize;
        self.ghost_atoms += self.atom_vec.len() - cp.atoms as usize;
        self.u8_vec.truncate(cp.u8s as usize);
        self.pair_vec.truncate(cp.pairs as usize);
        self.atom_vec.truncate(cp.atoms as usize);

        // This invalidates all NodePtrs with higher index than this, with a
        // lower version than self.versions.len()
        #[cfg(feature = "allocator-debug")]
        self.versions
            .push((self.atom_vec.len() as u32, self.pair_vec.len() as u32));
    }

    /// classify whether a node survives a restore to the checkpoint, and
    /// whether it references bytes allocated before or after that checkpoint.
    pub fn checkpoint_node_status(
        &self,
        checkpoint: &TransparentCheckpoint,
        node: NodePtr,
    ) -> NodeStatus {
        match node.object_type() {
            ObjectType::Pair => {
                if node.index() < checkpoint.pairs {
                    NodeStatus::Before
                } else {
                    NodeStatus::AfterNewBytes
                }
            }
            ObjectType::Bytes => {
                if node.index() < checkpoint.atoms {
                    NodeStatus::Before
                } else {
                    let atom = self.atom_vec[node.index() as usize];
                    if atom.start < checkpoint.u8s {
                        NodeStatus::AfterOldBytes {
                            start: atom.start,
                            end: atom.end,
                        }
                    } else {
                        NodeStatus::AfterNewBytes
                    }
                }
            }
            ObjectType::SmallAtom => NodeStatus::Before,
        }
    }

    /// Attempt to restore the checkpoint, and preserve the value of the /
    /// specified node. If the node was allocated after the checkpoint, it will
    /// be invalidated. Fix up accounting and optionally produce a replacement
    /// node. Caller must replace the value stack top when `Replace(node)` is
    /// returned, If the node is a tree or too large to be restored, the
    /// allocator will not be restored to the checkpoint and Aborted will be
    /// returned.
    pub fn maybe_restore_with_node(
        &mut self,
        checkpoint: &TransparentCheckpoint,
        ret: NodePtr,
    ) -> Result<MaybeRestore> {
        const CLONE_ATOM_LIMIT: usize = 48;
        const MIN_SAVINGS: usize = 1024;

        let saved_bytes = (self.u8_vec.len() - checkpoint.u8s as usize)
            + (self.atom_vec.len() - checkpoint.atoms as usize) * 8
            + (self.pair_vec.len() - checkpoint.pairs as usize) * 8;
        if saved_bytes < MIN_SAVINGS {
            return Ok(MaybeRestore::Aborted);
        }

        match self.checkpoint_node_status(checkpoint, ret) {
            NodeStatus::Before => {
                self.restore_transparent_checkpoint(checkpoint);
                Ok(MaybeRestore::NoReplace)
            }
            NodeStatus::AfterOldBytes { start, end } => {
                self.restore_transparent_checkpoint(checkpoint);
                if self.ghost_atoms == 0 {
                    return Err(EvalErr::InternalError(
                        NodePtr::NIL,
                        "ghost atom accounting error".to_string(),
                    ));
                }
                self.ghost_atoms -= 1;
                if end < start || end as usize > self.u8_vec.len() {
                    return Err(EvalErr::InternalError(
                        self.nil(),
                        "invalid atom byte range".to_string(),
                    ));
                }
                let idx = self.atom_vec.len();
                self.atom_vec.push(AtomBuf { start, end });
                let new_ret = self.mk_node(ObjectType::Bytes, idx);
                Ok(MaybeRestore::Replace(new_ret))
            }
            NodeStatus::AfterNewBytes => {
                let NodeVisitor::Buffer(buf) = self.node(ret) else {
                    return Ok(MaybeRestore::Aborted);
                };

                if buf.len() > CLONE_ATOM_LIMIT {
                    return Ok(MaybeRestore::Aborted);
                }
                let mut saved_bytes = [0u8; CLONE_ATOM_LIMIT];
                let len = buf.len();
                saved_bytes[..len].copy_from_slice(buf);
                self.restore_transparent_checkpoint(checkpoint);
                if self.ghost_atoms == 0 {
                    return Err(EvalErr::InternalError(
                        NodePtr::NIL,
                        "ghost atom accounting error".to_string(),
                    ));
                }
                self.ghost_atoms -= 1;
                if self.ghost_heap < len {
                    return Err(EvalErr::InternalError(
                        NodePtr::NIL,
                        "ghost heap accounting error".to_string(),
                    ));
                }
                self.ghost_heap -= len;
                Ok(MaybeRestore::Replace(self.new_atom(&saved_bytes[..len])?))
            }
        }
    }

    pub fn new_atom(&mut self, v: &[u8]) -> Result<NodePtr> {
        let start = self.u8_vec.len() as u32;
        if start as usize + self.ghost_heap + v.len() > self.heap_limit {
            return Err(EvalErr::OutOfMemory);
        }
        let idx = self.atom_vec.len();
        self.check_atom_limit()?;
        if let Some(ret) = fits_in_small_atom(v) {
            self.ghost_atoms += 1;
            self.ghost_heap += v.len();
            Ok(self.mk_node(ObjectType::SmallAtom, ret as usize))
        } else {
            self.u8_vec.extend_from_slice(v);
            let end = self.u8_vec.len() as u32;
            self.atom_vec.push(AtomBuf { start, end });
            #[cfg(feature = "counters")]
            self.update_max_counts();
            Ok(self.mk_node(ObjectType::Bytes, idx))
        }
    }

    pub fn new_small_number(&mut self, v: u32) -> Result<NodePtr> {
        debug_assert!(v <= NODE_PTR_IDX_MASK);
        let len = len_for_value(v);
        if self.u8_vec.len() + self.ghost_heap + len > self.heap_limit {
            return Err(EvalErr::OutOfMemory);
        }
        self.check_atom_limit()?;
        self.ghost_atoms += 1;
        self.ghost_heap += len;
        Ok(self.mk_node(ObjectType::SmallAtom, v as usize))
    }

    pub fn new_u64(&mut self, val: u64) -> Result<NodePtr> {
        let mut buf = [0u8; 9];
        buf[1..].copy_from_slice(&val.to_be_bytes());
        let start = if val == 0 {
            9
        } else if val < 0x80 {
            8
        } else if val < 0x8000 {
            7
        } else if val < 0x80_0000 {
            6
        } else if val < 0x8000_0000 {
            5
        } else if val < 0x80_0000_0000 {
            4
        } else if val < 0x8000_0000_0000 {
            3
        } else if val < 0x80_0000_0000_0000 {
            2
        } else if val < 0x8000_0000_0000_0000 {
            1
        } else {
            0
        };
        self.new_atom(&buf[start..])
    }

    pub fn new_i64(&mut self, val: i64) -> Result<NodePtr> {
        if val >= 0 {
            return self.new_u64(val as u64);
        }
        let buf = val.to_be_bytes();
        let start = if val >= -0x80 {
            7
        } else if val >= -0x8000 {
            6
        } else if val >= -0x80_0000 {
            5
        } else if val >= -0x8000_0000 {
            4
        } else if val >= -0x80_0000_0000 {
            3
        } else if val >= -0x8000_0000_0000 {
            2
        } else if val >= -0x80_0000_0000_0000 {
            1
        } else {
            0
        };
        self.new_atom(&buf[start..])
    }

    pub fn new_number(&mut self, v: Number) -> Result<NodePtr> {
        use num_traits::ToPrimitive;
        if let Some(val) = v.to_u32()
            && val <= NODE_PTR_IDX_MASK
        {
            return self.new_small_number(val);
        }
        let bytes: Vec<u8> = v.to_signed_bytes_be();
        let mut slice = bytes.as_slice();

        // make number minimal by removing leading zeros
        while (!slice.is_empty()) && (slice[0] == 0) {
            if slice.len() > 1 && (slice[1] & 0x80 == 0x80) {
                break;
            }
            slice = &slice[1..];
        }
        self.new_atom(slice)
    }

    pub fn new_malachite_number(&mut self, v: Malachite) -> Result<NodePtr> {
        use num_traits::ToPrimitive;
        if let Some(val) = v.to_u32()
            && val <= NODE_PTR_IDX_MASK
        {
            return self.new_small_number(val);
        }
        let bytes: Vec<u8> = v.to_signed_bytes_be();
        let mut slice = bytes.as_slice();

        // make number minimal by removing leading zeros
        while (!slice.is_empty()) && (slice[0] == 0) {
            if slice.len() > 1 && (slice[1] & 0x80 == 0x80) {
                break;
            }
            slice = &slice[1..];
        }
        self.new_atom(slice)
    }

    pub fn new_g1(&mut self, g1: G1Element) -> Result<NodePtr> {
        let bytes = g1.to_bytes();
        self.validated_g1_points.insert(bytes);
        self.new_atom(&bytes)
    }

    pub fn new_g2(&mut self, g2: G2Element) -> Result<NodePtr> {
        let bytes = g2.to_bytes();
        self.validated_g2_points.insert(bytes);
        self.new_atom(&bytes)
    }

    pub fn new_pair(&mut self, first: NodePtr, rest: NodePtr) -> Result<NodePtr> {
        #[cfg(feature = "allocator-debug")]
        {
            self.validate_node(first);
            self.validate_node(rest);
        }
        let idx = self.pair_vec.len();
        if idx >= MAX_NUM_PAIRS - self.ghost_pairs {
            return Err(EvalErr::TooManyPairs);
        }
        self.pair_vec.push(IntPair { first, rest });
        #[cfg(feature = "counters")]
        self.update_max_counts();
        Ok(self.mk_node(ObjectType::Pair, idx))
    }

    // this code is used when we are simulating pairs with a vec locally
    // in the deserialize_br code
    // we must maintain parity with the old deserialize_br code so need to track the skipped pairs
    pub fn add_ghost_pair(&mut self, amount: usize) -> Result<()> {
        if MAX_NUM_PAIRS - self.ghost_pairs - self.pair_vec.len() < amount {
            return Err(EvalErr::TooManyPairs);
        }
        self.ghost_pairs += amount;
        Ok(())
    }

    // this code is used when we actually create the pairs that were previously skipped ghost pairs
    pub fn remove_ghost_pair(&mut self, amount: usize) -> Result<()> {
        // currently let this panic with overflow if we go below 0 to debug if/where it happens
        debug_assert!(self.ghost_pairs >= amount);
        self.ghost_pairs -= amount;
        Ok(())
    }

    pub fn add_ghost_atom(&mut self, amount: usize) -> Result<()> {
        if MAX_NUM_ATOMS - self.ghost_atoms - self.atom_vec.len() < amount {
            return Err(EvalErr::TooManyAtoms);
        }
        self.ghost_atoms += amount;
        Ok(())
    }

    pub fn new_substr(&mut self, node: NodePtr, start: u32, end: u32) -> Result<NodePtr> {
        #[cfg(feature = "allocator-debug")]
        self.validate_node(node);

        self.check_atom_limit()?;

        fn bounds_check(node: NodePtr, start: u32, end: u32, len: u32) -> Result<()> {
            if start > len {
                Err(EvalErr::InvalidAllocArg(
                    node,
                    format!("substr start out of bounds: {start} > {len}"),
                ))?;
            }
            if end > len {
                Err(EvalErr::InvalidAllocArg(
                    node,
                    format!("substr end out of bounds: {end} > {len}"),
                ))?;
            }
            if end < start {
                Err(EvalErr::InvalidAllocArg(
                    node,
                    format!("substr invalid bounds: {end} < {start}"),
                ))?;
            }
            Ok(())
        }

        match node.object_type() {
            ObjectType::Pair => Err(EvalErr::InternalError(
                node,
                "substr expected atom, got pair".to_string(),
            ))?,
            ObjectType::Bytes => {
                let atom = self.atom_vec[node.index() as usize];
                let atom_len = atom.end - atom.start;
                bounds_check(node, start, end, atom_len)?;
                let idx = self.atom_vec.len();
                self.atom_vec.push(AtomBuf {
                    start: atom.start + start,
                    end: atom.start + end,
                });
                #[cfg(feature = "counters")]
                self.update_max_counts();
                Ok(self.mk_node(ObjectType::Bytes, idx))
            }
            ObjectType::SmallAtom => {
                let val = node.index();
                let len = len_for_value(val) as u32;
                bounds_check(node, start, end, len)?;
                let buf: [u8; 4] = val.to_be_bytes();
                let buf = &buf[4 - len as usize..];
                let substr = &buf[start as usize..end as usize];
                if let Some(new_val) = fits_in_small_atom(substr) {
                    self.ghost_atoms += 1;
                    Ok(self.mk_node(ObjectType::SmallAtom, new_val as usize))
                } else {
                    let start = self.u8_vec.len();
                    let end = start + substr.len();
                    self.u8_vec.extend_from_slice(substr);
                    let idx = self.atom_vec.len();
                    self.atom_vec.push(AtomBuf {
                        start: start as u32,
                        end: end as u32,
                    });
                    #[cfg(feature = "counters")]
                    self.update_max_counts();
                    Ok(self.mk_node(ObjectType::Bytes, idx))
                }
            }
        }
    }

    pub fn new_concat(&mut self, new_size: usize, nodes: &[NodePtr]) -> Result<NodePtr> {
        #[cfg(feature = "allocator-debug")]
        {
            for n in nodes {
                self.validate_node(*n);
            }
        }

        self.check_atom_limit()?;
        let start = self.u8_vec.len();
        if start + self.ghost_heap + new_size > self.heap_limit {
            return Err(EvalErr::OutOfMemory);
        }

        if nodes.is_empty() {
            if 0 != new_size {
                return Err(EvalErr::InternalError(
                    self.nil(),
                    "concat passed invalid new_size".to_string(),
                ))?;
            }
            // pretend that we created a new atom and allocated new_size bytes on the heap
            self.ghost_atoms += 1;
            return Ok(self.nil());
        }

        if nodes.len() == 1 {
            if self.atom_len(nodes[0]) != new_size {
                return Err(EvalErr::InternalError(
                    self.nil(),
                    "concat passed invalid new_size".to_string(),
                ))?;
            }
            // pretend that we created a new atom and allocated new_size bytes on the heap
            self.ghost_heap += new_size;
            self.ghost_atoms += 1;
            return Ok(nodes[0]);
        }

        self.u8_vec.reserve(new_size);

        let mut counter: usize = 0;
        for node in nodes {
            match node.object_type() {
                ObjectType::Pair => {
                    self.u8_vec.truncate(start);
                    return Err(EvalErr::InternalError(
                        *node,
                        "concat expected atom, got pair".to_string(),
                    ))?;
                }
                ObjectType::Bytes => {
                    let term = self.atom_vec[node.index() as usize];
                    if counter + term.len() > new_size {
                        self.u8_vec.truncate(start);
                        return Err(EvalErr::InternalError(
                            *node,
                            "concat passed invalid new_size".to_string(),
                        ))?;
                    }
                    self.u8_vec
                        .extend_from_within(term.start as usize..term.end as usize);
                    counter += term.len();
                }
                ObjectType::SmallAtom => {
                    let val = node.index();
                    let len = len_for_value(val) as u32;
                    let buf: [u8; 4] = val.to_be_bytes();
                    let buf = &buf[4 - len as usize..];
                    self.u8_vec.extend_from_slice(buf);
                    counter += len as usize;
                }
            }
        }
        if counter != new_size {
            self.u8_vec.truncate(start);
            return Err(EvalErr::InternalError(
                self.nil(),
                "concat passed invalid new_size".to_string(),
            ))?;
        }
        let end = self.u8_vec.len() as u32;
        let idx = self.atom_vec.len();
        self.atom_vec.push(AtomBuf {
            start: start as u32,
            end,
        });
        #[cfg(feature = "counters")]
        self.update_max_counts();
        Ok(self.mk_node(ObjectType::Bytes, idx))
    }

    pub fn atom_eq(&self, lhs: NodePtr, rhs: NodePtr) -> bool {
        #[cfg(feature = "allocator-debug")]
        {
            self.validate_node(lhs);
            self.validate_node(rhs);
        }
        let lhs_type = lhs.object_type();
        let rhs_type = rhs.object_type();

        match (lhs_type, rhs_type) {
            (ObjectType::Pair, _) | (_, ObjectType::Pair) => {
                panic!("atom_eq() called on pair");
            }
            (ObjectType::Bytes, ObjectType::Bytes) => {
                let lhs = self.atom_vec[lhs.index() as usize];
                let rhs = self.atom_vec[rhs.index() as usize];
                self.u8_vec[lhs.start as usize..lhs.end as usize]
                    == self.u8_vec[rhs.start as usize..rhs.end as usize]
            }
            (ObjectType::SmallAtom, ObjectType::SmallAtom) => lhs.index() == rhs.index(),
            (ObjectType::SmallAtom, ObjectType::Bytes) => {
                self.bytes_eq_int(self.atom_vec[rhs.index() as usize], lhs.index())
            }
            (ObjectType::Bytes, ObjectType::SmallAtom) => {
                self.bytes_eq_int(self.atom_vec[lhs.index() as usize], rhs.index())
            }
        }
    }

    fn bytes_eq_int(&self, atom: AtomBuf, val: u32) -> bool {
        let len = len_for_value(val) as u32;
        if (atom.end - atom.start) != len {
            return false;
        }
        if val == 0 {
            return true;
        }

        if self.u8_vec[atom.start as usize] & 0x80 != 0 {
            // SmallAtom only represents positive values
            // if the byte buffer is negative, they can't match
            return false;
        }

        // since we know the value of atom is small, we can turn it into a u32 and compare
        // against val
        let mut atom_val: u32 = 0;
        for i in atom.start..atom.end {
            atom_val <<= 8;
            atom_val |= self.u8_vec[i as usize] as u32;
        }
        val == atom_val
    }

    pub fn atom(&self, node: NodePtr) -> Atom<'_> {
        #[cfg(feature = "allocator-debug")]
        self.validate_node(node);

        let index = node.index();

        match node.object_type() {
            ObjectType::Bytes => {
                let atom = self.atom_vec[index as usize];
                Atom::Borrowed(&self.u8_vec[atom.start as usize..atom.end as usize])
            }
            ObjectType::SmallAtom => {
                let len = len_for_value(index);
                let bytes = index.to_be_bytes();
                Atom::U32(bytes, len)
            }
            _ => panic!("expected atom, got pair"),
        }
    }

    pub fn atom_len(&self, node: NodePtr) -> usize {
        #[cfg(feature = "allocator-debug")]
        self.validate_node(node);

        let index = node.index();

        match node.object_type() {
            ObjectType::Bytes => {
                let atom = self.atom_vec[index as usize];
                (atom.end - atom.start) as usize
            }
            ObjectType::SmallAtom => len_for_value(index),
            _ => {
                panic!("expected atom, got pair");
            }
        }
    }

    pub fn small_number(&self, node: NodePtr) -> Option<u32> {
        #[cfg(feature = "allocator-debug")]
        self.validate_node(node);

        match node.object_type() {
            ObjectType::SmallAtom => Some(node.index()),
            ObjectType::Bytes => {
                let atom = self.atom_vec[node.index() as usize];
                let buf = &self.u8_vec[atom.start as usize..atom.end as usize];
                fits_in_small_atom(buf)
            }
            _ => None,
        }
    }

    pub fn number(&self, node: NodePtr) -> Number {
        #[cfg(feature = "allocator-debug")]
        self.validate_node(node);

        let index = node.index();

        match node.object_type() {
            ObjectType::Bytes => {
                let atom = self.atom_vec[index as usize];
                number_from_u8(&self.u8_vec[atom.start as usize..atom.end as usize])
            }
            ObjectType::SmallAtom => Number::from(index),
            _ => {
                panic!("number() called on pair");
            }
        }
    }

    pub fn malachite_number(&self, node: NodePtr) -> Malachite {
        #[cfg(feature = "allocator-debug")]
        self.validate_node(node);

        let index = node.index();

        match node.object_type() {
            ObjectType::Bytes => {
                let atom = self.atom_vec[index as usize];
                malachite_number_from_u8(&self.u8_vec[atom.start as usize..atom.end as usize])
            }
            ObjectType::SmallAtom => Malachite::from(index),
            _ => {
                panic!("number() called on pair");
            }
        }
    }

    pub fn g1(&self, node: NodePtr) -> Result<G1Element> {
        #[cfg(feature = "allocator-debug")]
        self.validate_node(node);

        let idx = match node.object_type() {
            ObjectType::Bytes => node.index(),
            ObjectType::SmallAtom => {
                return Err(EvalErr::InvalidAllocArg(
                    node,
                    "atom is not G1 size, 48 bytes".to_string(),
                ))?;
            }
            ObjectType::Pair => {
                return Err(EvalErr::InvalidAllocArg(
                    node,
                    "pair found, expected G1 point".to_string(),
                ))?;
            }
        };
        let atom = self.atom_vec[idx as usize];
        if atom.end - atom.start != 48 {
            return Err(EvalErr::InvalidAllocArg(
                node,
                "atom is not G1 size, 48 bytes".to_string(),
            ))?;
        }

        let array: &[u8; 48] = &self.u8_vec[atom.start as usize..atom.end as usize]
            .try_into()
            .map_err(|_| {
                EvalErr::InvalidAllocArg(node, "atom is not G1 size, 48 bytes".to_string())
            })?;
        G1Element::from_bytes(array)
            .map_err(|_| EvalErr::InvalidAllocArg(node, "atom is not a G1 point".to_string()))
    }

    pub fn g2(&self, node: NodePtr) -> Result<G2Element> {
        #[cfg(feature = "allocator-debug")]
        self.validate_node(node);

        let idx = match node.object_type() {
            ObjectType::Bytes => node.index(),
            ObjectType::SmallAtom => {
                return Err(EvalErr::InvalidAllocArg(
                    node,
                    "atom is not G2 size, 96 bytes".to_string(),
                ))?;
            }
            ObjectType::Pair => {
                return Err(EvalErr::InvalidAllocArg(
                    node,
                    "pair found, expected G2 point".to_string(),
                ))?;
            }
        };

        let atom = self.atom_vec[idx as usize];

        let array: &[u8; 96] = &self.u8_vec[atom.start as usize..atom.end as usize]
            .try_into()
            .map_err(|_| {
                EvalErr::InvalidAllocArg(node, "atom is not G2 size, 96 bytes".to_string())
            })?;

        G2Element::from_bytes(array)
            .map_err(|_| EvalErr::InvalidAllocArg(node, "atom is not a G2 point".to_string()))
    }

    pub fn node(&self, node: NodePtr) -> NodeVisitor<'_> {
        #[cfg(feature = "allocator-debug")]
        self.validate_node(node);

        let index = node.index();

        match node.object_type() {
            ObjectType::Bytes => {
                let atom = self.atom_vec[index as usize];
                let buf = &self.u8_vec[atom.start as usize..atom.end as usize];
                NodeVisitor::Buffer(buf)
            }
            ObjectType::SmallAtom => NodeVisitor::U32(index),
            ObjectType::Pair => {
                let pair = self.pair_vec[index as usize];
                NodeVisitor::Pair(pair.first, pair.rest)
            }
        }
    }

    pub fn sexp(&self, node: NodePtr) -> SExp {
        #[cfg(feature = "allocator-debug")]
        self.validate_node(node);

        match node.object_type() {
            ObjectType::Bytes | ObjectType::SmallAtom => SExp::Atom,
            ObjectType::Pair => {
                let pair = self.pair_vec[node.index() as usize];
                SExp::Pair(pair.first, pair.rest)
            }
        }
    }

    // this is meant to be used when iterating lists:
    // while let Some((i, rest)) = a.next(node) {
    //     node = rest;
    //     ...
    // }
    pub fn next(&self, n: NodePtr) -> Option<(NodePtr, NodePtr)> {
        #[cfg(feature = "allocator-debug")]
        self.validate_node(n);

        match self.sexp(n) {
            SExp::Pair(first, rest) => Some((first, rest)),
            SExp::Atom => None,
        }
    }

    pub fn nil(&self) -> NodePtr {
        self.mk_node(ObjectType::SmallAtom, 0)
    }

    pub fn one(&self) -> NodePtr {
        self.mk_node(ObjectType::SmallAtom, 1)
    }

    #[inline]
    fn check_atom_limit(&self) -> Result<()> {
        if self.atom_vec.len() + self.ghost_atoms == MAX_NUM_ATOMS {
            Err(EvalErr::TooManyAtoms)
        } else {
            Ok(())
        }
    }

    pub fn atom_count(&self) -> usize {
        self.atom_vec.len() + self.ghost_atoms
    }

    pub fn allocated_atom_count(&self) -> usize {
        self.atom_vec.len()
    }

    pub fn pair_count(&self) -> usize {
        self.pair_vec.len() + self.ghost_pairs
    }

    pub fn allocated_pair_count(&self) -> usize {
        self.pair_vec.len()
    }

    pub fn heap_size(&self) -> usize {
        self.u8_vec.len() + self.ghost_heap
    }

    pub fn allocated_heap_size(&self) -> usize {
        self.u8_vec.len()
    }

    pub fn validate_g1(&mut self, node: NodePtr, bytes: [u8; 48]) -> Result<()> {
        if !self.validated_g1_points.contains(&bytes) {
            G1Element::from_bytes(&bytes)
                .map_err(|_| EvalErr::InvalidOpArg(node, "atom is not a G1 point".to_string()))?;
            self.validated_g1_points.insert(bytes);
        }
        Ok(())
    }

    pub fn validate_g2(&mut self, node: NodePtr, bytes: [u8; 96]) -> Result<()> {
        if !self.validated_g2_points.contains(&bytes) {
            G2Element::from_bytes(&bytes)
                .map_err(|_| EvalErr::InvalidOpArg(node, "atom is not a G2 point".to_string()))?;
            self.validated_g2_points.insert(bytes);
        }
        Ok(())
    }

    pub fn add_validated_g1(&mut self, bytes: [u8; 48]) {
        self.validated_g1_points.insert(bytes);
    }

    pub fn add_validated_g2(&mut self, bytes: [u8; 96]) {
        self.validated_g2_points.insert(bytes);
    }

    pub fn clear_validation_caches(&mut self) {
        self.validated_g1_points.clear();
        self.validated_g2_points.clear();
    }

    #[cfg(feature = "counters")]
    pub fn max_atom_count(&self) -> usize {
        self.max_atom_count
    }

    #[cfg(feature = "counters")]
    pub fn max_pair_count(&self) -> usize {
        self.max_pair_count
    }

    #[cfg(feature = "counters")]
    pub fn max_heap_size(&self) -> usize {
        self.max_heap_size
    }

    #[cfg(feature = "counters")]
    fn update_max_counts(&mut self) {
        let atom_count = self.atom_vec.len();
        self.max_atom_count = std::cmp::max(self.max_atom_count, atom_count);
        let pair_count = self.pair_vec.len();
        self.max_pair_count = std::cmp::max(self.max_pair_count, pair_count);
        let heap_size = self.u8_vec.len();
        self.max_heap_size = std::cmp::max(self.max_heap_size, heap_size);
    }
}

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

    #[test]
    fn test_atom_eq_1() {
        // these are a bunch of different representations of 1
        // make sure they all compare equal
        let mut a = Allocator::new();
        let a0 = a.one();
        let a1 = a.new_atom(&[1]).unwrap();
        let a2 = {
            let tmp = a.new_atom(&[0x01, 0xff]).unwrap();
            a.new_substr(tmp, 0, 1).unwrap()
        };
        let a3 = a.new_substr(a2, 0, 1).unwrap();
        let a4 = a.new_number(1.into()).unwrap();
        let a5 = a.new_small_number(1).unwrap();

        assert!(a.atom_eq(a0, a0));
        assert!(a.atom_eq(a0, a1));
        assert!(a.atom_eq(a0, a2));
        assert!(a.atom_eq(a0, a3));
        assert!(a.atom_eq(a0, a4));
        assert!(a.atom_eq(a0, a5));

        assert!(a.atom_eq(a1, a0));
        assert!(a.atom_eq(a1, a1));
        assert!(a.atom_eq(a1, a2));
        assert!(a.atom_eq(a1, a3));
        assert!(a.atom_eq(a1, a4));
        assert!(a.atom_eq(a1, a5));

        assert!(a.atom_eq(a2, a0));
        assert!(a.atom_eq(a2, a1));
        assert!(a.atom_eq(a2, a2));
        assert!(a.atom_eq(a2, a3));
        assert!(a.atom_eq(a2, a4));
        assert!(a.atom_eq(a2, a5));

        assert!(a.atom_eq(a3, a0));
        assert!(a.atom_eq(a3, a1));
        assert!(a.atom_eq(a3, a2));
        assert!(a.atom_eq(a3, a3));
        assert!(a.atom_eq(a3, a4));
        assert!(a.atom_eq(a3, a5));

        assert!(a.atom_eq(a4, a0));
        assert!(a.atom_eq(a4, a1));
        assert!(a.atom_eq(a4, a2));
        assert!(a.atom_eq(a4, a3));
        assert!(a.atom_eq(a4, a4));
        assert!(a.atom_eq(a4, a5));

        assert!(a.atom_eq(a5, a0));
        assert!(a.atom_eq(a5, a1));
        assert!(a.atom_eq(a5, a2));
        assert!(a.atom_eq(a5, a3));
        assert!(a.atom_eq(a5, a4));
        assert!(a.atom_eq(a5, a5));
    }

    #[test]
    fn test_atom_eq_minus_1() {
        // these are a bunch of different representations of -1
        // make sure they all compare equal
        let mut a = Allocator::new();
        let a0 = a.new_atom(&[0xff]).unwrap();
        let a1 = a.new_number((-1).into()).unwrap();
        let a2 = {
            let tmp = a.new_atom(&[0x01, 0xff]).unwrap();
            a.new_substr(tmp, 1, 2).unwrap()
        };
        let a3 = a.new_substr(a0, 0, 1).unwrap();

        assert!(a.atom_eq(a0, a0));
        assert!(a.atom_eq(a0, a1));
        assert!(a.atom_eq(a0, a2));
        assert!(a.atom_eq(a0, a3));

        assert!(a.atom_eq(a1, a0));
        assert!(a.atom_eq(a1, a1));
        assert!(a.atom_eq(a1, a2));
        assert!(a.atom_eq(a1, a3));

        assert!(a.atom_eq(a2, a0));
        assert!(a.atom_eq(a2, a1));
        assert!(a.atom_eq(a2, a2));
        assert!(a.atom_eq(a2, a3));

        assert!(a.atom_eq(a3, a0));
        assert!(a.atom_eq(a3, a1));
        assert!(a.atom_eq(a3, a2));
        assert!(a.atom_eq(a3, a3));
    }

    #[test]
    fn test_atom_eq() {
        let mut a = Allocator::new();
        let a0 = a.nil();
        let a1 = a.one();
        let a2 = a.new_atom(&[1]).unwrap();
        let a3 = a.new_atom(&[0xfa, 0xc7]).unwrap();
        let a4 = a.new_small_number(1).unwrap();
        let a5 = a.new_number((-1337).into()).unwrap();

        assert!(a.atom_eq(a0, a0));
        assert!(!a.atom_eq(a0, a1));
        assert!(!a.atom_eq(a0, a2));
        assert!(!a.atom_eq(a0, a3));
        assert!(!a.atom_eq(a0, a4));
        assert!(!a.atom_eq(a0, a5));

        assert!(!a.atom_eq(a1, a0));
        assert!(a.atom_eq(a1, a1));
        assert!(a.atom_eq(a1, a2));
        assert!(!a.atom_eq(a1, a3));
        assert!(a.atom_eq(a1, a4));
        assert!(!a.atom_eq(a1, a5));

        assert!(!a.atom_eq(a2, a0));
        assert!(a.atom_eq(a2, a1));
        assert!(a.atom_eq(a2, a2));
        assert!(!a.atom_eq(a2, a3));
        assert!(a.atom_eq(a2, a4));
        assert!(!a.atom_eq(a2, a5));

        assert!(!a.atom_eq(a3, a0));
        assert!(!a.atom_eq(a3, a1));
        assert!(!a.atom_eq(a3, a2));
        assert!(a.atom_eq(a3, a3));
        assert!(!a.atom_eq(a3, a4));
        assert!(a.atom_eq(a3, a5));

        assert!(!a.atom_eq(a4, a0));
        assert!(a.atom_eq(a4, a1));
        assert!(a.atom_eq(a4, a2));
        assert!(!a.atom_eq(a4, a3));
        assert!(a.atom_eq(a4, a4));
        assert!(!a.atom_eq(a4, a5));
    }

    #[test]
    #[should_panic]
    fn test_atom_eq_pair1() {
        let mut a = Allocator::new();
        let a0 = a.nil();
        let pair = a.new_pair(a0, a0).unwrap();
        a.atom_eq(pair, a0);
    }

    #[test]
    #[should_panic]
    fn test_atom_eq_pair2() {
        let mut a = Allocator::new();
        let a0 = a.nil();
        let pair = a.new_pair(a0, a0).unwrap();
        a.atom_eq(a0, pair);
    }

    #[test]
    #[should_panic]
    fn test_atom_len_pair() {
        let mut a = Allocator::new();
        let a0 = a.nil();
        let pair = a.new_pair(a0, a0).unwrap();
        a.atom_len(pair);
    }

    #[test]
    #[should_panic]
    fn test_number_pair() {
        let mut a = Allocator::new();
        let a0 = a.nil();
        let pair = a.new_pair(a0, a0).unwrap();
        a.number(pair);
    }

    #[test]
    #[should_panic]
    fn test_malachite_number_pair() {
        let mut a = Allocator::new();
        let a0 = a.nil();
        let pair = a.new_pair(a0, a0).unwrap();
        a.malachite_number(pair);
    }

    #[cfg(not(feature = "allocator-debug"))]
    #[test]
    #[should_panic]
    fn test_invalid_node_ptr_type() {
        let node = NodePtr(3 << NODE_PTR_IDX_BITS);
        // unknown NodePtr type
        let _ = node.object_type();
    }

    #[cfg(debug_assertions)]
    #[test]
    #[should_panic]
    fn test_node_ptr_overflow() {
        NodePtr::new(ObjectType::Bytes, NODE_PTR_IDX_MASK as usize + 1);
    }

    #[cfg(debug_assertions)]
    #[test]
    #[should_panic]
    fn test_invalid_small_number() {
        let mut a = Allocator::new();
        a.new_small_number(NODE_PTR_IDX_MASK + 1).unwrap();
    }

    #[rstest]
    #[case(0, 0)]
    #[case(1, 1)]
    #[case(0x7f, 1)]
    #[case(0x80, 2)]
    #[case(0x7fff, 2)]
    #[case(0x7fffff, 3)]
    #[case(0x800000, 4)]
    #[case(0x7fffffff, 4)]
    #[case(0x80000000, 5)]
    #[case(0xffffffff, 5)]
    fn test_len_for_value(#[case] val: u32, #[case] len: usize) {
        assert_eq!(len_for_value(val), len);
    }

    #[test]
    fn test_nil() {
        let a = Allocator::new();
        assert_eq!(a.atom(a.nil()).as_ref(), b"");
        assert_eq!(a.sexp(a.nil()), SExp::Atom);
        assert_eq!(a.nil(), NodePtr::default());
        assert_eq!(a.nil(), NodePtr::NIL);
    }

    #[test]
    fn test_one() {
        let a = Allocator::new();
        assert_eq!(a.atom(a.one()).as_ref(), b"\x01");
        assert_eq!(a.sexp(a.one()), SExp::Atom);
    }

    #[test]
    fn test_allocate_atom() {
        let mut a = Allocator::new();
        let atom = a.new_atom(b"foobar").unwrap();
        assert_eq!(a.atom(atom).as_ref(), b"foobar");
        assert_eq!(a.sexp(atom), SExp::Atom);
    }

    #[test]
    fn test_allocate_pair() {
        let mut a = Allocator::new();
        let atom1 = a.new_atom(b"foo").unwrap();
        let atom2 = a.new_atom(b"bar").unwrap();
        let pair = a.new_pair(atom1, atom2).unwrap();

        assert_eq!(a.sexp(pair), SExp::Pair(atom1, atom2));

        let pair2 = a.new_pair(pair, pair).unwrap();
        assert_eq!(a.sexp(pair2), SExp::Pair(pair, pair));
    }

    #[test]
    fn test_allocate_heap_limit() {
        let mut a = Allocator::new_limited(6);
        // we can't allocate 6 bytes
        assert_eq!(a.new_atom(b"foobar").unwrap_err(), EvalErr::OutOfMemory);
        // but 5 is OK
        let _atom = a.new_atom(b"fooba").unwrap();
    }

    #[test]
    fn test_new_atom_heap_limit() {
        let mut a = Allocator::new_limited(6);
        assert_eq!(a.new_atom(b"foobar").unwrap_err(), EvalErr::OutOfMemory);
        a.new_atom(b"fooba").unwrap();
    }

    #[test]
    fn test_new_atom_small_value_heap_limit() {
        // small-atom-eligible values still count against the heap
        // ghost_heap starts at 1, so with limit=1 there are 0 bytes available
        let mut a = Allocator::new_limited(1);
        assert_eq!(a.new_atom(&[1]).unwrap_err(), EvalErr::OutOfMemory);
    }

    #[test]
    fn test_new_small_number_heap_limit() {
        let mut a = Allocator::new_limited(1);
        assert_eq!(a.new_small_number(1).unwrap_err(), EvalErr::OutOfMemory);
        // len_for_value(0) == 0, so this always fits
        a.new_small_number(0).unwrap();
    }

    #[test]
    fn test_new_number_small_path_heap_limit() {
        let mut a = Allocator::new_limited(1);
        assert_eq!(a.new_number(1.into()).unwrap_err(), EvalErr::OutOfMemory);
    }

    #[test]
    fn test_new_number_large_path_heap_limit() {
        // 0xff_ffff_ffff -> [0, 0xff, 0xff, 0xff, 0xff] = 5 bytes, limit allows 4
        let mut a = Allocator::new_limited(5);
        assert_eq!(
            a.new_number(Number::from(0xffffffffff_u64)).unwrap_err(),
            EvalErr::OutOfMemory
        );
    }

    #[test]
    fn test_new_malachite_number_small_path_heap_limit() {
        let mut a = Allocator::new_limited(1);
        assert_eq!(
            a.new_malachite_number(Malachite::from(1u64)).unwrap_err(),
            EvalErr::OutOfMemory
        );
    }

    #[test]
    fn test_new_malachite_number_large_path_heap_limit() {
        let mut a = Allocator::new_limited(5);
        assert_eq!(
            a.new_malachite_number(Malachite::from(0xffffffffff_u64))
                .unwrap_err(),
            EvalErr::OutOfMemory
        );
    }

    #[test]
    fn test_new_g1_heap_limit() {
        let g1_bytes = hex::decode(VALID_G1).unwrap();
        let g1 = G1Element::from_bytes(g1_bytes.as_slice().try_into().unwrap()).unwrap();
        assert_eq!(
            Allocator::new_limited(48).new_g1(g1).unwrap_err(),
            EvalErr::OutOfMemory
        );
        let g1 = G1Element::from_bytes(g1_bytes.as_slice().try_into().unwrap()).unwrap();
        Allocator::new_limited(49).new_g1(g1).unwrap();
    }

    #[test]
    fn test_new_g2_heap_limit() {
        let g2_bytes = hex::decode(VALID_G2).unwrap();
        let g2 = G2Element::from_bytes(g2_bytes.as_slice().try_into().unwrap()).unwrap();
        assert_eq!(
            Allocator::new_limited(96).new_g2(g2).unwrap_err(),
            EvalErr::OutOfMemory
        );
        let g2 = G2Element::from_bytes(g2_bytes.as_slice().try_into().unwrap()).unwrap();
        Allocator::new_limited(97).new_g2(g2).unwrap();
    }

    #[test]
    fn test_new_concat_heap_limit() {
        let mut a = Allocator::new_limited(5);
        let atom = a.new_atom(&[0x80]).unwrap(); // 1 real heap byte (negative, not a small atom)
        // available: 5 - 1 - 1(ghost) = 3
        assert_eq!(
            a.new_concat(4, &[atom, atom, atom, atom]).unwrap_err(),
            EvalErr::OutOfMemory
        );
        a.new_concat(3, &[atom, atom, atom]).unwrap();
    }

    #[test]
    fn test_allocate_atom_limit() {
        let mut a = Allocator::new();

        for _ in 0..MAX_NUM_ATOMS - 2 {
            // exhaust the number of atoms allowed to be allocated
            let _ = a.new_atom(b"foo").unwrap();
        }
        assert_eq!(a.new_atom(b"foobar").unwrap_err(), EvalErr::TooManyAtoms);
        assert_eq!(a.u8_vec.len(), 0);
        assert_eq!(a.ghost_atoms, MAX_NUM_ATOMS);
    }

    #[test]
    fn test_allocate_small_number_limit() {
        let mut a = Allocator::new();

        for _ in 0..MAX_NUM_ATOMS - 2 {
            // exhaust the number of atoms allowed to be allocated
            let _ = a.new_atom(b"foo").unwrap();
        }
        assert_eq!(a.new_small_number(3).unwrap_err(), EvalErr::TooManyAtoms);
        assert_eq!(a.u8_vec.len(), 0);
        assert_eq!(a.ghost_atoms, MAX_NUM_ATOMS);
    }

    #[test]
    fn test_allocate_substr_limit() {
        let mut a = Allocator::new();

        for _ in 0..MAX_NUM_ATOMS - 3 {
            // exhaust the number of atoms allowed to be allocated
            let _ = a.new_atom(b"foo").unwrap();
        }
        let atom = a.new_atom(b"foo").unwrap();
        assert_eq!(a.new_substr(atom, 1, 2).unwrap_err(), EvalErr::TooManyAtoms);
        assert_eq!(a.u8_vec.len(), 0);
        assert_eq!(a.ghost_atoms, MAX_NUM_ATOMS);
    }

    #[test]
    fn test_allocate_concat_limit() {
        let mut a = Allocator::new();

        for _ in 0..MAX_NUM_ATOMS - 3 {
            // exhaust the number of atoms allowed to be allocated
            let _ = a.new_atom(b"foo").unwrap();
        }
        let atom = a.new_atom(b"foo").unwrap();
        assert_eq!(a.new_concat(3, &[atom]).unwrap_err(), EvalErr::TooManyAtoms);
        assert_eq!(a.u8_vec.len(), 0);
        assert_eq!(a.ghost_atoms, MAX_NUM_ATOMS);
    }

    #[test]
    fn test_allocate_pair_limit() {
        let mut a = Allocator::new();
        let atom = a.new_atom(b"foo").unwrap();
        // one pair is OK
        let _pair1 = a.new_pair(atom, atom).unwrap();
        for _ in 1..MAX_NUM_PAIRS {
            // exhaust the number of pairs allowed to be allocated
            let _ = a.new_pair(atom, atom).unwrap();
        }

        assert_eq!(a.new_pair(atom, atom).unwrap_err(), EvalErr::TooManyPairs);
        assert_eq!(a.add_ghost_pair(1).unwrap_err(), EvalErr::TooManyPairs);
    }

    #[test]
    fn test_ghost_pair_limit() {
        let mut a = Allocator::new();
        let atom = a.new_atom(b"foo").unwrap();
        // one pair is OK
        let _pair1 = a.new_pair(atom, atom).unwrap();
        a.add_ghost_pair(MAX_NUM_PAIRS - 1).unwrap();

        assert_eq!(a.new_pair(atom, atom).unwrap_err(), EvalErr::TooManyPairs);
        assert_eq!(a.add_ghost_pair(1).unwrap_err(), EvalErr::TooManyPairs);
    }

    #[test]
    fn test_transparent_checkpoint() {
        let mut a = Allocator::new();

        let atom1 = a.new_atom(&[4, 3, 2, 1]).unwrap();
        assert!(a.atom(atom1).as_ref() == [4, 3, 2, 1]);

        let checkpoint = a.transparent_checkpoint();

        let atom2 = a.new_atom(&[6, 5, 4, 3]).unwrap();
        let _pair1 = a.new_pair(atom1, atom2).unwrap();
        assert!(a.atom(atom1).as_ref() == [4, 3, 2, 1]);
        assert!(a.atom(atom2).as_ref() == [6, 5, 4, 3]);

        let atom_count_before = a.atom_count();
        let pair_count_before = a.pair_count();

        // at this point we have two atoms and a checkpoint from before the second
        // atom was created

        // now, restoring the checkpoint state will make atom2 disappear

        a.restore_transparent_checkpoint(&checkpoint);

        assert_eq!(a.atom_count(), atom_count_before);
        assert_eq!(a.pair_count(), pair_count_before);

        assert!(a.atom(atom1).as_ref() == [4, 3, 2, 1]);
        let atom3 = a.new_atom(&[6, 5, 4, 3]).unwrap();
        assert!(a.atom(atom3).as_ref() == [6, 5, 4, 3]);

        // since atom2 was removed, atom3 should actually be using that slot
        assert_eq!(atom2, atom3);
    }

    #[test]
    fn test_transparent_checkpoint_contains() {
        let mut a = Allocator::new();

        let atom_before = a.new_atom(b"hello").unwrap();
        let pair_before = a.new_pair(atom_before, atom_before).unwrap();
        let small_before = a.new_small_number(1).unwrap();

        let checkpoint = a.transparent_checkpoint();

        let atom_after_new = a.new_atom(b"world").unwrap();
        let pair_after = a.new_pair(atom_after_new, atom_before).unwrap();
        let small_after = a.new_small_number(2).unwrap();
        let atom_after_old = a.new_substr(atom_before, 0, 5).unwrap();

        assert_eq!(
            a.checkpoint_node_status(&checkpoint, atom_before),
            NodeStatus::Before
        );
        assert_eq!(
            a.checkpoint_node_status(&checkpoint, pair_before),
            NodeStatus::Before
        );
        assert_eq!(
            a.checkpoint_node_status(&checkpoint, small_before),
            NodeStatus::Before
        );
        assert_eq!(
            a.checkpoint_node_status(&checkpoint, small_after),
            NodeStatus::Before
        );
        assert_eq!(
            a.checkpoint_node_status(&checkpoint, atom_after_new),
            NodeStatus::AfterNewBytes
        );
        assert_eq!(
            a.checkpoint_node_status(&checkpoint, pair_after),
            NodeStatus::AfterNewBytes
        );
        assert!(matches!(
            a.checkpoint_node_status(&checkpoint, atom_after_old),
            NodeStatus::AfterOldBytes { .. }
        ));
    }

    fn alloc_filler(a: &mut Allocator) {
        a.new_atom(&[0u8; 1024]).unwrap();
    }

    #[test]
    fn test_restore_node_before_checkpoint() {
        let mut a = Allocator::new();
        let atom1 = a.new_atom(&[4, 3, 2, 1]).unwrap();
        let cp = a.transparent_checkpoint();
        alloc_filler(&mut a);
        let out = a.maybe_restore_with_node(&cp, atom1).unwrap();
        assert!(matches!(out, MaybeRestore::NoReplace));
        assert_eq!(a.atom(atom1).as_ref(), [4, 3, 2, 1]);
    }

    #[test]
    fn test_restore_node_after_old_bytes() {
        let mut a = Allocator::new();
        let atom_hello = a.new_atom(b"hello").unwrap();
        let cp = a.transparent_checkpoint();
        alloc_filler(&mut a);
        let substr = a.new_substr(atom_hello, 0, 5).unwrap();
        assert_eq!(a.atom(substr).as_ref(), b"hello");
        let out = a.maybe_restore_with_node(&cp, substr).unwrap();
        let MaybeRestore::Replace(new_node) = out else {
            panic!("expected Replace");
        };
        assert_eq!(a.atom(new_node).as_ref(), b"hello");
    }

    #[test]
    fn test_restore_node_after_new_bytes() {
        let mut a = Allocator::new();
        let cp = a.transparent_checkpoint();
        alloc_filler(&mut a);
        let atom_x = a.new_atom(b"foobar").unwrap();
        let out = a.maybe_restore_with_node(&cp, atom_x).unwrap();
        let MaybeRestore::Replace(new_node) = out else {
            panic!("expected Replace");
        };
        assert_eq!(a.atom(new_node).as_ref(), b"foobar");
    }

    #[test]
    fn test_restore_aborted_atom_too_large() {
        let mut a = Allocator::new();
        let cp = a.transparent_checkpoint();
        alloc_filler(&mut a);
        let big: Vec<u8> = (0..49).collect();
        let atom_big = a.new_atom(&big).unwrap();
        let out = a.maybe_restore_with_node(&cp, atom_big).unwrap();
        assert!(matches!(out, MaybeRestore::Aborted));
    }

    #[test]
    fn test_restore_aborted_savings_too_small() {
        let mut a = Allocator::new();
        let cp = a.transparent_checkpoint();
        let tiny = a.new_atom(b"x").unwrap();
        let out = a.maybe_restore_with_node(&cp, tiny).unwrap();
        assert!(matches!(out, MaybeRestore::Aborted));
    }

    #[test]
    fn test_substr() {
        let mut a = Allocator::new();
        let atom = a.new_atom(b"foobar").unwrap();
        let pair = a.new_pair(atom, atom).unwrap();

        let sub = a.new_substr(atom, 0, 1).unwrap();
        assert_eq!(a.atom(sub).as_ref(), b"f");
        let sub = a.new_substr(atom, 1, 6).unwrap();
        assert_eq!(a.atom(sub).as_ref(), b"oobar");
        let sub = a.new_substr(atom, 1, 1).unwrap();
        assert_eq!(a.atom(sub).as_ref(), b"");
        let sub = a.new_substr(atom, 0, 0).unwrap();
        assert_eq!(a.atom(sub).as_ref(), b"");

        assert!(matches!(
            a.new_substr(atom, 1, 0).unwrap_err(),
            EvalErr::InvalidAllocArg(
                _,
                ref msg
            ) if *msg == format!("substr invalid bounds: {1} < {0}", 1, 0)
        ));
        assert!(matches!(
            a.new_substr(atom, 7, 7).unwrap_err(),
            EvalErr::InvalidAllocArg(
                _,
                ref msg
            ) if *msg == format!("substr start out of bounds: {0} > {1}", 7, 6)
        ));
        assert!(matches!(
            a.new_substr(atom, 0, 7).unwrap_err(),
            EvalErr::InvalidAllocArg(
                _,
                ref msg
            ) if *msg == format!("substr end out of bounds: {0} > {1}", 7, 6)
        ));
        assert!(matches!(
            a.new_substr(atom, u32::MAX, 4).unwrap_err(),
            EvalErr::InvalidAllocArg(
                _,
                ref msg
            ) if *msg == format!("substr start out of bounds: {0} > {1}", u32::MAX, 6)
        ));
        assert!(matches!(
            a.new_substr(pair, 0, 0).unwrap_err(),
            EvalErr::InternalError(_, ref msg) if msg == "substr expected atom, got pair"
        ));
    }

    #[test]
    fn test_substr_small_number() {
        let mut a = Allocator::new();
        let atom = a.new_atom(b"a\x80").unwrap();
        assert!(a.small_number(atom).is_some());

        let sub = a.new_substr(atom, 0, 1).unwrap();
        assert_eq!(a.atom(sub).as_ref(), b"a");
        assert!(a.small_number(sub).is_some());
        let sub = a.new_substr(atom, 1, 2).unwrap();
        assert_eq!(a.atom(sub).as_ref(), b"\x80");
        assert!(a.small_number(sub).is_none());
        let sub = a.new_substr(atom, 1, 1).unwrap();
        assert_eq!(a.atom(sub).as_ref(), b"");
        let sub = a.new_substr(atom, 0, 0).unwrap();
        assert_eq!(a.atom(sub).as_ref(), b"");

        assert_eq!(
            a.new_substr(atom, 1, 0).unwrap_err(),
            EvalErr::InvalidAllocArg(atom, format!("substr invalid bounds: {1} < {0}", 1, 0))
        );
        assert!(matches!(
            a.new_substr(atom, 3, 3).unwrap_err(),
            EvalErr::InvalidAllocArg(
                _,
            ref msg) if *msg == format!("substr start out of bounds: {0} > {1}", 3,2 )

        ));
        assert!(matches!(
            a.new_substr(atom, 0, 3).unwrap_err(),
            EvalErr::InvalidAllocArg(
                _,
                ref msg ) if *msg == format!("substr end out of bounds: {1} > {0}", 2,3)

        ));
        println!("{}", a.new_substr(atom, u32::MAX, 2).unwrap_err());
        assert!(matches!(
            a.new_substr(atom, u32::MAX, 2).unwrap_err(),
            EvalErr::InvalidAllocArg(_, ref msg) if *msg ==  format!(
                    "substr start out of bounds: {0} > {1}",
                    u32::MAX,
                    2
                )
        ));
    }

    #[test]
    fn test_concat_launder_small_number() {
        let mut a = Allocator::new();
        let atom1 = a.new_small_number(42).expect("new_small_number");
        assert_eq!(a.small_number(atom1), Some(42));

        // this "launders" the small number into actually being allocated on the
        // heap
        let atom2 = a
            .new_concat(1, &[a.nil(), atom1, a.nil()])
            .expect("new_substr");

        // even though this atom is allocated on the heap (and not stored as a small
        // int), we can still retrieve it as one. The CLVM interpreter depends on
        // this when matching operators against quote, apply and softfork.
        assert_eq!(a.small_number(atom2), Some(42));
        assert_eq!(a.atom_len(atom2), 1);
        assert_eq!(a.atom(atom2).as_ref(), &[42]);
    }

    #[test]
    fn test_concat() {
        let mut a = Allocator::new();
        let atom1 = a.new_atom(b"f").unwrap();
        let atom2 = a.new_atom(b"o").unwrap();
        let atom3 = a.new_atom(b"o").unwrap();
        let atom4 = a.new_atom(b"b").unwrap();
        let atom5 = a.new_atom(b"a").unwrap();
        let atom6 = a.new_atom(b"r").unwrap();
        let pair = a.new_pair(atom1, atom2).unwrap();

        let cat = a
            .new_concat(6, &[atom1, atom2, atom3, atom4, atom5, atom6])
            .unwrap();
        assert_eq!(a.atom(cat).as_ref(), b"foobar");

        let cat = a.new_concat(12, &[cat, cat]).unwrap();
        assert_eq!(a.atom(cat).as_ref(), b"foobarfoobar");

        assert!(matches!(
            a.new_concat(11, &[cat, cat]).unwrap_err(),
            EvalErr::InternalError(_, ref msg) if msg == "concat passed invalid new_size"
        ));
        assert!(matches!(
            a.new_concat(13, &[cat, cat]).unwrap_err(),
            EvalErr::InternalError(_, ref msg) if msg == "concat passed invalid new_size"
        ));
        assert!(matches!(
            a.new_concat(12, &[atom3, pair]).unwrap_err(),
            EvalErr::InternalError(_, ref msg) if msg == "concat expected atom, got pair"
        ));

        assert!(matches!(
            a.new_concat(4, &[atom1, atom2, atom3]).unwrap_err(),
            EvalErr::InternalError(_, ref msg) if msg == "concat passed invalid new_size"
        ));

        assert!(matches!(
            a.new_concat(2, &[atom1, atom2, atom3]).unwrap_err(),
            EvalErr::InternalError(_, ref msg) if msg == "concat passed invalid new_size"
        ));

        assert!(matches!(
            a.new_concat(2, &[atom3]).unwrap_err(),
            EvalErr::InternalError(_, ref msg) if msg == "concat passed invalid new_size"
        ));
        assert!(matches!(
            a.new_concat(1, &[]).unwrap_err(),
            EvalErr::InternalError(_, ref msg) if msg == "concat passed invalid new_size"
        ));

        assert_eq!(a.new_concat(0, &[]).unwrap(), NodePtr::NIL);
        assert_eq!(a.new_concat(1, &[atom1]).unwrap(), atom1);
    }

    #[test]
    fn test_concat_large() {
        let mut a = Allocator::new();
        let atom1 = a.new_atom(b"foo").unwrap();
        let atom2 = a.new_atom(b"bar").unwrap();
        let pair = a.new_pair(atom1, atom2).unwrap();

        let cat = a.new_concat(6, &[atom1, atom2]).unwrap();
        assert_eq!(a.atom(cat).as_ref(), b"foobar");

        let cat = a.new_concat(12, &[cat, cat]).unwrap();
        assert_eq!(a.atom(cat).as_ref(), b"foobarfoobar");

        assert!(matches!(
            a.new_concat(11, &[cat, cat]).unwrap_err(),
            EvalErr::InternalError(_, ref msg) if msg == "concat passed invalid new_size"
        ));
        assert!(matches!(
            a.new_concat(13, &[cat, cat]).unwrap_err(),
            EvalErr::InternalError(_, ref msg) if msg == "concat passed invalid new_size"
        ));
        assert!(matches!(
            a.new_concat(12, &[atom1, pair]).unwrap_err(),
            EvalErr::InternalError(_, ref msg) if msg == "concat expected atom, got pair"

        ));

        assert!(matches!(
            a.new_concat(4, &[atom1, atom2]).unwrap_err(),
            EvalErr::InternalError(_, ref msg) if msg == "concat passed invalid new_size"
        ));

        assert!(matches!(
            a.new_concat(2, &[atom1, atom2]).unwrap_err(),
            EvalErr::InternalError(_, ref msg) if msg == "concat passed invalid new_size"
        ));
    }

    #[test]
    fn test_sexp() {
        let mut a = Allocator::new();
        let atom1 = a.new_atom(b"f").unwrap();
        let atom2 = a.new_atom(b"o").unwrap();
        let pair = a.new_pair(atom1, atom2).unwrap();

        assert_eq!(a.sexp(atom1), SExp::Atom);
        assert_eq!(a.sexp(atom2), SExp::Atom);
        assert_eq!(a.sexp(pair), SExp::Pair(atom1, atom2));
    }

    #[test]
    fn test_concat_limit() {
        // the Allocator::one() is always allocated and uses 1 byte of heap
        let mut a = Allocator::new_limited(9);
        let atom1 = a.new_atom(b"f").unwrap();
        let atom2 = a.new_atom(b"o").unwrap();
        let atom3 = a.new_atom(b"o").unwrap();
        let atom4 = a.new_atom(b"b").unwrap();
        let atom5 = a.new_atom(b"a").unwrap();
        let atom6 = a.new_atom(b"r").unwrap();

        // we only have 2 bytes left of allowed heap allocation
        assert_eq!(
            a.new_concat(6, &[atom1, atom2, atom3, atom4, atom5, atom6])
                .unwrap_err(),
            EvalErr::OutOfMemory
        );
        let cat = a.new_concat(2, &[atom1, atom2]).unwrap();
        assert_eq!(a.atom(cat).as_ref(), b"fo");
    }

    #[rstest]
    #[case(0.into(), &[])]
    #[case(1.into(), &[1])]
    #[case((-1).into(), &[0xff])]
    #[case(0x80.into(), &[0, 0x80])]
    #[case(0xff.into(), &[0, 0xff])]
    #[case(0xffffffff_u64.into(), &[0, 0xff, 0xff, 0xff, 0xff])]
    fn test_new_number(#[case] num: Number, #[case] expected: &[u8]) {
        let mut a = Allocator::new();

        // TEST creating the atom from a Number
        let atom = a.new_number(num.clone()).unwrap();

        // make sure we get back the same number
        assert_eq!(a.number(atom), num);
        assert_eq!(a.atom(atom).as_ref(), expected);
        assert_eq!(number_from_u8(expected), num);

        // TEST creating the atom from a buffer
        let atom = a.new_atom(expected).unwrap();

        // make sure we get back the same number
        assert_eq!(a.number(atom), num);
        assert_eq!(a.atom(atom).as_ref(), expected);
        assert_eq!(number_from_u8(expected), num);
    }

    #[rstest]
    #[case(Malachite::from(0u64), &[])]
    #[case(Malachite::from(1u64), &[1])]
    #[case(Malachite::from(-1i64), &[0xff])]
    #[case(Malachite::from(0x80u64), &[0, 0x80])]
    #[case(Malachite::from(0xffu64), &[0, 0xff])]
    #[case(Malachite::from(0xffffffff_u64), &[0, 0xff, 0xff, 0xff, 0xff])]
    fn test_new_malachite_number(#[case] num: Malachite, #[case] expected: &[u8]) {
        let mut a = Allocator::new();

        let atom = a.new_malachite_number(num.clone()).unwrap();

        assert_eq!(a.malachite_number(atom), num);
        assert_eq!(a.atom(atom).as_ref(), expected);
        assert_eq!(malachite_number_from_u8(expected), num);

        let atom = a.new_atom(expected).unwrap();

        assert_eq!(a.malachite_number(atom), num);
        assert_eq!(a.atom(atom).as_ref(), expected);
        assert_eq!(malachite_number_from_u8(expected), num);
    }

    #[test]
    fn test_checkpoints() {
        let mut a = Allocator::new();

        let atom1 = a.new_atom(&[4, 3, 2, 1]).unwrap();
        assert!(a.atom(atom1).as_ref() == [4, 3, 2, 1]);

        let checkpoint = a.checkpoint();

        let atom2 = a.new_atom(&[6, 5, 4, 3]).unwrap();
        let _pair1 = a.new_pair(atom1, atom2).unwrap();
        assert!(a.atom(atom1).as_ref() == [4, 3, 2, 1]);
        assert!(a.atom(atom2).as_ref() == [6, 5, 4, 3]);

        #[cfg(feature = "counters")]
        let prev_counters = (a.max_atom_count(), a.max_pair_count(), a.max_heap_size());

        // at this point we have two atoms and a checkpoint from before the second
        // atom was created

        // now, restoring the checkpoint state will make atom2 disappear

        a.restore_checkpoint(&checkpoint);

        #[cfg(feature = "counters")]
        assert_eq!(
            (a.max_atom_count(), a.max_pair_count(), a.max_heap_size()),
            prev_counters
        );

        assert!(a.atom(atom1).as_ref() == [4, 3, 2, 1]);
        let atom3 = a.new_atom(&[6, 5, 4, 3]).unwrap();
        assert!(a.atom(atom3).as_ref() == [6, 5, 4, 3]);

        // since atom2 was removed, atom3 should actually be using that slot
        assert_eq!(atom2, atom3);
    }

    fn test_g1(a: &Allocator, n: NodePtr) -> EvalErr {
        a.g1(n).unwrap_err()
    }

    fn test_g2(a: &Allocator, n: NodePtr) -> EvalErr {
        a.g2(n).unwrap_err()
    }

    type TestFun = fn(&Allocator, NodePtr) -> EvalErr;

    #[rstest]
    #[case(test_g1, 0, "atom is not G1 size, 48 bytes")]
    #[case(test_g1, 3, "atom is not G1 size, 48 bytes")]
    #[case(test_g1, 47, "atom is not G1 size, 48 bytes")]
    #[case(test_g1, 49, "atom is not G1 size, 48 bytes")]
    #[case(test_g1, 48, "atom is not a G1 point")]
    #[case(test_g2, 0, "atom is not G2 size, 96 bytes")]
    #[case(test_g2, 3, "atom is not G2 size, 96 bytes")]
    #[case(test_g2, 95, "atom is not G2 size, 96 bytes")]
    #[case(test_g2, 97, "atom is not G2 size, 96 bytes")]
    #[case(test_g2, 96, "atom is not a G2 point")]
    fn test_point_size_error(#[case] fun: TestFun, #[case] size: usize, #[case] expected: &str) {
        let mut a = Allocator::new();
        let mut buf = Vec::<u8>::new();
        buf.resize(size, 0xcc);
        let n = a.new_atom(&buf).unwrap();
        let r = fun(&a, n);
        assert_eq!(r.to_string(), format!("InvalidAllocatorArg: {expected}"));
    }

    #[rstest]
    #[case(test_g1, "pair found, expected G1 point")]
    #[case(test_g2, "pair found, expected G2 point")]
    fn test_point_atom_pair(#[case] fun: TestFun, #[case] expected: &str) {
        let mut a = Allocator::new();
        let n = a.new_pair(a.nil(), a.one()).unwrap();
        let r = fun(&a, n);
        assert_eq!(r.to_string(), format!("InvalidAllocatorArg: {expected}"));
    }

    #[rstest]
    #[case(
        "\
97f1d3a73197d7942695638c4fa9ac0f\
c3688c4f9774b905a14e3a3f171bac58\
6c55e83ff97a1aeffb3af00adb22c6bb"
    )]
    #[case(
        "\
a572cbea904d67468808c8eb50a9450c\
9721db309128012543902d0ac358a62a\
e28f75bb8f1c7c42c39a8c5529bf0f4e"
    )]
    fn test_g1_roundtrip(#[case] atom: &str) {
        let mut a = Allocator::new();
        let n = a.new_atom(&hex::decode(atom).unwrap()).unwrap();
        let g1 = a.g1(n).unwrap();
        assert_eq!(hex::encode(g1.to_bytes()), atom);

        let g1_copy = a.new_g1(g1).unwrap();
        let g1_atom = a.atom(g1_copy);
        assert_eq!(hex::encode(g1_atom), atom);

        // try interpreting the point as G1
        assert!(matches!(
            a.g2(n).unwrap_err(),
            EvalErr::InvalidAllocArg(_, msg) if msg == "atom is not G2 size, 96 bytes"
        ));
        assert!(matches!(
            a.g2(g1_copy).unwrap_err(),
            EvalErr::InvalidAllocArg(_, msg) if msg == "atom is not G2 size, 96 bytes"
        ));

        // try interpreting the point as number
        assert_eq!(a.number(n), number_from_u8(&hex::decode(atom).unwrap()));
        assert_eq!(
            a.number(g1_copy),
            number_from_u8(&hex::decode(atom).unwrap())
        );
    }

    #[rstest]
    #[case(
        "\
93e02b6052719f607dacd3a088274f65\
596bd0d09920b61ab5da61bbdc7f5049\
334cf11213945d57e5ac7d055d042b7e\
024aa2b2f08f0a91260805272dc51051\
c6e47ad4fa403b02b4510b647ae3d177\
0bac0326a805bbefd48056c8c121bdb8"
    )]
    #[case(
        "\
aa4edef9c1ed7f729f520e47730a124f\
d70662a904ba1074728114d1031e1572\
c6c886f6b57ec72a6178288c47c33577\
1638533957d540a9d2370f17cc7ed586\
3bc0b995b8825e0ee1ea1e1e4d00dbae\
81f14b0bf3611b78c952aacab827a053"
    )]
    fn test_g2_roundtrip(#[case] atom: &str) {
        let mut a = Allocator::new();
        let n = a.new_atom(&hex::decode(atom).unwrap()).unwrap();
        let g2 = a.g2(n).unwrap();
        assert_eq!(hex::encode(g2.to_bytes()), atom);

        let g2_copy = a.new_g2(g2).unwrap();
        let g2_atom = a.atom(g2_copy);
        assert_eq!(hex::encode(g2_atom), atom);

        // try interpreting the point as G1
        assert!(matches!(
            a.g1(n).unwrap_err(),
            EvalErr::InvalidAllocArg(_, msg) if msg == "atom is not G1 size, 48 bytes"
        ));
        assert!(matches!(
            a.g1(g2_copy).unwrap_err(),
            EvalErr::InvalidAllocArg(_, msg) if msg == "atom is not G1 size, 48 bytes"
        ));

        // try interpreting the point as number
        assert_eq!(a.number(n), number_from_u8(&hex::decode(atom).unwrap()));
        assert_eq!(
            a.number(g2_copy),
            number_from_u8(&hex::decode(atom).unwrap())
        );
    }

    type MakeFun = fn(&mut Allocator, &[u8]) -> NodePtr;

    fn make_buf(a: &mut Allocator, bytes: &[u8]) -> NodePtr {
        a.new_atom(bytes).unwrap()
    }

    fn make_number(a: &mut Allocator, bytes: &[u8]) -> NodePtr {
        let v = number_from_u8(bytes);
        a.new_number(v).unwrap()
    }

    fn make_g1(a: &mut Allocator, bytes: &[u8]) -> NodePtr {
        let v = G1Element::from_bytes(bytes.try_into().unwrap()).unwrap();
        a.new_g1(v).unwrap()
    }

    fn make_g2(a: &mut Allocator, bytes: &[u8]) -> NodePtr {
        let v = G2Element::from_bytes(bytes.try_into().unwrap()).unwrap();
        a.new_g2(v).unwrap()
    }

    fn make_g1_fail(a: &mut Allocator, bytes: &[u8]) -> NodePtr {
        assert!(<[u8; 48]>::try_from(bytes).is_err());
        a.new_atom(bytes).unwrap()
    }

    fn make_g2_fail(a: &mut Allocator, bytes: &[u8]) -> NodePtr {
        assert!(<[u8; 96]>::try_from(bytes).is_err());
        a.new_atom(bytes).unwrap()
    }

    type CheckFun = fn(&Allocator, NodePtr, &[u8]);

    fn check_buf(a: &Allocator, n: NodePtr, bytes: &[u8]) {
        let buf = a.atom(n);
        assert_eq!(buf.as_ref(), bytes);
    }

    fn check_number(a: &Allocator, n: NodePtr, bytes: &[u8]) {
        let num = a.number(n);
        let v = number_from_u8(bytes);
        assert_eq!(num, v);
    }

    fn check_g1(a: &Allocator, n: NodePtr, bytes: &[u8]) {
        let num = a.g1(n).unwrap();
        let v = G1Element::from_bytes(bytes.try_into().unwrap()).unwrap();
        assert_eq!(num, v);
    }

    fn check_g2(a: &Allocator, n: NodePtr, bytes: &[u8]) {
        let num = a.g2(n).unwrap();
        let v = G2Element::from_bytes(bytes.try_into().unwrap()).unwrap();
        assert_eq!(num, v);
    }

    fn check_g1_fail(a: &Allocator, n: NodePtr, bytes: &[u8]) {
        assert_eq!(a.g1(n).unwrap_err().node_ptr(), n);
        assert!(<[u8; 48]>::try_from(bytes).is_err());
    }

    fn check_g2_fail(a: &Allocator, n: NodePtr, bytes: &[u8]) {
        assert_eq!(a.g2(n).unwrap_err().node_ptr(), n);
        assert!(<[u8; 96]>::try_from(bytes).is_err());
    }

    const EMPTY: &str = "";

    const SMALL_BUF: &str = "133742";

    const VALID_G1: &str = "\
a572cbea904d67468808c8eb50a9450c\
9721db309128012543902d0ac358a62a\
e28f75bb8f1c7c42c39a8c5529bf0f4e";

    const VALID_G2: &str = "\
aa4edef9c1ed7f729f520e47730a124f\
d70662a904ba1074728114d1031e1572\
c6c886f6b57ec72a6178288c47c33577\
1638533957d540a9d2370f17cc7ed586\
3bc0b995b8825e0ee1ea1e1e4d00dbae\
81f14b0bf3611b78c952aacab827a053";

    /*
      We want to exercise round-tripping avery kind of value via every other kind
      of value (as far as possible). e.g. Every value can round-trip through a byte buffer
      or a number, but G1 cannot round-trip via G2.

      +-----------+--------+--------+------+------+
      | from / to | buffer | number | G1   | G2   |
      +-----------+--------+--------+------+------+
      | buffer    | o      | o      | -    | -    |
      | number    | o      | o      | -    | -    |
      | G1        | o      | o      | o    | -    |
      | G2        | o      | o      | -    | o    |
      +-----------+--------+--------+------+------+

    */

    #[rstest]
    // round trip empty buffer
    #[case(EMPTY, make_buf, check_buf)]
    #[case(EMPTY, make_buf, check_number)]
    #[case(EMPTY, make_buf, check_g1_fail)]
    #[case(EMPTY, make_buf, check_g2_fail)]
    #[case(EMPTY, make_number, check_buf)]
    #[case(EMPTY, make_number, check_number)]
    #[case(EMPTY, make_number, check_g1_fail)]
    #[case(EMPTY, make_number, check_g2_fail)]
    #[case(EMPTY, make_g1_fail, check_buf)]
    #[case(EMPTY, make_g1_fail, check_number)]
    #[case(EMPTY, make_g1_fail, check_g1_fail)]
    #[case(EMPTY, make_g1_fail, check_g2_fail)]
    #[case(EMPTY, make_g2_fail, check_buf)]
    #[case(EMPTY, make_g2_fail, check_number)]
    #[case(EMPTY, make_g2_fail, check_g1_fail)]
    #[case(EMPTY, make_g2_fail, check_g2_fail)]
    // round trip small buffer
    #[case(SMALL_BUF, make_buf, check_buf)]
    #[case(SMALL_BUF, make_buf, check_number)]
    #[case(SMALL_BUF, make_buf, check_g1_fail)]
    #[case(SMALL_BUF, make_buf, check_g2_fail)]
    #[case(SMALL_BUF, make_number, check_buf)]
    #[case(SMALL_BUF, make_number, check_number)]
    #[case(SMALL_BUF, make_number, check_g1_fail)]
    #[case(SMALL_BUF, make_number, check_g2_fail)]
    #[case(SMALL_BUF, make_g1_fail, check_buf)]
    #[case(SMALL_BUF, make_g1_fail, check_number)]
    #[case(SMALL_BUF, make_g1_fail, check_g1_fail)]
    #[case(SMALL_BUF, make_g1_fail, check_g2_fail)]
    #[case(SMALL_BUF, make_g2_fail, check_buf)]
    #[case(SMALL_BUF, make_g2_fail, check_number)]
    #[case(SMALL_BUF, make_g2_fail, check_g1_fail)]
    #[case(SMALL_BUF, make_g2_fail, check_g2_fail)]
    // round trip G1 point
    #[case(VALID_G1, make_buf, check_buf)]
    #[case(VALID_G1, make_buf, check_number)]
    #[case(VALID_G1, make_buf, check_g1)]
    #[case(VALID_G1, make_buf, check_g2_fail)]
    #[case(VALID_G1, make_number, check_buf)]
    #[case(VALID_G1, make_number, check_number)]
    #[case(VALID_G1, make_number, check_g1)]
    #[case(VALID_G1, make_number, check_g2_fail)]
    #[case(VALID_G1, make_g1, check_buf)]
    #[case(VALID_G1, make_g1, check_number)]
    #[case(VALID_G1, make_g1, check_g1)]
    #[case(VALID_G1, make_g1, check_g2_fail)]
    #[case(VALID_G1, make_g2_fail, check_buf)]
    #[case(VALID_G1, make_g2_fail, check_number)]
    #[case(VALID_G1, make_g2_fail, check_g1)]
    #[case(VALID_G1, make_g2_fail, check_g2_fail)]
    // round trip G2 point
    #[case(VALID_G2, make_buf, check_buf)]
    #[case(VALID_G2, make_buf, check_number)]
    #[case(VALID_G2, make_buf, check_g1_fail)]
    #[case(VALID_G2, make_buf, check_g2)]
    #[case(VALID_G2, make_number, check_buf)]
    #[case(VALID_G2, make_number, check_number)]
    #[case(VALID_G2, make_number, check_g1_fail)]
    #[case(VALID_G2, make_number, check_g2)]
    #[case(VALID_G2, make_g1_fail, check_buf)]
    #[case(VALID_G2, make_g1_fail, check_number)]
    #[case(VALID_G2, make_g1_fail, check_g1_fail)]
    #[case(VALID_G2, make_g1_fail, check_g2)]
    #[case(VALID_G2, make_g2, check_buf)]
    #[case(VALID_G2, make_g2, check_number)]
    #[case(VALID_G2, make_g2, check_g1_fail)]
    #[case(VALID_G2, make_g2, check_g2)]
    fn test_roundtrip(#[case] test_value: &str, #[case] make: MakeFun, #[case] check: CheckFun) {
        let value = hex::decode(test_value).unwrap();
        let mut a = Allocator::new();
        let node = make(&mut a, &value);
        check(&a, node, &value);
    }

    #[rstest]
    #[case(&[], 0)]
    #[case(&[1], 1)]
    #[case(&[1,2], 2)]
    #[case(&[1,2,3,4,5,6,7,8,9], 9)]
    #[case(&[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18], 18)]
    fn test_atom_len(#[case] buf: &[u8], #[case] expected: usize) {
        let mut a = Allocator::new();
        let atom = a.new_atom(buf).unwrap();
        assert_eq!(a.atom_len(atom), expected);
    }

    #[rstest]
    #[case(0.into(), 0)]
    #[case(42.into(), 1)]
    #[case(127.into(), 1)]
    #[case(1337.into(), 2)]
    #[case(0x7fffff.into(), 3)]
    #[case(0xffffff.into(), 4)]
    #[case((-1).into(), 1)]
    #[case((-128).into(), 1)]
    fn test_atom_len_number(#[case] value: Number, #[case] expected: usize) {
        let mut a = Allocator::new();
        let atom = a.new_number(value).unwrap();
        assert_eq!(a.atom_len(atom), expected);
    }

    #[rstest]
    #[case(Malachite::from(0u64), 0)]
    #[case(Malachite::from(42u64), 1)]
    #[case(Malachite::from(127u64), 1)]
    #[case(Malachite::from(1337u64), 2)]
    #[case(Malachite::from(0x7fffff_u64), 3)]
    #[case(Malachite::from(0xffffff_u64), 4)]
    #[case(Malachite::from(-1i64), 1)]
    #[case(Malachite::from(-128i64), 1)]
    fn test_atom_len_malachite_number(#[case] value: Malachite, #[case] expected: usize) {
        let mut a = Allocator::new();
        let atom = a.new_malachite_number(value).unwrap();
        assert_eq!(a.atom_len(atom), expected);
    }

    #[rstest]
    #[case(
        "\
97f1d3a73197d7942695638c4fa9ac0f\
c3688c4f9774b905a14e3a3f171bac58\
6c55e83ff97a1aeffb3af00adb22c6bb",
        48
    )]
    #[case(
        "\
a572cbea904d67468808c8eb50a9450c\
9721db309128012543902d0ac358a62a\
e28f75bb8f1c7c42c39a8c5529bf0f4e",
        48
    )]
    fn test_atom_len_g1(#[case] buffer_hex: &str, #[case] expected: usize) {
        let mut a = Allocator::new();
        let buffer = &hex::decode(buffer_hex).unwrap();
        let g1 = G1Element::from_bytes(&buffer[..].try_into().unwrap()).expect("invalid G1 point");
        let atom = a.new_g1(g1).unwrap();
        assert_eq!(a.atom_len(atom), expected);
    }

    #[rstest]
    #[case(
        "\
93e02b6052719f607dacd3a088274f65\
596bd0d09920b61ab5da61bbdc7f5049\
334cf11213945d57e5ac7d055d042b7e\
024aa2b2f08f0a91260805272dc51051\
c6e47ad4fa403b02b4510b647ae3d177\
0bac0326a805bbefd48056c8c121bdb8",
        96
    )]
    #[case(
        "\
aa4edef9c1ed7f729f520e47730a124f\
d70662a904ba1074728114d1031e1572\
c6c886f6b57ec72a6178288c47c33577\
1638533957d540a9d2370f17cc7ed586\
3bc0b995b8825e0ee1ea1e1e4d00dbae\
81f14b0bf3611b78c952aacab827a053",
        96
    )]
    fn test_atom_len_g2(#[case] buffer_hex: &str, #[case] expected: usize) {
        let mut a = Allocator::new();

        let buffer = &hex::decode(buffer_hex).unwrap();
        let g2 = G2Element::from_bytes(&buffer[..].try_into().unwrap()).expect("invalid G2 point");
        let atom = a.new_g2(g2).unwrap();
        assert_eq!(a.atom_len(atom), expected);
    }

    #[rstest]
    #[case(0.into())]
    #[case(1.into())]
    #[case(0x7f.into())]
    #[case(0x80.into())]
    #[case(0xff.into())]
    #[case(0x100.into())]
    #[case(0x7fff.into())]
    #[case(0x8000.into())]
    #[case(0xffff.into())]
    #[case(0x10000.into())]
    #[case(0x7ffff.into())]
    #[case(0x80000.into())]
    #[case(0xfffff.into())]
    #[case(0x100000.into())]
    #[case(0x7ffffff.into())]
    #[case(0x8000000.into())]
    #[case(0xfffffff.into())]
    #[case(0x10000000.into())]
    #[case(0x7ffffffff_u64.into())]
    #[case(0x8000000000_u64.into())]
    #[case(0xffffffffff_u64.into())]
    #[case(0x10000000000_u64.into())]
    #[case((-1).into())]
    #[case((-0x7f).into())]
    #[case((-0x80).into())]
    #[case((-0xff).into())]
    #[case((-0x100).into())]
    #[case((-0x7fff).into())]
    #[case((-0x8000).into())]
    #[case((-0xffff).into())]
    #[case((-0x10000).into())]
    #[case((-0x7ffff).into())]
    #[case((-0x80000).into())]
    #[case((-0xfffff).into())]
    #[case((-0x100000).into())]
    #[case((-0x7ffffff_i64).into())]
    #[case((-0x8000000_i64).into())]
    #[case((-0xfffffff_i64).into())]
    #[case((-0x10000000_i64).into())]
    #[case((-0x7ffffffff_i64).into())]
    #[case((-0x8000000000_i64).into())]
    #[case((-0xffffffffff_i64).into())]
    #[case((-0x10000000000_i64).into())]
    fn test_number_roundtrip(#[case] value: Number) {
        let mut a = Allocator::new();
        let atom = a.new_number(value.clone()).expect("new_number()");
        assert_eq!(a.number(atom), value);
    }

    #[rstest]
    #[case(Malachite::from(0u64))]
    #[case(Malachite::from(1u64))]
    #[case(Malachite::from(0x7fu64))]
    #[case(Malachite::from(0x80u64))]
    #[case(Malachite::from(0xffu64))]
    #[case(Malachite::from(0x100u64))]
    #[case(Malachite::from(0x7fffu64))]
    #[case(Malachite::from(0x8000u64))]
    #[case(Malachite::from(0xffffu64))]
    #[case(Malachite::from(0x10000u64))]
    #[case(Malachite::from(0x7ffffu64))]
    #[case(Malachite::from(0x80000u64))]
    #[case(Malachite::from(0xfffffu64))]
    #[case(Malachite::from(0x100000u64))]
    #[case(Malachite::from(0x7ffffffu64))]
    #[case(Malachite::from(0x8000000u64))]
    #[case(Malachite::from(0xfffffffu64))]
    #[case(Malachite::from(0x10000000u64))]
    #[case(Malachite::from(0x7ffffffffu64))]
    #[case(Malachite::from(0x8000000000u64))]
    #[case(Malachite::from(0xffffffffffu64))]
    #[case(Malachite::from(0x10000000000u64))]
    #[case(Malachite::from(-1i64))]
    #[case(Malachite::from(-0x7fi64))]
    #[case(Malachite::from(-0x80i64))]
    #[case(Malachite::from(-0xffi64))]
    #[case(Malachite::from(-0x100i64))]
    #[case(Malachite::from(-0x7fffi64))]
    #[case(Malachite::from(-0x8000i64))]
    #[case(Malachite::from(-0xffffi64))]
    #[case(Malachite::from(-0x10000i64))]
    #[case(Malachite::from(-0x7ffffi64))]
    #[case(Malachite::from(-0x80000i64))]
    #[case(Malachite::from(-0xfffffi64))]
    #[case(Malachite::from(-0x100000i64))]
    #[case(Malachite::from(-0x7ffffffi64))]
    #[case(Malachite::from(-0x8000000i64))]
    #[case(Malachite::from(-0xfffffffi64))]
    #[case(Malachite::from(-0x10000000i64))]
    #[case(Malachite::from(-0x7ffffffffi64))]
    #[case(Malachite::from(-0x8000000000i64))]
    #[case(Malachite::from(-0xffffffffffi64))]
    #[case(Malachite::from(-0x10000000000i64))]
    fn test_malachite_number_roundtrip(#[case] value: Malachite) {
        let mut a = Allocator::new();
        let atom = a
            .new_malachite_number(value.clone())
            .expect("new_malachite_number()");
        assert_eq!(a.malachite_number(atom), value);
    }

    #[rstest]
    #[case(0)]
    #[case(1)]
    #[case(0x7f)]
    #[case(0x80)]
    #[case(0xff)]
    #[case(0x100)]
    #[case(0x7fff)]
    #[case(0x8000)]
    #[case(0xffff)]
    #[case(0x10000)]
    #[case(0x7ffff)]
    #[case(0x80000)]
    #[case(0xfffff)]
    #[case(0x100000)]
    #[case(0x7fffff)]
    #[case(0x800000)]
    #[case(0xffffff)]
    #[case(0x1000000)]
    #[case(0x3ffffff)]
    fn test_small_number_roundtrip(#[case] value: u32) {
        let mut a = Allocator::new();
        let atom = a.new_small_number(value).expect("new_small_number()");
        assert_eq!(a.small_number(atom).expect("small_number()"), value);
    }

    #[rstest]
    #[case(0.into(), true)]
    #[case(1.into(), true)]
    #[case(0x3ffffff.into(), true)]
    #[case(0x4000000.into(), false)]
    #[case(0x7f.into(), true)]
    #[case(0x80.into(), true)]
    #[case(0xff.into(), true)]
    #[case(0x100.into(), true)]
    #[case(0x7fff.into(), true)]
    #[case(0x8000.into(), true)]
    #[case(0xffff.into(), true)]
    #[case(0x10000.into(), true)]
    #[case(0x7ffff.into(), true)]
    #[case(0x80000.into(), true)]
    #[case(0xfffff.into(), true)]
    #[case(0x100000.into(), true)]
    #[case(0x7ffffff.into(), false)]
    #[case(0x8000000.into(), false)]
    #[case(0xfffffff.into(), false)]
    #[case(0x10000000.into(), false)]
    #[case(0x7ffffffff_u64.into(), false)]
    #[case(0x8000000000_u64.into(), false )]
    #[case(0xffffffffff_u64.into(), false)]
    #[case(0x10000000000_u64.into(), false)]
    #[case((-1).into(), false)]
    #[case((-0x7f).into(), false)]
    #[case((-0x80).into(), false)]
    #[case((-0x10000000000_i64).into(), false)]
    fn test_auto_small_number(#[case] value: Number, #[case] expect_small: bool) {
        let mut a = Allocator::new();
        let atom = a.new_number(value.clone()).expect("new_number()");
        assert_eq!(a.small_number(atom).is_some(), expect_small);
        if let Some(v) = a.small_number(atom) {
            use num_traits::ToPrimitive;
            assert_eq!(v, value.to_u32().unwrap());
        }
        assert_eq!(a.number(atom), value);
    }

    #[rstest]
    #[case(Malachite::from(0u64), true)]
    #[case(Malachite::from(1u64), true)]
    #[case(Malachite::from(0x3ffffffu64), true)]
    #[case(Malachite::from(0x4000000u64), false)]
    #[case(Malachite::from(0x7fu64), true)]
    #[case(Malachite::from(0x80u64), true)]
    #[case(Malachite::from(0xffu64), true)]
    #[case(Malachite::from(0x100u64), true)]
    #[case(Malachite::from(0x7fffu64), true)]
    #[case(Malachite::from(0x8000u64), true)]
    #[case(Malachite::from(0xffffu64), true)]
    #[case(Malachite::from(0x10000u64), true)]
    #[case(Malachite::from(0x7ffffu64), true)]
    #[case(Malachite::from(0x80000u64), true)]
    #[case(Malachite::from(0xfffffu64), true)]
    #[case(Malachite::from(0x100000u64), true)]
    #[case(Malachite::from(0x7ffffffu64), false)]
    #[case(Malachite::from(0x8000000u64), false)]
    #[case(Malachite::from(0xfffffffu64), false)]
    #[case(Malachite::from(0x10000000u64), false)]
    #[case(Malachite::from(0x7ffffffffu64), false)]
    #[case(Malachite::from(0x8000000000u64), false)]
    #[case(Malachite::from(0xffffffffffu64), false)]
    #[case(Malachite::from(0x10000000000u64), false)]
    #[case(Malachite::from(-1i64), false)]
    #[case(Malachite::from(-0x7fi64), false)]
    #[case(Malachite::from(-0x80i64), false)]
    #[case(Malachite::from(-0x10000000000i64), false)]
    fn test_auto_small_malachite_number(#[case] value: Malachite, #[case] expect_small: bool) {
        let mut a = Allocator::new();
        let atom = a
            .new_malachite_number(value.clone())
            .expect("new_malachite_number()");
        assert_eq!(a.small_number(atom).is_some(), expect_small);
        if let Some(v) = a.small_number(atom) {
            use num_traits::ToPrimitive;
            assert_eq!(v, value.to_u32().unwrap());
        }
        assert_eq!(a.malachite_number(atom), value);
    }

    #[rstest]
    #[case(0u64, &[])]
    #[case(1, &[1])]
    #[case(0x7f, &[0x7f])]
    #[case(0x80, &[0x00, 0x80])]
    #[case(0xff, &[0x00, 0xff])]
    #[case(0x100, &[0x01, 0x00])]
    #[case(0x7fff, &[0x7f, 0xff])]
    #[case(0x8000, &[0x00, 0x80, 0x00])]
    #[case(0xffff, &[0x00, 0xff, 0xff])]
    #[case(0x7f_ffff, &[0x7f, 0xff, 0xff])]
    #[case(0x80_0000, &[0x00, 0x80, 0x00, 0x00])]
    #[case(0x7fff_ffff, &[0x7f, 0xff, 0xff, 0xff])]
    #[case(0x8000_0000, &[0x00, 0x80, 0x00, 0x00, 0x00])]
    #[case(0xffff_ffff, &[0x00, 0xff, 0xff, 0xff, 0xff])]
    #[case(0x1_0000_0000, &[0x01, 0x00, 0x00, 0x00, 0x00])]
    #[case(0x7f_ffff_ffff, &[0x7f, 0xff, 0xff, 0xff, 0xff])]
    #[case(0x80_0000_0000, &[0x00, 0x80, 0x00, 0x00, 0x00, 0x00])]
    #[case(0x7fff_ffff_ffff, &[0x7f, 0xff, 0xff, 0xff, 0xff, 0xff])]
    #[case(0x8000_0000_0000, &[0x00, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00])]
    #[case(0x7f_ffff_ffff_ffff, &[0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff])]
    #[case(0x80_0000_0000_0000, &[0x00, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00])]
    #[case(0x7fff_ffff_ffff_ffff, &[0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff])]
    #[case(0x8000_0000_0000_0000, &[0x00, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00])]
    #[case(u64::MAX, &[0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff])]
    fn test_new_u64(#[case] val: u64, #[case] expected_bytes: &[u8]) {
        let mut a = Allocator::new();
        let atom = a.new_u64(val).expect("new_u64()");
        assert_eq!(a.atom(atom).as_ref(), expected_bytes);
        let expected_number: Number = val.into();
        assert_eq!(a.number(atom), expected_number);
    }

    #[rstest]
    #[case(0i64, &[])]
    #[case(1, &[1])]
    #[case(0x7f, &[0x7f])]
    #[case(0x80, &[0x00, 0x80])]
    #[case(-1, &[0xff])]
    #[case(-0x7f, &[0x81])]
    #[case(-0x80, &[0x80])]
    #[case(-0x81, &[0xff, 0x7f])]
    #[case(-0x100, &[0xff, 0x00])]
    #[case(-0x7fff, &[0x80, 0x01])]
    #[case(-0x8000, &[0x80, 0x00])]
    #[case(-0x8001, &[0xff, 0x7f, 0xff])]
    #[case(-0x80_0000, &[0x80, 0x00, 0x00])]
    #[case(-0x80_0001, &[0xff, 0x7f, 0xff, 0xff])]
    #[case(-0x8000_0000, &[0x80, 0x00, 0x00, 0x00])]
    #[case(-0x8000_0001, &[0xff, 0x7f, 0xff, 0xff, 0xff])]
    #[case(-0x80_0000_0000, &[0x80, 0x00, 0x00, 0x00, 0x00])]
    #[case(-0x80_0000_0001, &[0xff, 0x7f, 0xff, 0xff, 0xff, 0xff])]
    #[case(-0x8000_0000_0000, &[0x80, 0x00, 0x00, 0x00, 0x00, 0x00])]
    #[case(-0x8000_0000_0001, &[0xff, 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff])]
    #[case(-0x80_0000_0000_0000, &[0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00])]
    #[case(-0x80_0000_0000_0001, &[0xff, 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff])]
    #[case(i64::MIN, &[0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00])]
    #[case(i64::MAX, &[0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff])]
    fn test_new_i64(#[case] val: i64, #[case] expected_bytes: &[u8]) {
        let mut a = Allocator::new();
        let atom = a.new_i64(val).expect("new_i64()");
        assert_eq!(a.atom(atom).as_ref(), expected_bytes);
        let expected_number: Number = val.into();
        assert_eq!(a.number(atom), expected_number);
    }

    #[rstest]
    // redundant leading zeros are not canoncial
    #[case(&[0x00], false)]
    #[case(&[0x00, 0x7f], false)]
    // negative numbers cannot be small ints
    #[case(&[0x80], false)]
    #[case(&[0xff], false)]
    #[case(&[0xff, 0xff], false)]
    #[case(&[0x80, 0xff, 0xff], false)]
    // small positive intergers can be small
    #[case(&[0x01], true)]
    #[case(&[0x00, 0xff], true)]
    #[case(&[0x7f, 0xff], true)]
    #[case(&[0x7f, 0xff, 0xff], true)]
    #[case(&[0x00, 0xff, 0xff, 0xff], true)]
    #[case(&[0x02, 0x00, 0x00, 0x00], true)]
    #[case(&[0x03, 0xff, 0xff, 0xff], true)]
    // too big
    #[case(&[0x04, 0x00, 0x00, 0x00], false)]
    fn test_auto_small_number_from_buf(#[case] buf: &[u8], #[case] expect_small: bool) {
        let mut a = Allocator::new();
        let atom = a.new_atom(buf).expect("new_atom()");
        assert_eq!(a.small_number(atom).is_some(), expect_small);
        if let Some(v) = a.small_number(atom) {
            use num_traits::ToPrimitive;
            assert_eq!(v, a.number(atom).to_u32().expect("to_u32()"));
        }
        assert_eq!(buf, a.atom(atom).as_ref());
    }

    #[rstest]
    // redundant leading zeros are not canoncial
    #[case(&[0x00], None)]
    #[case(&[0x00, 0x7f], None)]
    // negative numbers cannot be small ints
    #[case(&[0x80], None)]
    #[case(&[0xff], None)]
    // redundant leading 0xff are still negative
    #[case(&[0xff, 0xff], None)]
    #[case(&[0x80, 0xff, 0xff], None)]
    // to big
    #[case(&[0x04, 0x00, 0x00, 0x00], None)]
    #[case(&[0x05, 0x00, 0x00, 0x00], None)]
    #[case(&[0x04, 0x00, 0x00, 0x00, 0x00], None)]
    // small positive intergers can be small
    #[case(&[0x01], Some(0x01))]
    #[case(&[0x00, 0x80], Some(0x80))]
    #[case(&[0x00, 0xff], Some(0xff))]
    #[case(&[0x7f, 0xff], Some(0x7fff))]
    #[case(&[0x00, 0x80, 0x00], Some(0x8000))]
    #[case(&[0x00, 0xff, 0xff], Some(0xffff))]
    #[case(&[0x7f, 0xff, 0xff], Some(0x7fffff))]
    #[case(&[0x00, 0x80, 0x00, 0x00], Some(0x800000))]
    #[case(&[0x00, 0xff, 0xff, 0xff], Some(0xffffff))]
    #[case(&[0x02, 0x00, 0x00, 0x00], Some(0x2000000))]
    #[case(&[0x03, 0x00, 0x00, 0x00], Some(0x3000000))]
    #[case(&[0x03, 0xff, 0xff, 0xff], Some(0x3ffffff))]
    fn test_fits_in_small_atom(#[case] buf: &[u8], #[case] expected: Option<u32>) {
        assert_eq!(fits_in_small_atom(buf), expected);
    }

    #[rstest]
    // 0 is encoded as an empty string
    #[case(&[0], "0", &[])]
    #[case(&[1], "1", &[1])]
    // leading zeroes are redundant
    #[case(&[0,0,0,1], "1", &[1])]
    #[case(&[0,0,0x80], "128", &[0, 0x80])]
    // A leading zero is necessary to encode a positive number with the
    // penultimate byte's most significant bit set
    #[case(&[0,0xff], "255", &[0, 0xff])]
    #[case(&[0x7f,0xff], "32767", &[0x7f, 0xff])]
    // the first byte is redundant, it's still -1
    #[case(&[0xff,0xff], "-1", &[0xff])]
    #[case(&[0xff], "-1", &[0xff])]
    #[case(&[0,0,0x80,0], "32768", &[0,0x80,0])]
    #[case(&[0,0,0x40,0], "16384", &[0x40,0])]
    fn test_number_to_atom(#[case] bytes: &[u8], #[case] text: &str, #[case] buf: &[u8]) {
        let mut a = Allocator::new();

        // 0 is encoded as an empty string
        let num = number_from_u8(bytes);
        assert_eq!(format!("{num}"), text);
        let ptr = a.new_number(num).unwrap();
        assert_eq!(a.atom(ptr).as_ref(), buf);
    }

    #[rstest]
    #[case(&[0], "0", &[])]
    #[case(&[1], "1", &[1])]
    #[case(&[0,0,0,1], "1", &[1])]
    #[case(&[0,0,0x80], "128", &[0, 0x80])]
    #[case(&[0,0xff], "255", &[0, 0xff])]
    #[case(&[0x7f,0xff], "32767", &[0x7f, 0xff])]
    #[case(&[0xff,0xff], "-1", &[0xff])]
    #[case(&[0xff], "-1", &[0xff])]
    #[case(&[0,0,0x80,0], "32768", &[0,0x80,0])]
    #[case(&[0,0,0x40,0], "16384", &[0x40,0])]
    fn test_malachite_number_to_atom(#[case] bytes: &[u8], #[case] text: &str, #[case] buf: &[u8]) {
        let mut a = Allocator::new();

        let num = malachite_number_from_u8(bytes);
        assert_eq!(format!("{num}"), text);
        let ptr = a.new_malachite_number(num).unwrap();
        assert_eq!(a.atom(ptr).as_ref(), buf);
    }
}

#[cfg(feature = "allocator-debug")]
#[cfg(test)]
mod debug_tests {
    use super::*;
    use chia_bls::PublicKey;
    use chia_bls::Signature;
    use rstest::rstest;

    fn new_node(a: &mut Allocator, case: u8) -> (NodePtr, usize) {
        match case {
            0 => (a.nil(), 0),
            1 => (a.one(), 1),
            2 => (a.new_atom(b"foobar").expect("new_atom"), 6),
            3 => (a.new_pair(NodePtr::NIL, NodePtr::NIL).expect("new_pair"), 0),
            4 => (a.new_concat(2, &[a.one(), a.one()]).expect("new_concat"), 2),
            5 => (a.new_substr(a.one(), 0, 1).expect("new_substr"), 1),
            6 => (a.new_small_number(1337).expect("new_small_number"), 2),
            7 => (a.new_number(u32::MAX.into()).expect("new_number"), 5),
            8 => (a.new_g1(PublicKey::default()).expect("new_g1"), 48),
            9 => (a.new_g2(Signature::default()).expect("new_g2"), 32),
            _ => {
                panic!("unexpected case");
            }
        }
    }

    fn access_node(a: &mut Allocator, n: NodePtr, len: usize, case: u8) {
        match case {
            0 => {
                let _ = a.new_pair(n, a.nil());
            }
            1 => {
                let _ = a.new_pair(a.nil(), n);
            }
            2 => {
                let _ = a.new_substr(n, 0, (len / 2) as u32);
            }
            3 => {
                let _ = a.new_concat(len, &[n]);
            }
            4 => {
                let _ = a.new_concat(len + 1, &[a.one(), n]);
            }
            5 => {
                a.atom_eq(a.one(), n);
            }
            6 => {
                a.atom_eq(n, a.one());
            }
            7 => {
                a.atom(n);
            }
            8 => {
                a.atom_len(n);
            }
            9 => {
                a.small_number(n);
            }
            10 => {
                a.number(n);
            }
            11 => {
                let _ = a.g1(n);
            }
            12 => {
                let _ = a.g2(n);
            }
            13 => {
                a.node(n);
            }
            14 => {
                a.sexp(n);
            }
            15 => {
                a.next(n);
            }
            _ => {
                panic!("unexpected case");
            }
        }
    }

    #[rstest]
    #[should_panic(expected = "using a NodePtr on the wrong Allocator")]
    fn mixing_allocators(
        #[values(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)] create_case: u8,
        #[values(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)] access_case: u8,
    ) {
        let mut a1 = Allocator::new();
        let mut a2 = Allocator::new();

        let (node, len) = new_node(&mut a1, create_case);
        access_node(&mut a2, node, len, access_case);
    }

    #[rstest]
    #[should_panic(expected = "was invalidated by restore_checkpoint()")]
    fn invalidating_node(
        #[values(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)] create_case: u8,
        #[values(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)] access_case: u8,
    ) {
        let mut a1 = Allocator::new();
        let checkpoint = a1.checkpoint();

        let (node, len) = new_node(&mut a1, create_case);

        // this will invalidate "node"
        a1.restore_checkpoint(&checkpoint);
        access_node(&mut a1, node, len, access_case);

        if matches!(a1.node(node), NodeVisitor::U32(_)) {
            // small atoms aren't allocated on the heap, so we don't know
            // whether they should have been invalidated or not. They never are
            // in practice.
            panic!("simulated NodePtr was invalidated by restore_checkpoint()");
        }
    }
}