diff options
-rw-r--r-- | lib/auto.js | 64 | ||||
-rw-r--r-- | mocha_test/auto.js | 17 |
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({ |