FilterExpression


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