Skip to main content

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. :)

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

Post a Comment

Popular posts from this blog

Geolocation Search

Services that allow users to identify nearby points of interest continue to grow in popularity. I'm sure we're all familiar with social websites that let you search for the profiles of people near a postal code, or mobile applications that use geolocation to identify Thai restaurants within walking distance. It's surprisingly simple to implement such functionality, and in this post I will discuss how to do so.

The first step is to obtain the latitude and longitude coordinates of any locations you want to make searchable. In the restaurant scenario, you'd want the latitude and longitude of each eatery. In the social website scenario, you'd want to obtain a list of postal codes with their centroid latitude and longitude.

In general, postal code-based geolocation is a bad idea; their boundaries rarely form simple polygons, the area they cover vary in size, and are subject to change based on the whims of the postal service. But many times we find ourselves stuck on a c…

Composing Music with PHP

I’m not an expert on probability theory, artificial intelligence, and machine learning. And even my Music 201 class from years ago has been long forgotten. But if you’ll indulge me for the next 10 minutes, I think you’ll find that even just a little knowledge can yield impressive results if creatively woven together. I’d like to share with you how to teach PHP to compose music. Here’s an example: You’re looking at a melody generated by PHP. It’s not the most memorable, but it’s not unpleasant either. And surprisingly, the code to generate such sequences is rather brief. So what’s going on? The script calculates a probability map of melodic intervals and applies a Markov process to generate a new sequence. In friendlier terms, musical data is analyzed by a script to learn which intervals make up pleasing melodies. It then creates a new composition by selecting pitches based on the possibilities it’s observed. . Standing on ShouldersComposition doesn’t happen in a vacuum. Bach was f…

Creepy JavaScript Tracking

I recently began allergy shots so my new Monday morning routine includes me sitting in a doctor's office for 30 minutes (I must wait after receiving the shots and be checked by a nurse to make sure there was no reaction). With nothing else better to do while I waited last week, I started playing around with some JavaScript. This is what I came up with:
<html> <head> <title>Test</title> <script type="text/javascript"> window.onload = function () { var mX = 0,  mY = 0, sX = 0,  sY = 0, queue = [], interval = 200, recIntv = null, playIntv = null, b = document.body, de = document.documentElement, cursor = document.getElementById("cursor"), record = document.getElementById("record"), play = document.getElementById("play"); window.onmousemove = function (e) { e = e || window.event; if (e.pageX || e.pageY) { …