bug in delay?

Andreas Raab andreas.raab at gmx.de
Tue Jan 6 18:44:36 UTC 2004


This is clearly the case of an utterly broken collection. Look at this:

> VM: Win32 - Squeak3.6 of '6 October 2003' [latest update: #5424]
> Image: Squeak3.6 [latest update: #5424]
> Array(Object)>>error:
> Receiver: #(nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil
nil nil
> a Delay nil nil)

Given this array in a sorted collection it should be the case that:
firstIndex = 18
lastIndex = 18
(one element in the SC at position 18)

However, as we can see here:

> Array(SequenceableCollection)>>replaceFrom:to:with:startingAt:
> start: 19
> stop: 22
> repStart: 20

the replacement in OC>>insert:before: is done starting at index 19 and
trying to go up to 22. If you look at insert:before: it means that

firstIndex = 20
spotIndex = 24

(this can be derived straightforwardly from #insert:before:) which, in turn,
means that #indexForInserting: (being called by SortedCollection>>add:) has
computed an index which given the invariant firstIndex <= spot <=
lastIndex+1 means that

lastIndex >= 23

With an array of size 20 and one element at index 18, this collection is
utterly and totally broken (one thing to keep in mind here is that OC's
array NEVER shrinks so somewhere there must have been a computation which
screws up those invariants)

However, it gets even more interesting. If we look at
SortedCollection>>indexForInserting: which is responsible for creating the
out-of-range spotIndex, we can see that it computes the first probe as
"firstIndex + lastIndex // 2" which for the above values of firstIndex=20
and lastIndex >=23 will ALWAYS result in a probe index larger than 20 -
which should immediately raise an error in indexForInserting. This can be
seen, for example, by simulating that broken collection:

sc := SortedCollection new.
sc instVarNamed: 'array' put: ((Array new: 20) at: 18 put: 0; yourself).
sc instVarNamed: 'firstIndex' put: 20.
sc instVarNamed: 'lastIndex' put: 23.
sc add: 5.

Given that #indexForInserting: hasn't raised an error it almost smells as if
the array may still be correct in #indexForInserting: and "magically
changes" sometime later. Which smells a lot like the kind of bug that a
persistence framework may have. Any chance you're using one?

If not, then things are even more weird but it is clear that what you're
seeing really "cannot happen" for all the factors explained above. And given
that SortedCollection (and in particular Delay) have been working for years
I would strongly suspect that the problem is somewhere in your code.

  - Andreas

More information about the Squeak-dev mailing list