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
9import gyp.input
10import unittest
11import sys
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.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
89if __name__ == '__main__':
90  unittest.main()
91