test_digraph: fix bfs for PYTHONHASHSEED=random

1 files changed, 39 insertions, 4 deletions

diff --git a/pym/portage/tests/util/test_digraph.py b/pym/portage/tests/util/test_digraph.py
index b65c0b18e..4fb1f9571 100644
--- a/pym/portage/tests/util/test_digraph.py
+++ b/pym/portage/tests/util/test_digraph.py
@@ -1,4 +1,4 @@
-# Copyright 2010-2011 Gentoo Foundation
+# Copyright 2010-2012 Gentoo Foundation
 # Distributed under the terms of the GNU General Public License v2
 
 from portage.tests import TestCase
@@ -8,6 +8,41 @@ import portage.util
 
 class DigraphTest(TestCase):
 
+	def _assertBFSEqual(self, result, expected):
+		result_stack = list(result)
+		result_stack.reverse()
+		expected_stack = list(reversed(expected))
+		result_compared = []
+		expected_compared = []
+		while result_stack:
+			if not expected_stack:
+				result_compared.append(result_stack.pop())
+				self.assertEqual(result_compared, expected_compared)
+			expected_set = expected_stack.pop()
+			if not isinstance(expected_set, list):
+				expected_set = [expected_set]
+			expected_set = set(expected_set)
+			while expected_set:
+				if not result_stack:
+					expected_compared.extend(expected_set)
+					self.assertEqual(result_compared, expected_compared)
+				obj = result_stack.pop()
+				try:
+					expected_set.remove(obj)
+				except KeyError:
+					expected_compared.extend(expected_set)
+					result_compared.append(obj)
+					self.assertEqual(result_compared, expected_compared)
+				else:
+					expected_compared.append(obj)
+					result_compared.append(obj)
+		if expected_stack:
+			expected_set = expected_stack.pop()
+			if not isinstance(expected_set, list):
+				expected_set = [expected_set]
+			expected_compared.extend(expected_set)
+			self.assertEqual(result_compared, expected_compared)
+
 	def testBackwardCompatibility(self):
 		g = digraph()
 		f = g.copy()
@@ -71,7 +106,7 @@ class DigraphTest(TestCase):
 			self.assertEqual(x.parent_nodes("A", ignore_priority=-2), ["B"])
 			self.assertEqual(x.parent_nodes("A", ignore_priority=-1), [])
 			self.assertEqual(x.hasallzeros(), False)
-			self.assertEqual(list(x.bfs("A")), [(None, "A"), ("A", "D"), ("D", "C"), ("C", "B")])
+			self._assertBFSEqual(x.bfs("A"), [(None, "A"), ("A", "D"), ("D", "C"), ("C", "B")])
 			self.assertEqual(x.shortest_path("A", "D"), ["A", "D"])
 			self.assertEqual(x.shortest_path("D", "A"), ["D", "C", "B", "A"])
 			self.assertEqual(x.shortest_path("A", "D", ignore_priority=2), None)
@@ -115,7 +150,7 @@ class DigraphTest(TestCase):
 			self.assertEqual(x.parent_nodes("B", ignore_priority=-2), ["A"])
 			self.assertEqual(x.parent_nodes("B", ignore_priority=-1), [])
 			self.assertEqual(x.hasallzeros(), False)
-			self.assertEqual(list(x.bfs("A")), [(None, "A"), ("A", "C"), ("A", "B"), ("C", "E"), ("C", "D")])
+			self._assertBFSEqual(x.bfs("A"), [(None, "A"), [("A", "C"), ("A", "B")], [("C", "E"), ("C", "D")]])
 			self.assertEqual(x.shortest_path("A", "D"), ["A", "C", "D"])
 			self.assertEqual(x.shortest_path("D", "A"), None)
 			self.assertEqual(x.shortest_path("A", "D", ignore_priority=2), None)
@@ -158,7 +193,7 @@ class DigraphTest(TestCase):
 			self.assertEqual(x.parent_nodes("A", ignore_priority=0), ["C"])
 			self.assertEqual(x.parent_nodes("A", ignore_priority=1), [])
 			self.assertEqual(x.hasallzeros(), False)
-			self.assertEqual(list(x.bfs("A")), [(None, "A"), ("A", "C"), ("A", "B")])
+			self._assertBFSEqual(x.bfs("A"), [(None, "A"), [("A", "C"), ("A", "B")]])
 			self.assertEqual(x.shortest_path("A", "C"), ["A", "C"])
 			self.assertEqual(x.shortest_path("C", "A"), ["C", "A"])
 			self.assertEqual(x.shortest_path("A", "C", ignore_priority=0), ["A", "B", "C"])