001: package net.sf.saxon.expr;
002:
003: import net.sf.saxon.functions.Last;
004: import net.sf.saxon.functions.SystemFunction;
005: import net.sf.saxon.om.*;
006: import net.sf.saxon.trans.StaticError;
007: import net.sf.saxon.trans.XPathException;
008: import net.sf.saxon.type.AnyItemType;
009: import net.sf.saxon.type.ItemType;
010: import net.sf.saxon.type.Type;
011: import net.sf.saxon.type.TypeHierarchy;
012: import net.sf.saxon.value.*;
013:
014: import java.io.PrintStream;
015: import java.util.Iterator;
016:
017: /**
018: * A FilterExpression contains a base expression and a filter predicate, which may be an
019: * integer expression (positional filter), or a boolean expression (qualifier)
020: */
021:
022: public final class FilterExpression extends ComputedExpression {
023:
024: private Expression start;
025: private Expression filter;
026: private int filterDependencies; // the aspects of the context on which the filter
027: // expression depends
028: private boolean filterIsPositional; // true if the value of the filter might depend on
029: // the context position
030: private boolean filterIsRange; // true if the filter is of the form [position() = (A to B)]
031: // where A and B are focus-independent
032: private int isIndexable = 0;
033:
034: /**
035: * Constructor
036: * @param start A node-set expression denoting the absolute or relative set of nodes from which the
037: * navigation path should start.
038: * @param filter An expression defining the filter predicate
039: */
040:
041: public FilterExpression(Expression start, Expression filter,
042: StaticContext env) throws StaticError {
043: this .start = start;
044: this .filter = filter;
045: adoptChildExpression(start);
046: adoptChildExpression(filter);
047:
048: if (env != null) {
049: try {
050: filterDependencies = filter.simplify(env)
051: .getDependencies();
052: } catch (XPathException e) {
053: throw e.makeStatic();
054: }
055: }
056:
057: // the reason we simplify the filter before checking its dependencies
058: // is to ensure that functions like name() are expanded to use the
059: // context node as an implicit argument
060: }
061:
062: /**
063: * Get the data type of the items returned
064: * @return an integer representing the data type
065: * @param th
066: */
067:
068: public ItemType getItemType(TypeHierarchy th) {
069: return start.getItemType(th);
070: }
071:
072: /**
073: * Get the underlying expression
074: * @return the expression being filtered
075: */
076:
077: public Expression getBaseExpression() {
078: return start;
079: }
080:
081: /**
082: * Get the filter expression
083: * @return the expression acting as the filter predicate
084: */
085:
086: public Expression getFilter() {
087: return filter;
088: }
089:
090: /**
091: * Determine if the filter is positional
092: * @return true if the value of the filter depends on the position of the item against
093: * which it is evaluated
094: * @param th the Type Hierarchy (for cached access to type information)
095: */
096:
097: public boolean isPositional(TypeHierarchy th) {
098: return isPositionalFilter(filter, th);
099: }
100:
101: public boolean isIndexable() {
102: return isIndexable != 0;
103: }
104:
105: /**
106: * Simplify an expression
107: * @return the simplified expression
108: * @throws XPathException if any failure occurs
109: */
110:
111: public Expression simplify(StaticContext env) throws XPathException {
112:
113: if (filterDependencies == 0) {
114: filterDependencies = filter.simplify(env).getDependencies();
115: }
116:
117: start = start.simplify(env);
118: filter = filter.simplify(env);
119:
120: // ignore the filter if the base expression is an empty sequence
121: if (start instanceof EmptySequence) {
122: return start;
123: }
124:
125: // check whether the filter is a constant true() or false()
126: if (filter instanceof Value
127: && !(filter instanceof NumericValue)) {
128: try {
129: if (filter.effectiveBooleanValue(null)) {
130: return start;
131: } else {
132: return EmptySequence.getInstance();
133: }
134: } catch (XPathException e) {
135: throw new StaticError(e);
136: }
137: }
138:
139: // check whether the filter is [last()] (note, position()=last() is handled elsewhere)
140:
141: if (filter instanceof Last) {
142: filter = new IsLastExpression(true);
143: }
144:
145: return this ;
146:
147: }
148:
149: /**
150: * Type-check the expression
151: * @param env the static context
152: * @return the expression after type-checking (potentially modified to add run-time
153: * checks and/or conversions)
154: */
155:
156: public Expression typeCheck(StaticContext env,
157: ItemType contextItemType) throws XPathException {
158:
159: final TypeHierarchy th = env.getNamePool().getTypeHierarchy();
160: start = start.typeCheck(env, contextItemType);
161: filter = filter.typeCheck(env, start.getItemType(th));
162:
163: // The filter expression usually doesn't need to be sorted
164:
165: filter = ExpressionTool.unsortedIfHomogeneous(env
166: .getConfiguration().getOptimizer(), filter, false);
167:
168: // detect head expressions (E[1]) and tail expressions (E[position()!=1])
169: // and treat them specially
170:
171: if (filter instanceof IntegerValue) {
172: if (((IntegerValue) filter).longValue() == 1) {
173: return new FirstItemExpression(start);
174: }
175: }
176:
177: if (filter instanceof PositionRange) {
178: PositionRange range = (PositionRange) filter;
179: if (range.isFirstPositionOnly()) {
180: return new FirstItemExpression(start);
181: }
182: TailExpression tail = range.makeTailExpression(start);
183: if (tail != null) {
184: return tail;
185: }
186: }
187:
188: // determine whether the filter might depend on position
189: filterIsPositional = isPositionalFilter(filter, th);
190:
191: return this ;
192: }
193:
194: /**
195: * Perform optimisation of an expression and its subexpressions.
196: * <p/>
197: * <p>This method is called after all references to functions and variables have been resolved
198: * to the declaration of the function or variable, and after all type checking has been done.</p>
199: *
200: * @param opt the optimizer in use. This provides access to supporting functions; it also allows
201: * different optimization strategies to be used in different circumstances.
202: * @param env the static context of the expression
203: * @param contextItemType the static type of "." at the point where this expression is invoked.
204: * The parameter is set to null if it is known statically that the context item will be undefined.
205: * If the type of the context item is not known statically, the argument is set to
206: * {@link net.sf.saxon.type.Type#ITEM_TYPE}
207: * @return the original expression, rewritten if appropriate to optimize execution
208: * @throws net.sf.saxon.trans.StaticError if an error is discovered during this phase
209: * (typically a type error)
210: */
211:
212: public Expression optimize(Optimizer opt, StaticContext env,
213: ItemType contextItemType) throws XPathException {
214:
215: final TypeHierarchy th = env.getNamePool().getTypeHierarchy();
216: start = start.optimize(opt, env, contextItemType);
217: filter = filter.optimize(opt, env, start.getItemType(th));
218:
219: // The filter expression usually doesn't need to be sorted
220:
221: filter = ExpressionTool.unsortedIfHomogeneous(opt, filter,
222: false);
223:
224: // detect head expressions (E[1]) and tail expressions (E[position()!=1])
225: // and treat them specially
226:
227: if (filter instanceof IntegerValue) {
228: if (((IntegerValue) filter).longValue() == 1) {
229: return new FirstItemExpression(start);
230: }
231: }
232:
233: // the filter expression may have been reduced to a constant boolean by previous optimizations
234:
235: if (filter instanceof BooleanValue) {
236: if (((BooleanValue) filter).getBooleanValue()) {
237: return start;
238: } else {
239: return EmptySequence.getInstance();
240: }
241: }
242:
243: if (filter instanceof PositionRange) {
244: PositionRange range = (PositionRange) filter;
245: if (range.isFirstPositionOnly()) {
246: return new FirstItemExpression(start);
247: }
248: TailExpression tail = range.makeTailExpression(start);
249: if (tail != null) {
250: return tail;
251: }
252: }
253:
254: // determine whether the filter might depend on position
255: filterIsPositional = isPositionalFilter(filter, th);
256:
257: // determine whether the filter is indexable
258: if (filterIsPositional) {
259: isIndexable = 0;
260: } else {
261: isIndexable = opt.isIndexableFilter(filter);
262: }
263:
264: // if the filter is positional, try changing f[a and b] to f[a][b] to increase
265: // the chances of finishing early.
266:
267: if (filterIsPositional && filter instanceof BooleanExpression
268: && ((BooleanExpression) filter).operator == Token.AND) {
269: BooleanExpression bf = (BooleanExpression) filter;
270: if (isExplicitlyPositional(bf.operand0)
271: && !isExplicitlyPositional(bf.operand1)) {
272: Expression p0 = forceToBoolean(bf.operand0, env
273: .getNamePool());
274: Expression p1 = forceToBoolean(bf.operand1, env
275: .getNamePool());
276: FilterExpression f1 = new FilterExpression(start, p0,
277: env);
278: FilterExpression f2 = new FilterExpression(f1, p1, env);
279: //System.err.println("Simplified to: ");
280: //f2.display(10);
281: return f2.optimize(opt, env, contextItemType);
282: }
283: if (isExplicitlyPositional(bf.operand1)
284: && !isExplicitlyPositional(bf.operand0)) {
285: Expression p0 = forceToBoolean(bf.operand0, env
286: .getNamePool());
287: Expression p1 = forceToBoolean(bf.operand1, env
288: .getNamePool());
289: FilterExpression f1 = new FilterExpression(start, p1,
290: env);
291: FilterExpression f2 = new FilterExpression(f1, p0, env);
292: //System.err.println("Simplified to: ");
293: //f2.display(10);
294: return f2.optimize(opt, env, contextItemType);
295: }
296: }
297:
298: filterIsRange = filter instanceof PositionRange
299: && !((PositionRange) filter).hasFocusDependentRange();
300:
301: // If any subexpressions within the filter are not dependent on the focus,
302: // promote them: this causes them to be evaluated once, outside the filter
303: // expression. Note: we do this even if the filter is numeric, because it ensures that
304: // the subscript is pre-evaluated, allowing direct indexing into the sequence.
305:
306: PromotionOffer offer = new PromotionOffer(opt);
307: offer.action = PromotionOffer.FOCUS_INDEPENDENT;
308: offer.promoteDocumentDependent = (start.getSpecialProperties() & StaticProperty.CONTEXT_DOCUMENT_NODESET) != 0;
309: offer.containingExpression = this ;
310: filter = doPromotion(filter, offer);
311:
312: if (offer.containingExpression instanceof LetExpression) {
313: offer.containingExpression = offer.containingExpression
314: .optimize(opt, env, contextItemType);
315: }
316:
317: return offer.containingExpression;
318: }
319:
320: /**
321: * Construct an expression that obtains the effective boolean value of a given expression,
322: * by wrapping it in a call of the boolean() function
323: */
324:
325: private static Expression forceToBoolean(Expression in,
326: NamePool namePool) {
327: final TypeHierarchy th = namePool.getTypeHierarchy();
328: if (in.getItemType(th).getPrimitiveType() == Type.BOOLEAN) {
329: return in;
330: }
331: Expression[] args = { in };
332: FunctionCall fn = SystemFunction.makeSystemFunction("boolean",
333: 1, namePool);
334: fn.setArguments(args);
335: return fn;
336: }
337:
338: /**
339: * Promote this expression if possible
340: * @param offer details of the promotion that is possible
341: * @return the promoted expression (or the original expression, unchanged)
342: */
343:
344: public Expression promote(PromotionOffer offer)
345: throws XPathException {
346: Expression exp = offer.accept(this );
347: if (exp != null) {
348: return exp;
349: } else {
350: if (!(offer.action == PromotionOffer.UNORDERED && filterIsPositional)) {
351: start = doPromotion(start, offer);
352: }
353: if (offer.action == PromotionOffer.INLINE_VARIABLE_REFERENCES
354: || offer.action == PromotionOffer.REPLACE_CURRENT) {
355: // Don't pass on other requests. We could pass them on, but only after augmenting
356: // them to say we are interested in subexpressions that don't depend on either the
357: // outer context or the inner context.
358: filter = doPromotion(filter, offer);
359: }
360: return this ;
361: }
362: }
363:
364: /**
365: * Determine whether an expression, when used as a filter, is positional
366: */
367:
368: private static boolean isPositionalFilter(Expression exp,
369: TypeHierarchy th) {
370: ItemType type = exp.getItemType(th);
371: return (type == Type.ANY_ATOMIC_TYPE
372: || type instanceof AnyItemType
373: || type == Type.INTEGER_TYPE
374: || type == Type.NUMBER_TYPE
375: || th.isSubType(type, Type.NUMBER_TYPE) || isExplicitlyPositional(exp));
376: }
377:
378: /**
379: * Determine whether an expression, when used as a filter, has an explicit dependency on position() or last()
380: */
381:
382: private static boolean isExplicitlyPositional(Expression exp) {
383: return (exp.getDependencies() & (StaticProperty.DEPENDS_ON_POSITION | StaticProperty.DEPENDS_ON_LAST)) != 0;
384: }
385:
386: /**
387: * Get the immediate subexpressions of this expression
388: * @return the subexpressions, as an array
389: */
390:
391: public Iterator iterateSubExpressions() {
392: return new PairIterator(start, filter);
393: }
394:
395: /**
396: * Get the static cardinality of this expression
397: * @return the cardinality. The method attempts to determine the case where the
398: * filter predicate is guaranteed to select at most one item from the sequence being filtered
399: */
400:
401: public int computeCardinality() {
402: if (filter instanceof NumericValue) {
403: return StaticProperty.ALLOWS_ZERO_OR_ONE;
404: }
405: if (!Cardinality.allowsMany(start.getCardinality())) {
406: return StaticProperty.ALLOWS_ZERO_OR_ONE;
407: }
408: if (filter instanceof PositionRange) {
409: PositionRange p = (PositionRange) filter;
410: if (p.matchesAtMostOneItem()) {
411: return StaticProperty.ALLOWS_ZERO_OR_ONE;
412: }
413: }
414: if (filter instanceof IsLastExpression
415: && ((IsLastExpression) filter).getCondition()) {
416: return StaticProperty.ALLOWS_ZERO_OR_ONE;
417: }
418: int sc = start.getCardinality();
419: switch (sc) {
420: case StaticProperty.ALLOWS_ONE_OR_MORE:
421: return StaticProperty.ALLOWS_ZERO_OR_MORE;
422: case StaticProperty.EXACTLY_ONE:
423: return StaticProperty.ALLOWS_ZERO_OR_ONE;
424: default:
425: return sc;
426: }
427: }
428:
429: /**
430: * Get the static properties of this expression (other than its type). The result is
431: * bit-significant. These properties are used for optimizations. In general, if
432: * property bit is set, it is true, but if it is unset, the value is unknown.
433: * @return the static properties of the expression, as a bit-significant value
434: */
435:
436: public int computeSpecialProperties() {
437: return start.getSpecialProperties();
438: }
439:
440: /**
441: * Is this expression the same as another expression?
442: * @param other the expression to be compared with this one
443: * @return true if the two expressions are statically equivalent
444: */
445:
446: public boolean equals(Object other) {
447: if (other instanceof FilterExpression) {
448: FilterExpression f = (FilterExpression) other;
449: return (start.equals(f.start) && filter.equals(f.filter));
450: }
451: return false;
452: }
453:
454: /**
455: * get HashCode for comparing two expressions
456: * @return the hash code
457: */
458:
459: public int hashCode() {
460: return "FilterExpression".hashCode() + start.hashCode()
461: + filter.hashCode();
462: }
463:
464: /**
465: * Iterate over the results, returning them in the correct order
466: * @param context the dynamic context for the evaluation
467: * @return an iterator over the expression results
468: * @throws XPathException if any dynamic error occurs
469: */
470:
471: public SequenceIterator iterate(XPathContext context)
472: throws XPathException {
473:
474: // Fast path where both operands are constants, or simple variable references
475:
476: Expression startExp = start;
477: ValueRepresentation startValue = null;
478: if (startExp instanceof ValueRepresentation) {
479: startValue = (ValueRepresentation) startExp;
480: } else if (startExp instanceof VariableReference) {
481: startValue = ((VariableReference) startExp)
482: .evaluateVariable(context);
483: }
484:
485: if (startValue instanceof Value) {
486: startExp = (Value) startValue;
487: }
488:
489: if (startValue instanceof EmptySequence) {
490: return EmptyIterator.getInstance();
491: }
492:
493: ValueRepresentation filterValue = null;
494: if (filter instanceof ValueRepresentation) {
495: filterValue = (ValueRepresentation) filter;
496: } else if (filter instanceof VariableReference) {
497: filterValue = ((VariableReference) filter)
498: .evaluateVariable(context);
499: }
500:
501: // Handle the case where the filter is a value. Because of earlier static rewriting, this covers
502: // all cases where the filter expression is independent of the context, that is, where the
503: // value of the filter expression is the same for all items in the sequence being filtered.
504:
505: if (filterValue != null) {
506: if (filterValue instanceof Value) {
507: filterValue = ((Value) filterValue).reduce();
508: }
509: if (filterValue instanceof NumericValue) {
510: // Filter is a constant number
511: if (((NumericValue) filterValue).isWholeNumber()) {
512: int pos = (int) (((NumericValue) filterValue)
513: .longValue());
514: if (startValue != null) {
515: if (startValue instanceof Value) {
516: // if sequence is a value, use direct indexing
517: return SingletonIterator
518: .makeIterator(((Value) startValue)
519: .itemAt(pos - 1));
520: } else if (startValue instanceof NodeInfo) {
521: // sequence to be filtered is a single node
522: if (pos == 1) {
523: return SingletonIterator
524: .makeIterator((NodeInfo) startValue);
525: } else {
526: return EmptyIterator.getInstance();
527: }
528: }
529: }
530: if (pos >= 1) {
531: SequenceIterator base = startExp
532: .iterate(context);
533: return PositionIterator.make(base, pos, pos);
534: } else {
535: // index is less than one, no items will be selected
536: return EmptyIterator.getInstance();
537: }
538: } else {
539: // a non-integer value will never be equal to position()
540: return EmptyIterator.getInstance();
541: }
542: } else if (filterValue instanceof Value) {
543: // Filter is a constant that we can treat as boolean
544:
545: if (((Value) filterValue)
546: .effectiveBooleanValue(context)) {
547: return start.iterate(context);
548: } else {
549: return EmptyIterator.getInstance();
550: }
551: } else if (filterValue instanceof NodeInfo) {
552: return start.iterate(context);
553: }
554: }
555:
556: // see if the sequence to be filtered is an indexed value; if so, use the index
557:
558: if (isIndexable != 0 && startValue instanceof Closure
559: && ((Closure) startValue).isIndexable()) {
560: SequenceIterator indexedResult = context.getConfiguration()
561: .getOptimizer().tryIndexedFilter(startValue,
562: filter, isIndexable, context);
563: if (indexedResult != null) {
564: return indexedResult;
565: }
566: }
567:
568: // get an iterator over the base nodes
569:
570: SequenceIterator base = startExp.iterate(context);
571:
572: // quick exit for an empty sequence
573:
574: if (base instanceof EmptyIterator) {
575: return base;
576: }
577:
578: // Test whether the filter is a position range, e.g. [position()>$x]
579: // TODO: handle all such cases with a TailExpression
580:
581: if (filterIsRange) {
582: PositionRange pr = (PositionRange) filter;
583: // System.err.println("Using PositionIterator requireSort=" + requireSort + " isReverse=" + isReverseAxisFilter);
584: return pr.makePositionIterator(base, context);
585:
586: } else if (filterIsPositional) {
587: return new FilterIterator(base, filter, context);
588:
589: } else {
590: return new FilterIterator.NonNumeric(base, filter, context);
591: }
592:
593: }
594:
595: /**
596: * Determine which aspects of the context the expression depends on. The result is
597: * a bitwise-or'ed value composed from constants such as XPathContext.VARIABLES and
598: * XPathContext.CURRENT_NODE
599: * @return the dependencies
600: */
601:
602: public int computeDependencies() {
603: // not all dependencies in the filter expression matter, because the context node,
604: // position, and size are not dependent on the outer context.
605: return (start.getDependencies() | (filterDependencies & (StaticProperty.DEPENDS_ON_XSLT_CONTEXT
606: | StaticProperty.DEPENDS_ON_LOCAL_VARIABLES | StaticProperty.DEPENDS_ON_USER_FUNCTIONS)));
607: }
608:
609: /**
610: * Diagnostic print of expression structure
611: * @param level the indentation level
612: * @param out
613: */
614:
615: public void display(int level, NamePool pool, PrintStream out) {
616: out.println(ExpressionTool.indent(level) + "filter []");
617: start.display(level + 1, pool, out);
618: filter.display(level + 1, pool, out);
619: }
620:
621: }
622:
623: //
624: // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
625: // you may not use this file except in compliance with the License. You may obtain a copy of the
626: // License at http://www.mozilla.org/MPL/
627: //
628: // Software distributed under the License is distributed on an "AS IS" basis,
629: // WITHOUT WARRANTY OF ANY KIND, either express or implied.
630: // See the License for the specific language governing rights and limitations under the License.
631: //
632: // The Original Code is: all this file.
633: //
634: // The Initial Developer of the Original Code is Michael H. Kay.
635: //
636: // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
637: //
638: // Contributor(s): none.
639: //
|