Tuesday, July 24, 2012

PHP Recursive Directory Traversal

It sounds like a simple enough task: Generate an array that mirrors a directory structure. Directories may have subdirectories (arbitrary nesting), and entries should be alphabetized with directories grouped first. The image below shows what the array should look like given a sample directory.

While not terribly difficult, there are a few snags that can trip you up if you're not careful. For me, the first snag was trying to do it “the right way.”

The RecursiveDirectoryIterator “provides an interface for iterating recursively over filesystem directories” (php.net), so this was my first approach. I hacked together this code after a short while:

<?php
function getDirectoryList($dir) {
    $dirList = [];
    $dirIter = new RecursiveDirectoryIterator($dir,
        FilesystemIterator::SKIP_DOTS);
    $iterIter = new RecursiveIteratorIterator($dirIter);

    foreach ($iterIter as $entry) {
        $path = substr($entry->getPath(), strlen($dir) - 1);
        $keys = "['" . join("']['", explode("/", $path)) . "']";
        eval('$dirList' . $keys . '[]="' . $entry->getFilename() . '";');
    }

    return $dirList;
}

The function gets the nesting right for files, but empty directories are missing and the ordering is wrong. I could have spent some time trying to fix those issues, but the use of eval() bothered me enough to abandon the approach completely. A straight iteration wasn't going to build up the array correctly without it, so I needed to take a true recursive approach.

In addition to doing away with eval(), the recursive approach also afforded me an easy way to implement the necessary sorting. I was able to queue the directory names and file names separately, sort them, and then return their union.

<?php
function getDirectoryList($dir) {
    $dirList = $fileList = [];

    if ($dfp = opendir($dir)) {
        while (($entry = readdir($dfp)) !== false) {
            if ($entry[0] != ".") { // catches dot dirs and hidden files
                $path = "$dir/$entry";
                if (is_file($path)) {
                    $fileList[] = $entry;
                }
                else if (is_dir($path)) {
                    $dirList[$entry] = getDirectoryList($path);
                }
            }
        }
        closedir($dfp);

        uksort($dirList, "strnatcmp");
        natsort($fileList);
    }

    return $dirList + $fileList;
}

Interestingly enough, PHP doesn't have a natksort() function. I had to mock my own implementation using uksort() and strnatcmp().

I ran the solution past a few friends of mine and the response from one was:

you... bring shame to our profession.

His efforts to show me “the right way” again with RecursiveDirectoryIterator were short lived however when he came across the same issues I did and gave up to eat a leftover burrito.

So I guess there are a couple morals to my tale. One, that despite our fancy modern OOP APIs, sometimes the procedural approach is a better fit for the task at hand. We abstract everything so we don't have to re-invent the wheel but then have a mass of code that is too generic to actually do something that should be trivial. Two, we should be careful about being pompous. It's hard to eat a burrito with your foot in your mouth.

Of course, if you can come up with a better way then let me know. I might just buy you a new burrito. :)

6 comments:

  1. Very interesting article. I would pursue this further but I am kind of swamped learning Romulan. (Actually, I am learning Aussie speak. The chicks dig it. "It's your shout, mate". )

    ReplyDelete
  2. In the first code, $filename seems to be unused.

    ReplyDelete
  3. According to my benchmarks, it appears to be faster to use a non-recursive iterator recursively than to not use an iterator at all...

    function getDirectoryList($dir) {
    $dirList = $fileList = array();
    $iter = new FilesystemIterator($dir, FilesystemIterator::SKIP_DOTS);

    foreach($iter as $file) {
    if($file->isDir()) {
    $dirList[$file->getFilename()] = getDirList($file->getPathname());
    } else {
    $fileList[$file->getFilename()] = $file->getFilename();
    }
    }
    uksort($dirList, "strnatcmp");
    natsort($fileList);
    return $dirList + $fileList;
    }

    ReplyDelete
  4. Just stumbled over your blog-post and wondered why you haven't used "glob".
    Well glob is usable in very very large file-listings but in this case it does most of the work for you.
    E.g. ignore "."-Files and keep the sort-order.

    Here is my version of your function:

    function getDirectoryList($dir) {
    $dirs = $files = array();
    foreach (glob($dir."/*") as $f) {
    if (is_dir($f)) {
    $dirs[$f] = getDirectoryList($f);
    } else {
    $files[] = $f;
    }
    }
    return array_merge($dirs, $files);
    }

    Thanks for keeping me so hooked, that I immediately have to test it myself ;-)

    ReplyDelete