001: package net.sf.saxon.value;
002:
003: import net.sf.saxon.event.SequenceReceiver;
004: import net.sf.saxon.expr.*;
005: import net.sf.saxon.om.*;
006: import net.sf.saxon.trace.Location;
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.TypeHierarchy;
011: import net.sf.saxon.instruct.Block;
012:
013: import java.io.PrintStream;
014: import java.util.List;
015: import java.util.ArrayList;
016:
017: /**
018: * A Closure represents a value that has not yet been evaluated: the value is represented
019: * by an expression, together with saved values of all the context variables that the
020: * expression depends on.
021: *
022: * <p>This Closure is designed for use when the value is only read once. If the value
023: * is read more than once, a new iterator over the underlying expression is obtained
024: * each time: this may (for example in the case of a filter expression) involve
025: * significant re-calculation.</p>
026: *
027: * <p>The expression may depend on local variables and on the context item; these values
028: * are held in the saved XPathContext object that is kept as part of the Closure, and they
029: * will always be read from that object. The expression may also depend on global variables;
030: * these are unchanging, so they can be read from the Bindery in the normal way. Expressions
031: * that depend on other contextual information, for example the values of position(), last(),
032: * current(), current-group(), should not be evaluated using this mechanism: they should
033: * always be evaluated eagerly. This means that the Closure does not need to keep a copy
034: * of these context variables.</p>
035: *
036: */
037:
038: public class Closure extends Value {
039:
040: protected Expression expression;
041: protected XPathContextMajor savedXPathContext;
042: protected int depth = 0;
043:
044: // The base iterator is used to copy items on demand from the underlying value
045: // to the reservoir. It only ever has one instance (for each Closure) and each
046: // item is read only once.
047:
048: protected SequenceIterator inputIterator;
049:
050: // private static int countClosures = 0;
051: // private static int countMemoClosures = 0;
052:
053: /**
054: * Constructor should not be called directly, instances should be made using the make() method.
055: */
056:
057: public Closure() {
058: }
059:
060: /**
061: * Construct a Closure over an existing SequenceIterator. This is used when an extension function
062: * returns a SequenceIterator as its result (it replaces the old SequenceIntent class for this
063: * purpose). There is no known expression in this case. Note that the caller must
064: * ensure this is a "clean" iterator: it must be positioned at the start, and must
065: * not be shared by anyone else.
066: */
067:
068: public static Closure makeIteratorClosure(SequenceIterator iterator) {
069: Closure c = new Closure();
070: c.inputIterator = iterator;
071: return c;
072: }
073:
074: /**
075: * Construct a Closure by supplying the expression and the set of context variables.
076: */
077:
078: public static Value make(Expression expression,
079: XPathContext context, int ref) throws XPathException {
080:
081: // Don't allow lazy evaluation of an ErrorExpression, the results are too confusing
082:
083: if (expression instanceof ErrorExpression) {
084: expression.evaluateItem(context); // throws the exception
085: return null; // keep the compiler happy
086: }
087:
088: // Treat tail recursion as a special case, to avoid creating a deeply-nested
089: // tree of Closures. If this expression is a TailExpression, and its first
090: // argument is also a TailExpression, we combine the two TailExpressions into
091: // one and return a closure over that.
092:
093: if (expression instanceof TailExpression) {
094: TailExpression tail = (TailExpression) expression;
095: Expression base = tail.getBaseExpression();
096: if (base instanceof VariableReference) {
097: base = Value.asValue(ExpressionTool.lazyEvaluate(base,
098: context, ref));
099: if (base instanceof MemoClosure) {
100: SequenceIterator it = base.iterate(null);
101: base = ((GroundedIterator) it).materialize();
102: }
103: if (base instanceof IntegerRange) {
104: long start = ((IntegerRange) base).getStart() + 1;
105: long end = ((IntegerRange) base).getEnd();
106: if (start == end) {
107: return new IntegerValue(end);
108: } else {
109: return new IntegerRange(start, end);
110: }
111: }
112: if (base instanceof SequenceExtent) {
113: return new SequenceExtent((SequenceExtent) base,
114: tail.getStart() - 1,
115: ((SequenceExtent) base).getLength()
116: - tail.getStart() + 1);
117: }
118: }
119: }
120:
121: // If the expression is a Block, that is, it is appending a value to a sequence,
122: // then we have the opportunity to use a shared list underpinning the old value and
123: // the new. This takes precedence over lazy evaluation (it would be possible to do this
124: // lazily, but more difficult). We currently only do this for the common case of a two-argument
125: // append expression, in the case where the first argument is either a value, or a variable
126: // reference identifying a value. The most common case is that the first argument is an argument
127: // to a recursive function, where the recursive function returns the result of appending to
128: // the sequence.
129:
130: if (expression instanceof Block
131: && ((Block) expression).getChildren().length == 2) {
132: Block block = (Block) expression;
133: Expression base = block.getChildren()[0];
134: if (base instanceof VariableReference) {
135: base = Value.asValue(ExpressionTool.lazyEvaluate(base,
136: context, ref));
137: if (base instanceof MemoClosure
138: && ((MemoClosure) base).isFullyRead()) {
139: base = ((MemoClosure) base).materialize();
140: }
141: }
142: if (base instanceof ShareableSequence
143: && ((ShareableSequence) base).isShareable()) {
144: List list = ((ShareableSequence) base).getList();
145: SequenceIterator iter = block.getChildren()[1]
146: .iterate(context);
147: while (true) {
148: Item i = iter.next();
149: if (i == null) {
150: break;
151: }
152: list.add(i);
153: }
154: return new ShareableSequence(list);
155: } else if (base instanceof Value) {
156: List list = new ArrayList(20);
157: SequenceIterator iter = base.iterate(context);
158: while (true) {
159: Item i = iter.next();
160: if (i == null) {
161: break;
162: }
163: list.add(i);
164: }
165: iter = block.getChildren()[1].iterate(context);
166: while (true) {
167: Item i = iter.next();
168: if (i == null) {
169: break;
170: }
171: list.add(i);
172: }
173: return new ShareableSequence(list);
174: }
175: }
176:
177: Closure c = context.getConfiguration().getOptimizer()
178: .makeClosure(expression, ref);
179: //Closure c = (save? new MemoClosure() : new Closure());
180: // if (save) {
181: // countMemoClosures++;
182: // if (countMemoClosures % 100 == 0) System.err.println("MEMO_CLOSURES " + countMemoClosures);
183: // } else {
184: // countClosures++;
185: // if (countClosures % 100 == 0) System.err.println("CLOSURES " + countClosures);
186: // }
187: c.expression = expression;
188: c.savedXPathContext = context.newContext();
189: c.savedXPathContext
190: .setOriginatingConstructType(Location.LAZY_EVALUATION);
191:
192: // Make a copy of all local variables. If the value of any local variable is a closure
193: // whose depth exceeds a certain threshold, we evaluate the closure eagerly to avoid
194: // creating deeply nested lists of Closures, which consume memory unnecessarily
195:
196: // We only copy the local variables if the expression has dependencies on local variables.
197: // What's more, we only copy those variables that the expression actually depends on.
198:
199: if (expression instanceof ComputedExpression
200: && (expression.getDependencies() & StaticProperty.DEPENDS_ON_LOCAL_VARIABLES) != 0) {
201: StackFrame localStackFrame = context.getStackFrame();
202: ValueRepresentation[] local = localStackFrame
203: .getStackFrameValues();
204: int[] slotsUsed = ((ComputedExpression) expression)
205: .getSlotsUsed();
206: if (local != null) {
207: ValueRepresentation[] savedStackFrame = new ValueRepresentation[local.length];
208: for (int s = 0; s < slotsUsed.length; s++) {
209: int i = slotsUsed[s];
210: if (local[i] instanceof Closure) {
211: int cdepth = ((Closure) local[i]).depth;
212: if (cdepth >= 10) {
213: local[i] = ExpressionTool.eagerEvaluate(
214: (Closure) local[i], context);
215: } else if (cdepth + 1 > c.depth) {
216: c.depth = cdepth + 1;
217: }
218: }
219: savedStackFrame[i] = local[i];
220: }
221:
222: c.savedXPathContext.setStackFrame(localStackFrame
223: .getStackFrameMap(), savedStackFrame);
224: }
225: }
226:
227: // Make a copy of the context item
228: SequenceIterator currentIterator = context.getCurrentIterator();
229: if (currentIterator != null) {
230: Item contextItem = currentIterator.current();
231: AxisIterator single = SingletonIterator
232: .makeIterator(contextItem);
233: single.next();
234: c.savedXPathContext.setCurrentIterator(single);
235: // we don't save position() and last() because we have no way
236: // of restoring them. So the caller must ensure that a Closure is not
237: // created if the expression depends on position() or last()
238: }
239:
240: c.savedXPathContext.setReceiver(null);
241: return c;
242: }
243:
244: /**
245: * Get the static item type
246: * @param th
247: */
248:
249: public ItemType getItemType(TypeHierarchy th) {
250: if (expression == null) {
251: return AnyItemType.getInstance();
252: } else {
253: return expression.getItemType(th);
254: }
255: // This is probably rarely used, because a Closure has no static existence, and
256: // run-time polymorphism applies mainly to singletons, which are rarely evaluated as Closures.
257: }
258:
259: /**
260: * Get the cardinality
261: */
262:
263: public int getCardinality() {
264: if (expression == null) {
265: return StaticProperty.ALLOWS_ZERO_OR_MORE;
266: } else {
267: return expression.getCardinality();
268: }
269: }
270:
271: /**
272: * Get the static properties of this expression (other than its type). The result is
273: * bit-signficant. These properties are used for optimizations. In general, if
274: * property bit is set, it is true, but if it is unset, the value is unknown.
275: */
276:
277: public int getSpecialProperties() {
278: if (expression == null) {
279: return StaticProperty.ALLOWS_ZERO_OR_MORE;
280: } else {
281: return expression.getSpecialProperties();
282: }
283: }
284:
285: /**
286: * An implementation of Expression must provide at least one of the methods evaluateItem(), iterate(), or process().
287: * This method indicates which of these methods is provided. This implementation provides both iterate() and
288: * process() methods natively.
289: */
290:
291: public int getImplementationMethod() {
292: return ITERATE_METHOD | PROCESS_METHOD;
293: }
294:
295: /**
296: * Evaluate the expression in a given context to return an iterator over a sequence
297: * @param context the evaluation context. This is ignored; we use the context saved
298: * as part of the Closure instead.
299: */
300:
301: public SequenceIterator iterate(XPathContext context)
302: throws XPathException {
303:
304: if (inputIterator == null) {
305: inputIterator = expression.iterate(savedXPathContext);
306: return inputIterator;
307: } else {
308: // In an ideal world this shouldn't happen: if the value is needed more than once, we should
309: // have chosen a MemoClosure. In fact, this path is never taken when executing the standard
310: // test suite (April 2005). However, it provides robustness in case the compile-time analysis
311: // is flawed. I believe it's also possible that this path can be taken if a Closure needs to be
312: // evaluated when the chain of dependencies gets too long: this was happening routinely when
313: // all local variables were saved, rather than only those that the expression depends on.
314: return inputIterator.getAnother();
315: }
316:
317: }
318:
319: /**
320: * Process the instruction, without returning any tail calls
321: * @param context The dynamic context, giving access to the current node,
322: * the current variables, etc.
323: */
324:
325: public void process(XPathContext context) throws XPathException {
326: // To evaluate the closure in push mode, we need to use the original context of the
327: // expression for everything except the current output destination, which is newly created
328: XPathContext c2 = savedXPathContext.newContext();
329: SequenceReceiver out = context.getReceiver();
330: c2.setTemporaryReceiver(out);
331: expression.process(c2);
332: }
333:
334: /**
335: * Reduce a value to its simplest form. If the value is a closure or some other form of deferred value
336: * such as a FunctionCallPackage, then it is reduced to a SequenceExtent. If it is a SequenceExtent containing
337: * a single item, then it is reduced to that item. One consequence that is exploited by class FilterExpression
338: * is that if the value is a singleton numeric value, then the result will be an instance of NumericValue
339: */
340:
341: public Value reduce() throws XPathException {
342: return new SequenceExtent(iterate(null)).reduce();
343: }
344:
345: /**
346: * Determine whether this Closure is indexable
347: */
348:
349: public boolean isIndexable() {
350: return false;
351: }
352:
353: public void display(int level, NamePool pool, PrintStream out) {
354: out.println(ExpressionTool.indent(level)
355: + "Closure of expression:");
356: expression.display(level + 1, pool, out);
357: }
358:
359: }
360:
361: //
362: // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
363: // you may not use this file except in compliance with the License. You may obtain a copy of the
364: // License at http://www.mozilla.org/MPL/
365: //
366: // Software distributed under the License is distributed on an "AS IS" basis,
367: // WITHOUT WARRANTY OF ANY KIND, either express or implied.
368: // See the License for the specific language governing rights and limitations under the License.
369: //
370: // The Original Code is: all this file.
371: //
372: // The Initial Developer of the Original Code is Michael H. Kay.
373: //
374: // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
375: //
376: // Contributor(s): none.
377: //
|