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

Regression in 64b1ac7292c72d3551b2ad70b2a78c8fe4af3249.
Backport of b07298a73a8d444b3618aad8005055bee5ead8cb from main.

3 files changed, 71 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
diff --git a/tests/migrations/test_commands.py b/tests/migrations/test_commands.py
index b5817081d2..1ff680be07 100644
--- a/tests/migrations/test_commands.py
+++ b/tests/migrations/test_commands.py
@@ -3142,6 +3142,60 @@ class SquashMigrationsTests(MigrationTestBase):
             ]
             self.assertNotIn("migrations", applied_app_labels)
 
+    def test_double_replaced_migrations_are_checked_correctly(self):
+        """
+        If replaced migrations are already applied and replacing migrations
+        are not, then migrate should not fail with
+        InconsistentMigrationHistory.
+        """
+        with self.temporary_migration_module():
+            call_command(
+                "makemigrations",
+                "migrations",
+                "--empty",
+                interactive=False,
+                verbosity=0,
+            )
+            call_command(
+                "makemigrations",
+                "migrations",
+                "--empty",
+                interactive=False,
+                verbosity=0,
+            )
+            call_command(
+                "makemigrations",
+                "migrations",
+                "--empty",
+                interactive=False,
+                verbosity=0,
+            )
+            call_command(
+                "makemigrations",
+                "migrations",
+                "--empty",
+                interactive=False,
+                verbosity=0,
+            )
+            call_command("migrate", "migrations", interactive=False, verbosity=0)
+            call_command(
+                "squashmigrations",
+                "migrations",
+                "0001",
+                "0002",
+                interactive=False,
+                verbosity=0,
+            )
+            call_command(
+                "squashmigrations",
+                "migrations",
+                "0001_initial_squashed",
+                "0003",
+                interactive=False,
+                verbosity=0,
+            )
+            call_command("migrate", "migrations", interactive=False, verbosity=0)
+
     def test_squashmigrations_initial_attribute(self):
         with self.temporary_migration_module(
             module="migrations.test_migrations"