Add "contains" method to Collection.

Add "contains" method to Collection.

Also added a Sequence interface to capture things with a length and
integer indexing. List and String implement that interface, and
there is a base skeleton class for collections that are Sequences.

BUG=1030
Committed: https://code.google.com/p/dart/source/detail?r=13766

[floitsch, 2012-10-16 14:03:19]

LGTM although I'm not sure how to solve the "bad return type for map and filter"
problem.

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart
File lib/core/sequences.dart (right):

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart#newcode9
lib/core/sequences.dart:9: * sequences can implement.
sequence (-s)

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart#newco...
lib/core/sequences.dart:29: List result = new List(this.length);
This violates the specification of 'map' which specifies that the return type
should be the same as the type of 'this'.

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart#newco...
lib/core/sequences.dart:37: for (int i = 0; i < sequence.length; i++) {
I would store the length in a variable, but that's nit-picking.

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart#newco...
lib/core/sequences.dart:52: List<E> result = <E>[];
Ditto: violates the contract.

https://codereview.chromium.org/11169004/diff/1/lib/html/dart2js/html_dart2js...
File lib/html/dart2js/html_dart2js.dart (right):

https://codereview.chromium.org/11169004/diff/1/lib/html/dart2js/html_dart2js...
lib/html/dart2js/html_dart2js.dart:10270: +  bool containse(Element element) =>
_filtered.contains(element);
contains (-e)

https://codereview.chromium.org/11169004/diff/1/lib/html/dart2js/html_dart2js...
lib/html/dart2js/html_dart2js.dart:11449: +    final out = <Element>[];
That looks wrong.

https://codereview.chromium.org/11169004/diff/1/lib/html/dart2js/html_dart2js...
lib/html/dart2js/html_dart2js.dart:11566: +    final out = <Element>[];
ditto.

[ngeoffray, 2012-10-16 15:08:18]

https://codereview.chromium.org/11169004/diff/1/lib/core/collection.dart
File lib/core/collection.dart (right):

https://codereview.chromium.org/11169004/diff/1/lib/core/collection.dart#newc...
lib/core/collection.dart:66: Dynamic reduce(var initialValue,
Why is this one 'var'?

https://codereview.chromium.org/11169004/diff/1/lib/core/collection.dart#newc...
lib/core/collection.dart:67: Dynamic combine(var previousValue, E element)) {
ditto

https://codereview.chromium.org/11169004/diff/1/lib/core/collection.dart#newc...
lib/core/collection.dart:68: var value = initialValue;
Why this?

https://codereview.chromium.org/11169004/diff/1/lib/core/collection.dart#newc...
lib/core/collection.dart:69: for (Element element in this) value =
combine(value, element);
Element -> E

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart
File lib/core/sequences.dart (right):

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart#newco...
lib/core/sequences.dart:137: throw new IllegalAccessException();
Access? Should it be UnsupportedOperationException instead? (and same for all
others)

[sra1, 2012-10-16 18:52:52]

The lib/html changes need to be made by changing the generator, not editing the
output:

edit lib/html/templates/immutable_list_mixin.darttemplate
cd lib/html/scripts
./go.sh  # generates this file.

If you see changes other than your intended changes, ask for help.

If you need help with this, since you are adding a method which doesn't break
anything, make a separate CL for lib/html/... and get it checked in
ahead of your main change.

This should get easier when we get mixins.

It is a good idea to include one of blois, efortuna, antonm, podivilov, sra or
vsm on changes that touch lib/html.

https://codereview.chromium.org/11169004/diff/1/lib/core/collection.dart
File lib/core/collection.dart (right):

https://codereview.chromium.org/11169004/diff/1/lib/core/collection.dart#newc...
lib/core/collection.dart:66: Dynamic reduce(var initialValue,
I thought the standard coding style was to leave out Dynamic where possible.

reduce(initValue, combine(previousValue, E element)) {

https://codereview.chromium.org/11169004/diff/1/lib/core/collection.dart#newc...
lib/core/collection.dart:68: var value = initialValue;
On 2012/10/16 15:08:18, ngeoffray wrote:
> Why this?

It would be wrong to overwrite 'initialValue' since then the name 'initialValue'
would be misleading.

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart
File lib/core/sequences.dart (right):

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart#newco...
lib/core/sequences.dart:17: * A skeleton class for a [Collection] that is also a
[Sequence].
The assumption is that length is efficient, otherwise overriding the operators
like reduce is a bad idea.

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart#newco...
lib/core/sequences.dart:29: List result = new List(this.length);
Dont make the returned value fixed length, since it then you might be forced to
copy the result, e.g this won't work:

var s = myThings.map(stringify)..add('end')

https://codereview.chromium.org/11169004/diff/1/lib/html/dart2js/html_dart2js...
File lib/html/dart2js/html_dart2js.dart (right):

https://codereview.chromium.org/11169004/diff/1/lib/html/dart2js/html_dart2js...
lib/html/dart2js/html_dart2js.dart:2245: +  bool contains(CSSRule element) =>
_Collections.contains(this, element);
The only sane way to 'edit' this file is to regenerate it.

https://codereview.chromium.org/11169004/diff/1/lib/html/dart2js/html_dart2js...
lib/html/dart2js/html_dart2js.dart:8195: +    implements Console
This change should not be part of this CL unless due to changes in the
generator.
ditto for many changes below.

https://codereview.chromium.org/11169004/diff/1/lib/html/dartium/html_dartium...
File lib/html/dartium/html_dartium.dart (right):

https://codereview.chromium.org/11169004/diff/1/lib/html/dartium/html_dartium...
lib/html/dartium/html_dartium.dart:2821: +  bool contains(CSSRule element) =>
_Collections.contains(this, element);
See lib/html/dart2js/html_dart2js.dart

[Lasse Reichstein Nielsen, 2012-10-17 11:06:45]

Now using the generator to generate html-files.

The bad return type of map/filter can't really be solved.
They should be constructors for the type you want to create, so you write:
  new List<Foo>.filter(someIterable, (x) => x is Foo)
instead of 
  someCollection.filter((x) => x is Foo)
and getting some type back that you don't control.
It also allows correct typing of the result of map.

Alternatively, if we want to keep the utility of map/filter on objects, they
should return views backed by the original.
If you want a new object, you have to use "new".

https://codereview.chromium.org/11169004/diff/1/lib/core/collection.dart
File lib/core/collection.dart (right):

https://codereview.chromium.org/11169004/diff/1/lib/core/collection.dart#newc...
lib/core/collection.dart:66: Dynamic reduce(var initialValue,
I'm not sure it's *standard*, but it's definitely one of the opposing views :)
I prefer always writing a type to make the code more readable and show that the
dynamic typing is deliberate, and leave untyped code to quick hacks (and it's
great that we support that too!).
In this case, some Dynamic's could be written as the shorter "var" instead, but
return types can't.

https://codereview.chromium.org/11169004/diff/1/lib/core/collection.dart#newc...
lib/core/collection.dart:68: var value = initialValue;
Exactly :)

https://codereview.chromium.org/11169004/diff/1/lib/core/collection.dart#newc...
lib/core/collection.dart:69: for (Element element in this) value =
combine(value, element);
Thanks.

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart
File lib/core/sequences.dart (right):

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart#newcode9
lib/core/sequences.dart:9: * sequences can implement.
On 2012/10/16 14:03:19, floitsch wrote:
> sequence (-s)

Done.

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart#newco...
lib/core/sequences.dart:17: * A skeleton class for a [Collection] that is also a
[Sequence].
True. I'm adding this as comments on the methods of Sequence.

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart#newco...
lib/core/sequences.dart:29: List result = new List(this.length);
That specification can't be followed exactly. There are no concrete classes that
are only SequenceCollection, so we don't have one to return. A List is a
SequenceCollection, so it's not entirely wrong. It would be preferable to return
a SequenceCollection view of the list. We don't have a List.asCollection yet
(and I hope we will). I think this is the best we can do at this time.

Good point on the fixed-length-ness of the result. I keep forgetting that new
List(4) generates a fixed length list.
That *really* needs to be fixed!

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart#newco...
lib/core/sequences.dart:37: for (int i = 0; i < sequence.length; i++) {
I try to avoid that when I don't know whether the length of the sequence might
change between accesses. It's defensive programming (and not really safe if the
sequence is being deliberately malicious and changes between calls to "length").

Fixing length at the start will prevent an infinite loop if the list is, e.g.,
"list of the calls of '==' on my class".

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart#newco...
lib/core/sequences.dart:52: List<E> result = <E>[];
Arguably.

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart#newco...
lib/core/sequences.dart:137: throw new IllegalAccessException();
You are right - the VM's implementation mostly uses
UnsupportedOperationException (I must have been looking at immutable_map.dart).
Fixing.

This is another exception that should be a StateError with a suitable message.

https://codereview.chromium.org/11169004/diff/1/lib/html/dart2js/html_dart2js...
File lib/html/dart2js/html_dart2js.dart (right):

https://codereview.chromium.org/11169004/diff/1/lib/html/dart2js/html_dart2js...
lib/html/dart2js/html_dart2js.dart:2245: +  bool contains(CSSRule element) =>
_Collections.contains(this, element);
When I need to change this file, I have usually done it manually, and then told
Anton to update the generator to match. I'll try doing it myself this time :)

https://codereview.chromium.org/11169004/diff/1/lib/html/dart2js/html_dart2js...
lib/html/dart2js/html_dart2js.dart:10270: +  bool containse(Element element) =>
_filtered.contains(element);
On 2012/10/16 14:03:19, floitsch wrote:
> contains (-e)

Done.

https://codereview.chromium.org/11169004/diff/1/lib/html/dart2js/html_dart2js...
lib/html/dart2js/html_dart2js.dart:11449: +    final out = <Element>[];
True. The output type is unknown.

[Lasse Reichstein Nielsen, 2012-10-17 11:07:37]

Please take a new look at the template changes.

[floitsch, 2012-10-17 13:19:32]

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart
File lib/core/sequences.dart (right):

https://codereview.chromium.org/11169004/diff/1/lib/core/sequences.dart#newco...
lib/core/sequences.dart:29: List result = new List(this.length);
On 2012/10/17 11:06:45, Lasse Reichstein Nielsen wrote:
> That specification can't be followed exactly. There are no concrete classes
that
> are only SequenceCollection,
That was not my point: from what I can see this class should serve as template
(super-class) of other SequenceCollections. But that doesn't work since it
always returns a List.
> so we don't have one to return. A List is a
> SequenceCollection, so it's not entirely wrong. It would be preferable to
return
> a SequenceCollection view of the list. We don't have a List.asCollection yet
> (and I hope we will). I think this is the best we can do at this time.
> 
> Good point on the fixed-length-ness of the result. I keep forgetting that new
> List(4) generates a fixed length list.
> That *really* needs to be fixed!

[Lasse Reichstein Nielsen, 2012-10-17 14:42:13]

Now with changes actually uploaded.

@Florian: Your objection really points to a weakness in this design: There is no
SequenceCollection type that the user should worry about. It's just a handy
helper for implementing the Collection part of a List. There are no other
collections that are also sequences.
I think the SequenceCollection should be dropped, and just merged into List *as
soon as List stops being an interface*.
At that point, List will be the skeleton implementation for List
implementations, and include the Collection interface.

A Sequence wrapper as Collection is more useful - it could turn a String into a
Collection<String>.

I also think the map/filter methods creating their own result objects of "some
compatible type" is a bad design that we should change.

[floitsch, 2012-10-17 21:40:00]

LGTM, but wait for Stephen's OK.

https://codereview.chromium.org/11169004/diff/10001/lib/core/sequences.dart
File lib/core/sequences.dart (right):

https://codereview.chromium.org/11169004/diff/10001/lib/core/sequences.dart#n...
lib/core/sequences.dart:186: throw new IllegalAccessException();
Why is this not an UnsupportedOperationException?

[sra1, 2012-10-18 06:13:24]

lgtm

[Lasse Reichstein Nielsen, 2012-10-18 07:58:55]

https://codereview.chromium.org/11169004/diff/10001/lib/core/sequences.dart
File lib/core/sequences.dart (right):

https://codereview.chromium.org/11169004/diff/10001/lib/core/sequences.dart#n...
lib/core/sequences.dart:186: throw new IllegalAccessException();
Beats me. Selective blindness? Scrolled below the fold of my screen?