// Copyright (C) 2024 The Android Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package fsgen

import (
 "container/list"
 "fmt"
 "slices"
 "strings"
 "sync"

 "android/soong/android"
 "android/soong/cc"
 "android/soong/rust"

 "github.com/google/blueprint/proptools"
)

func RegisterCollectFileSystemDepsMutators(ctx android.RegisterMutatorsContext) {
 ctx.BottomUp("fs_recovery_fstab", setRecoveryFstabSrcs).MutatesGlobalState()
 ctx.BottomUp("fs_collect_deps", collectDepsMutator).MutatesGlobalState()
 ctx.BottomUp("fs_remove_deps", removeDepsMutator).MutatesGlobalState()
 ctx.BottomUp("fs_cross_partition_required_deps", crossPartitionRequiredMutator).MutatesGlobalState()
 ctx.BottomUp("fs_set_deps", setDepsMutator)
}

var fsGenStateOnceKey = android.NewOnceKey("FsGenState")
var fsGenRemoveOverridesOnceKey = android.NewOnceKey("FsGenRemoveOverrides")
var fsGenCrossPartitionRequiredDepsOnceKey = android.NewOnceKey("FsGenCrossPartitionRequiredDeps")

// 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
// created.
func getAllSoongGeneratedPartitionNames(config android.Config, partitions []string) map[string]string {
 ret := map[string]string{}
 for _, partition := range partitions {
  ret[generatedModuleNameForPartition(config, partition)] = partition
 }
 return ret
}

type depCandidateProps struct {
 Namespace           string
 Multilib            string
 Arch                []android.ArchType
 NativeBridgeSupport map[android.NativeBridgeSupport]bool
}

// Map of module name to depCandidateProps
type multilibDeps map[string]*depCandidateProps

func (m *multilibDeps) SortedFullyQualifiedNames() []string {
 ret := make([]string, len(*m))
 i := 0
 for moduleName, props := range *m {
  ret[i] = fullyQualifiedModuleName(moduleName, props.Namespace)
  i += 1
 }
 return android.SortedUniqueStrings(ret)
}

type moduleToInstallationProps struct {
 // Map of _all_ soong module fully qualified names to their corresponding installation properties
 // Should not be accessed directly to add entries; Use AddToMap instead.
 moduleToPropsMap map[string]installationProperties

 // TODO (b/420968370): Remove this after we enforce that all namespaces are valid.
 baseModuleNameToPropsMap map[string][]installationProperties
}

func (m *moduleToInstallationProps) AddToMap(ctx android.BottomUpMutatorContext, prop *installationProperties) {
 m.moduleToPropsMap[fullyQualifiedModuleName(ctx.ModuleName(), ctx.Namespace().Path)] = *prop
 m.baseModuleNameToPropsMap[ctx.ModuleName()] = append(m.baseModuleNameToPropsMap[ctx.ModuleName()], *prop)
}

func (m *moduleToInstallationProps) Get(ctx android.BottomUpMutatorContext) (installationProperties, bool) {
 return m.GetFromFullyQualifiedModuleName(fullyQualifiedModuleName(ctx.ModuleName(), ctx.Namespace().Path))
}

func (m *moduleToInstallationProps) GetFromFullyQualifiedModuleName(fullyQualifiedModuleName string) (installationProperties, bool) {
 prop, ok := m.moduleToPropsMap[fullyQualifiedModuleName]
 if ok {
  return prop, ok
 }
 return installationProperties{}, ok
}

func (m *moduleToInstallationProps) GetFromModuleName(name string) (string, installationProperties, bool) {
 if len(name) == 0 {
  return "", installationProperties{}, false
 }
 // If the name has a fully qualified module name format, get it from the fully qualified module name
 if strings.HasPrefix("//", name) {
  prop, ok := m.GetFromFullyQualifiedModuleName(name)
  return name, prop, ok
 }

 // Input name is not in fully qualified name format, but the module may be in a namespace
 if props, ok := m.baseModuleNameToPropsMap[name]; ok {
  for _, prop := range props {
   fullyQualifiedName := fullyQualifiedModuleName(name, prop.Namespace)
   if discoveredProp, ok := m.GetFromFullyQualifiedModuleName(fullyQualifiedName); ok {
    return fullyQualifiedName, discoveredProp, ok
   }
  }
 }
 return "", installationProperties{}, false
}

func (m *moduleToInstallationProps) ModuleNameToFullyQualifiedModuleName(name string) string {
 if fullyQualifiedName, _, ok := m.GetFromModuleName(name); ok {
  return fullyQualifiedName
 }
 return name
}

func (m *moduleToInstallationProps) SortedKeys() []string {
 return android.SortedKeys(m.moduleToPropsMap)
}

// Information necessary to generate the filesystem modules, including details about their
// dependencies
type FsGenState struct {
 // List of modules in `PRODUCT_PACKAGES` and `PRODUCT_PACKAGES_DEBUG`
 depCandidatesMap map[string]bool
 // Map of names of partition to the information of modules to be added as deps
 fsDeps map[string]*multilibDeps
 // Information about the main soong-generated partitions
 soongGeneratedPartitions allGeneratedPartitionData
 // Mutex to protect the fsDeps
 fsDepsMutex sync.Mutex

 moduleToInstallationProps moduleToInstallationProps
 // List of prebuilt_* modules that are autogenerated.
 generatedPrebuiltEtcModuleNames []string
 // Mapping from a path to an avb key to the name of a filegroup module that contains it
 avbKeyFilegroups map[string]string
 // Name of all native bridge modules
 nativeBridgeModules map[string]bool

 // Name of the generated recovery fstab module name
 recoveryFstabModuleName string

 // Mapping of the partition type to the list of overridden modules that will be listed as
 // `Overridden_modules` in the generated filesystem modules
 overriddenModuleNames map[string][]string
}

type installationProperties struct {
 Required            []string // Modules that should be installed alongside
 RequiredBy          []string // List of modules (or PRODUCT_PACKAGES) that require this module to be installed
 Overrides           []string
 CcAndRustSharedLibs []string
 Partition           string
 Namespace           string
 ArchType            android.ArchType
}

func defaultDepCandidateProps(config android.Config) *depCandidateProps {
 return &depCandidateProps{
  Namespace:           ".",
  Arch:                []android.ArchType{config.DevicePrimaryArchType()},
  NativeBridgeSupport: map[android.NativeBridgeSupport]bool{android.NativeBridgeDisabled: true},
 }
}

type DeviceConfigContext interface {
 Config() android.Config
 DeviceConfig() android.DeviceConfig
}

func productInstalledModules(ctx DeviceConfigContext, makefile string) []string {
 productPkg := ctx.Config().ProductVariables().PartitionVarsForSoongMigrationOnlyDoNotUse.ProductPackagesSet[makefile]
 allInstalledModules := productPkg.ProductPackages
 if ctx.Config().Debuggable() {
  allInstalledModules = append(allInstalledModules, productPkg.ProductPackagesDebug...)
  if ctx.Config().Eng() {
   allInstalledModules = append(allInstalledModules, productPkg.ProductPackagesEng...)
  }
  if android.InList("address", ctx.Config().SanitizeDevice()) {
   allInstalledModules = append(allInstalledModules, productPkg.ProductPackagesDebugAsan...)
  }
  if ctx.Config().IsEnvTrue("EMMA_INSTRUMENT") {
   allInstalledModules = append(allInstalledModules, productPkg.ProductPackagesDebugJavaCoverage...)
  }
 }
 if android.InList("arm64", []string{ctx.DeviceConfig().DeviceArch(), ctx.DeviceConfig().DeviceSecondaryArch()}) {
  allInstalledModules = append(allInstalledModules, productPkg.ProductPackagesArm64...)
 }
 if android.UncheckedFinalApiLevel(29).GreaterThanOrEqualTo(ctx.DeviceConfig().ShippingApiLevel()) {
  allInstalledModules = append(allInstalledModules, productPkg.ProductPackagesShippingApiLevel29...)
 }
 if android.UncheckedFinalApiLevel(33).GreaterThanOrEqualTo(ctx.DeviceConfig().ShippingApiLevel()) {
  allInstalledModules = append(allInstalledModules, productPkg.ProductPackagesShippingApiLevel33...)
 }
 if android.UncheckedFinalApiLevel(34).GreaterThanOrEqualTo(ctx.DeviceConfig().ShippingApiLevel()) {
  allInstalledModules = append(allInstalledModules, productPkg.ProductPackagesShippingApiLevel34...)
 }

 return allInstalledModules
}

func createFsGenState(ctx android.LoadHookContext, generatedPrebuiltEtcModuleNames []string, avbpubkeyGenerated bool) *FsGenState {
 return ctx.Config().Once(fsGenStateOnceKey, func() interface{} {
  allInstalledModules := slices.Concat(
   productInstalledModules(ctx, "all"),
   generatedPrebuiltEtcModuleNames,
  )
  candidatesMap := map[string]bool{}
  for _, candidate := range allInstalledModules {
   candidatesMap[candidate] = true
  }
  fsGenState := FsGenState{
   depCandidatesMap: candidatesMap,
   fsDeps: map[string]*multilibDeps{
    // These additional deps are added according to the cuttlefish system image bp.
    "system": {
     // keep-sorted start
     "com.android.apex.cts.shim.v1_prebuilt":     defaultDepCandidateProps(ctx.Config()),
     "dex_bootjars":                              defaultDepCandidateProps(ctx.Config()),
     "framework_compatibility_matrix.device.xml": defaultDepCandidateProps(ctx.Config()),
     "init.environ.rc-soong":                     defaultDepCandidateProps(ctx.Config()),
     "libdmabufheap":                             defaultDepCandidateProps(ctx.Config()),
     "libgsi":                                    defaultDepCandidateProps(ctx.Config()),
     "llndk.libraries.txt":                       defaultDepCandidateProps(ctx.Config()),
     "logpersist.start":                          defaultDepCandidateProps(ctx.Config()),
     "notice_xml_system":                         defaultDepCandidateProps(ctx.Config()),
     "update_engine_sideload":                    defaultDepCandidateProps(ctx.Config()),
     // keep-sorted end
    },
    "vendor": {
     "fs_config_files_vendor":                               defaultDepCandidateProps(ctx.Config()),
     "fs_config_dirs_vendor":                                defaultDepCandidateProps(ctx.Config()),
     "notice_xml_vendor":                                    defaultDepCandidateProps(ctx.Config()),
     generatedModuleName(ctx.Config(), "vendor-build.prop"): defaultDepCandidateProps(ctx.Config()),
    },
    "odm": {
     // fs_config_* files are automatically installed for all products with odm partitions.
     // https://cs.android.com/android/_/android/platform/build/+/e4849e87ab660b59a6501b3928693db065ee873b:tools/fs_config/Android.mk;l=34;drc=8d6481b92c4b4e9b9f31a61545b6862090fcc14b;bpv=1;bpt=0
     "fs_config_files_odm": defaultDepCandidateProps(ctx.Config()),
     "fs_config_dirs_odm":  defaultDepCandidateProps(ctx.Config()),
     "notice_xml_odm":      defaultDepCandidateProps(ctx.Config()),
    },
    "product": {
     "notice_xml_product": defaultDepCandidateProps(ctx.Config()),
    },
    "system_ext": {
     "notice_xml_system_ext": defaultDepCandidateProps(ctx.Config()),
    },
    "userdata": {},
    "system_dlkm": {
     // these are phony required deps of the phony fs_config_dirs_nonsystem
     "fs_config_dirs_system_dlkm":  defaultDepCandidateProps(ctx.Config()),
     "fs_config_files_system_dlkm": defaultDepCandidateProps(ctx.Config()),
     "notice_xml_system_dlkm":      defaultDepCandidateProps(ctx.Config()),
    },
    "vendor_dlkm": {
     "fs_config_dirs_vendor_dlkm":  defaultDepCandidateProps(ctx.Config()),
     "fs_config_files_vendor_dlkm": defaultDepCandidateProps(ctx.Config()),
     "notice_xml_vendor_dlkm":      defaultDepCandidateProps(ctx.Config()),
     "vendor_dlkm-build.prop":      defaultDepCandidateProps(ctx.Config()),
    },
    "odm_dlkm": {
     "fs_config_dirs_odm_dlkm":  defaultDepCandidateProps(ctx.Config()),
     "fs_config_files_odm_dlkm": defaultDepCandidateProps(ctx.Config()),
     "notice_xml_odm_dlkm":      defaultDepCandidateProps(ctx.Config()),
    },
    "ramdisk":                      {},
    "vendor_ramdisk":               {},
    "vendor_ramdisk-debug":         {},
    "vendor_ramdisk_fragment_dlkm": {},
    "vendor_ramdisk-test-harness":  {},
    "vendor_kernel_ramdisk":        {},
    "recovery": {
     "sepolicy.recovery":                     defaultDepCandidateProps(ctx.Config()),
     "plat_file_contexts.recovery":           defaultDepCandidateProps(ctx.Config()),
     "plat_service_contexts.recovery":        defaultDepCandidateProps(ctx.Config()),
     "plat_property_contexts.recovery":       defaultDepCandidateProps(ctx.Config()),
     "system_ext_file_contexts.recovery":     defaultDepCandidateProps(ctx.Config()),
     "system_ext_service_contexts.recovery":  defaultDepCandidateProps(ctx.Config()),
     "system_ext_property_contexts.recovery": defaultDepCandidateProps(ctx.Config()),
     "vendor_file_contexts.recovery":         defaultDepCandidateProps(ctx.Config()),
     "vendor_service_contexts.recovery":      defaultDepCandidateProps(ctx.Config()),
     "vendor_property_contexts.recovery":     defaultDepCandidateProps(ctx.Config()),
     "odm_file_contexts.recovery":            defaultDepCandidateProps(ctx.Config()),
     "odm_property_contexts.recovery":        defaultDepCandidateProps(ctx.Config()),
     "product_file_contexts.recovery":        defaultDepCandidateProps(ctx.Config()),
     "product_service_contexts.recovery":     defaultDepCandidateProps(ctx.Config()),
     "product_property_contexts.recovery":    defaultDepCandidateProps(ctx.Config()),
    },
    "debug_ramdisk": {
     "force_debuggable": defaultDepCandidateProps(ctx.Config()),
    }, // TODO: move this to PRODUCT_PACKAGES
    "test_harness_ramdisk": {
     "adb_debug.test_harness.prop": defaultDepCandidateProps(ctx.Config()),
    }, // TODO: move this to PRODUCT_PACKAGES
   },
   fsDepsMutex: sync.Mutex{},
   moduleToInstallationProps: moduleToInstallationProps{
    moduleToPropsMap:         map[string]installationProperties{},
    baseModuleNameToPropsMap: map[string][]installationProperties{},
   },
   generatedPrebuiltEtcModuleNames: generatedPrebuiltEtcModuleNames,
   avbKeyFilegroups:                map[string]string{},
   nativeBridgeModules:             map[string]bool{},
   overriddenModuleNames:           map[string][]string{},
  }

  if avbpubkeyGenerated {
   (*fsGenState.fsDeps["product"])["system_other_avbpubkey"] = defaultDepCandidateProps(ctx.Config())
  }

  if len(ctx.Config().DeviceManifestFiles()) > 0 {
   (*fsGenState.fsDeps["vendor"])["vendor_manifest.xml"] = defaultDepCandidateProps(ctx.Config())
  }

  // Add common resources `prebuilt_res` module as dep of recovery partition
  (*fsGenState.fsDeps["recovery"])[fmt.Sprintf("recovery-resources-common-%s", getDpi(ctx))] = defaultDepCandidateProps(ctx.Config())
  (*fsGenState.fsDeps["recovery"])[getRecoveryFontModuleName(ctx)] = defaultDepCandidateProps(ctx.Config())
  (*fsGenState.fsDeps["recovery"])[createRecoveryBuildProp(ctx)] = defaultDepCandidateProps(ctx.Config())
  if name, _ := getRecoveryBackgroundPicturesGeneratorModuleName(ctx); name != "" {
   (*fsGenState.fsDeps["recovery"])[name] = defaultDepCandidateProps(ctx.Config())
  }
  if name := createTargetRecoveryWipeModuleName(ctx); name != "" {
   (*fsGenState.fsDeps["recovery"])[name] = defaultDepCandidateProps(ctx.Config())
  }
  if name := handleRecoveryFstab(ctx); name != "" {
   (*fsGenState.fsDeps["recovery"])[name] = defaultDepCandidateProps(ctx.Config())
   fsGenState.recoveryFstabModuleName = name
  }

  // VNDK APEXes are deprecated and are not supported and disabled for riscv64 arch.
  // Adding these modules as deps of the auto generated riscv64 arch filesystem modules
  // leads to execution time build error, thus do not add them as deps when building
  // riscv64 arch product.
  if ctx.Config().DevicePrimaryArchType() != android.Riscv64 {
   for _, vndkVersion := range ctx.DeviceConfig().ExtraVndkVersions() {
    (*fsGenState.fsDeps["system_ext"])["com.android.vndk.v"+vndkVersion] = defaultDepCandidateProps(ctx.Config())
   }
  }

  if ctx.Config().ProductVariables().PartitionVarsForSoongMigrationOnlyDoNotUse.BuildingSystemDlkmImage {
   (*fsGenState.fsDeps["system_dlkm"])["system_dlkm-build.prop"] = defaultDepCandidateProps(ctx.Config())
  } else {
   // system_dlkm build.prop is installed in system partition if system_dlkm.img is not available
   (*fsGenState.fsDeps["system"])["system_dlkm-build.prop"] = defaultDepCandidateProps(ctx.Config())
  }

  if ctx.Config().ProductVariables().PartitionVarsForSoongMigrationOnlyDoNotUse.BuildingOdmDlkmImage {
   (*fsGenState.fsDeps["odm_dlkm"])["odm_dlkm-build.prop"] = defaultDepCandidateProps(ctx.Config())
  } else {
   // odm_dlkm build.prop is installed in vendor partition if odm_dlkm.img is not available
   (*fsGenState.fsDeps["vendor"])["odm_dlkm-build.prop"] = defaultDepCandidateProps(ctx.Config())
  }

  dtbo, dtbo16k := createPrebuiltDtboImages(ctx)
  if bootOtas := createBootOtas16kModules(ctx, dtbo, dtbo16k); bootOtas != "" &&
   ctx.Config().ProductVariables().PartitionVarsForSoongMigrationOnlyDoNotUse.Board16kOtaMoveVendor {
   (*fsGenState.fsDeps["vendor"])[bootOtas] = defaultDepCandidateProps(ctx.Config())
  }

  return &fsGenState
 }).(*FsGenState)
}

func checkDepModuleInMultipleNamespaces(mctx android.BottomUpMutatorContext, foundDeps multilibDeps, module string, partitionName string) {
 otherNamespace := mctx.Namespace().Path
 if val, found := foundDeps[module]; found && otherNamespace != "." && !android.InList(val.Namespace, []string{".", otherNamespace}) {
  mctx.ModuleErrorf("found in multiple namespaces(%s and %s) when including in %s partition", val.Namespace, otherNamespace, partitionName)
 }
}

func appendDepIfAppropriate(mctx android.BottomUpMutatorContext, deps *multilibDeps, installPartition string, nbs android.NativeBridgeSupport, moduleName string) {
 checkDepModuleInMultipleNamespaces(mctx, *deps, moduleName, installPartition)
 arch := mctx.Module().Target().Arch.ArchType
 if android.InList(installPartition, []string{
  "recovery",
  "ramdisk",
  "vendor_ramdisk",
  "debug_ramdisk",
 }) {
  // Only the primary arch is supported for these partitions.
  // https://cs.android.com/android/_/android/platform/build/soong/+/d046c2afef086a35d24222b09f4d2c4914e8a2a5:android/arch.go;l=618-621;drc=92ac46d1fe04a94d94025554bcecc5f8cb2416ae;bpv=1;bpt=0
  arch = mctx.Config().DevicePrimaryArchType()
 }
 if _, ok := (*deps)[moduleName]; ok {
  // Prefer the namespace-specific module over the platform module
  if mctx.Namespace().Path != "." {
   (*deps)[moduleName].Namespace = mctx.Namespace().Path
  }
  (*deps)[moduleName].Arch = append((*deps)[moduleName].Arch, arch)
  (*deps)[moduleName].NativeBridgeSupport[nbs] = true
 } else {
  multilib, _ := mctx.Module().DecodeMultilib(mctx)
  (*deps)[moduleName] = &depCandidateProps{
   Namespace:           mctx.Namespace().Path,
   Arch:                []android.ArchType{arch},
   Multilib:            multilib,
   NativeBridgeSupport: map[android.NativeBridgeSupport]bool{nbs: true},
  }
 }
}

func isEligibleForFsDeps(mctx android.BottomUpMutatorContext) bool {
 m := mctx.Module()
 // Only add the module as dependency when:
 // - it is enabled
 // - its namespace is included in PRODUCT_SOONG_NAMESPACES
 // - it is not hidden from make
 // - it is a preferred variant in a source/prebuilt pair
 return m.Enabled(mctx) && m.ExportedToMake() && !m.IsHideFromMake() && android.IsModulePreferred(m)
}

func collectDepsMutator(mctx android.BottomUpMutatorContext) {
 if !shouldEnableFilesystemCreator(mctx) {
  return
 }
 m := mctx.Module()
 if m.Target().Os.Class != android.Device {
  return
 }
 fsGenState := mctx.Config().Get(fsGenStateOnceKey).(*FsGenState)

 fsGenState.fsDepsMutex.Lock()
 defer fsGenState.fsDepsMutex.Unlock()

 moduleName := mctx.ModuleName()
 if p, ok := m.(android.PrebuiltInterface); ok && p.Prebuilt() != nil {
  if mm, ok := m.(interface{ BaseModuleName() string }); ok {
   moduleName = mm.BaseModuleName()
  }
 }

 image, imageOk := mctx.Module().(android.ImageInterface)

 if _, ok := fsGenState.depCandidatesMap[moduleName]; ok {
  installPartition := m.PartitionTag(mctx.DeviceConfig())
  systemPartitionFalsePositive := installPartition == "system" && android.InList(m.ImageVariation().Variation, []string{
   // cc/image.go marks some ramdisk and recovery modules as platform.
   // https://cs.android.com/android/platform/superproject/main/+/main:build/soong/cc/image.go;l=514-522?q=MakeAsPlatform%20f:build%2Fsoong&ss=android%2Fplatform%2Fsuperproject%2Fmain
   // Skip them in fsgen.
   android.RamdiskVariation,
   android.VendorRamdiskVariation,
   android.RecoveryVariation,
  })
  if isEligibleForFsDeps(mctx) && !systemPartitionFalsePositive {
   appendDepIfAppropriate(mctx, fsGenState.fsDeps[installPartition], installPartition, android.NativeBridgeDisabled, mctx.ModuleName())
  }
 }

 if _, ok := fsGenState.depCandidatesMap[mctx.ModuleName()+".native_bridge"]; ok {
  installPartition := m.PartitionTag(mctx.DeviceConfig())
  // Native bridge is only supported for system partition modules.
  // https://cs.android.com/android/_/android/platform/build/soong/+/d046c2afef086a35d24222b09f4d2c4914e8a2a5:android/arch.go;l=604;drc=92ac46d1fe04a94d94025554bcecc5f8cb2416ae;bpv=1;bpt=0
  if isEligibleForFsDeps(mctx) && installPartition == "system" {
   appendDepIfAppropriate(mctx, fsGenState.fsDeps[installPartition], installPartition, android.NativeBridgeEnabled, mctx.ModuleName())
  }
 } else if _, ok := fsGenState.depCandidatesMap[mctx.ModuleName()+".bootstrap.native_bridge"]; ok {
  installPartition := m.PartitionTag(mctx.DeviceConfig())
  // Native bridge is only supported for system partition modules.
  // https://cs.android.com/android/_/android/platform/build/soong/+/d046c2afef086a35d24222b09f4d2c4914e8a2a5:android/arch.go;l=604;drc=92ac46d1fe04a94d94025554bcecc5f8cb2416ae;bpv=1;bpt=0
  if isEligibleForFsDeps(mctx) && installPartition == "system" {
   appendDepIfAppropriate(mctx, fsGenState.fsDeps[installPartition], installPartition, android.NativeBridgeEnabled, mctx.ModuleName())
  }
 }
 if _, ok := fsGenState.depCandidatesMap[mctx.ModuleName()+".vendor_ramdisk"]; ok && imageOk && image.VendorRamdiskVariantNeeded(mctx) {
  installPartition := "vendor_ramdisk"
  if isEligibleForFsDeps(mctx) {
   appendDepIfAppropriate(mctx, fsGenState.fsDeps[installPartition], installPartition, android.NativeBridgeDisabled, mctx.ModuleName())
  }
 }
 if _, ok := fsGenState.depCandidatesMap[mctx.ModuleName()+".recovery"]; ok && imageOk && image.RecoveryVariantNeeded(mctx) {
  installPartition := "recovery"
  if isEligibleForFsDeps(mctx) {
   appendDepIfAppropriate(mctx, fsGenState.fsDeps[installPartition], installPartition, android.NativeBridgeDisabled, mctx.ModuleName())
  }
 }

 // store the map of module to (required,overrides) even if the module is not in PRODUCT_PACKAGES.
 // the module might be installed transitively.
 if isEligibleForFsDeps(mctx) {
  var ccAndRustSharedLibs []string
  if rustModule, ok := m.(*rust.Module); ok {
   if !rustModule.StdLinkageIsRlibLinkage(mctx.Device()) {
    for _, prop := range m.GetProperties() {
     if rustCompilerProps, ok := prop.(*rust.BaseCompilerProperties); ok {
      ccAndRustSharedLibs = rustCompilerProps.Rustlibs.GetOrDefault(mctx, nil)
     }
    }
   }
  }
  if _, ok := m.(*cc.Module); ok {
   for _, prop := range m.GetProperties() {
    if linkerProps, ok := prop.(*cc.BaseLinkerProperties); ok {
     deps := cc.CoalesceLibs(mctx, linkerProps, cc.Deps{})
     ccAndRustSharedLibs = append(ccAndRustSharedLibs, deps.SharedLibs...)
    }
   }
  }

  fsGenState.moduleToInstallationProps.AddToMap(mctx, &installationProperties{
   Required:            m.RequiredModuleNames(mctx),
   CcAndRustSharedLibs: ccAndRustSharedLibs,
   Overrides:           m.Overrides(),
   Partition:           m.PartitionTag(mctx.DeviceConfig()),
   Namespace:           mctx.Namespace().Path,
   ArchType:            mctx.Target().Arch.ArchType,
  })
 }

 if mctx.Target().NativeBridge == android.NativeBridgeEnabled {
  fsGenState.nativeBridgeModules[fullyQualifiedModuleName(mctx.ModuleName(), mctx.Namespace().Path)] = true
 }
}

type depsStruct struct {
 Deps []string
}

type multilibDepsStruct struct {
 Common        depsStruct
 Lib32         depsStruct
 Lib64         depsStruct
 Both          depsStruct
 Prefer32      depsStruct
 Native_bridge depsStruct
}

type packagingPropsStruct struct {
 Overridden_deps    []string
 High_priority_deps []string
 Deps               []string
 Multilib           multilibDepsStruct
}

func fullyQualifiedModuleName(moduleName, namespace string) string {
 if namespace == "." || strings.HasPrefix(moduleName, "//") {
  return moduleName
 }
 return fmt.Sprintf("//%s:%s", namespace, moduleName)
}

func getBitness(archTypes []android.ArchType) (ret []string) {
 for _, archType := range archTypes {
  if archType.Multilib == "" {
   ret = append(ret, android.COMMON_VARIANT)
  } else {
   ret = append(ret, archType.Bitness())
  }
 }
 return ret
}

func removeDepsMutator(mctx android.BottomUpMutatorContext) {
 if !shouldEnableFilesystemCreator(mctx) {
  return
 }
 fsGenState := mctx.Config().Get(fsGenStateOnceKey).(*FsGenState)
 fsGenState.fsDepsMutex.Lock()
 defer fsGenState.fsDepsMutex.Unlock()
 updatePartitionsOfOverrideModules(mctx)
}

func crossPartitionRequiredMutator(mctx android.BottomUpMutatorContext) {
 if !shouldEnableFilesystemCreator(mctx) {
  return
 }
 fsGenState := mctx.Config().Get(fsGenStateOnceKey).(*FsGenState)
 fsGenState.fsDepsMutex.Lock()
 defer fsGenState.fsDepsMutex.Unlock()
 additionalCrossPartitionRequiredDeps := correctCrossPartitionRequiredDeps(mctx.Config())
 fullyQualifiedModuleName := fullyQualifiedModuleName(mctx.ModuleName(), mctx.Namespace().Path)
 if xPartitionDep, ok := additionalCrossPartitionRequiredDeps[fullyQualifiedModuleName]; ok && mctx.Module().PartitionTag(mctx.DeviceConfig()) == xPartitionDep.partition {
  // For shared libraries, add the dependency only if the archType of the dep and parent match.
  addXPartitionDep := !xPartitionDep.isSharedLibDep || android.InList(mctx.Target().Arch.ArchType, xPartitionDep.archesOfRequiredSharedLibDep)
  if addXPartitionDep {
   appendDepIfAppropriate(mctx, fsGenState.fsDeps[xPartitionDep.partition], xPartitionDep.partition, android.NativeBridgeDisabled, mctx.ModuleName())
  }
 }
}

func setDepsMutator(mctx android.BottomUpMutatorContext) {
 if !shouldEnableFilesystemCreator(mctx) {
  return
 }
 removeOverriddenDeps(mctx)
 fsGenState := mctx.Config().Get(fsGenStateOnceKey).(*FsGenState)
 fsDeps := fsGenState.fsDeps
 m := mctx.Module()
 if partition := fsGenState.soongGeneratedPartitions.typeForName(m.Name()); partition != "" {
  if fsGenState.soongGeneratedPartitions.isHandwritten(m.Name()) {
   // Handwritten image, don't modify it
   return
  }

  var overriddenDeps []string
  if deps, ok := fsGenState.overriddenModuleNames[partition]; ok {
   overriddenDeps = deps
  }

  if partition == "tzsw" {
   // tzsw is a prebuilt file, and does not use android_filesystem module type.
   return
  }

  backgroundRecoveryImageGenerator, _ := getRecoveryBackgroundPicturesGeneratorModuleName(mctx)
  // backgroundRecoveryImageGenerator generates additional images which takes precedence over images files
  // created by other deps of recovery.img.
  // Use this in highPriorityDeps
  depsStruct := generateDepStruct(*fsDeps[partition], append([]string{backgroundRecoveryImageGenerator}, fsGenState.generatedPrebuiltEtcModuleNames...), overriddenDeps)
  if err := proptools.AppendMatchingProperties(m.GetProperties(), depsStruct, nil); err != nil {
   mctx.ModuleErrorf(err.Error())
  }
 }
}

// Adds override apps (override_android_app, override_apex, ...) to the partition of their `base` apps.
func updatePartitionsOfOverrideModules(mctx android.BottomUpMutatorContext) {
 if override, ok := mctx.Module().(android.OverrideModule); ok {
  fsGenState := mctx.Config().Get(fsGenStateOnceKey).(*FsGenState)
  fsDeps := fsGenState.fsDeps
  overridePartition := mctx.Module().PartitionTag(mctx.DeviceConfig())
  if _, ok := (*fsDeps[overridePartition])[mctx.Module().Name()]; !ok {
   // The override module is not in PRODUCT_PACKAGES
   return
  }
  base := override.GetOverriddenModuleName()
  if strings.HasPrefix(base, "//") { // Has path prefix, which is either the path to the module or the namespace
   base = strings.Split(base, ":")[1]

   // TODO (b/420968370): Re-enable this after we enforce that all namespaces are valid.

   //pathOrNamspace := strings.TrimPrefix(strings.Split(base, ":")[0], "//")
   // If the path prefix is not within the exported namespace, it is likely that the
   // prefix is the path to the module, not the namespace. In that case, drop the
   // prefix as the non-namespace path prefix is not part of the fully qualified module
   // name.
   //if !android.InList(pathOrNamspace, mctx.Config().ProductVariables().NamespacesToExport) {
   // base = strings.Split(base, ":")[1]
   //}
  }

  // TODO (b/420968370): Use fully qualifed name after we enforce that all namespaces are valid.
  if baseModuleProps, ok := fsGenState.moduleToInstallationProps.baseModuleNameToPropsMap[base]; ok && isEligibleForFsDeps(mctx) {
   basePartitionCandidates := []string{}
   for _, ip := range baseModuleProps {
    basePartitionCandidates = append(basePartitionCandidates, ip.Partition)
   }
   basePartitionCandidates = android.SortedUniqueStrings(basePartitionCandidates)
   if len(basePartitionCandidates) > 1 {
    mctx.ModuleErrorf("Could not determine partition of base module %s. Possible partitions %s\n", base, basePartitionCandidates)
   }
   partition := basePartitionCandidates[0]
   appendDepIfAppropriate(mctx, fsDeps[partition], partition, android.NativeBridgeDisabled, mctx.Module().Name())
  }
 }
}

type queue struct {
 internalQueue *list.List
}

func (q *queue) Pop() string {
 ret := q.internalQueue.Front()
 if ret == nil {
  return ""
 }
 q.internalQueue.Remove(ret)
 return ret.Value.(string)
}

func (q *queue) Add(inputs ...string) {
 for _, input := range inputs {
  q.internalQueue.PushBack(input)
 }
}

func (q *queue) Len() int {
 return q.internalQueue.Len()
}

// removeOverriddenDeps collects PRODUCT_PACKAGES and (transitive) required deps.
// it then removes any modules which appear in `overrides` of the above list.
// Returns the list of names of the overridden modules. These are passed as `Overridden_modules`
// when generating the filesystem modules.
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, moduleInfo := range *fsDep {
    fullyQualifiedDepName := depName
    // If depName is not fully qualified and the dep specifies namespace, append the
    // namespace for correct lookup in Step 2.
    if !strings.HasPrefix(depName, "//") && !android.InList(moduleInfo.Namespace, []string{"", "."}) {
     fullyQualifiedDepName = fmt.Sprintf("//%s:%s", moduleInfo.Namespace, fullyQualifiedDepName)
    }
    allDeps = append(allDeps, fullyQualifiedDepName)
   }
  }

  // Record all modules' required rdeps (i.e. modules that set the module as a required
  // dependency) and whether if the module is installed as a top level module.
  moduleToRequiredRdepsMap := map[string][]string{}
  for _, productPackagesEntry := range productInstalledModules(mctx, "all") {
   if moduleName, _, ok := fsGenState.moduleToInstallationProps.GetFromModuleName(productPackagesEntry); ok {
    moduleToRequiredRdepsMap[moduleName] = append(moduleToRequiredRdepsMap[moduleName], "PRODUCT_PACKAGES")
   }
  }

  // Step 2: Process the queue, and add required modules to the queue.
  i := 0
  for {
   if i == len(allDeps) {
    break
   }
   depName := allDeps[i]
   props, _ := fsGenState.moduleToInstallationProps.GetFromFullyQualifiedModuleName(depName)
   for _, overrides := range props.Overrides {
    if _, ok := fsGenState.nativeBridgeModules[depName]; ok {
     // Do not remove automatically remove overrides of native bridge modules
     // Some native_bridge_supported modules override the native_bridge variant
     // of another module, but not the "main" variant.
     // Determining this in fsgen requires additional information. Defer this to
     // android_filesystem.
     continue
    }
    overridden[overrides] = true
   }
   for _, requiredModule := range props.Required {
    if requiredModuleName, _, ok := fsGenState.moduleToInstallationProps.GetFromModuleName(requiredModule); ok {
     moduleToRequiredRdepsMap[requiredModuleName] = append(moduleToRequiredRdepsMap[requiredModuleName], depName)
    }
   }

   // add required dep to the queue.
   allDeps = append(allDeps, props.Required...)
   i += 1
  }

  fullyQualifiedOverriddenModuleNames := map[string]installationProperties{}
  for overridden := range overridden {
   if fullyQualifiedModuleName, props, ok := fsGenState.moduleToInstallationProps.GetFromModuleName(overridden); ok {
    fullyQualifiedOverriddenModuleNames[fullyQualifiedModuleName] = props
   }
  }

  removeModuleFromFsDeps := func(moduleName string) {
   for partition := range fsDeps {
    delete(*fsDeps[partition], moduleName)
   }
  }

  // isOverriddenModule returns true if the module itself is overridden by another module,
  // or is transitively overridden as all of its required reverse dependencies are overridden.
  // The module is not overridden if it is listed in PRODUCT_PACKAGES, even all of its
  // required reverse dependencies are overridden
  isOverriddenModule := func(moduleName string) bool {
   // check if the module itself is overridden
   if _, ok := fullyQualifiedOverriddenModuleNames[moduleName]; ok {
    return true
   }

   // check if all of its required reverse dependencies are overridden
   rdeps, ok := moduleToRequiredRdepsMap[moduleName]
   if !ok {
    return false
   }
   for _, rdep := range rdeps {
    // The module cannot be transitively overridden if it is listed in PRODUCT_PACKAGES
    if rdep == "PRODUCT_PACKAGES" {
     return false
    } else if _, ok := fullyQualifiedOverriddenModuleNames[rdep]; !ok {
     return false
    }
   }

   return true
  }

  // Step 3: Delete all the overridden modules and its required deps.
  // The module is removed only if all of its required rdeps are overridden.
  // e.g. if the module is referenced by multiple modules as a required dependency
  // and if any of the rdep modules are not overridden, the module should be installed.
  for _, overridden := range android.SortedKeys(fullyQualifiedOverriddenModuleNames) {
   requiredQueue := queue{internalQueue: list.New()}
   requiredQueue.Add(overridden)

   // Iterate over overridden module and its rdeps until the queue is empty.
   // Rdeps are added to the queue if the module is overridden
   for requiredQueue.Len() > 0 {
    requiredModule := requiredQueue.Pop()
    if isOverriddenModule(requiredModule) {
     removeModuleFromFsDeps(requiredModule)
     requiredModuleProp, _ := fsGenState.moduleToInstallationProps.GetFromFullyQualifiedModuleName(requiredModule)
     for _, requiredDep := range requiredModuleProp.Required {
      if fullyQualifiedRequiredDepName, _, ok := fsGenState.moduleToInstallationProps.GetFromModuleName(requiredDep); ok {
       requiredQueue.Add(fullyQualifiedRequiredDepName)
      }
     }
    }
   }
  }

  filteredOverriddenDepsMap := make(map[string][]string)
  for _, overriddenDep := range android.SortedKeys(fullyQualifiedOverriddenModuleNames) {
   prop := fullyQualifiedOverriddenModuleNames[overriddenDep]
   filteredOverriddenDepsMap[prop.Partition] = append(filteredOverriddenDepsMap[prop.Partition], overriddenDep)
  }

  fsGenState.overriddenModuleNames = filteredOverriddenDepsMap
  return nil
 })
}

type directDepWithParentPartition struct {
 // name of the install partition of the parent module
 parentPartition string
 parentArchType  android.ArchType
 // fully qualified module name of the "required" direct dep
 directDepName string
 // whether this is a rustlib or native shared lib dependency
 isSharedLibDep bool
}

type crossPartitionRequiredDep struct {
 partition      string
 isSharedLibDep bool
 // Arches of the binary that requested the cross partition dependency.
 archesOfRequiredSharedLibDep []android.ArchType
}

// This function is run only once to compute the list of transitive "required" dependencies
// where the install partition differs from that of the direct reverse dependency (i.e. parent
// module). Note that this is done via a graph walk from the top level deps of the autogenerated
// filesystem modules. Thus, the module will not be included in the returning map even when the
// install partition differs from that of the parent module if the module is not installed
// for the target product.
// The return value is a mapping of fully qualified module name to their install partition and arch types.
func correctCrossPartitionRequiredDeps(config android.Config) map[string]crossPartitionRequiredDep {
 return config.Once(fsGenCrossPartitionRequiredDepsOnceKey, func() interface{} {
  fsGenState := config.Get(fsGenStateOnceKey).(*FsGenState)
  fsDeps := fsGenState.fsDeps
  moduleToInstallationProps := fsGenState.moduleToInstallationProps

  // Mapping of fully qualified module name to its list of install partition
  // Given that a single module cannot be listed as deps of multiple filesystem modules,
  // the key is a single string value instead of a list of strings
  ret := make(map[string]crossPartitionRequiredDep)

  // Add the pair of:
  // 1. install partition of the top level dep module
  // 2. fully qualified module name of the direct dep of the top level dep module
  // to the stack to perform dfs.
  moduleNamesStack := []directDepWithParentPartition{}
  for _, partition := range android.SortedKeys(fsDeps) {
   for _, topLevelModule := range fsDeps[partition].SortedFullyQualifiedNames() {
    if props, ok := moduleToInstallationProps.GetFromFullyQualifiedModuleName(topLevelModule); ok {
     for _, requiredModule := range props.Required {
      moduleNamesStack = append(moduleNamesStack, directDepWithParentPartition{
       parentPartition: partition,
       parentArchType:  props.ArchType,
       directDepName:   fullyQualifiedModuleName(requiredModule, props.Namespace),
      })
     }
     // system_ext-specific image variation is not created, thus system_ext
     // rust or cc module will link against system rustlibs or shared libs.
     // Since cross-partition installation is not supported in filesystem modules,
     // system rustlibs or shared libs of system_ext_specific modules should be
     // separately added as deps of the system image.
     if partition == "system_ext" {
      for _, sharedLibModule := range props.CcAndRustSharedLibs {
       moduleNamesStack = append(moduleNamesStack, directDepWithParentPartition{
        parentPartition: partition,
        parentArchType:  props.ArchType,
        directDepName:   fullyQualifiedModuleName(sharedLibModule, props.Namespace),
        isSharedLibDep:  true,
       })
      }
     }
    }
   }
  }

  // map of fully qualified module names to store the names of modules that have been
  // visited during the traversal
  traversalMap := map[string]bool{}

  // Iterate through the stack and find modules where the partition does not match that of
  // the parent module
  for len(moduleNamesStack) > 0 {
   // Pop the last element from the stack
   visitingModule := moduleNamesStack[len(moduleNamesStack)-1]
   moduleNamesStack = moduleNamesStack[:len(moduleNamesStack)-1]

   // Add the fully qualified module name to the returning map with its install
   // partition if it does not match that of its parent.
   // If the module has already been visited, it means its required direct deps has
   // already been visited. Thus do not add the required deps to the stack.
   // If it's the first time visiting the module, add the required deps to the stack and
   // mark the module visited.
   if moduleProps, ok := moduleToInstallationProps.GetFromFullyQualifiedModuleName(visitingModule.directDepName); ok {
    if moduleProps.Partition != visitingModule.parentPartition {
     if !visitingModule.isSharedLibDep || moduleProps.Partition == "system" {
      if entry, exists := ret[visitingModule.directDepName]; exists {
       archesOfRequiredSharedLibDep := append(entry.archesOfRequiredSharedLibDep, visitingModule.parentArchType)
       entry.archesOfRequiredSharedLibDep = archesOfRequiredSharedLibDep
      } else {
       ret[visitingModule.directDepName] = crossPartitionRequiredDep{
        partition:                    moduleProps.Partition,
        isSharedLibDep:               visitingModule.isSharedLibDep,
        archesOfRequiredSharedLibDep: []android.ArchType{visitingModule.parentArchType},
       }
      }
     }
    }
    if _, ok := traversalMap[visitingModule.directDepName]; !ok {
     traversalMap[visitingModule.directDepName] = true
     for _, requiredModule := range moduleProps.Required {
      moduleNamesStack = append(moduleNamesStack, directDepWithParentPartition{
       parentPartition: moduleProps.Partition,
       directDepName:   requiredModule,
      })
     }
     if moduleProps.Partition == "system_ext" {
      for _, rustLibModule := range moduleProps.CcAndRustSharedLibs {
       moduleNamesStack = append(moduleNamesStack, directDepWithParentPartition{
        parentPartition: moduleProps.Partition,
        directDepName:   rustLibModule,
        isSharedLibDep:  true,
       })
      }
     }
    }
   }
  }
  return ret
 }).(map[string]crossPartitionRequiredDep)
}

var HighPriorityDeps = []string{}

func isHighPriorityDep(depName string) bool {
 for _, highPriorityDeps := range HighPriorityDeps {
  if strings.HasPrefix(depName, highPriorityDeps) {
   return true
  }
 }
 return false
}

func generateDepStruct(deps map[string]*depCandidateProps, highPriorityDeps []string, overriddenDeps []string) *packagingPropsStruct {
 depsStruct := packagingPropsStruct{}
 for depName, depProps := range deps {
  if _, ok := depProps.NativeBridgeSupport[android.NativeBridgeDisabled]; !ok {
   // Only the native bridge variant of this dep should be added.
   // This will be done separately.
   continue
  }
  bitness := getBitness(depProps.Arch)
  fullyQualifiedDepName := fullyQualifiedModuleName(depName, depProps.Namespace)
  if android.InList(depName, highPriorityDeps) {
   depsStruct.High_priority_deps = append(depsStruct.High_priority_deps, fullyQualifiedDepName)
  } else if android.InList("32", bitness) && android.InList("64", bitness) {
   // If both 32 and 64 bit variants are enabled for this module
   switch depProps.Multilib {
   case string(android.MultilibBoth):
    depsStruct.Multilib.Both.Deps = append(depsStruct.Multilib.Both.Deps, fullyQualifiedDepName)
   case string(android.MultilibCommon), string(android.MultilibFirst):
    depsStruct.Deps = append(depsStruct.Deps, fullyQualifiedDepName)
   case "32":
    depsStruct.Multilib.Lib32.Deps = append(depsStruct.Multilib.Lib32.Deps, fullyQualifiedDepName)
   case "64", "darwin_universal":
    depsStruct.Multilib.Lib64.Deps = append(depsStruct.Multilib.Lib64.Deps, fullyQualifiedDepName)
   case "prefer32", "first_prefer32":
    depsStruct.Multilib.Prefer32.Deps = append(depsStruct.Multilib.Prefer32.Deps, fullyQualifiedDepName)
   default:
    depsStruct.Multilib.Both.Deps = append(depsStruct.Multilib.Both.Deps, fullyQualifiedDepName)
   }
  } else if android.InList("64", bitness) {
   // If only 64 bit variant is enabled
   depsStruct.Multilib.Lib64.Deps = append(depsStruct.Multilib.Lib64.Deps, fullyQualifiedDepName)
  } else if android.InList("32", bitness) {
   // If only 32 bit variant is enabled
   depsStruct.Multilib.Lib32.Deps = append(depsStruct.Multilib.Lib32.Deps, fullyQualifiedDepName)
  } else {
   // If only common variant is enabled
   depsStruct.Multilib.Common.Deps = append(depsStruct.Multilib.Common.Deps, fullyQualifiedDepName)
  }
 }
 // Add the native bridge deps
 var nativeBridgeDeps []string
 for depName, depProps := range deps {
  if _, ok := depProps.NativeBridgeSupport[android.NativeBridgeEnabled]; !ok {
   continue
  }
  if depProps.Namespace != "." { // Add the fully qualified name
   nativeBridgeDeps = append(nativeBridgeDeps, "//"+depProps.Namespace+":"+depName)
  } else {
   nativeBridgeDeps = append(nativeBridgeDeps, depName)
  }
 }

 depsStruct.Deps = android.SortedUniqueStrings(depsStruct.Deps)
 depsStruct.Multilib.Lib32.Deps = android.SortedUniqueStrings(depsStruct.Multilib.Lib32.Deps)
 depsStruct.Multilib.Lib64.Deps = android.SortedUniqueStrings(depsStruct.Multilib.Lib64.Deps)
 depsStruct.Multilib.Prefer32.Deps = android.SortedUniqueStrings(depsStruct.Multilib.Prefer32.Deps)
 depsStruct.Multilib.Both.Deps = android.SortedUniqueStrings(depsStruct.Multilib.Both.Deps)
 depsStruct.Multilib.Common.Deps = android.SortedUniqueStrings(depsStruct.Multilib.Common.Deps)
 depsStruct.Multilib.Native_bridge.Deps = android.SortedUniqueStrings(nativeBridgeDeps)
 depsStruct.High_priority_deps = android.SortedUniqueStrings(depsStruct.High_priority_deps)
 depsStruct.Overridden_deps = android.SortedUniqueStrings(overriddenDeps)

 return &depsStruct
}