Merge "Modify the splitsRulesIntoIndexBuckets to return sorted list of rules instead of a Map that contains unordered set of rules."

2 files changed, 91 insertions, 43 deletions

diff --git a/services/core/java/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifier.java b/services/core/java/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifier.java
index 61dddf09a80a..7d5e83649373 100644
--- a/services/core/java/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifier.java
+++ b/services/core/java/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifier.java
@@ -30,6 +30,7 @@ import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Optional;
+import java.util.TreeMap;
 
 /** A helper class for identifying the indexing type and key of a given rule. */
 class RuleIndexingDetailsIdentifier {
@@ -37,23 +38,29 @@ class RuleIndexingDetailsIdentifier {
     private static final String DEFAULT_RULE_KEY = "N/A";
 
     /**
-     * Splits a given rule list into three indexing categories.
+     * Splits a given rule list into three indexing categories and returns a sorted list of rules
+     * per each index.
      *
-     * TODO(b/145488708): Instead of this structure, sort the values in the map and just return a
-     * sorted list.
+     * The sorting guarantees an order based on the key but the rules that have the same key
+     * can be in arbitrary order. For example, given the rules of [package_name_a_rule_1,
+     * package_name_a_rule_2, package_name_b_rule_3, package_name_b_rule_4], the  method will
+     * guarantee that package_name_b rules (i.e., 3 and 4) will never come before package_name_a
+     * rules (i.e., 1 and 2). However, we do not care about the ordering between rule 1 and 2.
+     * We also do not care about the ordering between rule 3 and 4.
      */
-    public static Map<Integer, Map<String, List<Rule>>> splitRulesIntoIndexBuckets(
-            List<Rule> rules) {
+    public static Map<Integer, List<Rule>> splitRulesIntoIndexBuckets(List<Rule> rules) {
         if (rules == null) {
             throw new IllegalArgumentException(
                     "Index buckets cannot be created for null rule list.");
         }
 
         Map<Integer, Map<String, List<Rule>>> typeOrganizedRuleMap = new HashMap();
-        typeOrganizedRuleMap.put(NOT_INDEXED, new HashMap());
-        typeOrganizedRuleMap.put(PACKAGE_NAME_INDEXED, new HashMap());
-        typeOrganizedRuleMap.put(APP_CERTIFICATE_INDEXED, new HashMap());
+        typeOrganizedRuleMap.put(NOT_INDEXED, new TreeMap());
+        typeOrganizedRuleMap.put(PACKAGE_NAME_INDEXED, new TreeMap());
+        typeOrganizedRuleMap.put(APP_CERTIFICATE_INDEXED, new TreeMap());
 
+        // Split the rules into the appropriate indexed pattern. The Tree Maps help us to keep the
+        // entries sorted by their index key.
         for (Rule rule : rules) {
             RuleIndexingDetails indexingDetails = getIndexingDetails(rule.getFormula());
             String ruleKey =
@@ -73,7 +80,19 @@ class RuleIndexingDetailsIdentifier {
                     .add(rule);
         }
 
-        return typeOrganizedRuleMap;
+        // Per indexing type, create the sorted rule set based on their key.
+        Map<Integer, List<Rule>> orderedListPerIndexingType = new HashMap<>();
+
+        for (Integer indexingKey : typeOrganizedRuleMap.keySet()) {
+            List<Rule> sortedRules = new ArrayList();
+            for (Map.Entry<String, List<Rule>> entry :
+                    typeOrganizedRuleMap.get(indexingKey).entrySet()) {
+                sortedRules.addAll(entry.getValue());
+            }
+            orderedListPerIndexingType.put(indexingKey, sortedRules);
+        }
+
+        return orderedListPerIndexingType;
     }
 
     private static RuleIndexingDetails getIndexingDetails(Formula formula) {
diff --git a/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifierTest.java b/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifierTest.java
index b25f3bc5c3fd..90ec19e06c8c 100644
--- a/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifierTest.java
+++ b/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifierTest.java
@@ -138,16 +138,14 @@ public class RuleIndexingDetailsIdentifierTest {
         List<Rule> ruleList = new ArrayList();
         ruleList.add(RULE_WITH_PACKAGE_NAME);
 
-        Map<Integer, Map<String, List<Rule>>> result = splitRulesIntoIndexBuckets(ruleList);
+        Map<Integer, List<Rule>> result = splitRulesIntoIndexBuckets(ruleList);
 
         // Verify the resulting map content.
         assertThat(result.keySet())
                 .containsExactly(NOT_INDEXED, PACKAGE_NAME_INDEXED, APP_CERTIFICATE_INDEXED);
         assertThat(result.get(NOT_INDEXED)).isEmpty();
         assertThat(result.get(APP_CERTIFICATE_INDEXED)).isEmpty();
-        assertThat(result.get(PACKAGE_NAME_INDEXED).keySet()).containsExactly(SAMPLE_PACKAGE_NAME);
-        assertThat(result.get(PACKAGE_NAME_INDEXED).get(SAMPLE_PACKAGE_NAME))
-                .containsExactly(RULE_WITH_PACKAGE_NAME);
+        assertThat(result.get(PACKAGE_NAME_INDEXED)).containsExactly(RULE_WITH_PACKAGE_NAME);
     }
 
     @Test
@@ -155,16 +153,13 @@ public class RuleIndexingDetailsIdentifierTest {
         List<Rule> ruleList = new ArrayList();
         ruleList.add(RULE_WITH_APP_CERTIFICATE);
 
-        Map<Integer, Map<String, List<Rule>>> result = splitRulesIntoIndexBuckets(ruleList);
+        Map<Integer, List<Rule>> result = splitRulesIntoIndexBuckets(ruleList);
 
         assertThat(result.keySet())
                 .containsExactly(NOT_INDEXED, PACKAGE_NAME_INDEXED, APP_CERTIFICATE_INDEXED);
         assertThat(result.get(NOT_INDEXED)).isEmpty();
         assertThat(result.get(PACKAGE_NAME_INDEXED)).isEmpty();
-        assertThat(result.get(APP_CERTIFICATE_INDEXED).keySet())
-                .containsExactly(SAMPLE_APP_CERTIFICATE);
-        assertThat(result.get(APP_CERTIFICATE_INDEXED).get(SAMPLE_APP_CERTIFICATE))
-                .containsExactly(RULE_WITH_APP_CERTIFICATE);
+        assertThat(result.get(APP_CERTIFICATE_INDEXED)).containsExactly(RULE_WITH_APP_CERTIFICATE);
     }
 
     @Test
@@ -172,15 +167,13 @@ public class RuleIndexingDetailsIdentifierTest {
         List<Rule> ruleList = new ArrayList();
         ruleList.add(RULE_WITH_INSTALLER_RESTRICTIONS);
 
-        Map<Integer, Map<String, List<Rule>>> result = splitRulesIntoIndexBuckets(ruleList);
+        Map<Integer, List<Rule>> result = splitRulesIntoIndexBuckets(ruleList);
 
         assertThat(result.keySet())
                 .containsExactly(NOT_INDEXED, PACKAGE_NAME_INDEXED, APP_CERTIFICATE_INDEXED);
         assertThat(result.get(PACKAGE_NAME_INDEXED)).isEmpty();
         assertThat(result.get(APP_CERTIFICATE_INDEXED)).isEmpty();
-        assertThat(result.get(NOT_INDEXED).keySet()).containsExactly("N/A");
-        assertThat(result.get(NOT_INDEXED).get("N/A"))
-                .containsExactly(RULE_WITH_INSTALLER_RESTRICTIONS);
+        assertThat(result.get(NOT_INDEXED)).containsExactly(RULE_WITH_INSTALLER_RESTRICTIONS);
     }
 
     @Test
@@ -188,15 +181,13 @@ public class RuleIndexingDetailsIdentifierTest {
         List<Rule> ruleList = new ArrayList();
         ruleList.add(RULE_WITH_NONSTRING_RESTRICTIONS);
 
-        Map<Integer, Map<String, List<Rule>>> result = splitRulesIntoIndexBuckets(ruleList);
+        Map<Integer, List<Rule>> result = splitRulesIntoIndexBuckets(ruleList);
 
         assertThat(result.keySet())
                 .containsExactly(NOT_INDEXED, PACKAGE_NAME_INDEXED, APP_CERTIFICATE_INDEXED);
         assertThat(result.get(PACKAGE_NAME_INDEXED)).isEmpty();
         assertThat(result.get(APP_CERTIFICATE_INDEXED)).isEmpty();
-        assertThat(result.get(NOT_INDEXED).keySet()).containsExactly("N/A");
-        assertThat(result.get(NOT_INDEXED).get("N/A"))
-                .containsExactly(RULE_WITH_NONSTRING_RESTRICTIONS);
+        assertThat(result.get(NOT_INDEXED)).containsExactly(RULE_WITH_NONSTRING_RESTRICTIONS);
     }
 
     @Test
@@ -215,41 +206,79 @@ public class RuleIndexingDetailsIdentifierTest {
         List<Rule> ruleList = new ArrayList();
         ruleList.add(negatedRule);
 
-        Map<Integer, Map<String, List<Rule>>> result = splitRulesIntoIndexBuckets(ruleList);
+        Map<Integer, List<Rule>> result = splitRulesIntoIndexBuckets(ruleList);
 
         assertThat(result.keySet())
                 .containsExactly(NOT_INDEXED, PACKAGE_NAME_INDEXED, APP_CERTIFICATE_INDEXED);
         assertThat(result.get(PACKAGE_NAME_INDEXED)).isEmpty();
         assertThat(result.get(APP_CERTIFICATE_INDEXED)).isEmpty();
-        assertThat(result.get(NOT_INDEXED).keySet()).containsExactly("N/A");
-        assertThat(result.get(NOT_INDEXED).get("N/A")).containsExactly(negatedRule);
+        assertThat(result.get(NOT_INDEXED)).containsExactly(negatedRule);
     }
 
     @Test
-    public void getIndexType_allRulesTogether() {
+    public void getIndexType_allRulesTogetherInValidOrder() {
+        Rule packageNameRuleA = getRuleWithPackageName("aaa");
+        Rule packageNameRuleB = getRuleWithPackageName("bbb");
+        Rule packageNameRuleC = getRuleWithPackageName("ccc");
+        Rule certificateRule1 = getRuleWithAppCertificate("cert1");
+        Rule certificateRule2 = getRuleWithAppCertificate("cert2");
+        Rule certificateRule3 = getRuleWithAppCertificate("cert3");
+
         List<Rule> ruleList = new ArrayList();
-        ruleList.add(RULE_WITH_PACKAGE_NAME);
-        ruleList.add(RULE_WITH_APP_CERTIFICATE);
+        ruleList.add(packageNameRuleB);
+        ruleList.add(packageNameRuleC);
+        ruleList.add(packageNameRuleA);
+        ruleList.add(certificateRule3);
+        ruleList.add(certificateRule2);
+        ruleList.add(certificateRule1);
         ruleList.add(RULE_WITH_INSTALLER_RESTRICTIONS);
         ruleList.add(RULE_WITH_NONSTRING_RESTRICTIONS);
 
-        Map<Integer, Map<String, List<Rule>>> result = splitRulesIntoIndexBuckets(ruleList);
+        Map<Integer, List<Rule>> result = splitRulesIntoIndexBuckets(ruleList);
 
         assertThat(result.keySet())
                 .containsExactly(NOT_INDEXED, PACKAGE_NAME_INDEXED, APP_CERTIFICATE_INDEXED);
 
-        assertThat(result.get(PACKAGE_NAME_INDEXED).keySet()).containsExactly(SAMPLE_PACKAGE_NAME);
-        assertThat(result.get(PACKAGE_NAME_INDEXED).get(SAMPLE_PACKAGE_NAME))
-                .containsExactly(RULE_WITH_PACKAGE_NAME);
+        // We check asserts this way to ensure ordering based on package name.
+        assertThat(result.get(PACKAGE_NAME_INDEXED).get(0)).isEqualTo(packageNameRuleA);
+        assertThat(result.get(PACKAGE_NAME_INDEXED).get(1)).isEqualTo(packageNameRuleB);
+        assertThat(result.get(PACKAGE_NAME_INDEXED).get(2)).isEqualTo(packageNameRuleC);
+
+        // We check asserts this way to ensure ordering based on app certificate.
+        assertThat(result.get(APP_CERTIFICATE_INDEXED).get(0)).isEqualTo(certificateRule1);
+        assertThat(result.get(APP_CERTIFICATE_INDEXED).get(1)).isEqualTo(certificateRule2);
+        assertThat(result.get(APP_CERTIFICATE_INDEXED).get(2)).isEqualTo(certificateRule3);
 
-        assertThat(result.get(APP_CERTIFICATE_INDEXED).keySet())
-                .containsExactly(SAMPLE_APP_CERTIFICATE);
-        assertThat(result.get(APP_CERTIFICATE_INDEXED).get(SAMPLE_APP_CERTIFICATE))
-                .containsExactly(RULE_WITH_APP_CERTIFICATE);
+        assertThat(result.get(NOT_INDEXED))
+                .containsExactly(
+                        RULE_WITH_INSTALLER_RESTRICTIONS,
+                        RULE_WITH_NONSTRING_RESTRICTIONS);
+    }
+
+    private Rule getRuleWithPackageName(String packageName) {
+        return new Rule(
+                new CompoundFormula(
+                        CompoundFormula.AND,
+                        Arrays.asList(
+                                new AtomicFormula.StringAtomicFormula(
+                                        AtomicFormula.PACKAGE_NAME,
+                                        packageName,
+                                        /* isHashedValue= */ false),
+                                ATOMIC_FORMULA_WITH_INSTALLER_NAME)),
+                Rule.DENY);
+    }
 
-        assertThat(result.get(NOT_INDEXED).keySet()).containsExactly("N/A");
-        assertThat(result.get(NOT_INDEXED).get("N/A")).containsExactly(
-                RULE_WITH_INSTALLER_RESTRICTIONS, RULE_WITH_NONSTRING_RESTRICTIONS);
+    private Rule getRuleWithAppCertificate(String certificate) {
+        return new Rule(
+                new CompoundFormula(
+                        CompoundFormula.AND,
+                        Arrays.asList(
+                                new AtomicFormula.StringAtomicFormula(
+                                        AtomicFormula.APP_CERTIFICATE,
+                                        certificate,
+                                        /* isHashedValue= */ false),
+                                ATOMIC_FORMULA_WITH_INSTALLER_NAME)),
+                Rule.DENY);
     }
 
     private Formula getInvalidFormula() {