ros/rosdep — pull request #3 by wjwwood (2012-04-13 04:10:42+00:00)
Title: Respecting inter-package manager dependency resolution order

## The Problem

Often on OS X there are inter package manager dependencies that get lost in an effort to execute dependency installation with common Installers in groups.

For example, matplotlib is installed via pip, but matplotlib will not install unless pkg-config is installed. pkg-config is installed via homebrew and the `python-matplotlib` rosdep entry depends on the `pkg-config` rosdep entry, so pkg-config gets added to the list of things to be installed because of matplotlib. The problem occurs when the dependencies are installed. Matplotlib will come up to be installed before pkg-config even though it depends on it because they are from different package managers. The relevant rosdep snippet:

....
pkg-config:
osx:
homebrew:
packages: [ pkg-config ]
....
python-matplotlib:
osx:
pip:
packages: [ matplotlib ]
depends: [ pkg-config ]
....

Therefore I added a dependency graph mechanism to prevent this from happening. It can handle circular dependencies and errors from referencing nonexistent rosdep entries. There are tests in the test folder for the dependency_graph module, and all but one of the original tests still pass. (There is an unrelated redhat test that fails because yum isn't on the system)

This seems to work well on OS X, take this comparison of `rosdep install -as`:

Current rosdep2:

∫ rosdep install -as
#[pip] Installation commands:
sudo pip install -U matplotlib
#[homebrew] Installation commands:
brew install eigen
brew install pyside
brew install freeimage
brew install libxml2
brew install jpeg
brew install graphviz
brew install shiboken
brew install cppunit
brew install sip
brew install fltk
brew install sdl_image
brew install opencv
brew install yaml-cpp
brew install pcre++
brew install ros/fuerte/tinyxml
brew install ros/fuerte/swig-wx
brew install libzzip
brew install assimp
brew install libogg
brew install gtk+
brew install tbb
brew install theora
brew install netpbm
brew install ossp-uuid
brew install generatorrunner
brew install pkg-config

Modified rosdep2 with DependencyGraph:

∫ rosdep install -as
#[homebrew] Installation commands:
brew install pkg-config
#[pip] Installation commands:
sudo pip install -U matplotlib
#[homebrew] Installation commands:
brew install eigen
brew install pyside
brew install freeimage
brew install libxml2
brew install jpeg
brew install graphviz
brew install shiboken
brew install cppunit
brew install sip
brew install fltk
brew install sdl_image
brew install opencv
brew install yaml-cpp
brew install pcre++
brew install ros/fuerte/tinyxml
brew install ros/fuerte/swig-wx
brew install libzzip
brew install assimp
brew install libogg
brew install gtk+
brew install tbb
brew install theora
brew install netpbm
brew install ossp-uuid
brew install generatorrunner

## Pull Request Details

Added a dependency graph to the resolve_all function of RosdepLookup so that inter package manager dependency resolution order is preserved.

Major changes:

* The structure commonly referred to `resolutions` or `uninstalled` was previous a dict with the installer_key as the key and a list of install_keys as the value. I had to change that structure to be a list of tuples pairs where the first element of the pair was the installer_key and the second element of the pair is the list of install_keys.
* This propagated to syntax changes in lookup.py, installers.py, main.py, and two of the test files.
* Added the dependency_graph module with the DependencyGraph class which is responsible for collecting the installer_key, install_keys, and dependencies and then ensuring they are a valid dependency graph and then producing an ordered uninstalled list to be passed to install.
* Added nose tests for the dependency_graph module.

## Recommendation of Action

These changes need to be read over by some other people and the changes tested more on Linux before being merged. Specifically there needs to be more tests for error handling in the larger rosdep system when errors occur with the DependencyGraph class.