scripts/hiddenapi/signature_trie.py - LeafOS-Project/android_build_soong - Gitiles

 #!/usr/bin/env python
 #
 # 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.
 """Verify that one set of hidden API flags is a subset of another."""
 import dataclasses
 import typing

 from itertools import chain


 @dataclasses.dataclass()
 class Node:
     """A node in the signature trie."""

     # The type of the node.
     #
     # Leaf nodes are of type "member".
     # Interior nodes can be either "package", or "class".
     type: str

     # The selector of the node.
     #
     # That is a string that can be used to select the node, e.g. in a pattern
     # that is passed to InteriorNode.get_matching_rows().
     selector: str

     def values(self, selector):
         """Get the values from a set of selected nodes.

         :param selector: a function that can be applied to a key in the nodes
             attribute to determine whether to return its values.

         :return: A list of iterables of all the values associated with
             this node and its children.
         """
         values = []
         self.append_values(values, selector)
         return values

     def append_values(self, values, selector):
         """Append the values associated with this node and its children.

         For each item (key, child) in nodes the child node's values are returned
         if and only if the selector returns True when called on its key. A child
         node's values are all the values associated with it and all its
         descendant nodes.

         :param selector: a function that can be applied to a key in the nodes
         attribute to determine whether to return its values.
         :param values: a list of a iterables of values.
         """
         raise NotImplementedError("Please Implement this method")

     def child_nodes(self):
         """Get an iterable of the child nodes of this node."""
         raise NotImplementedError("Please Implement this method")


 # pylint: disable=line-too-long
 @dataclasses.dataclass()
 class InteriorNode(Node):
     """An interior node in a trie.

     Each interior node has a dict that maps from an element of a signature to
     either another interior node or a leaf. Each interior node represents either
     a package, class or nested class. Class members are represented by a Leaf.

     Associating the set of flags [public-api] with the signature
     "Ljava/lang/Object;->String()Ljava/lang/String;" will cause the following
     nodes to be created:
     Node()
     ^- package:java -> Node()
        ^- package:lang -> Node()
            ^- class:Object -> Node()
               ^- member:String()Ljava/lang/String; -> Leaf([public-api])

     Associating the set of flags [blocked,core-platform-api] with the signature
     "Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;"
     will cause the following nodes to be created:
     Node()
     ^- package:java -> Node()
        ^- package:lang -> Node()
            ^- class:Character -> Node()
               ^- class:UnicodeScript -> Node()
                  ^- member:of(I)Ljava/lang/Character$UnicodeScript;
                     -> Leaf([blocked,core-platform-api])
     """

     # pylint: enable=line-too-long

     # A dict from an element of the signature to the Node/Leaf containing the
     # next element/value.
     nodes: typing.Dict[str, Node] = dataclasses.field(default_factory=dict)

     # pylint: disable=line-too-long
     @staticmethod
     def signature_to_elements(signature):
         """Split a signature or a prefix into a number of elements:

         1. The packages (excluding the leading L preceding the first package).
         2. The class names, from outermost to innermost.
         3. The member signature.
         e.g.
         Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;
         will be broken down into these elements:
         1. package:java
         2. package:lang
         3. class:Character
         4. class:UnicodeScript
         5. member:of(I)Ljava/lang/Character$UnicodeScript;
         """
         # Remove the leading L.
         #  - java/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;
         text = signature.removeprefix("L")
         # Split the signature between qualified class name and the class member
         # signature.
         #  0 - java/lang/Character$UnicodeScript
         #  1 - of(I)Ljava/lang/Character$UnicodeScript;
         parts = text.split(";->")
         # If there is no member then this will be an empty list.
         member = parts[1:]
         # Split the qualified class name into packages, and class name.
         #  0 - java
         #  1 - lang
         #  2 - Character$UnicodeScript
         elements = parts[0].split("/")
         last_element = elements[-1]
         wildcard = []
         classes = []
         if "*" in last_element:
             if last_element not in ("*", "**"):
                 raise Exception(f"Invalid signature '{signature}': invalid "
                                 f"wildcard '{last_element}'")
             packages = elements[0:-1]
             # Cannot specify a wildcard and target a specific member
             if member:
                 raise Exception(f"Invalid signature '{signature}': contains "
                                 f"wildcard '{last_element}' and "
                                 f"member signature '{member[0]}'")
             wildcard = [last_element]
         else:
             packages = elements[0:-1]
             # Split the class name into outer / inner classes
             #  0 - Character
             #  1 - UnicodeScript
             classes = last_element.removesuffix(";").split("$")

         # Assemble the parts into a single list, adding prefixes to identify
         # the different parts. If a wildcard is provided then it looks something
         # like this:
         #  0 - package:java
         #  1 - package:lang
         #  2 - *
         #
         # Otherwise, it looks something like this:
         #  0 - package:java
         #  1 - package:lang
         #  2 - class:Character
         #  3 - class:UnicodeScript
         #  4 - member:of(I)Ljava/lang/Character$UnicodeScript;
         return list(
             chain([("package", x) for x in packages],
                   [("class", x) for x in classes],
                   [("member", x) for x in member],
                   [("wildcard", x) for x in wildcard]))

     # pylint: enable=line-too-long

     @staticmethod
     def split_element(element):
         element_type, element_value = element
         return element_type, element_value

     @staticmethod
     def element_type(element):
         element_type, _ = InteriorNode.split_element(element)
         return element_type

     @staticmethod
     def elements_to_selector(elements):
         """Compute a selector for a set of elements.

         A selector uniquely identifies a specific Node in the trie. It is
         essentially a prefix of a signature (without the leading L).

         e.g. a trie containing "Ljava/lang/Object;->String()Ljava/lang/String;"
         would contain nodes with the following selectors:
         * "java"
         * "java/lang"
         * "java/lang/Object"
         * "java/lang/Object;->String()Ljava/lang/String;"
         """
         signature = ""
         preceding_type = ""
         for element in elements:
             element_type, element_value = InteriorNode.split_element(element)
             separator = ""
             if element_type == "package":
                 separator = "/"
             elif element_type == "class":
                 if preceding_type == "class":
                     separator = "$"
                 else:
                     separator = "/"
             elif element_type == "wildcard":
                 separator = "/"
             elif element_type == "member":
                 separator += ";->"

             if signature:
                 signature += separator

             signature += element_value

             preceding_type = element_type

         return signature

     def add(self, signature, value, only_if_matches=False):
         """Associate the value with the specific signature.

         :param signature: the member signature
         :param value: the value to associated with the signature
         :param only_if_matches: True if the value is added only if the signature
              matches at least one of the existing top level packages.
         :return: n/a
         """
         # Split the signature into elements.
         elements = self.signature_to_elements(signature)
         # Find the Node associated with the deepest class.
         node = self
         for index, element in enumerate(elements[:-1]):
             if element in node.nodes:
                 node = node.nodes[element]
             elif only_if_matches and index == 0:
                 return
             else:
                 selector = self.elements_to_selector(elements[0:index + 1])
                 next_node = InteriorNode(
                     type=InteriorNode.element_type(element), selector=selector)
                 node.nodes[element] = next_node
                 node = next_node
         # Add a Leaf containing the value and associate it with the member
         # signature within the class.
         last_element = elements[-1]
         last_element_type = self.element_type(last_element)
         if last_element_type != "member":
             raise Exception(
                 f"Invalid signature: {signature}, does not identify a "
                 "specific member")
         if last_element in node.nodes:
             raise Exception(f"Duplicate signature: {signature}")
         leaf = Leaf(
             type=last_element_type,
             selector=signature,
             value=value,
         )
         node.nodes[last_element] = leaf

     def get_matching_rows(self, pattern):
         """Get the values (plural) associated with the pattern.

         e.g. If the pattern is a full signature then this will return a list
         containing the value associated with that signature.

         If the pattern is a class then this will return a list containing the
         values associated with all members of that class.

         If the pattern ends with "*" then the preceding part is treated as a
         package and this will return a list containing the values associated
         with all the members of all the classes in that package.

         If the pattern ends with "**" then the preceding part is treated
         as a package and this will return a list containing the values
         associated with all the members of all the classes in that package and
         all sub-packages.

         :param pattern: the pattern which could be a complete signature or a
         class, or package wildcard.
         :return: an iterable containing all the values associated with the
         pattern.
         """
         elements = self.signature_to_elements(pattern)
         node = self

         # Include all values from this node and all its children.
         selector = lambda x: True

         last_element = elements[-1]
         last_element_type, last_element_value = self.split_element(last_element)
         if last_element_type == "wildcard":
             elements = elements[:-1]
             if last_element_value == "*":
                 # Do not include values from sub-packages.
                 selector = lambda x: InteriorNode.element_type(x) != "package"

         for element in elements:
             if element in node.nodes:
                 node = node.nodes[element]
             else:
                 return []

         return node.values(selector)

     def append_values(self, values, selector):
         for key, node in self.nodes.items():
             if selector(key):
                 node.append_values(values, lambda x: True)

     def child_nodes(self):
         return self.nodes.values()


 @dataclasses.dataclass()
 class Leaf(Node):
     """A leaf of the trie"""

     # The value associated with this leaf.
     value: typing.Any

     def append_values(self, values, selector):
         values.append(self.value)

     def child_nodes(self):
         return []


 def signature_trie():
     return InteriorNode(type="root", selector="")
	#!/usr/bin/env python
	#
	# 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.
	"""Verify that one set of hidden API flags is a subset of another."""
	import dataclasses
	import typing

	from itertools import chain


	@dataclasses.dataclass()
	class Node:
	"""A node in the signature trie."""

	# The type of the node.
	#
	# Leaf nodes are of type "member".
	# Interior nodes can be either "package", or "class".
	type: str

	# The selector of the node.
	#
	# That is a string that can be used to select the node, e.g. in a pattern
	# that is passed to InteriorNode.get_matching_rows().
	selector: str

	def values(self, selector):
	"""Get the values from a set of selected nodes.

	:param selector: a function that can be applied to a key in the nodes
	attribute to determine whether to return its values.

	:return: A list of iterables of all the values associated with
	this node and its children.
	"""
	values = []
	self.append_values(values, selector)
	return values

	def append_values(self, values, selector):
	"""Append the values associated with this node and its children.

	For each item (key, child) in nodes the child node's values are returned
	if and only if the selector returns True when called on its key. A child
	node's values are all the values associated with it and all its
	descendant nodes.

	:param selector: a function that can be applied to a key in the nodes
	attribute to determine whether to return its values.
	:param values: a list of a iterables of values.
	"""
	raise NotImplementedError("Please Implement this method")

	def child_nodes(self):
	"""Get an iterable of the child nodes of this node."""
	raise NotImplementedError("Please Implement this method")


	# pylint: disable=line-too-long
	@dataclasses.dataclass()
	class InteriorNode(Node):
	"""An interior node in a trie.

	Each interior node has a dict that maps from an element of a signature to
	either another interior node or a leaf. Each interior node represents either
	a package, class or nested class. Class members are represented by a Leaf.

	Associating the set of flags [public-api] with the signature
	"Ljava/lang/Object;->String()Ljava/lang/String;" will cause the following
	nodes to be created:
	Node()
	^- package:java -> Node()
	^- package:lang -> Node()
	^- class:Object -> Node()
	^- member:String()Ljava/lang/String; -> Leaf([public-api])

	Associating the set of flags [blocked,core-platform-api] with the signature
	"Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;"
	will cause the following nodes to be created:
	Node()
	^- package:java -> Node()
	^- package:lang -> Node()
	^- class:Character -> Node()
	^- class:UnicodeScript -> Node()
	^- member:of(I)Ljava/lang/Character$UnicodeScript;
	-> Leaf([blocked,core-platform-api])
	"""

	# pylint: enable=line-too-long

	# A dict from an element of the signature to the Node/Leaf containing the
	# next element/value.
	nodes: typing.Dict[str, Node] = dataclasses.field(default_factory=dict)

	# pylint: disable=line-too-long
	@staticmethod
	def signature_to_elements(signature):
	"""Split a signature or a prefix into a number of elements:

	1. The packages (excluding the leading L preceding the first package).
	2. The class names, from outermost to innermost.
	3. The member signature.
	e.g.
	Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;
	will be broken down into these elements:
	1. package:java
	2. package:lang
	3. class:Character
	4. class:UnicodeScript
	5. member:of(I)Ljava/lang/Character$UnicodeScript;
	"""
	# Remove the leading L.
	# - java/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;
	text = signature.removeprefix("L")
	# Split the signature between qualified class name and the class member
	# signature.
	# 0 - java/lang/Character$UnicodeScript
	# 1 - of(I)Ljava/lang/Character$UnicodeScript;
	parts = text.split(";->")
	# If there is no member then this will be an empty list.
	member = parts[1:]
	# Split the qualified class name into packages, and class name.
	# 0 - java
	# 1 - lang
	# 2 - Character$UnicodeScript
	elements = parts[0].split("/")
	last_element = elements[-1]
	wildcard = []
	classes = []
	if "*" in last_element:
	if last_element not in ("", "*"):
	raise Exception(f"Invalid signature '{signature}': invalid "
	f"wildcard '{last_element}'")
	packages = elements[0:-1]
	# Cannot specify a wildcard and target a specific member
	if member:
	raise Exception(f"Invalid signature '{signature}': contains "
	f"wildcard '{last_element}' and "
	f"member signature '{member[0]}'")
	wildcard = [last_element]
	else:
	packages = elements[0:-1]
	# Split the class name into outer / inner classes
	# 0 - Character
	# 1 - UnicodeScript
	classes = last_element.removesuffix(";").split("$")

	# Assemble the parts into a single list, adding prefixes to identify
	# the different parts. If a wildcard is provided then it looks something
	# like this:
	# 0 - package:java
	# 1 - package:lang
	# 2 - *
	#
	# Otherwise, it looks something like this:
	# 0 - package:java
	# 1 - package:lang
	# 2 - class:Character
	# 3 - class:UnicodeScript
	# 4 - member:of(I)Ljava/lang/Character$UnicodeScript;
	return list(
	chain([("package", x) for x in packages],
	[("class", x) for x in classes],
	[("member", x) for x in member],
	[("wildcard", x) for x in wildcard]))

	# pylint: enable=line-too-long

	@staticmethod
	def split_element(element):
	element_type, element_value = element
	return element_type, element_value

	@staticmethod
	def element_type(element):
	element_type, _ = InteriorNode.split_element(element)
	return element_type

	@staticmethod
	def elements_to_selector(elements):
	"""Compute a selector for a set of elements.

	A selector uniquely identifies a specific Node in the trie. It is
	essentially a prefix of a signature (without the leading L).

	e.g. a trie containing "Ljava/lang/Object;->String()Ljava/lang/String;"
	would contain nodes with the following selectors:
	* "java"
	* "java/lang"
	* "java/lang/Object"
	* "java/lang/Object;->String()Ljava/lang/String;"
	"""
	signature = ""
	preceding_type = ""
	for element in elements:
	element_type, element_value = InteriorNode.split_element(element)
	separator = ""
	if element_type == "package":
	separator = "/"
	elif element_type == "class":
	if preceding_type == "class":
	separator = "$"
	else:
	separator = "/"
	elif element_type == "wildcard":
	separator = "/"
	elif element_type == "member":
	separator += ";->"

	if signature:
	signature += separator

	signature += element_value

	preceding_type = element_type

	return signature

	def add(self, signature, value, only_if_matches=False):
	"""Associate the value with the specific signature.

	:param signature: the member signature
	:param value: the value to associated with the signature
	:param only_if_matches: True if the value is added only if the signature
	matches at least one of the existing top level packages.
	:return: n/a
	"""
	# Split the signature into elements.
	elements = self.signature_to_elements(signature)
	# Find the Node associated with the deepest class.
	node = self
	for index, element in enumerate(elements[:-1]):
	if element in node.nodes:
	node = node.nodes[element]
	elif only_if_matches and index == 0:
	return
	else:
	selector = self.elements_to_selector(elements[0:index + 1])
	next_node = InteriorNode(
	type=InteriorNode.element_type(element), selector=selector)
	node.nodes[element] = next_node
	node = next_node
	# Add a Leaf containing the value and associate it with the member
	# signature within the class.
	last_element = elements[-1]
	last_element_type = self.element_type(last_element)
	if last_element_type != "member":
	raise Exception(
	f"Invalid signature: {signature}, does not identify a "
	"specific member")
	if last_element in node.nodes:
	raise Exception(f"Duplicate signature: {signature}")
	leaf = Leaf(
	type=last_element_type,
	selector=signature,
	value=value,
	)
	node.nodes[last_element] = leaf

	def get_matching_rows(self, pattern):
	"""Get the values (plural) associated with the pattern.

	e.g. If the pattern is a full signature then this will return a list
	containing the value associated with that signature.

	If the pattern is a class then this will return a list containing the
	values associated with all members of that class.

	If the pattern ends with "*" then the preceding part is treated as a
	package and this will return a list containing the values associated
	with all the members of all the classes in that package.

	If the pattern ends with "**" then the preceding part is treated
	as a package and this will return a list containing the values
	associated with all the members of all the classes in that package and
	all sub-packages.

	:param pattern: the pattern which could be a complete signature or a
	class, or package wildcard.
	:return: an iterable containing all the values associated with the
	pattern.
	"""
	elements = self.signature_to_elements(pattern)
	node = self

	# Include all values from this node and all its children.
	selector = lambda x: True

	last_element = elements[-1]
	last_element_type, last_element_value = self.split_element(last_element)
	if last_element_type == "wildcard":
	elements = elements[:-1]
	if last_element_value == "*":
	# Do not include values from sub-packages.
	selector = lambda x: InteriorNode.element_type(x) != "package"

	for element in elements:
	if element in node.nodes:
	node = node.nodes[element]
	else:
	return []

	return node.values(selector)

	def append_values(self, values, selector):
	for key, node in self.nodes.items():
	if selector(key):
	node.append_values(values, lambda x: True)

	def child_nodes(self):
	return self.nodes.values()


	@dataclasses.dataclass()
	class Leaf(Node):
	"""A leaf of the trie"""

	# The value associated with this leaf.
	value: typing.Any

	def append_values(self, values, selector):
	values.append(self.value)

	def child_nodes(self):
	return []


	def signature_trie():
	return InteriorNode(type="root", selector="")