123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341 |
- #!/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="")
|