history.js: Add clear-history and clear-form-history commands.
[conkeror.git] / modules / coroutine.js
blob851c49297ecb1d78556d8397d039121f146d4699
1 /**
2  * (C) Copyright 2008, 2014 Jeremy Maitin-Shepard
3  *
4  * Use, modification, and distribution are subject to the terms specified in the
5  * COPYING file.
6 **/
8 /**
9  * Coroutine (i.e. cooperative multithreading) implementation in
10  * JavaScript based on Mozilla JavaScript 1.7 generators.
11  *
12  * This is very similar to the Task mechanism implemented in Task.jsm:
13  * https://developer.mozilla.org/en-US/docs/Mozilla/JavaScript_code_modules/Task.jsm
14  *
15  * Like Task.jsm, Conkeror's coroutines integrate with Promises:
16  * https://developer.mozilla.org/en-US/docs/Mozilla/JavaScript_code_modules/Promise.jsm
17  *
18  * Conkeror uses resource://gre/modules/Promise.jsm if it is available (Gecko >=
19  * 25); otherwise, a copy of Gecko 26 Promise.jsm file in
20  * modules/compat/Promise.jsm is used.
21  *
22  * Before trying to understand this file, first read about generators
23  * as described here:
24  * https://developer.mozilla.org/en/New_in_JavaScript_1.7
25  *
26  * Additionally, here is a document describing another implementation
27  * of coroutines/cooperative multithreading in JavaScript based on
28  * generators that may be of interest:
29  * http://www.neilmix.com/2007/02/07/threading-in-javascript-17/
30  *
31  * === Introduction ===
32  *
33  * For the purposes of Conkeror, a coroutine is a generator function
34  * (i.e. a function that uses the yield keyword) that adheres to
35  * certain practices (described later in this file).
36  *
37  * As described in the "New in JavaScript 1.7" document, although a
38  * generator function `foo' can be invoked using the same syntax as
39  * any other function, i.e.:
40  *
41  *   foo(a,b,c)
42  *
43  * this "function call" merely serves to bind the arguments (including
44  * the special `this' argument) without actually running any of the
45  * code specified in the defintion of foo, and return a special
46  * generator object. The generator object has three methods, `next',
47  * 'send', and 'close', that can be called to actually run code
48  * specified in the definition of the generator function.
49  *
50  * In Conkeror, a `coroutine' refers to a generator function that
51  * adheres to the practices described later in this file. In a
52  * JavaScript program, a coroutine (or any generator function)
53  * unfortunately cannot be distinguished from a normal function
54  * without actually invoking it. A `prepared coroutine' refers to a
55  * generator object obtained from calling a coroutine
56  * function. Generally when using this coroutine library, none of the
57  * methods of these generator objects should be called directly. The
58  * `is_coroutine' function can be used to check whether a given value
59  * is a generator object (not a generator function). This library
60  * generally assumes that any generator objects it is passed are
61  * proper prepared coroutines. If a generator function that does not
62  * adhere to the practices required of a coroutine is used with this
63  * library as a coroutine, undefined (and generally undesirable)
64  * behavior may occur.
65  *
66  * === Requirements for a coroutine ===
67  *
68  * In most ways, a coroutine function can be written like a normal
69  * function. Arbitrary computation can be done, including arbitrary
70  * calls to normal functions, exceptions can be thrown, and exceptions
71  * can be handled using try-catch-finally blocks.
72  *
73  * --- Return values ---
74  *
75  * One of the main differences from a normal function is that the
76  * `return' keyword cannot be used to return a value to the caller
77  * (which is necessarily either another coroutine function, or the
78  * coroutine was itself started in a new "thread" in which case the
79  * return value is ignored). The `return' keyword can still be used to
80  * return `undefined' to the caller. In order to return a value,
81  * though, the special syntax:
82  *
83  *   yield co_return(<expr>);
84  *
85  * must be used in place of the normal syntax:
86  *
87  *   return <expr>;
88  *
89  * --- Invoking another coroutine function synchronously ---
90  *
91  * Another very important operation is calling another coroutine
92  * function synchronously, meaning that control will not return to the
93  * caller (the current coroutine) until the specified coroutine has
94  * either returned or thrown an exception. Conceptually, the specified
95  * coroutine is run in the same "thread" as the current coroutine, as
96  * opposed to being invoked asynchronously, in which case it would be
97  * run in a new "thread". This is done using the syntax:
98  *
99  *   yield <prepared-coroutine-expr>
101  * where <prepared-coroutine-expr> is some expression that evaluates to
102  * a generator object, most typically a direct call to a coroutine
103  * function in the form of
105  *   yield foo(a,b,c)
107  * or
109  *   yield obj.foo(a,b,c)
111  * in the case that "foo" is a coroutine method of some object
112  * `obj'.
114  * If the specified coroutine returns a value normally, the yield
115  * expression evaluates to that value. That is, using the the syntax
117  *   var x = yield foo(a,b,c);
119  * if foo is a coroutine and returns a normal value, that value will
120  * be stored in `x'.
122  * Alternatively, if the specified coroutine throws an exception, the
123  * exception will be propagated out of the yield expression, and can
124  * optionally be handled using a try-catch-finally block. If it is not
125  * handled, it will be propagated to the caller of the current
126  * coroutine in the same way.
128  * Note that it is safe to invoke a normal function using `yield' as
129  * well as if it were a coroutine. That is, the syntax
131  *   yield foo(a,b,c)
133  * can likewise be used if foo is a normal function, and the same
134  * return value and exception propagation semantics
135  * apply. (Technically, what is actually happenining is that if yield
136  * is passed a value that is not a generator object or one of the
137  * several other types of values that are handled specially like the
138  * return value of co_return, it simply returns the value back
139  * untouched to the coroutine function. Thus, if foo is a normal
140  * function and returns a value, the return value is passed to yield,
141  * which immediately passes it back. If it throws an exception, then
142  * due to the normal exception propagation, yield is never even
143  * called.)
145  * --- Integration with Promise API ---
147  * Promises provide a simple, standard interface for asynchronous operations.
148  * Coroutines can wait synchronously for the result of a Promise by using yield:
150  *   yield <promise>
152  * Promises are detected by presence of a `then' member of type function.  If
153  * the Promise is resolved, the yield expression will evaluate to the resolved
154  * value.  Otherwise, if the Promise is rejected, the yield expression will
155  * cause the rejection exception to be thrown.
157  * In effect, a function that starts an asyncronous operation and returns a
158  * Promise can be called synchronously from a coroutine, in the same way that
159  * another coroutine can be called synchronously, by using:
161  *   yield function_that_returns_a_promise()
163  * --- [[deprecated]] Current continutation/"thread" handle ---
165  * Note: This API is deprecated because it is error-prone.  Instead, use the
166  * Promise integration.
168  * The special syntax
170  *   var cc = yield CONTINUATION;
172  * can be used to obtain a special "continuation" object that serves
173  * as a sort of "handle" to the current thread. Note that while in a
174  * single "thread", even if not in the same coroutine function, the
175  * exact same "continuation" object will always be returned.
177  * The continuation object is used in conjuction with another special
178  * operation:
180  *   yield SUSPEND;
182  * This operation suspends execution of the current "thread" until it
183  * is resumed using a reference to the continuation object for the
184  * "thread". There are two ways to resume executation. To resume
185  * execution normally, the syntax:
187  *   cc(value)
189  * or
191  *   cc() (equivalent to cc(undefined))
193  * can be used. This resumes execution and causes the yield SUSPEND
194  * expression to evaluate to the specified value. Alternatively, the
195  * syntax:
197  *   cc.throw(e)
199  * can be used. This causes the specified exception `e' to be thrown
200  * from the yield SUSPEND expression.
202  * It is not valid to use either of these two operations on a
203  * continutation corresponding to a thread that is either currently
204  * running or has already terminated.
206  * Generally, any coroutine function that suspends the current
207  * "thread" should also arrange using some other asynchronous
208  * facility, such as a timer with a callback or an event handler, to
209  * resume the "thread" later. It should also arrange to resume the
210  * "thread" with an exception if an error of some sort occurs in lieu
211  * of simply not resuming the "thread" at all.
213  * It is not technically necessary to resume a "thread" after
214  * suspending it, but it generally should always be done, as otherwise
215  * important error handling code, including code in `finally' blocks,
216  * may not be run.
218  * === Invoking a coroutine asynchronously/spawning a new thread ===
220  * A coroutine function can be called asynchronously from either a
221  * normal function or a coroutine function. Conceptually, this is
222  * equivalent to spawning a new "thread" to run the specified
223  * coroutine function. This operation is done using the spawn
224  * function as follows:
226  *   spawn(<prepared-coroutine-expr>)
228  * or, for example,
230  *   spawn(foo(a,b,c))
232  * or
234  *   spawn(function (){ yield foo(a,b,c); }())
236  * The `spawn' function returns a Promise representing the result of the
237  * asyncronous call.
239  * As a convenience, if the argument to `spawn' is a Promise instead of a
240  * prepared coroutine (i.e. a generator), it is returned as is, such that
241  * spawn can be used transparently with both generator functions and functions
242  * returning Promises.
244  * === Cancelation ===
246  * Conkeror's coroutines support an extension to the Promise API for
247  * cancelation: a Promise may have a `cancel' member of type function, which
248  * attempts to cancel the corresponding asynchronous operation.
250  * The `cancel' function should not make use of the implicit `this' argument.
251  * The `cancel' function takes one optional argument (defaults to
252  * task_canceled()), which specifies the exception with which the Promise should
253  * be rejected if the cancelation is successful.
255  * The `cancel' function is asynchronous and returns without providing any
256  * indication of whether the cancelation was successful.  There is no guarantee
257  * that cancelation will be possible or even successful, for instance the
258  * Promise may have already been resolved or rejected, or the asynchronous
259  * operation may not be in a cancelable state, or the cancelation notification
260  * may be ignored for some reason.  However, if the cancelation is successful,
261  * this should be indicated by rejecting the Promise with the specified
262  * exception.
264  * The helper functions `make_cancelable' and `make_simple_cancelable' are
265  * useful for creating Promises that support the cancelation API.
267  * The Promise returned by `spawn' supports cancelation, and works as follows:
269  * The `cancel' function in the returned Promise marks the "thread" for
270  * cancelation.  While a "thread" is marked for cancelation, any Promise the
271  * thread waits on synchronously (including one in progress when `cancel' is
272  * called) will be immediately canceled if it supports cancelation.  The
273  * "thread" will remain marked for cancelation until one of the cancelation
274  * requests is successful, i.e. one of the canceled Promises is rejected with
275  * the cancelation exception.
276  **/
278 try {
279     Components.utils.import("resource://gre/modules/Promise.jsm");
280 } catch (e) {
281     // Gecko < 25
282     Components.utils.import("chrome://conkeror/content/compat/Promise.jsm");
285 function _return_value (x) {
286     this.value = x;
289 function co_return (x) {
290     return new _return_value(x);
293 const CONTINUATION = { toString: function () "[object CONTINUATION]" };
294 const SUSPEND = { toString: function () "[object SUSPEND]" };
297  * Returns true if the `obj' is a generator object. Returns false
298  * otherwise. It is assumed that only generator objects that are
299  * actually `prepared coroutines' (see above) will be used with this
300  * library.
301  **/
302 function is_coroutine (obj) {
303     return obj != null &&
304         typeof(obj) == "object" &&
305         typeof(obj.next) == "function" &&
306         typeof(obj.send) == "function";
310  * Returns an object that behaves like a Promise but also has a
311  * `cancel` method, which invokes the specified `canceler` function.
312  * The returned object has the specified promise as its prototype.
313  * Note that we have to create a new object to add the `cancel` method
314  * because Promise objects are sealed.
316  * The canceler function must take one argument `e`, a cancelation
317  * exception.  The canceler function should arrange so that the
318  * promise is rejected with `e` if the cancelation is successful.  Any
319  * other result of the promise indicates that the cancelation was not
320  * successfully delivered.  If `e` is undefined, it defaults to
321  * task_canceled().
323  * This protocol is important for coroutines as it makes it possible
324  * to retry delivering the cancelation notification until it is
325  * delivered successfully at least once.
326  **/
327 function make_cancelable (promise, canceler) {
328     return { __proto__: promise,
329              cancel: function (e) {
330                  if (e === undefined)
331                      e = task_canceled();
332                  canceler(e);
333              }
334            };
338  * Returns a Promise that supports cancelation by simply rejecting the specified
339  * `deferred` object with the cancelation exception.
341  * This will likely leave the asynchronous operation running, and a proper
342  * cancelation function that actually stops the asynchronous operation should be
343  * used instead when possible.
344  **/
345 function make_simple_cancelable(deferred) {
346     return make_cancelable(deferred.promise, deferred.reject);
349 function task_canceled () {
350     let e = new Error("task_canceled");
351     e.__proto__ = task_canceled.prototype;
352     return e;
354 task_canceled.prototype.__proto__ = Error.prototype;
356 function _co_impl (f) {
358     // Current generator function currently at top of call stack
359     this.f = f;
360     /**
361      * Stack of (partially-run) prepared coroutines/generator objects
362      * that specifies the call-chain of the current coroutine function
363      * `f'.  Conceptually, `f' is at the top of the stack.
364      **/
365     this.stack = [];
367     /**
368      * Deferred object used to return the result of the coroutine.
369      **/
370     this.deferred = Promise.defer();
372     /**
373      * The current canceler function, used to interrupt this coroutine.  If null, then any cancelation will be delayed.
374      **/
375     this.canceler = null;
377     /**
378      * A pending cancelation.
379      **/
380     this.pending_cancelation = undefined;
383 _co_impl.prototype = {
384     constructor: _co_impl,
385     cancel: function _co_impl__cancel (e) {
386         this.pending_cancelation = e;
387         if (this.canceler) {
388             this.canceler(e);
389         }
390     },
391     send: function _co_impl__send(throw_value, y) {
392         if (this.canceler === undefined) {
393             let e = new Error("Programming error: _co_impl.send called on already-running coroutine.");
394             dump_error(e);
395             throw e;
396         }
397         this.canceler = undefined;
399         // Cancelation has been successfully delivered, remove pending cancelation
400         if (throw_value && this.pending_cancelation == y && y !== undefined)
401             this.pending_cancelation = undefined;
403         while (true) {
404             try { // We must capture any exception thrown by `f'
406                 /**
407                  * If `f' yields again after being resumed, the value
408                  * passed to yield will be stored in `x'.
409                  **/
410                 let x;
411                 if (throw_value) {
412                     throw_value = false;
413                     x = this.f.throw(y); // f.throw returns the next value passed to yield
414                 } else
415                     x = this.f.send(y); // f.send also returns the next value passed to yield
417                 // [[Deprecated]]
418                 // The promise API should be used instead.
419                 if (x === CONTINUATION) {
420                     /**
421                      * The coroutine (`f') asked us to pass it a reference
422                      * to the current continuation.  We don't need to make
423                      * any adjustments to the call stack.
424                      **/
425                     let cc = this.send.bind(this, false);
426                     cc.throw = this.send.bind(this, true);
428                     y = cc;
429                     continue;
430                 }
432                 // [[Deprecated]]
433                 // The promise API should be used instead.
434                 if (x === SUSPEND) {
435                     this.canceler = null;
436                     return;
437                 }
439                 if (is_coroutine(x)) {
440                     // `f' wants to synchronously call the coroutine `x'
441                     this.stack[this.stack.length] = this.f; // push the current coroutine `f' onto the call stack
442                     this.f = x; // make `x' the new top of the stack
443                     y = undefined; // `x` is a new coroutine so we must start it by passing `undefined'
444                     continue;
445                 }
447                 if (x && typeof(x.then) == "function") {
448                     // x is assumed to be a Promise
449                     // Wait for result before returning to caller
450                     if (typeof(x.cancel) == "function") {
451                         if (this.pending_cancelation !== undefined)
452                             x.cancel(this.pending_cancelation);
453                         this.canceler = x.cancel;
454                     } else
455                         this.canceler = null;
457                     x.then(this.send.bind(this, false), this.send.bind(this, true));
458                     return;
459                 }
461                 if (x instanceof _return_value) {
462                     // `f' wants to return a value
463                     this.f.close();
464                     if (this.stack.length == 0) {
465                         /**
466                          * `f' doesn't have a caller, so we resolve
467                          * this.deferred with the return value and
468                          * terminate the coroutine.
469                          */
470                         this.deferred.resolve(x.value);
471                         return;
472                     }
473                     // Pop the caller of `f' off the top of the stack
474                     this.f = this.stack[this.stack.length - 1];
475                     this.stack.length--;
476                     // Pass the return value to the caller, which is now the current coroutine
477                     y = x.value;
478                     continue;
479                 }
481                 /**
482                  * `f' yielded to us a value without any special
483                  * interpretation. Most likely, this is due to `f' calling
484                  * a normal function as if it were a coroutine, in which
485                  * case `x' simply contains the return value of that
486                  * normal function. Just return the value back to `f'.
487                  **/
488                 y = x;
489             } catch (e) {
490                 /**
491                  * `f' threw an exception. If `e' is a StopIteration
492                  * exception, then `f' exited without returning a value
493                  * (equivalent to returning a value of
494                  * `undefined'). Otherwise, `f' threw or propagted a real
495                  * exception.
496                  **/
497                 if (this.stack.length == 0) {
498                     /**
499                      * `f' doesn't have a caller, so we resolve/reject
500                      * this.deferred and terminate the coroutine.
501                      */
502                     if (e instanceof StopIteration)
503                         this.deferred.resolve(undefined);
504                     else
505                         this.deferred.reject(e);
506                     return;
507                 }
508                 // Pop the caller of `f' off the top of the stack
509                 this.f = this.stack[this.stack.length - 1];
510                 this.stack.length--;
511                 if (e instanceof StopIteration)
512                     y = undefined; // propagate a return value of `undefined' to the caller
513                 else {
514                     // propagate the exception to the caller
515                     y = e;
516                     throw_value = true;
517                 }
518             }
519         }
520     },
524  * Runs the specified coroutine asynchronously.  Returns a potentially-cancelable
525  * Promise representing the result.
527  * In the normal case, the `f` is a prepared coroutine (i.e. generator).
529  * If `f` is instead a Promise, it is returned as is, with a no-op canceler.
531  * If `f` is some other value, this returns `Promise.resolve(f)` with a no-op canceler.
532  **/
533 function spawn (f) {
534     if (!is_coroutine(f)) {
535         if (f && typeof(f.then) == "function") {
536             // f is a Promise, just return as is
537             if (typeof(f.cancel) != "function")
538                 return make_cancelable(f, function () {} );
539             return f;
540         }
541         return make_cancelable(Promise.resolve(f), function () {});
542     }
544     let x = new _co_impl(f);
545     x.send(false, undefined); // initialize
547     return make_cancelable(x.deferred.promise, x.cancel.bind(x));
551  * [[deprecated]] Runs the specified coroutine asynchronously.
552  * Returns the corresponding continuation object.
554  * Use `spawn' instead, which returns a Promise rather than a continuation object.
555  **/
556 function co_call (f) {
557     if (!is_coroutine(f))
558         return;
560     let x = new _co_impl(f);
561     x.send(false, undefined); // initialize
563     let cc = x.send.bind(this, false);
564     cc.throw = x.send.bind(this, true);
565     return cc;
568 provide("coroutine");