Bug in remove_prefix?

[ninegua]

The following test seems to produce wrong result:

#[test]
fn remove_prefix() {
    let mut trie = Trie::new();
    for i in 0..10 {
        let mut bytes = [0; 16];
        let (left, right) = bytes.split_at_mut(8);
        left.copy_from_slice(&u64::to_be_bytes(i));
        right.copy_from_slice(&u64::to_be_bytes(i));
        println!("insert {:?}", bytes);
        trie.insert(bytes, ());
    }
    println!("trie = {:?}", trie);
    assert_eq!(trie.count(), 10);
    for i in 0..5 {
        let subtrie = trie.remove_prefix(&u64::to_be_bytes(i)[..]);
        println!("remove_prefix {} removed {}", i, subtrie.count());
    }
    println!("trie = {:?}", trie);
    assert_eq!(trie.count(), 5);
}

The output is:

running 1 test
test remove_prefix ... FAILED

failures:

---- remove_prefix stdout ----
test remove_prefix ... FAILED

failures:

---- remove_prefix stdout ----
insert [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
insert [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1]
insert [0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2]
insert [0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 3]
insert [0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 4]
insert [0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 5]
insert [0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 6]
insert [0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 7]
insert [0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 8]
insert [0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 9]
trie = {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]: (), [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1]: (), [0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2]: (), [0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0
, 0, 0, 0, 0, 3]: (), [0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 4]: (), [0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 5]: (), [0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 6]: (), [0, 0, 0, 0, 0, 0,
 0, 7, 0, 0, 0, 0, 0, 0, 0, 7]: (), [0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 8]: (), [0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 9]: ()}
remove_prefix 0 removed 10
remove_prefix 1 removed 0
remove_prefix 2 removed 0
remove_prefix 3 removed 0
remove_prefix 4 removed 0
trie = {}
thread 'remove_prefix' panicked at 'assertion failed: `(left == right)`
  left: `10`,
 right: `5`', tests/lib.rs:317:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

There are at least two problems:

• Each remove_prefix should return a subtree that has only 1 element. But the first one says "removed 10", the rest says "0".
• After remove_prefix, the count is still 10 despite that all elements are removed.

[sdleffler]

Looks like the recent optimization to track counts by inserts/removals missed tracking remove_prefix. Aside from the count, I'll need to look more closely. Thank you for the report.

[ninegua]

Made an easy fix, not sure if it is correct. Please have a look. Thanks! @sdleffler

[sdleffler]

Not quite correct but you got the location right. :) Fix published to crates.io as version 0.7.6.