| Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 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 | import sys |
| 12 | |
| 13 | |
| 14 | class 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.iteritems(): |
| 26 | self.assertEquals([], 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.iteritems(): |
| 34 | self.assertEquals([], 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.iteritems(): |
| 42 | self.assertEquals([], node.FindCycles()) |
| 43 | |
| 44 | def test_cycle_self_reference(self): |
| 45 | self._create_dependency(self.nodes['a'], self.nodes['a']) |
| 46 | |
| 47 | self.assertEquals([[self.nodes['a'], self.nodes['a']]], |
| 48 | self.nodes['a'].FindCycles()) |
| 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.assertEquals([[self.nodes['a'], self.nodes['b'], self.nodes['a']]], |
| 55 | self.nodes['a'].FindCycles()) |
| 56 | self.assertEquals([[self.nodes['b'], self.nodes['a'], self.nodes['b']]], |
| 57 | self.nodes['b'].FindCycles()) |
| 58 | |
| 59 | def test_two_cycles(self): |
| 60 | self._create_dependency(self.nodes['a'], self.nodes['b']) |
| 61 | self._create_dependency(self.nodes['b'], self.nodes['a']) |
| 62 | |
| 63 | self._create_dependency(self.nodes['b'], self.nodes['c']) |
| 64 | self._create_dependency(self.nodes['c'], self.nodes['b']) |
| 65 | |
| 66 | cycles = self.nodes['a'].FindCycles() |
| 67 | self.assertTrue( |
| 68 | [self.nodes['a'], self.nodes['b'], self.nodes['a']] in cycles) |
| 69 | self.assertTrue( |
| 70 | [self.nodes['b'], self.nodes['c'], self.nodes['b']] in cycles) |
| 71 | self.assertEquals(2, len(cycles)) |
| 72 | |
| 73 | def test_big_cycle(self): |
| 74 | self._create_dependency(self.nodes['a'], self.nodes['b']) |
| 75 | self._create_dependency(self.nodes['b'], self.nodes['c']) |
| 76 | self._create_dependency(self.nodes['c'], self.nodes['d']) |
| 77 | self._create_dependency(self.nodes['d'], self.nodes['e']) |
| 78 | self._create_dependency(self.nodes['e'], self.nodes['a']) |
| 79 | |
| 80 | self.assertEquals([[self.nodes['a'], |
| 81 | self.nodes['b'], |
| 82 | self.nodes['c'], |
| 83 | self.nodes['d'], |
| 84 | self.nodes['e'], |
| 85 | self.nodes['a']]], |
| 86 | self.nodes['a'].FindCycles()) |
| 87 | |
| 88 | |
| 89 | if __name__ == '__main__': |
| 90 | unittest.main() |