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