Dom: 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.