Use trie to store monolithic hidden API flags
Previously, a simple map from dex signature to the flags was used to
store the monolithic hidden API flags. This change replaces that with a
trie that uses packages and class names extracted from the signature
to map from the signature to the flags.
The signature is broken down into pieces consisting of package names,
class names and the remaining member signature. They are used in turn
to navigate through nodes in the trie to a Leaf that contains the flags
associated with the signature.
The flags can be retrieved from the trie in a number of ways:
* Using the complete signature to retrieve the flags for a single
member.
* Using a class name to retrieve the flags for all the members in a
class and any nested classes.
* Using a package wildcard to retrieve the flags for all the members in
the classes in that package.
* Using a recursive package wildcard to retrieve the flags for all the
members in the classes in that package and nested packages.
This will allow a bootclasspath_fragment to select a subset of the
monolithic flags to compare against itself without specifying the
signatures of every member of that set.
Before creating the trie an attempt was made to compute the subset by
iterating over all the signatures in the monolithic flags and matching
against a regular expression created from the patterns but that was too
slow. It took minutes to run whereas using the simple map or the trie
only takes a few seconds.
Bug: 194063708
Test: atest --host verify_overlaps_test
Change-Id: I36f5e319d3e7d62dd34305de1eec990a93cb3a89
diff --git a/scripts/hiddenapi/verify_overlaps_test.py b/scripts/hiddenapi/verify_overlaps_test.py
index b6d5fa3..7477254 100755
--- a/scripts/hiddenapi/verify_overlaps_test.py
+++ b/scripts/hiddenapi/verify_overlaps_test.py
@@ -20,8 +20,52 @@
from verify_overlaps import *
+class TestSignatureToElements(unittest.TestCase):
+
+ def signatureToElements(self, signature):
+ return InteriorNode().signatureToElements(signature)
+
+ def test_signatureToElements_1(self):
+ expected = [
+ 'package:java',
+ 'package:lang',
+ 'class:ProcessBuilder',
+ 'class:Redirect',
+ 'class:1',
+ 'member:<init>()V',
+ ]
+ self.assertEqual(expected, self.signatureToElements(
+ "Ljava/lang/ProcessBuilder$Redirect$1;-><init>()V"))
+
+ def test_signatureToElements_2(self):
+ expected = [
+ 'package:java',
+ 'package:lang',
+ 'class:Object',
+ 'member:hashCode()I',
+ ]
+ self.assertEqual(expected, self.signatureToElements(
+ "Ljava/lang/Object;->hashCode()I"))
+
+ def test_signatureToElements_3(self):
+ expected = [
+ 'package:java',
+ 'package:lang',
+ 'class:CharSequence',
+ 'class:',
+ 'class:ExternalSyntheticLambda0',
+ 'member:<init>(Ljava/lang/CharSequence;)V',
+ ]
+ self.assertEqual(expected, self.signatureToElements(
+ "Ljava/lang/CharSequence$$ExternalSyntheticLambda0;"
+ "-><init>(Ljava/lang/CharSequence;)V"))
+
class TestDetectOverlaps(unittest.TestCase):
+ def read_flag_trie_from_string(self, csv):
+ with io.StringIO(csv) as f:
+ return read_flag_trie_from_stream(f)
+
def read_signature_csv_from_string_as_dict(self, csv):
with io.StringIO(csv) as f:
return read_signature_csv_from_stream_as_dict(f)
@@ -33,13 +77,14 @@
extractInput = '''
Ljava/lang/Object;->hashCode()I,public-api,system-api,test-api
Ljava/lang/Object;->toString()Ljava/lang/String;,blocked
+Ljava/util/zip/ZipFile;-><clinit>()V,blocked
+Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;,blocked
+Ljava/lang/Character;->serialVersionUID:J,sdk
+Ljava/lang/ProcessBuilder$Redirect$1;-><init>()V,blocked
'''
- def test_extract_subset(self):
- monolithic = self.read_signature_csv_from_string_as_dict(TestDetectOverlaps.extractInput)
- modular = self.read_signature_csv_from_string_as_dict('''
-Ljava/lang/Object;->hashCode()I,public-api,system-api,test-api
-''')
+ def test_extract_subset_signature(self):
+ monolithic = self.read_flag_trie_from_string(TestDetectOverlaps.extractInput)
patterns = 'Ljava/lang/Object;->hashCode()I'
@@ -52,6 +97,144 @@
}
self.assertEqual(expected, subset)
+ def test_extract_subset_class(self):
+ monolithic = self.read_flag_trie_from_string(TestDetectOverlaps.extractInput)
+
+ patterns = 'java/lang/Object'
+
+ subset = self.extract_subset_from_monolithic_flags_as_dict_from_string(monolithic, patterns)
+ expected = {
+ 'Ljava/lang/Object;->hashCode()I': {
+ None: ['public-api', 'system-api', 'test-api'],
+ 'signature': 'Ljava/lang/Object;->hashCode()I',
+ },
+ 'Ljava/lang/Object;->toString()Ljava/lang/String;': {
+ None: ['blocked'],
+ 'signature': 'Ljava/lang/Object;->toString()Ljava/lang/String;',
+ },
+ }
+ self.assertEqual(expected, subset)
+
+ def test_extract_subset_outer_class(self):
+ monolithic = self.read_flag_trie_from_string(TestDetectOverlaps.extractInput)
+
+ patterns = 'java/lang/Character'
+
+ subset = self.extract_subset_from_monolithic_flags_as_dict_from_string(monolithic, patterns)
+ expected = {
+ 'Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;': {
+ None: ['blocked'],
+ 'signature': 'Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;',
+ },
+ 'Ljava/lang/Character;->serialVersionUID:J': {
+ None: ['sdk'],
+ 'signature': 'Ljava/lang/Character;->serialVersionUID:J',
+ },
+ }
+ self.assertEqual(expected, subset)
+
+ def test_extract_subset_nested_class(self):
+ monolithic = self.read_flag_trie_from_string(TestDetectOverlaps.extractInput)
+
+ patterns = 'java/lang/Character$UnicodeScript'
+
+ subset = self.extract_subset_from_monolithic_flags_as_dict_from_string(monolithic, patterns)
+ expected = {
+ 'Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;': {
+ None: ['blocked'],
+ 'signature': 'Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;',
+ },
+ }
+ self.assertEqual(expected, subset)
+
+ def test_extract_subset_package(self):
+ monolithic = self.read_flag_trie_from_string(TestDetectOverlaps.extractInput)
+
+ patterns = 'java/lang/*'
+
+ subset = self.extract_subset_from_monolithic_flags_as_dict_from_string(monolithic, patterns)
+ expected = {
+ 'Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;': {
+ None: ['blocked'],
+ 'signature': 'Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;',
+ },
+ 'Ljava/lang/Character;->serialVersionUID:J': {
+ None: ['sdk'],
+ 'signature': 'Ljava/lang/Character;->serialVersionUID:J',
+ },
+ 'Ljava/lang/Object;->hashCode()I': {
+ None: ['public-api', 'system-api', 'test-api'],
+ 'signature': 'Ljava/lang/Object;->hashCode()I',
+ },
+ 'Ljava/lang/Object;->toString()Ljava/lang/String;': {
+ None: ['blocked'],
+ 'signature': 'Ljava/lang/Object;->toString()Ljava/lang/String;',
+ },
+ 'Ljava/lang/ProcessBuilder$Redirect$1;-><init>()V': {
+ None: ['blocked'],
+ 'signature': 'Ljava/lang/ProcessBuilder$Redirect$1;-><init>()V',
+ },
+ }
+ self.assertEqual(expected, subset)
+
+ def test_extract_subset_recursive_package(self):
+ monolithic = self.read_flag_trie_from_string(TestDetectOverlaps.extractInput)
+
+ patterns = 'java/**'
+
+ subset = self.extract_subset_from_monolithic_flags_as_dict_from_string(monolithic, patterns)
+ expected = {
+ 'Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;': {
+ None: ['blocked'],
+ 'signature': 'Ljava/lang/Character$UnicodeScript;->of(I)Ljava/lang/Character$UnicodeScript;',
+ },
+ 'Ljava/lang/Character;->serialVersionUID:J': {
+ None: ['sdk'],
+ 'signature': 'Ljava/lang/Character;->serialVersionUID:J',
+ },
+ 'Ljava/lang/Object;->hashCode()I': {
+ None: ['public-api', 'system-api', 'test-api'],
+ 'signature': 'Ljava/lang/Object;->hashCode()I',
+ },
+ 'Ljava/lang/Object;->toString()Ljava/lang/String;': {
+ None: ['blocked'],
+ 'signature': 'Ljava/lang/Object;->toString()Ljava/lang/String;',
+ },
+ 'Ljava/lang/ProcessBuilder$Redirect$1;-><init>()V': {
+ None: ['blocked'],
+ 'signature': 'Ljava/lang/ProcessBuilder$Redirect$1;-><init>()V',
+ },
+ 'Ljava/util/zip/ZipFile;-><clinit>()V': {
+ None: ['blocked'],
+ 'signature': 'Ljava/util/zip/ZipFile;-><clinit>()V',
+ },
+ }
+ self.assertEqual(expected, subset)
+
+ def test_extract_subset_invalid_pattern_wildcard_and_member(self):
+ monolithic = self.read_flag_trie_from_string(TestDetectOverlaps.extractInput)
+
+ patterns = 'Ljava/lang/*;->hashCode()I'
+
+ with self.assertRaises(Exception) as context:
+ self.extract_subset_from_monolithic_flags_as_dict_from_string(monolithic, patterns)
+ self.assertTrue("contains wildcard * and member signature hashCode()I" in str(context.exception))
+
+ def test_read_trie_duplicate(self):
+ with self.assertRaises(Exception) as context:
+ self.read_flag_trie_from_string('''
+Ljava/lang/Object;->hashCode()I,public-api,system-api,test-api
+Ljava/lang/Object;->hashCode()I,blocked
+''')
+ self.assertTrue("Duplicate signature: Ljava/lang/Object;->hashCode()I" in str(context.exception))
+
+ def test_read_trie_missing_member(self):
+ with self.assertRaises(Exception) as context:
+ self.read_flag_trie_from_string('''
+Ljava/lang/Object,public-api,system-api,test-api
+''')
+ self.assertTrue("Invalid signature: Ljava/lang/Object, does not identify a specific member" in str(context.exception))
+
def test_match(self):
monolithic = self.read_signature_csv_from_string_as_dict('''
Ljava/lang/Object;->hashCode()I,public-api,system-api,test-api