Fix back stack changes during host lifecycle changes

When we dispatch lifecycle changes to destinations
because of back stack changes, we operate on a copy
of the back stack to avoid reentrant changes -
lifecycle observers that call navigate / popBackStack.

Now, we do the same for host lifecycle changes,
ensuring that any lifecycle observers that are triggered
when the host lifecycle changes state also avoid
any reentrant issues due to changing the back stack
during the dispatch of the lifecycle change.

Relnote: "Fixed a `ConcurrentModificationException` that
could occur when a `LifecycleObserver` attached to a
`NavBackStackEntry` triggers a change to the back stack
when the host `LifecycleOwner` such as the containing
Activity or Fragment changes its lifecycle state."
Test: new NavControllerTest
BUG: 377537292

Change-Id: Ia9494e9967aa45a7613c49d7530f524f5400d1ca
diff --git a/navigation/navigation-runtime/src/androidTest/java/androidx/navigation/NavControllerTest.kt b/navigation/navigation-runtime/src/androidTest/java/androidx/navigation/NavControllerTest.kt
index 95a9f20..7bd2f5c 100644
--- a/navigation/navigation-runtime/src/androidTest/java/androidx/navigation/NavControllerTest.kt
+++ b/navigation/navigation-runtime/src/androidTest/java/androidx/navigation/NavControllerTest.kt
@@ -1774,6 +1774,43 @@
 
     @UiThreadTest
     @Test
+    fun testNavigateFromLifecycleObserverDuringHostLifecycleChange() {
+        val navController = createNavController()
+        val hostLifecycleOwner = TestLifecycleOwner(Lifecycle.State.CREATED)
+        navController.setLifecycleOwner(hostLifecycleOwner)
+        navController.setGraph(R.navigation.nav_simple)
+
+        val receivedDestinationIds = mutableListOf<Int>()
+        navController.addOnDestinationChangedListener { _, destination, _ ->
+            receivedDestinationIds += destination.id
+        }
+
+        navController.navigate(R.id.second_test)
+
+        val destinationLifecycle = navController.getBackStackEntry(R.id.second_test).lifecycle
+        assertThat(destinationLifecycle.currentState).isEqualTo(Lifecycle.State.CREATED)
+        destinationLifecycle.addObserver(
+            object : LifecycleEventObserver {
+                override fun onStateChanged(source: LifecycleOwner, event: Lifecycle.Event) {
+                    if (event == Lifecycle.Event.ON_RESUME) {
+                        navController.popBackStack()
+                    }
+                }
+            }
+        )
+
+        // Now change the host lifecycle to trigger our observer
+        hostLifecycleOwner.currentState = Lifecycle.State.RESUMED
+
+        // And assert that we navigated correctly
+        assertThat(navController.currentDestination?.id).isEqualTo(R.id.start_test)
+        assertThat(receivedDestinationIds)
+            .containsExactly(R.id.start_test, R.id.second_test, R.id.start_test)
+            .inOrder()
+    }
+
+    @UiThreadTest
+    @Test
     fun testPopFromLifecycleObserver() {
         val navController = createNavController()
         navController.setLifecycleOwner(TestLifecycleOwner(Lifecycle.State.RESUMED))
diff --git a/navigation/navigation-runtime/src/main/java/androidx/navigation/NavController.kt b/navigation/navigation-runtime/src/main/java/androidx/navigation/NavController.kt
index 8efc3e2..4f43515 100644
--- a/navigation/navigation-runtime/src/main/java/androidx/navigation/NavController.kt
+++ b/navigation/navigation-runtime/src/main/java/androidx/navigation/NavController.kt
@@ -204,7 +204,10 @@
     private val lifecycleObserver: LifecycleObserver = LifecycleEventObserver { _, event ->
         hostLifecycleState = event.targetState
         if (_graph != null) {
-            for (entry in backQueue) {
+            // Operate on a copy of the queue to avoid issues with reentrant
+            // calls if updating the Lifecycle calls navigate() or popBackStack()
+            val backStack = backQueue.toMutableList()
+            for (entry in backStack) {
                 entry.handleLifecycleEvent(event)
             }
         }