Merge pull request #1140 from b-paul/fix-#1092

Fix #1092

2 files changed, 63 insertions, 18 deletions

diff --git a/lib/auto.js b/lib/auto.js
index 148cd5f..4750eef 100644
--- a/lib/auto.js
+++ b/lib/auto.js
@@ -112,36 +112,33 @@ 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) {
+            if (!tasks[dependencyName]) {
+                throw new Error('async.auto task `' + key +
+                    '` has a non-existent dependency in ' +
+                    dependencies.join(', '));
+            }
             addListener(dependencyName, function () {
                 remainingDependencies--;
                 if (remainingDependencies === 0) {
@@ -151,9 +148,9 @@ export default function (tasks, concurrency, callback) {
         });
     });
 
+    checkForDeadlocks();
     processQueue();
 
-
     function enqueueTask(key, task) {
         readyTasks.push(function () {
             runTask(key, task);
@@ -222,5 +219,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) >= 0) {
+                result.push(key);
+            }
+        });
+        return result;
+    }
 }
diff --git a/mocha_test/auto.js b/mocha_test/auto.js
index fb779ee..49fac6a 100644
--- a/mocha_test/auto.js
+++ b/mocha_test/auto.js
@@ -305,6 +305,23 @@ describe('auto', function () {
         done();
     });
 
+    // Issue 1092 on github: https://github.com/caolan/async/issues/1092
+    it('extended cycle detection', function(done) {
+        var task = function (name) {
+            return function (results, callback) {
+                callback(null, 'task ' + name);
+            };
+        };
+        expect(function () {
+            async.auto({
+                a: ['c', task('a')],
+                b: ['a', task('b')],
+                c: ['b', task('c')]
+            });
+        }).to.throw();
+        done();
+    });
+
     // Issue 988 on github: https://github.com/caolan/async/issues/988
     it('auto stops running tasks on error', function(done) {
         async.auto({