[6.0.x] Fixed #36141 -- Checked for applied replaced migrations recursively.

Regression in 64b1ac7292c72d3551b2ad70b2a78c8fe4af3249.
Backport of b07298a73a8d444b3618aad8005055bee5ead8cb from main.

2 files changed, 17 insertions, 7 deletions

diff --git a/django/db/migrations/executor.py b/django/db/migrations/executor.py
index 1ad7d0c18c..074d7b2d28 100644
--- a/django/db/migrations/executor.py
+++ b/django/db/migrations/executor.py
@@ -304,8 +304,7 @@ class MigrationExecutor:
         """
         applied = self.recorder.applied_migrations()
         for key, migration in self.loader.replacements.items():
-            all_applied = all(m in applied for m in migration.replaces)
-            if all_applied and key not in applied:
+            if key not in applied and self.loader.all_replaced_applied(key, applied):
                 self.recorder.record_applied(*key)
 
     def detect_soft_applied(self, project_state, migration):
diff --git a/django/db/migrations/loader.py b/django/db/migrations/loader.py
index 66944c7ab7..df195e0802 100644
--- a/django/db/migrations/loader.py
+++ b/django/db/migrations/loader.py
@@ -356,11 +356,8 @@ class MigrationLoader:
                 if parent not in applied:
                     # Skip unapplied squashed migrations that have all of their
                     # `replaces` applied.
-                    if parent in self.replacements:
-                        if all(
-                            m in applied for m in self.replacements[parent].replaces
-                        ):
-                            continue
+                    if self.all_replaced_applied(parent.key, applied):
+                        continue
                     raise InconsistentMigrationHistory(
                         "Migration {}.{} is applied before its dependency "
                         "{}.{} on database '{}'.".format(
@@ -372,6 +369,20 @@ class MigrationLoader:
                         )
                     )
 
+    def all_replaced_applied(self, migration_key, applied):
+        """
+        Checks (recursively) whether all replaced migrations are applied.
+        """
+        if migration_key in self.replacements:
+            for replaced_key in self.replacements[migration_key].replaces:
+                if replaced_key not in applied and not self.all_replaced_applied(
+                    replaced_key, applied
+                ):
+                    return False
+            return True
+
+        return False
+
     def detect_conflicts(self):
         """
         Look through the loaded graph and detect any conflicts - apps