signature_trie.py 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341
  1. #!/usr/bin/env python
  2. #
  3. # Copyright (C) 2022 The Android Open Source Project
  4. #
  5. # Licensed under the Apache License, Version 2.0 (the "License");
  6. # you may not use this file except in compliance with the License.
  7. # You may obtain a copy of the License at
  8. #
  9. # http://www.apache.org/licenses/LICENSE-2.0
  10. #
  11. # Unless required by applicable law or agreed to in writing, software
  12. # distributed under the License is distributed on an "AS IS" BASIS,
  13. # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14. # See the License for the specific language governing permissions and
  15. # limitations under the License.
  16. """Verify that one set of hidden API flags is a subset of another."""
  17. import dataclasses
  18. import typing
  19. from itertools import chain
  20. @dataclasses.dataclass()
  21. class Node:
  22. """A node in the signature trie."""
  23. # The type of the node.
  24. #
  25. # Leaf nodes are of type "member".
  26. # Interior nodes can be either "package", or "class".
  27. type: str
  28. # The selector of the node.
  29. #
  30. # That is a string that can be used to select the node, e.g. in a pattern
  31. # that is passed to InteriorNode.get_matching_rows().
  32. selector: str
  33. def values(self, selector):
  34. """Get the values from a set of selected nodes.
  35. :param selector: a function that can be applied to a key in the nodes
  36. attribute to determine whether to return its values.
  37. :return: A list of iterables of all the values associated with
  38. this node and its children.
  39. """
  40. values = []
  41. self.append_values(values, selector)
  42. return values
  43. def append_values(self, values, selector):
  44. """Append the values associated with this node and its children.
  45. For each item (key, child) in nodes the child node's values are returned
  46. if and only if the selector returns True when called on its key. A child
  47. node's values are all the values associated with it and all its
  48. descendant nodes.
  49. :param selector: a function that can be applied to a key in the nodes
  50. attribute to determine whether to return its values.
  51. :param values: a list of a iterables of values.
  52. """
  53. raise NotImplementedError("Please Implement this method")
  54. def child_nodes(self):
  55. """Get an iterable of the child nodes of this node."""
  56. raise NotImplementedError("Please Implement this method")
  57. # pylint: disable=line-too-long
  58. @dataclasses.dataclass()
  59. class InteriorNode(Node):
  60. """An interior node in a trie.
  61. Each interior node has a dict that maps from an element of a signature to
  62. either another interior node or a leaf. Each interior node represents either
  63. a package, class or nested class. Class members are represented by a Leaf.
  64. Associating the set of flags [public-api] with the signature
  65. "Ljava/lang/Object;->String()Ljava/lang/String;" will cause the following
  66. nodes to be created:
  67. Node()
  68. ^- package:java -> Node()
  69. ^- package:lang -> Node()
  70. ^- class:Object -> Node()
  71. ^- member:String()Ljava/lang/String; -> Leaf([public-api])
  72. Associating the set of flags [blocked,core-platform-api] with the signature
  73. "Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;"
  74. will cause the following nodes to be created:
  75. Node()
  76. ^- package:java -> Node()
  77. ^- package:lang -> Node()
  78. ^- class:Character -> Node()
  79. ^- class:UnicodeScript -> Node()
  80. ^- member:of(I)Ljava/lang/Character$UnicodeScript;
  81. -> Leaf([blocked,core-platform-api])
  82. """
  83. # pylint: enable=line-too-long
  84. # A dict from an element of the signature to the Node/Leaf containing the
  85. # next element/value.
  86. nodes: typing.Dict[str, Node] = dataclasses.field(default_factory=dict)
  87. # pylint: disable=line-too-long
  88. @staticmethod
  89. def signature_to_elements(signature):
  90. """Split a signature or a prefix into a number of elements:
  91. 1. The packages (excluding the leading L preceding the first package).
  92. 2. The class names, from outermost to innermost.
  93. 3. The member signature.
  94. e.g.
  95. Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;
  96. will be broken down into these elements:
  97. 1. package:java
  98. 2. package:lang
  99. 3. class:Character
  100. 4. class:UnicodeScript
  101. 5. member:of(I)Ljava/lang/Character$UnicodeScript;
  102. """
  103. # Remove the leading L.
  104. # - java/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;
  105. text = signature.removeprefix("L")
  106. # Split the signature between qualified class name and the class member
  107. # signature.
  108. # 0 - java/lang/Character$UnicodeScript
  109. # 1 - of(I)Ljava/lang/Character$UnicodeScript;
  110. parts = text.split(";->")
  111. # If there is no member then this will be an empty list.
  112. member = parts[1:]
  113. # Split the qualified class name into packages, and class name.
  114. # 0 - java
  115. # 1 - lang
  116. # 2 - Character$UnicodeScript
  117. elements = parts[0].split("/")
  118. last_element = elements[-1]
  119. wildcard = []
  120. classes = []
  121. if "*" in last_element:
  122. if last_element not in ("*", "**"):
  123. raise Exception(f"Invalid signature '{signature}': invalid "
  124. f"wildcard '{last_element}'")
  125. packages = elements[0:-1]
  126. # Cannot specify a wildcard and target a specific member
  127. if member:
  128. raise Exception(f"Invalid signature '{signature}': contains "
  129. f"wildcard '{last_element}' and "
  130. f"member signature '{member[0]}'")
  131. wildcard = [last_element]
  132. else:
  133. packages = elements[0:-1]
  134. # Split the class name into outer / inner classes
  135. # 0 - Character
  136. # 1 - UnicodeScript
  137. classes = last_element.removesuffix(";").split("$")
  138. # Assemble the parts into a single list, adding prefixes to identify
  139. # the different parts. If a wildcard is provided then it looks something
  140. # like this:
  141. # 0 - package:java
  142. # 1 - package:lang
  143. # 2 - *
  144. #
  145. # Otherwise, it looks something like this:
  146. # 0 - package:java
  147. # 1 - package:lang
  148. # 2 - class:Character
  149. # 3 - class:UnicodeScript
  150. # 4 - member:of(I)Ljava/lang/Character$UnicodeScript;
  151. return list(
  152. chain([("package", x) for x in packages],
  153. [("class", x) for x in classes],
  154. [("member", x) for x in member],
  155. [("wildcard", x) for x in wildcard]))
  156. # pylint: enable=line-too-long
  157. @staticmethod
  158. def split_element(element):
  159. element_type, element_value = element
  160. return element_type, element_value
  161. @staticmethod
  162. def element_type(element):
  163. element_type, _ = InteriorNode.split_element(element)
  164. return element_type
  165. @staticmethod
  166. def elements_to_selector(elements):
  167. """Compute a selector for a set of elements.
  168. A selector uniquely identifies a specific Node in the trie. It is
  169. essentially a prefix of a signature (without the leading L).
  170. e.g. a trie containing "Ljava/lang/Object;->String()Ljava/lang/String;"
  171. would contain nodes with the following selectors:
  172. * "java"
  173. * "java/lang"
  174. * "java/lang/Object"
  175. * "java/lang/Object;->String()Ljava/lang/String;"
  176. """
  177. signature = ""
  178. preceding_type = ""
  179. for element in elements:
  180. element_type, element_value = InteriorNode.split_element(element)
  181. separator = ""
  182. if element_type == "package":
  183. separator = "/"
  184. elif element_type == "class":
  185. if preceding_type == "class":
  186. separator = "$"
  187. else:
  188. separator = "/"
  189. elif element_type == "wildcard":
  190. separator = "/"
  191. elif element_type == "member":
  192. separator += ";->"
  193. if signature:
  194. signature += separator
  195. signature += element_value
  196. preceding_type = element_type
  197. return signature
  198. def add(self, signature, value, only_if_matches=False):
  199. """Associate the value with the specific signature.
  200. :param signature: the member signature
  201. :param value: the value to associated with the signature
  202. :param only_if_matches: True if the value is added only if the signature
  203. matches at least one of the existing top level packages.
  204. :return: n/a
  205. """
  206. # Split the signature into elements.
  207. elements = self.signature_to_elements(signature)
  208. # Find the Node associated with the deepest class.
  209. node = self
  210. for index, element in enumerate(elements[:-1]):
  211. if element in node.nodes:
  212. node = node.nodes[element]
  213. elif only_if_matches and index == 0:
  214. return
  215. else:
  216. selector = self.elements_to_selector(elements[0:index + 1])
  217. next_node = InteriorNode(
  218. type=InteriorNode.element_type(element), selector=selector)
  219. node.nodes[element] = next_node
  220. node = next_node
  221. # Add a Leaf containing the value and associate it with the member
  222. # signature within the class.
  223. last_element = elements[-1]
  224. last_element_type = self.element_type(last_element)
  225. if last_element_type != "member":
  226. raise Exception(
  227. f"Invalid signature: {signature}, does not identify a "
  228. "specific member")
  229. if last_element in node.nodes:
  230. raise Exception(f"Duplicate signature: {signature}")
  231. leaf = Leaf(
  232. type=last_element_type,
  233. selector=signature,
  234. value=value,
  235. )
  236. node.nodes[last_element] = leaf
  237. def get_matching_rows(self, pattern):
  238. """Get the values (plural) associated with the pattern.
  239. e.g. If the pattern is a full signature then this will return a list
  240. containing the value associated with that signature.
  241. If the pattern is a class then this will return a list containing the
  242. values associated with all members of that class.
  243. If the pattern ends with "*" then the preceding part is treated as a
  244. package and this will return a list containing the values associated
  245. with all the members of all the classes in that package.
  246. If the pattern ends with "**" then the preceding part is treated
  247. as a package and this will return a list containing the values
  248. associated with all the members of all the classes in that package and
  249. all sub-packages.
  250. :param pattern: the pattern which could be a complete signature or a
  251. class, or package wildcard.
  252. :return: an iterable containing all the values associated with the
  253. pattern.
  254. """
  255. elements = self.signature_to_elements(pattern)
  256. node = self
  257. # Include all values from this node and all its children.
  258. selector = lambda x: True
  259. last_element = elements[-1]
  260. last_element_type, last_element_value = self.split_element(last_element)
  261. if last_element_type == "wildcard":
  262. elements = elements[:-1]
  263. if last_element_value == "*":
  264. # Do not include values from sub-packages.
  265. selector = lambda x: InteriorNode.element_type(x) != "package"
  266. for element in elements:
  267. if element in node.nodes:
  268. node = node.nodes[element]
  269. else:
  270. return []
  271. return node.values(selector)
  272. def append_values(self, values, selector):
  273. for key, node in self.nodes.items():
  274. if selector(key):
  275. node.append_values(values, lambda x: True)
  276. def child_nodes(self):
  277. return self.nodes.values()
  278. @dataclasses.dataclass()
  279. class Leaf(Node):
  280. """A leaf of the trie"""
  281. # The value associated with this leaf.
  282. value: typing.Any
  283. def append_values(self, values, selector):
  284. values.append(self.value)
  285. def child_nodes(self):
  286. return []
  287. def signature_trie():
  288. return InteriorNode(type="root", selector="")