Hash collision

Bug #1556588 reported by hilaire on 2016-03-13
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
Dr. Geo II
High
hilaire

Bug Description

We have collision between DrGPointIntersection and DrGSegment2Points instances.

Althought parents of these two instances:
- two circles
- two point

It occurs with Koch and Durer scripts

description: updated
hilaire (hilaire-fernandes) wrote :

DrGPointIntersection>>rehash
 ^hash := (super rehash bitXor: k ) bitXor: point hash

helps on Koch and Dragon scripts

Changed in drgeo:
status: Confirmed → Fix Committed
Changed in drgeo:
status: Fix Committed → In Progress
hilaire (hilaire-fernandes) wrote :

For the broken Durer script, hash problem comes from:

DrGLine2PtsItem>>rehash
 ^ hash := super rehash bitXor: self parents reverse hash

The part with the hash on the reversed parents is the source of the problem.
It was introduced so lines (AB) and (BA) share the same hash value.

hilaire (hilaire-fernandes) wrote :

Remove specific hash and comparing criteria of DrGLine2Pts and DrGSegment2Pts

Now line (AB) and (BA), as well segment [AB] and [BA], will not be treat as equal entity.

Changed in drgeo:
status: In Progress → Fix Committed
Changed in drgeo:
status: Fix Committed → Fix Released
hilaire (hilaire-fernandes) wrote :

Pharo suffers from bad hash value for Float generating unexpected collisions on numbers as 0.5 and -0.5.
As a result Point item in DrGeo are too often seen as duplicated but there are not.

The proper way to fix this issue: in the Dr. Geo's Factory when there is hash equality between two geometric items, it should then check for the logical (ontological) equality of these two items

Code to implement it:

DrGFactory>>indexOf: anItem in: aPool
"No identity equality but hashed value to detect duplicated object we must consider as equal"
 ^ anItem
  ifNil: [0]
  ifNotNil: [aPool findFirst: [ :each |
    each hash = anItem hash
     and: ["double check when hash is equal (can be a collision)"
       each = anItem ]
   ]
  ]

Changed in drgeo:
assignee: nobody → hilaire (hilaire-fernandes)
milestone: 16.03 → wip
status: Fix Released → New
Changed in drgeo:
status: New → Fix Committed
Changed in drgeo:
milestone: wip → 17.07
Changed in drgeo:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers