yippee.fun
Precise DOM morphing
morphing
typescript
dom
joel.drapper.me
1const SupportsMoveBefore = "moveBefore" in Element.prototype
2const ParentNodeTypes = new Set([1, 9, 11])
3
4type IdSet = Set<string>
5type IdMap = WeakMap<Node, IdSet>
6
7declare const brand: unique symbol
8type Branded<T, B extends string> = T & { [brand]: B }
9
10type PairOfNodes<N extends Node> = [N, N]
11type PairOfMatchingElements<E extends Element> = Branded<PairOfNodes<E>, "MatchingElementPair">
12
13interface Options {
14 preserveModified?: boolean
15 beforeNodeVisited?: (fromNode: Node, toNode: Node) => boolean
16 afterNodeVisited?: (fromNode: Node, toNode: Node) => void
17 beforeNodeAdded?: (parent: ParentNode, node: Node, insertionPoint: ChildNode | null) => boolean
18 afterNodeAdded?: (node: Node) => void
19 beforeNodeRemoved?: (node: Node) => boolean
20 afterNodeRemoved?: (node: Node) => void
21 beforeAttributeUpdated?: (element: Element, attributeName: string, newValue: string | null) => boolean
22 afterAttributeUpdated?: (element: Element, attributeName: string, previousValue: string | null) => void
23 beforeChildrenVisited?: (parent: ParentNode) => boolean
24 afterChildrenVisited?: (parent: ParentNode) => void
25}
26
27type NodeWithMoveBefore = ParentNode & {
28 moveBefore: (node: ChildNode, before: ChildNode | null) => void
29}
30
31export function morph(from: ChildNode, to: ChildNode | NodeListOf<ChildNode> | string, options: Options = {}): void {
32 if (typeof to === "string") to = parseString(to).childNodes
33
34 if (isParentNode(from)) flagDirtyInputs(from)
35
36 new Morph(options).morph(from, to)
37}
38
39export function morphInner(from: ChildNode, to: ChildNode | string, options: Options = {}): void {
40 if (typeof to === "string") {
41 const fragment = parseString(to)
42
43 if (fragment.firstChild && fragment.childNodes.length === 1 && isElement(fragment.firstChild)) {
44 to = fragment.firstChild
45 } else {
46 throw new Error("[Morphlex] The string was not a valid HTML element.")
47 }
48 }
49
50 const pair: PairOfNodes<Node> = [from, to]
51 if (isElementPair(pair) && isMatchingElementPair(pair)) {
52 if (isParentNode(from)) flagDirtyInputs(from)
53 new Morph(options).visitChildNodes(pair)
54 } else {
55 throw new Error("[Morphlex] You can only do an inner morph with matching elements.")
56 }
57}
58
59function flagDirtyInputs(node: ParentNode): void {
60 for (const element of node.querySelectorAll("input")) {
61 if (element.value !== element.defaultValue) {
62 element.setAttribute("morphlex-dirty", "")
63 }
64
65 if (element.checked !== element.defaultChecked) {
66 element.setAttribute("morphlex-dirty", "")
67 }
68 }
69
70 for (const element of node.querySelectorAll("option")) {
71 if (element.selected !== element.defaultSelected) {
72 element.setAttribute("morphlex-dirty", "")
73 }
74 }
75
76 for (const element of node.querySelectorAll("textarea")) {
77 if (element.value !== element.defaultValue) {
78 element.setAttribute("morphlex-dirty", "")
79 }
80 }
81}
82
83function parseString(string: string): DocumentFragment {
84 const template = document.createElement("template")
85 template.innerHTML = string.trim()
86
87 return template.content
88}
89
90function moveBefore(parent: ParentNode, node: ChildNode, insertionPoint: ChildNode | null): void {
91 if (node === insertionPoint) return
92 if (node.parentNode === parent) {
93 if (node.nextSibling === insertionPoint) return
94 if (supportsMoveBefore(parent)) {
95 parent.moveBefore(node, insertionPoint)
96 return
97 }
98 }
99
100 parent.insertBefore(node, insertionPoint)
101}
102
103class Morph {
104 private readonly idMap: IdMap = new WeakMap()
105 private readonly options: Options
106
107 constructor(options: Options = {}) {
108 this.options = options
109 }
110
111 // Find longest increasing subsequence to minimize moves during reordering
112 // Returns the indices in the sequence that form the LIS
113 private longestIncreasingSubsequence(sequence: Array<number>): Array<number> {
114 const n = sequence.length
115 if (n === 0) return []
116
117 // smallestEnding[i] = smallest ending value of any increasing subsequence of length i+1
118 const smallestEnding: Array<number> = []
119 // indices[i] = index in sequence where smallestEnding[i] occurs
120 const indices: Array<number> = []
121 // prev[i] = previous index in the LIS ending at sequence[i]
122 const prev: Array<number> = Array.from({ length: n }, () => -1)
123
124 // Build the LIS by processing each value
125 for (let i = 0; i < n; i++) {
126 const val = sequence[i]!
127 if (val === -1) continue // Skip new nodes (not in original sequence)
128
129 // Binary search: find where this value fits in smallestEnding
130 let left = 0
131 let right = smallestEnding.length
132
133 while (left < right) {
134 const mid = Math.floor((left + right) / 2)
135 if (smallestEnding[mid]! < val) left = mid + 1
136 else right = mid
137 }
138
139 // Link this element to the previous one in the subsequence
140 if (left > 0) prev[i] = indices[left - 1]!
141
142 // Either extend the sequence or update an existing position
143 if (left === smallestEnding.length) {
144 // Extend: this value is larger than all previous endings
145 smallestEnding.push(val)
146 indices.push(i)
147 } else {
148 // Update: found a better (smaller) ending for this length
149 smallestEnding[left] = val
150 indices[left] = i
151 }
152 }
153
154 // Reconstruct the actual indices that form the LIS
155 const result: Array<number> = []
156 if (indices.length === 0) return result
157
158 // Walk backwards through prev links to build the LIS
159 let curr: number | undefined = indices[indices.length - 1]
160 while (curr !== undefined && curr !== -1) {
161 result.unshift(curr)
162 curr = prev[curr]
163 }
164
165 return result
166 }
167
168 morph(from: ChildNode, to: ChildNode | NodeListOf<ChildNode>): void {
169 if (isParentNode(from)) {
170 this.mapIdSets(from)
171 }
172
173 if (to instanceof NodeList) {
174 this.mapIdSetsForEach(to)
175 this.morphOneToMany(from, to)
176 } else if (isParentNode(to)) {
177 this.mapIdSets(to)
178 this.morphOneToOne(from, to)
179 }
180 }
181
182 private morphOneToMany(from: ChildNode, to: NodeListOf<ChildNode>): void {
183 const length = to.length
184
185 if (length === 0) {
186 this.removeNode(from)
187 } else if (length === 1) {
188 this.morphOneToOne(from, to[0]!)
189 } else if (length > 1) {
190 const newNodes = Array.from(to)
191 this.morphOneToOne(from, newNodes.shift()!)
192 const insertionPoint = from.nextSibling
193 const parent = from.parentNode || document
194
195 for (const newNode of newNodes) {
196 if (this.options.beforeNodeAdded?.(parent, newNode, insertionPoint) ?? true) {
197 moveBefore(parent, newNode, insertionPoint)
198 this.options.afterNodeAdded?.(newNode)
199 }
200 }
201 }
202 }
203
204 private morphOneToOne(from: ChildNode, to: ChildNode): void {
205 // Fast path: if nodes are exactly the same object, skip morphing
206 if (from === to) return
207 if (from.isEqualNode?.(to)) return
208
209 if (!(this.options.beforeNodeVisited?.(from, to) ?? true)) return
210
211 const pair: PairOfNodes<ChildNode> = [from, to]
212
213 if (isElementPair(pair)) {
214 if (isMatchingElementPair(pair)) {
215 this.morphMatchingElements(pair)
216 } else {
217 this.morphNonMatchingElements(pair)
218 }
219 } else {
220 this.morphOtherNode(pair)
221 }
222
223 this.options.afterNodeVisited?.(from, to)
224 }
225
226 private morphMatchingElements(pair: PairOfMatchingElements<Element>): void {
227 const [from, to] = pair
228
229 if (from.hasAttributes() || to.hasAttributes()) {
230 this.visitAttributes(pair)
231 }
232
233 if (isTextAreaElement(from) && isTextAreaElement(to)) {
234 this.visitTextArea(pair as PairOfMatchingElements<HTMLTextAreaElement>)
235 } else if (from.hasChildNodes() || to.hasChildNodes()) {
236 this.visitChildNodes(pair)
237 }
238 }
239
240 private morphNonMatchingElements([from, to]: PairOfNodes<Element>): void {
241 this.replaceNode(from, to)
242 }
243
244 private morphOtherNode([from, to]: PairOfNodes<ChildNode>): void {
245 if (from.nodeType === to.nodeType && from.nodeValue !== null && to.nodeValue !== null) {
246 from.nodeValue = to.nodeValue
247 } else {
248 this.replaceNode(from, to)
249 }
250 }
251
252 private visitAttributes([from, to]: PairOfMatchingElements<Element>): void {
253 if (from.hasAttribute("morphlex-dirty")) {
254 from.removeAttribute("morphlex-dirty")
255 }
256
257 // First pass: update/add attributes from reference (iterate forwards)
258 for (const { name, value } of to.attributes) {
259 if (name === "value") {
260 if (isInputElement(from) && from.value !== value) {
261 if (!this.options.preserveModified || from.value === from.defaultValue) {
262 from.value = value
263 }
264 }
265 }
266
267 if (name === "selected") {
268 if (isOptionElement(from) && !from.selected) {
269 if (!this.options.preserveModified || from.selected === from.defaultSelected) {
270 from.selected = true
271 }
272 }
273 }
274
275 if (name === "checked") {
276 if (isInputElement(from) && !from.checked) {
277 if (!this.options.preserveModified || from.checked === from.defaultChecked) {
278 from.checked = true
279 }
280 }
281 }
282
283 const oldValue = from.getAttribute(name)
284
285 if (oldValue !== value && (this.options.beforeAttributeUpdated?.(from, name, value) ?? true)) {
286 from.setAttribute(name, value)
287 this.options.afterAttributeUpdated?.(from, name, oldValue)
288 }
289 }
290
291 const fromAttrs = from.attributes
292
293 // Second pass: remove excess attributes (iterate backwards for efficiency)
294 for (let i = fromAttrs.length - 1; i >= 0; i--) {
295 const { name, value } = fromAttrs[i]!
296
297 if (!to.hasAttribute(name)) {
298 if (name === "selected") {
299 if (isOptionElement(from) && from.selected) {
300 if (!this.options.preserveModified || from.selected === from.defaultSelected) {
301 from.selected = false
302 }
303 }
304 }
305
306 if (name === "checked") {
307 if (isInputElement(from) && from.checked) {
308 if (!this.options.preserveModified || from.checked === from.defaultChecked) {
309 from.checked = false
310 }
311 }
312 }
313
314 if (this.options.beforeAttributeUpdated?.(from, name, null) ?? true) {
315 from.removeAttribute(name)
316 this.options.afterAttributeUpdated?.(from, name, value)
317 }
318 }
319 }
320 }
321
322 private visitTextArea([from, to]: PairOfMatchingElements<HTMLTextAreaElement>): void {
323 const newTextContent = to.textContent || ""
324 const isModified = from.value !== from.defaultValue
325
326 // Update text content (which updates defaultValue)
327 if (from.textContent !== newTextContent) {
328 from.textContent = newTextContent
329 }
330
331 if (this.options.preserveModified && isModified) return
332
333 from.value = from.defaultValue
334 }
335
336 visitChildNodes([from, to]: PairOfMatchingElements<Element>): void {
337 if (!(this.options.beforeChildrenVisited?.(from) ?? true)) return
338 const parent = from
339
340 const fromChildNodes = from.childNodes
341 const toChildNodes = Array.from(to.childNodes)
342
343 const candidateNodes: Set<ChildNode> = new Set()
344 const candidateElements: Set<Element> = new Set()
345
346 const matches: Array<ChildNode | null> = Array.from({ length: toChildNodes.length }, () => null)
347
348 for (const candidate of fromChildNodes) {
349 if (isElement(candidate)) candidateElements.add(candidate)
350 else candidateNodes.add(candidate)
351 }
352
353 // Match elements by isEqualNode
354 for (let i = 0; i < toChildNodes.length; i++) {
355 const element = toChildNodes[i]!
356 if (!isElement(element)) continue
357
358 for (const candidate of candidateElements) {
359 if (candidate.isEqualNode(element)) {
360 matches[i] = candidate
361 candidateElements.delete(candidate)
362 break
363 }
364 }
365 }
366
367 // Match by exact id
368 for (let i = 0; i < toChildNodes.length; i++) {
369 if (matches[i]) continue
370 const element = toChildNodes[i]!
371 if (!isElement(element)) continue
372
373 const id = element.id
374 if (id === "") continue
375
376 for (const candidate of candidateElements) {
377 if (element.localName === candidate.localName && id === candidate.id) {
378 matches[i] = candidate
379 candidateElements.delete(candidate)
380 break
381 }
382 }
383 }
384
385 // Match by idSet
386 for (let i = 0; i < toChildNodes.length; i++) {
387 if (matches[i]) continue
388 const element = toChildNodes[i]!
389 if (!isElement(element)) continue
390
391 const idSet = this.idMap.get(element)
392 if (!idSet) continue
393
394 candidateLoop: for (const candidate of candidateElements) {
395 if (isElement(candidate)) {
396 const candidateIdSet = this.idMap.get(candidate)
397 if (candidateIdSet) {
398 for (const id of idSet) {
399 if (candidateIdSet.has(id)) {
400 matches[i] = candidate
401 candidateElements.delete(candidate)
402 break candidateLoop
403 }
404 }
405 }
406 }
407 }
408 }
409
410 // Match by heuristics
411 for (let i = 0; i < toChildNodes.length; i++) {
412 if (matches[i]) continue
413 const element = toChildNodes[i]!
414 if (!isElement(element)) continue
415
416 const name = element.getAttribute("name")
417 const href = element.getAttribute("href")
418 const src = element.getAttribute("src")
419
420 for (const candidate of candidateElements) {
421 if (
422 isElement(candidate) &&
423 element.localName === candidate.localName &&
424 ((name !== "" && name === candidate.getAttribute("name")) ||
425 (href !== "" && href === candidate.getAttribute("href")) ||
426 (src !== "" && src === candidate.getAttribute("src")))
427 ) {
428 matches[i] = candidate
429 candidateElements.delete(candidate)
430 break
431 }
432 }
433 }
434
435 // Match by tagName
436 for (let i = 0; i < toChildNodes.length; i++) {
437 if (matches[i]) continue
438 const element = toChildNodes[i]!
439 if (!isElement(element)) continue
440
441 const localName = element.localName
442
443 for (const candidate of candidateElements) {
444 if (localName === candidate.localName) {
445 if (isInputElement(candidate) && isInputElement(element) && candidate.type !== element.type) {
446 // Treat inputs with different type as though they are different tags.
447 continue
448 }
449 matches[i] = candidate
450 candidateElements.delete(candidate)
451 break
452 }
453 }
454 }
455
456 // Match nodes by isEqualNode
457 for (let i = 0; i < toChildNodes.length; i++) {
458 if (matches[i]) continue
459 const node = toChildNodes[i]!
460 if (isElement(node)) continue
461
462 for (const candidate of candidateNodes) {
463 if (candidate.isEqualNode(node)) {
464 matches[i] = candidate
465 candidateNodes.delete(candidate)
466 break
467 }
468 }
469 }
470
471 // Match by nodeType
472 for (let i = 0; i < toChildNodes.length; i++) {
473 if (matches[i]) continue
474 const node = toChildNodes[i]!
475 if (isElement(node)) continue
476
477 const nodeType = node.nodeType
478
479 for (const candidate of candidateNodes) {
480 if (nodeType === candidate.nodeType) {
481 matches[i] = candidate
482 candidateNodes.delete(candidate)
483 break
484 }
485 }
486 }
487
488 // Build sequence of current indices for LIS calculation
489 const fromIndex = new Map<ChildNode, number>()
490 Array.from(fromChildNodes).forEach((node, i) => fromIndex.set(node, i))
491
492 const sequence: Array<number> = []
493 for (let i = 0; i < matches.length; i++) {
494 const match = matches[i]
495 if (match && fromIndex.has(match)) {
496 sequence.push(fromIndex.get(match)!)
497 } else {
498 sequence.push(-1) // New node, not in sequence
499 }
500 }
501
502 // Find LIS - these nodes don't need to move
503 const lisIndices = this.longestIncreasingSubsequence(sequence)
504 const shouldNotMove = new Set<number>()
505 for (const idx of lisIndices) {
506 shouldNotMove.add(sequence[idx]!)
507 }
508
509 // Process nodes in forward order to maintain proper positioning
510 let insertionPoint: ChildNode | null = parent.firstChild
511 for (let i = 0; i < toChildNodes.length; i++) {
512 const node = toChildNodes[i]!
513 const match = matches[i]
514 if (match) {
515 const matchIndex = fromIndex.get(match)!
516 // Only move if not in LIS
517 if (!shouldNotMove.has(matchIndex)) {
518 moveBefore(parent, match, insertionPoint)
519 }
520 this.morphOneToOne(match, node)
521 insertionPoint = match.nextSibling
522 // Skip over any nodes that will be removed to avoid unnecessary moves
523 while (
524 insertionPoint &&
525 (candidateNodes.has(insertionPoint) || (isElement(insertionPoint) && candidateElements.has(insertionPoint)))
526 ) {
527 insertionPoint = insertionPoint.nextSibling
528 }
529 } else {
530 if (this.options.beforeNodeAdded?.(parent, node, insertionPoint) ?? true) {
531 moveBefore(parent, node, insertionPoint)
532 this.options.afterNodeAdded?.(node)
533 insertionPoint = node.nextSibling
534 // Skip over any nodes that will be removed to avoid unnecessary moves
535 while (
536 insertionPoint &&
537 (candidateNodes.has(insertionPoint) || (isElement(insertionPoint) && candidateElements.has(insertionPoint)))
538 ) {
539 insertionPoint = insertionPoint.nextSibling
540 }
541 }
542 }
543 }
544
545 // Remove any remaining unmatched candidates
546 for (const candidate of candidateNodes) {
547 this.removeNode(candidate)
548 }
549
550 for (const candidate of candidateElements) {
551 this.removeNode(candidate)
552 }
553
554 this.options.afterChildrenVisited?.(from)
555 }
556
557 private replaceNode(node: ChildNode, newNode: ChildNode): void {
558 const parent = node.parentNode || document
559 const insertionPoint = node
560 if (this.options.beforeNodeAdded?.(parent, newNode, insertionPoint) ?? true) {
561 moveBefore(parent, newNode, insertionPoint)
562 this.options.afterNodeAdded?.(newNode)
563 this.removeNode(node)
564 }
565 }
566
567 private removeNode(node: ChildNode): void {
568 if (this.options.beforeNodeRemoved?.(node) ?? true) {
569 node.remove()
570 this.options.afterNodeRemoved?.(node)
571 }
572 }
573
574 private mapIdSetsForEach(nodeList: NodeList): void {
575 for (const childNode of nodeList) {
576 if (isParentNode(childNode)) {
577 this.mapIdSets(childNode)
578 }
579 }
580 }
581
582 // For each node with an ID, push that ID into the IdSet on the IdMap, for each of its parent elements.
583 private mapIdSets(node: ParentNode): void {
584 for (const elementWithId of node.querySelectorAll("[id]")) {
585 const id = elementWithId.id
586
587 if (id === "") continue
588
589 let currentElement: Element | null = elementWithId
590
591 while (currentElement) {
592 const idSet: IdSet | undefined = this.idMap.get(currentElement)
593 if (idSet) idSet.add(id)
594 else this.idMap.set(currentElement, new Set([id]))
595 if (currentElement === node) break
596 currentElement = currentElement.parentElement
597 }
598 }
599 }
600}
601
602function supportsMoveBefore(_node: ParentNode): _node is NodeWithMoveBefore {
603 return SupportsMoveBefore
604}
605
606function isMatchingElementPair(pair: PairOfNodes<Element>): pair is PairOfMatchingElements<Element> {
607 const [a, b] = pair
608 return a.localName === b.localName
609}
610
611function isElementPair(pair: PairOfNodes<Node>): pair is PairOfNodes<Element> {
612 const [a, b] = pair
613 return isElement(a) && isElement(b)
614}
615
616function isElement(node: Node): node is Element {
617 return node.nodeType === 1
618}
619
620function isInputElement(element: Element): element is HTMLInputElement {
621 return element.localName === "input"
622}
623
624function isOptionElement(element: Element): element is HTMLOptionElement {
625 return element.localName === "option"
626}
627
628function isTextAreaElement(element: Element): element is HTMLTextAreaElement {
629 return element.localName === "textarea"
630}
631
632function isParentNode(node: Node): node is ParentNode {
633 return ParentNodeTypes.has(node.nodeType)
634}