Interior mutability can cause inconsistency in collections

[apasel422]

Collections that perform lookups based on a given property (e.g. a hash or an ordering) can be put into an inconsistent state when the property changes while its corresponding item is in the collection. This is normally not a problem, because such collections (at least those in std) do not provide mutable access to the type from which the property is derived (keys in the case of maps, items in the case of sets), but types with interior mutability can induce this behavior in safe code:

#[test]
fn test() {
    use std::cell::Cell;
    use std::collections::HashSet;
    use std::hash;

    #[derive(PartialEq)]
    struct Foo(Cell<u32>);

    impl Eq for Foo {}

    impl hash::Hash for Foo {
        fn hash<H: hash::Hasher>(&self, h: &mut H) { self.0.get().hash(h); }
    }

    let mut set = HashSet::new();
    set.insert(Foo(Cell::new(0)));
    set.insert(Foo(Cell::new(1)));

    for foo in &set {
        foo.0.set(2);
        break;
    }

    assert!(set.contains(&Foo(Cell::new(2))));
}

Output:

thread 'test' panicked at 'assertion failed: set.contains(&Foo(Cell::new(2)))'

This is obvious from the definition of interior mutability, but it's definitely a footgun. If the use of such keys cannot be prevented with the type system, the collections should at least document that the property must remain constant for the duration of the item's presence in the collection.

For example, Java's Map interface documentation contains the following note:

great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map.

[alexcrichton]

This is a dupe of #13438, which was previously closed for reasons in the thread itself.

I believe the gist of the conversion was that yes, this can happen. Our implementations should ensure that this does not cause memory unsafety, but otherwise these sorts of "odd assertions" are ok to happen as this should be quite a rare occurrence anyway.

[apasel422]

I still think the collection documentation needs to identify this problem.

On Friday, March 13, 2015, Alex Crichton [email protected] wrote:

Closed #23327 #23327.

—
Reply to this email directly or view it on GitHub
#23327 (comment).

[alexcrichton]

Hm good point! I've added an appropriate tag.

[apasel422]

@alexcrichton I'm working on a patch to document this.