Add convenient, ergonomic, performant API for sorting siblings

[fantasai]

[Could've sworn I filed this already, but maybe we only talked about it.]

Back in 2015 Bo Campbell from IBM reported a major accessibility problem with websites using Flexbox: they were using the order property to to perform semantic re-ordering of elements, because the order property was much easier and more performant than re-ordering with JavaScript.

The problem with this is that the re-ordering isn't reflected in the accessibility tree or in the navigation order: CSS deliberately forbids this, since the point of this property was to create a divergence between the visual positioning and logical ordering of the elements.* Our continued position is that semantic ordering belongs in the source.

* The reason CSS allows this divergence is because visual perception is 2D and is affected by things like the gestalt principles. Size differences, color contrast, spatial grouping, and other techniques are regularly used by designers to guide the eye around the page in patterns that don't follow a simple top-left->bottom-right coordinate scan; allowing the spatial order to diverge from the source order lets designers map the source order to the intended visual perception order. (This is all out-of-scope for the issue, just wanted to head off any off-topic comments like “why does CSS define order this way”.)

However, because reordering elements in the DOM is so unwieldy, authors are sorely tempted to use order for it. Roma Kamarov’s sorting solution with CSS variables, for example, is so much more straightforward than a JS approach. It would be helpful if the DOM offered an API for sorting siblings that was as simple and powerful as sorting with order in CSS; even if it can't be quite as performant as a CSS-only solution (since it has to do strictly more work by altering the DOM tree as well), it would hopefully be useful enough to head off some of the more misguided uses of CSS, and provide a useful convenience to people using JS regardless.

[fantasai]

@domenic and I were discussing this issue this evening; one suggestion, inspired by Roma’s post, was to have an API that accepts the name of an attribute and sorts by its value (with an optional comparison function if the standard string-sorting algo wasn't sufficient).

@domenic also had another, more generic approach of passing a function or method, the details of which I've now forgotten. :(

[AmeliaBR]

One question: on what interface would this method exist?

Would it be on parentNode, and automatically apply to all child nodes? What about text nodes or comment nodes? Would they need to be handled by the sort function? Or would the sort function only get element nodes, and other nodes would automatically be dropped from the DOM? Or shunted to the end of the list?

---

an API that accepts the name of an attribute and sorts by its value (with an optional comparison function if the standard string-sorting algo wasn't sufficient).

You might want to sort by data that isn't stored in attributes (like the text content, or sorting by whether the checkboxes are currently checked). And the things you're sorting on might be properties of child elements (e.g., when sorting table rows by the data in cells). Finally, you may have a list of sort values (checked vs unchecked, then alphabetically by content).

The simplest initial API would take a generic comparison function that is passed two element objects, inside the function, the author could then query child elements, attributes, or properties, and compare them in order.

Example:

container.reorderChildren((el1, el2) => {
/* sort checked items before unchecked,
   then alphabetically by description */
  return (el1.querySelector(".ToDoList__done").checked 
          - el2.querySelector(".ToDoList__done").checked) ||
        (el1.querySelector(".ToDoList__description").textContent 
          - el2.querySelector(".ToDoList__description").textContent );
});

A more complex (but easier to optimize) API would take two arrays of functions:

• the first array would define accessor functions, each passed one element object & returning one key value
• the second array would be the comparator functions, which would be passed the key values accessed from two different elements by the matching accessor function. The first comparator to return a non-zero value would determine the relative order of the elements. Comparators could be left null to use the natural comparison order of whatever data type is used for the key. (Or, if people would prefer to be consistent with JS Array sort(), a null comparator could mean coerce to string and then compare using alphabetical order. But that's less useful.)

The optimization benefit of this approach, compared to doing it all in a single sort function, is that you'd only run each accessor function (which might include things like querySelector, or normalizing strings, or parsing dates) once per element, instead of doing that work for every pairwise comparison. In addition, for authoring, it makes it easier to dynamically change which keys you are sorting by.

Example of this second API:

const sortingKeys = {
dueDate: (el)=>(new Date( el.querySelector(".ToDoList__dueDate").textContent)),
label: (el)=>(el.querySelector(".ToDoList_description").textContent),
done: (el)=>(el.querySelector(".ToDoList_done").checked),
}
const sortingComparators = {
dueDate: (a, b)=>( (isFinite(a)-isFinite(b)) || (a - b) ),
    //valid dates before invalid, then sort by Date
/* label would sort by default comparator */
done: (a,b)=>(a - b)
    //this would be default comparator if we don't convert boolean to string
}

let sortBy = [done, dueDate, label]; // this would change based on user selections
container.reorderChildrenBy( sortBy.map((key)=>sortingKeys[key]) ,
                             sortBy.map((key)=>sortingComparators[key] ) );

(One thing missing from that example is a way to reverse the sort order. Not sure if that should also be part of the API, or if it makes sense to require the author to adjust the comparator functions.)

[annevk]

It would probably be good to look at various JavaScript sorting libraries and see what they have on offer. (HTML tried to offer sortable tables before, but perhaps that was too high-level and an API is the right answer here.)

[domenic]

The trick here is creating something that's simple enough to be attractive and woo folks away from CSS ordering, but isn't too restrictive. My thought was something like this strikes the balance:

parentEl.reorderChildren(el => el.dataset.order);

// Perhaps even this, as an overload?? Then we don't cross back into JS at all.
parentEl.reorderChildren("data-order");

where it converts the return value to a number and does sorting that way.

The alternative is going full-on comparator like @AmeliaBR's version. But I think that tips the feature into the territory of losing out to CSS ordering on ease of use. It also hurts potential performance benefits; instead of calling into JS for the comparator n times, you call in at least O(n log n) times.

On the other hand, requiring the sorting key to be numeric as I have done hurts the cases where you want to do string comparison :-/. It's really a question of how big the scope here should be, or stated another way, how much we want to tradeoff authors doing setup work to prepare for a simple reorder call vs. authors doing complex reorder calls.

[AmeliaBR]

To clarify, @domenic, you're suggesting that the accessor function/attribute would need to return an integer index? Or at least numeric? (That seems more useful than string comparison, which is what I was thinking was meant by using an attribute value.)

With a numeric key, an author could map the child elements to an array, sort that with custom JS comparators, and then save the resulting array indices on the elements. Which is no worse, from an authoring perspective, than any existing options for sorting elements. Although it does mean that the sorting is happening twice: once in JS, to generate the index values, and then once in the DOM method, to sort the actual elements by the indices. But for a table-sorting use case, where data in the table isn't changing, you would only need to calculate the sort order for each key once.

Could the method be overloaded, so that if the sort key parameter is a function, it gets called for each element, otherwise it's used as the name of an attribute to parse? Or is that too much of a JS thing for a DOM API?

What about the idea of taking a list of different keys, for tie-breaker values (so that, for static content like a data table, you could calculate out the sort order for each key separately, and store in different element attributes/properties)? And/or having an easy built-in way to reverse the sort order?

---

Per @AnneVK's question, What Would JS Libraries Do?

• D3's selection.sort takes a generic comparator function, although the comparator function runs on the bound data objects rather than the elements themselves. (D3 also includes ready to use ascending/descending comparators for simple data types.)

• JQuery doesn't have a built in method of sorting selections, nor any official plug-ins. Most examples I found just use JS array sort & then re-insert the elements into their parent container one at a time.

• This utility library, TinySort (which came up when searching for JQuery plug-ins, although it's dependency free) is interesting because it doesn't require the author to specify comparator functions. Instead, it takes complex customization objects describing which value to use for comparing (including an optional selector to select a child element from each element in the list, before extracting an attribute or text content or certain other properties). The number of options would probably make it overly complex for a DOM API, though.

• Angular has an orderBy directive for ngRepeat components. It takes the name of a data property (you're sorting the array of data objects used to fill out the template, not the final elements) or an accessor function or an array of names/functions. By default, it sorts according to data type (e.g., numeric vs string), but you can also set a custom comparator function. I don't know if it reorders existing elements on update or if it keeps the elements in order & modifies their content to match the new data (probably the second).

• Vue.js requires you to sort your data array before updating a list of components defined by a v-for directive, but it allows you to specify a key for matching existing elements with data, forcing a true DOM re-order instead of modifying elements in place.

• React doesn't seem to have any standard built-in approach to sorting a list of components; lots of different examples/plug-ins come up in a search. I suspect they're all using JS array sorting somewhere under the hood.

[domenic]

you're suggesting that the accessor function/attribute would need to return an integer index? Or at least numeric?

Yeah, that was the idea.

Could the method be overloaded, so that if the sort key parameter is a function, it gets called for each element, otherwise it's used as the name of an attribute to parse? Or is that too much of a JS thing for a DOM API?

Right, that overload was what I was implying with my "Perhaps even this" sample.

What about the idea of taking a list of different keys, for tie-breaker values (so that, for static content like a data table, you could calculate out the sort order for each key separately, and store in different element attributes/properties)?

I'm hesitant about this kind of scope creep, but it might be doable. However, note that it's easy to do on top of the simpler API: el => getKey1(el) * el.parentNode.childElementCount + getKey2(el)

And/or having an easy built-in way to reverse the sort order?

Again I'm unsure on the scope creep. For example JS's sort() doesn't have such a facility; you have to modify the sorting comparator. Here, similarly, you'd modify the sorting mapper: el => -getKey(el).

---

Great survey of existing libraries.

I also forgot to mention that your concern about non-element children is a real one and I'm not sure what the right answer is. I do think for most use cases there won't be any, but does that justify making an API that does something strange like shuffling them to the end?

[domenic]

Also I should note I'm not wedded to the idea of a numeric key-based method. A comparator function like JS's array.sort() seems like a better fit with the existing platform, and a bit more powerful, but it definitely brings extra complexity. I'm just unsure.

[bradkemper]

I don’t think any of that would woo me away from using CSS to move a navigation bar to a different spot for mobile. What would be better would be a CSS property/value to indicate that it was OK for AT and tab order to be affected by that visual order change.

[annevk]

If we define this as

1. Remove all children.
2. Sort.
3. Insert sorted children.

we could make it a primitive of sorts that generates a single mutation record. That would also ensure script doesn't have much chance of changing the world view too much.

[fantasai]

There's two reasons people use order: one's convenience, and the other is speed. We'd need to address both, though not necessarily in a single API.

Having a sorting method that takes a comparator function which accepts two elements would be convenient, and might be worth having, but it alone wouldn't solve the problem here. As @domenic says, we need something that doesn't call back into JS for the simple cases, and as @annevk says, it should be an atomic operation from the DOM's perspective. Otherwise we give up most of the optimization opportunities that would allow for comparative performance.

Sorting by passing in an attribute name would get you parity with Roma's CSS-based solution, both in simplicity and (insofar as possible) performance. If it's not too hard, I'd suggest accepting numberish things rather than just numbers, so that you can get dates and dimensions and currency sorts (on normalized values) for free. Folks wanting string sorting or other fancy operations client-side would need to either generate numeric keys, or use a method that takes a comparator-function. (They can't use order without some kind of key preprocessing anyway, so that's no different.) Such an API might be worth having as well, though--its convenience and power, rather than performance and simplicity, would be the draw.

@bradkemper That's off-topic.

Whatever we end up with here, please file an issue back against Flexbox to add some good examples, to steer people towards it once it's available. :)

[guest271314]

For N elements there are at least N! distinct possible renderings of the content without duplicate orderings of the sets. A map of the total possible permutations of the input data (HTML content as string) could be created corresponding each set to a distinct logical key. When the predefined conditions are met, the value for the single logical key can be set at .innerHTML or .outerHTML of N elements. The total possible input data (for example, HTML, JSON, etc.) map of possible orderings can be stored in document itself; at an element data-* attribute (as JSON); <template> element; or other node for example a ProcessingInstrcution node. The sorting would take place once for initial data, and once more when data is added to the set; following the content orders can be retrieved from the mapped set of possible orderings when the logical conditions are met.

[AmeliaBR]

we need something that doesn't call back into JS for the simple cases, and as @annevk says, it should be an atomic operation from the DOM's perspective.

Wouldn't using Anne's idea, of describing the operation in terms of grouped transactions, allow the JS comparator approach at least pass the second measure?

The only question is whether you'd run the comparator function (on all elements, to determine the abstract sort order) before touching the DOM, or if you extract all the elements first, and sort them in a detached state. The first approach makes it more "atomic", and allows you to use comparator functions that only work on attached elements, but any DOM-altering side effects in the comparator could make the sort order undefined.

I'd suggest accepting numberish things rather than just numbers, so that you can get dates and dimensions and currency sorts (on normalized values) for free.

That seems to open up a lot of ambiguity. What determines the parsing rules for converting from string attribute values to the correct numeric type?

[guest271314]

@AmeliaBR Intl could be used to normalize date and time values at HTML element attribute or text content.

The index of an element within a collection of N possibly infinite sets of values is sufficient to get that specific set within the total possible lexicographic arrangements of individual values within a set of a collection.

If the elements of any set are unique the values themselves can be ignored.

The question, from perspective here, would be is it more expensive to create a map of the total dataset with corresponding logical key to get an index of a pre-sorted and stored set which retrieves that unique value, or to sort the dataset dynamically at each call to the sort function without storing the accrued results of the sort function calls, to prevent for example, having to iterate to 51 out of 100 or 49 in reverse to get a single sort order that will not change from the initial call to the compare function to the next call to the compare function.

[chrishtr]

Agenda+ to discuss this proposal at an upcoming triage meeting. There is now a ED CSS specification for display order:

https://drafts.csswg.org/css-display-4/#display-order

And as referenced here, it would be good to also have a DOM sorting API for some use cases.

[chrishtr]

Full proposal:

parentEl.reorderChildren("my-attribute"); // sorts chidlren of parentEl numerically by my-attribute

And:

1. The update happens atomically, with Mutation Observer callbacks at the next microtask checkpoint, and that each observer receives at most one collected observation record.

2. The older MutationEvents are not fired at all for this operation. (Those are synchronous and deprecated, and I don't think we need/want to extend them to new APIs like this, and will get in the way of an efficient API.)

3. Any side effects such as reloading iframes still happen as usual, similar to if you call insertBefore on an element that is an iframe and change its DOM location.

[WebReflection]

This is close to React keyed nodes so it allows somehow DOM diffing, a feature I’ve asked for years ago already, except is limited to always same list of nodes. Why not doing an extra step to handle also removed nodes and eventual new nodes, at this point? That way all diffing libraries can be gone and performance would win. udomdiff among others can help suggesting the implementation details too, happy to help as I can as I wrote 5 different algo for diffing already.

[WebReflection]

Why not doing an extra step to handle also removed nodes and eventual new nodes

As couple of examples/ideas around this:

• parentEl.reorderChildren(parentEl.childNodes) would basically be a no-op
• parentEl.reorderChildren([...parentEl.childNodes, document.createElement('p')]) adds last P to the list
• parentEl.reorderChildren([...parentEl.childNodes].slice(1)) drops first node
• parentEl.reorderChildren([....childNodes].sort(byAttribute)) does what's being proposed in here but it doesn't limit the feature to a single attribute
• parentEl.reorderChildren([document.createElement('p')]) would basically replace children with just the P element

Maybe reorderChildren is not the most semantic way to describe this variant but it will solve all diffing and ordering issues we have (yesterday) today and tomorrow without requiring attributes all over the place to keep track of the reordering ... wouldn't this be better? the described behavior of a single MO record with addedNodes or removedNodes still makes sense, no synchronous old style mutation events should be fired, iframes can do iframes things, but everything else will be just natively "diffed" and we won't need to ask again for this in the future.

[chrishtr]

React keyed nodes

I'd like to understand the exact use case you're describing. Is it this:

Replace children of a node with a given list of nodes, in the specified order

And expect the UA to do so in the most efficient way possible, such as by avoiding re-creation of nodes in the list that are already children of the given node?

Is an algorithm for this use case deployed in a diffing algorithm for React or some other common library?

[WebReflection]

I am surprised react keys are not known today, but this is the documentation about it.

Ported to this reorderChildren idea, let's take a basic list as example:

<ul id="list">
  <li data-order="2">b</li>
  <li data-order="1">a</li>
  <li data-order="3">c</li>
</ul>

If I understood correctly what's being proposed, a list.reorderChildren("data-order") would produce the following output:

<ul id="list">
  <li data-order="1">a</li>
  <li data-order="2">b</li>
  <li data-order="3">c</li>
</ul>

and every single <LI> element in the list is preserved, meaning the second <li data-order="1">a</li> in the initial list, will be exactly the same <li data-order="1">a</li> found as first element child of the list, so if that's the case, we're having the very same behavior keys in React are meant to bring: same node per reference.

Let's see a swap nodes, using the keys as extra approach:

<ul id="list">
  <li data-order="1" key="a-key">a</li>
  <li data-order="2" key="b-key">b</li>
  <li data-order="3" key="c-key">c</li>
</ul>

Now swapping 1 with 3 would preserve the node identity and the JS would be like:

list.firstElementChild.dataset.order = 3;
list.lastElementChild.dataset.order = 1;
list.reorderChildren("data-order");

Now we have preserved identity and a way to diff a previous state with the current one, where some node got prioritized or de-prioritized but all of them have kept their references.

This is an extremely limited way to deal with the potential of a diffing previous-next API that could not only order by all means, not just numerically for attributes that also are always strings on the DOM, but it could take into account new nodes either inserted or removed at a specific index of the list, so that such API would cover every single possible use case out there, instead of requiring effort to cover only numerical sort out of strings, avoiding possible growing and shrinking lists to benefit from such API (a TODO list is already a good example of that, as mutable state to handle).

I hope this explains better why this API would have 1% of the potential it could have if it would instead just diff the passed along list of nodes as iterable that could benefit from any sorting method, not just numeric, and avoid tons of boilerplates for libraries authors to deal with just the number, as that requires a "keep in sync" attributes with diffing for an API that, as presented, already takes care of diffing previous nodes with the new ordered one.

[annevk]

@chrishtr as per https://github.com/whatwg/dom/issues/891#issuecomment-1103926483 I think solving the interoperability issues around #808 is a pre-requisite here.

[Bobris]

Please first focus on lower level API (ability to set new/reordered array of DOM children), as sorting by attribute value could be easily implemented on top of it. Also same feature should be working in SVG context.

[chrishtr]

The diffing use case sounds interesting, but still not clear to me how in practice an API like is being proposed here solves that use case. (And there is also the replaceChildren API...)

In any case, I would like to focus this issue instead on solving the use case of a visual order sorting of DOM siblings that is easy enough to use that developers will, like @domenic said, use it instead of CSS order when CSS is not the right tool for the job.

The original comment in this issue is really about ergonomics of sorting children, not performance. I'd like the triage meeting discussion this week to focus on this use case, whether it is important enough to support directly in a DOM API, and how best to meet it if so (assuming it's needed, that's how I arrived at this proposal).

[dead-claudia]

Speaking of CSS order, I have a question: does that also impact the accessibility tree, or does that only impact visual layout?

[chrishtr]

Speaking of CSS order, I have a question: does that also impact the accessibility tree, or does that only impact visual layout?

That's a good question. Right now it does not affect accessibility or tab index order, but there are discussions to change that so as to improve accessibility when CSS order is used.

[dead-claudia]

The reason I ask is because if it's handled that way, you could do sorting and similar reordering patterns as follows, deferring most of the real work to the layout engine and other things that consume styled DOMs:

• Let itemList be the list of items to display somehow and nodeList be the list of nodes corresponding to each item.
• Initially, set the order CSS property to each node's offset. Initially, this would look like 1, 2, 3, and so on.
• To sort:
  • Create an orderList to the list of offsets in itemList.
  • Sort orderList by the items in itemList, using itemList[i] instead of orderList[i] === i where applicable.
  • Set the order properties of each node in nodeList to the value of orderList at that corresponding offset.
• To change back to sequential, just set the order property of each node to their offset in nodeList. Changing to reverse sequential is as easy as using nodeList.length - offset instead.
• To reverse, one could either use the usual tricks with flexbox/grid/text direction/etc. or do the following:
  • Save all the order properties of each item in nodeList to a temporary variable orderList.
  • Reverse orderList.
  • Set the order properties of each node in nodeList to the value of orderList at that corresponding offset.
• For interactive reordering:
  • On drop before, increment all the order properties of each node by 1 that are both less than the node's old index and greater or equal to the target index, then set the node's order property to that target index.
  • On drop after, decrement all the order properties of each node by 1 that are both greater than the node's old index and less or equal to the target index, then set the node's order property to that target index.

This of course is pretty limited and only works for lists with a single shared ancestor, and custom elements that manage their own elements separately from their shadow roots and such would still have to implement it manually.

I wonder if this would work? Or would it be too hackish? Obviously it's not the most elegant, but it does use the CSS order property for more or less what it's there for. And of course, one could imagine a native utility to back this up as well.

Edit: SVG would also need an attribute added with similar functionality. Just wanted to call that out as a potential concern.

[WebReflection]

And there is also the replaceChildren API...

As that name suggests, replaceChildren does, in fact, replace children, it doesn't re-order children.

With this argument, we don't need any sorting API neither:

parent.replaceChildren(
  [...parent.children].sort(
   (a, b) => (
        parseFloat(a.dataset.order) -
        parseFloat(b.dataset.order)
    )
  )
);

If the sorting is smarter at not removing children that don't need to be moved (less mutations on the tree) then it is a missed opportunity to confine that ability to same list length and same nodes only and via attributes, that is why I've raised my suggestion we could do a little more and solve diffing forever on the DOM.

[WebReflection]

@chrishtr it's worth mentioning that abusing the API already allows diffing (at least per elements, not per mixed elements and text nodes (or comments) ... example:

const diff = (parent, prev, curr) => {
  const {length: plength} = prev;
  const {length: clength} = curr;
  const childs = [];
  let i = 0, length = i;
  // order old nodes after
  while (i < plength)
    prev[i++].dataset.i = (clength + i);
  i = 0;
  // order new nodes before
  while (i < clength) {
    const child = curr[i++];
    child.dataset.i = i;
    if (child.parentNode !== parent)
      length = childs.push(child);
  }
  if (length)
    parent.append(...childs);
  // reorder all by attribute
  parent.reorderChildren('data-i');
  // drop nodes still there
  length += plength;
  if (i < length) {
    const {children} = parent;
    const range = new Range;
    range.setStartBefore(children[i]);
    range.setEndAfter(children[length - 1]);
    range.deleteContents();
  }
  return curr;
};

Assuming for now the polyfill would be like:

Element.prototype.reorderChildren = function (attributeName) {
  this.replaceChildren(
    ...[...this.children].sort(
      (a, b) => (
        parseInt(a.getAttribute(attributeName)) -
        parseInt(b.getAttribute(attributeName))
      )
    )
  );
};

Given the following operations would move, insert once, and drop all at once on every needed situation:

document.body.innerHTML = `<ul><li>a</li><li>b</li><li>c</li></ul>`;
const ul = document.body.firstElementChild;
let children = [...ul.children];
// nothing happens
children = diff(ul, children, children);

// a swaps with c
children = diff(ul, children, [children[2], children[1], children[0]]);

let li = document.createElement('li');
li.textContent = 'd';
// result into c, b, a, d
children = diff(ul, children, children.concat(li));

// b, a remain
children = diff(ul, children, [children[1], children[2]]);

// d, b
children = diff(ul, children, [li, children[0]]);

// z
children = diff(ul, children, [document.createElement('li')]);
children[0].textContent = 'z';

After all this already helps diffing nodes in a keyed like way so maybe it's OK to have at least this helper and be creative around its full potentials.

[pygy]

Chiming in here since I rewrote Mithril's keyed diffing algo.

There are quite a few things to have in mind if you want to solve node sorting holistically:

• not all children are elements, you can't rely on the presence of attributes on text nodes and comments
  • some frameworks (finely grained) use comments to delineate the dynamic parts of the DOM
• sometimes you only want to sort a subset of siblings, not all the children of an element
• some keys map to "fragments" (I wish there was a way to refer to a contiguous subset of the children of an element edit: broodmates could do...).

Here's an example that showcases some these scenarios (no comments here since Mithril does not use them). Note that when we move the nodes around in a keyed list, the DOM node identity is preserved.

For the details of the operation, it would be ideal from an app developer perspective to make the reordering

• an atomic operation
• that doesn't detach the nodes from their parent or the document
• thus preserving the state of iframes, media elements, and the focus.

With these concerns in mind, IMO an optimal API would be something like this:

parent.replaceRangeAtomically(
  previousSibling: Node|null,
  nextSibling: Node|null,
  newNodes: Array<Node|null>
)

• A null previousSibling means that the range to be replaced includes the first node of the list. Likewise for a null nextSibling and the last node.
• If the bounds are not present in the parent or out of order, throw.
• null values in the newNode array are ignored (we also ignore booleans in Mithril, not sure if you'd want that here).

Regarding the implementation, since moving nodes is expensive, we minimize the number of operations by computing the longest subsequence of keys that have the same order in the old and the new list, and only move the other nodes. So if we move from nodes with keys [A, B, C, d, e] to [A, d, B, e, C], A, B, C is the longest ordered subsequence, and we only move d and e. This may be less of a concern if the reordering happens entirely in native land, and if you generate a single mutation event for the reordering. In your use case, the key is the Node itself.

[WebReflection]

@pygy you just rewrote my initial comment around making this API more generic, and all your algorithms are already part of udomdiff, domdiff, majinbu, or speedy Mayern approach I’ve explored, but like I’ve demoed already, those are implementation details and this API already provides a way to diff natively. The only point I fully agree is the “node not leaving the DOM while sorted” so I’m plus 1 on iframes and focused elements, to name a few, not re-initializing themselves, same way diffing already works in every modern library, but I don’t know full constraints behind this expectation

[pygy]

@WebReflection This comment was addressed to the WhatWG members, not you personally.

1. you missed the part where I suggest targeting a subset of children
2. I'm providing context and examples of things that happen in the wild (using Mithril rather that React because I'm more fluent with it, but none of the algos are mine conceptually... The longest ordered subsequence comes from Boris Kaul's IVI, and the pioneering fragment support in Mithril is the work of Leo Horie).
3. This was meant as support for your call for a more generic API, and going a bit further re. versatility (see point 1).
4. The longest ordered subsequence may or may not be relevant, I'm mentioning it here because it is optimal from the JS side, and it was pretty obscure before Boris added it to IVI. It wasn't mentioned or implemented anywhere before that, and even if it is now well known among framework authors, it may not be beyond that small circle, and may thus be useful for the implementers.