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