Clean pattern to manage multi-step async processes on a tree

Question

I need to visit each node in a tree, do some asynchronous work, and then find out when all of the asynchronous work has completed. Here are the steps.

1. Visit a node and modify its children asynchronously.
2. When async modifications to children are done, visit all children (which might require async work).
3. When all asynchronous work for all descendants is done, do something else.

Update:

I ended up using a pattern that looks like a monitor/lock (but isn't) for each node to know when to begin step 2. I used events and attributes to keep track of all descendants of a node to know when to begin step 3.

It works, but man is this difficult to read! Is there a cleaner pattern?

function step1(el) { // recursive
  var allDone = false;
  var monitor = new Monitor();
  var lock = monitor.lock(); // obtain a lock
  $(el).attr("step1", ""); // step1 in progress for this node

  // fires each time a descendant node finishes step 1
  $(el).on("step1done", function (event) {
    if (allDone) return;
    var step1Descendants = $(el).find("[step1]");
    if (step1Descendants.length === 0) {
      // step 1 done for all descendants (so step 2 is complete)
      step3(el); // not async
      allDone = true;
    }
  });

  // fires first time all locks are unlocked
  monitor.addEventListener("done", function () {
    $(el).removeAttr("step1"); // done with step 1
    step2(el); // might have async work
    $(el).trigger("step1done");
  });

  doAsyncWork(el, monitor); // pass monitor to lock/unlock
  lock.unlock(); // immediately checks if no other locks outstanding
};

function step2(el) { // visit children
  $(el).children().each(function (i, child) {
    step1(child);
  });
};

Answer 1

Here's an updated version that walks the node-tree, processing each child in the initial root node, and then descends recursively into each child's tree and processes its child nodes and so on.

Here's a jsfiddle demo

// Pass the root node, and the callback to invoke
// when the entire tree has been processed
function processTree(rootNode, callback) {
    var i, l, pending;

    // If there are no child nodes, just invoke the callback
    // and return immediately
    if( (pending = rootNode.childNodes.length) === 0 ) {
        callback();
        return;
    }

    // Create a function to call, when something completes
    function done() {
        --pending || callback();
    }

    // For each child node
    for( i = 0, l = rootNode.childNodes.length ; i < l ; i++ ) {
        // Wrap the following to avoid the good ol'
        // index-closure-loop issue. Pass the function
        // a child node
        (function (node) {

            // Process the child node asynchronously.
            // I'm assuming the function takes a callback argument
            // it'll invoke when it's done.
            processChildNodeAsync(node, function () {

                // When the processing is done, descend into
                // the child's tree (recurse)
                processTree(node, done);

            });

        }(rootNode.childNodes[i]));
    }
}

---

Original Answer

Here's a basic example you might be able to use... though without the specifics of your problem, it's half psuedo-code

function doAsyncTreeStuff(rootNode, callback) {
    var pending = 0;

    // Callback to handle completed DOM node processes
    // When pending is zero, the callback will be invoked
    function done() {
        --pending || callback();
    }

    // Recurse down through the tree, processing each node
    function doAsyncThingsToNode(node) {
        pending++;

        // I'm assuming the async function takes some sort of
        // callback it'll invoke when it's finished.
        // Here, we pass it the `done` function
        asyncFunction(node, done);

        // Recursively process child nodes
        for( var i = 0 ; i < node.children.length ; i++ ) {
            doAsyncThingsToNode(node.children[i]);
        }
    }

    // Start the process
    doAsyncThingsToNode(rootNode);
}

Answer 2

It seems the right pattern for this problem and for async work in general is Promises. The idea is that any function that will do asynchronous work should return a promise object, to which the caller can attach functions that should be called when the asynchronous work is completed.

jQuery has a great API for implementing this pattern. It's called a jQuery.Deferred object. Here's a simple example:

function asyncWork() {
  var deferred = $.Deferred();
  setTimeout(function () {
    // pass arguments via the resolve method
    deferred.resolve("Done.");
  }, 1000);
  return deferred.promise();
}

asyncWork().then(function (result) {
  console.log(result);
});

Very tidy. What's the difference between a Deferred object and its promise object? Good question.

Here's how you might apply this pattern to solve this problem.

function step1(el) { // recursive
  var deferred = $.Deferred();

  // doAsyncWork needs to return a promise
  doAsyncWork(el).then(function () {
    step2(el).then(function () {
      step3(el); // not async
      deferred.resolve();
    });
  });
  return deferred.promise();
};

function step2(el) { // visit children
  var deferred = $.Deferred();
  var childPromises = [];
  $(el).children().each(function (i, child) {
    childPromises.push(step1(child));
  });

  // When all child promises are resolved…
  $.when.apply(this, childPromises).then(function () {
    deferred.resolve();
  });
  return deferred.promise();
};

So much cleaner. So much easier to read.

Answer 3

This is something you would probably prefer to do with threads to continue other work, but since you are using JavaScript you need to work around this with some sort of blocking. One way is make an initially empty list of finished tasks, make the asynchronous calls, and have each call register itself on the list when it is finished. While you are waiting for the calls, enter a loop with a timer, and at each iteration check if the finished tasks list is complete; if so, continue with other tasks. You may want to give up if your loop runs too long.