chinedufn / percy

Build frontend browser apps with Rust + WebAssembly. Supports server side rendering.
https://chinedufn.github.io/percy/
Apache License 2.0
2.27k stars 84 forks source link

Introduce implicit keying #191

Closed chinedufn closed 1 year ago

chinedufn commented 1 year ago

This commit introduces implicit keys to siblings that are being diffed.

This was introduced to solve for the following case:

start: <div> <span><input /></span> </div>
end: <div> <img /> <span><input /></span> </div>

Before this commit, if the input in the above example was focused at the start, it would lose its focused after the patches were applied since the span would have gotten replaced by the img.

Now all elements with the same tag are implicitly keyed such that the diffing algorithm will send up generating patches that will move elements instead of replace them, when possible.

Note that there is a cost to this, since the longest increasing subsequence algorithm that we're using to diff keyed siblings is `O(n log n).

This commit makes it such that n will always be the number of child elements, now that all child elements have either an explicit or implicit key and will all pass through our LCS pass.

Note that the n is the number of siblings across the chldren of two different nodes, not the number of nodes in the entire dom tree.

So, for most realistic use cases n should be relatively small, since most use cases don't have large lists of sibling nodes.