HuasoFoundries / phpPgAdmin6

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

    xpathParseCache[expr] = ret;

    xpathLog(' ... simple 2');

    return ret;

  }

  var cachekey = expr; // expr is modified during parse

  var stack = [];

  var ahead = 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));

  // DGF any valid XPath should "reduce" to a single Expr token

  if (stack.length != 1) {

    throw 'XPath parse error ' + cachekey + ':\n' + stackToString(stack);

  }

  xpathParseCache[cachekey] = result;

  xpathLog('XPath parse: ' + parse_count + ' / ' +

           lexer_count + ' / ' + reduce_count);

  return result;

}

var xpathParseCache = {};

function xpathCacheLookup(expr) {

  return xpathParseCache[expr];

}

/*DGF xpathReduce is where the magic happens in this parser.

Skim down to the bottom of this file to find the table of 

grammatical rules and precedence numbers, "The productions of the grammar".

The idea here

is that we want to take a stack of tokens and apply

grammatical rules to them, "reducing" them to higher-level

tokens.  Ultimately, any valid XPath should reduce to exactly one

"Expr" token.

Reduce too early or too late and you'll have two tokens that can't reduce

to single Expr.  For example, you may hastily reduce a qname that

should name a function, incorrectly treating it as a tag name.

Or you may reduce too late, accidentally reducing the last part of the

XPath into a top-level "Expr" that won't reduce with earlier parts of

the XPath.

A "cand" is a grammatical rule candidate, with a given precedence

number.  "ahead" is the upcoming token, which also has a precedence

number.  If the token has a higher precedence number than

the rule candidate, we'll "shift" the token onto the token stack,

instead of immediately applying the rule candidate.

Some tokens have left associativity, in which case we shift when they

have LOWER precedence than the candidate.

*/

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

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

    xpathLog('going to apply ' + cand.rule[3].toString());

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

      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.)

//

//   set/isCaseInsensitive -- specifies whether node name tests should

//   be case sensitive.  If you're executing xpaths against a regular

//   HTML DOM, you probably don't want case-sensitivity, because

//   browsers tend to disagree about whether elements & attributes

//   should be upper/lower case.  If you're running xpaths in an

//   XSLT instance, you probably DO want case sensitivity, as per the

//   XSL spec.

//

//   set/isReturnOnFirstMatch -- whether XPath evaluation should quit as soon

//   as a result is found. This is an optimization that might make sense if you

//   only care about the first result.

//

//   set/isIgnoreNonElementNodesForNTA -- whether to ignore non-element nodes

//   when evaluating the "node()" any node test. While technically this is

//   contrary to the XPath spec, practically it can enhance performance

//   significantly, and makes sense if you a) use "node()" when you mean "*",

//   and b) use "//" when you mean "/descendant::*/".

function ExprContext(node, opt_position, opt_nodelist, opt_parent,

  opt_caseInsensitive, opt_ignoreAttributesWithoutValue,

  opt_returnOnFirstMatch, opt_ignoreNonElementNodesForNTA)

{

  this.node = node;

  this.position = opt_position || 0;

  this.nodelist = opt_nodelist || [ node ];

  this.variables = {};

  this.parent = opt_parent || null;

  this.caseInsensitive = opt_caseInsensitive || false;

  this.ignoreAttributesWithoutValue = opt_ignoreAttributesWithoutValue || false;

  this.returnOnFirstMatch = opt_returnOnFirstMatch || false;

  this.ignoreNonElementNodesForNTA = opt_ignoreNonElementNodesForNTA || false;

  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, this.caseInsensitive,

      this.ignoreAttributesWithoutValue, this.returnOnFirstMatch,

      this.ignoreNonElementNodesForNTA);

};

ExprContext.prototype.setVariable = function(name, value) {

  if (value instanceof StringValue || value instanceof BooleanValue || 

    value instanceof NumberValue || value instanceof NodeSetValue) {

    this.variables[name] = value;

    return;

  }

  if ('true' === value) {

    this.variables[name] = new BooleanValue(true);

  } else if ('false' === value) {

    this.variables[name] = new BooleanValue(false);

  } else if (TOK_NUMBER.re.test(value)) {

    this.variables[name] = new NumberValue(value);

  } else {

    // DGF What if it's null?

    this.variables[name] = new StringValue(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;

};

ExprContext.prototype.isCaseInsensitive = function() {

  return this.caseInsensitive;

};

ExprContext.prototype.setCaseInsensitive = function(caseInsensitive) {

  return this.caseInsensitive = caseInsensitive;

};

ExprContext.prototype.isIgnoreAttributesWithoutValue = function() {

  return this.ignoreAttributesWithoutValue;

};

ExprContext.prototype.setIgnoreAttributesWithoutValue = function(ignore) {

  return this.ignoreAttributesWithoutValue = ignore;

};

ExprContext.prototype.isReturnOnFirstMatch = function() {

  return this.returnOnFirstMatch;

};

ExprContext.prototype.setReturnOnFirstMatch = function(returnOnFirstMatch) {

  return this.returnOnFirstMatch = returnOnFirstMatch;

};

ExprContext.prototype.isIgnoreNonElementNodesForNTA = function() {

  return this.ignoreNonElementNodesForNTA;

};

ExprContext.prototype.setIgnoreNonElementNodesForNTA = function(ignoreNonElementNodesForNTA) {

  return this.ignoreNonElementNodesForNTA = ignoreNonElementNodesForNTA;

};

// 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) {

  var combinedStep = this._combineSteps(this.steps[this.steps.length-1], s);

  if (combinedStep) {

    this.steps[this.steps.length-1] = combinedStep;

  } else {

    this.steps.push(s);

  }

}

LocationExpr.prototype.prependStep = function(s) {

  var combinedStep = this._combineSteps(s, this.steps[0]);

  if (combinedStep) {

    this.steps[0] = combinedStep;

  } else {

    this.steps.unshift(s);

  }

};

// DGF try to combine two steps into one step (perf enhancement)

LocationExpr.prototype._combineSteps = function(prevStep, nextStep) {

  if (!prevStep) return null;

  if (!nextStep) return null;

  var hasPredicates = (prevStep.predicates && prevStep.predicates.length > 0);

  if (prevStep.nodetest instanceof NodeTestAny && !hasPredicates) {

    // maybe suitable to be combined

    if (prevStep.axis == xpathAxis.DESCENDANT_OR_SELF) {

      if (nextStep.axis == xpathAxis.CHILD) {

        // HBC - commenting out, because this is not a valid reduction

        //nextStep.axis = xpathAxis.DESCENDANT;

        //return nextStep;

      } else if (nextStep.axis == xpathAxis.SELF) {

        nextStep.axis = xpathAxis.DESCENDANT_OR_SELF;

        return nextStep;

      }

    } else if (prevStep.axis == xpathAxis.DESCENDANT) {

      if (nextStep.axis == xpathAxis.SELF) {

        nextStep.axis = xpathAxis.DESCENDANT;

        return nextStep;

      }

    }

  }

  return null;

}

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

  if (ctx.returnOnFirstMatch && !s.hasPositionalPredicate) {

    var nodelist = s.evaluate(ctx2).nodeSetValue();

    // the predicates were not processed in the last evaluate(), so that we can

    // process them here with the returnOnFirstMatch optimization. We do a

    // depth-first grab at any nodes that pass the predicate tests. There is no

    // way to optimize when predicates contain positional selectors, including

    // indexes or uses of the last() or position() functions, because they

    // typically require the entire nodelist for context. Process without

    // optimization if we encounter such selectors.

    var nLength = nodelist.length;

    var pLength = s.predicate.length;

    nodelistLoop:

    for (var i = 0; i < nLength; ++i) {

      var n = nodelist[i];

      for (var j = 0; j < pLength; ++j) {

        if (!s.predicate[j].evaluate(ctx.clone(n, i, nodelist)).booleanValue()) {

          continue nodelistLoop;

        }

      }

      // n survived the predicate tests!

      if (step == steps.length - 1) {

        nodes.push(n);

      }

      else {

        xPathStep(nodes, steps, step + 1, n, ctx);

      }

      if (nodes.length > 0) {

        break;

      }

    }

  }

  else {

    // set returnOnFirstMatch to false for the cloned ExprContext, because

    // behavior in StepExpr.prototype.evaluate is driven off its value. Note

    // that the original context may still have true for this value.

    ctx2.returnOnFirstMatch = false;

      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 || [];

  this.hasPositionalPredicate = false;

  for (var i = 0; i < this.predicate.length; ++i) {

    if (predicateExprHasPositionalSelector(this.predicate[i].expr)) {

      this.hasPositionalPredicate = true;

      break;

    }

  }

}

StepExpr.prototype.appendPredicate = function(p) {

  this.predicate.push(p);

  if (!this.hasPositionalPredicate) {

    this.hasPositionalPredicate = predicateExprHasPositionalSelector(p.expr);

  }

}

StepExpr.prototype.evaluate = function(ctx) {

  var input = ctx.node;

  var nodelist = [];

  var skipNodeTest = false;

  if (this.nodetest instanceof NodeTestAny) {

    skipNodeTest = true;

  }

  // 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) {

      nodelist.push(n);

    }

  } else if (this.axis == xpathAxis.ATTRIBUTE) {

    if (this.nodetest.name != undefined) {

      // single-attribute step

      if (input.attributes) {

        if (input.attributes instanceof Array) {

          // probably evaluating on document created by xmlParse()

          copyArray(nodelist, input.attributes);

        }

        else {

          if (this.nodetest.name == 'style') {

            var value = input.getAttribute('style');

            if (value && typeof(value) != 'string') {

              // this is the case where indexing into the attributes array

              // doesn't give us the attribute node in IE - we create our own

              // node instead

              nodelist.push(XNode.create(DOM_ATTRIBUTE_NODE, 'style',

                value.cssText, document));

            }

            else {

              nodelist.push(input.attributes[this.nodetest.name]);

            }

          }

          else {

            nodelist.push(input.attributes[this.nodetest.name]);

          }

        }

      }