GRIN/grin-node
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
goblin
grin-node/store/tests/prune_list.rs
T
John Tromp 53414ae105 Fixmmr part2 (#3666) 
* use 0-based positions in  methods pmmr_leaf_to_insertion_index and bintree_postorder_height; add round_up_to_leaf_pos method

* use 0-based positions in method insertion_to_pmmr_index

* use 0-based positions in method is_leaf

* use 0-based positions in method family()

* use 0-based positions in method is_left_sibling

* use 0-based positions in method family_branch

* use 0-based positions in methods bintree_{left,right}most

* use 0-based positions in method bintree_pos_iter

* use 0-based positions in method bintree_range

* use 0-based positions in method bintree_leaf_pos_iter

* rename last_pos in MMR related structs to size

* use 0-based positions in method prune

* use 0-based positions in method push and apply_output return value

* use 0-based position argument of method merkle_proof

* use 0-based outputs in method pmmr::peaks

* fix peaks() code comments

* refix peaks() code comments

* use 0-based positions in method get_peak_from_file

* use 0-based positions in methods get_data_from_file

* use 0-based positions in methods get_from_file

* use 0-based positions in methods get_data

* use 0-based positions in methods get_hash

* use 0-based positions in method peak_path

* use 0-based positions in method bag_the_rhs

* use 0-based positions in method Backend::remove

* use 0-based positions in method leaf_pos_iter

* use 0-based positions in method self.LeafSet::includes

* use 0-based positions in methods self.LeafSet::{add,remove}

* use 0-based positions in methods is_pruned,is_pruned_root,is_compacted

* use 0-based positions in methods PruneList::append

* use 0-based positions in methods append_pruned_subtree

* use 0-based positions in method calculate_next_leaf_shift

* use 0-based positions in method append_single

* use 0-based positions in method calculate_next_shift

* use 0-based positions in method segment_pos_range

* use 0-based positions in method reconstruct_root

* use 0-based positions in method validate_with

* use 0-based positions in method validate

* rename size (formerly last_pos) to mmr_size

* use 0-based positions in Segment's hash_pos and leaf_pos

* minimize use of saturating_sub(1) and rename some pos/idx to size

* use 0-based positions in methods get_output_pos

* use 0-based positions in method get_unspent_output_at

* use 0-based positions in method get_header_hash

* use 0-based positions in methods MerkleProof::verify{,_consume}

* use 0-based positions in method cleanup_subtree

* don't allow 0 in prunelist bitmap

* use 0-based positions in methods get_{,leaf_}shift

* rename some 1-based pos to pos1; identify TODO

* Address yeastplume's PR review comments
2021-11-26 11:25:10 +00:00

387 lines
10 KiB
Rust
Raw Permalink Blame History

// Copyright 2021 The Grin Developers
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
use grin_store as store;
use crate::store::prune_list::PruneList;
#[test]
fn test_is_pruned() {
let mut pl = PruneList::empty();
assert_eq!(pl.len(), 0);
assert_eq!(pl.is_pruned(0), false);
assert_eq!(pl.is_pruned(1), false);
assert_eq!(pl.is_pruned(2), false);
pl.append(1);
pl.flush().unwrap();
assert_eq!(pl.iter().collect::<Vec<_>>(), [2]);
assert_eq!(pl.is_pruned(0), false);
assert_eq!(pl.is_pruned(1), true);
assert_eq!(pl.is_pruned(2), false);
assert_eq!(pl.is_pruned(3), false);
let mut pl = PruneList::empty();
pl.append(0);
pl.append(1);
pl.flush().unwrap();
assert_eq!(pl.len(), 1);
assert_eq!(pl.iter().collect::<Vec<_>>(), [3]);
assert_eq!(pl.is_pruned(0), true);
assert_eq!(pl.is_pruned(1), true);
assert_eq!(pl.is_pruned(2), true);
assert_eq!(pl.is_pruned(3), false);
pl.append(3);
// Flushing the prune_list removes any individual leaf positions.
// This assumes we will track these outside the prune_list via the leaf_set.
pl.flush().unwrap();
assert_eq!(pl.len(), 2);
assert_eq!(pl.to_vec(), [3, 4]);
assert_eq!(pl.is_pruned(0), true);
assert_eq!(pl.is_pruned(1), true);
assert_eq!(pl.is_pruned(2), true);
assert_eq!(pl.is_pruned(3), true);
assert_eq!(pl.is_pruned(4), false);
}
#[test]
fn test_get_leaf_shift() {
let mut pl = PruneList::empty();
// start with an empty prune list (nothing shifted)
assert_eq!(pl.len(), 0);
assert_eq!(pl.get_leaf_shift(4), 0);
assert_eq!(pl.get_leaf_shift(1), 0);
assert_eq!(pl.get_leaf_shift(2), 0);
assert_eq!(pl.get_leaf_shift(3), 0);
// now add a single leaf pos to the prune list
// leaves will not shift shift anything
// we only start shifting after pruning a parent
pl.append(0);
pl.flush().unwrap();
assert_eq!(pl.iter().collect::<Vec<_>>(), [1]);
assert_eq!(pl.get_leaf_shift(0), 0);
assert_eq!(pl.get_leaf_shift(1), 0);
assert_eq!(pl.get_leaf_shift(2), 0);
assert_eq!(pl.get_leaf_shift(3), 0);
// now add the sibling leaf pos (pos 1) which will prune the parent
// at pos 2 this in turn will "leaf shift" the leaf at pos 2 by 2
pl.append(1);
pl.flush().unwrap();
assert_eq!(pl.len(), 1);
assert_eq!(pl.get_leaf_shift(0), 0);
assert_eq!(pl.get_leaf_shift(1), 0);
assert_eq!(pl.get_leaf_shift(2), 2);
assert_eq!(pl.get_leaf_shift(3), 2);
assert_eq!(pl.get_leaf_shift(4), 2);
// now prune an additional leaf at pos 3
// leaf offset of subsequent pos will be 2
// 00100120
pl.append(3);
pl.flush().unwrap();
assert_eq!(pl.len(), 2);
assert_eq!(pl.iter().collect::<Vec<_>>(), [3, 4]);
assert_eq!(pl.get_leaf_shift(0), 0);
assert_eq!(pl.get_leaf_shift(1), 0);
assert_eq!(pl.get_leaf_shift(2), 2);
assert_eq!(pl.get_leaf_shift(3), 2);
assert_eq!(pl.get_leaf_shift(4), 2);
assert_eq!(pl.get_leaf_shift(5), 2);
assert_eq!(pl.get_leaf_shift(6), 2);
assert_eq!(pl.get_leaf_shift(7), 2);
// now prune the sibling at pos 4
// the two smaller subtrees (pos 2 and pos 5) are rolled up to larger subtree
// (pos 6) the leaf offset is now 4 to cover entire subtree containing first
// 4 leaves 00100120
pl.append(4);
pl.flush().unwrap();
assert_eq!(pl.len(), 1);
assert_eq!(pl.iter().collect::<Vec<_>>(), [7]);
assert_eq!(pl.get_leaf_shift(0), 0);
assert_eq!(pl.get_leaf_shift(1), 0);
assert_eq!(pl.get_leaf_shift(2), 0);
assert_eq!(pl.get_leaf_shift(3), 0);
assert_eq!(pl.get_leaf_shift(4), 0);
assert_eq!(pl.get_leaf_shift(5), 0);
assert_eq!(pl.get_leaf_shift(6), 4);
assert_eq!(pl.get_leaf_shift(7), 4);
assert_eq!(pl.get_leaf_shift(8), 4);
// now check we can prune some unconnected nodes
// and that leaf_shift is correct for various pos
let mut pl = PruneList::empty();
pl.append(3);
pl.append(4);
pl.append(10);
pl.append(11);
pl.flush().unwrap();
assert_eq!(pl.len(), 2);
assert_eq!(pl.iter().collect::<Vec<_>>(), [6, 13]);
assert_eq!(pl.get_leaf_shift(1), 0);
assert_eq!(pl.get_leaf_shift(3), 0);
assert_eq!(pl.get_leaf_shift(7), 2);
assert_eq!(pl.get_leaf_shift(8), 2);
assert_eq!(pl.get_leaf_shift(12), 4);
assert_eq!(pl.get_leaf_shift(13), 4);
}
#[test]
fn test_get_shift() {
let mut pl = PruneList::empty();
assert!(pl.is_empty());
assert_eq!(pl.get_shift(0), 0);
assert_eq!(pl.get_shift(1), 0);
assert_eq!(pl.get_shift(2), 0);
// prune a single leaf node
// pruning only a leaf node does not shift any subsequent pos
// we will only start shifting when a parent can be pruned
pl.append(0);
pl.flush().unwrap();
assert_eq!(pl.iter().collect::<Vec<_>>(), [1]);
assert_eq!(pl.get_shift(0), 0);
assert_eq!(pl.get_shift(1), 0);
assert_eq!(pl.get_shift(2), 0);
pl.append(1);
pl.flush().unwrap();
assert_eq!(pl.iter().collect::<Vec<_>>(), [3]);
assert_eq!(pl.get_shift(0), 0);
assert_eq!(pl.get_shift(1), 0);
assert_eq!(pl.get_shift(2), 2);
assert_eq!(pl.get_shift(3), 2);
assert_eq!(pl.get_shift(4), 2);
assert_eq!(pl.get_shift(5), 2);
pl.append(3);
pl.flush().unwrap();
assert_eq!(pl.iter().collect::<Vec<_>>(), [3, 4]);
assert_eq!(pl.get_shift(0), 0);
assert_eq!(pl.get_shift(1), 0);
assert_eq!(pl.get_shift(2), 2);
assert_eq!(pl.get_shift(3), 2);
assert_eq!(pl.get_shift(4), 2);
assert_eq!(pl.get_shift(5), 2);
pl.append(4);
pl.flush().unwrap();
assert_eq!(pl.iter().collect::<Vec<_>>(), [7]);
assert_eq!(pl.get_shift(0), 0);
assert_eq!(pl.get_shift(1), 0);
assert_eq!(pl.get_shift(2), 0);
assert_eq!(pl.get_shift(3), 0);
assert_eq!(pl.get_shift(4), 0);
assert_eq!(pl.get_shift(5), 0);
assert_eq!(pl.get_shift(6), 6);
assert_eq!(pl.get_shift(7), 6);
assert_eq!(pl.get_shift(8), 6);
// prune a bunch more
for x in 5..999 {
if !pl.is_pruned(x) {
pl.append(x);
}
}
pl.flush().unwrap();
// and check we shift by a large number (hopefully the correct number...)
assert_eq!(pl.get_shift(1009), 996);
// now check we can do some sparse pruning
let mut pl = PruneList::empty();
pl.append(3);
pl.append(4);
pl.append(7);
pl.append(8);
pl.flush().unwrap();
assert_eq!(pl.iter().collect::<Vec<_>>(), [6, 10]);
assert_eq!(pl.get_shift(0), 0);
assert_eq!(pl.get_shift(1), 0);
assert_eq!(pl.get_shift(2), 0);
assert_eq!(pl.get_shift(3), 0);
assert_eq!(pl.get_shift(4), 0);
assert_eq!(pl.get_shift(5), 2);
assert_eq!(pl.get_shift(6), 2);
assert_eq!(pl.get_shift(7), 2);
assert_eq!(pl.get_shift(8), 2);
assert_eq!(pl.get_shift(9), 4);
assert_eq!(pl.get_shift(10), 4);
assert_eq!(pl.get_shift(11), 4);
}
#[test]
pub fn test_iter() {
let mut pl = PruneList::empty();
pl.append(0);
pl.append(1);
pl.append(3);
assert_eq!(pl.iter().collect::<Vec<_>>(), [3, 4]);
let mut pl = PruneList::empty();
pl.append(0);
pl.append(1);
pl.append(4);
assert_eq!(pl.iter().collect::<Vec<_>>(), [3, 5]);
}
#[test]
pub fn test_pruned_bintree_range_iter() {
let mut pl = PruneList::empty();
pl.append(0);
pl.append(1);
pl.append(3);
assert_eq!(
pl.pruned_bintree_range_iter().collect::<Vec<_>>(),
[1..4, 4..5]
);
let mut pl = PruneList::empty();
pl.append(0);
pl.append(1);
pl.append(4);
assert_eq!(
pl.pruned_bintree_range_iter().collect::<Vec<_>>(),
[1..4, 5..6]
);
}
#[test]
pub fn test_unpruned_iter() {
let pl = PruneList::empty();
assert_eq!(pl.unpruned_iter(5).collect::<Vec<_>>(), [1, 2, 3, 4, 5]);
let mut pl = PruneList::empty();
pl.append(1);
assert_eq!(pl.iter().collect::<Vec<_>>(), [2]);
assert_eq!(pl.pruned_bintree_range_iter().collect::<Vec<_>>(), [2..3]);
assert_eq!(pl.unpruned_iter(4).collect::<Vec<_>>(), [1, 3, 4]);
let mut pl = PruneList::empty();
pl.append(1);
pl.append(3);
pl.append(4);
assert_eq!(pl.iter().collect::<Vec<_>>(), [2, 6]);
assert_eq!(
pl.pruned_bintree_range_iter().collect::<Vec<_>>(),
[2..3, 4..7]
);
assert_eq!(pl.unpruned_iter(9).collect::<Vec<_>>(), [1, 3, 7, 8, 9]);
}
#[test]
fn test_unpruned_leaf_iter() {
let pl = PruneList::empty();
assert_eq!(
pl.unpruned_leaf_iter(8).collect::<Vec<_>>(),
[1, 2, 4, 5, 8]
);
let mut pl = PruneList::empty();
pl.append(1);
assert_eq!(pl.iter().collect::<Vec<_>>(), [2]);
assert_eq!(pl.pruned_bintree_range_iter().collect::<Vec<_>>(), [2..3]);
assert_eq!(pl.unpruned_leaf_iter(5).collect::<Vec<_>>(), [1, 4, 5]);
let mut pl = PruneList::empty();
pl.append(1);
pl.append(3);
pl.append(4);
assert_eq!(pl.iter().collect::<Vec<_>>(), [2, 6]);
assert_eq!(
pl.pruned_bintree_range_iter().collect::<Vec<_>>(),
[2..3, 4..7]
);
assert_eq!(pl.unpruned_leaf_iter(9).collect::<Vec<_>>(), [1, 8, 9]);
}
pub fn test_append_pruned_subtree() {
let mut pl = PruneList::empty();
// append a pruned leaf pos (shift and leaf shift are unaffected).
pl.append(0);
assert_eq!(pl.to_vec(), [1]);
assert_eq!(pl.get_shift(1), 0);
assert_eq!(pl.get_leaf_shift(1), 0);
pl.append(2);
// subtree beneath root at 2 is pruned
// pos 3 is shifted by 2 pruned hashes [1, 2]
// pos 3 is shifted by 2 leaves [1, 2]
assert_eq!(pl.to_vec(), [3]);
assert_eq!(pl.get_shift(3), 2);
assert_eq!(pl.get_leaf_shift(3), 2);
// append another pruned subtree (ancester of previous one)
pl.append(6);
// subtree beneath root at 6 is pruned
// pos 7 is shifted by 6 pruned hashes [1, 2, 3, 4, 5, 6]
// pos 3 is shifted by 4 leaves [1, 2, 4, 5]
assert_eq!(pl.to_vec(), [7]);
assert_eq!(pl.get_shift(7), 6);
assert_eq!(pl.get_leaf_shift(7), 4);
// now append another pruned leaf pos
pl.append(7);
// additional pruned leaf does not affect the shift or leaf shift
// pos 8 is shifted by 6 pruned hashes [1, 2, 3, 4, 5, 6]
// pos 8 is shifted by 4 leaves [1, 2, 4, 5]
assert_eq!(pl.to_vec(), [7, 8]);
assert_eq!(pl.get_shift(8), 6);
assert_eq!(pl.get_leaf_shift(8), 4);
}
#[test]
fn test_recreate_prune_list() {
let mut pl = PruneList::empty();
pl.append(3);
pl.append(4);
pl.append(10);
let pl2 = PruneList::new(None, vec![4, 5, 11].into_iter().collect());
assert_eq!(pl.to_vec(), pl2.to_vec());
assert_eq!(pl.shift_cache(), pl2.shift_cache());
assert_eq!(pl.leaf_shift_cache(), pl2.leaf_shift_cache());
let pl3 = PruneList::new(None, vec![6, 11].into_iter().collect());
assert_eq!(pl.to_vec(), pl3.to_vec());
assert_eq!(pl.shift_cache(), pl3.shift_cache());
assert_eq!(pl.leaf_shift_cache(), pl3.leaf_shift_cache());
}
Reference in New Issue View Git Blame Copy Permalink