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

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 Shoulders Composition doesn’t happen in a vacuum. Bach wa

Learning Prolog

I'm not quite sure exactly I was searching for, but somehow I serendipitously stumbled upon the site learnprolognow.org a few months ago. It's the home for an introductory Prolog programming course. Logic programming offers an interesting way to think about your problems; I've been doing so much procedural and object-oriented programming in the past decade that it really took effort to think at a higher level! I found the most interesting features to be definite clause grammars (DCG), and unification. Difference lists are very powerful and Prolog's DCG syntax makes it easy to work with them. Specifying a grammar such as: s(s(NP,VP)) --> np(NP,X,Y,subject), vp(VP,X,Y). np(np(DET,NBAR,PP),X,Y,_) --> det(DET,X), nbar(NBAR,X,Y), pp(PP). np(np(DET,NBAR),X,Y,_) --> det(DET,X), nbar(NBAR,X,Y). np(np(PRO),X,Y,Z) --> pro(PRO,X,Y,Z). vp(vp(V),X,Y) --> v(V,X,Y). vp(vp(V,NP),X,Y) --> v(V,X,Y), np(NP,_,_,object). nbar(nbar(JP),X,3) --> jp(JP,X). pp(pp(PREP,N

What's Wrong with OOP

Proponents of Object Oriented Programming feel the paradigm yields code that is better organized, easier to understand and maintain, and reusable. They view procedural programming code as unwieldy spaghetti and embrace OO-centric design patterns as the "right way" to do things. They argue objects are easier to grasp because they model how we view the world. If the popularity of languages like Java and C# is any indication, they may be right. But after almost 20 years of OOP in the mainstream, there's still a large portion of programmers who resist it. If objects truly model the way people think of things in the real world, then why do people have a hard time understanding and working in OOP? I suspect the problem might be the focus on objects instead of actions. If I may quote from Steve Yegge's Execution in the Kingdom of Nouns : Verbs in Javaland are responsible for all the work, but as they are held in contempt by all, no Verb is ever permitted to wander about