Fixed #23660 -- Moved sort_dependencies to core.

4 files changed, 104 insertions, 105 deletions

diff --git a/django/core/management/commands/dumpdata.py b/django/core/management/commands/dumpdata.py
index b5a3de5fd4..9d506d1611 100644
--- a/django/core/management/commands/dumpdata.py
+++ b/django/core/management/commands/dumpdata.py
@@ -138,7 +138,7 @@ class Command(BaseCommand):
 
         def get_objects():
             # Collate the objects to be serialized.
-            for model in sort_dependencies(app_list.items()):
+            for model in serializers.sort_dependencies(app_list.items()):
                 if model in excluded_models:
                     continue
                 if not model._meta.proxy and router.allow_migrate(using, model):
@@ -168,82 +168,3 @@ class Command(BaseCommand):
             if show_traceback:
                 raise
             raise CommandError("Unable to serialize database: %s" % e)
-
-
-def sort_dependencies(app_list):
-    """Sort a list of (app_config, models) pairs into a single list of models.
-
-    The single list of models is sorted so that any model with a natural key
-    is serialized before a normal model, and any model with a natural key
-    dependency has it's dependencies serialized first.
-    """
-    # Process the list of models, and get the list of dependencies
-    model_dependencies = []
-    models = set()
-    for app_config, model_list in app_list:
-        if model_list is None:
-            model_list = app_config.get_models()
-
-        for model in model_list:
-            models.add(model)
-            # Add any explicitly defined dependencies
-            if hasattr(model, 'natural_key'):
-                deps = getattr(model.natural_key, 'dependencies', [])
-                if deps:
-                    deps = [apps.get_model(dep) for dep in deps]
-            else:
-                deps = []
-
-            # Now add a dependency for any FK relation with a model that
-            # defines a natural key
-            for field in model._meta.fields:
-                if hasattr(field.rel, 'to'):
-                    rel_model = field.rel.to
-                    if hasattr(rel_model, 'natural_key') and rel_model != model:
-                        deps.append(rel_model)
-            # Also add a dependency for any simple M2M relation with a model
-            # that defines a natural key.  M2M relations with explicit through
-            # models don't count as dependencies.
-            for field in model._meta.many_to_many:
-                if field.rel.through._meta.auto_created:
-                    rel_model = field.rel.to
-                    if hasattr(rel_model, 'natural_key') and rel_model != model:
-                        deps.append(rel_model)
-            model_dependencies.append((model, deps))
-
-    model_dependencies.reverse()
-    # Now sort the models to ensure that dependencies are met. This
-    # is done by repeatedly iterating over the input list of models.
-    # If all the dependencies of a given model are in the final list,
-    # that model is promoted to the end of the final list. This process
-    # continues until the input list is empty, or we do a full iteration
-    # over the input models without promoting a model to the final list.
-    # If we do a full iteration without a promotion, that means there are
-    # circular dependencies in the list.
-    model_list = []
-    while model_dependencies:
-        skipped = []
-        changed = False
-        while model_dependencies:
-            model, deps = model_dependencies.pop()
-
-            # If all of the models in the dependency list are either already
-            # on the final model list, or not on the original serialization list,
-            # then we've found another model with all it's dependencies satisfied.
-            found = True
-            for candidate in ((d not in models or d in model_list) for d in deps):
-                if not candidate:
-                    found = False
-            if found:
-                model_list.append(model)
-                changed = True
-            else:
-                skipped.append((model, deps))
-        if not changed:
-            raise CommandError("Can't resolve dependencies for %s in serialized app list." %
-                ', '.join('%s.%s' % (model._meta.app_label, model._meta.object_name)
-                for model, deps in sorted(skipped, key=lambda obj: obj[0].__name__))
-            )
-        model_dependencies = skipped
-
-    return model_list
diff --git a/django/core/serializers/__init__.py b/django/core/serializers/__init__.py
index 68200e754f..5d049a4f91 100644
--- a/django/core/serializers/__init__.py
+++ b/django/core/serializers/__init__.py
@@ -18,6 +18,7 @@ To add your own serializers, use the SERIALIZATION_MODULES setting::
 
 import importlib
 
+from django.apps import apps
 from django.conf import settings
 from django.utils import six
 from django.core.serializers.base import SerializerDoesNotExist
@@ -154,3 +155,82 @@ def _load_serializers():
         for format in settings.SERIALIZATION_MODULES:
             register_serializer(format, settings.SERIALIZATION_MODULES[format], serializers)
     _serializers = serializers
+
+
+def sort_dependencies(app_list):
+    """Sort a list of (app_config, models) pairs into a single list of models.
+
+    The single list of models is sorted so that any model with a natural key
+    is serialized before a normal model, and any model with a natural key
+    dependency has it's dependencies serialized first.
+    """
+    # Process the list of models, and get the list of dependencies
+    model_dependencies = []
+    models = set()
+    for app_config, model_list in app_list:
+        if model_list is None:
+            model_list = app_config.get_models()
+
+        for model in model_list:
+            models.add(model)
+            # Add any explicitly defined dependencies
+            if hasattr(model, 'natural_key'):
+                deps = getattr(model.natural_key, 'dependencies', [])
+                if deps:
+                    deps = [apps.get_model(dep) for dep in deps]
+            else:
+                deps = []
+
+            # Now add a dependency for any FK relation with a model that
+            # defines a natural key
+            for field in model._meta.fields:
+                if hasattr(field.rel, 'to'):
+                    rel_model = field.rel.to
+                    if hasattr(rel_model, 'natural_key') and rel_model != model:
+                        deps.append(rel_model)
+            # Also add a dependency for any simple M2M relation with a model
+            # that defines a natural key.  M2M relations with explicit through
+            # models don't count as dependencies.
+            for field in model._meta.many_to_many:
+                if field.rel.through._meta.auto_created:
+                    rel_model = field.rel.to
+                    if hasattr(rel_model, 'natural_key') and rel_model != model:
+                        deps.append(rel_model)
+            model_dependencies.append((model, deps))
+
+    model_dependencies.reverse()
+    # Now sort the models to ensure that dependencies are met. This
+    # is done by repeatedly iterating over the input list of models.
+    # If all the dependencies of a given model are in the final list,
+    # that model is promoted to the end of the final list. This process
+    # continues until the input list is empty, or we do a full iteration
+    # over the input models without promoting a model to the final list.
+    # If we do a full iteration without a promotion, that means there are
+    # circular dependencies in the list.
+    model_list = []
+    while model_dependencies:
+        skipped = []
+        changed = False
+        while model_dependencies:
+            model, deps = model_dependencies.pop()
+
+            # If all of the models in the dependency list are either already
+            # on the final model list, or not on the original serialization list,
+            # then we've found another model with all it's dependencies satisfied.
+            found = True
+            for candidate in ((d not in models or d in model_list) for d in deps):
+                if not candidate:
+                    found = False
+            if found:
+                model_list.append(model)
+                changed = True
+            else:
+                skipped.append((model, deps))
+        if not changed:
+            raise RuntimeError("Can't resolve dependencies for %s in serialized app list." %
+                ', '.join('%s.%s' % (model._meta.app_label, model._meta.object_name)
+                for model, deps in sorted(skipped, key=lambda obj: obj[0].__name__))
+            )
+        model_dependencies = skipped
+
+    return model_list
diff --git a/django/db/backends/creation.py b/django/db/backends/creation.py
index 9077399adc..723027a575 100644
--- a/django/db/backends/creation.py
+++ b/django/db/backends/creation.py
@@ -8,7 +8,6 @@ from django.utils.encoding import force_bytes
 from django.utils.functional import cached_property
 from django.utils.six.moves import input
 from django.utils.six import StringIO
-from django.core.management.commands.dumpdata import sort_dependencies
 from django.db import router
 from django.apps import apps
 from django.core import serializers
@@ -425,7 +424,7 @@ class BaseDatabaseCreation(object):
 
         # Make a function to iteratively return every object
         def get_objects():
-            for model in sort_dependencies(app_list):
+            for model in serializers.sort_dependencies(app_list):
                 if (not model._meta.proxy and model._meta.managed and
                         router.allow_migrate(self.connection.alias, model)):
                     queryset = model._default_manager.using(self.connection.alias).order_by(model._meta.pk.name)
diff --git a/tests/fixtures_regress/tests.py b/tests/fixtures_regress/tests.py
index f8f13f824a..62b1dca3a0 100644
--- a/tests/fixtures_regress/tests.py
+++ b/tests/fixtures_regress/tests.py
@@ -11,7 +11,6 @@ from django.core import serializers
 from django.core.serializers.base import DeserializationError
 from django.core import management
 from django.core.management.base import CommandError
-from django.core.management.commands.dumpdata import sort_dependencies
 from django.db import transaction, IntegrityError
 from django.db.models import signals
 from django.test import (TestCase, TransactionTestCase, skipIfDBFeature,
@@ -579,7 +578,7 @@ class NaturalKeyFixtureTests(TestCase):
         Store *must* be serialized before then Person, and both
         must be serialized before Book.
         """
-        sorted_deps = sort_dependencies(
+        sorted_deps = serializers.sort_dependencies(
             [('fixtures_regress', [Book, Person, Store])]
         )
         self.assertEqual(
@@ -588,7 +587,7 @@ class NaturalKeyFixtureTests(TestCase):
         )
 
     def test_dependency_sorting_2(self):
-        sorted_deps = sort_dependencies(
+        sorted_deps = serializers.sort_dependencies(
             [('fixtures_regress', [Book, Store, Person])]
         )
         self.assertEqual(
@@ -597,7 +596,7 @@ class NaturalKeyFixtureTests(TestCase):
         )
 
     def test_dependency_sorting_3(self):
-        sorted_deps = sort_dependencies(
+        sorted_deps = serializers.sort_dependencies(
             [('fixtures_regress', [Store, Book, Person])]
         )
         self.assertEqual(
@@ -606,7 +605,7 @@ class NaturalKeyFixtureTests(TestCase):
         )
 
     def test_dependency_sorting_4(self):
-        sorted_deps = sort_dependencies(
+        sorted_deps = serializers.sort_dependencies(
             [('fixtures_regress', [Store, Person, Book])]
         )
         self.assertEqual(
@@ -615,7 +614,7 @@ class NaturalKeyFixtureTests(TestCase):
         )
 
     def test_dependency_sorting_5(self):
-        sorted_deps = sort_dependencies(
+        sorted_deps = serializers.sort_dependencies(
             [('fixtures_regress', [Person, Book, Store])]
         )
         self.assertEqual(
@@ -624,7 +623,7 @@ class NaturalKeyFixtureTests(TestCase):
         )
 
     def test_dependency_sorting_6(self):
-        sorted_deps = sort_dependencies(
+        sorted_deps = serializers.sort_dependencies(
             [('fixtures_regress', [Person, Store, Book])]
         )
         self.assertEqual(
@@ -633,7 +632,7 @@ class NaturalKeyFixtureTests(TestCase):
         )
 
     def test_dependency_sorting_dangling(self):
-        sorted_deps = sort_dependencies(
+        sorted_deps = serializers.sort_dependencies(
             [('fixtures_regress', [Person, Circle1, Store, Book])]
         )
         self.assertEqual(
@@ -643,38 +642,38 @@ class NaturalKeyFixtureTests(TestCase):
 
     def test_dependency_sorting_tight_circular(self):
         self.assertRaisesMessage(
-            CommandError,
+            RuntimeError,
             """Can't resolve dependencies for fixtures_regress.Circle1, fixtures_regress.Circle2 in serialized app list.""",
-            sort_dependencies,
+            serializers.sort_dependencies,
             [('fixtures_regress', [Person, Circle2, Circle1, Store, Book])],
         )
 
     def test_dependency_sorting_tight_circular_2(self):
         self.assertRaisesMessage(
-            CommandError,
+            RuntimeError,
             """Can't resolve dependencies for fixtures_regress.Circle1, fixtures_regress.Circle2 in serialized app list.""",
-            sort_dependencies,
+            serializers.sort_dependencies,
             [('fixtures_regress', [Circle1, Book, Circle2])],
         )
 
     def test_dependency_self_referential(self):
         self.assertRaisesMessage(
-            CommandError,
+            RuntimeError,
             """Can't resolve dependencies for fixtures_regress.Circle3 in serialized app list.""",
-            sort_dependencies,
+            serializers.sort_dependencies,
             [('fixtures_regress', [Book, Circle3])],
         )
 
     def test_dependency_sorting_long(self):
         self.assertRaisesMessage(
-            CommandError,
+            RuntimeError,
             """Can't resolve dependencies for fixtures_regress.Circle1, fixtures_regress.Circle2, fixtures_regress.Circle3 in serialized app list.""",
-            sort_dependencies,
+            serializers.sort_dependencies,
             [('fixtures_regress', [Person, Circle2, Circle1, Circle3, Store, Book])],
         )
 
     def test_dependency_sorting_normal(self):
-        sorted_deps = sort_dependencies(
+        sorted_deps = serializers.sort_dependencies(
             [('fixtures_regress', [Person, ExternalDependency, Book])]
         )
         self.assertEqual(
@@ -720,7 +719,7 @@ class M2MNaturalKeyFixtureTests(TestCase):
         #14226, namely if M2M checks are removed from sort_dependencies
         altogether.
         """
-        sorted_deps = sort_dependencies(
+        sorted_deps = serializers.sort_dependencies(
             [('fixtures_regress', [M2MSimpleA, M2MSimpleB])]
         )
         self.assertEqual(sorted_deps, [M2MSimpleB, M2MSimpleA])
@@ -731,10 +730,10 @@ class M2MNaturalKeyFixtureTests(TestCase):
         fail loudly
         """
         self.assertRaisesMessage(
-            CommandError,
+            RuntimeError,
             "Can't resolve dependencies for fixtures_regress.M2MSimpleCircularA, "
             "fixtures_regress.M2MSimpleCircularB in serialized app list.",
-            sort_dependencies,
+            serializers.sort_dependencies,
             [('fixtures_regress', [M2MSimpleCircularA, M2MSimpleCircularB])]
         )
 
@@ -743,7 +742,7 @@ class M2MNaturalKeyFixtureTests(TestCase):
         M2M relations with explicit through models should NOT count as
         dependencies.  The through model itself will have dependencies, though.
         """
-        sorted_deps = sort_dependencies(
+        sorted_deps = serializers.sort_dependencies(
             [('fixtures_regress', [M2MComplexA, M2MComplexB, M2MThroughAB])]
         )
         # Order between M2MComplexA and M2MComplexB doesn't matter. The through
@@ -758,7 +757,7 @@ class M2MNaturalKeyFixtureTests(TestCase):
                                      M2MComplexCircular1C, M2MCircular1ThroughAB,
                                      M2MCircular1ThroughBC, M2MCircular1ThroughCA)
         try:
-            sorted_deps = sort_dependencies(
+            sorted_deps = serializers.sort_dependencies(
                 [('fixtures_regress', [A, B, C, AtoB, BtoC, CtoA])]
             )
         except CommandError:
@@ -778,7 +777,7 @@ class M2MNaturalKeyFixtureTests(TestCase):
         This test tests the circularity with explicit natural_key.dependencies
         """
         try:
-            sorted_deps = sort_dependencies([
+            sorted_deps = serializers.sort_dependencies([
                 ('fixtures_regress', [
                     M2MComplexCircular2A,
                     M2MComplexCircular2B,