diff options
Diffstat (limited to 'test_tools/selenium/core/xpath')
-rw-r--r-- | test_tools/selenium/core/xpath/dom.js | 428 | ||||
-rw-r--r-- | test_tools/selenium/core/xpath/misc.js | 255 | ||||
-rw-r--r-- | test_tools/selenium/core/xpath/xpath.js | 2182 |
3 files changed, 0 insertions, 2865 deletions
diff --git a/test_tools/selenium/core/xpath/dom.js b/test_tools/selenium/core/xpath/dom.js deleted file mode 100644 index 85e0ab08..00000000 --- a/test_tools/selenium/core/xpath/dom.js +++ /dev/null @@ -1,428 +0,0 @@ -// Copyright 2005 Google Inc. -// All Rights Reserved -// -// An XML parse and a minimal DOM implementation that just supportes -// the subset of the W3C DOM that is used in the XSLT implementation. -// -// References: -// -// [DOM] W3C DOM Level 3 Core Specification -// <http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/>. -// -// -// Author: Steffen Meschkat <mesch@google.com> - -// NOTE: The split() method in IE omits empty result strings. This is -// utterly annoying. So we don't use it here. - -// Resolve entities in XML text fragments. According to the DOM -// specification, the DOM is supposed to resolve entity references at -// the API level. I.e. no entity references are passed through the -// API. See "Entities and the DOM core", p.12, DOM 2 Core -// Spec. However, different browsers actually pass very different -// values at the API. -// -function xmlResolveEntities(s) { - - var parts = stringSplit(s, '&'); - - var ret = parts[0]; - for (var i = 1; i < parts.length; ++i) { - var rp = stringSplit(parts[i], ';'); - if (rp.length == 1) { - // no entity reference: just a & but no ; - ret += parts[i]; - continue; - } - - var ch; - switch (rp[0]) { - case 'lt': - ch = '<'; - break; - case 'gt': - ch = '>'; - break; - case 'amp': - ch = '&'; - break; - case 'quot': - ch = '"'; - break; - case 'apos': - ch = '\''; - break; - case 'nbsp': - ch = String.fromCharCode(160); - break; - default: - // Cool trick: let the DOM do the entity decoding. We assign - // the entity text through non-W3C DOM properties and read it - // through the W3C DOM. W3C DOM access is specified to resolve - // entities. - var span = window.document.createElement('span'); - span.innerHTML = '&' + rp[0] + '; '; - ch = span.childNodes[0].nodeValue.charAt(0); - } - ret += ch + rp[1]; - } - - return ret; -} - - -// Parses the given XML string with our custom, JavaScript XML parser. Written -// by Steffen Meschkat (mesch@google.com). -function xmlParse(xml) { - Timer.start('xmlparse'); - var regex_empty = /\/$/; - - // See also <http://www.w3.org/TR/REC-xml/#sec-common-syn> for - // allowed chars in a tag and attribute name. TODO(mesch): the - // following is still not completely correct. - - var regex_tagname = /^([\w:-]*)/; - var regex_attribute = /([\w:-]+)\s?=\s?('([^\']*)'|"([^\"]*)")/g; - - var xmldoc = new XDocument(); - var root = xmldoc; - - // For the record: in Safari, we would create native DOM nodes, but - // in Opera that is not possible, because the DOM only allows HTML - // element nodes to be created, so we have to do our own DOM nodes. - - // xmldoc = document.implementation.createDocument('','',null); - // root = xmldoc; // .createDocumentFragment(); - // NOTE(mesch): using the DocumentFragment instead of the Document - // crashes my Safari 1.2.4 (v125.12). - var stack = []; - - var parent = root; - stack.push(parent); - - var x = stringSplit(xml, '<'); - for (var i = 1; i < x.length; ++i) { - var xx = stringSplit(x[i], '>'); - var tag = xx[0]; - var text = xmlResolveEntities(xx[1] || ''); - - if (tag.charAt(0) == '/') { - stack.pop(); - parent = stack[stack.length-1]; - - } else if (tag.charAt(0) == '?') { - // Ignore XML declaration and processing instructions - } else if (tag.charAt(0) == '!') { - // Ignore notation and comments - } else { - var empty = tag.match(regex_empty); - var tagname = regex_tagname.exec(tag)[1]; - var node = xmldoc.createElement(tagname); - - var att; - while (att = regex_attribute.exec(tag)) { - var val = xmlResolveEntities(att[3] || att[4] || ''); - node.setAttribute(att[1], val); - } - - if (empty) { - parent.appendChild(node); - } else { - parent.appendChild(node); - parent = node; - stack.push(node); - } - } - - if (text && parent != root) { - parent.appendChild(xmldoc.createTextNode(text)); - } - } - - Timer.end('xmlparse'); - return root; -} - - -// Our W3C DOM Node implementation. Note we call it XNode because we -// can't define the identifier Node. We do this mostly for Opera, -// where we can't reuse the HTML DOM for parsing our own XML, and for -// Safari, where it is too expensive to have the template processor -// operate on native DOM nodes. -function XNode(type, name, value, owner) { - this.attributes = []; - this.childNodes = []; - - XNode.init.call(this, type, name, value, owner); -} - -// Don't call as method, use apply() or call(). -XNode.init = function(type, name, value, owner) { - this.nodeType = type - 0; - this.nodeName = '' + name; - this.nodeValue = '' + value; - this.ownerDocument = owner; - - this.firstChild = null; - this.lastChild = null; - this.nextSibling = null; - this.previousSibling = null; - this.parentNode = null; -} - -XNode.unused_ = []; - -XNode.recycle = function(node) { - if (!node) { - return; - } - - if (node.constructor == XDocument) { - XNode.recycle(node.documentElement); - return; - } - - if (node.constructor != this) { - return; - } - - XNode.unused_.push(node); - for (var a = 0; a < node.attributes.length; ++a) { - XNode.recycle(node.attributes[a]); - } - for (var c = 0; c < node.childNodes.length; ++c) { - XNode.recycle(node.childNodes[c]); - } - node.attributes.length = 0; - node.childNodes.length = 0; - XNode.init.call(node, 0, '', '', null); -} - -XNode.create = function(type, name, value, owner) { - if (XNode.unused_.length > 0) { - var node = XNode.unused_.pop(); - XNode.init.call(node, type, name, value, owner); - return node; - } else { - return new XNode(type, name, value, owner); - } -} - -XNode.prototype.appendChild = function(node) { - // firstChild - if (this.childNodes.length == 0) { - this.firstChild = node; - } - - // previousSibling - node.previousSibling = this.lastChild; - - // nextSibling - node.nextSibling = null; - if (this.lastChild) { - this.lastChild.nextSibling = node; - } - - // parentNode - node.parentNode = this; - - // lastChild - this.lastChild = node; - - // childNodes - this.childNodes.push(node); -} - - -XNode.prototype.replaceChild = function(newNode, oldNode) { - if (oldNode == newNode) { - return; - } - - for (var i = 0; i < this.childNodes.length; ++i) { - if (this.childNodes[i] == oldNode) { - this.childNodes[i] = newNode; - - var p = oldNode.parentNode; - oldNode.parentNode = null; - newNode.parentNode = p; - - p = oldNode.previousSibling; - oldNode.previousSibling = null; - newNode.previousSibling = p; - if (newNode.previousSibling) { - newNode.previousSibling.nextSibling = newNode; - } - - p = oldNode.nextSibling; - oldNode.nextSibling = null; - newNode.nextSibling = p; - if (newNode.nextSibling) { - newNode.nextSibling.previousSibling = newNode; - } - - if (this.firstChild == oldNode) { - this.firstChild = newNode; - } - - if (this.lastChild == oldNode) { - this.lastChild = newNode; - } - - break; - } - } -} - -XNode.prototype.insertBefore = function(newNode, oldNode) { - if (oldNode == newNode) { - return; - } - - if (oldNode.parentNode != this) { - return; - } - - if (newNode.parentNode) { - newNode.parentNode.removeChild(newNode); - } - - var newChildren = []; - for (var i = 0; i < this.childNodes.length; ++i) { - var c = this.childNodes[i]; - if (c == oldNode) { - newChildren.push(newNode); - - newNode.parentNode = this; - - newNode.previousSibling = oldNode.previousSibling; - oldNode.previousSibling = newNode; - if (newNode.previousSibling) { - newNode.previousSibling.nextSibling = newNode; - } - - newNode.nextSibling = oldNode; - - if (this.firstChild == oldNode) { - this.firstChild = newNode; - } - } - newChildren.push(c); - } - this.childNodes = newChildren; -} - -XNode.prototype.removeChild = function(node) { - var newChildren = []; - for (var i = 0; i < this.childNodes.length; ++i) { - var c = this.childNodes[i]; - if (c != node) { - newChildren.push(c); - } else { - if (c.previousSibling) { - c.previousSibling.nextSibling = c.nextSibling; - } - if (c.nextSibling) { - c.nextSibling.previousSibling = c.previousSibling; - } - if (this.firstChild == c) { - this.firstChild = c.nextSibling; - } - if (this.lastChild == c) { - this.lastChild = c.previousSibling; - } - } - } - this.childNodes = newChildren; -} - - -XNode.prototype.hasAttributes = function() { - return this.attributes.length > 0; -} - - -XNode.prototype.setAttribute = function(name, value) { - for (var i = 0; i < this.attributes.length; ++i) { - if (this.attributes[i].nodeName == name) { - this.attributes[i].nodeValue = '' + value; - return; - } - } - this.attributes.push(new XNode(DOM_ATTRIBUTE_NODE, name, value)); -} - - -XNode.prototype.getAttribute = function(name) { - for (var i = 0; i < this.attributes.length; ++i) { - if (this.attributes[i].nodeName == name) { - return this.attributes[i].nodeValue; - } - } - return null; -} - -XNode.prototype.removeAttribute = function(name) { - var a = []; - for (var i = 0; i < this.attributes.length; ++i) { - if (this.attributes[i].nodeName != name) { - a.push(this.attributes[i]); - } - } - this.attributes = a; -} - - -function XDocument() { - XNode.call(this, DOM_DOCUMENT_NODE, '#document', null, this); - this.documentElement = null; -} - -XDocument.prototype = new XNode(DOM_DOCUMENT_NODE, '#document'); - -XDocument.prototype.clear = function() { - XNode.recycle(this.documentElement); - this.documentElement = null; -} - -XDocument.prototype.appendChild = function(node) { - XNode.prototype.appendChild.call(this, node); - this.documentElement = this.childNodes[0]; -} - -XDocument.prototype.createElement = function(name) { - return XNode.create(DOM_ELEMENT_NODE, name, null, this); -} - -XDocument.prototype.createDocumentFragment = function() { - return XNode.create(DOM_DOCUMENT_FRAGMENT_NODE, '#document-fragment', - null, this); -} - -XDocument.prototype.createTextNode = function(value) { - return XNode.create(DOM_TEXT_NODE, '#text', value, this); -} - -XDocument.prototype.createAttribute = function(name) { - return XNode.create(DOM_ATTRIBUTE_NODE, name, null, this); -} - -XDocument.prototype.createComment = function(data) { - return XNode.create(DOM_COMMENT_NODE, '#comment', data, this); -} - -XNode.prototype.getElementsByTagName = function(name, list) { - if (!list) { - list = []; - } - - if (this.nodeName == name) { - list.push(this); - } - - for (var i = 0; i < this.childNodes.length; ++i) { - this.childNodes[i].getElementsByTagName(name, list); - } - - return list; -} diff --git a/test_tools/selenium/core/xpath/misc.js b/test_tools/selenium/core/xpath/misc.js deleted file mode 100644 index b9573a22..00000000 --- a/test_tools/selenium/core/xpath/misc.js +++ /dev/null @@ -1,255 +0,0 @@ -// Copyright 2005 Google Inc. -// All Rights Reserved -// -// Miscellania that support the ajaxslt implementation. -// -// Author: Steffen Meschkat <mesch@google.com> -// - -function el(i) { - return document.getElementById(i); -} - -function px(x) { - return x + 'px'; -} - -// Split a string s at all occurrences of character c. This is like -// the split() method of the string object, but IE omits empty -// strings, which violates the invariant (s.split(x).join(x) == s). -function stringSplit(s, c) { - var a = s.indexOf(c); - if (a == -1) { - return [ s ]; - } - - var parts = []; - parts.push(s.substr(0,a)); - while (a != -1) { - var a1 = s.indexOf(c, a + 1); - if (a1 != -1) { - parts.push(s.substr(a + 1, a1 - a - 1)); - } else { - parts.push(s.substr(a + 1)); - } - a = a1; - } - - return parts; -} - -// Returns the text value if a node; for nodes without children this -// is the nodeValue, for nodes with children this is the concatenation -// of the value of all children. -function xmlValue(node) { - if (!node) { - return ''; - } - - var ret = ''; - if (node.nodeType == DOM_TEXT_NODE || - node.nodeType == DOM_CDATA_SECTION_NODE || - node.nodeType == DOM_ATTRIBUTE_NODE) { - ret += node.nodeValue; - - } else if (node.nodeType == DOM_ELEMENT_NODE || - node.nodeType == DOM_DOCUMENT_NODE || - node.nodeType == DOM_DOCUMENT_FRAGMENT_NODE) { - for (var i = 0; i < node.childNodes.length; ++i) { - ret += arguments.callee(node.childNodes[i]); - } - } - return ret; -} - -// Returns the representation of a node as XML text. -function xmlText(node) { - var ret = ''; - if (node.nodeType == DOM_TEXT_NODE) { - ret += xmlEscapeText(node.nodeValue); - - } else if (node.nodeType == DOM_ELEMENT_NODE) { - ret += '<' + node.nodeName; - for (var i = 0; i < node.attributes.length; ++i) { - var a = node.attributes[i]; - if (a && a.nodeName && a.nodeValue) { - ret += ' ' + a.nodeName; - ret += '="' + xmlEscapeAttr(a.nodeValue) + '"'; - } - } - - if (node.childNodes.length == 0) { - ret += '/>'; - - } else { - ret += '>'; - for (var i = 0; i < node.childNodes.length; ++i) { - ret += arguments.callee(node.childNodes[i]); - } - ret += '</' + node.nodeName + '>'; - } - - } else if (node.nodeType == DOM_DOCUMENT_NODE || - node.nodeType == DOM_DOCUMENT_FRAGMENT_NODE) { - for (var i = 0; i < node.childNodes.length; ++i) { - ret += arguments.callee(node.childNodes[i]); - } - } - - return ret; -} - -// Applies the given function to each element of the array. -function mapExec(array, func) { - for (var i = 0; i < array.length; ++i) { - func(array[i]); - } -} - -// Returns an array that contains the return value of the given -// function applied to every element of the input array. -function mapExpr(array, func) { - var ret = []; - for (var i = 0; i < array.length; ++i) { - ret.push(func(array[i])); - } - return ret; -}; - -// Reverses the given array in place. -function reverseInplace(array) { - for (var i = 0; i < array.length / 2; ++i) { - var h = array[i]; - var ii = array.length - i - 1; - array[i] = array[ii]; - array[ii] = h; - } -} - -// Shallow-copies an array. -function copyArray(dst, src) { - for (var i = 0; i < src.length; ++i) { - dst.push(src[i]); - } -} - -function assert(b) { - if (!b) { - throw 'assertion failed'; - } -} - -// Based on -// <http://www.w3.org/TR/2000/REC-DOM-Level-2-Core-20001113/core.html#ID-1950641247> -var DOM_ELEMENT_NODE = 1; -var DOM_ATTRIBUTE_NODE = 2; -var DOM_TEXT_NODE = 3; -var DOM_CDATA_SECTION_NODE = 4; -var DOM_ENTITY_REFERENCE_NODE = 5; -var DOM_ENTITY_NODE = 6; -var DOM_PROCESSING_INSTRUCTION_NODE = 7; -var DOM_COMMENT_NODE = 8; -var DOM_DOCUMENT_NODE = 9; -var DOM_DOCUMENT_TYPE_NODE = 10; -var DOM_DOCUMENT_FRAGMENT_NODE = 11; -var DOM_NOTATION_NODE = 12; - - -var xpathdebug = false; // trace xpath parsing -var xsltdebug = false; // trace xslt processing - - -// Escape XML special markup chracters: tag delimiter < > and entity -// reference start delimiter &. The escaped string can be used in XML -// text portions (i.e. between tags). -function xmlEscapeText(s) { - return s.replace(/&/g, '&').replace(/</g, '<').replace(/>/g, '>'); -} - -// Escape XML special markup characters: tag delimiter < > entity -// reference start delimiter & and quotes ". The escaped string can be -// used in double quoted XML attribute value portions (i.e. in -// attributes within start tags). -function xmlEscapeAttr(s) { - return xmlEscapeText(s).replace(/\"/g, '"'); -} - -// Escape markup in XML text, but don't touch entity references. The -// escaped string can be used as XML text (i.e. between tags). -function xmlEscapeTags(s) { - return s.replace(/</g, '<').replace(/>/g, '>'); -} - -// An implementation of the debug log. - -var logging__ = false; - -function Log() {}; - -Log.lines = []; - -Log.write = function(s) { - if (logging__) { - this.lines.push(xmlEscapeText(s)); - this.show(); - } -}; - -// Writes the given XML with every tag on a new line. -Log.writeXML = function(xml) { - if (logging__) { - var s0 = xml.replace(/</g, '\n<'); - var s1 = xmlEscapeText(s0); - var s2 = s1.replace(/\s*\n(\s|\n)*/g, '<br/>'); - this.lines.push(s2); - this.show(); - } -} - -// Writes without any escaping -Log.writeRaw = function(s) { - if (logging__) { - this.lines.push(s); - this.show(); - } -} - -Log.clear = function() { - if (logging__) { - var l = this.div(); - l.innerHTML = ''; - this.lines = []; - } -} - -Log.show = function() { - var l = this.div(); - l.innerHTML += this.lines.join('<br/>') + '<br/>'; - this.lines = []; - l.scrollTop = l.scrollHeight; -} - -Log.div = function() { - var l = document.getElementById('log'); - if (!l) { - l = document.createElement('div'); - l.id = 'log'; - l.style.position = 'absolute'; - l.style.right = '5px'; - l.style.top = '5px'; - l.style.width = '250px'; - l.style.height = '150px'; - l.style.overflow = 'auto'; - l.style.backgroundColor = '#f0f0f0'; - l.style.border = '1px solid gray'; - l.style.fontSize = '10px'; - l.style.padding = '5px'; - document.body.appendChild(l); - } - return l; -} - - -function Timer() {} -Timer.start = function() {} -Timer.end = function() {} diff --git a/test_tools/selenium/core/xpath/xpath.js b/test_tools/selenium/core/xpath/xpath.js deleted file mode 100644 index b93469f2..00000000 --- a/test_tools/selenium/core/xpath/xpath.js +++ /dev/null @@ -1,2182 +0,0 @@ -// Copyright 2005 Google Inc. -// All Rights Reserved -// -// An XPath parser and evaluator written in JavaScript. The -// implementation is complete except for functions handling -// namespaces. -// -// Reference: [XPATH] XPath Specification -// <http://www.w3.org/TR/1999/REC-xpath-19991116>. -// -// -// The API of the parser has several parts: -// -// 1. The parser function xpathParse() that takes a string and returns -// an expession object. -// -// 2. The expression object that has an evaluate() method to evaluate the -// XPath expression it represents. (It is actually a hierarchy of -// objects that resembles the parse tree, but an application will call -// evaluate() only on the top node of this hierarchy.) -// -// 3. The context object that is passed as an argument to the evaluate() -// method, which represents the DOM context in which the expression is -// evaluated. -// -// 4. The value object that is returned from evaluate() and represents -// values of the different types that are defined by XPath (number, -// string, boolean, and node-set), and allows to convert between them. -// -// These parts are near the top of the file, the functions and data -// that are used internally follow after them. -// -// -// TODO(mesch): add jsdoc comments. Use more coherent naming. -// -// -// Author: Steffen Meschkat <mesch@google.com> - - -// The entry point for the parser. -// -// @param expr a string that contains an XPath expression. -// @return an expression object that can be evaluated with an -// expression context. - -function xpathParse(expr) { - if (xpathdebug) { - Log.write('XPath parse ' + expr); - } - xpathParseInit(); - - var cached = xpathCacheLookup(expr); - if (cached) { - if (xpathdebug) { - Log.write(' ... cached'); - } - return cached; - } - - // Optimize for a few common cases: simple attribute node tests - // (@id), simple element node tests (page), variable references - // ($address), numbers (4), multi-step path expressions where each - // step is a plain element node test - // (page/overlay/locations/location). - - if (expr.match(/^(\$|@)?\w+$/i)) { - var ret = makeSimpleExpr(expr); - xpathParseCache[expr] = ret; - if (xpathdebug) { - Log.write(' ... simple'); - } - return ret; - } - - if (expr.match(/^\w+(\/\w+)*$/i)) { - var ret = makeSimpleExpr2(expr); - xpathParseCache[expr] = ret; - if (xpathdebug) { - Log.write(' ... simple 2'); - } - return ret; - } - - var cachekey = expr; // expr is modified during parse - if (xpathdebug) { - Timer.start('XPath parse', cachekey); - } - - var stack = []; - var ahead = null; - var previous = null; - var done = false; - - var parse_count = 0; - var lexer_count = 0; - var reduce_count = 0; - - while (!done) { - parse_count++; - expr = expr.replace(/^\s*/, ''); - previous = ahead; - ahead = null; - - var rule = null; - var match = ''; - for (var i = 0; i < xpathTokenRules.length; ++i) { - var result = xpathTokenRules[i].re.exec(expr); - lexer_count++; - if (result && result.length > 0 && result[0].length > match.length) { - rule = xpathTokenRules[i]; - match = result[0]; - break; - } - } - - // Special case: allow operator keywords to be element and - // variable names. - - // NOTE(mesch): The parser resolves conflicts by looking ahead, - // and this is the only case where we look back to - // disambiguate. So this is indeed something different, and - // looking back is usually done in the lexer (via states in the - // general case, called "start conditions" in flex(1)). Also,the - // conflict resolution in the parser is not as robust as it could - // be, so I'd like to keep as much off the parser as possible (all - // these precedence values should be computed from the grammar - // rules and possibly associativity declarations, as in bison(1), - // and not explicitly set. - - if (rule && - (rule == TOK_DIV || - rule == TOK_MOD || - rule == TOK_AND || - rule == TOK_OR) && - (!previous || - previous.tag == TOK_AT || - previous.tag == TOK_DSLASH || - previous.tag == TOK_SLASH || - previous.tag == TOK_AXIS || - previous.tag == TOK_DOLLAR)) { - rule = TOK_QNAME; - } - - if (rule) { - expr = expr.substr(match.length); - if (xpathdebug) { - Log.write('token: ' + match + ' -- ' + rule.label); - } - ahead = { - tag: rule, - match: match, - prec: rule.prec ? rule.prec : 0, // || 0 is removed by the compiler - expr: makeTokenExpr(match) - }; - - } else { - if (xpathdebug) { - Log.write('DONE'); - } - done = true; - } - - while (xpathReduce(stack, ahead)) { - reduce_count++; - if (xpathdebug) { - Log.write('stack: ' + stackToString(stack)); - } - } - } - - if (xpathdebug) { - Log.write(stackToString(stack)); - } - - if (stack.length != 1) { - throw 'XPath parse error ' + cachekey + ':\n' + stackToString(stack); - } - - var result = stack[0].expr; - xpathParseCache[cachekey] = result; - - if (xpathdebug) { - Timer.end('XPath parse', cachekey); - } - - if (xpathdebug) { - Log.write('XPath parse: ' + parse_count + ' / ' + - lexer_count + ' / ' + reduce_count); - } - - return result; -} - -var xpathParseCache = {}; - -function xpathCacheLookup(expr) { - return xpathParseCache[expr]; -} - -function xpathReduce(stack, ahead) { - var cand = null; - - if (stack.length > 0) { - var top = stack[stack.length-1]; - var ruleset = xpathRules[top.tag.key]; - - if (ruleset) { - for (var i = 0; i < ruleset.length; ++i) { - var rule = ruleset[i]; - var match = xpathMatchStack(stack, rule[1]); - if (match.length) { - cand = { - tag: rule[0], - rule: rule, - match: match - }; - cand.prec = xpathGrammarPrecedence(cand); - break; - } - } - } - } - - var ret; - if (cand && (!ahead || cand.prec > ahead.prec || - (ahead.tag.left && cand.prec >= ahead.prec))) { - for (var i = 0; i < cand.match.matchlength; ++i) { - stack.pop(); - } - - if (xpathdebug) { - Log.write('reduce ' + cand.tag.label + ' ' + cand.prec + - ' ahead ' + (ahead ? ahead.tag.label + ' ' + ahead.prec + - (ahead.tag.left ? ' left' : '') - : ' none ')); - } - - var matchexpr = mapExpr(cand.match, function(m) { return m.expr; }); - cand.expr = cand.rule[3].apply(null, matchexpr); - - stack.push(cand); - ret = true; - - } else { - if (ahead) { - if (xpathdebug) { - Log.write('shift ' + ahead.tag.label + ' ' + ahead.prec + - (ahead.tag.left ? ' left' : '') + - ' over ' + (cand ? cand.tag.label + ' ' + - cand.prec : ' none')); - } - stack.push(ahead); - } - ret = false; - } - return ret; -} - -function xpathMatchStack(stack, pattern) { - - // NOTE(mesch): The stack matches for variable cardinality are - // greedy but don't do backtracking. This would be an issue only - // with rules of the form A* A, i.e. with an element with variable - // cardinality followed by the same element. Since that doesn't - // occur in the grammar at hand, all matches on the stack are - // unambiguous. - - var S = stack.length; - var P = pattern.length; - var p, s; - var match = []; - match.matchlength = 0; - var ds = 0; - for (p = P - 1, s = S - 1; p >= 0 && s >= 0; --p, s -= ds) { - ds = 0; - var qmatch = []; - if (pattern[p] == Q_MM) { - p -= 1; - match.push(qmatch); - while (s - ds >= 0 && stack[s - ds].tag == pattern[p]) { - qmatch.push(stack[s - ds]); - ds += 1; - match.matchlength += 1; - } - - } else if (pattern[p] == Q_01) { - p -= 1; - match.push(qmatch); - while (s - ds >= 0 && ds < 2 && stack[s - ds].tag == pattern[p]) { - qmatch.push(stack[s - ds]); - ds += 1; - match.matchlength += 1; - } - - } else if (pattern[p] == Q_1M) { - p -= 1; - match.push(qmatch); - if (stack[s].tag == pattern[p]) { - while (s - ds >= 0 && stack[s - ds].tag == pattern[p]) { - qmatch.push(stack[s - ds]); - ds += 1; - match.matchlength += 1; - } - } else { - return []; - } - - } else if (stack[s].tag == pattern[p]) { - match.push(stack[s]); - ds += 1; - match.matchlength += 1; - - } else { - return []; - } - - reverseInplace(qmatch); - qmatch.expr = mapExpr(qmatch, function(m) { return m.expr; }); - } - - reverseInplace(match); - - if (p == -1) { - return match; - - } else { - return []; - } -} - -function xpathTokenPrecedence(tag) { - return tag.prec || 2; -} - -function xpathGrammarPrecedence(frame) { - var ret = 0; - - if (frame.rule) { /* normal reduce */ - if (frame.rule.length >= 3 && frame.rule[2] >= 0) { - ret = frame.rule[2]; - - } else { - for (var i = 0; i < frame.rule[1].length; ++i) { - var p = xpathTokenPrecedence(frame.rule[1][i]); - ret = Math.max(ret, p); - } - } - } else if (frame.tag) { /* TOKEN match */ - ret = xpathTokenPrecedence(frame.tag); - - } else if (frame.length) { /* Q_ match */ - for (var j = 0; j < frame.length; ++j) { - var p = xpathGrammarPrecedence(frame[j]); - ret = Math.max(ret, p); - } - } - - return ret; -} - -function stackToString(stack) { - var ret = ''; - for (var i = 0; i < stack.length; ++i) { - if (ret) { - ret += '\n'; - } - ret += stack[i].tag.label; - } - return ret; -} - - -// XPath expression evaluation context. An XPath context consists of a -// DOM node, a list of DOM nodes that contains this node, a number -// that represents the position of the single node in the list, and a -// current set of variable bindings. (See XPath spec.) -// -// The interface of the expression context: -// -// Constructor -- gets the node, its position, the node set it -// belongs to, and a parent context as arguments. The parent context -// is used to implement scoping rules for variables: if a variable -// is not found in the current context, it is looked for in the -// parent context, recursively. Except for node, all arguments have -// default values: default position is 0, default node set is the -// set that contains only the node, and the default parent is null. -// -// Notice that position starts at 0 at the outside interface; -// inside XPath expressions this shows up as position()=1. -// -// clone() -- creates a new context with the current context as -// parent. If passed as argument to clone(), the new context has a -// different node, position, or node set. What is not passed is -// inherited from the cloned context. -// -// setVariable(name, expr) -- binds given XPath expression to the -// name. -// -// getVariable(name) -- what the name says. -// -// setNode(node, position) -- sets the context to the new node and -// its corresponding position. Needed to implement scoping rules for -// variables in XPath. (A variable is visible to all subsequent -// siblings, not only to its children.) - -function ExprContext(node, position, nodelist, parent) { - this.node = node; - this.position = position || 0; - this.nodelist = nodelist || [ node ]; - this.variables = {}; - this.parent = parent || null; - this.root = parent ? parent.root : node.ownerDocument; -} - -ExprContext.prototype.clone = function(node, position, nodelist) { - return new - ExprContext(node || this.node, - typeof position != 'undefined' ? position : this.position, - nodelist || this.nodelist, this); -}; - -ExprContext.prototype.setVariable = function(name, value) { - this.variables[name] = value; -}; - -ExprContext.prototype.getVariable = function(name) { - if (typeof this.variables[name] != 'undefined') { - return this.variables[name]; - - } else if (this.parent) { - return this.parent.getVariable(name); - - } else { - return null; - } -} - -ExprContext.prototype.setNode = function(node, position) { - this.node = node; - this.position = position; -} - - -// XPath expression values. They are what XPath expressions evaluate -// to. Strangely, the different value types are not specified in the -// XPath syntax, but only in the semantics, so they don't show up as -// nonterminals in the grammar. Yet, some expressions are required to -// evaluate to particular types, and not every type can be coerced -// into every other type. Although the types of XPath values are -// similar to the types present in JavaScript, the type coercion rules -// are a bit peculiar, so we explicitly model XPath types instead of -// mapping them onto JavaScript types. (See XPath spec.) -// -// The four types are: -// -// StringValue -// -// NumberValue -// -// BooleanValue -// -// NodeSetValue -// -// The common interface of the value classes consists of methods that -// implement the XPath type coercion rules: -// -// stringValue() -- returns the value as a JavaScript String, -// -// numberValue() -- returns the value as a JavaScript Number, -// -// booleanValue() -- returns the value as a JavaScript Boolean, -// -// nodeSetValue() -- returns the value as a JavaScript Array of DOM -// Node objects. -// - -function StringValue(value) { - this.value = value; - this.type = 'string'; -} - -StringValue.prototype.stringValue = function() { - return this.value; -} - -StringValue.prototype.booleanValue = function() { - return this.value.length > 0; -} - -StringValue.prototype.numberValue = function() { - return this.value - 0; -} - -StringValue.prototype.nodeSetValue = function() { - throw this + ' ' + Error().stack; -} - -function BooleanValue(value) { - this.value = value; - this.type = 'boolean'; -} - -BooleanValue.prototype.stringValue = function() { - return '' + this.value; -} - -BooleanValue.prototype.booleanValue = function() { - return this.value; -} - -BooleanValue.prototype.numberValue = function() { - return this.value ? 1 : 0; -} - -BooleanValue.prototype.nodeSetValue = function() { - throw this + ' ' + Error().stack; -} - -function NumberValue(value) { - this.value = value; - this.type = 'number'; -} - -NumberValue.prototype.stringValue = function() { - return '' + this.value; -} - -NumberValue.prototype.booleanValue = function() { - return !!this.value; -} - -NumberValue.prototype.numberValue = function() { - return this.value - 0; -} - -NumberValue.prototype.nodeSetValue = function() { - throw this + ' ' + Error().stack; -} - -function NodeSetValue(value) { - this.value = value; - this.type = 'node-set'; -} - -NodeSetValue.prototype.stringValue = function() { - if (this.value.length == 0) { - return ''; - } else { - return xmlValue(this.value[0]); - } -} - -NodeSetValue.prototype.booleanValue = function() { - return this.value.length > 0; -} - -NodeSetValue.prototype.numberValue = function() { - return this.stringValue() - 0; -} - -NodeSetValue.prototype.nodeSetValue = function() { - return this.value; -}; - -// XPath expressions. They are used as nodes in the parse tree and -// possess an evaluate() method to compute an XPath value given an XPath -// context. Expressions are returned from the parser. Teh set of -// expression classes closely mirrors the set of non terminal symbols -// in the grammar. Every non trivial nonterminal symbol has a -// corresponding expression class. -// -// The common expression interface consists of the following methods: -// -// evaluate(context) -- evaluates the expression, returns a value. -// -// toString() -- returns the XPath text representation of the -// expression (defined in xsltdebug.js). -// -// parseTree(indent) -- returns a parse tree representation of the -// expression (defined in xsltdebug.js). - -function TokenExpr(m) { - this.value = m; -} - -TokenExpr.prototype.evaluate = function() { - return new StringValue(this.value); -}; - -function LocationExpr() { - this.absolute = false; - this.steps = []; -} - -LocationExpr.prototype.appendStep = function(s) { - this.steps.push(s); -} - -LocationExpr.prototype.prependStep = function(s) { - var steps0 = this.steps; - this.steps = [ s ]; - for (var i = 0; i < steps0.length; ++i) { - this.steps.push(steps0[i]); - } -}; - -LocationExpr.prototype.evaluate = function(ctx) { - var start; - if (this.absolute) { - start = ctx.root; - - } else { - start = ctx.node; - } - - var nodes = []; - xPathStep(nodes, this.steps, 0, start, ctx); - return new NodeSetValue(nodes); -}; - -function xPathStep(nodes, steps, step, input, ctx) { - var s = steps[step]; - var ctx2 = ctx.clone(input); - var nodelist = s.evaluate(ctx2).nodeSetValue(); - - for (var i = 0; i < nodelist.length; ++i) { - if (step == steps.length - 1) { - nodes.push(nodelist[i]); - } else { - xPathStep(nodes, steps, step + 1, nodelist[i], ctx); - } - } -} - -function StepExpr(axis, nodetest, predicate) { - this.axis = axis; - this.nodetest = nodetest; - this.predicate = predicate || []; -} - -StepExpr.prototype.appendPredicate = function(p) { - this.predicate.push(p); -} - -StepExpr.prototype.evaluate = function(ctx) { - var input = ctx.node; - var nodelist = []; - - // NOTE(mesch): When this was a switch() statement, it didn't work - // in Safari/2.0. Not sure why though; it resulted in the JavaScript - // console output "undefined" (without any line number or so). - - if (this.axis == xpathAxis.ANCESTOR_OR_SELF) { - nodelist.push(input); - for (var n = input.parentNode; n; n = input.parentNode) { - nodelist.push(n); - } - - } else if (this.axis == xpathAxis.ANCESTOR) { - for (var n = input.parentNode; n; n = input.parentNode) { - nodelist.push(n); - } - - } else if (this.axis == xpathAxis.ATTRIBUTE) { - copyArray(nodelist, input.attributes); - - } else if (this.axis == xpathAxis.CHILD) { - copyArray(nodelist, input.childNodes); - - } else if (this.axis == xpathAxis.DESCENDANT_OR_SELF) { - nodelist.push(input); - xpathCollectDescendants(nodelist, input); - - } else if (this.axis == xpathAxis.DESCENDANT) { - xpathCollectDescendants(nodelist, input); - - } else if (this.axis == xpathAxis.FOLLOWING) { - for (var n = input.parentNode; n; n = n.parentNode) { - for (var nn = n.nextSibling; nn; nn = nn.nextSibling) { - nodelist.push(nn); - xpathCollectDescendants(nodelist, nn); - } - } - - } else if (this.axis == xpathAxis.FOLLOWING_SIBLING) { - for (var n = input.nextSibling; n; n = input.nextSibling) { - nodelist.push(n); - } - - } else if (this.axis == xpathAxis.NAMESPACE) { - alert('not implemented: axis namespace'); - - } else if (this.axis == xpathAxis.PARENT) { - if (input.parentNode) { - nodelist.push(input.parentNode); - } - - } else if (this.axis == xpathAxis.PRECEDING) { - for (var n = input.parentNode; n; n = n.parentNode) { - for (var nn = n.previousSibling; nn; nn = nn.previousSibling) { - nodelist.push(nn); - xpathCollectDescendantsReverse(nodelist, nn); - } - } - - } else if (this.axis == xpathAxis.PRECEDING_SIBLING) { - for (var n = input.previousSibling; n; n = input.previousSibling) { - nodelist.push(n); - } - - } else if (this.axis == xpathAxis.SELF) { - nodelist.push(input); - - } else { - throw 'ERROR -- NO SUCH AXIS: ' + this.axis; - } - - // process node test - var nodelist0 = nodelist; - nodelist = []; - for (var i = 0; i < nodelist0.length; ++i) { - var n = nodelist0[i]; - if (this.nodetest.evaluate(ctx.clone(n, i, nodelist0)).booleanValue()) { - nodelist.push(n); - } - } - - // process predicates - for (var i = 0; i < this.predicate.length; ++i) { - var nodelist0 = nodelist; - nodelist = []; - for (var ii = 0; ii < nodelist0.length; ++ii) { - var n = nodelist0[ii]; - if (this.predicate[i].evaluate(ctx.clone(n, ii, nodelist0)).booleanValue()) { - nodelist.push(n); - } - } - } - - return new NodeSetValue(nodelist); -}; - -function NodeTestAny() { - this.value = new BooleanValue(true); -} - -NodeTestAny.prototype.evaluate = function(ctx) { - return this.value; -}; - -function NodeTestElement() {} - -NodeTestElement.prototype.evaluate = function(ctx) { - return new BooleanValue(ctx.node.nodeType == DOM_ELEMENT_NODE); -} - -function NodeTestText() {} - -NodeTestText.prototype.evaluate = function(ctx) { - return new BooleanValue(ctx.node.nodeType == DOM_TEXT_NODE); -} - -function NodeTestComment() {} - -NodeTestComment.prototype.evaluate = function(ctx) { - return new BooleanValue(ctx.node.nodeType == DOM_COMMENT_NODE); -} - -function NodeTestPI(target) { - this.target = target; -} - -NodeTestPI.prototype.evaluate = function(ctx) { - return new - BooleanValue(ctx.node.nodeType == DOM_PROCESSING_INSTRUCTION_NODE && - (!this.target || ctx.node.nodeName == this.target)); -} - -function NodeTestNC(nsprefix) { - this.regex = new RegExp("^" + nsprefix + ":"); - this.nsprefix = nsprefix; -} - -NodeTestNC.prototype.evaluate = function(ctx) { - var n = ctx.node; - return new BooleanValue(this.regex.match(n.nodeName)); -} - -function NodeTestName(name) { - this.name = name; -} - -NodeTestName.prototype.evaluate = function(ctx) { - var n = ctx.node; - // NOTE (Patrick Lightbody): this change allows node selection to be case-insensitive - return new BooleanValue(n.nodeName.toUpperCase() == this.name.toUpperCase()); -} - -function PredicateExpr(expr) { - this.expr = expr; -} - -PredicateExpr.prototype.evaluate = function(ctx) { - var v = this.expr.evaluate(ctx); - if (v.type == 'number') { - // NOTE(mesch): Internally, position is represented starting with - // 0, however in XPath position starts with 1. See functions - // position() and last(). - return new BooleanValue(ctx.position == v.numberValue() - 1); - } else { - return new BooleanValue(v.booleanValue()); - } -}; - -function FunctionCallExpr(name) { - this.name = name; - this.args = []; -} - -FunctionCallExpr.prototype.appendArg = function(arg) { - this.args.push(arg); -}; - -FunctionCallExpr.prototype.evaluate = function(ctx) { - var fn = '' + this.name.value; - var f = this.xpathfunctions[fn]; - if (f) { - return f.call(this, ctx); - } else { - Log.write('XPath NO SUCH FUNCTION ' + fn); - return new BooleanValue(false); - } -}; - -FunctionCallExpr.prototype.xpathfunctions = { - 'last': function(ctx) { - assert(this.args.length == 0); - // NOTE(mesch): XPath position starts at 1. - return new NumberValue(ctx.nodelist.length); - }, - - 'position': function(ctx) { - assert(this.args.length == 0); - // NOTE(mesch): XPath position starts at 1. - return new NumberValue(ctx.position + 1); - }, - - 'count': function(ctx) { - assert(this.args.length == 1); - var v = this.args[0].evaluate(ctx); - return new NumberValue(v.nodeSetValue().length); - }, - - 'id': function(ctx) { - assert(this.args.length == 1); - var e = this.args.evaluate(ctx); - var ret = []; - var ids; - if (e.type == 'node-set') { - ids = []; - for (var i = 0; i < e.length; ++i) { - var v = xmlValue(e[i]).split(/\s+/); - for (var ii = 0; ii < v.length; ++ii) { - ids.push(v[ii]); - } - } - } else { - ids = e.split(/\s+/); - } - var d = ctx.node.ownerDocument; - for (var i = 0; i < ids.length; ++i) { - var n = d.getElementById(ids[i]); - if (n) { - ret.push(n); - } - } - return new NodeSetValue(ret); - }, - - 'local-name': function(ctx) { - alert('not implmented yet: XPath function local-name()'); - }, - - 'namespace-uri': function(ctx) { - alert('not implmented yet: XPath function namespace-uri()'); - }, - - 'name': function(ctx) { - assert(this.args.length == 1 || this.args.length == 0); - var n; - if (this.args.length == 0) { - n = [ ctx.node ]; - } else { - n = this.args[0].evaluate(ctx).nodeSetValue(); - } - - if (n.length == 0) { - return new StringValue(''); - } else { - return new StringValue(n[0].nodeName); - } - }, - - 'string': function(ctx) { - assert(this.args.length == 1 || this.args.length == 0); - if (this.args.length == 0) { - return new StringValue(new NodeSetValue([ ctx.node ]).stringValue()); - } else { - return new StringValue(this.args[0].evaluate(ctx).stringValue()); - } - }, - - 'concat': function(ctx) { - var ret = ''; - for (var i = 0; i < this.args.length; ++i) { - ret += this.args[i].evaluate(ctx).stringValue(); - } - return new StringValue(ret); - }, - - 'starts-with': function(ctx) { - assert(this.args.length == 2); - var s0 = this.args[0].evaluate(ctx).stringValue(); - var s1 = this.args[1].evaluate(ctx).stringValue(); - return new BooleanValue(s0.indexOf(s1) == 0); - }, - - 'contains': function(ctx) { - assert(this.args.length == 2); - var s0 = this.args[0].evaluate(ctx).stringValue(); - var s1 = this.args[1].evaluate(ctx).stringValue(); - return new BooleanValue(s0.indexOf(s1) != -1); - }, - - 'substring-before': function(ctx) { - assert(this.args.length == 2); - var s0 = this.args[0].evaluate(ctx).stringValue(); - var s1 = this.args[1].evaluate(ctx).stringValue(); - var i = s0.indexOf(s1); - var ret; - if (i == -1) { - ret = ''; - } else { - ret = s0.substr(0,i); - } - return new StringValue(ret); - }, - - 'substring-after': function(ctx) { - assert(this.args.length == 2); - var s0 = this.args[0].evaluate(ctx).stringValue(); - var s1 = this.args[1].evaluate(ctx).stringValue(); - var i = s0.indexOf(s1); - var ret; - if (i == -1) { - ret = ''; - } else { - ret = s0.substr(i + s1.length); - } - return new StringValue(ret); - }, - - 'substring': function(ctx) { - // NOTE: XPath defines the position of the first character in a - // string to be 1, in JavaScript this is 0 ([XPATH] Section 4.2). - assert(this.args.length == 2 || this.args.length == 3); - var s0 = this.args[0].evaluate(ctx).stringValue(); - var s1 = this.args[1].evaluate(ctx).numberValue(); - var ret; - if (this.args.length == 2) { - var i1 = Math.max(0, Math.round(s1) - 1); - ret = s0.substr(i1); - - } else { - var s2 = this.args[2].evaluate(ctx).numberValue(); - var i0 = Math.round(s1) - 1; - var i1 = Math.max(0, i0); - var i2 = Math.round(s2) - Math.max(0, -i0); - ret = s0.substr(i1, i2); - } - return new StringValue(ret); - }, - - 'string-length': function(ctx) { - var s; - if (this.args.length > 0) { - s = this.args[0].evaluate(ctx).stringValue(); - } else { - s = new NodeSetValue([ ctx.node ]).stringValue(); - } - return new NumberValue(s.length); - }, - - 'normalize-space': function(ctx) { - var s; - if (this.args.length > 0) { - s = this.args[0].evaluate(ctx).stringValue(); - } else { - s = new NodeSetValue([ ctx.node ]).stringValue(); - } - s = s.replace(/^\s*/,'').replace(/\s*$/,'').replace(/\s+/g, ' '); - return new StringValue(s); - }, - - 'translate': function(ctx) { - assert(this.args.length == 3); - var s0 = this.args[0].evaluate(ctx).stringValue(); - var s1 = this.args[1].evaluate(ctx).stringValue(); - var s2 = this.args[2].evaluate(ctx).stringValue(); - - for (var i = 0; i < s1.length; ++i) { - s0 = s0.replace(new RegExp(s1.charAt(i), 'g'), s2.charAt(i)); - } - return new StringValue(s0); - }, - - 'boolean': function(ctx) { - assert(this.args.length == 1); - return new BooleanValue(this.args[0].evaluate(ctx).booleanValue()); - }, - - 'not': function(ctx) { - assert(this.args.length == 1); - var ret = !this.args[0].evaluate(ctx).booleanValue(); - return new BooleanValue(ret); - }, - - 'true': function(ctx) { - assert(this.args.length == 0); - return new BooleanValue(true); - }, - - 'false': function(ctx) { - assert(this.args.length == 0); - return new BooleanValue(false); - }, - - 'lang': function(ctx) { - assert(this.args.length == 1); - var lang = this.args[0].evaluate(ctx).stringValue(); - var xmllang; - var n = ctx.node; - while (n && n != n.parentNode /* just in case ... */) { - xmllang = n.getAttribute('xml:lang'); - if (xmllang) { - break; - } - n = n.parentNode; - } - if (!xmllang) { - return new BooleanValue(false); - } else { - var re = new RegExp('^' + lang + '$', 'i'); - return new BooleanValue(xmllang.match(re) || - xmllang.replace(/_.*$/,'').match(re)); - } - }, - - 'number': function(ctx) { - assert(this.args.length == 1 || this.args.length == 0); - - if (this.args.length == 1) { - return new NumberValue(this.args[0].evaluate(ctx).numberValue()); - } else { - return new NumberValue(new NodeSetValue([ ctx.node ]).numberValue()); - } - }, - - 'sum': function(ctx) { - assert(this.args.length == 1); - var n = this.args[0].evaluate(ctx).nodeSetValue(); - var sum = 0; - for (var i = 0; i < n.length; ++i) { - sum += xmlValue(n[i]) - 0; - } - return new NumberValue(sum); - }, - - 'floor': function(ctx) { - assert(this.args.length == 1); - var num = this.args[0].evaluate(ctx).numberValue(); - return new NumberValue(Math.floor(num)); - }, - - 'ceiling': function(ctx) { - assert(this.args.length == 1); - var num = this.args[0].evaluate(ctx).numberValue(); - return new NumberValue(Math.ceil(num)); - }, - - 'round': function(ctx) { - assert(this.args.length == 1); - var num = this.args[0].evaluate(ctx).numberValue(); - return new NumberValue(Math.round(num)); - }, - - // TODO(mesch): The following functions are custom. There is a - // standard that defines how to add functions, which should be - // applied here. - - 'ext-join': function(ctx) { - assert(this.args.length == 2); - var nodes = this.args[0].evaluate(ctx).nodeSetValue(); - var delim = this.args[1].evaluate(ctx).stringValue(); - var ret = ''; - for (var i = 0; i < nodes.length; ++i) { - if (ret) { - ret += delim; - } - ret += xmlValue(nodes[i]); - } - return new StringValue(ret); - }, - - // ext-if() evaluates and returns its second argument, if the - // boolean value of its first argument is true, otherwise it - // evaluates and returns its third argument. - - 'ext-if': function(ctx) { - assert(this.args.length == 3); - if (this.args[0].evaluate(ctx).booleanValue()) { - return this.args[1].evaluate(ctx); - } else { - return this.args[2].evaluate(ctx); - } - }, - - 'ext-sprintf': function(ctx) { - assert(this.args.length >= 1); - var args = []; - for (var i = 0; i < this.args.length; ++i) { - args.push(this.args[i].evaluate(ctx).stringValue()); - } - return new StringValue(sprintf.apply(null, args)); - }, - - // ext-cardinal() evaluates its single argument as a number, and - // returns the current node that many times. It can be used in the - // select attribute to iterate over an integer range. - - 'ext-cardinal': function(ctx) { - assert(this.args.length >= 1); - var c = this.args[0].evaluate(ctx).numberValue(); - var ret = []; - for (var i = 0; i < c; ++i) { - ret.push(ctx.node); - } - return new NodeSetValue(ret); - } -}; - -function UnionExpr(expr1, expr2) { - this.expr1 = expr1; - this.expr2 = expr2; -} - -UnionExpr.prototype.evaluate = function(ctx) { - var nodes1 = this.expr1.evaluate(ctx).nodeSetValue(); - var nodes2 = this.expr2.evaluate(ctx).nodeSetValue(); - var I1 = nodes1.length; - for (var i2 = 0; i2 < nodes2.length; ++i2) { - for (var i1 = 0; i1 < I1; ++i1) { - if (nodes1[i1] == nodes2[i2]) { - // break inner loop and continue outer loop, labels confuse - // the js compiler, so we don't use them here. - i1 = I1; - } - } - nodes1.push(nodes2[i2]); - } - return new NodeSetValue(nodes2); -}; - -function PathExpr(filter, rel) { - this.filter = filter; - this.rel = rel; -} - -PathExpr.prototype.evaluate = function(ctx) { - var nodes = this.filter.evaluate(ctx).nodeSetValue(); - var nodes1 = []; - for (var i = 0; i < nodes.length; ++i) { - var nodes0 = this.rel.evaluate(ctx.clone(nodes[i], i, nodes)).nodeSetValue(); - for (var ii = 0; ii < nodes0.length; ++ii) { - nodes1.push(nodes0[ii]); - } - } - return new NodeSetValue(nodes1); -}; - -function FilterExpr(expr, predicate) { - this.expr = expr; - this.predicate = predicate; -} - -FilterExpr.prototype.evaluate = function(ctx) { - var nodes = this.expr.evaluate(ctx).nodeSetValue(); - for (var i = 0; i < this.predicate.length; ++i) { - var nodes0 = nodes; - nodes = []; - for (var j = 0; j < nodes0.length; ++j) { - var n = nodes0[j]; - if (this.predicate[i].evaluate(ctx.clone(n, j, nodes0)).booleanValue()) { - nodes.push(n); - } - } - } - - return new NodeSetValue(nodes); -} - -function UnaryMinusExpr(expr) { - this.expr = expr; -} - -UnaryMinusExpr.prototype.evaluate = function(ctx) { - return new NumberValue(-this.expr.evaluate(ctx).numberValue()); -}; - -function BinaryExpr(expr1, op, expr2) { - this.expr1 = expr1; - this.expr2 = expr2; - this.op = op; -} - -BinaryExpr.prototype.evaluate = function(ctx) { - var ret; - switch (this.op.value) { - case 'or': - ret = new BooleanValue(this.expr1.evaluate(ctx).booleanValue() || - this.expr2.evaluate(ctx).booleanValue()); - break; - - case 'and': - ret = new BooleanValue(this.expr1.evaluate(ctx).booleanValue() && - this.expr2.evaluate(ctx).booleanValue()); - break; - - case '+': - ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() + - this.expr2.evaluate(ctx).numberValue()); - break; - - case '-': - ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() - - this.expr2.evaluate(ctx).numberValue()); - break; - - case '*': - ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() * - this.expr2.evaluate(ctx).numberValue()); - break; - - case 'mod': - ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() % - this.expr2.evaluate(ctx).numberValue()); - break; - - case 'div': - ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() / - this.expr2.evaluate(ctx).numberValue()); - break; - - case '=': - ret = this.compare(ctx, function(x1, x2) { return x1 == x2; }); - break; - - case '!=': - ret = this.compare(ctx, function(x1, x2) { return x1 != x2; }); - break; - - case '<': - ret = this.compare(ctx, function(x1, x2) { return x1 < x2; }); - break; - - case '<=': - ret = this.compare(ctx, function(x1, x2) { return x1 <= x2; }); - break; - - case '>': - ret = this.compare(ctx, function(x1, x2) { return x1 > x2; }); - break; - - case '>=': - ret = this.compare(ctx, function(x1, x2) { return x1 >= x2; }); - break; - - default: - alert('BinaryExpr.evaluate: ' + this.op.value); - } - return ret; -}; - -BinaryExpr.prototype.compare = function(ctx, cmp) { - var v1 = this.expr1.evaluate(ctx); - var v2 = this.expr2.evaluate(ctx); - - var ret; - if (v1.type == 'node-set' && v2.type == 'node-set') { - var n1 = v1.nodeSetValue(); - var n2 = v2.nodeSetValue(); - ret = false; - for (var i1 = 0; i1 < n1.length; ++i1) { - for (var i2 = 0; i2 < n2.length; ++i2) { - if (cmp(xmlValue(n1[i1]), xmlValue(n2[i2]))) { - ret = true; - // Break outer loop. Labels confuse the jscompiler and we - // don't use them. - i2 = n2.length; - i1 = n1.length; - } - } - } - - } else if (v1.type == 'node-set' || v2.type == 'node-set') { - - if (v1.type == 'number') { - var s = v1.numberValue(); - var n = v2.nodeSetValue(); - - ret = false; - for (var i = 0; i < n.length; ++i) { - var nn = xmlValue(n[i]) - 0; - if (cmp(s, nn)) { - ret = true; - break; - } - } - - } else if (v2.type == 'number') { - var n = v1.nodeSetValue(); - var s = v2.numberValue(); - - ret = false; - for (var i = 0; i < n.length; ++i) { - var nn = xmlValue(n[i]) - 0; - if (cmp(nn, s)) { - ret = true; - break; - } - } - - } else if (v1.type == 'string') { - var s = v1.stringValue(); - var n = v2.nodeSetValue(); - - ret = false; - for (var i = 0; i < n.length; ++i) { - var nn = xmlValue(n[i]); - if (cmp(s, nn)) { - ret = true; - break; - } - } - - } else if (v2.type == 'string') { - var n = v1.nodeSetValue(); - var s = v2.stringValue(); - - ret = false; - for (var i = 0; i < n.length; ++i) { - var nn = xmlValue(n[i]); - if (cmp(nn, s)) { - ret = true; - break; - } - } - - } else { - ret = cmp(v1.booleanValue(), v2.booleanValue()); - } - - } else if (v1.type == 'boolean' || v2.type == 'boolean') { - ret = cmp(v1.booleanValue(), v2.booleanValue()); - - } else if (v1.type == 'number' || v2.type == 'number') { - ret = cmp(v1.numberValue(), v2.numberValue()); - - } else { - ret = cmp(v1.stringValue(), v2.stringValue()); - } - - return new BooleanValue(ret); -} - -function LiteralExpr(value) { - this.value = value; -} - -LiteralExpr.prototype.evaluate = function(ctx) { - return new StringValue(this.value); -}; - -function NumberExpr(value) { - this.value = value; -} - -NumberExpr.prototype.evaluate = function(ctx) { - return new NumberValue(this.value); -}; - -function VariableExpr(name) { - this.name = name; -} - -VariableExpr.prototype.evaluate = function(ctx) { - return ctx.getVariable(this.name); -} - -// Factory functions for semantic values (i.e. Expressions) of the -// productions in the grammar. When a production is matched to reduce -// the current parse state stack, the function is called with the -// semantic values of the matched elements as arguments, and returns -// another semantic value. The semantic value is a node of the parse -// tree, an expression object with an evaluate() method that evaluates the -// expression in an actual context. These factory functions are used -// in the specification of the grammar rules, below. - -function makeTokenExpr(m) { - return new TokenExpr(m); -} - -function passExpr(e) { - return e; -} - -function makeLocationExpr1(slash, rel) { - rel.absolute = true; - return rel; -} - -function makeLocationExpr2(dslash, rel) { - rel.absolute = true; - rel.prependStep(makeAbbrevStep(dslash.value)); - return rel; -} - -function makeLocationExpr3(slash) { - var ret = new LocationExpr(); - ret.appendStep(makeAbbrevStep('.')); - ret.absolute = true; - return ret; -} - -function makeLocationExpr4(dslash) { - var ret = new LocationExpr(); - ret.absolute = true; - ret.appendStep(makeAbbrevStep(dslash.value)); - return ret; -} - -function makeLocationExpr5(step) { - var ret = new LocationExpr(); - ret.appendStep(step); - return ret; -} - -function makeLocationExpr6(rel, slash, step) { - rel.appendStep(step); - return rel; -} - -function makeLocationExpr7(rel, dslash, step) { - rel.appendStep(makeAbbrevStep(dslash.value)); - return rel; -} - -function makeStepExpr1(dot) { - return makeAbbrevStep(dot.value); -} - -function makeStepExpr2(ddot) { - return makeAbbrevStep(ddot.value); -} - -function makeStepExpr3(axisname, axis, nodetest) { - return new StepExpr(axisname.value, nodetest); -} - -function makeStepExpr4(at, nodetest) { - return new StepExpr('attribute', nodetest); -} - -function makeStepExpr5(nodetest) { - return new StepExpr('child', nodetest); -} - -function makeStepExpr6(step, predicate) { - step.appendPredicate(predicate); - return step; -} - -function makeAbbrevStep(abbrev) { - switch (abbrev) { - case '//': - return new StepExpr('descendant-or-self', new NodeTestAny); - - case '.': - return new StepExpr('self', new NodeTestAny); - - case '..': - return new StepExpr('parent', new NodeTestAny); - } -} - -function makeNodeTestExpr1(asterisk) { - return new NodeTestElement; -} - -function makeNodeTestExpr2(ncname, colon, asterisk) { - return new NodeTestNC(ncname.value); -} - -function makeNodeTestExpr3(qname) { - return new NodeTestName(qname.value); -} - -function makeNodeTestExpr4(typeo, parenc) { - var type = typeo.value.replace(/\s*\($/, ''); - switch(type) { - case 'node': - return new NodeTestAny; - - case 'text': - return new NodeTestText; - - case 'comment': - return new NodeTestComment; - - case 'processing-instruction': - return new NodeTestPI; - } -} - -function makeNodeTestExpr5(typeo, target, parenc) { - var type = typeo.replace(/\s*\($/, ''); - if (type != 'processing-instruction') { - throw type + ' ' + Error().stack; - } - return new NodeTestPI(target.value); -} - -function makePredicateExpr(pareno, expr, parenc) { - return new PredicateExpr(expr); -} - -function makePrimaryExpr(pareno, expr, parenc) { - return expr; -} - -function makeFunctionCallExpr1(name, pareno, parenc) { - return new FunctionCallExpr(name); -} - -function makeFunctionCallExpr2(name, pareno, arg1, args, parenc) { - var ret = new FunctionCallExpr(name); - ret.appendArg(arg1); - for (var i = 0; i < args.length; ++i) { - ret.appendArg(args[i]); - } - return ret; -} - -function makeArgumentExpr(comma, expr) { - return expr; -} - -function makeUnionExpr(expr1, pipe, expr2) { - return new UnionExpr(expr1, expr2); -} - -function makePathExpr1(filter, slash, rel) { - return new PathExpr(filter, rel); -} - -function makePathExpr2(filter, dslash, rel) { - rel.prependStep(makeAbbrevStep(dslash.value)); - return new PathExpr(filter, rel); -} - -function makeFilterExpr(expr, predicates) { - if (predicates.length > 0) { - return new FilterExpr(expr, predicates); - } else { - return expr; - } -} - -function makeUnaryMinusExpr(minus, expr) { - return new UnaryMinusExpr(expr); -} - -function makeBinaryExpr(expr1, op, expr2) { - return new BinaryExpr(expr1, op, expr2); -} - -function makeLiteralExpr(token) { - // remove quotes from the parsed value: - var value = token.value.substring(1, token.value.length - 1); - return new LiteralExpr(value); -} - -function makeNumberExpr(token) { - return new NumberExpr(token.value); -} - -function makeVariableReference(dollar, name) { - return new VariableExpr(name.value); -} - -// Used before parsing for optimization of common simple cases. See -// the begin of xpathParse() for which they are. -function makeSimpleExpr(expr) { - if (expr.charAt(0) == '$') { - return new VariableExpr(expr.substr(1)); - } else if (expr.charAt(0) == '@') { - var a = new NodeTestName(expr.substr(1)); - var b = new StepExpr('attribute', a); - var c = new LocationExpr(); - c.appendStep(b); - return c; - } else if (expr.match(/^[0-9]+$/)) { - return new NumberExpr(expr); - } else { - var a = new NodeTestName(expr); - var b = new StepExpr('child', a); - var c = new LocationExpr(); - c.appendStep(b); - return c; - } -} - -function makeSimpleExpr2(expr) { - var steps = expr.split('/'); - var c = new LocationExpr(); - for (var i in steps) { - var a = new NodeTestName(steps[i]); - var b = new StepExpr('child', a); - c.appendStep(b); - } - return c; -} - -// The axes of XPath expressions. - -var xpathAxis = { - ANCESTOR_OR_SELF: 'ancestor-or-self', - ANCESTOR: 'ancestor', - ATTRIBUTE: 'attribute', - CHILD: 'child', - DESCENDANT_OR_SELF: 'descendant-or-self', - DESCENDANT: 'descendant', - FOLLOWING_SIBLING: 'following-sibling', - FOLLOWING: 'following', - NAMESPACE: 'namespace', - PARENT: 'parent', - PRECEDING_SIBLING: 'preceding-sibling', - PRECEDING: 'preceding', - SELF: 'self' -}; - -var xpathAxesRe = [ - xpathAxis.ANCESTOR_OR_SELF, - xpathAxis.ANCESTOR, - xpathAxis.ATTRIBUTE, - xpathAxis.CHILD, - xpathAxis.DESCENDANT_OR_SELF, - xpathAxis.DESCENDANT, - xpathAxis.FOLLOWING_SIBLING, - xpathAxis.FOLLOWING, - xpathAxis.NAMESPACE, - xpathAxis.PARENT, - xpathAxis.PRECEDING_SIBLING, - xpathAxis.PRECEDING, - xpathAxis.SELF -].join('|'); - - -// The tokens of the language. The label property is just used for -// generating debug output. The prec property is the precedence used -// for shift/reduce resolution. Default precedence is 0 as a lookahead -// token and 2 on the stack. TODO(mesch): this is certainly not -// necessary and too complicated. Simplify this! - -// NOTE: tabular formatting is the big exception, but here it should -// be OK. - -var TOK_PIPE = { label: "|", prec: 17, re: new RegExp("^\\|") }; -var TOK_DSLASH = { label: "//", prec: 19, re: new RegExp("^//") }; -var TOK_SLASH = { label: "/", prec: 30, re: new RegExp("^/") }; -var TOK_AXIS = { label: "::", prec: 20, re: new RegExp("^::") }; -var TOK_COLON = { label: ":", prec: 1000, re: new RegExp("^:") }; -var TOK_AXISNAME = { label: "[axis]", re: new RegExp('^(' + xpathAxesRe + ')') }; -var TOK_PARENO = { label: "(", prec: 34, re: new RegExp("^\\(") }; -var TOK_PARENC = { label: ")", re: new RegExp("^\\)") }; -var TOK_DDOT = { label: "..", prec: 34, re: new RegExp("^\\.\\.") }; -var TOK_DOT = { label: ".", prec: 34, re: new RegExp("^\\.") }; -var TOK_AT = { label: "@", prec: 34, re: new RegExp("^@") }; - -var TOK_COMMA = { label: ",", re: new RegExp("^,") }; - -var TOK_OR = { label: "or", prec: 10, re: new RegExp("^or\\b") }; -var TOK_AND = { label: "and", prec: 11, re: new RegExp("^and\\b") }; -var TOK_EQ = { label: "=", prec: 12, re: new RegExp("^=") }; -var TOK_NEQ = { label: "!=", prec: 12, re: new RegExp("^!=") }; -var TOK_GE = { label: ">=", prec: 13, re: new RegExp("^>=") }; -var TOK_GT = { label: ">", prec: 13, re: new RegExp("^>") }; -var TOK_LE = { label: "<=", prec: 13, re: new RegExp("^<=") }; -var TOK_LT = { label: "<", prec: 13, re: new RegExp("^<") }; -var TOK_PLUS = { label: "+", prec: 14, re: new RegExp("^\\+"), left: true }; -var TOK_MINUS = { label: "-", prec: 14, re: new RegExp("^\\-"), left: true }; -var TOK_DIV = { label: "div", prec: 15, re: new RegExp("^div\\b"), left: true }; -var TOK_MOD = { label: "mod", prec: 15, re: new RegExp("^mod\\b"), left: true }; - -var TOK_BRACKO = { label: "[", prec: 32, re: new RegExp("^\\[") }; -var TOK_BRACKC = { label: "]", re: new RegExp("^\\]") }; -var TOK_DOLLAR = { label: "$", re: new RegExp("^\\$") }; - -var TOK_NCNAME = { label: "[ncname]", re: new RegExp('^[a-z][-\\w]*','i') }; - -var TOK_ASTERISK = { label: "*", prec: 15, re: new RegExp("^\\*"), left: true }; -var TOK_LITERALQ = { label: "[litq]", prec: 20, re: new RegExp("^'[^\\']*'") }; -var TOK_LITERALQQ = { - label: "[litqq]", - prec: 20, - re: new RegExp('^"[^\\"]*"') -}; - -var TOK_NUMBER = { - label: "[number]", - prec: 35, - re: new RegExp('^\\d+(\\.\\d*)?') }; - -var TOK_QNAME = { - label: "[qname]", - re: new RegExp('^([a-z][-\\w]*:)?[a-z][-\\w]*','i') -}; - -var TOK_NODEO = { - label: "[nodetest-start]", - re: new RegExp('^(processing-instruction|comment|text|node)\\(') -}; - -// The table of the tokens of our grammar, used by the lexer: first -// column the tag, second column a regexp to recognize it in the -// input, third column the precedence of the token, fourth column a -// factory function for the semantic value of the token. -// -// NOTE: order of this list is important, because the first match -// counts. Cf. DDOT and DOT, and AXIS and COLON. - -var xpathTokenRules = [ - TOK_DSLASH, - TOK_SLASH, - TOK_DDOT, - TOK_DOT, - TOK_AXIS, - TOK_COLON, - TOK_AXISNAME, - TOK_NODEO, - TOK_PARENO, - TOK_PARENC, - TOK_BRACKO, - TOK_BRACKC, - TOK_AT, - TOK_COMMA, - TOK_OR, - TOK_AND, - TOK_NEQ, - TOK_EQ, - TOK_GE, - TOK_GT, - TOK_LE, - TOK_LT, - TOK_PLUS, - TOK_MINUS, - TOK_ASTERISK, - TOK_PIPE, - TOK_MOD, - TOK_DIV, - TOK_LITERALQ, - TOK_LITERALQQ, - TOK_NUMBER, - TOK_QNAME, - TOK_NCNAME, - TOK_DOLLAR -]; - -// All the nonterminals of the grammar. The nonterminal objects are -// identified by object identity; the labels are used in the debug -// output only. -var XPathLocationPath = { label: "LocationPath" }; -var XPathRelativeLocationPath = { label: "RelativeLocationPath" }; -var XPathAbsoluteLocationPath = { label: "AbsoluteLocationPath" }; -var XPathStep = { label: "Step" }; -var XPathNodeTest = { label: "NodeTest" }; -var XPathPredicate = { label: "Predicate" }; -var XPathLiteral = { label: "Literal" }; -var XPathExpr = { label: "Expr" }; -var XPathPrimaryExpr = { label: "PrimaryExpr" }; -var XPathVariableReference = { label: "Variablereference" }; -var XPathNumber = { label: "Number" }; -var XPathFunctionCall = { label: "FunctionCall" }; -var XPathArgumentRemainder = { label: "ArgumentRemainder" }; -var XPathPathExpr = { label: "PathExpr" }; -var XPathUnionExpr = { label: "UnionExpr" }; -var XPathFilterExpr = { label: "FilterExpr" }; -var XPathDigits = { label: "Digits" }; - -var xpathNonTerminals = [ - XPathLocationPath, - XPathRelativeLocationPath, - XPathAbsoluteLocationPath, - XPathStep, - XPathNodeTest, - XPathPredicate, - XPathLiteral, - XPathExpr, - XPathPrimaryExpr, - XPathVariableReference, - XPathNumber, - XPathFunctionCall, - XPathArgumentRemainder, - XPathPathExpr, - XPathUnionExpr, - XPathFilterExpr, - XPathDigits -]; - -// Quantifiers that are used in the productions of the grammar. -var Q_01 = { label: "?" }; -var Q_MM = { label: "*" }; -var Q_1M = { label: "+" }; - -// Tag for left associativity (right assoc is implied by undefined). -var ASSOC_LEFT = true; - -// The productions of the grammar. Columns of the table: -// -// - target nonterminal, -// - pattern, -// - precedence, -// - semantic value factory -// -// The semantic value factory is a function that receives parse tree -// nodes from the stack frames of the matched symbols as arguments and -// returns an a node of the parse tree. The node is stored in the top -// stack frame along with the target object of the rule. The node in -// the parse tree is an expression object that has an evaluate() method -// and thus evaluates XPath expressions. -// -// The precedence is used to decide between reducing and shifting by -// comparing the precendence of the rule that is candidate for -// reducing with the precedence of the look ahead token. Precedence of -// -1 means that the precedence of the tokens in the pattern is used -// instead. TODO: It shouldn't be necessary to explicitly assign -// precedences to rules. - -var xpathGrammarRules = - [ - [ XPathLocationPath, [ XPathRelativeLocationPath ], 18, - passExpr ], - [ XPathLocationPath, [ XPathAbsoluteLocationPath ], 18, - passExpr ], - - [ XPathAbsoluteLocationPath, [ TOK_SLASH, XPathRelativeLocationPath ], 18, - makeLocationExpr1 ], - [ XPathAbsoluteLocationPath, [ TOK_DSLASH, XPathRelativeLocationPath ], 18, - makeLocationExpr2 ], - - [ XPathAbsoluteLocationPath, [ TOK_SLASH ], 0, - makeLocationExpr3 ], - [ XPathAbsoluteLocationPath, [ TOK_DSLASH ], 0, - makeLocationExpr4 ], - - [ XPathRelativeLocationPath, [ XPathStep ], 31, - makeLocationExpr5 ], - [ XPathRelativeLocationPath, - [ XPathRelativeLocationPath, TOK_SLASH, XPathStep ], 31, - makeLocationExpr6 ], - [ XPathRelativeLocationPath, - [ XPathRelativeLocationPath, TOK_DSLASH, XPathStep ], 31, - makeLocationExpr7 ], - - [ XPathStep, [ TOK_DOT ], 33, - makeStepExpr1 ], - [ XPathStep, [ TOK_DDOT ], 33, - makeStepExpr2 ], - [ XPathStep, - [ TOK_AXISNAME, TOK_AXIS, XPathNodeTest ], 33, - makeStepExpr3 ], - [ XPathStep, [ TOK_AT, XPathNodeTest ], 33, - makeStepExpr4 ], - [ XPathStep, [ XPathNodeTest ], 33, - makeStepExpr5 ], - [ XPathStep, [ XPathStep, XPathPredicate ], 33, - makeStepExpr6 ], - - [ XPathNodeTest, [ TOK_ASTERISK ], 33, - makeNodeTestExpr1 ], - [ XPathNodeTest, [ TOK_NCNAME, TOK_COLON, TOK_ASTERISK ], 33, - makeNodeTestExpr2 ], - [ XPathNodeTest, [ TOK_QNAME ], 33, - makeNodeTestExpr3 ], - [ XPathNodeTest, [ TOK_NODEO, TOK_PARENC ], 33, - makeNodeTestExpr4 ], - [ XPathNodeTest, [ TOK_NODEO, XPathLiteral, TOK_PARENC ], 33, - makeNodeTestExpr5 ], - - [ XPathPredicate, [ TOK_BRACKO, XPathExpr, TOK_BRACKC ], 33, - makePredicateExpr ], - - [ XPathPrimaryExpr, [ XPathVariableReference ], 33, - passExpr ], - [ XPathPrimaryExpr, [ TOK_PARENO, XPathExpr, TOK_PARENC ], 33, - makePrimaryExpr ], - [ XPathPrimaryExpr, [ XPathLiteral ], 30, - passExpr ], - [ XPathPrimaryExpr, [ XPathNumber ], 30, - passExpr ], - [ XPathPrimaryExpr, [ XPathFunctionCall ], 30, - passExpr ], - - [ XPathFunctionCall, [ TOK_QNAME, TOK_PARENO, TOK_PARENC ], -1, - makeFunctionCallExpr1 ], - [ XPathFunctionCall, - [ TOK_QNAME, TOK_PARENO, XPathExpr, XPathArgumentRemainder, Q_MM, - TOK_PARENC ], -1, - makeFunctionCallExpr2 ], - [ XPathArgumentRemainder, [ TOK_COMMA, XPathExpr ], -1, - makeArgumentExpr ], - - [ XPathUnionExpr, [ XPathPathExpr ], 20, - passExpr ], - [ XPathUnionExpr, [ XPathUnionExpr, TOK_PIPE, XPathPathExpr ], 20, - makeUnionExpr ], - - [ XPathPathExpr, [ XPathLocationPath ], 20, - passExpr ], - [ XPathPathExpr, [ XPathFilterExpr ], 19, - passExpr ], - [ XPathPathExpr, - [ XPathFilterExpr, TOK_SLASH, XPathRelativeLocationPath ], 20, - makePathExpr1 ], - [ XPathPathExpr, - [ XPathFilterExpr, TOK_DSLASH, XPathRelativeLocationPath ], 20, - makePathExpr2 ], - - [ XPathFilterExpr, [ XPathPrimaryExpr, XPathPredicate, Q_MM ], 20, - makeFilterExpr ], - - [ XPathExpr, [ XPathPrimaryExpr ], 16, - passExpr ], - [ XPathExpr, [ XPathUnionExpr ], 16, - passExpr ], - - [ XPathExpr, [ TOK_MINUS, XPathExpr ], -1, - makeUnaryMinusExpr ], - - [ XPathExpr, [ XPathExpr, TOK_OR, XPathExpr ], -1, - makeBinaryExpr ], - [ XPathExpr, [ XPathExpr, TOK_AND, XPathExpr ], -1, - makeBinaryExpr ], - - [ XPathExpr, [ XPathExpr, TOK_EQ, XPathExpr ], -1, - makeBinaryExpr ], - [ XPathExpr, [ XPathExpr, TOK_NEQ, XPathExpr ], -1, - makeBinaryExpr ], - - [ XPathExpr, [ XPathExpr, TOK_LT, XPathExpr ], -1, - makeBinaryExpr ], - [ XPathExpr, [ XPathExpr, TOK_LE, XPathExpr ], -1, - makeBinaryExpr ], - [ XPathExpr, [ XPathExpr, TOK_GT, XPathExpr ], -1, - makeBinaryExpr ], - [ XPathExpr, [ XPathExpr, TOK_GE, XPathExpr ], -1, - makeBinaryExpr ], - - [ XPathExpr, [ XPathExpr, TOK_PLUS, XPathExpr ], -1, - makeBinaryExpr, ASSOC_LEFT ], - [ XPathExpr, [ XPathExpr, TOK_MINUS, XPathExpr ], -1, - makeBinaryExpr, ASSOC_LEFT ], - - [ XPathExpr, [ XPathExpr, TOK_ASTERISK, XPathExpr ], -1, - makeBinaryExpr, ASSOC_LEFT ], - [ XPathExpr, [ XPathExpr, TOK_DIV, XPathExpr ], -1, - makeBinaryExpr, ASSOC_LEFT ], - [ XPathExpr, [ XPathExpr, TOK_MOD, XPathExpr ], -1, - makeBinaryExpr, ASSOC_LEFT ], - - [ XPathLiteral, [ TOK_LITERALQ ], -1, - makeLiteralExpr ], - [ XPathLiteral, [ TOK_LITERALQQ ], -1, - makeLiteralExpr ], - - [ XPathNumber, [ TOK_NUMBER ], -1, - makeNumberExpr ], - - [ XPathVariableReference, [ TOK_DOLLAR, TOK_QNAME ], 200, - makeVariableReference ] - ]; - -// That function computes some optimizations of the above data -// structures and will be called right here. It merely takes the -// counter variables out of the global scope. - -var xpathRules = []; - -function xpathParseInit() { - if (xpathRules.length) { - return; - } - - // Some simple optimizations for the xpath expression parser: sort - // grammar rules descending by length, so that the longest match is - // first found. - - xpathGrammarRules.sort(function(a,b) { - var la = a[1].length; - var lb = b[1].length; - if (la < lb) { - return 1; - } else if (la > lb) { - return -1; - } else { - return 0; - } - }); - - var k = 1; - for (var i = 0; i < xpathNonTerminals.length; ++i) { - xpathNonTerminals[i].key = k++; - } - - for (i = 0; i < xpathTokenRules.length; ++i) { - xpathTokenRules[i].key = k++; - } - - Log.write('XPath parse INIT: ' + k + ' rules'); - - // Another slight optimization: sort the rules into bins according - // to the last element (observing quantifiers), so we can restrict - // the match against the stack to the subest of rules that match the - // top of the stack. - // - // TODO(mesch): What we actually want is to compute states as in - // bison, so that we don't have to do any explicit and iterated - // match against the stack. - - function push_(array, position, element) { - if (!array[position]) { - array[position] = []; - } - array[position].push(element); - } - - for (i = 0; i < xpathGrammarRules.length; ++i) { - var rule = xpathGrammarRules[i]; - var pattern = rule[1]; - - for (var j = pattern.length - 1; j >= 0; --j) { - if (pattern[j] == Q_1M) { - push_(xpathRules, pattern[j-1].key, rule); - break; - - } else if (pattern[j] == Q_MM || pattern[j] == Q_01) { - push_(xpathRules, pattern[j-1].key, rule); - --j; - - } else { - push_(xpathRules, pattern[j].key, rule); - break; - } - } - } - - Log.write('XPath parse INIT: ' + xpathRules.length + ' rule bins'); - - var sum = 0; - mapExec(xpathRules, function(i) { - if (i) { - sum += i.length; - } - }); - - Log.write('XPath parse INIT: ' + (sum / xpathRules.length) + ' average bin size'); -} - -// Local utility functions that are used by the lexer or parser. - -function xpathCollectDescendants(nodelist, node) { - for (var n = node.firstChild; n; n = n.nextSibling) { - nodelist.push(n); - arguments.callee(nodelist, n); - } -} - -function xpathCollectDescendantsReverse(nodelist, node) { - for (var n = node.lastChild; n; n = n.previousSibling) { - nodelist.push(n); - arguments.callee(nodelist, n); - } -} - - -// The entry point for the library: match an expression against a DOM -// node. Returns an XPath value. -function xpathDomEval(expr, node) { - var expr1 = xpathParse(expr); - var ret = expr1.evaluate(new ExprContext(node)); - return ret; -} - -// Utility function to sort a list of nodes. Used by xsltSort() and -// nxslSelect(). -function xpathSort(input, sort) { - if (sort.length == 0) { - return; - } - - var sortlist = []; - - for (var i = 0; i < input.nodelist.length; ++i) { - var node = input.nodelist[i]; - var sortitem = { node: node, key: [] }; - var context = input.clone(node, 0, [ node ]); - - for (var j = 0; j < sort.length; ++j) { - var s = sort[j]; - var value = s.expr.evaluate(context); - - var evalue; - if (s.type == 'text') { - evalue = value.stringValue(); - } else if (s.type == 'number') { - evalue = value.numberValue(); - } - sortitem.key.push({ value: evalue, order: s.order }); - } - - // Make the sort stable by adding a lowest priority sort by - // id. This is very convenient and furthermore required by the - // spec ([XSLT] - Section 10 Sorting). - sortitem.key.push({ value: i, order: 'ascending' }); - - sortlist.push(sortitem); - } - - sortlist.sort(xpathSortByKey); - - var nodes = []; - for (var i = 0; i < sortlist.length; ++i) { - nodes.push(sortlist[i].node); - } - input.nodelist = nodes; - input.setNode(nodes[0], 0); -} - - -// Sorts by all order criteria defined. According to the JavaScript -// spec ([ECMA] Section 11.8.5), the compare operators compare strings -// as strings and numbers as numbers. -// -// NOTE: In browsers which do not follow the spec, this breaks only in -// the case that numbers should be sorted as strings, which is very -// uncommon. - -function xpathSortByKey(v1, v2) { - // NOTE: Sort key vectors of different length never occur in - // xsltSort. - - for (var i = 0; i < v1.key.length; ++i) { - var o = v1.key[i].order == 'descending' ? -1 : 1; - if (v1.key[i].value > v2.key[i].value) { - return +1 * o; - } else if (v1.key[i].value < v2.key[i].value) { - return -1 * o; - } - } - - return 0; -} |