/* xpath.js - Revision: Spry Preview Release 1.4 */



// Copyright (c) 2005, Google Inc.

// All rights reserved.

// 

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

//         

//  * Redistributions of source code must retain the above copyright

//    notice, this list of conditions and the following disclaimer.

// 

//  * Redistributions in binary form must reproduce the above copyright

//    notice, this list of conditions and the following disclaimer in the

//    documentation and/or other materials provided with the

//    distribution.

// 

//  * Neither the name of Google Inc. nor the names of its contributors

//    may be used to endorse or promote products derived from this

//    software without specific prior written permission.

// 

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

//

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

  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 {

    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 = 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('^[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++;

  }



  if (xpathdebug)

  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;

      }

    }

  }



  if (xpathdebug)

  Log.write('XPath parse INIT: ' + xpathRules.length + ' rule bins');

  

  var sum = 0;

  mapExec(xpathRules, function(i) {

    if (i) {

      sum += i.length;

    }

  });

  

  if (xpathdebug)

  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;

}





// Copyright (c) 2005, Google Inc.

// All rights reserved.

// 

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

//         

//  * Redistributions of source code must retain the above copyright

//    notice, this list of conditions and the following disclaimer.

// 

//  * Redistributions in binary form must reproduce the above copyright

//    notice, this list of conditions and the following disclaimer in the

//    documentation and/or other materials provided with the

//    distribution.

// 

//  * Neither the name of Google Inc. nor the names of its contributors

//    may be used to endorse or promote products derived from this

//    software without specific prior written permission.

// 

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

//

// 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, '&amp;').replace(/</g, '&lt;').replace(/>/g, '&gt;');

}



// 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, '&quot;');

}



// 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, '&lt;').replace(/>/g, '&gt;');

}



// An implementation of the debug log. 



var logging__ = true;



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() {}