Mixing Promises and Recursion in Node.js

Question

I have a sticky problem I am trying to solve. To illustrate the problem, I will use a familiar scenario: traversing a directory. I know there are tons of libraries out that that already traverse a directory. However, that's not what I'm trying to do. Traversing a directory is just a metaphor for my problem.

Basically, I have the following:

structure: [],

traverseDirectory: function(path) {
  var scope = this;

  var promise = new Promise(function(resolve, reject) {
    openDirectory(path, function(results) {
      for (var i=0; i<results.length; i++) {
        if (results[i].type === 'directory') {
          scope.traverseDirectory(results[i].name);
        } else {
          scope.structure.push({ filename:name });
        }
      }
      resolve(scope.structure);
    });
  });
  return promise;
},

getDirectoryStructure: function(path) {
  this.traverseDirectory(path)
    .then(function(results) {
      // Print out all of the files found in the directories.
      console.log(JSON.stringify(results));
    }
  ;
}

My problem is the .then of getDirectoryStructure fires before the directory is actually traversed. Its not waiting like I thought it would. Plus, I'm not sure how to "pass" (not sure if that's the right word) the promise around as I'm recursing through the directory structure. Can I even do what I'm trying with promises?

Thank you for any help.

I kind of miss the goal. do you search for item, or do you want to build some kind of representation of the structure? That would make significant difference in approach. — webduvet
– webduvet, Commented Oct 29, 2015 at 14:18

Bergi · Accepted Answer · 2015-10-29 13:59:03Z

1

In this case you would need to consider that you have multiple "steps" per level... or in your directory traversal example multiple sub directories, so essentially you need to fork... what @Anonymous0day suggests is close, however returning out of the for loop is counter indicative.

What you need is Promise.all: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Promise/all

var traverseDirectory = function(path) {

  var promise = new Promise(function(resolve, reject) {
    openDirectory(path, function(results) {
      resolve(results);
    });
  });
  return promise.then(function(results) {
    var pros = [];

    for (var i=0; i<results.length; i++) {
      if (results[i].type === 'directory') {
        pros.push(scope.traverseDirectory(results[i].name)); // <- recursive call
      } else {
        pros.push([{filename:name}]);
      }
    }

    return Promise.all(pros).then(function(arrs) {
       var structure = [];
       for (var i=0; i<arrs.length; i++)
         structure = structure.concat(arr[i]);
       return structure;
    });
  });
}

(PS I kinda de "scoped" this, to show you that you don't need an external object in the same way to keep track of the structure... you can keep it inside the function and only expose it when the outer promise resolves).

But the biggest thing you needed to do was actually WAIT to resolve the outer promise until after you're all done traversing (PS - I'll leave it to you to see what Promise.all does if the 'pros' array is empty).

You were seeing it execute immediately because it was literally resolving right after it was done with the for loop... if those recursions had actually been asynch, the event loop would indeed immediately resolve.

Cheers, lemme know if that makes sense. [EDITED for proper Promise.all().then(success, fail) instead of the .catch I had].

edited Oct 29, 2015 at 13:59

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

answered Oct 29, 2015 at 2:25

Nick Sharp

1,89112 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

12 Comments

Nick Sharp Over a year ago

PS- I think I may have buggered up the then.catch on the Promise.all... You might need it more like this: Promise.all([p1, p2, p3, p4, p5]).then(function(value) { console.log(value); }, function(err) { console.log(reason) });

Bergi Over a year ago

Avoid the Promise constructor antipattern! You should only promisify openDirectory and do everything else via then.

JQuery Mobile Over a year ago

@NickSharp - I had an external scope because I need to see if a file had already been added. In the scenario presented, a file wouldn't be added twice because it involves directory traversing. However, traversing tags is more representative of my scenario. Sp, I need to check to see if a file has already been added before I add it. Which leads me back to my scoping issue. Right now, files are getting added multiple times to the structure[]. I'm not sure how to resolve this. Also, what's the Promise constructor anti pattern? I read the link. It doesn't make sense to me in this situation.

JQuery Mobile Over a year ago

@Bergi How would you fix this answer to avoid the Promise constructor anti pattern? I read the link. I've been pondering it. Unfortunately, it doesn't make entire sense to me.

Bergi Over a year ago

@JQueryMobile: See my edit to the answer (I've also fixed the structure thing to include the results from the recursive calls)

|

JLRishe · Accepted Answer · 2015-10-29 16:22:23Z

Here is a relatively concise way to do it that avoids for-loops and mutating variables. It returns a tree structure of all the retrieved results:

// returns a promise for an object with two properties:
//   directoryname (string)
//   contents (array of objects (directories and files) for the contents of the directory)
function traverseDirectory(path) {
    return new Promise(function(resolve, reject) {
        openDirectory(path, resolve);
    }).then(function (results) {
         return Promise.all(results.map(function (item) {
             return item.type === 'directory'
                 ? traverseDirectory(item.name)
                 : { filename: item.name };
        }));
    }).then(function (contents) {
       return {
           directoryname: path,
           contents: contents
       };
    });
}

If your objective is to obtain a flat array of all files in the directory tree, you can do this (everything is the same except for the last then):

// returns a promise for an array of all of the files in the directory and its descendants
function traverseDirectory(path) {
    return new Promise(function(resolve, reject) {
        openDirectory(path, resolve);
    }).then(function (results) {
        return Promise.all(results.map(function (item) {
            return item.type === 'directory'
                ? traverseDirectory(item.name)
                : { filename: item.name };
        }));
    }).then(function (contents) {
        return Array.prototype.concat.apply([], contents);
    });
}

Roamer-1888 · Accepted Answer · 2015-10-29 22:24:10Z

1

For a more flexible approach, you might choose for :

.getDirectoryStructure() to deliver what it says, a representation of a directory hierarchy.
A flattener to operate on the hierarchical array to produce what is actually asked for - a flat array of objects. You can use something like lodash's _.flattenDeep() or write your own.

First, a couple of general points :

In general, you should promisify at the lowest possible level. In this case, that means promisifying a version of openDirectory(). By doing so the code in traverseDirectory() will simplify. (In the solution below, what remains of traverseDirectory() is actually subsumed by getDirectoryStructure()).
Use Promise.all() to aggregate families of promises generated during the traversal.

In doing this, you can dispense with outer var structure and rely instead on Promise.all() to deliver, (recursively) an array of results.

Here's the code :

var dirOpener = {
    openDirectoryAsync: function(path) {
        return new Promise(function(resolve, reject) {
            openDirectory(path, resolve);
        });
    },
    getDirectoryStructure: function(path) {
        var scope = this;
        return scope.openDirectoryAsync(path).then(function(results) {
            var promises = results.map(function(file) {
                return (file.type === 'directory') ? scope.getDirectoryStructure(file.name) : { filename: file.name };
            });
            return Promise.all(promises);
        });
    },
    flattenDeep: function(arr) {
        var fn = arguments.callee;
        return arr.reduce(function(a, x) {
            return a.concat(Array.isArray(x) ? fn(x) : x);
        }, []);
    }
}

For an array reflecting the full directory structure, call as follows :

dirOpener.getDirectoryStructure(rootPath)
.then(function(results) {
    console.log(results);
})
.catch(function(e) {
    console.log(e);
});

Or, for a flattened array containing just the filename objects :

dirOpener.getDirectoryStructure(rootPath)
.then(dirOpener.flattenDeep)
.then(function(results) {
    console.log(results);
})
.catch(function(e) {
    console.log(e);
});

edited Oct 29, 2015 at 22:24

answered Oct 29, 2015 at 21:07

Roamer-1888

19.3k5 gold badges35 silver badges45 bronze badges

3 Comments

Bergi Over a year ago

There is no reason to use try catch in the Promise constructor callback. All exceptions in there will automatically reject the promise (that's the large advantage over the deferred pattern).

Roamer-1888 Over a year ago

@Bergi, I thought I read somewhere that Bluebird worked that way but native Promise didn't?

Bergi Over a year ago

No, all ES6-compatible promise libraries work that way. Which includes the native implementation :-)

Collectives™ on Stack Overflow

Mixing Promises and Recursion in Node.js

3 Answers 3

12 Comments

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

12 Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related