Improve data separation test coverage

Two areas need better coverage:
1. Tests are not verifying that files in /data/vendor do not have the
core_data_file_type attribute.
2. No error is thrown if a type lives in both /data/vendor
/data/<not vendor>.

Bug: 72998741
Test: build all selinux policies on master (assert build time tests)
Test: build and boot Marlin and Taimen, verify no selinux denials and
    everything works as expected.

Change-Id: I133a068123139a599b9b81ddcc254616894621eb
(cherry picked from commit 55d5e28472ad9cd87da0b451d78555d8aae43bb8)
diff --git a/tests/policy.py b/tests/policy.py
index 2c4b0a6..b51ebf2 100644
--- a/tests/policy.py
+++ b/tests/policy.py
@@ -3,6 +3,7 @@
 import os
 import sys
 import platform
+import FcSort
 
 ###
 # Check whether the regex will match a file path starting with the provided
@@ -45,10 +46,26 @@
     __ExpandedRules = set()
     __Rules = set()
     __FcDict = None
+    __FcSorted = None
     __libsepolwrap = None
     __policydbP = None
     __BUFSIZE = 2048
 
+    def AssertPathTypesDoNotHaveAttr(self, MatchPrefix, DoNotMatchPrefix, Attr):
+        # Query policy for the types associated with Attr
+        TypesPol = self.QueryTypeAttribute(Attr, True)
+        # Search file_contexts to find types associated with input paths.
+        TypesFc = self.__GetTypesByFilePathPrefix(MatchPrefix, DoNotMatchPrefix)
+        violators = TypesFc.intersection(TypesPol)
+        ret = ""
+        if len(violators) > 0:
+            ret += "The following types on "
+            ret += " ".join(str(x) for x in sorted(MatchPrefix))
+            ret += " must not be associated with the "
+            ret += "\"" + Attr + "\" attribute: "
+            ret += " ".join(str(x) for x in sorted(violators)) + "\n"
+        return ret
+
     # Check that path prefixes that match MatchPrefix, and do not Match
     # DoNotMatchPrefix have the attribute Attr.
     # For example assert that all types in /sys, and not in /sys/kernel/debugfs
@@ -198,17 +215,50 @@
         self.__libsepolwrap.destroy_type_iter(TypeIterP)
         return AllTypes
 
+    def __ExactMatchPathPrefix(self, pathregex, prefix):
+        pattern = re.compile('^' + pathregex + "$")
+        if pattern.match(prefix):
+            return True
+        return False
+
+    # Return a tuple (prefix, i) where i is the index of the most specific
+    # match of prefix in the sorted file_contexts. This is useful for limiting a
+    # file_contexts search to matches that are more specific and omitting less
+    # specific matches. For example, finding all matches to prefix /data/vendor
+    # should not include /data(/.*)? if /data/vendor(/.*)? is also specified.
+    def __FcSortedIndex(self, prefix):
+        index = 0
+        for i in range(0, len(self.__FcSorted)):
+            if self.__ExactMatchPathPrefix(self.__FcSorted[i].path, prefix):
+                index = i
+        return prefix, index
+
+    # Return a tuple of (path, Type) for all matching paths. Use the sorted
+    # file_contexts and index returned from __FcSortedIndex() to limit results
+    # to results that are more specific than the prefix.
+    def __MatchPathPrefixTypes(self, prefix, index):
+        PathType = []
+        for i in range(index, len(self.__FcSorted)):
+            if MatchPathPrefix(self.__FcSorted[i].path, prefix):
+                PathType.append((self.__FcSorted[i].path, self.__FcSorted[i].Type))
+        return PathType
+
+    # Return types that match MatchPrefixes but do not match
+    # DoNotMatchPrefixes
     def __GetTypesByFilePathPrefix(self, MatchPrefixes, DoNotMatchPrefixes):
         Types = set()
-        for Type in self.__FcDict:
-            for pathregex in self.__FcDict[Type]:
-                if not MatchPathPrefixes(pathregex, MatchPrefixes):
-                    continue
-                if MatchPathPrefixes(pathregex, DoNotMatchPrefixes):
-                    continue
-                Types.add(Type)
-        return Types
 
+        MatchPrefixesWithIndex = []
+        for MatchPrefix in MatchPrefixes:
+            MatchPrefixesWithIndex.append(self.__FcSortedIndex(MatchPrefix))
+
+        for MatchPrefixWithIndex in MatchPrefixesWithIndex:
+            PathTypes = self.__MatchPathPrefixTypes(*MatchPrefixWithIndex)
+            for PathType in PathTypes:
+                if MatchPathPrefixes(PathType[0], DoNotMatchPrefixes):
+                    continue
+                Types.add(PathType[1])
+        return Types
 
     def __GetTERules(self, policydbP, avtabIterP, Rules):
         if Rules is None:
@@ -313,6 +363,7 @@
                     self.__FcDict[t] = [rec[0]]
             except:
                 pass
+        self.__FcSorted = FcSort.FcSort(FcPaths)
 
     # load policy
     def __InitPolicy(self, PolicyPath):