composer/composer — pull request #2644 by olvlvl (2014-01-29 13:20:51+00:00)
Title: Improved package sorting

Hi,

While I was trying to resolve an issue that caused files defined by a same package to be scattered across the autoload files array, I noticed that the package sorting algorithm needed to be improved because the position (or importance) of the packages wasn't computed recursively and the resulting positions were sorted using `asort` which produced unpredictable results for packages with the same position, because as you know the sorting algorithm used by PHP is not stable (from the manual: If two members compare as equal, their relative order in the sorted array is undefined).

This new algorithm has two purpose: compute positions (or weights) recursively, so that a package required by a package of weight -10 has at least a weight of -11; use a stable sorting algorithm so that the order of packages with the same weight is preserved.

The following is a comparison of the current algorithm with the proposal algorithm. I'm using the [icybee/modules-nodes](https://packagist.org/packages/icybee/module-nodes) 2.x for testing purpose, because testing the package with the current Composer is causing a fatal error since the files of the [icanboogie/http](https://packagist.org/packages/icanboogie/http) package are loaded after the files of the [icanboogie/icanboogie](https://packagist.org/packages/icanboogie/icanboogie) package, although `icanboogie/icanboogie` requires `icanboogie/http`.

|PACKAGES |SORTED CURRENT |SORTED PROPOSAL |
|----------------------------|--------------------------------|----------------------------------|
|icanboogie/module-installer |icanboogie/module-installer (-7)|icanboogie/common (-81) |
|ircmaxell/password-compat |ircmaxell/password-compat (-6) |icanboogie/inflector (-35) |
|brickrouge/css-class-names |brickrouge/css-class-names (-5) |icanboogie/prototype (-27) |
|icanboogie/inflector |icanboogie/inflector (-4) |icanboogie/datetime (-24) |
|icanboogie/common |icanboogie/common (-3) |icanboogie/event (-21) |
|icanboogie/event |icanboogie/event (-2) |icanboogie/http (-13) |
|icanboogie/datetime |icanboogie/datetime (-1) |icanboogie/errors (-9) |
|icanboogie/prototype |icanboogie/prototype (0) |icanboogie/activerecord (-7) |
|icanboogie/activerecord |icanboogie/activerecord (1) |icanboogie/routing (-6) |
|icybee/module-users |icanboogie/module (6) |icanboogie/operation (-3) |
|icybee/module-sites |icanboogie/operation (6) |icanboogie/module-installer (-2) |
|icanboogie/errors |icanboogie/routing (7) |icanboogie/module (-2) |
|icanboogie/module |icanboogie/errors (7) |ircmaxell/password-compat (-1) |
|icanboogie/http |icanboogie/icanboogie (7) |brickrouge/css-class-names (-1) |
|icanboogie/routing |icanboogie/http (7) |icanboogie/icanboogie (-1) |
|icanboogie/operation |icybee/module-users (9) |icybee/module-users (0) |
|icanboogie/icanboogie |icybee/module-sites (10) |icybee/module-sites (0) |
|icybee/core |icybee/core (17) |icybee/core (0) |

With this proposal, `icanboogie/common` is rightfully at the top since it is used by many packages, although sometimes indirectly; and `icanboogie/http` is well before `icanboogie/icanboogie` since it is used by `icanboogie/routing` and `icanboogie/icanboogie` and by other packages as well although indirectly. Also notice that the order of packages with the same weight is preserved.

Note: This pull request is similar to the [PR #2642](https://github.com/composer/composer/pull/2642), but it features only the diff for the `sortPackageMap()` mehtod.