Remove overriden modules from deps of autogenerated filesystem modules

`android_filesystem` supports overrides, but only if the module is
overriden by another module in its deps. For AOSP CF, the autogenerated
system.img contains an additional /bin/charger. The Kati system.img does
not contain this file because it is overriden by a module which is
installed in /vendor.

This CL updates the autogen mutators to remove a module from deps if it
is overriden by another module in PRODUCT_PACKAGES or by a transitve
required module dependency of PRODUCT_PACKAGES

Test: go test ./fsgen
Test: verified that /bin/charger no longer appears in diff_test of
system for aosp_cf_x86_64
Change-Id: Idafa1db07a42519ba3c441f851480b1c6faa63b8

Change-Id: If09050a6fd110d07d975595644dba85c740027e2
diff --git a/fsgen/filesystem_creator.go b/fsgen/filesystem_creator.go
index c903338..468794f 100644
--- a/fsgen/filesystem_creator.go
+++ b/fsgen/filesystem_creator.go
@@ -47,6 +47,7 @@
 }
 
 var fsGenStateOnceKey = android.NewOnceKey("FsGenState")
+var fsGenRemoveOverridesOnceKey = android.NewOnceKey("FsGenRemoveOverrides")
 
 // Map of partition module name to its partition that may be generated by Soong.
 // Note that it is not guaranteed that all modules returned by this function are successfully
@@ -79,6 +80,13 @@
 	soongGeneratedPartitions []string
 	// Mutex to protect the fsDeps
 	fsDepsMutex sync.Mutex
+	// Map of _all_ soong module names to their corresponding installation properties
+	moduleToInstallationProps map[string]installationProperties
+}
+
+type installationProperties struct {
+	Required  []string
+	Overrides []string
 }
 
 func newMultilibDeps() multilibDeps {
@@ -147,8 +155,9 @@
 					"com.android.vndk.v34": defaultDepCandidateProps(ctx.Config()),
 				},
 			},
-			soongGeneratedPartitions: generatedPartitions,
-			fsDepsMutex:              sync.Mutex{},
+			soongGeneratedPartitions:  generatedPartitions,
+			fsDepsMutex:               sync.Mutex{},
+			moduleToInstallationProps: map[string]installationProperties{},
 		}
 	}).(*FsGenState)
 }
@@ -193,6 +202,16 @@
 		}
 		fsGenState.fsDepsMutex.Unlock()
 	}
+	// store the map of module to (required,overrides) even if the module is not in PRODUCT_PACKAGES.
+	// the module might be installed transitively.
+	if m.Target().Os.Class == android.Device && m.Enabled(mctx) && m.ExportedToMake() {
+		fsGenState.fsDepsMutex.Lock()
+		fsGenState.moduleToInstallationProps[m.Name()] = installationProperties{
+			Required:  m.RequiredModuleNames(mctx),
+			Overrides: m.Overrides(),
+		}
+		fsGenState.fsDepsMutex.Unlock()
+	}
 }
 
 type depsStruct struct {
@@ -231,6 +250,7 @@
 }
 
 func setDepsMutator(mctx android.BottomUpMutatorContext) {
+	removeOverriddenDeps(mctx)
 	fsGenState := mctx.Config().Get(fsGenStateOnceKey).(*FsGenState)
 	fsDeps := fsGenState.fsDeps
 	soongGeneratedPartitionMap := getAllSoongGeneratedPartitionNames(mctx.Config(), fsGenState.soongGeneratedPartitions)
@@ -243,6 +263,47 @@
 	}
 }
 
+// removeOverriddenDeps collects PRODUCT_PACKAGES and (transitive) required deps.
+// it then removes any modules which appear in `overrides` of the above list.
+func removeOverriddenDeps(mctx android.BottomUpMutatorContext) {
+	mctx.Config().Once(fsGenRemoveOverridesOnceKey, func() interface{} {
+		fsGenState := mctx.Config().Get(fsGenStateOnceKey).(*FsGenState)
+		fsDeps := fsGenState.fsDeps
+		overridden := map[string]bool{}
+		allDeps := []string{}
+
+		// Step 1: Initialization: Append PRODUCT_PACKAGES to the queue
+		for _, fsDep := range fsDeps {
+			for depName, _ := range *fsDep {
+				allDeps = append(allDeps, depName)
+			}
+		}
+
+		// Step 2: Process the queue, and add required modules to the queue.
+		i := 0
+		for {
+			if i == len(allDeps) {
+				break
+			}
+			depName := allDeps[i]
+			for _, overrides := range fsGenState.moduleToInstallationProps[depName].Overrides {
+				overridden[overrides] = true
+			}
+			// add required dep to the queue.
+			allDeps = append(allDeps, fsGenState.moduleToInstallationProps[depName].Required...)
+			i += 1
+		}
+
+		// Step 3: Delete all the overridden modules.
+		for overridden, _ := range overridden {
+			for partition, _ := range fsDeps {
+				delete(*fsDeps[partition], overridden)
+			}
+		}
+		return nil
+	})
+}
+
 func generateDepStruct(deps map[string]*depCandidateProps) *packagingPropsStruct {
 	depsStruct := packagingPropsStruct{}
 	for depName, depProps := range deps {