yippee.fun
Precise DOM morphing
morphing
typescript
dom
joel.drapper.me
1type HTMLOrSVG = HTMLElement | SVGElement | MathMLElement
2
3export const isHTMLOrSVG = (el: Node): el is HTMLOrSVG =>
4 el instanceof HTMLElement || el instanceof SVGElement || el instanceof MathMLElement
5
6const ctxIdMap = new Map<Node, Set<string>>()
7const ctxPersistentIds = new Set<string>()
8const oldIdTagNameMap = new Map<string, string>()
9const duplicateIds = new Set<string>()
10const ctxPantry = document.createElement("div")
11ctxPantry.hidden = true
12
13const aliasedIgnoreMorph = "ignore-morph"
14const aliasedIgnoreMorphAttr = `[${aliasedIgnoreMorph}]`
15export const morph = (
16 oldElt: Element | ShadowRoot,
17 newContent: DocumentFragment | Element,
18 mode: "outer" | "inner" = "outer",
19): void => {
20 if (
21 (isHTMLOrSVG(oldElt) &&
22 isHTMLOrSVG(newContent) &&
23 oldElt.hasAttribute(aliasedIgnoreMorph) &&
24 newContent.hasAttribute(aliasedIgnoreMorph)) ||
25 oldElt.parentElement?.closest(aliasedIgnoreMorphAttr)
26 ) {
27 return
28 }
29
30 const normalizedElt = document.createElement("div")
31 normalizedElt.append(newContent)
32 document.body.insertAdjacentElement("afterend", ctxPantry)
33
34 // Computes the set of IDs that persist between the two contents excluding duplicates
35 const oldIdElements = oldElt.querySelectorAll("[id]")
36 for (const { id, tagName } of oldIdElements) {
37 if (oldIdTagNameMap.has(id)) {
38 duplicateIds.add(id)
39 } else {
40 oldIdTagNameMap.set(id, tagName)
41 }
42 }
43 if (oldElt instanceof Element && oldElt.id) {
44 if (oldIdTagNameMap.has(oldElt.id)) {
45 duplicateIds.add(oldElt.id)
46 } else {
47 oldIdTagNameMap.set(oldElt.id, oldElt.tagName)
48 }
49 }
50
51 ctxPersistentIds.clear()
52 const newIdElements = normalizedElt.querySelectorAll("[id]")
53 for (const { id, tagName } of newIdElements) {
54 if (ctxPersistentIds.has(id)) {
55 duplicateIds.add(id)
56 } else if (oldIdTagNameMap.get(id) === tagName) {
57 ctxPersistentIds.add(id)
58 }
59 }
60
61 for (const id of duplicateIds) {
62 ctxPersistentIds.delete(id)
63 }
64
65 oldIdTagNameMap.clear()
66 duplicateIds.clear()
67 ctxIdMap.clear()
68
69 const parent = mode === "outer" ? oldElt.parentElement! : oldElt
70 populateIdMapWithTree(parent, oldIdElements)
71 populateIdMapWithTree(normalizedElt, newIdElements)
72
73 morphChildren(parent, normalizedElt, mode === "outer" ? oldElt : null, oldElt.nextSibling)
74
75 ctxPantry.remove()
76}
77
78// This is the core algorithm for matching up children.
79// The idea is to use ID sets to try to match up nodes as faithfully as possible.
80// We greedily match, which allows us to keep the algorithm fast,
81// but by using ID sets, we are able to better match up with content deeper in the DOM.
82const morphChildren = (
83 oldParent: Element | ShadowRoot, // the old content that we are merging the new content into
84 newParent: Element, // the parent element of the new content
85 insertionPoint: Node | null = null, // the point in the DOM we start morphing at (defaults to first child)
86 endPoint: Node | null = null, // the point in the DOM we stop morphing at (defaults to after last child)
87): void => {
88 // normalize
89 if (oldParent instanceof HTMLTemplateElement && newParent instanceof HTMLTemplateElement) {
90 // we can pretend the DocumentElement is an Element
91 oldParent = oldParent.content as unknown as Element
92 newParent = newParent.content as unknown as Element
93 }
94 insertionPoint ??= oldParent.firstChild
95
96 // run through all the new content
97 for (const newChild of newParent.childNodes) {
98 // once we reach the end of the old parent content skip to the end and insert the rest
99 if (insertionPoint && insertionPoint !== endPoint) {
100 const bestMatch = findBestMatch(newChild, insertionPoint, endPoint)
101 if (bestMatch) {
102 // if the node to morph is not at the insertion point then remove/move up to it
103 if (bestMatch !== insertionPoint) {
104 let cursor: Node | null = insertionPoint
105 // Remove nodes between the start and end nodes
106 while (cursor && cursor !== bestMatch) {
107 const tempNode = cursor
108 cursor = cursor.nextSibling
109 removeNode(tempNode)
110 }
111 }
112 morphNode(bestMatch, newChild)
113 insertionPoint = bestMatch.nextSibling
114 continue
115 }
116 }
117
118 // if the matching node is elsewhere in the original content
119 if (newChild instanceof Element && ctxPersistentIds.has(newChild.id)) {
120 // move it and all its children here and morph, will always be found
121 // Search for an element by ID within the document and pantry, and move it using moveBefore.
122 const movedChild = document.getElementById(newChild.id) as Element
123
124 // Removes an element from its ancestors' ID maps.
125 // This is needed when an element is moved from the "future" via `moveBeforeId`.
126 // Otherwise, its erstwhile ancestors could be mistakenly moved to the pantry rather than being deleted,
127 // preventing their removal hooks from being called.
128 let current = movedChild
129 while ((current = current.parentNode as Element)) {
130 const idSet = ctxIdMap.get(current)
131 if (idSet) {
132 idSet.delete(newChild.id)
133 if (!idSet.size) {
134 ctxIdMap.delete(current)
135 }
136 }
137 }
138
139 moveBefore(oldParent, movedChild, insertionPoint)
140 morphNode(movedChild, newChild)
141 insertionPoint = movedChild.nextSibling
142 continue
143 }
144
145 // This performs the action of inserting a new node while handling situations where the node contains
146 // elements with persistent IDs and possible state info we can still preserve by moving in and then morphing
147 if (ctxIdMap.has(newChild)) {
148 // node has children with IDs with possible state so create a dummy elt of same type and apply full morph algorithm
149 const newEmptyChild = document.createElement((newChild as Element).tagName)
150 oldParent.insertBefore(newEmptyChild, insertionPoint)
151 morphNode(newEmptyChild, newChild)
152 insertionPoint = newEmptyChild.nextSibling
153 } else {
154 // optimization: no id state to preserve so we can just insert a clone of the newChild and its descendants
155 const newClonedChild = document.importNode(newChild, true) // importNode to not mutate newParent
156 oldParent.insertBefore(newClonedChild, insertionPoint)
157 insertionPoint = newClonedChild.nextSibling
158 }
159 }
160
161 // remove any remaining old nodes that didn't match up with new content
162 while (insertionPoint && insertionPoint !== endPoint) {
163 const tempNode = insertionPoint
164 insertionPoint = insertionPoint.nextSibling
165 removeNode(tempNode)
166 }
167}
168
169// Scans forward from the startPoint to the endPoint looking for a match for the node.
170// It looks for an id set match first, then a soft match.
171// We abort soft matching if we find two future soft matches, to reduce churn.
172const findBestMatch = (node: Node, startPoint: Node | null, endPoint: Node | null): Node | null => {
173 let bestMatch: Node | null | undefined = null
174 let nextSibling = node.nextSibling
175 let siblingSoftMatchCount = 0
176 let displaceMatchCount = 0
177
178 // Max ID matches we are willing to displace in our search
179 const nodeMatchCount = ctxIdMap.get(node)?.size || 0
180
181 let cursor = startPoint
182 while (cursor && cursor !== endPoint) {
183 // soft matching is a prerequisite for id set matching
184 if (isSoftMatch(cursor, node)) {
185 let isIdSetMatch = false
186 const oldSet = ctxIdMap.get(cursor)
187 const newSet = ctxIdMap.get(node)
188
189 if (newSet && oldSet) {
190 for (const id of oldSet) {
191 // a potential match is an id in the new and old nodes that
192 // has not already been merged into the DOM
193 // But the newNode content we call this on has not been
194 // merged yet and we don't allow duplicate IDs so it is simple
195 if (newSet.has(id)) {
196 isIdSetMatch = true
197 break
198 }
199 }
200 }
201
202 if (isIdSetMatch) {
203 return cursor // found an id set match, we're done!
204 }
205
206 // we haven’t yet saved a soft match fallback
207 // the current soft match will hard match something else in the future, leave it
208 if (!bestMatch && !ctxIdMap.has(cursor)) {
209 // optimization: if node can't id set match, we can just return the soft match immediately
210 if (!nodeMatchCount) {
211 return cursor
212 }
213 // save this as the fallback if we get through the loop without finding a hard match
214 bestMatch = cursor
215 }
216 }
217
218 // check for IDs we may be displaced when matching
219 displaceMatchCount += ctxIdMap.get(cursor)?.size || 0
220 if (displaceMatchCount > nodeMatchCount) {
221 // if we are going to displace more IDs than the node contains then
222 // we do not have a good candidate for an ID match, so return
223 break
224 }
225
226 if (bestMatch === null && nextSibling && isSoftMatch(cursor, nextSibling)) {
227 // The next new node has a soft match with this node, so
228 // increment the count of future soft matches
229 siblingSoftMatchCount++
230 nextSibling = nextSibling.nextSibling
231
232 // If there are two future soft matches, block soft matching for this node to allow
233 // future siblings to soft match. This is to reduce churn in the DOM when an element
234 // is prepended.
235 if (siblingSoftMatchCount >= 2) {
236 bestMatch = undefined
237 }
238 }
239
240 cursor = cursor.nextSibling
241 }
242
243 return bestMatch || null
244}
245
246// ok to cast: if one is not element, `id` and `tagName` will be null and we'll just compare that.
247const isSoftMatch = (oldNode: Node, newNode: Node): boolean =>
248 oldNode.nodeType === newNode.nodeType &&
249 (oldNode as Element).tagName === (newNode as Element).tagName &&
250 // If oldElt has an `id` with possible state and it doesn’t match newElt.id then avoid morphing.
251 // We'll still match an anonymous node with an IDed newElt, though, because if it got this far,
252 // its not persistent, and new nodes can't have any hidden state.
253 (!(oldNode as Element).id || (oldNode as Element).id === (newNode as Element).id)
254
255// Gets rid of an unwanted DOM node; strategy depends on nature of its reuse:
256// - Persistent nodes will be moved to the pantry for later reuse
257// - Other nodes will have their hooks called, and then are removed
258const removeNode = (node: Node): void => {
259 // are we going to id set match this later?
260 ctxIdMap.has(node)
261 ? // skip callbacks and move to pantry
262 moveBefore(ctxPantry, node, null)
263 : // remove for realsies
264 node.parentNode?.removeChild(node)
265}
266
267// Moves an element before another element within the same parent.
268// Uses the proposed `moveBefore` API if available (and working), otherwise falls back to `insertBefore`.
269// This is essentially a forward-compat wrapper.
270const moveBefore: (parentNode: Node, node: Node, after: Node | null) => void =
271 // @ts-expect-error
272 removeNode.call.bind(ctxPantry.moveBefore ?? ctxPantry.insertBefore)
273
274const aliasedPreserveAttr = "preserve-attr"
275
276// syncs the oldNode to the newNode, copying over all attributes and
277// inner element state from the newNode to the oldNode
278const morphNode = (
279 oldNode: Node, // root node to merge content into
280 newNode: Node, // new content to merge
281): Node => {
282 const type = newNode.nodeType
283
284 // if is an element type, sync the attributes from the
285 // new node into the new node
286 if (type === 1 /* element type */) {
287 const oldElt = oldNode as Element
288 const newElt = newNode as Element
289 if (oldElt.hasAttribute(aliasedIgnoreMorph) && newElt.hasAttribute(aliasedIgnoreMorph)) {
290 return oldNode
291 }
292
293 // many bothans died to bring us this information:
294 // https://github.com/patrick-steele-idem/morphdom/blob/master/src/specialElHandlers.js
295 // https://github.com/choojs/nanomorph/blob/master/lib/morph.js#L113
296 if (oldElt instanceof HTMLInputElement && newElt instanceof HTMLInputElement && newElt.type !== "file") {
297 // https://github.com/bigskysoftware/idiomorph/issues/27
298 // | old input value | new input value | behaviour |
299 // | --------------- | ---------------- | -------------------------------------- |
300 // | `null` | `null` | preserve old input value |
301 // | some value | the same value | preserve old input value |
302 // | some value | `null` | set old input value to `""` |
303 // | `null` | some value | set old input value to new input value |
304 // | some value | some other value | set old input value to new input value |
305 if (newElt.getAttribute("value") !== oldElt.getAttribute("value")) {
306 oldElt.value = newElt.getAttribute("value") ?? ""
307 }
308 } else if (oldElt instanceof HTMLTextAreaElement && newElt instanceof HTMLTextAreaElement) {
309 if (newElt.value !== oldElt.value) {
310 oldElt.value = newElt.value
311 }
312 if (oldElt.firstChild && oldElt.firstChild.nodeValue !== newElt.value) {
313 oldElt.firstChild.nodeValue = newElt.value
314 }
315 }
316
317 const preserveAttrs = ((newNode as HTMLElement).getAttribute(aliasedPreserveAttr) ?? "").split(" ")
318
319 for (const { name, value } of newElt.attributes) {
320 if (oldElt.getAttribute(name) !== value && !preserveAttrs.includes(name)) {
321 oldElt.setAttribute(name, value)
322 }
323 }
324
325 for (let i = oldElt.attributes.length - 1; i >= 0; i--) {
326 const { name } = oldElt.attributes[i]!
327 if (!newElt.hasAttribute(name) && !preserveAttrs.includes(name)) {
328 oldElt.removeAttribute(name)
329 }
330 }
331
332 if (!oldElt.isEqualNode(newElt)) {
333 morphChildren(oldElt, newElt)
334 }
335 }
336
337 if (type === 8 /* comment */ || type === 3 /* text */) {
338 if (oldNode.nodeValue !== newNode.nodeValue) {
339 oldNode.nodeValue = newNode.nodeValue
340 }
341 }
342
343 return oldNode
344}
345
346// A bottom-up algorithm that populates a map of Element -> IdSet.
347// The ID set for a given element is the set of all IDs contained within its subtree.
348// As an optimization, we filter these IDs through the given list of persistent IDs,
349// because we don't need to bother considering IDed elements that won't be in the new content.
350const populateIdMapWithTree = (root: Element | ShadowRoot | null, elements: Iterable<Element>): void => {
351 for (const elt of elements) {
352 if (ctxPersistentIds.has(elt.id)) {
353 let current: Element | null = elt
354 // walk up the parent hierarchy of that element, adding the ID of element to the parent's ID set
355 while (current && current !== root) {
356 let idSet = ctxIdMap.get(current)
357 // if the ID set doesn’t exist, create it and insert it in the map
358 if (!idSet) {
359 idSet = new Set()
360 ctxIdMap.set(current, idSet)
361 }
362 idSet.add(elt.id)
363 current = current.parentElement
364 }
365 }
366 }
367}