I've been working on a MutationObserver es5 shim and would appreciate some feedback on my technique for identifying changes between a node and its clone from earlier state. The reason I'm asking for this code review is that this function is likely not perfect (i.e. will have to be updated in the future for missed/incorrect cases) and was the most difficult snippet of code I've ever written. I would like to know if how I've written the code is intuitive/commented enough for fresh eyes and if you have any suggestions for a couple things.
Here's the pseudocode I wrote that my actual code is based on:
findChildMutations ($node, $oldnode, deep):
mutations = []
conflicts = []
iterate each $node.childNodes as $node and $oldnode.childNodes as $old:
if(sameNode($node, $old)):
if(deep):
check children of $node and $old
resolveConflicts()
else:
if($node not checked):
if($node not in $oldnode.childNodes):
add addedNode MutationRecord to mutations
else if($node at different index in $oldnode.childNodes)
add conflict
#*similarly for $old*
resolveConflicts()
return mutations
The goals of the function is to accurately be able to identify addedNodes or removedNodes in the (optionally deep) childNodes of an element. The function should also notice when there is a change in order of nodes. Finally the function should of course be efficient as it will be running more than 20 times a second.
Implementation 1
This is the best I had gotten it with the node.cloneNode implementation (some room for optimization by checking if both $kids and $oldkids are empty and avoid entering resolver see imp #2)
/*subtree and childlist helpers*/
var has = Object.hasOwnProperty;
//Assigns a unique id to each node to be watched in order to be able to compare cloned nodes
//TODO find a cleaner way eg some hash represnetnation
var counter = 0;
var getId = function($ele) {
var id = $ele.nodeType === 3 ? $ele.nodeValue ://text node id is the text content
$ele.id || $ele.getAttribute("mut-id") || ++counter;
if(id === counter) {
$ele.setAttribute("mut-id", id);
}
return id;
};
var sameNode = function(node1, node2) {
return node1 && node2 && getId(node1) === getId(node2);
};
var findIndex = function(set, node, from) {
from = ~~from;
for(var i = from,l=set.length; i<l; i++) {
if(sameNode(node, set[i])) return i;
}
return -1;
};
//set the ids for all of an elements children
var $id_kids = function(ele, deep) {
if(ele.nodeType !== 3) {
foreach.call(ele.children, function(node) {//only iterate elements not text nodes
getId(node);
if(deep) $id_kids(node, deep);
});
}
return ele;
};
//findChildMutations: array of mutations so far, element, element clone, bool => array of mutations
// dfs comparision search of two nodes
// perf and function tests: http://jsbin.com/uhoVibU/4
var findChildMutations = function(target, oldstate, deep) {
var mutations = [];
var add = function(node) {
mutations.push(new MutationRecord({
type: "childList",
target: node.parentElement,
addedNodes: [node]
}));
if(deep) $id_kids(node, deep);//ensure children of added ele have ids
};
var rem = function(node) {
mutations.push(new MutationRecord({
type: "childList",
target: deep ? node.parentElement : target,//so target will appear correct on childList - more complicated on subtree
removedNodes: [node]
}));
};
var findMut = function(node, oldnode) {
var $kids = node.childNodes;
var $oldkids = oldnode.childNodes;
var klen = $kids.length;
var olen = $oldkids.length;
//id to i and j search hash to prevent double checking an element
var id;
var map = {};
//array of potention conflict hashes
var conflicts = [];
//offsets
//var offset_add = 0;//nodes added since last resolve //we dont have to check added as these are handled before remove
var offset_rem = 0;//nodes removed since last resolve
/*
* There is no gaurentee that the same node will be returned for both added and removed nodes
* if the position has been shuffled
*/
var resolver = function() {
var counter = 0;//prevents same conflict being resolved twice
var conflict;
for (var i = 0, l = conflicts.length-1; i <= l; i++) {
conflict = conflicts[i];
//attempt to determine if there was node rearrangement... won't gaurentee all matches
//also handles case where added/removed nodes cause nodes to be identified as conflicts
if(counter < l && Math.abs(conflict.i - (conflict.j + offset_rem)) >= l) {
add($kids[conflict.i]);//rearrangment ie removed then readded
rem($kids[conflict.i]);
counter++;
} else if(deep) {//conflicts resolved - check deep
findMut($kids[conflict.i], $oldkids[conflict.j]);
}
}
offset_rem = conflicts.length = 0;
};
//iterate over both old and current child nodes at the same time
for(var i = 0, j = 0, p; i < klen || j < olen; ) {
if(sameNode($kids[i], $oldkids[j])) {//simple expected case
if(deep) {//recurse
findMut($kids[i], $oldkids[j]);
}
//resolve conflicts
resolver();
i++;
j++;
} else {//lookahead until they are the same again or the end of children
if(i < klen) {
id = getId($kids[i]);
//check id is in the location map otherwise do a indexOf search
if(!has.call(map, id)) {//not already found
if((p = findIndex($oldkids, $kids[i], j)) === -1) {
add($kids[i]);
} else {
conflicts.push(map[id] = {//bit dirty
i: i,
j: p
});
}
}
i++;
}
if(j < olen) {
id = getId($oldkids[j]);
if(!has.call(map, id)) {
if((p = findIndex($kids, $oldkids[j], i)) === -1) {
rem($oldkids[j]);
offset_rem++;
} else {
conflicts.push(map[id] = {
i: p,
j: j
});
}
}
j++;
}
}
}
resolver();
};
findMut(target, oldstate);
return mutations;
};
Usage
//node is a html element
//deep is a boolean
findChildMutations(node, node.cloneNode(true), deep)
Implementation 2
Using a custom datastructure for cloned nodes and heavily optimized compared to imp #1. Appears about 3-6 times faster in early tests with no mutations registered (expected case).
Usage
Actual Test cases
JSBin (todo)
/*subtree and childlist helpers*/
var has = Object.hasOwnProperty;
var map = Array.prototype.map;
var indexOf = Array.prototype.indexOf;
//using a non id (eg outerHTML or nodeValue) is extremely naive and will run into issues with nodes that may appear the same like <li></li>
var counter = 0;
var getId = function($ele) {
return $ele.id || ($ele._id = $ele._id || counter++);
};
//clone an html node into a custom datastructure
// see https://gist.github.com/megawac/8201012
var clone = function (par, deep) {
var copy = function(par, top) {
return {
node: par,
kids: top || deep ? map.call(par.childNodes, function(node) {
return copy(node);
}) : null
};
};
return copy(par, true);
};
//findChildMutations: array of mutations so far, element, element clone, bool => array of mutations
// dfs comparision search of two nodes
// this has to be as quick as possible
var findChildMutations = function(target, oldstate, deep) {
var mutations = [];
var add = function(node) {
mutations.push(new MutationRecord({
type: "childList",
target: node.parentElement,
addedNodes: [node]
}));
};
var rem = function(node, tar) {//have to pass tar because node.parentElement will be null when removed
mutations.push(new MutationRecord({
type: "childList",
target: tar,
removedNodes: [node]
}));
};
var findMut = function(node, old) {
var $kids = node.childNodes;
var $oldkids = old.kids;
var klen = $kids.length;
var olen = $oldkids.length;
if(!olen && !klen) return;//both empty; clearly no changes
//id to i and j search hash to prevent double checking an element
var id;
var map = {};
//array of potention conflict hashes
var conflicts = [];
//offsets since last resolve. Can also solve the problem with a continue but we exect this method to be faster as i and j should eventually correlate
//var offset_add = 0;//nodes added since last resolve //we dont have to check added as these are handled before remove
var offset_rem = 0;//nodes removed since last resolve
/*
* There is no gaurentee that the same node will be returned for both added and removed nodes
* if the position has been shuffled
*/
var resolver = function() {
var counter = 0;//prevents same conflict being resolved twice
var conflict;
for (var i = 0, l = conflicts.length-1; i <= l; i++) {
conflict = conflicts[i];
//attempt to determine if there was node rearrangement... won't gaurentee all matches
//also handles case where added/removed nodes cause nodes to be identified as conflicts
if(counter < l && Math.abs(conflict.i - (conflict.j + offset_rem)) >= l) {
add($kids[conflict.i]);//rearrangment ie removed then readded
rem($kids[conflict.i], old.node);
counter++;
} else if(deep) {//conflicts resolved - check deep
findMut($kids[conflict.i], $oldkids[conflict.j]);
}
}
offset_rem = conflicts.length = 0;//clear conflicts
};
var $cur, $old;//current and old nodes
//iterate over both old and current child nodes at the same time
for(var i = 0, j = 0, idx; i < klen || j < olen; ) {
//current and old nodes at the indexs
$cur = $kids[i];
$old = $oldkids[j] && $oldkids[j].node;
if($cur === $old) {//simple expected case - needs to be as fast as possible
if(deep) {//recurse
findMut($kids[i], $oldkids[j]);
}
//resolve conflicts
if(conflicts.length) resolver();
i++;
j++;
} else {//lookahead until they are the same again or the end of children
if($cur) {
id = getId($cur);
//check id is in the location map otherwise do a indexOf search
if(!has.call(map, id)) {//not already found
if((idx = indexOf.call($oldkids, $cur, j)) === -1) {
add($cur);
} else {
map[id] = true;
conflicts.push({//bit dirty
i: i,
j: idx
});
}
}
i++;
//continue;
}
if($old) {
id = getId($old);
if(!has.call(map, id)) {
if((idx = indexOf.call($kids, $old, i)) === -1) {
rem($old, old.node);
offset_rem++;
} else {
map[id] = true;
conflicts.push({
i: idx,
j: j
});
}
}
j++;
}
}
}
if(conflicts.length) resolver();
};
findMut(target, oldstate);
return mutations;
};
Usage
//node is a html element
//deep is a boolean
findChildMutations(node, clone(node, deep), deep)
Questions:
- Is there a better way to be able to accurately compare a node to its clone than to assign a unique id to each element being watched (see
getIdhelper function)? My concern with using.equalNodeor parsing the HTML is being able to match the node if there are changes and handling two similarly appearing nodes such as ali. I wrote a gist describing the problem. Implementation #2 applies the soloution discussed in the gist. - Can you give me some feedback and suggestions on my implementation? Is there any way to reduce this redundant code? (2.5) I feel like a node's position being moved in the child list does not have to be a special case and we may be able to just find it as an
addedNodeandremovedNodein the algorithm (may be difficult). - Update another issue with this code is it can be unacceptably slow when I tested it on some mobile devices (runs some of these JSLitmus tests (doesnt work in webkit because MutationObserver is protected) only 50 times a second). Can you give me some optimization tips for the snippet. Note, we can expect that there will usually not be any mutations.
- Do you know of any research/papers discussing comparing two trees/graphs? I haven't found much on the topic.