Reconciliation

ShadowJS has no virtual DOM, so there is exactly one place where "old" is compared with "new": a region, the run of DOM nodes that one insert owns. When the value of a region changes, insert flattens it to a list of DOM nodes and makes the parent's children equal that list. The rules are:

• A node that is in both the old and the new list keeps the same DOM object, including its input value and scroll position. Focus and iframe state depend on the browser's support for state-preserving moves, described below.
• Nodes that left the list are removed. Nodes that are new are inserted.
• Surviving nodes that must change relative order are moved, each at most once, with the minimum number of moves for the order they have.
• Moves use Element.prototype.moveBefore when the parent has it (it preserves focus and iframe state), insertBefore otherwise.

The algorithm (reconcileNodes in @shadow-js/web/extend):

1. Trim the common prefix and suffix. Appends, prepends and removals at either end touch only the nodes that changed. An unchanged list touches nothing.
2. Remove the nodes that left.
3. Place the rest from the end backwards. Nodes on a longest increasing subsequence of surviving positions stay; every other node is moved or inserted directly before the node that follows it. Patience sorting makes this O(n log n).

Two components sit on top: For and Index produce stable node arrays (the same row node for the same row), which is what makes the identity rule useful.