scripts/bp2build_progress/dependency_analysis.py - platform/build/bazel - Git at Google

 #!/usr/bin/env python3
 #
 # Copyright (C) 2022 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.
 """Utility functions to produce module or module type dependency graphs using json-module-graph or queryview."""

 import collections
 import dataclasses
 import json
 import os
 import os.path
 import subprocess
 import sys
 from typing import Dict, Optional, Set
 import xml.etree.ElementTree
 from bp2build_metrics_proto.bp2build_metrics_pb2 import Bp2BuildMetrics


 @dataclasses.dataclass(frozen=True, order=True)
 class TargetProduct:
   product: Optional[str] = None
   banchan_mode: bool = False


 @dataclasses.dataclass(frozen=True, order=True)
 class _ModuleKey:
   """_ModuleKey uniquely identifies a module by name nad variations."""

   name: str
   variations: list

   def __str__(self):
     return f"{self.name}, {self.variations}"

   def __hash__(self):
     return (self.name + str(self.variations)).__hash__()


 # This list of module types are omitted from the report and graph
 # for brevity and simplicity. Presence in this list doesn't mean
 # that they shouldn't be converted, but that they are not that useful
 # to be recorded in the graph or report currently.
 IGNORED_KINDS = set([
     "cc_defaults",
     "cpython3_python_stdlib",
     "hidl_package_root",  # not being converted, contents converted as part of hidl_interface
     "java_defaults",
     "license",
     "license_kind",
 ])

 # queryview doesn't have information on the type of deps, so we explicitly skip
 # prebuilt types
 _QUERYVIEW_IGNORE_KINDS = set([
     "android_app_import",
     "android_library_import",
     "cc_prebuilt_library",
     "cc_prebuilt_library_headers",
     "cc_prebuilt_library_shared",
     "cc_prebuilt_library_static",
     "cc_prebuilt_library_static",
     "cc_prebuilt_object",
     "java_import",
     "java_import_host",
     "java_sdk_library_import",
     "cpython3_python_stdlib",
     "cpython2_python_stdlib",
 ])


 # Soong adds some dependencies that are handled by Bazel as part of the
 # toolchain
 _TOOLCHAIN_DEP_TYPES = frozenset([
     "python.dependencyTag {BaseDependencyTag:{} name:hostLauncher}",
     "python.dependencyTag {BaseDependencyTag:{} name:hostLauncherSharedLib}",
     "python.dependencyTag {BaseDependencyTag:{} name:hostStdLib}",
     "python.dependencyTag {BaseDependencyTag:{} name:launcher}",
     (
         "python.installDependencyTag {BaseDependencyTag:{}"
         " InstallAlwaysNeededDependencyTag:{} name:launcherSharedLib}"
     ),
 ])

 def get_src_root_dir() -> str:
   # Search up the directory tree until we find soong_ui.bash as a regular file, not a symlink.
   # This is so that we find the real source tree root, and not the bazel execroot which symlimks in
   # soong_ui.bash.
   def soong_ui(path):
     return os.path.join(path, 'build/soong/soong_ui.bash')

   path = '.'
   while not os.path.isfile(soong_ui(path)) or os.path.islink(soong_ui(path)):
     if os.path.abspath(path) == '/':
       sys.exit('Could not find android source tree root.')
     path = os.path.join(path, '..')
   return os.path.abspath(path)

 SRC_ROOT_DIR = get_src_root_dir()

 LUNCH_ENV = {
     # Use aosp_arm as the canonical target product.
     "TARGET_PRODUCT": "aosp_arm",
     "TARGET_BUILD_VARIANT": "userdebug",
 }

 BANCHAN_ENV = {
     # Use module_arm64 as the canonical banchan target product.
     "TARGET_PRODUCT": "module_arm64",
     "TARGET_BUILD_VARIANT": "eng",
     # just needs to be non-empty, not the specific module for Soong
     # analysis purposes
     "TARGET_BUILD_APPS": "all",
 }

 _REQUIRED_PROPERTIES = [
     "Required",
     "Host_required",
     "Target_required",
 ]


 def _build_with_soong(target, target_product):
   env = BANCHAN_ENV if target_product.banchan_mode else LUNCH_ENV
   if target_product.product:
     env["TARGET_PRODUCT"] = target_product.product

   subprocess.check_output(
       [
           "build/soong/soong_ui.bash",
           "--make-mode",
           "--skip-soong-tests",
           target,
       ],
       cwd=SRC_ROOT_DIR,
       env=env,
   )


 def get_properties(json_module):
   set_properties = {}
   if "Module" not in json_module:
     return set_properties
   if "Android" not in json_module["Module"]:
     return set_properties
   if "SetProperties" not in json_module["Module"]["Android"]:
     return set_properties
   if json_module["Module"]["Android"]["SetProperties"] is None:
     return set_properties

   for prop in json_module["Module"]["Android"]["SetProperties"]:
     if prop["Values"]:
       value = prop["Values"]
     else:
       value = prop["Value"]
     set_properties[prop["Name"]] = value

   return set_properties


 def get_property_names(json_module):
   return get_properties(json_module).keys()


 def get_queryview_module_info_by_type(types, target_product):
   """Returns the list of transitive dependencies of input module as built by queryview."""
   _build_with_soong("queryview", target_product)

   queryview_xml = subprocess.check_output(
       [
           "build/bazel/bin/bazel",
           "query",
           "--config=ci",
           "--config=queryview",
           "--output=xml",
           # union of queries to get the deps of all Soong modules with the give names
           " + ".join(
               f'deps(attr("soong_module_type", "^{t}$", //...))' for t in types
           ),
       ],
       cwd=SRC_ROOT_DIR,
   )
   try:
     return xml.etree.ElementTree.fromstring(queryview_xml)
   except xml.etree.ElementTree.ParseError as err:
     sys.exit(f"""Could not parse XML:
 {queryview_xml}
 ParseError: {err}""")


 def get_queryview_module_info(modules, target_product):
   """Returns the list of transitive dependencies of input module as built by queryview."""
   _build_with_soong("queryview", target_product)

   queryview_xml = subprocess.check_output(
       [
           "build/bazel/bin/bazel",
           "query",
           "--config=ci",
           "--config=queryview",
           "--output=xml",
           # union of queries to get the deps of all Soong modules with the give names
           " + ".join(
               f'deps(attr("soong_module_name", "^{m}$", //...))'
               for m in modules
           ),
       ],
       cwd=SRC_ROOT_DIR,
   )
   try:
     return xml.etree.ElementTree.fromstring(queryview_xml)
   except xml.etree.ElementTree.ParseError as err:
     sys.exit(f"""Could not parse XML:
 {queryview_xml}
 ParseError: {err}""")


 def get_json_module_info(target_product=None):
   """Returns the list of transitive dependencies of input module as provided by Soong's json module graph."""
   _build_with_soong("json-module-graph", target_product)
   try:
     with open(os.path.join(SRC_ROOT_DIR, "out/soong/module-graph.json")) as f:
       return json.load(f)
   except json.JSONDecodeError as err:
     sys.exit(f"""Could not decode json:
 out/soong/module-graph.json
 JSONDecodeError: {err}""")


 def ignore_json_module(json_module, ignore_by_name):
   # windows is not a priority currently
   if is_windows_variation(json_module):
     return True
   if ignore_kind(json_module["Type"]):
     return True
   if json_module["Name"] in ignore_by_name:
     return True
   # for filegroups with a name the same as the source, we are not migrating the
   # filegroup and instead just rely on the filename being exported
   if json_module["Type"] == "filegroup":
     set_properties = get_properties(json_module)
     srcs = set_properties.get("Srcs", [])
     if len(srcs) == 1:
       return json_module["Name"] in srcs
   return False


 def visit_json_module_graph_post_order(
     module_graph, ignore_by_name, ignore_java_auto_deps, filter_predicate, visit
 ):
   # The set of ignored modules. These modules (and their dependencies) are not shown
   # in the graph or report.
   ignored = set()

   # name to all module variants
   module_graph_map = {}
   root_module_keys = []
   name_to_keys = collections.defaultdict(list)

   # Do a single pass to find all top-level modules to be ignored
   for module in module_graph:
     name = module["Name"]
     key = _ModuleKey(name, module["Variations"])
     if ignore_json_module(module, ignore_by_name):
       ignored.add(key)
       continue
     name_to_keys[name].append(key)
     module_graph_map[key] = module
     if filter_predicate(module):
       root_module_keys.append(key)

   visited = set()

   def json_module_graph_post_traversal(module_key):
     if module_key in ignored or module_key in visited:
       return
     visited.add(module_key)

     deps = set()
     module = module_graph_map[module_key]
     created_by = module["CreatedBy"]

     extra_deps = []
     if created_by:
       extra_deps.append(created_by)

     set_properties = get_properties(module)
     for prop in set_properties.keys():
       for req in _REQUIRED_PROPERTIES:
         if prop.endswith(req):
           modules = set_properties.get(prop, [])
           extra_deps.extend(modules)

     for m in extra_deps:
       for key in name_to_keys.get(m, []):
         if key in ignored:
           continue
         # treat created by as a dep so it appears as a blocker, otherwise the
         # module will be disconnected from the traversal graph despite having a
         # direct relationship to a module and must addressed in the migration
         deps.add(m)
         json_module_graph_post_traversal(key)

     # collect all variants and dependencies from those variants
     # we want to visit all deps before other variants
     all_variants = {}
     all_deps = []
     for k in name_to_keys[module["Name"]]:
       visited.add(k)
       m = module_graph_map[k]
       all_variants[k] = m
       all_deps.extend(m["Deps"])

     deps_visited = set()
     for dep in all_deps:
       dep_name = dep["Name"]
       dep_key = _ModuleKey(dep_name, dep["Variations"])
       # only check if we need to ignore or visit each dep once but it might
       # appear multiple times due to different variants
       if dep_key in deps_visited:
         continue
       deps_visited.add(dep_key)

       if ignore_json_dep(dep, module["Name"], ignored, ignore_java_auto_deps):
         continue

       deps.add(dep_name)
       json_module_graph_post_traversal(dep_key)

     for k, m in all_variants.items():
       visit(m, deps)

   for module_key in root_module_keys:
     json_module_graph_post_traversal(module_key)


 QueryviewModule = collections.namedtuple(
     "QueryviewModule",
     [
         "name",
         "kind",
         "variant",
         "dirname",
         "deps",
         "srcs",
     ],
 )


 def _bazel_target_to_dir(full_target):
   dirname, _ = full_target.split(":")
   return dirname[len("//") :]  # discard prefix


 def _get_queryview_module(name_with_variant, module, kind):
   name = None
   variant = ""
   deps = []
   srcs = []
   for attr in module:
     attr_name = attr.attrib["name"]
     if attr.tag == "rule-input":
       deps.append(attr_name)
     elif attr_name == "soong_module_name":
       name = attr.attrib["value"]
     elif attr_name == "soong_module_variant":
       variant = attr.attrib["value"]
     elif attr_name == "soong_module_type" and kind == "generic_soong_module":
       kind = attr.attrib["value"]
     elif attr_name == "srcs":
       for item in attr:
         srcs.append(item.attrib["value"])

   return QueryviewModule(
       name=name,
       kind=kind,
       variant=variant,
       dirname=_bazel_target_to_dir(name_with_variant),
       deps=deps,
       srcs=srcs,
   )


 def _ignore_queryview_module(module, ignore_by_name):
   if module.name in ignore_by_name:
     return True
   if ignore_kind(module.kind, queryview=True):
     return True
   # special handling for filegroup srcs, if a source has the same name as
   # the filegroup module, we don't convert it
   if module.kind == "filegroup" and module.name in module.srcs:
     return True
   return module.variant.startswith("windows")


 def visit_queryview_xml_module_graph_post_order(
     module_graph, ignored_by_name, filter_predicate, visit
 ):
   # The set of ignored modules. These modules (and their dependencies) are
   # not shown in the graph or report.
   ignored = set()

   # queryview embeds variant in long name, keep a map of the name with vaiarnt
   # to just name
   name_with_variant_to_name = dict()

   module_graph_map = dict()
   to_visit = []

   for module in module_graph:
     ignore = False
     if module.tag != "rule":
       continue
     kind = module.attrib["class"]
     name_with_variant = module.attrib["name"]

     qv_module = _get_queryview_module(name_with_variant, module, kind)

     if _ignore_queryview_module(qv_module, ignored_by_name):
       ignored.add(name_with_variant)
       continue

     if filter_predicate(qv_module):
       to_visit.append(name_with_variant)

     name_with_variant_to_name.setdefault(name_with_variant, qv_module.name)
     module_graph_map[name_with_variant] = qv_module

   visited = set()

   def queryview_module_graph_post_traversal(name_with_variant):
     module = module_graph_map[name_with_variant]
     if name_with_variant in ignored or name_with_variant in visited:
       return
     visited.add(name_with_variant)

     name = name_with_variant_to_name[name_with_variant]

     deps = set()
     for dep_name_with_variant in module.deps:
       if dep_name_with_variant in ignored:
         continue
       dep_name = name_with_variant_to_name[dep_name_with_variant]
       if dep_name == "prebuilt_" + name:
         continue
       if dep_name_with_variant not in visited:
         queryview_module_graph_post_traversal(dep_name_with_variant)

       if name != dep_name:
         deps.add(dep_name)

     visit(module, deps)

   for name_with_variant in to_visit:
     queryview_module_graph_post_traversal(name_with_variant)


 def get_bp2build_converted_modules(target_product) -> Dict[str, Set[str]]:
   """Returns the list of modules that bp2build can currently convert."""
   _build_with_soong("bp2build", target_product)
   # Parse the list of converted module names from bp2build
   with open(
       os.path.join(
           SRC_ROOT_DIR,
           "out/soong/soong_injection/metrics/converted_modules.json",
       ),
       "r",
   ) as f:
     converted_mods = json.loads(f.read())
     ret = collections.defaultdict(set)
     for m in converted_mods:
       ret[m["name"]].add(m["type"])
   return ret


 def get_bp2build_metrics(bp2build_metrics_location):
   """Returns the bp2build metrics"""
   bp2build_metrics = Bp2BuildMetrics()
   with open(
       os.path.join(bp2build_metrics_location, "bp2build_metrics.pb"), "rb"
   ) as f:
     bp2build_metrics.ParseFromString(f.read())
     f.close()
   return bp2build_metrics


 def get_json_module_type_info(module_type, target_product=None):
   """Returns the combined transitive dependency closures of all modules of module_type."""
   if target_product is None:
     target_product = TargetProduct(banchan_mode=False)
   _build_with_soong("json-module-graph", target_product)
   # Run query.sh on the module graph for the top level module type
   result = subprocess.check_output(
       [
           "build/bazel/json_module_graph/query.sh",
           "fullTransitiveModuleTypeDeps",
           "out/soong/module-graph.json",
           module_type,
       ],
       cwd=SRC_ROOT_DIR,
   )
   return json.loads(result)


 def is_windows_variation(module):
   """Returns True if input module's variant is Windows.

   Args:
     module: an entry parsed from Soong's json-module-graph
   """
   dep_variations = module.get("Variations")
   dep_variation_os = ""
   if dep_variations != None:
     for v in dep_variations:
       if v["Mutator"] == "os":
         dep_variation_os = v["Variation"]
   return dep_variation_os == "windows"


 def ignore_kind(kind, queryview=False):
   if queryview and kind in _QUERYVIEW_IGNORE_KINDS:
     return True
   return kind in IGNORED_KINDS or "defaults" in kind


 def is_prebuilt_to_source_dep(dep):
   # Soong always adds a dependency from a source module to its corresponding
   # prebuilt module, if it exists.
   # https://cs.android.com/android/platform/superproject/+/master:build/soong/android/prebuilt.go;l=395-396;drc=5d6fa4d8571d01a6e5a63a8b7aa15e61f45737a9
   # This makes it appear that the prebuilt is a transitive dependency regardless
   # of whether it is actually necessary. Skip these to keep the graph to modules
   # used to build.
   return dep["Tag"] == "android.prebuiltDependencyTag {BaseDependencyTag:{}}"


 def _is_toolchain_dep(dep):
   return dep["Tag"] in _TOOLCHAIN_DEP_TYPES


 def _is_java_auto_dep(dep):
   # Soong adds a number of dependencies automatically for Java deps, making it
   # difficult to understand the actual dependencies, remove the
   # non-user-specified deps
   tag = dep["Tag"]
   if not tag:
     return False

   if tag.startswith("java.dependencyTag") and (
       "name:system modules" in tag or "name:bootclasspath" in tag
   ):
     name = dep["Name"]
     # only remove automatically added bootclasspath/system modules
     return (
         name
         in frozenset([
             "core-lambda-stubs",
             "core-module-lib-stubs-system-modules",
             "core-public-stubs-system-modules",
             "core-system-server-stubs-system-modules",
             "core-system-stubs-system-modules",
             "core-test-stubs-system-modules",
             "core.current.stubs",
             "legacy-core-platform-api-stubs-system-modules",
             "legacy.core.platform.api.stubs",
             "stable-core-platform-api-stubs-system-modules",
             "stable.core.platform.api.stubs",
         ])
         or (name.startswith("android_") and name.endswith("_stubs_current"))
         or (name.startswith("sdk_") and name.endswith("_system_modules"))
     )
   return (
       (
           tag.startswith("java.dependencyTag")
           and (
               "name:proguard-raise" in tag
               or "name:framework-res" in tag
               or "name:sdklib" in tag
               or "name:java9lib" in tag
           )
           or (
               tag.startswith("java.usesLibraryDependencyTag")
               or tag.startswith("java.hiddenAPIStubsDependencyTag")
           )
       )
       or (
           tag.startswith("android.sdkMemberDependencyTag")
           or tag.startswith("java.scopeDependencyTag")
       )
       or tag.startswith("dexpreopt.dex2oatDependencyTag")
   )


 def ignore_json_dep(dep, module_name, ignored_keys, ignore_java_auto_deps):
   """Whether to ignore a json dependency based on heuristics.

   Args:
     dep: dependency struct from an entry in Soogn's json-module-graph
     module_name: name of the module this is a dependency of
     ignored_names: a set of _ModuleKey to ignore
   """
   if is_prebuilt_to_source_dep(dep):
     return True
   if _is_toolchain_dep(dep):
     return True
   elif dep["Name"] == "py3-stdlib":
     return True
   if ignore_java_auto_deps and _is_java_auto_dep(dep):
     return True
   name = dep["Name"]
   return (
       _ModuleKey(name, dep["Variations"]) in ignored_keys or name == module_name
   )
	#!/usr/bin/env python3
	#
	# Copyright (C) 2022 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.
	"""Utility functions to produce module or module type dependency graphs using json-module-graph or queryview."""

	import collections
	import dataclasses
	import json
	import os
	import os.path
	import subprocess
	import sys
	from typing import Dict, Optional, Set
	import xml.etree.ElementTree
	from bp2build_metrics_proto.bp2build_metrics_pb2 import Bp2BuildMetrics


	@dataclasses.dataclass(frozen=True, order=True)
	class TargetProduct:
	product: Optional[str] = None
	banchan_mode: bool = False


	@dataclasses.dataclass(frozen=True, order=True)
	class _ModuleKey:
	"""_ModuleKey uniquely identifies a module by name nad variations."""

	name: str
	variations: list

	def __str__(self):
	return f"{self.name}, {self.variations}"

	def __hash__(self):
	return (self.name + str(self.variations)).__hash__()


	# This list of module types are omitted from the report and graph
	# for brevity and simplicity. Presence in this list doesn't mean
	# that they shouldn't be converted, but that they are not that useful
	# to be recorded in the graph or report currently.
	IGNORED_KINDS = set([
	"cc_defaults",
	"cpython3_python_stdlib",
	"hidl_package_root", # not being converted, contents converted as part of hidl_interface
	"java_defaults",
	"license",
	"license_kind",
	])

	# queryview doesn't have information on the type of deps, so we explicitly skip
	# prebuilt types
	_QUERYVIEW_IGNORE_KINDS = set([
	"android_app_import",
	"android_library_import",
	"cc_prebuilt_library",
	"cc_prebuilt_library_headers",
	"cc_prebuilt_library_shared",
	"cc_prebuilt_library_static",
	"cc_prebuilt_library_static",
	"cc_prebuilt_object",
	"java_import",
	"java_import_host",
	"java_sdk_library_import",
	"cpython3_python_stdlib",
	"cpython2_python_stdlib",
	])


	# Soong adds some dependencies that are handled by Bazel as part of the
	# toolchain
	_TOOLCHAIN_DEP_TYPES = frozenset([
	"python.dependencyTag {BaseDependencyTag:{} name:hostLauncher}",
	"python.dependencyTag {BaseDependencyTag:{} name:hostLauncherSharedLib}",
	"python.dependencyTag {BaseDependencyTag:{} name:hostStdLib}",
	"python.dependencyTag {BaseDependencyTag:{} name:launcher}",
	(
	"python.installDependencyTag {BaseDependencyTag:{}"
	" InstallAlwaysNeededDependencyTag:{} name:launcherSharedLib}"
	),
	])

	def get_src_root_dir() -> str:
	# Search up the directory tree until we find soong_ui.bash as a regular file, not a symlink.
	# This is so that we find the real source tree root, and not the bazel execroot which symlimks in
	# soong_ui.bash.
	def soong_ui(path):
	return os.path.join(path, 'build/soong/soong_ui.bash')

	path = '.'
	while not os.path.isfile(soong_ui(path)) or os.path.islink(soong_ui(path)):
	if os.path.abspath(path) == '/':
	sys.exit('Could not find android source tree root.')
	path = os.path.join(path, '..')
	return os.path.abspath(path)

	SRC_ROOT_DIR = get_src_root_dir()

	LUNCH_ENV = {
	# Use aosp_arm as the canonical target product.
	"TARGET_PRODUCT": "aosp_arm",
	"TARGET_BUILD_VARIANT": "userdebug",
	}

	BANCHAN_ENV = {
	# Use module_arm64 as the canonical banchan target product.
	"TARGET_PRODUCT": "module_arm64",
	"TARGET_BUILD_VARIANT": "eng",
	# just needs to be non-empty, not the specific module for Soong
	# analysis purposes
	"TARGET_BUILD_APPS": "all",
	}

	_REQUIRED_PROPERTIES = [
	"Required",
	"Host_required",
	"Target_required",
	]


	def _build_with_soong(target, target_product):
	env = BANCHAN_ENV if target_product.banchan_mode else LUNCH_ENV
	if target_product.product:
	env["TARGET_PRODUCT"] = target_product.product

	subprocess.check_output(
	[
	"build/soong/soong_ui.bash",
	"--make-mode",
	"--skip-soong-tests",
	target,
	],
	cwd=SRC_ROOT_DIR,
	env=env,
	)


	def get_properties(json_module):
	set_properties = {}
	if "Module" not in json_module:
	return set_properties
	if "Android" not in json_module["Module"]:
	return set_properties
	if "SetProperties" not in json_module["Module"]["Android"]:
	return set_properties
	if json_module["Module"]["Android"]["SetProperties"] is None:
	return set_properties

	for prop in json_module["Module"]["Android"]["SetProperties"]:
	if prop["Values"]:
	value = prop["Values"]
	else:
	value = prop["Value"]
	set_properties[prop["Name"]] = value

	return set_properties


	def get_property_names(json_module):
	return get_properties(json_module).keys()


	def get_queryview_module_info_by_type(types, target_product):
	"""Returns the list of transitive dependencies of input module as built by queryview."""
	_build_with_soong("queryview", target_product)

	queryview_xml = subprocess.check_output(
	[
	"build/bazel/bin/bazel",
	"query",
	"--config=ci",
	"--config=queryview",
	"--output=xml",
	# union of queries to get the deps of all Soong modules with the give names
	" + ".join(
	f'deps(attr("soong_module_type", "^{t}$", //...))' for t in types
	),
	],
	cwd=SRC_ROOT_DIR,
	)
	try:
	return xml.etree.ElementTree.fromstring(queryview_xml)
	except xml.etree.ElementTree.ParseError as err:
	sys.exit(f"""Could not parse XML:
	{queryview_xml}
	ParseError: {err}""")


	def get_queryview_module_info(modules, target_product):
	"""Returns the list of transitive dependencies of input module as built by queryview."""
	_build_with_soong("queryview", target_product)

	queryview_xml = subprocess.check_output(
	[
	"build/bazel/bin/bazel",
	"query",
	"--config=ci",
	"--config=queryview",
	"--output=xml",
	# union of queries to get the deps of all Soong modules with the give names
	" + ".join(
	f'deps(attr("soong_module_name", "^{m}$", //...))'
	for m in modules
	),
	],
	cwd=SRC_ROOT_DIR,
	)
	try:
	return xml.etree.ElementTree.fromstring(queryview_xml)
	except xml.etree.ElementTree.ParseError as err:
	sys.exit(f"""Could not parse XML:
	{queryview_xml}
	ParseError: {err}""")


	def get_json_module_info(target_product=None):
	"""Returns the list of transitive dependencies of input module as provided by Soong's json module graph."""
	_build_with_soong("json-module-graph", target_product)
	try:
	with open(os.path.join(SRC_ROOT_DIR, "out/soong/module-graph.json")) as f:
	return json.load(f)
	except json.JSONDecodeError as err:
	sys.exit(f"""Could not decode json:
	out/soong/module-graph.json
	JSONDecodeError: {err}""")


	def ignore_json_module(json_module, ignore_by_name):
	# windows is not a priority currently
	if is_windows_variation(json_module):
	return True
	if ignore_kind(json_module["Type"]):
	return True
	if json_module["Name"] in ignore_by_name:
	return True
	# for filegroups with a name the same as the source, we are not migrating the
	# filegroup and instead just rely on the filename being exported
	if json_module["Type"] == "filegroup":
	set_properties = get_properties(json_module)
	srcs = set_properties.get("Srcs", [])
	if len(srcs) == 1:
	return json_module["Name"] in srcs
	return False


	def visit_json_module_graph_post_order(
	module_graph, ignore_by_name, ignore_java_auto_deps, filter_predicate, visit
	):
	# The set of ignored modules. These modules (and their dependencies) are not shown
	# in the graph or report.
	ignored = set()

	# name to all module variants
	module_graph_map = {}
	root_module_keys = []
	name_to_keys = collections.defaultdict(list)

	# Do a single pass to find all top-level modules to be ignored
	for module in module_graph:
	name = module["Name"]
	key = _ModuleKey(name, module["Variations"])
	if ignore_json_module(module, ignore_by_name):
	ignored.add(key)
	continue
	name_to_keys[name].append(key)
	module_graph_map[key] = module
	if filter_predicate(module):
	root_module_keys.append(key)

	visited = set()

	def json_module_graph_post_traversal(module_key):
	if module_key in ignored or module_key in visited:
	return
	visited.add(module_key)

	deps = set()
	module = module_graph_map[module_key]
	created_by = module["CreatedBy"]

	extra_deps = []
	if created_by:
	extra_deps.append(created_by)

	set_properties = get_properties(module)
	for prop in set_properties.keys():
	for req in _REQUIRED_PROPERTIES:
	if prop.endswith(req):
	modules = set_properties.get(prop, [])
	extra_deps.extend(modules)

	for m in extra_deps:
	for key in name_to_keys.get(m, []):
	if key in ignored:
	continue
	# treat created by as a dep so it appears as a blocker, otherwise the
	# module will be disconnected from the traversal graph despite having a
	# direct relationship to a module and must addressed in the migration
	deps.add(m)
	json_module_graph_post_traversal(key)

	# collect all variants and dependencies from those variants
	# we want to visit all deps before other variants
	all_variants = {}
	all_deps = []
	for k in name_to_keys[module["Name"]]:
	visited.add(k)
	m = module_graph_map[k]
	all_variants[k] = m
	all_deps.extend(m["Deps"])

	deps_visited = set()
	for dep in all_deps:
	dep_name = dep["Name"]
	dep_key = _ModuleKey(dep_name, dep["Variations"])
	# only check if we need to ignore or visit each dep once but it might
	# appear multiple times due to different variants
	if dep_key in deps_visited:
	continue
	deps_visited.add(dep_key)

	if ignore_json_dep(dep, module["Name"], ignored, ignore_java_auto_deps):
	continue

	deps.add(dep_name)
	json_module_graph_post_traversal(dep_key)

	for k, m in all_variants.items():
	visit(m, deps)

	for module_key in root_module_keys:
	json_module_graph_post_traversal(module_key)


	QueryviewModule = collections.namedtuple(
	"QueryviewModule",
	[
	"name",
	"kind",
	"variant",
	"dirname",
	"deps",
	"srcs",
	],
	)


	def _bazel_target_to_dir(full_target):
	dirname, _ = full_target.split(":")
	return dirname[len("//") :] # discard prefix


	def _get_queryview_module(name_with_variant, module, kind):
	name = None
	variant = ""
	deps = []
	srcs = []
	for attr in module:
	attr_name = attr.attrib["name"]
	if attr.tag == "rule-input":
	deps.append(attr_name)
	elif attr_name == "soong_module_name":
	name = attr.attrib["value"]
	elif attr_name == "soong_module_variant":
	variant = attr.attrib["value"]
	elif attr_name == "soong_module_type" and kind == "generic_soong_module":
	kind = attr.attrib["value"]
	elif attr_name == "srcs":
	for item in attr:
	srcs.append(item.attrib["value"])

	return QueryviewModule(
	name=name,
	kind=kind,
	variant=variant,
	dirname=_bazel_target_to_dir(name_with_variant),
	deps=deps,
	srcs=srcs,
	)


	def _ignore_queryview_module(module, ignore_by_name):
	if module.name in ignore_by_name:
	return True
	if ignore_kind(module.kind, queryview=True):
	return True
	# special handling for filegroup srcs, if a source has the same name as
	# the filegroup module, we don't convert it
	if module.kind == "filegroup" and module.name in module.srcs:
	return True
	return module.variant.startswith("windows")


	def visit_queryview_xml_module_graph_post_order(
	module_graph, ignored_by_name, filter_predicate, visit
	):
	# The set of ignored modules. These modules (and their dependencies) are
	# not shown in the graph or report.
	ignored = set()

	# queryview embeds variant in long name, keep a map of the name with vaiarnt
	# to just name
	name_with_variant_to_name = dict()

	module_graph_map = dict()
	to_visit = []

	for module in module_graph:
	ignore = False
	if module.tag != "rule":
	continue
	kind = module.attrib["class"]
	name_with_variant = module.attrib["name"]

	qv_module = _get_queryview_module(name_with_variant, module, kind)

	if _ignore_queryview_module(qv_module, ignored_by_name):
	ignored.add(name_with_variant)
	continue

	if filter_predicate(qv_module):
	to_visit.append(name_with_variant)

	name_with_variant_to_name.setdefault(name_with_variant, qv_module.name)
	module_graph_map[name_with_variant] = qv_module

	visited = set()

	def queryview_module_graph_post_traversal(name_with_variant):
	module = module_graph_map[name_with_variant]
	if name_with_variant in ignored or name_with_variant in visited:
	return
	visited.add(name_with_variant)

	name = name_with_variant_to_name[name_with_variant]

	deps = set()
	for dep_name_with_variant in module.deps:
	if dep_name_with_variant in ignored:
	continue
	dep_name = name_with_variant_to_name[dep_name_with_variant]
	if dep_name == "prebuilt_" + name:
	continue
	if dep_name_with_variant not in visited:
	queryview_module_graph_post_traversal(dep_name_with_variant)

	if name != dep_name:
	deps.add(dep_name)

	visit(module, deps)

	for name_with_variant in to_visit:
	queryview_module_graph_post_traversal(name_with_variant)


	def get_bp2build_converted_modules(target_product) -> Dict[str, Set[str]]:
	"""Returns the list of modules that bp2build can currently convert."""
	_build_with_soong("bp2build", target_product)
	# Parse the list of converted module names from bp2build
	with open(
	os.path.join(
	SRC_ROOT_DIR,
	"out/soong/soong_injection/metrics/converted_modules.json",
	),
	"r",
	) as f:
	converted_mods = json.loads(f.read())
	ret = collections.defaultdict(set)
	for m in converted_mods:
	ret[m["name"]].add(m["type"])
	return ret


	def get_bp2build_metrics(bp2build_metrics_location):
	"""Returns the bp2build metrics"""
	bp2build_metrics = Bp2BuildMetrics()
	with open(
	os.path.join(bp2build_metrics_location, "bp2build_metrics.pb"), "rb"
	) as f:
	bp2build_metrics.ParseFromString(f.read())
	f.close()
	return bp2build_metrics


	def get_json_module_type_info(module_type, target_product=None):
	"""Returns the combined transitive dependency closures of all modules of module_type."""
	if target_product is None:
	target_product = TargetProduct(banchan_mode=False)
	_build_with_soong("json-module-graph", target_product)
	# Run query.sh on the module graph for the top level module type
	result = subprocess.check_output(
	[
	"build/bazel/json_module_graph/query.sh",
	"fullTransitiveModuleTypeDeps",
	"out/soong/module-graph.json",
	module_type,
	],
	cwd=SRC_ROOT_DIR,
	)
	return json.loads(result)


	def is_windows_variation(module):
	"""Returns True if input module's variant is Windows.

	Args:
	module: an entry parsed from Soong's json-module-graph
	"""
	dep_variations = module.get("Variations")
	dep_variation_os = ""
	if dep_variations != None:
	for v in dep_variations:
	if v["Mutator"] == "os":
	dep_variation_os = v["Variation"]
	return dep_variation_os == "windows"


	def ignore_kind(kind, queryview=False):
	if queryview and kind in _QUERYVIEW_IGNORE_KINDS:
	return True
	return kind in IGNORED_KINDS or "defaults" in kind


	def is_prebuilt_to_source_dep(dep):
	# Soong always adds a dependency from a source module to its corresponding
	# prebuilt module, if it exists.
	# https://cs.android.com/android/platform/superproject/+/master:build/soong/android/prebuilt.go;l=395-396;drc=5d6fa4d8571d01a6e5a63a8b7aa15e61f45737a9
	# This makes it appear that the prebuilt is a transitive dependency regardless
	# of whether it is actually necessary. Skip these to keep the graph to modules
	# used to build.
	return dep["Tag"] == "android.prebuiltDependencyTag {BaseDependencyTag:{}}"


	def _is_toolchain_dep(dep):
	return dep["Tag"] in _TOOLCHAIN_DEP_TYPES


	def _is_java_auto_dep(dep):
	# Soong adds a number of dependencies automatically for Java deps, making it
	# difficult to understand the actual dependencies, remove the
	# non-user-specified deps
	tag = dep["Tag"]
	if not tag:
	return False

	if tag.startswith("java.dependencyTag") and (
	"name:system modules" in tag or "name:bootclasspath" in tag
	):
	name = dep["Name"]
	# only remove automatically added bootclasspath/system modules
	return (
	name
	in frozenset([
	"core-lambda-stubs",
	"core-module-lib-stubs-system-modules",
	"core-public-stubs-system-modules",
	"core-system-server-stubs-system-modules",
	"core-system-stubs-system-modules",
	"core-test-stubs-system-modules",
	"core.current.stubs",
	"legacy-core-platform-api-stubs-system-modules",
	"legacy.core.platform.api.stubs",
	"stable-core-platform-api-stubs-system-modules",
	"stable.core.platform.api.stubs",
	])
	or (name.startswith("android_") and name.endswith("_stubs_current"))
	or (name.startswith("sdk_") and name.endswith("_system_modules"))
	)
	return (
	(
	tag.startswith("java.dependencyTag")
	and (
	"name:proguard-raise" in tag
	or "name:framework-res" in tag
	or "name:sdklib" in tag
	or "name:java9lib" in tag
	)
	or (
	tag.startswith("java.usesLibraryDependencyTag")
	or tag.startswith("java.hiddenAPIStubsDependencyTag")
	)
	)
	or (
	tag.startswith("android.sdkMemberDependencyTag")
	or tag.startswith("java.scopeDependencyTag")
	)
	or tag.startswith("dexpreopt.dex2oatDependencyTag")
	)


	def ignore_json_dep(dep, module_name, ignored_keys, ignore_java_auto_deps):
	"""Whether to ignore a json dependency based on heuristics.

	Args:
	dep: dependency struct from an entry in Soogn's json-module-graph
	module_name: name of the module this is a dependency of
	ignored_names: a set of _ModuleKey to ignore
	"""
	if is_prebuilt_to_source_dep(dep):
	return True
	if _is_toolchain_dep(dep):
	return True
	elif dep["Name"] == "py3-stdlib":
	return True
	if ignore_java_auto_deps and _is_java_auto_dep(dep):
	return True
	name = dep["Name"]
	return (
	_ModuleKey(name, dep["Variations"]) in ignored_keys or name == module_name
	)