Fix overridden deps to be skipped correctly

Current implementation only checks the name of the direct child and the
owner of the packaging spec. But this can cause unintentionally
installing unnecessary dependencies of overridden modules.

This can be fixed by 1) gathering all overridden modules, 2) walking
deps with skipping overridden modules, and 3) installing packages from
visitied modules only.

Bug: 330141242
Test: TH
Test: try building pixel system image
Change-Id: I4a646941b61e890b5cd2c9aa137e74c80777f837
diff --git a/android/packaging.go b/android/packaging.go
index bb1fe4e..bf18409 100644
--- a/android/packaging.go
+++ b/android/packaging.go
@@ -506,13 +506,11 @@
 	// all packaging specs gathered from the high priority deps.
 	var highPriorities []PackagingSpec
 
-	// Name of the dependency which requested the packaging spec.
-	// If this dep is overridden, the packaging spec will not be installed via this dependency chain.
-	// (the packaging spec might still be installed if there are some other deps which depend on it).
-	var depNames []string
-
 	// list of module names overridden
-	var overridden []string
+	overridden := make(map[string]bool)
+
+	// all installed modules which are not overridden.
+	modulesToInstall := make(map[string]bool)
 
 	var arches []ArchType
 	for _, target := range getSupportedTargets(ctx) {
@@ -529,6 +527,7 @@
 		return false
 	}
 
+	// find all overridden modules and packaging specs
 	ctx.VisitDirectDepsProxy(func(child ModuleProxy) {
 		depTag := ctx.OtherModuleDependencyTag(child)
 		if pi, ok := depTag.(PackagingItem); !ok || !pi.IsPackagingItem() {
@@ -556,20 +555,32 @@
 				regularPriorities = append(regularPriorities, ps)
 			}
 
-			depNames = append(depNames, child.Name())
-			overridden = append(overridden, ps.overrides.ToSlice()...)
+			for o := range ps.overrides.Iter() {
+				overridden[o] = true
+			}
 		}
 	})
 
-	filterOverridden := func(input []PackagingSpec) []PackagingSpec {
-		// input minus packaging specs that are overridden
-		var filtered []PackagingSpec
-		for index, ps := range input {
-			if ps.owner != "" && InList(ps.owner, overridden) {
-				continue
+	// gather modules to install, skipping overridden modules
+	ctx.WalkDeps(func(child, parent Module) bool {
+		owner := ctx.OtherModuleName(child)
+		if o, ok := child.(OverridableModule); ok {
+			if overriddenBy := o.GetOverriddenBy(); overriddenBy != "" {
+				owner = overriddenBy
 			}
-			// The dependency which requested this packaging spec has been overridden.
-			if InList(depNames[index], overridden) {
+		}
+		if overridden[owner] {
+			return false
+		}
+		modulesToInstall[owner] = true
+		return true
+	})
+
+	filterOverridden := func(input []PackagingSpec) []PackagingSpec {
+		// input minus packaging specs that are not installed
+		var filtered []PackagingSpec
+		for _, ps := range input {
+			if !modulesToInstall[ps.owner] {
 				continue
 			}
 			filtered = append(filtered, ps)