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