9969783315

Committed 17 Jul 2024 07:09AM UTC coverage: 91.834% (-2.2%) from 94.072%

Build # 9969783315

Build Type

push

github

Committed by

Chik-Network

Commit Message

update 0.2.5

Run Details

1191 of 1284 new or added lines in 29 files covered. (92.76%)

66 existing lines in 11 files now uncovered.

4071 of 4433 relevant lines covered (91.83%)

3553.81 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.89

/src/allocator.rs

use crate::err_utils::err;
use crate::number::{node_from_number, number_from_u8, Number};
use crate::reduction::EvalErr;

pub type NodePtr = i32;

pub enum SExp {
    Atom(AtomBuf),
    Pair(NodePtr, NodePtr),
}

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

impl AtomBuf {
    pub fn idx_range(&self) -> (u32, u32) {
        (self.start, self.end)
    }
    pub fn is_empty(&self) -> bool {
        self.start == self.end
    }
    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 {
    u8s: usize,
    pairs: usize,
    atoms: usize,
}

#[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 pair_vec may not grow past this
    pair_limit: usize,

    // the atom_vec may not grow past this
    atom_limit: usize,
}

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

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

    pub fn new_limited(heap_limit: usize, pair_limit: usize, atom_limit: usize) -> Self {
        // we have a maximum of 4 GiB heap, because pointers are 32 bit unsigned
        assert!(heap_limit <= u32::MAX as usize);
        // the atoms and pairs share a single 32 bit address space, where
        // negative numbers are atoms and positive numbers are pairs. That's why
        // we have one more slot for pairs than atoms
        assert!(pair_limit <= i32::MAX as usize);
        assert!(atom_limit < i32::MAX as usize);

        let mut r = Self {
            u8_vec: Vec::new(),
            pair_vec: Vec::new(),
            atom_vec: Vec::new(),
            heap_limit,
            pair_limit,
            atom_limit,
        };
        r.u8_vec.reserve(1024 * 1024);
        r.atom_vec.reserve(256);
        r.pair_vec.reserve(256);
        r.u8_vec.push(1_u8);
        // Preallocated empty list
        r.atom_vec.push(AtomBuf { start: 0, end: 0 });
        // Preallocated 1
        r.atom_vec.push(AtomBuf { start: 0, end: 1 });
        r
    }

    // 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 {
            u8s: self.u8_vec.len(),
            pairs: self.pair_vec.len(),
            atoms: self.atom_vec.len(),
        }
    }

    pub fn restore_checkpoint(&mut self, cp: &Checkpoint) {
        // 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 earler state). You can only restore backwards in time,
        // not forwards.
        assert!(self.u8_vec.len() >= cp.u8s);
        assert!(self.pair_vec.len() >= cp.pairs);
        assert!(self.atom_vec.len() >= cp.atoms);
        self.u8_vec.truncate(cp.u8s);
        self.pair_vec.truncate(cp.pairs);
        self.atom_vec.truncate(cp.atoms);
    }

    pub fn new_atom(&mut self, v: &[u8]) -> Result<NodePtr, EvalErr> {
        let start = self.u8_vec.len() as u32;
        if (self.heap_limit - start as usize) < v.len() {
            return err(self.null(), "out of memory");
        }
        if self.atom_vec.len() == self.atom_limit {
            return err(self.null(), "too many atoms");
        }
        self.u8_vec.extend_from_slice(v);
        let end = self.u8_vec.len() as u32;
        self.atom_vec.push(AtomBuf { start, end });
        Ok(-(self.atom_vec.len() as i32))
    }

    pub fn new_number(&mut self, v: Number) -> Result<NodePtr, EvalErr> {
        node_from_number(self, &v)
    }

    pub fn new_pair(&mut self, first: NodePtr, rest: NodePtr) -> Result<NodePtr, EvalErr> {
        let r = self.pair_vec.len() as i32;
        if self.pair_vec.len() == self.pair_limit {
            return err(self.null(), "too many pairs");
        }
        self.pair_vec.push(IntPair { first, rest });
        Ok(r)
    }

    pub fn new_substr(&mut self, node: NodePtr, start: u32, end: u32) -> Result<NodePtr, EvalErr> {
        if node >= 0 {
            return err(node, "(internal error) substr expected atom, got pair");
        }
        if self.atom_vec.len() == self.atom_limit {
            return err(self.null(), "too many atoms");
        }
        let atom = self.atom_vec[(-node - 1) as usize];
        let atom_len = atom.end - atom.start;
        if start > atom_len {
            return err(node, "substr start out of bounds");
        }
        if end > atom_len {
            return err(node, "substr end out of bounds");
        }
        if end < start {
            return err(node, "substr invalid bounds");
        }
        self.atom_vec.push(AtomBuf {
            start: atom.start + start,
            end: atom.start + end,
        });
        Ok(-(self.atom_vec.len() as i32))
    }

    pub fn new_concat(&mut self, new_size: usize, nodes: &[NodePtr]) -> Result<NodePtr, EvalErr> {
        if self.atom_vec.len() == self.atom_limit {
            return err(self.null(), "too many atoms");
        }
        let start = self.u8_vec.len();
        if self.heap_limit - start < new_size {
            return err(self.null(), "out of memory");
        }
        self.u8_vec.reserve(new_size);

        let mut counter: usize = 0;
        for node in nodes {
            if *node >= 0 {
                self.u8_vec.truncate(start);
                return err(*node, "(internal error) concat expected atom, got pair");
            }

            let term = self.atom_vec[(-node - 1) as usize];
            if counter + term.len() > new_size {
                self.u8_vec.truncate(start);
                return err(*node, "(internal error) concat passed invalid new_size");
            }
            self.u8_vec
                .extend_from_within(term.start as usize..term.end as usize);
            counter += term.len();
        }
        if counter != new_size {
            self.u8_vec.truncate(start);
            return err(
                self.null(),
                "(internal error) concat passed invalid new_size",
            );
        }
        let end = self.u8_vec.len() as u32;
        self.atom_vec.push(AtomBuf {
            start: (start as u32),
            end,
        });
        Ok(-(self.atom_vec.len() as i32))
    }

    pub fn atom(&self, node: NodePtr) -> &[u8] {
        assert!(node < 0, "expected atom, got pair");
        let atom = self.atom_vec[(-node - 1) as usize];
        &self.u8_vec[atom.start as usize..atom.end as usize]
    }

    pub fn buf<'a>(&'a self, node: &AtomBuf) -> &'a [u8] {
        &self.u8_vec[node.start as usize..node.end as usize]
    }

    pub fn atom_len(&self, node: NodePtr) -> usize {
        self.atom(node).len()
    }

    pub fn number(&self, node: NodePtr) -> Number {
        number_from_u8(self.atom(node))
    }

    pub fn sexp(&self, node: NodePtr) -> SExp {
        if node >= 0 {
            let pair = self.pair_vec[node as usize];
            SExp::Pair(pair.first, pair.rest)
        } else {
            let atom = self.atom_vec[(-node - 1) as usize];
            SExp::Atom(atom)
        }
    }

    pub fn null(&self) -> NodePtr {
        -1
    }

    pub fn one(&self) -> NodePtr {
        -2
    }

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

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

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

#[test]
fn test_null() {
    let a = Allocator::new();
    assert_eq!(a.atom(a.null()), b"");

    let buf = match a.sexp(a.null()) {
        SExp::Atom(b) => a.buf(&b),
        SExp::Pair(_, _) => panic!("unexpected"),
    };
    assert_eq!(buf, b"");
}

#[test]
fn test_one() {
    let a = Allocator::new();
    assert_eq!(a.atom(a.one()), b"\x01");
    assert_eq!(
        match a.sexp(a.one()) {
            SExp::Atom(b) => a.buf(&b),
            SExp::Pair(_, _) => panic!("unexpected"),
        },
        b"\x01"
    );
}

#[test]
fn test_allocate_atom() {
    let mut a = Allocator::new();
    let atom = a.new_atom(b"foobar").unwrap();
    assert_eq!(a.atom(atom), b"foobar");
    assert_eq!(
        match a.sexp(atom) {
            SExp::Atom(b) => a.buf(&b),
            SExp::Pair(_, _) => panic!("unexpected"),
        },
        b"foobar"
    );
}

#[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!(
        match a.sexp(pair) {
            SExp::Atom(_) => panic!("unexpected"),
            SExp::Pair(left, right) => (left, right),
        },
        (atom1, atom2)
    );

    let pair2 = a.new_pair(pair, pair).unwrap();
    assert_eq!(
        match a.sexp(pair2) {
            SExp::Atom(_) => panic!("unexpected"),
            SExp::Pair(left, right) => (left, right),
        },
        (pair, pair)
    );
}

#[test]
fn test_allocate_heap_limit() {
    let mut a = Allocator::new_limited(6, i32::MAX as usize, (i32::MAX - 1) as usize);
    // we can't allocate 6 bytes
    assert_eq!(a.new_atom(b"foobar").unwrap_err().1, "out of memory");
    // but 5 is OK
    let _atom = a.new_atom(b"fooba").unwrap();
}

#[test]
fn test_allocate_atom_limit() {
    let mut a = Allocator::new_limited(u32::MAX as usize, i32::MAX as usize, 5);
    // we can allocate 5 atoms total
    // keep in mind that we always have 2 pre-allocated atoms for null and one,
    // so with a limit of 5, we only have 3 slots left at this point.
    let _atom = a.new_atom(b"foo").unwrap();
    let _atom = a.new_atom(b"bar").unwrap();
    let _atom = a.new_atom(b"baz").unwrap();

    // the 4th fails and ensure not to append atom to the stack
    assert_eq!(a.u8_vec.len(), 10);
    assert_eq!(a.new_atom(b"foobar").unwrap_err().1, "too many atoms");
    assert_eq!(a.u8_vec.len(), 10);
}

#[test]
fn test_allocate_pair_limit() {
    let mut a = Allocator::new_limited(u32::MAX as usize, 1, (i32::MAX - 1) as usize);
    let atom = a.new_atom(b"foo").unwrap();
    // one pair is OK
    let _pair1 = a.new_pair(atom, atom).unwrap();
    // but not 2
    assert_eq!(a.new_pair(atom, atom).unwrap_err().1, "too many pairs");
}

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

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

    assert_eq!(
        a.new_substr(atom, 1, 0).unwrap_err().1,
        "substr invalid bounds"
    );
    assert_eq!(
        a.new_substr(atom, 7, 7).unwrap_err().1,
        "substr start out of bounds"
    );
    assert_eq!(
        a.new_substr(atom, 0, 7).unwrap_err().1,
        "substr end out of bounds"
    );
    assert_eq!(
        a.new_substr(atom, u32::MAX, 4).unwrap_err().1,
        "substr start out of bounds"
    );
}

#[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), b"foobar");

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

    assert_eq!(
        a.new_concat(11, &[cat, cat]).unwrap_err().1,
        "(internal error) concat passed invalid new_size"
    );
    assert_eq!(
        a.new_concat(13, &[cat, cat]).unwrap_err().1,
        "(internal error) concat passed invalid new_size"
    );
    assert_eq!(
        a.new_concat(12, &[atom3, pair]).unwrap_err().1,
        "(internal error) concat expected atom, got pair"
    );
}

#[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!(
        match a.sexp(atom1) {
            SExp::Atom(_) => 0,
            SExp::Pair(_, _) => 1,
        },
        0
    );
    assert_eq!(
        match a.sexp(atom2) {
            SExp::Atom(_) => 0,
            SExp::Pair(_, _) => 1,
        },
        0
    );
    assert_eq!(
        match a.sexp(pair) {
            SExp::Atom(_) => 0,
            SExp::Pair(_, _) => 1,
        },
        1
    );
}

#[test]
fn test_concat_limit() {
    let mut a = Allocator::new_limited(9, i32::MAX as usize, (i32::MAX - 1) as usize);
    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()
            .1,
        "out of memory"
    );
    let cat = a.new_concat(2, &[atom1, atom2]).unwrap();
    assert_eq!(a.atom(cat), b"fo");
}

#[cfg(test)]
use rstest::rstest;

#[cfg(test)]
#[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), 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), expected);
    assert_eq!(number_from_u8(expected), num);
}

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

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

    let checkpoint = a.checkpoint();

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

    // 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);

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

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

1	use crate::err_utils::err;
2	use crate::number::{node_from_number, number_from_u8, Number};
3	use crate::reduction::EvalErr;
4
5	pub type NodePtr = i32;
6
7	pub enum SExp {
8	Atom(AtomBuf),
9	Pair(NodePtr, NodePtr),
10	}
11
12	#[derive(Clone, Copy, Debug)]
13	pub struct AtomBuf {
14	start: u32,
15	end: u32,
16	}
17
18	impl AtomBuf {
NEW 19	pub fn idx_range(&self) -> (u32, u32) {	×
NEW 20	(self.start, self.end)	×
NEW 21	}	×
22	pub fn is_empty(&self) -> bool {	6,123✔
23	self.start == self.end	6,123✔
24	}	6,123✔
25	pub fn len(&self) -> usize {	218✔
26	(self.end - self.start) as usize	218✔
27	}	218✔
28	}
29
30	#[derive(Clone, Copy, Debug)]
31	pub struct IntPair {
32	first: NodePtr,
33	rest: NodePtr,
34	}
35
36	// this represents a specific (former) state of an allocator. This can be used
37	// to restore an allocator to a previous state. It cannot be used to re-create
38	// the state from some other allocator.
39	pub struct Checkpoint {
40	u8s: usize,
41	pairs: usize,
42	atoms: usize,
43	}
44
45	#[derive(Debug)]
46	pub struct Allocator {
47	// this is effectively a grow-only stack where atoms are allocated. Atoms
48	// are immutable, so once they are created, they will stay around until the
49	// program completes
50	u8_vec: Vec<u8>,
51
52	// storage for all pairs (positive indices)
53	pair_vec: Vec<IntPair>,
54
55	// storage for all atoms (negative indices).
56	// node index -1 refers to index 0 in this vector, -2 refers to 1 and so
57	// on.
58	atom_vec: Vec<AtomBuf>,
59
60	// the atom_vec may not grow past this
61	heap_limit: usize,
62
63	// the pair_vec may not grow past this
64	pair_limit: usize,
65
66	// the atom_vec may not grow past this
67	atom_limit: usize,
68	}
69
70	impl Default for Allocator {
71	fn default() -> Self {	×
72	Self::new()	×
73	}	×
74	}
75
76	impl Allocator {
77	pub fn new() -> Self {	1,657✔
78	Self::new_limited(	1,657✔
79	u32::MAX as usize,	1,657✔
80	i32::MAX as usize,	1,657✔
81	(i32::MAX - 1) as usize,	1,657✔
82	)	1,657✔
83	}	1,657✔
84
85	pub fn new_limited(heap_limit: usize, pair_limit: usize, atom_limit: usize) -> Self {	1,661✔
86	// we have a maximum of 4 GiB heap, because pointers are 32 bit unsigned	1,661✔
87	assert!(heap_limit <= u32::MAX as usize);	1,661✔
88	// the atoms and pairs share a single 32 bit address space, where
89	// negative numbers are atoms and positive numbers are pairs. That's why
90	// we have one more slot for pairs than atoms
91	assert!(pair_limit <= i32::MAX as usize);	1,661✔
92	assert!(atom_limit < i32::MAX as usize);	1,661✔
93
94	let mut r = Self {	1,661✔
95	u8_vec: Vec::new(),	1,661✔
96	pair_vec: Vec::new(),	1,661✔
97	atom_vec: Vec::new(),	1,661✔
98	heap_limit,	1,661✔
99	pair_limit,	1,661✔
100	atom_limit,	1,661✔
101	};	1,661✔
102	r.u8_vec.reserve(1024 * 1024);	1,661✔
103	r.atom_vec.reserve(256);	1,661✔
104	r.pair_vec.reserve(256);	1,661✔
105	r.u8_vec.push(1_u8);	1,661✔
106	// Preallocated empty list	1,661✔
107	r.atom_vec.push(AtomBuf { start: 0, end: 0 });	1,661✔
108	// Preallocated 1	1,661✔
109	r.atom_vec.push(AtomBuf { start: 0, end: 1 });	1,661✔
110	r	1,661✔
111	}	1,661✔
112
113	// create a checkpoint for the current state of the allocator. This can be
114	// used to go back to an earlier allocator state by passing the Checkpoint
115	// to restore_checkpoint().
116	pub fn checkpoint(&self) -> Checkpoint {	6✔
117	Checkpoint {	6✔
118	u8s: self.u8_vec.len(),	6✔
119	pairs: self.pair_vec.len(),	6✔
120	atoms: self.atom_vec.len(),	6✔
121	}	6✔
122	}	6✔
123
124	pub fn restore_checkpoint(&mut self, cp: &Checkpoint) {	3✔
125	// if any of these asserts fire, it means we're trying to restore to	3✔
126	// a state that has already been "long-jumped" passed (via another	3✔
127	// restore to an earler state). You can only restore backwards in time,	3✔
128	// not forwards.	3✔
129	assert!(self.u8_vec.len() >= cp.u8s);	3✔
130	assert!(self.pair_vec.len() >= cp.pairs);	3✔
131	assert!(self.atom_vec.len() >= cp.atoms);	3✔
132	self.u8_vec.truncate(cp.u8s);	3✔
133	self.pair_vec.truncate(cp.pairs);	3✔
134	self.atom_vec.truncate(cp.atoms);	3✔
135	}	3✔
136
137	pub fn new_atom(&mut self, v: &[u8]) -> Result<NodePtr, EvalErr> {	10,781✔
138	let start = self.u8_vec.len() as u32;	10,781✔
139	if (self.heap_limit - start as usize) < v.len() {	10,781✔
140	return err(self.null(), "out of memory");	1✔
141	}	10,780✔
142	if self.atom_vec.len() == self.atom_limit {	10,780✔
143	return err(self.null(), "too many atoms");	1✔
144	}	10,779✔
145	self.u8_vec.extend_from_slice(v);	10,779✔
146	let end = self.u8_vec.len() as u32;	10,779✔
147	self.atom_vec.push(AtomBuf { start, end });	10,779✔
148	Ok(-(self.atom_vec.len() as i32))	10,779✔
149	}	10,781✔
150
151	pub fn new_number(&mut self, v: Number) -> Result<NodePtr, EvalErr> {	6,010✔
152	node_from_number(self, &v)	6,010✔
153	}	6,010✔
154
155	pub fn new_pair(&mut self, first: NodePtr, rest: NodePtr) -> Result<NodePtr, EvalErr> {	65,427✔
156	let r = self.pair_vec.len() as i32;	65,427✔
157	if self.pair_vec.len() == self.pair_limit {	65,427✔
158	return err(self.null(), "too many pairs");	1✔
159	}	65,426✔
160	self.pair_vec.push(IntPair { first, rest });	65,426✔
161	Ok(r)	65,426✔
162	}	65,427✔
163
164	pub fn new_substr(&mut self, node: NodePtr, start: u32, end: u32) -> Result<NodePtr, EvalErr> {	28✔
165	if node >= 0 {	28✔
NEW 166	return err(node, "(internal error) substr expected atom, got pair");	×
167	}	28✔
168	if self.atom_vec.len() == self.atom_limit {	28✔
NEW 169	return err(self.null(), "too many atoms");	×
170	}	28✔
171	let atom = self.atom_vec[(-node - 1) as usize];	28✔
172	let atom_len = atom.end - atom.start;	28✔
173	if start > atom_len {	28✔
174	return err(node, "substr start out of bounds");	2✔
175	}	26✔
176	if end > atom_len {	26✔
177	return err(node, "substr end out of bounds");	1✔
178	}	25✔
179	if end < start {	25✔
180	return err(node, "substr invalid bounds");	1✔
181	}	24✔
182	self.atom_vec.push(AtomBuf {	24✔
183	start: atom.start + start,	24✔
184	end: atom.start + end,	24✔
185	});	24✔
186	Ok(-(self.atom_vec.len() as i32))	24✔
187	}	28✔
188
189	pub fn new_concat(&mut self, new_size: usize, nodes: &[NodePtr]) -> Result<NodePtr, EvalErr> {	19✔
190	if self.atom_vec.len() == self.atom_limit {	19✔
NEW 191	return err(self.null(), "too many atoms");	×
192	}	19✔
193	let start = self.u8_vec.len();	19✔
194	if self.heap_limit - start < new_size {	19✔
195	return err(self.null(), "out of memory");	1✔
196	}	18✔
197	self.u8_vec.reserve(new_size);	18✔
198		18✔
199	let mut counter: usize = 0;	18✔
200	for node in nodes {	53✔
201	if *node >= 0 {	38✔
202	self.u8_vec.truncate(start);	1✔
203	return err(*node, "(internal error) concat expected atom, got pair");	1✔
204	}	37✔
205		37✔
206	let term = self.atom_vec[(-node - 1) as usize];	37✔
207	if counter + term.len() > new_size {	37✔
208	self.u8_vec.truncate(start);	2✔
209	return err(*node, "(internal error) concat passed invalid new_size");	2✔
210	}	35✔
211	self.u8_vec	35✔
212	.extend_from_within(term.start as usize..term.end as usize);	35✔
213	counter += term.len();	35✔
214	}
215	if counter != new_size {	15✔
UNCOV 216	self.u8_vec.truncate(start);	×
UNCOV 217	return err(	×
NEW 218	self.null(),	×
UNCOV 219	"(internal error) concat passed invalid new_size",	×
UNCOV 220	);	×
221	}	15✔
222	let end = self.u8_vec.len() as u32;	15✔
223	self.atom_vec.push(AtomBuf {	15✔
224	start: (start as u32),	15✔
225	end,	15✔
226	});	15✔
227	Ok(-(self.atom_vec.len() as i32))	15✔
228	}	19✔
229
230	pub fn atom(&self, node: NodePtr) -> &[u8] {	81,015✔
231	assert!(node < 0, "expected atom, got pair");	81,015✔
232	let atom = self.atom_vec[(-node - 1) as usize];	81,015✔
233	&self.u8_vec[atom.start as usize..atom.end as usize]	81,015✔
234	}	81,015✔
235
236	pub fn buf<'a>(&'a self, node: &AtomBuf) -> &'a [u8] {	68,020✔
237	&self.u8_vec[node.start as usize..node.end as usize]	68,020✔
238	}	68,020✔
239
240	pub fn atom_len(&self, node: NodePtr) -> usize {	13,080✔
241	self.atom(node).len()	13,080✔
242	}	13,080✔
243
244	pub fn number(&self, node: NodePtr) -> Number {	8,770✔
245	number_from_u8(self.atom(node))	8,770✔
246	}	8,770✔
247
248	pub fn sexp(&self, node: NodePtr) -> SExp {	345,432✔
249	if node >= 0 {	345,432✔
250	let pair = self.pair_vec[node as usize];	202,351✔
251	SExp::Pair(pair.first, pair.rest)	202,351✔
252	} else {
253	let atom = self.atom_vec[(-node - 1) as usize];	143,081✔
254	SExp::Atom(atom)	143,081✔
255	}
256	}	345,432✔
257
258	pub fn null(&self) -> NodePtr {	26,475✔
259	-1	26,475✔
260	}	26,475✔
261
262	pub fn one(&self) -> NodePtr {	16,110✔
263	-2	16,110✔
264	}	16,110✔
265
266	#[cfg(feature = "counters")]
267	pub fn atom_count(&self) -> usize {
268	self.atom_vec.len()
269	}
270
271	#[cfg(feature = "counters")]
272	pub fn pair_count(&self) -> usize {
273	self.pair_vec.len()
274	}
275
276	#[cfg(feature = "counters")]
277	pub fn heap_size(&self) -> usize {
278	self.u8_vec.len()
279	}
280	}
281
282	#[test]
283	fn test_null() {	1✔
284	let a = Allocator::new();	1✔
285	assert_eq!(a.atom(a.null()), b"");	1✔
286
287	let buf = match a.sexp(a.null()) {	1✔
288	SExp::Atom(b) => a.buf(&b),	1✔
NEW 289	SExp::Pair(_, _) => panic!("unexpected"),	×
290	};
291	assert_eq!(buf, b"");	1✔
292	}	1✔
293
294	#[test]
295	fn test_one() {	1✔
296	let a = Allocator::new();	1✔
297	assert_eq!(a.atom(a.one()), b"\x01");	1✔
298	assert_eq!(	1✔
299	match a.sexp(a.one()) {	1✔
300	SExp::Atom(b) => a.buf(&b),	1✔
NEW 301	SExp::Pair(_, _) => panic!("unexpected"),	×
302	},
303	b"\x01"
304	);
305	}	1✔
306
307	#[test]
308	fn test_allocate_atom() {	1✔
309	let mut a = Allocator::new();	1✔
310	let atom = a.new_atom(b"foobar").unwrap();	1✔
311	assert_eq!(a.atom(atom), b"foobar");	1✔
312	assert_eq!(	1✔
313	match a.sexp(atom) {	1✔
314	SExp::Atom(b) => a.buf(&b),	1✔
NEW 315	SExp::Pair(_, _) => panic!("unexpected"),	×
316	},
317	b"foobar"
318	);
319	}	1✔
320
321	#[test]
322	fn test_allocate_pair() {	1✔
323	let mut a = Allocator::new();	1✔
324	let atom1 = a.new_atom(b"foo").unwrap();	1✔
325	let atom2 = a.new_atom(b"bar").unwrap();	1✔
326	let pair = a.new_pair(atom1, atom2).unwrap();	1✔
327
328	assert_eq!(	1✔
329	match a.sexp(pair) {	1✔
NEW 330	SExp::Atom(_) => panic!("unexpected"),	×
331	SExp::Pair(left, right) => (left, right),	1✔
332	},	1✔
333	(atom1, atom2)	1✔
334	);
335
336	let pair2 = a.new_pair(pair, pair).unwrap();	1✔
337	assert_eq!(	1✔
338	match a.sexp(pair2) {	1✔
NEW 339	SExp::Atom(_) => panic!("unexpected"),	×
340	SExp::Pair(left, right) => (left, right),	1✔
341	},	1✔
342	(pair, pair)	1✔
343	);
344	}	1✔
345
346	#[test]
347	fn test_allocate_heap_limit() {	1✔
348	let mut a = Allocator::new_limited(6, i32::MAX as usize, (i32::MAX - 1) as usize);	1✔
349	// we can't allocate 6 bytes	1✔
350	assert_eq!(a.new_atom(b"foobar").unwrap_err().1, "out of memory");	1✔
351	// but 5 is OK
352	let _atom = a.new_atom(b"fooba").unwrap();	1✔
353	}	1✔
354
355	#[test]
356	fn test_allocate_atom_limit() {	1✔
357	let mut a = Allocator::new_limited(u32::MAX as usize, i32::MAX as usize, 5);	1✔
358	// we can allocate 5 atoms total	1✔
359	// keep in mind that we always have 2 pre-allocated atoms for null and one,	1✔
360	// so with a limit of 5, we only have 3 slots left at this point.	1✔
361	let _atom = a.new_atom(b"foo").unwrap();	1✔
362	let _atom = a.new_atom(b"bar").unwrap();	1✔
363	let _atom = a.new_atom(b"baz").unwrap();	1✔
364		1✔
365	// the 4th fails and ensure not to append atom to the stack	1✔
366	assert_eq!(a.u8_vec.len(), 10);	1✔
367	assert_eq!(a.new_atom(b"foobar").unwrap_err().1, "too many atoms");	1✔
368	assert_eq!(a.u8_vec.len(), 10);	1✔
369	}	1✔
370
371	#[test]
372	fn test_allocate_pair_limit() {	1✔
373	let mut a = Allocator::new_limited(u32::MAX as usize, 1, (i32::MAX - 1) as usize);	1✔
374	let atom = a.new_atom(b"foo").unwrap();	1✔
375	// one pair is OK	1✔
376	let _pair1 = a.new_pair(atom, atom).unwrap();	1✔
377	// but not 2	1✔
378	assert_eq!(a.new_pair(atom, atom).unwrap_err().1, "too many pairs");	1✔
379	}	1✔
380
381	#[test]
382	fn test_substr() {	1✔
383	let mut a = Allocator::new();	1✔
384	let atom = a.new_atom(b"foobar").unwrap();	1✔
385		1✔
386	let sub = a.new_substr(atom, 0, 1).unwrap();	1✔
387	assert_eq!(a.atom(sub), b"f");	1✔
388	let sub = a.new_substr(atom, 1, 6).unwrap();	1✔
389	assert_eq!(a.atom(sub), b"oobar");	1✔
390	let sub = a.new_substr(atom, 1, 1).unwrap();	1✔
391	assert_eq!(a.atom(sub), b"");	1✔
392	let sub = a.new_substr(atom, 0, 0).unwrap();	1✔
393	assert_eq!(a.atom(sub), b"");	1✔
394
395	assert_eq!(	1✔
396	a.new_substr(atom, 1, 0).unwrap_err().1,	1✔
397	"substr invalid bounds"	1✔
398	);	1✔
399	assert_eq!(	1✔
400	a.new_substr(atom, 7, 7).unwrap_err().1,	1✔
401	"substr start out of bounds"	1✔
402	);	1✔
403	assert_eq!(	1✔
404	a.new_substr(atom, 0, 7).unwrap_err().1,	1✔
405	"substr end out of bounds"	1✔
406	);	1✔
407	assert_eq!(	1✔
408	a.new_substr(atom, u32::MAX, 4).unwrap_err().1,	1✔
409	"substr start out of bounds"	1✔
410	);	1✔
411	}	1✔
412
413	#[test]
414	fn test_concat() {	1✔
415	let mut a = Allocator::new();	1✔
416	let atom1 = a.new_atom(b"f").unwrap();	1✔
417	let atom2 = a.new_atom(b"o").unwrap();	1✔
418	let atom3 = a.new_atom(b"o").unwrap();	1✔
419	let atom4 = a.new_atom(b"b").unwrap();	1✔
420	let atom5 = a.new_atom(b"a").unwrap();	1✔
421	let atom6 = a.new_atom(b"r").unwrap();	1✔
422	let pair = a.new_pair(atom1, atom2).unwrap();	1✔
423		1✔
424	let cat = a	1✔
425	.new_concat(6, &[atom1, atom2, atom3, atom4, atom5, atom6])	1✔
426	.unwrap();	1✔
427	assert_eq!(a.atom(cat), b"foobar");	1✔
428
429	let cat = a.new_concat(12, &[cat, cat]).unwrap();	1✔
430	assert_eq!(a.atom(cat), b"foobarfoobar");	1✔
431
432	assert_eq!(	1✔
433	a.new_concat(11, &[cat, cat]).unwrap_err().1,	1✔
434	"(internal error) concat passed invalid new_size"	1✔
435	);	1✔
436	assert_eq!(	1✔
437	a.new_concat(13, &[cat, cat]).unwrap_err().1,	1✔
438	"(internal error) concat passed invalid new_size"	1✔
439	);	1✔
440	assert_eq!(	1✔
441	a.new_concat(12, &[atom3, pair]).unwrap_err().1,	1✔
442	"(internal error) concat expected atom, got pair"	1✔
443	);	1✔
444	}	1✔
445
446	#[test]
447	fn test_sexp() {	1✔
448	let mut a = Allocator::new();	1✔
449	let atom1 = a.new_atom(b"f").unwrap();	1✔
450	let atom2 = a.new_atom(b"o").unwrap();	1✔
451	let pair = a.new_pair(atom1, atom2).unwrap();	1✔
452
453	assert_eq!(	1✔
454	match a.sexp(atom1) {	1✔
455	SExp::Atom(_) => 0,	1✔
NEW 456	SExp::Pair(_, _) => 1,	×
457	},
458	0
459	);
460	assert_eq!(	1✔
461	match a.sexp(atom2) {	1✔
462	SExp::Atom(_) => 0,	1✔
NEW 463	SExp::Pair(_, _) => 1,	×
464	},
465	0
466	);
467	assert_eq!(	1✔
468	match a.sexp(pair) {	1✔
NEW 469	SExp::Atom(_) => 0,	×
470	SExp::Pair(_, _) => 1,	1✔
471	},
472	1
473	);
474	}	1✔
475
476	#[test]
477	fn test_concat_limit() {	1✔
478	let mut a = Allocator::new_limited(9, i32::MAX as usize, (i32::MAX - 1) as usize);	1✔
479	let atom1 = a.new_atom(b"f").unwrap();	1✔
480	let atom2 = a.new_atom(b"o").unwrap();	1✔
481	let atom3 = a.new_atom(b"o").unwrap();	1✔
482	let atom4 = a.new_atom(b"b").unwrap();	1✔
483	let atom5 = a.new_atom(b"a").unwrap();	1✔
484	let atom6 = a.new_atom(b"r").unwrap();	1✔
485		1✔
486	// we only have 2 bytes left of allowed heap allocation	1✔
487	assert_eq!(	1✔
488	a.new_concat(6, &[atom1, atom2, atom3, atom4, atom5, atom6])	1✔
489	.unwrap_err()	1✔
490	.1,	1✔
491	"out of memory"	1✔
492	);	1✔
493	let cat = a.new_concat(2, &[atom1, atom2]).unwrap();	1✔
494	assert_eq!(a.atom(cat), b"fo");	1✔
495	}	1✔
496
497	#[cfg(test)]
498	use rstest::rstest;
499
500	#[cfg(test)]
501	#[rstest]	6✔
502	#[case(0.into(), &[])]
503	#[case(1.into(), &[1])]
504	#[case((-1).into(), &[0xff])]
505	#[case(0x80.into(), &[0, 0x80])]
506	#[case(0xff.into(), &[0, 0xff])]
507	#[case(0xffffffff_u64.into(), &[0, 0xff, 0xff, 0xff, 0xff])]
508	fn test_new_number(#[case] num: Number, #[case] expected: &[u8]) {
509	let mut a = Allocator::new();
510
511	// TEST creating the atom from a Number
512	let atom = a.new_number(num.clone()).unwrap();
513
514	// make sure we get back the same number
515	assert_eq!(a.number(atom), num);
516	assert_eq!(a.atom(atom), expected);
517	assert_eq!(number_from_u8(expected), num);
518
519	// TEST creating the atom from a buffer
520	let atom = a.new_atom(expected).unwrap();
521
522	// make sure we get back the same number
523	assert_eq!(a.number(atom), num);
524	assert_eq!(a.atom(atom), expected);
525	assert_eq!(number_from_u8(expected), num);
526	}
527
528	#[test]
529	fn test_checkpoints() {	1✔
530	let mut a = Allocator::new();	1✔
531		1✔
532	let atom1 = a.new_atom(&[1, 2, 3]).unwrap();	1✔
533	assert!(a.atom(atom1) == &[1, 2, 3]);	1✔
534
535	let checkpoint = a.checkpoint();	1✔
536		1✔
537	let atom2 = a.new_atom(&[4, 5, 6]).unwrap();	1✔
538	assert!(a.atom(atom1) == &[1, 2, 3]);	1✔
539	assert!(a.atom(atom2) == &[4, 5, 6]);	1✔
540
541	// at this point we have two atoms and a checkpoint from before the second
542	// atom was created
543
544	// now, restoring the checkpoint state will make atom2 disappear
545
546	a.restore_checkpoint(&checkpoint);	1✔
547		1✔
548	assert!(a.atom(atom1) == &[1, 2, 3]);	1✔
549	let atom3 = a.new_atom(&[6, 7, 8]).unwrap();	1✔
550	assert!(a.atom(atom3) == &[6, 7, 8]);	1✔
551
552	// since atom2 was removed, atom3 should actually be using that slot
553	assert_eq!(atom2, atom3);	1✔
554	}	1✔

Chik-Network / klvm_rs / 9969783315

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous