I've been working on a [`MutationObserver` es5 shim][1] 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)
[Usage][2]
[Actual Test cases][3]
[JSBin][4]
/*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).
**Edits** fixed the following bugs:
1. Calling `Array.prototype.indexOf` on `$oldkids` would not work as we were comparing an element to a clone data structure. Added a comparitor function to handle the case
2. Started ids at 1 as 0 is falsy
3. Fixed a bug in resolve conflicts when there is more than 1 conflict (solved by making counter the ceil of dividing len of conflicts by 2 instead of subbing 1)
4. Added a special case for when `idx=0` so we can get out of the hacky resolve conflict case and return to the expected case
[Usage][5]
[Actual Test cases][6]
JSBin (todo)
/*subtree and childlist helpers*/
//indexOf for collection using a comparitor
var has = Object.hasOwnProperty;
var map = Array.prototype.map;
var indexOf = Array.prototype.indexOf;
var findIndex = function(set, comparitor, from) {
for(var i = ~~from, l=set.length; i<l; i++) {
if(comparitor(set[i])) return i;
}
return -1;
};
//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 = 1;//don't use 0 as id (falsy)
var getId = function($ele) {
return $ele.id || ($ele[expando] = $ele[expando] || ++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 map = {};
var id;
var idx;//index of a moved or inserted element
//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 positions have been shuffled.
*/
var resolver = function() {
var size = conflicts.length - 1;
var counter = -~ (size / 2);//prevents same conflict being resolved twice consider when two nodes switch places. only one should be given a mutation event (note -~ is math.ceil shorthand)
conflicts.forEach(function(conflict) {
//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 && Math.abs(conflict.i - (conflict.j + offset_rem)) >= size) {
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
};
//current and old nodes
var $cur;
var $old;
//iterate over both old and current child nodes at the same time
for(var i = 0, j = 0; i < klen || j < olen; ) {
//current and old nodes at the indexs
$cur = $kids[i];
$old = j < olen && $oldkids[j].node;
if($cur === $old) {//simple expected case - needs to be as fast as possible
//recurse on next level of children
if(deep) findMut($cur, $oldkids[j]);
//resolve conflicts
if(conflicts.length) resolver();
i++;
j++;
} else {//(uncommon case) 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(map, id)) {//not already found
/* jshint loopfunc:true */
if((idx = findIndex($oldkids, function($el) { return $el.node === $cur; }, j)) === -1) { //custom indexOf using comparitor
add($cur);//$cur is a new node
} else {
map[id] = true;//mark id as found
conflicts.push({//add conflict
i: i,
j: idx
});
}
}
i++;
}
if($old) {
id = getId($old);
if(!has(map, id)) {
if((idx = indexOf.call($kids, $old, i)) === -1) {//dont need to use a special indexof but need to i-1 due to o-b-1 from previous part
rem($old, old.node);
offset_rem++;
} else if(idx === 0) {//special case: if idx=0 i and j are congurent so we can continue without conflict
continue;
} 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 (answer or reasonable suggestions for any of these will earn the bounty):
----------
1. 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 `getId` helper function)? My concern with using `.equalNode` or parsing the HTML is being able to match the node if there are changes and handling two similarly appearing nodes such as a `li`. I wrote a [gist describing the problem][7]. *Implementation #2 applies the soloution discussed in the gist.*
2. Can you give me some feedback and suggestions on my implementation? Is there any way to reduce [this redundant code?][8] (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 `addedNode` and `removedNode` in the algorithm (may be difficult).
3. **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)][9] 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.
<s>Also do you know of any research/papers discussing comparing two trees/graphs? I haven't found much on the topic.</s>
[1]: https://github.com/megawac/MutationObserver.js
[2]: https://github.com/megawac/MutationObserver.js/blob/30ab064a19d0a4f9ad70f409b9a29186fd87a085/MutationObserver.js#L230-239
[3]: https://rawgithub.com/megawac/MutationObserver.js/master/test/index.html
[4]: http://jsbin.com/uhoVibU/7
[5]: https://github.com/megawac/MutationObserver.js/blob/8de99a296017b07d71c2b9fce55dce41f9489d24/MutationObserver.js#L226-233
[6]: https://rawgithub.com/megawac/MutationObserver.js/childList-implementation-2/test/index.html
[7]: https://gist.github.com/megawac/8201012
[8]: https://github.com/megawac/MutationObserver.js/blob/8de99a296017b07d71c2b9fce55dce41f9489d24/MutationObserver.js#L142-175
[9]: https://rawgithub.com/megawac/MutationObserver.js/master/test/index.html