1 | #!/usr/bin/env python
|
---|
2 |
|
---|
3 | # Copyright 2013 Google Inc. All rights reserved.
|
---|
4 | # Use of this source code is governed by a BSD-style license that can be
|
---|
5 | # found in the LICENSE file.
|
---|
6 |
|
---|
7 | """Unit tests for the input.py file."""
|
---|
8 |
|
---|
9 | import gyp.input
|
---|
10 | import unittest
|
---|
11 |
|
---|
12 |
|
---|
13 | class TestFindCycles(unittest.TestCase):
|
---|
14 | def setUp(self):
|
---|
15 | self.nodes = {}
|
---|
16 | for x in ("a", "b", "c", "d", "e"):
|
---|
17 | self.nodes[x] = gyp.input.DependencyGraphNode(x)
|
---|
18 |
|
---|
19 | def _create_dependency(self, dependent, dependency):
|
---|
20 | dependent.dependencies.append(dependency)
|
---|
21 | dependency.dependents.append(dependent)
|
---|
22 |
|
---|
23 | def test_no_cycle_empty_graph(self):
|
---|
24 | for label, node in self.nodes.items():
|
---|
25 | self.assertEqual([], node.FindCycles())
|
---|
26 |
|
---|
27 | def test_no_cycle_line(self):
|
---|
28 | self._create_dependency(self.nodes["a"], self.nodes["b"])
|
---|
29 | self._create_dependency(self.nodes["b"], self.nodes["c"])
|
---|
30 | self._create_dependency(self.nodes["c"], self.nodes["d"])
|
---|
31 |
|
---|
32 | for label, node in self.nodes.items():
|
---|
33 | self.assertEqual([], node.FindCycles())
|
---|
34 |
|
---|
35 | def test_no_cycle_dag(self):
|
---|
36 | self._create_dependency(self.nodes["a"], self.nodes["b"])
|
---|
37 | self._create_dependency(self.nodes["a"], self.nodes["c"])
|
---|
38 | self._create_dependency(self.nodes["b"], self.nodes["c"])
|
---|
39 |
|
---|
40 | for label, node in self.nodes.items():
|
---|
41 | self.assertEqual([], node.FindCycles())
|
---|
42 |
|
---|
43 | def test_cycle_self_reference(self):
|
---|
44 | self._create_dependency(self.nodes["a"], self.nodes["a"])
|
---|
45 |
|
---|
46 | self.assertEqual(
|
---|
47 | [[self.nodes["a"], self.nodes["a"]]], self.nodes["a"].FindCycles()
|
---|
48 | )
|
---|
49 |
|
---|
50 | def test_cycle_two_nodes(self):
|
---|
51 | self._create_dependency(self.nodes["a"], self.nodes["b"])
|
---|
52 | self._create_dependency(self.nodes["b"], self.nodes["a"])
|
---|
53 |
|
---|
54 | self.assertEqual(
|
---|
55 | [[self.nodes["a"], self.nodes["b"], self.nodes["a"]]],
|
---|
56 | self.nodes["a"].FindCycles(),
|
---|
57 | )
|
---|
58 | self.assertEqual(
|
---|
59 | [[self.nodes["b"], self.nodes["a"], self.nodes["b"]]],
|
---|
60 | self.nodes["b"].FindCycles(),
|
---|
61 | )
|
---|
62 |
|
---|
63 | def test_two_cycles(self):
|
---|
64 | self._create_dependency(self.nodes["a"], self.nodes["b"])
|
---|
65 | self._create_dependency(self.nodes["b"], self.nodes["a"])
|
---|
66 |
|
---|
67 | self._create_dependency(self.nodes["b"], self.nodes["c"])
|
---|
68 | self._create_dependency(self.nodes["c"], self.nodes["b"])
|
---|
69 |
|
---|
70 | cycles = self.nodes["a"].FindCycles()
|
---|
71 | self.assertTrue([self.nodes["a"], self.nodes["b"], self.nodes["a"]] in cycles)
|
---|
72 | self.assertTrue([self.nodes["b"], self.nodes["c"], self.nodes["b"]] in cycles)
|
---|
73 | self.assertEqual(2, len(cycles))
|
---|
74 |
|
---|
75 | def test_big_cycle(self):
|
---|
76 | self._create_dependency(self.nodes["a"], self.nodes["b"])
|
---|
77 | self._create_dependency(self.nodes["b"], self.nodes["c"])
|
---|
78 | self._create_dependency(self.nodes["c"], self.nodes["d"])
|
---|
79 | self._create_dependency(self.nodes["d"], self.nodes["e"])
|
---|
80 | self._create_dependency(self.nodes["e"], self.nodes["a"])
|
---|
81 |
|
---|
82 | self.assertEqual(
|
---|
83 | [
|
---|
84 | [
|
---|
85 | self.nodes["a"],
|
---|
86 | self.nodes["b"],
|
---|
87 | self.nodes["c"],
|
---|
88 | self.nodes["d"],
|
---|
89 | self.nodes["e"],
|
---|
90 | self.nodes["a"],
|
---|
91 | ]
|
---|
92 | ],
|
---|
93 | self.nodes["a"].FindCycles(),
|
---|
94 | )
|
---|
95 |
|
---|
96 |
|
---|
97 | if __name__ == "__main__":
|
---|
98 | unittest.main()
|
---|