interesting, potentially critical bug in PEAR

Recently, I noticed that in certain cases, PEAR appears to sort dependencies in slightly the wrong order when installing packages. For instance, while debugging the Structures_DataGrid package, which has a complex sub-package structure, I noticed that the Pager package was installed after the Structures_DataGrid_Renderers_Pager package. This disturbed me for two reasons:

1. Structures_DataGrid_Renderers_Pager depends on Pager, and so Pager should be installed first
2. There was no error.

After investigating (which in my case meant briefly recalling from memory how PEAR actually validates dependencies), I remembered that PEAR validates dependencies twice, once prior to download, and once prior to installation. By the time the dependencies are sorted, PEAR assumes that the sort algorithm properly sorts things. This is actually a pretty reasonable assumption considering the unit tests that are in place to test this.  However, like all regression testing, the unit tests test boundaries and likely cases, but not all possible inputs.

I was unsure of how to proceed, until I picked up Kyle Loudon's Mastering Algorithms with C again.  I purchased this excellent book last year to explore both common algorithms and their implementation right about the time I was most heavily into working on the phar extension.  Phar is not dead, only postponed, for those of you wondering.  The Graph section of the book has an implementation of topological sorting, and while glancing at the simple example of sorting classes and their prerequisites, it dawned on me that this is exactly what I needed.

Sorting packages with dependencies so that the dependencies are always installed first is a topological sort.  So, I took a look around and found Sergio Carvallho's Structures_Graph package at pear.php.net (although it was not easy, pear.php.net's search facilities are pretty feeble now, stay tuned for improvements at some point in the near future).  The package has a full implementation of topological sorting plus a few other things I won't need, but I now have a working implementation as part of the PEAR package.

This will unfortunately delay the release of PEAR 1.5.0 stable, as I consider this bug to be a critical bug.  Why?

When PEAR installs dependent packages that are of dependency type "subpackage" it does a special trick.  First, a little background:

Subpackage dependencies are designed to facilitate the splitting of large, bloated packages into lithe, efficient package and subpackages.  In order to do this, PEAR must cleverly remove the files in the subpackage from the parent package prior to installation, otherwise we'll get a file conflict.  If the packages are installed in the wrong order, this causes serious doodoo to hit the fan.  Look for the fix in the next release candidate, PEAR 1.5.0RC3