/* global define */
(function () {
'use strict';
/**
* @module bff/patch-dom
*/
function moduleFactory() {
function makeLevMat(xSize, ySize) {
var i, levMat = new Array(xSize + 1);
for (i = 0; i <= xSize; ++i) {
levMat[i] = new Array(ySize + 1);
levMat[i][0] = i;
}
for (i = 0; i <= ySize; ++i) {
levMat[0][i] = i;
}
return levMat;
}
var preallocLevMatSizeX = 63;
var preallocLevMatSizeY = 63;
var preallocLevMat = makeLevMat(preallocLevMatSizeX, preallocLevMatSizeY);
function areProbablyTheSame(target, source) {
if (!source) { return false; }
return target.nodeName === source.nodeName &&
((target.attributes && target.getAttribute('data-id')) ===
(source.attributes && source.getAttribute('data-id')));
}
function namedNodeMapToObject(namedNodeMap) {
var obj = {};
for (var i = 0, n = namedNodeMap.length; i < n; ++i) {
var node = namedNodeMap[i];
obj[node.name] = node.value;
}
return obj;
}
function patchElementNode(target, source) {
// Ref: http://quirksmode.org/dom/core/#attributes
var targetAttrObj = namedNodeMapToObject(target.attributes);
var sourceAttrArr = source.attributes;
var i, n, sourceAttr, targetAttr, attrName;
// Special cases
if (target.nodeName === 'INPUT') { target.value = source.value || ''; }
if (source.checked !== undefined) { target.checked = source.checked; }
if (source.selected !== undefined) { target.selected = source.selected; }
for (i = 0, n = sourceAttrArr.length; i < n; ++i) {
sourceAttr = sourceAttrArr[i];
attrName = sourceAttr.name;
targetAttr = targetAttrObj[attrName];
delete targetAttrObj[sourceAttr.name];
if (targetAttr && targetAttr.value === sourceAttr.value) { continue; }
target.setAttribute(attrName, sourceAttr.value);
}
for (attrName in targetAttrObj) {
target.removeAttribute(attrName);
}
}
function patchTextNode(target, source) {
var sourceValue = source.nodeValue;
if (target.nodeValue === sourceValue) { return; }
target.nodeValue = sourceValue;
}
function patchNode(target, source) {
switch (target.nodeType) {
case Node.ELEMENT_NODE: patchElementNode(target, source); break;
case Node.TEXT_NODE: patchTextNode(target, source); break;
}
}
function shouldIgnoreNode(node) {
return !!node.hasAttribute && node.hasAttribute('patch-ignore');
}
function patchRecursive(target, source, ignoreSubtreeOf) {
var targetParent = target.parentNode;
var childrenToPatch = [];
// Patch the current node
if (areProbablyTheSame(target, source)) {
patchNode(target, source);
} else {
if (source) {
targetParent.replaceChild(source, target);
} else {
targetParent.removeChild(target);
}
return;
}
if (ignoreSubtreeOf && Array.prototype.indexOf.call(ignoreSubtreeOf, target) !== -1) { return; }
// Diff subtree using Levenshtein distance algorithm
var targetChildren = target.childNodes;
var sourceChildren = source.childNodes;
var i, n, targetPos, sourcePos, targetChild, sourceChild;
var nTargetChildren = targetChildren.length;
var nSourceChildren = sourceChildren.length;
var nLeadingSameTypeChildren = 0;
var nIgnoredTargetChildren = 0;
var nTargetChildrenToIgnore = 0;
var allChildrenMatchSoFar = true;
for (i = 0; i < nTargetChildren; ++i) {
if (shouldIgnoreNode(targetChildren[i])) {
nTargetChildrenToIgnore++;
} else if (allChildrenMatchSoFar) {
if (areProbablyTheSame(targetChildren[i + nTargetChildrenToIgnore], sourceChildren[i])) {
childrenToPatch.push(targetChildren[i + nTargetChildrenToIgnore]);
childrenToPatch.push(sourceChildren[i]);
nLeadingSameTypeChildren++;
} else {
allChildrenMatchSoFar = false;
}
}
}
if (nTargetChildren - nTargetChildrenToIgnore === 0 && nSourceChildren === 0) { return; }
var levMatSizeX = nTargetChildren - nLeadingSameTypeChildren;
var levMatSizeY = nSourceChildren - nLeadingSameTypeChildren;
var levMat;
if (preallocLevMatSizeX < levMatSizeX || preallocLevMatSizeY < levMatSizeY) {
// The preallocated matrix is too small.
if (preallocLevMatSizeX <= levMatSizeX && preallocLevMatSizeY <= levMatSizeY) {
// The needed matrix is bigger or equal to the preallocated one i all dimensions, so let's grow the
// preallocated one.
preallocLevMatSizeX = levMatSizeX;
preallocLevMatSizeY = levMatSizeY;
preallocLevMat = makeLevMat(preallocLevMatSizeX, preallocLevMatSizeY);
levMat = preallocLevMat;
} else {
// The needed matrix is larger than the preallocated one in some, but not all dimensions. This
// should be quite an edge case, so just use a temporary matrix for this operation.
levMat = makeLevMat(levMatSizeX, levMatSizeY);
}
} else {
// The needed matrix fits inside the preallocated one, so just use that one. This should be the most
// common case.
levMat = preallocLevMat;
}
for (targetPos = 1; targetPos + nIgnoredTargetChildren <= nTargetChildren - nLeadingSameTypeChildren; targetPos++) {
targetChild = targetChildren[targetPos + nIgnoredTargetChildren + nLeadingSameTypeChildren - 1];
if (shouldIgnoreNode(targetChild)) {
nIgnoredTargetChildren++;
targetPos--;
continue;
}
for (sourcePos = 1; sourcePos <= nSourceChildren - nLeadingSameTypeChildren; ++sourcePos) {
if (areProbablyTheSame(targetChild, sourceChildren[sourcePos + nLeadingSameTypeChildren - 1])) {
levMat[targetPos][sourcePos] = levMat[targetPos - 1][sourcePos - 1];
} else {
levMat[targetPos][sourcePos] = 1 + Math.min(
levMat[targetPos - 1][sourcePos - 1],
levMat[targetPos][sourcePos - 1],
levMat[targetPos - 1][sourcePos]);
}
}
}
targetPos = nTargetChildren - nLeadingSameTypeChildren - nTargetChildrenToIgnore;
sourcePos = nSourceChildren - nLeadingSameTypeChildren;
while (targetPos > 0 || sourcePos > 0) {
targetChild = targetChildren[targetPos + nLeadingSameTypeChildren + nTargetChildrenToIgnore - 1];
if (targetChild && shouldIgnoreNode(targetChild)) {
nTargetChildrenToIgnore--;
continue;
}
var substitution = targetPos > 0 && sourcePos > 0 ? levMat[targetPos - 1][sourcePos - 1] : Infinity;
var insertion = sourcePos > 0 ? levMat[targetPos][sourcePos - 1] : Infinity;
var deletion = targetPos > 0 ? levMat[targetPos - 1][sourcePos] : Infinity;
sourceChild = sourceChildren[sourcePos + nLeadingSameTypeChildren - 1];
if (substitution <= insertion && substitution <= deletion) {
if (substitution < levMat[targetPos][sourcePos]) {
// Substitute
target.replaceChild(sourceChild, targetChild);
} else {
// Add to patch list
childrenToPatch.push(targetChild);
childrenToPatch.push(sourceChild);
}
targetPos--;
sourcePos--;
} else if (insertion <= deletion) {
// Insert
target.insertBefore(sourceChild, targetChild ? targetChild.nextSibling : null);
sourcePos--;
} else {
// Delete
target.removeChild(targetChild);
targetPos--;
}
}
for (i = 0, n = childrenToPatch.length; i < n; i += 2) {
patchRecursive(childrenToPatch[i], childrenToPatch[i + 1], ignoreSubtreeOf);
}
}
/**
* Patches the target element and its child elements such that it will be identical to the source element and its child structure. It achieves this by recursively _patching_, _removing_ or _adding_ elements in the target element hierarchy. The overall logic of the algorithm goes as follows:
* * If the target and source elements have differing node type types (e.g. a `<div>` and a `<span>` tag) the target element is replaced by the source element.
* * Otherwise, if the target and source elements are of the same type (e.g. two `<div>` tags), the attributes of the target element will be replaced by those of the target element. Then the target and source elements' children lists are compared using a version of the Levenshtein algorithm. This results in the children of the target element being either patched (by calling `patchDom` recursively) or removed. Child elements only present in the source child list will also be added to the target child list at their respective positions.
*
* If any encountered target elements has a `patch-ignore` attribute, that node and its children will not be patched.
*
* @alias module:bff/patch-dom
* @arg {HTMLElement} target - The element (hierarchy) to be patched. Will be identical to the source element (hierarchy) after the function call completes.
* @arg {HTMLElement} source - The element (hierarchy) that the target (hierarchy) will be transformed into.
* @arg {Object} [options] - Options that will be recursively passed down to all patchDom calls. Currently only one option is implemented:
* * _ignoreSubtreeOf_: A CSS selector string that identifies any elements, whose subtrees will not be patched.
*/
function patchDom(target, source, options) {
options = options || {};
if (RUNTIME_CHECKS) {
if (!(target instanceof HTMLElement)) {
throw '"target" argument must be an HTMLElement';
} else if (!(source instanceof HTMLElement)) {
throw '"source" argument must be an HTMLElement';
} else if (arguments.length > 2 && typeof options !== 'object') {
throw '"options" argument must be an object';
} else if ('ignoreSubtreeOf' in options && typeof options.ignoreSubtreeOf !== 'string') {
throw 'ignoreSubtreeOf option must be a valid CSS selector string';
} else if (target === source) {
throw 'Target and source are the same, which makes no sense!';
}
}
var ignoreSubtreeOf = options.ignoreSubtreeOf && target.querySelectorAll(options.ignoreSubtreeOf);
patchRecursive(target, source, ignoreSubtreeOf);
return target;
}
return patchDom;
}
// Expose, based on environment
if (typeof define === 'function' && define.amd) { // AMD
define(moduleFactory);
} else if (typeof exports === 'object') { // Node, CommonJS-like
module.exports = moduleFactory();
} else { // Browser globals
var bff = window.bff = window.bff || {};
bff.patchDom = moduleFactory();
}
}());