MemoClosure


1   package net.sf.saxon.value;
2   
3   import net.sf.saxon.Controller;
4   import net.sf.saxon.event.SequenceOutputter;
5   import net.sf.saxon.event.SequenceReceiver;
6   import net.sf.saxon.event.TeeOutputter;
7   import net.sf.saxon.expr.LastPositionFinder;
8   import net.sf.saxon.expr.XPathContext;
9   import net.sf.saxon.om.*;
10  import net.sf.saxon.trans.DynamicError;
11  import net.sf.saxon.trans.XPathException;
12  
13  import java.util.List  ;
14  
15  /**
16   * A MemoClosure represents a value that has not yet been evaluated: the value is represented
17   * by an expression, together with saved values of all the context variables that the
18   * expression depends on.
19   * <p/>
20   * <p>The MemoClosure is designed for use when the value is only read several times. The
21   * value is saved on the first evaluation and remembered for later use.</p>
22   * <p/>
23   * <p>The MemoClosure maintains a reservoir containing those items in the value that have
24   * already been read. When a new iterator is requested to read the value, this iterator
25   * first examines and returns any items already placed in the reservoir by previous
26   * users of the MemoClosure. When the reservoir is exhausted, it then uses an underlying
27   * Input Iterator to read further values of the underlying expression. If the value is
28   * not read to completion (for example, if the first user did exists($expr), then the
29   * Input Iterator is left positioned where this user abandoned it. The next user will read
30   * any values left in the reservoir by the first user, and then pick up iterating the
31   * base expression where the first user left off. Eventually, all the values of the
32   * expression will find their way into the reservoir, and future users simply iterate
33   * over the reservoir contents. Alternatively, of course, the values may be left unread.</p>
34   * <p/>
35   * <p>Delayed evaluation is used only for expressions with a static type that allows
36   * more than one item, so the evaluateItem() method will not normally be used, but it is
37   * supported for completeness.</p>
38   * <p/>
39   * <p>The expression may depend on local variables and on the context item; these values
40   * are held in the saved XPathContext object that is kept as part of the Closure, and they
41   * will always be read from that object. The expression may also depend on global variables;
42   * these are unchanging, so they can be read from the Bindery in the normal way. Expressions
43   * that depend on other contextual information, for example the values of position(), last(),
44   * current(), current-group(), should not be evaluated using this mechanism: they should
45   * always be evaluated eagerly. This means that the Closure does not need to keep a copy
46   * of these context variables.</p>
47   */
48  
49  public class MemoClosure extends Closure {
50  
51      private Item[] reservoir = null;
52      private int used;
53      private int state;
54  
55      // State in which no items have yet been read
56      private static final int UNREAD = 0;
57  
58      // State in which zero or more items are in the reservoir and it is not known
59      // whether more items exist
60      private static final int MAYBE_MORE = 1;
61  
62      // State in which all the items are in the reservoir
63      private static final int ALL_READ = 3;
64  
65      // State in which we are getting the base iterator. If the closure is called in this state,
66      // it indicates a recursive entry, which is only possible on an error path
67      private static final int BUSY = 4;
68  
69      // State in which we know that the value is an empty sequence
70      private static final int EMPTY = 5;
71  
72      /**
73       * Constructor should not be called directly, instances should be made using the make() method.
74       */
75  
76      public MemoClosure() {
77      }
78  
79      /**
80       * Evaluate the expression in a given context to return an iterator over a sequence
81       *
82       * @param context the evaluation context. This is ignored; we use the context saved
83       *                as part of the Closure instead.
84       */
85  
86      public SequenceIterator iterate(XPathContext context) throws XPathException {
87  
88          switch (state) {
89              case UNREAD:
90                  state = BUSY;
91                  inputIterator = expression.iterate(savedXPathContext);
92                  if (inputIterator instanceof EmptyIterator) {
93                      state = EMPTY;
94                      return inputIterator;
95                  }
96                  // TODO: following optimization looks OK, but it throws func20 into an infinite loop
97  //                if (inputIterator instanceof GroundedIterator) {
98  //                    state = UNREAD;
99  //                    return inputIterator.getAnother();
100 //                }
101                 reservoir = new Item[50];
102                 used = 0;
103                 state = MAYBE_MORE;
104                 return new ProgressiveIterator();
105 
106             case MAYBE_MORE:
107                 return new ProgressiveIterator();
108 
109             case ALL_READ:
110                 return new ArrayIterator(reservoir, 0, used);
111 
112             case BUSY:
113                 // this indicates a recursive entry, probably on an error path while printing diagnostics
114                 throw new DynamicError("Attempt to access a lazily-evaluated variable while it is being evaluated");
115 
116             case EMPTY:
117                 return EmptyIterator.getInstance();
118 
119             default:
120                 throw new IllegalStateException  ("Unknown iterator state");
121 
122         }
123     }
124 
125     /**
126      * Process the instruction, without returning any tail calls
127      *
128      * @param context The dynamic context, giving access to the current node,
129      *                the current variables, etc.
130      */
131 
132     public void process(XPathContext context) throws XPathException {
133         // To evaluate the closure in push mode, we need to use the original context of the
134         // expression for everything except the current output destination, which is taken from the
135         // context supplied at evaluation time
136         if (state == EMPTY) {
137             return;     // we know there is nothing to do
138         }
139         if (reservoir != null) {
140             SequenceIterator iter = iterate(context);
141             SequenceReceiver out = context.getReceiver();
142             while (true) {
143                 Item it = iter.next();
144                 if (it==null) break;
145                 out.append(it, 0, NodeInfo.ALL_NAMESPACES);
146             }
147         } else {
148             Controller controller = context.getController();
149             XPathContext c2 = savedXPathContext.newMinorContext();
150             //c2.setOrigin(this);
151             // Fork the output: one copy goes to a SequenceOutputter which remembers the contents for
152             // use next time the variable is referenced; another copy goes to the current output destination.
153             SequenceOutputter seq = new SequenceOutputter();
154             seq.setPipelineConfiguration(controller.makePipelineConfiguration());
155             seq.open();
156             TeeOutputter tee = new TeeOutputter(context.getReceiver(), seq);
157             tee.setPipelineConfiguration(controller.makePipelineConfiguration());
158             c2.setTemporaryReceiver(tee);
159 
160             expression.process(c2);
161 
162             seq.close();
163             List   list = seq.getList();
164             if (list.size() == 0) {
165                 state = EMPTY;
166             } else {
167                 reservoir = new Item[list.size()];
168                 reservoir = (Item[])list.toArray(reservoir);
169                 used = list.size();
170                 state = ALL_READ;
171             }
172             // give unwanted stuff to the garbage collector
173             savedXPathContext = null;
174 //            inputIterator = null;
175 //            expression = null;
176         }
177 
178     }
179 
180     /**
181      * Get the n'th item in the sequence (starting from 0). This is defined for all
182      * SequenceValues, but its real benefits come for a SequenceValue stored extensionally
183      */
184 
185     public Item itemAt(int n) throws XPathException {
186         if (n < 0) {
187             return null;
188         }
189         if (reservoir != null && n < used) {
190             return reservoir[n];
191         }
192         if (state == ALL_READ || state == EMPTY) {
193             return null;
194         }
195         if (state == UNREAD) {
196             return super.itemAt(n);
197             // this will read from the start of the sequence
198         }
199         // We have read some items from the input sequence but not enough. Read as many more as are needed.
200         int diff = n - used + 1;
201         while (diff-- > 0) {
202             Item i = inputIterator.next();
203             if (i == null) {
204                 state = ALL_READ;
205                 condense();
206                 return itemAt(n);
207             }
208             append(i);
209             state = MAYBE_MORE;
210         }
211         return reservoir[n];
212     }
213 
214     /**
215      * Get the length of the sequence
216      */
217 
218     public int getLength() throws XPathException {
219         if (state == ALL_READ) {
220             return used;
221         } else if (state == EMPTY) {
222             return 0;
223         } else {
224             return super.getLength();
225         }
226     }
227 
228     /**
229      * Append an item to the reservoir
230      */
231 
232     private void append(Item item) {
233         if (used >= reservoir.length) {
234             Item[] r2 = new Item[used*2];
235             System.arraycopy(reservoir, 0, r2, 0, used);
236             reservoir = r2;
237         }
238         reservoir[used++] = item;
239     }
240 
241     /**
242      * Release unused space in the reservoir (provided the amount of unused space is worth reclaiming)
243      */
244 
245     private void condense() {
246         if (reservoir.length - used > 30) {
247             Item[] r2 = new Item[used];
248             System.arraycopy(reservoir, 0, r2, 0, used);
249             reservoir = r2;
250         }
251         // give unwanted stuff to the garbage collector
252         savedXPathContext = null;
253 //        inputIterator = null;
254 //        expression = null;
255     }
256 
257     /**
258      * A ProgressiveIterator starts by reading any items already held in the reservoir;
259      * when the reservoir is exhausted, it reads further items from the inputIterator,
260      * copying them into the reservoir as they are read.
261      */
262 
263     public final class ProgressiveIterator implements SequenceIterator, LastPositionFinder, GroundedIterator {
264 
265         int position = -1;  // zero-based position in the reservoir of the
266         // item most recently read
267 
268         public ProgressiveIterator() {
269 
270         }
271 
272         public Item next() throws XPathException {
273             if (position == -2) {   // means we've already return null once, keep doing so if called again.
274                 return null;
275             }
276             if (++position < used) {
277                 return reservoir[position];
278 //            } else if (state == ALL_READ) {
279 //                return null;
280             } else {
281                 Item i = inputIterator.next();
282                 if (i == null) {
283                     state = ALL_READ;
284                     condense();
285                     //position--;     // leave position at last item
286                     position = -2;
287                     return null;
288                 }
289                 position = used;
290                 append(i);
291                 state = MAYBE_MORE;
292                 return i;
293             }
294         }
295 
296         public Item current() {
297             if (position < 0) {
298                 return null;
299             }
300             return reservoir[position];
301         }
302 
303         public int position() {
304             return position + 1;    // return one-based position
305         }
306 
307         public SequenceIterator getAnother() {
308             return new ProgressiveIterator();
309         }
310 
311         /**
312          * Get the last position (that is, the number of items in the sequence)
313          */
314 
315         public int getLastPosition() throws XPathException {
316             if (state == ALL_READ) {
317                 return used;
318             } else if (state == EMPTY) {
319                 return 0;
320             } else {
321                 // save the current position
322                 int savePos = position;
323                 // fill the reservoir
324                 while (true) {
325                     Item item = next();
326                     if (item == null) {
327                         break;
328                     }
329                 }
330                 // reset the current position
331                 position = savePos;
332                 // return the total number of items
333                 return used;
334             }
335         }
336 
337         /**
338          * Return a value containing all the items in the sequence returned by this
339          * SequenceIterator
340          *
341          * @return the corresponding value
342          */
343 
344         public Value materialize() throws XPathException {
345             if (state == ALL_READ) {
346                 return new SequenceExtent(reservoir);
347             } else if (state == EMPTY) {
348                 return EmptySequence.getInstance();
349             }
350             return new SequenceExtent(iterate(null));
351 
352         }
353 
354         /**
355          * Get properties of this iterator, as a bit-significant integer.
356          *
357          * @return the properties of this iterator. This will be some combination of
358          *         properties such as {@link GROUNDED} and {@link LAST_POSITION_FINDER}. It is always
359          *         acceptable to return the value zero, indicating that there are no known special properties.
360          */
361 
362         public int getProperties() {
363             if (state == EMPTY || state == ALL_READ) {
364                 return GROUNDED | LAST_POSITION_FINDER;
365             } else {
366                 return 0;
367             }
368         }
369     }
370 
371 }
372 
373 //
374 // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
375 // you may not use this file except in compliance with the License. You may obtain a copy of the
376 // License at http://www.mozilla.org/MPL/
377 //
378 // Software distributed under the License is distributed on an "AS IS" basis,
379 // WITHOUT WARRANTY OF ANY KIND, either express or implied.
380 // See the License for the specific language governing rights and limitations under the License.
381 //
382 // The Original Code is: all this file.
383 //
384 // The Initial Developer of the Original Code is Michael H. Kay.
385 //
386 // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
387 //
388 // Contributor(s): none.
389 //
390
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags