Different Results when Checking Same Vector?

help
1

I've been stuck on this issue for a while, and was wondering if any of you had any insight. I have a Tree struct, which has a method contains(x: &T), which returns true if one of the leaves of the tree is equal to x. So I create a Vec<T> in a test function and make sure that every element of this vector is in my Tree. Okay good, Calling MerkleTree::contains on each element of x returned true. Now I pass this vector into MerkleTree::prune where the exact same test is performed, only this time it returns false.

This issue occurs even when I don't call contains on all the elements before passing them to prune, ruling out my suspicion that contains was somehow mutating the elements of my vector. I'm sort of at a loss now, and so was wondering if any of you had encountered a similiar issue. I snipped my code and copied it below so you could get a better look:

#[test]
fn test_func() {

  /*let m_tree = MerkleTree::construct(...)
    ...
    Snip */

    let to_check = vec!(11.to_string(), 101.to_string());

    /* This returns true! */
    for element in to_check {
        assert!(m_tree.contains(&element).unwrap());
    }

    /* This method does the same thing as above, but it panics at the assert!*/
    m_tree.prune(&to_check)
}

impl<T: Ord + Clone> MerkleTree<T> {

    /* Snip */


    pub fn prune(&mut self, to_keep: &Vec<T>) -> bool {
    
        if to_keep.len() <= 0 { debug_assert!(false, "To_keep has length less than 1"); return false; } 

        /*This returns false!*/
        for element in to_keep {
            if !self.contains(&element).unwrap() { 
                assert!(false);
                return false; 
            }
        }

        self._prune(to_keep)
    
    }

    /* Snip */

}

Here is the link to my Repo where the non-snipped code is if any of you want more info: https://github.com/rileylyman/newton/tree/master/src

2

In the second unit test in the repo, there’s this:

for i in (2..1001).step_by(2) {
        if i % 2 == 0 {
            println!("{}", i);
            assert!(!m_tree.contains(&i.to_string()).unwrap());
        }
    }

Why is that asserting that even numbers aren’t present but then later in the test it calls prune() with 10 and 100 (part of the commented out code) and expects prune() to return true? Perhaps I’m overlooking something and this is a stupid question :slight_smile:.

Maybe you can post more details about the test failure (eg panic location) with respect to the real code.

3

Oops, that's my mistake. I hadn't pushed up the tests on my machine yet. Fixed now. The part I'm having trouble with is line 85 in the test file. When I call prune on my tree, it returns false at line 245 in merkle.rs. I have an assert on that line in my local machine that's not pushed up to the repo, but other than that the code is the same.

This is weird, seeing how the checks at lines 69-79 in my test file pass, but the same checks fail in MerkleTree::prune in merkle.rs.

Thanks for taking the time to look through my code :smile:

4

It looks like prune() ends up being called multiple times via MerkleTree::prune_recurse() - my guess is the to_keep elements are being removed (or otherwise not found) whereas they shouldn't be. I don't think it's an inconsistency between contains() and prune() though, which is what you were suggesting.

5

Wow, I completely overlooked that. The reason I have two versions of prune, prune and _prune, was to avoid this very issue, and yet I completely forgot to call _prune instead of prune in prune_recurse.

Thanks a lot, I don't know how long it would have taken me to catch that!

6

No problem. At least your tests detect it! :slight_smile:

1 Like