clone with clone children flag set should append clone before cloning children

[dbaron]

The clone algorithm in the DOM spec currently describes the cloning algorithm when the "clone children" flag is set as recursively cloning the children and then appending them to the cloned parent. While, strictly, it doesn't link to append, it probably meant to, and the definition of append involves running the insertion steps on all shadow-including descendants. This means that the algorithm described in the specification is quadratic in the tree depth, since the insertion steps are run depth times for each node.

This quadratic behavior is in fact present in current Chromium. @mfreed7 just landed a CL to to fix that; it seemed like given the way insertion steps usually (although not quite always) care about whether the element is connected, the difference in ordering probably wouldn't be observable, since most of the insertion steps would only matter when the resulting tree gets appended to something that is connected. (There are some insertion steps where this isn't true, though, but they also generally seem to care about being connected to some ancestor in particular, for example for picture element media selection. I think for picture element selection there's a decent chance that this change is an observable behavior change in Chromium... though not observably spec-violating since the spec for picture stuff is quite vague about timing (through use of in parallel.)

I decided to just now to look at the relevant Gecko code; nsINode::CloneNode calls nsINode::Clone which calls nsINode::CloneAndAdopt which appears to have the same behavior as the new Chromium behavior.

Given that:

• this alternative behavior is faster
• one engine has already adopted it, and another is trying to
• it seems likely that the difference is Web-observable, and that chance will increase over time

I think it seems likely to be worthwhile to change the DOM spec to describe element cloning in this new way.

The disadvantage is that I think it will make the spec a bit more complicated. (Thus, I'm filing an issue rather than immediately writing a PR, since the PR would take a good bit more time to write!)

[annevk]

I guess we could refactor by having "clone" and "clone into parent". And "clone into parent" recurses. And "clone" calls "clone into parent" for each of the node's children when the flag is set (which as per #1220 we should probably refactor).

cc @rniwa

[rniwa]

FWIW, WebKit has had this new Chromium behavior for about a decade.