6926488036

Committed 20 Nov 2023 06:23AM UTC coverage: 92.973%. First build

Build # 6926488036

Build Type

push

github

Committed by

Chik-Network

Commit Message

update 0.3.0

Run Details

81 of 84 new or added lines in 7 files covered. (96.43%)

5147 of 5536 relevant lines covered (92.97%)

140680400.25 hits per line

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

95.74

/src/serde/object_cache.rs

/// `ObjectCache` provides a way to calculate and cache values for each node
/// in a klvm object tree. It can be used to calculate the sha256 tree hash
/// for an object and save the hash for all the child objects for building
/// usage tables, for example.
///
/// It also allows a function that's defined recursively on a klvm tree to
/// have a non-recursive implementation (as it keeps a stack of uncached
/// objects locally).
use std::convert::TryInto;

use crate::allocator::{Allocator, NodePtr, SExp};
type CachedFunction<T> = fn(&mut ObjectCache<T>, &Allocator, NodePtr) -> Option<T>;
use super::bytes32::{hash_blobs, Bytes32};

pub struct ObjectCache<'a, T> {
    cache: Vec<Option<T>>,
    allocator: &'a Allocator,

    /// The function `f` is expected to calculate its T value recursively based
    /// on the T values for the left and right child for a pair. For an atom, the
    /// function f must calculate the T value directly.
    ///
    /// If a pair is passed and one of the children does not have its T value cached
    /// in `ObjectCache` yet, return `None` and f will be called with each child in turn.
    /// Don't recurse in f; that's the point of this structure.
    f: CachedFunction<T>,
}

/// turn a `NodePtr` into a `usize`. Positive values become even indices
/// and negative values become odd indices.

fn node_to_index(node: &NodePtr) -> usize {
    let value = node.0;
    if value < 0 {
        (-value - value - 1) as usize
    } else {
        (value + value) as usize
    }
}

impl<'a, T: Clone> ObjectCache<'a, T> {
    pub fn new(allocator: &'a Allocator, f: CachedFunction<T>) -> Self {
        let cache = vec![];
        Self {
            cache,
            allocator,
            f,
        }
    }

    /// return the function value for this node, either from cache
    /// or by calculating it
    pub fn get_or_calculate(&mut self, node: &NodePtr) -> Option<&T> {
        self.calculate(node);
        self.get_from_cache(node)
    }

    /// return the cached value for this node, or `None`
    fn get_from_cache(&self, node: &NodePtr) -> Option<&T> {
        let index = node_to_index(node);
        if index < self.cache.len() {
            self.cache[index].as_ref()
        } else {
            None
        }
    }

    /// set the cached value for a node
    fn set(&mut self, node: &NodePtr, v: T) {
        let index = node_to_index(node);
        if index >= self.cache.len() {
            self.cache.resize(index + 1, None);
        }
        self.cache[index] = Some(v)
    }

    /// calculate the function's value for the given node, traversing uncached children
    /// as necessary
    fn calculate(&mut self, root_node: &NodePtr) {
        let mut obj_list = vec![*root_node];
        while let Some(node) = obj_list.pop() {
            let v = self.get_from_cache(&node);
            match v {
                Some(_) => {}
                None => match (self.f)(self, self.allocator, node) {
                    None => match self.allocator.sexp(node) {
                        SExp::Pair(left, right) => {
                            obj_list.push(node);
                            obj_list.push(left);
                            obj_list.push(right);
                        }
                        _ => panic!("f returned `None` for atom"),
                    },
                    Some(v) => {
                        self.set(&node, v);
                    }
                },
            }
        }
    }
}

/// calculate the standard `sha256tree` has for a node

pub fn treehash(
    cache: &mut ObjectCache<Bytes32>,
    allocator: &Allocator,
    node: NodePtr,
) -> Option<Bytes32> {
    match allocator.sexp(node) {
        SExp::Pair(left, right) => match cache.get_from_cache(&left) {
            None => None,
            Some(left_value) => cache
                .get_from_cache(&right)
                .map(|right_value| hash_blobs(&[&[2], left_value, right_value])),
        },
        SExp::Atom => Some(hash_blobs(&[&[1], allocator.atom(node)])),
    }
}

/// calculate the serialized length (without backrefs) of a node. This is used
/// to check if using backrefs is actually smaller.

pub fn serialized_length(
    cache: &mut ObjectCache<u64>,
    allocator: &Allocator,
    node: NodePtr,
) -> Option<u64> {
    match allocator.sexp(node) {
        SExp::Pair(left, right) => match cache.get_from_cache(&left) {
            None => None,
            Some(left_value) => cache.get_from_cache(&right).map(|right_value| {
                1_u64
                    .saturating_add(*left_value)
                    .saturating_add(*right_value)
            }),
        },
        SExp::Atom => {
            let buf = allocator.atom(node);
            let lb: u64 = buf.len().try_into().unwrap_or(u64::MAX);
            Some(if lb == 0 || (lb == 1 && buf[0] < 128) {
                1
            } else if lb < 0x40 {
                1 + lb
            } else if lb < 0x2000 {
                2 + lb
            } else if lb < 0x100000 {
                3 + lb
            } else if lb < 0x8000000 {
                4 + lb
            } else {
                5 + lb
            })
        }
    }
}

#[cfg(test)]
use std::cmp::max;

#[cfg(test)]
use std::fmt::Debug;

#[cfg(test)]
use std::io::Cursor;

#[cfg(test)]
use hex::FromHex;

#[cfg(test)]
use crate::serde::de::node_from_stream;

/// calculate the depth of a node. Used for tests

#[cfg(test)]
fn calculate_depth_simple(
    cache: &mut ObjectCache<usize>,
    allocator: &Allocator,
    node: NodePtr,
) -> Option<usize> {
    match allocator.sexp(node) {
        SExp::Pair(left, right) => match cache.get_from_cache(&left) {
            None => None,
            Some(left_value) => cache
                .get_from_cache(&right)
                .map(|right_value| 1 + max(*left_value, *right_value)),
        },
        SExp::Atom => Some(0),
    }
}

#[cfg(test)]
fn check_cached_function<T>(obj_as_hex: &str, expected_value: T, f: CachedFunction<T>)
where
    T: Clone + Eq + Debug,
{
    let mut allocator = Allocator::new();
    let blob: Vec<u8> = Vec::from_hex(obj_as_hex).unwrap();
    let mut cursor: Cursor<&[u8]> = Cursor::new(&blob);
    let obj = node_from_stream(&mut allocator, &mut cursor).unwrap();
    let mut oc = ObjectCache::new(&allocator, f);

    assert_eq!(oc.get_from_cache(&obj), None);

    oc.calculate(&obj);

    assert_eq!(oc.get_from_cache(&obj), Some(&expected_value));

    assert_eq!(oc.get_or_calculate(&obj).unwrap().clone(), expected_value);

    assert_eq!(oc.get_from_cache(&obj), Some(&expected_value));

    // do it again, but the simple way
    let mut oc = ObjectCache::new(&allocator, f);
    assert_eq!(oc.get_or_calculate(&obj).unwrap().clone(), expected_value);
}

#[test]
fn test_depths_cache() {
    let check = |a, b| check_cached_function(a, b, calculate_depth_simple);
    check("01", 0); // 1
    check("ff83666f6f83626172", 1); // (foo . bar)
    check("ff83666f6fff8362617280", 2); // (foo bar)
    check("ffff0102ff0304", 2); // ((1 . 2) . (3 . 4))
    check("ff01ff02ff03ff04ff05ff0680", 6); // (1 2 3 4 5 6)
}

#[test]
fn test_treehash() {
    let check = |a, b| check_cached_function(a, Bytes32::from_hex(b).unwrap(), treehash);
    check(
        "ff83666f6f83626172",
        "c518e45ae6a7b4146017b7a1d81639051b132f1f5572ce3088a3898a9ed1280b",
    ); // (foo . bar)
    check(
        "ff83666f6fff8362617280",
        "c97d97cc81100a4980080ba81ff1ba3985f7cff1db9d41d904b9d512bb875144",
    ); // (foo bar)
    check(
        "ffff0102ff0304",
        "2824018d148bc6aed0847e2c86aaa8a5407b916169f15b12cea31fa932fc4c8d",
    ); // ((1 . 2) . (3 . 4))
    check(
        "ff01ff02ff03ff04ff05ff0680",
        "65de5098d18bebd62aee37de32f0b62d1803d9c7c48f10dca25501243d7a0392",
    ); // (1 2 3 4 5 6)
}

#[test]
fn test_serialized_length() {
    let check = |a, b| check_cached_function(a, b, serialized_length);
    check("ff83666f6f83626172", 9); // (foo . bar)
    check("ff83666f6fff8362617280", 11); // (foo bar)
    check("ffff0102ff0304", 7); // ((1 . 2) . (3 . 4))
    check("ff01ff02ff03ff04ff05ff0680", 13); // (1 2 3 4 5 6)
}

#[test]
fn test_node_to_index() {
    assert_eq!(node_to_index(&NodePtr(0)), 0);
    assert_eq!(node_to_index(&NodePtr(1)), 2);
    assert_eq!(node_to_index(&NodePtr(2)), 4);
    assert_eq!(node_to_index(&NodePtr(-1)), 1);
    assert_eq!(node_to_index(&NodePtr(-2)), 3);
}

// this test takes a very long time (>60s) in debug mode, so it only runs in release mode

#[cfg(not(debug_assertions))]
#[test]
fn test_very_long_list() {
    // in this test, we check that `treehash` and `serialized_length` can handle very deep trees that
    // would normally blow out the stack. It's expensive to create such a long list, so we do both
    // tests here so we only have to to create the list once

    const LIST_SIZE: u64 = 20_000_000;
    let mut allocator = Allocator::new();
    let mut top = allocator.null();
    for _ in 0..LIST_SIZE {
        let atom = allocator.one();
        top = allocator.new_pair(atom, top).unwrap();
    }

    let expected_value = LIST_SIZE * 2 + 1;
    let mut oc = ObjectCache::new(&allocator, serialized_length);
    assert_eq!(oc.get_or_calculate(&top).unwrap().clone(), expected_value);

    let expected_value =
        <[u8; 32]>::from_hex("a168fce695099a30c0745075e6db3722ed7f059e0d7cc4d7e7504e215db5017b")
            .unwrap();
    let mut oc = ObjectCache::new(&allocator, treehash);
    assert_eq!(oc.get_or_calculate(&top).unwrap().clone(), expected_value);
}

1	/// `ObjectCache` provides a way to calculate and cache values for each node
2	/// in a klvm object tree. It can be used to calculate the sha256 tree hash
3	/// for an object and save the hash for all the child objects for building
4	/// usage tables, for example.
5	///
6	/// It also allows a function that's defined recursively on a klvm tree to
7	/// have a non-recursive implementation (as it keeps a stack of uncached
8	/// objects locally).
9	use std::convert::TryInto;
10
11	use crate::allocator::{Allocator, NodePtr, SExp};
12	type CachedFunction<T> = fn(&mut ObjectCache<T>, &Allocator, NodePtr) -> Option<T>;
13	use super::bytes32::{hash_blobs, Bytes32};
14
15	pub struct ObjectCache<'a, T> {
16	cache: Vec<Option<T>>,
17	allocator: &'a Allocator,
18
19	/// The function `f` is expected to calculate its T value recursively based
20	/// on the T values for the left and right child for a pair. For an atom, the
21	/// function f must calculate the T value directly.
22	///
23	/// If a pair is passed and one of the children does not have its T value cached
24	/// in `ObjectCache` yet, return `None` and f will be called with each child in turn.
25	/// Don't recurse in f; that's the point of this structure.
26	f: CachedFunction<T>,
27	}
28
29	/// turn a `NodePtr` into a `usize`. Positive values become even indices
30	/// and negative values become odd indices.
31
32	fn node_to_index(node: &NodePtr) -> usize {	280,003,536✔
33	let value = node.0;	280,003,536✔
34	if value < 0 {	280,003,536✔
35	(-value - value - 1) as usize	120,001,612✔
36	} else {
37	(value + value) as usize	160,001,924✔
38	}
39	}	280,003,536✔
40
41	impl<'a, T: Clone> ObjectCache<'a, T> {
42	pub fn new(allocator: &'a Allocator, f: CachedFunction<T>) -> Self {	50✔
43	let cache = vec![];	50✔
44	Self {	50✔
45	cache,	50✔
46	allocator,	50✔
47	f,	50✔
48	}	50✔
49	}	50✔
50
51	/// return the function value for this node, either from cache
52	/// or by calculating it
53	pub fn get_or_calculate(&mut self, node: &NodePtr) -> Option<&T> {	154✔
54	self.calculate(node);	154✔
55	self.get_from_cache(node)	154✔
56	}	154✔
57
58	/// return the cached value for this node, or `None`
59	fn get_from_cache(&self, node: &NodePtr) -> Option<&T> {	240,002,798✔
60	let index = node_to_index(node);	240,002,798✔
61	if index < self.cache.len() {	240,002,798✔
62	self.cache[index].as_ref()	120,002,372✔
63	} else {
64	None	120,000,426✔
65	}
66	}	240,002,798✔
67
68	/// set the cached value for a node
69	fn set(&mut self, node: &NodePtr, v: T) {	40,000,733✔
70	let index = node_to_index(node);	40,000,733✔
71	if index >= self.cache.len() {	40,000,733✔
72	self.cache.resize(index + 1, None);	40,000,117✔
73	}	40,000,117✔
74	self.cache[index] = Some(v)	40,000,733✔
75	}	40,000,733✔
76
77	/// calculate the function's value for the given node, traversing uncached children
78	/// as necessary
79	fn calculate(&mut self, root_node: &NodePtr) {	167✔
80	let mut obj_list = vec![*root_node];	167✔
81	while let Some(node) = obj_list.pop() {	120,001,552✔
82	let v = self.get_from_cache(&node);	120,001,385✔
83	match v {	120,001,385✔
84	Some(_) => {}	40,000,246✔
85	None => match (self.f)(self, self.allocator, node) {	80,001,139✔
86	None => match self.allocator.sexp(node) {	40,000,406✔
87	SExp::Pair(left, right) => {	40,000,406✔
88	obj_list.push(node);	40,000,406✔
89	obj_list.push(left);	40,000,406✔
90	obj_list.push(right);	40,000,406✔
91	}	40,000,406✔
NEW 92	_ => panic!("f returned `None` for atom"),	×
93	},
94	Some(v) => {	40,000,733✔
95	self.set(&node, v);	40,000,733✔
96	}	40,000,733✔
97	},
98	}
99	}
100	}	167✔
101	}
102
103	/// calculate the standard `sha256tree` has for a node
104
105	pub fn treehash(	40,000,592✔
106	cache: &mut ObjectCache<Bytes32>,	40,000,592✔
107	allocator: &Allocator,	40,000,592✔
108	node: NodePtr,	40,000,592✔
109	) -> Option<Bytes32> {	40,000,592✔
110	match allocator.sexp(node) {	40,000,592✔
111	SExp::Pair(left, right) => match cache.get_from_cache(&left) {	40,000,424✔
112	None => None,	20,000,210✔
113	Some(left_value) => cache	20,000,214✔
114	.get_from_cache(&right)	20,000,214✔
115	.map(\|right_value\| hash_blobs(&[&[2], left_value, right_value])),	20,000,214✔
116	},
117	SExp::Atom => Some(hash_blobs(&[&[1], allocator.atom(node)])),	168✔
118	}
119	}	40,000,592✔
120
121	/// calculate the serialized length (without backrefs) of a node. This is used
122	/// to check if using backrefs is actually smaller.
123
124	pub fn serialized_length(	40,000,465✔
125	cache: &mut ObjectCache<u64>,	40,000,465✔
126	allocator: &Allocator,	40,000,465✔
127	node: NodePtr,	40,000,465✔
128	) -> Option<u64> {	40,000,465✔
129	match allocator.sexp(node) {	40,000,465✔
130	SExp::Pair(left, right) => match cache.get_from_cache(&left) {	40,000,340✔
131	None => None,	20,000,170✔
132	Some(left_value) => cache.get_from_cache(&right).map(\|right_value\| {	20,000,170✔
133	1_u64	20,000,170✔
134	.saturating_add(*left_value)	20,000,170✔
135	.saturating_add(*right_value)	20,000,170✔
136	}),	20,000,170✔
137	},
138	SExp::Atom => {
139	let buf = allocator.atom(node);	125✔
140	let lb: u64 = buf.len().try_into().unwrap_or(u64::MAX);	125✔
141	Some(if lb == 0 \|\| (lb == 1 && buf[0] < 128) {	125✔
142	1	41✔
143	} else if lb < 0x40 {	84✔
144	1 + lb	84✔
145	} else if lb < 0x2000 {	×
146	2 + lb	×
147	} else if lb < 0x100000 {	×
148	3 + lb	×
149	} else if lb < 0x8000000 {	×
150	4 + lb	×
151	} else {
152	5 + lb	×
153	})
154	}
155	}
156	}	40,000,465✔
157
158	#[cfg(test)]
159	use std::cmp::max;
160
161	#[cfg(test)]
162	use std::fmt::Debug;
163
164	#[cfg(test)]
165	use std::io::Cursor;
166
167	#[cfg(test)]
168	use hex::FromHex;
169
170	#[cfg(test)]
171	use crate::serde::de::node_from_stream;
172
173	/// calculate the depth of a node. Used for tests
174
175	#[cfg(test)]
176	fn calculate_depth_simple(	82✔
177	cache: &mut ObjectCache<usize>,	82✔
178	allocator: &Allocator,	82✔
179	node: NodePtr,	82✔
180	) -> Option<usize> {	82✔
181	match allocator.sexp(node) {	82✔
182	SExp::Pair(left, right) => match cache.get_from_cache(&left) {	48✔
183	None => None,	24✔
184	Some(left_value) => cache	24✔
185	.get_from_cache(&right)	24✔
186	.map(\|right_value\| 1 + max(left_value, right_value)),	24✔
187	},
188	SExp::Atom => Some(0),	34✔
189	}
190	}	82✔
191
192	#[cfg(test)]
193	fn check_cached_function<T>(obj_as_hex: &str, expected_value: T, f: CachedFunction<T>)	13✔
194	where	13✔
195	T: Clone + Eq + Debug,	13✔
196	{	13✔
197	let mut allocator = Allocator::new();	13✔
198	let blob: Vec<u8> = Vec::from_hex(obj_as_hex).unwrap();	13✔
199	let mut cursor: Cursor<&[u8]> = Cursor::new(&blob);	13✔
200	let obj = node_from_stream(&mut allocator, &mut cursor).unwrap();	13✔
201	let mut oc = ObjectCache::new(&allocator, f);	13✔
202		13✔
203	assert_eq!(oc.get_from_cache(&obj), None);	13✔
204
205	oc.calculate(&obj);	13✔
206		13✔
207	assert_eq!(oc.get_from_cache(&obj), Some(&expected_value));	13✔
208
209	assert_eq!(oc.get_or_calculate(&obj).unwrap().clone(), expected_value);	13✔
210
211	assert_eq!(oc.get_from_cache(&obj), Some(&expected_value));	13✔
212
213	// do it again, but the simple way
214	let mut oc = ObjectCache::new(&allocator, f);	13✔
215	assert_eq!(oc.get_or_calculate(&obj).unwrap().clone(), expected_value);	13✔
216	}	13✔
217
218	#[test]	1✔
219	fn test_depths_cache() {	1✔
220	let check = \|a, b\| check_cached_function(a, b, calculate_depth_simple);	5✔
221	check("01", 0); // 1	1✔
222	check("ff83666f6f83626172", 1); // (foo . bar)	1✔
223	check("ff83666f6fff8362617280", 2); // (foo bar)	1✔
224	check("ffff0102ff0304", 2); // ((1 . 2) . (3 . 4))	1✔
225	check("ff01ff02ff03ff04ff05ff0680", 6); // (1 2 3 4 5 6)	1✔
226	}	1✔
227
228	#[test]	1✔
229	fn test_treehash() {	1✔
230	let check = \|a, b\| check_cached_function(a, Bytes32::from_hex(b).unwrap(), treehash);	4✔
231	check(	1✔
232	"ff83666f6f83626172",	1✔
233	"c518e45ae6a7b4146017b7a1d81639051b132f1f5572ce3088a3898a9ed1280b",	1✔
234	); // (foo . bar)	1✔
235	check(	1✔
236	"ff83666f6fff8362617280",	1✔
237	"c97d97cc81100a4980080ba81ff1ba3985f7cff1db9d41d904b9d512bb875144",	1✔
238	); // (foo bar)	1✔
239	check(	1✔
240	"ffff0102ff0304",	1✔
241	"2824018d148bc6aed0847e2c86aaa8a5407b916169f15b12cea31fa932fc4c8d",	1✔
242	); // ((1 . 2) . (3 . 4))	1✔
243	check(	1✔
244	"ff01ff02ff03ff04ff05ff0680",	1✔
245	"65de5098d18bebd62aee37de32f0b62d1803d9c7c48f10dca25501243d7a0392",	1✔
246	); // (1 2 3 4 5 6)	1✔
247	}	1✔
248
249	#[test]	1✔
250	fn test_serialized_length() {	1✔
251	let check = \|a, b\| check_cached_function(a, b, serialized_length);	4✔
252	check("ff83666f6f83626172", 9); // (foo . bar)	1✔
253	check("ff83666f6fff8362617280", 11); // (foo bar)	1✔
254	check("ffff0102ff0304", 7); // ((1 . 2) . (3 . 4))	1✔
255	check("ff01ff02ff03ff04ff05ff0680", 13); // (1 2 3 4 5 6)	1✔
256	}	1✔
257
258	#[test]	1✔
259	fn test_node_to_index() {	1✔
260	assert_eq!(node_to_index(&NodePtr(0)), 0);	1✔
261	assert_eq!(node_to_index(&NodePtr(1)), 2);	1✔
262	assert_eq!(node_to_index(&NodePtr(2)), 4);	1✔
263	assert_eq!(node_to_index(&NodePtr(-1)), 1);	1✔
264	assert_eq!(node_to_index(&NodePtr(-2)), 3);	1✔
265	}	1✔
266
267	// this test takes a very long time (>60s) in debug mode, so it only runs in release mode
268
269	#[cfg(not(debug_assertions))]
270	#[test]	1✔
271	fn test_very_long_list() {	1✔
272	// in this test, we check that `treehash` and `serialized_length` can handle very deep trees that	1✔
273	// would normally blow out the stack. It's expensive to create such a long list, so we do both	1✔
274	// tests here so we only have to to create the list once	1✔
275		1✔
276	const LIST_SIZE: u64 = 20_000_000;	1✔
277	let mut allocator = Allocator::new();	1✔
278	let mut top = allocator.null();	1✔
279	for _ in 0..LIST_SIZE {	20,000,001✔
280	let atom = allocator.one();	20,000,000✔
281	top = allocator.new_pair(atom, top).unwrap();	20,000,000✔
282	}	20,000,000✔
283
284	let expected_value = LIST_SIZE * 2 + 1;	1✔
285	let mut oc = ObjectCache::new(&allocator, serialized_length);	1✔
286	assert_eq!(oc.get_or_calculate(&top).unwrap().clone(), expected_value);	1✔
287
288	let expected_value =	1✔
289	<[u8; 32]>::from_hex("a168fce695099a30c0745075e6db3722ed7f059e0d7cc4d7e7504e215db5017b")	1✔
290	.unwrap();	1✔
291	let mut oc = ObjectCache::new(&allocator, treehash);	1✔
292	assert_eq!(oc.get_or_calculate(&top).unwrap().clone(), expected_value);	1✔
293	}	1✔

Chik-Network / klvm_rs / 6926488036

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