// xpath.js - version 0.7 - Spry Pre-Release 1.6.1
//
// Code from xmltoken.js.
//
// Copyright 2006 Google Inc.
// All Rights Reserved
//
// Defines regular expression patterns to extract XML tokens from string.
// See <http://www.w3.org/TR/REC-xml/#sec-common-syn>,
// <http://www.w3.org/TR/xml11/#sec-common-syn> and
// <http://www.w3.org/TR/REC-xml-names/#NT-NCName> for the specifications.
//
// Author: Junji Takagi <jtakagi@google.com>

// Detect whether RegExp supports Unicode characters or not.

var REGEXP_UNICODE = function(){
    var tests = [' ', '\u0120', -1, // Konquerer 3.4.0 fails here.
 '!', '\u0120', -1, '\u0120', '\u0120', 0, '\u0121', '\u0120', -1, '\u0121', '\u0120|\u0121', 0, '\u0122', '\u0120|\u0121', -1, '\u0120', '[\u0120]', 0, // Safari 2.0.3 fails here.
 '\u0121', '[\u0120]', -1, '\u0121', '[\u0120\u0121]', 0, // Safari 2.0.3 fails here.
 '\u0122', '[\u0120\u0121]', -1, '\u0121', '[\u0120-\u0121]', 0, // Safari 2.0.3 fails here.
 '\u0122', '[\u0120-\u0121]', -1];
    for (var i = 0; i < tests.length; i += 3) {
        if (tests[i].search(new RegExp(tests[i + 1])) != tests[i + 2]) {
            return false;
        }
    }
    return true;
}
();

// Common tokens in XML 1.0 and XML 1.1.

var XML_S = '[ \t\r\n]+';
var XML_EQ = '(' + XML_S + ')?=(' + XML_S + ')?';
var XML_CHAR_REF = '&#[0-9]+;|&#x[0-9a-fA-F]+;';

// XML 1.0 tokens.

var XML10_VERSION_INFO = XML_S + 'version' + XML_EQ + '("1\\.0"|' + "'1\\.0')";
var XML10_BASE_CHAR = (REGEXP_UNICODE) ? '\u0041-\u005a\u0061-\u007a\u00c0-\u00d6\u00d8-\u00f6\u00f8-\u00ff' +
'\u0100-\u0131\u0134-\u013e\u0141-\u0148\u014a-\u017e\u0180-\u01c3' +
'\u01cd-\u01f0\u01f4-\u01f5\u01fa-\u0217\u0250-\u02a8\u02bb-\u02c1\u0386' +
'\u0388-\u038a\u038c\u038e-\u03a1\u03a3-\u03ce\u03d0-\u03d6\u03da\u03dc' +
'\u03de\u03e0\u03e2-\u03f3\u0401-\u040c\u040e-\u044f\u0451-\u045c' +
'\u045e-\u0481\u0490-\u04c4\u04c7-\u04c8\u04cb-\u04cc\u04d0-\u04eb' +
'\u04ee-\u04f5\u04f8-\u04f9\u0531-\u0556\u0559\u0561-\u0586\u05d0-\u05ea' +
'\u05f0-\u05f2\u0621-\u063a\u0641-\u064a\u0671-\u06b7\u06ba-\u06be' +
'\u06c0-\u06ce\u06d0-\u06d3\u06d5\u06e5-\u06e6\u0905-\u0939\u093d' +
'\u0958-\u0961\u0985-\u098c\u098f-\u0990\u0993-\u09a8\u09aa-\u09b0\u09b2' +
'\u09b6-\u09b9\u09dc-\u09dd\u09df-\u09e1\u09f0-\u09f1\u0a05-\u0a0a' +
'\u0a0f-\u0a10\u0a13-\u0a28\u0a2a-\u0a30\u0a32-\u0a33\u0a35-\u0a36' +
'\u0a38-\u0a39\u0a59-\u0a5c\u0a5e\u0a72-\u0a74\u0a85-\u0a8b\u0a8d' +
'\u0a8f-\u0a91\u0a93-\u0aa8\u0aaa-\u0ab0\u0ab2-\u0ab3\u0ab5-\u0ab9' +
'\u0abd\u0ae0\u0b05-\u0b0c\u0b0f-\u0b10\u0b13-\u0b28\u0b2a-\u0b30' +
'\u0b32-\u0b33\u0b36-\u0b39\u0b3d\u0b5c-\u0b5d\u0b5f-\u0b61\u0b85-\u0b8a' +
'\u0b8e-\u0b90\u0b92-\u0b95\u0b99-\u0b9a\u0b9c\u0b9e-\u0b9f\u0ba3-\u0ba4' +
'\u0ba8-\u0baa\u0bae-\u0bb5\u0bb7-\u0bb9\u0c05-\u0c0c\u0c0e-\u0c10' +
'\u0c12-\u0c28\u0c2a-\u0c33\u0c35-\u0c39\u0c60-\u0c61\u0c85-\u0c8c' +
'\u0c8e-\u0c90\u0c92-\u0ca8\u0caa-\u0cb3\u0cb5-\u0cb9\u0cde\u0ce0-\u0ce1' +
'\u0d05-\u0d0c\u0d0e-\u0d10\u0d12-\u0d28\u0d2a-\u0d39\u0d60-\u0d61' +
'\u0e01-\u0e2e\u0e30\u0e32-\u0e33\u0e40-\u0e45\u0e81-\u0e82\u0e84' +
'\u0e87-\u0e88\u0e8a\u0e8d\u0e94-\u0e97\u0e99-\u0e9f\u0ea1-\u0ea3\u0ea5' +
'\u0ea7\u0eaa-\u0eab\u0ead-\u0eae\u0eb0\u0eb2-\u0eb3\u0ebd\u0ec0-\u0ec4' +
'\u0f40-\u0f47\u0f49-\u0f69\u10a0-\u10c5\u10d0-\u10f6\u1100\u1102-\u1103' +
'\u1105-\u1107\u1109\u110b-\u110c\u110e-\u1112\u113c\u113e\u1140\u114c' +
'\u114e\u1150\u1154-\u1155\u1159\u115f-\u1161\u1163\u1165\u1167\u1169' +
'\u116d-\u116e\u1172-\u1173\u1175\u119e\u11a8\u11ab\u11ae-\u11af' +
'\u11b7-\u11b8\u11ba\u11bc-\u11c2\u11eb\u11f0\u11f9\u1e00-\u1e9b' +
'\u1ea0-\u1ef9\u1f00-\u1f15\u1f18-\u1f1d\u1f20-\u1f45\u1f48-\u1f4d' +
'\u1f50-\u1f57\u1f59\u1f5b\u1f5d\u1f5f-\u1f7d\u1f80-\u1fb4\u1fb6-\u1fbc' +
'\u1fbe\u1fc2-\u1fc4\u1fc6-\u1fcc\u1fd0-\u1fd3\u1fd6-\u1fdb\u1fe0-\u1fec' +
'\u1ff2-\u1ff4\u1ff6-\u1ffc\u2126\u212a-\u212b\u212e\u2180-\u2182' +
'\u3041-\u3094\u30a1-\u30fa\u3105-\u312c\uac00-\ud7a3' : 'A-Za-z';
var XML10_IDEOGRAPHIC = (REGEXP_UNICODE) ? '\u4e00-\u9fa5\u3007\u3021-\u3029' : '';
var XML10_COMBINING_CHAR = (REGEXP_UNICODE) ? '\u0300-\u0345\u0360-\u0361\u0483-\u0486\u0591-\u05a1\u05a3-\u05b9' +
'\u05bb-\u05bd\u05bf\u05c1-\u05c2\u05c4\u064b-\u0652\u0670\u06d6-\u06dc' +
'\u06dd-\u06df\u06e0-\u06e4\u06e7-\u06e8\u06ea-\u06ed\u0901-\u0903\u093c' +
'\u093e-\u094c\u094d\u0951-\u0954\u0962-\u0963\u0981-\u0983\u09bc\u09be' +
'\u09bf\u09c0-\u09c4\u09c7-\u09c8\u09cb-\u09cd\u09d7\u09e2-\u09e3\u0a02' +
'\u0a3c\u0a3e\u0a3f\u0a40-\u0a42\u0a47-\u0a48\u0a4b-\u0a4d\u0a70-\u0a71' +
'\u0a81-\u0a83\u0abc\u0abe-\u0ac5\u0ac7-\u0ac9\u0acb-\u0acd\u0b01-\u0b03' +
'\u0b3c\u0b3e-\u0b43\u0b47-\u0b48\u0b4b-\u0b4d\u0b56-\u0b57\u0b82-\u0b83' +
'\u0bbe-\u0bc2\u0bc6-\u0bc8\u0bca-\u0bcd\u0bd7\u0c01-\u0c03\u0c3e-\u0c44' +
'\u0c46-\u0c48\u0c4a-\u0c4d\u0c55-\u0c56\u0c82-\u0c83\u0cbe-\u0cc4' +
'\u0cc6-\u0cc8\u0cca-\u0ccd\u0cd5-\u0cd6\u0d02-\u0d03\u0d3e-\u0d43' +
'\u0d46-\u0d48\u0d4a-\u0d4d\u0d57\u0e31\u0e34-\u0e3a\u0e47-\u0e4e\u0eb1' +
'\u0eb4-\u0eb9\u0ebb-\u0ebc\u0ec8-\u0ecd\u0f18-\u0f19\u0f35\u0f37\u0f39' +
'\u0f3e\u0f3f\u0f71-\u0f84\u0f86-\u0f8b\u0f90-\u0f95\u0f97\u0f99-\u0fad' +
'\u0fb1-\u0fb7\u0fb9\u20d0-\u20dc\u20e1\u302a-\u302f\u3099\u309a' : '';
var XML10_DIGIT = (REGEXP_UNICODE) ? '\u0030-\u0039\u0660-\u0669\u06f0-\u06f9\u0966-\u096f\u09e6-\u09ef' +
'\u0a66-\u0a6f\u0ae6-\u0aef\u0b66-\u0b6f\u0be7-\u0bef\u0c66-\u0c6f' +
'\u0ce6-\u0cef\u0d66-\u0d6f\u0e50-\u0e59\u0ed0-\u0ed9\u0f20-\u0f29' : '0-9';
var XML10_EXTENDER = (REGEXP_UNICODE) ? '\u00b7\u02d0\u02d1\u0387\u0640\u0e46\u0ec6\u3005\u3031-\u3035' +
'\u309d-\u309e\u30fc-\u30fe' : '';
var XML10_LETTER = XML10_BASE_CHAR + XML10_IDEOGRAPHIC;
var XML10_NAME_CHAR = XML10_LETTER + XML10_DIGIT + '\\._:' +
XML10_COMBINING_CHAR +
XML10_EXTENDER +
'-';
var XML10_NAME = '[' + XML10_LETTER + '_:][' + XML10_NAME_CHAR + ']*';

var XML10_ENTITY_REF = '&' + XML10_NAME + ';';
var XML10_REFERENCE = XML10_ENTITY_REF + '|' + XML_CHAR_REF;
var XML10_ATT_VALUE = '"(([^<&"]|' + XML10_REFERENCE + ')*)"|' +
"'(([^<&']|" +
XML10_REFERENCE +
")*)'";
var XML10_ATTRIBUTE = '(' + XML10_NAME + ')' + XML_EQ + '(' + XML10_ATT_VALUE + ')';

// XML 1.1 tokens.
// TODO(jtakagi): NameStartChar also includes \u10000-\ueffff.
// ECMAScript Language Specifiction defines UnicodeEscapeSequence as
// "\u HexDigit HexDigit HexDigit HexDigit" and we may need to use
// surrogate pairs, but any browser doesn't support surrogate paris in
// character classes of regular expression, so avoid including them for now.

var XML11_VERSION_INFO = XML_S + 'version' + XML_EQ + '("1\\.1"|' + "'1\\.1')";
var XML11_NAME_START_CHAR = (REGEXP_UNICODE) ? ':A-Z_a-z\u00c0-\u00d6\u00d8-\u00f6\u00f8-\u02ff\u0370-\u037d' +
'\u037f-\u1fff\u200c-\u200d\u2070-\u218f\u2c00-\u2fef\u3001-\ud7ff' +
'\uf900-\ufdcf\ufdf0-\ufffd' : ':A-Z_a-z';
var XML11_NAME_CHAR = XML11_NAME_START_CHAR +
((REGEXP_UNICODE) ? '\\.0-9\u00b7\u0300-\u036f\u203f-\u2040-' : '\\.0-9-');
var XML11_NAME = '[' + XML11_NAME_START_CHAR + '][' + XML11_NAME_CHAR + ']*';

var XML11_ENTITY_REF = '&' + XML11_NAME + ';';
var XML11_REFERENCE = XML11_ENTITY_REF + '|' + XML_CHAR_REF;
var XML11_ATT_VALUE = '"(([^<&"]|' + XML11_REFERENCE + ')*)"|' +
"'(([^<&']|" +
XML11_REFERENCE +
")*)'";
var XML11_ATTRIBUTE = '(' + XML11_NAME + ')' + XML_EQ + '(' + XML11_ATT_VALUE + ')';

// XML Namespace tokens.
// Used in XML parser and XPath parser.

var XML_NC_NAME_CHAR = XML10_LETTER + XML10_DIGIT + '\\._' +
XML10_COMBINING_CHAR +
XML10_EXTENDER +
'-';
var XML_NC_NAME = '[' + XML10_LETTER + '_][' + XML_NC_NAME_CHAR + ']*';


// Code from dom.js.
//
// 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;

// Code from util.js.
//
// Copyright 2005 Google
//
// Author: Steffen Meschkat <mesch@google.com>
//
// Miscellaneous utility and placeholder functions.

// Dummy implmentation for the logging functions. Replace by something
// useful when you want to debug.
function xpathLog(msg){
};
function xsltLog(msg){
};
function xsltLogXml(msg){
};

// Throws an exception if false.
function assert(b){
    if (!b) {
        throw "Assertion failed";
    }
}

// Splits 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;
}

// Applies the given function to each element of the array, preserving
// this, and passing the index.
function mapExec(array, func){
    for (var i = 0; i < array.length; ++i) {
        func.call(this, array[i], 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;
    }
}

// Removes value from array. Returns the number of instances of value
// that were removed from array.
function removeFromArray(array, value, opt_notype){
    var shift = 0;
    for (var i = 0; i < array.length; ++i) {
        if (array[i] === value || (opt_notype && array[i] == value)) {
            array.splice(i--, 1);
            shift++;
        }
    }
    return shift;
}

// Shallow-copies an array.
function copyArray(dst, src){
    for (var i = 0; i < src.length; ++i) {
        dst.push(src[i]);
    }
}

// Returns the text value of 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;
}

// Code from xpath.js.
//
// 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.
//
//
// 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){
    xpathLog('parse ' + expr);
    xpathParseInit();
    
    var cached = xpathCacheLookup(expr);
    if (cached) {
        xpathLog(' ... 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;
        xpathLog(' ... simple');
        return ret;
    }
    
    if (expr.match(/^\w+(\/\w+)*$/i)) {
        var ret = makeSimpleExpr2(expr);
        xpathParseCache[expr] = ret;
        xpathLog(' ... simple 2');
        return ret;
    }
    
    var cachekey = expr; // expr is modified during parse
    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);
            xpathLog('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 {
            xpathLog('DONE');
            done = true;
        }
        
        while (xpathReduce(stack, ahead)) {
            reduce_count++;
            xpathLog('stack: ' + stackToString(stack));
        }
    }
    
    xpathLog('stack: ' + stackToString(stack));
    
    if (stack.length != 1) {
        throw 'XPath parse error ' + cachekey + ':\n' + stackToString(stack);
    }
    
    var result = stack[0].expr;
    xpathParseCache[cachekey] = result;
    
    xpathLog('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();
        }
        
        xpathLog('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) {
            xpathLog('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(position) -- sets the context to the node at the given
//   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, opt_position, opt_nodelist, opt_parent){
    this.node = node;
    this.position = opt_position || 0;
    this.nodelist = opt_nodelist || [node];
    this.variables = {};
    this.parent = opt_parent || null;
    if (opt_parent) {
        this.root = opt_parent.root;
    }
    else 
        if (this.node.nodeType == DOM_DOCUMENT_NODE) {
            // NOTE(mesch): DOM Spec stipulates that the ownerDocument of a
            // document is null. Our root, however is the document that we are
            // processing, so the initial context is created from its document
            // node, which case we must handle here explcitly.
            this.root = node;
        }
        else {
            this.root = node.ownerDocument;
        }
}

ExprContext.prototype.clone = function(opt_node, opt_position, opt_nodelist){
    return new ExprContext(opt_node || this.node, typeof opt_position != 'undefined' ? opt_position : this.position, opt_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(position){
    this.node = this.nodelist[position];
    this.position = position;
};

ExprContext.prototype.contextSize = function(){
    return this.nodelist.length;
};


// 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;
};

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;
};

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;
};

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, opt_predicate){
    this.axis = axis;
    this.nodetest = nodetest;
    this.predicate = opt_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 = n.parentNode) {
            nodelist.push(n);
        }
        
    }
    else 
        if (this.axis == xpathAxis.ANCESTOR) {
            for (var n = input.parentNode; n; n = n.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; 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 = n.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; 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 = n.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 NodeTestElementOrAttribute(){
}

NodeTestElementOrAttribute.prototype.evaluate = function(ctx){
    return new BooleanValue(ctx.node.nodeType == DOM_ELEMENT_NODE ||
    ctx.node.nodeType == DOM_ATTRIBUTE_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;
    return new BooleanValue(n.nodeName == this.name);
};

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 {
        xpathLog('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.contextSize());
    },
    
    '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[0].evaluate(ctx);
        var ret = [];
        var ids;
        if (e.type == 'node-set') {
            ids = [];
            var en = e.nodeSetValue();
            for (var i = 0; i < en.length; ++i) {
                var v = xmlValue(en[i]).split(/\s+/);
                for (var ii = 0; ii < v.length; ++ii) {
                    ids.push(v[ii]);
                }
            }
        }
        else {
            ids = e.stringValue().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-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) {
        var n = nodes2[i2];
        var inBoth = false;
        for (var i1 = 0; i1 < I1; ++i1) {
            if (nodes1[i1] == n) {
                inBoth = true;
                i1 = I1; // break inner loop
            }
        }
        if (!inBoth) {
            nodes1.push(n);
        }
    }
    return new NodeSetValue(nodes1);
};

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 NodeTestElementOrAttribute;
}

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;
    }
    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 = stringSplit(expr, '/');
    var c = new LocationExpr();
    for (var i = 0; i < steps.length; ++i) {
        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('^' + XML_NC_NAME)
};

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('^(' + XML_NC_NAME + ':)?' + XML_NC_NAME)
};

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++;
    }
    
    xpathLog('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;
                }
        }
    }
    
    xpathLog('XPath parse INIT: ' + xpathRules.length + ' rule bins');
    
    var sum = 0;
    mapExec(xpathRules, function(i){
        if (i) {
            sum += i.length;
        }
    });
    
    xpathLog('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.contextSize(); ++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(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;
}


// Parses and then evaluates the given XPath expression in the given
// input context. Notice that parsed xpath expressions are cached.
function xpathEval(select, context){
    var expr = xpathParse(select);
    var ret = expr.evaluate(context);
    return ret;
}