diff options
author | B Paul Anderson <benpaul.anderson@gmail.com> | 2016-05-02 21:01:52 -0500 |
---|---|---|
committer | B Paul Anderson <benpaul.anderson@gmail.com> | 2016-05-02 21:01:52 -0500 |
commit | 63bee74d1091b488c622ea88cbffa514cf9aaef0 (patch) | |
tree | acc3995d8f169a6628c1bb9b8e9b586525e3cb87 | |
parent | 2209027e0b6479edc7243edfc02c951335a7cf8d (diff) | |
download | async-63bee74d1091b488c622ea88cbffa514cf9aaef0.tar.gz |
Implement cycle checking with Kahn's algorithm
-rw-r--r-- | lib/auto.js | 61 |
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; + } } |