[BUG]Collection>>removeAll:

Richard A. O'Keefe ok at cs.otago.ac.nz
Thu Aug 22 02:43:30 UTC 2002


	To me, the definition of removeAll: is not an English description
	of what it does, it is
	
	removeAll: aCollection
	  aCollection do: [:each | self remove: each]
	
That is NOT a definition.
It is an IMPLEMENTATION.
Not only that, it is a buggy implementation.

On this view, it would be impossible for any bugs to exist anywhere,
because "the definition of" anything would not be "an English description
of what it does" but the code itself.

I tried this very topic out in a class today.

I discussed with them the point that
    If *YOU* are traversing a collection, whether you are using
    an enumeration method or a stream of some kind,
    then *YOU* must not change the object you are iterating over.

They all understood this, and all accepted it.  I provided examples
in Java and Smalltalk of what not to do.

I then presented
    x := #(1 2 3 4) asOrderedCollection.
    x removeAll: x.

The students were unanimous in their view that they didn't see any
traversal here.  The person CALLING this method has NOT written a
traversal, and is NOT changing the collection iterated over.

They were insistent that it was totally unreasonable to expect
someone using a method like #removeAll: to understand the code
intimately before using it; they pointed out without any prompting
that the code in the method doesn't do what the comment says it does,
what the comment says is useful, and the code is therefore wrong.

I presented the
    x := OrderedCollection with: #foo.
    x addAll: x
example and they again unanimously agreed that the behaviour was
extremely surprising, quite unreasonable, and not consistent with
the documentation comment.

	Smalltalk might have been invented as a language for children,
	but that was a long time ago.

Nonononono, the phrase is not "children" but "children of all ages".

It should be *FUN* to program in Smalltalk, not *SCARY*.

	For the past 25 years or so, it has been a language for
	experienced programmers to build serious systems.
	
It has been that AS WELL.  If you've had the kind of experience I have,
when you find methods in core library classes that do not do what their
documentation says they do, you start looking for another tool.

The students all agreed that their confidence in Squeak was severely
shaken by the #removeAll: and #addAll: bug.  It didn't help that some
of them were aware that Java explicitly documents that
 "The behavior of an iterator is unspecified if the underlying
  collection is modified while the iteration is in progress in any way
  other than by calling [Iterator.remove()]."
and for List.addAll() it EXPLICITLY documents that it
 "Appends all of the elements in the specified collection to the end of
  this list, in the order that they are returned by the specified
  collection's iterator (optional operation).  The behavior of this
  operation is unspecified if the specified collection is modified
  while the operation is in progress.  (Note that this will occur if
  the specified collection is this list, and it's nonempty.)"
They didn't see why Squeak couldn't document this too.

One of them even knew about _this_:
 "The Iterators returned by Vector's iterator and listIterator methods
  are fail-fast>: if the Vector is structurally modified at any time after
  the Iterator is created, in any way except through the Iterator's own
  remove or add methods, the Iterator will throw a
  ConcurrentModificationException.  Thus, in the face of concurrent
  modification, the Iterator fails quickly and cleanly, rather than risking
  arbitrary, non-deterministic behavior at an undetermined time in the future."

When I pointed out how easily #addAll: could be made to _work_ in this case,
they didn't see why Java couldn't do that too.

	That said, if a lot of people make the same kind of mistake, it
	makes sense to change the system.  Collections should certainly
	support a removeAll operation that makes a collection empty.
	But the real problem here is that do: is not safe if the collection
	is being changed.

I'm afraid that's NOT the real problem.

The real problem is that the #do: is a #do: that the *PROGRAMMER* did not
write and cannot reasonably be expected to know about.  It's a #do: that
the library designers wrote; it was they who introduced a hole in the
specification and decided to leave Squeak programmers in the dark about it.

Yes, any Smalltalk programmer CAN read the implementation of ANY method they
use.  But no Smalltalk programmer has enough spare time to read EVERY method
they ever use.  I have spent a lot of time reading Squeak sources, and I
still haven't come near most of it, and don't understand a lot that I have
read.  Mostly, I just check the comments.

In fact, it's worse than that.  The new browser in Squeak 3.2, by
offering you the comment as a help balloon without opening the method
in a code pane, ENCOURAGES Squeakers not to look at the implementation
when the comment seems to be sufficiently helpful.

	It would be pretty simple to change do: such that
	it makes a copy of the collection before iterating over it.

That could be done, but there isn't the slightest need to.
When a programmer invokes an enumeration method, it is reasonable to
expect that programmer to live by the rule "don't YOU change what YOU
are iterating over."  The issue is iterations that the programmer
DOESN'T know about.

We are talking about
 - collection methods
 - which do "bulk" changes
 - and iterate over a "batch" collection passed as an argument
 - and make changes to the receiver during that traversal.
   (Conversely, something that iterates over the receiver and changes
   another collection passed as an argument would also have the problem)
 - yet because there are many possible implementations,
   someone invoking the method has no reason to suspect that
   argument traversal and receiver mutation are interleaved in this way.

	I see two arguments against this change.  One is that it would
	break existing programs.  I find this hard to believe.  Nobody
	depends on the behavior of changing a collection while you are
	iterating over it.  It is certainly not well defined.  I don't
	think it would break any existing programs.
	
Let's look at OrderedCollection>>do:

    do: aBlock
        |index|
        index := firstIndex.
        [index <= lastIndex] whileTrue: [
            aBlock value: (array at: index).
            index := index + 1].

If that were

    do: aBlock
	|index limit|
	index := firstIndex.
	limit := lastIndex.
	[index <= limit] whileTrue: [
	    aBlock value: (array at: index).
	    index := index + 1].

what would happen?  Well,

    a := OrderedCollection with: #foo.
    a addAll: a.

would leave the variable a referring to an OrderedCollection(#foo #foo).
In fact, this is what I originally expected OrderedCollection>>do: to do.

	The other argument is that it would make the system slower.
	I bet it wouldn't have much impact. The only way to find out
	is to try it, of course.  So I did.
	[about 20% slower on some Cincom benchmarks]

I tried changing OrderedCollection>>do: to
    do: aBlock
	self asArray do: aBlock
and the result of 0 tinyBenchmarks went UP (24.7 bc/sec -> 25.4 bc/sec).
Does 0 tinyBenchmarks do any OrderedCollection iterations, or is this noise?

	I think that if you are going to change Collections, you should go
	all the way and change do:.  Don't patch removeAll: or addAll:.  They
	are not the problem, and if you start trying to make them safe without
	changing do: then you will make the system too complicated.
	
The problem is the interaction of several factors:

1. Designers accepting "done change a collection you are iterating over"
   as a reasonable constraint on use.

   I've cited Java above partly in order to defend this decision.  Making
   copies to make #do: safe may seem reasonable on a 250MHz 64MB machine;
   it clearly WASN'T such a good idea back on the Dandelions and Dorados.
   
   Other languages and other libraries have similar restrictions.
   This _is_ something an experienced programmer can be expected to know
   about in general, even without Smalltalk experience, and beginners
   can be expected to grasp once it is pointed out to them.

2. Designers writing the simplest clearest code they can for operations
   but not thinking about all the boundary cases.  (x-x and x+x are
   perfectly reasonable in arithmetic; x\x and xUx are perfectly reasonable
   in set theory; but they are a sort of boundary case.)

   My evidence that they didn't think about this is that they don't seem
   to have documented their decision.  I seriously doubt whether there
   WAS a decision to make the x removeAll: x or x addAll: x cases go
   insane.  Had anyone thought about these cases, they would have realised
   that at the very least returning the argument object every time was a
   bad idea; returning the same object (as opposed to an object with the
   right state that MAY be the same object) only works when the two are
   different.

3. From the *outside*, the operations don't look dangerous.  There are
   many possible ways to implement #removeAll: and #addAll: and their
   relatives, and many of these ways do not trigger the do+mutate bug.

The result of these factors is that the programmer sees an operation that
COULD work, the documentation suggests that it SHOULD work, but it doesn't,
and it doesn't detect that it didn't work either.


A related problem can occur even when the programmer is not making and not
requesting any changes at all.

Consider a self-organising structure, specifically a splay tree.
One nice thing about splay trees is that whatever their initial shape,
    do: aBlock
	|each|
	each := self minKey.
	[each == nil] whileFalse: [
	    aBlock value: each.
	    each := self nextKeyAfter: each]
will traverse the keys of the tree in ascending order in linear time.

Suppose that aBlock looks things up in the tree.  No change at all to the
abstract state, but there is a change to the concrete state.  Another nice
thing about splay trees is that the loop will continue to work.  It would
even work if you added and removed things.  But just looking things up
changes the configuration of the tree, and the performance bound is lost.
The loop goes to at least O(n.lg n) instead of O(n); amortised of course.

My preferred representation for hash tables uses dynamic hashing, the
buckets being represented by singly linked lists, with the move-to-front
heuristic applied to those lists.  Performs well, but while you are
iterating over such a table, you had better not do ANYTHING else with it,
even an "innocent" lookup, because move-to-front will change the structure.

Of course iterating over a copy would solve that problem.  But because it
is MY code, I know about the problem and avoid it and don't think it is a
serious problem.


For me, the cause of the problem appears to be that no-one ever DECIDED
whether (x removeAll: x) should work or not, or if they did, didn't think
anyone else needed to know what the decision was.

A documented decision to ban it would please me less than code without
mysterious special cases, but it would be a good second best.


Part of the story, I think, is that Smalltalk-80 was just one in a series
of experimental systems which were being developed and replaced quite
rapidly.  I don't suppose that the original authors were expecting the
process to stop with Smalltalk-80.  If you are expecting to have to throw
away or massively revise the code in another year or two, you won't be
inclined to put a lot of effort into documentation.  But Smalltalk-80 HAS
lasted, and we are seeing some of the consequences.

Come to think of it, when is that big Morphic cleanup going to happen?
I hope this thread hasn't done anything to delay _that_!




More information about the Squeak-dev mailing list