michael@0: "use strict";
michael@0: // TODO: iframes, contenteditable/designMode
michael@0: 
michael@0: // Everything is done in functions in this test harness, so we have to declare
michael@0: // all the variables before use to make sure they can be reused.
michael@0: var selection;
michael@0: var testDiv, paras, detachedDiv, detachedPara1, detachedPara2,
michael@0: 	foreignDoc, foreignPara1, foreignPara2, xmlDoc, xmlElement,
michael@0: 	detachedXmlElement, detachedTextNode, foreignTextNode,
michael@0: 	detachedForeignTextNode, xmlTextNode, detachedXmlTextNode,
michael@0: 	processingInstruction, detachedProcessingInstruction, comment,
michael@0: 	detachedComment, foreignComment, detachedForeignComment, xmlComment,
michael@0: 	detachedXmlComment, docfrag, foreignDocfrag, xmlDocfrag, doctype,
michael@0: 	foreignDoctype, xmlDoctype;
michael@0: var testRanges, testPoints, testNodes;
michael@0: 
michael@0: function setupRangeTests() {
michael@0: 	selection = getSelection();
michael@0: 	testDiv = document.querySelector("#test");
michael@0: 	if (testDiv) {
michael@0: 		testDiv.parentNode.removeChild(testDiv);
michael@0: 	}
michael@0: 	testDiv = document.createElement("div");
michael@0: 	testDiv.id = "test";
michael@0: 	document.body.insertBefore(testDiv, document.body.firstChild);
michael@0: 	// Test some diacritics, to make sure browsers are using code units here
michael@0: 	// and not something like grapheme clusters.
michael@0: 	testDiv.innerHTML = "<p id=a>A&#x308;b&#x308;c&#x308;d&#x308;e&#x308;f&#x308;g&#x308;h&#x308;\n"
michael@0: 		+ "<p id=b style=display:none>Ijklmnop\n"
michael@0: 		+ "<p id=c>Qrstuvwx"
michael@0: 		+ "<p id=d style=display:none>Yzabcdef"
michael@0: 		+ "<p id=e style=display:none>Ghijklmn";
michael@0: 	paras = testDiv.querySelectorAll("p");
michael@0: 
michael@0: 	detachedDiv = document.createElement("div");
michael@0: 	detachedPara1 = document.createElement("p");
michael@0: 	detachedPara1.appendChild(document.createTextNode("Opqrstuv"));
michael@0: 	detachedPara2 = document.createElement("p");
michael@0: 	detachedPara2.appendChild(document.createTextNode("Wxyzabcd"));
michael@0: 	detachedDiv.appendChild(detachedPara1);
michael@0: 	detachedDiv.appendChild(detachedPara2);
michael@0: 
michael@0: 	// Opera doesn't automatically create a doctype for a new HTML document,
michael@0: 	// contrary to spec.  It also doesn't let you add doctypes to documents
michael@0: 	// after the fact through any means I've tried.  So foreignDoc in Opera
michael@0: 	// will have no doctype, foreignDoctype will be null, and Opera will fail
michael@0: 	// some tests somewhat mysteriously as a result.
michael@0: 	foreignDoc = document.implementation.createHTMLDocument("");
michael@0: 	foreignPara1 = foreignDoc.createElement("p");
michael@0: 	foreignPara1.appendChild(foreignDoc.createTextNode("Efghijkl"));
michael@0: 	foreignPara2 = foreignDoc.createElement("p");
michael@0: 	foreignPara2.appendChild(foreignDoc.createTextNode("Mnopqrst"));
michael@0: 	foreignDoc.body.appendChild(foreignPara1);
michael@0: 	foreignDoc.body.appendChild(foreignPara2);
michael@0: 
michael@0: 	// Now we get to do really silly stuff, which nobody in the universe is
michael@0: 	// ever going to actually do, but the spec defines behavior, so too bad.
michael@0: 	// Testing is fun!
michael@0: 	xmlDoctype = document.implementation.createDocumentType("qorflesnorf", "abcde", "x\"'y");
michael@0: 	xmlDoc = document.implementation.createDocument(null, null, xmlDoctype);
michael@0: 	detachedXmlElement = xmlDoc.createElement("everyone-hates-hyphenated-element-names");
michael@0: 	detachedTextNode = document.createTextNode("Uvwxyzab");
michael@0: 	detachedForeignTextNode = foreignDoc.createTextNode("Cdefghij");
michael@0: 	detachedXmlTextNode = xmlDoc.createTextNode("Klmnopqr");
michael@0: 	// PIs only exist in XML documents, so don't bother with document or
michael@0: 	// foreignDoc.
michael@0: 	detachedProcessingInstruction = xmlDoc.createProcessingInstruction("whippoorwill", "chirp chirp chirp");
michael@0: 	detachedComment = document.createComment("Stuvwxyz");
michael@0: 	// Hurrah, we finally got to "z" at the end!
michael@0: 	detachedForeignComment = foreignDoc.createComment("אריה יהודה");
michael@0: 	detachedXmlComment = xmlDoc.createComment("בן חיים אליעזר");
michael@0: 
michael@0: 	// We should also test with document fragments that actually contain stuff
michael@0: 	// . . . but, maybe later.
michael@0: 	docfrag = document.createDocumentFragment();
michael@0: 	foreignDocfrag = foreignDoc.createDocumentFragment();
michael@0: 	xmlDocfrag = xmlDoc.createDocumentFragment();
michael@0: 
michael@0: 	xmlElement = xmlDoc.createElement("igiveuponcreativenames");
michael@0: 	xmlTextNode = xmlDoc.createTextNode("do re mi fa so la ti");
michael@0: 	xmlElement.appendChild(xmlTextNode);
michael@0: 	processingInstruction = xmlDoc.createProcessingInstruction("somePI", 'Did you know that ":syn sync fromstart" is very useful when using vim to edit large amounts of JavaScript embedded in HTML?');
michael@0: 	xmlDoc.appendChild(xmlElement);
michael@0: 	xmlDoc.appendChild(processingInstruction);
michael@0: 	xmlComment = xmlDoc.createComment("I maliciously created a comment that will break incautious XML serializers, but Firefox threw an exception, so all I got was this lousy T-shirt");
michael@0: 	xmlDoc.appendChild(xmlComment);
michael@0: 
michael@0: 	comment = document.createComment("Alphabet soup?");
michael@0: 	testDiv.appendChild(comment);
michael@0: 
michael@0: 	foreignComment = foreignDoc.createComment('"Commenter" and "commentator" mean different things.  I\'ve seen non-native speakers trip up on this.');
michael@0: 	foreignDoc.appendChild(foreignComment);
michael@0: 	foreignTextNode = foreignDoc.createTextNode("I admit that I harbor doubts about whether we really need so many things to test, but it's too late to stop now.");
michael@0: 	foreignDoc.body.appendChild(foreignTextNode);
michael@0: 
michael@0: 	doctype = document.doctype;
michael@0: 	foreignDoctype = foreignDoc.doctype;
michael@0: 
michael@0: 	testRanges = [
michael@0: 		// Various ranges within the text node children of different
michael@0: 		// paragraphs.  All should be valid.
michael@0: 		"[paras[0].firstChild, 0, paras[0].firstChild, 0]",
michael@0: 		"[paras[0].firstChild, 0, paras[0].firstChild, 1]",
michael@0: 		"[paras[0].firstChild, 2, paras[0].firstChild, 8]",
michael@0: 		"[paras[0].firstChild, 2, paras[0].firstChild, 9]",
michael@0: 		"[paras[1].firstChild, 0, paras[1].firstChild, 0]",
michael@0: 		"[paras[1].firstChild, 0, paras[1].firstChild, 1]",
michael@0: 		"[paras[1].firstChild, 2, paras[1].firstChild, 8]",
michael@0: 		"[paras[1].firstChild, 2, paras[1].firstChild, 9]",
michael@0: 		"[detachedPara1.firstChild, 0, detachedPara1.firstChild, 0]",
michael@0: 		"[detachedPara1.firstChild, 0, detachedPara1.firstChild, 1]",
michael@0: 		"[detachedPara1.firstChild, 2, detachedPara1.firstChild, 8]",
michael@0: 		"[foreignPara1.firstChild, 0, foreignPara1.firstChild, 0]",
michael@0: 		"[foreignPara1.firstChild, 0, foreignPara1.firstChild, 1]",
michael@0: 		"[foreignPara1.firstChild, 2, foreignPara1.firstChild, 8]",
michael@0: 		// Now try testing some elements, not just text nodes.
michael@0: 		"[document.documentElement, 0, document.documentElement, 1]",
michael@0: 		"[document.documentElement, 0, document.documentElement, 2]",
michael@0: 		"[document.documentElement, 1, document.documentElement, 2]",
michael@0: 		"[document.head, 1, document.head, 1]",
michael@0: 		"[document.body, 0, document.body, 1]",
michael@0: 		"[foreignDoc.documentElement, 0, foreignDoc.documentElement, 1]",
michael@0: 		"[foreignDoc.head, 1, foreignDoc.head, 1]",
michael@0: 		"[foreignDoc.body, 0, foreignDoc.body, 0]",
michael@0: 		"[paras[0], 0, paras[0], 0]",
michael@0: 		"[paras[0], 0, paras[0], 1]",
michael@0: 		"[detachedPara1, 0, detachedPara1, 0]",
michael@0: 		"[detachedPara1, 0, detachedPara1, 1]",
michael@0: 		// Now try some ranges that span elements.
michael@0: 		"[paras[0].firstChild, 0, paras[1].firstChild, 0]",
michael@0: 		"[paras[0].firstChild, 0, paras[1].firstChild, 8]",
michael@0: 		"[paras[0].firstChild, 3, paras[3], 1]",
michael@0: 		// How about something that spans a node and its descendant?
michael@0: 		"[paras[0], 0, paras[0].firstChild, 7]",
michael@0: 		"[testDiv, 2, paras[4], 1]",
michael@0: 		"[testDiv, 1, paras[2].firstChild, 5]",
michael@0: 		"[document.documentElement, 1, document.body, 0]",
michael@0: 		"[foreignDoc.documentElement, 1, foreignDoc.body, 0]",
michael@0: 		// Then a few more interesting things just for good measure.
michael@0: 		"[document, 0, document, 1]",
michael@0: 		"[document, 0, document, 2]",
michael@0: 		"[document, 1, document, 2]",
michael@0: 		"[testDiv, 0, comment, 5]",
michael@0: 		"[paras[2].firstChild, 4, comment, 2]",
michael@0: 		"[paras[3], 1, comment, 8]",
michael@0: 		"[foreignDoc, 0, foreignDoc, 0]",
michael@0: 		"[foreignDoc, 1, foreignComment, 2]",
michael@0: 		"[foreignDoc.body, 0, foreignTextNode, 36]",
michael@0: 		"[xmlDoc, 0, xmlDoc, 0]",
michael@0: 		// Opera 11 crashes if you extractContents() a range that ends at offset
michael@0: 		// zero in a comment.  Comment out this line to run the tests successfully.
michael@0: 		"[xmlDoc, 1, xmlComment, 0]",
michael@0: 		"[detachedTextNode, 0, detachedTextNode, 8]",
michael@0: 		"[detachedForeignTextNode, 7, detachedForeignTextNode, 7]",
michael@0: 		"[detachedForeignTextNode, 0, detachedForeignTextNode, 8]",
michael@0: 		"[detachedXmlTextNode, 7, detachedXmlTextNode, 7]",
michael@0: 		"[detachedXmlTextNode, 0, detachedXmlTextNode, 8]",
michael@0: 		"[detachedComment, 3, detachedComment, 4]",
michael@0: 		"[detachedComment, 5, detachedComment, 5]",
michael@0: 		"[detachedForeignComment, 0, detachedForeignComment, 1]",
michael@0: 		"[detachedForeignComment, 4, detachedForeignComment, 4]",
michael@0: 		"[detachedXmlComment, 2, detachedXmlComment, 6]",
michael@0: 		"[docfrag, 0, docfrag, 0]",
michael@0: 		"[foreignDocfrag, 0, foreignDocfrag, 0]",
michael@0: 		"[xmlDocfrag, 0, xmlDocfrag, 0]",
michael@0: 	];
michael@0: 
michael@0: 	testPoints = [
michael@0: 		// Various positions within the page, some invalid.  Remember that
michael@0: 		// paras[0] is visible, and paras[1] is display: none.
michael@0: 		"[paras[0].firstChild, -1]",
michael@0: 		"[paras[0].firstChild, 0]",
michael@0: 		"[paras[0].firstChild, 1]",
michael@0: 		"[paras[0].firstChild, 2]",
michael@0: 		"[paras[0].firstChild, 8]",
michael@0: 		"[paras[0].firstChild, 9]",
michael@0: 		"[paras[0].firstChild, 10]",
michael@0: 		"[paras[0].firstChild, 65535]",
michael@0: 		"[paras[1].firstChild, -1]",
michael@0: 		"[paras[1].firstChild, 0]",
michael@0: 		"[paras[1].firstChild, 1]",
michael@0: 		"[paras[1].firstChild, 2]",
michael@0: 		"[paras[1].firstChild, 8]",
michael@0: 		"[paras[1].firstChild, 9]",
michael@0: 		"[paras[1].firstChild, 10]",
michael@0: 		"[paras[1].firstChild, 65535]",
michael@0: 		"[detachedPara1.firstChild, 0]",
michael@0: 		"[detachedPara1.firstChild, 1]",
michael@0: 		"[detachedPara1.firstChild, 8]",
michael@0: 		"[detachedPara1.firstChild, 9]",
michael@0: 		"[foreignPara1.firstChild, 0]",
michael@0: 		"[foreignPara1.firstChild, 1]",
michael@0: 		"[foreignPara1.firstChild, 8]",
michael@0: 		"[foreignPara1.firstChild, 9]",
michael@0: 		// Now try testing some elements, not just text nodes.
michael@0: 		"[document.documentElement, -1]",
michael@0: 		"[document.documentElement, 0]",
michael@0: 		"[document.documentElement, 1]",
michael@0: 		"[document.documentElement, 2]",
michael@0: 		"[document.documentElement, 7]",
michael@0: 		"[document.head, 1]",
michael@0: 		"[document.body, 3]",
michael@0: 		"[foreignDoc.documentElement, 0]",
michael@0: 		"[foreignDoc.documentElement, 1]",
michael@0: 		"[foreignDoc.head, 0]",
michael@0: 		"[foreignDoc.body, 1]",
michael@0: 		"[paras[0], 0]",
michael@0: 		"[paras[0], 1]",
michael@0: 		"[paras[0], 2]",
michael@0: 		"[paras[1], 0]",
michael@0: 		"[paras[1], 1]",
michael@0: 		"[paras[1], 2]",
michael@0: 		"[detachedPara1, 0]",
michael@0: 		"[detachedPara1, 1]",
michael@0: 		"[testDiv, 0]",
michael@0: 		"[testDiv, 3]",
michael@0: 		// Then a few more interesting things just for good measure.
michael@0: 		"[document, -1]",
michael@0: 		"[document, 0]",
michael@0: 		"[document, 1]",
michael@0: 		"[document, 2]",
michael@0: 		"[document, 3]",
michael@0: 		"[comment, -1]",
michael@0: 		"[comment, 0]",
michael@0: 		"[comment, 4]",
michael@0: 		"[comment, 96]",
michael@0: 		"[foreignDoc, 0]",
michael@0: 		"[foreignDoc, 1]",
michael@0: 		"[foreignComment, 2]",
michael@0: 		"[foreignTextNode, 0]",
michael@0: 		"[foreignTextNode, 36]",
michael@0: 		"[xmlDoc, -1]",
michael@0: 		"[xmlDoc, 0]",
michael@0: 		"[xmlDoc, 1]",
michael@0: 		"[xmlDoc, 5]",
michael@0: 		"[xmlComment, 0]",
michael@0: 		"[xmlComment, 4]",
michael@0: 		"[processingInstruction, 0]",
michael@0: 		"[processingInstruction, 5]",
michael@0: 		"[processingInstruction, 9]",
michael@0: 		"[detachedTextNode, 0]",
michael@0: 		"[detachedTextNode, 8]",
michael@0: 		"[detachedForeignTextNode, 0]",
michael@0: 		"[detachedForeignTextNode, 8]",
michael@0: 		"[detachedXmlTextNode, 0]",
michael@0: 		"[detachedXmlTextNode, 8]",
michael@0: 		"[detachedProcessingInstruction, 12]",
michael@0: 		"[detachedComment, 3]",
michael@0: 		"[detachedComment, 5]",
michael@0: 		"[detachedForeignComment, 0]",
michael@0: 		"[detachedForeignComment, 4]",
michael@0: 		"[detachedXmlComment, 2]",
michael@0: 		"[docfrag, 0]",
michael@0: 		"[foreignDocfrag, 0]",
michael@0: 		"[xmlDocfrag, 0]",
michael@0: 		"[doctype, 0]",
michael@0: 		"[doctype, -17]",
michael@0: 		"[doctype, 1]",
michael@0: 		"[foreignDoctype, 0]",
michael@0: 		"[xmlDoctype, 0]",
michael@0: 	];
michael@0: 
michael@0: 	testNodes = [
michael@0: 		"paras[0]",
michael@0: 		"paras[0].firstChild",
michael@0: 		"paras[1]",
michael@0: 		"paras[1].firstChild",
michael@0: 		"foreignPara1",
michael@0: 		"foreignPara1.firstChild",
michael@0: 		"detachedPara1",
michael@0: 		"detachedPara1.firstChild",
michael@0: 		"detachedPara1",
michael@0: 		"detachedPara1.firstChild",
michael@0: 		"testDiv",
michael@0: 		"document",
michael@0: 		"detachedDiv",
michael@0: 		"detachedPara2",
michael@0: 		"foreignDoc",
michael@0: 		"foreignPara2",
michael@0: 		"xmlDoc",
michael@0: 		"xmlElement",
michael@0: 		"detachedXmlElement",
michael@0: 		"detachedTextNode",
michael@0: 		"foreignTextNode",
michael@0: 		"detachedForeignTextNode",
michael@0: 		"xmlTextNode",
michael@0: 		"detachedXmlTextNode",
michael@0: 		"processingInstruction",
michael@0: 		"detachedProcessingInstruction",
michael@0: 		"comment",
michael@0: 		"detachedComment",
michael@0: 		"foreignComment",
michael@0: 		"detachedForeignComment",
michael@0: 		"xmlComment",
michael@0: 		"detachedXmlComment",
michael@0: 		"docfrag",
michael@0: 		"foreignDocfrag",
michael@0: 		"xmlDocfrag",
michael@0: 		"doctype",
michael@0: 		"foreignDoctype",
michael@0: 		"xmlDoctype",
michael@0: 	];
michael@0: }
michael@0: if ("setup" in window) {
michael@0: 	setup(setupRangeTests);
michael@0: } else {
michael@0: 	// Presumably we're running from within an iframe or something
michael@0: 	setupRangeTests();
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Return the length of a node as specified in DOM Range.
michael@0:  */
michael@0: function getNodeLength(node) {
michael@0: 	if (node.nodeType == Node.DOCUMENT_TYPE_NODE) {
michael@0: 		return 0;
michael@0: 	}
michael@0: 	if (node.nodeType == Node.TEXT_NODE || node.nodeType == Node.PROCESSING_INSTRUCTION_NODE || node.nodeType == Node.COMMENT_NODE) {
michael@0: 		return node.length;
michael@0: 	}
michael@0: 	return node.childNodes.length;
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Returns the furthest ancestor of a Node as defined by the spec.
michael@0:  */
michael@0: function furthestAncestor(node) {
michael@0: 	var root = node;
michael@0: 	while (root.parentNode != null) {
michael@0: 		root = root.parentNode;
michael@0: 	}
michael@0: 	return root;
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * "The ancestor containers of a Node are the Node itself and all its
michael@0:  * ancestors."
michael@0:  *
michael@0:  * Is node1 an ancestor container of node2?
michael@0:  */
michael@0: function isAncestorContainer(node1, node2) {
michael@0: 	return node1 == node2 ||
michael@0: 		(node2.compareDocumentPosition(node1) & Node.DOCUMENT_POSITION_CONTAINS);
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Returns the first Node that's after node in tree order, or null if node is
michael@0:  * the last Node.
michael@0:  */
michael@0: function nextNode(node) {
michael@0: 	if (node.hasChildNodes()) {
michael@0: 		return node.firstChild;
michael@0: 	}
michael@0: 	return nextNodeDescendants(node);
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Returns the last Node that's before node in tree order, or null if node is
michael@0:  * the first Node.
michael@0:  */
michael@0: function previousNode(node) {
michael@0: 	if (node.previousSibling) {
michael@0: 		node = node.previousSibling;
michael@0: 		while (node.hasChildNodes()) {
michael@0: 			node = node.lastChild;
michael@0: 		}
michael@0: 		return node;
michael@0: 	}
michael@0: 	return node.parentNode;
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Returns the next Node that's after node and all its descendants in tree
michael@0:  * order, or null if node is the last Node or an ancestor of it.
michael@0:  */
michael@0: function nextNodeDescendants(node) {
michael@0: 	while (node && !node.nextSibling) {
michael@0: 		node = node.parentNode;
michael@0: 	}
michael@0: 	if (!node) {
michael@0: 		return null;
michael@0: 	}
michael@0: 	return node.nextSibling;
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Returns the ownerDocument of the Node, or the Node itself if it's a
michael@0:  * Document.
michael@0:  */
michael@0: function ownerDocument(node) {
michael@0: 	return node.nodeType == Node.DOCUMENT_NODE
michael@0: 		? node
michael@0: 		: node.ownerDocument;
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Returns true if ancestor is an ancestor of descendant, false otherwise.
michael@0:  */
michael@0: function isAncestor(ancestor, descendant) {
michael@0: 	if (!ancestor || !descendant) {
michael@0: 		return false;
michael@0: 	}
michael@0: 	while (descendant && descendant != ancestor) {
michael@0: 		descendant = descendant.parentNode;
michael@0: 	}
michael@0: 	return descendant == ancestor;
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Returns true if descendant is a descendant of ancestor, false otherwise.
michael@0:  */
michael@0: function isDescendant(descendant, ancestor) {
michael@0: 	return isAncestor(ancestor, descendant);
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * The position of two boundary points relative to one another, as defined by
michael@0:  * the spec.
michael@0:  */
michael@0: function getPosition(nodeA, offsetA, nodeB, offsetB) {
michael@0: 	// "If node A is the same as node B, return equal if offset A equals offset
michael@0: 	// B, before if offset A is less than offset B, and after if offset A is
michael@0: 	// greater than offset B."
michael@0: 	if (nodeA == nodeB) {
michael@0: 		if (offsetA == offsetB) {
michael@0: 			return "equal";
michael@0: 		}
michael@0: 		if (offsetA < offsetB) {
michael@0: 			return "before";
michael@0: 		}
michael@0: 		if (offsetA > offsetB) {
michael@0: 			return "after";
michael@0: 		}
michael@0: 	}
michael@0: 
michael@0: 	// "If node A is after node B in tree order, compute the position of (node
michael@0: 	// B, offset B) relative to (node A, offset A). If it is before, return
michael@0: 	// after. If it is after, return before."
michael@0: 	if (nodeB.compareDocumentPosition(nodeA) & Node.DOCUMENT_POSITION_FOLLOWING) {
michael@0: 		var pos = getPosition(nodeB, offsetB, nodeA, offsetA);
michael@0: 		if (pos == "before") {
michael@0: 			return "after";
michael@0: 		}
michael@0: 		if (pos == "after") {
michael@0: 			return "before";
michael@0: 		}
michael@0: 	}
michael@0: 
michael@0: 	// "If node A is an ancestor of node B:"
michael@0: 	if (nodeB.compareDocumentPosition(nodeA) & Node.DOCUMENT_POSITION_CONTAINS) {
michael@0: 		// "Let child equal node B."
michael@0: 		var child = nodeB;
michael@0: 
michael@0: 		// "While child is not a child of node A, set child to its parent."
michael@0: 		while (child.parentNode != nodeA) {
michael@0: 			child = child.parentNode;
michael@0: 		}
michael@0: 
michael@0: 		// "If the index of child is less than offset A, return after."
michael@0: 		if (indexOf(child) < offsetA) {
michael@0: 			return "after";
michael@0: 		}
michael@0: 	}
michael@0: 
michael@0: 	// "Return before."
michael@0: 	return "before";
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * "contained" as defined by DOM Range: "A Node node is contained in a range
michael@0:  * range if node's furthest ancestor is the same as range's root, and (node, 0)
michael@0:  * is after range's start, and (node, length of node) is before range's end."
michael@0:  */
michael@0: function isContained(node, range) {
michael@0: 	var pos1 = getPosition(node, 0, range.startContainer, range.startOffset);
michael@0: 	var pos2 = getPosition(node, getNodeLength(node), range.endContainer, range.endOffset);
michael@0: 
michael@0: 	return furthestAncestor(node) == furthestAncestor(range.startContainer)
michael@0: 		&& pos1 == "after"
michael@0: 		&& pos2 == "before";
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * "partially contained" as defined by DOM Range: "A Node is partially
michael@0:  * contained in a range if it is an ancestor container of the range's start but
michael@0:  * not its end, or vice versa."
michael@0:  */
michael@0: function isPartiallyContained(node, range) {
michael@0: 	var cond1 = isAncestorContainer(node, range.startContainer);
michael@0: 	var cond2 = isAncestorContainer(node, range.endContainer);
michael@0: 	return (cond1 && !cond2) || (cond2 && !cond1);
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Index of a node as defined by the spec.
michael@0:  */
michael@0: function indexOf(node) {
michael@0: 	if (!node.parentNode) {
michael@0: 		// No preceding sibling nodes, right?
michael@0: 		return 0;
michael@0: 	}
michael@0: 	var i = 0;
michael@0: 	while (node != node.parentNode.childNodes[i]) {
michael@0: 		i++;
michael@0: 	}
michael@0: 	return i;
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * extractContents() implementation, following the spec.  If an exception is
michael@0:  * supposed to be thrown, will return a string with the name (e.g.,
michael@0:  * "HIERARCHY_REQUEST_ERR") instead of a document fragment.  It might also
michael@0:  * return an arbitrary human-readable string if a condition is hit that implies
michael@0:  * a spec bug.
michael@0:  */
michael@0: function myExtractContents(range) {
michael@0: 	// "If the context object's detached flag is set, raise an
michael@0: 	// INVALID_STATE_ERR exception and abort these steps."
michael@0: 	try {
michael@0: 		range.collapsed;
michael@0: 	} catch (e) {
michael@0: 		return "INVALID_STATE_ERR";
michael@0: 	}
michael@0: 
michael@0: 	// "Let frag be a new DocumentFragment whose ownerDocument is the same as
michael@0: 	// the ownerDocument of the context object's start node."
michael@0: 	var ownerDoc = range.startContainer.nodeType == Node.DOCUMENT_NODE
michael@0: 		? range.startContainer
michael@0: 		: range.startContainer.ownerDocument;
michael@0: 	var frag = ownerDoc.createDocumentFragment();
michael@0: 
michael@0: 	// "If the context object's start and end are the same, abort this method,
michael@0: 	// returning frag."
michael@0: 	if (range.startContainer == range.endContainer
michael@0: 	&& range.startOffset == range.endOffset) {
michael@0: 		return frag;
michael@0: 	}
michael@0: 
michael@0: 	// "Let original start node, original start offset, original end node, and
michael@0: 	// original end offset be the context object's start and end nodes and
michael@0: 	// offsets, respectively."
michael@0: 	var originalStartNode = range.startContainer;
michael@0: 	var originalStartOffset = range.startOffset;
michael@0: 	var originalEndNode = range.endContainer;
michael@0: 	var originalEndOffset = range.endOffset;
michael@0: 
michael@0: 	// "If original start node and original end node are the same, and they are
michael@0: 	// a Text or Comment node:"
michael@0: 	if (range.startContainer == range.endContainer
michael@0: 	&& (range.startContainer.nodeType == Node.TEXT_NODE
michael@0: 	|| range.startContainer.nodeType == Node.COMMENT_NODE)) {
michael@0: 		// "Let clone be the result of calling cloneNode(false) on original
michael@0: 		// start node."
michael@0: 		var clone = originalStartNode.cloneNode(false);
michael@0: 
michael@0: 		// "Set the data of clone to the result of calling
michael@0: 		// substringData(original start offset, original end offset − original
michael@0: 		// start offset) on original start node."
michael@0: 		clone.data = originalStartNode.substringData(originalStartOffset,
michael@0: 			originalEndOffset - originalStartOffset);
michael@0: 
michael@0: 		// "Append clone as the last child of frag."
michael@0: 		frag.appendChild(clone);
michael@0: 
michael@0: 		// "Call deleteData(original start offset, original end offset −
michael@0: 		// original start offset) on original start node."
michael@0: 		originalStartNode.deleteData(originalStartOffset,
michael@0: 			originalEndOffset - originalStartOffset);
michael@0: 
michael@0: 		// "Abort this method, returning frag."
michael@0: 		return frag;
michael@0: 	}
michael@0: 
michael@0: 	// "Let common ancestor equal original start node."
michael@0: 	var commonAncestor = originalStartNode;
michael@0: 
michael@0: 	// "While common ancestor is not an ancestor container of original end
michael@0: 	// node, set common ancestor to its own parent."
michael@0: 	while (!isAncestorContainer(commonAncestor, originalEndNode)) {
michael@0: 		commonAncestor = commonAncestor.parentNode;
michael@0: 	}
michael@0: 
michael@0: 	// "If original start node is an ancestor container of original end node,
michael@0: 	// let first partially contained child be null."
michael@0: 	var firstPartiallyContainedChild;
michael@0: 	if (isAncestorContainer(originalStartNode, originalEndNode)) {
michael@0: 		firstPartiallyContainedChild = null;
michael@0: 	// "Otherwise, let first partially contained child be the first child of
michael@0: 	// common ancestor that is partially contained in the context object."
michael@0: 	} else {
michael@0: 		for (var i = 0; i < commonAncestor.childNodes.length; i++) {
michael@0: 			if (isPartiallyContained(commonAncestor.childNodes[i], range)) {
michael@0: 				firstPartiallyContainedChild = commonAncestor.childNodes[i];
michael@0: 				break;
michael@0: 			}
michael@0: 		}
michael@0: 		if (!firstPartiallyContainedChild) {
michael@0: 			throw "Spec bug: no first partially contained child!";
michael@0: 		}
michael@0: 	}
michael@0: 
michael@0: 	// "If original end node is an ancestor container of original start node,
michael@0: 	// let last partially contained child be null."
michael@0: 	var lastPartiallyContainedChild;
michael@0: 	if (isAncestorContainer(originalEndNode, originalStartNode)) {
michael@0: 		lastPartiallyContainedChild = null;
michael@0: 	// "Otherwise, let last partially contained child be the last child of
michael@0: 	// common ancestor that is partially contained in the context object."
michael@0: 	} else {
michael@0: 		for (var i = commonAncestor.childNodes.length - 1; i >= 0; i--) {
michael@0: 			if (isPartiallyContained(commonAncestor.childNodes[i], range)) {
michael@0: 				lastPartiallyContainedChild = commonAncestor.childNodes[i];
michael@0: 				break;
michael@0: 			}
michael@0: 		}
michael@0: 		if (!lastPartiallyContainedChild) {
michael@0: 			throw "Spec bug: no last partially contained child!";
michael@0: 		}
michael@0: 	}
michael@0: 
michael@0: 	// "Let contained children be a list of all children of common ancestor
michael@0: 	// that are contained in the context object, in tree order."
michael@0: 	//
michael@0: 	// "If any member of contained children is a DocumentType, raise a
michael@0: 	// HIERARCHY_REQUEST_ERR exception and abort these steps."
michael@0: 	var containedChildren = [];
michael@0: 	for (var i = 0; i < commonAncestor.childNodes.length; i++) {
michael@0: 		if (isContained(commonAncestor.childNodes[i], range)) {
michael@0: 			if (commonAncestor.childNodes[i].nodeType
michael@0: 			== Node.DOCUMENT_TYPE_NODE) {
michael@0: 				return "HIERARCHY_REQUEST_ERR";
michael@0: 			}
michael@0: 			containedChildren.push(commonAncestor.childNodes[i]);
michael@0: 		}
michael@0: 	}
michael@0: 
michael@0: 	// "If original start node is an ancestor container of original end node,
michael@0: 	// set new node to original start node and new offset to original start
michael@0: 	// offset."
michael@0: 	var newNode, newOffset;
michael@0: 	if (isAncestorContainer(originalStartNode, originalEndNode)) {
michael@0: 		newNode = originalStartNode;
michael@0: 		newOffset = originalStartOffset;
michael@0: 	// "Otherwise:"
michael@0: 	} else {
michael@0: 		// "Let reference node equal original start node."
michael@0: 		var referenceNode = originalStartNode;
michael@0: 
michael@0: 		// "While reference node's parent is not null and is not an ancestor
michael@0: 		// container of original end node, set reference node to its parent."
michael@0: 		while (referenceNode.parentNode
michael@0: 		&& !isAncestorContainer(referenceNode.parentNode, originalEndNode)) {
michael@0: 			referenceNode = referenceNode.parentNode;
michael@0: 		}
michael@0: 
michael@0: 		// "Set new node to the parent of reference node, and new offset to one
michael@0: 		// plus the index of reference node."
michael@0: 		newNode = referenceNode.parentNode;
michael@0: 		newOffset = 1 + indexOf(referenceNode);
michael@0: 	}
michael@0: 
michael@0: 	// "If first partially contained child is a Text or Comment node:"
michael@0: 	if (firstPartiallyContainedChild
michael@0: 	&& (firstPartiallyContainedChild.nodeType == Node.TEXT_NODE
michael@0: 	|| firstPartiallyContainedChild.nodeType == Node.COMMENT_NODE)) {
michael@0: 		// "Let clone be the result of calling cloneNode(false) on original
michael@0: 		// start node."
michael@0: 		var clone = originalStartNode.cloneNode(false);
michael@0: 
michael@0: 		// "Set the data of clone to the result of calling substringData() on
michael@0: 		// original start node, with original start offset as the first
michael@0: 		// argument and (length of original start node − original start offset)
michael@0: 		// as the second."
michael@0: 		clone.data = originalStartNode.substringData(originalStartOffset,
michael@0: 			getNodeLength(originalStartNode) - originalStartOffset);
michael@0: 
michael@0: 		// "Append clone as the last child of frag."
michael@0: 		frag.appendChild(clone);
michael@0: 
michael@0: 		// "Call deleteData() on original start node, with original start
michael@0: 		// offset as the first argument and (length of original start node −
michael@0: 		// original start offset) as the second."
michael@0: 		originalStartNode.deleteData(originalStartOffset,
michael@0: 			getNodeLength(originalStartNode) - originalStartOffset);
michael@0: 	// "Otherwise, if first partially contained child is not null:"
michael@0: 	} else if (firstPartiallyContainedChild) {
michael@0: 		// "Let clone be the result of calling cloneNode(false) on first
michael@0: 		// partially contained child."
michael@0: 		var clone = firstPartiallyContainedChild.cloneNode(false);
michael@0: 
michael@0: 		// "Append clone as the last child of frag."
michael@0: 		frag.appendChild(clone);
michael@0: 
michael@0: 		// "Let subrange be a new Range whose start is (original start node,
michael@0: 		// original start offset) and whose end is (first partially contained
michael@0: 		// child, length of first partially contained child)."
michael@0: 		var subrange = ownerDoc.createRange();
michael@0: 		subrange.setStart(originalStartNode, originalStartOffset);
michael@0: 		subrange.setEnd(firstPartiallyContainedChild,
michael@0: 			getNodeLength(firstPartiallyContainedChild));
michael@0: 
michael@0: 		// "Let subfrag be the result of calling extractContents() on
michael@0: 		// subrange."
michael@0: 		var subfrag = myExtractContents(subrange);
michael@0: 
michael@0: 		// "For each child of subfrag, in order, append that child to clone as
michael@0: 		// its last child."
michael@0: 		for (var i = 0; i < subfrag.childNodes.length; i++) {
michael@0: 			clone.appendChild(subfrag.childNodes[i]);
michael@0: 		}
michael@0: 	}
michael@0: 
michael@0: 	// "For each contained child in contained children, append contained child
michael@0: 	// as the last child of frag."
michael@0: 	for (var i = 0; i < containedChildren.length; i++) {
michael@0: 		frag.appendChild(containedChildren[i]);
michael@0: 	}
michael@0: 
michael@0: 	// "If last partially contained child is a Text or Comment node:"
michael@0: 	if (lastPartiallyContainedChild
michael@0: 	&& (lastPartiallyContainedChild.nodeType == Node.TEXT_NODE
michael@0: 	|| lastPartiallyContainedChild.nodeType == Node.COMMENT_NODE)) {
michael@0: 		// "Let clone be the result of calling cloneNode(false) on original
michael@0: 		// end node."
michael@0: 		var clone = originalEndNode.cloneNode(false);
michael@0: 
michael@0: 		// "Set the data of clone to the result of calling substringData(0,
michael@0: 		// original end offset) on original end node."
michael@0: 		clone.data = originalEndNode.substringData(0, originalEndOffset);
michael@0: 
michael@0: 		// "Append clone as the last child of frag."
michael@0: 		frag.appendChild(clone);
michael@0: 
michael@0: 		// "Call deleteData(0, original end offset) on original end node."
michael@0: 		originalEndNode.deleteData(0, originalEndOffset);
michael@0: 	// "Otherwise, if last partially contained child is not null:"
michael@0: 	} else if (lastPartiallyContainedChild) {
michael@0: 		// "Let clone be the result of calling cloneNode(false) on last
michael@0: 		// partially contained child."
michael@0: 		var clone = lastPartiallyContainedChild.cloneNode(false);
michael@0: 
michael@0: 		// "Append clone as the last child of frag."
michael@0: 		frag.appendChild(clone);
michael@0: 
michael@0: 		// "Let subrange be a new Range whose start is (last partially
michael@0: 		// contained child, 0) and whose end is (original end node, original
michael@0: 		// end offset)."
michael@0: 		var subrange = ownerDoc.createRange();
michael@0: 		subrange.setStart(lastPartiallyContainedChild, 0);
michael@0: 		subrange.setEnd(originalEndNode, originalEndOffset);
michael@0: 
michael@0: 		// "Let subfrag be the result of calling extractContents() on
michael@0: 		// subrange."
michael@0: 		var subfrag = myExtractContents(subrange);
michael@0: 
michael@0: 		// "For each child of subfrag, in order, append that child to clone as
michael@0: 		// its last child."
michael@0: 		for (var i = 0; i < subfrag.childNodes.length; i++) {
michael@0: 			clone.appendChild(subfrag.childNodes[i]);
michael@0: 		}
michael@0: 	}
michael@0: 
michael@0: 	// "Set the context object's start and end to (new node, new offset)."
michael@0: 	range.setStart(newNode, newOffset);
michael@0: 	range.setEnd(newNode, newOffset);
michael@0: 
michael@0: 	// "Return frag."
michael@0: 	return frag;
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * insertNode() implementation, following the spec.  If an exception is
michael@0:  * supposed to be thrown, will return a string with the name (e.g.,
michael@0:  * "HIERARCHY_REQUEST_ERR") instead of a document fragment.  It might also
michael@0:  * return an arbitrary human-readable string if a condition is hit that implies
michael@0:  * a spec bug.
michael@0:  */
michael@0: function myInsertNode(range, newNode) {
michael@0: 	// "If the context object's detached flag is set, raise an
michael@0: 	// INVALID_STATE_ERR exception and abort these steps."
michael@0: 	//
michael@0: 	// Assume that if accessing collapsed throws, it's detached.
michael@0: 	try {
michael@0: 		range.collapsed;
michael@0: 	} catch (e) {
michael@0: 		return "INVALID_STATE_ERR";
michael@0: 	}
michael@0: 
michael@0: 	// "If the context object's start node is a Text or Comment node and its
michael@0: 	// parent is null, raise an HIERARCHY_REQUEST_ERR exception and abort these
michael@0: 	// steps."
michael@0: 	if ((range.startContainer.nodeType == Node.TEXT_NODE
michael@0: 	|| range.startContainer.nodeType == Node.COMMENT_NODE)
michael@0: 	&& !range.startContainer.parentNode) {
michael@0: 		return "HIERARCHY_REQUEST_ERR";
michael@0: 	}
michael@0: 
michael@0: 	// "If the context object's start node is a Text node, run splitText() on
michael@0: 	// it with the context object's start offset as its argument, and let
michael@0: 	// reference node be the result."
michael@0: 	var referenceNode;
michael@0: 	if (range.startContainer.nodeType == Node.TEXT_NODE) {
michael@0: 		// We aren't testing how ranges vary under mutations, and browsers vary
michael@0: 		// in how they mutate for splitText, so let's just force the correct
michael@0: 		// way.
michael@0: 		var start = [range.startContainer, range.startOffset];
michael@0: 		var end = [range.endContainer, range.endOffset];
michael@0: 
michael@0: 		referenceNode = range.startContainer.splitText(range.startOffset);
michael@0: 
michael@0: 		if (start[0] == end[0]
michael@0: 		&& end[1] > start[1]) {
michael@0: 			end[0] = referenceNode;
michael@0: 			end[1] -= start[1];
michael@0: 		} else if (end[0] == start[0].parentNode
michael@0: 		&& end[1] > indexOf(referenceNode)) {
michael@0: 			end[1]++;
michael@0: 		}
michael@0: 		range.setStart(start[0], start[1]);
michael@0: 		range.setEnd(end[0], end[1]);
michael@0: 	// "Otherwise, if the context object's start node is a Comment, let
michael@0: 	// reference node be the context object's start node."
michael@0: 	} else if (range.startContainer.nodeType == Node.COMMENT_NODE) {
michael@0: 		referenceNode = range.startContainer;
michael@0: 	// "Otherwise, let reference node be the child of the context object's
michael@0: 	// start node with index equal to the context object's start offset, or
michael@0: 	// null if there is no such child."
michael@0: 	} else {
michael@0: 		referenceNode = range.startContainer.childNodes[range.startOffset];
michael@0: 		if (typeof referenceNode == "undefined") {
michael@0: 			referenceNode = null;
michael@0: 		}
michael@0: 	}
michael@0: 
michael@0: 	// "If reference node is null, let parent node be the context object's
michael@0: 	// start node."
michael@0: 	var parentNode;
michael@0: 	if (!referenceNode) {
michael@0: 		parentNode = range.startContainer;
michael@0: 	// "Otherwise, let parent node be the parent of reference node."
michael@0: 	} else {
michael@0: 		parentNode = referenceNode.parentNode;
michael@0: 	}
michael@0: 
michael@0: 	// "Call insertBefore(newNode, reference node) on parent node, re-raising
michael@0: 	// any exceptions that call raised."
michael@0: 	try {
michael@0: 		parentNode.insertBefore(newNode, referenceNode);
michael@0: 	} catch (e) {
michael@0: 		return getDomExceptionName(e);
michael@0: 	}
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Asserts that two nodes are equal, in the sense of isEqualNode().  If they
michael@0:  * aren't, tries to print a relatively informative reason why not.  TODO: Move
michael@0:  * this to testharness.js?
michael@0:  */
michael@0: function assertNodesEqual(actual, expected, msg) {
michael@0: 	if (!actual.isEqualNode(expected)) {
michael@0: 		msg = "Actual and expected mismatch for " + msg + ".  ";
michael@0: 
michael@0: 		while (actual && expected) {
michael@0: 			assert_true(actual.nodeType === expected.nodeType
michael@0: 				&& actual.nodeName === expected.nodeName
michael@0: 				&& actual.nodeValue === expected.nodeValue
michael@0: 				&& actual.childNodes.length === expected.childNodes.length,
michael@0: 				"First differing node: expected " + format_value(expected)
michael@0: 				+ ", got " + format_value(actual));
michael@0: 			actual = nextNode(actual);
michael@0: 			expected = nextNode(expected);
michael@0: 		}
michael@0: 
michael@0: 		assert_unreached("DOMs were not equal but we couldn't figure out why");
michael@0: 	}
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Given a DOMException, return the name (e.g., "HIERARCHY_REQUEST_ERR").  In
michael@0:  * theory this should be just e.name, but in practice it's not.  So I could
michael@0:  * legitimately just return e.name, but then every engine but WebKit would fail
michael@0:  * every test, since no one seems to care much for standardizing DOMExceptions.
michael@0:  * Instead I mangle it to account for browser bugs, so as not to fail
michael@0:  * insertNode() tests (for instance) for insertBefore() bugs.  Of course, a
michael@0:  * standards-compliant browser will work right in any event.
michael@0:  *
michael@0:  * If the exception has no string property called "name" or "message", we just
michael@0:  * re-throw it.
michael@0:  */
michael@0: function getDomExceptionName(e) {
michael@0: 	if (typeof e.name == "string"
michael@0: 	&& /^[A-Z_]+_ERR$/.test(e.name)) {
michael@0: 		// Either following the standard, or prefixing NS_ERROR_DOM (I'm
michael@0: 		// looking at you, Gecko).
michael@0: 		return e.name.replace(/^NS_ERROR_DOM_/, "");
michael@0: 	}
michael@0: 
michael@0: 	if (typeof e.message == "string"
michael@0: 	&& /^[A-Z_]+_ERR$/.test(e.message)) {
michael@0: 		// Opera
michael@0: 		return e.message;
michael@0: 	}
michael@0: 
michael@0: 	if (typeof e.message == "string"
michael@0: 	&& /^DOM Exception:/.test(e.message)) {
michael@0: 		// IE
michael@0: 		return /[A-Z_]+_ERR/.exec(e.message)[0];
michael@0: 	}
michael@0: 
michael@0: 	throw e;
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Given an array of endpoint data [start container, start offset, end
michael@0:  * container, end offset], returns a Range with those endpoints.
michael@0:  */
michael@0: function rangeFromEndpoints(endpoints) {
michael@0: 	// If we just use document instead of the ownerDocument of endpoints[0],
michael@0: 	// WebKit will throw on setStart/setEnd.  This is a WebKit bug, but it's in
michael@0: 	// range, not selection, so we don't want to fail anything for it.
michael@0: 	var range = ownerDocument(endpoints[0]).createRange();
michael@0: 	range.setStart(endpoints[0], endpoints[1]);
michael@0: 	range.setEnd(endpoints[2], endpoints[3]);
michael@0: 	return range;
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Given an array of endpoint data [start container, start offset, end
michael@0:  * container, end offset], sets the selection to have those endpoints.  Uses
michael@0:  * addRange, so the range will be forwards.  Accepts an empty array for
michael@0:  * endpoints, in which case the selection will just be emptied.
michael@0:  */
michael@0: function setSelectionForwards(endpoints) {
michael@0: 	selection.removeAllRanges();
michael@0: 	if (endpoints.length) {
michael@0: 		selection.addRange(rangeFromEndpoints(endpoints));
michael@0: 	}
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Given an array of endpoint data [start container, start offset, end
michael@0:  * container, end offset], sets the selection to have those endpoints, with the
michael@0:  * direction backwards.  Uses extend, so it will throw in IE.  Accepts an empty
michael@0:  * array for endpoints, in which case the selection will just be emptied.
michael@0:  */
michael@0: function setSelectionBackwards(endpoints) {
michael@0: 	selection.removeAllRanges();
michael@0: 	if (endpoints.length) {
michael@0: 		selection.collapse(endpoints[2], endpoints[3]);
michael@0: 		selection.extend(endpoints[0], endpoints[1]);
michael@0: 	}
michael@0: }