WeakHashSet::retain doesn't iterate over all valid items

[m-demare]

Hi, I'm having this issue where sometimes WeakHashSet::retain skips some valid items.

For example, the following code fails about 1 out of 5 times I run it (I think the randomness is probably related to the randomness in a HashSet's iteration order):

use std::{
    fmt::Write,
    rc::{Rc, Weak},
};

use weak_table::WeakHashSet;

fn main() {
    let mut set = WeakHashSet::default();
    let mut v = Vec::new();

    let n = 5;

    for i in 0..n {
        let rc = Rc::new(i);
        v.push(rc.clone());
        set.insert(rc);
    }

    let rc = Rc::new(n);
    set.insert(rc.clone());

    print_set(&set, "before drop");

    drop(v);

    print_set(&set, "after drop");

    let mut retain_calls = Vec::new();
    set.retain(|val| {
        retain_calls.push(val);
        false
    });

    assert!(
        retain_calls.iter().any(|v| v == &n.into()),
        "retain was not called on {n}"
    );
}

fn print_set(set: &WeakHashSet<Weak<u32>>, name: &str) {
    let elems = set.iter().fold(String::new(), |mut f, val| {
        let _ = write!(f, "{val}, ");
        f
    });
    println!("elems ({name}): {elems}");
}

If you need any further info, please tell me. Thanks for making this incredibly useful crate!

[nmathewson]

Not sure if this crate is still maintained, but I've looked at the bug a bit to diagnose the issue and to see whether any other APIs are affected. Here's my theory:

The retain method works by calling remove_index, which potentially shifts elements within the hash table in order to preserve invariants. (The hash table uses open addressing, so whenever an element is removed, we need to check whether another element should go into the now-vacated bucket.) But any elements that shift as part of this remove_index call are not automatically checked in the retain loop.