- /*
- * The Apache Software License, Version 1.1
- *
- *
- * Copyright (c) 1999 The Apache Software Foundation. All rights
- * reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- *
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in
- * the documentation and/or other materials provided with the
- * distribution.
- *
- * 3. The end-user documentation included with the redistribution,
- * if any, must include the following acknowledgment:
- * "This product includes software developed by the
- * Apache Software Foundation (http://www.apache.org/)."
- * Alternately, this acknowledgment may appear in the software itself,
- * if and wherever such third-party acknowledgments normally appear.
- *
- * 4. The names "Xalan" and "Apache Software Foundation" must
- * not be used to endorse or promote products derived from this
- * software without prior written permission. For written
- * permission, please contact apache@apache.org.
- *
- * 5. Products derived from this software may not be called "Apache",
- * nor may "Apache" appear in their name, without prior written
- * permission of the Apache Software Foundation.
- *
- * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
- * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
- * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
- * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
- * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
- * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- * ====================================================================
- *
- * This software consists of voluntary contributions made by many
- * individuals on behalf of the Apache Software Foundation and was
- * originally based on software copyright (c) 1999, Lotus
- * Development Corporation., http://www.lotus.com. For more
- * information on the Apache Software Foundation, please see
- * <http://www.apache.org/>.
- */
- package org.apache.xml.dtm.ref;
-
- import java.util.*;
- import org.apache.xml.dtm.*;
-
- import org.apache.xalan.res.XSLTErrorResources;
- import org.apache.xalan.res.XSLMessages;
-
-
- /**
- * <meta name="usage" content="internal"/>
- * <p>Support the coroutine design pattern.</p>
- *
- * <p>A coroutine set is a very simple cooperative non-preemptive
- * multitasking model, where the switch from one task to another is
- * performed via an explicit request. Coroutines interact according to
- * the following rules:</p>
- *
- * <ul>
- * <li>One coroutine in the set has control, which it retains until it
- * either exits or resumes another coroutine.</li>
- * <li>A coroutine is activated when it is resumed by some other coroutine
- * for the first time.</li>
- * <li>An active coroutine that gives up control by resuming another in
- * the set retains its context -- including call stack and local variables
- * -- so that if/when it is resumed, it will proceed from the point at which
- * it last gave up control.</li>
- * </ul>
- *
- * <p>Coroutines can be thought of as falling somewhere between pipes and
- * subroutines. Like call/return, there is an explicit flow of control
- * from one coroutine to another. Like pipes, neither coroutine is
- * actually "in charge", and neither must exit in order to transfer
- * control to the other. </p>
- *
- * <p>One classic application of coroutines is in compilers, where both
- * the parser and the lexer are maintaining complex state
- * information. The parser resumes the lexer to process incoming
- * characters into lexical tokens, and the lexer resumes the parser
- * when it has reached a point at which it has a reliably interpreted
- * set of tokens available for semantic processing. Structuring this
- * as call-and-return would require saving and restoring a
- * considerable amount of state each time. Structuring it as two tasks
- * connected by a queue may involve higher overhead (in systems which
- * can optimize the coroutine metaphor), isn't necessarily as clear in
- * intent, may have trouble handling cases where data flows in both
- * directions, and may not handle some of the more complex cases where
- * more than two coroutines are involved.</p>
- *
- * <p>Most coroutine systems also provide a way to pass data between the
- * source and target of a resume operation; this is sometimes referred
- * to as "yielding" a value. Others rely on the fact that, since only
- * one member of a coroutine set is running at a time and does not
- * lose control until it chooses to do so, data structures may be
- * directly shared between them with only minimal precautions.</p>
- *
- * <p>"Note: This should not be taken to mean that producer/consumer
- * problems should be always be done with coroutines." Queueing is
- * often a better solution when only two threads of execution are
- * involved and full two-way handshaking is not required. It's a bit
- * difficult to find short pedagogical examples that require
- * coroutines for a clear solution.</p>
- *
- * <p>The fact that only one of a group of coroutines is running at a
- * time, and the control transfer between them is explicit, simplifies
- * their possible interactions, and in some implementations permits
- * them to be implemented more efficiently than general multitasking.
- * In some situations, coroutines can be compiled out entirely;
- * in others, they may only require a few instructions more than a
- * simple function call.</p>
- *
- * <p>This version is built on top of standard Java threading, since
- * that's all we have available right now. It's been encapsulated for
- * code clarity and possible future optimization.</p>
- *
- * <p>(Two possible approaches: wait-notify based and queue-based. Some
- * folks think that a one-item queue is a cleaner solution because it's
- * more abstract -- but since coroutine _is_ an abstraction I'm not really
- * worried about that; folks should be able to switch this code without
- * concern.)</p>
- *
- * <p>%TBD% THIS SHOULD BE AN INTERFACE, to facilitate building other
- * implementations... perhaps including a true coroutine system
- * someday, rather than controlled threading. Arguably Coroutine
- * itself should be an interface much like Runnable, but I think that
- * can be built on top of this.</p>
- * */
- public class CoroutineManager
- {
- /** "Is this coroutine ID number already in use" lookup table.
- * Currently implemented as a bitset as a compromise between
- * compactness and speed of access, but obviously other solutions
- * could be applied.
- * */
- BitSet m_activeIDs=new BitSet();
-
- /** Limit on the coroutine ID numbers accepted. I didn't want the
- * in-use table to grow without bound. If we switch to a more efficient
- * sparse-array mechanism, it may be possible to raise or eliminate
- * this boundary.
- */
- static final int m_unreasonableId=1024;
-
- /** Internal field used to hold the data being explicitly passed
- * from one coroutine to another during a co_resume() operation.
- * (Of course implicit data sharing may also occur; one of the reasons
- * for using coroutines is that you're guaranteed that none of the
- * other coroutines in your set are using shared structures at the time
- * you access them.)
- *
- * %REVIEW% It's been proposed that we be able to pass types of data
- * other than Object -- more specific object types, or
- * lighter-weight primitives. This would seem to create a potential
- * explosion of "pass x recieve y back" methods (or require
- * fracturing resume into two calls, resume-other and
- * wait-to-be-resumed), and the weight issue could be managed by
- * reusing a mutable buffer object to contain the primitive
- * (remember that only one coroutine runs at a time, so once the
- * buffer's set it won't be walked on). Typechecking objects is
- * interesting from a code-robustness point of view, but it's
- * unclear whether it makes sense to encapsulate that in the
- * coroutine code or let the callers do it, since it depends on RTTI
- * either way. Restricting the parameters to objects implementing a
- * specific CoroutineParameter interface does _not_ seem to be a net
- * win; applications can do so if they want via front-end code, but
- * there seem to be too many use cases involving passing an existing
- * object type that you may not have the freedom to alter and may
- * not want to spend time wrapping another object around.
- * */
- Object m_yield=null;
-
- // Expose???
- final static int NOBODY=-1;
- final static int ANYBODY=-1;
-
- /** Internal field used to confirm that the coroutine now waking up is
- * in fact the one we intended to resume. Some such selection mechanism
- * is needed when more that two coroutines are operating within the same
- * group.
- */
- int m_nextCoroutine=NOBODY;
-
- /** <p>Each coroutine in the set managed by a single
- * CoroutineManager is identified by a small positive integer. This
- * brings up the question of how to manage those integers to avoid
- * reuse... since if two coroutines use the same ID number, resuming
- * that ID could resume either. I can see arguments for either
- * allowing applications to select their own numbers (they may want
- * to declare mnemonics via manefest constants) or generating
- * numbers on demand. This routine's intended to support both
- * approaches.</p>
- *
- * <p>%REVIEW% We could use an object as the identifier. Not sure
- * it's a net gain, though it would allow the thread to be its own
- * ID. Ponder.</p>
- *
- * @param coroutineID: If >=0, requests that we reserve this number.
- * If <0, requests that we find, reserve, and return an available ID
- * number.
- *
- * @return If >=0, the ID number to be used by this coroutine. If <0,
- * an error occurred -- the ID requested was already in use, or we
- * couldn't assign one without going over the "unreasonable value" mark
- * */
- public synchronized int co_joinCoroutineSet(int coroutineID)
- {
- if(coroutineID>=0)
- {
- if(coroutineID>=m_unreasonableId || m_activeIDs.get(coroutineID))
- return -1;
- }
- else
- {
- // What I want is "Find first clear bit". That doesn't exist.
- // JDK1.2 added "find last set bit", but that doesn't help now.
- coroutineID=0;
- while(coroutineID<m_unreasonableId)
- {
- if(m_activeIDs.get(coroutineID))
- ++coroutineID;
- else
- break;
- }
- if(coroutineID>=m_unreasonableId)
- return -1;
- }
-
- m_activeIDs.set(coroutineID);
- return coroutineID;
- }
-
- /** In the standard coroutine architecture, coroutines are
- * identified by their method names and are launched and run up to
- * their first yield by simply resuming them; its's presumed that
- * this recognizes the not-already-running case and does the right
- * thing. We seem to need a way to achieve that same threadsafe
- * run-up... eg, start the coroutine with a wait.
- *
- * %TBD% whether this makes any sense...
- *
- * @param thisCoroutine the identifier of this coroutine, so we can
- * recognize when we are being resumed.
- * @exception java.lang.NoSuchMethodException if thisCoroutine isn't
- * a registered member of this group. %REVIEW% whether this is the
- * best choice.
- * */
- public synchronized Object co_entry_pause(int thisCoroutine) throws java.lang.NoSuchMethodException
- {
- if(!m_activeIDs.get(thisCoroutine))
- throw new java.lang.NoSuchMethodException();
-
- while(m_nextCoroutine != thisCoroutine)
- {
- try
- {
- wait();
- }
- catch(java.lang.InterruptedException e)
- {
- // %TBD% -- Declare? Encapsulate? Ignore? Or
- // dance widdershins about the instruction cache?
- }
- }
-
- return m_yield;
- }
-
- /** Transfer control to another coroutine which has already been started and
- * is waiting on this CoroutineManager. We won't return from this call
- * until that routine has relinquished control.
- *
- * %TBD% What should we do if toCoroutine isn't registered? Exception?
- *
- * @param arg_object A value to be passed to the other coroutine.
- * @param thisCoroutine Integer identifier for this coroutine. This is the
- * ID we watch for to see if we're the ones being resumed.
- * @param toCoroutine. Integer identifier for the coroutine we wish to
- * invoke.
- * @exception java.lang.NoSuchMethodException if toCoroutine isn't a
- * registered member of this group. %REVIEW% whether this is the best choice.
- * */
- public synchronized Object co_resume(Object arg_object,int thisCoroutine,int toCoroutine) throws java.lang.NoSuchMethodException
- {
- if(!m_activeIDs.get(toCoroutine))
- throw new java.lang.NoSuchMethodException(XSLMessages.createMessage(XSLTErrorResources.ER_COROUTINE_NOT_AVAIL, new Object[]{Integer.toString(toCoroutine)})); //"Coroutine not available, id="+toCoroutine);
-
- // We expect these values to be overwritten during the notify()/wait()
- // periods, as other coroutines in this set get their opportunity to run.
- m_yield=arg_object;
- m_nextCoroutine=toCoroutine;
-
- notify();
- while(m_nextCoroutine != thisCoroutine || m_nextCoroutine==ANYBODY || m_nextCoroutine==NOBODY)
- {
- try
- {
- // System.out.println("waiting...");
- wait();
- }
- catch(java.lang.InterruptedException e)
- {
- // %TBD% -- Declare? Encapsulate? Ignore? Or
- // dance deasil about the program counter?
- }
- }
-
- if(m_nextCoroutine==NOBODY)
- {
- // Pass it along
- co_exit(thisCoroutine);
- // And inform this coroutine that its partners are Going Away
- // %REVIEW% Should this throw/return something more useful?
- throw new java.lang.NoSuchMethodException(XSLMessages.createMessage(XSLTErrorResources.ER_COROUTINE_CO_EXIT, null)); //"CoroutineManager recieved co_exit() request");
- }
-
- return m_yield;
- }
-
- /** Terminate this entire set of coroutines. The others will be
- * deregistered and have exceptions thrown at them. Note that this
- * is intended as a panic-shutdown operation; under normal
- * circumstances a coroutine should always end with co_exit_to() in
- * order to politely inform at least one of its partners that it is
- * going away.
- *
- * %TBD% This may need significantly more work.
- *
- * %TBD% Should this just be co_exit_to(,,CoroutineManager.PANIC)?
- *
- * @param thisCoroutine Integer identifier for the coroutine requesting exit.
- * */
- public synchronized void co_exit(int thisCoroutine)
- {
- m_activeIDs.clear(thisCoroutine);
- m_nextCoroutine=NOBODY; // %REVIEW%
- notify();
- }
-
- /** Make the ID available for reuse and terminate this coroutine,
- * transferring control to the specified coroutine. Note that this
- * returns immediately rather than waiting for any further coroutine
- * traffic, so the thread can proceed with other shutdown activities.
- *
- * @param arg_object A value to be passed to the other coroutine.
- * @param thisCoroutine Integer identifier for the coroutine leaving the set.
- * @param toCoroutine. Integer identifier for the coroutine we wish to
- * invoke.
- * @exception java.lang.NoSuchMethodException if toCoroutine isn't a
- * registered member of this group. %REVIEW% whether this is the best choice.
- * */
- public synchronized void co_exit_to(Object arg_object,int thisCoroutine,int toCoroutine) throws java.lang.NoSuchMethodException
- {
- if(!m_activeIDs.get(toCoroutine))
- throw new java.lang.NoSuchMethodException(XSLMessages.createMessage(XSLTErrorResources.ER_COROUTINE_NOT_AVAIL, new Object[]{Integer.toString(toCoroutine)})); //"Coroutine not available, id="+toCoroutine);
-
- // We expect these values to be overwritten during the notify()/wait()
- // periods, as other coroutines in this set get their opportunity to run.
- m_yield=arg_object;
- m_nextCoroutine=toCoroutine;
-
- m_activeIDs.clear(thisCoroutine);
-
- notify();
- }
- }