1####################################################################### 2# Tests for toposort module. 3# 4# Copyright 2014 True Blade Systems, Inc. 5# 6# Licensed under the Apache License, Version 2.0 (the "License"); 7# you may not use this file except in compliance with the License. 8# You may obtain a copy of the License at 9# 10# http://www.apache.org/licenses/LICENSE-2.0 11# 12# Unless required by applicable law or agreed to in writing, software 13# distributed under the License is distributed on an "AS IS" BASIS, 14# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15# See the License for the specific language governing permissions and 16# limitations under the License. 17# 18# Notes: 19# 20######################################################################## 21 22import unittest 23 24from toposort import toposort, toposort_flatten, CircularDependencyError 25 26class TestCase(unittest.TestCase): 27 def test_simple(self): 28 self.assertEqual(list(toposort({2: {11}, 29 9: {11, 8}, 30 10: {11, 3}, 31 11: {7, 5}, 32 8: {7, 3}, 33 })), 34 [{3, 5, 7}, 35 {8, 11}, 36 {2, 9, 10}, 37 ]) 38 39 # make sure self dependencies are ignored 40 self.assertEqual(list(toposort({2: {2, 11}, 41 9: {11, 8}, 42 10: {10, 11, 3}, 43 11: {7, 5}, 44 8: {7, 3}, 45 })), 46 [{3, 5, 7}, 47 {8, 11}, 48 {2, 9, 10}, 49 ]) 50 51 self.assertEqual(list(toposort({1: set()})), 52 [{1}]) 53 self.assertEqual(list(toposort({1: {1}})), 54 [{1}]) 55 56 def test_no_dependencies(self): 57 self.assertEqual(list(toposort({1: {2}, 58 3: {4}, 59 5: {6}, 60 })), 61 [{2, 4, 6}, {1, 3, 5}]) 62 63 self.assertEqual(list(toposort({1: set(), 64 3: set(), 65 5: set(), 66 })), 67 [{1, 3, 5}]) 68 69 def test_empty(self): 70 self.assertEqual(list(toposort({})), 71 []) 72 73 def test_strings(self): 74 self.assertEqual(list(toposort({'2': {'11'}, 75 '9': {'11', '8'}, 76 '10': {'11', '3'}, 77 '11': {'7', '5'}, 78 '8': {'7', '3'}, 79 })), 80 [{'3', '5', '7'}, 81 {'8', '11'}, 82 {'2', '9', '10'}, 83 ]) 84 85 def test_objects(self): 86 o2 = object() 87 o3 = object() 88 o5 = object() 89 o7 = object() 90 o8 = object() 91 o9 = object() 92 o10 = object() 93 o11 = object() 94 self.assertEqual(list(toposort({o2: {o11}, 95 o9: {o11, o8}, 96 o10: {o11, o3}, 97 o11: {o7, o5}, 98 o8: {o7, o3, o8}, 99 })), 100 [{o3, o5, o7}, 101 {o8, o11}, 102 {o2, o9, o10}, 103 ]) 104 105 def test_cycle(self): 106 # a simple, 2 element cycle 107 # make sure we can catch this both as ValueError and CircularDependencyError 108 self.assertRaises(ValueError, list, toposort({1: {2}, 109 2: {1} 110 })) 111 with self.assertRaises(CircularDependencyError) as ex: 112 list(toposort({1: {2}, 113 2: {1} 114 })) 115 self.assertEqual(ex.exception.data, {1: {2}, 2: {1}}) 116 117 # an indirect cycle 118 self.assertRaises(ValueError, list, toposort({1: {2}, 119 2: {3}, 120 3: {1}, 121 })) 122 with self.assertRaises(CircularDependencyError) as ex: 123 list(toposort({1: {2}, 124 2: {3}, 125 3: {1}, 126 })) 127 self.assertEqual(ex.exception.data, {1: {2}, 2: {3}, 3: {1}}) 128 129 # not all elements involved in a cycle 130 with self.assertRaises(CircularDependencyError) as ex: 131 list(toposort({1: {2}, 132 2: {3}, 133 3: {1}, 134 5: {4}, 135 4: {6}, 136 })) 137 self.assertEqual(ex.exception.data, {1: set([2]), 2: set([3]), 3: set([1])}) 138 139 def test_input_not_modified(self): 140 data = {2: {11}, 141 9: {11, 8}, 142 10: {11, 3}, 143 11: {7, 5}, 144 8: {7, 3, 8}, # includes something self-referential 145 } 146 orig = data.copy() 147 results = list(toposort(data)) 148 self.assertEqual(data, orig) 149 150 def test_input_not_modified_when_cycle_error(self): 151 data = {1: {2}, 152 2: {1}, 153 3: {4}, 154 } 155 orig = data.copy() 156 self.assertRaises(ValueError, list, toposort(data)) 157 self.assertEqual(data, orig) 158 159 160class TestCaseAll(unittest.TestCase): 161 def test_sort_flatten(self): 162 data = {2: {11}, 163 9: {11, 8}, 164 10: {11, 3}, 165 11: {7, 5}, 166 8: {7, 3, 8}, # includes something self-referential 167 } 168 expected = [{3, 5, 7}, {8, 11}, {2, 9, 10}] 169 self.assertEqual(list(toposort(data)), expected) 170 171 # now check the sorted results 172 results = [] 173 for item in expected: 174 results.extend(sorted(item)) 175 self.assertEqual(toposort_flatten(data), results) 176 177 # and the unsorted results. break the results up into groups to compare them 178 actual = toposort_flatten(data, False) 179 results = [{i for i in actual[0:3]}, {i for i in actual[3:5]}, {i for i in actual[5:8]}] 180 self.assertEqual(results, expected) 181 182 183class TestAll(unittest.TestCase): 184 def test_all(self): 185 import toposort 186 187 # check that __all__ in the module contains everything that should be 188 # public, and only those symbols 189 all = set(toposort.__all__) 190 191 # check that things in __all__ only appear once 192 self.assertEqual(len(all), len(toposort.__all__), 193 'some symbols appear more than once in __all__') 194 195 # get the list of public symbols 196 found = set(name for name in dir(toposort) if not name.startswith('_')) 197 198 # make sure it matches __all__ 199 self.assertEqual(all, found) 200 201unittest.main() 202