Implement NavController navigate with Object T

Add support for navigating with a serializable object instance. The target NavDestination must have been added to the NavGraph with a route from a KClass.

Test: ./gradlew navigation:navigation-runtime:cC
Bug: 188693139
Relnote: "Add new navigate API to navigate with a serializable object instance. The target NavDestination must have been added to the NavGraph with a route from KClass."
Change-Id: If44d34757c454d628e2e73794047a5a23c37308a
diff --git a/navigation/navigation-runtime/api/current.txt b/navigation/navigation-runtime/api/current.txt
index 4a18eee..ffc549c 100644
--- a/navigation/navigation-runtime/api/current.txt
+++ b/navigation/navigation-runtime/api/current.txt
@@ -128,6 +128,10 @@
     method @MainThread public final void navigate(String route, optional androidx.navigation.NavOptions? navOptions);
     method @MainThread public final void navigate(String route, optional androidx.navigation.NavOptions? navOptions, optional androidx.navigation.Navigator.Extras? navigatorExtras);
     method @MainThread public final void navigate(String route, kotlin.jvm.functions.Function1<? super androidx.navigation.NavOptionsBuilder,kotlin.Unit> builder);
+    method @SuppressCompatibility @MainThread @androidx.navigation.ExperimentalSafeArgsApi public final <T> void navigate(T route);
+    method @SuppressCompatibility @MainThread @androidx.navigation.ExperimentalSafeArgsApi public final <T> void navigate(T route, optional androidx.navigation.NavOptions? navOptions);
+    method @SuppressCompatibility @MainThread @androidx.navigation.ExperimentalSafeArgsApi public final <T> void navigate(T route, optional androidx.navigation.NavOptions? navOptions, optional androidx.navigation.Navigator.Extras? navigatorExtras);
+    method @SuppressCompatibility @MainThread @androidx.navigation.ExperimentalSafeArgsApi public final <T> void navigate(T route, kotlin.jvm.functions.Function1<? super androidx.navigation.NavOptionsBuilder,kotlin.Unit> builder);
     method @MainThread public boolean navigateUp();
     method @MainThread public boolean popBackStack();
     method @SuppressCompatibility @MainThread @androidx.navigation.ExperimentalSafeArgsApi public inline <reified T> boolean popBackStack(boolean inclusive, optional boolean saveState);
diff --git a/navigation/navigation-runtime/api/restricted_current.txt b/navigation/navigation-runtime/api/restricted_current.txt
index 4a18eee..ffc549c 100644
--- a/navigation/navigation-runtime/api/restricted_current.txt
+++ b/navigation/navigation-runtime/api/restricted_current.txt
@@ -128,6 +128,10 @@
     method @MainThread public final void navigate(String route, optional androidx.navigation.NavOptions? navOptions);
     method @MainThread public final void navigate(String route, optional androidx.navigation.NavOptions? navOptions, optional androidx.navigation.Navigator.Extras? navigatorExtras);
     method @MainThread public final void navigate(String route, kotlin.jvm.functions.Function1<? super androidx.navigation.NavOptionsBuilder,kotlin.Unit> builder);
+    method @SuppressCompatibility @MainThread @androidx.navigation.ExperimentalSafeArgsApi public final <T> void navigate(T route);
+    method @SuppressCompatibility @MainThread @androidx.navigation.ExperimentalSafeArgsApi public final <T> void navigate(T route, optional androidx.navigation.NavOptions? navOptions);
+    method @SuppressCompatibility @MainThread @androidx.navigation.ExperimentalSafeArgsApi public final <T> void navigate(T route, optional androidx.navigation.NavOptions? navOptions, optional androidx.navigation.Navigator.Extras? navigatorExtras);
+    method @SuppressCompatibility @MainThread @androidx.navigation.ExperimentalSafeArgsApi public final <T> void navigate(T route, kotlin.jvm.functions.Function1<? super androidx.navigation.NavOptionsBuilder,kotlin.Unit> builder);
     method @MainThread public boolean navigateUp();
     method @MainThread public boolean popBackStack();
     method @SuppressCompatibility @MainThread @androidx.navigation.ExperimentalSafeArgsApi public inline <reified T> boolean popBackStack(boolean inclusive, optional boolean saveState);
diff --git a/navigation/navigation-runtime/src/androidTest/java/androidx/navigation/NavControllerRouteTest.kt b/navigation/navigation-runtime/src/androidTest/java/androidx/navigation/NavControllerRouteTest.kt
index f35f98f..2d2965c0 100644
--- a/navigation/navigation-runtime/src/androidTest/java/androidx/navigation/NavControllerRouteTest.kt
+++ b/navigation/navigation-runtime/src/androidTest/java/androidx/navigation/NavControllerRouteTest.kt
@@ -647,6 +647,195 @@
 
     @UiThreadTest
     @Test
+    fun testNavigateWithObject() {
+        val navController = createNavController()
+        navController.graph = navController.createGraph(startDestination = "start") {
+            test("start")
+            test(TestClass::class)
+        }
+        assertThat(navController.currentDestination?.route).isEqualTo("start")
+        assertThat(navController.currentBackStack.value.size).isEqualTo(2)
+
+        navController.navigate(TestClass())
+        assertThat(navController.currentDestination?.route).isEqualTo(TEST_CLASS_ROUTE)
+        assertThat(navController.currentBackStack.value.size).isEqualTo(3)
+    }
+
+    @UiThreadTest
+    @Test
+    fun testNavigateWithObjectPathArg() {
+        val navController = createNavController()
+        navController.graph = navController.createGraph(startDestination = "start") {
+            test("start")
+            test(TestClassPathArg::class)
+        }
+        assertThat(navController.currentDestination?.route).isEqualTo("start")
+        assertThat(navController.currentBackStack.value.size).isEqualTo(2)
+
+        navController.navigate(TestClassPathArg(0))
+        assertThat(navController.currentDestination?.route).isEqualTo(TEST_CLASS_PATH_ARG_ROUTE)
+        assertThat(navController.currentBackStack.value.size).isEqualTo(3)
+        assertThat(navController.currentBackStackEntry?.arguments?.getInt("arg"))
+            .isEqualTo(0)
+    }
+
+    @UiThreadTest
+    @Test
+    fun testNavigateWithObjectQueryArg() {
+        @Serializable
+        class TestClass(val arg: IntArray)
+
+        val navController = createNavController()
+        navController.graph = navController.createGraph(startDestination = "start") {
+            test("start")
+            test(TestClass::class)
+        }
+        assertThat(navController.currentDestination?.route).isEqualTo("start")
+        assertThat(navController.currentBackStack.value.size).isEqualTo(2)
+
+        navController.navigate(TestClass(intArrayOf(0, 1, 2)))
+        assertThat(navController.currentDestination?.route).isEqualTo(
+            "androidx.navigation.NavControllerRouteTest." +
+                "testNavigateWithObjectQueryArg.TestClass?arg={arg}"
+        )
+        assertThat(navController.currentBackStack.value.size).isEqualTo(3)
+        assertThat(navController.currentBackStackEntry?.arguments?.getIntArray("arg"))
+            .isEqualTo(intArrayOf(0, 1, 2))
+    }
+
+    @UiThreadTest
+    @Test
+    fun testNavigateWithObjectPathQueryArg() {
+        @Serializable
+        class TestClass(val arg: IntArray, val arg2: Boolean)
+
+        val navController = createNavController()
+        navController.graph = navController.createGraph(startDestination = "start") {
+            test("start")
+            test(TestClass::class)
+        }
+        assertThat(navController.currentDestination?.route).isEqualTo("start")
+        assertThat(navController.currentBackStack.value.size).isEqualTo(2)
+
+        navController.navigate(TestClass(intArrayOf(0, 1, 2), true))
+        assertThat(navController.currentDestination?.route).isEqualTo(
+            "androidx.navigation.NavControllerRouteTest." +
+                "testNavigateWithObjectPathQueryArg.TestClass/{arg2}?arg={arg}"
+        )
+        assertThat(navController.currentBackStack.value.size).isEqualTo(3)
+        assertThat(navController.currentBackStackEntry?.arguments?.getIntArray("arg"))
+            .isEqualTo(intArrayOf(0, 1, 2))
+        assertThat(navController.currentBackStackEntry?.arguments?.getBoolean("arg2"))
+            .isEqualTo(true)
+    }
+
+    @UiThreadTest
+    @Test
+    fun testNavigateWithObjectInvalidObject() {
+        @Serializable
+        class WrongTestClass
+
+        val navController = createNavController()
+        navController.graph = navController.createGraph(startDestination = "start") {
+            test("start")
+            test(TestClass::class)
+        }
+        assertThat(navController.currentDestination?.route).isEqualTo("start")
+        assertThat(navController.currentBackStack.value.size).isEqualTo(2)
+
+        assertFailsWith<IllegalArgumentException> {
+            navController.navigate(WrongTestClass())
+        }
+    }
+
+    @UiThreadTest
+    @Test
+    fun testNavigateWithObjectWithPopUpTo() {
+        val navController = createNavController()
+        navController.graph = navController.createGraph(startDestination = "start") {
+            test("start")
+            test(TestClass::class)
+        }
+        assertThat(navController.currentDestination?.route).isEqualTo("start")
+        assertThat(navController.currentBackStack.value.size).isEqualTo(2)
+
+        navController.navigate(TestClass(), navOptions {
+            popUpTo("start") { inclusive = true }
+        })
+        assertThat(navController.currentDestination?.route).isEqualTo(TEST_CLASS_ROUTE)
+        assertThat(navController.currentBackStack.value.size).isEqualTo(2)
+    }
+
+    @UiThreadTest
+    @Test
+    fun testNavigateWithObjectArgsSavedAndRestored() {
+        val navController = createNavController()
+        navController.graph = navController.createGraph(startDestination = "start") {
+            test("start")
+            test(TestClassPathArg::class)
+        }
+        assertThat(navController.currentDestination?.route).isEqualTo("start")
+        assertThat(navController.currentBackStack.value.size).isEqualTo(2)
+
+        // first nav
+        val dest = TestClassPathArg(0)
+        navController.navigate(dest)
+        assertThat(navController.currentDestination?.route).isEqualTo(TEST_CLASS_PATH_ARG_ROUTE)
+        assertThat(navController.currentBackStackEntry?.arguments?.getInt("arg"))
+            .isEqualTo(0)
+
+        // pop + save
+        val popped = navController.popBackStack(dest, true, true)
+        assertThat(popped).isTrue()
+        assertThat(navController.currentDestination?.route).isEqualTo("start")
+
+        // second nav with restore
+        val dest2 = TestClassPathArg(1)
+        navController.navigate(dest2, navOptions { restoreState = true })
+        assertThat(navController.currentDestination?.route).isEqualTo(TEST_CLASS_PATH_ARG_ROUTE)
+        assertThat(navController.currentBackStackEntry?.arguments?.getInt("arg"))
+            .isEqualTo(0)
+    }
+
+    @UiThreadTest
+    @Test
+    fun testNavigateWithObjectArgsSavedNotRestored() {
+        val navController = createNavController()
+        navController.graph = navController.createGraph(startDestination = "start") {
+            test("start")
+            test(TestClassPathArg::class)
+        }
+        assertThat(navController.currentDestination?.route).isEqualTo("start")
+        assertThat(navController.currentBackStack.value.size).isEqualTo(2)
+
+        // first nav
+        val dest = TestClassPathArg(0)
+        navController.navigate(dest)
+        assertThat(navController.currentDestination?.route).isEqualTo(TEST_CLASS_PATH_ARG_ROUTE)
+        assertThat(navController.currentBackStackEntry?.arguments?.getInt("arg"))
+            .isEqualTo(0)
+
+        // pop + save
+        val popped = navController.popBackStack(dest, true, true)
+        assertThat(popped).isTrue()
+        assertThat(navController.currentDestination?.route).isEqualTo("start")
+
+        // second nav without restore
+        val dest2 = TestClassPathArg(1)
+        navController.navigate(dest2, navOptions { restoreState = false })
+        assertThat(navController.currentDestination?.route).isEqualTo(TEST_CLASS_PATH_ARG_ROUTE)
+        assertThat(navController.currentBackStackEntry?.arguments?.getInt("arg"))
+            .isEqualTo(1)
+
+        // now we restore
+        navController.navigate(dest2, navOptions { restoreState = true })
+        assertThat(navController.currentDestination?.route).isEqualTo(TEST_CLASS_PATH_ARG_ROUTE)
+        assertThat(navController.currentBackStackEntry?.arguments?.getInt("arg"))
+            .isEqualTo(0)
+    }
+
+    @UiThreadTest
+    @Test
     fun testNavigateWithPopUpToFurthestRoute() {
         val navController = createNavController()
         navController.graph = nav_singleArg_graph
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 d5a8117..0bc6506 100644
--- a/navigation/navigation-runtime/src/main/java/androidx/navigation/NavController.kt
+++ b/navigation/navigation-runtime/src/main/java/androidx/navigation/NavController.kt
@@ -578,7 +578,7 @@
     ): Boolean {
         // route contains arguments so we need to generate and pop with the populated route
         // rather than popping based on route pattern
-        val finalRoute = generateRouteFromBackStack(route) ?: return false
+        val finalRoute = generateRouteFilled(route, fromBackStack = true) ?: return false
         return popBackStack(finalRoute, inclusive, saveState)
     }
 
@@ -894,13 +894,9 @@
     @MainThread
     @ExperimentalSafeArgsApi
     public fun <T : Any> clearBackStack(route: T): Boolean {
-        val dest = findDestination(route::class.serializer().hashCode()) ?: return false
         // route contains arguments so we need to generate and clear with the populated route
         // rather than clearing based on route pattern
-        val finalRoute = route.generateRouteWithArgs(
-            // get argument typeMap
-            dest.arguments.mapValues { it.value.type }
-        )
+        val finalRoute = generateRouteFilled(route) ?: return false
         val cleared = clearBackStackInternal(finalRoute)
         // Only return true if the clear succeeded and we've dispatched
         // the change to a new destination
@@ -1658,16 +1654,24 @@
         return currentGraph.findNode(route)
     }
 
-    // finds destination from backstack and generates a route filled with args
-    // based on the input serializable object
+    // Finds destination and generates a route filled with args based on the serializable object.
+    // `fromBackStack` is for efficiency - if left false, the worst case scenario is searching
+    // from entire graph when we only care about backstack.
     @OptIn(InternalSerializationApi::class)
-    private fun <T : Any> generateRouteFromBackStack(route: T): String? {
-        val entry = backQueue.lastOrNull {
-            it.destination.id == route::class.serializer().hashCode()
-        } ?: return null
+    private fun <T : Any> generateRouteFilled(route: T, fromBackStack: Boolean = false): String? {
+        val destination = if (fromBackStack) {
+            // limit search within backstack
+            backQueue.lastOrNull {
+                it.destination.id == route::class.serializer().hashCode()
+            }?.destination
+        } else {
+            // search from within root graph
+            findDestination(route::class.serializer().hashCode())
+        }
+        if (destination == null) return null
         return route.generateRouteWithArgs(
             // get argument typeMap
-            entry.destination.arguments.mapValues { it.value.type }
+            destination.arguments.mapValues { it.value.type }
         )
     }
 
@@ -2354,6 +2358,56 @@
     }
 
     /**
+     * Navigate to a route from an Object in the current NavGraph. If an invalid route is given, an
+     * [IllegalArgumentException] will be thrown.
+     *
+     * The target NavDestination must have been created with route from a [KClass]
+     *
+     * If given [NavOptions] pass in [NavOptions.restoreState] `true`, any args passed here as part
+     * of the route will be overridden by the restored args.
+     *
+     * @param route route from an Object for the destination
+     * @param builder DSL for constructing a new [NavOptions]
+     *
+     * @throws IllegalArgumentException if the given route is invalid
+     */
+    @MainThread
+    @ExperimentalSafeArgsApi
+    public fun <T : Any> navigate(route: T, builder: NavOptionsBuilder.() -> Unit) {
+        navigate(route, navOptions(builder))
+    }
+
+    /**
+     * Navigate to a route from an Object in the current NavGraph. If an invalid route is given, an
+     * [IllegalArgumentException] will be thrown.
+     *
+     * The target NavDestination must have been created with route from a [KClass]
+     *
+     * If given [NavOptions] pass in [NavOptions.restoreState] `true`, any args passed here as part
+     * of the route will be overridden by the restored args.
+     *
+     * @param route route from an Object for the destination
+     * @param navOptions special options for this navigation operation
+     * @param navigatorExtras extras to pass to the [Navigator]
+     *
+     * @throws IllegalArgumentException if the given route is invalid
+     */
+    @MainThread
+    @JvmOverloads
+    @ExperimentalSafeArgsApi
+    public fun <T : Any> navigate(
+        route: T,
+        navOptions: NavOptions? = null,
+        navigatorExtras: Navigator.Extras? = null
+    ) {
+        val finalRoute = generateRouteFilled(route)
+        navigate(
+            NavDeepLinkRequest.Builder.fromUri(createRoute(finalRoute).toUri()).build(), navOptions,
+            navigatorExtras
+        )
+    }
+
+    /**
      * Create a deep link to a destination within this NavController.
      *
      * @return a [NavDeepLinkBuilder] suitable for constructing a deep link
@@ -2627,7 +2681,7 @@
     public fun <T : Any> getBackStackEntry(route: T): NavBackStackEntry {
         // route contains arguments so we need to generate the populated route
         // rather than getting entry based on route pattern
-        val finalRoute = generateRouteFromBackStack(route)
+        val finalRoute = generateRouteFilled(route, fromBackStack = true)
         requireNotNull(finalRoute) {
             "No destination with route $finalRoute is on the NavController's back stack. The " +
                 "current destination is $currentDestination"