Bug #17427: Hash getting multiple identical keys

• Status: Rejected
• Assignee: -
• Target version: -
• ruby -v: ruby 2.7.0p0 (2019-12-25 revision 647ee6f091) [x86_64-darwin19]
• Backport: 2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN

[amcaplan (Ariel Caplan)]

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.

[jeremyevans0 (Jeremy Evans)]

• 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).

[amcaplan (Ariel Caplan)]

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.