Removing nonexistent keys causes prefix matching to fail

[kellymclaughlin]

To demonstrate the issue I made the following change the prefix test case in the test module:

15:32:20:rust_radix_trie(remove-bug *) $ git diff src/test.rs
diff --git a/src/test.rs b/src/test.rs
index 9caae9b..e85977e 100644
--- a/src/test.rs
+++ b/src/test.rs
@@ -450,7 +450,9 @@ fn test_get_raw_descendant_borrow() {
 #[test]
 fn test_prefix() {
     let mut t = Trie::<u8, ()>::new();
+    t.remove(&0xf1);
     t.insert(0xf1, ());
+    t.remove(&0xf2);
     t.insert(0xf2, ());
     println!("{:#?}", t);
     assert_eq!(t.prefix(), [].as_ref());

Afterwards I get this failure:

15:27:25:rust_radix_trie(remove-bug *) $ RUST_BACKTRACE=1 cargo test test_prefix
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running target/debug/deps/radix_trie-2113ab568ed5b82e

running 1 test
test test::test_prefix ... FAILED

failures:

---- test::test_prefix stdout ----
Trie {
    length: 2,
    node: TrieNode {
        key: NibbleVec [],
        key_value: None,
        child_count: 1,
        children: [
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            None,
            Some(
                TrieNode {
                    key: NibbleVec [15, 2],
                    key_value: Some(
                        KeyValue {
                            key: 242,
                            value: (),
                        },
                    ),
                    child_count: 0,
                    children: [
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                        None,
                    ],
                },
            ),
        ],
    },
}
thread 'test::test_prefix' panicked at 'assertion failed: `(left == right)`
  left: `NibbleVec [15, 2]`,
 right: `[15]`', src/test.rs:460:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:39
   1: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:71
   2: std::panicking::default_hook::{{closure}}
             at src/libstd/sys_common/backtrace.rs:59
             at src/libstd/panicking.rs:197
   3: std::panicking::default_hook
             at src/libstd/panicking.rs:208
   4: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:474
   5: std::panicking::continue_panic_fmt
             at src/libstd/panicking.rs:381
   6: std::panicking::begin_panic_fmt
             at src/libstd/panicking.rs:336
   7: radix_trie::test::test_prefix
             at src/test.rs:460
   8: radix_trie::test::test_prefix::{{closure}}
             at src/test.rs:451
   9: core::ops::function::FnOnce::call_once
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libcore/ops/function.rs:231
  10: <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/liballoc/boxed.rs:704
  11: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:85
  12: test::run_test::run_test_inner::{{closure}}
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libstd/panicking.rs:272
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libstd/panic.rs:394
             at src/libtest/lib.rs:1468

failures:
    test::test_prefix

test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 48 filtered out

error: test failed, to rerun pass '--lib'

Next, I added a call to check_trie_integrity like this:

diff --git a/src/test.rs b/src/test.rs
index 9caae9b..f775775 100644
--- a/src/test.rs
+++ b/src/test.rs
@@ -450,8 +450,11 @@ fn test_get_raw_descendant_borrow() {
 #[test]
 fn test_prefix() {
     let mut t = Trie::<u8, ()>::new();
+    t.remove(&0xf1);
     t.insert(0xf1, ());
+    t.remove(&0xf2);
     t.insert(0xf2, ());
+    assert!(t.check_integrity());
     println!("{:#?}", t);
     assert_eq!(t.prefix(), [].as_ref());
     let first = t.children().next().unwrap();

The resulting test failure looks like this:

15:28:44:rust_radix_trie(remove-bug *) $ RUST_BACKTRACE=1 cargo test test_prefix
   Compiling radix_trie v0.1.4 (/home/kelly/repos/rust_radix_trie)
    Finished dev [unoptimized + debuginfo] target(s) in 1.02s
     Running target/debug/deps/radix_trie-2113ab568ed5b82e

running 1 test
test test::test_prefix ... FAILED

failures:

---- test::test_prefix stdout ----
thread 'test::test_prefix' panicked at 'assertion failed: t.check_integrity()', src/test.rs:457:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:39
   1: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:71
   2: std::panicking::default_hook::{{closure}}
             at src/libstd/sys_common/backtrace.rs:59
             at src/libstd/panicking.rs:197
   3: std::panicking::default_hook
             at src/libstd/panicking.rs:208
   4: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:474
   5: std::panicking::begin_panic
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libstd/panicking.rs:408
   6: radix_trie::test::test_prefix
             at src/test.rs:457
   7: radix_trie::test::test_prefix::{{closure}}
             at src/test.rs:451
   8: core::ops::function::FnOnce::call_once
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libcore/ops/function.rs:231
   9: <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/liballoc/boxed.rs:704
  10: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:85
  11: test::run_test::run_test_inner::{{closure}}
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libstd/panicking.rs:272
             at /rustc/a53f9df32fbb0b5f4382caaad8f1a46f36ea887c/src/libstd/panic.rs:394
             at src/libtest/lib.rs:1468

failures:
    test::test_prefix

test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 48 filtered out

error: test failed, to rerun pass '--lib'

So it seems that attempting to remove a key from the trie that doesn't exist in this manner has negative effect on the trie integrity.

I made the following change to the traversal module and it resolves the issue and all the tests pass (including my modifications):

15:29:03:rust_radix_trie(remove-bug *) $ git diff src/traversal.rs
diff --git a/src/traversal.rs b/src/traversal.rs
index 3395338..4a6a183 100644
--- a/src/traversal.rs
+++ b/src/traversal.rs
@@ -182,7 +182,10 @@ where
                 KeyMatch::SecondPrefix => {
                     let depth = child.key.len();
                     rec_remove(trie, child, bucket, key, depth, &nv)
-                }
+                },
+                KeyMatch::Partial(idx) => {
+                    rec_remove(trie, child, bucket, key, idx, &nv)
+                },
                 _ => None,
             }
         }

15:30:41:rust_radix_trie(remove-bug *) $ cargo test
   Compiling radix_trie v0.1.4 (/home/kelly/repos/rust_radix_trie)
    Finished dev [unoptimized + debuginfo] target(s) in 0.99s
     Running target/debug/deps/radix_trie-2113ab568ed5b82e

running 49 tests
test qc_test::subtrie_mut_get ... ok
test test::ancestor_key ... ok
test test::child_subtrie_keys ... ok
test test::empty_key ... ok
test test::from_iter ... ok
test test::get_ancestor_bug ... ok
test test::get_nonexistant ... ok
test test::get_prefix_bug ... ok
test test::get_raw_descendant ... ok
test test::insert ... ok
test test::insert_replace ... ok
test test::int_keys ... ok
test test::iter ... ok
test test::map_with_default ... ok
test test::nearest_ancestor ... ok
test test::nearest_ancestor_no_child_fn ... ok
test test::nearest_ancestor_root ... ok
test test::raw_ancestor ... ok
test test::raw_ancestor_prefix ... ok
test test::raw_descendant_prefix ... ok
test test::remove ... ok
test test::remove_non_existent ... ok
test test::remove_simple ... ok
test test::root_replace_bug ... ok
test test::subtrie ... ok
test test::subtrie_insert ... ok
test test::subtrie_len ... ok
test test::subtrie_lifetime ... ok
test test::subtrie_mut_lifetime ... ok
test test::subtrie_nonexistant ... ok
test test::subtrie_string ... ok
test test::test_get_ancestor_borrow ... ok
test test::test_get_ancestor_value_borrow ... ok
test test::test_get_borrow ... ok
test test::test_get_mut_borrow ... ok
test test::test_get_raw_ancestor_borrow ... ok
test test::test_get_raw_descendant_borrow ... ok
test test::test_prefix ... ok
test test::test_remove_borrow ... ok
test test::test_subtrie_borrow ... ok
test test::test_subtrie_mut_borrow ... ok
test test::unicode ... ok
test qc_test::subtrie_get ... ok
test qc_test::subtrie ... ok
test qc_test::values_iter ... ok
test qc_test::keys_iter ... ok
test qc_test::remove_non_existent ... ok
test qc_test::insert_all_remove_all ... ok
test qc_test::subtrie_insert ... ok

test result: ok. 49 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

   Doc-tests radix_trie

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

I don't know if that's a good fix or not, but I just noticed from adding dbg statements that the problem happened in rec_remove when the result of the match_keys call was KeyMatch::Partial.

[michaelsproul]

Nice find, I'll try to dig into this properly soon and decide on a fix. At first glance your solution looks reasonable 👍 Please ping me if I get distracted!

[michaelsproul]

I ended up opting for a more direct solution which covers more cases – the core of the issue was that the remove function was dropping the child node whenever it got a KeyMatch::Partial or KeyMatch::FirstPrefix. It now re-inserts the child correctly in these cases (so that the total effect of the remove is to do nothing).

[michaelsproul]

There's a new release out that fixes the bug

[kellymclaughlin]

Thanks @michaelsproul!