Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 445 lines (403 sloc) 14.275 kB
ca33263 @afri apollo 0.8.0 code
afri authored
1 /*
e15135d @afri more module browser/std lib refactoring
afri authored
2 * Oni Apollo 'cutil' module
ca33263 @afri apollo 0.8.0 code
afri authored
3 * Utility functions and constructs for concurrent stratified programming
4 *
70d98a4 @afri Big restructuring of oni-apollo.js. All modules are now external, oni…
afri authored
5 * Part of the Oni Apollo Standard Module Library
b48ce09 @afri Wrap version string in quotes rather than '< >'.
afri authored
6 * Version: 'unstable'
ca33263 @afri apollo 0.8.0 code
afri authored
7 * http://onilabs.com/apollo
8 *
7f92bc3 @afri Add shim for some ECMA 262/5 functions. Deprecate common.isArray()/co…
afri authored
9 * (c) 2010-2011 Oni Labs, http://onilabs.com
ca33263 @afri apollo 0.8.0 code
afri authored
10 *
11 * This file is licensed under the terms of the MIT License:
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining a copy
14 * of this software and associated documentation files (the "Software"), to deal
15 * in the Software without restriction, including without limitation the rights
16 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
17 * copies of the Software, and to permit persons to whom the Software is
18 * furnished to do so, subject to the following conditions:
19 *
20 * The above copyright notice and this permission notice shall be included in
21 * all copies or substantial portions of the Software.
22 *
23 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
24 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
25 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
26 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
28 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
29 * THE SOFTWARE.
30 *
31 */
32 /**
33 @module cutil
e15135d @afri more module browser/std lib refactoring
afri authored
34 @summary Utility functions and constructs for concurrent stratified programming
35 @home apollo:cutil
ca33263 @afri apollo 0.8.0 code
afri authored
36 */
37
4333136 @afri Add cutil.makeMemoizedFunction. Move waitforFirst/waitforAll to colle…
afri authored
38 var sys = require('sjs:apollo-sys');
52cddc7 @afri move collection.sjs into core/
afri authored
39 var coll = require('./collection');
f49c82d @afri Bring cutil.waitforAll/waitforFirst args in line with Array.map
afri authored
40
ca33263 @afri apollo 0.8.0 code
afri authored
41 /**
42 @function waitforAll
66c2bc4 @afri module browser rewrite
afri authored
43 @deprecated Use [collection::par.waitforAll]
ca33263 @afri apollo 0.8.0 code
afri authored
44 */
4333136 @afri Add cutil.makeMemoizedFunction. Move waitforFirst/waitforAll to colle…
afri authored
45 exports.waitforAll = coll.par.waitforAll;
5eda692 @afri Generalize cutil.waitforAll to single functions + argument arrays
afri authored
46
ca33263 @afri apollo 0.8.0 code
afri authored
47 /**
48 @function waitforFirst
66c2bc4 @afri module browser rewrite
afri authored
49 @deprecated Use [collection::par.waitforFirst]
ca33263 @afri apollo 0.8.0 code
afri authored
50 */
4333136 @afri Add cutil.makeMemoizedFunction. Move waitforFirst/waitforAll to colle…
afri authored
51 exports.waitforFirst = coll.par.waitforFirst;
91670a4 @afri Enhance cutil.waitforFirst()
afri authored
52
53
ca33263 @afri apollo 0.8.0 code
afri authored
54 /**
55 @class Semaphore
56 @summary A counting semaphore.
57 @function Semaphore
58 @param {Integer} [permits] Number of permits available to be handed out.
66c2bc4 @afri module browser rewrite
afri authored
59 @param {Boolean} [sync=false] Toggles synchronous behaviour (see [::Semaphore::release])
ca33263 @afri apollo 0.8.0 code
afri authored
60 @desc
61 Example:
62 `var S = new (cutil.Semaphore)(10);`
63 */
70d98a4 @afri Big restructuring of oni-apollo.js. All modules are now external, oni…
afri authored
64 function Semaphore(permits, sync) {
ca33263 @afri apollo 0.8.0 code
afri authored
65 /**
66 @variable Semaphore.permits
67 @summary Number of free permits currently available to be handed out.
68 */
69 this.permits = permits;
70d98a4 @afri Big restructuring of oni-apollo.js. All modules are now external, oni…
afri authored
70 this.sync = sync;
ca33263 @afri apollo 0.8.0 code
afri authored
71 this.queue = [];
72 var me = this;
73 this._permit = { __finally__: function() { me.release(); } };
74 }
75 exports.Semaphore = Semaphore;
76 Semaphore.prototype = {
77 /**
78 @function Semaphore.acquire
79 @summary Acquire a permit. If all permits are currently taken, block until one
80 becomes available.
81 @return {Permit} An object with a *__finally__* method, which will release
82 the semaphore.
83 @desc
66c2bc4 @afri module browser rewrite
afri authored
84 Calls to [::Semaphore::acquire] usually need to be paired up
b8ce726 @afri Semaphore.synchronize
afri authored
85 with calls to [::Semaphore::release]. Instead of ensuring this pairing
86 manually, consider using [::Semaphore::synchronize], or the following
87 deprecated `using` syntax:
ca33263 @afri apollo 0.8.0 code
afri authored
88
b8ce726 @afri Semaphore.synchronize
afri authored
89 using (mySemaphore.acquire()) {
90 ...
91 }
ca33263 @afri apollo 0.8.0 code
afri authored
92
b8ce726 @afri Semaphore.synchronize
afri authored
93 Here the `using` construct will automatically call the permit's
66c2bc4 @afri module browser rewrite
afri authored
94 `__finally__` method when the code block is left.
ca33263 @afri apollo 0.8.0 code
afri authored
95 */
96 acquire: function() {
97 if (this.permits <= 0) {
98 waitfor() {
99 this.queue.push(resume);
100 }
101 retract {
102 for (var i=0; this.queue[i] != resume; ++i) /**/;
103 this.queue.splice(i, 1);
104 }
105 }
106 --this.permits;
107 return this._permit;
108 },
109
110 /**
111 @function Semaphore.release
112 @summary Release a permit.
113 @desc
114 If upon releasing a permit, there are other strata
115 waiting for a permit (by blocking in
66c2bc4 @afri module browser rewrite
afri authored
116 [::Semaphore::acquire]),
70d98a4 @afri Big restructuring of oni-apollo.js. All modules are now external, oni…
afri authored
117 the oldest one will be handed the permit and resumed.
118
119 The sequencing of resumption is determined by the Semaphore
120 constructor flag 'sync':
121
122 If sync is false, the pending stratum will be resumed
66c2bc4 @afri module browser rewrite
afri authored
123 *after* [::Semaphore::release] returns.
70d98a4 @afri Big restructuring of oni-apollo.js. All modules are now external, oni…
afri authored
124
125 If sync is true, the pending stratum will be resumed *before*
66c2bc4 @afri module browser rewrite
afri authored
126 [::Semaphore::release] returns.
ca33263 @afri apollo 0.8.0 code
afri authored
127
66c2bc4 @afri module browser rewrite
afri authored
128 Calls to [::Semaphore::release] are usually
129 paired with calls to [::Semaphore::acquire].
130 See documentation for [::Semaphore::acquire]
ca33263 @afri apollo 0.8.0 code
afri authored
131 for an alternative to doing this manually.
132 */
133 release : function() {
43b3da3 @afri New 'spawn' operator
afri authored
134 spawn ((this.sync ? null : hold(0)), ++this.permits,
135 (this.queue.length ? this.queue.shift()() : null))
70d98a4 @afri Big restructuring of oni-apollo.js. All modules are now external, oni…
afri authored
136 },
b8ce726 @afri Semaphore.synchronize
afri authored
137
138 /**
139 @function Semaphore.synchronize
140 @altsyntax semaphore.synchronize { || ... some code ... }
141 @summary Acquire permit, execute function, and release permit.
142 @param {Function} [f] Argument-less function or block lambda to execute
143 @desc
144 `f` will be executed in a `try/finally` construct after the
145 permit has been acquired. The permit will be released in
146 the `finally` clause, i.e. it is guaranteed to to be released
147 even if `f` throws an exception or is cancelled.
148
149 [::Semaphore::synchronize] is intended to be used with paren-free
150 block lambda call syntax:
151
152 S.synchronize { || ... some code ... }
153 */
154 synchronize : function(f) {
155 this.acquire();
156 try {
157 f();
158 }
159 finally {
160 this.release();
161 }
162 }
ca33263 @afri apollo 0.8.0 code
afri authored
163 };
164
967b349 @gfxmonk added Event class to cutil module
gfxmonk authored
165
96fde7f @gfxmonk split cutil.Event into Event and Condition objects
gfxmonk authored
166 // TODO: pause / resume, in line with node events?
167 // TODO: wrap node's EventEmitters to provide the same API? e.g
168 // var dataEvent = new NodeEvents.Event(someEventEmitter, 'data');
967b349 @gfxmonk added Event class to cutil module
gfxmonk authored
169 /**
170 @class Event
96fde7f @gfxmonk split cutil.Event into Event and Condition objects
gfxmonk authored
171 @summary An event that can be waited upon and emitted multiple times.
967b349 @gfxmonk added Event class to cutil module
gfxmonk authored
172 @function Event
173 */
174 var Event = exports.Event = function Event() {
175 this.waiting = [];
176 };
177
178 /**
179 @function Event.wait
96fde7f @gfxmonk split cutil.Event into Event and Condition objects
gfxmonk authored
180 @summary Block until this event is next emitted, and return the emitted value (if given).
967b349 @gfxmonk added Event class to cutil module
gfxmonk authored
181 */
182 Event.prototype.wait = function wait() {
b863ccf @gfxmonk cutil.Event: resume waiting strata after a hold(0) so that the setter…
gfxmonk authored
183 var result = this.value;
cbdcee5 @gfxmonk added the ability for an Event to have an associated value
gfxmonk authored
184 if (!this.isSet) {
b863ccf @gfxmonk cutil.Event: resume waiting strata after a hold(0) so that the setter…
gfxmonk authored
185 waitfor(result) {
cbdcee5 @gfxmonk added the ability for an Event to have an associated value
gfxmonk authored
186 this.waiting.push(resume);
187 } retract {
b863ccf @gfxmonk cutil.Event: resume waiting strata after a hold(0) so that the setter…
gfxmonk authored
188 coll.remove(this.waiting, resume, null);
cbdcee5 @gfxmonk added the ability for an Event to have an associated value
gfxmonk authored
189 }
967b349 @gfxmonk added Event class to cutil module
gfxmonk authored
190 }
b863ccf @gfxmonk cutil.Event: resume waiting strata after a hold(0) so that the setter…
gfxmonk authored
191 return result;
967b349 @gfxmonk added Event class to cutil module
gfxmonk authored
192 };
193
194 /**
96fde7f @gfxmonk split cutil.Event into Event and Condition objects
gfxmonk authored
195 @function Event.emit
196 @param {optional Object} [value]
197 @summary Emit event with optional `value`
198 @desc
199 Resumes all strata that are waiting on this event object.
200
201 If `val` is provided, it will be the return value of all
202 outstanding `wait()` calls.
203 */
204 Event.prototype.emit = function emit(value) {
205 if(this.waiting.length == 0) return;
206 var waiting = this.waiting;
207 this.waiting = [];
208 spawn(coll.par.each(waiting, function(resume) { resume(value); }));
209 };
210
211
212 /**
213 @class Condition
214 @summary A single condition value that can be waited upon, set and cleared.
215 @function Condition
e21376d @afri more work on new module browser
afri authored
216
96fde7f @gfxmonk split cutil.Event into Event and Condition objects
gfxmonk authored
217 @variable Condition.isSet
218 @summary (Boolean) whether the condition is currently set
219 @variable Condition.value
220 @summary the currently set value, or `undefined` if the condition is not set
221 */
222 var Condition = exports.Condition = function Condition() {
223 this._ev = new Event();
224 this.clear();
225 };
226
227 /**
228 @function Condition.wait
229 @summary Block until this condition is set, and return the condition's `value`.
230 @desc
231 If the condition has already been set, this function returns immediately.
232 */
233 Condition.prototype.wait = function wait() {
234 if (!this.isSet) {
235 this.value = this._ev.wait();
236 }
237 return this.value;
238 };
239
240 /**
241 @function Condition.set
8c32449 @gfxmonk minor documentation fixes
gfxmonk authored
242 @param {optional Object} [value] the value to set
96fde7f @gfxmonk split cutil.Event into Event and Condition objects
gfxmonk authored
243 @summary Trigger (set) this condition
967b349 @gfxmonk added Event class to cutil module
gfxmonk authored
244 @desc
96fde7f @gfxmonk split cutil.Event into Event and Condition objects
gfxmonk authored
245 Does nothing if this condition is already set. Otherwise, this will
246 resume all strata that are waiting on this condition object.
cbdcee5 @gfxmonk added the ability for an Event to have an associated value
gfxmonk authored
247
96fde7f @gfxmonk split cutil.Event into Event and Condition objects
gfxmonk authored
248 If `val` is provided, it will become this condition's value (and
cbdcee5 @gfxmonk added the ability for an Event to have an associated value
gfxmonk authored
249 will be the return value of all outstanding `wait()` calls).
967b349 @gfxmonk added Event class to cutil module
gfxmonk authored
250 */
96fde7f @gfxmonk split cutil.Event into Event and Condition objects
gfxmonk authored
251 Condition.prototype.set = function set(value) {
967b349 @gfxmonk added Event class to cutil module
gfxmonk authored
252 if(this.isSet) return; // noop
253 this.isSet = true;
cbdcee5 @gfxmonk added the ability for an Event to have an associated value
gfxmonk authored
254 this.value = value;
96fde7f @gfxmonk split cutil.Event into Event and Condition objects
gfxmonk authored
255 this._ev.emit(value);
967b349 @gfxmonk added Event class to cutil module
gfxmonk authored
256 };
257
258 /**
96fde7f @gfxmonk split cutil.Event into Event and Condition objects
gfxmonk authored
259 @function Condition.clear
260 @summary Un-set (clear) this condition
967b349 @gfxmonk added Event class to cutil module
gfxmonk authored
261 @desc
96fde7f @gfxmonk split cutil.Event into Event and Condition objects
gfxmonk authored
262 Once cleared, the condition can be waited upon and triggered again with
967b349 @gfxmonk added Event class to cutil module
gfxmonk authored
263 `wait` and `set`.
264 */
96fde7f @gfxmonk split cutil.Event into Event and Condition objects
gfxmonk authored
265 Condition.prototype.clear = function clear() {
967b349 @gfxmonk added Event class to cutil module
gfxmonk authored
266 this.isSet = false;
cbdcee5 @gfxmonk added the ability for an Event to have an associated value
gfxmonk authored
267 this.value = undefined;
967b349 @gfxmonk added Event class to cutil module
gfxmonk authored
268 };
269
96fde7f @gfxmonk split cutil.Event into Event and Condition objects
gfxmonk authored
270
ca33263 @afri apollo 0.8.0 code
afri authored
271 /**
272 @function makeBoundedFunction
273 @summary A wrapper for limiting the number of concurrent executions of a function.
274 @return {Function} The wrapped function.
275 @param {Function} [f] The function to wrap.
276 @param {Integer} [max_concurrent_calls] The maximum number of concurrent executions to allow for 'f'.
277 */
278 exports.makeBoundedFunction = function(f, max_concurrent_calls) {
279 var permits = new Semaphore(max_concurrent_calls);
280 return function() {
281 using (permits.acquire())
282 return f.apply(this, arguments);
283 }
284 };
285
286 /**
f4bdb00 @afri Add cutil.makeRateLimitedFunction
afri authored
287 @function makeRateLimitedFunction
288 @summary A wrapper for limiting the rate at which a function can be called.
289 @return {Function} The wrapped function.
290 @param {Function} [f] The function to wrap.
291 @param {Integer} [max_cps] The maximum number of calls per seconds allowed for 'f'.
292 */
293 exports.makeRateLimitedFunction = function(f, max_cps) {
294 var min_elapsed = 1000/max_cps;
295 var last_call;
296 return exports.makeBoundedFunction(
297 function() {
298 if (last_call) {
299 var elapsed = (new Date()) - last_call;
300 if (elapsed < min_elapsed)
301 hold(min_elapsed - elapsed);
302 }
303 last_call = new Date();
304 return f.apply(this, arguments);
305 }, 1);
306 };
307
70d98a4 @afri Big restructuring of oni-apollo.js. All modules are now external, oni…
afri authored
308 /**
309 @function makeExclusiveFunction
310 @summary A wrapper for limiting the number of concurrent executions of a function to one.
311 Instead of potentially waiting for the previous execution to end, like makeBoundedFunction, it will cancel it.
312 @return {Function} The wrapped function.
313 @param {Function} [f] The function to wrap.
314 */
315 exports.makeExclusiveFunction = function(f) {
316 var executing = false, cancel;
317 return function() {
318 if (executing) cancel();
319 waitfor {
320 executing = true;
321 return f.apply(this, arguments);
322 }
323 or {
324 waitfor() {
325 cancel = resume;
326 }
327 }
328 finally {
329 executing = false;
330 }
331 }
332 }
333
341635d @afri cutil.makeDeferredFunction
afri authored
334 /**
335 @function makeDeferredFunction
336 @summary A wrapper for implementing the 'deferred pattern' on a function (see
337 [ECMAScript docs](http://wiki.ecmascript.org/doku.php?id=strawman:deferred_functions#deferred_pattern)).
338 @param {Function} [f] The function to wrap.
339 @return {Function} The wrapped function.
340 @desc
341 When the wrapped function is called, it returns a 'deferred object' which
66c2bc4 @afri module browser rewrite
afri authored
342 implements the methods `then` and `cancel`, as described in
341635d @afri cutil.makeDeferredFunction
afri authored
343 [ECMAScript docs](http://wiki.ecmascript.org/doku.php?id=strawman:deferred_functions#deferred_pattern). With these methods, plain JS code can be made to wait for
344 for the execution of asynchronous SJS code.
345 */
346 exports.makeDeferredFunction = function(f) {
347 return function() {
348 var stratum = spawn f.apply(this, arguments);
349 var deferred = {
350 then : function(callback, errback) {
351 spawn (function() {
352 try { callback(stratum.waitforValue()); }
353 catch (e) { if (errback) errback(e); }
354 })();
355 return deferred;
356 },
357 cancel : function() {
358 stratum.abort();
359 }
360 };
361 return deferred;
362 }
363 };
70d98a4 @afri Big restructuring of oni-apollo.js. All modules are now external, oni…
afri authored
364
4333136 @afri Add cutil.makeMemoizedFunction. Move waitforFirst/waitforAll to colle…
afri authored
365 /**
366 @function makeMemoizedFunction
367 @summary A wrapper for implementing a memoized version of a function.
368 @param {Function} [f] The function to wrap.
12773b3 @gfxmonk implemented caching for github: requires
gfxmonk authored
369 @param {optional Function} [key] The key function to use.
4333136 @afri Add cutil.makeMemoizedFunction. Move waitforFirst/waitforAll to colle…
afri authored
370 @return {Function} The wrapped function.
371 @desc
372 The wrapped function `g = makeMemoizedFunction(f)` stores values that have
12773b3 @gfxmonk implemented caching for github: requires
gfxmonk authored
373 been previously computed by `f` in the hash `g.db`, indexed by key.
374 If `g` is called multiple times with the same argument `X`, only the
4333136 @afri Add cutil.makeMemoizedFunction. Move waitforFirst/waitforAll to colle…
afri authored
375 first invocation will call `f(X)` and store the resulting value under
376 `g.db[X]`. Subsequent invocations to `g(X)` will read the value for `X` from
377 `g.db[X]`.
378
12773b3 @gfxmonk implemented caching for github: requires
gfxmonk authored
379 If `keyfn` is provided, it is called with the same arguments as the function
380 itself, and its return value becomes the key for this call. If `keyfn` is
381 omitted, the first argument to the function is used as the key.
382
ee9b9ab @afri docs
afri authored
383 It is safe to call `g` concurrently from multiple strata:
4333136 @afri Add cutil.makeMemoizedFunction. Move waitforFirst/waitforAll to colle…
afri authored
384 If a call `g(X)` is already in progress (blocked in `f(X)`), while
385 another call `g(X)` is being made, the second (and any subsequent) call
386 will not cause `f(X)` to be called again. Instead, these subsequent
387 calls will wait for the first invocation of `f(X)`.
388
389 `g` implements the following retraction semantics: A pending invocation of
390 `f(X)` will be aborted if and only if every `g(X)` call waiting for
391 `f(X)` to finish has been aborted (i.e. noone is interested in the value
392 for `X` at the moment).
393 */
12773b3 @gfxmonk implemented caching for github: requires
gfxmonk authored
394 exports.makeMemoizedFunction = sys.makeMemoizedFunction;
f4bdb00 @afri Add cutil.makeRateLimitedFunction
afri authored
395
396 /**
ca33263 @afri apollo 0.8.0 code
afri authored
397 @class Queue
398
399 @function Queue
400 @summary Constructor for a bounded FIFO queue datastructure.
401 @param {Integer} [capacity] Maximum number of items to which the queue will
402 be allowed to grow.
66c2bc4 @afri module browser rewrite
afri authored
403 @param {optional Boolean} [sync=false] Whether or not this queue uses synchronous semaphores (see [::Semaphore]).
ca33263 @afri apollo 0.8.0 code
afri authored
404 */
70d98a4 @afri Big restructuring of oni-apollo.js. All modules are now external, oni…
afri authored
405 function Queue(capacity, sync) {
ca33263 @afri apollo 0.8.0 code
afri authored
406 this.items = [];
70d98a4 @afri Big restructuring of oni-apollo.js. All modules are now external, oni…
afri authored
407 this.S_nonfull = new Semaphore(capacity, sync);
408 this.S_nonempty = new Semaphore(0, sync);
ca33263 @afri apollo 0.8.0 code
afri authored
409 }
410 exports.Queue = Queue;
411 Queue.prototype = {
412 /**
413 @function Queue.count
414 @summary Returns current number of elements in the queue.
415 @return {Integer}
416 */
417 count: function() { return this.items.length; },
418
419 /**
420 @function Queue.put
421 @summary Put an item into the queue; blocks if the queue has reached
422 its capacity. Safe to be called from multiple strata concurrently.
423 @param {anything} [item] Item to put into the queue.
424 */
425 put: function(item) {
426 this.S_nonfull.acquire();
427 this.items.push(item);
428 this.S_nonempty.release();
429 },
430
431 /**
432 @function Queue.get
433 @summary Get an item from the queue; blocks if the queue is empty.
434 Safe to be called from multiple strata concurrently.
435 @return {item} Item retrieved from front of queue.
436 */
437 get: function() {
438 this.S_nonempty.acquire();
439 var item = this.items.shift();
440 this.S_nonfull.release();
441 return item;
442 }
443 };
4333136 @afri Add cutil.makeMemoizedFunction. Move waitforFirst/waitforAll to colle…
afri authored
444
Something went wrong with that request. Please try again.