Fix type problem with FilteredElementList._iterable

Fix type problem with FilteredElementList._iterable

BUG=
R=whesse@google.com

Committed: https://github.com/dart-lang/sdk/commit/de3ce04f0a778e87f214224316ab9d7c67488d6e

[Alan Knight, 2015-07-15 20:35:23]

alanknight@google.com changed reviewers:
+ terry@google.com

[Alan Knight, 2015-07-15 20:35:24]

See https://github.com/dart-lang/sdk/issues/23849

The reason it fails is that we can't cast the result of the where to an
Iterable<Element> from an Iterable<Node>. This is remarkably difficult to do, at
least without allocating a new List. But we can take advantage of being in the
SDK to create a WhereIterable with the correct type directly.

This also points out that the generic in FilteredElementList is completely
unused and wouldn't really work. Almost all uses of it are dynamic, and the one
that isn't is Element (in svg). If you made the generic be anything but Element
or dynamic, things would break. So replacing it with just a hard-coded Element.

Also changed the implementation of remove, which is very slow if [] uses the
_filtered list, which we recreate each time.

[Bill Hesse, 2015-07-16 07:46:11]

whesse@google.com changed reviewers:
+ whesse@google.com

[Bill Hesse, 2015-07-16 07:46:13]

If you don't want to do all the changes suggested here, just the comment
changes, and the simple efficiency improvements, are OK.

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
File sdk/lib/html/html_common/filtered_element_list.dart (right):

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:8: * An indexable collection
of a node's descendants in the document tree,
Is this of all a node's descendants, or just its direct children?  Is node.nodes
all the elements below a node?

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:12: implements
NodeListWrapper {
Maybe write a better comment, that many methods will be inefficient, because
ListBase uses operator[], not an iterator, to implement its methods, and our
operator[] is linear time.

Almost any method that needs to be efficient needs to be reimplemented here,
using an iterator.  And I think they can all use a direct WhereIterable, rather
than creating the list _filtered, unless the method itself does concurrent
modification.

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:39: // modify the
collection, e.g. addAll might append a node to another parent.
I'm not convinced this comment is correct.  Only those operations implemented by
ListBase need to be safe in their implementations, and they only use [], which
makes a new iterator each time.  Any externally visible iteration over a list
can't concurrently modify it and expect the iterator to work.

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:93: _filtered.sublist(start,
end).forEach((el) => el.remove());
new List.from(_iterable.skip(start).take(end-start)) instead of
_filtered.sublist?  It's not that big an improvement.

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:103: final result =
this.last;
_iterable.last

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:111: var element =
_iterable.elementAt(index);
Does this throw the correct RangeError?

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:128: for (var child in this)
{
var child in _iterable.  Or much more efficiently,

if (contains(child)) {
  child.remove();
  return true;
}

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:137: int get length =>
_filtered.length;
_iterable.length

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:138: Element operator [](int
index) => _filtered[index];
operator[] can use elementAt on the _iterable, without creating the list
_filtered.  Make sure the RangeError is correct, though.

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:141: Iterator<Element> get
iterator => _filtered.iterator;
Iterators do not support concurrent modification in general.
We might need this support because we are extending ListBase.
But as far as I can see,
all the operations that mutate the list drop their iterators immediately
after any mutating operation.  So maybe this guarantee isn't needed.
Only removeRange seems to use an iterator

Is this extra guarantee needed on the visible API of FilteredElementList?  Is it
part of the DOM spec?

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
File sdk/lib/html/html_common/html_common.dart (right):

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/html_common.dart:9: import 'dart:_internal' show
WhereIterable;
Consider copying in this class, or even just the class WhereIterator, which is
very tiny, specialized for "is Element", to avoid a dependence on _internal.  If
the public iterator method can just return a WhereIterator (rather than making
the filtered list), then you can just use "this" whenever you are currently
using _iterable, I think.

[Alan Knight, 2015-07-16 22:11:59]

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
File sdk/lib/html/html_common/filtered_element_list.dart (right):

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:8: * An indexable collection
of a node's descendants in the document tree,
On 2015/07/16 07:46:12, Bill Hesse wrote:
> Is this of all a node's descendants, or just its direct children?  Is
node.nodes
> all the elements below a node?

Direct descendants. Added to comment.

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:12: implements
NodeListWrapper {
On 2015/07/16 07:46:12, Bill Hesse wrote:
> Maybe write a better comment, that many methods will be inefficient, because
> ListBase uses operator[], not an iterator, to implement its methods, and our
> operator[] is linear time.
> 
> Almost any method that needs to be efficient needs to be reimplemented here,
> using an iterator.  And I think they can all use a direct WhereIterable,
rather
> than creating the list _filtered, unless the method itself does concurrent
> modification.

Sadly, any method that calls user code might be doing concurrent modification,
because the DOM collections can be modified by operations on the contained
elements. Following the well-established design "Principle of Most
Astonishment". II wasted a bunch of time yesterday realizing this. So, e.g. if
we implement _iterator to return an iterator on the WhereIterable rather than on
a List that copies it, then 
   anElement.children.addAll(aFilteredElementList)
will throw an index out of range error because adding an element to
someOtherThing removes it from _childNodes. Similarly for forEach.

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:39: // modify the
collection, e.g. addAll might append a node to another parent.
On 2015/07/16 07:46:13, Bill Hesse wrote:
> I'm not convinced this comment is correct.  Only those operations implemented
by
> ListBase need to be safe in their implementations, and they only use [], which
> makes a new iterator each time.  Any externally visible iteration over a list
> can't concurrently modify it and expect the iterator to work.

As above, the function f can modify the iterator by doing operations on its
elements.

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:93: _filtered.sublist(start,
end).forEach((el) => el.remove());
On 2015/07/16 07:46:13, Bill Hesse wrote:
> new List.from(_iterable.skip(start).take(end-start)) instead of
> _filtered.sublist?  It's not that big an improvement.

Done.

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:103: final result =
this.last;
On 2015/07/16 07:46:13, Bill Hesse wrote:
> _iterable.last

Done.

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:111: var element =
_iterable.elementAt(index);
On 2015/07/16 07:46:12, Bill Hesse wrote:
> Does this throw the correct RangeError?

It does, added a test.

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:128: for (var child in this)
{
On 2015/07/16 07:46:12, Bill Hesse wrote:
> var child in _iterable.  Or much more efficiently,
> 
> if (contains(child)) {
>   child.remove();
>   return true;
> }

Done.

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:137: int get length =>
_filtered.length;
On 2015/07/16 07:46:12, Bill Hesse wrote:
> _iterable.length

Done.

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:137: int get length =>
_filtered.length;
On 2015/07/16 07:46:12, Bill Hesse wrote:
> _iterable.length

Done.

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:141: Iterator<Element> get
iterator => _filtered.iterator;
On 2015/07/16 07:46:12, Bill Hesse wrote:
> Iterators do not support concurrent modification in general.
> We might need this support because we are extending ListBase.
> But as far as I can see,
> all the operations that mutate the list drop their iterators immediately
> after any mutating operation.  So maybe this guarantee isn't needed.
> Only removeRange seems to use an iterator
> 
> Is this extra guarantee needed on the visible API of FilteredElementList?  Is
it
> part of the DOM spec?

See above re: DOM

[Bill Hesse, 2015-07-17 08:40:47]

lgtm

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
File sdk/lib/html/html_common/filtered_element_list.dart (right):

https://codereview.chromium.org/1236793006/diff/20001/sdk/lib/html/html_commo...
sdk/lib/html/html_common/filtered_element_list.dart:12: implements
NodeListWrapper {
On 2015/07/16 22:11:58, Alan Knight wrote:
> On 2015/07/16 07:46:12, Bill Hesse wrote:
> > Maybe write a better comment, that many methods will be inefficient, because
> > ListBase uses operator[], not an iterator, to implement its methods, and our
> > operator[] is linear time.
> > 
> > Almost any method that needs to be efficient needs to be reimplemented here,
> > using an iterator.  And I think they can all use a direct WhereIterable,
> rather
> > than creating the list _filtered, unless the method itself does concurrent
> > modification.
> 
> Sadly, any method that calls user code might be doing concurrent modification,
> because the DOM collections can be modified by operations on the contained
> elements. Following the well-established design "Principle of Most
> Astonishment". II wasted a bunch of time yesterday realizing this. So, e.g. if
> we implement _iterator to return an iterator on the WhereIterable rather than
on
> a List that copies it, then 
>    anElement.children.addAll(aFilteredElementList)
> will throw an index out of range error because adding an element to
> someOtherThing removes it from _childNodes. Similarly for forEach.
> 

True.  If it wasn't for this exact issue (allAll, and nodes being removed from
their original location when added), then I would say concurrent modification
should be disallowed, and all of the improvements can follow.  But I agree, that
the exposed forAll and iterator of FilteredElementList should be
modification-safe.

All other methods, that just return or set a single value, should use _iterator
though.

[Alan Knight, 2015-07-17 17:53:23]

Committed patchset #3 (id:40001) manually as
de3ce04f0a778e87f214224316ab9d7c67488d6e (presubmit successful).