Skip to content

Instantly share code, notes, and snippets.

@blankhart
Last active April 19, 2020 03:14
Show Gist options
  • Save blankhart/a36b64cee6b3e398f32725ee447c14e1 to your computer and use it in GitHub Desktop.
Save blankhart/a36b64cee6b3e398f32725ee447c14e1 to your computer and use it in GitHub Desktop.
DOM node list diff and patch
/* Adapted from snabbdom/updateChildren - The MIT License - Simon Friis Vindum */
import { api } from 'sinuous';
export function map(items, expr) {
const { subscribe, root, cleanup } = api;
let parent = document.createDocumentFragment();
const beforeNode = parent.appendChild(document.createTextNode(''));
const afterNode = parent.appendChild(document.createTextNode(''));
const disposers = new Map();
function disposeAll() {
disposers.forEach(d => d());
disposers.clear();
}
function dispose(node) {
let disposer = disposers.get(node);
disposer && disposer();
disposers.delete(node);
}
const unsubscribe = subscribe(a => {
a = a || [];
const b = items() || [];
// When parent was a DocumentFragment, then items got appended to the DOM.
parent = afterNode.parentNode;
const childNodes = Array.from(parent.childNodes);
const beforeNodeIndex = childNodes.indexOf(beforeNode);
const afterNodeIndex = childNodes.indexOf(afterNode);
// Optimization
// const afterNodeIndex =
// childNodes.pop() === afterNode
// ? childNodes.length
// : EMPTY_ARR.indexOf.call(childNodes, afterNode);
const a_index = new Map();
const b_index = new Map();
let need_indices = false;
let start_i = 0;
let end_i = a.length - 1;
let start_j = 0;
let end_j = b.length - 1;
let start_a = a[start_i];
let end_a = a[end_i];
let start_b = b[start_j];
let end_b = b[end_j];
let old_start_j;
let new_start_i;
while (start_i <= end_i && start_j <= end_j) {
if (start_a == null) {
start_a = a[++start_i];
} else if (end_a == null) {
end_a = a[--end_i];
} else if (start_b == null) {
start_b = b[++start_j];
} else if (end_b == null) {
end_b = b[--end_j];
} else if (start_a === start_b) {
start_a = a[++start_i];
start_b = b[++start_j];
} else if (end_a === end_b) {
end_a = a[--end_i];
end_b = b[--end_j];
}
else if (start_a === end_b) {
parent.insertBefore(
getOriginalChild(start_i),
getOriginalChild(end_i).nextSibling || afterNode
);
start_a = a[++start_i];
end_b = b[--end_j];
} else if (end_a === start_b) {
parent.insertBefore(
getOriginalChild(end_i),
getOriginalChild(start_i) || afterNode
);
end_a = a[--end_i];
start_b = b[++start_j];
}
else {
// Lazily build maps here. They are relevant only if there has been
// a move, or a mid-list insertion or deletion and not if there
// has been an insertion at the end or deletion from the front.
if (need_indices === false) {
need_indices = true;
// Create a mapping from keys to their position in the old list
for (i = 0; i < a.length; i++) {
a_index.set(a[i], i);
}
// Create a mapping from keys to their position in the new list
for (i = 0; i < b.length; i++) {
b_index.set(b[i], i);
}
}
old_start_j = a_index.get(start_b);
new_start_i = b_index.get(start_a);
// Replacement
// If considered on its own (with no other fine-grained update method)
// this is still slower than virtual dom libraries in the general case
// because it doesn't recursively diff and patch the replaced node.
if (old_start_j === undefined && new_start_i === undefined) {
parent.replaceChild(
create(start_b, start_j), // new
getOriginalChild(start_i) // old
);
start_a = a[++start_i];
start_b = b[++start_j];
}
// Insertion
else if (old_start_j === undefined) {
parent.insertBefore(
create(start_b, start_j),
getOriginalChild(start_i) || afterNode
);
start_b = b[++start_j];
}
// Deletion
else if (new_start_i === undefined) {
dispose(
parent.removeChild(getOriginalChild(start_i))
);
start_a = a[++start_i];
}
// Move
else {
parent.insertBefore(
getOriginalChild(old_start_j),
getOriginalChild(start_i) || afterNode
);
a[old_start_j] = null;
start_b = b[++start_j];
}
}
}
if (start_i <= end_i || start_j <= end_j) {
if (start_i > end_i) { // old list exhausted; process new list additions
let fragment = document.createDocumentFragment();
for (start_j; start_j <= end_j; start_b = b[++start_j]) {
fragment.appendChild(create(start_b, start_j));
}
parent.insertBefore(fragment, getOriginalChild(start_i) || afterNode);
} else { // new list exhausted; process old list removals
for (start_i; start_i <= end_i; ++start_i) {
dispose(
parent.removeChild(getOriginalChild(start_i))
);
}
}
}
function getOriginalChild(index) {
const i = beforeNodeIndex + index + 1;
return i > beforeNodeIndex && i < afterNodeIndex && childNodes[i];
}
function create(item, i) {
return root(disposeFn => {
item = expr(item, i);
item = item instanceof Node ? item : document.createTextNode(item);
disposers.set(item, disposeFn);
return item;
});
}
return b.slice();
});
cleanup(unsubscribe);
cleanup(disposeAll);
return parent;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment