ForExpression


1   package net.sf.saxon.expr;
2   import net.sf.saxon.om.Item;
3   import net.sf.saxon.om.NamePool;
4   import net.sf.saxon.om.SequenceIterator;
5   import net.sf.saxon.om.ValueRepresentation;
6   import net.sf.saxon.trace.Location;
7   import net.sf.saxon.trans.XPathException;
8   import net.sf.saxon.type.ItemType;
9   import net.sf.saxon.type.SchemaType;
10  import net.sf.saxon.value.Cardinality;
11  import net.sf.saxon.value.EmptySequence;
12  import net.sf.saxon.value.IntegerValue;
13  import net.sf.saxon.value.SequenceType;
14  import net.sf.saxon.functions.SystemFunction;
15  
16  import java.io.PrintStream  ;
17  import java.util.ArrayList  ;
18  import java.util.List  ;
19  
20  /**
21  * A ForExpression maps an expression over a sequence.
22  * This version works with range variables, it doesn't change the context information
23  */
24  
25  public class ForExpression extends Assignation {
26  
27      private transient RangeVariableDeclaration positionVariable = null;
28      private PositionBinding positionBinding = null;
29  
30  
31      public ForExpression() {
32      }
33  
34      /**
35       * Set the reference to the position variable (XQuery only)
36       */
37  
38      public void setPositionVariable (RangeVariableDeclaration decl) {
39          positionVariable = decl;
40          if (decl != null) {
41              positionBinding = new PositionBinding();
42          }
43      }
44  
45      public void setAction(Expression action) {
46          super.setAction(action);
47          if (positionVariable != null) {
48              positionVariable.fixupReferences(positionBinding);
49          }
50      }
51  
52      /**
53      * Set the slot number for the range variable
54      */
55  
56      public void setSlotNumber(int nr) {
57          super.setSlotNumber(nr);
58          if (positionBinding != null) {
59              positionBinding.setSlotNumber(nr+1);
60          }
61      }
62  
63      /**
64       * Get the number of slots required. Normally 1, except for a FOR expression with an AT clause, where it is 2.
65       */
66  
67      public int getRequiredSlots() {
68          return (positionBinding == null ? 1 : 2);
69      }
70  
71      /**
72      * Type-check the expression
73      */
74  
75      public Expression typeCheck(StaticContext env, ItemType contextItemType) throws XPathException {
76  
77          // The order of events is critical here. First we ensure that the type of the
78          // sequence expression is established. This is used to establish the type of the variable,
79          // which in turn is required when type-checking the action part.
80  
81          sequence = sequence.typeCheck(env, contextItemType);
82          if (sequence instanceof EmptySequence) {
83              return EmptySequence.getInstance();
84          }
85  
86          if (declaration != null) {
87              // if declaration is null, we've already done the type checking in a previous pass
88              SequenceType decl = declaration.getRequiredType();
89              SequenceType sequenceType = SequenceType.makeSequenceType(
90                      decl.getPrimaryType(), StaticProperty.ALLOWS_ZERO_OR_MORE);
91              RoleLocator role = new RoleLocator(RoleLocator.VARIABLE, new Integer  (nameCode), 0, env.getNamePool());
92              role.setSourceLocator(this);
93              sequence = TypeChecker.strictTypeCheck(
94                                      sequence, sequenceType, role, env);
95              ItemType actualItemType = sequence.getItemType();
96              declaration.refineTypeInformation(actualItemType,
97                      StaticProperty.EXACTLY_ONE,
98                      null,
99                      sequence.getSpecialProperties());
100         }
101 
102         action = action.typeCheck(env, contextItemType);
103         if (action instanceof EmptySequence) {
104             return EmptySequence.getInstance();
105         }
106 
107         return this;
108     }
109 
110     /**
111     * Optimize the expression
112     */
113 
114     public Expression optimize(Optimizer opt, StaticContext env, ItemType contextItemType) throws XPathException {
115 
116 
117 
118         // Try to promote any WHERE clause appearing within the FOR expression
119 
120         Expression p = promoteWhereClause(positionBinding);
121         if (p != null) {
122             return p.optimize(opt, env, contextItemType);
123         }
124 
125         // See if there is a simple "where" condition that can be turned into a predicate
126 
127         Expression pred = convertWhereToPredicate(opt, env, contextItemType);
128         if (pred != null && pred != this) {
129             return pred.optimize(opt, env, contextItemType);
130         }
131 
132         int tries = 0;
133         while (tries++ < 5) {
134             Expression seq2 = sequence.optimize(opt, env, contextItemType);
135             if (seq2 == sequence) {
136                 break;
137             }
138             sequence = seq2;
139             adoptChildExpression(sequence);
140             resetStaticProperties();
141         }
142         if (sequence instanceof EmptySequence) {
143             return EmptySequence.getInstance();
144         }
145 
146         tries = 0;
147         while (tries++ < 5) {
148             Expression act2 = action.optimize(opt, env, contextItemType);
149             if (act2 == action) {
150                 break;
151             }
152             action = act2;
153             adoptChildExpression(action);
154             resetStaticProperties();
155         }
156         if (action instanceof EmptySequence) {
157             return EmptySequence.getInstance();
158         }
159 
160         Expression e2 = extractLoopInvariants(opt, env, contextItemType);
161         if (e2 != null && e2 != this) {
162             return e2.optimize(opt, env, contextItemType);
163         }
164 
165         // Simplify an expression of the form "for $b in a/b/c return $b/d".
166         // (XQuery users seem to write these a lot!)
167 
168         if (declaration != null && positionVariable==null &&
169                 sequence instanceof PathExpression && action instanceof PathExpression) {
170             int count = declaration.getReferenceCount(this);
171             PathExpression path2 = (PathExpression)action;
172             Expression s2 = path2.getStartExpression();
173             if (count == 1 && s2 instanceof VariableReference && ((VariableReference)s2).getBinding() == this) {
174                 PathExpression newPath = new PathExpression(sequence, path2.getStepExpression());
175                 return newPath.simplify(env).typeCheck(env, contextItemType).optimize(opt, env, contextItemType);
176             }
177         }
178 
179         // Simplify an expression of the form "for $x in EXPR return $x". These sometimes
180         // arise as a result of previous optimization steps.
181 
182         if (action instanceof VariableReference && ((VariableReference)action).getBinding() == this) {
183             return sequence;
184         }
185 
186         declaration = null;     // let the garbage collector take it
187 
188 
189 
190         return this;
191     }
192 
193 
194     /**
195      * Extract subexpressions in the action part that don't depend on the range variable
196      */
197 
198     private Expression extractLoopInvariants(Optimizer opt, StaticContext env, ItemType contextItemType) throws XPathException {
199         // Extract subexpressions that don't depend on the range variable.
200         // We don't do this if there is a position variable. Ideally we would
201         // extract subexpressions so long as they don't depend on either variable,
202         // but we don't have the machinery to do that yet.
203         // TODO: add this optimisation: we now have the mechanism in ExpressionTool.dependsOnVariable()
204         // If a subexpression is (or might be) creative, this is, if it creates new nodes, we don't
205         // extract it from the loop, but we do extract its non-creative subexpressions
206 
207         if (positionVariable == null) {
208             PromotionOffer offer = new PromotionOffer(opt);
209             offer.containingExpression = this;
210             offer.action = PromotionOffer.RANGE_INDEPENDENT;
211             Binding[] bindingList = {this};
212             offer.bindingList = bindingList;
213             Container container = getParentExpression();
214             action = doPromotion(action, offer);
215             if (offer.containingExpression instanceof LetExpression) {
216                 // a subexpression has been promoted
217                 ((ComputedExpression)offer.containingExpression).setParentExpression(container);
218                 // try again: there may be further subexpressions to promote
219                 offer.containingExpression = offer.containingExpression.simplify(env).typeCheck(env, contextItemType);
220             }
221             return offer.containingExpression;
222         }
223         return null;
224 
225     }
226 
227     /**
228      * Convert where clause, if possible, to a predicate. Returns the converted expression if modified,
229      * or null otherwise
230      */
231 
232     public Expression convertWhereToPredicate(Optimizer opt, StaticContext env, ItemType contextItemType) throws XPathException {
233         if (action instanceof IfExpression && ((IfExpression)action).getElseExpression() instanceof EmptySequence) {
234             Expression head = null;
235             Expression selection = sequence;
236             if (sequence instanceof PathExpression && ((PathExpression)sequence).isAbsolute()) {
237                 head = ((PathExpression)sequence).getFirstStep();
238                 selection = ((PathExpression)sequence).getRemainingSteps();
239             }
240 
241             boolean changed = false;
242             IfExpression condAction = (IfExpression)action;
243             List   list = new ArrayList  (4);
244             BooleanExpression.listAndComponents(condAction.getCondition(), list);
245             for (int t=list.size()-1; t>=0; t--) {
246                 // Process each term in the where clause independently
247                 Expression term = (Expression)list.get(t);
248 
249                 if (term instanceof ValueComparison) {
250                     ValueComparison comp = (ValueComparison)term;
251                     Expression[] operands = comp.getOperands();
252                     for (int op=0; op<2; op++) {
253 
254                         // If the where clause is a simple test on the position variable, for example
255                         //    for $x at $p in EXPR where $p = 5 return A
256                         // then absorb the where condition into a predicate, rewriting it as
257                         //    for $x in EXPR[position() = 5] return A
258                         // This takes advantage of the optimizations applied to positional filter expressions
259                         // Only do this if the sequence expression has not yet been changed, because
260                         // the position in a predicate after the first is different.
261 
262                         if (positionVariable != null && positionVariable.getReferenceList().size() == 1 && !changed) {
263                             if (operands[op] instanceof VariableReference &&
264                                     ((VariableReference)operands[op]).getBinding() == positionBinding &&
265                                     (operands[1-op].getDependencies() & StaticProperty.DEPENDS_ON_FOCUS) == 0) {
266                                 FunctionCall position =
267                                         SystemFunction.makeSystemFunction("position", 1, env.getNamePool());
268                                 position.setArguments(SimpleExpression.NO_ARGUMENTS);
269                                 Expression predicate;
270                                 if (op==0) {
271                                     predicate = new ValueComparison(position, comp.getOperator(), operands[1]);
272                                 } else {
273                                     predicate = new ValueComparison(operands[0], comp.getOperator(), position);
274                                 }
275                                 selection = new FilterExpression(selection, predicate, env);
276                                 //action = condAction.getThenExpression();
277                                 positionVariable = null;
278                                 positionBinding = null;
279                                 list.remove(t);
280                                 changed = true;
281                                 break;
282                                 //return simplify(env).typeCheck(env, contextItemType).optimize(opt, env, contextItemType);
283                             }
284                         }
285 
286                         // If the where clause is a simple test on the value of the range variable, or a path
287                         // expression starting with the range variable, then rewrite it as a predicate.
288                         // For example, rewrite
289                         //    for $x in EXPR where $x/a/b eq "z" return A
290                         // as
291                         //    for $x in EXPR[a/b eq "z"] return A
292 
293                         Binding[] thisVar = {this};
294                         if ( positionVariable == null &&
295                                 ExpressionTool.isVariableReplaceableByDot(term, thisVar) &&
296                                 (term.getDependencies() & StaticProperty.DEPENDS_ON_FOCUS) == 0 &&
297                                 ExpressionTool.dependsOnVariable(operands[op], thisVar) &&
298                                 !ExpressionTool.dependsOnVariable(operands[1-op], thisVar)) {
299                             PromotionOffer offer = new PromotionOffer(opt);
300                             offer.action = PromotionOffer.INLINE_VARIABLE_REFERENCES;
301                             offer.bindingList = thisVar;
302                             offer.containingExpression = new ContextItemExpression();
303                             Expression newOperand = operands[op].promote(offer);
304                             if (newOperand != null && offer.accepted) {
305                                 Expression predicate;
306                                 if (op==0) {
307                                     predicate = new ValueComparison(newOperand, comp.getOperator(), operands[1]);
308                                 } else {
309                                     predicate = new ValueComparison(operands[0], comp.getOperator(), newOperand);
310                                 }
311                                 predicate = predicate.typeCheck(env, sequence.getItemType());
312                                 selection = new FilterExpression(selection, predicate, env);
313                                 changed = true;
314                                 positionVariable = null;
315                                 positionBinding = null;
316                                 list.remove(t);
317                             }
318                         }
319                     }
320                 } else if (term instanceof GeneralComparison) {
321                     GeneralComparison comp = (GeneralComparison)term;
322                     Expression[] operands = comp.getOperands();
323                     for (int op=0; op<2; op++) {
324 
325                         // If the where clause is a simple test on the value of the range variable, or a path
326                         // expression starting with the range variable, then rewrite it as a predicate.
327                         // For example, rewrite
328                         //    for $x in EXPR where $x/a/b = "z" return A
329                         // as
330                         //    for $x in EXPR[a/b = "z"] return A
331 
332                         Binding[] thisVar = {this};
333                         if (positionVariable == null &&
334                                 ExpressionTool.isVariableReplaceableByDot(term, thisVar) &&
335                                 (term.getDependencies() & StaticProperty.DEPENDS_ON_FOCUS) == 0 &&
336                                 ExpressionTool.dependsOnVariable(operands[op], thisVar) &&
337                                 !ExpressionTool.dependsOnVariable(operands[1-op], thisVar)) {
338                             PromotionOffer offer = new PromotionOffer(opt);
339                             offer.action = PromotionOffer.INLINE_VARIABLE_REFERENCES;
340                             offer.bindingList = thisVar;
341                             offer.containingExpression = new ContextItemExpression();
342                             Expression newOperand = operands[op].promote(offer);
343                             if (newOperand != null && !ExpressionTool.dependsOnVariable(newOperand, thisVar)) {
344                                 if (newOperand instanceof ComputedExpression) {
345                                     ((ComputedExpression)newOperand).resetStaticProperties();
346                                 }
347                                 Expression predicate;
348                                 //newOperand = new Atomizer(newOperand, env.getConfiguration());
349                                 if (op==0) {
350                                     // todo: make GeneralComparisonSA where appropriate
351                                     predicate = new GeneralComparison(newOperand, comp.getOperator(), operands[1]);
352                                 } else {
353                                     predicate = new GeneralComparison(operands[0], comp.getOperator(), newOperand);
354                                 }
355                                 selection = new FilterExpression(selection, predicate, env);
356                                 resetStaticProperties();
357                                 //action = condAction.getThenExpression();
358                                 positionVariable = null;
359                                 positionBinding = null;
360                                 //return simplify(env).typeCheck(env, contextItemType).optimize(opt, env, contextItemType);
361                                 list.remove(t);
362                                 changed = true;
363                                 break;
364                             }
365                         }
366 
367 //                        Expression start = operands[op];
368 //                        Expression rest = new ContextItemExpression();
369 //                        Expression ostart = start;
370 //                        if (start instanceof Atomizer) {
371 //                            ostart = ((Atomizer)start).getBaseExpression();
372 //                        }
373 //                        if (ostart instanceof PathExpression) {
374 //                            rest = ((PathExpression)ostart).getRemainingSteps();
375 //                            ostart = ((PathExpression)ostart).getFirstStep();
376 //                        }
377 //                        Binding[] thisVar = {this};
378 //                        if (ostart instanceof VariableReference &&
379 //                                ((VariableReference)ostart).getBinding() == this &&
380 //                                positionVariable == null &&
381 //                                (operands[1-op].getDependencies() & StaticProperty.DEPENDS_ON_FOCUS) == 0 &&
382 //                                !ExpressionTool.dependsOnVariable(rest, thisVar) &&
383 //                                !ExpressionTool.dependsOnVariable(operands[1-op], thisVar)) {
384 //                            Expression predicate;
385 //                            rest = new Atomizer(rest, env.getConfiguration());
386 //                            if (op==0) {
387 //                                predicate = new GeneralComparison(rest, comp.getOperator(), operands[1]);
388 //                            } else {
389 //                                predicate = new GeneralComparison(operands[0], comp.getOperator(), rest);
390 //                            }
391 //                            selection = new FilterExpression(selection, predicate, env);
392 //                            //action = condAction.getThenExpression();
393 //                            positionVariable = null;
394 //                            positionBinding = null;
395 //                            //return simplify(env).typeCheck(env, contextItemType).optimize(opt, env, contextItemType);
396 //                            list.remove(t);
397 //                            changed = true;
398 //                            break;
399 //                        }
400                     }
401                 }
402             }
403             if (changed) {
404                 if (list.isEmpty()) {
405                     action = condAction.getThenExpression();
406                     adoptChildExpression(action);
407                 } else {
408                     Expression term = (Expression)list.get(0);
409                     for (int t=1; t<list.size(); t++) {
410                         term = new BooleanExpression(term, Token.AND, (Expression)list.get(t));
411                     }
412                     condAction.setCondition(term);
413                 }
414                 if (head == null) {
415                     sequence = selection;
416                 } else {
417                     PathExpression path = new PathExpression(head, selection);
418                     path.setParentExpression(this);
419                     Expression k = opt.convertPathExpressionToKey(path, env);
420                     if (k == null) {
421                         sequence = path;
422                     } else {
423                         sequence = k;
424                     }
425                     sequence = sequence.simplify(env).typeCheck(env, contextItemType).optimize(opt, env, contextItemType);
426                     adoptChildExpression(sequence);
427                 }
428                 return this;
429             }
430         }
431         return null;
432     }
433 
434     /**
435      * Mark tail function calls: only possible if the for expression iterates zero or one times.
436      * (This arises in XSLT/XPath, which does not have a LET expression, so FOR gets used instead)
437      */
438 
439     public boolean markTailFunctionCalls() {
440         if (!Cardinality.allowsMany(sequence.getCardinality())) {
441             return ExpressionTool.markTailFunctionCalls(action);
442         } else {
443             return false;
444         }
445     }
446 
447     /**
448      * Extend an array of variable bindings to include the binding(s) defined in this expression
449      */
450 
451     protected Binding[] extendBindingList(Binding[] in) {
452         if (positionBinding == null) {
453             return super.extendBindingList(in);
454         }
455         Binding[] newBindingList = new Binding[in.length+2];
456         System.arraycopy(in, 0, newBindingList, 0, in.length);
457         newBindingList[in.length] = this;
458         newBindingList[in.length+1] = positionBinding;
459         return newBindingList;
460     }
461 
462     /**
463      * An implementation of Expression must provide at least one of the methods evaluateItem(), iterate(), or process().
464      * This method indicates which of these methods is provided. This implementation provides both iterate() and
465      * process() methods natively.
466      */
467 
468     public int getImplementationMethod() {
469         return ITERATE_METHOD | PROCESS_METHOD;
470     }
471 
472     /**
473      * Check that any elements and attributes constructed or returned by this expression are acceptable
474      * in the content model of a given complex type. It's always OK to say yes, since the check will be
475      * repeated at run-time. The process of checking element and attribute constructors against the content
476      * model of a complex type also registers the type of content expected of those constructors, so the
477      * static validation can continue recursively.
478      */
479 
480     public void checkPermittedContents(SchemaType parentType, StaticContext env, boolean whole) throws XPathException {
481         action.checkPermittedContents(parentType, env, false);
482     }
483 
484     /**
485     * Iterate over the sequence of values
486     */
487 
488     public SequenceIterator iterate(XPathContext context) throws XPathException {
489 
490         // First create an iteration of the base sequence.
491 
492         // Then create a MappingIterator which applies a mapping function to each
493         // item in the base sequence. The mapping function is essentially the "return"
494         // expression, wrapped in a MappingAction object that is responsible also for
495         // setting the range variable at each step.
496 
497         SequenceIterator base = sequence.iterate(context);
498 
499         MappingFunction map = new MappingAction(context, slotNumber, positionBinding, action);
500         return new MappingIterator(base, map, null);
501     }
502 
503     /**
504      * Process this expression as an instruction, writing results to the current
505      * outputter
506      */
507 
508     public void process(XPathContext context) throws XPathException {
509         SequenceIterator iter = sequence.iterate(context);
510         int position = 1;
511         while (true) {
512             Item item = iter.next();
513             if (item == null) break;
514             context.setLocalVariable(slotNumber, item);
515             if (positionBinding != null) {
516                 positionBinding.setPosition(position++, context);
517             }
518             action.process(context);
519         }
520     }
521 
522     /**
523     * Determine the data type of the items returned by the expression, if possible
524     * @return one of the values Type.STRING, Type.BOOLEAN, Type.NUMBER, Type.NODE,
525     * or Type.ITEM (meaning not known in advance)
526     */
527 
528     public ItemType getItemType() {
529         return action.getItemType();
530     }
531 
532     /**
533     * Determine the static cardinality of the expression
534     */
535 
536     public int computeCardinality() {
537         int c1 = sequence.getCardinality();
538         int c2 = action.getCardinality();
539         return Cardinality.multiply(c1, c2);
540     }
541 
542     /**
543     * Diagnostic print of expression structure
544     */
545 
546     public void display(int level, NamePool pool, PrintStream   out) {
547         out.println(ExpressionTool.indent(level) +
548                 "for $" + getVariableName(pool) +
549                 (positionVariable == null ? "" : " at $?") +
550                 " in");
551         sequence.display(level+1, pool, out);
552         out.println(ExpressionTool.indent(level) + "return");
553         action.display(level+1, pool, out);
554     }
555 
556     /**
557      * The MappingAction represents the action to be taken for each item in the
558      * source sequence. It acts as the MappingFunction for the mapping iterator, and
559      * also as the Binding of the position variable (at $n) in XQuery, if used.
560      */
561 
562     private static class MappingAction implements MappingFunction {
563 
564         private XPathContext context;
565         private int slotNumber;
566         private Expression action;
567         private PositionBinding positionBinding;
568         private int position = 1;
569 
570         public MappingAction(XPathContext context,
571                                 int slotNumber,
572                                 PositionBinding positionBinding,
573                                 Expression action) {
574             this.context = context;
575             this.slotNumber = slotNumber;
576             this.positionBinding = positionBinding;
577             this.action = action;
578         }
579 
580         public Object   map(Item item, XPathContext c) throws XPathException {
581             context.setLocalVariable(slotNumber, item);
582             if (positionBinding != null) {
583                 positionBinding.setPosition(position++, context);
584             }
585             return action.iterate(context);
586         }
587     }
588 
589     /**
590      * Get the type of this expression for use in tracing and diagnostics
591      * @return the type of expression, as enumerated in class {@link net.sf.saxon.trace.Location}
592      */
593 
594     protected int getConstructType() {
595         return Location.FOR_EXPRESSION;
596     }
597 
598     /**
599      * This class represents the binding of the position variable ("at $p") in an XQuery FOR clause.
600      * The variable is held in a slot on the stackframe: in 8.4 and earlier it was held as a property
601      * of the iterator, but that let to problems with lazy evaluation because the value wasn't saved as
602      * part of a Closure.
603      */
604 
605     private static class PositionBinding implements Binding {
606 
607         private int slotNumber;
608 
609         private void setSlotNumber(int slot) {
610             this.slotNumber = slot;
611         }
612 
613         private void setPosition(int position, XPathContext context) {
614             context.setLocalVariable(slotNumber, new IntegerValue(position));
615         }
616 
617         /**
618          * Indicate whether the binding is local or global. A global binding is one that has a fixed
619          * value for the life of a query or transformation; any other binding is local.
620          */
621 
622         public final boolean isGlobal() {
623             return false;
624         }
625 
626         /**
627         * Test whether it is permitted to assign to the variable using the saxon:assign
628         * extension element. This will only be for an XSLT global variable where the extra
629         * attribute saxon:assignable="yes" is present.
630         */
631 
632         public final boolean isAssignable() {
633             return false;
634         }
635 
636         /**
637          * If this is a local variable held on the local stack frame, return the corresponding slot number.
638          * In other cases, return -1.
639          */
640 
641         public int getLocalSlotNumber() {
642             return slotNumber;
643         }
644 
645         public ValueRepresentation evaluateVariable(XPathContext context) throws XPathException {
646             return context.evaluateLocalVariable(slotNumber);
647         }
648 
649     }
650 
651 }
652 
653 
654 
655 //
656 // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
657 // you may not use this file except in compliance with the License. You may obtain a copy of the
658 // License at http://www.mozilla.org/MPL/
659 //
660 // Software distributed under the License is distributed on an "AS IS" basis,
661 // WITHOUT WARRANTY OF ANY KIND, either express or implied.
662 // See the License for the specific language governing rights and limitations under the License.
663 //
664 // The Original Code is: all this file.
665 //
666 // The Initial Developer of the Original Code is Michael H. Kay
667 //
668 // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
669 //
670 // Contributor(s): none.
671 //
672
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags