diff --git a/tests/util/test_check_dependencies.py b/tests/util/test_check_dependencies.py
index aa20fe6780..c1392d8bfc 100644
--- a/tests/util/test_check_dependencies.py
+++ b/tests/util/test_check_dependencies.py
@@ -89,7 +89,8 @@ class TestDependencyChecker(TestCase):
def test_version_reported_as_none(self) -> None:
"""Complain if importlib.metadata.version() returns None.
- This shouldn't normally happen, but it was seen in the wild (#12223).
+ This shouldn't normally happen, but it was seen in the wild
+ (https://github.com/matrix-org/synapse/issues/12223).
"""
with patch(
"synapse.util.check_dependencies.metadata.requires",
@@ -148,7 +149,7 @@ class TestDependencyChecker(TestCase):
"""
Tests that release candidates count as far as satisfying a dependency
is concerned.
- (Regression test, see #12176.)
+ (Regression test, see https://github.com/matrix-org/synapse/issues/12176.)
"""
with patch(
"synapse.util.check_dependencies.metadata.requires",
@@ -162,7 +163,10 @@ class TestDependencyChecker(TestCase):
check_requirements()
def test_setuptools_rust_ignored(self) -> None:
- """Test a workaround for a `poetry build` problem. Reproduces #13926."""
+ """
+ Test a workaround for a `poetry build` problem. Reproduces
+ https://github.com/matrix-org/synapse/issues/13926.
+ """
with patch(
"synapse.util.check_dependencies.metadata.requires",
return_value=["setuptools_rust >= 1.3"],
diff --git a/tests/util/test_itertools.py b/tests/util/test_itertools.py
index 406c16cdcf..fabb05c7e4 100644
--- a/tests/util/test_itertools.py
+++ b/tests/util/test_itertools.py
@@ -13,7 +13,11 @@
# limitations under the License.
from typing import Dict, Iterable, List, Sequence
-from synapse.util.iterutils import chunk_seq, sorted_topologically
+from synapse.util.iterutils import (
+ chunk_seq,
+ sorted_topologically,
+ sorted_topologically_batched,
+)
from tests.unittest import TestCase
@@ -107,3 +111,73 @@ class SortTopologically(TestCase):
graph: Dict[int, List[int]] = {1: [], 2: [1], 3: [2], 4: [3, 2, 1]}
self.assertEqual(list(sorted_topologically([4, 3, 2, 1], graph)), [1, 2, 3, 4])
+
+
+class SortTopologicallyBatched(TestCase):
+ "Test cases for `sorted_topologically_batched`"
+
+ def test_empty(self) -> None:
+ "Test that an empty graph works correctly"
+
+ graph: Dict[int, List[int]] = {}
+ self.assertEqual(list(sorted_topologically_batched([], graph)), [])
+
+ def test_handle_empty_graph(self) -> None:
+ "Test that a graph where a node doesn't have an entry is treated as empty"
+
+ graph: Dict[int, List[int]] = {}
+
+ # For disconnected nodes the output is simply sorted.
+ self.assertEqual(list(sorted_topologically_batched([1, 2], graph)), [[1, 2]])
+
+ def test_disconnected(self) -> None:
+ "Test that a graph with no edges work"
+
+ graph: Dict[int, List[int]] = {1: [], 2: []}
+
+ # For disconnected nodes the output is simply sorted.
+ self.assertEqual(list(sorted_topologically_batched([1, 2], graph)), [[1, 2]])
+
+ def test_linear(self) -> None:
+ "Test that a simple `4 -> 3 -> 2 -> 1` graph works"
+
+ graph: Dict[int, List[int]] = {1: [], 2: [1], 3: [2], 4: [3]}
+
+ self.assertEqual(
+ list(sorted_topologically_batched([4, 3, 2, 1], graph)),
+ [[1], [2], [3], [4]],
+ )
+
+ def test_subset(self) -> None:
+ "Test that only sorting a subset of the graph works"
+ graph: Dict[int, List[int]] = {1: [], 2: [1], 3: [2], 4: [3]}
+
+ self.assertEqual(list(sorted_topologically_batched([4, 3], graph)), [[3], [4]])
+
+ def test_fork(self) -> None:
+ "Test that a forked graph works"
+ graph: Dict[int, List[int]] = {1: [], 2: [1], 3: [1], 4: [2, 3]}
+
+ # Valid orderings are `[1, 3, 2, 4]` or `[1, 2, 3, 4]`, but we should
+ # always get the same one.
+ self.assertEqual(
+ list(sorted_topologically_batched([4, 3, 2, 1], graph)), [[1], [2, 3], [4]]
+ )
+
+ def test_duplicates(self) -> None:
+ "Test that a graph with duplicate edges work"
+ graph: Dict[int, List[int]] = {1: [], 2: [1, 1], 3: [2, 2], 4: [3]}
+
+ self.assertEqual(
+ list(sorted_topologically_batched([4, 3, 2, 1], graph)),
+ [[1], [2], [3], [4]],
+ )
+
+ def test_multiple_paths(self) -> None:
+ "Test that a graph with multiple paths between two nodes work"
+ graph: Dict[int, List[int]] = {1: [], 2: [1], 3: [2], 4: [3, 2, 1]}
+
+ self.assertEqual(
+ list(sorted_topologically_batched([4, 3, 2, 1], graph)),
+ [[1], [2], [3], [4]],
+ )
|
