001: package net.sf.saxon.pattern;
002:
003: import net.sf.saxon.expr.*;
004: import net.sf.saxon.om.*;
005: import net.sf.saxon.style.ExpressionContext;
006: import net.sf.saxon.trace.Location;
007: import net.sf.saxon.trans.DynamicError;
008: import net.sf.saxon.trans.StaticError;
009: import net.sf.saxon.trans.XPathException;
010: import net.sf.saxon.type.ItemType;
011: import net.sf.saxon.type.Type;
012: import net.sf.saxon.type.TypeHierarchy;
013: import net.sf.saxon.value.BooleanValue;
014: import net.sf.saxon.value.IntegerValue;
015:
016: import java.util.Arrays;
017: import java.util.Collections;
018: import java.util.Iterator;
019:
020: /**
021: * A LocationPathPattern represents a path, for example of the form A/B/C... The components are represented
022: * as a linked list, each component pointing to its predecessor
023: */
024:
025: public final class LocationPathPattern extends Pattern {
026:
027: // the following public variables are exposed to the ExpressionParser
028:
029: public Pattern parentPattern = null;
030: public Pattern ancestorPattern = null;
031: public NodeTest nodeTest = AnyNodeTest.getInstance();
032: protected Expression[] filters = null;
033: protected int numberOfFilters = 0;
034: protected Expression equivalentExpr = null;
035: protected boolean firstElementPattern = false;
036: protected boolean lastElementPattern = false;
037: protected boolean specialFilter = false;
038: private Expression variableBinding = null;
039: private NodeTest refinedNodeTest = null;
040:
041: /**
042: * Add a filter to the pattern (while under construction)
043: * @param filter The predicate (a boolean expression or numeric expression) to be added
044: */
045:
046: public void addFilter(Expression filter) {
047: if (filters == null) {
048: filters = new Expression[3];
049: } else if (numberOfFilters == filters.length) {
050: Expression[] f2 = new Expression[numberOfFilters * 2];
051: System.arraycopy(filters, 0, f2, 0, numberOfFilters);
052: filters = f2;
053: }
054: filters[numberOfFilters++] = filter;
055: ExpressionTool.makeParentReferences(filter);
056: if (filter instanceof ComputedExpression) {
057: ((ComputedExpression) filter).setParentExpression(this );
058: }
059: }
060:
061: /**
062: * Simplify the pattern: perform any context-independent optimisations
063: */
064:
065: public Pattern simplify(StaticContext env) throws XPathException {
066:
067: // detect the simple cases: no parent or ancestor pattern, no predicates
068:
069: if (parentPattern == null && ancestorPattern == null
070: && filters == null && !firstElementPattern
071: && !lastElementPattern) {
072: NodeTestPattern ntp = new NodeTestPattern(nodeTest);
073: ntp.setSystemId(getSystemId());
074: ntp.setLineNumber(getLineNumber());
075: return ntp;
076: }
077:
078: // simplify each component of the pattern
079:
080: if (parentPattern != null) {
081: parentPattern = parentPattern.simplify(env);
082: } else if (ancestorPattern != null) {
083: ancestorPattern = ancestorPattern.simplify(env);
084: }
085:
086: if (filters != null) {
087: for (int i = numberOfFilters - 1; i >= 0; i--) {
088: Expression filter = filters[i];
089: filter = filter.simplify(env);
090: filters[i] = filter;
091: int dep = filter.getDependencies();
092: if ((dep & StaticProperty.DEPENDS_ON_CURRENT_GROUP) != 0) {
093: String errorCode = "XTSE1060";
094: String function = "current-group()";
095: if (toString().indexOf("current-grouping-key") >= 0) {
096: errorCode = "XTSE1070";
097: function = "current-grouping-key()";
098: }
099: StaticError err = new StaticError("The " + function
100: + " function cannot be used in a pattern");
101: err.setErrorCode(errorCode);
102: throw err;
103: }
104: }
105: }
106:
107: return this ;
108: }
109:
110: /**
111: * Type-check the pattern, performing any type-dependent optimizations.
112: * @return the optimised Pattern
113: */
114:
115: public Pattern analyze(StaticContext env, ItemType contextItemType)
116: throws XPathException {
117:
118: // analyze each component of the pattern
119: final TypeHierarchy th = env.getNamePool().getTypeHierarchy();
120: if (parentPattern != null) {
121: parentPattern = parentPattern.analyze(env, contextItemType);
122: // Check that this step in the pattern makes sense in the context of the parent step
123: AxisExpression step;
124: if (nodeTest.getPrimitiveType() == Type.ATTRIBUTE) {
125: step = new AxisExpression(Axis.ATTRIBUTE, nodeTest);
126: } else {
127: step = new AxisExpression(Axis.CHILD, nodeTest);
128: }
129: step.setLocationId(env.getLocationMap().allocateLocationId(
130: env.getSystemId(), getLineNumber()));
131: step.setParentExpression(this );
132: Expression exp = step.typeCheck(env, parentPattern
133: .getNodeTest());
134: refinedNodeTest = (NodeTest) exp.getItemType(th);
135: } else if (ancestorPattern != null) {
136: ancestorPattern = ancestorPattern.analyze(env,
137: contextItemType);
138: }
139:
140: if (filters != null) {
141: for (int i = numberOfFilters - 1; i >= 0; i--) {
142: Expression filter = filters[i].typeCheck(env,
143: getNodeTest());
144: // System.err.println("Filter after analyze:");filter.display(10);
145: filters[i] = filter;
146: // if the last filter is constant true, remove it
147: if ((filter instanceof BooleanValue)
148: && ((BooleanValue) filter).getBooleanValue()) {
149: if (i == numberOfFilters - 1) {
150: numberOfFilters--;
151: } // otherwise don't bother doing anything with it.
152: }
153:
154: // patterns are used outside XSLT, for internally-generated key definitions;
155: // but in this case they never contain variable references or calls on current(). So we only need to
156: // allocate slots in the XSLT case
157: if (env instanceof ExpressionContext) {
158: ((ExpressionContext) env).getStyleElement()
159: .allocateSlots(filter);
160: filters[i] = filter;
161: }
162: }
163: }
164:
165: // see if it's an element pattern with a single positional predicate of [1]
166:
167: if (nodeTest.getPrimitiveType() == Type.ELEMENT
168: && numberOfFilters == 1) {
169: if (((filters[0] instanceof IntegerValue) && ((IntegerValue) filters[0])
170: .longValue() == 1)
171: || ((filters[0] instanceof PositionRange) && ((PositionRange) filters[0])
172: .isFirstPositionOnly())) {
173: firstElementPattern = true;
174: specialFilter = true;
175: numberOfFilters = 0;
176: filters = null;
177: }
178: }
179:
180: // see if it's an element pattern with a single positional predicate
181: // of [position()=last()]
182:
183: if (nodeTest.getPrimitiveType() == Type.ELEMENT
184: && numberOfFilters == 1
185: && filters[0] instanceof IsLastExpression
186: && ((IsLastExpression) filters[0]).getCondition()) {
187: lastElementPattern = true;
188: specialFilter = true;
189: numberOfFilters = 0;
190: filters = null;
191: }
192:
193: if (isPositional(th)) {
194: equivalentExpr = makeEquivalentExpression(env);
195: equivalentExpr = equivalentExpr.typeCheck(env,
196: contextItemType);
197: // the rewritten expression may use additional variables; must ensure there are enough slots for these
198: // (see test match55)
199: ((ExpressionContext) env).getStyleElement().allocateSlots(
200: equivalentExpr);
201: specialFilter = true;
202: }
203:
204: return this ;
205:
206: // TODO:PERF: identify subexpressions within a pattern predicate that could be promoted
207: // In the case of match patterns in template rules, these would have to become global variables.
208: }
209:
210: /**
211: * Get the dependencies of the pattern. The only possible dependency for a pattern is
212: * on local variables. This is analyzed in those patterns where local variables may appear.
213: */
214:
215: public int getDependencies() {
216: int dependencies = 0;
217: if (parentPattern != null) {
218: dependencies |= parentPattern.getDependencies();
219: }
220: if (ancestorPattern != null) {
221: dependencies |= ancestorPattern.getDependencies();
222: }
223: for (int i = 0; i < numberOfFilters; i++) {
224: dependencies |= filters[i].getDependencies();
225: }
226: // the only dependency that's interesting is a dependency on local variables
227: dependencies &= StaticProperty.DEPENDS_ON_LOCAL_VARIABLES;
228: return dependencies;
229: }
230:
231: /**
232: * Iterate over the subexpressions within this pattern
233: */
234:
235: public Iterator iterateSubExpressions() {
236: Iterator iter;
237: if (numberOfFilters == 0) {
238: iter = Collections.EMPTY_LIST.iterator();
239: } else {
240: iter = Arrays.asList(filters).subList(0, numberOfFilters)
241: .iterator();
242: }
243: if (variableBinding != null) {
244: Iterator[] pair = { iter, new MonoIterator(variableBinding) };
245: iter = new MultiIterator(pair);
246: }
247: if (parentPattern != null) {
248: Iterator[] pair = { iter,
249: parentPattern.iterateSubExpressions() };
250: iter = new MultiIterator(pair);
251: }
252: if (ancestorPattern != null) {
253: Iterator[] pair = { iter,
254: ancestorPattern.iterateSubExpressions() };
255: iter = new MultiIterator(pair);
256: }
257: return iter;
258: }
259:
260: /**
261: * Offer promotion for subexpressions within this pattern. The offer will be accepted if the subexpression
262: * is not dependent on the factors (e.g. the context item) identified in the PromotionOffer.
263: * By default the offer is not accepted - this is appropriate in the case of simple expressions
264: * such as constant values and variable references where promotion would give no performance
265: * advantage. This method is always called at compile time.
266: * <p/>
267: * <p>Unlike the corresponding method on {@link net.sf.saxon.expr.Expression}, this method does not return anything:
268: * it can make internal changes to the pattern, but cannot return a different pattern. Only certain
269: * kinds of promotion are applicable within a pattern: specifically, promotions affecting local
270: * variable references within the pattern.
271: *
272: * @param offer details of the offer, for example the offer to move
273: * expressions that don't depend on the context to an outer level in
274: * the containing expression
275: * @throws net.sf.saxon.trans.XPathException
276: * if any error is detected
277: */
278:
279: public void promote(PromotionOffer offer) throws XPathException {
280:
281: if (parentPattern != null) {
282: parentPattern.promote(offer);
283: }
284: if (ancestorPattern != null) {
285: ancestorPattern.promote(offer);
286: }
287: for (int i = 0; i < numberOfFilters; i++) {
288: filters[i] = filters[i].promote(offer);
289: }
290: }
291:
292: /**
293: * For a positional pattern, make an equivalent nodeset expression to evaluate the filters
294: */
295:
296: private ComputedExpression makeEquivalentExpression(
297: StaticContext env) throws XPathException {
298: byte axis = (nodeTest.getPrimitiveType() == Type.ATTRIBUTE ? Axis.ATTRIBUTE
299: : Axis.CHILD);
300: ComputedExpression step = new AxisExpression(axis, nodeTest);
301: for (int n = 0; n < numberOfFilters; n++) {
302: step = new FilterExpression(step, filters[n], env);
303: }
304: PathExpression path = new PathExpression(
305: new ParentNodeExpression(), step);
306: path.setParentExpression(this );
307: return path;
308: // Note, the resulting expression is not required to deliver results in document order
309: }
310:
311: /**
312: * Determine whether the pattern matches a given node.
313: * @param node the node to be tested
314: * @return true if the pattern matches, else false
315: */
316:
317: public boolean matches(NodeInfo node, XPathContext context)
318: throws XPathException {
319: if (variableBinding != null) {
320: variableBinding.evaluateItem(context);
321: }
322: return internalMatches(node, context);
323: // matches() and internalMatches() differ in the way they handled the current() function.
324: // The variable holding the value of current() is initialized on entry to the top-level
325: // LocationPathPattern, but not on entry to its subordinate patterns.
326: }
327:
328: /**
329: * Test whether the pattern matches, but without changing the current() node
330: */
331:
332: protected boolean internalMatches(NodeInfo node,
333: XPathContext context) throws XPathException {
334: // System.err.println("Matching node type and fingerprint");
335: if (!nodeTest.matches(node)) {
336: return false;
337: }
338: if (parentPattern != null) {
339: //System.err.println("Testing parent pattern " + parentPattern + "(" + parentPattern.getClass() + ")");
340: NodeInfo par = node.getParent();
341: if (par == null)
342: return false;
343: if (!parentPattern.internalMatches(par, context)) {
344: return false;
345: }
346: }
347:
348: if (ancestorPattern != null) {
349: NodeInfo anc = node.getParent();
350: while (true) {
351: if (anc == null)
352: return false;
353: if (ancestorPattern.internalMatches(anc, context))
354: break;
355: anc = anc.getParent();
356: }
357: }
358:
359: if (specialFilter) {
360: if (firstElementPattern) {
361: SequenceIterator iter = node.iterateAxis(
362: Axis.PRECEDING_SIBLING, nodeTest);
363: return iter.next() == null;
364: }
365:
366: if (lastElementPattern) {
367: SequenceIterator iter = node.iterateAxis(
368: Axis.FOLLOWING_SIBLING, nodeTest);
369: return iter.next() == null;
370: }
371:
372: if (equivalentExpr != null) {
373:
374: // for a positional pattern, we do it the hard way: test whether the
375: // node is a member of the nodeset obtained by evaluating the
376: // equivalent expression
377:
378: // System.err.println("Testing positional pattern against node " + node.generateId());
379: XPathContext c2 = context.newMinorContext();
380: c2.setOriginatingConstructType(Location.PATTERN);
381: AxisIterator single = SingletonIterator
382: .makeIterator(node);
383: single.next();
384: c2.setCurrentIterator(single);
385: try {
386: SequenceIterator nsv = equivalentExpr.iterate(c2);
387: while (true) {
388: NodeInfo n = (NodeInfo) nsv.next();
389: if (n == null) {
390: return false;
391: }
392: if (n.isSameNodeInfo(node)) {
393: return true;
394: }
395: }
396: } catch (DynamicError e) {
397: DynamicError err = new DynamicError(
398: "An error occurred matching pattern {"
399: + toString() + "}: ", e);
400: err.setXPathContext(c2);
401: err.setErrorCode(e.getErrorCodeLocalPart());
402: err.setLocator(this );
403: c2.getController().recoverableError(err);
404: return false;
405: }
406: }
407: }
408:
409: if (filters != null) {
410: XPathContext c2 = context.newMinorContext();
411: c2.setOriginatingConstructType(Location.PATTERN);
412: AxisIterator iter = SingletonIterator.makeIterator(node);
413: iter.next();
414: c2.setCurrentIterator(iter);
415: // it's a non-positional filter, so we can handle each node separately
416:
417: for (int i = 0; i < numberOfFilters; i++) {
418: try {
419: if (!filters[i].effectiveBooleanValue(c2)) {
420: return false;
421: }
422: } catch (DynamicError e) {
423: DynamicError err = new DynamicError(
424: "An error occurred matching pattern {"
425: + toString() + "}: ", e);
426: err.setXPathContext(c2);
427: err.setErrorCode(e.getErrorCodeLocalPart());
428: err.setLocator(this );
429: c2.getController().recoverableError(err);
430: return false;
431: }
432: }
433: }
434:
435: return true;
436: }
437:
438: /**
439: * Determine the types of nodes to which this pattern applies. Used for optimisation.
440: * For patterns that match nodes of several types, return Node.NODE
441: * @return the type of node matched by this pattern. e.g. Node.ELEMENT or Node.TEXT
442: */
443:
444: public int getNodeKind() {
445: return nodeTest.getPrimitiveType();
446: }
447:
448: /**
449: * Determine the fingerprint of nodes to which this pattern applies.
450: * Used for optimisation.
451: * @return the fingerprint of nodes matched by this pattern.
452: */
453:
454: public int getFingerprint() {
455: return nodeTest.getFingerprint();
456: }
457:
458: /**
459: * Get a NodeTest that all the nodes matching this pattern must satisfy
460: */
461:
462: public NodeTest getNodeTest() {
463: if (refinedNodeTest != null) {
464: return refinedNodeTest;
465: } else {
466: return nodeTest;
467: }
468: }
469:
470: /**
471: * Determine if the pattern uses positional filters
472: * @return true if there is a numeric filter in the pattern, or one that uses the position()
473: * or last() functions
474: */
475:
476: private boolean isPositional(TypeHierarchy th) {
477: if (filters == null)
478: return false;
479: for (int i = 0; i < numberOfFilters; i++) {
480: int type = filters[i].getItemType(th).getPrimitiveType();
481: if (type == Type.DOUBLE || type == Type.DECIMAL
482: || type == Type.INTEGER || type == Type.FLOAT
483: || type == Type.ANY_ATOMIC)
484: return true;
485: if ((filters[i].getDependencies() & (StaticProperty.DEPENDS_ON_POSITION | StaticProperty.DEPENDS_ON_LAST)) != 0)
486: return true;
487: }
488: return false;
489: }
490:
491: /**
492: * If the pattern contains any calls on current(), this method is called to modify such calls
493: * to become variable references to a variable declared in a specially-allocated local variable
494: * @param let the expression that assigns the local variable. This returns a dummy result, and is executed
495: * just before evaluating the pattern, to get the value of the context item into the variable.
496: * @param offer A PromotionOffer used to process the expressions and change the call on current() into
497: * a variable reference
498: * @throws XPathException
499: */
500:
501: public void resolveCurrent(LetExpression let, PromotionOffer offer)
502: throws XPathException {
503: for (int i = 0; i < numberOfFilters; i++) {
504: filters[i] = filters[i].promote(offer);
505: }
506: if (parentPattern instanceof LocationPathPattern) {
507: ((LocationPathPattern) parentPattern).resolveCurrent(let,
508: offer);
509: }
510: if (ancestorPattern instanceof LocationPathPattern) {
511: ((LocationPathPattern) ancestorPattern).resolveCurrent(let,
512: offer);
513: }
514: variableBinding = let;
515: }
516: }
517:
518: //
519: // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
520: // you may not use this file except in compliance with the License. You may obtain a copy of the
521: // License at http://www.mozilla.org/MPL/
522: //
523: // Software distributed under the License is distributed on an "AS IS" basis,
524: // WITHOUT WARRANTY OF ANY KIND, either express or implied.
525: // See the License for the specific language governing rights and limitations under the License.
526: //
527: // The Original Code is: all this file.
528: //
529: // The Initial Developer of the Original Code is Michael H. Kay.
530: //
531: // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
532: //
533: // Contributor(s): none.
534: //
|