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] //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][5] [Actual Test cases][6] JSBin (todo) /*subtree and childlist helpers*/ 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: ---------- 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] 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. 4. Do you know of any research/papers discussing comparing two trees/graphs? I haven't found much on the topic. [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