MutationObserver (shim): Finding differences between 2 DOM trees

Question

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)

Usage
Actual Test cases
JSBin

/*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
Actual Test cases
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["mo_id"] = $ele["mo_id"] || ++counter);//normally mo_id is an expando variable
};

//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. 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? (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) 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.

Also do you know of any research/papers discussing comparing two trees/graphs? I haven't found much on the topic.

Answer 1

I assume you already scoured most resources on optimizing js, since you use most tricks ( including ~~ for Math.floor ). The only 1 I did not see is

• Store a reference to Math.abs: var abs = Math.abs;

I have to say I would not like to maintain this code, you have a serious arrow problem here:

                        });
                    }
                }
                j++;
            }
        }
    }
    resolver();
};

I am fairly certain that with some effort you could reduce this. Also the mixed naming does not help, you ought to stick to lowerCamelCasing at all times for variables and functions.

As for comparing elements, see this :

// Instead of using
node1.isSameNode(node2)

// use
node1 === node2 // or
node1 == node2

Update

The new approach you provided actually compares the elements which you store in your own custom structure, which is what I was trying to advocate before.

Some further observations:

• JSHint.com advises against creating functions in a loop, which you do on line 121, I agree with JSHint, you seem not to : /* jshint loopfunc:true */, do you need help unfunctioning that ?
• $ele["mo_id"] -> $ele.mo_id
• comparitor -> comparator
• tar -> target ?
• You have a number of times the following construct :

if ($old) {
  id = getId($old);
  if (!has(map, id)) {
    ...
  }
  j++
}

To prevent arrow coding, you could consider the folllowing Golfic approach which is acceptable IMO in this narrow case :

if( $old && j++ && id = getId($old) && !has(map,id) )
{
  ..
}