1
// Copyright 2005 Google Inc.
4
// An XPath parser and evaluator written in JavaScript. The
5
// implementation is complete except for functions handling
8
// Reference: [XPATH] XPath Specification
9
// <http://www.w3.org/TR/1999/REC-xpath-19991116>.
12
// The API of the parser has several parts:
14
// 1. The parser function xpathParse() that takes a string and returns
15
// an expession object.
17
// 2. The expression object that has an evaluate() method to evaluate the
18
// XPath expression it represents. (It is actually a hierarchy of
19
// objects that resembles the parse tree, but an application will call
20
// evaluate() only on the top node of this hierarchy.)
22
// 3. The context object that is passed as an argument to the evaluate()
23
// method, which represents the DOM context in which the expression is
26
// 4. The value object that is returned from evaluate() and represents
27
// values of the different types that are defined by XPath (number,
28
// string, boolean, and node-set), and allows to convert between them.
30
// These parts are near the top of the file, the functions and data
31
// that are used internally follow after them.
34
// Author: Steffen Meschkat <mesch@google.com>
37
// The entry point for the parser.
39
// @param expr a string that contains an XPath expression.
40
// @return an expression object that can be evaluated with an
41
// expression context.
43
function xpathParse(expr) {
44
xpathLog('parse ' + expr);
47
var cached = xpathCacheLookup(expr);
49
xpathLog(' ... cached');
53
// Optimize for a few common cases: simple attribute node tests
54
// (@id), simple element node tests (page), variable references
55
// ($address), numbers (4), multi-step path expressions where each
56
// step is a plain element node test
57
// (page/overlay/locations/location).
59
if (expr.match(/^(\$|@)?\w+$/i)) {
60
var ret = makeSimpleExpr(expr);
61
xpathParseCache[expr] = ret;
62
xpathLog(' ... simple');
66
if (expr.match(/^\w+(\/\w+)*$/i)) {
67
var ret = makeSimpleExpr2(expr);
68
xpathParseCache[expr] = ret;
69
xpathLog(' ... simple 2');
73
var cachekey = expr; // expr is modified during parse
86
expr = expr.replace(/^\s*/, '');
92
for (var i = 0; i < xpathTokenRules.length; ++i) {
93
var result = xpathTokenRules[i].re.exec(expr);
95
if (result && result.length > 0 && result[0].length > match.length) {
96
rule = xpathTokenRules[i];
102
// Special case: allow operator keywords to be element and
105
// NOTE(mesch): The parser resolves conflicts by looking ahead,
106
// and this is the only case where we look back to
107
// disambiguate. So this is indeed something different, and
108
// looking back is usually done in the lexer (via states in the
109
// general case, called "start conditions" in flex(1)). Also,the
110
// conflict resolution in the parser is not as robust as it could
111
// be, so I'd like to keep as much off the parser as possible (all
112
// these precedence values should be computed from the grammar
113
// rules and possibly associativity declarations, as in bison(1),
114
// and not explicitly set.
122
previous.tag == TOK_AT ||
123
previous.tag == TOK_DSLASH ||
124
previous.tag == TOK_SLASH ||
125
previous.tag == TOK_AXIS ||
126
previous.tag == TOK_DOLLAR)) {
131
expr = expr.substr(match.length);
132
xpathLog('token: ' + match + ' -- ' + rule.label);
136
prec: rule.prec ? rule.prec : 0, // || 0 is removed by the compiler
137
expr: makeTokenExpr(match)
145
while (xpathReduce(stack, ahead)) {
147
xpathLog('stack: ' + stackToString(stack));
151
xpathLog('stack: ' + stackToString(stack));
153
// DGF any valid XPath should "reduce" to a single Expr token
154
if (stack.length != 1) {
155
throw 'XPath parse error ' + cachekey + ':\n' + stackToString(stack);
158
var result = stack[0].expr;
159
xpathParseCache[cachekey] = result;
161
xpathLog('XPath parse: ' + parse_count + ' / ' +
162
lexer_count + ' / ' + reduce_count);
167
var xpathParseCache = {};
169
function xpathCacheLookup(expr) {
170
return xpathParseCache[expr];
173
/*DGF xpathReduce is where the magic happens in this parser.
174
Skim down to the bottom of this file to find the table of
175
grammatical rules and precedence numbers, "The productions of the grammar".
178
is that we want to take a stack of tokens and apply
179
grammatical rules to them, "reducing" them to higher-level
180
tokens. Ultimately, any valid XPath should reduce to exactly one
183
Reduce too early or too late and you'll have two tokens that can't reduce
184
to single Expr. For example, you may hastily reduce a qname that
185
should name a function, incorrectly treating it as a tag name.
186
Or you may reduce too late, accidentally reducing the last part of the
187
XPath into a top-level "Expr" that won't reduce with earlier parts of
190
A "cand" is a grammatical rule candidate, with a given precedence
191
number. "ahead" is the upcoming token, which also has a precedence
192
number. If the token has a higher precedence number than
193
the rule candidate, we'll "shift" the token onto the token stack,
194
instead of immediately applying the rule candidate.
196
Some tokens have left associativity, in which case we shift when they
197
have LOWER precedence than the candidate.
199
function xpathReduce(stack, ahead) {
202
if (stack.length > 0) {
203
var top = stack[stack.length-1];
204
var ruleset = xpathRules[top.tag.key];
207
for (var i = 0; i < ruleset.length; ++i) {
208
var rule = ruleset[i];
209
var match = xpathMatchStack(stack, rule[1]);
216
cand.prec = xpathGrammarPrecedence(cand);
224
if (cand && (!ahead || cand.prec > ahead.prec ||
225
(ahead.tag.left && cand.prec >= ahead.prec))) {
226
for (var i = 0; i < cand.match.matchlength; ++i) {
230
xpathLog('reduce ' + cand.tag.label + ' ' + cand.prec +
231
' ahead ' + (ahead ? ahead.tag.label + ' ' + ahead.prec +
232
(ahead.tag.left ? ' left' : '')
235
var matchexpr = mapExpr(cand.match, function(m) { return m.expr; });
236
xpathLog('going to apply ' + cand.rule[3].toString());
237
cand.expr = cand.rule[3].apply(null, matchexpr);
244
xpathLog('shift ' + ahead.tag.label + ' ' + ahead.prec +
245
(ahead.tag.left ? ' left' : '') +
246
' over ' + (cand ? cand.tag.label + ' ' +
247
cand.prec : ' none'));
255
function xpathMatchStack(stack, pattern) {
257
// NOTE(mesch): The stack matches for variable cardinality are
258
// greedy but don't do backtracking. This would be an issue only
259
// with rules of the form A* A, i.e. with an element with variable
260
// cardinality followed by the same element. Since that doesn't
261
// occur in the grammar at hand, all matches on the stack are
264
var S = stack.length;
265
var P = pattern.length;
268
match.matchlength = 0;
270
for (p = P - 1, s = S - 1; p >= 0 && s >= 0; --p, s -= ds) {
273
if (pattern[p] == Q_MM) {
276
while (s - ds >= 0 && stack[s - ds].tag == pattern[p]) {
277
qmatch.push(stack[s - ds]);
279
match.matchlength += 1;
282
} else if (pattern[p] == Q_01) {
285
while (s - ds >= 0 && ds < 2 && stack[s - ds].tag == pattern[p]) {
286
qmatch.push(stack[s - ds]);
288
match.matchlength += 1;
291
} else if (pattern[p] == Q_1M) {
294
if (stack[s].tag == pattern[p]) {
295
while (s - ds >= 0 && stack[s - ds].tag == pattern[p]) {
296
qmatch.push(stack[s - ds]);
298
match.matchlength += 1;
304
} else if (stack[s].tag == pattern[p]) {
305
match.push(stack[s]);
307
match.matchlength += 1;
313
reverseInplace(qmatch);
314
qmatch.expr = mapExpr(qmatch, function(m) { return m.expr; });
317
reverseInplace(match);
327
function xpathTokenPrecedence(tag) {
328
return tag.prec || 2;
331
function xpathGrammarPrecedence(frame) {
334
if (frame.rule) { /* normal reduce */
335
if (frame.rule.length >= 3 && frame.rule[2] >= 0) {
339
for (var i = 0; i < frame.rule[1].length; ++i) {
340
var p = xpathTokenPrecedence(frame.rule[1][i]);
341
ret = Math.max(ret, p);
344
} else if (frame.tag) { /* TOKEN match */
345
ret = xpathTokenPrecedence(frame.tag);
347
} else if (frame.length) { /* Q_ match */
348
for (var j = 0; j < frame.length; ++j) {
349
var p = xpathGrammarPrecedence(frame[j]);
350
ret = Math.max(ret, p);
357
function stackToString(stack) {
359
for (var i = 0; i < stack.length; ++i) {
363
ret += stack[i].tag.label;
369
// XPath expression evaluation context. An XPath context consists of a
370
// DOM node, a list of DOM nodes that contains this node, a number
371
// that represents the position of the single node in the list, and a
372
// current set of variable bindings. (See XPath spec.)
374
// The interface of the expression context:
376
// Constructor -- gets the node, its position, the node set it
377
// belongs to, and a parent context as arguments. The parent context
378
// is used to implement scoping rules for variables: if a variable
379
// is not found in the current context, it is looked for in the
380
// parent context, recursively. Except for node, all arguments have
381
// default values: default position is 0, default node set is the
382
// set that contains only the node, and the default parent is null.
384
// Notice that position starts at 0 at the outside interface;
385
// inside XPath expressions this shows up as position()=1.
387
// clone() -- creates a new context with the current context as
388
// parent. If passed as argument to clone(), the new context has a
389
// different node, position, or node set. What is not passed is
390
// inherited from the cloned context.
392
// setVariable(name, expr) -- binds given XPath expression to the
395
// getVariable(name) -- what the name says.
397
// setNode(position) -- sets the context to the node at the given
398
// position. Needed to implement scoping rules for variables in
399
// XPath. (A variable is visible to all subsequent siblings, not
400
// only to its children.)
402
// set/isCaseInsensitive -- specifies whether node name tests should
403
// be case sensitive. If you're executing xpaths against a regular
404
// HTML DOM, you probably don't want case-sensitivity, because
405
// browsers tend to disagree about whether elements & attributes
406
// should be upper/lower case. If you're running xpaths in an
407
// XSLT instance, you probably DO want case sensitivity, as per the
410
// set/isReturnOnFirstMatch -- whether XPath evaluation should quit as soon
411
// as a result is found. This is an optimization that might make sense if you
412
// only care about the first result.
414
// set/isIgnoreNonElementNodesForNTA -- whether to ignore non-element nodes
415
// when evaluating the "node()" any node test. While technically this is
416
// contrary to the XPath spec, practically it can enhance performance
417
// significantly, and makes sense if you a) use "node()" when you mean "*",
418
// and b) use "//" when you mean "/descendant::*/".
420
function ExprContext(node, opt_position, opt_nodelist, opt_parent,
421
opt_caseInsensitive, opt_ignoreAttributesWithoutValue,
422
opt_returnOnFirstMatch, opt_ignoreNonElementNodesForNTA)
425
this.position = opt_position || 0;
426
this.nodelist = opt_nodelist || [ node ];
428
this.parent = opt_parent || null;
429
this.caseInsensitive = opt_caseInsensitive || false;
430
this.ignoreAttributesWithoutValue = opt_ignoreAttributesWithoutValue || false;
431
this.returnOnFirstMatch = opt_returnOnFirstMatch || false;
432
this.ignoreNonElementNodesForNTA = opt_ignoreNonElementNodesForNTA || false;
434
this.root = opt_parent.root;
435
} else if (this.node.nodeType == DOM_DOCUMENT_NODE) {
436
// NOTE(mesch): DOM Spec stipulates that the ownerDocument of a
437
// document is null. Our root, however is the document that we are
438
// processing, so the initial context is created from its document
439
// node, which case we must handle here explcitly.
442
this.root = node.ownerDocument;
446
ExprContext.prototype.clone = function(opt_node, opt_position, opt_nodelist) {
447
return new ExprContext(
448
opt_node || this.node,
449
typeof opt_position != 'undefined' ? opt_position : this.position,
450
opt_nodelist || this.nodelist, this, this.caseInsensitive,
451
this.ignoreAttributesWithoutValue, this.returnOnFirstMatch,
452
this.ignoreNonElementNodesForNTA);
455
ExprContext.prototype.setVariable = function(name, value) {
456
if (value instanceof StringValue || value instanceof BooleanValue ||
457
value instanceof NumberValue || value instanceof NodeSetValue) {
458
this.variables[name] = value;
461
if ('true' === value) {
462
this.variables[name] = new BooleanValue(true);
463
} else if ('false' === value) {
464
this.variables[name] = new BooleanValue(false);
465
} else if (TOK_NUMBER.re.test(value)) {
466
this.variables[name] = new NumberValue(value);
468
// DGF What if it's null?
469
this.variables[name] = new StringValue(value);
473
ExprContext.prototype.getVariable = function(name) {
474
if (typeof this.variables[name] != 'undefined') {
475
return this.variables[name];
477
} else if (this.parent) {
478
return this.parent.getVariable(name);
485
ExprContext.prototype.setNode = function(position) {
486
this.node = this.nodelist[position];
487
this.position = position;
490
ExprContext.prototype.contextSize = function() {
491
return this.nodelist.length;
494
ExprContext.prototype.isCaseInsensitive = function() {
495
return this.caseInsensitive;
498
ExprContext.prototype.setCaseInsensitive = function(caseInsensitive) {
499
return this.caseInsensitive = caseInsensitive;
502
ExprContext.prototype.isIgnoreAttributesWithoutValue = function() {
503
return this.ignoreAttributesWithoutValue;
506
ExprContext.prototype.setIgnoreAttributesWithoutValue = function(ignore) {
507
return this.ignoreAttributesWithoutValue = ignore;
510
ExprContext.prototype.isReturnOnFirstMatch = function() {
511
return this.returnOnFirstMatch;
514
ExprContext.prototype.setReturnOnFirstMatch = function(returnOnFirstMatch) {
515
return this.returnOnFirstMatch = returnOnFirstMatch;
518
ExprContext.prototype.isIgnoreNonElementNodesForNTA = function() {
519
return this.ignoreNonElementNodesForNTA;
522
ExprContext.prototype.setIgnoreNonElementNodesForNTA = function(ignoreNonElementNodesForNTA) {
523
return this.ignoreNonElementNodesForNTA = ignoreNonElementNodesForNTA;
526
// XPath expression values. They are what XPath expressions evaluate
527
// to. Strangely, the different value types are not specified in the
528
// XPath syntax, but only in the semantics, so they don't show up as
529
// nonterminals in the grammar. Yet, some expressions are required to
530
// evaluate to particular types, and not every type can be coerced
531
// into every other type. Although the types of XPath values are
532
// similar to the types present in JavaScript, the type coercion rules
533
// are a bit peculiar, so we explicitly model XPath types instead of
534
// mapping them onto JavaScript types. (See XPath spec.)
536
// The four types are:
546
// The common interface of the value classes consists of methods that
547
// implement the XPath type coercion rules:
549
// stringValue() -- returns the value as a JavaScript String,
551
// numberValue() -- returns the value as a JavaScript Number,
553
// booleanValue() -- returns the value as a JavaScript Boolean,
555
// nodeSetValue() -- returns the value as a JavaScript Array of DOM
559
function StringValue(value) {
561
this.type = 'string';
564
StringValue.prototype.stringValue = function() {
568
StringValue.prototype.booleanValue = function() {
569
return this.value.length > 0;
572
StringValue.prototype.numberValue = function() {
573
return this.value - 0;
576
StringValue.prototype.nodeSetValue = function() {
580
function BooleanValue(value) {
582
this.type = 'boolean';
585
BooleanValue.prototype.stringValue = function() {
586
return '' + this.value;
589
BooleanValue.prototype.booleanValue = function() {
593
BooleanValue.prototype.numberValue = function() {
594
return this.value ? 1 : 0;
597
BooleanValue.prototype.nodeSetValue = function() {
601
function NumberValue(value) {
603
this.type = 'number';
606
NumberValue.prototype.stringValue = function() {
607
return '' + this.value;
610
NumberValue.prototype.booleanValue = function() {
614
NumberValue.prototype.numberValue = function() {
615
return this.value - 0;
618
NumberValue.prototype.nodeSetValue = function() {
622
function NodeSetValue(value) {
624
this.type = 'node-set';
627
NodeSetValue.prototype.stringValue = function() {
628
if (this.value.length == 0) {
631
return xmlValue(this.value[0]);
635
NodeSetValue.prototype.booleanValue = function() {
636
return this.value.length > 0;
639
NodeSetValue.prototype.numberValue = function() {
640
return this.stringValue() - 0;
643
NodeSetValue.prototype.nodeSetValue = function() {
647
// XPath expressions. They are used as nodes in the parse tree and
648
// possess an evaluate() method to compute an XPath value given an XPath
649
// context. Expressions are returned from the parser. Teh set of
650
// expression classes closely mirrors the set of non terminal symbols
651
// in the grammar. Every non trivial nonterminal symbol has a
652
// corresponding expression class.
654
// The common expression interface consists of the following methods:
656
// evaluate(context) -- evaluates the expression, returns a value.
658
// toString() -- returns the XPath text representation of the
659
// expression (defined in xsltdebug.js).
661
// parseTree(indent) -- returns a parse tree representation of the
662
// expression (defined in xsltdebug.js).
664
function TokenExpr(m) {
668
TokenExpr.prototype.evaluate = function() {
669
return new StringValue(this.value);
672
function LocationExpr() {
673
this.absolute = false;
677
LocationExpr.prototype.appendStep = function(s) {
678
var combinedStep = this._combineSteps(this.steps[this.steps.length-1], s);
680
this.steps[this.steps.length-1] = combinedStep;
686
LocationExpr.prototype.prependStep = function(s) {
687
var combinedStep = this._combineSteps(s, this.steps[0]);
689
this.steps[0] = combinedStep;
691
this.steps.unshift(s);
695
// DGF try to combine two steps into one step (perf enhancement)
696
LocationExpr.prototype._combineSteps = function(prevStep, nextStep) {
697
if (!prevStep) return null;
698
if (!nextStep) return null;
699
var hasPredicates = (prevStep.predicates && prevStep.predicates.length > 0);
700
if (prevStep.nodetest instanceof NodeTestAny && !hasPredicates) {
701
// maybe suitable to be combined
702
if (prevStep.axis == xpathAxis.DESCENDANT_OR_SELF) {
703
if (nextStep.axis == xpathAxis.CHILD) {
704
// HBC - commenting out, because this is not a valid reduction
705
//nextStep.axis = xpathAxis.DESCENDANT;
707
} else if (nextStep.axis == xpathAxis.SELF) {
708
nextStep.axis = xpathAxis.DESCENDANT_OR_SELF;
711
} else if (prevStep.axis == xpathAxis.DESCENDANT) {
712
if (nextStep.axis == xpathAxis.SELF) {
713
nextStep.axis = xpathAxis.DESCENDANT;
721
LocationExpr.prototype.evaluate = function(ctx) {
731
xPathStep(nodes, this.steps, 0, start, ctx);
732
return new NodeSetValue(nodes);
735
function xPathStep(nodes, steps, step, input, ctx) {
737
var ctx2 = ctx.clone(input);
739
if (ctx.returnOnFirstMatch && !s.hasPositionalPredicate) {
740
var nodelist = s.evaluate(ctx2).nodeSetValue();
741
// the predicates were not processed in the last evaluate(), so that we can
742
// process them here with the returnOnFirstMatch optimization. We do a
743
// depth-first grab at any nodes that pass the predicate tests. There is no
744
// way to optimize when predicates contain positional selectors, including
745
// indexes or uses of the last() or position() functions, because they
746
// typically require the entire nodelist for context. Process without
747
// optimization if we encounter such selectors.
748
var nLength = nodelist.length;
749
var pLength = s.predicate.length;
751
for (var i = 0; i < nLength; ++i) {
753
for (var j = 0; j < pLength; ++j) {
754
if (!s.predicate[j].evaluate(ctx.clone(n, i, nodelist)).booleanValue()) {
755
continue nodelistLoop;
758
// n survived the predicate tests!
759
if (step == steps.length - 1) {
763
xPathStep(nodes, steps, step + 1, n, ctx);
765
if (nodes.length > 0) {
771
// set returnOnFirstMatch to false for the cloned ExprContext, because
772
// behavior in StepExpr.prototype.evaluate is driven off its value. Note
773
// that the original context may still have true for this value.
774
ctx2.returnOnFirstMatch = false;
775
var nodelist = s.evaluate(ctx2).nodeSetValue();
776
for (var i = 0; i < nodelist.length; ++i) {
777
if (step == steps.length - 1) {
778
nodes.push(nodelist[i]);
780
xPathStep(nodes, steps, step + 1, nodelist[i], ctx);
786
function StepExpr(axis, nodetest, opt_predicate) {
788
this.nodetest = nodetest;
789
this.predicate = opt_predicate || [];
790
this.hasPositionalPredicate = false;
791
for (var i = 0; i < this.predicate.length; ++i) {
792
if (predicateExprHasPositionalSelector(this.predicate[i].expr)) {
793
this.hasPositionalPredicate = true;
799
StepExpr.prototype.appendPredicate = function(p) {
800
this.predicate.push(p);
801
if (!this.hasPositionalPredicate) {
802
this.hasPositionalPredicate = predicateExprHasPositionalSelector(p.expr);
806
StepExpr.prototype.evaluate = function(ctx) {
807
var input = ctx.node;
809
var skipNodeTest = false;
811
if (this.nodetest instanceof NodeTestAny) {
815
// NOTE(mesch): When this was a switch() statement, it didn't work
816
// in Safari/2.0. Not sure why though; it resulted in the JavaScript
817
// console output "undefined" (without any line number or so).
819
if (this.axis == xpathAxis.ANCESTOR_OR_SELF) {
820
nodelist.push(input);
821
for (var n = input.parentNode; n; n = n.parentNode) {
825
} else if (this.axis == xpathAxis.ANCESTOR) {
826
for (var n = input.parentNode; n; n = n.parentNode) {
830
} else if (this.axis == xpathAxis.ATTRIBUTE) {
831
if (this.nodetest.name != undefined) {
832
// single-attribute step
833
if (input.attributes) {
834
if (input.attributes instanceof Array) {
835
// probably evaluating on document created by xmlParse()
836
copyArray(nodelist, input.attributes);
839
if (this.nodetest.name == 'style') {
840
var value = input.getAttribute('style');
841
if (value && typeof(value) != 'string') {
842
// this is the case where indexing into the attributes array
843
// doesn't give us the attribute node in IE - we create our own
845
nodelist.push(XNode.create(DOM_ATTRIBUTE_NODE, 'style',
846
value.cssText, document));
849
nodelist.push(input.attributes[this.nodetest.name]);
853
nodelist.push(input.attributes[this.nodetest.name]);
859
// all-attributes step
860
if (ctx.ignoreAttributesWithoutValue) {
861
copyArrayIgnoringAttributesWithoutValue(nodelist, input.attributes);
864
copyArray(nodelist, input.attributes);
868
} else if (this.axis == xpathAxis.CHILD) {
869
copyArray(nodelist, input.childNodes);
871
} else if (this.axis == xpathAxis.DESCENDANT_OR_SELF) {
872
if (this.nodetest.evaluate(ctx).booleanValue()) {
873
nodelist.push(input);
875
var tagName = xpathExtractTagNameFromNodeTest(this.nodetest, ctx.ignoreNonElementNodesForNTA);
876
xpathCollectDescendants(nodelist, input, tagName);
877
if (tagName) skipNodeTest = true;
879
} else if (this.axis == xpathAxis.DESCENDANT) {
880
var tagName = xpathExtractTagNameFromNodeTest(this.nodetest, ctx.ignoreNonElementNodesForNTA);
881
xpathCollectDescendants(nodelist, input, tagName);
882
if (tagName) skipNodeTest = true;
884
} else if (this.axis == xpathAxis.FOLLOWING) {
885
for (var n = input; n; n = n.parentNode) {
886
for (var nn = n.nextSibling; nn; nn = nn.nextSibling) {
888
xpathCollectDescendants(nodelist, nn);
892
} else if (this.axis == xpathAxis.FOLLOWING_SIBLING) {
893
for (var n = input.nextSibling; n; n = n.nextSibling) {
897
} else if (this.axis == xpathAxis.NAMESPACE) {
898
alert('not implemented: axis namespace');
900
} else if (this.axis == xpathAxis.PARENT) {
901
if (input.parentNode) {
902
nodelist.push(input.parentNode);
905
} else if (this.axis == xpathAxis.PRECEDING) {
906
for (var n = input; n; n = n.parentNode) {
907
for (var nn = n.previousSibling; nn; nn = nn.previousSibling) {
909
xpathCollectDescendantsReverse(nodelist, nn);
913
} else if (this.axis == xpathAxis.PRECEDING_SIBLING) {
914
for (var n = input.previousSibling; n; n = n.previousSibling) {
918
} else if (this.axis == xpathAxis.SELF) {
919
nodelist.push(input);
922
throw 'ERROR -- NO SUCH AXIS: ' + this.axis;
927
var nodelist0 = nodelist;
929
for (var i = 0; i < nodelist0.length; ++i) {
930
var n = nodelist0[i];
931
if (this.nodetest.evaluate(ctx.clone(n, i, nodelist0)).booleanValue()) {
937
// process predicates
938
if (!ctx.returnOnFirstMatch) {
939
for (var i = 0; i < this.predicate.length; ++i) {
940
var nodelist0 = nodelist;
942
for (var ii = 0; ii < nodelist0.length; ++ii) {
943
var n = nodelist0[ii];
944
if (this.predicate[i].evaluate(ctx.clone(n, ii, nodelist0)).booleanValue()) {
951
return new NodeSetValue(nodelist);
954
function NodeTestAny() {
955
this.value = new BooleanValue(true);
958
NodeTestAny.prototype.evaluate = function(ctx) {
962
function NodeTestElementOrAttribute() {}
964
NodeTestElementOrAttribute.prototype.evaluate = function(ctx) {
965
return new BooleanValue(
966
ctx.node.nodeType == DOM_ELEMENT_NODE ||
967
ctx.node.nodeType == DOM_ATTRIBUTE_NODE);
970
function NodeTestText() {}
972
NodeTestText.prototype.evaluate = function(ctx) {
973
return new BooleanValue(ctx.node.nodeType == DOM_TEXT_NODE);
976
function NodeTestComment() {}
978
NodeTestComment.prototype.evaluate = function(ctx) {
979
return new BooleanValue(ctx.node.nodeType == DOM_COMMENT_NODE);
982
function NodeTestPI(target) {
983
this.target = target;
986
NodeTestPI.prototype.evaluate = function(ctx) {
988
BooleanValue(ctx.node.nodeType == DOM_PROCESSING_INSTRUCTION_NODE &&
989
(!this.target || ctx.node.nodeName == this.target));
992
function NodeTestNC(nsprefix) {
993
this.regex = new RegExp("^" + nsprefix + ":");
994
this.nsprefix = nsprefix;
997
NodeTestNC.prototype.evaluate = function(ctx) {
999
return new BooleanValue(this.regex.match(n.nodeName));
1002
function NodeTestName(name) {
1004
this.re = new RegExp('^' + name + '$', "i");
1007
NodeTestName.prototype.evaluate = function(ctx) {
1009
if (ctx.caseInsensitive) {
1010
if (n.nodeName.length != this.name.length) return new BooleanValue(false);
1011
return new BooleanValue(this.re.test(n.nodeName));
1013
return new BooleanValue(n.nodeName == this.name);
1017
function PredicateExpr(expr) {
1021
PredicateExpr.prototype.evaluate = function(ctx) {
1022
var v = this.expr.evaluate(ctx);
1023
if (v.type == 'number') {
1024
// NOTE(mesch): Internally, position is represented starting with
1025
// 0, however in XPath position starts with 1. See functions
1026
// position() and last().
1027
return new BooleanValue(ctx.position == v.numberValue() - 1);
1029
return new BooleanValue(v.booleanValue());
1033
function FunctionCallExpr(name) {
1038
FunctionCallExpr.prototype.appendArg = function(arg) {
1039
this.args.push(arg);
1042
FunctionCallExpr.prototype.evaluate = function(ctx) {
1043
var fn = '' + this.name.value;
1044
var f = this.xpathfunctions[fn];
1046
return f.call(this, ctx);
1048
xpathLog('XPath NO SUCH FUNCTION ' + fn);
1049
return new BooleanValue(false);
1053
FunctionCallExpr.prototype.xpathfunctions = {
1054
'last': function(ctx) {
1055
assert(this.args.length == 0);
1056
// NOTE(mesch): XPath position starts at 1.
1057
return new NumberValue(ctx.contextSize());
1060
'position': function(ctx) {
1061
assert(this.args.length == 0);
1062
// NOTE(mesch): XPath position starts at 1.
1063
return new NumberValue(ctx.position + 1);
1066
'count': function(ctx) {
1067
assert(this.args.length == 1);
1068
var v = this.args[0].evaluate(ctx);
1069
return new NumberValue(v.nodeSetValue().length);
1072
'id': function(ctx) {
1073
assert(this.args.length == 1);
1074
var e = this.args[0].evaluate(ctx);
1077
if (e.type == 'node-set') {
1079
var en = e.nodeSetValue();
1080
for (var i = 0; i < en.length; ++i) {
1081
var v = xmlValue(en[i]).split(/\s+/);
1082
for (var ii = 0; ii < v.length; ++ii) {
1087
ids = e.stringValue().split(/\s+/);
1090
for (var i = 0; i < ids.length; ++i) {
1091
var n = d.getElementById(ids[i]);
1096
return new NodeSetValue(ret);
1099
'local-name': function(ctx) {
1100
alert('not implmented yet: XPath function local-name()');
1103
'namespace-uri': function(ctx) {
1104
alert('not implmented yet: XPath function namespace-uri()');
1107
'name': function(ctx) {
1108
assert(this.args.length == 1 || this.args.length == 0);
1110
if (this.args.length == 0) {
1113
n = this.args[0].evaluate(ctx).nodeSetValue();
1116
if (n.length == 0) {
1117
return new StringValue('');
1119
return new StringValue(n[0].nodeName);
1123
'string': function(ctx) {
1124
assert(this.args.length == 1 || this.args.length == 0);
1125
if (this.args.length == 0) {
1126
return new StringValue(new NodeSetValue([ ctx.node ]).stringValue());
1128
return new StringValue(this.args[0].evaluate(ctx).stringValue());
1132
'concat': function(ctx) {
1134
for (var i = 0; i < this.args.length; ++i) {
1135
ret += this.args[i].evaluate(ctx).stringValue();
1137
return new StringValue(ret);
1140
'starts-with': function(ctx) {
1141
assert(this.args.length == 2);
1142
var s0 = this.args[0].evaluate(ctx).stringValue();
1143
var s1 = this.args[1].evaluate(ctx).stringValue();
1144
return new BooleanValue(s0.indexOf(s1) == 0);
1147
'ends-with': function(ctx) {
1148
assert(this.args.length == 2);
1149
var s0 = this.args[0].evaluate(ctx).stringValue();
1150
var s1 = this.args[1].evaluate(ctx).stringValue();
1151
var re = new RegExp(RegExp.escape(s1) + '$');
1152
return new BooleanValue(re.test(s0));
1155
'contains': function(ctx) {
1156
assert(this.args.length == 2);
1157
var s0 = this.args[0].evaluate(ctx).stringValue();
1158
var s1 = this.args[1].evaluate(ctx).stringValue();
1159
return new BooleanValue(s0.indexOf(s1) != -1);
1162
'substring-before': function(ctx) {
1163
assert(this.args.length == 2);
1164
var s0 = this.args[0].evaluate(ctx).stringValue();
1165
var s1 = this.args[1].evaluate(ctx).stringValue();
1166
var i = s0.indexOf(s1);
1171
ret = s0.substr(0,i);
1173
return new StringValue(ret);
1176
'substring-after': function(ctx) {
1177
assert(this.args.length == 2);
1178
var s0 = this.args[0].evaluate(ctx).stringValue();
1179
var s1 = this.args[1].evaluate(ctx).stringValue();
1180
var i = s0.indexOf(s1);
1185
ret = s0.substr(i + s1.length);
1187
return new StringValue(ret);
1190
'substring': function(ctx) {
1191
// NOTE: XPath defines the position of the first character in a
1192
// string to be 1, in JavaScript this is 0 ([XPATH] Section 4.2).
1193
assert(this.args.length == 2 || this.args.length == 3);
1194
var s0 = this.args[0].evaluate(ctx).stringValue();
1195
var s1 = this.args[1].evaluate(ctx).numberValue();
1197
if (this.args.length == 2) {
1198
var i1 = Math.max(0, Math.round(s1) - 1);
1199
ret = s0.substr(i1);
1202
var s2 = this.args[2].evaluate(ctx).numberValue();
1203
var i0 = Math.round(s1) - 1;
1204
var i1 = Math.max(0, i0);
1205
var i2 = Math.round(s2) - Math.max(0, -i0);
1206
ret = s0.substr(i1, i2);
1208
return new StringValue(ret);
1211
'string-length': function(ctx) {
1213
if (this.args.length > 0) {
1214
s = this.args[0].evaluate(ctx).stringValue();
1216
s = new NodeSetValue([ ctx.node ]).stringValue();
1218
return new NumberValue(s.length);
1221
'normalize-space': function(ctx) {
1223
if (this.args.length > 0) {
1224
s = this.args[0].evaluate(ctx).stringValue();
1226
s = new NodeSetValue([ ctx.node ]).stringValue();
1228
s = s.replace(/^\s*/,'').replace(/\s*$/,'').replace(/\s+/g, ' ');
1229
return new StringValue(s);
1232
'translate': function(ctx) {
1233
assert(this.args.length == 3);
1234
var s0 = this.args[0].evaluate(ctx).stringValue();
1235
var s1 = this.args[1].evaluate(ctx).stringValue();
1236
var s2 = this.args[2].evaluate(ctx).stringValue();
1238
for (var i = 0; i < s1.length; ++i) {
1239
s0 = s0.replace(new RegExp(s1.charAt(i), 'g'), s2.charAt(i));
1241
return new StringValue(s0);
1244
'matches': function(ctx) {
1245
assert(this.args.length >= 2);
1246
var s0 = this.args[0].evaluate(ctx).stringValue();
1247
var s1 = this.args[1].evaluate(ctx).stringValue();
1248
if (this.args.length > 2) {
1249
var s2 = this.args[2].evaluate(ctx).stringValue();
1250
if (/[^mi]/.test(s2)) {
1251
throw 'Invalid regular expression syntax: ' + s2;
1256
var re = new RegExp(s1, s2);
1259
throw 'Invalid matches argument: ' + s1;
1261
return new BooleanValue(re.test(s0));
1264
'boolean': function(ctx) {
1265
assert(this.args.length == 1);
1266
return new BooleanValue(this.args[0].evaluate(ctx).booleanValue());
1269
'not': function(ctx) {
1270
assert(this.args.length == 1);
1271
var ret = !this.args[0].evaluate(ctx).booleanValue();
1272
return new BooleanValue(ret);
1275
'true': function(ctx) {
1276
assert(this.args.length == 0);
1277
return new BooleanValue(true);
1280
'false': function(ctx) {
1281
assert(this.args.length == 0);
1282
return new BooleanValue(false);
1285
'lang': function(ctx) {
1286
assert(this.args.length == 1);
1287
var lang = this.args[0].evaluate(ctx).stringValue();
1290
while (n && n != n.parentNode /* just in case ... */) {
1291
xmllang = n.getAttribute('xml:lang');
1298
return new BooleanValue(false);
1300
var re = new RegExp('^' + lang + '$', 'i');
1301
return new BooleanValue(xmllang.match(re) ||
1302
xmllang.replace(/_.*$/,'').match(re));
1306
'number': function(ctx) {
1307
assert(this.args.length == 1 || this.args.length == 0);
1309
if (this.args.length == 1) {
1310
return new NumberValue(this.args[0].evaluate(ctx).numberValue());
1312
return new NumberValue(new NodeSetValue([ ctx.node ]).numberValue());
1316
'sum': function(ctx) {
1317
assert(this.args.length == 1);
1318
var n = this.args[0].evaluate(ctx).nodeSetValue();
1320
for (var i = 0; i < n.length; ++i) {
1321
sum += xmlValue(n[i]) - 0;
1323
return new NumberValue(sum);
1326
'floor': function(ctx) {
1327
assert(this.args.length == 1);
1328
var num = this.args[0].evaluate(ctx).numberValue();
1329
return new NumberValue(Math.floor(num));
1332
'ceiling': function(ctx) {
1333
assert(this.args.length == 1);
1334
var num = this.args[0].evaluate(ctx).numberValue();
1335
return new NumberValue(Math.ceil(num));
1338
'round': function(ctx) {
1339
assert(this.args.length == 1);
1340
var num = this.args[0].evaluate(ctx).numberValue();
1341
return new NumberValue(Math.round(num));
1344
// TODO(mesch): The following functions are custom. There is a
1345
// standard that defines how to add functions, which should be
1348
'ext-join': function(ctx) {
1349
assert(this.args.length == 2);
1350
var nodes = this.args[0].evaluate(ctx).nodeSetValue();
1351
var delim = this.args[1].evaluate(ctx).stringValue();
1353
for (var i = 0; i < nodes.length; ++i) {
1357
ret += xmlValue(nodes[i]);
1359
return new StringValue(ret);
1362
// ext-if() evaluates and returns its second argument, if the
1363
// boolean value of its first argument is true, otherwise it
1364
// evaluates and returns its third argument.
1366
'ext-if': function(ctx) {
1367
assert(this.args.length == 3);
1368
if (this.args[0].evaluate(ctx).booleanValue()) {
1369
return this.args[1].evaluate(ctx);
1371
return this.args[2].evaluate(ctx);
1375
// ext-cardinal() evaluates its single argument as a number, and
1376
// returns the current node that many times. It can be used in the
1377
// select attribute to iterate over an integer range.
1379
'ext-cardinal': function(ctx) {
1380
assert(this.args.length >= 1);
1381
var c = this.args[0].evaluate(ctx).numberValue();
1383
for (var i = 0; i < c; ++i) {
1386
return new NodeSetValue(ret);
1390
function UnionExpr(expr1, expr2) {
1395
UnionExpr.prototype.evaluate = function(ctx) {
1396
var nodes1 = this.expr1.evaluate(ctx).nodeSetValue();
1397
var nodes2 = this.expr2.evaluate(ctx).nodeSetValue();
1398
var I1 = nodes1.length;
1399
for (var i2 = 0; i2 < nodes2.length; ++i2) {
1402
for (var i1 = 0; i1 < I1; ++i1) {
1403
if (nodes1[i1] == n) {
1405
i1 = I1; // break inner loop
1412
return new NodeSetValue(nodes1);
1415
function PathExpr(filter, rel) {
1416
this.filter = filter;
1420
PathExpr.prototype.evaluate = function(ctx) {
1421
// the filter expression should be evaluated in its entirety with no
1422
// optimization, as we can't backtrack to it after having moved on to
1423
// evaluating the relative location path
1424
var flag = ctx.returnOnFirstMatch;
1425
ctx.setReturnOnFirstMatch(false);
1426
var nodes = this.filter.evaluate(ctx).nodeSetValue();
1427
ctx.setReturnOnFirstMatch(flag);
1430
if (ctx.returnOnFirstMatch) {
1431
for (var i = 0; i < nodes.length; ++i) {
1432
nodes1 = this.rel.evaluate(ctx.clone(nodes[i], i, nodes)).nodeSetValue();
1433
if (nodes1.length > 0) {
1437
return new NodeSetValue(nodes1);
1440
for (var i = 0; i < nodes.length; ++i) {
1441
var nodes0 = this.rel.evaluate(ctx.clone(nodes[i], i, nodes)).nodeSetValue();
1442
for (var ii = 0; ii < nodes0.length; ++ii) {
1443
nodes1.push(nodes0[ii]);
1446
return new NodeSetValue(nodes1);
1450
function FilterExpr(expr, predicate) {
1452
this.predicate = predicate;
1455
FilterExpr.prototype.evaluate = function(ctx) {
1456
var flag = ctx.returnOnFirstMatch;
1457
ctx.setReturnOnFirstMatch(false);
1458
var nodes = this.expr.evaluate(ctx).nodeSetValue();
1459
ctx.setReturnOnFirstMatch(flag);
1461
for (var i = 0; i < this.predicate.length; ++i) {
1464
for (var j = 0; j < nodes0.length; ++j) {
1466
if (this.predicate[i].evaluate(ctx.clone(n, j, nodes0)).booleanValue()) {
1472
return new NodeSetValue(nodes);
1475
function UnaryMinusExpr(expr) {
1479
UnaryMinusExpr.prototype.evaluate = function(ctx) {
1480
return new NumberValue(-this.expr.evaluate(ctx).numberValue());
1483
function BinaryExpr(expr1, op, expr2) {
1489
BinaryExpr.prototype.evaluate = function(ctx) {
1491
switch (this.op.value) {
1493
ret = new BooleanValue(this.expr1.evaluate(ctx).booleanValue() ||
1494
this.expr2.evaluate(ctx).booleanValue());
1498
ret = new BooleanValue(this.expr1.evaluate(ctx).booleanValue() &&
1499
this.expr2.evaluate(ctx).booleanValue());
1503
ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() +
1504
this.expr2.evaluate(ctx).numberValue());
1508
ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() -
1509
this.expr2.evaluate(ctx).numberValue());
1513
ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() *
1514
this.expr2.evaluate(ctx).numberValue());
1518
ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() %
1519
this.expr2.evaluate(ctx).numberValue());
1523
ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() /
1524
this.expr2.evaluate(ctx).numberValue());
1528
ret = this.compare(ctx, function(x1, x2) { return x1 == x2; });
1532
ret = this.compare(ctx, function(x1, x2) { return x1 != x2; });
1536
ret = this.compare(ctx, function(x1, x2) { return x1 < x2; });
1540
ret = this.compare(ctx, function(x1, x2) { return x1 <= x2; });
1544
ret = this.compare(ctx, function(x1, x2) { return x1 > x2; });
1548
ret = this.compare(ctx, function(x1, x2) { return x1 >= x2; });
1552
alert('BinaryExpr.evaluate: ' + this.op.value);
1557
BinaryExpr.prototype.compare = function(ctx, cmp) {
1558
var v1 = this.expr1.evaluate(ctx);
1559
var v2 = this.expr2.evaluate(ctx);
1562
if (v1.type == 'node-set' && v2.type == 'node-set') {
1563
var n1 = v1.nodeSetValue();
1564
var n2 = v2.nodeSetValue();
1566
for (var i1 = 0; i1 < n1.length; ++i1) {
1567
for (var i2 = 0; i2 < n2.length; ++i2) {
1568
if (cmp(xmlValue(n1[i1]), xmlValue(n2[i2]))) {
1570
// Break outer loop. Labels confuse the jscompiler and we
1578
} else if (v1.type == 'node-set' || v2.type == 'node-set') {
1580
if (v1.type == 'number') {
1581
var s = v1.numberValue();
1582
var n = v2.nodeSetValue();
1585
for (var i = 0; i < n.length; ++i) {
1586
var nn = xmlValue(n[i]) - 0;
1593
} else if (v2.type == 'number') {
1594
var n = v1.nodeSetValue();
1595
var s = v2.numberValue();
1598
for (var i = 0; i < n.length; ++i) {
1599
var nn = xmlValue(n[i]) - 0;
1606
} else if (v1.type == 'string') {
1607
var s = v1.stringValue();
1608
var n = v2.nodeSetValue();
1611
for (var i = 0; i < n.length; ++i) {
1612
var nn = xmlValue(n[i]);
1619
} else if (v2.type == 'string') {
1620
var n = v1.nodeSetValue();
1621
var s = v2.stringValue();
1624
for (var i = 0; i < n.length; ++i) {
1625
var nn = xmlValue(n[i]);
1633
ret = cmp(v1.booleanValue(), v2.booleanValue());
1636
} else if (v1.type == 'boolean' || v2.type == 'boolean') {
1637
ret = cmp(v1.booleanValue(), v2.booleanValue());
1639
} else if (v1.type == 'number' || v2.type == 'number') {
1640
ret = cmp(v1.numberValue(), v2.numberValue());
1643
ret = cmp(v1.stringValue(), v2.stringValue());
1646
return new BooleanValue(ret);
1649
function LiteralExpr(value) {
1653
LiteralExpr.prototype.evaluate = function(ctx) {
1654
return new StringValue(this.value);
1657
function NumberExpr(value) {
1661
NumberExpr.prototype.evaluate = function(ctx) {
1662
return new NumberValue(this.value);
1665
function VariableExpr(name) {
1669
VariableExpr.prototype.evaluate = function(ctx) {
1670
return ctx.getVariable(this.name);
1673
// Factory functions for semantic values (i.e. Expressions) of the
1674
// productions in the grammar. When a production is matched to reduce
1675
// the current parse state stack, the function is called with the
1676
// semantic values of the matched elements as arguments, and returns
1677
// another semantic value. The semantic value is a node of the parse
1678
// tree, an expression object with an evaluate() method that evaluates the
1679
// expression in an actual context. These factory functions are used
1680
// in the specification of the grammar rules, below.
1682
function makeTokenExpr(m) {
1683
return new TokenExpr(m);
1686
function passExpr(e) {
1690
function makeLocationExpr1(slash, rel) {
1691
rel.absolute = true;
1695
function makeLocationExpr2(dslash, rel) {
1696
rel.absolute = true;
1697
rel.prependStep(makeAbbrevStep(dslash.value));
1701
function makeLocationExpr3(slash) {
1702
var ret = new LocationExpr();
1703
ret.appendStep(makeAbbrevStep('.'));
1704
ret.absolute = true;
1708
function makeLocationExpr4(dslash) {
1709
var ret = new LocationExpr();
1710
ret.absolute = true;
1711
ret.appendStep(makeAbbrevStep(dslash.value));
1715
function makeLocationExpr5(step) {
1716
var ret = new LocationExpr();
1717
ret.appendStep(step);
1721
function makeLocationExpr6(rel, slash, step) {
1722
rel.appendStep(step);
1726
function makeLocationExpr7(rel, dslash, step) {
1727
rel.appendStep(makeAbbrevStep(dslash.value));
1728
rel.appendStep(step);
1732
function makeStepExpr1(dot) {
1733
return makeAbbrevStep(dot.value);
1736
function makeStepExpr2(ddot) {
1737
return makeAbbrevStep(ddot.value);
1740
function makeStepExpr3(axisname, axis, nodetest) {
1741
return new StepExpr(axisname.value, nodetest);
1744
function makeStepExpr4(at, nodetest) {
1745
return new StepExpr('attribute', nodetest);
1748
function makeStepExpr5(nodetest) {
1749
return new StepExpr('child', nodetest);
1752
function makeStepExpr6(step, predicate) {
1753
step.appendPredicate(predicate);
1757
function makeAbbrevStep(abbrev) {
1760
return new StepExpr('descendant-or-self', new NodeTestAny);
1763
return new StepExpr('self', new NodeTestAny);
1766
return new StepExpr('parent', new NodeTestAny);
1770
function makeNodeTestExpr1(asterisk) {
1771
return new NodeTestElementOrAttribute;
1774
function makeNodeTestExpr2(ncname, colon, asterisk) {
1775
return new NodeTestNC(ncname.value);
1778
function makeNodeTestExpr3(qname) {
1779
return new NodeTestName(qname.value);
1782
function makeNodeTestExpr4(typeo, parenc) {
1783
var type = typeo.value.replace(/\s*\($/, '');
1786
return new NodeTestAny;
1789
return new NodeTestText;
1792
return new NodeTestComment;
1794
case 'processing-instruction':
1795
return new NodeTestPI('');
1799
function makeNodeTestExpr5(typeo, target, parenc) {
1800
var type = typeo.replace(/\s*\($/, '');
1801
if (type != 'processing-instruction') {
1804
return new NodeTestPI(target.value);
1807
function makePredicateExpr(pareno, expr, parenc) {
1808
return new PredicateExpr(expr);
1811
function makePrimaryExpr(pareno, expr, parenc) {
1815
function makeFunctionCallExpr1(name, pareno, parenc) {
1816
return new FunctionCallExpr(name);
1819
function makeFunctionCallExpr2(name, pareno, arg1, args, parenc) {
1820
var ret = new FunctionCallExpr(name);
1821
ret.appendArg(arg1);
1822
for (var i = 0; i < args.length; ++i) {
1823
ret.appendArg(args[i]);
1828
function makeArgumentExpr(comma, expr) {
1832
function makeUnionExpr(expr1, pipe, expr2) {
1833
return new UnionExpr(expr1, expr2);
1836
function makePathExpr1(filter, slash, rel) {
1837
return new PathExpr(filter, rel);
1840
function makePathExpr2(filter, dslash, rel) {
1841
rel.prependStep(makeAbbrevStep(dslash.value));
1842
return new PathExpr(filter, rel);
1845
function makeFilterExpr(expr, predicates) {
1846
if (predicates.length > 0) {
1847
return new FilterExpr(expr, predicates);
1853
function makeUnaryMinusExpr(minus, expr) {
1854
return new UnaryMinusExpr(expr);
1857
function makeBinaryExpr(expr1, op, expr2) {
1858
return new BinaryExpr(expr1, op, expr2);
1861
function makeLiteralExpr(token) {
1862
// remove quotes from the parsed value:
1863
var value = token.value.substring(1, token.value.length - 1);
1864
return new LiteralExpr(value);
1867
function makeNumberExpr(token) {
1868
return new NumberExpr(token.value);
1871
function makeVariableReference(dollar, name) {
1872
return new VariableExpr(name.value);
1875
// Used before parsing for optimization of common simple cases. See
1876
// the begin of xpathParse() for which they are.
1877
function makeSimpleExpr(expr) {
1878
if (expr.charAt(0) == '$') {
1879
return new VariableExpr(expr.substr(1));
1880
} else if (expr.charAt(0) == '@') {
1881
var a = new NodeTestName(expr.substr(1));
1882
var b = new StepExpr('attribute', a);
1883
var c = new LocationExpr();
1886
} else if (expr.match(/^[0-9]+$/)) {
1887
return new NumberExpr(expr);
1889
var a = new NodeTestName(expr);
1890
var b = new StepExpr('child', a);
1891
var c = new LocationExpr();
1897
function makeSimpleExpr2(expr) {
1898
var steps = stringSplit(expr, '/');
1899
var c = new LocationExpr();
1900
for (var i = 0; i < steps.length; ++i) {
1901
var a = new NodeTestName(steps[i]);
1902
var b = new StepExpr('child', a);
1908
// The axes of XPath expressions.
1911
ANCESTOR_OR_SELF: 'ancestor-or-self',
1912
ANCESTOR: 'ancestor',
1913
ATTRIBUTE: 'attribute',
1915
DESCENDANT_OR_SELF: 'descendant-or-self',
1916
DESCENDANT: 'descendant',
1917
FOLLOWING_SIBLING: 'following-sibling',
1918
FOLLOWING: 'following',
1919
NAMESPACE: 'namespace',
1921
PRECEDING_SIBLING: 'preceding-sibling',
1922
PRECEDING: 'preceding',
1927
xpathAxis.ANCESTOR_OR_SELF,
1929
xpathAxis.ATTRIBUTE,
1931
xpathAxis.DESCENDANT_OR_SELF,
1932
xpathAxis.DESCENDANT,
1933
xpathAxis.FOLLOWING_SIBLING,
1934
xpathAxis.FOLLOWING,
1935
xpathAxis.NAMESPACE,
1937
xpathAxis.PRECEDING_SIBLING,
1938
xpathAxis.PRECEDING,
1943
// The tokens of the language. The label property is just used for
1944
// generating debug output. The prec property is the precedence used
1945
// for shift/reduce resolution. Default precedence is 0 as a lookahead
1946
// token and 2 on the stack. TODO(mesch): this is certainly not
1947
// necessary and too complicated. Simplify this!
1949
// NOTE: tabular formatting is the big exception, but here it should
1952
var TOK_PIPE = { label: "|", prec: 17, re: new RegExp("^\\|") };
1953
var TOK_DSLASH = { label: "//", prec: 19, re: new RegExp("^//") };
1954
var TOK_SLASH = { label: "/", prec: 30, re: new RegExp("^/") };
1955
var TOK_AXIS = { label: "::", prec: 20, re: new RegExp("^::") };
1956
var TOK_COLON = { label: ":", prec: 1000, re: new RegExp("^:") };
1957
var TOK_AXISNAME = { label: "[axis]", re: new RegExp('^(' + xpathAxesRe + ')') };
1958
var TOK_PARENO = { label: "(", prec: 34, re: new RegExp("^\\(") };
1959
var TOK_PARENC = { label: ")", re: new RegExp("^\\)") };
1960
var TOK_DDOT = { label: "..", prec: 34, re: new RegExp("^\\.\\.") };
1961
var TOK_DOT = { label: ".", prec: 34, re: new RegExp("^\\.") };
1962
var TOK_AT = { label: "@", prec: 34, re: new RegExp("^@") };
1964
var TOK_COMMA = { label: ",", re: new RegExp("^,") };
1966
var TOK_OR = { label: "or", prec: 10, re: new RegExp("^or\\b") };
1967
var TOK_AND = { label: "and", prec: 11, re: new RegExp("^and\\b") };
1968
var TOK_EQ = { label: "=", prec: 12, re: new RegExp("^=") };
1969
var TOK_NEQ = { label: "!=", prec: 12, re: new RegExp("^!=") };
1970
var TOK_GE = { label: ">=", prec: 13, re: new RegExp("^>=") };
1971
var TOK_GT = { label: ">", prec: 13, re: new RegExp("^>") };
1972
var TOK_LE = { label: "<=", prec: 13, re: new RegExp("^<=") };
1973
var TOK_LT = { label: "<", prec: 13, re: new RegExp("^<") };
1974
var TOK_PLUS = { label: "+", prec: 14, re: new RegExp("^\\+"), left: true };
1975
var TOK_MINUS = { label: "-", prec: 14, re: new RegExp("^\\-"), left: true };
1976
var TOK_DIV = { label: "div", prec: 15, re: new RegExp("^div\\b"), left: true };
1977
var TOK_MOD = { label: "mod", prec: 15, re: new RegExp("^mod\\b"), left: true };
1979
var TOK_BRACKO = { label: "[", prec: 32, re: new RegExp("^\\[") };
1980
var TOK_BRACKC = { label: "]", re: new RegExp("^\\]") };
1981
var TOK_DOLLAR = { label: "$", re: new RegExp("^\\$") };
1983
var TOK_NCNAME = { label: "[ncname]", re: new RegExp('^' + XML_NC_NAME) };
1985
var TOK_ASTERISK = { label: "*", prec: 15, re: new RegExp("^\\*"), left: true };
1986
var TOK_LITERALQ = { label: "[litq]", prec: 20, re: new RegExp("^'[^\\']*'") };
1987
var TOK_LITERALQQ = {
1990
re: new RegExp('^"[^\\"]*"')
1996
re: new RegExp('^\\d+(\\.\\d*)?') };
2000
re: new RegExp('^(' + XML_NC_NAME + ':)?' + XML_NC_NAME)
2004
label: "[nodetest-start]",
2005
re: new RegExp('^(processing-instruction|comment|text|node)\\(')
2008
// The table of the tokens of our grammar, used by the lexer: first
2009
// column the tag, second column a regexp to recognize it in the
2010
// input, third column the precedence of the token, fourth column a
2011
// factory function for the semantic value of the token.
2013
// NOTE: order of this list is important, because the first match
2014
// counts. Cf. DDOT and DOT, and AXIS and COLON.
2016
var xpathTokenRules = [
2053
// All the nonterminals of the grammar. The nonterminal objects are
2054
// identified by object identity; the labels are used in the debug
2056
var XPathLocationPath = { label: "LocationPath" };
2057
var XPathRelativeLocationPath = { label: "RelativeLocationPath" };
2058
var XPathAbsoluteLocationPath = { label: "AbsoluteLocationPath" };
2059
var XPathStep = { label: "Step" };
2060
var XPathNodeTest = { label: "NodeTest" };
2061
var XPathPredicate = { label: "Predicate" };
2062
var XPathLiteral = { label: "Literal" };
2063
var XPathExpr = { label: "Expr" };
2064
var XPathPrimaryExpr = { label: "PrimaryExpr" };
2065
var XPathVariableReference = { label: "Variablereference" };
2066
var XPathNumber = { label: "Number" };
2067
var XPathFunctionCall = { label: "FunctionCall" };
2068
var XPathArgumentRemainder = { label: "ArgumentRemainder" };
2069
var XPathPathExpr = { label: "PathExpr" };
2070
var XPathUnionExpr = { label: "UnionExpr" };
2071
var XPathFilterExpr = { label: "FilterExpr" };
2072
var XPathDigits = { label: "Digits" };
2074
var xpathNonTerminals = [
2076
XPathRelativeLocationPath,
2077
XPathAbsoluteLocationPath,
2084
XPathVariableReference,
2087
XPathArgumentRemainder,
2094
// Quantifiers that are used in the productions of the grammar.
2095
var Q_01 = { label: "?" };
2096
var Q_MM = { label: "*" };
2097
var Q_1M = { label: "+" };
2099
// Tag for left associativity (right assoc is implied by undefined).
2100
var ASSOC_LEFT = true;
2102
// The productions of the grammar. Columns of the table:
2104
// - target nonterminal,
2107
// - semantic value factory
2109
// The semantic value factory is a function that receives parse tree
2110
// nodes from the stack frames of the matched symbols as arguments and
2111
// returns an a node of the parse tree. The node is stored in the top
2112
// stack frame along with the target object of the rule. The node in
2113
// the parse tree is an expression object that has an evaluate() method
2114
// and thus evaluates XPath expressions.
2116
// The precedence is used to decide between reducing and shifting by
2117
// comparing the precendence of the rule that is candidate for
2118
// reducing with the precedence of the look ahead token. Precedence of
2119
// -1 means that the precedence of the tokens in the pattern is used
2120
// instead. TODO: It shouldn't be necessary to explicitly assign
2121
// precedences to rules.
2123
// DGF As it stands, these precedences are purely empirical; we're
2124
// not sure they can be made to be consistent at all.
2126
var xpathGrammarRules =
2128
[ XPathLocationPath, [ XPathRelativeLocationPath ], 18,
2130
[ XPathLocationPath, [ XPathAbsoluteLocationPath ], 18,
2133
[ XPathAbsoluteLocationPath, [ TOK_SLASH, XPathRelativeLocationPath ], 18,
2134
makeLocationExpr1 ],
2135
[ XPathAbsoluteLocationPath, [ TOK_DSLASH, XPathRelativeLocationPath ], 18,
2136
makeLocationExpr2 ],
2138
[ XPathAbsoluteLocationPath, [ TOK_SLASH ], 0,
2139
makeLocationExpr3 ],
2140
[ XPathAbsoluteLocationPath, [ TOK_DSLASH ], 0,
2141
makeLocationExpr4 ],
2143
[ XPathRelativeLocationPath, [ XPathStep ], 31,
2144
makeLocationExpr5 ],
2145
[ XPathRelativeLocationPath,
2146
[ XPathRelativeLocationPath, TOK_SLASH, XPathStep ], 31,
2147
makeLocationExpr6 ],
2148
[ XPathRelativeLocationPath,
2149
[ XPathRelativeLocationPath, TOK_DSLASH, XPathStep ], 31,
2150
makeLocationExpr7 ],
2152
[ XPathStep, [ TOK_DOT ], 33,
2154
[ XPathStep, [ TOK_DDOT ], 33,
2157
[ TOK_AXISNAME, TOK_AXIS, XPathNodeTest ], 33,
2159
[ XPathStep, [ TOK_AT, XPathNodeTest ], 33,
2161
[ XPathStep, [ XPathNodeTest ], 33,
2163
[ XPathStep, [ XPathStep, XPathPredicate ], 33,
2166
[ XPathNodeTest, [ TOK_ASTERISK ], 33,
2167
makeNodeTestExpr1 ],
2168
[ XPathNodeTest, [ TOK_NCNAME, TOK_COLON, TOK_ASTERISK ], 33,
2169
makeNodeTestExpr2 ],
2170
[ XPathNodeTest, [ TOK_QNAME ], 33,
2171
makeNodeTestExpr3 ],
2172
[ XPathNodeTest, [ TOK_NODEO, TOK_PARENC ], 33,
2173
makeNodeTestExpr4 ],
2174
[ XPathNodeTest, [ TOK_NODEO, XPathLiteral, TOK_PARENC ], 33,
2175
makeNodeTestExpr5 ],
2177
[ XPathPredicate, [ TOK_BRACKO, XPathExpr, TOK_BRACKC ], 33,
2178
makePredicateExpr ],
2180
[ XPathPrimaryExpr, [ XPathVariableReference ], 33,
2182
[ XPathPrimaryExpr, [ TOK_PARENO, XPathExpr, TOK_PARENC ], 33,
2184
[ XPathPrimaryExpr, [ XPathLiteral ], 30,
2186
[ XPathPrimaryExpr, [ XPathNumber ], 30,
2188
[ XPathPrimaryExpr, [ XPathFunctionCall ], 31,
2191
[ XPathFunctionCall, [ TOK_QNAME, TOK_PARENO, TOK_PARENC ], -1,
2192
makeFunctionCallExpr1 ],
2193
[ XPathFunctionCall,
2194
[ TOK_QNAME, TOK_PARENO, XPathExpr, XPathArgumentRemainder, Q_MM,
2196
makeFunctionCallExpr2 ],
2197
[ XPathArgumentRemainder, [ TOK_COMMA, XPathExpr ], -1,
2200
[ XPathUnionExpr, [ XPathPathExpr ], 20,
2202
[ XPathUnionExpr, [ XPathUnionExpr, TOK_PIPE, XPathPathExpr ], 20,
2205
[ XPathPathExpr, [ XPathLocationPath ], 20,
2207
[ XPathPathExpr, [ XPathFilterExpr ], 19,
2210
[ XPathFilterExpr, TOK_SLASH, XPathRelativeLocationPath ], 19,
2213
[ XPathFilterExpr, TOK_DSLASH, XPathRelativeLocationPath ], 19,
2216
[ XPathFilterExpr, [ XPathPrimaryExpr, XPathPredicate, Q_MM ], 31,
2219
[ XPathExpr, [ XPathPrimaryExpr ], 16,
2221
[ XPathExpr, [ XPathUnionExpr ], 16,
2224
[ XPathExpr, [ TOK_MINUS, XPathExpr ], -1,
2225
makeUnaryMinusExpr ],
2227
[ XPathExpr, [ XPathExpr, TOK_OR, XPathExpr ], -1,
2229
[ XPathExpr, [ XPathExpr, TOK_AND, XPathExpr ], -1,
2232
[ XPathExpr, [ XPathExpr, TOK_EQ, XPathExpr ], -1,
2234
[ XPathExpr, [ XPathExpr, TOK_NEQ, XPathExpr ], -1,
2237
[ XPathExpr, [ XPathExpr, TOK_LT, XPathExpr ], -1,
2239
[ XPathExpr, [ XPathExpr, TOK_LE, XPathExpr ], -1,
2241
[ XPathExpr, [ XPathExpr, TOK_GT, XPathExpr ], -1,
2243
[ XPathExpr, [ XPathExpr, TOK_GE, XPathExpr ], -1,
2246
[ XPathExpr, [ XPathExpr, TOK_PLUS, XPathExpr ], -1,
2247
makeBinaryExpr, ASSOC_LEFT ],
2248
[ XPathExpr, [ XPathExpr, TOK_MINUS, XPathExpr ], -1,
2249
makeBinaryExpr, ASSOC_LEFT ],
2251
[ XPathExpr, [ XPathExpr, TOK_ASTERISK, XPathExpr ], -1,
2252
makeBinaryExpr, ASSOC_LEFT ],
2253
[ XPathExpr, [ XPathExpr, TOK_DIV, XPathExpr ], -1,
2254
makeBinaryExpr, ASSOC_LEFT ],
2255
[ XPathExpr, [ XPathExpr, TOK_MOD, XPathExpr ], -1,
2256
makeBinaryExpr, ASSOC_LEFT ],
2258
[ XPathLiteral, [ TOK_LITERALQ ], -1,
2260
[ XPathLiteral, [ TOK_LITERALQQ ], -1,
2263
[ XPathNumber, [ TOK_NUMBER ], -1,
2266
[ XPathVariableReference, [ TOK_DOLLAR, TOK_QNAME ], 200,
2267
makeVariableReference ]
2270
// That function computes some optimizations of the above data
2271
// structures and will be called right here. It merely takes the
2272
// counter variables out of the global scope.
2274
var xpathRules = [];
2276
function xpathParseInit() {
2277
if (xpathRules.length) {
2281
// Some simple optimizations for the xpath expression parser: sort
2282
// grammar rules descending by length, so that the longest match is
2285
xpathGrammarRules.sort(function(a,b) {
2286
var la = a[1].length;
2287
var lb = b[1].length;
2290
} else if (la > lb) {
2298
for (var i = 0; i < xpathNonTerminals.length; ++i) {
2299
xpathNonTerminals[i].key = k++;
2302
for (i = 0; i < xpathTokenRules.length; ++i) {
2303
xpathTokenRules[i].key = k++;
2306
xpathLog('XPath parse INIT: ' + k + ' rules');
2308
// Another slight optimization: sort the rules into bins according
2309
// to the last element (observing quantifiers), so we can restrict
2310
// the match against the stack to the subest of rules that match the
2311
// top of the stack.
2313
// TODO(mesch): What we actually want is to compute states as in
2314
// bison, so that we don't have to do any explicit and iterated
2315
// match against the stack.
2317
function push_(array, position, element) {
2318
if (!array[position]) {
2319
array[position] = [];
2321
array[position].push(element);
2324
for (i = 0; i < xpathGrammarRules.length; ++i) {
2325
var rule = xpathGrammarRules[i];
2326
var pattern = rule[1];
2328
for (var j = pattern.length - 1; j >= 0; --j) {
2329
if (pattern[j] == Q_1M) {
2330
push_(xpathRules, pattern[j-1].key, rule);
2333
} else if (pattern[j] == Q_MM || pattern[j] == Q_01) {
2334
push_(xpathRules, pattern[j-1].key, rule);
2338
push_(xpathRules, pattern[j].key, rule);
2344
xpathLog('XPath parse INIT: ' + xpathRules.length + ' rule bins');
2347
mapExec(xpathRules, function(i) {
2353
xpathLog('XPath parse INIT: ' + (sum / xpathRules.length) +
2354
' average bin size');
2357
// Local utility functions that are used by the lexer or parser.
2359
function xpathCollectDescendants(nodelist, node, opt_tagName) {
2360
if (opt_tagName && node.getElementsByTagName) {
2361
copyArray(nodelist, node.getElementsByTagName(opt_tagName));
2364
for (var n = node.firstChild; n; n = n.nextSibling) {
2366
xpathCollectDescendants(nodelist, n);
2371
* DGF - extract a tag name suitable for getElementsByTagName
2373
* @param nodetest the node test
2374
* @param ignoreNonElementNodesForNTA if true, the node list returned when
2375
* evaluating "node()" will not contain
2376
* non-element nodes. This can boost
2377
* performance. This is false by default.
2379
function xpathExtractTagNameFromNodeTest(nodetest, ignoreNonElementNodesForNTA) {
2380
if (nodetest instanceof NodeTestName) {
2381
return nodetest.name;
2383
if ((ignoreNonElementNodesForNTA && nodetest instanceof NodeTestAny) ||
2384
nodetest instanceof NodeTestElementOrAttribute) {
2389
function xpathCollectDescendantsReverse(nodelist, node) {
2390
for (var n = node.lastChild; n; n = n.previousSibling) {
2392
xpathCollectDescendantsReverse(nodelist, n);
2397
// The entry point for the library: match an expression against a DOM
2398
// node. Returns an XPath value.
2399
function xpathDomEval(expr, node) {
2400
var expr1 = xpathParse(expr);
2401
var ret = expr1.evaluate(new ExprContext(node));
2405
// Utility function to sort a list of nodes. Used by xsltSort() and
2407
function xpathSort(input, sort) {
2408
if (sort.length == 0) {
2414
for (var i = 0; i < input.contextSize(); ++i) {
2415
var node = input.nodelist[i];
2416
var sortitem = { node: node, key: [] };
2417
var context = input.clone(node, 0, [ node ]);
2419
for (var j = 0; j < sort.length; ++j) {
2421
var value = s.expr.evaluate(context);
2424
if (s.type == 'text') {
2425
evalue = value.stringValue();
2426
} else if (s.type == 'number') {
2427
evalue = value.numberValue();
2429
sortitem.key.push({ value: evalue, order: s.order });
2432
// Make the sort stable by adding a lowest priority sort by
2433
// id. This is very convenient and furthermore required by the
2434
// spec ([XSLT] - Section 10 Sorting).
2435
sortitem.key.push({ value: i, order: 'ascending' });
2437
sortlist.push(sortitem);
2440
sortlist.sort(xpathSortByKey);
2443
for (var i = 0; i < sortlist.length; ++i) {
2444
nodes.push(sortlist[i].node);
2446
input.nodelist = nodes;
2451
// Sorts by all order criteria defined. According to the JavaScript
2452
// spec ([ECMA] Section 11.8.5), the compare operators compare strings
2453
// as strings and numbers as numbers.
2455
// NOTE: In browsers which do not follow the spec, this breaks only in
2456
// the case that numbers should be sorted as strings, which is very
2458
function xpathSortByKey(v1, v2) {
2459
// NOTE: Sort key vectors of different length never occur in
2462
for (var i = 0; i < v1.key.length; ++i) {
2463
var o = v1.key[i].order == 'descending' ? -1 : 1;
2464
if (v1.key[i].value > v2.key[i].value) {
2466
} else if (v1.key[i].value < v2.key[i].value) {
2475
// Parses and then evaluates the given XPath expression in the given
2476
// input context. Notice that parsed xpath expressions are cached.
2477
function xpathEval(select, context) {
2478
var expr = xpathParse(select);
2479
var ret = expr.evaluate(context);
added
removed
static/selenium/core/xpath/xpath.js
