continuation.js - npm Package Compare versions

Comparing version 0.1.1 to 0.2.0

package.json

 {
   "name": "continuation.js",
   "description": "A module for tail call optimization by Continuation Passing Style (CPS) transformation with trampoline technique for Node.js",
-  "version": "0.1.1",
+  "version": "0.2.0",
   "author": "Daishi Kato <[e-mail]>",
@@ -25,3 +25,3 @@ "dependencies": {
     "cps",
-    "tail calls",
+    "tail-call",
     "tco",
@@ -28,0 +28,0 @@ "compiler",

README.md

@@ -138,19 +138,18 @@ continuation.js
 |-----------------|---------------|-----------------|-----------|
-| Richards        | 370 ops/sec   | 16.90 ops/sec   | No        |
-| DeltaBlue       | 178 ops/sec   | 6.24 ops/sec    | No        |
-| Encrypt         | 171 ops/sec   | 79.93 ops/sec   | No        |
-| Decrypt         | 9.23 ops/sec  | 3.65 ops/sec    | No        |
-| RayTrace        | 19.82 ops/sec | 2.23 ops/sec    | No        |
-| Earley          | 268 ops/sec   | 20.77 ops/sec   | No        |
-| Boyer           | 19.01 ops/sec | 2.14 ops/sec    | No        |
-| RegExp          | 7.20 ops/sec  | 5.00 ops/sec    | No        |
-| Splay           | 116 ops/sec   | 69.90 ops/sec   | No        |
-| NavierStokes    | 2.57 ops/sec  | 2.43 ops/sec    | No        |
-| PdfJS           | 2.67 ops/sec  | 2.49 ops/sec    | No        |
-| Gameboy         | 0.99 ops/sec  | 0.28 ops/sec    | No        |
-| CodeLoadClosure | 343 ops/sec   | 392 ops/sec     | Yes       |
-| CodeLoadJQuery  | 10.23 ops/sec | 10.36 ops/sec   | Yes       |
-| Box2D           | 2.28 ops/sec  | 2.48 ops/sec    | Yes       |
+| Richards        | 324 ops/sec   | 38.28 ops/sec   | No        |
+| DeltaBlue       | 188 ops/sec   | 12.90 ops/sec   | No        |
+| Encrypt         | 162 ops/sec   | 122 ops/sec     | No        |
+| Decrypt         | 8.62 ops/sec  | 6.86 ops/sec    | No        |
+| RayTrace        | 19.71 ops/sec | 4.10 ops/sec    | No        |
+| Earley          | 278 ops/sec   | 33.91 ops/sec   | No        |
+| Boyer           | 18.19 ops/sec | 1.60 ops/sec    | No        |
+| RegExp          | 7.12 ops/sec  | 5.14 ops/sec    | No        |
+| Splay           | 123 ops/sec   | 75.21 ops/sec   | No        |
+| NavierStokes    | 2.40 ops/sec  | 3.13 ops/sec    | Yes       |
+| PdfJS           | 2.85 ops/sec  | 2.68 ops/sec    | No        |
+| Gameboy         | 0.98 ops/sec  | 0.35 ops/sec    | No        |
+| CodeLoadClosure | 370 ops/sec   | 372 ops/sec     | Yes       |
+| CodeLoadJQuery  | 8.83 ops/sec  | 10.61 ops/sec   | Yes       |
+| Box2D           | 2.33 ops/sec  | 2.54 ops/sec    | Yes       |
 
-
 Limitations
@@ -157,0 +156,0 @@ -----------

src/continuation.js

@@ -65,5 +65,5 @@ /*
 root.ast_prog_header = function() {
-  var code = root.parse("if (typeof CpsFunction === 'undefined') { CpsFunction = function(f, k) { this.f = f; this.k = k; }; } if (typeof CpsContinuation === 'undefined') { CpsContinuation = function(k) { if (k) { this.k = k; } else { this.k = function(r) { return r; }; }}; } if (typeof CpsResult === 'undefined') { CpsResult = function(r) { this.r = r; }; } if (typeof CpsRun === 'undefined') { CpsRun = function(x) { var last_k; while (x instanceof CpsFunction) { last_k = x.k; x = x.f(x.k); } if (x instanceof CpsResult) { return x.r; } else { return last_k.k(x); }}; }");
-  assert.equal(code.type, 'Program');
-  return code.body;
+  var ast = root.parse("if (typeof CpsFunction === 'undefined') { CpsFunction = function(f, k) { this.f = f; this.k = k; }; } if (typeof CpsContinuation === 'undefined') { CpsContinuation = function(k) { if (k) { this.k = k; } else { this.k = function(r) { return r; }; }}; } if (typeof CpsResult === 'undefined') { CpsResult = function(r) { this.r = r; }; } if (typeof CpsRun === 'undefined') { CpsRun = function(x) { var last_k; while (x instanceof CpsFunction) { last_k = x.k; x = x.f(x.k); } if (x instanceof CpsResult) { return x.r; } else { return last_k.k(x); }}; }");
+  assert.equal(ast.type, 'Program');
+  return ast.body;
 };
@@ -83,32 +83,31 @@
   var i_varname = root.generate_new_variable_name('i', exclude_ids);
-  var thisCopy = '';
+  var code = "var " + l_varname + " = arguments.length - 1;";
   if (t_varname) {
-    thisCopy = "var " + t_varname + " = this;";
+    code += "var " + t_varname + " = this;";
   }
-  var argsCopy = '';
   if (a_varname) {
-    argsCopy = "var " + a_varname + " = {}; for(var " + i_varname + " = 0; " + i_varname + " <= " + l_varname + "; " + i_varname + "++) { " + a_varname + "[" + i_varname + "] = arguments[" + i_varname + "]; }" + a_varname + ".length = 1 + " + l_varname + ";" + a_varname + ".callee = arguments.callee;";
+    code += "var " + a_varname + " = {}; for(var " + i_varname + " = 0; " + i_varname + " <= " + l_varname + "; " + i_varname + "++) { " + a_varname + "[" + i_varname + "] = arguments[" + i_varname + "]; }" + a_varname + ".length = 1 + " + l_varname + ";" + a_varname + ".callee = arguments.callee;";
   }
-  var code = root.parse("var " + l_varname + " = arguments.length - 1;" + thisCopy + argsCopy);
-  assert.equal(code.type, 'Program');
-  return code.body;
+  var ast = root.parse(code);
+  assert.equal(ast.type, 'Program');
+  return ast.body;
 };
 
 root.ast_func_wrapper = function(k_varname, l_varname, a_varname, params) {
-  var argsPop = '';
+  var code = "var " + k_varname + " = arguments[" + l_varname + "]; if (" + k_varname + " instanceof CpsContinuation) { ";
   if (a_varname) {
-    argsPop = "delete " + a_varname + "[" + l_varname + "]; " + a_varname + ".length--;";
+    code += "delete " + a_varname + "[" + l_varname + "]; " + a_varname + ".length--;";
   }
-  var fixParams = '';
   if (params.length > 0) {
-    fixParams = 'if (' + l_varname + ' >= ' + params.length + ') {';
+    code += "if (" + l_varname + " >= " + params.length + ") {";
     for (var i = params.length - 1; i >= 0; i--) {
       assert.equal(params[i].type, 'Identifier');
-      fixParams += '} else if (' + l_varname + ' >= ' + i + ') {' + params[i].name + ' = undefined;';
+      code += "} else if (" + l_varname + " >= " + i + ") {" + params[i].name + " = undefined;";
     }
-    fixParams += '}';
+    code += "}";
   }
-  var code = root.parse("var " + k_varname + " = arguments[" + l_varname + "]; if (" + k_varname + " instanceof CpsContinuation) { " + argsPop + fixParams + "}");
-  assert.equal(code.type, 'Program');
-  return code.body;
+  code += "}";
+  var ast = root.parse(code);
+  assert.equal(ast.type, 'Program');
+  return ast.body;
 };
@@ -198,9 +197,9 @@
   var header = root.ast_func_header(l_varname, using_this_var && t_varname, using_arguments && a_varname, exclude_ids);
-  var newbody = root.deep_clone(body.body);
+  var newbody = root.deep_clone(body);
   root.convert_function_call_to_new_cps_call(body.body, exclude_ids);
   var success = root.convert_normal_body_to_cps_body(k_varname, exclude_ids, newbody);
   if (success) {
-    while (newbody.length > 0) {
-      if (newbody[0].type === 'FunctionDeclaration') {
-        newbody.shift();
+    while (newbody.body.length > 0) {
+      if (newbody.body[0].type === 'FunctionDeclaration') {
+        newbody.body.shift();
       } else {
@@ -212,3 +211,3 @@ break;
     assert.ok(wrapper[1].consequent.body.length >= 0);
-    root.push(wrapper[1].consequent.body, newbody);
+    root.push(wrapper[1].consequent.body, newbody.body);
     root.push(wrapper[1].consequent.body, {
@@ -229,26 +228,27 @@ type: 'ReturnStatement',
 
+root.has_side_effect = function(node) {
+  if (!node) {
+    return false;
+  } else if (node.type === 'FunctionExpression') { //not really side-effect
+    return true;
+  } else if (node.type === 'CallExpression') {
+    return true;
+  } else if (node.type === 'UpdateExpression') {
+    return true;
+  } else if (node.type === 'AssignmentExpression') {
+    return true;
+  } else if (node.type === 'NewExpression') {
+    return true;
+  } else if (node instanceof Object) {
+    return _.some(node, root.has_side_effect);
+  } else {
+    return false;
+  }
+};
+
 root.convert_function_call_to_new_cps_call = function(body, exclude_ids) {
-  var has_side_effect = function(node) {
-    if (!node) {
-      return false;
-    } else if (node.type === 'FunctionExpression') { //not really side-effect
-      return true;
-    } else if (node.type === 'CallExpression') {
-      return true;
-    } else if (node.type === 'UpdateExpression') {
-      return true;
-    } else if (node.type === 'AssignmentExpression') {
-      return true;
-    } else if (node.type === 'NewExpression') {
-      return true;
-    } else if (node instanceof Object) {
-      return _.some(node, has_side_effect);
-    } else {
-      return false;
-    }
-  };
   var is_transformable_call = function(node) {
     if (!node.callee) {
       return false;
-    } else if (has_side_effect(node.callee)) {
+    } else if (root.has_side_effect(node.callee)) {
       return false;
@@ -341,31 +341,7 @@ } else if (node.callee.type === 'Identifier' && node.callee.name === 'CpsEnableWrapper') {
 
-root.convert_statements_into_cps = function(k_varname, exclude_ids, statements) {
-  var i = 0;
-  while (i < statements.length) {
-    assert.ok(statements[i].type);
-    assert.equal(statements[i].type.slice(-9), 'Statement');
-    var converted = root.convert_statement_into_cps(k_varname, exclude_ids, statements[i], statements.slice(i + 1));
-    if (converted) {
-      statements.splice(i + 1);
-      statements[i] = {
-        type: 'ReturnStatement',
-        argument: converted
-      };
-      break;
-    }
-  }
-};
-
-root.convert_statement_into_cps = function(k_varname, exlude_ids, statement, rest) {
-  if (statement.type === 'ExpressionStatement') {
-    //TODO
-  } else {
-    return false;
-  }
-};
-
-// only converting obvious tail calls or return calls to cps
+// only converting tail calls
 root.convert_normal_body_to_cps_body = function(k_varname, exclude_ids, body) {
   var create_cps_expression = function(call_expression) {
     var kk_varname = root.generate_new_variable_name('kk', exclude_ids);
+    var call_expression1 = root.deep_clone(call_expression);
     var call_expression2 = root.deep_clone(call_expression);
@@ -399,3 +375,3 @@ call_expression2.arguments.push({
                 computed: false,
-                object: call_expression.callee,
+                object: call_expression1.callee,
                 property: {
@@ -407,3 +383,3 @@ type: 'Identifier',
               consequent: call_expression2,
-              alternate: call_expression
+              alternate: call_expression1
 
@@ -422,75 +398,162 @@ }
   };
-  var walk = function(node, tail) {
-    if (node && (node.type === 'FunctionDeclaration' || node.type === 'FunctionExpression')) {
-      return true;
-    } else if (node && node.type === 'CallExpression' && !(node.callee && node.callee.id && node.callee.id.type === 'Identifier' && node.callee.id.name === 'CpsEnableWrapper')) {
-      return false;
-    } else if (node && node.type === 'ReturnStatement') {
-      if (node.argument && node.argument.type === 'CallExpression' && !(node.argument.callee && node.argument.callee.type === 'FunctionExpression')) {
-        node.argument = create_cps_expression(node.argument);
-        return true;
+
+  var create_cps_result = function(expression) {
+    return {
+      type: 'NewExpression',
+      callee: {
+        type: 'Identifier',
+        name: 'CpsResult'
+      },
+      arguments: [{
+        type: 'CallExpression',
+        callee: {
+          type: 'MemberExpression',
+          computed: false,
+          object: {
+            type: 'Identifier',
+            name: k_varname
+          },
+          property: {
+            type: 'Identifier',
+            name: 'k'
+          }
+        },
+        arguments: [expression || {
+          type: 'Literal',
+          value: null
+        }]
+      }]
+    };
+  };
+
+  var is_callee_cpsenablewrapper = function(node) {
+    return node.callee && node.callee.id && node.callee.id.type === 'Identifier' && node.callee.id.name === 'CpsEnableWrapper';
+  };
+
+  // the walk function below returns the number of CpsFunction transformation.
+  var walk = function(node, tail, wrapped) {
+    var transformed;
+    var i;
+    if (node === undefined || node === null) {
+      return 0;
+
+    } else if (node.type === 'FunctionDeclaration' || node.type === 'FunctionExpression') {
+      return 0;
+
+    } else if (node.type === 'CallExpression') {
+      if (tail && !wrapped && !is_callee_cpsenablewrapper(node) && !root.has_side_effect(node.callee)) {
+        var newnode = create_cps_expression(node);
+        _.each(node, function(value, key) {
+          delete node[key];
+        });
+        _.extend(node, newnode);
+        return 1;
       } else {
-        var success = walk(node.argument);
-        if (success) {
-          node.argument = {
-            type: 'NewExpression',
-            callee: {
-              type: 'Identifier',
-              name: 'CpsResult'
-            },
-            arguments: [{
-              type: 'CallExpression',
-              callee: {
-                type: 'MemberExpression',
-                computed: false,
-                object: {
-                  type: 'Identifier',
-                  name: k_varname
-                },
-                property: {
-                  type: 'Identifier',
-                  name: 'k'
-                }
-              },
-              arguments: [node.argument || {
-                type: 'Literal',
-                value: null
-              }]
-            }]
-          };
-          return true;
-        } else {
-          return false;
-        }
+        return 0;
       }
-    } else if (tail && node && node.type === 'IfStatement') {
-      return walk(node.consequent, tail) && walk(node.alternate, tail);
-    } else if (tail && node && node.type === 'BlockStatement') {
-      return walk(node.body, tail);
-    } else if (tail && Array.isArray(node)) {
-      for (var i = 0; i < node.length - 1; i++) {
-        var result = walk(node[i]);
-        if (!result) {
-          return false;
-        }
+
+    } else if (node.type === 'ConditionalExpression') {
+      return walk(node.test, false, wrapped) + walk(node.consequent, tail, wrapped) + walk(node.alternate, tail, wrapped);
+
+    } else if (node.type === 'SequenceExpression') {
+      transformed = 0;
+      for (i = 0; i < node.expressions.length; i++) {
+        transformed += walk(node.expressions[i], false, wrapped);
       }
-      var lastone = node[node.length - 1];
-      if (lastone && lastone.type === 'ExpressionStatement' && lastone.expression.type === 'CallExpression' && !(lastone.expression.callee && lastone.expression.callee.type === 'FunctionExpression')) {
-        node[node.length - 1] = {
-          type: 'ReturnStatement',
-          argument: create_cps_expression(lastone.expression)
-        };
-        return true;
-      } else {
-        return walk(lastone, tail);
+      return transformed;
+
+    } else if (node.type === 'AssignmentExpression' || node.type === 'BinaryExpression' || node.type === 'UpdateExpression' || node.type === 'MemberExpression' || node.type === 'LogicalExpression' || node.type === 'ArrayExpression' || node.type === 'ObjectExpression' || node.type === 'UnaryExpression' || node.type === 'NewExpression') {
+      return 0;
+
+    } else if (node.type === 'BlockStatement') {
+      transformed = 0;
+      for (i = 0; i < node.body.length; i++) {
+        transformed += walk(node.body[i], (i === node.body.length - 1 ? tail : false), wrapped);
       }
-    } else if (node instanceof Object) {
-      return _.every(node, function(x) {
-        return walk(x);
-      });
+      return transformed;
+
+    } else if (node.type === 'ExpressionStatement') {
+      transformed = walk(node.expression, tail, wrapped);
+      if (transformed) {
+        node.type = 'ReturnStatement';
+        node.argument = node.expression;
+        delete node.expression;
+      }
+      return transformed;
+
+    } else if (node.type === 'DoWhileStatement' || node.type === 'WhileStatement') {
+      return walk(node.body, false, wrapped) + walk(node.test, false, wrapped);
+
+    } else if (node.type === 'ForStatement') {
+      return walk(node.body, false, wrapped) + walk(node.init, false, wrapped) + walk(node.test, false, wrapped) + walk(node.update, false, wrapped);
+
+    } else if (node.type === 'ForInStatement') {
+      return walk(node.body, false, wrapped) + walk(node.left, false, wrapped) + walk(node.right, false, wrapped);
+
+    } else if (node.type === 'IfStatement') {
+      return walk(node.consequent, tail, wrapped) + walk(node.alternate, tail, wrapped);
+
+    } else if (node.type === 'LabeledStatement') {
+      return walk(node.body, tail, wrapped);
+
+    } else if (node.type === 'WithStatement') {
+      return walk(node.body, tail, wrapped) + walk(node.object, false, wrapped);
+
+    } else if (node.type === 'ReturnStatement') {
+      transformed = walk(node.argument, !wrapped, false);
+      if (transformed === 0) {
+        node.argument = create_cps_result(node.argument);
+      }
+      return transformed;
+
+    } else if (node.type === 'TryStatement') {
+      transformed = walk(node.block, tail, true);
+      for (i = 0; i < node.guardedHandlers.length; i++) {
+        transformed += walk(node.guardedHandlers[i].body, tail, true);
+      }
+      for (i = 0; i < node.handlers.length; i++) {
+        transformed += walk(node.handlers[i].body, tail, true);
+      }
+      transformed += walk(node.finalizer, tail, wrapped);
+      return transformed;
+
+    } else if (node.type === 'ThrowStatement') {
+      return walk(node.argument, false, wrapped);
+
+    } else if (node.type === 'SwitchStatement') {
+      transformed = walk(node.discriminant, false, wrapped);
+      for (i = 0; i < node.cases.length; i++) {
+        transformed += walk(node.cases[i], false, wrapped);
+      }
+      return transformed;
+
+    } else if (node.type === 'SwitchCase') {
+      transformed = walk(node.test, false, wrapped);
+      for (i = 0; i < node.consequent.length; i++) {
+        transformed += walk(node.consequent[i], false, wrapped);
+      }
+      return transformed;
+
+    } else if (node.type === 'BreakStatement' || node.type === 'ContinueStatement' || node.type === 'EmptyStatement') {
+      return 0;
+
+    } else if (node.type === 'VariableDeclaration') {
+      transformed = 0;
+      for (i = 0; i < node.declarations.length; i++) {
+        transformed += walk(node.declarations[i].init, false, wrapped);
+      }
+      return transformed;
+
+    } else if (node.type === 'Identifier') {
+      return 0;
+
+    } else if (node.type === 'Literal') {
+      return 0;
+
     } else {
-      return true;
+      console.warn('continuing with unsupported node type: ' + node.type);
+      return 0;
     }
   };
-  return walk(body, true);
+  return walk(body, true, false);
 };
@@ -620,17 +683,20 @@
 
+root.saved_require_js_function = null;
+
 root.enable_on_require = function() {
   var fs = require('fs');
-  require.extensions['.js'] = function(module, filename) {
-    var data = fs.readFileSync(filename, 'utf8');
-    module._compile(root.compile(data), filename);
-  };
+  if (!root.saved_require_js_function) {
+    root.saved_require_js_function = require.extensions['.js'];
+    require.extensions['.js'] = function(module, filename) {
+      var data = fs.readFileSync(filename, 'utf8');
+      module._compile(root.compile(data), filename);
+    };
+  }
 };
 
-//XXX not sure if this is really identical to the original function.
 root.disable_on_require = function() {
-  var fs = require('fs');
-  require.extensions['.js'] = function(module, filename) {
-    var data = fs.readFileSync(filename, 'utf8');
-    module._compile(data, filename);
-  };
+  if (root.saved_require_js_function) {
+    require.extensions['.js'] = root.saved_require_js_function;
+    root.saved_require_js_function = null;
+  }
 };
@@ -637,0 +703,0 @@

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

162234

increased by43.87%

Lines of code

2945

increased by28.27%

Number of low supply chain risk alerts

9

decreased by-25%

Worsened metrics

Number of lines in readme file

167

decreased by-0.6%

No dependency changes