Add EfficientLength marker interface to some iterabels.

sdk/lib/collection/queue.dart

Index: sdk/lib/collection/queue.dart
diff --git a/sdk/lib/collection/queue.dart b/sdk/lib/collection/queue.dart
index 1cacd18c18fc158784ff2fd0692a4b06e3e8a80d..91410ba0f87bc095e87046d5493b6780a8ae4f62 100644
--- a/sdk/lib/collection/queue.dart
+++ b/sdk/lib/collection/queue.dart
@@ -9,7 +9,7 @@ part of dart.collection;
  * can iterate over the elements of a queue through [forEach] or with
  * an [Iterator].
  */
-abstract class Queue<E> implements Iterable<E> {
+abstract class Queue<E> implements Iterable<E>, EfficientLength {

[sra1, 2013/10/09 21:16:53]

This is what is scary about tag interfaces.
They are irrevocable.
I can't "implement Queue" unless my implementation also guarantees
EfficientLength.
The implicit interface is polluted with implementation details.

A "get hasEfficientLength" method would allow subclasses to revoke the
attribute, but a method becomes an mandatory burden on each implementation.

To void this problem tag interfaces should be used only on private classes.

[floitsch, 2013/10/10 13:04:53]

I partially agree. However we already did "is Queue" checks and simply assumed
that it had an efficient length.
We should add documentation that 'length' of a Queue should be efficient.

And even then: if the length is not efficient the complexity of our operations
don't change. We just run through the elements twice (which is really only bad
when they have side-effects).
We could rename the TagInterface to something else.

@Lasse: add documentation for "length". ?

[sra1, 2013/10/10 17:02:41]

There are many interesting queue algorithms that do not have this property; to
require an efficient length would forego their use.

Can we at least move closer to the ideal of implementing EfficientLength only on
private classes?

What I propose:
'EfficientLength' is a statement about the behaviour of get:length, so it must
only be implemented by the classes that implement get:length.

Then at least you can visually check, and a programmable static analysis tool
might be able to enforce the style.

You can still screw up by overriding get:length, but that is a smaller problem
than polluting an abstract interface.

[floitsch, 2013/10/10 17:12:05]

The List interface specifies that its length must be efficient. There is no
reason not to add it there.
I'm willing to discuss its usefulness on other interfaces.

 
   /**
    * Creates a queue.