Drastically reduce the cost of walking the AST

[benjamn]

Before these changes, traversing the jQuery AST using walk.simple used to take ~15ms on my machine. Now, the walk function takes 0.03ms.

The trick is to scan the source string to find all possible positions of require tokens using the wordRe regular expression, then use those positions to guide the traversal, so that entire subtrees can be ignored if they do not contain any require tokens.

Parsing the code still takes the majority of the time (~70ms for jQuery), but the AST traversal savings definitely add up when browserifying large projects.

I also took this opportunity to add support for ES2015 import statements (and export...from statements, too): https://github.com/benjamn/node-detective/commit/2249f98405fc7549d66b4b6101286d157e6f88eb, though I'd be happy to split that out into a separate pull request (or contribute to #57) if you prefer.

[zertosh]

Very interesting, I'll take a deeper look when I get home.

I've been toying around with the idea of skipping parsing the AST all together and just using js-tokens. I built loose-envify as a light-weight alternative to envify using that technique. The tests are pretty robust but it does have its caveats.

I can envision node-detective doing something where it would first make sure the syntax is valid, then with js-tokens collect all the requires. If any one require doesn't follow the expected "terminator -> require -> open parens -> string -> close parens -> terminator", it'll fallback to the AST approach.

[benjamn]

That would be huge, since parsing is still so expensive. I presume that technique at least skips comments?

[zertosh]

I just got around to playing with this (sorry), and it's pretty clever. I think though, that the exec calls are actually pretty expensive, and you still have to walk the tree until you exhaust the indexes.

I took your idea of skipping branches whose source doesn't have the word we're looking for, and I came up with this:

diff --git a/index.js b/index.js
index 16e14462..2ab63954 100644
--- a/index.js
+++ b/index.js
@@ -43,9 +43,12 @@ exports.find = function (src, opts) {

     var ast = parse(src, opts.parse);

-    walk.simple(ast, {
-        CallExpression: function (node) {
-            if (!isRequire(node)) return;
+    function visit(node, st, c) {
+        var hasRequire = wordRe.test(src.slice(node.start, node.end));
+        if (!hasRequire) return;
+        walk.base[node.type](node, st, c);
+        if (node.type !== 'CallExpression') return;
+        if (isRequire(node)) {
             if (node.arguments.length) {
                 var arg = node.arguments[0];
                 if (arg.type === 'Literal') {
@@ -57,6 +60,11 @@ exports.find = function (src, opts) {
             }
             if (opts.nodes) modules.nodes.push(node);
         }
+    }
+    
+    walk.recursive(ast, null, {
+        Statement: visit,
+        Expression: visit
     });

     return modules;

I ran the benchmark against this file. It's a bundled react with the requires still in it – I don't like testing against jQuery because it doesn't actually have any requires, the world "require" is in a comment or string or something.

The current implementation of detective gives me: 140, 154, 152, 150, 147 Your implementation gives me: 127, 125, 128, 124, 129 And mine gives me: 122, 125, 123, 134, 130

What do you think?