258844 - Continuation support in interpreter

Status: RESOLVED FIXED

(Rhino Graveyard :: Core, enhancement)

Description

[Igor Bukanov]

Since it turned out that the interpreter implementing calls to interpreted
function and scripts without using Java stack does not add any overhead (see bug
256339), it should be possible to add the continuation support to the
interpreter without slowing the scripts that do not use it.

The continuation support should provide the same level of functionality that 
Christopher Oliver patch against Rhino 1.5R4_pre brought so Cocoon
http://cocoon.apache.org/ can use the new version without much efforts.

Comment 1

[Igor Bukanov]

Attachment: Initial patch for experimentation

The initial path provides something to experiment with and includes:

1. Continuation object that is available for scripts if 
Context.hasFeature(Context.FEATURE_INTERPRETER_CONTINUATIONS) returns true.

2. Modifications to shell that adds -continuations flag to enable the feature
and choose interpreter mode. I also added support for "-opt -2" to mean
"-continuations".

3. Interpreter changes to use "new Continuation()" (or just "Continuation()")
to capture continuation. As with Christopher Oliver's patch the continuation
capture is lightweight and use lazy state coping but the implementation is much
simpler. The continuation share explicitly share vars but not internal locals
or stack.

4. Interpreter changes to restore the continuation. As with Christopher
Oliver's patch the control effectively returned to the place that captured
continuation and then "return result" is executed. The control transfer
respects finally blocks and executes all of them that are found during stack
unwind. The implementation allows for finally blocks during continuation
restore to throw exceptions or even execute continuation capture/restore with
defined behavior.

5. Bugs.


Thinks to do:

1. The patch does not contain any support for special catch
(break|continue|return) statements since support for finally makes catch
(break|return) unnecessary and for now catch (continue) has to use workaround.
But it would be nice to have some way to do re-initialization cleared by
finally when restoring continuation state.

2. The patch do not have any support for interpretation across
Function.apply/call or across veal. 

3. There is no Java APO to restart continuation from Continuation object.

Comment 2

[Igor Bukanov]

Attachment: Test to play with

To use the test -continuations should be passed to Rhino shell

Comment 3

[Igor Bukanov]

http://www.mir2.org/igor/rhino/ contains prebuilt rhino distro with the patch
applied.

Comment 4

[Igor Bukanov]

Attachment: Update of the initial patch to reflect CVS changes

I committed few cleanups useful on their own from the patch to CVS tip to
remove changes unrelated to continuation support from the patch

Comment 5

[Igor Bukanov]

Attachment: Patch update with debugger changes

The patch update includes changes to the debugger to allow to use debug GUI to
debug continuation scripts.

To test it, pass "-continuations" option to the debugger when invoking it:

java -classpath js.jar \
    org.mozilla.javascript.tools.debugger.Main -continuations

Comment 6

[Igor Bukanov]

Attachment: test case to verify finally behavior

Comment 7

[Igor Bukanov]

Attachment: Update to allow external continuation restart

The patch update that allows to call stored Continuation from Java application
to restore its execution. For example, in Java one can use the following code
to check that "Object value" is continuation and restart it passing the string
"Hello" to the restoration point: 

if (value instanceof Function) {
	Function f = (Function)value;
	if ("Continuation".equals(f.getClassName())) {
		f.call(cx, scope, null, new Object[] { "Hello" });
	}
}

Note that the valid scope has to be passed to f.call as it is uses to
initialize the execution top scope.

Comment 8

[Igor Bukanov]

Note on Context.FEATURE_INTERPRETER_CONTINUATIONS:

Currently the patch uses the feature only to initialize "Continuation" object
during the initialization of the standard host objects in
Context.initStandardObjects(). It means that the feature should be set before
any calls to Context.initStandardObjects(). The simplest way to do it is to
define ContextFactory like in:

class MyFactory extends ContextFactory
{
    public boolean hasFeature(Context cx, int featureIndex)
    {
        // Turn on maximim compatibility with MSIE scripts
        switch (featureIndex) {
            case Context.FEATURE_INTERPRETER_CONTINUATIONS:
                return true;
        }
        return super.hasFeature(cx, featureIndex);
    }
}


and then set MyFactory as the global factory before any calls to
Context.initStandardObjects, perhaps in some static block:

     static {
         // Initialize GlobalFactory with custom factory
         ContextFactory.initGlobal(new MyFactory());
     }

Comment 9

[Igor Bukanov]

Attachment: Update to sync with CVS tip

Comment 10

[Igor Bukanov]

Attachment: Update with cheap restart

The patch changes continuation capture/restore logic to avoid calls frame
duplication on stack rewind. The implementation follows implementation paper of
SISC, http://sisc.sourceforge.net/sisc.ps.gz and during capture simply marks
all the necessary stack frames as frozen. Then only when the frame is about to
be used for script execution  it is cloned. In this way during rewind it is
necessary to clone only the last frame that gets control.

In this way captured continuations can be used for multiple freeze/restore and
that would be cheap since in case of no finally frame would only be copied only
on normal return to frozen frame.

Comment 11

[Igor Bukanov]

I updated http://www.mir2.org/igor/rhino/ with rhino build using the patch from
attachment 158864 [details] [diff] [review]

Comment 12

[Attila Szegedi]

One "minor" thing: make Interpreter.CallFrame implement Serializable, otherwise 
the continuations won't be serializable.

Comment 13

[Attila Szegedi]

Another minor thing: if FEATURE_INTERPRETER_CONTINUATIONS is on, make sure 
ScriptableOutputStream excludes "Continuation" and "Continuation.prototype" in 
excludeStandardObjectNames()

Comment 14

[Attila Szegedi]

Attachment: Finally not being respected

I still see that a "finally" block enclosing continuation capture is not being
respected. If you try the attached script "Finally not being respected" you'll
see what I mean. Of course, if it'd make implementation more complex or have
higher runtime overhead, then we might as well document this behavior as a
feature.

Comment 15

[Igor Bukanov]

(In reply to comment #14)
> Created an attachment (id=158872)
> Finally not being respected
> 
> I still see that a "finally" block enclosing continuation capture is not being
> respected. If you try the attached script "Finally not being respected" you'll
> see what I mean. Of course, if it'd make implementation more complex or have
> higher runtime overhead, then we might as well document this behavior as a
> feature.

This is by design: Continuation capture the state at the point of call to the
current function. Thus on restore the jump will be there, not to the point that
called Continuation. If you change the example to:

function captureContinuation()
{
    return Continuation();
}


var out=java.lang.System.out;
function x()
{
  try
  {
    return captureContinuation();
  }
  finally
  {
     out.println("finally");
  }
}

var cc = x();
out.println(cc);
if(cc instanceof Continuation)
{
  cc("You won't see finally again");
}

 
it should work.

Comment 16

[Igor Bukanov]

Attachment: Update with serialization support

Since CallFrame can store in CallFrame.stack Interpreter.DBL_MARK which is
Object it still would not be serializable even with "implements Serializable".
As a simple fix I changed DBL_MARK to be an instance of UniqueTag to ensure
that deserialization would map the tag back to UniqueTag.DOUBLE_MARK. It has
additional benefit of better debug printouts for DBL_MARK. 

A better solution would be to add custom read/write methods to write only used
data from the stack but due to potential sharing of CallFrame vars arrays it is
not trivial. For now DOUBLE_MARK should be good enough.

Comment 17

[Igor Bukanov]

Attachment: More serialization changes

I made Interpreter.ContinuationJump to implement Serializable since class
instances can be stored in frame locals. 

http://www.mir2.org/igor/rhino/ is updated with binary with this patch

Comment 18

[Attila Szegedi]

Applying the "More serialization changes" patch to CVS HEAD complains about 
already applied patches to

toolsrc/org/mozilla/javascript/tools/debugger/Dim.java
toolsrc/org/mozilla/javascript/tools/debugger/Main.java
toolsrc/org/mozilla/javascript/tools/shell/Global.java
toolsrc/org/mozilla/javascript/tools/shell/Main.java

I guess you have already committed these to CVS...

Comment 19

[Igor Bukanov]

(In reply to comment #18)
> Applying the "More serialization changes" patch to CVS HEAD complains about 
> already applied patches to
> 
> toolsrc/org/mozilla/javascript/tools/debugger/Dim.java
> toolsrc/org/mozilla/javascript/tools/debugger/Main.java
> toolsrc/org/mozilla/javascript/tools/shell/Global.java
> toolsrc/org/mozilla/javascript/tools/shell/Main.java

Are you sure about that? I just checked with CVS tip and the cjanges are not
there. In addition I was able to apply the patch cleanly:

~/w/js/rhino/tip> patch -p1 -i ~/s/cont.diff 
patching file src/org/mozilla/javascript/ContextFactory.java
patching file src/org/mozilla/javascript/Context.java
patching file src/org/mozilla/javascript/Continuation.java
patching file src/org/mozilla/javascript/Interpreter.java
patching file src/org/mozilla/javascript/ScriptRuntime.java
patching file src/org/mozilla/javascript/serialize/ScriptableOutputStream.java
patching file src/org/mozilla/javascript/UniqueTag.java
patching file toolsrc/org/mozilla/javascript/tools/debugger/Dim.java
patching file toolsrc/org/mozilla/javascript/tools/debugger/Main.java
patching file toolsrc/org/mozilla/javascript/tools/shell/Global.java
patching file toolsrc/org/mozilla/javascript/tools/shell/Main.java

Comment 20

[Igor Bukanov]

Attachment: Update to reflect CVS changes

I committed UniqueTag.DOUBLE_MARK and few debugger/shell changes from the patch
to Rhino CVS since they are useful on their own. So yo test the patch either
apply it to the latest CVS tip or use http://www.mir2.org/igor/rhino/

Comment 21

[Igor Bukanov]

I committed the last patch to Rhino CVS. I will keep the bug open until some
documentation would be written. 

On the otehr to imlemement possible sysntax sugar or to allow for continuations
to cross eval() and Function.prototype.(apply|call)() boundaries a separated
bugs should be filed.

Comment 22

[Attila Szegedi]

(In reply to comment #21)
> I committed the last patch to Rhino CVS. 

Great news. Thanks for all the work on it, Igor! I'm constantly testing it 
against a prototype system I have here that I have built around continuation-
supporting Rhino, and so far everything is peachy (altough I must admit I don't 
use more advanced stuff like multiple restarts, or restarting a continuation 
from inside a script).

Comment 23

[Igor Bukanov]

Attachment: Continuations by default

The patch enables support for Continuation object in the interpreter by default
and removes Context.FEATURE_INTERPRETER_CONTINUATIONS since the testing shows
that it works OK. If necessary, the application can disable continuations
support by removing Continuation from the scope after calling
Context.initStandardObjects()

In addition patch allows to specify -2 which is turned into -1 for
compatibility with the original Rhino+Continuations fork.

Comment 24

[Igor Bukanov]

I committed the last patch

Comment 25

[Attila Szegedi]

Ok, here's a problem: I invoke call() on a Continuation object from Java in a 
freshly created context to restart a continuation that was previously serialized 
in another JVM and now deserialized. I receive this:

java.lang.NullPointerException
	at org.mozilla.javascript.Interpreter$ContinuationJump.<init>(Interpreter.java:
291)
	at org.mozilla.javascript.Interpreter.restartContinuation(Interpreter.java:
2190)
	at org.mozilla.javascript.Continuation.call(Continuation.java:63)
	at org.mozilla.javascript.ContextFactory.doTopCall(ContextFactory.java:290)
	at org.mozilla.javascript.ScriptRuntime.doTopCall(ScriptRuntime.java:2780)
	at org.mozilla.javascript.Interpreter.restartContinuation(Interpreter.java:
2174)
	at org.mozilla.javascript.Continuation.call(Continuation.java:63)
...

Note that there are two invocations of Interpreter.restartContinuation on the 
stack after I call Continuation.call. At first glance, it seems that the problem 
is that null is being passed as the "CallFrame current" argument of the 
ContinuationJump constructor in Interpreter.java:2190. It is then assigned to 
the local variable "chain2" in the said constructor (line 287), and a little bit 
later dereferenced ("chain2.frameIndex", line 291).

Is it okay at all to restart a continuation from Java code using call() on 
Continuation?

Comment 26

[Igor Bukanov]

Attachment: Fix for the problem from the above comment

Comment 27

[Igor Bukanov]

(In reply to comment #25)
> Is it okay at all to restart a continuation from Java code using call() on 
> Continuation?

Yes, this is how it supposes to work. 

Comment 28

[Igor Bukanov]

I commited the fix for comment 25

Comment 29

[Attila Szegedi]

Thanks, works like charm.

Comment 30

[Attila Szegedi]

Here's a curious problem that we're seeing lately on continuation restarts:

java.lang.ArrayIndexOutOfBoundsException: -1
          at org.mozilla.javascript.Interpreter.interpret(Interpreter.java:2942)
          at org.mozilla.javascript.Interpreter.restartContinuation(Interpreter.
java:2196)
          at org.mozilla.javascript.continuations.Continuation.
call(Continuation.java:75)
          at org.mozilla.javascript.ContextFactory.doTopCall(ContextFactory.
java:301)
          ...

I've tried figuring out how could it happen, but to no avail. Do you have any 
idea? I'm sorry I can't provide you with more specific information at the moment 
- if you need additional information, please ask and I'll see what can I do. It 
happens in a rather big environment, and so far I was unfortunately not 
successful in reducing it into a reproducible testcase...

Comment 31

[Igor Bukanov]

(In reply to comment #30)
> Here's a curious problem that we're seeing lately on continuation restarts:
> 
> java.lang.ArrayIndexOutOfBoundsException: -1
>           at org.mozilla.javascript.Interpreter.interpret(Interpreter.java:2942)
...
> 
> I've tried figuring out how could it happen, but to no avail. Do you have any 
> idea? 

It indicates that stack tracking code in Interpreter.interpret is wrong
somewhere. To track that down try to do the following:

1. Add printout like the following before the line 2942:
if (stackTop < 0) {
System.out.println("BAD STACK!!!");
System.out.println("STACK CONTENT:");
for (int ii = 0; ii != stack.length; ++ii) {
  System.out.println("stack["+ii+"]="+stack[ii]);
}
for (int ii = 0; ii != stack.length; ++ii) {
  System.out.println("stack["+ii+"]="+stack[ii]);
}
System.out.println("Line: "+getIndex(iCode, frame.pcSourceLineStart));
System.out.println("Source: "+idata.itsSourceFile);
}

Then check the script source before the line: is it close to continuation
capture point?

Comment 32

[Attila Szegedi]

Ok, here's a problem: we use continuations to store interpreter state, and also 
use a top-level continuation to stop the interpreter after it captured its 
state. The problem is that whenever we execute the top-level continuation, all 
of the finally blocks get executed, i.e. see this console session:

js> c = new Continuation();
[object Continuation]
js> try { c(); } finally { java.lang.System.out.println("x"); }
x

This is rather undesirable for us - we don't want to have finally blocks 
executed when we terminate the interpreter using the top-level continuation. It 
is also arguable whether they should execute in the calling code whenever a 
continuation is resumed by being called. Is this a feature or a bug? (I can not 
decide...)

Comment 33

[Igor Bukanov]

(In reply to comment #32)
> This is rather undesirable for us - we don't want to have finally blocks 
> executed when we terminate the interpreter using the top-level continuation. It 
> is also arguable whether they should execute in the calling code whenever a 
> continuation is resumed by being called. Is this a feature or a bug? (I can not 
> decide...)

This is the feature. Continations are by design very similar to exceptions
except they can in addition to unwinding stack also rewind it. So continuations
has to execute finally blocks. Otherwise when exactly finally block should be
called given that continuations can restored multiple times? 

During initial work on continuations I though of adding "initially" block like in:

try {
  main_code
} initially {
  init_code
} finally {
  clenup_code
}

which would execute init_code whenever the control reaches main_code either
through normal flow or via continuation jump. Thus one can write:

try {
  use_db_connection ane jump out_in through continuations
} initially {
  db_connection = create_db_connection();
} finally {
  db_connection.close();
}

But that turned out to be extremely complex to implement correctly. In addition
there is a simple workaround for that like in:

db_connection = create_db_connection();
try {
  ...
  // after possible continuation control transfer
  if (db_connection == null) {
    db_connection = create_db_connection();
  }

  use_db_connection ane jump out_in through continuations
} finally {
  db_connection.close();
  db_connection = null;
}

Now if you need full freeze/restore, then it is NOT continuations and can be
implemented on the base of continuation mashinery pretty easily via special
marker function. Then your native code would have to implement its own
finalization, but that is a different story and bug.

Comment 34

[Igor Bukanov]

(In reply to comment #33)
> (In reply to comment #32)

One more thing: the test case from attachment 158640 [details] shows the intended behavior
of continuations which is in this case to print:

finally
result=1
i=1
B Restore
finally
result=1
i=2

Comment 35

[Igor Bukanov]

Marking as fixed: new issues with continuations should be reported as separated bugs