codekingpro/portable-devtools

1#!/usr/bin/env python3
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
9import unittest
10
11import gyp.input
12
13
14class TestFindCycles(unittest.TestCase):
15    def setUp(self):
16        self.nodes = {}
17        for x in ("a", "b", "c", "d", "e"):
18            self.nodes[x] = gyp.input.DependencyGraphNode(x)
19
20    def _create_dependency(self, dependent, dependency):
21        dependent.dependencies.append(dependency)
22        dependency.dependents.append(dependent)
23
24    def test_no_cycle_empty_graph(self):
25        for label, node in self.nodes.items():
26            self.assertEqual([], node.FindCycles())
27
28    def test_no_cycle_line(self):
29        self._create_dependency(self.nodes["a"], self.nodes["b"])
30        self._create_dependency(self.nodes["b"], self.nodes["c"])
31        self._create_dependency(self.nodes["c"], self.nodes["d"])
32
33        for label, node in self.nodes.items():
34            self.assertEqual([], node.FindCycles())
35
36    def test_no_cycle_dag(self):
37        self._create_dependency(self.nodes["a"], self.nodes["b"])
38        self._create_dependency(self.nodes["a"], self.nodes["c"])
39        self._create_dependency(self.nodes["b"], self.nodes["c"])
40
41        for label, node in self.nodes.items():
42            self.assertEqual([], node.FindCycles())
43
44    def test_cycle_self_reference(self):
45        self._create_dependency(self.nodes["a"], self.nodes["a"])
46
47        self.assertEqual(
48            [[self.nodes["a"], self.nodes["a"]]], self.nodes["a"].FindCycles()
49        )
50
51    def test_cycle_two_nodes(self):
52        self._create_dependency(self.nodes["a"], self.nodes["b"])
53        self._create_dependency(self.nodes["b"], self.nodes["a"])
54
55        self.assertEqual(
56            [[self.nodes["a"], self.nodes["b"], self.nodes["a"]]],
57            self.nodes["a"].FindCycles(),
58        )
59        self.assertEqual(
60            [[self.nodes["b"], self.nodes["a"], self.nodes["b"]]],
61            self.nodes["b"].FindCycles(),
62        )
63
64    def test_two_cycles(self):
65        self._create_dependency(self.nodes["a"], self.nodes["b"])
66        self._create_dependency(self.nodes["b"], self.nodes["a"])
67
68        self._create_dependency(self.nodes["b"], self.nodes["c"])
69        self._create_dependency(self.nodes["c"], self.nodes["b"])
70
71        cycles = self.nodes["a"].FindCycles()
72        self.assertTrue([self.nodes["a"], self.nodes["b"], self.nodes["a"]] in cycles)
73        self.assertTrue([self.nodes["b"], self.nodes["c"], self.nodes["b"]] in cycles)
74        self.assertEqual(2, len(cycles))
75
76    def test_big_cycle(self):
77        self._create_dependency(self.nodes["a"], self.nodes["b"])
78        self._create_dependency(self.nodes["b"], self.nodes["c"])
79        self._create_dependency(self.nodes["c"], self.nodes["d"])
80        self._create_dependency(self.nodes["d"], self.nodes["e"])
81        self._create_dependency(self.nodes["e"], self.nodes["a"])
82
83        self.assertEqual(
84            [
85                [
86                    self.nodes["a"],
87                    self.nodes["b"],
88                    self.nodes["c"],
89                    self.nodes["d"],
90                    self.nodes["e"],
91                    self.nodes["a"],
92                ]
93            ],
94            self.nodes["a"].FindCycles(),
95        )
96
97
98if __name__ == "__main__":
99    unittest.main()
100