1388775 - extractContents should copy nodes in tree order, not backwards

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, defect)

Description

[Aryeh Gregor (:ayg) (no longer with Mozilla)]

Per spec, Range.prototype.extractNodes() should copy the nodes in tree order.  Gecko instead copies them in reverse order.  This causes us to fail a mutation test: http://w3c-test.org/dom/nodes/MutationObserver-childList.html

Comment 1

[Aryeh Gregor (:ayg) (no longer with Mozilla)]

Attachment: Bug 1388775 - extractContents should copy nodes in tree order, not backwards;

Per spec, Range.prototype.extractNodes() should copy the nodes in tree
order:

https://dom.spec.whatwg.org/#dom-range-extractcontents

Gecko instead copies them in reverse order.  This causes us to fail a
wpt MutationObserver test.

Review commit: https://reviewboard.mozilla.org/r/166604/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/166604/

Comment 2

[Alex Vincent [:WeirdAl]]

Given enough time, all specifications change, making all code bitrot...

For historical purposes, bug 332148.  (Even though I'm sure the code has been rewritten at least once since.)

Comment 3

[Olli Pettay [:smaug]]

Comment on attachment 8895419 [details]
Bug 1388775 - extractContents should copy nodes in tree order, not backwards;

https://reviewboard.mozilla.org/r/166604/#review171914

I must be missing something. (1) Why do we need that while (nextNode && nsContentUtils::ContentIsDescendantOf(nextNode, node)) { loop and (2) why it is correct?

::: dom/base/nsRange.cpp:2175
(Diff revision 1)
>    while (!iter.IsDone())
>    {
>      nsCOMPtr<nsINode> nodeToResult;
>      nsCOMPtr<nsINode> node = iter.GetCurrentNode();
>  
> -    // Before we delete anything, advance the iterator to the
> +    // Before we delete anything, advance the iterator to the next node that's

I don't quite understand this. What if the other end of the range is somewhere underneath node?

Comment 4

[Aryeh Gregor (:ayg) (no longer with Mozilla)]

Comment on attachment 8895419 [details]
Bug 1388775 - extractContents should copy nodes in tree order, not backwards;

https://reviewboard.mozilla.org/r/166604/#review171914

We need it because otherwise nextNode will point to the first child of node, which will not be in the tree once we remove node.  When moving backwards this isn't a problem, which is I assume what the "We delete backwards to avoid iterator problems!" comment meant.

> I don't quite understand this. What if the other end of the range is somewhere underneath node?

The iterator only returns nodes fully contained in the range (and maybe the endpoint nodes).  If the endpoint of the range is in a descendant of a node, that node is not fully contained in the range, so it won't be returned by the iterator.

Comment 5

[Olli Pettay [:smaug]]

Comment on attachment 8895419 [details]
Bug 1388775 - extractContents should copy nodes in tree order, not backwards;

https://reviewboard.mozilla.org/r/166604/#review172346

In general I'm a bit worried about performance. Removing child nodes from first to last is slower currently than from last to first.
Though, prepending is slower than appendChild.
But please, think about performance, and if you can think of some worst case scenarios, write some test and measure.

::: dom/base/nsRange.cpp:2181
(Diff revision 1)
> -    // next subtree.
> +    // not a descendant of this one.  XXX It's a bit silly to iterate through
> +    // the descendants only to throw them out, we should use an iterator that
> +    // skips the descendants to begin with.
>  
> -    iter.Prev();
> +    iter.Next();
> +    nsCOMPtr<nsINode> nextNode = iter.GetCurrentNode();

I wonder if there are some worst-case-scenarios, where ContentIsDescendantOf starts to show up badly in profiles.

Comment 6

[Mozilla Autoland]

We're sorry, Autoland could not rebase your commits for you automatically. Please manually rebase your commits and try again.

hg error in cmd: hg rebase -s 64591613a91a -d 2e9296f1a1ad: rebasing 412722:64591613a91a "Bug 1388775 - extractContents should copy nodes in tree order, not backwards; r=smaug" (tip)
merging dom/base/nsRange.cpp
merging testing/web-platform/meta/dom/nodes/MutationObserver-childList.html.ini
warning: conflicts while merging testing/web-platform/meta/dom/nodes/MutationObserver-childList.html.ini! (edit, then use 'hg resolve --mark')
unresolved conflicts (see hg resolve, then hg rebase --continue)

Comment 7

[Aryeh Gregor (:ayg) (no longer with Mozilla)]

Comment on attachment 8895419 [details]
Bug 1388775 - extractContents should copy nodes in tree order, not backwards;

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/166604/diff/1-2/

Comment 8

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/3f0be44bb66f
extractContents should copy nodes in tree order, not backwards; r=smaug

Comment 9

[Aryeh Gregor (:ayg) (no longer with Mozilla)]

With this patch, many fewer removals are actually being done, because we're skipping all descendants of removed nodes.  This entails some computation to locate the descendants, but that could be easily avoided by using a different iterator, or just hand-coding the iteration, to omit all the descendants in the first place.

Comment 10

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/3f0be44bb66f