Clojure

Protocols Should Handle Hash Collision

Details

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

Description

Protocols internal is using min-hash and throwing a collision, similar to the bug fixed in CLJ-426.

https://groups.google.com/d/msg/clojure/0qllPii3fJY/Lile5yQPxuIJ

Attachments

  1. Text File
    map-fallback-cache.patch
    21/May/11 9:29 PM
    5 kB
    Alexander Taggart
  2. Text File
    test-801.patch
    27/May/11 2:45 PM
    3 kB
    Alexander Taggart
  3. Text File
    test-801b.patch
    01/Jun/11 1:47 PM
    2 kB
    Stuart Sierra
  4. Text File
    test-801c.patch
    02/Jun/11 9:15 AM
    6 kB
    Stuart Sierra

Activity

Ascending order - Click to sort in descending order
Hide
Permalink
Alexander Taggart added a comment -

map-fallback-cache.patch: protocol's method cache falls back to using a map when shift-mask table won't work, instead of throwing an exception.

Show
Alexander Taggart added a comment - map-fallback-cache.patch: protocol's method cache falls back to using a map when shift-mask table won't work, instead of throwing an exception.
Hide
Permalink
Alexander Taggart added a comment -

test-801.patch: tests method cache collision behaviour by modifying clojure.lang.MethodImplCache to allow arbitrary objects.

Show
Alexander Taggart added a comment - test-801.patch: tests method cache collision behaviour by modifying clojure.lang.MethodImplCache to allow arbitrary objects.
Hide
Permalink
Fogus added a comment -

The attached test helps to illustrate the problem, but it needs some work to make it a useful regression for the existing code.

Show
Fogus added a comment - The attached test helps to illustrate the problem, but it needs some work to make it a useful regression for the existing code.
Hide
Permalink
Stuart Sierra added a comment -

File "test-801b.patch" can replace A. Taggart's "test-801.patch" from 27/May/11.

This new test can be applied independently of the bug fix in "map-fallback-cache.patch".

The test temporarily redefines clojure.core/hash to force a hash collision. Before the bug fix, the test fails with "java.lang.IllegalArgumentException: Hashes must be distinct." After the fix, the test passes.

Show
Stuart Sierra added a comment - File "test-801b.patch" can replace A. Taggart's "test-801.patch" from 27/May/11. This new test can be applied independently of the bug fix in "map-fallback-cache.patch". The test temporarily redefines clojure.core/hash to force a hash collision. Before the bug fix, the test fails with "java.lang.IllegalArgumentException: Hashes must be distinct." After the fix, the test passes.
Hide
Permalink
Alexander Taggart added a comment -

Just wanted to note that hash collisions are not the only issue. The shift-mask's mask is limited to 13 bits, so it's possible for hashes to be distinct but still not satisfy the constraints. This latter condition is what was being tested by the "no min-hash" test case in test-801.patch.

Show
Alexander Taggart added a comment - Just wanted to note that hash collisions are not the only issue. The shift-mask's mask is limited to 13 bits, so it's possible for hashes to be distinct but still not satisfy the constraints. This latter condition is what was being tested by the "no min-hash" test case in test-801.patch.
Hide
Permalink
Stuart Sierra added a comment -

I'll try to add another test for the no-min-hash case.

Show
Stuart Sierra added a comment - I'll try to add another test for the no-min-hash case.
Hide
Permalink
Stuart Sierra added a comment -

File "test-801c.patch" supplants "test-801b.patch" and adds another test for the no-min-hash case.

Both tests fail before "map-fallback-cache.patch" and pass after.

Show
Stuart Sierra added a comment - File "test-801c.patch" supplants "test-801b.patch" and adds another test for the no-min-hash case. Both tests fail before "map-fallback-cache.patch" and pass after.
Hide
Permalink
Tassilo Horn added a comment -

I've just applied map-fallback-cache.patch on top of commit 66a88de9408e93cf2b0d73382e662624a54c6c86, and now my project runs fine. Before, I frequently had these "no distinct mappings found" error.

Show
Tassilo Horn added a comment - I've just applied map-fallback-cache.patch on top of commit 66a88de9408e93cf2b0d73382e662624a54c6c86, and now my project runs fine. Before, I frequently had these "no distinct mappings found" error.
Hide
Permalink
Stuart Sierra added a comment -

Code & Test patches pushed.

Show
Stuart Sierra added a comment - Code & Test patches pushed.

People

Vote (0)
Watch (0)

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.