JS Delta Walkthrough

JS Delta is a delta debugger for JavaScript-processing tools, primarily written by Max Schäfer. Delta debugging helps when your tool is failing on a large input, by finding a smaller input that causes the same kind of failure. It has been widely used since it was first described by Andreas Zeller, e.g., to find small programs that cause failures in C compilers (see Delta and C-Reduce).

The JS Delta documentation actually covers its usage options pretty well, but I thought it would be helpful to see a full walkthrough of the tool in action. This post shows how JS Delta can be used to find bugs in a very simple analysis. You can get all the example code here; just run npm install after cloning.

Our (rather contrived) example analysis aims to do the following: for each occurrence of the form x.f() in an input JavaScript program, it prints X, i.e., the receiver variable in all caps. Here is a buggy first version of the analysis, based on esprima and estraverse:

var esprima = require('esprima'),
    estraverse = require('estraverse'),
    fs = require('fs');
var file = process.argv[2];
var ast = esprima.parse(String(fs.readFileSync(file)));
estraverse.traverse(ast, {
  leave: function (node, parent) {
    if (node.type === 'CallExpression')
      console.log(node.callee.object.name.toUpperCase());
  }
});

The analysis works for a script test.js containing the single statement x.f();:

> node example.js test.js
X

Now, let’s get (too) ambitious and try running the analysis on jQuery:

> node example.js node_modules/jquery/dist/jquery.js

/Users/m.sridharan/git-repos/jsdelta-example/example.js:9
    console.log(node.callee.object.name.toUpperCase());
                                  ^
TypeError: Cannot read property 'name' of undefined
    at Controller.estraverse.traverse.leave (/Users/m.sridharan/git-repos/jsdelta-example/example.js:9:37)
    at Controller.__execute (/Users/m.sridharan/git-repos/jsdelta-example/node_modules/estraverse/estraverse.js:317:31)
    ...

Based on the error message alone, it is a bit hard to diagnose exactly what is wrong with the analysis. Here, we can use JS Delta to obtain a smaller subset of jQuery that still causes the problem. To do so, we run jsdelta as follows:

node node_modules/jsdelta/delta.js --cmd "node example.js" \
--msg "TypeError: Cannot read property 'name' of undefined" \
node_modules/jquery/dist/jquery.js

The --cmd option gives a shell command to run on each reduced input, and the --msg option gives the message that indicates the problem is occurring. The final option is the original failure-inducing input. After working for a few seconds, removing parts of jQuery and checking if the error still occurs, JS Delta outputs the following code in /tmp/tmp0/delta_js_smallest.js:

(function () {
    factory();
}());

This is quite a bit smaller than the original jQuery script! Investigating further, we see that a CallExpression does not have an object field if no receiver is passed for the call. Let’s patch the analysis code to handle this case:

estraverse.traverse(ast, {
    leave: function (node, parent) {
        if (node.type === 'CallExpression' &&
            node.callee.type === 'MemberExpression') {
            console.log(node.callee.object.name.toUpperCase());
        }
    }
});

Re-running this analysis on jQuery yields another crash, and running another round of JS Delta yields this input:

(function () {
}(function () {
    ({
        pushStack: function () {
            var ret = jQuery.merge(this.constructor());
        }
    });
}));

Here, the issue is the this.constructor() call, as this is represented with a special ThisExpression node in the AST. (It’s worth noting at this point that JS Delta typically does not compute a minimal failure-inducing input, as that would be too expensive. There are other transformations we could add that would yield a smaller program for cases like the above, but we haven’t implemented them yet.) Continuing to fix bugs in this manner, we eventually arrive at a working analysis, shown in example-fixed.js in the repository.

A couple of further usage notes for JS Delta: