From 77e53da127cfb5d4f0c9a3540a02ff24f04fe9e2 Mon Sep 17 00:00:00 2001
From: Matthias Kestenholz <mk@feinheit.ch>
Date: Sun, 24 Feb 2019 13:08:59 +0100
Subject: [2.2.x] Refs #30179 -- Moved topological sort functions to
 django.utils.

Backport of e04209e181c99ac16ca769d115ac640015a83757 from master.
---
 django/db/migrations/autodetector.py       |  3 +--
 django/db/migrations/topological_sort.py   | 32 --------------------------
 django/utils/topological_sort.py           | 36 ++++++++++++++++++++++++++++++
 tests/utils_tests/test_topological_sort.py | 24 ++++++++++++++++++++
 4 files changed, 61 insertions(+), 34 deletions(-)
 delete mode 100644 django/db/migrations/topological_sort.py
 create mode 100644 django/utils/topological_sort.py
 create mode 100644 tests/utils_tests/test_topological_sort.py

diff --git a/django/db/migrations/autodetector.py b/django/db/migrations/autodetector.py
index 3d3eeb9230..0dc1c77c53 100644
--- a/django/db/migrations/autodetector.py
+++ b/django/db/migrations/autodetector.py
@@ -12,8 +12,7 @@ from django.db.migrations.questioner import MigrationQuestioner
 from django.db.migrations.utils import (
     COMPILED_REGEX_TYPE, RegexObject, get_migration_name_timestamp,
 )
-
-from .topological_sort import stable_topological_sort
+from django.utils.topological_sort import stable_topological_sort
 
 
 class MigrationAutodetector:
diff --git a/django/db/migrations/topological_sort.py b/django/db/migrations/topological_sort.py
deleted file mode 100644
index e0a22c9236..0000000000
--- a/django/db/migrations/topological_sort.py
+++ /dev/null
@@ -1,32 +0,0 @@
-def topological_sort_as_sets(dependency_graph):
-    """
-    Variation of Kahn's algorithm (1962) that returns sets.
-
-    Take a dependency graph as a dictionary of node => dependencies.
-
-    Yield sets of items in topological order, where the first set contains
-    all nodes without dependencies, and each following set contains all
-    nodes that may depend on the nodes only in the previously yielded sets.
-    """
-    todo = dependency_graph.copy()
-    while todo:
-        current = {node for node, deps in todo.items() if not deps}
-
-        if not current:
-            raise ValueError('Cyclic dependency in graph: {}'.format(
-                ', '.join(repr(x) for x in todo.items())))
-
-        yield current
-
-        # remove current from todo's nodes & dependencies
-        todo = {node: (dependencies - current) for node, dependencies in
-                todo.items() if node not in current}
-
-
-def stable_topological_sort(l, dependency_graph):
-    result = []
-    for layer in topological_sort_as_sets(dependency_graph):
-        for node in l:
-            if node in layer:
-                result.append(node)
-    return result
diff --git a/django/utils/topological_sort.py b/django/utils/topological_sort.py
new file mode 100644
index 0000000000..3f8ea0f2e4
--- /dev/null
+++ b/django/utils/topological_sort.py
@@ -0,0 +1,36 @@
+class CyclicDependencyError(ValueError):
+    pass
+
+
+def topological_sort_as_sets(dependency_graph):
+    """
+    Variation of Kahn's algorithm (1962) that returns sets.
+
+    Take a dependency graph as a dictionary of node => dependencies.
+
+    Yield sets of items in topological order, where the first set contains
+    all nodes without dependencies, and each following set contains all
+    nodes that may depend on the nodes only in the previously yielded sets.
+    """
+    todo = dependency_graph.copy()
+    while todo:
+        current = {node for node, deps in todo.items() if not deps}
+
+        if not current:
+            raise CyclicDependencyError('Cyclic dependency in graph: {}'.format(
+                ', '.join(repr(x) for x in todo.items())))
+
+        yield current
+
+        # remove current from todo's nodes & dependencies
+        todo = {node: (dependencies - current) for node, dependencies in
+                todo.items() if node not in current}
+
+
+def stable_topological_sort(l, dependency_graph):
+    result = []
+    for layer in topological_sort_as_sets(dependency_graph):
+        for node in l:
+            if node in layer:
+                result.append(node)
+    return result
diff --git a/tests/utils_tests/test_topological_sort.py b/tests/utils_tests/test_topological_sort.py
new file mode 100644
index 0000000000..ed8f9fd5a6
--- /dev/null
+++ b/tests/utils_tests/test_topological_sort.py
@@ -0,0 +1,24 @@
+from django.test import SimpleTestCase
+from django.utils.topological_sort import (
+    CyclicDependencyError, stable_topological_sort, topological_sort_as_sets,
+)
+
+
+class TopologicalSortTests(SimpleTestCase):
+
+    def test_basic(self):
+        dependency_graph = {
+            1: {2, 3},
+            2: set(),
+            3: set(),
+            4: {5, 6},
+            5: set(),
+            6: {5},
+        }
+        self.assertEqual(list(topological_sort_as_sets(dependency_graph)), [{2, 3, 5}, {1, 6}, {4}])
+        self.assertEqual(stable_topological_sort([1, 2, 3, 4, 5, 6], dependency_graph), [2, 3, 5, 1, 6, 4])
+
+    def test_cyclic_dependency(self):
+        msg = 'Cyclic dependency in graph: '
+        with self.assertRaisesMessage(CyclicDependencyError, msg):
+            list(topological_sort_as_sets({1: {2}, 2: {1}}))
-- 
cgit v1.3