View Javadoc
1   /*
2    * reserved comment block
3    * DO NOT REMOVE OR ALTER!
4    */
5   /*
6    * Copyright 1999-2004 The Apache Software Foundation.
7    *
8    * Licensed under the Apache License, Version 2.0 (the "License");
9    * you may not use this file except in compliance with the License.
10   * You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  /*
21   * $Id: CoroutineManager.java,v 1.2.4.1 2005/09/15 08:14:58 suresh_emailid Exp $
22   */
23  package com.sun.org.apache.xml.internal.dtm.ref;
24  
25  import java.util.BitSet;
26  
27  import com.sun.org.apache.xml.internal.res.XMLErrorResources;
28  import com.sun.org.apache.xml.internal.res.XMLMessages;
29  
30  
31  /**
32   * <p>Support the coroutine design pattern.</p>
33   *
34   * <p>A coroutine set is a very simple cooperative non-preemptive
35   * multitasking model, where the switch from one task to another is
36   * performed via an explicit request. Coroutines interact according to
37   * the following rules:</p>
38   *
39   * <ul>
40   * <li>One coroutine in the set has control, which it retains until it
41   * either exits or resumes another coroutine.</li>
42   * <li>A coroutine is activated when it is resumed by some other coroutine
43   * for the first time.</li>
44   * <li>An active coroutine that gives up control by resuming another in
45   * the set retains its context -- including call stack and local variables
46   * -- so that if/when it is resumed, it will proceed from the point at which
47   * it last gave up control.</li>
48   * </ul>
49   *
50   * <p>Coroutines can be thought of as falling somewhere between pipes and
51   * subroutines. Like call/return, there is an explicit flow of control
52   * from one coroutine to another. Like pipes, neither coroutine is
53   * actually "in charge", and neither must exit in order to transfer
54   * control to the other. </p>
55   *
56   * <p>One classic application of coroutines is in compilers, where both
57   * the parser and the lexer are maintaining complex state
58   * information. The parser resumes the lexer to process incoming
59   * characters into lexical tokens, and the lexer resumes the parser
60   * when it has reached a point at which it has a reliably interpreted
61   * set of tokens available for semantic processing. Structuring this
62   * as call-and-return would require saving and restoring a
63   * considerable amount of state each time. Structuring it as two tasks
64   * connected by a queue may involve higher overhead (in systems which
65   * can optimize the coroutine metaphor), isn't necessarily as clear in
66   * intent, may have trouble handling cases where data flows in both
67   * directions, and may not handle some of the more complex cases where
68   * more than two coroutines are involved.</p>
69   *
70   * <p>Most coroutine systems also provide a way to pass data between the
71   * source and target of a resume operation; this is sometimes referred
72   * to as "yielding" a value.  Others rely on the fact that, since only
73   * one member of a coroutine set is running at a time and does not
74   * lose control until it chooses to do so, data structures may be
75   * directly shared between them with only minimal precautions.</p>
76   *
77   * <p>"Note: This should not be taken to mean that producer/consumer
78   * problems should be always be done with coroutines." Queueing is
79   * often a better solution when only two threads of execution are
80   * involved and full two-way handshaking is not required. It's a bit
81   * difficult to find short pedagogical examples that require
82   * coroutines for a clear solution.</p>
83   *
84   * <p>The fact that only one of a group of coroutines is running at a
85   * time, and the control transfer between them is explicit, simplifies
86   * their possible interactions, and in some implementations permits
87   * them to be implemented more efficiently than general multitasking.
88   * In some situations, coroutines can be compiled out entirely;
89   * in others, they may only require a few instructions more than a
90   * simple function call.</p>
91   *
92   * <p>This version is built on top of standard Java threading, since
93   * that's all we have available right now. It's been encapsulated for
94   * code clarity and possible future optimization.</p>
95   *
96   * <p>(Two possible approaches: wait-notify based and queue-based. Some
97   * folks think that a one-item queue is a cleaner solution because it's
98   * more abstract -- but since coroutine _is_ an abstraction I'm not really
99   * worried about that; folks should be able to switch this code without
100  * concern.)</p>
101  *
102  * <p>%TBD% THIS SHOULD BE AN INTERFACE, to facilitate building other
103  * implementations... perhaps including a true coroutine system
104  * someday, rather than controlled threading. Arguably Coroutine
105  * itself should be an interface much like Runnable, but I think that
106  * can be built on top of this.</p>
107  * */
108 public class CoroutineManager
109 {
110   /** "Is this coroutine ID number already in use" lookup table.
111    * Currently implemented as a bitset as a compromise between
112    * compactness and speed of access, but obviously other solutions
113    * could be applied.
114    * */
115   BitSet m_activeIDs=new BitSet();
116 
117   /** Limit on the coroutine ID numbers accepted. I didn't want the
118    * in-use table to grow without bound. If we switch to a more efficient
119    * sparse-array mechanism, it may be possible to raise or eliminate
120    * this boundary.
121    * @xsl.usage internal
122    */
123   static final int m_unreasonableId=1024;
124 
125   /** Internal field used to hold the data being explicitly passed
126    * from one coroutine to another during a co_resume() operation.
127    * (Of course implicit data sharing may also occur; one of the reasons
128    * for using coroutines is that you're guaranteed that none of the
129    * other coroutines in your set are using shared structures at the time
130    * you access them.)
131    *
132    * %REVIEW% It's been proposed that we be able to pass types of data
133    * other than Object -- more specific object types, or
134    * lighter-weight primitives.  This would seem to create a potential
135    * explosion of "pass x recieve y back" methods (or require
136    * fracturing resume into two calls, resume-other and
137    * wait-to-be-resumed), and the weight issue could be managed by
138    * reusing a mutable buffer object to contain the primitive
139    * (remember that only one coroutine runs at a time, so once the
140    * buffer's set it won't be walked on). Typechecking objects is
141    * interesting from a code-robustness point of view, but it's
142    * unclear whether it makes sense to encapsulate that in the
143    * coroutine code or let the callers do it, since it depends on RTTI
144    * either way. Restricting the parameters to objects implementing a
145    * specific CoroutineParameter interface does _not_ seem to be a net
146    * win; applications can do so if they want via front-end code, but
147    * there seem to be too many use cases involving passing an existing
148    * object type that you may not have the freedom to alter and may
149    * not want to spend time wrapping another object around.
150    * */
151   Object m_yield=null;
152 
153   // Expose???
154   final static int NOBODY=-1;
155   final static int ANYBODY=-1;
156 
157   /** Internal field used to confirm that the coroutine now waking up is
158    * in fact the one we intended to resume. Some such selection mechanism
159    * is needed when more that two coroutines are operating within the same
160    * group.
161    */
162   int m_nextCoroutine=NOBODY;
163 
164   /** <p>Each coroutine in the set managed by a single
165    * CoroutineManager is identified by a small positive integer. This
166    * brings up the question of how to manage those integers to avoid
167    * reuse... since if two coroutines use the same ID number, resuming
168    * that ID could resume either. I can see arguments for either
169    * allowing applications to select their own numbers (they may want
170    * to declare mnemonics via manefest constants) or generating
171    * numbers on demand.  This routine's intended to support both
172    * approaches.</p>
173    *
174    * <p>%REVIEW% We could use an object as the identifier. Not sure
175    * it's a net gain, though it would allow the thread to be its own
176    * ID. Ponder.</p>
177    *
178    * @param coroutineID  If >=0, requests that we reserve this number.
179    * If <0, requests that we find, reserve, and return an available ID
180    * number.
181    *
182    * @return If >=0, the ID number to be used by this coroutine. If <0,
183    * an error occurred -- the ID requested was already in use, or we
184    * couldn't assign one without going over the "unreasonable value" mark
185    * */
186   public synchronized int co_joinCoroutineSet(int coroutineID)
187   {
188     if(coroutineID>=0)
189       {
190         if(coroutineID>=m_unreasonableId || m_activeIDs.get(coroutineID))
191           return -1;
192       }
193     else
194       {
195         // What I want is "Find first clear bit". That doesn't exist.
196         // JDK1.2 added "find last set bit", but that doesn't help now.
197         coroutineID=0;
198         while(coroutineID<m_unreasonableId)
199           {
200             if(m_activeIDs.get(coroutineID))
201               ++coroutineID;
202             else
203               break;
204           }
205         if(coroutineID>=m_unreasonableId)
206           return -1;
207       }
208 
209     m_activeIDs.set(coroutineID);
210     return coroutineID;
211   }
212 
213   /** In the standard coroutine architecture, coroutines are
214    * identified by their method names and are launched and run up to
215    * their first yield by simply resuming them; its's presumed that
216    * this recognizes the not-already-running case and does the right
217    * thing. We seem to need a way to achieve that same threadsafe
218    * run-up...  eg, start the coroutine with a wait.
219    *
220    * %TBD% whether this makes any sense...
221    *
222    * @param thisCoroutine the identifier of this coroutine, so we can
223    * recognize when we are being resumed.
224    * @exception java.lang.NoSuchMethodException if thisCoroutine isn't
225    * a registered member of this group. %REVIEW% whether this is the
226    * best choice.
227    * */
228   public synchronized Object co_entry_pause(int thisCoroutine) throws java.lang.NoSuchMethodException
229   {
230     if(!m_activeIDs.get(thisCoroutine))
231       throw new java.lang.NoSuchMethodException();
232 
233     while(m_nextCoroutine != thisCoroutine)
234       {
235         try
236           {
237             wait();
238           }
239         catch(java.lang.InterruptedException e)
240           {
241             // %TBD% -- Declare? Encapsulate? Ignore? Or
242             // dance widdershins about the instruction cache?
243           }
244       }
245 
246     return m_yield;
247   }
248 
249   /** Transfer control to another coroutine which has already been started and
250    * is waiting on this CoroutineManager. We won't return from this call
251    * until that routine has relinquished control.
252    *
253    * %TBD% What should we do if toCoroutine isn't registered? Exception?
254    *
255    * @param arg_object A value to be passed to the other coroutine.
256    * @param thisCoroutine Integer identifier for this coroutine. This is the
257    * ID we watch for to see if we're the ones being resumed.
258    * @param toCoroutine  Integer identifier for the coroutine we wish to
259    * invoke.
260    * @exception java.lang.NoSuchMethodException if toCoroutine isn't a
261    * registered member of this group. %REVIEW% whether this is the best choice.
262    * */
263   public synchronized Object co_resume(Object arg_object,int thisCoroutine,int toCoroutine) throws java.lang.NoSuchMethodException
264   {
265     if(!m_activeIDs.get(toCoroutine))
266       throw new java.lang.NoSuchMethodException(XMLMessages.createXMLMessage(XMLErrorResources.ER_COROUTINE_NOT_AVAIL, new Object[]{Integer.toString(toCoroutine)})); //"Coroutine not available, id="+toCoroutine);
267 
268     // We expect these values to be overwritten during the notify()/wait()
269     // periods, as other coroutines in this set get their opportunity to run.
270     m_yield=arg_object;
271     m_nextCoroutine=toCoroutine;
272 
273     notify();
274     while(m_nextCoroutine != thisCoroutine || m_nextCoroutine==ANYBODY || m_nextCoroutine==NOBODY)
275       {
276         try
277           {
278             // System.out.println("waiting...");
279             wait();
280           }
281         catch(java.lang.InterruptedException e)
282           {
283             // %TBD% -- Declare? Encapsulate? Ignore? Or
284             // dance deasil about the program counter?
285           }
286       }
287 
288     if(m_nextCoroutine==NOBODY)
289       {
290         // Pass it along
291         co_exit(thisCoroutine);
292         // And inform this coroutine that its partners are Going Away
293         // %REVIEW% Should this throw/return something more useful?
294         throw new java.lang.NoSuchMethodException(XMLMessages.createXMLMessage(XMLErrorResources.ER_COROUTINE_CO_EXIT, null)); //"CoroutineManager recieved co_exit() request");
295       }
296 
297     return m_yield;
298   }
299 
300   /** Terminate this entire set of coroutines. The others will be
301    * deregistered and have exceptions thrown at them. Note that this
302    * is intended as a panic-shutdown operation; under normal
303    * circumstances a coroutine should always end with co_exit_to() in
304    * order to politely inform at least one of its partners that it is
305    * going away.
306    *
307    * %TBD% This may need significantly more work.
308    *
309    * %TBD% Should this just be co_exit_to(,,CoroutineManager.PANIC)?
310    *
311    * @param thisCoroutine Integer identifier for the coroutine requesting exit.
312    * */
313   public synchronized void co_exit(int thisCoroutine)
314   {
315     m_activeIDs.clear(thisCoroutine);
316     m_nextCoroutine=NOBODY; // %REVIEW%
317     notify();
318   }
319 
320   /** Make the ID available for reuse and terminate this coroutine,
321    * transferring control to the specified coroutine. Note that this
322    * returns immediately rather than waiting for any further coroutine
323    * traffic, so the thread can proceed with other shutdown activities.
324    *
325    * @param arg_object    A value to be passed to the other coroutine.
326    * @param thisCoroutine Integer identifier for the coroutine leaving the set.
327    * @param toCoroutine   Integer identifier for the coroutine we wish to
328    * invoke.
329    * @exception java.lang.NoSuchMethodException if toCoroutine isn't a
330    * registered member of this group. %REVIEW% whether this is the best choice.
331    * */
332   public synchronized void co_exit_to(Object arg_object,int thisCoroutine,int toCoroutine) throws java.lang.NoSuchMethodException
333   {
334     if(!m_activeIDs.get(toCoroutine))
335       throw new java.lang.NoSuchMethodException(XMLMessages.createXMLMessage(XMLErrorResources.ER_COROUTINE_NOT_AVAIL, new Object[]{Integer.toString(toCoroutine)})); //"Coroutine not available, id="+toCoroutine);
336 
337     // We expect these values to be overwritten during the notify()/wait()
338     // periods, as other coroutines in this set get their opportunity to run.
339     m_yield=arg_object;
340     m_nextCoroutine=toCoroutine;
341 
342     m_activeIDs.clear(thisCoroutine);
343 
344     notify();
345   }
346 }