Clojure

Broken equality for sets

Details

  • Type: Defect Defect
  • Status: Closed Closed
  • Priority: Major Major
  • Resolution: Completed
  • Affects Version/s: Release 1.4, Release 1.5
  • Fix Version/s: Release 1.5
  • Component/s: None
  • Labels:
    None
  • Patch:
    Code and Test
  • Approval:
    Ok

Description

Equality for sets is not consistent with other persistent collections when the hashCode differs:

(= {(Integer. -1) :foo} {(Long. -1) :foo})
=> true

(= [(Integer. -1)] [(Long. -1)])
=> true

(= #{(Integer. -1)} #{(Long. -1)})
=> false

Attached is what I believe to be a basic fix. It removes a hashCode check from APersistentSet.equals. A similar check was removed from APersistentMap in the following commit:

https://github.com/clojure/clojure/commit/b5f5ba2e15dc2f20e14e05141f7de7c6a3d91179

With this patch, set equality works as expected and all tests pass.

My understanding of the implications of this change are limited, so someone more knowledgeable would need to chime in about its correctness.

Activity

Ascending order - Click to sort in descending order
Justin Kramer made changes -
Field Original Value New Value
Description Equality for sets is not consistent with other persistent collections when the hashCode differs:

{{(= {(Integer. -1) :foo} {(Long. -1) :foo})
=> true

(= [(Integer. -1)] [(Long. -1)])
=> true

(= #{(Integer. -1)} #{(Long. -1)})
=> false}}

Attached is what I believe to be a basic fix. It removes a hashCode check from APersistentSet.equals. A similar check was removed from APersistentMap in the following commit:

https://github.com/clojure/clojure/commit/b5f5ba2e15dc2f20e14e05141f7de7c6a3d91179

With this patch, set equality works as expected and all tests pass.

My understanding of the implications of this change are limited, so someone more knowledgeable would need to chime in about its correctness. 		Equality for sets is not consistent with other persistent collections when the hashCode differs:

(= {(Integer. -1) :foo} {(Long. -1) :foo})
=> true

(= [(Integer. -1)] [(Long. -1)])
=> true

(= #{(Integer. -1)} #{(Long. -1)})
=> false

Attached is what I believe to be a basic fix. It removes a hashCode check from APersistentSet.equals. A similar check was removed from APersistentMap in the following commit:

https://github.com/clojure/clojure/commit/b5f5ba2e15dc2f20e14e05141f7de7c6a3d91179

With this patch, set equality works as expected and all tests pass.

My understanding of the implications of this change are limited, so someone more knowledgeable would need to chime in about its correctness.
Hide
Permalink
Andy Fingerhut added a comment -

Can you add some unit tests that fail with the current code but succeed with the change?

Show
Andy Fingerhut added a comment - Can you add some unit tests that fail with the current code but succeed with the change?
Justin Kramer made changes -
Attachment setequals.diff [ 11668 ]
Hide
Permalink
Justin Kramer added a comment -

Revised patch with unit test that fails in master and succeeds with patch

Show
Justin Kramer added a comment - Revised patch with unit test that fails in master and succeeds with patch
Justin Kramer made changes -
Attachment setequals.diff [ 11669 ]
Hide
Permalink
Timothy Baldridge added a comment -

vetting

Show
Timothy Baldridge added a comment - vetting
Timothy Baldridge made changes -
Patch Code [ 10001 ] Code and Test [ 10002 ]
Approval Vetted [ 10003 ]
Priority Major [ 3 ] Minor [ 4 ]
Timothy Baldridge made changes -
Fix Version/s Release 1.5 [ 10150 ]
Hide
Permalink
Gary Fredericks added a comment -

This came up when we were trying to diff two datasets by putting them in sets and comparing. We had Integers because they came back from JDBC that way.

Show
Gary Fredericks added a comment - This came up when we were trying to diff two datasets by putting them in sets and comparing. We had Integers because they came back from JDBC that way.
Gary Fredericks made changes -
Priority Minor [ 4 ] Major [ 3 ]
Hide
Permalink
Aaron Bedra added a comment -

I'm going to take a look and try to get this shipped. It hit us and I would love to to see it in 1.5

Show
Aaron Bedra added a comment - I'm going to take a look and try to get this shipped. It hit us and I would love to to see it in 1.5
Hide
Permalink
Paul Stadig added a comment -

I applied the patch on master (ca465d6d) and it applied cleanly and fixes the issue.

Show
Paul Stadig added a comment - I applied the patch on master (ca465d6d) and it applied cleanly and fixes the issue.
Hide
Permalink
Bo Jeanes added a comment -

Instead of removing m.hashCode() != hashCode(), perhaps we should use `Util.hasheq()` instead. It already seems to special case numbers (https://github.com/clojure/clojure/blob/f48d024e97/src/jvm/clojure/lang/Util.java#L164-L172) and won't have the potential performance impact that skipping hashCode checks could bring.

Show
Bo Jeanes added a comment - Instead of removing m.hashCode() != hashCode(), perhaps we should use `Util.hasheq()` instead. It already seems to special case numbers (https://github.com/clojure/clojure/blob/f48d024e97/src/jvm/clojure/lang/Util.java#L164-L172) and won't have the potential performance impact that skipping hashCode checks could bring.
Hide
Permalink
Bo Jeanes added a comment -

Attaching a patch with an alternate fix for this issue that does not skip hashCode checking.

It passes all existing tests and fixes this issue.

I want to benchmark the difference, too.

Show
Bo Jeanes added a comment - Attaching a patch with an alternate fix for this issue that does not skip hashCode checking. It passes all existing tests and fixes this issue. I want to benchmark the difference, too.
Bo Jeanes made changes -
Attachment 0001-CLJ-1106-Use-Util.hasheq-in-hashCode-for-persistent-.patch [ 11825 ]
Hide
Permalink
Bo Jeanes added a comment -

On further thought and comparison to APersistentMap, I'm not sure if that's the best use of Util.hasheq(). I can't find good reference on the semantic differences and am not familiar enough with the Clojure source to infer it, yet.

Show
Bo Jeanes added a comment - On further thought and comparison to APersistentMap, I'm not sure if that's the best use of Util.hasheq(). I can't find good reference on the semantic differences and am not familiar enough with the Clojure source to infer it, yet.
Hide
Permalink
Aaron Bedra added a comment -

Bo, I don't see you listed on the contributors list. Did you send in a CA?

Show
Aaron Bedra added a comment - Bo, I don't see you listed on the contributors list. Did you send in a CA?
Hide
Permalink
Aaron Bedra added a comment -

Both of the patches above are not complete. APersistentSet equiv calls equals. APersistentMap has two separate ways of handling this. This is the path that the fix should take.

Show
Aaron Bedra added a comment - Both of the patches above are not complete. APersistentSet equiv calls equals. APersistentMap has two separate ways of handling this. This is the path that the fix should take.
Hide
Permalink
Aaron Bedra added a comment -

This patch addresses the difference between equals and equiv.

Show
Aaron Bedra added a comment - This patch addresses the difference between equals and equiv.
Aaron Bedra made changes -
Attachment 0001-Fixing-set-equality.patch [ 11829 ]
Aaron Bedra made changes -
Assignee Aaron Bedra [ aaron ]
Hide
Permalink
Stuart Halloway added a comment -

The Set equality code currently in Clojure uses .hashCode to quickly bail out of comparisons in both .equals and .equiv. This feels wrong since .equals and .equiv presume different hashes. The map equality code avoids the problem by not checking any hash.

Aaron's 2/13 patch makes set equality work like map equality, not checking the hash. (I think a much shorter patch that accomplishes the same thing merely drops the call to hash.)

It seems to me a separate problem that both hash and set are broken for Java .equals rules, because of the equiv-based handling of their keys.

I think this needs more consideration.

Show
Stuart Halloway added a comment - The Set equality code currently in Clojure uses .hashCode to quickly bail out of comparisons in both .equals and .equiv. This feels wrong since .equals and .equiv presume different hashes. The map equality code avoids the problem by not checking any hash. Aaron's 2/13 patch makes set equality work like map equality, not checking the hash. (I think a much shorter patch that accomplishes the same thing merely drops the call to hash.) It seems to me a separate problem that both hash and set are broken for Java .equals rules, because of the equiv-based handling of their keys. I think this needs more consideration.
Hide
Permalink
Stuart Halloway added a comment -

Notes from discussion with Rich:

1. Aaron's 2/2/13 patch, which mimics map logic into set, is the preferred approach.

2. The broader issue I was worried about is the semantic collision between Map's containsKey and Associative's containsKey. This is out of scope here, and perhaps ever.

Show
Stuart Halloway added a comment - Notes from discussion with Rich: 1. Aaron's 2/2/13 patch, which mimics map logic into set, is the preferred approach. 2. The broader issue I was worried about is the semantic collision between Map's containsKey and Associative's containsKey. This is out of scope here, and perhaps ever.
Stuart Halloway made changes -
Approval Vetted [ 10003 ] Screened [ 10004 ]
Hide
Permalink
Aaron Bedra added a comment -

Any chance this will make 1.5?

Show
Aaron Bedra added a comment - Any chance this will make 1.5?
Rich Hickey made changes -
Approval Screened [ 10004 ] Ok [ 10007 ]
Rich Hickey made changes -
Resolution Completed [ 1 ]
Fix Version/s Release 1.5 [ 10150 ]
Status Open [ 1 ] Resolved [ 5 ]
Stuart Halloway made changes -
Status Resolved [ 5 ] Closed [ 6 ]

People

Vote (4)
Watch (6)

Dates

  • Created:
    Updated:
    Resolved:
Atlassian JIRA (v4.4#649-r158309) | Report a problem
Powered by a free Atlassian JIRA open source license for Clojure. Try JIRA - bug tracking software for your team.