KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > net > sf > saxon > expr > 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 JavaDoc;
13 import java.util.Iterator JavaDoc;
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 JavaDoc 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 JavaDoc 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 JavaDoc 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
Popular Tags