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 #891 (comment) 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.

[WebReflection]

@pygy im with you, I just don’t think the generic API is being considered, so something is better than nothing. I already proposed a generic API alternative that could work with other child nodes too, and by no mean I meant to appropriate to myself algorithms used here and there. Majinbu is out of levenshtein distance as example, only udomdiff is from scratch yet based on LOS in a branch of the logic. Again, thanks for your input, I hope it’ll be considered, but I also think current proposal might address already most use cases.

[pygy]

It does not address this case (and variations thereof):

const GimmeAKeyedList() {
  return someArray.map(x => <div key={x}>x</div>)
}

render(root, <div>
  <hr />
  <GimmeAKeyedList />
  <hr />
</div>
)

Suppose that GimmeAKeyedList can redraw on its own (as it would in a finely grained framework, or in React with useState) in order to tap into the proposed API, it has to

1. determine in what order it wants to render its own values
2. scour the parent north and south to gather the list of elements that precede and follow its own.
3. assemble 1 and 2 into a single list
4. pass it to the browser which has to consider more nodes than needed.

In order to handle that case efficiently, frameworks need an API that has the conceptual shape I suggested. I could also be

parent.replaceChildren(nodes: Array<Nodes|null>, options?: {previousSibling?,nextSibling?})

Which would make it more ergonomic when you want to replace/reorder all the children of an element.

[WebReflection]

In that regard doesn’t address “pinned changes” neither, those confined within a parent subset of nodes, common with UI when changes should be confined, addressed by my libs or lit via comments to pin-point before what node changes should happen, or within comments nodes as delimiter of a virtual fragment.

[pygy]

Could you give an example? Edit: do you mean that the original proposal doesn't work, or my suggestion?

[WebReflection]

@pygy your suggestion is an example ... uhtml/lit or others would use a <!--comment--> to pin-point the array of items that indeed cannot be ordered if the suggested proposal works on every node at the parent level. The diffing in template literals based libraries has comments as boundary for lists that change through new ordered items so the proposal as is wouldn't change and it would ask for an extra <div> container around the array ... that means: this proposal works only at one level on the parent but it's also being discussed to replace the need for CSS ordering so maybe that's good enough as initial API/helper?

[WebReflection]

P.S. I like the parent.replaceChildren(nodes: Array<Nodes|null>, options?: {previousSibling?,nextSibling?}) idea, but replaceChildren make all nodes leave the tree and re-initialize them all, even if exact same children are replaced.

If this proposal wants to replace the need for CSS ordering, where none of this happens (including iframes, just moved around but they never leave the DOM) we can't use replaceChildren unless among options there's a diff flag that suggests the intended behavior.

[pygy]

Re. not detaching nodes, agreed (as per my first comment), it was more of a suggestion for the API shape. It would also be nice to be able to move nodes diagonally (changing their parents) within the same document while preserving state. The same method could be used.

@WebReflection so you have nodes that are pinned within lists of nodes that can move? Did I get this right? I've dabbed with a finely reactive framework and also use pairs of comments, but to delineate the dynamic bits. So parent.rearangeChildren(nodes, {previous,next}) would almost be a direct replacement for what the diffing logic.

The only missing piece would be delayed node removal for exit animations. The options object could take an async delayRemoval(){} callback, called once per node removed, that would wait until the promise resolution to perform the action. Pre/post-reordering hooks for list animations would also be handy, but these can live in user space.

[annevk]

Could you please take this conversation to https://whatwg.org/chat or equivalent? There's over a 150 people watching this repository and the lengthier and less clear issues become, the less likely they are to get fixed.

[josepharhar]

Based in the discussion at the last triage meeting, I am interested in trying to satisfy both #586 and #891 with one new method: Element.reorderChildren().

Element.reorderChildren will take an array of nodes which are already children of the element and then reorder its children to match the provided list. If any nodes are in the given array but not in the child list, they are ignored. Similarly if any elements of the provided array aren’t Nodes, they are ignored. If any nodes are in the child list but not the array, they preserve their relative DOM order to each other but are placed at the end of the new child list. The purpose of all of these conditions is to ensure that reorderChildren() only reorders and can never add, remove, or reparent nodes.

No synchronous Mutation Events are fired. A MutationObserver “childList” observation will be emitted. This might need a new MutationRecord type such as movedNodes for this.

DOM Ranges which include a current child at the beginning or end of the Range will retain that same child after the reorder.

Images, iframes, input elements, embedded objects and other elements which maintain internal state retain that state and cannot observe the change internally to the element.

I think solving the interoperability issues around #808 is a pre-requisite here.

I’m happy to help with interop issues here but I believe that it’s pretty straightforward: no script can run synchronously during a call to reorderChildren(). Since iframes and script elements can’t be inserted or removed, and no synchronous mutation events can be fired, this shouldn’t be possible.

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.

If we want to insert or remove nodes, then we have to not only resolve #808 but also Ryosuke’s concerns about iframes and scripts. I’d like to help out with DOM diffing but I don’t think that is within scope of this method to simply reorder nodes. However, with the new (performant) reorderChildren() primitive, diffing libraries can use a combination of remove(), appendChild(), and reorderChildren() to optimally reconstruct the children of an Element.

[tabatkins]

@josepharhar I strongly support the proposal of a basic reordering primitive, which'll allow people to invent their own sort/etc operations on top of it. That's a great idea, and your description of the behavior sounds ideal.

However, that still leaves the base case ("I want to sort these table rows by the value of some cell" or "I want to sort this list by the value of some attribute") relatively unergonomic to do without a library. (At minimum it's el.reorderChildren([...el.childNodes].sort(cmpFn)), and that involves dipping into the DOM many times during the sort.) I think it's necessary to have a reasonably sugared API for the common case as well as the generic mechanism.

Luckily having the base primitive means we don't need to get complicated with the sugar; we can focus on the simplest case and let libraries handle all the in-between. I suggest having a second reordering method (suggested name sortChildElements()) that, as suggested above by Domenic/fantasai, takes a key function and sorts by its output, along with an overload that takes a string and sorts by the number-parsed value of the named attribute on the children. (That is, el.sortChildElements("foo") is equivalent to el.sortChildElements(x=>+x.getAttribute("foo").) This intentionally skips non-element nodes, for simplicity; they'll be sorted to end as per your suggested semantics for reorderChildren().

So total suggested API:

partial interface ParentNode {
	Element reorderChildren(sequence<Node> children);
	Element sortChildElements((DOMString or UnaryElementKeyer) keyFn);
};

callback UnaryElementKeyer = any (Element);

(I'm assuming that these return the parent node. They could also return undefined to match the similar existing functions, but god that's an annoying argument pattern.)

(sortChildElements() could also possibly take an optional second argument that's a comparator function, a la Array.sort(), and which gets fed the keyed values. Not strictly necessary for the common cases, but it's a small add that expands the things one can easily do and matches it up with existing sorting libraries.)

---

sortChildElements() approximately desugars to the following use of reorderChildren():

ParentNode.prototype.sortChildElements = function(key) {
	if(typeof key == "string") key = x=>+x.getAttribute(key);
	const keyedChildren = Array.from(this.childElements, el=>[key(el), el]);
	keyedChildren.sort((a,b)=>a[0] < b[0] ? -1 : a[0]==b[0] ? 0 : 1);
	return this.reorderChildren(keyedChildren.map(x=>x[1]);
}

[pygy]

@josepharhar

reorderChildren is almost ideal as far as reordering goes (no addition/removals). I'd let users specify a previousNode though. It would not complicate the implementation (unlike ranges which require a linear check to verify the bounds are in the right order in the children list, lest you end up with a circular result).

It can be implemented in linear time with the following algo (I suppose this is what you had in mind).

• given parent.reorderChildren(nodes: Array<ChildNode|Cruft>, previousNode?: ChildNode|null = null)

• if previousNode is in nodes throw

• iterate over each non-cruft node of nodes in reverse order:

  • detach node from the children list, making its previous neighbors siblings.
  • insert node after previousNode (prepend it if previousNode is null)

This lets the child list in the state you described.

parent.firstChild and friends can now be fixed up. As an optimization, you can first scan nodes from both ends looking for contiguous nodes, narrowing the [previousNode, lastNode] range.

Having the possibility to specify the previousNode lets user avoid wasteful scenarios where they know where they want things to happen (like, say, swap the last two nodes of a list). In the most extreme case not having previousNode could lead to N x M operations: suppose <List><Sublist /><Sublist />...</List> Where SubList returns a fragment, and all sublists are sorted according to the same criterion. When the criterion changes, In order to rely on reorderChildren each sublist would have to scan its previous siblings and pass them all to the browser which would have to skip them. A two way trip for naught.

I still would like to have a way to re-parent nodes without reinitializing them (assuming there is implementer interest too), but this would require a different API. I'm therefore mapping and compiling the state of affairs re. #808 and side effects timelines. There are many inconsistencies but I think UAs could be brought in line with a consistent model without breaking WebCompat™ (relying on the fact that, since the timeline is inconsistent, relying on it right now is not viable).

---

Edit: thanks to Anne and Tab for bouncing ideas about this in

Edit again, the algo is even simpler than I thought.

[josepharhar]

nodes: Array<ChildNode|Cruft>

iterate over each non-cruft node

What does cruft mean?

prepend it if previousNode is null

Any reason to prepend instead of append like my last comment suggests?

[pygy]

Cruft is either not a Node, or a Node that isn't a child of parent (values to be ignored, in other words, per your previous post).

If the method is meant to evolve in the future to accept non-child nodes, we could also throw TypeErrors for now when "cruft" is encountered, leaving room for the API update if we crack external nodes at some point.

By prepending in reverse order you automatically leave the children that were not in the nodes array at the bottom of the child list (assuming previousNode is null).

I had not understood you meant to append.

[justinfagnani]

Responding to just the reordering primitive use case here:

Preserving focus and not reloading resources is absolutely great, however we get there.

However, with the new (performant) reorderChildren() primitive, diffing libraries can use a combination of remove(), appendChild(), and reorderChildren() to optimally reconstruct the children of an Element.

reorderChildren() does sound like a nice improvement, but thinking how I'd use this to reimplement our list updating, I would personally rather have one call to move, add, and remove children, and limit the operation to a sublist of the child list.

Something like parentNode.updateChildren(children: Iteratable<Node>, from?: Node, to? Node)

Because

• Our looping primitives can be used in the middle of a child list. Right now they only need local knowledge of their contents, but without start and end node support they'll have to gather all the children on the parent to call reorderChildren() correctly.
• We'd have to track added, removed, and moved nodes separately, and added nodes would have to keep track of their new reference node to be able to call insertBefore(). This isn't terrible, but it might be more complicated than the individual remove and insert calls we use now. In some ways a moveBefore() that only took an existing child would be simpler to adopt. swapChildren(a, b) would be a very interesting option to given the current implementation of some of the list diffs. Otherwise, it seems likely simpler to build one list of the new node order and apply that in one call.
• If there are other perf benefits around skipping or batching integrity checks and mutation events, could that extend to adding and removing nodes too?

---

Sorting child nodes as in the other use case is something I've had to deal with less often, and usually via the looping mechanisms we have for the reorder use case, but I have seen it with tables. I think there it'd be very useful to be able to sort a sublist too, via before and after reference nodes.

[annevk]

I’m happy to help with interop issues here but I believe that it’s pretty straightforward: no script can run synchronously during a call to reorderChildren(). Since iframes and script elements can’t be inserted or removed, and no synchronous mutation events can be fired, this shouldn’t be possible.

The reason I want to build on top of #808 is because that will make it clear what kind of behavior elements have for removal and insertion. Some of that behavior we may want to preserve when moving them, even though we would not want to preserve all behavior (such as the behavior that results in script execution). Therefore I think we should solve that issue so we know exactly what the removal and insertion semantics are and can then much more confidently discuss move semantics.

[noamr]

What if instead of fixing this as a sorting problem, we treat it as a batched-update problem, and present an API that does specifically that?

e.g. (strawman) a function that takes an array of remove/insertAdjacentElement calls
and performs them atomically, leaving all side effects (including iframe reloads, mutation events, scripts, anything) to after it's done:

document.executeBatchUpdates([
   { remove: node },
   { insert: [parent, child, 'afterbegin'] }
])

Side note: at Wix we had to jump through crazy hoops because of the state-reset-at-reparent-or-reorder issue, this is far from being an exotic problem in my experience.

[annevk]

@noamr see #270.