Re: [whatwg/dom] Add convenient, ergonomic, performant API for sorting siblings (#586)

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).

Here's an [example](https://flems.io/#0=N4IgtglgJlA2CmIBcBWADAOgOwDYA0IAzgMYBOA9rLMgNpp5oC6BAZhAobaAHYCGYiJCAwALAC5hqBYuW5j4c5CAA8UCADcABNAC8AHRC8ADkYMA+ZQHo16s3u7KjpeNqj6QUcmHNWn8MyAEhPAIxGIQspxCAIxIAExoIAC+eDz8gsIAVpzSsvKKQjLchGKaACrkAOaVCACyLjqaABQAlJo6ZprA9pqaCKXqEIQQAEYI7ZpipACu8D2azmLTpNxdg-AA7kjNwMQi7FDO3EltHZo0871gTQDkI9NiYrI3eF2yxLAQxADWrcCDwzGDU0AEIAaMEEkUpoDBVqggDC08JdNNcDIQjLxuAZXgZABeEiORq16mnBQM0ADIKZo9gcjvNGEl7EzsdwiiU+kNSo0LiAAB44mEgEa8UiCgwigBegpuAE8XkKAI7TAWBIWS8ikVWMez2MAYMDkaZyJqeYjTARyDAjchQWUYNikEoAYX2sCgr26xPWW2ap06F2JvUslk0vBpXiMsgUpTEIl4pUWy2KYc0LFIvEqltK5BYmm4tvghE0hC8Llzmg2+z2KJDNKxmhGLie8PgUE0dr4kGIvCospR1zhNXg9VxIBonf4X3zhZ1ICRuqDmjr4e+8Flbc5HIrBagRbD3Hb6cz2cIKM+JQwhE+xHgTTiLQNxiaEHkYHanRRvVf8H1CG4lRxu0OiNNEX6aAA-KiDoZlmMZNMAa6ykgP5gNCaLCoKqFItob4tOB2wYdMgqIeu2yodC2EoguS4Dk0EoPE82JqsA7w3r8LReiSJJ1n4+TtnGQzaMWbCECI8CkJosoJkW4EXmIV6amITStB0TS1AmIgYBmh5eK0mgALSaJgKCaC0LQstx0LomQ-BAoiDJEr07zODJ2xqNemKygAoggp5OZosjTEYUBuR2QywF5vm-jGZ7HPhrIsMaYQRKsHmRbwPl+bFfzzJ4+ryHyYjOnkMYTOIkgAPpNrwDwQCwspNMYRgYEa8ikAAEmUtQADLafARiwLwt5NJYTTKHoeiWJNGwANRmC0TQ0AAesoZiMLNi0TXoc0LZYlTIiAAAkYH2EdcSTdwR0AMyEl0BgQNwnzcHMyDnIyCVJIEIAyGARjsBJyDcNMVBBCE8ApZESjRCgSDXdEySpCAXYZBgxCEDkP2lQUIAAFRdJiMCPZU2zXUYfIANwst9wShOEUMxEgiRJMwIDPd8UQ0GkAhKJAcakOw33LNQQjiGIRiEEgIbGkY3yVGjXiWHzIgC7AAACcQYJrcRK6+KvsAaj0YNk31iLKRgZCQAtGGIiPcxkNV1Q1BkVbAxuY8LShixLUuWDLcsK2AljZAZjvhA1avRBg0QACzYMHhCWJ8IyWGH9Wyi7EhuybBBmxbShWxANvJIyQA) 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:

```ts
parent.replaceRangeAtomically(
  previousSibling: Node|null,
  nextSibling: Node|null,
  newNodes: Array<Nodes|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, 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](https://github.com/localvoid/ivi/blob/41725469a2892b80d27fab803826c4832a0c8744/packages/ivi/src/vdom/reconciler.ts#L585-L813), and only move the other nodes. So if you 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 you 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.

-- 
Reply to this email directly or view it on GitHub:
https://github.com/whatwg/dom/issues/586#issuecomment-1424500714
You are receiving this because you are subscribed to this thread.

Message ID: <whatwg/dom/issues/586/1424500714@github.com>