How to handle callbacks in JavaScript within recursive functions?

Question

Trying to compare two sub trees of bookmarks in Chrome, I ran into troubles with the asynchronous API call to query the children of a bookmarks folder.

function titleComparator (lhs, rhs) {
  return lhs.title < rhs.title ? -1 : lhs.title > rhs.title ? 1 : 0;
}

// Return whether two bookmark trees have equal content
function compare(lhs, rhs) {
  // Not equal if one is a bookmark and another is a folder
  if (('url' in lhs) != ('url' in rhs))
    return false;
  // If both are bookmarks, compare url and title
  if ('url' in lhs && 'url' in rhs)
    return lhs.title == rhs.title && lhs.url == rhs.url;
  // If both are folders, compare contents
  chrome.bookmarks.getChildren(lhs.id, function (lhsChildren) {
    chrome.bookmarks.getChildren(rhs.id, function (rhsChildren) {
      if (lhsChildren.length != rhsChildren.length)
        return false;  // Want to return from compare()
      lhsChildren.sort(titleComparator);
      rhsChildren.sort(titleComparator);
      for (var i = 0; i < lhsChildren.length; i++)
        if (!compare(lhsChildren[i], rhsChildren[i])
          return false;  // Same here
      return true;  // Same here
    });
  });
}

How to handle callbacks in JavaScript within recursive functions?

Answer 1

return will only ever exit the callee

You're gonna have to provide a callback for the answer to be spat out into asynchronously.

Everywhere you've written a return statement intended to be consumed by the callback closure, you should standardize instead on passing it to your callback.

function compareAsync(lhs, rhs, callback) {
  //…
    callback(false); return;
  //…
    callback(lhs.title == rhs.title && lhs.url == rhs.url); return;
  //…
        callback(false); return;  // Want to return from compare()
  //…

  var finished = 0;
  var whetherSuccess = true;
  lhsChildren.forEach(function(iterand, index) {
    compareAsync(iterand, rhsChildren[index], function(result) {
      whetherSuccess &= result;
      if (++finished === lhsChildren.length) {
        callback(whetherSuccess);
      }
    });
  });
}

So: upon finding out what the lhsChildren are, we kick off a bunch of async functions. They'll each increment the finished counter at some point. They each have the power to demote the overall whetherSuccess to false via &=. The consumer who discovers they're the the final function to get an answer, is the person who will report whetherSuccess to the original callback.

Answer 2

as explained in detail here

you will need to refactor your code.

somehow it seems that it is not the correct way to use recursion within a asynchronous (often delayed) function to search a tree-based or hierarchical data model.

I think this should be the way to do it:

1. Seperatate the logic into several functions
2. Use "lazy loading" to avoid duplicate call of getChilden()
3. Use recursion and define a new nested function callback
4. Refactor the for-loop to recursion as well

See my untested code to show what I mean:

   function compare(lhs, rhs, callback, index, lhsChilds, rhsChilds){

    // Not equal if one is a bookmark and another is a folder
    if (('url' in lhs) != ('url' in rhs)) {
        callback(false);
        return;
    }
    // If both are bookmarks, compare url and title
    if ('url' in lhs && 'url' in rhs) {
        callback(lhs.title == rhs.title && lhs.url == rhs.url);
        return;
    }

    // If both are folders, check parameters and compare contents


    //First, check if the list has already been loaded (code is running inside a recursive step)
    if(lhsChilds != undefined && rhsChilds != undefined){
        compareTwoChilds(lhs, rhs, callback, index, lhsChilds, rhsChilds);
    }
    else{
        index = 0; //first recursion for this tuple (lhs, rhs)
        chrome.bookmarks.getChildren(lhs.id, function (lhsChildren) {
            chrome.bookmarks.getChildren(rhs.id, function (rhsChildren) {
                compareTwoChilds(lhs, rhs, callback, index, lhsChilds, rhsChilds);
            });
        });
    }

}

function compareTwoChilds(lhs, rhs, callback, index, lhsChilds, rhsChilds){
    if (index < lhsChildren.length){ //just for the safety
        if (lhsChildren.length != rhsChildren.length) {
            callback(false);
            return;
        }
        lhsChildren.sort(titleComparator);
        rhsChildren.sort(titleComparator);

        //compare using recursion, with an emtpy lists of rhs and lhs children
        compare(lhsChildren[index], rhsChildren[index], function(compareResult){
            if(!compareResult){
                callback(false); //if the result is false, no more search needed
            }else{ // use recursion again to loop through the next childs using the already loaded childs
                if (++index < lhsChildren.length){
                    compare(lhsChildren[index], rhsChildren[index], callback, index, lhsChilds, rhsChilds)
                }else{
                    callback(true); // the loop has ended,
                }
            }
        });

    }else{
        callback(false); //this should never happen, so not the same...
    }

}

you can call the compare function like that:

compare(lhs,rhs, function(result){
   var compareResult = result;
   //carry on with your code here
});
//and not here :-)

Answer 3

First of all, I found that Chrome has a getSubTree() function as well which makes things considerably easier. So if you just want to get it work, use this instead of asynchronously traversing the tree node by node. However, this remains an interesting problem and thanks to a reddit user, I figured out a working solution to this.

compare() is the main function that recursively calls itself. However, because of the asynchronous call inside, it cannot consume the return values of it's recursive calls.

// Pass a boolean to the callback indicating whether the recursive contents of
// both bookmarks folders are equal.
function compare(lhs, rhs, callback) {
    // Compare titles except for the top-level folder
    if (lhs.parent_ && lhs.title !== rhs.title) {
        compare_failure(callback);
        return;
    }
    // Compare urls if at least one of the sides is a bookmark
    if ('url' in lhs || 'url' in rhs) {
        if ((lhs.url || null) === (rhs.url || null))
            compare_respond(lhs.parent_, callback);
        else
            compare_failure(callback);
        return;
    }
    // For both sides being folders, we have to take a look at the contents
    chrome.bookmarks.getChildren(lhs.id, function (lhs_children) {
        chrome.bookmarks.getChildren(rhs.id, function (rhs_children) {
            // Compare amount of children
            if (lhs_children.length != rhs_children.length) {
                compare_failure(callback);
                return;
            }
            // Keep track of how many children already reported back
            lhs.all_children = lhs_children.length;
            lhs.equal_children = 0;
            // Let pairs of children compare each other
            lhs_children.sort(bookmark_comparator);
            rhs_children.sort(bookmark_comparator);
            for (var i = 0; i < lhs_children.length; i++) {
                var lhs_child = lhs_children[i];
                var rhs_child = rhs_children[i];
                // Store parent reference so the deeper function can
                // asynchronously respond with the results once finished.
                lhs_child.parent_ = lhs;
                compare(lhs_child, rhs_child, callback);
            }
        });
    });
};

compare_respond() is the counterpart that is used to propagate results of deeper nodes back up. It's used instead of return in the main function above.

// Report comparison results back to the parent node. The parent node waits
// until it collected the results from all its children. Then it reports to
// its parent in turn. At the root node, the user callback is executed.
function compare_respond(node, callback) {
    // Collect child results
    node.equal_children++;
    // Respond upwards if we got results from all
    if (node.equal_children == node.all_children) {
        if ('parent_' in node)
            compare_respond(node.parent_, callback);
        else
            callback(true);
    }
};

compare_failure() is used to abort the whole thing at any point when we found a pair of unequal nodes. We don't have to report upwards in that case.

// Break out of the recursive function and report failure to the user. It's
// safe against being called multiple times so multiple children can report
// failure and the user will only be notified once.
function compare_failure(callback) {
    if ('called' in callback)
        return;
    callback.called = true;
    callback(false);
};

bookmark_comparator() is a small helper that is used to sort arrays of child bookmarks. Sorting is needed to compare the contents of two folders since I don't want to rely on the item order.

// Comparator to sort lists of bookmark nodes first by title and second by
// url. Take into that folders have to url.
function bookmark_comparator(lhs, rhs) {
    if (lhs.title != rhs.title)
        return lhs.title < rhs.title ? -1 : 1;
    if (lhs.url || null != rhs.url || null)
        return lhs.url || null < rhs.url || null ? -1 : 1;
    return 0;
};