Bug #17427
closedHash getting multiple identical keys
Description
I have a situation where a hash (contained within a Set) seems to get duplicate keys. I've had some difficulty reproducing the issue in a minimal fashion, but I have a 175-ish-line program that runs it. (Just for context, if you want to know what's doing what, it's meant to solve https://adventofcode.com/2020/day/22 part 2.)
When I run it on my machine, it will quickly error out with something like:
[[26, 22, 44, 16, 31, 19, 30, 10, 40, 47, 21, 48, 45], [4, 24, 1, 7, 36, 29, 38, 33, 3, 13, 11, 17, 39]]
[[26, 22, 44, 16, 31, 19, 30, 10, 40, 47, 21, 48, 45], [4, 24, 1, 7, 36, 29, 38, 33, 3, 13, 11, 17, 39]]
aoc22.rb:37:in `play_against!': #<Set: {[[26, 22, 44, 16, 31, 19, 30, 10, 40, 47, 21, 48, 45], [4, 24, 1, 7, 36, 29, 38, 33, 3, 13, 11, 17, 39]], [[26, 22, 44, 16, 31, 19, 30, 10, 40, 47, 21, 48, 45], [4, 24, 1, 7, 36, 29, 38, 33, 3, 13, 11, 17, 39]]}> (RuntimeError)
from aoc22.rb:88:in `compete!'
from aoc22.rb:39:in `each'
from aoc22.rb:39:in `inject'
from aoc22.rb:39:in `play_against!'
from aoc22.rb:174:in `each'
from aoc22.rb:174:in `inject'
from aoc22.rb:174:in `<main>'
showing that the Set somehow contains 2 identical items.
By the way, if you replace [stack, other_deck.stack]
with [stack, other_deck.stack].hash
on lines 32 and 40, the program executes successfully.
I've been able to reproduce on multiple versions of Ruby up to 2.7.0. I'd test on a Ruby 3 preview also, but I've had trouble installing it, sorry.
Files
Updated by jeremyevans0 (Jeremy Evans) almost 4 years ago
- Status changed from Open to Rejected
This code is broken:
if states.map(&:hash).uniq.size < states.size
The result of hash
does not have to be unique. Two different objects can have the same hash
value without problems. The invariant is that if two objects are equal according to eql?
, they must have the same hash
value. You should remove the map(&:hash).
.
However, that isn't what is causing your issue. What is causing your issue is that you are mutating the elements of the set after adding the element to the set, which is not supported. From the documentation for Set:
Modifying an element of a set will render the set to an unreliable state.
Switch to:
states << [stack, other_deck.stack].freeze.each(&:freeze)
Then fix the rest of your code to not mutate the stacks. Alternatively, switch to:
states << [stack, other_deck.stack].freeze.map(&:dup)
That's still going to require other changes, since it currently appears to result in an infinite loop (or maybe I'm just not being patient enough).
Updated by amcaplan (Ariel Caplan) almost 4 years ago
Thanks, Jeremy!
I'm aware that hash
values can overlap, it was just a shortcut to find problematic situations. In this test, false negatives can happen, but false positives can't.
I wasn't aware that there was any scenario where a hash can have duplicate keys, or that keys are mutable at all. I guess I assumed they are all frozen, like Strings.
I'm curious about the history of this issue with hashes. Are you aware of any proposed solutions? Seems like a copy-on-write approach could be very helpful here, especially since we now have a deep-copy operation available (though it's expensive) for supporting Ractors.
By the way, just a nitpick on your nitpick 😉:
states << [stack, other_deck.stack].freeze.map(&:dup)
The first freeze
is unnecessary because map
will create a new array.