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

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;
};