1import graphlib
2import os
3import unittest
4
5from test.support.script_helper import assert_python_ok
6
7class TestTopologicalSort(unittest.TestCase):
8    def _test_graph(self, graph, expected):
9        def static_order_with_groups(ts):
10            ts.prepare()
11            while ts.is_active():
12                nodes = ts.get_ready()
13                for node in nodes:
14                    ts.done(node)
15                yield tuple(sorted(nodes))
16
17        ts = graphlib.TopologicalSorter(graph)
18        self.assertEqual(list(static_order_with_groups(ts)), list(expected))
19
20        ts = graphlib.TopologicalSorter(graph)
21        # need to be a bit careful comparing the result of ts.static_order and
22        # expected, because the order within a group is dependent on set
23        # iteration order
24        it = iter(ts.static_order())
25        for group in expected:
26            tsgroup = {next(it) for element in group}
27            self.assertEqual(set(group), tsgroup)
28
29    def _assert_cycle(self, graph, cycle):
30        ts = graphlib.TopologicalSorter()
31        for node, dependson in graph.items():
32            ts.add(node, *dependson)
33        try:
34            ts.prepare()
35        except graphlib.CycleError as e:
36            _, seq = e.args
37            self.assertIn(" ".join(map(str, cycle)), " ".join(map(str, seq * 2)))
38        else:
39            raise
40
41    def test_simple_cases(self):
42        self._test_graph(
43            {2: {11}, 9: {11, 8}, 10: {11, 3}, 11: {7, 5}, 8: {7, 3}},
44            [(3, 5, 7), (8, 11), (2, 9, 10)],
45        )
46
47        self._test_graph({1: {}}, [(1,)])
48
49        self._test_graph(
50            {x: {x + 1} for x in range(10)}, [(x,) for x in range(10, -1, -1)]
51        )
52
53        self._test_graph(
54            {2: {3}, 3: {4}, 4: {5}, 5: {1}, 11: {12}, 12: {13}, 13: {14}, 14: {15}},
55            [(1, 15), (5, 14), (4, 13), (3, 12), (2, 11)],
56        )
57
58        self._test_graph(
59            {
60                0: [1, 2],
61                1: [3],
62                2: [5, 6],
63                3: [4],
64                4: [9],
65                5: [3],
66                6: [7],
67                7: [8],
68                8: [4],
69                9: [],
70            },
71            [(9,), (4,), (3, 8), (1, 5, 7), (6,), (2,), (0,)],
72        )
73
74        self._test_graph({0: [1, 2], 1: [], 2: [3], 3: []}, [(1, 3), (2,), (0,)])
75
76        self._test_graph(
77            {0: [1, 2], 1: [], 2: [3], 3: [], 4: [5], 5: [6], 6: []},
78            [(1, 3, 6), (2, 5), (0, 4)],
79        )
80
81    def test_no_dependencies(self):
82        self._test_graph({1: {2}, 3: {4}, 5: {6}}, [(2, 4, 6), (1, 3, 5)])
83
84        self._test_graph({1: set(), 3: set(), 5: set()}, [(1, 3, 5)])
85
86    def test_the_node_multiple_times(self):
87        # Test same node multiple times in dependencies
88        self._test_graph({1: {2}, 3: {4}, 0: [2, 4, 4, 4, 4, 4]}, [(2, 4), (0, 1, 3)])
89
90        # Test adding the same dependency multiple times
91        ts = graphlib.TopologicalSorter()
92        ts.add(1, 2)
93        ts.add(1, 2)
94        ts.add(1, 2)
95        self.assertEqual([*ts.static_order()], [2, 1])
96
97    def test_graph_with_iterables(self):
98        dependson = (2 * x + 1 for x in range(5))
99        ts = graphlib.TopologicalSorter({0: dependson})
100        self.assertEqual(list(ts.static_order()), [1, 3, 5, 7, 9, 0])
101
102    def test_add_dependencies_for_same_node_incrementally(self):
103        # Test same node multiple times
104        ts = graphlib.TopologicalSorter()
105        ts.add(1, 2)
106        ts.add(1, 3)
107        ts.add(1, 4)
108        ts.add(1, 5)
109
110        ts2 = graphlib.TopologicalSorter({1: {2, 3, 4, 5}})
111        self.assertEqual([*ts.static_order()], [*ts2.static_order()])
112
113    def test_empty(self):
114        self._test_graph({}, [])
115
116    def test_cycle(self):
117        # Self cycle
118        self._assert_cycle({1: {1}}, [1, 1])
119        # Simple cycle
120        self._assert_cycle({1: {2}, 2: {1}}, [1, 2, 1])
121        # Indirect cycle
122        self._assert_cycle({1: {2}, 2: {3}, 3: {1}}, [1, 3, 2, 1])
123        # not all elements involved in a cycle
124        self._assert_cycle({1: {2}, 2: {3}, 3: {1}, 5: {4}, 4: {6}}, [1, 3, 2, 1])
125        # Multiple cycles
126        self._assert_cycle({1: {2}, 2: {1}, 3: {4}, 4: {5}, 6: {7}, 7: {6}}, [1, 2, 1])
127        # Cycle in the middle of the graph
128        self._assert_cycle({1: {2}, 2: {3}, 3: {2, 4}, 4: {5}}, [3, 2])
129
130    def test_calls_before_prepare(self):
131        ts = graphlib.TopologicalSorter()
132
133        with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"):
134            ts.get_ready()
135        with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"):
136            ts.done(3)
137        with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"):
138            ts.is_active()
139
140    def test_prepare_multiple_times(self):
141        ts = graphlib.TopologicalSorter()
142        ts.prepare()
143        with self.assertRaisesRegex(ValueError, r"cannot prepare\(\) more than once"):
144            ts.prepare()
145
146    def test_invalid_nodes_in_done(self):
147        ts = graphlib.TopologicalSorter()
148        ts.add(1, 2, 3, 4)
149        ts.add(2, 3, 4)
150        ts.prepare()
151        ts.get_ready()
152
153        with self.assertRaisesRegex(ValueError, "node 2 was not passed out"):
154            ts.done(2)
155        with self.assertRaisesRegex(ValueError, r"node 24 was not added using add\(\)"):
156            ts.done(24)
157
158    def test_done(self):
159        ts = graphlib.TopologicalSorter()
160        ts.add(1, 2, 3, 4)
161        ts.add(2, 3)
162        ts.prepare()
163
164        self.assertEqual(ts.get_ready(), (3, 4))
165        # If we don't mark anything as done, get_ready() returns nothing
166        self.assertEqual(ts.get_ready(), ())
167        ts.done(3)
168        # Now 2 becomes available as 3 is done
169        self.assertEqual(ts.get_ready(), (2,))
170        self.assertEqual(ts.get_ready(), ())
171        ts.done(4)
172        ts.done(2)
173        # Only 1 is missing
174        self.assertEqual(ts.get_ready(), (1,))
175        self.assertEqual(ts.get_ready(), ())
176        ts.done(1)
177        self.assertEqual(ts.get_ready(), ())
178        self.assertFalse(ts.is_active())
179
180    def test_is_active(self):
181        ts = graphlib.TopologicalSorter()
182        ts.add(1, 2)
183        ts.prepare()
184
185        self.assertTrue(ts.is_active())
186        self.assertEqual(ts.get_ready(), (2,))
187        self.assertTrue(ts.is_active())
188        ts.done(2)
189        self.assertTrue(ts.is_active())
190        self.assertEqual(ts.get_ready(), (1,))
191        self.assertTrue(ts.is_active())
192        ts.done(1)
193        self.assertFalse(ts.is_active())
194
195    def test_not_hashable_nodes(self):
196        ts = graphlib.TopologicalSorter()
197        self.assertRaises(TypeError, ts.add, dict(), 1)
198        self.assertRaises(TypeError, ts.add, 1, dict())
199        self.assertRaises(TypeError, ts.add, dict(), dict())
200
201    def test_order_of_insertion_does_not_matter_between_groups(self):
202        def get_groups(ts):
203            ts.prepare()
204            while ts.is_active():
205                nodes = ts.get_ready()
206                ts.done(*nodes)
207                yield set(nodes)
208
209        ts = graphlib.TopologicalSorter()
210        ts.add(3, 2, 1)
211        ts.add(1, 0)
212        ts.add(4, 5)
213        ts.add(6, 7)
214        ts.add(4, 7)
215
216        ts2 = graphlib.TopologicalSorter()
217        ts2.add(1, 0)
218        ts2.add(3, 2, 1)
219        ts2.add(4, 7)
220        ts2.add(6, 7)
221        ts2.add(4, 5)
222
223        self.assertEqual(list(get_groups(ts)), list(get_groups(ts2)))
224
225    def test_static_order_does_not_change_with_the_hash_seed(self):
226        def check_order_with_hash_seed(seed):
227            code = """if 1:
228                import graphlib
229                ts = graphlib.TopologicalSorter()
230                ts.add('blech', 'bluch', 'hola')
231                ts.add('abcd', 'blech', 'bluch', 'a', 'b')
232                ts.add('a', 'a string', 'something', 'b')
233                ts.add('bluch', 'hola', 'abcde', 'a', 'b')
234                print(list(ts.static_order()))
235                """
236            env = os.environ.copy()
237            # signal to assert_python not to do a copy
238            # of os.environ on its own
239            env["__cleanenv"] = True
240            env["PYTHONHASHSEED"] = str(seed)
241            out = assert_python_ok("-c", code, **env)
242            return out
243
244        run1 = check_order_with_hash_seed(1234)
245        run2 = check_order_with_hash_seed(31415)
246
247        self.assertNotEqual(run1, "")
248        self.assertNotEqual(run2, "")
249        self.assertEqual(run1, run2)
250
251if __name__ == "__main__":
252    unittest.main()
253