Implement cycle checking with Kahn's algorithm

1 files changed, 42 insertions, 19 deletions

diff --git a/lib/auto.js b/lib/auto.js
index 148cd5f..925db77 100644
--- a/lib/auto.js
+++ b/lib/auto.js
@@ -2,7 +2,7 @@
 
 import arrayEach from 'lodash/_arrayEach';
 import forOwn from 'lodash/forOwn';
-import indexOf from 'lodash/_baseIndexOf';
+import indexOf from 'lodash/indexOf';
 import isArray from 'lodash/isArray';
 import okeys from 'lodash/keys';
 import noop from 'lodash/noop';
@@ -112,34 +112,26 @@ export default function (tasks, concurrency, callback) {
 
     var readyTasks = [];
 
+    // for cycle detection:
+    var readyToCheck = []; // tasks that have been identified as reachable
+    // without the possibility of returning to an ancestor task
+    var uncheckedDependencies = {};
 
     forOwn(tasks, function (task, key) {
         if (!isArray(task)) {
             // no dependencies
             enqueueTask(key, [task]);
+            readyToCheck.push(key);
             return;
         }
 
         var dependencies = task.slice(0, task.length - 1);
         var remainingDependencies = dependencies.length;
-
-        checkForDeadlocks();
-
-        function checkForDeadlocks() {
-            var len = dependencies.length;
-            var dep;
-            while (len--) {
-                if (!(dep = tasks[dependencies[len]])) {
-                    throw new Error('async.auto task `' + key +
-                        '` has non-existent dependency in ' +
-                        dependencies.join(', '));
-                }
-                if (isArray(dep) && indexOf(dep, key, 0) >= 0) {
-                    throw new Error('async.auto task `' + key +
-                        '`Has cyclic dependencies');
-                }
-            }
+        if (!remainingDependencies) {
+            enqueueTask(key, [task]);
+            readyToCheck.push(key);
         }
+        uncheckedDependencies[key] = remainingDependencies;
 
         arrayEach(dependencies, function (dependencyName) {
             addListener(dependencyName, function () {
@@ -151,9 +143,9 @@ export default function (tasks, concurrency, callback) {
         });
     });
 
+    checkForDeadlocks();
     processQueue();
 
-
     function enqueueTask(key, task) {
         readyTasks.push(function () {
             runTask(key, task);
@@ -222,5 +214,36 @@ export default function (tasks, concurrency, callback) {
         }
     }
 
+    function checkForDeadlocks() {
+        // Kahn's algorithm
+        // https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm
+        // http://connalle.blogspot.com/2013/10/topological-sortingkahn-algorithm.html
+        var currentTask;
+        var counter = 0;
+        while (readyToCheck.length) {
+            currentTask = readyToCheck.pop();
+            counter++;
+            arrayEach(getDependents(currentTask), function (dependent) {
+                if (!(--uncheckedDependencies[dependent])) {
+                    readyToCheck.push(dependent);
+                }
+            });
+        }
+
+        if (counter !== numTasks) {
+            throw new Error(
+                'async.auto cannot execute tasks due to a recursive dependency'
+            );
+        }
+    }
 
+    function getDependents(taskName) {
+        var result = [];
+        forOwn(tasks, function (task, key) {
+            if (isArray(task) && indexOf(task, taskName) >= 0) {
+                result.push(key);
+            }
+        });
+        return result;
+    }
 }