Skip to content

Instantly share code, notes, and snippets.

@megawac

megawac/jsbin.uhoVibU.html

Created December 31, 2013 02:51
Show Gist options
  • Save megawac/8191773 to your computer and use it in GitHub Desktop.
Save megawac/8191773 to your computer and use it in GitHub Desktop.
Download ZIP
childList and subtree tests
Raw
jsbin.uhoVibU.html
<!DOCTYPE html>
<html>
<head>
<link href="//code.jquery.com/qunit/qunit-git.css" rel="stylesheet" type="text/css" />
<script src="//cdn.jsdelivr.net/es5.shim/2.1.0/es5-shim.min.js"></script>
<script src="//code.jquery.com/jquery.min.js"></script>
<script src="//cdn.jsdelivr.net/curl.js/0.7.5/jquery/curl.js"></script>
<script src="//code.jquery.com/qunit/qunit-git.js"></script>
<script src="//www.broofa.com/Tools/JSLitmus/JSLitmus.js"></script>
<meta charset=utf-8 />
<title>Child list comparitor</title>
</head>
<body>
<div id="qunit"></div>
<div id="qunit-fixture">
<div id="map-test">
<div id="id1"></div>
<div id="id2"></div>
</div>
</div>
<br>
<h1 class="qunit-header">Child Node comparitor tests</h1>
</body>
</html>
Raw
jsbin.uhoVibU.js
this.comparer = (function() {
"use strict";
var has = Object.hasOwnProperty;
var foreach = Array.prototype.forEach;
var each = function (object, fn, bind){
for (var key in object){
if (has.call(object, key)) fn.call(bind, object[key], key, object);
}
};
var MutationRecord = window.MutationRecord = function(data) {
each(data, function(v,k) {
this[k] = v;
}, this);
};
MutationRecord.prototype = {
target: null,
type: null,
addedNodes: [],
removedNodes: [],
attributeName: null,
oldValue: null
};
/*subtree and childlist helpers*/
//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;
};
return {
$set_ids: $id_kids,
childList: findChildMutations
};
})();
curl(["//rawgithub.com/megawac/MutationObserver.js/subtree/test/utils.js"], function(utils) {//utils are just some simple test comparisions
QUnit.test("subtree", function() {
var $original = $("<div><p><strong>{hi}</strong><i>{yo}</i></p><span>xxx</span></div>")[0];
var getTestNode = function(deep) {
return comparer.$set_ids($original.cloneNode(true), deep);
};
var changes, $clone, expected, $tar, kids;
//test1
var $test = getTestNode(true);
QUnit.deepEqual(comparer.childList($test, $test.cloneNode(true), true), [], "no changes found on exact clone");
//test2
$test = getTestNode(false);
$clone = $test.cloneNode(true);
expected = {
addedNodes: [$("<p>stuff</p>").get(0)],
removedNodes: []
};
$($test).append(expected.addedNodes);
changes = comparer.childList($test, $clone, false);
ok(utils.expectedMutations(changes, expected), "Finds level one append nodes");
//test3
$test = getTestNode(false);
$clone = $test.cloneNode(true);
expected = {
addedNodes: [],
removedNodes: utils.$children($test)
};
$($test).empty();
changes = comparer.childList($test, $clone, false);
ok(utils.expectedMutations(changes, expected), "Finds level one removed nodes");
//test4
$test = $("<span>test text</span>").get(0);
$clone = $test.cloneNode(true);
expected = {
removedNodes: utils.$children($test),
addedNodes: utils.$children($($test).text("new stuff"))
};
changes = comparer.childList($test, $clone, false);
ok(utils.expectedMutations(changes, expected), "Notices text changes");
//test5
$test = getTestNode(false);
$clone = $test.cloneNode(true);
kids = $test.childNodes;
$($test).prepend(kids[kids.length-1]);
changes = utils.countMutations(comparer.childList($test, $clone, false));
QUnit.deepEqual(changes, {added: 1, removed: 1}, "Identifies level one changes in order");
//test6
$test = getTestNode(true);
$clone = $test.cloneNode(true);
$tar = utils.$randomChild($test);
expected = {
addedNodes: [$("<p>stuff</p>").get(0)],
removedNodes: []
};
$($tar).append(expected.addedNodes);
changes = comparer.childList($test, $clone, true);
ok(utils.expectedMutations(changes, expected), "Finds nested append nodes");
//test7
$test = getTestNode(true);
$clone = $test.cloneNode(true);
$tar = utils.$randomChild($test);
expected = {
addedNodes: [],
removedNodes: utils.$children($tar)
};
$($tar).empty();
changes = comparer.childList($test, $clone, true);
ok(utils.expectedMutations(changes, expected), "Finds nested removed nodes");
//test8
$test = comparer.$set_ids($("<div><span>nm</span><a href='#'>stuff</a></div>").get(0));
$clone = $test.cloneNode(true);
$tar = $($test).find('a');
expected = {
removedNodes: utils.$children($tar),
addedNodes: utils.$children($tar.text("new stuff"))
};
changes = comparer.childList($test, $clone, true);
ok(utils.expectedMutations(changes, expected), "Notices nested text changes");
//test9
$test = getTestNode(true);
$tar = utils.$randomChild($test);
kids = $tar.get(0).childNodes;
$tar.append("<span>yo</span><a href='http//me.com'>help</a>");
comparer.$set_ids($test, true);
$clone = $test.cloneNode(true);
$tar.prepend(kids[kids.length-1]);
changes = utils.countMutations(comparer.childList($test, $clone, true));
QUnit.deepEqual(changes, {added: 1, removed: 1}, "Identifies deep changes in order");
//test10+11
$test = getTestNode(true);
$clone = $test.cloneNode(true);
expected = {
removedNodes: [utils.$randomChild($test).remove().get(0)],
addedNodes: [$("<div>").append("<span><p>mor<b>e</b></p>stuff</span>").appendTo($test).get(0)]
};
changes = comparer.childList($test, $clone, true);
ok(utils.expectedMutations(changes, expected), "Notices add and remove in same cycle and doesnt call with nested added elements");
changes = comparer.childList($test, $test.cloneNode(true), true);
ok(utils.expectedMutations(changes, {
addedNodes: [],
removedNodes: []
}), "When deep set, adds ids to nested appended elements so following checks dont notice them");
//test11
$test = getTestNode(true);
$clone = $test.cloneNode(true);
expected = {
addedNodes: [],
removedNodes: [utils.$randomChild($test).remove().append("<span>stuff</span>").get(0)]
};
changes = comparer.childList($test, $clone, true);
ok(utils.expectedMutations(changes, expected), "Does not identify changes on removed node");
//test12
$test = getTestNode(true);
$clone = $test.cloneNode(true);
$tar = utils.$randomChild($test);
expected = {
removedNodes: [$tar.siblings(":eq(0)").remove().get(0)],
addedNodes: [$("<span>ya</span>").appendTo($tar).get(0)]
};
changes = comparer.childList($test, $clone, true);
ok(utils.expectedMutations(changes, expected), "Notices changes to subtree and direct childs");
//test13
$test = getTestNode(true);
$clone = $test.cloneNode(true);
$tar = utils.$randomChild($test);
expected = {
removedNodes: [$tar.siblings(":eq(0)").remove().get(0), utils.$randomChild($tar, true).remove().get(0)],
addedNodes: [$("<div><p></p></div>").appendTo($test).get(0), $("<span>ya</span>").appendTo($tar).get(0), $("<span>more stuff</span>").appendTo($test).get(0)]
};
changes = comparer.childList($test, $clone, true);
ok(utils.expectedMutations(changes, expected), "Notices many changes to subtree and direct childs");
});
});
//perf tests
(function() {
var $body = window.document.body;
comparer.$set_ids($body, true);
var $clone = $body.cloneNode(true);
JSLitmus.test('childList (shallow) search on body', function() {
comparer.childList($body, $clone, false);
});
JSLitmus.test('subtree (deep) search on body', function() {
comparer.childList($body, $clone, true);
});
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment