Iterating over trees in PHP

As a good Drupal developer, one of your New Year's resolutions should be to learn more PHP features. Today, we'll talk about iterating over tree-structured data using the awkwardly-named class RecursiveIteratorIterator.

When it comes to arrays, PHP is chock-full of useful tools that you already know about, like
in_array, array_mappreg_grep. But what about tree structures? They show up all over the place: directories on your filesystem, Drupal menus, hierarchical taxonomy terms, DOM trees, and more. You can process them with loops and recursion but it gets pretty complex—just look at the source for file_scan_directory to see what I mean. Wouldn't it be easier if you could just use PHP's array functions on trees?

We'll use the built-in RecursiveIteratorIterator to flatten tree structures, and make them much easier to process. You just provide the RecursiveIteratorIterator constructor a RecursiveIterator, which tells it how to traverse the particular tree in question—for example RecursiveDirectoryIterator knows how to recurse into directories. Then you can iterate over the entire hierarchical structure in just a simple foreach loop! Here's an example:

// Create a RecursiveIterator that knows how to follow subdirectories.
$recursive_iter = new RecursiveDirectoryIterator('.', FilesystemIterator::SKIP_DOTS);

// Pass the RecursiveIterator to the constructor of RecursiveIteratorIterator.
$recursive_iter_iter = new RecursiveIteratorIterator(
  $recursive_iter,
  // Also pass in a 'mode', to specify whether parents should come before children,
  // after children, or not at all. We want parents first, so we use SELF_FIRST.
  RecursiveIteratorIterator::SELF_FIRST
);

// Use our RecursiveIteratorIterator as if it was a flat array.
foreach ($recursive_iter_iter as $path => $info) {
  print "$path\n";
}

// Or process it with standard array functions!
$pngs = preg_grep('/\.png$/', iterator_to_array($recursive_iter_iter));
foreach ($pngs as $path => $info) {
  print "png: $path\n";
}

Menus in Drupal are also trees, and they can be pretty complex to process! So let's try using the same approach as above, but this time for menus.

Unfortunately, there's no built-in RecursiveIterator for menu trees, like RecursiveDirectoryIterator is directories. So we have to build our own instead, by subclassing an existing iterator, and implementing getChildren() and hasChildren(). That's a bit of work, but then we can easily process a complete hierachical menu in just a few lines of code:

<?php

// A RecursiveIterator that knows how to recurse into Drupal menu trees.
class MenuIterator extends ArrayIterator implements RecursiveIterator {

  // Get a recursive iterator over the children of this item.
  public function getChildren() {
    $link_data = $this->current();
    return new MenuIterator($link_data['below']);
  }

  // Does this item have children?
  public function hasChildren() {
    $link_data = $this->current();
    return !empty($link_data['below']);
  }
}

// Now let's use our new class to print out a pretty list of menu items:

// Get a menu tree.
$menu = drush_get_option('menu');
$tree = menu_build_tree($menu);

// Create a MenuIterator over the tree.
$menu_iterator = new MenuIterator($tree);

// Create a RecursiveIteratorIterator, passing in our MenuIterator.
$recursive_iter_iter = new RecursiveIteratorIterator(
  $menu_iterator,
  RecursiveIteratorIterator::SELF_FIRST
);

// Iterate over the whole tree, as if it was flat.
foreach ($recursive_iter_iter` as $link_data) {
  $link = $link_data['link'];
  if ($link['hidden'] == 0) { // Ignore hidden items.
    $prefix = str_repeat('  ', $link['depth'] - 1); // Make our output pretty.
    printf("%-40s  %s\n", $prefix . $link['title'], $link['link_path']);
  }
}

Here's an example of running this script:

$ drush --user=1 php-script menu-tree.php --menu=management
Administration                            admin
  Dashboard                               admin/dashboard
  Content                                 admin/content
    Comments                              admin/content/comment
  Structure                               admin/structure
    Blocks                                admin/structure/block
    Content types                         admin/structure/types
    Menus                                 admin/structure/menu
      Main menu                           admin/structure/menu/manage/main-menu
      Management                          admin/structure/menu/manage/management
      Navigation                          admin/structure/menu/manage/navigation
      User menu                           admin/structure/menu/manage/user-menu
    Taxonomy                              admin/structure/taxonomy
  Appearance                              admin/appearance
[snip]

This is just the tip of the iceberg. There are so many other trees of data in the world that can be processed with RecursiveIteratorIterator: XML, IMAP folders, HTML elements and more. Let us know what uses you find for RecursiveIteratorIterator!

Blog

Iterating over trees in PHP