diff --git a/apex/apex_test.go b/apex/apex_test.go
index 3f16cd3..6280d11 100644
--- a/apex/apex_test.go
+++ b/apex/apex_test.go
@@ -839,6 +839,7 @@
 			name: "myapex",
 			key: "myapex.key",
 			native_shared_libs: ["mylib", "mylib3"],
+			binaries: ["foo.rust"],
 			updatable: false,
 		}
 
@@ -887,6 +888,25 @@
 			stl: "none",
 			apex_available: [ "myapex" ],
 		}
+
+		rust_binary {
+			name: "foo.rust",
+			srcs: ["foo.rs"],
+			shared_libs: ["libfoo.shared_from_rust"],
+			prefer_rlib: true,
+			apex_available: ["myapex"],
+		}
+
+		cc_library_shared {
+			name: "libfoo.shared_from_rust",
+			srcs: ["mylib.cpp"],
+			system_shared_libs: [],
+			stl: "none",
+			stubs: {
+				versions: ["10", "11", "12"],
+			},
+		}
+
 	`)
 
 	apexRule := ctx.ModuleForTests("myapex", "android_common_myapex_image").Rule("apexRule")
@@ -924,7 +944,17 @@
 		"lib64/mylib.so",
 		"lib64/mylib3.so",
 		"lib64/mylib4.so",
+		"bin/foo.rust",
+		"lib64/libc++.so", // by the implicit dependency from foo.rust
+		"lib64/liblog.so", // by the implicit dependency from foo.rust
 	})
+
+	// Ensure that stub dependency from a rust module is not included
+	ensureNotContains(t, copyCmds, "image.apex/lib64/libfoo.shared_from_rust.so")
+	// The rust module is linked to the stub cc library
+	rustDeps := ctx.ModuleForTests("foo.rust", "android_arm64_armv8-a_apex10000").Rule("rustc").Args["linkFlags"]
+	ensureContains(t, rustDeps, "libfoo.shared_from_rust/android_arm64_armv8-a_shared_current/libfoo.shared_from_rust.so")
+	ensureNotContains(t, rustDeps, "libfoo.shared_from_rust/android_arm64_armv8-a_shared/libfoo.shared_from_rust.so")
 }
 
 func TestApexWithStubsWithMinSdkVersion(t *testing.T) {
diff --git a/cc/cc.go b/cc/cc.go
index 5d6611b..818d5ff 100644
--- a/cc/cc.go
+++ b/cc/cc.go
@@ -1259,7 +1259,7 @@
 	return name
 }
 
-func (c *Module) bootstrap() bool {
+func (c *Module) Bootstrap() bool {
 	return Bool(c.Properties.Bootstrap)
 }
 
@@ -1504,7 +1504,7 @@
 }
 
 func (ctx *moduleContextImpl) bootstrap() bool {
-	return ctx.mod.bootstrap()
+	return ctx.mod.Bootstrap()
 }
 
 func (ctx *moduleContextImpl) nativeCoverage() bool {
@@ -2646,64 +2646,8 @@
 					return
 				}
 
-				sharedLibraryInfo := ctx.OtherModuleProvider(dep, SharedLibraryInfoProvider).(SharedLibraryInfo)
-				sharedLibraryStubsInfo := ctx.OtherModuleProvider(dep, SharedLibraryStubsProvider).(SharedLibraryStubsInfo)
-
-				if !libDepTag.explicitlyVersioned && len(sharedLibraryStubsInfo.SharedStubLibraries) > 0 {
-					useStubs := false
-
-					if lib := moduleLibraryInterface(dep); lib.buildStubs() && c.UseVndk() { // LLNDK
-						if !apexInfo.IsForPlatform() {
-							// For platform libraries, use current version of LLNDK
-							useStubs = true
-						}
-					} else if apexInfo.IsForPlatform() {
-						// If not building for APEX, use stubs only when it is from
-						// an APEX (and not from platform)
-						// However, for host, ramdisk, vendor_ramdisk, recovery or bootstrap modules,
-						// always link to non-stub variant
-						useStubs = dep.(android.ApexModule).NotInPlatform() && !c.bootstrap()
-						if useStubs {
-							// Another exception: if this module is a test for an APEX, then
-							// it is linked with the non-stub variant of a module in the APEX
-							// as if this is part of the APEX.
-							testFor := ctx.Provider(android.ApexTestForInfoProvider).(android.ApexTestForInfo)
-							for _, apexContents := range testFor.ApexContents {
-								if apexContents.DirectlyInApex(depName) {
-									useStubs = false
-									break
-								}
-							}
-						}
-						if useStubs {
-							// Yet another exception: If this module and the dependency are
-							// available to the same APEXes then skip stubs between their
-							// platform variants. This complements the test_for case above,
-							// which avoids the stubs on a direct APEX library dependency, by
-							// avoiding stubs for indirect test dependencies as well.
-							//
-							// TODO(b/183882457): This doesn't work if the two libraries have
-							// only partially overlapping apex_available. For that test_for
-							// modules would need to be split into APEX variants and resolved
-							// separately for each APEX they have access to.
-							if android.AvailableToSameApexes(c, dep.(android.ApexModule)) {
-								useStubs = false
-							}
-						}
-					} else {
-						// If building for APEX, use stubs when the parent is in any APEX that
-						// the child is not in.
-						useStubs = !android.DirectlyInAllApexes(apexInfo, depName)
-					}
-
-					// when to use (unspecified) stubs, use the latest one.
-					if useStubs {
-						stubs := sharedLibraryStubsInfo.SharedStubLibraries
-						toUse := stubs[len(stubs)-1]
-						sharedLibraryInfo = toUse.SharedLibraryInfo
-						depExporterInfo = toUse.FlagExporterInfo
-					}
-				}
+				sharedLibraryInfo, returnedDepExporterInfo := ChooseStubOrImpl(ctx, dep)
+				depExporterInfo = returnedDepExporterInfo
 
 				// Stubs lib doesn't link to the shared lib dependencies. Don't set
 				// linkFile, depFile, and ptr.
@@ -2916,6 +2860,100 @@
 	return depPaths
 }
 
+// ChooseStubOrImpl determines whether a given dependency should be redirected to the stub variant
+// of the dependency or not, and returns the SharedLibraryInfo and FlagExporterInfo for the right
+// dependency. The stub variant is selected when the dependency crosses a boundary where each side
+// has different level of updatability. For example, if a library foo in an APEX depends on a
+// library bar which provides stable interface and exists in the platform, foo uses the stub variant
+// of bar. If bar doesn't provide a stable interface (i.e. buildStubs() == false) or is in the
+// same APEX as foo, the non-stub variant of bar is used.
+func ChooseStubOrImpl(ctx android.ModuleContext, dep android.Module) (SharedLibraryInfo, FlagExporterInfo) {
+	depName := ctx.OtherModuleName(dep)
+	depTag := ctx.OtherModuleDependencyTag(dep)
+	libDepTag, ok := depTag.(libraryDependencyTag)
+	if !ok || !libDepTag.shared() {
+		panic(fmt.Errorf("Unexpected dependency tag: %T", depTag))
+	}
+
+	thisModule, ok := ctx.Module().(android.ApexModule)
+	if !ok {
+		panic(fmt.Errorf("Not an APEX module: %q", ctx.ModuleName()))
+	}
+
+	useVndk := false
+	bootstrap := false
+	if linkable, ok := ctx.Module().(LinkableInterface); !ok {
+		panic(fmt.Errorf("Not a Linkable module: %q", ctx.ModuleName()))
+	} else {
+		useVndk = linkable.UseVndk()
+		bootstrap = linkable.Bootstrap()
+	}
+
+	sharedLibraryInfo := ctx.OtherModuleProvider(dep, SharedLibraryInfoProvider).(SharedLibraryInfo)
+	depExporterInfo := ctx.OtherModuleProvider(dep, FlagExporterInfoProvider).(FlagExporterInfo)
+	sharedLibraryStubsInfo := ctx.OtherModuleProvider(dep, SharedLibraryStubsProvider).(SharedLibraryStubsInfo)
+	apexInfo := ctx.Provider(android.ApexInfoProvider).(android.ApexInfo)
+
+	if !libDepTag.explicitlyVersioned && len(sharedLibraryStubsInfo.SharedStubLibraries) > 0 {
+		useStubs := false
+
+		if lib := moduleLibraryInterface(dep); lib.buildStubs() && useVndk { // LLNDK
+			if !apexInfo.IsForPlatform() {
+				// For platform libraries, use current version of LLNDK
+				// If this is for use_vendor apex we will apply the same rules
+				// of apex sdk enforcement below to choose right version.
+				useStubs = true
+			}
+		} else if apexInfo.IsForPlatform() {
+			// If not building for APEX, use stubs only when it is from
+			// an APEX (and not from platform)
+			// However, for host, ramdisk, vendor_ramdisk, recovery or bootstrap modules,
+			// always link to non-stub variant
+			useStubs = dep.(android.ApexModule).NotInPlatform() && !bootstrap
+			if useStubs {
+				// Another exception: if this module is a test for an APEX, then
+				// it is linked with the non-stub variant of a module in the APEX
+				// as if this is part of the APEX.
+				testFor := ctx.Provider(android.ApexTestForInfoProvider).(android.ApexTestForInfo)
+				for _, apexContents := range testFor.ApexContents {
+					if apexContents.DirectlyInApex(depName) {
+						useStubs = false
+						break
+					}
+				}
+			}
+			if useStubs {
+				// Yet another exception: If this module and the dependency are
+				// available to the same APEXes then skip stubs between their
+				// platform variants. This complements the test_for case above,
+				// which avoids the stubs on a direct APEX library dependency, by
+				// avoiding stubs for indirect test dependencies as well.
+				//
+				// TODO(b/183882457): This doesn't work if the two libraries have
+				// only partially overlapping apex_available. For that test_for
+				// modules would need to be split into APEX variants and resolved
+				// separately for each APEX they have access to.
+				if android.AvailableToSameApexes(thisModule, dep.(android.ApexModule)) {
+					useStubs = false
+				}
+			}
+		} else {
+			// If building for APEX, use stubs when the parent is in any APEX that
+			// the child is not in.
+			useStubs = !android.DirectlyInAllApexes(apexInfo, depName)
+		}
+
+		// when to use (unspecified) stubs, use the latest one.
+		if useStubs {
+			stubs := sharedLibraryStubsInfo.SharedStubLibraries
+			toUse := stubs[len(stubs)-1]
+			sharedLibraryInfo = toUse.SharedLibraryInfo
+			depExporterInfo = toUse.FlagExporterInfo
+		}
+	}
+	return sharedLibraryInfo, depExporterInfo
+}
+
 // orderStaticModuleDeps rearranges the order of the static library dependencies of the module
 // to match the topological order of the dependency tree, including any static analogues of
 // direct shared libraries.  It returns the ordered static dependencies, and an android.DepSet
diff --git a/cc/linkable.go b/cc/linkable.go
index 0a5d16c..231626e 100644
--- a/cc/linkable.go
+++ b/cc/linkable.go
@@ -165,6 +165,9 @@
 	// "product_specific: true" modules are included here.
 	UseVndk() bool
 
+	// Bootstrap tests if this module is allowed to use non-APEX version of libraries.
+	Bootstrap() bool
+
 	// IsVndkSp returns true if this is a VNDK-SP module.
 	IsVndkSp() bool
 
diff --git a/rust/rust.go b/rust/rust.go
index b8c8be5..4dd0671 100644
--- a/rust/rust.go
+++ b/rust/rust.go
@@ -288,6 +288,10 @@
 	return mod.Properties.VndkVersion != ""
 }
 
+func (mod *Module) Bootstrap() bool {
+	return false
+}
+
 func (mod *Module) MustUseVendorVariant() bool {
 	return true
 }
@@ -952,7 +956,7 @@
 	directRlibDeps := []*Module{}
 	directDylibDeps := []*Module{}
 	directProcMacroDeps := []*Module{}
-	directSharedLibDeps := [](cc.LinkableInterface){}
+	directSharedLibDeps := []cc.SharedLibraryInfo{}
 	directStaticLibDeps := [](cc.LinkableInterface){}
 	directSrcProvidersDeps := []*Module{}
 	directSrcDeps := [](android.SourceFileProducer){}
@@ -1073,14 +1077,23 @@
 				directStaticLibDeps = append(directStaticLibDeps, ccDep)
 				mod.Properties.AndroidMkStaticLibs = append(mod.Properties.AndroidMkStaticLibs, makeLibName)
 			case cc.IsSharedDepTag(depTag):
+				// For the shared lib dependencies, we may link to the stub variant
+				// of the dependency depending on the context (e.g. if this
+				// dependency crosses the APEX boundaries).
+				sharedLibraryInfo, exportedInfo := cc.ChooseStubOrImpl(ctx, dep)
+
+				// Re-get linkObject as ChooseStubOrImpl actually tells us which
+				// object (either from stub or non-stub) to use.
+				linkObject = android.OptionalPathForPath(sharedLibraryInfo.SharedLibrary)
+				linkPath = linkPathFromFilePath(linkObject.Path())
+
 				depPaths.linkDirs = append(depPaths.linkDirs, linkPath)
 				depPaths.linkObjects = append(depPaths.linkObjects, linkObject.String())
-				exportedInfo := ctx.OtherModuleProvider(dep, cc.FlagExporterInfoProvider).(cc.FlagExporterInfo)
 				depPaths.depIncludePaths = append(depPaths.depIncludePaths, exportedInfo.IncludeDirs...)
 				depPaths.depSystemIncludePaths = append(depPaths.depSystemIncludePaths, exportedInfo.SystemIncludeDirs...)
 				depPaths.depClangFlags = append(depPaths.depClangFlags, exportedInfo.Flags...)
 				depPaths.depGeneratedHeaders = append(depPaths.depGeneratedHeaders, exportedInfo.GeneratedHeaders...)
-				directSharedLibDeps = append(directSharedLibDeps, ccDep)
+				directSharedLibDeps = append(directSharedLibDeps, sharedLibraryInfo)
 
 				// Record baseLibName for snapshots.
 				mod.Properties.SnapshotSharedLibs = append(mod.Properties.SnapshotSharedLibs, cc.BaseLibName(depName))
@@ -1135,11 +1148,11 @@
 	var sharedLibFiles android.Paths
 	var sharedLibDepFiles android.Paths
 	for _, dep := range directSharedLibDeps {
-		sharedLibFiles = append(sharedLibFiles, dep.OutputFile().Path())
-		if dep.Toc().Valid() {
-			sharedLibDepFiles = append(sharedLibDepFiles, dep.Toc().Path())
+		sharedLibFiles = append(sharedLibFiles, dep.SharedLibrary)
+		if dep.TableOfContents.Valid() {
+			sharedLibDepFiles = append(sharedLibDepFiles, dep.TableOfContents.Path())
 		} else {
-			sharedLibDepFiles = append(sharedLibDepFiles, dep.OutputFile().Path())
+			sharedLibDepFiles = append(sharedLibDepFiles, dep.SharedLibrary)
 		}
 	}