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