Fixed #31051 -- Allowed dumpdata to handle circular references in natural keys.

Since #26291 forward references in natural keys are properly handled by
loaddata, so sorting depenencies in dumpdata doesn't need to break on
cycles. This patch allows circular references in natural keys by
breaking sort_depenencies() on loops.

5 files changed, 70 insertions, 13 deletions

diff --git a/django/core/management/commands/dumpdata.py b/django/core/management/commands/dumpdata.py
index 2968f74805..247b0f20fd 100644
--- a/django/core/management/commands/dumpdata.py
+++ b/django/core/management/commands/dumpdata.py
@@ -144,7 +144,7 @@ class Command(BaseCommand):
             Collate the objects to be serialized. If count_only is True, just
             count the number of objects to be serialized.
             """
-            models = serializers.sort_dependencies(app_list.items())
+            models = serializers.sort_dependencies(app_list.items(), allow_cycles=True)
             for model in models:
                 if model in excluded_models:
                     continue
diff --git a/django/core/serializers/__init__.py b/django/core/serializers/__init__.py
index d0e504ade3..5e16a7560f 100644
--- a/django/core/serializers/__init__.py
+++ b/django/core/serializers/__init__.py
@@ -156,12 +156,15 @@ def _load_serializers():
     _serializers = serializers
 
 
-def sort_dependencies(app_list):
+def sort_dependencies(app_list, allow_cycles=False):
     """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.
+
+    If allow_cycles is True, return the best-effort ordering that will respect
+    most of dependencies but ignore some of them to break the cycles.
     """
     # Process the list of models, and get the list of dependencies
     model_dependencies = []
@@ -222,13 +225,20 @@ def sort_dependencies(app_list):
             else:
                 skipped.append((model, deps))
         if not changed:
-            raise RuntimeError(
-                "Can't resolve dependencies for %s in serialized app list." %
-                ', '.join(
-                    model._meta.label
-                    for model, deps in sorted(skipped, key=lambda obj: obj[0].__name__)
+            if allow_cycles:
+                # If cycles are allowed, add the last skipped model and ignore
+                # its dependencies. This could be improved by some graph
+                # analysis to ignore as few dependencies as possible.
+                model, _ = skipped.pop()
+                model_list.append(model)
+            else:
+                raise RuntimeError(
+                    "Can't resolve dependencies for %s in serialized app list."
+                    % ', '.join(
+                        model._meta.label
+                        for model, deps in sorted(skipped, key=lambda obj: obj[0].__name__)
+                    ),
                 )
-            )
         model_dependencies = skipped
 
     return model_list
diff --git a/tests/fixtures/fixtures/circular_reference_natural_key.json b/tests/fixtures/fixtures/circular_reference_natural_key.json
new file mode 100644
index 0000000000..d9dbe30aac
--- /dev/null
+++ b/tests/fixtures/fixtures/circular_reference_natural_key.json
@@ -0,0 +1,16 @@
+[
+  {
+    "model": "fixtures.circulara",
+    "fields": {
+      "key": "x",
+      "obj": ["y"]
+    }
+  },
+  {
+    "model": "fixtures.circularb",
+    "fields": {
+      "key": "y",
+      "obj": ["x"]
+    }
+  }
+]
diff --git a/tests/fixtures/models.py b/tests/fixtures/models.py
index db7d7fbd7a..ac64e7b82e 100644
--- a/tests/fixtures/models.py
+++ b/tests/fixtures/models.py
@@ -118,16 +118,17 @@ class PrimaryKeyUUIDModel(models.Model):
     id = models.UUIDField(primary_key=True, default=uuid.uuid4)
 
 
+class NaturalKeyManager(models.Manager):
+    def get_by_natural_key(self, key):
+        return self.get(key=key)
+
+
 class NaturalKeyThing(models.Model):
     key = models.CharField(max_length=100, unique=True)
     other_thing = models.ForeignKey('NaturalKeyThing', on_delete=models.CASCADE, null=True)
     other_things = models.ManyToManyField('NaturalKeyThing', related_name='thing_m2m_set')
 
-    class Manager(models.Manager):
-        def get_by_natural_key(self, key):
-            return self.get(key=key)
-
-    objects = Manager()
+    objects = NaturalKeyManager()
 
     def natural_key(self):
         return (self.key,)
@@ -140,7 +141,17 @@ class CircularA(models.Model):
     key = models.CharField(max_length=3, unique=True)
     obj = models.ForeignKey('CircularB', models.SET_NULL, null=True)
 
+    objects = NaturalKeyManager()
+
+    def natural_key(self):
+        return (self.key,)
+
 
 class CircularB(models.Model):
     key = models.CharField(max_length=3, unique=True)
     obj = models.ForeignKey('CircularA', models.SET_NULL, null=True)
+
+    objects = NaturalKeyManager()
+
+    def natural_key(self):
+        return (self.key,)
diff --git a/tests/fixtures/tests.py b/tests/fixtures/tests.py
index 2ed17d57be..1e723a7b66 100644
--- a/tests/fixtures/tests.py
+++ b/tests/fixtures/tests.py
@@ -880,3 +880,23 @@ class CircularReferenceTests(DumpDataAssertMixin, TestCase):
             '{"model": "fixtures.circularb", "pk": 1, '
             '"fields": {"key": "y", "obj": 1}}]',
         )
+
+    def test_circular_reference_natural_key(self):
+        management.call_command(
+            'loaddata',
+            'circular_reference_natural_key.json',
+            verbosity=0,
+        )
+        obj_a = CircularA.objects.get()
+        obj_b = CircularB.objects.get()
+        self.assertEqual(obj_a.obj, obj_b)
+        self.assertEqual(obj_b.obj, obj_a)
+        self._dumpdata_assert(
+            ['fixtures'],
+            '[{"model": "fixtures.circulara", '
+            '"fields": {"key": "x", "obj": ["y"]}}, '
+            '{"model": "fixtures.circularb", '
+            '"fields": {"key": "y", "obj": ["x"]}}]',
+            natural_primary_keys=True,
+            natural_foreign_keys=True,
+        )