Closed Bug 1388775 Opened 5 years ago Closed 5 years ago

extractContents should copy nodes in tree order, not backwards

Categories

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

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla57
Tracking Status
firefox57 --- fixed

People

(Reporter: ayg, Assigned: ayg)

Details

Attachments

(1 file)

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
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 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?
Attachment #8895419 - Flags: review?(bugs)
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.
Attachment #8895419 - Flags: review?(bugs)
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.
Attachment #8895419 - Flags: review?(bugs) → review+
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)
Pushed by ayg@aryeh.name:
https://hg.mozilla.org/integration/autoland/rev/3f0be44bb66f
extractContents should copy nodes in tree order, not backwards; r=smaug
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.
https://hg.mozilla.org/mozilla-central/rev/3f0be44bb66f
Status: ASSIGNED → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla57
Component: DOM → DOM: Core & HTML
You need to log in before you can comment on or make changes to this bug.