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