On Thu, Sep 8, 2011 at 8:02 AM, Henrik Sperre Johansen
<henrik.s.johansen@veloxit.no>
wrote:
On 08.09.2011 14:37, Michael Roberts wrote:
So I found the bug with the first assignment. It
is caused by a difference between squeak and Pharo
in SortedCollection. (on my phone so will be
brief)
In Pharo the debugger map collection gets sorted
and asked for an index for a given pc. It is
supposed to answer 1 because there is no match and
it is expected to be the first index for
insertion. However when the asSortedCollection
gets done the internal start index of the
collection is 2. This manifests the bug. 2 is
answered as the insertion position but this is a
value internal to the collection.
Squeak does not have this bug because it forces a
reset of the start index to 1. Hope that makes
sense. I don't know what the correct fix is. We
copy the reset:1 type code to force the collection
to have start from 1 property. We check semantics
of index for insertion. Is it the position of the
element of index relative to pointers? Or we
change the debugger to calculate the offset (but
this feels wrong)
So this is an opportunity for some test cases and
fixes around sorted collection if we know what the
correct semantics are. This leak of '2' out of the
collection is only wrong if 2 is a valid state. If
that makes sense...
Cheers
Mike
Mike, thanks for your careful search!
Hum, indexForInserting: is _supposed_ to answer the
internal index...
Depending on the startIndex being 1 for doing the
correct at: later is just wrong.
Squeak potentially has the same highlight bug for
different methds, as insert:before: used when converting
to SortedCollection in no way ensures startIndex remains
1 just because it started as it.
This is an ancient bug. I copied the code from
Debugger and it's been there since at least Smalltalk-80
V2:
!Debugger methodsFor: 'pc selection'!
pcRange
"Answer the indices in the source code for the
method corresponding
to the selected context's program counter value."
| i methodNode pc end |
(HighlightPC and: [context ~~ nil])
ifFalse: [^1 to: 0].
(sourceMap == nil or: [sourceMap size = 0])
ifTrue: [^1 to: 0].
pc_ context pc -
((context == processHandle topContext and:
[processHandle interrupted])
ifTrue: [1]
ifFalse: [2]).
i _ sourceMap indexForInserting: (Association
key: pc value: nil).
i < 1 ifTrue: [^1 to: 0].
i > sourceMap size
ifTrue:
[end _ sourceMap inject: 0 into:
[:prev :this | prev max: this value
last].
^ end+1 to: end].
^(sourceMap at: i) value! !
In Smalltalk-80 V2 indexForInserting: is also private,
but like Squeak it "just works" since firstIndex is 1 in
this context. So either take your approach or add a
non-private accessor to SortedCollection than answers an
external index. Personally I like the external accessor,
since findBinary: doesn't quite do what we want. In my
Qwaq-derived image Josh Gargus contributed
findNearbyBinaryIndex: which is nearly what we want:
!SequenceableCollection methodsFor: 'enumerating'
stamp: 'jcg 1/27/2009 18:32'!
findNearbyBinaryIndex: aBlock
"Search for an element in the receiver
using binary search.
The argument aBlock is a one-element
block returning
0 - if the element is
the one searched for
<0 - if the search
should continue in the first half
>0 - if the search
should continue in the second half
If no matching element is found,
answer the closest index we could find."
| index low high test |
low := 1.
high := self size.
[index := high + low // 2.
low > high] whileFalse:[
test := aBlock value: (self at:
index).
test = 0
ifTrue:[^index]
ifFalse:[test > 0
ifTrue: [low := index + 1]
ifFalse: [high := index - 1]]].
^index! !
but it doesn't answer an index > size when the
searched for element should be past the end.
#(1 3 5 7 11 15 23) findNearbyBinaryIndex: [ :arg | 0 -
arg ] 0
#(1 3 5 7 11 15 23) findNearbyBinaryIndex: [ :arg | 24
- arg ] 7
I think it should read
!SequenceableCollection methodsFor: 'enumerating'
stamp: 'eem 9/8/2011 10:23'!
findNearbyBinaryIndex: aBlock
"Search for an element in the receiver
using binary search.
The argument aBlock is a one-element
block returning
0 - if the element is
the one searched for
<0 - if the search
should continue in the first half
>0 - if the search
should continue in the second half
If no matching element is found,
answer the closest index we could find."
| index low high test |
low := 1.
high := self size.
[index := high + low // 2.
low > high] whileFalse:[
test := aBlock value: (self at:
index).
test = 0
ifTrue:[^index]
ifFalse:[test > 0
ifTrue: [low := index + 1]
ifFalse: [high := index - 1]]].
^index = self size ifTrue: [index + 1]
ifFalse: [index]! !
and then
#(1 3 5 7 11 15 23) findNearbyBinaryIndex: [ :arg | 0
- arg ] 0
#(1 3 5 7 11 15 23) findNearbyBinaryIndex: [ :arg |
24 - arg ] 8
and then the debugger method uses simply
i := sortedSourceMap
findNearbyBinaryIndex: [:assoc| pc - assoc key].
in place of
i := sortedSourceMap
indexForInserting: (pc -> nil)].
Find attached. I'll add this to Squeak trunk.