Collection invariants

On Fri, Mar 19, 2010 at 06:46:56PM +0100, martin odersky wrote:
> I did some spring cleaning of collections.

Some notes on this subject: I am just about finished implementing all
the changes described in

http://lampsvn.epfl.ch/trac/scala/ticket/3179

I'm glad I did this, because I realized there is what I consider a huge
trap lurking in there. The + methods are made to coexist by overloading
across subtype boundaries based on the static type of the value. This
means that if you have a mutable Map like this:

val x = mutable.Map(1 -> "abc", 2 -> "def")

Then these two operations have very different results:

x + ((3, "ghi")) // mutates x
x + ((3, "ghi": AnyRef)) // leaves x unchanged!

I hate stuff like that.

> If you add a new method to a collection class you need to add the same
> method to the corresponding ProxyLike class.
> [and similar for others]

I can't deal with having the correctness of this sort of thing dependent
on a bunch of individuals doing the right thing over time, and at some
point in the past I undertook this:

http://lampsvn.epfl.ch/svn-repos/scala/scala/trunk/src/library/scala/col...

They are out of date right now, but they exist with the intention of
giving us compiler verification that FooProxy, FooForwarder, and
whatever else implement all the methods of Foo. The idea is that by
defining an abstract version of every method in the collection, if you
try to instantiate something like

new IterableProxy with IterableMethods { def iterator = null }

it will not compile if you missed any. And then I'd have test cases
doing all those instantiations.

Of course this depends on IterableMethods being up to date -- so my
further intention is to add a compiler test which verifies they have the
same methods. It'd be easier if I had a sort of "reverse abstract"
ability, in the sense that the compiler will refuse to instantiate a
class with any abstract methods, and I also need a way to have it refuse
to instantiate a class if it has any "only concerete" public methods:
methods which are not implementations of an inherited abstract method.
However it's easy enough just to examine the bytecode.