1# Copyright (c) 2012, Willow Garage, Inc. 2# All rights reserved. 3# 4# Redistribution and use in source and binary forms, with or without 5# modification, are permitted provided that the following conditions are met: 6# 7# * Redistributions of source code must retain the above copyright 8# notice, this list of conditions and the following disclaimer. 9# * Redistributions in binary form must reproduce the above copyright 10# notice, this list of conditions and the following disclaimer in the 11# documentation and/or other materials provided with the distribution. 12# * Neither the name of the Willow Garage, Inc. nor the names of its 13# contributors may be used to endorse or promote products derived from 14# this software without specific prior written permission. 15# 16# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 17# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 20# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 23# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 24# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 25# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 26# POSSIBILITY OF SUCH DAMAGE. 27 28# Author William Woodall/wjwwood@gmail.com 29 30from collections import defaultdict 31 32 33class Resolution(dict): 34 """A default dictionary for use in the :class:`DependencyGraph`.""" 35 def __init__(self): 36 super(Resolution, self).__init__() 37 self['installer_key'] = None 38 self['install_keys'] = [] 39 self['dependencies'] = [] 40 self['is_root'] = True 41 42 43class DependencyGraph(defaultdict): 44 """ 45 Provides a mechanism for generating a list of resolutions which preserves the dependency order. 46 47 The :class:`DependencyGraph` inherits from a *defaultdict*, so it can be used as such to load 48 the dependency graph data into it. 49 Example:: 50 51 # Dependency graph:: A-B-C 52 dg = DependencyGraph() 53 dg['A']['installer_key'] = 'a_installer' 54 dg['A']['install_keys'] = ['a'] 55 dg['A']['dependencies'] = ['B'] 56 dg['B']['installer_key'] = 'b_installer' 57 dg['B']['install_keys'] = ['b'] 58 dg['B']['dependencies'] = ['C'] 59 dg['C']['installer_key'] = 'c_installer' 60 dg['C']['install_keys'] = ['c'] 61 dg['C']['dependencies'] = [] 62 result = dg.get_ordered_uninstalled() 63 64 """ 65 def __init__(self): 66 defaultdict.__init__(self, Resolution) 67 68 def detect_cycles(self, rosdep_key, traveled_keys): 69 """ 70 Recursive function to detect cycles in the dependency graph. 71 72 :param rosdep_key: This is the rosdep key to use as the root in the cycle exploration. 73 :param traveled_keys: A list of rosdep_keys that have been traversed thus far. 74 75 :raises: :exc:`AssertionError` if the rosdep_key is in the traveled keys, indicating a cycle has occurred. 76 """ 77 assert rosdep_key not in traveled_keys, 'A cycle in the dependency graph occurred with key `%s`.' % rosdep_key 78 traveled_keys.append(rosdep_key) 79 for dependency in self[rosdep_key]['dependencies']: 80 self.detect_cycles(dependency, traveled_keys) 81 82 def validate(self): 83 """ 84 Performs validations on the dependency graph, like cycle detection and invalid rosdep key detection. 85 86 :raises: :exc:`AssertionError` if a cycle is detected. 87 :raises: :exc:`KeyError` if an invalid rosdep_key is found in the dependency graph. 88 """ 89 for rosdep_key in self: 90 # Ensure all dependencies have definitions 91 # i.e.: Ensure we aren't pointing to invalid rosdep keys 92 for dependency in self[rosdep_key]['dependencies']: 93 if dependency not in self: 94 raise KeyError( 95 'Invalid Graph Structure: rosdep key `%s` does not exist in the dictionary of resolutions.' 96 % dependency) 97 self[dependency]['is_root'] = False 98 # Check each entry for cyclical dependencies 99 for rosdep_key in self: 100 self.detect_cycles(rosdep_key, []) 101 102 def get_ordered_dependency_list(self): 103 """ 104 Generates an ordered list of dependencies using the dependency graph. 105 106 :returns: *[(installer_key, [install_keys])]*, ``[(str, [str])]``. *installer_key* is the key 107 that denotes which installed the accompanying *install_keys* are for. *installer_key* are something 108 like ``apt`` or ``homebrew``. *install_keys* are something like ``boost`` or ``ros-fuerte-ros_comm``. 109 110 :raises: :exc:`AssertionError` if a cycle is detected. 111 :raises: :exc:`KeyError` if an invalid rosdep_key is found in the dependency graph. 112 """ 113 # Validate the graph 114 self.validate() 115 # Generate the dependency list 116 dep_list = [] 117 for rosdep_key in self: 118 if self[rosdep_key]['is_root']: 119 dep_list.extend(self.__get_ordered_uninstalled(rosdep_key)) 120 # Make the list unique and remove empty entries 121 result = [] 122 for item in dep_list: 123 if item not in result and item[1] != []: 124 result.append(item) 125 # Squash the results by installer_key 126 squashed_result = [] 127 previous_installer_key = None 128 for installer_key, resolved in result: 129 if previous_installer_key != installer_key: 130 squashed_result.append((installer_key, [])) 131 previous_installer_key = installer_key 132 squashed_result[-1][1].extend(resolved) 133 return squashed_result 134 135 def __get_ordered_uninstalled(self, key): 136 uninstalled = [] 137 for dependency in self[key]['dependencies']: 138 uninstalled.extend(self.__get_ordered_uninstalled(dependency)) 139 uninstalled.append((self[key]['installer_key'], self[key]['install_keys'])) 140 return uninstalled 141