Fixed #22861: Internal migrations done first so __first__ works

Thanks to Chris Beaven.

2 files changed, 13 insertions, 2 deletions

diff --git a/django/db/migrations/graph.py b/django/db/migrations/graph.py
index 8e034f2bd0..59578b110f 100644
--- a/django/db/migrations/graph.py
+++ b/django/db/migrations/graph.py
@@ -74,7 +74,7 @@ class MigrationGraph(object):
         for node in self.nodes:
             if not any(key[0] == node[0] for key in self.dependencies.get(node, set())) and (not app or app == node[0]):
                 roots.add(node)
-        return roots
+        return sorted(roots)
 
     def leaf_nodes(self, app=None):
         """
@@ -88,7 +88,7 @@ class MigrationGraph(object):
         for node in self.nodes:
             if not any(key[0] == node[0] for key in self.dependents.get(node, set())) and (not app or app == node[0]):
                 leaves.add(node)
-        return leaves
+        return sorted(leaves)
 
     def dfs(self, start, get_children):
         """
diff --git a/django/db/migrations/loader.py b/django/db/migrations/loader.py
index 86987db02c..5465f0ad18 100644
--- a/django/db/migrations/loader.py
+++ b/django/db/migrations/loader.py
@@ -223,8 +223,19 @@ class MigrationLoader(object):
         self.graph = MigrationGraph()
         for key, migration in normal.items():
             self.graph.add_node(key, migration)
+        # Add all internal dependencies first to ensure __first__ dependencies
+        # find the correct root node.
         for key, migration in normal.items():
             for parent in migration.dependencies:
+                if parent[0] != key[0] or parent[1] == '__first__':
+                    # Ignore __first__ references to the same app (#22325)
+                    continue
+                self.graph.add_dependency(key, parent)
+        for key, migration in normal.items():
+            for parent in migration.dependencies:
+                if parent[0] == key[0]:
+                    # Internal dependencies already added.
+                    continue
                 parent = self.check_key(parent, key[0])
                 if parent is not None:
                     self.graph.add_dependency(key, parent)