Entry API doesn't correctly update Trie count -- 0.8.0 may need to be yanked

[kevinaboos]

Hi @sdleffler, thanks so much for this awesome crate! We've been using it for years in Theseus OS for symbol maps and other things.

Problem

I've discovered a tricky issue with the Trie's count value -- it's not updated properly when modifying the Trie via the Entry API, so if you insert a new value using VacantEntry, the count will be wrong.

This bug manifests in two ways:

1. When integer overflow runtime checks are enabled (e.g., in debug builds), a panic occurs when removing the last key-value pair due to count - 1 "overflowing" below 0.

thread 'main' panicked at 'attempt to subtract with overflow', /home/kevin/.cargo/registry/src/github.com-1ecc6299db9ec823/qp-trie-0.8.0/src/trie.rs:323:13

2. When overflow checks are disabled (e.g., in release builds), the count value wraps around from 0 to usize::MAX, resulting in Trie::count() returning a bogus value.

count is now wrong: 18446744073709551615

Code example

Here's a commented example that shows the various ways this bug manifests.

use qp_trie::{
    Entry,
    Trie,
    wrapper::BString,
};

fn main() {
    let mut trie: Trie<BString, usize> = Trie::new();

    trie.insert("one".into(), 1);
    assert_eq!(1, trie.count()); // succeeds

    match trie.entry("two".into()) {
        Entry::Occupied(mut _old_val) => {
            panic!("'two' shouldn't exist yet");
        }
        Entry::Vacant(new_entry) => {
            new_entry.insert(2); // doesn't update `count`
        }
    }

    println!("Trie contents: {:?}", trie);

    assert_eq!(2, trie.count()); // fails

    // If you comment out the above assertion,
    // the following `remove` calls will also fail because count is incorrectly `1`,
    // meaning that `count` will throw a "subtract with overflow" error
    // when integer overflow is detected, e.g., for debug builds.
    trie.remove(&BString::from("two"));
    trie.remove(&BString::from("one")); // should succeed, but doesn't.

    // If you build in release mode (or otherwise disable integer overflow runtime checks),
    // this line will print `usize::MAX` because `count` has wrapped around from `0`
    println!("count is now wrong: {}", trie.count());
}

Discussion

• There may be other places where count isn't updated correctly, but I'm not sure. As far as I can tell, the count is only updated in the top-level insert and remove functions, but I'm not intimately familiar with the rest of the code.
• After this is fixed and published as v0.8.1, the current version 0.8.0 should be yanked from crates.io to ensure downstream users don't hit this bug.

[8573]

This seems like an issue for catching which a Rutenspitz test could be useful. I might get around to contributing one eventually.

[erikbrinkman]

This should be fixed in 0.8.1, although 0.8.0 should probably still be yanked. There could also be more exhaustive testing as @8573 suggests