1#######################################################################
2# Tests for toposort module.
3#
4# Copyright 2014 True Blade Systems, Inc.
5#
6# Licensed under the Apache License, Version 2.0 (the "License");
7# you may not use this file except in compliance with the License.
8# You may obtain a copy of the License at
9#
10# http://www.apache.org/licenses/LICENSE-2.0
11#
12# Unless required by applicable law or agreed to in writing, software
13# distributed under the License is distributed on an "AS IS" BASIS,
14# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15# See the License for the specific language governing permissions and
16# limitations under the License.
17#
18# Notes:
19#
20########################################################################
21
22import unittest
23
24from toposort import toposort, toposort_flatten, CircularDependencyError
25
26class TestCase(unittest.TestCase):
27    def test_simple(self):
28        self.assertEqual(list(toposort({2: {11},
29                                        9: {11, 8},
30                                        10: {11, 3},
31                                        11: {7, 5},
32                                        8: {7, 3},
33                                        })),
34                         [{3, 5, 7},
35                          {8, 11},
36                          {2, 9, 10},
37                          ])
38
39        # make sure self dependencies are ignored
40        self.assertEqual(list(toposort({2: {2, 11},
41                                        9: {11, 8},
42                                        10: {10, 11, 3},
43                                        11: {7, 5},
44                                        8: {7, 3},
45                                        })),
46                         [{3, 5, 7},
47                          {8, 11},
48                          {2, 9, 10},
49                          ])
50
51        self.assertEqual(list(toposort({1: set()})),
52                         [{1}])
53        self.assertEqual(list(toposort({1: {1}})),
54                         [{1}])
55
56    def test_no_dependencies(self):
57        self.assertEqual(list(toposort({1: {2},
58                                        3: {4},
59                                        5: {6},
60                                        })),
61                         [{2, 4, 6}, {1, 3, 5}])
62
63        self.assertEqual(list(toposort({1: set(),
64                                        3: set(),
65                                        5: set(),
66                                        })),
67                         [{1, 3, 5}])
68
69    def test_empty(self):
70        self.assertEqual(list(toposort({})),
71                         [])
72
73    def test_strings(self):
74        self.assertEqual(list(toposort({'2': {'11'},
75                                        '9': {'11', '8'},
76                                        '10': {'11', '3'},
77                                        '11': {'7', '5'},
78                                        '8': {'7', '3'},
79                                        })),
80                         [{'3', '5', '7'},
81                          {'8', '11'},
82                          {'2', '9', '10'},
83                          ])
84
85    def test_objects(self):
86        o2 = object()
87        o3 = object()
88        o5 = object()
89        o7 = object()
90        o8 = object()
91        o9 = object()
92        o10 = object()
93        o11 = object()
94        self.assertEqual(list(toposort({o2: {o11},
95                                        o9: {o11, o8},
96                                        o10: {o11, o3},
97                                        o11: {o7, o5},
98                                        o8: {o7, o3, o8},
99                                        })),
100                         [{o3, o5, o7},
101                          {o8, o11},
102                          {o2, o9, o10},
103                          ])
104
105    def test_cycle(self):
106        # a simple, 2 element cycle
107        # make sure we can catch this both as ValueError and CircularDependencyError
108        self.assertRaises(ValueError, list, toposort({1: {2},
109                                                      2: {1}
110                                                      }))
111        with self.assertRaises(CircularDependencyError) as ex:
112            list(toposort({1: {2},
113                           2: {1}
114                           }))
115        self.assertEqual(ex.exception.data, {1: {2}, 2: {1}})
116
117        # an indirect cycle
118        self.assertRaises(ValueError, list, toposort({1: {2},
119                                                      2: {3},
120                                                      3: {1},
121                                                      }))
122        with self.assertRaises(CircularDependencyError) as ex:
123            list(toposort({1: {2},
124                           2: {3},
125                           3: {1},
126                           }))
127        self.assertEqual(ex.exception.data, {1: {2}, 2: {3}, 3: {1}})
128
129        # not all elements involved in a cycle
130        with self.assertRaises(CircularDependencyError) as ex:
131            list(toposort({1: {2},
132                           2: {3},
133                           3: {1},
134                           5: {4},
135                           4: {6},
136                           }))
137        self.assertEqual(ex.exception.data, {1: set([2]), 2: set([3]), 3: set([1])})
138
139    def test_input_not_modified(self):
140        data = {2: {11},
141                9: {11, 8},
142                10: {11, 3},
143                11: {7, 5},
144                8: {7, 3, 8},  # includes something self-referential
145                }
146        orig = data.copy()
147        results = list(toposort(data))
148        self.assertEqual(data, orig)
149
150    def test_input_not_modified_when_cycle_error(self):
151        data = {1: {2},
152                2: {1},
153                3: {4},
154                }
155        orig = data.copy()
156        self.assertRaises(ValueError, list, toposort(data))
157        self.assertEqual(data, orig)
158
159
160class TestCaseAll(unittest.TestCase):
161    def test_sort_flatten(self):
162        data = {2: {11},
163                9: {11, 8},
164                10: {11, 3},
165                11: {7, 5},
166                8: {7, 3, 8},  # includes something self-referential
167                }
168        expected = [{3, 5, 7}, {8, 11}, {2, 9, 10}]
169        self.assertEqual(list(toposort(data)), expected)
170
171        # now check the sorted results
172        results = []
173        for item in expected:
174            results.extend(sorted(item))
175        self.assertEqual(toposort_flatten(data), results)
176
177        # and the unsorted results. break the results up into groups to compare them
178        actual = toposort_flatten(data, False)
179        results = [{i for i in actual[0:3]}, {i for i in actual[3:5]}, {i for i in actual[5:8]}]
180        self.assertEqual(results, expected)
181
182
183class TestAll(unittest.TestCase):
184    def test_all(self):
185        import toposort
186
187        # check that __all__ in the module contains everything that should be
188        #  public, and only those symbols
189        all = set(toposort.__all__)
190
191        # check that things in __all__ only appear once
192        self.assertEqual(len(all), len(toposort.__all__),
193                         'some symbols appear more than once in __all__')
194
195        # get the list of public symbols
196        found = set(name for name in dir(toposort) if not name.startswith('_'))
197
198        # make sure it matches __all__
199        self.assertEqual(all, found)
200
201unittest.main()
202