FishEye: file selenium/trunk/src/main/resources/core/xpath/xpath.js

View

Revision:

Diff

Diff from trunk to:

Annotations

Annotate by Age | Author | None

/fisheye/browse/selenium/trunk/src/main/resources/core/xpath/xpath.js

Annotated File View

dfabulich	1919	1	// Copyright 2005 Google Inc.
		2	// All Rights Reserved
		3	//
		4	// An XPath parser and evaluator written in JavaScript. The
		5	// implementation is complete except for functions handling
		6	// namespaces.
		7	//
		8	// Reference: [XPATH] XPath Specification
		9	// <http://www.w3.org/TR/1999/REC-xpath-19991116>.
		10	//
		11	//
		12	// The API of the parser has several parts:
		13	//
		14	// 1. The parser function xpathParse() that takes a string and returns
		15	// an expession object.
		16	//
		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.)
		21	//
		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
		24	// evaluated.
		25	//
		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.
		29	//
		30	// These parts are near the top of the file, the functions and data
		31	// that are used internally follow after them.
		32	//
		33	//
		34	// Author: Steffen Meschkat <mesch@google.com>
		35
		36
		37	// The entry point for the parser.
		38	//
		39	// @param expr a string that contains an XPath expression.
		40	// @return an expression object that can be evaluated with an
		41	// expression context.
		42
		43	function xpathParse(expr) {
		44	xpathLog('parse ' + expr);
		45	xpathParseInit();
		46
		47	var cached = xpathCacheLookup(expr);
		48	if (cached) {
		49	xpathLog(' ... cached');
		50	return cached;
		51	}
		52
		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).
		58
		59	if (expr.match(/^(\$\|@)?\w+$/i)) {
		60	var ret = makeSimpleExpr(expr);
		61	xpathParseCache[expr] = ret;
		62	xpathLog(' ... simple');
		63	return ret;
		64	}
65
66	if (expr.match(/^\w+(\/\w+)*$/i)) {
67	var ret = makeSimpleExpr2(expr);
68	xpathParseCache[expr] = ret;
69	xpathLog(' ... simple 2');
70	return ret;
71	}
72
73	var cachekey = expr; // expr is modified during parse
74
75	var stack = [];
76	var ahead = null;
77	var previous = null;
78	var done = false;
79
80	var parse_count = 0;
81	var lexer_count = 0;
82	var reduce_count = 0;
83
84	while (!done) {
85	parse_count++;
86	expr = expr.replace(/^\s*/, '');
87	previous = ahead;
88	ahead = null;
89
90	var rule = null;
91	var match = '';
92	for (var i = 0; i < xpathTokenRules.length; ++i) {
93	var result = xpathTokenRules[i].re.exec(expr);
94	lexer_count++;
95	if (result && result.length > 0 && result[0].length > match.length) {
96	rule = xpathTokenRules[i];
97	match = result[0];
98	break;
99	}
100	}
101
102	// Special case: allow operator keywords to be element and
103	// variable names.
104
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.
115
116	if (rule &&
117	(rule == TOK_DIV \|\|
118	rule == TOK_MOD \|\|
119	rule == TOK_AND \|\|
120	rule == TOK_OR) &&
121	(!previous \|\|
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)) {
127	rule = TOK_QNAME;
128	}
129
130	if (rule) {
131	expr = expr.substr(match.length);
132	xpathLog('token: ' + match + ' -- ' + rule.label);
133	ahead = {
134	tag: rule,
135	match: match,
136	prec: rule.prec ? rule.prec : 0, // \|\| 0 is removed by the compiler
137	expr: makeTokenExpr(match)
138	};
139
140	} else {
141	xpathLog('DONE');
142	done = true;
143	}
144
145	while (xpathReduce(stack, ahead)) {
146	reduce_count++;
147	xpathLog('stack: ' + stackToString(stack));
148	}
149	}
150
151	xpathLog('stack: ' + stackToString(stack));
152
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);
156	}
157
158	var result = stack[0].expr;
159	xpathParseCache[cachekey] = result;
160
161	xpathLog('XPath parse: ' + parse_count + ' / ' +
162	lexer_count + ' / ' + reduce_count);
163
164	return result;
165	}
166
167	var xpathParseCache = {};
168
169	function xpathCacheLookup(expr) {
170	return xpathParseCache[expr];
171	}
172
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".
176
177	The idea here
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
181	"Expr" token.
182
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
188	the XPath.
189
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.
195
196	Some tokens have left associativity, in which case we shift when they
197	have LOWER precedence than the candidate.
198	*/
199	function xpathReduce(stack, ahead) {
200	var cand = null;
201
202	if (stack.length > 0) {
203	var top = stack[stack.length-1];
204	var ruleset = xpathRules[top.tag.key];
205
206	if (ruleset) {
207	for (var i = 0; i < ruleset.length; ++i) {
208	var rule = ruleset[i];
209	var match = xpathMatchStack(stack, rule[1]);
210	if (match.length) {
211	cand = {
212	tag: rule[0],
213	rule: rule,
214	match: match
215	};
216	cand.prec = xpathGrammarPrecedence(cand);
217	break;
218	}
219	}
220	}
221	}
222
223	var ret;
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) {
227	stack.pop();
228	}
229
230	xpathLog('reduce ' + cand.tag.label + ' ' + cand.prec +
231	' ahead ' + (ahead ? ahead.tag.label + ' ' + ahead.prec +
232	(ahead.tag.left ? ' left' : '')
233	: ' none '));
234
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);
238
239	stack.push(cand);
240	ret = true;
241
242	} else {
243	if (ahead) {
244	xpathLog('shift ' + ahead.tag.label + ' ' + ahead.prec +
245	(ahead.tag.left ? ' left' : '') +
246	' over ' + (cand ? cand.tag.label + ' ' +
247	cand.prec : ' none'));
248	stack.push(ahead);
249	}
250	ret = false;
251	}
252	return ret;
253	}
254
255	function xpathMatchStack(stack, pattern) {
256
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
262	// unambiguous.
263
264	var S = stack.length;
265	var P = pattern.length;
266	var p, s;
267	var match = [];
268	match.matchlength = 0;
269	var ds = 0;
270	for (p = P - 1, s = S - 1; p >= 0 && s >= 0; --p, s -= ds) {
271	ds = 0;
272	var qmatch = [];
273	if (pattern[p] == Q_MM) {
274	p -= 1;
275	match.push(qmatch);
276	while (s - ds >= 0 && stack[s - ds].tag == pattern[p]) {
277	qmatch.push(stack[s - ds]);
278	ds += 1;
279	match.matchlength += 1;
280	}
281
282	} else if (pattern[p] == Q_01) {
283	p -= 1;
284	match.push(qmatch);
285	while (s - ds >= 0 && ds < 2 && stack[s - ds].tag == pattern[p]) {
286	qmatch.push(stack[s - ds]);
287	ds += 1;
288	match.matchlength += 1;
289	}
290
291	} else if (pattern[p] == Q_1M) {
292	p -= 1;
293	match.push(qmatch);
294	if (stack[s].tag == pattern[p]) {
295	while (s - ds >= 0 && stack[s - ds].tag == pattern[p]) {
296	qmatch.push(stack[s - ds]);
297	ds += 1;
298	match.matchlength += 1;
299	}
300	} else {
301	return [];
302	}
303
304	} else if (stack[s].tag == pattern[p]) {
305	match.push(stack[s]);
306	ds += 1;
307	match.matchlength += 1;
308
309	} else {
310	return [];
311	}
312
313	reverseInplace(qmatch);
314	qmatch.expr = mapExpr(qmatch, function(m) { return m.expr; });
315	}
316
317	reverseInplace(match);
318
319	if (p == -1) {
320	return match;
321
322	} else {
323	return [];
324	}
325	}
326
327	function xpathTokenPrecedence(tag) {
328	return tag.prec \|\| 2;
329	}
330
331	function xpathGrammarPrecedence(frame) {
332	var ret = 0;
333
334	if (frame.rule) { /* normal reduce */
335	if (frame.rule.length >= 3 && frame.rule[2] >= 0) {
336	ret = frame.rule[2];
337
338	} else {
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);
342	}
343	}
344	} else if (frame.tag) { /* TOKEN match */
345	ret = xpathTokenPrecedence(frame.tag);
346
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);
351	}
352	}
353
354	return ret;
355	}
356
357	function stackToString(stack) {
358	var ret = '';
359	for (var i = 0; i < stack.length; ++i) {
360	if (ret) {
361	ret += '\n';
362	}
363	ret += stack[i].tag.label;
364	}
365	return ret;
366	}
367
368
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.)
373	//
374	// The interface of the expression context:
375	//
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.
383	//
384	// Notice that position starts at 0 at the outside interface;
385	// inside XPath expressions this shows up as position()=1.
386	//
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.
391	//
392	// setVariable(name, expr) -- binds given XPath expression to the
393	// name.
394	//
395	// getVariable(name) -- what the name says.
396	//
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.)
401	//
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
408	// XSL spec.
gyrm	2357	409	//
		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.
		413	//
		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::*/".
dfabulich	1919	419
gyrm	2026	420	function ExprContext(node, opt_position, opt_nodelist, opt_parent,
gyrm	2026	421	opt_caseInsensitive, opt_ignoreAttributesWithoutValue,
gyrm	2357	422	opt_returnOnFirstMatch, opt_ignoreNonElementNodesForNTA)
gyrm	2026	423	{
dfabulich	1919	424	this.node = node;
		425	this.position = opt_position \|\| 0;
		426	this.nodelist = opt_nodelist \|\| [ node ];
		427	this.variables = {};
		428	this.parent = opt_parent \|\| null;
		429	this.caseInsensitive = opt_caseInsensitive \|\| false;
gyrm	1931	430	this.ignoreAttributesWithoutValue = opt_ignoreAttributesWithoutValue \|\| false;
gyrm	2026	431	this.returnOnFirstMatch = opt_returnOnFirstMatch \|\| false;
gyrm	2357	432	this.ignoreNonElementNodesForNTA = opt_ignoreNonElementNodesForNTA \|\| false;
dfabulich	1919	433	if (opt_parent) {
		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.
		440	this.root = node;
		441	} else {
		442	this.root = node.ownerDocument;
		443	}
		444	}
		445
		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,
gyrm	1931	450	opt_nodelist \|\| this.nodelist, this, this.caseInsensitive,
gyrm	2357	451	this.ignoreAttributesWithoutValue, this.returnOnFirstMatch,
gyrm	2357	452	this.ignoreNonElementNodesForNTA);
dfabulich	1919	453	};
		454
		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;
		459	return;
		460	}
		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);
		467	} else {
		468	// DGF What if it's null?
		469	this.variables[name] = new StringValue(value);
		470	}
		471	};
		472
		473	ExprContext.prototype.getVariable = function(name) {
		474	if (typeof this.variables[name] != 'undefined') {
		475	return this.variables[name];
		476
		477	} else if (this.parent) {
		478	return this.parent.getVariable(name);
		479
		480	} else {
		481	return null;
		482	}
		483	};
		484
		485	ExprContext.prototype.setNode = function(position) {
		486	this.node = this.nodelist[position];
		487	this.position = position;
		488	};
		489
		490	ExprContext.prototype.contextSize = function() {
		491	return this.nodelist.length;
		492	};
		493
		494	ExprContext.prototype.isCaseInsensitive = function() {
		495	return this.caseInsensitive;
		496	};
		497
		498	ExprContext.prototype.setCaseInsensitive = function(caseInsensitive) {
		499	return this.caseInsensitive = caseInsensitive;
		500	};
		501
gyrm	1931	502	ExprContext.prototype.isIgnoreAttributesWithoutValue = function() {
		503	return this.ignoreAttributesWithoutValue;
		504	};
		505
		506	ExprContext.prototype.setIgnoreAttributesWithoutValue = function(ignore) {
		507	return this.ignoreAttributesWithoutValue = ignore;
		508	};
		509
gyrm	2026	510	ExprContext.prototype.isReturnOnFirstMatch = function() {
		511	return this.returnOnFirstMatch;
		512	};
		513
		514	ExprContext.prototype.setReturnOnFirstMatch = function(returnOnFirstMatch) {
		515	return this.returnOnFirstMatch = returnOnFirstMatch;
		516	};
		517
gyrm	2357	518	ExprContext.prototype.isIgnoreNonElementNodesForNTA = function() {
		519	return this.ignoreNonElementNodesForNTA;
		520	};
		521
		522	ExprContext.prototype.setIgnoreNonElementNodesForNTA = function(ignoreNonElementNodesForNTA) {
		523	return this.ignoreNonElementNodesForNTA = ignoreNonElementNodesForNTA;
		524	};
		525
dfabulich	1919	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.)
		535	//
		536	// The four types are:
		537	//
		538	// StringValue
		539	//
		540	// NumberValue
		541	//
		542	// BooleanValue
		543	//
		544	// NodeSetValue
		545	//
		546	// The common interface of the value classes consists of methods that
		547	// implement the XPath type coercion rules:
		548	//
		549	// stringValue() -- returns the value as a JavaScript String,
		550	//
		551	// numberValue() -- returns the value as a JavaScript Number,
		552	//
		553	// booleanValue() -- returns the value as a JavaScript Boolean,
		554	//
		555	// nodeSetValue() -- returns the value as a JavaScript Array of DOM
		556	// Node objects.
		557	//
		558
		559	function StringValue(value) {
		560	this.value = value;
		561	this.type = 'string';
		562	}
		563
		564	StringValue.prototype.stringValue = function() {
		565	return this.value;
		566	}
		567
		568	StringValue.prototype.booleanValue = function() {
		569	return this.value.length > 0;
		570	}
		571
		572	StringValue.prototype.numberValue = function() {
		573	return this.value - 0;
		574	}
		575
		576	StringValue.prototype.nodeSetValue = function() {
		577	throw this;
		578	}
		579
		580	function BooleanValue(value) {
		581	this.value = value;
		582	this.type = 'boolean';
		583	}
		584
		585	BooleanValue.prototype.stringValue = function() {
		586	return '' + this.value;
		587	}
		588
		589	BooleanValue.prototype.booleanValue = function() {
590	return this.value;
591	}
592
593	BooleanValue.prototype.numberValue = function() {
594	return this.value ? 1 : 0;
595	}
596
597	BooleanValue.prototype.nodeSetValue = function() {
598	throw this;
599	}
600
601	function NumberValue(value) {
602	this.value = value;
603	this.type = 'number';
604	}
605
606	NumberValue.prototype.stringValue = function() {
607	return '' + this.value;
608	}
609
610	NumberValue.prototype.booleanValue = function() {
611	return !!this.value;
612	}
613
614	NumberValue.prototype.numberValue = function() {
615	return this.value - 0;
616	}
617
618	NumberValue.prototype.nodeSetValue = function() {
619	throw this;
620	}
621
622	function NodeSetValue(value) {
623	this.value = value;
624	this.type = 'node-set';
625	}
626
627	NodeSetValue.prototype.stringValue = function() {
628	if (this.value.length == 0) {
629	return '';
630	} else {
631	return xmlValue(this.value[0]);
632	}
633	}
634
635	NodeSetValue.prototype.booleanValue = function() {
636	return this.value.length > 0;
637	}
638
639	NodeSetValue.prototype.numberValue = function() {
640	return this.stringValue() - 0;
641	}
642
643	NodeSetValue.prototype.nodeSetValue = function() {
644	return this.value;
645	};
646
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.
653	//
654	// The common expression interface consists of the following methods:
655	//
656	// evaluate(context) -- evaluates the expression, returns a value.
657	//
658	// toString() -- returns the XPath text representation of the
659	// expression (defined in xsltdebug.js).
660	//
661	// parseTree(indent) -- returns a parse tree representation of the
662	// expression (defined in xsltdebug.js).
663
664	function TokenExpr(m) {
665	this.value = m;
666	}
667
668	TokenExpr.prototype.evaluate = function() {
669	return new StringValue(this.value);
670	};
671
672	function LocationExpr() {
673	this.absolute = false;
674	this.steps = [];
675	}
676
677	LocationExpr.prototype.appendStep = function(s) {
678	var combinedStep = this._combineSteps(this.steps[this.steps.length-1], s);
679	if (combinedStep) {
680	this.steps[this.steps.length-1] = combinedStep;
681	} else {
682	this.steps.push(s);
683	}
684	}
685
686	LocationExpr.prototype.prependStep = function(s) {
687	var combinedStep = this._combineSteps(s, this.steps[0]);
688	if (combinedStep) {
689	this.steps[0] = combinedStep;
690	} else {
691	this.steps.unshift(s);
692	}
693	};
694
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) {
gyrm	2092	704	// HBC - commenting out, because this is not a valid reduction
		705	//nextStep.axis = xpathAxis.DESCENDANT;
		706	//return nextStep;
dfabulich	1919	707	} else if (nextStep.axis == xpathAxis.SELF) {
		708	nextStep.axis = xpathAxis.DESCENDANT_OR_SELF;
		709	return nextStep;
		710	}
		711	} else if (prevStep.axis == xpathAxis.DESCENDANT) {
		712	if (nextStep.axis == xpathAxis.SELF) {
		713	nextStep.axis = xpathAxis.DESCENDANT;
		714	return nextStep;
		715	}
		716	}
		717	}
		718	return null;
		719	}
		720
		721	LocationExpr.prototype.evaluate = function(ctx) {
		722	var start;
		723	if (this.absolute) {
		724	start = ctx.root;
		725
		726	} else {
		727	start = ctx.node;
		728	}
		729
		730	var nodes = [];
		731	xPathStep(nodes, this.steps, 0, start, ctx);
		732	return new NodeSetValue(nodes);
		733	};
		734
		735	function xPathStep(nodes, steps, step, input, ctx) {
		736	var s = steps[step];
		737	var ctx2 = ctx.clone(input);
gyrm	2044	738
		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;
		750	nodelistLoop:
		751	for (var i = 0; i < nLength; ++i) {
		752	var n = nodelist[i];
		753	for (var j = 0; j < pLength; ++j) {
		754	if (!s.predicate[j].evaluate(ctx.clone(n, i, nodelist)).booleanValue()) {
		755	continue nodelistLoop;
		756	}
		757	}
		758	// n survived the predicate tests!
		759	if (step == steps.length - 1) {
		760	nodes.push(n);
		761	}
		762	else {
		763	xPathStep(nodes, steps, step + 1, n, ctx);
		764	}
		765	if (nodes.length > 0) {
		766	break;
		767	}
dfabulich	1919	768	}
gyrm	2044	769	}
		770	else {
		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]);
		779	} else {
		780	xPathStep(nodes, steps, step + 1, nodelist[i], ctx);
		781	}
gyrm	2026	782	}
dfabulich	1919	783	}
		784	}
		785
		786	function StepExpr(axis, nodetest, opt_predicate) {
		787	this.axis = axis;
		788	this.nodetest = nodetest;
		789	this.predicate = opt_predicate \|\| [];
gyrm	2044	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;
		794	break;
		795	}
		796	}
dfabulich	1919	797	}
		798
		799	StepExpr.prototype.appendPredicate = function(p) {
		800	this.predicate.push(p);
gyrm	2044	801	if (!this.hasPositionalPredicate) {
		802	this.hasPositionalPredicate = predicateExprHasPositionalSelector(p.expr);
		803	}
dfabulich	1919	804	}
		805
		806	StepExpr.prototype.evaluate = function(ctx) {
		807	var input = ctx.node;
		808	var nodelist = [];
		809	var skipNodeTest = false;
		810
		811	if (this.nodetest instanceof NodeTestAny) {
		812	skipNodeTest = true;
		813	}
		814
		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).
		818
		819	if (this.axis == xpathAxis.ANCESTOR_OR_SELF) {
		820	nodelist.push(input);
		821	for (var n = input.parentNode; n; n = n.parentNode) {
		822	nodelist.push(n);
		823	}
		824
		825	} else if (this.axis == xpathAxis.ANCESTOR) {
		826	for (var n = input.parentNode; n; n = n.parentNode) {
		827	nodelist.push(n);
		828	}
		829
		830	} else if (this.axis == xpathAxis.ATTRIBUTE) {
gyrm	2045	831	if (this.nodetest.name != undefined) {
gyrm	2044	832	// single-attribute step
gyrm	2045	833	if (input.attributes) {
		834	if (input.attributes instanceof Array) {
		835	// probably evaluating on document created by xmlParse()
		836	copyArray(nodelist, input.attributes);
		837	}
		838	else {
gyrm	2092	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
		844	// node instead
		845	nodelist.push(XNode.create(DOM_ATTRIBUTE_NODE, 'style',
		846	value.cssText, document));
		847	}
		848	else {
		849	nodelist.push(input.attributes[this.nodetest.name]);
		850	}
		851	}
		852	else {
		853	nodelist.push(input.attributes[this.nodetest.name]);
		854	}
gyrm	2045	855	}
gyrm	2045	856	}
gyrm	1931	857	}
gyrm	1931	858	else {
gyrm	2044	859	// all-attributes step
gyrm	2026	860	if (ctx.ignoreAttributesWithoutValue) {
		861	copyArrayIgnoringAttributesWithoutValue(nodelist, input.attributes);
		862	}
		863	else {
		864	copyArray(nodelist, input.attributes);
		865	}
gyrm	1931	866	}
gyrm	2026	867
dfabulich	1919	868	} else if (this.axis == xpathAxis.CHILD) {
		869	copyArray(nodelist, input.childNodes);
		870
		871	} else if (this.axis == xpathAxis.DESCENDANT_OR_SELF) {
		872	if (this.nodetest.evaluate(ctx).booleanValue()) {
		873	nodelist.push(input);
		874	}
gyrm	2357	875	var tagName = xpathExtractTagNameFromNodeTest(this.nodetest, ctx.ignoreNonElementNodesForNTA);
dfabulich	1919	876	xpathCollectDescendants(nodelist, input, tagName);
		877	if (tagName) skipNodeTest = true;
		878
		879	} else if (this.axis == xpathAxis.DESCENDANT) {
gyrm	2357	880	var tagName = xpathExtractTagNameFromNodeTest(this.nodetest, ctx.ignoreNonElementNodesForNTA);
dfabulich	1919	881	xpathCollectDescendants(nodelist, input, tagName);
		882	if (tagName) skipNodeTest = true;
		883
		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) {
		887	nodelist.push(nn);
		888	xpathCollectDescendants(nodelist, nn);
		889	}
		890	}
		891
		892	} else if (this.axis == xpathAxis.FOLLOWING_SIBLING) {
		893	for (var n = input.nextSibling; n; n = n.nextSibling) {
		894	nodelist.push(n);
		895	}
		896
		897	} else if (this.axis == xpathAxis.NAMESPACE) {
		898	alert('not implemented: axis namespace');
		899
		900	} else if (this.axis == xpathAxis.PARENT) {
		901	if (input.parentNode) {
		902	nodelist.push(input.parentNode);
		903	}
		904
		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) {
		908	nodelist.push(nn);
		909	xpathCollectDescendantsReverse(nodelist, nn);
		910	}
		911	}
		912
		913	} else if (this.axis == xpathAxis.PRECEDING_SIBLING) {
		914	for (var n = input.previousSibling; n; n = n.previousSibling) {
		915	nodelist.push(n);
		916	}
		917
		918	} else if (this.axis == xpathAxis.SELF) {
		919	nodelist.push(input);
		920
		921	} else {
		922	throw 'ERROR -- NO SUCH AXIS: ' + this.axis;
		923	}
		924
		925	if (!skipNodeTest) {
		926	// process node test
		927	var nodelist0 = nodelist;
		928	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()) {
		932	nodelist.push(n);
		933	}
		934	}
		935	}
		936
		937	// process predicates
gyrm	2044	938	if (!ctx.returnOnFirstMatch) {
		939	for (var i = 0; i < this.predicate.length; ++i) {
		940	var nodelist0 = nodelist;
		941	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()) {
		945	nodelist.push(n);
		946	}
dfabulich	1919	947	}
		948	}
		949	}
		950
		951	return new NodeSetValue(nodelist);
		952	};
		953
		954	function NodeTestAny() {
		955	this.value = new BooleanValue(true);
		956	}
		957
		958	NodeTestAny.prototype.evaluate = function(ctx) {
		959	return this.value;
		960	};
		961
		962	function NodeTestElementOrAttribute() {}
		963
		964	NodeTestElementOrAttribute.prototype.evaluate = function(ctx) {
		965	return new BooleanValue(
		966	ctx.node.nodeType == DOM_ELEMENT_NODE \|\|
		967	ctx.node.nodeType == DOM_ATTRIBUTE_NODE);
		968	}
		969
		970	function NodeTestText() {}
		971
		972	NodeTestText.prototype.evaluate = function(ctx) {
		973	return new BooleanValue(ctx.node.nodeType == DOM_TEXT_NODE);
		974	}
		975
		976	function NodeTestComment() {}
		977
		978	NodeTestComment.prototype.evaluate = function(ctx) {
		979	return new BooleanValue(ctx.node.nodeType == DOM_COMMENT_NODE);
		980	}
		981
		982	function NodeTestPI(target) {
		983	this.target = target;
		984	}
		985
		986	NodeTestPI.prototype.evaluate = function(ctx) {
		987	return new
		988	BooleanValue(ctx.node.nodeType == DOM_PROCESSING_INSTRUCTION_NODE &&
		989	(!this.target \|\| ctx.node.nodeName == this.target));
		990	}
		991
		992	function NodeTestNC(nsprefix) {
		993	this.regex = new RegExp("^" + nsprefix + ":");
		994	this.nsprefix = nsprefix;
		995	}
		996
		997	NodeTestNC.prototype.evaluate = function(ctx) {
		998	var n = ctx.node;
		999	return new BooleanValue(this.regex.match(n.nodeName));
		1000	}
		1001
		1002	function NodeTestName(name) {
		1003	this.name = name;
		1004	this.re = new RegExp('^' + name + '$', "i");
		1005	}
		1006
		1007	NodeTestName.prototype.evaluate = function(ctx) {
		1008	var n = ctx.node;
		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));
1012	} else {
1013	return new BooleanValue(n.nodeName == this.name);
1014	}
1015	}
1016
1017	function PredicateExpr(expr) {
1018	this.expr = expr;
1019	}
1020
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);
1028	} else {
1029	return new BooleanValue(v.booleanValue());
1030	}
1031	};
1032
1033	function FunctionCallExpr(name) {
1034	this.name = name;
1035	this.args = [];
1036	}
1037
1038	FunctionCallExpr.prototype.appendArg = function(arg) {
1039	this.args.push(arg);
1040	};
1041
1042	FunctionCallExpr.prototype.evaluate = function(ctx) {
1043	var fn = '' + this.name.value;
1044	var f = this.xpathfunctions[fn];
1045	if (f) {
1046	return f.call(this, ctx);
1047	} else {
1048	xpathLog('XPath NO SUCH FUNCTION ' + fn);
1049	return new BooleanValue(false);
1050	}
1051	};
1052
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());
1058	},
1059
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);
1064	},
1065
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);
1070	},
1071
1072	'id': function(ctx) {
1073	assert(this.args.length == 1);
1074	var e = this.args[0].evaluate(ctx);
1075	var ret = [];
1076	var ids;
1077	if (e.type == 'node-set') {
1078	ids = [];
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) {
1083	ids.push(v[ii]);
1084	}
1085	}
1086	} else {
1087	ids = e.stringValue().split(/\s+/);
1088	}
1089	var d = ctx.root;
1090	for (var i = 0; i < ids.length; ++i) {
1091	var n = d.getElementById(ids[i]);
1092	if (n) {
1093	ret.push(n);
1094	}
1095	}
1096	return new NodeSetValue(ret);
1097	},
1098
1099	'local-name': function(ctx) {
1100	alert('not implmented yet: XPath function local-name()');
1101	},
1102
1103	'namespace-uri': function(ctx) {
1104	alert('not implmented yet: XPath function namespace-uri()');
1105	},
1106
1107	'name': function(ctx) {
1108	assert(this.args.length == 1 \|\| this.args.length == 0);
1109	var n;
1110	if (this.args.length == 0) {
1111	n = [ ctx.node ];
1112	} else {
1113	n = this.args[0].evaluate(ctx).nodeSetValue();
1114	}
1115
1116	if (n.length == 0) {
1117	return new StringValue('');
1118	} else {
1119	return new StringValue(n[0].nodeName);
1120	}
1121	},
1122
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());
1127	} else {
1128	return new StringValue(this.args[0].evaluate(ctx).stringValue());
1129	}
1130	},
1131
1132	'concat': function(ctx) {
1133	var ret = '';
1134	for (var i = 0; i < this.args.length; ++i) {
1135	ret += this.args[i].evaluate(ctx).stringValue();
1136	}
1137	return new StringValue(ret);
1138	},
1139
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);
1145	},
gyrm	2026	1146
		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));
		1153	},
dfabulich	1919	1154
		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);
		1160	},
		1161
		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);
		1167	var ret;
		1168	if (i == -1) {
		1169	ret = '';
		1170	} else {
		1171	ret = s0.substr(0,i);
		1172	}
		1173	return new StringValue(ret);
		1174	},
		1175
		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);
		1181	var ret;
		1182	if (i == -1) {
		1183	ret = '';
		1184	} else {
		1185	ret = s0.substr(i + s1.length);
		1186	}
		1187	return new StringValue(ret);
		1188	},
		1189
		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();
		1196	var ret;
		1197	if (this.args.length == 2) {
		1198	var i1 = Math.max(0, Math.round(s1) - 1);
		1199	ret = s0.substr(i1);
		1200
		1201	} else {
		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);
		1207	}
		1208	return new StringValue(ret);
		1209	},
		1210
		1211	'string-length': function(ctx) {
		1212	var s;
		1213	if (this.args.length > 0) {
		1214	s = this.args[0].evaluate(ctx).stringValue();
		1215	} else {
		1216	s = new NodeSetValue([ ctx.node ]).stringValue();
		1217	}
1218	return new NumberValue(s.length);
1219	},
1220
1221	'normalize-space': function(ctx) {
1222	var s;
1223	if (this.args.length > 0) {
1224	s = this.args[0].evaluate(ctx).stringValue();
1225	} else {
1226	s = new NodeSetValue([ ctx.node ]).stringValue();
1227	}
1228	s = s.replace(/^\s/,'').replace(/\s$/,'').replace(/\s+/g, ' ');
1229	return new StringValue(s);
1230	},
1231
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();
1237
1238	for (var i = 0; i < s1.length; ++i) {
1239	s0 = s0.replace(new RegExp(s1.charAt(i), 'g'), s2.charAt(i));
1240	}
1241	return new StringValue(s0);
1242	},
gyrm	2026	1243
		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;
		1252	}
		1253	}
		1254
		1255	try {
		1256	var re = new RegExp(s1, s2);
		1257	}
		1258	catch (e) {
		1259	throw 'Invalid matches argument: ' + s1;
		1260	}
		1261	return new BooleanValue(re.test(s0));
		1262	},
dfabulich	1919	1263
		1264	'boolean': function(ctx) {
		1265	assert(this.args.length == 1);
		1266	return new BooleanValue(this.args[0].evaluate(ctx).booleanValue());
		1267	},
		1268
		1269	'not': function(ctx) {
		1270	assert(this.args.length == 1);
		1271	var ret = !this.args[0].evaluate(ctx).booleanValue();
		1272	return new BooleanValue(ret);
		1273	},
		1274
		1275	'true': function(ctx) {
		1276	assert(this.args.length == 0);
		1277	return new BooleanValue(true);
		1278	},
		1279
		1280	'false': function(ctx) {
		1281	assert(this.args.length == 0);
		1282	return new BooleanValue(false);
		1283	},
		1284
		1285	'lang': function(ctx) {
		1286	assert(this.args.length == 1);
		1287	var lang = this.args[0].evaluate(ctx).stringValue();
		1288	var xmllang;
		1289	var n = ctx.node;
		1290	while (n && n != n.parentNode /* just in case ... */) {
		1291	xmllang = n.getAttribute('xml:lang');
		1292	if (xmllang) {
		1293	break;
		1294	}
		1295	n = n.parentNode;
		1296	}
		1297	if (!xmllang) {
		1298	return new BooleanValue(false);
		1299	} else {
		1300	var re = new RegExp('^' + lang + '$', 'i');
		1301	return new BooleanValue(xmllang.match(re) \|\|
		1302	xmllang.replace(/_.*$/,'').match(re));
		1303	}
		1304	},
		1305
		1306	'number': function(ctx) {
		1307	assert(this.args.length == 1 \|\| this.args.length == 0);
		1308
		1309	if (this.args.length == 1) {
		1310	return new NumberValue(this.args[0].evaluate(ctx).numberValue());
		1311	} else {
		1312	return new NumberValue(new NodeSetValue([ ctx.node ]).numberValue());
		1313	}
		1314	},
		1315
		1316	'sum': function(ctx) {
		1317	assert(this.args.length == 1);
		1318	var n = this.args[0].evaluate(ctx).nodeSetValue();
		1319	var sum = 0;
		1320	for (var i = 0; i < n.length; ++i) {
		1321	sum += xmlValue(n[i]) - 0;
		1322	}
		1323	return new NumberValue(sum);
		1324	},
		1325
		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));
1330	},
1331
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));
1336	},
1337
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));
1342	},
1343
1344	// TODO(mesch): The following functions are custom. There is a
1345	// standard that defines how to add functions, which should be
1346	// applied here.
1347
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();
1352	var ret = '';
1353	for (var i = 0; i < nodes.length; ++i) {
1354	if (ret) {
1355	ret += delim;
1356	}
1357	ret += xmlValue(nodes[i]);
1358	}
1359	return new StringValue(ret);
1360	},
1361
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.
1365
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);
1370	} else {
1371	return this.args[2].evaluate(ctx);
1372	}
1373	},
1374
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.
1378
1379	'ext-cardinal': function(ctx) {
1380	assert(this.args.length >= 1);
1381	var c = this.args[0].evaluate(ctx).numberValue();
1382	var ret = [];
1383	for (var i = 0; i < c; ++i) {
1384	ret.push(ctx.node);
1385	}
1386	return new NodeSetValue(ret);
1387	}
1388	};
1389
1390	function UnionExpr(expr1, expr2) {
1391	this.expr1 = expr1;
1392	this.expr2 = expr2;
1393	}
1394
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) {
1400	var n = nodes2[i2];
1401	var inBoth = false;
1402	for (var i1 = 0; i1 < I1; ++i1) {
1403	if (nodes1[i1] == n) {
1404	inBoth = true;
1405	i1 = I1; // break inner loop
1406	}
1407	}
1408	if (!inBoth) {
1409	nodes1.push(n);
1410	}
1411	}
1412	return new NodeSetValue(nodes1);
1413	};
1414
1415	function PathExpr(filter, rel) {
1416	this.filter = filter;
1417	this.rel = rel;
1418	}
1419
1420	PathExpr.prototype.evaluate = function(ctx) {
gyrm	2072	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;
gyrm	2071	1425	ctx.setReturnOnFirstMatch(false);
dfabulich	1919	1426	var nodes = this.filter.evaluate(ctx).nodeSetValue();
gyrm	2072	1427	ctx.setReturnOnFirstMatch(flag);
gyrm	2072	1428
dfabulich	1919	1429	var nodes1 = [];
gyrm	2072	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) {
		1434	break;
		1435	}
dfabulich	1919	1436	}
gyrm	2072	1437	return new NodeSetValue(nodes1);
dfabulich	1919	1438	}
gyrm	2072	1439	else {
		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]);
		1444	}
		1445	}
		1446	return new NodeSetValue(nodes1);
		1447	}
dfabulich	1919	1448	};
		1449
		1450	function FilterExpr(expr, predicate) {
		1451	this.expr = expr;
		1452	this.predicate = predicate;
		1453	}
		1454
		1455	FilterExpr.prototype.evaluate = function(ctx) {
gyrm	2357	1456	var flag = ctx.returnOnFirstMatch;
gyrm	2357	1457	ctx.setReturnOnFirstMatch(false);
dfabulich	1919	1458	var nodes = this.expr.evaluate(ctx).nodeSetValue();
gyrm	2357	1459	ctx.setReturnOnFirstMatch(flag);
gyrm	2357	1460
dfabulich	1919	1461	for (var i = 0; i < this.predicate.length; ++i) {
		1462	var nodes0 = nodes;
		1463	nodes = [];
		1464	for (var j = 0; j < nodes0.length; ++j) {
		1465	var n = nodes0[j];
		1466	if (this.predicate[i].evaluate(ctx.clone(n, j, nodes0)).booleanValue()) {
		1467	nodes.push(n);
		1468	}
		1469	}
		1470	}
		1471
		1472	return new NodeSetValue(nodes);
		1473	}
		1474
		1475	function UnaryMinusExpr(expr) {
		1476	this.expr = expr;
		1477	}
		1478
		1479	UnaryMinusExpr.prototype.evaluate = function(ctx) {
		1480	return new NumberValue(-this.expr.evaluate(ctx).numberValue());
		1481	};
		1482
		1483	function BinaryExpr(expr1, op, expr2) {
		1484	this.expr1 = expr1;
		1485	this.expr2 = expr2;
		1486	this.op = op;
		1487	}
		1488
		1489	BinaryExpr.prototype.evaluate = function(ctx) {
		1490	var ret;
		1491	switch (this.op.value) {
		1492	case 'or':
		1493	ret = new BooleanValue(this.expr1.evaluate(ctx).booleanValue() \|\|
		1494	this.expr2.evaluate(ctx).booleanValue());
		1495	break;
		1496
		1497	case 'and':
		1498	ret = new BooleanValue(this.expr1.evaluate(ctx).booleanValue() &&
		1499	this.expr2.evaluate(ctx).booleanValue());
		1500	break;
		1501
		1502	case '+':
		1503	ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() +
		1504	this.expr2.evaluate(ctx).numberValue());
		1505	break;
		1506
		1507	case '-':
		1508	ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() -
		1509	this.expr2.evaluate(ctx).numberValue());
		1510	break;
		1511
		1512	case '*':
		1513	ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() *
		1514	this.expr2.evaluate(ctx).numberValue());
		1515	break;
		1516
		1517	case 'mod':
		1518	ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() %
		1519	this.expr2.evaluate(ctx).numberValue());
		1520	break;
		1521
		1522	case 'div':
		1523	ret = new NumberValue(this.expr1.evaluate(ctx).numberValue() /
		1524	this.expr2.evaluate(ctx).numberValue());
1525	break;
1526
1527	case '=':
1528	ret = this.compare(ctx, function(x1, x2) { return x1 == x2; });
1529	break;
1530
1531	case '!=':
1532	ret = this.compare(ctx, function(x1, x2) { return x1 != x2; });
1533	break;
1534
1535	case '<':
1536	ret = this.compare(ctx, function(x1, x2) { return x1 < x2; });
1537	break;
1538
1539	case '<=':
1540	ret = this.compare(ctx, function(x1, x2) { return x1 <= x2; });
1541	break;
1542
1543	case '>':
1544	ret = this.compare(ctx, function(x1, x2) { return x1 > x2; });
1545	break;
1546
1547	case '>=':
1548	ret = this.compare(ctx, function(x1, x2) { return x1 >= x2; });
1549	break;
1550
1551	default:
1552	alert('BinaryExpr.evaluate: ' + this.op.value);
1553	}
1554	return ret;
1555	};
1556
1557	BinaryExpr.prototype.compare = function(ctx, cmp) {
1558	var v1 = this.expr1.evaluate(ctx);
1559	var v2 = this.expr2.evaluate(ctx);
1560
1561	var ret;
1562	if (v1.type == 'node-set' && v2.type == 'node-set') {
1563	var n1 = v1.nodeSetValue();
1564	var n2 = v2.nodeSetValue();
1565	ret = false;
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]))) {
1569	ret = true;
1570	// Break outer loop. Labels confuse the jscompiler and we
1571	// don't use them.
1572	i2 = n2.length;
1573	i1 = n1.length;
1574	}
1575	}
1576	}
1577
1578	} else if (v1.type == 'node-set' \|\| v2.type == 'node-set') {
1579
1580	if (v1.type == 'number') {
1581	var s = v1.numberValue();
1582	var n = v2.nodeSetValue();
1583
1584	ret = false;
1585	for (var i = 0; i < n.length; ++i) {
1586	var nn = xmlValue(n[i]) - 0;
1587	if (cmp(s, nn)) {
1588	ret = true;
1589	break;
1590	}
1591	}
1592
1593	} else if (v2.type == 'number') {
1594	var n = v1.nodeSetValue();
1595	var s = v2.numberValue();
1596
1597	ret = false;
1598	for (var i = 0; i < n.length; ++i) {
1599	var nn = xmlValue(n[i]) - 0;
1600	if (cmp(nn, s)) {
1601	ret = true;
1602	break;
1603	}
1604	}
1605
1606	} else if (v1.type == 'string') {
1607	var s = v1.stringValue();
1608	var n = v2.nodeSetValue();
1609
1610	ret = false;
1611	for (var i = 0; i < n.length; ++i) {
1612	var nn = xmlValue(n[i]);
1613	if (cmp(s, nn)) {
1614	ret = true;
1615	break;
1616	}
1617	}
1618
1619	} else if (v2.type == 'string') {
1620	var n = v1.nodeSetValue();
1621	var s = v2.stringValue();
1622
1623	ret = false;
1624	for (var i = 0; i < n.length; ++i) {
1625	var nn = xmlValue(n[i]);
1626	if (cmp(nn, s)) {
1627	ret = true;
1628	break;
1629	}
1630	}
1631
1632	} else {
1633	ret = cmp(v1.booleanValue(), v2.booleanValue());
1634	}
1635
1636	} else if (v1.type == 'boolean' \|\| v2.type == 'boolean') {
1637	ret = cmp(v1.booleanValue(), v2.booleanValue());
1638
1639	} else if (v1.type == 'number' \|\| v2.type == 'number') {
1640	ret = cmp(v1.numberValue(), v2.numberValue());
1641
1642	} else {
1643	ret = cmp(v1.stringValue(), v2.stringValue());
1644	}
1645
1646	return new BooleanValue(ret);
1647	}
1648
1649	function LiteralExpr(value) {
1650	this.value = value;
1651	}
1652
1653	LiteralExpr.prototype.evaluate = function(ctx) {
1654	return new StringValue(this.value);
1655	};
1656
1657	function NumberExpr(value) {
1658	this.value = value;
1659	}
1660
1661	NumberExpr.prototype.evaluate = function(ctx) {
1662	return new NumberValue(this.value);
1663	};
1664
1665	function VariableExpr(name) {
1666	this.name = name;
1667	}
1668
1669	VariableExpr.prototype.evaluate = function(ctx) {
1670	return ctx.getVariable(this.name);
1671	}
1672
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.
1681
1682	function makeTokenExpr(m) {
1683	return new TokenExpr(m);
1684	}
1685
1686	function passExpr(e) {
1687	return e;
1688	}
1689
1690	function makeLocationExpr1(slash, rel) {
1691	rel.absolute = true;
1692	return rel;
1693	}
1694
1695	function makeLocationExpr2(dslash, rel) {
1696	rel.absolute = true;
1697	rel.prependStep(makeAbbrevStep(dslash.value));
1698	return rel;
1699	}
1700
1701	function makeLocationExpr3(slash) {
1702	var ret = new LocationExpr();
1703	ret.appendStep(makeAbbrevStep('.'));
1704	ret.absolute = true;
1705	return ret;
1706	}
1707
1708	function makeLocationExpr4(dslash) {
1709	var ret = new LocationExpr();
1710	ret.absolute = true;
1711	ret.appendStep(makeAbbrevStep(dslash.value));
1712	return ret;
1713	}
1714
1715	function makeLocationExpr5(step) {
1716	var ret = new LocationExpr();
1717	ret.appendStep(step);
1718	return ret;
1719	}
1720
1721	function makeLocationExpr6(rel, slash, step) {
1722	rel.appendStep(step);
1723	return rel;
1724	}
1725
1726	function makeLocationExpr7(rel, dslash, step) {
1727	rel.appendStep(makeAbbrevStep(dslash.value));
1728	rel.appendStep(step);
1729	return rel;
1730	}
1731
1732	function makeStepExpr1(dot) {
1733	return makeAbbrevStep(dot.value);
1734	}
1735
1736	function makeStepExpr2(ddot) {
1737	return makeAbbrevStep(ddot.value);
1738	}
1739
1740	function makeStepExpr3(axisname, axis, nodetest) {
1741	return new StepExpr(axisname.value, nodetest);
1742	}
1743
1744	function makeStepExpr4(at, nodetest) {
1745	return new StepExpr('attribute', nodetest);
1746	}
1747
1748	function makeStepExpr5(nodetest) {
1749	return new StepExpr('child', nodetest);
1750	}
1751
1752	function makeStepExpr6(step, predicate) {
1753	step.appendPredicate(predicate);
1754	return step;
1755	}
1756
1757	function makeAbbrevStep(abbrev) {
1758	switch (abbrev) {
1759	case '//':
1760	return new StepExpr('descendant-or-self', new NodeTestAny);
1761
1762	case '.':
1763	return new StepExpr('self', new NodeTestAny);
1764
1765	case '..':
1766	return new StepExpr('parent', new NodeTestAny);
1767	}
1768	}
1769
1770	function makeNodeTestExpr1(asterisk) {
1771	return new NodeTestElementOrAttribute;
1772	}
1773
1774	function makeNodeTestExpr2(ncname, colon, asterisk) {
1775	return new NodeTestNC(ncname.value);
1776	}
1777
1778	function makeNodeTestExpr3(qname) {
1779	return new NodeTestName(qname.value);
1780	}
1781
1782	function makeNodeTestExpr4(typeo, parenc) {
1783	var type = typeo.value.replace(/\s*\($/, '');
1784	switch(type) {
1785	case 'node':
1786	return new NodeTestAny;
1787
1788	case 'text':
1789	return new NodeTestText;
1790
1791	case 'comment':
1792	return new NodeTestComment;
1793
1794	case 'processing-instruction':
1795	return new NodeTestPI('');
1796	}
1797	}
1798
1799	function makeNodeTestExpr5(typeo, target, parenc) {
1800	var type = typeo.replace(/\s*\($/, '');
1801	if (type != 'processing-instruction') {
1802	throw type;
1803	}
1804	return new NodeTestPI(target.value);
1805	}
1806
1807	function makePredicateExpr(pareno, expr, parenc) {
1808	return new PredicateExpr(expr);
1809	}
1810
1811	function makePrimaryExpr(pareno, expr, parenc) {
1812	return expr;
1813	}
1814
1815	function makeFunctionCallExpr1(name, pareno, parenc) {
1816	return new FunctionCallExpr(name);
1817	}
1818
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]);
1824	}
1825	return ret;
1826	}
1827
1828	function makeArgumentExpr(comma, expr) {
1829	return expr;
1830	}
1831
1832	function makeUnionExpr(expr1, pipe, expr2) {
1833	return new UnionExpr(expr1, expr2);
1834	}
1835
1836	function makePathExpr1(filter, slash, rel) {
1837	return new PathExpr(filter, rel);
1838	}
1839
1840	function makePathExpr2(filter, dslash, rel) {
1841	rel.prependStep(makeAbbrevStep(dslash.value));
1842	return new PathExpr(filter, rel);
1843	}
1844
1845	function makeFilterExpr(expr, predicates) {
1846	if (predicates.length > 0) {
1847	return new FilterExpr(expr, predicates);
1848	} else {
1849	return expr;
1850	}
1851	}
1852
1853	function makeUnaryMinusExpr(minus, expr) {
1854	return new UnaryMinusExpr(expr);
1855	}
1856
1857	function makeBinaryExpr(expr1, op, expr2) {
1858	return new BinaryExpr(expr1, op, expr2);
1859	}
1860
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);
1865	}
1866
1867	function makeNumberExpr(token) {
1868	return new NumberExpr(token.value);
1869	}
1870
1871	function makeVariableReference(dollar, name) {
1872	return new VariableExpr(name.value);
1873	}
1874
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();
1884	c.appendStep(b);
1885	return c;
1886	} else if (expr.match(/^[0-9]+$/)) {
1887	return new NumberExpr(expr);
1888	} else {
1889	var a = new NodeTestName(expr);
1890	var b = new StepExpr('child', a);
1891	var c = new LocationExpr();
1892	c.appendStep(b);
1893	return c;
1894	}
1895	}
1896
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);
1903	c.appendStep(b);
1904	}
1905	return c;
1906	}
1907
1908	// The axes of XPath expressions.
1909
1910	var xpathAxis = {
1911	ANCESTOR_OR_SELF: 'ancestor-or-self',
1912	ANCESTOR: 'ancestor',
1913	ATTRIBUTE: 'attribute',
1914	CHILD: 'child',
1915	DESCENDANT_OR_SELF: 'descendant-or-self',
1916	DESCENDANT: 'descendant',
1917	FOLLOWING_SIBLING: 'following-sibling',
1918	FOLLOWING: 'following',
1919	NAMESPACE: 'namespace',
1920	PARENT: 'parent',
1921	PRECEDING_SIBLING: 'preceding-sibling',
1922	PRECEDING: 'preceding',
1923	SELF: 'self'
1924	};
1925
1926	var xpathAxesRe = [
1927	xpathAxis.ANCESTOR_OR_SELF,
1928	xpathAxis.ANCESTOR,
1929	xpathAxis.ATTRIBUTE,
1930	xpathAxis.CHILD,
1931	xpathAxis.DESCENDANT_OR_SELF,
1932	xpathAxis.DESCENDANT,
1933	xpathAxis.FOLLOWING_SIBLING,
1934	xpathAxis.FOLLOWING,
1935	xpathAxis.NAMESPACE,
1936	xpathAxis.PARENT,
1937	xpathAxis.PRECEDING_SIBLING,
1938	xpathAxis.PRECEDING,
1939	xpathAxis.SELF
1940	].join('\|');
1941
1942
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!
1948
1949	// NOTE: tabular formatting is the big exception, but here it should
1950	// be OK.
1951
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("^@") };
1963
1964	var TOK_COMMA = { label: ",", re: new RegExp("^,") };
1965
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 };
1978
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("^\\$") };
1982
1983	var TOK_NCNAME = { label: "[ncname]", re: new RegExp('^' + XML_NC_NAME) };
1984
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 = {
1988	label: "[litqq]",
1989	prec: 20,
1990	re: new RegExp('^"[^\\"]*"')
1991	};
1992
1993	var TOK_NUMBER = {
1994	label: "[number]",
1995	prec: 35,
1996	re: new RegExp('^\\d+(\\.\\d*)?') };
1997
1998	var TOK_QNAME = {
1999	label: "[qname]",
2000	re: new RegExp('^(' + XML_NC_NAME + ':)?' + XML_NC_NAME)
2001	};
2002
2003	var TOK_NODEO = {
2004	label: "[nodetest-start]",
2005	re: new RegExp('^(processing-instruction\|comment\|text\|node)\\(')
2006	};
2007
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.
2012	//
2013	// NOTE: order of this list is important, because the first match
2014	// counts. Cf. DDOT and DOT, and AXIS and COLON.
2015
2016	var xpathTokenRules = [
2017	TOK_DSLASH,
2018	TOK_SLASH,
2019	TOK_DDOT,
2020	TOK_DOT,
2021	TOK_AXIS,
2022	TOK_COLON,
2023	TOK_AXISNAME,
2024	TOK_NODEO,
2025	TOK_PARENO,
2026	TOK_PARENC,
2027	TOK_BRACKO,
2028	TOK_BRACKC,
2029	TOK_AT,
2030	TOK_COMMA,
2031	TOK_OR,
2032	TOK_AND,
2033	TOK_NEQ,
2034	TOK_EQ,
2035	TOK_GE,
2036	TOK_GT,
2037	TOK_LE,
2038	TOK_LT,
2039	TOK_PLUS,
2040	TOK_MINUS,
2041	TOK_ASTERISK,
2042	TOK_PIPE,
2043	TOK_MOD,
2044	TOK_DIV,
2045	TOK_LITERALQ,
2046	TOK_LITERALQQ,
2047	TOK_NUMBER,
2048	TOK_QNAME,
2049	TOK_NCNAME,
2050	TOK_DOLLAR
2051	];
2052
2053	// All the nonterminals of the grammar. The nonterminal objects are
2054	// identified by object identity; the labels are used in the debug
2055	// output only.
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" };
2073
2074	var xpathNonTerminals = [
2075	XPathLocationPath,
2076	XPathRelativeLocationPath,
2077	XPathAbsoluteLocationPath,
2078	XPathStep,
2079	XPathNodeTest,
2080	XPathPredicate,
2081	XPathLiteral,
2082	XPathExpr,
2083	XPathPrimaryExpr,
2084	XPathVariableReference,
2085	XPathNumber,
2086	XPathFunctionCall,
2087	XPathArgumentRemainder,
2088	XPathPathExpr,
2089	XPathUnionExpr,
2090	XPathFilterExpr,
2091	XPathDigits
2092	];
2093
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: "+" };
2098
2099	// Tag for left associativity (right assoc is implied by undefined).
2100	var ASSOC_LEFT = true;
2101
2102	// The productions of the grammar. Columns of the table:
2103	//
2104	// - target nonterminal,
2105	// - pattern,
2106	// - precedence,
2107	// - semantic value factory
2108	//
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.
2115	//
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.
2122
2123	// DGF As it stands, these precedences are purely empirical; we're
2124	// not sure they can be made to be consistent at all.
2125
2126	var xpathGrammarRules =
2127	[
2128	[ XPathLocationPath, [ XPathRelativeLocationPath ], 18,
2129	passExpr ],
2130	[ XPathLocationPath, [ XPathAbsoluteLocationPath ], 18,
2131	passExpr ],
2132
2133	[ XPathAbsoluteLocationPath, [ TOK_SLASH, XPathRelativeLocationPath ], 18,
2134	makeLocationExpr1 ],
2135	[ XPathAbsoluteLocationPath, [ TOK_DSLASH, XPathRelativeLocationPath ], 18,
2136	makeLocationExpr2 ],
2137
2138	[ XPathAbsoluteLocationPath, [ TOK_SLASH ], 0,
2139	makeLocationExpr3 ],
2140	[ XPathAbsoluteLocationPath, [ TOK_DSLASH ], 0,
2141	makeLocationExpr4 ],
2142
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 ],
2151
2152	[ XPathStep, [ TOK_DOT ], 33,
2153	makeStepExpr1 ],
2154	[ XPathStep, [ TOK_DDOT ], 33,
2155	makeStepExpr2 ],
2156	[ XPathStep,
2157	[ TOK_AXISNAME, TOK_AXIS, XPathNodeTest ], 33,
2158	makeStepExpr3 ],
2159	[ XPathStep, [ TOK_AT, XPathNodeTest ], 33,
2160	makeStepExpr4 ],
2161	[ XPathStep, [ XPathNodeTest ], 33,
2162	makeStepExpr5 ],
2163	[ XPathStep, [ XPathStep, XPathPredicate ], 33,
2164	makeStepExpr6 ],
2165
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 ],
2176
2177	[ XPathPredicate, [ TOK_BRACKO, XPathExpr, TOK_BRACKC ], 33,
2178	makePredicateExpr ],
2179
2180	[ XPathPrimaryExpr, [ XPathVariableReference ], 33,
2181	passExpr ],
2182	[ XPathPrimaryExpr, [ TOK_PARENO, XPathExpr, TOK_PARENC ], 33,
2183	makePrimaryExpr ],
2184	[ XPathPrimaryExpr, [ XPathLiteral ], 30,
2185	passExpr ],
2186	[ XPathPrimaryExpr, [ XPathNumber ], 30,
2187	passExpr ],
2188	[ XPathPrimaryExpr, [ XPathFunctionCall ], 31,
2189	passExpr ],
2190
2191	[ XPathFunctionCall, [ TOK_QNAME, TOK_PARENO, TOK_PARENC ], -1,
2192	makeFunctionCallExpr1 ],
2193	[ XPathFunctionCall,
2194	[ TOK_QNAME, TOK_PARENO, XPathExpr, XPathArgumentRemainder, Q_MM,
2195	TOK_PARENC ], -1,
2196	makeFunctionCallExpr2 ],
2197	[ XPathArgumentRemainder, [ TOK_COMMA, XPathExpr ], -1,
2198	makeArgumentExpr ],
2199
2200	[ XPathUnionExpr, [ XPathPathExpr ], 20,
2201	passExpr ],
2202	[ XPathUnionExpr, [ XPathUnionExpr, TOK_PIPE, XPathPathExpr ], 20,
2203	makeUnionExpr ],
2204
2205	[ XPathPathExpr, [ XPathLocationPath ], 20,
2206	passExpr ],
2207	[ XPathPathExpr, [ XPathFilterExpr ], 19,
2208	passExpr ],
2209	[ XPathPathExpr,
2210	[ XPathFilterExpr, TOK_SLASH, XPathRelativeLocationPath ], 19,
2211	makePathExpr1 ],
2212	[ XPathPathExpr,
2213	[ XPathFilterExpr, TOK_DSLASH, XPathRelativeLocationPath ], 19,
2214	makePathExpr2 ],
2215
2216	[ XPathFilterExpr, [ XPathPrimaryExpr, XPathPredicate, Q_MM ], 31,
2217	makeFilterExpr ],
2218
2219	[ XPathExpr, [ XPathPrimaryExpr ], 16,
2220	passExpr ],
2221	[ XPathExpr, [ XPathUnionExpr ], 16,
2222	passExpr ],
2223
2224	[ XPathExpr, [ TOK_MINUS, XPathExpr ], -1,
2225	makeUnaryMinusExpr ],
2226
2227	[ XPathExpr, [ XPathExpr, TOK_OR, XPathExpr ], -1,
2228	makeBinaryExpr ],
2229	[ XPathExpr, [ XPathExpr, TOK_AND, XPathExpr ], -1,
2230	makeBinaryExpr ],
2231
2232	[ XPathExpr, [ XPathExpr, TOK_EQ, XPathExpr ], -1,
2233	makeBinaryExpr ],
2234	[ XPathExpr, [ XPathExpr, TOK_NEQ, XPathExpr ], -1,
2235	makeBinaryExpr ],
2236
2237	[ XPathExpr, [ XPathExpr, TOK_LT, XPathExpr ], -1,
2238	makeBinaryExpr ],
2239	[ XPathExpr, [ XPathExpr, TOK_LE, XPathExpr ], -1,
2240	makeBinaryExpr ],
2241	[ XPathExpr, [ XPathExpr, TOK_GT, XPathExpr ], -1,
2242	makeBinaryExpr ],
2243	[ XPathExpr, [ XPathExpr, TOK_GE, XPathExpr ], -1,
2244	makeBinaryExpr ],
2245
2246	[ XPathExpr, [ XPathExpr, TOK_PLUS, XPathExpr ], -1,
2247	makeBinaryExpr, ASSOC_LEFT ],
2248	[ XPathExpr, [ XPathExpr, TOK_MINUS, XPathExpr ], -1,
2249	makeBinaryExpr, ASSOC_LEFT ],
2250
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 ],
2257
2258	[ XPathLiteral, [ TOK_LITERALQ ], -1,
2259	makeLiteralExpr ],
2260	[ XPathLiteral, [ TOK_LITERALQQ ], -1,
2261	makeLiteralExpr ],
2262
2263	[ XPathNumber, [ TOK_NUMBER ], -1,
2264	makeNumberExpr ],
2265
2266	[ XPathVariableReference, [ TOK_DOLLAR, TOK_QNAME ], 200,
2267	makeVariableReference ]
2268	];
2269
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.
2273
2274	var xpathRules = [];
2275
2276	function xpathParseInit() {
2277	if (xpathRules.length) {
2278	return;
2279	}
2280
2281	// Some simple optimizations for the xpath expression parser: sort
2282	// grammar rules descending by length, so that the longest match is
2283	// first found.
2284
2285	xpathGrammarRules.sort(function(a,b) {
2286	var la = a[1].length;
2287	var lb = b[1].length;
2288	if (la < lb) {
2289	return 1;
2290	} else if (la > lb) {
2291	return -1;
2292	} else {
2293	return 0;
2294	}
2295	});
2296
2297	var k = 1;
2298	for (var i = 0; i < xpathNonTerminals.length; ++i) {
2299	xpathNonTerminals[i].key = k++;
2300	}
2301
2302	for (i = 0; i < xpathTokenRules.length; ++i) {
2303	xpathTokenRules[i].key = k++;
2304	}
2305
2306	xpathLog('XPath parse INIT: ' + k + ' rules');
2307
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.
2312	//
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.
2316
2317	function push_(array, position, element) {
2318	if (!array[position]) {
2319	array[position] = [];
2320	}
2321	array[position].push(element);
2322	}
2323
2324	for (i = 0; i < xpathGrammarRules.length; ++i) {
2325	var rule = xpathGrammarRules[i];
2326	var pattern = rule[1];
2327
2328	for (var j = pattern.length - 1; j >= 0; --j) {
2329	if (pattern[j] == Q_1M) {
2330	push_(xpathRules, pattern[j-1].key, rule);
2331	break;
2332
2333	} else if (pattern[j] == Q_MM \|\| pattern[j] == Q_01) {
2334	push_(xpathRules, pattern[j-1].key, rule);
2335	--j;
2336
2337	} else {
2338	push_(xpathRules, pattern[j].key, rule);
2339	break;
2340	}
2341	}
2342	}
2343
2344	xpathLog('XPath parse INIT: ' + xpathRules.length + ' rule bins');
2345
2346	var sum = 0;
2347	mapExec(xpathRules, function(i) {
2348	if (i) {
2349	sum += i.length;
2350	}
2351	});
2352
2353	xpathLog('XPath parse INIT: ' + (sum / xpathRules.length) +
2354	' average bin size');
2355	}
2356
2357	// Local utility functions that are used by the lexer or parser.
2358
2359	function xpathCollectDescendants(nodelist, node, opt_tagName) {
2360	if (opt_tagName && node.getElementsByTagName) {
2361	copyArray(nodelist, node.getElementsByTagName(opt_tagName));
2362	return;
2363	}
2364	for (var n = node.firstChild; n; n = n.nextSibling) {
2365	nodelist.push(n);
2366	xpathCollectDescendants(nodelist, n);
2367	}
2368	}
2369
gyrm	2357	2370	/**
		2371	* DGF - extract a tag name suitable for getElementsByTagName
		2372	*
		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.
		2378	*/
		2379	function xpathExtractTagNameFromNodeTest(nodetest, ignoreNonElementNodesForNTA) {
dfabulich	1919	2380	if (nodetest instanceof NodeTestName) {
dfabulich	1919	2381	return nodetest.name;
gyrm	2357	2382	}
		2383	if ((ignoreNonElementNodesForNTA && nodetest instanceof NodeTestAny) \|\|
		2384	nodetest instanceof NodeTestElementOrAttribute) {
dfabulich	1919	2385	return "*";
		2386	}
		2387	}
		2388
		2389	function xpathCollectDescendantsReverse(nodelist, node) {
		2390	for (var n = node.lastChild; n; n = n.previousSibling) {
		2391	nodelist.push(n);
		2392	xpathCollectDescendantsReverse(nodelist, n);
		2393	}
		2394	}
		2395
		2396
		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));
		2402	return ret;
		2403	}
		2404
		2405	// Utility function to sort a list of nodes. Used by xsltSort() and
		2406	// nxslSelect().
		2407	function xpathSort(input, sort) {
		2408	if (sort.length == 0) {
		2409	return;
		2410	}
		2411
		2412	var sortlist = [];
		2413
		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 ]);
		2418
		2419	for (var j = 0; j < sort.length; ++j) {
		2420	var s = sort[j];
		2421	var value = s.expr.evaluate(context);
		2422
		2423	var evalue;
		2424	if (s.type == 'text') {
		2425	evalue = value.stringValue();
		2426	} else if (s.type == 'number') {
		2427	evalue = value.numberValue();
		2428	}
		2429	sortitem.key.push({ value: evalue, order: s.order });
		2430	}
		2431
		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' });
		2436
		2437	sortlist.push(sortitem);
		2438	}
		2439
		2440	sortlist.sort(xpathSortByKey);
		2441
		2442	var nodes = [];
		2443	for (var i = 0; i < sortlist.length; ++i) {
		2444	nodes.push(sortlist[i].node);
		2445	}
		2446	input.nodelist = nodes;
		2447	input.setNode(0);
		2448	}
2449
2450
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.
2454	//
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
2457	// uncommon.
2458	function xpathSortByKey(v1, v2) {
2459	// NOTE: Sort key vectors of different length never occur in
2460	// xsltSort.
2461
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) {
2465	return +1 * o;
2466	} else if (v1.key[i].value < v2.key[i].value) {
2467	return -1 * o;
2468	}
2469	}
2470
2471	return 0;
2472	}
2473
2474
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);
2480	return ret;
2481	}