Re: [vwnc] Bug in MethodDictionary

Holger,

Ahhh, very nice catch indeed.  We do have a somewhat related AR,

AR# 46540
Description SortedCollection>>includes:/indexOf: binary search

which implements binary search / binary inclusion checks for sorted
collections.  Note that this functionality is not meant to replace what
includes: / indexOf: are doing right now, but rather they provide this
via new selectors.

Something that came up with that AR is how binary search proceeds in the
presence of duplicates.  I think I found a beautiful solution to that,
and I also think it's correct.  If this AR moves, then I could simply
adapt the solution to MethodDictionary and this problem would go away.
I made another AR, 54789, back referencing AR 46540, for the problem
with MethodDictionary.

Thank you for letting us know about this!

Andres.

-----Original Message-----
From: vwnc-bounces@... [mailto:vwnc-bounces@...] On
Behalf Of Holger Kleinsorgen
Sent: Wednesday, July 16, 2008 3:37 AM
To: vwnc@...
Subject: [vwnc] Bug in MethodDictionary

Hello,

while loading some stuff from Store, I encountered an a "key not found
error" which resulted from a bug in MethodDictionary:

The method dictionary of a class showed some inconsistencies:

    "self includesKey: #packagesMLS"
evaluated to false, but

    "self keys includes: #packagesMLS"
evaluated to true

the keys were properly sorted, so it hat to be something else.
the first three selector symbols had the same identity hash:

   "(self basicAt: 1) identityHash" -> 3
   "(self basicAt: 3) identityHash" -> 3
   "(self basicAt: 5) identityHash" -> 3

which triggered an error in #findIndexOfKey:

    ...
    "Equal identityHashes.  Need linear search both ways until found."
    low := index - 2.
    [   low < 1
          ifTrue: [ ^ 0 ].
       ( probe := self basicAt: low ) == key
          ifTrue: [ ^ low ].
       probe identityHash = keyIdHash
    ] whileTrue: [ low := low - 2 ].
    low := index + 2.
    [   low > high
          ifTrue: [ ^ 0 ].
       ( probe := self basicAt: low ) == key
          ifTrue: [ ^ low ].
       probe identityHash = keyIdHash
    ] whileTrue: [ low := low + 2 ].
    ^ 0
    ...

if the hashes of all symbols from low to index are equal, but do not
include the key, the method will return 0 without looking in the range
from index to high

_______________________________________________
vwnc mailing list
vwnc@...
http://lists.cs.uiuc.edu/mailman/listinfo/vwnc

_______________________________________________
vwnc mailing list
vwnc@...
http://lists.cs.uiuc.edu/mailman/listinfo/vwnc